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 // The arch isn`t supported
268 if (GetGraph()->GetCallingConvention() == nullptr) {
269 return;
270 }
271
272 RegAlloc(GetGraph());
273 ASSERT_EQ(GetGraph()->GetAnalysis<LinearOrder>().IsValid(), false);
274 const auto &blocks = GetGraph()->GetBlocksLinearOrder();
275 ASSERT_EQ(GetGraph()->GetAnalysis<LinearOrder>().IsValid(), true);
276 GraphChecker(GetGraph()).Check();
277 CheckBlockFalseSuccessorPosition(&BB(2), blocks);
278 CheckBlockFalseSuccessorPosition(&BB(3), blocks);
279 ASSERT_EQ(BB(5).GetLastInst(), &INS(8));
280 }
281
282 /*
283 * [entry]
284 * |
285 * v
286 * /-------[2]
287 * | |
288 * | v
289 * [3] [4]
290 * | |
291 * \--------\------>[5]------\
292 * | | |
293 * | | v
294 * \--------\------>[6]--->[exit]
295 *
296 */
TEST_F(BasicBlockTest,IfTrueInsertFalseBlock)297 TEST_F(BasicBlockTest, IfTrueInsertFalseBlock)
298 {
299 GRAPH(GetGraph())
300 {
301 CONSTANT(0, 0);
302 CONSTANT(1, 1);
303
304 BASIC_BLOCK(2, 3, 4)
305 {
306 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).CC(CC_EQ).Inputs(0, 1);
307 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
308 }
309 BASIC_BLOCK(3, 5, 6)
310 {
311 INST(4, Opcode::Compare).b().SrcType(DataType::Type::INT64).CC(CC_NE).Inputs(0, 1);
312 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
313 }
314 BASIC_BLOCK(4, 5, 6)
315 {
316 INST(6, Opcode::Compare).b().SrcType(DataType::Type::INT64).CC(CC_EQ).Inputs(0, 1);
317 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
318 }
319 BASIC_BLOCK(5, -1)
320 {
321 INST(8, Opcode::Return).s64().Inputs(0);
322 }
323 BASIC_BLOCK(6, -1)
324 {
325 INST(9, Opcode::Return).s64().Inputs(1);
326 }
327 }
328 // The arch isn`t supported
329 if (GetGraph()->GetCallingConvention() == nullptr) {
330 return;
331 }
332
333 RegAlloc(GetGraph());
334 ASSERT_EQ(GetGraph()->GetAnalysis<LinearOrder>().IsValid(), false);
335 const auto &blocks = GetGraph()->GetBlocksLinearOrder();
336 ASSERT_EQ(GetGraph()->GetAnalysis<LinearOrder>().IsValid(), true);
337 GraphChecker(GetGraph()).Check();
338 CheckBlockFalseSuccessorPosition(&BB(2), blocks);
339 CheckBlockFalseSuccessorPosition(&BB(3), blocks);
340 CheckBlockFalseSuccessorPosition(&BB(4), blocks);
341 }
342
TEST_F(BasicBlockTest,Split)343 TEST_F(BasicBlockTest, Split)
344 {
345 GRAPH(GetGraph())
346 {
347 CONSTANT(0, 0);
348 CONSTANT(1, 1);
349
350 BASIC_BLOCK(2, 3, 4)
351 {
352 INST(2, Opcode::Add).s64().Inputs(0, 1);
353 INST(3, Opcode::Mul).s64().Inputs(0, 1);
354 INST(4, Opcode::Compare).b().CC(CC_EQ).Inputs(2, 3);
355 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
356 }
357
358 BASIC_BLOCK(3, -1)
359 {
360 INST(6, Opcode::ReturnVoid);
361 }
362 BASIC_BLOCK(4, -1)
363 {
364 INST(7, Opcode::ReturnVoid);
365 }
366 }
367 ASSERT_EQ(BB(2).GetTrueSuccessor(), &BB(3));
368 ASSERT_EQ(BB(2).GetFalseSuccessor(), &BB(4));
369 auto new_bb = BB(2).SplitBlockAfterInstruction(&INS(2), true);
370 GraphChecker(GetGraph()).Check();
371 ASSERT_EQ(BB(2).GetTrueSuccessor(), new_bb);
372 ASSERT_EQ(new_bb->GetPredsBlocks().size(), 1U);
373 ASSERT_EQ(new_bb->GetPredsBlocks().front(), &BB(2));
374 ASSERT_EQ(new_bb->GetFirstInst(), &INS(3));
375 ASSERT_EQ(new_bb->GetFirstInst()->GetNext(), &INS(4));
376 ASSERT_EQ(new_bb->GetFirstInst()->GetNext()->GetNext(), &INS(5));
377 ASSERT_EQ(BB(3).GetPredsBlocks().front(), new_bb);
378 ASSERT_EQ(BB(4).GetPredsBlocks().front(), new_bb);
379 ASSERT_EQ(new_bb->GetGuestPc(), INS(3).GetPc());
380 ASSERT_EQ(new_bb->GetTrueSuccessor(), &BB(3));
381 ASSERT_EQ(new_bb->GetFalseSuccessor(), &BB(4));
382 }
383
TEST_F(BasicBlockTest,SplitByPhi1)384 TEST_F(BasicBlockTest, SplitByPhi1)
385 {
386 GRAPH(GetGraph())
387 {
388 CONSTANT(0, 0); // initial
389 CONSTANT(1, 1); // increment
390 CONSTANT(2, 10); // len_array
391 PARAMETER(13, 0).s32(); // X
392 BASIC_BLOCK(2, 3, 6)
393 {
394 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
395 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
396 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
397 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
398 }
399 BASIC_BLOCK(3, 3, 6)
400 {
401 INST(4, Opcode::Phi).s32().Inputs(0, 10);
402 INST(20, Opcode::Phi).s32().Inputs(0, 21);
403 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
404 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
405 INST(9, Opcode::LoadArray).s32().Inputs(3, 8); // a[i]
406 INST(21, Opcode::Add).s32().Inputs(20, 9);
407 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
408 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
409 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
410 }
411 BASIC_BLOCK(6, 1)
412 {
413 INST(22, Opcode::Phi).s32().Inputs(0, 21);
414 INST(12, Opcode::Return).s32().Inputs(22);
415 }
416 }
417 BB(3).SplitBlockAfterInstruction(&INS(20), true);
418 auto graph1 = CreateEmptyGraph();
419 GRAPH(graph1)
420 {
421 CONSTANT(0, 0); // initial
422 CONSTANT(1, 1); // increment
423 CONSTANT(2, 10); // len_array
424 PARAMETER(13, 0).s32(); // X
425 BASIC_BLOCK(2, 3, 6)
426 {
427 INST(44, Opcode::LoadAndInitClass).ref().Inputs().TypeId(68);
428 INST(3, Opcode::NewArray).ref().Inputs(44, 2);
429 INST(14, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(0, 13); // i < X
430 INST(15, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(14);
431 }
432 BASIC_BLOCK(3, 7)
433 {
434 INST(4, Opcode::Phi).s32().Inputs(0, 10);
435 INST(20, Opcode::Phi).s32().Inputs(0, 21);
436 }
437 BASIC_BLOCK(7, 3, 6)
438 {
439 INST(7, Opcode::SaveState).Inputs(0, 1, 2, 3).SrcVregs({0, 1, 2, 3});
440 INST(8, Opcode::BoundsCheck).s32().Inputs(2, 4, 7);
441 INST(9, Opcode::LoadArray).s32().Inputs(3, 8); // a[i]
442 INST(21, Opcode::Add).s32().Inputs(20, 9);
443 INST(10, Opcode::Add).s32().Inputs(4, 1); // i++
444 INST(5, Opcode::Compare).CC(ConditionCode::CC_LT).b().Inputs(10, 13); // i < X
445 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
446 }
447 BASIC_BLOCK(6, 1)
448 {
449 INST(22, Opcode::Phi).s32().Inputs(0, 21);
450 INST(12, Opcode::Return).s32().Inputs(22);
451 }
452 }
453 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph1));
454 }
455
TEST_F(BasicBlockTest,DisconnectPhiWithInputItself)456 TEST_F(BasicBlockTest, DisconnectPhiWithInputItself)
457 {
458 GRAPH(GetGraph())
459 {
460 PARAMETER(0, 0).s32();
461 PARAMETER(1, 1).s32();
462 CONSTANT(2, 0);
463 BASIC_BLOCK(3, 4)
464 {
465 INST(3, Opcode::Add).s32().Inputs(0, 1);
466 }
467 BASIC_BLOCK(4, 4, 5)
468 {
469 INST(4, Opcode::Phi).s32().Inputs(3, 4);
470 INST(5, Opcode::Compare).CC(CC_GT).b().Inputs(4, 2);
471 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
472 }
473 BASIC_BLOCK(5, 1)
474 {
475 INST(10, Opcode::Return).s32().Inputs(4);
476 }
477 }
478
479 GetGraph()->DisconnectBlock(&BB(3));
480 GetGraph()->DisconnectBlock(&BB(4));
481 GetGraph()->DisconnectBlock(&BB(5));
482
483 ASSERT_TRUE(GetGraph()->GetStartBlock()->GetSuccsBlocks().empty());
484 ASSERT_TRUE(GetGraph()->GetEndBlock()->GetPredsBlocks().empty());
485 }
486 } // namespace panda::compiler
487