[tree-ssa] reaching def. question

[tree-ssa] reaching def. question

[Devang Patel]

How do I find out reaching definitions of 'a' at statement S1?

S1:      a = b;

What I want to know is whether S1 is defining 'a' first time
or killing earlier def of 'a'. compute_reaching_defs () is not
yet implemented. Is there any other alternative API?

Thank you,
--
Devang

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Tue, 2004-03-16 at 16:39, Devang Patel wrote:
> How do I find out reaching definitions of 'a' at statement S1?
> 
> S1:      a = b;
> 
> What I want to know is whether S1 is defining 'a' first time
> or killing earlier def of 'a'. compute_reaching_defs () is not
> yet implemented. Is there any other alternative API?
> 
compute_reaching_defs() wouldn't help you.  There are no uses of 'a' in
S1.

You need to do a dominator walk and stop when you find the first
definition.  But, there can be more than one:

	if (...)
	   a = b;
	else
	   a = c;

Both defs to 'a' are defininig 'a' for the "first time".  Besides, in
our current framework.  Every definition is a different variable.

What are you trying to solve?


Diego.

Re: [tree-ssa] reaching def. question

[Devang Patel]

On Mar 16, 2004, at 1:47 PM, Diego Novillo wrote:

> On Tue, 2004-03-16 at 16:39, Devang Patel wrote:
>> How do I find out reaching definitions of 'a' at statement S1?
>>
>> S1:      a = b;
>>
>> What I want to know is whether S1 is defining 'a' first time
>> or killing earlier def of 'a'. compute_reaching_defs () is not
>> yet implemented. Is there any other alternative API?
>>
> compute_reaching_defs() wouldn't help you.  There are no uses of 'a' in
> S1.
>
> You need to do a dominator walk and stop when you find the first
> definition.  But, there can be more than one:
>
> 	if (...)
> 	   a = b;
> 	else
> 	   a = c;
>
> Both defs to 'a' are defininig 'a' for the "first time".  Besides, in
> our current framework.  Every definition is a different variable.
>
> What are you trying to solve?

during if-conversion

S1: a_1 = x;
S2: if (...)
S3:   a_2 = b;

Now, to if-convert S3, I need to know if a_2 is first def. of variable 
'a'
or not. Based on that info I can replace S3 with

S3: MODIFY_EXPR <a_2, COND_EXPR < c, b, a_1>>

OR

S3: MODIFY_EXPR <a_2, COND_EXPR < c, b, NULL>>

--
Devang

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Tue, 2004-03-16 at 16:59, Devang Patel wrote:

