• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Branch Elimination
2## Overview
3
4`Branch Elimination` searches condition statements which result is known at compile-time and removes not reachable branches.
5
6## Rationality
7
8Reduce number of instructions and simplify control-flow.
9
10## Dependence
11
12* DominatorsTree
13* LoopAnalysis
14* Reverse Post Order (RPO)
15
16## Algorithm
17
18`Branch Elimination` optimization searches `if-true` blocks with resolvable conditional instruction.
19Condition can be resolved in the following ways:
20- Condition is constant:
21```
22             T           F
23           /---[ 1 > 0 ]---\
24           |               |
25           |               |
26           v               v
27                    can be eliminated
28```
29- Condition is dominated by the equal one condition with the same inputs and the only one successor of the dominant reaches dominated condition
30
31```
32             T           F
33           /---[ a > b ]---\
34           |               |
35           |         T     v     F
36          ...      /---[ a > b ]---\
37           |       |               |
38           v       v               v
39              can be eliminated
40
41             T           F
42           /---[ a > b ]---\
43           |               |
44          ...              |
45           |               |
46           \-------------->|
47                     T     v     F
48                   /---[ a > b ]---\
49                   |               |
50                   v               v
51            can't be eliminated - reachable from both successors
52```
53To resolve the condition result by the dominant one we use table, keeps the result of the condition in the row if the condition in the column is true:
54```
55    /*           CC_EQ    CC_NE    CC_LT    CC_LE    CC_GT    CC_GE    CC_B     CC_BE    CC_A     CC_AE */
56    /* CC_EQ */ {true,    false,   false,   nullopt, false,   nullopt, false,   nullopt, false,   nullopt},
57    /* CC_NE */ {false,   true,    true,    nullopt, true,    nullopt, true,    nullopt, true,    nullopt},
58    /* CC_LT */ {false,   nullopt, true,    nullopt, false,   false,   nullopt, nullopt, nullopt, nullopt},
59    /* CC_LE */ {true,    nullopt, true,    true,    false,   nullopt, nullopt, nullopt, nullopt, nullopt},
60    /* CC_GT */ {false,   nullopt, false,   false,   true,    nullopt, nullopt, nullopt, nullopt, nullopt},
61    /* CC_GE */ {true,    nullopt, false,   nullopt, true,    true,    nullopt, nullopt, nullopt, nullopt},
62    /* CC_B  */ {false,   nullopt, nullopt, nullopt, nullopt, nullopt, true,    nullopt, false,   false},
63    /* CC_BE */ {true,    nullopt, nullopt, nullopt, nullopt, nullopt, true,    true,    false,   nullopt},
64    /* CC_A  */ {false,   nullopt, nullopt, nullopt, nullopt, nullopt, false,   false,   true,    nullopt},
65    /* CC_AE */ {true,    nullopt, nullopt, nullopt, nullopt, nullopt, false,   nullopt, true,    true},
66```
67## Pseudocode
68
69TBD
70
71## Examples
72
73```cpp
74              [0]
75            T  |  F
76         /----[2]----\
77         |           |
78         v        T  v  F
79        [3]    /----[4]----\
80         |     |           |
81         |    [5]         [6]
82         |     |           |
83         v     v           |
84       [exit]<-------------/
85
86
87    GRAPH(graph) {
88        PARAMETER(0, 0).u64();
89        PARAMETER(1, 1).u64();
90        PARAMETER(2, 2).u64();
91
92        BASIC_BLOCK(2, 3, 4) {
93            INST(19, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
94            INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(19);
95        }
96        BASIC_BLOCK(3, 7) {
97            INST(5, Opcode::Add).u64().Inputs(0, 1);
98            INST(6, Opcode::Add).u64().Inputs(5, 2);
99        }
100        BASIC_BLOCK(4, 5, 6) {
101            INST(8, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
102            INST(9, Opcode::Compare).b().CC(CC_NE).Inputs(0, 1);
103            INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
104        }
105        BASIC_BLOCK(5, 7) {
106            INST(11, Opcode::Sub).u64().Inputs(0, 1);
107            INST(12, Opcode::Sub).u64().Inputs(11, 2);
108        }
109        BASIC_BLOCK(6, 7) {
110            INST(14, Opcode::Mul).u64().Inputs(0, 1);
111            INST(15, Opcode::Mul).u64().Inputs(14, 2);
112        }
113        BASIC_BLOCK(7, -1) {
114            INST(17, Opcode::Phi).u64().Inputs(6, 12, 15);
115            INST(18, Opcode::Return).u64().Inputs(17);
116        }
117    }
118
119```
120We reaches basic block `4` when the condition `PARAMETER(0) == PARAMETER(1)` is false, so that the result of instruction `INST(9)` always true.
121No we can eliminate basic block `6` and conditional statement form basic block `4`:
122
123```
124              [0]
125            T  |  F
126         /----[2]----\
127         |           |
128         v           v
129        [3]         [4]
130         |           |
131         |          [5]
132         |           |
133         v           |
134       [exit]<-------/
135```
136## Links
137
138Source code:
139[branch_elimination.cpp](../optimizer/optimizations/branch_elimination.cpp)
140[branch_elimination.h](../optimizer/optimizations/branch_elimination.h)
141
142Tests:
143[branch_elimination_test.cpp](../tests/branch_elimination_test.cpp)