Презентация на тему Linear scan. Register allocation

mapping an unbounded number of virtual registers to physical

ones
Good register allocation is necessary for performance
Several SPEC benchmarks benefit an order of magnitude from good allocation
Core memory (and even caches) are slow relative to registers
Register allocation is expensive
Most algorithms are variations on Graph Coloring
Non-trivial algorithms require liveness analysis
Allocators can be quadratic in the number of live intervals

quickly
Just-In-Time compilation
Dynamic code generation in language extensions (‘C)
Interactive environments

(IDEs, etc.)
Sacrifice code speed for a quicker compile.
Find a faster allocation algorithm
Compare it to the best allocation algorithms

instructions, outside of which a variable v is never

live.
(For this paper, intervals are assumed to be contiguous)
Spilling: Variables are spilled when they are stored on the stack
Interference: Two live ranges interfere if they are simultaneously live in a program.

as a graph coloring problem
Nodes represent live ranges
Edges represent

interferences
Colorings are safe allocations
Order V2 in live variables

(See Chaitin82 on PLDI list)

analysis
Walk through intervals in order:
Throw away expired live intervals.
If

there is contention, spill the interval that ends furthest in the future.
Allocate new interval to any free register

Complexity: O(V log R) for V vars and R registers

= < A >

= < A >
2. Active = < A, B

>

= < A >
2. Active = < A, B

>
3. Active = < A, B > ; Spill = < C >

= < A >
2. Active = < A, B

>
3. Active = < A, B > ; Spill = < C >
4. Active = < D, B > ; Spill = < C >

= < A >
2. Active = < A, B

>
3. Active = < A, B > ; Spill = < C >
4. Active = < D, B > ; Spill = < C >
5. Active = < D, E > ; Spill = < C >

run-time performance
Two Implementations
ICODE dynamic ‘C compiler; (already had efficient

allocators)
Benchmarks from the previously used ICODE suite (all small)
Compare against tuned graph-coloring and usage counts
Also evaluate a few pathological program examples
Machine SUIF
Selected benchmarks from SPEC92 and SPEC95
Compare against graph-coloring, usage counts, and second-chance binpacking
Compare both metrics on both implementations

Linear Scan, and Graph Coloring shown
Linear Scan allocation is

always faster than Graph Coloring

is around twice as fast than Binpacking
(Binpacking is known

to be slower than Graph Coloring)

interfering over the entire program execution
Other pathological cases omitted

for brevity; see Figure 6.

faster than Binpacking and Graph Coloring
works in dynamic code

generation (ICODE)
scales more gracefully than Graph Coloring


… but does it generate good code?

Linear Scan, and Graph Coloring shown
Dynamic kernels do not

have enough register pressure to illustrate differences

Counts, Linear Scan, Graph Coloring and Binpacking shown
Linear Scan

makes a fair performance trade-off (5% - 10% slower than G.C.)

than Binpacking and Graph Coloring
works in dynamic code generation

(ICODE)
scales more gracefully than Graph Coloring
generates code within 5-10% of Graph Coloring

Implementation alternatives evaluated in paper
Fast Live Variable Analysis
Spilling Hueristics

alternative to Graph Coloring for register allocation

Linear Scan generates

faster code than similar algorithms (Binpacking, Usage Counts)

Where can we go from here?
Reduce register interference with live range splitting
Use register move coalescing to free up extra registers