This also updates dominator related stuff.

llvm-svn: 79825

the pred list instead of a vector, saving a boat load of malloc/free's.

llvm-svn: 79062

PR4238.

llvm-svn: 72223

llvm-svn: 52907

llvm-svn: 52829

llvm-svn: 51075

llvm-svn: 50032

llvm-svn: 49768

This patch fixes Benchmarks/Trimaran/enc-pc1/enc-pc1 failure reported by Grawp-PIC i386 nightly tester

llvm-svn: 48623

llvm-svn: 48579

llvm-svn: 48554

llvm-svn: 45418

llvm-svn: 43259

llvm-svn: 43059

having dominator information on MBB's.

llvm-svn: 43036

Begin the process of allowing DomTree on MBB's.  Step One: template DomTreeNode by making it a typedef of a templated DomTreeNodeBase.

llvm-svn: 42743

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

llvm-svn: 42654

Also, add a FIXME for a bug in PostDomTree calculation I noticed while writing this,

llvm-svn: 42593

each one's runOnFunction method.

llvm-svn: 42563

Convert DFSPass into a templated friend function, in preparation for making it common to DomTree and PostDomTree.

llvm-svn: 42420

and the PostDomTree version first.

llvm-svn: 42250

change is not useful in and of itself, but it lays the groundwork for combining
the dominator and postdominator implementations.

Also, factor a few methods that are common to DominatorTree and PostDominatorTree
into DominatorTreeBase.  Again, this will make merging the two calculation methods
simpler in the future.

llvm-svn: 42248

llvm-svn: 41075

llvm-svn: 41052

1. domtree is a tree, not a graph.  There is no need to avoid revisiting nodes with a set.
2. the worklist can contain the child iterator pointers so we don't get N^2 rescanning of children.

This speeds up updateDFSNumbers significantly, making it basically free.  On the testcase in PR1432,
this speeds up loopsimplify by another 3x, dropping it from the 12th most expensive pass to the to
the 30th. :)  It used to be #1.

llvm-svn: 40923

natural loop canonicalization (which does many cfg xforms) by 4.3x, for 
example.  This also fixes a bug in postdom dfnumber computation.

llvm-svn: 40920

2. Make domtree printing print dfin/dfout #'s
3. Fix the Transforms/LoopSimplify/2004-04-13-LoopSimplifyUpdateDomFrontier.ll failure from last night (in DominanceFrontier::splitBlock).

w.r.t. #3, my patches last night happened to expose the bug, but this 
has been broken since Owen's r35839 patch to LoopSimplify.  The code
was subsequently moved over from LoopSimplify into Dominators, carrying
the latent bug.  Fun stuff.

llvm-svn: 40858

llvm-svn: 40830

domtree by 10% and postdomtree by 17%

llvm-svn: 40829

a smallptrset.  This speeds up domtree by about 15% and postdomtree by 20%.

llvm-svn: 40828

speeds up idom by about 45% and postidom by about 33%.

Some extra precautions must be taken not to invalidate densemap iterators.

llvm-svn: 40827

DenseMap instead of an std::map.  This speeds up postdomtree
by about 25% and domtree by about 23%.  It also speeds up clients,
for example, domfrontier by 11%, mem2reg by 4% and ADCE by 6%.

llvm-svn: 40826

exit edge to preserve LCSSA.

Fix dominance frontier update during loop unswitch. This fixes PR 1589, again

llvm-svn: 40737

llvm-svn: 40698

exit edge to preserve LCSSA.

Fix dominance frontier update during loop unswitch. This fixes PR 1589.

llvm-svn: 40695

llvm-svn: 40564

llvm-svn: 37765

from LoopSimplify.cpp to Dominator.cpp

llvm-svn: 37689

llvm-svn: 37562

llvm-svn: 37561