[tree-ssa vs lno] who is right?

[tree-ssa vs lno] who is right?

[Dale Johannesen]

When the LNO branch copies a loop, it attempts to fix up the phi nodes 
with
an algorithm that assumes there is only one phi per block per variable. 
  That is, it
won't see code like this:

;; basic block 19, loop depth 0, count 0
;; prev block 9, next block 20
;; pred:       10 [100.0%]  (fallthru)
;; succ:       28 [50.0%]  (true,exec) 29 [50.0%]  (false,exec)
# maxmin_Result_140 = PHI <1(10)>;
# maxmin_Result_142 = PHI <2(10)>;
# lsm_tmp.19_144 = PHI <lsm_tmp.19_84(10)>;
<L28>:;
if (m__10 == 0) goto <L26>; else goto <L27>;

Is that suppose to be a valid assumption?  The dup is created by 
copyrename, and
I see no code there that's intended to stop dups from being created (on 
the
contrary, but surely it's unusual for the live ranges to overlap).

Re: [tree-ssa vs lno] who is right?

[Diego Novillo]

On Thu, 2004-03-25 at 20:29, Dale Johannesen wrote:

> ;; basic block 19, loop depth 0, count 0
> ;; prev block 9, next block 20
> ;; pred:       10 [100.0%]  (fallthru)
> ;; succ:       28 [50.0%]  (true,exec) 29 [50.0%]  (false,exec)
> # maxmin_Result_140 = PHI <1(10)>;
> # maxmin_Result_142 = PHI <2(10)>;
> # lsm_tmp.19_144 = PHI <lsm_tmp.19_84(10)>;
> <L28>:;
> if (m__10 == 0) goto <L26>; else goto <L27>;
> 
> Is that suppose to be a valid assumption?  The dup is created by 
> copyrename, and
> I see no code there that's intended to stop dups from being created (on 
> the
> contrary, but surely it's unusual for the live ranges to overlap).
> 
Are maxmin_Result the same variable?  Use -uid to find out.  If they
both have the same UID, they're the same and that's a bug.  There should
only be a single PHI node per variable in a basic block.


Diego.

Re: [tree-ssa vs lno] who is right?

[Dale Johannesen]

On Mar 25, 2004, at 5:32 PM, Diego Novillo wrote:

