Page MenuHomePhabricator

Teach ComputeNumSignBits about signed divisions

Authored by nadav on Mar 3 2015, 12:03 AM.




The attached patch teaches ComputeNumSignBits that when a number is divided by a positive constant then the top floor(log(n)) bits are identical.


Diff Detail


Event Timeline

nadav updated this revision to Diff 21087.Mar 3 2015, 12:03 AM
nadav retitled this revision from to Teach ComputeNumSignBits about signed divisions.
nadav updated this object.
nadav edited the test plan for this revision. (Show Details)
nadav added reviewers: majnemer, nicholas.
nadav set the repository for this revision to rL LLVM.
nadav added a subscriber: Unknown Object (MLST).Mar 3 2015, 12:05 AM
sanjoy added a subscriber: sanjoy.Mar 3 2015, 12:54 AM
sanjoy added inline comments.
1732 ↗(On Diff #21087)

Nit: "non-positive"

1733 ↗(On Diff #21087)

Why not do this check before the call to ComputeNumSignBits? Then we'll bail out earlier without doing unnecessary work.

nadav updated this revision to Diff 21115.Mar 3 2015, 10:26 AM
majnemer added inline comments.Mar 3 2015, 1:18 PM

I think this result can become larger than the bitwidth if your numerator is very small and your denominator is very large.

Arithmetically, the result of such a division would be zero but we might not have simplified it yet.

An example of this would be

%and = and i32 %x, 1
%div = sdiv i32 %and, 1073741824

The number of sign bits in %and is 31 and they are all zero.
The log-base2 of the denominator is 30. I don't think the answer coming from this query cannot be larger than the bitwdith.

nadav accepted this revision.Mar 3 2015, 1:41 PM
nadav added a reviewer: nadav.


This revision is now accepted and ready to land.Mar 3 2015, 1:41 PM