llvm-project.git/llvm/lib/Support/DivisionByConstantInfo.cpp, branch users/nico/python-1

[DivisionByConstantInfo] Use APInt::getLowBitsSet instead of getAllOnes+lshr. NFC

2024-07-08T05:32:14+00:00

Use APInt::count{l,r}_{zero,one} (NFC)

2023-02-20T06:04:47+00:00

[Support][SelectionDAG][GlobalISel] Hoist PostShift adjustment for IsAdd into UnsignedDivideUsingMagic.

2023-01-04T23:18:12+00:00

Instead of doing the adjustment in 3 different places in the code
base, do it inside UnsignedDivideUsingMagic::get.

Differential Revision: https://reviews.llvm.org/D141014

[SelectionDAG][GlobalISel] Don't use UnsignedDivisionByConstantInfo for divisor of 1.

2023-01-04T18:01:15+00:00

The magic algorithm sets IsAdd indication for division by 1 that
the caller had to ignore.

I considered folding the ignore into UnsignedDivisionByConstantInfo,
but we only allow 1 for vectors of mixed visiors. And really what we
want to end up with is undef. Currently, we get to undef via
DemandedElts optimizations using the select instruction. We could
directly emit undef.

Differential Revision: https://reviews.llvm.org/D140940

[SelectionDAG][GlobalISel] Move even divisor optimization for division by constant into UnsignedDivideUsingMagic implementation. NFC

2023-01-04T00:34:13+00:00

I've added a bool to UnsignedDivideUsingMagic so we can continue
testing it in the unit test with and without this optimization in
the unit test.

This is a step towards supporting "uncooperative" odd divisors.
See https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html

Reviewed By: lebedev.ri

Differential Revision: https://reviews.llvm.org/D140924

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

2022-12-29T17:42:50+00:00

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

[NFC] Add exhaustive test coverage for `{Un}signedDivisionByConstantInfo`

2022-12-25T01:10:32+00:00

Use this wrapper if you want to try brute-forcing wider bit widths:
https://godbolt.org/z/3xGzTM881

I've brute-forced i16 for both signed and unsigned, and we're all good.
As mentioned in https://reviews.llvm.org/D140636

[Support] Use APInt::udivrem in DivisionByConstantInfo. NFC

2022-12-23T21:33:40+00:00

[Support] Use inplace APInt operators in DivisionByConstantInfo. NFC

2022-12-23T08:00:22+00:00

Reduces the number of temporary APInts that get created and
copy/moved from.

[Support] Move some APInt declarations in DivisionByConstantInfo to their first assignment.

2022-12-23T06:09:12+00:00

This uses copy initialization instead of default constructing the
APInts and assigning over them.