> On Thu, 2004-03-25 at 20:29, Dale Johannesen wrote:
>
>> ;; basic block 19, loop depth 0, count 0
>> ;; prev block 9, next block 20
>> ;; pred:       10 [100.0%]  (fallthru)
>> ;; succ:       28 [50.0%]  (true,exec) 29 [50.0%]  (false,exec)
>> # maxmin_Result_140 = PHI <1(10)>;
>> # maxmin_Result_142 = PHI <2(10)>;
>> # lsm_tmp.19_144 = PHI <lsm_tmp.19_84(10)>;
>> <L28>:;
>> if (m__10 == 0) goto <L26>; else goto <L27>;
>>
>> Is that suppose to be a valid assumption?  The dup is created by
>> copyrename, and
>> I see no code there that's intended to stop dups from being created 
>> (on
>> the
>> contrary, but surely it's unusual for the live ranges to overlap).

Thanks.

> Are maxmin_Result the same variable?  Use -uid to find out.

How?  Doesn't like that as a command line option...

> If they both have the same UID, they're the same and that's a bug.  
> There should
> only be a single PHI node per variable in a basic block.

They are the same VAR_DECL (pointed to from different SSA_NAMEs).
Is it one of the UIDs in there that matters, or the one in the PHI?

Re: [tree-ssa vs lno] who is right?

[Diego Novillo]

On Thu, 2004-03-25 at 20:58, Dale Johannesen wrote:

> > Are maxmin_Result the same variable?  Use -uid to find out.
> 
> How?  Doesn't like that as a command line option...
> 
Sorry.  I meant -fdump-tree-...  I usually just say,
-fdump-tree-all-vops-uid (to get both virtual operands and UIDs dumped).


> They are the same VAR_DECL (pointed to from different SSA_NAMEs).
> Is it one of the UIDs in there that matters, or the one in the PHI?
> 
If the UIDs are different, then they are different VAR_DECLs, but if
you've already tested that they are the same VAR_DECL pointer, then I
guess we have a bug.  Mind opening a PR?


Diego.

Re: [tree-ssa vs lno] who is right?

[Andrew Pinski]

On Mar 25, 2004, at 17:58, Dale Johannesen wrote:

>> Are maxmin_Result the same variable?  Use -uid to find out.
>
> How?  Doesn't like that as a command line option...

-fdump-tree-uid

Thanks,
Andrew Pinski

Re: [tree-ssa vs lno] who is right?

[Andrew MacLeod]

On Thu, 2004-03-25 at 20:32, Diego Novillo wrote:
> On Thu, 2004-03-25 at 20:29, Dale Johannesen wrote:
> 
> > ;; basic block 19, loop depth 0, count 0
> > ;; prev block 9, next block 20
> > ;; pred:       10 [100.0%]  (fallthru)
> > ;; succ:       28 [50.0%]  (true,exec) 29 [50.0%]  (false,exec)
> > # maxmin_Result_140 = PHI <1(10)>;
> > # maxmin_Result_142 = PHI <2(10)>;
> > # lsm_tmp.19_144 = PHI <lsm_tmp.19_84(10)>;
> > <L28>:;
> > if (m__10 == 0) goto <L26>; else goto <L27>;
> > 
> > Is that suppose to be a valid assumption?  The dup is created by 
> > copyrename, and
> > I see no code there that's intended to stop dups from being created (on 
> > the
> > contrary, but surely it's unusual for the live ranges to overlap).
> > 
> Are maxmin_Result the same variable?  Use -uid to find out.  If they
> both have the same UID, they're the same and that's a bug.  There should
> only be a single PHI node per variable in a basic block.

I dont see why we have to have that restriction... 

maxmin_Result_140 and maxmin_Result_142 should be treated as two
completely different variables. Why should we say its a bug to allow
that to happen? 

If the live range of SSA_NAMEs can overlap, why can't they overlap here?
What are the arguments for dissallowing it?

Andrew

Re: [tree-ssa vs lno] who is right?

[Diego Novillo]

On Fri, 2004-03-26 at 07:42, Andrew MacLeod wrote:

> If the live range of SSA_NAMEs can overlap, why can't they overlap here?
> What are the arguments for dissallowing it?
> 
You're absolutely right.  I don't know what I was thinking.

Sorry Dale.  Disregard what I said.  I wasn't paying attention.  Is this
leading you to a codegen bug or a compiler abort?


Diego.

Re: [tree-ssa vs lno] who is right?

[Andrew MacLeod]

On Fri, 2004-03-26 at 07:52, Diego Novillo wrote:
> On Fri, 2004-03-26 at 07:42, Andrew MacLeod wrote:
> 
> > If the live range of SSA_NAMEs can overlap, why can't they overlap here?
> > What are the arguments for dissallowing it?
> > 
> You're absolutely right.  I don't know what I was thinking.
> 
> Sorry Dale.  Disregard what I said.  I wasn't paying attention.  Is this
> leading you to a codegen bug or a compiler abort?
> 
That said, this case turns out to be not productive, so send me an
example and I'll see if its something preventable, or just a casualty of
optimization (which I suspect is the case).

I have some minor changes to copyrename in the queue, but I doubt it
will affect this. Since there is a constant in the arguments of the PHI,
it must have been renamed due to a copy between a temp and maxmin_Result
elsewhere in the program. The hope was that we'd be able to get rid of
the copy.  Looks like not, unless one or more of the PHIs can be
optimized away. :-)

Andrew

Re: [tree-ssa vs lno] who is right?

[law]

In message <1080264779.4600.25.camel@localhost.localdomain>, Diego Novillo writ
es:
 >On Thu, 2004-03-25 at 20:29, Dale Johannesen wrote:
 >
 >> ;; basic block 19, loop depth 0, count 0
 >> ;; prev block 9, next block 20
 >> ;; pred:       10 [100.0%]  (fallthru)
 >> ;; succ:       28 [50.0%]  (true,exec) 29 [50.0%]  (false,exec)
 >> # maxmin_Result_140 = PHI <1(10)>;
 >> # maxmin_Result_142 = PHI <2(10)>;
 >> # lsm_tmp.19_144 = PHI <lsm_tmp.19_84(10)>;
 >> <L28>:;
 >> if (m__10 == 0) goto <L26>; else goto <L27>;
 >> 
 >> Is that suppose to be a valid assumption?  The dup is created by 
 >> copyrename, and
 >> I see no code there that's intended to stop dups from being created (on 
 >> the
 >> contrary, but surely it's unusual for the live ranges to overlap).
 >> 
 >Are maxmin_Result the same variable?  Use -uid to find out.  If they
 >both have the same UID, they're the same and that's a bug.  There should
 >only be a single PHI node per variable in a basic block.
