Assignment 5: Hundred-pacer: Register Allocation
Due: Sun 11/05 at 11:59pm
git clone
The popular name “hundred pacer” refers to a local belief that, after being bitten, the victim will only be able to walk 100 steps before dying. Incorporating register allocation should allow your compiled code to complete its paces faster than before
This assignment will be a bit different from the others: there are no new features to implement and we won’t be testing your compiler’s input/output behavior directly. Rather this time you will be evaluated on how well you implement the component analyses of a register allocator. Incorporating the register allocation into your compiler is optional and will not be graded.
We break the assignment down into two parts. First, we need to analyze the code to determine which variables cannot be stored in the same register. Second, we use Chaitin’s graph coloring algorithm with a perfect elimination ordering derived from the function’s syntax to assign registers (or spilled stack slots) to all variables.
1 Liveness and Conflict Analysis
First need to figure out, for each global function definition in the program, which variables conflict with each other. We break this down into liveness analysis, which determines when a variable’s value is needed and conflict analysis which determines which variables are live at the same time with possibly different values.
We implement liveness analysis as a compiler pass, annotating all expressions with the free variables live at that point. It has the following type:
fn liveness<Ann>(e: &SeqExp<Ann>, params: &HashSet<String>) -> SeqExp<HashSet<String>> {
}
The parameter set params
are the parameters in the current
function body. You need this information because you should not treat
these parameters as part of your liveness analysis since where the
parameters are stored is dictated by the calling convention and so is
not subject to register allocation1more sophisticated
register allocators handle this by "pre-coloring" the parameters with
the register dictated by the calling convention. The output of this
function is an expression with the same structure as e
but with
each sub-expression annotated with the variables that are live in that
sub-expression. So for example, if the input expression were
let x = 3 in f(x, y, a)
where a
is a parameter, y
is not and
f
is a globally defined function, then your liveness
function would return the expression annotated as follows:
Let { var: "x",
bound_exp: Imm(Num(3), { }),
body: ExternalCall{ fun_name: "f", args: [Var("x"), Var("y"), Var("a")], is_tail: true, ann: {"x", "y"}},
ann: {"y"},
}
The inner ExternalCall
has both x
and y
live because both
values are used as arguments. a
is not live since it is a
parameter. The outer Let
only has y
live in it because
x
is written to in the let.
The liveness function returns a SeqExp<HashSet<String>>
, an
expression annotated with its liveness information. To extract the
liveness information for an expression you can use the .ann()
method implemented in syntax.rs
.
As discussed in the Monday, October 30th lecture, the algorithm we
gave for liveness analysis only works correctly when the
SeqExp
s are "fully flattened", meaning the bound_exp
of
a let expression can only ever be an immediate, call or primitive
operation, and not a let, if or fundef expression. The autograder will
only test your analysis on examples that are fully flattened in this
way, but if you want to incorporate register allocation in your
compiler you should add a pass to flatten your expressions first.
Next, given our liveness analysis, we go through and determine what
the conflicts are. This generates a graph that will be the
input to our graph coloring function.
The conflicts
function has the following type.
fn conflicts(e: &SeqExp<HashSet<String>>) -> Graph<String>
The output of the conflicts function is a Graph<String>
representing the conflicts between variables. The Graph
datatype is provided in the graph.rs
module, and represents an
undirected graph. Each method is documented with a brief
description. Note that other than Graph::new()
, these are all
methods on a graph, so for instance to insert a vertex v
into a
graph g
using the insert_vertex
method, you invoke the
method as g.insert_vertex(v)
.
Make sure you insert all let-bound variables and arguments to local function definitions into the graph you produce so that they are all assigned a register, even if they have no conflicts. To ensure that you don’t put any parameters in your output graph, add the variables into your output when you see them defined, rather than when they are used.
2 Graph Coloring
Now that we have our conflict graph, we attempt to assign each vertex a "color", i.e., register. As shown in class, we will use Chaitin’s algorithm, but using the perfect elimination order derived from the syntax being in SSA form.
So first you should implement
fn elimination_order<Ann>(e: &SeqExp<Ann>) -> Vec<String>
which produces an ordering of all of the variables defined in
let
and local function definitions so that if
x
is in scope when y
is defined, then
x
occurs before y
in the output vector. So
for example in
let x = 5 in
let y = x * 3 in
y * x
[x,y]
because x
is in
scope when y
is defined.fn graph_color(
conflicts: Graph<String>,
elimination_order: &[String],
registers: &[Reg],
) -> HashMap<String, VarLocation>
You are given the register interference graph, a vector of variables
representing the elimination order and a slice of registers to be used
in register allocation and you should return a HashMap mapping the
variables in the input graph to a VarLocation
, which is either
a register VarLocation::Reg(r)
or a stack offset
VarLocation::Spill(i)
.
Chaitin’s algorithm is defined recursively by removing a vertex from the graph, recursively coloring the rest of the graph and then adding the vertex back in and coloring it with the next available color. You must remove the vertices in the order given by the elimination ordering to ensure that you color the graph optimally.
We parameterize the graph coloring algorithm by which registers we are using so that we can test spilling more easily by passing in fewer registers. You may find this useful for incrementally implementing your use of registers as well2For instance you might first use no registers, then use only caller-save registers and finally both caller-save and callee-save registers.
3 Recommended TODO List
We suggest handling the graph coloring routines in the following order:
liveness
conflict analysis
elimination order
graph coloring
4 List of Deliverables
your
analysis.rs
, in particular theliveness
,conflicts
andallocate_registers
functionsany additional rust files you saw fit to write
the Cargo.toml
5 Grading Standards
This assignment will be solely autograded. There will not be any hidden tests.
There are two kinds of tests:
Liveness/Conflict analysis tests to test the soundness and precision of your analyses
Full register allocator tests that ensure you always give valid register/spill assignments and don’t spill when unnecessary
6 Submission
Wait! Please read the assignment again and verify that you have not forgotten anything!
Please submit your homework to gradescope by the above deadline.1more sophisticated register allocators handle this by "pre-coloring" the parameters with the register dictated by the calling convention
2For instance you might first use no registers, then use only caller-save registers and finally both caller-save and callee-save registers