register_allocator_test.cc revision 56b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2f 
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 "nodes.h"
23#include "optimizing_unit_test.h"
24#include "register_allocator.h"
25#include "ssa_liveness_analysis.h"
26#include "ssa_phi_elimination.h"
27#include "utils/arena_allocator.h"
28
29#include "gtest/gtest.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
36static bool Check(const uint16_t* data) {
37  ArenaPool pool;
38  ArenaAllocator allocator(&pool);
39  HGraphBuilder builder(&allocator);
40  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
41  HGraph* graph = builder.BuildGraph(*item);
42  graph->BuildDominatorTree();
43  graph->TransformToSSA();
44  graph->FindNaturalLoops();
45  x86::CodeGeneratorX86 codegen(graph);
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);
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  HGraphBuilder builder(allocator);
254  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
255  HGraph* graph = builder.BuildGraph(*item);
256  graph->BuildDominatorTree();
257  graph->TransformToSSA();
258  graph->FindNaturalLoops();
259  return graph;
260}
261
262TEST(RegisterAllocatorTest, Loop3) {
263  /*
264   * Test the following snippet:
265   *  int a = 0
266   *  do {
267   *    b = a;
268   *    a++;
269   *  } while (a != 5)
270   *  return b;
271   *
272   * Which becomes the following graph:
273   *       constant0
274   *       constant1
275   *       constant5
276   *       goto
277   *        |
278   *       goto
279   *        |++++++++++++
280   *       phi          +
281   *       a++          +
282   *       equals       +
283   *       if           +
284   *        |++++++++++++
285   *       return
286   *        |
287   *       exit
288   */
289
290  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
291    Instruction::CONST_4 | 0 | 0,
292    Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8,
293    Instruction::CONST_4 | 5 << 12 | 2 << 8,
294    Instruction::IF_NE | 1 << 8 | 2 << 12, 3,
295    Instruction::RETURN | 0 << 8,
296    Instruction::MOVE | 1 << 12 | 0 << 8,
297    Instruction::GOTO | 0xF900);
298
299  ArenaPool pool;
300  ArenaAllocator allocator(&pool);
301  HGraph* graph = BuildSSAGraph(data, &allocator);
302  x86::CodeGeneratorX86 codegen(graph);
303  SsaLivenessAnalysis liveness(*graph, &codegen);
304  liveness.Analyze();
305  RegisterAllocator register_allocator(&allocator, &codegen, liveness);
306  register_allocator.AllocateRegisters();
307  ASSERT_TRUE(register_allocator.Validate(false));
308
309  HBasicBlock* loop_header = graph->GetBlocks().Get(2);
310  HPhi* phi = loop_header->GetFirstPhi()->AsPhi();
311
312  LiveInterval* phi_interval = phi->GetLiveInterval();
313  LiveInterval* loop_update = phi->InputAt(1)->GetLiveInterval();
314  ASSERT_TRUE(phi_interval->HasRegister());
315  ASSERT_TRUE(loop_update->HasRegister());
316  ASSERT_NE(phi_interval->GetRegister(), loop_update->GetRegister());
317
318  HBasicBlock* return_block = graph->GetBlocks().Get(3);
319  HReturn* ret = return_block->GetLastInstruction()->AsReturn();
320  ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
321}
322
323TEST(RegisterAllocatorTest, FirstRegisterUse) {
324  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
325    Instruction::CONST_4 | 0 | 0,
326    Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8,
327    Instruction::ADD_INT_LIT8 | 0 << 8, 1 << 8,
328    Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8 | 1,
329    Instruction::RETURN_VOID);
330
331  ArenaPool pool;
332  ArenaAllocator allocator(&pool);
333  HGraph* graph = BuildSSAGraph(data, &allocator);
334  x86::CodeGeneratorX86 codegen(graph);
335  SsaLivenessAnalysis liveness(*graph, &codegen);
336  liveness.Analyze();
337
338  HAdd* first_add = graph->GetBlocks().Get(1)->GetFirstInstruction()->AsAdd();
339  HAdd* last_add = graph->GetBlocks().Get(1)->GetLastInstruction()->GetPrevious()->AsAdd();
340  ASSERT_EQ(last_add->InputAt(0), first_add);
341  LiveInterval* interval = first_add->GetLiveInterval();
342  ASSERT_EQ(interval->GetEnd(), last_add->GetLifetimePosition());
343  ASSERT_TRUE(interval->GetNextSibling() == nullptr);
344
345  // We need a register for the output of the instruction.
346  ASSERT_EQ(interval->FirstRegisterUse(), first_add->GetLifetimePosition());
347
348  // Split at the next instruction.
349  interval = interval->SplitAt(first_add->GetLifetimePosition() + 2);
350  // The user of the split is the last add.
351  ASSERT_EQ(interval->FirstRegisterUse(), last_add->GetLifetimePosition() - 1);
352
353  // Split before the last add.
354  LiveInterval* new_interval = interval->SplitAt(last_add->GetLifetimePosition() - 1);
355  // Ensure the current interval has no register use...
356  ASSERT_EQ(interval->FirstRegisterUse(), kNoLifetime);
357  // And the new interval has it for the last add.
358  ASSERT_EQ(new_interval->FirstRegisterUse(), last_add->GetLifetimePosition() - 1);
359}
360
361TEST(RegisterAllocatorTest, DeadPhi) {
362  /* Test for a dead loop phi taking as back-edge input a phi that also has
363   * this loop phi as input. Walking backwards in SsaDeadPhiElimination
364   * does not solve the problem because the loop phi will be visited last.
365   *
366   * Test the following snippet:
367   *  int a = 0
368   *  do {
369   *    if (true) {
370   *      a = 2;
371   *    }
372   *  } while (true);
373   */
374
375  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
376    Instruction::CONST_4 | 0 | 0,
377    Instruction::CONST_4 | 1 << 8 | 0,
378    Instruction::IF_NE | 1 << 8 | 1 << 12, 3,
379    Instruction::CONST_4 | 2 << 12 | 0 << 8,
380    Instruction::GOTO | 0xFD00,
381    Instruction::RETURN_VOID);
382
383  ArenaPool pool;
384  ArenaAllocator allocator(&pool);
385  HGraph* graph = BuildSSAGraph(data, &allocator);
386  SsaDeadPhiElimination(graph).Run();
387  x86::CodeGeneratorX86 codegen(graph);
388  SsaLivenessAnalysis liveness(*graph, &codegen);
389  liveness.Analyze();
390  RegisterAllocator register_allocator(&allocator, &codegen, liveness);
391  register_allocator.AllocateRegisters();
392  ASSERT_TRUE(register_allocator.Validate(false));
393}
394
395/**
396 * Test that the TryAllocateFreeReg method works in the presence of inactive intervals
397 * that share the same register. It should split the interval it is currently
398 * allocating for at the minimum lifetime position between the two inactive intervals.
399 */
400TEST(RegisterAllocatorTest, FreeUntil) {
401  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
402    Instruction::CONST_4 | 0 | 0,
403    Instruction::RETURN);
404
405  ArenaPool pool;
406  ArenaAllocator allocator(&pool);
407  HGraph* graph = BuildSSAGraph(data, &allocator);
408  SsaDeadPhiElimination(graph).Run();
409  x86::CodeGeneratorX86 codegen(graph);
410  SsaLivenessAnalysis liveness(*graph, &codegen);
411  liveness.Analyze();
412  RegisterAllocator register_allocator(&allocator, &codegen, liveness);
413
414  // Add an artifical range to cover the temps that will be put in the unhandled list.
415  LiveInterval* unhandled = graph->GetEntryBlock()->GetFirstInstruction()->GetLiveInterval();
416  unhandled->AddLoopRange(0, 60);
417
418  // Add three temps holding the same register, and starting at different positions.
419  // Put the one that should be picked in the middle of the inactive list to ensure
420  // we do not depend on an order.
421  LiveInterval* interval = LiveInterval::MakeTempInterval(&allocator, Primitive::kPrimInt);
422  interval->SetRegister(0);
423  interval->AddRange(40, 50);
424  register_allocator.inactive_.Add(interval);
425
426  interval = LiveInterval::MakeTempInterval(&allocator, Primitive::kPrimInt);
427  interval->SetRegister(0);
428  interval->AddRange(20, 30);
429  register_allocator.inactive_.Add(interval);
430
431  interval = LiveInterval::MakeTempInterval(&allocator, Primitive::kPrimInt);
432  interval->SetRegister(0);
433  interval->AddRange(60, 70);
434  register_allocator.inactive_.Add(interval);
435
436  register_allocator.number_of_registers_ = 1;
437  register_allocator.registers_array_ = allocator.AllocArray<size_t>(1);
438  register_allocator.processing_core_registers_ = true;
439  register_allocator.unhandled_ = &register_allocator.unhandled_core_intervals_;
440
441  register_allocator.TryAllocateFreeReg(unhandled);
442
443  // Check that we have split the interval.
444  ASSERT_EQ(1u, register_allocator.unhandled_->Size());
445  // Check that we know need to find a new register where the next interval
446  // that uses the register starts.
447  ASSERT_EQ(20u, register_allocator.unhandled_->Get(0)->GetStart());
448}
449
450static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator,
451                                  HPhi** phi,
452                                  HInstruction** input1,
453                                  HInstruction** input2) {
454  HGraph* graph = new (allocator) HGraph(allocator);
455  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
456  graph->AddBlock(entry);
457  graph->SetEntryBlock(entry);
458  HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
459  entry->AddInstruction(parameter);
460
461  HBasicBlock* block = new (allocator) HBasicBlock(graph);
462  graph->AddBlock(block);
463  entry->AddSuccessor(block);
464
465  HInstruction* test = new (allocator) HInstanceFieldGet(
466      parameter, Primitive::kPrimBoolean, MemberOffset(22));
467  block->AddInstruction(test);
468  block->AddInstruction(new (allocator) HIf(test));
469  HBasicBlock* then = new (allocator) HBasicBlock(graph);
470  HBasicBlock* else_ = new (allocator) HBasicBlock(graph);
471  HBasicBlock* join = new (allocator) HBasicBlock(graph);
472  graph->AddBlock(then);
473  graph->AddBlock(else_);
474  graph->AddBlock(join);
475
476  block->AddSuccessor(then);
477  block->AddSuccessor(else_);
478  then->AddSuccessor(join);
479  else_->AddSuccessor(join);
480  then->AddInstruction(new (allocator) HGoto());
481  else_->AddInstruction(new (allocator) HGoto());
482
483  *phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
484  join->AddPhi(*phi);
485  *input1 = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, MemberOffset(42));
486  *input2 = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, MemberOffset(42));
487  then->AddInstruction(*input1);
488  else_->AddInstruction(*input2);
489  join->AddInstruction(new (allocator) HExit());
490  (*phi)->AddInput(*input1);
491  (*phi)->AddInput(*input2);
492
493  graph->BuildDominatorTree();
494  graph->FindNaturalLoops();
495  return graph;
496}
497
498TEST(RegisterAllocatorTest, PhiHint) {
499  ArenaPool pool;
500  ArenaAllocator allocator(&pool);
501  HPhi *phi;
502  HInstruction *input1, *input2;
503
504  {
505    HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
506    x86::CodeGeneratorX86 codegen(graph);
507    SsaLivenessAnalysis liveness(*graph, &codegen);
508    liveness.Analyze();
509
510    // Check that the register allocator is deterministic.
511    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
512    register_allocator.AllocateRegisters();
513
514    ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0);
515    ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0);
516    ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0);
517  }
518
519  {
520    HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
521    x86::CodeGeneratorX86 codegen(graph);
522    SsaLivenessAnalysis liveness(*graph, &codegen);
523    liveness.Analyze();
524
525    // Set the phi to a specific register, and check that the inputs get allocated
526    // the same register.
527    phi->GetLocations()->SetOut(Location::RegisterLocation(2));
528    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
529    register_allocator.AllocateRegisters();
530
531    ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
532    ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
533    ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
534  }
535
536  {
537    HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
538    x86::CodeGeneratorX86 codegen(graph);
539    SsaLivenessAnalysis liveness(*graph, &codegen);
540    liveness.Analyze();
541
542    // Set input1 to a specific register, and check that the phi and other input get allocated
543    // the same register.
544    input1->GetLocations()->SetOut(Location::RegisterLocation(2));
545    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
546    register_allocator.AllocateRegisters();
547
548    ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
549    ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
550    ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
551  }
552
553  {
554    HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
555    x86::CodeGeneratorX86 codegen(graph);
556    SsaLivenessAnalysis liveness(*graph, &codegen);
557    liveness.Analyze();
558
559    // Set input2 to a specific register, and check that the phi and other input get allocated
560    // the same register.
561    input2->GetLocations()->SetOut(Location::RegisterLocation(2));
562    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
563    register_allocator.AllocateRegisters();
564
565    ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
566    ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
567    ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
568  }
569}
570
571static HGraph* BuildFieldReturn(ArenaAllocator* allocator,
572                                HInstruction** field,
573                                HInstruction** ret) {
574  HGraph* graph = new (allocator) HGraph(allocator);
575  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
576  graph->AddBlock(entry);
577  graph->SetEntryBlock(entry);
578  HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
579  entry->AddInstruction(parameter);
580
581  HBasicBlock* block = new (allocator) HBasicBlock(graph);
582  graph->AddBlock(block);
583  entry->AddSuccessor(block);
584
585  *field = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, MemberOffset(42));
586  block->AddInstruction(*field);
587  *ret = new (allocator) HReturn(*field);
588  block->AddInstruction(*ret);
589
590  HBasicBlock* exit = new (allocator) HBasicBlock(graph);
591  graph->AddBlock(exit);
592  block->AddSuccessor(exit);
593  exit->AddInstruction(new (allocator) HExit());
594  return graph;
595}
596
597TEST(RegisterAllocatorTest, ExpectedInRegisterHint) {
598  ArenaPool pool;
599  ArenaAllocator allocator(&pool);
600  HInstruction *field, *ret;
601
602  {
603    HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
604    x86::CodeGeneratorX86 codegen(graph);
605    SsaLivenessAnalysis liveness(*graph, &codegen);
606    liveness.Analyze();
607
608    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
609    register_allocator.AllocateRegisters();
610
611    // Sanity check that in normal conditions, the register should be hinted to 0 (EAX).
612    ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0);
613  }
614
615  {
616    HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
617    x86::CodeGeneratorX86 codegen(graph);
618    SsaLivenessAnalysis liveness(*graph, &codegen);
619    liveness.Analyze();
620
621    // Check that the field gets put in the register expected by its use.
622    ret->GetLocations()->SetInAt(0, Location::RegisterLocation(2));
623
624    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
625    register_allocator.AllocateRegisters();
626
627    ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2);
628  }
629}
630
631static HGraph* BuildTwoAdds(ArenaAllocator* allocator,
632                            HInstruction** first_add,
633                            HInstruction** second_add) {
634  HGraph* graph = new (allocator) HGraph(allocator);
635  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
636  graph->AddBlock(entry);
637  graph->SetEntryBlock(entry);
638  HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimInt);
639  HInstruction* constant1 = new (allocator) HIntConstant(0);
640  HInstruction* constant2 = new (allocator) HIntConstant(0);
641  entry->AddInstruction(parameter);
642  entry->AddInstruction(constant1);
643  entry->AddInstruction(constant2);
644
645  HBasicBlock* block = new (allocator) HBasicBlock(graph);
646  graph->AddBlock(block);
647  entry->AddSuccessor(block);
648
649  *first_add = new (allocator) HAdd(Primitive::kPrimInt, parameter, constant1);
650  block->AddInstruction(*first_add);
651  *second_add = new (allocator) HAdd(Primitive::kPrimInt, *first_add, constant2);
652  block->AddInstruction(*second_add);
653
654  block->AddInstruction(new (allocator) HExit());
655  return graph;
656}
657
658TEST(RegisterAllocatorTest, SameAsFirstInputHint) {
659  ArenaPool pool;
660  ArenaAllocator allocator(&pool);
661  HInstruction *first_add, *second_add;
662
663  {
664    HGraph* graph = BuildTwoAdds(&allocator, &first_add, &second_add);
665    x86::CodeGeneratorX86 codegen(graph);
666    SsaLivenessAnalysis liveness(*graph, &codegen);
667    liveness.Analyze();
668
669    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
670    register_allocator.AllocateRegisters();
671
672    // Sanity check that in normal conditions, the registers are the same.
673    ASSERT_EQ(first_add->GetLiveInterval()->GetRegister(), 1);
674    ASSERT_EQ(second_add->GetLiveInterval()->GetRegister(), 1);
675  }
676
677  {
678    HGraph* graph = BuildTwoAdds(&allocator, &first_add, &second_add);
679    x86::CodeGeneratorX86 codegen(graph);
680    SsaLivenessAnalysis liveness(*graph, &codegen);
681    liveness.Analyze();
682
683    // check that both adds get the same register.
684    first_add->InputAt(0)->GetLocations()->SetOut(Location::RegisterLocation(2));
685    ASSERT_EQ(first_add->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
686    ASSERT_EQ(second_add->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
687
688    RegisterAllocator register_allocator(&allocator, &codegen, liveness);
689    register_allocator.AllocateRegisters();
690
691    ASSERT_EQ(first_add->GetLiveInterval()->GetRegister(), 2);
692    ASSERT_EQ(second_add->GetLiveInterval()->GetRegister(), 2);
693  }
694}
695
696}  // namespace art
697