Aliasing and Pointer Analysis

Memory objects and pointers are among the most consequential aspects of compiler optimization for imperative languages that involve memory allocation, such as C, C++, and Java.

Memory Objects

Consider a variable declaration in C:

int x;

This declaration allocates a region of memory starting at some address addr. Assuming that the size of an integer is four bytes on our machine, the region spans [addr, addr+4), i.e., the four bytes at addr, addr+1, addr+2, and addr+3. The address of x (&x) points to the beginning of this region, i.e., &x and addr are the same value. Such a region of memory is called an object.

Similarly, a dynamic allocation using the new construct:

p = new X;

allocates a new memory object spanning [addr, addr+sizeof(X)) and returns a pointer p to the beginning of this region, i.e., p and addr are the same value.

An object need not be a contiguous region of memory. e.g., if X is a compound type (a class or a struct), p may point to the root node of a data structure that itself contains pointers to other regions; collectively, all these regions may be considered a single object. Thus, an object is a region, or a set of regions, of memory.

Aliasing

Let x represent an object of four bytes spanning [addr, addr+4), and let p point to a single byte within this region, say addr+1:

int x;
char *p = (char *)&x + 1;

Here, &x points to the object, and the object itself is x, which represents a region of four bytes. Similarly, p points to an object, and the object itself is *p, which represents a region of one byte (the size is determined by the type of p).

In this example, *p and x alias, because the regions of memory represented by them overlap (i.e., their intersection is non-empty). This definition applies to both contiguous and non-contiguous objects.

Aliasing: Two or more names for the same region of memory. In the example above, the byte at addr+1 has two names: one is derived from the variable x (e.g., *((char *)&x + 1)), and the other is *p. *p and x alias iff the memory regions named by them overlap.

Terminology subtlety: we talk about aliasing of objects, not pointers. If pointers p1 and p2 point to the same object, we say that *p1 and *p2 alias; we do not say that p1 and p2 alias. Similarly, in the example above, we say that *p aliases with x; we do not say that p aliases with &x. Notice that p1 is just an address, whereas *p1 represents a region of memory: it encodes both the start address and the size of the region (determined by the type of p1), and, for a non-contiguous object, all the regions that constitute that object. Two objects alias if their regions overlap. It is a common mistake to talk about aliasing of pointers; whenever we say aliasing, we are talking about aliasing of objects.

Why Aliasing Matters

Consider the following program:

x = new X;
x.f = 42;
y = x.f;
assert(y == 42);

A standard dataflow analysis can confirm that the assertion always holds, i.e., y is always equal to 42.

Now consider another program where p is computed through some complicated function of x (or of &x), such that *p may alias with *x:

x = new X;
p = ...;      // some complicated computation
x.f = 42;
p.f = 0;
y = x.f;
assert(y == 42);    // ?

Is it okay to assert y == 42? No: if *p aliases with *x, then y is 0; otherwise, y is 42. We say that p.f and x.f may alias. Unless the compiler can establish that *p and *x do not alias, it must make the conservative assumption that they may alias. e.g., while constant propagation can replace all subsequent uses of y with 42 in the first program, it cannot do so in the second program.

Thus, because of aliasing, many compiler analyses that would otherwise be straightforward become more complicated. For this reason, it is important for a compiler to perform alias analysis to identify, in a best-effort way, as many non-aliasing relationships as possible. e.g., a robust compiler should be able to determine that *p never aliases with *x, if that is indeed true for the program. This falls under the umbrella of pointer analysis in a compiler.

Now consider a third program, where p is directly assigned x:

x = new X;
p = x;
x.f = 42;
p.f = 0;
y = x.f;
assert(y == 0);

Is it okay to assert y == 0? Yes: here, we are sure that p and x point to the same object, i.e., *p and *x definitely alias (in fact, they fully overlap and represent the same object). Thus, the write to p.f is also a write to x.f, and reading x.f into y is guaranteed to yield 0. For the compiler to reason that y == 0 (e.g., for constant propagation), it needs to know that p.f and x.f definitely alias. We say that p.f and x.f must alias.

May-Alias and Must-Alias Analyses

May-alias: can two objects (e.g., *p and *x) potentially alias?
Must-alias: do two objects definitely alias?

Both problems are undecidable in general, and so we can only hope for a best-effort analysis.

Soundness:

A sound may-alias analysis captures all pairs that may alias at runtime, but may also include some spurious pairs that never alias at runtime. It is always safe to say that two objects may alias if we are not sure. e.g., in the program below, *x and *y clearly do not alias, because the language semantics ensure that the two allocations do not overlap:
```
x = new X;
y = new X;
```
But an imprecise may-alias analysis may include the pair (*x, *y) in its may-alias set; this is sound but imprecise. An unsound may-alias analysis would incorrectly claim that two objects do not alias even though they may alias at runtime.
A sound must-alias analysis may miss some pairs that must alias, but every pair that it captures definitely aliases at runtime. e.g., in the program below, *x and *y must alias:
```
x = new X;
y = x;
```
But an imprecise must-alias analysis may not include the pair (*x, *y) in its must-alias set; this is sound but imprecise. An unsound must-alias analysis would include wrong entries in the must-alias set.

