Add transformation:

 xor (or (icmp, icmp), true) -> and(icmp, icmp)

This is possible because of De Morgan's law.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61537 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 43 insertions, 1 deletions

diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp
index 5f22fd7..9e45193 100644
--- a/lib/Transforms/Scalar/InstructionCombining.cpp
+++ b/lib/Transforms/Scalar/InstructionCombining.cpp
@@ -4871,8 +4871,8 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   
   
   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
-    // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B
     if (RHS == ConstantInt::getTrue() && Op0->hasOneUse()) {
+      // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B
       if (ICmpInst *ICI = dyn_cast<ICmpInst>(Op0))
         return new ICmpInst(ICI->getInversePredicate(),
                             ICI->getOperand(0), ICI->getOperand(1));
@@ -4880,6 +4880,37 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) {
       if (FCmpInst *FCI = dyn_cast<FCmpInst>(Op0))
         return new FCmpInst(FCI->getInversePredicate(),
                             FCI->getOperand(0), FCI->getOperand(1));
+
+      // xor (or (cmp x,m),(cmp y,n)),true --> and (!cmp x,m),(!cmp y,n)
+      //
+      // Proof:
+      //   Let A = (cmp x,m)
+      //   Let B = (cmp y,n)
+      //   Let C = (or A, B)
+      //   C true implies that either A, B, or both are true.
+      //
+      //   (xor C, true) is true only if C is false. We can the apply de
+      //   Morgan's law. QED.
+      BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0);
+      if (Op0I) {
+        Value *A, *B;
+        if (match(Op0I, m_Or(m_Value(A), m_Value(B)))) {
+          ICmpInst *AOp = dyn_cast<ICmpInst>(A);
+          ICmpInst *BOp = dyn_cast<ICmpInst>(B);
+
+          if (AOp && BOp) {
+            ICmpInst *NewA = new ICmpInst(AOp->getInversePredicate(),
+                                          AOp->getOperand(0),
+                                          AOp->getOperand(1));
+            InsertNewInstBefore(NewA, I);
+            ICmpInst *NewB = new ICmpInst(BOp->getInversePredicate(),
+                                          BOp->getOperand(0),
+                                          BOp->getOperand(1));
+            InsertNewInstBefore(NewB, I);
+            return BinaryOperator::CreateAnd(NewA, NewB);
+          }
+        }
+      }
     }
 
     // fold (xor(zext(cmp)), 1) and (xor(sext(cmp)), -1) to ext(!cmp).
diff --git a/test/Transforms/InstCombine/xor-demorgans.ll b/test/Transforms/InstCombine/xor-demorgans.ll
new file mode 100644
index 0000000..763794b
--- /dev/null
+++ b/test/Transforms/InstCombine/xor-demorgans.ll
@@ -0,0 +1,11 @@
+; RUN: llvm-as < %s | opt -instcombine | llvm-dis | not grep {= or}
+; PR3266
+
+define i1 @foo(i32 %x, i32 %y) nounwind {
+.summary:
+       %0 = icmp sgt i32 %x, 4         ; <i1> [#uses=1]
+       %1 = icmp sgt i32 %y, 0         ; <i1> [#uses=1]
+       %.demorgan = or i1 %1, %0               ; <i1> [#uses=1]
+       %2 = xor i1 %.demorgan, true            ; <i1> [#uses=1]
+       ret i1 %2
+}