1.6 Structured Control Flow

1.6.1 Preface: What’s wrong with our language?

For our last abstraction, we designed the language Values-lang v3. This language is an improvement over x64, but has a significant limitation: we can only express simple, straight-line arithmetic computations. We’ll never be able to write any interesting programs!

In this chapter, we will expose a machine feature, control flow instructions in the form of labels and jmp instructions, and systematically abstract these into a structured control-flow primitive: if expressions. Control flow is complex, and adding it requires changes to nearly every pass and every intermediate language.

The overview of this version of the compiler is given in Figure 4.

1.6.2 Designing a source language with structured control flow

As usual, we’ll start with our goal and then design the compiler bottom-up. We want to extend Values-lang v3 with a structured control-flow feature: a form of if expression.

Our goal is Values-lang v4, duplicated below.

Note that an if expression, (if pred e e), is limited: it cannot branch on an arbitrary expression. It is restricted so that a comparison between two values must appear in the predicate position. This is a necessary artifact we’ll inherit from x64. Even by the end of this chapter, we will not yet have enough support from the low-level language to add values that represent the result of a comparison, i.e., we won’t have booleans.

Design digression:

This is a design choice. With the abstraction we have so far, we could add pseudo-boolean expressions by giving an arbitrary interpretation to any values in the predicate position. For example, we could interpret 0 as true and 1 as false, or vice versa. Unfortunately, this would expose our source language to undefined behaviour—what happens when an if expression branches on any other value? We could remedy this slightly by making any non-zero integer true, for example. However, it also means we become unable to distinguish booleans from integers, leading to type confusion when reading and writing data. If a programmer sees the number -5 printed or in a program, is it a boolean or a number?

There are many ways to solve the problem, but to keeping with our design principles of designing clear abstraction boundaries, we will later add proper booleans as a separate primitive data type. That is a task separate from adding control flow, so we deal with it later, and instead implement a limited form of structured control-flow first that booleans can compile to later.

1.6.3 Exposing Control-Flow Primitives

When we want to add a new feature to the source language, we must always ask if there’s some existing abstraction in the target language that we can use. So far, Paren-x64 v2 exposes only intructions to move data between locations and perform simple arithmetic computation on locations. This is insufficiently expressive, so we must reach even lower and expose new primitives from the machine.

We’ll begin the next version of our compiler by designing a new Paren-x64 v4 to expose the additional features of x64 necessary to implement control flow abstractions. This extends the previous Paren-x64 v2 with comparison operations, labels, and conditional and unconditional jump operations.

Labels are too complex to define by grammar; instead, they’re defined by the label? predicate in cpsc411/compiler-lib.

The library function sanitize-label turns a label? into a string that NASM will accept, as long as it is not too long.

In Paren-x64 v4, we model labels with the (with-label label s) instruction, which defines a label label at the instruction s in the instruction sequence. This corresponds to the x64 string label:\n s. Note that they can be nested, allowing the same behaviour as chaining labels in x64. For convenience, we assume all labels are symbols of the form L.<name>.<number>, and are globally unique.

Note that (with-label label s) does not behave like a define in Racket or in Values-lang v3. The instruction s gets executed after the previous instruction in the sequence, even if the previous instruction was not a jump. with-label additionally names the instruction so that we can jump to it later, the same as a label in x64.

The new comparison instruction (compare reg opand) corresponds to the x64 instruction cmp reg, opand. This instruction compares reg to opand and sets some flags in the machine describing their relation, such as whether reg is less than opand, or whether they are equal. The flags are used by the next conditional jump instruction. If the opand is an integer literal, it must restricted to 32-bits.

The conditional jump instructions in x64, in the same order as the definition of relop, are: jl label, jle label, je label, jge label, jg label, and jne label and each corresponds to "jump to trg if the comparison flag is set to ___". For example, the instruction je label jumps to label if the comparison flag "equal" is set.

In Paren-x64 v4, we abstract the various conditional jump instructions into a single instruction with multiple flags. The instruction je l corresponds to (jump-if = l). jl l jumps to l if comparison flag "less than" is set, and corresponds to (jump-if < l). The rest of the instructions follow this pattern.

We make an additional simplifying restriction in Paren-x64 v4 compared to x64. We assume that a compare instruction is always followed immediately by a jump-if, and similarly, that any jump-if is immediately preceeded by a compare. This is necessay since other instructions in x64, such as binary operations, can affect comparison flags. However, we do not want to try to reason about how the flags are affected by arbitrary comparison, and our compiler will always generate a compare-and-then-conditional-jump sequence of instructions.

