1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include <vector>
17 #include "unit_test.h"
18 #include "optimizer/analysis/rpo.h"
19
20 namespace panda::compiler {
21 class RpoTest : public GraphTest {
22 public:
Check_Subsequence(const std::vector<BasicBlock * > && subsequence)23 void Check_Subsequence(const std::vector<BasicBlock *> &&subsequence)
24 {
25 auto subseq_iter = subsequence.begin();
26 for (auto block : GetGraph()->GetBlocksRPO()) {
27 if (block == *subseq_iter) {
28 if (++subseq_iter == subsequence.end()) {
29 break;
30 }
31 }
32 }
33 EXPECT_TRUE(subseq_iter == subsequence.end());
34 }
35 };
36
TEST_F(RpoTest,OneBlock)37 TEST_F(RpoTest, OneBlock)
38 {
39 auto block = GetGraph()->CreateStartBlock();
40 Check_Subsequence({block});
41 }
42
43 /*
44 * [entry]
45 * |
46 * v
47 * [A]
48 * | \
49 * v v
50 * [B] <- [C]
51 * | |
52 * v v
53 * [D] <- [E]
54 * |
55 * v
56 * [exit]
57 *
58 * Add [M], [N], [K]:
59 * [entry]
60 * |
61 * v
62 * [A]
63 * / | \
64 * v v v
65 * [T] -> [B] <- [C]
66 * | |
67 * v v
68 * [D] <- [E] -> [N]
69 * | |
70 * v |
71 * [M] |
72 * | |
73 * v |
74 * [K] |
75 * | |
76 * v |
77 * [exit] <---------/
78 */
TEST_F(RpoTest,GraphNoCycles)79 TEST_F(RpoTest, GraphNoCycles)
80 {
81 GRAPH(GetGraph())
82 {
83 CONSTANT(0, 0);
84 CONSTANT(1, 1);
85 BASIC_BLOCK(2, 3, 4)
86 {
87 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
88 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
89 }
90 BASIC_BLOCK(4, 3, 6)
91 {
92 INST(4, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
93 INST(5, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
94 }
95 BASIC_BLOCK(3, 5) {}
96 BASIC_BLOCK(6, 5) {}
97 BASIC_BLOCK(5, -1)
98 {
99 INST(9, Opcode::ReturnVoid);
100 }
101 }
102 auto A = &BB(2);
103 auto B = &BB(3);
104 auto C = &BB(4);
105 auto D = &BB(5);
106 auto E = &BB(6);
107 auto exit = GetGraph()->GetEndBlock();
108
109 Check_Subsequence({A, B, D});
110 Check_Subsequence({A, C, E, D});
111 Check_Subsequence({A, C, B, D});
112
113 auto M = GetGraph()->CreateEmptyBlock();
114 auto N = GetGraph()->CreateEmptyBlock();
115 auto ret1 = GetGraph()->CreateInstReturnVoid();
116 N->AppendInst(ret1);
117 auto K = GetGraph()->CreateEmptyBlock();
118 auto ret2 = GetGraph()->CreateInstReturnVoid();
119 K->AppendInst(ret2);
120 D->AddSucc(M);
121 D->RemoveSucc(exit);
122 D->RemoveInst(&INS(9));
123 exit->RemovePred(D);
124 auto cmp = GetGraph()->CreateInstCompare();
125 cmp->SetType(DataType::BOOL);
126 cmp->SetInput(0, &INS(0));
127 cmp->SetInput(1, &INS(1));
128 cmp->SetOperandsType(DataType::Type::INT64);
129 E->AppendInst(cmp);
130 auto if_inst = GetGraph()->CreateInstIfImm();
131 if_inst->SetOperandsType(DataType::BOOL);
132 if_inst->SetCc(CC_NE);
133 if_inst->SetImm(0);
134 if_inst->SetInput(0, cmp);
135 E->AppendInst(if_inst);
136 E->AddSucc(N);
137 M->AddSucc(K);
138 K->AddSucc(exit);
139 N->AddSucc(exit);
140 // Check handle tree update
141 EXPECT_FALSE(GetGraph()->GetAnalysis<Rpo>().IsValid());
142 GetGraph()->GetAnalysis<Rpo>().SetValid(true);
143 ArenaVector<BasicBlock *> added_blocks({M, K}, GetGraph()->GetAllocator()->Adapter());
144 GetGraph()->GetAnalysis<Rpo>().AddVectorAfter(D, added_blocks);
145 GetGraph()->GetAnalysis<Rpo>().AddBasicBlockAfter(E, N);
146
147 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
148 GetGraph()->RunPass<LoopAnalyzer>();
149 GraphChecker(GetGraph()).Check();
150 Check_Subsequence({A, B, D, M, K});
151 Check_Subsequence({A, C, B, D, M, K});
152 Check_Subsequence({A, C, E, D, M, K});
153 Check_Subsequence({A, C, E, N});
154
155 // Check tree rebuilding
156 EXPECT_TRUE(GetGraph()->GetAnalysis<Rpo>().IsValid());
157 GetGraph()->GetAnalysis<Rpo>().SetValid(false);
158 Check_Subsequence({A, B, D, M, K});
159 Check_Subsequence({A, C, B, D, M, K});
160 Check_Subsequence({A, C, E, D, M, K});
161 Check_Subsequence({A, C, E, N});
162 }
163
164 /*
165 * [entry]
166 * |
167 * v
168 * [A]
169 * | \
170 * v v
171 * [B] [C] <- [M]
172 * | | ^
173 * V v /
174 * [G]<--> [D] <- [E] --/
175 * |
176 * v
177 * [exit]
178 *
179 *
180 * Add [N], [K]
181 * [entry]
182 * |
183 * v
184 * [A]
185 * | \
186 * v v
187 * [B] [C] <- [M]
188 * | | ^
189 * V v /
190 * [N] <- [G]<--> [D] <- [E] --/
191 * | ^ |
192 * | / v
193 * | / [L]
194 * | / |
195 * v / v
196 * [K]/ [exit]
197 */
TEST_F(RpoTest,GraphWithCycles)198 TEST_F(RpoTest, GraphWithCycles)
199 {
200 GRAPH(GetGraph())
201 {
202 CONSTANT(0, 0);
203 CONSTANT(1, 1);
204 BASIC_BLOCK(2, 3, 4)
205 {
206 INST(2, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
207 INST(3, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(2);
208 }
209 BASIC_BLOCK(4, 6) {}
210 BASIC_BLOCK(6, 5, 7)
211 {
212 INST(5, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
213 INST(6, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(5);
214 }
215 BASIC_BLOCK(7, 4) {}
216 BASIC_BLOCK(3, 5) {}
217 BASIC_BLOCK(5, 9, 8)
218 {
219 INST(9, Opcode::Compare).b().SrcType(DataType::Type::INT64).Inputs(0, 1);
220 INST(10, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(9);
221 }
222 BASIC_BLOCK(9, -1)
223 {
224 INST(11, Opcode::ReturnVoid);
225 }
226 BASIC_BLOCK(8, 5) {}
227 }
228 auto A = &BB(2);
229 auto B = &BB(3);
230 auto C = &BB(4);
231 auto D = &BB(5);
232 auto E = &BB(6);
233 auto G = &BB(7);
234 auto M = &BB(8);
235 auto L = &BB(9);
236 auto exit = GetGraph()->GetEndBlock();
237
238 // FIXME {A, B, T, D, exit} doesn't work
239 Check_Subsequence({A, B, D, L, exit});
240 Check_Subsequence({A, C, E, D, L, exit});
241 Check_Subsequence({A, C, E, M, L});
242
243 auto N = GetGraph()->CreateEmptyBlock();
244 auto cmp = GetGraph()->CreateInstCompare();
245 cmp->SetType(DataType::BOOL);
246 cmp->SetInput(0, &INS(0));
247 cmp->SetInput(1, &INS(1));
248 cmp->SetOperandsType(DataType::Type::INT64);
249 G->AppendInst(cmp);
250 auto if_inst = GetGraph()->CreateInstIfImm();
251 if_inst->SetOperandsType(DataType::BOOL);
252 if_inst->SetCc(CC_NE);
253 if_inst->SetImm(0);
254 if_inst->SetInput(0, cmp);
255 G->AppendInst(if_inst);
256 auto K = GetGraph()->CreateEmptyBlock();
257 G->AddSucc(N);
258 N->AddSucc(K);
259 K->AddSucc(G);
260
261 // Check handle tree update
262 EXPECT_FALSE(GetGraph()->GetAnalysis<Rpo>().IsValid());
263 GetGraph()->GetAnalysis<Rpo>().SetValid(true);
264 GetGraph()->GetAnalysis<Rpo>().AddBasicBlockAfter(G, N);
265 GetGraph()->GetAnalysis<Rpo>().AddBasicBlockAfter(N, K);
266 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
267 GetGraph()->RunPass<LoopAnalyzer>();
268 GraphChecker(GetGraph()).Check();
269
270 Check_Subsequence({A, B, D, L, exit});
271 Check_Subsequence({A, C, E, D, L, exit});
272 Check_Subsequence({A, C, E, M});
273
274 // Check tree rebuilding
275 EXPECT_TRUE(GetGraph()->GetAnalysis<Rpo>().IsValid());
276 GetGraph()->GetAnalysis<Rpo>().SetValid(false);
277 Check_Subsequence({A, B, D, L, exit});
278 Check_Subsequence({A, C, E, D, L, exit});
279 Check_Subsequence({A, C, E, M});
280 }
281 } // namespace panda::compiler
282