11 Compiler 4: Adding Control Flow (Corrected)

11.1 Assignment Summary

The goals of this assignment are to (1) practice exposing low-level features from the target language to the compiler, (2) introduce designing abstractions to tame low-level operations, (3) demonstrate the problems that control flow causes with program analysis, (4) introduce linking, and (5) practice thinking about programming at different levels of abstraction. We’ll expose labels and jmp instructions from x64, provide abstractions for using them in the source language, compile the latter abstraction to the former implementation, and practice reasoning about our new source language.

This assignment is due Friday Febuary 14, 2020 at 11:59pm; you have 2 weeks this time.

By Friday Febuary 7, 2020 at 11:59pm, you should have tests for all exercises, should have finished implementing 1/3–1/2 of the exercises. We will provide interim feedback by running any tests you’ve pushed to your repository against the reference solution at this time.

Assignment Checklist

You should find a new repository in your https://github.students.cs.ubc.ca account named a4_<team ids> with a code skeleton and a support library. You should complete the assignment in that git repository and push it to the GitHub Students instance.

You should first copy your solution to Compiler 3: Register Allocation (Corrected) into the starter code provided.

If we patch the code skeleton or library after the release, the most recent version will be available here at a4-skeleton.rkt and a4-compiler-lib.rkt, and the functional graph library a4-graph-lib.rkt. The name of the skeleton is a4-skeleton.rkt to avoid accidentally overwriting your files, but your file in the Git repository should be named a4.rkt.

Per Organizing Racket Code, you are not required to keep all of your code in a single file, but a4.rkt must export the at least the names exported by a4-skeleton.rkt, and you must follow the instructions on organizing your code from Organizing Racket Code.

