INF564 - Lab 6 - Translation to RTL

The goal of this lab is to implement the translation to RTL for mini-C.

Provided Code

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

`Pp`	Pretty-printing library
`Ops`	x86-64 operations to be used in instruction selection
`Label`	Labels
`Register`	Registers (x86-64 and pseudo-registers)
`Rtltree`	Register Transfer Language (RTL)
`Rtlinterp`	RTL interpreter (to make tests)

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

Lab Assignment

In a new file rtl.ml, implement a function program that translates the typed tree (Ttree) to RTL code, that is to a value of type Rtltree.file.

This new minic.ml adds a command line option --interp-rtl to execute the RTL code (using function Rtlinterp.program). Beside, the new main file outputs the RTL code (with function Rtltree.print_file) when the command line option --debug is used.

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

1. Minimal Program

We start with

expressions limited to integer literals;
statements limited to blocks and return;
no variable, no structure declaration.

The CFG under construction can be stored in a global reference:

  let graph = ref Label.M.empty

It is useful to declare a function to add a new instruction to the graph, at a fresh label that is returned:

  let generate i =
    let l = Label.fresh () in
    graph := Label.M.add l i !graph;
    l

To translate expressions, introduce a recursive function as follows,

  let rec expr e destr destl = ...

where e is the expression to translate, destr is the destination pseudo-register, and destl is the destination label.

To translate statements, introduce a recursive function as follows,

  let rec stmt s destl retr exitl = ...

where s is the statement to translate and destl is the destination label. When the statement is return, the returned value must be stored in retr and the control must be transferred to label exitl (function exit).

Introduce a function deffun to translate a mini-C function to a value of type Rtltree.deffun. To do so, create a fresh pseudo-register for the function result and a fresh label for the function exit, and call function stmt above on the function body.

Finally, implement a function that translates a mini-C program to the type Rtltree.file, by translating each mini-C function independently.

Test with the following mini-C program:

int main() {
  return 42;
}

You must get something like this:

=== RTL ==================================================
#1 main()
  entry : L2
  exit  : L1
  locals:
  L2: mov $42 #1  --> L1

2. Arithmetic

Add to function expr the cases for arithmetic operations (but not && and || for the moment).

The new RTL instructions to be used are: Emunop, Embinop.

Test with programs such as

int main() {
  return 40 - (-2);
}

3. Variables

Add support for local variables (but not function parameters for the moment). Each variable is mapped to a fresh pseudo-register. (Later, register allocation will assign it a location.) You can introduce a table for that purpose.

Test with programs such as

int main() {
  int x, y;
  y = 40;
  x = 2;
  return y + x;
}

4. Statements

Improve function stmt with support for the missing statements, that is skip (;), expression evaluation (e;), conditional (if) and loop (while).

To translate statements if and while, it is useful to introduce a function

  let rec condition e truel false = ...

that translates an expression e to RTL and transfers control to label truel if the value is not zero and to label falsel otherwise.

Add support for C constructions && and ||, with the expected lazy semantics.

New RTL instructions to be used are: Emubranch, Embbranch, Egoto.

Test with programs such as

int main() {
  if (1 <= 2)
    return 3;
  else
    return 4;
}

5. Function Call

Add support for formal parameters and function call. Each formal parameter is mapped to a fresh pseudo-register. In a function call, actual parameters are passed in corresponding (fresh) pseudo-registres. Remark: There is no need to do anything special for call to predefined function putchar and malloc.

The new RTL instructions to be used are: Ecall.

Test with programs such as

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

6. Structures

Finally, add support for structures, that is, field access (e->x) and field assignment (e1->x = e2). Remark: There is nothing to do for a structure declaration.

The new RTL instructions to be used are: Eload, Estore.

Test with programs such as

struct S { int a; int b; };
int main() {
  struct S *p;
  p = malloc(sizeof(struct S));
  p->a = 40;
  p->b = 2;
  return p->a + p->b;
}

7. Tests

Reuse the same tests as in lab 4-5 (tests-v1.tar.gz) but this time with option -i of script run, as follows:

> ./run -i  "mon/chemin/vers/mini-c --interp-rtl"
Test de mon/chemin/vers/mini-c --interp-rtl

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

back to the main page