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