Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 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 | |
Mathieu Chartier | b666f48 | 2015-02-18 14:33:14 -0800 | [diff] [blame] | 17 | #include "base/arena_allocator.h" |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 18 | #include "builder.h" |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 19 | #include "code_generator.h" |
David Sehr | 9e734c7 | 2018-01-04 17:56:19 -0800 | [diff] [blame] | 20 | #include "dex/dex_file.h" |
| 21 | #include "dex/dex_instruction.h" |
Calin Juravle | cd6dffe | 2015-01-08 17:35:35 +0000 | [diff] [blame] | 22 | #include "driver/compiler_options.h" |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 23 | #include "nodes.h" |
| 24 | #include "optimizing_unit_test.h" |
Nicolas Geoffray | 360231a | 2014-10-08 21:07:48 +0100 | [diff] [blame] | 25 | #include "prepare_for_register_allocation.h" |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 26 | #include "ssa_liveness_analysis.h" |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 27 | |
Alex Light | 68289a5 | 2015-12-15 17:30:30 -0800 | [diff] [blame] | 28 | namespace art { |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 29 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 30 | class LiveRangesTest : public OptimizingUnitTest { |
| 31 | public: |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 32 | HGraph* BuildGraph(const std::vector<uint16_t>& data); |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 33 | }; |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 34 | |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 35 | HGraph* LiveRangesTest::BuildGraph(const std::vector<uint16_t>& data) { |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 36 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | fbc695f | 2014-09-15 15:33:30 +0000 | [diff] [blame] | 37 | // Suspend checks implementation may change in the future, and this test relies |
| 38 | // on how instructions are ordered. |
| 39 | RemoveSuspendChecks(graph); |
Nicolas Geoffray | 360231a | 2014-10-08 21:07:48 +0100 | [diff] [blame] | 40 | // `Inline` conditions into ifs. |
Nicolas Geoffray | 61ba8d2 | 2018-08-07 09:55:57 +0100 | [diff] [blame] | 41 | PrepareForRegisterAllocation(graph, *compiler_options_).Run(); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 42 | return graph; |
| 43 | } |
| 44 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 45 | TEST_F(LiveRangesTest, CFG1) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 46 | /* |
| 47 | * Test the following snippet: |
| 48 | * return 0; |
| 49 | * |
| 50 | * Which becomes the following graph (numbered by lifetime position): |
| 51 | * 2: constant0 |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 52 | * 4: goto |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 53 | * | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 54 | * 8: return |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 55 | * | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 56 | * 12: exit |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 57 | */ |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 58 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 59 | Instruction::CONST_4 | 0 | 0, |
| 60 | Instruction::RETURN); |
| 61 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 62 | HGraph* graph = BuildGraph(data); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 63 | |
Vladimir Marko | a043111 | 2018-06-25 09:32:54 +0100 | [diff] [blame] | 64 | std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_); |
| 65 | SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 66 | liveness.Analyze(); |
| 67 | |
| 68 | LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 69 | LiveRange* range = interval->GetFirstRange(); |
| 70 | ASSERT_EQ(2u, range->GetStart()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 71 | // Last use is the return instruction. |
Nicolas Geoffray | 8e3964b | 2014-10-17 11:06:38 +0100 | [diff] [blame] | 72 | ASSERT_EQ(8u, range->GetEnd()); |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 73 | HBasicBlock* block = graph->GetBlocks()[1]; |
Roland Levillain | 476df55 | 2014-10-09 17:51:36 +0100 | [diff] [blame] | 74 | ASSERT_TRUE(block->GetLastInstruction()->IsReturn()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 75 | ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition()); |
| 76 | ASSERT_TRUE(range->GetNext() == nullptr); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 77 | } |
| 78 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 79 | TEST_F(LiveRangesTest, CFG2) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 80 | /* |
| 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 Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 90 | * 4: goto |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 91 | * | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 92 | * 8: equal |
| 93 | * 10: if |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 94 | * / \ |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 95 | * 14: goto 18: goto |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 96 | * \ / |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 97 | * 22: return |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 98 | * | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 99 | * 26: exit |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 100 | */ |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 101 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 102 | Instruction::CONST_4 | 0 | 0, |
| 103 | Instruction::IF_EQ, 3, |
| 104 | Instruction::GOTO | 0x100, |
| 105 | Instruction::RETURN | 0 << 8); |
| 106 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 107 | HGraph* graph = BuildGraph(data); |
Vladimir Marko | a043111 | 2018-06-25 09:32:54 +0100 | [diff] [blame] | 108 | std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_); |
| 109 | SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 110 | liveness.Analyze(); |
| 111 | |
| 112 | LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 113 | LiveRange* range = interval->GetFirstRange(); |
| 114 | ASSERT_EQ(2u, range->GetStart()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 115 | // Last use is the return instruction. |
Nicolas Geoffray | 8e3964b | 2014-10-17 11:06:38 +0100 | [diff] [blame] | 116 | ASSERT_EQ(22u, range->GetEnd()); |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 117 | HBasicBlock* block = graph->GetBlocks()[3]; |
Roland Levillain | 476df55 | 2014-10-09 17:51:36 +0100 | [diff] [blame] | 118 | ASSERT_TRUE(block->GetLastInstruction()->IsReturn()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 119 | ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition()); |
| 120 | ASSERT_TRUE(range->GetNext() == nullptr); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 121 | } |
| 122 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 123 | TEST_F(LiveRangesTest, CFG3) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 124 | /* |
| 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 Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 135 | * 4: constant4 |
| 136 | * 6: goto |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 137 | * | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 138 | * 10: equal |
| 139 | * 12: if |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 140 | * / \ |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 141 | * 16: goto 20: goto |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 142 | * \ / |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 143 | * 22: phi |
| 144 | * 24: return |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 145 | * | |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 146 | * 28: exit |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 147 | */ |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 148 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 149 | Instruction::CONST_4 | 0 | 0, |
| 150 | Instruction::IF_EQ, 3, |
| 151 | Instruction::CONST_4 | 4 << 12 | 0, |
| 152 | Instruction::RETURN | 0 << 8); |
| 153 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 154 | HGraph* graph = BuildGraph(data); |
Vladimir Marko | a043111 | 2018-06-25 09:32:54 +0100 | [diff] [blame] | 155 | std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_); |
| 156 | SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 157 | liveness.Analyze(); |
| 158 | |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 159 | // Test for the 4 constant. |
| 160 | LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 161 | LiveRange* range = interval->GetFirstRange(); |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 162 | ASSERT_EQ(4u, range->GetStart()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 163 | // Last use is the phi at the return block so instruction is live until |
| 164 | // the end of the then block. |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 165 | ASSERT_EQ(18u, range->GetEnd()); |
| 166 | ASSERT_TRUE(range->GetNext() == nullptr); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 167 | |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 168 | // Test for the 0 constant. |
| 169 | interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 170 | // The then branch is a hole for this constant, therefore its interval has 2 ranges. |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 171 | // First range starts from the definition and ends at the if block. |
| 172 | range = interval->GetFirstRange(); |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 173 | ASSERT_EQ(2u, range->GetStart()); |
| 174 | // 14 is the end of the if block. |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 175 | 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 Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 182 | |
| 183 | // Test for the phi. |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 184 | interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 185 | range = interval->GetFirstRange(); |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 186 | ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(2)->GetLifetimePosition()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 187 | ASSERT_EQ(22u, range->GetStart()); |
Nicolas Geoffray | 8e3964b | 2014-10-17 11:06:38 +0100 | [diff] [blame] | 188 | ASSERT_EQ(24u, range->GetEnd()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 189 | ASSERT_TRUE(range->GetNext() == nullptr); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 190 | } |
| 191 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 192 | TEST_F(LiveRangesTest, Loop1) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 193 | /* |
| 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 Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 203 | * 4: constant5 |
| 204 | * 6: constant4 |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 205 | * 8: goto |
| 206 | * | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 207 | * 12: goto |
| 208 | * | |
| 209 | * 14: phi |
| 210 | * 16: equal |
| 211 | * 18: if +++++ |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 212 | * | \ + |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 213 | * | 22: goto |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 214 | * | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 215 | * 26: return |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 216 | * | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 217 | * 30: exit |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 218 | */ |
| 219 | |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 220 | const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM( |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 221 | 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 Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 228 | HGraph* graph = BuildGraph(data); |
Nicolas Geoffray | 9ebc72c | 2014-09-25 16:33:42 +0100 | [diff] [blame] | 229 | RemoveSuspendChecks(graph); |
Vladimir Marko | a043111 | 2018-06-25 09:32:54 +0100 | [diff] [blame] | 230 | std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_); |
| 231 | SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 232 | liveness.Analyze(); |
| 233 | |
| 234 | // Test for the 0 constant. |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 235 | LiveInterval* interval = graph->GetIntConstant(0)->GetLiveInterval(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 236 | LiveRange* range = interval->GetFirstRange(); |
| 237 | ASSERT_EQ(2u, range->GetStart()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 238 | // Last use is the loop phi so instruction is live until |
| 239 | // the end of the pre loop header. |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 240 | ASSERT_EQ(14u, range->GetEnd()); |
| 241 | ASSERT_TRUE(range->GetNext() == nullptr); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 242 | |
| 243 | // Test for the 4 constant. |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 244 | interval = graph->GetIntConstant(4)->GetLiveInterval(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 245 | range = interval->GetFirstRange(); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 246 | // The instruction is live until the end of the loop. |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 247 | ASSERT_EQ(6u, range->GetStart()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 248 | ASSERT_EQ(24u, range->GetEnd()); |
| 249 | ASSERT_TRUE(range->GetNext() == nullptr); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 250 | |
| 251 | // Test for the 5 constant. |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 252 | interval = graph->GetIntConstant(5)->GetLiveInterval(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 253 | range = interval->GetFirstRange(); |
| 254 | // The instruction is live until the return instruction after the loop. |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 255 | ASSERT_EQ(4u, range->GetStart()); |
Nicolas Geoffray | 8e3964b | 2014-10-17 11:06:38 +0100 | [diff] [blame] | 256 | ASSERT_EQ(26u, range->GetEnd()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 257 | ASSERT_TRUE(range->GetNext() == nullptr); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 258 | |
| 259 | // Test for the phi. |
| 260 | interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 261 | range = interval->GetFirstRange(); |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 262 | // Instruction is input of non-materialized Equal and hence live until If. |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 263 | ASSERT_EQ(14u, range->GetStart()); |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 264 | ASSERT_EQ(19u, range->GetEnd()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 265 | ASSERT_TRUE(range->GetNext() == nullptr); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 266 | } |
| 267 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 268 | TEST_F(LiveRangesTest, Loop2) { |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 269 | /* |
| 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 Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 287 | * | 18: add |
| 288 | * | 20: goto |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 289 | * | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 290 | * 24: return |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 291 | * | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 292 | * 28: exit |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 293 | * |
| 294 | * We want to make sure the phi at 10 has a lifetime hole after the add at 20. |
| 295 | */ |
| 296 | |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 297 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 298 | 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 Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 304 | HGraph* graph = BuildGraph(data); |
Vladimir Marko | a043111 | 2018-06-25 09:32:54 +0100 | [diff] [blame] | 305 | std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_); |
| 306 | SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 307 | 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 Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 324 | ASSERT_EQ(19u, range->GetEnd()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 325 | range = range->GetNext(); |
| 326 | ASSERT_TRUE(range != nullptr); |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 327 | ASSERT_EQ(22u, range->GetStart()); |
| 328 | ASSERT_EQ(24u, range->GetEnd()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 329 | |
| 330 | // Test for the add instruction. |
| 331 | HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd(); |
| 332 | interval = add->GetLiveInterval(); |
| 333 | range = interval->GetFirstRange(); |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 334 | ASSERT_EQ(18u, range->GetStart()); |
| 335 | ASSERT_EQ(22u, range->GetEnd()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 336 | ASSERT_TRUE(range->GetNext() == nullptr); |
| 337 | } |
| 338 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 339 | TEST_F(LiveRangesTest, CFG4) { |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 340 | /* |
| 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 Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 369 | const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM( |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 370 | 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 Geoffray | a3c00e5 | 2014-11-25 11:18:37 +0000 | [diff] [blame] | 376 | Instruction::RETURN); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 377 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 378 | HGraph* graph = BuildGraph(data); |
Vladimir Marko | a043111 | 2018-06-25 09:32:54 +0100 | [diff] [blame] | 379 | std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_); |
| 380 | SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 381 | 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 Mendell | 09b8463 | 2015-02-13 17:48:38 -0500 | [diff] [blame] | 387 | ASSERT_EQ(17u, range->GetEnd()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 388 | range = range->GetNext(); |
| 389 | ASSERT_TRUE(range != nullptr); |
| 390 | ASSERT_EQ(20u, range->GetStart()); |
Mark Mendell | 09b8463 | 2015-02-13 17:48:38 -0500 | [diff] [blame] | 391 | ASSERT_EQ(23u, range->GetEnd()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 392 | 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 Geoffray | a3c00e5 | 2014-11-25 11:18:37 +0000 | [diff] [blame] | 398 | ASSERT_EQ(17u, range->GetEnd()); |
| 399 | range = range->GetNext(); |
| 400 | ASSERT_EQ(20u, range->GetStart()); |
| 401 | ASSERT_EQ(23u, range->GetEnd()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 402 | 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 Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 420 | HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi(); |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 421 | ASSERT_TRUE(phi->GetUses().HasExactlyOneElement()); |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 422 | 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 Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 429 | } // namespace art |