blob: 60f513ca48670f0d04fbf9e18d01eec824b3ca11 [file] [log] [blame]
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +01001/*
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
Mathieu Chartierb666f482015-02-18 14:33:14 -080017#include "base/arena_allocator.h"
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010018#include "builder.h"
Nicolas Geoffray31d76b42014-06-09 15:02:22 +010019#include "code_generator.h"
David Sehr9e734c72018-01-04 17:56:19 -080020#include "dex/dex_file.h"
21#include "dex/dex_instruction.h"
Calin Juravlecd6dffe2015-01-08 17:35:35 +000022#include "driver/compiler_options.h"
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010023#include "nodes.h"
24#include "optimizing_unit_test.h"
Nicolas Geoffray360231a2014-10-08 21:07:48 +010025#include "prepare_for_register_allocation.h"
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010026#include "ssa_liveness_analysis.h"
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010027
Alex Light68289a52015-12-15 17:30:30 -080028namespace art {
David Brazdild9510df2015-11-04 23:30:22 +000029
Vladimir Markoca6fff82017-10-03 14:49:14 +010030class LiveRangesTest : public OptimizingUnitTest {
31 public:
Mathieu Chartierfa3db3d2018-01-12 14:42:18 -080032 HGraph* BuildGraph(const std::vector<uint16_t>& data);
Vladimir Markoca6fff82017-10-03 14:49:14 +010033};
David Brazdil4833f5a2015-12-16 10:37:39 +000034
Mathieu Chartierfa3db3d2018-01-12 14:42:18 -080035HGraph* LiveRangesTest::BuildGraph(const std::vector<uint16_t>& data) {
Vladimir Markoca6fff82017-10-03 14:49:14 +010036 HGraph* graph = CreateCFG(data);
Nicolas Geoffrayfbc695f2014-09-15 15:33:30 +000037 // Suspend checks implementation may change in the future, and this test relies
38 // on how instructions are ordered.
39 RemoveSuspendChecks(graph);
Nicolas Geoffray360231a2014-10-08 21:07:48 +010040 // `Inline` conditions into ifs.
Nicolas Geoffray61ba8d22018-08-07 09:55:57 +010041 PrepareForRegisterAllocation(graph, *compiler_options_).Run();
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010042 return graph;
43}
44
David Brazdil4833f5a2015-12-16 10:37:39 +000045TEST_F(LiveRangesTest, CFG1) {
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010046 /*
47 * Test the following snippet:
48 * return 0;
49 *
50 * Which becomes the following graph (numbered by lifetime position):
51 * 2: constant0
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010052 * 4: goto
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010053 * |
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010054 * 8: return
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010055 * |
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010056 * 12: exit
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010057 */
Mathieu Chartierfa3db3d2018-01-12 14:42:18 -080058 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010059 Instruction::CONST_4 | 0 | 0,
60 Instruction::RETURN);
61
Vladimir Markoca6fff82017-10-03 14:49:14 +010062 HGraph* graph = BuildGraph(data);
Nicolas Geoffray31d76b42014-06-09 15:02:22 +010063
Vladimir Markoa0431112018-06-25 09:32:54 +010064 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
65 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010066 liveness.Analyze();
67
68 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010069 LiveRange* range = interval->GetFirstRange();
70 ASSERT_EQ(2u, range->GetStart());
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010071 // Last use is the return instruction.
Nicolas Geoffray8e3964b2014-10-17 11:06:38 +010072 ASSERT_EQ(8u, range->GetEnd());
Vladimir Markoec7802a2015-10-01 20:57:57 +010073 HBasicBlock* block = graph->GetBlocks()[1];
Roland Levillain476df552014-10-09 17:51:36 +010074 ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010075 ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition());
76 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010077}
78
David Brazdil4833f5a2015-12-16 10:37:39 +000079TEST_F(LiveRangesTest, CFG2) {
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010080 /*
81 * Test the following snippet:
82 * var a = 0;
83 * if (0 == 0) {
84 * } else {
85 * }
86 * return a;
87 *
88 * Which becomes the following graph (numbered by lifetime position):
89 * 2: constant0
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010090 * 4: goto
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010091 * |
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010092 * 8: equal
93 * 10: if
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010094 * / \
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010095 * 14: goto 18: goto
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010096 * \ /
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010097 * 22: return
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010098 * |
Nicolas Geoffraya7062e02014-05-22 12:50:17 +010099 * 26: exit
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100100 */
Mathieu Chartierfa3db3d2018-01-12 14:42:18 -0800101 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100102 Instruction::CONST_4 | 0 | 0,
103 Instruction::IF_EQ, 3,
104 Instruction::GOTO | 0x100,
105 Instruction::RETURN | 0 << 8);
106
Vladimir Markoca6fff82017-10-03 14:49:14 +0100107 HGraph* graph = BuildGraph(data);
Vladimir Markoa0431112018-06-25 09:32:54 +0100108 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
109 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100110 liveness.Analyze();
111
112 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100113 LiveRange* range = interval->GetFirstRange();
114 ASSERT_EQ(2u, range->GetStart());
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100115 // Last use is the return instruction.
Nicolas Geoffray8e3964b2014-10-17 11:06:38 +0100116 ASSERT_EQ(22u, range->GetEnd());
Vladimir Markoec7802a2015-10-01 20:57:57 +0100117 HBasicBlock* block = graph->GetBlocks()[3];
Roland Levillain476df552014-10-09 17:51:36 +0100118 ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100119 ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition());
120 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100121}
122
David Brazdil4833f5a2015-12-16 10:37:39 +0000123TEST_F(LiveRangesTest, CFG3) {
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100124 /*
125 * Test the following snippet:
126 * var a = 0;
127 * if (0 == 0) {
128 * } else {
129 * a = 4;
130 * }
131 * return a;
132 *
133 * Which becomes the following graph (numbered by lifetime position):
134 * 2: constant0
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100135 * 4: constant4
136 * 6: goto
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100137 * |
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100138 * 10: equal
139 * 12: if
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100140 * / \
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100141 * 16: goto 20: goto
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100142 * \ /
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100143 * 22: phi
144 * 24: return
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100145 * |
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100146 * 28: exit
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100147 */
Mathieu Chartierfa3db3d2018-01-12 14:42:18 -0800148 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100149 Instruction::CONST_4 | 0 | 0,
150 Instruction::IF_EQ, 3,
151 Instruction::CONST_4 | 4 << 12 | 0,
152 Instruction::RETURN | 0 << 8);
153
Vladimir Markoca6fff82017-10-03 14:49:14 +0100154 HGraph* graph = BuildGraph(data);
Vladimir Markoa0431112018-06-25 09:32:54 +0100155 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
156 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100157 liveness.Analyze();
158
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100159 // Test for the 4 constant.
160 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100161 LiveRange* range = interval->GetFirstRange();
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100162 ASSERT_EQ(4u, range->GetStart());
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100163 // Last use is the phi at the return block so instruction is live until
164 // the end of the then block.
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100165 ASSERT_EQ(18u, range->GetEnd());
166 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100167
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100168 // Test for the 0 constant.
169 interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100170 // The then branch is a hole for this constant, therefore its interval has 2 ranges.
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100171 // First range starts from the definition and ends at the if block.
172 range = interval->GetFirstRange();
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100173 ASSERT_EQ(2u, range->GetStart());
174 // 14 is the end of the if block.
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100175 ASSERT_EQ(14u, range->GetEnd());
176 // Second range is the else block.
177 range = range->GetNext();
178 ASSERT_EQ(18u, range->GetStart());
179 // Last use is the phi at the return block.
180 ASSERT_EQ(22u, range->GetEnd());
181 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100182
183 // Test for the phi.
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100184 interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100185 range = interval->GetFirstRange();
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100186 ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(2)->GetLifetimePosition());
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100187 ASSERT_EQ(22u, range->GetStart());
Nicolas Geoffray8e3964b2014-10-17 11:06:38 +0100188 ASSERT_EQ(24u, range->GetEnd());
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100189 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100190}
191
David Brazdil4833f5a2015-12-16 10:37:39 +0000192TEST_F(LiveRangesTest, Loop1) {
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100193 /*
194 * Test the following snippet:
195 * var a = 0;
196 * while (a == a) {
197 * a = 4;
198 * }
199 * return 5;
200 *
201 * Which becomes the following graph (numbered by lifetime position):
202 * 2: constant0
David Brazdildee58d62016-04-07 09:54:26 +0000203 * 4: constant5
204 * 6: constant4
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100205 * 8: goto
206 * |
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100207 * 12: goto
208 * |
209 * 14: phi
210 * 16: equal
211 * 18: if +++++
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100212 * | \ +
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100213 * | 22: goto
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100214 * |
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100215 * 26: return
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100216 * |
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100217 * 30: exit
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100218 */
219
Mathieu Chartierfa3db3d2018-01-12 14:42:18 -0800220 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100221 Instruction::CONST_4 | 0 | 0,
222 Instruction::IF_EQ, 4,
223 Instruction::CONST_4 | 4 << 12 | 0,
224 Instruction::GOTO | 0xFD00,
225 Instruction::CONST_4 | 5 << 12 | 1 << 8,
226 Instruction::RETURN | 1 << 8);
227
Vladimir Markoca6fff82017-10-03 14:49:14 +0100228 HGraph* graph = BuildGraph(data);
Nicolas Geoffray9ebc72c2014-09-25 16:33:42 +0100229 RemoveSuspendChecks(graph);
Vladimir Markoa0431112018-06-25 09:32:54 +0100230 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
231 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100232 liveness.Analyze();
233
234 // Test for the 0 constant.
David Brazdildee58d62016-04-07 09:54:26 +0000235 LiveInterval* interval = graph->GetIntConstant(0)->GetLiveInterval();
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100236 LiveRange* range = interval->GetFirstRange();
237 ASSERT_EQ(2u, range->GetStart());
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100238 // Last use is the loop phi so instruction is live until
239 // the end of the pre loop header.
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100240 ASSERT_EQ(14u, range->GetEnd());
241 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100242
243 // Test for the 4 constant.
David Brazdildee58d62016-04-07 09:54:26 +0000244 interval = graph->GetIntConstant(4)->GetLiveInterval();
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100245 range = interval->GetFirstRange();
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100246 // The instruction is live until the end of the loop.
David Brazdildee58d62016-04-07 09:54:26 +0000247 ASSERT_EQ(6u, range->GetStart());
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100248 ASSERT_EQ(24u, range->GetEnd());
249 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100250
251 // Test for the 5 constant.
David Brazdildee58d62016-04-07 09:54:26 +0000252 interval = graph->GetIntConstant(5)->GetLiveInterval();
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100253 range = interval->GetFirstRange();
254 // The instruction is live until the return instruction after the loop.
David Brazdildee58d62016-04-07 09:54:26 +0000255 ASSERT_EQ(4u, range->GetStart());
Nicolas Geoffray8e3964b2014-10-17 11:06:38 +0100256 ASSERT_EQ(26u, range->GetEnd());
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100257 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100258
259 // Test for the phi.
260 interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100261 range = interval->GetFirstRange();
David Brazdilb3e773e2016-01-26 11:28:37 +0000262 // Instruction is input of non-materialized Equal and hence live until If.
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100263 ASSERT_EQ(14u, range->GetStart());
David Brazdilb3e773e2016-01-26 11:28:37 +0000264 ASSERT_EQ(19u, range->GetEnd());
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100265 ASSERT_TRUE(range->GetNext() == nullptr);
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100266}
267
David Brazdil4833f5a2015-12-16 10:37:39 +0000268TEST_F(LiveRangesTest, Loop2) {
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100269 /*
270 * Test the following snippet:
271 * var a = 0;
272 * while (a == a) {
273 * a = a + a;
274 * }
275 * return a;
276 *
277 * Which becomes the following graph (numbered by lifetime position):
278 * 2: constant0
279 * 4: goto
280 * |
281 * 8: goto
282 * |
283 * 10: phi
284 * 12: equal
285 * 14: if +++++
286 * | \ +
David Brazdilbadd8262016-02-02 16:28:56 +0000287 * | 18: add
288 * | 20: goto
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100289 * |
David Brazdilbadd8262016-02-02 16:28:56 +0000290 * 24: return
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100291 * |
David Brazdilbadd8262016-02-02 16:28:56 +0000292 * 28: exit
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100293 *
294 * We want to make sure the phi at 10 has a lifetime hole after the add at 20.
295 */
296
Mathieu Chartierfa3db3d2018-01-12 14:42:18 -0800297 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100298 Instruction::CONST_4 | 0 | 0,
299 Instruction::IF_EQ, 6,
300 Instruction::ADD_INT, 0, 0,
301 Instruction::GOTO | 0xFB00,
302 Instruction::RETURN | 0 << 8);
303
Vladimir Markoca6fff82017-10-03 14:49:14 +0100304 HGraph* graph = BuildGraph(data);
Vladimir Markoa0431112018-06-25 09:32:54 +0100305 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
306 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100307 liveness.Analyze();
308
309 // Test for the 0 constant.
310 HIntConstant* constant = liveness.GetInstructionFromSsaIndex(0)->AsIntConstant();
311 LiveInterval* interval = constant->GetLiveInterval();
312 LiveRange* range = interval->GetFirstRange();
313 ASSERT_EQ(2u, range->GetStart());
314 // Last use is the loop phi so instruction is live until
315 // the end of the pre loop header.
316 ASSERT_EQ(10u, range->GetEnd());
317 ASSERT_TRUE(range->GetNext() == nullptr);
318
319 // Test for the loop phi.
320 HPhi* phi = liveness.GetInstructionFromSsaIndex(1)->AsPhi();
321 interval = phi->GetLiveInterval();
322 range = interval->GetFirstRange();
323 ASSERT_EQ(10u, range->GetStart());
David Brazdilbadd8262016-02-02 16:28:56 +0000324 ASSERT_EQ(19u, range->GetEnd());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100325 range = range->GetNext();
326 ASSERT_TRUE(range != nullptr);
David Brazdilbadd8262016-02-02 16:28:56 +0000327 ASSERT_EQ(22u, range->GetStart());
328 ASSERT_EQ(24u, range->GetEnd());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100329
330 // Test for the add instruction.
331 HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
332 interval = add->GetLiveInterval();
333 range = interval->GetFirstRange();
David Brazdilbadd8262016-02-02 16:28:56 +0000334 ASSERT_EQ(18u, range->GetStart());
335 ASSERT_EQ(22u, range->GetEnd());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100336 ASSERT_TRUE(range->GetNext() == nullptr);
337}
338
David Brazdil4833f5a2015-12-16 10:37:39 +0000339TEST_F(LiveRangesTest, CFG4) {
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100340 /*
341 * Test the following snippet:
342 * var a = 0;
343 * var b = 4;
344 * if (a == a) {
345 * a = b + a;
346 * } else {
347 * a = b + a
348 * }
349 * return b;
350 *
351 * Which becomes the following graph (numbered by lifetime position):
352 * 2: constant0
353 * 4: constant4
354 * 6: goto
355 * |
356 * 10: equal
357 * 12: if
358 * / \
359 * 16: add 22: add
360 * 18: goto 24: goto
361 * \ /
362 * 26: phi
363 * 28: return
364 * |
365 * 32: exit
366 *
367 * We want to make sure the constant0 has a lifetime hole after the 16: add.
368 */
Mathieu Chartierfa3db3d2018-01-12 14:42:18 -0800369 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100370 Instruction::CONST_4 | 0 | 0,
371 Instruction::CONST_4 | 4 << 12 | 1 << 8,
372 Instruction::IF_EQ, 5,
373 Instruction::ADD_INT, 1 << 8,
374 Instruction::GOTO | 0x300,
375 Instruction::ADD_INT, 1 << 8,
Nicolas Geoffraya3c00e52014-11-25 11:18:37 +0000376 Instruction::RETURN);
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100377
Vladimir Markoca6fff82017-10-03 14:49:14 +0100378 HGraph* graph = BuildGraph(data);
Vladimir Markoa0431112018-06-25 09:32:54 +0100379 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
380 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100381 liveness.Analyze();
382
383 // Test for the 0 constant.
384 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
385 LiveRange* range = interval->GetFirstRange();
386 ASSERT_EQ(2u, range->GetStart());
Mark Mendell09b84632015-02-13 17:48:38 -0500387 ASSERT_EQ(17u, range->GetEnd());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100388 range = range->GetNext();
389 ASSERT_TRUE(range != nullptr);
390 ASSERT_EQ(20u, range->GetStart());
Mark Mendell09b84632015-02-13 17:48:38 -0500391 ASSERT_EQ(23u, range->GetEnd());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100392 ASSERT_TRUE(range->GetNext() == nullptr);
393
394 // Test for the 4 constant.
395 interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
396 range = interval->GetFirstRange();
397 ASSERT_EQ(4u, range->GetStart());
Nicolas Geoffraya3c00e52014-11-25 11:18:37 +0000398 ASSERT_EQ(17u, range->GetEnd());
399 range = range->GetNext();
400 ASSERT_EQ(20u, range->GetStart());
401 ASSERT_EQ(23u, range->GetEnd());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100402 ASSERT_TRUE(range->GetNext() == nullptr);
403
404 // Test for the first add.
405 HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
406 interval = add->GetLiveInterval();
407 range = interval->GetFirstRange();
408 ASSERT_EQ(16u, range->GetStart());
409 ASSERT_EQ(20u, range->GetEnd());
410 ASSERT_TRUE(range->GetNext() == nullptr);
411
412 // Test for the second add.
413 add = liveness.GetInstructionFromSsaIndex(3)->AsAdd();
414 interval = add->GetLiveInterval();
415 range = interval->GetFirstRange();
416 ASSERT_EQ(22u, range->GetStart());
417 ASSERT_EQ(26u, range->GetEnd());
418 ASSERT_TRUE(range->GetNext() == nullptr);
419
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100420 HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi();
Vladimir Marko46817b82016-03-29 12:21:58 +0100421 ASSERT_TRUE(phi->GetUses().HasExactlyOneElement());
Nicolas Geoffray8ddb00c2014-09-29 12:00:40 +0100422 interval = phi->GetLiveInterval();
423 range = interval->GetFirstRange();
424 ASSERT_EQ(26u, range->GetStart());
425 ASSERT_EQ(28u, range->GetEnd());
426 ASSERT_TRUE(range->GetNext() == nullptr);
427}
428
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100429} // namespace art