[InstCombine] Add mul with negated power of 2 constant to canEvaluateShifted.

[craig.topper]

Summary

If we are right shifting a multiply by a negated power of 2 where
the power of 2 is the same as the shift amount, we can replace with
a negate followed by an And.

New tests have not been committed yet but the patch shows the diffs.
Let me know if you want any changes or additional tests.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

691

Can we assert !isLeftShift and/or this is a mul with negated-pow2-constant?

692

Is there a difference between using IC.Builder vs. manually inserting?

llvm/test/Transforms/InstCombine/shift.ll

1844

Do we have a negative test with an extra use of the mul?

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

692

Inserting with IC.Builder would insert at the outer LShr. Since we might have gone through a binop that would be the wrong location. foldShiftedShift handles this by calling moveBefore after using IC.Builder. But that still takes the debug location from the outer LShr which seemed wrong. InsertNewInstWith is used by the evaluateInDifferentType code in InstCombineCasts.cpp

[craig.topper]

-Add assert for !isLeftShift. Checking the constant would require calling match with m_APInt that we don't otherwise need.
-Add negative test with additional use of mul.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

 //===- InstCombineShifts.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
case Instruction::PHI: {
     // get into trouble with cyclic PHIs here because we only consider
     // instructions with a single use.
     PHINode *PN = cast<PHINode>(I);
     for (Value *IncValue : PN->incoming_values())
       if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN))
         return false;
     return true;
   }
+  case Instruction::Mul: {
+    const APInt *MulConst;
+    // We can fold (shr (mul X, -(1 << C)), C) -> (and (mul X, -1), C`)
+    return !IsLeftShift && match(I->getOperand(1), m_APInt(MulConst)) &&
+           MulConst->isNegatedPowerOf2() &&
+           MulConst->countTrailingZeros() == NumBits;
+  }
   }
 }
 
 /// Fold OuterShift (InnerShift X, C1), C2.
 /// See canEvaluateShiftedShift() for the constraints on these instructions.
 static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,
                                bool IsOuterShl,
                                InstCombiner::BuilderTy &Builder) {
case Instruction::PHI: {
     // get into trouble with cyclic PHIs here because we only consider
     // instructions with a single use.
     PHINode *PN = cast<PHINode>(I);
     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
       PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits,
                                               isLeftShift, IC, DL));
     return PN;
   }
