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.
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.
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.
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.
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.
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.
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 RPARENThese programs are very restricted:
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).
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.
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.
The public test cases only contain declarations (no assignment statements), so you can earn 1 mark on this problem without implementing assignment statements.
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.
int wain(int a, int b) {
return (240 + 1) - (2410 / 10);
}
When run with mips.twoints, the return value in $3
should be 0.
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.
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.
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.
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.
Extend your code generator to support programs whose parse tree contains the following additional rule:
statement → PUTCHAR LPAREN expr RPAREN SEMI statement → PRINTLN LPAREN expr RPAREN SEMI factor → GETCHAR LPAREN RPAREN
In other words, you now need to support I/O, through the putchar and println statements, and the getchar expression.
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.
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.
int wain(int a, int b) {
putchar(getchar());
return 0;
}
When run with mips.stdin, the return
value in $3 will be 0. However, the program should echo to standard output
the first character read from standard input.
Supporting the println statement introduces some complications, because unless you want to use your own print procedure from Assignment 3, 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
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.
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.
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.
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.
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.
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.
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.
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. ...