?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[docs] Fix build-docs.sh
[llvm-project.git] / llvm / unittests / Analysis / ValueTrackingTest.cpp
blob05e6a099c3a5b2f61240af01255f9067fd71cf1f
1 //===- ValueTrackingTest.cpp - ValueTracking tests ------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/Analysis/ValueTracking.h"
10 #include "llvm/Analysis/AssumptionCache.h"
11 #include "llvm/AsmParser/Parser.h"
12 #include "llvm/IR/ConstantRange.h"
13 #include "llvm/IR/Dominators.h"
14 #include "llvm/IR/Function.h"
15 #include "llvm/IR/IRBuilder.h"
16 #include "llvm/IR/InstIterator.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/LLVMContext.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include "llvm/Support/KnownBits.h"
22 #include "llvm/Support/SourceMgr.h"
23 #include "llvm/Transforms/Utils/Local.h"
24 #include "gtest/gtest.h"
25
26 using namespace llvm;
27
28 namespace {
29
30 static Instruction *findInstructionByNameOrNull(Function *F, StringRef Name) {
31 for (Instruction &I : instructions(F))
32 if (I.getName() == Name)
33 return &I;
34
35 return nullptr;
36 }
37
38 static Instruction &findInstructionByName(Function *F, StringRef Name) {
39 auto *I = findInstructionByNameOrNull(F, Name);
40 if (I)
41 return *I;
42
43 llvm_unreachable("Expected value not found");
44 }
45
46 class ValueTrackingTest : public testing::Test {
47 protected:
48 std::unique_ptr<Module> parseModule(StringRef Assembly) {
49 SMDiagnostic Error;
50 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
51
52 std::string errMsg;
53 raw_string_ostream os(errMsg);
54 Error.print("", os);
55 EXPECT_TRUE(M) << os.str();
56
57 return M;
58 }
59
60 void parseAssembly(StringRef Assembly) {
61 M = parseModule(Assembly);
62 ASSERT_TRUE(M);
63
64 F = M->getFunction("test");
65 ASSERT_TRUE(F) << "Test must have a function @test";
66 if (!F)
67 return;
68
69 A = findInstructionByNameOrNull(F, "A");
70 ASSERT_TRUE(A) << "@test must have an instruction %A";
71 A2 = findInstructionByNameOrNull(F, "A2");
72 A3 = findInstructionByNameOrNull(F, "A3");
73 A4 = findInstructionByNameOrNull(F, "A4");
74
75 CxtI = findInstructionByNameOrNull(F, "CxtI");
76 CxtI2 = findInstructionByNameOrNull(F, "CxtI2");
77 CxtI3 = findInstructionByNameOrNull(F, "CxtI3");
78 }
79
80 LLVMContext Context;
81 std::unique_ptr<Module> M;
82 Function *F = nullptr;
83 Instruction *A = nullptr;
84 // Instructions (optional)
85 Instruction *A2 = nullptr, *A3 = nullptr, *A4 = nullptr;
86
87 // Context instructions (optional)
88 Instruction *CxtI = nullptr, *CxtI2 = nullptr, *CxtI3 = nullptr;
89 };
90
91 class MatchSelectPatternTest : public ValueTrackingTest {
92 protected:
93 void expectPattern(const SelectPatternResult &P) {
94 Value *LHS, *RHS;
95 Instruction::CastOps CastOp;
96 SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp);
97 EXPECT_EQ(P.Flavor, R.Flavor);
98 EXPECT_EQ(P.NaNBehavior, R.NaNBehavior);
99 EXPECT_EQ(P.Ordered, R.Ordered);
100 }
101 };
102
103 class ComputeKnownBitsTest : public ValueTrackingTest {
104 protected:
105 void expectKnownBits(uint64_t Zero, uint64_t One) {
106 auto Known = computeKnownBits(A, M->getDataLayout());
107 ASSERT_FALSE(Known.hasConflict());
108 EXPECT_EQ(Known.One.getZExtValue(), One);
109 EXPECT_EQ(Known.Zero.getZExtValue(), Zero);
110 }
111 };
112
113 }
114
115 TEST_F(MatchSelectPatternTest, SimpleFMin) {
116 parseAssembly(
117 "define float @test(float %a) {\n"
118 " %1 = fcmp ult float %a, 5.0\n"
119 " %A = select i1 %1, float %a, float 5.0\n"
120 " ret float %A\n"
121 "}\n");
122 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
123 }
124
125 TEST_F(MatchSelectPatternTest, SimpleFMax) {
126 parseAssembly(
127 "define float @test(float %a) {\n"
128 " %1 = fcmp ogt float %a, 5.0\n"
129 " %A = select i1 %1, float %a, float 5.0\n"
130 " ret float %A\n"
131 "}\n");
132 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
133 }
134
135 TEST_F(MatchSelectPatternTest, SwappedFMax) {
136 parseAssembly(
137 "define float @test(float %a) {\n"
138 " %1 = fcmp olt float 5.0, %a\n"
139 " %A = select i1 %1, float %a, float 5.0\n"
140 " ret float %A\n"
141 "}\n");
142 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
143 }
144
145 TEST_F(MatchSelectPatternTest, SwappedFMax2) {
146 parseAssembly(
147 "define float @test(float %a) {\n"
148 " %1 = fcmp olt float %a, 5.0\n"
149 " %A = select i1 %1, float 5.0, float %a\n"
150 " ret float %A\n"
151 "}\n");
152 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
153 }
154
155 TEST_F(MatchSelectPatternTest, SwappedFMax3) {
156 parseAssembly(
157 "define float @test(float %a) {\n"
158 " %1 = fcmp ult float %a, 5.0\n"
159 " %A = select i1 %1, float 5.0, float %a\n"
160 " ret float %A\n"
161 "}\n");
162 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
163 }
164
165 TEST_F(MatchSelectPatternTest, FastFMin) {
166 parseAssembly(
167 "define float @test(float %a) {\n"
168 " %1 = fcmp nnan olt float %a, 5.0\n"
169 " %A = select i1 %1, float %a, float 5.0\n"
170 " ret float %A\n"
171 "}\n");
172 expectPattern({SPF_FMINNUM, SPNB_RETURNS_ANY, false});
173 }
174
175 TEST_F(MatchSelectPatternTest, FMinConstantZero) {
176 parseAssembly(
177 "define float @test(float %a) {\n"
178 " %1 = fcmp ole float %a, 0.0\n"
179 " %A = select i1 %1, float %a, float 0.0\n"
180 " ret float %A\n"
181 "}\n");
182 // This shouldn't be matched, as %a could be -0.0.
183 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
184 }
185
186 TEST_F(MatchSelectPatternTest, FMinConstantZeroNsz) {
187 parseAssembly(
188 "define float @test(float %a) {\n"
189 " %1 = fcmp nsz ole float %a, 0.0\n"
190 " %A = select i1 %1, float %a, float 0.0\n"
191 " ret float %A\n"
192 "}\n");
193 // But this should be, because we've ignored signed zeroes.
194 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
195 }
196
197 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero1) {
198 parseAssembly(
199 "define float @test(float %a) {\n"
200 " %1 = fcmp olt float -0.0, %a\n"
201 " %A = select i1 %1, float 0.0, float %a\n"
202 " ret float %A\n"
203 "}\n");
204 // The sign of zero doesn't matter in fcmp.
205 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
206 }
207
208 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero2) {
209 parseAssembly(
210 "define float @test(float %a) {\n"
211 " %1 = fcmp ogt float %a, -0.0\n"
212 " %A = select i1 %1, float 0.0, float %a\n"
213 " ret float %A\n"
214 "}\n");
215 // The sign of zero doesn't matter in fcmp.
216 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
217 }
218
219 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero3) {
220 parseAssembly(
221 "define float @test(float %a) {\n"
222 " %1 = fcmp olt float 0.0, %a\n"
223 " %A = select i1 %1, float -0.0, float %a\n"
224 " ret float %A\n"
225 "}\n");
226 // The sign of zero doesn't matter in fcmp.
227 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
228 }
229
230 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero4) {
231 parseAssembly(
232 "define float @test(float %a) {\n"
233 " %1 = fcmp ogt float %a, 0.0\n"
234 " %A = select i1 %1, float -0.0, float %a\n"
235 " ret float %A\n"
236 "}\n");
237 // The sign of zero doesn't matter in fcmp.
238 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
239 }
240
241 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero5) {
242 parseAssembly(
243 "define float @test(float %a) {\n"
244 " %1 = fcmp ogt float -0.0, %a\n"
245 " %A = select i1 %1, float %a, float 0.0\n"
246 " ret float %A\n"
247 "}\n");
248 // The sign of zero doesn't matter in fcmp.
249 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
250 }
251
252 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero6) {
253 parseAssembly(
254 "define float @test(float %a) {\n"
255 " %1 = fcmp olt float %a, -0.0\n"
256 " %A = select i1 %1, float %a, float 0.0\n"
257 " ret float %A\n"
258 "}\n");
259 // The sign of zero doesn't matter in fcmp.
260 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
261 }
262
263 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero7) {
264 parseAssembly(
265 "define float @test(float %a) {\n"
266 " %1 = fcmp ogt float 0.0, %a\n"
267 " %A = select i1 %1, float %a, float -0.0\n"
268 " ret float %A\n"
269 "}\n");
270 // The sign of zero doesn't matter in fcmp.
271 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
272 }
273
274 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero8) {
275 parseAssembly(
276 "define float @test(float %a) {\n"
277 " %1 = fcmp olt float %a, 0.0\n"
278 " %A = select i1 %1, float %a, float -0.0\n"
279 " ret float %A\n"
280 "}\n");
281 // The sign of zero doesn't matter in fcmp.
282 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
283 }
284
285 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero1) {
286 parseAssembly(
287 "define float @test(float %a) {\n"
288 " %1 = fcmp ogt float -0.0, %a\n"
289 " %A = select i1 %1, float 0.0, float %a\n"
290 " ret float %A\n"
291 "}\n");
292 // The sign of zero doesn't matter in fcmp.
293 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
294 }
295
296 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero2) {
297 parseAssembly(
298 "define float @test(float %a) {\n"
299 " %1 = fcmp olt float %a, -0.0\n"
300 " %A = select i1 %1, float 0.0, float %a\n"
301 " ret float %A\n"
302 "}\n");
303 // The sign of zero doesn't matter in fcmp.
304 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
305 }
306
307 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero3) {
308 parseAssembly(
309 "define float @test(float %a) {\n"
310 " %1 = fcmp ogt float 0.0, %a\n"
311 " %A = select i1 %1, float -0.0, float %a\n"
312 " ret float %A\n"
313 "}\n");
314 // The sign of zero doesn't matter in fcmp.
315 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
316 }
317
318 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero4) {
319 parseAssembly(
320 "define float @test(float %a) {\n"
321 " %1 = fcmp olt float %a, 0.0\n"
322 " %A = select i1 %1, float -0.0, float %a\n"
323 " ret float %A\n"
324 "}\n");
325 // The sign of zero doesn't matter in fcmp.
326 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
327 }
328
329 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero5) {
330 parseAssembly(
331 "define float @test(float %a) {\n"
332 " %1 = fcmp olt float -0.0, %a\n"
333 " %A = select i1 %1, float %a, float 0.0\n"
334 " ret float %A\n"
335 "}\n");
336 // The sign of zero doesn't matter in fcmp.
337 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
338 }
339
340 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero6) {
341 parseAssembly(
342 "define float @test(float %a) {\n"
343 " %1 = fcmp ogt float %a, -0.0\n"
344 " %A = select i1 %1, float %a, float 0.0\n"
345 " ret float %A\n"
346 "}\n");
347 // The sign of zero doesn't matter in fcmp.
348 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
349 }
350
351 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero7) {
352 parseAssembly(
353 "define float @test(float %a) {\n"
354 " %1 = fcmp olt float 0.0, %a\n"
355 " %A = select i1 %1, float %a, float -0.0\n"
356 " ret float %A\n"
357 "}\n");
358 // The sign of zero doesn't matter in fcmp.
359 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
360 }
361
362 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero8) {
363 parseAssembly(
364 "define float @test(float %a) {\n"
365 " %1 = fcmp ogt float %a, 0.0\n"
366 " %A = select i1 %1, float %a, float -0.0\n"
367 " ret float %A\n"
368 "}\n");
369 // The sign of zero doesn't matter in fcmp.
370 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
371 }
372
373 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZeroVecUndef) {
374 parseAssembly(
375 "define <2 x float> @test(<2 x float> %a) {\n"
376 " %1 = fcmp ogt <2 x float> %a, <float -0.0, float -0.0>\n"
377 " %A = select <2 x i1> %1, <2 x float> <float undef, float 0.0>, <2 x float> %a\n"
378 " ret <2 x float> %A\n"
379 "}\n");
380 // An undef in a vector constant can not be back-propagated for this analysis.
381 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
382 }
383
384 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZeroVecUndef) {
385 parseAssembly(
386 "define <2 x float> @test(<2 x float> %a) {\n"
387 " %1 = fcmp ogt <2 x float> %a, zeroinitializer\n"
388 " %A = select <2 x i1> %1, <2 x float> %a, <2 x float> <float -0.0, float undef>\n"
389 " ret <2 x float> %A\n"
390 "}\n");
391 // An undef in a vector constant can not be back-propagated for this analysis.
392 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
393 }
394
395 TEST_F(MatchSelectPatternTest, VectorFMinimum) {
396 parseAssembly(
397 "define <4 x float> @test(<4 x float> %a) {\n"
398 " %1 = fcmp ule <4 x float> %a, \n"
399 " <float 5.0, float 5.0, float 5.0, float 5.0>\n"
400 " %A = select <4 x i1> %1, <4 x float> %a,\n"
401 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n"
402 " ret <4 x float> %A\n"
403 "}\n");
404 // Check that pattern matching works on vectors where each lane has the same
405 // unordered pattern.
406 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
407 }
408
409 TEST_F(MatchSelectPatternTest, VectorFMinOtherOrdered) {
410 parseAssembly(
411 "define <4 x float> @test(<4 x float> %a) {\n"
412 " %1 = fcmp ole <4 x float> %a, \n"
413 " <float 5.0, float 5.0, float 5.0, float 5.0>\n"
414 " %A = select <4 x i1> %1, <4 x float> %a,\n"
415 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n"
416 " ret <4 x float> %A\n"
417 "}\n");
418 // Check that pattern matching works on vectors where each lane has the same
419 // ordered pattern.
420 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
421 }
422
423 TEST_F(MatchSelectPatternTest, VectorNotFMinimum) {
424 parseAssembly(
425 "define <4 x float> @test(<4 x float> %a) {\n"
426 " %1 = fcmp ule <4 x float> %a, \n"
427 " <float 5.0, float 0x7ff8000000000000, float 5.0, float 5.0>\n"
428 " %A = select <4 x i1> %1, <4 x float> %a,\n"
429 " <4 x float> <float 5.0, float 0x7ff8000000000000, float 5.0, float "
430 "5.0>\n"
431 " ret <4 x float> %A\n"
432 "}\n");
433 // The lane that contains a NaN (0x7ff80...) behaves like a
434 // non-NaN-propagating min and the other lines behave like a NaN-propagating
435 // min, so check that neither is returned.
436 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
437 }
438
439 TEST_F(MatchSelectPatternTest, VectorNotFMinZero) {
440 parseAssembly(
441 "define <4 x float> @test(<4 x float> %a) {\n"
442 " %1 = fcmp ule <4 x float> %a, \n"
443 " <float 5.0, float -0.0, float 5.0, float 5.0>\n"
444 " %A = select <4 x i1> %1, <4 x float> %a,\n"
445 " <4 x float> <float 5.0, float 0.0, float 5.0, float 5.0>\n"
446 " ret <4 x float> %A\n"
447 "}\n");
448 // Always selects the second lane of %a if it is positive or negative zero, so
449 // this is stricter than a min.
450 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
451 }
452
453 TEST_F(MatchSelectPatternTest, DoubleCastU) {
454 parseAssembly(
455 "define i32 @test(i8 %a, i8 %b) {\n"
456 " %1 = icmp ult i8 %a, %b\n"
457 " %2 = zext i8 %a to i32\n"
458 " %3 = zext i8 %b to i32\n"
459 " %A = select i1 %1, i32 %2, i32 %3\n"
460 " ret i32 %A\n"
461 "}\n");
462 // We should be able to look through the situation where we cast both operands
463 // to the select.
464 expectPattern({SPF_UMIN, SPNB_NA, false});
465 }
466
467 TEST_F(MatchSelectPatternTest, DoubleCastS) {
468 parseAssembly(
469 "define i32 @test(i8 %a, i8 %b) {\n"
470 " %1 = icmp slt i8 %a, %b\n"
471 " %2 = sext i8 %a to i32\n"
472 " %3 = sext i8 %b to i32\n"
473 " %A = select i1 %1, i32 %2, i32 %3\n"
474 " ret i32 %A\n"
475 "}\n");
476 // We should be able to look through the situation where we cast both operands
477 // to the select.
478 expectPattern({SPF_SMIN, SPNB_NA, false});
479 }
480
481 TEST_F(MatchSelectPatternTest, DoubleCastBad) {
482 parseAssembly(
483 "define i32 @test(i8 %a, i8 %b) {\n"
484 " %1 = icmp ult i8 %a, %b\n"
485 " %2 = zext i8 %a to i32\n"
486 " %3 = sext i8 %b to i32\n"
487 " %A = select i1 %1, i32 %2, i32 %3\n"
488 " ret i32 %A\n"
489 "}\n");
490 // The cast types here aren't the same, so we cannot match an UMIN.
491 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
492 }
493
494 TEST_F(MatchSelectPatternTest, NotNotSMin) {
495 parseAssembly(
496 "define i8 @test(i8 %a, i8 %b) {\n"
497 " %cmp = icmp sgt i8 %a, %b\n"
498 " %an = xor i8 %a, -1\n"
499 " %bn = xor i8 %b, -1\n"
500 " %A = select i1 %cmp, i8 %an, i8 %bn\n"
501 " ret i8 %A\n"
502 "}\n");
503 expectPattern({SPF_SMIN, SPNB_NA, false});
504 }
505
506 TEST_F(MatchSelectPatternTest, NotNotSMinSwap) {
507 parseAssembly(
508 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n"
509 " %cmp = icmp slt <2 x i8> %a, %b\n"
510 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n"
511 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n"
512 " %A = select <2 x i1> %cmp, <2 x i8> %bn, <2 x i8> %an\n"
513 " ret <2 x i8> %A\n"
514 "}\n");
515 expectPattern({SPF_SMIN, SPNB_NA, false});
516 }
517
518 TEST_F(MatchSelectPatternTest, NotNotSMax) {
519 parseAssembly(
520 "define i8 @test(i8 %a, i8 %b) {\n"
521 " %cmp = icmp slt i8 %a, %b\n"
522 " %an = xor i8 %a, -1\n"
523 " %bn = xor i8 %b, -1\n"
524 " %A = select i1 %cmp, i8 %an, i8 %bn\n"
525 " ret i8 %A\n"
526 "}\n");
527 expectPattern({SPF_SMAX, SPNB_NA, false});
528 }
529
530 TEST_F(MatchSelectPatternTest, NotNotSMaxSwap) {
531 parseAssembly(
532 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n"
533 " %cmp = icmp sgt <2 x i8> %a, %b\n"
534 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n"
535 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n"
536 " %A = select <2 x i1> %cmp, <2 x i8> %bn, <2 x i8> %an\n"
537 " ret <2 x i8> %A\n"
538 "}\n");
539 expectPattern({SPF_SMAX, SPNB_NA, false});
540 }
541
542 TEST_F(MatchSelectPatternTest, NotNotUMin) {
543 parseAssembly(
544 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n"
545 " %cmp = icmp ugt <2 x i8> %a, %b\n"
546 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n"
547 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n"
548 " %A = select <2 x i1> %cmp, <2 x i8> %an, <2 x i8> %bn\n"
549 " ret <2 x i8> %A\n"
550 "}\n");
551 expectPattern({SPF_UMIN, SPNB_NA, false});
552 }
553
554 TEST_F(MatchSelectPatternTest, NotNotUMinSwap) {
555 parseAssembly(
556 "define i8 @test(i8 %a, i8 %b) {\n"
557 " %cmp = icmp ult i8 %a, %b\n"
558 " %an = xor i8 %a, -1\n"
559 " %bn = xor i8 %b, -1\n"
560 " %A = select i1 %cmp, i8 %bn, i8 %an\n"
561 " ret i8 %A\n"
562 "}\n");
563 expectPattern({SPF_UMIN, SPNB_NA, false});
564 }
565
566 TEST_F(MatchSelectPatternTest, NotNotUMax) {
567 parseAssembly(
568 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n"
569 " %cmp = icmp ult <2 x i8> %a, %b\n"
570 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n"
571 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n"
572 " %A = select <2 x i1> %cmp, <2 x i8> %an, <2 x i8> %bn\n"
573 " ret <2 x i8> %A\n"
574 "}\n");
575 expectPattern({SPF_UMAX, SPNB_NA, false});
576 }
577
578 TEST_F(MatchSelectPatternTest, NotNotUMaxSwap) {
579 parseAssembly(
580 "define i8 @test(i8 %a, i8 %b) {\n"
581 " %cmp = icmp ugt i8 %a, %b\n"
582 " %an = xor i8 %a, -1\n"
583 " %bn = xor i8 %b, -1\n"
584 " %A = select i1 %cmp, i8 %bn, i8 %an\n"
585 " ret i8 %A\n"
586 "}\n");
587 expectPattern({SPF_UMAX, SPNB_NA, false});
588 }
589
590 TEST_F(MatchSelectPatternTest, NotNotEq) {
591 parseAssembly(
592 "define i8 @test(i8 %a, i8 %b) {\n"
593 " %cmp = icmp eq i8 %a, %b\n"
594 " %an = xor i8 %a, -1\n"
595 " %bn = xor i8 %b, -1\n"
596 " %A = select i1 %cmp, i8 %bn, i8 %an\n"
597 " ret i8 %A\n"
598 "}\n");
599 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
600 }
601
602 TEST_F(MatchSelectPatternTest, NotNotNe) {
603 parseAssembly(
604 "define i8 @test(i8 %a, i8 %b) {\n"
605 " %cmp = icmp ne i8 %a, %b\n"
606 " %an = xor i8 %a, -1\n"
607 " %bn = xor i8 %b, -1\n"
608 " %A = select i1 %cmp, i8 %bn, i8 %an\n"
609 " ret i8 %A\n"
610 "}\n");
611 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
612 }
613
614 TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) {
615 StringRef Assembly =
616 "declare void @nounwind_readonly(i32*) nounwind readonly "
617 "declare void @nounwind_argmemonly(i32*) nounwind argmemonly "
618 "declare void @nounwind_willreturn(i32*) nounwind willreturn "
619 "declare void @throws_but_readonly(i32*) readonly "
620 "declare void @throws_but_argmemonly(i32*) argmemonly "
621 "declare void @throws_but_willreturn(i32*) willreturn "
622 " "
623 "declare void @unknown(i32*) "
624 " "
625 "define void @f(i32* %p) { "
626 " call void @nounwind_readonly(i32* %p) "
627 " call void @nounwind_argmemonly(i32* %p) "
628 " call void @nounwind_willreturn(i32* %p)"
629 " call void @throws_but_readonly(i32* %p) "
630 " call void @throws_but_argmemonly(i32* %p) "
631 " call void @throws_but_willreturn(i32* %p) "
632 " call void @unknown(i32* %p) nounwind readonly "
633 " call void @unknown(i32* %p) nounwind argmemonly "
634 " call void @unknown(i32* %p) nounwind willreturn "
635 " call void @unknown(i32* %p) readonly "
636 " call void @unknown(i32* %p) argmemonly "
637 " call void @unknown(i32* %p) willreturn "
638 " ret void "
639 "} ";
640
641 LLVMContext Context;
642 SMDiagnostic Error;
643 auto M = parseAssemblyString(Assembly, Error, Context);
644 assert(M && "Bad assembly?");
645
646 auto *F = M->getFunction("f");
647 assert(F && "Bad assembly?");
648
649 auto &BB = F->getEntryBlock();
650 bool ExpectedAnswers[] = {
651 false, // call void @nounwind_readonly(i32* %p)
652 false, // call void @nounwind_argmemonly(i32* %p)
653 true, // call void @nounwind_willreturn(i32* %p)
654 false, // call void @throws_but_readonly(i32* %p)
655 false, // call void @throws_but_argmemonly(i32* %p)
656 false, // call void @throws_but_willreturn(i32* %p)
657 false, // call void @unknown(i32* %p) nounwind readonly
658 false, // call void @unknown(i32* %p) nounwind argmemonly
659 true, // call void @unknown(i32* %p) nounwind willreturn
660 false, // call void @unknown(i32* %p) readonly
661 false, // call void @unknown(i32* %p) argmemonly
662 false, // call void @unknown(i32* %p) willreturn
663 false, // ret void
664 };
665
666 int Index = 0;
667 for (auto &I : BB) {
668 EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I),
669 ExpectedAnswers[Index])
670 << "Incorrect answer at instruction " << Index << " = " << I;
671 Index++;
672 }
673 }
674
675 TEST_F(ValueTrackingTest, ComputeNumSignBits_PR32045) {
676 parseAssembly(
677 "define i32 @test(i32 %a) {\n"
678 " %A = ashr i32 %a, -1\n"
679 " ret i32 %A\n"
680 "}\n");
681 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
682 }
683
684 // No guarantees for canonical IR in this analysis, so this just bails out.
685 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle) {
686 parseAssembly(
687 "define <2 x i32> @test() {\n"
688 " %A = shufflevector <2 x i32> undef, <2 x i32> undef, <2 x i32> <i32 0, i32 0>\n"
689 " ret <2 x i32> %A\n"
690 "}\n");
691 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
692 }
693
694 // No guarantees for canonical IR in this analysis, so a shuffle element that
695 // references an undef value means this can't return any extra information.
696 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) {
697 parseAssembly(
698 "define <2 x i32> @test(<2 x i1> %x) {\n"
699 " %sext = sext <2 x i1> %x to <2 x i32>\n"
700 " %A = shufflevector <2 x i32> %sext, <2 x i32> undef, <2 x i32> <i32 0, i32 2>\n"
701 " ret <2 x i32> %A\n"
702 "}\n");
703 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
704 }
705
706 TEST_F(ValueTrackingTest, impliesPoisonTest_Identity) {
707 parseAssembly("define void @test(i32 %x, i32 %y) {\n"
708 " %A = add i32 %x, %y\n"
709 " ret void\n"
710 "}");
711 EXPECT_TRUE(impliesPoison(A, A));
712 }
713
714 TEST_F(ValueTrackingTest, impliesPoisonTest_ICmp) {
715 parseAssembly("define void @test(i32 %x) {\n"
716 " %A2 = icmp eq i32 %x, 0\n"
717 " %A = icmp eq i32 %x, 1\n"
718 " ret void\n"
719 "}");
720 EXPECT_TRUE(impliesPoison(A2, A));
721 }
722
723 TEST_F(ValueTrackingTest, impliesPoisonTest_ICmpUnknown) {
724 parseAssembly("define void @test(i32 %x, i32 %y) {\n"
725 " %A2 = icmp eq i32 %x, %y\n"
726 " %A = icmp eq i32 %x, 1\n"
727 " ret void\n"
728 "}");
729 EXPECT_FALSE(impliesPoison(A2, A));
730 }
731
732 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNswOkay) {
733 parseAssembly("define void @test(i32 %x) {\n"
734 " %A2 = add nsw i32 %x, 1\n"
735 " %A = add i32 %A2, 1\n"
736 " ret void\n"
737 "}");
738 EXPECT_TRUE(impliesPoison(A2, A));
739 }
740
741 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNswOkay2) {
742 parseAssembly("define void @test(i32 %x) {\n"
743 " %A2 = add i32 %x, 1\n"
744 " %A = add nsw i32 %A2, 1\n"
745 " ret void\n"
746 "}");
747 EXPECT_TRUE(impliesPoison(A2, A));
748 }
749
750 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNsw) {
751 parseAssembly("define void @test(i32 %x) {\n"
752 " %A2 = add nsw i32 %x, 1\n"
753 " %A = add i32 %x, 1\n"
754 " ret void\n"
755 "}");
756 EXPECT_FALSE(impliesPoison(A2, A));
757 }
758
759 TEST_F(ValueTrackingTest, impliesPoisonTest_Cmp) {
760 parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n"
761 " %A2 = icmp eq i32 %x, %y\n"
762 " %A0 = icmp ult i32 %x, %y\n"
763 " %A = or i1 %A0, %c\n"
764 " ret void\n"
765 "}");
766 EXPECT_TRUE(impliesPoison(A2, A));
767 }
768
769 TEST_F(ValueTrackingTest, impliesPoisonTest_FCmpFMF) {
770 parseAssembly("define void @test(float %x, float %y, i1 %c) {\n"
771 " %A2 = fcmp nnan oeq float %x, %y\n"
772 " %A0 = fcmp olt float %x, %y\n"
773 " %A = or i1 %A0, %c\n"
774 " ret void\n"
775 "}");
776 EXPECT_FALSE(impliesPoison(A2, A));
777 }
778
779 TEST_F(ValueTrackingTest, impliesPoisonTest_AddSubSameOps) {
780 parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n"
781 " %A2 = add i32 %x, %y\n"
782 " %A = sub i32 %x, %y\n"
783 " ret void\n"
784 "}");
785 EXPECT_TRUE(impliesPoison(A2, A));
786 }
787
788 TEST_F(ValueTrackingTest, impliesPoisonTest_MaskCmp) {
789 parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n"
790 " %M2 = and i32 %x, 7\n"
791 " %A2 = icmp eq i32 %M2, 1\n"
792 " %M = and i32 %x, 15\n"
793 " %A = icmp eq i32 %M, 3\n"
794 " ret void\n"
795 "}");
796 EXPECT_TRUE(impliesPoison(A2, A));
797 }
798
799 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle_Pointers) {
800 parseAssembly(
801 "define <2 x i32*> @test(<2 x i32*> %x) {\n"
802 " %A = shufflevector <2 x i32*> zeroinitializer, <2 x i32*> undef, <2 x i32> zeroinitializer\n"
803 " ret <2 x i32*> %A\n"
804 "}\n");
805 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 64u);
806 }
807
808 TEST(ValueTracking, propagatesPoison) {
809 std::string AsmHead =
810 "declare i32 @g(i32)\n"
811 "declare {i32, i1} @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)\n"
812 "declare {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)\n"
813 "declare {i32, i1} @llvm.smul.with.overflow.i32(i32 %a, i32 %b)\n"
814 "declare {i32, i1} @llvm.uadd.with.overflow.i32(i32 %a, i32 %b)\n"
815 "declare {i32, i1} @llvm.usub.with.overflow.i32(i32 %a, i32 %b)\n"
816 "declare {i32, i1} @llvm.umul.with.overflow.i32(i32 %a, i32 %b)\n"
817 "declare float @llvm.sqrt.f32(float)\n"
818 "declare float @llvm.powi.f32.i32(float, i32)\n"
819 "declare float @llvm.sin.f32(float)\n"
820 "declare float @llvm.cos.f32(float)\n"
821 "declare float @llvm.pow.f32(float, float)\n"
822 "declare float @llvm.exp.f32(float)\n"
823 "declare float @llvm.exp2.f32(float)\n"
824 "declare float @llvm.log.f32(float)\n"
825 "declare float @llvm.log10.f32(float)\n"
826 "declare float @llvm.log2.f32(float)\n"
827 "declare float @llvm.fma.f32(float, float, float)\n"
828 "declare float @llvm.fabs.f32(float)\n"
829 "declare float @llvm.minnum.f32(float, float)\n"
830 "declare float @llvm.maxnum.f32(float, float)\n"
831 "declare float @llvm.minimum.f32(float, float)\n"
832 "declare float @llvm.maximum.f32(float, float)\n"
833 "declare float @llvm.copysign.f32(float, float)\n"
834 "declare float @llvm.floor.f32(float)\n"
835 "declare float @llvm.ceil.f32(float)\n"
836 "declare float @llvm.trunc.f32(float)\n"
837 "declare float @llvm.rint.f32(float)\n"
838 "declare float @llvm.nearbyint.f32(float)\n"
839 "declare float @llvm.round.f32(float)\n"
840 "declare float @llvm.roundeven.f32(float)\n"
841 "declare i32 @llvm.lround.f32(float)\n"
842 "declare i64 @llvm.llround.f32(float)\n"
843 "declare i32 @llvm.lrint.f32(float)\n"
844 "declare i64 @llvm.llrint.f32(float)\n"
845 "declare float @llvm.fmuladd.f32(float, float, float)\n"
846 "define void @f(i32 %x, i32 %y, float %fx, float %fy, "
847 "i1 %cond, i8* %p) {\n";
848 std::string AsmTail = " ret void\n}";
849 // (propagates poison?, IR instruction)
850 SmallVector<std::pair<bool, std::string>, 32> Data = {
851 {true, "add i32 %x, %y"},
852 {true, "add nsw nuw i32 %x, %y"},
853 {true, "ashr i32 %x, %y"},
854 {true, "lshr exact i32 %x, 31"},
855 {true, "fadd float %fx, %fy"},
856 {true, "fsub float %fx, %fy"},
857 {true, "fmul float %fx, %fy"},
858 {true, "fdiv float %fx, %fy"},
859 {true, "frem float %fx, %fy"},
860 {true, "fneg float %fx"},
861 {true, "fcmp oeq float %fx, %fy"},
862 {true, "icmp eq i32 %x, %y"},
863 {true, "getelementptr i8, i8* %p, i32 %x"},
864 {true, "getelementptr inbounds i8, i8* %p, i32 %x"},
865 {true, "bitcast float %fx to i32"},
866 {false, "select i1 %cond, i32 %x, i32 %y"},
867 {false, "freeze i32 %x"},
868 {true, "udiv i32 %x, %y"},
869 {true, "urem i32 %x, %y"},
870 {true, "sdiv exact i32 %x, %y"},
871 {true, "srem i32 %x, %y"},
872 {false, "call i32 @g(i32 %x)"},
873 {true, "call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)"},
874 {true, "call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %x, i32 %y)"},
875 {true, "call {i32, i1} @llvm.smul.with.overflow.i32(i32 %x, i32 %y)"},
876 {true, "call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)"},
877 {true, "call {i32, i1} @llvm.usub.with.overflow.i32(i32 %x, i32 %y)"},
878 {true, "call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 %y)"},
879 {false, "call float @llvm.sqrt.f32(float %fx)"},
880 {false, "call float @llvm.powi.f32.i32(float %fx, i32 %x)"},
881 {false, "call float @llvm.sin.f32(float %fx)"},
882 {false, "call float @llvm.cos.f32(float %fx)"},
883 {false, "call float @llvm.pow.f32(float %fx, float %fy)"},
884 {false, "call float @llvm.exp.f32(float %fx)"},
885 {false, "call float @llvm.exp2.f32(float %fx)"},
886 {false, "call float @llvm.log.f32(float %fx)"},
887 {false, "call float @llvm.log10.f32(float %fx)"},
888 {false, "call float @llvm.log2.f32(float %fx)"},
889 {false, "call float @llvm.fma.f32(float %fx, float %fx, float %fy)"},
890 {false, "call float @llvm.fabs.f32(float %fx)"},
891 {false, "call float @llvm.minnum.f32(float %fx, float %fy)"},
892 {false, "call float @llvm.maxnum.f32(float %fx, float %fy)"},
893 {false, "call float @llvm.minimum.f32(float %fx, float %fy)"},
894 {false, "call float @llvm.maximum.f32(float %fx, float %fy)"},
895 {false, "call float @llvm.copysign.f32(float %fx, float %fy)"},
896 {false, "call float @llvm.floor.f32(float %fx)"},
897 {false, "call float @llvm.ceil.f32(float %fx)"},
898 {false, "call float @llvm.trunc.f32(float %fx)"},
899 {false, "call float @llvm.rint.f32(float %fx)"},
900 {false, "call float @llvm.nearbyint.f32(float %fx)"},
901 {false, "call float @llvm.round.f32(float %fx)"},
902 {false, "call float @llvm.roundeven.f32(float %fx)"},
903 {false, "call i32 @llvm.lround.f32(float %fx)"},
904 {false, "call i64 @llvm.llround.f32(float %fx)"},
905 {false, "call i32 @llvm.lrint.f32(float %fx)"},
906 {false, "call i64 @llvm.llrint.f32(float %fx)"},
907 {false, "call float @llvm.fmuladd.f32(float %fx, float %fx, float %fy)"}};
908
909 std::string AssemblyStr = AsmHead;
910 for (auto &Itm : Data)
911 AssemblyStr += Itm.second + "\n";
912 AssemblyStr += AsmTail;
913
914 LLVMContext Context;
915 SMDiagnostic Error;
916 auto M = parseAssemblyString(AssemblyStr, Error, Context);
917 assert(M && "Bad assembly?");
918
919 auto *F = M->getFunction("f");
920 assert(F && "Bad assembly?");
921
922 auto &BB = F->getEntryBlock();
923
924 int Index = 0;
925 for (auto &I : BB) {
926 if (isa<ReturnInst>(&I))
927 break;
928 EXPECT_EQ(propagatesPoison(cast<Operator>(&I)), Data[Index].first)
929 << "Incorrect answer at instruction " << Index << " = " << I;
930 Index++;
931 }
932 }
933
934 TEST_F(ValueTrackingTest, programUndefinedIfPoison) {
935 parseAssembly("declare i32 @any_num()"
936 "define void @test(i32 %mask) {\n"
937 " %A = call i32 @any_num()\n"
938 " %B = or i32 %A, %mask\n"
939 " udiv i32 1, %B"
940 " ret void\n"
941 "}\n");
942 // If %A was poison, udiv raises UB regardless of %mask's value
943 EXPECT_EQ(programUndefinedIfPoison(A), true);
944 }
945
946 TEST_F(ValueTrackingTest, programUndefinedIfUndefOrPoison) {
947 parseAssembly("declare i32 @any_num()"
948 "define void @test(i32 %mask) {\n"
949 " %A = call i32 @any_num()\n"
950 " %B = or i32 %A, %mask\n"
951 " udiv i32 1, %B"
952 " ret void\n"
953 "}\n");
954 // If %A was undef and %mask was 1, udiv does not raise UB
955 EXPECT_EQ(programUndefinedIfUndefOrPoison(A), false);
956 }
957
958 TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_exploitBranchCond) {
959 parseAssembly("declare i1 @any_bool()"
960 "define void @test(i1 %y) {\n"
961 " %A = call i1 @any_bool()\n"
962 " %cond = and i1 %A, %y\n"
963 " br i1 %cond, label %BB1, label %BB2\n"
964 "BB1:\n"
965 " ret void\n"
966 "BB2:\n"
967 " ret void\n"
968 "}\n");
969 DominatorTree DT(*F);
970 for (auto &BB : *F) {
971 if (&BB == &F->getEntryBlock())
972 continue;
973
974 EXPECT_EQ(isGuaranteedNotToBePoison(A, nullptr, BB.getTerminator(), &DT),
975 true)
976 << "isGuaranteedNotToBePoison does not hold at " << *BB.getTerminator();
977 }
978 }
979
980 TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_phi) {
981 parseAssembly("declare i32 @any_i32(i32)"
982 "define void @test() {\n"
983 "ENTRY:\n"
984 " br label %LOOP\n"
985 "LOOP:\n"
986 " %A = phi i32 [0, %ENTRY], [%A.next, %NEXT]\n"
987 " %A.next = call i32 @any_i32(i32 %A)\n"
988 " %cond = icmp eq i32 %A.next, 0\n"
989 " br i1 %cond, label %NEXT, label %EXIT\n"
990 "NEXT:\n"
991 " br label %LOOP\n"
992 "EXIT:\n"
993 " ret void\n"
994 "}\n");
995 DominatorTree DT(*F);
996 for (auto &BB : *F) {
997 if (BB.getName() == "LOOP") {
998 EXPECT_EQ(isGuaranteedNotToBePoison(A, nullptr, A, &DT), true)
999 << "isGuaranteedNotToBePoison does not hold";
1000 }
1001 }
1002 }
1003
1004 TEST_F(ValueTrackingTest, isGuaranteedNotToBeUndefOrPoison) {
1005 parseAssembly("declare void @f(i32 noundef)"
1006 "define void @test(i32 %x) {\n"
1007 " %A = bitcast i32 %x to i32\n"
1008 " call void @f(i32 noundef %x)\n"
1009 " ret void\n"
1010 "}\n");
1011 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(A), true);
1012 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(UndefValue::get(IntegerType::get(Context, 8))), false);
1013 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(PoisonValue::get(IntegerType::get(Context, 8))), false);
1014 EXPECT_EQ(isGuaranteedNotToBePoison(UndefValue::get(IntegerType::get(Context, 8))), true);
1015 EXPECT_EQ(isGuaranteedNotToBePoison(PoisonValue::get(IntegerType::get(Context, 8))), false);
1016
1017 Type *Int32Ty = Type::getInt32Ty(Context);
1018 Constant *CU = UndefValue::get(Int32Ty);
1019 Constant *CP = PoisonValue::get(Int32Ty);
1020 Constant *C1 = ConstantInt::get(Int32Ty, 1);
1021 Constant *C2 = ConstantInt::get(Int32Ty, 2);
1022
1023 {
1024 Constant *V1 = ConstantVector::get({C1, C2});
1025 EXPECT_TRUE(isGuaranteedNotToBeUndefOrPoison(V1));
1026 EXPECT_TRUE(isGuaranteedNotToBePoison(V1));
1027 }
1028
1029 {
1030 Constant *V2 = ConstantVector::get({C1, CU});
1031 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(V2));
1032 EXPECT_TRUE(isGuaranteedNotToBePoison(V2));
1033 }
1034
1035 {
1036 Constant *V3 = ConstantVector::get({C1, CP});
1037 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(V3));
1038 EXPECT_FALSE(isGuaranteedNotToBePoison(V3));
1039 }
1040 }
1041
1042 TEST_F(ValueTrackingTest, isGuaranteedNotToBeUndefOrPoison_assume) {
1043 parseAssembly("declare i1 @f_i1()\n"
1044 "declare i32 @f_i32()\n"
1045 "declare void @llvm.assume(i1)\n"
1046 "define void @test() {\n"
1047 " %A = call i32 @f_i32()\n"
1048 " %cond = call i1 @f_i1()\n"
1049 " %CxtI = add i32 0, 0\n"
1050 " br i1 %cond, label %BB1, label %EXIT\n"
1051 "BB1:\n"
1052 " %CxtI2 = add i32 0, 0\n"
1053 " %cond2 = call i1 @f_i1()\n"
1054 " call void @llvm.assume(i1 true) [ \"noundef\"(i32 %A) ]\n"
1055 " br i1 %cond2, label %BB2, label %EXIT\n"
1056 "BB2:\n"
1057 " %CxtI3 = add i32 0, 0\n"
1058 " ret void\n"
1059 "EXIT:\n"
1060 " ret void\n"
1061 "}");
1062 AssumptionCache AC(*F);
1063 DominatorTree DT(*F);
1064 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI, &DT));
1065 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI2, &DT));
1066 EXPECT_TRUE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI3, &DT));
1067 }
1068
1069 TEST(ValueTracking, canCreatePoisonOrUndef) {
1070 std::string AsmHead =
1071 "@s = external dso_local global i32, align 1\n"
1072 "declare i32 @g(i32)\n"
1073 "declare {i32, i1} @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)\n"
1074 "declare {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)\n"
1075 "declare {i32, i1} @llvm.smul.with.overflow.i32(i32 %a, i32 %b)\n"
1076 "declare {i32, i1} @llvm.uadd.with.overflow.i32(i32 %a, i32 %b)\n"
1077 "declare {i32, i1} @llvm.usub.with.overflow.i32(i32 %a, i32 %b)\n"
1078 "declare {i32, i1} @llvm.umul.with.overflow.i32(i32 %a, i32 %b)\n"
1079 "define void @f(i32 %x, i32 %y, float %fx, float %fy, i1 %cond, "
1080 "<4 x i32> %vx, <4 x i32> %vx2, <vscale x 4 x i32> %svx, i8* %p) {\n";
1081 std::string AsmTail = " ret void\n}";
1082 // (can create poison?, can create undef?, IR instruction)
1083 SmallVector<std::pair<std::pair<bool, bool>, std::string>, 32> Data = {
1084 {{false, false}, "add i32 %x, %y"},
1085 {{true, false}, "add nsw nuw i32 %x, %y"},
1086 {{true, false}, "shl i32 %x, %y"},
1087 {{true, false}, "shl <4 x i32> %vx, %vx2"},
1088 {{true, false}, "shl nsw i32 %x, %y"},
1089 {{true, false}, "shl nsw <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
1090 {{false, false}, "shl i32 %x, 31"},
1091 {{true, false}, "shl i32 %x, 32"},
1092 {{false, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
1093 {{true, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
1094 {{true, false}, "ashr i32 %x, %y"},
1095 {{true, false}, "ashr exact i32 %x, %y"},
1096 {{false, false}, "ashr i32 %x, 31"},
1097 {{true, false}, "ashr exact i32 %x, 31"},
1098 {{false, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
1099 {{true, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
1100 {{true, false}, "ashr exact <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
1101 {{true, false}, "lshr i32 %x, %y"},
1102 {{true, false}, "lshr exact i32 %x, 31"},
1103 {{false, false}, "udiv i32 %x, %y"},
1104 {{true, false}, "udiv exact i32 %x, %y"},
1105 {{false, false}, "getelementptr i8, i8* %p, i32 %x"},
1106 {{true, false}, "getelementptr inbounds i8, i8* %p, i32 %x"},
1107 {{true, false}, "fneg nnan float %fx"},
1108 {{false, false}, "fneg float %fx"},
1109 {{false, false}, "fadd float %fx, %fy"},
1110 {{true, false}, "fadd nnan float %fx, %fy"},
1111 {{false, false}, "urem i32 %x, %y"},
1112 {{true, false}, "fptoui float %fx to i32"},
1113 {{true, false}, "fptosi float %fx to i32"},
1114 {{false, false}, "bitcast float %fx to i32"},
1115 {{false, false}, "select i1 %cond, i32 %x, i32 %y"},
1116 {{true, false}, "select nnan i1 %cond, float %fx, float %fy"},
1117 {{true, false}, "extractelement <4 x i32> %vx, i32 %x"},
1118 {{false, false}, "extractelement <4 x i32> %vx, i32 3"},
1119 {{true, false}, "extractelement <vscale x 4 x i32> %svx, i32 4"},
1120 {{true, false}, "insertelement <4 x i32> %vx, i32 %x, i32 %y"},
1121 {{false, false}, "insertelement <4 x i32> %vx, i32 %x, i32 3"},
1122 {{true, false}, "insertelement <vscale x 4 x i32> %svx, i32 %x, i32 4"},
1123 {{false, false}, "freeze i32 %x"},
1124 {{false, false},
1125 "shufflevector <4 x i32> %vx, <4 x i32> %vx2, "
1126 "<4 x i32> <i32 0, i32 1, i32 2, i32 3>"},
1127 {{false, true},
1128 "shufflevector <4 x i32> %vx, <4 x i32> %vx2, "
1129 "<4 x i32> <i32 0, i32 1, i32 2, i32 undef>"},
1130 {{false, true},
1131 "shufflevector <vscale x 4 x i32> %svx, "
1132 "<vscale x 4 x i32> %svx, <vscale x 4 x i32> undef"},
1133 {{true, false}, "call i32 @g(i32 %x)"},
1134 {{false, false}, "call noundef i32 @g(i32 %x)"},
1135 {{true, false}, "fcmp nnan oeq float %fx, %fy"},
1136 {{false, false}, "fcmp oeq float %fx, %fy"},
1137 {{true, false},
1138 "ashr <4 x i32> %vx, select (i1 icmp sgt (i32 ptrtoint (i32* @s to "
1139 "i32), i32 1), <4 x i32> zeroinitializer, <4 x i32> <i32 0, i32 1, i32 "
1140 "2, i32 3>)"},
1141 {{false, false},
1142 "call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)"},
1143 {{false, false},
1144 "call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %x, i32 %y)"},
1145 {{false, false},
1146 "call {i32, i1} @llvm.smul.with.overflow.i32(i32 %x, i32 %y)"},
1147 {{false, false},
1148 "call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)"},
1149 {{false, false},
1150 "call {i32, i1} @llvm.usub.with.overflow.i32(i32 %x, i32 %y)"},
1151 {{false, false},
1152 "call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 %y)"}};
1153
1154 std::string AssemblyStr = AsmHead;
1155 for (auto &Itm : Data)
1156 AssemblyStr += Itm.second + "\n";
1157 AssemblyStr += AsmTail;
1158
1159 LLVMContext Context;
1160 SMDiagnostic Error;
1161 auto M = parseAssemblyString(AssemblyStr, Error, Context);
1162 assert(M && "Bad assembly?");
1163
1164 auto *F = M->getFunction("f");
1165 assert(F && "Bad assembly?");
1166
1167 auto &BB = F->getEntryBlock();
1168
1169 int Index = 0;
1170 for (auto &I : BB) {
1171 if (isa<ReturnInst>(&I))
1172 break;
1173 bool Poison = Data[Index].first.first;
1174 bool Undef = Data[Index].first.second;
1175 EXPECT_EQ(canCreatePoison(cast<Operator>(&I)), Poison)
1176 << "Incorrect answer of canCreatePoison at instruction " << Index
1177 << " = " << I;
1178 EXPECT_EQ(canCreateUndefOrPoison(cast<Operator>(&I)), Undef || Poison)
1179 << "Incorrect answer of canCreateUndef at instruction " << Index
1180 << " = " << I;
1181 Index++;
1182 }
1183 }
1184
1185 TEST_F(ValueTrackingTest, computePtrAlignment) {
1186 parseAssembly("declare i1 @f_i1()\n"
1187 "declare i8* @f_i8p()\n"
1188 "declare void @llvm.assume(i1)\n"
1189 "define void @test() {\n"
1190 " %A = call i8* @f_i8p()\n"
1191 " %cond = call i1 @f_i1()\n"
1192 " %CxtI = add i32 0, 0\n"
1193 " br i1 %cond, label %BB1, label %EXIT\n"
1194 "BB1:\n"
1195 " %CxtI2 = add i32 0, 0\n"
1196 " %cond2 = call i1 @f_i1()\n"
1197 " call void @llvm.assume(i1 true) [ \"align\"(i8* %A, i64 16) ]\n"
1198 " br i1 %cond2, label %BB2, label %EXIT\n"
1199 "BB2:\n"
1200 " %CxtI3 = add i32 0, 0\n"
1201 " ret void\n"
1202 "EXIT:\n"
1203 " ret void\n"
1204 "}");
1205 AssumptionCache AC(*F);
1206 DominatorTree DT(*F);
1207 const DataLayout &DL = M->getDataLayout();
1208 EXPECT_EQ(getKnownAlignment(A, DL, CxtI, &AC, &DT), Align(1));
1209 EXPECT_EQ(getKnownAlignment(A, DL, CxtI2, &AC, &DT), Align(1));
1210 EXPECT_EQ(getKnownAlignment(A, DL, CxtI3, &AC, &DT), Align(16));
1211 }
1212
1213 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
1214 parseAssembly(
1215 "define i32 @test(i32 %a, i32 %b) {\n"
1216 " %ash = mul i32 %a, 8\n"
1217 " %aad = add i32 %ash, 7\n"
1218 " %aan = and i32 %aad, 4095\n"
1219 " %bsh = shl i32 %b, 4\n"
1220 " %bad = or i32 %bsh, 6\n"
1221 " %ban = and i32 %bad, 4095\n"
1222 " %A = mul i32 %aan, %ban\n"
1223 " ret i32 %A\n"
1224 "}\n");
1225 expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u);
1226 }
1227
1228 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) {
1229 parseAssembly(
1230 "define i32 @test(i32 %a, i32 %b) {\n"
1231 " %aa = shl i32 %a, 5\n"
1232 " %bb = shl i32 %b, 5\n"
1233 " %aaa = or i32 %aa, 24\n"
1234 " %bbb = or i32 %bb, 28\n"
1235 " %A = mul i32 %aaa, %bbb\n"
1236 " ret i32 %A\n"
1237 "}\n");
1238 expectKnownBits(/*zero*/ 95u, /*one*/ 32u);
1239 }
1240
1241 TEST_F(ValueTrackingTest, isNonZeroRecurrence) {
1242 parseAssembly(R"(
1243 define i1 @test(i8 %n, i8 %r) {
1244 entry:
1245 br label %loop
1246 loop:
1247 %p = phi i8 [ -1, %entry ], [ %next, %loop ]
1248 %next = add nsw i8 %p, -1
1249 %cmp1 = icmp eq i8 %p, %n
1250 br i1 %cmp1, label %exit, label %loop
1251 exit:
1252 %A = or i8 %p, %r
1253 %CxtI = icmp eq i8 %A, 0
1254 ret i1 %CxtI
1255 }
1256 )");
1257 const DataLayout &DL = M->getDataLayout();
1258 AssumptionCache AC(*F);
1259 EXPECT_TRUE(isKnownNonZero(A, DL, 0, &AC, CxtI));
1260 }
1261
1262 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond) {
1263 parseAssembly(R"(
1264 declare i8* @f_i8()
1265 define void @test(i1 %c) {
1266 %A = call i8* @f_i8()
1267 %B = call i8* @f_i8()
1268 %c1 = icmp ne i8* %A, null
1269 %cond = and i1 %c1, %c
1270 br i1 %cond, label %T, label %Q
1271 T:
1272 %CxtI = add i32 0, 0
1273 ret void
1274 Q:
1275 %CxtI2 = add i32 0, 0
1276 ret void
1277 }
1278 )");
1279 AssumptionCache AC(*F);
1280 DominatorTree DT(*F);
1281 const DataLayout &DL = M->getDataLayout();
1282 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true);
1283 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false);
1284 }
1285
1286 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond2) {
1287 parseAssembly(R"(
1288 declare i8* @f_i8()
1289 define void @test(i1 %c) {
1290 %A = call i8* @f_i8()
1291 %B = call i8* @f_i8()
1292 %c1 = icmp ne i8* %A, null
1293 %cond = select i1 %c, i1 %c1, i1 false
1294 br i1 %cond, label %T, label %Q
1295 T:
1296 %CxtI = add i32 0, 0
1297 ret void
1298 Q:
1299 %CxtI2 = add i32 0, 0
1300 ret void
1301 }
1302 )");
1303 AssumptionCache AC(*F);
1304 DominatorTree DT(*F);
1305 const DataLayout &DL = M->getDataLayout();
1306 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true);
1307 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false);
1308 }
1309
1310 TEST_F(ValueTrackingTest, IsImpliedConditionAnd) {
1311 parseAssembly(R"(
1312 define void @test(i32 %x, i32 %y) {
1313 %c1 = icmp ult i32 %x, 10
1314 %c2 = icmp ult i32 %y, 15
1315 %A = and i1 %c1, %c2
1316 ; x < 10 /\ y < 15
1317 %A2 = icmp ult i32 %x, 20
1318 %A3 = icmp uge i32 %y, 20
1319 %A4 = icmp ult i32 %x, 5
1320 ret void
1321 }
1322 )");
1323 const DataLayout &DL = M->getDataLayout();
1324 EXPECT_EQ(isImpliedCondition(A, A2, DL), true);
1325 EXPECT_EQ(isImpliedCondition(A, A3, DL), false);
1326 EXPECT_EQ(isImpliedCondition(A, A4, DL), None);
1327 }
1328
1329 TEST_F(ValueTrackingTest, IsImpliedConditionAnd2) {
1330 parseAssembly(R"(
1331 define void @test(i32 %x, i32 %y) {
1332 %c1 = icmp ult i32 %x, 10
1333 %c2 = icmp ult i32 %y, 15
1334 %A = select i1 %c1, i1 %c2, i1 false
1335 ; x < 10 /\ y < 15
1336 %A2 = icmp ult i32 %x, 20
1337 %A3 = icmp uge i32 %y, 20
1338 %A4 = icmp ult i32 %x, 5
1339 ret void
1340 }
1341 )");
1342 const DataLayout &DL = M->getDataLayout();
1343 EXPECT_EQ(isImpliedCondition(A, A2, DL), true);
1344 EXPECT_EQ(isImpliedCondition(A, A3, DL), false);
1345 EXPECT_EQ(isImpliedCondition(A, A4, DL), None);
1346 }
1347
1348 TEST_F(ValueTrackingTest, IsImpliedConditionAndVec) {
1349 parseAssembly(R"(
1350 define void @test(<2 x i8> %x, <2 x i8> %y) {
1351 %A = icmp ult <2 x i8> %x, %y
1352 %A2 = icmp ule <2 x i8> %x, %y
1353 ret void
1354 }
1355 )");
1356 const DataLayout &DL = M->getDataLayout();
1357 EXPECT_EQ(isImpliedCondition(A, A2, DL), true);
1358 }
1359
1360 TEST_F(ValueTrackingTest, IsImpliedConditionOr) {
1361 parseAssembly(R"(
1362 define void @test(i32 %x, i32 %y) {
1363 %c1 = icmp ult i32 %x, 10
1364 %c2 = icmp ult i32 %y, 15
1365 %A = or i1 %c1, %c2 ; negated
1366 ; x >= 10 /\ y >= 15
1367 %A2 = icmp ult i32 %x, 5
1368 %A3 = icmp uge i32 %y, 10
1369 %A4 = icmp ult i32 %x, 15
1370 ret void
1371 }
1372 )");
1373 const DataLayout &DL = M->getDataLayout();
1374 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false);
1375 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true);
1376 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), None);
1377 }
1378
1379 TEST_F(ValueTrackingTest, IsImpliedConditionOr2) {
1380 parseAssembly(R"(
1381 define void @test(i32 %x, i32 %y) {
1382 %c1 = icmp ult i32 %x, 10
1383 %c2 = icmp ult i32 %y, 15
1384 %A = select i1 %c1, i1 true, i1 %c2 ; negated
1385 ; x >= 10 /\ y >= 15
1386 %A2 = icmp ult i32 %x, 5
1387 %A3 = icmp uge i32 %y, 10
1388 %A4 = icmp ult i32 %x, 15
1389 ret void
1390 }
1391 )");
1392 const DataLayout &DL = M->getDataLayout();
1393 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false);
1394 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true);
1395 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), None);
1396 }
1397
1398 TEST_F(ComputeKnownBitsTest, KnownNonZeroShift) {
1399 // %q is known nonzero without known bits.
1400 // Because %q is nonzero, %A[0] is known to be zero.
1401 parseAssembly(
1402 "define i8 @test(i8 %p, i8* %pq) {\n"
1403 " %q = load i8, i8* %pq, !range !0\n"
1404 " %A = shl i8 %p, %q\n"
1405 " ret i8 %A\n"
1406 "}\n"
1407 "!0 = !{ i8 1, i8 5 }\n");
1408 expectKnownBits(/*zero*/ 1u, /*one*/ 0u);
1409 }
1410
1411 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) {
1412 // fshl(....1111....0000, 00..1111........, 6)
1413 // = 11....000000..11
1414 parseAssembly(
1415 "define i16 @test(i16 %a, i16 %b) {\n"
1416 " %aa = shl i16 %a, 4\n"
1417 " %bb = lshr i16 %b, 2\n"
1418 " %aaa = or i16 %aa, 3840\n"
1419 " %bbb = or i16 %bb, 3840\n"
1420 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n"
1421 " ret i16 %A\n"
1422 "}\n"
1423 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
1424 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
1425 }
1426
1427 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) {
1428 // fshr(....1111....0000, 00..1111........, 26)
1429 // = 11....000000..11
1430 parseAssembly(
1431 "define i16 @test(i16 %a, i16 %b) {\n"
1432 " %aa = shl i16 %a, 4\n"
1433 " %bb = lshr i16 %b, 2\n"
1434 " %aaa = or i16 %aa, 3840\n"
1435 " %bbb = or i16 %bb, 3840\n"
1436 " %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n"
1437 " ret i16 %A\n"
1438 "}\n"
1439 "declare i16 @llvm.fshr.i16(i16, i16, i16)\n");
1440 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
1441 }
1442
1443 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) {
1444 // fshl(....1111....0000, 00..1111........, 0)
1445 // = ....1111....0000
1446 parseAssembly(
1447 "define i16 @test(i16 %a, i16 %b) {\n"
1448 " %aa = shl i16 %a, 4\n"
1449 " %bb = lshr i16 %b, 2\n"
1450 " %aaa = or i16 %aa, 3840\n"
1451 " %bbb = or i16 %bb, 3840\n"
1452 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n"
1453 " ret i16 %A\n"
1454 "}\n"
1455 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
1456 expectKnownBits(/*zero*/ 15u, /*one*/ 3840u);
1457 }
1458
1459 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) {
1460 // uadd.sat(1111...1, ........)
1461 // = 1111....
1462 parseAssembly(
1463 "define i8 @test(i8 %a, i8 %b) {\n"
1464 " %aa = or i8 %a, 241\n"
1465 " %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n"
1466 " ret i8 %A\n"
1467 "}\n"
1468 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
1469 expectKnownBits(/*zero*/ 0u, /*one*/ 240u);
1470 }
1471
1472 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) {
1473 // uadd.sat(00...011, .1...110)
1474 // = .......1
1475 parseAssembly(
1476 "define i8 @test(i8 %a, i8 %b) {\n"
1477 " %aa = or i8 %a, 3\n"
1478 " %aaa = and i8 %aa, 59\n"
1479 " %bb = or i8 %b, 70\n"
1480 " %bbb = and i8 %bb, 254\n"
1481 " %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n"
1482 " ret i8 %A\n"
1483 "}\n"
1484 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
1485 expectKnownBits(/*zero*/ 0u, /*one*/ 1u);
1486 }
1487
1488 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) {
1489 // usub.sat(0000...0, ........)
1490 // = 0000....
1491 parseAssembly(
1492 "define i8 @test(i8 %a, i8 %b) {\n"
1493 " %aa = and i8 %a, 14\n"
1494 " %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n"
1495 " ret i8 %A\n"
1496 "}\n"
1497 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
1498 expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
1499 }
1500
1501 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) {
1502 // usub.sat(........, 1111...1)
1503 // = 0000....
1504 parseAssembly(
1505 "define i8 @test(i8 %a, i8 %b) {\n"
1506 " %bb = or i8 %a, 241\n"
1507 " %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n"
1508 " ret i8 %A\n"
1509 "}\n"
1510 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
1511 expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
1512 }
1513
1514 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) {
1515 // usub.sat(11...011, .1...110)
1516 // = ......0.
1517 parseAssembly(
1518 "define i8 @test(i8 %a, i8 %b) {\n"
1519 " %aa = or i8 %a, 195\n"
1520 " %aaa = and i8 %aa, 251\n"
1521 " %bb = or i8 %b, 70\n"
1522 " %bbb = and i8 %bb, 254\n"
1523 " %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
1524 " ret i8 %A\n"
1525 "}\n"
1526 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
1527 expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
1528 }
1529
1530 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntTrunc) {
1531 // ptrtoint truncates the pointer type.
1532 parseAssembly(
1533 "define void @test(i8** %p) {\n"
1534 " %A = load i8*, i8** %p\n"
1535 " %i = ptrtoint i8* %A to i32\n"
1536 " %m = and i32 %i, 31\n"
1537 " %c = icmp eq i32 %m, 0\n"
1538 " call void @llvm.assume(i1 %c)\n"
1539 " ret void\n"
1540 "}\n"
1541 "declare void @llvm.assume(i1)\n");
1542 AssumptionCache AC(*F);
1543 KnownBits Known = computeKnownBits(
1544 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
1545 EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
1546 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1547 }
1548
1549 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntZext) {
1550 // ptrtoint zero extends the pointer type.
1551 parseAssembly(
1552 "define void @test(i8** %p) {\n"
1553 " %A = load i8*, i8** %p\n"
1554 " %i = ptrtoint i8* %A to i128\n"
1555 " %m = and i128 %i, 31\n"
1556 " %c = icmp eq i128 %m, 0\n"
1557 " call void @llvm.assume(i1 %c)\n"
1558 " ret void\n"
1559 "}\n"
1560 "declare void @llvm.assume(i1)\n");
1561 AssumptionCache AC(*F);
1562 KnownBits Known = computeKnownBits(
1563 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
1564 EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
1565 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1566 }
1567
1568 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsFreeze) {
1569 parseAssembly("define void @test() {\n"
1570 " %m = call i32 @any_num()\n"
1571 " %A = freeze i32 %m\n"
1572 " %n = and i32 %m, 31\n"
1573 " %c = icmp eq i32 %n, 0\n"
1574 " call void @llvm.assume(i1 %c)\n"
1575 " ret void\n"
1576 "}\n"
1577 "declare void @llvm.assume(i1)\n"
1578 "declare i32 @any_num()\n");
1579 AssumptionCache AC(*F);
1580 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1581 F->front().getTerminator());
1582 EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
1583 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1584 }
1585
1586 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRange) {
1587 parseAssembly("define void @test(i64* %p) {\n"
1588 " %A = load i64, i64* %p, !range !{i64 64, i64 65536}\n"
1589 " %APlus512 = add i64 %A, 512\n"
1590 " %c = icmp ugt i64 %APlus512, 523\n"
1591 " call void @llvm.assume(i1 %c)\n"
1592 " ret void\n"
1593 "}\n"
1594 "declare void @llvm.assume(i1)\n");
1595 AssumptionCache AC(*F);
1596 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1597 F->front().getTerminator());
1598 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1));
1599 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1600 Instruction &APlus512 = findInstructionByName(F, "APlus512");
1601 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC,
1602 F->front().getTerminator());
1603 // We know of one less zero because 512 may have produced a 1 that
1604 // got carried all the way to the first trailing zero.
1605 EXPECT_EQ(Known.Zero.getZExtValue(), (~(65536llu - 1)) << 1);
1606 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1607 // The known range is not precise given computeKnownBits works
1608 // with the masks of zeros and ones, not the ranges.
1609 EXPECT_EQ(Known.getMinValue(), 0u);
1610 EXPECT_EQ(Known.getMaxValue(), 131071);
1611 }
1612
1613 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsUnknownVScale) {
1614 Module M("", Context);
1615 IRBuilder<> Builder(Context);
1616 Function *TheFn =
1617 Intrinsic::getDeclaration(&M, Intrinsic::vscale, {Builder.getInt32Ty()});
1618 CallInst *CI = Builder.CreateCall(TheFn, {}, {}, "");
1619
1620 KnownBits Known = computeKnownBits(CI, M.getDataLayout(), /* Depth */ 0);
1621 // There is no parent function so we cannot look up the vscale_range
1622 // attribute to determine the number of bits.
1623 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1624 EXPECT_EQ(Known.Zero.getZExtValue(), 0u);
1625
1626 BasicBlock *BB = BasicBlock::Create(Context);
1627 BB->getInstList().push_back(CI);
1628 Known = computeKnownBits(CI, M.getDataLayout(), /* Depth */ 0);
1629 // There is no parent function so we cannot look up the vscale_range
1630 // attribute to determine the number of bits.
1631 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1632 EXPECT_EQ(Known.Zero.getZExtValue(), 0u);
1633
1634 CI->removeFromParent();
1635 delete CI;
1636 delete BB;
1637 }
1638
1639 // 512 + [32, 64) doesn't produce overlapping bits.
1640 // Make sure we get all the individual bits properly.
1641 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRangeNoOverlap) {
1642 parseAssembly("define void @test(i64* %p) {\n"
1643 " %A = load i64, i64* %p, !range !{i64 32, i64 64}\n"
1644 " %APlus512 = add i64 %A, 512\n"
1645 " %c = icmp ugt i64 %APlus512, 523\n"
1646 " call void @llvm.assume(i1 %c)\n"
1647 " ret void\n"
1648 "}\n"
1649 "declare void @llvm.assume(i1)\n");
1650 AssumptionCache AC(*F);
1651 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1652 F->front().getTerminator());
1653 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1));
1654 EXPECT_EQ(Known.One.getZExtValue(), 32u);
1655 Instruction &APlus512 = findInstructionByName(F, "APlus512");
1656 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC,
1657 F->front().getTerminator());
1658 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1));
1659 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u);
1660 // The known range is not precise given computeKnownBits works
1661 // with the masks of zeros and ones, not the ranges.
1662 EXPECT_EQ(Known.getMinValue(), 544);
1663 EXPECT_EQ(Known.getMaxValue(), 575);
1664 }
1665
1666 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRange) {
1667 parseAssembly(
1668 "define void @test(i64* %p) {\n"
1669 " %A = load i64, i64* %p, !range !{i64 64, i64 65536}\n"
1670 " %APtr = inttoptr i64 %A to float*"
1671 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n"
1672 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n"
1673 " call void @llvm.assume(i1 %c)\n"
1674 " ret void\n"
1675 "}\n"
1676 "declare void @llvm.assume(i1)\n");
1677 AssumptionCache AC(*F);
1678 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1679 F->front().getTerminator());
1680 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1));
1681 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1682 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512");
1683 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC,
1684 F->front().getTerminator());
1685 // We know of one less zero because 512 may have produced a 1 that
1686 // got carried all the way to the first trailing zero.
1687 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1) << 1);
1688 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1689 // The known range is not precise given computeKnownBits works
1690 // with the masks of zeros and ones, not the ranges.
1691 EXPECT_EQ(Known.getMinValue(), 0u);
1692 EXPECT_EQ(Known.getMaxValue(), 131071);
1693 }
1694
1695 // 4*128 + [32, 64) doesn't produce overlapping bits.
1696 // Make sure we get all the individual bits properly.
1697 // This test is useful to check that we account for the scaling factor
1698 // in the gep. Indeed, gep float, [32,64), 128 is not 128 + [32,64).
1699 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRangeNoOverlap) {
1700 parseAssembly(
1701 "define void @test(i64* %p) {\n"
1702 " %A = load i64, i64* %p, !range !{i64 32, i64 64}\n"
1703 " %APtr = inttoptr i64 %A to float*"
1704 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n"
1705 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n"
1706 " call void @llvm.assume(i1 %c)\n"
1707 " ret void\n"
1708 "}\n"
1709 "declare void @llvm.assume(i1)\n");
1710 AssumptionCache AC(*F);
1711 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1712 F->front().getTerminator());
1713 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1));
1714 EXPECT_EQ(Known.One.getZExtValue(), 32u);
1715 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512");
1716 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC,
1717 F->front().getTerminator());
1718 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1));
1719 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u);
1720 // The known range is not precise given computeKnownBits works
1721 // with the masks of zeros and ones, not the ranges.
1722 EXPECT_EQ(Known.getMinValue(), 544);
1723 EXPECT_EQ(Known.getMaxValue(), 575);
1724 }
1725
1726 TEST_F(ValueTrackingTest, HaveNoCommonBitsSet) {
1727 {
1728 // Check for an inverted mask: (X & ~M) op (Y & M).
1729 auto M = parseModule(R"(
1730 define i32 @test(i32 %X, i32 %Y, i32 %M) {
1731 %1 = xor i32 %M, -1
1732 %LHS = and i32 %1, %X
1733 %RHS = and i32 %Y, %M
1734 %Ret = add i32 %LHS, %RHS
1735 ret i32 %Ret
1736 })");
1737
1738 auto *F = M->getFunction("test");
1739 auto *LHS = findInstructionByNameOrNull(F, "LHS");
1740 auto *RHS = findInstructionByNameOrNull(F, "RHS");
1741
1742 const DataLayout &DL = M->getDataLayout();
1743 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL));
1744 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL));
1745 }
1746 {
1747 // Check for (A & B) and ~(A | B)
1748 auto M = parseModule(R"(
1749 define void @test(i32 %A, i32 %B) {
1750 %LHS = and i32 %A, %B
1751 %or = or i32 %A, %B
1752 %RHS = xor i32 %or, -1
1753
1754 %LHS2 = and i32 %B, %A
1755 %or2 = or i32 %A, %B
1756 %RHS2 = xor i32 %or2, -1
1757
1758 ret void
1759 })");
1760
1761 auto *F = M->getFunction("test");
1762 const DataLayout &DL = M->getDataLayout();
1763
1764 auto *LHS = findInstructionByNameOrNull(F, "LHS");
1765 auto *RHS = findInstructionByNameOrNull(F, "RHS");
1766 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL));
1767 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL));
1768
1769 auto *LHS2 = findInstructionByNameOrNull(F, "LHS2");
1770 auto *RHS2 = findInstructionByNameOrNull(F, "RHS2");
1771 EXPECT_TRUE(haveNoCommonBitsSet(LHS2, RHS2, DL));
1772 EXPECT_TRUE(haveNoCommonBitsSet(RHS2, LHS2, DL));
1773 }
1774 {
1775 // Check for (A & B) and ~(A | B) in vector version
1776 auto M = parseModule(R"(
1777 define void @test(<2 x i32> %A, <2 x i32> %B) {
1778 %LHS = and <2 x i32> %A, %B
1779 %or = or <2 x i32> %A, %B
1780 %RHS = xor <2 x i32> %or, <i32 -1, i32 -1>
1781
1782 %LHS2 = and <2 x i32> %B, %A
1783 %or2 = or <2 x i32> %A, %B
1784 %RHS2 = xor <2 x i32> %or2, <i32 -1, i32 -1>
1785
1786 ret void
1787 })");
1788
1789 auto *F = M->getFunction("test");
1790 const DataLayout &DL = M->getDataLayout();
1791
1792 auto *LHS = findInstructionByNameOrNull(F, "LHS");
1793 auto *RHS = findInstructionByNameOrNull(F, "RHS");
1794 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL));
1795 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL));
1796
1797 auto *LHS2 = findInstructionByNameOrNull(F, "LHS2");
1798 auto *RHS2 = findInstructionByNameOrNull(F, "RHS2");
1799 EXPECT_TRUE(haveNoCommonBitsSet(LHS2, RHS2, DL));
1800 EXPECT_TRUE(haveNoCommonBitsSet(RHS2, LHS2, DL));
1801 }
1802 }
1803
1804 class IsBytewiseValueTest : public ValueTrackingTest,
1805 public ::testing::WithParamInterface<
1806 std::pair<const char *, const char *>> {
1807 protected:
1808 };
1809
1810 const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
1811 {
1812 "i8 0",
1813 "i48* null",
1814 },
1815 {
1816 "i8 undef",
1817 "i48* undef",
1818 },
1819 {
1820 "i8 0",
1821 "i8 zeroinitializer",
1822 },
1823 {
1824 "i8 0",
1825 "i8 0",
1826 },
1827 {
1828 "i8 -86",
1829 "i8 -86",
1830 },
1831 {
1832 "i8 -1",
1833 "i8 -1",
1834 },
1835 {
1836 "i8 undef",
1837 "i16 undef",
1838 },
1839 {
1840 "i8 0",
1841 "i16 0",
1842 },
1843 {
1844 "",
1845 "i16 7",
1846 },
1847 {
1848 "i8 -86",
1849 "i16 -21846",
1850 },
1851 {
1852 "i8 -1",
1853 "i16 -1",
1854 },
1855 {
1856 "i8 0",
1857 "i48 0",
1858 },
1859 {
1860 "i8 -1",
1861 "i48 -1",
1862 },
1863 {
1864 "i8 0",
1865 "i49 0",
1866 },
1867 {
1868 "",
1869 "i49 -1",
1870 },
1871 {
1872 "i8 0",
1873 "half 0xH0000",
1874 },
1875 {
1876 "i8 -85",
1877 "half 0xHABAB",
1878 },
1879 {
1880 "i8 0",
1881 "float 0.0",
1882 },
1883 {
1884 "i8 -1",
1885 "float 0xFFFFFFFFE0000000",
1886 },
1887 {
1888 "i8 0",
1889 "double 0.0",
1890 },
1891 {
1892 "i8 -15",
1893 "double 0xF1F1F1F1F1F1F1F1",
1894 },
1895 {
1896 "i8 undef",
1897 "i16* undef",
1898 },
1899 {
1900 "i8 0",
1901 "i16* inttoptr (i64 0 to i16*)",
1902 },
1903 {
1904 "i8 -1",
1905 "i16* inttoptr (i64 -1 to i16*)",
1906 },
1907 {
1908 "i8 -86",
1909 "i16* inttoptr (i64 -6148914691236517206 to i16*)",
1910 },
1911 {
1912 "",
1913 "i16* inttoptr (i48 -1 to i16*)",
1914 },
1915 {
1916 "i8 -1",
1917 "i16* inttoptr (i96 -1 to i16*)",
1918 },
1919 {
1920 "i8 undef",
1921 "[0 x i8] zeroinitializer",
1922 },
1923 {
1924 "i8 undef",
1925 "[0 x i8] undef",
1926 },
1927 {
1928 "i8 undef",
1929 "[5 x [0 x i8]] zeroinitializer",
1930 },
1931 {
1932 "i8 undef",
1933 "[5 x [0 x i8]] undef",
1934 },
1935 {
1936 "i8 0",
1937 "[6 x i8] zeroinitializer",
1938 },
1939 {
1940 "i8 undef",
1941 "[6 x i8] undef",
1942 },
1943 {
1944 "i8 1",
1945 "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]",
1946 },
1947 {
1948 "",
1949 "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]",
1950 },
1951 {
1952 "i8 -1",
1953 "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]",
1954 },
1955 {
1956 "",
1957 "[4 x i8] [i8 1, i8 2, i8 1, i8 1]",
1958 },
1959 {
1960 "i8 1",
1961 "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]",
1962 },
1963 {
1964 "i8 0",
1965 "<6 x i8> zeroinitializer",
1966 },
1967 {
1968 "i8 undef",
1969 "<6 x i8> undef",
1970 },
1971 {
1972 "i8 1",
1973 "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>",
1974 },
1975 {
1976 "",
1977 "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>",
1978 },
1979 {
1980 "i8 -1",
1981 "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>",
1982 },
1983 {
1984 "",
1985 "<4 x i8> <i8 1, i8 1, i8 2, i8 1>",
1986 },
1987 {
1988 "i8 5",
1989 "<2 x i8> < i8 5, i8 undef >",
1990 },
1991 {
1992 "i8 0",
1993 "[2 x [2 x i16]] zeroinitializer",
1994 },
1995 {
1996 "i8 undef",
1997 "[2 x [2 x i16]] undef",
1998 },
1999 {
2000 "i8 -86",
2001 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
2002 "[2 x i16] [i16 -21846, i16 -21846]]",
2003 },
2004 {
2005 "",
2006 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
2007 "[2 x i16] [i16 -21836, i16 -21846]]",
2008 },
2009 {
2010 "i8 undef",
2011 "{ } zeroinitializer",
2012 },
2013 {
2014 "i8 undef",
2015 "{ } undef",
2016 },
2017 {
2018 "i8 undef",
2019 "{ {}, {} } zeroinitializer",
2020 },
2021 {
2022 "i8 undef",
2023 "{ {}, {} } undef",
2024 },
2025 {
2026 "i8 0",
2027 "{i8, i64, i16*} zeroinitializer",
2028 },
2029 {
2030 "i8 undef",
2031 "{i8, i64, i16*} undef",
2032 },
2033 {
2034 "i8 -86",
2035 "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}",
2036 },
2037 {
2038 "",
2039 "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}",
2040 },
2041 };
2042
2043 INSTANTIATE_TEST_SUITE_P(IsBytewiseValueParamTests, IsBytewiseValueTest,
2044 ::testing::ValuesIn(IsBytewiseValueTests));
2045
2046 TEST_P(IsBytewiseValueTest, IsBytewiseValue) {
2047 auto M = parseModule(std::string("@test = global ") + GetParam().second);
2048 GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
2049 Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout());
2050 std::string Buff;
2051 raw_string_ostream S(Buff);
2052 if (Actual)
2053 S << *Actual;
2054 EXPECT_EQ(GetParam().first, S.str());
2055 }
2056
2057 TEST_F(ValueTrackingTest, ComputeConstantRange) {
2058 {
2059 // Assumptions:
2060 // * stride >= 5
2061 // * stride < 10
2062 //
2063 // stride = [5, 10)
2064 auto M = parseModule(R"(
2065 declare void @llvm.assume(i1)
2066
2067 define i32 @test(i32 %stride) {
2068 %gt = icmp uge i32 %stride, 5
2069 call void @llvm.assume(i1 %gt)
2070 %lt = icmp ult i32 %stride, 10
2071 call void @llvm.assume(i1 %lt)
2072 %stride.plus.one = add nsw nuw i32 %stride, 1
2073 ret i32 %stride.plus.one
2074 })");
2075 Function *F = M->getFunction("test");
2076
2077 AssumptionCache AC(*F);
2078 Value *Stride = &*F->arg_begin();
2079 ConstantRange CR1 = computeConstantRange(Stride, false, true, &AC, nullptr);
2080 EXPECT_TRUE(CR1.isFullSet());
2081
2082 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2083 ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I);
2084 EXPECT_EQ(5, CR2.getLower());
2085 EXPECT_EQ(10, CR2.getUpper());
2086 }
2087
2088 {
2089 // Assumptions:
2090 // * stride >= 5
2091 // * stride < 200
2092 // * stride == 99
2093 //
2094 // stride = [99, 100)
2095 auto M = parseModule(R"(
2096 declare void @llvm.assume(i1)
2097
2098 define i32 @test(i32 %stride) {
2099 %gt = icmp uge i32 %stride, 5
2100 call void @llvm.assume(i1 %gt)
2101 %lt = icmp ult i32 %stride, 200
2102 call void @llvm.assume(i1 %lt)
2103 %eq = icmp eq i32 %stride, 99
2104 call void @llvm.assume(i1 %eq)
2105 %stride.plus.one = add nsw nuw i32 %stride, 1
2106 ret i32 %stride.plus.one
2107 })");
2108 Function *F = M->getFunction("test");
2109
2110 AssumptionCache AC(*F);
2111 Value *Stride = &*F->arg_begin();
2112 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2113 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I);
2114 EXPECT_EQ(99, *CR.getSingleElement());
2115 }
2116
2117 {
2118 // Assumptions:
2119 // * stride >= 5
2120 // * stride >= 50
2121 // * stride < 100
2122 // * stride < 200
2123 //
2124 // stride = [50, 100)
2125 auto M = parseModule(R"(
2126 declare void @llvm.assume(i1)
2127
2128 define i32 @test(i32 %stride, i1 %cond) {
2129 %gt = icmp uge i32 %stride, 5
2130 call void @llvm.assume(i1 %gt)
2131 %gt.2 = icmp uge i32 %stride, 50
2132 call void @llvm.assume(i1 %gt.2)
2133 br i1 %cond, label %bb1, label %bb2
2134
2135 bb1:
2136 %lt = icmp ult i32 %stride, 200
2137 call void @llvm.assume(i1 %lt)
2138 %lt.2 = icmp ult i32 %stride, 100
2139 call void @llvm.assume(i1 %lt.2)
2140 %stride.plus.one = add nsw nuw i32 %stride, 1
2141 ret i32 %stride.plus.one
2142
2143 bb2:
2144 ret i32 0
2145 })");
2146 Function *F = M->getFunction("test");
2147
2148 AssumptionCache AC(*F);
2149 Value *Stride = &*F->arg_begin();
2150 Instruction *GT2 = &findInstructionByName(F, "gt.2");
2151 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, GT2);
2152 EXPECT_EQ(5, CR.getLower());
2153 EXPECT_EQ(0, CR.getUpper());
2154
2155 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2156 ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I);
2157 EXPECT_EQ(50, CR2.getLower());
2158 EXPECT_EQ(100, CR2.getUpper());
2159 }
2160
2161 {
2162 // Assumptions:
2163 // * stride > 5
2164 // * stride < 5
2165 //
2166 // stride = empty range, as the assumptions contradict each other.
2167 auto M = parseModule(R"(
2168 declare void @llvm.assume(i1)
2169
2170 define i32 @test(i32 %stride, i1 %cond) {
2171 %gt = icmp ugt i32 %stride, 5
2172 call void @llvm.assume(i1 %gt)
2173 %lt = icmp ult i32 %stride, 5
2174 call void @llvm.assume(i1 %lt)
2175 %stride.plus.one = add nsw nuw i32 %stride, 1
2176 ret i32 %stride.plus.one
2177 })");
2178 Function *F = M->getFunction("test");
2179
2180 AssumptionCache AC(*F);
2181 Value *Stride = &*F->arg_begin();
2182
2183 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2184 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I);
2185 EXPECT_TRUE(CR.isEmptySet());
2186 }
2187
2188 {
2189 // Assumptions:
2190 // * x.1 >= 5
2191 // * x.2 < x.1
2192 //
2193 // stride = [0, -1)
2194 auto M = parseModule(R"(
2195 declare void @llvm.assume(i1)
2196
2197 define i32 @test(i32 %x.1, i32 %x.2) {
2198 %gt = icmp uge i32 %x.1, 5
2199 call void @llvm.assume(i1 %gt)
2200 %lt = icmp ult i32 %x.2, %x.1
2201 call void @llvm.assume(i1 %lt)
2202 %stride.plus.one = add nsw nuw i32 %x.1, 1
2203 ret i32 %stride.plus.one
2204 })");
2205 Function *F = M->getFunction("test");
2206
2207 AssumptionCache AC(*F);
2208 Value *X1 = &*(F->arg_begin());
2209 Value *X2 = &*std::next(F->arg_begin());
2210
2211 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2212 ConstantRange CR1 = computeConstantRange(X1, false, true, &AC, I);
2213 ConstantRange CR2 = computeConstantRange(X2, false, true, &AC, I);
2214
2215 EXPECT_EQ(5, CR1.getLower());
2216 EXPECT_EQ(0, CR1.getUpper());
2217
2218 EXPECT_EQ(0, CR2.getLower());
2219 EXPECT_EQ(0xffffffff, CR2.getUpper());
2220
2221 // Check the depth cutoff results in a conservative result (full set) by
2222 // passing Depth == MaxDepth == 6.
2223 ConstantRange CR3 = computeConstantRange(X2, false, true, &AC, I, nullptr, 6);
2224 EXPECT_TRUE(CR3.isFullSet());
2225 }
2226 {
2227 // Assumptions:
2228 // * x.2 <= x.1
2229 auto M = parseModule(R"(
2230 declare void @llvm.assume(i1)
2231
2232 define i32 @test(i32 %x.1, i32 %x.2) {
2233 %lt = icmp ule i32 %x.2, %x.1
2234 call void @llvm.assume(i1 %lt)
2235 %stride.plus.one = add nsw nuw i32 %x.1, 1
2236 ret i32 %stride.plus.one
2237 })");
2238 Function *F = M->getFunction("test");
2239
2240 AssumptionCache AC(*F);
2241 Value *X2 = &*std::next(F->arg_begin());
2242
2243 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2244 ConstantRange CR1 = computeConstantRange(X2, false, true, &AC, I);
2245 // If we don't know the value of x.2, we don't know the value of x.1.
2246 EXPECT_TRUE(CR1.isFullSet());
2247 }
2248 }
2249
2250 struct FindAllocaForValueTestParams {
2251 const char *IR;
2252 bool AnyOffsetResult;
2253 bool ZeroOffsetResult;
2254 };
2255
2256 class FindAllocaForValueTest
2257 : public ValueTrackingTest,
2258 public ::testing::WithParamInterface<FindAllocaForValueTestParams> {
2259 protected:
2260 };
2261
2262 const FindAllocaForValueTestParams FindAllocaForValueTests[] = {
2263 {R"(
2264 define void @test() {
2265 %a = alloca i64
2266 %r = bitcast i64* %a to i32*
2267 ret void
2268 })",
2269 true, true},
2270
2271 {R"(
2272 define void @test() {
2273 %a = alloca i32
2274 %r = getelementptr i32, i32* %a, i32 1
2275 ret void
2276 })",
2277 true, false},
2278
2279 {R"(
2280 define void @test() {
2281 %a = alloca i32
2282 %r = getelementptr i32, i32* %a, i32 0
2283 ret void
2284 })",
2285 true, true},
2286
2287 {R"(
2288 define void @test(i1 %cond) {
2289 entry:
2290 %a = alloca i32
2291 br label %bb1
2292
2293 bb1:
2294 %r = phi i32* [ %a, %entry ], [ %r, %bb1 ]
2295 br i1 %cond, label %bb1, label %exit
2296
2297 exit:
2298 ret void
2299 })",
2300 true, true},
2301
2302 {R"(
2303 define void @test(i1 %cond) {
2304 %a = alloca i32
2305 %r = select i1 %cond, i32* %a, i32* %a
2306 ret void
2307 })",
2308 true, true},
2309
2310 {R"(
2311 define void @test(i1 %cond) {
2312 %a = alloca i32
2313 %b = alloca i32
2314 %r = select i1 %cond, i32* %a, i32* %b
2315 ret void
2316 })",
2317 false, false},
2318
2319 {R"(
2320 define void @test(i1 %cond) {
2321 entry:
2322 %a = alloca i64
2323 %a32 = bitcast i64* %a to i32*
2324 br label %bb1
2325
2326 bb1:
2327 %x = phi i32* [ %a32, %entry ], [ %x, %bb1 ]
2328 %r = getelementptr i32, i32* %x, i32 1
2329 br i1 %cond, label %bb1, label %exit
2330
2331 exit:
2332 ret void
2333 })",
2334 true, false},
2335
2336 {R"(
2337 define void @test(i1 %cond) {
2338 entry:
2339 %a = alloca i64
2340 %a32 = bitcast i64* %a to i32*
2341 br label %bb1
2342
2343 bb1:
2344 %x = phi i32* [ %a32, %entry ], [ %r, %bb1 ]
2345 %r = getelementptr i32, i32* %x, i32 1
2346 br i1 %cond, label %bb1, label %exit
2347
2348 exit:
2349 ret void
2350 })",
2351 true, false},
2352
2353 {R"(
2354 define void @test(i1 %cond, i64* %a) {
2355 entry:
2356 %r = bitcast i64* %a to i32*
2357 ret void
2358 })",
2359 false, false},
2360
2361 {R"(
2362 define void @test(i1 %cond) {
2363 entry:
2364 %a = alloca i32
2365 %b = alloca i32
2366 br label %bb1
2367
2368 bb1:
2369 %r = phi i32* [ %a, %entry ], [ %b, %bb1 ]
2370 br i1 %cond, label %bb1, label %exit
2371
2372 exit:
2373 ret void
2374 })",
2375 false, false},
2376 {R"(
2377 declare i32* @retptr(i32* returned)
2378 define void @test(i1 %cond) {
2379 %a = alloca i32
2380 %r = call i32* @retptr(i32* %a)
2381 ret void
2382 })",
2383 true, true},
2384 {R"(
2385 declare i32* @fun(i32*)
2386 define void @test(i1 %cond) {
2387 %a = alloca i32
2388 %r = call i32* @fun(i32* %a)
2389 ret void
2390 })",
2391 false, false},
2392 };
2393
2394 TEST_P(FindAllocaForValueTest, findAllocaForValue) {
2395 auto M = parseModule(GetParam().IR);
2396 Function *F = M->getFunction("test");
2397 Instruction *I = &findInstructionByName(F, "r");
2398 const AllocaInst *AI = findAllocaForValue(I);
2399 EXPECT_EQ(!!AI, GetParam().AnyOffsetResult);
2400 }
2401
2402 TEST_P(FindAllocaForValueTest, findAllocaForValueZeroOffset) {
2403 auto M = parseModule(GetParam().IR);
2404 Function *F = M->getFunction("test");
2405 Instruction *I = &findInstructionByName(F, "r");
2406 const AllocaInst *AI = findAllocaForValue(I, true);
2407 EXPECT_EQ(!!AI, GetParam().ZeroOffsetResult);
2408 }
2409
2410 INSTANTIATE_TEST_SUITE_P(FindAllocaForValueTest, FindAllocaForValueTest,
2411 ::testing::ValuesIn(FindAllocaForValueTests));
LLVM monorepo