> S1: a_1 = x;
> S2: if (...)
> S3:   a_2 = b;
> 
> Now, to if-convert S3, I need to know if a_2 is first def. of variable 
> 'a'
> or not. Based on that info I can replace S3 with
> 
> S3: MODIFY_EXPR <a_2, COND_EXPR < c, b, a_1>>
> 
> OR
> 
> S3: MODIFY_EXPR <a_2, COND_EXPR < c, b, NULL>>
> 
Hmm, you could always if-convert S3 to MODIFY_EXPR <a, COND_EXPR <c, b,
a>> and then mark 'a' for rewriting.  After if-conversion, the renamer
will correctly pick up a_1 or a_0 (ie, a's default definition).

That would be my recommendation.  You won't get NULL, but a's default
def, which amounts to the same thing.

If you want to work hard, you'll need to duplicate the dominator walk
done by the SSA renamer (not really worth it, unless you can prove that
the extra call to the renamer is killing compile time performance).


Diego.

Re: [tree-ssa] reaching def. question

[Devang Patel]

On Mar 16, 2004, at 2:17 PM, Diego Novillo wrote:

> Hmm, you could always if-convert S3 to MODIFY_EXPR <a, COND_EXPR <c, b,
> a>> and then mark 'a' for rewriting.  After if-conversion, the renamer
> will correctly pick up a_1 or a_0 (ie, a's default definition).

OK. We're one the same page. I tried following and it did not work.

I have:

   # BLOCK 1
   # PRED: 15 [100.0%]  (fallthru) 13 [100.0%]  (fallthru)
   # A_24 = PHI <A_18(15), A_10(13)>;
   # i_22 = PHI <i_20(15), 0(13)>;
<L0>:;
   #   VUSE <A_24>;
   T.0_26 = A[i_22];

I convert it into:

   # BLOCK 1
   # PRED: 15 [100.0%]  (fallthru) 13 [100.0%]  (fallthru)
   # A_24 = PHI <A_18(15), A_10(13)>;
   # i_22 = PHI <i_20(15), 0(13)>;
<L0>:;
   #   VUSE <A_24>;
   T.0_26 = if (1)
     {
       A[i_22];
     }
   else
     {
       T.0_26
     };

Now, I mark this modify expr's operand 0's SSA_NAME_VAR for rewriting.

After ssa rewriting I get,


   # BLOCK 1
   # PRED: 15 [100.0%]  (fallthru) 13 [100.0%]  (fallthru)
   # A_11 = PHI <A_10(13), A_3(15)>;
   # i_22 = PHI <i_20(15), 0(13)>;
<L0>:;
   T.0_19 = if (1)
     {
       A[i_22];
     }
   else
     {
       A_26
     };


Maybe I am not marking it properly for rewrite?
--
Devang

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Tue, 2004-03-16 at 17:30, Devang Patel wrote:

>    # BLOCK 1
>    # PRED: 15 [100.0%]  (fallthru) 13 [100.0%]  (fallthru)
>    # A_11 = PHI <A_10(13), A_3(15)>;
>    # i_22 = PHI <i_20(15), 0(13)>;
> <L0>:;
>    T.0_19 = if (1)
>      {
>        A[i_22];
>      }
>    else
>      {
>        A_26
>      };
> 
A_26?  You seem to have a memory problem here.  Are you sure the
operands for COND_EXPR are setup properly?  How did we end up with A
when we had T.0?  Or did you mean T.0_26?  Which is also bad.  If you
want, point me to the patch and I'll take a look.

Side note.  If you give the COND_EXPR a non-void type, it will be
rendered as ?:, which is much more legible.  I would create it with
TREE_TYPE (TREE_OPERAND (stmt, 0)).

Diego.

Re: [tree-ssa] reaching def. question

[Richard Henderson]

On Tue, Mar 16, 2004 at 02:30:35PM -0800, Devang Patel wrote:
>   #   VUSE <A_24>;
>   T.0_26 = if (1)
>     {
>       A[i_22];
>     }
>   else
>     {
>       T.0_26
>     };

This isn't GIMPLE.  The operands to the if need to be is_gimple_val,
not is_gimple_rhs.  You need to introduce a temporary.


r~

Re: [tree-ssa] reaching def. question

[Richard Henderson]

On Tue, Mar 16, 2004 at 05:57:49PM -0500, Diego Novillo wrote:
> Side note.  If you give the COND_EXPR a non-void type, it will be
> rendered as ?:, which is much more legible.  I would create it with
> TREE_TYPE (TREE_OPERAND (stmt, 0)).

Indeed, these types *must* match.


r~

Re: [tree-ssa] reaching def. question

[Devang Patel]

On Mar 16, 2004, at 2:57 PM, Diego Novillo wrote:

> On Tue, 2004-03-16 at 17:30, Devang Patel wrote:
>
>>    # BLOCK 1
>>    # PRED: 15 [100.0%]  (fallthru) 13 [100.0%]  (fallthru)
>>    # A_11 = PHI <A_10(13), A_3(15)>;
>>    # i_22 = PHI <i_20(15), 0(13)>;
>> <L0>:;
>>    T.0_19 = if (1)
>>      {
>>        A[i_22];
>>      }
>>    else
>>      {
>>        A_26
>>      };
>>
> A_26?

yup. That's when I realized something is wrong hence original question.

> You seem to have a memory problem here.  Are you sure the
> operands for COND_EXPR are setup properly?  How did we end up with A
> when we had T.0?

No idea.
OK, so rewriter is suppose to handle this (use of variable before it is
defined) and there is a problem somewhere. I will investigate this.

>  Or did you mean T.0_26?  Which is also bad.  If you
> want, point me to the patch and I'll take a look.

I'll try if I can extract short patch which is meaningful and send it
to you offline.

> Side note.  If you give the COND_EXPR a non-void type, it will be
> rendered as ?:, which is much more legible.  I would create it with
> TREE_TYPE (TREE_OPERAND (stmt, 0)).

good idea.

Thank you,
--
Devang

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Tue, 2004-03-16 at 18:06, Richard Henderson wrote:

> On Tue, Mar 16, 2004 at 02:30:35PM -0800, Devang Patel wrote:
> >   #   VUSE <A_24>;
> >   T.0_26 = if (1)
> >     {
> >       A[i_22];
> >     }
> >   else
> >     {
> >       T.0_26
> >     };
> 
> This isn't GIMPLE.  The operands to the if need to be is_gimple_val,
> not is_gimple_rhs.  You need to introduce a temporary.
> 
Oh, right.  Devang, when you create COND_EXPRs, make sure you either (a)
call the gimplifier to request is_gimple_val, or (b) gimplify the
operands yourself before building it.  In this case, (b) is probably
just as easy.


Diego.

Re: [tree-ssa] reaching def. question

[Devang Patel]

On Mar 16, 2004, at 3:13 PM, Diego Novillo wrote:

> On Tue, 2004-03-16 at 18:06, Richard Henderson wrote:
>
>> On Tue, Mar 16, 2004 at 02:30:35PM -0800, Devang Patel wrote:
>>>   #   VUSE <A_24>;
>>>   T.0_26 = if (1)
>>>     {
>>>       A[i_22];
>>>     }
>>>   else
>>>     {
>>>       T.0_26
>>>     };
>>
>> This isn't GIMPLE.  The operands to the if need to be is_gimple_val,
>> not is_gimple_rhs.  You need to introduce a temporary.
>>
> Oh, right.  Devang, when you create COND_EXPRs, make sure you either 
> (a)
> call the gimplifier to request is_gimple_val, or (b) gimplify the
> operands yourself before building it.  In this case, (b) is probably
> just as easy.

OK. I was planning to gimplify condition only.

--
Devang

Re: [tree-ssa] reaching def. question

[law]

In message <1079475458.3173.461.camel@localhost.localdomain>, Diego Novillo wri
tes:
 >On Tue, 2004-03-16 at 16:59, Devang Patel wrote:
 >
 >> S1: a_1 = x;
 >> S2: if (...)
 >> S3:   a_2 = b;
 >> 
 >> Now, to if-convert S3, I need to know if a_2 is first def. of variable 
 >> 'a'
 >> or not. Based on that info I can replace S3 with
 >> 
 >> S3: MODIFY_EXPR <a_2, COND_EXPR < c, b, a_1>>
 >> 
 >> OR
 >> 
 >> S3: MODIFY_EXPR <a_2, COND_EXPR < c, b, NULL>>
 >> 
 >Hmm, you could always if-convert S3 to MODIFY_EXPR <a, COND_EXPR <c, b,
 >a>> and then mark 'a' for rewriting.  After if-conversion, the renamer
 >will correctly pick up a_1 or a_0 (ie, a's default definition).
It seems to me that to do that he must first take the affected variables
out of SSA form.  Otherwise how does the renamer know which instance of
"a" ought to be used?


jeff

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Tue, 2004-03-16 at 18:42, law@redhat.com wrote:

> It seems to me that to do that he must first take the affected variables
> out of SSA form.  Otherwise how does the renamer know which instance of
> "a" ought to be used?
> 
If you mark a _DECL to be renamed, the renamer itself strips the
SSA_NAME wrappers.  Or you mean *really* taking the variable out of SSA
form?

In this case, the renamer should never use the version of 'a' on the LHS
of the assignment, as it comes from the same statement.


Diego.

Re: [tree-ssa] reaching def. question

[law]

In message <1079481013.3173.481.camel@localhost.localdomain>, Diego Novillo wri
tes:
 >On Tue, 2004-03-16 at 18:42, law@redhat.com wrote:
 >
 >> It seems to me that to do that he must first take the affected variables
 >> out of SSA form.  Otherwise how does the renamer know which instance of
 >> "a" ought to be used?
 >> 
 >If you mark a _DECL to be renamed, the renamer itself strips the
 >SSA_NAME wrappers.
Which is not a safe thing to do if you've done things like copy propagation
since you can have overlapping lifetimes.

You also have to be damn careful about marking something to be rewritten
which is used in a mixed PHI node.  ie

a_3 = PHI (a_2, b_1)

Marking just a or b to be written is a recipe for disaster.


 > Or you mean *really* taking the variable out of SSA form?
If you've done things like copy propagation and the like, then yes,  you
really need to take it out of SSA form.


jeff

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Tue, 2004-03-16 at 19:27, law@redhat.com wrote:

> Which is not a safe thing to do if you've done things like copy propagation
> since you can have overlapping lifetimes.
> 
We do this all the time.  Passes just mark the variables they want to be
renamed and the SSA renamer is run as a cleanup.

> You also have to be damn careful about marking something to be rewritten
> which is used in a mixed PHI node.  ie
> 
> a_3 = PHI (a_2, b_1)
> 
> Marking just a or b to be written is a recipe for disaster.
> 
More context, with concrete examples, please.  Are you talking about
copyprop *while* doing if-conversion?


Diego.

Re: [tree-ssa] reaching def. question

[Devang Patel]

On Mar 16, 2004, at 4:27 PM, law@redhat.com wrote:

> You also have to be damn careful about marking something to be 
> rewritten
> which is used in a mixed PHI node.  ie
>
> a_3 = PHI (a_2, b_1)

This is new to me. When do I expect to see mixed PHI node? An example
would help me to  understand it.

Thank you,
--
Devang

Re: [tree-ssa] reaching def. question

[law]

In message <1079483792.3173.491.camel@localhost.localdomain>, Diego Novillo wri
tes:
 >On Tue, 2004-03-16 at 19:27, law@redhat.com wrote:
 >
 >> Which is not a safe thing to do if you've done things like copy propagation
 >> since you can have overlapping lifetimes.
 >> 
 >We do this all the time.  Passes just mark the variables they want to be
 >renamed and the SSA renamer is run as a cleanup.
They do this for newly exposed variables and possibly virtuals.  They do
not do this for real variables which have already been rewritten.  Re-rewriting
an existing variable is a non-trivial exercise.  


 >> You also have to be damn careful about marking something to be rewritten
 >> which is used in a mixed PHI node.  ie
 >> 
 >> a_3 = PHI (a_2, b_1)
 >> 
 >> Marking just a or b to be written is a recipe for disaster.
 >> 
 >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.
jeff

Re: [tree-ssa] reaching def. question

[law]

In message <11A7C99E-77AD-11D8-9053-000393A91CAA@apple.com>, Devang Patel write
s:
 >
 >On Mar 16, 2004, at 4:27 PM, law@redhat.com wrote:
 >
 >> You also have to be damn careful about marking something to be 
 >> rewritten
 >> which is used in a mixed PHI node.  ie
 >>
 >> a_3 = PHI (a_2, b_1)
 >
 >This is new to me. When do I expect to see mixed PHI node? An example
 >would help me to  understand it.
It happens on a regular basis due to copy propagation.

For example if you had

  if (cond)
    a_4 = b_1;
  else
    a_2 = p + q;

  a_3 = PHI (a_2, a_4);

Copy propagation would turn the PHI into:

  a_3 = PHI (a_2, b_1);


 
   
jeff

Re: [tree-ssa] reaching def. question

[Zdenek Dvorak]

Hello,

>  >On Tue, 2004-03-16 at 18:42, law@redhat.com wrote:
>  >
>  >> It seems to me that to do that he must first take the affected variables
>  >> out of SSA form.  Otherwise how does the renamer know which instance of
>  >> "a" ought to be used?
>  >> 
>  >If you mark a _DECL to be renamed, the renamer itself strips the
>  >SSA_NAME wrappers.
> Which is not a safe thing to do if you've done things like copy propagation
> since you can have overlapping lifetimes.
> 
> You also have to be damn careful about marking something to be rewritten
> which is used in a mixed PHI node.  ie
> 
> a_3 = PHI (a_2, b_1)
> 
> Marking just a or b to be written is a recipe for disaster.
> 
> 
>  > Or you mean *really* taking the variable out of SSA form?
> If you've done things like copy propagation and the like, then yes,  you
> really need to take it out of SSA form.

I have thought about this issue for some time -- would not it be better
to do ssa rewriting over ssa names, thus not requiring the rewrite out
of ssa? I.e. to allow the ssa name temporarily have several definitions,
and do rewriting just over them?  It might be faster.  It also would not
need to do rewriting out of ssa, which may require you to insert new
assignments that must be later optimized out.  It would also allow you
not to lose ssa name tags in the process.

Zdenek

Re: [tree-ssa] reaching def. question

[Diego Novillo]

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.

Re: [tree-ssa] reaching def. question

[law]

In message <1079535066.32455.54.camel@localhost.localdomain>, Diego Novillo wri
tes:
 >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.
Please stay in contact with me before you do this.  I'm also going to likely
be in this code as there are some serious compile-time performance issues
that need to be addressed.

jeff

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Wed, 2004-03-17 at 02:21, Zdenek Dvorak wrote:

> I have thought about this issue for some time -- would not it be better
> to do ssa rewriting over ssa names, thus not requiring the rewrite out
> of ssa?
>
That was the original design, yes.  See my other reply to this thread
earlier today.

>  I.e. to allow the ssa name temporarily have several definitions,
> and do rewriting just over them?  It might be faster.  It also would not
> need to do rewriting out of ssa, which may require you to insert new
> assignments that must be later optimized out.  It would also allow you
> not to lose ssa name tags in the process.
> 
It would also reduce the "missing variable" problem, like in the example
I quoted before.  We'll see.


Diego.

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Wed, 2004-03-17 at 09:58, law@redhat.com wrote:

> Please stay in contact with me before you do this.  I'm also going to likely
> be in this code as there are some serious compile-time performance issues
> that need to be addressed.
> 
Yeah, DOM needs to be taken apart and reassembled.  We've talked about
it several times.  I have half a mind of doing it before the merge, but
perhaps we should wait.  Unless you get to it before the final merge? 
That'd be great.


Diego.

Re: [tree-ssa] reaching def. question

[law]

In message <1079536405.32455.66.camel@localhost.localdomain>, Diego Novillo wri
tes:
 >On Wed, 2004-03-17 at 09:58, law@redhat.com wrote:
 >
 >> Please stay in contact with me before you do this.  I'm also going to likel
 >y
 >> be in this code as there are some serious compile-time performance issues
 >> that need to be addressed.
 >> 
 >Yeah, DOM needs to be taken apart and reassembled.  We've talked about
 >it several times.  I have half a mind of doing it before the merge, but
 >perhaps we should wait.  Unless you get to it before the final merge? 
 >That'd be great.
Well, I do expect to be inside it again before the final merge due to
some performance issues, but it's probably still at least a week before
I'll be able to start looking at it.


jeff

Re: [tree-ssa] reaching def. question

[law]

In message <1079536309.32455.62.camel@localhost.localdomain>, Diego Novillo wri
tes:
 >On Wed, 2004-03-17 at 02:21, Zdenek Dvorak wrote:
 >
 >> I have thought about this issue for some time -- would not it be better
 >> to do ssa rewriting over ssa names, thus not requiring the rewrite out
 >> of ssa?
 >>
 >That was the original design, yes.  See my other reply to this thread
 >earlier today.
Can one of y'all walk me through this and how it would work when the dominator
tree changes?

If you can make it work in that situation, then we'd be able to simplify
a goodly amount of code in the dominator optimizer.


jeff

Re: [tree-ssa] reaching def. question

[Daniel Berlin]

On Wed, 17 Mar 2004 law@redhat.com wrote:

> In message <1079536309.32455.62.camel@localhost.localdomain>, Diego Novillo wri
> tes:
>  >On Wed, 2004-03-17 at 02:21, Zdenek Dvorak wrote:
>  >
>  >> I have thought about this issue for some time -- would not it be better
>  >> to do ssa rewriting over ssa names, thus not requiring the rewrite out
>  >> of ssa?
>  >>
>  >That was the original design, yes.  See my other reply to this thread
>  >earlier today.
> Can one of y'all walk me through this and how it would work when the dominator
> tree changes?
>
> If you can make it work in that situation, then we'd be able to simplify
> a goodly amount of code in the dominator optimizer.
There's a paper on exactly this type of incremental update to SSA
somewhere.
I'll try to find it if someone doesn't explain it satisfactorily
beforehand.

Re: [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

Re: [tree-ssa] reaching def. question

[law]

In message <Pine.LNX.4.56.0403171348290.3322@dberlin.org>, Daniel Berlin writes
:
 >
 >
 >On Wed, 17 Mar 2004 law@redhat.com wrote:
 >
 >> In message <1079536309.32455.62.camel@localhost.localdomain>, Diego Novillo
 > wri
 >> tes:
 >>  >On Wed, 2004-03-17 at 02:21, Zdenek Dvorak wrote:
 >>  >
 >>  >> I have thought about this issue for some time -- would not it be better
 >>  >> to do ssa rewriting over ssa names, thus not requiring the rewrite out
 >>  >> of ssa?
 >>  >>
 >>  >That was the original design, yes.  See my other reply to this thread
 >>  >earlier today.
 >> Can one of y'all walk me through this and how it would work when the domina
 >tor
 >> tree changes?
 >>
 >> If you can make it work in that situation, then we'd be able to simplify
 >> a goodly amount of code in the dominator optimizer.
 >There's a paper on exactly this type of incremental update to SSA
 >somewhere.  I'll try to find it if someone doesn't explain it satisfactorily
 >beforehand.
I've seen stuff for incremental updates when adding new assginments.  I have
not seen stuff for incremental updates when changing the dominator tree.  If
you've got the latter, I'd love to get a copy.

jeff

Re: [tree-ssa] reaching def. question

[David Edelsohn]

	I have been discussing the SSA rewriting issues with a colleague
and friend of mine, Kenny Zadeck.  He asked me to forward the appended
comments to this discussion.

David

----- Begin Forwarded Message -----

Date: Wed, 17 Mar 2004 15:22:37 -0500
From: Kenneth Zadeck <zadeck@naturalbridge.com>
To: "Edelsohn, David" <dje@watson.ibm.com>
Subject: Re: [tree-ssa] reaching def. question

There are many differences between coming out of ssa form and leaving it
ssa form for ever:

"Coming out" of SSA form has some costs as well as some benefits.  We
(at NaturalBridge) go into SSA form early and never come out.  In the
compilers I have worked on (both here and at IBM), we left it in SSA
form for ever.

By not coming out, I am assuming that the program is broken in SSA
form and each SSA variable has a pointer to the original source
program variable for debugging, but not much else.  By coming out of
SSA form, I am assuming that you are first breaking source variables
into independent def-use chain webs (in IBM parlance solving the
"right number of names problem" and that each of these webs becomes
a real variable that the ssa variable map back to.

the benefits of coming out of SSA form:
  1) compatibility with later phases that will not understand this.
  2) easier to implement debugger if there are no overlapping ranges.
  3) space, there are a much smaller number of webs than ssa variables.

the benefits of never coming out (or at least deferring it as long as
possible):

  1) overlapping names are the norm rather than a special case in SSA
  form.  The only transformations that do not create overlapping names
  are the ones that simply delete code (for example constant
  propagation and dead code elimination). Any transformation that can
  move code around (for example partial redundancy elimination and
  loop invariant code motion) will create a potentially large number
  of overlapping names; the more aggressive forms of these
  transformations that you implement the more overlapping names you
  will create.

  Shortly after we developed SSA form, we noticed that many of the
  good optimizations had the property that they created overlapping
  live ranges.  (Our invariant code motion algorithm generates
  zillions of overlapping live ranges.) At first we thought this was a
  problem but then we decided that unless you did this, you were
  closing off a huge number of profitable transformations.  This
  meshed well with the notion that machines would soon have as John
  Cocke put it "as many registers as you would ever need, say 32".

  In particular, loop optimizations such as unrolling, create many
  opportunities for the moving transformations to create many
  overlapping live ranges since a lot of code from one iteration will
  be redundant with the previous iteration.

  As you seem to have discovered, even something as simple as if
  conversion with the right transformations can cause overlapping
  ranges.  However, as you start doing the really aggressive stuff,
  this will be the norm and not the exception.

  2) Lots of names in general means better optimization.  At the
  admitted cost of extra space and time, the smaller granularity of
  treating the SSA variables as first class variables will in general
  lead to better packing of registers and a smaller number of copy
  statements.  In the coming out world, there is an implicit
  assumption that all of the ssa variables associated with the web
  will be treated the same way.

  Later, if you implement good profile directed compiling coming out
  of SSA form will turn out to be a bad assumption because the smaller
  granularity of the SSA variables will allow you to get stellar code
  on the fast path and do a poorer job on the off path code that is
  represented in the other SSA variables.  The webs will have too much
  code in them.

