[InstCombine] Fold two select patterns into and-or

[bcl5980]

Summary

select (~a | c), a, b -> and a, (or c, b) https://alive2.llvm.org/ce/z/bnDobs
select (~c & b), a, b -> and b, (or a, c) https://alive2.llvm.org/ce/z/k2jJHJ

[RKSimon]

I'm almost afraid to ask - but should we consider supporting this with freeze?

----------------------------------------
define i1 @src(i1 %a, i1 %b, i1 %c) {
  %nota = xor i1 %a, 1
  %cond = or i1 %nota, %c
  %r = select i1 %cond, i1 %a, i1 %b
  ret i1 %r
}
=>
define i1 @tgt(i1 %a, i1 %b, i1 %c) {
  %bf = freeze i1 %b
  %tmp = or i1 %bf, %c
  %r = and i1 %tmp, %a
  ret i1 %r
}
Transformation seems to be correct!


----------------------------------------
define i1 @src(i1 %a, i1 %b, i1 %c) {
  %notc = xor i1 %c, 1
  %cond = and i1 %notc, %b
  %r = select i1 %cond, i1 %a, i1 %b
  ret i1 %r
}
=>
define i1 @tgt(i1 %a, i1 %b, i1 %c) {
  %fa = freeze i1 %a
  %tmp = or i1 %c, %fa
  %r = and i1 %tmp, %b
  ret i1 %r
}
Transformation seems to be correct!

[bcl5980]

This comment was removed by bcl5980.

[bcl5980]

In D122152#3396735, @RKSimon wrote:

I'm almost afraid to ask - but should we consider supporting this with freeze?

----------------------------------------
define i1 @src(i1 %a, i1 %b, i1 %c) {
  %nota = xor i1 %a, 1
  %cond = or i1 %nota, %c
  %r = select i1 %cond, i1 %a, i1 %b
  ret i1 %r
}
=>
define i1 @tgt(i1 %a, i1 %b, i1 %c) {
  %bf = freeze i1 %b
  %tmp = or i1 %bf, %c
  %r = and i1 %tmp, %a
  ret i1 %r
}
Transformation seems to be correct!


----------------------------------------
define i1 @src(i1 %a, i1 %b, i1 %c) {
  %notc = xor i1 %c, 1
  %cond = and i1 %notc, %b
  %r = select i1 %cond, i1 %a, i1 %b
  ret i1 %r
}
=>
define i1 @tgt(i1 %a, i1 %b, i1 %c) {
  %fa = freeze i1 %a
  %tmp = or i1 %c, %fa
  %r = and i1 %tmp, %b
  ret i1 %r
}
Transformation seems to be correct!

Which way is better do you think?

// select (~a | c), a, b -> and a, (or c, b)
if (match(CondVal, m_Or(m_Not(m_Value(TrueVal)), m_Value(C))))
  return BinaryOperator::CreateAnd(
      TrueVal, Builder.CreateOr(C, Builder.CreateFreeze(FalseVal)));
// select (~c & b), a, b -> and b, (or a, c)
if (match(CondVal, m_And(m_Not(m_Value(C)), m_Value(FalseVal))))
  return BinaryOperator::CreateAnd(
      FalseVal, Builder.CreateOr(C, Builder.CreateFreeze(TrueVal)));

Or

// select (~a | c), a, b -> and a, (or c, b)
if (match(CondVal, m_Or(m_Not(m_Value(TrueVal)), m_Value(C)))) {
  if (!llvm::isGuaranteedNotToBePoison(FalseVal))
    FalseVal = Builder.CreateFreeze(FalseVal);
  return BinaryOperator::CreateAnd(TrueVal, Builder.CreateOr(C, FalseVal));
}
// select (~c & b), a, b -> and b, (or a, c)
if (match(CondVal, m_And(m_Not(m_Value(C)), m_Value(FalseVal)))) {
  if (!llvm::isGuaranteedNotToBePoison(TrueVal))
    TrueVal = Builder.CreateFreeze(TrueVal);
  return BinaryOperator::CreateAnd(FalseVal, Builder.CreateOr(C, TrueVal));
}

