[PATCH] Teach SCCVN/PRE about type-punning through unions

[Daniel Berlin]

On Tue, Mar 4, 2008 at 4:13 AM, Richard Guenther <rguenther@suse.de> wrote:
>
> On Mon, 3 Mar 2008, Daniel Berlin wrote:
>
>  > On Mon, Mar 3, 2008 at 7:25 AM, Richard Guenther <rguenther@suse.de> wrote:
>  > >
>  > >  This patch is an alternate implementation to
>  > >  http://gcc.gnu.org/ml/gcc-patches/2008-02/msg01422.html
>  > >  to optimize type-punning operations through unions to use scalar
>  > >  operations (aka VIEW_CONVERT_EXPR).
>  > >
>  > >  It does so by doing (pseudo-)insertion of new expressions with an
>  > >  associated SSA_NAME (to hold its value number) during the final
>  > >  SCC iteration.  At PRE/FRE elimination time these expressions are
>  > >  inserted in place of the SSA_NAME (that is, no real insertion takes
>  > >  place, but we replace with an expression instead of an SSA_NAME),
>  > >  properly re-constructed with using expression leaders for its
>  > >  operands (where available).
>  > >
>  > >  Variants of this approach would be to add the fake SSA_NAMEs
>  > >  during regular SCC iteration, but then also to the SCC itself
>  > >  (which was too tricky for me, thus only doing that at the final
>  > >  iteration).
>  > >
>  > >  On the PRE/FRE side a new insertion phase after SCCVN could insert
>  > >  the expressions explicitly (like we insert fake stores);  I don't
>  > >  know if this would fix anything or make anything easier at the
>  > >  point of insertion though (at least we would only insert a replacement
>  > >  expression once).  The problem with availability we face is that for
>  > >
>  > >  union { int i; float f; } u;
>  > >
>  > >   # VUSE <u_1>
>  > >   tmp_2 = u.i;
>  > >   # VUSE <u_1>
>  > >   tmp_1 = u.f;
>  > >
>  > >  SCCVN (randomly?) processes the SCCs for tmp_1 and tmp_2 and thus
>  > >  can end up value-numbering tmp_2 as VIEW_CONVERT_EXPR <tmp_1> which
>  > >  obviously would violate SSA form.
>  >
>  > It should be sorting them into RPO so that we process tmp_2 before tmp_1.
>  >
>  > Is this not happening?
>  > If so, we should fix it :)
>
>  I don't see we process uses in any particular order (we sort members
>  of an SCC).  But - what is RPO again? ;)

Errr, DFS guarantees a particular order, buddy ;)
Then we sort the SCC's into reverse postorder.

>
>  In this case the two defining statements are connected only through
>  a common VUSE, tmp_2 and tmp_1 are not member of the same SCC.

Oh, then yes, you can't value number them like you want to, because
there is no ordering guarantee.

If you do the view_convert stuff ahead of time, it would work right
because DFS would process them in the right order.

>
>  We would need to process SCCs and uses in dominator order, which
>  obviously doesn't happen.  But maybe we don't need to for
>  optimality?

If you like, you can change the order we decide to start DFS of uses.
You can't change the order in which we process SCC's, it is required
for proper termination and optimality.