Similarly, analyze truncate through multiply.

llvm-svn: 123842

Add a missed SCEV fold that is required to continue analyzing the IR produced
by indvars through the scev expander.

trunc(add x, y) --> add(trunc x, y). Currently SCEV largely folds the other way
wh

Add a missed SCEV fold that is required to continue analyzing the IR produced
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

show more ...

Add a missing SCEV simplification sext(zext x) --> zext x.

llvm-svn: 123832

some comment improvements.

llvm-svn: 123243

Temporarily revert 123133, it's causing some regressions and I'm trying
to get a testcase.

llvm-svn: 123225

the GEP faq says that only inbounds geps are guaranteed to not overflow.

llvm-svn: 123218

add a fixme: ir isn't expressive enough.

llvm-svn: 123139

Step #4 in improving trip count analysis: HowFarToZero can analyze
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.

llvm-svn: 123136

Step #3 to improving trip count analysis: If we fold
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:

void f(int* begin, int* end) { std::fill(begin, end, 0); }

which turns into a != exit expression where one pointer is
strided and (thanks

Step #2 to improve trip count analysis for loops like this:

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

show more ...

teach SCEV analysis of PHI nodes that PHI recurences formed
with GEP instructions are always NUW, because PHIs cannot wrap
the end of the address space.

llvm-svn: 123105

reduce indentation. Print <nuw> and <nsw> when dumping SCEV AddRec's
that have the bit set.

llvm-svn: 123104

PR5207: Change APInt methods trunc(), sext(), zext(), sextOrTrunc() and
zextOrTrunc(), and APSInt methods extend(), extOrTrunc() and new method
trunc(), to be const and to return a new value instead

PR5207: Change APInt methods trunc(), sext(), zext(), sextOrTrunc() and
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

show more ...

PR5207: Rename overloaded APInt methods set(), clear(), flip() to
setAllBits(), setBit(unsigned), etc.

llvm-svn: 120564

Simplify code. No change in functionality.

llvm-svn: 119908

Silence warning about an uninitialized variable.

llvm-svn: 119800

Factor code for testing whether replacing one value with another
preserves LCSSA form out of ScalarEvolution and into the LoopInfo
class. Use it to check that SimplifyInstruction simplifications
are

Factor code for testing whether replacing one value with another
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

show more ...

Introduce memoization for ScalarEvolution dominates and properlyDominates
queries, and SCEVExpander getRelevantLoop queries.

llvm-svn: 119595

Factor out the code for purging a SCEV from all the various memoization maps.
Some of these maps may merge in the future, but for now it's convenient to have
a utility function for them.

llvm-svn: 1

Factor out the code for purging a SCEV from all the various memoization maps.
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

show more ...

Merge the implementations of isLoopInvariant and hasComputableLoopEvolution, and
memoize the results. This improves compile time in code which highly complex
expressions which get queried many times.

Merge the implementations of isLoopInvariant and hasComputableLoopEvolution, and
memoize the results. This improves compile time in code which highly complex
expressions which get queried many times.

llvm-svn: 119584

show more ...

Make SCEV::getType() and SCEV::print non-virtual. Move SCEV::hasOperand
to ScalarEvolution. Delete SCEV::~SCEV. SCEV is no longer virtual.

llvm-svn: 119578

Move SCEV::dominates and properlyDominates to ScalarEvolution.

llvm-svn: 119570

Move SCEV::isLoopInvariant and hasComputableLoopEvolution to be member
functions of ScalarEvolution, in preparation for memoization and
other optimizations.

llvm-svn: 119562

Before replacing a phi node with a different value, it
needs to be checked that this won't break LCSSA form.
Change the existing checking method to a more direct one:
rather than seeing if all predec

Before replacing a phi node with a different value, it
needs to be checked that this won't break LCSSA form.
Change the existing checking method to a more direct one:
rather than seeing if all predecessors belong to the loop,
check that the replacing value is either not in any loop or
is in a loop that contains the phi node.

llvm-svn: 119556

show more ...