[InstSimplify] Check the NonZero for power of two value

[Allen]

Summary

Fixes https://github.com/llvm/llvm-project/issues/64339

proofs: https://alive2.llvm.org/ce/z/yZ_I2a

[mstorsjo]

Thanks, I can confirm that this fixes my issue in a full rebuild and rerun of the tests!

[foad]

I've seen some correctness problems caused by D154953 (running Vulkan CTS testing on the AMDGPU target) and I can confirm that this patch fixes them.

[goldstein.w.n]

Is there any indication why this is necessary? The alive2 proof of the original transform seems to allow for INT_MIN: https://alive2.llvm.org/ce/z/yZ_I2a

[Allen]

In D156881#4554414, @goldstein.w.n wrote:

Is there any indication why this is necessary? The alive2 proof of the original transform seems to allow for INT_MIN: https://alive2.llvm.org/ce/z/yZ_I2a

Thanks, you are right, and we should prevent the case if the mask value is -1, https://alive2.llvm.org/ce/z/WU_j4a

[mstorsjo]

Can someone follow up on this patch? I'd kinda like the breakage in git main to get fixed - or perhaps we'd need to revert if we can't settle on a fix soon.

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2022

What is this change for? Is this part of the bugfix?

[Allen]

llvm/lib/Analysis/ValueTracking.cpp

2022

Yes. This is similar to the following logic in line 2045.

// A shift left or a logical shift right of a power of two is a power of two
// or zero.
if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) ||
               match(V, m_LShr(m_Value(X), m_Value()))))
  return isKnownToBeAPowerOfTwo(X, /*OrZero*/ true, Depth, Q);

This is try to match following code, because we can assume the vscale always bigger than 1, and it is a power of 2 if it has the attribute of vscale_range

%vscale = call i64 @llvm.vscale.i64()
  %shift = shl nuw nsw i64 %vscale, 11

[Allen]

hi @goldstein.w.n, because this patch it fixing some correctness problems which block many people, so would you help me to review this in high priority, thanks

[Allen]

In D156881#4558588, @mstorsjo wrote:

Can someone follow up on this patch? I'd kinda like the breakage in git main to get fixed - or perhaps we'd need to revert if we can't settle on a fix soon.

sorry for blocking your work, I'll revert that code if I don't land on this fixing today.

[goldstein.w.n]

LGTM.

llvm/lib/Analysis/ValueTracking.cpp

2022

But is it related to making the existing codes correct or just improving the coverage? I don't see how its related to the bug. If its not related to the bug, imo it should be split to a seperate patch.

[Allen]

llvm/lib/Analysis/ValueTracking.cpp

2022

Thanks very much again. I'll seperate this patch before landing.

This change is necessary to match the following code.
otherwise the case and_add_shl_vscale_not_power2_negative will don't have a chance to fold the return value because we only check the shl recursively when the OrZero is true now.

%vscale = call i64 @llvm.vscale.i64()
  %shift = shl nuw nsw i64 %vscale, 11

[Allen]

rebase to top

llvm/lib/Analysis/InstructionSimplify.cpp

       return Op0;
   }
 
   // and 2^x-1, 2^C --> 0 where x <= C.
   const APInt *PowerC;
   Value *Shift;
   if (match(Op1, m_Power2(PowerC)) &&
       match(Op0, m_Add(m_Value(Shift), m_AllOnes())) &&
-      isKnownToBeAPowerOfTwo(Shift, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
+      isKnownToBeAPowerOfTwo(Shift, Q.DL, /*OrZero*/ false, 0, Q.AC, Q.CxtI,
                              Q.DT)) {
     KnownBits Known = computeKnownBits(Shift, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
     // Use getActiveBits() to make use of the additional power of two knowledge
     if (PowerC->getActiveBits() >= Known.getMaxValue().getActiveBits())
       return ConstantInt::getNullValue(Op1->getType());
   }
 
   // If we have a multiplication overflow check that is being 'and'ed with a

llvm/lib/Analysis/ValueTracking.cpp

                             const SimplifyQuery &Q) {
   assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
 
   // Attempt to match against constants.
   if (OrZero && match(V, m_Power2OrZero()))
       return true;
   if (match(V, m_Power2()))
       return true;
-  if (Q.CxtI && match(V, m_VScale())) {
+  if (Q.CxtI &&
+      (match(V, m_VScale()) || match(V, m_Shl(m_VScale(), m_Value())))) {
     const Function *F = Q.CxtI->getFunction();
     // The vscale_range indicates vscale is a power-of-two.
     return F->hasFnAttribute(Attribute::VScaleRange);
   }
 
   // 1 << X is clearly a power of two if the one is not shifted off the end.  If
   // it is shifted off the end then the result is undefined.
   if (match(V, m_Shl(m_One(), m_Value())))

llvm/test/Transforms/InstCombine/rem-mul-shl.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 declare void @use8(i8)
 declare i64 @llvm.vscale.i64()
+declare i32 @llvm.vscale.i32()
 
 define i8 @srem_non_matching(i8 %X, i8 %Y) {
 ; CHECK-LABEL: @srem_non_matching(
 ; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], 15
 ; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[Y:%.*]], 5
 ; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;

 ; CHECK-NEXT:    ret i64 [[REM]]
 ;
   %vscale = call i64 @llvm.vscale.i64()
   %shift = shl nuw nsw i64 %vscale, 6
   %add = add i64 %shift, -1
   %rem = and i64 3072, %add
   ret i64 %rem
 }
+
+; Allow for INT_MIN, https://alive2.llvm.org/ce/z/yZ_I2a
+define i32 @and_add_shl_vscale_not_power2_negative() vscale_range(1,16) {
+; CHECK-LABEL: @and_add_shl_vscale_not_power2_negative(
+; CHECK-NEXT:    ret i32 0
+;
+  %vscale = call i32 @llvm.vscale.i32()
+  %shift = shl nuw nsw i32 %vscale, 6
+  %add = add i32 %shift, -1
+  %rem = and i32 -2147483648, %add
+  ret i32 %rem
+}
+
+; Negative test: the %sign may be 0, https://alive2.llvm.org/ce/z/WU_j4a
+define i32 @and_add_and (i32 %x) {
+; CHECK-LABEL: @and_add_and(
+; CHECK-NEXT:    [[X1:%.*]] = lshr i32 [[X:%.*]], 7
+; CHECK-NEXT:    [[SIGN:%.*]] = and i32 [[X1]], 1
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[SIGN]], -1
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ADD]], -2147483648
+; CHECK-NEXT:    ret i32 [[AND]]
+;
+  %x1 = lshr i32 %x, 7
+  %sign = and i32 %x1, 1  ; %sign = (%x >> 7) & 1
+  %add = add i32 %sign, -1
+  %and = and i32 %add, 2147483648
+  ret i32 %and
+}
+