[SCEV] Fix trip multiple calculation
ClosedPublic

Authored by huihuiz on Mar 10 2017, 11:12 AM.

Details

Summary

If loop bound containing calculations like min(a,b), the Scalar Evolution API getSmallConstantTripMultiple returns 4294967295 "-1" as the trip multiple. The problem is that, SCEV use -1 * umax to represent umin. The multiple constant -1 was returned, and the logic of guarding against huge trip counts was skipped. Because -1 has 32 active bits.

The fix attempt to factor more general cases. First try to get the greatest power of two divisor of trip count expression. In case overflow happens, the trip count expression is still divisible by the greatest power of two divisor returned. Returns 1 if not divisible by 2.

Patch by Huihui Zhang <huihuiz@codeaurora.org>

Diff Detail

Repository
rL LLVM
huihuiz created this revision.Mar 10 2017, 11:12 AM
huihuiz edited the summary of this revision. (Show Details)Mar 10 2017, 11:19 AM
huihuiz added reviewers: mzolotukhin, hfinkel.
huihuiz retitled this revision from Fix trip multiple calculation to [SCEV] Fix trip multiple calculation.
efriedma edited reviewers, added: efriedma; removed: eli.friedman.Mar 14 2017, 8:49 PM
sanjoy requested changes to this revision.Mar 15 2017, 10:49 PM

Pretty close to lgtm, only very minor comments.

lib/Analysis/ScalarEvolution.cpp
5429 ↗(On Diff #91381)

Can you please extract out this const ifying change and just land it?

5473 ↗(On Diff #91381)

Should you be left shifting 1u? Please check, but I think left shifting a positive number into a negative number (in signed type) is undefined behavior.

This revision now requires changes to proceed.Mar 15 2017, 10:49 PM
huihuiz updated this revision to Diff 92230.Mar 17 2017, 4:52 PM

Update based on Sanjoy's suggestions.

Use 1U left shift with unsigned number.

sanjoy accepted this revision.Mar 17 2017, 4:54 PM

LGTM!

This revision is now accepted and ready to land.Mar 17 2017, 4:54 PM
This revision was automatically updated to reflect the committed changes.