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 "berberis/backend/code_emitter.h"
20 #include "berberis/backend/x86_64/machine_ir.h"
21 #include "berberis/backend/x86_64/machine_ir_builder.h"
22 #include "berberis/backend/x86_64/machine_ir_check.h"
23 #include "berberis/base/arena_alloc.h"
24 #include "berberis/guest_state/guest_addr.h"
25
26 #include "berberis/backend/x86_64/machine_ir_test_corpus.h"
27
28 namespace berberis {
29
30 namespace {
31
TEST(MachineIRCheckTest,BasicBlockNotDstOfInEdgeLists)32 TEST(MachineIRCheckTest, BasicBlockNotDstOfInEdgeLists) {
33 Arena arena;
34 x86_64::MachineIR machine_ir(&arena);
35
36 auto* bb1 = machine_ir.NewBasicBlock();
37 auto* bb2 = machine_ir.NewBasicBlock();
38 machine_ir.bb_list().push_back(bb1);
39 machine_ir.bb_list().push_back(bb2);
40
41 auto* bad_edge = NewInArena<MachineEdge>(&arena, &arena, bb1, bb2);
42 auto* good_edge = NewInArena<MachineEdge>(&arena, &arena, bb2, bb1);
43 bb1->in_edges().push_back(bad_edge);
44 bb2->out_edges().push_back(good_edge);
45
46 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
47 }
48
TEST(MachineIRCheckTest,BasicBlockNotSrcOfItsOutEdgeLists)49 TEST(MachineIRCheckTest, BasicBlockNotSrcOfItsOutEdgeLists) {
50 Arena arena;
51 x86_64::MachineIR machine_ir(&arena);
52
53 auto* bb1 = machine_ir.NewBasicBlock();
54 auto* bb2 = machine_ir.NewBasicBlock();
55 machine_ir.bb_list().push_back(bb1);
56 machine_ir.bb_list().push_back(bb2);
57
58 auto* bad_edge = NewInArena<MachineEdge>(&arena, &arena, bb2, bb1);
59 auto* good_edge = NewInArena<MachineEdge>(&arena, &arena, bb1, bb2);
60 bb1->out_edges().push_back(bad_edge);
61 bb2->in_edges().push_back(good_edge);
62
63 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
64 }
65
TEST(MachineIRCheckTest,EdgeIsNotIncomingForItsDst)66 TEST(MachineIRCheckTest, EdgeIsNotIncomingForItsDst) {
67 Arena arena;
68 x86_64::MachineIR machine_ir(&arena);
69
70 auto* bb1 = machine_ir.NewBasicBlock();
71 auto* bb2 = machine_ir.NewBasicBlock();
72
73 auto* bb1_to_bb2_edge = NewInArena<MachineEdge>(&arena, &arena, bb1, bb2);
74 bb1->out_edges().push_back(bb1_to_bb2_edge);
75
76 x86_64::MachineIRBuilder builder(&machine_ir);
77 builder.StartBasicBlock(bb1);
78 builder.Gen<PseudoBranch>(bb2);
79 builder.StartBasicBlock(bb2);
80 builder.Gen<PseudoJump>(kNullGuestAddr);
81
82 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckDanglingEdge);
83 }
84
TEST(MachineIRCheckTest,EdgeIsNotOutgoingForItsSrc)85 TEST(MachineIRCheckTest, EdgeIsNotOutgoingForItsSrc) {
86 Arena arena;
87 x86_64::MachineIR machine_ir(&arena);
88
89 auto* bb1 = machine_ir.NewBasicBlock();
90 auto* bb2 = machine_ir.NewBasicBlock();
91 // Create two edges so that we don't encounter dongling basic block error.
92 auto* bb1_to_bb2_edge = NewInArena<MachineEdge>(&arena, &arena, bb1, bb2);
93 auto* bb2_to_bb1_edge = NewInArena<MachineEdge>(&arena, &arena, bb2, bb1);
94 bb2->in_edges().push_back(bb1_to_bb2_edge);
95 bb1->in_edges().push_back(bb2_to_bb1_edge);
96
97 x86_64::MachineIRBuilder builder(&machine_ir);
98 builder.StartBasicBlock(bb1);
99 builder.Gen<PseudoJump>(kNullGuestAddr);
100 builder.StartBasicBlock(bb2);
101 builder.Gen<PseudoJump>(kNullGuestAddr);
102
103 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckDanglingEdge);
104 }
105
TEST(MachineIRCheckTest,DanglingBasicBlock)106 TEST(MachineIRCheckTest, DanglingBasicBlock) {
107 Arena arena;
108 x86_64::MachineIR machine_ir(&arena);
109
110 // bb1 is on IR's list and links to bb2, so that the checker can find bb2.
111 // But bb2 isn't on IR's list.
112 auto* bb1 = machine_ir.NewBasicBlock();
113 auto* bb2 = machine_ir.NewBasicBlock();
114 machine_ir.bb_list().push_back(bb1);
115
116 machine_ir.AddEdge(bb1, bb2);
117
118 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckDanglingBasicBlock);
119 }
120
TEST(MachineIRCheckTest,SimpleWellFormedMachineIR)121 TEST(MachineIRCheckTest, SimpleWellFormedMachineIR) {
122 Arena arena;
123 x86_64::MachineIR machine_ir(&arena);
124
125 auto* bb1 = machine_ir.NewBasicBlock();
126 auto* bb2 = machine_ir.NewBasicBlock();
127
128 machine_ir.AddEdge(bb1, bb2);
129
130 x86_64::MachineIRBuilder builder(&machine_ir);
131
132 MachineReg vreg1 = machine_ir.AllocVReg();
133 MachineReg vreg2 = machine_ir.AllocVReg();
134
135 builder.StartBasicBlock(bb1);
136 builder.Gen<x86_64::MovqRegImm>(vreg1, 0);
137 builder.Gen<x86_64::MovqRegImm>(vreg2, 0);
138 builder.Gen<PseudoBranch>(bb2);
139
140 builder.StartBasicBlock(bb2);
141 builder.Gen<PseudoJump>(kNullGuestAddr);
142
143 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
144 }
145
TEST(MachineIRCheckTest,CorpusWellFormedMachineIRs)146 TEST(MachineIRCheckTest, CorpusWellFormedMachineIRs) {
147 Arena arena;
148
149 x86_64::MachineIR machine_ir1(&arena);
150 BuildDataFlowAcrossBasicBlocks(&machine_ir1);
151 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir1), x86_64::kMachineIRCheckSuccess);
152
153 x86_64::MachineIR machine_ir2(&arena);
154 BuildDataFlowFromTwoPreds(&machine_ir2);
155 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir2), x86_64::kMachineIRCheckSuccess);
156
157 x86_64::MachineIR machine_ir3(&arena);
158 BuildDataFlowToTwoSuccs(&machine_ir3);
159 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir3), x86_64::kMachineIRCheckSuccess);
160
161 x86_64::MachineIR machine_ir4(&arena);
162 BuildDataFlowToTwoSuccs(&machine_ir4);
163 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir4), x86_64::kMachineIRCheckSuccess);
164 }
165
TEST(MachineIRCheckTest,NoControlFlow)166 TEST(MachineIRCheckTest, NoControlFlow) {
167 Arena arena;
168 x86_64::MachineIR machine_ir(&arena);
169
170 auto* bb = machine_ir.NewBasicBlock();
171 machine_ir.bb_list().push_back(bb);
172
173 MachineReg reg1 = machine_ir.AllocVReg();
174 MachineReg reg2 = machine_ir.AllocVReg();
175 PseudoCopy* insn = machine_ir.NewInsn<PseudoCopy>(reg1, reg2, 8);
176
177 bb->insn_list().push_back(insn);
178
179 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
180 }
181
TEST(MachineIRCheckTest,MisplacedJump)182 TEST(MachineIRCheckTest, MisplacedJump) {
183 Arena arena;
184 x86_64::MachineIR machine_ir(&arena);
185
186 x86_64::MachineIRBuilder builder(&machine_ir);
187 auto* bb = machine_ir.NewBasicBlock();
188
189 MachineReg vreg = machine_ir.AllocVReg();
190
191 builder.StartBasicBlock(bb);
192 builder.Gen<PseudoJump>(kNullGuestAddr);
193 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
194
195 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
196 }
197
TEST(MachineIRCheckTest,MisplacedIndirectJump)198 TEST(MachineIRCheckTest, MisplacedIndirectJump) {
199 Arena arena;
200 x86_64::MachineIR machine_ir(&arena);
201
202 x86_64::MachineIRBuilder builder(&machine_ir);
203 auto* bb = machine_ir.NewBasicBlock();
204
205 MachineReg vreg = machine_ir.AllocVReg();
206
207 builder.StartBasicBlock(bb);
208 builder.Gen<PseudoIndirectJump>(vreg);
209 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
210
211 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
212 }
213
TEST(MachineIRCheckTest,MisplacedPseudoBranch)214 TEST(MachineIRCheckTest, MisplacedPseudoBranch) {
215 Arena arena;
216 x86_64::MachineIR machine_ir(&arena);
217
218 x86_64::MachineIRBuilder builder(&machine_ir);
219 auto* bb1 = machine_ir.NewBasicBlock();
220 auto* bb2 = machine_ir.NewBasicBlock();
221
222 machine_ir.AddEdge(bb1, bb2);
223
224 MachineReg vreg = machine_ir.AllocVReg();
225
226 builder.StartBasicBlock(bb1);
227 builder.Gen<PseudoBranch>(bb2);
228 builder.Gen<x86_64::MovqRegImm>(vreg, 0);
229
230 builder.StartBasicBlock(bb2);
231 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
232 builder.Gen<PseudoJump>(kNullGuestAddr);
233
234 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
235 }
236
TEST(MachineIRCheckTest,MisplacedPseudoCondBranch)237 TEST(MachineIRCheckTest, MisplacedPseudoCondBranch) {
238 Arena arena;
239 x86_64::MachineIR machine_ir(&arena);
240
241 x86_64::MachineIRBuilder builder(&machine_ir);
242 auto* bb1 = machine_ir.NewBasicBlock();
243 auto* bb2 = machine_ir.NewBasicBlock();
244 auto* bb3 = machine_ir.NewBasicBlock();
245
246 machine_ir.AddEdge(bb1, bb2);
247 machine_ir.AddEdge(bb1, bb3);
248
249 MachineReg vreg = machine_ir.AllocVReg();
250
251 builder.StartBasicBlock(bb1);
252 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
253 builder.Gen<x86_64::MovqRegImm>(vreg, 0);
254
255 builder.StartBasicBlock(bb2);
256 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
257 builder.Gen<PseudoJump>(kNullGuestAddr);
258
259 builder.StartBasicBlock(bb3);
260 builder.Gen<x86_64::MovqRegImm>(vreg, 1);
261 builder.Gen<PseudoJump>(kNullGuestAddr);
262
263 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
264 }
265
TEST(MachineIRCheckTest,NoThenEdgePseudoBranch)266 TEST(MachineIRCheckTest, NoThenEdgePseudoBranch) {
267 Arena arena;
268 x86_64::MachineIR machine_ir(&arena);
269
270 x86_64::MachineIRBuilder builder(&machine_ir);
271 auto* bb1 = machine_ir.NewBasicBlock();
272 auto* bb2 = machine_ir.NewBasicBlock();
273
274 MachineReg vreg = machine_ir.AllocVReg();
275
276 builder.StartBasicBlock(bb1);
277 builder.Gen<x86_64::MovqRegImm>(vreg, 0);
278 builder.Gen<PseudoBranch>(bb2);
279
280 builder.StartBasicBlock(bb2);
281 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
282 builder.Gen<PseudoJump>(kNullGuestAddr);
283
284 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckDanglingBasicBlock);
285 }
286
TEST(MachineIRCheckTest,NoThenEdgePseudoCondBranch)287 TEST(MachineIRCheckTest, NoThenEdgePseudoCondBranch) {
288 Arena arena;
289 x86_64::MachineIR machine_ir(&arena);
290
291 x86_64::MachineIRBuilder builder(&machine_ir);
292 auto* bb1 = machine_ir.NewBasicBlock();
293 auto* bb2 = machine_ir.NewBasicBlock();
294 auto* bb3 = machine_ir.NewBasicBlock();
295
296 machine_ir.AddEdge(bb1, bb3);
297
298 MachineReg vreg = machine_ir.AllocVReg();
299
300 builder.StartBasicBlock(bb1);
301 builder.Gen<x86_64::MovqRegImm>(vreg, 0);
302 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
303
304 builder.StartBasicBlock(bb2);
305 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
306 builder.Gen<PseudoJump>(kNullGuestAddr);
307
308 builder.StartBasicBlock(bb3);
309 builder.Gen<x86_64::MovqRegImm>(vreg, 1);
310 builder.Gen<PseudoJump>(kNullGuestAddr);
311
312 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
313 }
314
TEST(MachineIRCheckTest,NoElseEdgePseudoCondBranch)315 TEST(MachineIRCheckTest, NoElseEdgePseudoCondBranch) {
316 Arena arena;
317 x86_64::MachineIR machine_ir(&arena);
318
319 x86_64::MachineIRBuilder builder(&machine_ir);
320 auto* bb1 = machine_ir.NewBasicBlock();
321 auto* bb2 = machine_ir.NewBasicBlock();
322 auto* bb3 = machine_ir.NewBasicBlock();
323
324 machine_ir.AddEdge(bb1, bb2);
325
326 MachineReg vreg = machine_ir.AllocVReg();
327
328 builder.StartBasicBlock(bb1);
329 builder.Gen<x86_64::MovqRegImm>(vreg, 0);
330 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
331
332 builder.StartBasicBlock(bb2);
333 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
334 builder.Gen<PseudoJump>(kNullGuestAddr);
335
336 builder.StartBasicBlock(bb3);
337 builder.Gen<x86_64::MovqRegImm>(vreg, 1);
338 builder.Gen<PseudoJump>(kNullGuestAddr);
339
340 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckFail);
341 }
342
343 } // namespace
344
345 } // namespace berberis
346