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 "bounds_check_elimination.h"
18
19 #include "base/arena_allocator.h"
20 #include "builder.h"
21 #include "gvn.h"
22 #include "induction_var_analysis.h"
23 #include "instruction_simplifier.h"
24 #include "nodes.h"
25 #include "optimizing_unit_test.h"
26 #include "side_effects_analysis.h"
27
28 #include "gtest/gtest.h"
29
30 namespace art {
31
32 /**
33 * Fixture class for the BoundsCheckElimination tests.
34 */
35 class BoundsCheckEliminationTest : public OptimizingUnitTest {
36 public:
BoundsCheckEliminationTest()37 BoundsCheckEliminationTest() : graph_(CreateGraph()) {
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 HGraph* graph_;
60 };
61
62
63 // if (i < 0) { array[i] = 1; // Can't eliminate. }
64 // else if (i >= array.length) { array[i] = 1; // Can't eliminate. }
65 // else { array[i] = 1; // Can eliminate. }
TEST_F(BoundsCheckEliminationTest,NarrowingRangeArrayBoundsElimination)66 TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
67 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
68 graph_->AddBlock(entry);
69 graph_->SetEntryBlock(entry);
70 HInstruction* parameter1 = new (GetAllocator()) HParameterValue(
71 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); // array
72 HInstruction* parameter2 = new (GetAllocator()) HParameterValue(
73 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32); // i
74 entry->AddInstruction(parameter1);
75 entry->AddInstruction(parameter2);
76
77 HInstruction* constant_1 = graph_->GetIntConstant(1);
78 HInstruction* constant_0 = graph_->GetIntConstant(0);
79
80 HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_);
81 graph_->AddBlock(block1);
82 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(parameter2, constant_0);
83 HIf* if_inst = new (GetAllocator()) HIf(cmp);
84 block1->AddInstruction(cmp);
85 block1->AddInstruction(if_inst);
86 entry->AddSuccessor(block1);
87
88 HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_);
89 graph_->AddBlock(block2);
90 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter1, 0);
91 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0);
92 HBoundsCheck* bounds_check2 = new (GetAllocator())
93 HBoundsCheck(parameter2, array_length, 0);
94 HArraySet* array_set = new (GetAllocator()) HArraySet(
95 null_check, bounds_check2, constant_1, DataType::Type::kInt32, 0);
96 block2->AddInstruction(null_check);
97 block2->AddInstruction(array_length);
98 block2->AddInstruction(bounds_check2);
99 block2->AddInstruction(array_set);
100
101 HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_);
102 graph_->AddBlock(block3);
103 null_check = new (GetAllocator()) HNullCheck(parameter1, 0);
104 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
105 cmp = new (GetAllocator()) HLessThan(parameter2, array_length);
106 if_inst = new (GetAllocator()) HIf(cmp);
107 block3->AddInstruction(null_check);
108 block3->AddInstruction(array_length);
109 block3->AddInstruction(cmp);
110 block3->AddInstruction(if_inst);
111
112 HBasicBlock* block4 = new (GetAllocator()) HBasicBlock(graph_);
113 graph_->AddBlock(block4);
114 null_check = new (GetAllocator()) HNullCheck(parameter1, 0);
115 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
116 HBoundsCheck* bounds_check4 = new (GetAllocator())
117 HBoundsCheck(parameter2, array_length, 0);
118 array_set = new (GetAllocator()) HArraySet(
119 null_check, bounds_check4, constant_1, DataType::Type::kInt32, 0);
120 block4->AddInstruction(null_check);
121 block4->AddInstruction(array_length);
122 block4->AddInstruction(bounds_check4);
123 block4->AddInstruction(array_set);
124
125 HBasicBlock* block5 = new (GetAllocator()) HBasicBlock(graph_);
126 graph_->AddBlock(block5);
127 null_check = new (GetAllocator()) HNullCheck(parameter1, 0);
128 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
129 HBoundsCheck* bounds_check5 = new (GetAllocator())
130 HBoundsCheck(parameter2, array_length, 0);
131 array_set = new (GetAllocator()) HArraySet(
132 null_check, bounds_check5, constant_1, DataType::Type::kInt32, 0);
133 block5->AddInstruction(null_check);
134 block5->AddInstruction(array_length);
135 block5->AddInstruction(bounds_check5);
136 block5->AddInstruction(array_set);
137
138 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
139 graph_->AddBlock(exit);
140 block2->AddSuccessor(exit);
141 block4->AddSuccessor(exit);
142 block5->AddSuccessor(exit);
143 exit->AddInstruction(new (GetAllocator()) HExit());
144
145 block1->AddSuccessor(block3); // True successor
146 block1->AddSuccessor(block2); // False successor
147
148 block3->AddSuccessor(block5); // True successor
149 block3->AddSuccessor(block4); // False successor
150
151 RunBCE();
152
153 ASSERT_FALSE(IsRemoved(bounds_check2));
154 ASSERT_FALSE(IsRemoved(bounds_check4));
155 ASSERT_TRUE(IsRemoved(bounds_check5));
156 }
157
158 // if (i > 0) {
159 // // Positive number plus MAX_INT will overflow and be negative.
160 // int j = i + Integer.MAX_VALUE;
161 // if (j < array.length) array[j] = 1; // Can't eliminate.
162 // }
TEST_F(BoundsCheckEliminationTest,OverflowArrayBoundsElimination)163 TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
164 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
165 graph_->AddBlock(entry);
166 graph_->SetEntryBlock(entry);
167 HInstruction* parameter1 = new (GetAllocator()) HParameterValue(
168 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); // array
169 HInstruction* parameter2 = new (GetAllocator()) HParameterValue(
170 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32); // i
171 entry->AddInstruction(parameter1);
172 entry->AddInstruction(parameter2);
173
174 HInstruction* constant_1 = graph_->GetIntConstant(1);
175 HInstruction* constant_0 = graph_->GetIntConstant(0);
176 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
177
178 HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_);
179 graph_->AddBlock(block1);
180 HInstruction* cmp = new (GetAllocator()) HLessThanOrEqual(parameter2, constant_0);
181 HIf* if_inst = new (GetAllocator()) HIf(cmp);
182 block1->AddInstruction(cmp);
183 block1->AddInstruction(if_inst);
184 entry->AddSuccessor(block1);
185
186 HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_);
187 graph_->AddBlock(block2);
188 HInstruction* add =
189 new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter2, constant_max_int);
190 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter1, 0);
191 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0);
192 HInstruction* cmp2 = new (GetAllocator()) HGreaterThanOrEqual(add, array_length);
193 if_inst = new (GetAllocator()) HIf(cmp2);
194 block2->AddInstruction(add);
195 block2->AddInstruction(null_check);
196 block2->AddInstruction(array_length);
197 block2->AddInstruction(cmp2);
198 block2->AddInstruction(if_inst);
199
200 HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_);
201 graph_->AddBlock(block3);
202 HBoundsCheck* bounds_check = new (GetAllocator())
203 HBoundsCheck(add, array_length, 0);
204 HArraySet* array_set = new (GetAllocator()) HArraySet(
205 null_check, bounds_check, constant_1, DataType::Type::kInt32, 0);
206 block3->AddInstruction(bounds_check);
207 block3->AddInstruction(array_set);
208
209 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
210 graph_->AddBlock(exit);
211 exit->AddInstruction(new (GetAllocator()) HExit());
212 block1->AddSuccessor(exit); // true successor
213 block1->AddSuccessor(block2); // false successor
214 block2->AddSuccessor(exit); // true successor
215 block2->AddSuccessor(block3); // false successor
216 block3->AddSuccessor(exit);
217
218 RunBCE();
219
220 ASSERT_FALSE(IsRemoved(bounds_check));
221 }
222
223 // if (i < array.length) {
224 // int j = i - Integer.MAX_VALUE;
225 // j = j - Integer.MAX_VALUE; // j is (i+2) after subtracting MAX_INT twice
226 // if (j > 0) array[j] = 1; // Can't eliminate.
227 // }
TEST_F(BoundsCheckEliminationTest,UnderflowArrayBoundsElimination)228 TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
229 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
230 graph_->AddBlock(entry);
231 graph_->SetEntryBlock(entry);
232 HInstruction* parameter1 = new (GetAllocator()) HParameterValue(
233 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); // array
234 HInstruction* parameter2 = new (GetAllocator()) HParameterValue(
235 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32); // i
236 entry->AddInstruction(parameter1);
237 entry->AddInstruction(parameter2);
238
239 HInstruction* constant_1 = graph_->GetIntConstant(1);
240 HInstruction* constant_0 = graph_->GetIntConstant(0);
241 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
242
243 HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_);
244 graph_->AddBlock(block1);
245 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter1, 0);
246 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0);
247 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(parameter2, array_length);
248 HIf* if_inst = new (GetAllocator()) HIf(cmp);
249 block1->AddInstruction(null_check);
250 block1->AddInstruction(array_length);
251 block1->AddInstruction(cmp);
252 block1->AddInstruction(if_inst);
253 entry->AddSuccessor(block1);
254
255 HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_);
256 graph_->AddBlock(block2);
257 HInstruction* sub1 =
258 new (GetAllocator()) HSub(DataType::Type::kInt32, parameter2, constant_max_int);
259 HInstruction* sub2 = new (GetAllocator()) HSub(DataType::Type::kInt32, sub1, constant_max_int);
260 HInstruction* cmp2 = new (GetAllocator()) HLessThanOrEqual(sub2, constant_0);
261 if_inst = new (GetAllocator()) HIf(cmp2);
262 block2->AddInstruction(sub1);
263 block2->AddInstruction(sub2);
264 block2->AddInstruction(cmp2);
265 block2->AddInstruction(if_inst);
266
267 HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_);
268 graph_->AddBlock(block3);
269 HBoundsCheck* bounds_check = new (GetAllocator())
270 HBoundsCheck(sub2, array_length, 0);
271 HArraySet* array_set = new (GetAllocator()) HArraySet(
272 null_check, bounds_check, constant_1, DataType::Type::kInt32, 0);
273 block3->AddInstruction(bounds_check);
274 block3->AddInstruction(array_set);
275
276 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
277 graph_->AddBlock(exit);
278 exit->AddInstruction(new (GetAllocator()) 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 (GetAllocator()) HBasicBlock(graph_);
295 graph_->AddBlock(entry);
296 graph_->SetEntryBlock(entry);
297 HInstruction* parameter = new (GetAllocator()) HParameterValue(
298 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
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 (GetAllocator()) HBasicBlock(graph_);
307 graph_->AddBlock(block);
308 entry->AddSuccessor(block);
309
310 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter, 0);
311 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0);
312 HBoundsCheck* bounds_check6 = new (GetAllocator())
313 HBoundsCheck(constant_6, array_length, 0);
314 HInstruction* array_set = new (GetAllocator()) HArraySet(
315 null_check, bounds_check6, constant_1, DataType::Type::kInt32, 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 (GetAllocator()) HNullCheck(parameter, 0);
322 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
323 HBoundsCheck* bounds_check5 = new (GetAllocator())
324 HBoundsCheck(constant_5, array_length, 0);
325 array_set = new (GetAllocator()) HArraySet(
326 null_check, bounds_check5, constant_1, DataType::Type::kInt32, 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 (GetAllocator()) HNullCheck(parameter, 0);
333 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
334 HBoundsCheck* bounds_check4 = new (GetAllocator())
335 HBoundsCheck(constant_4, array_length, 0);
336 array_set = new (GetAllocator()) HArraySet(
337 null_check, bounds_check4, constant_1, DataType::Type::kInt32, 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 (GetAllocator()) HGoto());
344
345 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
346 graph_->AddBlock(exit);
347 block->AddSuccessor(exit);
348 exit->AddInstruction(new (GetAllocator()) 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, DataType::Type::kReference);
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, DataType::Type::kInt32);
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, DataType::Type::kInt32, 0);
414
415 HInstruction* add = new (allocator) HAdd(DataType::Type::kInt32, 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_, GetAllocator(), 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_, GetAllocator(), 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_, GetAllocator(), -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_, GetAllocator(), 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_, GetAllocator(), 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_, GetAllocator(), 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, DataType::Type::kReference);
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, DataType::Type::kInt32);
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(DataType::Type::kInt32, 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, DataType::Type::kInt32, 0);
531 HInstruction* add_phi = new (allocator) HAdd(DataType::Type::kInt32, 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_, GetAllocator(), 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_, GetAllocator(), 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_, GetAllocator(), -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_, GetAllocator(), 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_, GetAllocator(), 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 /* cls= */ constant_10,
602 /* length= */ constant_10,
603 /* dex_pc= */ 0,
604 /* component_size_shift= */ 0);
605 block->AddInstruction(new_array);
606 block->AddInstruction(new (allocator) HGoto());
607
608 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
609 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
610 HBasicBlock* exit = new (allocator) HBasicBlock(graph);
611
612 graph->AddBlock(loop_header);
613 graph->AddBlock(loop_body);
614 graph->AddBlock(exit);
615 block->AddSuccessor(loop_header);
616 loop_header->AddSuccessor(exit); // true successor
617 loop_header->AddSuccessor(loop_body); // false successor
618 loop_body->AddSuccessor(loop_header);
619
620 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, DataType::Type::kInt32);
621 HInstruction* cmp = nullptr;
622 if (cond == kCondGE) {
623 cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10);
624 } else {
625 DCHECK(cond == kCondGT);
626 cmp = new (allocator) HGreaterThan(phi, constant_10);
627 }
628 HInstruction* if_inst = new (allocator) HIf(cmp);
629 loop_header->AddPhi(phi);
630 loop_header->AddInstruction(cmp);
631 loop_header->AddInstruction(if_inst);
632 phi->AddInput(constant_initial);
633
634 HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0);
635 HArrayLength* array_length = new (allocator) HArrayLength(null_check, 0);
636 HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
637 HInstruction* array_set = new (allocator) HArraySet(
638 null_check, bounds_check, constant_10, DataType::Type::kInt32, 0);
639 HInstruction* add = new (allocator) HAdd(DataType::Type::kInt32, phi, constant_increment);
640 loop_body->AddInstruction(null_check);
641 loop_body->AddInstruction(array_length);
642 loop_body->AddInstruction(bounds_check);
643 loop_body->AddInstruction(array_set);
644 loop_body->AddInstruction(add);
645 loop_body->AddInstruction(new (allocator) HGoto());
646 phi->AddInput(add);
647
648 exit->AddInstruction(new (allocator) HExit());
649
650 return bounds_check;
651 }
652
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3a)653 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) {
654 // int[] array = new int[10];
655 // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. }
656 HInstruction* bounds_check = BuildSSAGraph3(graph_, GetAllocator(), 0, 1, kCondGE);
657 RunBCE();
658 ASSERT_TRUE(IsRemoved(bounds_check));
659 }
660
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3b)661 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) {
662 // int[] array = new int[10];
663 // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
664 HInstruction* bounds_check = BuildSSAGraph3(graph_, GetAllocator(), 1, 1, kCondGE);
665 RunBCE();
666 ASSERT_TRUE(IsRemoved(bounds_check));
667 }
668
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3c)669 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) {
670 // int[] array = new int[10];
671 // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
672 HInstruction* bounds_check = BuildSSAGraph3(graph_, GetAllocator(), 0, 1, kCondGT);
673 RunBCE();
674 ASSERT_FALSE(IsRemoved(bounds_check));
675 }
676
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3d)677 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) {
678 // int[] array = new int[10];
679 // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
680 HInstruction* bounds_check = BuildSSAGraph3(graph_, GetAllocator(), 1, 8, kCondGE);
681 RunBCE();
682 ASSERT_TRUE(IsRemoved(bounds_check));
683 }
684
685 // for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; }
BuildSSAGraph4(HGraph * graph,ArenaAllocator * allocator,int initial,IfCondition cond=kCondGE)686 static HInstruction* BuildSSAGraph4(HGraph* graph,
687 ArenaAllocator* allocator,
688 int initial,
689 IfCondition cond = kCondGE) {
690 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
691 graph->AddBlock(entry);
692 graph->SetEntryBlock(entry);
693 HInstruction* parameter = new (allocator) HParameterValue(
694 graph->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
695 entry->AddInstruction(parameter);
696
697 HInstruction* constant_initial = graph->GetIntConstant(initial);
698 HInstruction* constant_1 = graph->GetIntConstant(1);
699 HInstruction* constant_10 = graph->GetIntConstant(10);
700 HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
701
702 HBasicBlock* block = new (allocator) HBasicBlock(graph);
703 graph->AddBlock(block);
704 entry->AddSuccessor(block);
705 block->AddInstruction(new (allocator) HGoto());
706
707 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
708 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
709 HBasicBlock* exit = new (allocator) HBasicBlock(graph);
710
711 graph->AddBlock(loop_header);
712 graph->AddBlock(loop_body);
713 graph->AddBlock(exit);
714 block->AddSuccessor(loop_header);
715 loop_header->AddSuccessor(exit); // true successor
716 loop_header->AddSuccessor(loop_body); // false successor
717 loop_body->AddSuccessor(loop_header);
718
719 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, DataType::Type::kInt32);
720 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
721 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0);
722 HInstruction* cmp = nullptr;
723 if (cond == kCondGE) {
724 cmp = new (allocator) HGreaterThanOrEqual(phi, array_length);
725 } else if (cond == kCondGT) {
726 cmp = new (allocator) HGreaterThan(phi, array_length);
727 }
728 HInstruction* if_inst = new (allocator) HIf(cmp);
729 loop_header->AddPhi(phi);
730 loop_header->AddInstruction(null_check);
731 loop_header->AddInstruction(array_length);
732 loop_header->AddInstruction(cmp);
733 loop_header->AddInstruction(if_inst);
734 phi->AddInput(constant_initial);
735
736 null_check = new (allocator) HNullCheck(parameter, 0);
737 array_length = new (allocator) HArrayLength(null_check, 0);
738 HInstruction* sub = new (allocator) HSub(DataType::Type::kInt32, array_length, phi);
739 HInstruction* add_minus_1 = new (allocator)
740 HAdd(DataType::Type::kInt32, sub, constant_minus_1);
741 HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0);
742 HInstruction* array_set = new (allocator) HArraySet(
743 null_check, bounds_check, constant_10, DataType::Type::kInt32, 0);
744 HInstruction* add = new (allocator) HAdd(DataType::Type::kInt32, phi, constant_1);
745 loop_body->AddInstruction(null_check);
746 loop_body->AddInstruction(array_length);
747 loop_body->AddInstruction(sub);
748 loop_body->AddInstruction(add_minus_1);
749 loop_body->AddInstruction(bounds_check);
750 loop_body->AddInstruction(array_set);
751 loop_body->AddInstruction(add);
752 loop_body->AddInstruction(new (allocator) HGoto());
753 phi->AddInput(add);
754
755 exit->AddInstruction(new (allocator) HExit());
756
757 return bounds_check;
758 }
759
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4a)760 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) {
761 // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. }
762 HInstruction* bounds_check = BuildSSAGraph4(graph_, GetAllocator(), 0);
763 RunBCE();
764 ASSERT_TRUE(IsRemoved(bounds_check));
765 }
766
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4b)767 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) {
768 // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
769 HInstruction* bounds_check = BuildSSAGraph4(graph_, GetAllocator(), 1);
770 RunBCE();
771 ASSERT_TRUE(IsRemoved(bounds_check));
772 }
773
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4c)774 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) {
775 // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
776 HInstruction* bounds_check = BuildSSAGraph4(graph_, GetAllocator(), 0, kCondGT);
777 RunBCE();
778 ASSERT_FALSE(IsRemoved(bounds_check));
779 }
780
781 // Bubble sort:
782 // (Every array access bounds-check can be eliminated.)
783 // for (int i=0; i<array.length-1; i++) {
784 // for (int j=0; j<array.length-i-1; j++) {
785 // if (array[j] > array[j+1]) {
786 // int temp = array[j+1];
787 // array[j+1] = array[j];
788 // array[j] = temp;
789 // }
790 // }
791 // }
TEST_F(BoundsCheckEliminationTest,BubbleSortArrayBoundsElimination)792 TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
793 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
794 graph_->AddBlock(entry);
795 graph_->SetEntryBlock(entry);
796 HInstruction* parameter = new (GetAllocator()) HParameterValue(
797 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference);
798 entry->AddInstruction(parameter);
799
800 HInstruction* constant_0 = graph_->GetIntConstant(0);
801 HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
802 HInstruction* constant_1 = graph_->GetIntConstant(1);
803
804 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
805 graph_->AddBlock(block);
806 entry->AddSuccessor(block);
807 block->AddInstruction(new (GetAllocator()) HGoto());
808
809 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
810 graph_->AddBlock(exit);
811 exit->AddInstruction(new (GetAllocator()) HExit());
812
813 HBasicBlock* outer_header = new (GetAllocator()) HBasicBlock(graph_);
814 graph_->AddBlock(outer_header);
815 HPhi* phi_i = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
816 HNullCheck* null_check = new (GetAllocator()) HNullCheck(parameter, 0);
817 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0);
818 HAdd* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, array_length, constant_minus_1);
819 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(phi_i, add);
820 HIf* if_inst = new (GetAllocator()) HIf(cmp);
821 outer_header->AddPhi(phi_i);
822 outer_header->AddInstruction(null_check);
823 outer_header->AddInstruction(array_length);
824 outer_header->AddInstruction(add);
825 outer_header->AddInstruction(cmp);
826 outer_header->AddInstruction(if_inst);
827 phi_i->AddInput(constant_0);
828
829 HBasicBlock* inner_header = new (GetAllocator()) HBasicBlock(graph_);
830 graph_->AddBlock(inner_header);
831 HPhi* phi_j = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
832 null_check = new (GetAllocator()) HNullCheck(parameter, 0);
833 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
834 HSub* sub = new (GetAllocator()) HSub(DataType::Type::kInt32, array_length, phi_i);
835 add = new (GetAllocator()) HAdd(DataType::Type::kInt32, sub, constant_minus_1);
836 cmp = new (GetAllocator()) HGreaterThanOrEqual(phi_j, add);
837 if_inst = new (GetAllocator()) HIf(cmp);
838 inner_header->AddPhi(phi_j);
839 inner_header->AddInstruction(null_check);
840 inner_header->AddInstruction(array_length);
841 inner_header->AddInstruction(sub);
842 inner_header->AddInstruction(add);
843 inner_header->AddInstruction(cmp);
844 inner_header->AddInstruction(if_inst);
845 phi_j->AddInput(constant_0);
846
847 HBasicBlock* inner_body_compare = new (GetAllocator()) HBasicBlock(graph_);
848 graph_->AddBlock(inner_body_compare);
849 null_check = new (GetAllocator()) HNullCheck(parameter, 0);
850 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
851 HBoundsCheck* bounds_check1 = new (GetAllocator()) HBoundsCheck(phi_j, array_length, 0);
852 HArrayGet* array_get_j = new (GetAllocator())
853 HArrayGet(null_check, bounds_check1, DataType::Type::kInt32, 0);
854 inner_body_compare->AddInstruction(null_check);
855 inner_body_compare->AddInstruction(array_length);
856 inner_body_compare->AddInstruction(bounds_check1);
857 inner_body_compare->AddInstruction(array_get_j);
858 HInstruction* j_plus_1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_j, constant_1);
859 null_check = new (GetAllocator()) HNullCheck(parameter, 0);
860 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
861 HBoundsCheck* bounds_check2 = new (GetAllocator()) HBoundsCheck(j_plus_1, array_length, 0);
862 HArrayGet* array_get_j_plus_1 = new (GetAllocator())
863 HArrayGet(null_check, bounds_check2, DataType::Type::kInt32, 0);
864 cmp = new (GetAllocator()) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1);
865 if_inst = new (GetAllocator()) HIf(cmp);
866 inner_body_compare->AddInstruction(j_plus_1);
867 inner_body_compare->AddInstruction(null_check);
868 inner_body_compare->AddInstruction(array_length);
869 inner_body_compare->AddInstruction(bounds_check2);
870 inner_body_compare->AddInstruction(array_get_j_plus_1);
871 inner_body_compare->AddInstruction(cmp);
872 inner_body_compare->AddInstruction(if_inst);
873
874 HBasicBlock* inner_body_swap = new (GetAllocator()) HBasicBlock(graph_);
875 graph_->AddBlock(inner_body_swap);
876 j_plus_1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_j, constant_1);
877 // temp = array[j+1]
878 null_check = new (GetAllocator()) HNullCheck(parameter, 0);
879 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
880 HInstruction* bounds_check3 = new (GetAllocator()) HBoundsCheck(j_plus_1, array_length, 0);
881 array_get_j_plus_1 = new (GetAllocator())
882 HArrayGet(null_check, bounds_check3, DataType::Type::kInt32, 0);
883 inner_body_swap->AddInstruction(j_plus_1);
884 inner_body_swap->AddInstruction(null_check);
885 inner_body_swap->AddInstruction(array_length);
886 inner_body_swap->AddInstruction(bounds_check3);
887 inner_body_swap->AddInstruction(array_get_j_plus_1);
888 // array[j+1] = array[j]
889 null_check = new (GetAllocator()) HNullCheck(parameter, 0);
890 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
891 HInstruction* bounds_check4 = new (GetAllocator()) HBoundsCheck(phi_j, array_length, 0);
892 array_get_j = new (GetAllocator())
893 HArrayGet(null_check, bounds_check4, DataType::Type::kInt32, 0);
894 inner_body_swap->AddInstruction(null_check);
895 inner_body_swap->AddInstruction(array_length);
896 inner_body_swap->AddInstruction(bounds_check4);
897 inner_body_swap->AddInstruction(array_get_j);
898 null_check = new (GetAllocator()) HNullCheck(parameter, 0);
899 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
900 HInstruction* bounds_check5 = new (GetAllocator()) HBoundsCheck(j_plus_1, array_length, 0);
901 HArraySet* array_set_j_plus_1 = new (GetAllocator())
902 HArraySet(null_check, bounds_check5, array_get_j, DataType::Type::kInt32, 0);
903 inner_body_swap->AddInstruction(null_check);
904 inner_body_swap->AddInstruction(array_length);
905 inner_body_swap->AddInstruction(bounds_check5);
906 inner_body_swap->AddInstruction(array_set_j_plus_1);
907 // array[j] = temp
908 null_check = new (GetAllocator()) HNullCheck(parameter, 0);
909 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
910 HInstruction* bounds_check6 = new (GetAllocator()) HBoundsCheck(phi_j, array_length, 0);
911 HArraySet* array_set_j = new (GetAllocator())
912 HArraySet(null_check, bounds_check6, array_get_j_plus_1, DataType::Type::kInt32, 0);
913 inner_body_swap->AddInstruction(null_check);
914 inner_body_swap->AddInstruction(array_length);
915 inner_body_swap->AddInstruction(bounds_check6);
916 inner_body_swap->AddInstruction(array_set_j);
917 inner_body_swap->AddInstruction(new (GetAllocator()) HGoto());
918
919 HBasicBlock* inner_body_add = new (GetAllocator()) HBasicBlock(graph_);
920 graph_->AddBlock(inner_body_add);
921 add = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_j, constant_1);
922 inner_body_add->AddInstruction(add);
923 inner_body_add->AddInstruction(new (GetAllocator()) HGoto());
924 phi_j->AddInput(add);
925
926 HBasicBlock* outer_body_add = new (GetAllocator()) HBasicBlock(graph_);
927 graph_->AddBlock(outer_body_add);
928 add = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_i, constant_1);
929 outer_body_add->AddInstruction(add);
930 outer_body_add->AddInstruction(new (GetAllocator()) HGoto());
931 phi_i->AddInput(add);
932
933 block->AddSuccessor(outer_header);
934 outer_header->AddSuccessor(exit);
935 outer_header->AddSuccessor(inner_header);
936 inner_header->AddSuccessor(outer_body_add);
937 inner_header->AddSuccessor(inner_body_compare);
938 inner_body_compare->AddSuccessor(inner_body_add);
939 inner_body_compare->AddSuccessor(inner_body_swap);
940 inner_body_swap->AddSuccessor(inner_body_add);
941 inner_body_add->AddSuccessor(inner_header);
942 outer_body_add->AddSuccessor(outer_header);
943
944 RunBCE(); // gvn removes same bounds check already
945
946 ASSERT_TRUE(IsRemoved(bounds_check1));
947 ASSERT_TRUE(IsRemoved(bounds_check2));
948 ASSERT_TRUE(IsRemoved(bounds_check3));
949 ASSERT_TRUE(IsRemoved(bounds_check4));
950 ASSERT_TRUE(IsRemoved(bounds_check5));
951 ASSERT_TRUE(IsRemoved(bounds_check6));
952 }
953
954 // int[] array = new int[10];
955 // for (int i=0; i<200; i++) {
956 // array[i%10] = 10; // Can eliminate
957 // array[i%1] = 10; // Can eliminate
958 // array[i%200] = 10; // Cannot eliminate
959 // array[i%-10] = 10; // Can eliminate
960 // array[i%array.length] = 10; // Can eliminate
961 // array[param_i%10] = 10; // Can't eliminate, when param_i < 0
962 // }
TEST_F(BoundsCheckEliminationTest,ModArrayBoundsElimination)963 TEST_F(BoundsCheckEliminationTest, ModArrayBoundsElimination) {
964 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
965 graph_->AddBlock(entry);
966 graph_->SetEntryBlock(entry);
967 HInstruction* param_i = new (GetAllocator())
968 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32);
969 entry->AddInstruction(param_i);
970
971 HInstruction* constant_0 = graph_->GetIntConstant(0);
972 HInstruction* constant_1 = graph_->GetIntConstant(1);
973 HInstruction* constant_10 = graph_->GetIntConstant(10);
974 HInstruction* constant_200 = graph_->GetIntConstant(200);
975 HInstruction* constant_minus_10 = graph_->GetIntConstant(-10);
976
977 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
978 graph_->AddBlock(block);
979 entry->AddSuccessor(block);
980 // We pass a bogus constant for the class to avoid mocking one.
981 HInstruction* new_array = new (GetAllocator()) HNewArray(
982 /* cls= */ constant_10,
983 /* length= */ constant_10,
984 /* dex_pc= */ 0,
985 /* component_size_shift= */ 0);
986 block->AddInstruction(new_array);
987 block->AddInstruction(new (GetAllocator()) HGoto());
988
989 HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
990 HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
991 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
992
993 graph_->AddBlock(loop_header);
994 graph_->AddBlock(loop_body);
995 graph_->AddBlock(exit);
996 block->AddSuccessor(loop_header);
997 loop_header->AddSuccessor(exit); // true successor
998 loop_header->AddSuccessor(loop_body); // false successor
999 loop_body->AddSuccessor(loop_header);
1000
1001 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
1002 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(phi, constant_200);
1003 HInstruction* if_inst = new (GetAllocator()) HIf(cmp);
1004 loop_header->AddPhi(phi);
1005 loop_header->AddInstruction(cmp);
1006 loop_header->AddInstruction(if_inst);
1007 phi->AddInput(constant_0);
1008
1009 //////////////////////////////////////////////////////////////////////////////////
1010 // LOOP BODY:
1011 // array[i % 10] = 10;
1012 HRem* i_mod_10 = new (GetAllocator()) HRem(DataType::Type::kInt32, phi, constant_10, 0);
1013 HBoundsCheck* bounds_check_i_mod_10 = new (GetAllocator()) HBoundsCheck(i_mod_10, constant_10, 0);
1014 HInstruction* array_set = new (GetAllocator()) HArraySet(
1015 new_array, bounds_check_i_mod_10, constant_10, DataType::Type::kInt32, 0);
1016 loop_body->AddInstruction(i_mod_10);
1017 loop_body->AddInstruction(bounds_check_i_mod_10);
1018 loop_body->AddInstruction(array_set);
1019
1020 // array[i % 1] = 10;
1021 HRem* i_mod_1 = new (GetAllocator()) HRem(DataType::Type::kInt32, phi, constant_1, 0);
1022 HBoundsCheck* bounds_check_i_mod_1 = new (GetAllocator()) HBoundsCheck(i_mod_1, constant_10, 0);
1023 array_set = new (GetAllocator()) HArraySet(
1024 new_array, bounds_check_i_mod_1, constant_10, DataType::Type::kInt32, 0);
1025 loop_body->AddInstruction(i_mod_1);
1026 loop_body->AddInstruction(bounds_check_i_mod_1);
1027 loop_body->AddInstruction(array_set);
1028
1029 // array[i % 200] = 10;
1030 HRem* i_mod_200 = new (GetAllocator()) HRem(DataType::Type::kInt32, phi, constant_1, 0);
1031 HBoundsCheck* bounds_check_i_mod_200 = new (GetAllocator()) HBoundsCheck(
1032 i_mod_200, constant_10, 0);
1033 array_set = new (GetAllocator()) HArraySet(
1034 new_array, bounds_check_i_mod_200, constant_10, DataType::Type::kInt32, 0);
1035 loop_body->AddInstruction(i_mod_200);
1036 loop_body->AddInstruction(bounds_check_i_mod_200);
1037 loop_body->AddInstruction(array_set);
1038
1039 // array[i % -10] = 10;
1040 HRem* i_mod_minus_10 = new (GetAllocator()) HRem(
1041 DataType::Type::kInt32, phi, constant_minus_10, 0);
1042 HBoundsCheck* bounds_check_i_mod_minus_10 = new (GetAllocator()) HBoundsCheck(
1043 i_mod_minus_10, constant_10, 0);
1044 array_set = new (GetAllocator()) HArraySet(
1045 new_array, bounds_check_i_mod_minus_10, constant_10, DataType::Type::kInt32, 0);
1046 loop_body->AddInstruction(i_mod_minus_10);
1047 loop_body->AddInstruction(bounds_check_i_mod_minus_10);
1048 loop_body->AddInstruction(array_set);
1049
1050 // array[i%array.length] = 10;
1051 HNullCheck* null_check = new (GetAllocator()) HNullCheck(new_array, 0);
1052 HArrayLength* array_length = new (GetAllocator()) HArrayLength(null_check, 0);
1053 HRem* i_mod_array_length = new (GetAllocator()) HRem(
1054 DataType::Type::kInt32, phi, array_length, 0);
1055 HBoundsCheck* bounds_check_i_mod_array_len = new (GetAllocator()) HBoundsCheck(
1056 i_mod_array_length, array_length, 0);
1057 array_set = new (GetAllocator()) HArraySet(
1058 null_check, bounds_check_i_mod_array_len, constant_10, DataType::Type::kInt32, 0);
1059 loop_body->AddInstruction(null_check);
1060 loop_body->AddInstruction(array_length);
1061 loop_body->AddInstruction(i_mod_array_length);
1062 loop_body->AddInstruction(bounds_check_i_mod_array_len);
1063 loop_body->AddInstruction(array_set);
1064
1065 // array[param_i % 10] = 10;
1066 HRem* param_i_mod_10 = new (GetAllocator()) HRem(DataType::Type::kInt32, param_i, constant_10, 0);
1067 HBoundsCheck* bounds_check_param_i_mod_10 = new (GetAllocator()) HBoundsCheck(
1068 param_i_mod_10, constant_10, 0);
1069 array_set = new (GetAllocator()) HArraySet(
1070 new_array, bounds_check_param_i_mod_10, constant_10, DataType::Type::kInt32, 0);
1071 loop_body->AddInstruction(param_i_mod_10);
1072 loop_body->AddInstruction(bounds_check_param_i_mod_10);
1073 loop_body->AddInstruction(array_set);
1074
1075 // array[param_i%array.length] = 10;
1076 null_check = new (GetAllocator()) HNullCheck(new_array, 0);
1077 array_length = new (GetAllocator()) HArrayLength(null_check, 0);
1078 HRem* param_i_mod_array_length = new (GetAllocator()) HRem(
1079 DataType::Type::kInt32, param_i, array_length, 0);
1080 HBoundsCheck* bounds_check_param_i_mod_array_len = new (GetAllocator()) HBoundsCheck(
1081 param_i_mod_array_length, array_length, 0);
1082 array_set = new (GetAllocator()) HArraySet(
1083 null_check, bounds_check_param_i_mod_array_len, constant_10, DataType::Type::kInt32, 0);
1084 loop_body->AddInstruction(null_check);
1085 loop_body->AddInstruction(array_length);
1086 loop_body->AddInstruction(param_i_mod_array_length);
1087 loop_body->AddInstruction(bounds_check_param_i_mod_array_len);
1088 loop_body->AddInstruction(array_set);
1089
1090 // i++;
1091 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, constant_1);
1092 loop_body->AddInstruction(add);
1093 loop_body->AddInstruction(new (GetAllocator()) HGoto());
1094 phi->AddInput(add);
1095 //////////////////////////////////////////////////////////////////////////////////
1096
1097 exit->AddInstruction(new (GetAllocator()) HExit());
1098
1099 RunBCE();
1100
1101 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_10));
1102 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_1));
1103 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_200));
1104 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_minus_10));
1105 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_array_len));
1106 ASSERT_FALSE(IsRemoved(bounds_check_param_i_mod_10));
1107 }
1108
1109 } // namespace art
1110