Java Reference
In-Depth Information
in Figure 14.41(a). Thus, the program can be optimized by eliminating that
computation of v + w .
In this example, we explored the availability of a single expression v + w .
Programs typically contain many expressions and compilers often generate
more expressions than are written explicitly in programs (e.g., to compute the
byte o
set of a subscript expression). Optimizing compilers usually take one
of the following approaches to identify expressions of interest:
ff
The compiler may identify an expression such as v + w as important ,
in the sense that eliminating its computation can significantly improve
the program's performance. In this situation, the optimizing compiler
may selectively evaluate the availability of a single expression. SSA
Form (Section 14.7) and sparse evaluation graphs [CCF91] facilitate such
selective analysis.
The compiler may compute availability of all expressions, without regard
to the importance of the results. In this situation, it is common to for-
mulate a set of expressions and compute the availability of its members.
Section 14.4 and Exercise 35 consider this in greater detail.
14.3.2 Live Variables
We next examine an optimization problem related to register allocation. As
discussed in Chapter 13, k registers su
ce for a program whose interference
graph is k -colorable. In this graph, each node represents one of the program's
variables. An edge is placed between two nodes if their associated variables
are simultaneously live .Avariable v is live at control flow graph edge e if the
future behavior of the program can reference the value of v that is present at
edge e . In other words, the value of a live variable is potentially of future use
in the program. Thus, register allocation relies on computing livevariables to
build the interference graph.
The livevariablesproblem can be solved by data flow analysis techniques.
It is related to availableexpressions in that they are two of the four problems
commonly called the bit-vectoring data flow problems (Exercise 39).
In the availableexpressions solution shown in Figure 14.42, information
follows the orientation of the control flow graph. Information is collected at
the inedges of a node, pushed through the node, and transmitted on the node's
outedges. Such data flow problems are called forward . On the other hand,
solving the livevariables problem requires characterizing the future behavior
of a program. Such data flow problems are called backward . Information
is collected at a node's outedges, pushed backward through the node, and
transmitted out of the node on its inedges.
 
 
Search WWH ::




Custom Search