[InstCombine] Optimize compares with multiple selects as operands

[tejas]

Summary

In case of a comparison with two select instructions having the same
condition, check whether one of the resulting branches can be simplified.
If so, just compare the other branch and select the appropriate result.
For example:

%tmp1 = select i1 %cmp, i32 %y, i32 %x
%tmp2 = select i1 %cmp, i32 %z, i32 %x
%cmp2 = icmp slt i32 %tmp2, %tmp1

The icmp will result false for the false value of selects and the result
will depend upon the comparison of true values of selects if %cmp is
true. Thus, transform this into:

%cmp = icmp slt i32 %y, %z
%sel = select i1 %cond, i1 %cmp, i1 false

[tejas]

Updated with clang-format.

[tejas]

Hi @jdoerfert @fhahn, can you please review this case for simplifying cmp with selects? It basically folds to an appropriate result by checking both the possible values of selects.

[nikic]

I think it would be better to implement this more general transform in InstCombine: https://alive2.llvm.org/ce/z/aN8q7S In the case where the new comparison constant-folds it reduces to what you're implementing here.

[goldstein.w.n]

In D150360#4352188, @nikic wrote:

I think it would be better to implement this more general transform in InstCombine: https://alive2.llvm.org/ce/z/aN8q7S In the case where the new comparison constant-folds it reduces to what you're implementing here.

+1

[tejas]

Made the transformation generic as suggested and moved it to InstCombine.

[tejas]

Hi @nikic @goldstein.w.n , I have updated the patch just as suggested and moved it to InstCombine. Please review!
Thanks!

[nikic]

Looks pretty reasonable.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6596–6597

6600

Setting the insertion point is unnecessary.

llvm/test/Transforms/InstCombine/icmp-with-selects.ll

4

Drop the noundef and zeroext parameters.

77

Add negative tests:

1. Select conditions are not the same.
2. Neither side simplifies.

Also add multi-use tests, where one/both selects have additional uses. You'll find that you need to add some one-use checks.

[tejas]

Made specific changes to the code and removed insertion points. Added negative testcases.

[tejas]

llvm/test/Transforms/InstCombine/icmp-with-selects.ll

77

Added the negative tests. I had not added one-use checks since we are not explicitly removing the selects nor modifying them, but they do bloat up the code, so added now.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6597

There are two ways the one-use checks could be relaxed:

1. It should be fine to only require one-use on one of the selects, as we'll preserve the number of instructions in that case. I'm not entirely clear on profitability for that case -- I guess the fact that we're converting an arbitrary select into a logical and/or may make it generally beneficial?
2. If both comparisons fold, we don't care about uses at all, as the result is a constant.

I personally think it would be okay to start with the code you have, but in that case we should at least add a TODO to note the possibility.

llvm/test/Transforms/InstCombine/icmp-with-selects.ll

4

Could you please give these tests some more meaningful names, for example this could be something like @both_sides_fold.

126

For multi-use, it's customary to just do a call void @use(i32 %cond1). This is more obvious than trying to come up with a way to combine the uses.

[tejas]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6597

Can we go with relaxing the condition for one-use on one of the selects? if at least it seems beneficial at this point?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6597

Sure!

[tejas]

Relaxed the condition for one-use selects and refined the tests.

[nikic]

Thanks, the implementation looks good to me. It would be good to also add some vector tests. In particular, we should have a test where the select result is a vector, and a test where both the select condition and select result is a vector. I think your code should already correctly handle these cases.

[tejas]

Added the vector tests.

[nikic]

LGTM. Assuming you don't have commit access, which Name <email> should I use when landing?

