Add a propagateKnownNonPoison helper

[sanjoy]

Summary

NFC right now since the only user is the unit test.

[reames]

include/llvm/Analysis/ValueTracking.h

422

Ok, this interface is vague. Which set of values? And why might we wan this?

[sanjoy]

include/llvm/Analysis/ValueTracking.h

422

And why might we wan this?

As you've noted later, this is used in D30446

Which set of values?

Not sure how I can make it clearer in the documentation.

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   /// Return true if this function can prove that if PoisonI is executed
   /// and yields a full-poison value (all bits poison), then that will
   /// trigger undefined behavior.
   ///
   /// Note that this currently only considers the basic block that is
   /// the parent of I.
   bool isKnownNotFullPoison(const Instruction *PoisonI);
 
+  /// Starting with the assumption that \p I is not poison, fill \p
+  /// NonPoison with a set of values that are also known to not be
+  /// poison.  Internally this is a simple worklist algorithm around
+  /// \p propagatesFullPoison.
+  ///
+  /// The worklist algorithm does not follow values for which \p
+  /// FollowPred returns false.
+  void propagateKnownNonPoison(const Value *I,
+                               SmallVectorImpl<const Value *> &NonPoison,
+                               function_ref<bool(const Value *)> FollowPred);
+
   /// \brief Specific patterns of select instructions we can match.
   enum SelectPatternFlavor {
     SPF_UNKNOWN = 0,
     SPF_SMIN,                   /// Signed minimum
     SPF_UMIN,                   /// Unsigned minimum
     SPF_SMAX,                   /// Signed maximum
     SPF_UMAX,                   /// Unsigned maximum
     SPF_FMINNUM,                /// Floating point minnum

lib/Analysis/ValueTracking.cpp

case Instruction::ICmp:
     // instance, x s< (x +nsw 1) can be folded to true.
     return true;
 
   default:
     return false;
   }
 }
 
+void llvm::propagateKnownNonPoison(
+    const Value *I, SmallVectorImpl<const Value *> &NonPoison,
+    function_ref<bool(const Value *)> FollowPred) {
+  SmallPtrSet<const Value *, 8> Visited;
+  Visited.insert(I);
+  NonPoison.push_back(I);
+  unsigned Idx = 0;
+  do {
+    const auto *NextI = dyn_cast<Instruction>(NonPoison[Idx++]);
+    if (!NextI || !propagatesFullPoison(NextI))
+      continue;
+
+    copy_if(NextI->operands(), std::back_inserter(NonPoison), [&](Value *V) {
+      return FollowPred(V) && Visited.insert(V).second;
+    });
+  } while (Idx < NonPoison.size());
+}
+
 const Value *llvm::getGuaranteedNonFullPoisonOp(const Instruction *I) {
   switch (I->getOpcode()) {
     case Instruction::Store:
       return cast<StoreInst>(I)->getPointerOperand();
 
     case Instruction::Load:
       return cast<LoadInst>(I)->getPointerOperand();
 

unittests/Analysis/ValueTrackingTest.cpp

TEST(ValueTracking, ComputeNumSignBits_PR32045) {
 
   auto *F = M->getFunction("f");
   assert(F && "Bad assembly?");
 
   auto *RVal =
       cast<ReturnInst>(F->getEntryBlock().getTerminator())->getOperand(0);
   EXPECT_EQ(ComputeNumSignBits(RVal, M->getDataLayout()), 1u);
 }
+
+TEST(ValueTracking, propagateKnownNonPoison) {
+  StringRef Assembly = "define i1 @f(i32 %a) { "
+                       "  %val0 = add i32 %a, -1 "
+                       "  %val1 = sub i32 %val0, 1 "
+                       "  %cmp = icmp slt i32 %val1, 400 "
+                       "  ret i1 %cmp "
+                       "} ";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  assert(M && "Bad assembly?");
+
+  auto *F = M->getFunction("f");
+  assert(F && "Bad assembly?");
+
+  auto *RInst = cast<ReturnInst>(F->getEntryBlock().getTerminator());
+  auto *CmpI = cast<Instruction>(RInst->getOperand(0));
+  auto *SubI = cast<Instruction>(CmpI->getOperand(0));
+  auto *AddI = cast<Instruction>(SubI->getOperand(0));
+  auto *ArgA = cast<Argument>(AddI->getOperand(0));
+
+  {
+    SmallVector<const Value *, 4> NonPoison;
+    propagateKnownNonPoison(CmpI, NonPoison,
+                            [](const Value *V) { return true; });
+    EXPECT_TRUE(is_contained(NonPoison, CmpI));
+    EXPECT_TRUE(is_contained(NonPoison, SubI));
+    EXPECT_TRUE(is_contained(NonPoison, AddI));
+    EXPECT_TRUE(is_contained(NonPoison, ArgA));
+  }
+
+  {
+    SmallVector<const Value *, 4> NonPoison;
+    propagateKnownNonPoison(CmpI, NonPoison,
+                            [&](const Value *V) { return V != AddI; });
+    EXPECT_TRUE(is_contained(NonPoison, CmpI));
+    EXPECT_TRUE(is_contained(NonPoison, SubI));
+    EXPECT_FALSE(is_contained(NonPoison, AddI));
+    EXPECT_FALSE(is_contained(NonPoison, ArgA));
+  }
+}