3.5 Iteration 4: Adding Tail Calls
3.5.1 Milestone Summary
The goals of this milestone are to (1) introduce the procedure call abstraction (2) introduce calling conventions, an abstraction for compiling procedure calls In the process, we’ll learn a different approach to compiler design. Rather than building up layers of abstractions bottom-up, we consider how to compile a designed feature top-down. We’ll introduce an abstraction and consider how to design translations to lower the new an abstraction to existing features.
You can use the interrogator to get limited access to the reference solution: https://soft.vub.ac.be/compilers/interrogator?an=a5.
3.5.1.1 Learning Objectives
3.5.1.2 Checklist
Provided passes
implement-fvars
assign-homes-opt
Completely new passes
Major modifications
Minor modifications
resolve-predicates
patch-instructions
implement-fvars
generate-x64
assign-fvars
assign-homes
3.5.2 Reading
The reading for this week is Procedural Abstraction: Call. 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.5.3 Assignment
flatten-program
resolve-predicates
generate-x64
patch-instructions
Here are some useful notes:
In the uniquify pass, let-bound variables should be replaced by abstract locations as before. However, define-bound variables are procedure names, and should be replaced by a fresh label that represents the enty point for the procedure. You should use fresh-label, to produce labels. It optionally takes a string or symbol as argument which will be part of the generated label.
In the implementation of impose-calling-conventions you should use current-parameter-registers and you may use current-return-value-register rather than hard-coding the calling convention registers. In this way you can test passing parameters in frame variables using smaller examples by simply reducing the number of parameter registers. Try to reduce register pressure by ordering movs when compiling the calling convention.
3.5.4 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 1: Extend the function interp-values-lang, an interpreter for Values-lang v5.
Exercise 2: Design and implement check-values-lang to validate the safety of source programs. Remember that you will have to reject some safe programs.
3.5.5 Optional Exercises
Exercise 3 (optional): Extend assign-fvars to take conflicts from the calling convention into account and thereby preserve the unoptimized assign-homes pass. If you previously implemented the suggested interface for the graph coloring, then you can simply call your coloring function with a different set of assignable locations, i.e. frame variables only. Note: This functionality will become necessary when you implement Procedural Abstraction: Return.