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

[Sanjoy Das via llvm-dev]

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