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/balance_expressions.h"
18
19 namespace panda::compiler {
20 class BalanceExpressionsTest : public GraphTest {
21 };
22
TEST_F(BalanceExpressionsTest,AddMulParallel)23 TEST_F(BalanceExpressionsTest, AddMulParallel)
24 {
25 // Check that independent expression are not mixed with each other and being considered sequentially:
26 GRAPH(GetGraph())
27 {
28 PARAMETER(0, 0).u64();
29 PARAMETER(1, 1).u64();
30 PARAMETER(2, 2).u64();
31 PARAMETER(3, 3).u64();
32 PARAMETER(4, 4).u64();
33 PARAMETER(5, 5).u64();
34 PARAMETER(6, 6).u64();
35 PARAMETER(7, 7).u64();
36
37 /**
38 * From:
39 * (((((((a + b) + c) + d) + e) + f) + g) + h)
40 * interlined with
41 * (((((((a * b) * c) * d) * e) * f) * g) * h)
42 *
43 * (Critical path is 8)
44 */
45 BASIC_BLOCK(2, -1)
46 {
47 INST(8, Opcode::Add).u64().Inputs(0, 1);
48 INST(9, Opcode::Mul).u64().Inputs(0, 1);
49
50 INST(10, Opcode::Add).u64().Inputs(8, 2);
51 INST(11, Opcode::Mul).u64().Inputs(9, 2);
52
53 INST(12, Opcode::Add).u64().Inputs(10, 3);
54 INST(13, Opcode::Mul).u64().Inputs(11, 3);
55
56 INST(14, Opcode::Add).u64().Inputs(12, 4);
57 INST(15, Opcode::Mul).u64().Inputs(13, 4);
58
59 INST(16, Opcode::Add).u64().Inputs(14, 5);
60 INST(17, Opcode::Mul).u64().Inputs(15, 5);
61
62 INST(18, Opcode::Add).u64().Inputs(16, 6);
63 INST(19, Opcode::Mul).u64().Inputs(17, 6);
64
65 INST(20, Opcode::Add).u64().Inputs(18, 7);
66 INST(21, Opcode::Mul).u64().Inputs(19, 7);
67
68 INST(22, Opcode::Mul).u64().Inputs(21, 20);
69 INST(23, Opcode::Return).u64().Inputs(22);
70 }
71 }
72
73 ASSERT_TRUE(GetGraph()->RunPass<BalanceExpressions>());
74 ASSERT_TRUE(CheckUsers(INS(20), {22}));
75 ASSERT_TRUE(CheckUsers(INS(22), {23}));
76
77 auto graph = CreateEmptyGraph();
78 GRAPH(graph)
79 {
80 PARAMETER(0, 0).u64();
81 PARAMETER(1, 1).u64();
82 PARAMETER(2, 2).u64();
83 PARAMETER(3, 3).u64();
84 PARAMETER(4, 4).u64();
85 PARAMETER(5, 5).u64();
86 PARAMETER(6, 6).u64();
87 PARAMETER(7, 7).u64();
88
89 /**
90 * To:
91 * (((a + b) + (c + d)) + ((e + f) + (g + h)))
92 * followed by
93 * (((a * b) * (c * d)) * ((e * f) * (g * h)))
94 *
95 * (Critical path is 4)
96 */
97 BASIC_BLOCK(2, -1)
98 {
99 INST(8, Opcode::Add).u64().Inputs(0, 1);
100 INST(10, Opcode::Add).u64().Inputs(2, 3);
101 INST(12, Opcode::Add).u64().Inputs(8, 10);
102 INST(14, Opcode::Add).u64().Inputs(4, 5);
103 INST(16, Opcode::Add).u64().Inputs(6, 7);
104 INST(18, Opcode::Add).u64().Inputs(14, 16);
105 INST(20, Opcode::Add).u64().Inputs(12, 18);
106
107 INST(9, Opcode::Mul).u64().Inputs(0, 1);
108 INST(11, Opcode::Mul).u64().Inputs(2, 3);
109 INST(13, Opcode::Mul).u64().Inputs(9, 11);
110 INST(15, Opcode::Mul).u64().Inputs(4, 5);
111 INST(17, Opcode::Mul).u64().Inputs(6, 7);
112 INST(19, Opcode::Mul).u64().Inputs(15, 17);
113 INST(21, Opcode::Mul).u64().Inputs(13, 19);
114
115 INST(22, Opcode::Mul).u64().Inputs(21, 20);
116 INST(23, Opcode::Return).u64().Inputs(22);
117 }
118 }
119
120 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
121 }
122
TEST_F(BalanceExpressionsTest,MultipleUsers)123 TEST_F(BalanceExpressionsTest, MultipleUsers)
124 {
125 // Instruction with more than one user may create side effects, so it is needed to check that they are considered as
126 // sources (thus would not be modified).
127 // Also checks that the last operator of an expression has the same users as before its optimization:
128 GRAPH(GetGraph())
129 {
130 PARAMETER(0, 0).u64();
131 PARAMETER(1, 1).u64();
132 PARAMETER(2, 2).u64();
133 PARAMETER(3, 3).u64();
134 PARAMETER(4, 4).u64();
135 PARAMETER(5, 5).u64();
136 PARAMETER(6, 6).u64();
137
138 BASIC_BLOCK(2, -1)
139 {
140 INST(8, Opcode::Add).u64().Inputs(0, 1);
141 INST(9, Opcode::Add).u64().Inputs(2, 8);
142
143 // Has multiple users:
144 INST(10, Opcode::Add).u64().Inputs(3, 9);
145
146 INST(11, Opcode::Add).u64().Inputs(4, 10);
147 INST(12, Opcode::Add).u64().Inputs(5, 6);
148 INST(13, Opcode::Add).u64().Inputs(11, 12);
149 INST(14, Opcode::Add).u64().Inputs(10, 13);
150
151 INST(15, Opcode::Return).u64().Inputs(14);
152 }
153 }
154
155 ASSERT_TRUE(GetGraph()->RunPass<BalanceExpressions>());
156
157 // The same users as we expect that the second expression would be unchanged
158 ASSERT_TRUE(CheckUsers(INS(10), {11, 14}));
159 ASSERT_TRUE(CheckUsers(INS(14), {15}));
160
161 auto graph = CreateEmptyGraph();
162 GRAPH(graph)
163 {
164 PARAMETER(0, 0).u64();
165 PARAMETER(1, 1).u64();
166 PARAMETER(2, 2).u64();
167 PARAMETER(3, 3).u64();
168 PARAMETER(4, 4).u64();
169 PARAMETER(5, 5).u64();
170 PARAMETER(6, 6).u64();
171
172 BASIC_BLOCK(2, -1)
173 {
174 INST(8, Opcode::Add).u64().Inputs(3, 2);
175 INST(9, Opcode::Add).u64().Inputs(0, 1);
176
177 // Has multiple users:
178 INST(10, Opcode::Add).u64().Inputs(8, 9);
179
180 INST(11, Opcode::Add).u64().Inputs(4, 10);
181 INST(12, Opcode::Add).u64().Inputs(5, 6);
182 INST(13, Opcode::Add).u64().Inputs(11, 12);
183 INST(14, Opcode::Add).u64().Inputs(10, 13);
184
185 INST(15, Opcode::Return).u64().Inputs(14);
186 }
187 }
188 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
189 }
190
TEST_F(BalanceExpressionsTest,SameSource)191 TEST_F(BalanceExpressionsTest, SameSource)
192 {
193 // Check that expression with repeated sources are handled correctly:
194 GRAPH(GetGraph())
195 {
196 PARAMETER(0, 0).u64();
197
198 BASIC_BLOCK(2, -1)
199 {
200 INST(1, Opcode::Add).u64().Inputs(0, 0);
201 INST(2, Opcode::Add).u64().Inputs(0, 1);
202 INST(3, Opcode::Add).u64().Inputs(0, 2);
203
204 INST(4, Opcode::Return).u64().Inputs(3);
205 }
206 }
207 ASSERT_TRUE(GetGraph()->RunPass<BalanceExpressions>());
208 ASSERT_TRUE(CheckUsers(INS(3), {4}));
209
210 auto graph = CreateEmptyGraph();
211 GRAPH(graph)
212 {
213 PARAMETER(0, 0).u64();
214
215 BASIC_BLOCK(2, -1)
216 {
217 INST(1, Opcode::Add).u64().Inputs(0, 0);
218 INST(2, Opcode::Add).u64().Inputs(0, 0);
219 INST(3, Opcode::Add).u64().Inputs(1, 2);
220
221 INST(4, Opcode::Return).u64().Inputs(3);
222 }
223 }
224
225 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
226 }
227
TEST_F(BalanceExpressionsTest,OddSources)228 TEST_F(BalanceExpressionsTest, OddSources)
229 {
230 // Check that expression with odd number of sources are handled correctly:
231 GRAPH(GetGraph())
232 {
233 PARAMETER(0, 0).u64();
234 PARAMETER(1, 1).u64();
235 PARAMETER(2, 2).u64();
236 PARAMETER(3, 3).u64();
237 PARAMETER(4, 4).u64();
238
239 /**
240 * From:
241 * (a + (e + ((c + d) + b)))
242 *
243 * (Critical path is 4)
244 */
245 BASIC_BLOCK(2, -1)
246 {
247 INST(5, Opcode::Add).u64().Inputs(2, 3);
248 INST(6, Opcode::Add).u64().Inputs(5, 1);
249 INST(7, Opcode::Add).u64().Inputs(4, 6);
250 INST(8, Opcode::Add).u64().Inputs(0, 7);
251
252 INST(9, Opcode::Return).u64().Inputs(8);
253 }
254 }
255 ASSERT_TRUE(GetGraph()->RunPass<BalanceExpressions>());
256 ASSERT_TRUE(CheckUsers(INS(8), {9}));
257
258 auto graph = CreateEmptyGraph();
259 GRAPH(graph)
260 {
261 PARAMETER(0, 0).u64();
262 PARAMETER(1, 1).u64();
263 PARAMETER(2, 2).u64();
264 PARAMETER(3, 3).u64();
265 PARAMETER(4, 4).u64();
266
267 /**
268 * To:
269 * (((a + e) + (c + d)) + b)
270 *
271 * (Critical path is 3)
272 */
273 BASIC_BLOCK(2, -1)
274 {
275 INST(5, Opcode::Add).u64().Inputs(0, 4);
276 INST(6, Opcode::Add).u64().Inputs(2, 3);
277 INST(7, Opcode::Add).u64().Inputs(5, 6);
278 INST(8, Opcode::Add).u64().Inputs(7, 1);
279
280 INST(9, Opcode::Return).u64().Inputs(8);
281 }
282 }
283
284 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
285 }
286 } // namespace panda::compiler
287