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