INF564 - lab 8 - LTL Code Production, Linearization

Provided Code

Once uncompressed (for instance with tar zxvf ltl-java.tar.gz), you get the following Java files:

These classes are complete and documented here. Take some time to read and understand all this.

1. LTL Code Production

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

1.1. Building the Interference Graph

class Arcs {
  Set<Register> prefs = new HashSet<>();
  Set<Register> intfs = new HashSet<>();
}
class Interference {
  Map<Register, Arcs> graph;
}

  Interference(Liveness lg) {
    ...
  }

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

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

  void print() {
    System.out.println("interference:");
    for (Register r: graph.keySet()) {
      Arcs a = graph.get(r);
      System.out.println("  " + r + " pref=" + a.prefs + " intf=" + a.intfs);
    }
  }

int main() {
  return 42;
}

interference:
  #3 pref=[%r12] intf=[%rbx, %rax, #1, #2]
  %rbx pref=[#2] intf=[#3, %rax, %r12]
  %rax pref=[#1] intf=[#3, %rbx, %r12, #2]
  %r12 pref=[#3] intf=[%rbx, %rax, #2]
  #1 pref=[%rax] intf=[#3, #2]
  #2 pref=[%rbx] intf=[#3, %rax, %r12, #1]

1.2. Coloring the Interference Graph

class Coloring {
  Map<Register, Operand> colors = new HashMap<>();
  int nlocals = 0; // number of stack slots
  ...
}

  Coloring(Interference ig) {
    ...
  }

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

1. put all pseudo-registers in a todo set
2. for each pseudo-register, maintain its available colors; initially, this is the difference between Register.allocatable and its interferences
3. 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.

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

  void print() {
    System.out.println("coloring output:");
    for (Register r: colors.keySet()) {
      Operand o = colors.get(r);
      System.out.println("  " + r + " --> " + o);
    }
  }

int main() {
  return 42;
}

coloring output:
  #3 --> %r12
  #1 --> %rax
  #2 --> %rbx

1.3. LTL Code Construction

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

class ToLTL implements ERTLVisitor {
  private Coloring coloring; // coloring for the current function
  int size_locals; // size for the spilled registers
  LTLgraph graph;  // graph under construction
  ...
}

You can print the result with method print from class LTLfile. With a C program such as

int main() {
  return 42;
}

=== 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

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

2.1 Translating a LTL Function

class Lin implements LTLVisitor {
  private LTLgraph cfg; // graph under translation
  private X86_64 asm; // assembly code under de construction
  private HashSet<Label> visited; // instructions already translated
  ...

  private void lin(Label l) {
    if (visited.contains(l)) {
      asm.needLabel(l);
      asm.jmp(l.name);
    } else {
      visited.add(l);
      asm.label(l);
      cfg.graph.get(l).accept(this);
    }
  }

We translate a LTL function f as follows:

    cfg = f.body;
    asm.label(f.name);
    lin(f.entry);

2.2 Translating a LTL Program

• translate all the C functions, one by one;
• make function main visible for ld with asm.globl("main");
• append wrappers for functions putchar and malloc that ensure stack alignment.

With a C program such as

int main() {
  return 42;
}

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

2.3 Final Tests

> ./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%