Index: include/llvm/Analysis/ValueTracking.h
===================================================================
--- include/llvm/Analysis/ValueTracking.h
+++ include/llvm/Analysis/ValueTracking.h
@@ -418,6 +418,17 @@
   /// 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,
Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -3859,6 +3859,24 @@
   }
 }
 
+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:
Index: unittests/Analysis/ValueTrackingTest.cpp
===================================================================
--- unittests/Analysis/ValueTrackingTest.cpp
+++ unittests/Analysis/ValueTrackingTest.cpp
@@ -258,3 +258,46 @@
       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));
+  }
+}