PUBLIC COMMENTS
Reorder the basic blocks with the intent of minimizing the number of jumps
along frequently executed edges. By focusing on keeping frequently executed
blocks together, infrequent blocks should naturally be moved out of line. The
new pass is enabled by a flag, otherwise, the old functionality is employed.
The basic algorithm:
- Find all CFG edges that could be embodied by a branch or fallthroough
- Compute an edge frequencies using block frequencies and branch probabilities
- Make a list of edges sorted the in descending order by frequency
- Create a Trace (an ordereed list of basic blocks) for every basic block
- For each edge, in descending frequency
- if the edge is from the tail of one trace to the head of another
- if the traces are different, append the traces
- else, process edges as a back-branch (and possibly rotate loop)
- Make diamonds, when it is deemed profitable to merge one trace into the middle of another
- Append remaining traces end-to-end if an unprocessed edge indicates transfer between traces.
- Order remaining traces by frequency of first block
There are three new flags:
- BlockLayoutByFrequency: enables new algorithm (on by default)
- BlockLayoutRotateLoops: allows a back branch to be embodied as a
fall-through (off)
- BlockLayoutMinDiamondPercentage</b>: minimum % of
the lesser side of a diamond that will allow the two sides to be
merged into a single trace
Other changes:
Add classes for PhaseBlockLayout, Trace, and CFGEdge
In Estimate_Block_Frequency(), when the layout pass is enabled, do a
pre-estimate pass that lowers branch probabilities instead of a
post-pass that adjusts block frequencies. Also, delete code that could
scale block frequencies against something other than a single method
entry.
Divide remove_emopty() into two parts. Empty blocks are moved before
layout; flow if fixed after layout.
Revise loop alignment code. Loop alignments are computed before the
output pass because if a loop is rotated, loop-heads are no longer
guaranteed to be the backbranch target..
Add infrastructure to allow frequency based layout on a
method-by-method basis.
|
Java