WCET-aware register allocation based on graph coloring

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 regis...

Full description

Saved in:
Bibliographic Details
Main Author: Falk, Heiko
Format: Conference Proceeding
Language:English
Subjects:
Computer systems organization > Embedded and cyber-physical systems
Computer systems organization > Real-time systems
Design optimization
Embedded system
Optimizing compilers
Permission
Program processors
Real time systems
Register Allocation
Registers
Runtime
Safety
Software and its engineering > Software notations and tools > Compilers
Timing
WCET
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. 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.
ISSN:0738-100X
DOI:10.1145/1629911.1630100