INF564 - Lab 7 - ERTL Code Production, Liveness Analysis

The goal of this lab is to generate ERTL code for mini-C, then to perform liveness analysis on this code.

Provided Code

Once uncompressed (for instance with tar zxvf ertl-ocaml.tar.gz),you get a directory mini-c/ with the following OCaml files:

`Ertltree`	Explicit Register Transfer Language
`Ertlinterp`	ERTL interpreter (to test)

These modules are complete. Click on the module name to access its documentation. Take some time to read and understand what is provided.

1. ERTL Code Production

Ajouter au compilateur mini-C une fonction traduisant le code RTL en code ERTL, c'est-à-dire en une valeur du type Ertltree.file.

This new version of minic.ml extends the command line with an option --interp-ertl to execute the ERTL code and prints the ERTL code when we pass option --debug.

We strongly advise to proceed step by step, with systematic testing.

1.1. Unchanged Instructions

Start with instructions that are the same in RTL and ERTL, namely Rconst, Rload, Rstore, Rmunop, Rmbinop, Rmubranch, Rmbbranch, and Rgoto. It is a one-to-one mapping, which you can write as follows:

let instr = function
  | Rtltree.Econst (r, n, l) ->
      Econst (r, n, l)
  | ...

The only exception is that of instruction Rmbinop(Mdiv, r1, r2, l) for which r2 must be moved to %rax prior to the division, and for which the result in %rax must be moved to r2.

Do not handle instruction Rcall pour for the moment.

Then translate RTL functions to ERTL functions, using the translation of instructions above. As for RTL code production, the CFG under constructor can be stored in a global attribute. Add an instruction ERreturn at function exit.

Test with the following mini-C program:

int main() {
  return 42;
}

You must get something like this:

=== ERTL =================================================
main(0)
  entry : L2
  locals:
  L2: mov $42 #1  --> L1
  L1: return

Then test with more complex programs (but without function calls for the moment).

1.2. Function Call

Translate instruction RTL Rcall (r, f, rl, l). To do this,

pass the parameters (list rl) into the registers given by Register.parameters (with Mmov) and with the stack if there are too many (with ERpush_param);
make the call with ERTL instruction ERcall(f, n, ...) where n is the number of parameters passed in registers;
move Register.result to r ;
pop stack parameters, if any, using arithmetic on %rsp.

Test with mini-C programs such as

int fact(int n) {
  if (n <= 1) return 1;
  return n * fact(n-1);
}
int main() {
  return fact(42);
}

For the call fact(42), for instance, you must get something like this:

  L3: mov $42 #2  --> L2
  L2: goto L16
  L16: mov #2 %rdi  --> L15
  L15: call fact(1)  --> L14
  L14: mov %rax #1  --> L1

(a single parameter, passed in %rdi).

1.3. Translating a Function

Last, add new instructions at the entry and at the exit of each function.

at entry:
1. allocate the stack frame (instruction Ealloc_frame);
2. save the callee-saved registers (list Register.callee_saved) in fresh pseudo-registers;
3. move parameters from the registers in list Register.parameters (with Mmov) and from the stack and there are too many (with Eget_param).
at exit:
1. move the result to Register.rax;
2. restore the callee-saved registers;
3. delete the stack frame with instruction Edelete_frame;
4. end with instruction Ereturn (already done).

Test with mini-C programs such as

int fact(int n) {
  if (n <= 1) return 1;
  return n * fact(n-1);
}
int main() {
  return fact(42);
}

For function fact, for instance, you must get something like this:

fact(1)
  entry : L31
  locals: #11, #12
  L31: alloc_frame  --> L30
  L30: mov %rbx #11  --> L29
  L29: mov %r12 #12  --> L28
  L28: mov %rdi #3  --> L13
  ...
  L4: goto L36
  L36: mov #4 %rax  --> L35
  L35: mov #11 %rbx  --> L34
  L34: mov #12 %r12  --> L33
  L33: delete_frame  --> L32
  L32: return

Pseudo-registers #11 and #12 are used to save the callee-saved registers (here we show only two of them, but there are five).

1.4. Tests

Tests are provided in tests-v1.tar.gz.

Test like for RTL:

> ./run -i  "my/path/to/mini-c --interp-ertl"
Test de my/path/to/mini-c --interp-ertl

Interprétation
Execution normale
-----------------
...........................................................
Execution conduisant à un échec
-------------------------------
...
Compilation:
Compilation : 62/62 : 100%
Comportement du code : 62/62 : 100%

2. Liveness Analysis

We now perform the liveness analysis on the ERTL code. The goal is to build a function

val liveness: Ertltree.cfg -> live_info Label.map

with some ERTL control-flow graph as a parameter, which builds a map from each graph label to some information of the following type:

type live_info = {
         instr: Ertltree.instr;
          succ: Label.t list;    (* successeurs *)
  mutable pred: Label.set;       (* predecessors *)
          defs: Register.set;    (* definitions *)
          uses: Register.set;    (* uses *)
  mutable  ins: Register.set;    (* incoming live variables *)
  mutable outs: Register.set;    (* outcoming live variables *)
}

We advise to proceed as follows:

Build a table with all labels from the graph, with empty sets for fields pred, ins, and outs for the moment.
Functions Ertltree.succ and Ertltree.def_use are provided to fill fields succ, defs, and uses.
Traverse the table to fill the pred fields (the predecessors), from the information contained in the succ fields (the successors).
Last, implement Kildall's algorithm to fill the fields ins and outs.

To test, you can print the result with function Ertltree.visit together with the following:

let print_set = Register.print_set

let print_live_info fmt li =
  fprintf fmt "d={%a}@ u={%a}@ i={%a}@ o={%a}"
    print_set li.defs print_set li.uses print_set li.ins print_set li.outs

With a program such as

int main() {
  return 42;
}

you must get something like this:

  L5: alloc_frame  --> L4 d={} u={} i={%r12, %rbx} o={%r12, %rbx}
  L4: mov %rbx #2  --> L3 d={#2} u={%rbx} i={%r12, %rbx} o={#2, %r12}
  L3: mov %r12 #3  --> L2 d={#3} u={%r12} i={#2, %r12} o={#2, #3}
  L2: mov $42 #1  --> L1 d={#1} u={} i={#2, #3} o={#1, #2, #3}
  L1: goto L10 d={} u={} i={#1, #2, #3} o={#1, #2, #3}
 L10: mov #1 %rax  --> L9 d={%rax} u={#1} i={#1, #2, #3} o={#2, #3, %rax}
  L9: mov #2 %rbx  --> L8 d={%rbx} u={#2} i={#2, #3, %rax} o={#3, %rax, %rbx}
  L8: mov #3 %r12  --> L7 d={%r12} u={#3} i={#3, %rax, %rbx} o={%r12, %rax, %rbx}
  L7: delete_frame  --> L6 d={} u={} i={%r12, %rax, %rbx} o={%r12, %rax, %rbx}
  L6: return d={} u={%r12, %rax, %rbx} i={%r12, %rax, %rbx} o={}

Then test with more complex programs.

back to the main page