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

[dinesh.d]

Summary

This patch adds transforms for

• Single bit tests [http://nondot.org/sabre/LLVMNotes/InstCombine.txt]:

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

[majnemer]

You seem to be creating SelectInst instructions with the same Value for both the true and false arms. Instead, why not just return the Value?

[dinesh.d]

oh, silly mistake, updated patch to return Value directly.

[dinesh.d]

fixed one formatting issue

[bkramer]

This looks good now.

[dinesh.d]

Submitted as r208848.

Thanks for review and support.

lib/Transforms/InstCombine/InstCombineSelect.cpp

 ///   C1 and C2 are both powers of 2
 /// where:
 ///   C3 = Log(C2) - Log(C1)
 ///
 /// This transform handles cases where:
 /// 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());
   if (!IC || !IC->isEquality() || !SI.getType()->isIntegerTy())
     return nullptr;
 
   Value *CmpLHS = IC->getOperand(0);
   Value *CmpRHS = IC->getOperand(1);
 
   if (!match(CmpRHS, m_Zero()))
     return nullptr;
 
   Value *X;
   const APInt *C1;
   if (!match(CmpLHS, m_And(m_Value(X), m_Power2(C1))))
     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) {
+    Value *NewVal = Builder->CreateAnd(TrueVal, ~(*C1));
+    return Builder->CreateSelect(SI.getCondition(), NewVal, NewVal);
+  }
+
+  // if ((x & C) == 0) x ^= C becomes x |= C
+  if (match(TrueVal, m_Xor(m_Specific(FalseVal), m_APInt(C2))) && C1 == C2) {
+    Value *NewVal = Builder->CreateOr(FalseVal, *C1);
+    return Builder->CreateSelect(SI.getCondition(), NewVal, NewVal);
+  }
+
+  // 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 Builder->CreateSelect(SI.getCondition(), FalseVal, 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 Builder->CreateSelect(SI.getCondition(), TrueVal, TrueVal);
+
+  if (!OrOnTrueVal)
+    OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
 
   if (!OrOnFalseVal && !OrOnTrueVal)
     return nullptr;
 
   Value *V = CmpLHS;
   Value *Y = OrOnFalseVal ? TrueVal : FalseVal;
 
   unsigned C1Log = C1->logBase2();

test/Transforms/InstCombine/select.ll

 define <2 x i32> @select_icmp_eq_and_1_0_or_vector_of_2s(i32 %x, <2 x i32> %y) {
   %and = and i32 %x, 1
   %cmp = icmp eq i32 %and, 0
   %or = or <2 x i32> %y, <i32 2, i32 2>
   %select = select i1 %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
+; CHECK-LABEL: @select_icmp_and_8_eq_0_or_8(
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 8
+; CHECK-NEXT: ret i32 [[OR]]
+define i32 @select_icmp_and_8_eq_0_or_8(i32 %x) {
+  %and = and i32 %x, 8
+  %cmp = icmp eq i32 %and, 0
+  %or = or i32 %x, 8
+  %or.x = select i1 %cmp, i32 %or, i32 %x
+  ret i32 %or.x
+}
+
+; CHECK-LABEL: @select_icmp_and_8_ne_0_xor_8(
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, -9
+; CHECK-NEXT: ret i32 [[AND]]
+define i32 @select_icmp_and_8_ne_0_xor_8(i32 %x) {
+  %and = and i32 %x, 8
+  %cmp = icmp eq i32 %and, 0
+  %xor = xor i32 %x, 8
+  %x.xor = select i1 %cmp, i32 %x, i32 %xor
+  ret i32 %x.xor
+}
+
+; CHECK-LABEL: @select_icmp_and_8_eq_0_xor_8(
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 8
+; CHECK-NEXT: ret i32 [[OR]]
+define i32 @select_icmp_and_8_eq_0_xor_8(i32 %x) {
+  %and = and i32 %x, 8
+  %cmp = icmp eq i32 %and, 0
+  %xor = xor i32 %x, 8
+  %xor.x = select i1 %cmp, i32 %xor, i32 %x
+  ret i32 %xor.x
+}
+
+; CHECK-LABEL: @select_icmp_and_8_ne_0_and_not_8(
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, -9
+; CHECK-NEXT: ret i32 [[AND]]
+define i32 @select_icmp_and_8_ne_0_and_not_8(i32 %x) {
+  %and = and i32 %x, 8
+  %cmp = icmp eq i32 %and, 0
+  %and1 = and i32 %x, -9
+  %x.and1 = select i1 %cmp, i32 %x, i32 %and1
+  ret i32 %x.and1
+}
+
+; CHECK-LABEL: @select_icmp_and_8_eq_0_and_not_8(
+; CHECK-NEXT: ret i32 %x
+define i32 @select_icmp_and_8_eq_0_and_not_8(i32 %x) {
+  %and = and i32 %x, 8
+  %cmp = icmp eq i32 %and, 0
+  %and1 = and i32 %x, -9
+  %and1.x = select i1 %cmp, i32 %and1, i32 %x
+  ret i32 %and1.x
+}
+
 define i32 @test65(i64 %x) {
   %1 = and i64 %x, 16
   %2 = icmp ne i64 %1, 0
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 
 ; CHECK-LABEL: @test65(
 ; CHECK: and i64 %x, 16