[InstCombine] Dropping redundant masking before right-shift (PR42456)

[lebedev.ri]

Summary

If we have:
(X & (-1 << Y)) outer>> Y
Or non-canonical
((X inner>> Y) << Y) outer>> Y
The mask is redundant, and can be dropped:
X outer>> Y
This is valid for both lshr and ashr` in both positions and any combination.
https://rise4fun.com/Alive/Vf1p

We must not preserve exact:
https://rise4fun.com/Alive/DYq
https://rise4fun.com/Alive/JXjy

Should fix PR42456

[lebedev.ri]

Will get back to this.

lib/Transforms/InstCombine/InstCombineShifts.cpp

if (ShiftOpcode == Instruction::BinaryOps::Shl) {
     NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() &&
                                  Sh1->hasNoSignedWrap());
   } else {
     NewShift->setIsExact(Sh0->isExact() && Sh1->isExact());
   }
   return NewShift;
 }
 
+// If we have:
+//   (X & (-1 << Y)) outer>> Y
+// Or
+//   ((X inner>> Y) << Y) outer>> Y
+// The mask is redundant, and can be dropped:
+//   X outer>> Y
+// This is valid for both lshr and ashr in both positions and any combination.
+static Instruction *
+dropRedundantMaskingOfRightShiftInput(BinaryOperator *OuterShift) {
+  Value *Y;
+  if (!match(OuterShift, m_Shr(m_Value(), m_Value(Y))))
+    return nullptr;
+
+  Value *X;
+
+  // (-1 << Y)
+  auto Mask = m_Shl(m_AllOnes(), m_Specific(Y));
+  // (X & (-1 << Y))
+  auto MaskVariant = m_c_And(Mask, m_Value(X));
+
+  // ((X inner>> Y) << Y)
+  auto ShiftVariant = m_Shl(m_Shr(m_Value(X), m_Specific(Y)), m_Specific(Y));
+
+  if (!match(OuterShift->getOperand(0), m_CombineOr(MaskVariant, ShiftVariant)))
+    return nullptr;
+
+  return BinaryOperator::Create(OuterShift->getOpcode(), X, Y);
+}
+
 Instruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   assert(Op0->getType() == Op1->getType());
 
   // See if we can fold away this shift.
   if (SimplifyDemandedInstructionBits(I))
     return &I;
 
   // Try to fold constant and into select arguments.
   if (isa<Constant>(Op0))
     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
       if (Instruction *R = FoldOpIntoSelect(I, SI))
         return R;
 
   if (Constant *CUI = dyn_cast<Constant>(Op1))
     if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
       return Res;
 
   if (Instruction *NewShift =
           reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ))
     return NewShift;
 
+  if (Instruction *NewShift = dropRedundantMaskingOfRightShiftInput(&I))
+    return NewShift;
+
   // (C1 shift (A add C2)) -> (C1 shift C2) shift A)
   // iff A and C2 are both positive.
   Value *A;
   Constant *C;
   if (match(Op0, m_Constant()) && match(Op1, m_Add(m_Value(A), m_Constant(C))))
     if (isKnownNonNegative(A, DL, 0, &AC, &I, &DT) &&
         isKnownNonNegative(C, DL, 0, &AC, &I, &DT))
       return BinaryOperator::Create(

test/Transforms/InstCombine/redundant-shift-input-masking.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; If we have:
 ;   (data & (-1 << nbits)) outer>> nbits
 ; Or
 ;   ((data inner>> nbits) << nbits) outer>> nbits
 ; The mask is redundant, and can be dropped:
 ;   data outer>> nbits
 ; This is valid for both lshr and ashr in both positions and any combination.
 ; We must *not* preserve 'exact' on that final right-shift.
 
 define i32 @t0_lshr(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t0_lshr(
-; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[DATA:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = lshr exact i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[DATA:%.*]], [[NBITS:%.*]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = shl i32 -1, %nbits
   %t1 = and i32 %t0, %data
   %t2 = lshr exact i32 %t1, %nbits ; while there, test that we *don't* propagate 'exact'
   ret i32 %t2
 }
 define i32 @t1_sshr(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t1_sshr(
-; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[DATA:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = ashr exact i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = ashr i32 [[DATA:%.*]], [[NBITS:%.*]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = shl i32 -1, %nbits
   %t1 = and i32 %t0, %data
   %t2 = ashr exact i32 %t1, %nbits ; while there, test that we *don't* propagate 'exact'
   ret i32 %t2
 }
 
 ; Vectors
 
 define <4 x i32> @t2_vec(<4 x i32> %data, <4 x i32> %nbits) {
 ; CHECK-LABEL: @t2_vec(
-; CHECK-NEXT:    [[T0:%.*]] = shl <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = and <4 x i32> [[T0]], [[DATA:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = lshr <4 x i32> [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr <4 x i32> [[DATA:%.*]], [[NBITS:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T2]]
 ;
   %t0 = shl <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>, %nbits
   %t1 = and <4 x i32> %t0, %data
   %t2 = lshr <4 x i32> %t1, %nbits
   ret <4 x i32> %t2
 }
 
 define <4 x i32> @t3_vec_undef(<4 x i32> %data, <4 x i32> %nbits) {
 ; CHECK-LABEL: @t3_vec_undef(
-; CHECK-NEXT:    [[T0:%.*]] = shl <4 x i32> <i32 -1, i32 -1, i32 undef, i32 -1>, [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = and <4 x i32> [[T0]], [[DATA:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = lshr <4 x i32> [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr <4 x i32> [[DATA:%.*]], [[NBITS:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T2]]
 ;
   %t0 = shl <4 x i32> <i32 -1, i32 -1, i32 undef, i32 -1>, %nbits
   %t1 = and <4 x i32> %t0, %data
   %t2 = lshr <4 x i32> %t1, %nbits
   ret <4 x i32> %t2
 }
 
 ; Extra uses
 
 declare void @use32(i32)
 
 define i32 @t4_extrause0(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t4_extrause0(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[DATA:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[DATA:%.*]], [[NBITS]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = shl i32 -1, %nbits
   call void @use32(i32 %t0)
   %t1 = and i32 %t0, %data
   %t2 = lshr i32 %t1, %nbits
   ret i32 %t2
 }
 
 define i32 @t5_extrause1(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t5_extrause1(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[DATA:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[DATA]], [[NBITS]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = shl i32 -1, %nbits
   %t1 = and i32 %t0, %data
   call void @use32(i32 %t1)
   %t2 = lshr i32 %t1, %nbits
   ret i32 %t2
 }
 
 define i32 @t6_extrause2(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t6_extrause2(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[DATA:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[DATA]], [[NBITS]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = shl i32 -1, %nbits
   call void @use32(i32 %t0)
   %t1 = and i32 %t0, %data
   call void @use32(i32 %t1)
   %t2 = lshr i32 %t1, %nbits
   ret i32 %t2
 }
 
 ; Non-canonical mask pattern. Let's just test a single case with all-extra uses.
 
 define i32 @t7_noncanonical_lshr_lshr_extrauses(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t7_noncanonical_lshr_lshr_extrauses(
 ; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[DATA:%.*]], [[NBITS:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[T0]], [[NBITS]]
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[DATA]], [[NBITS]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = lshr i32 %data, %nbits
   call void @use32(i32 %t0)
   %t1 = shl i32 %t0, %nbits
   call void @use32(i32 %t1)
   %t2 = lshr i32 %t1, %nbits
   ret i32 %t2
 }
 
 define i32 @t8_noncanonical_lshr_ashr_extrauses(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t8_noncanonical_lshr_ashr_extrauses(
 ; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[DATA:%.*]], [[NBITS:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[T0]], [[NBITS]]
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = ashr i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = ashr i32 [[DATA]], [[NBITS]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = lshr i32 %data, %nbits
   call void @use32(i32 %t0)
   %t1 = shl i32 %t0, %nbits
   call void @use32(i32 %t1)
   %t2 = ashr i32 %t1, %nbits
   ret i32 %t2
 }
 
 define i32 @t9_noncanonical_ashr_lshr_extrauses(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t9_noncanonical_ashr_lshr_extrauses(
 ; CHECK-NEXT:    [[T0:%.*]] = ashr i32 [[DATA:%.*]], [[NBITS:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[T0]], [[NBITS]]
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[DATA]], [[NBITS]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = ashr i32 %data, %nbits
   call void @use32(i32 %t0)
   %t1 = shl i32 %t0, %nbits
   call void @use32(i32 %t1)
   %t2 = lshr i32 %t1, %nbits
   ret i32 %t2
 }
 
 define i32 @t10_noncanonical_ashr_ashr_extrauses(i32 %data, i32 %nbits) {
 ; CHECK-LABEL: @t10_noncanonical_ashr_ashr_extrauses(
 ; CHECK-NEXT:    [[T0:%.*]] = ashr i32 [[DATA:%.*]], [[NBITS:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[T0]], [[NBITS]]
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = ashr i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = ashr i32 [[DATA]], [[NBITS]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = ashr i32 %data, %nbits
   call void @use32(i32 %t0)
   %t1 = shl i32 %t0, %nbits
   call void @use32(i32 %t1)
   %t2 = ashr i32 %t1, %nbits
   ret i32 %t2
 }
 
 ; Commutativity
 
 declare i32 @gen32()
 
 define i32 @t11_commutative(i32 %nbits) {
 ; CHECK-LABEL: @t11_commutative(
 ; CHECK-NEXT:    [[DATA:%.*]] = call i32 @gen32()
-; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = and i32 [[DATA]], [[T0]]
-; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[T1]], [[NBITS]]
+; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[DATA]], [[NBITS:%.*]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %data = call i32 @gen32()
   %t0 = shl i32 -1, %nbits
   %t1 = and i32 %data, %t0 ; swapped
   %t2 = lshr i32 %t1, %nbits
   ret i32 %t2
 }