Page 604
Thus, like a statement, a basic block also generates a set of definitions and kills a set of definitions.
The gen set contains all the definitions inside the block that are “visible" immediately after the block
- we refer to them as downwards exposed. A definition is downwards exposed in a basic block only if
it is not “killed" by a subsequent definition to the same variable inside the same basic block. A basic
block's kill set is simply the union of all the definitions killed by the individual statements.
The reaching definitions problem is defined by the following equations:
Data Flow Equations
OUT[entry] = φ
Seven definitions of d1, d2, …, d7 are represented by a bit vector, di is represented by the bit i from
left.
We shall represent the seven definitions d1; d2; : : : ; d7 in the flow graph of Fig. 9.13 by bit vectors,
where bit i from the left represents definition di. The union of sets is computed by taking the logical
OR of the corresponding bit vectors. The difference of two sets S - T is computed by complementing
the bit vector of T, and then taking the logical AND of that complement, with the bit vector for S.
Execution path – B1, B2, B3, B4, EXIT
Superscript indicates pass of the algorithm (Page 606)
ALGORITHM: Detection of loop-invariant computations.
INPUT: A loop L consisting of a set of basic blocks, each block containing sequence of three-address
statements. We assume ud-chains are available for the individual statements.
OUTPUT: the set of three-address statements that compute the same value each time executed,
from the time control enters the loop L until control next leaves L.
METHOD: we shall give a rather informal specification of the algorithm, trusting that the principles
will be clear.
1, Mark “invariant” those statements whose operands are all either constant or have all their
reaching definitions outside L.
2, Repeat step (3) until at some repetition no new statements are marked “invariant”.
3. Mark “invariant” all those statements not previously so marked all of whose operands either are
constant, have all their reaching definitions outside L, or have exactly one reaching definition, and
that definition is a statement in L marked invariant.
Global Common sub-expression Elimination
An expression x + y is available at a point p, if every path from the entry node to
p evaluates x + y, and after the last such evaluation prior to reaching p, there
are no subsequent assignments to x or y.
For the available-expressions data flow schema we say that a block kills
expression x+y if it assigns (or may assign) x or y and does not subsequently
recompute x + y. A block generates expression x+y if it definitely evaluates x+y
and does not subsequently define x or y.
Note that the notion of “killing" or “generating" an available expression is not
exactly the same as that for reaching definitions. Nevertheless, these notions of
“kill" and “generate" behave essentially as they do for reaching definitions.
The primary use of available-expression information is for detecting global
common sub expressions. For example, in Fig. 9.17(a), the expression 4 * i in
block B3 will be a common sub expression if 4 * i is available at the entry point of
block B3. It will be available if i is not assigned a new value in block B2, or if, as
in Fig. 9.17(b), 4 * i is recomputed after i is assigned in B2.
A block kills x op y, if it assigns (or may assign) to x or y and does not
subsequently recompute x op y.
A block generates x op y, if it definitely evaluates x op y, and does not
subsequently redefine x or y
Let, U be the "universal" set of all expression appearing at the right of one or
more statements of the program.
For each node n, IN [n] is the set of expression of U that are available at the
point just before the beginning of n.
OUT [n] is the set of expression of U that are available at the point following the
end of n
E_GEN [n] is the set of expression generated by n.
E-KILL [n] is the set of expression in U killed by n.
Note
IN [n], OUT [n], E_GEN [n]), and E_KILL [n] can all be represented by (known) List-
rectory.
fon noden
