Let's suppose you have a ir which is represented as a graph like this:
- The ir is not allowed to have branches
- Output of ir nodes is not mutable
While building pseudo assembly code for that, we can automaticlly insert "Drop" instructions which indicates to the register allocator that the Operand/Register can be freed.
Like the name says, we first reverse the graph. Our example from the top would then look like this:
We can now create a list of the already seen ir nodes:
let mut seen: Vec<IrNodeOutput> = Vec::new();While iterating from the top to the bottom, we can look if the following condition is met:
- Is the current ir node not in the seen list? If yes, we can insert following register allocation instruction and pseudo assembly nodes (in chronological time):
Drop(output of the ir node)- Compilation of the ir node
After that we reverse the generated assembly (This actually prodouces a few errors, we need to keep the
assembly as a Vec<Vec<PseudoAssembly>> so that it doesn't fuck up the internals. After reversing we can simply merge all the inner vectors
into one).
When the register allocator runs, it visits each pseudo assembly instruction.
If it encounters a unallocated operand, it allocates the operand (respecting the position wishes).
If it encounters a Drop(...) instruction, it frees the intern operand (adding it back to the free register/memory positions list)
All illustrations were made using Excalidraw. Here's the link: excalidraw drawing