"Going out" of ssa form may be necessary to interface the compiler
with the current debugger, code generator, and register allocator
which may not be designed to handle the load of the large number of
variables and the potential large number of copy statements that are
now necessary to glue this together.  However, when you do this, there
is little (beyond the debugging info) to be gained by using the
original naming as the guide.


Kenneth Zadeck
zadeck@naturalbridge.com

----- End Forwarded Message -----

Re: [tree-ssa] reaching def. question

[Daniel Berlin]

>  >>
>  >> If you can make it work in that situation, then we'd be able to simplify
>  >> a goodly amount of code in the dominator optimizer.
>  >There's a paper on exactly this type of incremental update to SSA
>  >somewhere.  I'll try to find it if someone doesn't explain it satisfactorily
>  >beforehand.
> I've seen stuff for incremental updates when adding new assginments.  I have
> not seen stuff for incremental updates when changing the dominator tree.  If
> you've got the latter, I'd love to get a copy.
I remember seeing the latter.
As soon as citeseer is back up, i'll find it for you (Or am i the only one
who can't connect to citeseer).

Re: [tree-ssa] reaching def. question

[Diego Novillo]

On Wed, 2004-03-17 at 17:18, Daniel Berlin wrote:

> As soon as citeseer is back up, i'll find it for you (Or am i the only one
> who can't connect to citeseer).
> 
Nope.  It was down yesterday, too.


