summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* whitespaceAndrew Trick2011-03-091-18/+18
| | | | llvm-svn: 127340
* teach SCEV that the scale and addition of an inbounds gep don't NSW.Chris Lattner2011-02-131-2/+5
| | | | | | | This fixes a FIXME in scev-aa.ll (allowing a new no-alias result) and generally makes things more precise. llvm-svn: 125449
* Per discussion with Dan G, inbounds geps *certainly* can haveChris Lattner2011-02-111-3/+14
| | | | | | | | | | | unsigned overflow (e.g. "gep P, -1"), and while they can have signed wrap in theoretical situations, modelling an AddRec as not having signed wrap is going enough for any case we can think of today. In the future if this isn't enough, we can revisit this. Modeling them as having NUW isn't causing any known problems either FWIW. llvm-svn: 125410
* Fix memory corruption. If one of the SCEV creation functions calls another butNick Lewycky2011-01-261-0/+2
| | | | | | | doesn't return immediately after then the insert position in UniqueSCEVs will be out of date. No test because this is a memory corruption issue. Fixes PR9051! llvm-svn: 124282
* Add a comment.Dan Gohman2011-01-241-0/+1
| | | | llvm-svn: 124126
* Simplify some code with no functionality change. Make the test a lot moreNick Lewycky2011-01-231-12/+4
| | | | | | robust against smarter optimizations, using the power of FileCheck. llvm-svn: 124081
* Use value ranges to fold ext(trunc) in SCEV when possible.Nick Lewycky2011-01-231-0/+34
| | | | llvm-svn: 124062
OpenPOWER on IntegriCloud