second part dominates all the blocks dominated
by original basic block. And first part dominates
second part.

llvm-svn: 40035

llvm-svn: 40034

llvm-svn: 40025

This fixes PR1559.

llvm-svn: 40024

beyond the end of an alloca to make FastDSE faster and more aggressive.

llvm-svn: 39945

dead stores on 400.perlbench.

llvm-svn: 39929

llvm-gcc build to succeed. Without this change it fails in libstdc++
compilation. This causes no regressions in dejagnu tests. However, 
someone who knows this code better might want to review it.

llvm-svn: 39924

llvm-svn: 39921

llvm-svn: 39896

llvm-svn: 39894

First teach instcombine that sign bit checks only demand the 
sign bit, this allows simplify demanded bits to hack on 
expressions better.

Second, teach instcombine that ashr is useless if only the
sign bit is demanded.

llvm-svn: 39880

(X << 31) <s 0  --> (X&1) != 0

This happens dozens of times in the CFE.

llvm-svn: 39879

llvm-svn: 39852

llvm-svn: 39844

Handle GEPs with all-zero indices in the same way we handle pointer-pointer bitcasts. Also, fix a potentia infinite loop.

This brings FastDSE to parity with old DSE on 175.vpr.

llvm-svn: 39839

llvm-svn: 39834

This drastically improves the effect of FastDSE on kimwitu++.

llvm-svn: 39819

llvm-svn: 39790

llvm-svn: 39789

Remove the end-block handling code.  It was unsafe, and making it safe would have resulted in falling back to the slow DSE case.  I need to think some more about the right way to handle this.

llvm-svn: 39788

thanks Benoit Boissinot!

llvm-svn: 39774

llvm-svn: 39769

llvm-svn: 39767

that structure.

Also, refactor the runOnBasicBlock() function, splitting some of the special cases into separate functions.

llvm-svn: 39762

of a function.

llvm-svn: 39754

llvm-svn: 39753

llvm-svn: 39747

llvm-svn: 39744

as the current DSE, but it only a linear scan over each block, rather than quadratic.  Eventually
(once it has been improved somewhat), this will replace the current DSE.

NOTE: This has not yet been extensively tested.
llvm-svn: 38517

llvm-svn: 38508

llvm-svn: 38505

llvm-svn: 38483

Move some key maps from std::map to DenseMap.  This improves the time to optimize Anton's testcase from 17.5s
to 15.7s.

llvm-svn: 38480

Use a cheaper test, delaying calling find_leader() until we know that it's necessary.  This improves
the time to optimize Anton's testcase from 21.1s to 17.6s.

llvm-svn: 38479

llvm-svn: 38477

This reduces the time to optimize Anton's testcase from 31.2s to 21.s!

llvm-svn: 38475

llvm-svn: 38472

llvm-svn: 38459

often.  This improves Anton's testcase from 36s to 32s.

llvm-svn: 38441

in the set.  For the moment, this results in a slight performance decrease, but
it lays the groundwork for future improvements.

llvm-svn: 38439