2004/06/09 by Michael D. Smith, Norman F. Ramsey, Glenn Holloway · 2 citations
Computer Science · Mathematics · #Formal Methods in Verification #Parallel Computing and Optimization Techniques #Embedded Systems Design Techniques #Register allocation #Computer science #Graph coloring #Register (sociolinguistics) #Allocator #Graph #Parallel computing #Register file #Algorithm #Generalization #Programming language #Arithmetic #Theoretical computer science #Compiler #Instruction set #Mathematics
paper · doi:10.1145/996893.996875
openalex publication_date 2004/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
Graph-coloring register allocation is an elegant and extremely popular optimization for modern machines. But as currently formulated, it does not handle two characteristics commonly found in commercial architectures. First, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Second, multiple register names may be aliases for a single hardware register. We present a generalization of graph-coloring register allocation that handles these problematic characteristics while preserving the elegance and practicality of traditional graph coloring. Our generalization adapts easily to a new target machine, requiring only the sets of names in the register classes and a map of the register aliases. It also drops easily into a well-known graph-coloring allocator, is efficient at compile time, and produces high-quality code.