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/rename_vregs.h"
20
21 #include "berberis/backend/x86_64/machine_ir.h"
22 #include "berberis/backend/x86_64/machine_ir_builder.h"
23 #include "berberis/backend/x86_64/machine_ir_test_corpus.h"
24 #include "berberis/base/arena_alloc.h"
25 #include "berberis/guest_state/guest_addr.h"
26
27 namespace berberis {
28
29 namespace {
30
TEST(MachineRenameVRegsTest,AssignNewVRegsInSameBasicBlock)31 TEST(MachineRenameVRegsTest, AssignNewVRegsInSameBasicBlock) {
32 Arena arena;
33 x86_64::MachineIR machine_ir(&arena);
34
35 x86_64::MachineIRBuilder builder(&machine_ir);
36 MachineReg vreg = machine_ir.AllocVReg();
37
38 auto* bb = machine_ir.NewBasicBlock();
39
40 builder.StartBasicBlock(bb);
41 builder.Gen<x86_64::MovqRegImm>(vreg, 0);
42 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
43 builder.Gen<PseudoJump>(kNullGuestAddr);
44
45 x86_64::VRegMap vreg_map(&machine_ir);
46 vreg_map.AssignNewVRegs();
47
48 ASSERT_EQ(bb->insn_list().size(), 3U);
49 auto it = bb->insn_list().begin();
50 MachineReg new_vreg = (*it)->RegAt(0);
51 EXPECT_NE(vreg, new_vreg);
52 it++;
53 EXPECT_EQ(new_vreg, (*it)->RegAt(1));
54 // Hard regs remain unrenamed.
55 EXPECT_EQ(x86_64::kMachineRegRAX, (*it)->RegAt(0));
56 }
57
TEST(MachineRenameVRegsTest,AssignNewVRegsAcrossBasicBlocks)58 TEST(MachineRenameVRegsTest, AssignNewVRegsAcrossBasicBlocks) {
59 Arena arena;
60 x86_64::MachineIR machine_ir(&arena);
61
62 x86_64::MachineIRBuilder builder(&machine_ir);
63 MachineReg vreg = machine_ir.AllocVReg();
64
65 auto* bb1 = machine_ir.NewBasicBlock();
66 auto* bb2 = machine_ir.NewBasicBlock();
67
68 machine_ir.AddEdge(bb1, bb2);
69
70 builder.StartBasicBlock(bb1);
71 builder.Gen<x86_64::MovqRegImm>(vreg, 0);
72 builder.Gen<PseudoBranch>(bb2);
73
74 builder.StartBasicBlock(bb2);
75 builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
76 builder.Gen<PseudoJump>(kNullGuestAddr);
77
78 x86_64::VRegMap vreg_map(&machine_ir);
79 vreg_map.AssignNewVRegs();
80
81 ASSERT_EQ(bb1->insn_list().size(), 2U);
82 auto it = bb1->insn_list().begin();
83 MachineReg vreg_in_bb1 = (*it)->RegAt(0);
84 EXPECT_NE(vreg, vreg_in_bb1);
85
86 ASSERT_EQ(bb2->insn_list().size(), 2U);
87 it = bb2->insn_list().begin();
88 MachineReg vreg_in_bb2 = (*it)->RegAt(1);
89 EXPECT_NE(vreg, vreg_in_bb2);
90 EXPECT_NE(vreg_in_bb1, vreg_in_bb2);
91 // Hard regs remain unrenamed.
92 EXPECT_EQ(x86_64::kMachineRegRAX, (*it)->RegAt(0));
93 }
94
TEST(MachineRenameVRegsTest,DataFlowAcrossBasicBlocks)95 TEST(MachineRenameVRegsTest, DataFlowAcrossBasicBlocks) {
96 Arena arena;
97 x86_64::MachineIR machine_ir(&arena);
98
99 auto [bb1, bb2, bb3, vreg1, vreg2] = BuildDataFlowAcrossBasicBlocks(&machine_ir);
100
101 x86_64::RenameVRegs(&machine_ir);
102
103 // BB1:
104 // MOVQ bb1_v1, 0
105 // MOVQ bb1_v2, 0
106 // BRANCH BB2
107 ASSERT_EQ(bb1->insn_list().size(), 3U);
108 auto it = bb1->insn_list().begin();
109 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegImm);
110 MachineReg vreg1_in_bb1 = (*it)->RegAt(0);
111 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegImm);
112 it++;
113 MachineReg vreg2_in_bb1 = (*it)->RegAt(0);
114
115 // BB2:
116 // PSEUDO_COPY bb2_v1, bb1_v1
117 // PSEUDO_COPY bb2_v2, bb1_v2
118 // MOVQ RAX, bb2_v2
119 // BRANCH BB3
120 ASSERT_EQ(bb2->insn_list().size(), 4U);
121 MachineReg vreg1_in_bb2, vreg2_in_bb2;
122 it = bb2->insn_list().begin();
123 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
124 // Pseudo-moves order is not guaranteed. So consider both cases.
125 if ((*it)->RegAt(1) == vreg1_in_bb1) {
126 vreg1_in_bb2 = (*it)->RegAt(0);
127 it++;
128 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
129 EXPECT_EQ((*it)->RegAt(1), vreg2_in_bb1);
130 vreg2_in_bb2 = (*it)->RegAt(0);
131 } else {
132 EXPECT_EQ((*it)->RegAt(1), vreg2_in_bb1);
133
134 vreg2_in_bb2 = (*it)->RegAt(0);
135 it++;
136 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
137 EXPECT_EQ((*it)->RegAt(1), vreg1_in_bb1);
138 vreg1_in_bb2 = (*it)->RegAt(0);
139 }
140 it++;
141 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegReg);
142 EXPECT_EQ((*it)->RegAt(1), vreg2_in_bb2);
143
144 // BB3:
145 // PSEUDO_COPY bb3_v1, bb2_v1
146 // MOVQ RAX, bb3_v1
147 // JUMP
148 ASSERT_EQ(bb3->insn_list().size(), 3U);
149 it = bb3->insn_list().begin();
150 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
151 EXPECT_EQ((*it)->RegAt(1), vreg1_in_bb2);
152 MachineReg vreg1_in_bb3 = (*it)->RegAt(0);
153 it++;
154 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegReg);
155 EXPECT_EQ((*it)->RegAt(1), vreg1_in_bb3);
156 }
157
TEST(MachineRenameVRegsTest,DataFlowFromTwoPreds)158 TEST(MachineRenameVRegsTest, DataFlowFromTwoPreds) {
159 Arena arena;
160 x86_64::MachineIR machine_ir(&arena);
161
162 auto [bb1, bb2, bb3, vreg] = BuildDataFlowFromTwoPreds(&machine_ir);
163
164 x86_64::RenameVRegs(&machine_ir);
165
166 // BB1:
167 // MOVQ v1, 0
168 // PSEUDO_COPY v3, v1
169 // BRANCH BB3
170 ASSERT_EQ(bb1->insn_list().size(), 3U);
171 auto it = bb1->insn_list().begin();
172 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegImm);
173 auto vreg_in_bb1 = (*it)->RegAt(0);
174 it++;
175 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
176 EXPECT_EQ(vreg_in_bb1, (*it)->RegAt(1));
177 auto vreg_in_bb3 = (*it)->RegAt(0);
178
179 // BB2:
180 // MOVQ v2, 1
181 // PSEUDO_COPY v3, v2
182 // BRANCH BB3
183 ASSERT_EQ(bb2->insn_list().size(), 3U);
184 it = bb2->insn_list().begin();
185 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegImm);
186 auto vreg_in_bb2 = (*it)->RegAt(0);
187 it++;
188 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
189 EXPECT_EQ(vreg_in_bb2, (*it)->RegAt(1));
190 EXPECT_EQ(vreg_in_bb3, (*it)->RegAt(0));
191
192 // BB3:
193 // MOVQ RAX, v3
194 // JUMP
195 ASSERT_EQ(bb3->insn_list().size(), 2U);
196 it = bb3->insn_list().begin();
197 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegReg);
198 EXPECT_EQ(vreg_in_bb3, (*it)->RegAt(1));
199 }
200
TEST(MachineRenameVRegsTest,DataFlowToTwoSuccs)201 TEST(MachineRenameVRegsTest, DataFlowToTwoSuccs) {
202 Arena arena;
203 x86_64::MachineIR machine_ir(&arena);
204
205 auto [bb1, bb2, bb3, vreg] = BuildDataFlowToTwoSuccs(&machine_ir);
206
207 x86_64::RenameVRegs(&machine_ir);
208
209 // BB1:
210 // MOVQ v1, 0
211 // COND_BRANCH Z, BB2, BB3
212 ASSERT_EQ(bb1->insn_list().size(), 2U);
213 auto it = bb1->insn_list().begin();
214 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegImm);
215 auto vreg_in_bb1 = (*it)->RegAt(0);
216
217 // BB2:
218 // PSEUDO_COPY v2, v1
219 // MOVQ RAX, v2
220 // JUMP
221 ASSERT_EQ(bb2->insn_list().size(), 3U);
222 it = bb2->insn_list().begin();
223 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
224 EXPECT_EQ(vreg_in_bb1, (*it)->RegAt(1));
225 auto vreg_in_bb2 = (*it)->RegAt(0);
226 it++;
227 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegReg);
228 EXPECT_EQ(vreg_in_bb2, (*it)->RegAt(1));
229
230 // BB3:
231 // PSEUDO_COPY v3, v1
232 // MOVQ RAX, v3
233 // JUMP
234 ASSERT_EQ(bb3->insn_list().size(), 3U);
235 it = bb3->insn_list().begin();
236 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
237 EXPECT_EQ(vreg_in_bb1, (*it)->RegAt(1));
238 auto vreg_in_bb3 = (*it)->RegAt(0);
239 it++;
240 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegReg);
241 EXPECT_EQ(vreg_in_bb3, (*it)->RegAt(1));
242 }
243
TEST(MachineRenameVRegsTest,DataFlowAcrossEmptyLoop)244 TEST(MachineRenameVRegsTest, DataFlowAcrossEmptyLoop) {
245 Arena arena;
246 x86_64::MachineIR machine_ir(&arena);
247
248 auto [bb1, bb2, bb3, bb4, vreg] = BuildDataFlowAcrossEmptyLoop(&machine_ir);
249
250 x86_64::RenameVRegs(&machine_ir);
251
252 // BB1:
253 // MOVQ v1, 0
254 // PSEUDO_COPY v2, v1
255 // BRANCH BB2
256 ASSERT_EQ(bb1->insn_list().size(), 3U);
257 auto it = bb1->insn_list().begin();
258 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegImm);
259 auto vreg_in_bb1 = (*it)->RegAt(0);
260 it++;
261 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
262 EXPECT_EQ(vreg_in_bb1, (*it)->RegAt(1));
263 auto vreg_in_bb2 = (*it)->RegAt(0);
264
265 // BB2:
266 // COND_BRANCH Z, BB3, BB4
267 ASSERT_EQ(bb2->insn_list().size(), 1U);
268
269 // BB3:
270 // PSEUDO_COPY v3, v2
271 // PSEUDO_COPY v2, v3
272 // BRAND BB2
273 ASSERT_EQ(bb4->insn_list().size(), 3U);
274 it = bb3->insn_list().begin();
275 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
276 EXPECT_EQ(vreg_in_bb2, (*it)->RegAt(1));
277 auto vreg_in_bb3 = (*it)->RegAt(0);
278 it++;
279 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
280 EXPECT_EQ(vreg_in_bb3, (*it)->RegAt(1));
281 EXPECT_EQ(vreg_in_bb2, (*it)->RegAt(0));
282
283 // BB4:
284 // PSEUDO_COPY v4, v2
285 // MOVQ RAX, v4
286 // JUMP
287 ASSERT_EQ(bb4->insn_list().size(), 3U);
288 it = bb4->insn_list().begin();
289 EXPECT_EQ((*it)->opcode(), kMachineOpPseudoCopy);
290 EXPECT_EQ(vreg_in_bb2, (*it)->RegAt(1));
291 auto vreg_in_bb4 = (*it)->RegAt(0);
292 it++;
293 EXPECT_EQ((*it)->opcode(), kMachineOpMovqRegReg);
294 EXPECT_EQ(vreg_in_bb4, (*it)->RegAt(1));
295 }
296
297 } // namespace
298
299 } // namespace berberis
300