cj1 3.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
  1. .bp
  2. .NH 1
  3. Cross jumping
  4. .NH 2
  5. Introduction
  6. .PP
  7. The "Cross Jumping" optimization technique (CJ)
  8. .[
  9. wulf design optimizing compiler
  10. .]
  11. is basically a space optimization technique. It looks for pairs of
  12. basic blocks (B1,B2), for which:
  13. .DS
  14. SUCC(B1) = SUCC(B2) = {S}
  15. .DE
  16. (So B1 and B2 both have one and the same successor).
  17. If the last few non-branch instructions are the same for B1 and B2,
  18. one such sequence can be eliminated.
  19. .DS
  20. Pascal:
  21. if cond then
  22. S1
  23. S3
  24. else
  25. S2
  26. S3
  27. (pseudo) EM:
  28. .TS
  29. l l l.
  30. TEST COND TEST COND
  31. BNE *1 BNE *1
  32. S1 S1
  33. S3 ---> BRA *2
  34. BRA *2 1:
  35. 1: S2
  36. S2 2:
  37. S3 S3
  38. 2:
  39. .TE
  40. Fig. 9.1 An example of Cross Jumping
  41. .DE
  42. As the basic blocks have the same successor,
  43. at least one of them ends in an unconditional branch instruction (BRA).
  44. Hence no extra branch instruction is ever needed, just the target
  45. of an existing branch needs to be changed; neither the program size
  46. nor the execution time will ever increase.
  47. In general, the execution time will remain the same, unless
  48. further optimizations can be applied because of this optimization.
  49. .PP
  50. This optimization is particularly effective,
  51. because it cannot always be done by the programmer at the source level,
  52. as demonstrated by the Fig. 8.2.
  53. .DS
  54. Pascal:
  55. if cond then
  56. x := f(4)
  57. else
  58. x := g(5)
  59. EM:
  60. .TS
  61. l l.
  62. ... ...
  63. LOC 4 LOC 5
  64. CAL F CAL G
  65. ASP 2 ASP 2
  66. LFR 2 LFR 2
  67. STL X STL X
  68. .TE
  69. Fig. 9.2 Effectiveness of Cross Jumping
  70. .DE
  71. At the source level there is no common tail,
  72. but at the EM level there is a common tail.
  73. .NH 2
  74. Implementation
  75. .PP
  76. The implementation of cross jumping is rather straightforward.
  77. The technique is applied to one procedure at a time.
  78. The control flow graph of the procedure
  79. is scanned for pairs of basic blocks
  80. with the same (single) successor and with common tails.
  81. Note that there may be more than two such blocks (e.g. as the result
  82. of a case statement).
  83. This is dealt with by repeating the entire process until no
  84. further optimizations can de done for the current procedure.
  85. .sp
  86. If a suitable pair of basic blocks has been found, the control flow
  87. graph must be altered. One of the basic
  88. blocks must be split into two.
  89. The control flow graphs before and after the optimization are shown
  90. in Fig. 9.3 and Fig. 9.4.
  91. .DS
  92. .ft 5
  93. -------- --------
  94. | | | |
  95. | S1 | | S2 |
  96. | S3 | | S3 |
  97. | | | |
  98. -------- --------
  99. | |
  100. |------------------|--------------------|
  101. |
  102. v
  103. .ft R
  104. Fig. 9.3 CFG before optimization
  105. .DE
  106. .DS
  107. .ft 5
  108. -------- --------
  109. | | | |
  110. | S1 | | S2 |
  111. | | | |
  112. -------- --------
  113. | |
  114. |--------------------<------------------|
  115. v
  116. --------
  117. | |
  118. | S3 |
  119. | |
  120. --------
  121. |
  122. v
  123. .ft R
  124. Fig. 9.4 CFG after optimization
  125. .DE
  126. Some attributes of the three resulting blocks (such as immediate dominator)
  127. are updated.
  128. .PP
  129. In some cases, cross jumping might split the computation of an expression
  130. into two, by inserting a branch somewhere in the middle.
  131. Most code generators will generate very poor assembly code when
  132. presented with such EM code.
  133. Therefor, cross jumping is not performed in these cases.