a new value numbering set after splitting a critical edge.  This increases
the number of instances of PRE on 403.gcc from ~60 to ~570.

llvm-svn: 60393

llvm-svn: 60339

that it isn't reallocated all the time.  This is a tiny speedup for
GVN: 3.90->3.88s

llvm-svn: 60338

elimination: when finding dependent load/stores, realize that
they are the same if aliasing claims must alias instead of relying
on the pointers to be exactly equal.  This makes load elimination
more aggressive.  For example, on 403.gcc, we had:

<     68 gvn    - Number of instructions PRE'd
< 152718 gvn    - Number of instructions deleted
<  49699 gvn    - Number of loads deleted
<   6153 memdep - Number of dirty cached non-local responses
< 169336 memdep - Number of fully cached non-local responses
< 162428 memdep - Number of uncached non-local responses

now we have:

>     64 gvn    - Number of instructions PRE'd
> 153623 gvn    - Number of instructions deleted
>  49856 gvn    - Number of loads deleted
>   5022 memdep - Number of dirty cached non-local responses
> 159030 memdep - Number of fully cached non-local responses
> 162443 memdep - Number of uncached non-local responses

That's an extra 157 loads deleted and extra 905 other instructions nuked.

This slows down GVN very slightly, from 3.91 to 3.96s.

llvm-svn: 60314

vector instead of a densemap.  This shrinks the memory usage of this thing
substantially (the high water mark) as well as making operations like
scanning it faster.  This speeds up memdep slightly, gvn goes from
3.9376 to 3.9118s on 403.gcc

This also splits out the statistics for the cached non-local case to
differentiate between the dirty and clean cached case.  Here's the stats
for 403.gcc:

  6153 memdep - Number of dirty cached non-local responses
169336 memdep - Number of fully cached non-local responses
162428 memdep - Number of uncached non-local responses

yay for caching :)

llvm-svn: 60313

This speeds up GVN from 4.0386s to 3.9376s.

llvm-svn: 60310

remove some fixme's.  This speeds up GVN very slightly on 403.gcc 
(4.06->4.03s)

llvm-svn: 60309

If we see that a load depends on the allocation of its memory with no
intervening stores, we now return a 'None' depedency instead of "Normal".
This tweaks GVN to do its optimization with the new result.

llvm-svn: 60267

a smallvector instead of a DenseMap.  This speeds up GVN by 5%
on 403.gcc.

llvm-svn: 60255

formulation that is faster and doesn't require nonLazyHelper.
Much less code.

llvm-svn: 60253

former does caching, the later doesn't.  This dramatically simplifies
the logic in getDependency and getDependencyFrom.

llvm-svn: 60234

query.  This makes it crystal clear what cases can escape from MemDep that
the clients have to handle.  This also gives the clients a nice simplified
interface to it that is easy to poke at.

This patch also makes DepResultTy and MemoryDependenceAnalysis::DepType
private, yay.

llvm-svn: 60231

of a pointer/int pair instead of a manually bitmangled pointer.
This forces clients to think a little more about checking the 
appropriate pieces and will be useful for internal 
implementation improvements later.

I'm not particularly happy with this.  After going through this
I don't think that the clients of memdep should be exposed to
the internal type at all.  I'll fix this in a subsequent commit.

This has no functionality change.

llvm-svn: 60230

llvm-svn: 57353

Patch by Samuel Tardieu.

llvm-svn: 57291

pointer bitcasts and GEP's", and centralize the
logic in Value::getUnderlyingObject.  The
difference with stripPointerCasts is that
stripPointerCasts only strips GEPs if all
indices are zero, while getUnderlyingObject
strips GEPs no matter what the indices are.

llvm-svn: 56922

llvm-svn: 55779

llvm-svn: 55744

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