7 The Branch Optimization phase (BO) performs two related
8 (branch) optimizations.
10 Fusion of basic blocks
12 If two basic blocks B1 and B2 have the following properties:
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).
25 While-loop optimization
27 The straightforward way to translate a while loop is to
28 put the test for loop termination at the beginning of the loop.
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
36 Fig. 10.1 Example of Branch Optimization
38 If the condition fails at the Nth iteration, the following code
39 gets executed (dynamically):
43 N * conditional branch (which fails N-1 times)
44 N-1 * unconditional branch
45 N-1 * body of the loop
48 An alternative translation is:
55 Branch On True To LAB1
57 This translation results in the following profile:
61 N * conditional branch (which succeeds N-1 times)
62 1 * unconditional branch
63 N-1 * body of the loop
66 So the second translation will be significantly faster if N >> 2.
67 If N=2, execution time will be slightly increased.
68 On the average, the program will be speeded up.
69 Note that the code sizes of the two translations will be the same.
73 The basic block fusion technique is implemented
74 by traversing the control flow graph of a procedure,
75 looking for basic blocks B with only one successor (S).
76 If one is found, it is checked if S has only one predecessor
78 If so, the two basic blocks can in principle be combined.
79 However, as one basic block will have to be moved,
80 the textual order of the basic blocks will be altered.
81 This reordering causes severe problems in the presence
83 For example, if S ends in a conditional branch,
84 the basic block that comes textually next to S must stay
86 So the transformation in Fig. 10.2 is illegal.
98 Fig. 10.2 An illegal transformation of Branch Optimization
100 If B is moved towards S the same problem occurs if the block before B
101 ends in a conditional jump.
102 The problem could be solved by adding one extra branch,
103 but this would reduce the gains of the optimization to zero.
104 Hence the optimization will only be done if the block that
105 follows S (in the textual order) is not a successor of S.
106 This condition assures that S does not end in a conditional branch.
107 The condition always holds for the code generated by the "C"
108 front end for a switch statement.
110 After the transformation has been performed,
111 some attributes of the basic blocks involved (such as successor and
112 predecessor sets and immediate dominator) must be recomputed.
114 The while-loop technique is applied to one loop at a time.
115 The list of basic blocks of the loop is traversed to find
116 a block B that satisfies the following conditions:
118 the textually next block to B is not part of the loop
120 the last instruction of B is an unconditional branch;
121 hence B has only one successor, say S
123 the textually next block of B is a successor of S
125 the last instruction of S is a conditional branch
127 If such a block B is found, the control flow graph is changed
128 as depicted in Fig. 10.3.
134 |-----<------| ----->-----|
140 | --------- | | ----|---- |
144 | --------- | | | | |
145 v | | | ^ --------- |
147 | | BRA | | | |-----<-----
149 | --------- | | ____|____
151 | ------>------ | | S1 |
161 Fig. 10.3 Transformation of the CFG by Branch Optimization