[AMDGPU] Correct the known bits calculation for MUL_I24.

[craig.topper]

Summary

I'm not entirely sure, but based on how ComputeNumSignBits handles
ISD::MUL, I believe this code was miscounting the number of sign
bits.

As an example of an incorrect result let's say that countMinSignBits
returned 1 for the left hand side and 24 for the right hand side.
LHSValBits would be 23 and RHSValBits would be 0 and the sum would
be 23. This would cause the code to set 9 high bits as zero/one. Now
suppose the real values for the left side is 0x800000 and the right
hand side is 0xffffff. The product is 0x00800000 which has 8 sign bits
not 9.

The number of valid bits for the left and right operands is now
the number of non-sign bits + 1. If the sum of the valid bits of
the left and right sides exceeds 32, then the result may overflow and we
can't say anything about the sign of the result. If the sum is 32
or less then it won't overflow and we know the result has at least
1 sign bit.

For the previous example, the code will now calculate the left
side valid bits as 24 and the right side as 1. The sum will be 25
and the sign bits will be 32 - 25 + 1 which is 8, the correct value.

I don't know enough about AMDGPU to write a test for this. I just
noticed while looking at how KnownBits::countMinSignBits was used.

[lebedev.ri]

llvm/include/llvm/Support/KnownBits.h

252–253 ↗

