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

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


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180208/0fa8fc65/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: inconsistent-scev-zext.ll
Type: application/octet-stream
Size: 2421 bytes
Desc: inconsistent-scev-zext.ll
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180208/0fa8fc65/attachment.obj>

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

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