Added inst combine transforms for single bit tests from Chris's note

if ((x & C) == 0) x |= C becomes x |= C
if ((x & C) != 0) x ^= C becomes x &= ~C
if ((x & C) == 0) x ^= C becomes x |= C
if ((x & C) != 0) x &= ~C becomes x &= ~C
if ((x & C) == 0) x &= ~C becomes nothing

Z3 Verifications code for above transform
http://rise4fun.com/Z3/Pmsh

Differential Revision: http://reviews.llvm.org/D3717

llvm-svn: 208848

1 files changed, 37 insertions, 5 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
index 795e645840c..50b5b3740f1 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
@@ -365,7 +365,15 @@ static Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
 /// 1. The icmp predicate is inverted
 /// 2. The select operands are reversed
 /// 3. The magnitude of C2 and C1 are flipped
-static Value *foldSelectICmpAndOr(const SelectInst &SI, Value *TrueVal,
+///
+/// This also tries to turn
+/// --- Single bit tests:
+/// if ((x & C) == 0) x |= C	to  x |= C
+/// if ((x & C) != 0) x ^= C	to  x &= ~C
+/// if ((x & C) == 0) x ^= C	to  x |= C
+/// if ((x & C) != 0) x &= ~C	to  x &= ~C
+/// if ((x & C) == 0) x &= ~C	to  nothing
+static Value *foldSelectICmpAndOr(SelectInst &SI, Value *TrueVal,
                                   Value *FalseVal,
                                   InstCombiner::BuilderTy *Builder) {
   const ICmpInst *IC = dyn_cast<ICmpInst>(SI.getCondition());
@@ -384,10 +392,34 @@ static Value *foldSelectICmpAndOr(const SelectInst &SI, Value *TrueVal,
     return nullptr;
 
   const APInt *C2;
-  bool OrOnTrueVal = false;
-  bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
-  if (!OrOnFalseVal)
-    OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)));
+
+  // if ((x & C) != 0) x ^= C becomes x &= ~C
+  if (match(FalseVal, m_Xor(m_Specific(TrueVal), m_APInt(C2))) && C1 == C2) {
+    return Builder->CreateAnd(TrueVal, ~(*C1));
+  }
+
+  // if ((x & C) == 0) x ^= C becomes x |= C
+  if (match(TrueVal, m_Xor(m_Specific(FalseVal), m_APInt(C2))) && C1 == C2) {
+    return Builder->CreateOr(FalseVal, *C1);
+  }
+
+  // if ((x & C) != 0) x &= ~C	becomes x &= ~C
+  // if ((x & C) == 0) x &= ~C	becomes	nothing
+  if ((match(FalseVal, m_And(m_Specific(TrueVal), m_APInt(C2))) ||
+       match(TrueVal, m_And(m_Specific(FalseVal), m_APInt(C2)))) &&
+      *C1 == ~(*C2)) {
+    return FalseVal;
+  }
+
+  bool OrOnFalseVal = false;
+  bool OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)));
+
+  // if ((x & C) == 0) x |= C becomes x |= C
+  if (OrOnTrueVal && C1 == C2)
+    return TrueVal;
+
+  if (!OrOnTrueVal)
+    OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
 
   if (!OrOnFalseVal && !OrOnTrueVal)
     return nullptr;