Name
Abstract | ||
|---|---|---|
Many architectures require that a program use pairs of adjacent registers to hold double-precision floating-point values. Register allocators based on Chaitin's graph-coloring technique have trouble with programs that contain both single-register values and values that require adjacent pairs of registers. In particular, Chaitin's algorithm often produces excessive spilling on such programs. This results in underuse of the register set; the extra loads and stores inserted into the program for spilling also slow execution.An allocator based on an optimistic coloring scheme naturally avoids this problem. Such allocators delay the decision to spill a value until late in the allocation process. This eliminates the over-spilling provoked by adjacent register pairs in Chaitin's scheme.This paper discusses the representation of register pairs in a graph coloring allocator. It explains the problems that arise with Chaitin's allocator and shows how the optimistic allocator avoids them. It provides a rationale for determining how to add larger aggregates to the interference graph. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1145/130616.130617 | LOPLAS |
Keywords | Field | DocType |
coloring register pair,register allocation,interference graph,adjacent pair,register pair,optimistic coloring scheme,optimistic allocator,register set,program use pair,adjacent register pair,excessive spilling,graph coloring,adjacent register,floating point | Register allocation,Computer science,Parallel computing,Interference graph,Allocator,Graph coloring | Journal |
Volume | Issue | Citations |
1 | 1 | 11 |
PageRank | References | Authors |
1.59 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Preston Briggs | 1 | 379 | 32.43 |
| Keith D. Cooper | 2 | 1726 | 229.37 |
| Linda Torczon | 3 | 1096 | 146.31 |