Register allocation validator
This issue describes the algorithm for the register allocation validation in Zebu.
Eliot proposed the approach. I implemented it in Zebu, and put the pseudo code here. I am not exactly confident if I have captured all the ideas from Eliot, and implemented it correctly. This issue serves as a record of how the register allocation validation works. Any discussion is welcome, and it may help future work.
Input: register assignment ASSIGNED(reg) -> mreg, and code.
Output: PASS if ASSIGNED is correct; or ERROR if it is not.
Assumptions:
- we have correct liveness information.
- spill code (
SPILL_LOAD/SPILL_STORE) is already inserted, and spilled virtual registers are replaced with short-lived virtual registers, and we know the mapping.
We are trying to iterate through the code focusing on registers by maintaining analive set, each entry of which is a 3-element tupleENTRY(reg, machine_reg, mem), meaningregis alive (contains a valid value) at the moment inmachine_regand spilled locationmem. -
(-, machine_reg, -)means a machine register is alive, but no virtual register and no spill location is associated. -
(*, machine_reg, *)means matching entries that havemachine_reg -
(reg?, machine_reg, *)means matching entries that havemachine_reg, and naming the first element asreg(it may exist or not)
We have a few primitives about alive set -
x <- ALIVE[block]loads alive set forblockand uses aliasxfor it. -
x.ADD_ALIVE(r, m, mem)adds(r, m, mem)to alive setx. -
ALIVE[block] <- xsaves alive setxwithblock. -
x.ASSERT_ALIVE(r, m, mem)tries to match pattern(r, m, mem). If no entry is found, ends withERROR. -
x.KILL_ALIVE(r, m, mem)tries to match pattern(r, m, mem). If any entry is found, delete the entries. -
x.EXIST_ALIVE(r, m, mem)tries to match pattern(r, m, mem). If any entry is found, it is true. -
x.TRIM(list): for anyr,minlist, preserve them inx, delete other entries inx -
x.INTERSECT(y): if(r, m, *)or(-, m, *)appear in bothxandy, preserve it inx; otherwise delete it fromx. -
y <- x.COPY: copyxintoy
Pseudo code:
// set the initial alive set for a function start
init.ADD_ALIVE(-, stack pointer, -)
init.ADD_ALIVE(-, frame pointer, -)
init.ADD_ALIVE(-, program counter, -)
init.ADD_ALIVE(-, callee saved registers, -)
init.ADD_ALIVE(-, used argument registers, -)
push entry block to work queue
ALIVE[entry block] <- init
while work queue is not empty {
pop work queue -> block
alive <- ALIVE[block]
for each inst in block {
// (1) check spill
// we only care about the variable before spilling
if inst is SPILL_LOAD(mem) -> t for var v {
alive.ASSERT_ALIVE(v, *, mem)
} else if inst is SPILL_STORE(t) -> mem for var v {
alive.ADD_ALIVE(v, -, mem)
}
// (2) check use
// when we use a register, it needs to contain a valid value
for reg in inst.virtual_register_uses() {
mreg = ASSIGNED(reg)
alive.ASSERT_ALIVE(reg, mreg, *)
}
for mreg in inst.real_register_uses() {
alive.ASSERT_ALIVE(*, mreg, *)
}
// (3) kill died regs
// when a register dies, we remove its entry from alive set
for reg in inst.virtual_register_dies() {
alive.KILL_ALIVE(reg, *, *)
}
for mreg in inst.real_register_dies() {
alive.KILL_ALIVE(*, mreg, *)
}
// (4) check and add defines
for reg in inst.virtual_register_defines() {
if reg NOT in inst.liveout() {
// when a register is defined, but doesnt live out of this instruction
// we kill its previous values from alive set (by deleting the entries)
alive.KILL_ALIVE(reg, *, *)
} else {
mreg = ASSIGNED(reg)
if NOT alive.EXIST_ALIVE(*, mreg, *) {
// mreg doesnt hold any value at the moment, we simply add an entry
alive,ADD_ALIVE(reg, mreg, -)
} else {
// we need to ensure assigning mreg will not destroy useful values
for (x?, mreg, *) in ALIVE {
if x NOT exist {
x <- reg
} else {
// we have x in mreg, and we want reg in mreg as well
if x == reg {
// overwrite value (safe)
} else {
if inst is MOVE {
// possible coalescing (safe)
} else {
// we are destroying the value of x
// and x is alive at the moment (otherwise it is killed already in step 3)
ERROR
}
}
}
alive.ADD_ALIVE(reg, mreg, -)
}
}
}
}
for mreg in inst.real_register_defines() {
if mreg NOT in inst.liveout() {
// when a register is defined, but doesnt live out of this instruction
// we kill its previous values from alive set (by deleting the entries)
alive.KILL_ALIVE(*, mreg, *)
} else {
if NOT alive.EXIST_ALIVE(*, mreg, *) {
// mreg doesnt hold any value at the moment, we simply add an entry
alive.ADD_ALIVE(-, mreg, -)
} else {
for (reg?, mreg, -) in ALIVE {
if reg NOT exist {
// we have value in mreg, but it doesnt hold value of any variables
// overwrite the value is safe
} else {
// we are holding reg in mreg, defining mreg will destroy the value of reg
ERROR
}
}
}
}
}
// finishing the block, we only preserve what are alive at the end of the block
alive.TRIM(block.liveout())
if block is NOT visited {
ALIVE[block] <- alive
push_successors = true
} else {
alive_before <- ALIVE[block]
alive.INTERSECT(alive_before)
if alive <> alive_before {
push_successors = true
}
ALIVE[block] <- alive
}
mark block as visited
if push_successors {
if block has 1 successor {
push successor to work queue
ALIVE[successor] <- alive
} else block has 2 successors {
push successor1 to work queue
alive1 <- alive.COPY
ALIVE[successor1] <- alive1.TRIM(successor1.livein())
push successor2 to work queue
alive2 <- alive.COPY
ALIVE[successor2] <- alive2.TRIM(successor2,livein())
}
}
}
}