[InstCombine] fold more icmp + select patterns by distributive laws

[bcl5980]

Summary

follow up D139076, add icmp with not only eq/ne, but also gt/lt/ge/le.

[bcl5980]

I will pre-commit baseline tests after review.

[bcl5980]

update tests and fix two bugs.

[spatel]

It would be easier to review if you pre-commit the tests. You can add ; negative test comments in this patch to make it clear when a test is not intended to change.
Why are there changes in test files that do contain the patterns that are matched in this patch?

llvm/test/Transforms/InstCombine/select-cmp.ll

298

This is not correct.

[spatel]

Also, maybe we should handle all matching predicates without trying to swap as a first step. Then, add swap logic to deal with patterns that have swapped predicates in a follow-up patch. That way, we can be sure there are no bugs.

[bcl5980]

llvm/test/Transforms/InstCombine/select-cmp.ll

298

Ah, Thanks for finding the case.

298

Can I ask you how could you find that? Local alive2?

[spatel]

llvm/test/Transforms/InstCombine/select-cmp.ll

298

I just noticed that the predicate changed, but the common operand position did not.
I did paste it into Alive2 after that to make sure I saw it correctly. :)

[bcl5980]

fix bug for the case with the same predicate but not eq/ne

[bcl5980]

llvm/test/Transforms/InstCombine/select-cmp.ll

298

Should be correct now. Sorry for the wrong code.

[bcl5980]

rebase code

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

340

This deserves a code comment to explain the logic. Something like:

// If we are allowing commute or swap of operands, then
// allow a cross-operand match. In that case, MatchIsOpZero
// means that TI's operand 0 (FI's operand 1) is the common op.

[bcl5980]

address comments.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

Value *NewSI =
         Builder.CreateSelect(Cond, TI->getOperand(0), FI->getOperand(0),
                              SI.getName() + ".v", &SI);
     return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI,
                             TI->getType());
   }
 
   Value *OtherOpT, *OtherOpF;
   bool MatchIsOpZero;
