• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2024 Shenzhen Kaihong Digital Industry Development 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  * Copyright (c) 2024 Huawei Device Co., Ltd.
16  * Licensed under the Apache License, Version 2.0 (the "License");
17  * you may not use this file except in compliance with the License.
18  * You may obtain a copy of the License at
19 
20  * http://www.apache.org/licenses/LICENSE-2.0
21  *
22  * Unless required by applicable law or agreed to in writing, software
23  * distributed under the License is distributed on an "AS IS" BASIS,
24  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
25  * See the License for the specific language governing permissions and
26  * limitations under the License.
27  */
28 
29 #include <algorithm>
30 #include <cstdint>
31 #include <gtest/gtest.h>
32 #include <string>
33 #include <unordered_set>
34 #include <vector>
35 
36 #include "graph_comparator.h"
37 #include "graph_test.h"
38 #include "optimizer/analysis/dominators_tree.h"
39 #include "optimizer/analysis/loop_analyzer.h"
40 #include "optimizer/ir/basicblock.h"
41 #include "optimizer/ir/graph.h"
42 #include "optimizer/ir/graph_cloner.h"
43 #include "optimizer/ir/inst.h"
44 
45 using namespace testing::ext;
46 
47 namespace panda::compiler {
48 class GraphClonerTest : public testing::Test {
49 public:
SetUpTestCase(void)50     static void SetUpTestCase(void) {};
TearDownTestCase(void)51     static void TearDownTestCase(void) {};
SetUp()52     void SetUp() {};
TearDown()53     void TearDown() {};
54 
55     GraphTest graph_test_;
56 
GetLoopOuterBlock(BasicBlock * exit_block)57     static BasicBlock *GetLoopOuterBlock(BasicBlock *exit_block)
58     {
59         EXPECT_TRUE(exit_block->GetSuccsBlocks().size() == 2U);
60         auto loop = exit_block->GetLoop();
61         auto outer = exit_block->GetTrueSuccessor();
62         if (outer->GetLoop() == loop) {
63             outer = exit_block->GetFalseSuccessor();
64         }
65         EXPECT_TRUE(outer->GetLoop() != loop);
66         return outer;
67     }
68 
CompareInstsOpcode(BasicBlock * bb1,BasicBlock * bb2)69     static bool CompareInstsOpcode(BasicBlock *bb1, BasicBlock *bb2)
70     {
71         EXPECT_TRUE(bb1 != nullptr);
72         EXPECT_TRUE(bb2 != nullptr);
73         auto insts1 = bb1->Insts();
74         auto insts2 = bb2->Insts();
75         return std::equal(insts1.begin(), insts1.end(), insts2.begin(), insts2.end(),
76                           [](Inst *inst1, Inst *inst2) { return inst1->GetOpcode() == inst2->GetOpcode(); });
77     }
78 
CompareInstsOpcode(const std::vector<Inst * > & insts1,const InstIter & insts2)79     static bool CompareInstsOpcode(const std::vector<Inst*> &insts1, const InstIter &insts2)
80     {
81         return std::equal(insts1.begin(), insts1.end(), insts2.begin(), insts2.end(),
82                           [](Inst *inst1, Inst *inst2) { return inst1->GetOpcode() == inst2->GetOpcode(); });
83     }
84 
85     template<typename Callback>
ForEachNonRootLoop(Graph * graph,Callback cb)86     static void ForEachNonRootLoop(Graph *graph, Callback cb)
87     {
88         EXPECT_TRUE(graph != nullptr);
89         if (!graph->HasLoop()) {
90             return;
91         }
92 
93         auto root_loop = graph->GetRootLoop();
94         for (auto loop : root_loop->GetInnerLoops()) {
95             VisitLoopRec(loop, cb);
96         }
97     }
98 
99     template<typename Callback>
VisitLoopRec(Loop * loop,Callback cb)100     static void VisitLoopRec(Loop *loop, Callback cb)
101     {
102         EXPECT_TRUE(loop != nullptr);
103         cb(loop);
104         for (auto inner_loop : loop->GetInnerLoops()) {
105             VisitLoopRec(inner_loop, cb);
106         }
107     }
108 
CloneGraph(Graph * graph)109     static Graph* CloneGraph(Graph *graph)
110     {
111         GraphCloner graph_cloner(graph, graph->GetAllocator(), graph->GetLocalAllocator());
112         auto graph_clone = graph_cloner.CloneGraph();
113         EXPECT_TRUE(graph_clone != nullptr);
114         EXPECT_TRUE(graph_clone->RunPass<DominatorsTree>());
115         EXPECT_TRUE(graph_clone->RunPass<LoopAnalyzer>());
116         return graph_clone;
117     }
118 
119     template <UnrollType type>
CloneFirstLoopAndUnroll(Graph * graph,size_t factor)120     static Loop* CloneFirstLoopAndUnroll(Graph *graph, size_t factor)
121     {
122         auto graph_clone = CloneGraph(graph);
123         auto loop_clone = graph_clone->GetRootLoop()->GetInnerLoops()[0];
124         GraphCloner loop_cloner(graph_clone, graph_clone->GetAllocator(), graph_clone->GetLocalAllocator());
125         loop_cloner.UnrollLoopBody<type>(loop_clone, factor);
126         return loop_clone;
127     }
128 };
129 
130 /**
131  * @tc.name: graph_cloner_test_001
132  * @tc.desc: Verify the CloneGraph function.
133  * @tc.type: FUNC
134  * @tc.require:
135  */
136 HWTEST_F(GraphClonerTest, graph_cloner_test_001, TestSize.Level1)
137 {
138     std::string pfile = GRAPH_TEST_ABC_DIR "graphTest.abc";
139     bool status = false;
__anon35b0f5870302(Graph* graph, std::string &method_name) 140     graph_test_.TestBuildGraphFromFile(pfile, [&status](Graph* graph, std::string &method_name) {
141         GraphCloner cloner(graph, graph->GetAllocator(), graph->GetLocalAllocator());
142         auto graph_clone = cloner.CloneGraph();
143         EXPECT_TRUE(graph_clone != nullptr);
144         EXPECT_TRUE(GraphComparator().Compare(graph, graph_clone));
145         status = true;
146     });
147     EXPECT_TRUE(status);
148 }
149 
150 /**
151  * @tc.name: graph_cloner_test_002
152  * @tc.desc: Verify the CloneLoopHeader function.
153  * @tc.type: FUNC
154  * @tc.require:
155  */
156 HWTEST_F(GraphClonerTest, graph_cloner_test_002, TestSize.Level1)
157 {
158     std::string pfile = GRAPH_TEST_ABC_DIR "graphTest.abc";
159     std::unordered_set<std::string> test_method_names {
160         "loop1",
161         "loop2",
162         "loop3",
163         "loop4",
164     };
165     bool status = false;
__anon35b0f5870402(Graph* graph, std::string &method_name) 166     graph_test_.TestBuildGraphFromFile(pfile, [&test_method_names, &status](Graph* graph, std::string &method_name) {
167         if (test_method_names.count(method_name) == 0) {
168             return;
169         }
170 
171         EXPECT_TRUE(graph->RunPass<LoopAnalyzer>());
172 
173         auto graph_clone = CloneGraph(graph);
174         EXPECT_TRUE(GraphComparator().Compare(graph, graph_clone));
175         ForEachNonRootLoop(graph_clone, [&graph_clone](Loop *loop) {
176             auto blocks = graph_clone->GetVectorBlocks();
177             auto header = blocks[loop->GetHeader()->GetId()];
178             auto preheader = blocks[loop->GetPreHeader()->GetId()];
179             auto outer_bb = GetLoopOuterBlock(header);
180 
181             GraphCloner header_cloner(graph_clone, graph_clone->GetAllocator(), graph_clone->GetLocalAllocator());
182             auto header_clone = header_cloner.CloneLoopHeader(header, GetLoopOuterBlock(header), preheader);
183             auto resolver_bb = GetLoopOuterBlock(header);
184 
185             EXPECT_TRUE(preheader->HasSucc(header_clone));
186             EXPECT_TRUE(header_clone->HasSucc(header));
187             EXPECT_TRUE(CompareInstsOpcode(header_clone, header));
188             EXPECT_TRUE(resolver_bb->HasSucc(outer_bb));
189         });
190 
191         status = true;
192     });
193     EXPECT_TRUE(status);
194 }
195 
196 /**
197  * @tc.name: graph_cloner_test_003
198  * @tc.desc: Verify the IsLoopClonable function.
199  * @tc.type: FUNC
200  * @tc.require:
201  */
202 HWTEST_F(GraphClonerTest, graph_cloner_test_003, TestSize.Level1)
203 {
204     std::string pfile = GRAPH_TEST_ABC_DIR "graphTest.abc";
205     std::unordered_set<std::string> test_method_names {
206         "loop1",
207         "loop2",
208         "loop3",
209         "loop4",
210     };
211     bool status = false;
__anon35b0f5870602(Graph* graph, std::string &method_name) 212     graph_test_.TestBuildGraphFromFile(pfile, [&test_method_names, &status](Graph* graph, std::string &method_name) {
213         if (test_method_names.count(method_name) == 0) {
214             return;
215         }
216 
217         EXPECT_TRUE(graph->RunPass<LoopAnalyzer>());
218 
219         GraphCloner cloner(graph, graph->GetAllocator(), graph->GetLocalAllocator());
220 
221         ForEachNonRootLoop(graph, [&cloner](Loop *loop) {
222             if (!loop->GetInnerLoops().empty() || !loop->GetOuterLoop()->IsRoot() ||
223                 !IsLoopSingleBackEdgeExitPoint(loop)) {
224                 EXPECT_FALSE(cloner.IsLoopClonable(loop, UINT32_MAX));
225             } else {
226                 EXPECT_TRUE(cloner.CloneLoopHeader(loop->GetHeader(), GetLoopOuterBlock(loop->GetHeader()),
227                                                    loop->GetPreHeader()) != nullptr);
228 
229                 EXPECT_TRUE(cloner.IsLoopClonable(loop, UINT32_MAX));
230                 EXPECT_FALSE(cloner.IsLoopClonable(loop, 1));
231             }
232         });
233 
234         status = true;
235     });
236     EXPECT_TRUE(status);
237 }
238 
239 /**
240  * @tc.name: graph_cloner_test_004
241  * @tc.desc: Verify the CloneLoop function.
242  * @tc.type: FUNC
243  * @tc.require:
244  */
245 HWTEST_F(GraphClonerTest, graph_cloner_test_004, TestSize.Level1)
246 {
247     std::string pfile = GRAPH_TEST_ABC_DIR "graphTest.abc";
248     const char *test_method_name = "loop4";
249     bool status = false;
__anon35b0f5870802(Graph* graph, std::string &method_name) 250     graph_test_.TestBuildGraphFromFile(pfile, [&test_method_name, &status](Graph* graph, std::string &method_name) {
251         if (test_method_name != method_name) {
252             return;
253         }
254 
255         EXPECT_TRUE(graph->RunPass<LoopAnalyzer>());
256         auto loop = graph->GetRootLoop()->GetInnerLoops()[0];
257         EXPECT_TRUE(IsLoopSingleBackEdgeExitPoint(loop));
258 
259         GraphCloner header_cloner(graph, graph->GetAllocator(), graph->GetLocalAllocator());
260         EXPECT_TRUE(header_cloner.CloneLoopHeader(loop->GetHeader(), GetLoopOuterBlock(loop->GetHeader()),
261                                            loop->GetPreHeader()) != nullptr);
262         EXPECT_TRUE(loop->GetPreHeader()->GetLastInst()->GetOpcode() == Opcode::IfImm);
263 
264         GraphCloner loop_cloner(graph, graph->GetAllocator(), graph->GetLocalAllocator());
265         auto loop_clone = loop_cloner.CloneLoop(loop);
266         EXPECT_TRUE(loop_clone != nullptr);
267         EXPECT_TRUE(GetLoopOuterBlock(loop->GetHeader())->HasSucc(loop_clone->GetPreHeader()));
268         EXPECT_TRUE(CompareInstsOpcode(loop->GetPreHeader(), loop_clone->GetPreHeader()));
269         EXPECT_TRUE(CompareInstsOpcode(loop->GetHeader(), loop_clone->GetHeader()));
270 
271         status = true;
272     });
273     EXPECT_TRUE(status);
274 }
275 
276 /**
277  * @tc.name: graph_cloner_test_005
278  * @tc.desc: Verify the UnrollLoopBody function with side exits.
279  * @tc.type: FUNC
280  * @tc.require:
281  */
282 HWTEST_F(GraphClonerTest, graph_cloner_test_005, TestSize.Level1)
283 {
284     std::string pfile = GRAPH_TEST_ABC_DIR "graphTest.abc";
285     const char *test_method_name = "loop4";
286     bool status = false;
__anon35b0f5870902(Graph* graph, std::string &method_name) 287     graph_test_.TestBuildGraphFromFile(pfile, [&test_method_name, &status](Graph* graph, std::string &method_name) {
288         if (test_method_name != method_name) {
289             return;
290         }
291 
292         EXPECT_TRUE(graph->RunPass<LoopAnalyzer>());
293         auto loop = graph->GetRootLoop()->GetInnerLoops()[0];
294         EXPECT_TRUE(IsLoopSingleBackEdgeExitPoint(loop));
295         auto loop_body = loop->GetHeader();
296         auto outer_bb_id = GetLoopOuterBlock(loop->GetHeader())->GetId();
297 
298         auto loop_clone = CloneFirstLoopAndUnroll<UnrollType::UNROLL_WITH_SIDE_EXITS>(graph, 3);
299         auto graph_clone = loop_clone->GetPreHeader()->GetGraph();
300 
301         auto resolver_bb = graph_clone->GetVectorBlocks()[outer_bb_id]->GetPredecessor(0);
302         EXPECT_EQ(loop->GetPreHeader()->GetId(), loop_clone->GetPreHeader()->GetId());
303         for (auto bb : loop_clone->GetBlocks()) {
304             if (!bb->IsLoopHeader() && !bb->IsLoopPreHeader()) {
305                 EXPECT_TRUE(bb->HasSucc(resolver_bb));
306                 EXPECT_TRUE(CompareInstsOpcode(bb, loop_body));
307             }
308         }
309 
310         status = true;
311     });
312     EXPECT_TRUE(status);
313 }
314 
315 /**
316  * @tc.name: graph_cloner_test_006
317  * @tc.desc: Verify the UnrollLoopBody function without side exits.
318  * @tc.type: FUNC
319  * @tc.require:
320  */
321 HWTEST_F(GraphClonerTest, graph_cloner_test_006, TestSize.Level1)
322 {
323     std::string pfile = GRAPH_TEST_ABC_DIR "graphTest.abc";
324     const char *test_method_name = "loop4";
325     bool status = false;
__anon35b0f5870a02(Graph* graph, std::string &method_name) 326     graph_test_.TestBuildGraphFromFile(pfile, [&test_method_name, &status](Graph* graph, std::string &method_name) {
327         if (test_method_name != method_name) {
328             return;
329         }
330 
331         EXPECT_TRUE(graph->RunPass<LoopAnalyzer>());
332         auto loop = graph->GetRootLoop()->GetInnerLoops()[0];
333         EXPECT_TRUE(IsLoopSingleBackEdgeExitPoint(loop));
334 
335         // Make preheader have IfImm inst, which is required for UnrollLoopBody without side exits
336         GraphCloner header_cloner(graph, graph->GetAllocator(), graph->GetLocalAllocator());
337         EXPECT_TRUE(header_cloner.CloneLoopHeader(loop->GetHeader(), GetLoopOuterBlock(loop->GetHeader()),
338                                            loop->GetPreHeader()) != nullptr);
339         EXPECT_TRUE(loop->GetPreHeader()->GetLastInst()->GetOpcode() == Opcode::IfImm);
340 
341         auto outer_bb_id = GetLoopOuterBlock(loop->GetHeader())->GetId();
342         auto loop_body = loop->GetHeader();
343         std::vector<Inst*> loop_body_insts;
344         std::vector<Inst*> loop_cmp_if_insts;
345         for (auto inst : loop_body->Insts()) {
346             if (inst->GetOpcode() == Opcode::IfImm || inst->GetOpcode() == Opcode::Compare) {
347                 loop_cmp_if_insts.emplace_back(inst);
348             } else {
349                 loop_body_insts.emplace_back(inst);
350             }
351         }
352 
353         auto loop_clone = CloneFirstLoopAndUnroll<UnrollType::UNROLL_WITHOUT_SIDE_EXITS>(graph, 3);
354         auto graph_clone = loop_clone->GetPreHeader()->GetGraph();
355 
356         EXPECT_EQ(loop->GetPreHeader()->GetId(), loop_clone->GetPreHeader()->GetId());
357         for (auto bb : loop_clone->GetBlocks()) {
358             if (bb->IsLoopHeader() || bb->IsLoopPreHeader()) {
359                 continue;
360             }
361             auto insts = bb->Insts();
362             if (bb->GetSuccsBlocks().size() == 1) {
363                 // Insts are expected to be loop body insts
364                 EXPECT_TRUE(CompareInstsOpcode(loop_body_insts, insts));
365             } else {
366                 // Insts are expected to be the Compare and IfImm insts
367                 EXPECT_TRUE(bb->HasSucc(graph_clone->GetVectorBlocks()[outer_bb_id]));
368                 EXPECT_TRUE(CompareInstsOpcode(loop_cmp_if_insts, insts));
369             }
370         }
371 
372         status = true;
373     });
374     EXPECT_TRUE(status);
375 }
376 
377 /**
378  * @tc.name: graph_cloner_test_007
379  * @tc.desc: Verify the UnrollLoopBody function with post increment.
380  * @tc.type: FUNC
381  * @tc.require:
382  */
383 HWTEST_F(GraphClonerTest, graph_cloner_test_007, TestSize.Level1)
384 {
385     std::string pfile = GRAPH_TEST_ABC_DIR "graphTest.abc";
386     const char *test_method_name = "loop4";
387     bool status = false;
__anon35b0f5870b02(Graph* graph, std::string &method_name) 388     graph_test_.TestBuildGraphFromFile(pfile, [&test_method_name, &status](Graph* graph, std::string &method_name) {
389         if (test_method_name != method_name) {
390             return;
391         }
392 
393         EXPECT_TRUE(graph->RunPass<LoopAnalyzer>());
394         auto loop = graph->GetRootLoop()->GetInnerLoops()[0];
395         EXPECT_TRUE(IsLoopSingleBackEdgeExitPoint(loop));
396         auto loop_body = loop->GetHeader();
397 
398         auto loop_clone = CloneFirstLoopAndUnroll<UnrollType::UNROLL_POST_INCREMENT>(graph, 3);
399 
400         for (auto bb : loop_clone->GetBlocks()) {
401             if (bb->IsLoopHeader() || bb->IsLoopPreHeader()) {
402                 continue;
403             }
404             if (bb->GetSuccessor(0)->GetLoop() == bb->GetLoop()) {
405                 EXPECT_TRUE(CompareInstsOpcode(bb, loop_body));
406             } else {
407                 EXPECT_TRUE(bb->GetLastInst()->GetOpcode() == Opcode::Compare);
408             }
409         }
410 
411         status = true;
412     });
413     EXPECT_TRUE(status);
414 }
415 }  // namespace panda::compiler
416