[InstSimplify] Fold another Select with And/Or pattern

[xbolva00]

Summary

Proof: https://rise4fun.com/Alive/L5J

[xbolva00]

• More tests

[xbolva00]

Any test missing? If ok, I will precommit them.

[spatel]

In D49975#1180337, @xbolva00 wrote:

Any test missing? If ok, I will precommit them.

Tests look good; precommit.

The code logic seems unnecessarily complicated with all of these commuted matches. It would probably be easier to read and shorter if you match a binop with icmp operands and capture all 4 of those operands. Then, make sure the predicates match and make sure there's a common operand from the 4 captured icmp values.

[xbolva00]

• Rebased

I will change the code logic tomorrow.

[xbolva00]

• Updated code logic

[spatel]

lib/Analysis/InstructionSimplify.cpp

100 ↗

(On Diff #158180)

I think the logic is correct, but this is confusing variable naming because it doesn't match the code comments above. Just call these *X, *Y?

103 ↗

(On Diff #158180)

This does not need to be a commutative matcher?

[xbolva00]

• Fixed review notes

[spatel]

LGTM with 1 more comment fix.

lib/Analysis/InstructionSimplify.cpp

68–82 ↗

(On Diff #158227)

The comment still doesn't match the code. Might as well move this next to the match statement inside the function in case there are other folds possible here:

%A = icmp eq %TV, %FV
%B = icmp eq %X, %Y (and one of these is a select operand)
%C = and %A, %B
%D = select %C, %TV, %FV
-->
%FV

%A = icmp ne %TV, %FV
%B = icmp ne %X, %Y (and one of these is a select operand)
%C = or %A, %B
%D = select %C, %TV, %FV
-->
%TV

[xbolva00]

• Comment fix

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                                const SimplifyQuery &Q, unsigned MaxRecurse);
 static Value *SimplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
 static Value *SimplifyXorInst(Value *, Value *, const SimplifyQuery &, unsigned);
 static Value *SimplifyCastInst(unsigned, Value *, Type *,
                                const SimplifyQuery &, unsigned);
 static Value *SimplifyGEPInst(Type *, ArrayRef<Value *>, const SimplifyQuery &,
                               unsigned);
 
-/// Fold
-///   %A = icmp ne/eq i8 %X, %V1
-///   %B = icmp ne/eq i8 %X, %V2
-///   %C = or/and i1 %A, %B
-///   %D = select i1 %C, i8 %X, i8 %V1
-/// To
-///   %X/%V1
 static Value *foldSelectWithBinaryOp(Value *Cond, Value *TrueVal,
                                      Value *FalseVal) {
   BinaryOperator::BinaryOps BinOpCode;
   if (auto *BO = dyn_cast<BinaryOperator>(Cond))
     BinOpCode = BO->getOpcode();
   else
     return nullptr;
 
-  CmpInst::Predicate ExpectedPred;
+  CmpInst::Predicate ExpectedPred, Pred1, Pred2;
   if (BinOpCode == BinaryOperator::Or) {
     ExpectedPred = ICmpInst::ICMP_NE;
   } else if (BinOpCode == BinaryOperator::And) {
     ExpectedPred = ICmpInst::ICMP_EQ;
   } else
     return nullptr;
 
-  CmpInst::Predicate Pred1, Pred2;
-  if (!match(
-          Cond,
-          m_c_BinOp(m_c_ICmp(Pred1, m_Specific(TrueVal), m_Specific(FalseVal)),
-                    m_c_ICmp(Pred2, m_Specific(TrueVal), m_Value()))) ||
+  // %A = icmp eq %TV, %FV
+  // %B = icmp eq %X, %Y (and one of these is a select operand)
+  // %C = and %A, %B
+  // %D = select %C, %TV, %FV
+  // -->
+  // %FV
+
+  // %A = icmp ne %TV, %FV
+  // %B = icmp ne %X, %Y (and one of these is a select operand)
+  // %C = or %A, %B
+  // %D = select %C, %TV, %FV
+  // -->
+  // %TV
+  Value *X, *Y;
+  if (!match(Cond, m_c_BinOp(m_c_ICmp(Pred1, m_Specific(TrueVal),
+                                      m_Specific(FalseVal)),
+                             m_ICmp(Pred2, m_Value(X), m_Value(Y)))) ||
       Pred1 != Pred2 || Pred1 != ExpectedPred)
     return nullptr;
 
+  if (X == TrueVal || X == FalseVal || Y == TrueVal || Y == FalseVal)
     return BinOpCode == BinaryOperator::Or ? TrueVal : FalseVal;
+
+  return nullptr;
 }
 
 /// For a boolean type or a vector of boolean type, return false or a vector
 /// with every element false.
 static Constant *getFalse(Type *Ty) {
   return ConstantInt::getFalse(Ty);
 }
 

llvm/trunk/test/Transforms/InstSimplify/select-and-cmp.ll

;
   %B = icmp eq i32 %y, %z
   %C = and i1 %A, %B
   %D = select i1 %C, i32 %z, i32 %y
   ret i32 %D
 }
 
 define i32 @select_and_icmp_alt(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_icmp_alt(
-; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp eq i32 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[A]], [[B]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Z:%.*]]
 ;
   %A = icmp eq i32 %x, %z
   %B = icmp eq i32 %y, %z
   %C = and i1 %A, %B
   %D = select i1 %C, i32 %x, i32 %z
   ret i32 %D
 }
 
 define i32 @select_and_icmp_alt2(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_icmp_alt2(
-; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp eq i32 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[A]], [[B]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[Y]], i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Z:%.*]]
 ;
   %A = icmp eq i32 %x, %z
   %B = icmp eq i32 %y, %z
   %C = and i1 %A, %B
   %D = select i1 %C, i32 %y, i32 %z
   ret i32 %D
 }
 
 define i32 @select_and_icmp_inv_alt(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_icmp_inv_alt(
-; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[Z:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp eq i32 [[Z]], [[Y:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[A]], [[B]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Z:%.*]]
 ;
   %A = icmp eq i32 %z, %x
   %B = icmp eq i32 %z, %y
   %C = and i1 %A, %B
   %D = select i1 %C, i32 %x, i32 %z
   ret i32 %D
 }
 
 define i32 @select_and_inv_icmp_alt(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_inv_icmp_alt(
-; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp eq i32 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[B]], [[A]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Z:%.*]]
 ;
   %A = icmp eq i32 %x, %z
   %B = icmp eq i32 %y, %z
   %C = and i1 %B, %A
   %D = select i1 %C, i32 %x, i32 %z
   ret i32 %D
 }
 
 define i32 @select_and_inv_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_inv_icmp(
 ; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %A = icmp eq i32 %x, %z
   %B = icmp eq i32 %y, %z
   %C = and i1 %B , %A
   %D = select i1 %C, i32 %z, i32 %x
   ret i32 %D
 }
 
 define <2 x i8> @select_and_icmp_alt_vec(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @select_and_icmp_alt_vec(
-; CHECK-NEXT:    [[A:%.*]] = icmp eq <2 x i8> [[X:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp eq <2 x i8> [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[C:%.*]] = and <2 x i1> [[A]], [[B]]
-; CHECK-NEXT:    [[D:%.*]] = select <2 x i1> [[C]], <2 x i8> [[X]], <2 x i8> [[Z]]
-; CHECK-NEXT:    ret <2 x i8> [[D]]
+; CHECK-NEXT:    ret <2 x i8> [[Z:%.*]]
 ;
   %A = icmp eq <2 x i8> %x, %z
   %B = icmp eq <2 x i8> %y, %z
   %C = and <2 x i1> %A, %B
   %D = select <2 x i1> %C, <2 x i8> %x, <2 x i8> %z
   ret <2 x i8> %D
 }
 

llvm/trunk/test/Transforms/InstSimplify/select-or-cmp.ll

;
   %B = icmp ne i32 %y, %z
   %C = or i1 %A, %B
   %D = select i1 %C, i32 %z, i32 %y
   ret i32 %D
 }
 
 define i32 @select_or_icmp_alt(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_or_icmp_alt(
-; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp ne i32 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[A]], [[B]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %A = icmp ne i32 %x, %z
   %B = icmp ne i32 %y, %z
   %C = or i1 %A, %B
   %D = select i1 %C, i32 %x, i32 %z
   ret i32 %D
 }
 
 define i32 @select_or_icmp_alt2(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_or_icmp_alt2(
-; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp ne i32 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[A]], [[B]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[Y]], i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Y:%.*]]
 ;
   %A = icmp ne i32 %x, %z
   %B = icmp ne i32 %y, %z
   %C = or i1 %A, %B
   %D = select i1 %C, i32 %y, i32 %z
   ret i32 %D
 }
 
 define i32 @select_or_icmp_inv_alt(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_or_icmp_inv_alt(
-; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[Z:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp ne i32 [[Z]], [[Y:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[A]], [[B]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %A = icmp ne i32 %z, %x
   %B = icmp ne i32 %z, %y
   %C = or i1 %A, %B
   %D = select i1 %C, i32 %x, i32 %z
   ret i32 %D
 }
 
 define i32 @select_or_inv_icmp_alt(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_or_inv_icmp_alt(
-; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[Z:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp ne i32 [[Z]], [[Y:%.*]]
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[B]], [[A]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %A = icmp ne i32 %z, %x
   %B = icmp ne i32 %z, %y
   %C = or i1 %B, %A
   %D = select i1 %C, i32 %x, i32 %z
   ret i32 %D
 }
 
 define <2 x i8> @select_or_icmp_alt_vec(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @select_or_icmp_alt_vec(
-; CHECK-NEXT:    [[A:%.*]] = icmp ne <2 x i8> [[X:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp ne <2 x i8> [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[C:%.*]] = or <2 x i1> [[A]], [[B]]
-; CHECK-NEXT:    [[D:%.*]] = select <2 x i1> [[C]], <2 x i8> [[X]], <2 x i8> [[Z]]
-; CHECK-NEXT:    ret <2 x i8> [[D]]
+; CHECK-NEXT:    ret <2 x i8> [[X:%.*]]
 ;
   %A = icmp ne <2 x i8> %x, %z
   %B = icmp ne <2 x i8> %y, %z
   %C = or <2 x i1> %A, %B
   %D = select <2 x i1> %C, <2 x i8> %x, <2 x i8> %z
   ret <2 x i8> %D
 }