Target Code Generation - Crafting a Compiler - page 518

procedure P riority R eg A lloc ( proc , regCount )

ig ← build I nterference G raph ( proc )

unconstrained ←{ n ∈ nodes ( ig ) |neighbor C ount ( n ) < regCount }

constrained ←{ n ∈ nodes ( ig ) |neighbor C ount ( n ) ≥ regCount }

while constrained ∅ do

foreach c ∈ constrained |¬colorable

( c ) and can S plit ( c ) do

c 1 ( c )

constrained ← constrained −{ c }
if

, c 2 ← split

< regCount
then unconstrained ← unconstrained ∪{ c 1

neighbor C ount ( c 1)

}

else constrained ← constrained ∪{ c 1 }

if < regCount

then unconstrained ← unconstrained ∪{ c 2

neighbor C ount ( c 2)

}

else constrained ← constrained ∪{ c 2 }

d ∈ unconstrained and
neighbor

foreach

d ∈ neighbors

( c ) |

C ount ( d ) ≥ regCount

do

unconstrained ← unconstrained −{ d }
constrained ← constrained ∪{ d }

/ All nodes in constrained are colorable or cannot be split. /

p ← G et M ax P riority ( constrained )

if colorable ( p )

then Color p
else Spill p
Color all nodes ∈ unconstrained

end
function G et M ax P riority ( nodeSet ) returns Node

bestPriority ←−∞
foreach n ∈ nodeSet do
if

priority ( n ) > bestPriority

then
ans ← n
bestPriority ← priority ( n )

return ( ans )
end

Figure 13.20: A priority-based graph coloring register allocator