summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Remove an errant outer loop that contains nothing but an inner loop over ↵Nick Lewycky2014-09-011-58/+53
| | | | | | exactly the same elements. While no functionality is change intended (and hence there are no changes to tests), you don't want to skip this revision if bisecting for errors. llvm-svn: 216864
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-211-4/+5
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-201-5/+4
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* ScalarEvolution: Derive element size from the type of the loaded elementTobias Grosser2014-06-081-1/+1
| | | | | | | | | | Before, we where looking at the size of the pointer type that specifies the location from which to load the element. This did not make any sense at all. This change fixes a bug in the delinearization where we failed to delinerize certain load instructions. llvm-svn: 210435
* implement missing SCEVDivision caseSebastian Pop2014-05-291-0/+9
| | | | | | | | without this case we would end on an infinite recursion: the remainder is zero, so Numerator - Remainder is equal to Numerator and so we would recursively ask for the division of Numerator by Denominator. llvm-svn: 209838
* fail to find dimensions when ElementSize is nullptrSebastian Pop2014-05-291-1/+1
| | | | | | | | when ScalarEvolution::getElementSize returns nullptr it is safe to early return in ScalarEvolution::findArrayDimensions such that we avoid later problems when we try to divide the terms by ElementSize. llvm-svn: 209837
* avoid type mismatch when building SCEVsSebastian Pop2014-05-271-0/+26
| | | | | | | | | | | This is a corner case I have stumbled upon when dealing with ARM64 type conversions. I was not able to extract a testcase for the community codebase to fail on. The patch conservatively discards a division that would have ended up in an ICE due to a type mismatch when building a multiply expression. I have also added code to a place that builds add expressions and in which we should be careful not to pass in operands of different types. llvm-svn: 209694
* do not use the GCD to compute the delinearization stridesSebastian Pop2014-05-271-59/+8
| | | | | | | | | | | We do not need to compute the GCD anymore after we removed the constant coefficients from the terms: the terms are now all parametric expressions and there is no need to recognize constant terms that divide only a subset of the terms. We only rely on the size of the terms, i.e., the number of operands in the multiply expressions, to sort the terms and recognize the parametric dimensions. llvm-svn: 209693
* remove BasePointer before delinearizingSebastian Pop2014-05-271-18/+17
| | | | | | | | | | 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-17/+71
| | | | | | | | | | | | | | | | | | | | | | 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
* Some cleanup for r209568.Michael Zolotukhin2014-05-261-9/+7
| | | | llvm-svn: 209634
* Implement sext(C1 + C2*X) --> sext(C1) + sext(C2*X) andMichael Zolotukhin2014-05-241-0/+35
| | | | | | | | | | | sext{C1,+,C2} --> sext(C1) + sext{0,+,C2} transformation in Scalar Evolution. That helps SLP-vectorizer to recognize consecutive loads/stores. <rdar://problem/14860614> llvm-svn: 209568
* Fix and improve SCEV ComputeBackedgeTankCount.Andrew Trick2014-05-231-19/+46
| | | | | | | | | | | | | This is a follow-up to r209358: PR19799: Indvars miscompile due to an incorrect max backedge taken count from SCEV. That fix was incomplete as pointed out by Arnold and Michael Z. The code was also too confusing. It needed a careful rewrite with more unit tests. This version will also happen to optimize more cases. <rdar://17005101> PR19799: Indvars miscompile... llvm-svn: 209545
* ScalarEvolution: Fix handling of AddRecs in isKnownPredicateJustin Bogner2014-05-231-12/+24
| | | | | | | | | | | | | ScalarEvolution::isKnownPredicate() can wrongly reduce a comparison when both the LHS and RHS are SCEVAddRecExprs. This checks that both LHS and RHS are guarded in the case when both are SCEVAddRecExprs. The test case is against indvars because I could not find a way to directly test SCEV. Patch by Sanjay Patel! llvm-svn: 209487
* Fix a bug in SCEV's backedge taken count computation from my prior fix in Jan.Andrew Trick2014-05-221-8/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This has to do with the trip count computation for loops with multiple exits, which is quite subtle. Most passes just ask for a single trip count number, so we must be conservative assuming any exit could be taken. Normally, we rely on the "exact" trip count, which was correctly given as "unknown". However, SCEV also gives a "max" back-edge taken count. The loops max BE taken count is conservatively a maximum over the max of each exit's non-exiting iterations count. Note that some exit tests can be skipped so the max loop back-edge taken count can actually exceed the max non-exiting iterations for some exits. However, when we know the loop *latch* cannot be skipped, we can directly use its max taken count disregarding other exits. I previously took the minimum here without checking whether the other exit could be skipped. The correct, and simpler thing to do here is just to directly use the loop latch's max non-exiting iterations as the loops max back-edge count. In the problematic test case, the first loop exit had a max of zero non-exiting iterations, but could be skipped. The loop latch was known not to be skipped but had max of one non-exiting iteration. We incorrectly claimed the loop back-edge could be taken zero times, when it is actually taken one time. Fixes Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count. Loop %for.body.i: max backedge-taken count is 1. llvm-svn: 209358
* Rename ComputeMaskedBits to computeKnownBits. "Masked" has beenJay Foad2014-05-141-4/+4
| | | | | | inappropriate since it lost its Mask parameter in r154011. llvm-svn: 208811
* use nullptr instead of NULLSebastian Pop2014-05-121-4/+4
| | | | llvm-svn: 208622
* do not assert when delinearization failsSebastian Pop2014-05-121-8/+30
| | | | llvm-svn: 208615
* use isZero()Sebastian Pop2014-05-121-6/+5
| | | | llvm-svn: 208614
* SCEV: Use range-based for loop and fold variable into assert.Benjamin Kramer2014-05-101-6/+4
| | | | llvm-svn: 208476
* move findArrayDimensions to ScalarEvolutionSebastian Pop2014-05-091-9/+9
| | | | | | | 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
* fix typo in debug messageSebastian Pop2014-05-091-2/+2
| | | | llvm-svn: 208455
* Correct formatting.Tobias Grosser2014-05-081-4/+4
| | | | | | | | Sorry for the commit spam. My clang-format crashed on me and the vim plugin did not print an error, but instead just left the formatting untouched. llvm-svn: 208358
* Use std::remove_if to remove elements from a vectorTobias Grosser2014-05-081-5/+4
| | | | | Suggested-by: Benjamin Kramer <benny.kra@gmail.com> llvm-svn: 208357
* Revert "SCEV: Use I = vector<>.erase(I) to iterate and delete at the same time"Tobias Grosser2014-05-081-3/+6
| | | | | | as committed in r208282. The original commit was incorrect. llvm-svn: 208286
* SCEV: Use I = vector<>.erase(I) to iterate and delete at the same timeTobias Grosser2014-05-081-6/+3
| | | | llvm-svn: 208282
* avoid segfaultingSebastian Pop2014-05-071-2/+1
| | | | | | *Quotient and *Remainder don't have to be initialized. llvm-svn: 208238
* do not collect undef termsSebastian Pop2014-05-071-1/+36
| | | | llvm-svn: 208237
* split delinearization pass in 3 stepsSebastian Pop2014-05-071-361/+457
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [C++11] Add NArySCEV->Operands iterator rangeTobias Grosser2014-05-071-8/+6
| | | | llvm-svn: 208158
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+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-63/+66
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* divide by the result of the gcdSebastian Pop2014-04-081-1/+1
| | | | | | used to fail with 'Step should divide Start with no remainder.' llvm-svn: 205802
* handle special cases when findGCD returns 1Sebastian Pop2014-04-081-1/+6
| | | | | | used to fail with 'Step should divide Start with no remainder.' llvm-svn: 205801
* in findGCD of multiply expr return the gcdSebastian Pop2014-04-081-2/+4
| | | | | | we used to return 1 instead of the gcd llvm-svn: 205800
* ScalarEvolution: Compute exit counts for loops with a power-of-2 step.Benjamin Kramer2014-03-251-0/+10
| | | | | | | | | | | | | If we have a loop of the form for (unsigned n = 0; n != (k & -32); n += 32) {} then we know that n is always divisible by 32 and the loop must terminate. Even if we have a condition where the loop counter will overflow it'll always hold this invariant. PR19183. Our loop vectorizer creates this pattern and it's also occasionally formed by loop counters derived from pointers. llvm-svn: 204728
* Remove some dead assignements found by scan-buildArnaud A. de Grandmaison2014-03-151-6/+1
| | | | llvm-svn: 204013
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-10/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* Add missing parenthesis in SCEV commentTobias Grosser2014-03-051-1/+1
| | | | | Contributed-by: Michael Zolutukin <mzolotukhin@apple.com> llvm-svn: 202963
* [Modules] Move the ConstantRange class into the IR library. This isChandler Carruth2014-03-041-1/+1
| | | | | | | | | | a bit surprising, as the class is almost entirely abstracted away from any particular IR, however it encodes the comparsion predicates which mutate ranges as ICmp predicate codes. This is reasonable as they're used for both instructions and constants. Thus, it belongs in the IR library with instructions and constants. llvm-svn: 202838
* [Modules] Move GetElementPtrTypeIterator into the IR library. As itsChandler Carruth2014-03-041-1/+1
| | | | | | | | | name might indicate, it is an iterator over the types in an instruction in the IR.... You see where this is going. Another step of modularizing the support library. llvm-svn: 202815
* [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
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-2/+2
| | | | | | Remove the old functions. llvm-svn: 202636
* Make DataLayout a plain object, not a pass.Rafael Espindola2014-02-251-1/+2
| | | | | | | Instead, have a DataLayoutPass that holds one. This will allow parts of LLVM don't don't handle passes to also use DataLayout. llvm-svn: 202168
* fix a corner case in delinearizationSebastian Pop2014-02-211-24/+15
| | | | | | handle special cases Step==1, Step==-1, GCD==1, and GCD==-1 llvm-svn: 201868
* Rename some member variables from TD to DL.Rafael Espindola2014-02-181-28/+28
| | | | | | TargetData was renamed DataLayout back in r165242. llvm-svn: 201581
* SCEV: Cast switched values to make -Wswitch more useful.Benjamin Kramer2014-02-111-16/+16
| | | | llvm-svn: 201170
* ScalarEvolution: Analyze trip count of loops with a switch guarding the exit.Benjamin Kramer2014-02-111-15/+53
| | | | llvm-svn: 201159
* Fix crasher introduced in r200203 and caught by a libc++ buildbot. Don't ↵Nick Lewycky2014-01-271-1/+3
| | | | | | assume that getMulExpr returns a SCEVMulExpr, it may have simplified it to something else! llvm-svn: 200210
* Teach SCEV to handle more cases of 'and X, CST', specifically where CST is ↵Nick Lewycky2014-01-271-22/+84
| | | | | | | | | | any number of contiguous 1 bits in a row, with any number of leading and trailing 0 bits. Unfortunately, this in turn led to some lower quality SCEVs due to some different paths through expression simplification, so add getUDivExactExpr and use it. This fixes all instances of the problems that I found, but we can make that function smarter as necessary. Merge test "xor-and.ll" into "and-xor.ll" since I needed to update it anyways. Test 'nsw-offset.ll' analyzes a little deeper, %n now gets a scev in terms of %no instead of a SCEVUnknown. llvm-svn: 200203
OpenPOWER on IntegriCloud