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 "jit/profiling_data.h"
18 #include "compiler/optimizer/analysis/linear_order.h"
19 #include "compiler/optimizer/optimizations/loop_peeling.h"
20 #include "compiler/optimizer/optimizations/loop_unroll.h"
21
22 namespace panda::compiler {
23 class LinearOrderTest : public AsmTest {
24 public:
LinearOrderTest()25 LinearOrderTest() : default_threshold_(compiler::options.GetCompilerFreqBasedBranchReorderThreshold())
26 {
27 compiler::options.SetCompilerFreqBasedBranchReorderThreshold(10);
28 }
29
~LinearOrderTest()30 ~LinearOrderTest() override
31 {
32 compiler::options.SetCompilerFreqBasedBranchReorderThreshold(default_threshold_);
33 }
34
StartProfiling()35 void StartProfiling()
36 {
37 auto method = reinterpret_cast<Method *>(GetGraph()->GetMethod());
38 Locks::mutator_lock->WriteLock();
39 method->StartProfiling();
40 Locks::mutator_lock->Unlock();
41 }
42
UpdateBranchTaken(uint32_t pc,uint32_t count=1)43 void UpdateBranchTaken(uint32_t pc, uint32_t count = 1)
44 {
45 auto method = reinterpret_cast<Method *>(GetGraph()->GetMethod());
46 auto profiling_data = method->GetProfilingData();
47 for (uint32_t i = 0; i < count; i++) {
48 profiling_data->UpdateBranchTaken(pc);
49 }
50 }
51
UpdateBranchNotTaken(uint32_t pc,uint32_t count=1)52 void UpdateBranchNotTaken(uint32_t pc, uint32_t count = 1)
53 {
54 auto method = reinterpret_cast<Method *>(GetGraph()->GetMethod());
55 auto profiling_data = method->GetProfilingData();
56 for (uint32_t i = 0; i < count; i++) {
57 profiling_data->UpdateBranchNotTaken(pc);
58 }
59 }
60
Reset()61 void Reset()
62 {
63 GetGraph()->GetValidAnalysis<LinearOrder>().SetValid(false);
64 auto blocks = GetGraph()->GetVectorBlocks();
65 std::for_each(std::begin(blocks), std::end(blocks), [](BasicBlock *b) {
66 if (b != nullptr) {
67 b->SetNeedsJump(false);
68 }
69 });
70 }
71
GetOrderedBasicBlock(uint32_t id,uint32_t pos)72 const BasicBlock *GetOrderedBasicBlock(uint32_t id, uint32_t pos)
73 {
74 const auto &blocks = GetGraph()->GetBlocksLinearOrder();
75 return *(std::find_if(std::begin(blocks), std::end(blocks), [id](BasicBlock *b) { return b->GetId() == id; }) +
76 pos);
77 }
78
CheckOrder(uint32_t id,std::initializer_list<uint32_t> expected)79 bool CheckOrder(uint32_t id, std::initializer_list<uint32_t> expected)
80 {
81 Reset();
82 const auto &blocks = GetGraph()->GetBlocksLinearOrder();
83 auto actual_it =
84 std::find_if(std::begin(blocks), std::end(blocks), [id](BasicBlock *b) { return b->GetId() == id; }) + 1;
85 auto expected_it = std::begin(expected);
86 while (actual_it != std::end(blocks) && expected_it != std::end(expected)) {
87 if ((*actual_it)->GetId() != *expected_it) {
88 return false;
89 }
90 ++actual_it;
91 ++expected_it;
92 }
93 return expected_it == std::end(expected);
94 }
95
96 private:
97 uint32_t default_threshold_;
98 };
99
TEST_F(LinearOrderTest,RareLoopSideExit)100 TEST_F(LinearOrderTest, RareLoopSideExit)
101 {
102 auto source = R"(
103 .record Test <> {
104 u1 a <static>
105 }
106 .function i32 foo() <static> {
107 movi v0, 0xa
108 movi v1, 0x0
109 mov v2, v1
110 jump_label_2: lda v2
111 jge v0, jump_label_0
112 ldstatic Test.a
113 jeqz jump_label_1
114 lda v2
115 return
116 jump_label_1: lda v1
117 addi 0x1
118 sta v3
119 lda v2
120 addi 0x1
121 sta v1
122 mov v2, v1
123 mov v1, v3
124 jmp jump_label_2
125 jump_label_0: lda v1
126 return
127 }
128 )";
129 ASSERT_TRUE(ParseToGraph(source, "foo"));
130 ASSERT_TRUE(CheckOrder(2, {4, 3})) << "Unexpected initial order";
131
132 StartProfiling();
133 UpdateBranchTaken(0xF);
134
135 ASSERT_TRUE(CheckOrder(2, {3, 4})) << "Unexpected order";
136 }
137
TEST_F(LinearOrderTest,FrequencyThreshold)138 TEST_F(LinearOrderTest, FrequencyThreshold)
139 {
140 auto source = R"(
141 .record Test <> {
142 u1 f <static>
143 }
144 .function void foo() <static> {
145 return.void
146 }
147
148 .function void bar() <static> {
149 return.void
150 }
151 .function void main() <static> {
152 movi v0, 0x64
153 movi v1, 0x0
154 jump_label_3: lda v1
155 jge v0, jump_label_0
156 ldstatic Test.f
157 jeqz jump_label_1
158 call.short foo
159 jmp jump_label_2
160 jump_label_1: call.short bar
161 jump_label_2: inci v1, 0x1
162 jmp jump_label_3
163 jump_label_0: return.void
164 }
165 )";
166 ASSERT_TRUE(ParseToGraph(source, "main"));
167 ASSERT_TRUE(CheckOrder(2, {4, 3, 5})) << "Unexpected initial order";
168
169 StartProfiling();
170 UpdateBranchNotTaken(0xD, 90);
171 UpdateBranchTaken(0xD, 99);
172
173 ASSERT_TRUE(CheckOrder(2, {4, 3, 5})) << "Unexpected order, threshold was not exceeded";
174
175 UpdateBranchTaken(0xD);
176 ASSERT_TRUE(CheckOrder(2, {3, 5, 4})) << "Unexpected order, threshold was exceeded";
177
178 UpdateBranchNotTaken(0xD, 21);
179 ASSERT_TRUE(CheckOrder(2, {3, 4, 5})) << "Unexpected order, another branch didn't exceed threshold";
180
181 UpdateBranchNotTaken(0xD);
182 ASSERT_TRUE(CheckOrder(2, {4, 5, 3})) << "Unexpected order, another branch exceeded threshold";
183 }
184
TEST_F(LinearOrderTest,LoopTransform)185 TEST_F(LinearOrderTest, LoopTransform)
186 {
187 auto source = R"(
188 .function i32 foo() <static> {
189 movi v0, 0x64
190 movi v1, 0x0
191 mov v2, v1
192 jump_label_3: lda v2
193 jge v0, jump_label_0
194 lda v2
195 modi 0x3
196 jnez jump_label_1
197 lda v1
198 addi 0x2
199 sta v3
200 mov v1, v3
201 jmp jump_label_2
202 jump_label_1: lda v1
203 addi 0x3
204 sta v3
205 mov v1, v3
206 jump_label_2: inci v2, 0x1
207 jmp jump_label_3
208 jump_label_0: lda v1
209 return
210 }
211 )";
212 ASSERT_TRUE(ParseToGraph(source, "foo"));
213 ASSERT_TRUE(GetGraph()->RunPass<LoopPeeling>());
214 ASSERT_TRUE(GetGraph()->RunPass<Cleanup>());
215 ASSERT_TRUE(GetGraph()->RunPass<LoopUnroll>(100, 3));
216
217 ASSERT_TRUE(CheckOrder(20, {4, 3, 5, 22, 24, 25, 23, 26, 28, 29, 27, 21, 1})) << "Unexpected initial order";
218
219 StartProfiling();
220 UpdateBranchTaken(0x10, 10);
221 UpdateBranchNotTaken(0x10);
222
223 ASSERT_TRUE(CheckOrder(20, {3, 5, 22, 25, 23, 26, 29, 27, 21, 28, 24, 4, 1}))
224 << "Unexpected order, threshold was exceeded";
225
226 UpdateBranchNotTaken(0x10, 20);
227
228 ASSERT_TRUE(CheckOrder(20, {4, 5, 22, 24, 23, 26, 28, 27, 21, 29, 25, 3, 1}))
229 << "Unexpected order, another branch threshold was exceeded";
230 }
231 } // namespace panda::compiler
232