[InstCombine] Fold Select with binary op - non-commutative opcodes

[xbolva00]

Summary

Basic version was merged - https://reviews.llvm.org/D49954

This adds support for FP & non-commutative opcodes

Precommited tests: https://reviews.llvm.org/rL338727

[xbolva00]

lib/Transforms/InstCombine/InstCombineSelect.cpp

87 ↗

(On Diff #158765)

I would like to simplify it. But not sure what is prefered here. So kindly asking for advice :)

[spatel]

Let's handle this one step at a time. Please remove the FP changes. Let's make this patch only about handling the non-commutative integer binops.

Also, we should have tests for 'ne' for the non-commutative ops. Please add those as a preliminary commit if they're not already here. And add test for udiv/sdiv?

test/Transforms/InstCombine/select-binop-icmp.ll

179 ↗

(On Diff #158766)

This is not correct:
https://rise4fun.com/Alive/E5Y

460–463 ↗

(On Diff #158766)

This should have been transformed. Similarly, for the other opcodes - the matching is reversed.

[xbolva00]

• Added/fixed/updated tests (ok now?)
• Removed FP opcodes support (will be done as follow up work)

[spatel]

In D50190#1194883, @xbolva00 wrote:

• Added/fixed/updated tests (ok now?)

There aren't any positive tests for 'ne' predicates with the non-commutative opcodes?
Please at least a couple of those. You can commit all of the test changes ahead of this patch.

[spatel]

You should be able to adjust 2 lines of code to allow non-commutative ops after:
rL339439

[xbolva00]

In D50190#1195297, @spatel wrote:

You should be able to adjust 2 lines of code to allow non-commutative ops after:
rL339439

Ok, I will rebase it.

[xbolva00]

• Rebased/updated

[spatel]

In D50190#1195350, @xbolva00 wrote:

• Rebased/updated

Please rebase/update tests again. I had to revert rL339439 because it had a bug exposed by rearranging the predicates for this fold. I added/adjusted tests for that at rL339453, so should be fixed with rL339469.

[xbolva00]

• Updated

[spatel]

LGTM

llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp

static Instruction *foldSelectBinOpIdentity(SelectInst &Sel) {
   Constant *C;
   CmpInst::Predicate Pred;
   if (!match(Sel.getCondition(), m_ICmp(Pred, m_Value(X), m_Constant(C))) ||
       !ICmpInst::isEquality(Pred))
     return nullptr;
 
   // A select operand must be a binop, and the compare constant must be the
   // identity constant for that binop.
-  // TODO: Support non-commutative binops.
   bool IsEq = Pred == ICmpInst::ICMP_EQ;
   BinaryOperator *BO;
   if (!match(Sel.getOperand(IsEq ? 1 : 2), m_BinOp(BO)) ||
-      ConstantExpr::getBinOpIdentity(BO->getOpcode(), BO->getType(), false) != C)
+      ConstantExpr::getBinOpIdentity(BO->getOpcode(), BO->getType(), true) != C)
     return nullptr;
 
   // Last, match the compare variable operand with a binop operand.
   Value *Y;
+  if (!BO->isCommutative() && !match(BO, m_BinOp(m_Value(Y), m_Specific(X))))
+    return nullptr;
   if (!match(BO, m_c_BinOp(m_Value(Y), m_Specific(X))))
     return nullptr;
 
   // BO = binop Y, X
   // S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO }
   // =>
   // S = { select (cmp eq X, C),  Y, ? } or { select (cmp ne X, C), ?,  Y }
   Sel.setOperand(IsEq ? 1 : 2, Y);

llvm/trunk/test/Transforms/InstCombine/select-binop-icmp.ll

;
   %B = fdiv float %x, %z
   %C = select i1 %A, float %B, float %y
   ret float %C
 }
 
 define i32 @select_sub_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_sub_icmp(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[B:%.*]] = sub i32 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[B]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Z:%.*]], i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp eq i32 %x, 0
   %B = sub i32 %z, %x
   %C = select i1 %A, i32 %B, i32 %y
   ret i32 %C
 }
 
 define i32 @select_sub_icmp_2(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_sub_icmp_2(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @use2(i1 [[A]])
-; CHECK-NEXT:    [[B:%.*]] = sub i32 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[B]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Z:%.*]], i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp eq i32 %x, 0
   call void @use2(i1 %A)
   %B = sub i32 %z, %x
   %C = select i1 %A, i32 %B, i32 %y
   ret i32 %C
 }
 
 define i32 @select_sub_icmp_3(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_sub_icmp_3(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @use2(i1 [[A]])
-; CHECK-NEXT:    [[B:%.*]] = sub i32 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Y:%.*]], i32 [[B]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Y:%.*]], i32 [[Z:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp ne i32 %x, 0
   call void @use2(i1 %A)
   %B = sub i32 %z, %x
   %C = select i1 %A, i32 %y, i32 %B
   ret i32 %C
 }
 
 define <2 x i8> @select_sub_icmp_vec(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @select_sub_icmp_vec(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq <2 x i8> [[X:%.*]], zeroinitializer
-; CHECK-NEXT:    [[B:%.*]] = sub <2 x i8> [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select <2 x i1> [[A]], <2 x i8> [[B]], <2 x i8> [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = select <2 x i1> [[A]], <2 x i8> [[Z:%.*]], <2 x i8> [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i8> [[C]]
 ;
   %A = icmp eq <2 x i8>  %x, <i8 0, i8 0>
   %B = sub <2 x i8>  %z, %x
   %C = select <2 x i1>  %A, <2 x i8>  %B, <2 x i8>  %y
   ret <2 x i8>  %C
 }
 
 define i32 @select_shl_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_shl_icmp(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @use2(i1 [[A]])
-; CHECK-NEXT:    [[B:%.*]] = shl i32 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Y:%.*]], i32 [[B]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Y:%.*]], i32 [[Z:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp ne i32 %x, 0
   call void @use2(i1 %A) ; thwart predicate canonicalization
   %B = shl i32 %z, %x
   %C = select i1 %A, i32 %y, i32 %B
   ret i32 %C
 }
 
 define i32 @select_lshr_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_lshr_icmp(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[B:%.*]] = lshr i32 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[B]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Z:%.*]], i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp eq i32 %x, 0
   %B = lshr i32 %z, %x
   %C = select i1 %A, i32 %B, i32 %y
   ret i32 %C
 }
 
 define i32 @select_ashr_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_ashr_icmp(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @use2(i1 [[A]])
-; CHECK-NEXT:    [[B:%.*]] = ashr i32 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Y:%.*]], i32 [[B]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Y:%.*]], i32 [[Z:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp ne i32 %x, 0
   call void @use2(i1 %A) ; thwart predicate canonicalization
   %B = ashr i32 %z, %x
   %C = select i1 %A, i32 %y, i32 %B
   ret i32 %C
 }
 
 define i32 @select_udiv_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_udiv_icmp(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[B:%.*]] = udiv i32 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[B]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Z:%.*]], i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp eq i32 %x, 1
   %B = udiv i32 %z, %x
   %C = select i1 %A, i32 %B, i32 %y
   ret i32 %C
 }
 
 define i32 @select_sdiv_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_sdiv_icmp(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], 1
 ; CHECK-NEXT:    call void @use2(i1 [[A]])
-; CHECK-NEXT:    [[B:%.*]] = sdiv i32 [[Z:%.*]], [[X]]
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Y:%.*]], i32 [[B]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[Y:%.*]], i32 [[Z:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp ne i32 %x, 1
   call void @use2(i1 %A) ; thwart predicate canonicalization
   %B = sdiv i32 %z, %x
   %C = select i1 %A, i32 %y, i32 %B
   ret i32 %C
 }