1982/01/01 by Gregory J. Chaitin · 17 citations
Computer Science · #Parallel Computing and Optimization Techniques #Teaching and Learning Programming #Embedded Systems Design Techniques #Register allocation #Computer science #Compiler #Graph coloring #Parallel computing #Optimizing compiler #Graph #Register (sociolinguistics) #Compile time #Processor register #Computation #Programming language #Theoretical computer science #Operating system
paper · doi:10.1145/800230.806984
openalex publication_date 1982/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to the number of available machine registers, it must add code to spill and reload registers to and from storage. Previously the compiler produced spill code whose quality sometimes left much to be desired, and the ad hoe techniques used took considerable amounts of compile time. We have now discovered how to extend the graph coloring approach so that it naturally solves the spilling problem. Spill decisions are now made on the basis of the register conflict graph and cost estimates of the value of keeping the result of a computation in a register rather than in storage. This new approach produces better object code and takes much less compile time.