Lab 2b - Stack Interpreter (the return)

Exercice 1 - Allocation

1. Implement the instruction NEW in the StackInterpreter and verifies that the test maked Q13 in StackInterpreterInsnTest pass.
2. Verify that you can access to local variables to initialize the field of the object and that fields initialization are interpreted in the right order by running the tests marked Q14.
   Otherwise, change the code accordingly.
3. Implement the instruction GET in the StackInterpreter and verifies that the tests marked Q15 pass.
4. Implement the instruction PUT in the StackInterpreter and verifies that the tests marked Q16 pass.
5. Verify that the test marked Q17 that does a method call works.
6. Now that the interpreter is working, we need to implement the support of the AST nodes. First, implement the support of the node New in the Rewriter, and verify that the tests marked Q13 and Q14 in StackInterpreterTest pass.
   Note: you may need to change other part of the Rewriter.
7. Implement the AST node FieldAccess in the Rewriter and verifies that the tests marked Q15 pass.
8. Implement the AST node FieldAssignment in the Rewriter and verifies that the tests marked Q16 pass.
9. Implement the AST node MethodCall in the Rewriter and verifies that the tests marked Q17 pass.

Exercice 2 - Heap Bang & StackTrace

1. How to detect that the heap is full when doing a NEW ?
2. What data structure of the interpreter contains the information necessary to generate a stack trace ?
3. 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

1. When the Garbage Collection algorithm should start ?
   What does it mean that a Garbage Collection fail ?
   What the VM should do in that case ?
2. 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 ?
3. 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.
4. Cut and paste the skeleton of the GC algorithm that will help you to answer the next questions.

       private static void dumpHeap(String message, int[] heap, int hp, Dictionary dict) {
           System.err.println(message);
           for (var i = 0; i < hp; i++) {
               var value = heap[i];
               try {
                   System.err.println(i + ": " + value + " " + decodeAnyValue(value, dict, heap));
               } catch (IndexOutOfBoundsException | ClassCastException e) {
                   System.err.println(i + ": " + value + " (can't decode)");
               }
           }
           System.err.println();
       }
   
       private static void mark(int[] heap, int obj, Dictionary dict) {
           // if already marked, return
           // TODO
           // mark the object at the GC_OFFSET
           // TODO
           // call recursively to mark all other objects following the fields
           scanAnObject(heap, obj, dict, (addr, ref) -> mark(heap, ref, dict));
       }
       
       private static int gc(int requestedMemory, int[] stack, int sp, int bp, JSObject function, int[] heap, int hpEnd, Dictionary dict) {
           System.err.println("--------- start a gc " + hpEnd);
   
           // 1) scan the stack and recursively mark all reachable objects in the heap
           scanStack(stack, sp, bp, function, dict, (addr, ref) -> mark(heap, ref, dict));
   
           // 2) scan the heap to find the new addresses of all live objects
           // and store them in the corresponding object gc slot
           var virtual = new Object() { int hp; }; // 'virtual' hp, address of the object after the GC
           scanHeap(heap, hpEnd, dict, (ref, __, clazz) -> {
               // if its a live object
               //TODO
               {
                 // store the new address at gc offset
                 // TODO
                 // move virtual cursor
                 virtual.hp += OBJECT_HEADER_SIZE + clazz.length();
               }
           });
   
           // DEBUG
           System.err.println("new virtual hp at " + virtual.hp);
   
           // 3) do we have enough free memory ?
           if (virtual.hp > heap.length - requestedMemory) {
               // we are morons
               throw new Failure("out of memory error");
           }
   
           // 4) scan the heap to rewrite all field references to point to their new addresses
           scanHeap(heap, hpEnd, dict, (ref, __, clazz) -> {
               // if it's a live object (WARNING, it's not a GC_MARK anymore)
               // TODO
               {
                   // rewrite all reference fields
                   // TODO
               }
           });
           
           // 5) scan the stack to rewrite the stack reference to point to the new addresses
           scanStack(stack, sp, bp, function, dict, (addr, ref) -> {
               // TODO
           });
   
           // 6) scan the heap and move the objects
           scanHeap(heap, hpEnd, dict, (ref, tagClass, clazz) -> {
               // if it's a live object
               // TODO
               {
                   // get new address
                   // TODO
                   // copy fields (in reverse order because old object and new object can overlap)
                   for (var i = clazz.length(); --i >= 0;) {
                       // TODO
                   }
                   // recreate the header
                   // TODO
               }
           });
   
           return virtual.hp;
       }
       
       interface HeapClosure {
           void accept(int ref, int tagClass, JSObject clazz);
       }
       
       private static void scanHeap(int[] heap, int hpEnd, Dictionary dict, HeapClosure heapClosure) {
           // scan the heap and call the heapClosure on each objects of the heap
           // TODO
       }
       
       interface StackClosure {
           void accept(int addr, int ref);
       }
       
       private static void scanStack(int[] stack, int sp, int bp, JSObject function, Dictionary dict, StackClosure stackClosure) {
           for (;;) {
               // System.err.println("function " + function);
               var code = (Code) function.lookup("__code__");
               var activation = bp + code.getSlotVarCount();
   
               // scan the stack and call the stack closure on all references
               // System.err.println("scan stack");
               // TODO
   
               // scan the local variables and the stack closure on all references
               // System.err.println("scan locals");
               // TODO
   
               // find previous function from activation frame
               var previousFunction = stack[activation + FUN_OFFSET];
               if (previousFunction == 0) {
                   // end of the stack
                   return;
               }
               
               // update sp, bp and function
               sp = bp;
               bp = stack[activation + BP_OFFSET];
               function = (JSObject) decodeDictObject(previousFunction, dict);
           }
       }
   
       private static void scanAnObject(int[] heap, int ref, Dictionary dict, StackClosure referenceClosure) {
           // 1) get class descriptor from the heap
           // TODO
           // 2) Decoding the class object
           // TODO
           // DEBUG
           //System.err.println("found class " + clazz + " at " + ref);
   
           // 4) decode fields
           for (var i = 0; i < clazz.length(); i++) {
               // compute field address
               // TODO
               // get the field value
               // TODO
               // if is it a reference, call the reference closure
               // TODO
           }
       }
   
       private static final int GC_OFFSET = 1;
       private static final int GC_MARK = -1;
       private static final int GC_EMPTY = -2;
          

   
   What is the purpose of the two functional interfaces ?
5. Write the algorithm part that mark the object recursively from the stack.
6. Write the algorithm part that calculate the future address of the instances that are marked in the heap.
7. Write the algorithm part that rewrite all the references on the stack.
8. Write the algorithm part that rewrite all the references in the fields on the heap.
9. Write the algorithm part that compact the heap.
10. Test that your algorithm works by running all the tests in StackInterpreterGCTests.