Skip to content

Latest commit

 

History

History
127 lines (94 loc) · 5.5 KB

4.md

File metadata and controls

127 lines (94 loc) · 5.5 KB
Raw

PA4: IR

Your job in this assignment is to translate programs in an intermediate representation, GrumpyIR, to equivalent GrumpyVM assembly code. An experimental tool for you to experience this is: https://oucompilers.github.io/.

                                                                             /--------------\
                                                                             |     GC       | <-- PA3
                                                                             \--------------/
                                                                                   |||
              /--------------\                /-------------\                /--------------\
<file.gpy> => |      ir      | => <file.s> => |    assem    | => <file.o> => |     vm       | => result
              \--------------/                \-------------/                \--------------/
                   ^| PA4                          ^| PA1                         ^| PA2

TL;DR: Consider the following program fib.gpy written in GrumpyIR:

(fun fib (x i32) -> i32
     (cond (== x 0) 1
           (cond (== x 1) 1
	   	 (+ (fib (- x 1)) (fib (- x 2))))))		 
%
(fib 20)

which calculates the 20th Fibonnaci number starting from 1.

Once you've completed PA4, doing the following:

> cargo run fib.gpy

should write on stdout an assembly program like:

setframe 0
push Lmain
call
halt
Lmain:
push 20
push Lfib
setframe 2
swap
call
ret
Lfib:
push 0
var 0
binary ==
push _L3
...

Your compiler may produce different code than the above. What matters is that it produces assembly code that behaves the same as the original GrumpyIR program.

Suggested Implementation Strategy

1: Generate Assembly Code

Use the lecture notes on code generation to guide you as you generate assembly code (recursively) from GrumpyIR programs. The assembly programs you generate should be valid according to the grammar you built an assembler for in PA1. Start small, generating code first for expressions with no variables, then for expressions with variables and lets, then for complete programs with functions, etc. Test your code generator at each step, by actually running in your VM the code that you're producing.

2: Testing

Test your code by writing unit tests (as always) and then by running your compiler on the following PA4-specific test cases in tests/pass and tests/fail, which are directories containing the test cases in the template repository:

array.gpy
array2.gpy
array3.gpy
comment.gpy
div.gpy
fact.gpy
fact2.gpy
fib.gpy
fib-memo.gpy
funptr.gpy
funptr2.gpy
funptr3.gpy
heap.gpy
heap2.gpy
heap3.gpy
let1.gpy
let2.gpy
minus.gpy
multi-arg.gpy
neg.gpy
plus.gpy
seq.gpy
times.gpy

For each input .gpy file, your compiler should output to stdout an equivalent GrumpyVM assembly program. To test for equivalence, you can manually compare against the associated .s file that we've given you. Alternatively, and perhaps smarter, is to assemble and run the .s files you generate, comparing the results against the .expected files.

Additional examples

The following six examples are suitable for manual code generation. It is recommended that you process them manually and get the output right by hand before you proceed to coding.

Specifics

  1. Post a unique test case (a GrumpyIR program) to Teams (you only need one per team).

  2. Write a program that compiles GrumpyIR programs in <file.gpy>, as defined by the grammar in GrumpyIR, to equivalent GrumpyVM assembly programs printed to stdout.

  3. Equivalent means that the assembly programs you produce should halt (if the original GrumpyIR program did) with the source GrumpyIR program's result as the sole value on the stack.

  4. This is a pair assignment. You may work with up to one other person. Only one person need submit. Both partners' names must be in your README.

  5. You can test your compiler on the .gpy files we've added to the /tests directory for this assignment. One possible testing procedure is to compile each .gpy file to a .s file, then assemble and run the resulting code on your VM, making sure you get the .expected result. A pre-compiled assembler+vm binary is provided in the template (named grumpy-assembly-interp), which is used by the test script to compare the results of your compiled programs with the expected output. If you're on a linux system, you can run grumpy-assembly-interp <file.s> (this file is in /pa/tests in this repository) and verify the output is the same as in the .expected file. Otherwise, you can use your own implementation of the assembler and vm to verify the correctness of the assembly code generated by your compiler.

  6. You can assume that there is no variable shadowing in the .gpy files.

  7. You can assume that there is no function-name shadowing in the .gpy files (that is, no function is defined more than once).

  8. Be sure to write at least 3 non-trivial unit tests (for the code generator) before submitting your assignment.

  9. Submit your code by making a commit to the master branch in your repository on or by the due date. We will grade your code based on the last commit to your master branch.

Submission

You can accept the assignment here.

Submit the repo URL to Blackboard. Be sure to add a note about pair programming if you partnered with another student on this PA. Both students need to submit in that case.