14 Compiler 7: Immediate Data Types

14.1 Assignment Summary

The goal of this assignment is to introduce data type representation. We will finally add booleans, as well as the empty list, the void object, characters, and an error value. We will introduce a tagged object representation to distinguished different data types dynamically. This will let us implement dynamic tag checking, reducing the amount of undefined behaviour in our surface language.

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

TODO: Explicit learning objectives

You should first merge your solution to Compiler 6: Calling Conventions 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 a7-skeleton.rkt to avoid accidentally overwriting your files, but your file in the Git repository should be named a7.rkt.

No modifications to other passes (if your compiler has been designed with good abstractions).

14.2 Language Diagram

14.3 Preface: What’s Wrong with Values-lang v6

Values-lang v6 gained the ability to express non-tail calls, an important step forward in writing real programs. However, our functions are still limited to work on machine integers. We cannot write many interesting programs without more data types.

Unfortunately, once we add data types, we have a problem distinguishing between any two data types. Everything is eventually represented as 64-bit integers in x64. We need some way to distinguish 0 as an integer, from a boolean, from the empty list, from a pointer to a function. Otherwise, we will have serious problems with undefined behaviour (like C).

One way to do this is to add a static type system. This will certainly restrict undefined behaviour, but may impose a higher cost on programming. Due to Rice’s TheoremStill a huge buzz kill., we will never be able to decide whether an arbitrary program is well typed. Instead, we will be required to approximate and/or require user annotations, ruling out some well-behaved programs to ensure no undefined behaviour.

Another way is to add dynamic checking. This imposes a run-time cost, but frees the programmer from proving absence of undefined behaviour, and allows the language implementation to catch only those errors that would actually have resulted in undefined behaviour.

We will follow Scheme and Racket’s (and JavaScript and Python and ...’s) approach and use dynamic checking.

There’s a second limitation in Values-lang v6 that we will lift this week. So far, we do not have algebraic expressions—we must manually bind all intermediate computations to names. This is particularly tedious since we know how to write a compiler, which ought to do the tedious work of binding expressions to temporary names. After we have proper data types with dynamic checking, we can more easily nest expressions, particularly in the predicate position of an if.

Our goal in this assignment is to implement the following language, Exprs-lang v7.

(define (ascii-char-literal? x)

(and (char? x) (<= 40 (char->integer x) 176)))

(define (fixnum? x)

(int-size? 61 x))

(define (uint8? x)

(<= 0 x 255))

The new a7-compiler-lib.rkt features a run-time system that supports printing the new values. execute takes a new optional second parameter, which can be used to change your view of the result. By default, you get back a Racket value. You can pass nasm-run/print-string to get back the string representation of the result, which will be handy to view the result of (void) correctly. You can pass nasm-run/exit-code to get the exit code, which is helpful for viewing the result of (error uint8), which sets the exit code to uint8.

We also add new primitive operations, primarily predicates on our new data types. The interpretation of several operations will also change to add dynamic type checking. This will prevent those operations from being a source of undefined behaviour.

With proper booleans, we can finally allow an arbitrary value in the predicate position of an if expression in the surface language.

It is not clear how to support new data types going top-down, so we begin this assignment at the bottom.

14.4 Introduction to Tagged Object Representation

A common approach to efficiently represent word-sized data types is called object tagging. Some of our clever tag choices, and some terminology, is borrowed from R. Kent Dybvig. You can learn more about it’s use in Chez Scheme from this talk by his former PhD student Andy Keep: https://www.youtube.com/watch?v=BcC3KScZ-yA. Each data type in our language will now be represented by a ptr (pronounced like footer). A ptr is a machine word whose n least-significant bits represent the primary tag, and whose upper (- word-size n) bits represent the data.

In our system, we have 64-bit words and will use the 3 least-significant bits for primary tags. With 3 bits, we can represent 8 primary data types in a ptr. We want to reserve these for the most common and most performance critical data that can fit in a ptr, but we have additional constraints. This will limit the size of data we can represent, but gives us additional data types—probably a good trade off.

If we want more than 8 data types, which most languages support, we must reserve one tag for "everything else" (a pointer to memory). The structure in memory has infinite space in which to store additional tags. This seems to leave us only 7 possible data types.

Some data types require fewer than 64-bits, and we can exploit this fact to gain a few extra data types. For example, booleans really only require one bit. The empty list and the void object only require a tag, since they do not contain any data. ASCII characters only require 8 bits. We can make all of these share a single primary tag, and steal some of the unnecessary high-order bits for a secondary tag. This gives us 4 data types for the price of only 1 primary tag—what a bargain!