Why would that be a bug?  It just means that we have overlapping lifetimes
for the two objects. 

It's certainly a little odd, but I wouldn't go straight to classifying it
as a bug.  Instead I would suggest looking into the first place where these
two PHIs appeared and figure out why it happened.  It could be a bug or
it could be normal behavior.
jeff

Re: [tree-ssa vs lno] who is right?

[Diego Novillo]

On Fri, 2004-03-26 at 10:28, law@redhat.com wrote:

> Why would that be a bug?  It just means that we have overlapping lifetimes
> for the two objects. 
> 
Yeah, I was smoking FUD chains again.


Diego.

Re: [tree-ssa vs lno] who is right?

[law]

In message <1080308082.12528.27.camel@p4>, Andrew MacLeod writes:
 >I have some minor changes to copyrename in the queue, but I doubt it
 >will affect this. Since there is a constant in the arguments of the PHI,
 >it must have been renamed due to a copy between a temp and maxmin_Result
 >elsewhere in the program. The hope was that we'd be able to get rid of
 >the copy.  Looks like not, unless one or more of the PHIs can be
 >optimized away. :-)
I'd expect DOM to propagate the constants so that there were no uses
of maxmin_Result_140, maxmin_Result_142, then I'd expect DCE to zap the
useless PHIs.

Alternatively Zdenek's block trivial PHI removal code may zap them.

But again, I think step #1 is to figure out how we got them in the first
place.
jeff

Re: [tree-ssa vs lno] who is right?

[Andrew MacLeod]

On Fri, 2004-03-26 at 10:30, law@redhat.com wrote:
> In message <1080308082.12528.27.camel@p4>, Andrew MacLeod writes:
>  >I have some minor changes to copyrename in the queue, but I doubt it
>  >will affect this. Since there is a constant in the arguments of the PHI,
>  >it must have been renamed due to a copy between a temp and maxmin_Result
>  >elsewhere in the program. The hope was that we'd be able to get rid of
>  >the copy.  Looks like not, unless one or more of the PHIs can be
>  >optimized away. :-)
> I'd expect DOM to propagate the constants so that there were no uses
> of maxmin_Result_140, maxmin_Result_142, then I'd expect DCE to zap the
> useless PHIs.
> 
> Alternatively Zdenek's block trivial PHI removal code may zap them.
> 
> But again, I think step #1 is to figure out how we got them in the first
> place.
> jeff
> 

It would be pretty easy, something like:

maxmin_Result_140 = PHI <1(10)>;
T.55_142 = PHI <2(10)>;
<...>
maxmin_Result_133 = T.55_142

could result in the 2 PHI nodes since we'd rename T.55_142 to
maxmin_Result_133 in hopes of getting rid of the copy.

It could also happen if T.55_142 is later used as a PHI argument to a
maxmin_Result PHI result.

Andrew

Re: [tree-ssa vs lno] who is right?

[law]

In message <1080315577.12834.102.camel@p4>, Andrew MacLeod writes:
 >On Fri, 2004-03-26 at 10:30, law@redhat.com wrote:
 >> In message <1080308082.12528.27.camel@p4>, Andrew MacLeod writes:
 >>  >I have some minor changes to copyrename in the queue, but I doubt it
 >>  >will affect this. Since there is a constant in the arguments of the PHI,
 >>  >it must have been renamed due to a copy between a temp and maxmin_Result
 >>  >elsewhere in the program. The hope was that we'd be able to get rid of
 >>  >the copy.  Looks like not, unless one or more of the PHIs can be
 >>  >optimized away. :-)
 >> I'd expect DOM to propagate the constants so that there were no uses
 >> of maxmin_Result_140, maxmin_Result_142, then I'd expect DCE to zap the
 >> useless PHIs.
 >> 
 >> Alternatively Zdenek's block trivial PHI removal code may zap them.
 >> 
 >> But again, I think step #1 is to figure out how we got them in the first
 >> place.
 >> jeff
 >> 
 >
 >It would be pretty easy, something like:
 >
 >maxmin_Result_140 = PHI <1(10)>;
 >T.55_142 = PHI <2(10)>;
 ><...>
 >maxmin_Result_133 = T.55_142
 >
 >could result in the 2 PHI nodes since we'd rename T.55_142 to
 >maxmin_Result_133 in hopes of getting rid of the copy.
 >
 >It could also happen if T.55_142 is later used as a PHI argument to a
 >maxmin_Result PHI result.
