[Support] Fix what I think is an off by 1 bug in UnsignedDivisionByConstantInfo.

[craig.topper]

Summary

The code in Hacker's Delight says
nc = -1 - (-d)%d;

But we have
NC = AllOnes - (AllOnes-D)%D

The Hacker's Delight code is written for the LeadingZeros==0 case.
AllOnes - D is not the same as -d from Hacker's Delight.

This patch changes the code to
NC = AllOnes - (AllOnes+1-D)%D

This will increment AllOnes to 0 in the LeadingZeros==0 case. This
will make it equivalent to -D. I believe this is also correct for
LeadingZeros>0.

I've been unable to find a case that changes with the new code.
I've checked all divisors for i8 and i16 udiv and the resulting
code is the same. i32 is a much larger search space to check.

[barannikov88]

https://github.com/llvm/llvm-project/commit/3aab6a86a263369fc49a6180f9163d0077435a02
https://github.com/llvm/llvm-project/issues/13698

There are a few testcases that might worth checking / adding:
https://github.com/llvm/llvm-project/issues/13698#issuecomment-980909412

[craig.topper]

In D140636#4015758, @barannikov88 wrote:

https://github.com/llvm/llvm-project/commit/3aab6a86a263369fc49a6180f9163d0077435a02
https://github.com/llvm/llvm-project/issues/13698

There are a few testcases that might worth checking / adding:
https://github.com/llvm/llvm-project/issues/13698#issuecomment-980909412

Those test cases test i8 udiv by 78 and 116. The tests for those are still in test/CodeGen/X86/div-by-constant.ll and did not change with this patch.

[efriedma]

I'd like to know what, exactly, changed between 3aab6a86 and now to make this correct. Otherwise this seems sort of suspicious, even if it doesn't appear to have any effect on the current code generation.

[lebedev.ri]

Let me add some tests here.

[barannikov88]

In D140636#4016127, @lebedev.ri wrote:

Let me add some tests here.

In case that helps, I've tried a few bitwidth variants.
With LeadingZeros = 0, I get different magics iff the divisor has LSB and MSB ones and all other bits zeros. (I.e. 0b1000...0001 for any bitwidth.)
Example: APInt(8, 0x81).

With LeadingZeros != 0, the old algorithm asserts iff the divisor is a certain power of two. Examples:
D = APInt(8, 0x80) and LeadingZeros = 1
D = APInt(8, 0x40) and LeadingZeros = 2.
The fixed version does not crash and returns what seems to be correct values (can that be enough for a unittest?)

[craig.topper]

Add a comment and assert to describe what NC is supposed to be.

[craig.topper]

In D140636#4016133, @barannikov88 wrote:

In D140636#4016127, @lebedev.ri wrote:

Let me add some tests here.

In case that helps, I've tried a few bitwidth variants.
With LeadingZeros = 0, I get different magics iff the divisor has LSB and MSB ones and all other bits zeros. (I.e. 0b1000...0001 for any bitwidth.)
Example: APInt(8, 0x81).

With LeadingZeros != 0, the old algorithm asserts iff the divisor is a certain power of two. Examples:
D = APInt(8, 0x80) and LeadingZeros = 1
D = APInt(8, 0x40) and LeadingZeros = 2.
The fixed version does not crash and returns what seems to be correct values (can that be enough for a unittest?)

Thanks. I thought I checked all of the i8 cases. But you're right there is a difference with 0x81.

I think what happened is that I checked by writing the code in C and InstCombine has a replacement for udiv with a divisor that large. So I didn't test udiv for that value.

[barannikov88]

In D140636#4016138, @craig.topper wrote:

I think what happened is that I checked by writing the code in C and InstCombine has a replacement for udiv with a divisor that large. So I didn't test udiv for that value.

Yeah, that's probably the reason the bug hasn't been reported yet (I found this case by directly calling the function from a simple GTest).
It won't assert with APInt(8, 0x80) on a C code either, since division by a power of two is optimized into a shift.
We probably just need a targeted test in llvm/unittests/Support

[lebedev.ri]

I've added exhaustive test coverage for this division expansion: 066b492b747a7e00f537eab9f0196575522ec285 (that now always tests bit widths 2..12)
And additionally brute-forced it for i16, without and with this patch, using: https://godbolt.org/z/3xGzTM881.
This change does not cause any changes, our existing expansion is correct regardless.
TargetLowering::BuildUDIV() seen a lot of changes since then.

