[InstCombine] Optimize away the unnecessary multi-use sign-extend

[Bhramar.vatsa]

Summary

C.f. https://bugs.llvm.org/show_bug.cgi?id=47765

Added a case for handling the sign-extend (Shl+AShr) for multiple uses, to optimize it away for an individual use, when the demanded bits aren't affected by sign-extend.

https://rise4fun.com/Alive/lgf

[RKSimon]

vector tests?

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

912

Is it worth merging the Shl matching and LeftShiftAmt == RightShiftAmt here as well?

915

Safer just to do a SRA->getValue()->ult(BitWidth) bounds check?

921

Use APInt::setLowBits ?

llvm/test/Transforms/InstCombine/simplify-multiuse-demanded-bits-ashr.ll

8 ↗

(On Diff #304805)

strip the metadata/attaributes?

[RKSimon]

Can the test cases be simplified? I'm not sure you need the multiple blocks to just check for multiuse?

[spatel]

In D91343#2392480, @RKSimon wrote:

Can the test cases be simplified? I'm not sure you need the multiple blocks to just check for multiuse?

Note that I posted an alternate version at D91364 and added tests for it. Unless I missed some corner case covered by these tests, they should not be needed now.

[Bhramar.vatsa]

I have adapted the code as per @spatel's suggestion. This also solves the comments given on earlier version by @RKSimon.

@spatel, yes, I did see the requirement for same diff in the test. So, added the test to patch with same changes as shown in D91364.

[lebedev.ri]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

904–906

s/if the demanded bits are already within original operand/if we do not demand any of the new sign bits/

[Bhramar.vatsa]

Modified the comment as suggested by @lebedev.ri

[Bhramar.vatsa]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

931

For this patch, this call will no more happen, even when the 'case AShr' doesn't match completely. So, should a call to computeKnownBits(), be added in that case?
The call isn't there for other cases, but there, perhaps it isn't needed.

[lebedev.ri]

Please do say if you need help landing this (state the name [e-mail] to be used for the git commit's Author field).

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

931

Yes, this doesn't look immediately correct to me, but it's a preexisting problem.
I think the contents of default: switch should be located after the switch.
I think it would be an interesting experiment to make that change,
but not in this review.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

931

Don't the other handlers already do the equivalent of the default?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

931

The equivalent being computing the Known - err, right, they do.

[Bhramar.vatsa]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

931

So, then, perhaps in the favor of not changing the functionality when optimization doesn't take place, should the code for the default case be added for 'AShr' case too?
If agreed, I will provide another patch with this change.

[Bhramar.vatsa]

Added the missing computation of Known bits for the case Instruction::AShr. This should result in no change of functionality except when intended.

Thanks @lebedev.ri , please help in landing this. Please use Name: Bhramar Vatsa, e-mail : [e-mail]

[jeroen.dobbelaere]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

922–925

Maybe this should be moved between line 904 and 906 ? (After the computKnownBits, but before checking the signextend pattern). This brings it more in line how the other cases are handled, preferring to return a constant when that is possible.

[Bhramar.vatsa]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

922–925

Yes, I agree.

[Bhramar.vatsa]

Restructured the code as suggested by @jeroen.dobbelaere

[Bhramar.vatsa]

Apologies for wrong patch (repeat of previous). I have now put up the latest patch. Please review and accept.

[jeroen.dobbelaere]

Looks good to me.

[fhahn]

This appears to cause the following crash: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=32759

It would be great if you could take a look. Reproducer test case linked on the page is https://oss-fuzz.com/download?testcase_id=5658887807172608 , crashes when running opt -instcombine

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

921

Its possible that the shift amount is out of bounds - add a check for ShiftLC->ult(BitWidth) ?

[jeroen.dobbelaere]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

921

Yes, that seems to be the case. I am looking for a fix.

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

case Instruction::Xor: {
     // other.
     if (DemandedMask.isSubsetOf(RHSKnown.Zero))
       return I->getOperand(0);
     if (DemandedMask.isSubsetOf(LHSKnown.Zero))
       return I->getOperand(1);
 
     break;
   }
+  case Instruction::AShr: {
+    // Compute the Known bits to simplify things downstream.
+    computeKnownBits(I, Known, Depth, CxtI);
+
+    // If this user is only demanding bits that we know, return the known
+    // constant.
+    if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
+      return Constant::getIntegerValue(ITy, Known.One);
+
+    // If the right shift operand 0 is a result of a left shift by the same
+    // amount, this is probably a zero/sign extension, which may be unnecessary,
+    // if we do not demand any of the new sign bits. So, return the original
+    // operand instead.
+    const APInt *ShiftRC;
+    const APInt *ShiftLC;
+    Value *X;
+    unsigned BitWidth = DemandedMask.getBitWidth();
+    if (match(I,
+              m_AShr(m_Shl(m_Value(X), m_APInt(ShiftLC)), m_APInt(ShiftRC))) &&
+        ShiftLC == ShiftRC &&
+        DemandedMask.isSubsetOf(APInt::getLowBitsSet(
+            BitWidth, BitWidth - ShiftRC->getZExtValue()))) {
+      return X;
+    }
+
+    break;
+  }
   default:
     // Compute the Known bits to simplify things downstream.
     computeKnownBits(I, Known, Depth, CxtI);
 
     // If this user is only demanding bits that we know, return the known
     // constant.
     if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
       return Constant::getIntegerValue(ITy, Known.One);
 
     break;
   }

llvm/test/Transforms/InstCombine/and.ll

;
   ret <2 x i59> %r
 }
 
 define i32 @lowmask_sext_in_reg(i32 %x) {
 ; CHECK-LABEL: @lowmask_sext_in_reg(
 ; CHECK-NEXT:    [[L:%.*]] = shl i32 [[X:%.*]], 20
 ; CHECK-NEXT:    [[R:%.*]] = ashr exact i32 [[L]], 20
 ; CHECK-NEXT:    call void @use32(i32 [[R]])
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[R]], 4095
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X]], 4095
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %l = shl i32 %x, 20
   %r = ashr i32 %l, 20
   call void @use32(i32 %r)
   %and = and i32 %r, 4095
   ret i32 %and
 }
 
