A Visual Guide to Pointer Analysis with cclyzer++: Part 2

This is the second part of a two-part blog post series that visually illustrates the essence of cclyzer++ by means of examples. You’ll probably want to read part 1 before continuing.

The previous post explained that the goal of pointer analysis is to compute an overapproximation of the points-to relation of a program, which relates program variables and allocations to the sets of allocations they can point to at runtime. All of the examples in that post only showed analysis of a single function. In this installment, we’ll examine how cclyzer++ performs inter-procedural analysis on whole programs. We’ll also see two sources of imprecision for pointer analyses and how cclyzer++ ameliorates them.

Computing the Fixed Point

In part 1, we saw the core rules of a flow-insensitive pointer analysis for LLVM. To compute the points-to relation, pointer analyses apply these rules until they reach a fixed point, that is, until no rule can generate new points-to information. This analysis is guaranteed to reach such a fixed point and terminate, because each rule adds an edge/pair to the points-to relation and the allocation site abstraction guarantees that the points-to relation has a finite maximum size. In the limit, each variable could point to each allocation, but even such an exceedingly large points-to relation would be finite.

Interprocedural Analysis

Consider the following C program and its LLVM translation:

#include <stdlib.h>

void *snd(char *u, int *v) {
  void *w = (void *)v;
  return w;
}

int main() {
  char *x = malloc(sizeof(char));
  int *y = malloc(sizeof(int));
  void *z = snd(x, y);
  return 0;
}

define i8* @snd(i8* %u, i32* %v) {
entry:
    %w = bitcast i32* %v to i8*
    ret i8* %w
}

define i32 @main() {
entry:
    %x = call i8* @malloc(i64 1)
    %y1 = call i8* @malloc(i64 4)
    %y2 = bitcast i8* %y1 to i32*
    %z = call i8* @snd(i8* %x, i32* %y2)
    ret i32 0
}

(Note that LLVM doesn’t distinguish between void pointers and byte pointers, translating both void* and char* as i8*.)

To see what %z might point to, cclyzer++ must reason about the call to @snd. When cclyzer++ analyzes this call, it looks at the arguments to the call and matches them up with the formal parameters of the callee. In this case, %x gets matched with %u and %y2 gets matched with %v. For each argument, the points-to information from the actual argument gets copied to the formal argument. So before the call, the points-to graph looks like this:

Right at the beginning of the execution of @snd, the points to information for %x gets copied to %u, and similarly for %y2 and %v, giving

Then the body of the function (i.e., the bitcast instruction) is analyzed, yielding

Finally, the points-to information for the return value is copied back into the variable that captures the return value of the call. In this example, points-to information is copied from %w to %z.

Context Sensitivity

The interprocedural analysis sketched above loses precision in some cases. Consider the following program:

#include <stdlib.h>

void *id(void *z) {
  return z;
}

int main() {
  char u;
  char v;
  char *x = id(&u);
  char *y = id(&v);
  return 0;
}

define i8* @id(i8* %z) {
entry:
    ret i8* %z
}

define i32 @main() {
entry:
    %u = alloca i8, align 1
    %v = alloca i8, align 1
    %x = call i8* @id(i8* %u)
    %y = call i8* @id(i8* %v)
    ret i32 0
}

After the first call to @id, the points-to graph would look like this:

However, after the second call, %z additionally points to stack@main[%v], which then gets propagated back to %x (and vice versa for stack@main[%u] and %y).

This result is imprecise. At runtime, %x really can only point to the allocation represented by stack@main[%u] and %y can only point to stack@main[%v], but the two get conflated when they both flow through @id. To avoid this issue, cclyzer++ can analyze functions context-sensitively. A context-sensitive analysis analyzes each function once per context. The most common choice of context is the callsite.

Let’s look at this program again, but analyze @id once per context. Contexts are drawn as boxes and labeled with their callsite. Since @main has no callers, its context is just labeled @main. After the first call to @id, the points-to graph would look like this:

Since @id gets analyzed separately in a new context at the second callsite, the parameters and return values don’t get conflated.

While this example program was fairly contrived, context sensitivity turns out to be a crucial technique for pointer analyses to retain precision on realistic programs. cclyzer++ provides several settings for tuning context-sensitivity, including types of contexts other than callsites, and increased context depth (this example showed a context depth of 1).

Field Sensitivity

The analysis described so far loses precision when applied to programs that use structs. Consider the following program:

typedef struct { int *x; int *y; } s;

int main() {
    int u;
    int v;
    s w;
    w.x = &u;
    w.y = &v;
    int *z = w.x;
    return 0;
}

At the LLVM level, a field assignment like w.x = &u (that is, a reference to a field on the left-hand side of an assignment) gets split into two instructions, a getelementptr instruction that calculates the address of the field and a store that stores the value to it. Likewise, a reference to a field on the right-hand side of an assignment turns into a getelementptr followed by a load. The getelementptr instruction looks a bit intimidating, but suffice to say that in this example, the three getelementptr instructions correspond exactly to the three field references in the source program. (See this blog post, some LLVM docs, and the official language reference for more details on getelementptr.)

%struct.s = type { i32*, i32* }

define i32 @main() {
entry:
    %u = alloca i32, align 4
    %v = alloca i32, align 4
    %w = alloca %struct.s, align 8
    %x = getelementptr %struct.s, %struct.s* %w, i32 0, i32 0
    store i32* %u, i32** %x, align 8
    %y = getelementptr %struct.s, %struct.s* %w, i32 0, i32 1
    store i32* %v, i32** %y, align 8
    %x1 = getelementptr %struct.s, %struct.s* %w, i32 0, i32 0
    %z = load i32*, i32** %x1, align 8
    ret i32 0
}

