[ValueTracking] Strengthen impliesPoison reasoning

Split impliesPoison into two recursive walks, one over V, the
other over ValAssumedPoison. This allows us to reason about poison
implications in a number of additional cases that are important
in practice. This is a generalized form of D94859, which handles
the cmp to cmp implication in particular.

Differential Revision: https://reviews.llvm.org/D94866

1 files changed, 33 insertions, 48 deletions

diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index a9cef91..7f8f101 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -4806,64 +4806,49 @@ bool llvm::canCreatePoison(const Operator *Op) {
   return ::canCreateUndefOrPoison(Op, /*PoisonOnly=*/true);
 }
 
-bool llvm::impliesPoison(const Value *ValAssumedPoison, const Value *V) {
-  // Construct a set of values which are known to be poison from the knowledge
-  // that ValAssumedPoison is poison.
-  SmallPtrSet<const Value *, 4> PoisonValues;
-  PoisonValues.insert(ValAssumedPoison);
-  const Instruction *PoisonI = dyn_cast<Instruction>(ValAssumedPoison);
-  unsigned Depth = 0;
-  const unsigned MaxDepth = 2;
-
-  while (PoisonI && Depth < MaxDepth) {
-    // We'd like to know whether an operand of PoisonI is also poison.
-    if (canCreatePoison(cast<Operator>(PoisonI)))
-      // PoisonI can be a poison-generating instruction, so don't look further
-      break;
-
-    const Value *NextVal = nullptr;
-    bool MoreThanOneCandidate = false;
-    // See which operand can be poison
-    for (const auto &Op : PoisonI->operands()) {
-      if (!isGuaranteedNotToBeUndefOrPoison(Op.get())) {
-        // Op can be poison.
-        if (NextVal) {
-          // There is more than one operand that can make PoisonI poison.
-          MoreThanOneCandidate = true;
-          break;
-        }
-        NextVal = Op.get();
-      }
-    }
+static bool directlyImpliesPoison(const Value *ValAssumedPoison,
+                                  const Value *V, unsigned Depth) {
+  if (ValAssumedPoison == V)
+    return true;
 
-    if (NextVal == nullptr) {
-      // All operands are non-poison, so PoisonI cannot be poison.
-      // Since assumption is false, return true
-      return true;
-    } else if (MoreThanOneCandidate)
-      break;
+  const unsigned MaxDepth = 2;
+  if (Depth >= MaxDepth)
+    return false;
 
-    Depth++;
-    PoisonValues.insert(NextVal);
-    PoisonI = dyn_cast<Instruction>(NextVal);
+  const auto *I = dyn_cast<Instruction>(V);
+  if (I && propagatesPoison(cast<Operator>(I))) {
+    return any_of(I->operands(), [=](const Value *Op) {
+      return directlyImpliesPoison(ValAssumedPoison, Op, Depth + 1);
+    });
   }
+  return false;
+}
 
-  if (PoisonValues.contains(V))
+static bool impliesPoison(const Value *ValAssumedPoison, const Value *V,
+                          unsigned Depth) {
+  if (isGuaranteedNotToBeUndefOrPoison(ValAssumedPoison))
     return true;
 
-  // Let's look one level further, by seeing its arguments if I was an
-  // instruction.
-  // This happens when I is e.g. 'icmp X, const' where X is in PoisonValues.
-  const auto *I = dyn_cast<Instruction>(V);
-  if (I && propagatesPoison(cast<Operator>(I))) {
-    for (const auto &Op : I->operands())
-      if (PoisonValues.count(Op.get()))
-        return true;
-  }
+  if (directlyImpliesPoison(ValAssumedPoison, V, /* Depth */ 0))
+    return true;
 
+  const unsigned MaxDepth = 2;
+  if (Depth >= MaxDepth)
+    return false;
+
+  const auto *I = dyn_cast<Instruction>(ValAssumedPoison);
+  if (I && !canCreatePoison(cast<Operator>(I))) {
+    return all_of(I->operands(), [=](const Value *Op) {
+      return impliesPoison(Op, V, Depth + 1);
+    });
+  }
   return false;
 }
 
+bool llvm::impliesPoison(const Value *ValAssumedPoison, const Value *V) {
+  return ::impliesPoison(ValAssumedPoison, V, /* Depth */ 0);
+}
+
 static bool programUndefinedIfUndefOrPoison(const Value *V,
                                             bool PoisonOnly);