[176935]
Title: WCET-aware Register Allocation based on Integer-Linear Programming. <em>In Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS)</em>
Written by: Heiko Falk, Norman Schmitz and Florian Schmoll
in: July (2011).
Volume: Number:
on pages: 13-22
Chapter:
Editor:
Publisher:
Series: 20110706-ecrts-falk.pdf
Address: Porto / Portugal
Edition:
ISBN: 10.1109/ECRTS.2011.10
how published: 11-85 FSS11 ECRTS
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 runtime.<br /> This paper presents an integer-linear programming (ILP) based register allocator that uses precise worst-case execution time (WCET) models. Using this WCET timing data, the compiler avoids 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 ILP-based register allocator. Our results underline the effectiveness of the proposed techniques. For a total of 55 realistic benchmarks, we reduced WCETs by 20.2% on average and ACETs by 14%, compared to a standard graph coloring allocator. Furthermore, our ILP-based register allocator outperforms a WCET-aware graph coloring allocator by more than a factor of two for the considered benchmarks, while requiring less runtime.