[ValueTracking] Strengthen impliesPoison reasoning

[nikic]

Summary

This implements the same basic change as D94859, but in a more general way. directlyImpliesPoison recurses on V, impliesPoison recurses on ValAssumedPoison. Both recursions have independent small depth limits. This allows us to handle more than just the icmp+icmp case, such as the mask+icmp case for example.

[aqjune]

Okay, I agree that this is more general.
I was cautious about possible compile time degradation - do you have a number for this?

unittests/Analysis/ValueTrackingTest.cpp

783 ↗

(On Diff #317179)

Maybe icmp eq i32 %M2, 1 here? (similarly below)

790 ↗

(On Diff #317179)

Shall we have one more example that has EXPECT_FALSE because ValAssumedPoison was e.g. icmp eq %x, %z where z wasn't used by A?

[nikic]

Fix typos in mask test.

[nikic]

In D94866#2504011, @aqjune wrote:

Okay, I agree that this is more general.
I was cautious about possible compile time degradation - do you have a number for this?

Compile-time results (on top of flipping the select optimization flag, otherwise it would not get called): https://llvm-compile-time-tracker.com/compare.php?from=0c9e135ecde32b57393fb502cc45f90c2a17346d&to=3d7dcc78542627d6440613327f21d177bcdf6f00&stat=instructions There does not seem to be any impact above noise.

unittests/Analysis/ValueTrackingTest.cpp

783 ↗

(On Diff #317179)

Yes, this test didn't make sense...

790 ↗

(On Diff #317179)

I think this case is checked by the existing impliesPoisonTest_ICmpUnknown test. It uses icmp eq i32 %x, %y and icmp eq i32 %x, 1.

[aqjune]

LGTM

unittests/Analysis/ValueTrackingTest.cpp

790 ↗

(On Diff #317179)

+1

llvm/lib/Analysis/ValueTracking.cpp

 bool llvm::canCreateUndefOrPoison(const Operator *Op) {
   return ::canCreateUndefOrPoison(Op, /*PoisonOnly=*/false);
 }
 
 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;
+static bool directlyImpliesPoison(const Value *ValAssumedPoison,
+                                  const Value *V, unsigned Depth) {
+  if (ValAssumedPoison == V)
+    return true;
 
-  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 unsigned MaxDepth = 2;
+  if (Depth >= MaxDepth)
+    return false;
 
-    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();
-      }
-    }
+  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 (NextVal == nullptr) {
-      // All operands are non-poison, so PoisonI cannot be poison.
-      // Since assumption is false, return true
-      return true;
-    } else if (MoreThanOneCandidate)
-      break;
+static bool impliesPoison(const Value *ValAssumedPoison, const Value *V,
+                          unsigned Depth) {
+  if (isGuaranteedNotToBeUndefOrPoison(ValAssumedPoison))
 
-    Depth++;
-    PoisonValues.insert(NextVal);
-    PoisonI = dyn_cast<Instruction>(NextVal);
-  }
-
-  if (PoisonValues.contains(V))
+  if (directlyImpliesPoison(ValAssumedPoison, V, /* Depth */ 0))
     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;
-  }
+  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);
 
 static bool isGuaranteedNotToBeUndefOrPoison(const Value *V,
                                              AssumptionCache *AC,
                                              const Instruction *CtxI,
                                              const DominatorTree *DT,
                                              unsigned Depth, bool PoisonOnly) {

llvm/test/Transforms/InstCombine/select-and-or.ll

 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 true, i1 %b
   ret i1 %res
 }
 
 ; Noundef on false value allows conversion to or.
-; TODO: impliesPoison doesn't handle this yet.
 define i1 @logical_or_noundef_b(i1 %a, i1 noundef %b) {
 ; CHECK-LABEL: @logical_or_noundef_b(
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    [[RES:%.*]] = or i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 true, i1 %b
   ret i1 %res
 }
 
 ; Noundef on condition has no effect.
 define i1 @logical_and_noundef_a(i1 noundef %a, i1 %b) {
 ; CHECK-LABEL: @logical_and_noundef_a(
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 %b, i1 false
   ret i1 %res
 }
 
 ; Noundef on false value allows conversion to and.
-; TODO: impliesPoison doesn't handle this yet.
 define i1 @logical_and_noundef_b(i1 %a, i1 noundef %b) {
 ; CHECK-LABEL: @logical_and_noundef_b(
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 %b, i1 false
   ret i1 %res
 }

llvm/unittests/Analysis/ValueTrackingTest.cpp

TEST_F(ValueTrackingTest, impliesPoisonTest_AddNsw) {
   parseAssembly("define void @test(i32 %x) {\n"
                 "  %A2 = add nsw i32 %x, 1\n"
                 "  %A = add i32 %x, 1\n"
                 "  ret void\n"
                 "}");
   EXPECT_FALSE(impliesPoison(A2, A));
 }
 
+TEST_F(ValueTrackingTest, impliesPoisonTest_Cmp) {
+  parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n"
+                "  %A2 = icmp eq i32 %x, %y\n"
+                "  %A0 = icmp ult i32 %x, %y\n"
+                "  %A = or i1 %A0, %c\n"
+                "  ret void\n"
+                "}");
+  EXPECT_TRUE(impliesPoison(A2, A));
+}
+
+TEST_F(ValueTrackingTest, impliesPoisonTest_FCmpFMF) {
+  parseAssembly("define void @test(float %x, float %y, i1 %c) {\n"
+                "  %A2 = fcmp nnan oeq float %x, %y\n"
+                "  %A0 = fcmp olt float %x, %y\n"
+                "  %A = or i1 %A0, %c\n"
+                "  ret void\n"
+                "}");
+  EXPECT_FALSE(impliesPoison(A2, A));
+}
+
+TEST_F(ValueTrackingTest, impliesPoisonTest_AddSubSameOps) {
+  parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n"
+                "  %A2 = add i32 %x, %y\n"
+                "  %A = sub i32 %x, %y\n"
+                "  ret void\n"
+                "}");
+  EXPECT_TRUE(impliesPoison(A2, A));
+}
+
+TEST_F(ValueTrackingTest, impliesPoisonTest_MaskCmp) {
+  parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n"
+                "  %M2 = and i32 %x, 7\n"
+                "  %A2 = icmp eq i32 %M2, 1\n"
+                "  %M = and i32 %x, 15\n"
+                "  %A = icmp eq i32 %M, 3\n"
+                "  ret void\n"
+                "}");
+  EXPECT_TRUE(impliesPoison(A2, A));
+}
+
 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle_Pointers) {
   parseAssembly(
       "define <2 x i32*> @test(<2 x i32*> %x) {\n"
       "  %A = shufflevector <2 x i32*> zeroinitializer, <2 x i32*> undef, <2 x i32> zeroinitializer\n"
       "  ret <2 x i32*> %A\n"
       "}\n");
   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 64u);
 }