aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
AgeCommit message (Collapse)AuthorFilesLines
2011-07-26SCEV: Added a data structure for storing not-taken info per loopAndrew Trick1-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
2011-07-19Use ArrayRef in ConstantFoldInstOperands and ConstantFoldCall.Jay Foad1-3/+2
llvm-svn: 135477
2011-07-18land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner1-71/+71
llvm-svn: 135375
2011-06-01SCEV: missing null check fix for r132360, dragonegg crash.Andrew Trick1-3/+3
llvm-svn: 132416
2011-05-31scev: Better sign-extend removal. Normalize postincrement recurrencesAndrew Trick1-31/+102
so that their sign extended forms are congruent when no overflow occurs. llvm-svn: 132360
2011-05-09Change a few std::maps to DenseMaps.Dan Gohman1-2/+2
llvm-svn: 131088
2011-04-27Corrects an old, old typo in a case that doesn't seem to be reached in practice.Andrew Trick1-1/+1
llvm-svn: 130316
2011-04-27Test case and comment for PR9633.Andrew Trick1-2/+3
llvm-svn: 130294
2011-04-27Fix for PR9633 [indvars] Assertion `isa<X>(Val) && "cast<Ty>() argument of ↵Andrew Trick1-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
2011-04-25Fix an iterator invalidation bug.Dan Gohman1-9/+16
llvm-svn: 130166
2011-04-15Fix a ton of comment typos found by codespell. Patch byChris Lattner1-1/+1
Luis Felipe Strano Moraes! llvm-svn: 129558
2011-03-17Added isValidRewrite() to check the result of ScalarEvolutionExpander.Andrew Trick1-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
2011-03-15Remove getMinusSCEVForExitTest().Andrew Trick1-106/+3
This function performed acrobatics to prove no-self-wrap, which we now have for free. llvm-svn: 127643
2011-03-15Propagate SCEV no-wrap flags whenever possible.Andrew Trick1-60/+72
This needs review. llvm-svn: 127638
2011-03-14Negating a recurrence preserves no-self-wrap.Andrew Trick1-0/+11
llvm-svn: 127593
2011-03-14HowFarToZero can compute a trip count as long as the recurrence has ↵Andrew Trick1-16/+20
no-self-wrap. llvm-svn: 127591
2011-03-14Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick1-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
2011-03-09When SCEV can determine the loop test is X < X, set ExactBECount=0.Andrew Trick1-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
2011-03-09whitespaceAndrew Trick1-18/+18
llvm-svn: 127340
2011-02-13teach SCEV that the scale and addition of an inbounds gep don't NSW.Chris Lattner1-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
2011-02-11Per discussion with Dan G, inbounds geps *certainly* can haveChris Lattner1-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
2011-01-26Fix memory corruption. If one of the SCEV creation functions calls another butNick Lewycky1-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
2011-01-24Add a comment.Dan Gohman1-0/+1
llvm-svn: 124126
2011-01-23Simplify some code with no functionality change. Make the test a lot moreNick Lewycky1-12/+4
robust against smarter optimizations, using the power of FileCheck. llvm-svn: 124081
2011-01-23Use value ranges to fold ext(trunc) in SCEV when possible.Nick Lewycky1-0/+34
llvm-svn: 124062
2011-01-22Have SCEV turn sext(x) into zext(x) when x is s>= 0. This applies many times inNick Lewycky1-0/+4
"make check" alone. llvm-svn: 124046
2011-01-19Similarly, analyze truncate through multiply.Nick Lewycky1-0/+14
llvm-svn: 123842
2011-01-19Add a missed SCEV fold that is required to continue analyzing the IR producedNick Lewycky1-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
2011-01-19Add a missing SCEV simplification sext(zext x) --> zext x.Nick Lewycky1-0/+4
llvm-svn: 123832
2011-01-11some comment improvements.Chris Lattner1-3/+4
llvm-svn: 123243
2011-01-11Temporarily revert 123133, it's causing some regressions and I'm tryingEric Christopher1-8/+4
to get a testcase. llvm-svn: 123225
2011-01-11the GEP faq says that only inbounds geps are guaranteed to not overflow.Chris Lattner1-2/+3
llvm-svn: 123218
2011-01-09add a fixme: ir isn't expressive enough.Chris Lattner1-0/+1
llvm-svn: 123139
2011-01-09Step #4 in improving trip count analysis: HowFarToZero can analyzeChris Lattner1-2/+11
NUW AddRec's much more aggressively. We now get a trip count for @test2 in nsw.ll llvm-svn: 123138
2011-01-09rearrange some code, no functionality change.Chris Lattner1-41/+45
llvm-svn: 123136
2011-01-09Step #3 to improving trip count analysis: If we foldChris Lattner1-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
2011-01-09Step #2 to improve trip count analysis for loops like this:Chris Lattner1-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
2011-01-09teach SCEV analysis of PHI nodes that PHI recurences formedChris Lattner1-0/+5
with GEP instructions are always NUW, because PHIs cannot wrap the end of the address space. llvm-svn: 123105
2011-01-09reduce indentation. Print <nuw> and <nsw> when dumping SCEV AddRec'sChris Lattner1-49/+54
that have the bit set. llvm-svn: 123104
2010-12-07PR5207: Change APInt methods trunc(), sext(), zext(), sextOrTrunc() andJay Foad1-2/+2
zextOrTrunc(), and APSInt methods extend(), extOrTrunc() and new method trunc(), to be const and to return a new value instead of modifying the object in place. llvm-svn: 121120
2010-12-01PR5207: Rename overloaded APInt methods set(), clear(), flip() toJay Foad1-1/+1
setAllBits(), setBit(unsigned), etc. llvm-svn: 120564
2010-11-20Simplify code. No change in functionality.Benjamin Kramer1-2/+2
llvm-svn: 119908
2010-11-19Silence warning about an uninitialized variable.Benjamin Kramer1-1/+1
llvm-svn: 119800
2010-11-18Factor code for testing whether replacing one value with anotherDuncan Sands1-17/+2
preserves LCSSA form out of ScalarEvolution and into the LoopInfo class. Use it to check that SimplifyInstruction simplifications are not breaking LCSSA form. Fixes PR8622. llvm-svn: 119727
2010-11-18Introduce memoization for ScalarEvolution dominates and properlyDominatesDan Gohman1-58/+56
queries, and SCEVExpander getRelevantLoop queries. llvm-svn: 119595
2010-11-17Factor out the code for purging a SCEV from all the various memoization maps.Dan Gohman1-26/+13
Some of these maps may merge in the future, but for now it's convenient to have a utility function for them. llvm-svn: 119587
2010-11-17Merge the implementations of isLoopInvariant and hasComputableLoopEvolution, andDan Gohman1-71/+58
memoize the results. This improves compile time in code which highly complex expressions which get queried many times. llvm-svn: 119584
2010-11-17Make SCEV::getType() and SCEV::print non-virtual. Move SCEV::hasOperandDan Gohman1-105/+167
to ScalarEvolution. Delete SCEV::~SCEV. SCEV is no longer virtual. llvm-svn: 119578
2010-11-17Move SCEV::dominates and properlyDominates to ScalarEvolution.Dan Gohman1-58/+91
llvm-svn: 119570
2010-11-17Move SCEV::isLoopInvariant and hasComputableLoopEvolution to be memberDan Gohman1-81/+135
functions of ScalarEvolution, in preparation for memoization and other optimizations. llvm-svn: 119562
generated by cgit v1.1 at 2025-11-02 19:39:22 +0000