1.7 Procedural Abstraction: Call

1.7.1 Preface: What’s wrong with our language?

In the last chapter, we designed the language Values-lang v4 with support for structured control-flow operations. This enables our programs to make run-time decisions that influence what code is executed. However, the language is missing a key feature necessary for practical programming: the ability to reuse code.

Normally, procedures are thought about as composed of two features: call and return. However, these are two separate abstractions. In this chapter, we introduce only the call abstraction. Procedures can be called, but never return. We limit where such a call can happen so we do not have to answer inconvenient questions.

1.7.2 Designing a source language with call

Below, we define Values-lang v5 by extending Values-lang-v4 with a tail calls—a procedure call in tail position.

A program now begins with a set of declared procedures, named blocks of code that are parameterized over some data indicated by the list of names (x ...), called the parameters. Each of these procedures can be used by the call abstraction (call name value ...), which takes the name of a procedure and a list of values, called the arguments, with which to instantiate the parameters. At run-time, the call unconditionally transfers control to the code declared in the definition of the procedure name.

Notice this call is restricted to tail context. If we allowed a call in value context, for example, then we could have a call on the right-hand side of a let. This would transfer control with a tail still remaining to be executed. Defining what this means in a sensible way is difficult, and requires introducing some abstraction to transfer control back from a procedure to the middle of some existing computation. Recall that a value in tail context is implicitly the final answer, and is compiled to a halt instruction. In terms of the lower-level languages, we can understand a tail call as jumping until the program reaches a halt instruction.

We already have the machinery to compile procedure definitions and calls. Procedure definitions are transformed into basic blocks, and calls into, essentially, jmp instructions.

The only question is how to pass arguments. The call instruction needs to know in which locations to store the arguments, and the called procedure needs to know from which locations to read its parameters. The problem is deciding how to ensure the locations end up the same. To solve this, we introduce a calling convention.

1.7.3 Calling Conventions Introduction

The calling convention gives us a pattern to set up a call to any procedure. We fix a set of physical locations. Both the caller and the callee agree that those locations are the only thing they need to know about. Every call will first set those locations and pass control to the procedure. Every procedure will read from those locations on entry, and move the arguments into its own abstract locations. This way, no procedure needs to know about another’s abstract locations. This allows our register allocator to continue functioning as is, with only a small change in scope from the entire program to procedure definition.

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.

A simple implementation of these global shared location is to 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 procedure 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. This makes all our abstractions only partial abstractions, and injects undefined behaviour back into our intermediate languages.

We could also use the stack to implement the calling convention. This is simpler, as we can keep registers abstract and need to expose memory high in the compiler pipeline anyway, but slower since every procedure call must now access memory.

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 to 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. This leads us right back to the original design: expose physical locations through the register allocator, high in the compiler pipeline.

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 procedure 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 variables.

Since tail calls never return, we do not need to worry about what is on the frame before a call. We can simply overwrite all existing frame variables. This means recursive tail calls have the same performance characteristic as, and in fact compile to, loops: they use a constant amount of stack space, compile directly to jumps, and only need registers as long as they use fewer than 6 arguments.

1.7.3.1 Designing the Calling Convention Translation

To design our calling convention translation, we start by looking at how we want to translate terms into abstractions we already have. We then redesign our intermediate languages to support our translation.

Design digression:

We must be careful to design a translation that eliminates some abstraction layer, or we risk developing a translation that simply kicks the real problem down to the next language. A good heuristic here is to avoid designing a translation that introduces any new abstractions. If we need new abstractions, we should look at the problem bottom up—designing the proposed abstraction as an abstraction of some features expressible in the target language.

Intuitively, we know how to compile calls. We want to instantiate the parameters of the procedure, moving arguments to the shared locations, then jump to the label of the procedure. Concretely, we want to perform the following transformations.

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

  `(begin

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

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

  The order of the set!s is not important for correctness, but can influence optimizations. We want limit the live ranges of registers to help the register allocator make better use of registers, so we should generate accesses to registers first to limit their live ranges.

• When transforming a tail call, `(call ,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)

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

  where:

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

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

  Again, the order of the set!s is not important for correctness, but can enable better use of registers and optimizations. This time, we move values into the registers last, to keep their lives as short as possible.

  Here, we decorate the jump instruction with its undead-out set. Going top-down, it is not obvious why we would do this; let’s think ahead:

  We know we want to compile a call to a series of assignments and a jump. But, since we’re going top-down, we need to ask: will the lower-level language be able to implement jump? We must look bottom-up at how we would expose jump from the lower level languages.

  We will need to expose jump from Block-pred-lang v5, all the way up to whatever this transformation targets. This means at least exposing jump through the register allocator. In undead-analysis, we will need to decide what set of locations is undead after a jump. In general (blame Rice’s Theorem), we will not know the target of a jump, so we cannot go analyze the target to figure out what is live. Therefore, we need to either approximate (anything could be live), or we need someone to tell us the answer. Thankfully, using our calling convention, when generating a jump, we know exactly which locations will be live—the locations used by the caller, and no others. So we provide a hint to the undead analysis, annotating each jump with its undead-out set.

