CS 241 — Winter 2024 — Assignment 7

Assignment 7: Due Monday, Apr 1st, 5:00 pm / Out of 18 marks

In Assignment 7 and 8, you will write a code generator for WLP4, and finally complete the process of translating WLP4 source code to MIPS assembly!

In Assignment 7, you implement the basic features of WLP4: the wain procedure, integer variables and constants, declarations, assignment, arithmetic, control flow, and printing.

In Assignment 8, you build on these features and add support for pointers, other procedures, and dynamic memory allocation.

Click here to skip the preamble and go to the problem statements.

Filenames

In both Assignment 7 and Assignment 8, you are gradually building up one large program across multiple problems. You can submit the same program to problems P1 to P5 (on both assignments!) if you want.

For all problems, you must submit one of the following two files:

You can submit additional files if you wish to divide your program into multiple files, but a file with one of the above names must be present in your submission.

Input, Output, and Testing

The input format on this assignment is the WLP4 Typed Intermediate (.wlp4ti) format that you produced as the output for Assignment 6. This is a preorder traversal of a WLP4 parse tree that includes type information for expression nodes. You will not need the type information in Assignment 7, but it will be needed in Assignment 8.

Given some WLP4 source code, you can produce the .wlp4ti input file using the web tool in one step, or using the following command:

wlp4scan < input.wlp4 | wlp4parse | wlp4type > input.wlp4ti

The output format is MIPS assembly code. The goal of this assignment is to produce MIPS assembly code that implements the behaviour specified by the WLP4 program!

After running the .wlp4ti file through your code generator, you can test your program by running it through cs241.binasm* and then using either mips.twoints or mips.array, depending on whether the WLP4 program expects two integers or an array as input.

Here are the commands for running it on the Student Linux server with mips.twoints, assuming your code generator executable is named wlp4gen.

./wlp4gen < input.wlp4ti > output.asm
cs241.binasm < output.asm > output.mips
mips.twoints output.mips

* In Problem 5 of each assignment, you will need to use a different assembler. More details are given in the problem and the reason behind it will be explored in Problems 6 and 7.

In these assignments, there is no "correct executable" to compare your output to, because that concept does not make sense for a code generator. Instead, test your code generator by comparing the behaviour of the compiled program to the expected behaviour. If you are unsure what the expected behaviour is, you can use wlp4c to compile the program, and compare "your compiled program" with "wlp4c's compiled program".

wlp4c < input.wlp4 > expected.mips

Note that wlp4c takes WLP4 source code as input, not a .wlp4ti file like your program, and produces MIPS machine code as output, not MIPS assembly code like your program.

You can then run both MIPS programs and check if the return value in $3 matches, as well as standard output if the program includes printing.

Dependencies

Ultimately, in Assignments 7 and 8 you are writing one large program, a code generator. You cannot get full marks on Assignment 8 without completing Assignment 7. But we have tried to set up the problems so that if you partially complete Assignment 7, then you will be able to partially complete Assignment 8.

In general, this is how the dependencies between problems work:

For example, suppose you only complete Assignment 7 up to Problem 3. You should be able to complete Assignment 8 up to Problem 3 as well.

The following diagram shows the dependencies graphically.

It may also be possible to earn part marks on some problems even if you haven't completed one of the problems it "depends" on. More details about opportunities for part marks will be added to the assignment page once Marmoset is set up.

Problems

To reflect the dependency structure described above, we have grouped the problems for each assignment together. That is, we only list five "problems" below, but each problem has an "Assignment 7 version" and an "Assignment 8 version". The "Assignment 8 version" builds on the "Assignment 7 version" by asking you to implement additional WLP4 features related to pointers and procedures.

There is also an optional "Bonus Problem" at the very end, which is to be completed after finishing both Assignment 7 and Assignment 8.

Efficiency Warning

There are no particular efficiency requirements for these assignments, and most of the test programs are small. However, students have a tendency to accidentally write tree-building code that uses an exponential amount of memory in the tree size (particularly if they're trying to avoid using pointers, and don't understand C++ move/copy semantics). Exponential time or memory usage is not acceptable even on an assignment with relaxed efficiency requirements.

If you make this mistake, then you will likely exceed Marmoset's time or memory limit on tests with larger programs. The largest programs are reserved for the secret tests, so this could lead you to fail secret tests despite passing all the other tests.

