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