+  case Instruction::Mul: {
+    assert(!isLeftShift && "Unexpected shift direction!");
+    auto *Neg = BinaryOperator::CreateNeg(I->getOperand(0));
+    IC.InsertNewInstWith(Neg, *I);
+    unsigned TypeWidth = I->getType()->getScalarSizeInBits();
+    APInt Mask = APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits);
+    auto *And = BinaryOperator::CreateAnd(Neg,
+                                          ConstantInt::get(I->getType(), Mask));
+    And->takeName(I);
+    return IC.InsertNewInstWith(And, *I);
+  }
   }
 }
 
 // If this is a bitwise operator or add with a constant RHS we might be able
 // to pull it through a shift.
 static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift,
                                          BinaryOperator *BO) {
   switch (BO->getOpcode()) {

llvm/test/Transforms/InstCombine/apint-shift.ll

;
   ret <2 x i19> %sh2
 }
 
 ; In general, we would need an 'and' for this transform, but the masked-off bits are known zero.
 ; shl (lshr X, C1), C2 --> lshr X, C1 - C2
 
 define <2 x i7> @lshr_shl_splat_vec(<2 x i7> %X) {
 ; CHECK-LABEL: @lshr_shl_splat_vec(
-; CHECK-NEXT:    [[MUL:%.*]] = mul <2 x i7> [[X:%.*]], <i7 -8, i7 -8>
-; CHECK-NEXT:    [[SH1:%.*]] = lshr exact <2 x i7> [[MUL]], <i7 1, i7 1>
-; CHECK-NEXT:    ret <2 x i7> [[SH1]]
+; CHECK-NEXT:    [[DOTNEG:%.*]] = mul <2 x i7> [[X:%.*]], <i7 60, i7 60>
+; CHECK-NEXT:    [[SH2:%.*]] = and <2 x i7> [[DOTNEG]], <i7 60, i7 60>
+; CHECK-NEXT:    ret <2 x i7> [[SH2]]
 ;
   %mul = mul <2 x i7> %X, <i7 -8, i7 -8>
   %sh1 = lshr exact <2 x i7> %mul, <i7 3, i7 3>
   %sh2 = shl nuw nsw <2 x i7> %sh1, <i7 2, i7 2>
   ret <2 x i7> %sh2
 }
 
 ; In general, we would need an 'and' for this transform, but the masked-off bits are known zero.

llvm/test/Transforms/InstCombine/shift.ll

 ;
   %s = shl i8 12, %x ; 0b00001100
   %r = and i8 %s, 7  ; 0b00000111
   ret i8 %r
 }
 
 define i64 @lshr_mul_negpow2(i64 %x) {
 ; CHECK-LABEL: @lshr_mul_negpow2(
-; CHECK-NEXT:    [[A:%.*]] = mul i64 [[X:%.*]], -4294967296
-; CHECK-NEXT:    [[B:%.*]] = lshr exact i64 [[A]], 32
-; CHECK-NEXT:    ret i64 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = and i64 [[TMP1]], 4294967295
+; CHECK-NEXT:    ret i64 [[A]]
 ;
   %a = mul i64 %x, -4294967296
   %b = lshr i64 %a, 32
   ret i64 %b
 }
 
 define i64 @lshr_mul_negpow2_2(i64 %x) {
 ; CHECK-LABEL: @lshr_mul_negpow2_2(
-; CHECK-NEXT:    [[A:%.*]] = mul i64 [[X:%.*]], -65536
-; CHECK-NEXT:    [[B:%.*]] = lshr exact i64 [[A]], 16
-; CHECK-NEXT:    ret i64 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = and i64 [[TMP1]], 281474976710655
+; CHECK-NEXT:    ret i64 [[A]]
 ;
   %a = mul i64 %x, -65536
   %b = lshr i64 %a, 16
   ret i64 %b
 }
 
 define <2 x i32> @lshr_mul_negpow2_3(<2 x i32> %x) {
 ; CHECK-LABEL: @lshr_mul_negpow2_3(
-; CHECK-NEXT:    [[A:%.*]] = mul <2 x i32> [[X:%.*]], <i32 -16777216, i32 -16777216>
-; CHECK-NEXT:    [[B:%.*]] = lshr exact <2 x i32> [[A]], <i32 24, i32 24>
-; CHECK-NEXT:    ret <2 x i32> [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub <2 x i32> zeroinitializer, [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = and <2 x i32> [[TMP1]], <i32 255, i32 255>
+; CHECK-NEXT:    ret <2 x i32> [[A]]
 ;
   %a = mul <2 x i32> %x, <i32 -16777216, i32 -16777216>
   %b = lshr <2 x i32> %a, <i32 24, i32 24>
   ret <2 x i32>  %b
 }
 
 define i32 @lshr_mul_negpow2_4(i32 %x) {
 ; CHECK-LABEL: @lshr_mul_negpow2_4(
-; CHECK-NEXT:    [[A:%.*]] = mul i32 [[X:%.*]], -65536
-; CHECK-NEXT:    [[B:%.*]] = lshr exact i32 [[A]], 16
-; CHECK-NEXT:    [[C:%.*]] = xor i32 [[B]], 1
-; CHECK-NEXT:    ret i32 [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 0, [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = and i32 [[TMP1]], 65535
+; CHECK-NEXT:    [[B:%.*]] = xor i32 [[A]], 1
+; CHECK-NEXT:    ret i32 [[B]]
 ;
   %a = mul i32 %x, -65536
   %b = xor i32 %a, 65536
   %c = lshr i32 %b, 16
   ret i32 %c
 }
 
 define <2 x i32> @lshr_mul_negpow2_5(<2 x i32> %x) {
 ; CHECK-LABEL: @lshr_mul_negpow2_5(
-; CHECK-NEXT:    [[A:%.*]] = mul <2 x i32> [[X:%.*]], <i32 -65536, i32 -65536>
-; CHECK-NEXT:    [[B:%.*]] = lshr exact <2 x i32> [[A]], <i32 16, i32 16>
-; CHECK-NEXT:    [[C:%.*]] = or <2 x i32> [[B]], <i32 8, i32 8>
-; CHECK-NEXT:    ret <2 x i32> [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub <2 x i32> zeroinitializer, [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = and <2 x i32> [[TMP1]], <i32 65527, i32 65527>
+; CHECK-NEXT:    [[B:%.*]] = or <2 x i32> [[A]], <i32 8, i32 8>
+; CHECK-NEXT:    ret <2 x i32> [[B]]
 ;
   %a = mul <2 x i32> %x, <i32 -65536, i32 -65536>
   %b = or <2 x i32> %a, <i32 524288, i32 524288>
   %c = lshr <2 x i32> %b, <i32 16, i32 16>
   ret <2 x i32> %c
 }
 
 define i64 @lshr_mul_negpow2_extra_use(i64 %x) {