[InstSimplify] Add logic `or` fold

[MehrHeidar]

Summary

Add logic or fold: (A ^ B) | (~A | B) --> -1

https://alive2.llvm.org/ce/z/PMtdYB

[foad]

Looks fine to me but I will defer to @spatel.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

2231–2232

This is more like the folds at lines 2205 / 2213, right? If there are 2 commutative ops, then we are handling 4 distinct patterns.

And that means there should be 8 tests after we account for the swapped operands handled by the caller.

[MehrHeidar]

Add more commuted version of test cases.

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2231–2232

Thank you!
I added 5 more test cases for the rest of commuted versions.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

2229–2230

The code comment doesn't line up with the match logic. We always match the 'not' of A, so there shouldn't be a ~B here. There should be 4 lines in this list to make it symmetric with the other comments in this function.

llvm/test/Transforms/InstSimplify/or.ll

956

I think the tests are covering all the possibilities, but (similar to my previous comment) I'd prefer that we keep the 'not' on 'A' only, so it's easier to see how things are moving around in these comments/tests.

[MehrHeidar]

Change the test cases and format of the comments to be more consistent with existing ones.

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2229–2230

I did change the comments to 4 lines and only A is not in the comments to match with the logic in code.

llvm/test/Transforms/InstSimplify/or.ll

956

I changed the test cases based on your suggestions; it totally make sense to follow same rule across the tests.
Thanks.

[spatel]

LGTM - thanks! See inline for one very minor comment.

llvm/lib/Analysis/InstructionSimplify.cpp

2229

One more tiny nit - the 'X' in all of these formulas is the first operand of the 'or', but this set of formulas is showing 'X' as the second operand. That is, the inner 'or' that includes the 'not A' operand should be on the left side and the 'A ^ B' should be on the right to match what the code does.

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2229

Thank you!
Right, I changed the order of or and xor in the comments to match the code.

llvm/lib/Analysis/InstructionSimplify.cpp

