summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Now that we look at all the header PHIs, we need to consider all the header PHIsNick Lewycky2011-10-241-6/+14
| | | | | | | when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142843
* Reapply r142781 with fix. Original message:Nick Lewycky2011-10-241-20/+32
| | | | | | | | | | | | | | | | | | | Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } llvm-svn: 142790
* PHI nodes not in the loop header aren't part of the loop iteration initialNick Lewycky2011-10-241-1/+1
| | | | | | | state. Furthermore, they might not have two operands. This fixes the underlying issue behind the crashes introduced in r142781. llvm-svn: 142788
* Speculatively revert r142781. Bots are showingNick Lewycky2011-10-241-32/+20
| | | | | | | Assertion `i_nocapture < OperandTraits<PHINode>::operands(this) && "getOperand() out of range!"' failed. coming out of indvars. llvm-svn: 142786
* Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in theNick Lewycky2011-10-231-20/+32
| | | | | | | | | | | | | | | | | | loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } llvm-svn: 142781
* Make SCEV's brute force analysis stronger in two ways. Firstly, we should beNick Lewycky2011-10-221-26/+145
| | | | | | | | | | | | | | | | able to constant fold load instructions where the argument is a constant. Second, we should be able to watch multiple PHI nodes through the loop; this patch only supports PHIs in loop headers, more can be done here. With this patch, we now constant evaluate: static const int arr[] = {1, 2, 3, 4, 5}; int test() { int sum = 0; for (int i = 0; i < 5; ++i) sum += arr[i]; return sum; } llvm-svn: 142731
* An instruction's operands aren't necessarily instructions or constants. TheyNick Lewycky2011-10-141-1/+2
| | | | | | | | could be arguments, for example. No testcase because this is a bug-fix broken out of a larger optimization patch. llvm-svn: 141951
* Fixes PR11070 - assert in SCEV getConstantEvolvingPHIOperands.Andrew Trick2011-10-051-16/+10
| | | | llvm-svn: 141219
* Typo. Thanks Bob.Andrew Trick2011-10-051-1/+1
| | | | llvm-svn: 141188
* Fix a broken assert found by -Wparentheses.Chandler Carruth2011-10-051-1/+1
| | | | llvm-svn: 141168
* Fix disabled SCEV analysis caused r141161 and add unit test.Andrew Trick2011-10-051-17/+32
| | | | | | | | I noticed during self-review that my previous checkin disabled some analysis. Even with the reenabled analysis the test case runs in about 5ms. Without the fix, it will take several minutes at least. llvm-svn: 141164
* Avoid exponential recursion in SCEV getConstantEvolvingPHI and ↵Andrew Trick2011-10-051-34/+82
| | | | | | | | | | EvaluateExpression. Note to compiler writers: never recurse on multiple instruction operands without memoization. Fixes rdar://10187945. Was taking 45s, now taking 5ms. llvm-svn: 141161
* The product of two chrec's can always be represented as a chrec.Nick Lewycky2011-10-041-32/+72
| | | | llvm-svn: 141066
* Reapply r140979 with fix! We never did get a testcase, but careful review of theNick Lewycky2011-10-031-4/+15
| | | | | | logic by David Meyer revealed this bug. llvm-svn: 140992
* Revert r140979 due to reports of bootstrap failure.Nick Lewycky2011-10-031-8/+4
| | | | llvm-svn: 140980
* Add one more case we compute a max trip count.Nick Lewycky2011-10-031-4/+8
| | | | llvm-svn: 140979
* indvars: generalize SCEV getPreStartForSignExtend.Andrew Trick2011-09-281-2/+14
| | | | | | | Handle general Add expressions to avoid leaving around redundant 32-bit IVs. llvm-svn: 140701
* Set NSW/NUW flags on SCEVAddExpr when the operation is flagged asAndrew Trick2011-09-101-1/+7
| | | | | | | | | | such. I'm doing this now for completeness because I can't think of/remember any reason that it was left out. I'm not sure it will help anything, but if we don't do it we need to explain why in comments. llvm-svn: 139450
* This transform only handles two-operand AddRec's. Prevent it from trying toNick Lewycky2011-09-061-13/+23
| | | | | | handle anything more complex. Fixes PR10383 again! llvm-svn: 139186
* Fix typo in comment again.Nick Lewycky2011-09-061-1/+1
| | | | llvm-svn: 139139
* Apparently we compile the code, not the comments. Thanks Eli!Nick Lewycky2011-09-061-2/+1
| | | | llvm-svn: 139138
* Fix typo in comment.Nick Lewycky2011-09-061-1/+1
| | | | llvm-svn: 139137
* Nope! I had it right the first time. Revert the operative part of r139135 andNick Lewycky2011-09-061-5/+8
| | | | | | add more showing of my work. llvm-svn: 139136
* Fix flipped sign. While there, show my math.Nick Lewycky2011-09-061-2/+9
| | | | llvm-svn: 139135
* No no no, fix typo properly!Nick Lewycky2011-09-061-2/+2
| | | | llvm-svn: 139134
* The logic inside getMulExpr to simplify {a,+,b}*{c,+,d} was wrong, which wasNick Lewycky2011-09-061-13/+20
| | | | | | | visible given a=b=c=d=1, on iteration #1 (the second iteration). Replace it with correct math. Fixes PR10383! llvm-svn: 139133
* Revert r139126 due to selfhost failures reported by buildbots.Nick Lewycky2011-09-061-6/+2
| | | | llvm-svn: 139130
* Teach SCEV to report a max backedge count in one interesting case inNick Lewycky2011-09-051-2/+6
| | | | | | HowFarToZero; the case for a canonical loop. llvm-svn: 139126
* Comment and clarifying assert.Andrew Trick2011-09-021-0/+1
| | | | llvm-svn: 139036
* Allow loop unrolling to get known trip counts from ScalarEvolution.Andrew Trick2011-08-111-0/+57
| | | | | | | | | | | | | SCEV unrolling can unroll loops with arbitrary induction variables. It is a prerequisite for -disable-iv-rewrite performance. It is also easily handles loops of arbitrary structure including multiple exits and is generally more robust. This is under a temporary option to avoid affecting default behavior for the next couple of weeks. It is needed so that I can checkin unit tests for updateUnloop. llvm-svn: 137384
* Made SCEV's UDiv expressions more canonical. When dividing aAndrew Trick2011-08-061-4/+21
| | | | | | | | | | | | | | | | | | | | | | | recurrence, the initial values low bits can sometimes be ignored. To take advantage of this, added FoldIVUser to IndVarSimplify to fold an IV operand into a udiv/lshr if the operator doesn't affect the result. -indvars -disable-iv-rewrite now transforms i = phi i4 i1 = i0 + 1 idx = i1 >> (2 or more) i4 = i + 4 into i = phi i4 idx = i0 >> ... i4 = i + 4 llvm-svn: 137013
* Use consistent terminology for loop exit/exiting blocks. Name change only.Andrew Trick2011-08-021-9/+9
| | | | llvm-svn: 136677
* SCEV: Added a data structure for storing not-taken info per loopAndrew Trick2011-07-261-127/+212
| | | | | | | exit. Added an interfaces for querying either the loop's exact/max backedge taken count or a specific loop exit's not-taken count. llvm-svn: 136100
* Use ArrayRef in ConstantFoldInstOperands and ConstantFoldCall.Jay Foad2011-07-191-3/+2
| | | | llvm-svn: 135477
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-71/+71
| | | | llvm-svn: 135375
* SCEV: missing null check fix for r132360, dragonegg crash.Andrew Trick2011-06-011-3/+3
| | | | llvm-svn: 132416
* scev: Better sign-extend removal. Normalize postincrement recurrencesAndrew Trick2011-05-311-31/+102
| | | | | | so that their sign extended forms are congruent when no overflow occurs. llvm-svn: 132360
* Change a few std::maps to DenseMaps.Dan Gohman2011-05-091-2/+2
| | | | llvm-svn: 131088
* Corrects an old, old typo in a case that doesn't seem to be reached in practice.Andrew Trick2011-04-271-1/+1
| | | | llvm-svn: 130316
* Test case and comment for PR9633.Andrew Trick2011-04-271-2/+3
| | | | llvm-svn: 130294
* Fix for PR9633 [indvars] Assertion `isa<X>(Val) && "cast<Ty>() argument of ↵Andrew Trick2011-04-271-2/+7
| | | | | | | | | incompatible type!"' failed. Added a type check in ScalarEvolution::computeSCEVAtScope to handle the case in which operands of an AddRecExpr in the current scope are folded. llvm-svn: 130271
* Fix an iterator invalidation bug.Dan Gohman2011-04-251-9/+16
| | | | llvm-svn: 130166
* Fix a ton of comment typos found by codespell. Patch byChris Lattner2011-04-151-1/+1
| | | | | | Luis Felipe Strano Moraes! llvm-svn: 129558
* Added isValidRewrite() to check the result of ScalarEvolutionExpander.Andrew Trick2011-03-171-0/+30
| | | | | | | | | SCEV may generate expressions composed of multiple pointers, which can lead to invalid GEP expansion. Until we can teach SCEV to follow strict pointer rules, make sure no bad GEPs creep into IR. Fixes rdar://problem/9038671. llvm-svn: 127839
* Remove getMinusSCEVForExitTest().Andrew Trick2011-03-151-106/+3
| | | | | | | This function performed acrobatics to prove no-self-wrap, which we now have for free. llvm-svn: 127643
* Propagate SCEV no-wrap flags whenever possible.Andrew Trick2011-03-151-60/+72
| | | | | | This needs review. llvm-svn: 127638
* Negating a recurrence preserves no-self-wrap.Andrew Trick2011-03-141-0/+11
| | | | llvm-svn: 127593
* HowFarToZero can compute a trip count as long as the recurrence has ↵Andrew Trick2011-03-141-16/+20
| | | | | | no-self-wrap. llvm-svn: 127591
* Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick2011-03-141-126/+187
| | | | | | | | | 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. llvm-svn: 127590
* When SCEV can determine the loop test is X < X, set ExactBECount=0.Andrew Trick2011-03-091-1/+17
| | | | | | | | When ExactBECount is a constant, use it for MaxBECount. When MaxBECount cannot be computed, replace it with ExactBECount. Fixes PR9424. llvm-svn: 127342
OpenPOWER on IntegriCloud