llvm-svn: 123288

once at the beginning of GVN instead of once per iteration.

llvm-svn: 123278

llvm-svn: 123270

actually reached in the testcase in PR8954, but it's safe and good
practice.

llvm-svn: 123224

phi nodes.  It is called from MergeBlockIntoPredecessor which is 
called from GVN, which claims to preserve these.

I'm skeptical that this is the actual problem behind PR8954, but
this is a stab in the right direction.

llvm-svn: 123222

Don't bother value numbering instructions with void types in GVN. In theory this should allow us to insert
fewer things into the value numbering maps, but any speedup is beneath the noise threshold on my machine
on 403.gcc.

llvm-svn: 122844

llvm-svn: 122828

llvm-svn: 122827

llvm-svn: 122826

Clarify terminology, settling on referring to what was the "number table" as the "leader table", and
rename methods to make it much more clear what they're doing.

llvm-svn: 122823

llvm-svn: 122822

Branch instructions don't produce values, so there's no need to generate a value number for them.  This
avoids adding them to the various value numbering tables, resulting in a minor (~3%) speedup for GVN
on 40.gcc.

llvm-svn: 122819

llvm-svn: 122817

Use the new addEscapingValue callback to update GlobalsModRef when GVN adds PHIs of GEPs. For the moment,
have GlobalsModRef handle this conservatively by simply removing the value from its maps.

llvm-svn: 122787

almost-but-not-quite-identical code.  No intended functionality change.

llvm-svn: 122760

so that Dominators.h is *just* domtree.  Also prune #includes a bit.

llvm-svn: 122714

I still think that LVI should be handling this, but that capability is some ways off in the future,
and this matters for some significant benchmarks.

llvm-svn: 122378

llvm-svn: 122371

llvm-svn: 122362

llvm-svn: 122190

llvm-svn: 121921

function so that it can live in Analysis instead of
VMCore.

llvm-svn: 121885

llvm-svn: 120476

llvm-svn: 120474

llvm-svn: 119865

Completely rework the datastructure GVN uses to represent the value number to leader mapping.  Previously,
this was a tree of hashtables, and a query recursed into the table for the immediate dominator ad infinitum
if the initial lookup failed.  This led to really bad performance on tall, narrow CFGs.

We can instead replace it with what is conceptually a multimap of value numbers to leaders (actually
represented by a hashtable with a list of Value*'s as the value type), and then
determine which leader from that set to use very cheaply thanks to the DFS numberings maintained by
DominatorTree.  Because there are typically few duplicates of a given value, this scan tends to be
quite fast.  Additionally, we use a custom linked list and BumpPtr allocation to avoid any unnecessary
allocation in representing the value-side of the multimap.

This change brings with it a 15% (!) improvement in the total running time of GVN on 403.gcc, which I
think is pretty good considering that includes all the "real work" being done by MemDep as well.

The one downside to this approach is that we can no longer use GVN to perform simple conditional progation,
but that seems like an acceptable loss since we now have LVI and CorrelatedValuePropagation to pick up
the slack.  If you see conditional propagation that's not happening, please file bugs against LVI or CVP.

llvm-svn: 119714

systematically, CollapsePhi will always return null here.  Note
that CollapsePhi did an extra check, isSafeReplacement, which
the SimplifyInstruction logic does not do.  I think that check
was bogus - I guess we will soon find out!  (It was originally
added in commit 41998 without a testcase).

llvm-svn: 119456

it to get better phi node simplification.

llvm-svn: 119055

"%z = %x and %y".  If GVN can prove that %y equals %x, then it turns
this into "%z = %x and %x".  With the new code, %z will be replaced
with %x everywhere (and then deleted).  Previously %z would be value
numbered too, which is a waste of time.  Also, while a clever value
numbering algorithm would give %z the same value number as %x, our
current one doesn't do so (at least I don't think it does).  The new
logic has an essentially equivalent effect to what you would get if
%z was given the same value number as %x, i.e. it should make value
numbering smarter.  While there, get hold of target data once at the
start rather than a gazillion times all over the place.

llvm-svn: 118923

and vaarg instructions.

llvm-svn: 118845

references. For example, this allows gvn to eliminate the load in
this example:

  void foo(int n, int* p, int *q) {
    p[0] = 0;
    p[1] = 1;
    if (n) {
      *q = p[0];
    }
  }

llvm-svn: 118714

instructions instead of hard-coding operand numbers.

llvm-svn: 118698

Get rid of static constructors for pass registration.  Instead, every pass exposes an initializeMyPassFunction(), which
must be called in the pass's constructor.  This function uses static dependency declarations to recursively initialize
the pass's dependencies.

Clients that only create passes through the createFooPass() APIs will require no changes.  Clients that want to use the
CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h
before parsing commandline arguments.

I have tested this with all standard configurations of clang and llvm-gcc on Darwin.  It is possible that there are problems
with the static dependencies that will only be visible with non-standard options.  If you encounter any crash in pass
registration/creation, please send the testcase to me directly.

llvm-svn: 116820

perform initialization without static constructors AND without explicit initialization
by the client.  For the moment, passes are required to initialize both their
(potential) dependencies and any passes they preserve.  I hope to be able to relax
the latter requirement in the future.

llvm-svn: 116334

llvm-svn: 115996

Now that the profitable bits of EnableFullLoadPRE have been enabled by default, rip out the remainder.
Anyone interested in more general PRE would be better served by implementing it separately, to get real
anticipation calculation, etc.

llvm-svn: 115337

We do want to allow LoadPRE to perform LICM-like transformations: we already consider PHI nodes to be negligible for
code size (making this transform code size neutral), and it allows us to hoist values out of loops, which is always
a good thing.

llvm-svn: 115205

LoadPRE was not properly checking that the load it was PRE'ing post-dominated the block it was being hoisted to.
Splitting critical edges at the merge point only addressed part of the issue; it is also possible for non-post-domination
to occur when the path from the load to the merge has branches in it.  Unfortunately, full anticipation analysis is
time-consuming, so for now approximate it.  This is strictly more conservative than real anticipation, so we will miss
some cases that real PRE would allow, but we also no longer insert loads into paths where they didn't exist before. :-)

This is a very slight net positive on SPEC for me (0.5% on average).  Most of the benchmarks are largely unaffected, but
when it pays off it pays off decently: 181.mcf improves by 4.5% on my machine.

llvm-svn: 114785

llvm-svn: 113073

I'm sure it is harmless.  Original commit message:
If PrototypeValue is erased in the middle of using the SSAUpdator
then the SSAUpdator may access freed memory.  Instead, simply pass
in the type and name explicitly, which is all that was used anyway.

llvm-svn: 112810