How Data Flows on CFG?

How application-specific Data Flows through Nodes (BBs/stmts) and Edges(control flows) of CFG (a program) ?

may analysis:

outputs information that may be true (over-approximation)

must analysis:

outputs information that must be true (under-approximation)

Over- nad under-approximations are both for safety of analysis

Input and Output States

each execution of an IR statement transforms an input state to a new output state
the input (output) state is associated with the program point before(after) the statement

In each data-flow analysis application, we associate with every program point a data-flow value that represents an abstraction of the set of all possible program states that can be observed for that point.

Another view: Data-flow analysis is to find a solution to a set of safe-approximation-directed constraints on the IN[s]‘s and OUT[s]‘s, for all stmts

constraints based on semantics of stmts (transfer functions)
constraints based on the flows of control

Notations for transfer functions

Forward Analysis

$O U T [s] = f_{s} (I N [s])$

Backward Analysis

$I N [s] = f_{s} (O U T [s])$

Notations for Control Flow’s Constraints

Control flow within a BB

$I N [s_{i + 1}] = O U T [s_{i}], f or a ll i = 1, 2, \dots, n - 1$

Control flow among BBs

$I N [B] = I N [s_{1}] O U T [B] = O U T [s_{n}]$

$O U T [B] = f_{B} (I N [B]), f_{B} = f_{s_{n}} \circ \dots \circ f_{s_{2}} \circ f_{s_{1}}$

$I N [B] = \land_{P a p re d ecessor o f B} O U T [P]$

$I N [B] = f_{B} (O U T [B]), f_{B} = f_{s_{1}} \circ \dots \circ f_{s_{n - 1}} \circ f_{s_{n}}$

$O U T [S] = \land_{S a s u ccessor o f B} I N [S]$

Application

Reaching Definitions Analysis

A definition d at program point p reaches a point q if there is a path from p to q such that d is not “killed” along that path.

For example: lint variable undefined error

Recent Resource

Recent Project

Recent Area

Data Flow Analysis