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 "base/macros.h"
21 #include "builder.h"
22 #include "gvn.h"
23 #include "induction_var_analysis.h"
24 #include "instruction_simplifier.h"
25 #include "nodes.h"
26 #include "optimizing_unit_test.h"
27 #include "side_effects_analysis.h"
28
29 #include "gtest/gtest.h"
30
31 namespace art HIDDEN {
32
33 /**
34 * Fixture class for the BoundsCheckElimination tests.
35 */
36 class BoundsCheckEliminationTest : public OptimizingUnitTest {
37 public:
RunBCE()38 void RunBCE() {
39 graph_->SetHasBoundsChecks(true);
40 graph_->BuildDominatorTree();
41
42 InstructionSimplifier(graph_, /* codegen= */ nullptr).Run();
43
44 SideEffectsAnalysis side_effects(graph_);
45 side_effects.Run();
46
47 GVNOptimization(graph_, side_effects).Run();
48
49 HInductionVarAnalysis induction(graph_);
50 induction.Run();
51
52 BoundsCheckElimination(graph_, side_effects, &induction).Run();
53 }
54
55 HInstruction* BuildSSAGraph1(int initial, int increment, IfCondition cond = kCondGE);
56 HInstruction* BuildSSAGraph2(int initial, int increment = -1, IfCondition cond = kCondLE);
57 HInstruction* BuildSSAGraph3(int initial, int increment, IfCondition cond);
58 HInstruction* BuildSSAGraph4(int initial, IfCondition cond = kCondGE);
59 };
60
61
62 // if (i < 0) { array[i] = 1; // Can't eliminate. }
63 // else if (i >= array.length) { array[i] = 1; // Can't eliminate. }
64 // else { array[i] = 1; // Can eliminate. }
TEST_F(BoundsCheckEliminationTest,NarrowingRangeArrayBoundsElimination)65 TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
66 CreateGraph();
67 HBasicBlock* entry = AddNewBlock();
68 graph_->SetEntryBlock(entry);
69 HInstruction* parameter1 = MakeParam(DataType::Type::kReference); // array
70 HInstruction* parameter2 = MakeParam(DataType::Type::kInt32); // i
71
72 HInstruction* constant_1 = graph_->GetIntConstant(1);
73 HInstruction* constant_0 = graph_->GetIntConstant(0);
74
75 HBasicBlock* block1 = AddNewBlock();
76 HInstruction* cmp = MakeCondition(block1, kCondGE, parameter2, constant_0);
77 MakeIf(block1, cmp);
78 entry->AddSuccessor(block1);
79
80 HBasicBlock* block2 = AddNewBlock();
81 HNullCheck* null_check = MakeNullCheck(block2, parameter1);
82 HArrayLength* array_length = MakeArrayLength(block2, null_check);
83 HBoundsCheck* bounds_check2 = MakeBoundsCheck(block2, parameter2, array_length);
84 MakeArraySet(block2, null_check, bounds_check2, constant_1, DataType::Type::kInt32);
85
86 HBasicBlock* block3 = AddNewBlock();
87 null_check = MakeNullCheck(block3, parameter1);
88 array_length = MakeArrayLength(block3, null_check);
89 cmp = MakeCondition(block3, kCondLT, parameter2, array_length);
90 MakeIf(block3, cmp);
91
92 HBasicBlock* block4 = AddNewBlock();
93 null_check = MakeNullCheck(block4, parameter1);
94 array_length = MakeArrayLength(block4, null_check);
95 HBoundsCheck* bounds_check4 = MakeBoundsCheck(block4, parameter2, array_length);
96 MakeArraySet(block4, null_check, bounds_check4, constant_1, DataType::Type::kInt32);
97
98 HBasicBlock* block5 = AddNewBlock();
99 null_check = MakeNullCheck(block5, parameter1);
100 array_length = MakeArrayLength(block5, null_check);
101 HBoundsCheck* bounds_check5 = MakeBoundsCheck(block5, parameter2, array_length);
102 MakeArraySet(block5, null_check, bounds_check5, constant_1, DataType::Type::kInt32);
103
104 HBasicBlock* exit = AddNewBlock();
105 block2->AddSuccessor(exit);
106 block4->AddSuccessor(exit);
107 block5->AddSuccessor(exit);
108 MakeExit(exit);
109
110 block1->AddSuccessor(block3); // True successor
111 block1->AddSuccessor(block2); // False successor
112
113 block3->AddSuccessor(block5); // True successor
114 block3->AddSuccessor(block4); // False successor
115
116 RunBCE();
117
118 ASSERT_FALSE(IsRemoved(bounds_check2));
119 ASSERT_FALSE(IsRemoved(bounds_check4));
120 ASSERT_TRUE(IsRemoved(bounds_check5));
121 }
122
123 // if (i > 0) {
124 // // Positive number plus MAX_INT will overflow and be negative.
125 // int j = i + Integer.MAX_VALUE;
126 // if (j < array.length) array[j] = 1; // Can't eliminate.
127 // }
TEST_F(BoundsCheckEliminationTest,OverflowArrayBoundsElimination)128 TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
129 CreateGraph();
130 HBasicBlock* entry = AddNewBlock();
131 graph_->SetEntryBlock(entry);
132 HInstruction* parameter1 = MakeParam(DataType::Type::kReference); // array
133 HInstruction* parameter2 = MakeParam(DataType::Type::kInt32); // i
134
135 HInstruction* constant_1 = graph_->GetIntConstant(1);
136 HInstruction* constant_0 = graph_->GetIntConstant(0);
137 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
138
139 HBasicBlock* block1 = AddNewBlock();
140 HInstruction* cmp = MakeCondition(block1, kCondLE, parameter2, constant_0);
141 MakeIf(block1, cmp);
142 entry->AddSuccessor(block1);
143
144 HBasicBlock* block2 = AddNewBlock();
145 HInstruction* add = MakeBinOp<HAdd>(block2, DataType::Type::kInt32, parameter2, constant_max_int);
146 HNullCheck* null_check = MakeNullCheck(block2, parameter1);
147 HArrayLength* array_length = MakeArrayLength(block2, null_check);
148 HInstruction* cmp2 = MakeCondition(block2, kCondGE, add, array_length);
149 MakeIf(block2, cmp2);
150
151 HBasicBlock* block3 = AddNewBlock();
152 HBoundsCheck* bounds_check = MakeBoundsCheck(block3, add, array_length);
153 MakeArraySet(block3, null_check, bounds_check, constant_1, DataType::Type::kInt32);
154
155 HBasicBlock* exit = AddNewBlock();
156 MakeExit(exit);
157 block1->AddSuccessor(exit); // true successor
158 block1->AddSuccessor(block2); // false successor
159 block2->AddSuccessor(exit); // true successor
160 block2->AddSuccessor(block3); // false successor
161 block3->AddSuccessor(exit);
162
163 RunBCE();
164
165 ASSERT_FALSE(IsRemoved(bounds_check));
166 }
167
168 // if (i < array.length) {
169 // int j = i - Integer.MAX_VALUE;
170 // j = j - Integer.MAX_VALUE; // j is (i+2) after subtracting MAX_INT twice
171 // if (j > 0) array[j] = 1; // Can't eliminate.
172 // }
TEST_F(BoundsCheckEliminationTest,UnderflowArrayBoundsElimination)173 TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
174 CreateGraph();
175 HBasicBlock* entry = AddNewBlock();
176 graph_->SetEntryBlock(entry);
177 HInstruction* parameter1 = MakeParam(DataType::Type::kReference); // array
178 HInstruction* parameter2 = MakeParam(DataType::Type::kInt32); // i
179
180 HInstruction* constant_1 = graph_->GetIntConstant(1);
181 HInstruction* constant_0 = graph_->GetIntConstant(0);
182 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
183
184 HBasicBlock* block1 = AddNewBlock();
185 HNullCheck* null_check = MakeNullCheck(block1, parameter1);
186 HArrayLength* array_length = MakeArrayLength(block1, null_check);
187 HInstruction* cmp = MakeCondition(block1, kCondGE, parameter2, array_length);
188 MakeIf(block1, cmp);
189 entry->AddSuccessor(block1);
190
191 HBasicBlock* block2 = AddNewBlock();
192 HInstruction* sub1 =
193 MakeBinOp<HSub>(block2, DataType::Type::kInt32, parameter2, constant_max_int);
194 HInstruction* sub2 = MakeBinOp<HSub>(block2, DataType::Type::kInt32, sub1, constant_max_int);
195 HInstruction* cmp2 = MakeCondition(block2, kCondLE, sub2, constant_0);
196 MakeIf(block2, cmp2);
197
198 HBasicBlock* block3 = AddNewBlock();
199 HBoundsCheck* bounds_check = MakeBoundsCheck(block3, sub2, array_length);
200 MakeArraySet(block3, null_check, bounds_check, constant_1, DataType::Type::kInt32);
201
202 HBasicBlock* exit = AddNewBlock();
203 MakeExit(exit);
204 block1->AddSuccessor(exit); // true successor
205 block1->AddSuccessor(block2); // false successor
206 block2->AddSuccessor(exit); // true successor
207 block2->AddSuccessor(block3); // false successor
208 block3->AddSuccessor(exit);
209
210 RunBCE();
211
212 ASSERT_FALSE(IsRemoved(bounds_check));
213 }
214
215 // array[6] = 1; // Can't eliminate.
216 // array[5] = 1; // Can eliminate.
217 // array[4] = 1; // Can eliminate.
TEST_F(BoundsCheckEliminationTest,ConstantArrayBoundsElimination)218 TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
219 HBasicBlock* block = InitEntryMainExitGraphWithReturnVoid();
220
221 HInstruction* parameter = MakeParam(DataType::Type::kReference);
222 HInstruction* constant_5 = graph_->GetIntConstant(5);
223 HInstruction* constant_4 = graph_->GetIntConstant(4);
224 HInstruction* constant_6 = graph_->GetIntConstant(6);
225 HInstruction* constant_1 = graph_->GetIntConstant(1);
226
227 HNullCheck* null_check = MakeNullCheck(block, parameter);
228 HArrayLength* array_length = MakeArrayLength(block, null_check);
229 HBoundsCheck* bounds_check6 = MakeBoundsCheck(block, constant_6, array_length);
230 MakeArraySet(block, null_check, bounds_check6, constant_1, DataType::Type::kInt32);
231
232 null_check = MakeNullCheck(block, parameter);
233 array_length = MakeArrayLength(block, null_check);
234 HBoundsCheck* bounds_check5 = MakeBoundsCheck(block, constant_5, array_length);
235 MakeArraySet(block, null_check, bounds_check5, constant_1, DataType::Type::kInt32);
236
237 null_check = MakeNullCheck(block, parameter);
238 array_length = MakeArrayLength(block, null_check);
239 HBoundsCheck* bounds_check4 = MakeBoundsCheck(block, constant_4, array_length);
240 MakeArraySet(block, null_check, bounds_check4, constant_1, DataType::Type::kInt32);
241
242 RunBCE();
243
244 ASSERT_FALSE(IsRemoved(bounds_check6));
245 ASSERT_TRUE(IsRemoved(bounds_check5));
246 ASSERT_TRUE(IsRemoved(bounds_check4));
247 }
248
249 // for (int i=initial; i<array.length; i+=increment) { array[i] = 10; }
BuildSSAGraph1(int initial,int increment,IfCondition cond)250 HInstruction* BoundsCheckEliminationTest::BuildSSAGraph1(int initial,
251 int increment,
252 IfCondition cond) {
253 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
254 auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
255
256 HInstruction* parameter = MakeParam(DataType::Type::kReference);
257 HInstruction* constant_10 = graph_->GetIntConstant(10);
258
259 auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, initial, increment);
260 HInstruction* null_check = MakeNullCheck(loop_header, parameter);
261 HInstruction* array_length = MakeArrayLength(loop_header, null_check);
262 DCHECK(cond == kCondGE || cond == kCondGT) << cond;
263 HInstruction* cmp = MakeCondition(loop_header, cond, phi, array_length);
264 MakeIf(loop_header, cmp);
265
266 null_check = MakeNullCheck(loop_body, parameter);
267 array_length = MakeArrayLength(loop_body, null_check);
268 HInstruction* bounds_check = MakeBoundsCheck(loop_body, phi, array_length);
269 MakeArraySet(loop_body, null_check, bounds_check, constant_10, DataType::Type::kInt32);
270
271 return bounds_check;
272 }
273
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1a)274 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1a) {
275 // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. }
276 HInstruction* bounds_check = BuildSSAGraph1(0, 1);
277 RunBCE();
278 ASSERT_TRUE(IsRemoved(bounds_check));
279 }
280
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1b)281 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1b) {
282 // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. }
283 HInstruction* bounds_check = BuildSSAGraph1(1, 1);
284 RunBCE();
285 ASSERT_TRUE(IsRemoved(bounds_check));
286 }
287
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1c)288 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1c) {
289 // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. }
290 HInstruction* bounds_check = BuildSSAGraph1(-1, 1);
291 RunBCE();
292 ASSERT_FALSE(IsRemoved(bounds_check));
293 }
294
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1d)295 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1d) {
296 // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. }
297 HInstruction* bounds_check = BuildSSAGraph1(0, 1, kCondGT);
298 RunBCE();
299 ASSERT_FALSE(IsRemoved(bounds_check));
300 }
301
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1e)302 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1e) {
303 // for (int i=0; i<array.length; i += 2) {
304 // array[i] = 10; // Can't eliminate due to overflow concern. }
305 HInstruction* bounds_check = BuildSSAGraph1(0, 2);
306 RunBCE();
307 ASSERT_FALSE(IsRemoved(bounds_check));
308 }
309
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination1f)310 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1f) {
311 // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. }
312 HInstruction* bounds_check = BuildSSAGraph1(1, 2);
313 RunBCE();
314 ASSERT_TRUE(IsRemoved(bounds_check));
315 }
316
317 // for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; }
BuildSSAGraph2(int initial,int increment,IfCondition cond)318 HInstruction* BoundsCheckEliminationTest::BuildSSAGraph2(int initial,
319 int increment,
320 IfCondition cond) {
321 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
322 auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
323
324 HInstruction* parameter = MakeParam(DataType::Type::kReference);
325 HInstruction* constant_initial = graph_->GetIntConstant(initial);
326 HInstruction* constant_increment = graph_->GetIntConstant(increment);
327 HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
328 HInstruction* constant_10 = graph_->GetIntConstant(10);
329
330 HInstruction* null_check = MakeNullCheck(pre_header, parameter);
331 HInstruction* array_length = MakeArrayLength(pre_header, null_check);
332
333 auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, array_length, constant_minus_1);
334 DCHECK(cond == kCondLE || cond == kCondLT) << cond;
335 HInstruction* cmp = MakeCondition(loop_header, cond, phi, constant_initial);
336 MakeIf(loop_header, cmp);
337
338 null_check = MakeNullCheck(loop_body, parameter);
339 array_length = MakeArrayLength(loop_body, null_check);
340 HInstruction* bounds_check = MakeBoundsCheck(loop_body, add, array_length);
341 MakeArraySet(loop_body, null_check, bounds_check, constant_10, DataType::Type::kInt32);
342
343 return bounds_check;
344 }
345
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2a)346 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2a) {
347 // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. }
348 HInstruction* bounds_check = BuildSSAGraph2(0);
349 RunBCE();
350 ASSERT_TRUE(IsRemoved(bounds_check));
351 }
352
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2b)353 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2b) {
354 // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. }
355 HInstruction* bounds_check = BuildSSAGraph2(1);
356 RunBCE();
357 ASSERT_TRUE(IsRemoved(bounds_check));
358 }
359
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2c)360 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2c) {
361 // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. }
362 HInstruction* bounds_check = BuildSSAGraph2(-1);
363 RunBCE();
364 ASSERT_FALSE(IsRemoved(bounds_check));
365 }
366
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2d)367 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2d) {
368 // for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. }
369 HInstruction* bounds_check = BuildSSAGraph2(0, -1, kCondLT);
370 RunBCE();
371 ASSERT_FALSE(IsRemoved(bounds_check));
372 }
373
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination2e)374 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2e) {
375 // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. }
376 HInstruction* bounds_check = BuildSSAGraph2(0, -2);
377 RunBCE();
378 ASSERT_TRUE(IsRemoved(bounds_check));
379 }
380
381 // int[] array = new int[10];
382 // for (int i=0; i<10; i+=increment) { array[i] = 10; }
BuildSSAGraph3(int initial,int increment,IfCondition cond)383 HInstruction* BoundsCheckEliminationTest::BuildSSAGraph3(int initial,
384 int increment,
385 IfCondition cond) {
386 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
387 auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
388
389 HInstruction* constant_10 = graph_->GetIntConstant(10);
390
391 // We pass a bogus constant for the class to avoid mocking one.
392 HInstruction* new_array =
393 MakeNewArray(pre_header, /* cls= */ constant_10, /* length= */ constant_10);
394
395 auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, initial, increment);
396 DCHECK(cond == kCondGE || cond == kCondGT) << cond;
397 HInstruction* cmp = MakeCondition(loop_header, cond, phi, constant_10);
398 MakeIf(loop_header, cmp);
399
400 HNullCheck* null_check = MakeNullCheck(loop_body, new_array);
401 HArrayLength* array_length = MakeArrayLength(loop_body, null_check);
402 HInstruction* bounds_check = MakeBoundsCheck(loop_body, phi, array_length);
403 MakeArraySet(loop_body, null_check, bounds_check, constant_10, DataType::Type::kInt32);
404
405 return bounds_check;
406 }
407
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3a)408 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) {
409 // int[] array = new int[10];
410 // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. }
411 HInstruction* bounds_check = BuildSSAGraph3(0, 1, kCondGE);
412 RunBCE();
413 ASSERT_TRUE(IsRemoved(bounds_check));
414 }
415
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3b)416 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) {
417 // int[] array = new int[10];
418 // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
419 HInstruction* bounds_check = BuildSSAGraph3(1, 1, kCondGE);
420 RunBCE();
421 ASSERT_TRUE(IsRemoved(bounds_check));
422 }
423
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3c)424 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) {
425 // int[] array = new int[10];
426 // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
427 HInstruction* bounds_check = BuildSSAGraph3(0, 1, kCondGT);
428 RunBCE();
429 ASSERT_FALSE(IsRemoved(bounds_check));
430 }
431
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination3d)432 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) {
433 // int[] array = new int[10];
434 // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
435 HInstruction* bounds_check = BuildSSAGraph3(1, 8, kCondGE);
436 RunBCE();
437 ASSERT_TRUE(IsRemoved(bounds_check));
438 }
439
440 // for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; }
BuildSSAGraph4(int initial,IfCondition cond)441 HInstruction* BoundsCheckEliminationTest::BuildSSAGraph4(int initial, IfCondition cond) {
442 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
443 auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
444
445 HInstruction* parameter = MakeParam(DataType::Type::kReference);
446 HInstruction* constant_10 = graph_->GetIntConstant(10);
447 HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
448
449 auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, initial, /*increment=*/ 1);
450 HInstruction* null_check = MakeNullCheck(loop_header, parameter);
451 HInstruction* array_length = MakeArrayLength(loop_header, null_check);
452 DCHECK(cond == kCondGE || cond == kCondGT) << cond;
453 HInstruction* cmp = MakeCondition(loop_header, cond, phi, array_length);
454 MakeIf(loop_header, cmp);
455
456 null_check = MakeNullCheck(loop_body, parameter);
457 array_length = MakeArrayLength(loop_body, null_check);
458 HInstruction* sub = MakeBinOp<HSub>(loop_body, DataType::Type::kInt32, array_length, phi);
459 HInstruction* add_minus_1 =
460 MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, sub, constant_minus_1);
461 HInstruction* bounds_check = MakeBoundsCheck(loop_body, add_minus_1, array_length);
462 MakeArraySet(loop_body, null_check, bounds_check, constant_10, DataType::Type::kInt32);
463
464 return bounds_check;
465 }
466
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4a)467 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) {
468 // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. }
469 HInstruction* bounds_check = BuildSSAGraph4(0);
470 RunBCE();
471 ASSERT_TRUE(IsRemoved(bounds_check));
472 }
473
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4b)474 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) {
475 // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
476 HInstruction* bounds_check = BuildSSAGraph4(1);
477 RunBCE();
478 ASSERT_TRUE(IsRemoved(bounds_check));
479 }
480
TEST_F(BoundsCheckEliminationTest,LoopArrayBoundsElimination4c)481 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) {
482 // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
483 HInstruction* bounds_check = BuildSSAGraph4(0, kCondGT);
484 RunBCE();
485 ASSERT_FALSE(IsRemoved(bounds_check));
486 }
487
488 // Bubble sort:
489 // (Every array access bounds-check can be eliminated.)
490 // for (int i=0; i<array.length-1; i++) {
491 // for (int j=0; j<array.length-i-1; j++) {
492 // if (array[j] > array[j+1]) {
493 // int temp = array[j+1];
494 // array[j+1] = array[j];
495 // array[j] = temp;
496 // }
497 // }
498 // }
TEST_F(BoundsCheckEliminationTest,BubbleSortArrayBoundsElimination)499 TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
500 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
501 auto [outer_pre_header, outer_header, outer_body_add] = CreateWhileLoop(return_block);
502 auto [inner_pre_header, inner_header, inner_body_add] = CreateWhileLoop(outer_body_add);
503 auto [inner_body_compare, inner_body_swap, skip_swap] = CreateDiamondPattern(inner_body_add);
504
505 HInstruction* parameter = MakeParam(DataType::Type::kReference);
506 HInstruction* constant_0 = graph_->GetIntConstant(0);
507 HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
508 HInstruction* constant_1 = graph_->GetIntConstant(1);
509
510 auto [phi_i, add_i] =
511 MakeLinearLoopVar(outer_header, outer_body_add, /*initial=*/ 0, /*increment=*/ 1);
512 HNullCheck* null_check = MakeNullCheck(outer_header, parameter);
513 HArrayLength* array_length = MakeArrayLength(outer_header, null_check);
514 HAdd* add = MakeBinOp<HAdd>(outer_header, DataType::Type::kInt32, array_length, constant_minus_1);
515 HInstruction* cmp = MakeCondition(outer_header, kCondGE, phi_i, add);
516 MakeIf(outer_header, cmp);
517
518 auto [phi_j, add_j] =
519 MakeLinearLoopVar(inner_header, inner_body_add, /*initial=*/ 0, /*increment=*/ 1);
520 null_check = MakeNullCheck(inner_header, parameter);
521 array_length = MakeArrayLength(inner_header, null_check);
522 HSub* sub = MakeBinOp<HSub>(inner_header, DataType::Type::kInt32, array_length, phi_i);
523 add = MakeBinOp<HAdd>(inner_header, DataType::Type::kInt32, sub, constant_minus_1);
524 cmp = MakeCondition(inner_header, kCondGE, phi_j, add);
525 MakeIf(inner_header, cmp);
526
527 null_check = MakeNullCheck(inner_body_compare, parameter);
528 array_length = MakeArrayLength(inner_body_compare, null_check);
529 HBoundsCheck* bounds_check1 = MakeBoundsCheck(inner_body_compare, phi_j, array_length);
530 HArrayGet* array_get_j =
531 MakeArrayGet(inner_body_compare, null_check, bounds_check1, DataType::Type::kInt32);
532 HInstruction* j_plus_1 =
533 MakeBinOp<HAdd>(inner_body_compare, DataType::Type::kInt32, phi_j, constant_1);
534 null_check = MakeNullCheck(inner_body_compare, parameter);
535 array_length = MakeArrayLength(inner_body_compare, null_check);
536 HBoundsCheck* bounds_check2 = MakeBoundsCheck(inner_body_compare, j_plus_1, array_length);
537 HArrayGet* array_get_j_plus_1 =
538 MakeArrayGet(inner_body_compare, null_check, bounds_check2, DataType::Type::kInt32);
539 cmp = MakeCondition(inner_body_compare, kCondGE, array_get_j, array_get_j_plus_1);
540 MakeIf(inner_body_compare, cmp);
541
542 j_plus_1 = MakeBinOp<HAdd>(inner_body_swap, DataType::Type::kInt32, phi_j, constant_1);
543 // temp = array[j+1]
544 null_check = MakeNullCheck(inner_body_swap, parameter);
545 array_length = MakeArrayLength(inner_body_swap, null_check);
546 HInstruction* bounds_check3 = MakeBoundsCheck(inner_body_swap, j_plus_1, array_length);
547 array_get_j_plus_1 =
548 MakeArrayGet(inner_body_swap, null_check, bounds_check3, DataType::Type::kInt32);
549 // array[j+1] = array[j]
550 null_check = MakeNullCheck(inner_body_swap, parameter);
551 array_length = MakeArrayLength(inner_body_swap, null_check);
552 HInstruction* bounds_check4 = MakeBoundsCheck(inner_body_swap, phi_j, array_length);
553 array_get_j = MakeArrayGet(inner_body_swap, null_check, bounds_check4, DataType::Type::kInt32);
554 null_check = MakeNullCheck(inner_body_swap, parameter);
555 array_length = MakeArrayLength(inner_body_swap, null_check);
556 HInstruction* bounds_check5 = MakeBoundsCheck(inner_body_swap, j_plus_1, array_length);
557 MakeArraySet(inner_body_swap, null_check, bounds_check5, array_get_j, DataType::Type::kInt32);
558 // array[j] = temp
559 null_check = MakeNullCheck(inner_body_swap, parameter);
560 array_length = MakeArrayLength(inner_body_swap, null_check);
561 HInstruction* bounds_check6 = MakeBoundsCheck(inner_body_swap, phi_j, array_length);
562 MakeArraySet(
563 inner_body_swap, null_check, bounds_check6, array_get_j_plus_1, DataType::Type::kInt32);
564
565 RunBCE(); // gvn removes same bounds check already
566
567 ASSERT_TRUE(IsRemoved(bounds_check1));
568 ASSERT_TRUE(IsRemoved(bounds_check2));
569 ASSERT_TRUE(IsRemoved(bounds_check3));
570 ASSERT_TRUE(IsRemoved(bounds_check4));
571 ASSERT_TRUE(IsRemoved(bounds_check5));
572 ASSERT_TRUE(IsRemoved(bounds_check6));
573 }
574
575 // int[] array = new int[10];
576 // for (int i=0; i<200; i++) {
577 // array[i%10] = 10; // Can eliminate
578 // array[i%1] = 10; // Can eliminate
579 // array[i%200] = 10; // Cannot eliminate
580 // array[i%-10] = 10; // Can eliminate
581 // array[i%array.length] = 10; // Can eliminate
582 // array[param_i%10] = 10; // Can't eliminate, when param_i < 0
583 // }
TEST_F(BoundsCheckEliminationTest,ModArrayBoundsElimination)584 TEST_F(BoundsCheckEliminationTest, ModArrayBoundsElimination) {
585 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
586 auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
587
588 HInstruction* param_i = MakeParam(DataType::Type::kInt32);
589 HInstruction* constant_1 = graph_->GetIntConstant(1);
590 HInstruction* constant_10 = graph_->GetIntConstant(10);
591 HInstruction* constant_200 = graph_->GetIntConstant(200);
592 HInstruction* constant_minus_10 = graph_->GetIntConstant(-10);
593
594 // We pass a bogus constant for the class to avoid mocking one.
595 HInstruction* new_array =
596 MakeNewArray(pre_header, /* cls= */ constant_10, /* length= */ constant_10);
597
598 auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, /*initial=*/ 0, /*increment=*/ 1);
599 HInstruction* cmp = MakeCondition(loop_header, kCondGE, phi, constant_200);
600 MakeIf(loop_header, cmp);
601
602 //////////////////////////////////////////////////////////////////////////////////
603 // LOOP BODY:
604 // array[i % 10] = 10;
605 HRem* i_mod_10 = MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, phi, constant_10);
606 HBoundsCheck* bounds_check_i_mod_10 = MakeBoundsCheck(loop_body, i_mod_10, constant_10);
607 MakeArraySet(loop_body, new_array, bounds_check_i_mod_10, constant_10, DataType::Type::kInt32);
608
609 // array[i % 1] = 10;
610 HRem* i_mod_1 = MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, phi, constant_1);
611 HBoundsCheck* bounds_check_i_mod_1 = MakeBoundsCheck(loop_body, i_mod_1, constant_10);
612 MakeArraySet(loop_body, new_array, bounds_check_i_mod_1, constant_10, DataType::Type::kInt32);
613
614 // array[i % 200] = 10;
615 HRem* i_mod_200 = MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, phi, constant_200);
616 HBoundsCheck* bounds_check_i_mod_200 = MakeBoundsCheck(loop_body, i_mod_200, constant_10);
617 MakeArraySet(loop_body, new_array, bounds_check_i_mod_200, constant_10, DataType::Type::kInt32);
618
619 // array[i % -10] = 10;
620 HRem* i_mod_minus_10 = MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, phi, constant_minus_10);
621 HBoundsCheck* bounds_check_i_mod_minus_10 =
622 MakeBoundsCheck(loop_body, i_mod_minus_10, constant_10);
623 MakeArraySet(
624 loop_body, new_array, bounds_check_i_mod_minus_10, constant_10, DataType::Type::kInt32);
625
626 // array[i%array.length] = 10;
627 HNullCheck* null_check = MakeNullCheck(loop_body, new_array);
628 HArrayLength* array_length = MakeArrayLength(loop_body, null_check);
629 HRem* i_mod_array_length = MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, phi, array_length);
630 HBoundsCheck* bounds_check_i_mod_array_len =
631 MakeBoundsCheck(loop_body, i_mod_array_length, array_length);
632 MakeArraySet(
633 loop_body, null_check, bounds_check_i_mod_array_len, constant_10, DataType::Type::kInt32);
634
635 // array[param_i % 10] = 10;
636 HRem* param_i_mod_10 = MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, param_i, constant_10);
637 HBoundsCheck* bounds_check_param_i_mod_10 =
638 MakeBoundsCheck(loop_body, param_i_mod_10, constant_10);
639 MakeArraySet(
640 loop_body, new_array, bounds_check_param_i_mod_10, constant_10, DataType::Type::kInt32);
641
642 // array[param_i%array.length] = 10;
643 null_check = MakeNullCheck(loop_body, new_array);
644 array_length = MakeArrayLength(loop_body, null_check);
645 HRem* param_i_mod_array_length =
646 MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, param_i, array_length);
647 HBoundsCheck* bounds_check_param_i_mod_array_len =
648 MakeBoundsCheck(loop_body, param_i_mod_array_length, array_length);
649 MakeArraySet(loop_body,
650 null_check,
651 bounds_check_param_i_mod_array_len,
652 constant_10,
653 DataType::Type::kInt32);
654
655 //////////////////////////////////////////////////////////////////////////////////
656
657 RunBCE();
658
659 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_10));
660 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_1));
661 ASSERT_FALSE(IsRemoved(bounds_check_i_mod_200));
662 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_minus_10));
663 ASSERT_TRUE(IsRemoved(bounds_check_i_mod_array_len));
664 ASSERT_FALSE(IsRemoved(bounds_check_param_i_mod_10));
665 }
666
667 } // namespace art
668