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(ValueTracking, GuaranteedToTransferExecutionToSuccessor) {
466   StringRef Assembly =
467       "declare void @nounwind_readonly(i32*) nounwind readonly "
468       "declare void @nounwind_argmemonly(i32*) nounwind argmemonly "
469       "declare void @throws_but_readonly(i32*) readonly "
470       "declare void @throws_but_argmemonly(i32*) argmemonly "
471       "declare void @nounwind_willreturn(i32*) nounwind willreturn"
472       " "
473       "declare void @unknown(i32*) "
474       " "
475       "define void @f(i32* %p) { "
476       "  call void @nounwind_readonly(i32* %p) "
477       "  call void @nounwind_argmemonly(i32* %p) "
478       "  call void @throws_but_readonly(i32* %p) "
479       "  call void @throws_but_argmemonly(i32* %p) "
480       "  call void @unknown(i32* %p) nounwind readonly "
481       "  call void @unknown(i32* %p) nounwind argmemonly "
482       "  call void @unknown(i32* %p) readonly "
483       "  call void @unknown(i32* %p) argmemonly "
484       "  call void @nounwind_willreturn(i32* %p)"
485       "  ret void "
486       "} ";
487 
488   LLVMContext Context;
489   SMDiagnostic Error;
490   auto M = parseAssemblyString(Assembly, Error, Context);
491   assert(M && "Bad assembly?");
492 
493   auto *F = M->getFunction("f");
494   assert(F && "Bad assembly?");
495 
496   auto &BB = F->getEntryBlock();
497   bool ExpectedAnswers[] = {
498       true,  // call void @nounwind_readonly(i32* %p)
499       true,  // call void @nounwind_argmemonly(i32* %p)
500       false, // call void @throws_but_readonly(i32* %p)
501       false, // call void @throws_but_argmemonly(i32* %p)
502       true,  // call void @unknown(i32* %p) nounwind readonly
503       true,  // call void @unknown(i32* %p) nounwind argmemonly
504       false, // call void @unknown(i32* %p) readonly
505       false, // call void @unknown(i32* %p) argmemonly
506       true,  // call void @nounwind_willreturn(i32* %p)
507       false, // ret void
508   };
509 
510   int Index = 0;
511   for (auto &I : BB) {
512     EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I),
513               ExpectedAnswers[Index])
514         << "Incorrect answer at instruction " << Index << " = " << I;
515     Index++;
516   }
517 }
518 
519 TEST_F(ValueTrackingTest, ComputeNumSignBits_PR32045) {
520   parseAssembly(
521       "define i32 @test(i32 %a) {\n"
522       "  %A = ashr i32 %a, -1\n"
523       "  ret i32 %A\n"
524       "}\n");
525   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
526 }
527 
528 // No guarantees for canonical IR in this analysis, so this just bails out.
529 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle) {
530   parseAssembly(
531       "define <2 x i32> @test() {\n"
532       "  %A = shufflevector <2 x i32> undef, <2 x i32> undef, <2 x i32> <i32 0, i32 0>\n"
533       "  ret <2 x i32> %A\n"
534       "}\n");
535   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
536 }
537 
538 // No guarantees for canonical IR in this analysis, so a shuffle element that
539 // references an undef value means this can't return any extra information.
540 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) {
541   parseAssembly(
542       "define <2 x i32> @test(<2 x i1> %x) {\n"
543       "  %sext = sext <2 x i1> %x to <2 x i32>\n"
544       "  %A = shufflevector <2 x i32> %sext, <2 x i32> undef, <2 x i32> <i32 0, i32 2>\n"
545       "  ret <2 x i32> %A\n"
546       "}\n");
547   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
548 }
549 
550 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
551   parseAssembly(
552       "define i32 @test(i32 %a, i32 %b) {\n"
553       "  %ash = mul i32 %a, 8\n"
554       "  %aad = add i32 %ash, 7\n"
555       "  %aan = and i32 %aad, 4095\n"
556       "  %bsh = shl i32 %b, 4\n"
557       "  %bad = or i32 %bsh, 6\n"
558       "  %ban = and i32 %bad, 4095\n"
559       "  %A = mul i32 %aan, %ban\n"
560       "  ret i32 %A\n"
561       "}\n");
562   expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u);
563 }
564 
565 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) {
566   parseAssembly(
567       "define i32 @test(i32 %a, i32 %b) {\n"
568       "  %aa = shl i32 %a, 5\n"
569       "  %bb = shl i32 %b, 5\n"
570       "  %aaa = or i32 %aa, 24\n"
571       "  %bbb = or i32 %bb, 28\n"
572       "  %A = mul i32 %aaa, %bbb\n"
573       "  ret i32 %A\n"
574       "}\n");
575   expectKnownBits(/*zero*/ 95u, /*one*/ 32u);
576 }
577 
578 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) {
579   // fshl(....1111....0000, 00..1111........, 6)
580   // = 11....000000..11
581   parseAssembly(
582       "define i16 @test(i16 %a, i16 %b) {\n"
583       "  %aa = shl i16 %a, 4\n"
584       "  %bb = lshr i16 %b, 2\n"
585       "  %aaa = or i16 %aa, 3840\n"
586       "  %bbb = or i16 %bb, 3840\n"
587       "  %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n"
588       "  ret i16 %A\n"
589       "}\n"
590       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
591   expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
592 }
593 
594 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) {
595   // fshr(....1111....0000, 00..1111........, 26)
596   // = 11....000000..11
597   parseAssembly(
598       "define i16 @test(i16 %a, i16 %b) {\n"
599       "  %aa = shl i16 %a, 4\n"
600       "  %bb = lshr i16 %b, 2\n"
601       "  %aaa = or i16 %aa, 3840\n"
602       "  %bbb = or i16 %bb, 3840\n"
603       "  %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n"
604       "  ret i16 %A\n"
605       "}\n"
606       "declare i16 @llvm.fshr.i16(i16, i16, i16)\n");
607   expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
608 }
609 
610 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) {
611   // fshl(....1111....0000, 00..1111........, 0)
612   // = ....1111....0000
613   parseAssembly(
614       "define i16 @test(i16 %a, i16 %b) {\n"
615       "  %aa = shl i16 %a, 4\n"
616       "  %bb = lshr i16 %b, 2\n"
617       "  %aaa = or i16 %aa, 3840\n"
618       "  %bbb = or i16 %bb, 3840\n"
619       "  %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n"
620       "  ret i16 %A\n"
621       "}\n"
622       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
623   expectKnownBits(/*zero*/ 15u, /*one*/ 3840u);
624 }
625 
626 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) {
627   // uadd.sat(1111...1, ........)
628   // = 1111....
629   parseAssembly(
630       "define i8 @test(i8 %a, i8 %b) {\n"
631       "  %aa = or i8 %a, 241\n"
632       "  %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n"
633       "  ret i8 %A\n"
634       "}\n"
635       "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
636   expectKnownBits(/*zero*/ 0u, /*one*/ 240u);
637 }
638 
639 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) {
640   // uadd.sat(00...011, .1...110)
641   // = .......1
642   parseAssembly(
643       "define i8 @test(i8 %a, i8 %b) {\n"
644       "  %aa = or i8 %a, 3\n"
645       "  %aaa = and i8 %aa, 59\n"
646       "  %bb = or i8 %b, 70\n"
647       "  %bbb = and i8 %bb, 254\n"
648       "  %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n"
649       "  ret i8 %A\n"
650       "}\n"
651       "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
652   expectKnownBits(/*zero*/ 0u, /*one*/ 1u);
653 }
654 
655 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) {
656   // usub.sat(0000...0, ........)
657   // = 0000....
658   parseAssembly(
659       "define i8 @test(i8 %a, i8 %b) {\n"
660       "  %aa = and i8 %a, 14\n"
661       "  %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n"
662       "  ret i8 %A\n"
663       "}\n"
664       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
665   expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
666 }
667 
668 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) {
669   // usub.sat(........, 1111...1)
670   // = 0000....
671   parseAssembly(
672       "define i8 @test(i8 %a, i8 %b) {\n"
673       "  %bb = or i8 %a, 241\n"
674       "  %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n"
675       "  ret i8 %A\n"
676       "}\n"
677       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
678   expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
679 }
680 
681 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) {
682   // usub.sat(11...011, .1...110)
683   // = ......0.
684   parseAssembly(
685       "define i8 @test(i8 %a, i8 %b) {\n"
686       "  %aa = or i8 %a, 195\n"
687       "  %aaa = and i8 %aa, 251\n"
688       "  %bb = or i8 %b, 70\n"
689       "  %bbb = and i8 %bb, 254\n"
690       "  %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
691       "  ret i8 %A\n"
692       "}\n"
693       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
694   expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
695 }
696 
697 class IsBytewiseValueTest : public ValueTrackingTest,
698                             public ::testing::WithParamInterface<
699                                 std::pair<const char *, const char *>> {
700 protected:
701 };
702 
703 const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
704     {
705         "i8 0",
706         "i48* null",
707     },
708     {
709         "i8 undef",
710         "i48* undef",
711     },
712     {
713         "i8 0",
714         "i8 zeroinitializer",
715     },
716     {
717         "i8 0",
718         "i8 0",
719     },
720     {
721         "i8 -86",
722         "i8 -86",
723     },
724     {
725         "i8 -1",
726         "i8 -1",
727     },
728     {
729         "i8 undef",
730         "i16 undef",
731     },
732     {
733         "i8 0",
734         "i16 0",
735     },
736     {
737         "",
738         "i16 7",
739     },
740     {
741         "i8 -86",
742         "i16 -21846",
743     },
744     {
745         "i8 -1",
746         "i16 -1",
747     },
748     {
749         "i8 0",
750         "i48 0",
751     },
752     {
753         "i8 -1",
754         "i48 -1",
755     },
756     {
757         "i8 0",
758         "i49 0",
759     },
760     {
761         "",
762         "i49 -1",
763     },
764     {
765         "i8 0",
766         "half 0xH0000",
767     },
768     {
769         "i8 -85",
770         "half 0xHABAB",
771     },
772     {
773         "i8 0",
774         "float 0.0",
775     },
776     {
777         "i8 -1",
778         "float 0xFFFFFFFFE0000000",
779     },
780     {
781         "i8 0",
782         "double 0.0",
783     },
784     {
785         "i8 -15",
786         "double 0xF1F1F1F1F1F1F1F1",
787     },
788     {
789         "i8 undef",
790         "i16* undef",
791     },
792     {
793         "i8 0",
794         "i16* inttoptr (i64 0 to i16*)",
795     },
796     {
797         "i8 -1",
798         "i16* inttoptr (i64 -1 to i16*)",
799     },
800     {
801         "i8 -86",
802         "i16* inttoptr (i64 -6148914691236517206 to i16*)",
803     },
804     {
805         "",
806         "i16* inttoptr (i48 -1 to i16*)",
807     },
808     {
809         "i8 -1",
810         "i16* inttoptr (i96 -1 to i16*)",
811     },
812     {
813         "i8 undef",
814         "[0 x i8] zeroinitializer",
815     },
816     {
817         "i8 undef",
818         "[0 x i8] undef",
819     },
820     {
821         "i8 undef",
822         "[5 x [0 x i8]] zeroinitializer",
823     },
824     {
825         "i8 undef",
826         "[5 x [0 x i8]] undef",
827     },
828     {
829         "i8 0",
830         "[6 x i8] zeroinitializer",
831     },
832     {
833         "i8 undef",
834         "[6 x i8] undef",
835     },
836     {
837         "i8 1",
838         "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]",
839     },
840     {
841         "",
842         "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]",
843     },
844     {
845         "i8 -1",
846         "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]",
847     },
848     {
849         "",
850         "[4 x i8] [i8 1, i8 2, i8 1, i8 1]",
851     },
852     {
853         "i8 1",
854         "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]",
855     },
856     {
857         "i8 0",
858         "<6 x i8> zeroinitializer",
859     },
860     {
861         "i8 undef",
862         "<6 x i8> undef",
863     },
864     {
865         "i8 1",
866         "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>",
867     },
868     {
869         "",
870         "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>",
871     },
872     {
873         "i8 -1",
874         "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>",
875     },
876     {
877         "",
878         "<4 x i8> <i8 1, i8 1, i8 2, i8 1>",
879     },
880     {
881         "i8 5",
882         "<2 x i8> < i8 5, i8 undef >",
883     },
884     {
885         "i8 0",
886         "[2 x [2 x i16]] zeroinitializer",
887     },
888     {
889         "i8 undef",
890         "[2 x [2 x i16]] undef",
891     },
892     {
893         "i8 -86",
894         "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
895         "[2 x i16] [i16 -21846, i16 -21846]]",
896     },
897     {
898         "",
899         "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
900         "[2 x i16] [i16 -21836, i16 -21846]]",
901     },
902     {
903         "i8 undef",
904         "{ } zeroinitializer",
905     },
906     {
907         "i8 undef",
908         "{ } undef",
909     },
910     {
911         "i8 undef",
912         "{ {}, {} } zeroinitializer",
913     },
914     {
915         "i8 undef",
916         "{ {}, {} } undef",
917     },
918     {
919         "i8 0",
920         "{i8, i64, i16*} zeroinitializer",
921     },
922     {
923         "i8 undef",
924         "{i8, i64, i16*} undef",
925     },
926     {
927         "i8 -86",
928         "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}",
929     },
930     {
931         "",
932         "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}",
933     },
934 };
935 
936 INSTANTIATE_TEST_CASE_P(IsBytewiseValueParamTests, IsBytewiseValueTest,
937                         ::testing::ValuesIn(IsBytewiseValueTests),);
938 
939 TEST_P(IsBytewiseValueTest, IsBytewiseValue) {
940   auto M = parseModule(std::string("@test = global ") + GetParam().second);
941   GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
942   Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout());
943   std::string Buff;
944   raw_string_ostream S(Buff);
945   if (Actual)
946     S << *Actual;
947   EXPECT_EQ(GetParam().first, S.str());
948 }
949