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 "arch/x86/instruction_set_features_x86.h"
18 #include "base/arena_allocator.h"
19 #include "builder.h"
20 #include "code_generator.h"
21 #include "code_generator_x86.h"
22 #include "dex_file.h"
23 #include "dex_file_types.h"
24 #include "dex_instruction.h"
25 #include "driver/compiler_options.h"
26 #include "nodes.h"
27 #include "optimizing_unit_test.h"
28 #include "register_allocator.h"
29 #include "register_allocator_linear_scan.h"
30 #include "ssa_liveness_analysis.h"
31 #include "ssa_phi_elimination.h"
32
33 namespace art {
34
35 using Strategy = RegisterAllocator::Strategy;
36
37 // Note: the register allocator tests rely on the fact that constants have live
38 // intervals and registers get allocated to them.
39
40 class RegisterAllocatorTest : public CommonCompilerTest {
41 protected:
42 // These functions need to access private variables of LocationSummary, so we declare it
43 // as a member of RegisterAllocatorTest, which we make a friend class.
44 static void SameAsFirstInputHint(Strategy strategy);
45 static void ExpectedInRegisterHint(Strategy strategy);
46 };
47
48 // This macro should include all register allocation strategies that should be tested.
49 #define TEST_ALL_STRATEGIES(test_name)\
50 TEST_F(RegisterAllocatorTest, test_name##_LinearScan) {\
51 test_name(Strategy::kRegisterAllocatorLinearScan);\
52 }\
53 TEST_F(RegisterAllocatorTest, test_name##_GraphColor) {\
54 test_name(Strategy::kRegisterAllocatorGraphColor);\
55 }
56
Check(const uint16_t * data,Strategy strategy)57 static bool Check(const uint16_t* data, Strategy strategy) {
58 ArenaPool pool;
59 ArenaAllocator allocator(&pool);
60 HGraph* graph = CreateCFG(&allocator, data);
61 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
62 X86InstructionSetFeatures::FromCppDefines());
63 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
64 SsaLivenessAnalysis liveness(graph, &codegen);
65 liveness.Analyze();
66 RegisterAllocator* register_allocator =
67 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
68 register_allocator->AllocateRegisters();
69 return register_allocator->Validate(false);
70 }
71
72 /**
73 * Unit testing of RegisterAllocator::ValidateIntervals. Register allocator
74 * tests are based on this validation method.
75 */
TEST_F(RegisterAllocatorTest,ValidateIntervals)76 TEST_F(RegisterAllocatorTest, ValidateIntervals) {
77 ArenaPool pool;
78 ArenaAllocator allocator(&pool);
79 HGraph* graph = CreateGraph(&allocator);
80 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
81 X86InstructionSetFeatures::FromCppDefines());
82 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
83 ArenaVector<LiveInterval*> intervals(allocator.Adapter());
84
85 // Test with two intervals of the same range.
86 {
87 static constexpr size_t ranges[][2] = {{0, 42}};
88 intervals.push_back(BuildInterval(ranges, arraysize(ranges), &allocator, 0));
89 intervals.push_back(BuildInterval(ranges, arraysize(ranges), &allocator, 1));
90 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
91 intervals, 0, 0, codegen, &allocator, true, false));
92
93 intervals[1]->SetRegister(0);
94 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
95 intervals, 0, 0, codegen, &allocator, true, false));
96 intervals.clear();
97 }
98
99 // Test with two non-intersecting intervals.
100 {
101 static constexpr size_t ranges1[][2] = {{0, 42}};
102 intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
103 static constexpr size_t ranges2[][2] = {{42, 43}};
104 intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
105 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
106 intervals, 0, 0, codegen, &allocator, true, false));
107
108 intervals[1]->SetRegister(0);
109 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
110 intervals, 0, 0, codegen, &allocator, true, false));
111 intervals.clear();
112 }
113
114 // Test with two non-intersecting intervals, with one with a lifetime hole.
115 {
116 static constexpr size_t ranges1[][2] = {{0, 42}, {45, 48}};
117 intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
118 static constexpr size_t ranges2[][2] = {{42, 43}};
119 intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
120 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
121 intervals, 0, 0, codegen, &allocator, true, false));
122
123 intervals[1]->SetRegister(0);
124 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
125 intervals, 0, 0, codegen, &allocator, true, false));
126 intervals.clear();
127 }
128
129 // Test with intersecting intervals.
130 {
131 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}};
132 intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
133 static constexpr size_t ranges2[][2] = {{42, 47}};
134 intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
135 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
136 intervals, 0, 0, codegen, &allocator, true, false));
137
138 intervals[1]->SetRegister(0);
139 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
140 intervals, 0, 0, codegen, &allocator, true, false));
141 intervals.clear();
142 }
143
144 // Test with siblings.
145 {
146 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}};
147 intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
148 intervals[0]->SplitAt(43);
149 static constexpr size_t ranges2[][2] = {{42, 47}};
150 intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
151 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
152 intervals, 0, 0, codegen, &allocator, true, false));
153
154 intervals[1]->SetRegister(0);
155 // Sibling of the first interval has no register allocated to it.
156 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
157 intervals, 0, 0, codegen, &allocator, true, false));
158
159 intervals[0]->GetNextSibling()->SetRegister(0);
160 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
161 intervals, 0, 0, codegen, &allocator, true, false));
162 }
163 }
164
CFG1(Strategy strategy)165 static void CFG1(Strategy strategy) {
166 /*
167 * Test the following snippet:
168 * return 0;
169 *
170 * Which becomes the following graph:
171 * constant0
172 * goto
173 * |
174 * return
175 * |
176 * exit
177 */
178 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
179 Instruction::CONST_4 | 0 | 0,
180 Instruction::RETURN);
181
182 ASSERT_TRUE(Check(data, strategy));
183 }
184
185 TEST_ALL_STRATEGIES(CFG1);
186
Loop1(Strategy strategy)187 static void Loop1(Strategy strategy) {
188 /*
189 * Test the following snippet:
190 * int a = 0;
191 * while (a == a) {
192 * a = 4;
193 * }
194 * return 5;
195 *
196 * Which becomes the following graph:
197 * constant0
198 * constant4
199 * constant5
200 * goto
201 * |
202 * goto
203 * |
204 * phi
205 * equal
206 * if +++++
207 * | \ +
208 * | goto
209 * |
210 * return
211 * |
212 * exit
213 */
214
215 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
216 Instruction::CONST_4 | 0 | 0,
217 Instruction::IF_EQ, 4,
218 Instruction::CONST_4 | 4 << 12 | 0,
219 Instruction::GOTO | 0xFD00,
220 Instruction::CONST_4 | 5 << 12 | 1 << 8,
221 Instruction::RETURN | 1 << 8);
222
223 ASSERT_TRUE(Check(data, strategy));
224 }
225
226 TEST_ALL_STRATEGIES(Loop1);
227
Loop2(Strategy strategy)228 static void Loop2(Strategy strategy) {
229 /*
230 * Test the following snippet:
231 * int a = 0;
232 * while (a == 8) {
233 * a = 4 + 5;
234 * }
235 * return 6 + 7;
236 *
237 * Which becomes the following graph:
238 * constant0
239 * constant4
240 * constant5
241 * constant6
242 * constant7
243 * constant8
244 * goto
245 * |
246 * goto
247 * |
248 * phi
249 * equal
250 * if +++++
251 * | \ +
252 * | 4 + 5
253 * | goto
254 * |
255 * 6 + 7
256 * return
257 * |
258 * exit
259 */
260
261 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
262 Instruction::CONST_4 | 0 | 0,
263 Instruction::CONST_4 | 8 << 12 | 1 << 8,
264 Instruction::IF_EQ | 1 << 8, 7,
265 Instruction::CONST_4 | 4 << 12 | 0 << 8,
266 Instruction::CONST_4 | 5 << 12 | 1 << 8,
267 Instruction::ADD_INT, 1 << 8 | 0,
268 Instruction::GOTO | 0xFA00,
269 Instruction::CONST_4 | 6 << 12 | 1 << 8,
270 Instruction::CONST_4 | 7 << 12 | 1 << 8,
271 Instruction::ADD_INT, 1 << 8 | 0,
272 Instruction::RETURN | 1 << 8);
273
274 ASSERT_TRUE(Check(data, strategy));
275 }
276
277 TEST_ALL_STRATEGIES(Loop2);
278
Loop3(Strategy strategy)279 static void Loop3(Strategy strategy) {
280 /*
281 * Test the following snippet:
282 * int a = 0
283 * do {
284 * b = a;
285 * a++;
286 * } while (a != 5)
287 * return b;
288 *
289 * Which becomes the following graph:
290 * constant0
291 * constant1
292 * constant5
293 * goto
294 * |
295 * goto
296 * |++++++++++++
297 * phi +
298 * a++ +
299 * equals +
300 * if +
301 * |++++++++++++
302 * return
303 * |
304 * exit
305 */
306
307 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
308 Instruction::CONST_4 | 0 | 0,
309 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8,
310 Instruction::CONST_4 | 5 << 12 | 2 << 8,
311 Instruction::IF_NE | 1 << 8 | 2 << 12, 3,
312 Instruction::RETURN | 0 << 8,
313 Instruction::MOVE | 1 << 12 | 0 << 8,
314 Instruction::GOTO | 0xF900);
315
316 ArenaPool pool;
317 ArenaAllocator allocator(&pool);
318 HGraph* graph = CreateCFG(&allocator, data);
319 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
320 X86InstructionSetFeatures::FromCppDefines());
321 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
322 SsaLivenessAnalysis liveness(graph, &codegen);
323 liveness.Analyze();
324 RegisterAllocator* register_allocator =
325 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
326 register_allocator->AllocateRegisters();
327 ASSERT_TRUE(register_allocator->Validate(false));
328
329 HBasicBlock* loop_header = graph->GetBlocks()[2];
330 HPhi* phi = loop_header->GetFirstPhi()->AsPhi();
331
332 LiveInterval* phi_interval = phi->GetLiveInterval();
333 LiveInterval* loop_update = phi->InputAt(1)->GetLiveInterval();
334 ASSERT_TRUE(phi_interval->HasRegister());
335 ASSERT_TRUE(loop_update->HasRegister());
336 ASSERT_NE(phi_interval->GetRegister(), loop_update->GetRegister());
337
338 HBasicBlock* return_block = graph->GetBlocks()[3];
339 HReturn* ret = return_block->GetLastInstruction()->AsReturn();
340 ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
341 }
342
343 TEST_ALL_STRATEGIES(Loop3);
344
TEST_F(RegisterAllocatorTest,FirstRegisterUse)345 TEST_F(RegisterAllocatorTest, FirstRegisterUse) {
346 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
347 Instruction::CONST_4 | 0 | 0,
348 Instruction::XOR_INT_LIT8 | 1 << 8, 1 << 8,
349 Instruction::XOR_INT_LIT8 | 0 << 8, 1 << 8,
350 Instruction::XOR_INT_LIT8 | 1 << 8, 1 << 8 | 1,
351 Instruction::RETURN_VOID);
352
353 ArenaPool pool;
354 ArenaAllocator allocator(&pool);
355 HGraph* graph = CreateCFG(&allocator, data);
356 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
357 X86InstructionSetFeatures::FromCppDefines());
358 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
359 SsaLivenessAnalysis liveness(graph, &codegen);
360 liveness.Analyze();
361
362 HXor* first_xor = graph->GetBlocks()[1]->GetFirstInstruction()->AsXor();
363 HXor* last_xor = graph->GetBlocks()[1]->GetLastInstruction()->GetPrevious()->AsXor();
364 ASSERT_EQ(last_xor->InputAt(0), first_xor);
365 LiveInterval* interval = first_xor->GetLiveInterval();
366 ASSERT_EQ(interval->GetEnd(), last_xor->GetLifetimePosition());
367 ASSERT_TRUE(interval->GetNextSibling() == nullptr);
368
369 // We need a register for the output of the instruction.
370 ASSERT_EQ(interval->FirstRegisterUse(), first_xor->GetLifetimePosition());
371
372 // Split at the next instruction.
373 interval = interval->SplitAt(first_xor->GetLifetimePosition() + 2);
374 // The user of the split is the last add.
375 ASSERT_EQ(interval->FirstRegisterUse(), last_xor->GetLifetimePosition());
376
377 // Split before the last add.
378 LiveInterval* new_interval = interval->SplitAt(last_xor->GetLifetimePosition() - 1);
379 // Ensure the current interval has no register use...
380 ASSERT_EQ(interval->FirstRegisterUse(), kNoLifetime);
381 // And the new interval has it for the last add.
382 ASSERT_EQ(new_interval->FirstRegisterUse(), last_xor->GetLifetimePosition());
383 }
384
DeadPhi(Strategy strategy)385 static void DeadPhi(Strategy strategy) {
386 /* Test for a dead loop phi taking as back-edge input a phi that also has
387 * this loop phi as input. Walking backwards in SsaDeadPhiElimination
388 * does not solve the problem because the loop phi will be visited last.
389 *
390 * Test the following snippet:
391 * int a = 0
392 * do {
393 * if (true) {
394 * a = 2;
395 * }
396 * } while (true);
397 */
398
399 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
400 Instruction::CONST_4 | 0 | 0,
401 Instruction::CONST_4 | 1 << 8 | 0,
402 Instruction::IF_NE | 1 << 8 | 1 << 12, 3,
403 Instruction::CONST_4 | 2 << 12 | 0 << 8,
404 Instruction::GOTO | 0xFD00,
405 Instruction::RETURN_VOID);
406
407 ArenaPool pool;
408 ArenaAllocator allocator(&pool);
409 HGraph* graph = CreateCFG(&allocator, data);
410 SsaDeadPhiElimination(graph).Run();
411 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
412 X86InstructionSetFeatures::FromCppDefines());
413 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
414 SsaLivenessAnalysis liveness(graph, &codegen);
415 liveness.Analyze();
416 RegisterAllocator* register_allocator =
417 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
418 register_allocator->AllocateRegisters();
419 ASSERT_TRUE(register_allocator->Validate(false));
420 }
421
422 TEST_ALL_STRATEGIES(DeadPhi);
423
424 /**
425 * Test that the TryAllocateFreeReg method works in the presence of inactive intervals
426 * that share the same register. It should split the interval it is currently
427 * allocating for at the minimum lifetime position between the two inactive intervals.
428 * This test only applies to the linear scan allocator.
429 */
TEST_F(RegisterAllocatorTest,FreeUntil)430 TEST_F(RegisterAllocatorTest, FreeUntil) {
431 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
432 Instruction::CONST_4 | 0 | 0,
433 Instruction::RETURN);
434
435 ArenaPool pool;
436 ArenaAllocator allocator(&pool);
437 HGraph* graph = CreateCFG(&allocator, data);
438 SsaDeadPhiElimination(graph).Run();
439 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
440 X86InstructionSetFeatures::FromCppDefines());
441 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
442 SsaLivenessAnalysis liveness(graph, &codegen);
443 liveness.Analyze();
444 RegisterAllocatorLinearScan register_allocator(&allocator, &codegen, liveness);
445
446 // Add an artifical range to cover the temps that will be put in the unhandled list.
447 LiveInterval* unhandled = graph->GetEntryBlock()->GetFirstInstruction()->GetLiveInterval();
448 unhandled->AddLoopRange(0, 60);
449
450 // Populate the instructions in the liveness object, to please the register allocator.
451 for (size_t i = 0; i < 60; ++i) {
452 liveness.instructions_from_lifetime_position_.push_back(
453 graph->GetEntryBlock()->GetFirstInstruction());
454 }
455
456 // For SSA value intervals, only an interval resulted from a split may intersect
457 // with inactive intervals.
458 unhandled = register_allocator.Split(unhandled, 5);
459
460 // Add three temps holding the same register, and starting at different positions.
461 // Put the one that should be picked in the middle of the inactive list to ensure
462 // we do not depend on an order.
463 LiveInterval* interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
464 interval->AddRange(40, 50);
465 register_allocator.inactive_.push_back(interval);
466
467 interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
468 interval->AddRange(20, 30);
469 register_allocator.inactive_.push_back(interval);
470
471 interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
472 interval->AddRange(60, 70);
473 register_allocator.inactive_.push_back(interval);
474
475 register_allocator.number_of_registers_ = 1;
476 register_allocator.registers_array_ = allocator.AllocArray<size_t>(1);
477 register_allocator.processing_core_registers_ = true;
478 register_allocator.unhandled_ = ®ister_allocator.unhandled_core_intervals_;
479
480 ASSERT_TRUE(register_allocator.TryAllocateFreeReg(unhandled));
481
482 // Check that we have split the interval.
483 ASSERT_EQ(1u, register_allocator.unhandled_->size());
484 // Check that we know need to find a new register where the next interval
485 // that uses the register starts.
486 ASSERT_EQ(20u, register_allocator.unhandled_->front()->GetStart());
487 }
488
BuildIfElseWithPhi(ArenaAllocator * allocator,HPhi ** phi,HInstruction ** input1,HInstruction ** input2)489 static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator,
490 HPhi** phi,
491 HInstruction** input1,
492 HInstruction** input2) {
493 HGraph* graph = CreateGraph(allocator);
494 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
495 graph->AddBlock(entry);
496 graph->SetEntryBlock(entry);
497 HInstruction* parameter = new (allocator) HParameterValue(
498 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
499 entry->AddInstruction(parameter);
500
501 HBasicBlock* block = new (allocator) HBasicBlock(graph);
502 graph->AddBlock(block);
503 entry->AddSuccessor(block);
504
505 HInstruction* test = new (allocator) HInstanceFieldGet(parameter,
506 nullptr,
507 Primitive::kPrimBoolean,
508 MemberOffset(22),
509 false,
510 kUnknownFieldIndex,
511 kUnknownClassDefIndex,
512 graph->GetDexFile(),
513 0);
514 block->AddInstruction(test);
515 block->AddInstruction(new (allocator) HIf(test));
516 HBasicBlock* then = new (allocator) HBasicBlock(graph);
517 HBasicBlock* else_ = new (allocator) HBasicBlock(graph);
518 HBasicBlock* join = new (allocator) HBasicBlock(graph);
519 graph->AddBlock(then);
520 graph->AddBlock(else_);
521 graph->AddBlock(join);
522
523 block->AddSuccessor(then);
524 block->AddSuccessor(else_);
525 then->AddSuccessor(join);
526 else_->AddSuccessor(join);
527 then->AddInstruction(new (allocator) HGoto());
528 else_->AddInstruction(new (allocator) HGoto());
529
530 *phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
531 join->AddPhi(*phi);
532 *input1 = new (allocator) HInstanceFieldGet(parameter,
533 nullptr,
534 Primitive::kPrimInt,
535 MemberOffset(42),
536 false,
537 kUnknownFieldIndex,
538 kUnknownClassDefIndex,
539 graph->GetDexFile(),
540 0);
541 *input2 = new (allocator) HInstanceFieldGet(parameter,
542 nullptr,
543 Primitive::kPrimInt,
544 MemberOffset(42),
545 false,
546 kUnknownFieldIndex,
547 kUnknownClassDefIndex,
548 graph->GetDexFile(),
549 0);
550 then->AddInstruction(*input1);
551 else_->AddInstruction(*input2);
552 join->AddInstruction(new (allocator) HExit());
553 (*phi)->AddInput(*input1);
554 (*phi)->AddInput(*input2);
555
556 graph->BuildDominatorTree();
557 graph->AnalyzeLoops();
558 return graph;
559 }
560
PhiHint(Strategy strategy)561 static void PhiHint(Strategy strategy) {
562 ArenaPool pool;
563 ArenaAllocator allocator(&pool);
564 HPhi *phi;
565 HInstruction *input1, *input2;
566
567 {
568 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
569 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
570 X86InstructionSetFeatures::FromCppDefines());
571 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
572 SsaLivenessAnalysis liveness(graph, &codegen);
573 liveness.Analyze();
574
575 // Check that the register allocator is deterministic.
576 RegisterAllocator* register_allocator =
577 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
578 register_allocator->AllocateRegisters();
579
580 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0);
581 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0);
582 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0);
583 }
584
585 {
586 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
587 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
588 X86InstructionSetFeatures::FromCppDefines());
589 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
590 SsaLivenessAnalysis liveness(graph, &codegen);
591 liveness.Analyze();
592
593 // Set the phi to a specific register, and check that the inputs get allocated
594 // the same register.
595 phi->GetLocations()->UpdateOut(Location::RegisterLocation(2));
596 RegisterAllocator* register_allocator =
597 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
598 register_allocator->AllocateRegisters();
599
600 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
601 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
602 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
603 }
604
605 {
606 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
607 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
608 X86InstructionSetFeatures::FromCppDefines());
609 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
610 SsaLivenessAnalysis liveness(graph, &codegen);
611 liveness.Analyze();
612
613 // Set input1 to a specific register, and check that the phi and other input get allocated
614 // the same register.
615 input1->GetLocations()->UpdateOut(Location::RegisterLocation(2));
616 RegisterAllocator* register_allocator =
617 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
618 register_allocator->AllocateRegisters();
619
620 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
621 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
622 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
623 }
624
625 {
626 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
627 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
628 X86InstructionSetFeatures::FromCppDefines());
629 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
630 SsaLivenessAnalysis liveness(graph, &codegen);
631 liveness.Analyze();
632
633 // Set input2 to a specific register, and check that the phi and other input get allocated
634 // the same register.
635 input2->GetLocations()->UpdateOut(Location::RegisterLocation(2));
636 RegisterAllocator* register_allocator =
637 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
638 register_allocator->AllocateRegisters();
639
640 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
641 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
642 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
643 }
644 }
645
646 // TODO: Enable this test for graph coloring register allocation when iterative move
647 // coalescing is merged.
TEST_F(RegisterAllocatorTest,PhiHint_LinearScan)648 TEST_F(RegisterAllocatorTest, PhiHint_LinearScan) {
649 PhiHint(Strategy::kRegisterAllocatorLinearScan);
650 }
651
BuildFieldReturn(ArenaAllocator * allocator,HInstruction ** field,HInstruction ** ret)652 static HGraph* BuildFieldReturn(ArenaAllocator* allocator,
653 HInstruction** field,
654 HInstruction** ret) {
655 HGraph* graph = CreateGraph(allocator);
656 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
657 graph->AddBlock(entry);
658 graph->SetEntryBlock(entry);
659 HInstruction* parameter = new (allocator) HParameterValue(
660 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
661 entry->AddInstruction(parameter);
662
663 HBasicBlock* block = new (allocator) HBasicBlock(graph);
664 graph->AddBlock(block);
665 entry->AddSuccessor(block);
666
667 *field = new (allocator) HInstanceFieldGet(parameter,
668 nullptr,
669 Primitive::kPrimInt,
670 MemberOffset(42),
671 false,
672 kUnknownFieldIndex,
673 kUnknownClassDefIndex,
674 graph->GetDexFile(),
675 0);
676 block->AddInstruction(*field);
677 *ret = new (allocator) HReturn(*field);
678 block->AddInstruction(*ret);
679
680 HBasicBlock* exit = new (allocator) HBasicBlock(graph);
681 graph->AddBlock(exit);
682 block->AddSuccessor(exit);
683 exit->AddInstruction(new (allocator) HExit());
684
685 graph->BuildDominatorTree();
686 return graph;
687 }
688
ExpectedInRegisterHint(Strategy strategy)689 void RegisterAllocatorTest::ExpectedInRegisterHint(Strategy strategy) {
690 ArenaPool pool;
691 ArenaAllocator allocator(&pool);
692 HInstruction *field, *ret;
693
694 {
695 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
696 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
697 X86InstructionSetFeatures::FromCppDefines());
698 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
699 SsaLivenessAnalysis liveness(graph, &codegen);
700 liveness.Analyze();
701
702 RegisterAllocator* register_allocator =
703 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
704 register_allocator->AllocateRegisters();
705
706 // Sanity check that in normal conditions, the register should be hinted to 0 (EAX).
707 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0);
708 }
709
710 {
711 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
712 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
713 X86InstructionSetFeatures::FromCppDefines());
714 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
715 SsaLivenessAnalysis liveness(graph, &codegen);
716 liveness.Analyze();
717
718 // Check that the field gets put in the register expected by its use.
719 // Don't use SetInAt because we are overriding an already allocated location.
720 ret->GetLocations()->inputs_[0] = Location::RegisterLocation(2);
721
722 RegisterAllocator* register_allocator =
723 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
724 register_allocator->AllocateRegisters();
725
726 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2);
727 }
728 }
729
730 // TODO: Enable this test for graph coloring register allocation when iterative move
731 // coalescing is merged.
TEST_F(RegisterAllocatorTest,ExpectedInRegisterHint_LinearScan)732 TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint_LinearScan) {
733 ExpectedInRegisterHint(Strategy::kRegisterAllocatorLinearScan);
734 }
735
BuildTwoSubs(ArenaAllocator * allocator,HInstruction ** first_sub,HInstruction ** second_sub)736 static HGraph* BuildTwoSubs(ArenaAllocator* allocator,
737 HInstruction** first_sub,
738 HInstruction** second_sub) {
739 HGraph* graph = CreateGraph(allocator);
740 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
741 graph->AddBlock(entry);
742 graph->SetEntryBlock(entry);
743 HInstruction* parameter = new (allocator) HParameterValue(
744 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
745 entry->AddInstruction(parameter);
746
747 HInstruction* constant1 = graph->GetIntConstant(1);
748 HInstruction* constant2 = graph->GetIntConstant(2);
749
750 HBasicBlock* block = new (allocator) HBasicBlock(graph);
751 graph->AddBlock(block);
752 entry->AddSuccessor(block);
753
754 *first_sub = new (allocator) HSub(Primitive::kPrimInt, parameter, constant1);
755 block->AddInstruction(*first_sub);
756 *second_sub = new (allocator) HSub(Primitive::kPrimInt, *first_sub, constant2);
757 block->AddInstruction(*second_sub);
758
759 block->AddInstruction(new (allocator) HExit());
760
761 graph->BuildDominatorTree();
762 return graph;
763 }
764
SameAsFirstInputHint(Strategy strategy)765 void RegisterAllocatorTest::SameAsFirstInputHint(Strategy strategy) {
766 ArenaPool pool;
767 ArenaAllocator allocator(&pool);
768 HInstruction *first_sub, *second_sub;
769
770 {
771 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub);
772 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
773 X86InstructionSetFeatures::FromCppDefines());
774 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
775 SsaLivenessAnalysis liveness(graph, &codegen);
776 liveness.Analyze();
777
778 RegisterAllocator* register_allocator =
779 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
780 register_allocator->AllocateRegisters();
781
782 // Sanity check that in normal conditions, the registers are the same.
783 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 1);
784 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 1);
785 }
786
787 {
788 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub);
789 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
790 X86InstructionSetFeatures::FromCppDefines());
791 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
792 SsaLivenessAnalysis liveness(graph, &codegen);
793 liveness.Analyze();
794
795 // check that both adds get the same register.
796 // Don't use UpdateOutput because output is already allocated.
797 first_sub->InputAt(0)->GetLocations()->output_ = Location::RegisterLocation(2);
798 ASSERT_EQ(first_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
799 ASSERT_EQ(second_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
800
801 RegisterAllocator* register_allocator =
802 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
803 register_allocator->AllocateRegisters();
804
805 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 2);
806 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 2);
807 }
808 }
809
810 // TODO: Enable this test for graph coloring register allocation when iterative move
811 // coalescing is merged.
TEST_F(RegisterAllocatorTest,SameAsFirstInputHint_LinearScan)812 TEST_F(RegisterAllocatorTest, SameAsFirstInputHint_LinearScan) {
813 SameAsFirstInputHint(Strategy::kRegisterAllocatorLinearScan);
814 }
815
BuildDiv(ArenaAllocator * allocator,HInstruction ** div)816 static HGraph* BuildDiv(ArenaAllocator* allocator,
817 HInstruction** div) {
818 HGraph* graph = CreateGraph(allocator);
819 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
820 graph->AddBlock(entry);
821 graph->SetEntryBlock(entry);
822 HInstruction* first = new (allocator) HParameterValue(
823 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
824 HInstruction* second = new (allocator) HParameterValue(
825 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
826 entry->AddInstruction(first);
827 entry->AddInstruction(second);
828
829 HBasicBlock* block = new (allocator) HBasicBlock(graph);
830 graph->AddBlock(block);
831 entry->AddSuccessor(block);
832
833 *div = new (allocator) HDiv(Primitive::kPrimInt, first, second, 0); // don't care about dex_pc.
834 block->AddInstruction(*div);
835
836 block->AddInstruction(new (allocator) HExit());
837
838 graph->BuildDominatorTree();
839 return graph;
840 }
841
ExpectedExactInRegisterAndSameOutputHint(Strategy strategy)842 static void ExpectedExactInRegisterAndSameOutputHint(Strategy strategy) {
843 ArenaPool pool;
844 ArenaAllocator allocator(&pool);
845 HInstruction *div;
846
847 {
848 HGraph* graph = BuildDiv(&allocator, &div);
849 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
850 X86InstructionSetFeatures::FromCppDefines());
851 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
852 SsaLivenessAnalysis liveness(graph, &codegen);
853 liveness.Analyze();
854
855 RegisterAllocator* register_allocator =
856 RegisterAllocator::Create(&allocator, &codegen, liveness, strategy);
857 register_allocator->AllocateRegisters();
858
859 // div on x86 requires its first input in eax and the output be the same as the first input.
860 ASSERT_EQ(div->GetLiveInterval()->GetRegister(), 0);
861 }
862 }
863
864 // TODO: Enable this test for graph coloring register allocation when iterative move
865 // coalescing is merged.
TEST_F(RegisterAllocatorTest,ExpectedExactInRegisterAndSameOutputHint_LinearScan)866 TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint_LinearScan) {
867 ExpectedExactInRegisterAndSameOutputHint(Strategy::kRegisterAllocatorLinearScan);
868 }
869
870 // Test a bug in the register allocator, where allocating a blocked
871 // register would lead to spilling an inactive interval at the wrong
872 // position.
873 // This test only applies to the linear scan allocator.
TEST_F(RegisterAllocatorTest,SpillInactive)874 TEST_F(RegisterAllocatorTest, SpillInactive) {
875 ArenaPool pool;
876
877 // Create a synthesized graph to please the register_allocator and
878 // ssa_liveness_analysis code.
879 ArenaAllocator allocator(&pool);
880 HGraph* graph = CreateGraph(&allocator);
881 HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
882 graph->AddBlock(entry);
883 graph->SetEntryBlock(entry);
884 HInstruction* one = new (&allocator) HParameterValue(
885 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
886 HInstruction* two = new (&allocator) HParameterValue(
887 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
888 HInstruction* three = new (&allocator) HParameterValue(
889 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
890 HInstruction* four = new (&allocator) HParameterValue(
891 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
892 entry->AddInstruction(one);
893 entry->AddInstruction(two);
894 entry->AddInstruction(three);
895 entry->AddInstruction(four);
896
897 HBasicBlock* block = new (&allocator) HBasicBlock(graph);
898 graph->AddBlock(block);
899 entry->AddSuccessor(block);
900 block->AddInstruction(new (&allocator) HExit());
901
902 // We create a synthesized user requesting a register, to avoid just spilling the
903 // intervals.
904 HPhi* user = new (&allocator) HPhi(&allocator, 0, 1, Primitive::kPrimInt);
905 user->AddInput(one);
906 user->SetBlock(block);
907 LocationSummary* locations = new (&allocator) LocationSummary(user, LocationSummary::kNoCall);
908 locations->SetInAt(0, Location::RequiresRegister());
909 static constexpr size_t phi_ranges[][2] = {{20, 30}};
910 BuildInterval(phi_ranges, arraysize(phi_ranges), &allocator, -1, user);
911
912 // Create an interval with lifetime holes.
913 static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}};
914 LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one);
915 first->first_use_ = new(&allocator) UsePosition(user, false, 8, first->first_use_);
916 first->first_use_ = new(&allocator) UsePosition(user, false, 7, first->first_use_);
917 first->first_use_ = new(&allocator) UsePosition(user, false, 6, first->first_use_);
918
919 locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall);
920 locations->SetOut(Location::RequiresRegister());
921 first = first->SplitAt(1);
922
923 // Create an interval that conflicts with the next interval, to force the next
924 // interval to call `AllocateBlockedReg`.
925 static constexpr size_t ranges2[][2] = {{2, 4}};
926 LiveInterval* second = BuildInterval(ranges2, arraysize(ranges2), &allocator, -1, two);
927 locations = new (&allocator) LocationSummary(second->GetDefinedBy(), LocationSummary::kNoCall);
928 locations->SetOut(Location::RequiresRegister());
929
930 // Create an interval that will lead to splitting the first interval. The bug occured
931 // by splitting at a wrong position, in this case at the next intersection between
932 // this interval and the first interval. We would have then put the interval with ranges
933 // "[0, 2(, [4, 6(" in the list of handled intervals, even though we haven't processed intervals
934 // before lifetime position 6 yet.
935 static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}};
936 LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three);
937 third->first_use_ = new(&allocator) UsePosition(user, false, 8, third->first_use_);
938 third->first_use_ = new(&allocator) UsePosition(user, false, 4, third->first_use_);
939 third->first_use_ = new(&allocator) UsePosition(user, false, 3, third->first_use_);
940 locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall);
941 locations->SetOut(Location::RequiresRegister());
942 third = third->SplitAt(3);
943
944 // Because the first part of the split interval was considered handled, this interval
945 // was free to allocate the same register, even though it conflicts with it.
946 static constexpr size_t ranges4[][2] = {{4, 6}};
947 LiveInterval* fourth = BuildInterval(ranges4, arraysize(ranges4), &allocator, -1, four);
948 locations = new (&allocator) LocationSummary(fourth->GetDefinedBy(), LocationSummary::kNoCall);
949 locations->SetOut(Location::RequiresRegister());
950
951 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
952 X86InstructionSetFeatures::FromCppDefines());
953 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
954 SsaLivenessAnalysis liveness(graph, &codegen);
955 // Populate the instructions in the liveness object, to please the register allocator.
956 for (size_t i = 0; i < 32; ++i) {
957 liveness.instructions_from_lifetime_position_.push_back(user);
958 }
959
960 RegisterAllocatorLinearScan register_allocator(&allocator, &codegen, liveness);
961 register_allocator.unhandled_core_intervals_.push_back(fourth);
962 register_allocator.unhandled_core_intervals_.push_back(third);
963 register_allocator.unhandled_core_intervals_.push_back(second);
964 register_allocator.unhandled_core_intervals_.push_back(first);
965
966 // Set just one register available to make all intervals compete for the same.
967 register_allocator.number_of_registers_ = 1;
968 register_allocator.registers_array_ = allocator.AllocArray<size_t>(1);
969 register_allocator.processing_core_registers_ = true;
970 register_allocator.unhandled_ = ®ister_allocator.unhandled_core_intervals_;
971 register_allocator.LinearScan();
972
973 // Test that there is no conflicts between intervals.
974 ArenaVector<LiveInterval*> intervals(allocator.Adapter());
975 intervals.push_back(first);
976 intervals.push_back(second);
977 intervals.push_back(third);
978 intervals.push_back(fourth);
979 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
980 intervals, 0, 0, codegen, &allocator, true, false));
981 }
982
983 } // namespace art
984