With the field-insensitive analysis described above, the points-to graph would look like this:

The results for %z are imprecise – at runtime, %z can actually only point to stack@main[%u]. To fix this issue, cclyzer++ creates field suballocations for different struct fields. getelementptr instructions return the appropriate field suballocation when applied to a struct-typed allocation. Otherwise, field suballocations act just like normal abstract allocations.

Graphically, a struct-typed allocation is linked to its suballocations with a dotted arrow. The first suballocation of a struct is also linked to its parent by a thick, undirected edge which indicates that they are must-aliases, i.e., everything that one points to is also pointed to by the other. For the sake of presentation, outgoing edges of must-aliases aren’t actually duplicated.

Here’s what the points-to graph would look like just after the stack allocation of %w:

After the rest of the function:

Now, %x1 points to the first field of %w (stack@main[%w].u) instead of all of it, and the result for %z is correspondingly more precise.

There’s an analogous precision issue for programs with arrays, which can be solved in an analogous way with array sensitivity.

An Extended Example

We’re now ready to examine the example that was shown at the beginning of Part 1 of this series. It’s a program that constructs a linked list.

#include <stdlib.h>

typedef struct list list_t;
typedef struct list {
  void *data;
  list_t *next;
} list_t;

list_t *head;

list_t *mk(void *d) {
  list_t *node = malloc(sizeof(node));
  node->data = d;
  node->next = NULL;
  return node;
}

int main(int argc, char *argv[]) {
  int x = 0;
  head = mk(&x);
  list_t *last = head;
  for (int i = 0; i next = new;
    last = new;
  }
  return 0;
}

Now, the LLVM. This example has more conditional control flow using the icmp, br, and phi instructions, but it can be ignored (recall that cclyzer++ is flow-insensitive). It’s big, but we’ll walk through it step by step.

%struct.list = type { i8*, %struct.list* }

@head = global %struct.list* null, align 8

define %struct.list* @mk(i8* %d) {
entry:
  %node1 = call i8* @malloc(i64 8)
  %node2 = bitcast i8* %node1 to %struct.list*
  %data = getelementptr %struct.list, %struct.list* %node2, i32 0, i32 0
  store i8* %d, i8** %data, align 8
  %nx = getelementptr %struct.list, %struct.list* %node2, i32 0, i32 1
  store %struct.list* null, %struct.list** %nx, align 8
  ret %struct.list* %node2
}

define i32 @main(i32 %argc, i8** %argv) {
entry:
  %x1 = alloca i32, align 4
  %iptr1 = alloca i32, align 4
  store i32 0, i32* %x1, align 4
  %x2 = bitcast i32* %x1 to i8*
  %call = call %struct.list* @mk(i8* %x2)
  store %struct.list* %call, %struct.list** @head, align 8
  %head = load %struct.list*, %struct.list** @head, align 8
  store i32 0, i32* %iptr1, align 4
  br label %for.cond

for.cond:
  %last = phi %struct.list* [ %head, %entry ], [ %new, %for.inc ]
  %i1 = load i32, i32* %iptr1, align 4
  %cmp = icmp slt i32 %i1, %argc
  br i1 %cmp, label %for.body, label %for.end

for.body:
  %iptr2 = bitcast i32* %iptr1 to i8*
  %new = call %struct.list* @mk(i8* %iptr2)
  %next = getelementptr %struct.list, %struct.list* %last, i32 0, i32 1
  store %struct.list* %new, %struct.list** %next, align 8
  br label %for.inc

for.inc:
  %i2 = load i32, i32* %iptr1, align 4
  %inc = add i32 %i2, 1
  store i32 %inc, i32* %iptr1, align 4
  br label %for.cond

for.end:
  ret i32 0
}

Let’s start with just the global variable @head, which initially points to null. For the sake of simplicity, the analysis is context-insensitive.

At the first call to @mk, %x2 gets copied to %d:

Then the body of the function executes, creating a new struct-typed heap allocation (with corresponding field suballocations) and initializing it with some data.

The call returns, assigning %node2 to the return value %call. @main stores %call to the global variable @head, and loads to the local variable %head from the global @head, so that it aliases %call.

At the beginning of the for-loop, there’s a phi instruction. In the first iteration of the loop it assigns %head to %last, and on the rest of the iterations it assigns %new to %last.

At the basic block label for.body, %iptr1 is cast to an i32* and then passed to @mk. Due to the allocation site abstraction and context insensitivity, this only results in minor updates to the points-to facts in the body of @mk. In particular, the writes to heap@mk[%node1].data are combined, even though at runtime they happen to different concrete allocations. This imprecision would be avoided with a 1-callsite-sensitive analysis with a 1-callsite-sensitive heap.

After @mk returns, the freshly-allocated link %new is stored to the next field of %last. This results in a sort of cycle in the points-to graph, where heap@mk[%node1].next points to heap@mk[%node1]. This demonstrates two ways that the context-insensitive allocation site abstraction loses precision on this program:

1. It loses information about the length of the linked list, which must be of length >1 at this point in the program.
2. It doesn’t rule out this program constructing a circular list.

When returning to the head of the loop, no additional points-to facts are computed because %head and %new point to the same abstract allocation. The for.inc block has no effect on the points-to graph, so we’ve computed the fixed point and we’re done! Phew!