[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

84

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

238

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

610–643

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

lib/Transforms/InstCombine/InstCombineSelect.cpp

 
 /// Fold
 ///   %A = icmp eq/ne i8 %x, 0
 ///   %B = op i8 %x, %z
 ///   %C = select i1 %A, i8 %B, i8 %y
 /// To
 ///   %C = select i1 %A, i8 %z, i8 %y
 /// OP: binop with an identity constant
-/// TODO: support for non-commutative and FP opcodes
+/// TODO: support for undefs and FP opcodes
 static Instruction *foldSelectBinOpIdentity(SelectInst &Sel) {
-
   Value *Cond = Sel.getCondition();
   Value *X, *Z;
   Constant *C;
   CmpInst::Predicate Pred;
-  if (!match(Cond, m_ICmp(Pred, m_Value(X), m_Constant(C))) ||
+  if (!match(Cond, m_Cmp(Pred, m_Value(X), m_Constant(C))) ||
       !ICmpInst::isEquality(Pred))
     return nullptr;
 
   bool IsEq = Pred == ICmpInst::ICMP_EQ;
   auto *BO =
       dyn_cast<BinaryOperator>(IsEq ? Sel.getTrueValue() : Sel.getFalseValue());
-  // TODO: support for undefs
-  if (BO && match(BO, m_c_BinOp(m_Specific(X), m_Value(Z))) &&
+  if (!BO)
+    return nullptr;
+
+  if (match(BO, m_c_BinOp(m_Specific(X), m_Value(Z))) &&
       ConstantExpr::getBinOpIdentity(BO->getOpcode(), X->getType()) == C) {
     Sel.setOperand(IsEq ? 1 : 2, Z);
     return &Sel;
+  } else if (match(BO, m_BinOp(m_Value(Z), m_Specific(X))) &&
+             ConstantExpr::getBinOpIdentity(BO->getOpcode(), X->getType(),
+                                            true) == C) {
+    Sel.setOperand(IsEq ? 1 : 2, Z);
+    return &Sel;
   }
   return nullptr;
 }
 
 /// This folds:
 ///  select (icmp eq (and X, C1)), TC, FC
 ///    iff C1 is a power 2 and the difference between TC and FC is a power-of-2.
 /// To something like:

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 eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[B:%.*]] = shl 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 = shl i32 %z, %x
   %C = select i1 %A, i32 %B, i32 %y
   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 eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[B:%.*]] = ashr 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 = ashr i32 %z, %x
   %C = select i1 %A, i32 %B, i32 %y
   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 eq i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[B:%.*]] = sdiv 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 = sdiv i32 %z, %x
   %C = select i1 %A, i32 %B, i32 %y
   ret i32 %C
 }
 

 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[B]], i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp eq i32 %x, 0
   %B = sub i32 %x, %z
   %C = select i1 %A, i32 %B, i32 %y
   ret i32 %C
 }
 
 define i32 @select_sub_icmp_bad_2(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_sub_icmp_bad_2(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[B:%.*]] = sub i32 [[Z:%.*]], [[X]]
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[A]], i32 [[B]], i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = icmp eq i32 %x, 1
   %B = sub i32 %z, %x
   %C = select i1 %A, i32 %B, i32 %y
   ret i32 %C
 }
 
 define i32 @select_sub_icmp_bad_3(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_sub_icmp_bad_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 [[B]], i32 [[Y:%.*]]
 ; 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 %B, i32 %y
   ret i32 %C
 }
 
 define i32 @select_sub_icmp_4(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_sub_icmp_4(
 ; 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 [[B]], i32 [[Y:%.*]]
 ; 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 %B, i32 %y
   ret i32 %C