For non-obvious test cases, add a comment explaining which language feature or edge case you are testing. For trivial tests, such as (check-exn exn:fail? (thunk (check-values-lang '()))), this is not necessary and will only make your code less readable.

• Redesign and extend the implementation of generate-x64, a compiler from Paren-x64 v3 to x64.

• Design and implement link-paren-x64, a linker for the Paren-x64 v3 (equivalently, a compiler from Paren-x64 v3 to Paren-x64-rt).

• Redesign and extend the implementation of interp-paren-x64, the interpreter for Paren-x64 v3

• Redesign and extend the implementation of patch-instructions, a compiler from Paren-asm v2 to Paren-x64 v3.

• Design and implement flatten-program, a compiler from Block-asm-lang to Paren-asm v2.

• Design and implement expose-basic-blocks, a compiler from Block-nested-lang to Block-asm-lang.

• Redesign and extend the implementation of replace-locations, a compiler from Block-assigned-lang to Block-nested-lang.

• Design and implement discard-call-live, a compiler from Block-jump-live-lang to Block-assigned-lang.

• Redesign and extend the implementation of assign-registers, a compiler from Conflict-lang v2 to Block-jump-live-lang.

• Redesign and extend the implementation of conflict-analysis, a compiler from Undead-block-lang to Conflict-lang v2.

• Redesign and extend the implementation of undead-analysis, a compiler from Block-locals-lang to Undead-block-lang.

• Redesign and extend the implementation of uncover-locals, a compiler from Block-lang to Block-locals-lang.

• Redesign and extend the implementation of select-instructions, a compiler from Values-unique-lang v2 to Block-lang.

• Redesign and extend the implementation of uniquify, a compiler from Values-lang v2 to Values-unique-lang v2.

11.2 Language Diagram

11.3 Related Reading

You can find additional reading material on register allocation and undead analysis at the resources below. These comes from other courses that use a compiler that is similar to, but different from, your compiler. Their intermediate languages are different, and their compiler pipeline is different. There is no one universal truth of how these passes work for all compilers in all situations, so you will need to generalize from these lessons and apply them to your compiler.

11.4 Preface: What’s wrong with Values-lang

The language Values-lang has a significant limitation: we can only expression simple, straight-line arithmetic computations. We’ll never be able to write any interesting programs!

In this assignment, we will expose a machine feature, control flow instructions in the form of labels and jmp instructions, and systematically abstract these. This requires changes to nearly every pass and every intermediate language.

We’ll proceed bottom-up, but first let’s take a look at our goal. We want to extend Values-lang with control-flow features: a form of if expression, top-level function definitions, and non-returning function calls (tail calls).

Note that an if expression, (if (cmp v v) e e), 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 inherited from x64. Even by the end of this assignment, 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.

Note also that a function can only be called as the very last expression. This is because we will not have introduced enough to implement returning from a function, so all function calls are restricted to only jump forward.

Despite the limitations of Values-lang v2, the language is finally expressive enough to write interesting programs. We’ll therefore implement a type checking tool to help us program in Values-lang v2, and spend some time writing programs to understand its expressiveness and its limitations. If you prefer, you can jump to the last few exercises and complete those first.

11.5 Exposing Control-Flow Primitives

We’ll start by designing a new Paren-x64 v3 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.

(define (label? s)

(and (symbol? s)

(regexp-match-exact? #rx"L\\..+\\.[0-9]+" (symbol->string s))))

In Paren-x64 v3, we model labels with the (define 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 behavior as chaining labels in x64. For convenience, we assume all labels are symbols of the form L.<name>.<number>, and are unique.

Note that (define label s) does not behave like a define in Racket or in Values-lang v2. The instruction s gets executed after the previous instruction in the sequence, even of the previous instruction was not a jump. All define does here is name the instruction so 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 condition jump instruction.

The conditional jump instructions in x64, in the same order as the cmp, are: jne label, je label, jl label, jle label, jg label, and jge label. 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 v3, we abstract the various conditional jump instructions into a single instruction with multiple flags. The instruction je l corresponds to (jump-if eq? 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.

Exercise 1: Redesign and extend the implementation of generate-x64 to support control-flow primitives. The source language is Paren-x64 v3 and the target language is x64.

To compile halt to Paren-x64, it may help if you generate a labeled instruction that essentially does nothing. This way, you can insert a label at the end of your program. Otherwise, you’ll need to think carefully about how to arrange and generate blocks.

Labels and jumps are a small change to the language syntactically, but have a large effect on the semantics. You’ll notice this, for example, when writing the interpreter for a language with labels and jumps compared to a language without them.

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

We’re going to write a simple linker for Paren-x64 v3 to give you a rough idea of how the operating system’s linker works. We’ll use a low-level linking implementation that is similar to the operating systems 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, which represents the run-time language used by the interpreter after linking.

(define pc-addr? natural-number/c)

We remove the instruction (define label s), which the linker will remove, and turn all label values into pc-addr, a representation of an address recognized by the interpreter. 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.

Exercise 2: Design and implement link-paren-x64, which resolves all labels into the address of the instruction in the instruction sequence. The source language is Paren-x64 v3 and the target language is Paren-x64-rt.

Exercise 3: Redesign and extend the implementation of interp-paren-x64 to support control-flow primitives. The source language is Paren-x64 v3 and the output is a Racket integer.

It should use link-paren-x64 to resolve all labels, and should use a program counter to loop over the instruction sequence instead of folding over the sequence. This means some inner helper function accepts Paren-x64-rt programs.

You may want to refer to the code skeleton in a4-skeleton.rkt.

Next, we redesign Paren-asm v2, exposing 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 locations.

While halt is still an instructions, we assume that there is exactly one halt in the program, and that it is the final instruction executed in the program. We do not restrict the syntax to require this, since we now support jumps. Jumps mean our syntax does not give us a clear indication of which instruction is executed last. It might be the case that halt is the second instruction in the instruction sequence, but is always executed last becuase of the control flow of the program. It could also be that there are multiple halt instructions syntactically, but only one will ever be executed due to conditional jumps.

While we’re redesigning, we also lift some restrictions to allow our compiler to "not be stupid". We generalize Paren-asm v2 to allow literal values in some operands. We allow jumps to take either a location or a label directly, and allow binops and halt to take either a value or a location. Relaxing this restriction makes Paren-asm v2 less uniform, but makes it easier to work with, and allows us to produce better code.

Forcing ourselves to "be stupid" is a common hazard when designing abstraction boundaries. Previously, in our attempt to abstract away from annoying details of x64 and make a more uniform language, we actually forced our compiler to produce worse code. We required all operations in Paren-asm to work uniformly over locations only, even though x64 supports working over values for many instructions. This required all compiler passes that target Paren-asm to introduce extra instructions. While we could "optimize" those instructions away, it’s often better to "not be stupid"—to avoid generating bad code that you have to clean up, since optimizations are often incomplete.

Exercise 4: Redesign and extend the implementation of patch-instructions to implement the new instructions jump and compare instructions that don’t exist in x64 by instruction sequences that are valid in x64. The source language is Paren-asm v2 and the target is Paren-x64 v3.

It will be tricky to implement the instruction (compare addr addr) with only one temporary register. You can do it in four Paren-x64 v3 instructions.

You should continue to use rax as a temporary register.

11.6 Blocks: Abstracting labeled instructions

In Paren-asm v2, control can jump to any instruction at any time. This makes giving semantics to programs, such as writing an interpreter or an analysis, very difficult. At any label, we must make assumptions about the state of the machine, since the state is not affected only by the sequence of instructions that came before the label in the instruction sequence, but potentially arbitrary instructions that were executed prior to a jumping to the label.

To simplify reasoning about programs, we can organizing code into labeled blocks, assuming that control flow only enters the beginning of a block and exits the end of a block. This block abstraction simplifies reasoning about control flow. We have more structure on which to hang assumption, and can make more assumptions about code when writing analyses. We want to introduce this abstraction before we have to extend the register allocator, which currently does the most analysis in our compiler.

We design Block-asm-lang, a basic-block-structured abstract assembly language in which sequences of statements are organized into basic blocks, and code can jump between blocks. Labels are no longer instructions that can happen anywhere; instead, each block is labeled. Jumps cannot appear just anywhere; instead, they happen only at the end of a block.

In Block-asm-lang, a program is a non-empty sequence of labeled blocks. We consider the first block in the sequence to be the start of the program. A tail represents a self-contained block of statements. Jumps can only appear at the end of blocks, and jumps only enter the beginning of blocks.

The halt instruction should only appear at the end of the final block; it cannot stop control flow, but only indicates that if the program has ended, the opand is the final value. Again, we cannot enforce this syntactically due to jumps. Instead, we require that halt appears at the end of a block, and assume only one halt instruction is ever executed during exectuion.

Note that now there is an info field for each block. Many analyses that previously worked over the entire program must now work over each block.

Exercise 5: Design and implement flatten-program to flatten all blocks into straight-line code. The source language is Block-asm-lang and the target language is Paren-asm v2.

Challenge 1: In Paren-asm v2, it’s unnecessary to have a jump when the target of the jump is the next instruction. Design and implement an optimization pass, called inline-jump, that eliminates these unnecessary jumps. The source language is Paren-asm v2 and target is Paren-asm v2

Challenge 2: Branches are often thought of as expensive, so real compilers often perform trace scheduling, an optimization that rearranges blocks and takes advantage of fall-through between blocks to reduce the number of jumps.

Implement a function trace-schedule to perform this optimization. The source language is Block-asm-lang and the target language is Block-asm-lang.

This optimization works in conjunction with the previous optimization.

11.6.1 Nested tails

Before we start modifying the register allocator, we will make a simplifying assumption: we should allow nested tails. This means nested if statements, and begins in the branches of an if statement.

It is not obvious why we would want to make this change, and this is one place where our back-to-front design fails us. In truth, compiler design, like most software design, is an interative process. We must look ahead a few steps in the compiler to see the problem.

If we were following our nose and propagating our new features up to the next abstraction layer, the next step might be to simply start on the register allocator, extending it with support for blocks. As soon as we do that, we realize that analyzing arbitrary jump instructions is kind of complicated. However, analyzing if is somewhat less complicated, as the structure of the control flow is more constrained. By allowing tails to be nested, we can allow more ifs and fewer apparent jumps in the source language of the analyses. The fewer jumps, the better job the analysis can do, and the better code it can produce. So we want to minimizes jumps in the language that we analyze.

We introduce Block-nested-lang, which allows nesting some sequences of expressions that would otherwise require additional blocks and jumps. In particular, if and begin can be nested. This means we could have an if statement of the form (if (cmp loc loc) (begin s ... (jump loc)) (begin s ... (jump loc))). Compiling this require introducing a new fresh label. The nesting structure allows all earlier compiler passes to ignore jumps that are quite easy to eliminate. In general, jumps are difficult to deal with (as we will see), so avoiding them for as long as possible is generally a good design choice.

Exercise 6: Design and implement expose-basic-blocks, which creates new blocks of any nested tails and replaces those nested tails with jumps. The source language is Block-nested-lang and the target language is Block-asm-lang.

You may want to use fresh-label from a4-compiler-lib.rkt.

11.7 Abstracting Low-level Control Flow

We now switch to a top-down perspective. So far, our goal was merely to expose some of the low-level features of x64. But going bottom-up, the next step is register allocation. It’s not clear how to assign registers to variables until we know how variables behave in this language with function calls.

We define Block-lang, a basic-block-structured location-oriented language. This is essentially the same as Block-nested-lang, but without the info field, and with all locations replaced by abstract locations. We know the register allocator will be responsible for assigning the abstract locations to real locations.

We also know that the register allocator will need some information about programs. In particular, the undead analysis will need to know what locations are undead-out after a jump. Since it may be impossible to figure out the target of the jump (Rice’s Theorem), we will annotate all jumps will that information any time we generate a jump instruction. Their only purpose here it to communicate to the analysis which locations should be considered undead; they are not actual arguments any more.

Notice that if we did not allow nested tails, the branches of each if expression would require these annotation. It’s pretty clear how to produce the arguments to a jump from a function call. However, trying to produce arguments for every if expression would not be so obvious. We would essentially need to perform undead analysis on the branches of the if, but the whole point of the annotation is to simplify undead analysis.

There are many design choices in a compiler like this. If we introduce an abstraction too late, our compiler may suffer. However, as we saw in the design of Paren-asm vs Paren-asm v2, premature abstraction boundaries can cause us to suffer as well.

(define (aloc? s)

(and (symbol? s)

(not (register? s))

(not (label? s))

(regexp-match-exact? #rx".+\\.[0-9]+" (symbol->string s))))

Now we need to design value-oriented versions of if and jump.

In Values-lang v2, we extend expressions with an if expression that takes a comparison between two values. We have to restrict the predicate position because we have no explicit representation of the value that a comparison operation produces, i.e., we don’t have booleans. All the intermediate languages simply use the comparison instruction, which sets x64 flags that we do not yet have access to. The lower level languages we’ve design essentially treat compare-and-branch as an atomic statement.

We also add an apply expression that can call a declared function with some arguments. We must restrict calls to be in tail position, i.e., as the final expression in a block, since we do not know how to implement returning from a function call yet.

Notice that we also modify a program syntax to be a list of function definitions followed by an expression. The final expression is where code begins executing.

Now that we have more than one kind of value (we have int64 and label), we begin to run into the problem of ill-typed operations. For example, our run-time system assumes that we halt with an integer, but the syntax of Values-unique-lang v2 allows the final expression to be a label. Similarly, a binop will only succeed if it is given two integers, but not if we try to add an integer and a label.

We have two options to make our language make sense: we can add dynamic type checking, or we can assume the problem never happens because the constraints of a higher language and its compilation strategy avoid this scenario. We’re still dealing with quite a low-level language, so we choose the latter option.

Similarly, we assume that labels are never used as arguments to binops, cmps. They can be used as arguments to apply, though.

Note that you won’t be able to write a checker to enforce these property on all programs, so you must simply assume it.

We modify Values-unique-lang v2 to include the if and apply expressions.

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

You may find this implementation of alpha equivalence for Values-lang v2 helpful: a4-alpha-equal.rkt. The code is annotated to demonstrate idiomatic Racket style, and explain feature you may be unfamiliar with.

We therefore add as a requirement to Values-lang v2 that a program is only valid if it contains no indirect function calls.

Exercise 8: Redesign and extend the implementation of select-instructions to translate value-oriented operations into location-oriented instruction. The source language is Values-unique-lang v2 and the target language is Block-lang.

11.8 Register Allocation

Next we need to extend the register allocator and analyses to jumps. We continue top-down.

Since variables are now shared across blocks. Essentially, our abstract locations represent global variables. The only way we can allocate registers correcly is to ensure the register allocation is aware of conflicts across blocks, and shares assignments across blocks. To do this, we need to do undead analysis across blocks, discover conflicts across blocks, and ensure register assignments are shared across blocks.

We can easily accomplish this by first uncovering locals on each block, then taking the union of the locals sets for the entire module.

Exercise 9: Redesign and extend the implementation of uncover-locals to add a list of all variables used in each block to the info field of the block. The source language is Block-lang and the target language is Block-locals-lang.

11.8.1 Undead analysis, globally

Now that we have variables that are live across blocks, our undead analysis algorithm must change to follow the control flow of the program. This gives us a more general analysis that is more precise, but much more complex and difficult to implement efficiently.

First, we define Undead-block-lang below.

(define (undead-set? x)

(and (list? x)

(andmap aloc? x)

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

(define (undead-set-tree? ust)

(match ust

[(? undead-set?) #t]

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

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

[else #f]))

We will not need undead-out sets for the module; only each block.

We add the undead-out sets to our info fields. The data structure of undead-out sets is more complex than in Compiler 3: Register Allocation (Corrected). Previously, programs were lists of instructions, so a list sufficed. Now, our programs are trees. if introduces branching.

We design a new data structure call the Undead-set-tree below.

11.8.2 Control-flow Analysis, and use/def chains

To compute the undead sets, we first need to perform control-flow analysis to build a control-flow graph. A control-flow graph is a directed graph in which each instruction represents a node (vertex), and an edge from vertex v1 to v2 means that v1 is executed before v2. In general, a vertex may have multiple predecessors due to jumps, and a multiple successors due to branching.

We generate the control-flow graph essentially by labeling each instruction with a uniquie identifier (such as a number, a symbol, or a pointer to the instruction’s representation), traversing the program, and adding an edge from instruction’s ID to the ID of its successor.

While building the control-flow graph, we also collect all the variables defined at that node in the graph, and all the variables used at that node. A variable is defined if it gets a new value assigned to it, such as the variable x.1 in the instruction (set! x.1 (+ y.6 z.7)). A variable is used if it is referenced in the instruction, such as y.6 and z.7 in the above instruction. We associate these sets with the instruction’s ID.