[InstCombine] Fold Select with AND/OR condition

[xbolva00]

Summary

Fold

%A = icmp ne i8 %X, %V1
%B = icmp ne i8 %X, %V2
%C = or i1 %A, %B
%D = select i1 %C, i8 %X, i8 %V1
ret i8 %D
  =>
ret i8 %X

Fixes https://bugs.llvm.org/show_bug.cgi?id=38334
Proof: https://rise4fun.com/Alive/plI8

[lebedev.ri]

This should be in InstSimplify, as you don't create any new instructions.

[craig.topper]

There should be an opposite version with and instead of or and the compare condition inverted. We should handle that too.

[xbolva00]

Ok, I will look on it.

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineSelect.cpp

65–87 ↗

(On Diff #157701)

One more thing - this is slightly too verbose. I suspect it may miss some commutative cases, too.
Please make better use of pattern matchers.

How about:

Value *foldSelectInstBinaryOp(SelectInst &Sel) {
  Value *X, *V1, *V2;
  CmpInst::Predicate Pred1, Pred2;
  if (!match(&Sel, m_Select(m_c_Or(m_ICmp(Pred1, m_Value(X), m_Value(V1)),
                                   m_c_ICmp(Pred2, m_Deferred(X), m_Value(V2))),
                            m_Deferred(X), m_Deferred(V1))) ||
      !(Pred1 == Pred2 && Pred1 == ICmpInst::ICMP_NE))
    return nullptr;
  return X;
}

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineSelect.cpp

65–87 ↗

(On Diff #157701)

Actually, you won't even need V2 right now, i think, so,

static Value *foldSelectInstBinaryOp(SelectInst &Sel) {
  Value *X, *V1;
  CmpInst::Predicate Pred1, Pred2;
  if (!match(&Sel, m_Select(m_c_Or(m_ICmp(Pred1, m_Value(X), m_Value(V1)),
                                   m_c_ICmp(Pred2, m_Deferred(X), m_Value())),
                            m_Deferred(X), m_Deferred(V1))) ||
      !(Pred1 == Pred2 && Pred1 == ICmpInst::ICMP_NE))
    return nullptr;
  return X;
}

[xbolva00]

lib/Transforms/InstCombine/InstCombineSelect.cpp

65–87 ↗

(On Diff #157701)

Wow, nice simplification :) Thanks

[xbolva00]

• Added AND variant
• Addressed review comments

[xbolva00]

Can we handle even more cases? Any ideas how to easily extend this patch to handle them?
https://godbolt.org/g/kKhQ3s

Nevermind, maybe for now TODO. Let's do this simple case.

[lebedev.ri]

lib/Analysis/InstructionSimplify.cpp

78–93 ↗

(On Diff #157709)

Nice.
Then i'd suggest something a bit more flatter:

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;
  if (BinOpCode == BinaryOperator::Or) {
    ExpectedPred = ICmpInst::ICMP_NE;
  } else if (BinOpCode == BinaryOperator::And) {
    ExpectedPred = ICmpInst::ICMP_EQ;
    std::swap(TrueVal, FalseVal);
  } 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()))) ||
      Pred1 != Pred2 || Pred1 != ExpectedPred)
    return nullptr;

  return TrueVal;
}

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

56 ↗

(On Diff #157709)

Please split this into two different test case files, i.e. the tests for and variant should go into the new file.

[xbolva00]

• Improved matching

[lebedev.ri]

In general, looks ok, but i would like to see better test coverage
(the both test files should be identical other than or vs. and and ne vs. eq)

1. A positive test with <2 x i32> vector
2. Negative tests:
   • wrong (opposite) predicate (one and/or both, i.e. ideally 3 tests?)
   • Some other TrueVal of the select - a some new argument %k
   • Some other FalseVal of the select - a some new argument %k

lib/Analysis/InstructionSimplify.cpp

102–106 ↗

(On Diff #157725)

Hmm, ok, i think that would work too. https://rise4fun.com/Alive/wYX
But maybe

return BinOpCode == BinaryOperator::Or ? TrueVal : FalseVal;

to not anyone else wonder about this being done after the match.

[lebedev.ri]

In D49919#1178631, @lebedev.ri wrote:

2. Negative tests:

+

• wrong (opposite) binary operation - or instead of and

[lebedev.ri]

In D49919#1178644, @lebedev.ri wrote:

In D49919#1178631, @lebedev.ri wrote:

2. Negative tests:

+

• %x replaced with some other new argument in one of the icmp's

Not sure what other cases would be valuable to check against.

[xbolva00]

• Tests

replaced with some other new argument in one of the icmp's

Ok, i will do.

[xbolva00]

• Added more negative tests

[lebedev.ri]

In D49919#1178705, @xbolva00 wrote:

• Added more negative tests

Thank you.
Tests look good (i only looked at the select-and-cmp.ll, i assume the other one is fully identical/symmetrical).
Please commit the tests now, and rebase.

[lebedev.ri]

Ok, i think this looks good, other than nits.
Please wait a bit (1 day?) before committing in case others want to comment.

lib/Analysis/InstructionSimplify.cpp

68–77 ↗

(On Diff #157755)

Maybe something like

/// 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

3792 ↗

(On Diff #157755)

Can we come up with more descriptive name?
I don't have any good ideas here.

[xbolva00]

• Updated comment

[spatel]

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

2

The code was moved to instsimplify, but the tests remained in instcombine. The files should be moved, and the RUN lines should be changed to only use "-instsimplify".

[xbolva00]

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

2

Move them directly to test/Analysis? There are many inner folders - is there any folder which is more suitable for this tests?

[spatel]

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

2

instsimplify tests are under:
test/Transforms/InstSimplify

I think that's because instsimplify can be used as either an analysis or a transform pass.

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;
+  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()))) ||
+      Pred1 != Pred2 || Pred1 != ExpectedPred)
+    return nullptr;
+
+  return BinOpCode == BinaryOperator::Or ? TrueVal : FalseVal;
+}
+
 /// 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);
 }
 
 /// For a boolean type or a vector of boolean type, return true or a vector
 /// with every element true.
