1 /*
2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "unit_test.h"
17 #include "optimizer/ir/graph_cloner.h"
18 #include "optimizer/ir/inst.h"
19 #include "optimizer/optimizations/lse.h"
20 #include "optimizer/optimizations/peepholes.h"
21
22 namespace ark::compiler {
23 class LSETest : public GraphTest {};
24
25 // NOLINTBEGIN(readability-magic-numbers)
26 /// Two consecutive loads of the same array element with leading store
TEST_F(LSETest,SimpleLoad)27 TEST_F(LSETest, SimpleLoad)
28 {
29 GRAPH(GetGraph())
30 {
31 PARAMETER(0U, 0U).ref();
32 PARAMETER(1U, 1U).s32();
33 PARAMETER(2U, 2U).s32();
34 BASIC_BLOCK(2U, -1L)
35 {
36 INST(3U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({2U, 5U});
37 INST(4U, Opcode::NullCheck).ref().Inputs(0U, 3U);
38 INST(5U, Opcode::LenArray).s32().Inputs(4U);
39 INST(6U, Opcode::BoundsCheck).s32().Inputs(5U, 2U, 3U);
40 INST(7U, Opcode::StoreArray).u32().Inputs(4U, 6U, 1U);
41 INST(8U, Opcode::SaveState).Inputs(0U, 2U).SrcVregs({2U, 5U});
42 INST(11U, Opcode::BoundsCheck).s32().Inputs(5U, 2U, 8U);
43 INST(12U, Opcode::LoadArray).s32().Inputs(4U, 11U);
44 INST(13U, Opcode::SaveState).Inputs(12U, 2U, 0U).SrcVregs({0U, 5U, 1U});
45 INST(16U, Opcode::BoundsCheck).s32().Inputs(5U, 2U, 13U);
46 INST(17U, Opcode::LoadArray).s32().Inputs(4U, 16U);
47 INST(18U, Opcode::Add).s32().Inputs(12U, 17U);
48 INST(19U, Opcode::Return).s32().Inputs(18U);
49 }
50 }
51
52 Graph *graphLsed = CreateEmptyGraph();
53 GRAPH(graphLsed)
54 {
55 PARAMETER(0U, 0U).ref();
56 PARAMETER(1U, 1U).s32();
57 PARAMETER(2U, 2U).s32();
58 BASIC_BLOCK(2U, -1L)
59 {
60 INST(3U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({2U, 5U});
61 INST(4U, Opcode::NullCheck).ref().Inputs(0U, 3U);
62 INST(5U, Opcode::LenArray).s32().Inputs(4U);
63 INST(6U, Opcode::BoundsCheck).s32().Inputs(5U, 2U, 3U);
64 INST(7U, Opcode::StoreArray).u32().Inputs(4U, 6U, 1U);
65 INST(18U, Opcode::Add).s32().Inputs(1U, 1U);
66 INST(19U, Opcode::Return).s32().Inputs(18U);
67 }
68 }
69
70 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
71 GraphChecker(GetGraph()).Check();
72 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
73 }
74
75 /// Two consecutive stores to the same array element
TEST_F(LSETest,SimpleStore)76 TEST_F(LSETest, SimpleStore)
77 {
78 GRAPH(GetGraph())
79 {
80 PARAMETER(0U, 0U).ref();
81 PARAMETER(1U, 1U).s32();
82 PARAMETER(2U, 2U).s32();
83 BASIC_BLOCK(2U, -1L)
84 {
85 INST(3U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 3U});
86 INST(4U, Opcode::NullCheck).ref().Inputs(0U, 3U);
87 INST(5U, Opcode::LenArray).s32().Inputs(4U);
88 INST(6U, Opcode::BoundsCheck).s32().Inputs(5U, 2U, 3U);
89 INST(7U, Opcode::StoreArray).u32().Inputs(4U, 6U, 1U);
90 INST(8U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 3U});
91 INST(11U, Opcode::BoundsCheck).s32().Inputs(5U, 2U, 8U);
92 INST(12U, Opcode::StoreArray).u32().Inputs(4U, 11U, 1U);
93 INST(13U, Opcode::ReturnVoid).v0id();
94 }
95 }
96 Graph *graphLsed = CreateEmptyGraph();
97 GRAPH(graphLsed)
98 {
99 PARAMETER(0U, 0U).ref();
100 PARAMETER(1U, 1U).s32();
101 PARAMETER(2U, 2U).s32();
102 BASIC_BLOCK(2U, -1L)
103 {
104 INST(3U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 3U});
105 INST(4U, Opcode::NullCheck).ref().Inputs(0U, 3U);
106 INST(5U, Opcode::LenArray).s32().Inputs(4U);
107 INST(6U, Opcode::BoundsCheck).s32().Inputs(5U, 2U, 3U);
108 INST(7U, Opcode::StoreArray).u32().Inputs(4U, 6U, 1U);
109 INST(13U, Opcode::ReturnVoid).v0id();
110 }
111 }
112 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
113 GraphChecker(GetGraph()).Check();
114 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
115 }
116
117 /// Store comes from previous basic block
SRC_GRAPH(PreviousBlocks,Graph * graph)118 SRC_GRAPH(PreviousBlocks, Graph *graph)
119 {
120 GRAPH(graph)
121 {
122 PARAMETER(0U, 0U).ref();
123 PARAMETER(1U, 1U).s32();
124 PARAMETER(2U, 2U).s32();
125 CONSTANT(8U, 0x8U).s64();
126 BASIC_BLOCK(2U, 3U, 4U)
127 {
128 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 2U, 1U);
129 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
130 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
131 }
132 BASIC_BLOCK(4U, 3U)
133 {
134 INST(15U, Opcode::LoadArray).s32().Inputs(0U, 2U);
135 INST(20U, Opcode::LoadArray).s32().Inputs(0U, 2U);
136 INST(21U, Opcode::Add).s32().Inputs(15U, 20U);
137 }
138 BASIC_BLOCK(3U, -1L)
139 {
140 INST(22U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 21U}});
141 INST(23U, Opcode::Return).s32().Inputs(22U);
142 }
143 }
144 }
145
OUT_GRAPH(PreviousBlocks,Graph * graph)146 OUT_GRAPH(PreviousBlocks, Graph *graph)
147 {
148 GRAPH(graph)
149 {
150 PARAMETER(0U, 0U).ref();
151 PARAMETER(1U, 1U).s32();
152 PARAMETER(2U, 2U).s32();
153 CONSTANT(8U, 0x8U).s64();
154 BASIC_BLOCK(2U, 3U, 4U)
155 {
156 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 2U, 1U);
157 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
158 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
159 }
160 BASIC_BLOCK(4U, 3U)
161 {
162 INST(21U, Opcode::Add).s32().Inputs(1U, 1U);
163 }
164 BASIC_BLOCK(3U, -1L)
165 {
166 INST(22U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 21U}});
167 INST(23U, Opcode::Return).s32().Inputs(22U);
168 }
169 }
170 }
171
TEST_F(LSETest,PreviousBlocks)172 TEST_F(LSETest, PreviousBlocks)
173 {
174 src_graph::PreviousBlocks::CREATE(GetGraph());
175 Graph *graphLsed = CreateEmptyGraph();
176 out_graph::PreviousBlocks::CREATE(graphLsed);
177 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
178 GraphChecker(GetGraph()).Check();
179 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
180 }
181
182 /// Loading unknown value twice
TEST_F(LSETest,LoadWithoutStore)183 TEST_F(LSETest, LoadWithoutStore)
184 {
185 GRAPH(GetGraph())
186 {
187 PARAMETER(0U, 0U).ref();
188 PARAMETER(1U, 1U).s64();
189 BASIC_BLOCK(2U, -1L)
190 {
191 INST(6U, Opcode::LoadArray).s64().Inputs(0U, 1U);
192 INST(11U, Opcode::LoadArray).s64().Inputs(0U, 1U);
193 INST(12U, Opcode::Add).s32().Inputs(6U, 11U);
194 INST(13U, Opcode::Return).s32().Inputs(12U);
195 }
196 }
197 Graph *graphLsed = CreateEmptyGraph();
198 GRAPH(graphLsed)
199 {
200 PARAMETER(0U, 0U).ref();
201 PARAMETER(1U, 1U).s64();
202 BASIC_BLOCK(2U, -1L)
203 {
204 INST(6U, Opcode::LoadArray).s64().Inputs(0U, 1U);
205 INST(12U, Opcode::Add).s32().Inputs(6U, 6U);
206 INST(13U, Opcode::Return).s32().Inputs(12U);
207 }
208 }
209 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
210 GraphChecker(GetGraph()).Check();
211 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
212 }
213
214 /// Empty basic block after elimination
TEST_F(LSETest,EmptyBB)215 TEST_F(LSETest, EmptyBB)
216 {
217 GRAPH(GetGraph())
218 {
219 PARAMETER(0U, 0U).ref();
220 PARAMETER(1U, 1U).s64();
221 BASIC_BLOCK(2U, 3U, 4U)
222 {
223 INST(6U, Opcode::LoadArray).s64().Inputs(0U, 1U);
224 INST(7U, Opcode::Compare).b().CC(CC_GT).Inputs(6U, 1U);
225 INST(8U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(7U);
226 }
227 BASIC_BLOCK(4U, 3U)
228 {
229 INST(13U, Opcode::LoadArray).s64().Inputs(0U, 1U);
230 }
231 BASIC_BLOCK(3U, -1L)
232 {
233 INST(14U, Opcode::Phi).s64().Inputs({{2U, 6U}, {4U, 13U}});
234 INST(15U, Opcode::Return).s64().Inputs(14U);
235 }
236 }
237 Graph *graphLsed = CreateEmptyGraph();
238 GRAPH(graphLsed)
239 {
240 PARAMETER(0U, 0U).ref();
241 PARAMETER(1U, 1U).s64();
242 BASIC_BLOCK(2U, 3U, 4U)
243 {
244 INST(6U, Opcode::LoadArray).s64().Inputs(0U, 1U);
245 INST(7U, Opcode::Compare).b().CC(CC_GT).Inputs(6U, 1U);
246 INST(8U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(7U);
247 }
248 BASIC_BLOCK(4U, 3U) {}
249 BASIC_BLOCK(3U, -1L)
250 {
251 INST(14U, Opcode::Phi).s64().Inputs({{2U, 6U}, {4U, 6U}});
252 INST(15U, Opcode::Return).s64().Inputs(14U);
253 }
254 }
255 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
256 GraphChecker(GetGraph()).Check();
257 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
258 }
259
260 /// Do not load constant multiple times
TEST_F(LSETest,DISABLED_PoolConstants)261 TEST_F(LSETest, DISABLED_PoolConstants)
262 {
263 GRAPH(GetGraph())
264 {
265 BASIC_BLOCK(2U, -1L)
266 {
267 INST(9U, Opcode::SaveState).NoVregs();
268 INST(6U, Opcode::LoadAndInitClass).ref().Inputs(9U);
269
270 INST(12U, Opcode::SaveState).NoVregs();
271 INST(0U, Opcode::LoadString).ref().Inputs(12U).TypeId(42U);
272 INST(1U, Opcode::StoreStatic).ref().Inputs(6U, 0U);
273
274 INST(13U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
275 INST(2U, Opcode::LoadString).ref().Inputs(13U).TypeId(27U);
276 INST(3U, Opcode::StoreStatic).ref().Inputs(6U, 2U);
277
278 INST(14U, Opcode::SaveState).Inputs(2U).SrcVregs({0U});
279 INST(4U, Opcode::LoadString).ref().Inputs(14U).TypeId(42U);
280 INST(5U, Opcode::StoreStatic).ref().Inputs(6U, 4U);
281
282 INST(21U, Opcode::ReturnVoid).v0id();
283 }
284 }
285 Graph *graphLsed = CreateEmptyGraph();
286 GRAPH(graphLsed)
287 {
288 BASIC_BLOCK(2U, -1L)
289 {
290 INST(9U, Opcode::SaveState).NoVregs();
291 INST(6U, Opcode::LoadAndInitClass).ref().Inputs(9U);
292
293 INST(12U, Opcode::SaveState).NoVregs();
294 INST(0U, Opcode::LoadString).ref().Inputs(12U).TypeId(42U);
295 INST(1U, Opcode::StoreStatic).ref().Inputs(6U, 0U);
296
297 INST(13U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
298 INST(2U, Opcode::LoadString).ref().Inputs(13U).TypeId(27U);
299 INST(3U, Opcode::StoreStatic).ref().Inputs(6U, 2U);
300
301 INST(5U, Opcode::StoreStatic).ref().Inputs(6U, 0U);
302
303 INST(21U, Opcode::ReturnVoid).v0id();
304 }
305 }
306 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
307 GraphChecker(GetGraph()).Check();
308 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
309 }
310
311 /// Eliminate object field's operations.
TEST_F(LSETest,InstanceFields)312 TEST_F(LSETest, InstanceFields)
313 {
314 GRAPH(GetGraph())
315 {
316 PARAMETER(0U, 0U).ref();
317 PARAMETER(1U, 1U).s64();
318 BASIC_BLOCK(2U, -1L)
319 {
320 INST(2U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 2U});
321 INST(3U, Opcode::NullCheck).ref().Inputs(0U, 2U);
322 INST(4U, Opcode::StoreObject).s64().Inputs(3U, 1U).TypeId(122U);
323 INST(5U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 2U});
324 INST(6U, Opcode::NullCheck).ref().Inputs(0U, 5U);
325 INST(7U, Opcode::LoadObject).s64().Inputs(6U).TypeId(122U);
326 INST(8U, Opcode::Return).s64().Inputs(7U);
327 }
328 }
329 Graph *graphLsed = CreateEmptyGraph();
330 GRAPH(graphLsed)
331 {
332 PARAMETER(0U, 0U).ref();
333 PARAMETER(1U, 1U).s64();
334 BASIC_BLOCK(2U, -1L)
335 {
336 INST(2U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 2U});
337 INST(3U, Opcode::NullCheck).ref().Inputs(0U, 2U);
338 INST(4U, Opcode::StoreObject).s64().Inputs(3U, 1U).TypeId(122U);
339 INST(8U, Opcode::Return).s64().Inputs(1U);
340 }
341 }
342 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
343 GraphChecker(GetGraph()).Check();
344 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
345 }
346
347 /// A store before branch eliminates a load after branch
TEST_F(LSETest,DominationHere)348 TEST_F(LSETest, DominationHere)
349 {
350 GRAPH(GetGraph())
351 {
352 PARAMETER(0U, 0U).ref();
353 PARAMETER(1U, 1U).s64();
354 BASIC_BLOCK(2U, 3U, 4U)
355 {
356 INST(6U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(122U);
357 INST(7U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 1U);
358 INST(8U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(7U);
359 }
360 BASIC_BLOCK(4U, 3U)
361 {
362 INST(11U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(136U);
363 }
364 BASIC_BLOCK(3U, -1L)
365 {
366 INST(14U, Opcode::LoadObject).s64().Inputs(0U).TypeId(122U);
367 INST(15U, Opcode::Return).s64().Inputs(14U);
368 }
369 }
370 Graph *graphLsed = CreateEmptyGraph();
371 GRAPH(graphLsed)
372 {
373 PARAMETER(0U, 0U).ref();
374 PARAMETER(1U, 1U).s64();
375 BASIC_BLOCK(2U, 3U, 4U)
376 {
377 INST(6U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(122U);
378 INST(7U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 1U);
379 INST(8U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(7U);
380 }
381 BASIC_BLOCK(4U, 3U)
382 {
383 INST(11U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(136U);
384 }
385 BASIC_BLOCK(3U, -1L)
386 {
387 INST(15U, Opcode::Return).s64().Inputs(1U);
388 }
389 }
390 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
391 GraphChecker(GetGraph()).Check();
392 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
393 }
394
395 /// Infer the stored value through the heap
TEST_F(LSETest,TransitiveValues)396 TEST_F(LSETest, TransitiveValues)
397 {
398 GRAPH(GetGraph())
399 {
400 PARAMETER(0U, 0U).ref();
401 PARAMETER(1U, 1U).s64();
402 BASIC_BLOCK(2U, -1L)
403 {
404 INST(4U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
405 INST(7U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
406 INST(10U, Opcode::StoreObject).s64().Inputs(0U, 7U).TypeId(243U);
407 INST(13U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
408 INST(16U, Opcode::StoreObject).s64().Inputs(0U, 13U).TypeId(243U);
409 INST(17U, Opcode::ReturnVoid).v0id();
410 }
411 }
412 Graph *graphLsed = CreateEmptyGraph();
413 GRAPH(graphLsed)
414 {
415 PARAMETER(0U, 0U).ref();
416 PARAMETER(1U, 1U).s64();
417 BASIC_BLOCK(2U, -1L)
418 {
419 INST(4U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
420 INST(17U, Opcode::ReturnVoid).v0id();
421 }
422 }
423 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
424 GraphChecker(GetGraph()).Check();
425 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
426 }
427
428 /**
429 * Tests that store of an eliminated value and store of an replacement for this
430 * eliminated value are treated as same stores.
431 */
TEST_F(LSETest,StoreEliminableDominatesStoreReplacement)432 TEST_F(LSETest, StoreEliminableDominatesStoreReplacement)
433 {
434 GRAPH(GetGraph())
435 {
436 PARAMETER(0U, 0U).ref();
437 PARAMETER(1U, 1U).s64();
438 PARAMETER(2U, 2U).ref();
439 BASIC_BLOCK(2U, -1L)
440 {
441 INST(4U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
442 // Should be replaced with v1
443 INST(7U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
444 // v5-v6 to invalidate the whole heap
445 INST(5U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 2U});
446 INST(6U, Opcode::CallStatic).s64().Inputs({{DataType::REFERENCE, 0U}, {DataType::NO_TYPE, 5U}});
447 // Here v7 and v1 are the same values. v1 is a replacement for v7
448 INST(10U, Opcode::StoreObject).s64().Inputs(2U, 7U).TypeId(243U);
449 INST(11U, Opcode::StoreObject).s64().Inputs(2U, 1U).TypeId(243U);
450 INST(17U, Opcode::ReturnVoid).v0id();
451 }
452 }
453 Graph *graphLsed = CreateEmptyGraph();
454 GRAPH(graphLsed)
455 {
456 PARAMETER(0U, 0U).ref();
457 PARAMETER(1U, 1U).s64();
458 PARAMETER(2U, 2U).ref();
459 BASIC_BLOCK(2U, -1L)
460 {
461 INST(4U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
462 INST(5U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 2U});
463 INST(6U, Opcode::CallStatic).s64().Inputs({{DataType::REFERENCE, 0U}, {DataType::NO_TYPE, 5U}});
464 INST(10U, Opcode::StoreObject).s64().Inputs(2U, 1U).TypeId(243U);
465 INST(17U, Opcode::ReturnVoid).v0id();
466 }
467 }
468 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
469 GraphChecker(GetGraph()).Check();
470 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
471 }
472
473 /**
474 * Tests that store of an eliminated value and store of an replacement for this
475 * eliminated value are treated as same stores.
476 */
TEST_F(LSETest,StoreReplacementDominatesStoreEliminable)477 TEST_F(LSETest, StoreReplacementDominatesStoreEliminable)
478 {
479 GRAPH(GetGraph())
480 {
481 PARAMETER(0U, 0U).ref();
482 PARAMETER(1U, 1U).s64();
483 PARAMETER(2U, 2U).ref();
484 BASIC_BLOCK(2U, -1L)
485 {
486 INST(4U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
487 // Should be replaced with v1
488 INST(7U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
489 // v5-v6 to invalidate the whole heap
490 INST(5U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 2U});
491 INST(6U, Opcode::CallStatic).s64().Inputs({{DataType::REFERENCE, 0U}, {DataType::NO_TYPE, 5U}});
492 // Here v7 and v1 are the same values. v1 is a replacement for v7
493 INST(10U, Opcode::StoreObject).s64().Inputs(2U, 1U).TypeId(243U);
494 INST(11U, Opcode::StoreObject).s64().Inputs(2U, 7U).TypeId(243U);
495 INST(17U, Opcode::ReturnVoid).v0id();
496 }
497 }
498 Graph *graphLsed = CreateEmptyGraph();
499 GRAPH(graphLsed)
500 {
501 PARAMETER(0U, 0U).ref();
502 PARAMETER(1U, 1U).s64();
503 PARAMETER(2U, 2U).ref();
504 BASIC_BLOCK(2U, -1L)
505 {
506 INST(4U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
507 INST(5U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 2U});
508 INST(6U, Opcode::CallStatic).s64().Inputs({{DataType::REFERENCE, 0U}, {DataType::NO_TYPE, 5U}});
509 INST(10U, Opcode::StoreObject).s64().Inputs(2U, 1U).TypeId(243U);
510 INST(17U, Opcode::ReturnVoid).v0id();
511 }
512 }
513 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
514 GraphChecker(GetGraph()).Check();
515 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
516 }
517
518 /// Load elimination in loop by means of a dominated load
SRC_GRAPH(LoopElimination,Graph * graph)519 SRC_GRAPH(LoopElimination, Graph *graph)
520 {
521 GRAPH(graph)
522 {
523 PARAMETER(0U, 0U).ref();
524 CONSTANT(7U, 0x0U).s64();
525 CONSTANT(28U, 0x1U).s64();
526 BASIC_BLOCK(2U, 3U, 4U)
527 {
528 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U);
529 INST(6U, Opcode::LenArray).s32().Inputs(3U);
530 INST(30U, Opcode::Cmp).s32().Inputs(7U, 6U);
531 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(30U, 7U);
532 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
533 }
534 // For (v10 = 0, v10 < lenarr(v3), ++v10)
535 // v11 += v3[v10]
536 BASIC_BLOCK(4U, 3U, 4U)
537 {
538 INST(10U, Opcode::Phi).s32().Inputs({{2U, 7U}, {4U, 27U}});
539 INST(11U, Opcode::Phi).s32().Inputs({{2U, 7U}, {4U, 26U}});
540
541 INST(20U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U); // Eliminable due to checked access above
542
543 INST(25U, Opcode::LoadArray).s32().Inputs(20U, 10U);
544
545 INST(26U, Opcode::Add).s32().Inputs(25U, 11U);
546 INST(27U, Opcode::Add).s32().Inputs(10U, 28U);
547 INST(16U, Opcode::Compare).b().CC(CC_GE).Inputs(27U, 6U);
548 INST(17U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(16U);
549 }
550 BASIC_BLOCK(3U, -1L)
551 {
552 INST(35U, Opcode::Phi).s32().Inputs({{4U, 26U}, {2U, 7U}});
553 INST(29U, Opcode::Return).s32().Inputs(35U);
554 }
555 }
556 }
557
OUT_GRAPH(LoopElimination,Graph * graph)558 OUT_GRAPH(LoopElimination, Graph *graph)
559 {
560 GRAPH(graph)
561 {
562 PARAMETER(0U, 0U).ref();
563 CONSTANT(7U, 0x0U).s64();
564 CONSTANT(28U, 0x1U).s64();
565 BASIC_BLOCK(2U, 3U, 4U)
566 {
567 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U);
568 INST(6U, Opcode::LenArray).s32().Inputs(3U);
569 INST(30U, Opcode::Cmp).s32().Inputs(7U, 6U);
570 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(30U, 7U);
571 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
572 }
573 // For (v10 = 0, v10 < lenarr(v3), ++v10)
574 // v11 += v3[v10]
575 BASIC_BLOCK(4U, 3U, 4U)
576 {
577 INST(10U, Opcode::Phi).s32().Inputs({{2U, 7U}, {4U, 27U}});
578 INST(11U, Opcode::Phi).s32().Inputs({{2U, 7U}, {4U, 26U}});
579
580 INST(25U, Opcode::LoadArray).s32().Inputs(3U, 10U);
581
582 INST(26U, Opcode::Add).s32().Inputs(25U, 11U);
583 INST(27U, Opcode::Add).s32().Inputs(10U, 28U);
584 INST(16U, Opcode::Compare).b().CC(CC_GE).Inputs(27U, 6U);
585 INST(17U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(16U);
586 }
587 BASIC_BLOCK(3U, -1L)
588 {
589 INST(35U, Opcode::Phi).s32().Inputs({{4U, 26U}, {2U, 7U}});
590 INST(29U, Opcode::Return).s32().Inputs(35U);
591 }
592 }
593 }
594
TEST_F(LSETest,LoopElimination)595 TEST_F(LSETest, LoopElimination)
596 {
597 src_graph::LoopElimination::CREATE(GetGraph());
598 Graph *graphLsed = CreateEmptyGraph();
599 out_graph::LoopElimination::CREATE(graphLsed);
600 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
601 GraphChecker(GetGraph()).Check();
602 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
603 }
604
605 /// Loop of multiple blocks
SRC_GRAPH(LoopBranches,Graph * graph)606 SRC_GRAPH(LoopBranches, Graph *graph)
607 {
608 GRAPH(graph)
609 {
610 PARAMETER(0U, 0U).ref();
611 CONSTANT(7U, 0x0U).s64();
612 CONSTANT(8U, 0x2U).s64();
613 CONSTANT(37U, 0x1U).s64();
614 BASIC_BLOCK(2U, 3U, 4U)
615 {
616 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U);
617 INST(6U, Opcode::LenArray).s32().Inputs(3U);
618 INST(48U, Opcode::Compare).b().CC(CC_GE).Inputs(7U, 6U);
619 INST(49U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(48U);
620 }
621 // For (v11 = 0, v11 < lenarr(v3), ++v11)
622 BASIC_BLOCK(4U, 5U, 6U)
623 {
624 INST(11U, Opcode::Phi).s32().Inputs({{2U, 7U}, {7U, 46U}});
625 INST(12U, Opcode::Phi).s32().Inputs({{2U, 7U}, {7U, 45U}});
626 INST(22U, Opcode::Mod).s32().Inputs(11U, 8U);
627 INST(23U, Opcode::Compare).b().CC(CC_EQ).Inputs(22U, 7U);
628 INST(24U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(23U);
629 }
630 // If (v11 % 2 == 1)
631 // v44 = v3[v11]
632 BASIC_BLOCK(6U, 7U)
633 {
634 INST(27U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U); // Eliminable due to checked access above
635 INST(32U, Opcode::LoadArray).s32().Inputs(27U, 11U);
636 }
637 // else
638 // v44 = v3[v11 + 1]
639 BASIC_BLOCK(5U, 7U)
640 {
641 INST(35U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U); // Eliminable due to checked access above
642 INST(36U, Opcode::Add).s32().Inputs(11U, 37U);
643 INST(42U, Opcode::LoadArray).s32().Inputs(35U, 36U);
644 }
645 // v12 += v44
646 BASIC_BLOCK(7U, 3U, 4U)
647 {
648 INST(44U, Opcode::Phi).s32().Inputs({{6U, 32U}, {5U, 42U}});
649 INST(45U, Opcode::Add).s32().Inputs(44U, 12U);
650 INST(46U, Opcode::Add).s32().Inputs(11U, 37U);
651 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(46U, 6U);
652 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
653 }
654 BASIC_BLOCK(3U, -1L)
655 {
656 INST(51U, Opcode::Phi).s32().Inputs({{7U, 45U}, {2U, 7U}});
657 INST(47U, Opcode::Return).s32().Inputs(51U);
658 }
659 }
660 }
661
OUT_GRAPH(LoopBranches,Graph * graph)662 OUT_GRAPH(LoopBranches, Graph *graph)
663 {
664 GRAPH(graph)
665 {
666 PARAMETER(0U, 0U).ref();
667 CONSTANT(7U, 0x0U).s64();
668 CONSTANT(8U, 0x2U).s64();
669 CONSTANT(37U, 0x1U).s64();
670 BASIC_BLOCK(2U, 3U, 4U)
671 {
672 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U);
673 INST(6U, Opcode::LenArray).s32().Inputs(3U);
674 INST(48U, Opcode::Compare).b().CC(CC_GE).Inputs(7U, 6U);
675 INST(49U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(48U);
676 }
677 // For (v11 = 0, v11 < lenarr(v3), ++v11)
678 BASIC_BLOCK(4U, 5U, 6U)
679 {
680 INST(11U, Opcode::Phi).s32().Inputs({{2U, 7U}, {7U, 46U}});
681 INST(12U, Opcode::Phi).s32().Inputs({{2U, 7U}, {7U, 45U}});
682 INST(22U, Opcode::Mod).s32().Inputs(11U, 8U);
683 INST(23U, Opcode::Compare).b().CC(CC_EQ).Inputs(22U, 7U);
684 INST(24U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(23U);
685 }
686 // If (v11 % 2 == 1)
687 // v44 = v3[v11]
688 BASIC_BLOCK(6U, 7U)
689 {
690 INST(32U, Opcode::LoadArray).s32().Inputs(3U, 11U);
691 }
692 // else
693 // v44 = v3[v11 + 1]
694 BASIC_BLOCK(5U, 7U)
695 {
696 INST(36U, Opcode::Add).s32().Inputs(11U, 37U);
697 INST(42U, Opcode::LoadArray).s32().Inputs(3U, 36U);
698 }
699 // v12 += v44
700 BASIC_BLOCK(7U, 3U, 4U)
701 {
702 INST(44U, Opcode::Phi).s32().Inputs({{6U, 32U}, {5U, 42U}});
703 INST(45U, Opcode::Add).s32().Inputs(44U, 12U);
704 INST(46U, Opcode::Add).s32().Inputs(11U, 37U);
705 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(46U, 6U);
706 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
707 }
708 BASIC_BLOCK(3U, -1L)
709 {
710 INST(51U, Opcode::Phi).s32().Inputs({{7U, 45U}, {2U, 7U}});
711 INST(47U, Opcode::Return).s32().Inputs(51U);
712 }
713 }
714 }
715
TEST_F(LSETest,LoopBranches)716 TEST_F(LSETest, LoopBranches)
717 {
718 src_graph::LoopBranches::CREATE(GetGraph());
719 Graph *graphLsed = CreateEmptyGraph();
720 out_graph::LoopBranches::CREATE(graphLsed);
721 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
722 GraphChecker(GetGraph()).Check();
723 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
724 }
725
726 /// Nested loop elimination
SRC_GRAPH(NestedLoopElimination,Graph * graph)727 SRC_GRAPH(NestedLoopElimination, Graph *graph)
728 {
729 GRAPH(graph)
730 {
731 PARAMETER(0U, 0U).ref();
732 PARAMETER(1U, 1U).ref();
733 CONSTANT(11U, 0x0U).s64();
734 CONSTANT(62U, 0x1U).s64();
735 BASIC_BLOCK(2U, 8U)
736 {
737 INST(4U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(181U);
738 INST(7U, Opcode::LoadObject).ref().Inputs(0U).TypeId(195U);
739 INST(10U, Opcode::LenArray).s32().Inputs(7U);
740 }
741 // For (v14 = 0, v14 < lenarr(v7), v14++)
742 BASIC_BLOCK(8U, 3U, 4U)
743 {
744 INST(14U, Opcode::Phi).s32().Inputs({{2U, 11U}, {5U, 63U}});
745 INST(15U, Opcode::Phi).s32().Inputs({{2U, 11U}, {5U, 69U}});
746 INST(20U, Opcode::Cmp).s32().Inputs(14U, 10U);
747 INST(21U, Opcode::Compare).b().CC(CC_GE).Inputs(20U, 11U);
748 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
749 }
750 BASIC_BLOCK(4U, 5U, 6U)
751 {
752 INST(25U, Opcode::LoadObject).ref().Inputs(0U).TypeId(209U);
753 INST(28U, Opcode::LenArray).s32().Inputs(25U);
754 INST(65U, Opcode::Cmp).s32().Inputs(11U, 28U);
755 INST(66U, Opcode::Compare).b().CC(CC_GE).Inputs(65U, 11U);
756 INST(67U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(66U);
757 }
758 // For (v35 = 0, v35 < lenarr(v25), v35++)
759 // v32 += (v7[v14] * v25[v35])
760 BASIC_BLOCK(6U, 5U, 6U)
761 {
762 INST(32U, Opcode::Phi).s32().Inputs({{4U, 15U}, {6U, 60U}});
763 INST(35U, Opcode::Phi).s32().Inputs({{4U, 11U}, {6U, 61U}});
764 INST(45U, Opcode::LoadObject).ref().Inputs(0U).TypeId(195U); // Already loaded in BB2
765 INST(50U, Opcode::LoadArray).s32().Inputs(45U, 14U);
766 INST(53U, Opcode::LoadObject).ref().Inputs(0U).TypeId(209U); // Already loaded in BB4
767 INST(58U, Opcode::LoadArray).s32().Inputs(53U, 35U);
768 INST(59U, Opcode::Mul).s32().Inputs(50U, 58U);
769 INST(60U, Opcode::Add).s32().Inputs(59U, 32U);
770 INST(61U, Opcode::Add).s32().Inputs(35U, 62U);
771 INST(40U, Opcode::Cmp).s32().Inputs(61U, 28U);
772 INST(41U, Opcode::Compare).b().CC(CC_GE).Inputs(40U, 11U);
773 INST(42U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(41U);
774 }
775 BASIC_BLOCK(5U, 8U)
776 {
777 INST(69U, Opcode::Phi).s32().Inputs({{6U, 60U}, {4U, 15U}});
778 INST(63U, Opcode::Add).s32().Inputs(14U, 62U);
779 }
780 BASIC_BLOCK(3U, -1L)
781 {
782 INST(64U, Opcode::Return).s32().Inputs(15U);
783 }
784 }
785 }
786
OUT_GRAPH(NestedLoopElimination,Graph * graph)787 OUT_GRAPH(NestedLoopElimination, Graph *graph)
788 {
789 GRAPH(graph)
790 {
791 PARAMETER(0U, 0U).ref();
792 PARAMETER(1U, 1U).ref();
793 CONSTANT(11U, 0x0U).s64();
794 CONSTANT(62U, 0x1U).s64();
795 BASIC_BLOCK(2U, 8U)
796 {
797 INST(4U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(181U);
798 INST(7U, Opcode::LoadObject).ref().Inputs(0U).TypeId(195U);
799 INST(10U, Opcode::LenArray).s32().Inputs(7U);
800 }
801 // For (v14 = 0, v14 < lenarr(v7), v14++)
802 BASIC_BLOCK(8U, 3U, 4U)
803 {
804 INST(14U, Opcode::Phi).s32().Inputs({{2U, 11U}, {5U, 63U}});
805 INST(15U, Opcode::Phi).s32().Inputs({{2U, 11U}, {5U, 69U}});
806 INST(20U, Opcode::Cmp).s32().Inputs(14U, 10U);
807 INST(21U, Opcode::Compare).b().CC(CC_GE).Inputs(20U, 11U);
808 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
809 }
810 BASIC_BLOCK(4U, 5U, 6U)
811 {
812 INST(25U, Opcode::LoadObject).ref().Inputs(0U).TypeId(209U);
813 INST(28U, Opcode::LenArray).s32().Inputs(25U);
814 INST(65U, Opcode::Cmp).s32().Inputs(11U, 28U);
815 INST(66U, Opcode::Compare).b().CC(CC_GE).Inputs(65U, 11U);
816 INST(67U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(66U);
817 }
818 // For (v35 = 0, v35 < lenarr(v25), v35++)
819 // v32 += (v7[v14] * v25[v35])
820 BASIC_BLOCK(6U, 5U, 6U)
821 {
822 INST(32U, Opcode::Phi).s32().Inputs({{4U, 15U}, {6U, 60U}});
823 INST(35U, Opcode::Phi).s32().Inputs({{4U, 11U}, {6U, 61U}});
824 INST(50U, Opcode::LoadArray).s32().Inputs(7U, 14U);
825 INST(58U, Opcode::LoadArray).s32().Inputs(25U, 35U);
826 INST(59U, Opcode::Mul).s32().Inputs(50U, 58U);
827 INST(60U, Opcode::Add).s32().Inputs(59U, 32U);
828 INST(61U, Opcode::Add).s32().Inputs(35U, 62U);
829 INST(40U, Opcode::Cmp).s32().Inputs(61U, 28U);
830 INST(41U, Opcode::Compare).b().CC(CC_GE).Inputs(40U, 11U);
831 INST(42U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(41U);
832 }
833 BASIC_BLOCK(5U, 8U)
834 {
835 INST(69U, Opcode::Phi).s32().Inputs({{6U, 60U}, {4U, 15U}});
836 INST(63U, Opcode::Add).s32().Inputs(14U, 62U);
837 }
838 BASIC_BLOCK(3U, -1L)
839 {
840 INST(64U, Opcode::Return).s32().Inputs(15U);
841 }
842 }
843 }
844
TEST_F(LSETest,NestedLoopElimination)845 TEST_F(LSETest, NestedLoopElimination)
846 {
847 src_graph::NestedLoopElimination::CREATE(GetGraph());
848 Graph *graphLsed = CreateEmptyGraph();
849 out_graph::NestedLoopElimination::CREATE(graphLsed);
850 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
851 GraphChecker(GetGraph()).Check();
852 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
853 }
854
855 // Replace MUST_ALIASed accesses
856 // Move out of loop NO_ALIASed accesses
SRC_GRAPH(LoopWithMayAliases,Graph * graph)857 SRC_GRAPH(LoopWithMayAliases, Graph *graph)
858 {
859 GRAPH(graph)
860 {
861 PARAMETER(0U, 0U).ref(); // i32[][]
862 CONSTANT(1U, 0x0U).s64();
863 CONSTANT(30U, 0x1U).s64();
864 BASIC_BLOCK(2U, 3U, 4U)
865 {
866 INST(6U, Opcode::LoadArray).ref().Inputs(0U, 1U);
867 INST(9U, Opcode::LenArray).s32().Inputs(6U);
868 INST(45U, Opcode::Compare).b().CC(CC_GE).Inputs(1U, 9U);
869 INST(46U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(45U);
870 }
871 // v6 = v[0]
872 // For (v12 = 0, v12 < lenarr(v0[0]), v12++)
873 // v13 += v0[0][0] + v0[1][0]
874 BASIC_BLOCK(4U, 3U, 4U)
875 {
876 INST(12U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 43U}});
877 INST(13U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 42U}});
878 INST(24U, Opcode::LoadArray).ref().Inputs(0U, 1U); // Eliminated due to v6
879 INST(29U, Opcode::LoadArray).s32().Inputs(24U, 1U);
880 INST(35U, Opcode::LoadArray).ref().Inputs(0U, 30U); // Move out of loop
881 INST(40U, Opcode::LoadArray).s32().Inputs(35U, 1U);
882 INST(41U, Opcode::Add).s32().Inputs(40U, 29U);
883 INST(42U, Opcode::Add).s32().Inputs(41U, 13U);
884 INST(43U, Opcode::Add).s32().Inputs(12U, 30U);
885 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(43U, 9U);
886 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
887 }
888 BASIC_BLOCK(3U, -1L)
889 {
890 INST(48U, Opcode::Phi).s32().Inputs({{4U, 42U}, {2U, 1U}});
891 INST(44U, Opcode::Return).s32().Inputs(48U);
892 }
893 }
894 }
895
OUT_GRAPH(LoopWithMayAliases,Graph * graph)896 OUT_GRAPH(LoopWithMayAliases, Graph *graph)
897 {
898 GRAPH(graph)
899 {
900 PARAMETER(0U, 0U).ref(); // i32[][]
901 CONSTANT(1U, 0x0U).s64();
902 CONSTANT(30U, 0x1U).s64();
903 BASIC_BLOCK(2U, 3U, 4U)
904 {
905 INST(6U, Opcode::LoadArray).ref().Inputs(0U, 1U);
906 INST(9U, Opcode::LenArray).s32().Inputs(6U);
907 INST(45U, Opcode::Compare).b().CC(CC_GE).Inputs(1U, 9U);
908 INST(35U, Opcode::LoadArray).ref().Inputs(0U, 30U);
909 INST(46U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(45U);
910 }
911 // v6 = v0[0]
912 // v35 = v0[1]
913 // For (v12 = 0, v12 < lenarr(v0[0]), v12++)
914 // v13 += v6[0] + v35[0]
915 BASIC_BLOCK(4U, 3U, 4U)
916 {
917 INST(12U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 43U}});
918 INST(13U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 42U}});
919 INST(29U, Opcode::LoadArray).s32().Inputs(6U, 1U);
920 INST(40U, Opcode::LoadArray).s32().Inputs(35U, 1U);
921 INST(41U, Opcode::Add).s32().Inputs(40U, 29U);
922 INST(42U, Opcode::Add).s32().Inputs(41U, 13U);
923 INST(43U, Opcode::Add).s32().Inputs(12U, 30U);
924 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(43U, 9U);
925 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
926 }
927 BASIC_BLOCK(3U, -1L)
928 {
929 INST(48U, Opcode::Phi).s32().Inputs({{4U, 42U}, {2U, 1U}});
930 INST(44U, Opcode::Return).s32().Inputs(48U);
931 }
932 }
933 }
934
TEST_F(LSETest,LoopWithMayAliases)935 TEST_F(LSETest, LoopWithMayAliases)
936 {
937 src_graph::LoopWithMayAliases::CREATE(GetGraph());
938 Graph *graphLsed = CreateEmptyGraph();
939 out_graph::LoopWithMayAliases::CREATE(graphLsed);
940 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
941 GraphChecker(GetGraph()).Check();
942 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
943 }
944
945 /// Loop elimination combined with regular elimination
SRC_GRAPH(CombinedWithLoop,Graph * graph)946 SRC_GRAPH(CombinedWithLoop, Graph *graph)
947 {
948 GRAPH(graph)
949 {
950 PARAMETER(0U, 0U).ref(); // i32[][]
951 CONSTANT(1U, 0x0U).s64();
952 CONSTANT(43U, 0x1U).s64();
953 BASIC_BLOCK(2U, 3U, 4U)
954 {
955 INST(6U, Opcode::LoadArray).ref().Inputs(0U, 1U);
956 INST(9U, Opcode::LenArray).s32().Inputs(6U);
957 INST(45U, Opcode::Compare).b().CC(CC_GE).Inputs(1U, 9U);
958 INST(46U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(45U);
959 }
960 // For (v12 = 0, v12 < lenarr(v0[0]), v12++)
961 // v13 += v0[0][0] + v0[0][0]
962 BASIC_BLOCK(4U, 3U, 4U)
963 {
964 INST(12U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 42U}});
965 INST(13U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 41U}});
966 INST(24U, Opcode::LoadArray).ref().Inputs(0U, 1U); // Eliminated due to v6
967 INST(29U, Opcode::LoadArray).s32().Inputs(24U, 1U);
968 INST(34U, Opcode::LoadArray).ref().Inputs(0U, 1U); // Eliminated due to v24
969 INST(39U, Opcode::LoadArray).s32().Inputs(34U, 1U); // Eliminated due to v29
970 INST(40U, Opcode::Add).s32().Inputs(39U, 29U);
971 INST(41U, Opcode::Add).s32().Inputs(40U, 13U);
972 INST(42U, Opcode::Add).s32().Inputs(12U, 43U);
973 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(42U, 9U);
974 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
975 }
976 BASIC_BLOCK(3U, -1L)
977 {
978 INST(48U, Opcode::Phi).s32().Inputs({{4U, 41U}, {2U, 1U}});
979 INST(44U, Opcode::Return).s32().Inputs(48U);
980 }
981 }
982 }
983
OUT_GRAPH(CombinedWithLoop,Graph * graph)984 OUT_GRAPH(CombinedWithLoop, Graph *graph)
985 {
986 GRAPH(graph)
987 {
988 PARAMETER(0U, 0U).ref(); // i32[][]
989 CONSTANT(1U, 0x0U).s64();
990 CONSTANT(43U, 0x1U).s64();
991 BASIC_BLOCK(2U, 3U, 4U)
992 {
993 INST(6U, Opcode::LoadArray).ref().Inputs(0U, 1U);
994 INST(9U, Opcode::LenArray).s32().Inputs(6U);
995 INST(45U, Opcode::Compare).b().CC(CC_GE).Inputs(1U, 9U);
996 INST(46U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(45U);
997 }
998 // For (v12 = 0, v12 < lenarr(v0[0]), v12++)
999 // v13 += v0[0][0] + v0[0][0]
1000 BASIC_BLOCK(4U, 3U, 4U)
1001 {
1002 INST(12U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 42U}});
1003 INST(13U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 41U}});
1004 INST(29U, Opcode::LoadArray).s32().Inputs(6U, 1U);
1005 INST(40U, Opcode::Add).s32().Inputs(29U, 29U);
1006 INST(41U, Opcode::Add).s32().Inputs(40U, 13U);
1007 INST(42U, Opcode::Add).s32().Inputs(12U, 43U);
1008 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(42U, 9U);
1009 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
1010 }
1011 BASIC_BLOCK(3U, -1L)
1012 {
1013 INST(48U, Opcode::Phi).s32().Inputs({{4U, 41U}, {2U, 1U}});
1014 INST(44U, Opcode::Return).s32().Inputs(48U);
1015 }
1016 }
1017 }
1018
TEST_F(LSETest,CombinedWithLoop)1019 TEST_F(LSETest, CombinedWithLoop)
1020 {
1021 src_graph::CombinedWithLoop::CREATE(GetGraph());
1022 Graph *graphLsed = CreateEmptyGraph();
1023 out_graph::CombinedWithLoop::CREATE(graphLsed);
1024 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1025 GraphChecker(GetGraph()).Check();
1026 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1027 }
1028
1029 /// Phi candidates are the origins of values on the heap
SRC_GRAPH(OverwrittenPhiCandidates,Graph * graph)1030 SRC_GRAPH(OverwrittenPhiCandidates, Graph *graph)
1031 {
1032 GRAPH(graph)
1033 {
1034 PARAMETER(0U, 0U).ref();
1035 PARAMETER(1U, 1U).ref();
1036 CONSTANT(2U, 0x0U).s64();
1037 CONSTANT(50U, 0x1U).s64();
1038 BASIC_BLOCK(2U, 3U, 4U)
1039 {
1040 INST(7U, Opcode::LoadArray).ref().Inputs(0U, 2U);
1041 INST(12U, Opcode::StoreArray).ref().Inputs(0U, 2U, 1U);
1042 INST(15U, Opcode::LenArray).s32().Inputs(7U);
1043 INST(52U, Opcode::Compare).b().CC(CC_GE).Inputs(2U, 15U);
1044 INST(53U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(52U);
1045 }
1046 BASIC_BLOCK(4U, 3U, 4U)
1047 {
1048 INST(18U, Opcode::Phi).s32().Inputs({{2U, 2U}, {4U, 49U}});
1049 INST(19U, Opcode::Phi).s32().Inputs({{2U, 2U}, {4U, 48U}});
1050 // Must be replaced with a1 not v7
1051 INST(31U, Opcode::LoadArray).ref().Inputs(0U, 2U);
1052 INST(36U, Opcode::LoadArray).s32().Inputs(31U, 2U);
1053 // Must be replaced with a1 not v7
1054 INST(41U, Opcode::LoadArray).ref().Inputs(0U, 2U);
1055 INST(46U, Opcode::LoadArray).s32().Inputs(41U, 2U);
1056 INST(47U, Opcode::Add).s32().Inputs(46U, 36U);
1057 INST(48U, Opcode::Add).s32().Inputs(47U, 19U);
1058 INST(49U, Opcode::Add).s32().Inputs(18U, 50U);
1059 INST(25U, Opcode::Compare).b().CC(CC_GE).Inputs(49U, 15U);
1060 INST(26U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(25U);
1061 }
1062 BASIC_BLOCK(3U, -1L)
1063 {
1064 INST(55U, Opcode::Phi).s32().Inputs({{4U, 48U}, {2U, 2U}});
1065 INST(51U, Opcode::Return).s32().Inputs(55U);
1066 }
1067 }
1068 }
1069
OUT_GRAPH(OverwrittenPhiCandidates,Graph * graph)1070 OUT_GRAPH(OverwrittenPhiCandidates, Graph *graph)
1071 {
1072 GRAPH(graph)
1073 {
1074 PARAMETER(0U, 0U).ref();
1075 PARAMETER(1U, 1U).ref();
1076 CONSTANT(2U, 0x0U).s64();
1077 CONSTANT(50U, 0x1U).s64();
1078 BASIC_BLOCK(2U, 3U, 4U)
1079 {
1080 INST(7U, Opcode::LoadArray).ref().Inputs(0U, 2U);
1081 INST(12U, Opcode::StoreArray).ref().Inputs(0U, 2U, 1U);
1082 INST(15U, Opcode::LenArray).s32().Inputs(7U);
1083 INST(52U, Opcode::Compare).b().CC(CC_GE).Inputs(2U, 15U);
1084 INST(53U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(52U);
1085 }
1086 BASIC_BLOCK(4U, 3U, 4U)
1087 {
1088 INST(18U, Opcode::Phi).s32().Inputs({{2U, 2U}, {4U, 49U}});
1089 INST(19U, Opcode::Phi).s32().Inputs({{2U, 2U}, {4U, 48U}});
1090 INST(36U, Opcode::LoadArray).s32().Inputs(1U, 2U);
1091 INST(46U, Opcode::LoadArray).s32().Inputs(1U, 2U);
1092 INST(47U, Opcode::Add).s32().Inputs(46U, 36U);
1093 INST(48U, Opcode::Add).s32().Inputs(47U, 19U);
1094 INST(49U, Opcode::Add).s32().Inputs(18U, 50U);
1095 INST(25U, Opcode::Compare).b().CC(CC_GE).Inputs(49U, 15U);
1096 INST(26U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(25U);
1097 }
1098 BASIC_BLOCK(3U, -1L)
1099 {
1100 INST(55U, Opcode::Phi).s32().Inputs({{4U, 48U}, {2U, 2U}});
1101 INST(51U, Opcode::Return).s32().Inputs(55U);
1102 }
1103 }
1104 }
1105
TEST_F(LSETest,OverwrittenPhiCandidates)1106 TEST_F(LSETest, OverwrittenPhiCandidates)
1107 {
1108 src_graph::OverwrittenPhiCandidates::CREATE(GetGraph());
1109 Graph *graphLsed = CreateEmptyGraph();
1110 out_graph::OverwrittenPhiCandidates::CREATE(graphLsed);
1111 ASSERT_TRUE(GetGraph()->RunPass<Lse>(false));
1112 GraphChecker(GetGraph()).Check();
1113 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1114 }
1115
1116 /**
1117 * Do not use a deleted instruction as a valid phi candidate
1118 * [entry]
1119 * |
1120 * [2]
1121 * |
1122 * [3]--\
1123 * | [7]<--\
1124 * [6]<-/ \---/
1125 * |
1126 * [exit]
1127 */
SRC_GRAPH(DeletedPhiCandidate,Graph * graph)1128 SRC_GRAPH(DeletedPhiCandidate, Graph *graph)
1129 {
1130 GRAPH(graph)
1131 {
1132 CONSTANT(9U, 0x0U).s64();
1133 CONSTANT(47U, 0x1U).s64();
1134 BASIC_BLOCK(2U, 6U, 7U)
1135 {
1136 INST(10U, Opcode::SaveState).Inputs(9U).SrcVregs({0U});
1137 INST(3U, Opcode::LoadAndInitClass).ref().Inputs(10U).TypeId(0U);
1138 INST(1U, Opcode::LoadStatic).s32().Inputs(3U).TypeId(3059U); // A valid phi candidate for 3059
1139 INST(97U, Opcode::SaveState);
1140 INST(4U, Opcode::NewArray).ref().Inputs(3U, 1U, 97U).TypeId(273U);
1141 INST(5U, Opcode::StoreStatic).ref().Inputs(3U, 4U).TypeId(3105U);
1142 INST(65U, Opcode::LoadStatic).s32().Inputs(3U).TypeId(3059U); // Would be a deleted phi candidate
1143 INST(94U, Opcode::SaveState);
1144 INST(68U, Opcode::NewArray).ref().Inputs(3U, 65U, 94U).TypeId(273U);
1145 INST(69U, Opcode::StoreStatic).ref().Inputs(3U, 68U).TypeId(3105U);
1146 INST(89U, Opcode::LoadStatic).s32().Inputs(3U).TypeId(3059U); // Would be a deleted phi candidate
1147 INST(90U, Opcode::Compare).b().CC(CC_GE).Inputs(9U, 89U);
1148 INST(91U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(90U);
1149 }
1150 BASIC_BLOCK(7U, 6U, 7U)
1151 {
1152 INST(72U, Opcode::Phi).s32().Inputs({{2U, 9U}, {7U, 87U}});
1153 INST(79U, Opcode::LoadStatic).ref().Inputs(3U).TypeId(3105U);
1154 INST(87U, Opcode::Add).s32().Inputs(72U, 47U);
1155 INST(76U, Opcode::LoadStatic).s32().Inputs(3U).TypeId(3059U);
1156 INST(77U, Opcode::Compare).b().CC(CC_GE).Inputs(87U, 76U);
1157 INST(78U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(77U);
1158 }
1159 BASIC_BLOCK(6U, -1L)
1160 {
1161 INST(88U, Opcode::ReturnVoid).v0id();
1162 }
1163 }
1164 }
1165
OUT_GRAPH(DeletedPhiCandidate,Graph * graph)1166 OUT_GRAPH(DeletedPhiCandidate, Graph *graph)
1167 {
1168 GRAPH(graph)
1169 {
1170 CONSTANT(9U, 0x0U).s64();
1171 CONSTANT(47U, 0x1U).s64();
1172 BASIC_BLOCK(2U, 6U, 7U)
1173 {
1174 INST(10U, Opcode::SaveState).Inputs(9U).SrcVregs({0U});
1175 INST(3U, Opcode::LoadAndInitClass).ref().Inputs(10U).TypeId(0U);
1176 INST(1U, Opcode::LoadStatic).s32().Inputs(3U).TypeId(3059U);
1177 INST(97U, Opcode::SaveState);
1178 INST(4U, Opcode::NewArray).ref().Inputs(3U, 1U, 97U).TypeId(273U);
1179 INST(5U, Opcode::StoreStatic).ref().Inputs(3U, 4U).TypeId(3105U);
1180 INST(94U, Opcode::SaveState);
1181 INST(68U, Opcode::NewArray).ref().Inputs(3U, 1U, 94U).TypeId(273U);
1182 INST(69U, Opcode::StoreStatic).ref().Inputs(3U, 68U).TypeId(3105U);
1183 INST(90U, Opcode::Compare).b().CC(CC_GE).Inputs(9U, 1U);
1184 INST(91U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(90U);
1185 }
1186 BASIC_BLOCK(7U, 6U, 7U)
1187 {
1188 INST(72U, Opcode::Phi).s32().Inputs({{2U, 9U}, {7U, 87U}});
1189 INST(87U, Opcode::Add).s32().Inputs(72U, 47U);
1190 INST(77U, Opcode::Compare).b().CC(CC_GE).Inputs(87U, 1U);
1191 INST(78U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(77U);
1192 }
1193 BASIC_BLOCK(6U, -1L)
1194 {
1195 INST(88U, Opcode::ReturnVoid).v0id();
1196 }
1197 }
1198 }
1199
TEST_F(LSETest,DeletedPhiCandidate)1200 TEST_F(LSETest, DeletedPhiCandidate)
1201 {
1202 src_graph::DeletedPhiCandidate::CREATE(GetGraph());
1203 Graph *graphLsed = CreateEmptyGraph();
1204 out_graph::DeletedPhiCandidate::CREATE(graphLsed);
1205 ASSERT_TRUE(GetGraph()->RunPass<Lse>(false));
1206 GraphChecker(GetGraph()).Check();
1207 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1208 }
1209
1210 /// Stored value might be casted therefore we should cast if types are different
TEST_F(LSETest,PrimitiveTypeCasting)1211 TEST_F(LSETest, PrimitiveTypeCasting)
1212 {
1213 GRAPH(GetGraph())
1214 {
1215 PARAMETER(0U, 0U).ref();
1216 PARAMETER(1U, 1U).s64();
1217 PARAMETER(2U, 2U).s64();
1218 BASIC_BLOCK(2U, -1L)
1219 {
1220 INST(3U, Opcode::Add).s64().Inputs(1U, 2U);
1221 INST(6U, Opcode::StoreObject).s32().Inputs(0U, 3U).TypeId(157U);
1222 INST(9U, Opcode::LoadObject).s32().Inputs(0U).TypeId(157U);
1223 INST(10U, Opcode::Return).s32().Inputs(9U);
1224 }
1225 }
1226 Graph *graphLsed = CreateEmptyGraph();
1227 GRAPH(graphLsed)
1228 {
1229 PARAMETER(0U, 0U).ref();
1230 PARAMETER(1U, 1U).s64();
1231 PARAMETER(2U, 2U).s64();
1232 BASIC_BLOCK(2U, -1L)
1233 {
1234 INST(3U, Opcode::Add).s64().Inputs(1U, 2U);
1235 INST(6U, Opcode::StoreObject).s32().Inputs(0U, 3U).TypeId(157U);
1236 // Types of a stored value (v3) and loaded (v9) are different. Cast is needed.
1237 INST(11U, Opcode::Cast).s32().SrcType(DataType::INT64).Inputs(3U);
1238 INST(10U, Opcode::Return).s32().Inputs(11U);
1239 }
1240 }
1241 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1242 GraphChecker(GetGraph()).Check();
1243 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1244 }
1245
1246 /**
1247 * Stored value might be casted therefore we should cast if types are different
1248 * To avoid inappropriate Cast, skip the elimination of some loadobj inst
1249 */
SRC_GRAPH(PrimitiveInt8TypeCasting,Graph * graph)1250 SRC_GRAPH(PrimitiveInt8TypeCasting, Graph *graph)
1251 {
1252 GRAPH(graph)
1253 {
1254 PARAMETER(0U, 0U).ref();
1255 PARAMETER(1U, 1U).s64();
1256 PARAMETER(2U, 2U).s64();
1257
1258 PARAMETER(3U, 3U).ref();
1259 PARAMETER(4U, 4U).s8();
1260 PARAMETER(5U, 5U).s8();
1261
1262 BASIC_BLOCK(2U, -1L)
1263 {
1264 INST(7U, Opcode::Add).s64().Inputs(1U, 2U);
1265 INST(9U, Opcode::StoreObject).s32().Inputs(0U, 7U).TypeId(159U);
1266 INST(11U, Opcode::LoadObject).s32().Inputs(0U).TypeId(159U);
1267
1268 INST(16U, Opcode::Add).s8().Inputs(4U, 5U);
1269 INST(17U, Opcode::StoreObject).s32().Inputs(3U, 16U).TypeId(163U);
1270 INST(18U, Opcode::LoadObject).s32().Inputs(3U).TypeId(163U);
1271 INST(23U, Opcode::Add).s32().Inputs(11U, 18U);
1272 INST(19U, Opcode::Return).s32().Inputs(23U);
1273 }
1274 }
1275 }
1276
OUT_GRAPH(PrimitiveInt8TypeCasting,Graph * graph)1277 OUT_GRAPH(PrimitiveInt8TypeCasting, Graph *graph)
1278 {
1279 GRAPH(graph)
1280 {
1281 PARAMETER(0U, 0U).ref();
1282 PARAMETER(1U, 1U).s64();
1283 PARAMETER(2U, 2U).s64();
1284
1285 PARAMETER(3U, 3U).ref();
1286 PARAMETER(4U, 4U).s8();
1287 PARAMETER(5U, 5U).s8();
1288
1289 BASIC_BLOCK(2U, -1L)
1290 {
1291 INST(7U, Opcode::Add).s64().Inputs(1U, 2U);
1292 INST(9U, Opcode::StoreObject).s32().Inputs(0U, 7U).TypeId(159U);
1293 // Types of stored value (v4, INT8) and loaded (v9, INT32) are different and
1294 // legal for cast. We can use Cast to take place of LoadObject.
1295 INST(11U, Opcode::Cast).s32().SrcType(DataType::INT64).Inputs(7U);
1296
1297 INST(16U, Opcode::Add).s8().Inputs(4U, 5U);
1298 INST(17U, Opcode::StoreObject).s32().Inputs(3U, 16U).TypeId(163U);
1299 // if eliminate the loadobj inst, inappropriate inst 'i32 Cast i8' will be created.
1300 INST(18U, Opcode::LoadObject).s32().Inputs(3U).TypeId(163U);
1301 INST(23U, Opcode::Add).s32().Inputs(11U, 18U);
1302 INST(19U, Opcode::Return).s32().Inputs(23U);
1303 }
1304 }
1305 }
1306
TEST_F(LSETest,PrimitiveInt8TypeCasting)1307 TEST_F(LSETest, PrimitiveInt8TypeCasting)
1308 {
1309 auto graph = CreateEmptyBytecodeGraph();
1310 src_graph::PrimitiveInt8TypeCasting::CREATE(graph);
1311 auto graphLsed = CreateEmptyBytecodeGraph();
1312 out_graph::PrimitiveInt8TypeCasting::CREATE(graphLsed);
1313 ASSERT_TRUE(graph->RunPass<Lse>());
1314 GraphChecker(graph).Check();
1315 ASSERT_TRUE(GraphComparator().Compare(graph, graphLsed));
1316 }
1317
1318 /// Overwritten load in loop
SRC_GRAPH(LoopWithOverwrite,Graph * graph)1319 SRC_GRAPH(LoopWithOverwrite, Graph *graph)
1320 {
1321 GRAPH(graph)
1322 {
1323 PARAMETER(0U, 0U).ref();
1324 CONSTANT(7U, 0x0U).s64();
1325 CONSTANT(28U, 0x1U).s64();
1326 BASIC_BLOCK(2U, 3U, 4U)
1327 {
1328 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U);
1329 INST(6U, Opcode::LenArray).s32().Inputs(3U);
1330 INST(30U, Opcode::Cmp).s32().Inputs(7U, 6U);
1331 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(30U, 7U);
1332 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
1333 }
1334 // For (v10 = 0, v10 < lenarr(v3), v10++)
1335 // v3 = v3[v10]
1336 BASIC_BLOCK(4U, 3U, 4U)
1337 {
1338 INST(10U, Opcode::Phi).s32().Inputs({{2U, 7U}, {4U, 27U}});
1339
1340 INST(20U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U);
1341 INST(25U, Opcode::LoadArray).ref().Inputs(20U, 10U);
1342
1343 INST(27U, Opcode::Add).s32().Inputs(10U, 28U);
1344
1345 INST(33U, Opcode::StoreObject).ref().Inputs(0U, 25U).TypeId(242U);
1346
1347 INST(15U, Opcode::Cmp).s32().Inputs(27U, 6U);
1348 INST(16U, Opcode::Compare).b().CC(CC_GE).Inputs(15U, 7U);
1349 INST(17U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(16U);
1350 }
1351 BASIC_BLOCK(3U, -1L)
1352 {
1353 INST(29U, Opcode::ReturnVoid).v0id();
1354 }
1355 }
1356 }
1357
OUT_GRAPH(LoopWithOverwrite,Graph * graph)1358 OUT_GRAPH(LoopWithOverwrite, Graph *graph)
1359 {
1360 GRAPH(graph)
1361 {
1362 PARAMETER(0U, 0U).ref();
1363 CONSTANT(7U, 0x0U).s64();
1364 CONSTANT(28U, 0x1U).s64();
1365 BASIC_BLOCK(2U, 3U, 4U)
1366 {
1367 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(242U);
1368 INST(6U, Opcode::LenArray).s32().Inputs(3U);
1369 INST(30U, Opcode::Cmp).s32().Inputs(7U, 6U);
1370 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(30U, 7U);
1371 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
1372 }
1373 // For (v10 = 0, v10 < lenarr(v3), v10++)
1374 // v3 = v3[v10]
1375 BASIC_BLOCK(4U, 3U, 4U)
1376 {
1377 INST(10U, Opcode::Phi).s32().Inputs({{2U, 7U}, {4U, 27U}});
1378 INST(11U, Opcode::Phi).ref().Inputs({{2U, 3U}, {4U, 25U}});
1379
1380 INST(25U, Opcode::LoadArray).ref().Inputs(11U, 10U);
1381
1382 INST(27U, Opcode::Add).s32().Inputs(10U, 28U);
1383
1384 INST(33U, Opcode::StoreObject).ref().Inputs(0U, 25U).TypeId(242U);
1385
1386 INST(15U, Opcode::Cmp).s32().Inputs(27U, 6U);
1387 INST(16U, Opcode::Compare).b().CC(CC_GE).Inputs(15U, 7U);
1388 INST(17U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(16U);
1389 }
1390 BASIC_BLOCK(3U, -1L)
1391 {
1392 INST(29U, Opcode::ReturnVoid).v0id();
1393 }
1394 }
1395 }
1396
TEST_F(LSETest,LoopWithOverwrite)1397 TEST_F(LSETest, LoopWithOverwrite)
1398 {
1399 src_graph::LoopWithOverwrite::CREATE(GetGraph());
1400 Graph *graphLsed = CreateEmptyGraph();
1401 out_graph::LoopWithOverwrite::CREATE(graphLsed);
1402 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1403 GraphChecker(GetGraph()).Check();
1404 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1405 }
1406
1407 /// Eliminate loads saved in SaveState and SafePoint.
TEST_F(LSETest,SavedLoadInSafePoint)1408 TEST_F(LSETest, SavedLoadInSafePoint)
1409 {
1410 GRAPH(GetGraph())
1411 {
1412 PARAMETER(0U, 0U).ref();
1413 BASIC_BLOCK(2U, -1L)
1414 {
1415 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
1416 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 3U).TypeId(122U);
1417
1418 INST(7U, Opcode::SafePoint).Inputs(0U, 3U).SrcVregs({0U, 2U});
1419
1420 // Eliminable because of v3 saved in SafePoint
1421 INST(8U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
1422
1423 INST(12U, Opcode::Return).ref().Inputs(8U);
1424 }
1425 }
1426 Graph *graphLsed = CreateEmptyGraph();
1427 GRAPH(graphLsed)
1428 {
1429 PARAMETER(0U, 0U).ref();
1430 BASIC_BLOCK(2U, -1L)
1431 {
1432 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
1433 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 3U).TypeId(122U);
1434
1435 INST(7U, Opcode::SafePoint).Inputs(0U, 3U).SrcVregs({0U, 2U});
1436
1437 INST(12U, Opcode::Return).ref().Inputs(3U);
1438 }
1439 }
1440 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1441 GraphChecker(GetGraph()).Check();
1442 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1443 }
1444
1445 /// SafePoint may relocate collected references making them invalid
TEST_F(LSETest,LoopWithSafePoint)1446 TEST_F(LSETest, LoopWithSafePoint)
1447 {
1448 GRAPH(GetGraph())
1449 {
1450 PARAMETER(0U, 0U).ref();
1451 BASIC_BLOCK(2U, 8U)
1452 {
1453 INST(5U, Opcode::LoadObject).ref().Inputs(0U).TypeId(657U);
1454 INST(8U, Opcode::LenArray).s32().Inputs(5U);
1455 }
1456 BASIC_BLOCK(8U, 8U, 4U)
1457 {
1458 INST(16U, Opcode::SafePoint).Inputs(0U).SrcVregs({0U});
1459 INST(22U, Opcode::LoadObject).ref().Inputs(0U).TypeId(657U);
1460 INST(23U, Opcode::LenArray).s32().Inputs(22U);
1461 INST(17U, Opcode::Compare).b().CC(CC_GE).Inputs(23U, 8U);
1462 INST(18U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(17U);
1463 }
1464 BASIC_BLOCK(4U, -1L)
1465 {
1466 INST(19U, Opcode::ReturnVoid);
1467 }
1468 }
1469
1470 Graph *graphLsed = CreateEmptyGraph();
1471 GRAPH(graphLsed)
1472 {
1473 PARAMETER(0U, 0U).ref();
1474 BASIC_BLOCK(2U, 8U)
1475 {
1476 INST(5U, Opcode::LoadObject).ref().Inputs(0U).TypeId(657U);
1477 INST(8U, Opcode::LenArray).s32().Inputs(5U);
1478 }
1479 BASIC_BLOCK(8U, 8U, 4U)
1480 {
1481 INST(16U, Opcode::SafePoint).Inputs(0U, 5U).SrcVregs({0U, VirtualRegister::BRIDGE});
1482 INST(23U, Opcode::LenArray).s32().Inputs(5U);
1483 INST(17U, Opcode::Compare).b().CC(CC_GE).Inputs(23U, 8U);
1484 INST(18U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(17U);
1485 }
1486 BASIC_BLOCK(4U, -1L)
1487 {
1488 INST(19U, Opcode::ReturnVoid);
1489 }
1490 }
1491 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1492 GraphChecker(GetGraph()).Check();
1493 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1494 }
1495
1496 /// Call generally invalidates all heap.
TEST_F(LSETest,MemEscaping)1497 TEST_F(LSETest, MemEscaping)
1498 {
1499 std::vector<Graph *> equalGraphs = {GetGraph(), CreateEmptyGraph()};
1500 for (auto graph : equalGraphs) {
1501 GRAPH(graph)
1502 {
1503 PARAMETER(0U, 0U).ref();
1504 PARAMETER(1U, 1U).s64();
1505 BASIC_BLOCK(2U, -1L)
1506 {
1507 INST(4U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(122U);
1508 INST(5U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 2U});
1509 INST(6U, Opcode::CallStatic).s64().Inputs({{DataType::REFERENCE, 0U}, {DataType::NO_TYPE, 5U}});
1510 INST(9U, Opcode::LoadObject).s64().Inputs(0U).TypeId(122U);
1511 INST(10U, Opcode::Return).s64().Inputs(9U);
1512 }
1513 }
1514 }
1515 ASSERT_FALSE(equalGraphs[0U]->RunPass<Lse>());
1516 GraphChecker(equalGraphs[0U]).Check();
1517 ASSERT_TRUE(GraphComparator().Compare(equalGraphs[0U], equalGraphs[1U]));
1518 }
1519
1520 /**
1521 * Use a dominated access after elimination
1522 * [entry]
1523 * |
1524 * /--[2]--\
1525 * [4] |
1526 * \----->[3]------\
1527 * | |
1528 * /->[7]--\ |
1529 * \---| | |
1530 * [5]<-----/
1531 * |
1532 * [exit]
1533 */
SRC_GRAPH(ReplaceByDominated,Graph * graph)1534 SRC_GRAPH(ReplaceByDominated, Graph *graph)
1535 {
1536 GRAPH(graph)
1537 {
1538 PARAMETER(0U, 0U).s32();
1539 CONSTANT(1U, 0x2U).s64();
1540 CONSTANT(2U, 0x0U).s64();
1541 CONSTANT(6U, 0x1U).s64();
1542 BASIC_BLOCK(2U, 3U, 4U)
1543 {
1544 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1545 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
1546 INST(3U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 0U);
1547 INST(4U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(3U);
1548 }
1549 BASIC_BLOCK(4U, 3U)
1550 {
1551 INST(5U, Opcode::LoadStatic).ref().Inputs(30U).TypeId(83U);
1552 INST(7U, Opcode::SaveState).Inputs(0U, 1U, 2U, 6U, 1U, 5U).SrcVregs({5U, 4U, 3U, 2U, 1U, 0U});
1553 INST(8U, Opcode::NullCheck).ref().Inputs(5U, 7U);
1554 INST(11U, Opcode::StoreArray).s8().Inputs(5U, 1U, 6U);
1555 }
1556 BASIC_BLOCK(3U, 5U, 7U)
1557 {
1558 INST(13U, Opcode::Phi).s32().Inputs({{2U, 0U}, {4U, 1U}});
1559 INST(15U, Opcode::LoadStatic).ref().Inputs(30U).TypeId(83U);
1560 INST(20U, Opcode::LoadArray).s32().Inputs(15U, 13U);
1561 INST(21U, Opcode::Compare).b().CC(CC_EQ).Inputs(20U, 2U);
1562 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
1563 }
1564 BASIC_BLOCK(7U, 5U, 7U)
1565 {
1566 // Replace by dominated v15 not v5
1567 INST(33U, Opcode::LoadStatic).ref().Inputs(30U).TypeId(83U);
1568 INST(38U, Opcode::StoreArray).s32().Inputs(33U, 13U, 6U);
1569 INST(31U, Opcode::Compare).b().CC(CC_GT).Inputs(6U, 13U);
1570 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
1571 }
1572 BASIC_BLOCK(5U, -1L)
1573 {
1574 INST(45U, Opcode::Phi).s32().Inputs({{3U, 20U}, {7U, 6U}});
1575 INST(46U, Opcode::Return).s32().Inputs(45U);
1576 }
1577 }
1578 }
1579
OUT_GRAPH(ReplaceByDominated,Graph * graph)1580 OUT_GRAPH(ReplaceByDominated, Graph *graph)
1581 {
1582 GRAPH(graph)
1583 {
1584 PARAMETER(0U, 0U).s32();
1585 CONSTANT(1U, 0x2U).s64();
1586 CONSTANT(2U, 0x0U).s64();
1587 CONSTANT(6U, 0x1U).s64();
1588 BASIC_BLOCK(2U, 3U, 4U)
1589 {
1590 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1591 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
1592 INST(3U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 0U);
1593 INST(4U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(3U);
1594 }
1595 BASIC_BLOCK(4U, 3U)
1596 {
1597 INST(5U, Opcode::LoadStatic).ref().Inputs(30U).TypeId(83U);
1598 INST(7U, Opcode::SaveState).Inputs(0U, 1U, 2U, 6U, 1U, 5U).SrcVregs({5U, 4U, 3U, 2U, 1U, 0U});
1599 INST(8U, Opcode::NullCheck).ref().Inputs(5U, 7U);
1600 INST(11U, Opcode::StoreArray).s8().Inputs(5U, 1U, 6U);
1601 }
1602 BASIC_BLOCK(3U, 5U, 7U)
1603 {
1604 INST(13U, Opcode::Phi).s32().Inputs({{2U, 0U}, {4U, 1U}});
1605 INST(15U, Opcode::LoadStatic).ref().Inputs(30U).TypeId(83U);
1606 INST(20U, Opcode::LoadArray).s32().Inputs(15U, 13U);
1607 INST(21U, Opcode::Compare).b().CC(CC_EQ).Inputs(20U, 2U);
1608 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
1609 }
1610 BASIC_BLOCK(7U, 5U, 7U)
1611 {
1612 INST(38U, Opcode::StoreArray).s32().Inputs(15U, 13U, 6U);
1613 INST(31U, Opcode::Compare).b().CC(CC_GT).Inputs(6U, 13U);
1614 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
1615 }
1616 BASIC_BLOCK(5U, -1L)
1617 {
1618 INST(45U, Opcode::Phi).s32().Inputs({{3U, 20U}, {7U, 6U}});
1619 INST(46U, Opcode::Return).s32().Inputs(45U);
1620 }
1621 }
1622 }
1623
TEST_F(LSETest,ReplaceByDominated)1624 TEST_F(LSETest, ReplaceByDominated)
1625 {
1626 src_graph::ReplaceByDominated::CREATE(GetGraph());
1627 Graph *graphLsed = CreateEmptyGraph();
1628 out_graph::ReplaceByDominated::CREATE(graphLsed);
1629 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1630 GraphChecker(GetGraph()).Check();
1631 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1632 }
1633
1634 /// Normal loads and stores can be eliminated after volatile store
TEST_F(LSETest,ReorderableVolatileStore)1635 TEST_F(LSETest, ReorderableVolatileStore)
1636 {
1637 GRAPH(GetGraph())
1638 {
1639 PARAMETER(0U, 0U).ref();
1640 BASIC_BLOCK(2U, -1L)
1641 {
1642 INST(1U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1643 INST(2U, Opcode::NullCheck).ref().Inputs(0U, 1U);
1644 INST(3U, Opcode::LoadObject).ref().Inputs(2U).TypeId(152U);
1645 INST(4U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1646 INST(5U, Opcode::NullCheck).ref().Inputs(0U, 4U);
1647 INST(6U, Opcode::StoreObject).ref().Inputs(5U, 3U).TypeId(138U);
1648 INST(7U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1649 INST(8U, Opcode::NullCheck).ref().Inputs(0U, 7U);
1650 INST(9U, Opcode::LoadObject).ref().Inputs(8U).TypeId(152U);
1651 INST(10U, Opcode::Return).ref().Inputs(9U);
1652 }
1653 }
1654 Graph *graphLsed = CreateEmptyGraph();
1655 GRAPH(graphLsed)
1656 {
1657 PARAMETER(0U, 0U).ref();
1658 BASIC_BLOCK(2U, -1L)
1659 {
1660 INST(1U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1661 INST(2U, Opcode::NullCheck).ref().Inputs(0U, 1U);
1662 INST(3U, Opcode::LoadObject).ref().Inputs(2U).TypeId(152U);
1663 INST(4U, Opcode::SaveState).Inputs(0U, 3U).SrcVregs({0U, VirtualRegister::BRIDGE});
1664 INST(5U, Opcode::NullCheck).ref().Inputs(0U, 4U);
1665 INST(6U, Opcode::StoreObject).ref().Inputs(5U, 3U).TypeId(138U);
1666 INST(10U, Opcode::Return).ref().Inputs(3U);
1667 }
1668 }
1669 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1670 GraphChecker(GetGraph()).Check();
1671 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1672 }
1673
TEST_F(LSETest,ReorderableVolatileStoreWithOutBridge)1674 TEST_F(LSETest, ReorderableVolatileStoreWithOutBridge)
1675 {
1676 GRAPH(GetGraph())
1677 {
1678 PARAMETER(0U, 0U).ref();
1679 BASIC_BLOCK(2U, -1L)
1680 {
1681 INST(1U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1682 INST(2U, Opcode::NullCheck).ref().Inputs(0U, 1U);
1683 INST(3U, Opcode::LoadObject).s32().Inputs(2U).TypeId(152U);
1684 INST(4U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1685 INST(5U, Opcode::NullCheck).ref().Inputs(0U, 4U);
1686 INST(6U, Opcode::StoreObject).s32().Inputs(5U, 3U).TypeId(138U);
1687 INST(7U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1688 INST(8U, Opcode::NullCheck).ref().Inputs(0U, 7U);
1689 INST(9U, Opcode::LoadObject).s32().Inputs(8U).TypeId(152U);
1690 INST(10U, Opcode::Return).s32().Inputs(9U);
1691 }
1692 }
1693 Graph *graphLsed = CreateEmptyGraph();
1694 GRAPH(graphLsed)
1695 {
1696 PARAMETER(0U, 0U).ref();
1697 BASIC_BLOCK(2U, -1L)
1698 {
1699 INST(1U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1700 INST(2U, Opcode::NullCheck).ref().Inputs(0U, 1U);
1701 INST(3U, Opcode::LoadObject).s32().Inputs(2U).TypeId(152U);
1702 INST(4U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
1703 INST(5U, Opcode::NullCheck).ref().Inputs(0U, 4U);
1704 INST(6U, Opcode::StoreObject).s32().Inputs(5U, 3U).TypeId(138U);
1705 INST(10U, Opcode::Return).s32().Inputs(3U);
1706 }
1707 }
1708 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1709 GraphChecker(GetGraph()).Check();
1710 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1711 }
1712
1713 /// v9 and v12 MAY_ALIAS each other. But after elimination of v11 they have NO_ALIAS.
SRC_GRAPH(PhiCandidatesWithUpdatedAA,Graph * graph)1714 SRC_GRAPH(PhiCandidatesWithUpdatedAA, Graph *graph)
1715 {
1716 GRAPH(graph)
1717 {
1718 PARAMETER(0U, 0U).f32();
1719 CONSTANT(1U, 0x2U);
1720 CONSTANT(3U, 0x0U).f32();
1721 BASIC_BLOCK(2U, 3U)
1722 {
1723 INST(5U, Opcode::SaveState).Inputs(3U, 1U).SrcVregs({1U, 5U});
1724 INST(6U, Opcode::LoadAndInitClass).ref().Inputs(5U);
1725 INST(7U, Opcode::NewObject).ref().Inputs(6U, 5U);
1726
1727 INST(23U, Opcode::SaveState).Inputs(7U).SrcVregs({0U});
1728 INST(8U, Opcode::NewArray).ref().Inputs(6U, 1U, 23U).TypeId(20U);
1729 INST(9U, Opcode::StoreArray).ref().Inputs(8U, 1U, 7U);
1730 INST(10U, Opcode::LoadArray).ref().Inputs(8U, 1U);
1731 INST(11U, Opcode::StoreObject).f32().Inputs(10U, 0U).TypeId(2726U);
1732 }
1733 BASIC_BLOCK(3U, 3U, 4U)
1734 {
1735 INST(14U, Opcode::Phi).f32().Inputs({{2U, 3U}, {3U, 15U}});
1736 INST(12U, Opcode::LoadObject).ref().Inputs(10U).TypeId(2740U);
1737 INST(13U, Opcode::LoadArray).f32().Inputs(12U, 1U);
1738 INST(15U, Opcode::Add).f32().Inputs(14U, 13U);
1739 INST(16U, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(true).Inputs(3U, 15U);
1740 INST(19U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_NE).Imm(0x0U).Inputs(16U);
1741 }
1742 BASIC_BLOCK(4U, -1L)
1743 {
1744 INST(20U, Opcode::Return).f32().Inputs(15U);
1745 }
1746 }
1747 }
1748
OUT_GRAPH(PhiCandidatesWithUpdatedAA,Graph * graph)1749 OUT_GRAPH(PhiCandidatesWithUpdatedAA, Graph *graph)
1750 {
1751 GRAPH(graph)
1752 {
1753 PARAMETER(0U, 0U).f32();
1754 CONSTANT(1U, 0x2U);
1755 CONSTANT(3U, 0x0U).f32();
1756 BASIC_BLOCK(2U, 3U)
1757 {
1758 INST(5U, Opcode::SaveState).Inputs(3U, 1U).SrcVregs({1U, 5U});
1759 INST(6U, Opcode::LoadAndInitClass).ref().Inputs(5U);
1760 INST(7U, Opcode::NewObject).ref().Inputs(6U, 5U);
1761
1762 INST(23U, Opcode::SaveState).Inputs(7U).SrcVregs({0U});
1763 INST(8U, Opcode::NewArray).ref().Inputs(6U, 1U, 23U).TypeId(20U);
1764 INST(9U, Opcode::StoreArray).ref().Inputs(8U, 1U, 7U);
1765 INST(11U, Opcode::StoreObject).f32().Inputs(7U, 0U).TypeId(2726U);
1766 }
1767 BASIC_BLOCK(3U, 3U, 4U)
1768 {
1769 INST(14U, Opcode::Phi).f32().Inputs({{2U, 3U}, {3U, 15U}});
1770 INST(12U, Opcode::LoadObject).ref().Inputs(7U).TypeId(2740U);
1771 INST(13U, Opcode::LoadArray).f32().Inputs(12U, 1U);
1772 INST(15U, Opcode::Add).f32().Inputs(14U, 13U);
1773 INST(16U, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(true).Inputs(3U, 15U);
1774 INST(19U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_NE).Imm(0x0U).Inputs(16U);
1775 }
1776 BASIC_BLOCK(4U, -1L)
1777 {
1778 INST(20U, Opcode::Return).f32().Inputs(15U);
1779 }
1780 }
1781 }
1782
TEST_F(LSETest,PhiCandidatesWithUpdatedAA)1783 TEST_F(LSETest, PhiCandidatesWithUpdatedAA)
1784 {
1785 src_graph::PhiCandidatesWithUpdatedAA::CREATE(GetGraph());
1786 Graph *graphLsed = CreateEmptyGraph();
1787 out_graph::PhiCandidatesWithUpdatedAA::CREATE(graphLsed);
1788 ASSERT_TRUE(GetGraph()->RunPass<Lse>(false));
1789 GraphChecker(GetGraph()).Check();
1790 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1791 }
1792
1793 /**
1794 * The test relies on LSE debug internal check. The check aimed to control
1795 * that none of eliminated instructions are replaced by other eliminated
1796 * instructions.
1797 *
1798 * Here v25 may be erroneously replaced by v14.
1799 */
TEST_F(LSETest,EliminationOrderMatters)1800 TEST_F(LSETest, EliminationOrderMatters)
1801 {
1802 GRAPH(GetGraph())
1803 {
1804 PARAMETER(0U, 0U).ref();
1805 PARAMETER(1U, 1U).ref();
1806 PARAMETER(2U, 2U).s64();
1807 PARAMETER(3U, 3U).s64();
1808 CONSTANT(4U, 0x0U).s64();
1809 BASIC_BLOCK(2U, -1L)
1810 {
1811 INST(9U, Opcode::StoreArray).s64().Inputs(1U, 4U, 2U);
1812 // V14 is eliminated due to v9
1813 INST(14U, Opcode::LoadArray).s64().Inputs(1U, 4U);
1814 // v19 MAY_ALIAS v9 and v14 therefore pops them from block_heap
1815 INST(19U, Opcode::StoreArray).s64().Inputs(1U, 3U, 3U);
1816
1817 INST(22U, Opcode::StoreObject).s64().Inputs(0U, 14U).TypeId(382U);
1818 // v25 is eliminated due to v22 and should be replaced with v2 because v14 is eliminated too
1819 INST(25U, Opcode::LoadObject).s64().Inputs(0U).TypeId(382U);
1820 INST(29U, Opcode::Return).s64().Inputs(25U);
1821 }
1822 }
1823 Graph *graphLsed = CreateEmptyGraph();
1824 GRAPH(graphLsed)
1825 {
1826 PARAMETER(0U, 0U).ref();
1827 PARAMETER(1U, 1U).ref();
1828 PARAMETER(2U, 2U).s64();
1829 PARAMETER(3U, 3U).s64();
1830 CONSTANT(4U, 0x0U).s64();
1831 BASIC_BLOCK(2U, -1L)
1832 {
1833 INST(9U, Opcode::StoreArray).s64().Inputs(1U, 4U, 2U);
1834 INST(19U, Opcode::StoreArray).s64().Inputs(1U, 3U, 3U);
1835
1836 INST(22U, Opcode::StoreObject).s64().Inputs(0U, 2U).TypeId(382U);
1837 INST(29U, Opcode::Return).s64().Inputs(2U);
1838 }
1839 }
1840 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1841 GraphChecker(GetGraph()).Check();
1842 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1843 }
1844
1845 /**
1846 * Similar to the test above but chain of elimination is across loops.
1847 *
1848 * Here v19 may be erroneously replaced by v15.
1849 */
SRC_GRAPH(EliminationOrderMattersLoops,Graph * graph)1850 SRC_GRAPH(EliminationOrderMattersLoops, Graph *graph)
1851 {
1852 GRAPH(graph)
1853 {
1854 PARAMETER(0U, 0U).ref();
1855 CONSTANT(10U, 0x0U).s64();
1856 CONSTANT(11U, 0xffffffffffffffffU).s64();
1857 BASIC_BLOCK(5U, 6U)
1858 {
1859 INST(12U, Opcode::Cast).s16().SrcType(DataType::INT64).Inputs(11U);
1860 INST(13U, Opcode::LoadObject).ref().Inputs(0U).TypeId(947545U);
1861 INST(14U, Opcode::LenArray).s32().Inputs(13U);
1862 }
1863 BASIC_BLOCK(6U, 7U, 6U)
1864 {
1865 // v15 is eliminated due to v13
1866 INST(15U, Opcode::LoadObject).ref().Inputs(0U).TypeId(947545U);
1867 INST(16U, Opcode::StoreArray).s16().Inputs(15U, 14U, 12U);
1868 INST(17U, Opcode::Compare).b().CC(CC_EQ).Inputs(14U, 10U);
1869 INST(18U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(17U);
1870 }
1871 BASIC_BLOCK(7U, 8U, 7U)
1872 {
1873 // v19 is eliminated due to v15 (a valid heap value after the last iteration of previous loop)
1874 // and should be replaced with v13 because v15 is eliminated too
1875 INST(19U, Opcode::LoadObject).ref().Inputs(0U).TypeId(947545U);
1876 INST(20U, Opcode::StoreArray).s16().Inputs(19U, 14U, 12U);
1877 INST(21U, Opcode::Compare).b().CC(CC_NE).Inputs(14U, 10U);
1878 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
1879 }
1880 BASIC_BLOCK(8U, -1L)
1881 {
1882 INST(23U, Opcode::ReturnVoid).v0id();
1883 }
1884 }
1885 }
1886
OUT_GRAPH(EliminationOrderMattersLoops,Graph * graph)1887 OUT_GRAPH(EliminationOrderMattersLoops, Graph *graph)
1888 {
1889 GRAPH(graph)
1890 {
1891 PARAMETER(0U, 0U).ref();
1892 CONSTANT(10U, 0x0U).s64();
1893 CONSTANT(11U, 0xffffffffffffffffU).s64();
1894 BASIC_BLOCK(5U, 6U)
1895 {
1896 INST(12U, Opcode::Cast).s16().SrcType(DataType::INT64).Inputs(11U);
1897 INST(13U, Opcode::LoadObject).ref().Inputs(0U).TypeId(947545U);
1898 INST(14U, Opcode::LenArray).s32().Inputs(13U);
1899 }
1900 BASIC_BLOCK(6U, 7U, 6U)
1901 {
1902 INST(16U, Opcode::StoreArray).s16().Inputs(13U, 14U, 12U);
1903 INST(17U, Opcode::Compare).b().CC(CC_EQ).Inputs(14U, 10U);
1904 INST(18U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(17U);
1905 }
1906 BASIC_BLOCK(7U, 8U, 7U)
1907 {
1908 INST(20U, Opcode::StoreArray).s16().Inputs(13U, 14U, 12U);
1909 INST(21U, Opcode::Compare).b().CC(CC_NE).Inputs(14U, 10U);
1910 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
1911 }
1912 BASIC_BLOCK(8U, -1L)
1913 {
1914 INST(23U, Opcode::ReturnVoid).v0id();
1915 }
1916 }
1917 }
1918
TEST_F(LSETest,EliminationOrderMattersLoops)1919 TEST_F(LSETest, EliminationOrderMattersLoops)
1920 {
1921 src_graph::EliminationOrderMattersLoops::CREATE(GetGraph());
1922 Graph *graphLsed = CreateEmptyGraph();
1923 out_graph::EliminationOrderMattersLoops::CREATE(graphLsed);
1924 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1925 GraphChecker(GetGraph()).Check();
1926 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1927 }
1928
1929 /*
1930 * We can eliminate over SafePoints if the reference is listed in arguments
1931 */
TEST_F(LSETest,EliminationWithSafePoint)1932 TEST_F(LSETest, EliminationWithSafePoint)
1933 {
1934 GRAPH(GetGraph())
1935 {
1936 PARAMETER(0U, 0U).ref();
1937 BASIC_BLOCK(2U, -1L)
1938 {
1939 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
1940 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 3U).TypeId(122U);
1941
1942 INST(7U, Opcode::SafePoint).Inputs(3U, 0U).SrcVregs({0U, 1U});
1943 INST(8U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
1944 INST(9U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
1945 INST(10U, Opcode::SaveState).Inputs(8U, 9U).SrcVregs({0U, 1U});
1946 INST(11U, Opcode::NullCheck).ref().Inputs(9U, 10U);
1947 INST(12U, Opcode::Return).ref().Inputs(8U);
1948 }
1949 }
1950 Graph *graphLsed = CreateEmptyGraph();
1951 GRAPH(graphLsed)
1952 {
1953 PARAMETER(0U, 0U).ref();
1954 BASIC_BLOCK(2U, -1L)
1955 {
1956 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
1957 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 3U).TypeId(122U);
1958
1959 INST(7U, Opcode::SafePoint).Inputs(3U, 0U).SrcVregs({0U, 1U});
1960 INST(10U, Opcode::SaveState).Inputs(3U, 3U).SrcVregs({0U, 1U});
1961 INST(11U, Opcode::NullCheck).ref().Inputs(3U, 10U);
1962 INST(12U, Opcode::Return).ref().Inputs(3U);
1963 }
1964 }
1965 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
1966 GraphChecker(GetGraph()).Check();
1967 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
1968 }
1969
1970 /*
1971 * We should be able to eliminate over SafePoints if the reference listed in
1972 * arguments was eliminated
1973 */
TEST_F(LSETest,EliminatedWithSafePoint)1974 TEST_F(LSETest, EliminatedWithSafePoint)
1975 {
1976 GRAPH(GetGraph())
1977 {
1978 PARAMETER(0U, 0U).ref();
1979 PARAMETER(1U, 1U).ref();
1980 BASIC_BLOCK(2U, -1L)
1981 {
1982 INST(3U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
1983 // v4 would be replaced with v1
1984 INST(4U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
1985 // v1 should be alive after replacements
1986 INST(5U, Opcode::SafePoint).Inputs(0U, 4U).SrcVregs({0U, 1U});
1987 // v6 would be replaced with v1
1988 INST(6U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
1989 INST(7U, Opcode::Return).ref().Inputs(6U);
1990 }
1991 }
1992 Graph *graphLsed = CreateEmptyGraph();
1993 GRAPH(graphLsed)
1994 {
1995 PARAMETER(0U, 0U).ref();
1996 PARAMETER(1U, 1U).ref();
1997 BASIC_BLOCK(2U, -1L)
1998 {
1999 INST(3U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
2000 INST(5U, Opcode::SafePoint).Inputs(0U, 1U).SrcVregs({0U, 1U});
2001 INST(7U, Opcode::Return).ref().Inputs(1U);
2002 }
2003 }
2004 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2005 GraphChecker(GetGraph()).Check();
2006 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2007 }
2008
TEST_F(LSETest,EliminatedWithSafePointNeedBridge)2009 TEST_F(LSETest, EliminatedWithSafePointNeedBridge)
2010 {
2011 GRAPH(GetGraph())
2012 {
2013 PARAMETER(0U, 0U).ref();
2014 BASIC_BLOCK(2U, -1L)
2015 {
2016 INST(4U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
2017 INST(5U, Opcode::SafePoint).Inputs(0U).SrcVregs({0U});
2018 INST(6U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
2019 INST(7U, Opcode::Return).ref().Inputs(6U);
2020 }
2021 }
2022 Graph *graphLsed = CreateEmptyGraph();
2023 GRAPH(graphLsed)
2024 {
2025 PARAMETER(0U, 0U).ref();
2026 BASIC_BLOCK(2U, -1L)
2027 {
2028 INST(4U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
2029 INST(5U, Opcode::SafePoint).Inputs(0U, 4U).SrcVregs({0U, VirtualRegister::BRIDGE});
2030 INST(7U, Opcode::Return).ref().Inputs(4U);
2031 }
2032 }
2033 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2034 GraphChecker(GetGraph()).Check();
2035 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2036 }
2037
2038 /// Not aliased array acceses, since array cannot overlap each other
SRC_GRAPH(SameArrayAccesses,Graph * graph)2039 SRC_GRAPH(SameArrayAccesses, Graph *graph)
2040 {
2041 GRAPH(graph)
2042 {
2043 PARAMETER(0U, 0U).ref();
2044 CONSTANT(5U, 0x1U).s64();
2045 CONSTANT(9U, 0x0U).s64();
2046 CONSTANT(32U, 0x2U).s64();
2047 CONSTANT(58U, 0x3U).s64();
2048 BASIC_BLOCK(2U, 1U)
2049 {
2050 INST(4U, Opcode::LoadObject).ref().TypeId(302U).Inputs(0U);
2051 INST(8U, Opcode::LoadObject).ref().TypeId(312U).Inputs(0U);
2052
2053 INST(14U, Opcode::LoadArray).s64().Inputs(8U, 9U);
2054 INST(22U, Opcode::LoadArray).s64().Inputs(8U, 5U);
2055 INST(23U, Opcode::Or).s64().Inputs(14U, 22U);
2056 INST(28U, Opcode::StoreArray).s64().Inputs(4U, 5U, 23U);
2057
2058 // Same to 14, in spite of possible aliasing of i4 and i8, they
2059 // have been accessed at different indices
2060 INST(40U, Opcode::LoadArray).s64().Inputs(8U, 9U);
2061 INST(48U, Opcode::LoadArray).s64().Inputs(8U, 32U);
2062 INST(49U, Opcode::Or).s64().Inputs(40U, 48U);
2063 INST(54U, Opcode::StoreArray).s64().Inputs(4U, 32U, 49U);
2064
2065 // Same to 14 and 40, in spite of possible aliasing of i4 and i8,
2066 // they have been accessed at different indices
2067 INST(66U, Opcode::LoadArray).s64().Inputs(8U, 9U);
2068 INST(74U, Opcode::LoadArray).s64().Inputs(8U, 58U);
2069 INST(75U, Opcode::Or).s64().Inputs(66U, 74U);
2070 INST(80U, Opcode::StoreArray).s64().Inputs(4U, 58U, 75U);
2071
2072 INST(81U, Opcode::ReturnVoid).v0id();
2073 }
2074 }
2075 }
2076
OUT_GRAPH(SameArrayAccesses,Graph * graph)2077 OUT_GRAPH(SameArrayAccesses, Graph *graph)
2078 {
2079 GRAPH(graph)
2080 {
2081 PARAMETER(0U, 0U).ref();
2082 CONSTANT(5U, 0x1U).s64();
2083 CONSTANT(9U, 0x0U).s64();
2084 CONSTANT(32U, 0x2U).s64();
2085 CONSTANT(58U, 0x3U).s64();
2086 BASIC_BLOCK(2U, 1U)
2087 {
2088 INST(4U, Opcode::LoadObject).ref().TypeId(302U).Inputs(0U);
2089 INST(8U, Opcode::LoadObject).ref().TypeId(312U).Inputs(0U);
2090
2091 INST(14U, Opcode::LoadArray).s64().Inputs(8U, 9U);
2092 INST(22U, Opcode::LoadArray).s64().Inputs(8U, 5U);
2093 INST(23U, Opcode::Or).s64().Inputs(14U, 22U);
2094 INST(28U, Opcode::StoreArray).s64().Inputs(4U, 5U, 23U);
2095
2096 INST(48U, Opcode::LoadArray).s64().Inputs(8U, 32U);
2097 INST(49U, Opcode::Or).s64().Inputs(14U, 48U);
2098 INST(54U, Opcode::StoreArray).s64().Inputs(4U, 32U, 49U);
2099
2100 INST(74U, Opcode::LoadArray).s64().Inputs(8U, 58U);
2101 INST(75U, Opcode::Or).s64().Inputs(14U, 74U);
2102 INST(80U, Opcode::StoreArray).s64().Inputs(4U, 58U, 75U);
2103
2104 INST(81U, Opcode::ReturnVoid).v0id();
2105 }
2106 }
2107 }
2108
TEST_F(LSETest,SameArrayAccesses)2109 TEST_F(LSETest, SameArrayAccesses)
2110 {
2111 src_graph::SameArrayAccesses::CREATE(GetGraph());
2112 Graph *graphLsed = CreateEmptyGraph();
2113 out_graph::SameArrayAccesses::CREATE(graphLsed);
2114 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2115 GraphChecker(GetGraph()).Check();
2116 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2117 }
2118
2119 /// Eliminate in case of inlined virtual calls
SRC_GRAPH(OverInlinedVirtualCall,Graph * graph)2120 SRC_GRAPH(OverInlinedVirtualCall, Graph *graph)
2121 {
2122 GRAPH(graph)
2123 {
2124 PARAMETER(0U, 0U).b();
2125 PARAMETER(1U, 1U).ref();
2126 PARAMETER(2U, 2U).i32();
2127 BASIC_BLOCK(2U, 3U, 4U)
2128 {
2129 INST(3U, Opcode::StoreObject).i32().Inputs(1U, 2U).TypeId(122U);
2130 INST(4U, Opcode::SaveState).Inputs(1U).SrcVregs({0U});
2131 INST(5U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(0U);
2132 }
2133 BASIC_BLOCK(3U, 5U)
2134 {
2135 INST(6U, Opcode::CallVirtual).v0id().InputsAutoType(1U, 2U, 4U).Inlined();
2136 INST(7U, Opcode::LoadObject).i32().Inputs(1U).TypeId(122U);
2137 INST(8U, Opcode::ReturnInlined).v0id().Inputs(4U);
2138 }
2139 BASIC_BLOCK(4U, 5U)
2140 {
2141 INST(9U, Opcode::CallVirtual).v0id().InputsAutoType(1U, 2U, 4U).Inlined();
2142 INST(10U, Opcode::LoadObject).i32().Inputs(1U).TypeId(122U);
2143 INST(11U, Opcode::ReturnInlined).v0id().Inputs(4U);
2144 }
2145 BASIC_BLOCK(5U, -1L)
2146 {
2147 INST(12U, Opcode::LoadObject).i32().Inputs(1U).TypeId(122U);
2148 INST(13U, Opcode::Return).i32().Inputs(12U);
2149 }
2150 }
2151 }
2152
OUT_GRAPH(OverInlinedVirtualCall,Graph * graph)2153 OUT_GRAPH(OverInlinedVirtualCall, Graph *graph)
2154 {
2155 GRAPH(graph)
2156 {
2157 PARAMETER(0U, 0U).b();
2158 PARAMETER(1U, 1U).ref();
2159 PARAMETER(2U, 2U).i32();
2160 BASIC_BLOCK(2U, 3U, 4U)
2161 {
2162 INST(3U, Opcode::StoreObject).i32().Inputs(1U, 2U).TypeId(122U);
2163 INST(4U, Opcode::SaveState).Inputs(1U).SrcVregs({0U});
2164 INST(5U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(0U);
2165 }
2166 BASIC_BLOCK(3U, 5U)
2167 {
2168 INST(6U, Opcode::CallVirtual).v0id().InputsAutoType(1U, 2U, 4U).Inlined();
2169 INST(8U, Opcode::ReturnInlined).v0id().Inputs(4U);
2170 }
2171 BASIC_BLOCK(4U, 5U)
2172 {
2173 INST(9U, Opcode::CallVirtual).v0id().InputsAutoType(1U, 2U, 4U).Inlined();
2174 INST(11U, Opcode::ReturnInlined).v0id().Inputs(4U);
2175 }
2176 BASIC_BLOCK(5U, -1L)
2177 {
2178 INST(13U, Opcode::Return).i32().Inputs(2U);
2179 }
2180 }
2181 }
2182
TEST_F(LSETest,OverInlinedVirtualCall)2183 TEST_F(LSETest, OverInlinedVirtualCall)
2184 {
2185 src_graph::OverInlinedVirtualCall::CREATE(GetGraph());
2186 Graph *graphLsed = CreateEmptyGraph();
2187 out_graph::OverInlinedVirtualCall::CREATE(graphLsed);
2188 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2189 GraphChecker(GetGraph()).Check();
2190 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2191 }
2192
2193 /// Counter case with aliased store
TEST_F(LSETest,SameArrayAccessesWithOverwrite)2194 TEST_F(LSETest, SameArrayAccessesWithOverwrite)
2195 {
2196 GRAPH(GetGraph())
2197 {
2198 PARAMETER(0U, 0U).ref();
2199 CONSTANT(5U, 0x1U).s64();
2200 CONSTANT(9U, 0x0U).s64();
2201 CONSTANT(32U, 0x2U).s64();
2202 CONSTANT(58U, 0x3U).s64();
2203 BASIC_BLOCK(2U, 1U)
2204 {
2205 INST(4U, Opcode::LoadObject).ref().TypeId(302U).Inputs(0U);
2206 INST(8U, Opcode::LoadObject).ref().TypeId(312U).Inputs(0U);
2207
2208 INST(14U, Opcode::LoadArray).s64().Inputs(8U, 9U);
2209 INST(22U, Opcode::LoadArray).s64().Inputs(8U, 5U);
2210 INST(23U, Opcode::Or).s64().Inputs(14U, 22U);
2211 INST(28U, Opcode::StoreArray).s64().Inputs(4U, 9U, 23U);
2212
2213 // Same to 14 but i4 and i8 may be aliased and v28 may overwrite
2214 // previous load
2215 INST(40U, Opcode::LoadArray).s64().Inputs(8U, 9U);
2216 INST(48U, Opcode::LoadArray).s64().Inputs(8U, 32U);
2217 INST(49U, Opcode::Or).s64().Inputs(40U, 48U);
2218 INST(54U, Opcode::StoreArray).s64().Inputs(4U, 32U, 49U);
2219
2220 INST(81U, Opcode::ReturnVoid).v0id();
2221 }
2222 }
2223 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
2224 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
2225 GraphChecker(GetGraph()).Check();
2226 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
2227 }
2228
2229 /// Counter case with unknown index
TEST_F(LSETest,SameArrayAccessesWithUnknownIndices)2230 TEST_F(LSETest, SameArrayAccessesWithUnknownIndices)
2231 {
2232 GRAPH(GetGraph())
2233 {
2234 PARAMETER(0U, 0U).ref();
2235 PARAMETER(1U, 1U).s64();
2236 CONSTANT(5U, 0x1U).s64();
2237 CONSTANT(32U, 0x2U).s64();
2238 CONSTANT(58U, 0x3U).s64();
2239 BASIC_BLOCK(2U, 1U)
2240 {
2241 INST(4U, Opcode::LoadObject).ref().TypeId(302U).Inputs(0U);
2242 INST(8U, Opcode::LoadObject).ref().TypeId(312U).Inputs(0U);
2243
2244 INST(14U, Opcode::LoadArray).s64().Inputs(8U, 1U);
2245 INST(22U, Opcode::LoadArray).s64().Inputs(8U, 5U);
2246 INST(23U, Opcode::Or).s64().Inputs(14U, 22U);
2247 INST(28U, Opcode::StoreArray).s64().Inputs(4U, 5U, 23U);
2248
2249 // Same to v14 but index is unknown, it may be equal to v5
2250 INST(40U, Opcode::LoadArray).s64().Inputs(8U, 1U);
2251 INST(48U, Opcode::LoadArray).s64().Inputs(8U, 32U);
2252 INST(49U, Opcode::Or).s64().Inputs(40U, 48U);
2253 INST(54U, Opcode::StoreArray).s64().Inputs(4U, 32U, 49U);
2254
2255 INST(81U, Opcode::ReturnVoid).v0id();
2256 }
2257 }
2258 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
2259 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
2260 GraphChecker(GetGraph()).Check();
2261 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
2262 }
2263
2264 /// A store does not dominate a load
TEST_F(LSETest,NoDominationHere)2265 TEST_F(LSETest, NoDominationHere)
2266 {
2267 std::vector<Graph *> equalGraphs = {GetGraph(), CreateEmptyGraph()};
2268 for (auto graph : equalGraphs) {
2269 GRAPH(graph)
2270 {
2271 PARAMETER(0U, 0U).ref();
2272 PARAMETER(1U, 1U).s64();
2273 BASIC_BLOCK(2U, 3U, 4U)
2274 {
2275 INST(2U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 1U);
2276 INST(3U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(2U);
2277 }
2278 BASIC_BLOCK(4U, 3U)
2279 {
2280 INST(8U, Opcode::StoreArray).s64().Inputs(0U, 1U, 1U);
2281 }
2282 BASIC_BLOCK(3U, -1L)
2283 {
2284 INST(14U, Opcode::LoadArray).s64().Inputs(0U, 1U);
2285 INST(15U, Opcode::Return).s64().Inputs(14U);
2286 }
2287 }
2288 }
2289 ASSERT_FALSE(equalGraphs[0U]->RunPass<Lse>());
2290 GraphChecker(equalGraphs[0U]).Check();
2291 ASSERT_TRUE(GraphComparator().Compare(equalGraphs[0U], equalGraphs[1U]));
2292 }
2293
SRC_GRAPH(EliminateMonitoredStores,Graph * graph)2294 SRC_GRAPH(EliminateMonitoredStores, Graph *graph)
2295 {
2296 GRAPH(graph)
2297 {
2298 PARAMETER(0U, 0U).ref();
2299 PARAMETER(1U, 1U).s64();
2300 CONSTANT(2U, 1U);
2301 BASIC_BLOCK(2U, -1L)
2302 {
2303 INST(15U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
2304 INST(3U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
2305 INST(4U, Opcode::Monitor).v0id().Entry().Inputs(0U, 15U);
2306 INST(5U, Opcode::Add).s64().Inputs(1U, 2U);
2307 INST(6U, Opcode::StoreObject).s64().Inputs(0U, 5U).TypeId(243U);
2308 INST(7U, Opcode::Add).s64().Inputs(5U, 2U);
2309 INST(8U, Opcode::StoreObject).s64().Inputs(0U, 7U).TypeId(243U);
2310 INST(16U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
2311 INST(9U, Opcode::Monitor).v0id().Exit().Inputs(0U, 16U);
2312 INST(10U, Opcode::Add).s64().Inputs(7U, 2U);
2313 INST(11U, Opcode::StoreObject).s64().Inputs(0U, 10U).TypeId(243U);
2314 INST(12U, Opcode::Add).s64().Inputs(10U, 2U);
2315 INST(13U, Opcode::StoreObject).s64().Inputs(0U, 12U).TypeId(243U);
2316 INST(14U, Opcode::ReturnVoid).v0id();
2317 }
2318 }
2319 }
2320
OUT_GRAPH(EliminateMonitoredStores,Graph * graph)2321 OUT_GRAPH(EliminateMonitoredStores, Graph *graph)
2322 {
2323 GRAPH(graph)
2324 {
2325 PARAMETER(0U, 0U).ref();
2326 PARAMETER(1U, 1U).s64();
2327 CONSTANT(2U, 1U);
2328 BASIC_BLOCK(2U, -1L)
2329 {
2330 INST(15U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
2331 INST(3U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
2332 INST(4U, Opcode::Monitor).v0id().Entry().Inputs(0U, 15U);
2333 INST(5U, Opcode::Add).s64().Inputs(1U, 2U);
2334 INST(7U, Opcode::Add).s64().Inputs(5U, 2U);
2335 INST(8U, Opcode::StoreObject).s64().Inputs(0U, 7U).TypeId(243U);
2336 INST(16U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
2337 INST(9U, Opcode::Monitor).v0id().Exit().Inputs(0U, 16U);
2338 INST(10U, Opcode::Add).s64().Inputs(7U, 2U);
2339 INST(12U, Opcode::Add).s64().Inputs(10U, 2U);
2340 INST(13U, Opcode::StoreObject).s64().Inputs(0U, 12U).TypeId(243U);
2341 INST(14U, Opcode::ReturnVoid).v0id();
2342 }
2343 }
2344 }
2345
TEST_F(LSETest,EliminateMonitoredStores)2346 TEST_F(LSETest, EliminateMonitoredStores)
2347 {
2348 src_graph::EliminateMonitoredStores::CREATE(GetGraph());
2349 Graph *graphLsed = CreateEmptyGraph();
2350 out_graph::EliminateMonitoredStores::CREATE(graphLsed);
2351 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2352 GraphChecker(GetGraph()).Check();
2353 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2354 }
2355
TEST_F(LSETest,EliminateMonitoredLoads)2356 TEST_F(LSETest, EliminateMonitoredLoads)
2357 {
2358 GRAPH(GetGraph())
2359 {
2360 PARAMETER(0U, 0U).ref();
2361 BASIC_BLOCK(2U, -1L)
2362 {
2363 INST(11U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
2364 INST(1U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2365 INST(2U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2366 INST(3U, Opcode::Monitor).v0id().Entry().Inputs(0U, 11U);
2367 INST(4U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2368 INST(5U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2369 INST(12U, Opcode::SaveState).Inputs(0U, 1U, 2U, 4U, 5U).SrcVregs({0U, 1U, 2U, 4U, 5U});
2370 INST(6U, Opcode::Monitor).v0id().Exit().Inputs(0U, 12U);
2371 INST(7U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2372 INST(8U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2373 INST(13U, Opcode::SaveState).Inputs(0U, 1U, 2U, 4U, 5U, 7U, 8U).SrcVregs({0U, 1U, 2U, 4U, 5U, 7U, 8U});
2374 INST(9U, Opcode::CallStatic).b().InputsAutoType(1U, 2U, 4U, 5U, 7U, 8U, 13U);
2375 INST(10U, Opcode::Return).b().Inputs(9U);
2376 }
2377 }
2378 Graph *graphLsed = CreateEmptyGraph();
2379 GRAPH(graphLsed)
2380 {
2381 PARAMETER(0U, 0U).ref();
2382 BASIC_BLOCK(2U, -1L)
2383 {
2384 INST(11U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
2385 INST(1U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2386 INST(3U, Opcode::Monitor).v0id().Entry().Inputs(0U, 11U);
2387 INST(4U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2388 INST(12U, Opcode::SaveState).Inputs(0U, 1U, 1U, 4U, 4U).SrcVregs({0U, 1U, 2U, 4U, 5U});
2389 INST(6U, Opcode::Monitor).v0id().Exit().Inputs(0U, 12U);
2390 INST(13U, Opcode::SaveState).Inputs(0U, 1U, 1U, 4U, 4U, 4U, 4U).SrcVregs({0U, 1U, 2U, 4U, 5U, 7U, 8U});
2391 INST(9U, Opcode::CallStatic).b().InputsAutoType(1U, 1U, 4U, 4U, 4U, 4U, 13U);
2392 INST(10U, Opcode::Return).b().Inputs(9U);
2393 }
2394 }
2395 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2396 GraphChecker(GetGraph()).Check();
2397 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2398 }
2399
2400 /// Stores that cannot be eliminated due to monitors
TEST_F(LSETest,NotEliminableMonitoredStores)2401 TEST_F(LSETest, NotEliminableMonitoredStores)
2402 {
2403 std::vector<Graph *> equalGraphs = {GetGraph(), CreateEmptyGraph()};
2404 for (auto graph : equalGraphs) {
2405 GRAPH(graph)
2406 {
2407 PARAMETER(0U, 0U).ref();
2408 PARAMETER(1U, 1U).s64();
2409 BASIC_BLOCK(2U, -1L)
2410 {
2411 INST(9U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
2412 INST(7U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
2413 INST(2U, Opcode::Monitor).v0id().Entry().Inputs(0U, 7U);
2414 INST(5U, Opcode::StoreObject).s64().Inputs(0U, 1U).TypeId(243U);
2415 INST(8U, Opcode::SaveState).Inputs(0U, 1U).SrcVregs({0U, 1U});
2416 INST(6U, Opcode::Monitor).v0id().Exit().Inputs(0U, 8U);
2417 INST(10U, Opcode::ReturnVoid).v0id();
2418 }
2419 }
2420 }
2421 ASSERT_TRUE(equalGraphs[0U]->RunPass<MonitorAnalysis>());
2422 ASSERT_FALSE(equalGraphs[0U]->RunPass<Lse>());
2423 GraphChecker(equalGraphs[0U]).Check();
2424 ASSERT_TRUE(GraphComparator().Compare(equalGraphs[0U], equalGraphs[1U]));
2425 }
2426
TEST_F(LSETest,NotEliminableMonitoredLoadStore)2427 TEST_F(LSETest, NotEliminableMonitoredLoadStore)
2428 {
2429 std::vector<Graph *> equalGraphs = {GetGraph(), CreateEmptyGraph()};
2430 for (auto graph : equalGraphs) {
2431 GRAPH(graph)
2432 {
2433 PARAMETER(0U, 0U).ref();
2434 BASIC_BLOCK(2U, -1L)
2435 {
2436 INST(9U, Opcode::LoadObject).s64().Inputs(0U).TypeId(243U);
2437 INST(7U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
2438 INST(2U, Opcode::Monitor).v0id().Entry().Inputs(0U, 7U);
2439 INST(5U, Opcode::StoreObject).s64().Inputs(0U, 9U).TypeId(243U);
2440 INST(8U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
2441 INST(6U, Opcode::Monitor).v0id().Exit().Inputs(0U, 8U);
2442 INST(10U, Opcode::ReturnVoid).v0id();
2443 }
2444 }
2445 }
2446 ASSERT_TRUE(equalGraphs[0U]->RunPass<MonitorAnalysis>());
2447 ASSERT_FALSE(equalGraphs[0U]->RunPass<Lse>());
2448 GraphChecker(equalGraphs[0U]).Check();
2449 ASSERT_TRUE(GraphComparator().Compare(equalGraphs[0U], equalGraphs[1U]));
2450 }
2451
2452 /// Inner loop overwrites outer loop reference. No elimination
SRC_GRAPH(InnerOverwrite,Graph * graph)2453 SRC_GRAPH(InnerOverwrite, Graph *graph)
2454 {
2455 GRAPH(graph)
2456 {
2457 PARAMETER(0U, 0U).ref();
2458 PARAMETER(1U, 1U).ref();
2459 CONSTANT(8U, 0x0U).s64();
2460 CONSTANT(53U, 0x1U).s64();
2461 BASIC_BLOCK(2U, 8U)
2462 {
2463 INST(4U, Opcode::LoadObject).ref().Inputs(0U).TypeId(194U);
2464 INST(7U, Opcode::LenArray).s32().Inputs(4U);
2465 }
2466 // For (v11 = 0, v11 < lenarr(v4), v11++)
2467 BASIC_BLOCK(8U, 3U, 4U)
2468 {
2469 INST(11U, Opcode::Phi).s32().Inputs({{2U, 8U}, {5U, 63U}});
2470 INST(12U, Opcode::Phi).s32().Inputs({{2U, 8U}, {5U, 62U}});
2471 INST(17U, Opcode::Cmp).s32().Inputs(11U, 7U);
2472 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(17U, 8U);
2473 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
2474 }
2475 BASIC_BLOCK(4U, 5U, 6U)
2476 {
2477 INST(22U, Opcode::LenArray).s32().Inputs(1U);
2478 INST(65U, Opcode::Cmp).s32().Inputs(8U, 22U);
2479 INST(66U, Opcode::Compare).b().CC(CC_GE).Inputs(65U, 8U);
2480 INST(67U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(66U);
2481 }
2482 // For (v28 = 0, v28 < lenarr(v1), v28++)
2483 // v4 = v28[v4[v11]]
2484 BASIC_BLOCK(6U, 5U, 6U)
2485 {
2486 INST(28U, Opcode::Phi).s32().Inputs({{4U, 8U}, {6U, 52U}});
2487 INST(38U, Opcode::LoadObject).ref().Inputs(0U).TypeId(194U); // Cannot eliminate due to v51
2488 INST(43U, Opcode::LoadArray).s32().Inputs(38U, 11U);
2489 INST(48U, Opcode::LoadArray).ref().Inputs(1U, 43U);
2490 INST(51U, Opcode::StoreObject).ref().Inputs(0U, 48U).TypeId(194U);
2491 INST(52U, Opcode::Add).s32().Inputs(28U, 53U);
2492 INST(33U, Opcode::Cmp).s32().Inputs(52U, 22U);
2493 INST(34U, Opcode::Compare).b().CC(CC_GE).Inputs(33U, 8U);
2494 INST(35U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(34U);
2495 }
2496 // v12 += v4[v11]
2497 BASIC_BLOCK(5U, 8U)
2498 {
2499 INST(56U, Opcode::LoadObject).ref().Inputs(0U).TypeId(194U); // Cannot eliminate due to v51
2500 INST(61U, Opcode::LoadArray).s32().Inputs(56U, 11U);
2501 INST(62U, Opcode::Add).s32().Inputs(61U, 12U);
2502 INST(63U, Opcode::Add).s32().Inputs(11U, 53U);
2503 }
2504 BASIC_BLOCK(3U, -1L)
2505 {
2506 INST(64U, Opcode::Return).s32().Inputs(12U);
2507 }
2508 }
2509 }
2510
TEST_F(LSETest,InnerOverwrite)2511 TEST_F(LSETest, InnerOverwrite)
2512 {
2513 src_graph::InnerOverwrite::CREATE(GetGraph());
2514 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
2515 ASSERT_FALSE(GetGraph()->RunPass<Lse>(false));
2516 GraphChecker(GetGraph()).Check();
2517 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
2518 }
2519
2520 /// Outer loop overwrites inner loop reference.
SRC_GRAPH(OuterOverwrite,Graph * graph)2521 SRC_GRAPH(OuterOverwrite, Graph *graph)
2522 {
2523 GRAPH(graph)
2524 {
2525 PARAMETER(0U, 0U).ref();
2526 PARAMETER(1U, 1U).ref();
2527 CONSTANT(8U, 0x0U).s64();
2528 CONSTANT(46U, 0x1U).s64();
2529 BASIC_BLOCK(2U, 8U)
2530 {
2531 INST(4U, Opcode::LoadObject).ref().Inputs(0U).TypeId(194U);
2532 INST(7U, Opcode::LenArray).s32().Inputs(4U);
2533 }
2534 // For (v11 = 0, v11 < lenarr(v4), v11++)
2535 BASIC_BLOCK(8U, 3U, 4U)
2536 {
2537 INST(11U, Opcode::Phi).s32().Inputs({{2U, 8U}, {5U, 55U}});
2538 INST(12U, Opcode::Phi).s32().Inputs({{2U, 8U}, {5U, 62U}});
2539 INST(17U, Opcode::Cmp).s32().Inputs(11U, 7U);
2540 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(17U, 8U);
2541 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
2542 }
2543 BASIC_BLOCK(4U, 5U, 6U)
2544 {
2545 INST(57U, Opcode::Cmp).s32().Inputs(8U, 7U);
2546 INST(58U, Opcode::Compare).b().CC(CC_GE).Inputs(57U, 8U);
2547 INST(59U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(58U);
2548 }
2549 // For (v28 = 0, v28 < lenarr(v4), v28++)
2550 // v12 += v4[v28]
2551 BASIC_BLOCK(6U, 5U, 6U)
2552 {
2553 INST(26U, Opcode::Phi).s32().Inputs({{4U, 12U}, {6U, 44U}});
2554 INST(28U, Opcode::Phi).s32().Inputs({{4U, 8U}, {6U, 45U}});
2555 INST(38U, Opcode::LoadObject).ref().Inputs(0U).TypeId(194U);
2556 INST(43U, Opcode::LoadArray).s32().Inputs(38U, 28U);
2557 INST(44U, Opcode::Add).s32().Inputs(43U, 26U);
2558 INST(45U, Opcode::Add).s32().Inputs(28U, 46U);
2559 INST(33U, Opcode::Cmp).s32().Inputs(45U, 7U);
2560 INST(34U, Opcode::Compare).b().CC(CC_GE).Inputs(33U, 8U);
2561 INST(35U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(34U);
2562 }
2563 // v4 = v1[v11]
2564 BASIC_BLOCK(5U, 8U)
2565 {
2566 INST(62U, Opcode::Phi).s32().Inputs({{6U, 44U}, {4U, 12U}});
2567 INST(51U, Opcode::LoadArray).ref().Inputs(1U, 11U);
2568 INST(54U, Opcode::StoreObject).ref().Inputs(0U, 51U).TypeId(194U);
2569 INST(55U, Opcode::Add).s32().Inputs(11U, 46U);
2570 }
2571 BASIC_BLOCK(3U, -1L)
2572 {
2573 INST(56U, Opcode::Return).s32().Inputs(12U);
2574 }
2575 }
2576 }
2577
OUT_GRAPH(OuterOverwrite,Graph * graph)2578 OUT_GRAPH(OuterOverwrite, Graph *graph)
2579 {
2580 GRAPH(graph)
2581 {
2582 PARAMETER(0U, 0U).ref();
2583 PARAMETER(1U, 1U).ref();
2584 CONSTANT(8U, 0x0U).s64();
2585 CONSTANT(46U, 0x1U).s64();
2586 BASIC_BLOCK(2U, 8U)
2587 {
2588 INST(4U, Opcode::LoadObject).ref().Inputs(0U).TypeId(194U);
2589 INST(7U, Opcode::LenArray).s32().Inputs(4U);
2590 }
2591 // For (v11 = 0, v11 < lenarr(v4), v11++)
2592 BASIC_BLOCK(8U, 3U, 4U)
2593 {
2594 INST(11U, Opcode::Phi).s32().Inputs({{2U, 8U}, {5U, 55U}});
2595 INST(12U, Opcode::Phi).s32().Inputs({{2U, 8U}, {5U, 62U}});
2596 INST(13U, Opcode::Phi).ref().Inputs({{2U, 4U}, {5U, 51U}});
2597 INST(17U, Opcode::Cmp).s32().Inputs(11U, 7U);
2598 INST(18U, Opcode::Compare).b().CC(CC_GE).Inputs(17U, 8U);
2599 INST(19U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(18U);
2600 }
2601 BASIC_BLOCK(4U, 5U, 6U)
2602 {
2603 INST(57U, Opcode::Cmp).s32().Inputs(8U, 7U);
2604 INST(58U, Opcode::Compare).b().CC(CC_GE).Inputs(57U, 8U);
2605 INST(59U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(58U);
2606 }
2607 // For (v28 = 0, v28 < lenarr(v4), v28++)
2608 // v12 += v4[v28]
2609 BASIC_BLOCK(6U, 5U, 6U)
2610 {
2611 INST(26U, Opcode::Phi).s32().Inputs({{4U, 12U}, {6U, 44U}});
2612 INST(28U, Opcode::Phi).s32().Inputs({{4U, 8U}, {6U, 45U}});
2613 INST(43U, Opcode::LoadArray).s32().Inputs(13U, 28U);
2614 INST(44U, Opcode::Add).s32().Inputs(43U, 26U);
2615 INST(45U, Opcode::Add).s32().Inputs(28U, 46U);
2616 INST(33U, Opcode::Cmp).s32().Inputs(45U, 7U);
2617 INST(34U, Opcode::Compare).b().CC(CC_GE).Inputs(33U, 8U);
2618 INST(35U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(34U);
2619 }
2620 // v4 = v1[v11]
2621 BASIC_BLOCK(5U, 8U)
2622 {
2623 INST(62U, Opcode::Phi).s32().Inputs({{6U, 44U}, {4U, 12U}});
2624 INST(51U, Opcode::LoadArray).ref().Inputs(1U, 11U);
2625 INST(54U, Opcode::StoreObject).ref().Inputs(0U, 51U).TypeId(194U);
2626 INST(55U, Opcode::Add).s32().Inputs(11U, 46U);
2627 }
2628 BASIC_BLOCK(3U, -1L)
2629 {
2630 INST(56U, Opcode::Return).s32().Inputs(12U);
2631 }
2632 }
2633 }
2634
TEST_F(LSETest,OuterOverwrite)2635 TEST_F(LSETest, OuterOverwrite)
2636 {
2637 src_graph::OuterOverwrite::CREATE(GetGraph());
2638 Graph *graphLsed = CreateEmptyGraph();
2639 out_graph::OuterOverwrite::CREATE(graphLsed);
2640 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2641 GraphChecker(GetGraph()).Check();
2642 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2643 }
2644
2645 /// Invalidating phi candidates
TEST_F(LSETest,PhiCandOverCall)2646 TEST_F(LSETest, PhiCandOverCall)
2647 {
2648 GRAPH(GetGraph())
2649 {
2650 PARAMETER(0U, 0U).ref();
2651 CONSTANT(7U, 0x0U).s64();
2652 CONSTANT(28U, 0x1U).s64();
2653 BASIC_BLOCK(2U, 3U, 4U)
2654 {
2655 INST(2U, Opcode::LoadObject).ref().Inputs(0U).TypeId(130U);
2656 INST(3U, Opcode::LoadObject).ref().Inputs(2U).TypeId(242U);
2657 INST(4U, Opcode::LenArray).s32().Inputs(3U);
2658 INST(30U, Opcode::Cmp).s32().Inputs(7U, 4U);
2659 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(30U, 7U);
2660 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
2661 }
2662 // For (v10 = 0, v10 < lenarr(v3), ++v10)
2663 // v11 += v3[v10]
2664 BASIC_BLOCK(4U, 3U, 4U)
2665 {
2666 INST(10U, Opcode::Phi).s32().Inputs({{2U, 7U}, {4U, 27U}});
2667 INST(11U, Opcode::Phi).s32().Inputs({{2U, 7U}, {4U, 26U}});
2668 INST(40U, Opcode::SaveState).NoVregs();
2669 INST(18U, Opcode::CallStatic).v0id().InputsAutoType(2U, 40U);
2670 // Can't eliminated v19 because array may be overwritted in v4
2671 INST(19U, Opcode::LoadObject).ref().Inputs(0U).TypeId(130U);
2672 INST(20U, Opcode::LoadObject).ref().Inputs(19U).TypeId(242U);
2673
2674 INST(25U, Opcode::LoadArray).s32().Inputs(20U, 10U);
2675
2676 INST(26U, Opcode::Add).s32().Inputs(25U, 11U);
2677 INST(27U, Opcode::Add).s32().Inputs(10U, 28U);
2678 INST(16U, Opcode::Compare).b().CC(CC_GE).Inputs(27U, 4U);
2679 INST(17U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(16U);
2680 }
2681 BASIC_BLOCK(3U, -1L)
2682 {
2683 INST(35U, Opcode::Phi).s32().Inputs({{4U, 26U}, {2U, 7U}});
2684 INST(29U, Opcode::Return).s32().Inputs(35U);
2685 }
2686 }
2687 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
2688 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
2689 GraphChecker(GetGraph()).Check();
2690 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
2691 }
2692
2693 /// Not dominated volatile load
TEST_F(LSETest,NotDominatedVolatileLoad)2694 TEST_F(LSETest, NotDominatedVolatileLoad)
2695 {
2696 GRAPH(GetGraph())
2697 {
2698 PARAMETER(0U, 0U).ref();
2699 PARAMETER(1U, 1U).s32();
2700 PARAMETER(2U, 2U).s32();
2701 CONSTANT(7U, 0x0U).s64();
2702 BASIC_BLOCK(2U, 3U, 4U)
2703 {
2704 INST(5U, Opcode::LoadObject).s32().Inputs(0U).TypeId(152U);
2705 INST(6U, Opcode::Compare).b().CC(CC_EQ).Inputs(2U, 7U);
2706 INST(8U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(6U);
2707 }
2708 BASIC_BLOCK(4U, 3U)
2709 {
2710 INST(11U, Opcode::LoadObject).s32().Volatile().Inputs(0U).TypeId(138U);
2711 }
2712 BASIC_BLOCK(3U, -1L)
2713 {
2714 INST(12U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 11U}});
2715 INST(14U, Opcode::SaveState).Inputs(2U, 1U, 0U, 12U, 5U).SrcVregs({4U, 3U, 2U, 1U, 0U});
2716 INST(15U, Opcode::NullCheck).ref().Inputs(0U, 14U);
2717 // v16 is not eliminable due to volatile load v11
2718 INST(16U, Opcode::LoadObject).s32().Inputs(0U).TypeId(152U);
2719 INST(17U, Opcode::Add).s32().Inputs(16U, 12U);
2720 INST(18U, Opcode::Return).s32().Inputs(17U);
2721 }
2722 }
2723 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
2724 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
2725 GraphChecker(GetGraph()).Check();
2726 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
2727 }
2728
2729 /// If we eliminate load over safepoint, check that it is correctly bridged
TEST_F(LSETest,LoadsWithSafePoint)2730 TEST_F(LSETest, LoadsWithSafePoint)
2731 {
2732 GRAPH(GetGraph())
2733 {
2734 PARAMETER(0U, 0U).ref();
2735 BASIC_BLOCK(2U, -1L)
2736 {
2737 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
2738 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 3U).TypeId(122U);
2739
2740 INST(7U, Opcode::SafePoint).Inputs(0U).SrcVregs({0U});
2741 // Eliminable because of v6 but v6 can be relocated by GC
2742 INST(8U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
2743 // Eliminable because of v3 but v3 can be relocated by GC
2744 INST(9U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
2745 INST(10U, Opcode::SaveState).Inputs(8U).SrcVregs({0U});
2746 INST(11U, Opcode::NullCheck).ref().Inputs(9U, 10U);
2747 INST(12U, Opcode::Return).ref().Inputs(8U);
2748 }
2749 }
2750
2751 Graph *graphLsed = CreateEmptyGraph();
2752 GRAPH(graphLsed)
2753 {
2754 PARAMETER(0U, 0U).ref();
2755 BASIC_BLOCK(2U, -1L)
2756 {
2757 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
2758 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 3U).TypeId(122U);
2759
2760 INST(7U, Opcode::SafePoint).Inputs(0U, 3U).SrcVregs({0U, VirtualRegister::BRIDGE});
2761 INST(10U, Opcode::SaveState).Inputs(3U).SrcVregs({0U});
2762 INST(11U, Opcode::NullCheck).ref().Inputs(3U, 10U);
2763 INST(12U, Opcode::Return).ref().Inputs(3U);
2764 }
2765 }
2766
2767 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2768 GraphChecker(GetGraph()).Check();
2769 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2770 }
2771
2772 /// Pool constants can be relocated as well and should be bridged.
TEST_F(LSETest,RelocatablePoolConstants)2773 TEST_F(LSETest, RelocatablePoolConstants)
2774 {
2775 GRAPH(GetGraph())
2776 {
2777 BASIC_BLOCK(2U, -1L)
2778 {
2779 INST(0U, Opcode::SaveState).NoVregs();
2780 INST(1U, Opcode::LoadAndInitClass).ref().Inputs(0U);
2781
2782 INST(2U, Opcode::SaveState).NoVregs();
2783 INST(3U, Opcode::LoadString).ref().Inputs(2U).TypeId(42U);
2784 INST(4U, Opcode::StoreStatic).ref().Inputs(1U, 3U);
2785
2786 INST(7U, Opcode::SafePoint).NoVregs();
2787
2788 INST(8U, Opcode::SaveState).NoVregs();
2789 INST(9U, Opcode::LoadString).ref().Inputs(8U).TypeId(42U);
2790 INST(10U, Opcode::StoreStatic).ref().Inputs(1U, 9U);
2791
2792 INST(11U, Opcode::ReturnVoid);
2793 }
2794 }
2795
2796 Graph *graphLsed = CreateEmptyGraph();
2797 GRAPH(graphLsed)
2798 {
2799 BASIC_BLOCK(2U, -1L)
2800 {
2801 INST(0U, Opcode::SaveState).NoVregs();
2802 INST(1U, Opcode::LoadAndInitClass).ref().Inputs(0U);
2803
2804 INST(2U, Opcode::SaveState).NoVregs();
2805 INST(3U, Opcode::LoadString).ref().Inputs(2U).TypeId(42U);
2806 INST(4U, Opcode::StoreStatic).ref().Inputs(1U, 3U);
2807
2808 INST(7U, Opcode::SafePoint).Inputs(3U).SrcVregs({VirtualRegister::BRIDGE});
2809
2810 INST(10U, Opcode::StoreStatic).ref().Inputs(1U, 3U);
2811
2812 INST(11U, Opcode::ReturnVoid);
2813 }
2814 }
2815
2816 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2817 GraphChecker(GetGraph()).Check();
2818 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2819 }
2820
2821 /// If we replace load in loop by value stored before loop, check that it's correctly bridged in any loop safepoints
TEST_F(LSETest,StoreAndLoadLoopWithSafepoint)2822 TEST_F(LSETest, StoreAndLoadLoopWithSafepoint)
2823 {
2824 GRAPH(GetGraph())
2825 {
2826 PARAMETER(0U, 0U).ref();
2827 PARAMETER(1U, 1U).ref();
2828 BASIC_BLOCK(2U, 3U)
2829 {
2830 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
2831 }
2832 BASIC_BLOCK(3U, 3U, 4U)
2833 {
2834 INST(7U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
2835 INST(8U, Opcode::SafePoint).Inputs(0U).SrcVregs({0U});
2836 INST(9U, Opcode::IfImm).SrcType(DataType::REFERENCE).CC(CC_NE).Imm(0U).Inputs(7U);
2837 }
2838 BASIC_BLOCK(4U, -1L)
2839 {
2840 INST(10U, Opcode::Return).ref().Inputs(7U);
2841 }
2842 }
2843
2844 Graph *graphLsed = CreateEmptyGraph();
2845 GRAPH(graphLsed)
2846 {
2847 PARAMETER(0U, 0U).ref();
2848 PARAMETER(1U, 1U).ref();
2849 BASIC_BLOCK(2U, 3U)
2850 {
2851 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
2852 }
2853 BASIC_BLOCK(3U, 3U, 4U)
2854 {
2855 INST(8U, Opcode::SafePoint).Inputs(0U, 1U).SrcVregs({0U, VirtualRegister::BRIDGE});
2856 INST(9U, Opcode::IfImm).SrcType(DataType::REFERENCE).CC(CC_NE).Imm(0U).Inputs(1U);
2857 }
2858 BASIC_BLOCK(4U, -1L)
2859 {
2860 INST(10U, Opcode::Return).ref().Inputs(1U);
2861 }
2862 }
2863 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2864 GraphChecker(GetGraph()).Check();
2865 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2866 }
2867
2868 /// If we hoist load from loop, check that it's correctly bridged in any loop safepoints
TEST_F(LSETest,HoistFromLoopWithSafepoint)2869 TEST_F(LSETest, HoistFromLoopWithSafepoint)
2870 {
2871 GRAPH(GetGraph())
2872 {
2873 PARAMETER(0U, 0U).ref();
2874 PARAMETER(1U, 1U).ref();
2875 BASIC_BLOCK(2U, 3U) {}
2876 BASIC_BLOCK(3U, 3U, 4U)
2877 {
2878 INST(7U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
2879 INST(8U, Opcode::SafePoint).Inputs(0U).SrcVregs({0U});
2880 INST(9U, Opcode::IfImm).SrcType(DataType::REFERENCE).CC(CC_NE).Imm(0U).Inputs(7U);
2881 }
2882 BASIC_BLOCK(4U, -1L)
2883 {
2884 INST(10U, Opcode::Return).ref().Inputs(7U);
2885 }
2886 }
2887
2888 Graph *graphLsed = CreateEmptyGraph();
2889 GRAPH(graphLsed)
2890 {
2891 PARAMETER(0U, 0U).ref();
2892 PARAMETER(1U, 1U).ref();
2893 BASIC_BLOCK(2U, 3U)
2894 {
2895 INST(7U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
2896 }
2897 BASIC_BLOCK(3U, 3U, 4U)
2898 {
2899 INST(8U, Opcode::SafePoint).Inputs(0U, 7U).SrcVregs({0U, VirtualRegister::BRIDGE});
2900 INST(9U, Opcode::IfImm).SrcType(DataType::REFERENCE).CC(CC_NE).Imm(0U).Inputs(7U);
2901 }
2902 BASIC_BLOCK(4U, -1L)
2903 {
2904 INST(10U, Opcode::Return).ref().Inputs(7U);
2905 }
2906 }
2907 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2908 GraphChecker(GetGraph()).Check();
2909 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2910 }
2911
2912 /// Store that is not read, but overwritten on all paths is removed
SRC_GRAPH(RemoveShadowedStore,Graph * graph)2913 SRC_GRAPH(RemoveShadowedStore, Graph *graph)
2914 {
2915 GRAPH(graph)
2916 {
2917 PARAMETER(0U, 0U).ref();
2918 PARAMETER(1U, 1U).s32();
2919 PARAMETER(2U, 2U).s32();
2920 CONSTANT(8U, 0x8U).s64();
2921 BASIC_BLOCK(2U, 3U, 4U)
2922 {
2923 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 2U, 1U);
2924 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
2925 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
2926 }
2927 BASIC_BLOCK(3U, 5U)
2928 {
2929 INST(21U, Opcode::Add).s32().Inputs(1U, 1U);
2930 INST(17U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
2931 }
2932 BASIC_BLOCK(4U, 5U)
2933 {
2934 INST(22U, Opcode::Mul).s32().Inputs(1U, 1U);
2935 INST(18U, Opcode::StoreArray).s32().Inputs(0U, 2U, 22U);
2936 }
2937 BASIC_BLOCK(5U, -1L)
2938 {
2939 INST(23U, Opcode::Return).s32().Inputs(2U);
2940 }
2941 }
2942 }
2943
OUT_GRAPH(RemoveShadowedStore,Graph * graph)2944 OUT_GRAPH(RemoveShadowedStore, Graph *graph)
2945 {
2946 GRAPH(graph)
2947 {
2948 PARAMETER(0U, 0U).ref();
2949 PARAMETER(1U, 1U).s32();
2950 PARAMETER(2U, 2U).s32();
2951 CONSTANT(8U, 0x8U).s64();
2952 BASIC_BLOCK(2U, 3U, 4U)
2953 {
2954 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
2955 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
2956 }
2957 BASIC_BLOCK(3U, 5U)
2958 {
2959 INST(21U, Opcode::Add).s32().Inputs(1U, 1U);
2960 INST(17U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
2961 }
2962 BASIC_BLOCK(4U, 5U)
2963 {
2964 INST(22U, Opcode::Mul).s32().Inputs(1U, 1U);
2965 INST(18U, Opcode::StoreArray).s32().Inputs(0U, 2U, 22U);
2966 }
2967 BASIC_BLOCK(5U, -1L)
2968 {
2969 INST(23U, Opcode::Return).s32().Inputs(2U);
2970 }
2971 }
2972 }
2973
TEST_F(LSETest,RemoveShadowedStore)2974 TEST_F(LSETest, RemoveShadowedStore)
2975 {
2976 src_graph::RemoveShadowedStore::CREATE(GetGraph());
2977 Graph *graphLsed = CreateEmptyGraph();
2978 out_graph::RemoveShadowedStore::CREATE(graphLsed);
2979 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
2980 GraphChecker(GetGraph()).Check();
2981 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
2982 }
2983
2984 /// Store that is not read, but not overwritten on all paths is not removed
TEST_F(LSETest,DontRemoveStoreIfPathWithoutShadowExists)2985 TEST_F(LSETest, DontRemoveStoreIfPathWithoutShadowExists)
2986 {
2987 GRAPH(GetGraph())
2988 {
2989 PARAMETER(0U, 0U).ref();
2990 PARAMETER(1U, 1U).s32();
2991 PARAMETER(2U, 2U).s32();
2992 CONSTANT(8U, 0x8U).s64();
2993 BASIC_BLOCK(2U, 3U, 4U)
2994 {
2995 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 2U, 1U);
2996 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
2997 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
2998 }
2999 BASIC_BLOCK(3U, 4U)
3000 {
3001 INST(21U, Opcode::Add).s32().Inputs(1U, 1U);
3002 INST(17U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
3003 }
3004 BASIC_BLOCK(4U, -1L)
3005 {
3006 INST(23U, Opcode::Return).s32().Inputs(2U);
3007 }
3008 }
3009 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3010 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3011 GraphChecker(GetGraph()).Check();
3012 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3013 }
3014
SRC_GRAPH(DISABLED_ShadowInInnerLoop,Graph * graph)3015 SRC_GRAPH(DISABLED_ShadowInInnerLoop, Graph *graph)
3016 {
3017 GRAPH(graph)
3018 {
3019 PARAMETER(0U, 0U).ref();
3020 PARAMETER(1U, 1U).s32();
3021 PARAMETER(2U, 2U).s32();
3022 CONSTANT(8U, 0x8U).s64();
3023 BASIC_BLOCK(2U, 3U, 4U)
3024 {
3025 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 2U, 1U);
3026 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
3027 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3028 }
3029 BASIC_BLOCK(3U, 5U)
3030 {
3031 INST(21U, Opcode::Add).s32().Inputs(1U, 1U);
3032 INST(17U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
3033 }
3034 BASIC_BLOCK(4U, 5U, 4U)
3035 {
3036 INST(6U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 22U}});
3037 INST(22U, Opcode::Add).s32().Inputs(6U, 1U);
3038 INST(18U, Opcode::StoreArray).s32().Inputs(0U, 2U, 22U);
3039 INST(11U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
3040 INST(12U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(11U);
3041 }
3042 BASIC_BLOCK(5U, -1L)
3043 {
3044 INST(23U, Opcode::Return).s32().Inputs(2U);
3045 }
3046 }
3047 }
3048
OUT_GRAPH(DISABLED_ShadowInInnerLoop,Graph * graph)3049 OUT_GRAPH(DISABLED_ShadowInInnerLoop, Graph *graph)
3050 {
3051 GRAPH(graph)
3052 {
3053 PARAMETER(0U, 0U).ref();
3054 PARAMETER(1U, 1U).s32();
3055 PARAMETER(2U, 2U).s32();
3056 CONSTANT(8U, 0x8U).s64();
3057 BASIC_BLOCK(2U, 3U, 4U)
3058 {
3059 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
3060 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3061 }
3062 BASIC_BLOCK(3U, 5U)
3063 {
3064 INST(21U, Opcode::Add).s32().Inputs(1U, 1U);
3065 INST(17U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
3066 }
3067 BASIC_BLOCK(4U, 5U, 4U)
3068 {
3069 INST(6U, Opcode::Phi).s32().Inputs({{2U, 1U}, {4U, 22U}});
3070 INST(22U, Opcode::Add).s32().Inputs(6U, 1U);
3071 INST(18U, Opcode::StoreArray).s32().Inputs(0U, 2U, 22U);
3072 INST(11U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
3073 INST(12U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(11U);
3074 }
3075 BASIC_BLOCK(5U, -1L)
3076 {
3077 INST(23U, Opcode::Return).s32().Inputs(2U);
3078 }
3079 }
3080 }
3081
TEST_F(LSETest,DISABLED_ShadowInInnerLoop)3082 TEST_F(LSETest, DISABLED_ShadowInInnerLoop)
3083 {
3084 src_graph::DISABLED_ShadowInInnerLoop::CREATE(GetGraph());
3085 Graph *graphLsed = CreateEmptyGraph();
3086 out_graph::DISABLED_ShadowInInnerLoop::CREATE(graphLsed);
3087 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
3088 GraphChecker(GetGraph()).Check();
3089 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
3090 }
3091
3092 /// Stores are not removed from loops, unless they're shadowed in the same loop
SRC_GRAPH(ShadowedStoresInLoop,Graph * graph)3093 SRC_GRAPH(ShadowedStoresInLoop, Graph *graph)
3094 {
3095 GRAPH(graph)
3096 {
3097 PARAMETER(0U, 0U).ref();
3098 PARAMETER(1U, 1U).s32();
3099 PARAMETER(2U, 2U).s32();
3100 CONSTANT(8U, 0x8U).s64();
3101 BASIC_BLOCK(2U, 3U) {}
3102 BASIC_BLOCK(3U, 4U, 3U)
3103 {
3104 INST(7U, Opcode::Phi).s32().Inputs({{2U, 1U}, {3U, 21U}});
3105 INST(21U, Opcode::Add).s32().Inputs(7U, 1U);
3106 INST(17U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
3107 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
3108 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3109 }
3110 BASIC_BLOCK(4U, 5U, 4U)
3111 {
3112 INST(27U, Opcode::Phi).s32().Inputs({{3U, 1U}, {4U, 21U}});
3113 INST(35U, Opcode::StoreArray).s32().Inputs(0U, 2U, 27U);
3114 INST(41U, Opcode::Mul).s32().Inputs(27U, 1U);
3115 INST(37U, Opcode::StoreArray).s32().Inputs(0U, 2U, 41U);
3116 INST(30U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3117 }
3118 BASIC_BLOCK(5U, 6U)
3119 {
3120 INST(28U, Opcode::Phi).s32().Inputs({{4U, 1U}, {6U, 41U}});
3121 INST(36U, Opcode::StoreArray).s32().Inputs(0U, 2U, 28U);
3122 }
3123 BASIC_BLOCK(6U, 7U, 5U)
3124 {
3125 INST(42U, Opcode::Mul).s32().Inputs(27U, 1U);
3126 INST(38U, Opcode::StoreArray).s32().Inputs(0U, 2U, 42U);
3127 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3128 }
3129 BASIC_BLOCK(7U, -1L)
3130 {
3131 INST(23U, Opcode::Return).s32().Inputs(2U);
3132 }
3133 }
3134 }
3135
OUT_GRAPH(ShadowedStoresInLoop,Graph * graph)3136 OUT_GRAPH(ShadowedStoresInLoop, Graph *graph)
3137 {
3138 GRAPH(graph)
3139 {
3140 PARAMETER(0U, 0U).ref();
3141 PARAMETER(1U, 1U).s32();
3142 PARAMETER(2U, 2U).s32();
3143 CONSTANT(8U, 0x8U).s64();
3144 BASIC_BLOCK(2U, 3U) {}
3145 BASIC_BLOCK(3U, 4U, 3U)
3146 {
3147 INST(7U, Opcode::Phi).s32().Inputs({{2U, 1U}, {3U, 21U}});
3148 INST(21U, Opcode::Add).s32().Inputs(7U, 1U);
3149 INST(17U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
3150 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 8U);
3151 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3152 }
3153 BASIC_BLOCK(4U, 5U, 4U)
3154 {
3155 INST(27U, Opcode::Phi).s32().Inputs({{3U, 1U}, {4U, 21U}});
3156 INST(41U, Opcode::Mul).s32().Inputs(27U, 1U);
3157 INST(37U, Opcode::StoreArray).s32().Inputs(0U, 2U, 41U);
3158 INST(30U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3159 }
3160 BASIC_BLOCK(5U, 6U)
3161 {
3162 INST(28U, Opcode::Phi).s32().Inputs({{4U, 1U}, {6U, 41U}});
3163 }
3164 BASIC_BLOCK(6U, 7U, 5U)
3165 {
3166 INST(42U, Opcode::Mul).s32().Inputs(27U, 1U);
3167 INST(38U, Opcode::StoreArray).s32().Inputs(0U, 2U, 42U);
3168 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3169 }
3170 BASIC_BLOCK(7U, -1L)
3171 {
3172 INST(23U, Opcode::Return).s32().Inputs(2U);
3173 }
3174 }
3175 }
3176
TEST_F(LSETest,ShadowedStoresInLoop)3177 TEST_F(LSETest, ShadowedStoresInLoop)
3178 {
3179 src_graph::ShadowedStoresInLoop::CREATE(GetGraph());
3180 Graph *graphLsed = CreateEmptyGraph();
3181 out_graph::ShadowedStoresInLoop::CREATE(graphLsed);
3182 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
3183 GraphChecker(GetGraph()).Check();
3184 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
3185 }
3186
3187 /// Store that can be read is not removed
TEST_F(LSETest,DontRemoveShadowedStoreIfRead)3188 TEST_F(LSETest, DontRemoveShadowedStoreIfRead)
3189 {
3190 GRAPH(GetGraph())
3191 {
3192 PARAMETER(0U, 0U).ref();
3193 PARAMETER(1U, 1U).s32();
3194 PARAMETER(2U, 2U).s32();
3195 PARAMETER(3U, 3U).ref();
3196 BASIC_BLOCK(2U, -1L)
3197 {
3198 INST(7U, Opcode::StoreArray).u32().Inputs(0U, 2U, 1U);
3199 INST(8U, Opcode::NullCheck).ref().Inputs(3U);
3200 INST(10U, Opcode::Add).s32().Inputs(1U, 1U);
3201 INST(11U, Opcode::StoreArray).u32().Inputs(0U, 2U, 10U);
3202 INST(13U, Opcode::ReturnVoid).v0id();
3203 }
3204 }
3205 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3206 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3207 GraphChecker(GetGraph()).Check();
3208 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3209 }
3210
3211 /// Check that shadows store search correctly handles irreducible loops
TEST_F(LSETest,ShadowStoreWithIrreducibleLoop)3212 TEST_F(LSETest, ShadowStoreWithIrreducibleLoop)
3213 {
3214 GRAPH(GetGraph())
3215 {
3216 PARAMETER(0U, 0U).s32();
3217 PARAMETER(1U, 1U).s32();
3218 PARAMETER(2U, 2U).s32();
3219 PARAMETER(3U, 3U).s32();
3220 PARAMETER(4U, 4U).ref();
3221 CONSTANT(5U, 0x2aU).s64();
3222 BASIC_BLOCK(2U, 3U, 4U)
3223 {
3224 INST(7U, Opcode::StoreArray).s32().Inputs(4U, 2U, 1U);
3225 INST(8U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0U).Inputs(0U);
3226 }
3227 BASIC_BLOCK(4U, 5U, 7U)
3228 {
3229 INST(10U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0U).Inputs(1U);
3230 }
3231 BASIC_BLOCK(5U, 6U, 9U)
3232 {
3233 INST(20U, Opcode::Phi).s32().Inputs({{4U, 5U}, {7U, 11U}});
3234 INST(26U, Opcode::Mul).s32().Inputs(20U, 5U);
3235 INST(28U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0U).Inputs(2U);
3236 }
3237 BASIC_BLOCK(6U, 7U)
3238 {
3239 INST(30U, Opcode::SaveState).Inputs(4U).SrcVregs({0U});
3240 }
3241 BASIC_BLOCK(7U, 5U, 9U)
3242 {
3243 INST(11U, Opcode::Phi).s32().Inputs({{4U, 5U}, {6U, 26U}});
3244 INST(19U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0U).Inputs(3U);
3245 }
3246 BASIC_BLOCK(3U, 9U)
3247 {
3248 INST(12U, Opcode::StoreArray).s32().Inputs(4U, 2U, 3U);
3249 }
3250 BASIC_BLOCK(9U, -1L)
3251 {
3252 INST(34U, Opcode::Phi).s32().Inputs({{3U, 1U}, {5U, 2U}, {7U, 3U}});
3253 INST(35U, Opcode::Return).s32().Inputs(34U);
3254 }
3255 }
3256 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3257 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3258 GraphChecker(GetGraph()).Check();
3259 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3260 }
3261
3262 /// Do not eliminate loads over runtime calls due to GC relocations
TEST_F(LSETest,LoadsWithRuntimeCalls)3263 TEST_F(LSETest, LoadsWithRuntimeCalls)
3264 {
3265 GRAPH(GetGraph())
3266 {
3267 PARAMETER(0U, 0U).ref();
3268 BASIC_BLOCK(2U, -1L)
3269 {
3270 INST(3U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
3271 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 3U).TypeId(122U);
3272
3273 INST(13U, Opcode::SaveState).Inputs(0U, 3U).SrcVregs({0U, 1U});
3274 INST(14U, Opcode::LoadAndInitClass).ref().Inputs(13U);
3275 INST(15U, Opcode::StoreStatic).ref().Inputs(14U, 3U);
3276
3277 // Eliminable because of v6 but v6 can be relocated by GC
3278 INST(8U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
3279 // Eliminable because of v3 but v3 can be relocated by GC
3280 INST(9U, Opcode::LoadObject).ref().Inputs(0U).TypeId(100U);
3281 INST(10U, Opcode::SaveState).Inputs(8U).SrcVregs({0U});
3282 INST(11U, Opcode::NullCheck).ref().Inputs(9U, 10U);
3283 INST(12U, Opcode::Return).ref().Inputs(8U);
3284 }
3285 }
3286 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3287 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3288 GraphChecker(GetGraph()).Check();
3289 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3290 }
3291
3292 /// Do not eliminate through static constructors
TEST_F(LSETest,OverClassInitialization)3293 TEST_F(LSETest, OverClassInitialization)
3294 {
3295 GRAPH(GetGraph())
3296 {
3297 PARAMETER(0U, 0U).ref();
3298 BASIC_BLOCK(2U, -1L)
3299 {
3300 INST(5U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3301 INST(6U, Opcode::LoadAndInitClass).ref().Inputs(5U);
3302 INST(7U, Opcode::StoreStatic).ref().Inputs(6U, 0U).TypeId(42U);
3303
3304 INST(9U, Opcode::InitClass).Inputs(5U).TypeId(200U);
3305
3306 INST(11U, Opcode::LoadStatic).ref().Inputs(6U).TypeId(42U);
3307 INST(21U, Opcode::Return).ref().Inputs(11U);
3308 }
3309 }
3310 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3311 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3312 GraphChecker(GetGraph()).Check();
3313 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3314 }
3315
3316 /// Don't hoist from irreducible loop
TEST_F(LSETest,DontHoistWithIrreducibleLoop)3317 TEST_F(LSETest, DontHoistWithIrreducibleLoop)
3318 {
3319 GRAPH(GetGraph())
3320 {
3321 PARAMETER(0U, 0U).s32();
3322 PARAMETER(1U, 1U).s32();
3323 PARAMETER(2U, 2U).s32();
3324 PARAMETER(3U, 3U).s32();
3325 PARAMETER(4U, 4U).ref();
3326 CONSTANT(5U, 0x2aU).s64();
3327 BASIC_BLOCK(2U, 3U, 4U)
3328 {
3329 INST(7U, Opcode::StoreArray).s32().Inputs(4U, 2U, 1U);
3330 INST(8U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0U).Inputs(0U);
3331 }
3332 BASIC_BLOCK(4U, 5U, 7U)
3333 {
3334 INST(10U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0U).Inputs(1U);
3335 }
3336 BASIC_BLOCK(5U, 6U, 9U)
3337 {
3338 INST(20U, Opcode::Phi).s32().Inputs({{4U, 5U}, {7U, 11U}});
3339 INST(21U, Opcode::LoadArray).s32().Inputs(4U, 2U);
3340 INST(26U, Opcode::Mul).s32().Inputs(20U, 21U);
3341 INST(28U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0U).Inputs(2U);
3342 }
3343 BASIC_BLOCK(6U, 7U)
3344 {
3345 INST(30U, Opcode::SaveState).Inputs(4U).SrcVregs({0U});
3346 }
3347 BASIC_BLOCK(7U, 5U, 9U)
3348 {
3349 INST(11U, Opcode::Phi).s32().Inputs({{4U, 5U}, {6U, 26U}});
3350 INST(19U, Opcode::IfImm).SrcType(DataType::INT32).CC(CC_EQ).Imm(0U).Inputs(3U);
3351 }
3352 BASIC_BLOCK(3U, 9U)
3353 {
3354 INST(12U, Opcode::StoreArray).s32().Inputs(4U, 2U, 3U);
3355 }
3356 BASIC_BLOCK(9U, -1L)
3357 {
3358 INST(34U, Opcode::Phi).s32().Inputs({{3U, 1U}, {5U, 2U}, {7U, 3U}});
3359 INST(35U, Opcode::Return).s32().Inputs(34U);
3360 }
3361 }
3362 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3363 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3364 GraphChecker(GetGraph()).Check();
3365 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3366 }
3367
3368 /// Don't hoist values not alive on backedge
TEST_F(LSETest,DontHoistIfNotAlive)3369 TEST_F(LSETest, DontHoistIfNotAlive)
3370 {
3371 GRAPH(GetGraph())
3372 {
3373 PARAMETER(0U, 0U).s32();
3374 CONSTANT(1U, 0x2U).s64();
3375 CONSTANT(2U, 0x1U).s64();
3376 CONSTANT(6U, 0x10U).s64();
3377 BASIC_BLOCK(2U, 3U)
3378 {
3379 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3380 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3381 }
3382 BASIC_BLOCK(3U, 4U, 5U)
3383 {
3384 INST(45U, Opcode::Phi).s64().Inputs({{2U, 1U}, {6U, 35U}});
3385 INST(21U, Opcode::Compare).b().CC(CC_LT).Inputs(45U, 6U);
3386 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3387 }
3388 BASIC_BLOCK(4U, 6U)
3389 {
3390 INST(25U, Opcode::Add).s64().Inputs(45U, 45U);
3391 INST(26U, Opcode::StoreStatic).s64().Inputs(30U, 25U).TypeId(83U);
3392 }
3393 BASIC_BLOCK(5U, 6U)
3394 {
3395 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3396 INST(17U, Opcode::Mul).s64().Inputs(16U, 45U);
3397 }
3398 BASIC_BLOCK(6U, 3U, 7U)
3399 {
3400 INST(35U, Opcode::Phi).s64().Inputs({{4U, 25U}, {5U, 17U}});
3401 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(35U, 2U);
3402 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3403 }
3404 BASIC_BLOCK(7U, -1L)
3405 {
3406 INST(46U, Opcode::Return).s32().Inputs(45U);
3407 }
3408 }
3409 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3410 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3411 GraphChecker(GetGraph()).Check();
3412 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3413 }
3414
3415 /// Don't hoist values not alive on backedge
TEST_F(LSETest,DontHoistIfNotAliveTriangle)3416 TEST_F(LSETest, DontHoistIfNotAliveTriangle)
3417 {
3418 GRAPH(GetGraph())
3419 {
3420 PARAMETER(0U, 0U).s32();
3421 CONSTANT(1U, 0x2U).s64();
3422 CONSTANT(2U, 0x1U).s64();
3423 CONSTANT(6U, 0x10U).s64();
3424 BASIC_BLOCK(2U, 3U)
3425 {
3426 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3427 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3428 }
3429 BASIC_BLOCK(3U, 4U, 5U)
3430 {
3431 INST(25U, Opcode::Phi).s64().Inputs({{2U, 1U}, {5U, 35U}});
3432 INST(21U, Opcode::Compare).b().CC(CC_LT).Inputs(25U, 6U);
3433 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3434 }
3435 BASIC_BLOCK(4U, 5U)
3436 {
3437 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3438 INST(17U, Opcode::Mul).s64().Inputs(16U, 25U);
3439 }
3440 BASIC_BLOCK(5U, 3U, 6U)
3441 {
3442 INST(35U, Opcode::Phi).s64().Inputs({{3U, 25U}, {4U, 17U}});
3443 INST(33U, Opcode::StoreStatic).s64().Inputs(30U, 35U).TypeId(83U);
3444 INST(34U, Opcode::Add).s64().Inputs(35U, 1U);
3445 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(34U, 2U);
3446 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3447 }
3448 BASIC_BLOCK(6U, -1L)
3449 {
3450 INST(46U, Opcode::ReturnVoid).v0id();
3451 }
3452 }
3453 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3454 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3455 GraphChecker(GetGraph()).Check();
3456 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3457 }
3458
3459 /// Double hoist
SRC_GRAPH(HoistInnerLoop,Graph * graph)3460 SRC_GRAPH(HoistInnerLoop, Graph *graph)
3461 {
3462 GRAPH(graph)
3463 {
3464 PARAMETER(0U, 0U).s32();
3465 CONSTANT(1U, 0x2U).s64();
3466 CONSTANT(2U, 0x1U).s64();
3467 CONSTANT(6U, 0x10U).s64();
3468 BASIC_BLOCK(2U, 3U)
3469 {
3470 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3471 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3472 }
3473 BASIC_BLOCK(3U, 4U, 5U)
3474 {
3475 INST(45U, Opcode::Phi).s64().Inputs({{2U, 1U}, {4U, 25U}});
3476 INST(21U, Opcode::Compare).b().CC(CC_LT).Inputs(45U, 6U);
3477 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3478 }
3479 BASIC_BLOCK(4U, 4U, 3U)
3480 {
3481 INST(35U, Opcode::Phi).s64().Inputs({{3U, 45U}, {4U, 25U}});
3482 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3483 INST(25U, Opcode::Add).s64().Inputs(45U, 16U);
3484 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(16U, 2U);
3485 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3486 }
3487 BASIC_BLOCK(5U, -1L)
3488 {
3489 INST(46U, Opcode::Return).s32().Inputs(45U);
3490 }
3491 }
3492 }
3493
OUT_GRAPH(HoistInnerLoop,Graph * graph)3494 OUT_GRAPH(HoistInnerLoop, Graph *graph)
3495 {
3496 GRAPH(graph)
3497 {
3498 PARAMETER(0U, 0U).s32();
3499 CONSTANT(1U, 0x2U).s64();
3500 CONSTANT(2U, 0x1U).s64();
3501 CONSTANT(6U, 0x10U).s64();
3502 BASIC_BLOCK(2U, 3U)
3503 {
3504 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3505 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3506 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3507 }
3508 BASIC_BLOCK(3U, 4U, 5U)
3509 {
3510 INST(45U, Opcode::Phi).s64().Inputs({{2U, 1U}, {4U, 25U}});
3511 INST(21U, Opcode::Compare).b().CC(CC_LT).Inputs(45U, 6U);
3512 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3513 }
3514 BASIC_BLOCK(4U, 4U, 3U)
3515 {
3516 INST(35U, Opcode::Phi).s64().Inputs({{3U, 45U}, {4U, 25U}});
3517 INST(25U, Opcode::Add).s64().Inputs(45U, 16U);
3518 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(16U, 2U);
3519 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3520 }
3521 BASIC_BLOCK(5U, -1L)
3522 {
3523 INST(46U, Opcode::Return).s32().Inputs(45U);
3524 }
3525 }
3526 }
3527
TEST_F(LSETest,HoistInnerLoop)3528 TEST_F(LSETest, HoistInnerLoop)
3529 {
3530 src_graph::HoistInnerLoop::CREATE(GetGraph());
3531 Graph *graphLsed = CreateEmptyGraph();
3532 out_graph::HoistInnerLoop::CREATE(graphLsed);
3533 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
3534 GraphChecker(GetGraph()).Check();
3535 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
3536 }
3537
3538 /// Single hoist
SRC_GRAPH(HoistInnerLoop2,Graph * graph)3539 SRC_GRAPH(HoistInnerLoop2, Graph *graph)
3540 {
3541 GRAPH(graph)
3542 {
3543 PARAMETER(0U, 0U).s32();
3544 CONSTANT(1U, 0x2U).s64();
3545 CONSTANT(2U, 0x1U).s64();
3546 CONSTANT(6U, 0x10U).s64();
3547 BASIC_BLOCK(2U, 3U)
3548 {
3549 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3550 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3551 }
3552 BASIC_BLOCK(3U, 4U, 6U)
3553 {
3554 INST(45U, Opcode::Phi).s64().Inputs({{2U, 1U}, {5U, 25U}});
3555 INST(21U, Opcode::Compare).b().CC(CC_LT).Inputs(45U, 6U);
3556 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3557 }
3558 BASIC_BLOCK(4U, 4U, 5U)
3559 {
3560 INST(35U, Opcode::Phi).s64().Inputs({{3U, 45U}, {4U, 25U}});
3561 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3562 INST(25U, Opcode::Add).s64().Inputs(45U, 16U);
3563 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(16U, 2U);
3564 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3565 }
3566 BASIC_BLOCK(5U, 3U)
3567 {
3568 INST(17U, Opcode::StoreStatic).s64().Inputs(30U, 25U).TypeId(83U);
3569 }
3570 BASIC_BLOCK(6U, -1L)
3571 {
3572 INST(46U, Opcode::Return).s32().Inputs(45U);
3573 }
3574 }
3575 }
3576
OUT_GRAPH(HoistInnerLoop2,Graph * graph)3577 OUT_GRAPH(HoistInnerLoop2, Graph *graph)
3578 {
3579 GRAPH(graph)
3580 {
3581 PARAMETER(0U, 0U).s32();
3582 CONSTANT(1U, 0x2U).s64();
3583 CONSTANT(2U, 0x1U).s64();
3584 CONSTANT(6U, 0x10U).s64();
3585 BASIC_BLOCK(2U, 3U)
3586 {
3587 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3588 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3589 }
3590 BASIC_BLOCK(3U, 4U, 6U)
3591 {
3592 INST(45U, Opcode::Phi).s64().Inputs({{2U, 1U}, {5U, 25U}});
3593 INST(21U, Opcode::Compare).b().CC(CC_LT).Inputs(45U, 6U);
3594 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3595 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3596 }
3597 BASIC_BLOCK(4U, 4U, 5U)
3598 {
3599 INST(35U, Opcode::Phi).s64().Inputs({{3U, 45U}, {4U, 25U}});
3600 INST(25U, Opcode::Add).s64().Inputs(45U, 16U);
3601 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(16U, 2U);
3602 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3603 }
3604 BASIC_BLOCK(5U, 3U)
3605 {
3606 INST(17U, Opcode::StoreStatic).s64().Inputs(30U, 25U).TypeId(83U);
3607 }
3608 BASIC_BLOCK(6U, -1L)
3609 {
3610 INST(46U, Opcode::Return).s32().Inputs(45U);
3611 }
3612 }
3613 }
3614
TEST_F(LSETest,HoistInnerLoop2)3615 TEST_F(LSETest, HoistInnerLoop2)
3616 {
3617 src_graph::HoistInnerLoop2::CREATE(GetGraph());
3618 Graph *graphLsed = CreateEmptyGraph();
3619 out_graph::HoistInnerLoop2::CREATE(graphLsed);
3620 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
3621 GraphChecker(GetGraph()).Check();
3622 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
3623 }
3624
3625 /// Don't hoist due to inner store
TEST_F(LSETest,DontHoistOuterLoop)3626 TEST_F(LSETest, DontHoistOuterLoop)
3627 {
3628 GRAPH(GetGraph())
3629 {
3630 PARAMETER(0U, 0U).s32();
3631 CONSTANT(1U, 0x2U).s64();
3632 CONSTANT(2U, 0x1U).s64();
3633 CONSTANT(6U, 0x10U).s64();
3634 BASIC_BLOCK(2U, 3U)
3635 {
3636 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3637 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3638 }
3639 BASIC_BLOCK(3U, 4U, 6U)
3640 {
3641 INST(45U, Opcode::Phi).s64().Inputs({{2U, 1U}, {4U, 25U}});
3642 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3643 INST(21U, Opcode::Compare).b().CC(CC_LT).Inputs(45U, 6U);
3644 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3645 }
3646 BASIC_BLOCK(4U, 4U, 3U)
3647 {
3648 INST(35U, Opcode::Phi).s64().Inputs({{3U, 45U}, {4U, 25U}});
3649 INST(25U, Opcode::Add).s64().Inputs(45U, 16U);
3650 INST(17U, Opcode::StoreStatic).s64().Inputs(30U, 25U).TypeId(83U);
3651 INST(31U, Opcode::Compare).b().CC(CC_GE).Inputs(16U, 2U);
3652 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3653 }
3654 BASIC_BLOCK(6U, -1L)
3655 {
3656 INST(46U, Opcode::Return).s32().Inputs(45U);
3657 }
3658 }
3659 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3660 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3661 GraphChecker(GetGraph()).Check();
3662 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3663 }
3664
3665 /// Don't hoist from OSR loop
TEST_F(LSETest,DontHoistFromOsrLoop)3666 TEST_F(LSETest, DontHoistFromOsrLoop)
3667 {
3668 GetGraph()->SetMode(GraphMode::Osr());
3669 GRAPH(GetGraph())
3670 {
3671 PARAMETER(0U, 0U).ref();
3672 PARAMETER(1U, 1U).ref();
3673 PARAMETER(2U, 2U).s32();
3674 BASIC_BLOCK(2U, 3U)
3675 {
3676 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
3677 INST(11U, Opcode::StoreObject).s32().Inputs(0U, 2U).TypeId(123U);
3678 INST(12U, Opcode::LoadObject).s32().Inputs(0U).TypeId(124U);
3679 INST(13U, Opcode::LoadObject).s32().Inputs(0U).TypeId(125U);
3680 }
3681 BASIC_BLOCK(3U, 3U, 4U)
3682 {
3683 INST(7U, Opcode::SaveStateOsr).Inputs(0U, 1U).SrcVregs({0U, 1U});
3684 INST(8U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U); // store-load pair
3685 INST(14U, Opcode::StoreObject).s32().Inputs(0U, 2U).TypeId(123U); // store-store pair
3686 INST(15U, Opcode::LoadObject).s32().Inputs(0U).TypeId(124U); // load-load pair
3687 INST(9U, Opcode::IfImm).SrcType(DataType::REFERENCE).CC(CC_NE).Imm(0U).Inputs(8U);
3688 }
3689 BASIC_BLOCK(4U, -1L)
3690 {
3691 INST(16U, Opcode::LoadObject).s32().Inputs(0U).TypeId(125U); // load-load pair, before and after OSR loop
3692 INST(10U, Opcode::Return).s32().Inputs(16U);
3693 }
3694 }
3695
3696 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
3697 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
3698 GraphChecker(GetGraph()).Check();
3699 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
3700 }
3701
SRC_GRAPH(AliveLoadInBackedge,Graph * graph)3702 SRC_GRAPH(AliveLoadInBackedge, Graph *graph)
3703 {
3704 GRAPH(graph)
3705 {
3706 PARAMETER(0U, 0U).s32();
3707 CONSTANT(1U, 0x2U).s64();
3708 CONSTANT(2U, 0x0U).s64();
3709 CONSTANT(6U, 0x1U).s64();
3710 BASIC_BLOCK(2U, 3U)
3711 {
3712 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3713 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3714 INST(5U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3715 }
3716 BASIC_BLOCK(3U, 4U, 5U)
3717 {
3718 INST(15U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3719 INST(21U, Opcode::Compare).b().CC(CC_EQ).Inputs(15U, 2U);
3720 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3721 }
3722 BASIC_BLOCK(4U, 6U)
3723 {
3724 INST(24U, Opcode::Add).s64().Inputs(15U, 1U);
3725 }
3726 BASIC_BLOCK(5U, 6U)
3727 {
3728 INST(23U, Opcode::Mul).s64().Inputs(15U, 15U);
3729 INST(7U, Opcode::StoreStatic).s64().Inputs(30U, 23U).TypeId(83U);
3730 }
3731 BASIC_BLOCK(6U, 7U, 3U)
3732 {
3733 INST(45U, Opcode::Phi).s64().Inputs({{4U, 24U}, {5U, 23U}});
3734 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3735 INST(31U, Opcode::Compare).b().CC(CC_EQ).Inputs(16U, 6U);
3736 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3737 }
3738 BASIC_BLOCK(7U, -1L)
3739 {
3740 INST(46U, Opcode::Return).s32().Inputs(45U);
3741 }
3742 }
3743 }
3744
OUT_GRAPH(AliveLoadInBackedge,Graph * graph)3745 OUT_GRAPH(AliveLoadInBackedge, Graph *graph)
3746 {
3747 GRAPH(graph)
3748 {
3749 PARAMETER(0U, 0U).s32();
3750 CONSTANT(1U, 0x2U).s64();
3751 CONSTANT(2U, 0x0U).s64();
3752 CONSTANT(6U, 0x1U).s64();
3753 BASIC_BLOCK(2U, 3U)
3754 {
3755 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3756 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3757 INST(5U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3758 }
3759 BASIC_BLOCK(3U, 4U, 5U)
3760 {
3761 INST(15U, Opcode::Phi).s64().Inputs({{2U, 5U}, {6U, 16U}});
3762 INST(21U, Opcode::Compare).b().CC(CC_EQ).Inputs(15U, 2U);
3763 INST(22U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(21U);
3764 }
3765 BASIC_BLOCK(4U, 6U)
3766 {
3767 INST(24U, Opcode::Add).s64().Inputs(15U, 1U);
3768 }
3769 BASIC_BLOCK(5U, 6U)
3770 {
3771 INST(23U, Opcode::Mul).s64().Inputs(15U, 15U);
3772 INST(7U, Opcode::StoreStatic).s64().Inputs(30U, 23U).TypeId(83U);
3773 }
3774 BASIC_BLOCK(6U, 7U, 3U)
3775 {
3776 INST(45U, Opcode::Phi).s64().Inputs({{4U, 24U}, {5U, 23U}});
3777 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3778 INST(31U, Opcode::Compare).b().CC(CC_EQ).Inputs(16U, 6U);
3779 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3780 }
3781 BASIC_BLOCK(7U, -1L)
3782 {
3783 INST(46U, Opcode::Return).s32().Inputs(45U);
3784 }
3785 }
3786 }
3787
TEST_F(LSETest,AliveLoadInBackedge)3788 TEST_F(LSETest, AliveLoadInBackedge)
3789 {
3790 src_graph::AliveLoadInBackedge::CREATE(GetGraph());
3791 Graph *graphLsed = CreateEmptyGraph();
3792 out_graph::AliveLoadInBackedge::CREATE(graphLsed);
3793 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
3794 GraphChecker(GetGraph()).Check();
3795 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
3796 }
3797
SRC_GRAPH(AliveLoadInBackedgeInnerLoop,Graph * graph)3798 SRC_GRAPH(AliveLoadInBackedgeInnerLoop, Graph *graph)
3799 {
3800 GRAPH(graph)
3801 {
3802 PARAMETER(0U, 0U).s32();
3803 CONSTANT(1U, 0x2U).s64();
3804 CONSTANT(2U, 0x1U).s64();
3805 CONSTANT(6U, 0x10U).s64();
3806 BASIC_BLOCK(2U, 3U)
3807 {
3808 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3809 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3810 INST(5U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3811 }
3812 BASIC_BLOCK(3U, 4U)
3813 {
3814 INST(15U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3815 INST(24U, Opcode::Add).s64().Inputs(15U, 1U);
3816 INST(7U, Opcode::StoreStatic).s64().Inputs(30U, 24U).TypeId(83U);
3817 }
3818 BASIC_BLOCK(4U, 4U, 5U)
3819 {
3820 INST(45U, Opcode::Phi).s64().Inputs({{3U, 1U}, {4U, 25U}});
3821 INST(25U, Opcode::Mul).s64().Inputs(45U, 45U);
3822 INST(31U, Opcode::Compare).b().CC(CC_EQ).Inputs(25U, 6U);
3823 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3824 }
3825 BASIC_BLOCK(5U, 3U, 6U)
3826 {
3827 INST(16U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3828 INST(27U, Opcode::Compare).b().CC(CC_EQ).Inputs(16U, 2U);
3829 INST(28U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(27U);
3830 }
3831 BASIC_BLOCK(6U, -1L)
3832 {
3833 INST(46U, Opcode::Return).s32().Inputs(45U);
3834 }
3835 }
3836 }
3837
OUT_GRAPH(AliveLoadInBackedgeInnerLoop,Graph * graph)3838 OUT_GRAPH(AliveLoadInBackedgeInnerLoop, Graph *graph)
3839 {
3840 GRAPH(graph)
3841 {
3842 PARAMETER(0U, 0U).s32();
3843 CONSTANT(1U, 0x2U).s64();
3844 CONSTANT(2U, 0x1U).s64();
3845 CONSTANT(6U, 0x10U).s64();
3846 BASIC_BLOCK(2U, 3U)
3847 {
3848 INST(40U, Opcode::SaveState).Inputs(0U).SrcVregs({0U});
3849 INST(30U, Opcode::LoadAndInitClass).ref().Inputs(40U).TypeId(0U);
3850 INST(5U, Opcode::LoadStatic).s64().Inputs(30U).TypeId(83U);
3851 }
3852 BASIC_BLOCK(3U, 4U)
3853 {
3854 INST(55U, Opcode::Phi).s64().Inputs({{2U, 5U}, {5U, 24U}});
3855 INST(24U, Opcode::Add).s64().Inputs(55U, 1U);
3856 INST(7U, Opcode::StoreStatic).s64().Inputs(30U, 24U).TypeId(83U);
3857 }
3858 BASIC_BLOCK(4U, 4U, 5U)
3859 {
3860 INST(45U, Opcode::Phi).s64().Inputs({{3U, 1U}, {4U, 25U}});
3861 INST(25U, Opcode::Mul).s64().Inputs(45U, 45U);
3862 INST(31U, Opcode::Compare).b().CC(CC_EQ).Inputs(25U, 6U);
3863 INST(32U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(31U);
3864 }
3865 BASIC_BLOCK(5U, 3U, 6U)
3866 {
3867 INST(27U, Opcode::Compare).b().CC(CC_EQ).Inputs(24U, 2U);
3868 INST(28U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0x0U).Inputs(27U);
3869 }
3870 BASIC_BLOCK(6U, -1L)
3871 {
3872 INST(46U, Opcode::Return).s32().Inputs(45U);
3873 }
3874 }
3875 }
3876
TEST_F(LSETest,AliveLoadInBackedgeInnerLoop)3877 TEST_F(LSETest, AliveLoadInBackedgeInnerLoop)
3878 {
3879 src_graph::AliveLoadInBackedgeInnerLoop::CREATE(GetGraph());
3880 Graph *graphLsed = CreateEmptyGraph();
3881 out_graph::AliveLoadInBackedgeInnerLoop::CREATE(graphLsed);
3882 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
3883 GraphChecker(GetGraph()).Check();
3884 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
3885 }
3886
3887 /// Do not eliminate loads over runtime calls due to GC relocations
SRC_GRAPH(PhiOverSaveStates,Graph * graph)3888 SRC_GRAPH(PhiOverSaveStates, Graph *graph)
3889 {
3890 GRAPH(graph)
3891 {
3892 PARAMETER(0U, 0U).ref();
3893 PARAMETER(1U, 1U).ref();
3894 PARAMETER(2U, 2U).ref();
3895 BASIC_BLOCK(2U, 3U)
3896 {
3897 INST(4U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
3898 }
3899 BASIC_BLOCK(3U, 3U, 4U)
3900 {
3901 INST(6U, Opcode::SafePoint).Inputs(0U, 1U, 2U).SrcVregs({0U, 1U, 2U});
3902 INST(7U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U);
3903 INST(8U, Opcode::SaveState).Inputs(0U, 2U, 7U).SrcVregs({0U, 2U, 3U});
3904
3905 INST(9U, Opcode::LoadObject).ref().Inputs(7U).TypeId(100U);
3906
3907 INST(10U, Opcode::SaveState).Inputs(0U, 2U, 9U).SrcVregs({0U, 2U, 3U});
3908 INST(15U, Opcode::LoadObject).s64().Inputs(9U).TypeId(133U);
3909 INST(11U, Opcode::StoreObject).ref().Inputs(0U, 9U).TypeId(122U);
3910 INST(12U, Opcode::IfImm).SrcType(DataType::INT64).CC(CC_NE).Imm(0x0U).Inputs(15U);
3911 }
3912 BASIC_BLOCK(4U, -1L)
3913 {
3914 INST(23U, Opcode::ReturnVoid).v0id();
3915 }
3916 }
3917 }
3918
OUT_GRAPH(PhiOverSaveStates,Graph * graph)3919 OUT_GRAPH(PhiOverSaveStates, Graph *graph)
3920 {
3921 GRAPH(graph)
3922 {
3923 PARAMETER(0U, 0U).ref();
3924 PARAMETER(1U, 1U).ref();
3925 PARAMETER(2U, 2U).ref();
3926 BASIC_BLOCK(2U, 3U)
3927 {
3928 INST(4U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
3929 }
3930 BASIC_BLOCK(3U, 3U, 4U)
3931 {
3932 INST(25U, Opcode::Phi).ref().Inputs(1U, 9U);
3933 INST(6U, Opcode::SafePoint).Inputs(0U, 1U, 2U, 25U).SrcVregs({0U, 1U, 2U, VirtualRegister::BRIDGE});
3934 INST(8U, Opcode::SaveState).Inputs(0U, 2U, 25U).SrcVregs({0U, 2U, 3U});
3935
3936 INST(9U, Opcode::LoadObject).ref().Inputs(25U).TypeId(100U);
3937
3938 INST(10U, Opcode::SaveState).Inputs(0U, 2U, 9U).SrcVregs({0U, 2U, 3U});
3939 INST(15U, Opcode::LoadObject).s64().Inputs(9U).TypeId(133U);
3940 INST(11U, Opcode::StoreObject).ref().Inputs(0U, 9U).TypeId(122U);
3941 INST(12U, Opcode::IfImm).SrcType(DataType::INT64).CC(CC_NE).Imm(0x0U).Inputs(15U);
3942 }
3943 BASIC_BLOCK(4U, -1L)
3944 {
3945 INST(23U, Opcode::ReturnVoid).v0id();
3946 }
3947 }
3948 }
3949
TEST_F(LSETest,PhiOverSaveStates)3950 TEST_F(LSETest, PhiOverSaveStates)
3951 {
3952 src_graph::PhiOverSaveStates::CREATE(GetGraph());
3953
3954 Graph *graphLsed = CreateEmptyGraph();
3955 out_graph::PhiOverSaveStates::CREATE(graphLsed);
3956 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
3957 GraphChecker(GetGraph()).Check();
3958 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
3959 }
3960
3961 /// Simple condition phi
SRC_GRAPH(SimpleConditionPhi,Graph * graph)3962 SRC_GRAPH(SimpleConditionPhi, Graph *graph)
3963 {
3964 GRAPH(graph)
3965 {
3966 PARAMETER(0U, 0U).ref();
3967 PARAMETER(1U, 1U).s32();
3968 PARAMETER(2U, 2U).s32();
3969 CONSTANT(8U, 0x8U).s64();
3970 BASIC_BLOCK(2U, 3U, 4U)
3971 {
3972 INST(5U, Opcode::LoadArray).s32().Inputs(0U, 2U);
3973 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(5U, 8U);
3974 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
3975 }
3976 BASIC_BLOCK(4U, 3U)
3977 {
3978 INST(21U, Opcode::Add).s32().Inputs(5U, 1U);
3979 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
3980 }
3981 BASIC_BLOCK(3U, -1L)
3982 {
3983 INST(22U, Opcode::LoadArray).s32().Inputs(0U, 2U);
3984 INST(23U, Opcode::Return).s32().Inputs(22U);
3985 }
3986 }
3987 }
3988
OUT_GRAPH(SimpleConditionPhi,Graph * graph)3989 OUT_GRAPH(SimpleConditionPhi, Graph *graph)
3990 {
3991 GRAPH(graph)
3992 {
3993 PARAMETER(0U, 0U).ref();
3994 PARAMETER(1U, 1U).s32();
3995 PARAMETER(2U, 2U).s32();
3996 CONSTANT(8U, 0x8U).s64();
3997 BASIC_BLOCK(2U, 3U, 4U)
3998 {
3999 INST(5U, Opcode::LoadArray).s32().Inputs(0U, 2U);
4000 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(5U, 8U);
4001 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
4002 }
4003 BASIC_BLOCK(3U, 4U)
4004 {
4005 INST(21U, Opcode::Add).s32().Inputs(5U, 1U);
4006 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
4007 }
4008 BASIC_BLOCK(4U, -1L)
4009 {
4010 INST(25U, Opcode::Phi).s32().Inputs({{2U, 5U}, {3U, 21U}});
4011 INST(23U, Opcode::Return).s32().Inputs(25U);
4012 }
4013 }
4014 }
4015
TEST_F(LSETest,SimpleConditionPhi)4016 TEST_F(LSETest, SimpleConditionPhi)
4017 {
4018 src_graph::SimpleConditionPhi::CREATE(GetGraph());
4019 Graph *graphLsed = CreateEmptyGraph();
4020 out_graph::SimpleConditionPhi::CREATE(graphLsed);
4021 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
4022 GraphChecker(GetGraph()).Check();
4023 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
4024 }
4025
4026 /// Simple condition phi
SRC_GRAPH(SimpleConditionPhi2,Graph * graph)4027 SRC_GRAPH(SimpleConditionPhi2, Graph *graph)
4028 {
4029 GRAPH(graph)
4030 {
4031 PARAMETER(0U, 0U).ref();
4032 PARAMETER(1U, 1U).s32();
4033 PARAMETER(2U, 2U).s32();
4034 PARAMETER(3U, 3U).s32();
4035 CONSTANT(8U, 0x8U).s64();
4036 BASIC_BLOCK(2U, 3U, 4U)
4037 {
4038 INST(5U, Opcode::LoadArray).s32().Inputs(0U, 2U);
4039 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(5U, 8U);
4040 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
4041 }
4042 BASIC_BLOCK(3U, 5U)
4043 {
4044 INST(21U, Opcode::Add).s32().Inputs(5U, 1U);
4045 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 3U, 21U);
4046 }
4047 BASIC_BLOCK(4U, 5U)
4048 {
4049 INST(6U, Opcode::LoadArray).s32().Inputs(0U, 3U);
4050 }
4051 BASIC_BLOCK(5U, -1L)
4052 {
4053 INST(22U, Opcode::LoadArray).s32().Inputs(0U, 3U);
4054 INST(23U, Opcode::Return).s32().Inputs(22U);
4055 }
4056 }
4057 }
4058
OUT_GRAPH(SimpleConditionPhi2,Graph * graph)4059 OUT_GRAPH(SimpleConditionPhi2, Graph *graph)
4060 {
4061 GRAPH(graph)
4062 {
4063 PARAMETER(0U, 0U).ref();
4064 PARAMETER(1U, 1U).s32();
4065 PARAMETER(2U, 2U).s32();
4066 PARAMETER(3U, 3U).s32();
4067 CONSTANT(8U, 0x8U).s64();
4068 BASIC_BLOCK(2U, 3U, 4U)
4069 {
4070 INST(5U, Opcode::LoadArray).s32().Inputs(0U, 2U);
4071 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(5U, 8U);
4072 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
4073 }
4074 BASIC_BLOCK(3U, 5U)
4075 {
4076 INST(21U, Opcode::Add).s32().Inputs(5U, 1U);
4077 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 3U, 21U);
4078 }
4079 BASIC_BLOCK(4U, 5U)
4080 {
4081 INST(6U, Opcode::LoadArray).s32().Inputs(0U, 3U);
4082 }
4083 BASIC_BLOCK(5U, -1L)
4084 {
4085 INST(25U, Opcode::Phi).s32().Inputs({{3U, 21U}, {4U, 6U}});
4086 INST(23U, Opcode::Return).s32().Inputs(25U);
4087 }
4088 }
4089 }
4090
TEST_F(LSETest,SimpleConditionPhi2)4091 TEST_F(LSETest, SimpleConditionPhi2)
4092 {
4093 src_graph::SimpleConditionPhi2::CREATE(GetGraph());
4094 Graph *graphLsed = CreateEmptyGraph();
4095 out_graph::SimpleConditionPhi2::CREATE(graphLsed);
4096 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
4097 GraphChecker(GetGraph()).Check();
4098 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
4099 }
4100
TEST_F(LSETest,SimpleConditionPhiMayAlias)4101 TEST_F(LSETest, SimpleConditionPhiMayAlias)
4102 {
4103 GRAPH(GetGraph())
4104 {
4105 PARAMETER(0U, 0U).ref();
4106 PARAMETER(1U, 1U).s32();
4107 PARAMETER(2U, 2U).s32();
4108 CONSTANT(8U, 0x8U).s64();
4109 BASIC_BLOCK(2U, 3U, 4U)
4110 {
4111 INST(5U, Opcode::LoadArray).s32().Inputs(0U, 2U);
4112 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(5U, 8U);
4113 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
4114 }
4115 BASIC_BLOCK(4U, 3U)
4116 {
4117 INST(21U, Opcode::Add).s32().Inputs(5U, 1U);
4118 INST(7U, Opcode::StoreArray).s32().Inputs(0U, 2U, 21U);
4119 INST(6U, Opcode::StoreArray).s32().Inputs(0U, 1U, 1U);
4120 }
4121 BASIC_BLOCK(3U, -1L)
4122 {
4123 INST(22U, Opcode::LoadArray).s32().Inputs(0U, 2U);
4124 INST(23U, Opcode::Return).s32().Inputs(22U);
4125 }
4126 }
4127 auto initial = GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
4128 ASSERT_FALSE(GetGraph()->RunPass<Lse>());
4129 GraphChecker(GetGraph()).Check();
4130 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), initial));
4131 }
4132
4133 /// Simple condition phi, check bridges
SRC_GRAPH(SimpleConditionPhiWithRefInputs,Graph * graph)4134 SRC_GRAPH(SimpleConditionPhiWithRefInputs, Graph *graph)
4135 {
4136 GRAPH(graph)
4137 {
4138 PARAMETER(0U, 0U).s32();
4139 PARAMETER(1U, 1U).ref();
4140 PARAMETER(2U, 2U).ref();
4141 PARAMETER(3U, 3U).ref();
4142 CONSTANT(4U, 0x4U).s64();
4143 BASIC_BLOCK(2U, 3U, 4U)
4144 {
4145 INST(5U, Opcode::StoreArray).ref().Inputs(1U, 0U, 2U);
4146 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(0U, 4U);
4147 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
4148 }
4149 BASIC_BLOCK(4U, 3U)
4150 {
4151 INST(7U, Opcode::StoreArray).ref().Inputs(1U, 0U, 3U);
4152 INST(8U, Opcode::SafePoint).Inputs(1U).SrcVregs({1U});
4153 }
4154 BASIC_BLOCK(3U, -1L)
4155 {
4156 INST(21U, Opcode::SafePoint).Inputs(1U).SrcVregs({1U});
4157 INST(22U, Opcode::LoadArray).ref().Inputs(1U, 0U);
4158 INST(23U, Opcode::SaveState).Inputs(22U).SrcVregs({22U});
4159 INST(24U, Opcode::CallStatic).v0id().InputsAutoType(22U, 23U);
4160 INST(25U, Opcode::Return).ref().Inputs(22U);
4161 }
4162 }
4163 }
4164
OUT_GRAPH(SimpleConditionPhiWithRefInputs,Graph * graph)4165 OUT_GRAPH(SimpleConditionPhiWithRefInputs, Graph *graph)
4166 {
4167 GRAPH(graph)
4168 {
4169 PARAMETER(0U, 0U).s32();
4170 PARAMETER(1U, 1U).ref();
4171 PARAMETER(2U, 2U).ref();
4172 PARAMETER(3U, 3U).ref();
4173 CONSTANT(4U, 0x4U).s64();
4174 BASIC_BLOCK(2U, 3U, 4U)
4175 {
4176 INST(5U, Opcode::StoreArray).ref().Inputs(1U, 0U, 2U);
4177 INST(9U, Opcode::Compare).b().CC(CC_GT).Inputs(0U, 4U);
4178 INST(10U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(9U);
4179 }
4180 BASIC_BLOCK(4U, 3U)
4181 {
4182 INST(7U, Opcode::StoreArray).ref().Inputs(1U, 0U, 3U);
4183 INST(8U, Opcode::SafePoint).Inputs(1U, 3U).SrcVregs({1U, VirtualRegister::BRIDGE});
4184 }
4185 BASIC_BLOCK(3U, -1L)
4186 {
4187 INST(26U, Opcode::Phi).ref().Inputs({{2U, 2U}, {4U, 3U}});
4188 INST(21U, Opcode::SafePoint).Inputs(1U, 26U).SrcVregs({1U, VirtualRegister::BRIDGE});
4189 INST(23U, Opcode::SaveState).Inputs(26U).SrcVregs({22U});
4190 INST(24U, Opcode::CallStatic).v0id().InputsAutoType(26U, 23U);
4191 INST(25U, Opcode::Return).ref().Inputs(26U);
4192 }
4193 }
4194 }
4195
TEST_F(LSETest,SimpleConditionPhiWithRefInputs)4196 TEST_F(LSETest, SimpleConditionPhiWithRefInputs)
4197 {
4198 src_graph::SimpleConditionPhiWithRefInputs::CREATE(GetGraph());
4199 Graph *graphLsed = CreateEmptyGraph();
4200 out_graph::SimpleConditionPhiWithRefInputs::CREATE(graphLsed);
4201 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
4202 GraphChecker(GetGraph()).Check();
4203 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
4204 }
4205
4206 /// SaveStateDeoptimize does not prevent elimination and does not need bridges
SRC_GRAPH(EliminateOverSaveStateDeoptimize,Graph * graph)4207 SRC_GRAPH(EliminateOverSaveStateDeoptimize, Graph *graph)
4208 {
4209 GRAPH(graph)
4210 {
4211 PARAMETER(0U, 0U).ref();
4212 PARAMETER(1U, 1U).ref();
4213 PARAMETER(2U, 2U).s32();
4214 PARAMETER(3U, 3U).s32();
4215 BASIC_BLOCK(2U, -1L)
4216 {
4217 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
4218 INST(11U, Opcode::StoreObject).s32().Inputs(0U, 2U).TypeId(123U);
4219 INST(12U, Opcode::LoadObject).ref().Inputs(0U).TypeId(124U);
4220
4221 INST(7U, Opcode::SaveStateDeoptimize).Inputs(0U).SrcVregs({0U});
4222 INST(8U, Opcode::LoadObject).ref().Inputs(0U).TypeId(122U); // store-load pair
4223 INST(14U, Opcode::StoreObject).s32().Inputs(0U, 3U).TypeId(123U); // store-store pair
4224 INST(15U, Opcode::LoadObject).ref().Inputs(0U).TypeId(124U); // load-load pair
4225
4226 INST(16U, Opcode::SaveState).Inputs(12U, 8U, 15U).SrcVregs({0U, 1U, 2U});
4227 INST(17U, Opcode::CallStatic).ref().InputsAutoType(12U, 8U, 15U, 16U);
4228
4229 INST(10U, Opcode::Return).ref().Inputs(17U);
4230 }
4231 }
4232 }
4233
OUT_GRAPH(EliminateOverSaveStateDeoptimize,Graph * graph)4234 OUT_GRAPH(EliminateOverSaveStateDeoptimize, Graph *graph)
4235 {
4236 GRAPH(graph)
4237 {
4238 PARAMETER(0U, 0U).ref();
4239 PARAMETER(1U, 1U).ref();
4240 PARAMETER(2U, 2U).s32();
4241 PARAMETER(3U, 3U).s32();
4242 BASIC_BLOCK(2U, -1L)
4243 {
4244 INST(6U, Opcode::StoreObject).ref().Inputs(0U, 1U).TypeId(122U);
4245 INST(12U, Opcode::LoadObject).ref().Inputs(0U).TypeId(124U);
4246
4247 INST(7U, Opcode::SaveStateDeoptimize).Inputs(0U).SrcVregs({0U});
4248 INST(14U, Opcode::StoreObject).s32().Inputs(0U, 3U).TypeId(123U);
4249
4250 INST(16U, Opcode::SaveState).Inputs(12U, 1U, 12U).SrcVregs({0U, 1U, 2U});
4251 INST(17U, Opcode::CallStatic).ref().InputsAutoType(12U, 1U, 12U, 16U);
4252
4253 INST(10U, Opcode::Return).ref().Inputs(17U);
4254 }
4255 }
4256 }
4257
TEST_F(LSETest,EliminateOverSaveStateDeoptimize)4258 TEST_F(LSETest, EliminateOverSaveStateDeoptimize)
4259 {
4260 src_graph::EliminateOverSaveStateDeoptimize::CREATE(GetGraph());
4261
4262 Graph *graphLsed = CreateEmptyGraph();
4263 out_graph::EliminateOverSaveStateDeoptimize::CREATE(graphLsed);
4264
4265 ASSERT_TRUE(GetGraph()->RunPass<Lse>());
4266 GraphChecker(GetGraph()).Check();
4267 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graphLsed));
4268 }
4269
4270 // NOLINTEND(readability-magic-numbers)
4271
4272 } // namespace ark::compiler
4273