1 /*
2 * Copyright (C) 2019 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 <tuple>
18
19 #include "load_store_analysis.h"
20 #include "load_store_elimination.h"
21 #include "nodes.h"
22 #include "optimizing_unit_test.h"
23 #include "side_effects_analysis.h"
24
25 #include "gtest/gtest.h"
26
27 namespace art {
28
29 class LoadStoreEliminationTest : public OptimizingUnitTest {
30 public:
PerformLSE()31 void PerformLSE() {
32 graph_->BuildDominatorTree();
33 SideEffectsAnalysis side_effects(graph_);
34 side_effects.Run();
35 LoadStoreElimination lse(graph_, side_effects, /*stats=*/ nullptr);
36 lse.Run();
37 EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks());
38 }
39
40 // Create instructions shared among tests.
CreateEntryBlockInstructions()41 void CreateEntryBlockInstructions() {
42 HInstruction* c1 = graph_->GetIntConstant(1);
43 HInstruction* c4 = graph_->GetIntConstant(4);
44 i_add1_ = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_, c1);
45 i_add4_ = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_, c4);
46 entry_block_->AddInstruction(i_add1_);
47 entry_block_->AddInstruction(i_add4_);
48 entry_block_->AddInstruction(new (GetAllocator()) HGoto());
49 }
50
51 // Create the major CFG used by tests:
52 // entry
53 // |
54 // pre_header
55 // |
56 // loop[]
57 // |
58 // return
59 // |
60 // exit
CreateTestControlFlowGraph()61 void CreateTestControlFlowGraph() {
62 InitGraphAndParameters();
63 pre_header_ = AddNewBlock();
64 loop_ = AddNewBlock();
65
66 entry_block_->ReplaceSuccessor(return_block_, pre_header_);
67 pre_header_->AddSuccessor(loop_);
68 loop_->AddSuccessor(loop_);
69 loop_->AddSuccessor(return_block_);
70
71 HInstruction* c0 = graph_->GetIntConstant(0);
72 HInstruction* c1 = graph_->GetIntConstant(1);
73 HInstruction* c128 = graph_->GetIntConstant(128);
74
75 CreateEntryBlockInstructions();
76
77 // pre_header block
78 // phi = 0;
79 phi_ = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
80 loop_->AddPhi(phi_);
81 pre_header_->AddInstruction(new (GetAllocator()) HGoto());
82 phi_->AddInput(c0);
83
84 // loop block:
85 // suspend_check
86 // phi++;
87 // if (phi >= 128)
88 suspend_check_ = new (GetAllocator()) HSuspendCheck();
89 HInstruction* inc_phi = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_, c1);
90 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(phi_, c128);
91 HInstruction* hif = new (GetAllocator()) HIf(cmp);
92 loop_->AddInstruction(suspend_check_);
93 loop_->AddInstruction(inc_phi);
94 loop_->AddInstruction(cmp);
95 loop_->AddInstruction(hif);
96 phi_->AddInput(inc_phi);
97
98 CreateEnvForSuspendCheck();
99 }
100
CreateEnvForSuspendCheck()101 void CreateEnvForSuspendCheck() {
102 ArenaVector<HInstruction*> current_locals({array_, i_, j_},
103 GetAllocator()->Adapter(kArenaAllocInstruction));
104 ManuallyBuildEnvFor(suspend_check_, ¤t_locals);
105 }
106
107 // Create the diamond-shaped CFG:
108 // upper
109 // / \
110 // left right
111 // \ /
112 // down
113 //
114 // Return: the basic blocks forming the CFG in the following order {upper, left, right, down}.
CreateDiamondShapedCFG()115 std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateDiamondShapedCFG() {
116 InitGraphAndParameters();
117 CreateEntryBlockInstructions();
118
119 HBasicBlock* upper = AddNewBlock();
120 HBasicBlock* left = AddNewBlock();
121 HBasicBlock* right = AddNewBlock();
122
123 entry_block_->ReplaceSuccessor(return_block_, upper);
124 upper->AddSuccessor(left);
125 upper->AddSuccessor(right);
126 left->AddSuccessor(return_block_);
127 right->AddSuccessor(return_block_);
128
129 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(i_, j_);
130 HInstruction* hif = new (GetAllocator()) HIf(cmp);
131 upper->AddInstruction(cmp);
132 upper->AddInstruction(hif);
133
134 left->AddInstruction(new (GetAllocator()) HGoto());
135 right->AddInstruction(new (GetAllocator()) HGoto());
136
137 return std::make_tuple(upper, left, right, return_block_);
138 }
139
140 // Add a HVecLoad instruction to the end of the provided basic block.
141 //
142 // Return: the created HVecLoad instruction.
AddVecLoad(HBasicBlock * block,HInstruction * array,HInstruction * index)143 HInstruction* AddVecLoad(HBasicBlock* block, HInstruction* array, HInstruction* index) {
144 DCHECK(block != nullptr);
145 DCHECK(array != nullptr);
146 DCHECK(index != nullptr);
147 HInstruction* vload = new (GetAllocator()) HVecLoad(
148 GetAllocator(),
149 array,
150 index,
151 DataType::Type::kInt32,
152 SideEffects::ArrayReadOfType(DataType::Type::kInt32),
153 4,
154 /*is_string_char_at*/ false,
155 kNoDexPc);
156 block->InsertInstructionBefore(vload, block->GetLastInstruction());
157 return vload;
158 }
159
160 // Add a HVecStore instruction to the end of the provided basic block.
161 // If no vdata is specified, generate HVecStore: array[index] = [1,1,1,1].
162 //
163 // Return: the created HVecStore instruction.
AddVecStore(HBasicBlock * block,HInstruction * array,HInstruction * index,HInstruction * vdata=nullptr)164 HInstruction* AddVecStore(HBasicBlock* block,
165 HInstruction* array,
166 HInstruction* index,
167 HInstruction* vdata = nullptr) {
168 DCHECK(block != nullptr);
169 DCHECK(array != nullptr);
170 DCHECK(index != nullptr);
171 if (vdata == nullptr) {
172 HInstruction* c1 = graph_->GetIntConstant(1);
173 vdata = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
174 c1,
175 DataType::Type::kInt32,
176 4,
177 kNoDexPc);
178 block->InsertInstructionBefore(vdata, block->GetLastInstruction());
179 }
180 HInstruction* vstore = new (GetAllocator()) HVecStore(
181 GetAllocator(),
182 array,
183 index,
184 vdata,
185 DataType::Type::kInt32,
186 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
187 4,
188 kNoDexPc);
189 block->InsertInstructionBefore(vstore, block->GetLastInstruction());
190 return vstore;
191 }
192
193 // Add a HArrayGet instruction to the end of the provided basic block.
194 //
195 // Return: the created HArrayGet instruction.
AddArrayGet(HBasicBlock * block,HInstruction * array,HInstruction * index)196 HInstruction* AddArrayGet(HBasicBlock* block, HInstruction* array, HInstruction* index) {
197 DCHECK(block != nullptr);
198 DCHECK(array != nullptr);
199 DCHECK(index != nullptr);
200 HInstruction* get = new (GetAllocator()) HArrayGet(array, index, DataType::Type::kInt32, 0);
201 block->InsertInstructionBefore(get, block->GetLastInstruction());
202 return get;
203 }
204
205 // Add a HArraySet instruction to the end of the provided basic block.
206 // If no data is specified, generate HArraySet: array[index] = 1.
207 //
208 // Return: the created HArraySet instruction.
AddArraySet(HBasicBlock * block,HInstruction * array,HInstruction * index,HInstruction * data=nullptr)209 HInstruction* AddArraySet(HBasicBlock* block,
210 HInstruction* array,
211 HInstruction* index,
212 HInstruction* data = nullptr) {
213 DCHECK(block != nullptr);
214 DCHECK(array != nullptr);
215 DCHECK(index != nullptr);
216 if (data == nullptr) {
217 data = graph_->GetIntConstant(1);
218 }
219 HInstruction* store = new (GetAllocator()) HArraySet(array,
220 index,
221 data,
222 DataType::Type::kInt32,
223 0);
224 block->InsertInstructionBefore(store, block->GetLastInstruction());
225 return store;
226 }
227
InitGraphAndParameters()228 void InitGraphAndParameters() {
229 InitGraph();
230 AddParameter(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
231 dex::TypeIndex(0),
232 0,
233 DataType::Type::kInt32));
234 array_ = parameters_.back();
235 AddParameter(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
236 dex::TypeIndex(1),
237 1,
238 DataType::Type::kInt32));
239 i_ = parameters_.back();
240 AddParameter(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
241 dex::TypeIndex(1),
242 2,
243 DataType::Type::kInt32));
244 j_ = parameters_.back();
245 }
246
247 HBasicBlock* pre_header_;
248 HBasicBlock* loop_;
249
250 HInstruction* array_;
251 HInstruction* i_;
252 HInstruction* j_;
253 HInstruction* i_add1_;
254 HInstruction* i_add4_;
255 HInstruction* suspend_check_;
256
257 HPhi* phi_;
258 };
259
TEST_F(LoadStoreEliminationTest,ArrayGetSetElimination)260 TEST_F(LoadStoreEliminationTest, ArrayGetSetElimination) {
261 CreateTestControlFlowGraph();
262
263 HInstruction* c1 = graph_->GetIntConstant(1);
264 HInstruction* c2 = graph_->GetIntConstant(2);
265 HInstruction* c3 = graph_->GetIntConstant(3);
266
267 // array[1] = 1;
268 // x = array[1]; <--- Remove.
269 // y = array[2];
270 // array[1] = 1; <--- Remove, since it stores same value.
271 // array[i] = 3; <--- MAY alias.
272 // array[1] = 1; <--- Cannot remove, even if it stores the same value.
273 AddArraySet(entry_block_, array_, c1, c1);
274 HInstruction* load1 = AddArrayGet(entry_block_, array_, c1);
275 HInstruction* load2 = AddArrayGet(entry_block_, array_, c2);
276 HInstruction* store1 = AddArraySet(entry_block_, array_, c1, c1);
277 AddArraySet(entry_block_, array_, i_, c3);
278 HInstruction* store2 = AddArraySet(entry_block_, array_, c1, c1);
279
280 PerformLSE();
281
282 ASSERT_TRUE(IsRemoved(load1));
283 ASSERT_FALSE(IsRemoved(load2));
284 ASSERT_TRUE(IsRemoved(store1));
285 ASSERT_FALSE(IsRemoved(store2));
286 }
287
TEST_F(LoadStoreEliminationTest,SameHeapValue1)288 TEST_F(LoadStoreEliminationTest, SameHeapValue1) {
289 CreateTestControlFlowGraph();
290
291 HInstruction* c1 = graph_->GetIntConstant(1);
292 HInstruction* c2 = graph_->GetIntConstant(2);
293
294 // Test LSE handling same value stores on array.
295 // array[1] = 1;
296 // array[2] = 1;
297 // array[1] = 1; <--- Can remove.
298 // array[1] = 2; <--- Can NOT remove.
299 AddArraySet(entry_block_, array_, c1, c1);
300 AddArraySet(entry_block_, array_, c2, c1);
301 HInstruction* store1 = AddArraySet(entry_block_, array_, c1, c1);
302 HInstruction* store2 = AddArraySet(entry_block_, array_, c1, c2);
303
304 PerformLSE();
305
306 ASSERT_TRUE(IsRemoved(store1));
307 ASSERT_FALSE(IsRemoved(store2));
308 }
309
TEST_F(LoadStoreEliminationTest,SameHeapValue2)310 TEST_F(LoadStoreEliminationTest, SameHeapValue2) {
311 CreateTestControlFlowGraph();
312
313 // Test LSE handling same value stores on vector.
314 // vdata = [0x1, 0x2, 0x3, 0x4, ...]
315 // VecStore array[i...] = vdata;
316 // VecStore array[j...] = vdata; <--- MAY ALIAS.
317 // VecStore array[i...] = vdata; <--- Cannot Remove, even if it's same value.
318 AddVecStore(entry_block_, array_, i_);
319 AddVecStore(entry_block_, array_, j_);
320 HInstruction* vstore = AddVecStore(entry_block_, array_, i_);
321
322 PerformLSE();
323
324 ASSERT_FALSE(IsRemoved(vstore));
325 }
326
TEST_F(LoadStoreEliminationTest,SameHeapValue3)327 TEST_F(LoadStoreEliminationTest, SameHeapValue3) {
328 CreateTestControlFlowGraph();
329
330 // VecStore array[i...] = vdata;
331 // VecStore array[i+1...] = vdata; <--- MAY alias due to partial overlap.
332 // VecStore array[i...] = vdata; <--- Cannot remove, even if it's same value.
333 AddVecStore(entry_block_, array_, i_);
334 AddVecStore(entry_block_, array_, i_add1_);
335 HInstruction* vstore = AddVecStore(entry_block_, array_, i_);
336
337 PerformLSE();
338
339 ASSERT_FALSE(IsRemoved(vstore));
340 }
341
TEST_F(LoadStoreEliminationTest,OverlappingLoadStore)342 TEST_F(LoadStoreEliminationTest, OverlappingLoadStore) {
343 CreateTestControlFlowGraph();
344
345 HInstruction* c1 = graph_->GetIntConstant(1);
346
347 // Test LSE handling array LSE when there is vector store in between.
348 // a[i] = 1;
349 // .. = a[i]; <-- Remove.
350 // a[i,i+1,i+2,i+3] = data; <-- PARTIAL OVERLAP !
351 // .. = a[i]; <-- Cannot remove.
352 AddArraySet(entry_block_, array_, i_, c1);
353 HInstruction* load1 = AddArrayGet(entry_block_, array_, i_);
354 AddVecStore(entry_block_, array_, i_);
355 HInstruction* load2 = AddArrayGet(entry_block_, array_, i_);
356
357 // Test LSE handling vector load/store partial overlap.
358 // a[i,i+1,i+2,i+3] = data;
359 // a[i+4,i+5,i+6,i+7] = data;
360 // .. = a[i,i+1,i+2,i+3];
361 // .. = a[i+4,i+5,i+6,i+7];
362 // a[i+1,i+2,i+3,i+4] = data; <-- PARTIAL OVERLAP !
363 // .. = a[i,i+1,i+2,i+3];
364 // .. = a[i+4,i+5,i+6,i+7];
365 AddVecStore(entry_block_, array_, i_);
366 AddVecStore(entry_block_, array_, i_add4_);
367 HInstruction* vload1 = AddVecLoad(entry_block_, array_, i_);
368 HInstruction* vload2 = AddVecLoad(entry_block_, array_, i_add4_);
369 AddVecStore(entry_block_, array_, i_add1_);
370 HInstruction* vload3 = AddVecLoad(entry_block_, array_, i_);
371 HInstruction* vload4 = AddVecLoad(entry_block_, array_, i_add4_);
372
373 // Test LSE handling vector LSE when there is array store in between.
374 // a[i,i+1,i+2,i+3] = data;
375 // a[i+1] = 1; <-- PARTIAL OVERLAP !
376 // .. = a[i,i+1,i+2,i+3];
377 AddVecStore(entry_block_, array_, i_);
378 AddArraySet(entry_block_, array_, i_, c1);
379 HInstruction* vload5 = AddVecLoad(entry_block_, array_, i_);
380
381 PerformLSE();
382
383 ASSERT_TRUE(IsRemoved(load1));
384 ASSERT_FALSE(IsRemoved(load2));
385
386 ASSERT_TRUE(IsRemoved(vload1));
387 ASSERT_TRUE(IsRemoved(vload2));
388 ASSERT_FALSE(IsRemoved(vload3));
389 ASSERT_FALSE(IsRemoved(vload4));
390
391 ASSERT_FALSE(IsRemoved(vload5));
392 }
393 // function (int[] a, int j) {
394 // a[j] = 1;
395 // for (int i=0; i<128; i++) {
396 // /* doesn't do any write */
397 // }
398 // a[j] = 1;
TEST_F(LoadStoreEliminationTest,StoreAfterLoopWithoutSideEffects)399 TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithoutSideEffects) {
400 CreateTestControlFlowGraph();
401
402 HInstruction* c1 = graph_->GetIntConstant(1);
403
404 // a[j] = 1
405 AddArraySet(pre_header_, array_, j_, c1);
406
407 // LOOP BODY:
408 // .. = a[i,i+1,i+2,i+3];
409 AddVecLoad(loop_, array_, phi_);
410
411 // a[j] = 1;
412 HInstruction* array_set = AddArraySet(return_block_, array_, j_, c1);
413
414 PerformLSE();
415
416 ASSERT_TRUE(IsRemoved(array_set));
417 }
418
419 // function (int[] a, int j) {
420 // int[] b = new int[128];
421 // a[j] = 0;
422 // for (int phi=0; phi<128; phi++) {
423 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
424 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
425 // }
426 // a[j] = 0;
427 // }
TEST_F(LoadStoreEliminationTest,StoreAfterSIMDLoopWithSideEffects)428 TEST_F(LoadStoreEliminationTest, StoreAfterSIMDLoopWithSideEffects) {
429 CreateTestControlFlowGraph();
430
431 HInstruction* c0 = graph_->GetIntConstant(0);
432 HInstruction* c128 = graph_->GetIntConstant(128);
433
434 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
435 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
436 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
437
438 // a[j] = 0;
439 AddArraySet(pre_header_, array_, j_, c0);
440
441 // LOOP BODY:
442 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
443 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
444 AddVecStore(loop_, array_, phi_);
445 HInstruction* vload = AddVecLoad(loop_, array_, phi_);
446 AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
447
448 // a[j] = 0;
449 HInstruction* a_set = AddArraySet(return_block_, array_, j_, c0);
450
451 PerformLSE();
452
453 ASSERT_TRUE(IsRemoved(vload));
454 ASSERT_FALSE(IsRemoved(a_set)); // Cannot remove due to write side-effect in the loop.
455 }
456
457 // function (int[] a, int j) {
458 // int[] b = new int[128];
459 // a[j] = 0;
460 // for (int phi=0; phi<128; phi++) {
461 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
462 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
463 // }
464 // x = a[j];
465 // }
TEST_F(LoadStoreEliminationTest,LoadAfterSIMDLoopWithSideEffects)466 TEST_F(LoadStoreEliminationTest, LoadAfterSIMDLoopWithSideEffects) {
467 CreateTestControlFlowGraph();
468
469 HInstruction* c0 = graph_->GetIntConstant(0);
470 HInstruction* c128 = graph_->GetIntConstant(128);
471
472 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
473 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
474 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
475
476 // a[j] = 0;
477 AddArraySet(pre_header_, array_, j_, c0);
478
479 // LOOP BODY:
480 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
481 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
482 AddVecStore(loop_, array_, phi_);
483 HInstruction* vload = AddVecLoad(loop_, array_, phi_);
484 AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
485
486 // x = a[j];
487 HInstruction* load = AddArrayGet(return_block_, array_, j_);
488
489 PerformLSE();
490
491 ASSERT_TRUE(IsRemoved(vload));
492 ASSERT_FALSE(IsRemoved(load)); // Cannot remove due to write side-effect in the loop.
493 }
494
495 // Check that merging works correctly when there are VecStors in predecessors.
496 //
497 // vstore1: a[i,... i + 3] = [1,...1]
498 // / \
499 // / \
500 // vstore2: a[i,... i + 3] = [1,...1] vstore3: a[i+1, ... i + 4] = [1, ... 1]
501 // \ /
502 // \ /
503 // vstore4: a[i,... i + 3] = [1,...1]
504 //
505 // Expected:
506 // 'vstore2' is removed.
507 // 'vstore3' is not removed.
508 // 'vstore4' is not removed. Such cases are not supported at the moment.
TEST_F(LoadStoreEliminationTest,MergePredecessorVecStores)509 TEST_F(LoadStoreEliminationTest, MergePredecessorVecStores) {
510 HBasicBlock* upper;
511 HBasicBlock* left;
512 HBasicBlock* right;
513 HBasicBlock* down;
514 std::tie(upper, left, right, down) = CreateDiamondShapedCFG();
515
516 // upper: a[i,... i + 3] = [1,...1]
517 HInstruction* vstore1 = AddVecStore(upper, array_, i_);
518 HInstruction* vdata = vstore1->InputAt(2);
519
520 // left: a[i,... i + 3] = [1,...1]
521 HInstruction* vstore2 = AddVecStore(left, array_, i_, vdata);
522
523 // right: a[i+1, ... i + 4] = [1, ... 1]
524 HInstruction* vstore3 = AddVecStore(right, array_, i_add1_, vdata);
525
526 // down: a[i,... i + 3] = [1,...1]
527 HInstruction* vstore4 = AddVecStore(down, array_, i_, vdata);
528
529 PerformLSE();
530
531 ASSERT_TRUE(IsRemoved(vstore2));
532 ASSERT_FALSE(IsRemoved(vstore3));
533 ASSERT_FALSE(IsRemoved(vstore4));
534 }
535
536 // Check that merging works correctly when there are ArraySets in predecessors.
537 //
538 // a[i] = 1
539 // / \
540 // / \
541 // store1: a[i] = 1 store2: a[i+1] = 1
542 // \ /
543 // \ /
544 // store3: a[i] = 1
545 //
546 // Expected:
547 // 'store1' is removed.
548 // 'store2' is not removed.
549 // 'store3' is removed.
TEST_F(LoadStoreEliminationTest,MergePredecessorStores)550 TEST_F(LoadStoreEliminationTest, MergePredecessorStores) {
551 HBasicBlock* upper;
552 HBasicBlock* left;
553 HBasicBlock* right;
554 HBasicBlock* down;
555 std::tie(upper, left, right, down) = CreateDiamondShapedCFG();
556
557 // upper: a[i,... i + 3] = [1,...1]
558 AddArraySet(upper, array_, i_);
559
560 // left: a[i,... i + 3] = [1,...1]
561 HInstruction* store1 = AddArraySet(left, array_, i_);
562
563 // right: a[i+1, ... i + 4] = [1, ... 1]
564 HInstruction* store2 = AddArraySet(right, array_, i_add1_);
565
566 // down: a[i,... i + 3] = [1,...1]
567 HInstruction* store3 = AddArraySet(down, array_, i_);
568
569 PerformLSE();
570
571 ASSERT_TRUE(IsRemoved(store1));
572 ASSERT_FALSE(IsRemoved(store2));
573 ASSERT_TRUE(IsRemoved(store3));
574 }
575
576 // Check that redundant VStore/VLoad are removed from a SIMD loop.
577 //
578 // LOOP BODY
579 // vstore1: a[i,... i + 3] = [1,...1]
580 // vload: x = a[i,... i + 3]
581 // vstore2: b[i,... i + 3] = x
582 // vstore3: a[i,... i + 3] = [1,...1]
583 //
584 // Expected:
585 // 'vstore1' is not removed.
586 // 'vload' is removed.
587 // 'vstore3' is removed.
TEST_F(LoadStoreEliminationTest,RedundantVStoreVLoadInLoop)588 TEST_F(LoadStoreEliminationTest, RedundantVStoreVLoadInLoop) {
589 CreateTestControlFlowGraph();
590
591 HInstruction* c0 = graph_->GetIntConstant(0);
592 HInstruction* c128 = graph_->GetIntConstant(128);
593
594 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
595 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
596 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
597
598 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
599 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
600 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
601
602 // LOOP BODY:
603 // a[i,... i + 3] = [1,...1]
604 // x = a[i,... i + 3]
605 // b[i,... i + 3] = x
606 // a[i,... i + 3] = [1,...1]
607 HInstruction* vstore1 = AddVecStore(loop_, array_a, phi_);
608 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
609 AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
610 HInstruction* vstore3 = AddVecStore(loop_, array_a, phi_, vstore1->InputAt(2));
611
612 PerformLSE();
613
614 ASSERT_FALSE(IsRemoved(vstore1));
615 ASSERT_TRUE(IsRemoved(vload));
616 ASSERT_TRUE(IsRemoved(vstore3));
617 }
618
619 // Loop write side effects invalidate all stores.
620 // This causes stores after such loops not to be removed, even
621 // their values are known.
TEST_F(LoadStoreEliminationTest,StoreAfterLoopWithSideEffects)622 TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithSideEffects) {
623 CreateTestControlFlowGraph();
624
625 HInstruction* c0 = graph_->GetIntConstant(0);
626 HInstruction* c2 = graph_->GetIntConstant(2);
627 HInstruction* c128 = graph_->GetIntConstant(128);
628
629 // array[0] = 2;
630 // loop:
631 // b[i] = array[i]
632 // array[0] = 2
633 AddArraySet(entry_block_, array_, c0, c2);
634
635 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
636 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
637 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
638
639 HInstruction* load = AddArrayGet(loop_, array_, phi_);
640 AddArraySet(loop_, array_b, phi_, load);
641
642 HInstruction* store = AddArraySet(return_block_, array_, c0, c2);
643
644 PerformLSE();
645
646 ASSERT_FALSE(IsRemoved(store));
647 }
648
649 // As it is not allowed to use defaults for VecLoads, check if there is a new created array
650 // a VecLoad used in a loop and after it is not replaced with a default.
TEST_F(LoadStoreEliminationTest,VLoadDefaultValueInLoopWithoutWriteSideEffects)651 TEST_F(LoadStoreEliminationTest, VLoadDefaultValueInLoopWithoutWriteSideEffects) {
652 CreateTestControlFlowGraph();
653
654 HInstruction* c0 = graph_->GetIntConstant(0);
655 HInstruction* c128 = graph_->GetIntConstant(128);
656
657 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
658 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
659 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
660
661 // LOOP BODY:
662 // v = a[i,... i + 3]
663 // array[0,... 3] = v
664 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
665 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
666
667 PerformLSE();
668
669 ASSERT_FALSE(IsRemoved(vload));
670 ASSERT_FALSE(IsRemoved(vstore));
671 }
672
673 // As it is not allowed to use defaults for VecLoads, check if there is a new created array
674 // a VecLoad is not replaced with a default.
TEST_F(LoadStoreEliminationTest,VLoadDefaultValue)675 TEST_F(LoadStoreEliminationTest, VLoadDefaultValue) {
676 CreateTestControlFlowGraph();
677
678 HInstruction* c0 = graph_->GetIntConstant(0);
679 HInstruction* c128 = graph_->GetIntConstant(128);
680
681 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
682 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
683 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
684
685 // v = a[0,... 3]
686 // array[0,... 3] = v
687 HInstruction* vload = AddVecLoad(pre_header_, array_a, c0);
688 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
689
690 PerformLSE();
691
692 ASSERT_FALSE(IsRemoved(vload));
693 ASSERT_FALSE(IsRemoved(vstore));
694 }
695
696 // As it is allowed to use defaults for ordinary loads, check if there is a new created array
697 // a load used in a loop and after it is replaced with a default.
TEST_F(LoadStoreEliminationTest,LoadDefaultValueInLoopWithoutWriteSideEffects)698 TEST_F(LoadStoreEliminationTest, LoadDefaultValueInLoopWithoutWriteSideEffects) {
699 CreateTestControlFlowGraph();
700
701 HInstruction* c0 = graph_->GetIntConstant(0);
702 HInstruction* c128 = graph_->GetIntConstant(128);
703
704 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
705 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
706 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
707
708 // LOOP BODY:
709 // v = a[i]
710 // array[0] = v
711 HInstruction* load = AddArrayGet(loop_, array_a, phi_);
712 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
713
714 PerformLSE();
715
716 ASSERT_TRUE(IsRemoved(load));
717 ASSERT_FALSE(IsRemoved(store));
718 }
719
720 // As it is allowed to use defaults for ordinary loads, check if there is a new created array
721 // a load is replaced with a default.
TEST_F(LoadStoreEliminationTest,LoadDefaultValue)722 TEST_F(LoadStoreEliminationTest, LoadDefaultValue) {
723 CreateTestControlFlowGraph();
724
725 HInstruction* c0 = graph_->GetIntConstant(0);
726 HInstruction* c128 = graph_->GetIntConstant(128);
727
728 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
729 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
730 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
731
732 // v = a[0]
733 // array[0] = v
734 HInstruction* load = AddArrayGet(pre_header_, array_a, c0);
735 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
736
737 PerformLSE();
738
739 ASSERT_TRUE(IsRemoved(load));
740 ASSERT_FALSE(IsRemoved(store));
741 }
742
743 // As it is not allowed to use defaults for VecLoads but allowed for regular loads,
744 // check if there is a new created array, a VecLoad and a load used in a loop and after it,
745 // VecLoad is not replaced with a default but the load is.
TEST_F(LoadStoreEliminationTest,VLoadAndLoadDefaultValueInLoopWithoutWriteSideEffects)746 TEST_F(LoadStoreEliminationTest, VLoadAndLoadDefaultValueInLoopWithoutWriteSideEffects) {
747 CreateTestControlFlowGraph();
748
749 HInstruction* c0 = graph_->GetIntConstant(0);
750 HInstruction* c128 = graph_->GetIntConstant(128);
751
752 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
753 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
754 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
755
756 // LOOP BODY:
757 // v = a[i,... i + 3]
758 // v1 = a[i]
759 // array[0,... 3] = v
760 // array[0] = v1
761 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
762 HInstruction* load = AddArrayGet(loop_, array_a, phi_);
763 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
764 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
765
766 PerformLSE();
767
768 ASSERT_FALSE(IsRemoved(vload));
769 ASSERT_TRUE(IsRemoved(load));
770 ASSERT_FALSE(IsRemoved(vstore));
771 ASSERT_FALSE(IsRemoved(store));
772 }
773
774 // As it is not allowed to use defaults for VecLoads but allowed for regular loads,
775 // check if there is a new created array, a VecLoad and a load,
776 // VecLoad is not replaced with a default but the load is.
TEST_F(LoadStoreEliminationTest,VLoadAndLoadDefaultValue)777 TEST_F(LoadStoreEliminationTest, VLoadAndLoadDefaultValue) {
778 CreateTestControlFlowGraph();
779
780 HInstruction* c0 = graph_->GetIntConstant(0);
781 HInstruction* c128 = graph_->GetIntConstant(128);
782
783 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
784 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
785 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
786
787 // v = a[0,... 3]
788 // v1 = a[0]
789 // array[0,... 3] = v
790 // array[0] = v1
791 HInstruction* vload = AddVecLoad(pre_header_, array_a, c0);
792 HInstruction* load = AddArrayGet(pre_header_, array_a, c0);
793 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
794 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
795
796 PerformLSE();
797
798 ASSERT_FALSE(IsRemoved(vload));
799 ASSERT_TRUE(IsRemoved(load));
800 ASSERT_FALSE(IsRemoved(vstore));
801 ASSERT_FALSE(IsRemoved(store));
802 }
803
804 // It is not allowed to use defaults for VecLoads. However it should not prevent from removing
805 // loads getting the same value.
806 // Check a load getting a known value is eliminated (a loop test case).
TEST_F(LoadStoreEliminationTest,VLoadDefaultValueAndVLoadInLoopWithoutWriteSideEffects)807 TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoadInLoopWithoutWriteSideEffects) {
808 CreateTestControlFlowGraph();
809
810 HInstruction* c0 = graph_->GetIntConstant(0);
811 HInstruction* c128 = graph_->GetIntConstant(128);
812
813 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
814 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
815 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
816
817 // LOOP BODY:
818 // v = a[i,... i + 3]
819 // v1 = a[i,... i + 3]
820 // array[0,... 3] = v
821 // array[128,... 131] = v1
822 HInstruction* vload1 = AddVecLoad(loop_, array_a, phi_);
823 HInstruction* vload2 = AddVecLoad(loop_, array_a, phi_);
824 HInstruction* vstore1 = AddVecStore(return_block_, array_, c0, vload1->AsVecLoad());
825 HInstruction* vstore2 = AddVecStore(return_block_, array_, c128, vload2->AsVecLoad());
826
827 PerformLSE();
828
829 ASSERT_FALSE(IsRemoved(vload1));
830 ASSERT_TRUE(IsRemoved(vload2));
831 ASSERT_FALSE(IsRemoved(vstore1));
832 ASSERT_FALSE(IsRemoved(vstore2));
833 }
834
835 // It is not allowed to use defaults for VecLoads. However it should not prevent from removing
836 // loads getting the same value.
837 // Check a load getting a known value is eliminated.
TEST_F(LoadStoreEliminationTest,VLoadDefaultValueAndVLoad)838 TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoad) {
839 CreateTestControlFlowGraph();
840
841 HInstruction* c0 = graph_->GetIntConstant(0);
842 HInstruction* c128 = graph_->GetIntConstant(128);
843
844 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
845 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
846 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
847
848 // v = a[0,... 3]
849 // v1 = a[0,... 3]
850 // array[0,... 3] = v
851 // array[128,... 131] = v1
852 HInstruction* vload1 = AddVecLoad(pre_header_, array_a, c0);
853 HInstruction* vload2 = AddVecLoad(pre_header_, array_a, c0);
854 HInstruction* vstore1 = AddVecStore(return_block_, array_, c0, vload1->AsVecLoad());
855 HInstruction* vstore2 = AddVecStore(return_block_, array_, c128, vload2->AsVecLoad());
856
857 PerformLSE();
858
859 ASSERT_FALSE(IsRemoved(vload1));
860 ASSERT_TRUE(IsRemoved(vload2));
861 ASSERT_FALSE(IsRemoved(vstore1));
862 ASSERT_FALSE(IsRemoved(vstore2));
863 }
864
865 } // namespace art
866