[RFC] New SSA variable mapping infrastructure

[Richard Guenther]

On 11/7/07, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Nov  7, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:
>
> > int foo(int i, int j)
> > {
> >   int l = j + i * 10;
> >   int k = i * 10;
> >   return l + k;
> > }
>
> > foo (i, j)
> > {
> >   int D.1545;
>
> > <bb 2>:
> >   D.1545 = i * 10 E{ k };
> >   return (D.1545 + D.1545) + j;
> > }
>
> In this case, there's not much harm done in annotating the assignment
> to D.1545 as an assignment to k.  It's close enough, even in the same
> block.  But what if it wasn't?  What if k had a value before, that is
> live into the separate basic block?  What if the assignment is
> conditional?
>
> And what happened to l?

l is no longer a value that is computed (we do not compute D.1545 + j, but
only D.1545 + D.1545 and the final sum.  This is what I mean with "preserving
values" - values that are no longer computed do not have their values retained)

> Consider:
>
> int foo(int i, int j) {
>   int l = j + i * 10;
>   int k = 0;
>
>   if (i < j) {
>     k = i * 10;
>     breakpoint1();
>   } else
>     breakpoint2();
>   }
>
>   breakpoint3();
>
>   return l + k;
> }
>
> Given your infrastructure, if I set breakpoints in the empty
> uninlinable breakpoint* functions, go up a frame and print k, what
> will you get, assuming the optimized code just before out-of-ssa ends
> up looking like this:
>
> int foo(int i, int j) {
>   int D;
>   int k;
>
>  <bb 2>:
>   D_2 = i_1(D) * 10; /* E { k } ? */
>   if (i_1(D) < j_4(D))
>     goto <bb 3>;
>   else
>     goto <bb 4>;
>
>  <bb 3>:
>    breakpoint1();
>    goto <bb 5>;
>
>  <bb 4>:
>    breakpoint2();
>    goto <bb 5>;
>
>  <bb 5>:
>    # k_3 = PHI<D(3), 0(4)>;
>    breakpoint3();
>    return j_4(D) + D_2 + k_3;
> }

While in general if you have a single location and multiple names for it there
are things you cannot work around (but you can just declare them as designed
as such).  For example if in register 'ax' you have a value that has names 'a'
and 'd', what happens if in the debugger you set 'a'?  Of course the
value of 'd'
also changes - 'a' and 'd' have been CSEd and we certainly don't want to undo
this transformation.

Now onto the above case.  What we end up with after tree optimizations in
the moment is:

foo (i, j)
{
  int k.5;
  int k;

<bb 2>:
  k.5 = i * 10 E{ k };
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  k = k.5;
  goto <bb 5>;

<bb 4>:
  k = 0;

<bb 5>:
  return (j + k.5 E{ l }) + k;

}

That is, i * 10 has the name 'k' (yes, computed unconditionally - but it is also
life in the relevant block), we still compute 'l' in this case, as j +
k.5, and the
final value in 'k' after the merge will be either 0 or i * 10.

I believe you cannot do better here unless you limit optimization.

With VTA I see (final_cleanup again):

foo (i, j)
{
  int k.5;
  int k;

<bb 2>:
  k.5 = i * 10;
  # DEBUG l optimized away;
  # DEBUG k = 0;
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  k = k.5;
  goto <bb 5>;

<bb 4>:
  k = 0;

<bb 5>:
  # DEBUG k = k;
  return (j + k.5) + k;

}

so you lost 'l' (I didn't ;)) and from what I see you might in this
case avoid making
the value i * 10 globally associated to 'k' because you track constants in debug
expressions?  (I didn't investigate what this means to debug information).  So
let's avoid having k constant in one path:

int foo(int i, int j)
{
  int l = j + i*10;
  int k = j + i;
  if (i < j)
    k = i * 10;
  return l + k;
}

I get

foo (i, j)
{
  int k.5;
  int k;

<bb 2>:
  k.5 = i * 10 E{ k };
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  k = k.5;
  goto <bb 5>;

<bb 4>:
  k = j + i;

<bb 5>:
  return (j + k.5 E{ l }) + k;

}

which is basically the same situation as before.  With VTA we get

foo (i, j)
{
  int k.5;
  int k;

<bb 2>:
  k.5 = i * 10;
  # DEBUG l optimized away;
  # DEBUG k optimized away;
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  k = k.5;
  goto <bb 5>;

<bb 4>:
  k = j + i;

<bb 5>:
  # DEBUG k = k;
  return (j + k.5) + k;

}

which looks confusing somehow (it looks to me that some of the 'k' in DEBUG
exprs should be 'k.5'?)  But maybe you can explain what happens to what names
here?

Thanks,
Richard.