+; Negative test - mismatched shift amounts
+
 define i32 @lowmask_not_sext_in_reg(i32 %x) {
 ; CHECK-LABEL: @lowmask_not_sext_in_reg(
 ; CHECK-NEXT:    [[L:%.*]] = shl i32 [[X:%.*]], 19
 ; CHECK-NEXT:    [[R:%.*]] = ashr i32 [[L]], 20
 ; CHECK-NEXT:    call void @use32(i32 [[R]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[R]], 4095
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %l = shl i32 %x, 19
   %r = ashr i32 %l, 20
   call void @use32(i32 %r)
   %and = and i32 %r, 4095
   ret i32 %and
 }
 
+; Negative test - too much shift for mask
+
 define i32 @not_lowmask_sext_in_reg(i32 %x) {
 ; CHECK-LABEL: @not_lowmask_sext_in_reg(
 ; CHECK-NEXT:    [[L:%.*]] = shl i32 [[X:%.*]], 20
 ; CHECK-NEXT:    [[R:%.*]] = ashr exact i32 [[L]], 20
 ; CHECK-NEXT:    call void @use32(i32 [[R]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[R]], 4096
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %l = shl i32 %x, 20
   %r = ashr i32 %l, 20
   call void @use32(i32 %r)
   %and = and i32 %r, 4096
   ret i32 %and
 }
 
+; Negative test - too much shift for mask
+
 define i32 @not_lowmask_sext_in_reg2(i32 %x) {
 ; CHECK-LABEL: @not_lowmask_sext_in_reg2(
 ; CHECK-NEXT:    [[L:%.*]] = shl i32 [[X:%.*]], 21
 ; CHECK-NEXT:    [[R:%.*]] = ashr exact i32 [[L]], 21
 ; CHECK-NEXT:    call void @use32(i32 [[R]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[R]], 4095
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %l = shl i32 %x, 21
   %r = ashr i32 %l, 21
   call void @use32(i32 %r)
   %and = and i32 %r, 4095
   ret i32 %and
 }
 
 define <2 x i32> @lowmask_sext_in_reg_splat(<2 x i32> %x, <2 x i32>* %p) {
 ; CHECK-LABEL: @lowmask_sext_in_reg_splat(
 ; CHECK-NEXT:    [[L:%.*]] = shl <2 x i32> [[X:%.*]], <i32 20, i32 20>
 ; CHECK-NEXT:    [[R:%.*]] = ashr exact <2 x i32> [[L]], <i32 20, i32 20>
 ; CHECK-NEXT:    store <2 x i32> [[R]], <2 x i32>* [[P:%.*]], align 8
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[R]], <i32 4095, i32 4095>
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X]], <i32 4095, i32 4095>
 ; CHECK-NEXT:    ret <2 x i32> [[AND]]
 ;
   %l = shl <2 x i32> %x, <i32 20, i32 20>
   %r = ashr <2 x i32> %l, <i32 20, i32 20>
   store <2 x i32> %r, <2 x i32>* %p
   %and = and <2 x i32> %r, <i32 4095, i32 4095>
   ret <2 x i32> %and
 }