bounds_check_elimination_test.cc revision 69aa60163989c33a008115205d39732a76ecc1dc
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" 210304e182adee81be32c744fd3c0d28add29974ffMingyao Yang#include "instruction_simplifier.h" 22f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "nodes.h" 23f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "optimizing_unit_test.h" 24827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray#include "side_effects_analysis.h" 25f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 26f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang#include "gtest/gtest.h" 27f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 28f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangnamespace art { 29f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 300304e182adee81be32c744fd3c0d28add29974ffMingyao Yangstatic void RunSimplifierAndGvn(HGraph* graph) { 310304e182adee81be32c744fd3c0d28add29974ffMingyao Yang InstructionSimplifier simplify(graph); 320304e182adee81be32c744fd3c0d28add29974ffMingyao Yang simplify.Run(); 33e6f171514c9c499bd0a137aff6bd8a7a79d2682aNicolas Geoffray SideEffectsAnalysis side_effects(graph); 34e6f171514c9c499bd0a137aff6bd8a7a79d2682aNicolas Geoffray side_effects.Run(); 35827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray GVNOptimization(graph, side_effects).Run(); 36e6f171514c9c499bd0a137aff6bd8a7a79d2682aNicolas Geoffray} 37e6f171514c9c499bd0a137aff6bd8a7a79d2682aNicolas Geoffray 38f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (i < 0) { array[i] = 1; // Can't eliminate. } 39f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// else if (i >= array.length) { array[i] = 1; // Can't eliminate. } 40f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// else { array[i] = 1; // Can eliminate. } 41f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) { 42f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 43f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 44f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 450a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 461152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 47f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 48f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 49f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 50f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 51f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter1 = new (&allocator) 52f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimNot); // array 53f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter2 = new (&allocator) 54f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimInt); // i 55f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 56f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 578d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 588d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_1 = graph->GetIntConstant(1); 598d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_0 = graph->GetIntConstant(0); 60f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 61f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); 62f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block1); 63f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, constant_0); 64f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HIf* if_inst = new (&allocator) HIf(cmp); 65f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 66f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 67f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 68f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 69f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); 70f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block2); 71f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); 72f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 73f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check2 = new (&allocator) 74f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 75f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set = new (&allocator) HArraySet( 76f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0); 77f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(null_check); 78f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_length); 79f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(bounds_check2); 80f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_set); 81f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 82f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); 83f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block3); 84f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter1, 0); 85f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 86f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (&allocator) HLessThan(parameter2, array_length); 87f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp); 88f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(null_check); 89f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_length); 90f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(cmp); 91f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(if_inst); 92f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 93f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block4 = new (&allocator) HBasicBlock(graph); 94f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block4); 95f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter1, 0); 96f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 97f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check4 = new (&allocator) 98f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 99f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_set = new (&allocator) HArraySet( 100f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 101f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(null_check); 102f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(array_length); 103f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(bounds_check4); 104f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(array_set); 105f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 106f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block5 = new (&allocator) HBasicBlock(graph); 107f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block5); 108f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter1, 0); 109f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 110f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check5 = new (&allocator) 111f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 112f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_set = new (&allocator) HArraySet( 113f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 114f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(null_check); 115f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(array_length); 116f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(bounds_check5); 117f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(array_set); 118f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 119f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 120f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 121f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddSuccessor(exit); 122f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddSuccessor(exit); 123f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddSuccessor(exit); 124f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 125f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 126f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddSuccessor(block3); // True successor 127f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddSuccessor(block2); // False successor 128f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 129f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(block5); // True successor 130f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(block4); // False successor 131f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 132f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 1330304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 134f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 135f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 136f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check2)); 137f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check4)); 138f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 139f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 140f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 141f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (i > 0) { 142f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// // Positive number plus MAX_INT will overflow and be negative. 143f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int j = i + Integer.MAX_VALUE; 144f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (j < array.length) array[j] = 1; // Can't eliminate. 145f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 146f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) { 147f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 148f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 149f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1500a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 1511152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 152f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 153f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 154f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 155f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 156f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter1 = new (&allocator) 157f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimNot); // array 158f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter2 = new (&allocator) 159f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimInt); // i 160f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 161f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 1628d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 1638d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_1 = graph->GetIntConstant(1); 1648d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_0 = graph->GetIntConstant(0); 1658d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_max_int = graph->GetIntConstant(INT_MAX); 166f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 167f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); 168f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block1); 169f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = new (&allocator) HLessThanOrEqual(parameter2, constant_0); 170f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HIf* if_inst = new (&allocator) HIf(cmp); 171f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 172f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 173f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 174f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 175f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); 176f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block2); 177f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (&allocator) HAdd(Primitive::kPrimInt, parameter2, constant_max_int); 178f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); 179f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 180f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp2 = new (&allocator) HGreaterThanOrEqual(add, array_length); 181f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp2); 182f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(add); 183f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(null_check); 184f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_length); 185f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(cmp2); 186f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(if_inst); 187f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 188f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); 189f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block3); 190f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check = new (&allocator) 191f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(add, array_length, 0); 192f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set = new (&allocator) HArraySet( 193f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 194f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(bounds_check); 195f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_set); 196f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 197f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 198f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 199f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 2000418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(exit); // true successor 2010418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(block2); // false successor 2020418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(exit); // true successor 2030418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(block3); // false successor 204f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(exit); 205f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 206f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 2070304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 208f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 209f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 210f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 211f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 212f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 213f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (i < array.length) { 214f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int j = i - Integer.MAX_VALUE; 215f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// j = j - Integer.MAX_VALUE; // j is (i+2) after substracting MAX_INT twice 216f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (j > 0) array[j] = 1; // Can't eliminate. 217f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 218f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) { 219f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 220f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 221f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 2220a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 2231152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 224f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 225f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 226f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 227f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 228f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter1 = new (&allocator) 229f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimNot); // array 230f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter2 = new (&allocator) 231f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimInt); // i 232f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 233f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 2348d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 2358d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_1 = graph->GetIntConstant(1); 2368d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_0 = graph->GetIntConstant(0); 2378d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_max_int = graph->GetIntConstant(INT_MAX); 238f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 239f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); 240f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block1); 241f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); 242f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 243f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, array_length); 244f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HIf* if_inst = new (&allocator) HIf(cmp); 245f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(null_check); 246f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(array_length); 247f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 248f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 249f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 250f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 251f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); 252f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block2); 253f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* sub1 = new (&allocator) HSub(Primitive::kPrimInt, parameter2, constant_max_int); 254f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* sub2 = new (&allocator) HSub(Primitive::kPrimInt, sub1, constant_max_int); 255f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp2 = new (&allocator) HLessThanOrEqual(sub2, constant_0); 256f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp2); 257f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(sub1); 258f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(sub2); 259f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(cmp2); 260f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(if_inst); 261f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 262f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); 263f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block3); 264f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check = new (&allocator) 265f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(sub2, array_length, 0); 266f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set = new (&allocator) HArraySet( 267f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 268f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(bounds_check); 269f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_set); 270f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 271f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 272f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 273f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 2740418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(exit); // true successor 2750418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(block2); // false successor 2760418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(exit); // true successor 2770418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(block3); // false successor 278f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(exit); 279f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 280f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 2810304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 282f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 283f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 284f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 285f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 286f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 2870ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe// array[6] = 1; // Can't eliminate. 288d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang// array[5] = 1; // Can eliminate. 289d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang// array[4] = 1; // Can eliminate. 290f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) { 291f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 292f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 293f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 2940a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 2951152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 296f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 297f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 298f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 299f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 300f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); 301f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 3028d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 3038d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_5 = graph->GetIntConstant(5); 3048d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_4 = graph->GetIntConstant(4); 3058d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_6 = graph->GetIntConstant(6); 3068d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_1 = graph->GetIntConstant(1); 307f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 308f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (&allocator) HBasicBlock(graph); 309f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 310f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 311f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 312f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0); 313f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 314d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck* bounds_check6 = new (&allocator) 315d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck(constant_6, array_length, 0); 3160ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe HInstruction* array_set = new (&allocator) HArraySet( 317d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0); 318f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 319f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 320d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang block->AddInstruction(bounds_check6); 321f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_set); 322f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 323f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 324f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 325d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck* bounds_check5 = new (&allocator) 326d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck(constant_5, array_length, 0); 327f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_set = new (&allocator) HArraySet( 328d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 329f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 330f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 331d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang block->AddInstruction(bounds_check5); 332f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_set); 333f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 3340ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe null_check = new (&allocator) HNullCheck(parameter, 0); 3350ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe array_length = new (&allocator) HArrayLength(null_check); 336d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck* bounds_check4 = new (&allocator) 337d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang HBoundsCheck(constant_4, array_length, 0); 3380ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe array_set = new (&allocator) HArraySet( 339d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 3400ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(null_check); 3410ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(array_length); 342d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang block->AddInstruction(bounds_check4); 3430ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(array_set); 3440ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe 345f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (&allocator) HGoto()); 346f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 347f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 348f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 349f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(exit); 350f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 351f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 352f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 3530304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 354f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 355f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 3560ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe ASSERT_FALSE(IsRemoved(bounds_check6)); 357d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 358d43b3ac88cd46b8815890188c9c2b9a3f1564648Mingyao Yang ASSERT_TRUE(IsRemoved(bounds_check4)); 359f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 360f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 361f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=initial; i<array.length; i+=increment) { array[i] = 10; } 362f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangstatic HGraph* BuildSSAGraph1(ArenaAllocator* allocator, 363f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction** bounds_check, 364f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int initial, 365f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int increment, 366f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang IfCondition cond = kCondGE) { 3670a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(allocator); 3681152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 369f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 370f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 371f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 372f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 373f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 374f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 3758d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 3768d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_initial = graph->GetIntConstant(initial); 3778d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_increment = graph->GetIntConstant(increment); 3788d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_10 = graph->GetIntConstant(10); 379f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 380f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 381f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 382f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 383f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 384f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 385f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 386f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 387f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 388f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 389f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 390f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 391f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 392f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 393f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 394f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 395f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 396f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 397f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 398f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 399f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_length = new (allocator) HArrayLength(null_check); 400f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 401f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 402f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 403f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 404f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondGT); 405f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, array_length); 406f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 407f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 408f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 409f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(null_check); 410f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(array_length); 411f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 412f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 4131abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 414f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 415f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 416f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (allocator) HArrayLength(null_check); 417f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 418f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 419f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); 420f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 421f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 422f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 423f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 424f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(*bounds_check); 425f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 426f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 427f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 428f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 429f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 430f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 431f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 432f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang return graph; 433f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 434f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 435f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) { 436f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 437f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 438f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 439f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. } 440f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check = nullptr; 441f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1); 442f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 443f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 444f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 445f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 446f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 447f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // This time add gvn. Need gvn to eliminate the second 448f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // HArrayLength which uses the null check as its input. 449f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1); 450f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4510304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 452f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_after_gvn(graph); 453f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_after_gvn.Run(); 454f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 455f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 456f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. } 457f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1); 458f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4590304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 460f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); 461f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_1.Run(); 462f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 463f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 464f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. } 465f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1); 466f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4670304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 468f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph); 469f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_minus_1.Run(); 470f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 471f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 472f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. } 473f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT); 474f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4750304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 476f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); 477f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_greater_than.Run(); 478f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 479f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 480f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i += 2) { 481f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[i] = 10; // Can't eliminate due to overflow concern. } 482f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 2); 483f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4840304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 485f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_increment_2(graph); 486f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_increment_2.Run(); 487f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 488f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 489f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. } 490f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2); 491f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4920304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 493f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph); 494f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_increment_2_from_1.Run(); 495f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 496f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 497f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 498f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; } 499f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangstatic HGraph* BuildSSAGraph2(ArenaAllocator* allocator, 500f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction** bounds_check, 501f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int initial, 502f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int increment = -1, 503f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang IfCondition cond = kCondLE) { 5040a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(allocator); 5051152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 506f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 507f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 508f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 509f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 510f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 511f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 5128d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 5138d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_initial = graph->GetIntConstant(initial); 5148d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_increment = graph->GetIntConstant(increment); 5158d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 5168d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_10 = graph->GetIntConstant(10); 517f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 518f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 519f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 520f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 521f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 522f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_length = new (allocator) HArrayLength(null_check); 523f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 524f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 525f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 526f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 527f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 528f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 529f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 530f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 531f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 532f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 533f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 534f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 535f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 536f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 537f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 538f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 539f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 540f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 541f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondLE) { 542f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HLessThanOrEqual(phi, constant_initial); 543f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 544f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondLT); 545f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HLessThan(phi, constant_initial); 546f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 547f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 548f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 549f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 550f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 5511abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(array_length); 552f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 553f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1); 554f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 555f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (allocator) HArrayLength(null_check); 556f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang *bounds_check = new (allocator) HBoundsCheck(add, array_length, 0); 557f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 558f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); 559f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 560f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 561f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 562f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 563f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(*bounds_check); 564f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 565f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add_phi); 566f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 567f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 568f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 569f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 570f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 571f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang return graph; 572f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 573f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 574f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) { 575f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 576f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 577f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 578f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. } 579f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check = nullptr; 580f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = BuildSSAGraph2(&allocator, &bounds_check, 0); 581f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 582f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 583f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 584f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 585f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 586f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // This time add gvn. Need gvn to eliminate the second 587f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // HArrayLength which uses the null check as its input. 588f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, 0); 589f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 5900304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 591f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_after_gvn(graph); 592f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_after_gvn.Run(); 593f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 594f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 595f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. } 596f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, 1); 597f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 5980304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 599f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); 600f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_1.Run(); 601f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 602f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 603f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. } 604f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, -1); 605f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 6060304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 607f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph); 608f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_minus_1.Run(); 609f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 610f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 611f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. } 612f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -1, kCondLT); 613f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 6140304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 615f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_less_than(graph); 616f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_less_than.Run(); 617f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 618f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 619f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. } 620f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2); 621f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 6220304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 623f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph); 624f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_increment_minus_2.Run(); 625f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 626f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 627f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 6288c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang// int[] array = new int[10]; 629f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=0; i<10; i+=increment) { array[i] = 10; } 630f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangstatic HGraph* BuildSSAGraph3(ArenaAllocator* allocator, 631f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction** bounds_check, 632f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int initial, 633f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int increment, 634f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang IfCondition cond) { 6350a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(allocator); 6361152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 637f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 638f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 639f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 640f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 6418d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 6428d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_10 = graph->GetIntConstant(10); 6438d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_initial = graph->GetIntConstant(initial); 6448d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_increment = graph->GetIntConstant(increment); 645f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 646f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 647f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 648f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 64969aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray HInstruction* new_array = new (allocator) HNewArray( 65069aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray constant_10, 65169aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray graph->GetCurrentMethod(), 65269aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray 0, 65369aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray Primitive::kPrimInt, 65469aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray graph->GetDexFile(), 65569aa60163989c33a008115205d39732a76ecc1dcNicolas Geoffray kQuickAllocArray); 656f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new_array); 657f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 658f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 659f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 660f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 661f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 662f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 663f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 664f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 665f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 666f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 667f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 668f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 669f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 670f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 671f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 672f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 673f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 674f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10); 675f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 676f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondGT); 677f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, constant_10); 678f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 679f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 680f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 681f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 682f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 6831abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 684f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 685f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0); 686f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (allocator) HArrayLength(null_check); 687f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 688f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 689f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); 690f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 691f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 692f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 693f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(*bounds_check); 694f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 695f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 696f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 697f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 698f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 699f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 700f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 701f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang return graph; 702f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 703f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 704f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) { 705f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 706f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 707f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 7088c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 709f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. } 710f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check = nullptr; 711f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE); 712f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 7130304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 714f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_after_gvn(graph); 715f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_after_gvn.Run(); 716f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 717f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 7188c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 719f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. } 720f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE); 721f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 7220304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 723f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); 724f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_1.Run(); 725f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 726f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 7278c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 728f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. } 729f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT); 730f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 7310304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 732f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); 733f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_greater_than.Run(); 734f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 735f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 7368c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 737f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. } 738f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE); 739f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 7400304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 741f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_increment_8(graph); 742f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_increment_8.Run(); 743f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 744f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 745f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 746f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; } 747f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangstatic HGraph* BuildSSAGraph4(ArenaAllocator* allocator, 748f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction** bounds_check, 749f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int initial, 750f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang IfCondition cond = kCondGE) { 7510a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(allocator); 7521152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 753f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 754f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 755f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 756f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 757f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 758f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 7598d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 7608d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_initial = graph->GetIntConstant(initial); 7618d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_1 = graph->GetIntConstant(1); 7628d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_10 = graph->GetIntConstant(10); 7638d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 764f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 765f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 766f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 767f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 768f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 769f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 770f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 771f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 772f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 773f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 774f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 775f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 776f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 777f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 778f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 779f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 780f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 781f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 782f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 783f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 784f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_length = new (allocator) HArrayLength(null_check); 785f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 786f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 787f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 788f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else if (cond == kCondGT) { 789f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, array_length); 790f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 791f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 792f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 793f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(null_check); 794f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(array_length); 795f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 796f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 7971abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 798f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 799f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 800f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (allocator) HArrayLength(null_check); 801f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi); 802f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add_minus_1 = new (allocator) 803f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HAdd(Primitive::kPrimInt, sub, constant_minus_1); 804f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang *bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0); 805f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 806f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); 807f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1); 808f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 809f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 810f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(sub); 811f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add_minus_1); 812f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(*bounds_check); 813f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 814f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 815f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 816f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 817f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 818f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 819f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 820f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang return graph; 821f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 822f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 823f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination4) { 824f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 825f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 826f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 827f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. } 828f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check = nullptr; 829f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = BuildSSAGraph4(&allocator, &bounds_check, 0); 830f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 831f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 832f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 833f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 834f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 835f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // This time add gvn. Need gvn to eliminate the second 836f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // HArrayLength which uses the null check as its input. 837f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph4(&allocator, &bounds_check, 0); 838f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 8390304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 840f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_after_gvn(graph); 841f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_after_gvn.Run(); 842f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 843f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 844f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. } 845f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph4(&allocator, &bounds_check, 1); 846f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 8470304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 848f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); 849f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_1.Run(); 850f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 851f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 852f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. } 853f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph4(&allocator, &bounds_check, 0, kCondGT); 854f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 8550304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 856f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); 857f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_greater_than.Run(); 858f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 859f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 860f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 861f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// Bubble sort: 862f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// (Every array access bounds-check can be eliminated.) 863f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=0; i<array.length-1; i++) { 864f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int j=0; j<array.length-i-1; j++) { 865f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (array[j] > array[j+1]) { 866f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int temp = array[j+1]; 867f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// array[j+1] = array[j]; 868f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// array[j] = temp; 869f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 870f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 871f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 872f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) { 873f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 874f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 875f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 8760a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 8771152c926076a760490085c4497c3f117fa8da891Mark Mendell graph->SetHasBoundsChecks(true); 878f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 879f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 880f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 881f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 882f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); 883f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 8848d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil 8858d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_0 = graph->GetIntConstant(0); 8868d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 8878d5b8b295930aaa43255c4f0b74ece3ee8b43a47David Brazdil HInstruction* constant_1 = graph->GetIntConstant(1); 888f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 889f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (&allocator) HBasicBlock(graph); 890f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 891f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 892f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (&allocator) HGoto()); 893f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 894f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 895f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 896f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 897f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 898f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* outer_header = new (&allocator) HBasicBlock(graph); 899f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(outer_header); 900f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi_i = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt); 901f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0); 902f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 903f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HAdd* add = new (&allocator) HAdd(Primitive::kPrimInt, array_length, constant_minus_1); 904f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(phi_i, add); 905f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HIf* if_inst = new (&allocator) HIf(cmp); 906f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddPhi(phi_i); 907f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(null_check); 908f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(array_length); 909f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(add); 910f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(cmp); 911f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(if_inst); 9121abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi_i->AddInput(constant_0); 913f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 914f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph); 915f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(inner_header); 916f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt); 917f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 918f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 919f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HSub* sub = new (&allocator) HSub(Primitive::kPrimInt, array_length, phi_i); 920f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang add = new (&allocator) HAdd(Primitive::kPrimInt, sub, constant_minus_1); 921f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (&allocator) HGreaterThanOrEqual(phi_j, add); 922f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp); 923f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddPhi(phi_j); 924f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(null_check); 925f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(array_length); 926f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(sub); 927f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(add); 928f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(cmp); 929f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(if_inst); 9301abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi_j->AddInput(constant_0); 931f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 932f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* inner_body_compare = new (&allocator) HBasicBlock(graph); 933f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(inner_body_compare); 934f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 935f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 936f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check1 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); 937f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet* array_get_j = new (&allocator) 938f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet(null_check, bounds_check1, Primitive::kPrimInt); 939f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(null_check); 940f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_length); 941f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(bounds_check1); 942f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_get_j); 943f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); 944f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 945f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 946f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check2 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); 947f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet* array_get_j_plus_1 = new (&allocator) 948f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet(null_check, bounds_check2, Primitive::kPrimInt); 949f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (&allocator) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1); 950f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp); 951f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(j_plus_1); 952f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(null_check); 953f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_length); 954f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(bounds_check2); 955f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_get_j_plus_1); 956f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(cmp); 957f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(if_inst); 958f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 959f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* inner_body_swap = new (&allocator) HBasicBlock(graph); 960f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(inner_body_swap); 961f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); 962f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // temp = array[j+1] 963f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 964f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 965f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check3 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); 966f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_get_j_plus_1 = new (&allocator) 967f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet(null_check, bounds_check3, Primitive::kPrimInt); 968f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(j_plus_1); 969f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 970f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 971f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check3); 972f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_get_j_plus_1); 973f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[j+1] = array[j] 974f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 975f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 976f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check4 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); 977f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_get_j = new (&allocator) 978f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet(null_check, bounds_check4, Primitive::kPrimInt); 979f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 980f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 981f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check4); 982f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_get_j); 983f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 984f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 985f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check5 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); 986f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set_j_plus_1 = new (&allocator) 987f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0); 988f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 989f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 990f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check5); 991f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_set_j_plus_1); 992f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[j] = temp 993f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 994f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 995f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check6 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); 996f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set_j = new (&allocator) 997f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0); 998f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 999f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 1000f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check6); 1001f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_set_j); 1002f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(new (&allocator) HGoto()); 1003f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1004f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* inner_body_add = new (&allocator) HBasicBlock(graph); 1005f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(inner_body_add); 1006f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang add = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); 1007f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_add->AddInstruction(add); 1008f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_add->AddInstruction(new (&allocator) HGoto()); 1009f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi_j->AddInput(add); 1010f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1011f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* outer_body_add = new (&allocator) HBasicBlock(graph); 1012f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(outer_body_add); 1013f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang add = new (&allocator) HAdd(Primitive::kPrimInt, phi_i, constant_1); 1014f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_body_add->AddInstruction(add); 1015f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_body_add->AddInstruction(new (&allocator) HGoto()); 1016f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi_i->AddInput(add); 1017f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1018f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(outer_header); 1019f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddSuccessor(exit); 1020f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddSuccessor(inner_header); 1021f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddSuccessor(outer_body_add); 1022f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddSuccessor(inner_body_compare); 1023f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddSuccessor(inner_body_add); 1024f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddSuccessor(inner_body_swap); 1025f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddSuccessor(inner_body_add); 1026f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_add->AddSuccessor(inner_header); 1027f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_body_add->AddSuccessor(outer_header); 1028f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1029f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 10300304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 1031f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // gvn should remove the same bounds check. 1032f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check1)); 1033f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check2)); 1034f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check3)); 1035f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check4)); 1036f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 1037f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check6)); 1038f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1039f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 1040f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 1041f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check1)); 1042f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check2)); 1043f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check3)); 1044f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check4)); 1045f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 1046f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check6)); 1047f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 1048f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1049f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} // namespace art 1050