1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "base/arena_allocator.h"
18 #include "bounds_check_elimination.h"
19 #include "builder.h"
20 #include "gvn.h"
21 #include "induction_var_analysis.h"
22 #include "instruction_simplifier.h"
23 #include "nodes.h"
24 #include "optimizing_unit_test.h"
25 #include "side_effects_analysis.h"
26 
27 #include "gtest/gtest.h"
28 
29 namespace art {
30 
31 /**
32  * Fixture class for the BoundsCheckElimination tests.
33  */
34 class BoundsCheckEliminationTest : public testing::Test {
35  public:
BoundsCheckEliminationTest()36   BoundsCheckEliminationTest()  : pool_(), allocator_(&pool_) {
37     graph_ = CreateGraph(&allocator_);
38     graph_->SetHasBoundsChecks(true);
39   }
40 
~BoundsCheckEliminationTest()41   ~BoundsCheckEliminationTest() { }
42 
RunBCE()43   void RunBCE() {
44     graph_->BuildDominatorTree();
45 
46     InstructionSimplifier(graph_, /* codegen */ nullptr).Run();
47 
48     SideEffectsAnalysis side_effects(graph_);
49     side_effects.Run();
50 
51     GVNOptimization(graph_, side_effects).Run();
52 
53     HInductionVarAnalysis induction(graph_);
54     induction.Run();
55 
56     BoundsCheckElimination(graph_, side_effects, &induction).Run();
57   }
58 
59   ArenaPool pool_;
60   ArenaAllocator allocator_;
61   HGraph* graph_;
62 };
63 
64 
65 // if (i < 0) { array[i] = 1; // Can't eliminate. }
66 // else if (i >= array.length) { array[i] = 1; // Can't eliminate. }
67 // else { array[i] = 1; // Can eliminate. }
TEST_F(BoundsCheckEliminationTest,NarrowingRangeArrayBoundsElimination)68 TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
69   HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
70   graph_->AddBlock(entry);
71   graph_->SetEntryBlock(entry);
72   HInstruction* parameter1 = new (&allocator_)
73       HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);  // array
74   HInstruction* parameter2 = new (&allocator_)
75       HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);  // i
76   entry->AddInstruction(parameter1);
77   entry->AddInstruction(parameter2);
78 
79   HInstruction* constant_1 = graph_->GetIntConstant(1);
80   HInstruction* constant_0 = graph_->GetIntConstant(0);
81 
82   HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
83   graph_->AddBlock(block1);
84   HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, constant_0);
85   HIf* if_inst = new (&allocator_) HIf(cmp);
86   block1->AddInstruction(cmp);
87   block1->AddInstruction(if_inst);
88   entry->AddSuccessor(block1);
89 
90   HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
91   graph_->AddBlock(block2);
92   HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
93   HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0);
94   HBoundsCheck* bounds_check2 = new (&allocator_)
95       HBoundsCheck(parameter2, array_length, 0);
96   HArraySet* array_set = new (&allocator_) HArraySet(
97     null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0);
98   block2->AddInstruction(null_check);
99   block2->AddInstruction(array_length);
100   block2->AddInstruction(bounds_check2);
101   block2->AddInstruction(array_set);
102 
103   HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
104   graph_->AddBlock(block3);
105   null_check = new (&allocator_) HNullCheck(parameter1, 0);
106   array_length = new (&allocator_) HArrayLength(null_check, 0);
107   cmp = new (&allocator_) HLessThan(parameter2, array_length);
108   if_inst = new (&allocator_) HIf(cmp);
109   block3->AddInstruction(null_check);
110   block3->AddInstruction(array_length);
111   block3->AddInstruction(cmp);
112   block3->AddInstruction(if_inst);
113 
114   HBasicBlock* block4 = new (&allocator_) HBasicBlock(graph_);
115   graph_->AddBlock(block4);
116   null_check = new (&allocator_) HNullCheck(parameter1, 0);
117   array_length = new (&allocator_) HArrayLength(null_check, 0);
118   HBoundsCheck* bounds_check4 = new (&allocator_)
119       HBoundsCheck(parameter2, array_length, 0);
120   array_set = new (&allocator_) HArraySet(
121     null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0);
122   block4->AddInstruction(null_check);
123   block4->AddInstruction(array_length);
124   block4->AddInstruction(bounds_check4);
125   block4->AddInstruction(array_set);
126 
127   HBasicBlock* block5 = new (&allocator_) HBasicBlock(graph_);
128   graph_->AddBlock(block5);
129   null_check = new (&allocator_) HNullCheck(parameter1, 0);
130   array_length = new (&allocator_) HArrayLength(null_check, 0);
131   HBoundsCheck* bounds_check5 = new (&allocator_)
132       HBoundsCheck(parameter2, array_length, 0);
133   array_set = new (&allocator_) HArraySet(
134     null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
135   block5->AddInstruction(null_check);
136   block5->AddInstruction(array_length);
137   block5->AddInstruction(bounds_check5);
138   block5->AddInstruction(array_set);
139 
140   HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
141   graph_->AddBlock(exit);
142   block2->AddSuccessor(exit);
143   block4->AddSuccessor(exit);
144   block5->AddSuccessor(exit);
145   exit->AddInstruction(new (&allocator_) HExit());
146 
147   block1->AddSuccessor(block3);  // True successor
148   block1->AddSuccessor(block2);  // False successor
149 
150   block3->AddSuccessor(block5);  // True successor
151   block3->AddSuccessor(block4);  // False successor
152 
153   RunBCE();
154 
155   ASSERT_FALSE(IsRemoved(bounds_check2));
156   ASSERT_FALSE(IsRemoved(bounds_check4));
157   ASSERT_TRUE(IsRemoved(bounds_check5));
158 }
159 
160 // if (i > 0) {
161 //   // Positive number plus MAX_INT will overflow and be negative.
162 //   int j = i + Integer.MAX_VALUE;
163 //   if (j < array.length) array[j] = 1;  // Can't eliminate.
164 // }
TEST_F(BoundsCheckEliminationTest,OverflowArrayBoundsElimination)165 TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
166   HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
167   graph_->AddBlock(entry);
168   graph_->SetEntryBlock(entry);
169   HInstruction* parameter1 = new (&allocator_)
170       HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);  // array
171   HInstruction* parameter2 = new (&allocator_)
172       HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);  // i
173   entry->AddInstruction(parameter1);
174   entry->AddInstruction(parameter2);
175 
176   HInstruction* constant_1 = graph_->GetIntConstant(1);
177   HInstruction* constant_0 = graph_->GetIntConstant(0);
178   HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
179 
180   HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
181   graph_->AddBlock(block1);
182   HInstruction* cmp = new (&allocator_) HLessThanOrEqual(parameter2, constant_0);
183   HIf* if_inst = new (&allocator_) HIf(cmp);
184   block1->AddInstruction(cmp);
185   block1->AddInstruction(if_inst);
186   entry->AddSuccessor(block1);
187 
188   HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
189   graph_->AddBlock(block2);
190   HInstruction* add = new (&allocator_) HAdd(Primitive::kPrimInt, parameter2, constant_max_int);
191   HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
192   HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0);
193   HInstruction* cmp2 = new (&allocator_) HGreaterThanOrEqual(add, array_length);
194   if_inst = new (&allocator_) HIf(cmp2);
195   block2->AddInstruction(add);
196   block2->AddInstruction(null_check);
197   block2->AddInstruction(array_length);
198   block2->AddInstruction(cmp2);
199   block2->AddInstruction(if_inst);
200 
201   HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
202   graph_->AddBlock(block3);
203   HBoundsCheck* bounds_check = new (&allocator_)
204       HBoundsCheck(add, array_length, 0);
205   HArraySet* array_set = new (&allocator_) HArraySet(
206     null_check, bounds_check, constant_1, Primitive::kPrimInt, 0);
207   block3->AddInstruction(bounds_check);
208   block3->AddInstruction(array_set);
209 
210   HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
211   graph_->AddBlock(exit);
212   exit->AddInstruction(new (&allocator_) HExit());
213   block1->AddSuccessor(exit);    // true successor
214   block1->AddSuccessor(block2);  // false successor
215   block2->AddSuccessor(exit);    // true successor
216   block2->AddSuccessor(block3);  // false successor
217   block3->AddSuccessor(exit);
218 
219   RunBCE();
220 
221   ASSERT_FALSE(IsRemoved(bounds_check));
222 }
223 
224 // if (i < array.length) {
225 //   int j = i - Integer.MAX_VALUE;
226 //   j = j - Integer.MAX_VALUE;  // j is (i+2) after subtracting MAX_INT twice
227 //   if (j > 0) array[j] = 1;    // Can't eliminate.
228 // }
TEST_F(BoundsCheckEliminationTest,UnderflowArrayBoundsElimination)229 TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
230   HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
231   graph_->AddBlock(entry);
232   graph_->SetEntryBlock(entry);
233   HInstruction* parameter1 = new (&allocator_)
234       HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);  // array
235   HInstruction* parameter2 = new (&allocator_)
236       HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);  // i
237   entry->AddInstruction(parameter1);
238   entry->AddInstruction(parameter2);
239 
240   HInstruction* constant_1 = graph_->GetIntConstant(1);
241   HInstruction* constant_0 = graph_->GetIntConstant(0);
242   HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
243 
244   HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
245   graph_->AddBlock(block1);
246   HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
247   HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0);
248   HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, array_length);
249   HIf* if_inst = new (&allocator_) HIf(cmp);
250   block1->AddInstruction(null_check);
251   block1->AddInstruction(array_length);
252   block1->AddInstruction(cmp);
253   block1->AddInstruction(if_inst);
254   entry->AddSuccessor(block1);
255 
256   HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
257   graph_->AddBlock(block2);
258   HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, parameter2, constant_max_int);
259   HInstruction* sub2 = new (&allocator_) HSub(Primitive::kPrimInt, sub1, constant_max_int);
260   HInstruction* cmp2 = new (&allocator_) HLessThanOrEqual(sub2, constant_0);
261   if_inst = new (&allocator_) HIf(cmp2);
262   block2->AddInstruction(sub1);
263   block2->AddInstruction(sub2);
264   block2->AddInstruction(cmp2);
265   block2->AddInstruction(if_inst);
266 
267   HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
268   graph_->AddBlock(block3);
269   HBoundsCheck* bounds_check = new (&allocator_)
270       HBoundsCheck(sub2, array_length, 0);
271   HArraySet* array_set = new (&allocator_) HArraySet(
272     null_check, bounds_check, constant_1, Primitive::kPrimInt, 0);
273   block3->AddInstruction(bounds_check);
274   block3->AddInstruction(array_set);
275 
276   HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
277   graph_->AddBlock(exit);
278   exit->AddInstruction(new (&allocator_) HExit());
279   block1->AddSuccessor(exit);    // true successor
280   block1->AddSuccessor(block2);  // false successor
281   block2->AddSuccessor(exit);    // true successor
282   block2->AddSuccessor(block3);  // false successor
283   block3->AddSuccessor(exit);
284 
285   RunBCE();
286 
287   ASSERT_FALSE(IsRemoved(bounds_check));
288 }
289 
290 // array[6] = 1; // Can't eliminate.
291 // array[5] = 1; // Can eliminate.
292 // array[4] = 1; // Can eliminate.
TEST_F(BoundsCheckEliminationTest,ConstantArrayBoundsElimination)293 TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
294   HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
295   graph_->AddBlock(entry);
296   graph_->SetEntryBlock(entry);
297   HInstruction* parameter = new (&allocator_) HParameterValue(
298       graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
299   entry->AddInstruction(parameter);
300 
301   HInstruction* constant_5 = graph_->GetIntConstant(5);
302   HInstruction* constant_4 = graph_->GetIntConstant(4);
303   HInstruction* constant_6 = graph_->GetIntConstant(6);
304   HInstruction* constant_1 = graph_->GetIntConstant(1);
305 
306   HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
307   graph_->AddBlock(block);
308   entry->AddSuccessor(block);
309 
310   HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0);
311   HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0);
312   HBoundsCheck* bounds_check6 = new (&allocator_)
313       HBoundsCheck(constant_6, array_length, 0);
314   HInstruction* array_set = new (&allocator_) HArraySet(
315     null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0);
316   block->AddInstruction(null_check);
317   block->AddInstruction(array_length);
318   block->AddInstruction(bounds_check6);
319   block->AddInstruction(array_set);
320 
321   null_check = new (&allocator_) HNullCheck(parameter, 0);
322   array_length = new (&allocator_) HArrayLength(null_check, 0);
323   HBoundsCheck* bounds_check5 = new (&allocator_)
324       HBoundsCheck(constant_5, array_length, 0);
325   array_set = new (&allocator_) HArraySet(
326     null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
327   block->AddInstruction(null_check);
328   block->AddInstruction(array_length);
329   block->AddInstruction(bounds_check5);
330   block->AddInstruction(array_set);
331 
332   null_check = new (&allocator_) HNullCheck(parameter, 0);
333   array_length = new (&allocator_) HArrayLength(null_check, 0);
334   HBoundsCheck* bounds_check4 = new (&allocator_)
335       HBoundsCheck(constant_4, array_length, 0);
336   array_set = new (&allocator_) HArraySet(
337     null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0);
338   block->AddInstruction(null_check);
339   block->AddInstruction(array_length);
340   block->AddInstruction(bounds_check4);
341   block->AddInstruction(array_set);
342 
343   block->AddInstruction(new (&allocator_) HGoto());
344 
345   HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
346   graph_->AddBlock(exit);
347   block->AddSuccessor(exit);
348   exit->AddInstruction(new (&allocator_) HExit());
349 
350   RunBCE();
351 
352   ASSERT_FALSE(IsRemoved(bounds_check6));
353   ASSERT_TRUE(IsRemoved(bounds_check5));
354   ASSERT_TRUE(IsRemoved(bounds_check4));
355 }
356 
357 // for (int i=initial; i<array.length; i+=increment) { array[i] = 10; }
BuildSSAGraph1(HGraph * graph,ArenaAllocator * allocator,int initial,int increment,IfCondition cond=kCondGE)358 static HInstruction* BuildSSAGraph1(HGraph* graph,
359                                     ArenaAllocator* allocator,
360                                     int initial,
361                                     int increment,
362                                     IfCondition cond = kCondGE) {
363   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
364   graph->AddBlock(entry);
365   graph->SetEntryBlock(entry);
366   HInstruction* parameter = new (allocator) HParameterValue(
367       graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
368   entry->AddInstruction(parameter);
369 
370   HInstruction* constant_initial = graph->GetIntConstant(initial);
371   HInstruction* constant_increment = graph->GetIntConstant(increment);
372   HInstruction* constant_10 = graph->GetIntConstant(10);
373 
374   HBasicBlock* block = new (allocator) HBasicBlock(graph);
375   graph->AddBlock(block);
376   entry->AddSuccessor(block);
377   block->AddInstruction(new (allocator) HGoto());
378 
379   HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
380   HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
381   HBasicBlock* exit = new (allocator) HBasicBlock(graph);
382 
383   graph->AddBlock(loop_header);
384   graph->AddBlock(loop_body);
385   graph->AddBlock(exit);
386   block->AddSuccessor(loop_header);
387   loop_header->AddSuccessor(exit);       // true successor
388   loop_header->AddSuccessor(loop_body);  // false successor
389   loop_body->AddSuccessor(loop_header);
390 
391   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
392   HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
393   HInstruction* array_length = new (allocator) HArrayLength(null_check, 0);
394   HInstruction* cmp = nullptr;
395   if (cond == kCondGE) {
396     cmp = new (allocator) HGreaterThanOrEqual(phi, array_length);
397   } else {
398     DCHECK(cond == kCondGT);
399     cmp = new (allocator) HGreaterThan(phi, array_length);
400   }
401   HInstruction* if_inst = new (allocator) HIf(cmp);
402   loop_header->AddPhi(phi);
403   loop_header->AddInstruction(null_check);
404   loop_header->AddInstruction(array_length);
405   loop_header->AddInstruction(cmp);
406   loop_header->AddInstruction(if_inst);
407   phi->AddInput(constant_initial);
408 
409   null_check = new (allocator) HNullCheck(parameter, 0);
410   array_length = new (allocator) HArrayLength(null_check, 0);
411   HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
412   HInstruction* array_set = new (allocator) HArraySet(
413       null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
414 
415   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
416   loop_body->AddInstruction(null_check);
417   loop_body->AddInstruction(array_length);
418   loop_body->AddInstruction(bounds_check);
419   loop_body->AddInstruction(array_set);
420   loop_body->AddInstruction(add);
421   loop_body->AddInstruction(new (allocator) HGoto());
422   phi->AddInput(add);
423 
424   exit->AddInstruction(new (allocator) HExit());
425 
426   return bounds_check;
427 }
428 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1a)429 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1a) {
430   // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. }
431   HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1);
432   RunBCE();
433   ASSERT_TRUE(IsRemoved(bounds_check));
434 }
435 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1b)436 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1b) {
437   // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. }
438   HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 1);
439   RunBCE();
440   ASSERT_TRUE(IsRemoved(bounds_check));
441 }
442 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1c)443 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1c) {
444   // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. }
445   HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, -1, 1);
446   RunBCE();
447   ASSERT_FALSE(IsRemoved(bounds_check));
448 }
449 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1d)450 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1d) {
451   // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. }
452   HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1, kCondGT);
453   RunBCE();
454   ASSERT_FALSE(IsRemoved(bounds_check));
455 }
456 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1e)457 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1e) {
458   // for (int i=0; i<array.length; i += 2) {
459   //   array[i] = 10; // Can't eliminate due to overflow concern. }
460   HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 2);
461   RunBCE();
462   ASSERT_FALSE(IsRemoved(bounds_check));
463 }
464 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1f)465 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1f) {
466   // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. }
467   HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 2);
468   RunBCE();
469   ASSERT_TRUE(IsRemoved(bounds_check));
470 }
471 
472 // for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; }
BuildSSAGraph2(HGraph * graph,ArenaAllocator * allocator,int initial,int increment=-1,IfCondition cond=kCondLE)473 static HInstruction* BuildSSAGraph2(HGraph *graph,
474                                     ArenaAllocator* allocator,
475                                     int initial,
476                                     int increment = -1,
477                                     IfCondition cond = kCondLE) {
478   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
479   graph->AddBlock(entry);
480   graph->SetEntryBlock(entry);
481   HInstruction* parameter = new (allocator) HParameterValue(
482       graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
483   entry->AddInstruction(parameter);
484 
485   HInstruction* constant_initial = graph->GetIntConstant(initial);
486   HInstruction* constant_increment = graph->GetIntConstant(increment);
487   HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
488   HInstruction* constant_10 = graph->GetIntConstant(10);
489 
490   HBasicBlock* block = new (allocator) HBasicBlock(graph);
491   graph->AddBlock(block);
492   entry->AddSuccessor(block);
493   HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
494   HInstruction* array_length = new (allocator) HArrayLength(null_check, 0);
495   block->AddInstruction(null_check);
496   block->AddInstruction(array_length);
497   block->AddInstruction(new (allocator) HGoto());
498 
499   HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
500   HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
501   HBasicBlock* exit = new (allocator) HBasicBlock(graph);
502 
503   graph->AddBlock(loop_header);
504   graph->AddBlock(loop_body);
505   graph->AddBlock(exit);
506   block->AddSuccessor(loop_header);
507   loop_header->AddSuccessor(exit);       // true successor
508   loop_header->AddSuccessor(loop_body);  // false successor
509   loop_body->AddSuccessor(loop_header);
510 
511   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
512   HInstruction* cmp = nullptr;
513   if (cond == kCondLE) {
514     cmp = new (allocator) HLessThanOrEqual(phi, constant_initial);
515   } else {
516     DCHECK(cond == kCondLT);
517     cmp = new (allocator) HLessThan(phi, constant_initial);
518   }
519   HInstruction* if_inst = new (allocator) HIf(cmp);
520   loop_header->AddPhi(phi);
521   loop_header->AddInstruction(cmp);
522   loop_header->AddInstruction(if_inst);
523   phi->AddInput(array_length);
524 
525   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1);
526   null_check = new (allocator) HNullCheck(parameter, 0);
527   array_length = new (allocator) HArrayLength(null_check, 0);
528   HInstruction* bounds_check = new (allocator) HBoundsCheck(add, array_length, 0);
529   HInstruction* array_set = new (allocator) HArraySet(
530       null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
531   HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
532   loop_body->AddInstruction(add);
533   loop_body->AddInstruction(null_check);
534   loop_body->AddInstruction(array_length);
535   loop_body->AddInstruction(bounds_check);
536   loop_body->AddInstruction(array_set);
537   loop_body->AddInstruction(add_phi);
538   loop_body->AddInstruction(new (allocator) HGoto());
539   phi->AddInput(add);
540 
541   exit->AddInstruction(new (allocator) HExit());
542 
543   return bounds_check;
544 }
545 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2a)546 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2a) {
547   // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. }
548   HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0);
549   RunBCE();
550   ASSERT_TRUE(IsRemoved(bounds_check));
551 }
552 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2b)553 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2b) {
554   // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. }
555   HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 1);
556   RunBCE();
557   ASSERT_TRUE(IsRemoved(bounds_check));
558 }
559 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2c)560 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2c) {
561   // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. }
562   HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, -1);
563   RunBCE();
564   ASSERT_FALSE(IsRemoved(bounds_check));
565 }
566 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2d)567 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2d) {
568   // for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. }
569   HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -1, kCondLT);
570   RunBCE();
571   ASSERT_FALSE(IsRemoved(bounds_check));
572 }
573 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2e)574 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2e) {
575   // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. }
576   HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -2);
577   RunBCE();
578   ASSERT_TRUE(IsRemoved(bounds_check));
579 }
580 
581 // int[] array = new int[10];
582 // for (int i=0; i<10; i+=increment) { array[i] = 10; }
BuildSSAGraph3(HGraph * graph,ArenaAllocator * allocator,int initial,int increment,IfCondition cond)583 static HInstruction* BuildSSAGraph3(HGraph* graph,
584                                     ArenaAllocator* allocator,
585                                     int initial,
586                                     int increment,
587                                     IfCondition cond) {
588   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
589   graph->AddBlock(entry);
590   graph->SetEntryBlock(entry);
591 
592   HInstruction* constant_10 = graph->GetIntConstant(10);
593   HInstruction* constant_initial = graph->GetIntConstant(initial);
594   HInstruction* constant_increment = graph->GetIntConstant(increment);
595 
596   HBasicBlock* block = new (allocator) HBasicBlock(graph);
597   graph->AddBlock(block);
598   entry->AddSuccessor(block);
599   // We pass a bogus constant for the class to avoid mocking one.
600   HInstruction* new_array = new (allocator) HNewArray(
601       constant_10,
602       constant_10,
603       0);
604   block->AddInstruction(new_array);
605   block->AddInstruction(new (allocator) HGoto());
606 
607   HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
608   HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
609   HBasicBlock* exit = new (allocator) HBasicBlock(graph);
610 
611   graph->AddBlock(loop_header);
612   graph->AddBlock(loop_body);
613   graph->AddBlock(exit);
614   block->AddSuccessor(loop_header);
615   loop_header->AddSuccessor(exit);       // true successor
616   loop_header->AddSuccessor(loop_body);  // false successor
617   loop_body->AddSuccessor(loop_header);
618 
619   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
620   HInstruction* cmp = nullptr;
621   if (cond == kCondGE) {
622     cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10);
623   } else {
624     DCHECK(cond == kCondGT);
625     cmp = new (allocator) HGreaterThan(phi, constant_10);
626   }
627   HInstruction* if_inst = new (allocator) HIf(cmp);
628   loop_header->AddPhi(phi);
629   loop_header->AddInstruction(cmp);
630   loop_header->AddInstruction(if_inst);
631   phi->AddInput(constant_initial);
632 
633   HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0);
634   HArrayLength* array_length = new (allocator) HArrayLength(null_check, 0);
635   HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
636   HInstruction* array_set = new (allocator) HArraySet(
637       null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
638   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
639   loop_body->AddInstruction(null_check);
640   loop_body->AddInstruction(array_length);
641   loop_body->AddInstruction(bounds_check);
642   loop_body->AddInstruction(array_set);
643   loop_body->AddInstruction(add);
644   loop_body->AddInstruction(new (allocator) HGoto());
645   phi->AddInput(add);
646 
647   exit->AddInstruction(new (allocator) HExit());
648 
649   return bounds_check;
650 }
651 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3a)652 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) {
653   // int[] array = new int[10];
654   // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. }
655   HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGE);
656   RunBCE();
657   ASSERT_TRUE(IsRemoved(bounds_check));
658 }
659 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3b)660 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) {
661   // int[] array = new int[10];
662   // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
663   HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 1, kCondGE);
664   RunBCE();
665   ASSERT_TRUE(IsRemoved(bounds_check));
666 }
667 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3c)668 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) {
669   // int[] array = new int[10];
670   // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
671   HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGT);
672   RunBCE();
673   ASSERT_FALSE(IsRemoved(bounds_check));
674 }
675 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3d)676 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) {
677   // int[] array = new int[10];
678   // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
679   HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 8, kCondGE);
680   RunBCE();
681   ASSERT_TRUE(IsRemoved(bounds_check));
682 }
683 
684 // for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; }
BuildSSAGraph4(HGraph * graph,ArenaAllocator * allocator,int initial,IfCondition cond=kCondGE)685 static HInstruction* BuildSSAGraph4(HGraph* graph,
686                                     ArenaAllocator* allocator,
687                                     int initial,
688                                     IfCondition cond = kCondGE) {
689   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
690   graph->AddBlock(entry);
691   graph->SetEntryBlock(entry);
692   HInstruction* parameter = new (allocator) HParameterValue(
693       graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
694   entry->AddInstruction(parameter);
695 
696   HInstruction* constant_initial = graph->GetIntConstant(initial);
697   HInstruction* constant_1 = graph->GetIntConstant(1);
698   HInstruction* constant_10 = graph->GetIntConstant(10);
699   HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
700 
701   HBasicBlock* block = new (allocator) HBasicBlock(graph);
702   graph->AddBlock(block);
703   entry->AddSuccessor(block);
704   block->AddInstruction(new (allocator) HGoto());
705 
706   HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
707   HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
708   HBasicBlock* exit = new (allocator) HBasicBlock(graph);
709 
710   graph->AddBlock(loop_header);
711   graph->AddBlock(loop_body);
712   graph->AddBlock(exit);
713   block->AddSuccessor(loop_header);
714   loop_header->AddSuccessor(exit);       // true successor
715   loop_header->AddSuccessor(loop_body);  // false successor
716   loop_body->AddSuccessor(loop_header);
717 
718   HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
719   HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
720   HInstruction* array_length = new (allocator) HArrayLength(null_check, 0);
721   HInstruction* cmp = nullptr;
722   if (cond == kCondGE) {
723     cmp = new (allocator) HGreaterThanOrEqual(phi, array_length);
724   } else if (cond == kCondGT) {
725     cmp = new (allocator) HGreaterThan(phi, array_length);
726   }
727   HInstruction* if_inst = new (allocator) HIf(cmp);
728   loop_header->AddPhi(phi);
729   loop_header->AddInstruction(null_check);
730   loop_header->AddInstruction(array_length);
731   loop_header->AddInstruction(cmp);
732   loop_header->AddInstruction(if_inst);
733   phi->AddInput(constant_initial);
734 
735   null_check = new (allocator) HNullCheck(parameter, 0);
736   array_length = new (allocator) HArrayLength(null_check, 0);
737   HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi);
738   HInstruction* add_minus_1 = new (allocator)
739       HAdd(Primitive::kPrimInt, sub, constant_minus_1);
740   HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0);
741   HInstruction* array_set = new (allocator) HArraySet(
742       null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
743   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1);
744   loop_body->AddInstruction(null_check);
745   loop_body->AddInstruction(array_length);
746   loop_body->AddInstruction(sub);
747   loop_body->AddInstruction(add_minus_1);
748   loop_body->AddInstruction(bounds_check);
749   loop_body->AddInstruction(array_set);
750   loop_body->AddInstruction(add);
751   loop_body->AddInstruction(new (allocator) HGoto());
752   phi->AddInput(add);
753 
754   exit->AddInstruction(new (allocator) HExit());
755 
756   return bounds_check;
757 }
758 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4a)759 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) {
760   // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. }
761   HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0);
762   RunBCE();
763   ASSERT_TRUE(IsRemoved(bounds_check));
764 }
765 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4b)766 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) {
767   // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
768   HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 1);
769   RunBCE();
770   ASSERT_TRUE(IsRemoved(bounds_check));
771 }
772 
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4c)773 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) {
774   // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
775   HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0, kCondGT);
776   RunBCE();
777   ASSERT_FALSE(IsRemoved(bounds_check));
778 }
779 
780 // Bubble sort:
781 // (Every array access bounds-check can be eliminated.)
782 // for (int i=0; i<array.length-1; i++) {
783 //  for (int j=0; j<array.length-i-1; j++) {
784 //     if (array[j] > array[j+1]) {
785 //       int temp = array[j+1];
786 //       array[j+1] = array[j];
787 //       array[j] = temp;
788 //     }
789 //  }
790 // }
TEST_F(BoundsCheckEliminationTest,BubbleSortArrayBoundsElimination)791 TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
792   HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
793   graph_->AddBlock(entry);
794   graph_->SetEntryBlock(entry);
795   HInstruction* parameter = new (&allocator_) HParameterValue(
796       graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
797   entry->AddInstruction(parameter);
798 
799   HInstruction* constant_0 = graph_->GetIntConstant(0);
800   HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
801   HInstruction* constant_1 = graph_->GetIntConstant(1);
802 
803   HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
804   graph_->AddBlock(block);
805   entry->AddSuccessor(block);
806   block->AddInstruction(new (&allocator_) HGoto());
807 
808   HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
809   graph_->AddBlock(exit);
810   exit->AddInstruction(new (&allocator_) HExit());
811 
812   HBasicBlock* outer_header = new (&allocator_) HBasicBlock(graph_);
813   graph_->AddBlock(outer_header);
814   HPhi* phi_i = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
815   HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0);
816   HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0);
817   HAdd* add = new (&allocator_) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
818   HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(phi_i, add);
819   HIf* if_inst = new (&allocator_) HIf(cmp);
820   outer_header->AddPhi(phi_i);
821   outer_header->AddInstruction(null_check);
822   outer_header->AddInstruction(array_length);
823   outer_header->AddInstruction(add);
824   outer_header->AddInstruction(cmp);
825   outer_header->AddInstruction(if_inst);
826   phi_i->AddInput(constant_0);
827 
828   HBasicBlock* inner_header = new (&allocator_) HBasicBlock(graph_);
829   graph_->AddBlock(inner_header);
830   HPhi* phi_j = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
831   null_check = new (&allocator_) HNullCheck(parameter, 0);
832   array_length = new (&allocator_) HArrayLength(null_check, 0);
833   HSub* sub = new (&allocator_) HSub(Primitive::kPrimInt, array_length, phi_i);
834   add = new (&allocator_) HAdd(Primitive::kPrimInt, sub, constant_minus_1);
835   cmp = new (&allocator_) HGreaterThanOrEqual(phi_j, add);
836   if_inst = new (&allocator_) HIf(cmp);
837   inner_header->AddPhi(phi_j);
838   inner_header->AddInstruction(null_check);
839   inner_header->AddInstruction(array_length);
840   inner_header->AddInstruction(sub);
841   inner_header->AddInstruction(add);
842   inner_header->AddInstruction(cmp);
843   inner_header->AddInstruction(if_inst);
844   phi_j->AddInput(constant_0);
845 
846   HBasicBlock* inner_body_compare = new (&allocator_) HBasicBlock(graph_);
847   graph_->AddBlock(inner_body_compare);
848   null_check = new (&allocator_) HNullCheck(parameter, 0);
849   array_length = new (&allocator_) HArrayLength(null_check, 0);
850   HBoundsCheck* bounds_check1 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
851   HArrayGet* array_get_j = new (&allocator_)
852       HArrayGet(null_check, bounds_check1, Primitive::kPrimInt, 0);
853   inner_body_compare->AddInstruction(null_check);
854   inner_body_compare->AddInstruction(array_length);
855   inner_body_compare->AddInstruction(bounds_check1);
856   inner_body_compare->AddInstruction(array_get_j);
857   HInstruction* j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
858   null_check = new (&allocator_) HNullCheck(parameter, 0);
859   array_length = new (&allocator_) HArrayLength(null_check, 0);
860   HBoundsCheck* bounds_check2 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
861   HArrayGet* array_get_j_plus_1 = new (&allocator_)
862       HArrayGet(null_check, bounds_check2, Primitive::kPrimInt, 0);
863   cmp = new (&allocator_) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1);
864   if_inst = new (&allocator_) HIf(cmp);
865   inner_body_compare->AddInstruction(j_plus_1);
866   inner_body_compare->AddInstruction(null_check);
867   inner_body_compare->AddInstruction(array_length);
868   inner_body_compare->AddInstruction(bounds_check2);
869   inner_body_compare->AddInstruction(array_get_j_plus_1);
870   inner_body_compare->AddInstruction(cmp);
871   inner_body_compare->AddInstruction(if_inst);
872 
873   HBasicBlock* inner_body_swap = new (&allocator_) HBasicBlock(graph_);
874   graph_->AddBlock(inner_body_swap);
875   j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
876   // temp = array[j+1]
877   null_check = new (&allocator_) HNullCheck(parameter, 0);
878   array_length = new (&allocator_) HArrayLength(null_check, 0);
879   HInstruction* bounds_check3 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
880   array_get_j_plus_1 = new (&allocator_)
881       HArrayGet(null_check, bounds_check3, Primitive::kPrimInt, 0);
882   inner_body_swap->AddInstruction(j_plus_1);
883   inner_body_swap->AddInstruction(null_check);
884   inner_body_swap->AddInstruction(array_length);
885   inner_body_swap->AddInstruction(bounds_check3);
886   inner_body_swap->AddInstruction(array_get_j_plus_1);
887   // array[j+1] = array[j]
888   null_check = new (&allocator_) HNullCheck(parameter, 0);
889   array_length = new (&allocator_) HArrayLength(null_check, 0);
890   HInstruction* bounds_check4 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
891   array_get_j = new (&allocator_)
892       HArrayGet(null_check, bounds_check4, Primitive::kPrimInt, 0);
893   inner_body_swap->AddInstruction(null_check);
894   inner_body_swap->AddInstruction(array_length);
895   inner_body_swap->AddInstruction(bounds_check4);
896   inner_body_swap->AddInstruction(array_get_j);
897   null_check = new (&allocator_) HNullCheck(parameter, 0);
898   array_length = new (&allocator_) HArrayLength(null_check, 0);
899   HInstruction* bounds_check5 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
900   HArraySet* array_set_j_plus_1 = new (&allocator_)
901       HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0);
902   inner_body_swap->AddInstruction(null_check);
903   inner_body_swap->AddInstruction(array_length);
904   inner_body_swap->AddInstruction(bounds_check5);
905   inner_body_swap->AddInstruction(array_set_j_plus_1);
906   // array[j] = temp
907   null_check = new (&allocator_) HNullCheck(parameter, 0);
908   array_length = new (&allocator_) HArrayLength(null_check, 0);
909   HInstruction* bounds_check6 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
910   HArraySet* array_set_j = new (&allocator_)
911       HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0);
912   inner_body_swap->AddInstruction(null_check);
913   inner_body_swap->AddInstruction(array_length);
914   inner_body_swap->AddInstruction(bounds_check6);
915   inner_body_swap->AddInstruction(array_set_j);
916   inner_body_swap->AddInstruction(new (&allocator_) HGoto());
917 
918   HBasicBlock* inner_body_add = new (&allocator_) HBasicBlock(graph_);
919   graph_->AddBlock(inner_body_add);
920   add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
921   inner_body_add->AddInstruction(add);
922   inner_body_add->AddInstruction(new (&allocator_) HGoto());
923   phi_j->AddInput(add);
924 
925   HBasicBlock* outer_body_add = new (&allocator_) HBasicBlock(graph_);
926   graph_->AddBlock(outer_body_add);
927   add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_i, constant_1);
928   outer_body_add->AddInstruction(add);
929   outer_body_add->AddInstruction(new (&allocator_) HGoto());
930   phi_i->AddInput(add);
931 
932   block->AddSuccessor(outer_header);
933   outer_header->AddSuccessor(exit);
934   outer_header->AddSuccessor(inner_header);
935   inner_header->AddSuccessor(outer_body_add);
936   inner_header->AddSuccessor(inner_body_compare);
937   inner_body_compare->AddSuccessor(inner_body_add);
938   inner_body_compare->AddSuccessor(inner_body_swap);
939   inner_body_swap->AddSuccessor(inner_body_add);
940   inner_body_add->AddSuccessor(inner_header);
941   outer_body_add->AddSuccessor(outer_header);
942 
943   RunBCE();  // gvn removes same bounds check already
944 
945   ASSERT_TRUE(IsRemoved(bounds_check1));
946   ASSERT_TRUE(IsRemoved(bounds_check2));
947   ASSERT_TRUE(IsRemoved(bounds_check3));
948   ASSERT_TRUE(IsRemoved(bounds_check4));
949   ASSERT_TRUE(IsRemoved(bounds_check5));
950   ASSERT_TRUE(IsRemoved(bounds_check6));
951 }
952 
953 }  // namespace art
954