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