[InstCombine] dropRedundantMaskingOfLeftShiftInput(): pat. c/d/e with mask (PR42563)

[lebedev.ri]

Summary

If we have a pattern (x & (-1 >> maskNbits)) << shiftNbits,
we already know (have a fold) that will drop the & (-1 >> maskNbits)
mask iff (shiftNbits-maskNbits) s>= 0 (i.e. shiftNbits u>= maskNbits).

So even if (shiftNbits-maskNbits) s< 0, we can still
fold, we will just need to apply a constant mask afterwards:

Name: c, normal+mask
  %t0 = lshr i32 -1, C1
  %t1 = and i32 %t0, %x
  %r = shl i32 %t1, C2
=>
  %n0 = shl i32 %x, C2
  %n1 = i32 ((-(C2-C1))+32)
  %n2 = zext i32 %n1 to i64 
  %n3 = lshr i64 -1, %n2
  %n4 = trunc i64 %n3 to i32
  %r = and i32 %n0, %n4

https://rise4fun.com/Alive/gslRa

Naturally, old %masked will have to be one-use.
This is not valid for pattern f - where "masking" is done via ashr.

https://bugs.llvm.org/show_bug.cgi?id=42563

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

216–220

This is duplicated, will later hoist into Type itself.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

207

Did we ensure that Masked is not a ConstantExpr? If so, add an assert that Masked must be an Instruction here or somewhere above here?

[lebedev.ri]

Avoid constantexpr pitfail.
I'm not adding a test - i tried to come up with it, but it does not match.

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

207

*sigh*

[lebedev.ri]

Err, actually upload the correct patch.

[spatel]

LGTM

[lebedev.ri]

In D67725#1679374, @spatel wrote:

LGTM

Thank you for the review!

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

auto *ShAmtsDiff = dyn_cast_or_null<Constant>(
         SimplifySubInst(ShiftShAmt, MaskShAmt, /*IsNSW=*/false, /*IsNUW=*/false,
                         SQ.getWithInstruction(OuterShift)));
     if (!ShAmtsDiff)
       return nullptr; // Did not simplify.
     // In this pattern ShAmtsDiff correlates with the number of high bits that
     // shall be unset in the root value (OuterShift). If ShAmtsDiff is negative,
     // we'll need to also produce a mask to unset ShAmtsDiff high bits.
     // So, does *any* channel need a mask? (is ShiftShAmt u>= MaskShAmt ?)
-    if (!match(ShAmtsDiff, m_NonNegative()))
-      return nullptr; // FIXME.
-    // All good, we can do this fold.
+    if (!match(ShAmtsDiff, m_NonNegative())) {
+      // This sub-fold (with mask) is invalid for 'ashr' "masking" instruction.
+      if (cast<Instruction>(Masked)->isArithmeticShift())
+        return nullptr;
+      // For a mask we need to get rid of old masking instruction.
+      if (!Masked->hasOneUse())
+        return nullptr; // Else we can't perform the fold.
+      Type *Ty = X->getType();
+      unsigned BitWidth = Ty->getScalarSizeInBits();
+      // We should produce compute the mask in wider type, and truncate later!
+      // Get type twice as wide element-wise (same number of elements!).
+      Type *ExtendedScalarTy = Type::getIntNTy(Ty->getContext(), 2 * BitWidth);
+      Type *ExtendedTy =
+          Ty->isVectorTy()
+              ? VectorType::get(ExtendedScalarTy, Ty->getVectorNumElements())
+              : ExtendedScalarTy;
+      auto *ExtendedNumHighBitsToClear = ConstantExpr::getZExt(
+          ConstantExpr::getAdd(
+              ConstantExpr::getNeg(ShAmtsDiff),
+              ConstantInt::get(Ty, BitWidth, /*isSigned=*/false)),
+          ExtendedTy);
+      // And compute the mask as usual: (-1 l>> (ShAmtsDiff))
+      auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);
+      auto *ExtendedMask =
+          ConstantExpr::getLShr(ExtendedAllOnes, ExtendedNumHighBitsToClear);
+      NewMask = ConstantExpr::getTrunc(ExtendedMask, Ty);
+    } else
       NewMask = nullptr; // No mask needed.
