Optimal spilling for CISC machines with few registers

A. W. Appel, L. George

Research output: Contribution to conferencePaper

80 Scopus citations

Abstract

Many graph-coloring register-allocation algorithms don't work well for machines with few registers. Heuristics for live-range splitting are complex or suboptimal; heuristics for register assignment rarely factor the presence of fancy addressing modes; these problems are more severe the fewer registers there are to work with. We show how to optimally split live ranges and optimally use addressing modes, where the optimality condition measures dynamically weighted loads and stores but not register-register moves. Our algorithm uses integer linear programming but is much more efficient than previous ILP-based approaches to register allocation. We then show a variant of Park and Moon's optimistic coalescing algorithm that does a very good (though not provably optimal) job of removing the register-register moves. The result is Pentium code that is 9.5% faster than code generated by SSA-based splitting with iterated register coalescing.

Original languageEnglish (US)
Pages243-253
Number of pages11
StatePublished - Jan 1 2001
EventACM SIGPLAN'01 Conference on Programming Language Design and Implementation (PLDI) - Snowbird, UT, United States
Duration: Jun 20 2001Jun 22 2001

Other

OtherACM SIGPLAN'01 Conference on Programming Language Design and Implementation (PLDI)
CountryUnited States
CitySnowbird, UT
Period6/20/016/22/01

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Optimal spilling for CISC machines with few registers'. Together they form a unique fingerprint.

  • Cite this

    Appel, A. W., & George, L. (2001). Optimal spilling for CISC machines with few registers. 243-253. Paper presented at ACM SIGPLAN'01 Conference on Programming Language Design and Implementation (PLDI), Snowbird, UT, United States.