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