CS 320: Compiling Techniques

COS 320 - Assignment 8

Compiling Techniques, Spring 2012, Princeton University. Due date: Monday 16 April.

Liveness Analysis

Warning: This assignment is not a trivial one. Don't put it off until the last minute.

Implement a liveness analyzer for Mips programs.

Copy all your as7 files into a fresh as8 directory, and unpack as8.zip. The new files are graph.sig, graph.sml, liveness.sml. Modify sources.cm as appropriate.
Implement the analyze function in liveness.sml.
Add a line to your compile.sml to call liveness analysis on each function in your Mips.program (including main, alloc, _printint).
Debug by examining the diagnostic output printed by Liveness.interference_graph.
Turn in README and liveness.sml to dropbox here.

The Graph module

Read graph.sig. It's different than the one described in Section 10.2 of the textbook; it's more streamlined and easier to use.

signature GRAPH = sig

 structure S : ORD_SET

 type node = S.Key.ord_key

 type graph

 val succ: graph -> node -> S.set

 val pred: graph -> node -> S.set

 val adj: graph -> node -> S.set

 val newGraph: unit -> graph

 val mk_edge: graph -> {from: node, to: node} -> unit

 val rm_edge: graph -> {from: node, to: node} -> unit

 val nodes: graph -> S.set

end

