Pointer analysis is an important topic in compiler optimization. One interesting aspect is the dynamic scope of pointers. LLVM differentiates between two situations:

  • Pointer Capture: A pointer value is captured if the function makes a copy of any part of the pointer that outlives the call.
  • Pointer Escape: A pointer value escapes if it is is accessible from outside the current function or thread. The latter case is sometimes considered separate and called thread-escape.

Although the names seem to suggest that these two are opposites, it should be clear from their definition that they are not. Informally, escaping is concerned with the contents of the pointer, while capturing is concerned with the pointer itself[^1].

In languages like C and C++, a pointer that escapes is always captured because there is no way to refer to an object without being able to determine its address. The opposite doesn’t hold: a pointer can be captured without escaping.

The function below returns whether a given pointer p is is aligned on a 16-byte boundary. This function captures p but does not cause its value to escape.

int f(void* p) {
  return ((unsigned long)p & 15) == 0;
}

The goal of knowing whether a pointer is captured or escaped, is providing the compiler to correctly change the address or content respectively of a pointer.

Capture Tracking in LLVM

LLVM contains code to determine whether a given pointer is captured. It provides two APIs: PointerMayBeCaptured and PointerMayBeCapturedBefore. The latter takes a dominator tree as additional argument and only considers captures before the given instruction.

Algorithm

The meat and potatoes of the capture tracker is fairly simple: it uses a fixed-point algorithm, driven by a worklist.

The worklist is initially filled with al the uses of the given pointer value. The main loop considers each instruction in the worklist and halts when the worklist is empty. Based on the opcode (and sometimes a property of the instruction) the algorithm determines whether the current instruction causes the pointer to be captured.

For example, if the pointer is used by a load-instruction and it is volatile, the pointer is said to be captured because volatile loads make the address observable.

False Positives

Like most compiler algorithms, the capture tracking algorithm is conservative. If there’s any doubt that a pointer might be captured, it is said to be. This is of course intentional and a good thing: from a compiler perspective a false positive merely means a potential missed opportunity for optimization, while a false negative can make the result incorrect.

The store-instruction is one example of a false negative returned by the current implementation. Even though the API suggests otherwise, with the current implementation each store-instruction is considered to capture a pointer[^2].

Applications

LLVM uses information about captures throughout different analyses and optimizations:

  • Function inlining: to add alias scopes metadata for each original noalias argument to the inlined function.
  • Stateless alias analysis (Basic AA): to determine whether a pointer is pointing tot a function-local object.
  • Dead store elimination: to find dead heap objects.
  • Loop invariant code motion (LICM): to hoist a load if it’s thread-local.

I wrote this blog post because I had been looking to improve the behavior of capture tracking in combination with store instructions. More specifically, I wanted only stores to globals or function arguments to be considered as capturing. While the idea makes sense it theory, it turned out harder than expected to realize because it relies on knowing that two pointer never alias, an uncomputable problem[^3].