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_).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(), 0, 0, Primitive::kPrimNot); // array
74 HInstruction* parameter2 = new (&allocator_)
75 HParameterValue(graph_->GetDexFile(), 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(), 0, 0, Primitive::kPrimNot); // array
171 HInstruction* parameter2 = new (&allocator_)
172 HParameterValue(graph_->GetDexFile(), 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(), 0, 0, Primitive::kPrimNot); // array
235 HInstruction* parameter2 = new (&allocator_)
236 HParameterValue(graph_->GetDexFile(), 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(), 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(), 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(), 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 HInstruction* new_array = new (allocator) HNewArray(
600 constant_10,
601 graph->GetCurrentMethod(),
602 0,
603 Primitive::kPrimInt,
604 graph->GetDexFile(),
605 kQuickAllocArray);
606 block->AddInstruction(new_array);
607 block->AddInstruction(new (allocator) HGoto());
608
609 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
610 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
611 HBasicBlock* exit = new (allocator) HBasicBlock(graph);
612
613 graph->AddBlock(loop_header);
614 graph->AddBlock(loop_body);
615 graph->AddBlock(exit);
616 block->AddSuccessor(loop_header);
617 loop_header->AddSuccessor(exit); // true successor
618 loop_header->AddSuccessor(loop_body); // false successor
619 loop_body->AddSuccessor(loop_header);
620
621 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
622 HInstruction* cmp = nullptr;
623 if (cond == kCondGE) {
624 cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10);
625 } else {
626 DCHECK(cond == kCondGT);
627 cmp = new (allocator) HGreaterThan(phi, constant_10);
628 }
629 HInstruction* if_inst = new (allocator) HIf(cmp);
630 loop_header->AddPhi(phi);
631 loop_header->AddInstruction(cmp);
632 loop_header->AddInstruction(if_inst);
633 phi->AddInput(constant_initial);
634
635 HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0);
636 HArrayLength* array_length = new (allocator) HArrayLength(null_check, 0);
637 HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
638 HInstruction* array_set = new (allocator) HArraySet(
639 null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
640 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
641 loop_body->AddInstruction(null_check);
642 loop_body->AddInstruction(array_length);
643 loop_body->AddInstruction(bounds_check);
644 loop_body->AddInstruction(array_set);
645 loop_body->AddInstruction(add);
646 loop_body->AddInstruction(new (allocator) HGoto());
647 phi->AddInput(add);
648
649 exit->AddInstruction(new (allocator) HExit());
650
651 return bounds_check;
652 }
653
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3a)654 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) {
655 // int[] array = new int[10];
656 // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. }
657 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGE);
658 RunBCE();
659 ASSERT_TRUE(IsRemoved(bounds_check));
660 }
661
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3b)662 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) {
663 // int[] array = new int[10];
664 // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
665 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 1, kCondGE);
666 RunBCE();
667 ASSERT_TRUE(IsRemoved(bounds_check));
668 }
669
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3c)670 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) {
671 // int[] array = new int[10];
672 // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
673 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGT);
674 RunBCE();
675 ASSERT_FALSE(IsRemoved(bounds_check));
676 }
677
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3d)678 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) {
679 // int[] array = new int[10];
680 // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
681 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 8, kCondGE);
682 RunBCE();
683 ASSERT_TRUE(IsRemoved(bounds_check));
684 }
685
686 // for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; }
BuildSSAGraph4(HGraph * graph,ArenaAllocator * allocator,int initial,IfCondition cond=kCondGE)687 static HInstruction* BuildSSAGraph4(HGraph* graph,
688 ArenaAllocator* allocator,
689 int initial,
690 IfCondition cond = kCondGE) {
691 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
692 graph->AddBlock(entry);
693 graph->SetEntryBlock(entry);
694 HInstruction* parameter = new (allocator) HParameterValue(
695 graph->GetDexFile(), 0, 0, Primitive::kPrimNot);
696 entry->AddInstruction(parameter);
697
698 HInstruction* constant_initial = graph->GetIntConstant(initial);
699 HInstruction* constant_1 = graph->GetIntConstant(1);
700 HInstruction* constant_10 = graph->GetIntConstant(10);
701 HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
702
703 HBasicBlock* block = new (allocator) HBasicBlock(graph);
704 graph->AddBlock(block);
705 entry->AddSuccessor(block);
706 block->AddInstruction(new (allocator) HGoto());
707
708 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
709 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
710 HBasicBlock* exit = new (allocator) HBasicBlock(graph);
711
712 graph->AddBlock(loop_header);
713 graph->AddBlock(loop_body);
714 graph->AddBlock(exit);
715 block->AddSuccessor(loop_header);
716 loop_header->AddSuccessor(exit); // true successor
717 loop_header->AddSuccessor(loop_body); // false successor
718 loop_body->AddSuccessor(loop_header);
719
720 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
721 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
722 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0);
723 HInstruction* cmp = nullptr;
724 if (cond == kCondGE) {
725 cmp = new (allocator) HGreaterThanOrEqual(phi, array_length);
726 } else if (cond == kCondGT) {
727 cmp = new (allocator) HGreaterThan(phi, array_length);
728 }
729 HInstruction* if_inst = new (allocator) HIf(cmp);
730 loop_header->AddPhi(phi);
731 loop_header->AddInstruction(null_check);
732 loop_header->AddInstruction(array_length);
733 loop_header->AddInstruction(cmp);
734 loop_header->AddInstruction(if_inst);
735 phi->AddInput(constant_initial);
736
737 null_check = new (allocator) HNullCheck(parameter, 0);
738 array_length = new (allocator) HArrayLength(null_check, 0);
739 HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi);
740 HInstruction* add_minus_1 = new (allocator)
741 HAdd(Primitive::kPrimInt, sub, constant_minus_1);
742 HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0);
743 HInstruction* array_set = new (allocator) HArraySet(
744 null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
745 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1);
746 loop_body->AddInstruction(null_check);
747 loop_body->AddInstruction(array_length);
748 loop_body->AddInstruction(sub);
749 loop_body->AddInstruction(add_minus_1);
750 loop_body->AddInstruction(bounds_check);
751 loop_body->AddInstruction(array_set);
752 loop_body->AddInstruction(add);
753 loop_body->AddInstruction(new (allocator) HGoto());
754 phi->AddInput(add);
755
756 exit->AddInstruction(new (allocator) HExit());
757
758 return bounds_check;
759 }
760
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4a)761 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) {
762 // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. }
763 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0);
764 RunBCE();
765 ASSERT_TRUE(IsRemoved(bounds_check));
766 }
767
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4b)768 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) {
769 // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
770 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 1);
771 RunBCE();
772 ASSERT_TRUE(IsRemoved(bounds_check));
773 }
774
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4c)775 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) {
776 // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
777 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0, kCondGT);
778 RunBCE();
779 ASSERT_FALSE(IsRemoved(bounds_check));
780 }
781
782 // Bubble sort:
783 // (Every array access bounds-check can be eliminated.)
784 // for (int i=0; i<array.length-1; i++) {
785 // for (int j=0; j<array.length-i-1; j++) {
786 // if (array[j] > array[j+1]) {
787 // int temp = array[j+1];
788 // array[j+1] = array[j];
789 // array[j] = temp;
790 // }
791 // }
792 // }
TEST_F(BoundsCheckEliminationTest,BubbleSortArrayBoundsElimination)793 TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
794 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
795 graph_->AddBlock(entry);
796 graph_->SetEntryBlock(entry);
797 HInstruction* parameter = new (&allocator_) HParameterValue(
798 graph_->GetDexFile(), 0, 0, Primitive::kPrimNot);
799 entry->AddInstruction(parameter);
800
801 HInstruction* constant_0 = graph_->GetIntConstant(0);
802 HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
803 HInstruction* constant_1 = graph_->GetIntConstant(1);
804
805 HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
806 graph_->AddBlock(block);
807 entry->AddSuccessor(block);
808 block->AddInstruction(new (&allocator_) HGoto());
809
810 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
811 graph_->AddBlock(exit);
812 exit->AddInstruction(new (&allocator_) HExit());
813
814 HBasicBlock* outer_header = new (&allocator_) HBasicBlock(graph_);
815 graph_->AddBlock(outer_header);
816 HPhi* phi_i = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
817 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0);
818 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0);
819 HAdd* add = new (&allocator_) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
820 HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(phi_i, add);
821 HIf* if_inst = new (&allocator_) HIf(cmp);
822 outer_header->AddPhi(phi_i);
823 outer_header->AddInstruction(null_check);
824 outer_header->AddInstruction(array_length);
825 outer_header->AddInstruction(add);
826 outer_header->AddInstruction(cmp);
827 outer_header->AddInstruction(if_inst);
828 phi_i->AddInput(constant_0);
829
830 HBasicBlock* inner_header = new (&allocator_) HBasicBlock(graph_);
831 graph_->AddBlock(inner_header);
832 HPhi* phi_j = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
833 null_check = new (&allocator_) HNullCheck(parameter, 0);
834 array_length = new (&allocator_) HArrayLength(null_check, 0);
835 HSub* sub = new (&allocator_) HSub(Primitive::kPrimInt, array_length, phi_i);
836 add = new (&allocator_) HAdd(Primitive::kPrimInt, sub, constant_minus_1);
837 cmp = new (&allocator_) HGreaterThanOrEqual(phi_j, add);
838 if_inst = new (&allocator_) HIf(cmp);
839 inner_header->AddPhi(phi_j);
840 inner_header->AddInstruction(null_check);
841 inner_header->AddInstruction(array_length);
842 inner_header->AddInstruction(sub);
843 inner_header->AddInstruction(add);
844 inner_header->AddInstruction(cmp);
845 inner_header->AddInstruction(if_inst);
846 phi_j->AddInput(constant_0);
847
848 HBasicBlock* inner_body_compare = new (&allocator_) HBasicBlock(graph_);
849 graph_->AddBlock(inner_body_compare);
850 null_check = new (&allocator_) HNullCheck(parameter, 0);
851 array_length = new (&allocator_) HArrayLength(null_check, 0);
852 HBoundsCheck* bounds_check1 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
853 HArrayGet* array_get_j = new (&allocator_)
854 HArrayGet(null_check, bounds_check1, Primitive::kPrimInt, 0);
855 inner_body_compare->AddInstruction(null_check);
856 inner_body_compare->AddInstruction(array_length);
857 inner_body_compare->AddInstruction(bounds_check1);
858 inner_body_compare->AddInstruction(array_get_j);
859 HInstruction* j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
860 null_check = new (&allocator_) HNullCheck(parameter, 0);
861 array_length = new (&allocator_) HArrayLength(null_check, 0);
862 HBoundsCheck* bounds_check2 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
863 HArrayGet* array_get_j_plus_1 = new (&allocator_)
864 HArrayGet(null_check, bounds_check2, Primitive::kPrimInt, 0);
865 cmp = new (&allocator_) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1);
866 if_inst = new (&allocator_) HIf(cmp);
867 inner_body_compare->AddInstruction(j_plus_1);
868 inner_body_compare->AddInstruction(null_check);
869 inner_body_compare->AddInstruction(array_length);
870 inner_body_compare->AddInstruction(bounds_check2);
871 inner_body_compare->AddInstruction(array_get_j_plus_1);
872 inner_body_compare->AddInstruction(cmp);
873 inner_body_compare->AddInstruction(if_inst);
874
875 HBasicBlock* inner_body_swap = new (&allocator_) HBasicBlock(graph_);
876 graph_->AddBlock(inner_body_swap);
877 j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
878 // temp = array[j+1]
879 null_check = new (&allocator_) HNullCheck(parameter, 0);
880 array_length = new (&allocator_) HArrayLength(null_check, 0);
881 HInstruction* bounds_check3 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
882 array_get_j_plus_1 = new (&allocator_)
883 HArrayGet(null_check, bounds_check3, Primitive::kPrimInt, 0);
884 inner_body_swap->AddInstruction(j_plus_1);
885 inner_body_swap->AddInstruction(null_check);
886 inner_body_swap->AddInstruction(array_length);
887 inner_body_swap->AddInstruction(bounds_check3);
888 inner_body_swap->AddInstruction(array_get_j_plus_1);
889 // array[j+1] = array[j]
890 null_check = new (&allocator_) HNullCheck(parameter, 0);
891 array_length = new (&allocator_) HArrayLength(null_check, 0);
892 HInstruction* bounds_check4 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
893 array_get_j = new (&allocator_)
894 HArrayGet(null_check, bounds_check4, Primitive::kPrimInt, 0);
895 inner_body_swap->AddInstruction(null_check);
896 inner_body_swap->AddInstruction(array_length);
897 inner_body_swap->AddInstruction(bounds_check4);
898 inner_body_swap->AddInstruction(array_get_j);
899 null_check = new (&allocator_) HNullCheck(parameter, 0);
900 array_length = new (&allocator_) HArrayLength(null_check, 0);
901 HInstruction* bounds_check5 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
902 HArraySet* array_set_j_plus_1 = new (&allocator_)
903 HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0);
904 inner_body_swap->AddInstruction(null_check);
905 inner_body_swap->AddInstruction(array_length);
906 inner_body_swap->AddInstruction(bounds_check5);
907 inner_body_swap->AddInstruction(array_set_j_plus_1);
908 // array[j] = temp
909 null_check = new (&allocator_) HNullCheck(parameter, 0);
910 array_length = new (&allocator_) HArrayLength(null_check, 0);
911 HInstruction* bounds_check6 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
912 HArraySet* array_set_j = new (&allocator_)
913 HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0);
914 inner_body_swap->AddInstruction(null_check);
915 inner_body_swap->AddInstruction(array_length);
916 inner_body_swap->AddInstruction(bounds_check6);
917 inner_body_swap->AddInstruction(array_set_j);
918 inner_body_swap->AddInstruction(new (&allocator_) HGoto());
919
920 HBasicBlock* inner_body_add = new (&allocator_) HBasicBlock(graph_);
921 graph_->AddBlock(inner_body_add);
922 add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
923 inner_body_add->AddInstruction(add);
924 inner_body_add->AddInstruction(new (&allocator_) HGoto());
925 phi_j->AddInput(add);
926
927 HBasicBlock* outer_body_add = new (&allocator_) HBasicBlock(graph_);
928 graph_->AddBlock(outer_body_add);
929 add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_i, constant_1);
930 outer_body_add->AddInstruction(add);
931 outer_body_add->AddInstruction(new (&allocator_) HGoto());
932 phi_i->AddInput(add);
933
934 block->AddSuccessor(outer_header);
935 outer_header->AddSuccessor(exit);
936 outer_header->AddSuccessor(inner_header);
937 inner_header->AddSuccessor(outer_body_add);
938 inner_header->AddSuccessor(inner_body_compare);
939 inner_body_compare->AddSuccessor(inner_body_add);
940 inner_body_compare->AddSuccessor(inner_body_swap);
941 inner_body_swap->AddSuccessor(inner_body_add);
942 inner_body_add->AddSuccessor(inner_header);
943 outer_body_add->AddSuccessor(outer_header);
944
945 RunBCE(); // gvn removes same bounds check already
946
947 ASSERT_TRUE(IsRemoved(bounds_check1));
948 ASSERT_TRUE(IsRemoved(bounds_check2));
949 ASSERT_TRUE(IsRemoved(bounds_check3));
950 ASSERT_TRUE(IsRemoved(bounds_check4));
951 ASSERT_TRUE(IsRemoved(bounds_check5));
952 ASSERT_TRUE(IsRemoved(bounds_check6));
953 }
954
955 } // namespace art
956