[LLVMdev] Cast to SCEVAddRecExpr

[Nema, Ashutosh]

Hi Nick,

Consider below case:

for (j=1; j < itr; j++) {
     - - - - 
     for (i=1; i < itr; i++) {
     {
       temp=  var[1 << i];
        - - - - - 
     }
}

In the above example, we are unable to get "SCEVAddRecExpr" for "var[1 << i]" 

Its "SCEVAddRecExpr" is computable in *Outer Loop* 

I expected SCEV will hoist AddRec to top level, but it's not doing that.

Instead if I change "var[1 << i]" to "var[i * 2]" then I'm getting "SCEVAddRecExpr".

What is your opinion on this, to me this looks like a missed opportunity in SCEV.

Regards,
Ashutosh


-----Original Message-----
From: Nick Lewycky [mailto:nicholas at mxc.ca] 
Sent: Friday, March 20, 2015 9:51 AM
To: Nema, Ashutosh
Cc: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] Cast to SCEVAddRecExpr

Nema, Ashutosh wrote:
> Yes, I can get "SCEVAddRecExpr" from operands of "(sext i32 {2,+,2}<%for.body4>   to i64)".
>
> So whenever SCEV cast to "SCEVAddRecExpr" fails, we have drill down for such patterns ?

I don't know, what are you planning to do with it? Even if you do drill 
down and find the addrec inside, is that useful to you? SCEV will 
already try to hoist out the addrec to the top level. If it isn't there, 
then it probably can't be rewritten so that it could be. If it can be, 
that's a missed optimization opportunity and should be taught to SCEV.

What's your goal? Look at every addrec? If that's it, I would say that 
yes you need to drill down, but that you should only query SCEV about 
PHINode instructions.

>
> Is that the right way ?
>
> Regards,
> Ashutosh
>
> -----Original Message-----
> From: Nick Lewycky [mailto:nicholas at mxc.ca]
> Sent: Thursday, March 19, 2015 1:02 PM
> To: Nema, Ashutosh
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] Cast to SCEVAddRecExpr
>
> Nema, Ashutosh wrote:
>> Hi Nick,
>>
>> Thanks for looking into it.
>>
>> I have tried that as well but it didn't worked.
>>
>> "AddExpr->getOperand(0))" node is:
>> " (4 * (sext i32 {2,+,2}<%for.body4>   to i64))<nsw>"
>>
>> When I cast this to "SCEVAddRecExpr" it returns NULL.
>
> Oh. Yeah, that's because it's a multiply with a 4 on the left. On the
> right is an sext, and if you grab its operand, then *that* is a
> SCEVAddRecExpr.
>
>>
>> Regards,
>> Ashutosh
>>
>> -----Original Message-----
>> From: Nick Lewycky [mailto:nicholas at mxc.ca]
>> Sent: Thursday, March 19, 2015 12:19 PM
>> To: Nema, Ashutosh
>> Cc: llvmdev at cs.uiuc.edu
>> Subject: Re: [LLVMdev] Cast to SCEVAddRecExpr
>>
>> Nema, Ashutosh wrote:
>>> Hi,
>>> I'm trying to cast one of the SCEV node to "SCEVAddRecExpr".
>>> Every time cast return NULL, and I'm unable to do this.
>>> SCEV Node:
>>> ((4 * (sext i32 {2,+,2}<%for.body4>   to i64))<nsw>   + %var)<nsw>
>>> Casting:
>>> const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEVNode);
>>> 'var' is of type float pointer (float*).
>>> Without 'sext' it works, but I'm wondering why it not working in above case.
>>> I'm not sure, is such casting allowed ?
>>
>> It looks like your node is a SCEVAddExpr whose LHS is "(4 * (sext i32
>> {2,+,2}<%for.body4>   to i64))<nsw>" and RHS is "%var", instead of a
>> SCEVAddRecExpr. Perhaps if the sext weren't there SCEV might simplify
>> the whole thing to a single SCEVAddRecExpr.
>>
>> Can you cast your node to a SCEVAddExpr, then
>> dyn_cast<SCEVAddRecExpr>(AddExpr->getOperand(0))?
>>
>> Note that SCEV does not handle floats as anything but completely opaque
>> values.
>>
>> Nick
>>
>
>