if (isa<UndefValue>(TrueVal))   // select ?, undef, X -> X
     return FalseVal;
   if (isa<UndefValue>(FalseVal))   // select ?, X, undef -> X
     return TrueVal;
 
   if (Value *V =
           simplifySelectWithICmpCond(Cond, TrueVal, FalseVal, Q, MaxRecurse))
     return V;
 
+  if (Value *V = foldSelectWithBinaryOp(Cond, TrueVal, FalseVal))
+    return V;
+
   return nullptr;
 }
 
 Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
                                 const SimplifyQuery &Q) {
   return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Q, RecursionLimit);
 }
 

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @select_and_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_icmp(
-; 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 [[Z]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %A = icmp eq i32 %x, %z
   %B = icmp eq i32 %y, %z
   %C = and i1 %A, %B
   %D = select i1 %C, i32 %z, i32 %x
   ret i32 %D
 }
 
 define <2 x i8> @select_and_icmp_vec(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @select_and_icmp_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> [[Z]], <2 x i8> [[X]]
-; CHECK-NEXT:    ret <2 x i8> [[D]]
+; CHECK-NEXT:    ret <2 x i8> [[X:%.*]]
 ;
   %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> %z, <2 x i8> %x
   ret <2 x i8> %D
 }
 
 define i32 @select_and_icmp2(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_icmp2(
-; 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 [[Z]], i32 [[Y]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Y:%.*]]
 ;
   %A = icmp eq i32 %x, %z
   %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_inv_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_inv_icmp(
-; 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 [[Z]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[D]]
+; 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 i32 @select_and_icmp_inv(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_and_icmp_inv(
-; 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 [[Z]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %A = icmp eq i32 %z, %x
   %B = icmp eq i32 %z, %y
   %C = and i1 %A, %B
   %D = select i1 %C, i32 %z, i32 %x
   ret i32 %D
 }
 

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @select_or_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_or_icmp(
-; 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 [[Z]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Z:%.*]]
 ;
   %A = icmp ne i32 %x, %z
   %B = icmp ne i32 %y, %z
   %C = or i1 %A, %B
   %D = select i1 %C, i32 %z, i32 %x
   ret i32 %D
 }
 
 define <2 x i8> @select_or_icmp_vec(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @select_or_icmp_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> [[Z]], <2 x i8> [[X]]
-; CHECK-NEXT:    ret <2 x i8> [[D]]
+; CHECK-NEXT:    ret <2 x i8> [[Z:%.*]]
 ;
   %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> %z, <2 x i8> %x
   ret <2 x i8> %D
 }
 
 define i32 @select_or_icmp2(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_or_icmp2(
-; 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 [[Z]], i32 [[Y]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Z:%.*]]
 ;
   %A = icmp ne i32 %x, %z
   %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_inv_icmp(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_or_inv_icmp(
-; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = icmp ne i32 [[Y:%.*]], [[Z]]
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[B]], [[A]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[Z]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Z:%.*]]
 ;
   %A = icmp ne i32 %x, %z
   %B = icmp ne i32 %y, %z
   %C = or i1 %B , %A
   %D = select i1 %C, i32 %z, i32 %x
   ret i32 %D
 }
 
 define i32 @select_or_icmp_inv(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @select_or_icmp_inv(
-; 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 [[Z]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 [[Z:%.*]]
 ;
   %A = icmp ne i32 %z, %x
   %B = icmp ne i32 %z, %y
   %C = or i1 %A, %B
   %D = select i1 %C, i32 %z, i32 %x
   ret i32 %D
 }