[InstCombine] Fold two select patterns into or-and

[dtcxzyw]

Summary

This patch is the follow-up improvement of D122152.
Fixes https://github.com/llvm/llvm-project/issues/64558.

select (a | c), a, b -> select a, true, (select ~c, b, false) where c is free to invert
select (c & ~b), a, b -> select b, true, (select c, a, false)
Alive2: https://alive2.llvm.org/ce/z/KwxtMA

[nikic]

The correct transforms are these: https://alive2.llvm.org/ce/z/K8cuab

[dtcxzyw]

Fix the transformation.

I will fix D122152 in a separate patch.

[nikic]

llvm/test/Transforms/InstCombine/select-and-or.ll

629

noundef on b seems irrelevant, did you mean to put it on a?

653

Drop noundef from these tests and call them _multiuse.

697

Is this supposed to be a commuted test? If so, put it next to the original test and make it _commuted.

711

Something is wrong with these negative tests. You have an unused variable %a.

[dtcxzyw]

llvm/test/Transforms/InstCombine/select-and-or.ll

629

These tests are based on and_or* series above.

[dtcxzyw]

Cleanup tests.

[dtcxzyw]

llvm/test/Transforms/InstCombine/select-and-or.ll

697

I don't think commuted tests are necessary.

[nikic]

llvm/test/Transforms/InstCombine/select-and-or.ll

682

Swap the operand of the or here to cover the commuted case.

711

We do still need negative tests where the not operand is not the same as the other select operand. The previous test had the right idea, it just didn't use the correct variables. It should be something like this:

define i1 @or_and1_wrong_operand(i1 %a, i1 %b, i1 %c, i1 %c) {
  %notb = xor i1 %b, true
  %cond = and i1 %notb, %c
  %r = select i1 %cond, i1 %a, i1 %d
  ret i1 %r
}

And similar for the other case.

[dtcxzyw]

Add commuted tests and negative tests.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

3093

Instead of matching m_Not imo should match m_Specific and then check isFreeToInvert and generate CreateNot if that is the case.

[nikic]

This looks reasonable to me, can you pleas precommit the tests?

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

3093

I don't get what you're suggesting here. isFreeToInvert doesn't tell you how inverted values are related, which is important here. (We need ~b and b, just being invertible is not enough.)

[dtcxzyw]

Rebase.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

3093

err doesn't work for the FalseVal one, but for the true case you can do:
match(CondVal, m_c_Or(m_Specific(TrueVal), m_Value(C)) && CondVal->hasOneUse() && IsFreeToInvert(C) { C = Builder.CreateNot(C); ...}. That gets more patterns.

[nikic]

FYI I slightly adjusted the test coverage in https://github.com/llvm/llvm-project/commit/5f9b4bc293c26d93c9115c5fbe99ddc4e5fab6da to make sure the operand order is right.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

3093

Thanks, I get what you mean now. That should indeed work for the first case.

[dtcxzyw]

• Rebase
• Fold select (a | c), a, b -> select a, true, (select ~c, b, false) where c is free to invert.
• Add more tests for the generalized transform

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (match(CondVal, m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))) &&
     return BinaryOperator::CreateAnd(TrueVal, Builder.CreateOr(C, FalseVal));
   }
   // select (~c & b), a, b -> and b, (or freeze(a), c)
   if (match(CondVal, m_c_And(m_Not(m_Value(C)), m_Specific(FalseVal))) &&
       CondVal->hasOneUse()) {
     TrueVal = Builder.CreateFreeze(TrueVal);
     return BinaryOperator::CreateAnd(FalseVal, Builder.CreateOr(C, TrueVal));
   }
