PDG — Program Dependence Graph

Overview

The Program Dependence Graph (PDG) is a fine-grained representation of data and control dependences. It is built on top of the ICFG and is used for slicing, security analyses, and other dependence-aware queries.

  • Location: lib/IR/PDG/, include/IR/PDG/

Core Passes

The PDG infrastructure provides several LLVM passes:

  • DataDependencyGraph – builds def-use, read-after-write (RAW), and alias-based data dependence edges.

  • ControlDependencyGraph – computes control dependences between basic blocks and instructions.

  • ProgramDependencyGraph – combines data and control dependences and exposes a unified query interface.

Unified Query API

The public query layer lives in include/IR/PDG/Analysis/PDGQuery.h and is organized around five service objects:

  • SliceQuery – forward/backward slices, chops, and thin slices

  • DependenceQuery – reachability and shortest-path style queries

  • DataFlowQuery – reaching definitions, liveness, and control-region views

  • TransformQuery – motion legality and scheduling helpers

  • DiffQuery – structural differencing and impact summaries

All services share the same option/result model:

  • PDGQueryOptions – edge preset, scope, context mode, traversal limits, cache policy, and explanation mode

  • PDGQueryScope – whole graph, explicit node set, function, or prior query result

  • PDGQueryResult – nodes, induced edges, predecessor map, witness paths, distances, and diagnostics

  • PDGCriteriaResolver – seeds queries from nodes, LLVM values, function names, callee names, source locations, property specs, and Cypher results

High-Level Usage

PDG is exposed as an LLVM ModulePass. A typical usage pattern:

#include "IR/PDG/Core/ProgramDependencyGraph.h"
using namespace llvm;
using namespace pdg;

legacy::PassManager PM;
PM.add(new DataDependencyGraph());
PM.add(new ControlDependencyGraph());
auto *pdgPass = new ProgramDependencyGraph();
PM.add(pdgPass);
PM.run(module);

ProgramGraph *G = pdgPass->getPDG();
SliceQuery slicer(*G);

PDGCriteria criteria;
criteria.values.push_back(src);

PDGQueryOptions options;
options.edge_preset = PDGEdgePreset::Data;
options.context_mode = PDGContextMode::ContextSensitive;

auto result = slicer.forward(criteria, options, &module);

For interactive querying and slicing, see the ../pdg_query_language and the pdg-query tool described in ../tools/ir.

pdg-query Analysis Mode

pdg-query still accepts raw Cypher queries, but it can now also run the PDG analysis services directly:

  • --analysis slice-forward / slice-backward / chop

  • --analysis shortest-path / reaching-defs / control-region

  • --analysis live / dead / diff

Analysis mode uses Cypher as a selector front end:

  • --criteria-query selects analysis seeds

  • --target-query selects targets for binary analyses

  • --scope-function or --scope-query restrict analysis scope

  • --edge-preset chooses one of all, data, control, parameter, interprocedural, value-flow, or transform-legality

  • --context-sensitive enables call/return matching

  • --thin enables thin slicing semantics

  • --format text|json|dot controls rendering