1.3 Abstract Locations

1.3.1 Preface: What’s wrong with our language?

In the last chapter, we designed our first language, Paren-x64 v1, and wrote our first compiler to implement it. This language introduces the barest, although still very useful, abstraction—freedom from boilerplate. Paren-x64 v1 abstracts away from the boilerplate of x64, and details of exactly how to pass a value to the operating system.

While Paren-x64 v1 is an improvement of x64, it has a significant limitation for writing programs that we address in this chapter. The language requires the programmer to manually manage a small number of variables, namely the registers, while programming. Human memory is much less reliable than computer memory, so we should design languages that make the computer remember more and free the human to remember less. This will prevent the human from causing run-time errors when they inevitably make a mistake and overwrite a register that was still in use.

To address this, we will introduce abstract locations, of which there are an arbitrary number and that the programmer does not need to know what physical location they end up using.

In general, these cannot all be mapped to registers, since there are a fixed number of registers. So to implement abstract locations, we’ll need to expose a little more from our target language. We expose some limited access to memory in x64, and introduce the abstraction of a frame variable to help use compile abstract locations to physical locations.

We also need to design a new language, and some translations, that enable instructions to work over abstract locations, even though x64 restricts which kinds of physical locations instructions can use.

1.3.2 Designing a Source language

When designing a new abstraction, I often start by reading and writing some programs using an existing abstraction until I spot a pattern I dislike.

We’ve seen a few Paren-x64 v1 programs by now, and they all have a pattern: all computations act on a small set of 16 registers. This limits the way we can write computations. We must, manually, order and collapse sub-computations to keep the number of registers that are in use small. We must keep track of which registers are still in use before we move a value, or we will overwrite part of our computation.

Furthermore, the instructions we’re given are idiosyncratic—they only work with certain operands, such as requiring some integer literals to be 32-bit or 64-bit, depending on which instruction we’re using. The programmer is forced to consider the size of their data before choosing how to proceed with a computation.

These limitations make programming cumbersome and error-prone.

Instead, we should free the programmers (ourselves), eliminating cumbersomeness and removing error-prone programming patterns.

We should free the programmer to invent new locations at will if it helps their programming, and not worry about irrelevant machine-specific restrictions on these locations.

We design a new language, Asm-lang v2, to abstract away from these two machine-specific concerns.

The language no longer knows about registers, but instead presents an abstract location to the programmer. There are two assembly instructions—move a value to an abstract location, or perform a binary operation on an abstract location. These now act uniformly on their arguments. The left-hand-side is always the destination location, and the right-hand-side is an arbitrary trivial value.

Our convention requires that we pass the result to the OS in rax, but we’ve removed registers from the language. This requires us to design some new feature that we can use to indicate the result without exposing registers, and that the compiler can identify in order to compile to an instruction that sets rax. We add the halt instruction, which indicates the end of the computation with a particular value as the result.

1.3.3 Exposing Memory in Paren-x64

We first need to expose x64 features to access memory locations. In particular, we expose displacement mode operands for memory locations. The displacement mode operand is a new operand that can appear in some location positions as the operand of an instruction. This allows accessing memory locations using pointer arithmetic. It is written as QWORD [reg - int32] or QWORD [reg + int32] in x64, where reg is a register holding some memory address and the int32 is an offset number of bytes from that address to access, as a 32-bit integer. The keyword QWORD, which is an unintuitive spelling of "8 bytes", indicates that this operand is accessing 64 bits at a time.

"Word" normally means the unit of addressing memory—64 bits in our case. Unfortunately, in the past, the word size was different. In order to avoid backwards incompatibilty changes, tools that use WORD as a keyword, like nasm, didn’t want to change it’s meaning. Instead, the keyword WORD means 16 bits, not the word size, and prefixes give us multiple of that notion of WORD. So QWORD is 4 WORDs, or 64 bits, which is the word size on x64.

For example, if rbp holds a memory address, we can move the value 42 to that memory address using the instruction mov QWORD [rbp - 0], 42. We can move the value from memory into the register rax using the instruction mov rax, QWORD [rbp - 0].

These accesses grow downwards, subtracting from the base pointer rather than adding, following common conventions about how stack memory is used. This is an arbitrary choice, but we choose to follow the convention.

The new version of Paren-x64 v2 (paren-x64-v2) is below.

