Merging Head and Tail Duplication for Convergent Hyperblock Formation

Bertrand A. Maher, Aaron Smith, Doug Burger, Kathryn S. McKinley

Research output: Chapter in Book/Report/Conference proceedingConference contribution


VLIW and EDGE (Explicit Data Graph Execution) ar- chitectures rely on compilers to form high-quality hyper- blocks for good performance. These compilers typically perform hyperblock formation, loop unrolling, and scalar optimizations in a fixed order. This approach limits the compiler's ability to exploit or correct interactions among these phases. EDGE architectures exacerbate this problem by imposing structural constraints on hyperblocks, such as instruction count and instruction composition. This paper presents convergent hyperblock formation, which iteratively applies if-conversion, peeling, unrolling, and scalar optimizations until converging on hyperblocks that are as close as possible to the structural constraints. To perform peeling and unrolling, convergent hyperblock formation generalizes tail duplication, which removes side entrances to acyclic traces, to remove back edges into cyclic traces using head duplication. Simulation results for an EDGE architecture show that convergent hyperblock formation improves code quality over discrete-phase ap- proaches with heuristics for VLIW and EDGE. This algo- rithm offers a solution to hyperblock phase ordering prob- lems and can be configured to implement a wide range of policies.
Original languageEnglish
Title of host publicationProceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture
Place of PublicationWashington, DC, USA
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Print)0-7695-2732-9
Publication statusPublished - 2006

Publication series

NameMICRO 39
PublisherIEEE Computer Society


Dive into the research topics of 'Merging Head and Tail Duplication for Convergent Hyperblock Formation'. Together they form a unique fingerprint.

Cite this