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/AsmParser/Parser.h"
11 #include "llvm/IR/Function.h"
12 #include "llvm/IR/InstIterator.h"
13 #include "llvm/IR/LLVMContext.h"
14 #include "llvm/IR/Module.h"
15 #include "llvm/Support/ErrorHandling.h"
16 #include "llvm/Support/KnownBits.h"
17 #include "llvm/Support/SourceMgr.h"
18 #include "gtest/gtest.h"
19 
20 using namespace llvm;
21 
22 namespace {
23 
24 class ValueTrackingTest : public testing::Test {
25 protected:
26   std::unique_ptr<Module> parseModule(StringRef Assembly) {
27     SMDiagnostic Error;
28     std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
29 
30     std::string errMsg;
31     raw_string_ostream os(errMsg);
32     Error.print("", os);
33     EXPECT_TRUE(M) << os.str();
34 
35     return M;
36   }
37 
38   void parseAssembly(StringRef Assembly) {
39     M = parseModule(Assembly);
40     ASSERT_TRUE(M);
41 
42     Function *F = M->getFunction("test");
43     ASSERT_TRUE(F) << "Test must have a function @test";
44     if (!F)
45       return;
46 
47     A = nullptr;
48     for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
49       if (I->hasName()) {
50         if (I->getName() == "A")
51           A = &*I;
52       }
53     }
54     ASSERT_TRUE(A) << "@test must have an instruction %A";
55   }
56 
57   LLVMContext Context;
58   std::unique_ptr<Module> M;
59   Instruction *A = nullptr;
60 };
61 
62 class MatchSelectPatternTest : public ValueTrackingTest {
63 protected:
64   void expectPattern(const SelectPatternResult &P) {
65     Value *LHS, *RHS;
66     Instruction::CastOps CastOp;
67     SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp);
68     EXPECT_EQ(P.Flavor, R.Flavor);
69     EXPECT_EQ(P.NaNBehavior, R.NaNBehavior);
70     EXPECT_EQ(P.Ordered, R.Ordered);
71   }
72 };
73 
74 class ComputeKnownBitsTest : public ValueTrackingTest {
75 protected:
76   void expectKnownBits(uint64_t Zero, uint64_t One) {
77     auto Known = computeKnownBits(A, M->getDataLayout());
78     ASSERT_FALSE(Known.hasConflict());
79     EXPECT_EQ(Known.One.getZExtValue(), One);
80     EXPECT_EQ(Known.Zero.getZExtValue(), Zero);
81   }
82 };
83 
84 }
85 
86 TEST_F(MatchSelectPatternTest, SimpleFMin) {
87   parseAssembly(
88       "define float @test(float %a) {\n"
89       "  %1 = fcmp ult float %a, 5.0\n"
90       "  %A = select i1 %1, float %a, float 5.0\n"
91       "  ret float %A\n"
92       "}\n");
93   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
94 }
95 
96 TEST_F(MatchSelectPatternTest, SimpleFMax) {
97   parseAssembly(
98       "define float @test(float %a) {\n"
99       "  %1 = fcmp ogt float %a, 5.0\n"
100       "  %A = select i1 %1, float %a, float 5.0\n"
101       "  ret float %A\n"
102       "}\n");
103   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
104 }
105 
106 TEST_F(MatchSelectPatternTest, SwappedFMax) {
107   parseAssembly(
108       "define float @test(float %a) {\n"
109       "  %1 = fcmp olt float 5.0, %a\n"
110       "  %A = select i1 %1, float %a, float 5.0\n"
111       "  ret float %A\n"
112       "}\n");
113   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
114 }
115 
116 TEST_F(MatchSelectPatternTest, SwappedFMax2) {
117   parseAssembly(
118       "define float @test(float %a) {\n"
119       "  %1 = fcmp olt float %a, 5.0\n"
120       "  %A = select i1 %1, float 5.0, float %a\n"
121       "  ret float %A\n"
122       "}\n");
123   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
124 }
125 
126 TEST_F(MatchSelectPatternTest, SwappedFMax3) {
127   parseAssembly(
128       "define float @test(float %a) {\n"
129       "  %1 = fcmp ult float %a, 5.0\n"
130       "  %A = select i1 %1, float 5.0, float %a\n"
131       "  ret float %A\n"
132       "}\n");
133   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
134 }
135 
136 TEST_F(MatchSelectPatternTest, FastFMin) {
137   parseAssembly(
138       "define float @test(float %a) {\n"
139       "  %1 = fcmp nnan olt float %a, 5.0\n"
140       "  %A = select i1 %1, float %a, float 5.0\n"
141       "  ret float %A\n"
142       "}\n");
143   expectPattern({SPF_FMINNUM, SPNB_RETURNS_ANY, false});
144 }
145 
146 TEST_F(MatchSelectPatternTest, FMinConstantZero) {
147   parseAssembly(
148       "define float @test(float %a) {\n"
149       "  %1 = fcmp ole float %a, 0.0\n"
150       "  %A = select i1 %1, float %a, float 0.0\n"
151       "  ret float %A\n"
152       "}\n");
153   // This shouldn't be matched, as %a could be -0.0.
154   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
155 }
156 
157 TEST_F(MatchSelectPatternTest, FMinConstantZeroNsz) {
158   parseAssembly(
159       "define float @test(float %a) {\n"
160       "  %1 = fcmp nsz ole float %a, 0.0\n"
161       "  %A = select i1 %1, float %a, float 0.0\n"
162       "  ret float %A\n"
163       "}\n");
164   // But this should be, because we've ignored signed zeroes.
165   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
166 }
167 
168 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero1) {
169   parseAssembly(
170       "define float @test(float %a) {\n"
171       "  %1 = fcmp olt float -0.0, %a\n"
172       "  %A = select i1 %1, float 0.0, float %a\n"
173       "  ret float %A\n"
174       "}\n");
175   // The sign of zero doesn't matter in fcmp.
176   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, true});
177 }
178 
179 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero2) {
180   parseAssembly(
181       "define float @test(float %a) {\n"
182       "  %1 = fcmp ogt float %a, -0.0\n"
183       "  %A = select i1 %1, float 0.0, float %a\n"
184       "  ret float %A\n"
185       "}\n");
186   // The sign of zero doesn't matter in fcmp.
187   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
188 }
189 
190 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero3) {
191   parseAssembly(
192       "define float @test(float %a) {\n"
193       "  %1 = fcmp olt float 0.0, %a\n"
194       "  %A = select i1 %1, float -0.0, float %a\n"
195       "  ret float %A\n"
196       "}\n");
197   // The sign of zero doesn't matter in fcmp.
198   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, true});
199 }
200 
201 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero4) {
202   parseAssembly(
203       "define float @test(float %a) {\n"
204       "  %1 = fcmp ogt float %a, 0.0\n"
205       "  %A = select i1 %1, float -0.0, float %a\n"
206       "  ret float %A\n"
207       "}\n");
208   // The sign of zero doesn't matter in fcmp.
209   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
210 }
211 
212 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero5) {
213   parseAssembly(
214       "define float @test(float %a) {\n"
215       "  %1 = fcmp ogt float -0.0, %a\n"
216       "  %A = select i1 %1, float %a, float 0.0\n"
217       "  ret float %A\n"
218       "}\n");
219   // The sign of zero doesn't matter in fcmp.
220   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, false});
221 }
222 
223 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero6) {
224   parseAssembly(
225       "define float @test(float %a) {\n"
226       "  %1 = fcmp olt float %a, -0.0\n"
227       "  %A = select i1 %1, float %a, float 0.0\n"
228       "  ret float %A\n"
229       "}\n");
230   // The sign of zero doesn't matter in fcmp.
231   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
232 }
233 
234 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero7) {
235   parseAssembly(
236       "define float @test(float %a) {\n"
237       "  %1 = fcmp ogt float 0.0, %a\n"
238       "  %A = select i1 %1, float %a, float -0.0\n"
239       "  ret float %A\n"
240       "}\n");
241   // The sign of zero doesn't matter in fcmp.
242   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, false});
243 }
244 
245 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero8) {
246   parseAssembly(
247       "define float @test(float %a) {\n"
248       "  %1 = fcmp olt float %a, 0.0\n"
249       "  %A = select i1 %1, float %a, float -0.0\n"
250       "  ret float %A\n"
251       "}\n");
252   // The sign of zero doesn't matter in fcmp.
253   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
254 }
255 
256 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero1) {
257   parseAssembly(
258       "define float @test(float %a) {\n"
259       "  %1 = fcmp ogt float -0.0, %a\n"
260       "  %A = select i1 %1, float 0.0, float %a\n"
261       "  ret float %A\n"
262       "}\n");
263   // The sign of zero doesn't matter in fcmp.
264   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, true});
265 }
266 
267 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero2) {
268   parseAssembly(
269       "define float @test(float %a) {\n"
270       "  %1 = fcmp olt float %a, -0.0\n"
271       "  %A = select i1 %1, float 0.0, float %a\n"
272       "  ret float %A\n"
273       "}\n");
274   // The sign of zero doesn't matter in fcmp.
275   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
276 }
277 
278 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero3) {
279   parseAssembly(
280       "define float @test(float %a) {\n"
281       "  %1 = fcmp ogt float 0.0, %a\n"
282       "  %A = select i1 %1, float -0.0, float %a\n"
283       "  ret float %A\n"
284       "}\n");
285   // The sign of zero doesn't matter in fcmp.
286   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, true});
287 }
288 
289 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero4) {
290   parseAssembly(
291       "define float @test(float %a) {\n"
292       "  %1 = fcmp olt float %a, 0.0\n"
293       "  %A = select i1 %1, float -0.0, float %a\n"
294       "  ret float %A\n"
295       "}\n");
296   // The sign of zero doesn't matter in fcmp.
297   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
298 }
299 
300 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero5) {
301   parseAssembly(
302       "define float @test(float %a) {\n"
303       "  %1 = fcmp olt float -0.0, %a\n"
304       "  %A = select i1 %1, float %a, float 0.0\n"
305       "  ret float %A\n"
306       "}\n");
307   // The sign of zero doesn't matter in fcmp.
308   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
309 }
310 
311 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero6) {
312   parseAssembly(
313       "define float @test(float %a) {\n"
314       "  %1 = fcmp ogt float %a, -0.0\n"
315       "  %A = select i1 %1, float %a, float 0.0\n"
316       "  ret float %A\n"
317       "}\n");
318   // The sign of zero doesn't matter in fcmp.
319   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
320 }
321 
322 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero7) {
323   parseAssembly(
324       "define float @test(float %a) {\n"
325       "  %1 = fcmp olt float 0.0, %a\n"
326       "  %A = select i1 %1, float %a, float -0.0\n"
327       "  ret float %A\n"
328       "}\n");
329   // The sign of zero doesn't matter in fcmp.
330   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
331 }
332 
333 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero8) {
334   parseAssembly(
335       "define float @test(float %a) {\n"
336       "  %1 = fcmp ogt float %a, 0.0\n"
337       "  %A = select i1 %1, float %a, float -0.0\n"
338       "  ret float %A\n"
339       "}\n");
340   // The sign of zero doesn't matter in fcmp.
341   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
342 }
343 
344 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZeroVecUndef) {
345   parseAssembly(
346       "define <2 x float> @test(<2 x float> %a) {\n"
347       "  %1 = fcmp ogt <2 x float> %a, <float -0.0, float -0.0>\n"
348       "  %A = select <2 x i1> %1, <2 x float> <float undef, float 0.0>, <2 x float> %a\n"
349       "  ret <2 x float> %A\n"
350       "}\n");
351   // An undef in a vector constant can not be back-propagated for this analysis.
352   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
353 }
354 
355 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZeroVecUndef) {
356   parseAssembly(
357       "define <2 x float> @test(<2 x float> %a) {\n"
358       "  %1 = fcmp ogt <2 x float> %a, zeroinitializer\n"
359       "  %A = select <2 x i1> %1, <2 x float> %a, <2 x float> <float -0.0, float undef>\n"
360       "  ret <2 x float> %A\n"
361       "}\n");
362   // An undef in a vector constant can not be back-propagated for this analysis.
363   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
364 }
365 
366 TEST_F(MatchSelectPatternTest, VectorFMinimum) {
367   parseAssembly(
368       "define <4 x float> @test(<4 x float> %a) {\n"
369       "  %1 = fcmp ule <4 x float> %a, \n"
370       "    <float 5.0, float 5.0, float 5.0, float 5.0>\n"
371       "  %A = select <4 x i1> %1, <4 x float> %a,\n"
372       "     <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n"
373       "  ret <4 x float> %A\n"
374       "}\n");
375   // Check that pattern matching works on vectors where each lane has the same
376   // unordered pattern.
377   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
378 }
379 
380 TEST_F(MatchSelectPatternTest, VectorFMinOtherOrdered) {
381   parseAssembly(
382       "define <4 x float> @test(<4 x float> %a) {\n"
383       "  %1 = fcmp ole <4 x float> %a, \n"
384       "    <float 5.0, float 5.0, float 5.0, float 5.0>\n"
385       "  %A = select <4 x i1> %1, <4 x float> %a,\n"
386       "     <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n"
387       "  ret <4 x float> %A\n"
388       "}\n");
389   // Check that pattern matching works on vectors where each lane has the same
390   // ordered pattern.
391   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
392 }
393 
394 TEST_F(MatchSelectPatternTest, VectorNotFMinimum) {
395   parseAssembly(
396       "define <4 x float> @test(<4 x float> %a) {\n"
397       "  %1 = fcmp ule <4 x float> %a, \n"
398       "    <float 5.0, float 0x7ff8000000000000, float 5.0, float 5.0>\n"
399       "  %A = select <4 x i1> %1, <4 x float> %a,\n"
400       "     <4 x float> <float 5.0, float 0x7ff8000000000000, float 5.0, float "
401       "5.0>\n"
402       "  ret <4 x float> %A\n"
403       "}\n");
404   // The lane that contains a NaN (0x7ff80...) behaves like a
405   // non-NaN-propagating min and the other lines behave like a NaN-propagating
406   // min, so check that neither is returned.
407   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
408 }
409 
410 TEST_F(MatchSelectPatternTest, VectorNotFMinZero) {
411   parseAssembly(
412       "define <4 x float> @test(<4 x float> %a) {\n"
413       "  %1 = fcmp ule <4 x float> %a, \n"
414       "    <float 5.0, float -0.0, float 5.0, float 5.0>\n"
415       "  %A = select <4 x i1> %1, <4 x float> %a,\n"
416       "     <4 x float> <float 5.0, float 0.0, float 5.0, float 5.0>\n"
417       "  ret <4 x float> %A\n"
418       "}\n");
419   // Always selects the second lane of %a if it is positive or negative zero, so
420   // this is stricter than a min.
421   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
422 }
423 
424 TEST_F(MatchSelectPatternTest, DoubleCastU) {
425   parseAssembly(
426       "define i32 @test(i8 %a, i8 %b) {\n"
427       "  %1 = icmp ult i8 %a, %b\n"
428       "  %2 = zext i8 %a to i32\n"
429       "  %3 = zext i8 %b to i32\n"
430       "  %A = select i1 %1, i32 %2, i32 %3\n"
431       "  ret i32 %A\n"
432       "}\n");
433   // We should be able to look through the situation where we cast both operands
434   // to the select.
435   expectPattern({SPF_UMIN, SPNB_NA, false});
436 }
437 
438 TEST_F(MatchSelectPatternTest, DoubleCastS) {
439   parseAssembly(
440       "define i32 @test(i8 %a, i8 %b) {\n"
441       "  %1 = icmp slt i8 %a, %b\n"
442       "  %2 = sext i8 %a to i32\n"
443       "  %3 = sext i8 %b to i32\n"
444       "  %A = select i1 %1, i32 %2, i32 %3\n"
445       "  ret i32 %A\n"
446       "}\n");
447   // We should be able to look through the situation where we cast both operands
448   // to the select.
449   expectPattern({SPF_SMIN, SPNB_NA, false});
450 }
451 
452 TEST_F(MatchSelectPatternTest, DoubleCastBad) {
453   parseAssembly(
454       "define i32 @test(i8 %a, i8 %b) {\n"
455       "  %1 = icmp ult i8 %a, %b\n"
456       "  %2 = zext i8 %a to i32\n"
457       "  %3 = sext i8 %b to i32\n"
458       "  %A = select i1 %1, i32 %2, i32 %3\n"
459       "  ret i32 %A\n"
460       "}\n");
461   // The cast types here aren't the same, so we cannot match an UMIN.
462   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
463 }
464 
465 TEST_F(MatchSelectPatternTest, NotNotSMin) {
466   parseAssembly(
467       "define i8 @test(i8 %a, i8 %b) {\n"
468       "  %cmp = icmp sgt i8 %a, %b\n"
469       "  %an = xor i8 %a, -1\n"
470       "  %bn = xor i8 %b, -1\n"
471       "  %A = select i1 %cmp, i8 %an, i8 %bn\n"
472       "  ret i8 %A\n"
473       "}\n");
474   expectPattern({SPF_SMIN, SPNB_NA, false});
475 }
476 
477 TEST_F(MatchSelectPatternTest, NotNotSMinSwap) {
478   parseAssembly(
479       "define i8 @test(i8 %a, i8 %b) {\n"
480       "  %cmp = icmp slt i8 %a, %b\n"
481       "  %an = xor i8 %a, -1\n"
482       "  %bn = xor i8 %b, -1\n"
483       "  %A = select i1 %cmp, i8 %bn, i8 %an\n"
484       "  ret i8 %A\n"
485       "}\n");
486   expectPattern({SPF_SMIN, SPNB_NA, false});
487 }
488 
489 TEST_F(MatchSelectPatternTest, NotNotSMax) {
490   parseAssembly(
491       "define i8 @test(i8 %a, i8 %b) {\n"
492       "  %cmp = icmp slt i8 %a, %b\n"
493       "  %an = xor i8 %a, -1\n"
494       "  %bn = xor i8 %b, -1\n"
495       "  %A = select i1 %cmp, i8 %an, i8 %bn\n"
496       "  ret i8 %A\n"
497       "}\n");
498   expectPattern({SPF_SMAX, SPNB_NA, false});
499 }
500 
501 TEST_F(MatchSelectPatternTest, NotNotSMaxSwap) {
502   parseAssembly(
503       "define i8 @test(i8 %a, i8 %b) {\n"
504       "  %cmp = icmp sgt i8 %a, %b\n"
505       "  %an = xor i8 %a, -1\n"
506       "  %bn = xor i8 %b, -1\n"
507       "  %A = select i1 %cmp, i8 %bn, i8 %an\n"
508       "  ret i8 %A\n"
509       "}\n");
510   expectPattern({SPF_SMAX, SPNB_NA, false});
511 }
512 
513 TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) {
514   StringRef Assembly =
515       "declare void @nounwind_readonly(i32*) nounwind readonly "
516       "declare void @nounwind_argmemonly(i32*) nounwind argmemonly "
517       "declare void @throws_but_readonly(i32*) readonly "
518       "declare void @throws_but_argmemonly(i32*) argmemonly "
519       "declare void @nounwind_willreturn(i32*) nounwind willreturn"
520       " "
521       "declare void @unknown(i32*) "
522       " "
523       "define void @f(i32* %p) { "
524       "  call void @nounwind_readonly(i32* %p) "
525       "  call void @nounwind_argmemonly(i32* %p) "
526       "  call void @throws_but_readonly(i32* %p) "
527       "  call void @throws_but_argmemonly(i32* %p) "
528       "  call void @unknown(i32* %p) nounwind readonly "
529       "  call void @unknown(i32* %p) nounwind argmemonly "
530       "  call void @unknown(i32* %p) readonly "
531       "  call void @unknown(i32* %p) argmemonly "
532       "  call void @nounwind_willreturn(i32* %p)"
533       "  ret void "
534       "} ";
535 
536   LLVMContext Context;
537   SMDiagnostic Error;
538   auto M = parseAssemblyString(Assembly, Error, Context);
539   assert(M && "Bad assembly?");
540 
541   auto *F = M->getFunction("f");
542   assert(F && "Bad assembly?");
543 
544   auto &BB = F->getEntryBlock();
545   bool ExpectedAnswers[] = {
546       true,  // call void @nounwind_readonly(i32* %p)
547       true,  // call void @nounwind_argmemonly(i32* %p)
548       false, // call void @throws_but_readonly(i32* %p)
549       false, // call void @throws_but_argmemonly(i32* %p)
550       true,  // call void @unknown(i32* %p) nounwind readonly
551       true,  // call void @unknown(i32* %p) nounwind argmemonly
552       false, // call void @unknown(i32* %p) readonly
553       false, // call void @unknown(i32* %p) argmemonly
554       true,  // call void @nounwind_willreturn(i32* %p)
555       false, // ret void
556   };
557 
558   int Index = 0;
559   for (auto &I : BB) {
560     EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I),
561               ExpectedAnswers[Index])
562         << "Incorrect answer at instruction " << Index << " = " << I;
563     Index++;
564   }
565 }
566 
567 TEST_F(ValueTrackingTest, ComputeNumSignBits_PR32045) {
568   parseAssembly(
569       "define i32 @test(i32 %a) {\n"
570       "  %A = ashr i32 %a, -1\n"
571       "  ret i32 %A\n"
572       "}\n");
573   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
574 }
575 
576 // No guarantees for canonical IR in this analysis, so this just bails out.
577 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle) {
578   parseAssembly(
579       "define <2 x i32> @test() {\n"
580       "  %A = shufflevector <2 x i32> undef, <2 x i32> undef, <2 x i32> <i32 0, i32 0>\n"
581       "  ret <2 x i32> %A\n"
582       "}\n");
583   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
584 }
585 
586 // No guarantees for canonical IR in this analysis, so a shuffle element that
587 // references an undef value means this can't return any extra information.
588 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) {
589   parseAssembly(
590       "define <2 x i32> @test(<2 x i1> %x) {\n"
591       "  %sext = sext <2 x i1> %x to <2 x i32>\n"
592       "  %A = shufflevector <2 x i32> %sext, <2 x i32> undef, <2 x i32> <i32 0, i32 2>\n"
593       "  ret <2 x i32> %A\n"
594       "}\n");
595   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
596 }
597 
598 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
599   parseAssembly(
600       "define i32 @test(i32 %a, i32 %b) {\n"
601       "  %ash = mul i32 %a, 8\n"
602       "  %aad = add i32 %ash, 7\n"
603       "  %aan = and i32 %aad, 4095\n"
604       "  %bsh = shl i32 %b, 4\n"
605       "  %bad = or i32 %bsh, 6\n"
606       "  %ban = and i32 %bad, 4095\n"
607       "  %A = mul i32 %aan, %ban\n"
608       "  ret i32 %A\n"
609       "}\n");
610   expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u);
611 }
612 
613 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) {
614   parseAssembly(
615       "define i32 @test(i32 %a, i32 %b) {\n"
616       "  %aa = shl i32 %a, 5\n"
617       "  %bb = shl i32 %b, 5\n"
618       "  %aaa = or i32 %aa, 24\n"
619       "  %bbb = or i32 %bb, 28\n"
620       "  %A = mul i32 %aaa, %bbb\n"
621       "  ret i32 %A\n"
622       "}\n");
623   expectKnownBits(/*zero*/ 95u, /*one*/ 32u);
624 }
625 
626 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) {
627   // fshl(....1111....0000, 00..1111........, 6)
628   // = 11....000000..11
629   parseAssembly(
630       "define i16 @test(i16 %a, i16 %b) {\n"
631       "  %aa = shl i16 %a, 4\n"
632       "  %bb = lshr i16 %b, 2\n"
633       "  %aaa = or i16 %aa, 3840\n"
634       "  %bbb = or i16 %bb, 3840\n"
635       "  %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n"
636       "  ret i16 %A\n"
637       "}\n"
638       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
639   expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
640 }
641 
642 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) {
643   // fshr(....1111....0000, 00..1111........, 26)
644   // = 11....000000..11
645   parseAssembly(
646       "define i16 @test(i16 %a, i16 %b) {\n"
647       "  %aa = shl i16 %a, 4\n"
648       "  %bb = lshr i16 %b, 2\n"
649       "  %aaa = or i16 %aa, 3840\n"
650       "  %bbb = or i16 %bb, 3840\n"
651       "  %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n"
652       "  ret i16 %A\n"
653       "}\n"
654       "declare i16 @llvm.fshr.i16(i16, i16, i16)\n");
655   expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
656 }
657 
658 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) {
659   // fshl(....1111....0000, 00..1111........, 0)
660   // = ....1111....0000
661   parseAssembly(
662       "define i16 @test(i16 %a, i16 %b) {\n"
663       "  %aa = shl i16 %a, 4\n"
664       "  %bb = lshr i16 %b, 2\n"
665       "  %aaa = or i16 %aa, 3840\n"
666       "  %bbb = or i16 %bb, 3840\n"
667       "  %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n"
668       "  ret i16 %A\n"
669       "}\n"
670       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
671   expectKnownBits(/*zero*/ 15u, /*one*/ 3840u);
672 }
673 
674 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) {
675   // uadd.sat(1111...1, ........)
676   // = 1111....
677   parseAssembly(
678       "define i8 @test(i8 %a, i8 %b) {\n"
679       "  %aa = or i8 %a, 241\n"
680       "  %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n"
681       "  ret i8 %A\n"
682       "}\n"
683       "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
684   expectKnownBits(/*zero*/ 0u, /*one*/ 240u);
685 }
686 
687 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) {
688   // uadd.sat(00...011, .1...110)
689   // = .......1
690   parseAssembly(
691       "define i8 @test(i8 %a, i8 %b) {\n"
692       "  %aa = or i8 %a, 3\n"
693       "  %aaa = and i8 %aa, 59\n"
694       "  %bb = or i8 %b, 70\n"
695       "  %bbb = and i8 %bb, 254\n"
696       "  %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n"
697       "  ret i8 %A\n"
698       "}\n"
699       "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
700   expectKnownBits(/*zero*/ 0u, /*one*/ 1u);
701 }
702 
703 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) {
704   // usub.sat(0000...0, ........)
705   // = 0000....
706   parseAssembly(
707       "define i8 @test(i8 %a, i8 %b) {\n"
708       "  %aa = and i8 %a, 14\n"
709       "  %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n"
710       "  ret i8 %A\n"
711       "}\n"
712       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
713   expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
714 }
715 
716 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) {
717   // usub.sat(........, 1111...1)
718   // = 0000....
719   parseAssembly(
720       "define i8 @test(i8 %a, i8 %b) {\n"
721       "  %bb = or i8 %a, 241\n"
722       "  %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n"
723       "  ret i8 %A\n"
724       "}\n"
725       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
726   expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
727 }
728 
729 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) {
730   // usub.sat(11...011, .1...110)
731   // = ......0.
732   parseAssembly(
733       "define i8 @test(i8 %a, i8 %b) {\n"
734       "  %aa = or i8 %a, 195\n"
735       "  %aaa = and i8 %aa, 251\n"
736       "  %bb = or i8 %b, 70\n"
737       "  %bbb = and i8 %bb, 254\n"
738       "  %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
739       "  ret i8 %A\n"
740       "}\n"
741       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
742   expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
743 }
744 
745 class IsBytewiseValueTest : public ValueTrackingTest,
746                             public ::testing::WithParamInterface<
747                                 std::pair<const char *, const char *>> {
748 protected:
749 };
750 
751 const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
752     {
753         "i8 0",
754         "i48* null",
755     },
756     {
757         "i8 undef",
758         "i48* undef",
759     },
760     {
761         "i8 0",
762         "i8 zeroinitializer",
763     },
764     {
765         "i8 0",
766         "i8 0",
767     },
768     {
769         "i8 -86",
770         "i8 -86",
771     },
772     {
773         "i8 -1",
774         "i8 -1",
775     },
776     {
777         "i8 undef",
778         "i16 undef",
779     },
780     {
781         "i8 0",
782         "i16 0",
783     },
784     {
785         "",
786         "i16 7",
787     },
788     {
789         "i8 -86",
790         "i16 -21846",
791     },
792     {
793         "i8 -1",
794         "i16 -1",
795     },
796     {
797         "i8 0",
798         "i48 0",
799     },
800     {
801         "i8 -1",
802         "i48 -1",
803     },
804     {
805         "i8 0",
806         "i49 0",
807     },
808     {
809         "",
810         "i49 -1",
811     },
812     {
813         "i8 0",
814         "half 0xH0000",
815     },
816     {
817         "i8 -85",
818         "half 0xHABAB",
819     },
820     {
821         "i8 0",
822         "float 0.0",
823     },
824     {
825         "i8 -1",
826         "float 0xFFFFFFFFE0000000",
827     },
828     {
829         "i8 0",
830         "double 0.0",
831     },
832     {
833         "i8 -15",
834         "double 0xF1F1F1F1F1F1F1F1",
835     },
836     {
837         "i8 undef",
838         "i16* undef",
839     },
840     {
841         "i8 0",
842         "i16* inttoptr (i64 0 to i16*)",
843     },
844     {
845         "i8 -1",
846         "i16* inttoptr (i64 -1 to i16*)",
847     },
848     {
849         "i8 -86",
850         "i16* inttoptr (i64 -6148914691236517206 to i16*)",
851     },
852     {
853         "",
854         "i16* inttoptr (i48 -1 to i16*)",
855     },
856     {
857         "i8 -1",
858         "i16* inttoptr (i96 -1 to i16*)",
859     },
860     {
861         "i8 undef",
862         "[0 x i8] zeroinitializer",
863     },
864     {
865         "i8 undef",
866         "[0 x i8] undef",
867     },
868     {
869         "i8 undef",
870         "[5 x [0 x i8]] zeroinitializer",
871     },
872     {
873         "i8 undef",
874         "[5 x [0 x i8]] undef",
875     },
876     {
877         "i8 0",
878         "[6 x i8] zeroinitializer",
879     },
880     {
881         "i8 undef",
882         "[6 x i8] undef",
883     },
884     {
885         "i8 1",
886         "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]",
887     },
888     {
889         "",
890         "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]",
891     },
892     {
893         "i8 -1",
894         "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]",
895     },
896     {
897         "",
898         "[4 x i8] [i8 1, i8 2, i8 1, i8 1]",
899     },
900     {
901         "i8 1",
902         "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]",
903     },
904     {
905         "i8 0",
906         "<6 x i8> zeroinitializer",
907     },
908     {
909         "i8 undef",
910         "<6 x i8> undef",
911     },
912     {
913         "i8 1",
914         "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>",
915     },
916     {
917         "",
918         "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>",
919     },
920     {
921         "i8 -1",
922         "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>",
923     },
924     {
925         "",
926         "<4 x i8> <i8 1, i8 1, i8 2, i8 1>",
927     },
928     {
929         "i8 5",
930         "<2 x i8> < i8 5, i8 undef >",
931     },
932     {
933         "i8 0",
934         "[2 x [2 x i16]] zeroinitializer",
935     },
936     {
937         "i8 undef",
938         "[2 x [2 x i16]] undef",
939     },
940     {
941         "i8 -86",
942         "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
943         "[2 x i16] [i16 -21846, i16 -21846]]",
944     },
945     {
946         "",
947         "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
948         "[2 x i16] [i16 -21836, i16 -21846]]",
949     },
950     {
951         "i8 undef",
952         "{ } zeroinitializer",
953     },
954     {
955         "i8 undef",
956         "{ } undef",
957     },
958     {
959         "i8 undef",
960         "{ {}, {} } zeroinitializer",
961     },
962     {
963         "i8 undef",
964         "{ {}, {} } undef",
965     },
966     {
967         "i8 0",
968         "{i8, i64, i16*} zeroinitializer",
969     },
970     {
971         "i8 undef",
972         "{i8, i64, i16*} undef",
973     },
974     {
975         "i8 -86",
976         "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}",
977     },
978     {
979         "",
980         "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}",
981     },
982 };
983 
984 INSTANTIATE_TEST_CASE_P(IsBytewiseValueParamTests, IsBytewiseValueTest,
985                         ::testing::ValuesIn(IsBytewiseValueTests),);
986 
987 TEST_P(IsBytewiseValueTest, IsBytewiseValue) {
988   auto M = parseModule(std::string("@test = global ") + GetParam().second);
989   GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
990   Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout());
991   std::string Buff;
992   raw_string_ostream S(Buff);
993   if (Actual)
994     S << *Actual;
995   EXPECT_EQ(GetParam().first, S.str());
996 }
997