2.8 Milestone 6: Adding Return

2.8.1 Milestone Summary

The goal of this assignment is to introduce the procedure return abstraction and non-tail calls, so that we can call functions that return values to non-tail contexts.

You can use the interrogator to get limited access to the reference solution: https://soft.vub.ac.be/compilers/interrogator?an=a6.

2.8.2 Practicalities

The due date for this milestone is: Wednesday 29th of May 2024 23:59 CEST.

The project is preferably in teams of 2 students or otherwise individual. Please remember that sending code or sharing code between teams is strictly not allowed.

A snapshot of your repository will be made on the day and time indicated by the due date. Make sure your code runs with the expected Racket and nasm versions by running it on the wilma server (see below) before submitting it. You may create additional files to structure your code, e.g. utility function or testing harness etc., but put code relevant for a single compilation pass in a racket file under the passes directory that is named like the pass. Make sure you keep the compiler.rkt and interface-test.rkt files provided by the skeleton, so we can easily access your implementation for every exercise.

Make sure to thoroughly unit-test each compiler pass you implement (this will be graded as well). We would like you to write your own original tests. You can get some inspiration for tests by using the online interrogator. It is good practice to write your tests and design your code before implementing it. You can include your tests in the special test submodule

You should reinstall the support package to use the one from https://github.com/soft-compilers/cpsc411-pub. You can do this via the command raco pkg update –batch –auto https://github.com/soft-compilers/cpsc411-pub.git?path=cpsc411-lib. This updated support package allows "begin" to have an empty list of effects, which is produced by the new "bury-dead" pass.

2.8.3 Grading

The project assignment needs to be done individually. Sending code or sharing code is strictly not allowed. Your project assignment will be evaluated on the basis of 3 different criteria:

• Correctness Is your compiler correct? In other words, is there a difference between (1) intepreting (running) the source code or (2) compiling the source code and interpreting the target? We ask you to provide tests for this as well.

• Implementation Are the non-obvious aspects of your implementation properly documented in comments in the code? Is the code comprehensible given your comments? Does the code uses meaningful identifiers? Do you successfully avoid excessive code duplication? Does it use the Racket standard library when possible?

• Tests Did you write your own tests? Are edge cases tested? Are all the cases tested?

2.8.4 Checklist

Completely new passes

• assign-call-undead-variables

• allocate-frames

• assign-frame-variables

Major modifications to passes

• impose-calling-conventions

• assign-registers

• implement-fvars

Minor modifications to passes

• check-values-lang

• interp-values-lang

• uniquify

• sequentialize-let

• normalize-bind

• propagate-copies

• bury-dead

• select-instructions

• uncover-locals

• undead-analysis

• conflict-analysis

• replace-locations

• expose-basic-blocks

• patch-instructions

• check-paren-x64

• interp-paren-x64

• link-paren-x64

• interp-loop

• generate-x64

(Possibly) no modifications to passes

• resolve-predicates

• trace-schedule

• flatten-program

• inline-jumps

2.8.5 Reading

The reading for this week is Procedural Abstraction: Return. As usual, this milestone description links to the documentation for each exercise in the chapter for convenience, but you are responsible for the reading the entire chapter.

2.8.6 Exercises

Exercise 1: Extend uniquify to support procedure calls in the source language.

Exercise 2: Extend sequentialize-let with non-tail calls.

Exercise 3: Extend normalize-bind with non-tail calls.

Exercise 4: Extend propagate-copies with non-tail calls.

Exercise 5: Extend bury-dead with non-tail calls.

Exercise 6: Extend impose-calling-conventions with support for non-tail calls and return.

You should use current-return-address-register and current-return-value-register rather than hard-coding the calling convention registers.

Exercise 7: Extend select-instructions with support for return points.

Exercise 8: Extend uncover-locals with support for return points.

Exercise 9: Extend undead-analysis with support for return points.

Hint: A simple way to get the call-undead locations is to use a single mutable variable that is local to the helper function that processes definitions. See box.

Hint: Because the core algorithms are similar, much of the assign-call-undead-variables, assign-frame-variables and assign-registers can share code if abstracted properly.

Exercise 10: Extend conflict-analysis with support for return points.

Exercise 11: Design and implement assign-call-undead-variables.

Be careful when computing which frame variables cannot be used; your conflict graph contains a mix of abstract locations and physical locations.

Exercise 12: Design and implement allocate-frames.

Exercise 13: Extend assign-registers to avoid directly implementing spilling.

Be careful when computing which registers cannot be used; your conflict graph contains a mix of abstract locations and physical locations.

You should use the parameter current-assignable-registers.

Exercise 14: Design and implement assign-frame-variables.

Be careful when computing which frame variables cannot be used; your conflict graph contains a mix of abstract locations and physical locations.

Exercise 15: Extend replace-locations to support return points and non-tail calls.

Exercise 16: Extend expose-basic-blocks to implement the return point abstraction.

Exercise 17: Extend implement-fvars to correctly implement frame variables relative to the current value of the current-frame-base-pointer-register.

You should use an accumulator or a mutable variable representing the current offset from the current block’s frame.

You shouldn’t assume that the current-frame-base-pointer-register is rbp, and should use the parameter instead.

Exercise 18: Modify patch-instructions to support instructions with addrs instead of fvars.

Exercise 19: Extend generate-x64 to support the the new binop.

2.8.7 Validators and interpreters

In these exercises you extend the well-formedness checkers and the interpreters for the source language. Generic definitions are given for these by default which you have to replace with your own implementations. You should however prioritize the exercises above, which do not have default implementation and are therefore more important for obtaining a fully functioning compiler pipeline.

Exercise 20: Extend interp-paren-x64, an interpreter for Paren-x64 v6.

Exercise 21: Extend check-paren-x64, a validator for Paren-x64 v6.

Exercise 22: Extend the function interp-values-lang, an interpreter for Values-lang v6.

Exercise 23: Extend check-values-lang to validate the safety of source programs. Remember that you will have to reject some safe programs.