This is an archive of the discontinued LLVM Phabricator instance.

Teach ComputeNumSignBits about signed divisions
ClosedPublic

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

Details

Summary

Hi,

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

Thanks,
Nadav

Diff Detail

Repository
rL LLVM

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.
lib/Analysis/ValueTracking.cpp
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
../llvm/lib/Analysis/ValueTracking.cpp
1738

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.

r231140

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