1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include <vector>
17 #include "unit_test.h"
18 #include "optimizer/analysis/dominators_tree.h"
19
20 namespace panda::compiler {
21 class DomTreeTest : public GraphTest {
22 public:
CheckImmediateDominators(BasicBlock * dominator,const std::set<BasicBlock * > && expected)23 void CheckImmediateDominators(BasicBlock *dominator, const std::set<BasicBlock *> &&expected)
24 {
25 ASSERT_EQ(dominator->GetDominatedBlocks().size(), expected.size());
26
27 for (auto block : dominator->GetDominatedBlocks()) {
28 EXPECT_EQ(block->GetDominator(), dominator);
29 EXPECT_TRUE(expected.find(block) != expected.end());
30 }
31 }
32
CheckImmediateDominatorsIdSet(int id_dom,std::vector<int> && bb_ids)33 void CheckImmediateDominatorsIdSet(int id_dom, std::vector<int> &&bb_ids)
34 {
35 std::set<BasicBlock *> bb_set;
36 for (auto id : bb_ids) {
37 bb_set.insert(&BB(id));
38 }
39 CheckImmediateDominators(&BB(id_dom), std::move(bb_set));
40 }
41
42 template <const bool Condition>
CheckListDominators(BasicBlock * dominator,const std::vector<BasicBlock * > && expected)43 void CheckListDominators(BasicBlock *dominator, const std::vector<BasicBlock *> &&expected)
44 {
45 for (auto dom : expected) {
46 EXPECT_EQ(dominator->IsDominate(dom), Condition);
47 }
48 }
49 };
50
TEST_F(DomTreeTest,OneBlock)51 TEST_F(DomTreeTest, OneBlock)
52 {
53 GRAPH(GetGraph())
54 {
55 BASIC_BLOCK(2, -1)
56 {
57 INST(0, Opcode::ReturnVoid);
58 };
59 }
60
61 auto block = GetGraph()->GetStartBlock();
62 GetGraph()->RunPass<DominatorsTree>();
63
64 EXPECT_TRUE(GetGraph()->IsAnalysisValid<DominatorsTree>());
65 EXPECT_TRUE(block->IsDominate(block));
66 }
67 /*
68 * [entry]
69 * |
70 * v
71 * /-------[2]-------\
72 * | |
73 * v v
74 * [3] [4]
75 * | |
76 * | v
77 * | /-------[5]-------\
78 * | | |
79 * | v v
80 * | [6] [7]
81 * | | |
82 * | v |
83 * \----->[exit]<-------------/
84 *
85 * Dominators tree:
86 *
87 * [entry]
88 * |
89 * v
90 * [2]
91 * / | \
92 * v v v
93 * [3] [exit] [4]
94 * |
95 * v
96 * [5]
97 * / \
98 * v v
99 * [6] [7]
100 *
101 *
102 */
TEST_F(DomTreeTest,GraphNoCycles)103 TEST_F(DomTreeTest, GraphNoCycles)
104 {
105 GRAPH(GetGraph())
106 {
107 CONSTANT(0, 0);
108 CONSTANT(1, 1);
109 BASIC_BLOCK(2, 3, 4)
110 {
111 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
112 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
113 }
114 BASIC_BLOCK(3, -1)
115 {
116 INST(4, Opcode::ReturnVoid);
117 }
118 BASIC_BLOCK(4, 5) {}
119 BASIC_BLOCK(5, 6, 7)
120 {
121 INST(6, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
122 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
123 }
124 BASIC_BLOCK(6, -1)
125 {
126 INST(8, Opcode::ReturnVoid);
127 }
128 BASIC_BLOCK(7, -1)
129 {
130 INST(9, Opcode::ReturnVoid);
131 }
132 }
133
134 auto entry = GetGraph()->GetStartBlock();
135 auto A = &BB(2);
136 auto B = &BB(3);
137 auto C = &BB(4);
138 auto D = &BB(5);
139 auto E = &BB(6);
140 auto F = &BB(7);
141 auto exit = GetGraph()->GetEndBlock();
142
143 // Check if DomTree is valid after building Dom tree
144 GetGraph()->RunPass<DominatorsTree>();
145 EXPECT_TRUE(GetGraph()->IsAnalysisValid<DominatorsTree>());
146
147 // Check if DomTree is not valid after adding new block
148 auto G = GetGraph()->CreateEmptyBlock();
149 auto returnVoid = GetGraph()->CreateInstReturnVoid();
150 G->AppendInst(returnVoid);
151 auto cmp = GetGraph()->CreateInstCompare();
152 cmp->SetType(DataType::BOOL);
153 cmp->SetInput(0, &INS(0));
154 cmp->SetInput(1, &INS(1));
155 cmp->SetOperandsType(DataType::Type::INT64);
156 C->AppendInst(cmp);
157 auto if_inst = GetGraph()->CreateInstIfImm();
158 if_inst->SetOperandsType(DataType::BOOL);
159 if_inst->SetCc(CC_NE);
160 if_inst->SetImm(0);
161 if_inst->SetInput(0, cmp);
162 C->AppendInst(if_inst);
163 C->AddSucc(G);
164 G->AddSucc(exit);
165 GetGraph()->GetRootLoop()->AppendBlock(G);
166
167 EXPECT_FALSE(GetGraph()->IsAnalysisValid<DominatorsTree>());
168 GraphChecker(GetGraph()).Check();
169
170 // Rebuild DomTree and checks dominators
171 GetGraph()->RunPass<DominatorsTree>();
172 CheckImmediateDominators(entry, {A});
173 CheckImmediateDominators(A, {B, exit, C});
174 CheckImmediateDominators(B, {});
175 CheckImmediateDominators(C, {D, G});
176 CheckImmediateDominators(D, {E, F});
177 CheckImmediateDominators(E, {});
178 CheckImmediateDominators(F, {});
179 CheckImmediateDominators(G, {});
180 CheckImmediateDominators(exit, {});
181
182 CheckListDominators<true>(entry, {entry, A, B, C, D, E, F, G, exit});
183 CheckListDominators<true>(A, {A, B, C, D, E, F, G, exit});
184 CheckListDominators<true>(C, {C, D, E, F, G});
185 CheckListDominators<true>(D, {D, E, F});
186
187 CheckListDominators<false>(B, {entry, A, C, D, E, F, G, exit});
188 CheckListDominators<false>(E, {entry, A, B, C, D, F, G, exit});
189 CheckListDominators<false>(F, {entry, A, B, C, D, E, G, exit});
190 CheckListDominators<false>(G, {entry, A, B, C, D, E, F, exit});
191 CheckListDominators<false>(exit, {entry, A, B, C, D, E, F, G});
192 }
193
194 /*
195 * [entry]
196 * |
197 * v
198 * /-------------------->[2]-------------\
199 * | | |
200 * | | v
201 * | | [3]
202 * | v |
203 * | [4]<-------------/
204 * | ^
205 * | |
206 * | v
207 * | [5]
208 * | / ^
209 * | v |
210 * | [6] |
211 * | \ |
212 * | \ |
213 * | v |
214 * | [8]
215 * | |
216 * | v
217 * | [9]
218 * | / \
219 * | v v
220 * \----------------[10] [11]
221 * |
222 * |
223 * v
224 * [exit]
225 *
226 * Dominators tree:
227 * [entry]
228 * |
229 * v
230 * [2]
231 * / \
232 * v v
233 * [3] [4]
234 * |
235 * [5]
236 * |
237 * v
238 * [6]
239 * |
240 * v
241 * [9]
242 * / \
243 * v v
244 * [10] [11]
245 * |
246 * v
247 * [exit]
248 */
TEST_F(DomTreeTest,GraphWithCycles)249 TEST_F(DomTreeTest, GraphWithCycles)
250 {
251 GRAPH(GetGraph())
252 {
253 CONSTANT(0, 0);
254 CONSTANT(1, 1);
255 BASIC_BLOCK(2, 3, 4)
256 {
257 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
258 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
259 }
260 BASIC_BLOCK(3, 4) {}
261 BASIC_BLOCK(4, 5) {}
262 BASIC_BLOCK(5, 6, 4)
263 {
264 INST(6, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
265 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
266 }
267 BASIC_BLOCK(6, 8) {}
268 BASIC_BLOCK(8, 5, 9)
269 {
270 INST(9, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
271 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
272 }
273 BASIC_BLOCK(9, 10, 11)
274 {
275 INST(11, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
276 INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
277 }
278 BASIC_BLOCK(10, 2) {}
279 BASIC_BLOCK(11, -1)
280 {
281 INST(14, Opcode::ReturnVoid);
282 }
283 }
284 auto entry = GetGraph()->GetStartBlock();
285 auto K = &BB(2);
286 auto A = &BB(3);
287 auto B = &BB(4);
288 auto C = &BB(5);
289 auto D = &BB(6);
290 auto F = &BB(8);
291 auto G = &BB(9);
292 auto H = &BB(10);
293 auto I = &BB(11);
294 auto exit = GetGraph()->GetEndBlock();
295
296 GraphChecker(GetGraph()).Check();
297
298 // Check if DomTree is valid after building Dom tree
299 GetGraph()->GetAnalysis<DominatorsTree>().SetValid(false);
300 GetGraph()->RunPass<DominatorsTree>();
301 EXPECT_TRUE(GetGraph()->IsAnalysisValid<DominatorsTree>());
302
303 CheckImmediateDominators(GetGraph()->GetStartBlock(), {BB(2).GetLoop()->GetPreHeader()});
304 CheckImmediateDominators(&BB(2), {&BB(3), BB(4).GetLoop()->GetPreHeader()});
305 CheckImmediateDominatorsIdSet(3, {});
306 CheckImmediateDominatorsIdSet(4, {5});
307 CheckImmediateDominatorsIdSet(5, {6});
308 CheckImmediateDominatorsIdSet(6, {8});
309 CheckImmediateDominatorsIdSet(8, {9});
310 CheckImmediateDominatorsIdSet(9, {10, 11});
311 CheckImmediateDominatorsIdSet(10, {});
312 CheckImmediateDominatorsIdSet(11, {IrConstructor::ID_EXIT_BB});
313
314 CheckListDominators<true>(entry, {entry, K, A, B, C, D, F, G, H, I, exit});
315 CheckListDominators<true>(K, {K, A, B, C, D, F, G, H, I, exit});
316 CheckListDominators<true>(B, {B, C, D, F, G, H, I, exit});
317 CheckListDominators<true>(C, {C, D, F, G, H, I, exit});
318 CheckListDominators<true>(F, {F, G, H, I, exit});
319 CheckListDominators<true>(G, {H, I, exit});
320
321 CheckListDominators<false>(A, {entry, B, C, D, F, G, H, I, exit});
322 CheckListDominators<false>(D, {entry, A, B, C});
323 CheckListDominators<false>(H, {entry, A, B, C, D, F, G, I, exit});
324 CheckListDominators<false>(I, {entry, A, B, C, D, F, G, H});
325 }
326 } // namespace panda::compiler
327