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 "prepare_for_register_allocation.h"
28#include "ssa_liveness_analysis.h"
29
30#include "gtest/gtest.h"
31
32namespace art {
33
34static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) {
35  HGraph* graph = CreateGraph(allocator);
36  HGraphBuilder builder(graph);
37  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
38  builder.BuildGraph(*item);
39  // Suspend checks implementation may change in the future, and this test relies
40  // on how instructions are ordered.
41  RemoveSuspendChecks(graph);
42  graph->TryBuildingSsa();
43  // `Inline` conditions into ifs.
44  PrepareForRegisterAllocation(graph).Run();
45  return graph;
46}
47
48TEST(LiveRangesTest, CFG1) {
49  /*
50   * Test the following snippet:
51   *  return 0;
52   *
53   * Which becomes the following graph (numbered by lifetime position):
54   *       2: constant0
55   *       4: goto
56   *           |
57   *       8: return
58   *           |
59   *       12: exit
60   */
61  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
62    Instruction::CONST_4 | 0 | 0,
63    Instruction::RETURN);
64
65  ArenaPool pool;
66  ArenaAllocator allocator(&pool);
67  HGraph* graph = BuildGraph(data, &allocator);
68
69  std::unique_ptr<const X86InstructionSetFeatures> features_x86(
70      X86InstructionSetFeatures::FromCppDefines());
71  x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
72  SsaLivenessAnalysis liveness(graph, &codegen);
73  liveness.Analyze();
74
75  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
76  LiveRange* range = interval->GetFirstRange();
77  ASSERT_EQ(2u, range->GetStart());
78  // Last use is the return instruction.
79  ASSERT_EQ(8u, range->GetEnd());
80  HBasicBlock* block = graph->GetBlocks().Get(1);
81  ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
82  ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition());
83  ASSERT_TRUE(range->GetNext() == nullptr);
84}
85
86TEST(LiveRangesTest, CFG2) {
87  /*
88   * Test the following snippet:
89   *  var a = 0;
90   *  if (0 == 0) {
91   *  } else {
92   *  }
93   *  return a;
94   *
95   * Which becomes the following graph (numbered by lifetime position):
96   *       2: constant0
97   *       4: goto
98   *           |
99   *       8: equal
100   *       10: if
101   *       /       \
102   *   14: goto   18: goto
103   *       \       /
104   *       22: return
105   *         |
106   *       26: exit
107   */
108  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
109    Instruction::CONST_4 | 0 | 0,
110    Instruction::IF_EQ, 3,
111    Instruction::GOTO | 0x100,
112    Instruction::RETURN | 0 << 8);
113
114  ArenaPool pool;
115  ArenaAllocator allocator(&pool);
116  HGraph* graph = BuildGraph(data, &allocator);
117  std::unique_ptr<const X86InstructionSetFeatures> features_x86(
118      X86InstructionSetFeatures::FromCppDefines());
119  x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
120  SsaLivenessAnalysis liveness(graph, &codegen);
121  liveness.Analyze();
122
123  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
124  LiveRange* range = interval->GetFirstRange();
125  ASSERT_EQ(2u, range->GetStart());
126  // Last use is the return instruction.
127  ASSERT_EQ(22u, range->GetEnd());
128  HBasicBlock* block = graph->GetBlocks().Get(3);
129  ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
130  ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition());
131  ASSERT_TRUE(range->GetNext() == nullptr);
132}
133
134TEST(LiveRangesTest, CFG3) {
135  /*
136   * Test the following snippet:
137   *  var a = 0;
138   *  if (0 == 0) {
139   *  } else {
140   *    a = 4;
141   *  }
142   *  return a;
143   *
144   * Which becomes the following graph (numbered by lifetime position):
145   *       2: constant0
146   *       4: constant4
147   *       6: goto
148   *           |
149   *       10: equal
150   *       12: if
151   *       /       \
152   *   16: goto   20: goto
153   *       \       /
154   *       22: phi
155   *       24: return
156   *         |
157   *       28: exit
158   */
159  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
160    Instruction::CONST_4 | 0 | 0,
161    Instruction::IF_EQ, 3,
162    Instruction::CONST_4 | 4 << 12 | 0,
163    Instruction::RETURN | 0 << 8);
164
165  ArenaPool pool;
166  ArenaAllocator allocator(&pool);
167  HGraph* graph = BuildGraph(data, &allocator);
168  std::unique_ptr<const X86InstructionSetFeatures> features_x86(
169      X86InstructionSetFeatures::FromCppDefines());
170  x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
171  SsaLivenessAnalysis liveness(graph, &codegen);
172  liveness.Analyze();
173
174  // Test for the 4 constant.
175  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
176  LiveRange* range = interval->GetFirstRange();
177  ASSERT_EQ(4u, range->GetStart());
178  // Last use is the phi at the return block so instruction is live until
179  // the end of the then block.
180  ASSERT_EQ(18u, range->GetEnd());
181  ASSERT_TRUE(range->GetNext() == nullptr);
182
183  // Test for the 0 constant.
184  interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
185  // The then branch is a hole for this constant, therefore its interval has 2 ranges.
186  // First range starts from the definition and ends at the if block.
187  range = interval->GetFirstRange();
188  ASSERT_EQ(2u, range->GetStart());
189  // 14 is the end of the if block.
190  ASSERT_EQ(14u, range->GetEnd());
191  // Second range is the else block.
192  range = range->GetNext();
193  ASSERT_EQ(18u, range->GetStart());
194  // Last use is the phi at the return block.
195  ASSERT_EQ(22u, range->GetEnd());
196  ASSERT_TRUE(range->GetNext() == nullptr);
197
198  // Test for the phi.
199  interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
200  range = interval->GetFirstRange();
201  ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(2)->GetLifetimePosition());
202  ASSERT_EQ(22u, range->GetStart());
203  ASSERT_EQ(24u, range->GetEnd());
204  ASSERT_TRUE(range->GetNext() == nullptr);
205}
206
207TEST(LiveRangesTest, Loop1) {
208  /*
209   * Test the following snippet:
210   *  var a = 0;
211   *  while (a == a) {
212   *    a = 4;
213   *  }
214   *  return 5;
215   *
216   * Which becomes the following graph (numbered by lifetime position):
217   *       2: constant0
218   *       4: constant4
219   *       6: constant5
220   *       8: goto
221   *           |
222   *       12: goto
223   *           |
224   *       14: phi
225   *       16: equal
226   *       18: if +++++
227   *        |       \ +
228   *        |     22: goto
229   *        |
230   *       26: return
231   *         |
232   *       30: exit
233   */
234
235  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
236    Instruction::CONST_4 | 0 | 0,
237    Instruction::IF_EQ, 4,
238    Instruction::CONST_4 | 4 << 12 | 0,
239    Instruction::GOTO | 0xFD00,
240    Instruction::CONST_4 | 5 << 12 | 1 << 8,
241    Instruction::RETURN | 1 << 8);
242
243  ArenaPool pool;
244  ArenaAllocator allocator(&pool);
245  HGraph* graph = BuildGraph(data, &allocator);
246  RemoveSuspendChecks(graph);
247  std::unique_ptr<const X86InstructionSetFeatures> features_x86(
248      X86InstructionSetFeatures::FromCppDefines());
249  x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
250  SsaLivenessAnalysis liveness(graph, &codegen);
251  liveness.Analyze();
252
253  // Test for the 0 constant.
254  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
255  LiveRange* range = interval->GetFirstRange();
256  ASSERT_EQ(2u, range->GetStart());
257  // Last use is the loop phi so instruction is live until
258  // the end of the pre loop header.
259  ASSERT_EQ(14u, range->GetEnd());
260  ASSERT_TRUE(range->GetNext() == nullptr);
261
262  // Test for the 4 constant.
263  interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
264  range = interval->GetFirstRange();
265  // The instruction is live until the end of the loop.
266  ASSERT_EQ(4u, range->GetStart());
267  ASSERT_EQ(24u, range->GetEnd());
268  ASSERT_TRUE(range->GetNext() == nullptr);
269
270  // Test for the 5 constant.
271  interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
272  range = interval->GetFirstRange();
273  // The instruction is live until the return instruction after the loop.
274  ASSERT_EQ(6u, range->GetStart());
275  ASSERT_EQ(26u, range->GetEnd());
276  ASSERT_TRUE(range->GetNext() == nullptr);
277
278  // Test for the phi.
279  interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
280  range = interval->GetFirstRange();
281  // Instruction is consumed by the if.
282  ASSERT_EQ(14u, range->GetStart());
283  ASSERT_EQ(17u, range->GetEnd());
284  ASSERT_TRUE(range->GetNext() == nullptr);
285}
286
287TEST(LiveRangesTest, Loop2) {
288  /*
289   * Test the following snippet:
290   *  var a = 0;
291   *  while (a == a) {
292   *    a = a + a;
293   *  }
294   *  return a;
295   *
296   * Which becomes the following graph (numbered by lifetime position):
297   *       2: constant0
298   *       4: goto
299   *           |
300   *       8: goto
301   *           |
302   *       10: phi
303   *       12: equal
304   *       14: if +++++
305   *        |       \ +
306   *        |     18: suspend
307   *        |     20: add
308   *        |     22: goto
309   *        |
310   *       26: return
311   *         |
312   *       30: exit
313   *
314   * We want to make sure the phi at 10 has a lifetime hole after the add at 20.
315   */
316
317  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
318    Instruction::CONST_4 | 0 | 0,
319    Instruction::IF_EQ, 6,
320    Instruction::ADD_INT, 0, 0,
321    Instruction::GOTO | 0xFB00,
322    Instruction::RETURN | 0 << 8);
323
324  ArenaPool pool;
325  ArenaAllocator allocator(&pool);
326  HGraph* graph = BuildGraph(data, &allocator);
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  // Test for the 0 constant.
334  HIntConstant* constant = liveness.GetInstructionFromSsaIndex(0)->AsIntConstant();
335  LiveInterval* interval = constant->GetLiveInterval();
336  LiveRange* range = interval->GetFirstRange();
337  ASSERT_EQ(2u, range->GetStart());
338  // Last use is the loop phi so instruction is live until
339  // the end of the pre loop header.
340  ASSERT_EQ(10u, range->GetEnd());
341  ASSERT_TRUE(range->GetNext() == nullptr);
342
343  // Test for the loop phi.
344  HPhi* phi = liveness.GetInstructionFromSsaIndex(1)->AsPhi();
345  interval = phi->GetLiveInterval();
346  range = interval->GetFirstRange();
347  ASSERT_EQ(10u, range->GetStart());
348  ASSERT_EQ(21u, range->GetEnd());
349  range = range->GetNext();
350  ASSERT_TRUE(range != nullptr);
351  ASSERT_EQ(24u, range->GetStart());
352  ASSERT_EQ(26u, range->GetEnd());
353
354  // Test for the add instruction.
355  HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
356  interval = add->GetLiveInterval();
357  range = interval->GetFirstRange();
358  ASSERT_EQ(20u, range->GetStart());
359  ASSERT_EQ(24u, range->GetEnd());
360  ASSERT_TRUE(range->GetNext() == nullptr);
361}
362
363TEST(LiveRangesTest, CFG4) {
364  /*
365   * Test the following snippet:
366   *  var a = 0;
367   *  var b = 4;
368   *  if (a == a) {
369   *    a = b + a;
370   *  } else {
371   *    a = b + a
372   *  }
373   *  return b;
374   *
375   * Which becomes the following graph (numbered by lifetime position):
376   *       2: constant0
377   *       4: constant4
378   *       6: goto
379   *           |
380   *       10: equal
381   *       12: if
382   *       /       \
383   *   16: add    22: add
384   *   18: goto   24: goto
385   *       \       /
386   *       26: phi
387   *       28: return
388   *         |
389   *       32: exit
390   *
391   * We want to make sure the constant0 has a lifetime hole after the 16: add.
392   */
393  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
394    Instruction::CONST_4 | 0 | 0,
395    Instruction::CONST_4 | 4 << 12 | 1 << 8,
396    Instruction::IF_EQ, 5,
397    Instruction::ADD_INT, 1 << 8,
398    Instruction::GOTO | 0x300,
399    Instruction::ADD_INT, 1 << 8,
400    Instruction::RETURN);
401
402  ArenaPool pool;
403  ArenaAllocator allocator(&pool);
404  HGraph* graph = BuildGraph(data, &allocator);
405  std::unique_ptr<const X86InstructionSetFeatures> features_x86(
406      X86InstructionSetFeatures::FromCppDefines());
407  x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
408  SsaLivenessAnalysis liveness(graph, &codegen);
409  liveness.Analyze();
410
411  // Test for the 0 constant.
412  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
413  LiveRange* range = interval->GetFirstRange();
414  ASSERT_EQ(2u, range->GetStart());
415  ASSERT_EQ(17u, range->GetEnd());
416  range = range->GetNext();
417  ASSERT_TRUE(range != nullptr);
418  ASSERT_EQ(20u, range->GetStart());
419  ASSERT_EQ(23u, range->GetEnd());
420  ASSERT_TRUE(range->GetNext() == nullptr);
421
422  // Test for the 4 constant.
423  interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
424  range = interval->GetFirstRange();
425  ASSERT_EQ(4u, range->GetStart());
426  ASSERT_EQ(17u, range->GetEnd());
427  range = range->GetNext();
428  ASSERT_EQ(20u, range->GetStart());
429  ASSERT_EQ(23u, range->GetEnd());
430  ASSERT_TRUE(range->GetNext() == nullptr);
431
432  // Test for the first add.
433  HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
434  interval = add->GetLiveInterval();
435  range = interval->GetFirstRange();
436  ASSERT_EQ(16u, range->GetStart());
437  ASSERT_EQ(20u, range->GetEnd());
438  ASSERT_TRUE(range->GetNext() == nullptr);
439
440  // Test for the second add.
441  add = liveness.GetInstructionFromSsaIndex(3)->AsAdd();
442  interval = add->GetLiveInterval();
443  range = interval->GetFirstRange();
444  ASSERT_EQ(22u, range->GetStart());
445  ASSERT_EQ(26u, range->GetEnd());
446  ASSERT_TRUE(range->GetNext() == nullptr);
447
448  HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi();
449  ASSERT_TRUE(phi->GetUses().HasOnlyOneUse());
450  interval = phi->GetLiveInterval();
451  range = interval->GetFirstRange();
452  ASSERT_EQ(26u, range->GetStart());
453  ASSERT_EQ(28u, range->GetEnd());
454  ASSERT_TRUE(range->GetNext() == nullptr);
455}
456
457}  // namespace art
458