llvm-svn: 54710

Fix PR2355: bug in ChangeCompareStride. When the loop termination compare is the only use of its iv stride, the stride can be eliminated by moving it to another stride. If the scale is negative, swap the predicate instead of using a inverse predicate.

llvm-svn: 54415

leads into a cycle involving a different PHI, LSR got stuck running
around that cycle looking for the original PHI. To avoid this, keep
track of visited PHIs and stop searching if we see one more than once.
This fixes PR2570.

llvm-svn: 53879

llvm-svn: 53564

1. LSR runOnLoop is always returning false regardless if any transformation is made.
2. AddUsersIfInteresting can create new instructions that are added to DeadInsts. But there is a later early exit which prevents them from being freed.

llvm-svn: 53193

llvm-svn: 52648

with more than two nodes.

llvm-svn: 52617

function, and make use of it in several places.

llvm-svn: 52463

when changing the stride of a comparison so that it's slightly
more precise, by having it scan the instruction list to determine
if there is a use of the condition after the point where the
condition will be inserted.

llvm-svn: 52371

llvm-svn: 52361

llvm-svn: 52339

for it to generate use-before-def IR, such as in this testcase.

llvm-svn: 52258

llvm-svn: 52226

Remove x86.sse2.loadh.pd and x86.sse2.loadl.pd. These will be lowered into load and shuffle instructions.

llvm-svn: 51521

ScalarEvolution::deleteValueFromRecords on it before doing the
replaceAllUsesWith, because ScalarEvolution looks at the instruction's
users to find SCEV references to the instruction's SCEV object in its
internal maps.

Move all of LSR's loop-related state clearing after processing the loop
and before cleaning up dead PHI nodes. This eliminates all of LSR's SCEV
references just before the calls to ScalarEvolution::deleteValueFromRecords
so that when ScalarEvolution drops its own SCEV references, the reference
counts will reach zero and the SCEVs will be deleted immediately.

These changes fix some compiler aborts involving ScalarEvolution holding
onto and reusing SCEV objects for instructions that have been deleted.
No regression test unfortunately; because the symptoms were due to
dangling pointers, reduced testcases ended up being fairly arbitrary.

llvm-svn: 51359

replaced is a PHI. This prevents it from inserting uses before defs
in the case that it isn't a PHI and it depends on other instructions
later in the block. This fixes the 447.dealII regression on x86-64.

llvm-svn: 51292

use-before-def. The problem comes up in code with multiple PHIs where
one PHI is being rewritten in terms of the other, but the other needs
to be casted first. LLVM rules requre the cast instruction to be
inserted after any PHI instructions, but when instructions were
inserted to replace the second PHI value with a function of the first,
they were ended up going before the cast instruction. Avoid this
problem by remembering the location of the cast instruction, when one
is needed, and inserting the expansion of the new value after it.

This fixes a bug that surfaced in 255.vortex on x86-64 when
instcombine was removed from the middle of the loop optimization
passes. 

llvm-svn: 51169

several things that were neither in an anonymous namespace nor static
but not intended to be global.

llvm-svn: 51017

llvm-svn: 49671

Specifically, introduction of XXX::Create methods
for Users that have a potentially variable number of
Uses.

llvm-svn: 49277

llvm-svn: 48556

llvm-svn: 46514

llvm-svn: 45418

Clean up previous patch: PHI uses should not prevent iv reuse if all other uses are addresses. This trades a constant multiply for one fewer iv.

llvm-svn: 45251

llvm-svn: 45230

fix an occasional nonrepeatable bootstrap failure we've
been seeing on Darwin.

llvm-svn: 44202

At end of LSR, replace uses of now constant (as result of SplitCriticalEdge) PHI node with the constant value.

llvm-svn: 43533

It's not safe to tell SplitCriticalEdge to merge identical edges. It may delete the phi instruction that's being processed.

llvm-svn: 43524

- Allow icmp rewrite using an iv / stride of a smaller integer type.

llvm-svn: 43480

llvm-svn: 43463

llvm-svn: 43462

llvm-svn: 43461

llvm-svn: 43460

- ChangeCompareStride only reuse stride that is larger than current stride. It
  will let the general reuse mechanism to try to reuse a smaller stride.
- Watch out for multiplication overflow in ChangeCompareStride.
- Replace std::set with SmallPtrSet.

llvm-svn: 43408

llvm-svn: 43384

Loosen up iv reuse to allow reuse of the same stride but a larger type when truncating from the larger type to smaller type is free.
e.g.
Turns this loop:
LBB1_1: # entry.bb_crit_edge
        xorl    %ecx, %ecx
        xorw    %dx, %dx
        movw    %dx, %si
LBB1_2: # bb
        movl    L_X$non_lazy_ptr, %edi
        movw    %si, (%edi)
        movl    L_Y$non_lazy_ptr, %edi
        movw    %dx, (%edi)
		addw    $4, %dx
		incw    %si
		incl    %ecx
		cmpl    %eax, %ecx
		jne     LBB1_2  # bb
	
into

LBB1_1: # entry.bb_crit_edge
        xorl    %ecx, %ecx
        xorw    %dx, %dx
LBB1_2: # bb
        movl    L_X$non_lazy_ptr, %esi
        movw    %cx, (%esi)
        movl    L_Y$non_lazy_ptr, %esi
        movw    %dx, (%esi)
        addw    $4, %dx
		incl    %ecx
        cmpl    %eax, %ecx
        jne     LBB1_2  # bb

llvm-svn: 43375

stride may be rewritten using the stride of the compare instruction.

llvm-svn: 43367

llvm-svn: 43356

and the compaison is against a constant value, try eliminate the stride
by moving the compare instruction to another stride and change its
constant operand accordingly. e.g.

loop:
...
v1 = v1 + 3
v2 = v2 + 1
if (v2 < 10) goto loop
=>
loop:
...
v1 = v1 + 3
if (v1 < 30) goto loop

llvm-svn: 43336

 - Avoid attempting stride-reuse in the case that there are users that
   aren't addresses. In that case, there will be places where the
   multiplications won't be folded away, so it's better to try to
   strength-reduce them.

 - Several SSE intrinsics have operands that strength-reduction can
   treat as addresses. The previous item makes this more visible, as
   any non-address use of an IV can inhibit stride-reuse.

 - Make ValidStride aware of whether there's likely to be a base
   register in the address computation. This prevents it from thinking
   that things like stride 9 are valid on x86 when the base register is
   already occupied.

Also, XFAIL the 2007-08-10-LEA16Use32.ll test; the new logic to avoid
stride-reuse elimintes the LEA in the loop, so the test is no longer
testing what it was intended to test.

llvm-svn: 43231