From 91e37ef278779c3c8700bbddbb5c9d37739b1716 Mon Sep 17 00:00:00 2001
From: Benjamin Kramer <benny.kra@googlemail.com>
Date: Sun, 20 Feb 2011 13:23:43 +0000
Subject: [PATCH] InstCombine: Add a bunch of combines of the form x | (y ^ z).

We usually catch this kind of optimization through InstSimplify's distributive
magic, but or doesn't distribute over xor in general.

"A | ~(A | B) -> A | ~B" hits 24 times on gcc.c.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126081 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../InstCombine/InstCombineAndOrXor.cpp       | 41 ++++++++
 test/Transforms/InstCombine/or-xor.ll         | 94 +++++++++++++++++++
 2 files changed, 135 insertions(+)
 create mode 100644 test/Transforms/InstCombine/or-xor.ll

diff --git a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index b6b6b84d964..07069ada9a2 100644
--- a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1897,6 +1897,47 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) {
         return BinaryOperator::CreateNot(And);
       }
 
+  // Canonicalize xor to the RHS.
+  if (match(Op0, m_Xor(m_Value(), m_Value())))
+    std::swap(Op0, Op1);
+
+  // A | ( A ^ B) -> A |  B
+  // A | (~A ^ B) -> A | ~B
+  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
+    if (Op0 == A || Op0 == B)
+      return BinaryOperator::CreateOr(A, B);
+
+    if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
+      Value *Not = Builder->CreateNot(B, B->getName()+".not");
+      return BinaryOperator::CreateOr(Not, Op0);
+    }
+    if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
+      Value *Not = Builder->CreateNot(A, A->getName()+".not");
+      return BinaryOperator::CreateOr(Not, Op0);
+    }
+  }
+
+  // A | ~(A | B) -> A | ~B
+  // A | ~(A ^ B) -> A | ~B
+  // A | ~(A & B) -> -1
+  if (match(Op1, m_Not(m_Value(A))))
+    if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
+      if (Op0 == B->getOperand(0) || Op0 == B->getOperand(1))
+        switch (B->getOpcode()) {
+        default: break;
+        case Instruction::Or:
+        case Instruction::Xor:
+          if (Op1->hasOneUse()) {
+            Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
+                                                     B->getOperand(0);
+            Value *Not = Builder->CreateNot(NotOp, NotOp->getName()+".not");
+            return BinaryOperator::CreateOr(Not, Op0);
+          }
+          break;
+        case Instruction::And:
+          return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType()));
+        }
+
   if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
     if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
       if (Value *Res = FoldOrOfICmps(LHS, RHS))
diff --git a/test/Transforms/InstCombine/or-xor.ll b/test/Transforms/InstCombine/or-xor.ll
new file mode 100644
index 00000000000..f496dd48c40
--- /dev/null
+++ b/test/Transforms/InstCombine/or-xor.ll
@@ -0,0 +1,94 @@
+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+define i32 @test1(i32 %x, i32 %y) nounwind {
+  %or = or i32 %x, %y
+  %not = xor i32 %or, -1
+  %z = or i32 %x, %not
+  ret i32 %z
+; CHECK: @test1
+; CHECK-NEXT: %y.not = xor i32 %y, -1
+; CHECK-NEXT: %z = or i32 %y.not, %x
+; CHECK-NEXT: ret i32 %z
+}
+
+define i32 @test2(i32 %x, i32 %y) nounwind {
+  %or = or i32 %x, %y
+  %not = xor i32 %or, -1
+  %z = or i32 %y, %not
+  ret i32 %z
+; CHECK: @test2
+; CHECK-NEXT: %x.not = xor i32 %x, -1
+; CHECK-NEXT: %z = or i32 %x.not, %y
+; CHECK-NEXT: ret i32 %z
+}
+
+define i32 @test3(i32 %x, i32 %y) nounwind {
+  %xor = xor i32 %x, %y
+  %not = xor i32 %xor, -1
+  %z = or i32 %x, %not
+  ret i32 %z
+; CHECK: @test3
+; CHECK-NEXT: %y.not = xor i32 %y, -1
+; CHECK-NEXT: %z = or i32 %y.not, %x
+; CHECK-NEXT: ret i32 %z
+}
+
+define i32 @test4(i32 %x, i32 %y) nounwind {
+  %xor = xor i32 %x, %y
+  %not = xor i32 %xor, -1
+  %z = or i32 %y, %not
+  ret i32 %z
+; CHECK: @test4
+; CHECK-NEXT: %x.not = xor i32 %x, -1
+; CHECK-NEXT: %z = or i32 %x.not, %y
+; CHECK-NEXT: ret i32 %z
+}
+
+define i32 @test5(i32 %x, i32 %y) nounwind {
+  %and = and i32 %x, %y
+  %not = xor i32 %and, -1
+  %z = or i32 %x, %not
+  ret i32 %z
+; CHECK: @test5
+; CHECK-NEXT: ret i32 -1
+}
+
+define i32 @test6(i32 %x, i32 %y) nounwind {
+  %and = and i32 %x, %y
+  %not = xor i32 %and, -1
+  %z = or i32 %y, %not
+  ret i32 %z
+; CHECK: @test6
+; CHECK-NEXT: ret i32 -1
+}
+
+define i32 @test7(i32 %x, i32 %y) nounwind {
+  %xor = xor i32 %x, %y
+  %z = or i32 %y, %xor
+  ret i32 %z
+; CHECK: @test7
+; CHECK-NEXT: %z = or i32 %x, %y
+; CHECK-NEXT: ret i32 %z
+}
+
+define i32 @test8(i32 %x, i32 %y) nounwind {
+  %not = xor i32 %y, -1
+  %xor = xor i32 %x, %not
+  %z = or i32 %y, %xor
+  ret i32 %z
+; CHECK: @test8
+; CHECK-NEXT: %x.not = xor i32 %x, -1
+; CHECK-NEXT: %z = or i32 %x.not, %y
+; CHECK-NEXT: ret i32 %z
+}
+
+define i32 @test9(i32 %x, i32 %y) nounwind {
+  %not = xor i32 %x, -1
+  %xor = xor i32 %not, %y
+  %z = or i32 %x, %xor
+  ret i32 %z
+; CHECK: @test9
+; CHECK-NEXT: %y.not = xor i32 %y, -1
+; CHECK-NEXT: %z = or i32 %y.not, %x
+; CHECK-NEXT: ret i32 %z
+}
-- 
2.34.1