Diego.

Citeseer's replacement?

[Scott A Crosby]

This was forwarded to me.


From: Moshe Vardi <vardi@cs.rice.edu>
Subject: CiteSeer's Future
To: faculty@cs.rice.edu, phd@cs.rice.edu
Date: Fri, 12 Mar 2004 12:59:51 -0600 (CST)

Note that citeseer.org is no available anymore.
You can still access CiteSeer at http://citeseer.ist.psu.edu/

Moshe
-------------------------------------------------------------------------

http://chronicle.com/daily/2004/03/2004031204n.htm

New Database to Track Citations of Online Scholarship
By VINCENT KIERNAN

The company that compiles highly influential databases on the use of
scholarly papers in print has decided to gather similar information on
scholarly works that are disseminated solely online, often without peer
review. The tool could prove a boon to the distribution of scholarship
in cyberspace.

Thomson ISI announced last month that it would create the Web Citation
Index. The database will list which scholarly works have cited
particular papers published online, said James Pringle, vice president
for development. It also will track citations of traditionally published
works by online papers, but it will remain separate from the company's
database of citations of peer-reviewed journals.

The new database will be tested this year, and the company plans to sell
full access to it in 2005, Mr. Pringle said.

Citation rates of papers in printed journals, as compiled by Thomson ISI
in products such as its Web of Science database, play an important role
in promotion and tenure decisions, particularly in the sciences.

