[SCEV] Move SCEVLostPoisonFlags() check into SCEVExpander

[nikic]

Summary

Always insert values into ExprValueMap, and instead skip using them in SCEVExpander if poison-generating flags have been lost. This ensures that all values that are in ValueExprMap are also in ExprValueMap, so we can use the latter to invalidate the former.

This change is probably not entirely NFC for the case where originally the SCEV had no nowrap flags but they were inferred later, in which case that would now allow reusing the existing value for expansion.

[nikic]

Rebase

[reames]

So, LGTM to the code motion, but I think this code is badly incomplete.

If I understand it correctly, the intent is to prevent SCEVExpander from reusing an IR instruction with flags stronger than those implied by the SCEV. This is a laudable goal, but the code completely ignores folding of the binop during SCEV construction.

I see two correct approaches:

1. Default to returning true (meaning can't reuse) unless we can prove flag match. This is somewhat the inverse of the current code.
2. drop poison generating flags from the IR instruction

We could, of course, use some combination of both.

Any chance you'd be willing to follow up here? If not, I probably will.

[nikic]

In D112389#3084958, @reames wrote:

So, LGTM to the code motion, but I think this code is badly incomplete.

If I understand it correctly, the intent is to prevent SCEVExpander from reusing an IR instruction with flags stronger than those implied by the SCEV. This is a laudable goal, but the code completely ignores folding of the binop during SCEV construction.

Right. I agree that the handling is incomplete, though it might be tricky to come up with cases where it fails in practice.

I see two correct approaches:

1. Default to returning true (meaning can't reuse) unless we can prove flag match. This is somewhat the inverse of the current code.
2. drop poison generating flags from the IR instruction

We could, of course, use some combination of both.

Any chance you'd be willing to follow up here? If not, I probably will.

I don't plan to look into this one myself -- I only ran into this while looking at invalidation.

llvm/lib/Analysis/ScalarEvolution.cpp

if (I != ValueExprMap.end()) {
     if (Offset != nullptr) {
       if (auto *SV = getSCEVValues(Stripped))
         SV->remove({V, Offset});
     }
     ValueExprMap.erase(V);
   }
 }
 
-/// Check whether value has nuw/nsw/exact set but SCEV does not.
-/// TODO: In reality it is better to check the poison recursively
-/// but this is better than nothing.
-static bool SCEVLostPoisonFlags(const SCEV *S, const Value *V) {
-  if (auto *I = dyn_cast<Instruction>(V)) {
-    if (isa<OverflowingBinaryOperator>(I)) {
-      if (auto *NS = dyn_cast<SCEVNAryExpr>(S)) {
-        if (I->hasNoSignedWrap() && !NS->hasNoSignedWrap())
-          return true;
-        if (I->hasNoUnsignedWrap() && !NS->hasNoUnsignedWrap())
-          return true;
-      }
-    } else if (isa<PossiblyExactOperator>(I) && I->isExact())
-      return true;
-  }
-  return false;
-}
-
 /// Return an existing SCEV if it exists, otherwise analyze the expression and
 /// create a new one.
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   const SCEV *S = getExistingSCEV(V);
   if (S == nullptr) {
     S = createSCEV(V);
     // During PHI resolution, it is possible to create two SCEVs for the same
     // V, so it is needed to double check whether V->S is inserted into
     // ValueExprMap before insert S->{V, 0} into ExprValueMap.
     std::pair<ValueExprMapType::iterator, bool> Pair =
         ValueExprMap.insert({SCEVCallbackVH(V, this), S});
-    if (Pair.second && !SCEVLostPoisonFlags(S, V)) {
+    if (Pair.second) {
       ExprValueMap[S].insert({V, nullptr});
 
       // If S == Stripped + Offset, add Stripped -> {V, Offset} into
       // ExprValueMap.
       const SCEV *Stripped = S;
       ConstantInt *Offset = nullptr;
       std::tie(Stripped, Offset) = splitAddExpr(S);
       // If stripped is SCEVUnknown, don't bother to save

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
   if (Ty) {
     assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
            "non-trivial casts should be done with the SCEVs directly!");
     V = InsertNoopCastOfTo(V, Ty);
   }
   return V;
 }
 
+/// Check whether value has nuw/nsw/exact set but SCEV does not.
+/// TODO: In reality it is better to check the poison recursively
+/// but this is better than nothing.
+static bool SCEVLostPoisonFlags(const SCEV *S, const Instruction *I) {
+  if (isa<OverflowingBinaryOperator>(I)) {
+    if (auto *NS = dyn_cast<SCEVNAryExpr>(S)) {
+      if (I->hasNoSignedWrap() && !NS->hasNoSignedWrap())
+        return true;
+      if (I->hasNoUnsignedWrap() && !NS->hasNoUnsignedWrap())
+        return true;
+    }
+  } else if (isa<PossiblyExactOperator>(I) && I->isExact())
+    return true;
+  return false;
+}
+
 ScalarEvolution::ValueOffsetPair
 SCEVExpander::FindValueInExprValueMap(const SCEV *S,
                                       const Instruction *InsertPt) {
   auto *Set = SE.getSCEVValues(S);
   // If the expansion is not in CanonicalMode, and the SCEV contains any
   // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
   if (CanonicalMode || !SE.containsAddRecurrence(S)) {
     // If S is scConstant, it may be worse to reuse an existing Value.
     if (S->getSCEVType() != scConstant && Set) {
       // Choose a Value from the set which dominates the InsertPt.
       // InsertPt should be inside the Value's parent loop so as not to break
       // the LCSSA form.
       for (auto const &VOPair : *Set) {
         Value *V = VOPair.first;
         ConstantInt *Offset = VOPair.second;
         Instruction *EntInst = dyn_cast_or_null<Instruction>(V);
         if (!EntInst)
           continue;
 
         assert(EntInst->getFunction() == InsertPt->getFunction());
         if (S->getType() == V->getType() &&
             SE.DT.dominates(EntInst, InsertPt) &&
             (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
-             SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
+             SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)) &&
+            !SCEVLostPoisonFlags(S, EntInst))
           return {V, Offset};
       }
     }
   }
   return {nullptr, nullptr};
 }
 
 // The expansion of SCEV will either reuse a previous Value in ExprValueMap,