We add the new non-terminal addr to the language, and add addr as a production to loc. The addr non-terminal represents a displacement mode operand to an instruction. We abstract the language over the base frame pointer, the pointer to the start of the current stack frame, which is stored in the parameter current-frame-base-pointer-register and is rbp by default. An addr may only be used with the current-frame-base-pointer-register as its first operand. The offset of each addr is restricted to be an integer that is divisible by 8, the number of bytes in a machine word in x64. This ensures all memory accesses are machine-word aligned, meaning we leave space for all bytes in the word between each access. Note that the offset is negative; we access the stack backwards, following the x64 "stack grows down" convention.

All languages in our compiler assume that the uses of current-frame-base-pointer-register obey the stack discipline, defined below; all other uses are undefined behaviour. Setting its value directly is forbidden. Pointer arithmetic, such as (set! rbp (+ rbp opand)), is allowed only when the opand is a dispoffset?. Incrementing the pointer beyond its initial value given by the run-time system is forbidden. We do not try to enforce these statically, since it may be impossible to do so in general.

Design digression:

The language is parameterized by the current-frame-base-pointer-register. Parameterizing the language this way lets us avoid committing to particular register choices, making the language inherently more machine and convention agnostic. This is helpful in designing a compiler with multiple machine backends. A real compiler would want to support many machines, not just x64, and parameterizing the language makes this simpler. We could imagine retargeting a new operating system that uses a different stack register, by changing the value of current-frame-base-pointer-register, among other parameters. If our language definitions were sufficiently parameterized, few if any compiler passes would need to differ between target machines. This language is not suffiently abstract yet, but using parameterized languages in this way is a common tool we will use.

To use the stack, the run-time system must initialize current-frame-base-pointer-register. On systems following the SYS V ABI, rsp is initialized the end of the virtual memory space, so we can create a simple run-time system by copying rsp into rbp, and growing down from there will access unused memory.

We provide such a run-time system in cpsc411/2c-run-time. The run-time system provides a default stack of size 8 megabytes. This should be enough for now, but if it’s not, you can use the parameter? current-stack-size to increase it. Our run-time system also prints the value of rax to the screen, instead of returning it via an exit code, and does the work of converting numbers to ASCII strings. The execute function uses nasm-run/read to parse printed output into a Racket datum. If you’re interested in how this is done, you can read the definition of wrap-x86-64-run-time. We assume that this run-time system is used until we introduce data types, which require additional run-time support.

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

p : paren-x64-v2?

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

Examples:

> (require racket/pretty)

