Page MenuHomePhabricator

Fix APInt division algorithm
ClosedPublic

Authored by chfast on Mar 19 2015, 10:22 AM.

Details

Summary

APInt uses Knuth's D algorithm for long division. In rare cases the implementation applied a transformation that was not needed.

Diff Detail

Repository
rL LLVM

Event Timeline

chfast updated this revision to Diff 22269.Mar 19 2015, 10:22 AM
chfast retitled this revision from to Fix APInt division algorithm.
chfast updated this object.
chfast edited the test plan for this revision. (Show Details)
chfast set the repository for this revision to rL LLVM.
chfast added subscribers: Unknown Object (MLST), chandlerc.
yaron.keren accepted this revision.Mar 26 2015, 1:07 AM
yaron.keren added a reviewer: yaron.keren.

Minor nitpicks, LGTM.

lib/Support/APInt.cpp
1510

Could b be LLVM_CONSTEXPR ?

1583

The parenthesis around the shift make the expression more readable, even if not required.

You flipped the | arguments so they would consistent with the usual u[j+n], u[j+n-1]...u[j] representation?

1786

I'd remove the FIXME and explain that *currently* this is a dead case since all callers in APInt calls either test for divide() with lhswords == rhswords == 1 or proivde the a small radix before calling divide() but it is worth keeping this code alive for correctness in case some new code does call divide() with lhswords == rhswords == 1.

This revision is now accepted and ready to land.Mar 26 2015, 1:07 AM
chfast added inline comments.Mar 26 2015, 6:14 AM
lib/Support/APInt.cpp
1510

Probably. I'm not used to constexpr because Visual Studio still does not support it.

1583

I flipped arguments because I like high word being on the left. You shift left to make space for a low word.

1786

Ok, I will change that. I'm just a bit worried that this code cannot be reached with unittests.

chfast updated this revision to Diff 22720.Mar 26 2015, 7:35 AM
chfast edited edge metadata.

Applied suggestions by yaron.keren.

Can you submit the patch for me?

yaron.keren closed this revision.Mar 26 2015, 12:51 PM

Sure, committed revision 233312.