ACM SIGPLAN Notices · 2004 · 207 citations · 12 references
ComputingComputer EngineeringComputer ScienceCompilersComputer ArchitectureProgramming LanguagesControl-flow AnalysisData-flow AnalysisInstruction SchedulingRegister AllocationGlobal Register AllocationLocal Register AllocationRegister AssignmentRegisters
In previous work in global register allocation, the compiler colors a conflict graph constructed from liveness dataflow information, in order to allocate the same register to many variables that are not simultaneously live. If two procedures are in separately compiled modules, however, the compiler must do this allocation separately for each procedure. As a result, the two procedures might use different registers for the same global, or the same register for different locals.We can remove these problems if we delay the register allocation until link time. Our compiler produces object modules that can be linked and run without global register allocation, but includes with each object module a body of information describing how the module uses variables and procedures. A link-time register allocator then decides which variables are used most frequently, selects registers for them, and rewrites the code to reflect the decision that these variables reside in registers rather than in memory. Construction of the call graph allows us to use the same register for locals of procedures that are not simultaneously active, giving us most of the advantages of a full-scale coloring without the expense.When we use our method for 52 registers, our benchmarks speed up by 10 to 25 percent. Even with only 8 registers, the speedup can be nearly that large if we use previously collected profile information to guide the allocation. We cannot do much better, because programs whose variables all fit in registers rarely speed up by more than 30%. Moreover, profiling shows us that we usually remove 60% to 90% of the loads and stores of scalar variables that the program performs during its execution, and often much more.
12
Susan L. Graham, Peter B. Kessler, Marshall Kirk McKusick · 1982 · 978 citations
Register allocation & spilling via graph coloring
Gregory J. Chaitin · ACM SIGPLAN Notices · 1982 · 767 citations · Full text
Register allocation via coloring
Gregory J. Chaitin, Marc Auslander, Ashok K. Chandra et al. · Computer Languages · 1981 · 731 citations
Register allocation & spilling via graph coloring
Gregory J. Chaitin · 1982 · 668 citations
Reduced instruction set computers
David A. Patterson · Communications of the ACM · 1985 · 451 citations · Full text