[ValueTracking] Make impliesPoison look into operands of V

[aqjune]

Summary

This patch updates impliesPoison to look into operands of V up to MaxDepth.

Relevant patch: D94550

[aqjune]

I'll leave the diff result after setting -instcombine-unsafe-select-transform=0 at another patch that's going to follow this.

[nikic]

I posted an alternative patch at D94866. It's potentially more expensive, but I think it will cover more of the cases we need.

llvm/include/llvm/IR/PatternMatch.h

 //===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 //
 
 /// Matches a BinaryOperator with LHS and RHS in either order.
 template <typename LHS, typename RHS>
 inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
   return AnyBinaryOp_match<LHS, RHS, true>(L, R);
 }
 
+/// Matches a Cmp with a predicate over LHS and RHS in either order.
+/// Swaps the predicate if operands are commuted.
+template <typename LHS, typename RHS>
+inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate, true>
+m_c_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
+  return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate, true>(Pred, L,
+                                                                     R);
+}
+
 /// Matches an ICmp with a predicate over LHS and RHS in either order.
 /// Swaps the predicate if operands are commuted.
 template <typename LHS, typename RHS>
 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
   return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
                                                                        R);
 }

llvm/lib/Analysis/ValueTracking.cpp

 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
while (PoisonI && Depth < MaxDepth) {
     } else if (MoreThanOneCandidate)
       break;
 
     Depth++;
     PoisonValues.insert(NextVal);
     PoisonI = dyn_cast<Instruction>(NextVal);
   }
 
+  SmallVector<std::pair<const Value *, unsigned>> Worklist;
+  Worklist.push_back({V, 0});
+
+  while (!Worklist.empty()) {
+    auto Item = Worklist.back();
+    Worklist.pop_back();
+    const Value *V = Item.first;
+    unsigned Depth = Item.second;
+
     if (PoisonValues.contains(V))
       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()))
+    // Common syntactic pattern
+    // cmp pred1 X, Y -> cmp pred2 X, Y
+    const Value *V1, *V2;
+    CmpInst::Predicate Pred, Pred2;
+    if (match(V, m_Cmp(Pred, m_Value(V1), m_Value(V2)))) {
+      for (auto *VP : PoisonValues) {
+        if (match(VP, m_c_Cmp(Pred2, m_Specific(V1), m_Specific(V2))) &&
+            !canCreatePoison(cast<Operator>(VP)))
           return true;
       }
+    }
+
+    if (Depth == MaxDepth)
+      continue;
+
+    if (const auto *SI = dyn_cast<SelectInst>(V))
+      Worklist.push_back({SI->getCondition(), Depth + 1});
+    else if (const auto *Oper = dyn_cast<Operator>(V)) {
+      if (propagatesPoison(Oper))
+        for (const auto &Op : Oper->operands())
+          Worklist.push_back({Op.get(), Depth + 1});
+    }
+  }
 
   return false;
 }
 
 static bool programUndefinedIfUndefOrPoison(const Value *V,
                                             bool PoisonOnly);
 
 static bool isGuaranteedNotToBeUndefOrPoison(const Value *V,

llvm/unittests/Analysis/ValueTrackingTest.cpp

 //===- ValueTrackingTest.cpp - ValueTracking tests ------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
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, 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);
 }