bounds_check_elimination_test.cc revision 0ba627337274ccfb8c9cb9bf23fffb1e1b9d1430
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 45f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (&allocator) HGraph(&allocator); 466775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(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 HInstruction* constant_1 = new (&allocator) HIntConstant(1); 56f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_0 = new (&allocator) HIntConstant(0); 57f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 58f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 59f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_1); 60f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_0); 61f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 62f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); 63f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block1); 64f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, constant_0); 65f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HIf* if_inst = new (&allocator) HIf(cmp); 66f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 67f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 68f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 69f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 70f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); 71f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block2); 72f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); 73f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 74f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check2 = new (&allocator) 75f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 76f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set = new (&allocator) HArraySet( 77f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0); 78f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(null_check); 79f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_length); 80f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(bounds_check2); 81f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_set); 82f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 83f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); 84f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block3); 85f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter1, 0); 86f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 87f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (&allocator) HLessThan(parameter2, array_length); 88f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp); 89f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(null_check); 90f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_length); 91f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(cmp); 92f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(if_inst); 93f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 94f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block4 = new (&allocator) HBasicBlock(graph); 95f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block4); 96f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter1, 0); 97f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 98f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check4 = new (&allocator) 99f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 100f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_set = new (&allocator) HArraySet( 101f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 102f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(null_check); 103f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(array_length); 104f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(bounds_check4); 105f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddInstruction(array_set); 106f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 107f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block5 = new (&allocator) HBasicBlock(graph); 108f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block5); 109f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter1, 0); 110f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 111f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check5 = new (&allocator) 112f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(parameter2, array_length, 0); 113f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_set = new (&allocator) HArraySet( 114f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 115f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(null_check); 116f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(array_length); 117f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(bounds_check5); 118f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddInstruction(array_set); 119f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 120f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 121f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 122f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddSuccessor(exit); 123f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block4->AddSuccessor(exit); 124f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block5->AddSuccessor(exit); 125f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 126f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 127f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddSuccessor(block3); // True successor 128f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddSuccessor(block2); // False successor 129f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 130f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(block5); // True successor 131f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(block4); // False successor 132f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 133f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 1340304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 135f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 136f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 137f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check2)); 138f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check4)); 139f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 140f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 141f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 142f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (i > 0) { 143f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// // Positive number plus MAX_INT will overflow and be negative. 144f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int j = i + Integer.MAX_VALUE; 145f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (j < array.length) array[j] = 1; // Can't eliminate. 146f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 147f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) { 148f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 149f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 150f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 151f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (&allocator) HGraph(&allocator); 1526775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(true); 153f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 154f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 155f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 156f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 157f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter1 = new (&allocator) 158f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimNot); // array 159f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter2 = new (&allocator) 160f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimInt); // i 161f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_1 = new (&allocator) HIntConstant(1); 162f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_0 = new (&allocator) HIntConstant(0); 163f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_max_int = new (&allocator) HIntConstant(INT_MAX); 164f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 165f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 166f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_1); 167f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_0); 168f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_max_int); 169f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 170f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); 171f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block1); 172f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = new (&allocator) HLessThanOrEqual(parameter2, constant_0); 173f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HIf* if_inst = new (&allocator) HIf(cmp); 174f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 175f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 176f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 177f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 178f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); 179f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block2); 180f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (&allocator) HAdd(Primitive::kPrimInt, parameter2, constant_max_int); 181f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); 182f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 183f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp2 = new (&allocator) HGreaterThanOrEqual(add, array_length); 184f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp2); 185f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(add); 186f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(null_check); 187f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(array_length); 188f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(cmp2); 189f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(if_inst); 190f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 191f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); 192f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block3); 193f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check = new (&allocator) 194f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(add, array_length, 0); 195f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set = new (&allocator) HArraySet( 196f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 197f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(bounds_check); 198f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_set); 199f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 200f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 201f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 202f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 2030418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(exit); // true successor 2040418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(block2); // false successor 2050418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(exit); // true successor 2060418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(block3); // false successor 207f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(exit); 208f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 209f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 2100304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 211f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 212f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 213f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 214f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 215f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 216f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (i < array.length) { 217f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int j = i - Integer.MAX_VALUE; 218f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// j = j - Integer.MAX_VALUE; // j is (i+2) after substracting MAX_INT twice 219f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (j > 0) array[j] = 1; // Can't eliminate. 220f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 221f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) { 222f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 223f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 224f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 225f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (&allocator) HGraph(&allocator); 2266775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(true); 227f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 228f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 229f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 230f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 231f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter1 = new (&allocator) 232f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimNot); // array 233f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter2 = new (&allocator) 234f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HParameterValue(0, Primitive::kPrimInt); // i 235f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_1 = new (&allocator) HIntConstant(1); 236f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_0 = new (&allocator) HIntConstant(0); 237f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_max_int = new (&allocator) HIntConstant(INT_MAX); 238f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter1); 239f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter2); 240f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_1); 241f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_0); 242f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_max_int); 243f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 244f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); 245f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block1); 246f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); 247f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 248f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, array_length); 249f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HIf* if_inst = new (&allocator) HIf(cmp); 250f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(null_check); 251f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(array_length); 252f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(cmp); 253f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block1->AddInstruction(if_inst); 254f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block1); 255f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 256f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); 257f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block2); 258f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* sub1 = new (&allocator) HSub(Primitive::kPrimInt, parameter2, constant_max_int); 259f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* sub2 = new (&allocator) HSub(Primitive::kPrimInt, sub1, constant_max_int); 260f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp2 = new (&allocator) HLessThanOrEqual(sub2, constant_0); 261f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp2); 262f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(sub1); 263f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(sub2); 264f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(cmp2); 265f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block2->AddInstruction(if_inst); 266f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 267f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); 268f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block3); 269f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check = new (&allocator) 270f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck(sub2, array_length, 0); 271f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set = new (&allocator) HArraySet( 272f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 273f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(bounds_check); 274f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddInstruction(array_set); 275f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 276f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 277f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 278f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 2790418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(exit); // true successor 2800418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block1->AddSuccessor(block2); // false successor 2810418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(exit); // true successor 2820418b5b20587c645b6bf9d8cb65d3d6a9f074d96Andreas Gampe block2->AddSuccessor(block3); // false successor 283f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block3->AddSuccessor(exit); 284f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 285f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 2860304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 287f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 288f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 289f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 290f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 291f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 2920ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe// array[5] = 1; // Can't eliminate. 293e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang// array[4] = 1; // Can eliminate. 2940ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe// array[6] = 1; // Can't eliminate. 295f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) { 296f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 297f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 298f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 299f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (&allocator) HGraph(&allocator); 3006775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(true); 301f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 302f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 303f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 304f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 305f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); 306f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_5 = new (&allocator) HIntConstant(5); 307f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_4 = new (&allocator) HIntConstant(4); 308f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_6 = new (&allocator) HIntConstant(6); 309f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_1 = new (&allocator) HIntConstant(1); 310f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 311f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_5); 312f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_4); 313f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_6); 314f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_1); 315f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 316f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (&allocator) HBasicBlock(graph); 317f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 318f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 319f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 320f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0); 321f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 322e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang HBoundsCheck* bounds_check5 = new (&allocator) 323e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang HBoundsCheck(constant_5, array_length, 0); 3240ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe HInstruction* array_set = new (&allocator) HArraySet( 325e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 326f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 327f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 328e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang block->AddInstruction(bounds_check5); 329f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_set); 330f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 331f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 332f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 333e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang HBoundsCheck* bounds_check4 = new (&allocator) 334e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang HBoundsCheck(constant_4, array_length, 0); 335f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_set = new (&allocator) HArraySet( 336e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 337f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 338f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 339e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang block->AddInstruction(bounds_check4); 340f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_set); 341f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 3420ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe null_check = new (&allocator) HNullCheck(parameter, 0); 3430ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe array_length = new (&allocator) HArrayLength(null_check); 3440ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe HBoundsCheck* bounds_check6 = new (&allocator) 3450ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe HBoundsCheck(constant_6, array_length, 0); 3460ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe array_set = new (&allocator) HArraySet( 3470ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0); 3480ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(null_check); 3490ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(array_length); 3500ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(bounds_check6); 3510ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe block->AddInstruction(array_set); 3520ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe 353f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (&allocator) HGoto()); 354f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 355f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 356f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 357f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(exit); 358f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 359f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 360f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 3610304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 362f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 363f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 3640ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe ASSERT_FALSE(IsRemoved(bounds_check5)); 365e295e6ec5beaea31be5d7d3c996cd8cfa2053129Mingyao Yang ASSERT_TRUE(IsRemoved(bounds_check4)); 3660ba627337274ccfb8c9cb9bf23fffb1e1b9d1430Andreas Gampe ASSERT_FALSE(IsRemoved(bounds_check6)); 367f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 368f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 369f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=initial; i<array.length; i+=increment) { array[i] = 10; } 370f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangstatic HGraph* BuildSSAGraph1(ArenaAllocator* allocator, 371f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction** bounds_check, 372f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int initial, 373f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int increment, 374f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang IfCondition cond = kCondGE) { 375f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (allocator) HGraph(allocator); 3766775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(true); 377f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 378f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 379f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 380f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 381f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 382f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_initial = new (allocator) HIntConstant(initial); 383f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_increment = new (allocator) HIntConstant(increment); 384f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_10 = new (allocator) HIntConstant(10); 385f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 386f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_initial); 387f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_increment); 388f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_10); 389f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 390f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 391f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 392f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 393f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 394f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 395f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 396f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 397f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 398f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 399f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 400f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 401f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 402f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 403f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 404f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 405f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 406f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 407f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 408f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 409f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_length = new (allocator) HArrayLength(null_check); 410f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 411f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 412f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 413f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 414f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondGT); 415f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, array_length); 416f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 417f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 418f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 419f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(null_check); 420f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(array_length); 421f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 422f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 4231abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 424f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 425f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 426f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (allocator) HArrayLength(null_check); 427f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 428f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 429f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); 430f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 431f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 432f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 433f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 434f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(*bounds_check); 435f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 436f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 437f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 438f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 439f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 440f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 441f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 442f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang return graph; 443f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 444f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 445f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) { 446f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 447f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 448f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 449f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. } 450f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check = nullptr; 451f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1); 452f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 453f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 454f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 455f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 456f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 457f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // This time add gvn. Need gvn to eliminate the second 458f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // HArrayLength which uses the null check as its input. 459f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1); 460f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4610304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 462f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_after_gvn(graph); 463f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_after_gvn.Run(); 464f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 465f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 466f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. } 467f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1); 468f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4690304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 470f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); 471f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_1.Run(); 472f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 473f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 474f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. } 475f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1); 476f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4770304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 478f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph); 479f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_minus_1.Run(); 480f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 481f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 482f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. } 483f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT); 484f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4850304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 486f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); 487f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_greater_than.Run(); 488f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 489f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 490f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i += 2) { 491f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[i] = 10; // Can't eliminate due to overflow concern. } 492f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 2); 493f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 4940304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 495f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_increment_2(graph); 496f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_increment_2.Run(); 497f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 498f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 499f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. } 500f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2); 501f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 5020304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 503f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph); 504f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_increment_2_from_1.Run(); 505f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 506f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 507f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 508f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; } 509f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangstatic HGraph* BuildSSAGraph2(ArenaAllocator* allocator, 510f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction** bounds_check, 511f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int initial, 512f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int increment = -1, 513f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang IfCondition cond = kCondLE) { 514f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (allocator) HGraph(allocator); 5156775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(true); 516f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 517f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 518f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 519f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 520f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 521f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_initial = new (allocator) HIntConstant(initial); 522f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_increment = new (allocator) HIntConstant(increment); 523f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_minus_1 = new (allocator) HIntConstant(-1); 524f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_10 = new (allocator) HIntConstant(10); 525f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 526f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_initial); 527f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_increment); 528f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_minus_1); 529f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_10); 530f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 531f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 532f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 533f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 534f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 535f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_length = new (allocator) HArrayLength(null_check); 536f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(null_check); 537f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(array_length); 538f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 539f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 540f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 541f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 542f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 543f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 544f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 545f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 546f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 547f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 548f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 549f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 550f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 551f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 552f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 553f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 554f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondLE) { 555f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HLessThanOrEqual(phi, constant_initial); 556f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 557f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondLT); 558f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HLessThan(phi, constant_initial); 559f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 560f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 561f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 562f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 563f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 5641abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(array_length); 565f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 566f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1); 567f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 568f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (allocator) HArrayLength(null_check); 569f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang *bounds_check = new (allocator) HBoundsCheck(add, array_length, 0); 570f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 571f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); 572f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 573f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 574f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 575f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 576f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(*bounds_check); 577f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 578f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add_phi); 579f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 580f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 581f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 582f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 583f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 584f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang return graph; 585f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 586f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 587f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) { 588f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 589f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 590f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 591f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. } 592f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check = nullptr; 593f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = BuildSSAGraph2(&allocator, &bounds_check, 0); 594f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 595f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 596f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 597f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 598f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 599f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // This time add gvn. Need gvn to eliminate the second 600f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // HArrayLength which uses the null check as its input. 601f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, 0); 602f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 6030304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 604f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_after_gvn(graph); 605f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_after_gvn.Run(); 606f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 607f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 608f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. } 609f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, 1); 610f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 6110304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 612f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); 613f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_1.Run(); 614f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 615f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 616f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. } 617f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, -1); 618f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 6190304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 620f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph); 621f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_minus_1.Run(); 622f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 623f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 624f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. } 625f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -1, kCondLT); 626f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 6270304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 628f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_less_than(graph); 629f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_less_than.Run(); 630f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 631f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 632f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. } 633f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2); 634f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 6350304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 636f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph); 637f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_increment_minus_2.Run(); 638f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 639f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 640f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 6418c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang// int[] array = new int[10]; 642f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=0; i<10; i+=increment) { array[i] = 10; } 643f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangstatic HGraph* BuildSSAGraph3(ArenaAllocator* allocator, 644f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction** bounds_check, 645f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int initial, 646f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int increment, 647f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang IfCondition cond) { 648f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (allocator) HGraph(allocator); 6496775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(true); 650f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 651f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 652f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 653f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 654f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_10 = new (allocator) HIntConstant(10); 655f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_initial = new (allocator) HIntConstant(initial); 656f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_increment = new (allocator) HIntConstant(increment); 657f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_10); 658f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_initial); 659f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_increment); 660f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 661f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 662f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 663f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 664f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* new_array = new (allocator) 665cb1b00aedd94785e7599f18065a0b97b314e64f6Nicolas Geoffray HNewArray(constant_10, 0, Primitive::kPrimInt, kQuickAllocArray); 666f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new_array); 667f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 668f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 669f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 670f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 671f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 672f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 673f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 674f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 675f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 676f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 677f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 678f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 679f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 680f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 681f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 682f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 683f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 684f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10); 685f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else { 686f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang DCHECK(cond == kCondGT); 687f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, constant_10); 688f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 689f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 690f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 691f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 692f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 6931abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 694f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 695f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0); 696f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (allocator) HArrayLength(null_check); 697f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 698f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 699f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); 700f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 701f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 702f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 703f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(*bounds_check); 704f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 705f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 706f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 707f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 708f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 709f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 710f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 711f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang return graph; 712f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 713f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 714f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) { 715f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 716f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 717f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 7188c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 719f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. } 720f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check = nullptr; 721f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE); 722f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 7230304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 724f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_after_gvn(graph); 725f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_after_gvn.Run(); 726f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 727f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 7288c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 729f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. } 730f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE); 731f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 7320304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 733f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); 734f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_1.Run(); 735f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 736f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 7378c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 738f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. } 739f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT); 740f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 7410304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 742f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); 743f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_greater_than.Run(); 744f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 745f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 7468c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // int[] array = new int[10]; 747f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. } 748f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE); 749f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 7500304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 751f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_increment_8(graph); 752f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_increment_8.Run(); 753f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 754f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 755f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 756f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; } 757f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yangstatic HGraph* BuildSSAGraph4(ArenaAllocator* allocator, 758f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction** bounds_check, 759f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang int initial, 760f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang IfCondition cond = kCondGE) { 761f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (allocator) HGraph(allocator); 7626775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(true); 763f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 764f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (allocator) HBasicBlock(graph); 765f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 766f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 767f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 768f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_initial = new (allocator) HIntConstant(initial); 769f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_1 = new (allocator) HIntConstant(1); 770f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_10 = new (allocator) HIntConstant(10); 771f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_minus_1 = new (allocator) HIntConstant(-1); 772f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 773f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_initial); 774f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_1); 775f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_10); 776f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_minus_1); 777f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 778f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (allocator) HBasicBlock(graph); 779f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 780f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 781f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (allocator) HGoto()); 782f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 783f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 784f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 785f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (allocator) HBasicBlock(graph); 786f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 787f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_header); 788f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(loop_body); 789f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 790f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(loop_header); 791f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(exit); // true successor 792f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddSuccessor(loop_body); // false successor 793f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddSuccessor(loop_header); 794f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 795f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 796f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 797f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_length = new (allocator) HArrayLength(null_check); 798f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = nullptr; 799f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if (cond == kCondGE) { 800f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 801f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } else if (cond == kCondGT) { 802f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (allocator) HGreaterThan(phi, array_length); 803f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang } 804f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* if_inst = new (allocator) HIf(cmp); 805f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddPhi(phi); 806f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(null_check); 807f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(array_length); 808f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(cmp); 809f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_header->AddInstruction(if_inst); 8101abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi->AddInput(constant_initial); 811f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 812f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (allocator) HNullCheck(parameter, 0); 813f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (allocator) HArrayLength(null_check); 814f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi); 815f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add_minus_1 = new (allocator) 816f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HAdd(Primitive::kPrimInt, sub, constant_minus_1); 817f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang *bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0); 818f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* array_set = new (allocator) HArraySet( 819f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); 820f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1); 821f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(null_check); 822f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_length); 823f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(sub); 824f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add_minus_1); 825f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(*bounds_check); 826f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(array_set); 827f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(add); 828f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang loop_body->AddInstruction(new (allocator) HGoto()); 829f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi->AddInput(add); 830f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 831f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (allocator) HExit()); 832f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 833f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang return graph; 834f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 835f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 836f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination4) { 837f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 838f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 839f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 840f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. } 841f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check = nullptr; 842f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = BuildSSAGraph4(&allocator, &bounds_check, 0); 843f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 844f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 845f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 846f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 847f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 848f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // This time add gvn. Need gvn to eliminate the second 849f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // HArrayLength which uses the null check as its input. 850f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph4(&allocator, &bounds_check, 0); 851f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 8520304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 853f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_after_gvn(graph); 854f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_after_gvn.Run(); 855f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 856f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 857f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. } 858f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph4(&allocator, &bounds_check, 1); 859f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 8600304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 861f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); 862f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_initial_1.Run(); 863f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check)); 864f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 865f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. } 866f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph = BuildSSAGraph4(&allocator, &bounds_check, 0, kCondGT); 867f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 8680304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 869f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); 870f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination_with_greater_than.Run(); 871f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check)); 872f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 873f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 874f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// Bubble sort: 875f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// (Every array access bounds-check can be eliminated.) 876f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int i=0; i<array.length-1; i++) { 877f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// for (int j=0; j<array.length-i-1; j++) { 878f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// if (array[j] > array[j+1]) { 879f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// int temp = array[j+1]; 880f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// array[j+1] = array[j]; 881f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// array[j] = temp; 882f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 883f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 884f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang// } 885f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao YangTEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) { 886f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaPool pool; 887f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ArenaAllocator allocator(&pool); 888f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 889f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HGraph* graph = new (&allocator) HGraph(&allocator); 8906775ba544283897c7bd0cac9e7c70c354b962a5aMingyao Yang graph->SetHasArrayAccesses(true); 891f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 892f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 893f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(entry); 894f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->SetEntryBlock(entry); 895f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); 896f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_0 = new (&allocator) HIntConstant(0); 897f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_minus_1 = new (&allocator) HIntConstant(-1); 898f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* constant_1 = new (&allocator) HIntConstant(1); 899f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(parameter); 900f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_0); 901f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_minus_1); 902f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddInstruction(constant_1); 903f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 904f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* block = new (&allocator) HBasicBlock(graph); 905f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(block); 906f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang entry->AddSuccessor(block); 907f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddInstruction(new (&allocator) HGoto()); 908f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 909f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 910f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(exit); 911f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang exit->AddInstruction(new (&allocator) HExit()); 912f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 913f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* outer_header = new (&allocator) HBasicBlock(graph); 914f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(outer_header); 915f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi_i = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt); 916f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0); 917f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayLength* array_length = new (&allocator) HArrayLength(null_check); 918f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HAdd* add = new (&allocator) HAdd(Primitive::kPrimInt, array_length, constant_minus_1); 919f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(phi_i, add); 920f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HIf* if_inst = new (&allocator) HIf(cmp); 921f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddPhi(phi_i); 922f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(null_check); 923f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(array_length); 924f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(add); 925f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(cmp); 926f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddInstruction(if_inst); 9271abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi_i->AddInput(constant_0); 928f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 929f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph); 930f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(inner_header); 931f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt); 932f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 933f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 934f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HSub* sub = new (&allocator) HSub(Primitive::kPrimInt, array_length, phi_i); 935f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang add = new (&allocator) HAdd(Primitive::kPrimInt, sub, constant_minus_1); 936f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (&allocator) HGreaterThanOrEqual(phi_j, add); 937f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp); 938f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddPhi(phi_j); 939f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(null_check); 940f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(array_length); 941f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(sub); 942f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(add); 943f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(cmp); 944f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddInstruction(if_inst); 9451abb4191a2e56d8dbf518efcaeefb266c1acdf2bDavid Brazdil phi_j->AddInput(constant_0); 946f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 947f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* inner_body_compare = new (&allocator) HBasicBlock(graph); 948f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(inner_body_compare); 949f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 950f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 951f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check1 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); 952f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet* array_get_j = new (&allocator) 953f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet(null_check, bounds_check1, Primitive::kPrimInt); 954f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(null_check); 955f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_length); 956f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(bounds_check1); 957f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_get_j); 958f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); 959f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 960f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 961f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBoundsCheck* bounds_check2 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); 962f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet* array_get_j_plus_1 = new (&allocator) 963f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet(null_check, bounds_check2, Primitive::kPrimInt); 964f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang cmp = new (&allocator) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1); 965f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang if_inst = new (&allocator) HIf(cmp); 966f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(j_plus_1); 967f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(null_check); 968f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_length); 969f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(bounds_check2); 970f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(array_get_j_plus_1); 971f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(cmp); 972f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddInstruction(if_inst); 973f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 974f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* inner_body_swap = new (&allocator) HBasicBlock(graph); 975f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(inner_body_swap); 976f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); 977f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // temp = array[j+1] 978f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 979f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 980f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check3 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); 981f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_get_j_plus_1 = new (&allocator) 982f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet(null_check, bounds_check3, Primitive::kPrimInt); 983f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(j_plus_1); 984f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 985f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 986f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check3); 987f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_get_j_plus_1); 988f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[j+1] = array[j] 989f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 990f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 991f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check4 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); 992f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_get_j = new (&allocator) 993f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArrayGet(null_check, bounds_check4, Primitive::kPrimInt); 994f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 995f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 996f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check4); 997f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_get_j); 998f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 999f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 1000f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check5 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); 1001f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set_j_plus_1 = new (&allocator) 1002f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0); 1003f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 1004f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 1005f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check5); 1006f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_set_j_plus_1); 1007f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // array[j] = temp 1008f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang null_check = new (&allocator) HNullCheck(parameter, 0); 1009f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang array_length = new (&allocator) HArrayLength(null_check); 1010f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HInstruction* bounds_check6 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); 1011f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet* array_set_j = new (&allocator) 1012f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0); 1013f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(null_check); 1014f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_length); 1015f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(bounds_check6); 1016f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(array_set_j); 1017f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddInstruction(new (&allocator) HGoto()); 1018f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1019f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* inner_body_add = new (&allocator) HBasicBlock(graph); 1020f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(inner_body_add); 1021f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang add = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); 1022f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_add->AddInstruction(add); 1023f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_add->AddInstruction(new (&allocator) HGoto()); 1024f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi_j->AddInput(add); 1025f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1026f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang HBasicBlock* outer_body_add = new (&allocator) HBasicBlock(graph); 1027f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->AddBlock(outer_body_add); 1028f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang add = new (&allocator) HAdd(Primitive::kPrimInt, phi_i, constant_1); 1029f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_body_add->AddInstruction(add); 1030f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_body_add->AddInstruction(new (&allocator) HGoto()); 1031f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang phi_i->AddInput(add); 1032f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1033f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang block->AddSuccessor(outer_header); 1034f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddSuccessor(exit); 1035f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_header->AddSuccessor(inner_header); 1036f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddSuccessor(outer_body_add); 1037f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_header->AddSuccessor(inner_body_compare); 1038f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddSuccessor(inner_body_add); 1039f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_compare->AddSuccessor(inner_body_swap); 1040f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_swap->AddSuccessor(inner_body_add); 1041f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang inner_body_add->AddSuccessor(inner_header); 1042f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang outer_body_add->AddSuccessor(outer_header); 1043f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1044f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang graph->BuildDominatorTree(); 10450304e182adee81be32c744fd3c0d28add29974ffMingyao Yang RunSimplifierAndGvn(graph); 1046f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang // gvn should remove the same bounds check. 1047f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check1)); 1048f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_FALSE(IsRemoved(bounds_check2)); 1049f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check3)); 1050f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check4)); 1051f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 1052f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check6)); 1053f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1054f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang BoundsCheckElimination bounds_check_elimination(graph); 1055f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang bounds_check_elimination.Run(); 1056f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check1)); 1057f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check2)); 1058f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check3)); 1059f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check4)); 1060f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check5)); 1061f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang ASSERT_TRUE(IsRemoved(bounds_check6)); 1062f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} 1063f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang 1064f384f88d4d1e89df82f47fbc7245a8acc9c2d49cMingyao Yang} // namespace art 1065