summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* SCEV: Add MarkPendingLoopPredicates to avoid recursive isImpliedCond.Andrew Trick2012-05-191-0/+24
| | | | | | | | | | getUDivExpr attempts to simplify by checking for overflow. isLoopEntryGuardedByCond then evaluates the loop predicate which may lead to the same getUDivExpr causing endless recursion. Fixes PR12868: clang 3.2 segmentation fault. llvm-svn: 157092
* reuse the result of some expensive computations in getSignExtendExpr() and ↵Nuno Lopes2012-05-151-18/+20
| | | | | | | | getZeroExtendExpr() this gives a speedup of > 80 in a debug build in the test case of PR12825 (php_sha512_crypt_r) llvm-svn: 156849
* minor simplification to code: Ty is already a SCEV type; don't need to run ↵Nuno Lopes2012-05-151-6/+3
| | | | | | getEffectiveSCEVType() twice llvm-svn: 156823
* Rewrite ScalarEvolution::hasOperand to use an explicit worklist insteadDan Gohman2012-05-101-35/+50
| | | | | | of recursion, to avoid excessive stack usage on deep expressions. llvm-svn: 156554
* Revert "SCEV: When expanding a GEP the final addition to the base pointer ↵Benjamin Kramer2012-04-171-1/+1
| | | | | | | | has NUW but not NSW." This isn't right either, reverting for now. llvm-svn: 154910
* SCEV: When expanding a GEP the final addition to the base pointer has NUW ↵Benjamin Kramer2012-04-071-1/+1
| | | | | | | | but not NSW. Found by inspection. llvm-svn: 154262
* Always compute all the bits in ComputeMaskedBits.Rafael Espindola2012-04-041-6/+3
| | | | | | | | This allows us to keep passing reduced masks to SimplifyDemandedBits, but know about all the bits if SimplifyDemandedBits fails. This allows instcombine to simplify cases like the one in the included testcase. llvm-svn: 154011
* SCEV fix: Handle loop invariant loads.Andrew Trick2012-03-261-1/+5
| | | | | | Fixes PR11882: NULL dereference in ComputeLoadConstantCompareExitLimit. llvm-svn: 153480
* switch SCEV to use the new ConstantFoldLoadThroughGEPIndices functionChris Lattner2012-01-241-35/+3
| | | | | | | | instead of its own hard coded thing, allowing it to handle ConstantDataSequential and fixing some obscure bugs (e.g. it would previously crash on a CAZ of vector type). llvm-svn: 148788
* More dead code removal (using -Wunreachable-code)David Blaikie2012-01-201-22/+8
| | | | llvm-svn: 148578
* Remove obviously invalid early exit that prevented analyzing ↵Benjamin Kramer2012-01-201-1/+0
| | | | | | | | ConstantAggregateZeros. Found by the clang static analyzer. llvm-svn: 148540
* Clarified the SCEV getSmallConstantTripCount interface with in-your-face ↵Andrew Trick2012-01-111-9/+18
| | | | | | | | comments. This interface is misleading and dangerous, but it is actually what we need for unrolling. llvm-svn: 147926
* Expose isNonConstantNegative to users of ScalarEvolution.Andrew Trick2012-01-071-0/+14
| | | | llvm-svn: 147700
* Fix a few more places where TargetData/TargetLibraryInfo is not being passed.Chad Rosier2011-12-021-6/+7
| | | | | | Add FIXMEs to places that are non-trivial to fix. llvm-svn: 145661
* Last bit of TargetLibraryInfo propagation. Also fixed a case for TargetDataChad Rosier2011-12-011-9/+12
| | | | | | | where it appeared beneficial to pass. More of rdar://10500969 llvm-svn: 145630
* Propagate TargetLibraryInfo throughout ConstantFolding.cpp and Chad Rosier2011-12-011-1/+5
| | | | | | | InstructionSimplify.cpp. Other fixups as needed. Part of rdar://10500969 llvm-svn: 145559
* SCEV fix. In general, Add/Mul expressions should not inherit NSW/NUW.Andrew Trick2011-11-291-8/+8
| | | | | | | This reverts r139450, fixes r139453, and adds much needed comments and a unit test. llvm-svn: 145367
* Make SCEV print <nsw><nuw> for Add/MulExpr.Andrew Trick2011-11-291-0/+8
| | | | llvm-svn: 145364
* SCEV: Actually set overflow flags on add expressions.Benjamin Kramer2011-11-201-2/+2
| | | | | | setFlags doesn't modify its arguments. llvm-svn: 145007
* Fix SCEV overly optimistic back edge taken count for multi-exit loops.Andrew Trick2011-11-161-9/+22
| | | | | | Fixes PR11375: Different results for 'clang++ huh.cpp'... llvm-svn: 144746
* Don't try to loop on iterators that are potentially invalidated inside the ↵Nick Lewycky2011-11-121-0/+18
| | | | | | loop. Fixes PR11361! llvm-svn: 144454
* Don't forget to check FlagNW when determining whether an AddRecExpr will wrapNick Lewycky2011-11-091-2/+3
| | | | | | or not. Patch by Brendon Cahoon! llvm-svn: 144173
* Restore commits 142790 and 142843 - they weren't breaking the buildDuncan Sands2011-10-251-26/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | bots. Original commit messages: - Reapply r142781 with fix. Original message: 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; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142919
* Speculatively revert commits 142790 and 142843 to see if it fixesDuncan Sands2011-10-251-46/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | | the dragonegg and llvm-gcc self-host buildbots. Original commit messages: - Reapply r142781 with fix. Original message: 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; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142916
* 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
OpenPOWER on IntegriCloud