summaryrefslogtreecommitdiff
path: root/include/llvm/Analysis/ScalarEvolutionExpressions.h
Commit message (Collapse)AuthorAge
* remove BasePointer before delinearizingSebastian Pop2014-05-27
| | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209692 91177308-0d34-0410-b5e6-96231b3b80d8
* remove constant termsSebastian Pop2014-05-27
| | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209691 91177308-0d34-0410-b5e6-96231b3b80d8
* move findArrayDimensions to ScalarEvolutionSebastian Pop2014-05-09
| | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208456 91177308-0d34-0410-b5e6-96231b3b80d8
* split delinearization pass in 3 stepsSebastian Pop2014-05-07
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208232 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Add NArySCEV->Operands iterator rangeTobias Grosser2014-05-07
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208158 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-05
| | | | | | class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202945 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVRewriter: Optionally interpret constants in value map as SCEVConstantArnold Schwaighofer2014-01-10
| | | | | | | | | An upcoming loop vectorizer commit will want to replace a SCEVUnknown(Value*) by a SCEVConstant. This commit modifies the SCEVParameterRewriter to support this. The SCEVParameterRewriter constructor can optionally specify to follow this behavior. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@198949 91177308-0d34-0410-b5e6-96231b3b80d8
* delinearization of arraysSebastian Pop2013-11-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194527 91177308-0d34-0410-b5e6-96231b3b80d8
* remove virtual methods in SCEVApplyRewriter and SCEVParameterRewriterSebastian Pop2013-11-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194526 91177308-0d34-0410-b5e6-96231b3b80d8
* Pacify -Wnon-virtual-dtorMatt Beaumont-Gay2013-02-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175324 91177308-0d34-0410-b5e6-96231b3b80d8
* capitalize SCEV to match the current naming conventionSebastian Pop2013-02-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175302 91177308-0d34-0410-b5e6-96231b3b80d8
* add ScevApplyRewriterSebastian Pop2013-02-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175294 91177308-0d34-0410-b5e6-96231b3b80d8
* add SCEVParameterRewriterSebastian Pop2013-02-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175293 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix include guards so they exactly match file names.Jakub Staszak2013-01-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172025 91177308-0d34-0410-b5e6-96231b3b80d8
* Sort the #include lines for the include/... tree with the script.Chandler Carruth2012-12-03
| | | | | | | | | | AKA: Recompile *ALL* the source code! This one went much better. No manual edits here. I spot-checked for silliness and grep-checked for really broken edits and everything seemed good. It all still compiles. Yell if you see something that looks goofy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169133 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unnecessary classof()'sSean Silva2012-10-11
| | | | | | | isa<> et al. automatically infer when the cast is an upcast (including a self-cast), so these are no longer necessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165767 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru2012-09-27
| | | | | | See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164768 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a typo 'iff' => 'if'Sylvestre Ledru2012-09-27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164767 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVTraversal: Add a visited set.Andrew Trick2012-07-18
| | | | | | Expression trees may be DAGs. Make sure traversal has linear complexity. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160426 91177308-0d34-0410-b5e6-96231b3b80d8
* Factor SCEV traversal code so I can use it elsewhere. No functionality.Andrew Trick2012-07-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160203 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove dead code. Improve llvm_unreachable text. Simplify some control flow.Ahmed Charles2012-02-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150918 91177308-0d34-0410-b5e6-96231b3b80d8
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
* Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick2011-03-14
| | | | | | | | | | properties. Added the self-wrap flag for SCEV::AddRecExpr. A slew of temporary FIXMEs indicate the intention of the no-self-wrap flag without changing behavior in this revision. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127590 91177308-0d34-0410-b5e6-96231b3b80d8
* Make SCEV::getType() and SCEV::print non-virtual. Move SCEV::hasOperandDan Gohman2010-11-17
| | | | | | | to ScalarEvolution. Delete SCEV::~SCEV. SCEV is no longer virtual. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119578 91177308-0d34-0410-b5e6-96231b3b80d8
* Move SCEV::dominates and properlyDominates to ScalarEvolution.Dan Gohman2010-11-17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119570 91177308-0d34-0410-b5e6-96231b3b80d8
* Move SCEV::isLoopInvariant and hasComputableLoopEvolution to be memberDan Gohman2010-11-17
| | | | | | | | functions of ScalarEvolution, in preparation for memoization and other optimizations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119562 91177308-0d34-0410-b5e6-96231b3b80d8
* Verify SCEVAddRecExpr's invariant in ScalarEvolution::getAddRecExprDan Gohman2010-11-17
| | | | | | | | instead of in SCEVAddRecExpr's constructor, in preparation for an upcoming change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119554 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r111031. The way LLVM defines loop invariance, the property of anDan Gohman2010-08-16
| | | | | | | | | | expression being loop invariant is not equivalent to the property of properly dominating the loop header. Other optimizations have also made this optimization less important. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111160 91177308-0d34-0410-b5e6-96231b3b80d8
* Move SCEVNAryExpr's virtual member functions out of line, and convertDan Gohman2010-08-16
| | | | | | | them to iterators. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111140 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement hasComputableLoopEvolution for Add, Mul, and Trunc operators,Dan Gohman2010-08-13
| | | | | | | | since they can support trivial implementations. This avoids potentially expensive traversals of the operands. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111031 91177308-0d34-0410-b5e6-96231b3b80d8
* Make SCEVUnknown a CallbackVH, so that it can be notified directlyDan Gohman2010-08-02
| | | | | | | | | | | | of Value deletions and RAUWs, instead of relying on ScalarEvolution's Scalars map being notified, as that's complicated at best, and insufficient in general. This means SCEVUnknown needs a non-trivial destructor, so introduce a mechanism to allow ScalarEvolution to locate all the SCEVUnknowns. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110086 91177308-0d34-0410-b5e6-96231b3b80d8
* Speculatively revert r109705 since it seems to be causing some build botEric Christopher2010-07-29
| | | | | | | angst. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109718 91177308-0d34-0410-b5e6-96231b3b80d8
* Factor out some of the code for updating old SCEVUnknown values, andDan Gohman2010-07-29
| | | | | | | | | | extend it to handle the case where multiple RAUWs affect a single SCEVUnknown. Add a ScalarEvolution unittest to test for this situation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109705 91177308-0d34-0410-b5e6-96231b3b80d8
* Add some extra friend declarations to fix a gcc-4.0 compile error.Dan Gohman2010-07-28
| | | | | | | This is a temporary fix, until more elaborate changes are ready. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109593 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a comment.Dan Gohman2010-07-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109565 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r106304 (105548 and friends), which are the SCEVComplexityCompareDan Gohman2010-06-18
| | | | | | | optimizations. There is still some nondeterminism remaining. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106306 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply 105540, 105542, and 105548, and revert r105732.Dan Gohman2010-06-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106304 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert 105540, 105542, 105544, 105546, and 105548 to unbreak bootstrapping.Evan Cheng2010-06-09
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@105740 91177308-0d34-0410-b5e6-96231b3b80d8
* The FoldingSet hash data includes pointer values, so it isn'tDan Gohman2010-06-07
| | | | | | | | determinstic. Instead, give SCEV objects an arbitrary sequence number. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@105548 91177308-0d34-0410-b5e6-96231b3b80d8
* Add the ability to "intern" FoldingSetNodeID data into aDan Gohman2010-03-18
| | | | | | | | | | | | | BumpPtrAllocator-allocated region to allow it to be stored in a more compact form and to avoid the need for a non-trivial destructor call. Use this new mechanism in ScalarEvolution instead of FastFoldingSetNode to avoid leaking memory in the case where a FoldingSetNodeID uses heap storage, and to reduce overall memory usage. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98829 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply r98755 with a thinko which miscompiled gengtype fixed.Dan Gohman2010-03-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98793 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert 98755, which may be causing trouble.Dan Gohman2010-03-17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98762 91177308-0d34-0410-b5e6-96231b3b80d8
* Change SCEVNAryExpr's operand array from a SmallVector to a plainDan Gohman2010-03-17
| | | | | | | | | | | pointer and length, and allocate the arrays in ScalarEvolution's BumpPtrAllocator, so that they get released when their owning SCEV gets released. SCEVs are immutable, so they don't need to worry about operand array resizing. This fixes a memory leak reported in PR6637. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98755 91177308-0d34-0410-b5e6-96231b3b80d8
* Override dominates and properlyDominates for SCEVAddRecExpr, as aDan Gohman2010-02-13
| | | | | | | | SCEVAddRecExpr doesn't necessarily dominate blocks merely dominated by all of its operands. This fixes an abort compiling 403.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96056 91177308-0d34-0410-b5e6-96231b3b80d8
* Minor code simplification.Dan Gohman2010-02-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95780 91177308-0d34-0410-b5e6-96231b3b80d8
* Generalize target-independent folding rules for sizeof to handle moreDan Gohman2010-02-01
| | | | | | | | | | | | | | | | | | | | cases, and implement target-independent folding rules for alignof and offsetof. Also, reassociate reassociative operators when it leads to more folding. Generalize ScalarEvolution's isOffsetOf to recognize offsetof on arrays. Rename getAllocSizeExpr to getSizeOfExpr, and getFieldOffsetExpr to getOffsetOfExpr, for consistency with analagous ConstantExpr routines. Make the target-dependent folder promote GEP array indices to pointer-sized integers, to make implicit casting explicit and exposed to subsequent folding. And add a bunch of testcases for this new functionality, and a bunch of related existing functionality. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94987 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove SCEVAllocSizeExpr and SCEVFieldOffsetExpr, and in their placeDan Gohman2010-01-28
| | | | | | | | | | | | | | | | | use plain SCEVUnknowns with ConstantExpr::getSizeOf and ConstantExpr::getOffsetOf constants. This eliminates a bunch of special-case code. Also add code for pattern-matching these expressions, for clients that want to recognize them. Move ScalarEvolution's logic for expanding array and vector sizeof expressions into an element count times the element size, to expose the multiplication to subsequent folding, into the regular constant folder. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94737 91177308-0d34-0410-b5e6-96231b3b80d8
* Make SCEVAddRecExpr's getType return a pointer type when the addDan Gohman2010-01-19
| | | | | | | | has a pointer member. This helps reduce unnecessary bitcasting and uglygeps. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@93939 91177308-0d34-0410-b5e6-96231b3b80d8
* Add the ability to track HasNSW and HasNUW on more kinds of SCEV expressions.Dan Gohman2009-10-09
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83601 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a properlyDominates member function to ScalarEvolution.Dan Gohman2009-09-27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82898 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-09 17:05:50 +0000