Studying optimal spilling in the light of SSA

Quentin Colombet, Florian Brandner, Alain Darte

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Recent developments in register allocation, mostly linked to static single assignment (SSA) form, have shown that it is possible to decouple the problem in two successive phases: a first spilling phase places load and store instructions so that the register pressure at all program points is small enough, a second assignment and coalescing phase maps the remaining variables to physical registers and reduces the number of move instructions among registers. This paper focuses on the first phase, for which many open questions remain: in particular, we study the notion of optimal spilling (what can be expressed?) and the impact of SSA form (does it help?). To identify the important features for optimal spilling on load-store architectures, we develop a new integer linear programming formulation, more accurate and expressive than previous approaches. Among other features, we can express SSA φ-functions, memory-to-memory copies, and the fact that a value can be stored simultaneously in a register and in memory. Based on this formulation, we present a thorough analysis of the results obtained for the SPECINT 2000 and EEMBC 1.1 benchmarks, from which we draw, among others, the following conclusions: a) rematerialization is extremely important, b) SSA complicates the formulation of optimal spilling, especially because of memory coalescing when the code is not in CSSA, c) micro-architectural features are significant and thus have to be accounted for, d) significant savings can be obtained in terms of static spill costs, cache miss rates, and dynamic instruction counts.
Keyword: register allocation,spilling,ssa,load-store architectures
Original languageEnglish
Title of host publicationCASES '11 Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems
PublisherACM USA www.acm.org/publications
Publication date1983
Pages25-34
ISBN (Print)978-14-50-30713-0
DOIs
Publication statusPublished - 1983
Externally publishedYes
EventCompilers, architectures and synthesis for embedded systems -
Duration: 1 Jan 2011 → …

Conference

ConferenceCompilers, architectures and synthesis for embedded systems
Period01/01/2011 → …

Cite this

Colombet, Q., Brandner, F., & Darte, A. (1983). Studying optimal spilling in the light of SSA. In CASES '11 Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems (pp. 25-34). ACM USA www.acm.org/publications. https://doi.org/10.1145/2038698.2038706