CSE, loops, and array accesses

[Andrew Dinn]

On 01/10/15 14:00, Edward Nevill wrote:
> On Thu, 2015-10-01 at 11:27 +0100, Andrew Haley wrote:
>> I'm looking at a failure to CSE the array base offset in this loop:
>> . . .
> 
> The reason it does not do the loop invariant lifting is because of the following transformation in AddPNode::Ideal in addnode.cpp
> 
>         // Else move the constant to the right.  ((A+con)+B) into ((A+B)+con)
>         address = phase->transform(new (phase->C) AddPNode(in(Base),addp->in(Address),in(Offset)));
>         offset  = addp->in(Offset);
> 
> So, once it has transformed ((A+con)+B) into ((A+B)+con) all bets are off, we can never CSE/Loop invariant lift.
> 
> Try the following patch, it should generate the code you want.

That may indeed fix this case but at what cost to other optimizations?
The implementations of Ideal across all graph nodes are supposed to
reduce to a normal form in an order-independent manner -- normally
described as 'reduction is confluent'. I wonder if this change will
break the confluence property because other transformations expect
(eventually) to see constants pushed up and to the right.

If that is the case then I think the real problem here is that the loop
invariant test knows that (A+con) is invariant when A is invariant but
does not know that ((A+B)+con) also contains a loop invariant when
either A or B is invariant. Maybe that is where the fix should be applied?

regards,


Andrew Dinn
-----------
Senior Principal Software Engineer
Red Hat UK Ltd
Registered in UK and Wales under Company Registration No. 3798903
Directors: Michael Cunningham (USA), Matt Parson (USA), Charlie Peters
(USA), Michael O'Neill (Ireland)