(On Diff #396843)

This is certainly a right change.
Is there no exhaustive test for this function?
If not, could you add one? Else, adjust it to check that the returned value is u>=1 ?

[craig.topper]

Add KnownBits::countMinSignBits() unit test.

[foad]

Both changes look good to me but it's not clear how they are related, and it seems odd to include the generic change in a patch which claims to be AMDGPU-specific. Would it makes sense to commit the generic change separately first?

As an example of an incorrect result let's say that countMinSignBits
returned 1 for the left hand side and 24 for the right hand side.
LHSValBits would be 23 and RHSValBits would be 0 and the sum would
be 23. This would cause the code to set 9 high bits as zero/one. Now
suppose the real values for the left side is 0x8000000 and the right
hand side is 0xffffff. The product is 0x00800000 which has 8 sign bits
not 9.

"... the real value for the left side is 0x800000 ..."? Your value 0x8000000 has too many zeros.

I can try to come up with an AMDGPU test case but not until Tuesday (GMT) at the earliest.

Incidentally there is some very similar logic for 24-bit multiplies in AMDGPUCodeGenPrepare::replaceMulWithMul24.

[craig.topper]

In D116469#3216166, @foad wrote:

Both changes look good to me but it's not clear how they are related, and it seems odd to include the generic change in a patch which claims to be AMDGPU-specific. Would it makes sense to commit the generic change separately first?

I'll split them. I think the generic change affect AMDGPU behavior becuase the return value of 0 that is being changed only happens when no bits are known. In that case the isNegative/isNonNegative/isStrictlyPositive would all return false so no calls to setHighBits would occur.

As an example of an incorrect result let's say that countMinSignBits
returned 1 for the left hand side and 24 for the right hand side.
LHSValBits would be 23 and RHSValBits would be 0 and the sum would
be 23. This would cause the code to set 9 high bits as zero/one. Now
suppose the real values for the left side is 0x8000000 and the right
hand side is 0xffffff. The product is 0x00800000 which has 8 sign bits
not 9.

"... the real value for the left side is 0x800000 ..."? Your value 0x8000000 has too many zeros.

Fixed. I guess my brain really wanted to write a 32-bit number.

[craig.topper]

Remove KnownBits change

[RKSimon]

llvm/lib/Target/AMDGPU/AMDGPUISelLowering.cpp

4629–4632

Do you think it'd be confusing if we added KnownBits::getMinSignedBits() to match APInt::getMinSignedBits() ?

4646–4647

Use KnownBits::countMaxActiveBits() ?

[craig.topper]

llvm/lib/Target/AMDGPU/AMDGPUISelLowering.cpp

4629–4632

Shouldn’t it be getMaxSignedBits? It’s an upper bound like getMaxActiveBits.

Likewise ComputeMinSignedBits is also misnamed.

[craig.topper]

Address Simon's comments.

[lebedev.ri]

This looks obviously correct(C) to me, but i'll leave this to amdgpu folks.

[foad]

This patch seems to change codegen in test/CodeGen/AMDGPU/lshl64-to-32.ll but I haven't managed to understand whether the change is good, bad or indifferent.

[craig.topper]

Rebase

[craig.topper]

In D116469#3219140, @foad wrote:

This patch seems to change codegen in test/CodeGen/AMDGPU/lshl64-to-32.ll but I haven't managed to understand whether the change is good, bad or indifferent.

I'm not seeing any failure for that test in my local runs. The test appears to be generated by update_llc_test_checks.py and rerunning the script produced no changes. Am I missing something?

[foad]

In D116469#3220809, @craig.topper wrote:

In D116469#3219140, @foad wrote:

This patch seems to change codegen in test/CodeGen/AMDGPU/lshl64-to-32.ll but I haven't managed to understand whether the change is good, bad or indifferent.

I'm not seeing any failure for that test in my local runs. The test appears to be generated by update_llc_test_checks.py and rerunning the script produced no changes. Am I missing something?

Sorry, false alarm. I had to manually rebase the patch when I tested it, and I got it wrong.

[craig.topper]

@foad were you able to come up with a test for this?

[foad]

In D116469#3235782, @craig.topper wrote:

@foad were you able to come up with a test for this?

Sorry it had dropped off my radar. Here's a test where your patch makes a difference (with llc -march=amdgcn -mcpu=gfx900):

define i32 @f(i32 %x, i32 %y) {
  %xx = or i32 %x, -128 ; 0xffffff80
  %yy = or i32 %y, -128 ; 0xffffff80
  %r = mul i32 %xx, %yy
  %rr = lshr i32 %r, 14
  ret i32 %rr
}

Without your patch the result is simplified to 0 which is wrong. %xx and %yy are in the range -128..-1, so if they are both -128 then the product is -16384, shifted right by 14 is 1.

[craig.topper]

Rebase with test. Test will be added in a separate review.

[foad]

LGTM, thanks!

llvm/lib/Target/AMDGPU/AMDGPUISelLowering.cpp

case AMDGPUISD::MUL_I24: {
     if (TrailZ >= 32)
       break;
 
     // Truncate to 24 bits.
     LHSKnown = LHSKnown.trunc(24);
     RHSKnown = RHSKnown.trunc(24);
 
     if (Opc == AMDGPUISD::MUL_I24) {
-      unsigned LHSValBits = 24 - LHSKnown.countMinSignBits();
-      unsigned RHSValBits = 24 - RHSKnown.countMinSignBits();
-      unsigned MaxValBits = std::min(LHSValBits + RHSValBits, 32u);
-      if (MaxValBits >= 32)
+      unsigned LHSValBits = LHSKnown.countMaxSignificantBits();
+      unsigned RHSValBits = RHSKnown.countMaxSignificantBits();
+      unsigned MaxValBits = LHSValBits + RHSValBits;
+      if (MaxValBits > 32)
         break;
+      unsigned SignBits = 32 - MaxValBits + 1;
       bool LHSNegative = LHSKnown.isNegative();
       bool LHSNonNegative = LHSKnown.isNonNegative();
       bool LHSPositive = LHSKnown.isStrictlyPositive();
       bool RHSNegative = RHSKnown.isNegative();
       bool RHSNonNegative = RHSKnown.isNonNegative();
       bool RHSPositive = RHSKnown.isStrictlyPositive();
 
       if ((LHSNonNegative && RHSNonNegative) || (LHSNegative && RHSNegative))
-        Known.Zero.setHighBits(32 - MaxValBits);
+        Known.Zero.setHighBits(SignBits);
       else if ((LHSNegative && RHSPositive) || (LHSPositive && RHSNegative))
-        Known.One.setHighBits(32 - MaxValBits);
+        Known.One.setHighBits(SignBits);
     } else {
-      unsigned LHSValBits = 24 - LHSKnown.countMinLeadingZeros();
-      unsigned RHSValBits = 24 - RHSKnown.countMinLeadingZeros();
-      unsigned MaxValBits = std::min(LHSValBits + RHSValBits, 32u);
+      unsigned LHSValBits = LHSKnown.countMaxActiveBits();
+      unsigned RHSValBits = RHSKnown.countMaxActiveBits();
+      unsigned MaxValBits = LHSValBits + RHSValBits;
       if (MaxValBits >= 32)
         break;
-      Known.Zero.setHighBits(32 - MaxValBits);
+      Known.Zero.setBitsFrom(MaxValBits);
     }
     break;
   }
   case AMDGPUISD::PERM: {
     ConstantSDNode *CMask = dyn_cast<ConstantSDNode>(Op.getOperand(2));
     if (!CMask)
       return;
 

llvm/test/CodeGen/AMDGPU/amdgpu-mul24-knownbits.ll

entry:
   store float 0.000, float addrspace(1)* %v3, align 4
   ret void
 }
 
 define i32 @f(i32 %x, i32 %y) {
 ; GCN-LABEL: f:
 ; GCN:       ; %bb.0:
 ; GCN-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
-; GCN-NEXT:    v_mov_b32_e32 v0, 0
+; GCN-NEXT:    s_mov_b32 s4, 0xffff80
+; GCN-NEXT:    v_or_b32_e32 v0, s4, v0
+; GCN-NEXT:    v_or_b32_e32 v1, s4, v1
+; GCN-NEXT:    v_mul_i32_i24_e32 v0, v0, v1
+; GCN-NEXT:    v_lshrrev_b32_e32 v0, 14, v0
 ; GCN-NEXT:    s_setpc_b64 s[30:31]
   %xx = or i32 %x, -128 ; 0xffffff80
   %yy = or i32 %y, -128 ; 0xffffff80
   %r = mul i32 %xx, %yy
   %rr = lshr i32 %r, 14
   ret i32 %rr
 }
 
 ; Function Attrs: nounwind readnone speculatable
 declare i32 @llvm.amdgcn.workitem.id.x() #20
 
 !4 = !{i32 0, i32 1024}