This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] More accurate calculation of max backedge count of some less-than loops
ClosedPublic

Authored by john.brawn on Oct 14 2016, 4:20 AM.

Details

Summary

In loops that look something like

i = n;
do {
 ...
} while(i++ < n+k);

where k is a constant, the maximum backedge count is k (in fact the backedge count will be either 0 or k, depending on whether n+k wraps). More generally for LHS < RHS if RHS-(LHS of first comparison) is a constant then the loop will iterate either 0 or that constant number of times.

This allows for more loop unrolling with the recent upper bound loop unrolling changes, and I'm working on a patch that will let loop unrolling additionally make use of the loop being executed either 0 or k times (we need to retain the loop comparison only on the first unrolled iteration).

Diff Detail

Repository
rL LLVM

Event Timeline

john.brawn updated this revision to Diff 74656.Oct 14 2016, 4:20 AM
john.brawn retitled this revision from to [SCEV] More accurate calculation of max backedge count of some less-than loops.
john.brawn updated this object.
john.brawn added reviewers: sanjoy, christof, haicheng.
john.brawn set the repository for this revision to rL LLVM.
john.brawn added a subscriber: llvm-commits.
sanjoy accepted this revision.Oct 17 2016, 10:29 AM
sanjoy edited edge metadata.

LGTM! Thanks!

This revision is now accepted and ready to land.Oct 17 2016, 10:29 AM
This revision was automatically updated to reflect the committed changes.