Gitiles
Code Review Sign In
LeafOS / LeafOS-Project / android_art / f5a84cb8a950632cd4e730839c7f9f34b52c81d1 / . / compiler / optimizing / load_store_elimination_test.cc
blob: 0598e27275b068904b39a5409c6615fb1724ea07 [file] [log] [blame]
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]1/*
2 * Copyright (C) 2019 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <tuple>
18
Alex Light2610dfe2020-12-07 16:26:43 -0800[diff] [blame]19#include "compilation_kind.h"
20#include "entrypoints/quick/quick_entrypoints_enum.h"
21#include "gtest/gtest.h"
22#include "handle_scope.h"
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]23#include "load_store_analysis.h"
24#include "load_store_elimination.h"
25#include "nodes.h"
26#include "optimizing_unit_test.h"
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]27
28#include "gtest/gtest.h"
29
30namespace art {
31
Vladimir Marko5d2311a2020-05-13 17:30:32 +0100[diff] [blame]32class LoadStoreEliminationTest : public OptimizingUnitTest {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]33 public:
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]34 AdjacencyListGraph SetupFromAdjacencyList(
35 const std::string_view entry_name,
36 const std::string_view exit_name,
37 const std::vector<AdjacencyListGraph::Edge>& adj) {
38 return AdjacencyListGraph(graph_, GetAllocator(), entry_name, exit_name, adj);
39 }
40
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]41 void PerformLSE() {
42 graph_->BuildDominatorTree();
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]43 LoadStoreElimination lse(graph_, /*stats=*/ nullptr);
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]44 lse.Run();
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]45 std::ostringstream oss;
46 EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks(oss)) << oss.str();
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]47 }
48
49 // Create instructions shared among tests.
50 void CreateEntryBlockInstructions() {
51 HInstruction* c1 = graph_->GetIntConstant(1);
52 HInstruction* c4 = graph_->GetIntConstant(4);
53 i_add1_ = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_, c1);
54 i_add4_ = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_, c4);
55 entry_block_->AddInstruction(i_add1_);
56 entry_block_->AddInstruction(i_add4_);
57 entry_block_->AddInstruction(new (GetAllocator()) HGoto());
58 }
59
60 // Create the major CFG used by tests:
61 // entry
62 // |
63 // pre_header
64 // |
65 // loop[]
66 // |
67 // return
68 // |
69 // exit
70 void CreateTestControlFlowGraph() {
Vladimir Marko5d2311a2020-05-13 17:30:32 +0100[diff] [blame]71 InitGraphAndParameters();
72 pre_header_ = AddNewBlock();
73 loop_ = AddNewBlock();
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]74
75 entry_block_->ReplaceSuccessor(return_block_, pre_header_);
76 pre_header_->AddSuccessor(loop_);
77 loop_->AddSuccessor(loop_);
78 loop_->AddSuccessor(return_block_);
79
80 HInstruction* c0 = graph_->GetIntConstant(0);
81 HInstruction* c1 = graph_->GetIntConstant(1);
82 HInstruction* c128 = graph_->GetIntConstant(128);
83
84 CreateEntryBlockInstructions();
85
86 // pre_header block
87 // phi = 0;
88 phi_ = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
89 loop_->AddPhi(phi_);
90 pre_header_->AddInstruction(new (GetAllocator()) HGoto());
91 phi_->AddInput(c0);
92
93 // loop block:
94 // suspend_check
95 // phi++;
96 // if (phi >= 128)
97 suspend_check_ = new (GetAllocator()) HSuspendCheck();
98 HInstruction* inc_phi = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_, c1);
99 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(phi_, c128);
100 HInstruction* hif = new (GetAllocator()) HIf(cmp);
101 loop_->AddInstruction(suspend_check_);
102 loop_->AddInstruction(inc_phi);
103 loop_->AddInstruction(cmp);
104 loop_->AddInstruction(hif);
105 phi_->AddInput(inc_phi);
106
107 CreateEnvForSuspendCheck();
108 }
109
110 void CreateEnvForSuspendCheck() {
111 ArenaVector<HInstruction*> current_locals({array_, i_, j_},
112 GetAllocator()->Adapter(kArenaAllocInstruction));
113 ManuallyBuildEnvFor(suspend_check_, &current_locals);
114 }
115
116 // Create the diamond-shaped CFG:
117 // upper
118 // / \
119 // left right
120 // \ /
121 // down
122 //
123 // Return: the basic blocks forming the CFG in the following order {upper, left, right, down}.
124 std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateDiamondShapedCFG() {
Vladimir Marko5d2311a2020-05-13 17:30:32 +0100[diff] [blame]125 InitGraphAndParameters();
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]126 CreateEntryBlockInstructions();
127
Vladimir Marko5d2311a2020-05-13 17:30:32 +0100[diff] [blame]128 HBasicBlock* upper = AddNewBlock();
129 HBasicBlock* left = AddNewBlock();
130 HBasicBlock* right = AddNewBlock();
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]131
132 entry_block_->ReplaceSuccessor(return_block_, upper);
133 upper->AddSuccessor(left);
134 upper->AddSuccessor(right);
135 left->AddSuccessor(return_block_);
136 right->AddSuccessor(return_block_);
137
138 HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(i_, j_);
139 HInstruction* hif = new (GetAllocator()) HIf(cmp);
140 upper->AddInstruction(cmp);
141 upper->AddInstruction(hif);
142
143 left->AddInstruction(new (GetAllocator()) HGoto());
144 right->AddInstruction(new (GetAllocator()) HGoto());
145
146 return std::make_tuple(upper, left, right, return_block_);
147 }
148
149 // Add a HVecLoad instruction to the end of the provided basic block.
150 //
151 // Return: the created HVecLoad instruction.
152 HInstruction* AddVecLoad(HBasicBlock* block, HInstruction* array, HInstruction* index) {
153 DCHECK(block != nullptr);
154 DCHECK(array != nullptr);
155 DCHECK(index != nullptr);
156 HInstruction* vload = new (GetAllocator()) HVecLoad(
157 GetAllocator(),
158 array,
159 index,
160 DataType::Type::kInt32,
161 SideEffects::ArrayReadOfType(DataType::Type::kInt32),
162 4,
163 /*is_string_char_at*/ false,
164 kNoDexPc);
165 block->InsertInstructionBefore(vload, block->GetLastInstruction());
166 return vload;
167 }
168
169 // Add a HVecStore instruction to the end of the provided basic block.
170 // If no vdata is specified, generate HVecStore: array[index] = [1,1,1,1].
171 //
172 // Return: the created HVecStore instruction.
173 HInstruction* AddVecStore(HBasicBlock* block,
174 HInstruction* array,
175 HInstruction* index,
176 HInstruction* vdata = nullptr) {
177 DCHECK(block != nullptr);
178 DCHECK(array != nullptr);
179 DCHECK(index != nullptr);
180 if (vdata == nullptr) {
181 HInstruction* c1 = graph_->GetIntConstant(1);
182 vdata = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
183 c1,
184 DataType::Type::kInt32,
185 4,
186 kNoDexPc);
187 block->InsertInstructionBefore(vdata, block->GetLastInstruction());
188 }
189 HInstruction* vstore = new (GetAllocator()) HVecStore(
190 GetAllocator(),
191 array,
192 index,
193 vdata,
194 DataType::Type::kInt32,
195 SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
196 4,
197 kNoDexPc);
198 block->InsertInstructionBefore(vstore, block->GetLastInstruction());
199 return vstore;
200 }
201
202 // Add a HArrayGet instruction to the end of the provided basic block.
203 //
204 // Return: the created HArrayGet instruction.
205 HInstruction* AddArrayGet(HBasicBlock* block, HInstruction* array, HInstruction* index) {
206 DCHECK(block != nullptr);
207 DCHECK(array != nullptr);
208 DCHECK(index != nullptr);
209 HInstruction* get = new (GetAllocator()) HArrayGet(array, index, DataType::Type::kInt32, 0);
210 block->InsertInstructionBefore(get, block->GetLastInstruction());
211 return get;
212 }
213
214 // Add a HArraySet instruction to the end of the provided basic block.
215 // If no data is specified, generate HArraySet: array[index] = 1.
216 //
217 // Return: the created HArraySet instruction.
218 HInstruction* AddArraySet(HBasicBlock* block,
219 HInstruction* array,
220 HInstruction* index,
221 HInstruction* data = nullptr) {
222 DCHECK(block != nullptr);
223 DCHECK(array != nullptr);
224 DCHECK(index != nullptr);
225 if (data == nullptr) {
226 data = graph_->GetIntConstant(1);
227 }
228 HInstruction* store = new (GetAllocator()) HArraySet(array,
229 index,
230 data,
231 DataType::Type::kInt32,
232 0);
233 block->InsertInstructionBefore(store, block->GetLastInstruction());
234 return store;
235 }
236
Vladimir Marko5d2311a2020-05-13 17:30:32 +0100[diff] [blame]237 void InitGraphAndParameters() {
238 InitGraph();
239 AddParameter(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
240 dex::TypeIndex(0),
241 0,
242 DataType::Type::kInt32));
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]243 array_ = parameters_.back();
Vladimir Marko5d2311a2020-05-13 17:30:32 +0100[diff] [blame]244 AddParameter(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
245 dex::TypeIndex(1),
246 1,
247 DataType::Type::kInt32));
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]248 i_ = parameters_.back();
Vladimir Marko5d2311a2020-05-13 17:30:32 +0100[diff] [blame]249 AddParameter(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
250 dex::TypeIndex(1),
251 2,
252 DataType::Type::kInt32));
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]253 j_ = parameters_.back();
254 }
255
256 HBasicBlock* pre_header_;
257 HBasicBlock* loop_;
258
259 HInstruction* array_;
260 HInstruction* i_;
261 HInstruction* j_;
262 HInstruction* i_add1_;
263 HInstruction* i_add4_;
264 HInstruction* suspend_check_;
265
266 HPhi* phi_;
267};
268
269TEST_F(LoadStoreEliminationTest, ArrayGetSetElimination) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]270 CreateTestControlFlowGraph();
271
272 HInstruction* c1 = graph_->GetIntConstant(1);
273 HInstruction* c2 = graph_->GetIntConstant(2);
274 HInstruction* c3 = graph_->GetIntConstant(3);
275
276 // array[1] = 1;
277 // x = array[1]; <--- Remove.
278 // y = array[2];
279 // array[1] = 1; <--- Remove, since it stores same value.
280 // array[i] = 3; <--- MAY alias.
281 // array[1] = 1; <--- Cannot remove, even if it stores the same value.
282 AddArraySet(entry_block_, array_, c1, c1);
283 HInstruction* load1 = AddArrayGet(entry_block_, array_, c1);
284 HInstruction* load2 = AddArrayGet(entry_block_, array_, c2);
285 HInstruction* store1 = AddArraySet(entry_block_, array_, c1, c1);
286 AddArraySet(entry_block_, array_, i_, c3);
287 HInstruction* store2 = AddArraySet(entry_block_, array_, c1, c1);
288
289 PerformLSE();
290
291 ASSERT_TRUE(IsRemoved(load1));
292 ASSERT_FALSE(IsRemoved(load2));
293 ASSERT_TRUE(IsRemoved(store1));
294 ASSERT_FALSE(IsRemoved(store2));
295}
296
297TEST_F(LoadStoreEliminationTest, SameHeapValue1) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]298 CreateTestControlFlowGraph();
299
300 HInstruction* c1 = graph_->GetIntConstant(1);
301 HInstruction* c2 = graph_->GetIntConstant(2);
302
303 // Test LSE handling same value stores on array.
304 // array[1] = 1;
305 // array[2] = 1;
306 // array[1] = 1; <--- Can remove.
307 // array[1] = 2; <--- Can NOT remove.
308 AddArraySet(entry_block_, array_, c1, c1);
309 AddArraySet(entry_block_, array_, c2, c1);
310 HInstruction* store1 = AddArraySet(entry_block_, array_, c1, c1);
311 HInstruction* store2 = AddArraySet(entry_block_, array_, c1, c2);
312
313 PerformLSE();
314
315 ASSERT_TRUE(IsRemoved(store1));
316 ASSERT_FALSE(IsRemoved(store2));
317}
318
319TEST_F(LoadStoreEliminationTest, SameHeapValue2) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]320 CreateTestControlFlowGraph();
321
322 // Test LSE handling same value stores on vector.
323 // vdata = [0x1, 0x2, 0x3, 0x4, ...]
324 // VecStore array[i...] = vdata;
325 // VecStore array[j...] = vdata; <--- MAY ALIAS.
326 // VecStore array[i...] = vdata; <--- Cannot Remove, even if it's same value.
327 AddVecStore(entry_block_, array_, i_);
328 AddVecStore(entry_block_, array_, j_);
329 HInstruction* vstore = AddVecStore(entry_block_, array_, i_);
330
331 PerformLSE();
332
333 ASSERT_FALSE(IsRemoved(vstore));
334}
335
336TEST_F(LoadStoreEliminationTest, SameHeapValue3) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]337 CreateTestControlFlowGraph();
338
339 // VecStore array[i...] = vdata;
340 // VecStore array[i+1...] = vdata; <--- MAY alias due to partial overlap.
341 // VecStore array[i...] = vdata; <--- Cannot remove, even if it's same value.
342 AddVecStore(entry_block_, array_, i_);
343 AddVecStore(entry_block_, array_, i_add1_);
344 HInstruction* vstore = AddVecStore(entry_block_, array_, i_);
345
346 PerformLSE();
347
348 ASSERT_FALSE(IsRemoved(vstore));
349}
350
351TEST_F(LoadStoreEliminationTest, OverlappingLoadStore) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]352 CreateTestControlFlowGraph();
353
354 HInstruction* c1 = graph_->GetIntConstant(1);
355
356 // Test LSE handling array LSE when there is vector store in between.
357 // a[i] = 1;
358 // .. = a[i]; <-- Remove.
359 // a[i,i+1,i+2,i+3] = data; <-- PARTIAL OVERLAP !
360 // .. = a[i]; <-- Cannot remove.
361 AddArraySet(entry_block_, array_, i_, c1);
362 HInstruction* load1 = AddArrayGet(entry_block_, array_, i_);
363 AddVecStore(entry_block_, array_, i_);
364 HInstruction* load2 = AddArrayGet(entry_block_, array_, i_);
365
366 // Test LSE handling vector load/store partial overlap.
367 // a[i,i+1,i+2,i+3] = data;
368 // a[i+4,i+5,i+6,i+7] = data;
369 // .. = a[i,i+1,i+2,i+3];
370 // .. = a[i+4,i+5,i+6,i+7];
371 // a[i+1,i+2,i+3,i+4] = data; <-- PARTIAL OVERLAP !
372 // .. = a[i,i+1,i+2,i+3];
373 // .. = a[i+4,i+5,i+6,i+7];
374 AddVecStore(entry_block_, array_, i_);
375 AddVecStore(entry_block_, array_, i_add4_);
376 HInstruction* vload1 = AddVecLoad(entry_block_, array_, i_);
377 HInstruction* vload2 = AddVecLoad(entry_block_, array_, i_add4_);
378 AddVecStore(entry_block_, array_, i_add1_);
379 HInstruction* vload3 = AddVecLoad(entry_block_, array_, i_);
380 HInstruction* vload4 = AddVecLoad(entry_block_, array_, i_add4_);
381
382 // Test LSE handling vector LSE when there is array store in between.
383 // a[i,i+1,i+2,i+3] = data;
384 // a[i+1] = 1; <-- PARTIAL OVERLAP !
385 // .. = a[i,i+1,i+2,i+3];
386 AddVecStore(entry_block_, array_, i_);
387 AddArraySet(entry_block_, array_, i_, c1);
388 HInstruction* vload5 = AddVecLoad(entry_block_, array_, i_);
389
390 PerformLSE();
391
392 ASSERT_TRUE(IsRemoved(load1));
393 ASSERT_FALSE(IsRemoved(load2));
394
395 ASSERT_TRUE(IsRemoved(vload1));
396 ASSERT_TRUE(IsRemoved(vload2));
397 ASSERT_FALSE(IsRemoved(vload3));
398 ASSERT_FALSE(IsRemoved(vload4));
399
400 ASSERT_FALSE(IsRemoved(vload5));
401}
402// function (int[] a, int j) {
403// a[j] = 1;
404// for (int i=0; i<128; i++) {
405// /* doesn't do any write */
406// }
407// a[j] = 1;
408TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithoutSideEffects) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]409 CreateTestControlFlowGraph();
410
411 HInstruction* c1 = graph_->GetIntConstant(1);
412
413 // a[j] = 1
414 AddArraySet(pre_header_, array_, j_, c1);
415
416 // LOOP BODY:
417 // .. = a[i,i+1,i+2,i+3];
418 AddVecLoad(loop_, array_, phi_);
419
420 // a[j] = 1;
421 HInstruction* array_set = AddArraySet(return_block_, array_, j_, c1);
422
423 PerformLSE();
424
425 ASSERT_TRUE(IsRemoved(array_set));
426}
427
428// function (int[] a, int j) {
429// int[] b = new int[128];
430// a[j] = 0;
431// for (int phi=0; phi<128; phi++) {
432// a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
433// b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
434// }
435// a[j] = 0;
436// }
437TEST_F(LoadStoreEliminationTest, StoreAfterSIMDLoopWithSideEffects) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]438 CreateTestControlFlowGraph();
439
440 HInstruction* c0 = graph_->GetIntConstant(0);
441 HInstruction* c128 = graph_->GetIntConstant(128);
442
443 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
444 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
445 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
446
447 // a[j] = 0;
448 AddArraySet(pre_header_, array_, j_, c0);
449
450 // LOOP BODY:
451 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
452 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
453 AddVecStore(loop_, array_, phi_);
454 HInstruction* vload = AddVecLoad(loop_, array_, phi_);
455 AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
456
457 // a[j] = 0;
458 HInstruction* a_set = AddArraySet(return_block_, array_, j_, c0);
459
460 PerformLSE();
461
462 ASSERT_TRUE(IsRemoved(vload));
463 ASSERT_FALSE(IsRemoved(a_set)); // Cannot remove due to write side-effect in the loop.
464}
465
466// function (int[] a, int j) {
467// int[] b = new int[128];
468// a[j] = 0;
469// for (int phi=0; phi<128; phi++) {
470// a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
471// b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
472// }
473// x = a[j];
474// }
475TEST_F(LoadStoreEliminationTest, LoadAfterSIMDLoopWithSideEffects) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]476 CreateTestControlFlowGraph();
477
478 HInstruction* c0 = graph_->GetIntConstant(0);
479 HInstruction* c128 = graph_->GetIntConstant(128);
480
481 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
482 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
483 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
484
485 // a[j] = 0;
486 AddArraySet(pre_header_, array_, j_, c0);
487
488 // LOOP BODY:
489 // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
490 // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
491 AddVecStore(loop_, array_, phi_);
492 HInstruction* vload = AddVecLoad(loop_, array_, phi_);
493 AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
494
495 // x = a[j];
496 HInstruction* load = AddArrayGet(return_block_, array_, j_);
497
498 PerformLSE();
499
500 ASSERT_TRUE(IsRemoved(vload));
501 ASSERT_FALSE(IsRemoved(load)); // Cannot remove due to write side-effect in the loop.
502}
503
504// Check that merging works correctly when there are VecStors in predecessors.
505//
506// vstore1: a[i,... i + 3] = [1,...1]
507// / \
508// / \
509// vstore2: a[i,... i + 3] = [1,...1] vstore3: a[i+1, ... i + 4] = [1, ... 1]
510// \ /
511// \ /
512// vstore4: a[i,... i + 3] = [1,...1]
513//
514// Expected:
515// 'vstore2' is removed.
516// 'vstore3' is not removed.
517// 'vstore4' is not removed. Such cases are not supported at the moment.
518TEST_F(LoadStoreEliminationTest, MergePredecessorVecStores) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]519 HBasicBlock* upper;
520 HBasicBlock* left;
521 HBasicBlock* right;
522 HBasicBlock* down;
523 std::tie(upper, left, right, down) = CreateDiamondShapedCFG();
524
525 // upper: a[i,... i + 3] = [1,...1]
526 HInstruction* vstore1 = AddVecStore(upper, array_, i_);
527 HInstruction* vdata = vstore1->InputAt(2);
528
529 // left: a[i,... i + 3] = [1,...1]
530 HInstruction* vstore2 = AddVecStore(left, array_, i_, vdata);
531
532 // right: a[i+1, ... i + 4] = [1, ... 1]
533 HInstruction* vstore3 = AddVecStore(right, array_, i_add1_, vdata);
534
535 // down: a[i,... i + 3] = [1,...1]
536 HInstruction* vstore4 = AddVecStore(down, array_, i_, vdata);
537
538 PerformLSE();
539
540 ASSERT_TRUE(IsRemoved(vstore2));
541 ASSERT_FALSE(IsRemoved(vstore3));
542 ASSERT_FALSE(IsRemoved(vstore4));
543}
544
545// Check that merging works correctly when there are ArraySets in predecessors.
546//
547// a[i] = 1
548// / \
549// / \
550// store1: a[i] = 1 store2: a[i+1] = 1
551// \ /
552// \ /
553// store3: a[i] = 1
554//
555// Expected:
556// 'store1' is removed.
557// 'store2' is not removed.
558// 'store3' is removed.
559TEST_F(LoadStoreEliminationTest, MergePredecessorStores) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]560 HBasicBlock* upper;
561 HBasicBlock* left;
562 HBasicBlock* right;
563 HBasicBlock* down;
564 std::tie(upper, left, right, down) = CreateDiamondShapedCFG();
565
566 // upper: a[i,... i + 3] = [1,...1]
567 AddArraySet(upper, array_, i_);
568
569 // left: a[i,... i + 3] = [1,...1]
570 HInstruction* store1 = AddArraySet(left, array_, i_);
571
572 // right: a[i+1, ... i + 4] = [1, ... 1]
573 HInstruction* store2 = AddArraySet(right, array_, i_add1_);
574
575 // down: a[i,... i + 3] = [1,...1]
576 HInstruction* store3 = AddArraySet(down, array_, i_);
577
578 PerformLSE();
579
580 ASSERT_TRUE(IsRemoved(store1));
581 ASSERT_FALSE(IsRemoved(store2));
582 ASSERT_TRUE(IsRemoved(store3));
583}
584
585// Check that redundant VStore/VLoad are removed from a SIMD loop.
586//
587// LOOP BODY
588// vstore1: a[i,... i + 3] = [1,...1]
589// vload: x = a[i,... i + 3]
590// vstore2: b[i,... i + 3] = x
591// vstore3: a[i,... i + 3] = [1,...1]
592//
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]593// Return 'a' from the method to make it escape.
594//
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]595// Expected:
596// 'vstore1' is not removed.
597// 'vload' is removed.
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]598// 'vstore2' is removed because 'b' does not escape.
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]599// 'vstore3' is removed.
600TEST_F(LoadStoreEliminationTest, RedundantVStoreVLoadInLoop) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]601 CreateTestControlFlowGraph();
602
603 HInstruction* c0 = graph_->GetIntConstant(0);
604 HInstruction* c128 = graph_->GetIntConstant(128);
605
606 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
607 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
608 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
609
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]610 ASSERT_TRUE(return_block_->GetLastInstruction()->IsReturnVoid());
611 HInstruction* ret = new (GetAllocator()) HReturn(array_a);
612 return_block_->ReplaceAndRemoveInstructionWith(return_block_->GetLastInstruction(), ret);
613
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]614 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
615 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
616 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
617
618 // LOOP BODY:
619 // a[i,... i + 3] = [1,...1]
620 // x = a[i,... i + 3]
621 // b[i,... i + 3] = x
622 // a[i,... i + 3] = [1,...1]
623 HInstruction* vstore1 = AddVecStore(loop_, array_a, phi_);
624 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]625 HInstruction* vstore2 = AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]626 HInstruction* vstore3 = AddVecStore(loop_, array_a, phi_, vstore1->InputAt(2));
627
628 PerformLSE();
629
630 ASSERT_FALSE(IsRemoved(vstore1));
631 ASSERT_TRUE(IsRemoved(vload));
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]632 ASSERT_TRUE(IsRemoved(vstore2));
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]633 ASSERT_TRUE(IsRemoved(vstore3));
634}
635
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]636// Loop writes invalidate only possibly aliased heap locations.
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]637TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithSideEffects) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]638 CreateTestControlFlowGraph();
639
640 HInstruction* c0 = graph_->GetIntConstant(0);
641 HInstruction* c2 = graph_->GetIntConstant(2);
642 HInstruction* c128 = graph_->GetIntConstant(128);
643
644 // array[0] = 2;
645 // loop:
646 // b[i] = array[i]
647 // array[0] = 2
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]648 HInstruction* store1 = AddArraySet(entry_block_, array_, c0, c2);
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]649
650 HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
651 pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
652 array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
653
654 HInstruction* load = AddArrayGet(loop_, array_, phi_);
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]655 HInstruction* store2 = AddArraySet(loop_, array_b, phi_, load);
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]656
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]657 HInstruction* store3 = AddArraySet(return_block_, array_, c0, c2);
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]658
659 PerformLSE();
660
Vladimir Marko3224f382020-06-23 14:19:53 +0100[diff] [blame]661 ASSERT_FALSE(IsRemoved(store1));
662 ASSERT_TRUE(IsRemoved(store2));
663 ASSERT_TRUE(IsRemoved(store3));
664}
665
666// Loop writes invalidate only possibly aliased heap locations.
667TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithSideEffects2) {
668 CreateTestControlFlowGraph();
669
670 // Add another array parameter that may alias with `array_`.
671 // Note: We're not adding it to the suspend check environment.
672 AddParameter(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
673 dex::TypeIndex(0),
674 3,
675 DataType::Type::kInt32));
676 HInstruction* array2 = parameters_.back();
677
678 HInstruction* c0 = graph_->GetIntConstant(0);
679 HInstruction* c2 = graph_->GetIntConstant(2);
680
681 // array[0] = 2;
682 // loop:
683 // array2[i] = array[i]
684 // array[0] = 2
685 HInstruction* store1 = AddArraySet(entry_block_, array_, c0, c2);
686
687 HInstruction* load = AddArrayGet(loop_, array_, phi_);
688 HInstruction* store2 = AddArraySet(loop_, array2, phi_, load);
689
690 HInstruction* store3 = AddArraySet(return_block_, array_, c0, c2);
691
692 PerformLSE();
693
694 ASSERT_FALSE(IsRemoved(store1));
695 ASSERT_FALSE(IsRemoved(store2));
696 ASSERT_FALSE(IsRemoved(store3));
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]697}
698
699// As it is not allowed to use defaults for VecLoads, check if there is a new created array
700// a VecLoad used in a loop and after it is not replaced with a default.
701TEST_F(LoadStoreEliminationTest, VLoadDefaultValueInLoopWithoutWriteSideEffects) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]702 CreateTestControlFlowGraph();
703
704 HInstruction* c0 = graph_->GetIntConstant(0);
705 HInstruction* c128 = graph_->GetIntConstant(128);
706
707 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
708 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
709 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
710
711 // LOOP BODY:
712 // v = a[i,... i + 3]
713 // array[0,... 3] = v
714 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
715 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
716
717 PerformLSE();
718
719 ASSERT_FALSE(IsRemoved(vload));
720 ASSERT_FALSE(IsRemoved(vstore));
721}
722
723// As it is not allowed to use defaults for VecLoads, check if there is a new created array
724// a VecLoad is not replaced with a default.
725TEST_F(LoadStoreEliminationTest, VLoadDefaultValue) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]726 CreateTestControlFlowGraph();
727
728 HInstruction* c0 = graph_->GetIntConstant(0);
729 HInstruction* c128 = graph_->GetIntConstant(128);
730
731 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
732 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
733 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
734
735 // v = a[0,... 3]
736 // array[0,... 3] = v
737 HInstruction* vload = AddVecLoad(pre_header_, array_a, c0);
738 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
739
740 PerformLSE();
741
742 ASSERT_FALSE(IsRemoved(vload));
743 ASSERT_FALSE(IsRemoved(vstore));
744}
745
746// As it is allowed to use defaults for ordinary loads, check if there is a new created array
747// a load used in a loop and after it is replaced with a default.
748TEST_F(LoadStoreEliminationTest, LoadDefaultValueInLoopWithoutWriteSideEffects) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]749 CreateTestControlFlowGraph();
750
751 HInstruction* c0 = graph_->GetIntConstant(0);
752 HInstruction* c128 = graph_->GetIntConstant(128);
753
754 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
755 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
756 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
757
758 // LOOP BODY:
759 // v = a[i]
760 // array[0] = v
761 HInstruction* load = AddArrayGet(loop_, array_a, phi_);
762 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
763
764 PerformLSE();
765
766 ASSERT_TRUE(IsRemoved(load));
767 ASSERT_FALSE(IsRemoved(store));
768}
769
770// As it is allowed to use defaults for ordinary loads, check if there is a new created array
771// a load is replaced with a default.
772TEST_F(LoadStoreEliminationTest, LoadDefaultValue) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]773 CreateTestControlFlowGraph();
774
775 HInstruction* c0 = graph_->GetIntConstant(0);
776 HInstruction* c128 = graph_->GetIntConstant(128);
777
778 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
779 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
780 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
781
782 // v = a[0]
783 // array[0] = v
784 HInstruction* load = AddArrayGet(pre_header_, array_a, c0);
785 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
786
787 PerformLSE();
788
789 ASSERT_TRUE(IsRemoved(load));
790 ASSERT_FALSE(IsRemoved(store));
791}
792
793// As it is not allowed to use defaults for VecLoads but allowed for regular loads,
794// check if there is a new created array, a VecLoad and a load used in a loop and after it,
795// VecLoad is not replaced with a default but the load is.
796TEST_F(LoadStoreEliminationTest, VLoadAndLoadDefaultValueInLoopWithoutWriteSideEffects) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]797 CreateTestControlFlowGraph();
798
799 HInstruction* c0 = graph_->GetIntConstant(0);
800 HInstruction* c128 = graph_->GetIntConstant(128);
801
802 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
803 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
804 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
805
806 // LOOP BODY:
807 // v = a[i,... i + 3]
808 // v1 = a[i]
809 // array[0,... 3] = v
810 // array[0] = v1
811 HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
812 HInstruction* load = AddArrayGet(loop_, array_a, phi_);
813 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
814 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
815
816 PerformLSE();
817
818 ASSERT_FALSE(IsRemoved(vload));
819 ASSERT_TRUE(IsRemoved(load));
820 ASSERT_FALSE(IsRemoved(vstore));
821 ASSERT_FALSE(IsRemoved(store));
822}
823
824// As it is not allowed to use defaults for VecLoads but allowed for regular loads,
825// check if there is a new created array, a VecLoad and a load,
826// VecLoad is not replaced with a default but the load is.
827TEST_F(LoadStoreEliminationTest, VLoadAndLoadDefaultValue) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]828 CreateTestControlFlowGraph();
829
830 HInstruction* c0 = graph_->GetIntConstant(0);
831 HInstruction* c128 = graph_->GetIntConstant(128);
832
833 HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
834 pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
835 array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
836
837 // v = a[0,... 3]
838 // v1 = a[0]
839 // array[0,... 3] = v
840 // array[0] = v1
841 HInstruction* vload = AddVecLoad(pre_header_, array_a, c0);
842 HInstruction* load = AddArrayGet(pre_header_, array_a, c0);
843 HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
844 HInstruction* store = AddArraySet(return_block_, array_, c0, load);
845
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).
857TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoadInLoopWithoutWriteSideEffects) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]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->AsVecLoad());
875 HInstruction* vstore2 = AddVecStore(return_block_, array_, c128, vload2->AsVecLoad());
876
877 PerformLSE();
878
879 ASSERT_FALSE(IsRemoved(vload1));
880 ASSERT_TRUE(IsRemoved(vload2));
881 ASSERT_FALSE(IsRemoved(vstore1));
882 ASSERT_FALSE(IsRemoved(vstore2));
883}
884
885// It is not allowed to use defaults for VecLoads. However it should not prevent from removing
886// loads getting the same value.
887// Check a load getting a known value is eliminated.
888TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoad) {
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]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,... 3]
900 // array[0,... 3] = v
901 // array[128,... 131] = v1
902 HInstruction* vload1 = AddVecLoad(pre_header_, array_a, c0);
903 HInstruction* vload2 = AddVecLoad(pre_header_, array_a, c0);
904 HInstruction* vstore1 = AddVecStore(return_block_, array_, c0, vload1->AsVecLoad());
905 HInstruction* vstore2 = AddVecStore(return_block_, array_, c128, vload2->AsVecLoad());
906
907 PerformLSE();
908
909 ASSERT_FALSE(IsRemoved(vload1));
910 ASSERT_TRUE(IsRemoved(vload2));
911 ASSERT_FALSE(IsRemoved(vstore1));
912 ASSERT_FALSE(IsRemoved(vstore2));
913}
914
Alex Light2610dfe2020-12-07 16:26:43 -0800[diff] [blame]915// Object o = new Obj();
916// // Needed because otherwise we short-circuit LSA since GVN would get almost
917// // everything other than this. Also since this isn't expected to be a very
918// // common pattern it's not worth changing the LSA logic.
919// o.foo = 3;
920// return o.shadow$_klass_;
921TEST_F(LoadStoreEliminationTest, DefaultShadowClass) {
922 CreateGraph();
923 AdjacencyListGraph blocks(
924 graph_, GetAllocator(), "entry", "exit", {{"entry", "main"}, {"main", "exit"}});
925#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
926 GET_BLOCK(entry);
927 GET_BLOCK(main);
928 GET_BLOCK(exit);
929#undef GET_BLOCK
930
931 HInstruction* suspend_check = new (GetAllocator()) HSuspendCheck();
932 entry->AddInstruction(suspend_check);
933 entry->AddInstruction(new (GetAllocator()) HGoto());
934 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
935 ManuallyBuildEnvFor(suspend_check, &current_locals);
936
937 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
938 dex::TypeIndex(10),
939 graph_->GetDexFile(),
940 ScopedNullHandle<mirror::Class>(),
941 false,
942 0,
943 false);
944 HInstruction* new_inst =
945 new (GetAllocator()) HNewInstance(cls,
946 0,
947 dex::TypeIndex(10),
948 graph_->GetDexFile(),
949 false,
950 QuickEntrypointEnum::kQuickAllocObjectInitialized);
951 HInstruction* const_fence = new (GetAllocator()) HConstructorFence(new_inst, 0, GetAllocator());
952 HInstruction* set_field = new (GetAllocator()) HInstanceFieldSet(new_inst,
953 graph_->GetIntConstant(33),
954 nullptr,
955 DataType::Type::kReference,
956 MemberOffset(10),
957 false,
958 0,
959 0,
960 graph_->GetDexFile(),
961 0);
962 HInstruction* get_field = new (GetAllocator()) HInstanceFieldGet(new_inst,
963 nullptr,
964 DataType::Type::kReference,
965 mirror::Object::ClassOffset(),
966 false,
967 0,
968 0,
969 graph_->GetDexFile(),
970 0);
971 HInstruction* return_val = new (GetAllocator()) HReturn(get_field);
972 main->AddInstruction(cls);
973 main->AddInstruction(new_inst);
974 main->AddInstruction(const_fence);
975 main->AddInstruction(set_field);
976 main->AddInstruction(get_field);
977 main->AddInstruction(return_val);
978 cls->CopyEnvironmentFrom(suspend_check->GetEnvironment());
979 new_inst->CopyEnvironmentFrom(suspend_check->GetEnvironment());
980
981 exit->AddInstruction(new (GetAllocator()) HExit());
982
983 graph_->ClearDominanceInformation();
984 PerformLSE();
985
986 EXPECT_TRUE(IsRemoved(new_inst));
987 EXPECT_TRUE(IsRemoved(const_fence));
988 EXPECT_TRUE(IsRemoved(get_field));
989 EXPECT_TRUE(IsRemoved(set_field));
990 EXPECT_FALSE(IsRemoved(cls));
991 EXPECT_EQ(cls, return_val->InputAt(0));
992}
993
Alex Light9dec90a2020-09-14 17:58:28 -0700[diff] [blame]994// void DO_CAL() {
995// int i = 1;
996// int[] w = new int[80];
997// int t = 0;
998// while (i < 80) {
999// w[i] = PLEASE_INTERLEAVE(w[i - 1], 1)
1000// t = PLEASE_SELECT(w[i], t);
1001// i++;
1002// }
1003// return t;
1004// }
1005TEST_F(LoadStoreEliminationTest, ArrayLoopOverlap) {
1006 CreateGraph();
1007 AdjacencyListGraph blocks(graph_,
1008 GetAllocator(),
1009 "entry",
1010 "exit",
1011 { { "entry", "loop_pre_header" },
1012 { "loop_pre_header", "loop_entry" },
1013 { "loop_entry", "loop_body" },
1014 { "loop_entry", "loop_post" },
1015 { "loop_body", "loop_entry" },
1016 { "loop_post", "exit" } });
1017#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1018 GET_BLOCK(entry);
1019 GET_BLOCK(loop_pre_header);
1020 GET_BLOCK(loop_entry);
1021 GET_BLOCK(loop_body);
1022 GET_BLOCK(loop_post);
1023 GET_BLOCK(exit);
1024#undef GET_BLOCK
1025
1026 HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
1027 HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
1028 HInstruction* eighty_const = graph_->GetConstant(DataType::Type::kInt32, 80);
1029 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1030 entry->AddInstruction(entry_goto);
1031
1032 HInstruction* alloc_w = new (GetAllocator()) HNewArray(zero_const, eighty_const, 0, 0);
1033 HInstruction* pre_header_goto = new (GetAllocator()) HGoto();
1034 loop_pre_header->AddInstruction(alloc_w);
1035 loop_pre_header->AddInstruction(pre_header_goto);
1036 // environment
1037 ArenaVector<HInstruction*> alloc_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1038 ManuallyBuildEnvFor(alloc_w, &alloc_locals);
1039
1040 // loop-start
1041 HPhi* i_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
1042 HPhi* t_phi = new (GetAllocator()) HPhi(GetAllocator(), 1, 0, DataType::Type::kInt32);
1043 HInstruction* suspend = new (GetAllocator()) HSuspendCheck();
1044 HInstruction* i_cmp_top = new (GetAllocator()) HGreaterThanOrEqual(i_phi, eighty_const);
1045 HInstruction* loop_start_branch = new (GetAllocator()) HIf(i_cmp_top);
1046 loop_entry->AddPhi(i_phi);
1047 loop_entry->AddPhi(t_phi);
1048 loop_entry->AddInstruction(suspend);
1049 loop_entry->AddInstruction(i_cmp_top);
1050 loop_entry->AddInstruction(loop_start_branch);
1051 CHECK_EQ(loop_entry->GetSuccessors().size(), 2u);
1052 if (loop_entry->GetNormalSuccessors()[1] != loop_body) {
1053 loop_entry->SwapSuccessors();
1054 }
1055 CHECK_EQ(loop_entry->GetPredecessors().size(), 2u);
1056 if (loop_entry->GetPredecessors()[0] != loop_pre_header) {
1057 loop_entry->SwapPredecessors();
1058 }
1059 i_phi->AddInput(one_const);
1060 t_phi->AddInput(zero_const);
1061
1062 // environment
1063 ArenaVector<HInstruction*> suspend_locals({ alloc_w, i_phi, t_phi },
1064 GetAllocator()->Adapter(kArenaAllocInstruction));
1065 ManuallyBuildEnvFor(suspend, &suspend_locals);
1066
1067 // BODY
1068 HInstruction* last_i = new (GetAllocator()) HSub(DataType::Type::kInt32, i_phi, one_const);
1069 HInstruction* last_get =
1070 new (GetAllocator()) HArrayGet(alloc_w, last_i, DataType::Type::kInt32, 0);
1071 HInvoke* body_value = new (GetAllocator())
1072 HInvokeStaticOrDirect(GetAllocator(),
1073 2,
1074 DataType::Type::kInt32,
1075 0,
1076 { nullptr, 0 },
1077 nullptr,
1078 {},
1079 InvokeType::kStatic,
1080 { nullptr, 0 },
1081 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1082 body_value->SetRawInputAt(0, last_get);
1083 body_value->SetRawInputAt(1, one_const);
1084 HInstruction* body_set =
1085 new (GetAllocator()) HArraySet(alloc_w, i_phi, body_value, DataType::Type::kInt32, 0);
1086 HInstruction* body_get =
1087 new (GetAllocator()) HArrayGet(alloc_w, i_phi, DataType::Type::kInt32, 0);
1088 HInvoke* t_next = new (GetAllocator())
1089 HInvokeStaticOrDirect(GetAllocator(),
1090 2,
1091 DataType::Type::kInt32,
1092 0,
1093 { nullptr, 0 },
1094 nullptr,
1095 {},
1096 InvokeType::kStatic,
1097 { nullptr, 0 },
1098 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1099 t_next->SetRawInputAt(0, body_get);
1100 t_next->SetRawInputAt(1, t_phi);
1101 HInstruction* i_next = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_phi, one_const);
1102 HInstruction* body_goto = new (GetAllocator()) HGoto();
1103 loop_body->AddInstruction(last_i);
1104 loop_body->AddInstruction(last_get);
1105 loop_body->AddInstruction(body_value);
1106 loop_body->AddInstruction(body_set);
1107 loop_body->AddInstruction(body_get);
1108 loop_body->AddInstruction(t_next);
1109 loop_body->AddInstruction(i_next);
1110 loop_body->AddInstruction(body_goto);
1111 body_value->CopyEnvironmentFrom(suspend->GetEnvironment());
1112
1113 i_phi->AddInput(i_next);
1114 t_phi->AddInput(t_next);
1115 t_next->CopyEnvironmentFrom(suspend->GetEnvironment());
1116
1117 // loop-post
1118 HInstruction* return_inst = new (GetAllocator()) HReturn(t_phi);
1119 loop_post->AddInstruction(return_inst);
1120
1121 // exit
1122 HInstruction* exit_inst = new (GetAllocator()) HExit();
1123 exit->AddInstruction(exit_inst);
1124
1125 graph_->ClearDominanceInformation();
1126 graph_->ClearLoopInformation();
1127 PerformLSE();
1128
1129 // TODO Technically this is optimizable. LSE just needs to add phis to keep
1130 // track of the last `N` values set where `N` is how many locations we can go
1131 // back into the array.
1132 if (IsRemoved(last_get)) {
1133 // If we were able to remove the previous read the entire array should be removable.
1134 EXPECT_TRUE(IsRemoved(body_set));
1135 EXPECT_TRUE(IsRemoved(alloc_w));
1136 } else {
1137 // This is the branch we actually take for now. If we rely on being able to
1138 // read the array we'd better remember to write to it as well.
1139 EXPECT_FALSE(IsRemoved(body_set));
1140 }
1141 // The last 'get' should always be removable.
1142 EXPECT_TRUE(IsRemoved(body_get));
1143}
1144
1145
1146// void DO_CAL2() {
1147// int i = 1;
1148// int[] w = new int[80];
1149// int t = 0;
1150// while (i < 80) {
1151// w[i] = PLEASE_INTERLEAVE(w[i - 1], 1) // <-- removed
1152// t = PLEASE_SELECT(w[i], t);
1153// w[i] = PLEASE_INTERLEAVE(w[i - 1], 1) // <-- removed
1154// t = PLEASE_SELECT(w[i], t);
1155// w[i] = PLEASE_INTERLEAVE(w[i - 1], 1) // <-- kept
1156// t = PLEASE_SELECT(w[i], t);
1157// i++;
1158// }
1159// return t;
1160// }
1161TEST_F(LoadStoreEliminationTest, ArrayLoopOverlap2) {
1162 CreateGraph();
1163 AdjacencyListGraph blocks(graph_,
1164 GetAllocator(),
1165 "entry",
1166 "exit",
1167 { { "entry", "loop_pre_header" },
1168 { "loop_pre_header", "loop_entry" },
1169 { "loop_entry", "loop_body" },
1170 { "loop_entry", "loop_post" },
1171 { "loop_body", "loop_entry" },
1172 { "loop_post", "exit" } });
1173#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1174 GET_BLOCK(entry);
1175 GET_BLOCK(loop_pre_header);
1176 GET_BLOCK(loop_entry);
1177 GET_BLOCK(loop_body);
1178 GET_BLOCK(loop_post);
1179 GET_BLOCK(exit);
1180#undef GET_BLOCK
1181
1182 HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
1183 HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
1184 HInstruction* eighty_const = graph_->GetConstant(DataType::Type::kInt32, 80);
1185 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1186 entry->AddInstruction(entry_goto);
1187
1188 HInstruction* alloc_w = new (GetAllocator()) HNewArray(zero_const, eighty_const, 0, 0);
1189 HInstruction* pre_header_goto = new (GetAllocator()) HGoto();
1190 loop_pre_header->AddInstruction(alloc_w);
1191 loop_pre_header->AddInstruction(pre_header_goto);
1192 // environment
1193 ArenaVector<HInstruction*> alloc_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1194 ManuallyBuildEnvFor(alloc_w, &alloc_locals);
1195
1196 // loop-start
1197 HPhi* i_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
1198 HPhi* t_phi = new (GetAllocator()) HPhi(GetAllocator(), 1, 0, DataType::Type::kInt32);
1199 HInstruction* suspend = new (GetAllocator()) HSuspendCheck();
1200 HInstruction* i_cmp_top = new (GetAllocator()) HGreaterThanOrEqual(i_phi, eighty_const);
1201 HInstruction* loop_start_branch = new (GetAllocator()) HIf(i_cmp_top);
1202 loop_entry->AddPhi(i_phi);
1203 loop_entry->AddPhi(t_phi);
1204 loop_entry->AddInstruction(suspend);
1205 loop_entry->AddInstruction(i_cmp_top);
1206 loop_entry->AddInstruction(loop_start_branch);
1207 CHECK_EQ(loop_entry->GetSuccessors().size(), 2u);
1208 if (loop_entry->GetNormalSuccessors()[1] != loop_body) {
1209 loop_entry->SwapSuccessors();
1210 }
1211 CHECK_EQ(loop_entry->GetPredecessors().size(), 2u);
1212 if (loop_entry->GetPredecessors()[0] != loop_pre_header) {
1213 loop_entry->SwapPredecessors();
1214 }
1215 i_phi->AddInput(one_const);
1216 t_phi->AddInput(zero_const);
1217
1218 // environment
1219 ArenaVector<HInstruction*> suspend_locals({ alloc_w, i_phi, t_phi },
1220 GetAllocator()->Adapter(kArenaAllocInstruction));
1221 ManuallyBuildEnvFor(suspend, &suspend_locals);
1222
1223 // BODY
1224 HInstruction* last_i = new (GetAllocator()) HSub(DataType::Type::kInt32, i_phi, one_const);
1225 HInstruction* last_get_1, *last_get_2, *last_get_3;
1226 HInstruction* body_value_1, *body_value_2, *body_value_3;
1227 HInstruction* body_set_1, *body_set_2, *body_set_3;
1228 HInstruction* body_get_1, *body_get_2, *body_get_3;
1229 HInstruction* t_next_1, *t_next_2, *t_next_3;
1230 auto make_instructions = [&](HInstruction* last_t_value) {
1231 HInstruction* last_get =
1232 new (GetAllocator()) HArrayGet(alloc_w, last_i, DataType::Type::kInt32, 0);
1233 HInvoke* body_value = new (GetAllocator())
1234 HInvokeStaticOrDirect(GetAllocator(),
1235 2,
1236 DataType::Type::kInt32,
1237 0,
1238 { nullptr, 0 },
1239 nullptr,
1240 {},
1241 InvokeType::kStatic,
1242 { nullptr, 0 },
1243 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1244 body_value->SetRawInputAt(0, last_get);
1245 body_value->SetRawInputAt(1, one_const);
1246 HInstruction* body_set =
1247 new (GetAllocator()) HArraySet(alloc_w, i_phi, body_value, DataType::Type::kInt32, 0);
1248 HInstruction* body_get =
1249 new (GetAllocator()) HArrayGet(alloc_w, i_phi, DataType::Type::kInt32, 0);
1250 HInvoke* t_next = new (GetAllocator())
1251 HInvokeStaticOrDirect(GetAllocator(),
1252 2,
1253 DataType::Type::kInt32,
1254 0,
1255 { nullptr, 0 },
1256 nullptr,
1257 {},
1258 InvokeType::kStatic,
1259 { nullptr, 0 },
1260 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1261 t_next->SetRawInputAt(0, body_get);
1262 t_next->SetRawInputAt(1, last_t_value);
1263 loop_body->AddInstruction(last_get);
1264 loop_body->AddInstruction(body_value);
1265 loop_body->AddInstruction(body_set);
1266 loop_body->AddInstruction(body_get);
1267 loop_body->AddInstruction(t_next);
1268 return std::make_tuple(last_get, body_value, body_set, body_get, t_next);
1269 };
1270 std::tie(last_get_1, body_value_1, body_set_1, body_get_1, t_next_1) = make_instructions(t_phi);
1271 std::tie(last_get_2, body_value_2, body_set_2, body_get_2, t_next_2) =
1272 make_instructions(t_next_1);
1273 std::tie(last_get_3, body_value_3, body_set_3, body_get_3, t_next_3) =
1274 make_instructions(t_next_2);
1275 HInstruction* i_next = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_phi, one_const);
1276 HInstruction* body_goto = new (GetAllocator()) HGoto();
1277 loop_body->InsertInstructionBefore(last_i, last_get_1);
1278 loop_body->AddInstruction(i_next);
1279 loop_body->AddInstruction(body_goto);
1280 body_value_1->CopyEnvironmentFrom(suspend->GetEnvironment());
1281 body_value_2->CopyEnvironmentFrom(suspend->GetEnvironment());
1282 body_value_3->CopyEnvironmentFrom(suspend->GetEnvironment());
1283
1284 i_phi->AddInput(i_next);
1285 t_phi->AddInput(t_next_3);
1286 t_next_1->CopyEnvironmentFrom(suspend->GetEnvironment());
1287 t_next_2->CopyEnvironmentFrom(suspend->GetEnvironment());
1288 t_next_3->CopyEnvironmentFrom(suspend->GetEnvironment());
1289
1290 // loop-post
1291 HInstruction* return_inst = new (GetAllocator()) HReturn(t_phi);
1292 loop_post->AddInstruction(return_inst);
1293
1294 // exit
1295 HInstruction* exit_inst = new (GetAllocator()) HExit();
1296 exit->AddInstruction(exit_inst);
1297
1298 graph_->ClearDominanceInformation();
1299 graph_->ClearLoopInformation();
1300 PerformLSE();
1301
1302 // TODO Technically this is optimizable. LSE just needs to add phis to keep
1303 // track of the last `N` values set where `N` is how many locations we can go
1304 // back into the array.
1305 if (IsRemoved(last_get_1)) {
1306 // If we were able to remove the previous read the entire array should be removable.
1307 EXPECT_TRUE(IsRemoved(body_set_1));
1308 EXPECT_TRUE(IsRemoved(body_set_2));
1309 EXPECT_TRUE(IsRemoved(body_set_3));
1310 EXPECT_TRUE(IsRemoved(last_get_1));
1311 EXPECT_TRUE(IsRemoved(last_get_2));
1312 EXPECT_TRUE(IsRemoved(alloc_w));
1313 } else {
1314 // This is the branch we actually take for now. If we rely on being able to
1315 // read the array we'd better remember to write to it as well.
1316 EXPECT_FALSE(IsRemoved(body_set_3));
1317 }
1318 // The last 'get' should always be removable.
1319 EXPECT_TRUE(IsRemoved(body_get_1));
1320 EXPECT_TRUE(IsRemoved(body_get_2));
1321 EXPECT_TRUE(IsRemoved(body_get_3));
1322 // shadowed writes should always be removed
1323 EXPECT_TRUE(IsRemoved(body_set_1));
1324 EXPECT_TRUE(IsRemoved(body_set_2));
1325}
1326
1327TEST_F(LoadStoreEliminationTest, ArrayNonLoopPhi) {
1328 CreateGraph();
1329 AdjacencyListGraph blocks(graph_,
1330 GetAllocator(),
1331 "entry",
1332 "exit",
1333 { { "entry", "start" },
1334 { "start", "left" },
1335 { "start", "right" },
1336 { "left", "ret" },
1337 { "right", "ret" },
1338 { "ret", "exit" } });
1339#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1340 GET_BLOCK(entry);
1341 GET_BLOCK(start);
1342 GET_BLOCK(left);
1343 GET_BLOCK(right);
1344 GET_BLOCK(ret);
1345 GET_BLOCK(exit);
1346#undef GET_BLOCK
1347
1348 HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
1349 HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
1350 HInstruction* two_const = graph_->GetConstant(DataType::Type::kInt32, 2);
1351 HInstruction* param = new (GetAllocator())
1352 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 0, DataType::Type::kBool);
1353 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1354 entry->AddInstruction(param);
1355 entry->AddInstruction(entry_goto);
1356
1357 HInstruction* alloc_w = new (GetAllocator()) HNewArray(zero_const, two_const, 0, 0);
1358 HInstruction* branch = new (GetAllocator()) HIf(param);
1359 start->AddInstruction(alloc_w);
1360 start->AddInstruction(branch);
1361 // environment
1362 ArenaVector<HInstruction*> alloc_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1363 ManuallyBuildEnvFor(alloc_w, &alloc_locals);
1364
1365 // left
1366 HInvoke* left_value = new (GetAllocator())
1367 HInvokeStaticOrDirect(GetAllocator(),
1368 1,
1369 DataType::Type::kInt32,
1370 0,
1371 { nullptr, 0 },
1372 nullptr,
1373 {},
1374 InvokeType::kStatic,
1375 { nullptr, 0 },
1376 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1377 left_value->SetRawInputAt(0, zero_const);
1378 HInstruction* left_set_1 =
1379 new (GetAllocator()) HArraySet(alloc_w, zero_const, left_value, DataType::Type::kInt32, 0);
1380 HInstruction* left_set_2 =
1381 new (GetAllocator()) HArraySet(alloc_w, one_const, zero_const, DataType::Type::kInt32, 0);
1382 HInstruction* left_goto = new (GetAllocator()) HGoto();
1383 left->AddInstruction(left_value);
1384 left->AddInstruction(left_set_1);
1385 left->AddInstruction(left_set_2);
1386 left->AddInstruction(left_goto);
1387 ArenaVector<HInstruction*> left_locals({ alloc_w },
1388 GetAllocator()->Adapter(kArenaAllocInstruction));
1389 ManuallyBuildEnvFor(left_value, &alloc_locals);
1390
1391 // right
1392 HInvoke* right_value = new (GetAllocator())
1393 HInvokeStaticOrDirect(GetAllocator(),
1394 1,
1395 DataType::Type::kInt32,
1396 0,
1397 { nullptr, 0 },
1398 nullptr,
1399 {},
1400 InvokeType::kStatic,
1401 { nullptr, 0 },
1402 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1403 right_value->SetRawInputAt(0, one_const);
1404 HInstruction* right_set_1 =
1405 new (GetAllocator()) HArraySet(alloc_w, zero_const, right_value, DataType::Type::kInt32, 0);
1406 HInstruction* right_set_2 =
1407 new (GetAllocator()) HArraySet(alloc_w, one_const, zero_const, DataType::Type::kInt32, 0);
1408 HInstruction* right_goto = new (GetAllocator()) HGoto();
1409 right->AddInstruction(right_value);
1410 right->AddInstruction(right_set_1);
1411 right->AddInstruction(right_set_2);
1412 right->AddInstruction(right_goto);
1413 ArenaVector<HInstruction*> right_locals({ alloc_w },
1414 GetAllocator()->Adapter(kArenaAllocInstruction));
1415 ManuallyBuildEnvFor(right_value, &alloc_locals);
1416
1417 // ret
1418 HInstruction* read_1 =
1419 new (GetAllocator()) HArrayGet(alloc_w, zero_const, DataType::Type::kInt32, 0);
1420 HInstruction* read_2 =
1421 new (GetAllocator()) HArrayGet(alloc_w, one_const, DataType::Type::kInt32, 0);
1422 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, read_1, read_2);
1423 HInstruction* return_inst = new (GetAllocator()) HReturn(add);
1424 ret->AddInstruction(read_1);
1425 ret->AddInstruction(read_2);
1426 ret->AddInstruction(add);
1427 ret->AddInstruction(return_inst);
1428
1429 // exit
1430 HInstruction* exit_inst = new (GetAllocator()) HExit();
1431 exit->AddInstruction(exit_inst);
1432
1433 graph_->ClearDominanceInformation();
1434 graph_->ClearLoopInformation();
1435 PerformLSE();
1436
1437 EXPECT_TRUE(IsRemoved(read_1));
1438 EXPECT_TRUE(IsRemoved(read_2));
1439 EXPECT_TRUE(IsRemoved(left_set_1));
1440 EXPECT_TRUE(IsRemoved(left_set_2));
1441 EXPECT_TRUE(IsRemoved(right_set_1));
1442 EXPECT_TRUE(IsRemoved(right_set_2));
1443 EXPECT_TRUE(IsRemoved(alloc_w));
1444
1445 EXPECT_FALSE(IsRemoved(left_value));
1446 EXPECT_FALSE(IsRemoved(right_value));
1447}
1448
1449TEST_F(LoadStoreEliminationTest, ArrayMergeDefault) {
1450 CreateGraph();
1451 AdjacencyListGraph blocks(graph_,
1452 GetAllocator(),
1453 "entry",
1454 "exit",
1455 { { "entry", "start" },
1456 { "start", "left" },
1457 { "start", "right" },
1458 { "left", "ret" },
1459 { "right", "ret" },
1460 { "ret", "exit" } });
1461#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
1462 GET_BLOCK(entry);
1463 GET_BLOCK(start);
1464 GET_BLOCK(left);
1465 GET_BLOCK(right);
1466 GET_BLOCK(ret);
1467 GET_BLOCK(exit);
1468#undef GET_BLOCK
1469
1470 HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
1471 HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
1472 HInstruction* two_const = graph_->GetConstant(DataType::Type::kInt32, 2);
1473 HInstruction* param = new (GetAllocator())
1474 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 0, DataType::Type::kBool);
1475 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1476 entry->AddInstruction(param);
1477 entry->AddInstruction(entry_goto);
1478
1479 HInstruction* alloc_w = new (GetAllocator()) HNewArray(zero_const, two_const, 0, 0);
1480 HInstruction* branch = new (GetAllocator()) HIf(param);
1481 start->AddInstruction(alloc_w);
1482 start->AddInstruction(branch);
1483 // environment
1484 ArenaVector<HInstruction*> alloc_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1485 ManuallyBuildEnvFor(alloc_w, &alloc_locals);
1486
1487 // left
1488 HInstruction* left_set_1 =
1489 new (GetAllocator()) HArraySet(alloc_w, zero_const, one_const, DataType::Type::kInt32, 0);
1490 HInstruction* left_set_2 =
1491 new (GetAllocator()) HArraySet(alloc_w, zero_const, zero_const, DataType::Type::kInt32, 0);
1492 HInstruction* left_goto = new (GetAllocator()) HGoto();
1493 left->AddInstruction(left_set_1);
1494 left->AddInstruction(left_set_2);
1495 left->AddInstruction(left_goto);
1496
1497 // right
1498 HInstruction* right_set_1 =
1499 new (GetAllocator()) HArraySet(alloc_w, one_const, one_const, DataType::Type::kInt32, 0);
1500 HInstruction* right_set_2 =
1501 new (GetAllocator()) HArraySet(alloc_w, one_const, zero_const, DataType::Type::kInt32, 0);
1502 HInstruction* right_goto = new (GetAllocator()) HGoto();
1503 right->AddInstruction(right_set_1);
1504 right->AddInstruction(right_set_2);
1505 right->AddInstruction(right_goto);
1506
1507 // ret
1508 HInstruction* read_1 =
1509 new (GetAllocator()) HArrayGet(alloc_w, zero_const, DataType::Type::kInt32, 0);
1510 HInstruction* read_2 =
1511 new (GetAllocator()) HArrayGet(alloc_w, one_const, DataType::Type::kInt32, 0);
1512 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, read_1, read_2);
1513 HInstruction* return_inst = new (GetAllocator()) HReturn(add);
1514 ret->AddInstruction(read_1);
1515 ret->AddInstruction(read_2);
1516 ret->AddInstruction(add);
1517 ret->AddInstruction(return_inst);
1518
1519 // exit
1520 HInstruction* exit_inst = new (GetAllocator()) HExit();
1521 exit->AddInstruction(exit_inst);
1522
1523 graph_->ClearDominanceInformation();
1524 graph_->ClearLoopInformation();
1525 PerformLSE();
1526
1527 EXPECT_TRUE(IsRemoved(read_1));
1528 EXPECT_TRUE(IsRemoved(read_2));
1529 EXPECT_TRUE(IsRemoved(left_set_1));
1530 EXPECT_TRUE(IsRemoved(left_set_2));
1531 EXPECT_TRUE(IsRemoved(right_set_1));
1532 EXPECT_TRUE(IsRemoved(right_set_2));
1533 EXPECT_TRUE(IsRemoved(alloc_w));
1534}
1535
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]1536// // ENTRY
1537// obj = new Obj();
1538// // ALL should be kept
1539// switch (parameter_value) {
1540// case 1:
1541// // Case1
1542// obj.field = 1;
1543// call_func(obj);
1544// break;
1545// case 2:
1546// // Case2
1547// obj.field = 2;
1548// call_func(obj);
1549// // We don't know what obj.field is now we aren't able to eliminate the read below!
1550// break;
1551// default:
1552// // Case3
1553// // TODO This only happens because of limitations on our LSE which is unable
1554// // to materialize co-dependent loop and non-loop phis.
1555// // Ideally we'd want to generate
1556// // P1 = PHI[3, loop_val]
1557// // while (test()) {
1558// // if (test2()) { goto; } else { goto; }
1559// // loop_val = [P1, 5]
1560// // }
1561// // Currently we aren't able to unfortunately.
1562// obj.field = 3;
1563// while (test()) {
1564// if (test2()) { } else { obj.field = 5; }
1565// }
1566// break;
1567// }
1568// EXIT
1569// return obj.field
1570TEST_F(LoadStoreEliminationTest, PartialUnknownMerge) {
1571 CreateGraph();
1572 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1573 "exit",
1574 { { "entry", "bswitch" },
1575 { "bswitch", "case1" },
1576 { "bswitch", "case2" },
1577 { "bswitch", "case3" },
1578 { "case1", "breturn" },
1579 { "case2", "breturn" },
1580 { "case3", "loop_pre_header" },
1581 { "loop_pre_header", "loop_header" },
1582 { "loop_header", "loop_body" },
1583 { "loop_body", "loop_if_left" },
1584 { "loop_body", "loop_if_right" },
1585 { "loop_if_left", "loop_end" },
1586 { "loop_if_right", "loop_end" },
1587 { "loop_end", "loop_header" },
1588 { "loop_header", "breturn" },
1589 { "breturn", "exit" } }));
1590#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
1591 GET_BLOCK(entry);
1592 GET_BLOCK(bswitch);
1593 GET_BLOCK(exit);
1594 GET_BLOCK(breturn);
1595 GET_BLOCK(case1);
1596 GET_BLOCK(case2);
1597 GET_BLOCK(case3);
1598
1599 GET_BLOCK(loop_pre_header);
1600 GET_BLOCK(loop_header);
1601 GET_BLOCK(loop_body);
1602 GET_BLOCK(loop_if_left);
1603 GET_BLOCK(loop_if_right);
1604 GET_BLOCK(loop_end);
1605#undef GET_BLOCK
1606 HInstruction* switch_val = new (GetAllocator())
1607 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32);
1608 HInstruction* c1 = graph_->GetIntConstant(1);
1609 HInstruction* c2 = graph_->GetIntConstant(2);
1610 HInstruction* c3 = graph_->GetIntConstant(3);
1611 HInstruction* c5 = graph_->GetIntConstant(5);
1612 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1613 dex::TypeIndex(10),
1614 graph_->GetDexFile(),
1615 ScopedNullHandle<mirror::Class>(),
1616 false,
1617 0,
1618 false);
1619 HInstruction* new_inst =
1620 new (GetAllocator()) HNewInstance(cls,
1621 0,
1622 dex::TypeIndex(10),
1623 graph_->GetDexFile(),
1624 false,
1625 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1626 HInstruction* entry_goto = new (GetAllocator()) HGoto();
1627 entry->AddInstruction(switch_val);
1628 entry->AddInstruction(cls);
1629 entry->AddInstruction(new_inst);
1630 entry->AddInstruction(entry_goto);
1631 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1632 ManuallyBuildEnvFor(cls, &current_locals);
1633 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
1634
1635 HInstruction* switch_inst = new (GetAllocator()) HPackedSwitch(0, 2, switch_val);
1636 bswitch->AddInstruction(switch_inst);
1637
1638 HInstruction* write_c1 = new (GetAllocator()) HInstanceFieldSet(new_inst,
1639 c1,
1640 nullptr,
1641 DataType::Type::kInt32,
1642 MemberOffset(10),
1643 false,
1644 0,
1645 0,
1646 graph_->GetDexFile(),
1647 0);
1648 HInstruction* call_c1 = new (GetAllocator())
1649 HInvokeStaticOrDirect(GetAllocator(),
1650 1,
1651 DataType::Type::kVoid,
1652 0,
1653 { nullptr, 0 },
1654 nullptr,
1655 {},
1656 InvokeType::kStatic,
1657 { nullptr, 0 },
1658 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1659 HInstruction* goto_c1 = new (GetAllocator()) HGoto();
1660 call_c1->AsInvoke()->SetRawInputAt(0, new_inst);
1661 case1->AddInstruction(write_c1);
1662 case1->AddInstruction(call_c1);
1663 case1->AddInstruction(goto_c1);
1664 call_c1->CopyEnvironmentFrom(cls->GetEnvironment());
1665
1666 HInstruction* write_c2 = new (GetAllocator()) HInstanceFieldSet(new_inst,
1667 c2,
1668 nullptr,
1669 DataType::Type::kInt32,
1670 MemberOffset(10),
1671 false,
1672 0,
1673 0,
1674 graph_->GetDexFile(),
1675 0);
1676 HInstruction* call_c2 = new (GetAllocator())
1677 HInvokeStaticOrDirect(GetAllocator(),
1678 1,
1679 DataType::Type::kVoid,
1680 0,
1681 { nullptr, 0 },
1682 nullptr,
1683 {},
1684 InvokeType::kStatic,
1685 { nullptr, 0 },
1686 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1687 HInstruction* goto_c2 = new (GetAllocator()) HGoto();
1688 call_c2->AsInvoke()->SetRawInputAt(0, new_inst);
1689 case2->AddInstruction(write_c2);
1690 case2->AddInstruction(call_c2);
1691 case2->AddInstruction(goto_c2);
1692 call_c2->CopyEnvironmentFrom(cls->GetEnvironment());
1693
1694 HInstruction* write_c3 = new (GetAllocator()) HInstanceFieldSet(new_inst,
1695 c3,
1696 nullptr,
1697 DataType::Type::kInt32,
1698 MemberOffset(10),
1699 false,
1700 0,
1701 0,
1702 graph_->GetDexFile(),
1703 0);
1704 HInstruction* goto_c3 = new (GetAllocator()) HGoto();
1705 case3->AddInstruction(write_c3);
1706 case3->AddInstruction(goto_c3);
1707
1708 HInstruction* goto_preheader = new (GetAllocator()) HGoto();
1709 loop_pre_header->AddInstruction(goto_preheader);
1710
1711 HInstruction* suspend_check_header = new (GetAllocator()) HSuspendCheck();
1712 HInstruction* call_loop_header = new (GetAllocator())
1713 HInvokeStaticOrDirect(GetAllocator(),
1714 0,
1715 DataType::Type::kBool,
1716 0,
1717 { nullptr, 0 },
1718 nullptr,
1719 {},
1720 InvokeType::kStatic,
1721 { nullptr, 0 },
1722 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1723 HInstruction* if_loop_header = new (GetAllocator()) HIf(call_loop_header);
1724 loop_header->AddInstruction(suspend_check_header);
1725 loop_header->AddInstruction(call_loop_header);
1726 loop_header->AddInstruction(if_loop_header);
1727 call_loop_header->CopyEnvironmentFrom(cls->GetEnvironment());
1728 suspend_check_header->CopyEnvironmentFrom(cls->GetEnvironment());
1729
1730 HInstruction* call_loop_body = new (GetAllocator())
1731 HInvokeStaticOrDirect(GetAllocator(),
1732 0,
1733 DataType::Type::kBool,
1734 0,
1735 { nullptr, 0 },
1736 nullptr,
1737 {},
1738 InvokeType::kStatic,
1739 { nullptr, 0 },
1740 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1741 HInstruction* if_loop_body = new (GetAllocator()) HIf(call_loop_body);
1742 loop_body->AddInstruction(call_loop_body);
1743 loop_body->AddInstruction(if_loop_body);
1744 call_loop_body->CopyEnvironmentFrom(cls->GetEnvironment());
1745
1746 HInstruction* goto_loop_left = new (GetAllocator()) HGoto();
1747 loop_if_left->AddInstruction(goto_loop_left);
1748
1749 HInstruction* write_loop_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1750 c5,
1751 nullptr,
1752 DataType::Type::kInt32,
1753 MemberOffset(10),
1754 false,
1755 0,
1756 0,
1757 graph_->GetDexFile(),
1758 0);
1759 HInstruction* goto_loop_right = new (GetAllocator()) HGoto();
1760 loop_if_right->AddInstruction(write_loop_right);
1761 loop_if_right->AddInstruction(goto_loop_right);
1762
1763 HInstruction* goto_loop_end = new (GetAllocator()) HGoto();
1764 loop_end->AddInstruction(goto_loop_end);
1765
1766 HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
1767 nullptr,
1768 DataType::Type::kInt32,
1769 MemberOffset(10),
1770 false,
1771 0,
1772 0,
1773 graph_->GetDexFile(),
1774 0);
1775 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
1776 breturn->AddInstruction(read_bottom);
1777 breturn->AddInstruction(return_exit);
1778
1779 HInstruction* exit_ins = new (GetAllocator()) HExit();
1780 exit->AddInstruction(exit_ins);
1781 // PerformLSE expects this to be empty.
1782 graph_->ClearDominanceInformation();
1783 PerformLSE();
1784
1785 EXPECT_FALSE(IsRemoved(read_bottom));
1786 EXPECT_FALSE(IsRemoved(write_c1));
1787 EXPECT_FALSE(IsRemoved(write_c2));
1788 EXPECT_FALSE(IsRemoved(write_c3));
1789 // EXPECT_FALSE(IsRemoved(write_loop_left));
1790 EXPECT_FALSE(IsRemoved(write_loop_right));
1791}
1792
1793// // ENTRY
1794// obj = new Obj();
1795// if (parameter_value) {
1796// // LEFT
1797// obj.field = 1;
1798// call_func(obj);
1799// foo_r = obj.field
1800// } else {
1801// // TO BE ELIMINATED
1802// obj.field = 2;
1803// // RIGHT
1804// // TO BE ELIMINATED
1805// foo_l = obj.field;
1806// }
1807// EXIT
1808// return PHI(foo_l, foo_r)
1809TEST_F(LoadStoreEliminationTest, PartialLoadElimination) {
1810 InitGraph();
1811 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1812 "exit_REAL",
1813 { { "entry", "left" },
1814 { "entry", "right" },
1815 { "left", "exit" },
1816 { "right", "exit" },
1817 { "exit", "exit_REAL" } }));
1818 HBasicBlock* entry = blks.Get("entry");
1819 HBasicBlock* left = blks.Get("left");
1820 HBasicBlock* right = blks.Get("right");
1821 HBasicBlock* exit = blks.Get("exit");
1822 HInstruction* bool_value = new (GetAllocator())
1823 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1824 HInstruction* c1 = graph_->GetIntConstant(1);
1825 HInstruction* c2 = graph_->GetIntConstant(2);
1826 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1827 dex::TypeIndex(10),
1828 graph_->GetDexFile(),
1829 ScopedNullHandle<mirror::Class>(),
1830 false,
1831 0,
1832 false);
1833 HInstruction* new_inst =
1834 new (GetAllocator()) HNewInstance(cls,
1835 0,
1836 dex::TypeIndex(10),
1837 graph_->GetDexFile(),
1838 false,
1839 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1840 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1841 entry->AddInstruction(bool_value);
1842 entry->AddInstruction(cls);
1843 entry->AddInstruction(new_inst);
1844 entry->AddInstruction(if_inst);
1845 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1846 ManuallyBuildEnvFor(cls, &current_locals);
1847 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
1848
1849 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
1850 c1,
1851 nullptr,
1852 DataType::Type::kInt32,
1853 MemberOffset(10),
1854 false,
1855 0,
1856 0,
1857 graph_->GetDexFile(),
1858 0);
1859 HInstruction* call_left = new (GetAllocator())
1860 HInvokeStaticOrDirect(GetAllocator(),
1861 1,
1862 DataType::Type::kVoid,
1863 0,
1864 { nullptr, 0 },
1865 nullptr,
1866 {},
1867 InvokeType::kStatic,
1868 { nullptr, 0 },
1869 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
1870 HInstruction* read_left = new (GetAllocator()) HInstanceFieldGet(new_inst,
1871 nullptr,
1872 DataType::Type::kInt32,
1873 MemberOffset(16),
1874 false,
1875 0,
1876 0,
1877 graph_->GetDexFile(),
1878 0);
1879 HInstruction* goto_left = new (GetAllocator()) HGoto();
1880 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
1881 left->AddInstruction(write_left);
1882 left->AddInstruction(call_left);
1883 left->AddInstruction(read_left);
1884 left->AddInstruction(goto_left);
1885 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
1886
1887 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
1888 c2,
1889 nullptr,
1890 DataType::Type::kInt32,
1891 MemberOffset(16),
1892 false,
1893 0,
1894 0,
1895 graph_->GetDexFile(),
1896 0);
1897 HInstruction* read_right = new (GetAllocator()) HInstanceFieldGet(new_inst,
1898 nullptr,
1899 DataType::Type::kInt32,
1900 MemberOffset(16),
1901 false,
1902 0,
1903 0,
1904 graph_->GetDexFile(),
1905 0);
1906 HInstruction* goto_right = new (GetAllocator()) HGoto();
1907 right->AddInstruction(write_right);
1908 right->AddInstruction(read_right);
1909 right->AddInstruction(goto_right);
1910
1911 HInstruction* phi_final =
1912 new (GetAllocator()) HPhi(GetAllocator(), 12, 2, DataType::Type::kInt32);
1913 phi_final->SetRawInputAt(0, read_left);
1914 phi_final->SetRawInputAt(1, read_right);
1915 HInstruction* return_exit = new (GetAllocator()) HReturn(phi_final);
1916 exit->AddPhi(phi_final->AsPhi());
1917 exit->AddInstruction(return_exit);
1918
1919 // PerformLSE expects this to be empty.
1920 graph_->ClearDominanceInformation();
1921 PerformLSE();
1922
1923 ASSERT_TRUE(IsRemoved(read_right));
1924 ASSERT_FALSE(IsRemoved(read_left));
1925 ASSERT_FALSE(IsRemoved(phi_final));
1926 ASSERT_TRUE(phi_final->GetInputs()[1] == c2);
1927 ASSERT_TRUE(phi_final->GetInputs()[0] == read_left);
1928 ASSERT_TRUE(IsRemoved(write_right));
1929}
1930
1931// // ENTRY
1932// obj = new Obj();
1933// if (parameter_value) {
1934// // LEFT
1935// obj.field = 1;
1936// call_func(obj);
1937// // We don't know what obj.field is now we aren't able to eliminate the read below!
1938// } else {
1939// // DO NOT ELIMINATE
1940// obj.field = 2;
1941// // RIGHT
1942// }
1943// EXIT
1944// return obj.field
1945// TODO We eventually want to be able to eliminate the right write along with the final read but
1946// will need either new blocks or new instructions.
1947TEST_F(LoadStoreEliminationTest, PartialLoadPreserved) {
1948 InitGraph();
1949 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
1950 "exit_REAL",
1951 { { "entry", "left" },
1952 { "entry", "right" },
1953 { "left", "exit" },
1954 { "right", "exit" },
1955 { "exit", "exit_REAL" } }));
1956 HBasicBlock* entry = blks.Get("entry");
1957 HBasicBlock* left = blks.Get("left");
1958 HBasicBlock* right = blks.Get("right");
1959 HBasicBlock* exit = blks.Get("exit");
1960 HInstruction* bool_value = new (GetAllocator())
1961 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
1962 HInstruction* c1 = graph_->GetIntConstant(1);
1963 HInstruction* c2 = graph_->GetIntConstant(2);
1964 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
1965 dex::TypeIndex(10),
1966 graph_->GetDexFile(),
1967 ScopedNullHandle<mirror::Class>(),
1968 false,
1969 0,
1970 false);
1971 HInstruction* new_inst =
1972 new (GetAllocator()) HNewInstance(cls,
1973 0,
1974 dex::TypeIndex(10),
1975 graph_->GetDexFile(),
1976 false,
1977 QuickEntrypointEnum::kQuickAllocObjectInitialized);
1978 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
1979 entry->AddInstruction(bool_value);
1980 entry->AddInstruction(cls);
1981 entry->AddInstruction(new_inst);
1982 entry->AddInstruction(if_inst);
1983 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
1984 ManuallyBuildEnvFor(cls, &current_locals);
1985 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
1986
1987 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
1988 c1,
1989 nullptr,
1990 DataType::Type::kInt32,
1991 MemberOffset(10),
1992 false,
1993 0,
1994 0,
1995 graph_->GetDexFile(),
1996 0);
1997 HInstruction* call_left = new (GetAllocator())
1998 HInvokeStaticOrDirect(GetAllocator(),
1999 1,
2000 DataType::Type::kVoid,
2001 0,
2002 { nullptr, 0 },
2003 nullptr,
2004 {},
2005 InvokeType::kStatic,
2006 { nullptr, 0 },
2007 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2008 HInstruction* goto_left = new (GetAllocator()) HGoto();
2009 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
2010 left->AddInstruction(write_left);
2011 left->AddInstruction(call_left);
2012 left->AddInstruction(goto_left);
2013 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2014
2015 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
2016 c2,
2017 nullptr,
2018 DataType::Type::kInt32,
2019 MemberOffset(10),
2020 false,
2021 0,
2022 0,
2023 graph_->GetDexFile(),
2024 0);
2025 HInstruction* goto_right = new (GetAllocator()) HGoto();
2026 right->AddInstruction(write_right);
2027 right->AddInstruction(goto_right);
2028
2029 HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
2030 nullptr,
2031 DataType::Type::kInt32,
2032 MemberOffset(10),
2033 false,
2034 0,
2035 0,
2036 graph_->GetDexFile(),
2037 0);
2038 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
2039 exit->AddInstruction(read_bottom);
2040 exit->AddInstruction(return_exit);
2041 // PerformLSE expects this to be empty.
2042 graph_->ClearDominanceInformation();
2043 PerformLSE();
2044
2045 ASSERT_FALSE(IsRemoved(read_bottom));
2046 ASSERT_FALSE(IsRemoved(write_right));
2047}
2048
2049// // ENTRY
2050// obj = new Obj();
2051// if (parameter_value) {
2052// // LEFT
2053// obj.field = 1;
2054// call_func(obj);
2055// // We don't know what obj.field is now we aren't able to eliminate the read below!
2056// } else {
2057// // DO NOT ELIMINATE
2058// if (param2) {
2059// obj.field = 2;
2060// } else {
2061// obj.field = 3;
2062// }
2063// // RIGHT
2064// }
2065// EXIT
2066// return obj.field
2067// TODO We eventually want to be able to eliminate the right write along with the final read but
2068// will need either new blocks or new instructions.
2069TEST_F(LoadStoreEliminationTest, PartialLoadPreserved2) {
2070 InitGraph();
2071 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2072 "exit_REAL",
2073 { { "entry", "left" },
2074 { "entry", "right_start" },
2075 { "left", "exit" },
2076 { "right_start", "right_first" },
2077 { "right_start", "right_second" },
2078 { "right_first", "right_end" },
2079 { "right_second", "right_end" },
2080 { "right_end", "exit" },
2081 { "exit", "exit_REAL" } }));
2082 HBasicBlock* entry = blks.Get("entry");
2083 HBasicBlock* left = blks.Get("left");
2084 HBasicBlock* right_start = blks.Get("right_start");
2085 HBasicBlock* right_first = blks.Get("right_first");
2086 HBasicBlock* right_second = blks.Get("right_second");
2087 HBasicBlock* right_end = blks.Get("right_end");
2088 HBasicBlock* exit = blks.Get("exit");
2089 HInstruction* bool_value = new (GetAllocator())
2090 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
2091 HInstruction* bool_value_2 = new (GetAllocator())
2092 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 2, DataType::Type::kBool);
2093 HInstruction* c1 = graph_->GetIntConstant(1);
2094 HInstruction* c2 = graph_->GetIntConstant(2);
2095 HInstruction* c3 = graph_->GetIntConstant(3);
2096 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
2097 dex::TypeIndex(10),
2098 graph_->GetDexFile(),
2099 ScopedNullHandle<mirror::Class>(),
2100 false,
2101 0,
2102 false);
2103 HInstruction* new_inst =
2104 new (GetAllocator()) HNewInstance(cls,
2105 0,
2106 dex::TypeIndex(10),
2107 graph_->GetDexFile(),
2108 false,
2109 QuickEntrypointEnum::kQuickAllocObjectInitialized);
2110 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2111 entry->AddInstruction(bool_value);
2112 entry->AddInstruction(bool_value_2);
2113 entry->AddInstruction(cls);
2114 entry->AddInstruction(new_inst);
2115 entry->AddInstruction(if_inst);
2116 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
2117 ManuallyBuildEnvFor(cls, &current_locals);
2118 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2119
2120 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
2121 c1,
2122 nullptr,
2123 DataType::Type::kInt32,
2124 MemberOffset(10),
2125 false,
2126 0,
2127 0,
2128 graph_->GetDexFile(),
2129 0);
2130 HInstruction* call_left = new (GetAllocator())
2131 HInvokeStaticOrDirect(GetAllocator(),
2132 1,
2133 DataType::Type::kVoid,
2134 0,
2135 { nullptr, 0 },
2136 nullptr,
2137 {},
2138 InvokeType::kStatic,
2139 { nullptr, 0 },
2140 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2141 HInstruction* goto_left = new (GetAllocator()) HGoto();
2142 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
2143 left->AddInstruction(write_left);
2144 left->AddInstruction(call_left);
2145 left->AddInstruction(goto_left);
2146 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2147
2148 HInstruction* right_if = new (GetAllocator()) HIf(bool_value_2);
2149 right_start->AddInstruction(right_if);
2150
2151 HInstruction* write_right_first = new (GetAllocator()) HInstanceFieldSet(new_inst,
2152 c2,
2153 nullptr,
2154 DataType::Type::kInt32,
2155 MemberOffset(10),
2156 false,
2157 0,
2158 0,
2159 graph_->GetDexFile(),
2160 0);
2161 HInstruction* goto_right_first = new (GetAllocator()) HGoto();
2162 right_first->AddInstruction(write_right_first);
2163 right_first->AddInstruction(goto_right_first);
2164
2165 HInstruction* write_right_second = new (GetAllocator()) HInstanceFieldSet(new_inst,
2166 c3,
2167 nullptr,
2168 DataType::Type::kInt32,
2169 MemberOffset(10),
2170 false,
2171 0,
2172 0,
2173 graph_->GetDexFile(),
2174 0);
2175 HInstruction* goto_right_second = new (GetAllocator()) HGoto();
2176 right_second->AddInstruction(write_right_second);
2177 right_second->AddInstruction(goto_right_second);
2178
2179 HInstruction* goto_right_end = new (GetAllocator()) HGoto();
2180 right_end->AddInstruction(goto_right_end);
2181
2182 HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
2183 nullptr,
2184 DataType::Type::kInt32,
2185 MemberOffset(10),
2186 false,
2187 0,
2188 0,
2189 graph_->GetDexFile(),
2190 0);
2191 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
2192 exit->AddInstruction(read_bottom);
2193 exit->AddInstruction(return_exit);
2194 // PerformLSE expects this to be empty.
2195 graph_->ClearDominanceInformation();
2196 PerformLSE();
2197
2198 ASSERT_FALSE(IsRemoved(read_bottom));
2199 EXPECT_FALSE(IsRemoved(write_right_first));
2200 EXPECT_FALSE(IsRemoved(write_right_second));
2201}
2202
2203// // ENTRY
2204// obj = new Obj();
2205// if (parameter_value) {
2206// // LEFT
2207// // DO NOT ELIMINATE
2208// escape(obj);
2209// obj.field = 1;
2210// } else {
2211// // RIGHT
2212// // ELIMINATE
2213// obj.field = 2;
2214// }
2215// EXIT
2216// ELIMINATE
2217// return obj.field
2218TEST_F(LoadStoreEliminationTest, PartialLoadElimination2) {
2219 InitGraph();
2220 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2221 "exit",
2222 { { "entry", "left" },
2223 { "entry", "right" },
2224 { "left", "breturn"},
2225 { "right", "breturn" },
2226 { "breturn", "exit" } }));
2227#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2228 GET_BLOCK(entry);
2229 GET_BLOCK(exit);
2230 GET_BLOCK(breturn);
2231 GET_BLOCK(left);
2232 GET_BLOCK(right);
2233#undef GET_BLOCK
2234 HInstruction* bool_value = new (GetAllocator())
2235 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
2236 HInstruction* c1 = graph_->GetIntConstant(1);
2237 HInstruction* c2 = graph_->GetIntConstant(2);
2238 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
2239 dex::TypeIndex(10),
2240 graph_->GetDexFile(),
2241 ScopedNullHandle<mirror::Class>(),
2242 false,
2243 0,
2244 false);
2245 HInstruction* new_inst =
2246 new (GetAllocator()) HNewInstance(cls,
2247 0,
2248 dex::TypeIndex(10),
2249 graph_->GetDexFile(),
2250 false,
2251 QuickEntrypointEnum::kQuickAllocObjectInitialized);
2252 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2253 entry->AddInstruction(bool_value);
2254 entry->AddInstruction(cls);
2255 entry->AddInstruction(new_inst);
2256 entry->AddInstruction(if_inst);
2257 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
2258 ManuallyBuildEnvFor(cls, &current_locals);
2259 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2260
2261 HInstruction* call_left = new (GetAllocator())
2262 HInvokeStaticOrDirect(GetAllocator(),
2263 1,
2264 DataType::Type::kVoid,
2265 0,
2266 { nullptr, 0 },
2267 nullptr,
2268 {},
2269 InvokeType::kStatic,
2270 { nullptr, 0 },
2271 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2272 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
2273 c1,
2274 nullptr,
2275 DataType::Type::kInt32,
2276 MemberOffset(10),
2277 false,
2278 0,
2279 0,
2280 graph_->GetDexFile(),
2281 0);
2282 HInstruction* goto_left = new (GetAllocator()) HGoto();
2283 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
2284 left->AddInstruction(call_left);
2285 left->AddInstruction(write_left);
2286 left->AddInstruction(goto_left);
2287 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2288
2289 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
2290 c2,
2291 nullptr,
2292 DataType::Type::kInt32,
2293 MemberOffset(10),
2294 false,
2295 0,
2296 0,
2297 graph_->GetDexFile(),
2298 0);
2299 HInstruction* goto_right = new (GetAllocator()) HGoto();
2300 right->AddInstruction(write_right);
2301 right->AddInstruction(goto_right);
2302
2303 HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
2304 nullptr,
2305 DataType::Type::kInt32,
2306 MemberOffset(10),
2307 false,
2308 0,
2309 0,
2310 graph_->GetDexFile(),
2311 0);
2312 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
2313 breturn->AddInstruction(read_bottom);
2314 breturn->AddInstruction(return_exit);
2315
2316 HInstruction* exit_instruction = new (GetAllocator()) HExit();
2317 exit->AddInstruction(exit_instruction);
2318 // PerformLSE expects this to be empty.
2319 graph_->ClearDominanceInformation();
2320 PerformLSE();
2321
2322 EXPECT_TRUE(IsRemoved(read_bottom));
2323 EXPECT_TRUE(IsRemoved(write_right));
2324 EXPECT_FALSE(IsRemoved(write_left));
2325 EXPECT_FALSE(IsRemoved(call_left));
2326}
2327
2328// // ENTRY
2329// obj = new Obj();
2330// if (parameter_value) {
2331// // LEFT
2332// // DO NOT ELIMINATE
2333// obj.field = 1;
2334// escape(obj);
2335// return obj.field;
2336// } else {
2337// // RIGHT
2338// // ELIMINATE
2339// obj.field = 2;
2340// return obj.field;
2341// }
2342// EXIT
2343TEST_F(LoadStoreEliminationTest, PartialLoadElimination3) {
2344 InitGraph();
2345 AdjacencyListGraph blks(SetupFromAdjacencyList(
2346 "entry",
2347 "exit",
2348 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
2349#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2350 GET_BLOCK(entry);
2351 GET_BLOCK(exit);
2352 GET_BLOCK(left);
2353 GET_BLOCK(right);
2354#undef GET_BLOCK
2355 HInstruction* bool_value = new (GetAllocator())
2356 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
2357 HInstruction* c1 = graph_->GetIntConstant(1);
2358 HInstruction* c2 = graph_->GetIntConstant(2);
2359 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
2360 dex::TypeIndex(10),
2361 graph_->GetDexFile(),
2362 ScopedNullHandle<mirror::Class>(),
2363 false,
2364 0,
2365 false);
2366 HInstruction* new_inst =
2367 new (GetAllocator()) HNewInstance(cls,
2368 0,
2369 dex::TypeIndex(10),
2370 graph_->GetDexFile(),
2371 false,
2372 QuickEntrypointEnum::kQuickAllocObjectInitialized);
2373 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2374 entry->AddInstruction(bool_value);
2375 entry->AddInstruction(cls);
2376 entry->AddInstruction(new_inst);
2377 entry->AddInstruction(if_inst);
2378 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
2379 ManuallyBuildEnvFor(cls, &current_locals);
2380 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2381
2382 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
2383 c1,
2384 nullptr,
2385 DataType::Type::kInt32,
2386 MemberOffset(10),
2387 false,
2388 0,
2389 0,
2390 graph_->GetDexFile(),
2391 0);
2392 HInstruction* call_left = new (GetAllocator())
2393 HInvokeStaticOrDirect(GetAllocator(),
2394 1,
2395 DataType::Type::kVoid,
2396 0,
2397 { nullptr, 0 },
2398 nullptr,
2399 {},
2400 InvokeType::kStatic,
2401 { nullptr, 0 },
2402 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2403 HInstruction* read_left = new (GetAllocator()) HInstanceFieldGet(new_inst,
2404 nullptr,
2405 DataType::Type::kInt32,
2406 MemberOffset(10),
2407 false,
2408 0,
2409 0,
2410 graph_->GetDexFile(),
2411 0);
2412 HInstruction* return_left = new (GetAllocator()) HReturn(read_left);
2413 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
2414 left->AddInstruction(write_left);
2415 left->AddInstruction(call_left);
2416 left->AddInstruction(read_left);
2417 left->AddInstruction(return_left);
2418 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2419
2420 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
2421 c2,
2422 nullptr,
2423 DataType::Type::kInt32,
2424 MemberOffset(10),
2425 false,
2426 0,
2427 0,
2428 graph_->GetDexFile(),
2429 0);
2430 HInstruction* read_right = new (GetAllocator()) HInstanceFieldGet(new_inst,
2431 nullptr,
2432 DataType::Type::kInt32,
2433 MemberOffset(10),
2434 false,
2435 0,
2436 0,
2437 graph_->GetDexFile(),
2438 0);
2439 HInstruction* return_right = new (GetAllocator()) HReturn(read_right);
2440 right->AddInstruction(write_right);
2441 right->AddInstruction(read_right);
2442 right->AddInstruction(return_right);
2443
2444 HInstruction* exit_instruction = new (GetAllocator()) HExit();
2445 exit->AddInstruction(exit_instruction);
2446 // PerformLSE expects this to be empty.
2447 graph_->ClearDominanceInformation();
2448 PerformLSE();
2449
2450 EXPECT_TRUE(IsRemoved(read_right));
2451 EXPECT_TRUE(IsRemoved(write_right));
2452 EXPECT_FALSE(IsRemoved(write_left));
2453 EXPECT_FALSE(IsRemoved(call_left));
2454 EXPECT_FALSE(IsRemoved(read_left));
2455}
2456
2457// // ENTRY
2458// obj = new Obj();
2459// if (parameter_value) {
2460// // LEFT
2461// // DO NOT ELIMINATE
2462// obj.field = 1;
2463// while (true) {
2464// bool esc = escape(obj);
2465// // DO NOT ELIMINATE
2466// obj.field = 3;
2467// if (esc) break;
2468// }
2469// // ELIMINATE.
2470// return obj.field;
2471// } else {
2472// // RIGHT
2473// // ELIMINATE
2474// obj.field = 2;
2475// return obj.field;
2476// }
2477// EXIT
2478TEST_F(LoadStoreEliminationTest, PartialLoadElimination4) {
2479 InitGraph();
2480 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2481 "exit",
2482 { { "entry", "entry_post" },
2483 { "entry_post", "right" },
2484 { "right", "exit" },
2485 { "entry_post", "left_pre" },
2486 { "left_pre", "left_loop" },
2487 { "left_loop", "left_loop" },
2488 { "left_loop", "left_finish" },
2489 { "left_finish", "exit" } }));
2490#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2491 GET_BLOCK(entry);
2492 GET_BLOCK(entry_post);
2493 GET_BLOCK(exit);
2494 GET_BLOCK(left_pre);
2495 GET_BLOCK(left_loop);
2496 GET_BLOCK(left_finish);
2497 GET_BLOCK(right);
2498#undef GET_BLOCK
2499 // Left-loops first successor is the break.
2500 if (left_loop->GetSuccessors()[0] != left_finish) {
2501 left_loop->SwapSuccessors();
2502 }
2503 HInstruction* bool_value = new (GetAllocator())
2504 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
2505 HInstruction* c1 = graph_->GetIntConstant(1);
2506 HInstruction* c2 = graph_->GetIntConstant(2);
2507 HInstruction* c3 = graph_->GetIntConstant(3);
2508 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
2509 dex::TypeIndex(10),
2510 graph_->GetDexFile(),
2511 ScopedNullHandle<mirror::Class>(),
2512 false,
2513 0,
2514 false);
2515 HInstruction* new_inst =
2516 new (GetAllocator()) HNewInstance(cls,
2517 0,
2518 dex::TypeIndex(10),
2519 graph_->GetDexFile(),
2520 false,
2521 QuickEntrypointEnum::kQuickAllocObjectInitialized);
2522 HInstruction* goto_entry = new (GetAllocator()) HGoto();
2523 entry->AddInstruction(bool_value);
2524 entry->AddInstruction(cls);
2525 entry->AddInstruction(new_inst);
2526 entry->AddInstruction(goto_entry);
2527 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
2528 ManuallyBuildEnvFor(cls, &current_locals);
2529 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2530
2531 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2532 entry_post->AddInstruction(if_inst);
2533
2534 HInstruction* write_left_pre = new (GetAllocator()) HInstanceFieldSet(new_inst,
2535 c1,
2536 nullptr,
2537 DataType::Type::kInt32,
2538 MemberOffset(10),
2539 false,
2540 0,
2541 0,
2542 graph_->GetDexFile(),
2543 0);
2544 HInstruction* goto_left_pre = new (GetAllocator()) HGoto();
2545 left_pre->AddInstruction(write_left_pre);
2546 left_pre->AddInstruction(goto_left_pre);
2547
2548 HInstruction* suspend_left_loop = new (GetAllocator()) HSuspendCheck();
2549 HInstruction* call_left_loop = new (GetAllocator())
2550 HInvokeStaticOrDirect(GetAllocator(),
2551 1,
2552 DataType::Type::kBool,
2553 0,
2554 { nullptr, 0 },
2555 nullptr,
2556 {},
2557 InvokeType::kStatic,
2558 { nullptr, 0 },
2559 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2560 HInstruction* write_left_loop = new (GetAllocator()) HInstanceFieldSet(new_inst,
2561 c3,
2562 nullptr,
2563 DataType::Type::kInt32,
2564 MemberOffset(10),
2565 false,
2566 0,
2567 0,
2568 graph_->GetDexFile(),
2569 0);
2570 HInstruction* if_left_loop = new (GetAllocator()) HIf(call_left_loop);
2571 call_left_loop->AsInvoke()->SetRawInputAt(0, new_inst);
2572 left_loop->AddInstruction(suspend_left_loop);
2573 left_loop->AddInstruction(call_left_loop);
2574 left_loop->AddInstruction(write_left_loop);
2575 left_loop->AddInstruction(if_left_loop);
2576 suspend_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
2577 call_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
2578
2579 HInstruction* read_left_end = new (GetAllocator()) HInstanceFieldGet(new_inst,
2580 nullptr,
2581 DataType::Type::kInt32,
2582 MemberOffset(10),
2583 false,
2584 0,
2585 0,
2586 graph_->GetDexFile(),
2587 0);
2588 HInstruction* return_left_end = new (GetAllocator()) HReturn(read_left_end);
2589 left_finish->AddInstruction(read_left_end);
2590 left_finish->AddInstruction(return_left_end);
2591
2592 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
2593 c2,
2594 nullptr,
2595 DataType::Type::kInt32,
2596 MemberOffset(10),
2597 false,
2598 0,
2599 0,
2600 graph_->GetDexFile(),
2601 0);
2602 HInstruction* read_right = new (GetAllocator()) HInstanceFieldGet(new_inst,
2603 nullptr,
2604 DataType::Type::kInt32,
2605 MemberOffset(10),
2606 false,
2607 0,
2608 0,
2609 graph_->GetDexFile(),
2610 0);
2611 HInstruction* return_right = new (GetAllocator()) HReturn(read_right);
2612 right->AddInstruction(write_right);
2613 right->AddInstruction(read_right);
2614 right->AddInstruction(return_right);
2615
2616 HInstruction* exit_instruction = new (GetAllocator()) HExit();
2617 exit->AddInstruction(exit_instruction);
2618 // PerformLSE expects this to be empty.
2619 graph_->ClearDominanceInformation();
2620 PerformLSE();
2621
2622 EXPECT_FALSE(IsRemoved(write_left_pre));
2623 EXPECT_TRUE(IsRemoved(read_right));
2624 EXPECT_TRUE(IsRemoved(write_right));
2625 EXPECT_FALSE(IsRemoved(write_left_loop));
2626 EXPECT_FALSE(IsRemoved(call_left_loop));
2627 EXPECT_TRUE(IsRemoved(read_left_end));
2628}
2629
2630// // ENTRY
2631// obj = new Obj();
2632// if (parameter_value) {
2633// // LEFT
2634// // DO NOT ELIMINATE
2635// escape(obj);
2636// obj.field = 1;
2637// } else {
2638// // RIGHT
2639// // obj hasn't escaped so it's invisible.
2640// // ELIMINATE
2641// obj.field = 2;
2642// noescape();
2643// }
2644// EXIT
2645// ELIMINATE
2646// return obj.field
2647TEST_F(LoadStoreEliminationTest, PartialLoadElimination5) {
2648 InitGraph();
2649 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2650 "exit",
2651 { { "entry", "left" },
2652 { "entry", "right" },
2653 { "left", "breturn" },
2654 { "right", "breturn" },
2655 { "breturn", "exit" } }));
2656#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2657 GET_BLOCK(entry);
2658 GET_BLOCK(exit);
2659 GET_BLOCK(breturn);
2660 GET_BLOCK(left);
2661 GET_BLOCK(right);
2662#undef GET_BLOCK
2663 HInstruction* bool_value = new (GetAllocator())
2664 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
2665 HInstruction* c1 = graph_->GetIntConstant(1);
2666 HInstruction* c2 = graph_->GetIntConstant(2);
2667 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
2668 dex::TypeIndex(10),
2669 graph_->GetDexFile(),
2670 ScopedNullHandle<mirror::Class>(),
2671 false,
2672 0,
2673 false);
2674 HInstruction* new_inst =
2675 new (GetAllocator()) HNewInstance(cls,
2676 0,
2677 dex::TypeIndex(10),
2678 graph_->GetDexFile(),
2679 false,
2680 QuickEntrypointEnum::kQuickAllocObjectInitialized);
2681 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2682 entry->AddInstruction(bool_value);
2683 entry->AddInstruction(cls);
2684 entry->AddInstruction(new_inst);
2685 entry->AddInstruction(if_inst);
2686 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
2687 ManuallyBuildEnvFor(cls, &current_locals);
2688 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2689
2690 HInstruction* call_left = new (GetAllocator())
2691 HInvokeStaticOrDirect(GetAllocator(),
2692 1,
2693 DataType::Type::kVoid,
2694 0,
2695 { nullptr, 0 },
2696 nullptr,
2697 {},
2698 InvokeType::kStatic,
2699 { nullptr, 0 },
2700 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2701 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
2702 c1,
2703 nullptr,
2704 DataType::Type::kInt32,
2705 MemberOffset(10),
2706 false,
2707 0,
2708 0,
2709 graph_->GetDexFile(),
2710 0);
2711 HInstruction* goto_left = new (GetAllocator()) HGoto();
2712 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
2713 left->AddInstruction(call_left);
2714 left->AddInstruction(write_left);
2715 left->AddInstruction(goto_left);
2716 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2717
2718 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
2719 c2,
2720 nullptr,
2721 DataType::Type::kInt32,
2722 MemberOffset(10),
2723 false,
2724 0,
2725 0,
2726 graph_->GetDexFile(),
2727 0);
2728 HInstruction* call_right = new (GetAllocator())
2729 HInvokeStaticOrDirect(GetAllocator(),
2730 0,
2731 DataType::Type::kVoid,
2732 0,
2733 { nullptr, 0 },
2734 nullptr,
2735 {},
2736 InvokeType::kStatic,
2737 { nullptr, 0 },
2738 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2739 HInstruction* goto_right = new (GetAllocator()) HGoto();
2740 right->AddInstruction(write_right);
2741 right->AddInstruction(call_right);
2742 right->AddInstruction(goto_right);
2743 call_right->CopyEnvironmentFrom(cls->GetEnvironment());
2744
2745 HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
2746 nullptr,
2747 DataType::Type::kInt32,
2748 MemberOffset(10),
2749 false,
2750 0,
2751 0,
2752 graph_->GetDexFile(),
2753 0);
2754 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
2755 breturn->AddInstruction(read_bottom);
2756 breturn->AddInstruction(return_exit);
2757
2758 HInstruction* exit_instruction = new (GetAllocator()) HExit();
2759 exit->AddInstruction(exit_instruction);
2760 // PerformLSE expects this to be empty.
2761 graph_->ClearDominanceInformation();
2762 PerformLSE();
2763
2764 EXPECT_TRUE(IsRemoved(read_bottom));
2765 EXPECT_TRUE(IsRemoved(write_right));
2766 EXPECT_FALSE(IsRemoved(write_left));
2767 EXPECT_FALSE(IsRemoved(call_left));
2768 EXPECT_FALSE(IsRemoved(call_right));
2769}
2770
2771// // ENTRY
2772// obj = new Obj();
2773// // Eliminate this one. Object hasn't escaped yet so it's safe.
2774// obj.field = 3;
2775// noescape();
2776// if (parameter_value) {
2777// // LEFT
2778// // DO NOT ELIMINATE
2779// obj.field = 5;
2780// escape(obj);
2781// obj.field = 1;
2782// } else {
2783// // RIGHT
2784// // ELIMINATE
2785// obj.field = 2;
2786// }
2787// EXIT
2788// ELIMINATE
2789// return obj.field
2790TEST_F(LoadStoreEliminationTest, PartialLoadElimination6) {
2791 InitGraph();
2792 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2793 "exit",
2794 { { "entry", "left" },
2795 { "entry", "right" },
2796 { "left", "breturn" },
2797 { "right", "breturn" },
2798 { "breturn", "exit" } }));
2799#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2800 GET_BLOCK(entry);
2801 GET_BLOCK(exit);
2802 GET_BLOCK(breturn);
2803 GET_BLOCK(left);
2804 GET_BLOCK(right);
2805#undef GET_BLOCK
2806 HInstruction* bool_value = new (GetAllocator())
2807 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
2808 HInstruction* c1 = graph_->GetIntConstant(1);
2809 HInstruction* c2 = graph_->GetIntConstant(2);
2810 HInstruction* c3 = graph_->GetIntConstant(3);
2811 HInstruction* c5 = graph_->GetIntConstant(5);
2812 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
2813 dex::TypeIndex(10),
2814 graph_->GetDexFile(),
2815 ScopedNullHandle<mirror::Class>(),
2816 false,
2817 0,
2818 false);
2819 HInstruction* new_inst =
2820 new (GetAllocator()) HNewInstance(cls,
2821 0,
2822 dex::TypeIndex(10),
2823 graph_->GetDexFile(),
2824 false,
2825 QuickEntrypointEnum::kQuickAllocObjectInitialized);
2826 HInstruction* write_entry = new (GetAllocator()) HInstanceFieldSet(new_inst,
2827 c3,
2828 nullptr,
2829 DataType::Type::kInt32,
2830 MemberOffset(10),
2831 false,
2832 0,
2833 0,
2834 graph_->GetDexFile(),
2835 0);
2836 HInstruction* call_entry = new (GetAllocator())
2837 HInvokeStaticOrDirect(GetAllocator(),
2838 0,
2839 DataType::Type::kVoid,
2840 0,
2841 { nullptr, 0 },
2842 nullptr,
2843 {},
2844 InvokeType::kStatic,
2845 { nullptr, 0 },
2846 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2847 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
2848 entry->AddInstruction(bool_value);
2849 entry->AddInstruction(cls);
2850 entry->AddInstruction(new_inst);
2851 entry->AddInstruction(write_entry);
2852 entry->AddInstruction(call_entry);
2853 entry->AddInstruction(if_inst);
2854 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
2855 ManuallyBuildEnvFor(cls, &current_locals);
2856 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
2857 call_entry->CopyEnvironmentFrom(cls->GetEnvironment());
2858
2859 HInstruction* write_left_start = new (GetAllocator()) HInstanceFieldSet(new_inst,
2860 c5,
2861 nullptr,
2862 DataType::Type::kInt32,
2863 MemberOffset(10),
2864 false,
2865 0,
2866 0,
2867 graph_->GetDexFile(),
2868 0);
2869 HInstruction* call_left = new (GetAllocator())
2870 HInvokeStaticOrDirect(GetAllocator(),
2871 1,
2872 DataType::Type::kVoid,
2873 0,
2874 { nullptr, 0 },
2875 nullptr,
2876 {},
2877 InvokeType::kStatic,
2878 { nullptr, 0 },
2879 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
2880 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
2881 c1,
2882 nullptr,
2883 DataType::Type::kInt32,
2884 MemberOffset(10),
2885 false,
2886 0,
2887 0,
2888 graph_->GetDexFile(),
2889 0);
2890 HInstruction* goto_left = new (GetAllocator()) HGoto();
2891 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
2892 left->AddInstruction(write_left_start);
2893 left->AddInstruction(call_left);
2894 left->AddInstruction(write_left);
2895 left->AddInstruction(goto_left);
2896 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
2897
2898 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
2899 c2,
2900 nullptr,
2901 DataType::Type::kInt32,
2902 MemberOffset(10),
2903 false,
2904 0,
2905 0,
2906 graph_->GetDexFile(),
2907 0);
2908 HInstruction* goto_right = new (GetAllocator()) HGoto();
2909 right->AddInstruction(write_right);
2910 right->AddInstruction(goto_right);
2911
2912 HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
2913 nullptr,
2914 DataType::Type::kInt32,
2915 MemberOffset(10),
2916 false,
2917 0,
2918 0,
2919 graph_->GetDexFile(),
2920 0);
2921 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
2922 breturn->AddInstruction(read_bottom);
2923 breturn->AddInstruction(return_exit);
2924
2925 HInstruction* exit_instruction = new (GetAllocator()) HExit();
2926 exit->AddInstruction(exit_instruction);
2927 // PerformLSE expects this to be empty.
2928 graph_->ClearDominanceInformation();
2929 PerformLSE();
2930
2931 EXPECT_TRUE(IsRemoved(read_bottom));
2932 EXPECT_TRUE(IsRemoved(write_right));
2933 EXPECT_TRUE(IsRemoved(write_entry));
2934 EXPECT_FALSE(IsRemoved(write_left_start));
2935 EXPECT_FALSE(IsRemoved(write_left));
2936 EXPECT_FALSE(IsRemoved(call_left));
2937 EXPECT_FALSE(IsRemoved(call_entry));
2938}
2939
2940// // ENTRY
2941// obj = new Obj();
2942// if (parameter_value) {
2943// // LEFT
2944// // DO NOT ELIMINATE
2945// obj.field = 1;
2946// while (true) {
2947// bool esc = escape(obj);
2948// if (esc) break;
2949// // DO NOT ELIMINATE
2950// obj.field = 3;
2951// }
2952// } else {
2953// // RIGHT
2954// // DO NOT ELIMINATE
2955// obj.field = 2;
2956// }
2957// // DO NOT ELIMINATE
2958// return obj.field;
2959// EXIT
2960TEST_F(LoadStoreEliminationTest, PartialLoadPreserved3) {
2961 InitGraph();
2962 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
2963 "exit",
2964 { { "entry", "entry_post" },
2965 { "entry_post", "right" },
2966 { "right", "return_block" },
2967 { "entry_post", "left_pre" },
2968 { "left_pre", "left_loop" },
2969 { "left_loop", "left_loop_post" },
2970 { "left_loop_post", "left_loop" },
2971 { "left_loop", "return_block" },
2972 { "return_block", "exit" } }));
2973#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
2974 GET_BLOCK(entry);
2975 GET_BLOCK(entry_post);
2976 GET_BLOCK(exit);
2977 GET_BLOCK(return_block);
2978 GET_BLOCK(left_pre);
2979 GET_BLOCK(left_loop);
2980 GET_BLOCK(left_loop_post);
2981 GET_BLOCK(right);
2982#undef GET_BLOCK
2983 // Left-loops first successor is the break.
2984 if (left_loop->GetSuccessors()[0] != return_block) {
2985 left_loop->SwapSuccessors();
2986 }
2987 HInstruction* bool_value = new (GetAllocator())
2988 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
2989 HInstruction* c1 = graph_->GetIntConstant(1);
2990 HInstruction* c2 = graph_->GetIntConstant(2);
2991 HInstruction* c3 = graph_->GetIntConstant(3);
2992 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
2993 dex::TypeIndex(10),
2994 graph_->GetDexFile(),
2995 ScopedNullHandle<mirror::Class>(),
2996 false,
2997 0,
2998 false);
2999 HInstruction* new_inst =
3000 new (GetAllocator()) HNewInstance(cls,
3001 0,
3002 dex::TypeIndex(10),
3003 graph_->GetDexFile(),
3004 false,
3005 QuickEntrypointEnum::kQuickAllocObjectInitialized);
3006 HInstruction* goto_entry = new (GetAllocator()) HGoto();
3007 entry->AddInstruction(bool_value);
3008 entry->AddInstruction(cls);
3009 entry->AddInstruction(new_inst);
3010 entry->AddInstruction(goto_entry);
3011 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
3012 ManuallyBuildEnvFor(cls, &current_locals);
3013 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
3014
3015 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
3016 entry_post->AddInstruction(if_inst);
3017
3018 HInstruction* write_left_pre = new (GetAllocator()) HInstanceFieldSet(new_inst,
3019 c1,
3020 nullptr,
3021 DataType::Type::kInt32,
3022 MemberOffset(10),
3023 false,
3024 0,
3025 0,
3026 graph_->GetDexFile(),
3027 0);
3028 HInstruction* goto_left_pre = new (GetAllocator()) HGoto();
3029 left_pre->AddInstruction(write_left_pre);
3030 left_pre->AddInstruction(goto_left_pre);
3031
3032 HInstruction* suspend_left_loop = new (GetAllocator()) HSuspendCheck();
3033 HInstruction* call_left_loop = new (GetAllocator())
3034 HInvokeStaticOrDirect(GetAllocator(),
3035 1,
3036 DataType::Type::kBool,
3037 0,
3038 { nullptr, 0 },
3039 nullptr,
3040 {},
3041 InvokeType::kStatic,
3042 { nullptr, 0 },
3043 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
3044 HInstruction* if_left_loop = new (GetAllocator()) HIf(call_left_loop);
3045 call_left_loop->AsInvoke()->SetRawInputAt(0, new_inst);
3046 left_loop->AddInstruction(suspend_left_loop);
3047 left_loop->AddInstruction(call_left_loop);
3048 left_loop->AddInstruction(if_left_loop);
3049 suspend_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
3050 call_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
3051
3052 HInstruction* write_left_loop = new (GetAllocator()) HInstanceFieldSet(new_inst,
3053 c3,
3054 nullptr,
3055 DataType::Type::kInt32,
3056 MemberOffset(10),
3057 false,
3058 0,
3059 0,
3060 graph_->GetDexFile(),
3061 0);
3062 HInstruction* goto_left_loop = new (GetAllocator()) HGoto();
3063 left_loop_post->AddInstruction(write_left_loop);
3064 left_loop_post->AddInstruction(goto_left_loop);
3065
3066 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
3067 c2,
3068 nullptr,
3069 DataType::Type::kInt32,
3070 MemberOffset(10),
3071 false,
3072 0,
3073 0,
3074 graph_->GetDexFile(),
3075 0);
3076 HInstruction* goto_right = new (GetAllocator()) HGoto();
3077 right->AddInstruction(write_right);
3078 right->AddInstruction(goto_right);
3079
3080 HInstruction* read_return = new (GetAllocator()) HInstanceFieldGet(new_inst,
3081 nullptr,
3082 DataType::Type::kInt32,
3083 MemberOffset(10),
3084 false,
3085 0,
3086 0,
3087 graph_->GetDexFile(),
3088 0);
3089 HInstruction* return_final = new (GetAllocator()) HReturn(read_return);
3090 return_block->AddInstruction(read_return);
3091 return_block->AddInstruction(return_final);
3092
3093 HInstruction* exit_instruction = new (GetAllocator()) HExit();
3094 exit->AddInstruction(exit_instruction);
3095 // PerformLSE expects this to be empty.
3096 graph_->ClearDominanceInformation();
3097 PerformLSE();
3098
3099 EXPECT_FALSE(IsRemoved(write_left_pre));
3100 EXPECT_FALSE(IsRemoved(read_return));
3101 EXPECT_FALSE(IsRemoved(write_right));
3102 EXPECT_FALSE(IsRemoved(write_left_loop));
3103 EXPECT_FALSE(IsRemoved(call_left_loop));
3104}
3105
3106// // ENTRY
3107// obj = new Obj();
3108// if (parameter_value) {
3109// // LEFT
3110// // ELIMINATE (not visible since always overridden by obj.field = 3)
3111// obj.field = 1;
3112// while (true) {
3113// bool stop = should_stop();
3114// // DO NOT ELIMINATE (visible by read at end)
3115// obj.field = 3;
3116// if (stop) break;
3117// }
3118// } else {
3119// // RIGHT
3120// // DO NOT ELIMINATE
3121// obj.field = 2;
3122// escape(obj);
3123// }
3124// // DO NOT ELIMINATE
3125// return obj.field;
3126// EXIT
3127TEST_F(LoadStoreEliminationTest, PartialLoadPreserved4) {
3128 InitGraph();
3129 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
3130 "exit",
3131 { { "entry", "entry_post" },
3132 { "entry_post", "right" },
3133 { "right", "return_block" },
3134 { "entry_post", "left_pre" },
3135 { "left_pre", "left_loop" },
3136 { "left_loop", "left_loop" },
3137 { "left_loop", "return_block" },
3138 { "return_block", "exit" } }));
3139#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
3140 GET_BLOCK(entry);
3141 GET_BLOCK(entry_post);
3142 GET_BLOCK(exit);
3143 GET_BLOCK(return_block);
3144 GET_BLOCK(left_pre);
3145 GET_BLOCK(left_loop);
3146 GET_BLOCK(right);
3147#undef GET_BLOCK
3148 // Left-loops first successor is the break.
3149 if (left_loop->GetSuccessors()[0] != return_block) {
3150 left_loop->SwapSuccessors();
3151 }
3152 HInstruction* bool_value = new (GetAllocator())
3153 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
3154 HInstruction* c1 = graph_->GetIntConstant(1);
3155 HInstruction* c2 = graph_->GetIntConstant(2);
3156 HInstruction* c3 = graph_->GetIntConstant(3);
3157 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
3158 dex::TypeIndex(10),
3159 graph_->GetDexFile(),
3160 ScopedNullHandle<mirror::Class>(),
3161 false,
3162 0,
3163 false);
3164 HInstruction* new_inst =
3165 new (GetAllocator()) HNewInstance(cls,
3166 0,
3167 dex::TypeIndex(10),
3168 graph_->GetDexFile(),
3169 false,
3170 QuickEntrypointEnum::kQuickAllocObjectInitialized);
3171 HInstruction* goto_entry = new (GetAllocator()) HGoto();
3172 entry->AddInstruction(bool_value);
3173 entry->AddInstruction(cls);
3174 entry->AddInstruction(new_inst);
3175 entry->AddInstruction(goto_entry);
3176 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
3177 ManuallyBuildEnvFor(cls, &current_locals);
3178 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
3179
3180 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
3181 entry_post->AddInstruction(if_inst);
3182
3183 HInstruction* write_left_pre = new (GetAllocator()) HInstanceFieldSet(new_inst,
3184 c1,
3185 nullptr,
3186 DataType::Type::kInt32,
3187 MemberOffset(10),
3188 false,
3189 0,
3190 0,
3191 graph_->GetDexFile(),
3192 0);
3193 HInstruction* goto_left_pre = new (GetAllocator()) HGoto();
3194 left_pre->AddInstruction(write_left_pre);
3195 left_pre->AddInstruction(goto_left_pre);
3196
3197 HInstruction* suspend_left_loop = new (GetAllocator()) HSuspendCheck();
3198 HInstruction* call_left_loop = new (GetAllocator())
3199 HInvokeStaticOrDirect(GetAllocator(),
3200 0,
3201 DataType::Type::kBool,
3202 0,
3203 { nullptr, 0 },
3204 nullptr,
3205 {},
3206 InvokeType::kStatic,
3207 { nullptr, 0 },
3208 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
3209 HInstruction* write_left_loop = new (GetAllocator()) HInstanceFieldSet(new_inst,
3210 c3,
3211 nullptr,
3212 DataType::Type::kInt32,
3213 MemberOffset(10),
3214 false,
3215 0,
3216 0,
3217 graph_->GetDexFile(),
3218 0);
3219 HInstruction* if_left_loop = new (GetAllocator()) HIf(call_left_loop);
3220 left_loop->AddInstruction(suspend_left_loop);
3221 left_loop->AddInstruction(call_left_loop);
3222 left_loop->AddInstruction(write_left_loop);
3223 left_loop->AddInstruction(if_left_loop);
3224 suspend_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
3225 call_left_loop->CopyEnvironmentFrom(cls->GetEnvironment());
3226
3227 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
3228 c2,
3229 nullptr,
3230 DataType::Type::kInt32,
3231 MemberOffset(10),
3232 false,
3233 0,
3234 0,
3235 graph_->GetDexFile(),
3236 0);
3237 HInstruction* call_right = new (GetAllocator())
3238 HInvokeStaticOrDirect(GetAllocator(),
3239 1,
3240 DataType::Type::kBool,
3241 0,
3242 { nullptr, 0 },
3243 nullptr,
3244 {},
3245 InvokeType::kStatic,
3246 { nullptr, 0 },
3247 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
3248 HInstruction* goto_right = new (GetAllocator()) HGoto();
3249 call_right->AsInvoke()->SetRawInputAt(0, new_inst);
3250 right->AddInstruction(write_right);
3251 right->AddInstruction(call_right);
3252 right->AddInstruction(goto_right);
3253 call_right->CopyEnvironmentFrom(cls->GetEnvironment());
3254
3255 HInstruction* read_return = new (GetAllocator()) HInstanceFieldGet(new_inst,
3256 nullptr,
3257 DataType::Type::kInt32,
3258 MemberOffset(10),
3259 false,
3260 0,
3261 0,
3262 graph_->GetDexFile(),
3263 0);
3264 HInstruction* return_final = new (GetAllocator()) HReturn(read_return);
3265 return_block->AddInstruction(read_return);
3266 return_block->AddInstruction(return_final);
3267
3268 HInstruction* exit_instruction = new (GetAllocator()) HExit();
3269 exit->AddInstruction(exit_instruction);
3270 // PerformLSE expects this to be empty.
3271 graph_->ClearDominanceInformation();
3272 PerformLSE();
3273
3274 EXPECT_FALSE(IsRemoved(read_return));
3275 EXPECT_FALSE(IsRemoved(write_right));
3276 EXPECT_FALSE(IsRemoved(write_left_loop));
3277 EXPECT_FALSE(IsRemoved(call_left_loop));
3278 EXPECT_TRUE(IsRemoved(write_left_pre));
3279 EXPECT_FALSE(IsRemoved(call_right));
3280}
3281
3282// // ENTRY
3283// obj = new Obj();
3284// if (parameter_value) {
3285// // LEFT
3286// // DO NOT ELIMINATE
3287// escape(obj);
3288// obj.field = 1;
3289// // obj has already escaped so can't use field = 1 for value
3290// noescape();
3291// } else {
3292// // RIGHT
3293// // obj is needed for read since we don't know what the left value is
3294// // DO NOT ELIMINATE
3295// obj.field = 2;
3296// noescape();
3297// }
3298// EXIT
3299// ELIMINATE
3300// return obj.field
3301TEST_F(LoadStoreEliminationTest, PartialLoadPreserved5) {
3302 InitGraph();
3303 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
3304 "exit",
3305 { { "entry", "left" },
3306 { "entry", "right" },
3307 { "left", "breturn" },
3308 { "right", "breturn" },
3309 { "breturn", "exit" } }));
3310#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
3311 GET_BLOCK(entry);
3312 GET_BLOCK(exit);
3313 GET_BLOCK(breturn);
3314 GET_BLOCK(left);
3315 GET_BLOCK(right);
3316#undef GET_BLOCK
3317 HInstruction* bool_value = new (GetAllocator())
3318 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
3319 HInstruction* c1 = graph_->GetIntConstant(1);
3320 HInstruction* c2 = graph_->GetIntConstant(2);
3321 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
3322 dex::TypeIndex(10),
3323 graph_->GetDexFile(),
3324 ScopedNullHandle<mirror::Class>(),
3325 false,
3326 0,
3327 false);
3328 HInstruction* new_inst =
3329 new (GetAllocator()) HNewInstance(cls,
3330 0,
3331 dex::TypeIndex(10),
3332 graph_->GetDexFile(),
3333 false,
3334 QuickEntrypointEnum::kQuickAllocObjectInitialized);
3335 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
3336 entry->AddInstruction(bool_value);
3337 entry->AddInstruction(cls);
3338 entry->AddInstruction(new_inst);
3339 entry->AddInstruction(if_inst);
3340 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
3341 ManuallyBuildEnvFor(cls, &current_locals);
3342 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
3343
3344 HInstruction* call_left = new (GetAllocator())
3345 HInvokeStaticOrDirect(GetAllocator(),
3346 1,
3347 DataType::Type::kVoid,
3348 0,
3349 { nullptr, 0 },
3350 nullptr,
3351 {},
3352 InvokeType::kStatic,
3353 { nullptr, 0 },
3354 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
3355 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
3356 c1,
3357 nullptr,
3358 DataType::Type::kInt32,
3359 MemberOffset(10),
3360 false,
3361 0,
3362 0,
3363 graph_->GetDexFile(),
3364 0);
3365 HInstruction* call2_left = new (GetAllocator())
3366 HInvokeStaticOrDirect(GetAllocator(),
3367 0,
3368 DataType::Type::kVoid,
3369 0,
3370 { nullptr, 0 },
3371 nullptr,
3372 {},
3373 InvokeType::kStatic,
3374 { nullptr, 0 },
3375 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
3376 HInstruction* goto_left = new (GetAllocator()) HGoto();
3377 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
3378 left->AddInstruction(call_left);
3379 left->AddInstruction(write_left);
3380 left->AddInstruction(call2_left);
3381 left->AddInstruction(goto_left);
3382 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
3383 call2_left->CopyEnvironmentFrom(cls->GetEnvironment());
3384
3385 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
3386 c2,
3387 nullptr,
3388 DataType::Type::kInt32,
3389 MemberOffset(10),
3390 false,
3391 0,
3392 0,
3393 graph_->GetDexFile(),
3394 0);
3395 HInstruction* call_right = new (GetAllocator())
3396 HInvokeStaticOrDirect(GetAllocator(),
3397 0,
3398 DataType::Type::kVoid,
3399 0,
3400 { nullptr, 0 },
3401 nullptr,
3402 {},
3403 InvokeType::kStatic,
3404 { nullptr, 0 },
3405 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
3406 HInstruction* goto_right = new (GetAllocator()) HGoto();
3407 right->AddInstruction(write_right);
3408 right->AddInstruction(call_right);
3409 right->AddInstruction(goto_right);
3410 call_right->CopyEnvironmentFrom(cls->GetEnvironment());
3411
3412 HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
3413 nullptr,
3414 DataType::Type::kInt32,
3415 MemberOffset(10),
3416 false,
3417 0,
3418 0,
3419 graph_->GetDexFile(),
3420 0);
3421 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
3422 breturn->AddInstruction(read_bottom);
3423 breturn->AddInstruction(return_exit);
3424
3425 HInstruction* exit_instruction = new (GetAllocator()) HExit();
3426 exit->AddInstruction(exit_instruction);
3427 // PerformLSE expects this to be empty.
3428 graph_->ClearDominanceInformation();
3429 PerformLSE();
3430
3431 EXPECT_FALSE(IsRemoved(read_bottom));
3432 EXPECT_FALSE(IsRemoved(write_right));
3433 EXPECT_FALSE(IsRemoved(write_left));
3434 EXPECT_FALSE(IsRemoved(call_left));
3435 EXPECT_FALSE(IsRemoved(call_right));
3436}
3437
3438// // ENTRY
3439// obj = new Obj();
3440// DO NOT ELIMINATE. Kept by escape.
3441// obj.field = 3;
3442// noescape();
3443// if (parameter_value) {
3444// // LEFT
3445// // DO NOT ELIMINATE
3446// escape(obj);
3447// obj.field = 1;
3448// } else {
3449// // RIGHT
3450// // ELIMINATE
3451// obj.field = 2;
3452// }
3453// EXIT
3454// ELIMINATE
3455// return obj.field
3456TEST_F(LoadStoreEliminationTest, PartialLoadPreserved6) {
3457 InitGraph();
3458 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
3459 "exit",
3460 { { "entry", "left" },
3461 { "entry", "right" },
3462 { "left", "breturn" },
3463 { "right", "breturn" },
3464 { "breturn", "exit" } }));
3465#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
3466 GET_BLOCK(entry);
3467 GET_BLOCK(exit);
3468 GET_BLOCK(breturn);
3469 GET_BLOCK(left);
3470 GET_BLOCK(right);
3471#undef GET_BLOCK
3472 HInstruction* bool_value = new (GetAllocator())
3473 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kBool);
3474 HInstruction* c1 = graph_->GetIntConstant(1);
3475 HInstruction* c2 = graph_->GetIntConstant(2);
3476 HInstruction* c3 = graph_->GetIntConstant(3);
3477 HInstruction* cls = new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
3478 dex::TypeIndex(10),
3479 graph_->GetDexFile(),
3480 ScopedNullHandle<mirror::Class>(),
3481 false,
3482 0,
3483 false);
3484 HInstruction* new_inst =
3485 new (GetAllocator()) HNewInstance(cls,
3486 0,
3487 dex::TypeIndex(10),
3488 graph_->GetDexFile(),
3489 false,
3490 QuickEntrypointEnum::kQuickAllocObjectInitialized);
3491 HInstruction* write_entry = new (GetAllocator()) HInstanceFieldSet(new_inst,
3492 c3,
3493 nullptr,
3494 DataType::Type::kInt32,
3495 MemberOffset(10),
3496 false,
3497 0,
3498 0,
3499 graph_->GetDexFile(),
3500 0);
3501 HInstruction* call_entry = new (GetAllocator())
3502 HInvokeStaticOrDirect(GetAllocator(),
3503 0,
3504 DataType::Type::kVoid,
3505 0,
3506 { nullptr, 0 },
3507 nullptr,
3508 {},
3509 InvokeType::kStatic,
3510 { nullptr, 0 },
3511 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
3512 HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
3513 entry->AddInstruction(bool_value);
3514 entry->AddInstruction(cls);
3515 entry->AddInstruction(new_inst);
3516 entry->AddInstruction(write_entry);
3517 entry->AddInstruction(call_entry);
3518 entry->AddInstruction(if_inst);
3519 ArenaVector<HInstruction*> current_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
3520 ManuallyBuildEnvFor(cls, &current_locals);
3521 new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
3522 call_entry->CopyEnvironmentFrom(cls->GetEnvironment());
3523
3524 HInstruction* call_left = new (GetAllocator())
3525 HInvokeStaticOrDirect(GetAllocator(),
3526 1,
3527 DataType::Type::kVoid,
3528 0,
3529 { nullptr, 0 },
3530 nullptr,
3531 {},
3532 InvokeType::kStatic,
3533 { nullptr, 0 },
3534 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
3535 HInstruction* write_left = new (GetAllocator()) HInstanceFieldSet(new_inst,
3536 c1,
3537 nullptr,
3538 DataType::Type::kInt32,
3539 MemberOffset(10),
3540 false,
3541 0,
3542 0,
3543 graph_->GetDexFile(),
3544 0);
3545 HInstruction* goto_left = new (GetAllocator()) HGoto();
3546 call_left->AsInvoke()->SetRawInputAt(0, new_inst);
3547 left->AddInstruction(call_left);
3548 left->AddInstruction(write_left);
3549 left->AddInstruction(goto_left);
3550 call_left->CopyEnvironmentFrom(cls->GetEnvironment());
3551
3552 HInstruction* write_right = new (GetAllocator()) HInstanceFieldSet(new_inst,
3553 c2,
3554 nullptr,
3555 DataType::Type::kInt32,
3556 MemberOffset(10),
3557 false,
3558 0,
3559 0,
3560 graph_->GetDexFile(),
3561 0);
3562 HInstruction* goto_right = new (GetAllocator()) HGoto();
3563 right->AddInstruction(write_right);
3564 right->AddInstruction(goto_right);
3565
3566 HInstruction* read_bottom = new (GetAllocator()) HInstanceFieldGet(new_inst,
3567 nullptr,
3568 DataType::Type::kInt32,
3569 MemberOffset(10),
3570 false,
3571 0,
3572 0,
3573 graph_->GetDexFile(),
3574 0);
3575 HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
3576 breturn->AddInstruction(read_bottom);
3577 breturn->AddInstruction(return_exit);
3578
3579 HInstruction* exit_instruction = new (GetAllocator()) HExit();
3580 exit->AddInstruction(exit_instruction);
3581 // PerformLSE expects this to be empty.
3582 graph_->ClearDominanceInformation();
3583 PerformLSE();
3584
3585 EXPECT_TRUE(IsRemoved(read_bottom));
3586 EXPECT_TRUE(IsRemoved(write_right));
3587 EXPECT_FALSE(IsRemoved(write_entry));
3588 EXPECT_FALSE(IsRemoved(write_left));
3589 EXPECT_FALSE(IsRemoved(call_left));
3590 EXPECT_FALSE(IsRemoved(call_entry));
3591}
3592
xueliang.zhongd71f1dc2018-01-24 17:24:16 +0000[diff] [blame]3593} // namespace art