summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCEVExpand] do not hoist divisions by zero (PR30935)Sebastian Pop2016-12-122-31/+59
| | | | | | | | | | | | | | | SCEVExpand computes the insertion point for the components of a SCEV to be code generated. When it comes to generating code for a division, SCEVexpand would not be able to check (at compilation time) all the conditions necessary to avoid a division by zero. The patch disables hoisting of expressions containing divisions by anything other than non-zero constants in order to avoid hoisting these expressions past conditions that should hold before doing the division. The patch passes check-all on x86_64-linux. Differential Revision: https://reviews.llvm.org/D27216 llvm-svn: 289412
* [TBAA] Don't generate invalid TBAA when merging nodesSanjoy Das2016-12-111-1/+5
| | | | | | | | | | | | | | Summary: Fix a corner case in `MDNode::getMostGenericTBAA` where we can sometimes generate invalid TBAA metadata. Reviewers: chandlerc, hfinkel, mehdi_amini, manmanren Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D26635 llvm-svn: 289403
* [SCEVExpander] Explicitly expand AddRec starts into loop preheaderSanjoy Das2016-12-111-5/+8
| | | | | | | | | | | | | | | | This is NFC today, but won't be once D27216 (or an equivalent patch) is in. This change fixes a design problem in SCEVExpander -- it relied on a hoisting optimization to generate correct code for add recurrences. This meant changing the hoisting optimization to not kick in under certain circumstances (to avoid speculating faulting instructions, say) would break correctness. The fix is to make the correctness requirements explicit, and have it not rely on the hoisting optimization for correctness. llvm-svn: 289397
* [InstSimplify] improve function name; NFCSanjay Patel2016-12-101-4/+6
| | | | llvm-svn: 289332
* [PM] Support invalidation of inner analysis managers from a pass over the ↵Chandler Carruth2016-12-102-3/+104
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | outer IR unit. Summary: This never really got implemented, and was very hard to test before a lot of the refactoring changes to make things more robust. But now we can test it thoroughly and cleanly, especially at the CGSCC level. The core idea is that when an inner analysis manager proxy receives the invalidation event for the outer IR unit, it needs to walk the inner IR units and propagate it to the inner analysis manager for each of those units. For example, each function in the SCC needs to get an invalidation event when the SCC gets one. The function / module interaction is somewhat boring here. This really becomes interesting in the face of analysis-backed IR units. This patch effectively handles all of the CGSCC layer's needs -- both invalidating SCC analysis and invalidating function analysis when an SCC gets invalidated. However, this second aspect doesn't really handle the LoopAnalysisManager well at this point. That one will need some change of design in order to fully integrate, because unlike the call graph, the entire function behind a LoopAnalysis's results can vanish out from under us, and we won't even have a cached API to access. I'd like to try to separate solving the loop problems into a subsequent patch though in order to keep this more focused so I've adapted them to the API and updated the tests that immediately fail, but I've not added the level of testing and validation at that layer that I have at the CGSCC layer. An important aspect of this change is that the proxy for the FunctionAnalysisManager at the SCC pass layer doesn't work like the other proxies for an inner IR unit as it doesn't directly manage the FunctionAnalysisManager and invalidation or clearing of it. This would create an ever worsening problem of dual ownership of this responsibility, split between the module-level FAM proxy and this SCC-level FAM proxy. Instead, this patch changes the SCC-level FAM proxy to work in terms of the module-level proxy and defer to it to handle much of the updates. It only does SCC-specific invalidation. This will become more important in subsequent patches that support more complex invalidaiton scenarios. Reviewers: jlebar Subscribers: mehdi_amini, mcrosier, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D27197 llvm-svn: 289317
* [Analysis] Fix typo in comment. NFCCraig Topper2016-12-091-1/+1
| | | | llvm-svn: 289171
* [LCG] Minor cleanup to the LCG walk over a function, NFC.Chandler Carruth2016-12-091-19/+22
| | | | | | | | This just hoists the check for declarations up a layer which allows various sets used in the walk to be smaller. Also moves the relevant comments to match, and catches a few other cleanups in this code. llvm-svn: 289163
* [InstSimplify] Add "X / 1.0" to SimplifyFDivInst.Zia Ansari2016-12-081-0/+6
| | | | | | Differential Revision: https://reviews.llvm.org/D27587 llvm-svn: 289153
* IR, X86: Understand !absolute_symbol metadata on global variables.Peter Collingbourne2016-12-081-4/+4
| | | | | | | | | | | | | | | | | Summary: Attaching !absolute_symbol to a global variable does two things: 1) Marks it as an absolute symbol reference. 2) Specifies the value range of that symbol's address. Teach the X86 backend to allow absolute symbols to appear in place of immediates by extending the relocImm and mov64imm32 matchers. Start using relocImm in more places where it is legal. As previously proposed on llvm-dev: http://lists.llvm.org/pipermail/llvm-dev/2016-October/105800.html Differential Revision: https://reviews.llvm.org/D25878 llvm-svn: 289087
* ConstantFolding: Don't crash when encountering vector GEPKeno Fischer2016-12-081-3/+4
| | | | | | | | | | | | | | ConstantFolding tried to cast one of the scalar indices to a vector type. Instead, use the vector type only for the first index (which is the only one allowed to be a vector) and use its scalar type otherwise. Fixes PR31250. Reviewers: majnemer Differential Revision: https://reviews.llvm.org/D27389 llvm-svn: 289073
* InstCombine: Fold bitcast of vector to FP scalarMatt Arsenault2016-12-071-23/+25
| | | | llvm-svn: 288978
* Reintroduce a check accidentally removed in 288873 to fix clang botsPhilip Reames2016-12-071-4/+12
| | | | | | I believe this is the cause of the failure, but have not been able to confirm. Note that this is a speculative fix; I'm still waiting for a full build to finish as I synced and ended up doing a clean build which takes 20+ minutes on my machine. llvm-svn: 288886
* Fix a warning introduced in r288874Philip Reames2016-12-071-1/+0
| | | | llvm-svn: 288884
* [LCG] Add basic verification of the parent set and fix bugs it uncovers.Chandler Carruth2016-12-071-4/+23
| | | | | | The existing unittests actually cover this now that we verify things. llvm-svn: 288875
* [LVI] Remove used return value from markX functionsPhilip Reames2016-12-071-28/+26
| | | | llvm-svn: 288874
* [LVI] Simplify mergeIn codePhilip Reames2016-12-071-24/+20
| | | | | | Remove the unused return type, use early return, use assignment operator. llvm-svn: 288873
* [LVI] Simplify obfuscated codePhilip Reames2016-12-071-14/+0
| | | | | | It doesn't matter why something is overdefined if it is... llvm-svn: 288871
* [InstSimplify] fixed (?) to not mutate icmpsSanjay Patel2016-12-061-10/+4
| | | | | | | | | | | | | | As Eli noted in the post-commit thread for r288833, the use of swapOperands() may not be allowed in InstSimplify, so I'm removing those calls here pending further review. The swap mutates the icmp, and there doesn't appear to be precedent for instruction mutation in InstSimplify. I didn't actually have any tests for those cases, so I'm adding a few here. llvm-svn: 288855
* [InstSimplify] add folds for and-of-icmps with same operandsSanjay Patel2016-12-061-0/+33
| | | | | | | | | | | All of these (and a few more) are already handled by InstCombine, but we shouldn't have to wait until then to simplify these because they're cheap to deal with here in InstSimplify. This is the 'and' sibling of the earlier 'or' patch: https://reviews.llvm.org/rL288833 llvm-svn: 288841
* [InstSimplify] add folds for or-of-icmps with same operandsSanjay Patel2016-12-061-2/+34
| | | | | | | | All of these (and a few more) are already handled by InstCombine, but we shouldn't have to wait until then to simplify these because they're cheap to deal with here in InstSimplify. llvm-svn: 288833
* [LCG] Add some much needed asserts and verify runs to uncoverChandler Carruth2016-12-061-4/+12
| | | | | | | | | | | | | | | | | a hilarious bug and fix it. We somehow were never verifying the RefSCCs newly formed when splitting an existing one apart, and when verifying them we weren't really checking the SCC indices mapping effectively. If we had been, it would have been blindingly obvious that right after putting something int `RC.SCCs` we should update `RC.SCCIndices` instead of `SCCIndices` which we were about to clear and rebuild anyways. =[ Anyways, this is thoroughly covered by existing tests now that we actually verify things properly. llvm-svn: 288795
* [PM] Basic cleanups to CGSCC update code, NFC.Chandler Carruth2016-12-061-41/+36
| | | | | | | Just using InstIterator, simpler loop structures, and making better use of the visit callback infrastructure. llvm-svn: 288790
* [LVI] Remove dead code in mergeInPhilip Reames2016-12-061-18/+0
| | | | | | Integers are expressed in the lattice via constant ranges. They can never be represented by constants or not-constants; those are reserved for non-integer types. This code has been dead for literaly years. llvm-svn: 288767
* [LVI] Extract a helper functionPhilip Reames2016-12-061-32/+22
| | | | | | Extracting a helper function out of solveBlockValue makes the contract around the cache much easier to understand. llvm-svn: 288766
* [LVI] Hide the last markX function on LVILatticeValPhilip Reames2016-12-061-10/+10
| | | | | | This completes a small series of patches to hide the stateful updates of LVILatticeVal from the consuming code. The only remaining stateful API is mergeIn. llvm-svn: 288765
* [LVI] Hide a confusing internal interfacePhilip Reames2016-12-061-16/+19
| | | | llvm-svn: 288764
* [LVI] Remove duplicate code using existing helper functionPhilip Reames2016-12-061-6/+2
| | | | llvm-svn: 288761
* [LAA] Prevent invalid IR for loop-invariant bound in loop bodyKeno Fischer2016-12-051-7/+13
| | | | | | | | | | | | | | | | | | Summary: If LAA expands a bound that is loop invariant, but not hoisted out of the loop body, it used to use that value anyway, causing a non-domination error, because the memcheck block is of course not dominated by the scalar loop body. Detect this situation and expand the SCEV expression instead. Fixes PR31251 Reviewers: anemet Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D27397 llvm-svn: 288705
* [InstSimplify] add more helper functions for SimplifyICmpInst; NFCISanjay Patel2016-12-031-255/+288
| | | | llvm-svn: 288589
* [InstSimplify] add helper functions for SimplifyICmpInst; NFCISanjay Patel2016-12-031-112/+129
| | | | llvm-svn: 288588
* IR: Change PointerType to derive from Type rather than SequentialType.Peter Collingbourne2016-12-021-2/+2
| | | | | | | | | | | | | | | | | | | As proposed on llvm-dev: http://lists.llvm.org/pipermail/llvm-dev/2016-October/106640.html This is for a couple of reasons: - Values of type PointerType are unlike the other SequentialTypes (arrays and vectors) in that they do not hold values of the element type. By moving PointerType we can unify certain aspects of how the other SequentialTypes are handled. - PointerType will have no place in the SequentialType hierarchy once pointee types are removed, so this is a necessary step towards removing pointee types. Differential Revision: https://reviews.llvm.org/D26595 llvm-svn: 288462
* ConstantFolding: Factor code into helper functionMatt Arsenault2016-12-021-23/+34
| | | | llvm-svn: 288459
* IR: Change the gep_type_iterator API to avoid always exposing the "current" ↵Peter Collingbourne2016-12-024-9/+9
| | | | | | | | | | | | | type. Instead, expose whether the current type is an array or a struct, if an array what the upper bound is, and if a struct the struct type itself. This is in preparation for a later change which will make PointerType derive from Type rather than SequentialType. Differential Revision: https://reviews.llvm.org/D26594 llvm-svn: 288458
* Factor out common parts of LVI and Float2Int into ConstantRange [NFCI]Philip Reames2016-12-011-50/+4
| | | | | | | | | | This just extracts out the transfer rules for constant ranges into a single shared point. As it happens, neither bit of code actually overlaps in terms of the handled operators, but with this change that could easily be tweaked in the future. I also want to have this separated out to make experimenting with a eager value info implementation and possibly a ValueTracking-like fixed depth recursion peephole version. There's no reason all four of these can't share a common implementation which reduces the chances of bugs. Differential Revision: https://reviews.llvm.org/D27294 llvm-svn: 288413
* Object: Extract a ModuleSymbolTable class from IRObjectFile.Peter Collingbourne2016-12-011-3/+1
| | | | | | | | | | | | This class represents a symbol table built from in-memory IR. It provides access to GlobalValues and should only be used if such access is required (e.g. in the LTO implementation). We will eventually change IRObjectFile to read from a bitcode symbol table rather than using ModuleSymbolTable, so it would not be able to expose the module. Differential Revision: https://reviews.llvm.org/D27073 llvm-svn: 288319
* Revert previous whitespace changePhilip Reames2016-12-011-1/+0
| | | | llvm-svn: 288312
* Test commit of whitespace to check permissions.Philip Reames2016-12-011-0/+1
| | | | llvm-svn: 288311
* Fix some Clang-tidy and Include What You Use warnings; other minor fixes (NFC).Eugene Zelenko2016-11-301-1/+48
| | | | | | This preparation to remove SetVector.h dependency on SmallSet.h. llvm-svn: 288256
* [PM] Extend the explicit 'invalidate' method API on analysis results toChandler Carruth2016-11-281-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | accept an Invalidator that allows them to invalidate themselves if their dependencies are in turn invalidated. Rather than recording the dependency graph ahead of time when analysis get results from other analyses, this simply lets each result trigger the immediate invalidation of any analyses they actually depend on. They do this in a way that has three nice properties: 1) They don't have to handle transitive dependencies because the infrastructure will recurse for them. 2) The invalidate methods are still called only once. We just dynamically discover the necessary topological ordering, everything is memoized nicely. 3) The infrastructure still provides a default implementation and can access it so that only analyses which have dependencies need to do anything custom. To make this work at all, the invalidation logic also has to defer the deletion of the result objects themselves so that they can remain alive until we have collected the complete set of results to invalidate. A unittest is added here that has exactly the dependency pattern we are concerned with. It hit the use-after-free described by Sean in much detail in the long thread about analysis invalidation before this change, and even in an intermediate form of this change where we failed to defer the deletion of the result objects. There is an important problem with doing dependency invalidation that *isn't* solved here: we don't *enforce* that results correctly invalidate all the analyses whose results they depend on. I actually looked at what it would take to do that, and it isn't as hard as I had thought but the complexity it introduces seems very likely to outweigh the benefit. The technique would be to provide a base class for an analysis result that would be populated with other results, and automatically provide the invalidate method which immediately does the correct thing. This approach has some nice pros IMO: - Handles the case we care about and nothing else: only *results* that depend on other analyses trigger extra invalidation. - Localized to the result rather than centralized in the analysis manager. - Ties the storage of the reference to another result to the triggering of the invalidation of that analysis. - Still supports extending invalidation in customized ways. But the down sides here are: - Very heavy-weight meta-programming is needed to provide this base class. - Requires a pretty awful API for accessing the dependencies. Ultimately, I fear it will not pull its weight. But we can re-evaluate this at any point if we start discovering consistent problems where the invalidation and dependencies get out of sync. It will fit as a clean layer on top of the facilities in this patch that we can add if and when we need it. Note that I'm not really thrilled with the names for these APIs... The name "Invalidator" seems ok but not great. The method name "invalidate" also. In review some improvements were suggested, but they really need *other* uses of these terms to be updated as well so I'm going to do that in a follow-up commit. I'm working on the actual fixes to various analyses that need to use these, but I want to try to get tests for each of them so we don't regress. And those changes are seperable and obvious so once this goes in I should be able to roll them out throughout LLVM. Many thanks to Sean, Justin, and others for help reviewing here. Differential Revision: https://reviews.llvm.org/D23738 llvm-svn: 288077
* [PM] Remove weird marking of invalidated analyses as "preserved".Chandler Carruth2016-11-281-4/+8
| | | | | | | | | | | | | | | | | | | | | This never made a lot of sense. They've been invalidated for one IR unit but they aren't really preserved in any normal sense. It seemed like it would be an elegant way of communicating to outer IR units that pass managers and adaptors had already handled invalidation, but we've since ended up adding sets that model this more clearly: we're now using the 'AllAnalysesOn<IRUnitT>' set to handle cases where the trick of "preserving" invalidated analyses didn't work. This patch moves to rely on that technique exclusively and removes the cumbersome API aspect of updating the preserved set when doing invalidation. This in turn will simplify a *number* of upcoming patches. This has a side benefit of exposing a number of places where we were failing to mark the 'AllAnalysesOn<IRUnitT>' set as preserved. This patch fixes those, and with those fixes shouldn't change any observable behavior. llvm-svn: 288023
* [InstSimplify] allow integer vector types to use computeKnownBitsSanjay Patel2016-11-271-2/+2
| | | | | | | | Note that the non-splat lshr+lshr test folded, but that does not work in general. Something is missing or wrong in computeKnownBits as the non-splat shl+shl test still shows. llvm-svn: 288005
* [PM] Change the static object whose address is used to uniquely identifyChandler Carruth2016-11-2329-29/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | analyses to have a common type which is enforced rather than using a char object and a `void *` type when used as an identifier. This has a number of advantages. First, it at least helps some of the confusion raised in Justin Lebar's code review of why `void *` was being used everywhere by having a stronger type that connects to documentation about this. However, perhaps more importantly, it addresses a serious issue where the alignment of these pointer-like identifiers was unknown. This made it hard to use them in pointer-like data structures. We were already dodging this in dangerous ways to create the "all analyses" entry. In a subsequent patch I attempted to use these with TinyPtrVector and things fell apart in a very bad way. And it isn't just a compile time or type system issue. Worse than that, the actual alignment of these pointer-like opaque identifiers wasn't guaranteed to be a useful alignment as they were just characters. This change introduces a type to use as the "key" object whose address forms the opaque identifier. This both forces the objects to have proper alignment, and provides type checking that we get it right everywhere. It also makes the types somewhat less mysterious than `void *`. We could go one step further and introduce a truly opaque pointer-like type to return from the `ID()` static function rather than returning `AnalysisKey *`, but that didn't seem to be a clear win so this is just the initial change to get to a reliably typed and aligned object serving is a key for all the analyses. Thanks to Richard Smith and Justin Lebar for helping pick plausible names and avoid making this refactoring many times. =] And thanks to Sean for the super fast review! While here, I've tried to move away from the "PassID" nomenclature entirely as it wasn't really helping and is overloaded with old pass manager constructs. Now we have IDs for analyses, and key objects whose address can be used as IDs. Where possible and clear I've shortened this to just "ID". In a few places I kept "AnalysisID" to make it clear what was being identified. Differential Revision: https://reviews.llvm.org/D27031 llvm-svn: 287783
* [LCG] Add a previously missing assert about the relationship of RefSCCs.Chandler Carruth2016-11-221-0/+7
| | | | | | No intended change, everything seems to be in working order already. llvm-svn: 287705
* [LCG] Add utilities to compute parent and ascestor relationships betweenChandler Carruth2016-11-221-0/+58
| | | | | | | | | | | | | | | | | SCCs. These will be fairly expensive routines to call and might be abused in real code, but are quite useful when debugging or in asserts and are reasonable and well formed properties to query. I've used one of them in an assert that was requested in a code review here. In subsequent commits I'll start using these routines more heavily, for example in unittests etc. But this at least gets the groundwork in place. Differential Revision: https://reviews.llvm.org/D25506 llvm-svn: 287682
* Analysis: gep inbounds (gep inbounds (...)) is inbounds.Peter Collingbourne2016-11-221-2/+4
| | | | | | Differential Revision: https://reviews.llvm.org/D26441 llvm-svn: 287604
* [TLI] Fix breakage introduced by D21739.Marcin Koscielnicki2016-11-211-19/+19
| | | | | | | | | The initialize function has an early return for AMDGPU targets. If taken, the ShouldExtI32* initialization code will not be executed, resulting in invalid values in the corresponding fields. Fix this by moving the code to the top of the function. llvm-svn: 287570
* Fix known zero bits for addrspacecast.Yaxun Liu2016-11-211-1/+0
| | | | | | | | | | Currently LLVM assumes that a pointer addrspacecasted to a different addr space is equivalent to trunc or zext bitwise, which is not true. For example, in amdgcn target, when a null pointer is addrspacecasted from addr space 4 to 0, its value is changed from i64 0 to i32 -1. This patch teaches LLVM not to assume known bits of addrspacecast instruction to its operand. Differential Revision: https://reviews.llvm.org/D26803 llvm-svn: 287545
* [TLI] Add functions determining if int parameters/returns should be ↵Marcin Koscielnicki2016-11-211-2/+32
| | | | | | | | | | | | | | | zeroext/signext. On some architectures (s390x, ppc64, sparc64, mips), C-level int is passed as i32 signext instead of plain i32. Likewise, unsigned int may be passed as i32, i32 signext, or i32 zeroext depending on the platform. Add this information to TargetLibraryInfo, to be used whenever some LLVM pass inserts a compiler-rt call to a function involving int parameters or returns. Differential Revision: http://reviews.llvm.org/D21739 llvm-svn: 287533
* Fix comment typos. NFC.Simon Pilgrim2016-11-203-4/+4
| | | | | | Identified by Pedro Giffuni in PR27636. llvm-svn: 287490
* [SCEV] limit recursion depth of CompareSCEVComplexityDaniil Fukalov2016-11-171-17/+44
| | | | | | | | | | | | | | | Summary: CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time. Added cache of "equal" SCEV pairs to earlier cutoff of further estimation. Recursion depth limit was also introduced as a parameter. Reviewers: sanjoy Subscribers: mzolotukhin, tstellarAMD, llvm-commits Differential Revision: https://reviews.llvm.org/D26389 llvm-svn: 287232
OpenPOWER on IntegriCloud