llvm-svn: 29925

up lcssa much in practice.

llvm-svn: 29465

down approach, inspired by discussions with Tanya.

This approach is significantly faster, because it does not need dominator
frontiers and it does not insert extraneous unused PHI nodes.  For example, on
252.eon, in a release-asserts build, this speeds up LCSSA (which is the slowest
pass in gccas) from 9.14s to 0.74s on my G5.  This code is also slightly smaller
and significantly simpler than the old code.

Amusingly, in a normal Release build (which includes the
"assert(L->isLCSSAForm());" assertion), asserting that the result of LCSSA
is in LCSSA form is actually slower than the LCSSA transformation pass
itself on 252.eon.  I will see if Loop::isLCSSAForm can be sped up next.

llvm-svn: 29463

llvm-svn: 29078

cases.  Ideally, this issue will go away in the future as LCSSA gets smarter
about which Phi nodes it inserts.

llvm-svn: 29076

LCSSA is still the slowest pass when gccas'ing 252.eon, but now it only takes
39s instead of 289s. :)

llvm-svn: 28776

llvm-svn: 28774

not handling PHI nodes correctly when determining if a value was live-out.

This patch reduces the number of detected live-out variables in the testcase
from 6565 to 485.

llvm-svn: 28771

If a single exit block has multiple predecessors within the loop, it will
appear in the exit blocks list more than once.  LCSSA needs to take that into
account so that it doesn't double process that exit block.

llvm-svn: 28750

llvm-svn: 28748

Back out Owen's 6/9 changes. They broke MultiSource/Benchmarks/Prolangs-C/bison (and perhaps others).

llvm-svn: 28747

on this.

llvm-svn: 28738

require LCSSA.

llvm-svn: 28734

llvm-svn: 28694

llvm-svn: 28693

llvm-svn: 28680

llvm-svn: 28678

actually going on.

llvm-svn: 28677

llvm-svn: 28619

reimplement getValueDominatingFunction to walk the DominanceTree rather than
just searching blindly.

llvm-svn: 28618

llvm-svn: 28599

is now theoretically feature-complete.  It has not, however, been thoroughly
test, and is still considered experimental.

llvm-svn: 28529

other calculations on each individually, rather than trying to delay it and do
them all at the end.

llvm-svn: 28527

the iterated Dominance Frontier of the loop-closure Phi's.  This is the
second phase of the LCSSA pass.  The third phase (coming soon) will be to
update all uses of loop variables to use the loop-closure Phi's instead.

llvm-svn: 28524

llvm-svn: 28512

llvm-svn: 28507

there's still a lot of work to be done on it.

llvm-svn: 28506

and documentation updates soo.

llvm-svn: 28495