In this assignment, you will implement a garbage collector to manage the memory allocation for the Lacs language.
In preparation for the rest of this assignment, implement
copyChunk in MemoryManagement.scala if you
did not do so already as part of the bonus of Assignment 6.
In Transformations.scala,
in the Assignment 6 version of the addEntryExit method, the
prologue currently saves the address of the parameter chunk being passed
in using the result register into the
savedParamPtr register, and then it allocates the frame for
the procedure, either on the stack or on the heap. When we implement the
garbage collector, the process of allocating a chunk on the heap will
involve calling procedures, namely the procedures that implement the
garbage collector. To make procedure calls possible, the frame of the
current procedure (the caller) must already be fully set up. There is a
cyclic dependency: allocating the frame requires procedure calls, but
procedure calls require the frame to be allocated and fully set up. One
solution to this is to always allocate a temporary frame on the stack
first. Then we can allocate the permanent frame on the heap (and we can
call procedures in the process of doing so). Finally, we can copy the
temporary frame from the stack into the permanent frame on the heap, and
pop the temporary frame off the stack. Implement this solution in the
addEntryExit method, and check that your compiler still
passes the Marmoset tests for Assignments 5, 6, and 10. If your compiler
previously did not pass all of the tests for those assignments, check
that it still passes the same tests that it used to pass.
In MemoryManagement.scala, review
the comments of the Chunk class, and ensure that your
implementation of the methods variableToOffset,
load, store, and initialize is
consistent with what the comments say about Assignment 11. If you make
any changes to the implementation of the Chunk class at
this stage, now is also a good time to again confirm that the Marmoset
tests for Assignments 5, 6, and 10 still pass.
If you wrote explicit calls to
SimpleHeapAllocator.allocate() in Transformations.scala, change
those calls to heap.allocate(). By default,
heap is set to the SimpleHeapAllocator, but it
switches to the GarbageCollector when you compile Lacs
programs using Lacs.compileWithGarbageCollector instead of
Lacs.compile.
In MemoryManagement.scala, in the
GarbageCollector object, complete the implementations
of:
allocateProc.codeallocatecollectGarbage.codeYou can find the specification of the Lacs language here.