[bcl5980]

1. only condition value has one use will enable the optimize
2. add more tests

[spatel]

Does this fix https://github.com/llvm/llvm-project/issues/54313 ?

We need to account for the case where the 'not' is operand 1 of the other bitwise logic op. This won't happen in minimal tests because of commutation canonicalization rules, but you can add tests like this to exercise that path:

declare i1 @gen_i1()

define i1 @and_or1(i1 %a, i1 %b) {
  %c = call i1 @gen_i1()
  %nota = xor i1 %a, true
  %cond = or i1 %c, %nota
  %r = select i1 %cond, i1 %a, i1 %b
  ret i1 %r
}

[bcl5980]

In D122152#3399411, @spatel wrote:

Does this fix https://github.com/llvm/llvm-project/issues/54313 ?

We need to account for the case where the 'not' is operand 1 of the other bitwise logic op. This won't happen in minimal tests because of commutation canonicalization rules, but you can add tests like this to exercise that path:

declare i1 @gen_i1()

define i1 @and_or1(i1 %a, i1 %b) {
  %c = call i1 @gen_i1()
  %nota = xor i1 %a, true
  %cond = or i1 %c, %nota
  %r = select i1 %cond, i1 %a, i1 %b
  ret i1 %r
}

I'm trying to fix #54313. Unfortunately only this part can't fix 54313. This code can help to simplify the case to:

define dso_local noundef i1 @"?check4@@YA_N_N000@Z"(i1 noundef %0, i1 noundef %1, i1 noundef %2, i1 noundef %3) local_unnamed_addr #0 {
  %5 = or i1 %2, %3
  %6 = or i1 %5, %1
  %7 = or i1 %1, %2
  %8 = or i1 %7, %3
  %9 = xor i1 %8, %6
  %10 = and i1 %9, %0
  %11 = xor i1 %10, true
  ret i1 %11
}

We still need to implement the optimization (a or b) or c == a or (b or c)

[bcl5980]

account for the case where the 'not' is operand 1 of the other bitwise logic op

[RKSimon]

In D122152#3396833, @bcl5980 wrote:

In D122152#3396735, @RKSimon wrote:

I'm almost afraid to ask - but should we consider supporting this with freeze?

Which way is better do you think?

I'm of the opinion we should start using freeze more in general codegen - using isGuaranteedNotToBePoison is very limiting to how often the combine will ever get used.

[bcl5980]

update based on RKSimon's suggestion

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2576

Use m_c_Or and m_c_And?

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2574

add freeze to the description comment

2581

add freeze to the description comment

[RKSimon]

do we need vector test coverage?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2582–2583

Here and above - this is not the correct way to match an existing value. See m_Specific or m_Deferred.

This could crash or miscompile as written, so we need at least 2 negative tests where there is no repeated value from the select T/F in the condition to make sure the pattern matching is not broken.

[bcl5980]

Thanks for spatel's suggestion, use m_Specific to match existing value and add 2 neg tests.
Thanks for nikic's suggestion, use m_c_And/m_c_Or

[bcl5980]

In D122152#3399935, @RKSimon wrote:

do we need vector test coverage?

In this pattern, one of the true/false value comes from condition, so it should be always i1 I think.

[spatel]

I think the tests are still insufficient to provide coverage for the proposed code.

To make it easier to see the diffs, I pushed the current tests with baseline CHECK lines here:
7cc48026bd75

Please rebase and update here, so we will show the differences in the tests.

As mentioned earlier, we should have at least one test with vector types. It could look like this:

define <2 x i1> @and_or1_op1not_vec(<2 x i1> %a, <2 x i1> %b) {
  %c = call <2 x i1> @gen_v2i1()
  %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
 }

And we must test both of the commuted patterns - it could be this:

define i1 @and_or2_op1not(i1 %a, i1 %c) {
  %b = call i1 @gen_i1()
  %notc = xor i1 %c, true
  %cond = or i1 %b, %notc
  %r = select i1 %cond, i1 %a, i1 %b
  ret i1 %r
}

[bcl5980]

