1f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang/* 2f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * Copyright (C) 2014 The Android Open Source Project 3f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * 4f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * Licensed under the Apache License, Version 2.0 (the "License"); 5f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * you may not use this file except in compliance with the License. 6f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * You may obtain a copy of the License at 7f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * 8f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * http://www.apache.org/licenses/LICENSE-2.0 9f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * 10f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * Unless required by applicable law or agreed to in writing, software 11f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * distributed under the License is distributed on an "AS IS" BASIS, 12f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * See the License for the specific language governing permissions and 14f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang * limitations under the License. 15f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang */ 16f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 17b666f4805c8ae707ea6fd7f6c7f375e0b000dba8Mathieu Chartier#include "base/arena_allocator.h" 18f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "bounds_check_elimination.h" 19f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "builder.h" 20f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "gvn.h" 2122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik#include "induction_var_analysis.h" 220304e182adee81be32c744fd3c0d28add29974ffMingyao Yang#include "instruction_simplifier.h" 23f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "nodes.h" 24f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "optimizing_unit_test.h" 25827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray#include "side_effects_analysis.h" 26f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 27f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "gtest/gtest.h" 28f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 29f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangnamespace art { 30f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 3122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik/** 3222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik * Fixture class for the BoundsCheckElimination tests. 3322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik */ 3422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bikclass BoundsCheckEliminationTest : public testing::Test { 3522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik public: 3622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik BoundsCheckEliminationTest() : pool_(), allocator_(&pool_) { 3722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_ = CreateGraph(&allocator_); 3822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->SetHasBoundsChecks(true); 3922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik } 4022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 4122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ~BoundsCheckEliminationTest() { } 4222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 4322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik void RunBCE() { 4422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->BuildDominatorTree(); 4522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 4622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik InstructionSimplifier(graph_).Run(); 4722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 4822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik SideEffectsAnalysis side_effects(graph_); 4922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik side_effects.Run(); 5022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 5122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik GVNOptimization(graph_, side_effects).Run(); 5222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 5322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInductionVarAnalysis induction(graph_); 5422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik induction.Run(); 5522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 564a34277c55279ba57ab361f7580db846a201d9b1Aart Bik BoundsCheckElimination(graph_, side_effects, &induction).Run(); 5722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik } 5822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 5922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ArenaPool pool_; 6022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ArenaAllocator allocator_; 6122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HGraph* graph_; 6222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik}; 6322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 64e6f171514c9c499bd0a137aff6bd8a7a79d2682aNicolas Geoffray 65f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (i < 0) { array[i] = 1; // Can't eliminate. } 66f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// else if (i >= array.length) { array[i] = 1; // Can't eliminate. } 67f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// else { array[i] = 1; // Can eliminate. } 6822af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) { 6922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 7022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(entry); 7122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->SetEntryBlock(entry); 7222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* parameter1 = new (&allocator_) 73e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); // array 7422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* parameter2 = new (&allocator_) 75e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); // i 76f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 77f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 788d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 7922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_1 = graph_->GetIntConstant(1); 8022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_0 = graph_->GetIntConstant(0); 81f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 8222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 8322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block1); 8422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, constant_0); 8522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HIf* if_inst = new (&allocator_) HIf(cmp); 86f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 87f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 88f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 89f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 9022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 9122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block2); 9222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 93154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 9422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check2 = new (&allocator_) 95f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 9622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HArraySet* array_set = new (&allocator_) HArraySet( 97f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0); 98f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(null_check); 99f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_length); 100f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(bounds_check2); 101f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_set); 102f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 10322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 10422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block3); 10522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter1, 0); 106154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 10722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik cmp = new (&allocator_) HLessThan(parameter2, array_length); 10822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik if_inst = new (&allocator_) HIf(cmp); 109f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(null_check); 110f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_length); 111f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(cmp); 112f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(if_inst); 113f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 11422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block4 = new (&allocator_) HBasicBlock(graph_); 11522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block4); 11622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter1, 0); 117154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 11822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check4 = new (&allocator_) 119f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 12022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik array_set = new (&allocator_) HArraySet( 121f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 122f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(null_check); 123f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(array_length); 124f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(bounds_check4); 125f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(array_set); 126f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 12722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block5 = new (&allocator_) HBasicBlock(graph_); 12822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block5); 12922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter1, 0); 130154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 13122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check5 = new (&allocator_) 132f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 13322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik array_set = new (&allocator_) HArraySet( 134f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 135f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(null_check); 136f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(array_length); 137f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(bounds_check5); 138f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(array_set); 139f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 14022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 14122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(exit); 142f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddSuccessor(exit); 143f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddSuccessor(exit); 144f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddSuccessor(exit); 14522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik exit->AddInstruction(new (&allocator_) HExit()); 146f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 147f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddSuccessor(block3); // True successor 148f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddSuccessor(block2); // False successor 149f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 150f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(block5); // True successor 151f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(block4); // False successor 152f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 15322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 15422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 155f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check2)); 156f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check4)); 157f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 158f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 159f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 160f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (i > 0) { 161f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// // Positive number plus MAX_INT will overflow and be negative. 162f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int j = i + Integer.MAX_VALUE; 163f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (j < array.length) array[j] = 1; // Can't eliminate. 164f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 16522af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) { 16622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 16722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(entry); 16822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->SetEntryBlock(entry); 16922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* parameter1 = new (&allocator_) 170e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); // array 17122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* parameter2 = new (&allocator_) 172e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); // i 173f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 174f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 1758d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 17622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_1 = graph_->GetIntConstant(1); 17722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_0 = graph_->GetIntConstant(0); 17822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX); 179f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 18022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 18122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block1); 18222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* cmp = new (&allocator_) HLessThanOrEqual(parameter2, constant_0); 18322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HIf* if_inst = new (&allocator_) HIf(cmp); 184f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 185f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 186f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 187f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 18822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 18922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block2); 19022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* add = new (&allocator_) HAdd(Primitive::kPrimInt, parameter2, constant_max_int); 19122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 192154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 19322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* cmp2 = new (&allocator_) HGreaterThanOrEqual(add, array_length); 19422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik if_inst = new (&allocator_) HIf(cmp2); 195f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(add); 196f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(null_check); 197f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_length); 198f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(cmp2); 199f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(if_inst); 200f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 20122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 20222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block3); 20322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check = new (&allocator_) 204f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(add, array_length, 0); 20522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HArraySet* array_set = new (&allocator_) HArraySet( 206f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 207f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(bounds_check); 208f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_set); 209f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 21022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 21122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(exit); 21222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik exit->AddInstruction(new (&allocator_) HExit()); 2130418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(exit); // true successor 2140418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(block2); // false successor 2150418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(exit); // true successor 2160418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(block3); // false successor 217f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(exit); 218f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 21922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 22022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 221f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 222f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 223f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 224f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (i < array.length) { 225f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int j = i - Integer.MAX_VALUE; 22622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik// j = j - Integer.MAX_VALUE; // j is (i+2) after subtracting MAX_INT twice 227f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (j > 0) array[j] = 1; // Can't eliminate. 228f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 22922af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) { 23022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 23122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(entry); 23222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->SetEntryBlock(entry); 23322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* parameter1 = new (&allocator_) 234e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); // array 23522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* parameter2 = new (&allocator_) 236e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); // i 237f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 238f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 2398d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 24022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_1 = graph_->GetIntConstant(1); 24122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_0 = graph_->GetIntConstant(0); 24222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX); 24322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 24422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 24522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block1); 24622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 247154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 24822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, array_length); 24922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HIf* if_inst = new (&allocator_) HIf(cmp); 250f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(null_check); 251f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(array_length); 252f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 253f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 254f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 255f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 25622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 25722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block2); 25822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, parameter2, constant_max_int); 25922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* sub2 = new (&allocator_) HSub(Primitive::kPrimInt, sub1, constant_max_int); 26022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* cmp2 = new (&allocator_) HLessThanOrEqual(sub2, constant_0); 26122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik if_inst = new (&allocator_) HIf(cmp2); 262f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(sub1); 263f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(sub2); 264f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(cmp2); 265f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(if_inst); 266f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 26722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 26822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block3); 26922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check = new (&allocator_) 270f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(sub2, array_length, 0); 27122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HArraySet* array_set = new (&allocator_) HArraySet( 272f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 273f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(bounds_check); 274f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_set); 275f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 27622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 27722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(exit); 27822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik exit->AddInstruction(new (&allocator_) HExit()); 2790418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(exit); // true successor 2800418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(block2); // false successor 2810418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(exit); // true successor 2820418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(block3); // false successor 283f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(exit); 284f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 28522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 28622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 287f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 288f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 289f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 2900ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe// array[6] = 1; // Can't eliminate. 291d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang// array[5] = 1; // Can eliminate. 292d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang// array[4] = 1; // Can eliminate. 29322af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) { 29422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 29522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(entry); 29622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->SetEntryBlock(entry); 297e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HInstruction* parameter = new (&allocator_) HParameterValue( 298e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); 299f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 3008d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 30122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_5 = graph_->GetIntConstant(5); 30222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_4 = graph_->GetIntConstant(4); 30322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_6 = graph_->GetIntConstant(6); 30422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_1 = graph_->GetIntConstant(1); 305f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 30622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block = new (&allocator_) HBasicBlock(graph_); 30722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block); 308f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 309f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 31022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0); 311154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 31222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check6 = new (&allocator_) 313d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck(constant_6, array_length, 0); 31422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* array_set = new (&allocator_) HArraySet( 315d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0); 316f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 317f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 318d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang block->AddInstruction(bounds_check6); 319f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_set); 320f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 32122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 322154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 32322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check5 = new (&allocator_) 324d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck(constant_5, array_length, 0); 32522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik array_set = new (&allocator_) HArraySet( 326d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 327f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 328f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 329d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang block->AddInstruction(bounds_check5); 330f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_set); 331f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 33222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 333154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 33422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check4 = new (&allocator_) 335d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck(constant_4, array_length, 0); 33622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik array_set = new (&allocator_) HArraySet( 337d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 3380ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(null_check); 3390ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(array_length); 340d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang block->AddInstruction(bounds_check4); 3410ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(array_set); 3420ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe 34322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik block->AddInstruction(new (&allocator_) HGoto()); 344f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 34522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 34622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(exit); 347f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(exit); 34822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik exit->AddInstruction(new (&allocator_) HExit()); 34922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 35022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 351f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 3520ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe ASSERT_FALSE(IsRemoved(bounds_check6)); 353d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 354d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang ASSERT_TRUE(IsRemoved(bounds_check4)); 355f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 356f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 357f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=initial; i<array.length; i+=increment) { array[i] = 10; } 35822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bikstatic HInstruction* BuildSSAGraph1(HGraph* graph, 35922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ArenaAllocator* allocator, 36022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik int initial, 36122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik int increment, 36222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik IfCondition cond = kCondGE) { 363f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 364f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 365f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 366e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HInstruction* parameter = new (allocator) HParameterValue( 367e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle graph->GetDexFile(), 0, 0, Primitive::kPrimNot); 368f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 3698d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 3708d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_initial = graph->GetIntConstant(initial); 3718d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_increment = graph->GetIntConstant(increment); 3728d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_10 = graph->GetIntConstant(10); 373f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 374f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 375f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 376f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 377f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 378f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 379f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 380f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 381f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 382f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 383f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 384f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 385f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 386f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 387f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 388f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 389f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 390f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 391f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 392f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 393154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 394f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 395f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 396f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 397f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 398f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondGT); 399f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, array_length); 400f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 401f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 402f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 403f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(null_check); 404f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(array_length); 405f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 406f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 4071abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 408f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 409f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 410154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (allocator) HArrayLength(null_check, 0); 41122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 412f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 41322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 414f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 415f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 416f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 417f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 41822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik loop_body->AddInstruction(bounds_check); 419f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 420f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 421f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 422f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 423f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 424f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 425f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 42622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik return bounds_check; 427f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 428f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 42922af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1a) { 430f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. } 43122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1); 43222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 433f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 43422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 435f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 43622af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1b) { 437f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. } 43822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 1); 43922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 440f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 44122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 442f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 44322af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1c) { 444f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. } 44522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, -1, 1); 44622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 447f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 44822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 449f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 45022af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1d) { 451f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. } 45222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1, kCondGT); 45322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 454f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 45522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 456f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 45722af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1e) { 458f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i += 2) { 459f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[i] = 10; // Can't eliminate due to overflow concern. } 46022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 2); 46122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 462f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 46322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 464f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 46522af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1f) { 466f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. } 46722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 2); 46822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 469f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 470f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 471f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 472f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; } 47322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bikstatic HInstruction* BuildSSAGraph2(HGraph *graph, 47422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ArenaAllocator* allocator, 47522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik int initial, 47622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik int increment = -1, 47722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik IfCondition cond = kCondLE) { 478f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 479f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 480f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 481e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HInstruction* parameter = new (allocator) HParameterValue( 482e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle graph->GetDexFile(), 0, 0, Primitive::kPrimNot); 483f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 4848d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 4858d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_initial = graph->GetIntConstant(initial); 4868d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_increment = graph->GetIntConstant(increment); 4878d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 4888d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_10 = graph->GetIntConstant(10); 489f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 490f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 491f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 492f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 493f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 494154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 495f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 496f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 497f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 498f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 499f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 500f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 501f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 502f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 503f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 504f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 505f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 506f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 507f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 508f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 509f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 510f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 511f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 512f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 513f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondLE) { 514f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HLessThanOrEqual(phi, constant_initial); 515f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 516f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondLT); 517f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HLessThan(phi, constant_initial); 518f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 519f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 520f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 521f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 522f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 5231abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(array_length); 524f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 525f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1); 526f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 527154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (allocator) HArrayLength(null_check, 0); 52822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = new (allocator) HBoundsCheck(add, array_length, 0); 529f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 53022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 531f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 532f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 533f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 534f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 53522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik loop_body->AddInstruction(bounds_check); 536f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 537f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add_phi); 538f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 539f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 540f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 541f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 542f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 54322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik return bounds_check; 544f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 545f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 54622af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2a) { 547f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. } 54822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0); 54922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 550f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 55122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 552f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 55322af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2b) { 554f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. } 55522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 1); 55622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 557f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 55822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 559f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 56022af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2c) { 561f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. } 56222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, -1); 56322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 564f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 56522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 566f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 56722af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2d) { 568f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. } 56922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -1, kCondLT); 57022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 571f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 57222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 573f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 57422af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2e) { 575f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. } 57622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -2); 57722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 578f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 579f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 580f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 5818c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang// int[] array = new int[10]; 582f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=0; i<10; i+=increment) { array[i] = 10; } 58322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bikstatic HInstruction* BuildSSAGraph3(HGraph* graph, 58422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ArenaAllocator* allocator, 58522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik int initial, 58622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik int increment, 58722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik IfCondition cond) { 588f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 589f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 590f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 5918d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 5928d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_10 = graph->GetIntConstant(10); 5938d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_initial = graph->GetIntConstant(initial); 5948d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_increment = graph->GetIntConstant(increment); 595f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 596f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 597f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 598f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 59969aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray HInstruction* new_array = new (allocator) HNewArray( 60069aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray constant_10, 60169aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray graph->GetCurrentMethod(), 60269aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray 0, 60369aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray Primitive::kPrimInt, 60469aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray graph->GetDexFile(), 60569aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray kQuickAllocArray); 606f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new_array); 607f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 608f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 609f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 610f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 611f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 612f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 613f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 614f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 615f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 616f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 617f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 618f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 619f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 620f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 621f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 622f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 623f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 624f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10); 625f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 626f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondGT); 627f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, constant_10); 628f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 629f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 630f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 631f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 632f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 6331abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 634f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 635f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0); 636154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayLength* array_length = new (allocator) HArrayLength(null_check, 0); 63722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 638f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 63922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 640f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 641f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 642f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 64322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik loop_body->AddInstruction(bounds_check); 644f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 645f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 646f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 647f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 648f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 649f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 650f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 65122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik return bounds_check; 652f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 653f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 65422af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) { 6558c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 656f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. } 65722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGE); 65822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 659f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 66022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 661f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 66222af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) { 6638c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 664f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. } 66522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 1, kCondGE); 66622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 667f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 66822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 669f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 67022af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) { 6718c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 672f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. } 67322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGT); 67422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 675f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 67622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 677f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 67822af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) { 6798c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 680f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. } 68122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 8, kCondGE); 68222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 683f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 684f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 685f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 686f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; } 68722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bikstatic HInstruction* BuildSSAGraph4(HGraph* graph, 68822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ArenaAllocator* allocator, 68922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik int initial, 69022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik IfCondition cond = kCondGE) { 691f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 692f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 693f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 694e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HInstruction* parameter = new (allocator) HParameterValue( 695e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle graph->GetDexFile(), 0, 0, Primitive::kPrimNot); 696f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 6978d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 6988d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_initial = graph->GetIntConstant(initial); 6998d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_1 = graph->GetIntConstant(1); 7008d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_10 = graph->GetIntConstant(10); 7018d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 702f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 703f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 704f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 705f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 706f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 707f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 708f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 709f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 710f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 711f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 712f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 713f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 714f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 715f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 716f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 717f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 718f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 719f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 720f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 721f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 722154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 723f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 724f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 725f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 726f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else if (cond == kCondGT) { 727f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, array_length); 728f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 729f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 730f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 731f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(null_check); 732f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(array_length); 733f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 734f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 7351abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 736f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 737f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 738154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (allocator) HArrayLength(null_check, 0); 739f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi); 740f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add_minus_1 = new (allocator) 741f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HAdd(Primitive::kPrimInt, sub, constant_minus_1); 74222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0); 743f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 74422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 745f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1); 746f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 747f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 748f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(sub); 749f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add_minus_1); 75022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik loop_body->AddInstruction(bounds_check); 751f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 752f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 753f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 754f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 755f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 756f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 757f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 75822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik return bounds_check; 759f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 760f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 76122af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) { 762f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. } 76322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0); 76422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 765f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 76622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 767f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 76822af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) { 769f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. } 77022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 1); 77122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 772f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 77322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 774f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 77522af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) { 776f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. } 77722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0, kCondGT); 77822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); 779f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 780f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 781f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 782f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// Bubble sort: 783f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// (Every array access bounds-check can be eliminated.) 784f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=0; i<array.length-1; i++) { 785f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int j=0; j<array.length-i-1; j++) { 786f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (array[j] > array[j+1]) { 787f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int temp = array[j+1]; 788f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// array[j+1] = array[j]; 789f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// array[j] = temp; 790f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 791f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 792f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 79322af3bee34d0ab1a4bd186c71ccab00366882259Aart BikTEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) { 79422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 79522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(entry); 79622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->SetEntryBlock(entry); 797e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle HInstruction* parameter = new (&allocator_) HParameterValue( 798e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); 799f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 8008d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 80122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_0 = graph_->GetIntConstant(0); 80222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_minus_1 = graph_->GetIntConstant(-1); 80322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* constant_1 = graph_->GetIntConstant(1); 804f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 80522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* block = new (&allocator_) HBasicBlock(graph_); 80622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(block); 807f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 80822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik block->AddInstruction(new (&allocator_) HGoto()); 80922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 81022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 81122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(exit); 81222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik exit->AddInstruction(new (&allocator_) HExit()); 81322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 81422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* outer_header = new (&allocator_) HBasicBlock(graph_); 81522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(outer_header); 81622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HPhi* phi_i = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); 81722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0); 818154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 81922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HAdd* add = new (&allocator_) HAdd(Primitive::kPrimInt, array_length, constant_minus_1); 82022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(phi_i, add); 82122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HIf* if_inst = new (&allocator_) HIf(cmp); 822f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddPhi(phi_i); 823f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(null_check); 824f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(array_length); 825f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(add); 826f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(cmp); 827f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(if_inst); 8281abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi_i->AddInput(constant_0); 829f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 83022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* inner_header = new (&allocator_) HBasicBlock(graph_); 83122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(inner_header); 83222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HPhi* phi_j = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); 83322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 834154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 83522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HSub* sub = new (&allocator_) HSub(Primitive::kPrimInt, array_length, phi_i); 83622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik add = new (&allocator_) HAdd(Primitive::kPrimInt, sub, constant_minus_1); 83722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik cmp = new (&allocator_) HGreaterThanOrEqual(phi_j, add); 83822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik if_inst = new (&allocator_) HIf(cmp); 839f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddPhi(phi_j); 840f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(null_check); 841f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(array_length); 842f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(sub); 843f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(add); 844f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(cmp); 845f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(if_inst); 8461abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi_j->AddInput(constant_0); 847f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 84822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* inner_body_compare = new (&allocator_) HBasicBlock(graph_); 84922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(inner_body_compare); 85022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 851154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 85222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check1 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 85322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HArrayGet* array_get_j = new (&allocator_) 854154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayGet(null_check, bounds_check1, Primitive::kPrimInt, 0); 855f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(null_check); 856f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_length); 857f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(bounds_check1); 858f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_get_j); 85922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 86022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 861154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 86222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBoundsCheck* bounds_check2 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 86322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HArrayGet* array_get_j_plus_1 = new (&allocator_) 864154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayGet(null_check, bounds_check2, Primitive::kPrimInt, 0); 86522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik cmp = new (&allocator_) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1); 86622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik if_inst = new (&allocator_) HIf(cmp); 867f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(j_plus_1); 868f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(null_check); 869f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_length); 870f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(bounds_check2); 871f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_get_j_plus_1); 872f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(cmp); 873f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(if_inst); 874f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 87522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* inner_body_swap = new (&allocator_) HBasicBlock(graph_); 87622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(inner_body_swap); 87722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 878f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // temp = array[j+1] 87922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 880154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 88122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check3 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 88222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik array_get_j_plus_1 = new (&allocator_) 883154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayGet(null_check, bounds_check3, Primitive::kPrimInt, 0); 884f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(j_plus_1); 885f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 886f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 887f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check3); 888f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_get_j_plus_1); 889f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[j+1] = array[j] 89022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 891154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 89222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check4 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 89322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik array_get_j = new (&allocator_) 894154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle HArrayGet(null_check, bounds_check4, Primitive::kPrimInt, 0); 895f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 896f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 897f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check4); 898f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_get_j); 89922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 900154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 90122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check5 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 90222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HArraySet* array_set_j_plus_1 = new (&allocator_) 903f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0); 904f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 905f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 906f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check5); 907f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_set_j_plus_1); 908f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[j] = temp 90922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik null_check = new (&allocator_) HNullCheck(parameter, 0); 910154746b84b407cfd166b45e039b62e6a06dc3f39Calin Juravle array_length = new (&allocator_) HArrayLength(null_check, 0); 91122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* bounds_check6 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 91222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HArraySet* array_set_j = new (&allocator_) 913f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0); 914f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 915f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 916f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check6); 917f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_set_j); 91822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik inner_body_swap->AddInstruction(new (&allocator_) HGoto()); 919f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 92022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* inner_body_add = new (&allocator_) HBasicBlock(graph_); 92122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(inner_body_add); 92222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 923f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_add->AddInstruction(add); 92422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik inner_body_add->AddInstruction(new (&allocator_) HGoto()); 925f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi_j->AddInput(add); 926f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 92722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HBasicBlock* outer_body_add = new (&allocator_) HBasicBlock(graph_); 92822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik graph_->AddBlock(outer_body_add); 92922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_i, constant_1); 930f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_body_add->AddInstruction(add); 93122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik outer_body_add->AddInstruction(new (&allocator_) HGoto()); 932f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi_i->AddInput(add); 933f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 934f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(outer_header); 935f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddSuccessor(exit); 936f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddSuccessor(inner_header); 937f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddSuccessor(outer_body_add); 938f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddSuccessor(inner_body_compare); 939f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddSuccessor(inner_body_add); 940f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddSuccessor(inner_body_swap); 941f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddSuccessor(inner_body_add); 942f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_add->AddSuccessor(inner_header); 943f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_body_add->AddSuccessor(outer_header); 944f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 94522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RunBCE(); // gvn removes same bounds check already 946f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 947f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check1)); 948f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check2)); 949f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check3)); 950f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check4)); 951f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 952f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check6)); 953f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 954f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 955f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} // namespace art 956