13 Compiler 6: Calling Conventions

13.1 Assignment Summary

The goal of this assignment is to introduce calling conventions, so that we can call functions that return values to non-tail contexts, and make indirect function calls, which need not reference a function by name. To do this, we will expose physical locations in some intermediate languages that previously had machine-independent descriptions.

This assignment is due Friday, March 6, 2020 at 11:59pm.

You can use the reference solution here, but if you hammer it it might go down and not come back up. https://www.students.cs.ubc.ca/~cs-411/2019w2/a6-interrogator.cgi

Assignment Checklist

13.2 Language Diagram

13.3 New Source Language

This week, we shift perspective from bottom-up to top-down. The motivation for our new features comes from the source language, and we don’t need to expose any more x64 primitives to express it. Instead, we need to figure out how to generate what we want quite early in the pipeline, and this will tell us how we must modify intermediate languages later in the pipeline.

Now we can have an (apply v v ...) bound in the right-hand side of a let. We also allow function calls to arbitrary values, and support indirect function calls: calls to functions whose name (label) is not statically apparent.

Note that we continue to assume well-typed programs. For example, while (apply 1 2) is valid syntactically, it is not well typed, so its run-time behavior is undefined.

We also add subtraction as a binop. This week, we start to need subtraction a lot more and it’s tiring to encode it when x64 supports it.

13.4 Calling Conventions Introduction

Introducing a calling convention solves the two problems mentioned above.

First, the calling convention gives us a pattern to set up a call to any function, even if we do not know its signature. Instead of assigning to the exact abstract locations it expects, we fix a set of physical locations and only set those. Both the caller and the callee agree that those locations are the only thing they need to know about. Every function call will first set those locations and then call a function. Every function definition will read from those locations on entry, and move the values into its own abstract locations. This way, no function needs to know about another’s abstract locations: they become truly local.

Second, the calling convention gives a pattern for ending, or returning from, a call to a function. It dictates in which physical location the return value is stored. We have already seen a version of this in our run-time system; now we extend the idea to arbitrary functions. The calling convention also dictates where a return address is stored, so we can jump back to the middle of a previous computation, or jump directly to the next computation. This requires that during a function call, we set a return address. The calling convention also requires that the run-time system sets up a default return address.

Design digression:

Strictly speaking, we don’t need to use physical locations for our calling convention. What we need is a set of global, shared locations, whose names are unique across the entire program, and any program that we might link with. The register allocator needs to assign all uses of these shared locations to the same physical locations, or we run into exactly the same problems we saw in Compiler 4: Adding Control Flow (Corrected).

The simplest implementation of these global shared location is to just use physical locations. Physical locations are automatically globally consistent and unique, and automatically known by all programs we might link with. If we allow those physical locations to be registers, we can generate very fast function calls by keeping memory out of the picture as much as possible. Unfortunately, using them requires that we expose physical locations through every layer of abstraction up to the point where we implement the calling convention. That’s every language from Paren-asm v2 to Block-lang. This makes all our abstractions only partial abstractions, and injects undefined behavior back into our intermediate languages.

We could use the stack to implement the calling convention. This is simpler to abstract, but slower.

We could try to create global abstract locations. However, then our register allocator will only work over whole programs; we won’t be able to support separate compilation, without implementing a separate, lower-level calling convention. This would create unnecessary indirection and be less efficient.

We could try to introduce abstract call-setup and return-from-call instructions, and leave it to the register allocator to implement these in terms of physical locations. This complicates the register allocator, an already complicated pass. It also mixes concerns: assigning abstract locations physical locations, and generating the instructions to implement call and return. At some level, the register allocator will have to perform the transformation we’re already suggesting: first setup physical locations for the call, create conflicts between those physical locations and abstract locations, then assign registers. At very least, we need to do this before conflict analysis, so we might as well do it before all the analyses... that is, do it in select-instructions. This leads us right back to the original design: expose physical locations up through Block-lang.

We’ll not be completely faithful to the x64 System V ABI, but will use a similar, but simplified, calling convention. The calling convention is defined by parameters in a6-compiler-lib.rkt.

Our calling convention passes the first n arguments as registers, using the set of registers defined in the parameter current-parameter-registers. The default value is '(rdi rsi rdx rcx r8 r9), which is defined by the x64 System V ABI to be where the first 6 arguments of any function are stored. To deal with an arbitrary number of arguments, we may need more than the n registers we have available for parameters. For the rest, we use fresh frame locations.

