summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/DependenceAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* -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
* removes a few "const" qualifiersSebastian Pop2012-11-201-13/+13
| | | | | | | | | so that I can (someday) call SE->getSCEV without complaint. No semantic change intended. Patch from Preston Briggs <preston.briggs@gmail.com>. llvm-svn: 168391
* DependenceAnalysis: Print all dependency pairs when dumping. Update all ↵Benjamin Kramer2012-11-131-8/+5
| | | | | | | | testcases. Part of a patch by Preston Briggs. llvm-svn: 167827
* Fix a couple of comment typos.Benjamin Kramer2012-10-311-2/+2
| | | | llvm-svn: 167113
* DependenceAnalysis: Don't crash if there is no constant operand.Benjamin Kramer2012-10-311-3/+4
| | | | | | This makes the code match the comments. Resolves a crash in loop idiom (PR14219). llvm-svn: 167110
OpenPOWER on IntegriCloud