Trivial solutions: "everything may alias with everything else" is a sound may-alias solution; "nothing must alias with anything else" is a sound must-alias solution. Both are sound but completely imprecise (and hence useless).

In a compiler, we never compromise soundness, because an unsound analysis may cause the compiler to perform incorrect optimizations. Since the problem is undecidable, we cannot hope for a fully precise analysis, but we want as high a precision as possible:

For may-alias, we want to minimize the number of spurious pairs.
For must-alias, we want to minimize the number of missing pairs.

As is common in compilers, there is a trade-off between running time and precision: some algorithms are fast but imprecise; if an application cares more about precision and can afford a longer running time, then slower and more precise algorithms may be used.

Examples: Importance of Alias Analysis

memcpy: The C library function memcpy(dst, src, n) copies n bytes from [src, src+n) to [dst, dst+n). A basic implementation is:

void *memcpy(char *dst, char *src, size_t n) {
  for (size_t i = 0; i < n; i++) {
    dst[i] = src[i];
  }
  return dst;
}

memcpy is one of the most commonly used and performance-critical functions in the software stack. Real implementations are typically hundreds of lines of code, involving vectorization (e.g., copying four or eight bytes at a time) and specialized code for special cases. But if the regions [src, src+n) and [dst, dst+n) overlap (alias), such optimizations may become incorrect: e.g., copying a chunk of bytes in one go may read bytes that should have already been overwritten through dst. To avoid a slow implementation just because of this corner case, the C library designers specify that the source and destination regions must not overlap: it is undefined behaviour to call memcpy with overlapping regions. This example shows how aliasing pervades the systems stack, not just within a compiler but also in library design.

Accumulating an array:

void accumulate(int *a, int n, int *sum) {
  for (int i = 0; i < n; i++) {
    *sum += a[i];
  }
}

This loop can be made much faster than the naive implementation, e.g., by register-allocating *sum (and writing it back to memory only at the very end), and by vectorizing the loop (reading eight values of a at once and summing them using vector instructions). But these optimizations are legal only if *sum cannot alias with any a[i]. In the absence of other information, the compiler is forced to make the conservative assumption that *sum may alias with a[i], in which case all these optimizations are illegal. This shows how much difference good may-alias information can make to compiler optimization.

Basic Rules for May-Alias

Two separately declared variables x and y do not alias: by the language semantics, two distinct declarations are given distinct (non-overlapping) regions of memory.
For two separate allocations x = new ... and y = new ..., *x and *y do not alias, i.e., (*x, *y) does not belong to the may-alias set.

Such rules form the basis of the transfer functions used to develop a pointer analysis. We discuss how pointer analyses are implemented in subsequent modules.

Points-To Information

One way of determining which objects may alias is through points-to information: for each pointer, we want to determine the set of memory objects that it may point to. e.g., p1 may point to one of the objects o₁, o₂, ..., o_k1, and p2 may point to one of the objects q₁, q₂, ..., q_k2. This information is computed by a points-to analysis.

For example, consider the statements:

p = &x;
x = &y;

From the first statement, we know that p may point to the object x; from the second, that x may point to y. Thus, the points-to relation is p --> x --> y. In other words, the objects in the points-to sets may themselves appear on the left-hand side of the points-to relation (e.g., x is both pointed to, and may point to other objects). Also, the points-to sets of different pointers may overlap (have a non-empty intersection).

Approximating may-alias using points-to sets: May-alias information is among the most important information that a compiler needs to perform transformations (as seen in the memcpy and accumulate examples). A typical approach in compilers is to first compute, for each pointer, the set of all objects that it may point to. Let pointsTo(p) denote this set. Then:

*p1 and *p2 may alias  iff  pointsTo(p1) ∩ pointsTo(p2) ≠ {}

This is a sound approximation of may-alias information, assuming that the points-to sets are sound (i.e., pointsTo(p) includes all the objects that p may potentially point to at runtime). The only pairs left out of the may-alias set are those whose points-to sets are disjoint, i.e., the pointers point to distinct objects; such pairs definitely cannot alias.

Abstract Objects for Pointer Analysis

A points-to analysis identifies all the objects that a pointer may point to (and objects may, in turn, point to other objects). However, the number of objects created dynamically by a program may be unbounded. Consider the following program that creates a linked list of k nodes:

struct LNode {
  int v;
  LNode *next;
};

