[ConstraintElim] Check if second op implies first for And. (#75750)

Generalize checkAndSecondOpImpliedByFirst to also check if the second
operand implies the first.

5 files changed, 37 insertions, 25 deletions

diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
index 18266ba..f208ca2 100644
--- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
@@ -1365,16 +1365,27 @@ removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info,
     ReproducerCondStack.pop_back();
 }
 
-/// Check if the first condition for an AND implies the second.
-static bool checkAndSecondOpImpliedByFirst(
-    FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule,
-    SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
-    SmallVectorImpl<StackEntry> &DFSInStack) {
+/// Check if either the first condition of an AND is implied by the second or
+/// vice versa.
+static bool
+checkAndOpImpliedByOther(FactOrCheck &CB, ConstraintInfo &Info,
+                         Module *ReproducerModule,
+                         SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
+                         SmallVectorImpl<StackEntry> &DFSInStack) {
 
   CmpInst::Predicate Pred;
   Value *A, *B;
   Instruction *And = CB.getContextInst();
-  if (!match(And->getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(B))))
+  CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify());
+  unsigned OtherOpIdx = And->getOperand(0) == CmpToCheck ? 1 : 0;
+
+  // Don't try to simplify the first condition of a select by the second, as
+  // this may make the select more poisonous than the original one.
+  // TODO: check if the first operand may be poison.
+  if (OtherOpIdx != 0 && isa<SelectInst>(And))
+    return false;
+
+  if (!match(And->getOperand(OtherOpIdx), m_ICmp(Pred, m_Value(A), m_Value(B))))
     return false;
 
   // Optimistically add fact from first condition.
