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/Function.h"
14 #include "llvm/IR/InstIterator.h"
15 #include "llvm/IR/Instructions.h"
16 #include "llvm/IR/LLVMContext.h"
17 #include "llvm/IR/Module.h"
18 #include "llvm/Support/ErrorHandling.h"
19 #include "llvm/Support/KnownBits.h"
20 #include "llvm/Support/SourceMgr.h"
21 #include "gtest/gtest.h"
22
23 using namespace llvm;
24
25 namespace {
26
findInstructionByName(Function * F,StringRef Name)27 static Instruction &findInstructionByName(Function *F, StringRef Name) {
28 for (Instruction &I : instructions(F))
29 if (I.getName() == Name)
30 return I;
31
32 llvm_unreachable("Expected value not found");
33 }
34
35 class ValueTrackingTest : public testing::Test {
36 protected:
parseModule(StringRef Assembly)37 std::unique_ptr<Module> parseModule(StringRef Assembly) {
38 SMDiagnostic Error;
39 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
40
41 std::string errMsg;
42 raw_string_ostream os(errMsg);
43 Error.print("", os);
44 EXPECT_TRUE(M) << os.str();
45
46 return M;
47 }
48
parseAssembly(StringRef Assembly)49 void parseAssembly(StringRef Assembly) {
50 M = parseModule(Assembly);
51 ASSERT_TRUE(M);
52
53 F = M->getFunction("test");
54 ASSERT_TRUE(F) << "Test must have a function @test";
55 if (!F)
56 return;
57
58 A = &findInstructionByName(F, "A");
59 ASSERT_TRUE(A) << "@test must have an instruction %A";
60 }
61
62 LLVMContext Context;
63 std::unique_ptr<Module> M;
64 Function *F = nullptr;
65 Instruction *A = nullptr;
66 };
67
68 class MatchSelectPatternTest : public ValueTrackingTest {
69 protected:
expectPattern(const SelectPatternResult & P)70 void expectPattern(const SelectPatternResult &P) {
71 Value *LHS, *RHS;
72 Instruction::CastOps CastOp;
73 SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp);
74 EXPECT_EQ(P.Flavor, R.Flavor);
75 EXPECT_EQ(P.NaNBehavior, R.NaNBehavior);
76 EXPECT_EQ(P.Ordered, R.Ordered);
77 }
78 };
79
80 class ComputeKnownBitsTest : public ValueTrackingTest {
81 protected:
expectKnownBits(uint64_t Zero,uint64_t One)82 void expectKnownBits(uint64_t Zero, uint64_t One) {
83 auto Known = computeKnownBits(A, M->getDataLayout());
84 ASSERT_FALSE(Known.hasConflict());
85 EXPECT_EQ(Known.One.getZExtValue(), One);
86 EXPECT_EQ(Known.Zero.getZExtValue(), Zero);
87 }
88 };
89
90 }
91
TEST_F(MatchSelectPatternTest,SimpleFMin)92 TEST_F(MatchSelectPatternTest, SimpleFMin) {
93 parseAssembly(
94 "define float @test(float %a) {\n"
95 " %1 = fcmp ult float %a, 5.0\n"
96 " %A = select i1 %1, float %a, float 5.0\n"
97 " ret float %A\n"
98 "}\n");
99 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
100 }
101
TEST_F(MatchSelectPatternTest,SimpleFMax)102 TEST_F(MatchSelectPatternTest, SimpleFMax) {
103 parseAssembly(
104 "define float @test(float %a) {\n"
105 " %1 = fcmp ogt float %a, 5.0\n"
106 " %A = select i1 %1, float %a, float 5.0\n"
107 " ret float %A\n"
108 "}\n");
109 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
110 }
111
TEST_F(MatchSelectPatternTest,SwappedFMax)112 TEST_F(MatchSelectPatternTest, SwappedFMax) {
113 parseAssembly(
114 "define float @test(float %a) {\n"
115 " %1 = fcmp olt float 5.0, %a\n"
116 " %A = select i1 %1, float %a, float 5.0\n"
117 " ret float %A\n"
118 "}\n");
119 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
120 }
121
TEST_F(MatchSelectPatternTest,SwappedFMax2)122 TEST_F(MatchSelectPatternTest, SwappedFMax2) {
123 parseAssembly(
124 "define float @test(float %a) {\n"
125 " %1 = fcmp olt float %a, 5.0\n"
126 " %A = select i1 %1, float 5.0, float %a\n"
127 " ret float %A\n"
128 "}\n");
129 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
130 }
131
TEST_F(MatchSelectPatternTest,SwappedFMax3)132 TEST_F(MatchSelectPatternTest, SwappedFMax3) {
133 parseAssembly(
134 "define float @test(float %a) {\n"
135 " %1 = fcmp ult float %a, 5.0\n"
136 " %A = select i1 %1, float 5.0, float %a\n"
137 " ret float %A\n"
138 "}\n");
139 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
140 }
141
TEST_F(MatchSelectPatternTest,FastFMin)142 TEST_F(MatchSelectPatternTest, FastFMin) {
143 parseAssembly(
144 "define float @test(float %a) {\n"
145 " %1 = fcmp nnan olt float %a, 5.0\n"
146 " %A = select i1 %1, float %a, float 5.0\n"
147 " ret float %A\n"
148 "}\n");
149 expectPattern({SPF_FMINNUM, SPNB_RETURNS_ANY, false});
150 }
151
TEST_F(MatchSelectPatternTest,FMinConstantZero)152 TEST_F(MatchSelectPatternTest, FMinConstantZero) {
153 parseAssembly(
154 "define float @test(float %a) {\n"
155 " %1 = fcmp ole float %a, 0.0\n"
156 " %A = select i1 %1, float %a, float 0.0\n"
157 " ret float %A\n"
158 "}\n");
159 // This shouldn't be matched, as %a could be -0.0.
160 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
161 }
162
TEST_F(MatchSelectPatternTest,FMinConstantZeroNsz)163 TEST_F(MatchSelectPatternTest, FMinConstantZeroNsz) {
164 parseAssembly(
165 "define float @test(float %a) {\n"
166 " %1 = fcmp nsz ole float %a, 0.0\n"
167 " %A = select i1 %1, float %a, float 0.0\n"
168 " ret float %A\n"
169 "}\n");
170 // But this should be, because we've ignored signed zeroes.
171 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
172 }
173
TEST_F(MatchSelectPatternTest,FMinMismatchConstantZero1)174 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero1) {
175 parseAssembly(
176 "define float @test(float %a) {\n"
177 " %1 = fcmp olt float -0.0, %a\n"
178 " %A = select i1 %1, float 0.0, float %a\n"
179 " ret float %A\n"
180 "}\n");
181 // The sign of zero doesn't matter in fcmp.
182 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, true});
183 }
184
TEST_F(MatchSelectPatternTest,FMinMismatchConstantZero2)185 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero2) {
186 parseAssembly(
187 "define float @test(float %a) {\n"
188 " %1 = fcmp ogt float %a, -0.0\n"
189 " %A = select i1 %1, float 0.0, float %a\n"
190 " ret float %A\n"
191 "}\n");
192 // The sign of zero doesn't matter in fcmp.
193 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
194 }
195
TEST_F(MatchSelectPatternTest,FMinMismatchConstantZero3)196 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero3) {
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,FMinMismatchConstantZero4)207 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero4) {
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,FMinMismatchConstantZero5)218 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero5) {
219 parseAssembly(
220 "define float @test(float %a) {\n"
221 " %1 = fcmp ogt float -0.0, %a\n"
222 " %A = select i1 %1, float %a, float 0.0\n"
223 " ret float %A\n"
224 "}\n");
225 // The sign of zero doesn't matter in fcmp.
226 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, false});
227 }
228
TEST_F(MatchSelectPatternTest,FMinMismatchConstantZero6)229 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero6) {
230 parseAssembly(
231 "define float @test(float %a) {\n"
232 " %1 = fcmp olt float %a, -0.0\n"
233 " %A = select i1 %1, float %a, float 0.0\n"
234 " ret float %A\n"
235 "}\n");
236 // The sign of zero doesn't matter in fcmp.
237 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
238 }
239
TEST_F(MatchSelectPatternTest,FMinMismatchConstantZero7)240 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero7) {
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,FMinMismatchConstantZero8)251 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero8) {
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,FMaxMismatchConstantZero1)262 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero1) {
263 parseAssembly(
264 "define float @test(float %a) {\n"
265 " %1 = fcmp ogt float -0.0, %a\n"
266 " %A = select i1 %1, float 0.0, float %a\n"
267 " ret float %A\n"
268 "}\n");
269 // The sign of zero doesn't matter in fcmp.
270 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, true});
271 }
272
TEST_F(MatchSelectPatternTest,FMaxMismatchConstantZero2)273 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero2) {
274 parseAssembly(
275 "define float @test(float %a) {\n"
276 " %1 = fcmp olt float %a, -0.0\n"
277 " %A = select i1 %1, float 0.0, float %a\n"
278 " ret float %A\n"
279 "}\n");
280 // The sign of zero doesn't matter in fcmp.
281 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
282 }
283
TEST_F(MatchSelectPatternTest,FMaxMismatchConstantZero3)284 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero3) {
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,FMaxMismatchConstantZero4)295 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero4) {
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,FMaxMismatchConstantZero5)306 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero5) {
307 parseAssembly(
308 "define float @test(float %a) {\n"
309 " %1 = fcmp olt float -0.0, %a\n"
310 " %A = select i1 %1, float %a, float 0.0\n"
311 " ret float %A\n"
312 "}\n");
313 // The sign of zero doesn't matter in fcmp.
314 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
315 }
316
TEST_F(MatchSelectPatternTest,FMaxMismatchConstantZero6)317 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero6) {
318 parseAssembly(
319 "define float @test(float %a) {\n"
320 " %1 = fcmp ogt float %a, -0.0\n"
321 " %A = select i1 %1, float %a, float 0.0\n"
322 " ret float %A\n"
323 "}\n");
324 // The sign of zero doesn't matter in fcmp.
325 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
326 }
327
TEST_F(MatchSelectPatternTest,FMaxMismatchConstantZero7)328 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero7) {
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,FMaxMismatchConstantZero8)339 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero8) {
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,FMinMismatchConstantZeroVecUndef)350 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZeroVecUndef) {
351 parseAssembly(
352 "define <2 x float> @test(<2 x float> %a) {\n"
353 " %1 = fcmp ogt <2 x float> %a, <float -0.0, float -0.0>\n"
354 " %A = select <2 x i1> %1, <2 x float> <float undef, float 0.0>, <2 x float> %a\n"
355 " ret <2 x float> %A\n"
356 "}\n");
357 // An undef in a vector constant can not be back-propagated for this analysis.
358 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
359 }
360
TEST_F(MatchSelectPatternTest,FMaxMismatchConstantZeroVecUndef)361 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZeroVecUndef) {
362 parseAssembly(
363 "define <2 x float> @test(<2 x float> %a) {\n"
364 " %1 = fcmp ogt <2 x float> %a, zeroinitializer\n"
365 " %A = select <2 x i1> %1, <2 x float> %a, <2 x float> <float -0.0, float undef>\n"
366 " ret <2 x float> %A\n"
367 "}\n");
368 // An undef in a vector constant can not be back-propagated for this analysis.
369 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
370 }
371
TEST_F(MatchSelectPatternTest,VectorFMinimum)372 TEST_F(MatchSelectPatternTest, VectorFMinimum) {
373 parseAssembly(
374 "define <4 x float> @test(<4 x float> %a) {\n"
375 " %1 = fcmp ule <4 x float> %a, \n"
376 " <float 5.0, float 5.0, float 5.0, float 5.0>\n"
377 " %A = select <4 x i1> %1, <4 x float> %a,\n"
378 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n"
379 " ret <4 x float> %A\n"
380 "}\n");
381 // Check that pattern matching works on vectors where each lane has the same
382 // unordered pattern.
383 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
384 }
385
TEST_F(MatchSelectPatternTest,VectorFMinOtherOrdered)386 TEST_F(MatchSelectPatternTest, VectorFMinOtherOrdered) {
387 parseAssembly(
388 "define <4 x float> @test(<4 x float> %a) {\n"
389 " %1 = fcmp ole <4 x float> %a, \n"
390 " <float 5.0, float 5.0, float 5.0, float 5.0>\n"
391 " %A = select <4 x i1> %1, <4 x float> %a,\n"
392 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n"
393 " ret <4 x float> %A\n"
394 "}\n");
395 // Check that pattern matching works on vectors where each lane has the same
396 // ordered pattern.
397 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
398 }
399
TEST_F(MatchSelectPatternTest,VectorNotFMinimum)400 TEST_F(MatchSelectPatternTest, VectorNotFMinimum) {
401 parseAssembly(
402 "define <4 x float> @test(<4 x float> %a) {\n"
403 " %1 = fcmp ule <4 x float> %a, \n"
404 " <float 5.0, float 0x7ff8000000000000, float 5.0, float 5.0>\n"
405 " %A = select <4 x i1> %1, <4 x float> %a,\n"
406 " <4 x float> <float 5.0, float 0x7ff8000000000000, float 5.0, float "
407 "5.0>\n"
408 " ret <4 x float> %A\n"
409 "}\n");
410 // The lane that contains a NaN (0x7ff80...) behaves like a
411 // non-NaN-propagating min and the other lines behave like a NaN-propagating
412 // min, so check that neither is returned.
413 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
414 }
415
TEST_F(MatchSelectPatternTest,VectorNotFMinZero)416 TEST_F(MatchSelectPatternTest, VectorNotFMinZero) {
417 parseAssembly(
418 "define <4 x float> @test(<4 x float> %a) {\n"
419 " %1 = fcmp ule <4 x float> %a, \n"
420 " <float 5.0, float -0.0, float 5.0, float 5.0>\n"
421 " %A = select <4 x i1> %1, <4 x float> %a,\n"
422 " <4 x float> <float 5.0, float 0.0, float 5.0, float 5.0>\n"
423 " ret <4 x float> %A\n"
424 "}\n");
425 // Always selects the second lane of %a if it is positive or negative zero, so
426 // this is stricter than a min.
427 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
428 }
429
TEST_F(MatchSelectPatternTest,DoubleCastU)430 TEST_F(MatchSelectPatternTest, DoubleCastU) {
431 parseAssembly(
432 "define i32 @test(i8 %a, i8 %b) {\n"
433 " %1 = icmp ult i8 %a, %b\n"
434 " %2 = zext i8 %a to i32\n"
435 " %3 = zext i8 %b to i32\n"
436 " %A = select i1 %1, i32 %2, i32 %3\n"
437 " ret i32 %A\n"
438 "}\n");
439 // We should be able to look through the situation where we cast both operands
440 // to the select.
441 expectPattern({SPF_UMIN, SPNB_NA, false});
442 }
443
TEST_F(MatchSelectPatternTest,DoubleCastS)444 TEST_F(MatchSelectPatternTest, DoubleCastS) {
445 parseAssembly(
446 "define i32 @test(i8 %a, i8 %b) {\n"
447 " %1 = icmp slt i8 %a, %b\n"
448 " %2 = sext i8 %a to i32\n"
449 " %3 = sext i8 %b to i32\n"
450 " %A = select i1 %1, i32 %2, i32 %3\n"
451 " ret i32 %A\n"
452 "}\n");
453 // We should be able to look through the situation where we cast both operands
454 // to the select.
455 expectPattern({SPF_SMIN, SPNB_NA, false});
456 }
457
TEST_F(MatchSelectPatternTest,DoubleCastBad)458 TEST_F(MatchSelectPatternTest, DoubleCastBad) {
459 parseAssembly(
460 "define i32 @test(i8 %a, i8 %b) {\n"
461 " %1 = icmp ult i8 %a, %b\n"
462 " %2 = zext i8 %a to i32\n"
463 " %3 = sext i8 %b to i32\n"
464 " %A = select i1 %1, i32 %2, i32 %3\n"
465 " ret i32 %A\n"
466 "}\n");
467 // The cast types here aren't the same, so we cannot match an UMIN.
468 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
469 }
470
TEST_F(MatchSelectPatternTest,NotNotSMin)471 TEST_F(MatchSelectPatternTest, NotNotSMin) {
472 parseAssembly(
473 "define i8 @test(i8 %a, i8 %b) {\n"
474 " %cmp = icmp sgt i8 %a, %b\n"
475 " %an = xor i8 %a, -1\n"
476 " %bn = xor i8 %b, -1\n"
477 " %A = select i1 %cmp, i8 %an, i8 %bn\n"
478 " ret i8 %A\n"
479 "}\n");
480 expectPattern({SPF_SMIN, SPNB_NA, false});
481 }
482
TEST_F(MatchSelectPatternTest,NotNotSMinSwap)483 TEST_F(MatchSelectPatternTest, NotNotSMinSwap) {
484 parseAssembly(
485 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n"
486 " %cmp = icmp slt <2 x i8> %a, %b\n"
487 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n"
488 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n"
489 " %A = select <2 x i1> %cmp, <2 x i8> %bn, <2 x i8> %an\n"
490 " ret <2 x i8> %A\n"
491 "}\n");
492 expectPattern({SPF_SMIN, SPNB_NA, false});
493 }
494
TEST_F(MatchSelectPatternTest,NotNotSMax)495 TEST_F(MatchSelectPatternTest, NotNotSMax) {
496 parseAssembly(
497 "define i8 @test(i8 %a, i8 %b) {\n"
498 " %cmp = icmp slt i8 %a, %b\n"
499 " %an = xor i8 %a, -1\n"
500 " %bn = xor i8 %b, -1\n"
501 " %A = select i1 %cmp, i8 %an, i8 %bn\n"
502 " ret i8 %A\n"
503 "}\n");
504 expectPattern({SPF_SMAX, SPNB_NA, false});
505 }
506
TEST_F(MatchSelectPatternTest,NotNotSMaxSwap)507 TEST_F(MatchSelectPatternTest, NotNotSMaxSwap) {
508 parseAssembly(
509 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n"
510 " %cmp = icmp sgt <2 x i8> %a, %b\n"
511 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n"
512 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n"
513 " %A = select <2 x i1> %cmp, <2 x i8> %bn, <2 x i8> %an\n"
514 " ret <2 x i8> %A\n"
515 "}\n");
516 expectPattern({SPF_SMAX, SPNB_NA, false});
517 }
518
TEST_F(MatchSelectPatternTest,NotNotUMin)519 TEST_F(MatchSelectPatternTest, NotNotUMin) {
520 parseAssembly(
521 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n"
522 " %cmp = icmp ugt <2 x i8> %a, %b\n"
523 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n"
524 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n"
525 " %A = select <2 x i1> %cmp, <2 x i8> %an, <2 x i8> %bn\n"
526 " ret <2 x i8> %A\n"
527 "}\n");
528 expectPattern({SPF_UMIN, SPNB_NA, false});
529 }
530
TEST_F(MatchSelectPatternTest,NotNotUMinSwap)531 TEST_F(MatchSelectPatternTest, NotNotUMinSwap) {
532 parseAssembly(
533 "define i8 @test(i8 %a, i8 %b) {\n"
534 " %cmp = icmp ult i8 %a, %b\n"
535 " %an = xor i8 %a, -1\n"
536 " %bn = xor i8 %b, -1\n"
537 " %A = select i1 %cmp, i8 %bn, i8 %an\n"
538 " ret i8 %A\n"
539 "}\n");
540 expectPattern({SPF_UMIN, SPNB_NA, false});
541 }
542
TEST_F(MatchSelectPatternTest,NotNotUMax)543 TEST_F(MatchSelectPatternTest, NotNotUMax) {
544 parseAssembly(
545 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n"
546 " %cmp = icmp ult <2 x i8> %a, %b\n"
547 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n"
548 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n"
549 " %A = select <2 x i1> %cmp, <2 x i8> %an, <2 x i8> %bn\n"
550 " ret <2 x i8> %A\n"
551 "}\n");
552 expectPattern({SPF_UMAX, SPNB_NA, false});
553 }
554
TEST_F(MatchSelectPatternTest,NotNotUMaxSwap)555 TEST_F(MatchSelectPatternTest, NotNotUMaxSwap) {
556 parseAssembly(
557 "define i8 @test(i8 %a, i8 %b) {\n"
558 " %cmp = icmp ugt i8 %a, %b\n"
559 " %an = xor i8 %a, -1\n"
560 " %bn = xor i8 %b, -1\n"
561 " %A = select i1 %cmp, i8 %bn, i8 %an\n"
562 " ret i8 %A\n"
563 "}\n");
564 expectPattern({SPF_UMAX, SPNB_NA, false});
565 }
566
TEST_F(MatchSelectPatternTest,NotNotEq)567 TEST_F(MatchSelectPatternTest, NotNotEq) {
568 parseAssembly(
569 "define i8 @test(i8 %a, i8 %b) {\n"
570 " %cmp = icmp eq i8 %a, %b\n"
571 " %an = xor i8 %a, -1\n"
572 " %bn = xor i8 %b, -1\n"
573 " %A = select i1 %cmp, i8 %bn, i8 %an\n"
574 " ret i8 %A\n"
575 "}\n");
576 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
577 }
578
TEST_F(MatchSelectPatternTest,NotNotNe)579 TEST_F(MatchSelectPatternTest, NotNotNe) {
580 parseAssembly(
581 "define i8 @test(i8 %a, i8 %b) {\n"
582 " %cmp = icmp ne i8 %a, %b\n"
583 " %an = xor i8 %a, -1\n"
584 " %bn = xor i8 %b, -1\n"
585 " %A = select i1 %cmp, i8 %bn, i8 %an\n"
586 " ret i8 %A\n"
587 "}\n");
588 expectPattern({SPF_UNKNOWN, SPNB_NA, false});
589 }
590
TEST(ValueTracking,GuaranteedToTransferExecutionToSuccessor)591 TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) {
592 StringRef Assembly =
593 "declare void @nounwind_readonly(i32*) nounwind readonly "
594 "declare void @nounwind_argmemonly(i32*) nounwind argmemonly "
595 "declare void @throws_but_readonly(i32*) readonly "
596 "declare void @throws_but_argmemonly(i32*) argmemonly "
597 "declare void @nounwind_willreturn(i32*) nounwind willreturn"
598 " "
599 "declare void @unknown(i32*) "
600 " "
601 "define void @f(i32* %p) { "
602 " call void @nounwind_readonly(i32* %p) "
603 " call void @nounwind_argmemonly(i32* %p) "
604 " call void @throws_but_readonly(i32* %p) "
605 " call void @throws_but_argmemonly(i32* %p) "
606 " call void @unknown(i32* %p) nounwind readonly "
607 " call void @unknown(i32* %p) nounwind argmemonly "
608 " call void @unknown(i32* %p) readonly "
609 " call void @unknown(i32* %p) argmemonly "
610 " call void @nounwind_willreturn(i32* %p)"
611 " ret void "
612 "} ";
613
614 LLVMContext Context;
615 SMDiagnostic Error;
616 auto M = parseAssemblyString(Assembly, Error, Context);
617 assert(M && "Bad assembly?");
618
619 auto *F = M->getFunction("f");
620 assert(F && "Bad assembly?");
621
622 auto &BB = F->getEntryBlock();
623 bool ExpectedAnswers[] = {
624 true, // call void @nounwind_readonly(i32* %p)
625 true, // call void @nounwind_argmemonly(i32* %p)
626 false, // call void @throws_but_readonly(i32* %p)
627 false, // call void @throws_but_argmemonly(i32* %p)
628 true, // call void @unknown(i32* %p) nounwind readonly
629 true, // call void @unknown(i32* %p) nounwind argmemonly
630 false, // call void @unknown(i32* %p) readonly
631 false, // call void @unknown(i32* %p) argmemonly
632 true, // call void @nounwind_willreturn(i32* %p)
633 false, // ret void
634 };
635
636 int Index = 0;
637 for (auto &I : BB) {
638 EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I),
639 ExpectedAnswers[Index])
640 << "Incorrect answer at instruction " << Index << " = " << I;
641 Index++;
642 }
643 }
644
TEST_F(ValueTrackingTest,ComputeNumSignBits_PR32045)645 TEST_F(ValueTrackingTest, ComputeNumSignBits_PR32045) {
646 parseAssembly(
647 "define i32 @test(i32 %a) {\n"
648 " %A = ashr i32 %a, -1\n"
649 " ret i32 %A\n"
650 "}\n");
651 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
652 }
653
654 // No guarantees for canonical IR in this analysis, so this just bails out.
TEST_F(ValueTrackingTest,ComputeNumSignBits_Shuffle)655 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle) {
656 parseAssembly(
657 "define <2 x i32> @test() {\n"
658 " %A = shufflevector <2 x i32> undef, <2 x i32> undef, <2 x i32> <i32 0, i32 0>\n"
659 " ret <2 x i32> %A\n"
660 "}\n");
661 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
662 }
663
664 // No guarantees for canonical IR in this analysis, so a shuffle element that
665 // references an undef value means this can't return any extra information.
TEST_F(ValueTrackingTest,ComputeNumSignBits_Shuffle2)666 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) {
667 parseAssembly(
668 "define <2 x i32> @test(<2 x i1> %x) {\n"
669 " %sext = sext <2 x i1> %x to <2 x i32>\n"
670 " %A = shufflevector <2 x i32> %sext, <2 x i32> undef, <2 x i32> <i32 0, i32 2>\n"
671 " ret <2 x i32> %A\n"
672 "}\n");
673 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
674 }
675
TEST(ValueTracking,propagatesPoison)676 TEST(ValueTracking, propagatesPoison) {
677 std::string AsmHead = "declare i32 @g(i32)\n"
678 "define void @f(i32 %x, i32 %y, float %fx, float %fy, "
679 "i1 %cond, i8* %p) {\n";
680 std::string AsmTail = " ret void\n}";
681 // (propagates poison?, IR instruction)
682 SmallVector<std::pair<bool, std::string>, 32> Data = {
683 {true, "add i32 %x, %y"},
684 {true, "add nsw nuw i32 %x, %y"},
685 {true, "ashr i32 %x, %y"},
686 {true, "lshr exact i32 %x, 31"},
687 {true, "fcmp oeq float %fx, %fy"},
688 {true, "icmp eq i32 %x, %y"},
689 {true, "getelementptr i8, i8* %p, i32 %x"},
690 {true, "getelementptr inbounds i8, i8* %p, i32 %x"},
691 {true, "bitcast float %fx to i32"},
692 {false, "select i1 %cond, i32 %x, i32 %y"},
693 {false, "freeze i32 %x"},
694 {true, "udiv i32 %x, %y"},
695 {true, "urem i32 %x, %y"},
696 {true, "sdiv exact i32 %x, %y"},
697 {true, "srem i32 %x, %y"},
698 {false, "call i32 @g(i32 %x)"}};
699
700 std::string AssemblyStr = AsmHead;
701 for (auto &Itm : Data)
702 AssemblyStr += Itm.second + "\n";
703 AssemblyStr += AsmTail;
704
705 LLVMContext Context;
706 SMDiagnostic Error;
707 auto M = parseAssemblyString(AssemblyStr, Error, Context);
708 assert(M && "Bad assembly?");
709
710 auto *F = M->getFunction("f");
711 assert(F && "Bad assembly?");
712
713 auto &BB = F->getEntryBlock();
714
715 int Index = 0;
716 for (auto &I : BB) {
717 if (isa<ReturnInst>(&I))
718 break;
719 EXPECT_EQ(propagatesPoison(&I), Data[Index].first)
720 << "Incorrect answer at instruction " << Index << " = " << I;
721 Index++;
722 }
723 }
724
TEST(ValueTracking,canCreatePoison)725 TEST(ValueTracking, canCreatePoison) {
726 std::string AsmHead =
727 "declare i32 @g(i32)\n"
728 "define void @f(i32 %x, i32 %y, float %fx, float %fy, i1 %cond, "
729 "<4 x i32> %vx, <4 x i32> %vx2, <vscale x 4 x i32> %svx, i8* %p) {\n";
730 std::string AsmTail = " ret void\n}";
731 // (can create poison?, IR instruction)
732 SmallVector<std::pair<bool, std::string>, 32> Data = {
733 {false, "add i32 %x, %y"},
734 {true, "add nsw nuw i32 %x, %y"},
735 {true, "shl i32 %x, %y"},
736 {true, "shl <4 x i32> %vx, %vx2"},
737 {true, "shl nsw i32 %x, %y"},
738 {true, "shl nsw <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
739 {false, "shl i32 %x, 31"},
740 {true, "shl i32 %x, 32"},
741 {false, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
742 {true, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
743 {true, "ashr i32 %x, %y"},
744 {true, "ashr exact i32 %x, %y"},
745 {false, "ashr i32 %x, 31"},
746 {true, "ashr exact i32 %x, 31"},
747 {false, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
748 {true, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
749 {true, "ashr exact <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
750 {true, "lshr i32 %x, %y"},
751 {true, "lshr exact i32 %x, 31"},
752 {false, "udiv i32 %x, %y"},
753 {true, "udiv exact i32 %x, %y"},
754 {false, "getelementptr i8, i8* %p, i32 %x"},
755 {true, "getelementptr inbounds i8, i8* %p, i32 %x"},
756 {true, "fneg nnan float %fx"},
757 {false, "fneg float %fx"},
758 {false, "fadd float %fx, %fy"},
759 {true, "fadd nnan float %fx, %fy"},
760 {false, "urem i32 %x, %y"},
761 {true, "fptoui float %fx to i32"},
762 {true, "fptosi float %fx to i32"},
763 {false, "bitcast float %fx to i32"},
764 {false, "select i1 %cond, i32 %x, i32 %y"},
765 {true, "select nnan i1 %cond, float %fx, float %fy"},
766 {true, "extractelement <4 x i32> %vx, i32 %x"},
767 {false, "extractelement <4 x i32> %vx, i32 3"},
768 {true, "extractelement <vscale x 4 x i32> %svx, i32 4"},
769 {true, "insertelement <4 x i32> %vx, i32 %x, i32 %y"},
770 {false, "insertelement <4 x i32> %vx, i32 %x, i32 3"},
771 {true, "insertelement <vscale x 4 x i32> %svx, i32 %x, i32 4"},
772 {false, "freeze i32 %x"},
773 {true, "call i32 @g(i32 %x)"},
774 {true, "fcmp nnan oeq float %fx, %fy"},
775 {false, "fcmp oeq float %fx, %fy"}};
776
777 std::string AssemblyStr = AsmHead;
778 for (auto &Itm : Data)
779 AssemblyStr += Itm.second + "\n";
780 AssemblyStr += AsmTail;
781
782 LLVMContext Context;
783 SMDiagnostic Error;
784 auto M = parseAssemblyString(AssemblyStr, Error, Context);
785 assert(M && "Bad assembly?");
786
787 auto *F = M->getFunction("f");
788 assert(F && "Bad assembly?");
789
790 auto &BB = F->getEntryBlock();
791
792 int Index = 0;
793 for (auto &I : BB) {
794 if (isa<ReturnInst>(&I))
795 break;
796 EXPECT_EQ(canCreatePoison(&I), Data[Index].first)
797 << "Incorrect answer at instruction " << Index << " = " << I;
798 Index++;
799 }
800 }
801
TEST_F(ComputeKnownBitsTest,ComputeKnownBits)802 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
803 parseAssembly(
804 "define i32 @test(i32 %a, i32 %b) {\n"
805 " %ash = mul i32 %a, 8\n"
806 " %aad = add i32 %ash, 7\n"
807 " %aan = and i32 %aad, 4095\n"
808 " %bsh = shl i32 %b, 4\n"
809 " %bad = or i32 %bsh, 6\n"
810 " %ban = and i32 %bad, 4095\n"
811 " %A = mul i32 %aan, %ban\n"
812 " ret i32 %A\n"
813 "}\n");
814 expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u);
815 }
816
TEST_F(ComputeKnownBitsTest,ComputeKnownMulBits)817 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) {
818 parseAssembly(
819 "define i32 @test(i32 %a, i32 %b) {\n"
820 " %aa = shl i32 %a, 5\n"
821 " %bb = shl i32 %b, 5\n"
822 " %aaa = or i32 %aa, 24\n"
823 " %bbb = or i32 %bb, 28\n"
824 " %A = mul i32 %aaa, %bbb\n"
825 " ret i32 %A\n"
826 "}\n");
827 expectKnownBits(/*zero*/ 95u, /*one*/ 32u);
828 }
829
TEST_F(ComputeKnownBitsTest,KnownNonZeroShift)830 TEST_F(ComputeKnownBitsTest, KnownNonZeroShift) {
831 // %q is known nonzero without known bits.
832 // Because %q is nonzero, %A[0] is known to be zero.
833 parseAssembly(
834 "define i8 @test(i8 %p, i8* %pq) {\n"
835 " %q = load i8, i8* %pq, !range !0\n"
836 " %A = shl i8 %p, %q\n"
837 " ret i8 %A\n"
838 "}\n"
839 "!0 = !{ i8 1, i8 5 }\n");
840 expectKnownBits(/*zero*/ 1u, /*one*/ 0u);
841 }
842
TEST_F(ComputeKnownBitsTest,ComputeKnownFshl)843 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) {
844 // fshl(....1111....0000, 00..1111........, 6)
845 // = 11....000000..11
846 parseAssembly(
847 "define i16 @test(i16 %a, i16 %b) {\n"
848 " %aa = shl i16 %a, 4\n"
849 " %bb = lshr i16 %b, 2\n"
850 " %aaa = or i16 %aa, 3840\n"
851 " %bbb = or i16 %bb, 3840\n"
852 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n"
853 " ret i16 %A\n"
854 "}\n"
855 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
856 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
857 }
858
TEST_F(ComputeKnownBitsTest,ComputeKnownFshr)859 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) {
860 // fshr(....1111....0000, 00..1111........, 26)
861 // = 11....000000..11
862 parseAssembly(
863 "define i16 @test(i16 %a, i16 %b) {\n"
864 " %aa = shl i16 %a, 4\n"
865 " %bb = lshr i16 %b, 2\n"
866 " %aaa = or i16 %aa, 3840\n"
867 " %bbb = or i16 %bb, 3840\n"
868 " %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n"
869 " ret i16 %A\n"
870 "}\n"
871 "declare i16 @llvm.fshr.i16(i16, i16, i16)\n");
872 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
873 }
874
TEST_F(ComputeKnownBitsTest,ComputeKnownFshlZero)875 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) {
876 // fshl(....1111....0000, 00..1111........, 0)
877 // = ....1111....0000
878 parseAssembly(
879 "define i16 @test(i16 %a, i16 %b) {\n"
880 " %aa = shl i16 %a, 4\n"
881 " %bb = lshr i16 %b, 2\n"
882 " %aaa = or i16 %aa, 3840\n"
883 " %bbb = or i16 %bb, 3840\n"
884 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n"
885 " ret i16 %A\n"
886 "}\n"
887 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
888 expectKnownBits(/*zero*/ 15u, /*one*/ 3840u);
889 }
890
TEST_F(ComputeKnownBitsTest,ComputeKnownUAddSatLeadingOnes)891 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) {
892 // uadd.sat(1111...1, ........)
893 // = 1111....
894 parseAssembly(
895 "define i8 @test(i8 %a, i8 %b) {\n"
896 " %aa = or i8 %a, 241\n"
897 " %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n"
898 " ret i8 %A\n"
899 "}\n"
900 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
901 expectKnownBits(/*zero*/ 0u, /*one*/ 240u);
902 }
903
TEST_F(ComputeKnownBitsTest,ComputeKnownUAddSatOnesPreserved)904 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) {
905 // uadd.sat(00...011, .1...110)
906 // = .......1
907 parseAssembly(
908 "define i8 @test(i8 %a, i8 %b) {\n"
909 " %aa = or i8 %a, 3\n"
910 " %aaa = and i8 %aa, 59\n"
911 " %bb = or i8 %b, 70\n"
912 " %bbb = and i8 %bb, 254\n"
913 " %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n"
914 " ret i8 %A\n"
915 "}\n"
916 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
917 expectKnownBits(/*zero*/ 0u, /*one*/ 1u);
918 }
919
TEST_F(ComputeKnownBitsTest,ComputeKnownUSubSatLHSLeadingZeros)920 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) {
921 // usub.sat(0000...0, ........)
922 // = 0000....
923 parseAssembly(
924 "define i8 @test(i8 %a, i8 %b) {\n"
925 " %aa = and i8 %a, 14\n"
926 " %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n"
927 " ret i8 %A\n"
928 "}\n"
929 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
930 expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
931 }
932
TEST_F(ComputeKnownBitsTest,ComputeKnownUSubSatRHSLeadingOnes)933 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) {
934 // usub.sat(........, 1111...1)
935 // = 0000....
936 parseAssembly(
937 "define i8 @test(i8 %a, i8 %b) {\n"
938 " %bb = or i8 %a, 241\n"
939 " %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n"
940 " ret i8 %A\n"
941 "}\n"
942 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
943 expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
944 }
945
TEST_F(ComputeKnownBitsTest,ComputeKnownUSubSatZerosPreserved)946 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) {
947 // usub.sat(11...011, .1...110)
948 // = ......0.
949 parseAssembly(
950 "define i8 @test(i8 %a, i8 %b) {\n"
951 " %aa = or i8 %a, 195\n"
952 " %aaa = and i8 %aa, 251\n"
953 " %bb = or i8 %b, 70\n"
954 " %bbb = and i8 %bb, 254\n"
955 " %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
956 " ret i8 %A\n"
957 "}\n"
958 "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
959 expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
960 }
961
TEST_F(ComputeKnownBitsTest,ComputeKnownBitsPtrToIntTrunc)962 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntTrunc) {
963 // ptrtoint truncates the pointer type.
964 parseAssembly(
965 "define void @test(i8** %p) {\n"
966 " %A = load i8*, i8** %p\n"
967 " %i = ptrtoint i8* %A to i32\n"
968 " %m = and i32 %i, 31\n"
969 " %c = icmp eq i32 %m, 0\n"
970 " call void @llvm.assume(i1 %c)\n"
971 " ret void\n"
972 "}\n"
973 "declare void @llvm.assume(i1)\n");
974 AssumptionCache AC(*F);
975 KnownBits Known = computeKnownBits(
976 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
977 EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
978 EXPECT_EQ(Known.One.getZExtValue(), 0u);
979 }
980
TEST_F(ComputeKnownBitsTest,ComputeKnownBitsPtrToIntZext)981 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntZext) {
982 // ptrtoint zero extends the pointer type.
983 parseAssembly(
984 "define void @test(i8** %p) {\n"
985 " %A = load i8*, i8** %p\n"
986 " %i = ptrtoint i8* %A to i128\n"
987 " %m = and i128 %i, 31\n"
988 " %c = icmp eq i128 %m, 0\n"
989 " call void @llvm.assume(i1 %c)\n"
990 " ret void\n"
991 "}\n"
992 "declare void @llvm.assume(i1)\n");
993 AssumptionCache AC(*F);
994 KnownBits Known = computeKnownBits(
995 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
996 EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
997 EXPECT_EQ(Known.One.getZExtValue(), 0u);
998 }
999
1000 class IsBytewiseValueTest : public ValueTrackingTest,
1001 public ::testing::WithParamInterface<
1002 std::pair<const char *, const char *>> {
1003 protected:
1004 };
1005
1006 const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
1007 {
1008 "i8 0",
1009 "i48* null",
1010 },
1011 {
1012 "i8 undef",
1013 "i48* undef",
1014 },
1015 {
1016 "i8 0",
1017 "i8 zeroinitializer",
1018 },
1019 {
1020 "i8 0",
1021 "i8 0",
1022 },
1023 {
1024 "i8 -86",
1025 "i8 -86",
1026 },
1027 {
1028 "i8 -1",
1029 "i8 -1",
1030 },
1031 {
1032 "i8 undef",
1033 "i16 undef",
1034 },
1035 {
1036 "i8 0",
1037 "i16 0",
1038 },
1039 {
1040 "",
1041 "i16 7",
1042 },
1043 {
1044 "i8 -86",
1045 "i16 -21846",
1046 },
1047 {
1048 "i8 -1",
1049 "i16 -1",
1050 },
1051 {
1052 "i8 0",
1053 "i48 0",
1054 },
1055 {
1056 "i8 -1",
1057 "i48 -1",
1058 },
1059 {
1060 "i8 0",
1061 "i49 0",
1062 },
1063 {
1064 "",
1065 "i49 -1",
1066 },
1067 {
1068 "i8 0",
1069 "half 0xH0000",
1070 },
1071 {
1072 "i8 -85",
1073 "half 0xHABAB",
1074 },
1075 {
1076 "i8 0",
1077 "float 0.0",
1078 },
1079 {
1080 "i8 -1",
1081 "float 0xFFFFFFFFE0000000",
1082 },
1083 {
1084 "i8 0",
1085 "double 0.0",
1086 },
1087 {
1088 "i8 -15",
1089 "double 0xF1F1F1F1F1F1F1F1",
1090 },
1091 {
1092 "i8 undef",
1093 "i16* undef",
1094 },
1095 {
1096 "i8 0",
1097 "i16* inttoptr (i64 0 to i16*)",
1098 },
1099 {
1100 "i8 -1",
1101 "i16* inttoptr (i64 -1 to i16*)",
1102 },
1103 {
1104 "i8 -86",
1105 "i16* inttoptr (i64 -6148914691236517206 to i16*)",
1106 },
1107 {
1108 "",
1109 "i16* inttoptr (i48 -1 to i16*)",
1110 },
1111 {
1112 "i8 -1",
1113 "i16* inttoptr (i96 -1 to i16*)",
1114 },
1115 {
1116 "i8 undef",
1117 "[0 x i8] zeroinitializer",
1118 },
1119 {
1120 "i8 undef",
1121 "[0 x i8] undef",
1122 },
1123 {
1124 "i8 undef",
1125 "[5 x [0 x i8]] zeroinitializer",
1126 },
1127 {
1128 "i8 undef",
1129 "[5 x [0 x i8]] undef",
1130 },
1131 {
1132 "i8 0",
1133 "[6 x i8] zeroinitializer",
1134 },
1135 {
1136 "i8 undef",
1137 "[6 x i8] undef",
1138 },
1139 {
1140 "i8 1",
1141 "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]",
1142 },
1143 {
1144 "",
1145 "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]",
1146 },
1147 {
1148 "i8 -1",
1149 "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]",
1150 },
1151 {
1152 "",
1153 "[4 x i8] [i8 1, i8 2, i8 1, i8 1]",
1154 },
1155 {
1156 "i8 1",
1157 "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]",
1158 },
1159 {
1160 "i8 0",
1161 "<6 x i8> zeroinitializer",
1162 },
1163 {
1164 "i8 undef",
1165 "<6 x i8> undef",
1166 },
1167 {
1168 "i8 1",
1169 "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>",
1170 },
1171 {
1172 "",
1173 "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>",
1174 },
1175 {
1176 "i8 -1",
1177 "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>",
1178 },
1179 {
1180 "",
1181 "<4 x i8> <i8 1, i8 1, i8 2, i8 1>",
1182 },
1183 {
1184 "i8 5",
1185 "<2 x i8> < i8 5, i8 undef >",
1186 },
1187 {
1188 "i8 0",
1189 "[2 x [2 x i16]] zeroinitializer",
1190 },
1191 {
1192 "i8 undef",
1193 "[2 x [2 x i16]] undef",
1194 },
1195 {
1196 "i8 -86",
1197 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
1198 "[2 x i16] [i16 -21846, i16 -21846]]",
1199 },
1200 {
1201 "",
1202 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
1203 "[2 x i16] [i16 -21836, i16 -21846]]",
1204 },
1205 {
1206 "i8 undef",
1207 "{ } zeroinitializer",
1208 },
1209 {
1210 "i8 undef",
1211 "{ } undef",
1212 },
1213 {
1214 "i8 undef",
1215 "{ {}, {} } zeroinitializer",
1216 },
1217 {
1218 "i8 undef",
1219 "{ {}, {} } undef",
1220 },
1221 {
1222 "i8 0",
1223 "{i8, i64, i16*} zeroinitializer",
1224 },
1225 {
1226 "i8 undef",
1227 "{i8, i64, i16*} undef",
1228 },
1229 {
1230 "i8 -86",
1231 "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}",
1232 },
1233 {
1234 "",
1235 "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}",
1236 },
1237 };
1238
1239 INSTANTIATE_TEST_CASE_P(IsBytewiseValueParamTests, IsBytewiseValueTest,
1240 ::testing::ValuesIn(IsBytewiseValueTests),);
1241
TEST_P(IsBytewiseValueTest,IsBytewiseValue)1242 TEST_P(IsBytewiseValueTest, IsBytewiseValue) {
1243 auto M = parseModule(std::string("@test = global ") + GetParam().second);
1244 GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
1245 Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout());
1246 std::string Buff;
1247 raw_string_ostream S(Buff);
1248 if (Actual)
1249 S << *Actual;
1250 EXPECT_EQ(GetParam().first, S.str());
1251 }
1252
TEST_F(ValueTrackingTest,ComputeConstantRange)1253 TEST_F(ValueTrackingTest, ComputeConstantRange) {
1254 {
1255 // Assumptions:
1256 // * stride >= 5
1257 // * stride < 10
1258 //
1259 // stride = [5, 10)
1260 auto M = parseModule(R"(
1261 declare void @llvm.assume(i1)
1262
1263 define i32 @test(i32 %stride) {
1264 %gt = icmp uge i32 %stride, 5
1265 call void @llvm.assume(i1 %gt)
1266 %lt = icmp ult i32 %stride, 10
1267 call void @llvm.assume(i1 %lt)
1268 %stride.plus.one = add nsw nuw i32 %stride, 1
1269 ret i32 %stride.plus.one
1270 })");
1271 Function *F = M->getFunction("test");
1272
1273 AssumptionCache AC(*F);
1274 Value *Stride = &*F->arg_begin();
1275 ConstantRange CR1 = computeConstantRange(Stride, true, &AC, nullptr);
1276 EXPECT_TRUE(CR1.isFullSet());
1277
1278 Instruction *I = &findInstructionByName(F, "stride.plus.one");
1279 ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I);
1280 EXPECT_EQ(5, CR2.getLower());
1281 EXPECT_EQ(10, CR2.getUpper());
1282 }
1283
1284 {
1285 // Assumptions:
1286 // * stride >= 5
1287 // * stride < 200
1288 // * stride == 99
1289 //
1290 // stride = [99, 100)
1291 auto M = parseModule(R"(
1292 declare void @llvm.assume(i1)
1293
1294 define i32 @test(i32 %stride) {
1295 %gt = icmp uge i32 %stride, 5
1296 call void @llvm.assume(i1 %gt)
1297 %lt = icmp ult i32 %stride, 200
1298 call void @llvm.assume(i1 %lt)
1299 %eq = icmp eq i32 %stride, 99
1300 call void @llvm.assume(i1 %eq)
1301 %stride.plus.one = add nsw nuw i32 %stride, 1
1302 ret i32 %stride.plus.one
1303 })");
1304 Function *F = M->getFunction("test");
1305
1306 AssumptionCache AC(*F);
1307 Value *Stride = &*F->arg_begin();
1308 Instruction *I = &findInstructionByName(F, "stride.plus.one");
1309 ConstantRange CR = computeConstantRange(Stride, true, &AC, I);
1310 EXPECT_EQ(99, *CR.getSingleElement());
1311 }
1312
1313 {
1314 // Assumptions:
1315 // * stride >= 5
1316 // * stride >= 50
1317 // * stride < 100
1318 // * stride < 200
1319 //
1320 // stride = [50, 100)
1321 auto M = parseModule(R"(
1322 declare void @llvm.assume(i1)
1323
1324 define i32 @test(i32 %stride, i1 %cond) {
1325 %gt = icmp uge i32 %stride, 5
1326 call void @llvm.assume(i1 %gt)
1327 %gt.2 = icmp uge i32 %stride, 50
1328 call void @llvm.assume(i1 %gt.2)
1329 br i1 %cond, label %bb1, label %bb2
1330
1331 bb1:
1332 %lt = icmp ult i32 %stride, 200
1333 call void @llvm.assume(i1 %lt)
1334 %lt.2 = icmp ult i32 %stride, 100
1335 call void @llvm.assume(i1 %lt.2)
1336 %stride.plus.one = add nsw nuw i32 %stride, 1
1337 ret i32 %stride.plus.one
1338
1339 bb2:
1340 ret i32 0
1341 })");
1342 Function *F = M->getFunction("test");
1343
1344 AssumptionCache AC(*F);
1345 Value *Stride = &*F->arg_begin();
1346 Instruction *GT2 = &findInstructionByName(F, "gt.2");
1347 ConstantRange CR = computeConstantRange(Stride, true, &AC, GT2);
1348 EXPECT_EQ(5, CR.getLower());
1349 EXPECT_EQ(0, CR.getUpper());
1350
1351 Instruction *I = &findInstructionByName(F, "stride.plus.one");
1352 ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I);
1353 EXPECT_EQ(50, CR2.getLower());
1354 EXPECT_EQ(100, CR2.getUpper());
1355 }
1356
1357 {
1358 // Assumptions:
1359 // * stride > 5
1360 // * stride < 5
1361 //
1362 // stride = empty range, as the assumptions contradict each other.
1363 auto M = parseModule(R"(
1364 declare void @llvm.assume(i1)
1365
1366 define i32 @test(i32 %stride, i1 %cond) {
1367 %gt = icmp ugt i32 %stride, 5
1368 call void @llvm.assume(i1 %gt)
1369 %lt = icmp ult i32 %stride, 5
1370 call void @llvm.assume(i1 %lt)
1371 %stride.plus.one = add nsw nuw i32 %stride, 1
1372 ret i32 %stride.plus.one
1373 })");
1374 Function *F = M->getFunction("test");
1375
1376 AssumptionCache AC(*F);
1377 Value *Stride = &*F->arg_begin();
1378
1379 Instruction *I = &findInstructionByName(F, "stride.plus.one");
1380 ConstantRange CR = computeConstantRange(Stride, true, &AC, I);
1381 EXPECT_TRUE(CR.isEmptySet());
1382 }
1383
1384 {
1385 // Assumptions:
1386 // * x.1 >= 5
1387 // * x.2 < x.1
1388 //
1389 // stride = [0, 5)
1390 auto M = parseModule(R"(
1391 declare void @llvm.assume(i1)
1392
1393 define i32 @test(i32 %x.1, i32 %x.2) {
1394 %gt = icmp uge i32 %x.1, 5
1395 call void @llvm.assume(i1 %gt)
1396 %lt = icmp ult i32 %x.2, %x.1
1397 call void @llvm.assume(i1 %lt)
1398 %stride.plus.one = add nsw nuw i32 %x.1, 1
1399 ret i32 %stride.plus.one
1400 })");
1401 Function *F = M->getFunction("test");
1402
1403 AssumptionCache AC(*F);
1404 Value *X2 = &*std::next(F->arg_begin());
1405
1406 Instruction *I = &findInstructionByName(F, "stride.plus.one");
1407 ConstantRange CR1 = computeConstantRange(X2, true, &AC, I);
1408 EXPECT_EQ(0, CR1.getLower());
1409 EXPECT_EQ(5, CR1.getUpper());
1410
1411 // Check the depth cutoff results in a conservative result (full set) by
1412 // passing Depth == MaxDepth == 6.
1413 ConstantRange CR2 = computeConstantRange(X2, true, &AC, I, 6);
1414 EXPECT_TRUE(CR2.isFullSet());
1415 }
1416 }
1417