Unfortunately, the callee will not know the exact offset into the frame that we, the caller, might be using. We therefore need to agree a priori on which frame locations are used across the call. Since there might be arbitrary frame locations currently in use (for example, because the register allocator will be putting some abstract locations on the frame), there is no particular index that it’s safe to start from.

The solution is to introduce a stack of frames. Each function assumes that, prior to being called, it was given a brand-new frame from which it can start indexing at 0. The callee knows how many arguments it expected to receive, and can start counting from 0. The caller knows how many frame locations it has used, and can increment the frame base pointer beyond its own locations to a safe starting index. After the function call returns, the caller can decrement the frame base pointer by the same amount, restoring its own frame. These increment/decrement operations can be interpreted as "pushing" and "popping" a new frame on and off the stack (of frames).

We abstract the frame base pointer as a parameter stored in current-frame-base-pointer-register. The default value is 'rbp, the same register we’ve been using for our frame variables until now.

Prior to each call, the caller will store a return address in the parameter current-return-address-register. The default value is 'r15. Before a call, we store the return address in that register. When a call returns, the callee jumps to the return address stored in that register.

When returning from a call, we store the return value in current-return-value-register. The default value is 'rax, which we’ve been using as the final result of a program. With proper function calls, we will never quite know when the program is "complete". We must assume that we will always return to some prior call.

13.4.1 Designing a Calling Convention Translation

To implement calling conventions, we want to perform the following transformations.

• When transforming a function `(lambda (,x_0 ... ,x_n-1 ,x_n ... ,x_n+k-1) ,body), we generate:

  `(begin

  (set! ,tmp-rp ,(current-return-address-register))

  (set! ,x_0 ,r_0)

  ...

  (set! ,x_n-1 ,r_n-1)

  (set! ,x_n ,fv_0)

  ...

  (set! ,x_n+k-1 ,fv_k-1)

  ,body)

  where:

  • fv_0 ... fv_k-1 are the first k frame variables, i.e., locations on this function’s frame. As displacement operands, they would be `(rbp + 0), ..., `(rbp + ,(* k 8)).

    We begin using the addition form of displacement opands in this assignment for reasons that become apparent shortly.

  • r_0 ... r_n-1 are the n physical locations from current-parameter-registers.

  • tmp-rp is a fresh temporary storing the return address for this function.

  The order of the set!s is not important for correctness, but we can influence optimizations. We want limit the live ranges of registers to help the register allocator makes better use of registers, so we should generate accesses to registers last to limit their live ranges. Loading the return address register last can also help limit its live range for simple functions.

• When transforming a call in tail position, `(apply ,v ,v_0 ... ,v_n-1 ,v_n ... ,v_n+k-1), we generate:

  `(begin

  (set! ,fv_0 ,v_n) ...

  (set! ,fv_k-1 ,v_n+k-1) ...

  (set! ,r_0 ,v_0) ...

  (set! ,r_n-1 ,v_n-1) ...

  (set! ,ra ,tmp-rp)

  (jump ,v ,fbp ,ra ,r_0 ... ,r_n-1 ,fv_0 ... ,fv_k-1))

  where:

  • ra is the physical location storing the return address, current-return-address-register.

  • fbp is the physical location storing the frame base pointer, current-frame-base-pointer-register.

  • tmp-rp is the same fresh variable generated on entry to the current function.

  • all other meta-variables are the same as in the case for transforming lambda.

  Note that form a tail call, we do not modify the stack for the caller. The caller is able to reuse the callee’s frame and return address, since there is no more computation left in this function.

  Again, the order of the set!s is not important for correctness, but can enable better use of registers and optimizations.