if (match(X, m_Xor(m_Value(A), m_Value(B))) &&
     return Y;
 
   // ~(A ^ B) | (A | B) --> -1
   // ~(A ^ B) | (B | A) --> -1
   if (match(X, m_Not(m_Xor(m_Value(A), m_Value(B)))) &&
       match(Y, m_c_Or(m_Specific(A), m_Specific(B))))
     return ConstantInt::getAllOnesValue(Ty);
 
+  // (~A | B) | (A ^ B) --> -1
+  // (~A | B) | (B ^ A) --> -1
+  // (B | ~A) | (A ^ B) --> -1
+  // (B | ~A) | (B ^ A) --> -1
+  if (match(X, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
+      match(Y, m_c_Xor(m_Specific(A), m_Specific(B))))
+    return ConstantInt::getAllOnesValue(Ty);
+
   return nullptr;
 }
 
 /// Given operands for an Or, see if we can fold the result.
 /// If not, this returns null.
 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
                              unsigned MaxRecurse) {
   if (Constant *C = foldOrCommuteConstant(Instruction::Or, Op0, Op1, Q))

llvm/test/Transforms/InstSimplify/or.ll

;
   %r = or <2 x i4> %or, %not
   ret <2 x i4> %r
 }
 
 ; (A ^ B) | (~A | B) --> -1
 
 define i4 @or_xor_not_op_or(i4 %a, i4 %b){
 ; CHECK-LABEL: @or_xor_not_op_or(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i4 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i4 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i4 [[NOTA]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = or i4 [[XOR]], [[OR]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    ret i4 -1
 ;
   %xor = xor i4 %a, %b
   %nota = xor i4 %a, -1
   %or = or i4 %nota, %b
   %r = or i4 %xor, %or
   ret i4 %r
 }
 
-; (A ^ B) | (~B | A) --> -1
+; (A ^ B) | (B | ~A) --> -1
 
 define i71  @or_xor_not_op_or_commute1(i71 %a, i71 %b){
 ; CHECK-LABEL: @or_xor_not_op_or_commute1(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i71 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOTB:%.*]] = xor i71 [[B]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i71 [[NOTB]], [[A]]
-; CHECK-NEXT:    [[R:%.*]] = or i71 [[XOR]], [[OR]]
-; CHECK-NEXT:    ret i71 [[R]]
+; CHECK-NEXT:    ret i71 -1
 ;
   %xor = xor i71 %a, %b
-  %notb = xor i71  %b, -1
-  %or = or i71  %notb, %a
+  %nota = xor i71  %a, -1
+  %or = or i71  %b, %nota
   %r = or i71  %xor, %or
   ret i71  %r
 }
 
-; (~A | B)  | (A ^ B) --> -1
+; (B ^ A) | (~A | B) --> -1
 
 define i32  @or_xor_not_op_or_commute2(i32 %a, i32 %b){
 ; CHECK-LABEL: @or_xor_not_op_or_commute2(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOTA]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = or i32 [[OR]], [[XOR]]
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    ret i32 -1
+;
+  %xor = xor i32 %b, %a
+  %nota = xor i32  %a, -1
+  %or = or i32  %nota, %b
+  %r = or i32  %xor, %or
+  ret i32  %r
+}
+
+; (B ^ A) | (B | ~A) --> -1
+
+define i32  @or_xor_not_op_or_commute3(i32 %a, i32 %b){
+; CHECK-LABEL: @or_xor_not_op_or_commute3(
+; CHECK-NEXT:    ret i32 -1
+;
+  %xor = xor i32 %b, %a
+  %nota = xor i32  %a, -1
+  %or = or i32  %b, %nota
+  %r = or i32  %xor, %or
+  ret i32  %r
+}
+
+; (~A | B) | (A ^ B) --> -1
+
+define i32  @or_xor_not_op_or_commute4(i32 %a, i32 %b){
+; CHECK-LABEL: @or_xor_not_op_or_commute4(
+; CHECK-NEXT:    ret i32 -1
+;
+  %xor = xor i32 %a, %b
+  %nota = xor i32  %a, -1
+  %or = or i32  %nota, %b
+  %r = or i32  %or, %xor
+  ret i32  %r
+}
+
+; (B | ~A) | (A ^ B) --> -1
+
+define i32  @or_xor_not_op_or_commute5(i32 %a, i32 %b){
+; CHECK-LABEL: @or_xor_not_op_or_commute5(
+; CHECK-NEXT:    ret i32 -1
 ;
   %xor = xor i32 %a, %b
   %nota = xor i32  %a, -1
+  %or = or i32  %b, %nota
+  %r = or i32  %or, %xor
+  ret i32  %r
+}
+
+; (~A | B) | (B ^ A) --> -1
+
+define i32  @or_xor_not_op_or_commute6(i32 %a, i32 %b){
+; CHECK-LABEL: @or_xor_not_op_or_commute6(
+; CHECK-NEXT:    ret i32 -1
+;
+  %xor = xor i32 %b, %a
+  %nota = xor i32  %a, -1
   %or = or i32  %nota, %b
   %r = or i32  %or, %xor
   ret i32  %r
 }
 
+; (B | ~A)  | (B ^ A) --> -1
+
+define i32  @or_xor_not_op_or_commute7(i32 %a, i32 %b){
+; CHECK-LABEL: @or_xor_not_op_or_commute7(
+; CHECK-NEXT:    ret i32 -1
+;
+  %xor = xor i32 %b, %a
+  %nota = xor i32  %a, -1
+  %or = or i32  %b, %nota
+  %r = or i32  %or, %xor
+  ret i32  %r
+}
+
 define <2 x i4> @or_xor_not_op_or_undef_elt(<2 x i4> %a, <2 x i4> %b) {
 ; CHECK-LABEL: @or_xor_not_op_or_undef_elt(
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i4> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor <2 x i4> [[A]], <i4 -1, i4 undef>
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i4> [[NOTA]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[XOR]], [[OR]]
-; CHECK-NEXT:    ret <2 x i4> [[R]]
+; CHECK-NEXT:    ret <2 x i4> <i4 -1, i4 -1>
 ;
   %xor = xor <2 x i4> %a, %b
   %nota = xor <2 x i4> %a, <i4 -1, i4 undef>
   %or = or <2 x i4>  %nota, %b
   %r = or <2 x i4> %xor, %or
   ret <2 x i4> %r
 }
 
 ; negative test
 
 define i16 @or_xor_not_op_or_wrong_val(i16 %a, i16 %b, i16 %c) {
 ; CHECK-LABEL: @or_xor_not_op_or_wrong_val(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i16 [[A:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i16 [[A]], -1