“Optimal” Spilling using Integer Linear Programming

  • 2011-05-27
  • Research

Static Single Assignment form (SSA) provides favorable properties that promise to simplify register allocation by splitting the problem into three subphases.


In recent years register allocation regained lots of attention. A major insight, triggering several exciting developments, was the fact that Static Single Assignment form (SSA) provides many favorable properties that promise to simplify register allocation by splitting the problem into three separate subphases: spilling, assignment, and coalescing.

This talk will focus on the spilling problem, i.e., the problem of evicting variables to temporary locations in memory in order to limit the number of required registers. The main problem here is the placement of load and store instructions such that execution time and code size are minimized. We propose a new exact spilling model based on Integer Linear Programming (ILP) in order to gain further insights of the problem for the development of new spilling heuristics. Our experiments show that existing heuristics and even previous “optimal” formulations still leave headroom for improvements.


Florian Brandner is currently a INRIA post-doc researcher at the Ecole Normale Supérieure de Lyon (France). He graduated from the Vienna University of Technology (Austria) in 2004 and received his PhD from the same university in 2009. His research is focused on the interaction between architecture design and compiler development. During his PhD he developed a processor modeling and exploration system, which allows to automatically generate software development tools such as a compiler and instruction set simulators from concise processor specifications. His current research focus is on exploiting Static Single Assignment form (SSA) in code generation algorithms such as register allocation, spilling, and instruction selection.


This talk is organised by the Compilers and Languages Group at the Institute of Computer Languages. Tea at the library of E185/1, Argentinierstr. 8, 4th floor (central) at 2:30 p.m.


Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!