This leaves us 6 primary tags. One obvious choice is to use one for fixed sized integers; these will now be 61-bit integers. Integer operations are fast, and we don’t want to slow them down by making them go through heap allocation and pointer indirection. If we wanted to support graphics and scientific operations, we would reserve one for floating-point numbers too. We reserve the remaining primary tags for tagged pointers, pointers to common heap-allocated structures. Storing the tag on the pointer instead of in memory avoids the expense of an additional memory access to check a tag and the additional memory overhead of storing the tag in memory.

A handy fact about the choice of tag for fixnums is that any number n is represented as (* 8 n). This fact allows for some optimizations on fixnum operations, and will make porting your tests easier.

The representation of error is inefficient. We only require 8 bits of data for the error code, so 24 bits are wasted. But we’re not adding more data types with secondary tags, so it is not worth over-engineering. Besides, a better error data type would use at least a string payload, which requires allocating space on the heap anyway.

The particular choice of tags is not important for correctness, although clever choices like above can help us implement common operations more efficiently. We therefore should introduce abstractions to keep the compiler abstract with respect to particular tag choices, so we can change our minds later if a better representation occurs to us.

To implement ptrs, we need bitwise operations so that we can mask off the tags bits and operate on the data. This means we need to expose bitwise operations from x64.

14.5 Exposing Bitwise Operations in Paren-x64

First, we add each of these operations as a binop to Paren-x64 v7 below.

Exercise 1: Redesign and extend the implementation of the function generate-x64. The source is Paren-x64 v7 and the target is sequence of x64 instructions, as a string.

This should be a small change if you’ve abstracted over binops.

14.6 Exposing Bitwise Operations in Block-lang

We need to expose these operations all the way up to Block-lang v7. We define the new Block-lang v7 below.

The new operations do not have large effects on the language designs or compiler passes between select-instructions and generate-x64, so we leave you to figure out most of the details. You will need to redesign the intermediate languages with the new operations.

Exercise 2: Redesign and extend the implementation of patch-instructions. The source is Paren-asm v7 and the target is Paren-x64 v7.

You need not support a more general form of arithmetic-shift-right: it cannot be implemented by simply patching this instruction with a few moves to auxiliary locations as before; the second operand must be an integer literal in the range 0 to 63 (inclusive). x64 does not provide a way to make that second operand a location.

Exercise 3: Redesign and extend the implementations of all the following passes:

• flatten-program

• expose-basic-blocks

• implement-fvars

• replace-locations

• discard-call-live

• assign-frame-variables

• assign-registers

• assign-frames

• pre-assign-frame-variables

• conflict-analysis

• undead-analysis

• uncover-locals

This should involve a change to a single function if your compiler is well-designed.

14.7 Specifying Data Type Representation

14.7.1 select-instructions

Now that we have exposed the necessary primitives, we can specify the representation of our new data types in bits. For this, we design Values-bits-lang v7, which essentially corresponds to Values-unique-lang v6 extended with the new primitives. This will be the target language of our new compiler pass.

The only data type in Values-bits-lang v7 is BITS, 64 for them, interpreted as an integer sometimes.

We assume that each binop is well-typed; they shouldn’t be used with labels as arguments.

Exercise 4: Redesign and extend the implementation of select-instructions. The source language is Values-bits-lang v7 and the target language is Block-lang v7.

This should not change much, but be sure you do not put the second operand to an arithmetic-shift-right into an aloc.

14.7.2 a-normalize

