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

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

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

Instead of doing the adjustment in 3 different places in the code
base, do it inside UnsignedD

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

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

show more ...

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

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

I considered folding

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

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

show more ...

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

I've added a bool to UnsignedDivideUsingMagic so we can continue

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

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

show more ...

[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 Delig

[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

show more ...

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

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

I've brute-forced i16 f

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

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

show more ...

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

[Support] Use inplace APInt operators in DivisionByConstantInfo. NFC

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

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

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

[Support][CodeGen] Fix spelling Divison->Division. NFC

[llvm] Use true/false instead of 1/0 (NFC)

Identified with modernize-use-bool-literals.

[NFC] Restore magic and magicu to a globally visible location

While these functions are only used in one location in upstream,
it has been reused in multiple downstreams. Restore this file to
a glob

[NFC] Restore magic and magicu to a globally visible location

While these functions are only used in one location in upstream,
it has been reused in multiple downstreams. Restore this file to
a globally visibile location (outside of APInt.h) to eliminate
donwstream breakage and enable potential future reuse.

Additionally, this patch renames types and cleans up
clang-tidy issues.

show more ...