1/**
2 * Copyright (c) 2021-2022 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/optimizations/vn.h"
18#include "optimizer/optimizations/cleanup.h"
19#include "optimizer/ir/graph_cloner.h"
20
21namespace panda::compiler {
22class VNTest : public AsmTest {
23public:
24    VNTest() : graph_(CreateGraphWithDefaultRuntime()) {}
25
26    Graph *GetGraph() override
27    {
28        return graph_;
29    }
30
31private:
32    Graph *graph_;
33};
34
35TEST_F(VNTest, VnTestApply1)
36{
37    // Remove duplicate arithmetic instructions
38    GRAPH(GetGraph())
39    {
40        PARAMETER(0, 0).u64();
41        PARAMETER(1, 1).u64();
42        PARAMETER(2, 2).f64();
43        PARAMETER(3, 3).f64();
44        PARAMETER(4, 4).f32();
45        PARAMETER(5, 5).f32();
46
47        BASIC_BLOCK(2, -1)
48        {
49            INST(6, Opcode::Add).u64().Inputs(0, 1);
50            INST(7, Opcode::Sub).u32().Inputs(1, 0);
51            INST(8, Opcode::Mul).f32().Inputs(4, 5);
52            INST(9, Opcode::Div).f64().Inputs(3, 2);
53            INST(10, Opcode::Sub).u32().Inputs(1, 0);
54            INST(11, Opcode::Div).f64().Inputs(3, 2);
55            INST(12, Opcode::Mul).f32().Inputs(4, 5);
56            INST(13, Opcode::Add).u64().Inputs(0, 1);
57            INST(20, Opcode::SaveState).NoVregs();
58            INST(14, Opcode::CallStatic).b().InputsAutoType(6, 7, 8, 9, 10, 11, 12, 13, 20);
59            INST(15, Opcode::ReturnVoid);
60        }
61    }
62    Graph *graph_et = CreateGraphWithDefaultRuntime();
63    GRAPH(graph_et)
64    {
65        PARAMETER(0, 0).u64();
66        PARAMETER(1, 1).u64();
67        PARAMETER(2, 2).f64();
68        PARAMETER(3, 3).f64();
69        PARAMETER(4, 4).f32();
70        PARAMETER(5, 5).f32();
71
72        BASIC_BLOCK(2, -1)
73        {
74            INST(6, Opcode::Add).u64().Inputs(0, 1);
75            INST(7, Opcode::Sub).u32().Inputs(1, 0);
76            INST(8, Opcode::Mul).f32().Inputs(4, 5);
77            INST(9, Opcode::Div).f64().Inputs(3, 2);
78            INST(10, Opcode::Sub).u32().Inputs(1, 0);
79            INST(11, Opcode::Div).f64().Inputs(3, 2);
80            INST(12, Opcode::Mul).f32().Inputs(4, 5);
81            INST(13, Opcode::Add).u64().Inputs(0, 1);
82            INST(20, Opcode::SaveState).NoVregs();
83            INST(14, Opcode::CallStatic).b().InputsAutoType(6, 7, 8, 9, 7, 9, 8, 6, 20);
84            INST(15, Opcode::ReturnVoid);
85        }
86    }
87
88    GetGraph()->RunPass<ValNum>();
89    GraphChecker(GetGraph()).Check();
90    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
91}
92
93TEST_F(VNTest, VnTestApply2)
94{
95    // Remove duplicate Cast,  AddI, Fcmp and Cmp instructions
96    GRAPH(GetGraph())
97    {
98        PARAMETER(0, 0).u64();
99        PARAMETER(1, 1).u64();
100        PARAMETER(2, 2).f64();
101        PARAMETER(3, 3).f64();
102        PARAMETER(4, 4).f32();
103        PARAMETER(5, 5).f32();
104
105        BASIC_BLOCK(2, 3, 4)
106        {
107            INST(6, Opcode::Cast).u64().SrcType(DataType::FLOAT64).Inputs(2);
108            INST(7, Opcode::AddI).u32().Imm(10ULL).Inputs(1);
109            INST(8, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT64).Fcmpg(true).Inputs(2, 3);
110            INST(9, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(false).Inputs(4, 5);
111            INST(10, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
112            INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
113        }
114        BASIC_BLOCK(3, -1)
115        {
116            INST(23, Opcode::SaveState).NoVregs();
117            INST(12, Opcode::CallStatic).b().InputsAutoType(6, 7, 8, 9, 23);
118            INST(13, Opcode::ReturnVoid);
119        }
120        BASIC_BLOCK(4, 5, 6)
121        {
122            INST(14, Opcode::Cast).u64().SrcType(DataType::FLOAT64).Inputs(2);
123            INST(15, Opcode::AddI).u32().Imm(10ULL).Inputs(1);
124            INST(16, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT64).Fcmpg(true).Inputs(2, 3);
125            INST(17, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(false).Inputs(4, 5);
126            INST(18, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
127            INST(19, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(18);
128        }
129        BASIC_BLOCK(5, -1)
130        {
131            INST(24, Opcode::SaveState).NoVregs();
132            INST(20, Opcode::CallStatic).b().InputsAutoType(17, 16, 15, 14, 24);
133            INST(21, Opcode::ReturnVoid);
134        }
135        BASIC_BLOCK(6, -1)
136        {
137            INST(22, Opcode::ReturnVoid);
138        }
139    }
140    Graph *graph_et = CreateGraphWithDefaultRuntime();
141    GRAPH(graph_et)
142    {
143        PARAMETER(0, 0).u64();
144        PARAMETER(1, 1).u64();
145        PARAMETER(2, 2).f64();
146        PARAMETER(3, 3).f64();
147        PARAMETER(4, 4).f32();
148        PARAMETER(5, 5).f32();
149
150        BASIC_BLOCK(2, 3, 4)
151        {
152            INST(6, Opcode::Cast).u64().SrcType(DataType::FLOAT64).Inputs(2);
153            INST(7, Opcode::AddI).u32().Imm(10ULL).Inputs(1);
154            INST(8, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT64).Fcmpg(true).Inputs(2, 3);
155            INST(9, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(false).Inputs(4, 5);
156            INST(10, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
157            INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
158        }
159        BASIC_BLOCK(3, -1)
160        {
161            INST(23, Opcode::SaveState).NoVregs();
162            INST(12, Opcode::CallStatic).b().InputsAutoType(6, 7, 8, 9, 23);
163            INST(13, Opcode::ReturnVoid);
164        }
165        BASIC_BLOCK(4, 5, 6)
166        {
167            INST(14, Opcode::Cast).u64().SrcType(DataType::FLOAT64).Inputs(2);
168            INST(15, Opcode::AddI).u32().Imm(10ULL).Inputs(1);
169            INST(16, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT64).Fcmpg(true).Inputs(2, 3);
170            INST(17, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(false).Inputs(4, 5);
171            INST(18, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
172            INST(19, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
173        }
174        BASIC_BLOCK(5, -1)
175        {
176            INST(24, Opcode::SaveState).NoVregs();
177            INST(20, Opcode::CallStatic).b().InputsAutoType(9, 8, 7, 6, 24);
178            INST(21, Opcode::ReturnVoid);
179        }
180        BASIC_BLOCK(6, -1)
181        {
182            INST(22, Opcode::ReturnVoid);
183        }
184    }
185
186    GetGraph()->RunPass<ValNum>();
187    GraphChecker(GetGraph()).Check();
188    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
189}
190
191TEST_F(VNTest, VnTestNotApply1)
192{
193    // Arithmetic instructions has different type, inputs, opcodes
194    GRAPH(GetGraph())
195    {
196        PARAMETER(0, 0).u64();
197        PARAMETER(1, 1).u64();
198        PARAMETER(2, 2).f64();
199        PARAMETER(3, 3).f64();
200        PARAMETER(4, 4).f32();
201        PARAMETER(5, 5).f32();
202
203        BASIC_BLOCK(2, -1)
204        {
205            INST(6, Opcode::Add).u64().Inputs(0, 1);
206            INST(7, Opcode::Add).u16().Inputs(0, 1);
207            INST(8, Opcode::Add).u32().Inputs(0, 7);
208            INST(9, Opcode::Div).f64().Inputs(2, 3);
209            INST(10, Opcode::Div).f64().Inputs(3, 2);
210            INST(11, Opcode::Mul).f64().Inputs(2, 3);
211            INST(12, Opcode::Sub).f32().Inputs(4, 5);
212            INST(13, Opcode::Sub).f32().Inputs(5, 4);
213            INST(14, Opcode::Abs).f32().Inputs(4);
214            INST(15, Opcode::Neg).f32().Inputs(4);
215            INST(20, Opcode::SaveState).NoVregs();
216            INST(16, Opcode::CallStatic).b().InputsAutoType(6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20);
217            INST(17, Opcode::ReturnVoid);
218        }
219    }
220    Graph *graph_et = CreateGraphWithDefaultRuntime();
221    // graph_et is equal the graph
222    GRAPH(graph_et)
223    {
224        PARAMETER(0, 0).u64();
225        PARAMETER(1, 1).u64();
226        PARAMETER(2, 2).f64();
227        PARAMETER(3, 3).f64();
228        PARAMETER(4, 4).f32();
229        PARAMETER(5, 5).f32();
230
231        BASIC_BLOCK(2, -1)
232        {
233            INST(6, Opcode::Add).u64().Inputs(0, 1);
234            INST(7, Opcode::Add).u16().Inputs(0, 1);
235            INST(8, Opcode::Add).u32().Inputs(0, 7);
236            INST(9, Opcode::Div).f64().Inputs(2, 3);
237            INST(10, Opcode::Div).f64().Inputs(3, 2);
238            INST(11, Opcode::Mul).f64().Inputs(2, 3);
239            INST(12, Opcode::Sub).f32().Inputs(4, 5);
240            INST(13, Opcode::Sub).f32().Inputs(5, 4);
241            INST(14, Opcode::Abs).f32().Inputs(4);
242            INST(15, Opcode::Neg).f32().Inputs(4);
243            INST(20, Opcode::SaveState).NoVregs();
244            INST(16, Opcode::CallStatic).b().InputsAutoType(6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20);
245            INST(17, Opcode::ReturnVoid);
246        }
247    }
248
249    GetGraph()->RunPass<ValNum>();
250    GraphChecker(GetGraph()).Check();
251    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
252}
253
254TEST_F(VNTest, VnTestNotApply2)
255{
256    // Can't applies:
257    //  - Cast instructions have different types
258    //  - AddI instructions have different constant
259    //  - Fcmp instructions have different fcmpg flag
260    //  - Cmp instructions have different CC
261    GRAPH(GetGraph())
262    {
263        PARAMETER(0, 0).u64();
264        PARAMETER(1, 1).u64();
265        PARAMETER(2, 2).f64();
266        PARAMETER(3, 3).f64();
267        PARAMETER(4, 4).f32();
268        PARAMETER(5, 5).f32();
269
270        BASIC_BLOCK(2, 3, 4)
271        {
272            INST(6, Opcode::Cast).u32().SrcType(DataType::FLOAT64).Inputs(2);
273            INST(7, Opcode::AddI).u32().Imm(9ULL).Inputs(1);
274            INST(8, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT64).Fcmpg(false).Inputs(2, 3);
275            INST(9, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(true).Inputs(4, 5);
276            INST(10, Opcode::Compare).b().CC(CC_LT).Inputs(0, 1);
277            INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
278        }
279        BASIC_BLOCK(3, -1)
280        {
281            INST(23, Opcode::SaveState).NoVregs();
282            INST(12, Opcode::CallStatic).b().InputsAutoType(6, 7, 8, 9, 23);
283            INST(13, Opcode::ReturnVoid);
284        }
285        BASIC_BLOCK(4, 5, 6)
286        {
287            INST(14, Opcode::Cast).u64().SrcType(DataType::FLOAT64).Inputs(2);
288            INST(15, Opcode::AddI).u32().Imm(10ULL).Inputs(1);
289            INST(16, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT64).Fcmpg(true).Inputs(2, 3);
290            INST(17, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(false).Inputs(4, 5);
291            INST(18, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
292            INST(19, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(18);
293        }
294        BASIC_BLOCK(5, -1)
295        {
296            INST(24, Opcode::SaveState).NoVregs();
297            INST(20, Opcode::CallStatic).b().InputsAutoType(17, 16, 15, 14, 24);
298            INST(21, Opcode::ReturnVoid);
299        }
300        BASIC_BLOCK(6, -1)
301        {
302            INST(22, Opcode::ReturnVoid);
303        }
304    }
305    Graph *graph_et = CreateGraphWithDefaultRuntime();
306    // graph_et is equal the graph
307    GRAPH(graph_et)
308    {
309        PARAMETER(0, 0).u64();
310        PARAMETER(1, 1).u64();
311        PARAMETER(2, 2).f64();
312        PARAMETER(3, 3).f64();
313        PARAMETER(4, 4).f32();
314        PARAMETER(5, 5).f32();
315
316        BASIC_BLOCK(2, 3, 4)
317        {
318            INST(6, Opcode::Cast).u32().SrcType(DataType::FLOAT64).Inputs(2);
319            INST(7, Opcode::AddI).u32().Imm(9ULL).Inputs(1);
320            INST(8, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT64).Fcmpg(false).Inputs(2, 3);
321            INST(9, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(true).Inputs(4, 5);
322            INST(10, Opcode::Compare).b().CC(CC_LT).Inputs(0, 1);
323            INST(11, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(10);
324        }
325        BASIC_BLOCK(3, -1)
326        {
327            INST(23, Opcode::SaveState).NoVregs();
328            INST(12, Opcode::CallStatic).b().InputsAutoType(6, 7, 8, 9, 23);
329            INST(13, Opcode::ReturnVoid);
330        }
331        BASIC_BLOCK(4, 5, 6)
332        {
333            INST(14, Opcode::Cast).u64().SrcType(DataType::FLOAT64).Inputs(2);
334            INST(15, Opcode::AddI).u32().Imm(10ULL).Inputs(1);
335            INST(16, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT64).Fcmpg(true).Inputs(2, 3);
336            INST(17, Opcode::Cmp).s32().SrcType(DataType::Type::FLOAT32).Fcmpg(false).Inputs(4, 5);
337            INST(18, Opcode::Compare).b().CC(CC_EQ).Inputs(0, 1);
338            INST(19, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(18);
339        }
340        BASIC_BLOCK(5, -1)
341        {
342            INST(24, Opcode::SaveState).NoVregs();
343            INST(20, Opcode::CallStatic).b().InputsAutoType(17, 16, 15, 14, 24);
344            INST(21, Opcode::ReturnVoid);
345        }
346        BASIC_BLOCK(6, -1)
347        {
348            INST(22, Opcode::ReturnVoid);
349        }
350    }
351
352    GetGraph()->RunPass<ValNum>();
353    GraphChecker(GetGraph()).Check();
354    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
355}
356
357TEST_F(VNTest, VnTestNotApply3)
358{
359    // Can't applies:
360    //  - Arithmetic instructions aren't dominate
361    //  - CallStatic, LoadArray and StoreArray has NO_CSE
362    GRAPH(GetGraph())
363    {
364        PARAMETER(0, 0).u64();
365        PARAMETER(1, 1).u64();
366        PARAMETER(2, 2).f64();
367        PARAMETER(3, 3).f64();
368        PARAMETER(4, 4).ref();
369        PARAMETER(5, 5).ref();
370        PARAMETER(6, 6).s32();
371
372        BASIC_BLOCK(2, 3, 4)
373        {
374            INST(7, Opcode::LoadArray).u64().Inputs(5, 6);
375            INST(8, Opcode::LoadArray).u64().Inputs(5, 6);
376            INST(9, Opcode::StoreArray).f64().Inputs(4, 6, 3);
377            INST(10, Opcode::StoreArray).f64().Inputs(4, 6, 3);
378            INST(11, Opcode::Compare).b().CC(CC_LT).Inputs(7, 8);
379            INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
380        }
381        BASIC_BLOCK(3, -1)
382        {
383            INST(13, Opcode::Add).u64().Inputs(0, 1);
384            INST(14, Opcode::Sub).u64().Inputs(0, 1);
385            INST(15, Opcode::Mul).f64().Inputs(2, 3);
386            INST(16, Opcode::Div).f64().Inputs(2, 3);
387            INST(30, Opcode::SaveState).NoVregs();
388            INST(17, Opcode::CallStatic).b().InputsAutoType(13, 14, 15, 16, 30);
389            INST(18, Opcode::CallStatic).b().InputsAutoType(13, 14, 15, 16, 30);
390            INST(19, Opcode::ReturnVoid);
391        }
392        BASIC_BLOCK(4, -1)
393        {
394            INST(20, Opcode::Add).u64().Inputs(0, 1);
395            INST(21, Opcode::Sub).u64().Inputs(0, 1);
396            INST(22, Opcode::Mul).f64().Inputs(2, 3);
397            INST(23, Opcode::Div).f64().Inputs(2, 3);
398            INST(31, Opcode::SaveState).NoVregs();
399            INST(24, Opcode::CallStatic).b().InputsAutoType(20, 21, 22, 23, 31);
400            INST(25, Opcode::ReturnVoid);
401        }
402    }
403
404    GetGraph()->RunPass<ValNum>();
405    GraphChecker(GetGraph()).Check();
406    ASSERT_EQ(INS(13).GetVN(), INS(20).GetVN());
407    ASSERT_EQ(INS(14).GetVN(), INS(21).GetVN());
408    ASSERT_EQ(INS(15).GetVN(), INS(22).GetVN());
409    ASSERT_EQ(INS(16).GetVN(), INS(23).GetVN());
410
411    Graph *graph_et = CreateGraphWithDefaultRuntime();
412    // graph_et is equal the graph
413    GRAPH(graph_et)
414    {
415        PARAMETER(0, 0).u64();
416        PARAMETER(1, 1).u64();
417        PARAMETER(2, 2).f64();
418        PARAMETER(3, 3).f64();
419        PARAMETER(4, 4).ref();
420        PARAMETER(5, 5).ref();
421        PARAMETER(6, 6).s32();
422
423        BASIC_BLOCK(2, 3, 4)
424        {
425            INST(7, Opcode::LoadArray).u64().Inputs(5, 6);
426            INST(8, Opcode::LoadArray).u64().Inputs(5, 6);
427            INST(9, Opcode::StoreArray).f64().Inputs(4, 6, 3);
428            INST(10, Opcode::StoreArray).f64().Inputs(4, 6, 3);
429            INST(11, Opcode::Compare).b().CC(CC_LT).Inputs(7, 8);
430            INST(12, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(11);
431        }
432        BASIC_BLOCK(3, -1)
433        {
434            INST(13, Opcode::Add).u64().Inputs(0, 1);
435            INST(14, Opcode::Sub).u64().Inputs(0, 1);
436            INST(15, Opcode::Mul).f64().Inputs(2, 3);
437            INST(16, Opcode::Div).f64().Inputs(2, 3);
438            INST(30, Opcode::SaveState).NoVregs();
439            INST(17, Opcode::CallStatic).b().InputsAutoType(13, 14, 15, 16, 30);
440            INST(18, Opcode::CallStatic).b().InputsAutoType(13, 14, 15, 16, 30);
441            INST(19, Opcode::ReturnVoid);
442        }
443        BASIC_BLOCK(4, -1)
444        {
445            INST(20, Opcode::Add).u64().Inputs(0, 1);
446            INST(21, Opcode::Sub).u64().Inputs(0, 1);
447            INST(22, Opcode::Mul).f64().Inputs(2, 3);
448            INST(23, Opcode::Div).f64().Inputs(2, 3);
449            INST(31, Opcode::SaveState).NoVregs();
450            INST(24, Opcode::CallStatic).b().InputsAutoType(20, 21, 22, 23, 31);
451            INST(25, Opcode::ReturnVoid);
452        }
453    }
454
455    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
456}
457
458TEST_F(VNTest, VnTestApply3)
459{
460    GRAPH(GetGraph())
461    {
462        PARAMETER(0, 0).ref();
463        CONSTANT(1, 0);
464        CONSTANT(2, 1);
465        BASIC_BLOCK(2, 3)
466        {
467            INST(3, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
468            INST(4, Opcode::NullCheck).ref().Inputs(0, 3);
469            INST(5, Opcode::LenArray).s32().Inputs(4);
470        }
471        BASIC_BLOCK(3, 5, 4)
472        {
473            INST(7, Opcode::Phi).s32().Inputs(1, 20);
474            INST(11, Opcode::SafePoint).Inputs(0, 5, 7).SrcVregs({0, 1, 2});
475            INST(12, Opcode::Compare).CC(CC_EQ).b().Inputs(7, 5);  // i < X
476            INST(13, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(12);
477        }
478        BASIC_BLOCK(4, 3)
479        {
480            INST(15, Opcode::SaveState).Inputs(0, 1, 2, 5, 7).SrcVregs({0, 1, 2, 3, 4});
481            INST(16, Opcode::NullCheck).ref().Inputs(0, 15);
482            INST(17, Opcode::LenArray).s32().Inputs(16);
483            INST(18, Opcode::BoundsCheck).s32().Inputs(17, 7, 15);
484            INST(19, Opcode::StoreArray).s64().Inputs(16, 18, 1);
485            INST(20, Opcode::Add).s32().Inputs(7, 2);
486        }
487        BASIC_BLOCK(5, 1)
488        {
489            INST(23, Opcode::Return).ref().Inputs(0);
490        }
491    }
492    GetGraph()->RunPass<ValNum>();
493    GraphChecker(GetGraph()).Check();
494    ASSERT_EQ(INS(5).GetVN(), INS(17).GetVN());
495
496    Graph *graph_et = CreateGraphWithDefaultRuntime();
497    // graph_et is equal the graph
498    GRAPH(graph_et)
499    {
500        PARAMETER(0, 0).ref();
501        CONSTANT(1, 0);
502        CONSTANT(2, 1);
503        BASIC_BLOCK(2, 3)
504        {
505            INST(3, Opcode::SaveState).Inputs(0, 1, 2).SrcVregs({0, 1, 2});
506            INST(4, Opcode::NullCheck).ref().Inputs(0, 3);
507            INST(5, Opcode::LenArray).s32().Inputs(4);
508        }
509        BASIC_BLOCK(3, 5, 4)
510        {
511            INST(7, Opcode::Phi).s32().Inputs(1, 20);
512            INST(11, Opcode::SafePoint).Inputs(0, 5, 7).SrcVregs({0, 1, 2});
513            INST(12, Opcode::Compare).CC(CC_EQ).b().Inputs(7, 5);  // i < X
514            INST(13, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(12);
515        }
516        BASIC_BLOCK(4, 3)
517        {
518            INST(15, Opcode::SaveState).Inputs(0, 1, 2, 5, 7).SrcVregs({0, 1, 2, 3, 4});
519            INST(16, Opcode::NullCheck).ref().Inputs(0, 15);
520            INST(17, Opcode::LenArray).s32().Inputs(16);
521            INST(18, Opcode::BoundsCheck).s32().Inputs(5, 7, 15);
522            INST(19, Opcode::StoreArray).s64().Inputs(16, 18, 1);
523            INST(20, Opcode::Add).s32().Inputs(7, 2);
524        }
525        BASIC_BLOCK(5, 1)
526        {
527            INST(23, Opcode::Return).ref().Inputs(0);
528        }
529    }
530    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
531}
532
533TEST_F(VNTest, CleanupTrigger)
534{
535    GRAPH(GetGraph())
536    {
537        PARAMETER(0, 0).u64();
538        PARAMETER(1, 1).u64();
539        BASIC_BLOCK(2, 3, 4)
540        {
541            INST(5, Opcode::Add).u64().Inputs(0, 1);
542            INST(6, Opcode::Add).u64().Inputs(0, 1);
543            INST(7, Opcode::Compare).b().Inputs(0, 1);
544            INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
545        }
546        BASIC_BLOCK(3, 4) {}
547        BASIC_BLOCK(4, -1)
548        {
549            INST(9, Opcode::Phi).u64().Inputs({{2, 6}, {3, 5}});
550            INST(10, Opcode::Return).u64().Inputs(9);
551        }
552    }
553
554    GraphChecker(GetGraph()).Check();
555    GetGraph()->RunPass<ValNum>();
556
557    auto graph = CreateGraphWithDefaultRuntime();
558    GRAPH(graph)
559    {
560        PARAMETER(0, 0).u64();
561        PARAMETER(1, 1).u64();
562        BASIC_BLOCK(2, 3, 4)
563        {
564            INST(5, Opcode::Add).u64().Inputs(0, 1);
565            INST(6, Opcode::Add).u64().Inputs(0, 1);
566            INST(7, Opcode::Compare).b().Inputs(0, 1);
567            INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
568        }
569        BASIC_BLOCK(3, 4) {}
570        BASIC_BLOCK(4, -1)
571        {
572            INST(9, Opcode::Phi).u64().Inputs({{2, 5}, {3, 5}});
573            INST(10, Opcode::Return).u64().Inputs(9);
574        }
575    }
576    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
577}
578
579TEST_F(VNTest, OSR)
580{
581    GRAPH(GetGraph())
582    {
583        PARAMETER(0, 0).u64();
584        PARAMETER(1, 1).u64();
585        BASIC_BLOCK(2, 3, 4)
586        {
587            INST(2, Opcode::Add).u64().Inputs(0, 1);
588            INST(3, Opcode::Compare).b().Inputs(0, 2);
589            INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
590        }
591        BASIC_BLOCK(3, 3, 4)
592        {
593            INST(5, Opcode::Phi).u64().Inputs({{2, 0}, {3, 6}});
594            INST(6, Opcode::Sub).u64().Inputs(5, 1);
595            INST(7, Opcode::Compare).b().Inputs(6, 1);
596            INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
597        }
598        BASIC_BLOCK(4, -1)
599        {
600            INST(9, Opcode::Phi).u64().Inputs({{2, 0}, {3, 6}});
601            INST(10, Opcode::Add).u64().Inputs(0, 1);
602            INST(11, Opcode::Add).u64().Inputs(9, 10);
603            INST(12, Opcode::Return).u64().Inputs(11);
604        }
605    }
606
607    // Remove Inst 11 without OSR
608
609    GetGraph()->RunPass<ValNum>();
610    GetGraph()->RunPass<Cleanup>();
611
612    auto graph = CreateGraphWithDefaultRuntime();
613
614    GRAPH(graph)
615    {
616        PARAMETER(0, 0).u64();
617        PARAMETER(1, 1).u64();
618        BASIC_BLOCK(2, 3, 4)
619        {
620            INST(2, Opcode::Add).u64().Inputs(0, 1);
621            INST(3, Opcode::Compare).b().Inputs(0, 2);
622            INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
623        }
624        BASIC_BLOCK(3, 3, 4)
625        {
626            INST(5, Opcode::Phi).u64().Inputs({{2, 0}, {3, 6}});
627            INST(6, Opcode::Sub).u64().Inputs(5, 1);
628            INST(7, Opcode::Compare).b().Inputs(6, 1);
629            INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
630        }
631        BASIC_BLOCK(4, -1)
632        {
633            INST(9, Opcode::Phi).u64().Inputs({{2, 0}, {3, 6}});
634            INST(11, Opcode::Add).u64().Inputs(9, 2);
635            INST(12, Opcode::Return).u64().Inputs(11);
636        }
637    }
638
639    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
640
641    auto graph_osr = CreateGraphOsrWithDefaultRuntime();
642
643    GRAPH(graph_osr)
644    {
645        PARAMETER(0, 0).u64();
646        PARAMETER(1, 1).u64();
647        BASIC_BLOCK(2, 3, 4)
648        {
649            INST(2, Opcode::Add).u64().Inputs(0, 1);
650            INST(3, Opcode::Compare).b().Inputs(0, 2);
651            INST(4, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(3);
652        }
653        BASIC_BLOCK(3, 3, 4)
654        {
655            INST(5, Opcode::Phi).u64().Inputs({{2, 0}, {3, 6}});
656            INST(13, Opcode::SaveStateOsr).Inputs(0, 1, 5).SrcVregs({0, 1, 2});
657            INST(6, Opcode::Sub).u64().Inputs(5, 1);
658            INST(7, Opcode::Compare).b().Inputs(6, 1);
659            INST(8, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0).Inputs(7);
660        }
661        BASIC_BLOCK(4, -1)
662        {
663            INST(9, Opcode::Phi).u64().Inputs({{2, 0}, {3, 6}});
664            INST(10, Opcode::Add).u64().Inputs(0, 1);
665            INST(11, Opcode::Add).u64().Inputs(9, 10);
666            INST(12, Opcode::Return).u64().Inputs(11);
667        }
668    }
669
670    for (auto bb : graph_osr->GetBlocksRPO()) {
671        if (bb->IsLoopHeader()) {
672            bb->SetOsrEntry(true);
673        }
674    }
675
676    auto clone_osr = GraphCloner(graph_osr, graph_osr->GetAllocator(), graph_osr->GetLocalAllocator()).CloneGraph();
677
678    // Don't remove Inst 11 with OSR
679
680    graph_osr->RunPass<ValNum>();
681    graph_osr->RunPass<Cleanup>();
682
683    ASSERT_TRUE(GraphComparator().Compare(clone_osr, graph_osr));
684}
685
686TEST_F(VNTest, VnTestCommutative)
687{
688    // Remove commutative arithmetic instructions(See 2516)
689    GRAPH(GetGraph())
690    {
691        PARAMETER(0, 0).u64();
692        PARAMETER(1, 1).u64();
693
694        BASIC_BLOCK(2, -1)
695        {
696            INST(2, Opcode::Add).u64().Inputs(0, 1);
697            INST(3, Opcode::Mul).u64().Inputs(0, 1);
698            INST(4, Opcode::Xor).u64().Inputs(0, 1);
699            INST(5, Opcode::Or).u64().Inputs(0, 1);
700            INST(6, Opcode::And).u64().Inputs(0, 1);
701            INST(7, Opcode::Min).u64().Inputs(0, 1);
702            INST(8, Opcode::Max).u64().Inputs(0, 1);
703            INST(9, Opcode::Add).u64().Inputs(1, 0);
704            INST(10, Opcode::Mul).u64().Inputs(1, 0);
705            INST(11, Opcode::Xor).u64().Inputs(1, 0);
706            INST(12, Opcode::Or).u64().Inputs(1, 0);
707            INST(13, Opcode::And).u64().Inputs(1, 0);
708            INST(14, Opcode::Min).u64().Inputs(1, 0);
709            INST(15, Opcode::Max).u64().Inputs(1, 0);
710            INST(20, Opcode::SaveState).NoVregs();
711            INST(16, Opcode::CallStatic).b().InputsAutoType(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20);
712            INST(17, Opcode::ReturnVoid);
713        }
714    }
715    Graph *graph_et = CreateGraphWithDefaultRuntime();
716    GRAPH(graph_et)
717    {
718        PARAMETER(0, 0).u64();
719        PARAMETER(1, 1).u64();
720
721        BASIC_BLOCK(2, -1)
722        {
723            INST(2, Opcode::Add).u64().Inputs(0, 1);
724            INST(3, Opcode::Mul).u64().Inputs(0, 1);
725            INST(4, Opcode::Xor).u64().Inputs(0, 1);
726            INST(5, Opcode::Or).u64().Inputs(0, 1);
727            INST(6, Opcode::And).u64().Inputs(0, 1);
728            INST(7, Opcode::Min).u64().Inputs(0, 1);
729            INST(8, Opcode::Max).u64().Inputs(0, 1);
730            INST(20, Opcode::SaveState).NoVregs();
731            INST(16, Opcode::CallStatic).b().InputsAutoType(2, 3, 4, 5, 6, 7, 8, 2, 3, 4, 5, 6, 7, 8, 20);
732            INST(17, Opcode::ReturnVoid);
733        }
734    }
735
736    GetGraph()->RunPass<ValNum>();
737    GetGraph()->RunPass<Cleanup>();
738    GraphChecker(GetGraph()).Check();
739    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
740}
741
742TEST_F(VNTest, VnTestCommutativeNotAppliedNoApplied)
743{
744    // We don't remove float commutative arithmetic instructions and not commutative instruction(sub)
745    GRAPH(GetGraph())
746    {
747        PARAMETER(0, 0).f64();
748        PARAMETER(1, 1).f64();
749        PARAMETER(2, 2).u64();
750        PARAMETER(3, 3).u64();
751
752        BASIC_BLOCK(2, -1)
753        {
754            INST(4, Opcode::Add).f64().Inputs(0, 1);
755            INST(5, Opcode::Mul).f64().Inputs(0, 1);
756            INST(6, Opcode::Min).f64().Inputs(0, 1);
757            INST(7, Opcode::Max).f64().Inputs(0, 1);
758            INST(8, Opcode::Sub).u64().Inputs(2, 3);
759            INST(9, Opcode::Add).f64().Inputs(1, 0);
760            INST(10, Opcode::Mul).f64().Inputs(1, 0);
761            INST(11, Opcode::Min).f64().Inputs(1, 0);
762            INST(12, Opcode::Max).f64().Inputs(1, 0);
763            INST(13, Opcode::Sub).u64().Inputs(3, 2);
764            INST(20, Opcode::SaveState).NoVregs();
765            INST(14, Opcode::CallStatic).b().InputsAutoType(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 20);
766            INST(15, Opcode::ReturnVoid);
767        }
768    }
769    Graph *graph_et = CreateGraphWithDefaultRuntime();
770    GRAPH(graph_et)
771    {
772        PARAMETER(0, 0).f64();
773        PARAMETER(1, 1).f64();
774        PARAMETER(2, 2).u64();
775        PARAMETER(3, 3).u64();
776
777        BASIC_BLOCK(2, -1)
778        {
779            INST(4, Opcode::Add).f64().Inputs(0, 1);
780            INST(5, Opcode::Mul).f64().Inputs(0, 1);
781            INST(6, Opcode::Min).f64().Inputs(0, 1);
782            INST(7, Opcode::Max).f64().Inputs(0, 1);
783            INST(8, Opcode::Sub).u64().Inputs(2, 3);
784            INST(9, Opcode::Add).f64().Inputs(1, 0);
785            INST(10, Opcode::Mul).f64().Inputs(1, 0);
786            INST(11, Opcode::Min).f64().Inputs(1, 0);
787            INST(12, Opcode::Max).f64().Inputs(1, 0);
788            INST(13, Opcode::Sub).u64().Inputs(3, 2);
789            INST(20, Opcode::SaveState).NoVregs();
790            INST(14, Opcode::CallStatic).b().InputsAutoType(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 20);
791            INST(15, Opcode::ReturnVoid);
792        }
793    }
794
795    GetGraph()->RunPass<ValNum>();
796    GetGraph()->RunPass<Cleanup>();
797    GraphChecker(GetGraph()).Check();
798    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
799}
800
801TEST_F(VNTest, VnTestIsInstance)
802{
803    GRAPH(GetGraph())
804    {
805        PARAMETER(0, 0).ref();
806        PARAMETER(1, 1).ref();
807        BASIC_BLOCK(2, -1)
808        {
809            INST(12, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
810            INST(2, Opcode::LoadClass).ref().Inputs(12).TypeId(1);
811            INST(3, Opcode::IsInstance).b().Inputs(0, 2, 12).TypeId(1);
812            INST(4, Opcode::LoadClass).ref().Inputs(12).TypeId(1);
813            INST(5, Opcode::IsInstance).b().Inputs(0, 4, 12).TypeId(1);
814            INST(6, Opcode::LoadClass).ref().Inputs(12).TypeId(1);
815            INST(7, Opcode::IsInstance).b().Inputs(1, 6, 12).TypeId(1);
816            INST(8, Opcode::LoadClass).ref().Inputs(12).TypeId(2);
817            INST(9, Opcode::IsInstance).b().Inputs(0, 8, 12).TypeId(2);
818            INST(20, Opcode::SaveState).NoVregs();
819            INST(10, Opcode::CallStatic).b().InputsAutoType(3, 5, 7, 9, 20);
820            INST(11, Opcode::ReturnVoid);
821        }
822    }
823    Graph *graph_et = CreateGraphWithDefaultRuntime();
824    GRAPH(graph_et)
825    {
826        PARAMETER(0, 0).ref();
827        PARAMETER(1, 1).ref();
828        BASIC_BLOCK(2, -1)
829        {
830            INST(12, Opcode::SaveState).Inputs(0, 1).SrcVregs({0, 1});
831            INST(2, Opcode::LoadClass).ref().Inputs(12).TypeId(1);
832            INST(3, Opcode::IsInstance).b().Inputs(0, 2, 12).TypeId(1);
833            INST(7, Opcode::IsInstance).b().Inputs(1, 2, 12).TypeId(1);
834            INST(8, Opcode::LoadClass).ref().Inputs(12).TypeId(2);
835            INST(9, Opcode::IsInstance).b().Inputs(0, 8, 12).TypeId(2);
836            INST(20, Opcode::SaveState).NoVregs();
837            INST(10, Opcode::CallStatic).b().InputsAutoType(3, 3, 7, 9, 20);
838            INST(11, Opcode::ReturnVoid);
839        }
840    }
841
842    GetGraph()->RunPass<ValNum>();
843    GetGraph()->RunPass<Cleanup>();
844    GraphChecker(GetGraph()).Check();
845    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
846}
847
848TEST_F(VNTest, VnTestInitDifferentClasses)
849{
850    GRAPH(GetGraph())
851    {
852        BASIC_BLOCK(2, -1)
853        {
854            INST(1, Opcode::SaveState).NoVregs();
855            INST(2, Opcode::InitClass).Inputs(1).TypeId(1);
856            INST(3, Opcode::InitClass).Inputs(1).TypeId(2);
857            INST(4, Opcode::ReturnVoid);
858        }
859    }
860
861    auto clone_graph =
862        GraphCloner(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator()).CloneGraph();
863
864    GetGraph()->RunPass<ValNum>();
865    GetGraph()->RunPass<Cleanup>();
866    GraphChecker(GetGraph()).Check();
867    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), clone_graph));
868}
869
870TEST_F(VNTest, VnTestInitClass)
871{
872    GRAPH(GetGraph())
873    {
874        BASIC_BLOCK(2, -1)
875        {
876            INST(1, Opcode::SaveState).NoVregs();
877            INST(2, Opcode::InitClass).Inputs(1).TypeId(1);
878            INST(3, Opcode::InitClass).Inputs(1).TypeId(1);
879            INST(4, Opcode::ReturnVoid);
880        }
881    }
882
883    Graph *graph_et = CreateGraphWithDefaultRuntime();
884    GRAPH(graph_et)
885    {
886        BASIC_BLOCK(2, -1)
887        {
888            INST(1, Opcode::SaveState).NoVregs();
889            INST(2, Opcode::InitClass).Inputs(1).TypeId(1);
890            INST(4, Opcode::ReturnVoid);
891        }
892    }
893
894    GetGraph()->RunPass<ValNum>();
895    GetGraph()->RunPass<Cleanup>();
896    GraphChecker(GetGraph()).Check();
897    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
898}
899
900TEST_F(VNTest, VnTestInitAfterLoad)
901{
902    // If InitClass instruction dominates LoadAndInitClass, replace it with LoadAndInitClass
903    // and remove the old LoadAndInitClass
904    // We cannot move outputs of LoadAndInitClass to LoadClass
905    GRAPH(GetGraph())
906    {
907        PARAMETER(0, 0).ref();
908        BASIC_BLOCK(2, -1)
909        {
910            INST(1, Opcode::SaveState).Inputs(0).SrcVregs({0});
911            INST(2, Opcode::LoadClass).ref().Inputs(1).TypeId(1);
912            INST(3, Opcode::IsInstance).b().Inputs(0, 2, 1).TypeId(1);
913            INST(4, Opcode::InitClass).Inputs(1).TypeId(1);
914            INST(5, Opcode::CallStatic).v0id().InputsAutoType(1);
915            INST(6, Opcode::LoadAndInitClass).ref().Inputs(1).TypeId(1);
916            INST(7, Opcode::NewObject).ref().Inputs(6, 1).TypeId(1);
917            INST(8, Opcode::Return).b().Inputs(3);
918        }
919    }
920    Graph *graph_et = CreateGraphWithDefaultRuntime();
921    GRAPH(graph_et)
922    {
923        PARAMETER(0, 0).ref();
924        BASIC_BLOCK(2, -1)
925        {
926            INST(1, Opcode::SaveState).Inputs(0).SrcVregs({0});
927            INST(2, Opcode::LoadClass).ref().Inputs(1).TypeId(1);
928            INST(3, Opcode::IsInstance).b().Inputs(0, 2, 1).TypeId(1);
929            INST(4, Opcode::LoadAndInitClass).ref().Inputs(1).TypeId(1);
930            INST(5, Opcode::CallStatic).v0id().InputsAutoType(1);
931            INST(7, Opcode::NewObject).ref().Inputs(4, 1).TypeId(1);
932            INST(8, Opcode::Return).b().Inputs(3);
933        }
934    }
935
936    GetGraph()->RunPass<ValNum>();
937    GetGraph()->RunPass<Cleanup>();
938    GraphChecker(GetGraph()).Check();
939    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
940}
941
942TEST_F(VNTest, VnTestLoadAfterInit)
943{
944    GRAPH(GetGraph())
945    {
946        PARAMETER(0, 0).ref();
947        BASIC_BLOCK(2, -1)
948        {
949            INST(1, Opcode::SaveState).Inputs(0).SrcVregs({0});
950            INST(2, Opcode::LoadClass).ref().Inputs(1).TypeId(1);
951            INST(3, Opcode::IsInstance).b().Inputs(0, 2, 1).TypeId(1);
952            INST(4, Opcode::InitClass).Inputs(1).TypeId(1);
953            INST(5, Opcode::CallStatic).v0id().InputsAutoType(1);
954            INST(6, Opcode::LoadClass).ref().Inputs(1).TypeId(1);
955            INST(7, Opcode::CheckCast).b().Inputs(0, 6, 1).TypeId(1);
956            INST(8, Opcode::Return).b().Inputs(3);
957        }
958    }
959    Graph *graph_et = CreateGraphWithDefaultRuntime();
960    GRAPH(graph_et)
961    {
962        PARAMETER(0, 0).ref();
963        BASIC_BLOCK(2, -1)
964        {
965            INST(1, Opcode::SaveState).Inputs(0).SrcVregs({0});
966            INST(2, Opcode::LoadClass).ref().Inputs(1).TypeId(1);
967            INST(3, Opcode::IsInstance).b().Inputs(0, 2, 1).TypeId(1);
968            INST(4, Opcode::InitClass).Inputs(1).TypeId(1);
969            INST(5, Opcode::CallStatic).v0id().InputsAutoType(1);
970            INST(7, Opcode::CheckCast).b().Inputs(0, 2, 1).TypeId(1);
971            INST(8, Opcode::Return).b().Inputs(3);
972        }
973    }
974
975    GetGraph()->RunPass<ValNum>();
976    GetGraph()->RunPass<Cleanup>();
977    GraphChecker(GetGraph()).Check();
978    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
979}
980
981TEST_F(VNTest, VnTestLoadAndInit)
982{
983    // If InitClass, LoadClass, or LoadAndInitClass is dominated by LoadAndInitClass
984    // with the same TypeId, remove the dominated instruction
985    GRAPH(GetGraph())
986    {
987        PARAMETER(0, 0).ref();
988        BASIC_BLOCK(2, -1)
989        {
990            INST(1, Opcode::SaveState).Inputs(0).SrcVregs({0});
991            INST(2, Opcode::LoadAndInitClass).ref().Inputs(1).TypeId(1);
992            INST(3, Opcode::NewObject).ref().Inputs(2, 1).TypeId(1);
993            INST(4, Opcode::LoadClass).ref().Inputs(1).TypeId(1);
994            INST(5, Opcode::CheckCast).b().Inputs(0, 4, 1).TypeId(1);
995            INST(6, Opcode::InitClass).Inputs(1).TypeId(1);
996            INST(7, Opcode::LoadAndInitClass).ref().Inputs(1).TypeId(1);
997            INST(8, Opcode::NewObject).ref().Inputs(7, 1).TypeId(1);
998            INST(9, Opcode::ReturnVoid).v0id();
999        }
1000    }
1001    Graph *graph_et = CreateGraphWithDefaultRuntime();
1002    GRAPH(graph_et)
1003    {
1004        PARAMETER(0, 0).ref();
1005        BASIC_BLOCK(2, -1)
1006        {
1007            INST(1, Opcode::SaveState).Inputs(0).SrcVregs({0});
1008            INST(2, Opcode::LoadAndInitClass).ref().Inputs(1).TypeId(1);
1009            INST(3, Opcode::NewObject).ref().Inputs(2, 1).TypeId(1);
1010            INST(5, Opcode::CheckCast).b().Inputs(0, 2, 1).TypeId(1);
1011            INST(8, Opcode::NewObject).ref().Inputs(2, 1).TypeId(1);
1012            INST(9, Opcode::ReturnVoid).v0id();
1013        }
1014    }
1015
1016    GetGraph()->RunPass<ValNum>();
1017    GetGraph()->RunPass<Cleanup>();
1018    GraphChecker(GetGraph()).Check();
1019    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph_et));
1020}
1021
1022TEST_F(VNTest, Domination)
1023{
1024    GRAPH(GetGraph())
1025    {
1026        PARAMETER(0, 0).s64();
1027        PARAMETER(1, 1).s64();
1028
1029        BASIC_BLOCK(2, 3, 4)
1030        {
1031            INST(2, Opcode::IfImm).SrcType(DataType::INT64).CC(CC_EQ).Imm(0).Inputs(0);
1032        }
1033        BASIC_BLOCK(3, 5)
1034        {
1035            INST(4, Opcode::Mul).s64().Inputs(0, 1);
1036        }
1037        BASIC_BLOCK(4, 5)
1038        {
1039            // this inst does not dominate similar Add insts from bb 5
1040            INST(5, Opcode::Add).s64().Inputs(0, 1);
1041        }
1042        BASIC_BLOCK(5, -1)
1043        {
1044            INST(6, Opcode::Phi).s64().Inputs({{3, 4}, {4, 5}});
1045            // this inst dominates similar Add insts in this bb
1046            INST(7, Opcode::Add).s64().Inputs(0, 1);
1047            INST(8, Opcode::Mul).s64().Inputs(6, 7);
1048
1049            INST(9, Opcode::Add).s64().Inputs(0, 1);
1050            INST(10, Opcode::Mul).s64().Inputs(8, 9);
1051
1052            INST(11, Opcode::Add).s64().Inputs(0, 1);
1053            INST(12, Opcode::Mul).s64().Inputs(10, 11);
1054
1055            INST(13, Opcode::Return).s64().Inputs(12);
1056        }
1057    }
1058
1059    GraphChecker(GetGraph()).Check();
1060    GetGraph()->RunPass<ValNum>();
1061    GetGraph()->RunPass<Cleanup>();
1062    GraphChecker(GetGraph()).Check();
1063
1064    Graph *graph = CreateGraphWithDefaultRuntime();
1065    GRAPH(graph)
1066    {
1067        PARAMETER(0, 0).s64();
1068        PARAMETER(1, 1).s64();
1069
1070        BASIC_BLOCK(2, 3, 4)
1071        {
1072            INST(2, Opcode::IfImm).SrcType(DataType::INT64).CC(CC_EQ).Imm(0).Inputs(0);
1073        }
1074        BASIC_BLOCK(3, 5)
1075        {
1076            INST(4, Opcode::Mul).s64().Inputs(0, 1);
1077        }
1078        BASIC_BLOCK(4, 5)
1079        {
1080            // this inst does not dominate similar Add insts from bb 5
1081            INST(5, Opcode::Add).s64().Inputs(0, 1);
1082        }
1083        BASIC_BLOCK(5, -1)
1084        {
1085            INST(6, Opcode::Phi).s64().Inputs({{3, 4}, {4, 5}});
1086            // this inst dominates similar Add insts in this bb
1087            INST(7, Opcode::Add).s64().Inputs(0, 1);
1088            INST(8, Opcode::Mul).s64().Inputs(6, 7);
1089
1090            INST(10, Opcode::Mul).s64().Inputs(8, 7);
1091
1092            INST(12, Opcode::Mul).s64().Inputs(10, 7);
1093
1094            INST(13, Opcode::Return).s64().Inputs(12);
1095        }
1096    }
1097
1098    ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
1099}
1100
1101}  // namespace panda::compiler
1102