Memory Management

Overview

Whenever a variable is declared in Acus, the allocator will look for available space in the current stack-frame. From the allocator’s point of view, named locals, compiler temporaries and cache slots are all typed slots inside the current frame. They differ only in who requests them and when they are released.

This allocation can always succeed in the compiler model, because Acus assumes an unbounded Brainfuck tape and therefore allows frames to grow as needed. Frame sizes are only evaluated when the program has been fully defined and algorithms are retroactively adjusted to fit the final configuration. However, slots may also be recycled to keep the frames as tightly packed as possible; this is important to reduce the number of pointer movements. To accomplish this, the management system provides the following features:

1. Freed slots are marked Available and can be reused.

2. Declarations can be scoped to reduce the lifetime of variables. Variable slots will become Available when the variable goes out of scope.

3. Temporary slots declared by the compiler are freed immediately after use.

4. Adjacent Available slots are merged to accommodate larger data types.

5. Available slots will split into smaller parts when a variable with a size smaller than that of the slot is allocated to it.

Relative Offsets

The memory management system assigns each slot an offset relative to the start of its stack-frame. Absolute tape positions are not known at compile-time, because the same function frame may appear at different runtime locations on the tape. The compiler only needs to know the layout of one frame; generated movement algorithms are later adjusted to the final frame size.

Free vs Clear

When a slot is freed, its contents are not cleared. This means that no algorithm may assume that a newly allocated slot contains zero, even if that slot has just been created from previously available space. In particular, the Value fields of a slot must be treated as unknown until explicitly initialized. Freeing a slot is therefore purely a compiler-side bookkeeping operation and does not incur any runtime cost.

Heap Allocation

While technically possible, Acus does not support heap allocation. This would require a separate heap frame and a runtime system that keeps track of the memory layout in that frame (including deallocation, block splitting and block merging). The runtime overhead that would arise from managing the heap at runtime would be so costly that it was decided not to implement this as a feature. However, a front-end might emulate heap allocation using the global frame. One could certainly write algorithms on top of Acus to reserve a specific amount of raw data in the global frame and manage it using existing features.

Splitting and Merging

Slot Splitting

When a variable of type T is allocated, Acus looks for the first slot that is marked Available and is of size $\ge$ the size of T (first fit strategy, [11]). If the sizes match perfectly, the process ends here. If the available slot’s size exceeds the variable size, the remaining part of the slot is split off into its own available slot (Figure 49). If no available slots can be found at all, a new slot is allocated at the end of the current frame (increasing the eventual frame-size).

Slot Merging

Named local variables live until the end of their lexical scope. Temporaries usually live only for the duration of one generated algorithm. Cache slots live until their cache entries are flushed, invalidated, or discarded at a boundary. All three are returned to the same pool of available slots. In each of these scenarios, the slot is marked Available by the memory management system and can be used to accommodate other data. Often, this will result in adjacent Available slots, which can be merged as shown in Figure 50.