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
29namespace art {
30
31/**
32 * Fixture class for the BoundsCheckElimination tests.
33 */
34class BoundsCheckEliminationTest : public testing::Test {
35 public:
36  BoundsCheckEliminationTest()  : pool_(), allocator_(&pool_) {
37    graph_ = CreateGraph(&allocator_);
38    graph_->SetHasBoundsChecks(true);
39  }
40
41  ~BoundsCheckEliminationTest() { }
42
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. }
68TEST_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// }
165TEST_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// }
229TEST_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.
293TEST_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; }
358static 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
429TEST_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
436TEST_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
443TEST_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
450TEST_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
457TEST_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
465TEST_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; }
473static 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
546TEST_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
553TEST_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
560TEST_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
567TEST_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
574TEST_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; }
583static 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
654TEST_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
662TEST_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
670TEST_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
678TEST_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; }
687static 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
761TEST_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
768TEST_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
775TEST_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// }
793TEST_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