The tests will have to be precommitted (see https://llvm.org/docs/TestingGuide.html#precommit-workflow-for-tests), but I can do that while landing.

[tejas]

Thanks for your comments and submitting the patch on my behalf! Please use Tejas Joshi <[e-mail]> for landing.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
 
   if (auto *SI = dyn_cast<SelectInst>(Op0))
     if (Instruction *NI = foldSelectICmp(I.getPredicate(), SI, Op1, I))
       return NI;
   if (auto *SI = dyn_cast<SelectInst>(Op1))
     if (Instruction *NI = foldSelectICmp(I.getSwappedPredicate(), SI, Op0, I))
       return NI;
 
+  // In case of a comparison with two select instructions having the same
+  // condition, check whether one of the resulting branches can be simplified.
+  // If so, just compare the other branch and select the appropriate result.
+  // For example:
+  //   %tmp1 = select i1 %cmp, i32 %y, i32 %x
+  //   %tmp2 = select i1 %cmp, i32 %z, i32 %x
+  //   %cmp2 = icmp slt i32 %tmp2, %tmp1
+  // The icmp will result false for the false value of selects and the result
+  // will depend upon the comparison of true values of selects if %cmp is
+  // true. Thus, transform this into:
+  //   %cmp = icmp slt i32 %y, %z
+  //   %sel = select i1 %cond, i1 %cmp, i1 false
+  // This handles similar cases to transform.
+  {
+    Value *Cond, *A, *B, *C, *D;
+    if (match(Op0, m_Select(m_Value(Cond), m_Value(A), m_Value(B))) &&
+        match(Op1, m_Select(m_Specific(Cond), m_Value(C), m_Value(D))) &&
+        (Op0->hasOneUse() || Op1->hasOneUse())) {
+      // Check whether comparison of TrueValues can be simplified
+      if (Value *Res = simplifyICmpInst(Pred, A, C, SQ)) {
+        Value *NewICMP = Builder.CreateICmp(Pred, B, D);
+        return SelectInst::Create(Cond, Res, NewICMP);
+      }
+      // Check whether comparison of FalseValues can be simplified
+      if (Value *Res = simplifyICmpInst(Pred, B, D, SQ)) {
+        Value *NewICMP = Builder.CreateICmp(Pred, A, C);
+        return SelectInst::Create(Cond, NewICMP, Res);
+      }
+    }
+  }
+
   // Try to optimize equality comparisons against alloca-based pointers.
   if (Op0->getType()->isPointerTy() && I.isEquality()) {
     assert(Op1->getType()->isPointerTy() && "Comparing pointer with non-pointer?");
     if (auto *Alloca = dyn_cast<AllocaInst>(getUnderlyingObject(Op0)))
       if (foldAllocaCmp(Alloca))
         return nullptr;
     if (auto *Alloca = dyn_cast<AllocaInst>(getUnderlyingObject(Op1)))
       if (foldAllocaCmp(Alloca))

llvm/test/Transforms/InstCombine/icmp-with-selects.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @use(i32,...)
 
 define i1 @both_sides_fold_slt(i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @both_sides_fold_slt
 ; CHECK-SAME: (i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[COND]], i32 1, i32 [[PARAM]]
-; CHECK-NEXT:    [[COND6:%.*]] = select i1 [[COND]], i32 9, i32 [[PARAM]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[COND6]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cond1 = select i1 %cond, i32 1, i32 %param
   %cond6 = select i1 %cond, i32 9, i32 %param
   %cmp = icmp slt i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define i1 @both_sides_fold_eq(i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @both_sides_fold_eq
 ; CHECK-SAME: (i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[COND]], i32 1, i32 [[PARAM]]
-; CHECK-NEXT:    [[COND6:%.*]] = select i1 [[COND]], i32 9, i32 [[PARAM]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[COND6]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    [[NOT_COND:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    ret i1 [[NOT_COND]]
 ;
 entry:
   %cond1 = select i1 %cond, i32 1, i32 %param
   %cond6 = select i1 %cond, i32 9, i32 %param
   %cmp = icmp eq i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define i1 @one_side_fold_slt(i32 %val1, i32 %val2, i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @one_side_fold_slt
 ; CHECK-SAME: (i32 [[VAL1:%.*]], i32 [[VAL2:%.*]], i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[COND]], i32 [[VAL1]], i32 [[PARAM]]
-; CHECK-NEXT:    [[COND6:%.*]] = select i1 [[COND]], i32 [[VAL2]], i32 [[PARAM]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[COND6]], [[COND1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[VAL2]], [[VAL1]]
+; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[COND]], i1 [[TMP0]], i1 false
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %cond1 = select i1 %cond, i32 %val1, i32 %param
   %cond6 = select i1 %cond, i32 %val2, i32 %param
   %cmp = icmp slt i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define i1 @one_side_fold_sgt(i32 %val1, i32 %val2, i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @one_side_fold_sgt
 ; CHECK-SAME: (i32 [[VAL1:%.*]], i32 [[VAL2:%.*]], i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[COND]], i32 [[PARAM]], i32 [[VAL1]]
-; CHECK-NEXT:    [[COND6:%.*]] = select i1 [[COND]], i32 [[PARAM]], i32 [[VAL2]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[COND6]], [[COND1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[VAL2]], [[VAL1]]
+; CHECK-NEXT:    [[NOT_COND:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[NOT_COND]], i1 [[TMP0]], i1 false
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %cond1 = select i1 %cond, i32 %param, i32 %val1
   %cond6 = select i1 %cond, i32 %param, i32 %val2
   %cmp = icmp sgt i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define i1 @one_side_fold_eq(i32 %val1, i32 %val2, i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @one_side_fold_eq
 ; CHECK-SAME: (i32 [[VAL1:%.*]], i32 [[VAL2:%.*]], i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[COND]], i32 [[VAL1]], i32 [[PARAM]]
-; CHECK-NEXT:    [[COND6:%.*]] = select i1 [[COND]], i32 [[VAL2]], i32 [[PARAM]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[COND6]], [[COND1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[VAL2]], [[VAL1]]
+; CHECK-NEXT:    [[NOT_COND:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[NOT_COND]], i1 true, i1 [[TMP0]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %cond1 = select i1 %cond, i32 %val1, i32 %param
   %cond6 = select i1 %cond, i32 %val2, i32 %param
   %cmp = icmp eq i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define i1 @no_side_fold_cond(i32 %val1, i32 %val2, i32 %param, i1 %cond1, i1 %cond2) {
 ; CHECK-LABEL: define i1 @no_side_fold_cond
 ; CHECK-SAME: (i32 [[VAL1:%.*]], i32 [[VAL2:%.*]], i32 [[PARAM:%.*]], i1 [[COND1:%.*]], i1 [[COND2:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COND3:%.*]] = select i1 [[COND1]], i32 [[VAL1]], i32 [[PARAM]]
 ; CHECK-NEXT:    [[COND6:%.*]] = select i1 [[COND2]], i32 [[VAL2]], i32 [[PARAM]]
entry:
   ret i1 %cmp
 }
 
 define i1 @one_select_mult_use(i32 %val1, i32 %val2, i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @one_select_mult_use
 ; CHECK-SAME: (i32 [[VAL1:%.*]], i32 [[VAL2:%.*]], i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[COND]], i32 [[VAL1]], i32 [[PARAM]]
-; CHECK-NEXT:    [[COND6:%.*]] = select i1 [[COND]], i32 [[VAL2]], i32 [[PARAM]]
 ; CHECK-NEXT:    call void @use(i32 [[COND1]])
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[COND6]], [[COND1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[VAL2]], [[VAL1]]
+; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[COND]], i1 [[TMP0]], i1 false
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %cond1 = select i1 %cond, i32 %val1, i32 %param
   %cond6 = select i1 %cond, i32 %val2, i32 %param
   call void @use(i32 %cond1)
   %cmp = icmp slt i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define i1 @both_select_mult_use(i32 %val1, i32 %val2, i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @both_select_mult_use
 ; CHECK-SAME: (i32 [[VAL1:%.*]], i32 [[VAL2:%.*]], i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[COND]], i32 [[VAL1]], i32 [[PARAM]]
entry:
   %cmp = icmp slt i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define <4 x i1> @fold_vector_ops(<4 x i32> %val1, <4 x i32> %val2, <4 x i32> %param, i1 %cond) {
 ; CHECK-LABEL: define <4 x i1> @fold_vector_ops
 ; CHECK-SAME: (<4 x i32> [[VAL1:%.*]], <4 x i32> [[VAL2:%.*]], <4 x i32> [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[COND]], <4 x i32> [[VAL1]], <4 x i32> [[PARAM]]
-; CHECK-NEXT:    [[COND6:%.*]] = select i1 [[COND]], <4 x i32> [[VAL2]], <4 x i32> [[PARAM]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[COND6]], [[COND1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq <4 x i32> [[VAL2]], [[VAL1]]
+; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[COND]], <4 x i1> [[TMP0]], <4 x i1> <i1 true, i1 true, i1 true, i1 true>
 ; CHECK-NEXT:    ret <4 x i1> [[CMP]]
 ;
 entry:
   %cond1 = select i1 %cond, <4 x i32> %val1, <4 x i32> %param
   %cond6 = select i1 %cond, <4 x i32> %val2, <4 x i32> %param
   %cmp = icmp eq <4 x i32> %cond6, %cond1
   ret <4 x i1> %cmp
 }
 
 define <8 x i1> @fold_vector_cond_ops(<8 x i32> %val1, <8 x i32> %val2, <8 x i32> %param, <8 x i1> %cond) {
 ; CHECK-LABEL: define <8 x i1> @fold_vector_cond_ops
 ; CHECK-SAME: (<8 x i32> [[VAL1:%.*]], <8 x i32> [[VAL2:%.*]], <8 x i32> [[PARAM:%.*]], <8 x i1> [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND1:%.*]] = select <8 x i1> [[COND]], <8 x i32> [[VAL1]], <8 x i32> [[PARAM]]
-; CHECK-NEXT:    [[COND6:%.*]] = select <8 x i1> [[COND]], <8 x i32> [[VAL2]], <8 x i32> [[PARAM]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <8 x i32> [[COND6]], [[COND1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt <8 x i32> [[VAL2]], [[VAL1]]
+; CHECK-NEXT:    [[CMP:%.*]] = select <8 x i1> [[COND]], <8 x i1> [[TMP0]], <8 x i1> zeroinitializer
 ; CHECK-NEXT:    ret <8 x i1> [[CMP]]
 ;
 entry:
   %cond1 = select <8 x i1> %cond, <8 x i32> %val1, <8 x i32> %param
   %cond6 = select <8 x i1> %cond, <8 x i32> %val2, <8 x i32> %param
   %cmp = icmp sgt <8 x i32> %cond6, %cond1
   ret <8 x i1> %cmp
 }