register_allocator_test.cc revision 4833f5a1990c76bc2be89504225fb13cca22bedf 
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
31namespace art {
32
33// Note: the register allocator tests rely on the fact that constants have live
34// intervals and registers get allocated to them.
35
36class RegisterAllocatorTest : public CommonCompilerTest {};
37
38static 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  TransformToSsa(graph);
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 */
60TEST_F(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  ArenaVector<LiveInterval*> intervals(allocator.Adapter());
68
69  // Test with two intervals of the same range.
70  {
71    static constexpr size_t ranges[][2] = {{0, 42}};
72    intervals.push_back(BuildInterval(ranges, arraysize(ranges), &allocator, 0));
73    intervals.push_back(BuildInterval(ranges, arraysize(ranges), &allocator, 1));
74    ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
75        intervals, 0, 0, codegen, &allocator, true, false));
76
77    intervals[1]->SetRegister(0);
78    ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
79        intervals, 0, 0, codegen, &allocator, true, false));
80    intervals.clear();
81  }
82
83  // Test with two non-intersecting intervals.
84  {
85    static constexpr size_t ranges1[][2] = {{0, 42}};
86    intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
87    static constexpr size_t ranges2[][2] = {{42, 43}};
88    intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
89    ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
90        intervals, 0, 0, codegen, &allocator, true, false));
91
92    intervals[1]->SetRegister(0);
93    ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
94        intervals, 0, 0, codegen, &allocator, true, false));
95    intervals.clear();
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.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
102    static constexpr size_t ranges2[][2] = {{42, 43}};
103    intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
104    ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
105        intervals, 0, 0, codegen, &allocator, true, false));
106
107    intervals[1]->SetRegister(0);
108    ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
109        intervals, 0, 0, codegen, &allocator, true, false));
110    intervals.clear();
111  }
112
113  // Test with intersecting intervals.
114  {
115    static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}};
116    intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
117    static constexpr size_t ranges2[][2] = {{42, 47}};
118    intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
119    ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
120        intervals, 0, 0, codegen, &allocator, true, false));
121
122    intervals[1]->SetRegister(0);
123    ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
124        intervals, 0, 0, codegen, &allocator, true, false));
125    intervals.clear();
126  }
127
128  // Test with siblings.
129  {
130    static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}};
131    intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
132    intervals[0]->SplitAt(43);
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    // 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[0]->GetNextSibling()->SetRegister(0);
144    ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
145        intervals, 0, 0, codegen, &allocator, true, false));
146  }
147}
148
149TEST_F(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
169TEST_F(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
208TEST_F(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
257static 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  TransformToSsa(graph);
263  return graph;
264}
265
266TEST_F(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()[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()[3];
325  HReturn* ret = return_block->GetLastInstruction()->AsReturn();
326  ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
327}
328
329TEST_F(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()[1]->GetFirstInstruction()->AsXor();
347  HXor* last_xor = graph->GetBlocks()[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
369TEST_F(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 */
410TEST_F(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
430  // Populate the instructions in the liveness object, to please the register allocator.
431  for (size_t i = 0; i < 60; ++i) {
432    liveness.instructions_from_lifetime_position_.push_back(
433        graph->GetEntryBlock()->GetFirstInstruction());
434  }
435
436  // For SSA value intervals, only an interval resulted from a split may intersect
437  // with inactive intervals.
438  unhandled = register_allocator.Split(unhandled, 5);
439
440  // Add three temps holding the same register, and starting at different positions.
441  // Put the one that should be picked in the middle of the inactive list to ensure
442  // we do not depend on an order.
443  LiveInterval* interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
444  interval->AddRange(40, 50);
445  register_allocator.inactive_.push_back(interval);
446
447  interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
448  interval->AddRange(20, 30);
449  register_allocator.inactive_.push_back(interval);
450
451  interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
452  interval->AddRange(60, 70);
453  register_allocator.inactive_.push_back(interval);
454
455  register_allocator.number_of_registers_ = 1;
456  register_allocator.registers_array_ = allocator.AllocArray<size_t>(1);
457  register_allocator.processing_core_registers_ = true;
458  register_allocator.unhandled_ = &register_allocator.unhandled_core_intervals_;
459
460  ASSERT_TRUE(register_allocator.TryAllocateFreeReg(unhandled));
461
462  // Check that we have split the interval.
463  ASSERT_EQ(1u, register_allocator.unhandled_->size());
464  // Check that we know need to find a new register where the next interval
465  // that uses the register starts.
466  ASSERT_EQ(20u, register_allocator.unhandled_->front()->GetStart());
467}
468
469static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator,
470                                  HPhi** phi,
471                                  HInstruction** input1,
472                                  HInstruction** input2) {
473  HGraph* graph = CreateGraph(allocator);
474  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
475  ScopedNullHandle<mirror::DexCache> dex_cache;
476  graph->AddBlock(entry);
477  graph->SetEntryBlock(entry);
478  HInstruction* parameter = new (allocator) HParameterValue(
479      graph->GetDexFile(), 0, 0, Primitive::kPrimNot);
480  entry->AddInstruction(parameter);
481
482  HBasicBlock* block = new (allocator) HBasicBlock(graph);
483  graph->AddBlock(block);
484  entry->AddSuccessor(block);
485
486  HInstruction* test = new (allocator) HInstanceFieldGet(parameter,
487                                                         Primitive::kPrimBoolean,
488                                                         MemberOffset(22),
489                                                         false,
490                                                         kUnknownFieldIndex,
491                                                         kUnknownClassDefIndex,
492                                                         graph->GetDexFile(),
493                                                         dex_cache,
494                                                         0);
495  block->AddInstruction(test);
496  block->AddInstruction(new (allocator) HIf(test));
497  HBasicBlock* then = new (allocator) HBasicBlock(graph);
498  HBasicBlock* else_ = new (allocator) HBasicBlock(graph);
499  HBasicBlock* join = new (allocator) HBasicBlock(graph);
500  graph->AddBlock(then);
501  graph->AddBlock(else_);
502  graph->AddBlock(join);
503
504  block->AddSuccessor(then);
505  block->AddSuccessor(else_);
506  then->AddSuccessor(join);
507  else_->AddSuccessor(join);
508  then->AddInstruction(new (allocator) HGoto());
509  else_->AddInstruction(new (allocator) HGoto());
510
511  *phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
512  join->AddPhi(*phi);
513  *input1 = new (allocator) HInstanceFieldGet(parameter,
514                                              Primitive::kPrimInt,
515                                              MemberOffset(42),
516                                              false,
517                                              kUnknownFieldIndex,
518                                              kUnknownClassDefIndex,
519                                              graph->GetDexFile(),
520                                              dex_cache,
521                                              0);
522*input2 = new (allocator) HInstanceFieldGet(parameter,
523                                            Primitive::kPrimInt,
524                                            MemberOffset(42),
525                                            false,
526                                            kUnknownFieldIndex,
527                                            kUnknownClassDefIndex,
528                                            graph->GetDexFile(),
529                                            dex_cache,
530                                            0);
531  then->AddInstruction(*input1);
532  else_->AddInstruction(*input2);
533  join->AddInstruction(new (allocator) HExit());
534  (*phi)->AddInput(*input1);
535  (*phi)->AddInput(*input2);
536
537  graph->BuildDominatorTree();
538  graph->AnalyzeNaturalLoops();
539  return graph;
540}
541
542TEST_F(RegisterAllocatorTest, PhiHint) {
543  ArenaPool pool;
544  ArenaAllocator allocator(&pool);
545  HPhi *phi;
546  HInstruction *input1, *input2;
547
548  {
549    HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
550    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
551        X86InstructionSetFeatures::FromCppDefines());
552    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
553    SsaLivenessAnalysis liveness(graph, &codegen);
554    liveness.Analyze();
555
556    // Check that the register allocator is deterministic.
557    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
558    register_allocator.AllocateRegisters();
559
560    ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0);
561    ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0);
562    ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0);
563  }
564
565  {
566    HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
567    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
568        X86InstructionSetFeatures::FromCppDefines());
569    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
570    SsaLivenessAnalysis liveness(graph, &codegen);
571    liveness.Analyze();
572
573    // Set the phi to a specific register, and check that the inputs get allocated
574    // the same register.
575    phi->GetLocations()->UpdateOut(Location::RegisterLocation(2));
576    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
577    register_allocator.AllocateRegisters();
578
579    ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
580    ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
581    ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
582  }
583
584  {
585    HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
586    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
587        X86InstructionSetFeatures::FromCppDefines());
588    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
589    SsaLivenessAnalysis liveness(graph, &codegen);
590    liveness.Analyze();
591
592    // Set input1 to a specific register, and check that the phi and other input get allocated
593    // the same register.
594    input1->GetLocations()->UpdateOut(Location::RegisterLocation(2));
595    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
596    register_allocator.AllocateRegisters();
597
598    ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
599    ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
600    ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
601  }
602
603  {
604    HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
605    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
606        X86InstructionSetFeatures::FromCppDefines());
607    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
608    SsaLivenessAnalysis liveness(graph, &codegen);
609    liveness.Analyze();
610
611    // Set input2 to a specific register, and check that the phi and other input get allocated
612    // the same register.
613    input2->GetLocations()->UpdateOut(Location::RegisterLocation(2));
614    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
615    register_allocator.AllocateRegisters();
616
617    ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
618    ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
619    ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
620  }
621}
622
623static HGraph* BuildFieldReturn(ArenaAllocator* allocator,
624                                HInstruction** field,
625                                HInstruction** ret) {
626  HGraph* graph = CreateGraph(allocator);
627  ScopedNullHandle<mirror::DexCache> dex_cache;
628  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
629  graph->AddBlock(entry);
630  graph->SetEntryBlock(entry);
631  HInstruction* parameter = new (allocator) HParameterValue(
632      graph->GetDexFile(), 0, 0, Primitive::kPrimNot);
633  entry->AddInstruction(parameter);
634
635  HBasicBlock* block = new (allocator) HBasicBlock(graph);
636  graph->AddBlock(block);
637  entry->AddSuccessor(block);
638
639  *field = new (allocator) HInstanceFieldGet(parameter,
640                                             Primitive::kPrimInt,
641                                             MemberOffset(42),
642                                             false,
643                                             kUnknownFieldIndex,
644                                             kUnknownClassDefIndex,
645                                             graph->GetDexFile(),
646                                             dex_cache,
647                                             0);
648  block->AddInstruction(*field);
649  *ret = new (allocator) HReturn(*field);
650  block->AddInstruction(*ret);
651
652  HBasicBlock* exit = new (allocator) HBasicBlock(graph);
653  graph->AddBlock(exit);
654  block->AddSuccessor(exit);
655  exit->AddInstruction(new (allocator) HExit());
656
657  graph->BuildDominatorTree();
658  return graph;
659}
660
661TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) {
662  ArenaPool pool;
663  ArenaAllocator allocator(&pool);
664  HInstruction *field, *ret;
665
666  {
667    HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
668    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
669        X86InstructionSetFeatures::FromCppDefines());
670    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
671    SsaLivenessAnalysis liveness(graph, &codegen);
672    liveness.Analyze();
673
674    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
675    register_allocator.AllocateRegisters();
676
677    // Sanity check that in normal conditions, the register should be hinted to 0 (EAX).
678    ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0);
679  }
680
681  {
682    HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
683    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
684        X86InstructionSetFeatures::FromCppDefines());
685    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
686    SsaLivenessAnalysis liveness(graph, &codegen);
687    liveness.Analyze();
688
689    // Check that the field gets put in the register expected by its use.
690    // Don't use SetInAt because we are overriding an already allocated location.
691    ret->GetLocations()->inputs_[0] = Location::RegisterLocation(2);
692
693    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
694    register_allocator.AllocateRegisters();
695
696    ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2);
697  }
698}
699
700static HGraph* BuildTwoSubs(ArenaAllocator* allocator,
701                            HInstruction** first_sub,
702                            HInstruction** second_sub) {
703  HGraph* graph = CreateGraph(allocator);
704  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
705  graph->AddBlock(entry);
706  graph->SetEntryBlock(entry);
707  HInstruction* parameter = new (allocator) HParameterValue(
708      graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
709  entry->AddInstruction(parameter);
710
711  HInstruction* constant1 = graph->GetIntConstant(1);
712  HInstruction* constant2 = graph->GetIntConstant(2);
713
714  HBasicBlock* block = new (allocator) HBasicBlock(graph);
715  graph->AddBlock(block);
716  entry->AddSuccessor(block);
717
718  *first_sub = new (allocator) HSub(Primitive::kPrimInt, parameter, constant1);
719  block->AddInstruction(*first_sub);
720  *second_sub = new (allocator) HSub(Primitive::kPrimInt, *first_sub, constant2);
721  block->AddInstruction(*second_sub);
722
723  block->AddInstruction(new (allocator) HExit());
724
725  graph->BuildDominatorTree();
726  return graph;
727}
728
729TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) {
730  ArenaPool pool;
731  ArenaAllocator allocator(&pool);
732  HInstruction *first_sub, *second_sub;
733
734  {
735    HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub);
736    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
737        X86InstructionSetFeatures::FromCppDefines());
738    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
739    SsaLivenessAnalysis liveness(graph, &codegen);
740    liveness.Analyze();
741
742    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
743    register_allocator.AllocateRegisters();
744
745    // Sanity check that in normal conditions, the registers are the same.
746    ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 1);
747    ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 1);
748  }
749
750  {
751    HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub);
752    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
753        X86InstructionSetFeatures::FromCppDefines());
754    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
755    SsaLivenessAnalysis liveness(graph, &codegen);
756    liveness.Analyze();
757
758    // check that both adds get the same register.
759    // Don't use UpdateOutput because output is already allocated.
760    first_sub->InputAt(0)->GetLocations()->output_ = Location::RegisterLocation(2);
761    ASSERT_EQ(first_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
762    ASSERT_EQ(second_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
763
764    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
765    register_allocator.AllocateRegisters();
766
767    ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 2);
768    ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 2);
769  }
770}
771
772static HGraph* BuildDiv(ArenaAllocator* allocator,
773                        HInstruction** div) {
774  HGraph* graph = CreateGraph(allocator);
775  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
776  graph->AddBlock(entry);
777  graph->SetEntryBlock(entry);
778  HInstruction* first = new (allocator) HParameterValue(
779      graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
780  HInstruction* second = new (allocator) HParameterValue(
781      graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
782  entry->AddInstruction(first);
783  entry->AddInstruction(second);
784
785  HBasicBlock* block = new (allocator) HBasicBlock(graph);
786  graph->AddBlock(block);
787  entry->AddSuccessor(block);
788
789  *div = new (allocator) HDiv(Primitive::kPrimInt, first, second, 0);  // don't care about dex_pc.
790  block->AddInstruction(*div);
791
792  block->AddInstruction(new (allocator) HExit());
793
794  graph->BuildDominatorTree();
795  return graph;
796}
797
798TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) {
799  ArenaPool pool;
800  ArenaAllocator allocator(&pool);
801  HInstruction *div;
802
803  {
804    HGraph* graph = BuildDiv(&allocator, &div);
805    std::unique_ptr<const X86InstructionSetFeatures> features_x86(
806        X86InstructionSetFeatures::FromCppDefines());
807    x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
808    SsaLivenessAnalysis liveness(graph, &codegen);
809    liveness.Analyze();
810
811    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
812    register_allocator.AllocateRegisters();
813
814    // div on x86 requires its first input in eax and the output be the same as the first input.
815    ASSERT_EQ(div->GetLiveInterval()->GetRegister(), 0);
816  }
817}
818
819// Test a bug in the register allocator, where allocating a blocked
820// register would lead to spilling an inactive interval at the wrong
821// position.
822TEST_F(RegisterAllocatorTest, SpillInactive) {
823  ArenaPool pool;
824
825  // Create a synthesized graph to please the register_allocator and
826  // ssa_liveness_analysis code.
827  ArenaAllocator allocator(&pool);
828  HGraph* graph = CreateGraph(&allocator);
829  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
830  graph->AddBlock(entry);
831  graph->SetEntryBlock(entry);
832  HInstruction* one = new (&allocator) HParameterValue(
833      graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
834  HInstruction* two = new (&allocator) HParameterValue(
835      graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
836  HInstruction* three = new (&allocator) HParameterValue(
837      graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
838  HInstruction* four = new (&allocator) HParameterValue(
839      graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
840  entry->AddInstruction(one);
841  entry->AddInstruction(two);
842  entry->AddInstruction(three);
843  entry->AddInstruction(four);
844
845  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
846  graph->AddBlock(block);
847  entry->AddSuccessor(block);
848  block->AddInstruction(new (&allocator) HExit());
849
850  // We create a synthesized user requesting a register, to avoid just spilling the
851  // intervals.
852  HPhi* user = new (&allocator) HPhi(&allocator, 0, 1, Primitive::kPrimInt);
853  user->AddInput(one);
854  user->SetBlock(block);
855  LocationSummary* locations = new (&allocator) LocationSummary(user, LocationSummary::kNoCall);
856  locations->SetInAt(0, Location::RequiresRegister());
857  static constexpr size_t phi_ranges[][2] = {{20, 30}};
858  BuildInterval(phi_ranges, arraysize(phi_ranges), &allocator, -1, user);
859
860  // Create an interval with lifetime holes.
861  static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}};
862  LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one);
863  first->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, first->first_use_);
864  first->first_use_ = new(&allocator) UsePosition(user, 0, false, 7, first->first_use_);
865  first->first_use_ = new(&allocator) UsePosition(user, 0, false, 6, first->first_use_);
866
867  locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall);
868  locations->SetOut(Location::RequiresRegister());
869  first = first->SplitAt(1);
870
871  // Create an interval that conflicts with the next interval, to force the next
872  // interval to call `AllocateBlockedReg`.
873  static constexpr size_t ranges2[][2] = {{2, 4}};
874  LiveInterval* second = BuildInterval(ranges2, arraysize(ranges2), &allocator, -1, two);
875  locations = new (&allocator) LocationSummary(second->GetDefinedBy(), LocationSummary::kNoCall);
876  locations->SetOut(Location::RequiresRegister());
877
878  // Create an interval that will lead to splitting the first interval. The bug occured
879  // by splitting at a wrong position, in this case at the next intersection between
880  // this interval and the first interval. We would have then put the interval with ranges
881  // "[0, 2(, [4, 6(" in the list of handled intervals, even though we haven't processed intervals
882  // before lifetime position 6 yet.
883  static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}};
884  LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three);
885  third->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, third->first_use_);
886  third->first_use_ = new(&allocator) UsePosition(user, 0, false, 4, third->first_use_);
887  third->first_use_ = new(&allocator) UsePosition(user, 0, false, 3, third->first_use_);
888  locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall);
889  locations->SetOut(Location::RequiresRegister());
890  third = third->SplitAt(3);
891
892  // Because the first part of the split interval was considered handled, this interval
893  // was free to allocate the same register, even though it conflicts with it.
894  static constexpr size_t ranges4[][2] = {{4, 6}};
895  LiveInterval* fourth = BuildInterval(ranges4, arraysize(ranges4), &allocator, -1, four);
896  locations = new (&allocator) LocationSummary(fourth->GetDefinedBy(), LocationSummary::kNoCall);
897  locations->SetOut(Location::RequiresRegister());
898
899  std::unique_ptr<const X86InstructionSetFeatures> features_x86(
900      X86InstructionSetFeatures::FromCppDefines());
901  x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
902  SsaLivenessAnalysis liveness(graph, &codegen);
903  // Populate the instructions in the liveness object, to please the register allocator.
904  for (size_t i = 0; i < 32; ++i) {
905    liveness.instructions_from_lifetime_position_.push_back(user);
906  }
907
908  RegisterAllocator register_allocator(&allocator, &codegen, liveness);
909  register_allocator.unhandled_core_intervals_.push_back(fourth);
910  register_allocator.unhandled_core_intervals_.push_back(third);
911  register_allocator.unhandled_core_intervals_.push_back(second);
912  register_allocator.unhandled_core_intervals_.push_back(first);
913
914  // Set just one register available to make all intervals compete for the same.
915  register_allocator.number_of_registers_ = 1;
916  register_allocator.registers_array_ = allocator.AllocArray<size_t>(1);
917  register_allocator.processing_core_registers_ = true;
918  register_allocator.unhandled_ = &register_allocator.unhandled_core_intervals_;
919  register_allocator.LinearScan();
920
921  // Test that there is no conflicts between intervals.
922  ArenaVector<LiveInterval*> intervals(allocator.Adapter());
923  intervals.push_back(first);
924  intervals.push_back(second);
925  intervals.push_back(third);
926  intervals.push_back(fourth);
927  ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
928      intervals, 0, 0, codegen, &allocator, true, false));
929}
930
931}  // namespace art
932