Dataflow Analysis
- By the end of this topic, you will be able to:
- Define the concept of global optimization
- Explain dataflow analysis
- Describe dataflow equations
- Illustrate basic blocks and flow graphs
- Describe copy propagation
- Identify common subexpression elimination
- Explain induction variable elements
Introduction to the Dataflow Analysis:
Dataflow Analysis refers to a set of techniques that obtain
information on the flow of data along program execution paths
For example, one way to implement global common subexpression
elimination is to find out if two textually similar expressions evaluate to
same value along any possible execution path of the program
Consider another example wherein if the result of an
assignment is not used along any subsequent execution path, then the assignment
can be eliminated as a dead code. These and many other important questions can
be answered by dataflow analysis.
Global Optimization:
The global optimization is applied over a broad scope like
procedure or function body, whereas the local optimization has a very
restricted scope
In regards to a global optimization, the representation of a
program is in the form of a program flow graph
The program flow graph is a graphical representation, in
which each node represents the basic block and edges represent the flow of
control from on block to another block
There are two types
of analysis performed for global optimizations:
Control Flow
Analysis
Dataflow
Analysis
Control Flow Analysis:
The information about arrangement of graph nodes(basic
blocks), presence of loops, nesting of loops, nodes visited before execution of
specific node, is ascertained by the control flow analysis
Optimization
can be carried out with the help of this analytical information
Hence, in case of control flow analysis, the analysis is
performed on the flow of control by carefully examining the program flow graph
Dataflow Analysis:
In Dataflow Analysis, the analysis is performed on the flow
of data
With the help of Dataflow Analysis, information regarding
the definition and use of the data in the program is obtained
Optimization
can be obtained with the help of this kind of analysis
Basically, Dataflow Analysis is a process in which the
computation of values is done, with respect to dataflow properties.
Home
|
