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 <set>
17 #include "optimizer/analysis/linear_order.h"
18 #include "optimizer/optimizations/regalloc/reg_alloc.h"
19 #include "unit_test.h"
20
21 namespace panda::compiler {
22 class BasicBlockTest : public GraphTest {
23 public:
24 template <typename T>
CheckVectorEqualSet(ArenaVector<T * > blocks,std::set<T * > && excepct)25 void CheckVectorEqualSet(ArenaVector<T *> blocks, std::set<T *> &&excepct)
26 {
27 ASSERT_EQ(blocks.size(), excepct.size());
28
29 std::set<T *> result;
30 for (auto block : blocks) {
31 result.insert(block);
32 }
33 EXPECT_EQ(result, excepct);
34 }
35
CheckVectorEqualBlocksIdSet(ArenaVector<BasicBlock * > blocks,std::vector<int> && bb_ids)36 void CheckVectorEqualBlocksIdSet(ArenaVector<BasicBlock *> blocks, std::vector<int> &&bb_ids)
37 {
38 std::set<BasicBlock *> bb_set;
39 for (auto id : bb_ids) {
40 bb_set.insert(&BB(id));
41 }
42 CheckVectorEqualSet(blocks, std::move(bb_set));
43 }
44
45 /*
46 * Check if block's false-successor is placed in the next position of the rpo vector or the block `NeedsJump()`
47 */
CheckBlockFalseSuccessorPosition(BasicBlock * block,const ArenaVector<BasicBlock * > & blocks_vector)48 void CheckBlockFalseSuccessorPosition(BasicBlock *block, const ArenaVector<BasicBlock *> &blocks_vector)
49 {
50 auto block_rpo_it = std::find(blocks_vector.begin(), blocks_vector.end(), block);
51 auto false_block_it = std::find(blocks_vector.begin(), blocks_vector.end(), block->GetFalseSuccessor());
52 ASSERT_NE(block_rpo_it, blocks_vector.end());
53 ASSERT_NE(false_block_it, blocks_vector.end());
54 auto block_rpo_index = std::distance(blocks_vector.begin(), block_rpo_it);
55 auto false_block_rpo_index = std::distance(blocks_vector.begin(), false_block_it);
56 EXPECT_TRUE((block_rpo_index + 1 == false_block_rpo_index) || (block->NeedsJump()));
57 }
58 };
59
60 /*
61 * Test Graph:
62 * [entry]
63 * |
64 * v
65 * /-------[2]-------\
66 * | |
67 * v v
68 * [3] [4]
69 * | |
70 * | v
71 * | /--------[5]
72 * | | |
73 * | v v
74 * | [6] [7]
75 * | | |
76 * | v v
77 * \----->[9]<-------/
78 * |
79 * v
80 * [exit]
81 */
TEST_F(BasicBlockTest,RemoveBlocks)82 TEST_F(BasicBlockTest, RemoveBlocks)
83 {
84 // build graph
85 GRAPH(GetGraph())
86 {
87 CONSTANT(0, 12);
88 CONSTANT(1, 13);
89 PARAMETER(20, 0).u64();
90 PARAMETER(21, 1).u64();
91
92 BASIC_BLOCK(2, 3, 4)
93 {
94 INST(18, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
95 INST(19, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(18);
96 }
97 BASIC_BLOCK(4, 5) {}
98 BASIC_BLOCK(5, 6, 7)
99 {
100 INST(22, Opcode::Mul).u64().Inputs(20, 20);
101 INST(3, Opcode::Not).u64().Inputs(0);
102 INST(17, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
103 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(17);
104 }
105 BASIC_BLOCK(3, 9)
106 {
107 INST(4, Opcode::Add).u64().Inputs(0, 1);
108 }
109 BASIC_BLOCK(6, 9)
110 {
111 INST(5, Opcode::Sub).u64().Inputs(1, 0);
112 }
113 BASIC_BLOCK(7, 9)
114 {
115 INST(6, Opcode::Div).u64().Inputs(22, 21);
116 }
117 BASIC_BLOCK(9, -1)
118 {
119 INST(8, Opcode::Phi).u64().Inputs({{3, 4}, {6, 5}, {7, 6}});
120 INST(16, Opcode::ReturnVoid);
121 }
122 }
123
124 EXPECT_EQ(INS(8).GetInputsCount(), BB(9).GetPredsBlocks().size());
125 CheckVectorEqualBlocksIdSet(BB(IrConstructor::ID_ENTRY_BB).GetPredsBlocks(), {});
126 CheckVectorEqualBlocksIdSet(BB(IrConstructor::ID_ENTRY_BB).GetSuccsBlocks(), {2});
127 CheckVectorEqualBlocksIdSet(BB(2).GetPredsBlocks(), {IrConstructor::ID_ENTRY_BB});
128 CheckVectorEqualBlocksIdSet(BB(2).GetSuccsBlocks(), {3, 4});
129 CheckVectorEqualBlocksIdSet(BB(3).GetPredsBlocks(), {2});
130 CheckVectorEqualBlocksIdSet(BB(3).GetSuccsBlocks(), {9});
131 CheckVectorEqualBlocksIdSet(BB(4).GetPredsBlocks(), {2});
132 CheckVectorEqualBlocksIdSet(BB(4).GetSuccsBlocks(), {5});
133 CheckVectorEqualBlocksIdSet(BB(5).GetPredsBlocks(), {4});
134 CheckVectorEqualBlocksIdSet(BB(5).GetSuccsBlocks(), {6, 7});
135 CheckVectorEqualBlocksIdSet(BB(6).GetPredsBlocks(), {5});
136 CheckVectorEqualBlocksIdSet(BB(6).GetSuccsBlocks(), {9});
137 CheckVectorEqualBlocksIdSet(BB(7).GetPredsBlocks(), {5});
138 CheckVectorEqualBlocksIdSet(BB(7).GetSuccsBlocks(), {9});
139 CheckVectorEqualBlocksIdSet(BB(9).GetPredsBlocks(), {3, 6, 7});
140 CheckVectorEqualBlocksIdSet(BB(9).GetSuccsBlocks(), {IrConstructor::ID_EXIT_BB});
141 CheckVectorEqualBlocksIdSet(BB(IrConstructor::ID_EXIT_BB).GetPredsBlocks(), {9});
142 CheckVectorEqualBlocksIdSet(BB(IrConstructor::ID_EXIT_BB).GetSuccsBlocks(), {});
143 EXPECT_TRUE(INS(22).GetUsers().Front().GetInst() == &INS(6));
144 EXPECT_TRUE(INS(21).GetUsers().Front().GetInst() == &INS(6));
145
146 GetGraph()->DisconnectBlock(&BB(7));
147
148 EXPECT_TRUE(INS(22).GetUsers().Empty());
149 EXPECT_TRUE(INS(21).GetUsers().Empty());
150 CheckVectorEqualBlocksIdSet(BB(5).GetSuccsBlocks(), {6});
151 CheckVectorEqualBlocksIdSet(BB(9).GetPredsBlocks(), {3, 6});
152 EXPECT_EQ(INS(8).GetInputsCount(), BB(9).GetPredsBlocks().size());
153
154 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
155 GetGraph()->RunPass<LoopAnalyzer>();
156 GraphChecker(GetGraph()).Check();
157 }
158
159 /*
160 * [2]
161 * |
162 * /---------\
163 * [3] [4]
164 * \---------/
165 * |
166 * [5]
167 */
TEST_F(BasicBlockTest,RemoveEmptyBlock)168 TEST_F(BasicBlockTest, RemoveEmptyBlock)
169 {
170 GRAPH(GetGraph())
171 {
172 PARAMETER(0, 0).u64();
173 PARAMETER(1, 1).u64();
174 BASIC_BLOCK(2, 3, 4)
175 {
176 INST(2, Opcode::Compare).b().Inputs(0, 1);
177 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
178 }
179 BASIC_BLOCK(3, 5) {}
180 BASIC_BLOCK(4, 5) {}
181 BASIC_BLOCK(5, -1)
182 {
183 INST(4, Opcode::ReturnVoid);
184 }
185 }
186 ASSERT_EQ(BB(2).GetTrueSuccessor(), &BB(3));
187 ASSERT_EQ(BB(2).GetFalseSuccessor(), &BB(4));
188 auto bb5_pred3_idx = BB(5).GetPredBlockIndex(&BB(3));
189 auto bb5_pred4_idx = BB(5).GetPredBlockIndex(&BB(4));
190 GetGraph()->RemoveEmptyBlockWithPhis(&BB(3));
191 ASSERT_EQ(BB(2).GetTrueSuccessor(), &BB(5));
192 ASSERT_EQ(BB(2).GetFalseSuccessor(), &BB(4));
193 ASSERT_TRUE(BB(3).GetSuccsBlocks().empty());
194 ASSERT_TRUE(BB(3).GetPredsBlocks().empty());
195 ASSERT_EQ(BB(5).GetPredBlockIndex(&BB(2)), bb5_pred3_idx);
196 ASSERT_EQ(BB(5).GetPredBlockIndex(&BB(4)), bb5_pred4_idx);
197 }
198
TEST_F(BasicBlockTest,MissBBId)199 TEST_F(BasicBlockTest, MissBBId)
200 {
201 GRAPH(GetGraph())
202 {
203 BASIC_BLOCK(2, 4) {}
204 BASIC_BLOCK(4, -1)
205 {
206 INST(2, Opcode::ReturnVoid);
207 }
208 }
209 CheckVectorEqualBlocksIdSet(BB(IrConstructor::ID_ENTRY_BB).GetPredsBlocks(), {});
210 CheckVectorEqualBlocksIdSet(BB(IrConstructor::ID_ENTRY_BB).GetSuccsBlocks(), {2});
211 CheckVectorEqualBlocksIdSet(BB(2).GetPredsBlocks(), {IrConstructor::ID_ENTRY_BB});
212 CheckVectorEqualBlocksIdSet(BB(2).GetSuccsBlocks(), {4});
213 CheckVectorEqualBlocksIdSet(BB(4).GetPredsBlocks(), {2});
214 CheckVectorEqualBlocksIdSet(BB(4).GetSuccsBlocks(), {IrConstructor::ID_EXIT_BB});
215 CheckVectorEqualBlocksIdSet(BB(IrConstructor::ID_EXIT_BB).GetPredsBlocks(), {4});
216 CheckVectorEqualBlocksIdSet(BB(IrConstructor::ID_EXIT_BB).GetSuccsBlocks(), {});
217 }
218
219 /*
220 * [entry]
221 * |
222 * v
223 * [2]-------->[3]
224 * | / \
225 * v v v
226 * [4]---->[5]---->[6]
227 * |
228 * v
229 * [exit]
230 */
TEST_F(BasicBlockTest,IfTrueSwapSuccessors)231 TEST_F(BasicBlockTest, IfTrueSwapSuccessors)
232 {
233 GRAPH(GetGraph())
234 {
235 CONSTANT(0, 0);
236 CONSTANT(1, 1);
237
238 BASIC_BLOCK(2, 3, 4)
239 {
240 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).CC(CC_EQ).Inputs(0, 1);
241 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
242 }
243 BASIC_BLOCK(3, 5, 6)
244 {
245 INST(4, Opcode::Compare).b().SrcType(DataType::Type::INT64).CC(CC_NE).Inputs(0, 1);
246 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
247 }
248 BASIC_BLOCK(4, 5)
249 {
250 INST(6, Opcode::Add).s64().Inputs(0, 1);
251 }
252 BASIC_BLOCK(5, 6)
253 {
254 INST(13, Opcode::Phi).s64().Inputs({{4, 6}, {3, 0}});
255 INST(8, Opcode::Add).s64().Inputs(13, 13);
256 }
257 BASIC_BLOCK(6, 7)
258 {
259 INST(14, Opcode::Phi).s64().Inputs({{5, 8}, {3, 0}});
260 INST(10, Opcode::Add).s64().Inputs(14, 14);
261 }
262 BASIC_BLOCK(7, -1)
263 {
264 INST(12, Opcode::Return).s64().Inputs(10);
265 }
266 }
267 }
268
269 /*
270 * [entry]
271 * |
272 * v
273 * /-------[2]
274 * | |
275 * | v
276 * [3] [4]
277 * | |
278 * \--------\------>[5]------\
279 * | | |
280 * | | v
281 * \--------\------>[6]--->[exit]
282 *
283 */
TEST_F(BasicBlockTest,IfTrueInsertFalseBlock)284 TEST_F(BasicBlockTest, IfTrueInsertFalseBlock)
285 {
286 GRAPH(GetGraph())
287 {
288 CONSTANT(0, 0);
289 CONSTANT(1, 1);
290
291 BASIC_BLOCK(2, 3, 4)
292 {
293 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).CC(CC_EQ).Inputs(0, 1);
294 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
295 }
296 BASIC_BLOCK(3, 5, 6)
297 {
298 INST(4, Opcode::Compare).b().SrcType(DataType::Type::INT64).CC(CC_NE).Inputs(0, 1);
299 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
300 }
301 BASIC_BLOCK(4, 5, 6)
302 {
303 INST(6, Opcode::Compare).b().SrcType(DataType::Type::INT64).CC(CC_EQ).Inputs(0, 1);
304 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
305 }
306 BASIC_BLOCK(5, -1)
307 {
308 INST(8, Opcode::Return).s64().Inputs(0);
309 }
310 BASIC_BLOCK(6, -1)
311 {
312 INST(9, Opcode::Return).s64().Inputs(1);
313 }
314 }
315 }
316
TEST_F(BasicBlockTest,Split)317 TEST_F(BasicBlockTest, Split)
318 {
319 GRAPH(GetGraph())
320 {
321 CONSTANT(0, 0);
322 CONSTANT(1, 1);
323
324 BASIC_BLOCK(2, 3, 4)
325 {
326 INST(2, Opcode::Add).s64().Inputs(0, 1);
327 INST(3, Opcode::Mul).s64().Inputs(0, 1);
328 INST(4, Opcode::Compare).b().CC(CC_EQ).Inputs(2, 3);
329 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
330 }
331
332 BASIC_BLOCK(3, -1)
333 {
334 INST(6, Opcode::ReturnVoid);
335 }
336 BASIC_BLOCK(4, -1)
337 {
338 INST(7, Opcode::ReturnVoid);
339 }
340 }
341 ASSERT_EQ(BB(2).GetTrueSuccessor(), &BB(3));
342 ASSERT_EQ(BB(2).GetFalseSuccessor(), &BB(4));
343 auto new_bb = BB(2).SplitBlockAfterInstruction(&INS(2), true);
344 GraphChecker(GetGraph()).Check();
345 ASSERT_EQ(BB(2).GetTrueSuccessor(), new_bb);
346 ASSERT_EQ(new_bb->GetPredsBlocks().size(), 1U);
347 ASSERT_EQ(new_bb->GetPredsBlocks().front(), &BB(2));
348 ASSERT_EQ(new_bb->GetFirstInst(), &INS(3));
349 ASSERT_EQ(new_bb->GetFirstInst()->GetNext(), &INS(4));
350 ASSERT_EQ(new_bb->GetFirstInst()->GetNext()->GetNext(), &INS(5));
351 ASSERT_EQ(BB(3).GetPredsBlocks().front(), new_bb);
352 ASSERT_EQ(BB(4).GetPredsBlocks().front(), new_bb);
353 ASSERT_EQ(new_bb->GetGuestPc(), INS(3).GetPc());
354 ASSERT_EQ(new_bb->GetTrueSuccessor(), &BB(3));
355 ASSERT_EQ(new_bb->GetFalseSuccessor(), &BB(4));
356 }
357
TEST_F(BasicBlockTest,SplitByPhi1)358 TEST_F(BasicBlockTest, SplitByPhi1)
359 {
360 GRAPH(GetGraph())
361 {
362 CONSTANT(0, 0); // initial
363 CONSTANT(1, 1); // increment
364 CONSTANT(2, 10); // len_array
365 PARAMETER(13, 0).s32(); // X
366 BASIC_BLOCK(2, 3, 6)
367 {
368 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
369 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
370 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
371 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
372 }
373 BASIC_BLOCK(3, 3, 6)
374 {
375 INST(4, Opcode::Phi).s32().Inputs(0, 10);
376 INST(20, Opcode::Phi).s32().Inputs(0, 21);
377 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
378 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
379 INST(9, Opcode::LoadArray).s32().Inputs(3, 8); // a[i]
380 INST(21, Opcode::Add).s32().Inputs(20, 9);
381 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
382 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
383 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
384 }
385 BASIC_BLOCK(6, 1)
386 {
387 INST(22, Opcode::Phi).s32().Inputs(0, 21);
388 INST(12, Opcode::Return).s32().Inputs(22);
389 }
390 }
391 BB(3).SplitBlockAfterInstruction(&INS(20), true);
392 auto graph1 = CreateEmptyGraph();
393 GRAPH(graph1)
394 {
395 CONSTANT(0, 0); // initial
396 CONSTANT(1, 1); // increment
397 CONSTANT(2, 10); // len_array
398 PARAMETER(13, 0).s32(); // X
399 BASIC_BLOCK(2, 3, 6)
400 {
401 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
402 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
403 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
404 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
405 }
406 BASIC_BLOCK(3, 7)
407 {
408 INST(4, Opcode::Phi).s32().Inputs(0, 10);
409 INST(20, Opcode::Phi).s32().Inputs(0, 21);
410 }
411 BASIC_BLOCK(7, 3, 6)
412 {
413 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
414 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
415 INST(9, Opcode::LoadArray).s32().Inputs(3, 8); // a[i]
416 INST(21, Opcode::Add).s32().Inputs(20, 9);
417 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
418 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
419 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
420 }
421 BASIC_BLOCK(6, 1)
422 {
423 INST(22, Opcode::Phi).s32().Inputs(0, 21);
424 INST(12, Opcode::Return).s32().Inputs(22);
425 }
426 }
427 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph1));
428 }
429
TEST_F(BasicBlockTest,DisconnectPhiWithInputItself)430 TEST_F(BasicBlockTest, DisconnectPhiWithInputItself)
431 {
432 GRAPH(GetGraph())
433 {
434 PARAMETER(0, 0).s32();
435 PARAMETER(1, 1).s32();
436 CONSTANT(2, 0);
437 BASIC_BLOCK(3, 4)
438 {
439 INST(3, Opcode::Add).s32().Inputs(0, 1);
440 }
441 BASIC_BLOCK(4, 4, 5)
442 {
443 INST(4, Opcode::Phi).s32().Inputs(3, 4);
444 INST(5, Opcode::Compare).CC(CC_GT).b().Inputs(4, 2);
445 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
446 }
447 BASIC_BLOCK(5, 1)
448 {
449 INST(10, Opcode::Return).s32().Inputs(4);
450 }
451 }
452
453 GetGraph()->DisconnectBlock(&BB(3));
454 GetGraph()->DisconnectBlock(&BB(4));
455 GetGraph()->DisconnectBlock(&BB(5));
456
457 ASSERT_TRUE(GetGraph()->GetStartBlock()->GetSuccsBlocks().empty());
458 ASSERT_TRUE(GetGraph()->GetEndBlock()->GetPredsBlocks().empty());
459 }
460 } // namespace panda::compiler
461