-
Notifications
You must be signed in to change notification settings - Fork 36
Data Flow Analysis
New compiler transformations need to understand specific and new code properties related to how data might change through the code. Because of this, designing new data flow analyses is essential to identifying these new code properties. Data flow analysis follows a generic recipe of traversing the control flow graphs to collect information about what might happen at run time.
For each point in a program, a DFA combines information about all possible run time instances of the same program point. Data-flow Value is the set of all possible program states that can be observed at a given program point. Data-flow Analysis computes IN and OUT sets by computing the DFA-specific transfer functions.
A transfer function, f, relates relates the data-flow values before and after and instruction, i.
- In a forward data-flow problem
- OUT[i] = f( IN[i] )
- In a backward data-flow problem
- IN[i] = f( OUT[i] )
The transfer function relies on information that reaches i and transforms the information to propagate the result to the rest of the CFG.
- GEN[i] = data flow value added by i
- KILL[i] = data flow value removed because of i GEN[i] and KILL[i] are DFA-specific and typically independent of the data and control flow.
Implementing a data flow analysis that scales well with the number of instructions takes time and effort. The typical optimizations are DFA-agnostic, therefore a general data-flow engine can be built once and used by many data-flow analyses.