Lession 12--Differential Register Allocation Flashcards
Differential Register encoding
Instead of putting the register number, use the difference to the next register. This allows us to use less bits going from register to register.
RegN
Total number of registers
RegW
Number of bits in register field
DiffN
Number of distinct differences
DiffW
Number of bits needed for differences
Adjacency Graph
A directed weighted graph, each node representing a live range or register
set_last_reg
Solves “Difference out of range” and “Multipath inconsistency” issues. Allows us to set the register to the last register value, making the difference 0.
Edge Coverage
An edge is covered if the modulo difference of the two end nodes can be encoded after register allocation
Cost
Weight of uncovered edges (also the number of set_last_reg instructions needed to handle differences that cannot be fit int he register field)
Differential remapping
Remap register numbers after register allocation
Differential select
AG of live ranges instead of registers
Differential coalesce
Apply differential encoding to an optimal spilling register allocator