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 "base/arena_allocator.h" 18 #include "bounds_check_elimination.h" 19 #include "builder.h" 20 #include "gvn.h" 21 #include "induction_var_analysis.h" 22 #include "instruction_simplifier.h" 23 #include "nodes.h" 24 #include "optimizing_unit_test.h" 25 #include "side_effects_analysis.h" 26 27 #include "gtest/gtest.h" 28 29 namespace art { 30 31 /** 32 * Fixture class for the BoundsCheckElimination tests. 33 */ 34 class BoundsCheckEliminationTest : public testing::Test { 35 public: 36 BoundsCheckEliminationTest() : pool_(), allocator_(&pool_) { 37 graph_ = CreateGraph(&allocator_); 38 graph_->SetHasBoundsChecks(true); 39 } 40 41 ~BoundsCheckEliminationTest() { } 42 43 void RunBCE() { 44 graph_->BuildDominatorTree(); 45 46 InstructionSimplifier(graph_).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 ArenaPool pool_; 60 ArenaAllocator allocator_; 61 HGraph* graph_; 62 }; 63 64 65 // if (i < 0) { array[i] = 1; // Can't eliminate. } 66 // else if (i >= array.length) { array[i] = 1; // Can't eliminate. } 67 // else { array[i] = 1; // Can eliminate. } 68 TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) { 69 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 70 graph_->AddBlock(entry); 71 graph_->SetEntryBlock(entry); 72 HInstruction* parameter1 = new (&allocator_) 73 HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); // array 74 HInstruction* parameter2 = new (&allocator_) 75 HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); // i 76 entry->AddInstruction(parameter1); 77 entry->AddInstruction(parameter2); 78 79 HInstruction* constant_1 = graph_->GetIntConstant(1); 80 HInstruction* constant_0 = graph_->GetIntConstant(0); 81 82 HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 83 graph_->AddBlock(block1); 84 HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, constant_0); 85 HIf* if_inst = new (&allocator_) HIf(cmp); 86 block1->AddInstruction(cmp); 87 block1->AddInstruction(if_inst); 88 entry->AddSuccessor(block1); 89 90 HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 91 graph_->AddBlock(block2); 92 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 93 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 94 HBoundsCheck* bounds_check2 = new (&allocator_) 95 HBoundsCheck(parameter2, array_length, 0); 96 HArraySet* array_set = new (&allocator_) HArraySet( 97 null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0); 98 block2->AddInstruction(null_check); 99 block2->AddInstruction(array_length); 100 block2->AddInstruction(bounds_check2); 101 block2->AddInstruction(array_set); 102 103 HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 104 graph_->AddBlock(block3); 105 null_check = new (&allocator_) HNullCheck(parameter1, 0); 106 array_length = new (&allocator_) HArrayLength(null_check, 0); 107 cmp = new (&allocator_) HLessThan(parameter2, array_length); 108 if_inst = new (&allocator_) HIf(cmp); 109 block3->AddInstruction(null_check); 110 block3->AddInstruction(array_length); 111 block3->AddInstruction(cmp); 112 block3->AddInstruction(if_inst); 113 114 HBasicBlock* block4 = new (&allocator_) HBasicBlock(graph_); 115 graph_->AddBlock(block4); 116 null_check = new (&allocator_) HNullCheck(parameter1, 0); 117 array_length = new (&allocator_) HArrayLength(null_check, 0); 118 HBoundsCheck* bounds_check4 = new (&allocator_) 119 HBoundsCheck(parameter2, array_length, 0); 120 array_set = new (&allocator_) HArraySet( 121 null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 122 block4->AddInstruction(null_check); 123 block4->AddInstruction(array_length); 124 block4->AddInstruction(bounds_check4); 125 block4->AddInstruction(array_set); 126 127 HBasicBlock* block5 = new (&allocator_) HBasicBlock(graph_); 128 graph_->AddBlock(block5); 129 null_check = new (&allocator_) HNullCheck(parameter1, 0); 130 array_length = new (&allocator_) HArrayLength(null_check, 0); 131 HBoundsCheck* bounds_check5 = new (&allocator_) 132 HBoundsCheck(parameter2, array_length, 0); 133 array_set = new (&allocator_) HArraySet( 134 null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 135 block5->AddInstruction(null_check); 136 block5->AddInstruction(array_length); 137 block5->AddInstruction(bounds_check5); 138 block5->AddInstruction(array_set); 139 140 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 141 graph_->AddBlock(exit); 142 block2->AddSuccessor(exit); 143 block4->AddSuccessor(exit); 144 block5->AddSuccessor(exit); 145 exit->AddInstruction(new (&allocator_) HExit()); 146 147 block1->AddSuccessor(block3); // True successor 148 block1->AddSuccessor(block2); // False successor 149 150 block3->AddSuccessor(block5); // True successor 151 block3->AddSuccessor(block4); // False successor 152 153 RunBCE(); 154 155 ASSERT_FALSE(IsRemoved(bounds_check2)); 156 ASSERT_FALSE(IsRemoved(bounds_check4)); 157 ASSERT_TRUE(IsRemoved(bounds_check5)); 158 } 159 160 // if (i > 0) { 161 // // Positive number plus MAX_INT will overflow and be negative. 162 // int j = i + Integer.MAX_VALUE; 163 // if (j < array.length) array[j] = 1; // Can't eliminate. 164 // } 165 TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) { 166 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 167 graph_->AddBlock(entry); 168 graph_->SetEntryBlock(entry); 169 HInstruction* parameter1 = new (&allocator_) 170 HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); // array 171 HInstruction* parameter2 = new (&allocator_) 172 HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); // i 173 entry->AddInstruction(parameter1); 174 entry->AddInstruction(parameter2); 175 176 HInstruction* constant_1 = graph_->GetIntConstant(1); 177 HInstruction* constant_0 = graph_->GetIntConstant(0); 178 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX); 179 180 HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 181 graph_->AddBlock(block1); 182 HInstruction* cmp = new (&allocator_) HLessThanOrEqual(parameter2, constant_0); 183 HIf* if_inst = new (&allocator_) HIf(cmp); 184 block1->AddInstruction(cmp); 185 block1->AddInstruction(if_inst); 186 entry->AddSuccessor(block1); 187 188 HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 189 graph_->AddBlock(block2); 190 HInstruction* add = new (&allocator_) HAdd(Primitive::kPrimInt, parameter2, constant_max_int); 191 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 192 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 193 HInstruction* cmp2 = new (&allocator_) HGreaterThanOrEqual(add, array_length); 194 if_inst = new (&allocator_) HIf(cmp2); 195 block2->AddInstruction(add); 196 block2->AddInstruction(null_check); 197 block2->AddInstruction(array_length); 198 block2->AddInstruction(cmp2); 199 block2->AddInstruction(if_inst); 200 201 HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 202 graph_->AddBlock(block3); 203 HBoundsCheck* bounds_check = new (&allocator_) 204 HBoundsCheck(add, array_length, 0); 205 HArraySet* array_set = new (&allocator_) HArraySet( 206 null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 207 block3->AddInstruction(bounds_check); 208 block3->AddInstruction(array_set); 209 210 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 211 graph_->AddBlock(exit); 212 exit->AddInstruction(new (&allocator_) HExit()); 213 block1->AddSuccessor(exit); // true successor 214 block1->AddSuccessor(block2); // false successor 215 block2->AddSuccessor(exit); // true successor 216 block2->AddSuccessor(block3); // false successor 217 block3->AddSuccessor(exit); 218 219 RunBCE(); 220 221 ASSERT_FALSE(IsRemoved(bounds_check)); 222 } 223 224 // if (i < array.length) { 225 // int j = i - Integer.MAX_VALUE; 226 // j = j - Integer.MAX_VALUE; // j is (i+2) after subtracting MAX_INT twice 227 // if (j > 0) array[j] = 1; // Can't eliminate. 228 // } 229 TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) { 230 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 231 graph_->AddBlock(entry); 232 graph_->SetEntryBlock(entry); 233 HInstruction* parameter1 = new (&allocator_) 234 HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); // array 235 HInstruction* parameter2 = new (&allocator_) 236 HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); // i 237 entry->AddInstruction(parameter1); 238 entry->AddInstruction(parameter2); 239 240 HInstruction* constant_1 = graph_->GetIntConstant(1); 241 HInstruction* constant_0 = graph_->GetIntConstant(0); 242 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX); 243 244 HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 245 graph_->AddBlock(block1); 246 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 247 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 248 HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, array_length); 249 HIf* if_inst = new (&allocator_) HIf(cmp); 250 block1->AddInstruction(null_check); 251 block1->AddInstruction(array_length); 252 block1->AddInstruction(cmp); 253 block1->AddInstruction(if_inst); 254 entry->AddSuccessor(block1); 255 256 HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 257 graph_->AddBlock(block2); 258 HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, parameter2, constant_max_int); 259 HInstruction* sub2 = new (&allocator_) HSub(Primitive::kPrimInt, sub1, constant_max_int); 260 HInstruction* cmp2 = new (&allocator_) HLessThanOrEqual(sub2, constant_0); 261 if_inst = new (&allocator_) HIf(cmp2); 262 block2->AddInstruction(sub1); 263 block2->AddInstruction(sub2); 264 block2->AddInstruction(cmp2); 265 block2->AddInstruction(if_inst); 266 267 HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 268 graph_->AddBlock(block3); 269 HBoundsCheck* bounds_check = new (&allocator_) 270 HBoundsCheck(sub2, array_length, 0); 271 HArraySet* array_set = new (&allocator_) HArraySet( 272 null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 273 block3->AddInstruction(bounds_check); 274 block3->AddInstruction(array_set); 275 276 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 277 graph_->AddBlock(exit); 278 exit->AddInstruction(new (&allocator_) 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 (&allocator_) HBasicBlock(graph_); 295 graph_->AddBlock(entry); 296 graph_->SetEntryBlock(entry); 297 HInstruction* parameter = new (&allocator_) HParameterValue( 298 graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); 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 (&allocator_) HBasicBlock(graph_); 307 graph_->AddBlock(block); 308 entry->AddSuccessor(block); 309 310 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0); 311 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 312 HBoundsCheck* bounds_check6 = new (&allocator_) 313 HBoundsCheck(constant_6, array_length, 0); 314 HInstruction* array_set = new (&allocator_) HArraySet( 315 null_check, bounds_check6, constant_1, Primitive::kPrimInt, 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 (&allocator_) HNullCheck(parameter, 0); 322 array_length = new (&allocator_) HArrayLength(null_check, 0); 323 HBoundsCheck* bounds_check5 = new (&allocator_) 324 HBoundsCheck(constant_5, array_length, 0); 325 array_set = new (&allocator_) HArraySet( 326 null_check, bounds_check5, constant_1, Primitive::kPrimInt, 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 (&allocator_) HNullCheck(parameter, 0); 333 array_length = new (&allocator_) HArrayLength(null_check, 0); 334 HBoundsCheck* bounds_check4 = new (&allocator_) 335 HBoundsCheck(constant_4, array_length, 0); 336 array_set = new (&allocator_) HArraySet( 337 null_check, bounds_check4, constant_1, Primitive::kPrimInt, 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 (&allocator_) HGoto()); 344 345 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 346 graph_->AddBlock(exit); 347 block->AddSuccessor(exit); 348 exit->AddInstruction(new (&allocator_) 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(), 0, 0, Primitive::kPrimNot); 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, Primitive::kPrimInt); 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, Primitive::kPrimInt, 0); 414 415 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, 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_, &allocator_, 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_, &allocator_, 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_, &allocator_, -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_, &allocator_, 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_, &allocator_, 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_, &allocator_, 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(), 0, 0, Primitive::kPrimNot); 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, Primitive::kPrimInt); 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(Primitive::kPrimInt, 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, Primitive::kPrimInt, 0); 531 HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, 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_, &allocator_, 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_, &allocator_, 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_, &allocator_, -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_, &allocator_, 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_, &allocator_, 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 HInstruction* new_array = new (allocator) HNewArray( 600 constant_10, 601 graph->GetCurrentMethod(), 602 0, 603 Primitive::kPrimInt, 604 graph->GetDexFile(), 605 kQuickAllocArray); 606 block->AddInstruction(new_array); 607 block->AddInstruction(new (allocator) HGoto()); 608 609 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 610 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 611 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 612 613 graph->AddBlock(loop_header); 614 graph->AddBlock(loop_body); 615 graph->AddBlock(exit); 616 block->AddSuccessor(loop_header); 617 loop_header->AddSuccessor(exit); // true successor 618 loop_header->AddSuccessor(loop_body); // false successor 619 loop_body->AddSuccessor(loop_header); 620 621 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 622 HInstruction* cmp = nullptr; 623 if (cond == kCondGE) { 624 cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10); 625 } else { 626 DCHECK(cond == kCondGT); 627 cmp = new (allocator) HGreaterThan(phi, constant_10); 628 } 629 HInstruction* if_inst = new (allocator) HIf(cmp); 630 loop_header->AddPhi(phi); 631 loop_header->AddInstruction(cmp); 632 loop_header->AddInstruction(if_inst); 633 phi->AddInput(constant_initial); 634 635 HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0); 636 HArrayLength* array_length = new (allocator) HArrayLength(null_check, 0); 637 HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 638 HInstruction* array_set = new (allocator) HArraySet( 639 null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 640 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 641 loop_body->AddInstruction(null_check); 642 loop_body->AddInstruction(array_length); 643 loop_body->AddInstruction(bounds_check); 644 loop_body->AddInstruction(array_set); 645 loop_body->AddInstruction(add); 646 loop_body->AddInstruction(new (allocator) HGoto()); 647 phi->AddInput(add); 648 649 exit->AddInstruction(new (allocator) HExit()); 650 651 return bounds_check; 652 } 653 654 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) { 655 // int[] array = new int[10]; 656 // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. } 657 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGE); 658 RunBCE(); 659 ASSERT_TRUE(IsRemoved(bounds_check)); 660 } 661 662 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) { 663 // int[] array = new int[10]; 664 // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. } 665 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 1, kCondGE); 666 RunBCE(); 667 ASSERT_TRUE(IsRemoved(bounds_check)); 668 } 669 670 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) { 671 // int[] array = new int[10]; 672 // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. } 673 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGT); 674 RunBCE(); 675 ASSERT_FALSE(IsRemoved(bounds_check)); 676 } 677 678 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) { 679 // int[] array = new int[10]; 680 // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. } 681 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 8, kCondGE); 682 RunBCE(); 683 ASSERT_TRUE(IsRemoved(bounds_check)); 684 } 685 686 // for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; } 687 static HInstruction* BuildSSAGraph4(HGraph* graph, 688 ArenaAllocator* allocator, 689 int initial, 690 IfCondition cond = kCondGE) { 691 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 692 graph->AddBlock(entry); 693 graph->SetEntryBlock(entry); 694 HInstruction* parameter = new (allocator) HParameterValue( 695 graph->GetDexFile(), 0, 0, Primitive::kPrimNot); 696 entry->AddInstruction(parameter); 697 698 HInstruction* constant_initial = graph->GetIntConstant(initial); 699 HInstruction* constant_1 = graph->GetIntConstant(1); 700 HInstruction* constant_10 = graph->GetIntConstant(10); 701 HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 702 703 HBasicBlock* block = new (allocator) HBasicBlock(graph); 704 graph->AddBlock(block); 705 entry->AddSuccessor(block); 706 block->AddInstruction(new (allocator) HGoto()); 707 708 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 709 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 710 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 711 712 graph->AddBlock(loop_header); 713 graph->AddBlock(loop_body); 714 graph->AddBlock(exit); 715 block->AddSuccessor(loop_header); 716 loop_header->AddSuccessor(exit); // true successor 717 loop_header->AddSuccessor(loop_body); // false successor 718 loop_body->AddSuccessor(loop_header); 719 720 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 721 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 722 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 723 HInstruction* cmp = nullptr; 724 if (cond == kCondGE) { 725 cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 726 } else if (cond == kCondGT) { 727 cmp = new (allocator) HGreaterThan(phi, array_length); 728 } 729 HInstruction* if_inst = new (allocator) HIf(cmp); 730 loop_header->AddPhi(phi); 731 loop_header->AddInstruction(null_check); 732 loop_header->AddInstruction(array_length); 733 loop_header->AddInstruction(cmp); 734 loop_header->AddInstruction(if_inst); 735 phi->AddInput(constant_initial); 736 737 null_check = new (allocator) HNullCheck(parameter, 0); 738 array_length = new (allocator) HArrayLength(null_check, 0); 739 HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi); 740 HInstruction* add_minus_1 = new (allocator) 741 HAdd(Primitive::kPrimInt, sub, constant_minus_1); 742 HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0); 743 HInstruction* array_set = new (allocator) HArraySet( 744 null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 745 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1); 746 loop_body->AddInstruction(null_check); 747 loop_body->AddInstruction(array_length); 748 loop_body->AddInstruction(sub); 749 loop_body->AddInstruction(add_minus_1); 750 loop_body->AddInstruction(bounds_check); 751 loop_body->AddInstruction(array_set); 752 loop_body->AddInstruction(add); 753 loop_body->AddInstruction(new (allocator) HGoto()); 754 phi->AddInput(add); 755 756 exit->AddInstruction(new (allocator) HExit()); 757 758 return bounds_check; 759 } 760 761 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) { 762 // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. } 763 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0); 764 RunBCE(); 765 ASSERT_TRUE(IsRemoved(bounds_check)); 766 } 767 768 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) { 769 // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. } 770 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 1); 771 RunBCE(); 772 ASSERT_TRUE(IsRemoved(bounds_check)); 773 } 774 775 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) { 776 // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. } 777 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0, kCondGT); 778 RunBCE(); 779 ASSERT_FALSE(IsRemoved(bounds_check)); 780 } 781 782 // Bubble sort: 783 // (Every array access bounds-check can be eliminated.) 784 // for (int i=0; i<array.length-1; i++) { 785 // for (int j=0; j<array.length-i-1; j++) { 786 // if (array[j] > array[j+1]) { 787 // int temp = array[j+1]; 788 // array[j+1] = array[j]; 789 // array[j] = temp; 790 // } 791 // } 792 // } 793 TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) { 794 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 795 graph_->AddBlock(entry); 796 graph_->SetEntryBlock(entry); 797 HInstruction* parameter = new (&allocator_) HParameterValue( 798 graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); 799 entry->AddInstruction(parameter); 800 801 HInstruction* constant_0 = graph_->GetIntConstant(0); 802 HInstruction* constant_minus_1 = graph_->GetIntConstant(-1); 803 HInstruction* constant_1 = graph_->GetIntConstant(1); 804 805 HBasicBlock* block = new (&allocator_) HBasicBlock(graph_); 806 graph_->AddBlock(block); 807 entry->AddSuccessor(block); 808 block->AddInstruction(new (&allocator_) HGoto()); 809 810 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 811 graph_->AddBlock(exit); 812 exit->AddInstruction(new (&allocator_) HExit()); 813 814 HBasicBlock* outer_header = new (&allocator_) HBasicBlock(graph_); 815 graph_->AddBlock(outer_header); 816 HPhi* phi_i = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); 817 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0); 818 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 819 HAdd* add = new (&allocator_) HAdd(Primitive::kPrimInt, array_length, constant_minus_1); 820 HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(phi_i, add); 821 HIf* if_inst = new (&allocator_) HIf(cmp); 822 outer_header->AddPhi(phi_i); 823 outer_header->AddInstruction(null_check); 824 outer_header->AddInstruction(array_length); 825 outer_header->AddInstruction(add); 826 outer_header->AddInstruction(cmp); 827 outer_header->AddInstruction(if_inst); 828 phi_i->AddInput(constant_0); 829 830 HBasicBlock* inner_header = new (&allocator_) HBasicBlock(graph_); 831 graph_->AddBlock(inner_header); 832 HPhi* phi_j = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); 833 null_check = new (&allocator_) HNullCheck(parameter, 0); 834 array_length = new (&allocator_) HArrayLength(null_check, 0); 835 HSub* sub = new (&allocator_) HSub(Primitive::kPrimInt, array_length, phi_i); 836 add = new (&allocator_) HAdd(Primitive::kPrimInt, sub, constant_minus_1); 837 cmp = new (&allocator_) HGreaterThanOrEqual(phi_j, add); 838 if_inst = new (&allocator_) HIf(cmp); 839 inner_header->AddPhi(phi_j); 840 inner_header->AddInstruction(null_check); 841 inner_header->AddInstruction(array_length); 842 inner_header->AddInstruction(sub); 843 inner_header->AddInstruction(add); 844 inner_header->AddInstruction(cmp); 845 inner_header->AddInstruction(if_inst); 846 phi_j->AddInput(constant_0); 847 848 HBasicBlock* inner_body_compare = new (&allocator_) HBasicBlock(graph_); 849 graph_->AddBlock(inner_body_compare); 850 null_check = new (&allocator_) HNullCheck(parameter, 0); 851 array_length = new (&allocator_) HArrayLength(null_check, 0); 852 HBoundsCheck* bounds_check1 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 853 HArrayGet* array_get_j = new (&allocator_) 854 HArrayGet(null_check, bounds_check1, Primitive::kPrimInt, 0); 855 inner_body_compare->AddInstruction(null_check); 856 inner_body_compare->AddInstruction(array_length); 857 inner_body_compare->AddInstruction(bounds_check1); 858 inner_body_compare->AddInstruction(array_get_j); 859 HInstruction* j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 860 null_check = new (&allocator_) HNullCheck(parameter, 0); 861 array_length = new (&allocator_) HArrayLength(null_check, 0); 862 HBoundsCheck* bounds_check2 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 863 HArrayGet* array_get_j_plus_1 = new (&allocator_) 864 HArrayGet(null_check, bounds_check2, Primitive::kPrimInt, 0); 865 cmp = new (&allocator_) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1); 866 if_inst = new (&allocator_) HIf(cmp); 867 inner_body_compare->AddInstruction(j_plus_1); 868 inner_body_compare->AddInstruction(null_check); 869 inner_body_compare->AddInstruction(array_length); 870 inner_body_compare->AddInstruction(bounds_check2); 871 inner_body_compare->AddInstruction(array_get_j_plus_1); 872 inner_body_compare->AddInstruction(cmp); 873 inner_body_compare->AddInstruction(if_inst); 874 875 HBasicBlock* inner_body_swap = new (&allocator_) HBasicBlock(graph_); 876 graph_->AddBlock(inner_body_swap); 877 j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 878 // temp = array[j+1] 879 null_check = new (&allocator_) HNullCheck(parameter, 0); 880 array_length = new (&allocator_) HArrayLength(null_check, 0); 881 HInstruction* bounds_check3 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 882 array_get_j_plus_1 = new (&allocator_) 883 HArrayGet(null_check, bounds_check3, Primitive::kPrimInt, 0); 884 inner_body_swap->AddInstruction(j_plus_1); 885 inner_body_swap->AddInstruction(null_check); 886 inner_body_swap->AddInstruction(array_length); 887 inner_body_swap->AddInstruction(bounds_check3); 888 inner_body_swap->AddInstruction(array_get_j_plus_1); 889 // array[j+1] = array[j] 890 null_check = new (&allocator_) HNullCheck(parameter, 0); 891 array_length = new (&allocator_) HArrayLength(null_check, 0); 892 HInstruction* bounds_check4 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 893 array_get_j = new (&allocator_) 894 HArrayGet(null_check, bounds_check4, Primitive::kPrimInt, 0); 895 inner_body_swap->AddInstruction(null_check); 896 inner_body_swap->AddInstruction(array_length); 897 inner_body_swap->AddInstruction(bounds_check4); 898 inner_body_swap->AddInstruction(array_get_j); 899 null_check = new (&allocator_) HNullCheck(parameter, 0); 900 array_length = new (&allocator_) HArrayLength(null_check, 0); 901 HInstruction* bounds_check5 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 902 HArraySet* array_set_j_plus_1 = new (&allocator_) 903 HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0); 904 inner_body_swap->AddInstruction(null_check); 905 inner_body_swap->AddInstruction(array_length); 906 inner_body_swap->AddInstruction(bounds_check5); 907 inner_body_swap->AddInstruction(array_set_j_plus_1); 908 // array[j] = temp 909 null_check = new (&allocator_) HNullCheck(parameter, 0); 910 array_length = new (&allocator_) HArrayLength(null_check, 0); 911 HInstruction* bounds_check6 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 912 HArraySet* array_set_j = new (&allocator_) 913 HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0); 914 inner_body_swap->AddInstruction(null_check); 915 inner_body_swap->AddInstruction(array_length); 916 inner_body_swap->AddInstruction(bounds_check6); 917 inner_body_swap->AddInstruction(array_set_j); 918 inner_body_swap->AddInstruction(new (&allocator_) HGoto()); 919 920 HBasicBlock* inner_body_add = new (&allocator_) HBasicBlock(graph_); 921 graph_->AddBlock(inner_body_add); 922 add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 923 inner_body_add->AddInstruction(add); 924 inner_body_add->AddInstruction(new (&allocator_) HGoto()); 925 phi_j->AddInput(add); 926 927 HBasicBlock* outer_body_add = new (&allocator_) HBasicBlock(graph_); 928 graph_->AddBlock(outer_body_add); 929 add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_i, constant_1); 930 outer_body_add->AddInstruction(add); 931 outer_body_add->AddInstruction(new (&allocator_) HGoto()); 932 phi_i->AddInput(add); 933 934 block->AddSuccessor(outer_header); 935 outer_header->AddSuccessor(exit); 936 outer_header->AddSuccessor(inner_header); 937 inner_header->AddSuccessor(outer_body_add); 938 inner_header->AddSuccessor(inner_body_compare); 939 inner_body_compare->AddSuccessor(inner_body_add); 940 inner_body_compare->AddSuccessor(inner_body_swap); 941 inner_body_swap->AddSuccessor(inner_body_add); 942 inner_body_add->AddSuccessor(inner_header); 943 outer_body_add->AddSuccessor(outer_header); 944 945 RunBCE(); // gvn removes same bounds check already 946 947 ASSERT_TRUE(IsRemoved(bounds_check1)); 948 ASSERT_TRUE(IsRemoved(bounds_check2)); 949 ASSERT_TRUE(IsRemoved(bounds_check3)); 950 ASSERT_TRUE(IsRemoved(bounds_check4)); 951 ASSERT_TRUE(IsRemoved(bounds_check5)); 952 ASSERT_TRUE(IsRemoved(bounds_check6)); 953 } 954 955 } // namespace art 956
