[InstSimplify] shl nuw C, %x -> C iff signbit is set on C.

[lebedev.ri]

Summary

%r = shl nuw i8 C, %x

As per langref:

If the nuw keyword is present, then the shift produces
a poison value if it shifts out any non-zero bits.

Thus, if the sign bit is set on C, then %x can only be 0, which means that %r can only be C.
Or in other words, set sign bit means that the signed value is negative, so the constant is <= 0.

https://rise4fun.com/Alive/WMk
https://rise4fun.com/Alive/udv

Was mentioned in D47428 review.

We already handle the 0 constant, https://godbolt.org/g/UZq1sJ, so this only handles negative constants.

FIXME: could also use KnownBits.

[lebedev.ri]

Actually run ninja check-llvm this time.

[spatel]

LGTM.

Watch out for seemingly unrelated failures though - any time we get smarter about optimizing using these flags, there's a chance that we will expose bugs in other parts of the optimizer.

[lebedev.ri]

Rebased, NFC.

[lebedev.ri]

In D47883#1125194, @spatel wrote:

LGTM.

Watch out for seemingly unrelated failures though - any time we get smarter about optimizing using these flags, there's a chance that we will expose bugs in other parts of the optimizer.

Thank you for the review and a advice!

Posted KnownBits part as follow-up (D47891), but even that isn't sufficient to handle *all* the cases.

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
   // undef << X -> undef if (if it's NSW/NUW)
   if (match(Op0, m_Undef()))
     return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType());
 
   // (X >> A) << A -> X
   Value *X;
   if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
     return X;
+
+  // shl nuw i8 C, %x  ->  C  iff C has sign bit set.
+  if (isNUW && match(Op0, m_Negative()))
+    return Op0;
+  // NOTE: could use computeKnownBits() / LazyValueInfo,
+  // but the cost-benefit analysis suggests it isn't worth it.
+
   return nullptr;
 }
 
 Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
                              const SimplifyQuery &Q) {
   return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
 }
 

