DyckAA — Dyck-CFL Analysis

Overview

DyckAA is a high-precision, unification-based alias analysis that uses Dyck Context-Free Language (CFL) reachability to model pointer relationships. It is designed for maximum precision and is well suited to function-pointer resolution and detailed value-flow reasoning.

  • Location: lib/Alias/DyckAA

  • Context: Context-insensitive

  • Precision: Field-sensitive, CFL-based alias sets

Core Idea

DyckAA builds a Dyck graph whose edges are labeled with operations that behave like balanced parentheses:

  • (* / *) — dereference and reference

  • [field / field] — field access and projection

  • Assignment and copy edges

Alias relationships correspond to balanced paths in this labeled graph. The Dyck-CFL reachability algorithm discovers such paths and unifies equivalent nodes into alias sets.

Algorithm

The analysis uses Dyck Context-Free Language (CFL) reachability to model pointer relationships:

LLVM IR
   ↓
[Build Dyck Graph]
   ├─ Nodes: Values (pointers, objects)
   ├─ Edges with labels:
   │  ├─ *(* : Dereference
   │  ├─ *)* : Reference
   │  ├─ *[field]* : Field access
   │  └─ Assignment edges
   ↓
[Dyck-CFL Reachability]
   ├─ Find balanced paths
   ├─ Unify equivalent nodes
   └─ Build alias sets
   ↓
[Applications]
   ├─ Alias queries
   ├─ Call graph construction
   ├─ ModRef analysis
   └─ Value flow analysis

Dyck Language

Balanced parentheses language that captures pointer semantics:

  • ( ... ) : Dereference operations must balance

  • [ ... ] : Field accesses must match

  • Paths between nodes indicate aliasing

Example

int x;
int *p = &x;    // Edge: p -*)->* x
int **q = &p;   // Edge: q -*)->* p
int *r = *q;    // Path: r = *q, q points to p, so r = p
                // Dyck path: r -*(*-* q -*)->* p

Capabilities

DyckAA provides:

  • Precise alias queries (may/must sets).

  • Construction of call graphs for indirect calls.

  • ModRef information (modified/referenced memory).

  • Value-flow graphs (DyckVFG) for downstream analyses.

Strengths

  • Highly precise through CFL reachability

  • Handles complex pointer patterns

  • Good for function pointer resolution

  • Builds precise call graphs

Limitations

  • Computationally expensive

  • High memory usage for large programs

  • Context-insensitive (single analysis per function)

Usage

DyckAA is typically run via its dedicated tool:

./build/bin/dyck-aa -print-alias-set-info example.bc

Available Options

  • -print-alias-set-info

    Prints the evaluation of alias sets and outputs all alias sets and their relations (DOT format).

  • -count-fp

    Counts how many functions a function pointer may point to.

  • -no-function-type-check

    If set, disables function type checking when resolving pointer calls. Otherwise, only FuncTy-compatible functions can be aliased with a function pointer. Two functions f1 and f2 are FuncTy-compatible if:

    • Both or neither are variadic functions

    • Both or neither have a non-void return value

    • They have the same number of parameters

    • Parameters have the same FuncTy store sizes

    • There is an explicit cast operation between FuncTy(f1) and FuncTy(f2) (works with -with-function-cast-comb option)

  • -dot-dyck-callgraph

    Prints a call graph based on the alias analysis. Can be used with -with-labels option to add labels (call instructions) to the edges in call graphs.

Additional flags enable call graph export, function pointer statistics, and DOT visualizations of internal graphs.

Advanced Features

  • DyckVFG: Value Flow Graph construction for tracking value propagation

  • ModRef Analysis: Modified/Referenced analysis for optimization

  • Call Graph: Precise indirect call resolution