[SCEV] Use SCEVUnknown(poison) instead of SCEVUnknown(undef).

[fhahn]

Summary

Use poison instead of undef for SCEVUnkown of unreachable values.
This should be in line with the movement to replace undef with poison
when possible.

Suggested in D114650.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

7199

This change is fine, but I don't think the containsUndef -> containsPoison change makes sense. We can still have SCEVUnknown of UndefValue (from other places), and I believe current containsUndef() callers do want to check for those as well.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

7199

I suppose we would need to check for both undef & poison, which is achieved by just checking for UndefVal (because PoisonValue inherits from UndefValue)?

[fhahn]

Undo changes to containsUndefs.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

7199

Yes, exactly.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet.
   /// Does not mutate the original instruction.
   std::pair<SCEV::NoWrapFlags, bool /*Deduced*/>
   getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO);
 
   /// Notify this ScalarEvolution that \p User directly uses SCEVs in \p Ops.
   void registerUser(const SCEV *User, ArrayRef<const SCEV *> Ops);
 
-  /// Return true if the SCEV expression contains an undef value.
-  bool containsUndefs(const SCEV *S) const;
+  /// Return true if the SCEV expression contains a poison value.
+  bool containsPoison(const SCEV *S) const;
 
   /// Return true if the SCEV expression contains a Value that has been
   /// optimised out and is now a nullptr.
   bool containsErasedValue(const SCEV *S) const;
 
   /// Return a SCEV expression for the full generality of the specified
   /// expression.
   const SCEV *getSCEV(Value *V);

llvm/lib/Analysis/ScalarEvolution.cpp

if (!isSCEVable(V->getType()))
     return getUnknown(V);
 
   if (Instruction *I = dyn_cast<Instruction>(V)) {
     // Don't attempt to analyze instructions in blocks that aren't
     // reachable. Such instructions don't matter, and they aren't required
     // to obey basic rules for definitions dominating uses which this
     // analysis depends on.
     if (!DT.isReachableFromEntry(I->getParent()))
-      return getUnknown(UndefValue::get(V->getType()));
+      return getUnknown(PoisonValue::get(V->getType()));
   } else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
     return getConstant(CI);
   else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
     return GA->isInterposable() ? getUnknown(V) : getSCEV(GA->getAliasee());
   else if (!isa<ConstantExpr>(V))
     return getUnknown(V);
 
   const SCEV *LHS;
SCEVAddRecExpr::getPostIncExpr(ScalarEvolution &SE) const {
   const SCEV *Last = getOperand(getNumOperands() - 1);
   assert(!Last->isZero() && "Recurrency with zero step?");
   Ops.push_back(Last);
   return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, getLoop(),
                                                SCEV::FlagAnyWrap));
 }
 
 // Return true when S contains at least an undef value.
