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