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 "unit_test.h"
17 #include "optimizer/optimizations/branch_elimination.h"
18 #include "optimizer/optimizations/cleanup.h"
19
20 namespace panda::compiler {
21 enum class RemainedSuccessor { TRUE_SUCCESSOR, FALSE_SUCCESSOR, BOTH };
22 enum class DominantCondResult { FALSE, TRUE };
23 enum class SwapInputs { FALSE, TRUE };
24 enum class SwapCC { FALSE, TRUE };
25
26 class BranchEliminationTest : public GraphTest {
27 public:
28 template <uint64_t CONST_CONDITION_BLOCK_ID, uint64_t CONST_VALUE, SwapCC swap_cc = SwapCC::FALSE>
29 void BuildTestGraph(Graph *graph);
30
31 template <uint64_t CONST_CONDITION_BLOCK_ID, uint64_t CONST_VALUE>
32 void BuildTestGraph2(Graph *graph);
33
34 template <DominantCondResult dom_result, RemainedSuccessor elim_succ, SwapInputs swap_inputs = SwapInputs::FALSE>
35 void BuildGraphAndCheckElimination(ConditionCode dominant_code, ConditionCode code);
36
37 template <DominantCondResult dom_result, SwapInputs swap_inputs>
38 void BuildContitionsCheckGraph(Graph *graph, ConditionCode dominant_code, ConditionCode code);
39 template <DominantCondResult dom_result, SwapInputs swap_inputs>
40 void BuildContitionsCheckGraphElimTrueSucc(Graph *graph, ConditionCode dominant_code, ConditionCode code);
41 template <DominantCondResult dom_result, SwapInputs swap_inputs>
42 void BuildContitionsCheckGraphElimFalseSucc(Graph *graph, ConditionCode dominant_code, ConditionCode code);
43
44 protected:
InitBlockToBeDisconnected(std::vector<BasicBlock * > && blocks)45 void InitBlockToBeDisconnected(std::vector<BasicBlock *> &&blocks)
46 {
47 disconnected_blocks_ = std::move(blocks);
48 removed_instructions_.clear();
49 for (const auto &block : disconnected_blocks_) {
50 for (auto inst : block->AllInsts()) {
51 removed_instructions_.push_back(inst);
52 }
53 }
54 }
55
CheckBlocksDisconnected()56 void CheckBlocksDisconnected()
57 {
58 for (const auto &block : disconnected_blocks_) {
59 EXPECT_TRUE(block->GetGraph() == nullptr);
60 EXPECT_TRUE(block->IsEmpty());
61 EXPECT_EQ(block->GetSuccsBlocks().size(), 0U);
62 EXPECT_EQ(block->GetPredsBlocks().size(), 0U);
63 for (auto inst : block->AllInsts()) {
64 EXPECT_TRUE(inst->GetBasicBlock() == nullptr);
65 EXPECT_TRUE(inst->GetUsers().Empty());
66 for (auto input : inst->GetInputs()) {
67 EXPECT_TRUE(input.GetInst() == nullptr);
68 }
69 }
70 }
71 }
72
73 private:
74 std::vector<BasicBlock *> disconnected_blocks_;
75 std::vector<Inst *> removed_instructions_;
76 };
77
78 /*
79 * [0]
80 * |
81 * /----[2]----\
82 * | |
83 * v v
84 * [3] /----[4]----\
85 * | | |
86 * | [5] [6]
87 * | | |
88 * v v |
89 * [exit]<-------------/
90 */
91 template <uint64_t CONST_CONDITION_BLOCK_ID, uint64_t CONST_VALUE, SwapCC swap_cc>
BuildTestGraph(Graph * graph)92 void BranchEliminationTest::BuildTestGraph(Graph *graph)
93 {
94 GRAPH(graph)
95 {
96 PARAMETER(0, 0).u64();
97 PARAMETER(1, 1).u64();
98 PARAMETER(2, 2).u64();
99 CONSTANT(3, CONST_VALUE);
100
101 BASIC_BLOCK(2, 3, 4)
102 {
103 INST(19, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
104 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(19);
105 }
106 BASIC_BLOCK(3, 7)
107 {
108 INST(5, Opcode::Add).u64().Inputs(0, 1);
109 INST(6, Opcode::Add).u64().Inputs(5, 2);
110 }
111 BASIC_BLOCK(4, 5, 6)
112 {
113 INST(9, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 2);
114 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
115 }
116 BASIC_BLOCK(5, 7)
117 {
118 INST(11, Opcode::Sub).u64().Inputs(0, 1);
119 INST(12, Opcode::Sub).u64().Inputs(11, 2);
120 }
121 BASIC_BLOCK(6, 7)
122 {
123 INST(14, Opcode::Mul).u64().Inputs(0, 1);
124 INST(15, Opcode::Mul).u64().Inputs(14, 2);
125 }
126 BASIC_BLOCK(7, -1)
127 {
128 INST(17, Opcode::Phi).u64().Inputs(6, 12, 15);
129 INST(18, Opcode::Return).u64().Inputs(17);
130 }
131 }
132
133 auto inst_if = BB(CONST_CONDITION_BLOCK_ID).GetLastInst();
134 ASSERT_TRUE(inst_if->GetOpcode() == Opcode::IfImm);
135 inst_if->SetInput(0, &INS(3));
136
137 if constexpr (swap_cc == SwapCC::TRUE) {
138 INS(4).CastToIfImm()->SetCc(CC_EQ);
139 INS(10).CastToIfImm()->SetCc(CC_EQ);
140 }
141 }
142
143 /*
144 * [0]
145 * |
146 * /-----[2]-----\
147 * | |
148 * | v
149 * | /----[4]----\
150 * | | |
151 * [3]---->[5] [6]
152 * | | |
153 * v v |
154 * [exit]<---------------/
155 */
156 template <uint64_t CONST_CONDITION_BLOCK_ID, uint64_t CONST_VALUE>
BuildTestGraph2(Graph * graph)157 void BranchEliminationTest::BuildTestGraph2(Graph *graph)
158 {
159 GRAPH(graph)
160 {
161 PARAMETER(0, 0).u64();
162 PARAMETER(1, 1).u64();
163 PARAMETER(2, 2).u64();
164 CONSTANT(3, CONST_VALUE);
165
166 BASIC_BLOCK(2, 3, 4)
167 {
168 INST(19, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
169 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(19);
170 }
171 BASIC_BLOCK(3, 7, 5)
172 {
173 INST(5, Opcode::Add).u64().Inputs(0, 1);
174 INST(6, Opcode::Add).u64().Inputs(5, 2);
175 INST(20, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 2);
176 INST(21, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(20);
177 }
178 BASIC_BLOCK(4, 5, 6)
179 {
180 INST(9, Opcode::Compare).b().CC(CC_EQ).Inputs(1, 2);
181 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
182 }
183 BASIC_BLOCK(5, 7)
184 {
185 INST(11, Opcode::Phi).u64().Inputs(0, 1);
186 INST(12, Opcode::Sub).u64().Inputs(11, 2);
187 }
188 BASIC_BLOCK(6, 7)
189 {
190 INST(14, Opcode::Mul).u64().Inputs(0, 1);
191 INST(15, Opcode::Mul).u64().Inputs(14, 2);
192 }
193 BASIC_BLOCK(7, -1)
194 {
195 INST(17, Opcode::Phi).u64().Inputs(6, 12, 15);
196 INST(18, Opcode::Return).u64().Inputs(17);
197 }
198 }
199 auto inst_if = BB(CONST_CONDITION_BLOCK_ID).GetLastInst();
200 ASSERT_TRUE(inst_if->GetOpcode() == Opcode::IfImm);
201 inst_if->SetInput(0, &INS(3));
202 }
203
204 /*
205 * [0]
206 * |
207 * /----[2]----\
208 * | |
209 * v v
210 * [3] /----[4]----\
211 * | | |
212 * | [5] [6]
213 * | | |
214 * v v |
215 * [exit]<-------------/
216 *
217 * Disconnect branch: [4, 5, 6]
218 */
TEST_F(BranchEliminationTest,DisconnectFalseBranch)219 TEST_F(BranchEliminationTest, DisconnectFalseBranch)
220 {
221 static constexpr uint64_t CONST_CONDITION_BLOCK_ID = 2;
222 static constexpr uint64_t CONSTANT_VALUE = 1;
223 BuildTestGraph<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE>(GetGraph());
224 InitBlockToBeDisconnected({&BB(4), &BB(5), &BB(6)});
225
226 GetGraph()->RunPass<BranchElimination>();
227 CheckBlocksDisconnected();
228 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 1U);
229 EXPECT_EQ(BB(2).GetSuccessor(0), &BB(3));
230 EXPECT_FALSE(INS(17).HasUsers());
231 EXPECT_EQ(INS(18).GetInput(0).GetInst(), &INS(6));
232
233 auto graph = CreateEmptyGraph();
234 BuildTestGraph<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE, SwapCC::TRUE>(graph);
235 InitBlockToBeDisconnected({&BB(3)});
236 graph->RunPass<BranchElimination>();
237 CheckBlocksDisconnected();
238 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 1U);
239 EXPECT_EQ(BB(2).GetSuccessor(0), &BB(4));
240
241 auto phi = &INS(17);
242 EXPECT_TRUE(phi->HasUsers());
243 EXPECT_EQ(phi->GetInputsCount(), 2U);
244 EXPECT_EQ(INS(12).GetUsers().Front().GetInst(), phi);
245 EXPECT_EQ(INS(15).GetUsers().Front().GetInst(), phi);
246 }
247
248 /*
249 * [0]
250 * |
251 * /----[2]----\
252 * | |
253 * v v
254 * [3] /----[4]----\
255 * | | |
256 * | [5] [6]
257 * | | |
258 * v v |
259 * [exit]<-------------/
260 *
261 * Disconnect branch: [3]
262 */
TEST_F(BranchEliminationTest,DisconnectTrueBranch)263 TEST_F(BranchEliminationTest, DisconnectTrueBranch)
264 {
265 static constexpr uint64_t CONST_CONDITION_BLOCK_ID = 2;
266 static constexpr uint64_t CONSTANT_VALUE = 0;
267 BuildTestGraph<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE>(GetGraph());
268 InitBlockToBeDisconnected({&BB(3)});
269
270 GetGraph()->RunPass<BranchElimination>();
271 CheckBlocksDisconnected();
272 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 1U);
273 EXPECT_EQ(BB(2).GetSuccessor(0), &BB(4));
274
275 auto phi = &INS(17);
276 EXPECT_TRUE(phi->HasUsers());
277 EXPECT_EQ(phi->GetInputsCount(), 2U);
278 EXPECT_EQ(INS(12).GetUsers().Front().GetInst(), phi);
279 EXPECT_EQ(INS(15).GetUsers().Front().GetInst(), phi);
280
281 auto graph = CreateEmptyGraph();
282 BuildTestGraph<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE, SwapCC::TRUE>(graph);
283 InitBlockToBeDisconnected({&BB(4), &BB(5), &BB(6)});
284
285 graph->RunPass<BranchElimination>();
286 CheckBlocksDisconnected();
287 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 1U);
288 EXPECT_EQ(BB(2).GetSuccessor(0), &BB(3));
289 EXPECT_FALSE(INS(17).HasUsers());
290 EXPECT_EQ(INS(18).GetInput(0).GetInst(), &INS(6));
291 }
292
293 /*
294 * [0]
295 * |
296 * /----[2]----\
297 * | |
298 * v v
299 * [3] /----[4]----\
300 * | | |
301 * | [5] [6]
302 * | | |
303 * v v |
304 * [exit]<-------------/
305 *
306 * Disconnect branch: [6]
307 */
TEST_F(BranchEliminationTest,DisconnectInnerFalseBranch)308 TEST_F(BranchEliminationTest, DisconnectInnerFalseBranch)
309 {
310 static constexpr uint64_t CONST_CONDITION_BLOCK_ID = 4;
311 static constexpr uint64_t CONSTANT_VALUE = 1;
312 BuildTestGraph<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE>(GetGraph());
313 InitBlockToBeDisconnected({&BB(6)});
314
315 GetGraph()->RunPass<BranchElimination>();
316 CheckBlocksDisconnected();
317 EXPECT_EQ(BB(4).GetSuccsBlocks().size(), 1U);
318 EXPECT_EQ(BB(4).GetSuccessor(0), &BB(5));
319
320 auto phi = &INS(17);
321 EXPECT_TRUE(phi->HasUsers());
322 EXPECT_EQ(phi->GetInputsCount(), 2U);
323 EXPECT_EQ(INS(6).GetUsers().Front().GetInst(), phi);
324 EXPECT_EQ(INS(12).GetUsers().Front().GetInst(), phi);
325 }
326
327 /*
328 * [0]
329 * |
330 * /----[2]----\
331 * | |
332 * v v
333 * [3] /----[4]----\
334 * | | |
335 * | [5] [6]
336 * | | |
337 * v v |
338 * [exit]<-------------/
339 *
340 * Disconnect branch: [5]
341 */
TEST_F(BranchEliminationTest,DisconnectInnerTrueBranch)342 TEST_F(BranchEliminationTest, DisconnectInnerTrueBranch)
343 {
344 static constexpr uint64_t CONST_CONDITION_BLOCK_ID = 4;
345 static constexpr uint64_t CONSTANT_VALUE = 0;
346 BuildTestGraph<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE>(GetGraph());
347 InitBlockToBeDisconnected({&BB(5)});
348
349 GetGraph()->RunPass<BranchElimination>();
350 CheckBlocksDisconnected();
351 EXPECT_EQ(BB(4).GetSuccsBlocks().size(), 1U);
352 EXPECT_EQ(BB(4).GetSuccessor(0), &BB(6));
353
354 auto phi = &INS(17);
355 EXPECT_TRUE(phi->HasUsers());
356 EXPECT_EQ(phi->GetInputsCount(), 2U);
357 EXPECT_EQ(INS(6).GetUsers().Front().GetInst(), phi);
358 EXPECT_EQ(INS(15).GetUsers().Front().GetInst(), phi);
359 }
360
361 /*
362 * [0]
363 * |
364 * /-----[2]-----\
365 * | |
366 * | v
367 * | /----[4]----\
368 * | | |
369 * [3]---->[5] [6]
370 * | | |
371 * v v |
372 * [exit]<---------------/
373 *
374 * Disconnect branch: [4, 6]
375 */
TEST_F(BranchEliminationTest,RemoveBranchPart)376 TEST_F(BranchEliminationTest, RemoveBranchPart)
377 {
378 static constexpr uint64_t CONST_CONDITION_BLOCK_ID = 2;
379 static constexpr uint64_t CONSTANT_VALUE = 1;
380 BuildTestGraph2<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE>(GetGraph());
381 InitBlockToBeDisconnected({&BB(4), &BB(6)});
382
383 GetGraph()->RunPass<BranchElimination>();
384 CheckBlocksDisconnected();
385 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 1U);
386 EXPECT_EQ(BB(2).GetSuccessor(0), &BB(3));
387 EXPECT_EQ(BB(5).GetPredsBlocks().size(), 1U);
388 EXPECT_EQ(BB(5).GetPredBlockByIndex(0), &BB(3));
389
390 auto phi = &INS(17);
391 EXPECT_TRUE(phi->HasUsers());
392 EXPECT_EQ(phi->GetInputsCount(), 2U);
393 EXPECT_EQ(INS(6).GetUsers().Front().GetInst(), phi);
394 EXPECT_EQ(INS(12).GetUsers().Front().GetInst(), phi);
395 }
396
397 /*
398 * [0]
399 * |
400 * /-----[2]-----\
401 * | |
402 * | v
403 * | /----[4]----\
404 * | | |
405 * [3]---->[5] [6]
406 * | | |
407 * v v |
408 * [exit]<---------------/
409 *
410 * Remove edge between [4] and [5]
411 */
TEST_F(BranchEliminationTest,RemoveEdge)412 TEST_F(BranchEliminationTest, RemoveEdge)
413 {
414 static constexpr uint64_t CONST_CONDITION_BLOCK_ID = 4;
415 static constexpr uint64_t CONSTANT_VALUE = 0;
416 BuildTestGraph2<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE>(GetGraph());
417
418 GetGraph()->RunPass<BranchElimination>();
419
420 EXPECT_EQ(BB(4).GetSuccsBlocks().size(), 1U);
421 EXPECT_EQ(BB(4).GetSuccessor(0), &BB(6));
422 EXPECT_EQ(BB(5).GetPredsBlocks().size(), 1U);
423 EXPECT_EQ(BB(5).GetPredBlockByIndex(0), &BB(3));
424
425 auto phi = &INS(17);
426 EXPECT_TRUE(phi->HasUsers());
427 EXPECT_EQ(phi->GetInputsCount(), 3U);
428 EXPECT_EQ(INS(6).GetUsers().Front().GetInst(), phi);
429 EXPECT_EQ(INS(12).GetUsers().Front().GetInst(), phi);
430 EXPECT_EQ(INS(15).GetUsers().Front().GetInst(), phi);
431 }
432
433 /*
434 * [0]
435 * |
436 * /-----[2]-----\
437 * | |
438 * | v
439 * | /----[4]----\
440 * | | |
441 * [3]---->[5] [6]
442 * | | |
443 * v v |
444 * [exit]<---------------/
445 *
446 * Remove branches [3-5] and [4-5]
447 *
448 * [0]
449 * |
450 * [2]
451 * |
452 * [4]
453 * |
454 * [6]
455 * |
456 * [exit]
457 */
TEST_F(BranchEliminationTest,RemoveEdgeAndWholeBlock)458 TEST_F(BranchEliminationTest, RemoveEdgeAndWholeBlock)
459 {
460 static constexpr uint64_t CONST_CONDITION_BLOCK_ID = 2;
461 static constexpr uint64_t CONSTANT_VALUE = 0;
462 BuildTestGraph2<CONST_CONDITION_BLOCK_ID, CONSTANT_VALUE>(GetGraph());
463 BB(4).GetLastInst()->SetInput(0, &INS(3));
464 InitBlockToBeDisconnected({&BB(3), &BB(5)});
465
466 GetGraph()->RunPass<BranchElimination>();
467 CheckBlocksDisconnected();
468
469 EXPECT_EQ(BB(0).GetSuccsBlocks().size(), 1U);
470 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 1U);
471 EXPECT_EQ(BB(4).GetSuccsBlocks().size(), 1U);
472 EXPECT_EQ(BB(6).GetSuccsBlocks().size(), 1U);
473
474 auto phi = &INS(17);
475 EXPECT_FALSE(phi->HasUsers());
476 }
477
478 /*
479 * [0]
480 * |
481 * /-----[2]-----\
482 * | |
483 * v v
484 * /----[3]----\ /----[4]----\
485 * | | | |
486 * [5] [6][7] [8]
487 * | | | |
488 * | v v |
489 * | [9] |
490 * | v |
491 * \--------->[exit]<---------/
492 *
493 * Remove branches [3-6], [4-7] and as a result remove block [9]
494 */
TEST_F(BranchEliminationTest,DisconnectPredecessors)495 TEST_F(BranchEliminationTest, DisconnectPredecessors)
496 {
497 GRAPH(GetGraph())
498 {
499 PARAMETER(0, 0).b();
500 PARAMETER(1, 1).u64();
501 PARAMETER(2, 2).u64();
502 CONSTANT(3, 0);
503 CONSTANT(4, 1);
504
505 BASIC_BLOCK(2, 3, 4)
506 {
507 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(0);
508 }
509 BASIC_BLOCK(3, 5, 6)
510 {
511 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
512 }
513 BASIC_BLOCK(4, 7, 8)
514 {
515 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
516 }
517 BASIC_BLOCK(6, 9) {}
518 BASIC_BLOCK(7, 9) {}
519 BASIC_BLOCK(5, 10)
520 {
521 INST(10, Opcode::Add).u64().Inputs(1, 2);
522 }
523 BASIC_BLOCK(8, 10)
524 {
525 INST(12, Opcode::Sub).u64().Inputs(1, 2);
526 }
527 BASIC_BLOCK(9, 10)
528 {
529 INST(14, Opcode::Mul).u64().Inputs(1, 2);
530 }
531 BASIC_BLOCK(10, -1)
532 {
533 INST(16, Opcode::Phi).u64().Inputs(10, 12, 14);
534 INST(17, Opcode::Return).u64().Inputs(16);
535 }
536 }
537
538 InitBlockToBeDisconnected({&BB(6), &BB(7), &BB(9)});
539
540 GetGraph()->RunPass<BranchElimination>();
541 CheckBlocksDisconnected();
542
543 EXPECT_EQ(BB(3).GetSuccsBlocks().size(), 1U);
544 EXPECT_EQ(BB(3).GetSuccessor(0), &BB(5));
545 EXPECT_EQ(BB(4).GetSuccsBlocks().size(), 1U);
546 EXPECT_EQ(BB(4).GetSuccessor(0), &BB(8));
547 EXPECT_EQ(BB(10).GetPredsBlocks().size(), 2U);
548
549 auto phi = &INS(16);
550 EXPECT_EQ(phi->GetInputsCount(), 2U);
551 EXPECT_EQ(INS(10).GetUsers().Front().GetInst(), phi);
552 EXPECT_EQ(INS(12).GetUsers().Front().GetInst(), phi);
553 }
554
555 /*
556 * [0]
557 * |
558 * v
559 * /--->[2]----\
560 * | | |
561 * | v v
562 * \----[3] [exit]
563 *
564 * Remove [3]
565 *
566 * [0] -> [2] -> [exit]
567 *
568 */
TEST_F(BranchEliminationTest,RemoveLoopBackEdge)569 TEST_F(BranchEliminationTest, RemoveLoopBackEdge)
570 {
571 GRAPH(GetGraph())
572 {
573 PARAMETER(0, 0).b();
574 PARAMETER(1, 1).u64();
575 PARAMETER(2, 2).u64();
576 CONSTANT(3, 0);
577
578 BASIC_BLOCK(2, 3, 4)
579 {
580 INST(5, Opcode::Phi).u64().Inputs(1, 9);
581 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
582 }
583 BASIC_BLOCK(3, 2)
584 {
585 INST(8, Opcode::Add).u64().Inputs(5, 2);
586 INST(9, Opcode::Add).u64().Inputs(8, 2);
587 }
588 BASIC_BLOCK(4, -1)
589 {
590 INST(11, Opcode::Return).u64().Inputs(5);
591 }
592 }
593
594 InitBlockToBeDisconnected({&BB(3)});
595
596 GetGraph()->RunPass<BranchElimination>();
597 CheckBlocksDisconnected();
598 EXPECT_EQ(BB(0).GetSuccsBlocks().size(), 1U);
599 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 1U);
600 EXPECT_EQ(INS(11).GetInput(0).GetInst(), &INS(1));
601 }
602
603 /*
604 * [0]
605 * |
606 * v
607 * /--->[2]
608 * | | \
609 * | | \
610 * \----/ \
611 * |
612 * v
613 * [exit]
614 *
615 * Remove loop edge [2->2]
616 *
617 * [0] -> [2] -> [exit]
618 */
TEST_F(BranchEliminationTest,RemoveOneBlockLoopExit)619 TEST_F(BranchEliminationTest, RemoveOneBlockLoopExit)
620 {
621 GRAPH(GetGraph())
622 {
623 PARAMETER(0, 0).b();
624 PARAMETER(1, 1).u64();
625 PARAMETER(2, 2).u64();
626 CONSTANT(3, 0);
627
628 BASIC_BLOCK(2, 2, 4)
629 {
630 INST(5, Opcode::Phi).u64().Inputs(1, 9);
631 INST(8, Opcode::Add).u64().Inputs(5, 2);
632 INST(9, Opcode::Add).u64().Inputs(8, 2);
633 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
634 }
635 BASIC_BLOCK(4, -1)
636 {
637 INST(11, Opcode::Return).u64().Inputs(9);
638 }
639 }
640
641 GetGraph()->RunPass<BranchElimination>();
642
643 EXPECT_EQ(BB(0).GetSuccsBlocks().size(), 1U);
644 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 1U);
645
646 EXPECT_FALSE(INS(5).HasUsers());
647 EXPECT_TRUE(INS(8).HasUsers());
648 EXPECT_TRUE(INS(9).HasUsers());
649 EXPECT_EQ(INS(8).GetInput(0).GetInst(), &INS(1));
650 }
651
652 /*
653 * [0]
654 * |
655 * v
656 * /--->[2]
657 * | |
658 * | v
659 * \----[3]----\
660 * |
661 * v
662 * [exit]
663 *
664 * Remove edge [3-2]
665 *
666 * [0] -> [2] -> [3] -> [exit]
667 */
TEST_F(BranchEliminationTest,RemoveLoopExit)668 TEST_F(BranchEliminationTest, RemoveLoopExit)
669 {
670 GRAPH(GetGraph())
671 {
672 PARAMETER(0, 0).b();
673 PARAMETER(1, 1).u64();
674 PARAMETER(2, 2).u64();
675 CONSTANT(3, 0);
676
677 BASIC_BLOCK(2, 5, 6)
678 {
679 INST(5, Opcode::Phi).u64().Inputs(1, 9);
680 INST(20, Opcode::SaveState).NoVregs();
681 INST(7, Opcode::CallStatic).v0id().InputsAutoType(20);
682 INST(4, Opcode::If).SrcType(DataType::Type::UINT64).CC(CC_NE).Inputs(1, 2);
683 }
684 BASIC_BLOCK(5, 3)
685 {
686 INST(21, Opcode::SaveState).NoVregs();
687 INST(10, Opcode::CallStatic).v0id().InputsAutoType(21);
688 }
689 BASIC_BLOCK(6, 3)
690 {
691 INST(22, Opcode::SaveState).NoVregs();
692 INST(11, Opcode::CallStatic).v0id().InputsAutoType(22);
693 }
694 BASIC_BLOCK(3, 2, 4)
695 {
696 INST(8, Opcode::Add).u64().Inputs(5, 2);
697 INST(9, Opcode::Add).u64().Inputs(8, 2);
698 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
699 }
700 BASIC_BLOCK(4, -1)
701 {
702 INST(12, Opcode::Return).u64().Inputs(9);
703 }
704 }
705
706 GetGraph()->RunPass<BranchElimination>();
707
708 EXPECT_EQ(BB(0).GetSuccsBlocks().size(), 1U);
709 EXPECT_EQ(BB(2).GetSuccsBlocks().size(), 2U);
710 EXPECT_EQ(BB(3).GetSuccsBlocks().size(), 1U);
711
712 EXPECT_FALSE(INS(5).HasUsers());
713 EXPECT_TRUE(INS(8).HasUsers());
714 EXPECT_TRUE(INS(9).HasUsers());
715 EXPECT_EQ(INS(8).GetInput(0).GetInst(), &INS(1));
716 }
717
718 /*
719 * [0]
720 * T | F
721 * /-----[2]-----\
722 * | |
723 * v v
724 * [3]<----------[4]<----\
725 * | | |
726 * v v |
727 * [exit] [5]-----/
728 *
729 * Transform to [0]-->[2]-->[exit]
730 */
TEST_F(BranchEliminationTest,RemoveEdgeToLoop)731 TEST_F(BranchEliminationTest, RemoveEdgeToLoop)
732 {
733 GRAPH(GetGraph())
734 {
735 PARAMETER(0, 0).u64();
736 PARAMETER(1, 1).u64();
737 PARAMETER(2, 2).b();
738 CONSTANT(3, 1);
739
740 BASIC_BLOCK(2, 3, 4)
741 {
742 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
743 }
744 BASIC_BLOCK(3, -1)
745 {
746 INST(5, Opcode::Phi).u64().Inputs(0, 7);
747 INST(6, Opcode::Return).u64().Inputs(5);
748 }
749 BASIC_BLOCK(4, 5, 3)
750 {
751 INST(7, Opcode::Phi).u64().Inputs({{2, 0}, {5, 9}});
752 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
753 }
754 BASIC_BLOCK(5, 4)
755 {
756 INST(9, Opcode::Add).u64().Inputs(7, 0);
757 }
758 }
759 GetGraph()->RunPass<BranchElimination>();
760 GetGraph()->RunPass<Cleanup>();
761
762 auto expected_graph = CreateEmptyGraph();
763 GRAPH(expected_graph)
764 {
765 PARAMETER(0, 0).u64();
766 BASIC_BLOCK(2, -1)
767 {
768 INST(1, Opcode::Return).u64().Inputs(0);
769 }
770 }
771
772 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), expected_graph));
773 }
774
775 /*
776 * [0]
777 * T | F
778 * /----[2]----\
779 * | |
780 * v T v F
781 * [3] /----[4]----\
782 * | | |
783 * | [5] [6]
784 * | | |
785 * v v |
786 * [exit]<-------------/
787 */
788 template <DominantCondResult dom_result, SwapInputs swap_inputs>
BuildContitionsCheckGraph(Graph * graph,ConditionCode dominant_code,ConditionCode code)789 void BranchEliminationTest::BuildContitionsCheckGraph(Graph *graph, ConditionCode dominant_code, ConditionCode code)
790 {
791 GRAPH(graph)
792 {
793 PARAMETER(0, 0).u64();
794 PARAMETER(1, 1).u64();
795 PARAMETER(2, 2).u64();
796
797 BASIC_BLOCK(2, 3, 4)
798 {
799 INST(19, Opcode::Compare).b().CC(dominant_code).Inputs(0, 1);
800 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(19);
801 }
802 BASIC_BLOCK(3, 7)
803 {
804 INST(5, Opcode::Add).u64().Inputs(0, 1);
805 INST(6, Opcode::Add).u64().Inputs(5, 2);
806 }
807 BASIC_BLOCK(4, 5, 6)
808 {
809 INST(9, Opcode::Compare).b().CC(code).Inputs(0, 1);
810 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
811 }
812 BASIC_BLOCK(5, 7)
813 {
814 INST(11, Opcode::Sub).u64().Inputs(0, 1);
815 INST(12, Opcode::Sub).u64().Inputs(11, 2);
816 }
817 BASIC_BLOCK(6, 7)
818 {
819 INST(14, Opcode::Mul).u64().Inputs(0, 1);
820 INST(15, Opcode::Mul).u64().Inputs(14, 2);
821 }
822 BASIC_BLOCK(7, -1)
823 {
824 INST(17, Opcode::Phi).u64().Inputs(6, 12, 15);
825 INST(18, Opcode::Return).u64().Inputs(17);
826 }
827 }
828 if constexpr (dom_result == DominantCondResult::TRUE) {
829 BB(2).SwapTrueFalseSuccessors();
830 }
831 if constexpr (swap_inputs == SwapInputs::TRUE) {
832 INS(19).SwapInputs();
833 }
834 }
835
836 /*
837 * [0]
838 * |
839 * /----[2]----\
840 * | |
841 * v v
842 * [3] [4]
843 * | |
844 * | [5]
845 * | |
846 * v |
847 * [exit]<-------/
848 */
849 template <DominantCondResult dom_result, SwapInputs swap_inputs>
BuildContitionsCheckGraphElimFalseSucc(Graph * graph,ConditionCode dominant_code,ConditionCode code)850 void BranchEliminationTest::BuildContitionsCheckGraphElimFalseSucc(Graph *graph, ConditionCode dominant_code,
851 ConditionCode code)
852 {
853 GRAPH(graph)
854 {
855 PARAMETER(0, 0).u64();
856 PARAMETER(1, 1).u64();
857 PARAMETER(2, 2).u64();
858
859 BASIC_BLOCK(2, 3, 4)
860 {
861 INST(19, Opcode::Compare).b().CC(dominant_code).Inputs(0, 1);
862 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(19);
863 }
864 BASIC_BLOCK(3, 7)
865 {
866 INST(5, Opcode::Add).u64().Inputs(0, 1);
867 INST(6, Opcode::Add).u64().Inputs(5, 2);
868 }
869 BASIC_BLOCK(4, 5)
870 {
871 INST(9, Opcode::Compare).b().CC(code).Inputs(0, 1);
872 }
873 BASIC_BLOCK(5, 7)
874 {
875 INST(11, Opcode::Sub).u64().Inputs(0, 1);
876 INST(12, Opcode::Sub).u64().Inputs(11, 2);
877 }
878 BASIC_BLOCK(7, -1)
879 {
880 INST(17, Opcode::Phi).u64().Inputs(6, 12);
881 INST(18, Opcode::Return).u64().Inputs(17);
882 }
883 }
884 if constexpr (dom_result == DominantCondResult::TRUE) {
885 BB(2).SwapTrueFalseSuccessors();
886 }
887 if constexpr (swap_inputs == SwapInputs::TRUE) {
888 INS(19).SwapInputs();
889 }
890 }
891
892 /*
893 * [0]
894 * |
895 * /----[2]----\
896 * | |
897 * v v
898 * [3] [4]----\
899 * | |
900 * | [6]
901 * | |
902 * v |
903 * [exit]<-------------/
904 */
905 template <DominantCondResult dom_result, SwapInputs swap_inputs>
BuildContitionsCheckGraphElimTrueSucc(Graph * graph,ConditionCode dominant_code,ConditionCode code)906 void BranchEliminationTest::BuildContitionsCheckGraphElimTrueSucc(Graph *graph, ConditionCode dominant_code,
907 ConditionCode code)
908 {
909 GRAPH(graph)
910 {
911 PARAMETER(0, 0).u64();
912 PARAMETER(1, 1).u64();
913 PARAMETER(2, 2).u64();
914
915 BASIC_BLOCK(2, 3, 4)
916 {
917 INST(19, Opcode::Compare).b().CC(dominant_code).Inputs(0, 1);
918 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(19);
919 }
920 BASIC_BLOCK(3, 7)
921 {
922 INST(5, Opcode::Add).u64().Inputs(0, 1);
923 INST(6, Opcode::Add).u64().Inputs(5, 2);
924 }
925 BASIC_BLOCK(4, 6)
926 {
927 INST(9, Opcode::Compare).b().CC(code).Inputs(0, 1);
928 }
929 BASIC_BLOCK(6, 7)
930 {
931 INST(14, Opcode::Mul).u64().Inputs(0, 1);
932 INST(15, Opcode::Mul).u64().Inputs(14, 2);
933 }
934 BASIC_BLOCK(7, -1)
935 {
936 INST(17, Opcode::Phi).u64().Inputs(6, 15);
937 INST(18, Opcode::Return).u64().Inputs(17);
938 }
939 }
940 if constexpr (dom_result == DominantCondResult::TRUE) {
941 BB(2).SwapTrueFalseSuccessors();
942 }
943 if constexpr (swap_inputs == SwapInputs::TRUE) {
944 INS(19).SwapInputs();
945 }
946 }
947
948 template <DominantCondResult dom_result, RemainedSuccessor remained_succ, SwapInputs swap_inputs>
BuildGraphAndCheckElimination(ConditionCode dominant_code,ConditionCode code)949 void BranchEliminationTest::BuildGraphAndCheckElimination(ConditionCode dominant_code, ConditionCode code)
950 {
951 auto graph = CreateEmptyGraph();
952 BuildContitionsCheckGraph<dom_result, swap_inputs>(graph, dominant_code, code);
953 auto expected_graph = CreateEmptyGraph();
954 if constexpr (remained_succ == RemainedSuccessor::FALSE_SUCCESSOR) {
955 BuildContitionsCheckGraphElimTrueSucc<dom_result, swap_inputs>(expected_graph, dominant_code, code);
956 } else if constexpr (remained_succ == RemainedSuccessor::TRUE_SUCCESSOR) {
957 BuildContitionsCheckGraphElimFalseSucc<dom_result, swap_inputs>(expected_graph, dominant_code, code);
958 } else {
959 BuildContitionsCheckGraph<dom_result, swap_inputs>(expected_graph, dominant_code, code);
960 }
961
962 graph->RunPass<BranchElimination>();
963 ASSERT_TRUE(GraphComparator().Compare(graph, expected_graph));
964 }
965
TEST_F(BranchEliminationTest,EliminateByDominatedCondition)966 TEST_F(BranchEliminationTest, EliminateByDominatedCondition)
967 {
968 // dominant condition: a op1 b,
969 // dominated condition: a op2 b (reached from false successor)
970 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_EQ,
971 ConditionCode::CC_EQ);
972 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_EQ,
973 ConditionCode::CC_NE);
974 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_EQ,
975 ConditionCode::CC_LT);
976 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_EQ,
977 ConditionCode::CC_LE);
978 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_EQ,
979 ConditionCode::CC_GT);
980 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_EQ,
981 ConditionCode::CC_GE);
982 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_EQ,
983 ConditionCode::CC_B);
984 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_EQ,
985 ConditionCode::CC_BE);
986 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_EQ,
987 ConditionCode::CC_A);
988 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_EQ,
989 ConditionCode::CC_AE);
990
991 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_EQ,
992 ConditionCode::CC_EQ);
993 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_EQ,
994 ConditionCode::CC_NE);
995 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_EQ,
996 ConditionCode::CC_LT);
997 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_EQ,
998 ConditionCode::CC_LE);
999 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_EQ,
1000 ConditionCode::CC_GT);
1001 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_EQ,
1002 ConditionCode::CC_GE);
1003 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_EQ,
1004 ConditionCode::CC_B);
1005 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_EQ,
1006 ConditionCode::CC_BE);
1007 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_EQ,
1008 ConditionCode::CC_A);
1009 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_EQ,
1010 ConditionCode::CC_AE);
1011
1012 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_LT,
1013 ConditionCode::CC_EQ);
1014 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_LT,
1015 ConditionCode::CC_NE);
1016 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_LT,
1017 ConditionCode::CC_LT);
1018 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_LT,
1019 ConditionCode::CC_LE);
1020 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_LT,
1021 ConditionCode::CC_GT);
1022 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_LT,
1023 ConditionCode::CC_GE);
1024 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1025 ConditionCode::CC_B);
1026 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1027 ConditionCode::CC_BE);
1028 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1029 ConditionCode::CC_A);
1030 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1031 ConditionCode::CC_AE);
1032
1033 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1034 ConditionCode::CC_EQ);
1035 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1036 ConditionCode::CC_NE);
1037 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_LT,
1038 ConditionCode::CC_LT);
1039 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1040 ConditionCode::CC_LE);
1041 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1042 ConditionCode::CC_GT);
1043 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_LT,
1044 ConditionCode::CC_GE);
1045 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1046 ConditionCode::CC_B);
1047 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1048 ConditionCode::CC_BE);
1049 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1050 ConditionCode::CC_A);
1051 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LT,
1052 ConditionCode::CC_AE);
1053
1054 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1055 ConditionCode::CC_EQ);
1056 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1057 ConditionCode::CC_NE);
1058 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1059 ConditionCode::CC_LT);
1060 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_LE,
1061 ConditionCode::CC_LE);
1062 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_LE,
1063 ConditionCode::CC_GT);
1064 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1065 ConditionCode::CC_GE);
1066 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1067 ConditionCode::CC_B);
1068 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1069 ConditionCode::CC_BE);
1070 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1071 ConditionCode::CC_A);
1072 BuildGraphAndCheckElimination<DominantCondResult::TRUE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1073 ConditionCode::CC_AE);
1074
1075 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_LE,
1076 ConditionCode::CC_EQ);
1077 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_LE,
1078 ConditionCode::CC_NE);
1079 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_LE,
1080 ConditionCode::CC_LT);
1081 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::FALSE_SUCCESSOR>(ConditionCode::CC_LE,
1082 ConditionCode::CC_LE);
1083 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_LE,
1084 ConditionCode::CC_GT);
1085 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::TRUE_SUCCESSOR>(ConditionCode::CC_LE,
1086 ConditionCode::CC_GE);
1087 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1088 ConditionCode::CC_B);
1089 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1090 ConditionCode::CC_BE);
1091 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1092 ConditionCode::CC_A);
1093 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH>(ConditionCode::CC_LE,
1094 ConditionCode::CC_AE);
1095
1096 // dominant condition: b op1 a,
1097 // dominated condition: a op2 b (reached from false successor)
1098 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH, SwapInputs::TRUE>(
1099 ConditionCode::CC_GT, ConditionCode::CC_EQ);
1100 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::FALSE_SUCCESSOR, SwapInputs::TRUE>(
1101 ConditionCode::CC_GE, ConditionCode::CC_EQ);
1102 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::BOTH, SwapInputs::TRUE>(
1103 ConditionCode::CC_LT, ConditionCode::CC_EQ);
1104 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::FALSE_SUCCESSOR, SwapInputs::TRUE>(
1105 ConditionCode::CC_LE, ConditionCode::CC_EQ);
1106 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::FALSE_SUCCESSOR, SwapInputs::TRUE>(
1107 ConditionCode::CC_EQ, ConditionCode::CC_EQ);
1108 BuildGraphAndCheckElimination<DominantCondResult::FALSE, RemainedSuccessor::TRUE_SUCCESSOR, SwapInputs::TRUE>(
1109 ConditionCode::CC_NE, ConditionCode::CC_EQ);
1110 }
1111
TEST_F(BranchEliminationTest,CascadeElimination)1112 TEST_F(BranchEliminationTest, CascadeElimination)
1113 {
1114 /*
1115 * Case 1
1116 *
1117 * [0]
1118 * T | F
1119 * /----[2]----\
1120 * | |
1121 * v T v F
1122 * [3] /----[4]----\
1123 * | | T | F
1124 * | [5] /----[6]----\
1125 * | | | |
1126 * | | [7] [8]
1127 * v v v v
1128 * [exit]<-------------------/
1129 *
1130 * ---->
1131 *
1132 * [0]
1133 * |
1134 * /----[2]----\
1135 * | |
1136 * v v
1137 * [3] [4]
1138 * | |
1139 * | [6]
1140 * | |
1141 * | [8]
1142 * v |
1143 * [exit]<-------/
1144 */
1145
1146 auto graph = CreateEmptyGraph();
1147 GRAPH(graph)
1148 {
1149 PARAMETER(0, 0).u64();
1150 PARAMETER(1, 1).u64();
1151 PARAMETER(2, 2).u64();
1152
1153 BASIC_BLOCK(2, 3, 4)
1154 {
1155 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1156 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
1157 }
1158 BASIC_BLOCK(3, 9)
1159 {
1160 INST(5, Opcode::Add).u64().Inputs(0, 2);
1161 }
1162 BASIC_BLOCK(4, 5, 6)
1163 {
1164 INST(7, Opcode::Compare).b().CC(CC_EQ).Inputs(1, 0);
1165 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
1166 }
1167 BASIC_BLOCK(5, 9)
1168 {
1169 INST(9, Opcode::Sub).u64().Inputs(0, 2);
1170 }
1171 BASIC_BLOCK(6, 7, 8)
1172 {
1173 INST(11, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1174 INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
1175 }
1176 BASIC_BLOCK(7, 9)
1177 {
1178 INST(13, Opcode::Mul).u64().Inputs(0, 2);
1179 }
1180 BASIC_BLOCK(8, 9)
1181 {
1182 INST(15, Opcode::Div).u64().Inputs(0, 2);
1183 }
1184 BASIC_BLOCK(9, -1)
1185 {
1186 INST(17, Opcode::Phi).u64().Inputs(5, 9, 13, 15);
1187 INST(18, Opcode::Return).u64().Inputs(17);
1188 }
1189 }
1190 graph->RunPass<BranchElimination>();
1191 graph->RunPass<Cleanup>();
1192
1193 auto expected_graph = CreateEmptyGraph();
1194 GRAPH(expected_graph)
1195 {
1196 PARAMETER(0, 0).u64();
1197 PARAMETER(1, 1).u64();
1198 PARAMETER(2, 2).u64();
1199
1200 BASIC_BLOCK(2, 3, 8)
1201 {
1202 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1203 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
1204 }
1205 BASIC_BLOCK(3, 9)
1206 {
1207 INST(5, Opcode::Add).u64().Inputs(0, 2);
1208 }
1209 BASIC_BLOCK(8, 9)
1210 {
1211 INST(15, Opcode::Div).u64().Inputs(0, 2);
1212 }
1213 BASIC_BLOCK(9, -1)
1214 {
1215 INST(17, Opcode::Phi).u64().Inputs(5, 15);
1216 INST(18, Opcode::Return).u64().Inputs(17);
1217 }
1218 }
1219 ASSERT_TRUE(GraphComparator().Compare(graph, expected_graph));
1220
1221 /*
1222 * Case 2
1223 *
1224 * [0]
1225 * F | T
1226 * /----[2]----\
1227 * | |
1228 * v T v F
1229 * [3] /----[4]----\
1230 * | | T | F
1231 * | [5] /----[6]----\
1232 * | | | |
1233 * | | [7] [8]
1234 * v v v v
1235 * [exit]<-------------------/
1236 *
1237 * ---->
1238 *
1239 * [0]
1240 * T | F
1241 * /----[2]----\
1242 * | |
1243 * v v
1244 * [3] [4]
1245 * | |
1246 * | [5]
1247 * | |
1248 * | |
1249 * v |
1250 * [exit]<-------/
1251 *
1252 */
1253 auto graph_case2 = CreateEmptyGraph();
1254 GRAPH(graph_case2)
1255 {
1256 PARAMETER(0, 0).u64();
1257 PARAMETER(1, 1).u64();
1258 PARAMETER(2, 2).u64();
1259
1260 BASIC_BLOCK(2, 4, 3)
1261 {
1262 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1263 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
1264 }
1265 BASIC_BLOCK(3, 9)
1266 {
1267 INST(5, Opcode::Add).u64().Inputs(0, 2);
1268 }
1269 BASIC_BLOCK(4, 5, 6)
1270 {
1271 INST(7, Opcode::Compare).b().CC(CC_EQ).Inputs(1, 0);
1272 INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
1273 }
1274 BASIC_BLOCK(5, 9)
1275 {
1276 INST(9, Opcode::Sub).u64().Inputs(0, 2);
1277 }
1278 BASIC_BLOCK(6, 7, 8)
1279 {
1280 INST(11, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1281 INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
1282 }
1283 BASIC_BLOCK(7, 9)
1284 {
1285 INST(13, Opcode::Mul).u64().Inputs(0, 2);
1286 }
1287 BASIC_BLOCK(8, 9)
1288 {
1289 INST(15, Opcode::Div).u64().Inputs(0, 2);
1290 }
1291 BASIC_BLOCK(9, -1)
1292 {
1293 INST(17, Opcode::Phi).u64().Inputs(5, 9, 13, 15);
1294 INST(18, Opcode::Return).u64().Inputs(17);
1295 }
1296 }
1297 graph_case2->RunPass<BranchElimination>();
1298 graph_case2->RunPass<Cleanup>();
1299
1300 auto expected_graph2 = CreateEmptyGraph();
1301 GRAPH(expected_graph2)
1302 {
1303 PARAMETER(0, 0).u64();
1304 PARAMETER(1, 1).u64();
1305 PARAMETER(2, 2).u64();
1306
1307 BASIC_BLOCK(2, 5, 3)
1308 {
1309 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1310 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
1311 }
1312 BASIC_BLOCK(3, 9)
1313 {
1314 INST(5, Opcode::Add).u64().Inputs(0, 2);
1315 }
1316 BASIC_BLOCK(5, 9)
1317 {
1318 INST(9, Opcode::Sub).u64().Inputs(0, 2);
1319 }
1320 BASIC_BLOCK(9, -1)
1321 {
1322 INST(17, Opcode::Phi).u64().Inputs(5, 9);
1323 INST(18, Opcode::Return).u64().Inputs(17);
1324 }
1325 }
1326 ASSERT_TRUE(GraphComparator().Compare(graph_case2, expected_graph2));
1327 }
1328
TEST_F(BranchEliminationTest,ConditionEliminationNotApplied)1329 TEST_F(BranchEliminationTest, ConditionEliminationNotApplied)
1330 {
1331 /*
1332 * Case 1:
1333 * [0]
1334 * |
1335 * /----[2]----\
1336 * | |
1337 * v v
1338 * [3] [4]
1339 * | |
1340 * \-----------/
1341 * |
1342 * /----[6]----\
1343 * | |
1344 * [7] [8]
1345 * | |
1346 * v |
1347 * [exit]<-------/
1348 */
1349 auto graph = CreateEmptyGraph();
1350 GRAPH(graph)
1351 {
1352 PARAMETER(0, 0).u64();
1353 PARAMETER(1, 1).u64();
1354 PARAMETER(2, 2).u64();
1355
1356 BASIC_BLOCK(2, 3, 4)
1357 {
1358 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1359 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
1360 }
1361 BASIC_BLOCK(3, 6)
1362 {
1363 INST(5, Opcode::Add).u64().Inputs(1, 2);
1364 }
1365 BASIC_BLOCK(4, 6)
1366 {
1367 INST(7, Opcode::Sub).u64().Inputs(1, 2);
1368 }
1369 BASIC_BLOCK(6, 7, 8)
1370 {
1371 INST(9, Opcode::Phi).Inputs(5, 7).u64();
1372 INST(10, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1373 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
1374 }
1375 BASIC_BLOCK(7, 9)
1376 {
1377 INST(12, Opcode::Add).u64().Inputs(9, 1);
1378 }
1379 BASIC_BLOCK(8, 9)
1380 {
1381 INST(14, Opcode::Sub).u64().Inputs(9, 1);
1382 }
1383 BASIC_BLOCK(9, -1)
1384 {
1385 INST(16, Opcode::Phi).u64().Inputs(12, 14);
1386 INST(17, Opcode::Return).u64().Inputs(16);
1387 }
1388 }
1389 graph->RunPass<BranchElimination>();
1390 EXPECT_EQ(BB(6).GetSuccsBlocks().size(), 2U);
1391
1392 /*
1393 * Case 2
1394 * [0]
1395 * |
1396 * /----[2]----\
1397 * | |
1398 * | |
1399 * [3]--------->|
1400 * v
1401 * /----[4]----\
1402 * | |
1403 * [5] [6]
1404 * | |
1405 * v |
1406 * [exit]<-------/
1407 */
1408 auto graph2 = CreateEmptyGraph();
1409 GRAPH(graph2)
1410 {
1411 PARAMETER(0, 0).u64();
1412 PARAMETER(1, 1).u64();
1413 PARAMETER(2, 2).u64();
1414
1415 BASIC_BLOCK(2, 3, 4)
1416 {
1417 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1418 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
1419 }
1420 BASIC_BLOCK(3, 4)
1421 {
1422 INST(5, Opcode::Add).u64().Inputs(1, 2);
1423 }
1424 BASIC_BLOCK(4, 5, 6)
1425 {
1426 INST(7, Opcode::Phi).Inputs(1, 5).u64();
1427 INST(8, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1428 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
1429 }
1430 BASIC_BLOCK(5, 7)
1431 {
1432 INST(10, Opcode::Add).u64().Inputs(7, 1);
1433 }
1434 BASIC_BLOCK(6, 7)
1435 {
1436 INST(12, Opcode::Sub).u64().Inputs(7, 1);
1437 }
1438 BASIC_BLOCK(7, -1)
1439 {
1440 INST(14, Opcode::Phi).u64().Inputs(10, 12);
1441 INST(15, Opcode::Return).u64().Inputs(14);
1442 }
1443 }
1444 graph2->RunPass<BranchElimination>();
1445 EXPECT_EQ(BB(4).GetSuccsBlocks().size(), 2U);
1446 }
1447
1448 /*
1449 * [0]
1450 * |
1451 * /----[2]----\
1452 * | |
1453 * | v
1454 * | [3]
1455 * | |
1456 * | v
1457 * \--------->[4]
1458 * |
1459 * v
1460 * /----[5]----\
1461 * | |
1462 * [6] [7]
1463 * | |
1464 * v |
1465 * [exit]<-------/
1466 *
1467 */
TEST_F(BranchEliminationTest,DomBothSuccessorsReachTargetBlock)1468 TEST_F(BranchEliminationTest, DomBothSuccessorsReachTargetBlock)
1469 {
1470 auto graph = CreateEmptyGraph();
1471 GRAPH(graph)
1472 {
1473 PARAMETER(0, 0).u64();
1474 PARAMETER(1, 1).u64();
1475 PARAMETER(2, 2).u64();
1476
1477 BASIC_BLOCK(2, 3, 4)
1478 {
1479 INST(3, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1480 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
1481 }
1482 BASIC_BLOCK(3, 4)
1483 {
1484 INST(5, Opcode::Add).u64().Inputs(0, 0);
1485 }
1486 BASIC_BLOCK(4, 6, 7)
1487 {
1488 INST(7, Opcode::Phi).u64().Inputs({{2, 0}, {3, 5}});
1489 INST(8, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1490 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
1491 }
1492 BASIC_BLOCK(6, 8)
1493 {
1494 INST(10, Opcode::Add).u64().Inputs(7, 1);
1495 }
1496 BASIC_BLOCK(7, 8)
1497 {
1498 INST(12, Opcode::Sub).u64().Inputs(7, 1);
1499 }
1500 BASIC_BLOCK(8, -1)
1501 {
1502 INST(14, Opcode::Phi).u64().Inputs(10, 12);
1503 INST(15, Opcode::Return).u64().Inputs(14);
1504 }
1505 }
1506 graph->RunPass<BranchElimination>();
1507 // Elimination NOT applied
1508 EXPECT_EQ(BB(4).GetGraph(), graph);
1509 EXPECT_EQ(BB(4).GetSuccsBlocks().size(), 2U);
1510 }
1511
TEST_F(BranchEliminationTest,CreateInfiniteLoop)1512 TEST_F(BranchEliminationTest, CreateInfiniteLoop)
1513 {
1514 auto graph = CreateEmptyGraph();
1515 GRAPH(graph)
1516 {
1517 CONSTANT(1, 1);
1518
1519 BASIC_BLOCK(2, 2, 3)
1520 {
1521 INST(2, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(1);
1522 }
1523 BASIC_BLOCK(3, -1)
1524 {
1525 INST(4, Opcode::ReturnVoid);
1526 }
1527 }
1528 ASSERT_TRUE(graph->HasEndBlock());
1529 graph->RunPass<BranchElimination>();
1530 ASSERT_FALSE(graph->HasEndBlock());
1531
1532 auto expected_graph = CreateEmptyGraph();
1533 GRAPH(expected_graph)
1534 {
1535 CONSTANT(1, 1);
1536 BASIC_BLOCK(2, 3)
1537 { // pre-header
1538 }
1539 BASIC_BLOCK(3, 3)
1540 { // infinite loop
1541 }
1542 }
1543 ASSERT_TRUE(GraphComparator().Compare(graph, expected_graph));
1544 }
1545
1546 /**
1547 * compare1
1548 * ...
1549 * if_imm(compare1)
1550 */
TEST_F(BranchEliminationTest,CompareAndIfNotSameBlock)1551 TEST_F(BranchEliminationTest, CompareAndIfNotSameBlock)
1552 {
1553 auto graph = CreateEmptyGraph();
1554 GRAPH(graph)
1555 {
1556 PARAMETER(0, 0).s64();
1557 PARAMETER(1, 1).s64();
1558 PARAMETER(2, 2).s64();
1559 CONSTANT(3, 0);
1560 BASIC_BLOCK(2, 3)
1561 {
1562 INST(4, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1563 }
1564 BASIC_BLOCK(3, 4, 5)
1565 {
1566 INST(5, Opcode::Phi).s64().Inputs(2, 8);
1567 INST(6, Opcode::Compare).b().CC(CC_LT).Inputs(5, 0);
1568 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
1569 }
1570 BASIC_BLOCK(4, 3)
1571 {
1572 INST(8, Opcode::Add).s64().Inputs(5, 3);
1573 }
1574 BASIC_BLOCK(5, 6, 7)
1575 {
1576 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
1577 } // if INS(4) != 0 goto BB(6) else goto BB(7)
1578 BASIC_BLOCK(6, 12)
1579 {
1580 INST(10, Opcode::Mul).u64().Inputs(0, 1);
1581 }
1582 BASIC_BLOCK(7, 8, 9)
1583 {
1584 INST(11, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1); // equal to INS(4) -> INS(11) == 0
1585 INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_EQ).Imm(0).Inputs(11);
1586 } // INS(11) == 0 is true -> goto BB(8), remove BB(9)
1587 BASIC_BLOCK(8, 10, 11)
1588 {
1589 INST(14, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
1590 } // INS(11) == 1 is false -> goto BB(11), remove BB(10)
1591 BASIC_BLOCK(9, 12)
1592 {
1593 INST(15, Opcode::Sub).u64().Inputs(0, 1);
1594 }
1595 BASIC_BLOCK(10, 12)
1596 {
1597 INST(16, Opcode::Mul).u64().Inputs(1, 1);
1598 }
1599 BASIC_BLOCK(11, 12)
1600 {
1601 INST(17, Opcode::Add).u64().Inputs(2, 2);
1602 }
1603 BASIC_BLOCK(12, -1)
1604 {
1605 INST(18, Opcode::Phi).u64().Inputs(10, 15, 16, 17);
1606 INST(19, Opcode::Return).u64().Inputs(18);
1607 }
1608 }
1609 graph->RunPass<BranchElimination>();
1610 graph->RunPass<Cleanup>();
1611
1612 auto expected_graph = CreateEmptyGraph();
1613 GRAPH(expected_graph)
1614 {
1615 PARAMETER(0, 0).s64();
1616 PARAMETER(1, 1).s64();
1617 PARAMETER(2, 2).s64();
1618 CONSTANT(3, 0);
1619
1620 BASIC_BLOCK(2, 3)
1621 {
1622 INST(4, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
1623 }
1624 BASIC_BLOCK(3, 4, 5)
1625 {
1626 INST(5, Opcode::Phi).s64().Inputs(2, 8);
1627 INST(6, Opcode::Compare).b().CC(CC_LT).Inputs(5, 0);
1628 INST(7, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(6);
1629 }
1630 BASIC_BLOCK(4, 3)
1631 {
1632 INST(8, Opcode::Add).s64().Inputs(5, 3);
1633 }
1634 BASIC_BLOCK(5, 6, 11)
1635 {
1636 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(4);
1637 }
1638 BASIC_BLOCK(6, 12)
1639 {
1640 INST(10, Opcode::Mul).u64().Inputs(0, 1);
1641 }
1642 BASIC_BLOCK(11, 12)
1643 {
1644 INST(17, Opcode::Add).u64().Inputs(2, 2);
1645 }
1646 BASIC_BLOCK(12, -1)
1647 {
1648 INST(18, Opcode::Phi).u64().Inputs(10, 17);
1649 INST(19, Opcode::Return).u64().Inputs(18);
1650 }
1651 }
1652 ASSERT_TRUE(GraphComparator().Compare(graph, expected_graph));
1653 }
1654
TEST_F(BranchEliminationTest,DisconnectPhiWithInputItself)1655 TEST_F(BranchEliminationTest, DisconnectPhiWithInputItself)
1656 {
1657 auto graph = CreateEmptyGraph();
1658 GRAPH(graph)
1659 {
1660 CONSTANT(0, 0);
1661 CONSTANT(1, 1);
1662 CONSTANT(2, 10);
1663 PARAMETER(3, 0).s64();
1664 BASIC_BLOCK(2, 10, 4)
1665 {
1666 INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_EQ).Imm(0).Inputs(0);
1667 }
1668 BASIC_BLOCK(4, 7)
1669 {
1670 INST(5, Opcode::Mul).s64().Inputs(2, 2);
1671 }
1672 BASIC_BLOCK(7, 8, 10)
1673 {
1674 INST(6, Opcode::Phi).s64().Inputs(0, 12, 13);
1675 INST(7, Opcode::Phi).s64().Inputs(5, 6, 7);
1676 INST(8, Opcode::Compare).b().CC(CC_LT).Inputs(6, 7);
1677 INST(9, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(8);
1678 }
1679 BASIC_BLOCK(8, 5, 6)
1680 {
1681 INST(10, Opcode::Compare).b().CC(CC_LT).Inputs(6, 3);
1682 INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
1683 }
1684 BASIC_BLOCK(5, 7)
1685 {
1686 INST(12, Opcode::Add).s64().Inputs(6, 1);
1687 }
1688 BASIC_BLOCK(6, 7)
1689 {
1690 INST(13, Opcode::Add).s64().Inputs(6, 2);
1691 }
1692 BASIC_BLOCK(10, -1)
1693 {
1694 INST(20, Opcode::Phi).s64().Inputs(0, 6);
1695 INST(21, Opcode::Return).s64().Inputs(20);
1696 }
1697 }
1698 graph->RunPass<BranchElimination>();
1699 graph->RunPass<Cleanup>();
1700
1701 auto expected_graph = CreateEmptyGraph();
1702 GRAPH(expected_graph)
1703 {
1704 CONSTANT(0, 0);
1705 BASIC_BLOCK(2, -1)
1706 {
1707 INST(21, Opcode::Return).s64().Inputs(0);
1708 }
1709 }
1710 ASSERT_TRUE(GraphComparator().Compare(graph, expected_graph));
1711 }
1712 } // namespace panda::compiler
1713