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.
0 comments:
Post a Comment