• When transforming a value v in tail position, we generate:

  `(begin

  (set! ,rv ,v)

  (jump ,tmp-ra ,fbp ,rv))

  where:

  • rv is the physical location used to store the return value, current-return-value-register.

  • fbp and tmp-rp are the same as in the case above for transforming a tail call.

  We cannot, in general, figure out whether the program is returning a value to a caller or halting the program. This means halt will disappear from intermediate languages. Instead, the run-time system will setup the first return address, and the final result will be returned to the run-time system using the calling conventions.

  Transforming a binary operation in tail position will be similar, but may involve several temporary abstract locations.

• When transforming a call in non-tail position, `(apply ,v ,v_0 ... ,v_n-1 ,v_n ... ,v_n+k-1), we generate the following.

  `(return-point ,rp-label

  (begin

  (set! ,nfv_0 ,v_n) ...

  (set! ,nfv_k-1 ,v_n+k-1) ...

  (set! ,r_0 ,v_0) ...

  (set! ,r_n-1 ,v_n-1) ...

  (set! ,ra ,rp-label)

  (jump ,v ,fbp ,ra ,r_0 ... ,r_n-1 ,nfv_0 ... ,nfv_k-1)))

  where:

  • rp-label is a fresh label.

    Intuitively, we need some way to introduce a label at this instruction, so when the call is complete we can return to where this apply happened. This return-point will be a new instruction in the target language that introduces a fresh label rp-label.

    Note that our non-tail calls can only appear in a let-binding as `(let ([,x (apply ,v ,v_0 ... ,v_n-1 v_n ... v_n+k-1)]) ,e), so the above return-point will be followed by an instruction setting x to the (current-return-value-register), and the rest of the instructions for e.

    `(begin

    ,translation-of-non-tail-call

    (set! ,x ,rv)

    ,translation-of-e)

  • nfv_0 ... nfv_k-1 should be the first k frame variables, i.e., locations on the callee’s frame. As displacement operands, they would be `(rbp - 0), ..., `(rbp - ,(* k 8)) to the callee.

    However, we can’t make these frame variables yet. These variables are assigned in the caller, and the callee may not have the same frame base as the caller. Consider the following expression with a non-tail call using frame variables.

    `(begin

    (set! fv0 1)

    (set! rax 42)

    (return-point L.rp.1

    (set! fv0 rax)

    (set! r15 L.rp.1)

    (jump L.label.1 rbp r15 fv0))

    (set! r9 fv0)

    (set! rax (+ rax r9)))

    For this example, suppose we’ve exhausted our (current-parameter-registers), which we simulate by making it the empty set.

    The frame location 'fv0 is live across the call; we use it after the call returns. However, we need to store 'rax in the callee’s 'fv0. If we try to use frame variables, or addrs, directly, we overwrite the original value of 'fv0. We first need to figure out how large the caller’s frame is, and then move 'rax to the index after the last frame location used by the caller.

    Prior to undead analysis, we don’t know how much we need to increment the base frame pointer to save variables live after this non-tail call. This makes figuring the exact index for these new frame variables non-trivial. We need to know the base of the callee’s frame, while we only know the base of our frame, i.e., the caller’s frame.

    But to do undead analysis, we really need both of those occurrences of 'fv0 to be unique. We’ve assumed all locations are uniquely identified by name, but the return point changes the interpretation of frame variables, so two occurrences of of the same frame variable are not necessarily the same. We want to avoid introducing such an ambiguous location.

    Instead, we’ll generate something like this:

    `(begin

    (set! fv0 1)

    (set! rax 42)

    (return-point L.rp.1

    (set! nfv.0 rax)

    (set! r15 L.rp.1)

    (jump L.label.1 rbp r15 nfv.0))

    (set! r9 fv0)

    (set! rax (+ rax r9)))

    where nfv.0 must be assigned to frame location 0 in the callee’s frame. For now, we record these new-frame variables in an info field, and we’ll figure out how to assign frames later.

    Note that this is only a problem in a non-tail call. In a tail call, we can reuse the caller’s frame as the callee’s frame, since we never return.

13.5 Designing New Intermediate Languages

The above desired implementation of calling conventions suggests a few changes to the target languages.

First, we need a return point instruction to describe returning from a function. Second, while not necessary, it will drastically simplify our pass if we had a better abstraction for working with frame locations directly, and leave some other pass to generate the particular displacement mode offsets. We will have other operations we must do on frames and frame variables, like computing the size of each frame, so a new abstraction will be useful. Third, halt is gone, and instead the run-time system must setup an initial function call. You won’t have to worry about this; the a6-compiler-lib.rkt does it already.

Design digression:

We might think we could pre-process Values-lang v6 to lift all non-tail calls into new functions and rewrite the program to have only tail calls. This would correspond to a CPS transformation and would be difficult to optimize correctly, particularly at this level of abstraction. Each non-tail call would introduce an entire function call setup to the "rest" of the body, as a continuation. Any parameters live across the non-tail call would need to be packaged and explicitly passed as arguments to the continuation. By creating a return point abstraction, later in the compiler when we have access to lower-level abstraction (basic blocks), we’ll instead be able to generate a single jump back to this return point, instead of a whole function call.

They also suggest it would be useful to have a syntactic distinction between terms in tail position, and those in non-tail position. We can expand the syntax of Values-lang v6 to reflect this syntax. We name this altered syntax Values-ctx-lang v6. It’s the same language as Values-lang v6, but expressed with apparent redundancy.

In Values-ctx-lang v6, we duplicate the n non-terminal as tail. We use tail to indicate a tail position, and n to indicate a non-tail position. The advantage of this is that, if we follow the template for this language, we are guided to write two separate processors for apply: one in tail, and one in non-tail position. By designing our data to build in a distinction, we don’t have to think hard about recovering the distinction.

(define (fvar? x)

(and (symbol? x)

(regexp-match-exact? #rx"^fv[0-9]+" (symbol->string x))))

(define (loc? loc)

(or (aloc? loc) (rloc? loc)))

(define (rloc? loc)

(or (register? loc) (fvar? loc)))

We further assume that a return-point cannot appear inside another return-point, i.e., there are no nested return-points. Our compiler can never generate this code, and there is no reason to support.

A frame variable is a symbol starting with the letters fv followed by a number. Frame variables are distinct from labels, alocs, and rlocs. The number represents the index into the frame for the current function. The a6-compiler-lib.rkt defines a few helpers for working with frame variables: fvar?, make-fvar, fvar->index, and fvar->addr.

We’re using the addition form of displacement mode operands to help us read the stack like an array.

Note that rax is allowed in this language, since halt has disappeared and our calling conventions require it.

Note that rbp is allowed in this language. We abstract which register implement the frame base pointer into a parameter, current-frame-base-pointer-register. While syntactically allowed, directly manipulating current-frame-base-pointer-register when not pushing or popping a new frame is undefined behavior, since the compiler expects to manage the stack.

To implement fvars later, we requires that current-frame-base-pointer-register is assigned only by incrementing or decrementing it by an integer literal. Other uses current-frame-base-pointer-register are invalid programs. Later passes will assume this in order to compute frame variable locations.

The info field records all the new frames created in the block, and will be used later to push new frames on to the stack, and assign new-frame variables to frame locations. The new-frame variables should be in order. Each new-frame variable must only appear in one list in the new-frames field. Recall that alocs are unique, and the new-frames field represents newly defined alocs. It would not make sense for the same aloc to appear in two frames.

All later intermediate languages will need to be adapted to expose the necessary lower-level features to make this new Block-lang v6 possible.

13.6 Implementing Calling Convention

Before we get started with implementing calling conventions, we want to uniquify names.

Exercise 1: Redesign and extend the implementation of uniquify. The source language is Values-lang v6 and the target language is Values-unique-lang v6.

Exercise 2: Redesign and extend the implementation of select-instructions. The source language is Values-unique-lang v6 and the target language is Block-lang v6.

To handle apply, you should implement the calling conventions described in Designing a Calling Convention Translation. You must have proper handling of tail calls and non-tail calls.

Note that you can reinterpret Values-unique-lang v6 to impose the same syntactic distinction as in Values-ctx-lang v6.

Exercise 3: Redesign and extend the implementation of uncover-locals. The source language is Block-lang v6 and the target language is Block-locals-lang v6.

The new-frame variables should be listed in the locals set for the enclosing block.

It will help if you interpret the locals set as the set of unassigned variables, and remove variables from the set as they are assigned.

(define (undead-set? x)

(and (list? x)

(andmap loc? x)

(= (set-count x) (length x))))

(define (undead-set-tree? ust)

(match ust

; for an instruction

[(? undead-set?) #t]

; for a return point

[(list (? undead-set?) (? undead-set-tree?))]

; for an if

[(list (? undead-set?) (? undead-set-tree?) (? undead-set-tree?)) #t]

; for a begin

[`(,(? undead-set-tree?) ...) #t]

[else #f]))

Note that to handle the return-point instruction, which includes a nested tail, the undead-set-tree data structure is updated. The undead-set-tree corresponding to a begin can have as elements either undead-sets, for set! instructions, or undead-set-trees for return-point instructions.

Exercise 4: Redesign and extend the implementation of undead-analysis. The source language is Block-locals-lang v6 and the target language is Undead-block-lang v6.

It should return undead-out sets now. To make this clear, the info field has been renamed. This is necessary to support the frame allocation for non-tail calls.

The analysis should also record undead registers and frame variables, not just abstract locations.

Note that return-point implicitly assigns the register current-return-value-register.

The pass should also record in the info field call-undead every abstract location or frame variable that is in the undead-out set of a return point. These must be allocated to the frame in the next pass, and it will save us a traversal if we stash them in the info field.

The simplest way to get the call-undead locations is to use a single mutable variable that is local to the helper function that processes bs. Since the helper for instructions will need access to it, essentially all the helpers must be locally defined in the helper for b.