Put a heuristic in place to prevent GVN from falling into bad cases with massively complicated CFGs.
This speeds up a particular testcase from 12+ hours to 5 seconds with little perceptible loss of quality.

llvm-svn: 55391

Patch contributed by m-s.

llvm-svn: 55167

llvm-svn: 53771

Make PRE actually handle critical edges (by splitting them).  Confirmed that bootstrap passes with this change.

llvm-svn: 53762

llvm-svn: 53730

llvm-svn: 53705

could cause problems for memdep when it breaks critical edges.

llvm-svn: 53691

llvm-svn: 53627

llvm-svn: 53616

Have GVN do a pre-pass over the CFG that folds away unconditional branches where possible.  This allows local PRE to be more aggressive.

llvm-svn: 53615

llvm-svn: 53470

Use information already present in the ValueTable to fast-fail when we know there won't be a value number match.  This speeds up GVN on a case where there are very few redundancies by ~25%.

llvm-svn: 53108

llvm-svn: 53040

llvm-svn: 53032

llvm-svn: 52643

Tighten the conditions under which we do PRE, remove some unneeded code, and correct our preserved analyses list, since we
do now change the CFG by splitting critical edges during PRE.

llvm-svn: 52631

llvm-svn: 52574

llvm-svn: 52531

Change around the data structures used to store availability sets, resulting in a GVN+PRE that is faster that GVN alone was before.

llvm-svn: 52521

llvm-svn: 52518

once benchmarking is completed.

llvm-svn: 52506

llvm-svn: 52505

This fixes a failure on povray.

llvm-svn: 52499

GVN expects that all inputs which to an instruction fall somewhere in the value
hierarchy, which isn't true for these.

llvm-svn: 52496

llvm-svn: 52472

Add local PRE to GVN.  This only operates in cases where it would not increase code size, namely when the instantiated expression
would only need to be created in one predecessor.

llvm-svn: 52471

We don't want to find dependencies within the same block in this case.  It leads to incorrect results because
we're detecting something at or after the call we're querying on.

llvm-svn: 52433

llvm-svn: 52242

deprecated by the GVN and GVNPRE passes.

llvm-svn: 51983

llvm-svn: 51955

llvm-svn: 51230

bug as well as a missed optimization.  We weren't properly checking for local
dependencies before moving on to non-local ones when doing non-local read-only 
call CSE.

llvm-svn: 51082

llvm-svn: 51035

llvm-svn: 51024

llvm-svn: 50995

Move the various analyses used by GVN into static variables so we don't have to keep passing them around or refetching them.

llvm-svn: 50963

llvm-svn: 50035

llvm-svn: 49842

of calls and less aggressive with non-readnone calls.

llvm-svn: 49516

GVN and into its own pass.

llvm-svn: 49419