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 
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:
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 
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:
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:
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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.
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.
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 
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 
725 TEST(ValueTracking, canCreatePoisonOrUndef) {
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?, can create undef?, IR instruction)
732   SmallVector<std::pair<std::pair<bool, bool>, std::string>, 32> Data = {
733       {{false, false}, "add i32 %x, %y"},
734       {{true, false}, "add nsw nuw i32 %x, %y"},
735       {{true, false}, "shl i32 %x, %y"},
736       {{true, false}, "shl <4 x i32> %vx, %vx2"},
737       {{true, false}, "shl nsw i32 %x, %y"},
738       {{true, false}, "shl nsw <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
739       {{false, false}, "shl i32 %x, 31"},
740       {{true, false}, "shl i32 %x, 32"},
741       {{false, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
742       {{true, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
743       {{true, false}, "ashr i32 %x, %y"},
744       {{true, false}, "ashr exact i32 %x, %y"},
745       {{false, false}, "ashr i32 %x, 31"},
746       {{true, false}, "ashr exact i32 %x, 31"},
747       {{false, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
748       {{true, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
749       {{true, false}, "ashr exact <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
750       {{true, false}, "lshr i32 %x, %y"},
751       {{true, false}, "lshr exact i32 %x, 31"},
752       {{false, false}, "udiv i32 %x, %y"},
753       {{true, false}, "udiv exact i32 %x, %y"},
754       {{false, false}, "getelementptr i8, i8* %p, i32 %x"},
755       {{true, false}, "getelementptr inbounds i8, i8* %p, i32 %x"},
756       {{true, false}, "fneg nnan float %fx"},
757       {{false, false}, "fneg float %fx"},
758       {{false, false}, "fadd float %fx, %fy"},
759       {{true, false}, "fadd nnan float %fx, %fy"},
760       {{false, false}, "urem i32 %x, %y"},
761       {{true, false}, "fptoui float %fx to i32"},
762       {{true, false}, "fptosi float %fx to i32"},
763       {{false, false}, "bitcast float %fx to i32"},
764       {{false, false}, "select i1 %cond, i32 %x, i32 %y"},
765       {{true, false}, "select nnan i1 %cond, float %fx, float %fy"},
766       {{true, false}, "extractelement <4 x i32> %vx, i32 %x"},
767       {{false, false}, "extractelement <4 x i32> %vx, i32 3"},
768       {{true, false}, "extractelement <vscale x 4 x i32> %svx, i32 4"},
769       {{true, false}, "insertelement <4 x i32> %vx, i32 %x, i32 %y"},
770       {{false, false}, "insertelement <4 x i32> %vx, i32 %x, i32 3"},
771       {{true, false}, "insertelement <vscale x 4 x i32> %svx, i32 %x, i32 4"},
772       {{false, false}, "freeze i32 %x"},
773       {{false, false},
774        "shufflevector <4 x i32> %vx, <4 x i32> %vx2, "
775        "<4 x i32> <i32 0, i32 1, i32 2, i32 3>"},
776       {{false, true},
777        "shufflevector <4 x i32> %vx, <4 x i32> %vx2, "
778        "<4 x i32> <i32 0, i32 1, i32 2, i32 undef>"},
779       {{false, true},
780        "shufflevector <vscale x 4 x i32> %svx, "
781        "<vscale x 4 x i32> %svx, <vscale x 4 x i32> undef"},
782       {{true, false}, "call i32 @g(i32 %x)"},
783       {{false, false}, "call noundef i32 @g(i32 %x)"},
784       {{true, false}, "fcmp nnan oeq float %fx, %fy"},
785       {{false, false}, "fcmp oeq float %fx, %fy"}};
786 
787   std::string AssemblyStr = AsmHead;
788   for (auto &Itm : Data)
789     AssemblyStr += Itm.second + "\n";
790   AssemblyStr += AsmTail;
791 
792   LLVMContext Context;
793   SMDiagnostic Error;
794   auto M = parseAssemblyString(AssemblyStr, Error, Context);
795   assert(M && "Bad assembly?");
796 
797   auto *F = M->getFunction("f");
798   assert(F && "Bad assembly?");
799 
800   auto &BB = F->getEntryBlock();
801 
802   int Index = 0;
803   for (auto &I : BB) {
804     if (isa<ReturnInst>(&I))
805       break;
806     bool Poison = Data[Index].first.first;
807     bool Undef = Data[Index].first.second;
808     EXPECT_EQ(canCreatePoison(cast<Operator>(&I)), Poison)
809         << "Incorrect answer of canCreatePoison at instruction " << Index
810         << " = " << I;
811     EXPECT_EQ(canCreateUndefOrPoison(cast<Operator>(&I)), Undef || Poison)
812         << "Incorrect answer of canCreateUndef at instruction " << Index
813         << " = " << I;
814     Index++;
815   }
816 }
817 
818 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
819   parseAssembly(
820       "define i32 @test(i32 %a, i32 %b) {\n"
821       "  %ash = mul i32 %a, 8\n"
822       "  %aad = add i32 %ash, 7\n"
823       "  %aan = and i32 %aad, 4095\n"
824       "  %bsh = shl i32 %b, 4\n"
825       "  %bad = or i32 %bsh, 6\n"
826       "  %ban = and i32 %bad, 4095\n"
827       "  %A = mul i32 %aan, %ban\n"
828       "  ret i32 %A\n"
829       "}\n");
830   expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u);
831 }
832 
833 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) {
834   parseAssembly(
835       "define i32 @test(i32 %a, i32 %b) {\n"
836       "  %aa = shl i32 %a, 5\n"
837       "  %bb = shl i32 %b, 5\n"
838       "  %aaa = or i32 %aa, 24\n"
839       "  %bbb = or i32 %bb, 28\n"
840       "  %A = mul i32 %aaa, %bbb\n"
841       "  ret i32 %A\n"
842       "}\n");
843   expectKnownBits(/*zero*/ 95u, /*one*/ 32u);
844 }
845 
846 TEST_F(ComputeKnownBitsTest, KnownNonZeroShift) {
847   // %q is known nonzero without known bits.
848   // Because %q is nonzero, %A[0] is known to be zero.
849   parseAssembly(
850       "define i8 @test(i8 %p, i8* %pq) {\n"
851       "  %q = load i8, i8* %pq, !range !0\n"
852       "  %A = shl i8 %p, %q\n"
853       "  ret i8 %A\n"
854       "}\n"
855       "!0 = !{ i8 1, i8 5 }\n");
856   expectKnownBits(/*zero*/ 1u, /*one*/ 0u);
857 }
858 
859 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) {
860   // fshl(....1111....0000, 00..1111........, 6)
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.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n"
869       "  ret i16 %A\n"
870       "}\n"
871       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
872   expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
873 }
874 
875 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) {
876   // fshr(....1111....0000, 00..1111........, 26)
877   // = 11....000000..11
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.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n"
885       "  ret i16 %A\n"
886       "}\n"
887       "declare i16 @llvm.fshr.i16(i16, i16, i16)\n");
888   expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u);
889 }
890 
891 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) {
892   // fshl(....1111....0000, 00..1111........, 0)
893   // = ....1111....0000
894   parseAssembly(
895       "define i16 @test(i16 %a, i16 %b) {\n"
896       "  %aa = shl i16 %a, 4\n"
897       "  %bb = lshr i16 %b, 2\n"
898       "  %aaa = or i16 %aa, 3840\n"
899       "  %bbb = or i16 %bb, 3840\n"
900       "  %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n"
901       "  ret i16 %A\n"
902       "}\n"
903       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
904   expectKnownBits(/*zero*/ 15u, /*one*/ 3840u);
905 }
906 
907 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) {
908   // uadd.sat(1111...1, ........)
909   // = 1111....
910   parseAssembly(
911       "define i8 @test(i8 %a, i8 %b) {\n"
912       "  %aa = or i8 %a, 241\n"
913       "  %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n"
914       "  ret i8 %A\n"
915       "}\n"
916       "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
917   expectKnownBits(/*zero*/ 0u, /*one*/ 240u);
918 }
919 
920 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) {
921   // uadd.sat(00...011, .1...110)
922   // = .......1
923   parseAssembly(
924       "define i8 @test(i8 %a, i8 %b) {\n"
925       "  %aa = or i8 %a, 3\n"
926       "  %aaa = and i8 %aa, 59\n"
927       "  %bb = or i8 %b, 70\n"
928       "  %bbb = and i8 %bb, 254\n"
929       "  %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n"
930       "  ret i8 %A\n"
931       "}\n"
932       "declare i8 @llvm.uadd.sat.i8(i8, i8)\n");
933   expectKnownBits(/*zero*/ 0u, /*one*/ 1u);
934 }
935 
936 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) {
937   // usub.sat(0000...0, ........)
938   // = 0000....
939   parseAssembly(
940       "define i8 @test(i8 %a, i8 %b) {\n"
941       "  %aa = and i8 %a, 14\n"
942       "  %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n"
943       "  ret i8 %A\n"
944       "}\n"
945       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
946   expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
947 }
948 
949 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) {
950   // usub.sat(........, 1111...1)
951   // = 0000....
952   parseAssembly(
953       "define i8 @test(i8 %a, i8 %b) {\n"
954       "  %bb = or i8 %a, 241\n"
955       "  %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n"
956       "  ret i8 %A\n"
957       "}\n"
958       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
959   expectKnownBits(/*zero*/ 240u, /*one*/ 0u);
960 }
961 
962 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) {
963   // usub.sat(11...011, .1...110)
964   // = ......0.
965   parseAssembly(
966       "define i8 @test(i8 %a, i8 %b) {\n"
967       "  %aa = or i8 %a, 195\n"
968       "  %aaa = and i8 %aa, 251\n"
969       "  %bb = or i8 %b, 70\n"
970       "  %bbb = and i8 %bb, 254\n"
971       "  %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
972       "  ret i8 %A\n"
973       "}\n"
974       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
975   expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
976 }
977 
978 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntTrunc) {
979   // ptrtoint truncates the pointer type.
980   parseAssembly(
981       "define void @test(i8** %p) {\n"
982       "  %A = load i8*, i8** %p\n"
983       "  %i = ptrtoint i8* %A to i32\n"
984       "  %m = and i32 %i, 31\n"
985       "  %c = icmp eq i32 %m, 0\n"
986       "  call void @llvm.assume(i1 %c)\n"
987       "  ret void\n"
988       "}\n"
989       "declare void @llvm.assume(i1)\n");
990   AssumptionCache AC(*F);
991   KnownBits Known = computeKnownBits(
992       A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
993   EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
994   EXPECT_EQ(Known.One.getZExtValue(), 0u);
995 }
996 
997 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntZext) {
998   // ptrtoint zero extends the pointer type.
999   parseAssembly(
1000       "define void @test(i8** %p) {\n"
1001       "  %A = load i8*, i8** %p\n"
1002       "  %i = ptrtoint i8* %A to i128\n"
1003       "  %m = and i128 %i, 31\n"
1004       "  %c = icmp eq i128 %m, 0\n"
1005       "  call void @llvm.assume(i1 %c)\n"
1006       "  ret void\n"
1007       "}\n"
1008       "declare void @llvm.assume(i1)\n");
1009   AssumptionCache AC(*F);
1010   KnownBits Known = computeKnownBits(
1011       A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
1012   EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
1013   EXPECT_EQ(Known.One.getZExtValue(), 0u);
1014 }
1015 
1016 class IsBytewiseValueTest : public ValueTrackingTest,
1017                             public ::testing::WithParamInterface<
1018                                 std::pair<const char *, const char *>> {
1019 protected:
1020 };
1021 
1022 const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
1023     {
1024         "i8 0",
1025         "i48* null",
1026     },
1027     {
1028         "i8 undef",
1029         "i48* undef",
1030     },
1031     {
1032         "i8 0",
1033         "i8 zeroinitializer",
1034     },
1035     {
1036         "i8 0",
1037         "i8 0",
1038     },
1039     {
1040         "i8 -86",
1041         "i8 -86",
1042     },
1043     {
1044         "i8 -1",
1045         "i8 -1",
1046     },
1047     {
1048         "i8 undef",
1049         "i16 undef",
1050     },
1051     {
1052         "i8 0",
1053         "i16 0",
1054     },
1055     {
1056         "",
1057         "i16 7",
1058     },
1059     {
1060         "i8 -86",
1061         "i16 -21846",
1062     },
1063     {
1064         "i8 -1",
1065         "i16 -1",
1066     },
1067     {
1068         "i8 0",
1069         "i48 0",
1070     },
1071     {
1072         "i8 -1",
1073         "i48 -1",
1074     },
1075     {
1076         "i8 0",
1077         "i49 0",
1078     },
1079     {
1080         "",
1081         "i49 -1",
1082     },
1083     {
1084         "i8 0",
1085         "half 0xH0000",
1086     },
1087     {
1088         "i8 -85",
1089         "half 0xHABAB",
1090     },
1091     {
1092         "i8 0",
1093         "float 0.0",
1094     },
1095     {
1096         "i8 -1",
1097         "float 0xFFFFFFFFE0000000",
1098     },
1099     {
1100         "i8 0",
1101         "double 0.0",
1102     },
1103     {
1104         "i8 -15",
1105         "double 0xF1F1F1F1F1F1F1F1",
1106     },
1107     {
1108         "i8 undef",
1109         "i16* undef",
1110     },
1111     {
1112         "i8 0",
1113         "i16* inttoptr (i64 0 to i16*)",
1114     },
1115     {
1116         "i8 -1",
1117         "i16* inttoptr (i64 -1 to i16*)",
1118     },
1119     {
1120         "i8 -86",
1121         "i16* inttoptr (i64 -6148914691236517206 to i16*)",
1122     },
1123     {
1124         "",
1125         "i16* inttoptr (i48 -1 to i16*)",
1126     },
1127     {
1128         "i8 -1",
1129         "i16* inttoptr (i96 -1 to i16*)",
1130     },
1131     {
1132         "i8 undef",
1133         "[0 x i8] zeroinitializer",
1134     },
1135     {
1136         "i8 undef",
1137         "[0 x i8] undef",
1138     },
1139     {
1140         "i8 undef",
1141         "[5 x [0 x i8]] zeroinitializer",
1142     },
1143     {
1144         "i8 undef",
1145         "[5 x [0 x i8]] undef",
1146     },
1147     {
1148         "i8 0",
1149         "[6 x i8] zeroinitializer",
1150     },
1151     {
1152         "i8 undef",
1153         "[6 x i8] undef",
1154     },
1155     {
1156         "i8 1",
1157         "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]",
1158     },
1159     {
1160         "",
1161         "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]",
1162     },
1163     {
1164         "i8 -1",
1165         "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]",
1166     },
1167     {
1168         "",
1169         "[4 x i8] [i8 1, i8 2, i8 1, i8 1]",
1170     },
1171     {
1172         "i8 1",
1173         "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]",
1174     },
1175     {
1176         "i8 0",
1177         "<6 x i8> zeroinitializer",
1178     },
1179     {
1180         "i8 undef",
1181         "<6 x i8> undef",
1182     },
1183     {
1184         "i8 1",
1185         "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>",
1186     },
1187     {
1188         "",
1189         "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>",
1190     },
1191     {
1192         "i8 -1",
1193         "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>",
1194     },
1195     {
1196         "",
1197         "<4 x i8> <i8 1, i8 1, i8 2, i8 1>",
1198     },
1199     {
1200         "i8 5",
1201         "<2 x i8> < i8 5, i8 undef >",
1202     },
1203     {
1204         "i8 0",
1205         "[2 x [2 x i16]] zeroinitializer",
1206     },
1207     {
1208         "i8 undef",
1209         "[2 x [2 x i16]] undef",
1210     },
1211     {
1212         "i8 -86",
1213         "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
1214         "[2 x i16] [i16 -21846, i16 -21846]]",
1215     },
1216     {
1217         "",
1218         "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
1219         "[2 x i16] [i16 -21836, i16 -21846]]",
1220     },
1221     {
1222         "i8 undef",
1223         "{ } zeroinitializer",
1224     },
1225     {
1226         "i8 undef",
1227         "{ } undef",
1228     },
1229     {
1230         "i8 undef",
1231         "{ {}, {} } zeroinitializer",
1232     },
1233     {
1234         "i8 undef",
1235         "{ {}, {} } undef",
1236     },
1237     {
1238         "i8 0",
1239         "{i8, i64, i16*} zeroinitializer",
1240     },
1241     {
1242         "i8 undef",
1243         "{i8, i64, i16*} undef",
1244     },
1245     {
1246         "i8 -86",
1247         "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}",
1248     },
1249     {
1250         "",
1251         "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}",
1252     },
1253 };
1254 
1255 INSTANTIATE_TEST_CASE_P(IsBytewiseValueParamTests, IsBytewiseValueTest,
1256                         ::testing::ValuesIn(IsBytewiseValueTests),);
1257 
1258 TEST_P(IsBytewiseValueTest, IsBytewiseValue) {
1259   auto M = parseModule(std::string("@test = global ") + GetParam().second);
1260   GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
1261   Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout());
1262   std::string Buff;
1263   raw_string_ostream S(Buff);
1264   if (Actual)
1265     S << *Actual;
1266   EXPECT_EQ(GetParam().first, S.str());
1267 }
1268 
1269 TEST_F(ValueTrackingTest, ComputeConstantRange) {
1270   {
1271     // Assumptions:
1272     //  * stride >= 5
1273     //  * stride < 10
1274     //
1275     // stride = [5, 10)
1276     auto M = parseModule(R"(
1277   declare void @llvm.assume(i1)
1278 
1279   define i32 @test(i32 %stride) {
1280     %gt = icmp uge i32 %stride, 5
1281     call void @llvm.assume(i1 %gt)
1282     %lt = icmp ult i32 %stride, 10
1283     call void @llvm.assume(i1 %lt)
1284     %stride.plus.one = add nsw nuw i32 %stride, 1
1285     ret i32 %stride.plus.one
1286   })");
1287     Function *F = M->getFunction("test");
1288 
1289     AssumptionCache AC(*F);
1290     Value *Stride = &*F->arg_begin();
1291     ConstantRange CR1 = computeConstantRange(Stride, true, &AC, nullptr);
1292     EXPECT_TRUE(CR1.isFullSet());
1293 
1294     Instruction *I = &findInstructionByName(F, "stride.plus.one");
1295     ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I);
1296     EXPECT_EQ(5, CR2.getLower());
1297     EXPECT_EQ(10, CR2.getUpper());
1298   }
1299 
1300   {
1301     // Assumptions:
1302     //  * stride >= 5
1303     //  * stride < 200
1304     //  * stride == 99
1305     //
1306     // stride = [99, 100)
1307     auto M = parseModule(R"(
1308   declare void @llvm.assume(i1)
1309 
1310   define i32 @test(i32 %stride) {
1311     %gt = icmp uge i32 %stride, 5
1312     call void @llvm.assume(i1 %gt)
1313     %lt = icmp ult i32 %stride, 200
1314     call void @llvm.assume(i1 %lt)
1315     %eq = icmp eq i32 %stride, 99
1316     call void @llvm.assume(i1 %eq)
1317     %stride.plus.one = add nsw nuw i32 %stride, 1
1318     ret i32 %stride.plus.one
1319   })");
1320     Function *F = M->getFunction("test");
1321 
1322     AssumptionCache AC(*F);
1323     Value *Stride = &*F->arg_begin();
1324     Instruction *I = &findInstructionByName(F, "stride.plus.one");
1325     ConstantRange CR = computeConstantRange(Stride, true, &AC, I);
1326     EXPECT_EQ(99, *CR.getSingleElement());
1327   }
1328 
1329   {
1330     // Assumptions:
1331     //  * stride >= 5
1332     //  * stride >= 50
1333     //  * stride < 100
1334     //  * stride < 200
1335     //
1336     // stride = [50, 100)
1337     auto M = parseModule(R"(
1338   declare void @llvm.assume(i1)
1339 
1340   define i32 @test(i32 %stride, i1 %cond) {
1341     %gt = icmp uge i32 %stride, 5
1342     call void @llvm.assume(i1 %gt)
1343     %gt.2 = icmp uge i32 %stride, 50
1344     call void @llvm.assume(i1 %gt.2)
1345     br i1 %cond, label %bb1, label %bb2
1346 
1347   bb1:
1348     %lt = icmp ult i32 %stride, 200
1349     call void @llvm.assume(i1 %lt)
1350     %lt.2 = icmp ult i32 %stride, 100
1351     call void @llvm.assume(i1 %lt.2)
1352     %stride.plus.one = add nsw nuw i32 %stride, 1
1353     ret i32 %stride.plus.one
1354 
1355   bb2:
1356     ret i32 0
1357   })");
1358     Function *F = M->getFunction("test");
1359 
1360     AssumptionCache AC(*F);
1361     Value *Stride = &*F->arg_begin();
1362     Instruction *GT2 = &findInstructionByName(F, "gt.2");
1363     ConstantRange CR = computeConstantRange(Stride, true, &AC, GT2);
1364     EXPECT_EQ(5, CR.getLower());
1365     EXPECT_EQ(0, CR.getUpper());
1366 
1367     Instruction *I = &findInstructionByName(F, "stride.plus.one");
1368     ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I);
1369     EXPECT_EQ(50, CR2.getLower());
1370     EXPECT_EQ(100, CR2.getUpper());
1371   }
1372 
1373   {
1374     // Assumptions:
1375     //  * stride > 5
1376     //  * stride < 5
1377     //
1378     // stride = empty range, as the assumptions contradict each other.
1379     auto M = parseModule(R"(
1380   declare void @llvm.assume(i1)
1381 
1382   define i32 @test(i32 %stride, i1 %cond) {
1383     %gt = icmp ugt i32 %stride, 5
1384     call void @llvm.assume(i1 %gt)
1385     %lt = icmp ult i32 %stride, 5
1386     call void @llvm.assume(i1 %lt)
1387     %stride.plus.one = add nsw nuw i32 %stride, 1
1388     ret i32 %stride.plus.one
1389   })");
1390     Function *F = M->getFunction("test");
1391 
1392     AssumptionCache AC(*F);
1393     Value *Stride = &*F->arg_begin();
1394 
1395     Instruction *I = &findInstructionByName(F, "stride.plus.one");
1396     ConstantRange CR = computeConstantRange(Stride, true, &AC, I);
1397     EXPECT_TRUE(CR.isEmptySet());
1398   }
1399 
1400   {
1401     // Assumptions:
1402     //  * x.1 >= 5
1403     //  * x.2 < x.1
1404     //
1405     // stride = [0, 5)
1406     auto M = parseModule(R"(
1407   declare void @llvm.assume(i1)
1408 
1409   define i32 @test(i32 %x.1, i32 %x.2) {
1410     %gt = icmp uge i32 %x.1, 5
1411     call void @llvm.assume(i1 %gt)
1412     %lt = icmp ult i32 %x.2, %x.1
1413     call void @llvm.assume(i1 %lt)
1414     %stride.plus.one = add nsw nuw i32 %x.1, 1
1415     ret i32 %stride.plus.one
1416   })");
1417     Function *F = M->getFunction("test");
1418 
1419     AssumptionCache AC(*F);
1420     Value *X2 = &*std::next(F->arg_begin());
1421 
1422     Instruction *I = &findInstructionByName(F, "stride.plus.one");
1423     ConstantRange CR1 = computeConstantRange(X2, true, &AC, I);
1424     EXPECT_EQ(0, CR1.getLower());
1425     EXPECT_EQ(5, CR1.getUpper());
1426 
1427     // Check the depth cutoff results in a conservative result (full set) by
1428     // passing Depth == MaxDepth == 6.
1429     ConstantRange CR2 = computeConstantRange(X2, true, &AC, I, 6);
1430     EXPECT_TRUE(CR2.isFullSet());
1431   }
1432 }
1433