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

[Alexandre Isoard via llvm-dev]

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>