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