Optimize bitwise even/odd test (-x&1 -> x&1) to not use negation.

[bmakam]

Summary

We know that -x & 1 is equivalent to x & 1, avoid using negation for testing if a negative integer is even or odd.

[majnemer]

Please add more context to the diff.

[bmakam]

adding more context to diff.

[mcrosier]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1277

The isa<> check removes the need for a dyn_cast. You can safely use

const APInt &Op0LHSMask = cast<ConstantInt>(Op0LHS)->getValue();

if I'm not mistaken.

1278

No need for the extra braces as the condition is guarding a single statement.

[majnemer]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1276–1278

I think this can more concisely written as:

if (AndRHSMask == 1 && match(Op0LHS, m_Zero()))
  return BinaryOperator::CreateAnd(Op0RHS, AndRHS);

[majnemer]

LGTM

test/Transforms/InstCombine/and-with-one.ll

2–26

Instead of a new file, can you add these to and2.ll ?

[bmakam]

Adding tests to and2.ll Thanks for the review.

[mcrosier]

Balaram,
Please let me know when you're ready for the patch to land and I'll be happy to commit it on your behalf.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
 
       case Instruction::Sub:
         // ((A & N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == AndRHS.
         // ((A | N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0
         // ((A ^ N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0
         if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, true, I))
           return BinaryOperator::CreateAnd(V, AndRHS);
 
+        // -x & 1 -> x & 1
+        if (AndRHSMask == 1 && isa<ConstantInt>(Op0LHS)) {
+            const APInt &Op0LHSMask = dyn_cast<ConstantInt>(Op0LHS)->getValue();
+            if (Op0LHSMask == 0) {
+              return BinaryOperator::CreateAnd(Op0RHS, AndRHS);
+            }
+        }
+
         // (A - N) & AndRHS -> -N & AndRHS iff A&AndRHS==0 and AndRHS
         // has 1's for all bits that the subtraction with A might affect.
         if (Op0I->hasOneUse() && !match(Op0LHS, m_Zero())) {
           uint32_t BitWidth = AndRHSMask.getBitWidth();
           uint32_t Zeros = AndRHSMask.countLeadingZeros();
           APInt Mask = APInt::getLowBitsSet(BitWidth, BitWidth - Zeros);
 
           if (MaskedValueIsZero(Op0LHS, Mask, 0, &I)) {

test/Transforms/InstCombine/and-with-one.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define i64 @test1(i64 %x) {
+; CHECK-LABEL: @test1(
+; CHECK-NOT: %sub = sub nsw i64 0, %x
+; CHECK-NOT: %and = and i64 %sub, 1
+; CHECK-NEXT: %and = and i64 %x, 1
+; CHECK-NEXT: ret i64 %and
+  %sub = sub nsw i64 0, %x
+  %and = and i64 %sub, 1
+  ret i64 %and
+}
+
+define i64 @test2(i64 %x) {
+; CHECK-LABEL: @test2(
+; CHECK-NOT: %sub = sub nsw i64 0, %x
+; CHECK-NEXT: %and = and i64 %x, 1
+; CHECK-NOT: %add = add i64 %sub, %and
+; CHECK-NEXT: %add = sub i64 %and, %x
+; CHECK-NEXT: ret i64 %add
+  %sub = sub nsw i64 0, %x
+  %and = and i64 %sub, 1
+  %add = add i64 %sub, %and
+  ret i64 %add
+}