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

[Sanjoy Das via llvm-dev]

Hi Pankaj,

On Sun, Feb 11, 2018 at 2:32 PM, Chawla, Pankaj <pankaj.chawla at intel.com> wrote:
> Thanks for investigating the issue!
>
> I am more interested in getting the underlying problem fixed rather than making this particular test case work. I think I have more test cases where this problem crops up. I would any day prefer consistent results over compile time savings which can lead to inconsistencies. These inconsistencies require significant developer time to analyze and fix which just doesn't seem worth it.
>
> Based on my limited familiarity with ScalarEvolution code I would like to propose a solution that may work-
>
> Have two levels of caching for data structures for which infinite recursion is possible (like Value -> SCEV, Value->Predicate, Loop->BackedgeTakenCount etc).

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:

  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;
  }

> The first level of caching is the 'PendingCache' and the second one is the 'FinalCache'. PendingCache is similar to PendingLoopPredicates. It is used to break infinite recursion. In addition we keep a Boolean class member 'PessimisticMode' (common to all caches).
>
> The lookup logic for the cache is something like this-
>
> If (PendingCache.find(Key)) {
>   PessimisticMode = true;
>   return Value;
> } else if (FinalCache.find(Key)) {
>   return Value;
> }
>
> Insertion logic is like this-
>
> If (PessimisticMode) {
>   PendingCache.insert(Entry);
> } else {
>   FinalCache.insert(Entry);
> }
>
> We need to distinguish top level calls to the external interface like getSCEV()/getBackedgeTakenCount() etc from the internal recursive calls for setting/resetting the state correctly. We start with adding the most conservative result for the value in PendingCache. This would be getUnknown() for getSCEV().
>
> So getSCEV() may be implemented something like this-
>
> ScalarEvolution::getSCEV(Value *V) {
>   return getSCEVImpl(V, true);
> }
>
> 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?

>   }
>
>   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.

-- Sanjoy