Page MenuHomePhabricator

[APInt] Add helpers for rounding u/sdivs.
ClosedPublic

Authored by timshen on Jun 22 2018, 10:59 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

timshen created this revision.Jun 22 2018, 10:59 AM
sanjoy added inline comments.Jun 22 2018, 2:26 PM
llvm/include/llvm/ADT/APInt.h
2160 ↗(On Diff #152519)

Nit: rounding

Did you consider implementing these in sdiv and udiv and passing in a defaulted Rounded parameter? That seems a bit cleaner to me.

Otherwise can you please add comments on sdiv and udiv about their rounding behavior?

llvm/lib/Support/APInt.cpp
2686 ↗(On Diff #152519)

I'm wondering if this can be simplified. Is this logic correct:

Q, R = sdivrem(A, B);
if (R == 0) { return Q; }
if (Q < 0) { return RoundDown ? Q-1:Q; }
return RoundDown ? Q:Q-1;

the logic being that if R != 0 then the quotient is "off by one" depending on its sign.

timshen updated this revision to Diff 152762.Jun 25 2018, 1:29 PM

Updated comments.

timshen added inline comments.Jun 25 2018, 1:29 PM
llvm/include/llvm/ADT/APInt.h
2160 ↗(On Diff #152519)

Did you consider implementing these in sdiv and udiv and passing in a defaulted Rounded parameter? That seems a bit cleaner to me.

I thought about it, but it seems bad to just add complexity to the current APInt API, especially when we didn't find more usage.

APIntOps, on the other hand, are considered by me a set of helpers built on the top of APInt, therefore not adding API complexity to APInt itself.

Otherwise can you please add comments on sdiv and udiv about their rounding behavior?

I'm not sure if the behavior is intentionally not promised to the user, or just undocumented.

llvm/lib/Support/APInt.cpp
2686 ↗(On Diff #152519)

I'm not sure, as the divisor maybe positive or negative. I found it difficult to prove.

Notice that the current algorithm is easy to prove, as it doesn't care whether sdiv rounds towards zero, or down, or up (I changed the comment to make that clear). As long as Quo * B + Rem = A holds, this algorithm is correct.

sanjoy accepted this revision.Jun 25 2018, 3:57 PM

lgtm

llvm/include/llvm/ADT/APInt.h
2160 ↗(On Diff #152519)

APIntOps, on the other hand, are considered by me a set of helpers built on the top of APInt, therefore not adding API complexity to APInt itself.

SGTM

I'm not sure if the behavior is intentionally not promised to the user, or just undocumented.

But you're relying on it right, when the users requests TOWARDS_ZERO?

llvm/lib/Support/APInt.cpp
2680 ↗(On Diff #152762)

Nit: rounding

This revision is now accepted and ready to land.Jun 25 2018, 3:57 PM
timshen updated this revision to Diff 152806.Jun 25 2018, 4:52 PM

Updated comments.

timshen added inline comments.Jun 25 2018, 4:52 PM
llvm/include/llvm/ADT/APInt.h
2160 ↗(On Diff #152519)

Done. Added rounding guarantee to udiv and sdiv.

llvm/lib/Support/APInt.cpp
2680 ↗(On Diff #152762)

Removed. Those should be decl comments, not def comments.

This revision was automatically updated to reflect the committed changes.
lebedev.ri added inline comments.
llvm/trunk/unittests/ADT/APIntTest.cpp
2299

This doesn't do what you think it does..
In reality this inner loop simply never runs.

2307

This always asserts.