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 namespace art { 31 32 class LiveRangesTest : public CommonCompilerTest {}; 33 34 static 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 44 TEST_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 82 TEST_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 130 TEST_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 203 TEST_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 283 TEST_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 358 TEST_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
