JDK-6743900 : frequency based block layout
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: hs14
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2008-09-02
  • Updated: 2010-04-02
  • Resolved: 2008-11-19
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 6 JDK 7 Other
6u14Fixed 7Fixed hs14Fixed
Related Reports
Relates :  
JDK-6763452 - Loop induction variable incremented on back edge
Relates :  
JDK-6765180 - Block::is_uncommon() gives wrong answer sometimes
Relates :  
JDK-6810845 - Performance regression in mpegaudio on x64
Description
The server compiler currently computes block frequencies based on branch estimates and probabilities collected from profiling data.

The frequency data can be leveraged create a block layout that:
  - reduces the number of branches emitted
  - improves icache locality
  - rotates loops to end with a conditional branch
  - naturally moves uncommon code sequences out of line without using an arbitrary frequency cutoff

While only modest improvement in performance should be expected, a reduction in the methods for which "spaghetti code" is emitted, should make assembly code more readable.
Comments
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.
07-11-2008
EVALUATION http://hg.openjdk.java.net/jdk7/hotspot-comp/hotspot/rev/72c5366e5d86
07-11-2008
EVALUATION Create a post-register allocation pass that drives block layout by edge frequencies.
02-09-2008