+    // All good, we can do this fold.
   } else
     return nullptr; // Don't know anything about this pattern.
 
   // No 'NUW'/'NSW'!
   // We no longer know that we won't shift-out non-0 bits.
   auto *NewShift =
       BinaryOperator::Create(OuterShift->getOpcode(), X, ShiftShAmt);
   if (!NewMask)

llvm/test/Transforms/InstCombine/partally-redundant-left-shift-input-masking-variant-c.ll

 
 ; Simple tests.
 
 declare void @use32(i32)
 
 define i32 @t0_basic(i32 %x, i32 %nbits) {
 ; CHECK-LABEL: @t0_basic(
 ; CHECK-NEXT:    [[T0:%.*]] = lshr i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[X:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = add i32 [[NBITS]], -1
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
-; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[T1]], [[T2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], [[T2]]
+; CHECK-NEXT:    [[T3:%.*]] = and i32 [[TMP1]], 2147483647
 ; CHECK-NEXT:    ret i32 [[T3]]
 ;
   %t0 = lshr i32 -1, %nbits
   %t1 = and i32 %t0, %x
   %t2 = add i32 %nbits, -1
   call void @use32(i32 %t0)
   call void @use32(i32 %t2)
   %t3 = shl i32 %t1, %t2 ; shift is smaller than mask
   ret i32 %t3
 }
 
 ; Vectors
 
 declare void @use8xi32(<8 x i32>)
 
 define <8 x i32> @t1_vec_splat(<8 x i32> %x, <8 x i32> %nbits) {
 ; CHECK-LABEL: @t1_vec_splat(
 ; CHECK-NEXT:    [[T0:%.*]] = lshr <8 x i32> <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = and <8 x i32> [[T0]], [[X:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = add <8 x i32> [[NBITS]], <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T0]])
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T2]])
-; CHECK-NEXT:    [[T3:%.*]] = shl <8 x i32> [[T1]], [[T2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <8 x i32> [[X:%.*]], [[T2]]
+; CHECK-NEXT:    [[T3:%.*]] = and <8 x i32> [[TMP1]], <i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647>
 ; CHECK-NEXT:    ret <8 x i32> [[T3]]
 ;
   %t0 = lshr <8 x i32> <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>, %nbits
   %t1 = and <8 x i32> %t0, %x
   %t2 = add <8 x i32> %nbits, <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>
   call void @use8xi32(<8 x i32> %t0)
   call void @use8xi32(<8 x i32> %t2)
   %t3 = shl <8 x i32> %t1, %t2 ; shift is smaller than mask
   ret <8 x i32> %t3
 }
 
 define <8 x i32> @t1_vec_nonsplat(<8 x i32> %x, <8 x i32> %nbits) {
 ; CHECK-LABEL: @t1_vec_nonsplat(
 ; CHECK-NEXT:    [[T0:%.*]] = lshr <8 x i32> <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = and <8 x i32> [[T0]], [[X:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = add <8 x i32> [[NBITS]], <i32 -32, i32 -31, i32 -1, i32 0, i32 1, i32 31, i32 32, i32 33>
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T0]])
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T2]])
-; CHECK-NEXT:    [[T3:%.*]] = shl <8 x i32> [[T1]], [[T2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <8 x i32> [[X:%.*]], [[T2]]
+; CHECK-NEXT:    [[T3:%.*]] = and <8 x i32> [[TMP1]], <i32 undef, i32 1, i32 2147483647, i32 -1, i32 -1, i32 -1, i32 -1, i32 undef>
 ; CHECK-NEXT:    ret <8 x i32> [[T3]]
 ;
   %t0 = lshr <8 x i32> <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>, %nbits
   %t1 = and <8 x i32> %t0, %x
   %t2 = add <8 x i32> %nbits, <i32 -32, i32 -31, i32 -1, i32 0, i32 1, i32 31, i32 32, i32 33>
   call void @use8xi32(<8 x i32> %t0)
   call void @use8xi32(<8 x i32> %t2)
   %t3 = shl <8 x i32> %t1, %t2 ; shift is smaller than mask

llvm/test/Transforms/InstCombine/partally-redundant-left-shift-input-masking-variant-d.ll

 ; Simple tests.
 
 declare void @use32(i32)
 
 define i32 @t0_basic(i32 %x, i32 %nbits) {
 ; CHECK-LABEL: @t0_basic(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]]
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
 ; CHECK-NEXT:    [[T3:%.*]] = add i32 [[NBITS]], -1
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
-; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[T2]], [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], [[T3]]
+; CHECK-NEXT:    [[T4:%.*]] = and i32 [[TMP1]], 2147483647
 ; CHECK-NEXT:    ret i32 [[T4]]
 ;
   %t0 = shl i32 -1, %nbits
   %t1 = lshr i32 %t0, %nbits
   %t2 = and i32 %t1, %x
   %t3 = add i32 %nbits, -1
   call void @use32(i32 %t0)
   call void @use32(i32 %t1)
   call void @use32(i32 %t3)
   %t4 = shl i32 %t2, %t3 ; shift is smaller than mask
   ret i32 %t4
 }
 
 ; Vectors
 
 declare void @use8xi32(<8 x i32>)
 
 define <8 x i32> @t2_vec_splat(<8 x i32> %x, <8 x i32> %nbits) {
 ; CHECK-LABEL: @t2_vec_splat(
 ; CHECK-NEXT:    [[T0:%.*]] = shl <8 x i32> <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = lshr <8 x i32> [[T0]], [[NBITS]]
-; CHECK-NEXT:    [[T2:%.*]] = and <8 x i32> [[T1]], [[X:%.*]]
 ; CHECK-NEXT:    [[T3:%.*]] = add <8 x i32> [[NBITS]], <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T0]])
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T1]])
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T3]])
-; CHECK-NEXT:    [[T4:%.*]] = shl <8 x i32> [[T2]], [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <8 x i32> [[X:%.*]], [[T3]]
+; CHECK-NEXT:    [[T4:%.*]] = and <8 x i32> [[TMP1]], <i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647>
 ; CHECK-NEXT:    ret <8 x i32> [[T4]]
 ;
   %t0 = shl <8 x i32> <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>, %nbits
   %t1 = lshr <8 x i32> %t0, %nbits
   %t2 = and <8 x i32> %t1, %x
   %t3 = add <8 x i32> %nbits, <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>
   call void @use8xi32(<8 x i32> %t0)
   call void @use8xi32(<8 x i32> %t1)
   call void @use8xi32(<8 x i32> %t3)
   %t4 = shl <8 x i32> %t2, %t3 ; shift is smaller than mask
   ret <8 x i32> %t4
 }
 
 define <8 x i32> @t2_vec_nonsplat(<8 x i32> %x, <8 x i32> %nbits) {
 ; CHECK-LABEL: @t2_vec_nonsplat(
 ; CHECK-NEXT:    [[T0:%.*]] = shl <8 x i32> <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = lshr <8 x i32> [[T0]], [[NBITS]]
-; CHECK-NEXT:    [[T2:%.*]] = and <8 x i32> [[T1]], [[X:%.*]]
 ; CHECK-NEXT:    [[T3:%.*]] = add <8 x i32> [[NBITS]], <i32 -32, i32 -31, i32 -1, i32 0, i32 1, i32 31, i32 32, i32 33>
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T0]])
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T1]])
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T3]])
-; CHECK-NEXT:    [[T4:%.*]] = shl <8 x i32> [[T2]], [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <8 x i32> [[X:%.*]], [[T3]]
+; CHECK-NEXT:    [[T4:%.*]] = and <8 x i32> [[TMP1]], <i32 undef, i32 1, i32 2147483647, i32 -1, i32 -1, i32 -1, i32 -1, i32 undef>
 ; CHECK-NEXT:    ret <8 x i32> [[T4]]
 ;
   %t0 = shl <8 x i32> <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>, %nbits
   %t1 = lshr <8 x i32> %t0, %nbits
   %t2 = and <8 x i32> %t1, %x
   %t3 = add <8 x i32> %nbits, <i32 -32, i32 -31, i32 -1, i32 0, i32 1, i32 31, i32 32, i32 33>
   call void @use8xi32(<8 x i32> %t0)
   call void @use8xi32(<8 x i32> %t1)

llvm/test/Transforms/InstCombine/partally-redundant-left-shift-input-masking-variant-e.ll

 
 ; Simple tests.
 
 declare void @use32(i32)
 
 define i32 @t0_basic(i32 %x, i32 %nbits) {
 ; CHECK-LABEL: @t0_basic(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]]
 ; CHECK-NEXT:    [[T2:%.*]] = add i32 [[NBITS]], -1
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
-; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[T1]], [[T2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X]], [[T2]]
+; CHECK-NEXT:    [[T3:%.*]] = and i32 [[TMP1]], 2147483647
 ; CHECK-NEXT:    ret i32 [[T3]]
 ;
   %t0 = shl i32 %x, %nbits
   %t1 = lshr i32 %t0, %nbits
   %t2 = add i32 %nbits, -1
   call void @use32(i32 %t0)
   call void @use32(i32 %t2)
   %t3 = shl i32 %t1, %t2 ; shift is smaller than mask
   ret i32 %t3
 }
 
 ; Vectors
 
 declare void @use8xi32(<8 x i32>)
 
 define <8 x i32> @t1_vec_splat(<8 x i32> %x, <8 x i32> %nbits) {
 ; CHECK-LABEL: @t1_vec_splat(
 ; CHECK-NEXT:    [[T0:%.*]] = shl <8 x i32> [[X:%.*]], [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = lshr <8 x i32> [[T0]], [[NBITS]]
 ; CHECK-NEXT:    [[T2:%.*]] = add <8 x i32> [[NBITS]], <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T0]])
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T2]])
-; CHECK-NEXT:    [[T3:%.*]] = shl <8 x i32> [[T1]], [[T2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <8 x i32> [[X]], [[T2]]
+; CHECK-NEXT:    [[T3:%.*]] = and <8 x i32> [[TMP1]], <i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647>
 ; CHECK-NEXT:    ret <8 x i32> [[T3]]
 ;
   %t0 = shl <8 x i32> %x, %nbits
   %t1 = lshr <8 x i32> %t0, %nbits
   %t2 = add <8 x i32> %nbits, <i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1, i32 -1>
   call void @use8xi32(<8 x i32> %t0)
   call void @use8xi32(<8 x i32> %t2)
   %t3 = shl <8 x i32> %t1, %t2 ; shift is smaller than mask
   ret <8 x i32> %t3
 }
 
 define <8 x i32> @t1_vec_nonsplat(<8 x i32> %x, <8 x i32> %nbits) {
 ; CHECK-LABEL: @t1_vec_nonsplat(
 ; CHECK-NEXT:    [[T0:%.*]] = shl <8 x i32> [[X:%.*]], [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = lshr <8 x i32> [[T0]], [[NBITS]]
 ; CHECK-NEXT:    [[T2:%.*]] = add <8 x i32> [[NBITS]], <i32 -32, i32 -31, i32 -1, i32 0, i32 1, i32 31, i32 32, i32 33>
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T0]])
 ; CHECK-NEXT:    call void @use8xi32(<8 x i32> [[T2]])
-; CHECK-NEXT:    [[T3:%.*]] = shl <8 x i32> [[T1]], [[T2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <8 x i32> [[X]], [[T2]]
+; CHECK-NEXT:    [[T3:%.*]] = and <8 x i32> [[TMP1]], <i32 undef, i32 1, i32 2147483647, i32 -1, i32 -1, i32 -1, i32 -1, i32 undef>
 ; CHECK-NEXT:    ret <8 x i32> [[T3]]
 ;
   %t0 = shl <8 x i32> %x, %nbits
   %t1 = lshr <8 x i32> %t0, %nbits
   %t2 = add <8 x i32> %nbits, <i32 -32, i32 -31, i32 -1, i32 0, i32 1, i32 31, i32 32, i32 33>
   call void @use8xi32(<8 x i32> %t0)
   call void @use8xi32(<8 x i32> %t2)
   %t3 = shl <8 x i32> %t1, %t2 ; shift is smaller than mask