Caching

Slot proxies (Section Slot Proxies and Materialization) allow expressions to remain abstract until their value is needed. However, repeatedly materializing the same proxy can duplicate work. For example, accessing the same array element several times in a block should not require materializing the element locally each time. Instead, multiple accesses can be cached and a writeback occurs only when necessary, for example at control-flow boundaries.

let x: array<u8, 5>
let i: u8
...

let y: u8 = x[i]  # materializes x[i] in a local cache before assigning to y
x[i] = 42         # operates on the same cached value and marks it dirty
x[i] *= 2         # operates directly on the dirty entry
let y: u8 = f(x)  # before passing x to f(), x[i] is written
                  # back to canonical storage

To implement this caching system, dependencies between proxies need to be carefully maintained. During compilation, a dependency graph is built and used to determine which cache entries have become dirty and which ones need to be flushed back into their actual storage location. This chapter will go over the different techniques and compromises that were made in their implementation.

Cache Graphs

A cache entry connects a logical proxy to a concrete slot that currently holds its materialized value. Entries can be marked dirty when modified or invalidated/removed when there is no guarantee that their values still represent the actual referred-to data.

Figure 52 shows a simplified representation of a cache graph, where each entry (node) contains information about the proxy that it represents, the physical location of the cached slot, and its parent and child nodes. A proxy A is considered a parent of proxy B if the canonical storage location of B is a subset of that of A. For example, given the expression x[i][j], the expression x[i] is represented by a proxy that itself will be cached (assuming i is not known at compile time). Therefore, to materialize the element x[i][j], we first need to materialize x[i], and their cache entries are in a parent-child relation: x[i] is the parent of x[i][j] because the storage slot of x[i] encloses that of x[i][j].

In the example of Figure 52, the $3\times 3$ matrix x is indexed by the index variables i, j, k and l through the expressions at the top. The first line causes the left branch of the tree to be generated: in order to materialize x[i][j], its parent x[i] is materialized in a cache slot, which can be generated from the statically known starting address of its parent x (which does not have to be cached). In this example, x[i] is materialized right after its parent x (as can be confirmed from the offsets and size data) but this does not necessarily have to be the case.

The second expression causes a second cache-branch to be generated because the proxies x[i] and x[k] have different proxy-identities (even though they could be referring to the same objects at runtime, when i == k).

Flushing and Invalidation

Dirty Entries

In the example of Figure 52, all entries are clean (i.e. not dirty), since none of the expressions involving them modified their contents. The expression x[i][j] = 3 would have the effect of writing the value 3 to the cache slot and marking its corresponding entry as dirty. Dirty entries must at some point be flushed into their parent to make sure that all changes applied to a cached object eventually propagate into canonical storage.

Flushing

Flushing an entry means writing its contents back into its parent (either another cached slot or canonical storage). An entry needs to be flushed in the following scenarios:

1. The entry is marked dirty and a parent somewhere up in the cache hierarchy is materialized. If the dirty entry is multiple parents removed, this causes all intermediate parents to be flushed as well. For example, if x[i][j] is dirty and x is materialized, the dirty x[i][j] is flushed into x[i], which then becomes dirty and is subsequently flushed into x itself. The entire path from x[i][j] to x is now clean.

2. Whenever a control-flow boundary is crossed. For example, at jumps or function calls, the entire cache is cleared by flushing all entries (starting at the deepest child nodes) back into their canonical storage. This makes sure that all flow paths see the correct data.

3. Whenever a pointer is dereferenced. Because pointers can refer to anything (of some type) at runtime, the entire cache is cleared to make sure that the pointee is up-to-date when fetched by the dereferencing algorithm.

4. Before cache invalidation. In scenarios where a cache entry is invalidated (removed from the tree), it is flushed back before doing so. Cache invalidation is discussed in more detail below.

At a return boundary, local cache entries can be discarded because their frame is about to disappear. Entries referring to storage that outlives the frame, such as globals and dereferenced pointers, must first be flushed. Return values are transferred separately by the return mechanism described earlier.

Invalidation

Entries can be invalidated when an external dependency or (indirect) parent is modified or freed by the memory management system. In the example of Figure 52, the entries x[i] and x[i][j] have been materialized in cache using the value stored in slot i at that time. When the value of i is modified, the proxy refers to a new object and the entry has become invalid. When this is about to happen, the invalidated proxy has to be flushed (if dirty) before modifying the dependency, after which it (and its descendants) can be removed from the cache tree.

Writes

Writing to a proxy will, as mentioned before, cause its cached entry to be marked dirty. When the object is overwritten independently of its original value, there is no need to materialize that value at all. For example, when compiling the expression x[i][j] = 3, the value stored initially in x[i][j] is completely irrelevant. In such cases, a new entry for the proxy x[i][j] is created and marked dirty immediately and no materialization algorithm has to be executed.

Example

The listing below shows a more complete version of code that leads to the cache hierarchy of Figure 52. At the lines marked (a) and (b), the graph from Figure 52 is generated. Then, at line (c), a new value is assigned to x[i][j]. This assignment expression will write the value 3 directly to the already cached slot for the proxy x[i][j] and mark this entry as dirty. At the next expression (line (d)), a new proxy (x[i][k]) is materialized, which shares a parent (x[i]) with the now dirty entry x[i][j]. Therefore, before materializing x[i][k], the dirty entry is flushed upwards into x[i], after which its dirty state is cleared and x[i][k] can be materialized. Finally, at line (e), the value of i is modified. All cache entries that depend on i (the left branch of the graph) therefore need to be invalidated. In this example, these entries have just been flushed and are still clean, so there is no need to flush them prior to deletion.

using Vec3 = array<u8, 3>
using Mat  = array<Vec3, 3>
let x: Mat

# Indices (not known at compile-time)
let i: u8
let j: u8
let k: u8
let l: u8
...

# Materialization and caching
let y: u8 = x[i][j]    # (a)
let z: u8 = x[k][l]    # (b)

# Flushing and invalidating
x[i][j] = 3            # (c)
let q: u8 = x[i][k]    # (d)
i = 0                  # (e)
...