LNode *createList(int k) {
  LNode *head = nullptr;
  for (int i = 0; i < k; i++) {
    LNode *n = new LNode;
    n->v = i;
    n->next = head;
    head = n;
  }
  return head;
}

The number of times the allocation new LNode executes depends on the number of loop iterations, which in turn depends on the parameter k. In general, a program may have arbitrary logic preceding an allocation, and it is undecidable to determine how many times a loop executes; hence it is undecidable to determine the total number of objects that a program may create at runtime.

The actual (runtime) points-to graph for this program is:

head --> o_k --next--> o_k-1 --next--> ... --next--> o₁ --next--> null

i.e., head points to the most recently allocated object, whose next pointer points to the second most recently allocated object, and so on, until the oldest object whose next pointer is null. The number of objects in this graph is unknown at compile time. This picture can be drawn at runtime, but at compile time we do not know its size or shape. A compile-time analysis needs to reason about a bounded number of objects.

Abstract Objects

An abstract object represents a set of runtime objects. e.g., all the runtime objects created for a linked list may be represented by a single abstract object. The set of runtime objects represented by an abstract object may have a bounded size (known at compile time) or an unbounded size.

We partition the runtime objects created by the program into abstract objects. e.g., all the objects of the linked list may form one abstract object, all the objects of a binary search tree may form another, and so on.
For a compile-time analysis to work, the set of abstract objects must be finite. Whatever scheme we use to partition runtime objects into abstract objects must ensure this.
Corollary: a single abstract object may represent an unbounded number of runtime objects (because a finite number of abstract objects must together represent a potentially unbounded number of runtime objects).

Any partition of runtime objects is a valid choice of abstract objects, as long as the set of abstract objects is finite. We discuss three ideas below; some of them are popular because they are practically useful on real programs.

In a points-to graph over abstract objects, an edge from A to B means that a value stored in (some runtime object represented by) A may be a pointer to (some runtime object represented by) B. An edge from a variable p to A means that p may point to an object represented by A. The fewer the edges (while remaining sound), the more precise the analysis.

Recency Abstraction

In the linked-list example, we reasoned about objects in terms of the time of their creation: the most recently allocated object, the second most recently allocated object, and so on. The recency abstraction partitions runtime objects based on their time of creation. Given parameters n and finite numbers k₁, k₂, ..., k_n, at any point in the program execution:

For i in 1..n, abstract object A_i represents the last k_i runtime objects created before the ∑_j=1^i-1 k_j objects represented by A₁, ..., A_i-1. e.g., A₁ represents the last k₁ allocations; A₂ represents the k₂ allocations before those; and so on.
A_last represents all runtime objects created before the last ∑_j=1ⁿ k_j allocations.

                                                    program execution timeline --->
| ...... A_last ...... | k_n allocs: A_n | ... | k₂ allocs: A₂ | k₁ allocs: A₁ |  <-- now

Each of A₁, ..., A_n represents a finite number of runtime objects, but A_last represents a potentially unbounded number of runtime objects.

Example: For createList, let n = 2 and k₁ = k₂ = 1, i.e., we track the most recently allocated object (A₁), the second most recently allocated object (A₂), and all the objects allocated before these two (A_last). Since the set of abstract objects is finite and known at compile time, we can draw the complete points-to graph. The best answer that an analysis could produce at the end of the program is:

head --> A₁ --next--> A₂ --next--> A_last --next--> A_last

i.e., head points to the most recently allocated object, which points to the second most recently allocated object, which points to an object in A_last, which (through its next pointer) may point to another object in A_last.

Abstraction makes the problem tractable but loses information. e.g., the self-edge on A_last suggests that an object in A_last may point to itself, whereas in the original program, no list node points to itself. Because A_last represents multiple runtime objects, the edge from A_last to A_last conflates "points to another object in A_last" with "points to itself".

Weakness of the recency abstraction: Now suppose that the program also has a function createTree that, depending on some parameter, creates a tree with zero, one, two, or more nodes:

main() {
  head = createList(...);
  root = createTree(...);
}

At compile time, we cannot predict how many allocations createTree makes. So, at the end of main:

If createTree made no allocations, head points to A₁.
If createTree made exactly one allocation, head points to A₂.
If createTree made more than one allocation, head points to A_last.

So the analysis must conservatively determine that head may point to A₁, A₂, or A_last. Perhaps the analysis can determine that the last node allocated by createTree is the root, so that root points to A₁ (if it points to anything at all). Similarly, the edges between A₁, A₂, and A_last become imprecise: A₁, A₂, and A_last may each represent list nodes or tree nodes. This points-to graph is much less satisfactory: the structure of the data structures is lost, and it seems that head (and each abstract object) may point almost anywhere; e.g., *head and *root may alias, as both may point to A₁.

In general, if it is not possible to determine how many allocations happen in a program fragment, we must conservatively assume that any number of allocations may happen in that fragment, and this causes spurious edges in the points-to graph.

