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

[Chawla, Pankaj via llvm-dev]

Hi Sanjoy,

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

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

  SCEV *S =  createSCEV();
 
  If(IsTopCall) {
    FinalCache.insert(V, S);
    forgetMemoizedResults(PendingCache);
  } else if (PessimisticMode) {
    PendingCache.insert(V, S);
  } else {
    FinalCache.insert(V, S);
  }

  return S;
}

Implementation in ScalarEvolution.cpp uses getSCEVImpl() instead of getSCEV().
 
The idea is that we can conclude accurate result for the topmost call and for values computed before we hit PessimisticMode (recursion on self). We actually do this in some parts of the codebase. For example, getBackedgeTakenInfo()  inserts a conservative entry in the map, then replaces it with the real result and cleans up (possibly inaccurate) results for all the loop header phis. We just need to apply the approach in a more generic manner.

We may have to handle AddRecs (which are inherently self-recursive) as a special case in this setup.

Of course, we may be discarding more than necessary in this setup so it may have compile time implications. A better solution is more that welcome.

Please let me know your thoughts.

Thanks,
Pankaj

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

Hi,

+CC Max, Serguei

This looks like a textbook case of why caching is hard.

We first call getZeroExtendExpr on %dec, and this call does end up returning an add rec.  However, in the process of simplifying the zext, it also calls into isLoopBackedgeGuardedByCond which in turn calls getZeroExtendExpr(%dec) again.  However, this second (recursive) time, we don't simplify the zext and cache a pessimistic value for it.
We don't get the more precise answer the second time because we bail out on proving the same predicate recursively to avoid infinite loops (see ScalarEvolution::PendingLoopPredicates).

I don't think there is a nice and easy fix here.  We can try to find some specific property of the IV we can exploit here to make this work, but the general problem will remain.

-- Sanjoy

On Thu, Feb 8, 2018 at 2:19 PM, Chawla, Pankaj <pankaj.chawla at intel.com> wrote:
> Hi Sanjoy,
>
>
>
> SCEV is behaving inconsistently when forming SCEV for this zext 
> instruction in the attached test case-
>
> %conv5 = zext i32 %dec to i64
>
>
>
> If we request a SCEV for the instruction, it returns-
>
> (zext i32 {{-1,+,1}<nw><%for.body>,+,-1}<nw><%for.body7> to i64)
>
>
>
> This can be seen by invoking-
>
> $ opt -analyze -scalar-evolution inconsistent-scev-zext.ll
>
>
>
> But when computing the backedge taken count of the containing loop 
> for.body7, it is able to push zext inside the AddRec and forms the 
> following for the same instruction-
>
> {(zext i32 {-1,+,1}<%for.body> to i64),+,-1}<nw><%for.body7>
>
>
>
> This allows ScalarEvolution to compute a valid backedge taken count 
> for the loop.
>
>
>
> The ‘simplification’ is done by this piece of code inside
> getZeroExtendExpr()-
>
>
>
>             // Cache knowledge of AR NW, which is propagated to this
>
>             // AddRec.  Negative step causes unsigned wrap, but it
>
>             // still can't self-wrap.
>
>             const_cast<SCEVAddRecExpr 
> *>(AR)->setNoWrapFlags(SCEV::FlagNW);
>
>             // Return the expression with the addrec on the outside.
>
>             return getAddRecExpr(
>
>                 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this,
>
>                                                          Depth + 1),
>
>                 getSignExtendExpr(Step, Ty, Depth + 1), L,
>
>                 AR->getNoWrapFlags());
>
>           }
>
>
>
> I believe it is wrong for ScalarEvolution to use a simplified SCEV for 
> internal analysis and return a non-simplified SCEV to the client.
>
>
>
> Thanks,
>
> Pankaj
>
>
>
>