summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/DependenceAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatibleChandler Carruth2015-09-091-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with the new pass manager, and no longer relying on analysis groups. This builds essentially a ground-up new AA infrastructure stack for LLVM. The core ideas are the same that are used throughout the new pass manager: type erased polymorphism and direct composition. The design is as follows: - FunctionAAResults is a type-erasing alias analysis results aggregation interface to walk a single query across a range of results from different alias analyses. Currently this is function-specific as we always assume that aliasing queries are *within* a function. - AAResultBase is a CRTP utility providing stub implementations of various parts of the alias analysis result concept, notably in several cases in terms of other more general parts of the interface. This can be used to implement only a narrow part of the interface rather than the entire interface. This isn't really ideal, this logic should be hoisted into FunctionAAResults as currently it will cause a significant amount of redundant work, but it faithfully models the behavior of the prior infrastructure. - All the alias analysis passes are ported to be wrapper passes for the legacy PM and new-style analysis passes for the new PM with a shared result object. In some cases (most notably CFL), this is an extremely naive approach that we should revisit when we can specialize for the new pass manager. - BasicAA has been restructured to reflect that it is much more fundamentally a function analysis because it uses dominator trees and loop info that need to be constructed for each function. All of the references to getting alias analysis results have been updated to use the new aggregation interface. All the preservation and other pass management code has been updated accordingly. The way the FunctionAAResultsWrapperPass works is to detect the available alias analyses when run, and add them to the results object. This means that we should be able to continue to respect when various passes are added to the pipeline, for example adding CFL or adding TBAA passes should just cause their results to be available and to get folded into this. The exception to this rule is BasicAA which really needs to be a function pass due to using dominator trees and loop info. As a consequence, the FunctionAAResultsWrapperPass directly depends on BasicAA and always includes it in the aggregation. This has significant implications for preserving analyses. Generally, most passes shouldn't bother preserving FunctionAAResultsWrapperPass because rebuilding the results just updates the set of known AA passes. The exception to this rule are LoopPass instances which need to preserve all the function analyses that the loop pass manager will end up needing. This means preserving both BasicAAWrapperPass and the aggregating FunctionAAResultsWrapperPass. Now, when preserving an alias analysis, you do so by directly preserving that analysis. This is only necessary for non-immutable-pass-provided alias analyses though, and there are only three of interest: BasicAA, GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is preserved when needed because it (like DominatorTree and LoopInfo) is marked as a CFG-only pass. I've expanded GlobalsAA into the preserved set everywhere we previously were preserving all of AliasAnalysis, and I've added SCEVAA in the intersection of that with where we preserve SCEV itself. One significant challenge to all of this is that the CGSCC passes were actually using the alias analysis implementations by taking advantage of a pretty amazing set of loop holes in the old pass manager's analysis management code which allowed analysis groups to slide through in many cases. Moving away from analysis groups makes this problem much more obvious. To fix it, I've leveraged the flexibility the design of the new PM components provides to just directly construct the relevant alias analyses for the relevant functions in the IPO passes that need them. This is a bit hacky, but should go away with the new pass manager, and is already in many ways cleaner than the prior state. Another significant challenge is that various facilities of the old alias analysis infrastructure just don't fit any more. The most significant of these is the alias analysis 'counter' pass. That pass relied on the ability to snoop on AA queries at different points in the analysis group chain. Instead, I'm planning to build printing functionality directly into the aggregation layer. I've not included that in this patch merely to keep it smaller. Note that all of this needs a nearly complete rewrite of the AA documentation. I'm planning to do that, but I'd like to make sure the new design settles, and to flesh out a bit more of what it looks like in the new pass manager first. Differential Revision: http://reviews.llvm.org/D12080 llvm-svn: 247167
* Fix how DependenceAnalysis calls delinearizationHal Finkel2015-08-191-17/+34
| | | | | | | | | | Fix how DependenceAnalysis calls delinearization, mirroring what is done in Delinearization.cpp (mostly by making sure to call getSCEVAtScope before delinearizing, and by removing the unnecessary 'Pairs == 1' check). Patch by Vaivaswatha Nagaraj! llvm-svn: 245408
* [PM] Port ScalarEvolution to the new pass manager.Chandler Carruth2015-08-171-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change makes ScalarEvolution a stand-alone object and just produces one from a pass as needed. Making this work well requires making the object movable, using references instead of overwritten pointers in a number of places, and other refactorings. I've also wired it up to the new pass manager and added a RUN line to a test to exercise it under the new pass manager. This includes basic printing support much like with other analyses. But there is a big and somewhat scary change here. Prior to this patch ScalarEvolution was never *actually* invalidated!!! Re-running the pass just re-wired up the various other analyses and didn't remove any of the existing entries in the SCEV caches or clear out anything at all. This might seem OK as everything in SCEV that can uses ValueHandles to track updates to the values that serve as SCEV keys. However, this still means that as we ran SCEV over each function in the module, we kept accumulating more and more SCEVs into the cache. At the end, we would have a SCEV cache with every value that we ever needed a SCEV for in the entire module!!! Yowzers. The releaseMemory routine would dump all of this, but that isn't realy called during normal runs of the pipeline as far as I can see. To make matters worse, there *is* actually a key that we don't update with value handles -- there is a map keyed off of Loop*s. Because LoopInfo *does* release its memory from run to run, it is entirely possible to run SCEV over one function, then over another function, and then lookup a Loop* from the second function but find an entry inserted for the first function! Ouch. To make matters still worse, there are plenty of updates that *don't* trip a value handle. It seems incredibly unlikely that today GVN or another pass that invalidates SCEV can update values in *just* such a way that a subsequent run of SCEV will incorrectly find lookups in a cache, but it is theoretically possible and would be a nightmare to debug. With this refactoring, I've fixed all this by actually destroying and recreating the ScalarEvolution object from run to run. Technically, this could increase the amount of malloc traffic we see, but then again it is also technically correct. ;] I don't actually think we're suffering from tons of malloc traffic from SCEV because if we were, the fact that we never clear the memory would seem more likely to have come up as an actual problem before now. So, I've made the simple fix here. If in fact there are serious issues with too much allocation and deallocation, I can work on a clever fix that preserves the allocations (while clearing the data) between each run, but I'd prefer to do that kind of optimization with a test case / benchmark that shows why we need such cleverness (and that can test that we actually make it faster). It's possible that this will make some things faster by making the SCEV caches have higher locality (due to being significantly smaller) so until there is a clear benchmark, I think the simple change is best. Differential Revision: http://reviews.llvm.org/D12063 llvm-svn: 245193
* [PM/AA] Simplify the AliasAnalysis interface by removing a wrapperChandler Carruth2015-08-061-2/+2
| | | | | | | | | | | | | | | | around a DataLayout interface in favor of directly querying DataLayout. This wrapper specifically helped handle the case where this no DataLayout, but LLVM now requires it simplifynig all of this. I've updated callers to directly query DataLayout. This in turn exposed a bunch of places where we should have DataLayout readily available but don't which I've fixed. This then in turn exposed that we were passing DataLayout around in a bunch of arguments rather than making it readily available so I've also fixed that. No functionality changed. llvm-svn: 244189
* -Wdeprecated-clean: Fix cases of violating the rule of 5 in ways that are ↵David Blaikie2015-07-311-4/+3
| | | | | | deprecated in C++11 llvm-svn: 243788
* Move delinearization from SCEVAddRecExpr to ScalarEvolutionTobias Grosser2015-06-291-4/+4
| | | | | | | | | | The expressions we delinearize do not necessarily have to have a SCEVAddRecExpr at the outermost level. At this moment, the additional flexibility is not exploited in LLVM itself, but in Polly we will soon soonish use this functionality. For LLVM, this change should not affect existing functionality (which is covered by test/Analysis/Delinearization/) llvm-svn: 240952
* [PM/AA] Hoist the AliasResult enum out of the AliasAnalysis class.Chandler Carruth2015-06-221-9/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | This will allow classes to implement the AA interface without deriving from the class or referencing an internal enum of some other class as their return types. Also, to a pretty fundamental extent, concepts such as 'NoAlias', 'MayAlias', and 'MustAlias' are first class concepts in LLVM and we aren't saving anything by scoping them heavily. My mild preference would have been to use a scoped enum, but that feature is essentially completely broken AFAICT. I'm extremely disappointed. For example, we cannot through any reasonable[1] means construct an enum class (or analog) which has scoped names but converts to a boolean in order to test for the possibility of aliasing. [1]: Richard Smith came up with a "solution", but it requires class templates, and lots of boilerplate setting up the enumeration multiple times. Something like Boost.PP could potentially bundle this up, but even that would be quite painful and it doesn't seem realistically worth it. The enum class solution would probably work without the need for a bool conversion. Differential Revision: http://reviews.llvm.org/D10495 llvm-svn: 240255
* [DependenceAnalysis] Extend unifySubscriptType for handling coupled ↵Jingyue Wu2015-05-291-17/+53
| | | | | | | | | | | | | | | | | | | | | | | subscript groups. Summary: In continuation to an earlier commit to DependenceAnalysis.cpp by jingyue (r222100), the type for all subscripts in a coupled group need to be the same since constraints from one subscript may be propagated to another during testing. During testing, new SCEVs may be created and the operands for these need to be the same. This patch extends unifySubscriptType() to work on lists of subscript pairs, ensuring a common extended type for all of them. Test Plan: Added a test case to NonCanonicalizedSubscript.ll which causes dependence analysis to crash without this fix. All regression tests pass. Reviewers: spop, sebpop, jingyue Reviewed By: jingyue Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9698 llvm-svn: 238573
* [DependenceAnalysis] Fix for PR21585: collectUpperBound triggers assertsJames Molloy2015-05-151-2/+20
| | | | | | | | | | collectUpperBound hits an assertion when the back edge count is wider then the desired type. If that happens, truncate the backedge count. Patch by Philip Pfaffe! llvm-svn: 237439
* Fix a memory corruption in Dependency Analysis.Karthik Bhat2015-03-101-0/+2
| | | | | | | | | | This crash occurs due to memory corruption when trying to update dependency direction based on Constraints. This crash was observed during lnt regression of Polybench benchmark test case dynprog. Review: http://reviews.llvm.org/D8059 llvm-svn: 231788
* Fix a crash in Dependency Analysis.Karthik Bhat2015-03-101-6/+6
| | | | | | | | | | | | | | | | | | | | This crash in Dependency analysis is because we assume here that in case of UsefulGEP both source and destination have the same number of operands which may not be true. This incorrect assumption results in crash while populating Pairs. Fix the same. This crash was observed during lnt regression for code such as- struct s{ int A[10][10]; int C[10][10][10]; } S; void dep_constraint_crash_test(int k,int N) { for( int i=0;i<N;i++) for( int j=0;j<N;j++) S.A[0][0] = S.C[0][0][k]; } Review: http://reviews.llvm.org/D8162 llvm-svn: 231784
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-11/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* Reformat.NAKAMURA Takumi2015-03-051-14/+11
| | | | llvm-svn: 231336
* Revert r231103, "FullDependenceAnalysis: Avoid using the (deprecated in ↵NAKAMURA Takumi2015-03-051-22/+23
| | | | | | | | C++11) copy ctor" It is miscompiled on msc18. llvm-svn: 231335
* Revert r231104, "unique_ptrify FullDependenceAnalysis::DV", to appease msc18 ↵NAKAMURA Takumi2015-03-051-5/+9
| | | | | | C2280. llvm-svn: 231334
* unique_ptrify FullDependenceAnalysis::DVDavid Blaikie2015-03-031-9/+5
| | | | | | | Making this type a little harder to abuse (see workaround relating to use of the implicit copy ctor in the prior commit) llvm-svn: 231104
* FullDependenceAnalysis: Avoid using the (deprecated in C++11) copy ctorDavid Blaikie2015-03-031-23/+22
| | | | llvm-svn: 231103
* Add missing includes. make_unique proliferated everywhere.Benjamin Kramer2015-03-011-0/+1
| | | | llvm-svn: 230909
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-3/+3
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* [DependenceAnalysis] Allow subscripts of different typesJingyue Wu2014-11-161-4/+27
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: Several places in DependenceAnalysis assumes both SCEVs in a subscript pair share the same integer type. For instance, isKnownPredicate calls SE->getMinusSCEV(X, Y) which asserts X and Y share the same type. However, DependenceAnalysis fails to ensure this assumption when producing a subscript pair, causing tests such as NonCanonicalizedSubscript to crash. With this patch, DependenceAnalysis runs unifySubscriptType before producing any subscript pair, ensuring the assumption. Test Plan: Added NonCanonicalizedSubscript.ll on which DependenceAnalysis before the fix crashed because subscripts have different types. Reviewers: spop, sebpop, jingyue Reviewed By: jingyue Subscribers: eliben, meheff, llvm-commits Differential Revision: http://reviews.llvm.org/D6289 llvm-svn: 222100
* Reformat partially, where I touched for whitespace changes.NAKAMURA Takumi2014-10-281-9/+5
| | | | llvm-svn: 220773
* Untabify and whitespace cleanups.NAKAMURA Takumi2014-10-281-3/+3
| | | | llvm-svn: 220771
* Analysis: cleanupDylan Noblesmith2014-08-261-3/+2
| | | | | | Address review comments. llvm-svn: 216432
* Revert "Analysis: unique_ptr-ify DependenceAnalysis::collectCoeffInfo"Dylan Noblesmith2014-08-261-8/+8
| | | | | | This reverts commit r216358. llvm-svn: 216431
* Analysis: unique_ptr-ify DependenceAnalysis::collectCoeffInfoDylan Noblesmith2014-08-251-8/+8
| | | | llvm-svn: 216358
* Analysis: unique_ptr-ify DependenceAnalysis::dependsDylan Noblesmith2014-08-251-8/+8
| | | | llvm-svn: 216357
* Analysis: take a reference instead of pointerDylan Noblesmith2014-08-251-6/+5
| | | | | | This parameter is never null. llvm-svn: 216356
* remove BasePointer before delinearizingSebastian Pop2014-05-271-8/+13
| | | | | | | | | | No functional change is intended: instead of relying on the delinearization to come up with the base pointer as a remainder of the divisions in the delinearization, we just compute it from the array access and use that value. We substract the base pointer from the SCEV to be delinearized and that simplifies the work of the delinearizer. llvm-svn: 209692
* remove constant termsSebastian Pop2014-05-271-6/+7
| | | | | | | | | | | | | | | | | | | | | | The delinearization is needed only to remove the non linearity induced by expressions involving multiplications of parameters and induction variables. There is no problem in dealing with constant times parameters, or constant times an induction variable. For this reason, the current patch discards all constant terms and multipliers before running the delinearization algorithm on the terms. The only thing remaining in the term expressions are parameters and multiply expressions of parameters: these simplified term expressions are passed to the array shape recognizer that will not recognize constant dimensions anymore: these will be recognized as different strides in parametric subscripts. The only important special case of a constant dimension is the size of elements. Instead of relying on the delinearization to infer the size of an element, compute the element size from the base address type. This is a much more precise way of computing the element size than before, as we would have mixed together the size of an element with the strides of the innermost dimension. llvm-svn: 209691
* move findArrayDimensions to ScalarEvolutionSebastian Pop2014-05-091-1/+1
| | | | | | | we do not use the information from SCEVAddRecExpr to compute the shape of the array, so a better place for this function is in ScalarEvolution. llvm-svn: 208456
* split delinearization pass in 3 stepsSebastian Pop2014-05-071-34/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | To compute the dimensions of the array in a unique way, we split the delinearization analysis in three steps: - find parametric terms in all memory access functions - compute the array dimensions from the set of terms - compute the delinearized access functions for each dimension The first step is executed on all the memory access functions such that we gather all the patterns in which an array is accessed. The second step reduces all this information in a unique description of the sizes of the array. The third step is delinearizing each memory access function following the common description of the shape of the array computed in step 2. This rewrite of the delinearization pass also solves a problem we had with the previous implementation: because the previous algorithm was by induction on the structure of the SCEV, it would not correctly recognize the shape of the array when the memory access was not following the nesting of the loops: for example, see polly/test/ScopInfo/multidim_only_ivs_3d_reverse.ll ; void foo(long n, long m, long o, double A[n][m][o]) { ; ; for (long i = 0; i < n; i++) ; for (long j = 0; j < m; j++) ; for (long k = 0; k < o; k++) ; A[i][k][j] = 1.0; Starting with this patch we no longer delinearize access functions that do not contain parameters, for example in test/Analysis/DependenceAnalysis/GCD.ll ;; for (long int i = 0; i < 100; i++) ;; for (long int j = 0; j < 100; j++) { ;; A[2*i - 4*j] = i; ;; *B++ = A[6*i + 8*j]; these accesses will not be delinearized as the upper bound of the loops are constants, and their access functions do not contain SCEVUnknown parameters. llvm-svn: 208232
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-2/+2
| | | | | | | | | | definition below all the header #include lines, lib/Analysis/... edition. This one has a bit extra as there were *other* #define's before #include lines in addition to DEBUG_TYPE. I've sunk all of them as a block. llvm-svn: 206843
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-151-38/+38
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* [Modules] Move InstIterator out of the Support library, where it had noChandler Carruth2014-03-041-1/+1
| | | | | | | | | | | | | business. This header includes Function and BasicBlock and directly uses the interfaces of both classes. It has to do with the IR, it even has that in the name. =] Put it in the library it belongs to. This is one step toward making LLVM's Support library survive a C++ modules bootstrap. llvm-svn: 202814
* normalize the last delinearized dimensionSebastian Pop2014-02-211-2/+17
| | | | | | | | | | | | | | | | in the dependence test, we used to discard some information that the delinearization provides: the size of the innermost dimension of an array, i.e., the size of scalars stored in the array, and the remainder of the delinearization that provides the offset from which the array reads start, i.e., the base address of the array. To avoid losing this data in the rest of the data dependence analysis, the fix is to multiply the access function in the last delinearized dimension by its size, effectively making the size of the last dimension to always be in bytes, and then add the remainder of delinearization to the last subscript, effectively making the last subscript start at the base address of the array. llvm-svn: 201867
* fail delinearization when the size of subscripts differsSebastian Pop2014-02-211-1/+14
| | | | | | | | | | | Because the delinearization is not a global analysis pass, it will compute the delinearization independently of knowledge about the way the delinearization happened for other data accesses to the same array: the dependence analysis will only trigger the delinearization on a tuple of access functions, and thus delinearization may compute different subscripts sizes for a same array. When that happens the safest is to discard the delinearized information. llvm-svn: 201866
* Fix known typosAlp Toker2014-01-241-1/+1
| | | | | | | Sweep the codebase for common typos. Includes some changes to visible function names that were misspelt. llvm-svn: 200018
* Fix comment of findGCD.Mingjie Xing2014-01-071-2/+2
| | | | llvm-svn: 198660
* add more comments around the delinearization of arraysSebastian Pop2013-11-131-5/+16
| | | | llvm-svn: 194612
* delinearization of arraysSebastian Pop2013-11-121-0/+55
| | | | llvm-svn: 194527
* Remove extraneous semicolon.Jakub Staszak2013-08-061-1/+1
| | | | llvm-svn: 187806
* Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector ↵Craig Topper2013-07-141-1/+1
| | | | | | size. llvm-svn: 186274
* (no commit message)Preston Briggs2013-06-281-0/+5
| | | | llvm-svn: 185187
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-1/+1
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-2/+2
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Modified dump() to provide a littlePreston Briggs2012-11-301-32/+30
| | | | | | | | | more information for dependences between instructions that don't share a common loop. Updated the test results appropriately. llvm-svn: 168965
* Cleaned up a couple of comments.Preston Briggs2012-11-291-4/+4
| | | | llvm-svn: 168854
* Modified depends() to recognize that when all levels are "=" andPreston Briggs2012-11-271-1/+16
| | | | | | | | | there's no possible loo-independent dependence, then there's no dependence. Updated all test result appropriately. llvm-svn: 168719
* Modify depends(Src, Dst, PossiblyLoopIndependent).Preston Briggs2012-11-271-0/+3
| | | | | | | | | | If the Src and Dst are the same instruction, no loop-independent dependence is possible, so we force the PossiblyLoopIndependent flag to false. The test case results are updated appropriately. llvm-svn: 168678
* Corrects a problem where we reply exclusively of GEPs to drivePreston Briggs2012-11-211-69/+108
| | | | | | | | | | | | analysis. Better is to look for cases with useful GEPs and use them when possible. When a pair of useful GEPs is not available, use the raw SCEVs directly. This approach supports better analysis of pointer dereferencing. In parallel, all the test cases are updated appropriately. Cases where we have a store to *B++ can now be analyzed! llvm-svn: 168474
OpenPOWER on IntegriCloud