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 "bounds_check_elimination.h" 18 19 #include "base/arena_allocator.h" 20 #include "builder.h" 21 #include "gvn.h" 22 #include "induction_var_analysis.h" 23 #include "instruction_simplifier.h" 24 #include "nodes.h" 25 #include "optimizing_unit_test.h" 26 #include "side_effects_analysis.h" 27 28 #include "gtest/gtest.h" 29 30 namespace art { 31 32 /** 33 * Fixture class for the BoundsCheckElimination tests. 34 */ 35 class BoundsCheckEliminationTest : public OptimizingUnitTest { 36 public: 37 BoundsCheckEliminationTest() : graph_(CreateGraph()) { 38 graph_->SetHasBoundsChecks(true); 39 } 40 41 ~BoundsCheckEliminationTest() { } 42 43 void RunBCE() { 44 graph_->BuildDominatorTree(); 45 46 InstructionSimplifier(graph_, /* codegen= */ nullptr).Run(); 47 48 SideEffectsAnalysis side_effects(graph_); 49 side_effects.Run(); 50 51 GVNOptimization(graph_, side_effects).Run(); 52 53 HInductionVarAnalysis induction(graph_); 54 induction.Run(); 55 56 BoundsCheckElimination(graph_, side_effects, &induction).Run(); 57 } 58 59 HGraph* graph_; 60 }; 61 62 63 // if (i < 0) { array[i] = 1; // Can't eliminate. } 64 // else if (i >= array.length) { array[i] = 1; // Can't eliminate. } 65 // else { array[i] = 1; // Can eliminate. } 66 TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) { 67 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 68 graph_->AddBlock(entry); 69 graph_->SetEntryBlock(entry); 70 HInstruction* parameter1 = new (GetAllocator()) HParameterValue( 71 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); // array 72 HInstruction* parameter2 = new (GetAllocator()) HParameterValue( 73 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32); // i 74 entry->AddInstruction(parameter1); 75 entry->AddInstruction(parameter2); 76 77 HInstruction* constant_1 = graph_->GetIntConstant(1); 78 HInstruction* constant_0 = graph_->GetIntConstant(0); 79 80 HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_); 81 graph_->AddBlock(block1); 82 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(parameter2, constant_0); 83 HIf* if_inst = new (GetAllocator()) HIf(cmp); 84 block1->AddInstruction(cmp); 85 block1->AddInstruction(if_inst); 86 entry->AddSuccessor(block1); 87 88 HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_); 89 graph_->AddBlock(block2); 90 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter1, 0); 91 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0); 92 HBoundsCheck* bounds_check2 = new (GetAllocator()) 93 HBoundsCheck(parameter2, array_length, 0); 94 HArraySet* array_set = new (GetAllocator()) HArraySet( 95 null_check, bounds_check2, constant_1, DataType::Type::kInt32, 0); 96 block2->AddInstruction(null_check); 97 block2->AddInstruction(array_length); 98 block2->AddInstruction(bounds_check2); 99 block2->AddInstruction(array_set); 100 101 HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_); 102 graph_->AddBlock(block3); 103 null_check = new (GetAllocator()) HNullCheck(parameter1, 0); 104 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 105 cmp = new (GetAllocator()) HLessThan(parameter2, array_length); 106 if_inst = new (GetAllocator()) HIf(cmp); 107 block3->AddInstruction(null_check); 108 block3->AddInstruction(array_length); 109 block3->AddInstruction(cmp); 110 block3->AddInstruction(if_inst); 111 112 HBasicBlock* block4 = new (GetAllocator()) HBasicBlock(graph_); 113 graph_->AddBlock(block4); 114 null_check = new (GetAllocator()) HNullCheck(parameter1, 0); 115 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 116 HBoundsCheck* bounds_check4 = new (GetAllocator()) 117 HBoundsCheck(parameter2, array_length, 0); 118 array_set = new (GetAllocator()) HArraySet( 119 null_check, bounds_check4, constant_1, DataType::Type::kInt32, 0); 120 block4->AddInstruction(null_check); 121 block4->AddInstruction(array_length); 122 block4->AddInstruction(bounds_check4); 123 block4->AddInstruction(array_set); 124 125 HBasicBlock* block5 = new (GetAllocator()) HBasicBlock(graph_); 126 graph_->AddBlock(block5); 127 null_check = new (GetAllocator()) HNullCheck(parameter1, 0); 128 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 129 HBoundsCheck* bounds_check5 = new (GetAllocator()) 130 HBoundsCheck(parameter2, array_length, 0); 131 array_set = new (GetAllocator()) HArraySet( 132 null_check, bounds_check5, constant_1, DataType::Type::kInt32, 0); 133 block5->AddInstruction(null_check); 134 block5->AddInstruction(array_length); 135 block5->AddInstruction(bounds_check5); 136 block5->AddInstruction(array_set); 137 138 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_); 139 graph_->AddBlock(exit); 140 block2->AddSuccessor(exit); 141 block4->AddSuccessor(exit); 142 block5->AddSuccessor(exit); 143 exit->AddInstruction(new (GetAllocator()) HExit()); 144 145 block1->AddSuccessor(block3); // True successor 146 block1->AddSuccessor(block2); // False successor 147 148 block3->AddSuccessor(block5); // True successor 149 block3->AddSuccessor(block4); // False successor 150 151 RunBCE(); 152 153 ASSERT_FALSE(IsRemoved(bounds_check2)); 154 ASSERT_FALSE(IsRemoved(bounds_check4)); 155 ASSERT_TRUE(IsRemoved(bounds_check5)); 156 } 157 158 // if (i > 0) { 159 // // Positive number plus MAX_INT will overflow and be negative. 160 // int j = i + Integer.MAX_VALUE; 161 // if (j < array.length) array[j] = 1; // Can't eliminate. 162 // } 163 TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) { 164 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 165 graph_->AddBlock(entry); 166 graph_->SetEntryBlock(entry); 167 HInstruction* parameter1 = new (GetAllocator()) HParameterValue( 168 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); // array 169 HInstruction* parameter2 = new (GetAllocator()) HParameterValue( 170 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32); // i 171 entry->AddInstruction(parameter1); 172 entry->AddInstruction(parameter2); 173 174 HInstruction* constant_1 = graph_->GetIntConstant(1); 175 HInstruction* constant_0 = graph_->GetIntConstant(0); 176 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX); 177 178 HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_); 179 graph_->AddBlock(block1); 180 HInstruction* cmp = new (GetAllocator()) HLessThanOrEqual(parameter2, constant_0); 181 HIf* if_inst = new (GetAllocator()) HIf(cmp); 182 block1->AddInstruction(cmp); 183 block1->AddInstruction(if_inst); 184 entry->AddSuccessor(block1); 185 186 HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_); 187 graph_->AddBlock(block2); 188 HInstruction* add = 189 new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter2, constant_max_int); 190 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter1, 0); 191 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0); 192 HInstruction* cmp2 = new (GetAllocator()) HGreaterThanOrEqual(add, array_length); 193 if_inst = new (GetAllocator()) HIf(cmp2); 194 block2->AddInstruction(add); 195 block2->AddInstruction(null_check); 196 block2->AddInstruction(array_length); 197 block2->AddInstruction(cmp2); 198 block2->AddInstruction(if_inst); 199 200 HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_); 201 graph_->AddBlock(block3); 202 HBoundsCheck* bounds_check = new (GetAllocator()) 203 HBoundsCheck(add, array_length, 0); 204 HArraySet* array_set = new (GetAllocator()) HArraySet( 205 null_check, bounds_check, constant_1, DataType::Type::kInt32, 0); 206 block3->AddInstruction(bounds_check); 207 block3->AddInstruction(array_set); 208 209 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_); 210 graph_->AddBlock(exit); 211 exit->AddInstruction(new (GetAllocator()) HExit()); 212 block1->AddSuccessor(exit); // true successor 213 block1->AddSuccessor(block2); // false successor 214 block2->AddSuccessor(exit); // true successor 215 block2->AddSuccessor(block3); // false successor 216 block3->AddSuccessor(exit); 217 218 RunBCE(); 219 220 ASSERT_FALSE(IsRemoved(bounds_check)); 221 } 222 223 // if (i < array.length) { 224 // int j = i - Integer.MAX_VALUE; 225 // j = j - Integer.MAX_VALUE; // j is (i+2) after subtracting MAX_INT twice 226 // if (j > 0) array[j] = 1; // Can't eliminate. 227 // } 228 TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) { 229 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 230 graph_->AddBlock(entry); 231 graph_->SetEntryBlock(entry); 232 HInstruction* parameter1 = new (GetAllocator()) HParameterValue( 233 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); // array 234 HInstruction* parameter2 = new (GetAllocator()) HParameterValue( 235 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32); // i 236 entry->AddInstruction(parameter1); 237 entry->AddInstruction(parameter2); 238 239 HInstruction* constant_1 = graph_->GetIntConstant(1); 240 HInstruction* constant_0 = graph_->GetIntConstant(0); 241 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX); 242 243 HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_); 244 graph_->AddBlock(block1); 245 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter1, 0); 246 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0); 247 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(parameter2, array_length); 248 HIf* if_inst = new (GetAllocator()) HIf(cmp); 249 block1->AddInstruction(null_check); 250 block1->AddInstruction(array_length); 251 block1->AddInstruction(cmp); 252 block1->AddInstruction(if_inst); 253 entry->AddSuccessor(block1); 254 255 HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_); 256 graph_->AddBlock(block2); 257 HInstruction* sub1 = 258 new (GetAllocator()) HSub(DataType::Type::kInt32, parameter2, constant_max_int); 259 HInstruction* sub2 = new (GetAllocator()) HSub(DataType::Type::kInt32, sub1, constant_max_int); 260 HInstruction* cmp2 = new (GetAllocator()) HLessThanOrEqual(sub2, constant_0); 261 if_inst = new (GetAllocator()) HIf(cmp2); 262 block2->AddInstruction(sub1); 263 block2->AddInstruction(sub2); 264 block2->AddInstruction(cmp2); 265 block2->AddInstruction(if_inst); 266 267 HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_); 268 graph_->AddBlock(block3); 269 HBoundsCheck* bounds_check = new (GetAllocator()) 270 HBoundsCheck(sub2, array_length, 0); 271 HArraySet* array_set = new (GetAllocator()) HArraySet( 272 null_check, bounds_check, constant_1, DataType::Type::kInt32, 0); 273 block3->AddInstruction(bounds_check); 274 block3->AddInstruction(array_set); 275 276 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_); 277 graph_->AddBlock(exit); 278 exit->AddInstruction(new (GetAllocator()) HExit()); 279 block1->AddSuccessor(exit); // true successor 280 block1->AddSuccessor(block2); // false successor 281 block2->AddSuccessor(exit); // true successor 282 block2->AddSuccessor(block3); // false successor 283 block3->AddSuccessor(exit); 284 285 RunBCE(); 286 287 ASSERT_FALSE(IsRemoved(bounds_check)); 288 } 289 290 // array[6] = 1; // Can't eliminate. 291 // array[5] = 1; // Can eliminate. 292 // array[4] = 1; // Can eliminate. 293 TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) { 294 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 295 graph_->AddBlock(entry); 296 graph_->SetEntryBlock(entry); 297 HInstruction* parameter = new (GetAllocator()) HParameterValue( 298 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 299 entry->AddInstruction(parameter); 300 301 HInstruction* constant_5 = graph_->GetIntConstant(5); 302 HInstruction* constant_4 = graph_->GetIntConstant(4); 303 HInstruction* constant_6 = graph_->GetIntConstant(6); 304 HInstruction* constant_1 = graph_->GetIntConstant(1); 305 306 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_); 307 graph_->AddBlock(block); 308 entry->AddSuccessor(block); 309 310 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter, 0); 311 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0); 312 HBoundsCheck* bounds_check6 = new (GetAllocator()) 313 HBoundsCheck(constant_6, array_length, 0); 314 HInstruction* array_set = new (GetAllocator()) HArraySet( 315 null_check, bounds_check6, constant_1, DataType::Type::kInt32, 0); 316 block->AddInstruction(null_check); 317 block->AddInstruction(array_length); 318 block->AddInstruction(bounds_check6); 319 block->AddInstruction(array_set); 320 321 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 322 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 323 HBoundsCheck* bounds_check5 = new (GetAllocator()) 324 HBoundsCheck(constant_5, array_length, 0); 325 array_set = new (GetAllocator()) HArraySet( 326 null_check, bounds_check5, constant_1, DataType::Type::kInt32, 0); 327 block->AddInstruction(null_check); 328 block->AddInstruction(array_length); 329 block->AddInstruction(bounds_check5); 330 block->AddInstruction(array_set); 331 332 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 333 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 334 HBoundsCheck* bounds_check4 = new (GetAllocator()) 335 HBoundsCheck(constant_4, array_length, 0); 336 array_set = new (GetAllocator()) HArraySet( 337 null_check, bounds_check4, constant_1, DataType::Type::kInt32, 0); 338 block->AddInstruction(null_check); 339 block->AddInstruction(array_length); 340 block->AddInstruction(bounds_check4); 341 block->AddInstruction(array_set); 342 343 block->AddInstruction(new (GetAllocator()) HGoto()); 344 345 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_); 346 graph_->AddBlock(exit); 347 block->AddSuccessor(exit); 348 exit->AddInstruction(new (GetAllocator()) HExit()); 349 350 RunBCE(); 351 352 ASSERT_FALSE(IsRemoved(bounds_check6)); 353 ASSERT_TRUE(IsRemoved(bounds_check5)); 354 ASSERT_TRUE(IsRemoved(bounds_check4)); 355 } 356 357 // for (int i=initial; i<array.length; i+=increment) { array[i] = 10; } 358 static HInstruction* BuildSSAGraph1(HGraph* graph, 359 ArenaAllocator* allocator, 360 int initial, 361 int increment, 362 IfCondition cond = kCondGE) { 363 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 364 graph->AddBlock(entry); 365 graph->SetEntryBlock(entry); 366 HInstruction* parameter = new (allocator) HParameterValue( 367 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 368 entry->AddInstruction(parameter); 369 370 HInstruction* constant_initial = graph->GetIntConstant(initial); 371 HInstruction* constant_increment = graph->GetIntConstant(increment); 372 HInstruction* constant_10 = graph->GetIntConstant(10); 373 374 HBasicBlock* block = new (allocator) HBasicBlock(graph); 375 graph->AddBlock(block); 376 entry->AddSuccessor(block); 377 block->AddInstruction(new (allocator) HGoto()); 378 379 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 380 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 381 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 382 383 graph->AddBlock(loop_header); 384 graph->AddBlock(loop_body); 385 graph->AddBlock(exit); 386 block->AddSuccessor(loop_header); 387 loop_header->AddSuccessor(exit); // true successor 388 loop_header->AddSuccessor(loop_body); // false successor 389 loop_body->AddSuccessor(loop_header); 390 391 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, DataType::Type::kInt32); 392 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 393 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 394 HInstruction* cmp = nullptr; 395 if (cond == kCondGE) { 396 cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 397 } else { 398 DCHECK(cond == kCondGT); 399 cmp = new (allocator) HGreaterThan(phi, array_length); 400 } 401 HInstruction* if_inst = new (allocator) HIf(cmp); 402 loop_header->AddPhi(phi); 403 loop_header->AddInstruction(null_check); 404 loop_header->AddInstruction(array_length); 405 loop_header->AddInstruction(cmp); 406 loop_header->AddInstruction(if_inst); 407 phi->AddInput(constant_initial); 408 409 null_check = new (allocator) HNullCheck(parameter, 0); 410 array_length = new (allocator) HArrayLength(null_check, 0); 411 HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 412 HInstruction* array_set = new (allocator) HArraySet( 413 null_check, bounds_check, constant_10, DataType::Type::kInt32, 0); 414 415 HInstruction* add = new (allocator) HAdd(DataType::Type::kInt32, phi, constant_increment); 416 loop_body->AddInstruction(null_check); 417 loop_body->AddInstruction(array_length); 418 loop_body->AddInstruction(bounds_check); 419 loop_body->AddInstruction(array_set); 420 loop_body->AddInstruction(add); 421 loop_body->AddInstruction(new (allocator) HGoto()); 422 phi->AddInput(add); 423 424 exit->AddInstruction(new (allocator) HExit()); 425 426 return bounds_check; 427 } 428 429 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1a) { 430 // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. } 431 HInstruction* bounds_check = BuildSSAGraph1(graph_, GetAllocator(), 0, 1); 432 RunBCE(); 433 ASSERT_TRUE(IsRemoved(bounds_check)); 434 } 435 436 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1b) { 437 // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. } 438 HInstruction* bounds_check = BuildSSAGraph1(graph_, GetAllocator(), 1, 1); 439 RunBCE(); 440 ASSERT_TRUE(IsRemoved(bounds_check)); 441 } 442 443 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1c) { 444 // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. } 445 HInstruction* bounds_check = BuildSSAGraph1(graph_, GetAllocator(), -1, 1); 446 RunBCE(); 447 ASSERT_FALSE(IsRemoved(bounds_check)); 448 } 449 450 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1d) { 451 // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. } 452 HInstruction* bounds_check = BuildSSAGraph1(graph_, GetAllocator(), 0, 1, kCondGT); 453 RunBCE(); 454 ASSERT_FALSE(IsRemoved(bounds_check)); 455 } 456 457 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1e) { 458 // for (int i=0; i<array.length; i += 2) { 459 // array[i] = 10; // Can't eliminate due to overflow concern. } 460 HInstruction* bounds_check = BuildSSAGraph1(graph_, GetAllocator(), 0, 2); 461 RunBCE(); 462 ASSERT_FALSE(IsRemoved(bounds_check)); 463 } 464 465 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1f) { 466 // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. } 467 HInstruction* bounds_check = BuildSSAGraph1(graph_, GetAllocator(), 1, 2); 468 RunBCE(); 469 ASSERT_TRUE(IsRemoved(bounds_check)); 470 } 471 472 // for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; } 473 static HInstruction* BuildSSAGraph2(HGraph *graph, 474 ArenaAllocator* allocator, 475 int initial, 476 int increment = -1, 477 IfCondition cond = kCondLE) { 478 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 479 graph->AddBlock(entry); 480 graph->SetEntryBlock(entry); 481 HInstruction* parameter = new (allocator) HParameterValue( 482 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 483 entry->AddInstruction(parameter); 484 485 HInstruction* constant_initial = graph->GetIntConstant(initial); 486 HInstruction* constant_increment = graph->GetIntConstant(increment); 487 HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 488 HInstruction* constant_10 = graph->GetIntConstant(10); 489 490 HBasicBlock* block = new (allocator) HBasicBlock(graph); 491 graph->AddBlock(block); 492 entry->AddSuccessor(block); 493 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 494 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 495 block->AddInstruction(null_check); 496 block->AddInstruction(array_length); 497 block->AddInstruction(new (allocator) HGoto()); 498 499 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 500 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 501 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 502 503 graph->AddBlock(loop_header); 504 graph->AddBlock(loop_body); 505 graph->AddBlock(exit); 506 block->AddSuccessor(loop_header); 507 loop_header->AddSuccessor(exit); // true successor 508 loop_header->AddSuccessor(loop_body); // false successor 509 loop_body->AddSuccessor(loop_header); 510 511 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, DataType::Type::kInt32); 512 HInstruction* cmp = nullptr; 513 if (cond == kCondLE) { 514 cmp = new (allocator) HLessThanOrEqual(phi, constant_initial); 515 } else { 516 DCHECK(cond == kCondLT); 517 cmp = new (allocator) HLessThan(phi, constant_initial); 518 } 519 HInstruction* if_inst = new (allocator) HIf(cmp); 520 loop_header->AddPhi(phi); 521 loop_header->AddInstruction(cmp); 522 loop_header->AddInstruction(if_inst); 523 phi->AddInput(array_length); 524 525 HInstruction* add = new (allocator) HAdd(DataType::Type::kInt32, phi, constant_minus_1); 526 null_check = new (allocator) HNullCheck(parameter, 0); 527 array_length = new (allocator) HArrayLength(null_check, 0); 528 HInstruction* bounds_check = new (allocator) HBoundsCheck(add, array_length, 0); 529 HInstruction* array_set = new (allocator) HArraySet( 530 null_check, bounds_check, constant_10, DataType::Type::kInt32, 0); 531 HInstruction* add_phi = new (allocator) HAdd(DataType::Type::kInt32, phi, constant_increment); 532 loop_body->AddInstruction(add); 533 loop_body->AddInstruction(null_check); 534 loop_body->AddInstruction(array_length); 535 loop_body->AddInstruction(bounds_check); 536 loop_body->AddInstruction(array_set); 537 loop_body->AddInstruction(add_phi); 538 loop_body->AddInstruction(new (allocator) HGoto()); 539 phi->AddInput(add); 540 541 exit->AddInstruction(new (allocator) HExit()); 542 543 return bounds_check; 544 } 545 546 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2a) { 547 // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. } 548 HInstruction* bounds_check = BuildSSAGraph2(graph_, GetAllocator(), 0); 549 RunBCE(); 550 ASSERT_TRUE(IsRemoved(bounds_check)); 551 } 552 553 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2b) { 554 // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. } 555 HInstruction* bounds_check = BuildSSAGraph2(graph_, GetAllocator(), 1); 556 RunBCE(); 557 ASSERT_TRUE(IsRemoved(bounds_check)); 558 } 559 560 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2c) { 561 // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. } 562 HInstruction* bounds_check = BuildSSAGraph2(graph_, GetAllocator(), -1); 563 RunBCE(); 564 ASSERT_FALSE(IsRemoved(bounds_check)); 565 } 566 567 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2d) { 568 // for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. } 569 HInstruction* bounds_check = BuildSSAGraph2(graph_, GetAllocator(), 0, -1, kCondLT); 570 RunBCE(); 571 ASSERT_FALSE(IsRemoved(bounds_check)); 572 } 573 574 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2e) { 575 // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. } 576 HInstruction* bounds_check = BuildSSAGraph2(graph_, GetAllocator(), 0, -2); 577 RunBCE(); 578 ASSERT_TRUE(IsRemoved(bounds_check)); 579 } 580 581 // int[] array = new int[10]; 582 // for (int i=0; i<10; i+=increment) { array[i] = 10; } 583 static HInstruction* BuildSSAGraph3(HGraph* graph, 584 ArenaAllocator* allocator, 585 int initial, 586 int increment, 587 IfCondition cond) { 588 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 589 graph->AddBlock(entry); 590 graph->SetEntryBlock(entry); 591 592 HInstruction* constant_10 = graph->GetIntConstant(10); 593 HInstruction* constant_initial = graph->GetIntConstant(initial); 594 HInstruction* constant_increment = graph->GetIntConstant(increment); 595 596 HBasicBlock* block = new (allocator) HBasicBlock(graph); 597 graph->AddBlock(block); 598 entry->AddSuccessor(block); 599 // We pass a bogus constant for the class to avoid mocking one. 600 HInstruction* new_array = new (allocator) HNewArray( 601 /* cls= */ constant_10, 602 /* length= */ constant_10, 603 /* dex_pc= */ 0, 604 /* component_size_shift= */ 0); 605 block->AddInstruction(new_array); 606 block->AddInstruction(new (allocator) HGoto()); 607 608 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 609 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 610 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 611 612 graph->AddBlock(loop_header); 613 graph->AddBlock(loop_body); 614 graph->AddBlock(exit); 615 block->AddSuccessor(loop_header); 616 loop_header->AddSuccessor(exit); // true successor 617 loop_header->AddSuccessor(loop_body); // false successor 618 loop_body->AddSuccessor(loop_header); 619 620 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, DataType::Type::kInt32); 621 HInstruction* cmp = nullptr; 622 if (cond == kCondGE) { 623 cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10); 624 } else { 625 DCHECK(cond == kCondGT); 626 cmp = new (allocator) HGreaterThan(phi, constant_10); 627 } 628 HInstruction* if_inst = new (allocator) HIf(cmp); 629 loop_header->AddPhi(phi); 630 loop_header->AddInstruction(cmp); 631 loop_header->AddInstruction(if_inst); 632 phi->AddInput(constant_initial); 633 634 HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0); 635 HArrayLength* array_length = new (allocator) HArrayLength(null_check, 0); 636 HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 637 HInstruction* array_set = new (allocator) HArraySet( 638 null_check, bounds_check, constant_10, DataType::Type::kInt32, 0); 639 HInstruction* add = new (allocator) HAdd(DataType::Type::kInt32, phi, constant_increment); 640 loop_body->AddInstruction(null_check); 641 loop_body->AddInstruction(array_length); 642 loop_body->AddInstruction(bounds_check); 643 loop_body->AddInstruction(array_set); 644 loop_body->AddInstruction(add); 645 loop_body->AddInstruction(new (allocator) HGoto()); 646 phi->AddInput(add); 647 648 exit->AddInstruction(new (allocator) HExit()); 649 650 return bounds_check; 651 } 652 653 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) { 654 // int[] array = new int[10]; 655 // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. } 656 HInstruction* bounds_check = BuildSSAGraph3(graph_, GetAllocator(), 0, 1, kCondGE); 657 RunBCE(); 658 ASSERT_TRUE(IsRemoved(bounds_check)); 659 } 660 661 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) { 662 // int[] array = new int[10]; 663 // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. } 664 HInstruction* bounds_check = BuildSSAGraph3(graph_, GetAllocator(), 1, 1, kCondGE); 665 RunBCE(); 666 ASSERT_TRUE(IsRemoved(bounds_check)); 667 } 668 669 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) { 670 // int[] array = new int[10]; 671 // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. } 672 HInstruction* bounds_check = BuildSSAGraph3(graph_, GetAllocator(), 0, 1, kCondGT); 673 RunBCE(); 674 ASSERT_FALSE(IsRemoved(bounds_check)); 675 } 676 677 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) { 678 // int[] array = new int[10]; 679 // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. } 680 HInstruction* bounds_check = BuildSSAGraph3(graph_, GetAllocator(), 1, 8, kCondGE); 681 RunBCE(); 682 ASSERT_TRUE(IsRemoved(bounds_check)); 683 } 684 685 // for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; } 686 static HInstruction* BuildSSAGraph4(HGraph* graph, 687 ArenaAllocator* allocator, 688 int initial, 689 IfCondition cond = kCondGE) { 690 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 691 graph->AddBlock(entry); 692 graph->SetEntryBlock(entry); 693 HInstruction* parameter = new (allocator) HParameterValue( 694 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 695 entry->AddInstruction(parameter); 696 697 HInstruction* constant_initial = graph->GetIntConstant(initial); 698 HInstruction* constant_1 = graph->GetIntConstant(1); 699 HInstruction* constant_10 = graph->GetIntConstant(10); 700 HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 701 702 HBasicBlock* block = new (allocator) HBasicBlock(graph); 703 graph->AddBlock(block); 704 entry->AddSuccessor(block); 705 block->AddInstruction(new (allocator) HGoto()); 706 707 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 708 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 709 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 710 711 graph->AddBlock(loop_header); 712 graph->AddBlock(loop_body); 713 graph->AddBlock(exit); 714 block->AddSuccessor(loop_header); 715 loop_header->AddSuccessor(exit); // true successor 716 loop_header->AddSuccessor(loop_body); // false successor 717 loop_body->AddSuccessor(loop_header); 718 719 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, DataType::Type::kInt32); 720 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 721 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 722 HInstruction* cmp = nullptr; 723 if (cond == kCondGE) { 724 cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 725 } else if (cond == kCondGT) { 726 cmp = new (allocator) HGreaterThan(phi, array_length); 727 } 728 HInstruction* if_inst = new (allocator) HIf(cmp); 729 loop_header->AddPhi(phi); 730 loop_header->AddInstruction(null_check); 731 loop_header->AddInstruction(array_length); 732 loop_header->AddInstruction(cmp); 733 loop_header->AddInstruction(if_inst); 734 phi->AddInput(constant_initial); 735 736 null_check = new (allocator) HNullCheck(parameter, 0); 737 array_length = new (allocator) HArrayLength(null_check, 0); 738 HInstruction* sub = new (allocator) HSub(DataType::Type::kInt32, array_length, phi); 739 HInstruction* add_minus_1 = new (allocator) 740 HAdd(DataType::Type::kInt32, sub, constant_minus_1); 741 HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0); 742 HInstruction* array_set = new (allocator) HArraySet( 743 null_check, bounds_check, constant_10, DataType::Type::kInt32, 0); 744 HInstruction* add = new (allocator) HAdd(DataType::Type::kInt32, phi, constant_1); 745 loop_body->AddInstruction(null_check); 746 loop_body->AddInstruction(array_length); 747 loop_body->AddInstruction(sub); 748 loop_body->AddInstruction(add_minus_1); 749 loop_body->AddInstruction(bounds_check); 750 loop_body->AddInstruction(array_set); 751 loop_body->AddInstruction(add); 752 loop_body->AddInstruction(new (allocator) HGoto()); 753 phi->AddInput(add); 754 755 exit->AddInstruction(new (allocator) HExit()); 756 757 return bounds_check; 758 } 759 760 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) { 761 // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. } 762 HInstruction* bounds_check = BuildSSAGraph4(graph_, GetAllocator(), 0); 763 RunBCE(); 764 ASSERT_TRUE(IsRemoved(bounds_check)); 765 } 766 767 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) { 768 // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. } 769 HInstruction* bounds_check = BuildSSAGraph4(graph_, GetAllocator(), 1); 770 RunBCE(); 771 ASSERT_TRUE(IsRemoved(bounds_check)); 772 } 773 774 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) { 775 // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. } 776 HInstruction* bounds_check = BuildSSAGraph4(graph_, GetAllocator(), 0, kCondGT); 777 RunBCE(); 778 ASSERT_FALSE(IsRemoved(bounds_check)); 779 } 780 781 // Bubble sort: 782 // (Every array access bounds-check can be eliminated.) 783 // for (int i=0; i<array.length-1; i++) { 784 // for (int j=0; j<array.length-i-1; j++) { 785 // if (array[j] > array[j+1]) { 786 // int temp = array[j+1]; 787 // array[j+1] = array[j]; 788 // array[j] = temp; 789 // } 790 // } 791 // } 792 TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) { 793 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 794 graph_->AddBlock(entry); 795 graph_->SetEntryBlock(entry); 796 HInstruction* parameter = new (GetAllocator()) HParameterValue( 797 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 798 entry->AddInstruction(parameter); 799 800 HInstruction* constant_0 = graph_->GetIntConstant(0); 801 HInstruction* constant_minus_1 = graph_->GetIntConstant(-1); 802 HInstruction* constant_1 = graph_->GetIntConstant(1); 803 804 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_); 805 graph_->AddBlock(block); 806 entry->AddSuccessor(block); 807 block->AddInstruction(new (GetAllocator()) HGoto()); 808 809 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_); 810 graph_->AddBlock(exit); 811 exit->AddInstruction(new (GetAllocator()) HExit()); 812 813 HBasicBlock* outer_header = new (GetAllocator()) HBasicBlock(graph_); 814 graph_->AddBlock(outer_header); 815 HPhi* phi_i = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32); 816 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter, 0); 817 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0); 818 HAdd* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, array_length, constant_minus_1); 819 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(phi_i, add); 820 HIf* if_inst = new (GetAllocator()) HIf(cmp); 821 outer_header->AddPhi(phi_i); 822 outer_header->AddInstruction(null_check); 823 outer_header->AddInstruction(array_length); 824 outer_header->AddInstruction(add); 825 outer_header->AddInstruction(cmp); 826 outer_header->AddInstruction(if_inst); 827 phi_i->AddInput(constant_0); 828 829 HBasicBlock* inner_header = new (GetAllocator()) HBasicBlock(graph_); 830 graph_->AddBlock(inner_header); 831 HPhi* phi_j = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32); 832 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 833 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 834 HSub* sub = new (GetAllocator()) HSub(DataType::Type::kInt32, array_length, phi_i); 835 add = new (GetAllocator()) HAdd(DataType::Type::kInt32, sub, constant_minus_1); 836 cmp = new (GetAllocator()) HGreaterThanOrEqual(phi_j, add); 837 if_inst = new (GetAllocator()) HIf(cmp); 838 inner_header->AddPhi(phi_j); 839 inner_header->AddInstruction(null_check); 840 inner_header->AddInstruction(array_length); 841 inner_header->AddInstruction(sub); 842 inner_header->AddInstruction(add); 843 inner_header->AddInstruction(cmp); 844 inner_header->AddInstruction(if_inst); 845 phi_j->AddInput(constant_0); 846 847 HBasicBlock* inner_body_compare = new (GetAllocator()) HBasicBlock(graph_); 848 graph_->AddBlock(inner_body_compare); 849 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 850 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 851 HBoundsCheck* bounds_check1 = new (GetAllocator()) HBoundsCheck(phi_j, array_length, 0); 852 HArrayGet* array_get_j = new (GetAllocator()) 853 HArrayGet(null_check, bounds_check1, DataType::Type::kInt32, 0); 854 inner_body_compare->AddInstruction(null_check); 855 inner_body_compare->AddInstruction(array_length); 856 inner_body_compare->AddInstruction(bounds_check1); 857 inner_body_compare->AddInstruction(array_get_j); 858 HInstruction* j_plus_1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_j, constant_1); 859 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 860 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 861 HBoundsCheck* bounds_check2 = new (GetAllocator()) HBoundsCheck(j_plus_1, array_length, 0); 862 HArrayGet* array_get_j_plus_1 = new (GetAllocator()) 863 HArrayGet(null_check, bounds_check2, DataType::Type::kInt32, 0); 864 cmp = new (GetAllocator()) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1); 865 if_inst = new (GetAllocator()) HIf(cmp); 866 inner_body_compare->AddInstruction(j_plus_1); 867 inner_body_compare->AddInstruction(null_check); 868 inner_body_compare->AddInstruction(array_length); 869 inner_body_compare->AddInstruction(bounds_check2); 870 inner_body_compare->AddInstruction(array_get_j_plus_1); 871 inner_body_compare->AddInstruction(cmp); 872 inner_body_compare->AddInstruction(if_inst); 873 874 HBasicBlock* inner_body_swap = new (GetAllocator()) HBasicBlock(graph_); 875 graph_->AddBlock(inner_body_swap); 876 j_plus_1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_j, constant_1); 877 // temp = array[j+1] 878 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 879 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 880 HInstruction* bounds_check3 = new (GetAllocator()) HBoundsCheck(j_plus_1, array_length, 0); 881 array_get_j_plus_1 = new (GetAllocator()) 882 HArrayGet(null_check, bounds_check3, DataType::Type::kInt32, 0); 883 inner_body_swap->AddInstruction(j_plus_1); 884 inner_body_swap->AddInstruction(null_check); 885 inner_body_swap->AddInstruction(array_length); 886 inner_body_swap->AddInstruction(bounds_check3); 887 inner_body_swap->AddInstruction(array_get_j_plus_1); 888 // array[j+1] = array[j] 889 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 890 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 891 HInstruction* bounds_check4 = new (GetAllocator()) HBoundsCheck(phi_j, array_length, 0); 892 array_get_j = new (GetAllocator()) 893 HArrayGet(null_check, bounds_check4, DataType::Type::kInt32, 0); 894 inner_body_swap->AddInstruction(null_check); 895 inner_body_swap->AddInstruction(array_length); 896 inner_body_swap->AddInstruction(bounds_check4); 897 inner_body_swap->AddInstruction(array_get_j); 898 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 899 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 900 HInstruction* bounds_check5 = new (GetAllocator()) HBoundsCheck(j_plus_1, array_length, 0); 901 HArraySet* array_set_j_plus_1 = new (GetAllocator()) 902 HArraySet(null_check, bounds_check5, array_get_j, DataType::Type::kInt32, 0); 903 inner_body_swap->AddInstruction(null_check); 904 inner_body_swap->AddInstruction(array_length); 905 inner_body_swap->AddInstruction(bounds_check5); 906 inner_body_swap->AddInstruction(array_set_j_plus_1); 907 // array[j] = temp 908 null_check = new (GetAllocator()) HNullCheck(parameter, 0); 909 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 910 HInstruction* bounds_check6 = new (GetAllocator()) HBoundsCheck(phi_j, array_length, 0); 911 HArraySet* array_set_j = new (GetAllocator()) 912 HArraySet(null_check, bounds_check6, array_get_j_plus_1, DataType::Type::kInt32, 0); 913 inner_body_swap->AddInstruction(null_check); 914 inner_body_swap->AddInstruction(array_length); 915 inner_body_swap->AddInstruction(bounds_check6); 916 inner_body_swap->AddInstruction(array_set_j); 917 inner_body_swap->AddInstruction(new (GetAllocator()) HGoto()); 918 919 HBasicBlock* inner_body_add = new (GetAllocator()) HBasicBlock(graph_); 920 graph_->AddBlock(inner_body_add); 921 add = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_j, constant_1); 922 inner_body_add->AddInstruction(add); 923 inner_body_add->AddInstruction(new (GetAllocator()) HGoto()); 924 phi_j->AddInput(add); 925 926 HBasicBlock* outer_body_add = new (GetAllocator()) HBasicBlock(graph_); 927 graph_->AddBlock(outer_body_add); 928 add = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_i, constant_1); 929 outer_body_add->AddInstruction(add); 930 outer_body_add->AddInstruction(new (GetAllocator()) HGoto()); 931 phi_i->AddInput(add); 932 933 block->AddSuccessor(outer_header); 934 outer_header->AddSuccessor(exit); 935 outer_header->AddSuccessor(inner_header); 936 inner_header->AddSuccessor(outer_body_add); 937 inner_header->AddSuccessor(inner_body_compare); 938 inner_body_compare->AddSuccessor(inner_body_add); 939 inner_body_compare->AddSuccessor(inner_body_swap); 940 inner_body_swap->AddSuccessor(inner_body_add); 941 inner_body_add->AddSuccessor(inner_header); 942 outer_body_add->AddSuccessor(outer_header); 943 944 RunBCE(); // gvn removes same bounds check already 945 946 ASSERT_TRUE(IsRemoved(bounds_check1)); 947 ASSERT_TRUE(IsRemoved(bounds_check2)); 948 ASSERT_TRUE(IsRemoved(bounds_check3)); 949 ASSERT_TRUE(IsRemoved(bounds_check4)); 950 ASSERT_TRUE(IsRemoved(bounds_check5)); 951 ASSERT_TRUE(IsRemoved(bounds_check6)); 952 } 953 954 // int[] array = new int[10]; 955 // for (int i=0; i<200; i++) { 956 // array[i%10] = 10; // Can eliminate 957 // array[i%1] = 10; // Can eliminate 958 // array[i%200] = 10; // Cannot eliminate 959 // array[i%-10] = 10; // Can eliminate 960 // array[i%array.length] = 10; // Can eliminate 961 // array[param_i%10] = 10; // Can't eliminate, when param_i < 0 962 // } 963 TEST_F(BoundsCheckEliminationTest, ModArrayBoundsElimination) { 964 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 965 graph_->AddBlock(entry); 966 graph_->SetEntryBlock(entry); 967 HInstruction* param_i = new (GetAllocator()) 968 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32); 969 entry->AddInstruction(param_i); 970 971 HInstruction* constant_0 = graph_->GetIntConstant(0); 972 HInstruction* constant_1 = graph_->GetIntConstant(1); 973 HInstruction* constant_10 = graph_->GetIntConstant(10); 974 HInstruction* constant_200 = graph_->GetIntConstant(200); 975 HInstruction* constant_minus_10 = graph_->GetIntConstant(-10); 976 977 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_); 978 graph_->AddBlock(block); 979 entry->AddSuccessor(block); 980 // We pass a bogus constant for the class to avoid mocking one. 981 HInstruction* new_array = new (GetAllocator()) HNewArray( 982 /* cls= */ constant_10, 983 /* length= */ constant_10, 984 /* dex_pc= */ 0, 985 /* component_size_shift= */ 0); 986 block->AddInstruction(new_array); 987 block->AddInstruction(new (GetAllocator()) HGoto()); 988 989 HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_); 990 HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_); 991 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_); 992 993 graph_->AddBlock(loop_header); 994 graph_->AddBlock(loop_body); 995 graph_->AddBlock(exit); 996 block->AddSuccessor(loop_header); 997 loop_header->AddSuccessor(exit); // true successor 998 loop_header->AddSuccessor(loop_body); // false successor 999 loop_body->AddSuccessor(loop_header); 1000 1001 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32); 1002 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(phi, constant_200); 1003 HInstruction* if_inst = new (GetAllocator()) HIf(cmp); 1004 loop_header->AddPhi(phi); 1005 loop_header->AddInstruction(cmp); 1006 loop_header->AddInstruction(if_inst); 1007 phi->AddInput(constant_0); 1008 1009 ////////////////////////////////////////////////////////////////////////////////// 1010 // LOOP BODY: 1011 // array[i % 10] = 10; 1012 HRem* i_mod_10 = new (GetAllocator()) HRem(DataType::Type::kInt32, phi, constant_10, 0); 1013 HBoundsCheck* bounds_check_i_mod_10 = new (GetAllocator()) HBoundsCheck(i_mod_10, constant_10, 0); 1014 HInstruction* array_set = new (GetAllocator()) HArraySet( 1015 new_array, bounds_check_i_mod_10, constant_10, DataType::Type::kInt32, 0); 1016 loop_body->AddInstruction(i_mod_10); 1017 loop_body->AddInstruction(bounds_check_i_mod_10); 1018 loop_body->AddInstruction(array_set); 1019 1020 // array[i % 1] = 10; 1021 HRem* i_mod_1 = new (GetAllocator()) HRem(DataType::Type::kInt32, phi, constant_1, 0); 1022 HBoundsCheck* bounds_check_i_mod_1 = new (GetAllocator()) HBoundsCheck(i_mod_1, constant_10, 0); 1023 array_set = new (GetAllocator()) HArraySet( 1024 new_array, bounds_check_i_mod_1, constant_10, DataType::Type::kInt32, 0); 1025 loop_body->AddInstruction(i_mod_1); 1026 loop_body->AddInstruction(bounds_check_i_mod_1); 1027 loop_body->AddInstruction(array_set); 1028 1029 // array[i % 200] = 10; 1030 HRem* i_mod_200 = new (GetAllocator()) HRem(DataType::Type::kInt32, phi, constant_1, 0); 1031 HBoundsCheck* bounds_check_i_mod_200 = new (GetAllocator()) HBoundsCheck( 1032 i_mod_200, constant_10, 0); 1033 array_set = new (GetAllocator()) HArraySet( 1034 new_array, bounds_check_i_mod_200, constant_10, DataType::Type::kInt32, 0); 1035 loop_body->AddInstruction(i_mod_200); 1036 loop_body->AddInstruction(bounds_check_i_mod_200); 1037 loop_body->AddInstruction(array_set); 1038 1039 // array[i % -10] = 10; 1040 HRem* i_mod_minus_10 = new (GetAllocator()) HRem( 1041 DataType::Type::kInt32, phi, constant_minus_10, 0); 1042 HBoundsCheck* bounds_check_i_mod_minus_10 = new (GetAllocator()) HBoundsCheck( 1043 i_mod_minus_10, constant_10, 0); 1044 array_set = new (GetAllocator()) HArraySet( 1045 new_array, bounds_check_i_mod_minus_10, constant_10, DataType::Type::kInt32, 0); 1046 loop_body->AddInstruction(i_mod_minus_10); 1047 loop_body->AddInstruction(bounds_check_i_mod_minus_10); 1048 loop_body->AddInstruction(array_set); 1049 1050 // array[i%array.length] = 10; 1051 HNullCheck* null_check = new (GetAllocator()) HNullCheck(new_array, 0); 1052 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0); 1053 HRem* i_mod_array_length = new (GetAllocator()) HRem( 1054 DataType::Type::kInt32, phi, array_length, 0); 1055 HBoundsCheck* bounds_check_i_mod_array_len = new (GetAllocator()) HBoundsCheck( 1056 i_mod_array_length, array_length, 0); 1057 array_set = new (GetAllocator()) HArraySet( 1058 null_check, bounds_check_i_mod_array_len, constant_10, DataType::Type::kInt32, 0); 1059 loop_body->AddInstruction(null_check); 1060 loop_body->AddInstruction(array_length); 1061 loop_body->AddInstruction(i_mod_array_length); 1062 loop_body->AddInstruction(bounds_check_i_mod_array_len); 1063 loop_body->AddInstruction(array_set); 1064 1065 // array[param_i % 10] = 10; 1066 HRem* param_i_mod_10 = new (GetAllocator()) HRem(DataType::Type::kInt32, param_i, constant_10, 0); 1067 HBoundsCheck* bounds_check_param_i_mod_10 = new (GetAllocator()) HBoundsCheck( 1068 param_i_mod_10, constant_10, 0); 1069 array_set = new (GetAllocator()) HArraySet( 1070 new_array, bounds_check_param_i_mod_10, constant_10, DataType::Type::kInt32, 0); 1071 loop_body->AddInstruction(param_i_mod_10); 1072 loop_body->AddInstruction(bounds_check_param_i_mod_10); 1073 loop_body->AddInstruction(array_set); 1074 1075 // array[param_i%array.length] = 10; 1076 null_check = new (GetAllocator()) HNullCheck(new_array, 0); 1077 array_length = new (GetAllocator()) HArrayLength(null_check, 0); 1078 HRem* param_i_mod_array_length = new (GetAllocator()) HRem( 1079 DataType::Type::kInt32, param_i, array_length, 0); 1080 HBoundsCheck* bounds_check_param_i_mod_array_len = new (GetAllocator()) HBoundsCheck( 1081 param_i_mod_array_length, array_length, 0); 1082 array_set = new (GetAllocator()) HArraySet( 1083 null_check, bounds_check_param_i_mod_array_len, constant_10, DataType::Type::kInt32, 0); 1084 loop_body->AddInstruction(null_check); 1085 loop_body->AddInstruction(array_length); 1086 loop_body->AddInstruction(param_i_mod_array_length); 1087 loop_body->AddInstruction(bounds_check_param_i_mod_array_len); 1088 loop_body->AddInstruction(array_set); 1089 1090 // i++; 1091 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, constant_1); 1092 loop_body->AddInstruction(add); 1093 loop_body->AddInstruction(new (GetAllocator()) HGoto()); 1094 phi->AddInput(add); 1095 ////////////////////////////////////////////////////////////////////////////////// 1096 1097 exit->AddInstruction(new (GetAllocator()) HExit()); 1098 1099 RunBCE(); 1100 1101 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_10)); 1102 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_1)); 1103 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_200)); 1104 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_minus_10)); 1105 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_array_len)); 1106 ASSERT_FALSE(IsRemoved(bounds_check_param_i_mod_10)); 1107 } 1108 1109 } // namespace art 1110