Ah yes.  Seems quite reasonable.  






jeff

Re: [tree-ssa vs lno] who is right?

[Dale Johannesen]

On Mar 26, 2004, at 8:06 AM, law@redhat.com wrote:
> In message <1080315577.12834.102.camel@p4>, Andrew MacLeod writes:
>> On Fri, 2004-03-26 at 10:30, law@redhat.com wrote:
>>> In message <1080308082.12528.27.camel@p4>, Andrew MacLeod writes:
>>> But again, I think step #1 is to figure out how we got them in the 
>>> first
>>> place.
>>> jeff
>>>
>>
>> It would be pretty easy, something like:
>>
>> maxmin_Result_140 = PHI <1(10)>;
>> T.55_142 = PHI <2(10)>;
>> <...>
>> maxmin_Result_133 = T.55_142
>>
>> could result in the 2 PHI nodes since we'd rename T.55_142 to
>> maxmin_Result_133 in hopes of getting rid of the copy.
>>
>> It could also happen if T.55_142 is later used as a PHI argument to a
>> maxmin_Result PHI result.
> Ah yes.  Seems quite reasonable.

Well, at least this wasn't a trivial question...thanks to all of you.

So the consensus is that copyrename's behavior is valid and reasonable,
and the only thing wrong here is the LNO branch's algorithm that assumes
otherwise.  Right?   I'll go fix that.   (The testcase is from sixtrack 
in SPEC;
it's small, though, I may be able to come up with something not 
copyrighted.)

Re: [tree-ssa vs lno] who is right?

[Zdenek Dvorak]

Hello,

> When the LNO branch copies a loop, it attempts to fix up the phi nodes 
> with
> an algorithm that assumes there is only one phi per block per variable. 
>  That is, it
> won't see code like this:

where do we assume this (i.e. what do you mean by "copying a loop")?
While this certainly is unlikely to happen, there probably is nothing
that would prevent it.

Zdenek

> ;; basic block 19, loop depth 0, count 0
> ;; prev block 9, next block 20
> ;; pred:       10 [100.0%]  (fallthru)
> ;; succ:       28 [50.0%]  (true,exec) 29 [50.0%]  (false,exec)
> # maxmin_Result_140 = PHI <1(10)>;
> # maxmin_Result_142 = PHI <2(10)>;
> # lsm_tmp.19_144 = PHI <lsm_tmp.19_84(10)>;
> <L28>:;
> if (m__10 == 0) goto <L26>; else goto <L27>;
> 
> Is that suppose to be a valid assumption?  The dup is created by 
> copyrename, and
> I see no code there that's intended to stop dups from being created (on 
> the
> contrary, but surely it's unusual for the live ranges to overlap).
> 

Re: [tree-ssa vs lno] who is right?

[Dale Johannesen]

On Mar 26, 2004, at 10:10 AM, Zdenek Dvorak wrote:

> Hello,
>
>> When the LNO branch copies a loop, it attempts to fix up the phi nodes
>> with
>> an algorithm that assumes there is only one phi per block per 
>> variable.
>>  That is, it
>> won't see code like this:
>
>  (i.e. what do you mean by "copying a loop")?

tree_duplicate_loop_to_header_edge (called from unswitching in the 
failing case)

> where do we assume this

lv_adjust_loop_header_phi . The assumption is explicit:

                       /* There can not be second phi node for the same 
variable.
                          Get out of the for loop that walks phi nodes 
of 'first'.
                       */