Now that we know the translation we would like to perform, we need to figure out where to fit the new translation in our compiler pipeline. To do this, we need to ask a few questions.

First: which target languages support the features needed in the target of our translation? If we look at the pipeline from the last chapter, Appendix: Overview, we know the translation must come at least after sequentialize-let, since the target language will need to use imperative features introduced in that pass. Introducing calling conventions also generates begin statement in tail position, and generates set! expressions with a combination of values and locations for operands. This last feature tells us we should place the new pass before select-instructions, since we want the unrestricted set! feature select-instructions provides.

Second: which translations might be disrupted by introducing new features in their source language? If we add the new translation before normalize-bind, then we won’t need to extend normalize-bind to support the call construct, but we will need to make sure normalize-bind handles the jump construct. This might be a problem, if jump appears in effect context, but note that since call appears in tail context, so must the jump that call compiles to. This suggests we could place the new pass either right before or right after normalize-bind.

Third, we try to future proof our design decisions: will the answer to any of the above questions change if we add new features in the future? This is hard to predict; the future is vast so the search space is large. We can limit our search by focusing on limitations in features we’re now adding. We just added call in tail context. Are we likely to lift this restriction and allow calls in other contexts later? Yes, that seems likely; most languages allow calls in non-tail context. If we allowed calls in effect context, e.g., then our translation would need to generate a begin in effect context, and not just tail context. This tells us we want to support nested begin in the target language of our new pass. Since we changed the target of normalize-bind to allow nested begin, we can still place our new pass before or after normalize-bind. We’re also likely to add call in value context. Notice that normalize-bind is sensitive to forms in value position, in particular, on the right-hand side of a set!. This suggests we should avoid transforming call until after performing normalize-bind.

We conclude the new pass should go just after normalize-bind. We start by extending the first few passes down to normalize-bind.

1.7.4 Extending front-end with support for call

We start by formally defining Values-lang v5, the new source language. We typeset the difference compared to Values-lang v4.

Modules now define a set of procedures at the top-level before the initial tail. The program begins executing the tail following the set of definitions.

We have not introduced a method for dynamically checking that a procedure is used correctly yet. To avoid exposing undefined behaviour, we make an additional restriction to calls. Calls must call a statically known procedure with exactly the right number of arguments. Otherwise, our desired transformation will leave some physical locations uninitialized, resulting in undefined behaviour.

We now have two data types exposed in the source language: integers, and procedures. This introduces more opportunities for undefined behaviour. If we try to compare a procedure to an integer, we will generate code with undefined behaviour. We therefore require that source program does not use labels in this way.

To validate these assumptions, we can implement check-values-lang.

check-values-lang must necessarily rule out many well-defined programs, since without modifying the source language, we cannot tell the types of all procedure parameters. We design a conservative approximation that is sound, i.e., it never accepts a program with undefined behaviour, but incomplete, i.e., some well-defined programs are rejected. This is a normal trade off in compilers, and yet another consequence of Rice’s Theorem.

Finally, we have one restriction imposed by the run-time system: the final result of the program must be an int64.

procedure (check-values-lang p) → values-lang-v5?

p : any/c

Validates that the Values-lang v5 is syntactically well-formed, well bound and well typed: all procedure calls pass the correct number of arguments, and all binop and relop are never used with labels. You may want to separate this into two problems: first checking syntax, then type checking.

Next we need to resolve lexical identifiers. This is slightly complicated by introducing procedures. We want to compile procedures to labeled blocks and jumps, so we need to compile their names to labels rather than abstract locations.

First, we design Values-unique-lang v5. We typeset the differences compared to Values-lang v5.

As usual, we change local lexical identifiers to abstract locations. However, we also change top-level lexical identifiers into labels. labels are trivs, although we assume they are only used according to the typing rules imposed by check-values-lang.

procedure (uniquify p) → values-unique-lang-v5?

p : values-lang-v5?

Compiles Values-lang v5 to Values-unique-lang v5 by resolving top-level lexical identifiers into unique labels, and all other lexical identifiers into unique abstract locations.

Next we design Imp-mf-lang v5, an imperative language in monadic form with procedures. We typeset the differences compared to Values-unique-lang v5.

There are no interesting changes. We simply propagate the new procedure forms form down one more level of abstraction.

procedure (sequentialize-let p) → imp-mf-lang-v5?

p : values-unique-lang-v5?

Compiles Values-unique-lang v5 to Imp-mf-lang v5 by picking a particular order to implement let expressions using set!.

Finally, we need to normalize assignment statements so the right-hand side is a "trivial" value. Below, we design Proc-imp-cmf-lang-v5 the target language of normalize-bind.