llvm-svn: 101002

variables. For example, with code like this:

  for (i=0;i<n;++i)
    if (i<n)
      x[i] = 0;

IndVarSimplify will now recognize that i is always less than n inside
the loop, and eliminate the if.

llvm-svn: 101000

that it's only testing for the entry condition, not full loop-invariant
conditions.

llvm-svn: 100979

explicitly split into stride-and-offset pairs. Also, add the
ability to track multiple post-increment loops on the same expression.

This refines the concept of "normalizing" SCEV expressions used for
to post-increment uses, and introduces a dedicated utility routine for
normalizing and denormalizing expressions.

This fixes the expansion of expressions which are post-increment users
of more than one loop at a time. More broadly, this takes LSR another
step closer to being able to reason about more than one loop at a time.

llvm-svn: 100699

exits the loop.  With this information we can guarantee 
the iteration count of the loop is bounded by the 
compare.  I think this xforms is finally safe now.

llvm-svn: 100285

checker.  Amusingly, we already had tests that we should
have rejects because they would be miscompiled in the
testsuite.

The remaining issue with this is that we don't check that
the branch causes us to exit the loop if it fails, so we
don't actually know if we remain in bounds.

llvm-svn: 100284

to a signed vs unsigned value depending on the sign of the
constant fp means that we can't distinguish between a 
truly negative number and a positive number so large the
32nd bit is set.  So, do don't this!

llvm-svn: 100283

stuff.  More bugs remain though.

llvm-svn: 100282

the required validity checks in the first place, and supporting
a condition large enough to require the 32'nd bit isn't worth it.

llvm-svn: 100280

of llvm.

llvm-svn: 100276

no uses, it would have been deleted by 
RecursivelyDeleteTriviallyDeadInstructions

llvm-svn: 100275

llvm-svn: 100274

llvm-svn: 100273

llvm-svn: 100272

are in the same block.  Insert the new increment in the
correct location.

Also, more cleanups.

llvm-svn: 100271

this cleans up a bunch of code and also fixes several crashes and
miscompiles.  More to come unfortunately, this optimization
is quite broken.

llvm-svn: 100270

it can't currently observe such changes automatically.

llvm-svn: 100186

llvm-svn: 99324

so that the SCEVExpander doesn't retain a dangling pointer as its
insert position. The dangling pointer in this case wasn't ever used
to insert new instructions, but it was causing trouble with
SCEVExpander's code for automatically advancing its insert position
past debug intrinsics.

This fixes use-after-free errors that valgrind noticed in
test/Transforms/IndVarSimplify/2007-06-06-DeleteDanglesPtr.ll and
test/Transforms/IndVarSimplify/exit_value_tests.ll.

llvm-svn: 99036

llvm-svn: 98584

compute a set of reachable blocks for itself each time it is called, which
is fairly frequently.

llvm-svn: 98179

llvm-svn: 97453

which branch on undef to branch on a boolean constant for the edge
exiting the loop. This helps ScalarEvolution compute trip counts for
loops.

Teach ScalarEvolution to recognize single-value PHIs, when safe, and
ForgetSymbolicName to forget such single-value PHI nodes as apprpriate
in ForgetSymbolicName.

llvm-svn: 97126

llvm-svn: 96780

llvm-svn: 96771

to be spurious

llvm-svn: 96662

llvm-svn: 96653

a loop exit value, so that if a loop gets deleted, ScalarEvolution
isn't stick holding on to dangling SCEVAddRecExprs for that loop. This
fixes PR6339.

llvm-svn: 96626

llvm-svn: 96614

and T->isPointerTy().  Convert most instances of the first form to the second form.
Requested by Chris.

llvm-svn: 96344

bug fixes, and with improved heuristics for analyzing foreign-loop
addrecs.

This change also flattens IVUsers, eliminating the stride-oriented
groupings, which makes it easier to work with.

llvm-svn: 95975

llvm-svn: 95781

This new version is much more aggressive about doing "full" reduction in
cases where it reduces register pressure, and also more aggressive about
rewriting induction variables to count down (or up) to zero when doing so
reduces register pressure.

It currently uses fairly simplistic algorithms for finding reuse
opportunities, but it introduces a new framework allows it to combine
multiple strategies at once to form hybrid solutions, instead of doing
all full-reduction or all base+index.

llvm-svn: 94061

llvm-svn: 92735

llvm-svn: 92609

contains another loop, or an instruction. The loop form is
substantially more efficient on large loops than the typical
code it replaces.

llvm-svn: 91654

LoopSimplify form may not be available.

llvm-svn: 86175

clears out more information than just the stored backedge taken count.

llvm-svn: 85664

llvm-svn: 85327

update all the callers.

llvm-svn: 82889