| [176953] |
| Title: WCET-aware Register Allocation based on Graph Coloring. <em>In Proceedings of the 46th Design Automation Conference (DAC)</em> |
| Written by: Heiko Falk |
| in: July (2009). |
| Volume: Number: |
| on pages: 726-731 |
| Chapter: |
| Editor: |
| Publisher: |
| Series: 20090730-dac-falk.pdf |
| Address: San Francisco / USA |
| Edition: |
| ISBN: 10.1145/1629911.1630100 |
| how published: 09-55 Falk09c DAC |
| Organization: |
| School: |
| Institution: |
| Type: |
| DOI: |
| URL: |
| ARXIVID: |
| PMID: |
Note: hfalk, ESD, WCC
Abstract: Current compilers lack precise timing models guiding their built-in optimizations. Hence, compilers apply ad-hoc heuristics during optimization to improve code quality. One of the most important optimizations is register allocation. Many compilers heuristically decide when and where to spill a register to memory, without having a clear understanding of the impact of such spill code on a program's run time.<br /> This paper extends a graph coloring register allocator such that it uses precise worst-case execution time (WCET) models. Using this WCET timing data, the compiler tries to avoid spill code generation along the critical path defining a program’s WCET. To the best of our knowledge, this paper is the first one to present a WCET-aware register allocator. Our results underline the effectiveness of the proposed techniques. For a total of 46 realistic benchmarks, we reduced WCETs by 31.2% on average. Additionally, the runtimes of our WCET-aware register allocator still remain acceptable.