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