llvm-svn: 101125

llvm-svn: 101117

numerator is an induction variable. For example, with code like this:

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

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

llvm-svn: 101113

expression is a UDiv and it doesn't appear that the UDiv came from
the user's source.

ScalarEvolution has recently figured out how to compute a tripcount
expression for the inner loop in
SingleSource/Benchmarks/Shootout/sieve.c, using a udiv. Emitting a
udiv instruction dramatically slows down the enclosing loop.

llvm-svn: 101068

llvm-svn: 101033

a ScalarEvolution bug with overflow handling is fixed, the normal analysis
code will automatically decline to operate on the icmp instructions which
are responsible for the loop exit.

llvm-svn: 101032

instead of deleting just the user. This makes it more consistent with
other code in IndVarSimplify, and theoretically can eliminate more users
earlier.

llvm-svn: 101027

the loop exit test. This usually doesn't come up for a variety of
reasons, but it isn't impossible, so make IndVarSimplify handle it
conservatively.

llvm-svn: 101008

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

in some cases.

llvm-svn: 100937

into adjacent loops. Also, ensure that the insert position is
dominated by the loop latch of any loop in the post-inc set which
has a latch.

llvm-svn: 100906

so that an unfortunately placed bitcast doesn't pin a value in a
register.

llvm-svn: 100883

llvm-svn: 100856

a separate function.

llvm-svn: 100845

forced constant is changed to a constant, we would end
up adding the instruction to the wrong worklist, 
preventing it from being properly revisited.  This fixes
rdar://7832370

llvm-svn: 100837

inputs happen to negate each other.

llvm-svn: 100828

llvm-svn: 100824

ensure that the expansion is dominated by the increments of those loops.

llvm-svn: 100748

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

llvm-svn: 100550

undefs in branches/switches, we have two cases: a branch on a literal
undef or a branch on a symbolic value which is undef.  If we have a
literal undef, the code was correct: forcing it to a constant is the
right thing to do.

If we have a branch on a symbolic value that is undef, we should force
the symbolic value to a constant, which then makes the successor block
live.  Forcing the condition of the branch to being a constant isn't 
safe if later paths become live and the value becomes overdefined.  This
is the case that 'forcedconstant' is designed to handle, so just use it.

This fixes rdar://7765019 but there is no good testcase for this, the
one I have is too insane to be useful in the future.

llvm-svn: 100478

llvm-svn: 100468

llvm-svn: 100467

Added support for address spaces and added a isVolatile field to memcpy, memmove, and memset,
e.g., llvm.memcpy.i32(i8*, i8*, i32, i32) -> llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i32, i1)

llvm-svn: 100304

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

llvm-svn: 100262

llvm-svn: 100199