- 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

llvm-svn: 43305

implementing cases related to PR1738.

llvm-svn: 43289

 - 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

SCEV subclasses to being non-static member functions of the ScalarEvolution
class.

llvm-svn: 43224

 - enable phi instructions demotion to stack
 - create alloca instructions in the entry block

llvm-svn: 43208

Instead of loading small global string from memory, use
integer constant.

llvm-svn: 43148

llvm-svn: 43147

llvm-svn: 43103

Apply "Instead of loading small c string constant, use integer constant directly" transformation while processing load instruction.

llvm-svn: 43070

llvm-svn: 43055

llvm-svn: 42985

Do not filter memmove.

llvm-svn: 42930

llvm-svn: 42920

llvm-svn: 42892

Fix DecomposeSimpleLinearExpr to handle simple constants better.
Don't nuke gep(bitcast(allocation)) if the bitcast(allocation) will
fold the allocation.  This fixes PR1728 and Instcombine/malloc3.ll

llvm-svn: 42891

llvm-svn: 42864

Do not walk invalid iterator.

llvm-svn: 42812

unswitch when frontier includes basic blocks that 
are not inside loop.

llvm-svn: 42654

llvm-svn: 42591

llvm-svn: 42590

of comparing begin() and end().

llvm-svn: 42585

llvm-svn: 42582

llvm-svn: 42508

Relax unsafe use check. If there is one unconditional use inside the loop then it is safe to promote value even if there is another conditional use inside the loop.

llvm-svn: 42493

Fixes a SWB crash.

llvm-svn: 42422

This fixes PR714.

llvm-svn: 42309

llvm-svn: 42306

doh.. 

llvm-svn: 42300

for (i=A; i<N; i++) {
  if (i < X && i > Y)
    do_something();
}

is transformed into

U=min(N,X); L=max(A,Y);
for (i=L;i<U;i++)
  do_somethihg();                            

llvm-svn: 42299

llvm-svn: 42270

llvm-svn: 42262

llvm-svn: 42209

speedup for GVN.

llvm-svn: 42185

llvm-svn: 42180