@@ -1385,11 +1396,12 @@ static bool checkAndSecondOpImpliedByFirst(
 
   bool Changed = false;
   // Check if the second condition can be simplified now.
-  ICmpInst *Cmp = cast<ICmpInst>(And->getOperand(1));
-  if (auto ImpliedCondition = checkCondition(
-          Cmp->getPredicate(), Cmp->getOperand(0), Cmp->getOperand(1), Cmp,
-          Info, CB.NumIn, CB.NumOut, CB.getContextInst())) {
-    And->setOperand(1, ConstantInt::getBool(And->getType(), *ImpliedCondition));
+  if (auto ImpliedCondition =
+          checkCondition(CmpToCheck->getPredicate(), CmpToCheck->getOperand(0),
+                         CmpToCheck->getOperand(1), CmpToCheck, Info, CB.NumIn,
+                         CB.NumOut, CB.getContextInst())) {
+    And->setOperand(1 - OtherOpIdx,
+                    ConstantInt::getBool(And->getType(), *ImpliedCondition));
     Changed = true;
   }
 
@@ -1609,11 +1621,11 @@ static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI,
         bool Simplified = checkAndReplaceCondition(
             Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
             ReproducerModule.get(), ReproducerCondStack, S.DT, ToRemove);
-        if (!Simplified && match(CB.getContextInst(),
-                                 m_LogicalAnd(m_Value(), m_Specific(Inst)))) {
+        if (!Simplified &&
+            match(CB.getContextInst(), m_LogicalAnd(m_Value(), m_Value()))) {
           Simplified =
-              checkAndSecondOpImpliedByFirst(CB, Info, ReproducerModule.get(),
-                                             ReproducerCondStack, DFSInStack);
+              checkAndOpImpliedByOther(CB, Info, ReproducerModule.get(),
+                                       ReproducerCondStack, DFSInStack);
         }
         Changed |= Simplified;
       }
diff --git a/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll b/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll
index dc3b0f1..3d2a480 100644
--- a/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll
+++ b/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll
@@ -31,7 +31,7 @@ define i1 @test_first_and_condition_implied_by_second_ops(i8 %x) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[T_1]], [[C_1]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 true, [[C_1]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
@@ -105,7 +105,7 @@ define i1 @test_same_cond_for_and(i8 %x) {
 ; CHECK-LABEL: @test_same_cond_for_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], true
+; CHECK-NEXT:    [[AND:%.*]] = and i1 true, [[C_1]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
@@ -128,7 +128,7 @@ define i1 @test_same_cond_for_and_select_form(i8 %x) {
 ; CHECK-LABEL: @test_same_cond_for_and_select_form(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 true, i1 false
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
@@ -152,7 +152,7 @@ define i1 @test_second_and_condition_not_implied_by_first(i8 %x) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i8 [[X]], 5
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], [[C_1]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 true, [[C_1]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
diff --git a/llvm/test/Transforms/ConstraintElimination/and.ll b/llvm/test/Transforms/ConstraintElimination/and.ll
index 389a676..f9824df 100644
--- a/llvm/test/Transforms/ConstraintElimination/and.ll
+++ b/llvm/test/Transforms/ConstraintElimination/and.ll
@@ -438,7 +438,7 @@ define i1 @test_and_chain_select_ule(i4 %x, i4 %y, i4 %z, i4 %a) {
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i4 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule i4 3, [[X]]
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ule i4 3, [[A:%.*]]
-; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 true, i1 false
+; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
 ; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[AND_1]], i1 [[C_3]], i1 false
 ; CHECK-NEXT:    [[AND_3:%.*]] = select i1 [[C_4]], i1 [[AND_2]], i1 false
 ; CHECK-NEXT:    br i1 [[AND_3]], label [[BB1:%.*]], label [[EXIT:%.*]]
@@ -522,7 +522,7 @@ define i1 @test_and_chain_select_ule_logical_or(i4 %x, i4 %y, i4 %z, i4 %a) {
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i4 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule i4 3, [[X]]
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ule i4 3, [[A:%.*]]
-; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 true, i1 false
+; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
 ; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[AND_1]], i1 [[C_3]], i1 false
 ; CHECK-NEXT:    [[AND_3:%.*]] = select i1 [[C_4]], i1 [[AND_2]], i1 false
 ; CHECK-NEXT:    [[AND_4:%.*]] = select i1 [[AND_3]], i1 true, i1 false
diff --git a/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll b/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll
index d8ed479..96ff98b 100644
--- a/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll
+++ b/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll
@@ -611,7 +611,7 @@ define i4 @ptr_N_signed_positive_assume(ptr %src, ptr %lower, ptr %upper, i16 %N
 ; CHECK:       step.check:
 ; CHECK-NEXT:    [[STEP_POS:%.*]] = icmp sge i16 [[STEP:%.*]], 0
 ; CHECK-NEXT:    [[STEP_SLT_N:%.*]] = icmp slt i16 [[STEP]], [[N]]
-; CHECK-NEXT:    [[AND_STEP:%.*]] = and i1 [[STEP_POS]], false
+; CHECK-NEXT:    [[AND_STEP:%.*]] = and i1 false, [[STEP_SLT_N]]
 ; CHECK-NEXT:    br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]]
 ; CHECK:       ptr.check:
 ; CHECK-NEXT:    [[SRC_STEP:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i16 [[STEP]]
diff --git a/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll b/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll
index 4792383..834db04 100644
--- a/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll
+++ b/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll
@@ -36,7 +36,7 @@ define i1 @overflow_check_2_and(ptr %dst) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
+; CHECK-NEXT:    [[AND:%.*]] = and i1 true, [[DST_5_UGE]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
@@ -65,7 +65,7 @@ define i1 @overflow_check_3_and(ptr %dst) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
+; CHECK-NEXT:    [[AND:%.*]] = and i1 true, [[DST_5_UGE]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
@@ -98,7 +98,7 @@ define i1 @overflow_check_4_and(ptr %dst) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
+; CHECK-NEXT:    [[AND:%.*]] = and i1 true, [[DST_5_UGE]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4