WCET-aware register allocation based on graph coloring

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.

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.

REFERENCES

• 1: AbsInt Angewandte Informatik GmbH. aiT: Worst-Case Execution Time Analyzers. www.absint.com/ait, 2009.
• 2: P. Briggs. Register Allocation via Graph Coloring. PhD thesis, Rice University, Houston, Apr. 1992.
• 3: G. J. Chaitin, M. A. Auslander, et al. Register allocation via coloring. Computer Languages, 6, 1981.
• 4: J.-F. Deverge and I. Puaut. WCET-Directed Dynamic Scratchpad Memory Allocation of Data. In Proceedings of ECRTS, Pisa, July 2007.
• 5: H. Falk, P. Lokuciejewski, and H. Theiling. Design of a WCET-Aware C Compiler. In Proceedings of ESTIMedia, Seoul, Oct. 2006. ls12- www.cs.tu-dortmund.de/research/activities/wcc.
• 6: H. Falk, S. Plazar, and H. Theiling. Compile Time Decided Instruction Cache Locking Using Worst-Case Execution Paths. In Proceedings of CODES+ISSS, Salzburg, Oct. 2007.
• 7: D. W. Goodwin and K. D. Wilken. Optimal and Near-optimal Global Register Allocation Using 0-1 Integer Programming. Software: Practice and Experience, 26(8):929--965, Aug. 1996.
• 8: E. A. Lee. Absolutely Positive On Time: What Would It Take? IEEE Computer, July 2005.
• 9: P. Lokuciejewski, H. Falk, and P. Marwedel. WCET-driven Cache-based Procedure Positioning Optimizations. In Proceedings of ECRTS, Prague, July 2008.
• 10: G. Mandalika. Building Enterprise Applications with Sun Studio Profile Feedback. developers.sun.com/solaris/articles/building.html, 2007.
• 11: M. Poletto and V. Sarkar. Linear Scan Register Allocation. ACM TOPLAS, 21(5):895--913, Sept. 1999.
• 12: I. Puaut and C. Pais. Scratchpad memories vs locked caches in hard real-time systems: a quantitative comparison. In Proceedings of DATE, Nice, Apr. 2007.
• 13: S. Steinke, M. Knauer, L. Wehmeyer, and P. Marwedel. An Accurate and Fine Grain Instruction-Level Energy Model Supporting Software Optimizations. In Proceedings of PATMOS, Yverdon-Les-Bains, Sept. 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Performance

Keywords:
WCET, register allocation