llvm dev - Sep 2021 - [SCEV] UniqueSCEVs doesn't account for NoWrapFlags

Hello,

We recently came into an issue in indvars that made it generate relatively
poor IR (we are still working on making a minimal example) but we tracked
it down to a ScalarEvolution limitation.
Namely, when we uniquify SCEVs we do not account for NSW/NUW flags.

A typical example, let's say, when producing the SCEV for a zext, we will
first check if we already produced one of the same kind:

const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty,
unsigned Depth) {
...
  // Before doing any expensive analysis, check to see if we've already
  // computed a SCEV for this Op and Ty.
  ID.AddInteger(scZeroExtend);
  ID.AddPointer(Op);
  ID.AddPointer(Ty);

  void *IP = nullptr;
  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
...
}

So as to always produce the exact same pointer, and also speed-up the
computation. That is, we do not try to simplify that SCEV as the only way
it is in the table, is if an earlier attempt didn't succeed in simplifying
it. But in the case of zext, there are simplification patterns that depends
on the presence (or absence) of NSW/NUW in the SCEV of the operand, so this
has some consequences.

A typical scenario is:
1) we compute the a zext on an expression that doesn't have any NUW/NSW
flag, it can't be simplified, and we produce the SCEVZeroExtendExpr(Op);
2) we compute the zext on an expression that does have NUW/NSW flags, we
get the same SCEV pointer on that Op (as we don't account for NUW/NSW flags
in uniquification), and the quick check return that we already have a
SCEVZeroExtendExpr(Op) available, and we don't even try to simplify it

On the other hand, if we build the SCEV of the 2) case first, we will
simplify the expression, and build a simpler SCEV... until we build the one
for case 1).

A small modification of the above code, as follow:

const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty,
unsigned Depth) {
...
  // Before doing any expensive analysis, check to see if we've already
  // computed a SCEV for this Op and Ty.
  ID.AddInteger(scZeroExtend);
  ID.AddPointer(Op);
  ID.AddPointer(Ty);

*  if (const SCEVNAryExpr *NAE = dyn_cast<SCEVNAryExpr>(Op))
ID.AddInteger(NAE->getNoWrapFlags());*
  void *IP = nullptr;
  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
...
}

Make this specific issue disappear. But I have a few questions:
A) Is this safe? Does this break some implicit assumption about SCEV
uniquification?
B) Are we okay with that issue? Is that a known compile time / analysis
quality trade-off?

Note that this was an issue seen in 7.0, we are going to try to reproduce
it in an up-to-date version. It's quite tricky to "show" the
problem
because it depends heavily on the order in which ScalarEvolution is queried.

Thanks in advance.

-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210908/ee2bd59a/attachment-0001.html>

Alexandre,

You've stumbled into one of the dark ugly corners of SCEV. Welcome!

There's actually some related discussion happening on this right now.  
https://reviews.llvm.org/D106852 is a good starting place. Depending on 
your interest level, you might find my writeup (linked from comments on 
the review) helpful.

The short summary here is that SCEV's handling of flags is 
demonstrateably broken.  There's no firm agreement on what the semantics 
should be, and all of the options have serious downsides.  At the 
moment, the focus is on avoiding miscompiles, but finding a way to 
expose additional optimization potential in the process is definitely in 
scope as well.

Philip

On 9/8/21 7:00 PM, Alexandre Isoard via llvm-dev wrote:
> Hello,
>
> We recently came into an issue in indvars that made it generate 
> relatively poor IR (we are still working on making a minimal example) 
> but we tracked it down to a ScalarEvolution limitation.
> Namely, when we uniquify SCEVs we do not account for NSW/NUW flags.
>
> A typical example, let's say, when producing the SCEV for a zext, we 
> will first check if we already produced one of the same kind:
>
> const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type 
> *Ty, unsigned Depth) {
> ...
>   // Before doing any expensive analysis, check to see if we've already
>   // computed a SCEV for this Op and Ty.
>   ID.AddInteger(scZeroExtend);
>   ID.AddPointer(Op);
>   ID.AddPointer(Ty);
>
>   void *IP = nullptr;
>   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
> ...
> }
>
> So as to always produce the exact same pointer, and also speed-up the 
> computation. That is, we do not try to simplify that SCEV as the only 
> way it is in the table, is if an earlier attempt didn't succeed in 
> simplifying it. But in the case of zext, there are simplification 
> patterns that depends on the presence (or absence) of NSW/NUW in the 
> SCEV of the operand, so this has some consequences.
>
> A typical scenario is:
> 1) we compute the a zext on an expression that doesn't have any 
> NUW/NSW flag, it can't be simplified, and we produce the 
> SCEVZeroExtendExpr(Op);
> 2) we compute the zext on an expression that does have NUW/NSW flags, 
> we get the same SCEV pointer on that Op (as we don't account for 
> NUW/NSW flags in uniquification), and the quick check return that we 
> already have a SCEVZeroExtendExpr(Op) available, and we don't even try 
> to simplify it
>
> On the other hand, if we build the SCEV of the 2) case first, we will 
> simplify the expression, and build a simpler SCEV... until we build 
> the one for case 1).
>
> A small modification of the above code, as follow:
>
> const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type 
> *Ty, unsigned Depth) {
> ...
>   // Before doing any expensive analysis, check to see if we've already
>   // computed a SCEV for this Op and Ty.
>   ID.AddInteger(scZeroExtend);
>   ID.AddPointer(Op);
>   ID.AddPointer(Ty);
> *  if (const SCEVNAryExpr *NAE = dyn_cast<SCEVNAryExpr>(Op))
>     ID.AddInteger(NAE->getNoWrapFlags());*
>   void *IP = nullptr;
>   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
> ...
> }
>
> Make this specific issue disappear. But I have a few questions:
> A) Is this safe? Does this break some implicit assumption about SCEV 
> uniquification?
> B) Are we okay with that issue? Is that a known compile time / 
> analysis quality trade-off?
>
> Note that this was an issue seen in 7.0, we are going to try to 
> reproduce it in an up-to-date version. It's quite tricky to
"show" the
> problem because it depends heavily on the order in which 
> ScalarEvolution is queried.
>
> Thanks in advance.
>
> -- 
> *Alexandre Isoard*
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210909/f7a028de/attachment.html>