[InstCombineAddSub] Transformation for the expression (X | Y) - X --> (~X & Y)

[ankur29.garg]

Summary

Hi,
The following changes implement the transformation for the expression - (X | Y) - X --> (~X & Y).

Z3 Link: http://rise4fun.com/Z3/2D4n

Please help in reviewing it.

Thanks.

[ankur29.garg]

Gentle Ping!

[majnemer]

LGTM

[majnemer]

Actually, I think this needs a small tweak.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1643–1648

Please move your change so it is near this pattern.

[ankur29.garg]

Moved the transformation to the location suggested.

[ankur29.garg]

Added the test case. Forgot to include it in the last revision.

[majnemer]

LGTM

[ankur29.garg]

Thank you David, for reviewing the patch. Can you also please commit this, as I don't have commit access yet.

Thanks.

[majnemer]

test/Transforms/InstCombine/sub.ll

544–548 ↗

(On Diff #15683)

I don't believe you have run the tests after updating your patch, please do so in the future.

[majnemer]

Closed by commit rL221129 (authored by @majnemer).

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) &&
       if (C1 == C2) {
         Constant *Z1=nullptr, *Z2=nullptr;
         Value *A, *B, *C=C1;
         if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) {
             Z1 = dyn_cast<Constant>(A1); A = A2;
             Z2 = dyn_cast<Constant>(B2); B = B1;
         } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) {
             Z1 = dyn_cast<Constant>(B1); B = B2;
-            Z2 = dyn_cast<Constant>(A2); A = A1; 
+            Z2 = dyn_cast<Constant>(A2); A = A1;
         }
-        
-        if (Z1 && Z2 && 
-            (I.hasNoSignedZeros() || 
+        if (Z1 && Z2 &&
+            (I.hasNoSignedZeros() ||
              (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) {
           return SelectInst::Create(C, A, B);
         }
       }
     }
   }
 
   if (I.hasUnsafeAlgebra()) {
if (C->isNullValue() && match(Op1, m_SExt(m_Value(X))))
       if (X->getType()->getScalarType()->isIntegerTy(1))
         return CastInst::CreateZExtOrBitCast(X, Op1->getType());
   }
 
   if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
     // -(X >>u 31) -> (X >>s 31)
     // -(X >>s 31) -> (X >>u 31)
     if (C->isZero()) {
-      Value *X; 
+      Value *X;
       ConstantInt *CI;
       if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) &&
           // Verify we are shifting out everything but the sign bit.
           CI->getValue() == I.getType()->getPrimitiveSizeInBits() - 1)
         return BinaryOperator::CreateAShr(X, CI);
 
       if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) &&
           // Verify we are shifting out everything but the sign bit.
           CI->getValue() == I.getType()->getPrimitiveSizeInBits() - 1)
         return BinaryOperator::CreateLShr(X, CI);
     }
   }
 
 
-  { 
+  {
     Value *Y;
     // X-(X+Y) == -Y    X-(Y+X) == -Y
     if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) ||
         match(Op1, m_Add(m_Value(Y), m_Specific(Op0))))
       return BinaryOperator::CreateNeg(Y);
 
     // (X-Y)-X == -Y
     if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
if (Op1->hasOneUse()) {
     Constant *C = nullptr;
     Constant *CI = nullptr;
 
     // (X - (Y - Z))  -->  (X + (Z - Y)).
     if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
       return BinaryOperator::CreateAdd(Op0,
                                       Builder->CreateSub(Z, Y, Op1->getName()));
 
     // (X - (X & Y))   -->   (X & ~Y)
     //
     if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) ||
         match(Op1, m_And(m_Specific(Op0), m_Value(Y))))
       return BinaryOperator::CreateAnd(Op0,
                                   Builder->CreateNot(Y, Y->getName() + ".not"));
 
+    // ((X | Y) - X) --> (~X & Y)
+    if (match(Op0, m_Or(m_Value(Y), m_Specific(Op1))) ||
+        match(Op0, m_Or(m_Specific(Op1), m_Value(Y))))
+      return BinaryOperator::CreateAnd(
+          Y, Builder->CreateNot(Op1, Op1->getName() + ".not"));
+
     // 0 - (X sdiv C)  -> (X sdiv -C)  provided the negation doesn't overflow.
     if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && match(Op0, m_Zero()) &&
         C->isNotMinSignedValue() && !C->isOneValue())
       return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
 
     // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
     if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
       if (Value *XNeg = dyn_castNegVal(X))