update vector test and pattern 2 commute test

[spatel]

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

557

This doesn't test the pattern that we want. You must use @gen_i1 or some other instruction to force the 'not' to be operand 1.

[bcl5980]

use call i1 @gen_i1() to avoid canonicalization for and_or2_op1not

[spatel]

LGTM.

It's not clear how much of 'or' bitwise logic combining we want to replicate for select-of-bools, but this seems ok for now.

Ie, if we are willing to freeze, then any select-of-bools can be converted to logic ops. If the condition is itself composed of bitwise logic with a repeated value, then there's probably some logic reduction that can happen. For example if we change the 'not' on one of the patterns here:
https://alive2.llvm.org/ce/z/BsyhPk

[bcl5980]

In D122152#3411428, @spatel wrote:

LGTM.

It's not clear how much of 'or' bitwise logic combining we want to replicate for select-of-bools, but this seems ok for now.

Ie, if we are willing to freeze, then any select-of-bools can be converted to logic ops. If the condition is itself composed of bitwise logic with a repeated value, then there's probably some logic reduction that can happen. For example if we change the 'not' on one of the patterns here:
https://alive2.llvm.org/ce/z/BsyhPk

Thanks for the finding.
i1 logic space with add is an abel group(should be ring)
and -> a * b
xor -> a + b
or -> a * b + a + b
not -> a + 1
select -> c * a + (c + 1) * b

we can use this to simiplify all select with i1 types.
for example:
condition (~a | c) - > (a + 1) * c + a + 1 + c -> a * c + c + a + 1 +c -> a * c + a + 1
select (~a | c), a, b -> (a * c + a + 1) * a + (a * c + a + 1 + 1) * b ->
a * a * c + a * a + a + a * c * b + a * b ->
a * c + a + a + a * b * c + a * b ->
a * c + a * b + a * b * c ->
a * (c + b + b * c) ->
and a, (or b, c)

I'm not sure we need to do this in code or not in the future.
@spatel Can you help me to check in the code ?
name: chenglin.bi
email: [e-mail]

[spatel]

In D122152#3411608, @bcl5980 wrote:

In D122152#3411428, @spatel wrote:

LGTM.

It's not clear how much of 'or' bitwise logic combining we want to replicate for select-of-bools, but this seems ok for now.

Ie, if we are willing to freeze, then any select-of-bools can be converted to logic ops. If the condition is itself composed of bitwise logic with a repeated value, then there's probably some logic reduction that can happen. For example if we change the 'not' on one of the patterns here:
https://alive2.llvm.org/ce/z/BsyhPk

Thanks for the finding.
i1 logic space with add is an abel group(should be ring)
and -> a * b
xor -> a + b
or -> a * b + a + b
not -> a + 1
select -> c * a + (c + 1) * b

That's an interesting way to view it.

I'm not sure we need to do this in code or not in the future.

I don't know either. If we have more motivating bugs with missed optimizations like this one, then we can try harder.

@spatel Can you help me to check in the code ?
name: chenglin.bi
email: [e-mail]

Yes - I'll commit after applying and rebuilding locally.

[bcl5980]

@nikic @RKSimon @spatel
Thanks for the review.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (SelType->isIntOrIntVectorTy(1) && !isa<Constant>(CondVal) &&
     if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
         match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))
       return replaceOperand(SI, 0, A);
     // select (select a, b, false), b, false -> select a, b, false
     if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
         match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))
       return replaceOperand(SI, 0, A);
 
+    Value *C;
+    // select (~a | c), a, b -> and a, (or c, freeze(b))
+    if (match(CondVal, m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))) &&
+        CondVal->hasOneUse()) {
+      FalseVal = Builder.CreateFreeze(FalseVal);
+      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));
+    }
+
     if (!SelType->isVectorTy()) {
       if (Value *S = simplifyWithOpReplaced(TrueVal, CondVal, One, SQ,
                                             /* AllowRefinement */ true))
         return replaceOperand(SI, 1, S);
       if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal, Zero, SQ,
                                             /* AllowRefinement */ true))
         return replaceOperand(SI, 2, S);
     }

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=instcombine < %s | FileCheck %s
 
 declare void @use(i1)
 declare i1 @gen_i1()
