bo1 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
  1. .bp
  2. .NH 1
  3. Branch Optimization
  4. .NH 2
  5. Introduction
  6. .PP
  7. The Branch Optimization phase (BO) performs two related
  8. (branch) optimizations.
  9. .NH 3
  10. Fusion of basic blocks
  11. .PP
  12. If two basic blocks B1 and B2 have the following properties:
  13. .DS
  14. SUCC(B1) = {B2}
  15. PRED(B2) = {B1}
  16. .DE
  17. then B1 and B2 can be combined into one basic block.
  18. If B1 ends in an unconditional jump to the beginning of B2, this
  19. jump can be eliminated,
  20. hence saving a little execution time and object code size.
  21. This technique can be used to eliminate some deficiencies
  22. introduced by the front ends (for example, the "C" front end
  23. translates switch statements inefficiently due to its one pass nature).
  24. .NH 3
  25. While-loop optimization
  26. .PP
  27. The straightforward way to translate a while loop is to
  28. put the test for loop termination at the beginning of the loop.
  29. .DS
  30. while cond loop \kyLAB1: \kxTest cond
  31. body of the loop --->\h'|\nxu'Branch On False To LAB2
  32. end loop\h'|\nxu'code for body of loop
  33. \h'|\nxu'Branch To LAB1
  34. \h'|\nyu'LAB2:
  35. Fig. 10.1 Example of Branch Optimization
  36. .DE
  37. If the condition fails at the Nth iteration, the following code
  38. gets executed (dynamically):
  39. .DS
  40. .TS
  41. l l l.
  42. N * conditional branch (which fails N-1 times)
  43. N-1 * unconditional branch
  44. N-1 * body of the loop
  45. .TE
  46. .DE
  47. An alternative translation is:
  48. .DS
  49. Branch To LAB2
  50. LAB1:
  51. code for body of loop
  52. LAB2:
  53. Test cond
  54. Branch On True To LAB1
  55. .DE
  56. This translation results in the following profile:
  57. .DS
  58. .TS
  59. l l l.
  60. N * conditional branch (which succeeds N-1 times)
  61. 1 * unconditional branch
  62. N-1 * body of the loop
  63. .TE
  64. .DE
  65. So the second translation will be significantly faster if N >> 2.
  66. If N=2, execution time will be slightly increased.
  67. On the average, the program will be speeded up.
  68. Note that the code sizes of the two translations will be the same.
  69. .NH 2
  70. Implementation
  71. .PP
  72. The basic block fusion technique is implemented
  73. by traversing the control flow graph of a procedure,
  74. looking for basic blocks B with only one successor (S).
  75. If one is found, it is checked if S has only one predecessor
  76. (which has to be B).
  77. If so, the two basic blocks can in principle be combined.
  78. However, as one basic block will have to be moved,
  79. the textual order of the basic blocks will be altered.
  80. This reordering causes severe problems in the presence
  81. of conditional jumps.
  82. For example, if S ends in a conditional branch,
  83. the basic block that comes textually next to S must stay
  84. in that position.
  85. So the transformation in Fig. 10.2 is illegal.
  86. .DS
  87. .TS
  88. l l l l l.
  89. LAB1: S1 LAB1: S1
  90. BRA LAB2 S2
  91. ... --> BEQ LAB3
  92. LAB2: S2 ...
  93. BEQ LAB3 S3
  94. S3
  95. .TE
  96. Fig. 10.2 An illegal transformation of Branch Optimization
  97. .DE
  98. If B is moved towards S the same problem occurs if the block before B
  99. ends in a conditional jump.
  100. The problem could be solved by adding one extra branch,
  101. but this would reduce the gains of the optimization to zero.
  102. Hence the optimization will only be done if the block that
  103. follows S (in the textual order) is not a successor of S.
  104. This condition assures that S does not end in a conditional branch.
  105. The condition always holds for the code generated by the "C"
  106. front end for a switch statement.
  107. .PP
  108. After the transformation has been performed,
  109. some attributes of the basic blocks involved (such as successor and
  110. predecessor sets and immediate dominator) must be recomputed.
  111. .PP
  112. The while-loop technique is applied to one loop at a time.
  113. The list of basic blocks of the loop is traversed to find
  114. a block B that satisfies the following conditions:
  115. .IP 1.
  116. the textually next block to B is not part of the loop
  117. .IP 2.
  118. the last instruction of B is an unconditional branch;
  119. hence B has only one successor, say S
  120. .IP 3.
  121. the textually next block of B is a successor of S
  122. .IP 4.
  123. the last instruction of S is a conditional branch
  124. .LP
  125. If such a block B is found, the control flow graph is changed
  126. as depicted in Fig. 10.3.
  127. .DS
  128. .ft 5
  129. | |
  130. | v
  131. v |
  132. |-----<------| ----->-----|
  133. ____|____ | |
  134. | | | |-------| |
  135. | S1 | | | v |
  136. | Bcc | | | .... |
  137. |--| | | | |
  138. | --------- | | ----|---- |
  139. | | | | | |
  140. | .... ^ | | S2 | |
  141. | | | | | |
  142. | --------- | | | | |
  143. v | | | ^ --------- |
  144. | | S2 | | | | |
  145. | | BRA | | | |-----<-----
  146. | | | | | v
  147. | --------- | | ____|____
  148. | | | | | |
  149. | ------>------ | | S1 |
  150. | | | Bnn |
  151. |-------| | | |
  152. | | ----|----
  153. v | |
  154. |----<--|
  155. |
  156. v
  157. .ft R
  158. Fig. 10.3 Transformation of the CFG by Branch Optimization
  159. .DE