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