15 Compiler 8: Structured Data Types

15.1 Assignment Summary

The goal of this assignment is to introduce memory allocation and structured data. We will add cons pairs, vectors, and procedures. We will extend out tagged object representation to distinguished these data types dynamically.

This assignment is due Friday, March 20, 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/a8-interrogator.cgi

A file with tests is available here: a8-tests.rkt.

You should first merge your solution to Compiler 7: Immediate Data Types with the starter code provided. The new starter code has the correct provides and includes a submodule to help you run your compiler on the command line if you want. The name of the skeleton is a8-skeleton.rkt to avoid accidentally overwriting your files, but your file in the Git repository should be named a8.rkt.

15.2 Language Diagram

15.3 Preface: What’s wrong with Exprs-Lang v7

Exprs-lang v7 gained proper data types and algebraic expressions, which is a huge step forward in expressivity and high-level reasoning. However, it still does not allow us to express structured data. This is greatly limits our expressivity. Real languages require structured data—such as strings, vectors, and linked lists—to express interesting programs over data larger than a single word. Functional languages use procedures, a data structure, to provide functions as first-class values.

To express data larger than a single word, we need support from the low-level languages to get access to locations larger than a single word in size. All our locations so far, registers and frame locations, are only a single word in size. We need access to heap pointers, memory locations whose size can be arbitrary.

To implement these new memory operations, or mops, we need to expose additional features from x64.

15.4 Exposing Heap Pointers in the Back-end

15.4.1 generate-x64

We start by exposing a generalized addr form in Paren-x64 v8 below, which will allow us to access arbitrary memory locations.

The language contains a new addr representing the x64 index-mode operand (reg + reg). This supports accessing a memory location by the index stored in another register. For example, in x64, we represent loading the nth element of an array into r10 using mov r10 [r11 + r12], where the base of the array is stored at r11 and the value of n is stored in r12.

The index-mode operand is not restricted to use a particular register, unlike the displacement-mode operand from Paren-x64 v7. We will use this feature to store pointers to structured data, and the register allocator will move those pointers into whichever registers it chooses.

We also allow a generalized form of displacement-mode operand. We can access the value of pointed to by base register reg at offset int32. by (reg + int32). This allows optimizing heap accesses when a constant offset is known, which is often the case for some data structures. The index is not restricted to be a multiple of 8, but it should be the case in our compiler that the value of the base plus the value of the offset is a multiple of 8.

All languages with direct access to registers, including Paren-x64 v8, are now parameterized by a new register, current-heap-allocation-pointer-register (abbreviated hbp). The run-time system initializes this register to point to the base of the heap. Allocation is implemented by copying the current value of this pointer, and incrementing it by the number of bytes we wish to allocate. The pointer must only be incremented by word-size multiples of bytes. Any other access to this register is now undefined behavior, similar to accesses to fbp that do not obey the stack of frames discipline.

Design digression:

A real language implementation would expose access to the mmap system call for allocation, and implement a strategy (such as garbage collection) to deallocate memory that is no longer used. Garbage collection is tricky to implement and requires too much time for this course, so we use a different strategy. Our implementation of allocation is trivial, and does not support de-allocation. We rely on the operating system to clean up memory after our process exits.

Exercise 1: Redesign and extend the implementation of generate-x64 to support index-mode operands. The source language is Paren-x64 v8, and output is a sequence of x64 instructions represented as a string.

This should be a one-line change if your compiler is well designed.

15.4.2 implement-mops

Like when we implemented fvars to support working with frame locations, we implement primitive memory operations, mops (pronounced em ops), to simplify working with heap addresses. We should do this before patch-instructions to avoid complicating the already complex logic for rewriting set! instructions.

Exercise 2: Design and implement implement-mops. The source language is Paren-x64-mops v8 and the target is Paren-x64 v8. This should be a very simple compiler.

15.4.3 patch-instructions

Next we design Paren-asm v8. Below, we give a definition. However, your design may differ slightly since you’ve been responsible for the design of Paren-asm v6 and Paren-asm v7.

