4: Virtual Machine

In this assignment, you will implement a stack data structure and use that to implement a stack-based virtual machine (a computer program that executes other computer programs).

A minimal stack-based architecture has three elements:

• Instruction memory which storing the program as a sequence of instructions,

• a program counter which indicates to the next instruction to execute, and

• a stack of operands.

Our VM is very simple and operates only on integer values (ints). The operand stack is simply a stack of integer values that can be manipulated by the VM. In this architecture, the stack is unbounded, which means it can grow to any size (this would not generally be the case).

Each instruction has specific semantics. In general, these instructions work by popping (integer) values from the stack, performing some computation, and pushing the results. The full set of operations required for your program is described below.

Note that this project is essentially a scaled down version of the Java Virtual Machine.

I have provided an outline of the VM implementation; it parses an input program (described below), and iterates over the instructions in that file. You will need to execute the instructions.

Getting started

Clone the project stub into the Projects subdirectory of SVN working directory.

Be sure to svn add the newly exported List directory and then commit.

Investigate the contents of that directory. There’s a lot there. You should have the following files:

• CMakeLists.txt — The build system for your homework. Read this file carefully.

• machine.hpp and machine.cpp — You need to complete this information

• stack.hpp and stack.cpp — You need to implement this

• vector.hpp and vector.cpp — Replace this with your implementation

• string.hpp and string.cpp — Replace this with your implementation

• test.hpp and test.cpp — Tools provided to support testing. Read these files. You must not modify these file, but you may find them interesting to read.

• input — A directory containing test input.

The String and Vector classes are currently aliases to std::string and std::vector. In order to receive an A, you must use your own implementations.

Stack requirements

Implement a Stack template in stack.hpp.

// Default construction; the default value shall be an empty stack.

Stack<int> s1;

// Copy construction.

Stack<int> s2 = s1;

// Copy assignment. s1 = s2;

// A member function to determine if the stack is empty. This member function

// shall not modify its object.

bool b = l1.empty()

// A member function function that returns the number of elements in

// the stack. Returns a std::size_t value. This member function shall

// not modify its object.

std::size_t n = l1.size();

// Element access.

int x1 = s.top(); // Constant int& x2 = s.top(); // Non-constant

// Push. Adds an element to the top of the stack. s.push_front(0);

// Pop. Removes an element from the top of the stack. Does not return a

// value. The stack shall not be empty.

s.pop();

Machine requirements

The virtual machine executes instructions, represented by the Instruction class in machine.hpp. This is a simple class that stores an integer opcode (determines what the operation means), and an integer operand (a value). Note that not all operations require operands. In this case, the argument must be ignored.

The VM is implemented by the Machine class. It is partially implemented. The VM must be capable of implementing the following operations:

Instruction Behavior

push n Push the constant n onto the operand stack pop Pop the top operand on the stack, discarding it

Instruction Behavior

copy Push a copy of the top operand on the stack
add Pops two operands, pushes the result of adding the first to the second
sub Pops two operands, pushes the result of subtracting the first from the second
mul Pops two operands, pushes the result of multiplying the second by the first
div Pops two operands, pushes the quotient of dividing the second by the first
rem Pops two operands, pushes the remainder of dividing the second by the first
print Pops one operand, prints the value to standard output
read Read one value from standard input, push it on the stack
halt Sets the pc past the last instruction, causing the machine to stop

For clarity, each instruction is implemented by a diﬀerent member function in the Machine class. When the instruction is executed, that function is called. Your job is to implement these functions (they are all marked TODO).

The implementation halt instruction is implemented for you.

Building and running

Build your program in the usual way using CMake and make. A set of test inputs are given in the input directory. You can test your program by passing the the name of a program as an input to the file.

./vm ../input/test.asm

Going the extra mile

All of the data structures must be your own.

Extra credit

Yes. . . there is extra credit, but it’s hard, but it’s cool. You can make this VM a legitimate general purpose computer by adding memory banks, control flow, and support for function call.

Note that you will need to implement parsing and execution support for these new operations.

Part one: local variables

Implement an extra memory store for local variables. This is essentially a vector of integers that will be used as a stack. It’s not a stack because you will need to index into this vector to retrieve and set values.

Implement these instructions:

Instruction Behavior

alloca n Declare n local variables into process memory load n Push the value of local variable at index n

store n Pops one operand, stores its value in the local variable at index n

Note that alloca 1 allocates a single variable whereas alloca n would declare an array of n integers. Also note that without function call support, local variables are essentially global variables.

Using a vector for memory bank has the benefit of encoding its own stack pointer. The vector’s size always points to the top of the stack.

Example:

alloca 1 ; create v0
push 5 ; push 5 onto the stack
store 0 ; pop 5, store it in v0
push 1 ; push 1 onto the stack
load 0 ; load 5 from v0, push it onto the stack
add ; pop 5 and 1, add, push 6
print ; pop 6, print 6

Add test programs that use these instructions.

Part two: flow control

Add instructions to manipulate the program counter. Add new instructions, which will allow you to program with if statements and loops.

Instruction Behavior

jmp n Sets the next instruction to the n - 1 instruction from pc bz n Pops one operand, if its value is zero, jump n instructions

bnz n Pops one operand, if its value is non-zero, jump n instructions

cmp Compares the first operand to the second, push -1 if less than, 0 if equal, 1 if greater than

Because fetching an instruction automatically increments pc, we subtract 1 from n in order to locate the correct instruction. That is, jmp 1 must simply execute the next instruction, and jmp 0 is an infinite loop.

TODO: Write a simple example.

NOTE: the input language is extraordinarily fragile since jump destinations are given as absolute indexes into instruction memory.

Part three: function call

A function call is essentially an unconditional jump to some other instruction, and function return is simply a jump to a return instruction (usually one past the call). However, you need to start managing stack frames. A stack frame is a bit of information used to store the return address, arguments, and local variables.

The frame pointer is pointer to a stack frame. In this system, that is simply an index into memory bank indicating the start of a frame. This must be implemented as a special register (fp), much like the program counter.

Local variables and parameter passing make this interesting. If you want to refer to local variables within called “function”, then you need to compute their index in the memory bank from some base oﬀset. This is traditionally called the frame pointer. In this implementation, it is an index into the stack.

New local variables within the function added in the same way as before. However loads and stores must be adjusted by the value of the frame pointer.

Note that parameters are indistinguishable from local variables. If a “function” takes 2 parameters, then arguments to the function call are pushed past the frame pointer for the function.

Note that you must store the return address in the frame. You may also need to push additional information onto the operand stack in order to maintain a function’s current frame prior to making a function call.

You probably don’t need to add any new instructions to implement function call, but you do need to think carefully about how this works. You may add new instructions (call and ret) to simplify call setup and teardown.

Implement support needed for function call. Document your approach in the comments the of Machine class.

4: Virtual Machine In this assignment, you will implement a stac...