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/x86_64/machine_ir_opt.h"
20
21 #include "berberis/backend/code_emitter.h"
22 #include "berberis/backend/common/machine_ir_opt.h"
23 #include "berberis/backend/x86_64/machine_ir.h"
24 #include "berberis/backend/x86_64/machine_ir_builder.h"
25 #include "berberis/backend/x86_64/machine_ir_check.h"
26 #include "berberis/backend/x86_64/machine_ir_test_corpus.h"
27 #include "berberis/base/arena_alloc.h"
28 #include "berberis/guest_state/guest_addr.h"
29
30 namespace berberis {
31
32 namespace {
33
TEST(MachineIRRemoveDeadCodeTest,DefKilledByAnotherDef)34 TEST(MachineIRRemoveDeadCodeTest, DefKilledByAnotherDef) {
35 Arena arena;
36 x86_64::MachineIR machine_ir(&arena);
37
38 auto* bb = machine_ir.NewBasicBlock();
39
40 x86_64::MachineIRBuilder builder(&machine_ir);
41
42 MachineReg vreg1 = machine_ir.AllocVReg();
43
44 builder.StartBasicBlock(bb);
45 builder.Gen<x86_64::MovqRegReg>(vreg1, vreg1);
46 builder.Gen<x86_64::MovqRegImm>(vreg1, 1);
47 builder.Gen<PseudoBranch>(bb);
48
49 bb->live_out().push_back(vreg1);
50
51 x86_64::RemoveDeadCode(&machine_ir);
52
53 EXPECT_EQ(bb->insn_list().size(), 2UL);
54
55 auto insn_it = bb->insn_list().begin();
56 MachineInsn* insn = *insn_it;
57 MachineReg reg_after = insn->RegAt(0);
58 MachineOpcode opcode_after = insn->opcode();
59 EXPECT_EQ(kMachineOpMovqRegImm, opcode_after);
60 EXPECT_EQ(vreg1, reg_after);
61 }
62
TEST(MachineIRRemoveDeadCodeTest,RegUsedInSameBasicBlockNotErased)63 TEST(MachineIRRemoveDeadCodeTest, RegUsedInSameBasicBlockNotErased) {
64 Arena arena;
65 x86_64::MachineIR machine_ir(&arena);
66
67 auto* bb = machine_ir.NewBasicBlock();
68
69 x86_64::MachineIRBuilder builder(&machine_ir);
70
71 MachineReg vreg1 = machine_ir.AllocVReg();
72 MachineReg vreg2 = machine_ir.AllocVReg();
73
74 builder.StartBasicBlock(bb);
75 builder.Gen<x86_64::MovqRegImm>(vreg1, 4);
76 builder.Gen<x86_64::MovqMemBaseDispReg>(vreg2, 0, vreg1);
77 builder.Gen<PseudoBranch>(bb);
78
79 bb->live_out().push_back(vreg1);
80
81 x86_64::RemoveDeadCode(&machine_ir);
82
83 EXPECT_EQ(bb->insn_list().size(), 3UL);
84
85 auto insn_it = bb->insn_list().begin();
86 MachineInsn* insn = *insn_it;
87 MachineReg reg_after = insn->RegAt(0);
88 MachineOpcode opcode_after = insn->opcode();
89 EXPECT_EQ(kMachineOpMovqRegImm, opcode_after);
90 EXPECT_EQ(vreg1, reg_after);
91 }
92
TEST(MachineIRRemoveDeadCodeTest,LiveOutRegNotErased)93 TEST(MachineIRRemoveDeadCodeTest, LiveOutRegNotErased) {
94 Arena arena;
95 x86_64::MachineIR machine_ir(&arena);
96
97 auto* bb = machine_ir.NewBasicBlock();
98
99 x86_64::MachineIRBuilder builder(&machine_ir);
100
101 MachineReg vreg1 = machine_ir.AllocVReg();
102
103 builder.StartBasicBlock(bb);
104 builder.Gen<x86_64::MovqRegImm>(vreg1, 4);
105 builder.Gen<PseudoBranch>(bb);
106
107 bb->live_out().push_back(vreg1);
108
109 x86_64::RemoveDeadCode(&machine_ir);
110
111 EXPECT_EQ(bb->insn_list().size(), 2UL);
112
113 auto insn_it = bb->insn_list().begin();
114 MachineInsn* insn = *insn_it;
115 MachineReg reg_after = insn->RegAt(0);
116 MachineOpcode opcode_after = insn->opcode();
117 EXPECT_EQ(kMachineOpMovqRegImm, opcode_after);
118 EXPECT_EQ(vreg1, reg_after);
119 }
120
TEST(MachineIRRemoveDeadCodeTest,UseOfRegBeforeDoesNotMakeInsnLive)121 TEST(MachineIRRemoveDeadCodeTest, UseOfRegBeforeDoesNotMakeInsnLive) {
122 Arena arena;
123 x86_64::MachineIR machine_ir(&arena);
124
125 auto* bb = machine_ir.NewBasicBlock();
126
127 x86_64::MachineIRBuilder builder(&machine_ir);
128
129 MachineReg vreg1 = machine_ir.AllocVReg();
130 MachineReg vreg2 = machine_ir.AllocVReg();
131
132 builder.StartBasicBlock(bb);
133 builder.Gen<x86_64::MovqRegImm>(vreg1, 4);
134 builder.Gen<x86_64::MovqRegReg>(vreg2, vreg1);
135 builder.Gen<PseudoBranch>(bb);
136
137 bb->live_out().push_back(vreg1);
138
139 x86_64::RemoveDeadCode(&machine_ir);
140
141 EXPECT_EQ(bb->insn_list().size(), 2UL);
142
143 auto insn_it = bb->insn_list().rbegin();
144 insn_it++;
145 MachineInsn* insn = *insn_it++;
146 MachineReg reg_after = insn->RegAt(0);
147 MachineOpcode opcode_after = insn->opcode();
148 EXPECT_EQ(kMachineOpMovqRegImm, opcode_after);
149 EXPECT_EQ(vreg1, reg_after);
150 }
151
TEST(MachineIRRemoveDeadCodeTest,UnusedRegErased)152 TEST(MachineIRRemoveDeadCodeTest, UnusedRegErased) {
153 Arena arena;
154 x86_64::MachineIR machine_ir(&arena);
155
156 auto* bb = machine_ir.NewBasicBlock();
157
158 x86_64::MachineIRBuilder builder(&machine_ir);
159
160 MachineReg vreg1 = machine_ir.AllocVReg();
161
162 builder.StartBasicBlock(bb);
163 builder.Gen<x86_64::MovqRegImm>(vreg1, 4);
164 builder.Gen<PseudoBranch>(bb);
165
166 x86_64::RemoveDeadCode(&machine_ir);
167
168 EXPECT_EQ(bb->insn_list().size(), 1UL);
169
170 auto insn_it = bb->insn_list().begin();
171 MachineInsn* insn = *insn_it++;
172 MachineOpcode opcode_after = insn->opcode();
173 EXPECT_EQ(kMachineOpPseudoBranch, opcode_after);
174 }
175
TEST(MachineIRRemoveDeadCodeTest,DefKilledBySecondResultOfAnotherDef)176 TEST(MachineIRRemoveDeadCodeTest, DefKilledBySecondResultOfAnotherDef) {
177 Arena arena;
178 x86_64::MachineIR machine_ir(&arena);
179
180 auto* bb = machine_ir.NewBasicBlock();
181
182 x86_64::MachineIRBuilder builder(&machine_ir);
183
184 MachineReg vreg1 = machine_ir.AllocVReg();
185 MachineReg vreg2 = machine_ir.AllocVReg();
186 MachineReg vreg3 = machine_ir.AllocVReg();
187
188 builder.StartBasicBlock(bb);
189 builder.Gen<x86_64::AddbRegImm>(vreg1, 1, vreg3);
190 builder.Gen<x86_64::AddbRegImm>(vreg2, 2, vreg3);
191 builder.Gen<PseudoBranch>(bb);
192
193 bb->live_out().push_back(vreg2);
194
195 x86_64::RemoveDeadCode(&machine_ir);
196
197 EXPECT_EQ(bb->insn_list().size(), 2UL);
198
199 auto insn_it = bb->insn_list().begin();
200 MachineInsn* insn = *insn_it++;
201 MachineReg reg_after = insn->RegAt(0);
202 MachineOpcode opcode_after = insn->opcode();
203 EXPECT_EQ(kMachineOpAddbRegImm, opcode_after);
204 EXPECT_EQ(vreg2, reg_after);
205 }
206
TEST(MachineIRRemoveDeadCodeTest,HardRegisterAccess)207 TEST(MachineIRRemoveDeadCodeTest, HardRegisterAccess) {
208 Arena arena;
209 x86_64::MachineIR machine_ir(&arena);
210
211 auto* bb = machine_ir.NewBasicBlock();
212
213 x86_64::MachineIRBuilder builder(&machine_ir);
214
215 builder.StartBasicBlock(bb);
216 builder.Gen<x86_64::AddbRegImm>(x86_64::kMachineRegRAX, 3, x86_64::kMachineRegFLAGS);
217 builder.Gen<PseudoBranch>(bb);
218
219 x86_64::RemoveDeadCode(&machine_ir);
220
221 EXPECT_EQ(bb->insn_list().size(), 2UL);
222 }
223
TEST(MachineIRRemoveDeadCodeTest,CallImmArgIsLive)224 TEST(MachineIRRemoveDeadCodeTest, CallImmArgIsLive) {
225 Arena arena;
226 x86_64::MachineIR machine_ir(&arena);
227 auto* bb = machine_ir.NewBasicBlock();
228 x86_64::MachineIRBuilder builder(&machine_ir);
229
230 builder.StartBasicBlock(bb);
231 builder.GenCallImm(0,
232 machine_ir.AllocVReg(),
233 std::array<x86_64::CallImm::Arg, 1>{
234 {{machine_ir.AllocVReg(), x86_64::CallImm::kIntRegType}}});
235 builder.Gen<PseudoJump>(kNullGuestAddr);
236
237 x86_64::RemoveDeadCode(&machine_ir);
238
239 EXPECT_EQ(bb->insn_list().size(), 4UL);
240 }
241
GetInEdgeIndex(MachineBasicBlock * dst_bb,MachineBasicBlock * src_bb)242 int GetInEdgeIndex(MachineBasicBlock* dst_bb, MachineBasicBlock* src_bb) {
243 for (size_t i = 0; i < dst_bb->in_edges().size(); i++) {
244 if (dst_bb->in_edges()[i]->src() == src_bb) {
245 return i;
246 }
247 }
248 return -1;
249 }
250
GetOutEdgeIndex(MachineBasicBlock * src_bb,MachineBasicBlock * dst_bb)251 int GetOutEdgeIndex(MachineBasicBlock* src_bb, MachineBasicBlock* dst_bb) {
252 for (size_t i = 0; i < src_bb->out_edges().size(); i++) {
253 if (src_bb->out_edges()[i]->dst() == dst_bb) {
254 return i;
255 }
256 }
257 return -1;
258 }
259
TEST(MachineIR,RemoveCriticalEdge)260 TEST(MachineIR, RemoveCriticalEdge) {
261 Arena arena;
262 berberis::x86_64::MachineIR machine_ir(&arena);
263
264 x86_64::MachineIRBuilder builder(&machine_ir);
265
266 // bb1 bb2
267 // \ / \
268 // bb3 bb4
269 auto bb1 = machine_ir.NewBasicBlock();
270 auto bb2 = machine_ir.NewBasicBlock();
271 auto bb3 = machine_ir.NewBasicBlock();
272 auto bb4 = machine_ir.NewBasicBlock();
273 machine_ir.AddEdge(bb1, bb3);
274 machine_ir.AddEdge(bb2, bb3);
275 machine_ir.AddEdge(bb2, bb4);
276
277 builder.StartBasicBlock(bb1);
278 builder.Gen<PseudoBranch>(bb3);
279
280 builder.StartBasicBlock(bb2);
281 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb3, bb4, x86_64::kMachineRegFLAGS);
282
283 builder.StartBasicBlock(bb3);
284 builder.Gen<PseudoJump>(kNullGuestAddr);
285
286 builder.StartBasicBlock(bb4);
287 builder.Gen<PseudoJump>(kNullGuestAddr);
288
289 x86_64::RemoveCriticalEdges(&machine_ir);
290 ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
291
292 ASSERT_EQ(bb3->in_edges().size(), 2UL);
293 int bb1_index_in_bb3 = GetInEdgeIndex(bb3, bb1);
294 ASSERT_NE(bb1_index_in_bb3, -1);
295 auto new_bb = bb3->in_edges()[1 - bb1_index_in_bb3]->src();
296
297 ASSERT_EQ(bb2->out_edges().size(), 2UL);
298 int bb4_index_in_bb2 = GetOutEdgeIndex(bb2, bb4);
299 ASSERT_NE(bb4_index_in_bb2, -1);
300 EXPECT_EQ(new_bb, bb2->out_edges()[1 - bb4_index_in_bb2]->dst());
301 }
302
TEST(MachineIR,RemoveCriticalEdgeLoop)303 TEST(MachineIR, RemoveCriticalEdgeLoop) {
304 Arena arena;
305 berberis::x86_64::MachineIR machine_ir(&arena);
306
307 x86_64::MachineIRBuilder builder(&machine_ir);
308
309 // bb1
310 // |
311 // bb2 <---
312 // | \__/
313 // bb3
314 auto bb1 = machine_ir.NewBasicBlock();
315 auto bb2 = machine_ir.NewBasicBlock();
316 auto bb3 = machine_ir.NewBasicBlock();
317 machine_ir.AddEdge(bb1, bb2);
318 machine_ir.AddEdge(bb2, bb2);
319 machine_ir.AddEdge(bb2, bb3);
320
321 builder.StartBasicBlock(bb1);
322 builder.Gen<PseudoBranch>(bb2);
323
324 builder.StartBasicBlock(bb2);
325 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
326
327 builder.StartBasicBlock(bb3);
328 builder.Gen<PseudoJump>(kNullGuestAddr);
329
330 x86_64::RemoveCriticalEdges(&machine_ir);
331 ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
332
333 ASSERT_EQ(bb2->in_edges().size(), 2UL);
334 int bb1_index_in_bb2 = GetInEdgeIndex(bb2, bb1);
335 ASSERT_NE(bb1_index_in_bb2, -1);
336 auto new_bb = bb2->in_edges()[1 - bb1_index_in_bb2]->src();
337
338 ASSERT_EQ(bb2->out_edges().size(), 2UL);
339 int bb3_index_in_bb2 = GetOutEdgeIndex(bb2, bb3);
340 ASSERT_NE(bb3_index_in_bb2, -1);
341 EXPECT_EQ(new_bb, bb2->out_edges()[1 - bb3_index_in_bb2]->dst());
342 }
343
TEST(MachineIR,RemoveCriticalEdgeRecovery)344 TEST(MachineIR, RemoveCriticalEdgeRecovery) {
345 Arena arena;
346 berberis::x86_64::MachineIR machine_ir(&arena);
347
348 x86_64::MachineIRBuilder builder(&machine_ir);
349
350 // bb1 bb2
351 // \ / \
352 // bb3 bb4(recovery)
353 auto bb1 = machine_ir.NewBasicBlock();
354 auto bb2 = machine_ir.NewBasicBlock();
355 auto bb3 = machine_ir.NewBasicBlock();
356 auto bb4 = machine_ir.NewBasicBlock();
357 machine_ir.AddEdge(bb1, bb3);
358 machine_ir.AddEdge(bb2, bb3);
359 machine_ir.AddEdge(bb2, bb4);
360
361 builder.StartBasicBlock(bb1);
362 builder.Gen<PseudoBranch>(bb3);
363
364 builder.StartBasicBlock(bb2);
365 builder.Gen<PseudoBranch>(bb3);
366
367 builder.StartBasicBlock(bb3);
368 builder.Gen<PseudoJump>(kNullGuestAddr);
369
370 builder.StartBasicBlock(bb4);
371 bb4->MarkAsRecovery();
372 builder.Gen<PseudoJump>(kNullGuestAddr);
373
374 x86_64::RemoveCriticalEdges(&machine_ir);
375 ASSERT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
376
377 ASSERT_EQ(bb3->in_edges().size(), 2UL);
378 int bb1_index_in_bb3 = GetInEdgeIndex(bb3, bb1);
379 ASSERT_NE(bb1_index_in_bb3, -1);
380 auto new_bb = bb3->in_edges()[1 - bb1_index_in_bb3]->src();
381
382 ASSERT_EQ(bb2->out_edges().size(), 2UL);
383 int bb4_index_in_bb2 = GetOutEdgeIndex(bb2, bb4);
384 ASSERT_NE(bb4_index_in_bb2, -1);
385 EXPECT_EQ(new_bb, bb2->out_edges()[1 - bb4_index_in_bb2]->dst());
386
387 ASSERT_EQ(bb2->insn_list().size(), 1UL);
388 ASSERT_EQ(bb2->insn_list().front()->opcode(), kMachineOpPseudoBranch);
389 ASSERT_EQ(static_cast<PseudoBranch*>(bb2->insn_list().front())->then_bb(), new_bb);
390 }
391
TEST(MachineIR,PutsInSuccessorsKillPut)392 TEST(MachineIR, PutsInSuccessorsKillPut) {
393 Arena arena;
394 x86_64::MachineIR machine_ir(&arena);
395
396 auto* bb1 = machine_ir.NewBasicBlock();
397 auto* bb2 = machine_ir.NewBasicBlock();
398 auto* bb3 = machine_ir.NewBasicBlock();
399 machine_ir.AddEdge(bb1, bb2);
400 machine_ir.AddEdge(bb1, bb3);
401 x86_64::MachineIRBuilder builder(&machine_ir);
402
403 auto vreg = machine_ir.AllocVReg();
404 builder.StartBasicBlock(bb1);
405 builder.GenPut(GetThreadStateRegOffset(0), vreg);
406 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
407
408 builder.StartBasicBlock(bb2);
409 builder.GenPut(GetThreadStateRegOffset(0), vreg);
410 builder.Gen<PseudoJump>(kNullGuestAddr);
411
412 builder.StartBasicBlock(bb3);
413 builder.GenPut(GetThreadStateRegOffset(0), vreg);
414 builder.Gen<PseudoJump>(kNullGuestAddr);
415
416 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
417 x86_64::RemoveRedundantPut(&machine_ir);
418 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
419
420 ASSERT_EQ(1u, bb1->insn_list().size());
421 ASSERT_EQ(2u, bb2->insn_list().size());
422 ASSERT_EQ(2u, bb3->insn_list().size());
423 }
424
TEST(MachineIR,PutInOneOfTwoSuccessorsDoesNotKillPut)425 TEST(MachineIR, PutInOneOfTwoSuccessorsDoesNotKillPut) {
426 Arena arena;
427 x86_64::MachineIR machine_ir(&arena);
428
429 auto* bb1 = machine_ir.NewBasicBlock();
430 auto* bb2 = machine_ir.NewBasicBlock();
431 auto* bb3 = machine_ir.NewBasicBlock();
432 machine_ir.AddEdge(bb1, bb2);
433 machine_ir.AddEdge(bb1, bb3);
434 x86_64::MachineIRBuilder builder(&machine_ir);
435
436 auto vreg = machine_ir.AllocVReg();
437 builder.StartBasicBlock(bb1);
438 builder.GenPut(GetThreadStateRegOffset(0), vreg);
439 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
440
441 builder.StartBasicBlock(bb2);
442 builder.GenPut(GetThreadStateRegOffset(0), vreg);
443 builder.Gen<PseudoJump>(kNullGuestAddr);
444
445 builder.StartBasicBlock(bb3);
446 builder.Gen<PseudoJump>(kNullGuestAddr);
447
448 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
449 x86_64::RemoveRedundantPut(&machine_ir);
450 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
451
452 ASSERT_EQ(2u, bb1->insn_list().size());
453 ASSERT_EQ(2u, bb2->insn_list().size());
454 ASSERT_EQ(1u, bb3->insn_list().size());
455 }
456
TEST(MachineIR,MultiplePutsCanBeKilled)457 TEST(MachineIR, MultiplePutsCanBeKilled) {
458 Arena arena;
459 x86_64::MachineIR machine_ir(&arena);
460
461 auto* bb1 = machine_ir.NewBasicBlock();
462 auto* bb2 = machine_ir.NewBasicBlock();
463 auto* bb3 = machine_ir.NewBasicBlock();
464 machine_ir.AddEdge(bb1, bb2);
465 machine_ir.AddEdge(bb1, bb3);
466 x86_64::MachineIRBuilder builder(&machine_ir);
467
468 auto vreg1 = machine_ir.AllocVReg();
469 auto vreg2 = machine_ir.AllocVReg();
470 builder.StartBasicBlock(bb1);
471 builder.GenPut(GetThreadStateRegOffset(0), vreg1);
472 builder.GenPut(GetThreadStateRegOffset(1), vreg2);
473 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb2, bb3, x86_64::kMachineRegFLAGS);
474
475 builder.StartBasicBlock(bb2);
476 builder.GenPut(GetThreadStateRegOffset(0), vreg1);
477 builder.GenPut(GetThreadStateRegOffset(1), vreg2);
478 builder.Gen<PseudoJump>(kNullGuestAddr);
479
480 builder.StartBasicBlock(bb3);
481 builder.GenPut(GetThreadStateRegOffset(0), vreg1);
482 builder.GenPut(GetThreadStateRegOffset(1), vreg2);
483 builder.Gen<PseudoJump>(kNullGuestAddr);
484
485 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
486 x86_64::RemoveRedundantPut(&machine_ir);
487 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
488
489 ASSERT_EQ(1u, bb1->insn_list().size());
490 ASSERT_EQ(3u, bb2->insn_list().size());
491 ASSERT_EQ(3u, bb3->insn_list().size());
492 }
493
TEST(MachineIR,GetInOneOfTheSuccessorsMakesPutLive)494 TEST(MachineIR, GetInOneOfTheSuccessorsMakesPutLive) {
495 Arena arena;
496 x86_64::MachineIR machine_ir(&arena);
497
498 auto* bb1 = machine_ir.NewBasicBlock();
499 auto* bb2 = machine_ir.NewBasicBlock();
500 auto* bb3 = machine_ir.NewBasicBlock();
501 machine_ir.AddEdge(bb1, bb2);
502 machine_ir.AddEdge(bb1, bb3);
503 x86_64::MachineIRBuilder builder(&machine_ir);
504
505 auto vreg = machine_ir.AllocVReg();
506 builder.StartBasicBlock(bb1);
507 builder.GenPut(GetThreadStateRegOffset(0), vreg);
508 builder.Gen<PseudoBranch>(bb2);
509
510 builder.StartBasicBlock(bb2);
511 builder.GenGet(vreg, GetThreadStateRegOffset(0));
512 builder.GenPut(GetThreadStateRegOffset(0), vreg);
513 builder.Gen<PseudoJump>(kNullGuestAddr);
514
515 builder.StartBasicBlock(bb3);
516 builder.GenPut(GetThreadStateRegOffset(0), vreg);
517 builder.Gen<PseudoJump>(kNullGuestAddr);
518
519 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
520 x86_64::RemoveRedundantPut(&machine_ir);
521 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
522
523 ASSERT_EQ(2u, bb1->insn_list().size());
524 ASSERT_EQ(3u, bb2->insn_list().size());
525 ASSERT_EQ(2u, bb3->insn_list().size());
526 }
527
TEST(MachineIR,ForwardingPseudoBranch)528 TEST(MachineIR, ForwardingPseudoBranch) {
529 // We create:
530 //
531 // BB0 -> BB1
532 // BB1 (forwarder)
533 // BB2
534 //
535 // We verify that the jump to BB1 is redirected to BB2.
536
537 Arena arena;
538 x86_64::MachineIR machine_ir(&arena);
539 x86_64::MachineIRBuilder builder(&machine_ir);
540
541 auto* bb0 = machine_ir.NewBasicBlock();
542 auto* bb1 = machine_ir.NewBasicBlock();
543 auto* bb2 = machine_ir.NewBasicBlock();
544 machine_ir.AddEdge(bb0, bb1);
545 machine_ir.AddEdge(bb1, bb2);
546
547 builder.StartBasicBlock(bb0);
548 builder.Gen<x86_64::MovlRegImm>(x86_64::kMachineRegRAX, 23);
549 builder.Gen<PseudoBranch>(bb1);
550
551 // Create a forwarder block
552 builder.StartBasicBlock(bb1);
553 builder.Gen<PseudoBranch>(bb2);
554
555 builder.StartBasicBlock(bb2);
556 builder.Gen<PseudoJump>(kNullGuestAddr);
557
558 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
559 x86_64::RemoveForwarderBlocks(&machine_ir);
560 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
561
562 // Verify that we have exactly two basic blocks.
563 EXPECT_EQ(2u, machine_ir.bb_list().size());
564
565 auto bb_it = machine_ir.bb_list().begin();
566
567 // Verify that BB0 contains exactly two instructions.
568 EXPECT_EQ(bb0, *bb_it);
569 EXPECT_EQ(2u, bb0->insn_list().size());
570
571 // Verify that the last instruction is PseudoBranch that jumps
572 // to BB2.
573 MachineInsn* bb0_insn = bb0->insn_list().back();
574 EXPECT_EQ(kMachineOpPseudoBranch, bb0_insn->opcode());
575 PseudoBranch* bb0_branch_insn = static_cast<PseudoBranch*>(bb0_insn);
576 EXPECT_EQ(bb2, bb0_branch_insn->then_bb());
577
578 // Check for BB2. Note that RemoveForwarderBlocks deletes BB1.
579 EXPECT_EQ(bb2, *(++bb_it));
580 }
581
TEST(MachineIR,ForwardingPseudoCondBranchThen)582 TEST(MachineIR, ForwardingPseudoCondBranchThen) {
583 // We create:
584 //
585 // BB0 (cond jump)-> BB1 (then_bb) and BB3 (else_bb)
586 // BB1 (forwarder)
587 // BB2
588 // BB3
589 //
590 // We verify that the jump to BB1 is redirected to BB2.
591
592 Arena arena;
593 x86_64::MachineIR machine_ir(&arena);
594
595 auto* bb0 = machine_ir.NewBasicBlock();
596 auto* bb1 = machine_ir.NewBasicBlock();
597 auto* bb2 = machine_ir.NewBasicBlock();
598 auto* bb3 = machine_ir.NewBasicBlock();
599
600 machine_ir.AddEdge(bb0, bb1);
601 machine_ir.AddEdge(bb0, bb3);
602 machine_ir.AddEdge(bb1, bb2);
603 machine_ir.AddEdge(bb2, bb3);
604
605 x86_64::MachineIRBuilder builder(&machine_ir);
606 builder.StartBasicBlock(bb0);
607 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb1, bb3, x86_64::kMachineRegFLAGS);
608
609 // Create a forwarder block
610 builder.StartBasicBlock(bb1);
611 builder.Gen<PseudoBranch>(bb2);
612
613 builder.StartBasicBlock(bb2);
614 builder.Gen<x86_64::MovlRegImm>(x86_64::kMachineRegRAX, 23);
615 builder.Gen<PseudoBranch>(bb3);
616
617 builder.StartBasicBlock(bb3);
618 builder.Gen<PseudoJump>(kNullGuestAddr);
619
620 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
621 x86_64::RemoveForwarderBlocks(&machine_ir);
622 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
623
624 // Verify that we have exactly three basic blocks.
625 EXPECT_EQ(3u, machine_ir.bb_list().size());
626
627 auto bb_it = machine_ir.bb_list().begin();
628
629 // Verify that BB0 contains exactly one instruction.
630 EXPECT_EQ(bb0, *bb_it);
631 EXPECT_EQ(1u, bb0->insn_list().size());
632
633 // Verify that the sole instruction is PseudoCondBranch that jumps
634 // to BB2 (then_bb) and BB3 (else_bb).
635 MachineInsn* bb0_insn = bb0->insn_list().front();
636 EXPECT_EQ(kMachineOpPseudoCondBranch, bb0_insn->opcode());
637 PseudoCondBranch* bb0_branch_insn = static_cast<PseudoCondBranch*>(bb0_insn);
638 EXPECT_EQ(bb2, bb0_branch_insn->then_bb());
639 EXPECT_EQ(bb3, bb0_branch_insn->else_bb());
640
641 // Check for BB2. Note that RemoveForwarderBlocks deletes BB1.
642 EXPECT_EQ(bb2, *(++bb_it));
643
644 // Check for BB3.
645 EXPECT_EQ(bb3, *(++bb_it));
646 }
647
TEST(MachineIR,ForwardingPseudoCondBranchElse)648 TEST(MachineIR, ForwardingPseudoCondBranchElse) {
649 // We create:
650 //
651 // BB0 (cond jump)-> BB1 (then_bb) and BB2 (else_bb)
652 // BB1
653 // BB2 (forwarder)
654 // BB3
655 //
656 // We verify that the jump to BB2 is redirected to BB3.
657
658 Arena arena;
659 x86_64::MachineIR machine_ir(&arena);
660 x86_64::MachineIRBuilder builder(&machine_ir);
661
662 auto* bb0 = machine_ir.NewBasicBlock();
663 auto* bb1 = machine_ir.NewBasicBlock();
664 auto* bb2 = machine_ir.NewBasicBlock();
665 auto* bb3 = machine_ir.NewBasicBlock();
666
667 machine_ir.AddEdge(bb0, bb1);
668 machine_ir.AddEdge(bb0, bb2);
669 machine_ir.AddEdge(bb2, bb3);
670
671 builder.StartBasicBlock(bb0);
672 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb1, bb2, x86_64::kMachineRegFLAGS);
673
674 builder.StartBasicBlock(bb1);
675 builder.Gen<x86_64::MovlRegImm>(x86_64::kMachineRegRAX, 23);
676 builder.Gen<PseudoJump>(kNullGuestAddr);
677
678 // Create a forwarder block
679 builder.StartBasicBlock(bb2);
680 builder.Gen<PseudoBranch>(bb3);
681
682 builder.StartBasicBlock(bb3);
683 builder.Gen<PseudoJump>(kNullGuestAddr);
684
685 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
686 x86_64::RemoveForwarderBlocks(&machine_ir);
687 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
688
689 // Verify that we have exactly three basic blocks.
690 EXPECT_EQ(3u, machine_ir.bb_list().size());
691
692 auto bb_it = machine_ir.bb_list().begin();
693
694 // Verify that BB0 contains exactly one instruction.
695 EXPECT_EQ(bb0, *bb_it);
696 EXPECT_EQ(1u, bb0->insn_list().size());
697
698 // Verify that the sole instruction is PseudoCondBranch that jumps
699 // to BB1 (then_bb) and BB3 (else_bb).
700 MachineInsn* bb0_insn = bb0->insn_list().front();
701 EXPECT_EQ(kMachineOpPseudoCondBranch, bb0_insn->opcode());
702 PseudoCondBranch* bb0_branch_insn = static_cast<PseudoCondBranch*>(bb0_insn);
703 EXPECT_EQ(bb1, bb0_branch_insn->then_bb());
704 EXPECT_EQ(bb3, bb0_branch_insn->else_bb());
705
706 // Check for BB1.
707 EXPECT_EQ(bb1, *(++bb_it));
708
709 // Check for BB3. Note that RemoveForwarderBlocks deletes BB2.
710 EXPECT_EQ(bb3, *(++bb_it));
711 }
712
TEST(MachineIR,EntryForwarderIsNotRemoved)713 TEST(MachineIR, EntryForwarderIsNotRemoved) {
714 // BB0 (entry forwarder) -> BB2
715 // BB1
716 // BB2
717
718 Arena arena;
719 x86_64::MachineIR machine_ir(&arena);
720 x86_64::MachineIRBuilder builder(&machine_ir);
721
722 auto* bb0 = machine_ir.NewBasicBlock();
723 auto* bb1 = machine_ir.NewBasicBlock();
724 auto* bb2 = machine_ir.NewBasicBlock();
725
726 machine_ir.AddEdge(bb0, bb2);
727 machine_ir.AddEdge(bb1, bb2);
728
729 builder.StartBasicBlock(bb0);
730 builder.Gen<PseudoBranch>(bb2);
731
732 // Create a forwarder block
733 builder.StartBasicBlock(bb1);
734 builder.Gen<x86_64::MovlRegImm>(x86_64::kMachineRegRAX, 29);
735 builder.Gen<PseudoBranch>(bb2);
736
737 builder.StartBasicBlock(bb2);
738 builder.Gen<PseudoJump>(kNullGuestAddr);
739
740 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
741 x86_64::RemoveForwarderBlocks(&machine_ir);
742 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
743
744 // Verify that we still have exactly three basic blocks.
745 EXPECT_EQ(3u, machine_ir.bb_list().size());
746
747 auto bb_it = machine_ir.bb_list().begin();
748
749 // Check for BB0.
750 EXPECT_EQ(bb0, *bb_it);
751
752 // Check for BB1.
753 EXPECT_EQ(bb1, *(++bb_it));
754
755 // Check for BB2.
756 EXPECT_EQ(bb2, *(++bb_it));
757 }
758
TEST(MachineIR,SelfForwarderIsNotRemoved)759 TEST(MachineIR, SelfForwarderIsNotRemoved) {
760 // We add entry block BB0 so that BB1 is skipped because it's self-forwarding,
761 // and not because it's the entry block
762 //
763 // BB0
764 // BB1 -> BB1 (self-forwarder)
765
766 Arena arena;
767 x86_64::MachineIR machine_ir(&arena);
768 x86_64::MachineIRBuilder builder(&machine_ir);
769
770 auto* bb0 = machine_ir.NewBasicBlock();
771 auto* bb1 = machine_ir.NewBasicBlock();
772
773 machine_ir.AddEdge(bb0, bb1);
774 machine_ir.AddEdge(bb1, bb1);
775
776 builder.StartBasicBlock(bb0);
777 builder.Gen<PseudoBranch>(bb1);
778
779 builder.StartBasicBlock(bb1);
780 builder.Gen<PseudoBranch>(bb1);
781
782 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
783 x86_64::RemoveForwarderBlocks(&machine_ir);
784 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
785
786 EXPECT_EQ(machine_ir.bb_list().size(), 2u);
787
788 auto bb_it = machine_ir.bb_list().begin();
789
790 // Check for BB0.
791 EXPECT_EQ(bb0, *bb_it);
792
793 // Check for BB1.
794 EXPECT_EQ(bb1, *(++bb_it));
795 }
796
TEST(MachineIR,ForwarderLoopIsNotRemoved)797 TEST(MachineIR, ForwarderLoopIsNotRemoved) {
798 // We add entry block BB0 so that entry exception doesn't apply to loop nodes.
799 //
800 // BB0
801 // BB1 (forwarder)
802 // BB2 -> BB1 (forwarder)
803 //
804 // After BB1 is removed, BB2 becomes self-forwarder and should not be removed.
805
806 Arena arena;
807 x86_64::MachineIR machine_ir(&arena);
808 x86_64::MachineIRBuilder builder(&machine_ir);
809
810 auto* bb0 = machine_ir.NewBasicBlock();
811 auto* bb1 = machine_ir.NewBasicBlock();
812 auto* bb2 = machine_ir.NewBasicBlock();
813
814 machine_ir.AddEdge(bb0, bb1);
815 machine_ir.AddEdge(bb1, bb2);
816 machine_ir.AddEdge(bb2, bb1);
817
818 builder.StartBasicBlock(bb0);
819 builder.Gen<PseudoBranch>(bb1);
820
821 builder.StartBasicBlock(bb1);
822 builder.Gen<PseudoBranch>(bb2);
823
824 builder.StartBasicBlock(bb2);
825 builder.Gen<PseudoBranch>(bb1);
826
827 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
828 x86_64::RemoveForwarderBlocks(&machine_ir);
829 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
830
831 EXPECT_EQ(machine_ir.bb_list().size(), 2u);
832
833 auto bb_it = machine_ir.bb_list().begin();
834
835 EXPECT_EQ(bb0, *bb_it);
836 EXPECT_EQ(bb2, *(++bb_it));
837 }
838
TEST(MachineIR,RemoveConsecutiveForwarderBlocks)839 TEST(MachineIR, RemoveConsecutiveForwarderBlocks) {
840 // We create:
841 //
842 // BB0 (cond jump)-> BB3
843 // BB1
844 // BB2 (forwarder)
845 // BB3 (forwarder)
846 // BB4
847 // BB5
848 //
849 // Tested cases:
850 // 1) regular -> forwarder -> forwarder
851 // 2) cond else -> forwarder -> regular
852 //
853 // Not tested: cond then -> forwarder, loops, forwarder is the first bb in list
854 //
855 // Attention: forwarder loops are not allowed
856
857 Arena arena;
858 x86_64::MachineIR machine_ir(&arena);
859 x86_64::MachineIRBuilder builder(&machine_ir);
860
861 auto* bb0 = machine_ir.NewBasicBlock();
862 auto* bb1 = machine_ir.NewBasicBlock();
863 auto* bb2 = machine_ir.NewBasicBlock();
864 auto* bb3 = machine_ir.NewBasicBlock();
865 auto* bb4 = machine_ir.NewBasicBlock();
866 auto* bb5 = machine_ir.NewBasicBlock();
867
868 machine_ir.AddEdge(bb0, bb1);
869 machine_ir.AddEdge(bb0, bb3);
870 machine_ir.AddEdge(bb1, bb2);
871 machine_ir.AddEdge(bb2, bb3);
872 machine_ir.AddEdge(bb3, bb4);
873 machine_ir.AddEdge(bb4, bb5);
874
875 builder.StartBasicBlock(bb0);
876 builder.Gen<PseudoCondBranch>(CodeEmitter::Condition::kZero, bb1, bb3, x86_64::kMachineRegFLAGS);
877
878 builder.StartBasicBlock(bb1);
879 builder.Gen<x86_64::MovlRegImm>(x86_64::kMachineRegRAX, 23);
880 builder.Gen<PseudoBranch>(bb2);
881
882 // Create a forwarder block.
883 builder.StartBasicBlock(bb2);
884 builder.Gen<PseudoCopy>(x86_64::kMachineRegRAX, x86_64::kMachineRegRAX, 4);
885 builder.Gen<PseudoCopy>(x86_64::kMachineRegRBX, x86_64::kMachineRegRBX, 4);
886 builder.Gen<PseudoBranch>(bb3);
887
888 // Create another forwarder block.
889 builder.StartBasicBlock(bb3);
890 builder.Gen<PseudoBranch>(bb4);
891
892 builder.StartBasicBlock(bb4);
893 builder.Gen<x86_64::MovlRegImm>(x86_64::kMachineRegRBX, 7);
894 builder.Gen<PseudoBranch>(bb5);
895
896 builder.StartBasicBlock(bb5);
897 builder.Gen<PseudoJump>(kNullGuestAddr);
898
899 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
900 RemoveNopPseudoCopy(&machine_ir);
901 x86_64::RemoveForwarderBlocks(&machine_ir);
902 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
903
904 // Verify that we have exactly four basic blocks left after two
905 // forwarder blocks are removed.
906 //
907 // BB0 (cond jump)-> BB4 (target changed)
908 // BB1 (target changed)
909 // BB4
910 // BB5
911 EXPECT_EQ(4u, machine_ir.bb_list().size());
912
913 auto bb_it = machine_ir.bb_list().begin();
914
915 // Verify that BB0 jumps to BB1 (then_bb) and BB4 (else_bb).
916 EXPECT_EQ(bb0, *bb_it);
917 MachineInsn* bb0_last_insn = bb0->insn_list().back();
918 EXPECT_EQ(kMachineOpPseudoCondBranch, bb0_last_insn->opcode());
919 PseudoCondBranch* bb0_branch_insn = static_cast<PseudoCondBranch*>(bb0_last_insn);
920 EXPECT_EQ(bb1, bb0_branch_insn->then_bb());
921 EXPECT_EQ(bb4, bb0_branch_insn->else_bb());
922
923 // Verify that BB1 jumps to BB4.
924 EXPECT_EQ(bb1, *(++bb_it));
925 MachineInsn* bb1_last_insn = bb1->insn_list().back();
926 EXPECT_EQ(kMachineOpPseudoBranch, bb1_last_insn->opcode());
927 PseudoBranch* bb1_branch_insn = static_cast<PseudoBranch*>(bb1_last_insn);
928 EXPECT_EQ(bb4, bb1_branch_insn->then_bb());
929
930 // Check for BB4. Note that RemoveForwarderBlocks deletes BB2 and
931 // BB3.
932 EXPECT_EQ(bb4, *(++bb_it));
933
934 // Check for BB5.
935 EXPECT_EQ(bb5, *(++bb_it));
936 }
937
TEST(MachineIR,RemoveNopPseudoCopy)938 TEST(MachineIR, RemoveNopPseudoCopy) {
939 // Verify that RemoveNopPseudoCopy removes PseudoCopy instructions
940 // with identical source and destination operands while retaining
941 // all other instructions.
942
943 Arena arena;
944 x86_64::MachineIR machine_ir(&arena);
945 auto* bb0 = machine_ir.NewBasicBlock();
946 x86_64::MachineIRBuilder builder(&machine_ir);
947
948 builder.StartBasicBlock(bb0);
949 builder.Gen<PseudoCopy>(x86_64::kMachineRegRAX, x86_64::kMachineRegRAX, 4);
950 builder.Gen<PseudoCopy>(x86_64::kMachineRegRBX, x86_64::kMachineRegRCX, 4);
951 builder.Gen<PseudoJump>(kNullGuestAddr);
952
953 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
954 RemoveNopPseudoCopy(&machine_ir);
955 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
956
957 // Verify that we have exactly one basic block.
958 EXPECT_EQ(1u, machine_ir.bb_list().size());
959
960 // Verify that bb0 contains exactly two instructions.
961 EXPECT_EQ(bb0, machine_ir.bb_list().front());
962 EXPECT_EQ(2u, bb0->insn_list().size());
963
964 auto insn_it = bb0->insn_list().begin();
965
966 // Verify that the first instruction is PseudoCopy that copies ECX
967 // to EBX.
968 MachineInsn* insn0 = *insn_it;
969 EXPECT_EQ(kMachineOpPseudoCopy, insn0->opcode());
970 EXPECT_EQ(x86_64::kMachineRegRBX, insn0->RegAt(0));
971 EXPECT_EQ(x86_64::kMachineRegRCX, insn0->RegAt(1));
972
973 // Verify that the next instruction is PseudoJump.
974 MachineInsn* insn1 = *(++insn_it);
975 EXPECT_EQ(kMachineOpPseudoJump, insn1->opcode());
976 }
977
TEST(MachineIR,ReorderBasicBlocksInReversePostOrder)978 TEST(MachineIR, ReorderBasicBlocksInReversePostOrder) {
979 // |----|
980 // v |
981 // BB0 BB1 BB2
982 // | ^
983 // |---------|
984 Arena arena;
985 x86_64::MachineIR machine_ir(&arena);
986 x86_64::MachineIRBuilder builder(&machine_ir);
987
988 auto* bb0 = machine_ir.NewBasicBlock();
989 auto* bb1 = machine_ir.NewBasicBlock();
990 auto* bb2 = machine_ir.NewBasicBlock();
991
992 machine_ir.AddEdge(bb0, bb2);
993 machine_ir.AddEdge(bb2, bb1);
994
995 builder.StartBasicBlock(bb0);
996 builder.Gen<PseudoBranch>(bb2);
997
998 builder.StartBasicBlock(bb1);
999 builder.Gen<PseudoJump>(kNullGuestAddr);
1000
1001 builder.StartBasicBlock(bb2);
1002 builder.Gen<PseudoBranch>(bb1);
1003
1004 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
1005 x86_64::ReorderBasicBlocksInReversePostOrder(&machine_ir);
1006 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
1007
1008 EXPECT_EQ(3u, machine_ir.bb_list().size());
1009
1010 auto bb_it = machine_ir.bb_list().begin();
1011 EXPECT_EQ(bb0, *bb_it);
1012 EXPECT_EQ(bb2, *(++bb_it));
1013 EXPECT_EQ(bb1, *(++bb_it));
1014 }
1015
TEST(MachineIR,ReorderDiamondControlFlowInReversePostOrder)1016 TEST(MachineIR, ReorderDiamondControlFlowInReversePostOrder) {
1017 Arena arena;
1018 x86_64::MachineIR machine_ir(&arena);
1019
1020 auto [bb1, bb2, bb3, bb4] = BuildDiamondControlFlow(&machine_ir);
1021
1022 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
1023 x86_64::ReorderBasicBlocksInReversePostOrder(&machine_ir);
1024 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
1025
1026 EXPECT_EQ(4u, machine_ir.bb_list().size());
1027
1028 auto bb_it = machine_ir.bb_list().begin();
1029 auto* enter_bb = *bb_it++;
1030 auto* then_bb = *bb_it++;
1031 auto* else_bb = *bb_it++;
1032 auto* merge_bb = *bb_it++;
1033 EXPECT_EQ(enter_bb, bb1);
1034 // `Then` and `else` are not strictly ordered by RPO.
1035 if (then_bb == bb2) {
1036 EXPECT_EQ(else_bb, bb3);
1037 } else {
1038 EXPECT_EQ(then_bb, bb3);
1039 EXPECT_EQ(else_bb, bb2);
1040 }
1041 EXPECT_EQ(merge_bb, bb4);
1042 }
1043
TEST(MachineIR,ReorderControlFlowWithLoopInReversePostOrder)1044 TEST(MachineIR, ReorderControlFlowWithLoopInReversePostOrder) {
1045 Arena arena;
1046 x86_64::MachineIR machine_ir(&arena);
1047
1048 auto [bb1, bb2, bb3, bb4, unused_vreg] = BuildDataFlowAcrossEmptyLoop(&machine_ir);
1049
1050 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
1051 x86_64::ReorderBasicBlocksInReversePostOrder(&machine_ir);
1052 EXPECT_EQ(x86_64::CheckMachineIR(machine_ir), x86_64::kMachineIRCheckSuccess);
1053
1054 EXPECT_EQ(4u, machine_ir.bb_list().size());
1055
1056 auto bb_it = machine_ir.bb_list().begin();
1057 auto* enter_bb = *bb_it++;
1058 auto* loop_head_bb = *bb_it++;
1059 auto* then_bb = *bb_it++;
1060 auto* else_bb = *bb_it++;
1061 EXPECT_EQ(enter_bb, bb1);
1062 EXPECT_EQ(loop_head_bb, bb2);
1063 // `Then` and `else` are not strictly ordered by RPO.
1064 // Note that loop may be separated by the post loop code.
1065 if (then_bb == bb3) {
1066 EXPECT_EQ(else_bb, bb4);
1067 } else {
1068 EXPECT_EQ(then_bb, bb4);
1069 EXPECT_EQ(else_bb, bb3);
1070 }
1071 }
1072
1073 } // namespace
1074
1075 } // namespace berberis
1076