1 /*
2 * Copyright (c) 2021-2023 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/analysis/bounds_analysis.h"
18 #include "optimizer/optimizations/cleanup.h"
19 #include "optimizer/optimizations/peepholes.h"
20 #include "utils/arena_containers.h"
21
22 namespace panda::compiler {
23 class BoundsAnalysisTest : public CommonTest {
24 public:
BoundsAnalysisTest()25 BoundsAnalysisTest() : graph_(CreateGraphStartEndBlocks()) {}
26
GetGraph()27 Graph *GetGraph()
28 {
29 return graph_;
30 }
31
32 // ll, lr, rl, rr - test bounds
33 // rll, rlr, rrl, rrr - result bounds
CCTest(ConditionCode cc,int64_t ll,int64_t lr,int64_t rl,int64_t rr,int64_t rll,int64_t rlr,int64_t rrl,int64_t rrr)34 void CCTest(ConditionCode cc, int64_t ll, int64_t lr, int64_t rl, int64_t rr, int64_t rll, int64_t rlr, int64_t rrl,
35 int64_t rrr)
36 {
37 auto [nrl, nrr] = BoundsRange::TryNarrowBoundsByCC(cc, {BoundsRange(ll, lr), BoundsRange(rl, rr)});
38 ASSERT_EQ(nrl.GetLeft(), rll);
39 ASSERT_EQ(nrl.GetRight(), rlr);
40 ASSERT_EQ(nrr.GetLeft(), rrl);
41 ASSERT_EQ(nrr.GetRight(), rrr);
42 }
43
44 private:
45 Graph *graph_ {nullptr};
46 };
47 // NOLINTBEGIN(readability-magic-numbers)
TEST_F(BoundsAnalysisTest,NegTest)48 TEST_F(BoundsAnalysisTest, NegTest)
49 {
50 BoundsRange r1 = BoundsRange(-1L, 5U);
51 BoundsRange res1 = r1.Neg();
52 EXPECT_EQ(res1.GetLeft(), -5L);
53 EXPECT_EQ(res1.GetRight(), 1U);
54
55 BoundsRange r2 = BoundsRange(1U, 5U);
56 BoundsRange res2 = r2.Neg();
57 EXPECT_EQ(res2.GetLeft(), -5L);
58 EXPECT_EQ(res2.GetRight(), -1L);
59
60 BoundsRange r3 = BoundsRange(-5L, -1L);
61 BoundsRange res3 = r3.Neg();
62 EXPECT_EQ(res3.GetLeft(), 1U);
63 EXPECT_EQ(res3.GetRight(), 5U);
64 }
65
TEST_F(BoundsAnalysisTest,AbsTest)66 TEST_F(BoundsAnalysisTest, AbsTest)
67 {
68 BoundsRange r1 = BoundsRange(1U, 5U);
69 BoundsRange res1 = r1.Abs();
70 EXPECT_EQ(res1.GetLeft(), 1U);
71 EXPECT_EQ(res1.GetRight(), 5U);
72
73 BoundsRange r2 = BoundsRange(-5L, -1L);
74 BoundsRange res2 = r2.Abs();
75 EXPECT_EQ(res2.GetLeft(), 1U);
76 EXPECT_EQ(res2.GetRight(), 5U);
77
78 BoundsRange r3 = BoundsRange(-1L, 5U);
79 BoundsRange res3 = r3.Abs();
80 EXPECT_EQ(res3.GetLeft(), 0U);
81 EXPECT_EQ(res3.GetRight(), 5U);
82
83 BoundsRange r4 = BoundsRange(-10L, 5U);
84 BoundsRange res4 = r4.Abs();
85 EXPECT_EQ(res4.GetLeft(), 0U);
86 EXPECT_EQ(res4.GetRight(), 10U);
87 }
88
TEST_F(BoundsAnalysisTest,MulTest)89 TEST_F(BoundsAnalysisTest, MulTest)
90 {
91 BoundsRange r1 = BoundsRange(-7L, 5U);
92 BoundsRange r2 = BoundsRange(9U, 13U);
93 BoundsRange r3 = BoundsRange(2U, 5U);
94 BoundsRange r4 = BoundsRange(-4L, -1L);
95 BoundsRange r5 = BoundsRange(-5L, -2L);
96 BoundsRange r6 = BoundsRange(1U, 4U);
97
98 // All posible variations for GetLeft and GetRight
99 BoundsRange res = r1.Mul(r1);
100 EXPECT_EQ(res.GetLeft(), -7L * 5L); // min = ll * rr
101 EXPECT_EQ(res.GetRight(), -7L * -7L); // max = ll * rl
102
103 res = r2.Mul(r2);
104 EXPECT_EQ(res.GetLeft(), 9U * 9U); // min = ll * rl
105 EXPECT_EQ(res.GetRight(), 13U * 13U); // max = lr * rr
106
107 res = r3.Mul(r4);
108 EXPECT_EQ(res.GetLeft(), 5L * -4L); // min = lr * rl
109 EXPECT_EQ(res.GetRight(), 2L * -1L); // max = ll * rr
110
111 res = r4.Mul(r5);
112 EXPECT_EQ(res.GetLeft(), -1L * -2L); // min = lr * rr
113 EXPECT_EQ(res.GetRight(), -4L * -5L); // max = ll * rl
114
115 res = r5.Mul(r6);
116 EXPECT_EQ(res.GetLeft(), -5L * 4L); // min = ll * rr
117 EXPECT_EQ(res.GetRight(), -2L * 1L); // max = lr * rl
118 }
119
TEST_F(BoundsAnalysisTest,DivTest)120 TEST_F(BoundsAnalysisTest, DivTest)
121 {
122 auto l1 = BoundsRange(-7L, 5U);
123 auto l2 = BoundsRange(5U, 7U);
124 auto l3 = BoundsRange(-7L, -5L);
125 auto r1 = BoundsRange(2U);
126 auto r2 = BoundsRange(-2L);
127 BoundsRange res;
128
129 res = l1.Div(r1);
130 EXPECT_EQ(res.GetLeft(), -3L);
131 EXPECT_EQ(res.GetRight(), 2U);
132 res = l1.Div(r2);
133 EXPECT_EQ(res.GetLeft(), -2L);
134 EXPECT_EQ(res.GetRight(), 3U);
135
136 res = l2.Div(r1);
137 EXPECT_EQ(res.GetLeft(), 2U);
138 EXPECT_EQ(res.GetRight(), 3U);
139 res = l2.Div(r2);
140 EXPECT_EQ(res.GetLeft(), -3L);
141 EXPECT_EQ(res.GetRight(), -2L);
142
143 res = l3.Div(r1);
144 EXPECT_EQ(res.GetLeft(), -3L);
145 EXPECT_EQ(res.GetRight(), -2L);
146 res = l3.Div(r2);
147 EXPECT_EQ(res.GetLeft(), 2U);
148 EXPECT_EQ(res.GetRight(), 3U);
149 }
150
TEST_F(BoundsAnalysisTest,OverflowTest)151 TEST_F(BoundsAnalysisTest, OverflowTest)
152 {
153 ASSERT_EQ(BoundsRange::AddWithOverflowCheck(INT64_MAX, INT64_MAX), INT64_MAX);
154 ASSERT_EQ(BoundsRange::AddWithOverflowCheck(INT64_MAX, 1U), INT64_MAX);
155 ASSERT_EQ(BoundsRange::AddWithOverflowCheck(1U, INT64_MAX), INT64_MAX);
156 ASSERT_EQ(BoundsRange::AddWithOverflowCheck(INT64_MIN, INT64_MIN), INT64_MIN);
157 ASSERT_EQ(BoundsRange::AddWithOverflowCheck(INT64_MIN, -1L), INT64_MIN);
158 ASSERT_EQ(BoundsRange::AddWithOverflowCheck(-1L, INT64_MIN), INT64_MIN);
159
160 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(0U, INT64_MAX), 0U);
161 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MAX, 0U), 0U);
162 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(0U, INT64_MIN), 0U);
163 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MIN, 0U), 0U);
164
165 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MAX, INT64_MAX), INT64_MAX);
166 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MAX, 2U), INT64_MAX);
167 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MIN, INT64_MIN), INT64_MAX);
168 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MIN, -2L), INT64_MAX);
169 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MAX, INT64_MIN), INT64_MIN);
170 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MAX, -2L), INT64_MIN);
171 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MIN, INT64_MAX), INT64_MIN);
172 ASSERT_EQ(BoundsRange::MulWithOverflowCheck(INT64_MIN, 2U), INT64_MIN);
173
174 ASSERT_EQ(BoundsRange::DivWithOverflowCheck(INT64_MIN, -1L), INT64_MIN);
175 }
176
TEST_F(BoundsAnalysisTest,BoundsNarrowing)177 TEST_F(BoundsAnalysisTest, BoundsNarrowing)
178 {
179 // case 1
180 CCTest(ConditionCode::CC_GT, 10U, 50U, 20U, 60U, 21U, 50U, 20U, 49U);
181 CCTest(ConditionCode::CC_A, 10U, 50U, 20U, 60U, 21U, 50U, 20U, 49U);
182 CCTest(ConditionCode::CC_GE, 10U, 50U, 20U, 60U, 20U, 50U, 20U, 50U);
183 CCTest(ConditionCode::CC_AE, 10U, 50U, 20U, 60U, 20U, 50U, 20U, 50U);
184 CCTest(ConditionCode::CC_LT, 10U, 50U, 20U, 60U, 10U, 50U, 20U, 60U);
185 CCTest(ConditionCode::CC_B, 10U, 50U, 20U, 60U, 10U, 50U, 20U, 60U);
186 CCTest(ConditionCode::CC_LE, 10U, 50U, 20U, 60U, 10U, 50U, 20U, 60U);
187 CCTest(ConditionCode::CC_BE, 10U, 50U, 20U, 60U, 10U, 50U, 20U, 60U);
188 CCTest(ConditionCode::CC_EQ, 10U, 50U, 20U, 60U, 20U, 50U, 20U, 50U);
189 CCTest(ConditionCode::CC_NE, 10U, 50U, 20U, 60U, 10U, 50U, 20U, 60U);
190
191 // case 2
192 CCTest(ConditionCode::CC_GT, 10U, 20U, 50U, 60U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
193 CCTest(ConditionCode::CC_A, 10U, 20U, 50U, 60U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
194 CCTest(ConditionCode::CC_GE, 10U, 20U, 50U, 60U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
195 CCTest(ConditionCode::CC_AE, 10U, 20U, 50U, 60U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
196 CCTest(ConditionCode::CC_LT, 10U, 20U, 50U, 60U, 10U, 20U, 50U, 60U);
197 CCTest(ConditionCode::CC_B, 10U, 20U, 50U, 60U, 10U, 20U, 50U, 60U);
198 CCTest(ConditionCode::CC_LE, 10U, 20U, 50U, 60U, 10U, 20U, 50U, 60U);
199 CCTest(ConditionCode::CC_BE, 10U, 20U, 50U, 60U, 10U, 20U, 50U, 60U);
200 CCTest(ConditionCode::CC_EQ, 10U, 20U, 50U, 60U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
201 CCTest(ConditionCode::CC_NE, 10U, 20U, 50U, 60U, 10U, 20U, 50U, 60U);
202
203 // case 3
204 CCTest(ConditionCode::CC_GT, 10U, 60U, 20U, 50U, 21U, 60U, 20U, 50U);
205 CCTest(ConditionCode::CC_A, 10U, 60U, 20U, 50U, 21U, 60U, 20U, 50U);
206 CCTest(ConditionCode::CC_GE, 10U, 60U, 20U, 50U, 20U, 60U, 20U, 50U);
207 CCTest(ConditionCode::CC_AE, 10U, 60U, 20U, 50U, 20U, 60U, 20U, 50U);
208 CCTest(ConditionCode::CC_LT, 10U, 60U, 20U, 50U, 10U, 49U, 20U, 50U);
209 CCTest(ConditionCode::CC_B, 10U, 60U, 20U, 50U, 10U, 49U, 20U, 50U);
210 CCTest(ConditionCode::CC_LE, 10U, 60U, 20U, 50U, 10U, 50U, 20U, 50U);
211 CCTest(ConditionCode::CC_BE, 10U, 60U, 20U, 50U, 10U, 50U, 20U, 50U);
212 CCTest(ConditionCode::CC_EQ, 10U, 60U, 20U, 50U, 20U, 50U, 20U, 50U);
213 CCTest(ConditionCode::CC_NE, 10U, 60U, 20U, 50U, 10U, 60U, 20U, 50U);
214
215 // case 4
216 CCTest(ConditionCode::CC_GT, 20U, 60U, 10U, 50U, 20U, 60U, 10U, 50U);
217 CCTest(ConditionCode::CC_A, 20U, 60U, 10U, 50U, 20U, 60U, 10U, 50U);
218 CCTest(ConditionCode::CC_GE, 20U, 60U, 10U, 50U, 20U, 60U, 10U, 50U);
219 CCTest(ConditionCode::CC_AE, 20U, 60U, 10U, 50U, 20U, 60U, 10U, 50U);
220 CCTest(ConditionCode::CC_LT, 20U, 60U, 10U, 50U, 20U, 49U, 21U, 50U);
221 CCTest(ConditionCode::CC_B, 20U, 60U, 10U, 50U, 20U, 49U, 21U, 50U);
222 CCTest(ConditionCode::CC_LE, 20U, 60U, 10U, 50U, 20U, 50U, 20U, 50U);
223 CCTest(ConditionCode::CC_BE, 20U, 60U, 10U, 50U, 20U, 50U, 20U, 50U);
224 CCTest(ConditionCode::CC_EQ, 20U, 60U, 10U, 50U, 20U, 50U, 20U, 50U);
225 CCTest(ConditionCode::CC_NE, 20U, 60U, 10U, 50U, 20U, 60U, 10U, 50U);
226
227 // case 5
228 CCTest(ConditionCode::CC_GT, 50U, 60U, 10U, 20U, 50U, 60U, 10U, 20U);
229 CCTest(ConditionCode::CC_A, 50U, 60U, 10U, 20U, 50U, 60U, 10U, 20U);
230 CCTest(ConditionCode::CC_GE, 50U, 60U, 10U, 20U, 50U, 60U, 10U, 20U);
231 CCTest(ConditionCode::CC_AE, 50U, 60U, 10U, 20U, 50U, 60U, 10U, 20U);
232 CCTest(ConditionCode::CC_LT, 50U, 60U, 10U, 20U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
233 CCTest(ConditionCode::CC_B, 50U, 60U, 10U, 20U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
234 CCTest(ConditionCode::CC_LE, 50U, 60U, 10U, 20U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
235 CCTest(ConditionCode::CC_BE, 50U, 60U, 10U, 20U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
236 CCTest(ConditionCode::CC_EQ, 50U, 60U, 10U, 20U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
237 CCTest(ConditionCode::CC_NE, 50U, 60U, 10U, 20U, 50U, 60U, 10U, 20U);
238
239 // case 6
240 CCTest(ConditionCode::CC_GT, 20U, 50U, 10U, 60U, 20U, 50U, 10U, 49U);
241 CCTest(ConditionCode::CC_A, 20U, 50U, 10U, 60U, 20U, 50U, 10U, 49U);
242 CCTest(ConditionCode::CC_GE, 20U, 50U, 10U, 60U, 20U, 50U, 10U, 50U);
243 CCTest(ConditionCode::CC_AE, 20U, 50U, 10U, 60U, 20U, 50U, 10U, 50U);
244 CCTest(ConditionCode::CC_LT, 20U, 50U, 10U, 60U, 20U, 50U, 21U, 60U);
245 CCTest(ConditionCode::CC_B, 20U, 50U, 10U, 60U, 20U, 50U, 21U, 60U);
246 CCTest(ConditionCode::CC_LE, 20U, 50U, 10U, 60U, 20U, 50U, 20U, 60U);
247 CCTest(ConditionCode::CC_BE, 20U, 50U, 10U, 60U, 20U, 50U, 20U, 60U);
248 CCTest(ConditionCode::CC_EQ, 20U, 50U, 10U, 60U, 20U, 50U, 20U, 50U);
249 CCTest(ConditionCode::CC_NE, 20U, 50U, 10U, 60U, 20U, 50U, 10U, 60U);
250 }
251
TEST_F(BoundsAnalysisTest,IntervalCollisions)252 TEST_F(BoundsAnalysisTest, IntervalCollisions)
253 {
254 // Bounds collision
255 CCTest(ConditionCode::CC_GT, -10L, -5L, -5L, 0U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
256 CCTest(ConditionCode::CC_LT, -5L, 0U, -10L, -5L, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
257 // Single value interval collision
258 CCTest(ConditionCode::CC_GT, 0U, 20U, 20U, 20U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
259 CCTest(ConditionCode::CC_LT, 0U, 20U, 0U, 0U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
260 CCTest(ConditionCode::CC_GT, 16U, 16U, 16U, 32U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
261 CCTest(ConditionCode::CC_LT, 32U, 32U, 16U, 32U, INT64_MIN, INT64_MAX, INT64_MIN, INT64_MAX);
262 }
263
TEST_F(BoundsAnalysisTest,UnionTest)264 TEST_F(BoundsAnalysisTest, UnionTest)
265 {
266 ArenaVector<BoundsRange> ranges(GetGraph()->GetAllocator()->Adapter());
267 ranges.emplace_back(BoundsRange(-10L, 100U));
268 ranges.emplace_back(BoundsRange(-20L, 15U));
269 auto range = BoundsRange::Union(ranges);
270 ASSERT_EQ(range.GetLeft(), -20L);
271 ASSERT_EQ(range.GetRight(), 100U);
272 ranges.clear();
273
274 ranges.emplace_back(BoundsRange(INT64_MIN, -10L));
275 ranges.emplace_back(BoundsRange(10U, INT64_MAX));
276 range = BoundsRange::Union(ranges);
277 ASSERT_EQ(range.GetLeft(), INT64_MIN);
278 ASSERT_EQ(range.GetRight(), INT64_MAX);
279 }
280
TEST_F(BoundsAnalysisTest,TypeFitting)281 TEST_F(BoundsAnalysisTest, TypeFitting)
282 {
283 GRAPH(GetGraph())
284 {
285 PARAMETER(0U, 0U).u16();
286 PARAMETER(1U, 1U).s64();
287 PARAMETER(2U, 2U).u32();
288 CONSTANT(3U, 0x23U).s64();
289 CONSTANT(4U, 0x30U).s64();
290 BASIC_BLOCK(2U, 3U, 4U)
291 {
292 // v0 -- ANYTHING
293 // v1 -- ANYTHING
294 // v2 -- ANYTHING
295 INST(5U, Opcode::Compare).b().CC(CC_GT).Inputs(1U, 3U);
296 INST(6U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(5U);
297 }
298 BASIC_BLOCK(4U, 3U, 5U)
299 {
300 // v0 -- ANYTHING
301 // v1 <= 0x23
302 // v2 -- ANYTHING
303 INST(8U, Opcode::Compare).b().CC(CC_GT).Inputs(2U, 4U);
304 INST(9U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(8U);
305 }
306 BASIC_BLOCK(5U, -1L)
307 {
308 // v0 -- ANYTHING
309 // v1 <= 0x23
310 // v2 <= 0x30
311 INST(11U, Opcode::Return).u16().Inputs(0U);
312 }
313 BASIC_BLOCK(3U, -1L)
314 {
315 // v0 -- ANYTHING
316 // v1 -- ANYTHING
317 // v2 -- ANYTHING
318 INST(14U, Opcode::ReturnI).u16().Imm(0x23U);
319 }
320 }
321 auto rinfo = GetGraph()->GetBoundsRangeInfo();
322 BoundsRange range;
323
324 // BB2
325 range = rinfo->FindBoundsRange(&BB(2U), &INS(0U));
326 EXPECT_EQ(range.GetLeft(), 0U);
327 EXPECT_EQ(range.GetRight(), UINT16_MAX);
328
329 range = rinfo->FindBoundsRange(&BB(2U), &INS(1U));
330 EXPECT_EQ(range.GetLeft(), INT64_MIN);
331 EXPECT_EQ(range.GetRight(), INT64_MAX);
332
333 range = rinfo->FindBoundsRange(&BB(2U), &INS(2U));
334 EXPECT_EQ(range.GetLeft(), 0U);
335 EXPECT_EQ(range.GetRight(), UINT32_MAX);
336
337 // BB4
338 range = rinfo->FindBoundsRange(&BB(2U), &INS(0U));
339 EXPECT_EQ(range.GetLeft(), 0U);
340 EXPECT_EQ(range.GetRight(), UINT16_MAX);
341
342 range = rinfo->FindBoundsRange(&BB(4U), &INS(1U));
343 EXPECT_EQ(range.GetLeft(), INT64_MIN);
344 EXPECT_EQ(range.GetRight(), 0x23U);
345
346 range = rinfo->FindBoundsRange(&BB(2U), &INS(2U));
347 EXPECT_EQ(range.GetLeft(), 0U);
348 EXPECT_EQ(range.GetRight(), UINT32_MAX);
349
350 // BB5
351 range = rinfo->FindBoundsRange(&BB(2U), &INS(0U));
352 EXPECT_EQ(range.GetLeft(), 0U);
353 EXPECT_EQ(range.GetRight(), UINT16_MAX);
354
355 range = rinfo->FindBoundsRange(&BB(4U), &INS(1U));
356 EXPECT_EQ(range.GetLeft(), INT64_MIN);
357 EXPECT_EQ(range.GetRight(), 0x23U);
358
359 range = rinfo->FindBoundsRange(&BB(5U), &INS(2U));
360 EXPECT_EQ(range.GetLeft(), 0U);
361 EXPECT_EQ(range.GetRight(), 0x30U);
362
363 // BB3
364 range = rinfo->FindBoundsRange(&BB(2U), &INS(0U));
365 EXPECT_EQ(range.GetLeft(), 0U);
366 EXPECT_EQ(range.GetRight(), UINT16_MAX);
367
368 range = rinfo->FindBoundsRange(&BB(2U), &INS(1U));
369 EXPECT_EQ(range.GetLeft(), INT64_MIN);
370 EXPECT_EQ(range.GetRight(), INT64_MAX);
371
372 range = rinfo->FindBoundsRange(&BB(2U), &INS(2U));
373 EXPECT_EQ(range.GetLeft(), 0U);
374 EXPECT_EQ(range.GetRight(), UINT32_MAX);
375 }
376
TEST_F(BoundsAnalysisTest,NullCompare)377 TEST_F(BoundsAnalysisTest, NullCompare)
378 {
379 GRAPH(GetGraph())
380 {
381 PARAMETER(0U, 0U).ref();
382 CONSTANT(3U, nullptr);
383 BASIC_BLOCK(2U, 3U, 4U)
384 {
385 INST(4U, Opcode::Compare).b().CC(CC_NE).Inputs(3U, 0U);
386 INST(6U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(4U);
387 }
388 BASIC_BLOCK(3U, -1L)
389 {
390 INST(7U, Opcode::SaveState).Inputs(0U, 4U).SrcVregs({2U, 3U});
391 INST(8U, Opcode::NullCheck).ref().Inputs(0U, 7U);
392 INST(9U, Opcode::LoadObject).s64().Inputs(8U).TypeId(243U);
393 INST(10U, Opcode::Return).s64().Inputs(9U);
394 }
395 BASIC_BLOCK(4U, -1L)
396 {
397 INST(13U, Opcode::ReturnI).s64().Imm(0x14U);
398 }
399 }
400 auto rinfo = GetGraph()->GetBoundsRangeInfo();
401 EXPECT_EQ(rinfo->FindBoundsRange(&BB(2U), &INS(0U)).GetLeft(), 0U);
402 EXPECT_EQ(rinfo->FindBoundsRange(&BB(2U), &INS(0U)).GetRight(), BoundsRange::GetMax(INS(0U).GetType()));
403
404 EXPECT_NE(rinfo->FindBoundsRange(&BB(3U), &INS(0U)).GetLeft(), 0U);
405 EXPECT_EQ(rinfo->FindBoundsRange(&BB(3U), &INS(0U)).GetRight(), BoundsRange::GetMax(INS(0U).GetType()));
406
407 EXPECT_EQ(rinfo->FindBoundsRange(&BB(4U), &INS(0U)).GetLeft(), 0U);
408 EXPECT_EQ(rinfo->FindBoundsRange(&BB(4U), &INS(0U)).GetRight(), 0U);
409 }
410
TEST_F(BoundsAnalysisTest,InitMoreThenTest)411 TEST_F(BoundsAnalysisTest, InitMoreThenTest)
412 {
413 // For (int i = 10, i < 0, i++) {}
414 // this loop is counable, but init > test value.
415 GRAPH(GetGraph())
416 {
417 CONSTANT(0U, 10U);
418 CONSTANT(1U, 1U);
419 CONSTANT(2U, 0U);
420 BASIC_BLOCK(2U, 3U, 5U)
421 {
422 INST(5U, Opcode::Compare).SrcType(DataType::INT32).CC(CC_LT).b().Inputs(0U, 2U);
423 INST(6U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(5U);
424 }
425 BASIC_BLOCK(3U, 3U, 5U)
426 {
427 INST(4U, Opcode::Phi).s32().Inputs(0U, 10U);
428
429 INST(10U, Opcode::Add).s32().Inputs(4U, 1U);
430 INST(13U, Opcode::Compare).CC(CC_LT).b().Inputs(10U, 2U);
431 INST(14U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(13U);
432 }
433 BASIC_BLOCK(5U, 1U)
434 {
435 INST(12U, Opcode::ReturnVoid).v0id();
436 }
437 }
438 auto rinfo = GetGraph()->GetBoundsRangeInfo();
439 auto range = rinfo->FindBoundsRange(&BB(3U), &INS(4U));
440 EXPECT_EQ(range.GetLeft(), INT32_MIN);
441 EXPECT_EQ(range.GetRight(), INT32_MAX);
442 }
443
TEST_F(BoundsAnalysisTest,ModTest)444 TEST_F(BoundsAnalysisTest, ModTest)
445 {
446 auto res = BoundsRange(0U, 10U).Mod(BoundsRange(0U, 2U));
447 EXPECT_EQ(res.GetLeft(), 0U);
448 EXPECT_EQ(res.GetRight(), 1U);
449
450 res = BoundsRange(0U, 10U).Mod(BoundsRange(0U));
451 EXPECT_EQ(res.GetLeft(), INT64_MIN);
452 EXPECT_EQ(res.GetRight(), INT64_MAX);
453
454 // It's correct situation, when right value is 0, and left value isn't 0.
455 res = BoundsRange(-179L, -179L).Mod(BoundsRange(INT64_MIN, 0U));
456 EXPECT_EQ(res.GetLeft(), -179L);
457 EXPECT_EQ(res.GetRight(), 0U);
458
459 res = BoundsRange(5U, 10U).Mod(BoundsRange(-3L));
460 EXPECT_EQ(res.GetLeft(), 0U);
461 EXPECT_EQ(res.GetRight(), 2U);
462
463 res = BoundsRange(-10L, -5L).Mod(BoundsRange(-3L));
464 EXPECT_EQ(res.GetLeft(), -2L);
465 EXPECT_EQ(res.GetRight(), 0U);
466
467 res = BoundsRange(-10L, 10U).Mod(BoundsRange(3U));
468 EXPECT_EQ(res.GetLeft(), -2L);
469 EXPECT_EQ(res.GetRight(), 2U);
470
471 res = BoundsRange(-3L, 3U).Mod(BoundsRange(-10L, 10U));
472 EXPECT_EQ(res.GetLeft(), -3L);
473 EXPECT_EQ(res.GetRight(), 3U);
474 }
475
TEST_F(BoundsAnalysisTest,LoopWithBigStep)476 TEST_F(BoundsAnalysisTest, LoopWithBigStep)
477 {
478 // For (int i = 0, i < 5, i += 10) {}
479 // this loop is countable, and init + step > test value.
480 GRAPH(GetGraph())
481 {
482 CONSTANT(0U, 0U);
483 CONSTANT(1U, 5U);
484 CONSTANT(2U, 10U);
485 BASIC_BLOCK(2U, 3U, 5U)
486 {
487 INST(5U, Opcode::Compare).SrcType(DataType::INT32).CC(CC_LT).b().Inputs(0U, 1U);
488 INST(6U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(5U);
489 }
490 BASIC_BLOCK(3U, 3U, 5U)
491 {
492 INST(4U, Opcode::Phi).s32().Inputs(0U, 10U);
493
494 INST(10U, Opcode::Add).s32().Inputs(4U, 2U);
495 INST(13U, Opcode::Compare).CC(CC_LT).b().Inputs(10U, 1U);
496 INST(14U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(13U);
497 }
498 BASIC_BLOCK(5U, 1U)
499 {
500 INST(12U, Opcode::ReturnVoid).v0id();
501 }
502 }
503 auto rinfo = GetGraph()->GetBoundsRangeInfo();
504 auto range = rinfo->FindBoundsRange(&BB(3U), &INS(4U));
505 EXPECT_EQ(range.GetLeft(), 0U);
506 EXPECT_EQ(range.GetRight(), 4U);
507 }
508
TEST_F(BoundsAnalysisTest,LoopWithBigStep2)509 TEST_F(BoundsAnalysisTest, LoopWithBigStep2)
510 {
511 // For (int i = 1, i < 6, i += 2) {}
512 GRAPH(GetGraph())
513 {
514 CONSTANT(0U, 0U);
515 CONSTANT(1U, 6U);
516 CONSTANT(2U, 2U);
517 BASIC_BLOCK(2U, 3U, 5U)
518 {
519 INST(5U, Opcode::Compare).SrcType(DataType::INT32).CC(CC_LT).b().Inputs(0U, 1U);
520 INST(6U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(5U);
521 }
522 BASIC_BLOCK(3U, 3U, 5U)
523 {
524 INST(4U, Opcode::Phi).s32().Inputs(0U, 10U);
525
526 INST(10U, Opcode::Add).s32().Inputs(4U, 2U);
527 INST(13U, Opcode::Compare).CC(CC_LT).b().Inputs(10U, 1U);
528 INST(14U, Opcode::IfImm).SrcType(DataType::BOOL).CC(CC_NE).Imm(0U).Inputs(13U);
529 }
530 BASIC_BLOCK(5U, 1U)
531 {
532 INST(12U, Opcode::ReturnVoid).v0id();
533 }
534 }
535 auto rinfo = GetGraph()->GetBoundsRangeInfo();
536 auto range = rinfo->FindBoundsRange(&BB(3U), &INS(4U));
537 EXPECT_EQ(range.GetLeft(), 0U);
538 // Check that right bound is (upper - 1)
539 EXPECT_EQ(range.GetRight(), 5U);
540 }
541
TEST_F(BoundsAnalysisTest,ShrTest)542 TEST_F(BoundsAnalysisTest, ShrTest)
543 {
544 auto r1 = BoundsRange(2U);
545 auto max = BoundsRange();
546 auto r2 = BoundsRange(4U, 8U);
547 auto neg = BoundsRange(-1L);
548
549 EXPECT_EQ(r2.Shr(r2), max);
550 EXPECT_EQ(r2.Shr(neg), max);
551 EXPECT_EQ(r2.Shr(r1), BoundsRange(1U, 2U));
552
553 EXPECT_EQ(BoundsRange(-1L).Shr(BoundsRange(4U)), BoundsRange(0x0FFFFFFFFFFFFFFFU));
554 EXPECT_EQ(BoundsRange(-1L, 16U).Shr(BoundsRange(4U)), BoundsRange(0U, 0x0FFFFFFFFFFFFFFFU));
555 EXPECT_EQ(BoundsRange(9U, 15U).Shr(BoundsRange(2U)), BoundsRange(2U, 3U));
556 EXPECT_EQ(BoundsRange(-15L, -9L).Shr(BoundsRange(2U)), BoundsRange(0x3FFFFFFFFFFFFFFCU, 0x3FFFFFFFFFFFFFFDU));
557 EXPECT_EQ(BoundsRange(-100L, 100U).Shr(BoundsRange(4U)), BoundsRange(0U, 0x0FFFFFFFFFFFFFFFU));
558 }
559
TEST_F(BoundsAnalysisTest,AShrTest)560 TEST_F(BoundsAnalysisTest, AShrTest)
561 {
562 auto r1 = BoundsRange(2U);
563 auto max = BoundsRange();
564 auto r2 = BoundsRange(4U, 8U);
565 auto neg = BoundsRange(-1L);
566
567 EXPECT_EQ(r2.AShr(r2), max);
568 EXPECT_EQ(r2.AShr(neg), max);
569 EXPECT_EQ(r2.AShr(r1), BoundsRange(1U, 2U));
570
571 EXPECT_EQ(BoundsRange(-1L).AShr(BoundsRange(4U)), BoundsRange(-1L));
572 EXPECT_EQ(BoundsRange(-1L, 16U).AShr(BoundsRange(4U)), BoundsRange(-1L, 1U));
573 }
574
TEST_F(BoundsAnalysisTest,ShlTest)575 TEST_F(BoundsAnalysisTest, ShlTest)
576 {
577 auto max = BoundsRange();
578 auto r = BoundsRange(4U, 8U);
579 auto neg = BoundsRange(-1L);
580
581 EXPECT_EQ(r.Shl(r), max);
582 EXPECT_EQ(r.Shl(neg), max);
583
584 EXPECT_EQ(r.Shl(BoundsRange(2U)), BoundsRange(16U, 32U));
585 EXPECT_EQ(BoundsRange(-1L).Shl(BoundsRange(4U)), BoundsRange(0xFFFFFFFFFFFFFFF0U));
586 EXPECT_EQ(BoundsRange(-1L, 16U).Shl(BoundsRange(4U)), BoundsRange(0xFFFFFFFFFFFFFFF0U, 256U));
587 EXPECT_EQ(BoundsRange(16U, 0x0FFFFFFFFFFFFFFFU).Shl(BoundsRange(4U)), BoundsRange());
588 }
589
TEST_F(BoundsAnalysisTest,AShrDivTest)590 TEST_F(BoundsAnalysisTest, AShrDivTest)
591 {
592 GRAPH(GetGraph())
593 {
594 PARAMETER(0U, 0U).s32();
595 CONSTANT(1U, 4U);
596 BASIC_BLOCK(2U, -1L)
597 {
598 INST(2U, Opcode::Div).s32().Inputs(0U, 1U);
599 INST(3U, Opcode::Return).s32().Inputs(2U);
600 }
601 }
602
603 ASSERT_TRUE(GetGraph()->RunPass<Peepholes>());
604 ASSERT_TRUE(GetGraph()->RunPass<Cleanup>());
605
606 auto bb = &BB(2U);
607
608 auto graph = CreateEmptyGraph();
609 GRAPH(graph)
610 {
611 PARAMETER(0U, 0U).s32();
612 CONSTANT(1U, 31U);
613 CONSTANT(5U, 30U); // type size - log2(4)
614 CONSTANT(8U, 2U); // log2(4)
615 BASIC_BLOCK(2U, -1L)
616 {
617 INST(2U, Opcode::AShr).s32().Inputs(0U, 1U);
618 INST(4U, Opcode::Shr).s32().Inputs(2U, 5U);
619 INST(6U, Opcode::Add).s32().Inputs(4U, 0U);
620 INST(7U, Opcode::AShr).s32().Inputs(6U, 8U);
621 INST(3U, Opcode::Return).s32().Inputs(7U);
622 }
623 }
624 ASSERT_TRUE(GraphComparator().Compare(GetGraph(), graph));
625
626 auto bri = GetGraph()->GetBoundsRangeInfo();
627 auto range = bri->FindBoundsRange(bb, bb->GetLastInst()->GetInput(0U).GetInst());
628 ASSERT_EQ(range, BoundsRange(INT32_MIN / 4L, INT32_MAX / 4L));
629 }
630
TEST_F(BoundsAnalysisTest,AndTest)631 TEST_F(BoundsAnalysisTest, AndTest)
632 {
633 EXPECT_EQ(BoundsRange().And(BoundsRange(1U, 2U)), BoundsRange());
634 EXPECT_EQ(BoundsRange().And(BoundsRange(0x2U)), BoundsRange(0U, 0x2U));
635 EXPECT_EQ(BoundsRange().And(BoundsRange(0x3U)), BoundsRange(0U, 0x3U));
636 EXPECT_EQ(BoundsRange().And(BoundsRange(-1L)), BoundsRange());
637 EXPECT_EQ(BoundsRange().And(BoundsRange(0x8000000000000000U)), BoundsRange());
638 }
639 // NOLINTEND(readability-magic-numbers)
640
641 } // namespace panda::compiler
642