[InstCombine] generalize 2 LSB of demanded bits for X*X

[spatel]

Summary

This is a follow-up suggested in D119060. Instead of checking each of the bottom 2 bits individually, we can check them together and handle the possibility that we demand both together.

https://alive2.llvm.org/ce/z/C2ihC2

[RKSimon]

Please can you update the DAG version as well? Either in this patch or a followup.

[lebedev.ri]

Thanks, LG.

[spatel]

In D119139#3301156, @RKSimon wrote:

Please can you update the DAG version as well? Either in this patch or a followup.

Sure - I'll push this one and then update DAG tests/logic to correspond.

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

case Instruction::Sub: {
     // Otherwise just compute the known bits of the result.
     bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
     Known = KnownBits::computeForAddSub(I->getOpcode() == Instruction::Add,
                                         NSW, LHSKnown, RHSKnown);
     break;
   }
   case Instruction::Mul: {
     if (DemandedMask.isPowerOf2()) {
-      if (I->getOperand(0) == I->getOperand(1)) {
-        // X * X is odd iff X is odd.
-        if (DemandedMask == 1)
-          return I->getOperand(0);
-
-        // 'Quadratic Reciprocity': mul(x,x) -> 0 if we're only demanding bit[1]
-        if (DemandedMask == 2)
-          return ConstantInt::getNullValue(VTy);
-      }
-
       // The LSB of X*Y is set only if (X & 1) == 1 and (Y & 1) == 1.
       // If we demand exactly one bit N and we have "X * (C' << N)" where C' is
       // odd (has LSB set), then the left-shifted low bit of X is the answer.
       unsigned CTZ = DemandedMask.countTrailingZeros();
       const APInt *C;
       if (match(I->getOperand(1), m_APInt(C)) &&
           C->countTrailingZeros() == CTZ) {
         Constant *ShiftC = ConstantInt::get(I->getType(), CTZ);
         Instruction *Shl = BinaryOperator::CreateShl(I->getOperand(0), ShiftC);
         return InsertNewInstWith(Shl, *I);
       }
     }
+    // For a squared value "X * X", the bottom 2 bits are 0 and X[0] because:
+    // X * X is odd iff X is odd.
+    // 'Quadratic Reciprocity': X * X -> 0 for bit[1]
+    if (I->getOperand(0) == I->getOperand(1) && DemandedMask.ult(4)) {
+      Constant *One = ConstantInt::get(VTy, 1);
+      Instruction *And1 = BinaryOperator::CreateAnd(I->getOperand(0), One);
+      return InsertNewInstWith(And1, *I);
+    }
+
     computeKnownBits(I, Known, Depth, CxtI);
     break;
   }
   case Instruction::Shl: {
     const APInt *SA;
     if (match(I->getOperand(1), m_APInt(SA))) {
       const APInt *ShrAmt;
       if (match(I->getOperand(0), m_Shr(m_Value(), m_APInt(ShrAmt))))

llvm/test/Transforms/InstCombine/mul-masked-bits.ll

 ;
   %m = mul i67 %x, -63 ; any odd number will do
   %r = and i67 %m, 1
   ret i67 %r
 }
 
 define i33 @squared_one_demanded_low_bit(i33 %x) {
 ; CHECK-LABEL: @squared_one_demanded_low_bit(
-; CHECK-NEXT:    [[AND:%.*]] = and i33 [[X:%.*]], 1
-; CHECK-NEXT:    ret i33 [[AND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i33 [[X:%.*]], 1
+; CHECK-NEXT:    ret i33 [[TMP1]]
 ;
   %mul = mul i33 %x, %x
   %and = and i33 %mul, 1
   ret i33 %and
 }
 
 define <2 x i8> @squared_one_demanded_low_bit_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @squared_one_demanded_low_bit_splat(
 ; CHECK-NEXT:    [[AND:%.*]] = or <2 x i8> [[X:%.*]], <i8 -2, i8 -2>
 ; CHECK-NEXT:    ret <2 x i8> [[AND]]
 ;
   %mul = mul <2 x i8> %x, %x
   %and = or <2 x i8> %mul, <i8 254, i8 254>
   ret <2 x i8> %and
 }
 
 define i33 @squared_demanded_2_low_bits(i33 %x) {
 ; CHECK-LABEL: @squared_demanded_2_low_bits(
-; CHECK-NEXT:    [[MUL:%.*]] = mul i33 [[X:%.*]], [[X]]
-; CHECK-NEXT:    [[AND:%.*]] = and i33 [[MUL]], 3
-; CHECK-NEXT:    ret i33 [[AND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i33 [[X:%.*]], 1
+; CHECK-NEXT:    ret i33 [[TMP1]]
 ;
   %mul = mul i33 %x, %x
   %and = and i33 %mul, 3
   ret i33 %and
 }
 
 define <2 x i8> @squared_demanded_2_low_bits_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @squared_demanded_2_low_bits_splat(
-; CHECK-NEXT:    [[MUL:%.*]] = mul <2 x i8> [[X:%.*]], [[X]]
-; CHECK-NEXT:    [[AND:%.*]] = or <2 x i8> [[MUL]], <i8 -4, i8 -4>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 1, i8 1>
+; CHECK-NEXT:    [[AND:%.*]] = or <2 x i8> [[TMP1]], <i8 -4, i8 -4>
 ; CHECK-NEXT:    ret <2 x i8> [[AND]]
 ;
   %mul = mul <2 x i8> %x, %x
   %and = or <2 x i8> %mul, <i8 252, i8 252>
   ret <2 x i8> %and
 }
+
+; negative test
+
+define i33 @squared_demanded_3_low_bits(i33 %x) {
+; CHECK-LABEL: @squared_demanded_3_low_bits(
+; CHECK-NEXT:    [[MUL:%.*]] = mul i33 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[AND:%.*]] = and i33 [[MUL]], 7
+; CHECK-NEXT:    ret i33 [[AND]]
+;
+  %mul = mul i33 %x, %x
+  %and = and i33 %mul, 7
+  ret i33 %and
+}