Re: [PATCH] Teach SCCVN/FRE expression insertion, optimize type-punning through unions (final!)

[Richard Guenther <rguenther at suse dot de>]

On Fri, 14 Mar 2008, Daniel Berlin wrote:

> On Fri, Mar 14, 2008 at 7:06 AM, Richard Guenther <rguenther@suse.de> wrote:
> >
> >  This final patch makes it possible for SCCVN to value-number something
> >  to an expression that is not yet computed and cause it to be inserted
> >  at FRE elimination time instead.  The use in this patch is for optimizing
> >  type-punning through unions to use VIEW_CONVERT_EXPRs instead which
> >  allow to get rid of the union temporary and generates better code.
> >
> >  The SCCVN part generates a new (temporary) SSA_NAME as a leader and
> >  value-number for a to-be inserted expression.
> >
> >  During FRE elimination, if we do not find an available replacement, we
> >  use the PRE insertion infrastructure to insert the expression SCCVN
> >  thinks is simpler just before the elimination point.  As this is
> >  not always possible checks for availability in the replacement block
> >  (to make sure its not a partial redundancy) and dominance checks for
> >  the insertion point are done (this uglifies the patch somewhat, so
> >  just ignore that part ;)).
> >
> >  The main problem with insertion and dominance is that we visit
> >  unrelated SCCs in arbitrary oder and only once.  Thus for
> >
> >   # VUSE <SFT.10_8(D), SFT.11_9(D)>
> >   D.1569_1 = fs.offset;
> >   D.1570_2 = (char) D.1569_1;
> >   # SMT.16_10 = VDEF <SMT.16_6>
> >   *state_in_3(D) = D.1570_2;
> >   # VUSE <SFT.10_8(D), SFT.11_9(D)>
> >   D.1571_4 = fs.reg;
> >   D.1572_5 = (char) D.1571_4;
> >   # SMT.16_11 = VDEF <SMT.16_10>
> >   *state_in_3(D) = D.1572_5;
> >
> >  dependent on which singleton SCC (D.1569_1 = fs.offset or D.1571_4 =
> >  fs.reg) we happen to visit first, either the load from fs.reg or
> >  that of fs.offset is value-numbered to V_C_E <the-other-result>.
> >
> >  The verification makes sure that in the case we would try to replace
> >  the load from fs.offset, the replacement fails (and thus no optimization
> >  is done - we don't re-visit the other SCC to make both transformations
> >  after all).
> >
> >  One trivial adjustment makes the above cases less likely, namely
> >  iterating over all SSA_NAMEs in forward oder rather than backward
> >  order, which happens to more likely visit SCCs in dominator order.
> >  A "real" fix would try to do a topological sort of all SCCs after
> >  collecting them - but this is for another patch.
> >
> >  Bootstrapped and tested on x86_64-unknown-linux-gnu for all
> >  languages and Ada.
> >
> >  Ok for mainline?
> >
> 
> Rather than have may_insert be global, can you store it with the
> tables instead so it isn't global?
> (I understand it would be a serious pain in the ass to push it down
> through all the functions)
> If not, this is fine.

It's not really related to the tables but to if we use SCCVN for FRE
or PRE.  We always "insert" to the valid table, but only during
processing the SCCs, not during later lookups from FRE.

I expect some possible cleanups with the interaction of the tree-vn
code once we switch to the SCCVN IL in PRE/FRE.

So - I'll go ahead with the current version.

Thanks,
Richard.