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
20namespace panda::compiler {
21class RpoTest : public GraphTest {
22public:
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
37TEST_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 */
79TEST_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 */
198TEST_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