Revisiting Graph Coloring Register Allocation
A Study of the Chaitin-Briggs and Callahan-Koblenz Algorithms

Keith Cooper, Anshuman Dasgupta, Jason Eckhardt

Presenter: Anshuman Dasgupta

Register Allocation
 Process of mapping values in the program to a limited setof physical registers on the target architecture

Program values contained in locations called virtualregisters
 Must handle arbitrarily large number of virtual registers
 Registers are the fastest members in the memory
hierarchy Proficient allocation extremely important for applicationperformance Most programs contain segments where the number ofvalues exceeds the number of physical registers

Allocator must insert loads and stores: spill code

Cooper, Dasgupta, Eckhardt

LCPC 2005

Register Allocation
 Spills are memory accesses and therefore expensive
 Register allocators attempt to minimize the number ofspills
 Optimal register allocation is a NP-complete problem
Allocation algorithms use heuristics to approximate
optimal solution

Cooper, Dasgupta, Eckhardt

LCPC 2005

Graph Coloring Register Allocation
 Effective approach: Use graph coloring to model theallocation problem

Build an interference graph Construct live ranges from examining program values
 Live ranges are nodes in the graph Edges between nodes indicate that they cannot share aphysical register. The nodes interfere.
 Each color represents a physical register Neighbor nodes cannot share the same color The interference graph encodes safety constraints
 The allocator respects these constraints to preserve

program semantics

Cooper, Dasgupta, Eckhardt

LCPC 2005

Graph Coloring Register Allocation
 We examine two graph coloring allocation algorithms

Popular Chaitin-Briggs algorithm
 Callahan-Koblenz algorithm
 We shall use two major points of comparison

Amount of spill code inserted
 Efficacy of copy removal
 Copy removal: Tries to merge two live ranges connectedby a register-to-register copy

Can decrease register pressure Important for good allocation

Cooper, Dasgupta, Eckhardt

LCPC 2005

The Chaitin-Briggs Register Allocator

spill codebuildcoalesce

spill costs

simplify

select6 major phases
 Aggressive coalescing phase• Iterates until no more copies can be coalesced away

Simple spill insertion strategy if coloring fails• Choose spill candidates using heuristics (spill costs)• Spill all occurrences of candidate live range: loads before
every use, stores after every definition• Restart process after adding spills

Cooper, Dasgupta, Eckhardt

LCPC 2005

The Chaitin-Briggs Register Allocator Often cited shortcomings:

No topological program information preserved ininterference graph Approximated via spill costs• References in deeper loop nests given higher spill costSpill-everywhere approach

Different strategy suggested by Callahan and Koblenz…

Cooper, Dasgupta, Eckhardt

LCPC 2005

The Callahan-Koblenz Register Allocator Callahan-Koblenz developed allocator around the sametime as Briggs
 Augments Chaitin-style allocator:
Builds hierarchical structure (tile tree) to represent
program flow
• A tile is a set of basic blocks

Tile boundaries are candidates for live-range splitting Tries to schedule spill code in less frequently executedblocks
 Algorithm is more intricate than Chaitin-Briggs


Cooper, Dasgupta, Eckhardt

LCPC 2005

Callahan-Koblenz: The Tile TreeT0start0T0.1
A0.10.2

T0.1.2
BCT0.2

0.1.2

Tile T0: {start, A, B, C D}
Tile T0.1: {A, B, C}
Tile T0.1.2: {B}Tile T0.2: {D}DCooper, Dasgupta, Eckhardt

LCPC 2005

The Callahan-Koblenz Register Allocator
postorder traversal of tile tree

tile treebuild & prefs

subtileconflicts

colorsummarize

summarize

spill code

preorder traversal of tile tree

rebuild

Cooper, Dasgupta, Eckhardt

resolveconflicts

color

LCPC 2005

The Callahan-Koblenz Register Allocator Implemented at Cray, published in 1991, but nocomparison with Chaitin-Briggs

 Key questions:

How does the Callahan-Koblenz approach affect:• The number of dynamic spill instructions executed• The removal of register-to-register copies
 Callahan-Koblenz inserts some extra branches. How
does this affect performance?
Cooper, Dasgupta, Eckhardt

LCPC 2005

Spill Code InsertionChaitin-Briggs
 Simple strategy for spill code insertion

Choose candidates based on spill heuristic

Prefer spilling nodes with lower values
Heuristic function for live range l, H(l) = SpillCostl / Degreel
SpillCostl = LoadCostsl + StoreCostsl

 10loopdepth(i)StoreCost =  10loopdepth(j)LoadCostl =lwhere i  SpillLoads(l), j  SpillStores(l)Cooper, Dasgupta, Eckhardt

LCPC 2005

Callahan-Koblenz Spill Costs
Higher values indicate better fit for a register (Reg (v)  Mem (v)) + LocalWeight (v)Weightt =ss