By introducing mops, we implicitly restrict how heap addresses appear in the language and simplify the job of patch-instructions. The mops implicitly restrict heap addresses to being part of a move instruction, so we do not have to patch binary operation instructions despite apparently adding a new form of physical location. By making them separate forms, we only need to patch the new instructions, and leave old code untouched.

Exercise 3: Redesign and extend the implementation of patch-instructions. The source language is Paren-asm v8 and the target language is Paren-x64-mops v8.

You only need to add two cases, and you can write them very systematically, but they will take care to get right and cover all combinations.

15.4.4 Exposing mops up the pipeline

The new mops require minor changes to most of the pipeline up to Block-lang v8, where we will use them to implement data structures.

Exercise 4: Redesign and extend the implementation of

• flatten-program, should require no changes

• expose-basic-blocks, should require no changes

• implement-fvars, should require minor changes to support mops. Note that we assume the fbp is not modified by mops.

• replace-locations, should require minor changes to support mops.

• discard-call-live, should require no changes.

• assign-frame-variables, should require no changes.

• assign-registers, should require no changes.

• assign-frames, should require no changes.

• pre-assign-frame-variables, should require no changes.

• conflict-analysis, should require minor changes. Note that mops do not assign any registers or frame variables.

• undead-analysis, should require minor changes. Note that mops do not assign any registers or frame variables.

• uncover-locals, should require minor changes.

15.4.5 expose-allocation-pointer

Before we introduce structured data, we implement the alloc instruction to allow programs to allocate a bunch of bytes and not worry about the details of the allocation pointer. We want to do this after the passes that analyze physical locations, since then we do not have to update those passes to know that alloc introduces a reference to a register. However, we want to do this before we abstract away from all machine details so we do not need to expose registers beyond Block-lang v8.

We choose to insert this pass between uncover-locals and select-instructions.

Below, we design Block-lang v8, the source language for this pass.

TODO: Should not reuse index as the operand for alloc; it is semantically a different concept, which happens to have the same representation.

We expose the earlier mops, and add a new one, (set! loc (alloc index)). This is the low-level form of our allocation operation, which we will abstract into an expression in Exprs-lang v8. In (set! loc (alloc index)), the index is restricted to be an int32 if it is an integer literal, for the same reasons as the restriction on binops. It must also be a multiple of a word size. This requirement is partly from the operating system’s mmap (which will usually ignore us if we violate the restriction and give us page-aligned memory anyway), but mostly to ensure every pointer we get has #b000 as its final three bits so we can tag all pointers.

We design the target language, Block-hbp-lang v8, below. This language removes the alloc index form and is the highest-level language parameterized by current-heap-base-pointer-register. This language, and all languages between it and x64, assumes all accesses to hbp obey the restrictions described in Paren-x64 v8.

Exercise 5: Design and implement the function expose-allocation-pointer. The source language is Block-lang v8 and the target language is Block-hbp-lang v8.

15.4.6 select-instructions

Below we design Impure-Values-bits-lang v8 with support for mops.

The language is an extension of Values-bits-lang v7. We add value forms of mref and alloc to the n nonterminal. We require these forms are used in a well-typed way. This is a simple extension.

However, supporting mset! requires that we introduce a notion of effectful, or impure, computation into the language. Previously, all expressions in the Values-lang languages were pure—they evaluated and produced the same value regardless of in which order expressions were evaluated. We could freely reorder expressions, as long as we respected scope. Now, however, mset! modifies memory during its execution. It not safe to reorder expressions after an mset!. Furthermore, mset! does not return a useful value.

To deal with this, we introduce a contextual distinction in the language. We add the nonterminal c to represent an impure computation. A c represents an expression that does not have a value, and is executed only for its effect. We can use c in certain expression contexts using begin. If we’re already in an impure context, that is, in a c, then we can freely nest other cs.

This contextual distinction is similar to the one we introduce to distinguish tail calls from non-tail calls.

Despite the conceptually complex change to the language, the transformation is straightforward. Previously, select-instructions essentially implemented the pure Values-bits-lang v7 using the impure Block-lang v7. To transform the effectful computations, we essentially splice them into the effectful computations select-instructions was already producing. The new mops n are already valid operands in the target language, so nothing special is needed to deal with them.

