Changes:
  1. Update an obsolete comment.
  2. Make the sorting by base an explicit (though still N^2) step, so
     that the code is more clear on what it is doing.
  3. Partition uses so that uses inside the loop are handled before uses
     outside the loop.

Note that none of these changes currently changes the code inserted by LSR,
but they are a stepping stone to getting there.

This code is the result of some crazy pair programming with Nate. :)

llvm-svn: 29493

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: 29324

llvm-svn: 29226

llvm-svn: 29223

InternalizePass.

llvm-svn: 29222

llvm-svn: 29199

llvm-svn: 29198

somewhere down the road.

llvm-svn: 29197

llvm-svn: 29189

llvm-svn: 29186

llvm-svn: 29149

This should fix PR 831.

llvm-svn: 29141

llvm-svn: 29134

This unbreaks smg2000.

llvm-svn: 29127

llvm-svn: 29126

Handle this case, which doesn't require a new callgraph edge.  This fixes
a crash compiling MallocBench/gs.

llvm-svn: 29121

target CG node.  This allows the inliner to properly update the callgraph
when using the pruning inliner.  The pruning inliner may not copy over all
call sites from a callee to a caller, so the edges corresponding to those
call sites should not be copied over either.

This fixes PR827 and Transforms/Inline/2006-07-12-InlinePruneCGUpdate.ll

llvm-svn: 29120

llvm-svn: 29108

didn't start showing up until after the recent instcombine fixes.

llvm-svn: 29102

llvm-svn: 29094

llvm-svn: 29093

This implements Transforms/InstCombine/bswap.ll:test[34].

llvm-svn: 29087

llvm-svn: 29083

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

llvm-svn: 29071

dropped.  This shrinks libllvmgcc.dylib another 67K

llvm-svn: 28975

llvm-svn: 28972

will be profitable.  This is mainly to remove some cases where excessive
unswitching would result in long compile times and/or huge generated code.

Once someone comes up with a better heuristic that avoids these cases, this
should be switched out.

llvm-svn: 28962

llvm-svn: 28961

blocks.

llvm-svn: 28959

Remove the Function pointer cast in these calls, converting it to
a cast of argument.
%tmp60 = tail call int cast (int (ulong)* %str to int (int)*)( int 10 )
%tmp60 = tail call int cast (int (ulong)* %str to int (int)*)( uint %tmp51 )

llvm-svn: 28953

Be more careful when updating Phi nodes after eliminating dead switch cases.  Fix
proposed by Chris.

llvm-svn: 28947

remove the struct return argument of a csret function, even if it is obviously
dead.

llvm-svn: 28943

will make Shootout-C/nestedloop faster.

llvm-svn: 28924

llvm-svn: 28914

of LCSSA.  This results several times the number of unswitchings occurring on
tests such and timberwolfmc, unix-tbl, and ldecod.

llvm-svn: 28912

"LCSSA" phi node causes indvars to break dominance properties.  This fixes
causes indvars to avoid inserting aggressive code in this case, instead
indvars should be fixed to be more aggressive in the face of lcssa phi's.

llvm-svn: 28850