INF564 - lab 8 - LTL Code Production, Linearization

The goal of this lab is to implement LTL code production for mini-C, then its translation to x86_64 assembly.

Provided Code

Archive to download: ltl-ocaml.tar.gz

Once uncompressed (for instance with tar zxvf ltl-ocaml.tar.gz), you get the following OCaml modules:

`Ltltree`	Location Transfer Language (LTL)
`Ltlinterp`	LTL Interpreter (to make tests)
`X86_64`	x86-64 Assembly

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

1. LTL Code Production

The goal is to extend the mini-C compiler with a translation from ERTL to LTL, that is a value of type Ltltree.file. You can print such a value with function Ltltree.print_file.

As usual, we strongly advise to proceed step by step, with systematic testing.

1.1. Building the Interference Graph

An interference graph has vertices that are registers and two kinds of edges (interference and preference). An OCaml type for this is as follows:

type arcs = { prefs: Register.set; intfs: Register.set }
type igraph = arcs Register.map

Build such as graph from the liveness analysis, that is, implement a function

val make: live_info Label.map -> igraph

Hints:

make a first traversal of ERTL instructions (contained in the field instr of type live_info) to add a new preference edge for each instruction mov x y (with x and y distinct).
make a second traversal of ERTL instructions to add the interference edges.

Be careful to build an undirected graph (for each edge x-y we also have an edge y-x).

To debug, you can print the interference graph with the following function:

let print ig =
  Register.M.iter (fun r arcs ->
    Format.printf "%s: prefs=@[%a@] intfs=@[%a@]@." (r :> string)
      Register.print_set arcs.prefs Register.print_set arcs.intfs) ig

With a C program such as

int main() {
  return 42;
}

you should obtain something like

#1: prefs=%rax intfs=#2, #3
#2: prefs=%rbx intfs=#1, #3, %r12, %rax
#3: prefs=%r12 intfs=#1, #2, %rax, %rbx
%r12: prefs=#3 intfs=#2, %rax, %rbx
%rax: prefs=#1 intfs=#2, #3, %r12, %rbx
%rbx: prefs=#2 intfs=#3, %r12, %rax

1.2. Coloring the Interference Graph

We are now going to color the interference graph, that is to map a value of type Ltltree.operand (a physical register or a stack slot) to each pseudo-register. The coloring output is a map from pseudo-registers to colors, with the following type:

type color = Ltltree.operand
type coloring = color Register.map

Implement the coloring as a function with the following type:

val color: igraph -> coloring * int

The second output is the number of stack slots required by the spilled registers.

You do not have to implement George-Appel's algorithm presented in the lecture. You can go for something simpler, as follows:

put all pseudo-registers in a todo set
for each pseudo-register, maintain its available colors; initially, this is the difference between Register.allocatable and its interferences
as long as todo is not empty
- if a pseudo-register r has some available color c, remove r from todo and remove c from the available colors of all the interferences of r;
- otherwise, randomly pick up a pseudo-register to spill and remove it from todo.

When selecting a register to color, you can favor

a register with a single available color, and a preference for this color;
otherwise, a register with a single available color;
otherwise, a register with a preference whose color is set;
otherwise, a register with at least one available color, selected arbitrarily.

Spilled registers can be allocated linearly on the stack (i.e. each new spilled register picks the next available slot). Of course, we could do a much assignment (see the lecture).

To debug, one can print the coloring with the following function:

open Format
let print_color fmt = function
  | Reg hr    -> fprintf fmt "%a" Register.print hr
  | Spilled n -> fprintf fmt "stack %d" n
let print cm =
  RM.iter
    (fun r cr -> printf "%a -> %a@\n" Register.print r print_color cr) cm

With a C program such as

int main() {
  return 42;
}

you should obtain something like

  #1 -> %rax
  #2 -> %rbx
  #3 -> %r12

1.3. LTL Code Construction

To translate a function from ERTL to LTL, we need to

