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