summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Have SCEV turn sext(x) into zext(x) when x is s>= 0. This applies many times inNick Lewycky2011-01-221-0/+4
| | | | | | "make check" alone. llvm-svn: 124046
* Similarly, analyze truncate through multiply.Nick Lewycky2011-01-191-0/+14
| | | | llvm-svn: 123842
* Add a missed SCEV fold that is required to continue analyzing the IR producedNick Lewycky2011-01-191-0/+14
| | | | | | | | | | | by indvars through the scev expander. trunc(add x, y) --> add(trunc x, y). Currently SCEV largely folds the other way which is probably wrong, but preserved to minimize churn. Instcombine doesn't do this fold either, demonstrating a missed optz'n opportunity on code doing add+trunc+add. llvm-svn: 123838
* Add a missing SCEV simplification sext(zext x) --> zext x.Nick Lewycky2011-01-191-0/+4
| | | | llvm-svn: 123832
* some comment improvements.Chris Lattner2011-01-111-3/+4
| | | | llvm-svn: 123243
* Temporarily revert 123133, it's causing some regressions and I'm tryingEric Christopher2011-01-111-8/+4
| | | | | | to get a testcase. llvm-svn: 123225
* the GEP faq says that only inbounds geps are guaranteed to not overflow.Chris Lattner2011-01-111-2/+3
| | | | llvm-svn: 123218
* add a fixme: ir isn't expressive enough.Chris Lattner2011-01-091-0/+1
| | | | llvm-svn: 123139
* Step #4 in improving trip count analysis: HowFarToZero can analyzeChris Lattner2011-01-091-2/+11
| | | | | | | NUW AddRec's much more aggressively. We now get a trip count for @test2 in nsw.ll llvm-svn: 123138
* rearrange some code, no functionality change.Chris Lattner2011-01-091-41/+45
| | | | llvm-svn: 123136
* Step #3 to improving trip count analysis: If we foldChris Lattner2011-01-091-4/+8
| | | | | | | | a + {b,+,stride} into {a+b,+,stride} (because a is LIV), then the resultant AddRec is NUW/NSW if the client says it is. llvm-svn: 123133
* Step #2 to improve trip count analysis for loops like this:Chris Lattner2011-01-091-6/+105
| | | | | | | | | | | | | | | | | | | void f(int* begin, int* end) { std::fill(begin, end, 0); } which turns into a != exit expression where one pointer is strided and (thanks to step #1) known to not overflow, and the other is loop invariant. The observation here is that, though the IV is strided by 4 in this case, that the IV *has* to become equal to the end value. It cannot "miss" the end value by stepping over it, because if it did, the strided IV expression would eventually wrap around. Handle this by turning A != B into "A-B != 0" where the A-B part is known to be NUW. llvm-svn: 123131
OpenPOWER on IntegriCloud