[PATCH]: Implement load PRE

[Daniel Berlin]

This patch implements load PRE at the tree level.

Only expressions of the form INDIRECT_REF<name> are handled ATM.  This
isn't really a technical problem, it's because the portion that
recreates expressions does it in pieces, and it's not legal to generate
GIMPLE of the form "pretmp_3" where pretmp is an aggregate type.

IE, it would attempt to generate things like a->b as

pretemp_3 = *a
pretemp_4 = pretemp_3.b

and we don't allow that.

I will fix this soon by rewriting it to understand how to generate
COMPONENT_REF of INDIRECT_REF properly.

The patch consists of three main portions:

1. Changing value numbering to take a vector of vuses, instead of the
statement, so that we can compare vuses on created expressions properly
during phi translation.

2. Adding some dataflow to determine where loads reach.  This requires
determining what names virtual uses actually represent, because we can't
generate virtual uses with overlapping lifetimes.   We could simply kill
all names merged at a phi, but we get better results if we just keep a
bitmap of what names the merged name represents, and then only kill
those names when the phi value is actually def'd.

3. Inserting fake temporaries for each store, value numbering them, and
then making them real if we turn out to use them.  This avoids trying to
figure out where we need to reload values due to stores.   You can
actually avoid this step entirely, you just get less loads moved around
because we think they die more than they actually do.  We could also
just mark locations we could insert the reloads, pretend they already
exist, and then make them exist if necessary.  This is tricky.  SSAPRE
used to just insert at every kill point as well, like we do.

Theoretically, #2 and #3 could be done sparsely, but it's not clear
whether it is worth it.

If it's worth it anywhere, it's probably #3.
However, to cut down on memory usage due to inserting fake temporaries
for store, we pool allocate the entire expression, and then if we end up
using it, we then gc allocate it.

This patch adds about 1% compile time, but it's due to the extra
may-alias pass, *not* the actual PRE.  I can probably make this go away
with a little work on teaching it to use the vuses, since we know what
vuses the expression will get (the real problem with this is that we
won't get name tags for the pretemp's, so eventually *something* has to
rerun aliasing, or we have to be able to tell the aliaser to figure out
what these new things point to)

Bootstrapped and regtested on i686-pc-linux-gnu and powerpc-linux-gnu,
and committed to mainline.

--Dan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lprediff3.diff
Type: text/x-patch
Size: 69882 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20051230/c2b94172/attachment.bin>