Exercise 6: Redesign and extend the implementation of the function select-instructions. The source language is Impure-Values-bits-lang v8 and the target language is Block-lang v8.

select-instructions is getting to be a big pass. It now does several things—flattens let into set!, implements calling conventions, and selects instructions to implement binary operations on values. If you haven’t already, you might want to redesign it as several smaller passes.

15.4.7 a-normalize

Next we design Impure-Exprs-bits-lang v8 with support for mops.

While we remove the distinction between expressions and values, we maintain the contextual distinction between impure computations and pure expressions.

Exercise 7: Redesign and extend the implementation of the function a-normalize. The source language is Impure-Exprs-bits-lang v8 and the target language is Impure-Values-bits-lang v8.

Be careful not to reorder the effectful operations.

15.4.8 specify-representation

Now we have all the abstractions necessary to implement structured data.

We design a new Impure-Exprs-data-lang v8.

We add new primops for each of our new data types. Since the number of primitive operations is growing, we simplify the syntax to only give primops, rather than distinguishing unops, binops, and so on, so we can easily group like primops with like.

We also add impure computations, since vectors are a mutable data structure. Only effectful primops, those ending with !, are allowed in impure computations.

We follow the same pattern as Compiler 7: Immediate Data Types to implement the new predicates.

To implement constructors, we need to compile to alloc. cons allocates two words of space, storing its first argument in the first word and the second element in the second word, producing `(alloc ,(current-pair-size)). The ptr we get back needs to be tagged, so we produce `(bitwise-ior (alloc ,(current-pair-size)) ,(current-pair-tag)). make-procedure also allocates two words, one for the label and one for the argument arity. unsafe-make-vector allocates one word for the length, and then one word for every element of the vector. That is, it should allocate n+1 words for a vector of length n.

Since the length of the vector is dynamically determined, we do not initialize each field when implementing its constructor. Instead, we expose an unsafe constructor for vectors, and leave it to a safer language to initialize the vector.

Exercise 8: Redesign and extend the implementation of the function specify-representation. The source language is Impure-Exprs-data-lang v8 and the target language is Impure-Exprs-bits-lang v8.

Remember to not use constant values and instead use parameters. Some values may change.

Remember that the input language uses fixnum ptrs for all inputs, but the output uses bytes for mops.

15.4.9 implement-safe-apply

Last week, the last piece of undefined behavior in our language was in procedure calls. We were not checking that procedures were correctly applied to the number of expected arguments. Lower down, when procedure calls are implemented in terms of register and frame variables, this could result in dereferencing uninitialized locations. We can use the procedure data type to eliminate this undefined behavior.

This week, this pass is optional, as current events mean I haven’t been able to write up the design in time. Lucky you.

Challenge 1: Design and implement implement-safe-apply. You should design the source language, and the target language is Impure-Exprs-data-lang v8.

15.4.10 implement-safe-primops

All the accessors for the new data types can result in undefined behavior if used on the wrong ptr. Similarly, vector reference can access undefined values if the vector is constructed but never initialized.

Below we define Impure-Exprs-safe-lang v8.

As in the last assignment, we wrap all accessors to perform dynamic tag checking before using the unsafe operations. We also wrap unsafe-make-vector to initialize all elements to 0.

We remove make-procedure and procedure-label, which are used internally. The surface programmer will only be able to define safe procedures using lambda. However, we do allow the user to dynamically test whether a value is a procedure and how many arguments it takes.

Note that in this language, we’ve removed begin. The user must manually call impure functions and bind the result. The result of an effectful function could be void, or an error. It would be unwise, although technically safe, to simple discard errors.

All impure computations, those that end in !, should only return (void) or an error.

Exercise 9: Redesign and extend the implementation of implement-safe-primops. The source language is Impure-Exprs-safe-lang v8 and the target language is Impure-Exprs-data-lang v8, or your designed target language if you completed the challenge problem.

Now that there are now more combinations of primops and arguments than are possible to encode in a single number. You’ll need to give up some precision in error messages.

15.4.11 uniquify

Finally, we define the source language. Below we define Exprs-lang v8.

Exercise 10: Redesign and extend the implementation of uniquify. The source language is Exprs-lang v8 and the target language Impure-Exprs-safe v8.