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

llvm-svn: 12456

llvm-svn: 12454

llvm-svn: 12453

llvm-svn: 12452

llvm-svn: 12451

Add handling for Mul instruction.

llvm-svn: 12450

testcase from 32.5s in -raise to take .3s

llvm-svn: 12443

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

llvm-svn: 12435

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

client has another VN implementation that can VN calls.

llvm-svn: 12427

llvm-svn: 12425

llvm-svn: 12424

horrible hack.

llvm-svn: 12423

have an alias set, just like adds and subtracts don't.

llvm-svn: 12422

llvm-svn: 12421

llvm-svn: 12420

GCSE/call_cse.ll

llvm-svn: 12419

Also, add some stuff I missed before.

llvm-svn: 12417

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

llvm-svn: 12415

llvm-svn: 12413

use of the boolean queries

llvm-svn: 12410

llvm-svn: 12409

llvm-svn: 12408

llvm-svn: 12406

Simplify the input/output finder.  All elements of a basic block are
instructions.  Any used arguments are also inputs.  An instruction can only
be used by another instruction.

llvm-svn: 12405

extracted, and a function that contained a single top-level loop never had
the loop extracted, regardless of how much non-loop code there was.

llvm-svn: 12403

* Don't insert a branch to the switch instruction after the call, just
  make it a single block.
* Insert the new alloca instructions in the entry block of the original
  function instead of having them execute dynamically
* Don't make the default edge of the switch instruction go back to the switch.
  The loop extractor shouldn't create new loops!
* Give meaningful names to the alloca slots and the reload instructions
* Some minor code simplifications

llvm-svn: 12402

This also implements a two minor improvements:
  * Don't insert live-out stores IN the region, insert them on the code path
    that exits the region
  * If the region is exited to the same block from multiple paths, share the
    switch statement entry, live-out store code, and the basic block.

llvm-svn: 12401

a member of the class.  While we're at it, turn the collection into a set
instead of a vector to improve efficiency and make queries simpler.

llvm-svn: 12400

MachineBasicBlock::iterator take a MachineInstr*.

llvm-svn: 12392

the command line, and the single loop extractor, usable by bugpoint

llvm-svn: 12390

instruction to make the API more flexible.

llvm-svn: 12386

llvm-svn: 12385

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

llvm-svn: 12384

llvm-svn: 12382

Require 'simplified' loops, not just raw natural loops.  This fixes
CodeExtractor/2004-03-13-LoopExtractorCrash.ll

llvm-svn: 12381