12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 |
- .bp
- .NH 1
- Use-Definition analysis
- .NH 2
- Introduction
- .PP
- The "Use-Definition analysis" phase (UD) consists of two related optimization
- techniques that both depend on "Use-Definition" information.
- The techniques are Copy Propagation and Constant Propagation.
- They are best explained via an example (see Figs. 11.1 and 11.2).
- .DS
- (1) A := B A := B
- ... --> ...
- (2) use(A) use(B)
- Fig. 11.1 An example of Copy Propagation
- .DE
- .DS
- (1) A := 12 A := 12
- ... --> ...
- (2) use(A) use(12)
- Fig. 11.2 An example of Constant Propagation
- .DE
- Both optimizations have to check that the value of A at line (2)
- can only be obtained at line (1).
- Copy Propagation also has to assure that the value of B is
- the same at line (1) as at line (2).
- .PP
- One purpose of both transformations is to introduce
- opportunities for the Dead Code Elimination optimization.
- If the variable A is used nowhere else, the assignment A := B
- becomes useless and can be eliminated.
- .sp 0
- If B is less expensive to access than A (e.g. this is sometimes the case
- if A is a local variable and B is a global variable),
- Copy Propagation directly improves the code itself.
- If A is cheaper to access the transformation will not be performed.
- Likewise, a constant as operand may be cheeper than a variable.
- Having a constant as operand may also facilitate other optimizations.
- .PP
- The design of UD is based on the theory described in section
- 14.1 and 14.3 of.
- .[
- aho compiler design
- .]
- As a main departure from that theory,
- we do not demand the statement A := B to become redundant after
- Copy Propagation.
- If B is cheaper to access than A, the optimization is always performed;
- if B is more expensive than A, we never do the transformation.
- If A and B are equally expensive UD uses the heuristic rule to
- replace infrequently used variables by frequently used ones.
- This rule increases the chances of the assignment to become useless.
- .PP
- In the next section we will give a brief outline of the data
- flow theory used
- for the implementation of UD.
|