Chapter 5.5. Data-flow Analysis

Data-flow analysis tracks value flow through MIR locals — copy, move, borrow, field projection, dereference, and function calls. It builds a directed graph per function where nodes are MIR Local variables and edges record how values propagate between them. The module lives at rapx/src/analysis/dataflow/ and the core graph structures are in rapx/src/graphs/dataflow.rs.

Overview

For each function, the analyzer builds a DataflowGraph by visiting every MIR statement and terminator. Each edge in the graph records:

• Source / destination locals
• Edge operation: Copy, Move, Mut (mutable borrow), Immut (shared borrow), Deref, Field(i), Downcast(variant), Index, ConstIndex, Const, SubSlice
• Source location: basic block index and statement index

Each node records the MIR operations that produced its value (NodeOp): Use, Ref, Call(def_id), Cast, BinaryOp, Aggregate(kind), RawPtr, Discriminant, etc.

DataFlowAnalysis Trait

#![allow(unused)]
fn main() {
pub trait DataflowAnalysis: Analysis {
    fn get_fn_dataflow(&self, def_id: DefId) -> Option<DataFlowGraph>;
    fn get_all_dataflow(&self) -> DataFlowGraphMap;
    fn has_flow_between(&self, def_id: DefId, local1: Local, local2: Local) -> bool;
    fn collect_equivalent_locals(&self, def_id: DefId, local: Local) -> HashSet<Local>;
    fn get_fn_arg2ret(&self, def_id: DefId) -> Arg2Ret;
    fn get_all_arg2ret(&self) -> Arg2RetMap;
}
}

• get_fn_dataflow: Returns the full DataFlowGraph for a function.
• has_flow_between: Checks whether a value-flow path exists between two locals, traversing both upside (in-edges) and downside (out-edges) directions.
• collect_equivalent_locals: Finds all locals that are value-equivalent to the given local — traverses upside through Copy/Move/Mut/Immut/Deref edges to find the root, then traverses downside to collect equivalents.
• get_fn_arg2ret / get_all_arg2ret: Returns an IndexVec<Local, bool> mapping each argument to whether a value-flow path connects it to the return value (_0). This is the most commonly used query for downstream analyses.

Quick Usage

cargo rapx analyze dataflow

To enable debug logging and render DOT graphs:

cargo rapx analyze dataflow --debug --draw

In code:

#![allow(unused)]
fn main() {
let mut analyzer = DataflowAnalyzer::new(tcx, false);
analyzer.run();
let arg2ret = analyzer.get_all_arg2ret(); // Arg2RetMap
rap_info!("{}", Arg2RetMapWrapper(arg2ret));
}

Value Flow Graph Construction

DataflowAnalyzer::build_graphs() iterates over all local function definitions (iter_local_def_id) and calls build_graph for each Fn or AssocFn. The graph is built in DataflowGraph::add_statm_to_graph and add_terminator_to_graph by matching on each MIR statement kind:

Assignments (StatementKind::Assign)

For lv = rv:

Place Projections

When the left-hand side contains projections (e.g., (*ptr).field), intermediate nodes are created for each projection step:

• Deref — a new node with a Deref edge from the base pointer
• Field(i) — a new node with a Field(i) edge from the base struct/tuple
• Downcast(variant) — a new node with a Downcast edge from the enum
• Index — a new node with Index and Nop edges from the index operand

Call Terminators (TerminatorKind::Call)

For dst = f(args):

• If f is a known FnDef, each argument is connected to dst with the corresponding edge operation. The node is marked with NodeOp::Call(def_id).
• If f is a dynamic operand (trait object / function pointer), the function operand and arguments are connected to dst, marked NodeOp::CallOperand.

Constants

Constant operands create a synthetic marker node with NodeOp::Const(desc, ty) connected to the destination via a Const edge. This distinguishes constant-origin values from value-flow between program variables.

Graph Queries

DFS Traversal

The dfs method provides directional graph traversal:

#![allow(unused)]
fn main() {
pub fn dfs<F, G>(
    &self,
    now: Local,
    direction: Direction,    // Upside | Downside | Both
    node_operator: &mut F,   // FnMut(&DataflowGraph, Local) -> DFSStatus
    edge_validator: &mut G,  // FnMut(&DataflowGraph, EdgeIdx) -> DFSStatus
    traverse_all: bool,      // continue after finding target?
    seen: &mut HashSet<Local>,
) -> (DFSStatus, bool)
}

The traverse_all flag controls behavior: false stops immediately upon finding a target; true exhaustively visits all reachable nodes allowed by the validators. This is the foundation for is_connected, collect_equivalent_locals, collect_ancestor_locals, and collect_descending_locals.

Param-to-Return Dependencies

param_return_deps() is built on is_connected: for each argument _1.._n, it checks whether a value-flow path exists to _0. The result is IndexVec<Local, bool>.

Equivalent Locals

collect_equivalent_locals() finds all locals that hold the same value as the given local. It works in two phases:

1. Traverse upside through value-preserving edges (Copy, Move, Mut, Immut, Deref) to find the root.
2. Traverse downside from the root through the same edge types, collecting all reachable locals.

Field Sequence

get_field_sequence() traces upside through Field(i) edges to reconstruct the field access path (e.g., _1.0.2), returning the base local and the ordered sequence of field indices.

Example: create_vec

Consider the following function:

#![allow(unused)]
fn main() {
fn create_vec() -> *mut Vec<i32> {
    let mut v = Vec::new();
    v.push(1);
    &mut v as *mut Vec<i32>
}
}

The dataflow graph would show the following value flow:

• Vec::new() returns value into local v (Call edge).
• v.push(1) mutates v in place — &mut v is passed to push, creating a Mut edge from v to the borrow temporary, then to push's return.
• &mut v as *mut Vec<i32> creates a raw pointer — a Mut edge from v to the borrow temporary, a Cast to the raw pointer type, and the result flows to the return value _0.

The param_return_deps query would confirm that no function argument flows to the return value (since there are no parameters), indicating the return value is locally created.

Output Format

The DataFlowGraphWrapper display renders each function's graph as a compact adjacency list:

Function: "my_crate::create_vec"
Node _1 -> Node [_2]
Node _2 -> Node [_3, _4]
Node _3 -> Node [_0]

And Arg2RetWrapper shows argument-to-return dependencies:

Argument _1 ---> Return value _0
Argument _2 ---> Return value _0

Relationship to Other Modules

• Alias Analysis: Dataflow graphs provide value-equivalence information that complements alias relationships.
• SafeDrop: Uses dataflow analysis to determine whether a value flows to a deallocation site.
• Verification: The forward visitor uses def-use chains similar to dataflow's ancestor/descendant queries.

Test Example

The alias analysis test at rapx/tests/alias/alias_01/src/lib.rs demonstrates a simple value-flow scenario:

#![allow(unused)]
fn main() {
fn foo(p: *mut u8) -> Vec<u8, Global> {
    unsafe { Vec::from_raw_parts_in(p, 1, 1, Global) }
}
}

The dataflow graph for foo shows:

• p (argument _1) flows into Vec::from_raw_parts_in via a Move edge.
• The return value of from_raw_parts_in (_0) receives a Call edge from its arguments.
• The param_return_deps query confirms that _1 flows to _0.

This small function exercises all key graph features: argument tracking, call site modeling, and param-to-return dependency detection.