doc/ego/cj/cj1

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