register_allocator_test.cc revision 8a16d97fb8f031822b206e65f9109a071da40563 
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() + 1);
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}  // namespace art
396