To implement Paren-x64 v4, we define the procedure generate-x64, which simply converts each instruction to its x64 string form.

procedure (generate-x64 p) → (and/c string? x64-instructions?)

p : paren-x64-v4?

Compile the Paren-x64 v4 program into a valid sequence of x64 instructions, represented as a string.

1.6.3.1 The semantics of labels and jumps as linking

Labels and jumps are a small change to the language syntactically, but have a large effect on the semantics. We can see this by writing an interpreter for the language with labels and jumps and comparing it to an interpreter for a language without them.

We can no longer write the Paren-x64 v4 interpreter in one simple loop over the instructions. Instead, we need some way to resolve labels. That way, when running the interpreter, we must be able to jump to any expression at any time—a possibility the language now allows. This process of resolving labels is called linking.

We only cover linking local labels in this chapter. More generally, linking requires resolving references to external labels, i.e.,, linking imported libraries, and in the context of many operating systems, preparing some additional metadata so the operating system knows where to begin executing. The more general instance is conceptually similar to what we present here—the key concept is transforming the abstraction of labels to code and data into some encoding used by the underlying implementation.

We can view the process of linking as yet another compiler, and thus a language design problem. We design a simple linker for Paren-x64 v4 to give you a rough idea of how the operating system’s linker works. We use a low-level linking implementation that is similar to the operating system’s linker: we first resolve all labels to their address in memory (in our case, their index in the instruction sequence) and then implement jumps by simply setting a program counter to the instruction’s address.

To do this, we design a new language Paren-x64-rt v4 (paren-x64-rt-v4), which represents the run-time language used by the interpreter after linking.

We remove the instruction (with-label label s) and turn all label values into pc-addr, a representation of an address recognized by the interpreter. This encodes the idea that the linker, the compiler from Paren-x64 v4 to Paren-x64-rt v4, resolves labels into addresses. In our case, since programs are represented as lists of instructions, a pc-addr is a natural number representing the position of the instruction in the list.

To implement Paren-x64-rt v4 and thus perform linking, we define the procedure link-paren-x64.

procedure (link-paren-x64 p) → paren-x64-rt-v4?

p : paren-x64-v4?

Compiles Paren-x64 v4 to Paren-x64-rt v4 by resolving all labels to their position in the instruction sequence.

Now we can give a semantics to Paren-x64-rt v4, and thus give a semantics to Paren-x64 v4 and understand the meaning of labels and jumps. We define an interpreter interp-paren-x64 for Paren-x64 v4 by first linking using link-paren-x64, and then running an interpreter for Paren-x64-rt v4. The main loop of the Paren-x64-rt v4 interpreter uses a program counter to keep track of its position in an instruction sequence. To interpret a jump, we simply change the program counter to the number indicated in the jump.

procedure (interp-paren-x64 p) → int64?

p : paren-x64-v4?

Interpret the Paren-x64 v4 program p as a value, returning the final value of rax.

procedure (interp-loop code env pc) → int64?

code : (listof paren-x64-rt-v4.s)

env : dict?

pc : natural-number/c

The main loop of the interpreter for Paren-x64-rt v4. code does not change. env is a dict? mapping physical locations (as symbol?s) to their values (int64?). pc is the program counter, indicating the current instruction being executed as an index into the list code.

1.6.3.2 Finding the next abstraction boundary

Having exposed x64 features to our compiler internal languages, we now need to find the right boundary at which to abstract away from the low-level representation of control-flow—labels and jumps—and introduce a more structured form of control flow, if.

Our next two languages in the pipeline, bottom-up, are Paren-x64-fvars v4 and Para-asm-lang v4. Both of these languages abstract machine-specific details about physical locations. This doesn’t seem very related to control-flow, so we simply want to propagate our new primitives up through these layers of abstraction. We expose the new instructions while abstracting away from the machine constraints about which instructions work on which physical locations. Now jumps can target arbitrary locations, and compare can compare arbitrary locations. We can also move labels into arbitrary locations.

Below we typeset Paren-x64-fvars v4 (paren-x64-fvars-v4).

Nothing important changes in Paren-x64-fvars v4. We simply add the new control-flow primitives.

procedure (implement-fvars p) → paren-x64-v4?

p : paren-x64-fvars-v4?

Compile the Paren-x64-fvars v4 to Paren-x64 v4 by reifying fvars into displacement mode operands. The pass should use current-frame-base-pointer-register.

Next we typeset Para-asm-lang v4.