Data Flow Analysis (Applications)

overview

How Data Flows on CFG?

​ Flows throw the Nodes(BBs/statements) and Edges(control flows) of CFG(program)

How application-specific Data <- Abstraction

may analysis(for most static analyses):

outputs information that may be true (over-approximation)

must analysis:

outputs information that must be true (under-approximation)

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

Applications

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 the path

Safe-approximation

Algorithm:

Example:

Live Variables Analysis

Live variables analysis tells whether the value of variable v at program point p could be used along some path in CFG starting at p.If so, v is live at p; otherwise, v is dead at p.

Algorithm:

Example:

Available Expressions Analysis

An expression x op y is available at program point p if all paths from the entry to p must pass through the evaluation of x op y, and after the last evaluation of x op y, there is no redefinition of x or y

Algorithm:

Example:

Analysis Comparison