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/SourceMgr.h"
17 #include "llvm/Support/KnownBits.h"
18 #include "gtest/gtest.h"
19 
20 using namespace llvm;
21 
22 namespace {
23 
24 class ValueTrackingTest : public testing::Test {
25 protected:
26   void parseAssembly(const char *Assembly) {
27     SMDiagnostic Error;
28     M = parseAssemblyString(Assembly, Error, Context);
29 
30     std::string errMsg;
31     raw_string_ostream os(errMsg);
32     Error.print("", os);
33 
34     // A failure here means that the test itself is buggy.
35     if (!M)
36       report_fatal_error(os.str());
37 
38     Function *F = M->getFunction("test");
39     if (F == nullptr)
40       report_fatal_error("Test must have a function named @test");
41 
42     A = nullptr;
43     for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
44       if (I->hasName()) {
45         if (I->getName() == "A")
46           A = &*I;
47       }
48     }
49     if (A == nullptr)
50       report_fatal_error("@test must have an instruction %A");
51   }
52 
53   LLVMContext Context;
54   std::unique_ptr<Module> M;
55   Instruction *A;
56 };
57 
58 class MatchSelectPatternTest : public ValueTrackingTest {
59 protected:
60   void expectPattern(const SelectPatternResult &P) {
61     Value *LHS, *RHS;
62     Instruction::CastOps CastOp;
63     SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp);
64     EXPECT_EQ(P.Flavor, R.Flavor);
65     EXPECT_EQ(P.NaNBehavior, R.NaNBehavior);
66     EXPECT_EQ(P.Ordered, R.Ordered);
67   }
68 };
69 
70 class ComputeKnownBitsTest : public ValueTrackingTest {
71 protected:
72   void expectKnownBits(uint64_t Zero, uint64_t One) {
73     auto Known = computeKnownBits(A, M->getDataLayout());
74     ASSERT_FALSE(Known.hasConflict());
75     EXPECT_EQ(Known.One.getZExtValue(), One);
76     EXPECT_EQ(Known.Zero.getZExtValue(), Zero);
77   }
78 };
79 
80 }
81 
82 TEST_F(MatchSelectPatternTest, SimpleFMin) {
83   parseAssembly(
84       "define float @test(float %a) {\n"
85       "  %1 = fcmp ult float %a, 5.0\n"
86       "  %A = select i1 %1, float %a, float 5.0\n"
87       "  ret float %A\n"
88       "}\n");
89   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
90 }
91 
92 TEST_F(MatchSelectPatternTest, SimpleFMax) {
93   parseAssembly(
94       "define float @test(float %a) {\n"
95       "  %1 = fcmp ogt 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_FMAXNUM, SPNB_RETURNS_OTHER, true});
100 }
101 
102 TEST_F(MatchSelectPatternTest, SwappedFMax) {
103   parseAssembly(
104       "define float @test(float %a) {\n"
105       "  %1 = fcmp olt float 5.0, %a\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, false});
110 }
111 
112 TEST_F(MatchSelectPatternTest, SwappedFMax2) {
113   parseAssembly(
114       "define float @test(float %a) {\n"
115       "  %1 = fcmp olt float %a, 5.0\n"
116       "  %A = select i1 %1, float 5.0, float %a\n"
117       "  ret float %A\n"
118       "}\n");
119   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
120 }
121 
122 TEST_F(MatchSelectPatternTest, SwappedFMax3) {
123   parseAssembly(
124       "define float @test(float %a) {\n"
125       "  %1 = fcmp ult 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_OTHER, true});
130 }
131 
132 TEST_F(MatchSelectPatternTest, FastFMin) {
133   parseAssembly(
134       "define float @test(float %a) {\n"
135       "  %1 = fcmp nnan olt float %a, 5.0\n"
136       "  %A = select i1 %1, float %a, float 5.0\n"
137       "  ret float %A\n"
138       "}\n");
139   expectPattern({SPF_FMINNUM, SPNB_RETURNS_ANY, false});
140 }
141 
142 TEST_F(MatchSelectPatternTest, FMinConstantZero) {
143   parseAssembly(
144       "define float @test(float %a) {\n"
145       "  %1 = fcmp ole float %a, 0.0\n"
146       "  %A = select i1 %1, float %a, float 0.0\n"
147       "  ret float %A\n"
148       "}\n");
149   // This shouldn't be matched, as %a could be -0.0.
150   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
151 }
152 
153 TEST_F(MatchSelectPatternTest, FMinConstantZeroNsz) {
154   parseAssembly(
155       "define float @test(float %a) {\n"
156       "  %1 = fcmp nsz ole float %a, 0.0\n"
157       "  %A = select i1 %1, float %a, float 0.0\n"
158       "  ret float %A\n"
159       "}\n");
160   // But this should be, because we've ignored signed zeroes.
161   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
162 }
163 
164 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero1) {
165   parseAssembly(
166       "define float @test(float %a) {\n"
167       "  %1 = fcmp olt float -0.0, %a\n"
168       "  %A = select i1 %1, float 0.0, float %a\n"
169       "  ret float %A\n"
170       "}\n");
171   // The sign of zero doesn't matter in fcmp.
172   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, true});
173 }
174 
175 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero2) {
176   parseAssembly(
177       "define float @test(float %a) {\n"
178       "  %1 = fcmp ogt float %a, -0.0\n"
179       "  %A = select i1 %1, float 0.0, float %a\n"
180       "  ret float %A\n"
181       "}\n");
182   // The sign of zero doesn't matter in fcmp.
183   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
184 }
185 
186 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero3) {
187   parseAssembly(
188       "define float @test(float %a) {\n"
189       "  %1 = fcmp olt float 0.0, %a\n"
190       "  %A = select i1 %1, float -0.0, float %a\n"
191       "  ret float %A\n"
192       "}\n");
193   // The sign of zero doesn't matter in fcmp.
194   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, true});
195 }
196 
197 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero4) {
198   parseAssembly(
199       "define float @test(float %a) {\n"
200       "  %1 = fcmp ogt float %a, 0.0\n"
201       "  %A = select i1 %1, float -0.0, float %a\n"
202       "  ret float %A\n"
203       "}\n");
204   // The sign of zero doesn't matter in fcmp.
205   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
206 }
207 
208 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero5) {
209   parseAssembly(
210       "define float @test(float %a) {\n"
211       "  %1 = fcmp ogt float -0.0, %a\n"
212       "  %A = select i1 %1, float %a, float 0.0\n"
213       "  ret float %A\n"
214       "}\n");
215   // The sign of zero doesn't matter in fcmp.
216   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, false});
217 }
218 
219 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero6) {
220   parseAssembly(
221       "define float @test(float %a) {\n"
222       "  %1 = fcmp olt float %a, -0.0\n"
223       "  %A = select i1 %1, float %a, float 0.0\n"
224       "  ret float %A\n"
225       "}\n");
226   // The sign of zero doesn't matter in fcmp.
227   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
228 }
229 
230 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero7) {
231   parseAssembly(
232       "define float @test(float %a) {\n"
233       "  %1 = fcmp ogt float 0.0, %a\n"
234       "  %A = select i1 %1, float %a, float -0.0\n"
235       "  ret float %A\n"
236       "}\n");
237   // The sign of zero doesn't matter in fcmp.
238   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, false});
239 }
240 
241 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero8) {
242   parseAssembly(
243       "define float @test(float %a) {\n"
244       "  %1 = fcmp olt float %a, 0.0\n"
245       "  %A = select i1 %1, float %a, float -0.0\n"
246       "  ret float %A\n"
247       "}\n");
248   // The sign of zero doesn't matter in fcmp.
249   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
250 }
251 
252 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero1) {
253   parseAssembly(
254       "define float @test(float %a) {\n"
255       "  %1 = fcmp ogt float -0.0, %a\n"
256       "  %A = select i1 %1, float 0.0, float %a\n"
257       "  ret float %A\n"
258       "}\n");
259   // The sign of zero doesn't matter in fcmp.
260   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, true});
261 }
262 
263 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero2) {
264   parseAssembly(
265       "define float @test(float %a) {\n"
266       "  %1 = fcmp olt float %a, -0.0\n"
267       "  %A = select i1 %1, float 0.0, float %a\n"
268       "  ret float %A\n"
269       "}\n");
270   // The sign of zero doesn't matter in fcmp.
271   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
272 }
273 
274 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero3) {
275   parseAssembly(
276       "define float @test(float %a) {\n"
277       "  %1 = fcmp ogt float 0.0, %a\n"
278       "  %A = select i1 %1, float -0.0, float %a\n"
279       "  ret float %A\n"
280       "}\n");
281   // The sign of zero doesn't matter in fcmp.
282   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, true});
283 }
284 
285 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero4) {
286   parseAssembly(
287       "define float @test(float %a) {\n"
288       "  %1 = fcmp olt float %a, 0.0\n"
289       "  %A = select i1 %1, float -0.0, float %a\n"
290       "  ret float %A\n"
291       "}\n");
292   // The sign of zero doesn't matter in fcmp.
293   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
294 }
295 
296 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero5) {
297   parseAssembly(
298       "define float @test(float %a) {\n"
299       "  %1 = fcmp olt float -0.0, %a\n"
300       "  %A = select i1 %1, float %a, float 0.0\n"
301       "  ret float %A\n"
302       "}\n");
303   // The sign of zero doesn't matter in fcmp.
304   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
305 }
306 
307 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero6) {
308   parseAssembly(
309       "define float @test(float %a) {\n"
310       "  %1 = fcmp ogt float %a, -0.0\n"
311       "  %A = select i1 %1, float %a, float 0.0\n"
312       "  ret float %A\n"
313       "}\n");
314   // The sign of zero doesn't matter in fcmp.
315   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
316 }
317 
318 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero7) {
319   parseAssembly(
320       "define float @test(float %a) {\n"
321       "  %1 = fcmp olt float 0.0, %a\n"
322       "  %A = select i1 %1, float %a, float -0.0\n"
323       "  ret float %A\n"
324       "}\n");
325   // The sign of zero doesn't matter in fcmp.
326   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
327 }
328 
329 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero8) {
330   parseAssembly(
331       "define float @test(float %a) {\n"
332       "  %1 = fcmp ogt float %a, 0.0\n"
333       "  %A = select i1 %1, float %a, float -0.0\n"
334       "  ret float %A\n"
335       "}\n");
336   // The sign of zero doesn't matter in fcmp.
337   expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
338 }
339 
340 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZeroVecUndef) {
341   parseAssembly(
342       "define <2 x float> @test(<2 x float> %a) {\n"
343       "  %1 = fcmp ogt <2 x float> %a, <float -0.0, float -0.0>\n"
344       "  %A = select <2 x i1> %1, <2 x float> <float undef, float 0.0>, <2 x float> %a\n"
345       "  ret <2 x float> %A\n"
346       "}\n");
347   // An undef in a vector constant can not be back-propagated for this analysis.
348   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
349 }
350 
351 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZeroVecUndef) {
352   parseAssembly(
353       "define <2 x float> @test(<2 x float> %a) {\n"
354       "  %1 = fcmp ogt <2 x float> %a, zeroinitializer\n"
355       "  %A = select <2 x i1> %1, <2 x float> %a, <2 x float> <float -0.0, float undef>\n"
356       "  ret <2 x float> %A\n"
357       "}\n");
358   // An undef in a vector constant can not be back-propagated for this analysis.
359   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
360 }
361 
362 TEST_F(MatchSelectPatternTest, VectorFMinimum) {
363   parseAssembly(
364       "define <4 x float> @test(<4 x float> %a) {\n"
365       "  %1 = fcmp ule <4 x float> %a, \n"
366       "    <float 5.0, float 5.0, float 5.0, float 5.0>\n"
367       "  %A = select <4 x i1> %1, <4 x float> %a,\n"
368       "     <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n"
369       "  ret <4 x float> %A\n"
370       "}\n");
371   // Check that pattern matching works on vectors where each lane has the same
372   // unordered pattern.
373   expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
374 }
375 
376 TEST_F(MatchSelectPatternTest, VectorFMinOtherOrdered) {
377   parseAssembly(
378       "define <4 x float> @test(<4 x float> %a) {\n"
379       "  %1 = fcmp ole <4 x float> %a, \n"
380       "    <float 5.0, float 5.0, float 5.0, float 5.0>\n"
381       "  %A = select <4 x i1> %1, <4 x float> %a,\n"
382       "     <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n"
383       "  ret <4 x float> %A\n"
384       "}\n");
385   // Check that pattern matching works on vectors where each lane has the same
386   // ordered pattern.
387   expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
388 }
389 
390 TEST_F(MatchSelectPatternTest, VectorNotFMinimum) {
391   parseAssembly(
392       "define <4 x float> @test(<4 x float> %a) {\n"
393       "  %1 = fcmp ule <4 x float> %a, \n"
394       "    <float 5.0, float 0x7ff8000000000000, float 5.0, float 5.0>\n"
395       "  %A = select <4 x i1> %1, <4 x float> %a,\n"
396       "     <4 x float> <float 5.0, float 0x7ff8000000000000, float 5.0, float "
397       "5.0>\n"
398       "  ret <4 x float> %A\n"
399       "}\n");
400   // The lane that contains a NaN (0x7ff80...) behaves like a
401   // non-NaN-propagating min and the other lines behave like a NaN-propagating
402   // min, so check that neither is returned.
403   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
404 }
405 
406 TEST_F(MatchSelectPatternTest, VectorNotFMinZero) {
407   parseAssembly(
408       "define <4 x float> @test(<4 x float> %a) {\n"
409       "  %1 = fcmp ule <4 x float> %a, \n"
410       "    <float 5.0, float -0.0, float 5.0, float 5.0>\n"
411       "  %A = select <4 x i1> %1, <4 x float> %a,\n"
412       "     <4 x float> <float 5.0, float 0.0, float 5.0, float 5.0>\n"
413       "  ret <4 x float> %A\n"
414       "}\n");
415   // Always selects the second lane of %a if it is positive or negative zero, so
416   // this is stricter than a min.
417   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
418 }
419 
420 TEST_F(MatchSelectPatternTest, DoubleCastU) {
421   parseAssembly(
422       "define i32 @test(i8 %a, i8 %b) {\n"
423       "  %1 = icmp ult i8 %a, %b\n"
424       "  %2 = zext i8 %a to i32\n"
425       "  %3 = zext i8 %b to i32\n"
426       "  %A = select i1 %1, i32 %2, i32 %3\n"
427       "  ret i32 %A\n"
428       "}\n");
429   // We should be able to look through the situation where we cast both operands
430   // to the select.
431   expectPattern({SPF_UMIN, SPNB_NA, false});
432 }
433 
434 TEST_F(MatchSelectPatternTest, DoubleCastS) {
435   parseAssembly(
436       "define i32 @test(i8 %a, i8 %b) {\n"
437       "  %1 = icmp slt i8 %a, %b\n"
438       "  %2 = sext i8 %a to i32\n"
439       "  %3 = sext i8 %b to i32\n"
440       "  %A = select i1 %1, i32 %2, i32 %3\n"
441       "  ret i32 %A\n"
442       "}\n");
443   // We should be able to look through the situation where we cast both operands
444   // to the select.
445   expectPattern({SPF_SMIN, SPNB_NA, false});
446 }
447 
448 TEST_F(MatchSelectPatternTest, DoubleCastBad) {
449   parseAssembly(
450       "define i32 @test(i8 %a, i8 %b) {\n"
451       "  %1 = icmp ult i8 %a, %b\n"
452       "  %2 = zext i8 %a to i32\n"
453       "  %3 = sext i8 %b to i32\n"
454       "  %A = select i1 %1, i32 %2, i32 %3\n"
455       "  ret i32 %A\n"
456       "}\n");
457   // The cast types here aren't the same, so we cannot match an UMIN.
458   expectPattern({SPF_UNKNOWN, SPNB_NA, false});
459 }
460 
461 TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) {
462   StringRef Assembly =
463       "declare void @nounwind_readonly(i32*) nounwind readonly "
464       "declare void @nounwind_argmemonly(i32*) nounwind argmemonly "
465       "declare void @throws_but_readonly(i32*) readonly "
466       "declare void @throws_but_argmemonly(i32*) argmemonly "
467       "declare void @nounwind_willreturn(i32*) nounwind willreturn"
468       " "
469       "declare void @unknown(i32*) "
470       " "
471       "define void @f(i32* %p) { "
472       "  call void @nounwind_readonly(i32* %p) "
473       "  call void @nounwind_argmemonly(i32* %p) "
474       "  call void @throws_but_readonly(i32* %p) "
475       "  call void @throws_but_argmemonly(i32* %p) "
476       "  call void @unknown(i32* %p) nounwind readonly "
477       "  call void @unknown(i32* %p) nounwind argmemonly "
478       "  call void @unknown(i32* %p) readonly "
479       "  call void @unknown(i32* %p) argmemonly "
480       "  call void @nounwind_willreturn(i32* %p)"
481       "  ret void "
482       "} ";
483 
484   LLVMContext Context;
485   SMDiagnostic Error;
486   auto M = parseAssemblyString(Assembly, Error, Context);
487   assert(M && "Bad assembly?");
488 
489   auto *F = M->getFunction("f");
490   assert(F && "Bad assembly?");
491 
492   auto &BB = F->getEntryBlock();
493   bool ExpectedAnswers[] = {
494       true,  // call void @nounwind_readonly(i32* %p)
495       true,  // call void @nounwind_argmemonly(i32* %p)
496       false, // call void @throws_but_readonly(i32* %p)
497       false, // call void @throws_but_argmemonly(i32* %p)
498       true,  // call void @unknown(i32* %p) nounwind readonly
499       true,  // call void @unknown(i32* %p) nounwind argmemonly
500       false, // call void @unknown(i32* %p) readonly
501       false, // call void @unknown(i32* %p) argmemonly
502       true,  // call void @nounwind_willreturn(i32* %p)
503       false, // ret void
504   };
505 
506   int Index = 0;
507   for (auto &I : BB) {
508     EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I),
509               ExpectedAnswers[Index])
510         << "Incorrect answer at instruction " << Index << " = " << I;
511     Index++;
512   }
513 }
514 
515 TEST_F(ValueTrackingTest, ComputeNumSignBits_PR32045) {
516   parseAssembly(
517       "define i32 @test(i32 %a) {\n"
518       "  %A = ashr i32 %a, -1\n"
519       "  ret i32 %A\n"
520       "}\n");
521   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
522 }
523 
524 // No guarantees for canonical IR in this analysis, so this just bails out.
525 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle) {
526   parseAssembly(
527       "define <2 x i32> @test() {\n"
528       "  %A = shufflevector <2 x i32> undef, <2 x i32> undef, <2 x i32> <i32 0, i32 0>\n"
529       "  ret <2 x i32> %A\n"
530       "}\n");
531   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
532 }
533 
534 // No guarantees for canonical IR in this analysis, so a shuffle element that
535 // references an undef value means this can't return any extra information.
536 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) {
537   parseAssembly(
538       "define <2 x i32> @test(<2 x i1> %x) {\n"
539       "  %sext = sext <2 x i1> %x to <2 x i32>\n"
540       "  %A = shufflevector <2 x i32> %sext, <2 x i32> undef, <2 x i32> <i32 0, i32 2>\n"
541       "  ret <2 x i32> %A\n"
542       "}\n");
543   EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u);
544 }
545 
546 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
547   parseAssembly(
548       "define i32 @test(i32 %a, i32 %b) {\n"
549       "  %ash = mul i32 %a, 8\n"
550       "  %aad = add i32 %ash, 7\n"
551       "  %aan = and i32 %aad, 4095\n"
552       "  %bsh = shl i32 %b, 4\n"
553       "  %bad = or i32 %bsh, 6\n"
554       "  %ban = and i32 %bad, 4095\n"
555       "  %A = mul i32 %aan, %ban\n"
556       "  ret i32 %A\n"
557       "}\n");
558   expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u);
559 }
560 
561 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) {
562   parseAssembly(
563       "define i32 @test(i32 %a, i32 %b) {\n"
564       "  %aa = shl i32 %a, 5\n"
565       "  %bb = shl i32 %b, 5\n"
566       "  %aaa = or i32 %aa, 24\n"
567       "  %bbb = or i32 %bb, 28\n"
568       "  %A = mul i32 %aaa, %bbb\n"
569       "  ret i32 %A\n"
570       "}\n");
571   expectKnownBits(/*zero*/ 95u, /*one*/ 32u);
572 }
573 
574 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) {
575   // fshl(....1111....0000, 00..1111........, 6)
576   // = 11....000000..11
577   parseAssembly(
578       "define i16 @test(i16 %a, i16 %b) {\n"
579       "  %aa = shl i16 %a, 4\n"
580       "  %bb = lshr i16 %b, 2\n"
581       "  %aaa = or i16 %aa, 3840\n"
582       "  %bbb = or i16 %bb, 3840\n"
583       "  %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n"
584       "  ret i16 %A\n"
585       "}\n"
586       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
587   expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
588 }
589 
590 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) {
591   // fshr(....1111....0000, 00..1111........, 26)
592   // = 11....000000..11
593   parseAssembly(
594       "define i16 @test(i16 %a, i16 %b) {\n"
595       "  %aa = shl i16 %a, 4\n"
596       "  %bb = lshr i16 %b, 2\n"
597       "  %aaa = or i16 %aa, 3840\n"
598       "  %bbb = or i16 %bb, 3840\n"
599       "  %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n"
600       "  ret i16 %A\n"
601       "}\n"
602       "declare i16 @llvm.fshr.i16(i16, i16, i16)\n");
603   expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
604 }
605 
606 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) {
607   // fshl(....1111....0000, 00..1111........, 0)
608   // = ....1111....0000
609   parseAssembly(
610       "define i16 @test(i16 %a, i16 %b) {\n"
611       "  %aa = shl i16 %a, 4\n"
612       "  %bb = lshr i16 %b, 2\n"
613       "  %aaa = or i16 %aa, 3840\n"
614       "  %bbb = or i16 %bb, 3840\n"
615       "  %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n"
616       "  ret i16 %A\n"
617       "}\n"
618       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
619   expectKnownBits(/*zero*/ 15u, /*one*/ 3840u);
620 }
621 
622 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) {
623   // uadd.sat(1111...1, ........)
624   // = 1111....
625   parseAssembly(
626       "define i8 @test(i8 %a, i8 %b) {\n"
627       "  %aa = or i8 %a, 241\n"
628       "  %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n"
629       "  ret i8 %A\n"
630       "}\n"
631       "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
632   expectKnownBits(/*zero*/ 0u, /*one*/ 240u);
633 }
634 
635 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) {
636   // uadd.sat(00...011, .1...110)
637   // = .......1
638   parseAssembly(
639       "define i8 @test(i8 %a, i8 %b) {\n"
640       "  %aa = or i8 %a, 3\n"
641       "  %aaa = and i8 %aa, 59\n"
642       "  %bb = or i8 %b, 70\n"
643       "  %bbb = and i8 %bb, 254\n"
644       "  %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n"
645       "  ret i8 %A\n"
646       "}\n"
647       "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
648   expectKnownBits(/*zero*/ 0u, /*one*/ 1u);
649 }
650 
651 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) {
652   // usub.sat(0000...0, ........)
653   // = 0000....
654   parseAssembly(
655       "define i8 @test(i8 %a, i8 %b) {\n"
656       "  %aa = and i8 %a, 14\n"
657       "  %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n"
658       "  ret i8 %A\n"
659       "}\n"
660       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
661   expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
662 }
663 
664 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) {
665   // usub.sat(........, 1111...1)
666   // = 0000....
667   parseAssembly(
668       "define i8 @test(i8 %a, i8 %b) {\n"
669       "  %bb = or i8 %a, 241\n"
670       "  %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n"
671       "  ret i8 %A\n"
672       "}\n"
673       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
674   expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
675 }
676 
677 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) {
678   // usub.sat(11...011, .1...110)
679   // = ......0.
680   parseAssembly(
681       "define i8 @test(i8 %a, i8 %b) {\n"
682       "  %aa = or i8 %a, 195\n"
683       "  %aaa = and i8 %aa, 251\n"
684       "  %bb = or i8 %b, 70\n"
685       "  %bbb = and i8 %bb, 254\n"
686       "  %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
687       "  ret i8 %A\n"
688       "}\n"
689       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
690   expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
691 }
692