Skip to content

Latest commit

 

History

History
132 lines (84 loc) · 7.89 KB

2.md

File metadata and controls

132 lines (84 loc) · 7.89 KB

PA2: GrumpyVM

Your job in this assignment is to implement a program vm that executes GrumpyVM programs represented in bytecode. That is, vm takes programs output by your assembler from PA1 and executes them to produce the result of the corresponding program.

                /-------------\                    /--------------\
<filename.s> => |    assem    | => <filename.o> => |      vm      | => program's result
                \-------------/                    \--------------/
                     ^| PA1                              ^| This assignment

There are two main problems to solve.

  1. Parsing GrumpyVM bytecode into an internal data structure (Vec<Instr>).
  2. Executing the resulting program.

As in PA1, your main reference is the GrumpyVM documentation, which describes in detail the effect of each instruction on the GrumpyVM.

At a high level, the GrumpyVM operates over:

  • A register pc containing the current program counter, a u32
  • A register fp containing the current frame pointer, a u32
  • A stack of values Val, with maximum size STACK_SIZE
  • A heap of values Val, with maximum size HEAP_SIZE
  • The program to be executed, program, a vector of instructions.

The pc points to the instruction to be executed next. The fp register points to the location in the stack from which function local variables are loaded and stored (via an offset calculation fp + i; see the GrumpyVM documentation for details). Values Val are defined as in the GrumpyVM documentation. For the purposes of this assignment, you may assume that STACK_SIZE and HEAP_SIZE are both equal 1024 values (not bytes).

A peculiarity of GrumpyVM is that, unlike most real computers, GrumpyVM's stack grows upward from smaller to larger addresses (stacks traditionally grow downward, to lower addresses).

Example 1: push

As an example of how the VM executes an instruction, consider what happens on push 3. Schematically, the state of the VM before push 3 is:

pc fp stack heap program
i ... ... v2 v1 STACK_TOP ... ... push 3 ...
... ^i'th instruction ...

After push 3, we get the following VM state

pc fp stack heap program
i+1 ... ... v2 v1 Vi32(3) STACK_TOP ... ... push 3 ...
... ^i'th instruction ...

in which the pc has been incremented by 1 (to point to the next instruction in the program) and the 32-bit signed integer 3 has been pushed onto the stack. In a bit more detail, the VM's dispatch loop performs the following steps in order:

  1. Check whether pc is greater than or equal to the program length; if so, raise an error.
  2. Fetch the instruction at address pc.
  3. Increment the pc.
  4. Execute the fetched instruction (now at address pc-1 since pc has been incremented)
  5. Loop to 1.

Importantly, note that the pc register is incremented to point to the following instruction before the current instruction (at pc - 1) is executed. This may be relevant to your implementation of control-flow instructions like call.

Example 2: call

Consider, as a second example, how GrumpyVM's state changes when a call instruction is executed.

Before the call, the state looks like:

pc fp stack heap program
i cur_fp ... varg1 varg2 ... vargN Vloc(caller_fp) Vloc(target) STACK_TOP ... ... call ...
... ^cur_fp ... ^i'th instruction ...

The call expects the arguments to be on the stack beginning at address cur_fp, followed by two locations: caller_fp, the saved frame pointer of the caller, and target, the address of the function to be called.

After the call, the state looks like:

pc fp stack heap program
target cur_fp ... varg1 varg2 ... vargN Vloc(caller_fp) Vloc(i+1) STACK_TOP ... ... call ...
... ^cur_fp ... ^i'th instruction ...
  1. target has been popped.
  2. pc has been set to target.
  3. The location i+1 (pointing to the instruction right after the call) has been pushed onto the stack; this is the address to which the function will return when it executes a ret.

Specifics

Specifically, your tasks in this assignment are to:

  1. Accept the assignment at https://classroom.github.com/a/MBhym7Uz.

  2. Post a novel test case Grumpy assembly program to MS Teams (look for the thread for PA2). Especially good is a program that exercises an obscure corner case of the GrumpyVM.

  3. Implement a program vm that reads and executes GrumpyVM bytecode files <filename.o> according to the GrumpyVM specification given in GrumpyVM documentation. You may assume that <filename>.o is your program's first argument (the zeroth being your program's path in the file system). As described below, your program should write its result to stdout.

  4. Thoroughly test your code (we expect at least 3 unit tests).

  5. Submit your project by committing to Github Classroom assignment pa2-vm on or before the due date.

Details:

  • On errors, your program should exit with a nonzero exit code.

  • When it successfully executes a .o file, your program should exit with error code 0.

  • Your vm should print the result of each program it executes to stdout.

  • When printing the result of a GrumpyVM program to stdout, use the following serialization scheme:

Value Type Encoding
The unit value Vunit
An i32 value n Vi32(n), where n is a string encoding of the integer, e.g., -345
false Vbool(false)
true Vbool(true)
The undefined value Vundef
An usize integer address i Vaddr(i), where i is a string encoding of the integer i, e.g., 1012

The other value type Vsize is used internally by the GrumpyVM but does not appear in programs and will not appear as the result of programs; you therefore do not need to serialize it (instead report an error). The Vaddr value does not appear in .s files but may be returned as the result of a Grumpy program; you therefore do need to serialize it.

Testing

The tests directory contains a number of programs that you can use to test your VM implementation. In particular, for each object file <filename>.o there is a corresponding file <filename>.expected that contains the expected output of your VM when run on <filename>.o. We will use these test cases (and perhaps others) to test your code after you submit.

Pair Programming

Unlike in previous assignments, you are permitted (though not required) to work with up to one other person on this assignment. Note that:

  1. Pair programming doesn't mean evenly dividing the work to be done independently by the two students. If you work with someone else, you should both actively be building your solution, preferably by pair programming at the same computer.

  2. Only one member of a team need submit. Make sure, in your README, to list both team members.

  3. We additionally ask that in your README you briefly describe the contributions made by each team member (one to two sentences per team member).

Performance (Extra Credit)

Time permitting, we may test the performance of your VM implementation relative to our own implementation(s) and against those of other students. We plan to give a small amount of extra credit to those students or pairs (perhaps the top 3) who implement the fastest VMs. Note, however, that you cannot win the performance contest if your VM has correctness bugs (faithfully implementing all the instructions in GrumpyVM documentation is far more important than optimizing for speed).