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 "load_store_elimination.h"
18
19 #include <initializer_list>
20 #include <memory>
21 #include <tuple>
22 #include <variant>
23
24 #include "base/iteration_range.h"
25 #include "compilation_kind.h"
26 #include "dex/dex_file_types.h"
27 #include "entrypoints/quick/quick_entrypoints.h"
28 #include "entrypoints/quick/quick_entrypoints_enum.h"
29 #include "gtest/gtest.h"
30 #include "handle_scope.h"
31 #include "load_store_analysis.h"
32 #include "nodes.h"
33 #include "optimizing/data_type.h"
34 #include "optimizing/instruction_simplifier.h"
35 #include "optimizing/optimizing_compiler_stats.h"
36 #include "optimizing_unit_test.h"
37 #include "scoped_thread_state_change.h"
38
39 namespace art HIDDEN {
40
41 static constexpr bool kDebugLseTests = false;
42
43 #define CHECK_SUBROUTINE_FAILURE() \
44 do { \
45 if (HasFatalFailure()) { \
46 return; \
47 } \
48 } while (false)
49
50 template <typename SuperTest>
51 class LoadStoreEliminationTestBase : public SuperTest, public OptimizingUnitTestHelper {
52 public:
LoadStoreEliminationTestBase()53 LoadStoreEliminationTestBase() {
54 this->use_boot_image_ = true; // Make the Runtime creation cheaper.
55 }
56
SetUp()57 void SetUp() override {
58 SuperTest::SetUp();
59 if (kDebugLseTests) {
60 gLogVerbosity.compiler = true;
61 }
62 }
63
TearDown()64 void TearDown() override {
65 SuperTest::TearDown();
66 if (kDebugLseTests) {
67 gLogVerbosity.compiler = false;
68 }
69 }
70
PerformLSE()71 void PerformLSE() {
72 graph_->BuildDominatorTree();
73 LoadStoreElimination lse(graph_, /*stats=*/nullptr);
74 lse.Run();
75 std::ostringstream oss;
76 EXPECT_TRUE(CheckGraph(oss)) << oss.str();
77 }
78
PerformLSE(const AdjacencyListGraph & blks)79 void PerformLSE(const AdjacencyListGraph& blks) {
80 // PerformLSE expects this to be empty, and the creation of
81 // an `AdjacencyListGraph` computes it.
82 graph_->ClearDominanceInformation();
83 if (kDebugLseTests) {
84 LOG(INFO) << "Pre LSE " << blks;
85 }
86 PerformLSE();
87 if (kDebugLseTests) {
88 LOG(INFO) << "Post LSE " << blks;
89 }
90 }
91
92 // Create instructions shared among tests.
CreateEntryBlockInstructions()93 void CreateEntryBlockInstructions() {
94 HInstruction* c1 = graph_->GetIntConstant(1);
95 HInstruction* c4 = graph_->GetIntConstant(4);
96 i_add1_ = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_, c1);
97 i_add4_ = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_, c4);
98 entry_block_->AddInstruction(i_add1_);
99 entry_block_->AddInstruction(i_add4_);
100 entry_block_->AddInstruction(new (GetAllocator()) HGoto());
101 }
102
103 // Create the major CFG used by tests:
104 // entry
105 // |
106 // pre_header
107 // |
108 // loop[]
109 // |
110 // return
111 // |
112 // exit
CreateTestControlFlowGraph()113 void CreateTestControlFlowGraph() {
114 InitGraphAndParameters();
115 pre_header_ = AddNewBlock();
116 loop_ = AddNewBlock();
117
118 entry_block_->ReplaceSuccessor(return_block_, pre_header_);
119 pre_header_->AddSuccessor(loop_);
120 loop_->AddSuccessor(loop_);
121 loop_->AddSuccessor(return_block_);
122
123 HInstruction* c0 = graph_->GetIntConstant(0);
124 HInstruction* c1 = graph_->GetIntConstant(1);
125 HInstruction* c128 = graph_->GetIntConstant(128);
126
127 CreateEntryBlockInstructions();
128
129 // pre_header block
130 // phi = 0;
131 phi_ = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
132 loop_->AddPhi(phi_);
133 pre_header_->AddInstruction(new (GetAllocator()) HGoto());
134 phi_->AddInput(c0);
135
136 // loop block:
137 // suspend_check
138 // phi++;
139 // if (phi >= 128)
140 suspend_check_ = new (GetAllocator()) HSuspendCheck();
141 HInstruction* inc_phi = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_, c1);
142 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(phi_, c128);
143 HInstruction* hif = new (GetAllocator()) HIf(cmp);
144 loop_->AddInstruction(suspend_check_);
145 loop_->AddInstruction(inc_phi);
146 loop_->AddInstruction(cmp);
147 loop_->AddInstruction(hif);
148 phi_->AddInput(inc_phi);
149
150 CreateEnvForSuspendCheck();
151 }
152
CreateEnvForSuspendCheck()153 void CreateEnvForSuspendCheck() {
154 ManuallyBuildEnvFor(suspend_check_, {array_, i_, j_});
155 }
156
157 // Create the diamond-shaped CFG:
158 // upper
159 // / \
160 // left right
161 // \ /
162 // down
163 //
164 // Return: the basic blocks forming the CFG in the following order {upper, left, right, down}.
CreateDiamondShapedCFG()165 std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateDiamondShapedCFG() {
166 InitGraphAndParameters();
167 CreateEntryBlockInstructions();
168
169 HBasicBlock* upper = AddNewBlock();
170 HBasicBlock* left = AddNewBlock();
171 HBasicBlock* right = AddNewBlock();
172
173 entry_block_->ReplaceSuccessor(return_block_, upper);
174 upper->AddSuccessor(left);
175 upper->AddSuccessor(right);
176 left->AddSuccessor(return_block_);
177 right->AddSuccessor(return_block_);
178
179 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(i_, j_);
180 HInstruction* hif = new (GetAllocator()) HIf(cmp);
181 upper->AddInstruction(cmp);
182 upper->AddInstruction(hif);
183
184 left->AddInstruction(new (GetAllocator()) HGoto());
185 right->AddInstruction(new (GetAllocator()) HGoto());
186
187 return std::make_tuple(upper, left, right, return_block_);
188 }
189
190 // Add a HVecLoad instruction to the end of the provided basic block.
191 //
192 // Return: the created HVecLoad instruction.
AddVecLoad(HBasicBlock * block,HInstruction * array,HInstruction * index)193 HInstruction* AddVecLoad(HBasicBlock* block, HInstruction* array, HInstruction* index) {
194 DCHECK(block != nullptr);
195 DCHECK(array != nullptr);
196 DCHECK(index != nullptr);
197 HInstruction* vload =
198 new (GetAllocator()) HVecLoad(GetAllocator(),
199 array,
200 index,
201 DataType::Type::kInt32,
202 SideEffects::ArrayReadOfType(DataType::Type::kInt32),
203 4,
204 /*is_string_char_at*/ false,
205 kNoDexPc);
206 block->InsertInstructionBefore(vload, block->GetLastInstruction());
207 return vload;
208 }
209
210 // Add a HVecStore instruction to the end of the provided basic block.
211 // If no vdata is specified, generate HVecStore: array[index] = [1,1,1,1].
212 //
213 // Return: the created HVecStore instruction.
AddVecStore(HBasicBlock * block,HInstruction * array,HInstruction * index,HInstruction * vdata=nullptr)214 HInstruction* AddVecStore(HBasicBlock* block,
215 HInstruction* array,
216 HInstruction* index,
217 HInstruction* vdata = nullptr) {
218 DCHECK(block != nullptr);
219 DCHECK(array != nullptr);
220 DCHECK(index != nullptr);
221 if (vdata == nullptr) {
222 HInstruction* c1 = graph_->GetIntConstant(1);
223 vdata = new (GetAllocator())
224 HVecReplicateScalar(GetAllocator(), c1, DataType::Type::kInt32, 4, kNoDexPc);
225 block->InsertInstructionBefore(vdata, block->GetLastInstruction());
226 }
227 HInstruction* vstore =
228 new (GetAllocator()) HVecStore(GetAllocator(),
229 array,
230 index,
231 vdata,
232 DataType::Type::kInt32,
233 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
234 4,
235 kNoDexPc);
236 block->InsertInstructionBefore(vstore, block->GetLastInstruction());
237 return vstore;
238 }
239
240 // Add a HArrayGet instruction to the end of the provided basic block.
241 //
242 // Return: the created HArrayGet instruction.
AddArrayGet(HBasicBlock * block,HInstruction * array,HInstruction * index)243 HInstruction* AddArrayGet(HBasicBlock* block, HInstruction* array, HInstruction* index) {
244 DCHECK(block != nullptr);
245 DCHECK(array != nullptr);
246 DCHECK(index != nullptr);
247 HInstruction* get = new (GetAllocator()) HArrayGet(array, index, DataType::Type::kInt32, 0);
248 block->InsertInstructionBefore(get, block->GetLastInstruction());
249 return get;
250 }
251
252 // Add a HArraySet instruction to the end of the provided basic block.
253 // If no data is specified, generate HArraySet: array[index] = 1.
254 //
255 // Return: the created HArraySet instruction.
AddArraySet(HBasicBlock * block,HInstruction * array,HInstruction * index,HInstruction * data=nullptr)256 HInstruction* AddArraySet(HBasicBlock* block,
257 HInstruction* array,
258 HInstruction* index,
259 HInstruction* data = nullptr) {
260 DCHECK(block != nullptr);
261 DCHECK(array != nullptr);
262 DCHECK(index != nullptr);
263 if (data == nullptr) {
264 data = graph_->GetIntConstant(1);
265 }
266 HInstruction* store =
267 new (GetAllocator()) HArraySet(array, index, data, DataType::Type::kInt32, 0);
268 block->InsertInstructionBefore(store, block->GetLastInstruction());
269 return store;
270 }
271
InitGraphAndParameters()272 void InitGraphAndParameters() {
273 InitGraph();
274 AddParameter(new (GetAllocator()) HParameterValue(
275 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kInt32));
276 array_ = parameters_.back();
277 AddParameter(new (GetAllocator()) HParameterValue(
278 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32));
279 i_ = parameters_.back();
280 AddParameter(new (GetAllocator()) HParameterValue(
281 graph_->GetDexFile(), dex::TypeIndex(1), 2, DataType::Type::kInt32));
282 j_ = parameters_.back();
283 }
284
285 HBasicBlock* pre_header_;
286 HBasicBlock* loop_;
287
288 HInstruction* array_;
289 HInstruction* i_;
290 HInstruction* j_;
291 HInstruction* i_add1_;
292 HInstruction* i_add4_;
293 HInstruction* suspend_check_;
294
295 HPhi* phi_;
296 };
297
298 class LoadStoreEliminationTest : public LoadStoreEliminationTestBase<CommonCompilerTest> {};
299
300 enum class TestOrder { kSameAsAlloc, kReverseOfAlloc };
operator <<(std::ostream & os,const TestOrder & ord)301 std::ostream& operator<<(std::ostream& os, const TestOrder& ord) {
302 switch (ord) {
303 case TestOrder::kSameAsAlloc:
304 return os << "SameAsAlloc";
305 case TestOrder::kReverseOfAlloc:
306 return os << "ReverseOfAlloc";
307 }
308 }
309
TEST_F(LoadStoreEliminationTest,ArrayGetSetElimination)310 TEST_F(LoadStoreEliminationTest, ArrayGetSetElimination) {
311 CreateTestControlFlowGraph();
312
313 HInstruction* c1 = graph_->GetIntConstant(1);
314 HInstruction* c2 = graph_->GetIntConstant(2);
315 HInstruction* c3 = graph_->GetIntConstant(3);
316
317 // array[1] = 1;
318 // x = array[1]; <--- Remove.
319 // y = array[2];
320 // array[1] = 1; <--- Remove, since it stores same value.
321 // array[i] = 3; <--- MAY alias.
322 // array[1] = 1; <--- Cannot remove, even if it stores the same value.
323 AddArraySet(entry_block_, array_, c1, c1);
324 HInstruction* load1 = AddArrayGet(entry_block_, array_, c1);
325 HInstruction* load2 = AddArrayGet(entry_block_, array_, c2);
326 HInstruction* store1 = AddArraySet(entry_block_, array_, c1, c1);
327 AddArraySet(entry_block_, array_, i_, c3);
328 HInstruction* store2 = AddArraySet(entry_block_, array_, c1, c1);
329
330 PerformLSE();
331
332 ASSERT_TRUE(IsRemoved(load1));
333 ASSERT_FALSE(IsRemoved(load2));
334 ASSERT_TRUE(IsRemoved(store1));
335 ASSERT_FALSE(IsRemoved(store2));
336 }
337
TEST_F(LoadStoreEliminationTest,SameHeapValue1)338 TEST_F(LoadStoreEliminationTest, SameHeapValue1) {
339 CreateTestControlFlowGraph();
340
341 HInstruction* c1 = graph_->GetIntConstant(1);
342 HInstruction* c2 = graph_->GetIntConstant(2);
343
344 // Test LSE handling same value stores on array.
345 // array[1] = 1;
346 // array[2] = 1;
347 // array[1] = 1; <--- Can remove.
348 // array[1] = 2; <--- Can NOT remove.
349 AddArraySet(entry_block_, array_, c1, c1);
350 AddArraySet(entry_block_, array_, c2, c1);
351 HInstruction* store1 = AddArraySet(entry_block_, array_, c1, c1);
352 HInstruction* store2 = AddArraySet(entry_block_, array_, c1, c2);
353
354 PerformLSE();
355
356 ASSERT_TRUE(IsRemoved(store1));
357 ASSERT_FALSE(IsRemoved(store2));
358 }
359
TEST_F(LoadStoreEliminationTest,SameHeapValue2)360 TEST_F(LoadStoreEliminationTest, SameHeapValue2) {
361 CreateTestControlFlowGraph();
362
363 // Test LSE handling same value stores on vector.
364 // vdata = [0x1, 0x2, 0x3, 0x4, ...]
365 // VecStore array[i...] = vdata;
366 // VecStore array[j...] = vdata; <--- MAY ALIAS.
367 // VecStore array[i...] = vdata; <--- Cannot Remove, even if it's same value.
368 AddVecStore(entry_block_, array_, i_);
369 AddVecStore(entry_block_, array_, j_);
370 HInstruction* vstore = AddVecStore(entry_block_, array_, i_);
371
372 // TODO: enable LSE for graphs with predicated SIMD.
373 graph_->SetHasTraditionalSIMD(true);
374 PerformLSE();
375
376 ASSERT_FALSE(IsRemoved(vstore));
377 }
378
TEST_F(LoadStoreEliminationTest,SameHeapValue3)379 TEST_F(LoadStoreEliminationTest, SameHeapValue3) {
380 CreateTestControlFlowGraph();
381
382 // VecStore array[i...] = vdata;
383 // VecStore array[i+1...] = vdata; <--- MAY alias due to partial overlap.
384 // VecStore array[i...] = vdata; <--- Cannot remove, even if it's same value.
385 AddVecStore(entry_block_, array_, i_);
386 AddVecStore(entry_block_, array_, i_add1_);
387 HInstruction* vstore = AddVecStore(entry_block_, array_, i_);
388
389 // TODO: enable LSE for graphs with predicated SIMD.
390 graph_->SetHasTraditionalSIMD(true);
391 PerformLSE();
392
393 ASSERT_FALSE(IsRemoved(vstore));
394 }
395
TEST_F(LoadStoreEliminationTest,OverlappingLoadStore)396 TEST_F(LoadStoreEliminationTest, OverlappingLoadStore) {
397 CreateTestControlFlowGraph();
398
399 HInstruction* c1 = graph_->GetIntConstant(1);
400
401 // Test LSE handling array LSE when there is vector store in between.
402 // a[i] = 1;
403 // .. = a[i]; <-- Remove.
404 // a[i,i+1,i+2,i+3] = data; <-- PARTIAL OVERLAP !
405 // .. = a[i]; <-- Cannot remove.
406 AddArraySet(entry_block_, array_, i_, c1);
407 HInstruction* load1 = AddArrayGet(entry_block_, array_, i_);
408 AddVecStore(entry_block_, array_, i_);
409 HInstruction* load2 = AddArrayGet(entry_block_, array_, i_);
410
411 // Test LSE handling vector load/store partial overlap.
412 // a[i,i+1,i+2,i+3] = data;
413 // a[i+4,i+5,i+6,i+7] = data;
414 // .. = a[i,i+1,i+2,i+3];
415 // .. = a[i+4,i+5,i+6,i+7];
416 // a[i+1,i+2,i+3,i+4] = data; <-- PARTIAL OVERLAP !
417 // .. = a[i,i+1,i+2,i+3];
418 // .. = a[i+4,i+5,i+6,i+7];
419 AddVecStore(entry_block_, array_, i_);
420 AddVecStore(entry_block_, array_, i_add4_);
421 HInstruction* vload1 = AddVecLoad(entry_block_, array_, i_);
422 HInstruction* vload2 = AddVecLoad(entry_block_, array_, i_add4_);
423 AddVecStore(entry_block_, array_, i_add1_);
424 HInstruction* vload3 = AddVecLoad(entry_block_, array_, i_);
425 HInstruction* vload4 = AddVecLoad(entry_block_, array_, i_add4_);
426
427 // Test LSE handling vector LSE when there is array store in between.
428 // a[i,i+1,i+2,i+3] = data;
429 // a[i+1] = 1; <-- PARTIAL OVERLAP !
430 // .. = a[i,i+1,i+2,i+3];
431 AddVecStore(entry_block_, array_, i_);
432 AddArraySet(entry_block_, array_, i_, c1);
433 HInstruction* vload5 = AddVecLoad(entry_block_, array_, i_);
434
435 // TODO: enable LSE for graphs with predicated SIMD.
436 graph_->SetHasTraditionalSIMD(true);
437 PerformLSE();
438
439 ASSERT_TRUE(IsRemoved(load1));
440 ASSERT_FALSE(IsRemoved(load2));
441
442 ASSERT_TRUE(IsRemoved(vload1));
443 ASSERT_TRUE(IsRemoved(vload2));
444 ASSERT_FALSE(IsRemoved(vload3));
445 ASSERT_FALSE(IsRemoved(vload4));
446
447 ASSERT_FALSE(IsRemoved(vload5));
448 }
449 // function (int[] a, int j) {
450 // a[j] = 1;
451 // for (int i=0; i<128; i++) {
452 // /* doesn't do any write */
453 // }
454 // a[j] = 1;
TEST_F(LoadStoreEliminationTest,StoreAfterLoopWithoutSideEffects)455 TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithoutSideEffects) {
456 CreateTestControlFlowGraph();
457
458 HInstruction* c1 = graph_->GetIntConstant(1);
459
460 // a[j] = 1
461 AddArraySet(pre_header_, array_, j_, c1);
462
463 // LOOP BODY:
464 // .. = a[i,i+1,i+2,i+3];
465 AddVecLoad(loop_, array_, phi_);
466
467 // a[j] = 1;
468 HInstruction* array_set = AddArraySet(return_block_, array_, j_, c1);
469
470 // TODO: enable LSE for graphs with predicated SIMD.
471 graph_->SetHasTraditionalSIMD(true);
472 PerformLSE();
473
474 ASSERT_TRUE(IsRemoved(array_set));
475 }
476
477 // function (int[] a, int j) {
478 // int[] b = new int[128];
479 // a[j] = 0;
480 // for (int phi=0; phi<128; phi++) {
481 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
482 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
483 // }
484 // a[j] = 0;
485 // }
TEST_F(LoadStoreEliminationTest,StoreAfterSIMDLoopWithSideEffects)486 TEST_F(LoadStoreEliminationTest, StoreAfterSIMDLoopWithSideEffects) {
487 CreateTestControlFlowGraph();
488
489 HInstruction* c0 = graph_->GetIntConstant(0);
490 HInstruction* c128 = graph_->GetIntConstant(128);
491
492 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
493 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
494 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
495
496 // a[j] = 0;
497 AddArraySet(pre_header_, array_, j_, c0);
498
499 // LOOP BODY:
500 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
501 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
502 AddVecStore(loop_, array_, phi_);
503 HInstruction* vload = AddVecLoad(loop_, array_, phi_);
504 AddVecStore(loop_, array_b, phi_, vload);
505
506 // a[j] = 0;
507 HInstruction* a_set = AddArraySet(return_block_, array_, j_, c0);
508
509 // TODO: enable LSE for graphs with predicated SIMD.
510 graph_->SetHasTraditionalSIMD(true);
511 PerformLSE();
512
513 ASSERT_TRUE(IsRemoved(vload));
514 ASSERT_FALSE(IsRemoved(a_set)); // Cannot remove due to write side-effect in the loop.
515 }
516
517 // function (int[] a, int j) {
518 // int[] b = new int[128];
519 // a[j] = 0;
520 // for (int phi=0; phi<128; phi++) {
521 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
522 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
523 // }
524 // x = a[j];
525 // }
TEST_F(LoadStoreEliminationTest,LoadAfterSIMDLoopWithSideEffects)526 TEST_F(LoadStoreEliminationTest, LoadAfterSIMDLoopWithSideEffects) {
527 CreateTestControlFlowGraph();
528
529 HInstruction* c0 = graph_->GetIntConstant(0);
530 HInstruction* c128 = graph_->GetIntConstant(128);
531
532 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
533 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
534 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
535
536 // a[j] = 0;
537 AddArraySet(pre_header_, array_, j_, c0);
538
539 // LOOP BODY:
540 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
541 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
542 AddVecStore(loop_, array_, phi_);
543 HInstruction* vload = AddVecLoad(loop_, array_, phi_);
544 AddVecStore(loop_, array_b, phi_, vload);
545
546 // x = a[j];
547 HInstruction* load = AddArrayGet(return_block_, array_, j_);
548
549 // TODO: enable LSE for graphs with predicated SIMD.
550 graph_->SetHasTraditionalSIMD(true);
551 PerformLSE();
552
553 ASSERT_TRUE(IsRemoved(vload));
554 ASSERT_FALSE(IsRemoved(load)); // Cannot remove due to write side-effect in the loop.
555 }
556
557 // Check that merging works correctly when there are VecStors in predecessors.
558 //
559 // vstore1: a[i,... i + 3] = [1,...1]
560 // / \
561 // / \
562 // vstore2: a[i,... i + 3] = [1,...1] vstore3: a[i+1, ... i + 4] = [1, ... 1]
563 // \ /
564 // \ /
565 // vstore4: a[i,... i + 3] = [1,...1]
566 //
567 // Expected:
568 // 'vstore2' is removed.
569 // 'vstore3' is not removed.
570 // 'vstore4' is not removed. Such cases are not supported at the moment.
TEST_F(LoadStoreEliminationTest,MergePredecessorVecStores)571 TEST_F(LoadStoreEliminationTest, MergePredecessorVecStores) {
572 HBasicBlock* upper;
573 HBasicBlock* left;
574 HBasicBlock* right;
575 HBasicBlock* down;
576 std::tie(upper, left, right, down) = CreateDiamondShapedCFG();
577
578 // upper: a[i,... i + 3] = [1,...1]
579 HInstruction* vstore1 = AddVecStore(upper, array_, i_);
580 HInstruction* vdata = vstore1->InputAt(2);
581
582 // left: a[i,... i + 3] = [1,...1]
583 HInstruction* vstore2 = AddVecStore(left, array_, i_, vdata);
584
585 // right: a[i+1, ... i + 4] = [1, ... 1]
586 HInstruction* vstore3 = AddVecStore(right, array_, i_add1_, vdata);
587
588 // down: a[i,... i + 3] = [1,...1]
589 HInstruction* vstore4 = AddVecStore(down, array_, i_, vdata);
590
591 // TODO: enable LSE for graphs with predicated SIMD.
592 graph_->SetHasTraditionalSIMD(true);
593 PerformLSE();
594
595 ASSERT_TRUE(IsRemoved(vstore2));
596 ASSERT_FALSE(IsRemoved(vstore3));
597 ASSERT_FALSE(IsRemoved(vstore4));
598 }
599
600 // Check that merging works correctly when there are ArraySets in predecessors.
601 //
602 // a[i] = 1
603 // / \
604 // / \
605 // store1: a[i] = 1 store2: a[i+1] = 1
606 // \ /
607 // \ /
608 // store3: a[i] = 1
609 //
610 // Expected:
611 // 'store1' is removed.
612 // 'store2' is not removed.
613 // 'store3' is removed.
TEST_F(LoadStoreEliminationTest,MergePredecessorStores)614 TEST_F(LoadStoreEliminationTest, MergePredecessorStores) {
615 HBasicBlock* upper;
616 HBasicBlock* left;
617 HBasicBlock* right;
618 HBasicBlock* down;
619 std::tie(upper, left, right, down) = CreateDiamondShapedCFG();
620
621 // upper: a[i,... i + 3] = [1,...1]
622 AddArraySet(upper, array_, i_);
623
624 // left: a[i,... i + 3] = [1,...1]
625 HInstruction* store1 = AddArraySet(left, array_, i_);
626
627 // right: a[i+1, ... i + 4] = [1, ... 1]
628 HInstruction* store2 = AddArraySet(right, array_, i_add1_);
629
630 // down: a[i,... i + 3] = [1,...1]
631 HInstruction* store3 = AddArraySet(down, array_, i_);
632
633 PerformLSE();
634
635 ASSERT_TRUE(IsRemoved(store1));
636 ASSERT_FALSE(IsRemoved(store2));
637 ASSERT_TRUE(IsRemoved(store3));
638 }
639
640 // Check that redundant VStore/VLoad are removed from a SIMD loop.
641 //
642 // LOOP BODY
643 // vstore1: a[i,... i + 3] = [1,...1]
644 // vload: x = a[i,... i + 3]
645 // vstore2: b[i,... i + 3] = x
646 // vstore3: a[i,... i + 3] = [1,...1]
647 //
648 // Return 'a' from the method to make it escape.
649 //
650 // Expected:
651 // 'vstore1' is not removed.
652 // 'vload' is removed.
653 // 'vstore2' is removed because 'b' does not escape.
654 // 'vstore3' is removed.
TEST_F(LoadStoreEliminationTest,RedundantVStoreVLoadInLoop)655 TEST_F(LoadStoreEliminationTest, RedundantVStoreVLoadInLoop) {
656 CreateTestControlFlowGraph();
657
658 HInstruction* c0 = graph_->GetIntConstant(0);
659 HInstruction* c128 = graph_->GetIntConstant(128);
660
661 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
662 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
663 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
664
665 ASSERT_TRUE(return_block_->GetLastInstruction()->IsReturnVoid());
666 HInstruction* ret = new (GetAllocator()) HReturn(array_a);
667 return_block_->ReplaceAndRemoveInstructionWith(return_block_->GetLastInstruction(), ret);
668
669 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
670 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
671 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
672
673 // LOOP BODY:
674 // a[i,... i + 3] = [1,...1]
675 // x = a[i,... i + 3]
676 // b[i,... i + 3] = x
677 // a[i,... i + 3] = [1,...1]
678 HInstruction* vstore1 = AddVecStore(loop_, array_a, phi_);
679 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
680 HInstruction* vstore2 = AddVecStore(loop_, array_b, phi_, vload);
681 HInstruction* vstore3 = AddVecStore(loop_, array_a, phi_, vstore1->InputAt(2));
682
683 // TODO: enable LSE for graphs with predicated SIMD.
684 graph_->SetHasTraditionalSIMD(true);
685 PerformLSE();
686
687 ASSERT_FALSE(IsRemoved(vstore1));
688 ASSERT_TRUE(IsRemoved(vload));
689 ASSERT_TRUE(IsRemoved(vstore2));
690 ASSERT_TRUE(IsRemoved(vstore3));
691 }
692
693 // Loop writes invalidate only possibly aliased heap locations.
TEST_F(LoadStoreEliminationTest,StoreAfterLoopWithSideEffects)694 TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithSideEffects) {
695 CreateTestControlFlowGraph();
696
697 HInstruction* c0 = graph_->GetIntConstant(0);
698 HInstruction* c2 = graph_->GetIntConstant(2);
699 HInstruction* c128 = graph_->GetIntConstant(128);
700
701 // array[0] = 2;
702 // loop:
703 // b[i] = array[i]
704 // array[0] = 2
705 HInstruction* store1 = AddArraySet(entry_block_, array_, c0, c2);
706
707 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
708 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
709 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
710
711 HInstruction* load = AddArrayGet(loop_, array_, phi_);
712 HInstruction* store2 = AddArraySet(loop_, array_b, phi_, load);
713
714 HInstruction* store3 = AddArraySet(return_block_, array_, c0, c2);
715
716 PerformLSE();
717
718 ASSERT_FALSE(IsRemoved(store1));
719 ASSERT_TRUE(IsRemoved(store2));
720 ASSERT_TRUE(IsRemoved(store3));
721 }
722
723 // Loop writes invalidate only possibly aliased heap locations.
TEST_F(LoadStoreEliminationTest,StoreAfterLoopWithSideEffects2)724 TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithSideEffects2) {
725 CreateTestControlFlowGraph();
726
727 // Add another array parameter that may alias with `array_`.
728 // Note: We're not adding it to the suspend check environment.
729 AddParameter(new (GetAllocator()) HParameterValue(
730 graph_->GetDexFile(), dex::TypeIndex(0), 3, DataType::Type::kInt32));
731 HInstruction* array2 = parameters_.back();
732
733 HInstruction* c0 = graph_->GetIntConstant(0);
734 HInstruction* c2 = graph_->GetIntConstant(2);
735
736 // array[0] = 2;
737 // loop:
738 // array2[i] = array[i]
739 // array[0] = 2
740 HInstruction* store1 = AddArraySet(pre_header_, array_, c0, c2);
741
742 HInstruction* load = AddArrayGet(loop_, array_, phi_);
743 HInstruction* store2 = AddArraySet(loop_, array2, phi_, load);
744
745 HInstruction* store3 = AddArraySet(return_block_, array_, c0, c2);
746
747 PerformLSE();
748
749 ASSERT_FALSE(IsRemoved(store1));
750 ASSERT_FALSE(IsRemoved(store2));
751 ASSERT_FALSE(IsRemoved(store3));
752 }
753
754 // As it is not allowed to use defaults for VecLoads, check if there is a new created array
755 // a VecLoad used in a loop and after it is not replaced with a default.
TEST_F(LoadStoreEliminationTest,VLoadDefaultValueInLoopWithoutWriteSideEffects)756 TEST_F(LoadStoreEliminationTest, VLoadDefaultValueInLoopWithoutWriteSideEffects) {
757 CreateTestControlFlowGraph();
758
759 HInstruction* c0 = graph_->GetIntConstant(0);
760 HInstruction* c128 = graph_->GetIntConstant(128);
761
762 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
763 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
764 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
765
766 // LOOP BODY:
767 // v = a[i,... i + 3]
768 // array[0,... 3] = v
769 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
770 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload);
771
772 // TODO: enable LSE for graphs with predicated SIMD.
773 graph_->SetHasTraditionalSIMD(true);
774 PerformLSE();
775
776 ASSERT_FALSE(IsRemoved(vload));
777 ASSERT_FALSE(IsRemoved(vstore));
778 }
779
780 // As it is not allowed to use defaults for VecLoads, check if there is a new created array
781 // a VecLoad is not replaced with a default.
TEST_F(LoadStoreEliminationTest,VLoadDefaultValue)782 TEST_F(LoadStoreEliminationTest, VLoadDefaultValue) {
783 CreateTestControlFlowGraph();
784
785 HInstruction* c0 = graph_->GetIntConstant(0);
786 HInstruction* c128 = graph_->GetIntConstant(128);
787
788 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
789 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
790 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
791
792 // v = a[0,... 3]
793 // array[0,... 3] = v
794 HInstruction* vload = AddVecLoad(pre_header_, array_a, c0);
795 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload);
796
797 // TODO: enable LSE for graphs with predicated SIMD.
798 graph_->SetHasTraditionalSIMD(true);
799 PerformLSE();
800
801 ASSERT_FALSE(IsRemoved(vload));
802 ASSERT_FALSE(IsRemoved(vstore));
803 }
804
805 // As it is allowed to use defaults for ordinary loads, check if there is a new created array
806 // a load used in a loop and after it is replaced with a default.
TEST_F(LoadStoreEliminationTest,LoadDefaultValueInLoopWithoutWriteSideEffects)807 TEST_F(LoadStoreEliminationTest, LoadDefaultValueInLoopWithoutWriteSideEffects) {
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]
819 // array[0] = v
820 HInstruction* load = AddArrayGet(loop_, array_a, phi_);
821 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
822
823 PerformLSE();
824
825 ASSERT_TRUE(IsRemoved(load));
826 ASSERT_FALSE(IsRemoved(store));
827 }
828
829 // As it is allowed to use defaults for ordinary loads, check if there is a new created array
830 // a load is replaced with a default.
TEST_F(LoadStoreEliminationTest,LoadDefaultValue)831 TEST_F(LoadStoreEliminationTest, LoadDefaultValue) {
832 CreateTestControlFlowGraph();
833
834 HInstruction* c0 = graph_->GetIntConstant(0);
835 HInstruction* c128 = graph_->GetIntConstant(128);
836
837 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
838 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
839 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
840
841 // v = a[0]
842 // array[0] = v
843 HInstruction* load = AddArrayGet(pre_header_, array_a, c0);
844 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
845
846 PerformLSE();
847
848 ASSERT_TRUE(IsRemoved(load));
849 ASSERT_FALSE(IsRemoved(store));
850 }
851
852 // As it is not allowed to use defaults for VecLoads but allowed for regular loads,
853 // check if there is a new created array, a VecLoad and a load used in a loop and after it,
854 // VecLoad is not replaced with a default but the load is.
TEST_F(LoadStoreEliminationTest,VLoadAndLoadDefaultValueInLoopWithoutWriteSideEffects)855 TEST_F(LoadStoreEliminationTest, VLoadAndLoadDefaultValueInLoopWithoutWriteSideEffects) {
856 CreateTestControlFlowGraph();
857
858 HInstruction* c0 = graph_->GetIntConstant(0);
859 HInstruction* c128 = graph_->GetIntConstant(128);
860
861 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
862 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
863 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
864
865 // LOOP BODY:
866 // v = a[i,... i + 3]
867 // v1 = a[i]
868 // array[0,... 3] = v
869 // array[0] = v1
870 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
871 HInstruction* load = AddArrayGet(loop_, array_a, phi_);
872 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload);
873 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
874
875 // TODO: enable LSE for graphs with predicated SIMD.
876 graph_->SetHasTraditionalSIMD(true);
877 PerformLSE();
878
879 ASSERT_FALSE(IsRemoved(vload));
880 ASSERT_TRUE(IsRemoved(load));
881 ASSERT_FALSE(IsRemoved(vstore));
882 ASSERT_FALSE(IsRemoved(store));
883 }
884
885 // As it is not allowed to use defaults for VecLoads but allowed for regular loads,
886 // check if there is a new created array, a VecLoad and a load,
887 // VecLoad is not replaced with a default but the load is.
TEST_F(LoadStoreEliminationTest,VLoadAndLoadDefaultValue)888 TEST_F(LoadStoreEliminationTest, VLoadAndLoadDefaultValue) {
889 CreateTestControlFlowGraph();
890
891 HInstruction* c0 = graph_->GetIntConstant(0);
892 HInstruction* c128 = graph_->GetIntConstant(128);
893
894 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
895 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
896 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
897
898 // v = a[0,... 3]
899 // v1 = a[0]
900 // array[0,... 3] = v
901 // array[0] = v1
902 HInstruction* vload = AddVecLoad(pre_header_, array_a, c0);
903 HInstruction* load = AddArrayGet(pre_header_, array_a, c0);
904 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload);
905 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
906
907 // TODO: enable LSE for graphs with predicated SIMD.
908 graph_->SetHasTraditionalSIMD(true);
909 PerformLSE();
910
911 ASSERT_FALSE(IsRemoved(vload));
912 ASSERT_TRUE(IsRemoved(load));
913 ASSERT_FALSE(IsRemoved(vstore));
914 ASSERT_FALSE(IsRemoved(store));
915 }
916
917 // It is not allowed to use defaults for VecLoads. However it should not prevent from removing
918 // loads getting the same value.
919 // Check a load getting a known value is eliminated (a loop test case).
TEST_F(LoadStoreEliminationTest,VLoadDefaultValueAndVLoadInLoopWithoutWriteSideEffects)920 TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoadInLoopWithoutWriteSideEffects) {
921 CreateTestControlFlowGraph();
922
923 HInstruction* c0 = graph_->GetIntConstant(0);
924 HInstruction* c128 = graph_->GetIntConstant(128);
925
926 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
927 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
928 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
929
930 // LOOP BODY:
931 // v = a[i,... i + 3]
932 // v1 = a[i,... i + 3]
933 // array[0,... 3] = v
934 // array[128,... 131] = v1
935 HInstruction* vload1 = AddVecLoad(loop_, array_a, phi_);
936 HInstruction* vload2 = AddVecLoad(loop_, array_a, phi_);
937 HInstruction* vstore1 = AddVecStore(return_block_, array_, c0, vload1);
938 HInstruction* vstore2 = AddVecStore(return_block_, array_, c128, vload2);
939
940 // TODO: enable LSE for graphs with predicated SIMD.
941 graph_->SetHasTraditionalSIMD(true);
942 PerformLSE();
943
944 ASSERT_FALSE(IsRemoved(vload1));
945 ASSERT_TRUE(IsRemoved(vload2));
946 ASSERT_FALSE(IsRemoved(vstore1));
947 ASSERT_FALSE(IsRemoved(vstore2));
948 }
949
950 // It is not allowed to use defaults for VecLoads. However it should not prevent from removing
951 // loads getting the same value.
952 // Check a load getting a known value is eliminated.
TEST_F(LoadStoreEliminationTest,VLoadDefaultValueAndVLoad)953 TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoad) {
954 CreateTestControlFlowGraph();
955
956 HInstruction* c0 = graph_->GetIntConstant(0);
957 HInstruction* c128 = graph_->GetIntConstant(128);
958
959 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
960 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
961 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
962
963 // v = a[0,... 3]
964 // v1 = a[0,... 3]
965 // array[0,... 3] = v
966 // array[128,... 131] = v1
967 HInstruction* vload1 = AddVecLoad(pre_header_, array_a, c0);
968 HInstruction* vload2 = AddVecLoad(pre_header_, array_a, c0);
969 HInstruction* vstore1 = AddVecStore(return_block_, array_, c0, vload1);
970 HInstruction* vstore2 = AddVecStore(return_block_, array_, c128, vload2);
971
972 // TODO: enable LSE for graphs with predicated SIMD.
973 graph_->SetHasTraditionalSIMD(true);
974 PerformLSE();
975
976 ASSERT_FALSE(IsRemoved(vload1));
977 ASSERT_TRUE(IsRemoved(vload2));
978 ASSERT_FALSE(IsRemoved(vstore1));
979 ASSERT_FALSE(IsRemoved(vstore2));
980 }
981
982 // Object o = new Obj();
983 // // Needed because otherwise we short-circuit LSA since GVN would get almost
984 // // everything other than this. Also since this isn't expected to be a very
985 // // common pattern it's not worth changing the LSA logic.
986 // o.foo = 3;
987 // return o.shadow$_klass_;
TEST_F(LoadStoreEliminationTest,DefaultShadowClass)988 TEST_F(LoadStoreEliminationTest, DefaultShadowClass) {
989 CreateGraph();
990 AdjacencyListGraph blocks(
991 graph_, GetAllocator(), "entry", "exit", {{"entry", "main"}, {"main", "exit"}});
992 #define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
993 GET_BLOCK(entry);
994 GET_BLOCK(main);
995 GET_BLOCK(exit);
996 #undef GET_BLOCK
997
998 HInstruction* suspend_check = new (GetAllocator()) HSuspendCheck();
999 entry->AddInstruction(suspend_check);
1000 entry->AddInstruction(new (GetAllocator()) HGoto());
1001 ManuallyBuildEnvFor(suspend_check, {});
1002
1003 HInstruction* cls = MakeClassLoad();
1004 HInstruction* new_inst = MakeNewInstance(cls);
1005 HInstruction* const_fence = new (GetAllocator()) HConstructorFence(new_inst, 0, GetAllocator());
1006 HInstruction* set_field = MakeIFieldSet(new_inst, graph_->GetIntConstant(33), MemberOffset(32));
1007 HInstruction* get_field =
1008 MakeIFieldGet(new_inst, DataType::Type::kReference, mirror::Object::ClassOffset());
1009 HInstruction* return_val = new (GetAllocator()) HReturn(get_field);
1010 main->AddInstruction(cls);
1011 main->AddInstruction(new_inst);
1012 main->AddInstruction(const_fence);
1013 main->AddInstruction(set_field);
1014 main->AddInstruction(get_field);
1015 main->AddInstruction(return_val);
1016 cls->CopyEnvironmentFrom(suspend_check->GetEnvironment());
1017 new_inst->CopyEnvironmentFrom(suspend_check->GetEnvironment());
1018
1019 SetupExit(exit);
1020
1021 graph_->ClearDominanceInformation();
1022 PerformLSE();
1023
1024 EXPECT_INS_REMOVED(new_inst);
1025 EXPECT_INS_REMOVED(const_fence);
1026 EXPECT_INS_REMOVED(get_field);
1027 EXPECT_INS_REMOVED(set_field);
1028 EXPECT_INS_RETAINED(cls);
1029 EXPECT_INS_EQ(cls, return_val->InputAt(0));
1030 }
1031
1032 // Object o = new Obj();
1033 // // Needed because otherwise we short-circuit LSA since GVN would get almost
1034 // // everything other than this. Also since this isn't expected to be a very
1035 // // common pattern (only a single java function, Object.identityHashCode,
1036 // // ever reads this field) it's not worth changing the LSA logic.
1037 // o.foo = 3;
1038 // return o.shadow$_monitor_;
TEST_F(LoadStoreEliminationTest,DefaultShadowMonitor)1039 TEST_F(LoadStoreEliminationTest, DefaultShadowMonitor) {
1040 CreateGraph();
1041 AdjacencyListGraph blocks(
1042 graph_, GetAllocator(), "entry", "exit", {{"entry", "main"}, {"main", "exit"}});
1043 #define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1044 GET_BLOCK(entry);
1045 GET_BLOCK(main);
1046 GET_BLOCK(exit);
1047 #undef GET_BLOCK
1048
1049 HInstruction* suspend_check = new (GetAllocator()) HSuspendCheck();
1050 entry->AddInstruction(suspend_check);
1051 entry->AddInstruction(new (GetAllocator()) HGoto());
1052 ManuallyBuildEnvFor(suspend_check, {});
1053
1054 HInstruction* cls = MakeClassLoad();
1055 HInstruction* new_inst = MakeNewInstance(cls);
1056 HInstruction* const_fence = new (GetAllocator()) HConstructorFence(new_inst, 0, GetAllocator());
1057 HInstruction* set_field = MakeIFieldSet(new_inst, graph_->GetIntConstant(33), MemberOffset(32));
1058 HInstruction* get_field =
1059 MakeIFieldGet(new_inst, DataType::Type::kInt32, mirror::Object::MonitorOffset());
1060 HInstruction* return_val = new (GetAllocator()) HReturn(get_field);
1061 main->AddInstruction(cls);
1062 main->AddInstruction(new_inst);
1063 main->AddInstruction(const_fence);
1064 main->AddInstruction(set_field);
1065 main->AddInstruction(get_field);
1066 main->AddInstruction(return_val);
1067 cls->CopyEnvironmentFrom(suspend_check->GetEnvironment());
1068 new_inst->CopyEnvironmentFrom(suspend_check->GetEnvironment());
1069
1070 SetupExit(exit);
1071
1072 graph_->ClearDominanceInformation();
1073 PerformLSE();
1074
1075 EXPECT_INS_REMOVED(new_inst);
1076 EXPECT_INS_REMOVED(const_fence);
1077 EXPECT_INS_REMOVED(get_field);
1078 EXPECT_INS_REMOVED(set_field);
1079 EXPECT_INS_RETAINED(cls);
1080 EXPECT_INS_EQ(graph_->GetIntConstant(0), return_val->InputAt(0));
1081 }
1082
1083 // void DO_CAL() {
1084 // int i = 1;
1085 // int[] w = new int[80];
1086 // int t = 0;
1087 // while (i < 80) {
1088 // w[i] = PLEASE_INTERLEAVE(w[i - 1], 1)
1089 // t = PLEASE_SELECT(w[i], t);
1090 // i++;
1091 // }
1092 // return t;
1093 // }
TEST_F(LoadStoreEliminationTest,ArrayLoopOverlap)1094 TEST_F(LoadStoreEliminationTest, ArrayLoopOverlap) {
1095 ScopedObjectAccess soa(Thread::Current());
1096 VariableSizedHandleScope vshs(soa.Self());
1097 CreateGraph(&vshs);
1098 AdjacencyListGraph blocks(graph_,
1099 GetAllocator(),
1100 "entry",
1101 "exit",
1102 { { "entry", "loop_pre_header" },
1103 { "loop_pre_header", "loop_entry" },
1104 { "loop_entry", "loop_body" },
1105 { "loop_entry", "loop_post" },
1106 { "loop_body", "loop_entry" },
1107 { "loop_post", "exit" } });
1108 #define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1109 GET_BLOCK(entry);
1110 GET_BLOCK(loop_pre_header);
1111 GET_BLOCK(loop_entry);
1112 GET_BLOCK(loop_body);
1113 GET_BLOCK(loop_post);
1114 GET_BLOCK(exit);
1115 #undef GET_BLOCK
1116
1117 HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
1118 HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
1119 HInstruction* eighty_const = graph_->GetConstant(DataType::Type::kInt32, 80);
1120 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1121 entry->AddInstruction(entry_goto);
1122
1123 HInstruction* alloc_w = new (GetAllocator()) HNewArray(zero_const, eighty_const, 0, 0);
1124 HInstruction* pre_header_goto = new (GetAllocator()) HGoto();
1125 loop_pre_header->AddInstruction(alloc_w);
1126 loop_pre_header->AddInstruction(pre_header_goto);
1127 // environment
1128 ManuallyBuildEnvFor(alloc_w, {});
1129
1130 // loop-start
1131 HPhi* i_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
1132 HPhi* t_phi = new (GetAllocator()) HPhi(GetAllocator(), 1, 0, DataType::Type::kInt32);
1133 HInstruction* suspend = new (GetAllocator()) HSuspendCheck();
1134 HInstruction* i_cmp_top = new (GetAllocator()) HGreaterThanOrEqual(i_phi, eighty_const);
1135 HInstruction* loop_start_branch = new (GetAllocator()) HIf(i_cmp_top);
1136 loop_entry->AddPhi(i_phi);
1137 loop_entry->AddPhi(t_phi);
1138 loop_entry->AddInstruction(suspend);
1139 loop_entry->AddInstruction(i_cmp_top);
1140 loop_entry->AddInstruction(loop_start_branch);
1141 CHECK_EQ(loop_entry->GetSuccessors().size(), 2u);
1142 if (loop_entry->GetNormalSuccessors()[1] != loop_body) {
1143 loop_entry->SwapSuccessors();
1144 }
1145 CHECK_EQ(loop_entry->GetPredecessors().size(), 2u);
1146 if (loop_entry->GetPredecessors()[0] != loop_pre_header) {
1147 loop_entry->SwapPredecessors();
1148 }
1149 i_phi->AddInput(one_const);
1150 t_phi->AddInput(zero_const);
1151
1152 // environment
1153 ManuallyBuildEnvFor(suspend, { alloc_w, i_phi, t_phi });
1154
1155 // BODY
1156 HInstruction* last_i = new (GetAllocator()) HSub(DataType::Type::kInt32, i_phi, one_const);
1157 HInstruction* last_get =
1158 new (GetAllocator()) HArrayGet(alloc_w, last_i, DataType::Type::kInt32, 0);
1159 HInvoke* body_value = MakeInvoke(DataType::Type::kInt32, { last_get, one_const });
1160 HInstruction* body_set =
1161 new (GetAllocator()) HArraySet(alloc_w, i_phi, body_value, DataType::Type::kInt32, 0);
1162 HInstruction* body_get =
1163 new (GetAllocator()) HArrayGet(alloc_w, i_phi, DataType::Type::kInt32, 0);
1164 HInvoke* t_next = MakeInvoke(DataType::Type::kInt32, { body_get, t_phi });
1165 HInstruction* i_next = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_phi, one_const);
1166 HInstruction* body_goto = new (GetAllocator()) HGoto();
1167 loop_body->AddInstruction(last_i);
1168 loop_body->AddInstruction(last_get);
1169 loop_body->AddInstruction(body_value);
1170 loop_body->AddInstruction(body_set);
1171 loop_body->AddInstruction(body_get);
1172 loop_body->AddInstruction(t_next);
1173 loop_body->AddInstruction(i_next);
1174 loop_body->AddInstruction(body_goto);
1175 body_value->CopyEnvironmentFrom(suspend->GetEnvironment());
1176
1177 i_phi->AddInput(i_next);
1178 t_phi->AddInput(t_next);
1179 t_next->CopyEnvironmentFrom(suspend->GetEnvironment());
1180
1181 // loop-post
1182 HInstruction* return_inst = new (GetAllocator()) HReturn(t_phi);
1183 loop_post->AddInstruction(return_inst);
1184
1185 // exit
1186 SetupExit(exit);
1187
1188 graph_->ClearDominanceInformation();
1189 graph_->ClearLoopInformation();
1190 PerformLSE();
1191
1192 // TODO Technically this is optimizable. LSE just needs to add phis to keep
1193 // track of the last `N` values set where `N` is how many locations we can go
1194 // back into the array.
1195 if (IsRemoved(last_get)) {
1196 // If we were able to remove the previous read the entire array should be removable.
1197 EXPECT_INS_REMOVED(body_set);
1198 EXPECT_INS_REMOVED(alloc_w);
1199 } else {
1200 // This is the branch we actually take for now. If we rely on being able to
1201 // read the array we'd better remember to write to it as well.
1202 EXPECT_INS_RETAINED(body_set);
1203 }
1204 // The last 'get' should always be removable.
1205 EXPECT_INS_REMOVED(body_get);
1206 }
1207
1208 // void DO_CAL2() {
1209 // int i = 1;
1210 // int[] w = new int[80];
1211 // int t = 0;
1212 // while (i < 80) {
1213 // w[i] = PLEASE_INTERLEAVE(w[i - 1], 1) // <-- removed
1214 // t = PLEASE_SELECT(w[i], t);
1215 // w[i] = PLEASE_INTERLEAVE(w[i - 1], 1) // <-- removed
1216 // t = PLEASE_SELECT(w[i], t);
1217 // w[i] = PLEASE_INTERLEAVE(w[i - 1], 1) // <-- kept
1218 // t = PLEASE_SELECT(w[i], t);
1219 // i++;
1220 // }
1221 // return t;
1222 // }
TEST_F(LoadStoreEliminationTest,ArrayLoopOverlap2)1223 TEST_F(LoadStoreEliminationTest, ArrayLoopOverlap2) {
1224 ScopedObjectAccess soa(Thread::Current());
1225 VariableSizedHandleScope vshs(soa.Self());
1226 CreateGraph(&vshs);
1227 AdjacencyListGraph blocks(graph_,
1228 GetAllocator(),
1229 "entry",
1230 "exit",
1231 { { "entry", "loop_pre_header" },
1232 { "loop_pre_header", "loop_entry" },
1233 { "loop_entry", "loop_body" },
1234 { "loop_entry", "loop_post" },
1235 { "loop_body", "loop_entry" },
1236 { "loop_post", "exit" } });
1237 #define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1238 GET_BLOCK(entry);
1239 GET_BLOCK(loop_pre_header);
1240 GET_BLOCK(loop_entry);
1241 GET_BLOCK(loop_body);
1242 GET_BLOCK(loop_post);
1243 GET_BLOCK(exit);
1244 #undef GET_BLOCK
1245
1246 HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
1247 HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
1248 HInstruction* eighty_const = graph_->GetConstant(DataType::Type::kInt32, 80);
1249 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1250 entry->AddInstruction(entry_goto);
1251
1252 HInstruction* alloc_w = new (GetAllocator()) HNewArray(zero_const, eighty_const, 0, 0);
1253 HInstruction* pre_header_goto = new (GetAllocator()) HGoto();
1254 loop_pre_header->AddInstruction(alloc_w);
1255 loop_pre_header->AddInstruction(pre_header_goto);
1256 // environment
1257 ManuallyBuildEnvFor(alloc_w, {});
1258
1259 // loop-start
1260 HPhi* i_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
1261 HPhi* t_phi = new (GetAllocator()) HPhi(GetAllocator(), 1, 0, DataType::Type::kInt32);
1262 HInstruction* suspend = new (GetAllocator()) HSuspendCheck();
1263 HInstruction* i_cmp_top = new (GetAllocator()) HGreaterThanOrEqual(i_phi, eighty_const);
1264 HInstruction* loop_start_branch = new (GetAllocator()) HIf(i_cmp_top);
1265 loop_entry->AddPhi(i_phi);
1266 loop_entry->AddPhi(t_phi);
1267 loop_entry->AddInstruction(suspend);
1268 loop_entry->AddInstruction(i_cmp_top);
1269 loop_entry->AddInstruction(loop_start_branch);
1270 CHECK_EQ(loop_entry->GetSuccessors().size(), 2u);
1271 if (loop_entry->GetNormalSuccessors()[1] != loop_body) {
1272 loop_entry->SwapSuccessors();
1273 }
1274 CHECK_EQ(loop_entry->GetPredecessors().size(), 2u);
1275 if (loop_entry->GetPredecessors()[0] != loop_pre_header) {
1276 loop_entry->SwapPredecessors();
1277 }
1278 i_phi->AddInput(one_const);
1279 t_phi->AddInput(zero_const);
1280
1281 // environment
1282 ManuallyBuildEnvFor(suspend, { alloc_w, i_phi, t_phi });
1283
1284 // BODY
1285 HInstruction* last_i = new (GetAllocator()) HSub(DataType::Type::kInt32, i_phi, one_const);
1286 HInstruction *last_get_1, *last_get_2, *last_get_3;
1287 HInstruction *body_value_1, *body_value_2, *body_value_3;
1288 HInstruction *body_set_1, *body_set_2, *body_set_3;
1289 HInstruction *body_get_1, *body_get_2, *body_get_3;
1290 HInstruction *t_next_1, *t_next_2, *t_next_3;
1291 auto make_instructions = [&](HInstruction* last_t_value) {
1292 HInstruction* last_get =
1293 new (GetAllocator()) HArrayGet(alloc_w, last_i, DataType::Type::kInt32, 0);
1294 HInvoke* body_value = MakeInvoke(DataType::Type::kInt32, { last_get, one_const });
1295 HInstruction* body_set =
1296 new (GetAllocator()) HArraySet(alloc_w, i_phi, body_value, DataType::Type::kInt32, 0);
1297 HInstruction* body_get =
1298 new (GetAllocator()) HArrayGet(alloc_w, i_phi, DataType::Type::kInt32, 0);
1299 HInvoke* t_next = MakeInvoke(DataType::Type::kInt32, { body_get, last_t_value });
1300 loop_body->AddInstruction(last_get);
1301 loop_body->AddInstruction(body_value);
1302 loop_body->AddInstruction(body_set);
1303 loop_body->AddInstruction(body_get);
1304 loop_body->AddInstruction(t_next);
1305 return std::make_tuple(last_get, body_value, body_set, body_get, t_next);
1306 };
1307 std::tie(last_get_1, body_value_1, body_set_1, body_get_1, t_next_1) = make_instructions(t_phi);
1308 std::tie(last_get_2, body_value_2, body_set_2, body_get_2, t_next_2) =
1309 make_instructions(t_next_1);
1310 std::tie(last_get_3, body_value_3, body_set_3, body_get_3, t_next_3) =
1311 make_instructions(t_next_2);
1312 HInstruction* i_next = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_phi, one_const);
1313 HInstruction* body_goto = new (GetAllocator()) HGoto();
1314 loop_body->InsertInstructionBefore(last_i, last_get_1);
1315 loop_body->AddInstruction(i_next);
1316 loop_body->AddInstruction(body_goto);
1317 body_value_1->CopyEnvironmentFrom(suspend->GetEnvironment());
1318 body_value_2->CopyEnvironmentFrom(suspend->GetEnvironment());
1319 body_value_3->CopyEnvironmentFrom(suspend->GetEnvironment());
1320
1321 i_phi->AddInput(i_next);
1322 t_phi->AddInput(t_next_3);
1323 t_next_1->CopyEnvironmentFrom(suspend->GetEnvironment());
1324 t_next_2->CopyEnvironmentFrom(suspend->GetEnvironment());
1325 t_next_3->CopyEnvironmentFrom(suspend->GetEnvironment());
1326
1327 // loop-post
1328 HInstruction* return_inst = new (GetAllocator()) HReturn(t_phi);
1329 loop_post->AddInstruction(return_inst);
1330
1331 // exit
1332 SetupExit(exit);
1333
1334 graph_->ClearDominanceInformation();
1335 graph_->ClearLoopInformation();
1336 PerformLSE();
1337
1338 // TODO Technically this is optimizable. LSE just needs to add phis to keep
1339 // track of the last `N` values set where `N` is how many locations we can go
1340 // back into the array.
1341 if (IsRemoved(last_get_1)) {
1342 // If we were able to remove the previous read the entire array should be removable.
1343 EXPECT_INS_REMOVED(body_set_1);
1344 EXPECT_INS_REMOVED(body_set_2);
1345 EXPECT_INS_REMOVED(body_set_3);
1346 EXPECT_INS_REMOVED(last_get_1);
1347 EXPECT_INS_REMOVED(last_get_2);
1348 EXPECT_INS_REMOVED(alloc_w);
1349 } else {
1350 // This is the branch we actually take for now. If we rely on being able to
1351 // read the array we'd better remember to write to it as well.
1352 EXPECT_INS_RETAINED(body_set_3);
1353 }
1354 // The last 'get' should always be removable.
1355 EXPECT_INS_REMOVED(body_get_1);
1356 EXPECT_INS_REMOVED(body_get_2);
1357 EXPECT_INS_REMOVED(body_get_3);
1358 // shadowed writes should always be removed
1359 EXPECT_INS_REMOVED(body_set_1);
1360 EXPECT_INS_REMOVED(body_set_2);
1361 }
1362
TEST_F(LoadStoreEliminationTest,ArrayNonLoopPhi)1363 TEST_F(LoadStoreEliminationTest, ArrayNonLoopPhi) {
1364 ScopedObjectAccess soa(Thread::Current());
1365 VariableSizedHandleScope vshs(soa.Self());
1366 CreateGraph(&vshs);
1367 AdjacencyListGraph blocks(graph_,
1368 GetAllocator(),
1369 "entry",
1370 "exit",
1371 { { "entry", "start" },
1372 { "start", "left" },
1373 { "start", "right" },
1374 { "left", "ret" },
1375 { "right", "ret" },
1376 { "ret", "exit" } });
1377 #define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1378 GET_BLOCK(entry);
1379 GET_BLOCK(start);
1380 GET_BLOCK(left);
1381 GET_BLOCK(right);
1382 GET_BLOCK(ret);
1383 GET_BLOCK(exit);
1384 #undef GET_BLOCK
1385
1386 HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
1387 HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
1388 HInstruction* two_const = graph_->GetConstant(DataType::Type::kInt32, 2);
1389 HInstruction* param = MakeParam(DataType::Type::kBool);
1390
1391 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1392 entry->AddInstruction(entry_goto);
1393
1394 HInstruction* alloc_w = new (GetAllocator()) HNewArray(zero_const, two_const, 0, 0);
1395 HInstruction* branch = new (GetAllocator()) HIf(param);
1396 start->AddInstruction(alloc_w);
1397 start->AddInstruction(branch);
1398 // environment
1399 ManuallyBuildEnvFor(alloc_w, {});
1400
1401 // left
1402 HInvoke* left_value = MakeInvoke(DataType::Type::kInt32, { zero_const });
1403 HInstruction* left_set_1 =
1404 new (GetAllocator()) HArraySet(alloc_w, zero_const, left_value, DataType::Type::kInt32, 0);
1405 HInstruction* left_set_2 =
1406 new (GetAllocator()) HArraySet(alloc_w, one_const, zero_const, DataType::Type::kInt32, 0);
1407 HInstruction* left_goto = new (GetAllocator()) HGoto();
1408 left->AddInstruction(left_value);
1409 left->AddInstruction(left_set_1);
1410 left->AddInstruction(left_set_2);
1411 left->AddInstruction(left_goto);
1412 ManuallyBuildEnvFor(left_value, { alloc_w });
1413
1414 // right
1415 HInvoke* right_value = MakeInvoke(DataType::Type::kInt32, { one_const });
1416 HInstruction* right_set_1 =
1417 new (GetAllocator()) HArraySet(alloc_w, zero_const, right_value, DataType::Type::kInt32, 0);
1418 HInstruction* right_set_2 =
1419 new (GetAllocator()) HArraySet(alloc_w, one_const, zero_const, DataType::Type::kInt32, 0);
1420 HInstruction* right_goto = new (GetAllocator()) HGoto();
1421 right->AddInstruction(right_value);
1422 right->AddInstruction(right_set_1);
1423 right->AddInstruction(right_set_2);
1424 right->AddInstruction(right_goto);
1425 ManuallyBuildEnvFor(right_value, { alloc_w });
1426
1427 // ret
1428 HInstruction* read_1 =
1429 new (GetAllocator()) HArrayGet(alloc_w, zero_const, DataType::Type::kInt32, 0);
1430 HInstruction* read_2 =
1431 new (GetAllocator()) HArrayGet(alloc_w, one_const, DataType::Type::kInt32, 0);
1432 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, read_1, read_2);
1433 HInstruction* return_inst = new (GetAllocator()) HReturn(add);
1434 ret->AddInstruction(read_1);
1435 ret->AddInstruction(read_2);
1436 ret->AddInstruction(add);
1437 ret->AddInstruction(return_inst);
1438
1439 // exit
1440 SetupExit(exit);
1441
1442 graph_->ClearDominanceInformation();
1443 graph_->ClearLoopInformation();
1444 PerformLSE();
1445
1446 EXPECT_INS_REMOVED(read_1);
1447 EXPECT_INS_REMOVED(read_2);
1448 EXPECT_INS_REMOVED(left_set_1);
1449 EXPECT_INS_REMOVED(left_set_2);
1450 EXPECT_INS_REMOVED(right_set_1);
1451 EXPECT_INS_REMOVED(right_set_2);
1452 EXPECT_INS_REMOVED(alloc_w);
1453
1454 EXPECT_INS_RETAINED(left_value);
1455 EXPECT_INS_RETAINED(right_value);
1456 }
1457
TEST_F(LoadStoreEliminationTest,ArrayMergeDefault)1458 TEST_F(LoadStoreEliminationTest, ArrayMergeDefault) {
1459 ScopedObjectAccess soa(Thread::Current());
1460 VariableSizedHandleScope vshs(soa.Self());
1461 CreateGraph(&vshs);
1462 AdjacencyListGraph blocks(graph_,
1463 GetAllocator(),
1464 "entry",
1465 "exit",
1466 { { "entry", "start" },
1467 { "start", "left" },
1468 { "start", "right" },
1469 { "left", "ret" },
1470 { "right", "ret" },
1471 { "ret", "exit" } });
1472 #define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1473 GET_BLOCK(entry);
1474 GET_BLOCK(start);
1475 GET_BLOCK(left);
1476 GET_BLOCK(right);
1477 GET_BLOCK(ret);
1478 GET_BLOCK(exit);
1479 #undef GET_BLOCK
1480
1481 HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
1482 HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
1483 HInstruction* two_const = graph_->GetConstant(DataType::Type::kInt32, 2);
1484 HInstruction* param = MakeParam(DataType::Type::kBool);
1485 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1486
1487 entry->AddInstruction(entry_goto);
1488
1489 HInstruction* alloc_w = new (GetAllocator()) HNewArray(zero_const, two_const, 0, 0);
1490 HInstruction* branch = new (GetAllocator()) HIf(param);
1491 start->AddInstruction(alloc_w);
1492 start->AddInstruction(branch);
1493 // environment
1494 ArenaVector<HInstruction*> alloc_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1495 ManuallyBuildEnvFor(alloc_w, {});
1496
1497 // left
1498 HInstruction* left_set_1 =
1499 new (GetAllocator()) HArraySet(alloc_w, zero_const, one_const, DataType::Type::kInt32, 0);
1500 HInstruction* left_set_2 =
1501 new (GetAllocator()) HArraySet(alloc_w, zero_const, zero_const, DataType::Type::kInt32, 0);
1502 HInstruction* left_goto = new (GetAllocator()) HGoto();
1503 left->AddInstruction(left_set_1);
1504 left->AddInstruction(left_set_2);
1505 left->AddInstruction(left_goto);
1506
1507 // right
1508 HInstruction* right_set_1 =
1509 new (GetAllocator()) HArraySet(alloc_w, one_const, one_const, DataType::Type::kInt32, 0);
1510 HInstruction* right_set_2 =
1511 new (GetAllocator()) HArraySet(alloc_w, one_const, zero_const, DataType::Type::kInt32, 0);
1512 HInstruction* right_goto = new (GetAllocator()) HGoto();
1513 right->AddInstruction(right_set_1);
1514 right->AddInstruction(right_set_2);
1515 right->AddInstruction(right_goto);
1516
1517 // ret
1518 HInstruction* read_1 =
1519 new (GetAllocator()) HArrayGet(alloc_w, zero_const, DataType::Type::kInt32, 0);
1520 HInstruction* read_2 =
1521 new (GetAllocator()) HArrayGet(alloc_w, one_const, DataType::Type::kInt32, 0);
1522 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, read_1, read_2);
1523 HInstruction* return_inst = new (GetAllocator()) HReturn(add);
1524 ret->AddInstruction(read_1);
1525 ret->AddInstruction(read_2);
1526 ret->AddInstruction(add);
1527 ret->AddInstruction(return_inst);
1528
1529 // exit
1530 SetupExit(exit);
1531
1532 graph_->ClearDominanceInformation();
1533 graph_->ClearLoopInformation();
1534 PerformLSE();
1535
1536 EXPECT_INS_REMOVED(read_1);
1537 EXPECT_INS_REMOVED(read_2);
1538 EXPECT_INS_REMOVED(left_set_1);
1539 EXPECT_INS_REMOVED(left_set_2);
1540 EXPECT_INS_REMOVED(right_set_1);
1541 EXPECT_INS_REMOVED(right_set_2);
1542 EXPECT_INS_REMOVED(alloc_w);
1543 }
1544
1545 // Regression test for b/187487955.
1546 // We previusly failed to consider aliasing between an array location
1547 // with index `idx` defined in the loop (such as a loop Phi) and another
1548 // array location with index `idx + constant`. This could have led to
1549 // replacing the load with, for example, the default value 0.
TEST_F(LoadStoreEliminationTest,ArrayLoopAliasing1)1550 TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing1) {
1551 ScopedObjectAccess soa(Thread::Current());
1552 VariableSizedHandleScope vshs(soa.Self());
1553 CreateGraph(&vshs);
1554 AdjacencyListGraph blocks(graph_,
1555 GetAllocator(),
1556 "entry",
1557 "exit",
1558 { { "entry", "preheader" },
1559 { "preheader", "loop" },
1560 { "loop", "body" },
1561 { "body", "loop" },
1562 { "loop", "ret" },
1563 { "ret", "exit" } });
1564 #define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1565 GET_BLOCK(entry);
1566 GET_BLOCK(preheader);
1567 GET_BLOCK(loop);
1568 GET_BLOCK(body);
1569 GET_BLOCK(ret);
1570 GET_BLOCK(exit);
1571 #undef GET_BLOCK
1572 HInstruction* n = MakeParam(DataType::Type::kInt32);
1573 HInstruction* c0 = graph_->GetIntConstant(0);
1574 HInstruction* c1 = graph_->GetIntConstant(1);
1575
1576 // entry
1577 HInstruction* cls = MakeClassLoad();
1578 HInstruction* array = new (GetAllocator()) HNewArray(
1579 cls, n, /*dex_pc=*/ 0u, DataType::SizeShift(DataType::Type::kInt32));
1580 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1581 entry->AddInstruction(cls);
1582 entry->AddInstruction(array);
1583 entry->AddInstruction(entry_goto);
1584 ManuallyBuildEnvFor(cls, {});
1585 ManuallyBuildEnvFor(array, {});
1586
1587 HInstruction* preheader_goto = new (GetAllocator()) HGoto();
1588 preheader->AddInstruction(preheader_goto);
1589
1590 // loop
1591 HPhi* i_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
1592 HInstruction* loop_suspend_check = new (GetAllocator()) HSuspendCheck();
1593 HInstruction* loop_cond = new (GetAllocator()) HLessThan(i_phi, n);
1594 HIf* loop_if = new (GetAllocator()) HIf(loop_cond);
1595 loop->AddPhi(i_phi);
1596 loop->AddInstruction(loop_suspend_check);
1597 loop->AddInstruction(loop_cond);
1598 loop->AddInstruction(loop_if);
1599 CHECK(loop_if->IfTrueSuccessor() == body);
1600 ManuallyBuildEnvFor(loop_suspend_check, {});
1601
1602 // body
1603 HInstruction* body_set =
1604 new (GetAllocator()) HArraySet(array, i_phi, i_phi, DataType::Type::kInt32, /*dex_pc=*/ 0u);
1605 HInstruction* body_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_phi, c1);
1606 HInstruction* body_goto = new (GetAllocator()) HGoto();
1607 body->AddInstruction(body_set);
1608 body->AddInstruction(body_add);
1609 body->AddInstruction(body_goto);
1610
1611 // i_phi inputs
1612 i_phi->AddInput(c0);
1613 i_phi->AddInput(body_add);
1614
1615 // ret
1616 HInstruction* ret_sub = new (GetAllocator()) HSub(DataType::Type::kInt32, i_phi, c1);
1617 HInstruction* ret_get =
1618 new (GetAllocator()) HArrayGet(array, ret_sub, DataType::Type::kInt32, /*dex_pc=*/ 0);
1619 HInstruction* ret_return = new (GetAllocator()) HReturn(ret_get);
1620 ret->AddInstruction(ret_sub);
1621 ret->AddInstruction(ret_get);
1622 ret->AddInstruction(ret_return);
1623
1624 // exit
1625 SetupExit(exit);
1626
1627 graph_->ClearDominanceInformation();
1628 graph_->ClearLoopInformation();
1629 PerformLSE();
1630
1631 EXPECT_INS_RETAINED(cls);
1632 EXPECT_INS_RETAINED(array);
1633 EXPECT_INS_RETAINED(body_set);
1634 EXPECT_INS_RETAINED(ret_get);
1635 }
1636
1637 // Regression test for b/187487955.
1638 // Similar to the `ArrayLoopAliasing1` test above but with additional load
1639 // that marks a loop Phi placeholder as kept which used to trigger a DCHECK().
1640 // There is also an LSE run-test for this but it relies on BCE eliminating
1641 // BoundsCheck instructions and adds extra code in loop body to avoid
1642 // loop unrolling. This gtest does not need to jump through those hoops
1643 // as we do not unnecessarily run those optimization passes.
TEST_F(LoadStoreEliminationTest,ArrayLoopAliasing2)1644 TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing2) {
1645 ScopedObjectAccess soa(Thread::Current());
1646 VariableSizedHandleScope vshs(soa.Self());
1647 CreateGraph(&vshs);
1648 AdjacencyListGraph blocks(graph_,
1649 GetAllocator(),
1650 "entry",
1651 "exit",
1652 { { "entry", "preheader" },
1653 { "preheader", "loop" },
1654 { "loop", "body" },
1655 { "body", "loop" },
1656 { "loop", "ret" },
1657 { "ret", "exit" } });
1658 #define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1659 GET_BLOCK(entry);
1660 GET_BLOCK(preheader);
1661 GET_BLOCK(loop);
1662 GET_BLOCK(body);
1663 GET_BLOCK(ret);
1664 GET_BLOCK(exit);
1665 #undef GET_BLOCK
1666 HInstruction* n = MakeParam(DataType::Type::kInt32);
1667 HInstruction* c0 = graph_->GetIntConstant(0);
1668 HInstruction* c1 = graph_->GetIntConstant(1);
1669
1670 // entry
1671 HInstruction* cls = MakeClassLoad();
1672 HInstruction* array = new (GetAllocator()) HNewArray(
1673 cls, n, /*dex_pc=*/ 0u, DataType::SizeShift(DataType::Type::kInt32));
1674 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1675 entry->AddInstruction(cls);
1676 entry->AddInstruction(array);
1677 entry->AddInstruction(entry_goto);
1678 ManuallyBuildEnvFor(cls, {});
1679 ManuallyBuildEnvFor(array, {});
1680
1681 HInstruction* preheader_goto = new (GetAllocator()) HGoto();
1682 preheader->AddInstruction(preheader_goto);
1683
1684 // loop
1685 HPhi* i_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
1686 HInstruction* loop_suspend_check = new (GetAllocator()) HSuspendCheck();
1687 HInstruction* loop_cond = new (GetAllocator()) HLessThan(i_phi, n);
1688 HIf* loop_if = new (GetAllocator()) HIf(loop_cond);
1689 loop->AddPhi(i_phi);
1690 loop->AddInstruction(loop_suspend_check);
1691 loop->AddInstruction(loop_cond);
1692 loop->AddInstruction(loop_if);
1693 CHECK(loop_if->IfTrueSuccessor() == body);
1694 ManuallyBuildEnvFor(loop_suspend_check, {});
1695
1696 // body
1697 HInstruction* body_set =
1698 new (GetAllocator()) HArraySet(array, i_phi, i_phi, DataType::Type::kInt32, /*dex_pc=*/ 0u);
1699 HInstruction* body_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_phi, c1);
1700 HInstruction* body_goto = new (GetAllocator()) HGoto();
1701 body->AddInstruction(body_set);
1702 body->AddInstruction(body_add);
1703 body->AddInstruction(body_goto);
1704
1705 // i_phi inputs
1706 i_phi->AddInput(c0);
1707 i_phi->AddInput(body_add);
1708
1709 // ret
1710 HInstruction* ret_sub = new (GetAllocator()) HSub(DataType::Type::kInt32, i_phi, c1);
1711 HInstruction* ret_get1 =
1712 new (GetAllocator()) HArrayGet(array, ret_sub, DataType::Type::kInt32, /*dex_pc=*/ 0);
1713 HInstruction* ret_get2 =
1714 new (GetAllocator()) HArrayGet(array, i_phi, DataType::Type::kInt32, /*dex_pc=*/ 0);
1715 HInstruction* ret_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, ret_get1, ret_get2);
1716 HInstruction* ret_return = new (GetAllocator()) HReturn(ret_add);
1717 ret->AddInstruction(ret_sub);
1718 ret->AddInstruction(ret_get1);
1719 ret->AddInstruction(ret_get2);
1720 ret->AddInstruction(ret_add);
1721 ret->AddInstruction(ret_return);
1722
1723 // exit
1724 SetupExit(exit);
1725
1726 graph_->ClearDominanceInformation();
1727 graph_->ClearLoopInformation();
1728 PerformLSE();
1729
1730 EXPECT_INS_RETAINED(cls);
1731 EXPECT_INS_RETAINED(array);
1732 EXPECT_INS_RETAINED(body_set);
1733 EXPECT_INS_RETAINED(ret_get1);
1734 EXPECT_INS_RETAINED(ret_get2);
1735 }
1736
1737 // // ENTRY
1738 // obj = new Obj();
1739 // // ALL should be kept
1740 // switch (parameter_value) {
1741 // case 1:
1742 // // Case1
1743 // obj.field = 1;
1744 // call_func(obj);
1745 // break;
1746 // case 2:
1747 // // Case2
1748 // obj.field = 2;
1749 // call_func(obj);
1750 // // We don't know what obj.field is now we aren't able to eliminate the read below!
1751 // break;
1752 // default:
1753 // // Case3
1754 // // TODO This only happens because of limitations on our LSE which is unable
1755 // // to materialize co-dependent loop and non-loop phis.
1756 // // Ideally we'd want to generate
1757 // // P1 = PHI[3, loop_val]
1758 // // while (test()) {
1759 // // if (test2()) { goto; } else { goto; }
1760 // // loop_val = [P1, 5]
1761 // // }
1762 // // Currently we aren't able to unfortunately.
1763 // obj.field = 3;
1764 // while (test()) {
1765 // if (test2()) { } else { obj.field = 5; }
1766 // }
1767 // break;
1768 // }
1769 // EXIT
1770 // return obj.field
TEST_F(LoadStoreEliminationTest,PartialUnknownMerge)1771 TEST_F(LoadStoreEliminationTest, PartialUnknownMerge) {
1772 CreateGraph();
1773 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1774 "exit",
1775 {{"entry", "bswitch"},
1776 {"bswitch", "case1"},
1777 {"bswitch", "case2"},
1778 {"bswitch", "case3"},
1779 {"case1", "breturn"},
1780 {"case2", "breturn"},
1781 {"case3", "loop_pre_header"},
1782 {"loop_pre_header", "loop_header"},
1783 {"loop_header", "loop_body"},
1784 {"loop_body", "loop_if_left"},
1785 {"loop_body", "loop_if_right"},
1786 {"loop_if_left", "loop_end"},
1787 {"loop_if_right", "loop_end"},
1788 {"loop_end", "loop_header"},
1789 {"loop_header", "breturn"},
1790 {"breturn", "exit"}}));
1791 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
1792 GET_BLOCK(entry);
1793 GET_BLOCK(bswitch);
1794 GET_BLOCK(exit);
1795 GET_BLOCK(breturn);
1796 GET_BLOCK(case1);
1797 GET_BLOCK(case2);
1798 GET_BLOCK(case3);
1799
1800 GET_BLOCK(loop_pre_header);
1801 GET_BLOCK(loop_header);
1802 GET_BLOCK(loop_body);
1803 GET_BLOCK(loop_if_left);
1804 GET_BLOCK(loop_if_right);
1805 GET_BLOCK(loop_end);
1806 #undef GET_BLOCK
1807 HInstruction* switch_val = MakeParam(DataType::Type::kInt32);
1808 HInstruction* c1 = graph_->GetIntConstant(1);
1809 HInstruction* c2 = graph_->GetIntConstant(2);
1810 HInstruction* c3 = graph_->GetIntConstant(3);
1811 HInstruction* c5 = graph_->GetIntConstant(5);
1812
1813 HInstruction* cls = MakeClassLoad();
1814 HInstruction* new_inst = MakeNewInstance(cls);
1815 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1816 entry->AddInstruction(cls);
1817 entry->AddInstruction(new_inst);
1818 entry->AddInstruction(entry_goto);
1819 ManuallyBuildEnvFor(cls, {});
1820 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
1821
1822 HInstruction* switch_inst = new (GetAllocator()) HPackedSwitch(0, 2, switch_val);
1823 bswitch->AddInstruction(switch_inst);
1824
1825 HInstruction* write_c1 = MakeIFieldSet(new_inst, c1, MemberOffset(32));
1826 HInstruction* call_c1 = MakeInvoke(DataType::Type::kVoid, { new_inst });
1827 HInstruction* goto_c1 = new (GetAllocator()) HGoto();
1828 case1->AddInstruction(write_c1);
1829 case1->AddInstruction(call_c1);
1830 case1->AddInstruction(goto_c1);
1831 call_c1->CopyEnvironmentFrom(cls->GetEnvironment());
1832
1833 HInstruction* write_c2 = MakeIFieldSet(new_inst, c2, MemberOffset(32));
1834 HInstruction* call_c2 = MakeInvoke(DataType::Type::kVoid, { new_inst });
1835 HInstruction* goto_c2 = new (GetAllocator()) HGoto();
1836 case2->AddInstruction(write_c2);
1837 case2->AddInstruction(call_c2);
1838 case2->AddInstruction(goto_c2);
1839 call_c2->CopyEnvironmentFrom(cls->GetEnvironment());
1840
1841 HInstruction* write_c3 = MakeIFieldSet(new_inst, c3, MemberOffset(32));
1842 HInstruction* goto_c3 = new (GetAllocator()) HGoto();
1843 case3->AddInstruction(write_c3);
1844 case3->AddInstruction(goto_c3);
1845
1846 HInstruction* goto_preheader = new (GetAllocator()) HGoto();
1847 loop_pre_header->AddInstruction(goto_preheader);
1848
1849 HInstruction* suspend_check_header = new (GetAllocator()) HSuspendCheck();
1850 HInstruction* call_loop_header = MakeInvoke(DataType::Type::kBool, {});
1851 HInstruction* if_loop_header = new (GetAllocator()) HIf(call_loop_header);
1852 loop_header->AddInstruction(suspend_check_header);
1853 loop_header->AddInstruction(call_loop_header);
1854 loop_header->AddInstruction(if_loop_header);
1855 call_loop_header->CopyEnvironmentFrom(cls->GetEnvironment());
1856 suspend_check_header->CopyEnvironmentFrom(cls->GetEnvironment());
1857
1858 HInstruction* call_loop_body = MakeInvoke(DataType::Type::kBool, {});
1859 HInstruction* if_loop_body = new (GetAllocator()) HIf(call_loop_body);
1860 loop_body->AddInstruction(call_loop_body);
1861 loop_body->AddInstruction(if_loop_body);
1862 call_loop_body->CopyEnvironmentFrom(cls->GetEnvironment());
1863
1864 HInstruction* goto_loop_left = new (GetAllocator()) HGoto();
1865 loop_if_left->AddInstruction(goto_loop_left);
1866
1867 HInstruction* write_loop_right = MakeIFieldSet(new_inst, c5, MemberOffset(32));
1868 HInstruction* goto_loop_right = new (GetAllocator()) HGoto();
1869 loop_if_right->AddInstruction(write_loop_right);
1870 loop_if_right->AddInstruction(goto_loop_right);
1871
1872 HInstruction* goto_loop_end = new (GetAllocator()) HGoto();
1873 loop_end->AddInstruction(goto_loop_end);
1874
1875 HInstruction* read_bottom = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
1876 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
1877 breturn->AddInstruction(read_bottom);
1878 breturn->AddInstruction(return_exit);
1879
1880 SetupExit(exit);
1881
1882 PerformLSE(blks);
1883
1884 EXPECT_INS_RETAINED(read_bottom);
1885 EXPECT_INS_RETAINED(write_c1);
1886 EXPECT_INS_RETAINED(write_c2);
1887 EXPECT_INS_RETAINED(write_c3);
1888 EXPECT_INS_RETAINED(write_loop_right);
1889 }
1890
1891 // // ENTRY
1892 // obj = new Obj();
1893 // if (parameter_value) {
1894 // // LEFT
1895 // obj.field = 1;
1896 // call_func(obj);
1897 // // We don't know what obj.field is now we aren't able to eliminate the read below!
1898 // } else {
1899 // // DO NOT ELIMINATE
1900 // obj.field = 2;
1901 // // RIGHT
1902 // }
1903 // EXIT
1904 // return obj.field
1905 // This test runs with partial LSE disabled.
TEST_F(LoadStoreEliminationTest,PartialLoadPreserved)1906 TEST_F(LoadStoreEliminationTest, PartialLoadPreserved) {
1907 ScopedObjectAccess soa(Thread::Current());
1908 VariableSizedHandleScope vshs(soa.Self());
1909 CreateGraph(&vshs);
1910 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1911 "exit_REAL",
1912 { { "entry", "left" },
1913 { "entry", "right" },
1914 { "left", "exit" },
1915 { "right", "exit" },
1916 { "exit", "exit_REAL" } }));
1917 HBasicBlock* entry = blks.Get("entry");
1918 HBasicBlock* left = blks.Get("left");
1919 HBasicBlock* right = blks.Get("right");
1920 HBasicBlock* exit = blks.Get("exit");
1921 HInstruction* bool_value = MakeParam(DataType::Type::kBool);
1922 HInstruction* c1 = graph_->GetIntConstant(1);
1923 HInstruction* c2 = graph_->GetIntConstant(2);
1924
1925 HInstruction* cls = MakeClassLoad();
1926 HInstruction* new_inst = MakeNewInstance(cls);
1927 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1928 entry->AddInstruction(cls);
1929 entry->AddInstruction(new_inst);
1930 entry->AddInstruction(if_inst);
1931 ManuallyBuildEnvFor(cls, {});
1932 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
1933
1934 HInstruction* write_left = MakeIFieldSet(new_inst, c1, MemberOffset(32));
1935 HInstruction* call_left = MakeInvoke(DataType::Type::kVoid, { new_inst });
1936 HInstruction* goto_left = new (GetAllocator()) HGoto();
1937 left->AddInstruction(write_left);
1938 left->AddInstruction(call_left);
1939 left->AddInstruction(goto_left);
1940 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
1941
1942 HInstruction* write_right = MakeIFieldSet(new_inst, c2, MemberOffset(32));
1943 HInstruction* goto_right = new (GetAllocator()) HGoto();
1944 right->AddInstruction(write_right);
1945 right->AddInstruction(goto_right);
1946
1947 HInstruction* read_bottom = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
1948 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
1949 exit->AddInstruction(read_bottom);
1950 exit->AddInstruction(return_exit);
1951
1952 PerformLSE(blks);
1953
1954 EXPECT_INS_RETAINED(read_bottom) << *read_bottom;
1955 EXPECT_INS_RETAINED(write_right) << *write_right;
1956 }
1957
1958 // // ENTRY
1959 // obj = new Obj();
1960 // if (parameter_value) {
1961 // // LEFT
1962 // obj.field = 1;
1963 // call_func(obj);
1964 // // We don't know what obj.field is now we aren't able to eliminate the read below!
1965 // } else {
1966 // // DO NOT ELIMINATE
1967 // if (param2) {
1968 // obj.field = 2;
1969 // } else {
1970 // obj.field = 3;
1971 // }
1972 // // RIGHT
1973 // }
1974 // EXIT
1975 // return obj.field
1976 // NB This test is for non-partial LSE flow. Normally the obj.field writes will be removed
TEST_F(LoadStoreEliminationTest,PartialLoadPreserved2)1977 TEST_F(LoadStoreEliminationTest, PartialLoadPreserved2) {
1978 ScopedObjectAccess soa(Thread::Current());
1979 VariableSizedHandleScope vshs(soa.Self());
1980 CreateGraph(&vshs);
1981 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1982 "exit_REAL",
1983 { { "entry", "left" },
1984 { "entry", "right_start" },
1985 { "left", "exit" },
1986 { "right_start", "right_first" },
1987 { "right_start", "right_second" },
1988 { "right_first", "right_end" },
1989 { "right_second", "right_end" },
1990 { "right_end", "exit" },
1991 { "exit", "exit_REAL" } }));
1992 HBasicBlock* entry = blks.Get("entry");
1993 HBasicBlock* left = blks.Get("left");
1994 HBasicBlock* right_start = blks.Get("right_start");
1995 HBasicBlock* right_first = blks.Get("right_first");
1996 HBasicBlock* right_second = blks.Get("right_second");
1997 HBasicBlock* right_end = blks.Get("right_end");
1998 HBasicBlock* exit = blks.Get("exit");
1999 HInstruction* bool_value = MakeParam(DataType::Type::kBool);
2000 HInstruction* bool_value_2 = MakeParam(DataType::Type::kBool);
2001 HInstruction* c1 = graph_->GetIntConstant(1);
2002 HInstruction* c2 = graph_->GetIntConstant(2);
2003 HInstruction* c3 = graph_->GetIntConstant(3);
2004
2005 HInstruction* cls = MakeClassLoad();
2006 HInstruction* new_inst = MakeNewInstance(cls);
2007 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2008 entry->AddInstruction(cls);
2009 entry->AddInstruction(new_inst);
2010 entry->AddInstruction(if_inst);
2011 ManuallyBuildEnvFor(cls, {});
2012 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2013
2014 HInstruction* write_left = MakeIFieldSet(new_inst, c1, MemberOffset(32));
2015 HInstruction* call_left = MakeInvoke(DataType::Type::kVoid, { new_inst });
2016 HInstruction* goto_left = new (GetAllocator()) HGoto();
2017 left->AddInstruction(write_left);
2018 left->AddInstruction(call_left);
2019 left->AddInstruction(goto_left);
2020 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2021
2022 HInstruction* right_if = new (GetAllocator()) HIf(bool_value_2);
2023 right_start->AddInstruction(right_if);
2024
2025 HInstruction* write_right_first = MakeIFieldSet(new_inst, c2, MemberOffset(32));
2026 HInstruction* goto_right_first = new (GetAllocator()) HGoto();
2027 right_first->AddInstruction(write_right_first);
2028 right_first->AddInstruction(goto_right_first);
2029
2030 HInstruction* write_right_second = MakeIFieldSet(new_inst, c3, MemberOffset(32));
2031 HInstruction* goto_right_second = new (GetAllocator()) HGoto();
2032 right_second->AddInstruction(write_right_second);
2033 right_second->AddInstruction(goto_right_second);
2034
2035 HInstruction* goto_right_end = new (GetAllocator()) HGoto();
2036 right_end->AddInstruction(goto_right_end);
2037
2038 HInstruction* read_bottom = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
2039 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
2040 exit->AddInstruction(read_bottom);
2041 exit->AddInstruction(return_exit);
2042
2043 PerformLSE(blks);
2044
2045 EXPECT_INS_RETAINED(read_bottom);
2046 EXPECT_INS_RETAINED(write_right_first);
2047 EXPECT_INS_RETAINED(write_right_second);
2048 }
2049
2050 // // ENTRY
2051 // obj = new Obj();
2052 // if (parameter_value) {
2053 // // LEFT
2054 // // DO NOT ELIMINATE
2055 // obj.field = 1;
2056 // while (true) {
2057 // bool esc = escape(obj);
2058 // if (esc) break;
2059 // // DO NOT ELIMINATE
2060 // obj.field = 3;
2061 // }
2062 // } else {
2063 // // RIGHT
2064 // // DO NOT ELIMINATE
2065 // obj.field = 2;
2066 // }
2067 // // DO NOT ELIMINATE
2068 // return obj.field;
2069 // EXIT
TEST_F(LoadStoreEliminationTest,PartialLoadPreserved3)2070 TEST_F(LoadStoreEliminationTest, PartialLoadPreserved3) {
2071 ScopedObjectAccess soa(Thread::Current());
2072 VariableSizedHandleScope vshs(soa.Self());
2073 CreateGraph(&vshs);
2074 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2075 "exit",
2076 {{"entry", "entry_post"},
2077 {"entry_post", "right"},
2078 {"right", "return_block"},
2079 {"entry_post", "left_pre"},
2080 {"left_pre", "left_loop"},
2081 {"left_loop", "left_loop_post"},
2082 {"left_loop_post", "left_loop"},
2083 {"left_loop", "return_block"},
2084 {"return_block", "exit"}}));
2085 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2086 GET_BLOCK(entry);
2087 GET_BLOCK(entry_post);
2088 GET_BLOCK(exit);
2089 GET_BLOCK(return_block);
2090 GET_BLOCK(left_pre);
2091 GET_BLOCK(left_loop);
2092 GET_BLOCK(left_loop_post);
2093 GET_BLOCK(right);
2094 #undef GET_BLOCK
2095 // Left-loops first successor is the break.
2096 if (left_loop->GetSuccessors()[0] != return_block) {
2097 left_loop->SwapSuccessors();
2098 }
2099 HInstruction* bool_value = MakeParam(DataType::Type::kBool);
2100 HInstruction* c1 = graph_->GetIntConstant(1);
2101 HInstruction* c2 = graph_->GetIntConstant(2);
2102 HInstruction* c3 = graph_->GetIntConstant(3);
2103
2104 HInstruction* cls = MakeClassLoad();
2105 HInstruction* new_inst = MakeNewInstance(cls);
2106 HInstruction* goto_entry = new (GetAllocator()) HGoto();
2107 entry->AddInstruction(cls);
2108 entry->AddInstruction(new_inst);
2109 entry->AddInstruction(goto_entry);
2110 ManuallyBuildEnvFor(cls, {});
2111 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2112
2113 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2114 entry_post->AddInstruction(if_inst);
2115
2116 HInstruction* write_left_pre = MakeIFieldSet(new_inst, c1, MemberOffset(32));
2117 HInstruction* goto_left_pre = new (GetAllocator()) HGoto();
2118 left_pre->AddInstruction(write_left_pre);
2119 left_pre->AddInstruction(goto_left_pre);
2120
2121 HInstruction* suspend_left_loop = new (GetAllocator()) HSuspendCheck();
2122 HInstruction* call_left_loop = MakeInvoke(DataType::Type::kBool, {new_inst});
2123 HInstruction* if_left_loop = new (GetAllocator()) HIf(call_left_loop);
2124 left_loop->AddInstruction(suspend_left_loop);
2125 left_loop->AddInstruction(call_left_loop);
2126 left_loop->AddInstruction(if_left_loop);
2127 suspend_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
2128 call_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
2129
2130 HInstruction* write_left_loop = MakeIFieldSet(new_inst, c3, MemberOffset(32));
2131 HInstruction* goto_left_loop = new (GetAllocator()) HGoto();
2132 left_loop_post->AddInstruction(write_left_loop);
2133 left_loop_post->AddInstruction(goto_left_loop);
2134
2135 HInstruction* write_right = MakeIFieldSet(new_inst, c2, MemberOffset(32));
2136 HInstruction* goto_right = new (GetAllocator()) HGoto();
2137 right->AddInstruction(write_right);
2138 right->AddInstruction(goto_right);
2139
2140 HInstruction* read_return = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
2141 HInstruction* return_final = new (GetAllocator()) HReturn(read_return);
2142 return_block->AddInstruction(read_return);
2143 return_block->AddInstruction(return_final);
2144
2145 SetupExit(exit);
2146
2147 PerformLSE(blks);
2148
2149 EXPECT_INS_RETAINED(write_left_pre) << *write_left_pre;
2150 EXPECT_INS_RETAINED(read_return) << *read_return;
2151 EXPECT_INS_RETAINED(write_right) << *write_right;
2152 EXPECT_INS_RETAINED(write_left_loop) << *write_left_loop;
2153 EXPECT_INS_RETAINED(call_left_loop) << *call_left_loop;
2154 }
2155
2156 // // ENTRY
2157 // obj = new Obj();
2158 // if (parameter_value) {
2159 // // LEFT
2160 // // ELIMINATE (not visible since always overridden by obj.field = 3)
2161 // obj.field = 1;
2162 // while (true) {
2163 // bool stop = should_stop();
2164 // // DO NOT ELIMINATE (visible by read at end)
2165 // obj.field = 3;
2166 // if (stop) break;
2167 // }
2168 // } else {
2169 // // RIGHT
2170 // // DO NOT ELIMINATE
2171 // obj.field = 2;
2172 // escape(obj);
2173 // }
2174 // // DO NOT ELIMINATE
2175 // return obj.field;
2176 // EXIT
2177 // Disabled due to b/205813546.
TEST_F(LoadStoreEliminationTest,DISABLED_PartialLoadPreserved4)2178 TEST_F(LoadStoreEliminationTest, DISABLED_PartialLoadPreserved4) {
2179 ScopedObjectAccess soa(Thread::Current());
2180 VariableSizedHandleScope vshs(soa.Self());
2181 CreateGraph(&vshs);
2182 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2183 "exit",
2184 {{"entry", "entry_post"},
2185 {"entry_post", "right"},
2186 {"right", "return_block"},
2187 {"entry_post", "left_pre"},
2188 {"left_pre", "left_loop"},
2189 {"left_loop", "left_loop"},
2190 {"left_loop", "return_block"},
2191 {"return_block", "exit"}}));
2192 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2193 GET_BLOCK(entry);
2194 GET_BLOCK(entry_post);
2195 GET_BLOCK(exit);
2196 GET_BLOCK(return_block);
2197 GET_BLOCK(left_pre);
2198 GET_BLOCK(left_loop);
2199 GET_BLOCK(right);
2200 #undef GET_BLOCK
2201 // Left-loops first successor is the break.
2202 if (left_loop->GetSuccessors()[0] != return_block) {
2203 left_loop->SwapSuccessors();
2204 }
2205 HInstruction* bool_value = MakeParam(DataType::Type::kBool);
2206 HInstruction* c1 = graph_->GetIntConstant(1);
2207 HInstruction* c2 = graph_->GetIntConstant(2);
2208 HInstruction* c3 = graph_->GetIntConstant(3);
2209
2210 HInstruction* cls = MakeClassLoad();
2211 HInstruction* new_inst = MakeNewInstance(cls);
2212 HInstruction* goto_entry = new (GetAllocator()) HGoto();
2213 entry->AddInstruction(cls);
2214 entry->AddInstruction(new_inst);
2215 entry->AddInstruction(goto_entry);
2216 ManuallyBuildEnvFor(cls, {});
2217 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2218
2219 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2220 entry_post->AddInstruction(if_inst);
2221
2222 HInstruction* write_left_pre = MakeIFieldSet(new_inst, c1, MemberOffset(32));
2223 HInstruction* goto_left_pre = new (GetAllocator()) HGoto();
2224 left_pre->AddInstruction(write_left_pre);
2225 left_pre->AddInstruction(goto_left_pre);
2226
2227 HInstruction* suspend_left_loop = new (GetAllocator()) HSuspendCheck();
2228 HInstruction* call_left_loop = MakeInvoke(DataType::Type::kBool, {});
2229 HInstruction* write_left_loop = MakeIFieldSet(new_inst, c3, MemberOffset(32));
2230 HInstruction* if_left_loop = new (GetAllocator()) HIf(call_left_loop);
2231 left_loop->AddInstruction(suspend_left_loop);
2232 left_loop->AddInstruction(call_left_loop);
2233 left_loop->AddInstruction(write_left_loop);
2234 left_loop->AddInstruction(if_left_loop);
2235 suspend_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
2236 call_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
2237
2238 HInstruction* write_right = MakeIFieldSet(new_inst, c2, MemberOffset(32));
2239 HInstruction* call_right = MakeInvoke(DataType::Type::kBool, {new_inst});
2240 HInstruction* goto_right = new (GetAllocator()) HGoto();
2241 right->AddInstruction(write_right);
2242 right->AddInstruction(call_right);
2243 right->AddInstruction(goto_right);
2244 call_right->CopyEnvironmentFrom(cls->GetEnvironment());
2245
2246 HInstruction* read_return = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
2247 HInstruction* return_final = new (GetAllocator()) HReturn(read_return);
2248 return_block->AddInstruction(read_return);
2249 return_block->AddInstruction(return_final);
2250
2251 SetupExit(exit);
2252
2253 PerformLSE(blks);
2254
2255 EXPECT_INS_RETAINED(read_return);
2256 EXPECT_INS_RETAINED(write_right);
2257 EXPECT_INS_RETAINED(write_left_loop);
2258 EXPECT_INS_RETAINED(call_left_loop);
2259 EXPECT_INS_REMOVED(write_left_pre);
2260 EXPECT_INS_RETAINED(call_right);
2261 }
2262
2263 // // ENTRY
2264 // obj = new Obj();
2265 // if (parameter_value) {
2266 // // LEFT
2267 // // DO NOT ELIMINATE
2268 // escape(obj);
2269 // obj.field = 1;
2270 // // obj has already escaped so can't use field = 1 for value
2271 // noescape();
2272 // } else {
2273 // // RIGHT
2274 // // obj is needed for read since we don't know what the left value is
2275 // // DO NOT ELIMINATE
2276 // obj.field = 2;
2277 // noescape();
2278 // }
2279 // EXIT
2280 // ELIMINATE
2281 // return obj.field
TEST_F(LoadStoreEliminationTest,PartialLoadPreserved5)2282 TEST_F(LoadStoreEliminationTest, PartialLoadPreserved5) {
2283 ScopedObjectAccess soa(Thread::Current());
2284 VariableSizedHandleScope vshs(soa.Self());
2285 CreateGraph(&vshs);
2286 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2287 "exit",
2288 {{"entry", "left"},
2289 {"entry", "right"},
2290 {"left", "breturn"},
2291 {"right", "breturn"},
2292 {"breturn", "exit"}}));
2293 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2294 GET_BLOCK(entry);
2295 GET_BLOCK(exit);
2296 GET_BLOCK(breturn);
2297 GET_BLOCK(left);
2298 GET_BLOCK(right);
2299 #undef GET_BLOCK
2300 HInstruction* bool_value = MakeParam(DataType::Type::kBool);
2301 HInstruction* c1 = graph_->GetIntConstant(1);
2302 HInstruction* c2 = graph_->GetIntConstant(2);
2303
2304 HInstruction* cls = MakeClassLoad();
2305 HInstruction* new_inst = MakeNewInstance(cls);
2306 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2307 entry->AddInstruction(cls);
2308 entry->AddInstruction(new_inst);
2309 entry->AddInstruction(if_inst);
2310 ManuallyBuildEnvFor(cls, {});
2311 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2312
2313 HInstruction* call_left = MakeInvoke(DataType::Type::kVoid, { new_inst });
2314 HInstruction* write_left = MakeIFieldSet(new_inst, c1, MemberOffset(32));
2315 HInstruction* call2_left = MakeInvoke(DataType::Type::kVoid, {});
2316 HInstruction* goto_left = new (GetAllocator()) HGoto();
2317 left->AddInstruction(call_left);
2318 left->AddInstruction(write_left);
2319 left->AddInstruction(call2_left);
2320 left->AddInstruction(goto_left);
2321 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2322 call2_left->CopyEnvironmentFrom(cls->GetEnvironment());
2323
2324 HInstruction* write_right = MakeIFieldSet(new_inst, c2, MemberOffset(32));
2325 HInstruction* call_right = MakeInvoke(DataType::Type::kVoid, {});
2326 HInstruction* goto_right = new (GetAllocator()) HGoto();
2327 right->AddInstruction(write_right);
2328 right->AddInstruction(call_right);
2329 right->AddInstruction(goto_right);
2330 call_right->CopyEnvironmentFrom(cls->GetEnvironment());
2331
2332 HInstruction* read_bottom = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
2333 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
2334 breturn->AddInstruction(read_bottom);
2335 breturn->AddInstruction(return_exit);
2336
2337 SetupExit(exit);
2338
2339 PerformLSE(blks);
2340
2341 EXPECT_INS_RETAINED(read_bottom);
2342 EXPECT_INS_RETAINED(write_right);
2343 EXPECT_INS_RETAINED(write_left);
2344 EXPECT_INS_RETAINED(call_left);
2345 EXPECT_INS_RETAINED(call_right);
2346 }
2347
2348 // // ENTRY
2349 // obj = new Obj();
2350 // DO NOT ELIMINATE. Kept by escape.
2351 // obj.field = 3;
2352 // noescape();
2353 // if (parameter_value) {
2354 // // LEFT
2355 // // DO NOT ELIMINATE
2356 // escape(obj);
2357 // obj.field = 1;
2358 // } else {
2359 // // RIGHT
2360 // // ELIMINATE
2361 // obj.field = 2;
2362 // }
2363 // EXIT
2364 // ELIMINATE
2365 // return obj.field
2366 // Disabled due to b/205813546.
TEST_F(LoadStoreEliminationTest,DISABLED_PartialLoadPreserved6)2367 TEST_F(LoadStoreEliminationTest, DISABLED_PartialLoadPreserved6) {
2368 CreateGraph();
2369 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2370 "exit",
2371 {{"entry", "left"},
2372 {"entry", "right"},
2373 {"left", "breturn"},
2374 {"right", "breturn"},
2375 {"breturn", "exit"}}));
2376 #define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2377 GET_BLOCK(entry);
2378 GET_BLOCK(exit);
2379 GET_BLOCK(breturn);
2380 GET_BLOCK(left);
2381 GET_BLOCK(right);
2382 #undef GET_BLOCK
2383 HInstruction* bool_value = MakeParam(DataType::Type::kBool);
2384 HInstruction* c1 = graph_->GetIntConstant(1);
2385 HInstruction* c2 = graph_->GetIntConstant(2);
2386 HInstruction* c3 = graph_->GetIntConstant(3);
2387
2388 HInstruction* cls = MakeClassLoad();
2389 HInstruction* new_inst = MakeNewInstance(cls);
2390 HInstruction* write_entry = MakeIFieldSet(new_inst, c3, MemberOffset(32));
2391 HInstruction* call_entry = MakeInvoke(DataType::Type::kVoid, {});
2392 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2393 entry->AddInstruction(cls);
2394 entry->AddInstruction(new_inst);
2395 entry->AddInstruction(write_entry);
2396 entry->AddInstruction(call_entry);
2397 entry->AddInstruction(if_inst);
2398 ManuallyBuildEnvFor(cls, {});
2399 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2400 call_entry->CopyEnvironmentFrom(cls->GetEnvironment());
2401
2402 HInstruction* call_left = MakeInvoke(DataType::Type::kVoid, { new_inst });
2403 HInstruction* write_left = MakeIFieldSet(new_inst, c1, MemberOffset(32));
2404 HInstruction* goto_left = new (GetAllocator()) HGoto();
2405 left->AddInstruction(call_left);
2406 left->AddInstruction(write_left);
2407 left->AddInstruction(goto_left);
2408 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2409
2410 HInstruction* write_right = MakeIFieldSet(new_inst, c2, MemberOffset(32));
2411 HInstruction* goto_right = new (GetAllocator()) HGoto();
2412 right->AddInstruction(write_right);
2413 right->AddInstruction(goto_right);
2414
2415 HInstruction* read_bottom = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
2416 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
2417 breturn->AddInstruction(read_bottom);
2418 breturn->AddInstruction(return_exit);
2419
2420 SetupExit(exit);
2421
2422 PerformLSE(blks);
2423
2424 EXPECT_INS_REMOVED(read_bottom);
2425 EXPECT_INS_REMOVED(write_right);
2426 EXPECT_INS_RETAINED(write_entry);
2427 EXPECT_INS_RETAINED(write_left);
2428 EXPECT_INS_RETAINED(call_left);
2429 EXPECT_INS_RETAINED(call_entry);
2430 }
2431 } // namespace art
2432