:: Enseignements :: Master :: M2 :: 2016-2017 :: Machine Virtuelle (et bazar autour ...) ::

Lab 2b - Stack Interpreter (the return)

We now want to add the support of objects and implement a simple in-place garbage collector.
Here is a video of Gil Tene from Azul System explaining the different GC algorithms
Understanding Garbage Collection by Gil Tene

Exercice 1 - Allocation

First, we want to implement the operations NEW and GET defined like this:

  NEW classdesc
  GET fieldname

NEW instruction takes a JSObject stored in the dictionary as parameter that describes the fields and creates a new object in the heap.
The JSObject acts as a hashtable that stores for each field the offset of the field. By example,

  {
    x: 2,
    y: 4
  }

should be translated to

  CONST 2
  CONST 4
  NEW 'index'
  STORE local_index_of_point

with 'index' corresponding to the index in the dictionary of the JSObject { x: 0, y: 1 }.
In the heap, 4 integers should be reserved, the first one is the JSObject that describes the field of the object, the second one is for the GC and will be used in exercise 3. The fields 3 and 4 correspond to the field "x" and the field "y".
Note: the size of an object is the size of the header (2 fields in our implementation) + the length of the JSObject that describes the fields.
The instruction GET takes a field name as parameter, pops an object from the stack and push the value of the field of this object on the stack

Create an array of integers corresponding to the heap.
How to make the difference between a value which is a smallint, a value that represents an index in dictionary and a value that represents an instance of an object in the heap.
hint: given that the header of an object is 2 integers, we can align the instance of objects to be a multiple of 2. The other solution is to not align the header of an object and use a prefix to make the difference between an object in the heap and an object in the dictionary.
How to modify TagValues to reflect that changes ?
Add the two new instructions, NEW and GET and write the instructions corresponding to the following script
```
  var object = { a: 2, b: 3 };
  print(object.a);
        
```
Add the instruction NEW to the interpreter.
Verify that if you dump the value of the heap, the values are correct.
Verify that the following code will works
```
  var a = 3;
  var o = { foo: a, bar: a };
  print(o);
        
```
and modify the Rewriter to be able to generate a NEW.
Change the code of the Rewriter to introduce the generation of the instruction GET. You can verify that the following code works.
```
  var object = { a: 2, b: 3 };
  print(object.a);
        
```

Exercice 2 - Heap Bang & StackTrace

We want to detect if the heap is full and print the stacktrace

How to detect that the heap is full when doing a NEW ?
What data structure of the interpreter contains the information necessary to generate a stack trace ?
Write the code that generate a stack trace (without the line numbers) when the heap is full.
Be careful and verify that the method on top of the stack is the right one.

Exercice 3 - Garbage Collector

We now want to write a very simple on place garbage collector.

When the Garbage Collection algorithm should start ?
What does it mean that a Garbage Collection fail ?
What the VM should do in that case ?
We want to implement a Mark and Compact algorithm, in place.
What are the different phases of this algorithm ?
What it the different between a classical Mark and Compact and a Mark and Compact in place ?
Try to execute the algorithm on paper knowing that the header will have two slots, the first one will store the class (the JSObject containing the associating between a field and it's slot) and the second one i a word that can be freely used by the GC.
Write the algorithm part that mark the object recursively from the stack.
Write the algorithm part that calculate the future address of the instances that are marked in the heap.
Write the algorithm part that compact the heap.