Lecture 12: Instruction Selection & Register Allocation
Instruction Selection
In the first part of this lecture we study target machine architecture and their instruction set, and we start looking and code generation. We study the operational semantics rules for arithmetic expressions in ChocoPy. And we explore the translation of arithmetic expressions consisting of integer constants and additions to RISC-V code. The code is somewhat naive, since it can run out of temporary registers. Possible solutions are to store temporary values on the stack or the use register allocation. We end with looking compilation schemas as an abstraction from the implementation details of transformation rules.
Register Allocation
In the second part of the lecture we look at register allocation, i.e. mapping symbolic variables to concrete machine registers. An interference graph represents the (simultaneous) use of variables, which we obtain from liveness analysis. Using graph coloring we assign concrete registers to variables such that no two variables that are live at the same time are assigned to the same register. When that is not possible variables need to be spilled to memory.
