[SCEV] Clear poison flags during expansion of SCEV

[skatkov]

Summary

This is an alternate solution to rL322058 which causes performance
degradation according to report from @eastig.

Generally when we expand a SCEV and re-use the instruction we
check whether SCEV has lost a poison flags but instruction has.
In this case we just clear poison flags from instruction.

This is pretty similar what GVN will do if we we literally expand the SCEV
without poison flags.

Potentially it might have negative performance impact due to we clear
nuw/nsw from instruction and possible loose some performance
opportunities.

[skatkov]

Added regression test. Taken from @eastig.

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

1692

s/recursevely/recursively/

1694

This is bothering me -- I agree that this mitigation is better than nothing, but what you've found shows that this FindValueInExprValueMap business is basically incorrect, except in perhaps very limited cases.

I'm tempted to rip all of this reuse logic out of SCEV/SCEVExpander. Back when this was added in https://reviews.llvm.org/D12090 we talked about improving our CSE as an alternative to caching expressions like this; I think this bug is a sign that we should, in fact, seriously consider what FindValueInExprValueMap does as a CSE optimization.

+CC @wmi @hfinkel for discussion.

[skatkov]

lib/Analysis/ScalarEvolutionExpander.cpp

1694

Just a side note. This functionality is used in backend as well (in loop reduce pass). If I understand correctly your proposal is to eliminate caching and just always literally expand the SCEV and CSE later will eliminate all redundant instructions. But in this case we will need to add a CSE pass after loop reduce as well.

Ok, I keep looking into your discussion.

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

1694

But in this case we will need to add a CSE pass after loop reduce as well.

Or we can instead do some basic CSE during SCEV expansion (we already do a bit of this).

In any case, correctness trumps everything. :)

[skatkov]

ping

[mkazantsev]

Hi @sanjoy @wmi @hfinkel, is there any discussion ongoing about this patch? There is more than month without progress, should we maybe start a discussion here?

I'm personaly also inclined to think that this caching logic is wrong and we should get rid of it, but will clearly have consequences from compile time point, so it's definitely worth discussing.

lib/Analysis/ScalarEvolution.cpp

if (I != ValueExprMap.end()) {
     if (Offset != nullptr) {
       if (SetVector<ValueOffsetPair> *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 recursevely
-/// 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

lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
   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 recursevely
+/// 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;
+}
+
 ScalarEvolution::ValueOffsetPair
 SCEVExpander::FindValueInExprValueMap(const SCEV *S,
                                       const Instruction *InsertPt) {
+  ScalarEvolution::ValueOffsetPair Candidate = { nullptr, nullptr };
   SetVector<ScalarEvolution::ValueOffsetPair> *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 = nullptr;
         if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
             S->getType() == V->getType() &&
             EntInst->getFunction() == InsertPt->getFunction() &&
             SE.DT.dominates(EntInst, InsertPt) &&
             (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
-             SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
-          return {V, Offset};
-      }
-    }
+             SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt))) {
+          if (!SCEVLostPoisonFlags(S, V))
+            return { V, Offset };
+          // If SCEV lost poison flag we try to find better V if we can.
+          // if we fail to do so then we will strip the poison flags from V.
+          // Ignore current if we already have a candidate.
+          if (!Candidate.first)
+            Candidate = { V, Offset };
+        }
+      }
+  if (Candidate.first) {
+    // We have a candidate and failed to find a better candidate we should
+    // strip poison flags from it due to SCEV does not have ones.
+    cast<Instruction>(Candidate.first)->dropPoisonGeneratingFlags();
+    return Candidate;
   }
   return {nullptr, nullptr};
 }
 
 // The expansion of SCEV will either reuse a previous Value in ExprValueMap,
 // or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
 // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
 // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,