+declare <2 x i1> @gen_v2i1()
 
 ; Should not be converted to "and", which has different poison semantics.
 define i1 @logical_and(i1 %a, i1 %b) {
 ; CHECK-LABEL: @logical_and(
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 %b, i1 false

 ;
   %not.L = xor i1 %L, true
   %C15 = select i1 %not.L, i1 true, i1 xor (i1 and (i1 icmp eq (i16* getelementptr inbounds (i16, i16* @g2, i64 1), i16* @g1), i1 icmp ne (i16* getelementptr inbounds (i16, i16* @g2, i64 1), i16* @g1)), i1 true)
   ret i1 %C15
 }
 
 define i1 @and_or1(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @and_or1(
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = or i1 [[NOTA]], [[C:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A]], i1 [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %nota = xor i1 %a, true
   %cond = or i1 %nota, %c
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
 define i1 @and_or2(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @and_or2(
-; CHECK-NEXT:    [[NOTC:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = and i1 [[NOTC]], [[B:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A:%.*]], i1 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP2]], [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notc = xor i1 %c, true
   %cond = and i1 %notc, %b
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
 define i1 @and_or1_bundef(i1 %a, i1 noundef %b, i1 %c) {
 ; CHECK-LABEL: @and_or1_bundef(
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = or i1 [[NOTA]], [[C:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A]], i1 [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i1 [[C:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %nota = xor i1 %a, true
   %cond = or i1 %nota, %c
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
 define i1 @and_or2_aundef(i1 noundef %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @and_or2_aundef(
-; CHECK-NEXT:    [[NOTC:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = and i1 [[NOTC]], [[B:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A:%.*]], i1 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i1 [[C:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP1]], [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notc = xor i1 %c, true
   %cond = and i1 %notc, %b
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
;
   call void @use(i1 %cond)
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
 define i1 @and_or1_op1not(i1 %a, i1 %b) {
 ; CHECK-LABEL: @and_or1_op1not(
 ; CHECK-NEXT:    [[C:%.*]] = call i1 @gen_i1()
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[COND:%.*]] = or i1 [[C]], [[NOTA]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A]], i1 [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[C]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP2]], [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %c = call i1 @gen_i1()
   %nota = xor i1 %a, true
   %cond = or i1 %c, %nota
   %r = select i1 %cond, i1 %a, i1 %b
   ret i1 %r
 }
 
+define i1 @and_or2_op1not(i1 %a, i1 %c) {
+; CHECK-LABEL: @and_or2_op1not(
+; CHECK-NEXT:    [[B:%.*]] = call i1 @gen_i1()
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[B]], [[TMP2]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %b = call i1 @gen_i1()
+  %notc = xor i1 %c, true
+  %cond = and i1 %b, %notc
+  %r = select i1 %cond, i1 %a, i1 %b
+  ret i1 %r
+}
+
 define i1 @neg_and_or1(i1 %a, i1 %b, i1 %c, i1 %d) {
 ; CHECK-LABEL: @neg_and_or1(
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i1 [[A:%.*]], true
 ; CHECK-NEXT:    [[COND:%.*]] = or i1 [[NOTA]], [[C:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[D:%.*]], i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %nota = xor i1 %a, true

 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND]], i1 [[A:%.*]], i1 [[D:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notc = xor i1 %c, true
   %cond = and i1 %notc, %b
   %r = select i1 %cond, i1 %a, i1 %d
   ret i1 %r
 }
+
+define <2 x i1> @and_or1_op1not_vec(<2 x i1> %a, <2 x i1> %b) {
+; CHECK-LABEL: @and_or1_op1not_vec(
+; CHECK-NEXT:    [[C:%.*]] = call <2 x i1> @gen_v2i1()
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze <2 x i1> [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or <2 x i1> [[C]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = and <2 x i1> [[TMP2]], [[A:%.*]]
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %c = call <2 x i1> @gen_v2i1()
+  %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
+}