-  auto getCommonOp = [&](Instruction *TI, Instruction *FI,
-                         bool Commute) -> Value * {
-    Value *CommonOp = nullptr;
+  auto getCommonOp = [&](Instruction *TI, Instruction *FI, bool Commute,
+                         bool Swapped = false) -> Value * {
+    assert(!(Commute && Swapped) &&
+           "Commute and Swapped can't set at the same time");
+    if (!Swapped) {
       if (TI->getOperand(0) == FI->getOperand(0)) {
-      CommonOp = TI->getOperand(0);
         OtherOpT = TI->getOperand(1);
         OtherOpF = FI->getOperand(1);
         MatchIsOpZero = true;
+        return TI->getOperand(0);
       } else if (TI->getOperand(1) == FI->getOperand(1)) {
-      CommonOp = TI->getOperand(1);
         OtherOpT = TI->getOperand(0);
         OtherOpF = FI->getOperand(0);
         MatchIsOpZero = false;
-    } else if (!Commute) {
+        return TI->getOperand(1);
+      }
+    }
+
+    if (!Commute && !Swapped)
       return nullptr;
-    } else if (TI->getOperand(0) == FI->getOperand(1)) {
-      CommonOp = TI->getOperand(0);
+
+    // If we are allowing commute or swap of operands, then
+    // allow a cross-operand match. In that case, MatchIsOpZero
+    // means that TI's operand 0 (FI's operand 1) is the common op.
+    if (TI->getOperand(0) == FI->getOperand(1)) {
       OtherOpT = TI->getOperand(1);
       OtherOpF = FI->getOperand(0);
       MatchIsOpZero = true;
+      return TI->getOperand(0);
     } else if (TI->getOperand(1) == FI->getOperand(0)) {
-      CommonOp = TI->getOperand(1);
       OtherOpT = TI->getOperand(0);
       OtherOpF = FI->getOperand(1);
-      MatchIsOpZero = true;
+      MatchIsOpZero = false;
+      return TI->getOperand(1);
     }
-    return CommonOp;
+    return nullptr;
   };
 
   if (TI->hasOneUse() || FI->hasOneUse()) {
     // Cond ? -X : -Y --> -(Cond ? X : Y)
     Value *X, *Y;
     if (match(TI, m_FNeg(m_Value(X))) && match(FI, m_FNeg(m_Value(Y)))) {
       // Intersect FMF from the fneg instructions and union those with the
       // select.
if (TII && FII && TII->getIntrinsicID() == FII->getIntrinsicID()) {
         if (Value *MatchOp = getCommonOp(TI, FI, true)) {
           Value *NewSel =
               Builder.CreateSelect(Cond, OtherOpT, OtherOpF, "minmaxop", &SI);
           return CallInst::Create(TII->getCalledFunction(), {NewSel, MatchOp});
         }
       }
     }
 
-    // icmp eq/ne with a common operand also can have the common operand
+    // icmp with a common operand also can have the common operand
     // pulled after the select.
     ICmpInst::Predicate TPred, FPred;
     if (match(TI, m_ICmp(TPred, m_Value(), m_Value())) &&
         match(FI, m_ICmp(FPred, m_Value(), m_Value()))) {
-      if (TPred == FPred && ICmpInst::isEquality(TPred)) {
-        if (Value *MatchOp = getCommonOp(TI, FI, true)) {
+      if (TPred == FPred || TPred == CmpInst::getSwappedPredicate(FPred)) {
+        bool Swapped = TPred != FPred;
+        if (Value *MatchOp =
+                getCommonOp(TI, FI, ICmpInst::isEquality(TPred), Swapped)) {
           Value *NewSel = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,
                                                SI.getName() + ".v", &SI);
-          return new ICmpInst(TPred, NewSel, MatchOp);
+          return new ICmpInst(
+              MatchIsOpZero ? TPred : CmpInst::getSwappedPredicate(TPred),
+              MatchOp, NewSel);
         }
       }
     }
   }
 
   // Only handle binary operators (including two-operand getelementptr) with
   // one-use here. As with the cast case above, it may be possible to relax the
   // one-use constraint, but that needs be examined carefully since it may not

llvm/test/Transforms/InstCombine/select-bitext.ll

;
   %a.ext = zext i8 %a to i32
   call void @use32(i32 %a.ext)
   %r = select i1 %cond, i32 255, i32 %a.ext
   ret i32 %r
 }
 
 define i32 @test_op_op(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @test_op_op(
-; CHECK-NEXT:    [[CCA:%.*]] = icmp sgt i32 [[A:%.*]], 0
-; CHECK-NEXT:    [[CCB:%.*]] = icmp sgt i32 [[B:%.*]], 0
 ; CHECK-NEXT:    [[CCC:%.*]] = icmp sgt i32 [[C:%.*]], 0
-; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[CCC]], i1 [[CCA]], i1 [[CCB]]
+; CHECK-NEXT:    [[R_V_V:%.*]] = select i1 [[CCC]], i32 [[A:%.*]], i32 [[B:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = icmp sgt i32 [[R_V_V]], 0
 ; CHECK-NEXT:    [[R:%.*]] = sext i1 [[R_V]] to i32
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %cca = icmp sgt i32 %a, 0
   %ccax = sext i1 %cca to i32
   %ccb = icmp sgt i32 %b, 0
   %ccbx = sext i1 %ccb to i32
   %ccc = icmp sgt i32 %c, 0

llvm/test/Transforms/InstCombine/select-cmp.ll

;
   call void @use(i1 %cmp1)
   %cmp2 = icmp eq i8 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_slt_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_slt_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i6 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i6 [[X]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp slt i6 %x, %y
   %cmp2 = icmp slt i6 %x, %z
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_sgt_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_sgt_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i6 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i6 [[X]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp sgt i6 %x, %y
   %cmp2 = icmp sgt i6 %x, %z
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_sle_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_sle_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i6 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i6 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sle i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp sle i6 %y, %x
   %cmp2 = icmp sle i6 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_sge_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_sge_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i6 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i6 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sge i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp sge i6 %y, %x
   %cmp2 = icmp sge i6 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_slt_sgt_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_slt_sgt_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i6 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i6 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp slt i6 %x, %y
   %cmp2 = icmp sgt i6 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_sle_sge_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_sle_sge_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i6 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i6 [[X]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sle i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp sle i6 %y, %x
   %cmp2 = icmp sge i6 %x, %z
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_ult_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_ult_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i6 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i6 [[X]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp ult i6 %x, %y
   %cmp2 = icmp ult i6 %x, %z
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_ule_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_ule_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i6 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i6 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp ule i6 %y, %x
   %cmp2 = icmp ule i6 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_ugt_common(i1 %c, i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @icmp_ugt_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i8 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i8 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp ugt i8 %y, %x
   %cmp2 = icmp ugt i8 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_uge_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_uge_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp uge i6 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i6 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp uge i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp uge i6 %y, %x
   %cmp2 = icmp uge i6 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_ult_ugt_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_ult_ugt_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i6 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i6 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp ult i6 %x, %y
   %cmp2 = icmp ugt i6 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 define i1 @icmp_ule_uge_common(i1 %c, i6 %x, i6 %y, i6 %z) {
 ; CHECK-LABEL: @icmp_ule_uge_common(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ule i6 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i6 [[X]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[C:%.*]], i6 [[Y:%.*]], i6 [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i6 [[R_V]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp ule i6 %y, %x
   %cmp2 = icmp uge i6 %x, %z
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
 ; negative test: pred is not the same
 
 define i1 @icmp_common_pred_different(i1 %c, i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @icmp_common_pred_different(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i8 [[Z:%.*]], [[X]]
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp eq i8 %y, %x
   %cmp2 = icmp ne i8 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
-; negative test: two pred is not swap
+; negative test for non-equality: two pred is not swap
 
 define i1 @icmp_common_pred_not_swap(i1 %c, i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @icmp_common_pred_not_swap(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i8 [[Z:%.*]], [[X]]
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp slt i8 %y, %x
   %cmp2 = icmp sle i8 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
-; negative test: not commute pred
+; negative test for non-equality: not commute pred
 
 define i1 @icmp_common_pred_not_commute_pred(i1 %c, i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @icmp_common_pred_not_commute_pred(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 [[Z:%.*]], [[X]]
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[CMP1]], i1 [[CMP2]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;