[llvm-dev] [SCEV] Inconsistent SCEV formation for zext

[Chawla, Pankaj via llvm-dev]

Hi Sanjoy,

Thanks for the reply!
Would it be possible for you to implement this?
 
You know the codebase better than I do.

Thanks,
Pankaj

-----Original Message-----
From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] 
Sent: Tuesday, March 13, 2018 1:34 PM
To: Chawla, Pankaj <pankaj.chawla at intel.com>
Cc: Maxim Kazantsev <max.kazantsev at azul.com>; Serguei Katkov <serguei.katkov at azul.com>; llvm-dev at lists.llvm.org
Subject: Re: [SCEV] Inconsistent SCEV formation for zext

This sounds fine to me (and sorry for the delay!).

-- Sanjoy

On Mon, Mar 12, 2018 at 1:09 PM, Chawla, Pankaj <pankaj.chawla at intel.com> wrote:
> Hi Sanjoy,
>
> So what is the verdict on this issue?
>
> Thanks,
> Pankaj
>
>
> -----Original Message-----
> From: Chawla, Pankaj
> Sent: Monday, February 26, 2018 11:12 AM
> To: Sanjoy Das <sanjoy at playingwithpointers.com>
> Cc: Maxim Kazantsev <max.kazantsev at azul.com>; Serguei Katkov <serguei.katkov at azul.com>; llvm-dev at lists.llvm.org
> Subject: RE: [SCEV] Inconsistent SCEV formation for zext
>
> Hi Sanjoy,
>
>>> I'm a bit apprehensive of adding more caching to solve problems created by caching; but if there is no way out of adding another cache, how about adding a cache that maps SCEV expressions to their simplified versions?  Then we could do something like:
>
> I may be wrong but I think caching is not an issue in itself, but caching in the presence of self-recursion is.
>
>
>>>  getZeroExtendExpr(S) {
>>>    if (AlreadyPresent = UniqueSCEVs.find(kZeroExtend, S) {
>>>      if (Simplified = SimplifiedSCEVs.find(AlreadyPresent)) {
>>>        return Simplified;
>>>      }
>>>      return AlreadyPresent;
>>>    }
>
>>>    ...
>>>    // We discovered zext(s) can be simplified to t
>>>    UniqueSCEVs.insert({kZeroExtend, S}, t);
>>>    SimplifiedSCEVs[s] = t;
>>>    return t;
>>>  }
>
> I am not sure I understand how exactly SimplifiedSCEV is maintained and how UniqueSCEVs is going to be extended. I think the self-recursion issue is not related to just simplification of casts. It may be applicable in other scenarios (like deduction of wrap flags). As an example, I think ScalarEvolution has this commonly occurring cycle-
>  getBackedgeTakenInfo(Loop) -> getSCEV(LoopIV) -> getBackedgeTakenInfo(Loop)
>
> This is handled correctly because we have some logic to forget loop header phi entries. Under the new setup, we would not have to 'special case' this logic. It will be handled by the same 'IsTopCall' approach.
>
>>
>> ScalarEvolution::getSCEVImpl (Value *V, bool  IsTopCall = false) {
>>   // Look up in cache using logic described above
>>   If (S = getExistingSCEV())
>>     return S;
>>
>>   if (IsTopCall) {
>>    PessimisticMode = false;
>>    PendingCache.clear();
>>    PendingCache.insert(V, getUnknown(V));
>
>>> Can this be assert(!PessimisticMode && !PendingCache.empty()) since on a "top call" we could not have hit self recursion yet?
>
>
> Yes, if we reset them before exiting 'IsTopCall'. I wasn't doing that :)
>
>
>>   }
>>
>>   SCEV *S =  createSCEV();
>>
>>   If(IsTopCall) {
>>     FinalCache.insert(V, S);
>>     forgetMemoizedResults(PendingCache);
>
>>> I'm not 100% sure, but I suspect this will not work.
>>> forgetMemoizedResults will only remove the Value->SCEV mapping for the conservative cases, but in the test case you attached
>>> getZeroExtendExpr(S) tries to create a *new* SCEV for %conv5 (since I suspect the %conv5->mapping was removed by getBackedgeTakenInfo) but early-exits because zext(%dec) is present in UniqueSCEVs.
>
> In the setup I am proposing all the entries including the one for (%dec -> SCEV) will be 'forgotten' before we exit getBackedgeTakenInfo(Loop) because the pessimistic mode would be triggered due to self-recursion on %conv5. The only valid entry is for the topmost call 'getBackedgeTakenInfo(Loop)'.
>
> Thanks,
> Pankaj
>