[InstCombine] improve demanded bits analysis of left-shifted operand

[spatel]

Summary

If we don't demand high bits, then we also don't care about those high bits of a left-shift operand regardless of shift amount.
I noticed the sext/trunc pattern in a motivating example.
It seems like there should be a low-bits with right-shift sibling, but I haven't looked at that yet.

https://alive2.llvm.org/ce/z/JuS6jc
https://rise4fun.com/Alive/Trm (not sure how to use 'width' with Alive1)
https://alive2.llvm.org/ce/z/gRadbF

[spatel]

llvm/test/Transforms/InstCombine/rotate.ll

446–447

The extra trunc now matches the test below this one. We're using MaskedValueIsZero() to match the funnel/rotate operand, so it's not clear how to tell if they start at the same value in this case. CSE should take care of it.

[nikic]

LGTM

[spatel]

For reference, this patch missed a requirement: we have to drop poison flags on the shl as part of the transform.
Otherwise, we can miscompile as shown in:
https://llvm.org/PR50341
Should be fixed with:
e82db87fb102

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

if (match(I->getOperand(1), m_APInt(SA))) {
         if (SignBitZero)
           Known.Zero.setSignBit();
         else if (SignBitOne)
           Known.One.setSignBit();
         if (Known.hasConflict())
           return UndefValue::get(I->getType());
       }
     } else {
+      // This is a variable shift, so we can't shift the demand mask by a known
+      // amount. But if we are not demanding high bits, then we are not
+      // demanding those bits from the pre-shifted operand either.
+      if (unsigned CTLZ = DemandedMask.countLeadingZeros()) {
+        APInt DemandedFromOp(APInt::getLowBitsSet(BitWidth, BitWidth - CTLZ));
+        if (SimplifyDemandedBits(I, 0, DemandedFromOp, Known, Depth + 1))
+          return I;
+      }
       computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
   case Instruction::LShr: {
     const APInt *SA;
     if (match(I->getOperand(1), m_APInt(SA))) {
       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);

llvm/test/Transforms/InstCombine/rotate.ll

 ; The right-shifted value does not need to be a zexted value; here it is masked.
 ; The shift mask could be less than the bitwidth, but this is still ok.
 
 define i8 @rotate_right_commute_8bit_unmasked_shl(i32 %v, i32 %shift) {
 ; CHECK-LABEL: @rotate_right_commute_8bit_unmasked_shl(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[SHIFT:%.*]] to i8
 ; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = trunc i32 [[V:%.*]] to i8
-; CHECK-NEXT:    [[CONV2:%.*]] = call i8 @llvm.fshr.i8(i8 [[TMP3]], i8 [[TMP3]], i8 [[TMP2]])
+; CHECK-NEXT:    [[TMP4:%.*]] = trunc i32 [[V]] to i8
+; CHECK-NEXT:    [[CONV2:%.*]] = call i8 @llvm.fshr.i8(i8 [[TMP3]], i8 [[TMP4]], i8 [[TMP2]])
 ; CHECK-NEXT:    ret i8 [[CONV2]]
 ;
   %and = and i32 %shift, 3
   %conv = and i32 %v, 255
   %shr = lshr i32 %conv, %and
   %sub = sub i32 8, %and
   %shl = shl i32 %conv, %sub
   %or = or i32 %shr, %shl

llvm/test/Transforms/InstCombine/shl-demand.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 define i16 @sext_shl_trunc_same_size(i16 %x, i32 %y) {
 ; CHECK-LABEL: @sext_shl_trunc_same_size(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[X:%.*]] to i32
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV]], [[Y:%.*]]
+; CHECK-NEXT:    [[CONV1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV1]], [[Y:%.*]]
 ; CHECK-NEXT:    [[T:%.*]] = trunc i32 [[SHL]] to i16
 ; CHECK-NEXT:    ret i16 [[T]]
 ;
   %conv = sext i16 %x to i32
   %shl = shl i32 %conv, %y
   %t = trunc i32 %shl to i16
   ret i16 %t
 }
 
 define i5 @sext_shl_trunc_smaller(i16 %x, i32 %y) {
 ; CHECK-LABEL: @sext_shl_trunc_smaller(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[X:%.*]] to i32
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV]], [[Y:%.*]]
+; CHECK-NEXT:    [[CONV1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV1]], [[Y:%.*]]
 ; CHECK-NEXT:    [[T:%.*]] = trunc i32 [[SHL]] to i5
 ; CHECK-NEXT:    ret i5 [[T]]
 ;
   %conv = sext i16 %x to i32
   %shl = shl i32 %conv, %y
   %t = trunc i32 %shl to i5
   ret i5 %t
 }
 
+; negative test - demanding 1 high-bit too many to change the extend
+
 define i17 @sext_shl_trunc_larger(i16 %x, i32 %y) {
 ; CHECK-LABEL: @sext_shl_trunc_larger(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[X:%.*]] to i32
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV]], [[Y:%.*]]
 ; CHECK-NEXT:    [[T:%.*]] = trunc i32 [[SHL]] to i17
 ; CHECK-NEXT:    ret i17 [[T]]
 ;
   %conv = sext i16 %x to i32
   %shl = shl i32 %conv, %y
   %t = trunc i32 %shl to i17
   ret i17 %t
 }
 
 define i32 @sext_shl_mask(i16 %x, i32 %y) {
 ; CHECK-LABEL: @sext_shl_mask(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[X:%.*]] to i32
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV]], [[Y:%.*]]
+; CHECK-NEXT:    [[CONV1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV1]], [[Y:%.*]]
 ; CHECK-NEXT:    [[T:%.*]] = and i32 [[SHL]], 65535
 ; CHECK-NEXT:    ret i32 [[T]]
 ;
   %conv = sext i16 %x to i32
   %shl = shl i32 %conv, %y
   %t = and i32 %shl, 65535
   ret i32 %t
 }
 
+; negative test - demanding a bit that could change with sext
+
 define i32 @sext_shl_mask_higher(i16 %x, i32 %y) {
 ; CHECK-LABEL: @sext_shl_mask_higher(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[X:%.*]] to i32
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV]], [[Y:%.*]]
 ; CHECK-NEXT:    [[T:%.*]] = and i32 [[SHL]], 65536
 ; CHECK-NEXT:    ret i32 [[T]]
 ;
   %conv = sext i16 %x to i32
   %shl = shl i32 %conv, %y
   %t = and i32 %shl, 65536
   ret i32 %t
 }
 
+; May need some, but not all of the bits set by the 'or'.
+
 define i32 @set_shl_mask(i32 %x, i32 %y) {
 ; CHECK-LABEL: @set_shl_mask(
-; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X:%.*]], 196609
+; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X:%.*]], 65537
 ; CHECK-NEXT:    [[S:%.*]] = shl i32 [[Z]], [[Y:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[S]], 65536
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %z = or i32 %x, 196609
   %s = shl i32 %z, %y
   %r = and i32 %s, 65536
   ret i32 %r
 }