Department of Computer Science & Engineering
UIT-RGPV
Topic: Data Flow Analysis
Course: Compiler Design (CS701)
By:
Mr. Praveen Yadav
Assistant Professor
DoCSE, UIT-RGPV
Bhopal
Data Flow Analysis
• All the machine independent optimizations depend on data-flow
analysis.
• “Data-Flow analysis" refers to a body of techniques that derive
information about the flow of data along program execution
paths.
OR
• Data-flow analysis is a technique for gathering information about
the possible set of values calculated at various points in
a computer program.
• A program's control flow graph (CFG) is used to determine those
parts of a program to which a particular value assigned to a
variable might propagate.
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 2
Data Flow Analysis
• The information gathered is often used by compiler when
optimizing a program.
• A canonical example of a data-flow analysis is reaching
definitions.
• A simple way to perform data-flow analysis of programs is to set
up data-flow equations for each node of the control flow graph
and solve them by repeatedly calculating the output from the
input locally at each node until the whole system stabilizes
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 3
Basic principles
• Data-flow analysis is the process of collecting information about
the way the variables are used, defined in the program.
• It attempts to obtain particular information at each point in a
procedure.
• Data Flow Equation for statement:
Out[S] = Gen[S] U ( In[S] – Kill[S] )
The information at the end of a statement is either generated
within the statement or enters at the beginning and is not killed as
control flows through the statement.
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 4
Basic principles cont…
• Usually, it is enough to obtain this information at the boundaries
of basic blocks, since from that it is easy to compute the
information at points in the basic block.
• In forward flow analysis, the exit state of a block is a function of
the block's entry state. This function is the composition of the
effects of the statements in the block.
• The entry state of a block is a function of the exit states of its
predecessors.
• This yields a set of data-flow equations.
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 5
Basic principles cont…
• For each block B:
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 6
Basic Terminologies
• Definition Point: a point in a program containing some definition.
• Reference Point: a point in a program containing a reference to a
data item.
• Evaluation Point: a point in a program containing evaluation of
expression.
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 7
Data Flow Properties
1. Available Expression – A expression is said to be available at a
program point x iff along paths its reaching to x. A Expression is
available at its evaluation point.
A expression a+b is said to be available if none of the operands
gets modified before their use.
• Advantage: It is used to eliminate common sub expressions.
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 8
Available Expression Example
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 9
Available Expression Example cont…
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 10
Data Flow Properties cont…
2. Reaching Definition – A definition D is reaches a point x if there
is path from D to x in which D is not killed, i.e., not redefined.
Example:
Advantage: It is used in constant and variable propagation.
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 11
Reaching Definition Example
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 12
Data Flow Properties cont…
3. Live variable – A variable is said to be live at some point p if
from p to end the variable is used before it is redefined else it
becomes dead.
Example:
Advantage:
• It is useful for register allocation.
• It is used in dead code elimination.
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 13
Live Variable Analysis
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 14
Algorithm for Live Variable Analysis
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 15
Live Variable Analysis: Example
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 16
Data Flow Properties cont…
4. Busy Expression: An expression is busy along a path iff its
evaluation exists along that path and none of its operand definition
exists before its evaluation along the path.
• It is used for performing code hoisting/movement optimization and
partial redundancy elimination.
• Example: Here expression “B op C” is an busy expression.
• Code Hoisting: variables and function declarations are moved to
the top of their scope before code execution.
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 17
Thank You
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 18
