Re: [tree-ssa] reaching def. question

[Diego Novillo <dnovillo at redhat dot com>]

On Tue, 2004-03-16 at 22:30, law@redhat.com wrote:

>  >More context, with concrete examples, please.  Are you talking about
>  >copyprop *while* doing if-conversion?
> No, I'm talking about cases where it is not safe to simply drop version
> numbers, then rewrite the variables into SSA form again.
>
I was hoping you would provide more helpful details than "not safe" or
"non-trivial" :)

Devang, say you had this original code (admittedly contrived):

foo (int b)
{
  int a = b;
 
loop:
  if (b > 0)
    {
      b = bar (a);
      goto loop;
    }
 
  return a + b;
}

which is renamed into

foo (b)
{
  int a, T.0;
 
  a_3 = b_2;
 
  # b_1 = PHI <b_2(0), b_6(2)>;
loop:;
  if (b_1 > 0) goto <L1>; else goto <L2>;
 
<L1>:;
  T.0_5 = bar (a_3);
  b_6 = T.0_5;
  goto <bb 1> (loop);
 
<L2>:;
  return a_3 + b_1;
}

which copy propagation turns into

foo (b)
{
  int a, T.0;
 
  a_3 = b_2;
 
  # b_1 = PHI <b_2(0), b_5(2)>;
loop:;
  if (b_1 > 0) goto <L1>; else goto <L2>;
 
<L1>:;
  b_5 = bar (b_2);
  b_6 = b_5;
  goto <bb 1> (loop);
 
<L2>:;
  return b_2 + b_1;
}

Notice how copy propagation has made two different versions of 'b' to be
live simultaneously (return b_2 + b_1).  If we were to mark 'b' for
renaming, the SSA renamer would incorrectly rename the last statement
into something like 'return b_1 + b_1', because from its point of view,
both 'b's are the same object.

So, what we need to do is first take 'b' out of SSA form by creating a
different DECL to represent it.  If you look at the last output from the
tree optimizers you will see that variable 'a' has disappeared and a new
variable 'b.1' has been created in its place.

foo (b)
{
  int b.1;

<bb 0>:
  if (b > 0) goto <L1>; else goto <L8>;
 
loop:;
  if (b.1 > 0) goto <L1>; else goto <L2>;
 
<L1>:;
  b.1 = bar (b);
  goto <bb 1> (loop);
 
<L8>:;
  b.1 = b;
 
<L2>:;
  return b + b.1;
}

The fact that we allow overlapping live ranges for different SSA
versions of the same variable, forces us to have an out of SSA pass that
creates new _DECLs when it detects these situations created by copy
propagation (mostly).

In fact, this is one of the design decisions that we changed early on in
the project.  I had originally implemented an SSA form that did not need
an out-of-ssa pass.  You could just drop the SSA_NAME wrappers because
no overlapping live ranges would occur.  Other compilers (IBM's and
SGI's) do the same, but to date I have not found a convincing
explanation favouring one design over the other.  It is in my medium
term plans to revisit this and see if we can finally determine which one
is better.  My gut feeling is that they're both roughly the same, but I
don't know for certain.

Currently, DOM is careful to call out-of-ssa every time it needs to
rename variables that may have been moved around like this.  This is a
design bug.  Taking variables out of SSA ought to be done by the
renamer.  Individual passes should be free to mark *any* variable to be
renamed.  I will try and get to this before the merge.


Diego.