|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).|
|on pages: 13-22|
|Address: Porto / Portugal|
|how published: 11-85 FSS11 ECRTS|
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.