-bool ScalarEvolution::containsUndefs(const SCEV *S) const {
+bool ScalarEvolution::containsPoison(const SCEV *S) const {
   return SCEVExprContains(S, [](const SCEV *S) {
     if (const auto *SU = dyn_cast<SCEVUnknown>(S))
-      return isa<UndefValue>(SU->getValue());
+      return isa<PoisonValue>(SU->getValue());
     return false;
   });
 }
 
 // Return true when S contains a value that is a nullptr.
 bool ScalarEvolution::containsErasedValue(const SCEV *S) const {
   return SCEVExprContains(S, [](const SCEV *S) {
     if (const auto *SU = dyn_cast<SCEVUnknown>(S))
struct SCEVMapper : public SCEVRewriteVisitor<SCEVMapper> {
     }
   };
 
   SCEVMapper SCM(SE2);
   SmallPtrSet<BasicBlock *, 16> ReachableBlocks;
   SE2.getReachableBlocks(ReachableBlocks, F);
 
   auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * {
-    if (containsUndefs(Old) || containsUndefs(New)) {
+    if (containsPoison(Old) || containsPoison(New)) {
       // SCEV treats "undef" as an unknown but consistent value (i.e. it does
       // not propagate undef aggressively).  This means we can (and do) fail
       // verification in cases where a transform makes a value go from "undef"
       // to "undef+1" (say).  The transform is fine, since in both cases the
       // result is "undef", but SCEV thinks the value increased by 1.
       return nullptr;
     }
 

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

if (VH && !isa<UndefValue>(VH)) {
       LLVM_DEBUG(dbgs() << "scev-salvage: Location index " << i
                         << " now at index " << LocationOpIndexMap[i] << "\n");
       continue;
     }
 
     // It's possible that a value referred to in the SCEV may have been
     // optimised out by LSR.
     if (SE.containsErasedValue(DVIRec.SCEVs[i]) ||
-        SE.containsUndefs(DVIRec.SCEVs[i])) {
+        SE.containsPoison(DVIRec.SCEVs[i])) {
       LLVM_DEBUG(dbgs() << "scev-salvage: SCEV for location at index: " << i
                         << " refers to a location that is now undef or erased. "
                            "Salvage abandoned.\n");
       return false;
     }
 
     LLVM_DEBUG(dbgs() << "scev-salvage: salvaging location at index " << i
                       << " with SCEV: " << *DVIRec.SCEVs[i] << "\n");
for (auto &I : *B) {
         for (const auto LocOp : DVI->location_ops()) {
           if (!LocOp)
             return false;
 
           if (!SE.isSCEVable(LocOp->getType()))
             return false;
 
           const SCEV *S = SE.getSCEV(LocOp);
-          if (SE.containsUndefs(S))
+          if (SE.containsPoison(S))
             return false;
         }
         return true;
       };
 
       if (!HasTranslatableLocationOps(DVI))
         continue;
 

 /// surviving subsequent transforms.
 static llvm::PHINode *GetInductionVariable(const Loop &L, ScalarEvolution &SE,
                                            const LSRInstance &LSR) {
 
   auto IsSuitableIV = [&](PHINode *P) {
     if (!SE.isSCEVable(P->getType()))
       return false;
     if (const SCEVAddRecExpr *Rec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(P)))
-      return Rec->isAffine() && !SE.containsUndefs(SE.getSCEV(P));
+      return Rec->isAffine() && !SE.containsPoison(SE.getSCEV(P));
     return false;
   };
 
   // For now, just pick the first IV that was generated and inserted by
   // ScalarEvolution. Ideally pick an IV that is unlikely to be optimised away
   // by subsequent transforms.
   for (const WeakVH &IV : LSR.getScalarEvolutionIVs()) {
     if (!IV)

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

 }
 
 ; Corner case where phi is not in a loop because it is in unreachable
 ; code (which loopinfo ignores, but simple recurrence matching does not).
 define void @unreachable_phi() {
 ; CHECK-LABEL: 'unreachable_phi'
 ; CHECK-NEXT:  Classifying expressions for: @unreachable_phi
 ; CHECK-NEXT:    %p_58.addr.1 = phi i32 [ undef, %unreachable1 ], [ %sub2629, %unreachable2 ]
-; CHECK-NEXT:    --> undef U: full-set S: full-set
+; CHECK-NEXT:    --> poison U: full-set S: full-set
 ; CHECK-NEXT:    %sub2629 = sub i32 %p_58.addr.1, 1
-; CHECK-NEXT:    --> undef U: full-set S: full-set
+; CHECK-NEXT:    --> poison U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @unreachable_phi
 ;
 entry:
   ret void
 
 unreachable1:
   br label %unreachable_nonloop
 unreachable2:
   br label %unreachable_nonloop
 unreachable_nonloop:
   %p_58.addr.1 = phi i32 [ undef, %unreachable1 ], [ %sub2629, %unreachable2 ]
   %sub2629 = sub i32 %p_58.addr.1, 1
   unreachable
 }
 
 ; Corner case where phi is not in loop header because binop is in unreachable
 ; code (which loopinfo ignores, but simple recurrence matching does not).
 define void @unreachable_binop() {
 ; CHECK-LABEL: 'unreachable_binop'
 ; CHECK-NEXT:  Classifying expressions for: @unreachable_binop
 ; CHECK-NEXT:    %p_58.addr.1 = phi i32 [ undef, %header ], [ %sub2629, %unreachable ]
 ; CHECK-NEXT:    --> %p_58.addr.1 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %header: Variant }
 ; CHECK-NEXT:    %sub2629 = sub i32 %p_58.addr.1, 1
-; CHECK-NEXT:    --> undef U: full-set S: full-set
+; CHECK-NEXT:    --> poison U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @unreachable_binop
 ; CHECK-NEXT:  Loop %header: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %header: Unpredictable max backedge-taken count.
 ; CHECK-NEXT:  Loop %header: Unpredictable predicated backedge-taken count.
 ;
 entry:
   br label %header
 

llvm/test/Analysis/ScalarEvolution/unreachable-code.ll

 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 ; CHECK: %t = add i64 %t, 1
-; CHECK: -->  undef
+; CHECK: -->  poison
 
 define void @foo() {
 entry:
   ret void
 
 dead:
   %t = add i64 %t, 1
   ret void
 }