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

[Chawla, Pankaj via llvm-dev]

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