> (pretty-display    (generate-x64 '(begin (set! rax 42))))

mov rax, 42

> (pretty-display    (generate-x64 '(begin (set! rax 42) (set! rax (+ rax 0)))))

mov rax, 42 add rax, 0

> (pretty-display    (generate-x64    '(begin       (set! (rbp - 0) 0)       (set! (rbp - 8) 42)       (set! rax (rbp - 0))       (set! rax (+ rax (rbp - 8))))))

mov QWORD [rbp - 0], 0 mov QWORD [rbp - 8], 42 mov rax, QWORD [rbp - 0] add rax, QWORD [rbp - 8]

> (pretty-display    (generate-x64    '(begin       (set! rax 0)       (set! rbx 0)       (set! r9 42)       (set! rax (+ rax r9)))))

mov rax, 0 mov rbx, 0 mov r9, 42 add rax, r9

> (current-pass-list    (list     check-paren-x64     generate-x64     wrap-x64-run-time     wrap-x64-boilerplate))

> (execute '(begin (set! rax 42)))

42

> (execute '(begin (set! rax 42) (set! rax (+ rax 0))))

42

> (execute    '(begin       (set! (rbp - 0) 0)       (set! (rbp - 8) 42)       (set! rax (rbp - 0))       (set! rax (+ rax (rbp - 8)))))

42

> (execute    '(begin       (set! rax 0)       (set! rbx 0)       (set! r9 42)       (set! rax (+ rax r9))))

42

1.3.4 Abstracting the Machine

Now that we have effectively unlimited physical locations—registers and memory locations that can store values—on the machine, we want to begin abstracting away from machine details.

The first thing we do is to abstract away from the displacement mode operand, introducing an abstract notion of frame variable, a variable that is located in a particular slot on the frame. This lets the programmer stop worrying about details like which register contains the frame base, and what the constraints on displacement mode offset are.

We replace the addr, the displacement mode operand, with the abstraction of an fvar, which represents a unique location on the frame, relative to the current value of current-frame-base-pointer-register. These are written as the symbol fv followed by a number indicating the slot on the frame. For example fv1 is the frame variables indicating the first slot on the frame. Frame variables are distinct from registers and abstract locations. The number represents the index into the frame for the current function.

In Paren-x64-fvars v2, it is still undefined behaviour to violate stack discipline when using current-frame-base-pointer-register.

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

p : paren-x64-fvars-v2?

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

This is a useful step toward an abstract assembly language, but we’re still forced to remember odd restrictions on which kind of physical location each instruction takes as an operand. Our instructions in Paren x64-v2 are restricted by x64. For example, binary operations must use a register as their first operand.

We can create a new language which allows the user to ignore the differences between physical locations, enabling any instruction to work on any kind of physical locations. This way, the language is responsible for managing these annoying details instead of the programmer.

We do this by defining Para-asm-lang v2 (para-asm-lang-v2), a kind of less finicky assembly language. We can think of this language as parameterized by the set of locations, hence the name.

The main difference is in the effect non-terminal, which has been renamed and simplified from the s non-terminal. Now, instructions can use an arbitrary kind of loc as their operands. The semantics are otherwise unchanged. (set! loc triv) moves the value of triv into loc, and (set! loc_1 (+ loc_1 triv)) adds the values of loc_1 and triv, storing the result in loc_1. Note that the two occurrences of loc_1 in a binary operations are still required to be identical. We’re not trying to lift all restrictions from x64 yet.

We also add the halt instruction, which moves the value of its operand into the current-return-value-register (rax by default). Adding this abstraction frees the user from remembering which register is used for this purpose. This instruction is valid only as the final instruction executed in a program, and it must be present.

Notice that two registers, r10, and r11, have been removed from reg. Para-asm-lang v2 assumes control of these registers, forbidding the programmer from using them directly. Instead, the language implementation will make use of this when compiling to Paren-x64 v2. These auxiliary registers are defined by the parameter current-auxiliary-registers.

Design digression:

If we were trying to support multiple backends, we might parameterize the language further by the set of unrestricted registers. This set would describe the registers that can be used in an arbitrary way by the program, and would exclude the set of current-auxiliary-registers. Each restricted register would have some invariants associated with it, similar to the stack discipline invariant for the current-frame-base-pointer-register.

procedure (patch-instructions p) → paren-x64-fvars-v2?

p : para-asm-lang-v2?

Compiles Para-asm-lang v2 to Paren-x64-fvars v2 by patching instructions that have no x64 analogue into a sequence of instructions. The implementation should use auxiliary registers from current-patch-instructions-registers when generating instruction sequences, and current-return-value-register for compiling halt.

Examples:

> (patch-instructions '(begin (set! rbx 42) (halt rbx)))

'(begin (set! rbx 42) (set! rax rbx))

> (patch-instructions    '(begin       (set! fv0 0)       (set! fv1 42)       (set! fv0 fv1)       (halt fv0)))

'(begin    (set! fv0 0)    (set! fv1 42)    (set! r10 fv1)    (set! fv0 r10)    (set! rax fv0))

> (patch-instructions    '(begin       (set! rbx 0)       (set! rcx 0)       (set! r9 42)       (set! rbx rcx)       (set! rbx (+ rbx r9))       (halt rbx)))

'(begin    (set! rbx 0)    (set! rcx 0)    (set! r9 42)    (set! rbx rcx)    (set! rbx (+ rbx r9))    (set! rax rbx))

1.3.5 Nesting Instruction Sequences

One of the most restrictive limitations in our language is that expressions cannot be nested. Each program must be a linear sequence of instructions.

We can easily lift this restriction by designing a language that supports nesting, and compiling it using our well-known operations for composing instruction sequences. This simplifies the job of later passes that are now free to nest instructions if it’s helpful.

Below, we design Nested-asm-lang-v2 (nested-asm-lang-v2).

We add a tail production which loosely corresponds to the top-level program from Para-asm-lang v2. However, these can be nested, before eventually ending in a halt instruction. The tail production represents the "tail", or last, computation in the program.

We also enable nesting in effect position. This essentially allows us to copy and paste some instruction sequence into the middle of a program.

procedure (flatten-begins p) → para-asm-lang-v2

p : nested-asm-lang-v2

Flatten all nested begin expressions.

1.3.6 Abstracting Physical Locations

We are still required to think about physical locations. We don’t usually care which location a value is stored in, so long as it is stored somewhere.

We can introduce an abstraction to capture this idea. We define an abstract location to be a unique name for some physical location, that is unique for some unit of allocation (for the moment, this means they’re globally unique). Each abstract location must be allocated a physical location somewhere on the machine, and we want to ensure the allocater can replace any two instances of an abstract location with the same physical location.

We define Asm-lang v2 (asm-lang-v2) below. Asm-lang v2 is an imperative, assembly-like language.