Iterated Register Coalescing

Lal George, Andrew W. Appel

Research output: Contribution to journalArticle

178 Scopus citations

Abstract

An important function of any register allocator is to target registers so as to eliminate copy instructions. Graph-coloring register allocation is an elegant approach to this problem. If the source and destination of a move instruction do not interfere, then their nodes can be coalesced in the interference graph. Chaitin's coalescing heuristic could make a graph uncolorable (i.e., introduce spills); Briggs et al. demonstrated a conservative coalescing heuristic that preserves colorability. But Briggs's algorithm is too conservative and leaves too many move instructions in our programs. We show how to interleave coloring reductions with Briggs's coalescing heuristic, leading to an algorithm that is safe but much more aggressive.

Original languageEnglish (US)
Pages (from-to)300-324
Number of pages25
JournalACM Transactions on Programming Languages and Systems
Volume18
Issue number3
DOIs
StatePublished - May 1996

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Algorithms
  • Copy propagation
  • D.3.4 [Programming Languages]: Processors - Code generation
  • G.2 [Discrete Mathematics]: Graph Theory - Graph algorithms
  • Graph coloring
  • Languages
  • Optimization
  • Register allocation
  • Register coalescing

Fingerprint Dive into the research topics of 'Iterated Register Coalescing'. Together they form a unique fingerprint.

Cite this