1 /*
2 * Copyright (C) 2014 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 "builder.h"
18 #include "code_generator.h"
19 #include "dex_file.h"
20 #include "dex_instruction.h"
21 #include "nodes.h"
22 #include "optimizing_unit_test.h"
23 #include "register_allocator.h"
24 #include "ssa_liveness_analysis.h"
25 #include "utils/arena_allocator.h"
26
27 #include "gtest/gtest.h"
28
29 namespace art {
30
31 // Note: the register allocator tests rely on the fact that constants have live
32 // intervals and registers get allocated to them.
33
Check(const uint16_t * data)34 static bool Check(const uint16_t* data) {
35 ArenaPool pool;
36 ArenaAllocator allocator(&pool);
37 HGraphBuilder builder(&allocator);
38 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
39 HGraph* graph = builder.BuildGraph(*item);
40 graph->BuildDominatorTree();
41 graph->TransformToSSA();
42 graph->FindNaturalLoops();
43 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
44 SsaLivenessAnalysis liveness(*graph, codegen);
45 liveness.Analyze();
46 RegisterAllocator register_allocator(&allocator, codegen, liveness);
47 register_allocator.AllocateRegisters();
48 return register_allocator.Validate(false);
49 }
50
51 /**
52 * Unit testing of RegisterAllocator::ValidateIntervals. Register allocator
53 * tests are based on this validation method.
54 */
TEST(RegisterAllocatorTest,ValidateIntervals)55 TEST(RegisterAllocatorTest, ValidateIntervals) {
56 ArenaPool pool;
57 ArenaAllocator allocator(&pool);
58 HGraph* graph = new (&allocator) HGraph(&allocator);
59 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
60 GrowableArray<LiveInterval*> intervals(&allocator, 0);
61
62 // Test with two intervals of the same range.
63 {
64 static constexpr size_t ranges[][2] = {{0, 42}};
65 intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 0));
66 intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 1));
67 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
68 intervals, 0, *codegen, &allocator, true, false));
69
70 intervals.Get(1)->SetRegister(0);
71 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
72 intervals, 0, *codegen, &allocator, true, false));
73 intervals.Reset();
74 }
75
76 // Test with two non-intersecting intervals.
77 {
78 static constexpr size_t ranges1[][2] = {{0, 42}};
79 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
80 static constexpr size_t ranges2[][2] = {{42, 43}};
81 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
82 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
83 intervals, 0, *codegen, &allocator, true, false));
84
85 intervals.Get(1)->SetRegister(0);
86 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
87 intervals, 0, *codegen, &allocator, true, false));
88 intervals.Reset();
89 }
90
91 // Test with two non-intersecting intervals, with one with a lifetime hole.
92 {
93 static constexpr size_t ranges1[][2] = {{0, 42}, {45, 48}};
94 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
95 static constexpr size_t ranges2[][2] = {{42, 43}};
96 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
97 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
98 intervals, 0, *codegen, &allocator, true, false));
99
100 intervals.Get(1)->SetRegister(0);
101 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
102 intervals, 0, *codegen, &allocator, true, false));
103 intervals.Reset();
104 }
105
106 // Test with intersecting intervals.
107 {
108 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}};
109 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
110 static constexpr size_t ranges2[][2] = {{42, 47}};
111 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
112 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
113 intervals, 0, *codegen, &allocator, true, false));
114
115 intervals.Get(1)->SetRegister(0);
116 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
117 intervals, 0, *codegen, &allocator, true, false));
118 intervals.Reset();
119 }
120
121 // Test with siblings.
122 {
123 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}};
124 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
125 intervals.Get(0)->SplitAt(43);
126 static constexpr size_t ranges2[][2] = {{42, 47}};
127 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
128 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
129 intervals, 0, *codegen, &allocator, true, false));
130
131 intervals.Get(1)->SetRegister(0);
132 // Sibling of the first interval has no register allocated to it.
133 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
134 intervals, 0, *codegen, &allocator, true, false));
135
136 intervals.Get(0)->GetNextSibling()->SetRegister(0);
137 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
138 intervals, 0, *codegen, &allocator, true, false));
139 }
140 }
141
TEST(RegisterAllocatorTest,CFG1)142 TEST(RegisterAllocatorTest, CFG1) {
143 /*
144 * Test the following snippet:
145 * return 0;
146 *
147 * Which becomes the following graph:
148 * constant0
149 * goto
150 * |
151 * return
152 * |
153 * exit
154 */
155 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
156 Instruction::CONST_4 | 0 | 0,
157 Instruction::RETURN);
158
159 ASSERT_TRUE(Check(data));
160 }
161
TEST(RegisterAllocatorTest,Loop1)162 TEST(RegisterAllocatorTest, Loop1) {
163 /*
164 * Test the following snippet:
165 * int a = 0;
166 * while (a == a) {
167 * a = 4;
168 * }
169 * return 5;
170 *
171 * Which becomes the following graph:
172 * constant0
173 * constant4
174 * constant5
175 * goto
176 * |
177 * goto
178 * |
179 * phi
180 * equal
181 * if +++++
182 * | \ +
183 * | goto
184 * |
185 * return
186 * |
187 * exit
188 */
189
190 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
191 Instruction::CONST_4 | 0 | 0,
192 Instruction::IF_EQ, 4,
193 Instruction::CONST_4 | 4 << 12 | 0,
194 Instruction::GOTO | 0xFD00,
195 Instruction::CONST_4 | 5 << 12 | 1 << 8,
196 Instruction::RETURN | 1 << 8);
197
198 ASSERT_TRUE(Check(data));
199 }
200
TEST(RegisterAllocatorTest,Loop2)201 TEST(RegisterAllocatorTest, Loop2) {
202 /*
203 * Test the following snippet:
204 * int a = 0;
205 * while (a == 8) {
206 * a = 4 + 5;
207 * }
208 * return 6 + 7;
209 *
210 * Which becomes the following graph:
211 * constant0
212 * constant4
213 * constant5
214 * constant6
215 * constant7
216 * constant8
217 * goto
218 * |
219 * goto
220 * |
221 * phi
222 * equal
223 * if +++++
224 * | \ +
225 * | 4 + 5
226 * | goto
227 * |
228 * 6 + 7
229 * return
230 * |
231 * exit
232 */
233
234 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
235 Instruction::CONST_4 | 0 | 0,
236 Instruction::CONST_4 | 8 << 12 | 1 << 8,
237 Instruction::IF_EQ | 1 << 8, 7,
238 Instruction::CONST_4 | 4 << 12 | 0 << 8,
239 Instruction::CONST_4 | 5 << 12 | 1 << 8,
240 Instruction::ADD_INT, 1 << 8 | 0,
241 Instruction::GOTO | 0xFA00,
242 Instruction::CONST_4 | 6 << 12 | 1 << 8,
243 Instruction::CONST_4 | 7 << 12 | 1 << 8,
244 Instruction::ADD_INT, 1 << 8 | 0,
245 Instruction::RETURN | 1 << 8);
246
247 ASSERT_TRUE(Check(data));
248 }
249
BuildSSAGraph(const uint16_t * data,ArenaAllocator * allocator)250 static HGraph* BuildSSAGraph(const uint16_t* data, ArenaAllocator* allocator) {
251 HGraphBuilder builder(allocator);
252 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
253 HGraph* graph = builder.BuildGraph(*item);
254 graph->BuildDominatorTree();
255 graph->TransformToSSA();
256 graph->FindNaturalLoops();
257 return graph;
258 }
259
TEST(RegisterAllocatorTest,Loop3)260 TEST(RegisterAllocatorTest, Loop3) {
261 /*
262 * Test the following snippet:
263 * int a = 0
264 * do {
265 * b = a;
266 * a++;
267 * } while (a != 5)
268 * return b;
269 *
270 * Which becomes the following graph:
271 * constant0
272 * constant1
273 * constant5
274 * goto
275 * |
276 * goto
277 * |++++++++++++
278 * phi +
279 * a++ +
280 * equals +
281 * if +
282 * |++++++++++++
283 * return
284 * |
285 * exit
286 */
287
288 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
289 Instruction::CONST_4 | 0 | 0,
290 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8,
291 Instruction::CONST_4 | 5 << 12 | 2 << 8,
292 Instruction::IF_NE | 1 << 8 | 2 << 12, 3,
293 Instruction::RETURN | 0 << 8,
294 Instruction::MOVE | 1 << 12 | 0 << 8,
295 Instruction::GOTO | 0xF900);
296
297 ArenaPool pool;
298 ArenaAllocator allocator(&pool);
299 HGraph* graph = BuildSSAGraph(data, &allocator);
300 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
301 SsaLivenessAnalysis liveness(*graph, codegen);
302 liveness.Analyze();
303 RegisterAllocator register_allocator(&allocator, codegen, liveness);
304 register_allocator.AllocateRegisters();
305 ASSERT_TRUE(register_allocator.Validate(false));
306
307 HBasicBlock* loop_header = graph->GetBlocks().Get(2);
308 HPhi* phi = loop_header->GetFirstPhi()->AsPhi();
309
310 LiveInterval* phi_interval = phi->GetLiveInterval();
311 LiveInterval* loop_update = phi->InputAt(1)->GetLiveInterval();
312 ASSERT_TRUE(phi_interval->HasRegister());
313 ASSERT_TRUE(loop_update->HasRegister());
314 ASSERT_NE(phi_interval->GetRegister(), loop_update->GetRegister());
315
316 HBasicBlock* return_block = graph->GetBlocks().Get(3);
317 HReturn* ret = return_block->GetLastInstruction()->AsReturn();
318 ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
319 }
320
TEST(RegisterAllocatorTest,FirstRegisterUse)321 TEST(RegisterAllocatorTest, FirstRegisterUse) {
322 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
323 Instruction::CONST_4 | 0 | 0,
324 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8,
325 Instruction::ADD_INT_LIT8 | 0 << 8, 1 << 8,
326 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8 | 1,
327 Instruction::RETURN_VOID);
328
329 ArenaPool pool;
330 ArenaAllocator allocator(&pool);
331 HGraph* graph = BuildSSAGraph(data, &allocator);
332 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kArm);
333 SsaLivenessAnalysis liveness(*graph, codegen);
334 liveness.Analyze();
335
336 HAdd* first_add = graph->GetBlocks().Get(1)->GetFirstInstruction()->AsAdd();
337 HAdd* last_add = graph->GetBlocks().Get(1)->GetLastInstruction()->GetPrevious()->AsAdd();
338 ASSERT_EQ(last_add->InputAt(0), first_add);
339 LiveInterval* interval = first_add->GetLiveInterval();
340 ASSERT_EQ(interval->GetEnd(), last_add->GetLifetimePosition() + 1);
341 ASSERT_TRUE(interval->GetNextSibling() == nullptr);
342
343 // We need a register for the output of the instruction.
344 ASSERT_EQ(interval->FirstRegisterUse(), first_add->GetLifetimePosition());
345
346 // Split at the next instruction.
347 interval = interval->SplitAt(first_add->GetLifetimePosition() + 2);
348 // The user of the split is the last add.
349 ASSERT_EQ(interval->FirstRegisterUse(), last_add->GetLifetimePosition() + 1);
350
351 // Split before the last add.
352 LiveInterval* new_interval = interval->SplitAt(last_add->GetLifetimePosition() - 1);
353 // Ensure the current interval has no register use...
354 ASSERT_EQ(interval->FirstRegisterUse(), kNoLifetime);
355 // And the new interval has it for the last add.
356 ASSERT_EQ(new_interval->FirstRegisterUse(), last_add->GetLifetimePosition() + 1);
357 }
358
359 } // namespace art
360