A7P1 on Marmoset includes a "Warning" test which is not for marks and is just intended to warn you about potential efficiency issues. Passing this test does not guarantee your compiler is efficient, though.

Problem 1: Simple Programs

Assignment 7 [2 marks, 1 release+secret]

Write a code generator for WLP4 programs whose parse tree contains only the following rules:

start → BOF procedures EOF
procedures → main
main → INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE 
type → INT
dcl → type ID
dcls →
statements →
expr → term 
term → factor 
factor → NUM  
factor → ID
factor → LPAREN expr RPAREN
These programs are very restricted: All these programs can do is return a value, which is either a numeric constant, or one of the parameters of wain.

Example Program

int wain(int a, int b) { return a; }

When run with mips.twoints, the return value in $3 should be the first parameter of wain (the value given for $1).

Problem 2: Declarations, Assignment, and Unary Operations

Assignment 7 [3 marks, 2 release+secret]

Extend your code generator to support programs whose parse tree contains the following additional rules:

dcls → dcls dcl BECOMES NUM SEMI
statements → statements statement
statement → lvalue BECOMES expr SEMI
lvalue → ID
lvalue → LPAREN lvalue RPAREN

In other words, now you have to support declarations in the body of wain, and assignment statements.

Example Program

int wain(int a, int b) {
  int c = 241;
  b = c;
  a = b;
  return a;
}

When run with mips.twoints, the return value in $3 should be 241.

A7P2: Part Marks

The public test cases only contain declarations (no assignment statements), so you can earn 1 mark on this problem without implementing assignment statements.

Problem 3: Binary Operations

Assignment 7 [2 marks, 1 release+secret]

Extend your code generator to support programs whose parse tree contains the following additional rules:

expr → expr PLUS term
expr → expr MINUS term
term → term STAR factor
term → term SLASH factor
term → term PCT factor

In other words, you now have to support expressions with addition, subtraction, multiplication, division, and modulo.

Example Program

int wain(int a, int b) {
  return (240 + 1) - (2410 / 10);
}

When run with mips.twoints, the return value in $3 should be 0.

A7P3: Dependencies

The test cases in this problem do not contain declarations or assignment statements (the features implemented in A7P2), so you can earn full marks on this problem even if you have not solved A7P2.

Problem 4: Control Structures

Assignment 7 [4 marks, 2 release+secret, 1 secret]

Extend your code generator to support programs whose parse tree contains the following additional rules:

statement → IF LPAREN test RPAREN LBRACE statements RBRACE ELSE LBRACE statements RBRACE
statement → WHILE LPAREN test RPAREN LBRACE statements RBRACE
test → expr EQ expr
test → expr NE expr
test → expr LT expr
test → expr LE expr
test → expr GE expr
test → expr GT expr

In other words, you now have to support if-else statements and while loops, as well as Boolean comparisons.

Example Program

int wain(int a, int b) {
  if(a < b) {
    while(a < b) {
      a = a + 1;
    }
  } else { 
    a = 241;
  }
  return a;
}

When run with mips.twoints, the return value in $3 depends on the value of the first parameter (given in $1) and the value of the second parameter (given in $2). If $1 < $2, the return value should match the value of $2. Otherwise, the return value should be 241.

A7P4: Dependencies and Part Marks

The public test cases do not contain if-else statements, so you can earn 1 mark on this problem if you just implement while loops.

The public test cases do contain assignment statements and arithmetic, so you need to have solved A7P2 and A7P3.

Problem 5: External Libraries

Assignment 7 [3 marks, 1 release+secret, 1 secret]

Extend your code generator to support programs whose parse tree contains the following additional rule:

statement → PRINTLN LPAREN expr RPAREN SEMI

In other words, you now need to support the println statement.

Since this is the final problem on Assignment 7, you will be tested with programs that combine all the features you implemented on Assignment 7.

Example Program

int wain(int a, int b) {
  println(a+b);
  return 0;
}

When run with mips.twoints, the return value in $3 will be 0. However, the program should produce the value of $1 + $2 (the sum of the two parameters) on standard output.

Importing, Using, and Linking the Print Library

Supporting this statement introduces some complications, because unless you want to use your own print procedure from Assignment 2, you will need to import the print procedure from an external library, and link it with your generated code when testing.

The print library is available here: print.merl

To import the print procedure, include the following line at the start of your generated code:

.import print