Colleges frequently evaluate scholars in terms of how often their work
is cited and whether they have published it in journals that are highly
cited in general. Some departments have gone as far as to tout the
collective "impact factors" of their faculty members, and college
libraries have used the citation statistics in deciding on whether to
subscribe to expensive scholarly journals.

However, scholars have complained that the lack of similar information
about citations of online papers has discouraged them and their
colleagues from disseminating their papers online, whether on Web sites
and preprint servers or in repositories of papers that have not yet been
peer-reviewed.

The new database may encourage the use of preprint servers, which are
databases containing the full texts of papers that have not yet passed
formal peer review, and other online venues for scholarly research
because scholars will be able to document the impact their work has had
on others, said Mary Case, director of the scholarly-communication
office at the Association of Research Libraries.

"It will make the preprint servers so much more visible," she said.

But Julie M. Hurd, science librarian at the University of Illinois at
Chicago, predicted that the new citation statistics would be slow to
influence online publication because colleges remain leery of it.

"The people who make the promotion and tenure decisions are still stuck
on the model of print," said Ms. Hurd, who is one of the editors of From
Print to Electronic: The Transformation of Scientific Communication
(Information Today, 1996). "The coin of the realm is still the journal
article."

The Web Citation Index will remain separate from Thomson ISI's other
citation index. "There is no particular plan for some sort of integrated
impact factor," said Mr. Pringle, adding that the traditional index
already includes some peer-reviewed scholarly journals that are
available online.

