[SCEV] Fix trip multiple calculation

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



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

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.

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


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.