You can then call "print" in the same way you would call any other MIPS procedure, as if there was a label called "print" in your code. The procedure expects the value to print in $1, and preserves all registers.

Unfortunately, our trusty assembler cs241.binasm does not know what ".import" means and will produce an error when it sees the ".import print" line. To test our code, we will need to use a different assembler that supports imports.

This assembler is called cs241.linkasm. It produces MERL object files instead of raw MIPS machine code.

Once you run the output of your code generator through cs241.linkasm, you need to use cs241.linker to link your code with the print library. That will produce a combined MERL file you can run with mips.twoints.

The sequence of commands to compile and run a WLP4 program on the Student Linux server (with mips.twoints) now looks like this:

wlp4scan < input.wlp4 | wlp4parse | wlp4type > input.wlp4ti
./wlp4gen < input.wlp4ti > output.asm
cs241.linkasm < output.asm > output.merl
cs241.linker output.merl print.merl > linked.merl
mips.twoints linked.merl

A7P5: Dependencies and Part Marks

For both the public and secret tests, you must have implemented the features from all the previous Assignment 7 problems to pass. There are no part marks for just implementing printing.

Problems 6 and 7 Overview

In problems 6 and 7, we return to the glory days of writing MIPS assembly programs. You are to write a loader that can load a MERL file at an arbitrary location in memory, performing the necessary relocation to ensure the file will run correctly.

Starter Code

We have provided some starter code in the form of two MIPS procedures:

Both procedures preserve all registers not used for return values. So readWord preserves all registers except $3, and printHex preserves all registers.

The starter code is provided as both assembly source code and a MERL library. It is up to you whether you simply copy the source code into your submissions, or use the ".import" directive to import the procedures from the MERL file. Marmoset will accept both options.

Problem 6: Print Once (filename: p6.asm) [2 marks, 1 release+secret]

Write a MIPS program that reads a MERL file from standard input. Your program should print the contents of the MIPS code segment of the MERL file, then return.

The words in the MIPS code segment should be printed using the provided printHex procedure.

Example

Here is a simple MIPS program:

lis $3
.word 241
jr $31

You can assemble it into a MERL file with cs241.linkasm:

$ cs241.linkasm < input.asm > input.merl

You can assemble your own MIPS program with either cs241.binasm (if you are not using .import directives and just copied the starter code into your program) or with cs241.linkasm and cs241.linker (if you are using .import).

On the Student Linux server:

# If not using .import
$ cs241.binasm < p6.asm > p6.mips
# If using .import
$ cs241.linkasm < p6.asm > p6.merl
$ cs241.linker p6.merl starter.merl > linked.merl

If you pass the input.merl file to your program, it should print the the hexadecimal encoding of the MIPS program to standard output:

$ mips.stdin [your program] < input.merl
Running MIPS program.
00001814
000000F1
03E00008
MIPS program completed normally.
...

It is not practical to run a loader using the web tools; this you must run on the Student Linux server.

Problem 7: Print Twice (filename: load.asm) [2 marks, 1 release+secret]

Write a MIPS program that reads input (from standard input) consisting of a 32-bit memory address α followed by a MERL file. Your program should print the contents of the MIPS code segment of the MERL file twice, then return.

The words in the MIPS code segment should be printed using the provided printHex procedure.

To print the MIPS code segment twice, you should write a program with two loops.

  1. The first loop should read the MIPS code segment of the MERL file from standard input and copy it into memory at address α. As you read each word, print it out as well.
  2. The second loop should read the copy of the MIPS code segment that is stored in memory at α and print each word.

Implementation Notes

The MERL file will have an empty footer (no REL, ESR, or ESD entries). You do not need to perform relocation.

The address α will always be between 0x10000 and 0x100000. This means as long as your loader code has 16,384 instructions or less, you will not overwrite your own code when loading the provided MIPS code.

Example

To create test inputs for this problem (and future problems), you need to prepend the input MERL file with the binary encoding of the load address α. For example, if the load address was 0x10000, you could do this as follows:

cs241.binasm <<< '.word 0x10000' > address.bin
cs241.linkasm < input.asm > input.merl
cat address.bin input.merl > input.in

Assuming input.merl is created using the same example program as in Problem 1, the output would be:

$ mips.stdin [your program] < input.in
Running MIPS program.
00001814
000000F1
03E00008
00001814
000000F1
03E00008
MIPS program completed normally.
...