Added InstCombine transform for pattern "(A ^ B) | ((~A) ^ B) -> True".

[sonamkumari]

Summary

This patch implements transform for pattern "(A ^ B) | ((~A) ^ B) -> True".

Please help in reviewing the same.

Thanks,
Sonam.

[majnemer]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1286

This change seems irrelevant to the patch.

2013–2016

See my comments in your other differential, D4690.

test/Transforms/InstCombine/or.ll

411–420 ↗

(On Diff #11938)

Again, please see my comments in D4690.

[sonamkumari]

Hi David,

Thanks for your valuable review comments.
I have made the changes as you mentioned.
Please help in reviewing the patch.

Thanks,
Sonam.

[majnemer]

Thinking about this with some colleagues, I'm starting to believe that this can be fixed in a more general way.

We do not optimize (A ^ B) | ((A ^ -1) ^ B) but we correctly optimize (A ^ B) | ((A ^ B) ^ -1); this makes me think that we are looking at a bug in reassociate.

lib/Analysis/InstructionSimplify.cpp

1606 ↗

(On Diff #12015)

This comment looks wrong, it should probably be:

// (A ^ B) | ((~A) ^ B) = -1

[majnemer]

I've gone ahead and fixed this in rL214342; it includes a more general transform which should handle more cases.

[sonamkumari]

Hi David,

Thanks for your valuable comments.I will try to consider general case while doing any optimization in future.
But the patch which you uploaded in rL214342 fails for the following test cases as it doesn't take into consideration the symmetric case.

The test cases for which it fails are :

define i32 @test14(i32 %x, i32 %y) {

%nega = xor i32 %x, -1
%xor = xor i32 %nega, %y
%xor1 = xor i32 %x, %y
%or = or i32 %xor, %xor1
ret i32 %or

}

define i32 @test15(i32 %x, i32 %y) {

%xor = xor i32 %x, %y
%nega = xor i32 %x, -1
%xor1 = xor i32 %nega, %y
%or = or i32 %xor, %xor1
ret i32 %or

}

So, I modified the patch and submitting the same.
Kindly review it.

Thanks,
Sonam.

[suyog]

LGTM. I would wait for David to comment on it though.

[majnemer]

I don't think we need to do anything here, running reassociate before instcombine cleans things up.

$ cat t.ll
define i32 @test14(i32 %x, i32 %y) {
  %nega = xor i32 %x, -1
  %xor = xor i32 %nega, %y
  %xor1 = xor i32 %x, %y
  %or = or i32 %xor, %xor1
  ret i32 %or
}

define i32 @test15(i32 %x, i32 %y) {
  %xor = xor i32 %x, %y
  %nega = xor i32 %x, -1
  %xor1 = xor i32 %nega, %y
  %or = or i32 %xor, %xor1
  ret i32 %or
}

$ ~/llvm/Debug+Asserts/bin/opt -reassociate -instcombine t.ll -o - -S
; ModuleID = 't.ll'

define i32 @test14(i32 %x, i32 %y) {
  ret i32 -1
}

define i32 @test15(i32 %x, i32 %y) {
  ret i32 -1
}

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Value *Op0NotVal = dyn_castNotVal(Op0))
 
     // (A&((~A)|B)) -> A&B
     if (match(Op0, m_Or(m_Not(m_Specific(Op1)), m_Value(A))) ||
         match(Op0, m_Or(m_Value(A), m_Not(m_Specific(Op1)))))
       return BinaryOperator::CreateAnd(A, Op1);
     if (match(Op1, m_Or(m_Not(m_Specific(Op0)), m_Value(A))) ||
         match(Op1, m_Or(m_Value(A), m_Not(m_Specific(Op0)))))
       return BinaryOperator::CreateAnd(A, Op0);
 
     // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
     if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
       if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
         if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
           return BinaryOperator::CreateAnd(Op0, Builder->CreateNot(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))))
Instruction *InstCombiner::visitOr(BinaryOperator &I) {
   if (Op1->hasOneUse() &&
       match(Op1, m_Xor(m_Value(A), m_ConstantInt(C1))) &&
       MaskedValueIsZero(Op0, C1->getValue())) {
     Value *NOr = Builder->CreateOr(A, Op0);
     NOr->takeName(Op0);
     return BinaryOperator::CreateXor(NOr, C1);
   }
 
   // ((~A & B) | A) -> (A | B)
   if (match(Op0, m_And(m_Not(m_Value(A)), m_Value(B))) &&
       match(Op1, m_Specific(A)))
     return BinaryOperator::CreateOr(A, B);
 
   // ((A & B) | ~A) -> (~A | B)
   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
       match(Op1, m_Not(m_Specific(A))))
     return BinaryOperator::CreateOr(Builder->CreateNot(A), B);
 
   // (A & (~B)) | (A ^ B) -> (A ^ B)
   if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
     if (match(B, m_Or(m_Specific(A), m_Value(V1))) ||
         match(B, m_Or(m_Value(V1), m_Specific(A)))) {
       Instruction *Ret = FoldOrWithConstants(I, Op0, A, V1, D);
       if (Ret) return Ret;
     }
   }
 
   // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
-  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
-    if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
+  // (B ^ A) | ((B ^ C) ^ A) -> (A ^ B) | C
+  if (match(Op1, m_Xor(m_Xor(m_Value(B), m_Value(C)), m_Value(A))))
+    if (match(Op0, m_Xor(m_Specific(A), m_Specific(B))) ||
+        match(Op0, m_Xor(m_Specific(B), m_Specific(A))))
       if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
         return BinaryOperator::CreateOr(Op0, C);
 
   // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
+  // ((A ^ C) ^ B) | (A ^ B) -> (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 (match(Op1, m_Xor(m_Specific(B), m_Specific(A))) ||
+        match(Op1, m_Xor(m_Specific(A), m_Specific(B))))
       if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
         return BinaryOperator::CreateOr(Op1, 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) &&

test/Transforms/InstCombine/or-xor.ll

  %xor = xor i32 %neg, %y
  %or = or i32 %x, %y
  %and = and i32 %xor, %or
  ret i32 %and
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT: %and = and i32 %x, %y
 ; CHECK-NEXT: ret i32 %and
 }
+
+define i32 @test14(i32 %x, i32 %y) {
+  %nega = xor i32 %x, -1
+  %xor = xor i32 %nega, %y
+  %xor1 = xor i32 %x, %y
+  %or = or i32 %xor, %xor1
+  ret i32 %or
+; CHECK-LABEL: @test14(
+; CHECK-NEXT: ret i32 -1
+}
+
+define i32 @test15(i32 %x, i32 %y) {
+  %xor = xor i32 %x, %y
+  %nega = xor i32 %x, -1
+  %xor1 = xor i32 %nega, %y
+  %or = or i32 %xor, %xor1
+  ret i32 %or
+; CHECK-LABEL: @test15(
+; CHECK-NEXT: ret i32 -1
+}