Type Abstraction

Group runtime objects into abstract objects based on the type of the allocation. e.g., all objects of type LNode are represented by the abstract object LNode, and all objects of type TNode (tree nodes allocated by createTree) are represented by the abstract object TNode. The points-to graph for main becomes:

head --> LNode --next--> LNode
root --> TNode --left/right--> TNode

This is much better than the recency abstraction: head never points to a TNode; root never points to an LNode; an LNode never points to a TNode, and vice versa. In particular, *head and *root do not alias.

Weakness of the type abstraction: Consider the following program (the statements are labeled by their PC, which we use later). Assume that Z is a type derived from Y (so that z, declared of type Y*, may point to either):

1: x = new X;
2: y = new Y;
3: x.f = y;
4: z = new Y;
5: z.g = x;
6: z.f = y;
7: z = new Z;

In this discussion, we ignore the order of statements (i.e., the analysis is flow-insensitive): we keep adding edges until a fixed point is reached. We build the points-to graph under the type abstraction, where the abstract objects are X, Y, and Z:

Statements 1 and 2: x --> X and y --> Y.
Statement 3 (x.f = y): an object in X may contain (in field f) a pointer to an object in Y: X --> Y. (The field names are not shown in the points-to graph.)
Statement 4: z --> Y. Imprecision already: both y and z point to Y, so *y and *z may alias, whereas the program never assigns the pointer held in y to z.
Statement 7: z --> Z.
Statement 5 (z.g = x): whatever z points to (Y or Z) may contain a pointer to whatever x points to (X): Y --> X and Z --> X. The edge Y --> X is spurious: it suggests that X may be reachable through y, whereas in the program it is reachable only through z.
Statement 6 (z.f = y): Y --> Y and Z --> Y. Again, the self-edge on Y is spurious.

x --> X          X --> Y
y --> Y          Y --> X, Y
z --> Y, Z       Z --> X, Y

Many spurious edges are added due to the type abstraction.

Allocation-Site Abstraction

Label each statement in the program with its PC. All runtime objects allocated at the same allocation site (the PC of the allocation statement) are represented by one abstract object, named by that PC. Notice that statements 2 and 4 in the program above allocate objects of the same type Y, but they are different allocation sites, and so give rise to different abstract objects (2 and 4). For the same program:

Statements 1 and 2: x --> 1 and y --> 2.
Statement 3 (x.f = y): 1 --> 2.
Statement 4: z --> 4. This is where the precision improves: under the type abstraction, y and z both pointed to Y; now y points to 2 and z points to 4, so *y and *z cannot alias.
Statement 5 (z.g = x): 4 --> 1.
Statement 6 (z.f = y): 4 --> 2.
Statement 7: z --> 7. Now that z may also point to 7, statements 5 and 6 must be reconsidered (we iterate to a fixed point, as in a dataflow analysis): 7 --> 1 and 7 --> 2.

x --> 1          1 --> 2
y --> 2          4 --> 1, 2
z --> 4, 7       7 --> 1, 2

We will see an algorithm to compute such points-to graphs automatically later; here, we are primarily interested in the different abstractions and their trade-offs. The number of edges in the two graphs cannot be directly compared (the number of abstract objects differs), but fewer aliasing relationships are possible in the allocation-site graph than in the type-abstraction graph: e.g., *y and *z cannot alias under the allocation-site abstraction, but may alias under the type abstraction.

The list and tree example: With the allocation-site abstraction, there is one allocation site in createList (say, site 1, allocating LNode) and one in createTree (say, site 2, allocating TNode):

head --> 1 --next--> 1
root --> 2 --left/right--> 2

This allows us to rule out many points-to and aliasing relationships, and works well for this example, unlike the recency abstraction.

Weakness of the allocation-site abstraction: Suppose createList is called twice:

main() {
  head  = createList(...);
  head2 = createList(...);
  root  = createTree(...);
}

Both lists are allocated at the same allocation site (site 1), so:

head  --> 1 --next--> 1
head2 --> 1
root  --> 2 --left/right--> 2

This is still better than the recency abstraction, but it is imprecise: it implies that *head may alias with *head2, whereas the code shows that this is not the case. We will see ways to reduce such imprecision later.

Combining Abstractions

Multiple abstractions can be combined. e.g., if a recency abstraction creates abstract objects A₁, ..., A_n and an allocation-site abstraction creates abstract objects B₁, ..., B_m, we can use their Cartesian product (n × m abstract objects) to potentially obtain more precision than either abstraction alone. Any abstraction is acceptable as long as the total number of abstract objects is finite. However, there is a trade-off: Cartesian products can quickly make the number of abstract objects exponential; more abstract objects may give better precision, but at the cost of a higher running time of the points-to analysis.