12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 |
- .NH 2
- Data flow information
- .PP
- .NH 3
- Use-Definition information
- .PP
- A \fIdefinition\fR of a variable A is an assignment to A.
- A definition is said to \fIreach\fR a point p if there is a
- path in the control flow graph from the definition to p, such that
- A is not redefined on that path.
- .PP
- For every basic block B, we define the following sets:
- .IP GEN[b] 9
- the set of definitions in b that reach the end of b.
- .IP KILL[b]
- the set of definitions outside b that define a variable that
- is changed in b.
- .IP IN[b]
- the set of all definitions reaching the beginning of b.
- .IP OUT[b]
- the set of all definitions reaching the end of b.
- .LP
- GEN and KILL can be determined by inspecting the code of the procedure.
- IN and OUT are computed by solving the following data flow equations:
- .DS
- (1) OUT[b] = IN[b] - KILL[b] + GEN[b]
- (2) IN[b] = OUT[p1] + ... + OUT[pn],
- where PRED(b) = {p1, ... , pn}
- .DE
- .NH 3
- Copy information
- .PP
- A \fIcopy\fR is a definition of the form "A := B".
- A copy is said to be \fIgenerated\fR in a basic block n if
- it occurs in n and there is no subsequent assignment to B in n.
- A copy is said to be \fIkilled\fR in n if:
- .IP (i)
- it occurs in n and there is a subsequent assignment to B within n, or
- .IP (ii)
- it occurs outside n, the definition A := B reaches the beginning of n
- and B is changed in n (note that a copy also is a definition).
- .LP
- A copy \fIreaches\fR a point p, if there are no assignments to B
- on any path in the control flow graph from the copy to p.
- .PP
- We define the following sets:
- .IP C_GEN[b] 11
- the set of all copies in b generated in b.
- .IP C_KILL[b]
- the set of all copies killed in b.
- .IP C_IN[b]
- the set of all copies reaching the beginning of b.
- .IP C_OUT[b]
- the set of all copies reaching the end of b.
- .LP
- C_IN and C_OUT are computed by solving the following equations:
- (root is the entry node of the current procedure; '*' denotes
- set intersection)
- .DS
- (1) C_OUT[b] = C_IN[b] - C_KILL[b] + C_GEN[b]
- (2) C_IN[b] = C_OUT[p1] * ... * C_OUT[pn],
- where PRED(b) = {p1, ... , pn} and b /= root
- C_IN[root] = {all copies}
- .DE
|