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