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