There isn't any way to find the right phi at that point AFAICT, so I'm 
thinking
along the lines of making sure the phi lists are in the same order when 
doing
the loop duplication earlier (they aren't now).

> While this certainly is unlikely to happen, there probably is nothing
> that would prevent it.

> Zdenek
>
>> ;; basic block 19, loop depth 0, count 0
>> ;; prev block 9, next block 20
>> ;; pred:       10 [100.0%]  (fallthru)
>> ;; succ:       28 [50.0%]  (true,exec) 29 [50.0%]  (false,exec)
>> # maxmin_Result_140 = PHI <1(10)>;
>> # maxmin_Result_142 = PHI <2(10)>;
>> # lsm_tmp.19_144 = PHI <lsm_tmp.19_84(10)>;
>> <L28>:;
>> if (m__10 == 0) goto <L26>; else goto <L27>;
>>
>> Is that suppose to be a valid assumption?  The dup is created by
>> copyrename, and
>> I see no code there that's intended to stop dups from being created 
>> (on
>> the
>> contrary, but surely it's unusual for the live ranges to overlap).
>>

Re: [tree-ssa vs lno] who is right?

[Devang Patel]

On Mar 26, 2004, at 10:22 AM, Dale Johannesen wrote:

>
> On Mar 26, 2004, at 10:10 AM, Zdenek Dvorak wrote:
>
>> Hello,
>>
>>> When the LNO branch copies a loop, it attempts to fix up the phi 
>>> nodes
>>> with
>>> an algorithm that assumes there is only one phi per block per 
>>> variable.
>>>  That is, it
>>> won't see code like this:
>>
>>  (i.e. what do you mean by "copying a loop")?
>
> tree_duplicate_loop_to_header_edge (called from unswitching in the 
> failing case)

I saw this happening couple of days ago at this point in
tree_duplicate_loop...

       /* Add phi nodes for definitions to exit_block (we could find out
          which of them are really used outside of the loop and don't 
emit the
          phi nodes for the remaining ones; for this we would however 
need
          to know immediate uses).  */
       for (arg = usable_outside; arg; arg = TREE_CHAIN (arg))
         {
           def = TREE_VALUE (arg);
           phi = create_phi_node (def, exit_block);
           for (ae = exit_block->pred; ae; ae = ae->pred_next)
             add_phi_arg (&phi, def, ae);
         }

>> where do we assume this
>
> lv_adjust_loop_header_phi . The assumption is explicit:
>
>                       /* There can not be second phi node for the same 
> variable.
>                          Get out of the for loop that walks phi nodes 
> of 'first'.
>                       */

Yes, that's what my understanding was (until this thread). I'm glad I
note down my assumptions.

> There isn't any way to find the right phi at that point AFAICT,

That's what I found at that time... here is what I am trying to do
in lv_adjust_loop_header_phi

/* Adjust phi nodes for 'first' basic block.  'second' basic block is a 
copy
    of 'first'. Both of them are dominated by 'new_head' basic block. 
When
    'new_head' was created by [splitting] 'second's incoming edge it 
received phi arguments
    on the edge by split_edge(). Later, additional edge 'e' was created 
to
    connect 'new_head' and 'first'. Now this routnine adds phi args on 
this
    additional edge 'e' that new_head to second edge received as part of 
edge
    splitting.
*/

-
Devang

> so I'm thinking
> along the lines of making sure the phi lists are in the same order 
> when doing
> the loop duplication earlier (they aren't now).
>
>> While this certainly is unlikely to happen, there probably is nothing
>> that would prevent it.
>
>> Zdenek
>>
>>> ;; basic block 19, loop depth 0, count 0
>>> ;; prev block 9, next block 20
>>> ;; pred:       10 [100.0%]  (fallthru)
>>> ;; succ:       28 [50.0%]  (true,exec) 29 [50.0%]  (false,exec)
>>> # maxmin_Result_140 = PHI <1(10)>;
>>> # maxmin_Result_142 = PHI <2(10)>;
>>> # lsm_tmp.19_144 = PHI <lsm_tmp.19_84(10)>;
>>> <L28>:;
>>> if (m__10 == 0) goto <L26>; else goto <L27>;
>>>
>>> Is that suppose to be a valid assumption?  The dup is created by
>>> copyrename, and
>>> I see no code there that's intended to stop dups from being created 
>>> (on
>>> the
>>> contrary, but surely it's unusual for the live ranges to overlap).
>>>