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/Dominators.h" 14 #include "llvm/IR/Function.h" 15 #include "llvm/IR/InstIterator.h" 16 #include "llvm/IR/Instructions.h" 17 #include "llvm/IR/LLVMContext.h" 18 #include "llvm/IR/Module.h" 19 #include "llvm/Support/ErrorHandling.h" 20 #include "llvm/Support/KnownBits.h" 21 #include "llvm/Support/SourceMgr.h" 22 #include "llvm/Transforms/Utils/Local.h" 23 #include "gtest/gtest.h" 24 25 using namespace llvm; 26 27 namespace { 28 29 static Instruction *findInstructionByNameOrNull(Function *F, StringRef Name) { 30 for (Instruction &I : instructions(F)) 31 if (I.getName() == Name) 32 return &I; 33 34 return nullptr; 35 } 36 37 static Instruction &findInstructionByName(Function *F, StringRef Name) { 38 auto *I = findInstructionByNameOrNull(F, Name); 39 if (I) 40 return *I; 41 42 llvm_unreachable("Expected value not found"); 43 } 44 45 class ValueTrackingTest : public testing::Test { 46 protected: 47 std::unique_ptr<Module> parseModule(StringRef Assembly) { 48 SMDiagnostic Error; 49 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context); 50 51 std::string errMsg; 52 raw_string_ostream os(errMsg); 53 Error.print("", os); 54 EXPECT_TRUE(M) << os.str(); 55 56 return M; 57 } 58 59 void parseAssembly(StringRef Assembly) { 60 M = parseModule(Assembly); 61 ASSERT_TRUE(M); 62 63 F = M->getFunction("test"); 64 ASSERT_TRUE(F) << "Test must have a function @test"; 65 if (!F) 66 return; 67 68 A = findInstructionByNameOrNull(F, "A"); 69 ASSERT_TRUE(A) << "@test must have an instruction %A"; 70 A2 = findInstructionByNameOrNull(F, "A2"); 71 A3 = findInstructionByNameOrNull(F, "A3"); 72 A4 = findInstructionByNameOrNull(F, "A4"); 73 74 CxtI = findInstructionByNameOrNull(F, "CxtI"); 75 CxtI2 = findInstructionByNameOrNull(F, "CxtI2"); 76 CxtI3 = findInstructionByNameOrNull(F, "CxtI3"); 77 } 78 79 LLVMContext Context; 80 std::unique_ptr<Module> M; 81 Function *F = nullptr; 82 Instruction *A = nullptr; 83 // Instructions (optional) 84 Instruction *A2 = nullptr, *A3 = nullptr, *A4 = nullptr; 85 86 // Context instructions (optional) 87 Instruction *CxtI = nullptr, *CxtI2 = nullptr, *CxtI3 = nullptr; 88 }; 89 90 class MatchSelectPatternTest : public ValueTrackingTest { 91 protected: 92 void expectPattern(const SelectPatternResult &P) { 93 Value *LHS, *RHS; 94 Instruction::CastOps CastOp; 95 SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp); 96 EXPECT_EQ(P.Flavor, R.Flavor); 97 EXPECT_EQ(P.NaNBehavior, R.NaNBehavior); 98 EXPECT_EQ(P.Ordered, R.Ordered); 99 } 100 }; 101 102 class ComputeKnownBitsTest : public ValueTrackingTest { 103 protected: 104 void expectKnownBits(uint64_t Zero, uint64_t One) { 105 auto Known = computeKnownBits(A, M->getDataLayout()); 106 ASSERT_FALSE(Known.hasConflict()); 107 EXPECT_EQ(Known.One.getZExtValue(), One); 108 EXPECT_EQ(Known.Zero.getZExtValue(), Zero); 109 } 110 }; 111 112 } 113 114 TEST_F(MatchSelectPatternTest, SimpleFMin) { 115 parseAssembly( 116 "define float @test(float %a) {\n" 117 " %1 = fcmp ult float %a, 5.0\n" 118 " %A = select i1 %1, float %a, float 5.0\n" 119 " ret float %A\n" 120 "}\n"); 121 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false}); 122 } 123 124 TEST_F(MatchSelectPatternTest, SimpleFMax) { 125 parseAssembly( 126 "define float @test(float %a) {\n" 127 " %1 = fcmp ogt float %a, 5.0\n" 128 " %A = select i1 %1, float %a, float 5.0\n" 129 " ret float %A\n" 130 "}\n"); 131 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true}); 132 } 133 134 TEST_F(MatchSelectPatternTest, SwappedFMax) { 135 parseAssembly( 136 "define float @test(float %a) {\n" 137 " %1 = fcmp olt float 5.0, %a\n" 138 " %A = select i1 %1, float %a, float 5.0\n" 139 " ret float %A\n" 140 "}\n"); 141 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false}); 142 } 143 144 TEST_F(MatchSelectPatternTest, SwappedFMax2) { 145 parseAssembly( 146 "define float @test(float %a) {\n" 147 " %1 = fcmp olt float %a, 5.0\n" 148 " %A = select i1 %1, float 5.0, float %a\n" 149 " ret float %A\n" 150 "}\n"); 151 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false}); 152 } 153 154 TEST_F(MatchSelectPatternTest, SwappedFMax3) { 155 parseAssembly( 156 "define float @test(float %a) {\n" 157 " %1 = fcmp ult float %a, 5.0\n" 158 " %A = select i1 %1, float 5.0, float %a\n" 159 " ret float %A\n" 160 "}\n"); 161 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true}); 162 } 163 164 TEST_F(MatchSelectPatternTest, FastFMin) { 165 parseAssembly( 166 "define float @test(float %a) {\n" 167 " %1 = fcmp nnan olt float %a, 5.0\n" 168 " %A = select i1 %1, float %a, float 5.0\n" 169 " ret float %A\n" 170 "}\n"); 171 expectPattern({SPF_FMINNUM, SPNB_RETURNS_ANY, false}); 172 } 173 174 TEST_F(MatchSelectPatternTest, FMinConstantZero) { 175 parseAssembly( 176 "define float @test(float %a) {\n" 177 " %1 = fcmp ole float %a, 0.0\n" 178 " %A = select i1 %1, float %a, float 0.0\n" 179 " ret float %A\n" 180 "}\n"); 181 // This shouldn't be matched, as %a could be -0.0. 182 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 183 } 184 185 TEST_F(MatchSelectPatternTest, FMinConstantZeroNsz) { 186 parseAssembly( 187 "define float @test(float %a) {\n" 188 " %1 = fcmp nsz ole float %a, 0.0\n" 189 " %A = select i1 %1, float %a, float 0.0\n" 190 " ret float %A\n" 191 "}\n"); 192 // But this should be, because we've ignored signed zeroes. 193 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true}); 194 } 195 196 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero1) { 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, FMinMismatchConstantZero2) { 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, FMinMismatchConstantZero3) { 219 parseAssembly( 220 "define float @test(float %a) {\n" 221 " %1 = fcmp olt float 0.0, %a\n" 222 " %A = select i1 %1, float -0.0, float %a\n" 223 " ret float %A\n" 224 "}\n"); 225 // The sign of zero doesn't matter in fcmp. 226 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, true}); 227 } 228 229 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero4) { 230 parseAssembly( 231 "define float @test(float %a) {\n" 232 " %1 = fcmp ogt float %a, 0.0\n" 233 " %A = select i1 %1, float -0.0, float %a\n" 234 " ret float %A\n" 235 "}\n"); 236 // The sign of zero doesn't matter in fcmp. 237 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false}); 238 } 239 240 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero5) { 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, FMinMismatchConstantZero6) { 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, FMinMismatchConstantZero7) { 263 parseAssembly( 264 "define float @test(float %a) {\n" 265 " %1 = fcmp ogt float 0.0, %a\n" 266 " %A = select i1 %1, float %a, float -0.0\n" 267 " ret float %A\n" 268 "}\n"); 269 // The sign of zero doesn't matter in fcmp. 270 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, false}); 271 } 272 273 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero8) { 274 parseAssembly( 275 "define float @test(float %a) {\n" 276 " %1 = fcmp olt float %a, 0.0\n" 277 " %A = select i1 %1, float %a, float -0.0\n" 278 " ret float %A\n" 279 "}\n"); 280 // The sign of zero doesn't matter in fcmp. 281 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true}); 282 } 283 284 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero1) { 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, FMaxMismatchConstantZero2) { 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, FMaxMismatchConstantZero3) { 307 parseAssembly( 308 "define float @test(float %a) {\n" 309 " %1 = fcmp ogt float 0.0, %a\n" 310 " %A = select i1 %1, float -0.0, float %a\n" 311 " ret float %A\n" 312 "}\n"); 313 // The sign of zero doesn't matter in fcmp. 314 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, true}); 315 } 316 317 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero4) { 318 parseAssembly( 319 "define float @test(float %a) {\n" 320 " %1 = fcmp olt float %a, 0.0\n" 321 " %A = select i1 %1, float -0.0, float %a\n" 322 " ret float %A\n" 323 "}\n"); 324 // The sign of zero doesn't matter in fcmp. 325 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false}); 326 } 327 328 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero5) { 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, FMaxMismatchConstantZero6) { 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, FMaxMismatchConstantZero7) { 351 parseAssembly( 352 "define float @test(float %a) {\n" 353 " %1 = fcmp olt float 0.0, %a\n" 354 " %A = select i1 %1, float %a, float -0.0\n" 355 " ret float %A\n" 356 "}\n"); 357 // The sign of zero doesn't matter in fcmp. 358 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false}); 359 } 360 361 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero8) { 362 parseAssembly( 363 "define float @test(float %a) {\n" 364 " %1 = fcmp ogt float %a, 0.0\n" 365 " %A = select i1 %1, float %a, float -0.0\n" 366 " ret float %A\n" 367 "}\n"); 368 // The sign of zero doesn't matter in fcmp. 369 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true}); 370 } 371 372 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZeroVecUndef) { 373 parseAssembly( 374 "define <2 x float> @test(<2 x float> %a) {\n" 375 " %1 = fcmp ogt <2 x float> %a, <float -0.0, float -0.0>\n" 376 " %A = select <2 x i1> %1, <2 x float> <float undef, float 0.0>, <2 x float> %a\n" 377 " ret <2 x float> %A\n" 378 "}\n"); 379 // An undef in a vector constant can not be back-propagated for this analysis. 380 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 381 } 382 383 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZeroVecUndef) { 384 parseAssembly( 385 "define <2 x float> @test(<2 x float> %a) {\n" 386 " %1 = fcmp ogt <2 x float> %a, zeroinitializer\n" 387 " %A = select <2 x i1> %1, <2 x float> %a, <2 x float> <float -0.0, float undef>\n" 388 " ret <2 x float> %A\n" 389 "}\n"); 390 // An undef in a vector constant can not be back-propagated for this analysis. 391 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 392 } 393 394 TEST_F(MatchSelectPatternTest, VectorFMinimum) { 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 5.0, 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 5.0, float 5.0, float 5.0>\n" 401 " ret <4 x float> %A\n" 402 "}\n"); 403 // Check that pattern matching works on vectors where each lane has the same 404 // unordered pattern. 405 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false}); 406 } 407 408 TEST_F(MatchSelectPatternTest, VectorFMinOtherOrdered) { 409 parseAssembly( 410 "define <4 x float> @test(<4 x float> %a) {\n" 411 " %1 = fcmp ole <4 x float> %a, \n" 412 " <float 5.0, float 5.0, float 5.0, float 5.0>\n" 413 " %A = select <4 x i1> %1, <4 x float> %a,\n" 414 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n" 415 " ret <4 x float> %A\n" 416 "}\n"); 417 // Check that pattern matching works on vectors where each lane has the same 418 // ordered pattern. 419 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true}); 420 } 421 422 TEST_F(MatchSelectPatternTest, VectorNotFMinimum) { 423 parseAssembly( 424 "define <4 x float> @test(<4 x float> %a) {\n" 425 " %1 = fcmp ule <4 x float> %a, \n" 426 " <float 5.0, float 0x7ff8000000000000, float 5.0, float 5.0>\n" 427 " %A = select <4 x i1> %1, <4 x float> %a,\n" 428 " <4 x float> <float 5.0, float 0x7ff8000000000000, float 5.0, float " 429 "5.0>\n" 430 " ret <4 x float> %A\n" 431 "}\n"); 432 // The lane that contains a NaN (0x7ff80...) behaves like a 433 // non-NaN-propagating min and the other lines behave like a NaN-propagating 434 // min, so check that neither is returned. 435 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 436 } 437 438 TEST_F(MatchSelectPatternTest, VectorNotFMinZero) { 439 parseAssembly( 440 "define <4 x float> @test(<4 x float> %a) {\n" 441 " %1 = fcmp ule <4 x float> %a, \n" 442 " <float 5.0, float -0.0, float 5.0, float 5.0>\n" 443 " %A = select <4 x i1> %1, <4 x float> %a,\n" 444 " <4 x float> <float 5.0, float 0.0, float 5.0, float 5.0>\n" 445 " ret <4 x float> %A\n" 446 "}\n"); 447 // Always selects the second lane of %a if it is positive or negative zero, so 448 // this is stricter than a min. 449 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 450 } 451 452 TEST_F(MatchSelectPatternTest, DoubleCastU) { 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 = zext i8 %b to i32\n" 458 " %A = select i1 %1, i32 %2, i32 %3\n" 459 " ret i32 %A\n" 460 "}\n"); 461 // We should be able to look through the situation where we cast both operands 462 // to the select. 463 expectPattern({SPF_UMIN, SPNB_NA, false}); 464 } 465 466 TEST_F(MatchSelectPatternTest, DoubleCastS) { 467 parseAssembly( 468 "define i32 @test(i8 %a, i8 %b) {\n" 469 " %1 = icmp slt i8 %a, %b\n" 470 " %2 = sext i8 %a to i32\n" 471 " %3 = sext i8 %b to i32\n" 472 " %A = select i1 %1, i32 %2, i32 %3\n" 473 " ret i32 %A\n" 474 "}\n"); 475 // We should be able to look through the situation where we cast both operands 476 // to the select. 477 expectPattern({SPF_SMIN, SPNB_NA, false}); 478 } 479 480 TEST_F(MatchSelectPatternTest, DoubleCastBad) { 481 parseAssembly( 482 "define i32 @test(i8 %a, i8 %b) {\n" 483 " %1 = icmp ult i8 %a, %b\n" 484 " %2 = zext i8 %a to i32\n" 485 " %3 = sext i8 %b to i32\n" 486 " %A = select i1 %1, i32 %2, i32 %3\n" 487 " ret i32 %A\n" 488 "}\n"); 489 // The cast types here aren't the same, so we cannot match an UMIN. 490 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 491 } 492 493 TEST_F(MatchSelectPatternTest, NotNotSMin) { 494 parseAssembly( 495 "define i8 @test(i8 %a, i8 %b) {\n" 496 " %cmp = icmp sgt i8 %a, %b\n" 497 " %an = xor i8 %a, -1\n" 498 " %bn = xor i8 %b, -1\n" 499 " %A = select i1 %cmp, i8 %an, i8 %bn\n" 500 " ret i8 %A\n" 501 "}\n"); 502 expectPattern({SPF_SMIN, SPNB_NA, false}); 503 } 504 505 TEST_F(MatchSelectPatternTest, NotNotSMinSwap) { 506 parseAssembly( 507 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n" 508 " %cmp = icmp slt <2 x i8> %a, %b\n" 509 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n" 510 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n" 511 " %A = select <2 x i1> %cmp, <2 x i8> %bn, <2 x i8> %an\n" 512 " ret <2 x i8> %A\n" 513 "}\n"); 514 expectPattern({SPF_SMIN, SPNB_NA, false}); 515 } 516 517 TEST_F(MatchSelectPatternTest, NotNotSMax) { 518 parseAssembly( 519 "define i8 @test(i8 %a, i8 %b) {\n" 520 " %cmp = icmp slt i8 %a, %b\n" 521 " %an = xor i8 %a, -1\n" 522 " %bn = xor i8 %b, -1\n" 523 " %A = select i1 %cmp, i8 %an, i8 %bn\n" 524 " ret i8 %A\n" 525 "}\n"); 526 expectPattern({SPF_SMAX, SPNB_NA, false}); 527 } 528 529 TEST_F(MatchSelectPatternTest, NotNotSMaxSwap) { 530 parseAssembly( 531 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n" 532 " %cmp = icmp sgt <2 x i8> %a, %b\n" 533 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n" 534 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n" 535 " %A = select <2 x i1> %cmp, <2 x i8> %bn, <2 x i8> %an\n" 536 " ret <2 x i8> %A\n" 537 "}\n"); 538 expectPattern({SPF_SMAX, SPNB_NA, false}); 539 } 540 541 TEST_F(MatchSelectPatternTest, NotNotUMin) { 542 parseAssembly( 543 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n" 544 " %cmp = icmp ugt <2 x i8> %a, %b\n" 545 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n" 546 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n" 547 " %A = select <2 x i1> %cmp, <2 x i8> %an, <2 x i8> %bn\n" 548 " ret <2 x i8> %A\n" 549 "}\n"); 550 expectPattern({SPF_UMIN, SPNB_NA, false}); 551 } 552 553 TEST_F(MatchSelectPatternTest, NotNotUMinSwap) { 554 parseAssembly( 555 "define i8 @test(i8 %a, i8 %b) {\n" 556 " %cmp = icmp ult i8 %a, %b\n" 557 " %an = xor i8 %a, -1\n" 558 " %bn = xor i8 %b, -1\n" 559 " %A = select i1 %cmp, i8 %bn, i8 %an\n" 560 " ret i8 %A\n" 561 "}\n"); 562 expectPattern({SPF_UMIN, SPNB_NA, false}); 563 } 564 565 TEST_F(MatchSelectPatternTest, NotNotUMax) { 566 parseAssembly( 567 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n" 568 " %cmp = icmp ult <2 x i8> %a, %b\n" 569 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n" 570 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n" 571 " %A = select <2 x i1> %cmp, <2 x i8> %an, <2 x i8> %bn\n" 572 " ret <2 x i8> %A\n" 573 "}\n"); 574 expectPattern({SPF_UMAX, SPNB_NA, false}); 575 } 576 577 TEST_F(MatchSelectPatternTest, NotNotUMaxSwap) { 578 parseAssembly( 579 "define i8 @test(i8 %a, i8 %b) {\n" 580 " %cmp = icmp ugt i8 %a, %b\n" 581 " %an = xor i8 %a, -1\n" 582 " %bn = xor i8 %b, -1\n" 583 " %A = select i1 %cmp, i8 %bn, i8 %an\n" 584 " ret i8 %A\n" 585 "}\n"); 586 expectPattern({SPF_UMAX, SPNB_NA, false}); 587 } 588 589 TEST_F(MatchSelectPatternTest, NotNotEq) { 590 parseAssembly( 591 "define i8 @test(i8 %a, i8 %b) {\n" 592 " %cmp = icmp eq i8 %a, %b\n" 593 " %an = xor i8 %a, -1\n" 594 " %bn = xor i8 %b, -1\n" 595 " %A = select i1 %cmp, i8 %bn, i8 %an\n" 596 " ret i8 %A\n" 597 "}\n"); 598 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 599 } 600 601 TEST_F(MatchSelectPatternTest, NotNotNe) { 602 parseAssembly( 603 "define i8 @test(i8 %a, i8 %b) {\n" 604 " %cmp = icmp ne i8 %a, %b\n" 605 " %an = xor i8 %a, -1\n" 606 " %bn = xor i8 %b, -1\n" 607 " %A = select i1 %cmp, i8 %bn, i8 %an\n" 608 " ret i8 %A\n" 609 "}\n"); 610 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 611 } 612 613 TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) { 614 StringRef Assembly = 615 "declare void @nounwind_readonly(i32*) nounwind readonly " 616 "declare void @nounwind_argmemonly(i32*) nounwind argmemonly " 617 "declare void @throws_but_readonly(i32*) readonly " 618 "declare void @throws_but_argmemonly(i32*) argmemonly " 619 "declare void @nounwind_willreturn(i32*) nounwind willreturn" 620 " " 621 "declare void @unknown(i32*) " 622 " " 623 "define void @f(i32* %p) { " 624 " call void @nounwind_readonly(i32* %p) " 625 " call void @nounwind_argmemonly(i32* %p) " 626 " call void @throws_but_readonly(i32* %p) " 627 " call void @throws_but_argmemonly(i32* %p) " 628 " call void @unknown(i32* %p) nounwind readonly " 629 " call void @unknown(i32* %p) nounwind argmemonly " 630 " call void @unknown(i32* %p) readonly " 631 " call void @unknown(i32* %p) argmemonly " 632 " call void @nounwind_willreturn(i32* %p)" 633 " ret void " 634 "} "; 635 636 LLVMContext Context; 637 SMDiagnostic Error; 638 auto M = parseAssemblyString(Assembly, Error, Context); 639 assert(M && "Bad assembly?"); 640 641 auto *F = M->getFunction("f"); 642 assert(F && "Bad assembly?"); 643 644 auto &BB = F->getEntryBlock(); 645 bool ExpectedAnswers[] = { 646 true, // call void @nounwind_readonly(i32* %p) 647 true, // call void @nounwind_argmemonly(i32* %p) 648 false, // call void @throws_but_readonly(i32* %p) 649 false, // call void @throws_but_argmemonly(i32* %p) 650 true, // call void @unknown(i32* %p) nounwind readonly 651 true, // call void @unknown(i32* %p) nounwind argmemonly 652 false, // call void @unknown(i32* %p) readonly 653 false, // call void @unknown(i32* %p) argmemonly 654 true, // call void @nounwind_willreturn(i32* %p) 655 false, // ret void 656 }; 657 658 int Index = 0; 659 for (auto &I : BB) { 660 EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I), 661 ExpectedAnswers[Index]) 662 << "Incorrect answer at instruction " << Index << " = " << I; 663 Index++; 664 } 665 } 666 667 TEST_F(ValueTrackingTest, ComputeNumSignBits_PR32045) { 668 parseAssembly( 669 "define i32 @test(i32 %a) {\n" 670 " %A = ashr i32 %a, -1\n" 671 " ret i32 %A\n" 672 "}\n"); 673 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); 674 } 675 676 // No guarantees for canonical IR in this analysis, so this just bails out. 677 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle) { 678 parseAssembly( 679 "define <2 x i32> @test() {\n" 680 " %A = shufflevector <2 x i32> undef, <2 x i32> undef, <2 x i32> <i32 0, i32 0>\n" 681 " ret <2 x i32> %A\n" 682 "}\n"); 683 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); 684 } 685 686 // No guarantees for canonical IR in this analysis, so a shuffle element that 687 // references an undef value means this can't return any extra information. 688 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) { 689 parseAssembly( 690 "define <2 x i32> @test(<2 x i1> %x) {\n" 691 " %sext = sext <2 x i1> %x to <2 x i32>\n" 692 " %A = shufflevector <2 x i32> %sext, <2 x i32> undef, <2 x i32> <i32 0, i32 2>\n" 693 " ret <2 x i32> %A\n" 694 "}\n"); 695 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); 696 } 697 698 TEST_F(ValueTrackingTest, impliesPoisonTest_Identity) { 699 parseAssembly("define void @test(i32 %x, i32 %y) {\n" 700 " %A = add i32 %x, %y\n" 701 " ret void\n" 702 "}"); 703 EXPECT_TRUE(impliesPoison(A, A)); 704 } 705 706 TEST_F(ValueTrackingTest, impliesPoisonTest_ICmp) { 707 parseAssembly("define void @test(i32 %x) {\n" 708 " %A2 = icmp eq i32 %x, 0\n" 709 " %A = icmp eq i32 %x, 1\n" 710 " ret void\n" 711 "}"); 712 EXPECT_TRUE(impliesPoison(A2, A)); 713 } 714 715 TEST_F(ValueTrackingTest, impliesPoisonTest_ICmpUnknown) { 716 parseAssembly("define void @test(i32 %x, i32 %y) {\n" 717 " %A2 = icmp eq i32 %x, %y\n" 718 " %A = icmp eq i32 %x, 1\n" 719 " ret void\n" 720 "}"); 721 EXPECT_FALSE(impliesPoison(A2, A)); 722 } 723 724 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNswOkay) { 725 parseAssembly("define void @test(i32 %x) {\n" 726 " %A2 = add nsw i32 %x, 1\n" 727 " %A = add i32 %A2, 1\n" 728 " ret void\n" 729 "}"); 730 EXPECT_TRUE(impliesPoison(A2, A)); 731 } 732 733 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNswOkay2) { 734 parseAssembly("define void @test(i32 %x) {\n" 735 " %A2 = add i32 %x, 1\n" 736 " %A = add nsw i32 %A2, 1\n" 737 " ret void\n" 738 "}"); 739 EXPECT_TRUE(impliesPoison(A2, A)); 740 } 741 742 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNsw) { 743 parseAssembly("define void @test(i32 %x) {\n" 744 " %A2 = add nsw i32 %x, 1\n" 745 " %A = add i32 %x, 1\n" 746 " ret void\n" 747 "}"); 748 EXPECT_FALSE(impliesPoison(A2, A)); 749 } 750 751 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle_Pointers) { 752 parseAssembly( 753 "define <2 x i32*> @test(<2 x i32*> %x) {\n" 754 " %A = shufflevector <2 x i32*> zeroinitializer, <2 x i32*> undef, <2 x i32> zeroinitializer\n" 755 " ret <2 x i32*> %A\n" 756 "}\n"); 757 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 64u); 758 } 759 760 TEST(ValueTracking, propagatesPoison) { 761 std::string AsmHead = "declare i32 @g(i32)\n" 762 "define void @f(i32 %x, i32 %y, float %fx, float %fy, " 763 "i1 %cond, i8* %p) {\n"; 764 std::string AsmTail = " ret void\n}"; 765 // (propagates poison?, IR instruction) 766 SmallVector<std::pair<bool, std::string>, 32> Data = { 767 {true, "add i32 %x, %y"}, 768 {true, "add nsw nuw i32 %x, %y"}, 769 {true, "ashr i32 %x, %y"}, 770 {true, "lshr exact i32 %x, 31"}, 771 {true, "fcmp oeq float %fx, %fy"}, 772 {true, "icmp eq i32 %x, %y"}, 773 {true, "getelementptr i8, i8* %p, i32 %x"}, 774 {true, "getelementptr inbounds i8, i8* %p, i32 %x"}, 775 {true, "bitcast float %fx to i32"}, 776 {false, "select i1 %cond, i32 %x, i32 %y"}, 777 {false, "freeze i32 %x"}, 778 {true, "udiv i32 %x, %y"}, 779 {true, "urem i32 %x, %y"}, 780 {true, "sdiv exact i32 %x, %y"}, 781 {true, "srem i32 %x, %y"}, 782 {false, "call i32 @g(i32 %x)"}}; 783 784 std::string AssemblyStr = AsmHead; 785 for (auto &Itm : Data) 786 AssemblyStr += Itm.second + "\n"; 787 AssemblyStr += AsmTail; 788 789 LLVMContext Context; 790 SMDiagnostic Error; 791 auto M = parseAssemblyString(AssemblyStr, Error, Context); 792 assert(M && "Bad assembly?"); 793 794 auto *F = M->getFunction("f"); 795 assert(F && "Bad assembly?"); 796 797 auto &BB = F->getEntryBlock(); 798 799 int Index = 0; 800 for (auto &I : BB) { 801 if (isa<ReturnInst>(&I)) 802 break; 803 EXPECT_EQ(propagatesPoison(cast<Operator>(&I)), Data[Index].first) 804 << "Incorrect answer at instruction " << Index << " = " << I; 805 Index++; 806 } 807 } 808 809 TEST_F(ValueTrackingTest, programUndefinedIfPoison) { 810 parseAssembly("declare i32 @any_num()" 811 "define void @test(i32 %mask) {\n" 812 " %A = call i32 @any_num()\n" 813 " %B = or i32 %A, %mask\n" 814 " udiv i32 1, %B" 815 " ret void\n" 816 "}\n"); 817 // If %A was poison, udiv raises UB regardless of %mask's value 818 EXPECT_EQ(programUndefinedIfPoison(A), true); 819 } 820 821 TEST_F(ValueTrackingTest, programUndefinedIfUndefOrPoison) { 822 parseAssembly("declare i32 @any_num()" 823 "define void @test(i32 %mask) {\n" 824 " %A = call i32 @any_num()\n" 825 " %B = or i32 %A, %mask\n" 826 " udiv i32 1, %B" 827 " ret void\n" 828 "}\n"); 829 // If %A was undef and %mask was 1, udiv does not raise UB 830 EXPECT_EQ(programUndefinedIfUndefOrPoison(A), false); 831 } 832 833 TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_exploitBranchCond) { 834 parseAssembly("declare i1 @any_bool()" 835 "define void @test(i1 %y) {\n" 836 " %A = call i1 @any_bool()\n" 837 " %cond = and i1 %A, %y\n" 838 " br i1 %cond, label %BB1, label %BB2\n" 839 "BB1:\n" 840 " ret void\n" 841 "BB2:\n" 842 " ret void\n" 843 "}\n"); 844 DominatorTree DT(*F); 845 for (auto &BB : *F) { 846 if (&BB == &F->getEntryBlock()) 847 continue; 848 849 EXPECT_EQ(isGuaranteedNotToBePoison(A, nullptr, BB.getTerminator(), &DT), 850 true) 851 << "isGuaranteedNotToBePoison does not hold at " << *BB.getTerminator(); 852 } 853 } 854 855 TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_phi) { 856 parseAssembly("declare i32 @any_i32(i32)" 857 "define void @test() {\n" 858 "ENTRY:\n" 859 " br label %LOOP\n" 860 "LOOP:\n" 861 " %A = phi i32 [0, %ENTRY], [%A.next, %NEXT]\n" 862 " %A.next = call i32 @any_i32(i32 %A)\n" 863 " %cond = icmp eq i32 %A.next, 0\n" 864 " br i1 %cond, label %NEXT, label %EXIT\n" 865 "NEXT:\n" 866 " br label %LOOP\n" 867 "EXIT:\n" 868 " ret void\n" 869 "}\n"); 870 DominatorTree DT(*F); 871 for (auto &BB : *F) { 872 if (BB.getName() == "LOOP") { 873 EXPECT_EQ(isGuaranteedNotToBePoison(A, nullptr, A, &DT), true) 874 << "isGuaranteedNotToBePoison does not hold"; 875 } 876 } 877 } 878 879 TEST_F(ValueTrackingTest, isGuaranteedNotToBeUndefOrPoison) { 880 parseAssembly("declare void @f(i32 noundef)" 881 "define void @test(i32 %x) {\n" 882 " %A = bitcast i32 %x to i32\n" 883 " call void @f(i32 noundef %x)\n" 884 " ret void\n" 885 "}\n"); 886 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(A), true); 887 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(UndefValue::get(IntegerType::get(Context, 8))), false); 888 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(PoisonValue::get(IntegerType::get(Context, 8))), false); 889 EXPECT_EQ(isGuaranteedNotToBePoison(UndefValue::get(IntegerType::get(Context, 8))), true); 890 EXPECT_EQ(isGuaranteedNotToBePoison(PoisonValue::get(IntegerType::get(Context, 8))), false); 891 892 Type *Int32Ty = Type::getInt32Ty(Context); 893 Constant *CU = UndefValue::get(Int32Ty); 894 Constant *CP = PoisonValue::get(Int32Ty); 895 Constant *C1 = ConstantInt::get(Int32Ty, 1); 896 Constant *C2 = ConstantInt::get(Int32Ty, 2); 897 898 { 899 Constant *V1 = ConstantVector::get({C1, C2}); 900 EXPECT_TRUE(isGuaranteedNotToBeUndefOrPoison(V1)); 901 EXPECT_TRUE(isGuaranteedNotToBePoison(V1)); 902 } 903 904 { 905 Constant *V2 = ConstantVector::get({C1, CU}); 906 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(V2)); 907 EXPECT_TRUE(isGuaranteedNotToBePoison(V2)); 908 } 909 910 { 911 Constant *V3 = ConstantVector::get({C1, CP}); 912 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(V3)); 913 EXPECT_FALSE(isGuaranteedNotToBePoison(V3)); 914 } 915 } 916 917 TEST_F(ValueTrackingTest, isGuaranteedNotToBeUndefOrPoison_assume) { 918 parseAssembly("declare i1 @f_i1()\n" 919 "declare i32 @f_i32()\n" 920 "declare void @llvm.assume(i1)\n" 921 "define void @test() {\n" 922 " %A = call i32 @f_i32()\n" 923 " %cond = call i1 @f_i1()\n" 924 " %CxtI = add i32 0, 0\n" 925 " br i1 %cond, label %BB1, label %EXIT\n" 926 "BB1:\n" 927 " %CxtI2 = add i32 0, 0\n" 928 " %cond2 = call i1 @f_i1()\n" 929 " call void @llvm.assume(i1 true) [ \"noundef\"(i32 %A) ]\n" 930 " br i1 %cond2, label %BB2, label %EXIT\n" 931 "BB2:\n" 932 " %CxtI3 = add i32 0, 0\n" 933 " ret void\n" 934 "EXIT:\n" 935 " ret void\n" 936 "}"); 937 AssumptionCache AC(*F); 938 DominatorTree DT(*F); 939 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI, &DT)); 940 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI2, &DT)); 941 EXPECT_TRUE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI3, &DT)); 942 } 943 944 TEST(ValueTracking, canCreatePoisonOrUndef) { 945 std::string AsmHead = 946 "@s = external dso_local global i32, align 1\n" 947 "declare i32 @g(i32)\n" 948 "define void @f(i32 %x, i32 %y, float %fx, float %fy, i1 %cond, " 949 "<4 x i32> %vx, <4 x i32> %vx2, <vscale x 4 x i32> %svx, i8* %p) {\n"; 950 std::string AsmTail = " ret void\n}"; 951 // (can create poison?, can create undef?, IR instruction) 952 SmallVector<std::pair<std::pair<bool, bool>, std::string>, 32> Data = { 953 {{false, false}, "add i32 %x, %y"}, 954 {{true, false}, "add nsw nuw i32 %x, %y"}, 955 {{true, false}, "shl i32 %x, %y"}, 956 {{true, false}, "shl <4 x i32> %vx, %vx2"}, 957 {{true, false}, "shl nsw i32 %x, %y"}, 958 {{true, false}, "shl nsw <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"}, 959 {{false, false}, "shl i32 %x, 31"}, 960 {{true, false}, "shl i32 %x, 32"}, 961 {{false, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"}, 962 {{true, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"}, 963 {{true, false}, "ashr i32 %x, %y"}, 964 {{true, false}, "ashr exact i32 %x, %y"}, 965 {{false, false}, "ashr i32 %x, 31"}, 966 {{true, false}, "ashr exact i32 %x, 31"}, 967 {{false, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"}, 968 {{true, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"}, 969 {{true, false}, "ashr exact <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"}, 970 {{true, false}, "lshr i32 %x, %y"}, 971 {{true, false}, "lshr exact i32 %x, 31"}, 972 {{false, false}, "udiv i32 %x, %y"}, 973 {{true, false}, "udiv exact i32 %x, %y"}, 974 {{false, false}, "getelementptr i8, i8* %p, i32 %x"}, 975 {{true, false}, "getelementptr inbounds i8, i8* %p, i32 %x"}, 976 {{true, false}, "fneg nnan float %fx"}, 977 {{false, false}, "fneg float %fx"}, 978 {{false, false}, "fadd float %fx, %fy"}, 979 {{true, false}, "fadd nnan float %fx, %fy"}, 980 {{false, false}, "urem i32 %x, %y"}, 981 {{true, false}, "fptoui float %fx to i32"}, 982 {{true, false}, "fptosi float %fx to i32"}, 983 {{false, false}, "bitcast float %fx to i32"}, 984 {{false, false}, "select i1 %cond, i32 %x, i32 %y"}, 985 {{true, false}, "select nnan i1 %cond, float %fx, float %fy"}, 986 {{true, false}, "extractelement <4 x i32> %vx, i32 %x"}, 987 {{false, false}, "extractelement <4 x i32> %vx, i32 3"}, 988 {{true, false}, "extractelement <vscale x 4 x i32> %svx, i32 4"}, 989 {{true, false}, "insertelement <4 x i32> %vx, i32 %x, i32 %y"}, 990 {{false, false}, "insertelement <4 x i32> %vx, i32 %x, i32 3"}, 991 {{true, false}, "insertelement <vscale x 4 x i32> %svx, i32 %x, i32 4"}, 992 {{false, false}, "freeze i32 %x"}, 993 {{false, false}, 994 "shufflevector <4 x i32> %vx, <4 x i32> %vx2, " 995 "<4 x i32> <i32 0, i32 1, i32 2, i32 3>"}, 996 {{false, true}, 997 "shufflevector <4 x i32> %vx, <4 x i32> %vx2, " 998 "<4 x i32> <i32 0, i32 1, i32 2, i32 undef>"}, 999 {{false, true}, 1000 "shufflevector <vscale x 4 x i32> %svx, " 1001 "<vscale x 4 x i32> %svx, <vscale x 4 x i32> undef"}, 1002 {{true, false}, "call i32 @g(i32 %x)"}, 1003 {{false, false}, "call noundef i32 @g(i32 %x)"}, 1004 {{true, false}, "fcmp nnan oeq float %fx, %fy"}, 1005 {{false, false}, "fcmp oeq float %fx, %fy"}, 1006 {{true, false}, 1007 "ashr <4 x i32> %vx, select (i1 icmp sgt (i32 ptrtoint (i32* @s to " 1008 "i32), i32 1), <4 x i32> zeroinitializer, <4 x i32> <i32 0, i32 1, i32 " 1009 "2, i32 3>)"}}; 1010 1011 std::string AssemblyStr = AsmHead; 1012 for (auto &Itm : Data) 1013 AssemblyStr += Itm.second + "\n"; 1014 AssemblyStr += AsmTail; 1015 1016 LLVMContext Context; 1017 SMDiagnostic Error; 1018 auto M = parseAssemblyString(AssemblyStr, Error, Context); 1019 assert(M && "Bad assembly?"); 1020 1021 auto *F = M->getFunction("f"); 1022 assert(F && "Bad assembly?"); 1023 1024 auto &BB = F->getEntryBlock(); 1025 1026 int Index = 0; 1027 for (auto &I : BB) { 1028 if (isa<ReturnInst>(&I)) 1029 break; 1030 bool Poison = Data[Index].first.first; 1031 bool Undef = Data[Index].first.second; 1032 EXPECT_EQ(canCreatePoison(cast<Operator>(&I)), Poison) 1033 << "Incorrect answer of canCreatePoison at instruction " << Index 1034 << " = " << I; 1035 EXPECT_EQ(canCreateUndefOrPoison(cast<Operator>(&I)), Undef || Poison) 1036 << "Incorrect answer of canCreateUndef at instruction " << Index 1037 << " = " << I; 1038 Index++; 1039 } 1040 } 1041 1042 TEST_F(ValueTrackingTest, computePtrAlignment) { 1043 parseAssembly("declare i1 @f_i1()\n" 1044 "declare i8* @f_i8p()\n" 1045 "declare void @llvm.assume(i1)\n" 1046 "define void @test() {\n" 1047 " %A = call i8* @f_i8p()\n" 1048 " %cond = call i1 @f_i1()\n" 1049 " %CxtI = add i32 0, 0\n" 1050 " br i1 %cond, label %BB1, label %EXIT\n" 1051 "BB1:\n" 1052 " %CxtI2 = add i32 0, 0\n" 1053 " %cond2 = call i1 @f_i1()\n" 1054 " call void @llvm.assume(i1 true) [ \"align\"(i8* %A, i64 16) ]\n" 1055 " br i1 %cond2, label %BB2, label %EXIT\n" 1056 "BB2:\n" 1057 " %CxtI3 = add i32 0, 0\n" 1058 " ret void\n" 1059 "EXIT:\n" 1060 " ret void\n" 1061 "}"); 1062 AssumptionCache AC(*F); 1063 DominatorTree DT(*F); 1064 DataLayout DL = M->getDataLayout(); 1065 EXPECT_EQ(getKnownAlignment(A, DL, CxtI, &AC, &DT), Align(1)); 1066 EXPECT_EQ(getKnownAlignment(A, DL, CxtI2, &AC, &DT), Align(1)); 1067 EXPECT_EQ(getKnownAlignment(A, DL, CxtI3, &AC, &DT), Align(16)); 1068 } 1069 1070 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) { 1071 parseAssembly( 1072 "define i32 @test(i32 %a, i32 %b) {\n" 1073 " %ash = mul i32 %a, 8\n" 1074 " %aad = add i32 %ash, 7\n" 1075 " %aan = and i32 %aad, 4095\n" 1076 " %bsh = shl i32 %b, 4\n" 1077 " %bad = or i32 %bsh, 6\n" 1078 " %ban = and i32 %bad, 4095\n" 1079 " %A = mul i32 %aan, %ban\n" 1080 " ret i32 %A\n" 1081 "}\n"); 1082 expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u); 1083 } 1084 1085 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) { 1086 parseAssembly( 1087 "define i32 @test(i32 %a, i32 %b) {\n" 1088 " %aa = shl i32 %a, 5\n" 1089 " %bb = shl i32 %b, 5\n" 1090 " %aaa = or i32 %aa, 24\n" 1091 " %bbb = or i32 %bb, 28\n" 1092 " %A = mul i32 %aaa, %bbb\n" 1093 " ret i32 %A\n" 1094 "}\n"); 1095 expectKnownBits(/*zero*/ 95u, /*one*/ 32u); 1096 } 1097 1098 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond) { 1099 parseAssembly(R"( 1100 declare i8* @f_i8() 1101 define void @test(i1 %c) { 1102 %A = call i8* @f_i8() 1103 %B = call i8* @f_i8() 1104 %c1 = icmp ne i8* %A, null 1105 %cond = and i1 %c1, %c 1106 br i1 %cond, label %T, label %Q 1107 T: 1108 %CxtI = add i32 0, 0 1109 ret void 1110 Q: 1111 %CxtI2 = add i32 0, 0 1112 ret void 1113 } 1114 )"); 1115 AssumptionCache AC(*F); 1116 DominatorTree DT(*F); 1117 DataLayout DL = M->getDataLayout(); 1118 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true); 1119 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false); 1120 } 1121 1122 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond2) { 1123 parseAssembly(R"( 1124 declare i8* @f_i8() 1125 define void @test(i1 %c) { 1126 %A = call i8* @f_i8() 1127 %B = call i8* @f_i8() 1128 %c1 = icmp ne i8* %A, null 1129 %cond = select i1 %c, i1 %c1, i1 false 1130 br i1 %cond, label %T, label %Q 1131 T: 1132 %CxtI = add i32 0, 0 1133 ret void 1134 Q: 1135 %CxtI2 = add i32 0, 0 1136 ret void 1137 } 1138 )"); 1139 AssumptionCache AC(*F); 1140 DominatorTree DT(*F); 1141 DataLayout DL = M->getDataLayout(); 1142 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true); 1143 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false); 1144 } 1145 1146 TEST_F(ValueTrackingTest, IsImpliedConditionAnd) { 1147 parseAssembly(R"( 1148 define void @test(i32 %x, i32 %y) { 1149 %c1 = icmp ult i32 %x, 10 1150 %c2 = icmp ult i32 %y, 15 1151 %A = and i1 %c1, %c2 1152 ; x < 10 /\ y < 15 1153 %A2 = icmp ult i32 %x, 20 1154 %A3 = icmp uge i32 %y, 20 1155 %A4 = icmp ult i32 %x, 5 1156 ret void 1157 } 1158 )"); 1159 DataLayout DL = M->getDataLayout(); 1160 EXPECT_EQ(isImpliedCondition(A, A2, DL), true); 1161 EXPECT_EQ(isImpliedCondition(A, A3, DL), false); 1162 EXPECT_EQ(isImpliedCondition(A, A4, DL), None); 1163 } 1164 1165 TEST_F(ValueTrackingTest, IsImpliedConditionAnd2) { 1166 parseAssembly(R"( 1167 define void @test(i32 %x, i32 %y) { 1168 %c1 = icmp ult i32 %x, 10 1169 %c2 = icmp ult i32 %y, 15 1170 %A = select i1 %c1, i1 %c2, i1 false 1171 ; x < 10 /\ y < 15 1172 %A2 = icmp ult i32 %x, 20 1173 %A3 = icmp uge i32 %y, 20 1174 %A4 = icmp ult i32 %x, 5 1175 ret void 1176 } 1177 )"); 1178 DataLayout DL = M->getDataLayout(); 1179 EXPECT_EQ(isImpliedCondition(A, A2, DL), true); 1180 EXPECT_EQ(isImpliedCondition(A, A3, DL), false); 1181 EXPECT_EQ(isImpliedCondition(A, A4, DL), None); 1182 } 1183 1184 TEST_F(ValueTrackingTest, IsImpliedConditionOr) { 1185 parseAssembly(R"( 1186 define void @test(i32 %x, i32 %y) { 1187 %c1 = icmp ult i32 %x, 10 1188 %c2 = icmp ult i32 %y, 15 1189 %A = or i1 %c1, %c2 ; negated 1190 ; x >= 10 /\ y >= 15 1191 %A2 = icmp ult i32 %x, 5 1192 %A3 = icmp uge i32 %y, 10 1193 %A4 = icmp ult i32 %x, 15 1194 ret void 1195 } 1196 )"); 1197 DataLayout DL = M->getDataLayout(); 1198 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false); 1199 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true); 1200 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), None); 1201 } 1202 1203 TEST_F(ValueTrackingTest, IsImpliedConditionOr2) { 1204 parseAssembly(R"( 1205 define void @test(i32 %x, i32 %y) { 1206 %c1 = icmp ult i32 %x, 10 1207 %c2 = icmp ult i32 %y, 15 1208 %A = select i1 %c1, i1 true, i1 %c2 ; negated 1209 ; x >= 10 /\ y >= 15 1210 %A2 = icmp ult i32 %x, 5 1211 %A3 = icmp uge i32 %y, 10 1212 %A4 = icmp ult i32 %x, 15 1213 ret void 1214 } 1215 )"); 1216 DataLayout DL = M->getDataLayout(); 1217 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false); 1218 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true); 1219 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), None); 1220 } 1221 1222 TEST_F(ComputeKnownBitsTest, KnownNonZeroShift) { 1223 // %q is known nonzero without known bits. 1224 // Because %q is nonzero, %A[0] is known to be zero. 1225 parseAssembly( 1226 "define i8 @test(i8 %p, i8* %pq) {\n" 1227 " %q = load i8, i8* %pq, !range !0\n" 1228 " %A = shl i8 %p, %q\n" 1229 " ret i8 %A\n" 1230 "}\n" 1231 "!0 = !{ i8 1, i8 5 }\n"); 1232 expectKnownBits(/*zero*/ 1u, /*one*/ 0u); 1233 } 1234 1235 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) { 1236 // fshl(....1111....0000, 00..1111........, 6) 1237 // = 11....000000..11 1238 parseAssembly( 1239 "define i16 @test(i16 %a, i16 %b) {\n" 1240 " %aa = shl i16 %a, 4\n" 1241 " %bb = lshr i16 %b, 2\n" 1242 " %aaa = or i16 %aa, 3840\n" 1243 " %bbb = or i16 %bb, 3840\n" 1244 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n" 1245 " ret i16 %A\n" 1246 "}\n" 1247 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n"); 1248 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u); 1249 } 1250 1251 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) { 1252 // fshr(....1111....0000, 00..1111........, 26) 1253 // = 11....000000..11 1254 parseAssembly( 1255 "define i16 @test(i16 %a, i16 %b) {\n" 1256 " %aa = shl i16 %a, 4\n" 1257 " %bb = lshr i16 %b, 2\n" 1258 " %aaa = or i16 %aa, 3840\n" 1259 " %bbb = or i16 %bb, 3840\n" 1260 " %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n" 1261 " ret i16 %A\n" 1262 "}\n" 1263 "declare i16 @llvm.fshr.i16(i16, i16, i16)\n"); 1264 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u); 1265 } 1266 1267 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) { 1268 // fshl(....1111....0000, 00..1111........, 0) 1269 // = ....1111....0000 1270 parseAssembly( 1271 "define i16 @test(i16 %a, i16 %b) {\n" 1272 " %aa = shl i16 %a, 4\n" 1273 " %bb = lshr i16 %b, 2\n" 1274 " %aaa = or i16 %aa, 3840\n" 1275 " %bbb = or i16 %bb, 3840\n" 1276 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n" 1277 " ret i16 %A\n" 1278 "}\n" 1279 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n"); 1280 expectKnownBits(/*zero*/ 15u, /*one*/ 3840u); 1281 } 1282 1283 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) { 1284 // uadd.sat(1111...1, ........) 1285 // = 1111.... 1286 parseAssembly( 1287 "define i8 @test(i8 %a, i8 %b) {\n" 1288 " %aa = or i8 %a, 241\n" 1289 " %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n" 1290 " ret i8 %A\n" 1291 "}\n" 1292 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n"); 1293 expectKnownBits(/*zero*/ 0u, /*one*/ 240u); 1294 } 1295 1296 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) { 1297 // uadd.sat(00...011, .1...110) 1298 // = .......1 1299 parseAssembly( 1300 "define i8 @test(i8 %a, i8 %b) {\n" 1301 " %aa = or i8 %a, 3\n" 1302 " %aaa = and i8 %aa, 59\n" 1303 " %bb = or i8 %b, 70\n" 1304 " %bbb = and i8 %bb, 254\n" 1305 " %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n" 1306 " ret i8 %A\n" 1307 "}\n" 1308 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n"); 1309 expectKnownBits(/*zero*/ 0u, /*one*/ 1u); 1310 } 1311 1312 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) { 1313 // usub.sat(0000...0, ........) 1314 // = 0000.... 1315 parseAssembly( 1316 "define i8 @test(i8 %a, i8 %b) {\n" 1317 " %aa = and i8 %a, 14\n" 1318 " %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n" 1319 " ret i8 %A\n" 1320 "}\n" 1321 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 1322 expectKnownBits(/*zero*/ 240u, /*one*/ 0u); 1323 } 1324 1325 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) { 1326 // usub.sat(........, 1111...1) 1327 // = 0000.... 1328 parseAssembly( 1329 "define i8 @test(i8 %a, i8 %b) {\n" 1330 " %bb = or i8 %a, 241\n" 1331 " %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n" 1332 " ret i8 %A\n" 1333 "}\n" 1334 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 1335 expectKnownBits(/*zero*/ 240u, /*one*/ 0u); 1336 } 1337 1338 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) { 1339 // usub.sat(11...011, .1...110) 1340 // = ......0. 1341 parseAssembly( 1342 "define i8 @test(i8 %a, i8 %b) {\n" 1343 " %aa = or i8 %a, 195\n" 1344 " %aaa = and i8 %aa, 251\n" 1345 " %bb = or i8 %b, 70\n" 1346 " %bbb = and i8 %bb, 254\n" 1347 " %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n" 1348 " ret i8 %A\n" 1349 "}\n" 1350 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 1351 expectKnownBits(/*zero*/ 2u, /*one*/ 0u); 1352 } 1353 1354 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntTrunc) { 1355 // ptrtoint truncates the pointer type. 1356 parseAssembly( 1357 "define void @test(i8** %p) {\n" 1358 " %A = load i8*, i8** %p\n" 1359 " %i = ptrtoint i8* %A to i32\n" 1360 " %m = and i32 %i, 31\n" 1361 " %c = icmp eq i32 %m, 0\n" 1362 " call void @llvm.assume(i1 %c)\n" 1363 " ret void\n" 1364 "}\n" 1365 "declare void @llvm.assume(i1)\n"); 1366 AssumptionCache AC(*F); 1367 KnownBits Known = computeKnownBits( 1368 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator()); 1369 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 1370 EXPECT_EQ(Known.One.getZExtValue(), 0u); 1371 } 1372 1373 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntZext) { 1374 // ptrtoint zero extends the pointer type. 1375 parseAssembly( 1376 "define void @test(i8** %p) {\n" 1377 " %A = load i8*, i8** %p\n" 1378 " %i = ptrtoint i8* %A to i128\n" 1379 " %m = and i128 %i, 31\n" 1380 " %c = icmp eq i128 %m, 0\n" 1381 " call void @llvm.assume(i1 %c)\n" 1382 " ret void\n" 1383 "}\n" 1384 "declare void @llvm.assume(i1)\n"); 1385 AssumptionCache AC(*F); 1386 KnownBits Known = computeKnownBits( 1387 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator()); 1388 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 1389 EXPECT_EQ(Known.One.getZExtValue(), 0u); 1390 } 1391 1392 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsFreeze) { 1393 parseAssembly("define void @test() {\n" 1394 " %m = call i32 @any_num()\n" 1395 " %A = freeze i32 %m\n" 1396 " %n = and i32 %m, 31\n" 1397 " %c = icmp eq i32 %n, 0\n" 1398 " call void @llvm.assume(i1 %c)\n" 1399 " ret void\n" 1400 "}\n" 1401 "declare void @llvm.assume(i1)\n" 1402 "declare i32 @any_num()\n"); 1403 AssumptionCache AC(*F); 1404 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 1405 F->front().getTerminator()); 1406 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 1407 EXPECT_EQ(Known.One.getZExtValue(), 0u); 1408 } 1409 1410 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRange) { 1411 parseAssembly("define void @test(i64* %p) {\n" 1412 " %A = load i64, i64* %p, !range !{i64 64, i64 65536}\n" 1413 " %APlus512 = add i64 %A, 512\n" 1414 " %c = icmp ugt i64 %APlus512, 523\n" 1415 " call void @llvm.assume(i1 %c)\n" 1416 " ret void\n" 1417 "}\n" 1418 "declare void @llvm.assume(i1)\n"); 1419 AssumptionCache AC(*F); 1420 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 1421 F->front().getTerminator()); 1422 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1)); 1423 EXPECT_EQ(Known.One.getZExtValue(), 0u); 1424 Instruction &APlus512 = findInstructionByName(F, "APlus512"); 1425 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC, 1426 F->front().getTerminator()); 1427 // We know of one less zero because 512 may have produced a 1 that 1428 // got carried all the way to the first trailing zero. 1429 EXPECT_EQ(Known.Zero.getZExtValue(), (~(65536llu - 1)) << 1); 1430 EXPECT_EQ(Known.One.getZExtValue(), 0u); 1431 // The known range is not precise given computeKnownBits works 1432 // with the masks of zeros and ones, not the ranges. 1433 EXPECT_EQ(Known.getMinValue(), 0u); 1434 EXPECT_EQ(Known.getMaxValue(), 131071); 1435 } 1436 1437 // 512 + [32, 64) doesn't produce overlapping bits. 1438 // Make sure we get all the individual bits properly. 1439 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRangeNoOverlap) { 1440 parseAssembly("define void @test(i64* %p) {\n" 1441 " %A = load i64, i64* %p, !range !{i64 32, i64 64}\n" 1442 " %APlus512 = add i64 %A, 512\n" 1443 " %c = icmp ugt i64 %APlus512, 523\n" 1444 " call void @llvm.assume(i1 %c)\n" 1445 " ret void\n" 1446 "}\n" 1447 "declare void @llvm.assume(i1)\n"); 1448 AssumptionCache AC(*F); 1449 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 1450 F->front().getTerminator()); 1451 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1)); 1452 EXPECT_EQ(Known.One.getZExtValue(), 32u); 1453 Instruction &APlus512 = findInstructionByName(F, "APlus512"); 1454 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC, 1455 F->front().getTerminator()); 1456 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1)); 1457 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u); 1458 // The known range is not precise given computeKnownBits works 1459 // with the masks of zeros and ones, not the ranges. 1460 EXPECT_EQ(Known.getMinValue(), 544); 1461 EXPECT_EQ(Known.getMaxValue(), 575); 1462 } 1463 1464 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRange) { 1465 parseAssembly( 1466 "define void @test(i64* %p) {\n" 1467 " %A = load i64, i64* %p, !range !{i64 64, i64 65536}\n" 1468 " %APtr = inttoptr i64 %A to float*" 1469 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n" 1470 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n" 1471 " call void @llvm.assume(i1 %c)\n" 1472 " ret void\n" 1473 "}\n" 1474 "declare void @llvm.assume(i1)\n"); 1475 AssumptionCache AC(*F); 1476 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 1477 F->front().getTerminator()); 1478 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1)); 1479 EXPECT_EQ(Known.One.getZExtValue(), 0u); 1480 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512"); 1481 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC, 1482 F->front().getTerminator()); 1483 // We know of one less zero because 512 may have produced a 1 that 1484 // got carried all the way to the first trailing zero. 1485 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1) << 1); 1486 EXPECT_EQ(Known.One.getZExtValue(), 0u); 1487 // The known range is not precise given computeKnownBits works 1488 // with the masks of zeros and ones, not the ranges. 1489 EXPECT_EQ(Known.getMinValue(), 0u); 1490 EXPECT_EQ(Known.getMaxValue(), 131071); 1491 } 1492 1493 // 4*128 + [32, 64) doesn't produce overlapping bits. 1494 // Make sure we get all the individual bits properly. 1495 // This test is useful to check that we account for the scaling factor 1496 // in the gep. Indeed, gep float, [32,64), 128 is not 128 + [32,64). 1497 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRangeNoOverlap) { 1498 parseAssembly( 1499 "define void @test(i64* %p) {\n" 1500 " %A = load i64, i64* %p, !range !{i64 32, i64 64}\n" 1501 " %APtr = inttoptr i64 %A to float*" 1502 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n" 1503 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n" 1504 " call void @llvm.assume(i1 %c)\n" 1505 " ret void\n" 1506 "}\n" 1507 "declare void @llvm.assume(i1)\n"); 1508 AssumptionCache AC(*F); 1509 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 1510 F->front().getTerminator()); 1511 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1)); 1512 EXPECT_EQ(Known.One.getZExtValue(), 32u); 1513 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512"); 1514 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC, 1515 F->front().getTerminator()); 1516 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1)); 1517 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u); 1518 // The known range is not precise given computeKnownBits works 1519 // with the masks of zeros and ones, not the ranges. 1520 EXPECT_EQ(Known.getMinValue(), 544); 1521 EXPECT_EQ(Known.getMaxValue(), 575); 1522 } 1523 1524 class IsBytewiseValueTest : public ValueTrackingTest, 1525 public ::testing::WithParamInterface< 1526 std::pair<const char *, const char *>> { 1527 protected: 1528 }; 1529 1530 const std::pair<const char *, const char *> IsBytewiseValueTests[] = { 1531 { 1532 "i8 0", 1533 "i48* null", 1534 }, 1535 { 1536 "i8 undef", 1537 "i48* undef", 1538 }, 1539 { 1540 "i8 0", 1541 "i8 zeroinitializer", 1542 }, 1543 { 1544 "i8 0", 1545 "i8 0", 1546 }, 1547 { 1548 "i8 -86", 1549 "i8 -86", 1550 }, 1551 { 1552 "i8 -1", 1553 "i8 -1", 1554 }, 1555 { 1556 "i8 undef", 1557 "i16 undef", 1558 }, 1559 { 1560 "i8 0", 1561 "i16 0", 1562 }, 1563 { 1564 "", 1565 "i16 7", 1566 }, 1567 { 1568 "i8 -86", 1569 "i16 -21846", 1570 }, 1571 { 1572 "i8 -1", 1573 "i16 -1", 1574 }, 1575 { 1576 "i8 0", 1577 "i48 0", 1578 }, 1579 { 1580 "i8 -1", 1581 "i48 -1", 1582 }, 1583 { 1584 "i8 0", 1585 "i49 0", 1586 }, 1587 { 1588 "", 1589 "i49 -1", 1590 }, 1591 { 1592 "i8 0", 1593 "half 0xH0000", 1594 }, 1595 { 1596 "i8 -85", 1597 "half 0xHABAB", 1598 }, 1599 { 1600 "i8 0", 1601 "float 0.0", 1602 }, 1603 { 1604 "i8 -1", 1605 "float 0xFFFFFFFFE0000000", 1606 }, 1607 { 1608 "i8 0", 1609 "double 0.0", 1610 }, 1611 { 1612 "i8 -15", 1613 "double 0xF1F1F1F1F1F1F1F1", 1614 }, 1615 { 1616 "i8 undef", 1617 "i16* undef", 1618 }, 1619 { 1620 "i8 0", 1621 "i16* inttoptr (i64 0 to i16*)", 1622 }, 1623 { 1624 "i8 -1", 1625 "i16* inttoptr (i64 -1 to i16*)", 1626 }, 1627 { 1628 "i8 -86", 1629 "i16* inttoptr (i64 -6148914691236517206 to i16*)", 1630 }, 1631 { 1632 "", 1633 "i16* inttoptr (i48 -1 to i16*)", 1634 }, 1635 { 1636 "i8 -1", 1637 "i16* inttoptr (i96 -1 to i16*)", 1638 }, 1639 { 1640 "i8 undef", 1641 "[0 x i8] zeroinitializer", 1642 }, 1643 { 1644 "i8 undef", 1645 "[0 x i8] undef", 1646 }, 1647 { 1648 "i8 undef", 1649 "[5 x [0 x i8]] zeroinitializer", 1650 }, 1651 { 1652 "i8 undef", 1653 "[5 x [0 x i8]] undef", 1654 }, 1655 { 1656 "i8 0", 1657 "[6 x i8] zeroinitializer", 1658 }, 1659 { 1660 "i8 undef", 1661 "[6 x i8] undef", 1662 }, 1663 { 1664 "i8 1", 1665 "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]", 1666 }, 1667 { 1668 "", 1669 "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]", 1670 }, 1671 { 1672 "i8 -1", 1673 "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]", 1674 }, 1675 { 1676 "", 1677 "[4 x i8] [i8 1, i8 2, i8 1, i8 1]", 1678 }, 1679 { 1680 "i8 1", 1681 "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]", 1682 }, 1683 { 1684 "i8 0", 1685 "<6 x i8> zeroinitializer", 1686 }, 1687 { 1688 "i8 undef", 1689 "<6 x i8> undef", 1690 }, 1691 { 1692 "i8 1", 1693 "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>", 1694 }, 1695 { 1696 "", 1697 "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>", 1698 }, 1699 { 1700 "i8 -1", 1701 "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>", 1702 }, 1703 { 1704 "", 1705 "<4 x i8> <i8 1, i8 1, i8 2, i8 1>", 1706 }, 1707 { 1708 "i8 5", 1709 "<2 x i8> < i8 5, i8 undef >", 1710 }, 1711 { 1712 "i8 0", 1713 "[2 x [2 x i16]] zeroinitializer", 1714 }, 1715 { 1716 "i8 undef", 1717 "[2 x [2 x i16]] undef", 1718 }, 1719 { 1720 "i8 -86", 1721 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], " 1722 "[2 x i16] [i16 -21846, i16 -21846]]", 1723 }, 1724 { 1725 "", 1726 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], " 1727 "[2 x i16] [i16 -21836, i16 -21846]]", 1728 }, 1729 { 1730 "i8 undef", 1731 "{ } zeroinitializer", 1732 }, 1733 { 1734 "i8 undef", 1735 "{ } undef", 1736 }, 1737 { 1738 "i8 undef", 1739 "{ {}, {} } zeroinitializer", 1740 }, 1741 { 1742 "i8 undef", 1743 "{ {}, {} } undef", 1744 }, 1745 { 1746 "i8 0", 1747 "{i8, i64, i16*} zeroinitializer", 1748 }, 1749 { 1750 "i8 undef", 1751 "{i8, i64, i16*} undef", 1752 }, 1753 { 1754 "i8 -86", 1755 "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}", 1756 }, 1757 { 1758 "", 1759 "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}", 1760 }, 1761 }; 1762 1763 INSTANTIATE_TEST_CASE_P(IsBytewiseValueParamTests, IsBytewiseValueTest, 1764 ::testing::ValuesIn(IsBytewiseValueTests),); 1765 1766 TEST_P(IsBytewiseValueTest, IsBytewiseValue) { 1767 auto M = parseModule(std::string("@test = global ") + GetParam().second); 1768 GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test")); 1769 Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout()); 1770 std::string Buff; 1771 raw_string_ostream S(Buff); 1772 if (Actual) 1773 S << *Actual; 1774 EXPECT_EQ(GetParam().first, S.str()); 1775 } 1776 1777 TEST_F(ValueTrackingTest, ComputeConstantRange) { 1778 { 1779 // Assumptions: 1780 // * stride >= 5 1781 // * stride < 10 1782 // 1783 // stride = [5, 10) 1784 auto M = parseModule(R"( 1785 declare void @llvm.assume(i1) 1786 1787 define i32 @test(i32 %stride) { 1788 %gt = icmp uge i32 %stride, 5 1789 call void @llvm.assume(i1 %gt) 1790 %lt = icmp ult i32 %stride, 10 1791 call void @llvm.assume(i1 %lt) 1792 %stride.plus.one = add nsw nuw i32 %stride, 1 1793 ret i32 %stride.plus.one 1794 })"); 1795 Function *F = M->getFunction("test"); 1796 1797 AssumptionCache AC(*F); 1798 Value *Stride = &*F->arg_begin(); 1799 ConstantRange CR1 = computeConstantRange(Stride, true, &AC, nullptr); 1800 EXPECT_TRUE(CR1.isFullSet()); 1801 1802 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 1803 ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I); 1804 EXPECT_EQ(5, CR2.getLower()); 1805 EXPECT_EQ(10, CR2.getUpper()); 1806 } 1807 1808 { 1809 // Assumptions: 1810 // * stride >= 5 1811 // * stride < 200 1812 // * stride == 99 1813 // 1814 // stride = [99, 100) 1815 auto M = parseModule(R"( 1816 declare void @llvm.assume(i1) 1817 1818 define i32 @test(i32 %stride) { 1819 %gt = icmp uge i32 %stride, 5 1820 call void @llvm.assume(i1 %gt) 1821 %lt = icmp ult i32 %stride, 200 1822 call void @llvm.assume(i1 %lt) 1823 %eq = icmp eq i32 %stride, 99 1824 call void @llvm.assume(i1 %eq) 1825 %stride.plus.one = add nsw nuw i32 %stride, 1 1826 ret i32 %stride.plus.one 1827 })"); 1828 Function *F = M->getFunction("test"); 1829 1830 AssumptionCache AC(*F); 1831 Value *Stride = &*F->arg_begin(); 1832 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 1833 ConstantRange CR = computeConstantRange(Stride, true, &AC, I); 1834 EXPECT_EQ(99, *CR.getSingleElement()); 1835 } 1836 1837 { 1838 // Assumptions: 1839 // * stride >= 5 1840 // * stride >= 50 1841 // * stride < 100 1842 // * stride < 200 1843 // 1844 // stride = [50, 100) 1845 auto M = parseModule(R"( 1846 declare void @llvm.assume(i1) 1847 1848 define i32 @test(i32 %stride, i1 %cond) { 1849 %gt = icmp uge i32 %stride, 5 1850 call void @llvm.assume(i1 %gt) 1851 %gt.2 = icmp uge i32 %stride, 50 1852 call void @llvm.assume(i1 %gt.2) 1853 br i1 %cond, label %bb1, label %bb2 1854 1855 bb1: 1856 %lt = icmp ult i32 %stride, 200 1857 call void @llvm.assume(i1 %lt) 1858 %lt.2 = icmp ult i32 %stride, 100 1859 call void @llvm.assume(i1 %lt.2) 1860 %stride.plus.one = add nsw nuw i32 %stride, 1 1861 ret i32 %stride.plus.one 1862 1863 bb2: 1864 ret i32 0 1865 })"); 1866 Function *F = M->getFunction("test"); 1867 1868 AssumptionCache AC(*F); 1869 Value *Stride = &*F->arg_begin(); 1870 Instruction *GT2 = &findInstructionByName(F, "gt.2"); 1871 ConstantRange CR = computeConstantRange(Stride, true, &AC, GT2); 1872 EXPECT_EQ(5, CR.getLower()); 1873 EXPECT_EQ(0, CR.getUpper()); 1874 1875 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 1876 ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I); 1877 EXPECT_EQ(50, CR2.getLower()); 1878 EXPECT_EQ(100, CR2.getUpper()); 1879 } 1880 1881 { 1882 // Assumptions: 1883 // * stride > 5 1884 // * stride < 5 1885 // 1886 // stride = empty range, as the assumptions contradict each other. 1887 auto M = parseModule(R"( 1888 declare void @llvm.assume(i1) 1889 1890 define i32 @test(i32 %stride, i1 %cond) { 1891 %gt = icmp ugt i32 %stride, 5 1892 call void @llvm.assume(i1 %gt) 1893 %lt = icmp ult i32 %stride, 5 1894 call void @llvm.assume(i1 %lt) 1895 %stride.plus.one = add nsw nuw i32 %stride, 1 1896 ret i32 %stride.plus.one 1897 })"); 1898 Function *F = M->getFunction("test"); 1899 1900 AssumptionCache AC(*F); 1901 Value *Stride = &*F->arg_begin(); 1902 1903 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 1904 ConstantRange CR = computeConstantRange(Stride, true, &AC, I); 1905 EXPECT_TRUE(CR.isEmptySet()); 1906 } 1907 1908 { 1909 // Assumptions: 1910 // * x.1 >= 5 1911 // * x.2 < x.1 1912 // 1913 // stride = [0, 5) 1914 auto M = parseModule(R"( 1915 declare void @llvm.assume(i1) 1916 1917 define i32 @test(i32 %x.1, i32 %x.2) { 1918 %gt = icmp uge i32 %x.1, 5 1919 call void @llvm.assume(i1 %gt) 1920 %lt = icmp ult i32 %x.2, %x.1 1921 call void @llvm.assume(i1 %lt) 1922 %stride.plus.one = add nsw nuw i32 %x.1, 1 1923 ret i32 %stride.plus.one 1924 })"); 1925 Function *F = M->getFunction("test"); 1926 1927 AssumptionCache AC(*F); 1928 Value *X2 = &*std::next(F->arg_begin()); 1929 1930 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 1931 ConstantRange CR1 = computeConstantRange(X2, true, &AC, I); 1932 EXPECT_EQ(0, CR1.getLower()); 1933 EXPECT_EQ(5, CR1.getUpper()); 1934 1935 // Check the depth cutoff results in a conservative result (full set) by 1936 // passing Depth == MaxDepth == 6. 1937 ConstantRange CR2 = computeConstantRange(X2, true, &AC, I, 6); 1938 EXPECT_TRUE(CR2.isFullSet()); 1939 } 1940 } 1941 1942 struct FindAllocaForValueTestParams { 1943 const char *IR; 1944 bool AnyOffsetResult; 1945 bool ZeroOffsetResult; 1946 }; 1947 1948 class FindAllocaForValueTest 1949 : public ValueTrackingTest, 1950 public ::testing::WithParamInterface<FindAllocaForValueTestParams> { 1951 protected: 1952 }; 1953 1954 const FindAllocaForValueTestParams FindAllocaForValueTests[] = { 1955 {R"( 1956 define void @test() { 1957 %a = alloca i64 1958 %r = bitcast i64* %a to i32* 1959 ret void 1960 })", 1961 true, true}, 1962 1963 {R"( 1964 define void @test() { 1965 %a = alloca i32 1966 %r = getelementptr i32, i32* %a, i32 1 1967 ret void 1968 })", 1969 true, false}, 1970 1971 {R"( 1972 define void @test() { 1973 %a = alloca i32 1974 %r = getelementptr i32, i32* %a, i32 0 1975 ret void 1976 })", 1977 true, true}, 1978 1979 {R"( 1980 define void @test(i1 %cond) { 1981 entry: 1982 %a = alloca i32 1983 br label %bb1 1984 1985 bb1: 1986 %r = phi i32* [ %a, %entry ], [ %r, %bb1 ] 1987 br i1 %cond, label %bb1, label %exit 1988 1989 exit: 1990 ret void 1991 })", 1992 true, true}, 1993 1994 {R"( 1995 define void @test(i1 %cond) { 1996 %a = alloca i32 1997 %r = select i1 %cond, i32* %a, i32* %a 1998 ret void 1999 })", 2000 true, true}, 2001 2002 {R"( 2003 define void @test(i1 %cond) { 2004 %a = alloca i32 2005 %b = alloca i32 2006 %r = select i1 %cond, i32* %a, i32* %b 2007 ret void 2008 })", 2009 false, false}, 2010 2011 {R"( 2012 define void @test(i1 %cond) { 2013 entry: 2014 %a = alloca i64 2015 %a32 = bitcast i64* %a to i32* 2016 br label %bb1 2017 2018 bb1: 2019 %x = phi i32* [ %a32, %entry ], [ %x, %bb1 ] 2020 %r = getelementptr i32, i32* %x, i32 1 2021 br i1 %cond, label %bb1, label %exit 2022 2023 exit: 2024 ret void 2025 })", 2026 true, false}, 2027 2028 {R"( 2029 define void @test(i1 %cond) { 2030 entry: 2031 %a = alloca i64 2032 %a32 = bitcast i64* %a to i32* 2033 br label %bb1 2034 2035 bb1: 2036 %x = phi i32* [ %a32, %entry ], [ %r, %bb1 ] 2037 %r = getelementptr i32, i32* %x, i32 1 2038 br i1 %cond, label %bb1, label %exit 2039 2040 exit: 2041 ret void 2042 })", 2043 true, false}, 2044 2045 {R"( 2046 define void @test(i1 %cond, i64* %a) { 2047 entry: 2048 %r = bitcast i64* %a to i32* 2049 ret void 2050 })", 2051 false, false}, 2052 2053 {R"( 2054 define void @test(i1 %cond) { 2055 entry: 2056 %a = alloca i32 2057 %b = alloca i32 2058 br label %bb1 2059 2060 bb1: 2061 %r = phi i32* [ %a, %entry ], [ %b, %bb1 ] 2062 br i1 %cond, label %bb1, label %exit 2063 2064 exit: 2065 ret void 2066 })", 2067 false, false}, 2068 }; 2069 2070 TEST_P(FindAllocaForValueTest, findAllocaForValue) { 2071 auto M = parseModule(GetParam().IR); 2072 Function *F = M->getFunction("test"); 2073 Instruction *I = &findInstructionByName(F, "r"); 2074 const AllocaInst *AI = findAllocaForValue(I); 2075 EXPECT_EQ(!!AI, GetParam().AnyOffsetResult); 2076 } 2077 2078 TEST_P(FindAllocaForValueTest, findAllocaForValueZeroOffset) { 2079 auto M = parseModule(GetParam().IR); 2080 Function *F = M->getFunction("test"); 2081 Instruction *I = &findInstructionByName(F, "r"); 2082 const AllocaInst *AI = findAllocaForValue(I, true); 2083 EXPECT_EQ(!!AI, GetParam().ZeroOffsetResult); 2084 } 2085 2086 INSTANTIATE_TEST_CASE_P(FindAllocaForValueTest, FindAllocaForValueTest, 2087 ::testing::ValuesIn(FindAllocaForValueTests), ); 2088