Lession 12--Differential Register Allocation

Question 1

Differential Register encoding

Answer 1

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.

Question 2

RegN

Answer 2

Total number of registers

Question 3

RegW

Answer 3

Number of bits in register field

Question 4

DiffN

Answer 4

Number of distinct differences

Question 5

DiffW

Answer 5

Number of bits needed for differences

Question 6

Adjacency Graph

Answer 6

A directed weighted graph, each node representing a live range or register

Question 7

set_last_reg

Answer 7

Solves “Difference out of range” and “Multipath inconsistency” issues. Allows us to set the register to the last register value, making the difference 0.

Question 8

Edge Coverage

Answer 8

An edge is covered if the modulo difference of the two end nodes can be encoded after register allocation

Question 9

Cost

Answer 9

Weight of uncovered edges (also the number of set_last_reg instructions needed to handle differences that cannot be fit int he register field)

Question 10

Differential remapping

Answer 10

Remap register numbers after register allocation

Question 11

Differential select

Answer 11

AG of live ranges instead of registers

Question 12

Differential coalesce

Answer 12

Apply differential encoding to an optimal spilling register allocator