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