Graphs are based on the ORD_SET abstraction from the SML/NJ library. The node is just any ordered type, with its ordering relation given by S.compare. For register-interference graphs, we use node=Mips.reg (that is, S=Mips.RegSet). (For flowgraphs, we could use node=Mips.lab, but we won't use explicit flowgraphs; see below.)

Let IG be an instance of the GRAPH signature in which IG.S=Mips.RegSet, that is, we have a graph of registers. We describe this in ML as,

structure IG: GRAPH where S=Mips.RegSet

and you'll notice exactly this line in the LIVENESS signature.

To actually construct this structure IG, we apply the OrdGraph functor from graph.sml, as follows:

 structure IG = Graph(Mips.RegSet)

and you can see that this is already done for you in liveness.sml.

Given a graph g, one can get the set of all of its nodes by IG.nodes(g). One can get all the successors of a node n (that is, all the nodes x such that there is an edge from n to x) by IG.succ g n. One can get all the predecessors (the nodes x such that there is an edge from x to n) by IG.pred g n One can get the adjacent nodes (that is, the union of the successors and the predecessors) by IG.adj g n, which is completely equivalent to IG.S.union(IG.pred g n,IG.succ g n). (And by the way, IG.S.union is the same as Mips.RegSet.union.)

Graphs are destructively modified by the operations mk_edge and rm_edge. To make a new, empty graph, do IG.newGraph(). To add an edge (x,y), do IG.mk_edge{from=x,to=y}; if that edge is already in the graph, then adding it again doesn't have any effect. To remove an edge (x,y), do IG.rm_edge{from=x,to=y}; if that edge was not in the graph, then removing it doesn't have any effect.

Q. For interference graphs, we need undirected edges, not directed edges...
A. To add an edge, just add either direction of the directed edge. To query, just use the adj function.
Q. Can a node be in the graph if it doesn't have any edges?
A. Yes.
Q. How can I add a node to the graph without any edges?
A. Well, you could do the query IG.succ g x, which adds the node x to the graph if it wasn't already there.
Q. Ugh! That's horrible.
A. Well, nobody's perfect.

The Liveness module

Your task is to implement liveness analysis. In liveness.sml you can see this signature:

signature LIVENESS = sig

 structure IG: GRAPH where S=Mips.RegSet

 val analyze: {mention: Mips.reg -> unit,

               interfere: Mips.reg -> Mips.reg -> unit} ->

            Mips.funcode -> unit

 val interference_graph: Mips.funcode -> IG.graph

 val printgraph: (string->unit) -> IG.graph -> unit

end

The analyze function is given a list of basic blocks, and is expected to report all the variables that appear, and all the interferences it finds. It does this by calling mention on every register and pseudoregister that is ever used or defined by any instruction in the block, and by calling interfere on any pair of registers that must not be allocated to the same register.

It's perfectly all right to mention the same variable many times, or to call interfere on the same pair of variables again.

Examine the function interference_graph and you'll see that the way it works is to call analyze with an interfere function that adds an edge to an interference graph.

The algorithm

Instead of using Algorithm 10.4 exactly as written, I suggest you use this variation. This is only a sketch of the algorithm; you will have many design decisions to make for yourself about how best to implement this in ML.

Let n range over the set of block labels. Let live_at be a Symbol.table, mapping labels to sets of registers (Mips.RegSet.set). Let block ( n ) be the list of instructions comprising the block with label n. Let nextblock ( n ) be the label that comes after n (into which the last instruction of block n might fall through).

for each n

  live_at[n] := {}

repeat

  changed := false

  for each n

    new = compute_live_in(block( n ), live_at[nextblock( n )])

    if new <> live_at[n] then changed := true

    live_at[n] := new

until not changed

If you compare to Algorithm 10.4, you see that live_at[n] serves the same purpose as in[n].

The algorithm compute_live_in(il,live_at_end), where il is a list of instructions, works something like this:

compute_live_in(i::rest, live_at_end) =

let live_out = compute_live_in(rest, live_at_end) in

  if i is a straight-line instruction

  then return (use(i) + (live_out - def(i)))

  else if i is a conditional branch to label L

  then return (use(i) + ((live_at[L] + live_out) - def(i)))

  else if i is an unconditional branch to label L

  then return (use(i) + (live_at[L] - def(i)))

compute_live_in(nil, live_at_end) =

  return live_at_end

Uses and defs

The function Mips.instr_def_use can be very helpful, as it computes the uses and defs of all the instructions.

Jal instruction def-use: Note that Mips.instr_def_use does NOT fully report the uses and defs of the Jal instruction. This is because those uses and defs depend on how the client of mips.sml chooses to implement procedure-call conventions. You'll have to special-case this instruction. The appropriate uses are the actual-parameter registers ($a0); the defs are the caller-save registers, the return-address register, and the return-result register ($v0).

System call def-use: The Mips system-call instruction has different uses and defs, depending on the value of $v0. I suggest that you assume that the syscall instruction is always immediately preceded by a load-immediate (li) instruction that sets $v0. Then you can use the following hack:

compute_live_in(M.Li(r, i)::M.Syscall::rest, live_out) =>

 if r = Mips.reg "$v0"

 then (case M.syscall_def_use (M.immed2int i)

 of SOME {use,def} => (use + (live_out - def))

 | NONE => ErrorMsg.impossible "Unknown Syscall")

 else ErrorMsg.impossible "Syscall not preceded by li $v0"

Reporting interferences

I have left out of the sketch, above, the fact that the algorithm must report interferences (and "mention" every variable, just in case some variable is in the program but doesn't interfere with anything). Page 222 of your textbook (just before Section 10.2) gives the criteria for what interferences to report.

Debugging

I have found that it is very helpful to dump the contents of live_at in a format like this:

################## LIVENESS: _gt

_gt: $a0 $s0 $s1 $s2 $s3 $s4 $s5 $s6 $s7 $ra

L4: $x27 $x28 $x29 $x30 $x31 $x32 $x33 $x34 $x35

L3: $x27 $x28 $x29 $x30 $x31 $x32 $x33 $x34 $x35 $x41

L6: $x27 $x28 $x29 $x30 $x31 $x32 $x33 $x34 $x35

L5: $x27 $x28 $x29 $x30 $x31 $x32 $x33 $x34 $x35 $x44

L2: $x27 $x28 $x29 $x30 $x31 $x32 $x33 $x34 $x35

L1: $x27 $x28 $x29 $x30 $x31 $x32 $x33 $x34 $x35 $x39

L8: $x27 $x28 $x29 $x30 $x31 $x32 $x33 $x34 $x35

L7: $x27 $x28 $x29 $x30 $x31 $x32 $x33 $x34 $x35 $x48

_gt.epilog: $v0 $s0 $s1 $s2 $s3 $s4 $s5 $s6 $s7 $ra

Back to COS 320 front page