[Support] Fix what I think is an off by 1 bug in UnsignedDivisionByConstantInfo.
authorCraig Topper <craig.topper@sifive.com>
Thu, 29 Dec 2022 17:35:34 +0000 (09:35 -0800)
committerCraig Topper <craig.topper@sifive.com>
Thu, 29 Dec 2022 17:42:50 +0000 (09:42 -0800)
commit1490796dd28c80e987a0a9306104141c52022982
tree07e84c6b94b9a037ad9cfb9aa758c7c3e50e5d86
parenta8234196c58396c0505ac93983dafee743a67b11
[Support] Fix what I think is an off by 1 bug in UnsignedDivisionByConstantInfo.

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.

At least for i8, i16, and i32 the only divisor that changes is
((1 << (BitWidth-1)) | 1). Or 127 for i8, 32769 for i16, and 2147483649
for i32. These are all large enough that the quotient is 0 or 1 so
InstCombine replaces them with an icmp and zext before SelectionDAG.

Reviewed By: lebedev.ri

Differential Revision: https://reviews.llvm.org/D140636
llvm/lib/Support/DivisionByConstantInfo.cpp