Optimization: Introduction and Control Flow Analysis
Introduction
Data flow analysis provides information regarding the definition and use of data items. It provides the following information (among other): (1) paths along which a reference to a data item is not preceded by a definition and (2) detection of redundant or useless code. As the diagram above shows, we approach data flow analysis in two ways. The first, a low-level approach, is from a compiler phase perspective, using the control flow graph intermediate representation developed in Chapter 8. The second, a high-level approach, is to evaluate attributes on the abstract syntax tree.
Example 1 shows some problems which may be exposed by data flow analysis.
EXAMPLE 1
(1)
x := 3 (unused definition)
x := 2
(2)
x := 3 (useless assignment)
(no ... := x)
(3)
A := 3 (identical variables)
B := 3
In addition to those shown in Example 1, loop invariant variables may be detected, expressions which have already been computed may be detected, etc.