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

Archive to download: ertl-java.tar.gz

Once uncompressed (for instance with tar zxvf ertl-java.tar.gz), you get a directory mini_c/ with the following Java files:

`ERTL.java`	Explicit Register Transfer Language
`ERTLinterp.java`	ERTL interpreter (to test)

These classes are complete and documented here. Take some time to read and understand what is provided.

1. ERTL Code Production

Extend the mini-C compiler with a function to translate RTL code to ERTL code, that is to produce a value with type ERTLfile. This new version of Main.java 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. You can use the visitor RTLVisitor provided at lab 6.

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 ERalloc_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 ERget_param).
at exit:
1. move the result to Register.rax;
2. restore the callee-saved registers;
3. delete the stack frame with instruction ERdelete_frame;
4. end with instruction ERreturn (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 class

class Liveness {

  Map<Label, LiveInfo> info;

  Liveness(ERTLgraph g) { ... }
}

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

class LiveInfo {
           ERTL instr;
        Label[] succ;   // successors
     Set<Label> pred;   // predecessors
  Set<Register> defs;   // definitions
  Set<Register> uses;   // uses
  Set<Register> ins;    // incoming live variables
  Set<Register> outs;   // outcoming live variables
}

We advise to proceed as follows:

Fill the table info with all labels from the graph, with empty sets for fields pred, ins, and outs for the moment.
Methods are provided in class ERTL 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 display the result with the following code:

  private void print(Set<Label> visited, Label l) {
    if (visited.contains(l)) return;
    visited.add(l);
    LiveInfo li = this.info.get(l);
    System.out.println("  " + String.format("%3s", l) + ": " + li);
    for (Label s: li.succ) print(visited, s);
  }

  void print(Label entry) {
    print(new HashSet<Label>(), entry);
  }

et d'une méthode toString appropriée dans la classe LiveInfo.

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