Debian Codegraph @

llvm-project/llvm/unittests/Analysis/ValueTrackingTest.cpp

raw
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::tuple<bool, std::string, unsigned>, 32> Data = {
851 {true, "add i32 %x, %y", 0},
852 {true, "add i32 %x, %y", 1},
853 {true, "add nsw nuw i32 %x, %y", 0},
854 {true, "add nsw nuw i32 %x, %y", 1},
855 {true, "ashr i32 %x, %y", 0},
856 {true, "ashr i32 %x, %y", 1},
857 {true, "lshr exact i32 %x, 31", 0},
858 {true, "lshr exact i32 %x, 31", 1},
859 {true, "fadd float %fx, %fy", 0},
860 {true, "fadd float %fx, %fy", 1},
861 {true, "fsub float %fx, %fy", 0},
862 {true, "fsub float %fx, %fy", 1},
863 {true, "fmul float %fx, %fy", 0},
864 {true, "fmul float %fx, %fy", 1},
865 {true, "fdiv float %fx, %fy", 0},
866 {true, "fdiv float %fx, %fy", 1},
867 {true, "frem float %fx, %fy", 0},
868 {true, "frem float %fx, %fy", 1},
869 {true, "fneg float %fx", 0},
870 {true, "fcmp oeq float %fx, %fy", 0},
871 {true, "fcmp oeq float %fx, %fy", 1},
872 {true, "icmp eq i32 %x, %y", 0},
873 {true, "icmp eq i32 %x, %y", 1},
874 {true, "getelementptr i8, i8* %p, i32 %x", 0},
875 {true, "getelementptr i8, i8* %p, i32 %x", 1},
876 {true, "getelementptr inbounds i8, i8* %p, i32 %x", 0},
877 {true, "getelementptr inbounds i8, i8* %p, i32 %x", 1},
878 {true, "bitcast float %fx to i32", 0},
879 {true, "select i1 %cond, i32 %x, i32 %y", 0},
880 {false, "select i1 %cond, i32 %x, i32 %y", 1},
881 {false, "select i1 %cond, i32 %x, i32 %y", 2},
882 {false, "freeze i32 %x", 0},
883 {true, "udiv i32 %x, %y", 0},
884 {true, "udiv i32 %x, %y", 1},
885 {true, "urem i32 %x, %y", 0},
886 {true, "urem i32 %x, %y", 1},
887 {true, "sdiv exact i32 %x, %y", 0},
888 {true, "sdiv exact i32 %x, %y", 1},
889 {true, "srem i32 %x, %y", 0},
890 {true, "srem i32 %x, %y", 1},
891 {false, "call i32 @g(i32 %x)", 0},
892 {false, "call i32 @g(i32 %x)", 1},
893 {true, "call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)", 0},
894 {true, "call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %x, i32 %y)", 0},
895 {true, "call {i32, i1} @llvm.smul.with.overflow.i32(i32 %x, i32 %y)", 0},
896 {true, "call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)", 0},
897 {true, "call {i32, i1} @llvm.usub.with.overflow.i32(i32 %x, i32 %y)", 0},
898 {true, "call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 %y)", 0},
899 {false, "call float @llvm.sqrt.f32(float %fx)", 0},
900 {false, "call float @llvm.powi.f32.i32(float %fx, i32 %x)", 0},
901 {false, "call float @llvm.sin.f32(float %fx)", 0},
902 {false, "call float @llvm.cos.f32(float %fx)", 0},
903 {false, "call float @llvm.pow.f32(float %fx, float %fy)", 0},
904 {false, "call float @llvm.exp.f32(float %fx)", 0},
905 {false, "call float @llvm.exp2.f32(float %fx)", 0},
906 {false, "call float @llvm.log.f32(float %fx)", 0},
907 {false, "call float @llvm.log10.f32(float %fx)", 0},
908 {false, "call float @llvm.log2.f32(float %fx)", 0},
909 {false, "call float @llvm.fma.f32(float %fx, float %fx, float %fy)", 0},
910 {false, "call float @llvm.fabs.f32(float %fx)", 0},
911 {false, "call float @llvm.minnum.f32(float %fx, float %fy)", 0},
912 {false, "call float @llvm.maxnum.f32(float %fx, float %fy)", 0},
913 {false, "call float @llvm.minimum.f32(float %fx, float %fy)", 0},
914 {false, "call float @llvm.maximum.f32(float %fx, float %fy)", 0},
915 {false, "call float @llvm.copysign.f32(float %fx, float %fy)", 0},
916 {false, "call float @llvm.floor.f32(float %fx)", 0},
917 {false, "call float @llvm.ceil.f32(float %fx)", 0},
918 {false, "call float @llvm.trunc.f32(float %fx)", 0},
919 {false, "call float @llvm.rint.f32(float %fx)", 0},
920 {false, "call float @llvm.nearbyint.f32(float %fx)", 0},
921 {false, "call float @llvm.round.f32(float %fx)", 0},
922 {false, "call float @llvm.roundeven.f32(float %fx)", 0},
923 {false, "call i32 @llvm.lround.f32(float %fx)", 0},
924 {false, "call i64 @llvm.llround.f32(float %fx)", 0},
925 {false, "call i32 @llvm.lrint.f32(float %fx)", 0},
926 {false, "call i64 @llvm.llrint.f32(float %fx)", 0},
927 {false, "call float @llvm.fmuladd.f32(float %fx, float %fx, float %fy)",
928 0}};
929
930 std::string AssemblyStr = AsmHead;
931 for (auto &Itm : Data)
932 AssemblyStr += std::get<1>(Itm) + "\n";
933 AssemblyStr += AsmTail;
934
935 LLVMContext Context;
936 SMDiagnostic Error;
937 auto M = parseAssemblyString(AssemblyStr, Error, Context);
938 assert(M && "Bad assembly?");
939
940 auto *F = M->getFunction("f");
941 assert(F && "Bad assembly?");
942
943 auto &BB = F->getEntryBlock();
944
945 int Index = 0;
946 for (auto &I : BB) {
947 if (isa<ReturnInst>(&I))
948 break;
949 bool ExpectedVal = std::get<0>(Data[Index]);
950 unsigned OpIdx = std::get<2>(Data[Index]);
951 EXPECT_EQ(propagatesPoison(I.getOperandUse(OpIdx)), ExpectedVal)
952 << "Incorrect answer at instruction " << Index << " = " << I;
953 Index++;
954 }
955 }
956
957 TEST_F(ValueTrackingTest, programUndefinedIfPoison) {
958 parseAssembly("declare i32 @any_num()"
959 "define void @test(i32 %mask) {\n"
960 " %A = call i32 @any_num()\n"
961 " %B = or i32 %A, %mask\n"
962 " udiv i32 1, %B"
963 " ret void\n"
964 "}\n");
965 // If %A was poison, udiv raises UB regardless of %mask's value
966 EXPECT_EQ(programUndefinedIfPoison(A), true);
967 }
968
969 TEST_F(ValueTrackingTest, programUndefinedIfUndefOrPoison) {
970 parseAssembly("declare i32 @any_num()"
971 "define void @test(i32 %mask) {\n"
972 " %A = call i32 @any_num()\n"
973 " %B = or i32 %A, %mask\n"
974 " udiv i32 1, %B"
975 " ret void\n"
976 "}\n");
977 // If %A was undef and %mask was 1, udiv does not raise UB
978 EXPECT_EQ(programUndefinedIfUndefOrPoison(A), false);
979 }
980
981 TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_exploitBranchCond) {
982 parseAssembly("declare i1 @any_bool()"
983 "define void @test(i1 %y) {\n"
984 " %A = call i1 @any_bool()\n"
985 " %cond = and i1 %A, %y\n"
986 " br i1 %cond, label %BB1, label %BB2\n"
987 "BB1:\n"
988 " ret void\n"
989 "BB2:\n"
990 " ret void\n"
991 "}\n");
992 DominatorTree DT(*F);
993 for (auto &BB : *F) {
994 if (&BB == &F->getEntryBlock())
995 continue;
996
997 EXPECT_EQ(isGuaranteedNotToBePoison(A, nullptr, BB.getTerminator(), &DT),
998 true)
999 << "isGuaranteedNotToBePoison does not hold at " << *BB.getTerminator();
1000 }
1001 }
1002
1003 TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_phi) {
1004 parseAssembly("declare i32 @any_i32(i32)"
1005 "define void @test() {\n"
1006 "ENTRY:\n"
1007 " br label %LOOP\n"
1008 "LOOP:\n"
1009 " %A = phi i32 [0, %ENTRY], [%A.next, %NEXT]\n"
1010 " %A.next = call i32 @any_i32(i32 %A)\n"
1011 " %cond = icmp eq i32 %A.next, 0\n"
1012 " br i1 %cond, label %NEXT, label %EXIT\n"
1013 "NEXT:\n"
1014 " br label %LOOP\n"
1015 "EXIT:\n"
1016 " ret void\n"
1017 "}\n");
1018 DominatorTree DT(*F);
1019 for (auto &BB : *F) {
1020 if (BB.getName() == "LOOP") {
1021 EXPECT_EQ(isGuaranteedNotToBePoison(A, nullptr, A, &DT), true)
1022 << "isGuaranteedNotToBePoison does not hold";
1023 }
1024 }
1025 }
1026
1027 TEST_F(ValueTrackingTest, isGuaranteedNotToBeUndefOrPoison) {
1028 parseAssembly("declare void @f(i32 noundef)"
1029 "define void @test(i32 %x) {\n"
1030 " %A = bitcast i32 %x to i32\n"
1031 " call void @f(i32 noundef %x)\n"
1032 " ret void\n"
1033 "}\n");
1034 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(A), true);
1035 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(UndefValue::get(IntegerType::get(Context, 8))), false);
1036 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(PoisonValue::get(IntegerType::get(Context, 8))), false);
1037 EXPECT_EQ(isGuaranteedNotToBePoison(UndefValue::get(IntegerType::get(Context, 8))), true);
1038 EXPECT_EQ(isGuaranteedNotToBePoison(PoisonValue::get(IntegerType::get(Context, 8))), false);
1039
1040 Type *Int32Ty = Type::getInt32Ty(Context);
1041 Constant *CU = UndefValue::get(Int32Ty);
1042 Constant *CP = PoisonValue::get(Int32Ty);
1043 Constant *C1 = ConstantInt::get(Int32Ty, 1);
1044 Constant *C2 = ConstantInt::get(Int32Ty, 2);
1045
1046 {
1047 Constant *V1 = ConstantVector::get({C1, C2});
1048 EXPECT_TRUE(isGuaranteedNotToBeUndefOrPoison(V1));
1049 EXPECT_TRUE(isGuaranteedNotToBePoison(V1));
1050 }
1051
1052 {
1053 Constant *V2 = ConstantVector::get({C1, CU});
1054 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(V2));
1055 EXPECT_TRUE(isGuaranteedNotToBePoison(V2));
1056 }
1057
1058 {
1059 Constant *V3 = ConstantVector::get({C1, CP});
1060 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(V3));
1061 EXPECT_FALSE(isGuaranteedNotToBePoison(V3));
1062 }
1063 }
1064
1065 TEST_F(ValueTrackingTest, isGuaranteedNotToBeUndefOrPoison_assume) {
1066 parseAssembly("declare i1 @f_i1()\n"
1067 "declare i32 @f_i32()\n"
1068 "declare void @llvm.assume(i1)\n"
1069 "define void @test() {\n"
1070 " %A = call i32 @f_i32()\n"
1071 " %cond = call i1 @f_i1()\n"
1072 " %CxtI = add i32 0, 0\n"
1073 " br i1 %cond, label %BB1, label %EXIT\n"
1074 "BB1:\n"
1075 " %CxtI2 = add i32 0, 0\n"
1076 " %cond2 = call i1 @f_i1()\n"
1077 " call void @llvm.assume(i1 true) [ \"noundef\"(i32 %A) ]\n"
1078 " br i1 %cond2, label %BB2, label %EXIT\n"
1079 "BB2:\n"
1080 " %CxtI3 = add i32 0, 0\n"
1081 " ret void\n"
1082 "EXIT:\n"
1083 " ret void\n"
1084 "}");
1085 AssumptionCache AC(*F);
1086 DominatorTree DT(*F);
1087 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI, &DT));
1088 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI2, &DT));
1089 EXPECT_TRUE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI3, &DT));
1090 }
1091
1092 TEST(ValueTracking, canCreatePoisonOrUndef) {
1093 std::string AsmHead =
1094 "@s = external dso_local global i32, align 1\n"
1095 "declare i32 @g(i32)\n"
1096 "declare {i32, i1} @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)\n"
1097 "declare {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)\n"
1098 "declare {i32, i1} @llvm.smul.with.overflow.i32(i32 %a, i32 %b)\n"
1099 "declare {i32, i1} @llvm.uadd.with.overflow.i32(i32 %a, i32 %b)\n"
1100 "declare {i32, i1} @llvm.usub.with.overflow.i32(i32 %a, i32 %b)\n"
1101 "declare {i32, i1} @llvm.umul.with.overflow.i32(i32 %a, i32 %b)\n"
1102 "define void @f(i32 %x, i32 %y, float %fx, float %fy, i1 %cond, "
1103 "<4 x i32> %vx, <4 x i32> %vx2, <vscale x 4 x i32> %svx, i8* %p) {\n";
1104 std::string AsmTail = " ret void\n}";
1105 // (can create poison?, can create undef?, IR instruction)
1106 SmallVector<std::pair<std::pair<bool, bool>, std::string>, 32> Data = {
1107 {{false, false}, "add i32 %x, %y"},
1108 {{true, false}, "add nsw nuw i32 %x, %y"},
1109 {{true, false}, "shl i32 %x, %y"},
1110 {{true, false}, "shl <4 x i32> %vx, %vx2"},
1111 {{true, false}, "shl nsw i32 %x, %y"},
1112 {{true, false}, "shl nsw <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
1113 {{false, false}, "shl i32 %x, 31"},
1114 {{true, false}, "shl i32 %x, 32"},
1115 {{false, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
1116 {{true, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
1117 {{true, false}, "ashr i32 %x, %y"},
1118 {{true, false}, "ashr exact i32 %x, %y"},
1119 {{false, false}, "ashr i32 %x, 31"},
1120 {{true, false}, "ashr exact i32 %x, 31"},
1121 {{false, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
1122 {{true, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
1123 {{true, false}, "ashr exact <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
1124 {{true, false}, "lshr i32 %x, %y"},
1125 {{true, false}, "lshr exact i32 %x, 31"},
1126 {{false, false}, "udiv i32 %x, %y"},
1127 {{true, false}, "udiv exact i32 %x, %y"},
1128 {{false, false}, "getelementptr i8, i8* %p, i32 %x"},
1129 {{true, false}, "getelementptr inbounds i8, i8* %p, i32 %x"},
1130 {{true, false}, "fneg nnan float %fx"},
1131 {{false, false}, "fneg float %fx"},
1132 {{false, false}, "fadd float %fx, %fy"},
1133 {{true, false}, "fadd nnan float %fx, %fy"},
1134 {{false, false}, "urem i32 %x, %y"},
1135 {{true, false}, "fptoui float %fx to i32"},
1136 {{true, false}, "fptosi float %fx to i32"},
1137 {{false, false}, "bitcast float %fx to i32"},
1138 {{false, false}, "select i1 %cond, i32 %x, i32 %y"},
1139 {{true, false}, "select nnan i1 %cond, float %fx, float %fy"},
1140 {{true, false}, "extractelement <4 x i32> %vx, i32 %x"},
1141 {{false, false}, "extractelement <4 x i32> %vx, i32 3"},
1142 {{true, false}, "extractelement <vscale x 4 x i32> %svx, i32 4"},
1143 {{true, false}, "insertelement <4 x i32> %vx, i32 %x, i32 %y"},
1144 {{false, false}, "insertelement <4 x i32> %vx, i32 %x, i32 3"},
1145 {{true, false}, "insertelement <vscale x 4 x i32> %svx, i32 %x, i32 4"},
1146 {{false, false}, "freeze i32 %x"},
1147 {{false, false},
1148 "shufflevector <4 x i32> %vx, <4 x i32> %vx2, "
1149 "<4 x i32> <i32 0, i32 1, i32 2, i32 3>"},
1150 {{false, true},
1151 "shufflevector <4 x i32> %vx, <4 x i32> %vx2, "
1152 "<4 x i32> <i32 0, i32 1, i32 2, i32 undef>"},
1153 {{false, true},
1154 "shufflevector <vscale x 4 x i32> %svx, "
1155 "<vscale x 4 x i32> %svx, <vscale x 4 x i32> undef"},
1156 {{true, false}, "call i32 @g(i32 %x)"},
1157 {{false, false}, "call noundef i32 @g(i32 %x)"},
1158 {{true, false}, "fcmp nnan oeq float %fx, %fy"},
1159 {{false, false}, "fcmp oeq float %fx, %fy"},
1160 {{true, false},
1161 "ashr <4 x i32> %vx, select (i1 icmp sgt (i32 ptrtoint (i32* @s to "
1162 "i32), i32 1), <4 x i32> zeroinitializer, <4 x i32> <i32 0, i32 1, i32 "
1163 "2, i32 3>)"},
1164 {{false, false},
1165 "call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)"},
1166 {{false, false},
1167 "call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %x, i32 %y)"},
1168 {{false, false},
1169 "call {i32, i1} @llvm.smul.with.overflow.i32(i32 %x, i32 %y)"},
1170 {{false, false},
1171 "call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)"},
1172 {{false, false},
1173 "call {i32, i1} @llvm.usub.with.overflow.i32(i32 %x, i32 %y)"},
1174 {{false, false},
1175 "call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 %y)"}};
1176
1177 std::string AssemblyStr = AsmHead;
1178 for (auto &Itm : Data)
1179 AssemblyStr += Itm.second + "\n";
1180 AssemblyStr += AsmTail;
1181
1182 LLVMContext Context;
1183 SMDiagnostic Error;
1184 auto M = parseAssemblyString(AssemblyStr, Error, Context);
1185 assert(M && "Bad assembly?");
1186
1187 auto *F = M->getFunction("f");
1188 assert(F && "Bad assembly?");
1189
1190 auto &BB = F->getEntryBlock();
1191
1192 int Index = 0;
1193 for (auto &I : BB) {
1194 if (isa<ReturnInst>(&I))
1195 break;
1196 bool Poison = Data[Index].first.first;
1197 bool Undef = Data[Index].first.second;
1198 EXPECT_EQ(canCreatePoison(cast<Operator>(&I)), Poison)
1199 << "Incorrect answer of canCreatePoison at instruction " << Index
1200 << " = " << I;
1201 EXPECT_EQ(canCreateUndefOrPoison(cast<Operator>(&I)), Undef || Poison)
1202 << "Incorrect answer of canCreateUndef at instruction " << Index
1203 << " = " << I;
1204 Index++;
1205 }
1206 }
1207
1208 TEST_F(ValueTrackingTest, computePtrAlignment) {
1209 parseAssembly("declare i1 @f_i1()\n"
1210 "declare i8* @f_i8p()\n"
1211 "declare void @llvm.assume(i1)\n"
1212 "define void @test() {\n"
1213 " %A = call i8* @f_i8p()\n"
1214 " %cond = call i1 @f_i1()\n"
1215 " %CxtI = add i32 0, 0\n"
1216 " br i1 %cond, label %BB1, label %EXIT\n"
1217 "BB1:\n"
1218 " %CxtI2 = add i32 0, 0\n"
1219 " %cond2 = call i1 @f_i1()\n"
1220 " call void @llvm.assume(i1 true) [ \"align\"(i8* %A, i64 16) ]\n"
1221 " br i1 %cond2, label %BB2, label %EXIT\n"
1222 "BB2:\n"
1223 " %CxtI3 = add i32 0, 0\n"
1224 " ret void\n"
1225 "EXIT:\n"
1226 " ret void\n"
1227 "}");
1228 AssumptionCache AC(*F);
1229 DominatorTree DT(*F);
1230 const DataLayout &DL = M->getDataLayout();
1231 EXPECT_EQ(getKnownAlignment(A, DL, CxtI, &AC, &DT), Align(1));
1232 EXPECT_EQ(getKnownAlignment(A, DL, CxtI2, &AC, &DT), Align(1));
1233 EXPECT_EQ(getKnownAlignment(A, DL, CxtI3, &AC, &DT), Align(16));
1234 }
1235
1236 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
1237 parseAssembly(
1238 "define i32 @test(i32 %a, i32 %b) {\n"
1239 " %ash = mul i32 %a, 8\n"
1240 " %aad = add i32 %ash, 7\n"
1241 " %aan = and i32 %aad, 4095\n"
1242 " %bsh = shl i32 %b, 4\n"
1243 " %bad = or i32 %bsh, 6\n"
1244 " %ban = and i32 %bad, 4095\n"
1245 " %A = mul i32 %aan, %ban\n"
1246 " ret i32 %A\n"
1247 "}\n");
1248 expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u);
1249 }
1250
1251 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) {
1252 parseAssembly(
1253 "define i32 @test(i32 %a, i32 %b) {\n"
1254 " %aa = shl i32 %a, 5\n"
1255 " %bb = shl i32 %b, 5\n"
1256 " %aaa = or i32 %aa, 24\n"
1257 " %bbb = or i32 %bb, 28\n"
1258 " %A = mul i32 %aaa, %bbb\n"
1259 " ret i32 %A\n"
1260 "}\n");
1261 expectKnownBits(/*zero*/ 95u, /*one*/ 32u);
1262 }
1263
1264 TEST_F(ValueTrackingTest, isNonZeroRecurrence) {
1265 parseAssembly(R"(
1266 define i1 @test(i8 %n, i8 %r) {
1267 entry:
1268 br label %loop
1269 loop:
1270 %p = phi i8 [ -1, %entry ], [ %next, %loop ]
1271 %next = add nsw i8 %p, -1
1272 %cmp1 = icmp eq i8 %p, %n
1273 br i1 %cmp1, label %exit, label %loop
1274 exit:
1275 %A = or i8 %p, %r
1276 %CxtI = icmp eq i8 %A, 0
1277 ret i1 %CxtI
1278 }
1279 )");
1280 const DataLayout &DL = M->getDataLayout();
1281 AssumptionCache AC(*F);
1282 EXPECT_TRUE(isKnownNonZero(A, DL, 0, &AC, CxtI));
1283 }
1284
1285 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond) {
1286 parseAssembly(R"(
1287 declare i8* @f_i8()
1288 define void @test(i1 %c) {
1289 %A = call i8* @f_i8()
1290 %B = call i8* @f_i8()
1291 %c1 = icmp ne i8* %A, null
1292 %cond = and i1 %c1, %c
1293 br i1 %cond, label %T, label %Q
1294 T:
1295 %CxtI = add i32 0, 0
1296 ret void
1297 Q:
1298 %CxtI2 = add i32 0, 0
1299 ret void
1300 }
1301 )");
1302 AssumptionCache AC(*F);
1303 DominatorTree DT(*F);
1304 const DataLayout &DL = M->getDataLayout();
1305 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true);
1306 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false);
1307 }
1308
1309 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond2) {
1310 parseAssembly(R"(
1311 declare i8* @f_i8()
1312 define void @test(i1 %c) {
1313 %A = call i8* @f_i8()
1314 %B = call i8* @f_i8()
1315 %c1 = icmp ne i8* %A, null
1316 %cond = select i1 %c, i1 %c1, i1 false
1317 br i1 %cond, label %T, label %Q
1318 T:
1319 %CxtI = add i32 0, 0
1320 ret void
1321 Q:
1322 %CxtI2 = add i32 0, 0
1323 ret void
1324 }
1325 )");
1326 AssumptionCache AC(*F);
1327 DominatorTree DT(*F);
1328 const DataLayout &DL = M->getDataLayout();
1329 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true);
1330 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false);
1331 }
1332
1333 TEST_F(ValueTrackingTest, IsImpliedConditionAnd) {
1334 parseAssembly(R"(
1335 define void @test(i32 %x, i32 %y) {
1336 %c1 = icmp ult i32 %x, 10
1337 %c2 = icmp ult i32 %y, 15
1338 %A = and i1 %c1, %c2
1339 ; x < 10 /\ y < 15
1340 %A2 = icmp ult i32 %x, 20
1341 %A3 = icmp uge i32 %y, 20
1342 %A4 = icmp ult i32 %x, 5
1343 ret void
1344 }
1345 )");
1346 const DataLayout &DL = M->getDataLayout();
1347 EXPECT_EQ(isImpliedCondition(A, A2, DL), true);
1348 EXPECT_EQ(isImpliedCondition(A, A3, DL), false);
1349 EXPECT_EQ(isImpliedCondition(A, A4, DL), std::nullopt);
1350 }
1351
1352 TEST_F(ValueTrackingTest, IsImpliedConditionAnd2) {
1353 parseAssembly(R"(
1354 define void @test(i32 %x, i32 %y) {
1355 %c1 = icmp ult i32 %x, 10
1356 %c2 = icmp ult i32 %y, 15
1357 %A = select i1 %c1, i1 %c2, i1 false
1358 ; x < 10 /\ y < 15
1359 %A2 = icmp ult i32 %x, 20
1360 %A3 = icmp uge i32 %y, 20
1361 %A4 = icmp ult i32 %x, 5
1362 ret void
1363 }
1364 )");
1365 const DataLayout &DL = M->getDataLayout();
1366 EXPECT_EQ(isImpliedCondition(A, A2, DL), true);
1367 EXPECT_EQ(isImpliedCondition(A, A3, DL), false);
1368 EXPECT_EQ(isImpliedCondition(A, A4, DL), std::nullopt);
1369 }
1370
1371 TEST_F(ValueTrackingTest, IsImpliedConditionAndVec) {
1372 parseAssembly(R"(
1373 define void @test(<2 x i8> %x, <2 x i8> %y) {
1374 %A = icmp ult <2 x i8> %x, %y
1375 %A2 = icmp ule <2 x i8> %x, %y
1376 ret void
1377 }
1378 )");
1379 const DataLayout &DL = M->getDataLayout();
1380 EXPECT_EQ(isImpliedCondition(A, A2, DL), true);
1381 }
1382
1383 TEST_F(ValueTrackingTest, IsImpliedConditionOr) {
1384 parseAssembly(R"(
1385 define void @test(i32 %x, i32 %y) {
1386 %c1 = icmp ult i32 %x, 10
1387 %c2 = icmp ult i32 %y, 15
1388 %A = or i1 %c1, %c2 ; negated
1389 ; x >= 10 /\ y >= 15
1390 %A2 = icmp ult i32 %x, 5
1391 %A3 = icmp uge i32 %y, 10
1392 %A4 = icmp ult i32 %x, 15
1393 ret void
1394 }
1395 )");
1396 const DataLayout &DL = M->getDataLayout();
1397 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false);
1398 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true);
1399 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), std::nullopt);
1400 }
1401
1402 TEST_F(ValueTrackingTest, IsImpliedConditionOr2) {
1403 parseAssembly(R"(
1404 define void @test(i32 %x, i32 %y) {
1405 %c1 = icmp ult i32 %x, 10
1406 %c2 = icmp ult i32 %y, 15
1407 %A = select i1 %c1, i1 true, i1 %c2 ; negated
1408 ; x >= 10 /\ y >= 15
1409 %A2 = icmp ult i32 %x, 5
1410 %A3 = icmp uge i32 %y, 10
1411 %A4 = icmp ult i32 %x, 15
1412 ret void
1413 }
1414 )");
1415 const DataLayout &DL = M->getDataLayout();
1416 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false);
1417 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true);
1418 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), std::nullopt);
1419 }
1420
1421 TEST_F(ComputeKnownBitsTest, KnownNonZeroShift) {
1422 // %q is known nonzero without known bits.
1423 // Because %q is nonzero, %A[0] is known to be zero.
1424 parseAssembly(
1425 "define i8 @test(i8 %p, i8* %pq) {\n"
1426 " %q = load i8, i8* %pq, !range !0\n"
1427 " %A = shl i8 %p, %q\n"
1428 " ret i8 %A\n"
1429 "}\n"
1430 "!0 = !{ i8 1, i8 5 }\n");
1431 expectKnownBits(/*zero*/ 1u, /*one*/ 0u);
1432 }
1433
1434 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) {
1435 // fshl(....1111....0000, 00..1111........, 6)
1436 // = 11....000000..11
1437 parseAssembly(
1438 "define i16 @test(i16 %a, i16 %b) {\n"
1439 " %aa = shl i16 %a, 4\n"
1440 " %bb = lshr i16 %b, 2\n"
1441 " %aaa = or i16 %aa, 3840\n"
1442 " %bbb = or i16 %bb, 3840\n"
1443 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n"
1444 " ret i16 %A\n"
1445 "}\n"
1446 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
1447 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
1448 }
1449
1450 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) {
1451 // fshr(....1111....0000, 00..1111........, 26)
1452 // = 11....000000..11
1453 parseAssembly(
1454 "define i16 @test(i16 %a, i16 %b) {\n"
1455 " %aa = shl i16 %a, 4\n"
1456 " %bb = lshr i16 %b, 2\n"
1457 " %aaa = or i16 %aa, 3840\n"
1458 " %bbb = or i16 %bb, 3840\n"
1459 " %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n"
1460 " ret i16 %A\n"
1461 "}\n"
1462 "declare i16 @llvm.fshr.i16(i16, i16, i16)\n");
1463 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
1464 }
1465
1466 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) {
1467 // fshl(....1111....0000, 00..1111........, 0)
1468 // = ....1111....0000
1469 parseAssembly(
1470 "define i16 @test(i16 %a, i16 %b) {\n"
1471 " %aa = shl i16 %a, 4\n"
1472 " %bb = lshr i16 %b, 2\n"
1473 " %aaa = or i16 %aa, 3840\n"
1474 " %bbb = or i16 %bb, 3840\n"
1475 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n"
1476 " ret i16 %A\n"
1477 "}\n"
1478 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
1479 expectKnownBits(/*zero*/ 15u, /*one*/ 3840u);
1480 }
1481
1482 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) {
1483 // uadd.sat(1111...1, ........)
1484 // = 1111....
1485 parseAssembly(
1486 "define i8 @test(i8 %a, i8 %b) {\n"
1487 " %aa = or i8 %a, 241\n"
1488 " %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n"
1489 " ret i8 %A\n"
1490 "}\n"
1491 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
1492 expectKnownBits(/*zero*/ 0u, /*one*/ 240u);
1493 }
1494
1495 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) {
1496 // uadd.sat(00...011, .1...110)
1497 // = .......1
1498 parseAssembly(
1499 "define i8 @test(i8 %a, i8 %b) {\n"
1500 " %aa = or i8 %a, 3\n"
1501 " %aaa = and i8 %aa, 59\n"
1502 " %bb = or i8 %b, 70\n"
1503 " %bbb = and i8 %bb, 254\n"
1504 " %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n"
1505 " ret i8 %A\n"
1506 "}\n"
1507 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
1508 expectKnownBits(/*zero*/ 0u, /*one*/ 1u);
1509 }
1510
1511 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) {
1512 // usub.sat(0000...0, ........)
1513 // = 0000....
1514 parseAssembly(
1515 "define i8 @test(i8 %a, i8 %b) {\n"
1516 " %aa = and i8 %a, 14\n"
1517 " %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n"
1518 " ret i8 %A\n"
1519 "}\n"
1520 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
1521 expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
1522 }
1523
1524 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) {
1525 // usub.sat(........, 1111...1)
1526 // = 0000....
1527 parseAssembly(
1528 "define i8 @test(i8 %a, i8 %b) {\n"
1529 " %bb = or i8 %a, 241\n"
1530 " %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n"
1531 " ret i8 %A\n"
1532 "}\n"
1533 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
1534 expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
1535 }
1536
1537 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) {
1538 // usub.sat(11...011, .1...110)
1539 // = ......0.
1540 parseAssembly(
1541 "define i8 @test(i8 %a, i8 %b) {\n"
1542 " %aa = or i8 %a, 195\n"
1543 " %aaa = and i8 %aa, 251\n"
1544 " %bb = or i8 %b, 70\n"
1545 " %bbb = and i8 %bb, 254\n"
1546 " %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
1547 " ret i8 %A\n"
1548 "}\n"
1549 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
1550 expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
1551 }
1552
1553 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntTrunc) {
1554 // ptrtoint truncates the pointer type.
1555 parseAssembly(
1556 "define void @test(i8** %p) {\n"
1557 " %A = load i8*, i8** %p\n"
1558 " %i = ptrtoint i8* %A to i32\n"
1559 " %m = and i32 %i, 31\n"
1560 " %c = icmp eq i32 %m, 0\n"
1561 " call void @llvm.assume(i1 %c)\n"
1562 " ret void\n"
1563 "}\n"
1564 "declare void @llvm.assume(i1)\n");
1565 AssumptionCache AC(*F);
1566 KnownBits Known = computeKnownBits(
1567 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
1568 EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
1569 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1570 }
1571
1572 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntZext) {
1573 // ptrtoint zero extends the pointer type.
1574 parseAssembly(
1575 "define void @test(i8** %p) {\n"
1576 " %A = load i8*, i8** %p\n"
1577 " %i = ptrtoint i8* %A to i128\n"
1578 " %m = and i128 %i, 31\n"
1579 " %c = icmp eq i128 %m, 0\n"
1580 " call void @llvm.assume(i1 %c)\n"
1581 " ret void\n"
1582 "}\n"
1583 "declare void @llvm.assume(i1)\n");
1584 AssumptionCache AC(*F);
1585 KnownBits Known = computeKnownBits(
1586 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
1587 EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
1588 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1589 }
1590
1591 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsFreeze) {
1592 parseAssembly("define void @test() {\n"
1593 " %m = call i32 @any_num()\n"
1594 " %A = freeze i32 %m\n"
1595 " %n = and i32 %m, 31\n"
1596 " %c = icmp eq i32 %n, 0\n"
1597 " call void @llvm.assume(i1 %c)\n"
1598 " ret void\n"
1599 "}\n"
1600 "declare void @llvm.assume(i1)\n"
1601 "declare i32 @any_num()\n");
1602 AssumptionCache AC(*F);
1603 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1604 F->front().getTerminator());
1605 EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
1606 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1607 }
1608
1609 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRange) {
1610 parseAssembly("define void @test(i64* %p) {\n"
1611 " %A = load i64, i64* %p, !range !{i64 64, i64 65536}\n"
1612 " %APlus512 = add i64 %A, 512\n"
1613 " %c = icmp ugt i64 %APlus512, 523\n"
1614 " call void @llvm.assume(i1 %c)\n"
1615 " ret void\n"
1616 "}\n"
1617 "declare void @llvm.assume(i1)\n");
1618 AssumptionCache AC(*F);
1619 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1620 F->front().getTerminator());
1621 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1));
1622 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1623 Instruction &APlus512 = findInstructionByName(F, "APlus512");
1624 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC,
1625 F->front().getTerminator());
1626 // We know of one less zero because 512 may have produced a 1 that
1627 // got carried all the way to the first trailing zero.
1628 EXPECT_EQ(Known.Zero.getZExtValue(), (~(65536llu - 1)) << 1);
1629 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1630 // The known range is not precise given computeKnownBits works
1631 // with the masks of zeros and ones, not the ranges.
1632 EXPECT_EQ(Known.getMinValue(), 0u);
1633 EXPECT_EQ(Known.getMaxValue(), 131071);
1634 }
1635
1636 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsUnknownVScale) {
1637 Module M("", Context);
1638 IRBuilder<> Builder(Context);
1639 Function *TheFn =
1640 Intrinsic::getDeclaration(&M, Intrinsic::vscale, {Builder.getInt32Ty()});
1641 CallInst *CI = Builder.CreateCall(TheFn, {}, {}, "");
1642
1643 KnownBits Known = computeKnownBits(CI, M.getDataLayout(), /* Depth */ 0);
1644 // There is no parent function so we cannot look up the vscale_range
1645 // attribute to determine the number of bits.
1646 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1647 EXPECT_EQ(Known.Zero.getZExtValue(), 0u);
1648
1649 BasicBlock *BB = BasicBlock::Create(Context);
1650 CI->insertInto(BB, BB->end());
1651 Known = computeKnownBits(CI, M.getDataLayout(), /* Depth */ 0);
1652 // There is no parent function so we cannot look up the vscale_range
1653 // attribute to determine the number of bits.
1654 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1655 EXPECT_EQ(Known.Zero.getZExtValue(), 0u);
1656
1657 CI->removeFromParent();
1658 delete CI;
1659 delete BB;
1660 }
1661
1662 // 512 + [32, 64) doesn't produce overlapping bits.
1663 // Make sure we get all the individual bits properly.
1664 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRangeNoOverlap) {
1665 parseAssembly("define void @test(i64* %p) {\n"
1666 " %A = load i64, i64* %p, !range !{i64 32, i64 64}\n"
1667 " %APlus512 = add i64 %A, 512\n"
1668 " %c = icmp ugt i64 %APlus512, 523\n"
1669 " call void @llvm.assume(i1 %c)\n"
1670 " ret void\n"
1671 "}\n"
1672 "declare void @llvm.assume(i1)\n");
1673 AssumptionCache AC(*F);
1674 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1675 F->front().getTerminator());
1676 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1));
1677 EXPECT_EQ(Known.One.getZExtValue(), 32u);
1678 Instruction &APlus512 = findInstructionByName(F, "APlus512");
1679 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC,
1680 F->front().getTerminator());
1681 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1));
1682 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u);
1683 // The known range is not precise given computeKnownBits works
1684 // with the masks of zeros and ones, not the ranges.
1685 EXPECT_EQ(Known.getMinValue(), 544);
1686 EXPECT_EQ(Known.getMaxValue(), 575);
1687 }
1688
1689 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRange) {
1690 parseAssembly(
1691 "define void @test(i64* %p) {\n"
1692 " %A = load i64, i64* %p, !range !{i64 64, i64 65536}\n"
1693 " %APtr = inttoptr i64 %A to float*"
1694 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n"
1695 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n"
1696 " call void @llvm.assume(i1 %c)\n"
1697 " ret void\n"
1698 "}\n"
1699 "declare void @llvm.assume(i1)\n");
1700 AssumptionCache AC(*F);
1701 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1702 F->front().getTerminator());
1703 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1));
1704 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1705 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512");
1706 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC,
1707 F->front().getTerminator());
1708 // We know of one less zero because 512 may have produced a 1 that
1709 // got carried all the way to the first trailing zero.
1710 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1) << 1);
1711 EXPECT_EQ(Known.One.getZExtValue(), 0u);
1712 // The known range is not precise given computeKnownBits works
1713 // with the masks of zeros and ones, not the ranges.
1714 EXPECT_EQ(Known.getMinValue(), 0u);
1715 EXPECT_EQ(Known.getMaxValue(), 131071);
1716 }
1717
1718 // 4*128 + [32, 64) doesn't produce overlapping bits.
1719 // Make sure we get all the individual bits properly.
1720 // This test is useful to check that we account for the scaling factor
1721 // in the gep. Indeed, gep float, [32,64), 128 is not 128 + [32,64).
1722 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRangeNoOverlap) {
1723 parseAssembly(
1724 "define void @test(i64* %p) {\n"
1725 " %A = load i64, i64* %p, !range !{i64 32, i64 64}\n"
1726 " %APtr = inttoptr i64 %A to float*"
1727 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n"
1728 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n"
1729 " call void @llvm.assume(i1 %c)\n"
1730 " ret void\n"
1731 "}\n"
1732 "declare void @llvm.assume(i1)\n");
1733 AssumptionCache AC(*F);
1734 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC,
1735 F->front().getTerminator());
1736 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1));
1737 EXPECT_EQ(Known.One.getZExtValue(), 32u);
1738 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512");
1739 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC,
1740 F->front().getTerminator());
1741 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1));
1742 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u);
1743 // The known range is not precise given computeKnownBits works
1744 // with the masks of zeros and ones, not the ranges.
1745 EXPECT_EQ(Known.getMinValue(), 544);
1746 EXPECT_EQ(Known.getMaxValue(), 575);
1747 }
1748
1749 TEST_F(ValueTrackingTest, HaveNoCommonBitsSet) {
1750 {
1751 // Check for an inverted mask: (X & ~M) op (Y & M).
1752 auto M = parseModule(R"(
1753 define i32 @test(i32 %X, i32 %Y, i32 %M) {
1754 %1 = xor i32 %M, -1
1755 %LHS = and i32 %1, %X
1756 %RHS = and i32 %Y, %M
1757 %Ret = add i32 %LHS, %RHS
1758 ret i32 %Ret
1759 })");
1760
1761 auto *F = M->getFunction("test");
1762 auto *LHS = findInstructionByNameOrNull(F, "LHS");
1763 auto *RHS = findInstructionByNameOrNull(F, "RHS");
1764
1765 const DataLayout &DL = M->getDataLayout();
1766 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL));
1767 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL));
1768 }
1769 {
1770 // Check for (A & B) and ~(A | B)
1771 auto M = parseModule(R"(
1772 define void @test(i32 %A, i32 %B) {
1773 %LHS = and i32 %A, %B
1774 %or = or i32 %A, %B
1775 %RHS = xor i32 %or, -1
1776
1777 %LHS2 = and i32 %B, %A
1778 %or2 = or i32 %A, %B
1779 %RHS2 = xor i32 %or2, -1
1780
1781 ret void
1782 })");
1783
1784 auto *F = M->getFunction("test");
1785 const DataLayout &DL = M->getDataLayout();
1786
1787 auto *LHS = findInstructionByNameOrNull(F, "LHS");
1788 auto *RHS = findInstructionByNameOrNull(F, "RHS");
1789 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL));
1790 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL));
1791
1792 auto *LHS2 = findInstructionByNameOrNull(F, "LHS2");
1793 auto *RHS2 = findInstructionByNameOrNull(F, "RHS2");
1794 EXPECT_TRUE(haveNoCommonBitsSet(LHS2, RHS2, DL));
1795 EXPECT_TRUE(haveNoCommonBitsSet(RHS2, LHS2, DL));
1796 }
1797 {
1798 // Check for (A & B) and ~(A | B) in vector version
1799 auto M = parseModule(R"(
1800 define void @test(<2 x i32> %A, <2 x i32> %B) {
1801 %LHS = and <2 x i32> %A, %B
1802 %or = or <2 x i32> %A, %B
1803 %RHS = xor <2 x i32> %or, <i32 -1, i32 -1>
1804
1805 %LHS2 = and <2 x i32> %B, %A
1806 %or2 = or <2 x i32> %A, %B
1807 %RHS2 = xor <2 x i32> %or2, <i32 -1, i32 -1>
1808
1809 ret void
1810 })");
1811
1812 auto *F = M->getFunction("test");
1813 const DataLayout &DL = M->getDataLayout();
1814
1815 auto *LHS = findInstructionByNameOrNull(F, "LHS");
1816 auto *RHS = findInstructionByNameOrNull(F, "RHS");
1817 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL));
1818 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL));
1819
1820 auto *LHS2 = findInstructionByNameOrNull(F, "LHS2");
1821 auto *RHS2 = findInstructionByNameOrNull(F, "RHS2");
1822 EXPECT_TRUE(haveNoCommonBitsSet(LHS2, RHS2, DL));
1823 EXPECT_TRUE(haveNoCommonBitsSet(RHS2, LHS2, DL));
1824 }
1825 }
1826
1827 class IsBytewiseValueTest : public ValueTrackingTest,
1828 public ::testing::WithParamInterface<
1829 std::pair<const char *, const char *>> {
1830 protected:
1831 };
1832
1833 const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
1834 {
1835 "i8 0",
1836 "i48* null",
1837 },
1838 {
1839 "i8 undef",
1840 "i48* undef",
1841 },
1842 {
1843 "i8 0",
1844 "i8 zeroinitializer",
1845 },
1846 {
1847 "i8 0",
1848 "i8 0",
1849 },
1850 {
1851 "i8 -86",
1852 "i8 -86",
1853 },
1854 {
1855 "i8 -1",
1856 "i8 -1",
1857 },
1858 {
1859 "i8 undef",
1860 "i16 undef",
1861 },
1862 {
1863 "i8 0",
1864 "i16 0",
1865 },
1866 {
1867 "",
1868 "i16 7",
1869 },
1870 {
1871 "i8 -86",
1872 "i16 -21846",
1873 },
1874 {
1875 "i8 -1",
1876 "i16 -1",
1877 },
1878 {
1879 "i8 0",
1880 "i48 0",
1881 },
1882 {
1883 "i8 -1",
1884 "i48 -1",
1885 },
1886 {
1887 "i8 0",
1888 "i49 0",
1889 },
1890 {
1891 "",
1892 "i49 -1",
1893 },
1894 {
1895 "i8 0",
1896 "half 0xH0000",
1897 },
1898 {
1899 "i8 -85",
1900 "half 0xHABAB",
1901 },
1902 {
1903 "i8 0",
1904 "float 0.0",
1905 },
1906 {
1907 "i8 -1",
1908 "float 0xFFFFFFFFE0000000",
1909 },
1910 {
1911 "i8 0",
1912 "double 0.0",
1913 },
1914 {
1915 "i8 -15",
1916 "double 0xF1F1F1F1F1F1F1F1",
1917 },
1918 {
1919 "i8 undef",
1920 "i16* undef",
1921 },
1922 {
1923 "i8 0",
1924 "i16* inttoptr (i64 0 to i16*)",
1925 },
1926 {
1927 "i8 -1",
1928 "i16* inttoptr (i64 -1 to i16*)",
1929 },
1930 {
1931 "i8 -86",
1932 "i16* inttoptr (i64 -6148914691236517206 to i16*)",
1933 },
1934 {
1935 "",
1936 "i16* inttoptr (i48 -1 to i16*)",
1937 },
1938 {
1939 "i8 -1",
1940 "i16* inttoptr (i96 -1 to i16*)",
1941 },
1942 {
1943 "i8 undef",
1944 "[0 x i8] zeroinitializer",
1945 },
1946 {
1947 "i8 undef",
1948 "[0 x i8] undef",
1949 },
1950 {
1951 "i8 undef",
1952 "[5 x [0 x i8]] zeroinitializer",
1953 },
1954 {
1955 "i8 undef",
1956 "[5 x [0 x i8]] undef",
1957 },
1958 {
1959 "i8 0",
1960 "[6 x i8] zeroinitializer",
1961 },
1962 {
1963 "i8 undef",
1964 "[6 x i8] undef",
1965 },
1966 {
1967 "i8 1",
1968 "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]",
1969 },
1970 {
1971 "",
1972 "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]",
1973 },
1974 {
1975 "i8 -1",
1976 "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]",
1977 },
1978 {
1979 "",
1980 "[4 x i8] [i8 1, i8 2, i8 1, i8 1]",
1981 },
1982 {
1983 "i8 1",
1984 "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]",
1985 },
1986 {
1987 "i8 0",
1988 "<6 x i8> zeroinitializer",
1989 },
1990 {
1991 "i8 undef",
1992 "<6 x i8> undef",
1993 },
1994 {
1995 "i8 1",
1996 "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>",
1997 },
1998 {
1999 "",
2000 "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>",
2001 },
2002 {
2003 "i8 -1",
2004 "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>",
2005 },
2006 {
2007 "",
2008 "<4 x i8> <i8 1, i8 1, i8 2, i8 1>",
2009 },
2010 {
2011 "i8 5",
2012 "<2 x i8> < i8 5, i8 undef >",
2013 },
2014 {
2015 "i8 0",
2016 "[2 x [2 x i16]] zeroinitializer",
2017 },
2018 {
2019 "i8 undef",
2020 "[2 x [2 x i16]] undef",
2021 },
2022 {
2023 "i8 -86",
2024 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
2025 "[2 x i16] [i16 -21846, i16 -21846]]",
2026 },
2027 {
2028 "",
2029 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
2030 "[2 x i16] [i16 -21836, i16 -21846]]",
2031 },
2032 {
2033 "i8 undef",
2034 "{ } zeroinitializer",
2035 },
2036 {
2037 "i8 undef",
2038 "{ } undef",
2039 },
2040 {
2041 "i8 undef",
2042 "{ {}, {} } zeroinitializer",
2043 },
2044 {
2045 "i8 undef",
2046 "{ {}, {} } undef",
2047 },
2048 {
2049 "i8 0",
2050 "{i8, i64, i16*} zeroinitializer",
2051 },
2052 {
2053 "i8 undef",
2054 "{i8, i64, i16*} undef",
2055 },
2056 {
2057 "i8 -86",
2058 "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}",
2059 },
2060 {
2061 "",
2062 "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}",
2063 },
2064 };
2065
2066 INSTANTIATE_TEST_SUITE_P(IsBytewiseValueParamTests, IsBytewiseValueTest,
2067 ::testing::ValuesIn(IsBytewiseValueTests));
2068
2069 TEST_P(IsBytewiseValueTest, IsBytewiseValue) {
2070 auto M = parseModule(std::string("@test = global ") + GetParam().second);
2071 GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
2072 Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout());
2073 std::string Buff;
2074 raw_string_ostream S(Buff);
2075 if (Actual)
2076 S << *Actual;
2077 EXPECT_EQ(GetParam().first, S.str());
2078 }
2079
2080 TEST_F(ValueTrackingTest, ComputeConstantRange) {
2081 {
2082 // Assumptions:
2083 // * stride >= 5
2084 // * stride < 10
2085 //
2086 // stride = [5, 10)
2087 auto M = parseModule(R"(
2088 declare void @llvm.assume(i1)
2089
2090 define i32 @test(i32 %stride) {
2091 %gt = icmp uge i32 %stride, 5
2092 call void @llvm.assume(i1 %gt)
2093 %lt = icmp ult i32 %stride, 10
2094 call void @llvm.assume(i1 %lt)
2095 %stride.plus.one = add nsw nuw i32 %stride, 1
2096 ret i32 %stride.plus.one
2097 })");
2098 Function *F = M->getFunction("test");
2099
2100 AssumptionCache AC(*F);
2101 Value *Stride = &*F->arg_begin();
2102 ConstantRange CR1 = computeConstantRange(Stride, false, true, &AC, nullptr);
2103 EXPECT_TRUE(CR1.isFullSet());
2104
2105 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2106 ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I);
2107 EXPECT_EQ(5, CR2.getLower());
2108 EXPECT_EQ(10, CR2.getUpper());
2109 }
2110
2111 {
2112 // Assumptions:
2113 // * stride >= 5
2114 // * stride < 200
2115 // * stride == 99
2116 //
2117 // stride = [99, 100)
2118 auto M = parseModule(R"(
2119 declare void @llvm.assume(i1)
2120
2121 define i32 @test(i32 %stride) {
2122 %gt = icmp uge i32 %stride, 5
2123 call void @llvm.assume(i1 %gt)
2124 %lt = icmp ult i32 %stride, 200
2125 call void @llvm.assume(i1 %lt)
2126 %eq = icmp eq i32 %stride, 99
2127 call void @llvm.assume(i1 %eq)
2128 %stride.plus.one = add nsw nuw i32 %stride, 1
2129 ret i32 %stride.plus.one
2130 })");
2131 Function *F = M->getFunction("test");
2132
2133 AssumptionCache AC(*F);
2134 Value *Stride = &*F->arg_begin();
2135 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2136 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I);
2137 EXPECT_EQ(99, *CR.getSingleElement());
2138 }
2139
2140 {
2141 // Assumptions:
2142 // * stride >= 5
2143 // * stride >= 50
2144 // * stride < 100
2145 // * stride < 200
2146 //
2147 // stride = [50, 100)
2148 auto M = parseModule(R"(
2149 declare void @llvm.assume(i1)
2150
2151 define i32 @test(i32 %stride, i1 %cond) {
2152 %gt = icmp uge i32 %stride, 5
2153 call void @llvm.assume(i1 %gt)
2154 %gt.2 = icmp uge i32 %stride, 50
2155 call void @llvm.assume(i1 %gt.2)
2156 br i1 %cond, label %bb1, label %bb2
2157
2158 bb1:
2159 %lt = icmp ult i32 %stride, 200
2160 call void @llvm.assume(i1 %lt)
2161 %lt.2 = icmp ult i32 %stride, 100
2162 call void @llvm.assume(i1 %lt.2)
2163 %stride.plus.one = add nsw nuw i32 %stride, 1
2164 ret i32 %stride.plus.one
2165
2166 bb2:
2167 ret i32 0
2168 })");
2169 Function *F = M->getFunction("test");
2170
2171 AssumptionCache AC(*F);
2172 Value *Stride = &*F->arg_begin();
2173 Instruction *GT2 = &findInstructionByName(F, "gt.2");
2174 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, GT2);
2175 EXPECT_EQ(5, CR.getLower());
2176 EXPECT_EQ(0, CR.getUpper());
2177
2178 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2179 ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I);
2180 EXPECT_EQ(50, CR2.getLower());
2181 EXPECT_EQ(100, CR2.getUpper());
2182 }
2183
2184 {
2185 // Assumptions:
2186 // * stride > 5
2187 // * stride < 5
2188 //
2189 // stride = empty range, as the assumptions contradict each other.
2190 auto M = parseModule(R"(
2191 declare void @llvm.assume(i1)
2192
2193 define i32 @test(i32 %stride, i1 %cond) {
2194 %gt = icmp ugt i32 %stride, 5
2195 call void @llvm.assume(i1 %gt)
2196 %lt = icmp ult i32 %stride, 5
2197 call void @llvm.assume(i1 %lt)
2198 %stride.plus.one = add nsw nuw i32 %stride, 1
2199 ret i32 %stride.plus.one
2200 })");
2201 Function *F = M->getFunction("test");
2202
2203 AssumptionCache AC(*F);
2204 Value *Stride = &*F->arg_begin();
2205
2206 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2207 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I);
2208 EXPECT_TRUE(CR.isEmptySet());
2209 }
2210
2211 {
2212 // Assumptions:
2213 // * x.1 >= 5
2214 // * x.2 < x.1
2215 //
2216 // stride = [0, -1)
2217 auto M = parseModule(R"(
2218 declare void @llvm.assume(i1)
2219
2220 define i32 @test(i32 %x.1, i32 %x.2) {
2221 %gt = icmp uge i32 %x.1, 5
2222 call void @llvm.assume(i1 %gt)
2223 %lt = icmp ult i32 %x.2, %x.1
2224 call void @llvm.assume(i1 %lt)
2225 %stride.plus.one = add nsw nuw i32 %x.1, 1
2226 ret i32 %stride.plus.one
2227 })");
2228 Function *F = M->getFunction("test");
2229
2230 AssumptionCache AC(*F);
2231 Value *X1 = &*(F->arg_begin());
2232 Value *X2 = &*std::next(F->arg_begin());
2233
2234 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2235 ConstantRange CR1 = computeConstantRange(X1, false, true, &AC, I);
2236 ConstantRange CR2 = computeConstantRange(X2, false, true, &AC, I);
2237
2238 EXPECT_EQ(5, CR1.getLower());
2239 EXPECT_EQ(0, CR1.getUpper());
2240
2241 EXPECT_EQ(0, CR2.getLower());
2242 EXPECT_EQ(0xffffffff, CR2.getUpper());
2243
2244 // Check the depth cutoff results in a conservative result (full set) by
2245 // passing Depth == MaxDepth == 6.
2246 ConstantRange CR3 = computeConstantRange(X2, false, true, &AC, I, nullptr, 6);
2247 EXPECT_TRUE(CR3.isFullSet());
2248 }
2249 {
2250 // Assumptions:
2251 // * x.2 <= x.1
2252 auto M = parseModule(R"(
2253 declare void @llvm.assume(i1)
2254
2255 define i32 @test(i32 %x.1, i32 %x.2) {
2256 %lt = icmp ule i32 %x.2, %x.1
2257 call void @llvm.assume(i1 %lt)
2258 %stride.plus.one = add nsw nuw i32 %x.1, 1
2259 ret i32 %stride.plus.one
2260 })");
2261 Function *F = M->getFunction("test");
2262
2263 AssumptionCache AC(*F);
2264 Value *X2 = &*std::next(F->arg_begin());
2265
2266 Instruction *I = &findInstructionByName(F, "stride.plus.one");
2267 ConstantRange CR1 = computeConstantRange(X2, false, true, &AC, I);
2268 // If we don't know the value of x.2, we don't know the value of x.1.
2269 EXPECT_TRUE(CR1.isFullSet());
2270 }
2271 }
2272
2273 struct FindAllocaForValueTestParams {
2274 const char *IR;
2275 bool AnyOffsetResult;
2276 bool ZeroOffsetResult;
2277 };
2278
2279 class FindAllocaForValueTest
2280 : public ValueTrackingTest,
2281 public ::testing::WithParamInterface<FindAllocaForValueTestParams> {
2282 protected:
2283 };
2284
2285 const FindAllocaForValueTestParams FindAllocaForValueTests[] = {
2286 {R"(
2287 define void @test() {
2288 %a = alloca i64
2289 %r = bitcast i64* %a to i32*
2290 ret void
2291 })",
2292 true, true},
2293
2294 {R"(
2295 define void @test() {
2296 %a = alloca i32
2297 %r = getelementptr i32, i32* %a, i32 1
2298 ret void
2299 })",
2300 true, false},
2301
2302 {R"(
2303 define void @test() {
2304 %a = alloca i32
2305 %r = getelementptr i32, i32* %a, i32 0
2306 ret void
2307 })",
2308 true, true},
2309
2310 {R"(
2311 define void @test(i1 %cond) {
2312 entry:
2313 %a = alloca i32
2314 br label %bb1
2315
2316 bb1:
2317 %r = phi i32* [ %a, %entry ], [ %r, %bb1 ]
2318 br i1 %cond, label %bb1, label %exit
2319
2320 exit:
2321 ret void
2322 })",
2323 true, true},
2324
2325 {R"(
2326 define void @test(i1 %cond) {
2327 %a = alloca i32
2328 %r = select i1 %cond, i32* %a, i32* %a
2329 ret void
2330 })",
2331 true, true},
2332
2333 {R"(
2334 define void @test(i1 %cond) {
2335 %a = alloca i32
2336 %b = alloca i32
2337 %r = select i1 %cond, i32* %a, i32* %b
2338 ret void
2339 })",
2340 false, false},
2341
2342 {R"(
2343 define void @test(i1 %cond) {
2344 entry:
2345 %a = alloca i64
2346 %a32 = bitcast i64* %a to i32*
2347 br label %bb1
2348
2349 bb1:
2350 %x = phi i32* [ %a32, %entry ], [ %x, %bb1 ]
2351 %r = getelementptr i32, i32* %x, i32 1
2352 br i1 %cond, label %bb1, label %exit
2353
2354 exit:
2355 ret void
2356 })",
2357 true, false},
2358
2359 {R"(
2360 define void @test(i1 %cond) {
2361 entry:
2362 %a = alloca i64
2363 %a32 = bitcast i64* %a to i32*
2364 br label %bb1
2365
2366 bb1:
2367 %x = phi i32* [ %a32, %entry ], [ %r, %bb1 ]
2368 %r = getelementptr i32, i32* %x, i32 1
2369 br i1 %cond, label %bb1, label %exit
2370
2371 exit:
2372 ret void
2373 })",
2374 true, false},
2375
2376 {R"(
2377 define void @test(i1 %cond, i64* %a) {
2378 entry:
2379 %r = bitcast i64* %a to i32*
2380 ret void
2381 })",
2382 false, false},
2383
2384 {R"(
2385 define void @test(i1 %cond) {
2386 entry:
2387 %a = alloca i32
2388 %b = alloca i32
2389 br label %bb1
2390
2391 bb1:
2392 %r = phi i32* [ %a, %entry ], [ %b, %bb1 ]
2393 br i1 %cond, label %bb1, label %exit
2394
2395 exit:
2396 ret void
2397 })",
2398 false, false},
2399 {R"(
2400 declare i32* @retptr(i32* returned)
2401 define void @test(i1 %cond) {
2402 %a = alloca i32
2403 %r = call i32* @retptr(i32* %a)
2404 ret void
2405 })",
2406 true, true},
2407 {R"(
2408 declare i32* @fun(i32*)
2409 define void @test(i1 %cond) {
2410 %a = alloca i32
2411 %r = call i32* @fun(i32* %a)
2412 ret void
2413 })",
2414 false, false},
2415 };
2416
2417 TEST_P(FindAllocaForValueTest, findAllocaForValue) {
2418 auto M = parseModule(GetParam().IR);
2419 Function *F = M->getFunction("test");
2420 Instruction *I = &findInstructionByName(F, "r");
2421 const AllocaInst *AI = findAllocaForValue(I);
2422 EXPECT_EQ(!!AI, GetParam().AnyOffsetResult);
2423 }
2424
2425 TEST_P(FindAllocaForValueTest, findAllocaForValueZeroOffset) {
2426 auto M = parseModule(GetParam().IR);
2427 Function *F = M->getFunction("test");
2428 Instruction *I = &findInstructionByName(F, "r");
2429 const AllocaInst *AI = findAllocaForValue(I, true);
2430 EXPECT_EQ(!!AI, GetParam().ZeroOffsetResult);
2431 }
2432
2433 INSTANTIATE_TEST_SUITE_P(FindAllocaForValueTest, FindAllocaForValueTest,
2434 ::testing::ValuesIn(FindAllocaForValueTests));