tssubtiles( t )LocalWeightt (v) = P(b)  Ref (v)bb blocks(t )Transfert (v) =  P(e)  Livee(v)e E (t )0,if ¬InRegt(v)Regt(v) =  min(Transfert (v),Weightt (v)), if InRegt(v)Transfert (v),if ¬InRegt(v)Memt(v) = 
if InRegt(v)0,Penalty Costs for tile boundary spills and differing locations
Cooper, Dasgupta, Eckhardt

LCPC 2005

Experimental Methodology
 Implemented both allocators on LLVM


LLVM from Univ. of Illinois is a SSA-based, language
independent, intermediate representation and compiler
framework We ran our experiments on:

Pentium 4, 3.2 GHz., 1 GB RAM, Redhat Linux 9.0
 7 allocatable general purpose integer registers
 8 floating point registers

Evaluated on SPEC CPU 2000 integer benchmarks andepic from the Mediabench suite

Cooper, Dasgupta, Eckhardt

LCPC 2005

Dynamic Spill Code Comparison

Mean spill-code reduction: 20.5 %Callahan-Koblenz can insert copies on tile boundaries
Improvement with tile boundary copies: 19.1%
On epic, does much worse…
Cooper, Dasgupta, Eckhardt

LCPC 2005

Why Callahan-Koblenz Performs Better
x = …

x = …

x = …
store x

def t

def t
store tdef tuses of tload tuses of t

uses of tload xHeavy use of x

Heavy use of x

Heavy use of x

Before allocation

Chaitin-Briggs

Callhan-Koblenz

Cooper, Dasgupta, Eckhardt

LCPC 2005

Execution Counts of Instructions Inserted by Callahan-Koblenz

 Note disproportionate number of dynamic memory spills on tile boundaries for epic

Occurs due to differing locations for global values at each level in triply
nested loops
 Can tweak spill heuristic to correct this anomaly

Cooper, Dasgupta, Eckhardt

LCPC 2005

Removal of register-to-register copies

Inter-register Copy Removal

r1 = x op yr2 = r1

use r2

r1 = x op y

After copy removal

r2 = r1

use r1

 Helps allocation by decreasing register pressure

Cooper, Dasgupta, Eckhardt

LCPC 2005

Different Strategies Used For Copy Removal
 Chatin-Briggs uses coalescing and biased coloring

Coalesce if r1 and r2 are connected by a copy and do notinterfere
 Copies between a physical and virtual register (instruction
peculiarities, procedure calling conventions) are marked
 Coloring phase attempts to assign the same color to thevirtual register Callahan-Koblenz uses preferencing

On encountering a copy between r1 and r2, add one to theother’s preference list
 Try to satisfy preference during coloring Chaitin-Briggs’ strategy is far more aggressive
Cooper, Dasgupta, Eckhardt

LCPC 2005

Copy Coalescing: Experimental Evaluation

 Coalescing + biased coloring outperforms preferencing

3.6% fewer static copies in code 4.5% fewer copies executed
 We expected coalescing to win but were surprised at thecompetitive performance of preferencing

Cooper, Dasgupta, Eckhardt

LCPC 2005

Callahan-Koblenz: Control-flow Overhead
 Tile tree construction may warrant an insertion of basic

blocksMost inserted blocks fall through to successor. No extra
branches needed Some do not.


We measured the overhead of these branches• 5.8% more static branches• But only marginal increase in branches executed: 1.4%

Branches at tile boundaries are infrequently executed

Cooper, Dasgupta, Eckhardt

LCPC 2005

Execution Times of Allocated CodeCallahan-Koblenz achieves a 6.1% improvement over Chaitin-Briggs onaverage We chose not to use this metric as our major criteria for comparison• Very architecture dependent• Might not reflect qualitative differences in allocation

Cooper, Dasgupta, Eckhardt

LCPC 2005

Conclusions
 Considering program structure yields substantial

reduction in dynamic spill codeTile boundary based spilling outperforms spill-everywhere We were concerned about the performance of Callahan-

Koblenz’s copy coalescing mechanism
Chaitin-Briggs is very aggressive in removing copies

 Preferencing does reasonably wellPerforms within 4.5% of Chaitin-Briggs

 Control-flow overhead incurred by Callahan-Koblenz issmall

Cooper, Dasgupta, Eckhardt

LCPC 2005

Future Work
 Use insights gained from examining the allocators to devise better

allocation strategiesHybrid approach: Use aggressive coalescing with Callahan-Koblenz

 Several improvements have been suggested in the literature toaddress the spill-everywhere approachCompare these strategies with Callahan-Koblenz

 Both allocators are compile-time intensive

Can we design faster allocators while preserving allocation efficacy?
 Will be invaluable in a JIT environmentCooper, Dasgupta, Eckhardt

LCPC 2005