perform liveness analysis (see lab 7)
build the interference graph
color it
translate each ERTL instruction to one or several LTL instructions

This last step is very similar to the translation from RTL to ERTL (lab 7). You can store the control-flow graph under construction in a global reference and implement a function instr that translates one instruction, as follows:

let instr c frame_size = function
  | Ertltree.Econst (n, r, l) ->
      Econst (n, lookup c r, l)
  ...

where c is the coloring and frame_size is the size for the spilled registers.

The function lookup below maps a variable to its colors:

let lookup c r =
  if is_hw r then Reg r else M.find r c

You can print the LTL program with function Ltltree.print_file. With a C program such as

int main() {
  return 42;
}

you should obtain something like

=== LTL ==================================================
main()
  entry : L5
  L5: goto L4
  L4: goto L3
  L3: goto L2
  L2: mov $42 %rax  --> L1
  L1: goto L10
  L10: goto L9
  L9: goto L8
  L8: goto L7
  L7: goto L6
  L6: return

1.4. Tests

Extend your compiler with a new command line option --interp-ltl to execute the LTL code with function Ltlinterp.program.

Then you can test as follows:

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

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

2. Assembly Code Production

The very last step is to turn LTL code into x86-64 assembly code, that is to linearize the LTL control-flow graph. The module X86_64 provides means to build x86-64 assembly code and then to print it in a file.

2.1 Translating a LTL Function

To translate the LTL control-flow graph to assembly, you can use the following global variables:

let visited = Hashtbl.create 17
type instr = Code of X86_64.text | Label of Label.t
let code = ref []
let emit l i = code := Code i :: Label l :: !code
let emit_wl i = code := Code i :: !code
let labels = Hashtbl.create 17
let need_label l = Hashtbl.add labels l ()

The assembly code under construction is list !code (in reverse order). An instruction is added, together with a label, using function emit. The table visited stores the instructions already translated. The table labels stores the labels we need to keep in the final assembly code (jump targets).

Then you can implement two mutually recursive functions:

let rec lin g l =
  if not (Hashtbl.mem visited l) then begin
    Hashtbl.add visited l ();
    instr g l (Label.M.find l g)
  end else begin
    need_label l;
    emit_wl (jmp (l :> string))
  end

and instr g l = function
  | Econst (n, r, l1) ->
      emit l (movq (imm32 n) (operand r)); lin g l1
  ...

Function lin produces code from a given label, if not already done, and a jump to that label otherwise. Function instr produces the code from a given label and its corresponding instruction.

Function operand above, that you have to implement, translates a LTL operand with type Ltltree.operand to an x86-64 operand with type X86_64.operand. To translate a register with type Register.t to a register with type X86_64.register, a function X86_64.register64 is provided.

Once the LTL graph is fully translated (by calling lin on the function entry label), we can filter !code to get rid of labels that are not in table labels and then concatenate the filtered list with operator ++ from module X86_64.

2.2 Translating a LTL Program

To translate a LTL program, we proceed as follows:

translate all the C functions, one by one, and concatenate the assembly codes with function ++ from module X86_64;
make function main visible for ld with globl;
append wrappers for functions putchar and malloc that ensure stack alignment, with function X86_64.inline.

When this is done, the main file can print the assembly code into a file with function X86_64.print_program.

With a C program such as

int main() {
  return 42;
}

you should obtain something like

        .text
	.globl main
main:
	movq $42, %rax
	ret
        .data

2.3 Final Tests

Test your compiler as follows:

> ./run -3  mon/chemin/vers/mini-c
Test de mon/chemin/vers/mini-c

Partie 3
Execution normale
-----------------
...........................................................
Execution conduisant à un échec
-------------------------------
../run: line 266: 12739 Segmentation fault      ./a.out > out
../run: line 266: 12751 Floating point exception./a.out > out
../run: line 266: 12763 Floating point exception./a.out > out

Compilation:
Compilation : 62/62 : 100%
Code produit : 62/62 : 100%
Comportement du code : 62/62 : 100%

back to the main page