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-java.tar.gz), you get a directory mini_c/ with the following Java files:

`Ops.java`	x86-64 operations to be used in instruction selection
`Label.java`	Labels
`Register.java`	Registers (x86-64 and pseudo-registers)
`RTL.java`	Register Transfer Language (RTL)
`RTLinterp.java`	RTL interpreter (to make tests)

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

Lab Assignment

In a new class ToRTL, implement a method

  RTLfile translate(File f)

that translates the typed tree (Ttree) to RTL code, that is to a value of type RTLfile. One option is to implement it using a visitor,as follows:

  class ToRTL extends EmptyVisitor { ... }

This new Main.java adds a command line option --interp-rtl to execute the RTL code (using class RTLinterp). Beside, the new main file outputs the RTL code (with method print from class RTLfile) 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 variable:

  RTLgraph graph; // graph under construction

Method add in class RTLgraph adds a new instruction to the graph, at a fresh label, and returns that label.

To translate an expression, one needs

a pseudo-register to hold its value at the end;
a label where to transfer the control.

To translate a statement, one needs

a label where to transfer the control;
a pseudo-register to hold the returned value if the statement is return ;
a label for the function exit (where to transfer the control if the statement is return).

Translate each mini-C function to a value of type RTLfun. To do so, create a fresh pseudo-register for the function result and a fresh label for the function exit, and then translate the function body (a statement).

Finally, translate a mini-C program to the type RTLfile, 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 cases for arithmetic operations (but not && and || for the moment).

The new RTL instructions to be used are: Rmunop, Rmbinop.

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 y, x;
  y = 40;
  x = 2;
  return y + x;
}

4. Statements

Add 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 method that, given and expression and two labels truel and falsel, translates the expression 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: Rcall.

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: Rload, Rstore.

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