The company is collaborating on the Web Citation Index with NEC
Laboratories America, which has developed programs for finding online
papers and analyzing the citations in them. NEC has developed a digital
library of computer-science research, and so the compilation of the Web
Citation Index will probably start with papers in that field, said Mr.
Pringle.

Because most online scholarly materials are in the physical sciences,
with relatively little in the social sciences, he said, he expects the
new index to concentrate on the physical sciences.

But using a computer program to identify the material to be covered by
the index may be a challenge. "The tough part is to find the good
stuff," said George S. Porter, a science librarian at the California
Institute of Technology.

Papers on well-known preprint servers and on Web sites with addresses
ending in ".edu" may be safe bets for NEC's software to index, Mr.
Porter said. "But when you get a bit further afield, it's harder to
recognize scholarly material."

Editors at Thomson ISI will be involved in the indexing process to make
sure that only genuine scholarly papers are covered, Mr. Pringle said.

Copyright © 2004 by The Chronicle of Higher Education

Re: [tree-ssa] reaching def. question

[law]

In message <1079543327.9691.15.camel@p4>, Andrew MacLeod writes:
 >I also think at some point we need to stop taking all versions of an SSA
 >variable out of, and back into SSA, and focus just on the ones we need.
 >Things like copyrenaming which changes the base variable of an
 >ssa_version could wreak havoc on such activity. 
