ud1 2.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
  1. .bp
  2. .NH 1
  3. Use-Definition analysis
  4. .NH 2
  5. Introduction
  6. .PP
  7. The "Use-Definition analysis" phase (UD) consists of two related optimization
  8. techniques that both depend on "Use-Definition" information.
  9. The techniques are Copy Propagation and Constant Propagation.
  10. They are best explained via an example (see Figs. 11.1 and 11.2).
  11. .DS
  12. (1) A := B A := B
  13. ... --> ...
  14. (2) use(A) use(B)
  15. Fig. 11.1 An example of Copy Propagation
  16. .DE
  17. .DS
  18. (1) A := 12 A := 12
  19. ... --> ...
  20. (2) use(A) use(12)
  21. Fig. 11.2 An example of Constant Propagation
  22. .DE
  23. Both optimizations have to check that the value of A at line (2)
  24. can only be obtained at line (1).
  25. Copy Propagation also has to assure that the value of B is
  26. the same at line (1) as at line (2).
  27. .PP
  28. One purpose of both transformations is to introduce
  29. opportunities for the Dead Code Elimination optimization.
  30. If the variable A is used nowhere else, the assignment A := B
  31. becomes useless and can be eliminated.
  32. .sp 0
  33. If B is less expensive to access than A (e.g. this is sometimes the case
  34. if A is a local variable and B is a global variable),
  35. Copy Propagation directly improves the code itself.
  36. If A is cheaper to access the transformation will not be performed.
  37. Likewise, a constant as operand may be cheeper than a variable.
  38. Having a constant as operand may also facilitate other optimizations.
  39. .PP
  40. The design of UD is based on the theory described in section
  41. 14.1 and 14.3 of.
  42. .[
  43. aho compiler design
  44. .]
  45. As a main departure from that theory,
  46. we do not demand the statement A := B to become redundant after
  47. Copy Propagation.
  48. If B is cheaper to access than A, the optimization is always performed;
  49. if B is more expensive than A, we never do the transformation.
  50. If A and B are equally expensive UD uses the heuristic rule to
  51. replace infrequently used variables by frequently used ones.
  52. This rule increases the chances of the assignment to become useless.
  53. .PP
  54. In the next section we will give a brief outline of the data
  55. flow theory used
  56. for the implementation of UD.