5.10 Data types: Structured Data and Heap Allocation

5.10.1 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. 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 (pronounced em ops), we need to expose additional features from x64.

5.10.2 Exposing Heap Pointers in the Back-end

5.10.2.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 pointed to by a 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-base-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 might abstract 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.

For a quick introduction to garbage collection, see this short video https://twitter.com/TartanLlama/status/1296413612907663361?s=20.

5.10.2.2 Em-Ops: Abstracting Memory Operations

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

Below, we define Paren-x64-mops v8, with differences compared to Paren-x64-v8.

Next we design Para-asm-lang v8. Below, we give a definition.

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.

In patch-instructions, we also lift the restriction on index, so int64s can appear as an index. This makes index and opand coincide, syntactically, but they are conceptually different so we maintain separate non-terminal definitions.

5.10.2.3 Exposing mops up the pipeline

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

Exercise 9: Redesign and extend the implementation of

• flatten-program, should require no changes

• resolve-predicates, 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.

• optimize-predicates, could require minor changes.

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

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

• assign-registers, should require no changes.

• allocate-frames, should require no changes.

• assign-call-undead-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.

5.10.2.4 Implementing Allocation

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 Asm-alloc-lang v8.

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

Below, we design Asm-alloc-lang v8, the source language for this pass. We typeset the differences compared to Asm-pred-lang v7.

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, Asm-pred-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.