This also implements some new features for the indvars pass, including
linear function test replacement, exit value substitution, and it works with
a much more general class of induction variables and loops.

llvm-svn: 12620

llvm-svn: 12595

Testcase: LoopSimplify/2004-04-01-IncorrectDomUpdate.ll

llvm-svn: 12592

llvm-svn: 12573

llvm-svn: 12544

llvm-svn: 12540

llvm-svn: 12520

#1 is to unconditionally strip constantpointerrefs out of
instruction operands where they are absolutely pointless and inhibit
optimization.  GRRR!

#2 is to implement InstCombine/getelementptr_const.ll

llvm-svn: 12519

llvm-svn: 12507

llvm-svn: 12464

llvm-svn: 12458

as it is making effectively arbitrary modifications to the CFG and we don't
have a domset/domfrontier implementations that can handle the dynamic updates.
Instead of having a bunch of code that doesn't actually work in practice,
just demote any potentially tricky values to the stack (causing the problem
to go away entirely).  Later invocations of mem2reg will rebuild SSA for us.

This fixes all of the major performance regressions with tail duplication
from LLVM 1.1.  For example, this loop:

---
int popcount(int x) {
  int result = 0;
  while (x != 0) {
    result = result + (x & 0x1);
    x = x >> 1;
  }
  return result;
}
---
Used to be compiled into:

int %popcount(int %X) {
entry:
	br label %loopentry

loopentry:		; preds = %entry, %no_exit
	%x.0 = phi int [ %X, %entry ], [ %tmp.9, %no_exit ]		; <int> [#uses=3]
	%result.1.0 = phi int [ 0, %entry ], [ %tmp.6, %no_exit ]		; <int> [#uses=2]
	%tmp.1 = seteq int %x.0, 0		; <bool> [#uses=1]
	br bool %tmp.1, label %loopexit, label %no_exit

no_exit:		; preds = %loopentry
	%tmp.4 = and int %x.0, 1		; <int> [#uses=1]
	%tmp.6 = add int %tmp.4, %result.1.0		; <int> [#uses=1]
	%tmp.9 = shr int %x.0, ubyte 1		; <int> [#uses=1]
	br label %loopentry

loopexit:		; preds = %loopentry
	ret int %result.1.0
}

And is now compiled into:

int %popcount(int %X) {
entry:
        br label %no_exit

no_exit:                ; preds = %entry, %no_exit
        %x.0.0 = phi int [ %X, %entry ], [ %tmp.9, %no_exit ]          ; <int> [#uses=2]
        %result.1.0.0 = phi int [ 0, %entry ], [ %tmp.6, %no_exit ]             ; <int> [#uses=1]
        %tmp.4 = and int %x.0.0, 1              ; <int> [#uses=1]
        %tmp.6 = add int %tmp.4, %result.1.0.0          ; <int> [#uses=2]
        %tmp.9 = shr int %x.0.0, ubyte 1                ; <int> [#uses=2]
        %tmp.1 = seteq int %tmp.9, 0            ; <bool> [#uses=1]
        br bool %tmp.1, label %loopexit, label %no_exit

loopexit:               ; preds = %no_exit
        ret int %tmp.6
}

llvm-svn: 12457

time from 615s to 1.49s on a large testcase that has a gigantic switch statement
that all of the blocks in the function go to (an intepreter).

llvm-svn: 12442

llvm-svn: 12441

http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20040308/013095.html

Basically, this patch only updated the immediate dominatees of the header node
to tell them that the preheader also dominated them.  In practice, ALL
dominatees of the header node are also dominated by the preheader.

This fixes: LoopSimplify/2004-03-15-IncorrectDomUpdate.
and PR293

llvm-svn: 12434

llvm-svn: 12420

sin/cos/strlen calls and stuff.  This implements:
  LICM/call_sink_pure_function.ll
  LICM/call_sink_const_function.ll

llvm-svn: 12415

be non-empty!  This fixes LowerSwitch/2004-03-13-SwitchIsDefaultCrash.ll

llvm-svn: 12384

loop information won't see it, and we could have unreachable blocks pointing to
the non-header node of blocks in a natural loop.  This isn't tidy, so have the
loopsimplify pass clean it up.

llvm-svn: 12380

Fix InstCombine/2004-03-13-InstCombineInfLoop.ll which caused an infinite
loop compiling (I think) povray.

llvm-svn: 12365

On the testcase from GCC PR12440, which has a LOT of loops (1392 of which require
preheaders to be inserted), this speeds up the loopsimplify pass from 1.931s to
0.1875s.  The loop in question goes from 1.65s -> 0.0097s, which isn't bad. All of
these times are a debug build.

This adds a dependency on DominatorTree analysis that was not there before, but
we always had dominatortree available anyway, because LICM requires both loop
simplify and DT, so this doesn't add any extra analysis in practice.

llvm-svn: 12362

llvm-svn: 12355

llvm-svn: 12353

llvm-svn: 12318

llvm-svn: 12317

a zero value is the most likely way to cause further simplification, so we do it.

llvm-svn: 12197

llvm-svn: 12086

llvm-svn: 12021

Note that this is a band-aid put over a band-aid.  This just undisables
tail duplication in on very specific case that it seems to work in.

llvm-svn: 11989

Do not just inject a new prototype.

llvm-svn: 11951

Create a new AddUsesToWorkList method
optimize memmove/set/cpy of zero bytes to a noop.

llvm-svn: 11941

llvm-svn: 11940

This is a really minor thing, but might help out the 'switch statement induction'
code in simplifycfg.

llvm-svn: 11900

llvm-svn: 11821

llvm-svn: 11801

llvm-svn: 11775

llvm-svn: 11774

Also, turn 'shr int %X, 1234' into 'shr int %X, 31'

llvm-svn: 11768

llvm-svn: 11742

whether this is the sign bit or not, so check unsigned comparisons as well.

llvm-svn: 11740