Outline of Lecture 15

Send me an e-mail for tutorial answers, or if you need help setting up a programming environment.

1. Expressing the results of CSE using AFTER, DEFTEMP and TEMP nodes.

... <LOADW, <LOCAL n>> ... <LOADW, <LOCAL n>> ...

becomes

... <AFTER, <DEFTEMP 1, <LOADW, <LOCAL n>>>, <TEMP n>> ... <TEMP n> ...

which canonicalises to

<DEFTEMP 1, <LOADW, <LOCAL n>>>
... <TEMP n> ... <TEMP n> ...

2. [Live demo] Expressing procedure calls: unnesting via CSE, flattening.

• multi-word arguments (e.g. procedural parameters, but also arrays with base and bound) are translated into multiple args by the front end. CSE is very effective when e.g. code address and static link both require following the static chain.

3. [Live demo] Spills needed when args overlap with temps.

4. Register allocation via the eval_reg interface: eval_reg / BINOP Times then gen_reg.

let rec eval_reg t r =
  match t with...
    | <BINOP Times, t1, t2> ->
        let v1 = eval_reg t1 R_any in
        let v2 = eval_reg t2 R_any in
        gen_reg "mul $0, $1, $2" r [v1; v2]

Outline of gen_reg:

let gen_reg fmt r rands =
  List.iter release rands;
  let r' = get_reg r in
  emit_inst fmt r' rands;
  register r'

5. Dealing with temps: exec_stmt / DEFTEMP, eval_reg / TEMP.

let rec exec_stmt =
  function ...
    | <DEFTEMP n, t1> ->
        let v1 = eval_reg t1 R_temp in
        Regs.def_temp n (reg_of v1)

And for <TEMP> nodes:

let rec eval_reg t r =
  match t with...
    | <TEMP n> ->
        gen_move r (Regs.use_temp n)

6. Dealing with arguments: exec_stmt / ARG n, exec_stmt / CALL n GLOBAL.

let rec exec_stmt =
  function ...
    | <ARG i, t1> when i < 4 ->
        spill_temps [R i];
        ignore (eval_reg t (R i))

    | <CALL n, <GLOBAL f>> ->
        spill_temps volatile;
        gen "bl $1" [symbol f];
        release_args ()

7. Limitations of this approach:

• Not knowing where we are going: greedy assignment leads to avoidable reg-to-reg moves.
• Running out of regs – we just die with an apology, but should be able to spill temps to memory, or recalculate.
• Limited regions for keeping values in registers: basic block or (quite useful) whole function, but not e.g. over a loop.

Solution – a properly optimising compiler that uses control-flow and data-flow analysis to track regions where a value is live, and allocate registers to live values more fluidly.