+  // select (a | c), a, b -> select a, true, (select ~c, b, false)
+  if (match(CondVal, m_c_Or(m_Specific(TrueVal), m_Value(C))) &&
+      CondVal->hasOneUse() && isFreeToInvert(C, C->hasOneUse())) {
+    Value *NotC = Builder.CreateNot(C);
+    Value *AndV = Builder.CreateSelect(NotC, FalseVal, Zero);
+    return SelectInst::Create(TrueVal, One, AndV);
+  }
+  // select (c & ~b), a, b -> select b, true, (select c, a, false)
+  if (match(CondVal, m_c_And(m_Value(C), m_Not(m_Specific(FalseVal)))) &&
+      CondVal->hasOneUse()) {
+    Value *AndV = Builder.CreateSelect(C, TrueVal, Zero);
+    return SelectInst::Create(FalseVal, One, AndV);
+  }
 
   if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
     Use *Y = nullptr;
     bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
     Value *Op1 = IsAnd ? TrueVal : FalseVal;
     if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
       auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
       InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));

llvm/test/Transforms/InstCombine/select-and-or.ll

;
   %nota = xor <2 x i1> %a, <i1 true, i1 true>
   %cond = or <2 x i1> %c, %nota
   %r = select <2 x i1> %cond, <2 x i1> %a, <2 x i1> %b
   ret <2 x i1> %r
 }
 
 define i1 @or_and1(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @or_and1(
-; CHECK-NEXT:    [[NOTB:%.*]] = xor i1 [[B:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = and i1 [[NOTB]], [[C:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A:%.*]], i1 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i1 [[A:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notb = xor i1 %b, true
   %cond = and i1 %notb, %c
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
 define i1 @or_and2(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @or_and2(
-; CHECK-NEXT:    [[NOTC:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = or i1 [[NOTC]], [[A:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A]], i1 [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notc = xor i1 %c, true
   %cond = or i1 %notc, %a
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
-define i1 @or_and1_commuted(i1 %a, i1 %b) {
+define i1 @or_and1_commuted(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @or_and1_commuted(
-; CHECK-NEXT:    [[C:%.*]] = call i1 @gen_i1()
-; CHECK-NEXT:    [[NOTB:%.*]] = xor i1 [[B:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = and i1 [[C]], [[NOTB]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A:%.*]], i1 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i1 [[A:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
-  %c = call i1 @gen_i1()
   %notb = xor i1 %b, true
   %cond = and i1 %c, %notb
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
-define i1 @or_and2_commuted(i1 %b, i1 %c) {
+define i1 @or_and2_commuted(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @or_and2_commuted(
-; CHECK-NEXT:    [[A:%.*]] = call i1 @gen_i1()
-; CHECK-NEXT:    [[NOTC:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = or i1 [[A]], [[NOTC]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A]], i1 [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
-  %a = call i1 @gen_i1()
   %notc = xor i1 %c, true
   %cond = or i1 %a, %notc
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
 define i1 @or_and1_multiuse(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @or_and1_multiuse(
 ; CHECK-NEXT:    [[NOTB:%.*]] = xor i1 [[B:%.*]], true
 ; CHECK-NEXT:    [[COND:%.*]] = and i1 [[NOTB]], [[C:%.*]]
 ; CHECK-NEXT:    call void @use(i1 [[COND]])
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A:%.*]], i1 [[B]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notb = xor i1 %b, true

 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notc = xor i1 %c, true
   %cond = or i1 %notc, %a
   call void @use(i1 %cond)
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
-define <2 x i1> @or_and1_vec(<2 x i1> %a, <2 x i1> %b, <2 x i1> %c) {
+define <2 x i1> @or_and1_vec(<2 x i1> %a, <2 x i1> %b) {
 ; CHECK-LABEL: @or_and1_vec(
-; CHECK-NEXT:    [[NOTB:%.*]] = xor <2 x i1> [[B:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[COND:%.*]] = and <2 x i1> [[NOTB]], [[C:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[COND]], <2 x i1> [[A:%.*]], <2 x i1> [[B]]
+; CHECK-NEXT:    [[C:%.*]] = call <2 x i1> @gen_v2i1()
+; CHECK-NEXT:    [[TMP1:%.*]] = select <2 x i1> [[C]], <2 x i1> [[A:%.*]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[B:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
+  %c = call <2 x i1> @gen_v2i1()
   %notb = xor <2 x i1> %b, <i1 true, i1 true>
-  %cond = and <2 x i1> %notb, %c
+  %cond = and <2 x i1> %c, %notb
   %r = select <2 x i1> %cond, <2 x i1> %a, <2 x i1> %b
   ret <2 x i1> %r
 }
 
-define <2 x i1> @or_and2_vec(<2 x i1> %a, <2 x i1> %b, <2 x i1> %c) {
+define <2 x i1> @or_and2_vec(<2 x i1> %a, <2 x i1> %b) {
 ; CHECK-LABEL: @or_and2_vec(
-; CHECK-NEXT:    [[NOTC:%.*]] = xor <2 x i1> [[C:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[COND:%.*]] = or <2 x i1> [[NOTC]], [[A:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[COND]], <2 x i1> [[A]], <2 x i1> [[B:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = call <2 x i1> @gen_v2i1()
+; CHECK-NEXT:    [[TMP1:%.*]] = select <2 x i1> [[C]], <2 x i1> [[B:%.*]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[A:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
+  %c = call <2 x i1> @gen_v2i1()
   %notc = xor <2 x i1> %c, <i1 true, i1 true>
-  %cond = or <2 x i1> %notc, %a
+  %cond = or <2 x i1> %a, %notc
   %r = select <2 x i1> %cond, <2 x i1> %a, <2 x i1> %b
   ret <2 x i1> %r
 }
 
 define <2 x i1> @or_and1_vec_commuted(<2 x i1> %a, <2 x i1> %b) {
 ; CHECK-LABEL: @or_and1_vec_commuted(
 ; CHECK-NEXT:    [[C:%.*]] = call <2 x i1> @gen_v2i1()
-; CHECK-NEXT:    [[NOTB:%.*]] = xor <2 x i1> [[B:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[COND:%.*]] = and <2 x i1> [[C]], [[NOTB]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[COND]], <2 x i1> [[A:%.*]], <2 x i1> [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select <2 x i1> [[C]], <2 x i1> [[A:%.*]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[B:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %c = call <2 x i1> @gen_v2i1()
   %notb = xor <2 x i1> %b, <i1 true, i1 true>
-  %cond = and <2 x i1> %c, %notb
+  %cond = and <2 x i1> %notb, %c
   %r = select <2 x i1> %cond, <2 x i1> %a, <2 x i1> %b
   ret <2 x i1> %r
 }
 
-define <2 x i1> @or_and2_vec_commuted(<2 x i1> %b, <2 x i1> %c) {
+define <2 x i1> @or_and2_vec_commuted(<2 x i1> %a, <2 x i1> %b) {
 ; CHECK-LABEL: @or_and2_vec_commuted(
-; CHECK-NEXT:    [[A:%.*]] = call <2 x i1> @gen_v2i1()
-; CHECK-NEXT:    [[NOTC:%.*]] = xor <2 x i1> [[C:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[COND:%.*]] = or <2 x i1> [[A]], [[NOTC]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[COND]], <2 x i1> [[A]], <2 x i1> [[B:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = call <2 x i1> @gen_v2i1()
+; CHECK-NEXT:    [[TMP1:%.*]] = select <2 x i1> [[C]], <2 x i1> [[B:%.*]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[A:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
-  %a = call <2 x i1> @gen_v2i1()
+  %c = call <2 x i1> @gen_v2i1()
   %notc = xor <2 x i1> %c, <i1 true, i1 true>
-  %cond = or <2 x i1> %a, %notc
+  %cond = or <2 x i1> %notc, %a
   %r = select <2 x i1> %cond, <2 x i1> %a, <2 x i1> %b
   ret <2 x i1> %r
 }
 
 define i1 @or_and1_wrong_operand(i1 %a, i1 %b, i1 %c, i1 %d) {
 ; CHECK-LABEL: @or_and1_wrong_operand(
 ; CHECK-NEXT:    [[NOTB:%.*]] = xor i1 [[B:%.*]], true
 ; CHECK-NEXT:    [[COND:%.*]] = and i1 [[NOTB]], [[C:%.*]]
;
   %cond = or i1 %a, %notc
   %r = select i1 %cond, i1 %d, i1 %b
   ret i1 %r
 }
 
 define i1 @pr64558(i1 noundef %a, i1 noundef %b) {
 ; CHECK-LABEL: @pr64558(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[LNOT:%.*]] = xor i1 [[B:%.*]], true
-; CHECK-NEXT:    [[AND11:%.*]] = and i1 [[LNOT]], [[A:%.*]]
-; CHECK-NEXT:    [[COND_V:%.*]] = select i1 [[AND11]], i1 [[A]], i1 [[B]]
+; CHECK-NEXT:    [[COND_V:%.*]] = or i1 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[COND_V]]
 ;
 entry:
   %lnot = xor i1 %b, true
   %and11 = and i1 %lnot, %a
   %cond.v = select i1 %and11, i1 %a, i1 %b
   ret i1 %cond.v
 }
+
+define i1 @or_and3(i1 %a, i1 %b, i32 %x, i32 %y) {
+; CHECK-LABEL: @or_and3(
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[TMP1]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %c = icmp eq i32 %x, %y
+  %cond = or i1 %a, %c
+  %r = select i1 %cond, i1 %a, i1 %b
+  ret i1 %r
+}
+
+define i1 @or_and3_commuted(i1 %a, i1 %b, i32 %x, i32 %y) {
+; CHECK-LABEL: @or_and3_commuted(
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[TMP1]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %c = icmp eq i32 %x, %y
+  %cond = or i1 %c, %a
+  %r = select i1 %cond, i1 %a, i1 %b
+  ret i1 %r
+}
+
+define i1 @or_and3_not_free_to_invert(i1 %a, i1 %b, i1 %c) {
+; CHECK-LABEL: @or_and3_not_free_to_invert(
+; CHECK-NEXT:    [[COND:%.*]] = or i1 [[A:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A]], i1 [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %cond = or i1 %a, %c
+  %r = select i1 %cond, i1 %a, i1 %b
+  ret i1 %r
+}
+
+define i1 @or_and3_multiuse(i1 %a, i1 %b, i32 %x, i32 %y) {
+; CHECK-LABEL: @or_and3_multiuse(
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[COND:%.*]] = or i1 [[C]], [[A:%.*]]
+; CHECK-NEXT:    call void @use(i1 [[COND]])
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A]], i1 [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %c = icmp eq i32 %x, %y
+  %cond = or i1 %a, %c
+  call void @use(i1 %cond)
+  %r = select i1 %cond, i1 %a, i1 %b
+  ret i1 %r
+}
+
+define <2 x i1> @or_and3_vec(<2 x i1> %a, <2 x i1> %b, <2 x i32> %x, <2 x i32> %y) {
+; CHECK-LABEL: @or_and3_vec(
+; CHECK-NEXT:    [[C:%.*]] = icmp ne <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select <2 x i1> [[C]], <2 x i1> [[B:%.*]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[A:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[TMP1]]
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %c = icmp eq <2 x i32> %x, %y
+  %cond = or <2 x i1> %a, %c
+  %r = select <2 x i1> %cond, <2 x i1> %a, <2 x i1> %b
+  ret <2 x i1> %r
+}
+
+define <2 x i1> @or_and3_vec_commuted(<2 x i1> %a, <2 x i1> %b, <2 x i32> %x, <2 x i32> %y) {
+; CHECK-LABEL: @or_and3_vec_commuted(
+; CHECK-NEXT:    [[C:%.*]] = icmp ne <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select <2 x i1> [[C]], <2 x i1> [[B:%.*]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[A:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[TMP1]]
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %c = icmp eq <2 x i32> %x, %y
+  %cond = or <2 x i1> %c, %a
+  %r = select <2 x i1> %cond, <2 x i1> %a, <2 x i1> %b
+  ret <2 x i1> %r
+}
+
+define i1 @or_and3_wrong_operand(i1 %a, i1 %b, i32 %x, i32 %y, i1 %d) {
+; CHECK-LABEL: @or_and3_wrong_operand(
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[COND:%.*]] = or i1 [[C]], [[A:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[D:%.*]], i1 [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %c = icmp eq i32 %x, %y
+  %cond = or i1 %a, %c
+  %r = select i1 %cond, i1 %d, i1 %b
+  ret i1 %r
+}