[tree-ssa] reaching def. question

[Devang Patel]

On Mar 17, 2004, at 6:51 AM, Diego Novillo wrote:

> 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.

OK. Meanwhile, I will concentrate on other parts of if-conversion.
Thank you for your detailed explanation.

--
Devang