llvm/trunk/test/Transforms/InstCombine/set-lowbits-mask-canonicalize.ll

 ;
   %setbit = shl i32 1, %NBits
   %ret = add nsw i32 %setbit, -1
   ret i32 %ret
 }
 
 define i32 @shl_add_nuw(i32 %NBits) {
 ; CHECK-LABEL: @shl_add_nuw(
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 0
 ;
   %setbit = shl i32 1, %NBits
   %ret = add nuw i32 %setbit, -1
   ret i32 %ret
 }
 
 define i32 @shl_add_nsw_nuw(i32 %NBits) {
 ; CHECK-LABEL: @shl_add_nsw_nuw(
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 0
 ;
   %setbit = shl i32 1, %NBits
   %ret = add nuw nsw i32 %setbit, -1
   ret i32 %ret
 }
 
 ; shl is nsw
 

 ;
   %setbit = shl nsw i32 1, %NBits
   %ret = add nsw i32 %setbit, -1
   ret i32 %ret
 }
 
 define i32 @shl_nsw_add_nuw(i32 %NBits) {
 ; CHECK-LABEL: @shl_nsw_add_nuw(
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 0
 ;
   %setbit = shl nsw i32 1, %NBits
   %ret = add nuw i32 %setbit, -1
   ret i32 %ret
 }
 
 define i32 @shl_nsw_add_nsw_nuw(i32 %NBits) {
 ; CHECK-LABEL: @shl_nsw_add_nsw_nuw(
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 0
 ;
   %setbit = shl nsw i32 1, %NBits
   %ret = add nuw nsw i32 %setbit, -1
   ret i32 %ret
 }
 
 ; shl is nuw
 

 ;
   %setbit = shl nuw i32 1, %NBits
   %ret = add nsw i32 %setbit, -1
   ret i32 %ret
 }
 
 define i32 @shl_nuw_add_nuw(i32 %NBits) {
 ; CHECK-LABEL: @shl_nuw_add_nuw(
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 0
 ;
   %setbit = shl nuw i32 1, %NBits
   %ret = add nuw i32 %setbit, -1
   ret i32 %ret
 }
 
 define i32 @shl_nuw_add_nsw_nuw(i32 %NBits) {
 ; CHECK-LABEL: @shl_nuw_add_nsw_nuw(
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 0
 ;
   %setbit = shl nuw i32 1, %NBits
   %ret = add nuw nsw i32 %setbit, -1
   ret i32 %ret
 }
 
 ; shl is nuw nsw
 

 ;
   %setbit = shl nuw nsw i32 1, %NBits
   %ret = add nsw i32 %setbit, -1
   ret i32 %ret
 }
 
 define i32 @shl_nsw_nuw_add_nuw(i32 %NBits) {
 ; CHECK-LABEL: @shl_nsw_nuw_add_nuw(
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 0
 ;
   %setbit = shl nuw nsw i32 1, %NBits
   %ret = add nuw i32 %setbit, -1
   ret i32 %ret
 }
 
 define i32 @shl_nsw_nuw_add_nsw_nuw(i32 %NBits) {
 ; CHECK-LABEL: @shl_nsw_nuw_add_nsw_nuw(
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 0
 ;
   %setbit = shl nuw nsw i32 1, %NBits
   %ret = add nuw nsw i32 %setbit, -1
   ret i32 %ret
 }
 
 ; ============================================================================ ;
 ; Vectors

llvm/trunk/test/Transforms/InstSimplify/constantfold-shl-nuw-C-to-C.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 ; %r = shl nuw i8 C, %x
 ; As per langref: If the nuw keyword is present, then the shift produces
 ;                 a poison value if it shifts out any non-zero bits.
 ; Thus, if the sign bit is set on C, then %x can only be 0, which means that
 ; %r can only be C.
 
 define i8 @shl_nuw (i8 %x) {
 ; CHECK-LABEL: @shl_nuw(
-; CHECK-NEXT:    [[RET:%.*]] = shl nuw i8 -1, [[X:%.*]]
-; CHECK-NEXT:    ret i8 [[RET]]
+; CHECK-NEXT:    ret i8 -1
 ;
   %ret = shl nuw i8 -1, %x
   ; nuw here means that %x can only be 0
   ret i8 %ret
 }
 
 define i8 @shl_nuw_nsw (i8 %x) {
 ; CHECK-LABEL: @shl_nuw_nsw(
-; CHECK-NEXT:    [[RET:%.*]] = shl nuw nsw i8 -1, [[X:%.*]]
-; CHECK-NEXT:    ret i8 [[RET]]
+; CHECK-NEXT:    ret i8 -1
 ;
   %ret = shl nuw nsw i8 -1, %x
   ; nuw here means that %x can only be 0
   ret i8 %ret
 }
 
 define i8 @shl_128 (i8 %x) {
 ; CHECK-LABEL: @shl_128(
-; CHECK-NEXT:    [[RET:%.*]] = shl nuw i8 -128, [[X:%.*]]
-; CHECK-NEXT:    ret i8 [[RET]]
+; CHECK-NEXT:    ret i8 -128
 ;
   %ret = shl nuw i8 128, %x
   ; 128 == 1<<7 == just the sign bit is set
   ret i8 %ret
 }
 
 ; ============================================================================ ;
 ; Positive tests with value range known

 }
 
 ; ============================================================================ ;
 ; Vectors
 ; ============================================================================ ;
 
 define <2 x i8> @shl_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @shl_vec(
-; CHECK-NEXT:    [[RET:%.*]] = shl nuw <2 x i8> <i8 -1, i8 -1>, [[X:%.*]]
-; CHECK-NEXT:    ret <2 x i8> [[RET]]
+; CHECK-NEXT:    ret <2 x i8> <i8 -1, i8 -1>
 ;
   %ret = shl nuw <2 x i8> <i8 -1, i8 -1>, %x
   ret <2 x i8> %ret
 }
 
 define <3 x i8> @shl_vec_undef(<3 x i8> %x) {
 ; CHECK-LABEL: @shl_vec_undef(
-; CHECK-NEXT:    [[RET:%.*]] = shl nuw <3 x i8> <i8 -1, i8 undef, i8 -1>, [[X:%.*]]
-; CHECK-NEXT:    ret <3 x i8> [[RET]]
+; CHECK-NEXT:    ret <3 x i8> <i8 -1, i8 undef, i8 -1>
 ;
   %ret = shl nuw <3 x i8> <i8 -1, i8 undef, i8 -1>, %x
   ret <3 x i8> %ret
 }
 
 define <2 x i8> @shl_vec_nonsplat(<2 x i8> %x) {
 ; CHECK-LABEL: @shl_vec_nonsplat(
-; CHECK-NEXT:    [[RET:%.*]] = shl nuw <2 x i8> <i8 -1, i8 -2>, [[X:%.*]]
-; CHECK-NEXT:    ret <2 x i8> [[RET]]
+; CHECK-NEXT:    ret <2 x i8> <i8 -1, i8 -2>
 ;
   %ret = shl nuw <2 x i8> <i8 -1, i8 -2>, %x
   ret <2 x i8> %ret
 }
 
 ; ============================================================================ ;
 ; Negative tests. Should not be folded.
 ; ============================================================================ ;