Page MenuHomePhabricator

[LoopPred/WC] Use a dominating widenable condition to remove analyze loop exits
Needs ReviewPublic

Authored by reames on Mon, Nov 4, 3:34 PM.

Details

Summary

This implements a version of the predicateLoopExits transform from IndVarSimplify extended to exploit widenable conditions - and thus be much wider in scope of legality. The code structure ends up being almost entirely different, so I chose to duplicate this into the LoopPredication pass instead of trying to reuse the code in the IndVars.

The core notions of the transform are as follows:

  1. If we have a widenable condition which controls entry into the loop, we're allowed to widen it arbitrarily. Given that, it's simply a *profitability* question as to what conditions to fold into the widenable branch.
  2. To avoid pass ordering issues, we want to avoid widening cases that would otherwise be dischargeable. Or, widen in a form which can still be discharged. Thus, we phrase the transform as selecting one analyzeable exit from the set of analyzeable exits to keep. This avoids creating pass ordering complexities.
  3. Since none of the above proves that we actually exit through our analyzeable exits - we might exit through something else entirely - we limit ourselves to cases where a) the latch is analyzeable and b) the latch is predicted taken, and c) the exit being removed is statically cold.

Diff Detail

Event Timeline

reames created this revision.Mon, Nov 4, 3:34 PM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Nov 4, 3:34 PM
reames updated this revision to Diff 227794.Mon, Nov 4, 3:39 PM

Make the code a bit more explicit about checking property 3 in the review description.

simoll added a subscriber: simoll.Tue, Nov 5, 12:25 AM