Added InstCombine Transform for ((B | C) & A) | B -> B | (A & C)

[sonamkumari]

Summary

Hi All,

This patch implements transform for the pattern " ((B | C) & A) | B -> B | (A & C) "

Please help in reviewing the same.

Z3 Link : http://rise4fun.com/Z3/hP6p

Thanks,
Sonam.

[majnemer]

While this seems to handle ((B | C) & A) | B, it would be nice if you also handled ((B | C) & A) | C

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2129

This is a longwinded way of saying Op1 == B.

[sonamkumari]

Hi David,

Thanks for your valuable comments.
I have changed the second "if" condition as you mentioned.
For handling ( ( B | C ) & A ) | C -> C | ( A & B) :
I passed the following test case using reassociate before instcombine

define i32 @test19(i32 %x, i32 %y, i32 %z) {

%or = or i32 %y, %z
%and = and i32 %x, %or
%or1 = or i32 %and, %z
ret i32 %or1

}

The output I got was :

define i32 @test19(i32 %x, i32 %y, i32 %z) {

%1 = and i32 %x, %y
%or1 = or i32 %1, %z
ret i32 %or1

}

So, I guess we need not handle this case.
Please help in reviewing the same.

Thanks,
Sonam.

[majnemer]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2128–2129

Hrm, maybe this could be simplified further:

if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
  return BinaryOperator::CreateOr(Op1, Builder->CreateAnd(A, C));

[sonamkumari]

Hi David,

Thanks for further simplifying it.
I have made the changes and submitted the same.
Please help in reviewing the same.

Thanks,
Sonam

[majnemer]

LGTM.

[sonamkumari]

Hi David,

Can you please commit this on my behalf as i don't have commit access.

Thanks,
Sonam.

[majnemer]

Closed by commit rL215619 (authored by @majnemer).

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
         return BinaryOperator::CreateOr(Op0, C);
 
   // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
   if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
     if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
       if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
         return BinaryOperator::CreateOr(Op1, C);
 
+  // ((B | C) & A) | B -> B | (A & C)
+  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
+    return BinaryOperator::CreateOr(Op1, Builder->CreateAnd(A, C));
+
   // (X >> Z) | (Y >> Z)  -> (X|Y) >> Z  for all shifts.
   if (BinaryOperator *SI1 = dyn_cast<BinaryOperator>(Op1)) {
     if (BinaryOperator *SI0 = dyn_cast<BinaryOperator>(Op0))
       if (SI0->isShift() && SI0->getOpcode() == SI1->getOpcode() &&
           SI0->getOperand(1) == SI1->getOperand(1) &&
           (SI0->hasOneUse() || SI1->hasOneUse())) {
         Value *NewOp = Builder->CreateOr(SI0->getOperand(0), SI1->getOperand(0),
                                          SI0->getName());

test/Transforms/InstCombine/or.ll

 ; CHECK-LABEL: test44(
 ; CHECK-NEXT: %or = xor i32 %a, %b
  %xor = xor i32 %a, %b
  %neg = xor i32 %b, -1
  %and = and i32 %a, %neg
  %or = or i32 %xor, %and
  ret i32 %or
 }
+
+define i32 @test45(i32 %x, i32 %y, i32 %z) {
+; CHECK-LABEL: test45(
+; CHECK-NEXT: %1 = and i32 %x, %z
+; CHECK-NEXT: %or1 = or i32 %1, %y
+; CHECK-NEXT: ret i32 %or1
+  %or = or i32 %y, %z
+  %and = and i32 %x, %or
+  %or1 = or i32 %and, %y
+  ret i32 %or1
+}