I certainly can't disagree with this.  We do this in response to jump
threading changing the dominator tree -- I wouldn't be terribly surprised
if we could come up with an incremental way to handle this which didn't
require taking all the versions of affected variables out of SSA form.

Jeff

Re: [tree-ssa] reaching def. question

[Andrew MacLeod]

On Wed, 2004-03-17 at 11:43, Chris Lattner wrote:
> 
> Diego Novillo wrote:
> > 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.
> 
> At least in the case of SGI, I understood that they implemented it that
> way for two reasons: 1. avoid an increase in register pressure, and 2.
> work better with the legacy compiler optimizations they already had.
> 
> #2 certainly makes a lot of sense, and this decision also made their
> implementation of (e.g.) SSAPRE simpler, but I have a hard time buying
> argument #1.
> 
> For the record, LLVM allows arbitrary overlapping of virtual registers.
> We don't even have "versions" or an "out of SSA renamer".  In my
> *extremely biased* opinion, this makes it a lot easier to reason about
> what code does, e.g., making it trivial to answer Devang's original
> question.
> 

There has certainly been discussion of moving/delaying the ssa->normal
phase right up to the rtl generation stage, at which point all the
ssa_versions become distinct registers in rtl, and hopefully lots of
coalescing through PHI nodes to avoid copies. At that point, SSA->normal
becomes just a PHI node coalescer. I think that boils down to the same
thing you are talking about. We currently have to go back into non-ssa
form in order for the current expanders to work properly. That will not
be a permanent limitation. 

I also think at some point we need to stop taking all versions of an SSA
variable out of, and back into SSA, and focus just on the ones we need.
Things like copyrenaming which changes the base variable of an
ssa_version could wreak havoc on such activity. 

Andrew

Re: [tree-ssa] reaching def. question

[Chris Lattner]

Diego Novillo wrote:
> 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.

At least in the case of SGI, I understood that they implemented it that
way for two reasons: 1. avoid an increase in register pressure, and 2.
work better with the legacy compiler optimizations they already had.

#2 certainly makes a lot of sense, and this decision also made their
implementation of (e.g.) SSAPRE simpler, but I have a hard time buying
argument #1.

For the record, LLVM allows arbitrary overlapping of virtual registers.
We don't even have "versions" or an "out of SSA renamer".  In my
*extremely biased* opinion, this makes it a lot easier to reason about
what code does, e.g., making it trivial to answer Devang's original
question.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/