[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(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,

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

There’s actually some related discussion happening on this right now. 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