As we saw in Introduction to Tagged Object Representation, many of the operations we want to perform on ptrs are easily expressed as algebraic expressions. The expression (fixnum? 7) is expressed as (eq? (bitwise-and 7 #b111) #b000). Representing this in Values-bits-lang v7, which does not have algebraic expressions, is unnecessarily complicated. We would have to introduce auxiliary variables, manually pass them around the compiler, and generate code with additional let-bindings. This is particularly silly; we know how to write compilers, so the compiler should do this for us, and allow us to write the code we want to write.

We therefore design Exprs-bits-lang v7, a language that has only bits and bitwise operations, but that allows algebraic expressions in most positions. They are still disallowed for the predicate position of an if expression, since we cannot introduce algebraic if expressions without booleans.

I recommended that you use a procedural accumulator, i.e., write the transformation in CPS. This will turn your mind inside out, but after that, the code writes itself.

A-normal form was introduced in this paper, which you might be interested in reading, and it is still of active interest in the compiler construction and research community.

Exercise 5: Design and implement the function a-normalize. The source language is Exprs-bits-lang v7 and the target language is Values-bits-lang v7.

If you want to handle join-points, it’s more efficient and simpler if you use a single mutable variable. But be careful; you will have to manually sequentialize part of your code.

When transforming function calls, (apply e e ...), be sure to enforce left-to-right evaluation order.

14.7.3 specify-representation

Next we design Exprs-data-lang v7. We replace bits with proper data types, and lift the restriction on if expressions, which are now properly algebraic.

We assume all operations are well-typed in this language, and implement dynamic checks later. To make this clear, we prefix all the operators that require a dynamic check with unsafe-. apply is still unsafe, since we do not know how to tag functions yet.

First, we translate each value literal to ptrs.

For booleans, empty, and void, this is trivial. We simply emit their ptr representation; you can find some parameters for this defined in a7-compiler-lib.rkt.

Remember not to use magic numbers in your compiler, and instead use appropriate parameters so we can change tags and masks easily later.

The complicated cases are for operations on numbers, but even these are mostly unchanged due to some handy algebraic facts. Recall that every fixnum n is represented by a ptr whose value is (* 8 n). For + and -, this means we don’t need to do anything at all, since 8x + 8y = 8(x + y), and similarly 8x - 8y = 8(x - y). Similarly, <, <=, >, >=, and eq? all work unchanged on ptrs. However, these are boolean operations in Exprs-data-lang v7, so their implementation must return a boolean ptr.

Only * poses a problem, since 8x * 8y = 64(x * y). However, we do not need to adjust both arguments: we observe that 8x * y = 8(x * y), and similarly x * 8y = 8(x * y). We only need to shift one operand before performing * to get the correct result as a ptr. If either argument is constant, we can perform the shift at compile time, completely eliminating the additional overhead. Otherwise, we translate (* e_1 e_2) to (roughly) (* e_1 (arithmetic-shift-right e_2 3)).

Next, we translate if, which should be translated from an operation on booleans to the primitive compare-and-branch expression. Racket and Scheme are falsey languages—any thing that is not #f is considered true. We can implement this naively: simply compare to the ptr for #f. Recall from earlier that our representation allows us to treat anything that is not false as true by a simple bitwise-xor and comparison to 0, but we might want to leave that for a more general optimization.

When translating the booleans unops and binops binops on ptrs, we need to produce something that the translation of if can consume. if is expecting a boolean value, so each unop should be translated to an expression that returns a boolean. As we saw earlier, type predicates are implemented by masking the ptr using bitwise-and, and comparing the result to the tag using eq?. But the target language eq? is a comparison flag, so we translate (fixnum? e) to (if (eq? (bitwise-and e #b111) #b000) #t #f). Our representation of booleans supports optimizing this, as described earlier, but we should leave that optimization for a separate pass.

Exercise 6: Design and implement the function specify-representation. The source language is Exprs-data-lang v7 and the target language is Exprs-bits-lang v7.

Remember not to use magic constants, and instead use parameters for tags, shift lengths, and masks. See a7-compiler-lib.rkt, which defines some of these.

14.7.4 implement-safe-primops

Next we design Exprs-safe-data-lang v7, which exposes only dynamically checked versions of each unsafe operation. It also only exposes operations as functions which should be used with apply in the source language. This pass should "link" the definitions of these function in, and replace the reserved primop names for the functions with the appropriate fresh labels. Each safe function should raise a different error code depending on which operation was attempted, and which argument was not well-typed. Be sure to document your error codes.

In Exprs-safe-data-lang v7, most ill-typed expressions are valid programs. For example, (+ #t (eq? 5 (void))) is a valid program. The only invalid programs are those that attempt to apply a non-function, or use a label in any position except the first operand of apply; a limitation we will solve in the next assignment.

Exercise 7: Design and implement the function implement-safe-primops. The source language is Exprs-safe-data-lang v7 and the target language is Exprs-data-lang v7.

14.7.5 uniquify

Last but not least, we update uniquify. The source language, Exprs-lang v7, is defined below.

You are allowed to shadow prim-fs.

Exercise 8: Redesign and extend the implementation of uniquify. The source language is Exprs-lang v7 and the target language is Exprs-safe-data-lang v7.