3.7 Iteration 6: Call and Return

3.7.1 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.

3.7.2 Checklist

Provided passes

• check-values-lang

• interp-values-lang

• uniquify

• sequentialize-let

• normalize-bind

• select-instructions

• uncover-locals

• assign-registers

• assign-frame-variables

• replace-locations

• implement-fvars

• resolve-predicates

• flatten-program

• patch-instructions

• generate-x64

• link-paren-x64

• interp-paren-x64

Completely new passes

• assign-call-undead-variables

• allocate-frames

Major modifications to passes

• impose-calling-conventions

Minor modifications to passes

• propagate-copies

• bury-dead

• undead-analysis

• conflict-analysis

• expose-basic-blocks

(Possibly) no modifications to passes

• trace-schedule

• inline-jumps

3.7.3 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.

3.7.4 Assignment

Here are some useful notes:

• In the impose-calling-conventions pass you need to accumulate new frames. Since that nested deep inside the traversals, it is best to use imperative features to do so. Similarly, the undead-analysis pass now needs to accumulate call-undead variables. See box.

• The assign-call-undead-variables pass pre-allocates variables that need to be preserved during calls. However, this also needs to take conflicts into account. You can implement this pass simply by reusing the graph coloring algorithm, if you have previously implemented graph coloring using the suggested interface. You can also find a reference implementation in the graph-coloring.rkt file of the skeleton code.

• The template code for undead-analysis and expose-basic-blocks is an almost feature complete implementation of these passes for the previous iteration, which have also been published on Canvas. If you prefer, you can also continue to use your own solution. The modifications to these passes are comparably small.

• The implement-fvars pass moved up to before expose-basic-blocks for this iteration. This move will likely break several of your tests for expose-basic-blocks. If you are confident in your implementation, you can skip adapting these tests and concentrate on writing tests only for the new features. The remainder of the compilation pipeline is provided and thus does not need adapting.

3.7.5 Validators and interpreters

The validators and interpreters for the source and target language are provided. Hence you do not need to extend them.