I'm going to go ahead and stamp this.

[barannikov88]

@lebedev.ri
Thank you for volunteering adding the tests. Rare developer is willing to do so.

I have some concerns about the quality of the tests though.
The tests do not actually test the algorithm in question. They test a division algorithm
using the magic numbers, which is another, and huge, failure point.
Because of this failure point, the tests do not catch a real bug,
(e.g. the generated magic numbers are invalid for APInt(8, 0x81)).
Also, the tests should also cover non-zero LeadingZeros case.

Iterating over the whole search space may be nice. However, the most interesting cases of 32- and 64-bit divisor are not covered
(and can't be covered for performance reasons).

Would you mind replacing them with a few targeted tests that only call the 'get' method and check the returned result?
If you find this request inappropriate given the time you've already spent, that's absolutely OK.

[craig.topper]

In D140636#4016133, @barannikov88 wrote:

In D140636#4016127, @lebedev.ri wrote:

Let me add some tests here.

In case that helps, I've tried a few bitwidth variants.
With LeadingZeros = 0, I get different magics iff the divisor has LSB and MSB ones and all other bits zeros. (I.e. 0b1000...0001 for any bitwidth.)
Example: APInt(8, 0x81).

With LeadingZeros != 0, the old algorithm asserts iff the divisor is a certain power of two. Examples:
D = APInt(8, 0x80) and LeadingZeros = 1
D = APInt(8, 0x40) and LeadingZeros = 2.
The fixed version does not crash and returns what seems to be correct values (can that be enough for a unittest?)

I'm not sure I expect the algorithm to work if the divisor does not have at least as many leading zeros as the dividend. The AllOnes value the algorithm creates should be >= D. Norrmally when LeadingZeros is used both the dividend and the divisor have been shifted right by that many bits.

[lebedev.ri]

In D140636#4016185, @craig.topper wrote:

In D140636#4016133, @barannikov88 wrote:

In D140636#4016127, @lebedev.ri wrote:

Let me add some tests here.

In case that helps, I've tried a few bitwidth variants.
With LeadingZeros = 0, I get different magics iff the divisor has LSB and MSB ones and all other bits zeros. (I.e. 0b1000...0001 for any bitwidth.)
Example: APInt(8, 0x81).

With LeadingZeros != 0, the old algorithm asserts iff the divisor is a certain power of two. Examples:
D = APInt(8, 0x80) and LeadingZeros = 1
D = APInt(8, 0x40) and LeadingZeros = 2.
The fixed version does not crash and returns what seems to be correct values (can that be enough for a unittest?)

I'm not sure I expect the algorithm to work if the divisor does not have at least as many leading zeros as the dividend. The AllOnes value the algorithm creates should be >= D. Norrmally when LeadingZeros is used both the dividend and the divisor have been shifted right by that many bits.

ACK. It's not a nice API design, but you can't just pass random LeadingZeros there.

llvm/lib/Support/DivisionByConstantInfo.cpp

 //===----- DivisionByConstantInfo.cpp - division by constant -*- C++ -*----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///

 UnsignedDivisionByConstantInfo::get(const APInt &D, unsigned LeadingZeros) {
   APInt Delta;
   struct UnsignedDivisionByConstantInfo Retval;
   Retval.IsAdd = false; // initialize "add" indicator
   APInt AllOnes = APInt::getAllOnes(D.getBitWidth()).lshr(LeadingZeros);
   APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
   APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth());
 
-  APInt NC = AllOnes - (AllOnes - D).urem(D);
+  // Calculate NC, the largest dividend such that NC.urem(D) == D-1.
+  APInt NC = AllOnes - (AllOnes + 1 - D).urem(D);
+  assert(NC.urem(D) == D - 1 && "Unexpected NC value");
   unsigned P = D.getBitWidth() - 1; // initialize P
   APInt Q1, R1, Q2, R2;
   // initialize Q1 = 2P/NC; R1 = rem(2P,NC)
   APInt::udivrem(SignedMin, NC, Q1, R1);
   // initialize Q2 = (2P-1)/D; R2 = rem((2P-1),D)
   APInt::udivrem(SignedMax, D, Q2, R2);
   do {
     P = P + 1;