Page MenuHomePhabricator

[Unroll] Rework the naming and structure of the new unroll heuristics.
ClosedPublic

Authored by chandlerc on May 24 2015, 7:47 PM.

Details

Summary

The new naming is (to me) much easier to understand. Here is a summary
of the new state of the world:

  • '*Threshold' is the base line threshold for full unrolling. It is measured against the estimated unrolled cost as computed by getUserCost in TTI (or CodeMetrics, etc). We will exceed this threshold when unrolling loops where unrolling exposes a significant degree of simplification of the logic within the loop.
  • '*MaxThreshold' is an absolute cap computed the same way as '*Threshold' but is never exceeded even due to profitable circumstanctes.
  • '*PercentCostSavedThreshold' is the percentage of the loop's estimated dynamic execution cost which needs to be saved by unrolling to allow full unrolling in excess of the '*Threshold'.

When actually analyzing the loop, we now produce both an estimated
unrolled cost, and an estimated rolled cost. The rolled cost is notably
a dynamic estimate based on our analysis of the expected execution of
each iteration.

These estimates are pretty bad still, but we can make them much better,
and (to me) it is much more clear *how* to make them better when they
have reasonably descriptive names. For example, we may want to apply
estimated (from heuristics or profiles) dynamic execution weights to the
*dynamic* cost estimates. If we start doing that, we would also need to
track the static unrolled cost and the dynamic unrolled cost, as only
the latter could reasonably be weighted by profile information.

This patch is sadly not without functionality change for the new unroll
analysis logic. Buried in the heuristic management were several things
that surprised me. For example, we never subtracted the optimized
instruction count off when comparing against the unroll heursistics!
I don't know if this just got lost somewhere along the way or what, but
with the new accounting of things, this is much easier to keep track of
and we use the post-simplification cost estimate to compare to the
thresholds, and use the dynamic cost reduction ratio to select whether
we can exceed the baseline threshold.

My next series of patches will significantly improve the cost estimation
by handling dead control flows, weighting dynamic cost by the profile
(which both will amplify simplifications of nested loops and discount
simplifications of heavily predicated paths), and trying to track
instructions that are unnecessary after unrolling.

Diff Detail

Repository
rL LLVM

Event Timeline

chandlerc updated this revision to Diff 26392.May 24 2015, 7:47 PM
chandlerc retitled this revision from to [Unroll] Rework the naming and structure of the new unroll heuristics..
chandlerc updated this object.
chandlerc edited the test plan for this revision. (Show Details)
chandlerc added reviewers: mzolotukhin, hfinkel.
chandlerc added a subscriber: Unknown Object (MLST).
mzolotukhin edited edge metadata.May 25 2015, 11:12 AM

Hi Chandler,

In general I'm in favor for such changes, but my feeling is that MaxThreshold and Threshold are still pretty confusing. What about something like TinyLoopsThreshold and BigLoopsThreshold? The idea is that the TinyLoopsThreshold defines which loops are considered tiny (and which we unconditionally unroll), and BigLoopsThreshold defines huge loops, which will never be unrolled.

Other than that, the changes look good to me.

And by the way, thanks for your recent patches here!

Michael

chandlerc updated this revision to Diff 27205.Jun 5 2015, 9:54 AM
chandlerc edited edge metadata.

Switched to a single threshold and a discount after long discussions with
Michael on the best naming pattern here.

LGTM.

test/Transforms/LoopUnroll/full-unroll-heuristics.ll
4 ↗(On Diff #27205)

Please update the comment.

chandlerc accepted this revision.Jun 5 2015, 10:04 AM
chandlerc added a reviewer: chandlerc.

Thanks, submitting!

test/Transforms/LoopUnroll/full-unroll-heuristics.ll
4 ↗(On Diff #27205)

Done.

This revision is now accepted and ready to land.Jun 5 2015, 10:04 AM
This revision was automatically updated to reflect the committed changes.