1 /*
2  * Copyright (C) 2023 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "gtest/gtest.h"
18 
19 #include <vector>
20 
21 #include "berberis/backend/x86_64/machine_ir_analysis.h"
22 
23 #include "berberis/backend/code_emitter.h"
24 #include "berberis/backend/x86_64/machine_ir.h"
25 #include "berberis/backend/x86_64/machine_ir_builder.h"
26 #include "berberis/backend/x86_64/machine_ir_check.h"
27 #include "berberis/base/algorithm.h"
28 #include "berberis/base/logging.h"
29 #include "berberis/guest_state/guest_addr.h"
30 
31 namespace berberis {
32 
33 namespace {
34 
CheckLoopContent(x86_64::Loop * loop,std::vector<MachineBasicBlock * > body)35 void CheckLoopContent(x86_64::Loop* loop, std::vector<MachineBasicBlock*> body) {
36   EXPECT_EQ(loop->size(), body.size());
37 
38   // Loop head must be the first basic block in the loop.
39   EXPECT_EQ(loop->at(0), body[0]);
40 
41   for (auto* bb : body) {
42     EXPECT_TRUE(Contains(*loop, bb));
43   }
44 }
45 
TEST(MachineIRAnalysis,SelfLoop)46 TEST(MachineIRAnalysis, SelfLoop) {
47   Arena arena;
48   x86_64::MachineIR machine_ir(&arena);
49 
50   x86_64::MachineIRBuilder builder(&machine_ir);
51 
52   // bb1 -- bb2 -- bb3
53   //        | |
54   //        ---
55   auto bb1 = machine_ir.NewBasicBlock();
56   auto bb2 = machine_ir.NewBasicBlock();
57   auto bb3 = machine_ir.NewBasicBlock();
58   machine_ir.AddEdge(bb1, bb2);
59   machine_ir.AddEdge(bb2, bb2);
60   machine_ir.AddEdge(bb2, bb3);
61 
62   builder.StartBasicBlock(bb1);
63   builder.Gen<PseudoBranch>(bb2);
64 
65   builder.StartBasicBlock(bb2);
66   builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
67 
68   builder.StartBasicBlock(bb3);
69   builder.Gen<PseudoJump>(kNullGuestAddr);
70 
71   ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
72   auto loops = x86_64::FindLoops(&machine_ir);
73   EXPECT_EQ(loops.size(), 1UL);
74   auto loop = loops[0];
75   CheckLoopContent(loop, {bb2});
76 }
77 
TEST(MachineIRAnalysis,SingleLoop)78 TEST(MachineIRAnalysis, SingleLoop) {
79   Arena arena;
80   x86_64::MachineIR machine_ir(&arena);
81 
82   x86_64::MachineIRBuilder builder(&machine_ir);
83 
84   // bb1 -- bb2 -- bb3 ---- bb4
85   //         |      |
86   //         --------
87   auto bb1 = machine_ir.NewBasicBlock();
88   auto bb2 = machine_ir.NewBasicBlock();
89   auto bb3 = machine_ir.NewBasicBlock();
90   auto bb4 = machine_ir.NewBasicBlock();
91   machine_ir.AddEdge(bb1, bb2);
92   machine_ir.AddEdge(bb2, bb3);
93   machine_ir.AddEdge(bb3, bb2);
94   machine_ir.AddEdge(bb3, bb4);
95 
96   builder.StartBasicBlock(bb1);
97   builder.Gen<PseudoBranch>(bb2);
98 
99   builder.StartBasicBlock(bb2);
100   builder.Gen<PseudoBranch>(bb3);
101 
102   builder.StartBasicBlock(bb3);
103   builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb4, x86_64::kMachineRegFLAGS);
104 
105   builder.StartBasicBlock(bb4);
106   builder.Gen<PseudoJump>(kNullGuestAddr);
107 
108   ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
109   auto loops = x86_64::FindLoops(&machine_ir);
110   EXPECT_EQ(loops.size(), 1UL);
111   auto loop = loops[0];
112   CheckLoopContent(loop, {bb2, bb3});
113 }
114 
TEST(MachineIRAnalysis,MultipleBackEdges)115 TEST(MachineIRAnalysis, MultipleBackEdges) {
116   Arena arena;
117   x86_64::MachineIR machine_ir(&arena);
118 
119   x86_64::MachineIRBuilder builder(&machine_ir);
120 
121   //         -----------------
122   //         |               |
123   // bb1 -- bb2 -- bb3 ---- bb4
124   //         |      |
125   //         --------
126   auto bb1 = machine_ir.NewBasicBlock();
127   auto bb2 = machine_ir.NewBasicBlock();
128   auto bb3 = machine_ir.NewBasicBlock();
129   auto bb4 = machine_ir.NewBasicBlock();
130   machine_ir.AddEdge(bb1, bb2);
131   machine_ir.AddEdge(bb2, bb3);
132   machine_ir.AddEdge(bb3, bb2);
133   machine_ir.AddEdge(bb3, bb4);
134   machine_ir.AddEdge(bb4, bb2);
135 
136   builder.StartBasicBlock(bb1);
137   builder.Gen<PseudoBranch>(bb2);
138 
139   builder.StartBasicBlock(bb2);
140   builder.Gen<PseudoBranch>(bb3);
141 
142   builder.StartBasicBlock(bb3);
143   builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb4, x86_64::kMachineRegFLAGS);
144 
145   builder.StartBasicBlock(bb4);
146   builder.Gen<PseudoBranch>(bb2);
147 
148   ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
149   auto loops = x86_64::FindLoops(&machine_ir);
150   EXPECT_EQ(loops.size(), 1UL);
151   auto loop = loops[0];
152   CheckLoopContent(loop, {bb2, bb3, bb4});
153 }
154 
TEST(MachineIRAnalysis,TwoLoops)155 TEST(MachineIRAnalysis, TwoLoops) {
156   Arena arena;
157   x86_64::MachineIR machine_ir(&arena);
158 
159   x86_64::MachineIRBuilder builder(&machine_ir);
160 
161   //         ------------------------
162   //         |                      |
163   // bb0---bb1 -- bb2 -- bb3 ---- bb4
164   //               |      |
165   //               --------
166   auto bb0 = machine_ir.NewBasicBlock();
167   auto bb1 = machine_ir.NewBasicBlock();
168   auto bb2 = machine_ir.NewBasicBlock();
169   auto bb3 = machine_ir.NewBasicBlock();
170   auto bb4 = machine_ir.NewBasicBlock();
171   machine_ir.AddEdge(bb0, bb1);
172   machine_ir.AddEdge(bb1, bb2);
173   machine_ir.AddEdge(bb2, bb3);
174   machine_ir.AddEdge(bb3, bb2);
175   machine_ir.AddEdge(bb3, bb4);
176   machine_ir.AddEdge(bb4, bb1);
177 
178   builder.StartBasicBlock(bb0);
179   builder.Gen<PseudoBranch>(bb1);
180 
181   builder.StartBasicBlock(bb1);
182   builder.Gen<PseudoBranch>(bb2);
183 
184   builder.StartBasicBlock(bb2);
185   builder.Gen<PseudoBranch>(bb3);
186 
187   builder.StartBasicBlock(bb3);
188   builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb4, x86_64::kMachineRegFLAGS);
189 
190   builder.StartBasicBlock(bb4);
191   builder.Gen<PseudoBranch>(bb1);
192 
193   ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
194   auto loops = x86_64::FindLoops(&machine_ir);
195   EXPECT_EQ(loops.size(), 2UL);
196   auto loop1 = loops[0];
197   CheckLoopContent(loop1, {bb1, bb2, bb3, bb4});
198   auto loop2 = loops[1];
199   CheckLoopContent(loop2, {bb2, bb3});
200 }
201 
TEST(MachineIRAnalysis,LoopTreeInsertLoop)202 TEST(MachineIRAnalysis, LoopTreeInsertLoop) {
203   Arena arena;
204   x86_64::MachineIR machine_ir(&arena);
205 
206   auto* bb1 = machine_ir.NewBasicBlock();
207   x86_64::Loop loop1(&arena);
208   loop1.push_back(bb1);
209 
210   x86_64::LoopTree tree(&machine_ir);
211   tree.InsertLoop(&loop1);
212 
213   EXPECT_EQ(tree.root()->loop(), nullptr);
214   EXPECT_EQ(tree.root()->NumInnerloops(), 1UL);
215 
216   auto* node = tree.root()->GetInnerloopNode(0);
217   CheckLoopContent(node->loop(), {bb1});
218   EXPECT_EQ(node->NumInnerloops(), 0UL);
219 }
220 
TEST(MachineIRAnalysis,LoopTreeInsertParallelLoops)221 TEST(MachineIRAnalysis, LoopTreeInsertParallelLoops) {
222   Arena arena;
223   x86_64::MachineIR machine_ir(&arena);
224 
225   auto* bb1 = machine_ir.NewBasicBlock();
226   auto* bb2 = machine_ir.NewBasicBlock();
227   auto* bb3 = machine_ir.NewBasicBlock();
228   x86_64::Loop loop1(&arena);
229   loop1.push_back(bb1);
230   loop1.push_back(bb2);
231   x86_64::Loop loop2(&arena);
232   loop2.push_back(bb3);
233 
234   x86_64::LoopTree tree(&machine_ir);
235   tree.InsertLoop(&loop1);
236   tree.InsertLoop(&loop2);
237 
238   EXPECT_EQ(tree.root()->loop(), nullptr);
239   EXPECT_EQ(tree.root()->NumInnerloops(), 2UL);
240 
241   auto* node1 = tree.root()->GetInnerloopNode(0);
242   CheckLoopContent(node1->loop(), {bb1, bb2});
243   EXPECT_EQ(node1->NumInnerloops(), 0UL);
244 
245   auto* node2 = tree.root()->GetInnerloopNode(1);
246   CheckLoopContent(node2->loop(), {bb3});
247   EXPECT_EQ(node2->NumInnerloops(), 0UL);
248 }
249 
TEST(MachineIRAnalysis,LoopTreeInsertNestedLoops)250 TEST(MachineIRAnalysis, LoopTreeInsertNestedLoops) {
251   Arena arena;
252   x86_64::MachineIR machine_ir(&arena);
253 
254   auto* bb1 = machine_ir.NewBasicBlock();
255   auto* bb2 = machine_ir.NewBasicBlock();
256   x86_64::Loop loop1(&arena);
257   loop1.push_back(bb1);
258   loop1.push_back(bb2);
259   x86_64::Loop loop2(&arena);
260   loop2.push_back(bb2);
261 
262   x86_64::LoopTree tree(&machine_ir);
263   tree.InsertLoop(&loop1);
264   tree.InsertLoop(&loop2);
265 
266   EXPECT_EQ(tree.root()->loop(), nullptr);
267   EXPECT_EQ(tree.root()->NumInnerloops(), 1UL);
268 
269   auto* node1 = tree.root()->GetInnerloopNode(0);
270   CheckLoopContent(node1->loop(), {bb1, bb2});
271   EXPECT_EQ(node1->NumInnerloops(), 1UL);
272 
273   auto* node2 = node1->GetInnerloopNode(0);
274   CheckLoopContent(node2->loop(), {bb2});
275   EXPECT_EQ(node2->NumInnerloops(), 0UL);
276 }
277 
TEST(MachineIRAnalysis,FindSingleLoopTree)278 TEST(MachineIRAnalysis, FindSingleLoopTree) {
279   Arena arena;
280   x86_64::MachineIR machine_ir(&arena);
281 
282   x86_64::MachineIRBuilder builder(&machine_ir);
283 
284   // bb1 -- bb2 -- bb3
285   //        | |
286   //        ---
287   auto bb1 = machine_ir.NewBasicBlock();
288   auto bb2 = machine_ir.NewBasicBlock();
289   auto bb3 = machine_ir.NewBasicBlock();
290   machine_ir.AddEdge(bb1, bb2);
291   machine_ir.AddEdge(bb2, bb2);
292   machine_ir.AddEdge(bb2, bb3);
293 
294   builder.StartBasicBlock(bb1);
295   builder.Gen<PseudoBranch>(bb2);
296 
297   builder.StartBasicBlock(bb2);
298   builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
299 
300   builder.StartBasicBlock(bb3);
301   builder.Gen<PseudoJump>(kNullGuestAddr);
302 
303   ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
304   auto loop_tree = x86_64::BuildLoopTree(&machine_ir);
305   auto* root = loop_tree.root();
306 
307   EXPECT_EQ(root->NumInnerloops(), 1UL);
308   auto* loop_node = root->GetInnerloopNode(0);
309   CheckLoopContent(loop_node->loop(), {bb2});
310 }
311 
TEST(MachineIRAnalysis,FindNestedLoopTree)312 TEST(MachineIRAnalysis, FindNestedLoopTree) {
313   Arena arena;
314   x86_64::MachineIR machine_ir(&arena);
315 
316   x86_64::MachineIRBuilder builder(&machine_ir);
317 
318   //         ------------------------
319   //         |                      |
320   // bb0---bb1 -- bb2 -- bb3 ---- bb4
321   //               |      |
322   //               --------
323   auto bb0 = machine_ir.NewBasicBlock();
324   auto bb1 = machine_ir.NewBasicBlock();
325   auto bb2 = machine_ir.NewBasicBlock();
326   auto bb3 = machine_ir.NewBasicBlock();
327   auto bb4 = machine_ir.NewBasicBlock();
328   machine_ir.AddEdge(bb0, bb1);
329   machine_ir.AddEdge(bb1, bb2);
330   machine_ir.AddEdge(bb2, bb3);
331   machine_ir.AddEdge(bb3, bb2);
332   machine_ir.AddEdge(bb3, bb4);
333   machine_ir.AddEdge(bb4, bb1);
334 
335   builder.StartBasicBlock(bb0);
336   builder.Gen<PseudoBranch>(bb1);
337 
338   builder.StartBasicBlock(bb1);
339   builder.Gen<PseudoBranch>(bb2);
340 
341   builder.StartBasicBlock(bb2);
342   builder.Gen<PseudoBranch>(bb3);
343 
344   builder.StartBasicBlock(bb3);
345   builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb4, x86_64::kMachineRegFLAGS);
346 
347   builder.StartBasicBlock(bb4);
348   builder.Gen<PseudoBranch>(bb1);
349 
350   ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
351   auto loop_tree = x86_64::BuildLoopTree(&machine_ir);
352   auto* root = loop_tree.root();
353 
354   EXPECT_EQ(root->NumInnerloops(), 1UL);
355   auto* outerloop_node = root->GetInnerloopNode(0);
356   CheckLoopContent(outerloop_node->loop(), {bb1, bb2, bb3, bb4});
357 
358   EXPECT_EQ(outerloop_node->NumInnerloops(), 1UL);
359   auto* innerloop_node = outerloop_node->GetInnerloopNode(0);
360   CheckLoopContent(innerloop_node->loop(), {bb2, bb3});
361 }
362 
TEST(MachineIRAnalysis,FindLoopTreeWithMultipleInnerloops)363 TEST(MachineIRAnalysis, FindLoopTreeWithMultipleInnerloops) {
364   Arena arena;
365   x86_64::MachineIR machine_ir(&arena);
366 
367   x86_64::MachineIRBuilder builder(&machine_ir);
368 
369   //         -------------------------------
370   //         |                     |       |
371   // bb0---bb1 -- bb2 -- bb3 ---- bb4-----bb5
372   //               |      |
373   //               --------
374   auto bb0 = machine_ir.NewBasicBlock();
375   auto bb1 = machine_ir.NewBasicBlock();
376   auto bb2 = machine_ir.NewBasicBlock();
377   auto bb3 = machine_ir.NewBasicBlock();
378   auto bb4 = machine_ir.NewBasicBlock();
379   auto bb5 = machine_ir.NewBasicBlock();
380   machine_ir.AddEdge(bb0, bb1);
381   machine_ir.AddEdge(bb1, bb2);
382   machine_ir.AddEdge(bb2, bb3);
383   machine_ir.AddEdge(bb3, bb2);
384   machine_ir.AddEdge(bb3, bb4);
385   machine_ir.AddEdge(bb4, bb5);
386   machine_ir.AddEdge(bb5, bb4);
387   machine_ir.AddEdge(bb5, bb1);
388 
389   builder.StartBasicBlock(bb0);
390   builder.Gen<PseudoBranch>(bb1);
391 
392   builder.StartBasicBlock(bb1);
393   builder.Gen<PseudoBranch>(bb2);
394 
395   builder.StartBasicBlock(bb2);
396   builder.Gen<PseudoBranch>(bb3);
397 
398   builder.StartBasicBlock(bb3);
399   builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb4, x86_64::kMachineRegFLAGS);
400 
401   builder.StartBasicBlock(bb4);
402   builder.Gen<PseudoBranch>(bb5);
403 
404   builder.StartBasicBlock(bb5);
405   builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb1, bb4, x86_64::kMachineRegFLAGS);
406 
407   ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
408   auto loop_tree = x86_64::BuildLoopTree(&machine_ir);
409   auto* root = loop_tree.root();
410 
411   EXPECT_EQ(root->NumInnerloops(), 1UL);
412   auto* outerloop_node = root->GetInnerloopNode(0);
413   CheckLoopContent(outerloop_node->loop(), {bb1, bb2, bb3, bb4, bb5});
414 
415   EXPECT_EQ(outerloop_node->NumInnerloops(), 2UL);
416   auto* innerloop_node1 = outerloop_node->GetInnerloopNode(0);
417   CheckLoopContent(innerloop_node1->loop(), {bb2, bb3});
418   auto* innerloop_node2 = outerloop_node->GetInnerloopNode(1);
419   CheckLoopContent(innerloop_node2->loop(), {bb4, bb5});
420 }
421 
422 }  // namespace
423 
424 }  // namespace berberis
425