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/IRBuilder.h" 16 #include "llvm/IR/InstIterator.h" 17 #include "llvm/IR/Instructions.h" 18 #include "llvm/IR/LLVMContext.h" 19 #include "llvm/IR/Module.h" 20 #include "llvm/Support/ErrorHandling.h" 21 #include "llvm/Support/KnownBits.h" 22 #include "llvm/Support/SourceMgr.h" 23 #include "llvm/Transforms/Utils/Local.h" 24 #include "gtest/gtest.h" 25 26 using namespace llvm; 27 28 namespace { 29 30 static Instruction *findInstructionByNameOrNull(Function *F, StringRef Name) { 31 for (Instruction &I : instructions(F)) 32 if (I.getName() == Name) 33 return &I; 34 35 return nullptr; 36 } 37 38 static Instruction &findInstructionByName(Function *F, StringRef Name) { 39 auto *I = findInstructionByNameOrNull(F, Name); 40 if (I) 41 return *I; 42 43 llvm_unreachable("Expected value not found"); 44 } 45 46 class ValueTrackingTest : public testing::Test { 47 protected: 48 std::unique_ptr<Module> parseModule(StringRef Assembly) { 49 SMDiagnostic Error; 50 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context); 51 52 std::string errMsg; 53 raw_string_ostream os(errMsg); 54 Error.print("", os); 55 EXPECT_TRUE(M) << os.str(); 56 57 return M; 58 } 59 60 void parseAssembly(StringRef Assembly) { 61 M = parseModule(Assembly); 62 ASSERT_TRUE(M); 63 64 F = M->getFunction("test"); 65 ASSERT_TRUE(F) << "Test must have a function @test"; 66 if (!F) 67 return; 68 69 A = findInstructionByNameOrNull(F, "A"); 70 ASSERT_TRUE(A) << "@test must have an instruction %A"; 71 A2 = findInstructionByNameOrNull(F, "A2"); 72 A3 = findInstructionByNameOrNull(F, "A3"); 73 A4 = findInstructionByNameOrNull(F, "A4"); 74 A5 = findInstructionByNameOrNull(F, "A5"); 75 A6 = findInstructionByNameOrNull(F, "A6"); 76 A7 = findInstructionByNameOrNull(F, "A7"); 77 78 CxtI = findInstructionByNameOrNull(F, "CxtI"); 79 CxtI2 = findInstructionByNameOrNull(F, "CxtI2"); 80 CxtI3 = findInstructionByNameOrNull(F, "CxtI3"); 81 } 82 83 LLVMContext Context; 84 std::unique_ptr<Module> M; 85 Function *F = nullptr; 86 Instruction *A = nullptr; 87 // Instructions (optional) 88 Instruction *A2 = nullptr, *A3 = nullptr, *A4 = nullptr, *A5 = nullptr, 89 *A6 = nullptr, *A7 = nullptr; 90 91 // Context instructions (optional) 92 Instruction *CxtI = nullptr, *CxtI2 = nullptr, *CxtI3 = nullptr; 93 }; 94 95 class MatchSelectPatternTest : public ValueTrackingTest { 96 protected: 97 void expectPattern(const SelectPatternResult &P) { 98 Value *LHS, *RHS; 99 Instruction::CastOps CastOp; 100 SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp); 101 EXPECT_EQ(P.Flavor, R.Flavor); 102 EXPECT_EQ(P.NaNBehavior, R.NaNBehavior); 103 EXPECT_EQ(P.Ordered, R.Ordered); 104 } 105 }; 106 107 class ComputeKnownBitsTest : public ValueTrackingTest { 108 protected: 109 void expectKnownBits(uint64_t Zero, uint64_t One) { 110 auto Known = computeKnownBits(A, M->getDataLayout()); 111 ASSERT_FALSE(Known.hasConflict()); 112 EXPECT_EQ(Known.One.getZExtValue(), One); 113 EXPECT_EQ(Known.Zero.getZExtValue(), Zero); 114 } 115 }; 116 117 class ComputeKnownFPClassTest : public ValueTrackingTest { 118 protected: 119 void expectKnownFPClass(unsigned KnownTrue, std::optional<bool> SignBitKnown, 120 Instruction *TestVal = nullptr) { 121 if (!TestVal) 122 TestVal = A; 123 124 KnownFPClass Known = computeKnownFPClass(TestVal, M->getDataLayout()); 125 EXPECT_EQ(KnownTrue, Known.KnownFPClasses); 126 EXPECT_EQ(SignBitKnown, Known.SignBit); 127 } 128 }; 129 } 130 131 TEST_F(MatchSelectPatternTest, SimpleFMin) { 132 parseAssembly( 133 "define float @test(float %a) {\n" 134 " %1 = fcmp ult float %a, 5.0\n" 135 " %A = select i1 %1, float %a, float 5.0\n" 136 " ret float %A\n" 137 "}\n"); 138 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false}); 139 } 140 141 TEST_F(MatchSelectPatternTest, SimpleFMax) { 142 parseAssembly( 143 "define float @test(float %a) {\n" 144 " %1 = fcmp ogt float %a, 5.0\n" 145 " %A = select i1 %1, float %a, float 5.0\n" 146 " ret float %A\n" 147 "}\n"); 148 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true}); 149 } 150 151 TEST_F(MatchSelectPatternTest, SwappedFMax) { 152 parseAssembly( 153 "define float @test(float %a) {\n" 154 " %1 = fcmp olt float 5.0, %a\n" 155 " %A = select i1 %1, float %a, float 5.0\n" 156 " ret float %A\n" 157 "}\n"); 158 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false}); 159 } 160 161 TEST_F(MatchSelectPatternTest, SwappedFMax2) { 162 parseAssembly( 163 "define float @test(float %a) {\n" 164 " %1 = fcmp olt float %a, 5.0\n" 165 " %A = select i1 %1, float 5.0, float %a\n" 166 " ret float %A\n" 167 "}\n"); 168 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false}); 169 } 170 171 TEST_F(MatchSelectPatternTest, SwappedFMax3) { 172 parseAssembly( 173 "define float @test(float %a) {\n" 174 " %1 = fcmp ult float %a, 5.0\n" 175 " %A = select i1 %1, float 5.0, float %a\n" 176 " ret float %A\n" 177 "}\n"); 178 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true}); 179 } 180 181 TEST_F(MatchSelectPatternTest, FastFMin) { 182 parseAssembly( 183 "define float @test(float %a) {\n" 184 " %1 = fcmp nnan olt float %a, 5.0\n" 185 " %A = select i1 %1, float %a, float 5.0\n" 186 " ret float %A\n" 187 "}\n"); 188 expectPattern({SPF_FMINNUM, SPNB_RETURNS_ANY, false}); 189 } 190 191 TEST_F(MatchSelectPatternTest, FMinConstantZero) { 192 parseAssembly( 193 "define float @test(float %a) {\n" 194 " %1 = fcmp ole float %a, 0.0\n" 195 " %A = select i1 %1, float %a, float 0.0\n" 196 " ret float %A\n" 197 "}\n"); 198 // This shouldn't be matched, as %a could be -0.0. 199 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 200 } 201 202 TEST_F(MatchSelectPatternTest, FMinConstantZeroNsz) { 203 parseAssembly( 204 "define float @test(float %a) {\n" 205 " %1 = fcmp nsz ole float %a, 0.0\n" 206 " %A = select i1 %1, float %a, float 0.0\n" 207 " ret float %A\n" 208 "}\n"); 209 // But this should be, because we've ignored signed zeroes. 210 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true}); 211 } 212 213 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero1) { 214 parseAssembly( 215 "define float @test(float %a) {\n" 216 " %1 = fcmp olt float -0.0, %a\n" 217 " %A = select i1 %1, float 0.0, float %a\n" 218 " ret float %A\n" 219 "}\n"); 220 // The sign of zero doesn't matter in fcmp. 221 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 222 } 223 224 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero2) { 225 parseAssembly( 226 "define float @test(float %a) {\n" 227 " %1 = fcmp ogt float %a, -0.0\n" 228 " %A = select i1 %1, float 0.0, float %a\n" 229 " ret float %A\n" 230 "}\n"); 231 // The sign of zero doesn't matter in fcmp. 232 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 233 } 234 235 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero3) { 236 parseAssembly( 237 "define float @test(float %a) {\n" 238 " %1 = fcmp olt float 0.0, %a\n" 239 " %A = select i1 %1, float -0.0, float %a\n" 240 " ret float %A\n" 241 "}\n"); 242 // The sign of zero doesn't matter in fcmp. 243 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 244 } 245 246 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero4) { 247 parseAssembly( 248 "define float @test(float %a) {\n" 249 " %1 = fcmp ogt float %a, 0.0\n" 250 " %A = select i1 %1, float -0.0, float %a\n" 251 " ret float %A\n" 252 "}\n"); 253 // The sign of zero doesn't matter in fcmp. 254 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 255 } 256 257 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero5) { 258 parseAssembly( 259 "define float @test(float %a) {\n" 260 " %1 = fcmp ogt float -0.0, %a\n" 261 " %A = select i1 %1, float %a, float 0.0\n" 262 " ret float %A\n" 263 "}\n"); 264 // The sign of zero doesn't matter in fcmp. 265 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 266 } 267 268 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero6) { 269 parseAssembly( 270 "define float @test(float %a) {\n" 271 " %1 = fcmp olt float %a, -0.0\n" 272 " %A = select i1 %1, float %a, float 0.0\n" 273 " ret float %A\n" 274 "}\n"); 275 // The sign of zero doesn't matter in fcmp. 276 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 277 } 278 279 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero7) { 280 parseAssembly( 281 "define float @test(float %a) {\n" 282 " %1 = fcmp ogt float 0.0, %a\n" 283 " %A = select i1 %1, float %a, float -0.0\n" 284 " ret float %A\n" 285 "}\n"); 286 // The sign of zero doesn't matter in fcmp. 287 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 288 } 289 290 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero8) { 291 parseAssembly( 292 "define float @test(float %a) {\n" 293 " %1 = fcmp olt float %a, 0.0\n" 294 " %A = select i1 %1, float %a, float -0.0\n" 295 " ret float %A\n" 296 "}\n"); 297 // The sign of zero doesn't matter in fcmp. 298 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 299 } 300 301 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero1) { 302 parseAssembly( 303 "define float @test(float %a) {\n" 304 " %1 = fcmp ogt float -0.0, %a\n" 305 " %A = select i1 %1, float 0.0, float %a\n" 306 " ret float %A\n" 307 "}\n"); 308 // The sign of zero doesn't matter in fcmp. 309 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 310 } 311 312 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero2) { 313 parseAssembly( 314 "define float @test(float %a) {\n" 315 " %1 = fcmp olt float %a, -0.0\n" 316 " %A = select i1 %1, float 0.0, float %a\n" 317 " ret float %A\n" 318 "}\n"); 319 // The sign of zero doesn't matter in fcmp. 320 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 321 } 322 323 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero3) { 324 parseAssembly( 325 "define float @test(float %a) {\n" 326 " %1 = fcmp ogt float 0.0, %a\n" 327 " %A = select i1 %1, float -0.0, float %a\n" 328 " ret float %A\n" 329 "}\n"); 330 // The sign of zero doesn't matter in fcmp. 331 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 332 } 333 334 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero4) { 335 parseAssembly( 336 "define float @test(float %a) {\n" 337 " %1 = fcmp olt float %a, 0.0\n" 338 " %A = select i1 %1, float -0.0, float %a\n" 339 " ret float %A\n" 340 "}\n"); 341 // The sign of zero doesn't matter in fcmp. 342 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 343 } 344 345 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero5) { 346 parseAssembly( 347 "define float @test(float %a) {\n" 348 " %1 = fcmp olt float -0.0, %a\n" 349 " %A = select i1 %1, float %a, float 0.0\n" 350 " ret float %A\n" 351 "}\n"); 352 // The sign of zero doesn't matter in fcmp. 353 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 354 } 355 356 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero6) { 357 parseAssembly( 358 "define float @test(float %a) {\n" 359 " %1 = fcmp ogt float %a, -0.0\n" 360 " %A = select i1 %1, float %a, float 0.0\n" 361 " ret float %A\n" 362 "}\n"); 363 // The sign of zero doesn't matter in fcmp. 364 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 365 } 366 367 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero7) { 368 parseAssembly( 369 "define float @test(float %a) {\n" 370 " %1 = fcmp olt float 0.0, %a\n" 371 " %A = select i1 %1, float %a, float -0.0\n" 372 " ret float %A\n" 373 "}\n"); 374 // The sign of zero doesn't matter in fcmp. 375 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 376 } 377 378 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero8) { 379 parseAssembly( 380 "define float @test(float %a) {\n" 381 " %1 = fcmp ogt float %a, 0.0\n" 382 " %A = select i1 %1, float %a, float -0.0\n" 383 " ret float %A\n" 384 "}\n"); 385 // The sign of zero doesn't matter in fcmp. 386 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 387 } 388 389 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZeroVecUndef) { 390 parseAssembly( 391 "define <2 x float> @test(<2 x float> %a) {\n" 392 " %1 = fcmp ogt <2 x float> %a, <float -0.0, float -0.0>\n" 393 " %A = select <2 x i1> %1, <2 x float> <float undef, float 0.0>, <2 x float> %a\n" 394 " ret <2 x float> %A\n" 395 "}\n"); 396 // An undef in a vector constant can not be back-propagated for this analysis. 397 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 398 } 399 400 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZeroVecUndef) { 401 parseAssembly( 402 "define <2 x float> @test(<2 x float> %a) {\n" 403 " %1 = fcmp ogt <2 x float> %a, zeroinitializer\n" 404 " %A = select <2 x i1> %1, <2 x float> %a, <2 x float> <float -0.0, float undef>\n" 405 " ret <2 x float> %A\n" 406 "}\n"); 407 // An undef in a vector constant can not be back-propagated for this analysis. 408 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 409 } 410 411 TEST_F(MatchSelectPatternTest, VectorFMinimum) { 412 parseAssembly( 413 "define <4 x float> @test(<4 x float> %a) {\n" 414 " %1 = fcmp ule <4 x float> %a, \n" 415 " <float 5.0, float 5.0, float 5.0, float 5.0>\n" 416 " %A = select <4 x i1> %1, <4 x float> %a,\n" 417 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n" 418 " ret <4 x float> %A\n" 419 "}\n"); 420 // Check that pattern matching works on vectors where each lane has the same 421 // unordered pattern. 422 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false}); 423 } 424 425 TEST_F(MatchSelectPatternTest, VectorFMinOtherOrdered) { 426 parseAssembly( 427 "define <4 x float> @test(<4 x float> %a) {\n" 428 " %1 = fcmp ole <4 x float> %a, \n" 429 " <float 5.0, float 5.0, float 5.0, float 5.0>\n" 430 " %A = select <4 x i1> %1, <4 x float> %a,\n" 431 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n" 432 " ret <4 x float> %A\n" 433 "}\n"); 434 // Check that pattern matching works on vectors where each lane has the same 435 // ordered pattern. 436 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true}); 437 } 438 439 TEST_F(MatchSelectPatternTest, VectorNotFMinimum) { 440 parseAssembly( 441 "define <4 x float> @test(<4 x float> %a) {\n" 442 " %1 = fcmp ule <4 x float> %a, \n" 443 " <float 5.0, float 0x7ff8000000000000, float 5.0, float 5.0>\n" 444 " %A = select <4 x i1> %1, <4 x float> %a,\n" 445 " <4 x float> <float 5.0, float 0x7ff8000000000000, float 5.0, float " 446 "5.0>\n" 447 " ret <4 x float> %A\n" 448 "}\n"); 449 // The lane that contains a NaN (0x7ff80...) behaves like a 450 // non-NaN-propagating min and the other lines behave like a NaN-propagating 451 // min, so check that neither is returned. 452 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 453 } 454 455 TEST_F(MatchSelectPatternTest, VectorNotFMinZero) { 456 parseAssembly( 457 "define <4 x float> @test(<4 x float> %a) {\n" 458 " %1 = fcmp ule <4 x float> %a, \n" 459 " <float 5.0, float -0.0, float 5.0, float 5.0>\n" 460 " %A = select <4 x i1> %1, <4 x float> %a,\n" 461 " <4 x float> <float 5.0, float 0.0, float 5.0, float 5.0>\n" 462 " ret <4 x float> %A\n" 463 "}\n"); 464 // Always selects the second lane of %a if it is positive or negative zero, so 465 // this is stricter than a min. 466 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 467 } 468 469 TEST_F(MatchSelectPatternTest, DoubleCastU) { 470 parseAssembly( 471 "define i32 @test(i8 %a, i8 %b) {\n" 472 " %1 = icmp ult i8 %a, %b\n" 473 " %2 = zext i8 %a to i32\n" 474 " %3 = zext i8 %b to i32\n" 475 " %A = select i1 %1, i32 %2, i32 %3\n" 476 " ret i32 %A\n" 477 "}\n"); 478 // We should be able to look through the situation where we cast both operands 479 // to the select. 480 expectPattern({SPF_UMIN, SPNB_NA, false}); 481 } 482 483 TEST_F(MatchSelectPatternTest, DoubleCastS) { 484 parseAssembly( 485 "define i32 @test(i8 %a, i8 %b) {\n" 486 " %1 = icmp slt i8 %a, %b\n" 487 " %2 = sext i8 %a to i32\n" 488 " %3 = sext i8 %b to i32\n" 489 " %A = select i1 %1, i32 %2, i32 %3\n" 490 " ret i32 %A\n" 491 "}\n"); 492 // We should be able to look through the situation where we cast both operands 493 // to the select. 494 expectPattern({SPF_SMIN, SPNB_NA, false}); 495 } 496 497 TEST_F(MatchSelectPatternTest, DoubleCastBad) { 498 parseAssembly( 499 "define i32 @test(i8 %a, i8 %b) {\n" 500 " %1 = icmp ult i8 %a, %b\n" 501 " %2 = zext i8 %a to i32\n" 502 " %3 = sext i8 %b to i32\n" 503 " %A = select i1 %1, i32 %2, i32 %3\n" 504 " ret i32 %A\n" 505 "}\n"); 506 // The cast types here aren't the same, so we cannot match an UMIN. 507 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 508 } 509 510 TEST_F(MatchSelectPatternTest, NotNotSMin) { 511 parseAssembly( 512 "define i8 @test(i8 %a, i8 %b) {\n" 513 " %cmp = icmp sgt i8 %a, %b\n" 514 " %an = xor i8 %a, -1\n" 515 " %bn = xor i8 %b, -1\n" 516 " %A = select i1 %cmp, i8 %an, i8 %bn\n" 517 " ret i8 %A\n" 518 "}\n"); 519 expectPattern({SPF_SMIN, SPNB_NA, false}); 520 } 521 522 TEST_F(MatchSelectPatternTest, NotNotSMinSwap) { 523 parseAssembly( 524 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n" 525 " %cmp = icmp slt <2 x i8> %a, %b\n" 526 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n" 527 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n" 528 " %A = select <2 x i1> %cmp, <2 x i8> %bn, <2 x i8> %an\n" 529 " ret <2 x i8> %A\n" 530 "}\n"); 531 expectPattern({SPF_SMIN, SPNB_NA, false}); 532 } 533 534 TEST_F(MatchSelectPatternTest, NotNotSMax) { 535 parseAssembly( 536 "define i8 @test(i8 %a, i8 %b) {\n" 537 " %cmp = icmp slt i8 %a, %b\n" 538 " %an = xor i8 %a, -1\n" 539 " %bn = xor i8 %b, -1\n" 540 " %A = select i1 %cmp, i8 %an, i8 %bn\n" 541 " ret i8 %A\n" 542 "}\n"); 543 expectPattern({SPF_SMAX, SPNB_NA, false}); 544 } 545 546 TEST_F(MatchSelectPatternTest, NotNotSMaxSwap) { 547 parseAssembly( 548 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n" 549 " %cmp = icmp sgt <2 x i8> %a, %b\n" 550 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n" 551 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n" 552 " %A = select <2 x i1> %cmp, <2 x i8> %bn, <2 x i8> %an\n" 553 " ret <2 x i8> %A\n" 554 "}\n"); 555 expectPattern({SPF_SMAX, SPNB_NA, false}); 556 } 557 558 TEST_F(MatchSelectPatternTest, NotNotUMin) { 559 parseAssembly( 560 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n" 561 " %cmp = icmp ugt <2 x i8> %a, %b\n" 562 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n" 563 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n" 564 " %A = select <2 x i1> %cmp, <2 x i8> %an, <2 x i8> %bn\n" 565 " ret <2 x i8> %A\n" 566 "}\n"); 567 expectPattern({SPF_UMIN, SPNB_NA, false}); 568 } 569 570 TEST_F(MatchSelectPatternTest, NotNotUMinSwap) { 571 parseAssembly( 572 "define i8 @test(i8 %a, i8 %b) {\n" 573 " %cmp = icmp ult i8 %a, %b\n" 574 " %an = xor i8 %a, -1\n" 575 " %bn = xor i8 %b, -1\n" 576 " %A = select i1 %cmp, i8 %bn, i8 %an\n" 577 " ret i8 %A\n" 578 "}\n"); 579 expectPattern({SPF_UMIN, SPNB_NA, false}); 580 } 581 582 TEST_F(MatchSelectPatternTest, NotNotUMax) { 583 parseAssembly( 584 "define <2 x i8> @test(<2 x i8> %a, <2 x i8> %b) {\n" 585 " %cmp = icmp ult <2 x i8> %a, %b\n" 586 " %an = xor <2 x i8> %a, <i8 -1, i8-1>\n" 587 " %bn = xor <2 x i8> %b, <i8 -1, i8-1>\n" 588 " %A = select <2 x i1> %cmp, <2 x i8> %an, <2 x i8> %bn\n" 589 " ret <2 x i8> %A\n" 590 "}\n"); 591 expectPattern({SPF_UMAX, SPNB_NA, false}); 592 } 593 594 TEST_F(MatchSelectPatternTest, NotNotUMaxSwap) { 595 parseAssembly( 596 "define i8 @test(i8 %a, i8 %b) {\n" 597 " %cmp = icmp ugt i8 %a, %b\n" 598 " %an = xor i8 %a, -1\n" 599 " %bn = xor i8 %b, -1\n" 600 " %A = select i1 %cmp, i8 %bn, i8 %an\n" 601 " ret i8 %A\n" 602 "}\n"); 603 expectPattern({SPF_UMAX, SPNB_NA, false}); 604 } 605 606 TEST_F(MatchSelectPatternTest, NotNotEq) { 607 parseAssembly( 608 "define i8 @test(i8 %a, i8 %b) {\n" 609 " %cmp = icmp eq i8 %a, %b\n" 610 " %an = xor i8 %a, -1\n" 611 " %bn = xor i8 %b, -1\n" 612 " %A = select i1 %cmp, i8 %bn, i8 %an\n" 613 " ret i8 %A\n" 614 "}\n"); 615 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 616 } 617 618 TEST_F(MatchSelectPatternTest, NotNotNe) { 619 parseAssembly( 620 "define i8 @test(i8 %a, i8 %b) {\n" 621 " %cmp = icmp ne i8 %a, %b\n" 622 " %an = xor i8 %a, -1\n" 623 " %bn = xor i8 %b, -1\n" 624 " %A = select i1 %cmp, i8 %bn, i8 %an\n" 625 " ret i8 %A\n" 626 "}\n"); 627 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 628 } 629 630 TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) { 631 StringRef Assembly = 632 "declare void @nounwind_readonly(ptr) nounwind readonly " 633 "declare void @nounwind_argmemonly(ptr) nounwind argmemonly " 634 "declare void @nounwind_willreturn(ptr) nounwind willreturn " 635 "declare void @throws_but_readonly(ptr) readonly " 636 "declare void @throws_but_argmemonly(ptr) argmemonly " 637 "declare void @throws_but_willreturn(ptr) willreturn " 638 " " 639 "declare void @unknown(ptr) " 640 " " 641 "define void @f(ptr %p) { " 642 " call void @nounwind_readonly(ptr %p) " 643 " call void @nounwind_argmemonly(ptr %p) " 644 " call void @nounwind_willreturn(ptr %p)" 645 " call void @throws_but_readonly(ptr %p) " 646 " call void @throws_but_argmemonly(ptr %p) " 647 " call void @throws_but_willreturn(ptr %p) " 648 " call void @unknown(ptr %p) nounwind readonly " 649 " call void @unknown(ptr %p) nounwind argmemonly " 650 " call void @unknown(ptr %p) nounwind willreturn " 651 " call void @unknown(ptr %p) readonly " 652 " call void @unknown(ptr %p) argmemonly " 653 " call void @unknown(ptr %p) willreturn " 654 " ret void " 655 "} "; 656 657 LLVMContext Context; 658 SMDiagnostic Error; 659 auto M = parseAssemblyString(Assembly, Error, Context); 660 assert(M && "Bad assembly?"); 661 662 auto *F = M->getFunction("f"); 663 assert(F && "Bad assembly?"); 664 665 auto &BB = F->getEntryBlock(); 666 bool ExpectedAnswers[] = { 667 false, // call void @nounwind_readonly(ptr %p) 668 false, // call void @nounwind_argmemonly(ptr %p) 669 true, // call void @nounwind_willreturn(ptr %p) 670 false, // call void @throws_but_readonly(ptr %p) 671 false, // call void @throws_but_argmemonly(ptr %p) 672 false, // call void @throws_but_willreturn(ptr %p) 673 false, // call void @unknown(ptr %p) nounwind readonly 674 false, // call void @unknown(ptr %p) nounwind argmemonly 675 true, // call void @unknown(ptr %p) nounwind willreturn 676 false, // call void @unknown(ptr %p) readonly 677 false, // call void @unknown(ptr %p) argmemonly 678 false, // call void @unknown(ptr %p) willreturn 679 false, // ret void 680 }; 681 682 int Index = 0; 683 for (auto &I : BB) { 684 EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I), 685 ExpectedAnswers[Index]) 686 << "Incorrect answer at instruction " << Index << " = " << I; 687 Index++; 688 } 689 } 690 691 TEST_F(ValueTrackingTest, ComputeNumSignBits_PR32045) { 692 parseAssembly( 693 "define i32 @test(i32 %a) {\n" 694 " %A = ashr i32 %a, -1\n" 695 " ret i32 %A\n" 696 "}\n"); 697 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); 698 } 699 700 // No guarantees for canonical IR in this analysis, so this just bails out. 701 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle) { 702 parseAssembly( 703 "define <2 x i32> @test() {\n" 704 " %A = shufflevector <2 x i32> undef, <2 x i32> undef, <2 x i32> <i32 0, i32 0>\n" 705 " ret <2 x i32> %A\n" 706 "}\n"); 707 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); 708 } 709 710 // No guarantees for canonical IR in this analysis, so a shuffle element that 711 // references an undef value means this can't return any extra information. 712 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) { 713 parseAssembly( 714 "define <2 x i32> @test(<2 x i1> %x) {\n" 715 " %sext = sext <2 x i1> %x to <2 x i32>\n" 716 " %A = shufflevector <2 x i32> %sext, <2 x i32> undef, <2 x i32> <i32 0, i32 2>\n" 717 " ret <2 x i32> %A\n" 718 "}\n"); 719 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); 720 } 721 722 TEST_F(ValueTrackingTest, impliesPoisonTest_Identity) { 723 parseAssembly("define void @test(i32 %x, i32 %y) {\n" 724 " %A = add i32 %x, %y\n" 725 " ret void\n" 726 "}"); 727 EXPECT_TRUE(impliesPoison(A, A)); 728 } 729 730 TEST_F(ValueTrackingTest, impliesPoisonTest_ICmp) { 731 parseAssembly("define void @test(i32 %x) {\n" 732 " %A2 = icmp eq i32 %x, 0\n" 733 " %A = icmp eq i32 %x, 1\n" 734 " ret void\n" 735 "}"); 736 EXPECT_TRUE(impliesPoison(A2, A)); 737 } 738 739 TEST_F(ValueTrackingTest, impliesPoisonTest_ICmpUnknown) { 740 parseAssembly("define void @test(i32 %x, i32 %y) {\n" 741 " %A2 = icmp eq i32 %x, %y\n" 742 " %A = icmp eq i32 %x, 1\n" 743 " ret void\n" 744 "}"); 745 EXPECT_FALSE(impliesPoison(A2, A)); 746 } 747 748 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNswOkay) { 749 parseAssembly("define void @test(i32 %x) {\n" 750 " %A2 = add nsw i32 %x, 1\n" 751 " %A = add i32 %A2, 1\n" 752 " ret void\n" 753 "}"); 754 EXPECT_TRUE(impliesPoison(A2, A)); 755 } 756 757 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNswOkay2) { 758 parseAssembly("define void @test(i32 %x) {\n" 759 " %A2 = add i32 %x, 1\n" 760 " %A = add nsw i32 %A2, 1\n" 761 " ret void\n" 762 "}"); 763 EXPECT_TRUE(impliesPoison(A2, A)); 764 } 765 766 TEST_F(ValueTrackingTest, impliesPoisonTest_AddNsw) { 767 parseAssembly("define void @test(i32 %x) {\n" 768 " %A2 = add nsw i32 %x, 1\n" 769 " %A = add i32 %x, 1\n" 770 " ret void\n" 771 "}"); 772 EXPECT_FALSE(impliesPoison(A2, A)); 773 } 774 775 TEST_F(ValueTrackingTest, impliesPoisonTest_Cmp) { 776 parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n" 777 " %A2 = icmp eq i32 %x, %y\n" 778 " %A0 = icmp ult i32 %x, %y\n" 779 " %A = or i1 %A0, %c\n" 780 " ret void\n" 781 "}"); 782 EXPECT_TRUE(impliesPoison(A2, A)); 783 } 784 785 TEST_F(ValueTrackingTest, impliesPoisonTest_FCmpFMF) { 786 parseAssembly("define void @test(float %x, float %y, i1 %c) {\n" 787 " %A2 = fcmp nnan oeq float %x, %y\n" 788 " %A0 = fcmp olt float %x, %y\n" 789 " %A = or i1 %A0, %c\n" 790 " ret void\n" 791 "}"); 792 EXPECT_FALSE(impliesPoison(A2, A)); 793 } 794 795 TEST_F(ValueTrackingTest, impliesPoisonTest_AddSubSameOps) { 796 parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n" 797 " %A2 = add i32 %x, %y\n" 798 " %A = sub i32 %x, %y\n" 799 " ret void\n" 800 "}"); 801 EXPECT_TRUE(impliesPoison(A2, A)); 802 } 803 804 TEST_F(ValueTrackingTest, impliesPoisonTest_MaskCmp) { 805 parseAssembly("define void @test(i32 %x, i32 %y, i1 %c) {\n" 806 " %M2 = and i32 %x, 7\n" 807 " %A2 = icmp eq i32 %M2, 1\n" 808 " %M = and i32 %x, 15\n" 809 " %A = icmp eq i32 %M, 3\n" 810 " ret void\n" 811 "}"); 812 EXPECT_TRUE(impliesPoison(A2, A)); 813 } 814 815 TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle_Pointers) { 816 parseAssembly( 817 "define <2 x ptr> @test(<2 x ptr> %x) {\n" 818 " %A = shufflevector <2 x ptr> zeroinitializer, <2 x ptr> undef, <2 x i32> zeroinitializer\n" 819 " ret <2 x ptr> %A\n" 820 "}\n"); 821 EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 64u); 822 } 823 824 TEST(ValueTracking, propagatesPoison) { 825 std::string AsmHead = 826 "declare i32 @g(i32)\n" 827 "declare {i32, i1} @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)\n" 828 "declare {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)\n" 829 "declare {i32, i1} @llvm.smul.with.overflow.i32(i32 %a, i32 %b)\n" 830 "declare {i32, i1} @llvm.uadd.with.overflow.i32(i32 %a, i32 %b)\n" 831 "declare {i32, i1} @llvm.usub.with.overflow.i32(i32 %a, i32 %b)\n" 832 "declare {i32, i1} @llvm.umul.with.overflow.i32(i32 %a, i32 %b)\n" 833 "declare float @llvm.sqrt.f32(float)\n" 834 "declare float @llvm.powi.f32.i32(float, i32)\n" 835 "declare float @llvm.sin.f32(float)\n" 836 "declare float @llvm.cos.f32(float)\n" 837 "declare float @llvm.pow.f32(float, float)\n" 838 "declare float @llvm.exp.f32(float)\n" 839 "declare float @llvm.exp2.f32(float)\n" 840 "declare float @llvm.log.f32(float)\n" 841 "declare float @llvm.log10.f32(float)\n" 842 "declare float @llvm.log2.f32(float)\n" 843 "declare float @llvm.fma.f32(float, float, float)\n" 844 "declare float @llvm.fabs.f32(float)\n" 845 "declare float @llvm.minnum.f32(float, float)\n" 846 "declare float @llvm.maxnum.f32(float, float)\n" 847 "declare float @llvm.minimum.f32(float, float)\n" 848 "declare float @llvm.maximum.f32(float, float)\n" 849 "declare float @llvm.copysign.f32(float, float)\n" 850 "declare float @llvm.floor.f32(float)\n" 851 "declare float @llvm.ceil.f32(float)\n" 852 "declare float @llvm.trunc.f32(float)\n" 853 "declare float @llvm.rint.f32(float)\n" 854 "declare float @llvm.nearbyint.f32(float)\n" 855 "declare float @llvm.round.f32(float)\n" 856 "declare float @llvm.roundeven.f32(float)\n" 857 "declare i32 @llvm.lround.f32(float)\n" 858 "declare i64 @llvm.llround.f32(float)\n" 859 "declare i32 @llvm.lrint.f32(float)\n" 860 "declare i64 @llvm.llrint.f32(float)\n" 861 "declare float @llvm.fmuladd.f32(float, float, float)\n" 862 "define void @f(i32 %x, i32 %y, float %fx, float %fy, " 863 "i1 %cond, ptr %p) {\n"; 864 std::string AsmTail = " ret void\n}"; 865 // (propagates poison?, IR instruction) 866 SmallVector<std::tuple<bool, std::string, unsigned>, 32> Data = { 867 {true, "add i32 %x, %y", 0}, 868 {true, "add i32 %x, %y", 1}, 869 {true, "add nsw nuw i32 %x, %y", 0}, 870 {true, "add nsw nuw i32 %x, %y", 1}, 871 {true, "ashr i32 %x, %y", 0}, 872 {true, "ashr i32 %x, %y", 1}, 873 {true, "lshr exact i32 %x, 31", 0}, 874 {true, "lshr exact i32 %x, 31", 1}, 875 {true, "fadd float %fx, %fy", 0}, 876 {true, "fadd float %fx, %fy", 1}, 877 {true, "fsub float %fx, %fy", 0}, 878 {true, "fsub float %fx, %fy", 1}, 879 {true, "fmul float %fx, %fy", 0}, 880 {true, "fmul float %fx, %fy", 1}, 881 {true, "fdiv float %fx, %fy", 0}, 882 {true, "fdiv float %fx, %fy", 1}, 883 {true, "frem float %fx, %fy", 0}, 884 {true, "frem float %fx, %fy", 1}, 885 {true, "fneg float %fx", 0}, 886 {true, "fcmp oeq float %fx, %fy", 0}, 887 {true, "fcmp oeq float %fx, %fy", 1}, 888 {true, "icmp eq i32 %x, %y", 0}, 889 {true, "icmp eq i32 %x, %y", 1}, 890 {true, "getelementptr i8, ptr %p, i32 %x", 0}, 891 {true, "getelementptr i8, ptr %p, i32 %x", 1}, 892 {true, "getelementptr inbounds i8, ptr %p, i32 %x", 0}, 893 {true, "getelementptr inbounds i8, ptr %p, i32 %x", 1}, 894 {true, "bitcast float %fx to i32", 0}, 895 {true, "select i1 %cond, i32 %x, i32 %y", 0}, 896 {false, "select i1 %cond, i32 %x, i32 %y", 1}, 897 {false, "select i1 %cond, i32 %x, i32 %y", 2}, 898 {false, "freeze i32 %x", 0}, 899 {true, "udiv i32 %x, %y", 0}, 900 {true, "udiv i32 %x, %y", 1}, 901 {true, "urem i32 %x, %y", 0}, 902 {true, "urem i32 %x, %y", 1}, 903 {true, "sdiv exact i32 %x, %y", 0}, 904 {true, "sdiv exact i32 %x, %y", 1}, 905 {true, "srem i32 %x, %y", 0}, 906 {true, "srem i32 %x, %y", 1}, 907 {false, "call i32 @g(i32 %x)", 0}, 908 {false, "call i32 @g(i32 %x)", 1}, 909 {true, "call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)", 0}, 910 {true, "call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %x, i32 %y)", 0}, 911 {true, "call {i32, i1} @llvm.smul.with.overflow.i32(i32 %x, i32 %y)", 0}, 912 {true, "call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)", 0}, 913 {true, "call {i32, i1} @llvm.usub.with.overflow.i32(i32 %x, i32 %y)", 0}, 914 {true, "call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 %y)", 0}, 915 {false, "call float @llvm.sqrt.f32(float %fx)", 0}, 916 {false, "call float @llvm.powi.f32.i32(float %fx, i32 %x)", 0}, 917 {false, "call float @llvm.sin.f32(float %fx)", 0}, 918 {false, "call float @llvm.cos.f32(float %fx)", 0}, 919 {false, "call float @llvm.pow.f32(float %fx, float %fy)", 0}, 920 {false, "call float @llvm.exp.f32(float %fx)", 0}, 921 {false, "call float @llvm.exp2.f32(float %fx)", 0}, 922 {false, "call float @llvm.log.f32(float %fx)", 0}, 923 {false, "call float @llvm.log10.f32(float %fx)", 0}, 924 {false, "call float @llvm.log2.f32(float %fx)", 0}, 925 {false, "call float @llvm.fma.f32(float %fx, float %fx, float %fy)", 0}, 926 {false, "call float @llvm.fabs.f32(float %fx)", 0}, 927 {false, "call float @llvm.minnum.f32(float %fx, float %fy)", 0}, 928 {false, "call float @llvm.maxnum.f32(float %fx, float %fy)", 0}, 929 {false, "call float @llvm.minimum.f32(float %fx, float %fy)", 0}, 930 {false, "call float @llvm.maximum.f32(float %fx, float %fy)", 0}, 931 {false, "call float @llvm.copysign.f32(float %fx, float %fy)", 0}, 932 {false, "call float @llvm.floor.f32(float %fx)", 0}, 933 {false, "call float @llvm.ceil.f32(float %fx)", 0}, 934 {false, "call float @llvm.trunc.f32(float %fx)", 0}, 935 {false, "call float @llvm.rint.f32(float %fx)", 0}, 936 {false, "call float @llvm.nearbyint.f32(float %fx)", 0}, 937 {false, "call float @llvm.round.f32(float %fx)", 0}, 938 {false, "call float @llvm.roundeven.f32(float %fx)", 0}, 939 {false, "call i32 @llvm.lround.f32(float %fx)", 0}, 940 {false, "call i64 @llvm.llround.f32(float %fx)", 0}, 941 {false, "call i32 @llvm.lrint.f32(float %fx)", 0}, 942 {false, "call i64 @llvm.llrint.f32(float %fx)", 0}, 943 {false, "call float @llvm.fmuladd.f32(float %fx, float %fx, float %fy)", 944 0}}; 945 946 std::string AssemblyStr = AsmHead; 947 for (auto &Itm : Data) 948 AssemblyStr += std::get<1>(Itm) + "\n"; 949 AssemblyStr += AsmTail; 950 951 LLVMContext Context; 952 SMDiagnostic Error; 953 auto M = parseAssemblyString(AssemblyStr, Error, Context); 954 assert(M && "Bad assembly?"); 955 956 auto *F = M->getFunction("f"); 957 assert(F && "Bad assembly?"); 958 959 auto &BB = F->getEntryBlock(); 960 961 int Index = 0; 962 for (auto &I : BB) { 963 if (isa<ReturnInst>(&I)) 964 break; 965 bool ExpectedVal = std::get<0>(Data[Index]); 966 unsigned OpIdx = std::get<2>(Data[Index]); 967 EXPECT_EQ(propagatesPoison(I.getOperandUse(OpIdx)), ExpectedVal) 968 << "Incorrect answer at instruction " << Index << " = " << I; 969 Index++; 970 } 971 } 972 973 TEST_F(ValueTrackingTest, programUndefinedIfPoison) { 974 parseAssembly("declare i32 @any_num()" 975 "define void @test(i32 %mask) {\n" 976 " %A = call i32 @any_num()\n" 977 " %B = or i32 %A, %mask\n" 978 " udiv i32 1, %B" 979 " ret void\n" 980 "}\n"); 981 // If %A was poison, udiv raises UB regardless of %mask's value 982 EXPECT_EQ(programUndefinedIfPoison(A), true); 983 } 984 985 TEST_F(ValueTrackingTest, programUndefinedIfPoisonSelect) { 986 parseAssembly("declare i32 @any_num()" 987 "define void @test(i1 %Cond) {\n" 988 " %A = call i32 @any_num()\n" 989 " %B = add i32 %A, 1\n" 990 " %C = select i1 %Cond, i32 %A, i32 %B\n" 991 " udiv i32 1, %C" 992 " ret void\n" 993 "}\n"); 994 // If A is poison, B is also poison, and therefore C is poison regardless of 995 // the value of %Cond. 996 EXPECT_EQ(programUndefinedIfPoison(A), true); 997 } 998 999 TEST_F(ValueTrackingTest, programUndefinedIfUndefOrPoison) { 1000 parseAssembly("declare i32 @any_num()" 1001 "define void @test(i32 %mask) {\n" 1002 " %A = call i32 @any_num()\n" 1003 " %B = or i32 %A, %mask\n" 1004 " udiv i32 1, %B" 1005 " ret void\n" 1006 "}\n"); 1007 // If %A was undef and %mask was 1, udiv does not raise UB 1008 EXPECT_EQ(programUndefinedIfUndefOrPoison(A), false); 1009 } 1010 1011 TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_exploitBranchCond) { 1012 parseAssembly("declare i1 @any_bool()" 1013 "define void @test(i1 %y) {\n" 1014 " %A = call i1 @any_bool()\n" 1015 " %cond = and i1 %A, %y\n" 1016 " br i1 %cond, label %BB1, label %BB2\n" 1017 "BB1:\n" 1018 " ret void\n" 1019 "BB2:\n" 1020 " ret void\n" 1021 "}\n"); 1022 DominatorTree DT(*F); 1023 for (auto &BB : *F) { 1024 if (&BB == &F->getEntryBlock()) 1025 continue; 1026 1027 EXPECT_EQ(isGuaranteedNotToBePoison(A, nullptr, BB.getTerminator(), &DT), 1028 true) 1029 << "isGuaranteedNotToBePoison does not hold at " << *BB.getTerminator(); 1030 } 1031 } 1032 1033 TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_phi) { 1034 parseAssembly("declare i32 @any_i32(i32)" 1035 "define void @test() {\n" 1036 "ENTRY:\n" 1037 " br label %LOOP\n" 1038 "LOOP:\n" 1039 " %A = phi i32 [0, %ENTRY], [%A.next, %NEXT]\n" 1040 " %A.next = call i32 @any_i32(i32 %A)\n" 1041 " %cond = icmp eq i32 %A.next, 0\n" 1042 " br i1 %cond, label %NEXT, label %EXIT\n" 1043 "NEXT:\n" 1044 " br label %LOOP\n" 1045 "EXIT:\n" 1046 " ret void\n" 1047 "}\n"); 1048 DominatorTree DT(*F); 1049 for (auto &BB : *F) { 1050 if (BB.getName() == "LOOP") { 1051 EXPECT_EQ(isGuaranteedNotToBePoison(A, nullptr, A, &DT), true) 1052 << "isGuaranteedNotToBePoison does not hold"; 1053 } 1054 } 1055 } 1056 1057 TEST_F(ValueTrackingTest, isGuaranteedNotToBeUndefOrPoison) { 1058 parseAssembly("declare void @f(i32 noundef)" 1059 "define void @test(i32 %x) {\n" 1060 " %A = bitcast i32 %x to i32\n" 1061 " call void @f(i32 noundef %x)\n" 1062 " ret void\n" 1063 "}\n"); 1064 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(A), true); 1065 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(UndefValue::get(IntegerType::get(Context, 8))), false); 1066 EXPECT_EQ(isGuaranteedNotToBeUndefOrPoison(PoisonValue::get(IntegerType::get(Context, 8))), false); 1067 EXPECT_EQ(isGuaranteedNotToBePoison(UndefValue::get(IntegerType::get(Context, 8))), true); 1068 EXPECT_EQ(isGuaranteedNotToBePoison(PoisonValue::get(IntegerType::get(Context, 8))), false); 1069 1070 Type *Int32Ty = Type::getInt32Ty(Context); 1071 Constant *CU = UndefValue::get(Int32Ty); 1072 Constant *CP = PoisonValue::get(Int32Ty); 1073 Constant *C1 = ConstantInt::get(Int32Ty, 1); 1074 Constant *C2 = ConstantInt::get(Int32Ty, 2); 1075 1076 { 1077 Constant *V1 = ConstantVector::get({C1, C2}); 1078 EXPECT_TRUE(isGuaranteedNotToBeUndefOrPoison(V1)); 1079 EXPECT_TRUE(isGuaranteedNotToBePoison(V1)); 1080 } 1081 1082 { 1083 Constant *V2 = ConstantVector::get({C1, CU}); 1084 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(V2)); 1085 EXPECT_TRUE(isGuaranteedNotToBePoison(V2)); 1086 } 1087 1088 { 1089 Constant *V3 = ConstantVector::get({C1, CP}); 1090 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(V3)); 1091 EXPECT_FALSE(isGuaranteedNotToBePoison(V3)); 1092 } 1093 } 1094 1095 TEST_F(ValueTrackingTest, isGuaranteedNotToBeUndefOrPoison_assume) { 1096 parseAssembly("declare i1 @f_i1()\n" 1097 "declare i32 @f_i32()\n" 1098 "declare void @llvm.assume(i1)\n" 1099 "define void @test() {\n" 1100 " %A = call i32 @f_i32()\n" 1101 " %cond = call i1 @f_i1()\n" 1102 " %CxtI = add i32 0, 0\n" 1103 " br i1 %cond, label %BB1, label %EXIT\n" 1104 "BB1:\n" 1105 " %CxtI2 = add i32 0, 0\n" 1106 " %cond2 = call i1 @f_i1()\n" 1107 " call void @llvm.assume(i1 true) [ \"noundef\"(i32 %A) ]\n" 1108 " br i1 %cond2, label %BB2, label %EXIT\n" 1109 "BB2:\n" 1110 " %CxtI3 = add i32 0, 0\n" 1111 " ret void\n" 1112 "EXIT:\n" 1113 " ret void\n" 1114 "}"); 1115 AssumptionCache AC(*F); 1116 DominatorTree DT(*F); 1117 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI, &DT)); 1118 EXPECT_FALSE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI2, &DT)); 1119 EXPECT_TRUE(isGuaranteedNotToBeUndefOrPoison(A, &AC, CxtI3, &DT)); 1120 } 1121 1122 TEST(ValueTracking, canCreatePoisonOrUndef) { 1123 std::string AsmHead = 1124 "@s = external dso_local global i32, align 1\n" 1125 "declare i32 @g(i32)\n" 1126 "declare {i32, i1} @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)\n" 1127 "declare {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)\n" 1128 "declare {i32, i1} @llvm.smul.with.overflow.i32(i32 %a, i32 %b)\n" 1129 "declare {i32, i1} @llvm.uadd.with.overflow.i32(i32 %a, i32 %b)\n" 1130 "declare {i32, i1} @llvm.usub.with.overflow.i32(i32 %a, i32 %b)\n" 1131 "declare {i32, i1} @llvm.umul.with.overflow.i32(i32 %a, i32 %b)\n" 1132 "define void @f(i32 %x, i32 %y, float %fx, float %fy, i1 %cond, " 1133 "<4 x i32> %vx, <4 x i32> %vx2, <vscale x 4 x i32> %svx, ptr %p) {\n"; 1134 std::string AsmTail = " ret void\n}"; 1135 // (can create poison?, can create undef?, IR instruction) 1136 SmallVector<std::pair<std::pair<bool, bool>, std::string>, 32> Data = { 1137 {{false, false}, "add i32 %x, %y"}, 1138 {{true, false}, "add nsw nuw i32 %x, %y"}, 1139 {{true, false}, "shl i32 %x, %y"}, 1140 {{true, false}, "shl <4 x i32> %vx, %vx2"}, 1141 {{true, false}, "shl nsw i32 %x, %y"}, 1142 {{true, false}, "shl nsw <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"}, 1143 {{false, false}, "shl i32 %x, 31"}, 1144 {{true, false}, "shl i32 %x, 32"}, 1145 {{false, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"}, 1146 {{true, false}, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"}, 1147 {{true, false}, "ashr i32 %x, %y"}, 1148 {{true, false}, "ashr exact i32 %x, %y"}, 1149 {{false, false}, "ashr i32 %x, 31"}, 1150 {{true, false}, "ashr exact i32 %x, 31"}, 1151 {{false, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"}, 1152 {{true, false}, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"}, 1153 {{true, false}, "ashr exact <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"}, 1154 {{true, false}, "lshr i32 %x, %y"}, 1155 {{true, false}, "lshr exact i32 %x, 31"}, 1156 {{false, false}, "udiv i32 %x, %y"}, 1157 {{true, false}, "udiv exact i32 %x, %y"}, 1158 {{false, false}, "getelementptr i8, ptr %p, i32 %x"}, 1159 {{true, false}, "getelementptr inbounds i8, ptr %p, i32 %x"}, 1160 {{true, false}, "fneg nnan float %fx"}, 1161 {{false, false}, "fneg float %fx"}, 1162 {{false, false}, "fadd float %fx, %fy"}, 1163 {{true, false}, "fadd nnan float %fx, %fy"}, 1164 {{false, false}, "urem i32 %x, %y"}, 1165 {{true, false}, "fptoui float %fx to i32"}, 1166 {{true, false}, "fptosi float %fx to i32"}, 1167 {{false, false}, "bitcast float %fx to i32"}, 1168 {{false, false}, "select i1 %cond, i32 %x, i32 %y"}, 1169 {{true, false}, "select nnan i1 %cond, float %fx, float %fy"}, 1170 {{true, false}, "extractelement <4 x i32> %vx, i32 %x"}, 1171 {{false, false}, "extractelement <4 x i32> %vx, i32 3"}, 1172 {{true, false}, "extractelement <vscale x 4 x i32> %svx, i32 4"}, 1173 {{true, false}, "insertelement <4 x i32> %vx, i32 %x, i32 %y"}, 1174 {{false, false}, "insertelement <4 x i32> %vx, i32 %x, i32 3"}, 1175 {{true, false}, "insertelement <vscale x 4 x i32> %svx, i32 %x, i32 4"}, 1176 {{false, false}, "freeze i32 %x"}, 1177 {{false, false}, 1178 "shufflevector <4 x i32> %vx, <4 x i32> %vx2, " 1179 "<4 x i32> <i32 0, i32 1, i32 2, i32 3>"}, 1180 {{false, true}, 1181 "shufflevector <4 x i32> %vx, <4 x i32> %vx2, " 1182 "<4 x i32> <i32 0, i32 1, i32 2, i32 undef>"}, 1183 {{false, true}, 1184 "shufflevector <vscale x 4 x i32> %svx, " 1185 "<vscale x 4 x i32> %svx, <vscale x 4 x i32> undef"}, 1186 {{true, false}, "call i32 @g(i32 %x)"}, 1187 {{false, false}, "call noundef i32 @g(i32 %x)"}, 1188 {{true, false}, "fcmp nnan oeq float %fx, %fy"}, 1189 {{false, false}, "fcmp oeq float %fx, %fy"}, 1190 {{true, false}, "ashr i32 %x, ptrtoint (ptr @s to i32)"}, 1191 {{false, false}, 1192 "call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)"}, 1193 {{false, false}, 1194 "call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %x, i32 %y)"}, 1195 {{false, false}, 1196 "call {i32, i1} @llvm.smul.with.overflow.i32(i32 %x, i32 %y)"}, 1197 {{false, false}, 1198 "call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)"}, 1199 {{false, false}, 1200 "call {i32, i1} @llvm.usub.with.overflow.i32(i32 %x, i32 %y)"}, 1201 {{false, false}, 1202 "call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 %y)"}}; 1203 1204 std::string AssemblyStr = AsmHead; 1205 for (auto &Itm : Data) 1206 AssemblyStr += Itm.second + "\n"; 1207 AssemblyStr += AsmTail; 1208 1209 LLVMContext Context; 1210 SMDiagnostic Error; 1211 auto M = parseAssemblyString(AssemblyStr, Error, Context); 1212 assert(M && "Bad assembly?"); 1213 1214 auto *F = M->getFunction("f"); 1215 assert(F && "Bad assembly?"); 1216 1217 auto &BB = F->getEntryBlock(); 1218 1219 int Index = 0; 1220 for (auto &I : BB) { 1221 if (isa<ReturnInst>(&I)) 1222 break; 1223 bool Poison = Data[Index].first.first; 1224 bool Undef = Data[Index].first.second; 1225 EXPECT_EQ(canCreatePoison(cast<Operator>(&I)), Poison) 1226 << "Incorrect answer of canCreatePoison at instruction " << Index 1227 << " = " << I; 1228 EXPECT_EQ(canCreateUndefOrPoison(cast<Operator>(&I)), Undef || Poison) 1229 << "Incorrect answer of canCreateUndef at instruction " << Index 1230 << " = " << I; 1231 Index++; 1232 } 1233 } 1234 1235 TEST_F(ValueTrackingTest, computePtrAlignment) { 1236 parseAssembly("declare i1 @f_i1()\n" 1237 "declare ptr @f_i8p()\n" 1238 "declare void @llvm.assume(i1)\n" 1239 "define void @test() {\n" 1240 " %A = call ptr @f_i8p()\n" 1241 " %cond = call i1 @f_i1()\n" 1242 " %CxtI = add i32 0, 0\n" 1243 " br i1 %cond, label %BB1, label %EXIT\n" 1244 "BB1:\n" 1245 " %CxtI2 = add i32 0, 0\n" 1246 " %cond2 = call i1 @f_i1()\n" 1247 " call void @llvm.assume(i1 true) [ \"align\"(ptr %A, i64 16) ]\n" 1248 " br i1 %cond2, label %BB2, label %EXIT\n" 1249 "BB2:\n" 1250 " %CxtI3 = add i32 0, 0\n" 1251 " ret void\n" 1252 "EXIT:\n" 1253 " ret void\n" 1254 "}"); 1255 AssumptionCache AC(*F); 1256 DominatorTree DT(*F); 1257 const DataLayout &DL = M->getDataLayout(); 1258 EXPECT_EQ(getKnownAlignment(A, DL, CxtI, &AC, &DT), Align(1)); 1259 EXPECT_EQ(getKnownAlignment(A, DL, CxtI2, &AC, &DT), Align(1)); 1260 EXPECT_EQ(getKnownAlignment(A, DL, CxtI3, &AC, &DT), Align(16)); 1261 } 1262 1263 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) { 1264 parseAssembly( 1265 "define i32 @test(i32 %a, i32 %b) {\n" 1266 " %ash = mul i32 %a, 8\n" 1267 " %aad = add i32 %ash, 7\n" 1268 " %aan = and i32 %aad, 4095\n" 1269 " %bsh = shl i32 %b, 4\n" 1270 " %bad = or i32 %bsh, 6\n" 1271 " %ban = and i32 %bad, 4095\n" 1272 " %A = mul i32 %aan, %ban\n" 1273 " ret i32 %A\n" 1274 "}\n"); 1275 expectKnownBits(/*zero*/ 4278190085u, /*one*/ 10u); 1276 } 1277 1278 TEST_F(ComputeKnownBitsTest, ComputeKnownMulBits) { 1279 parseAssembly( 1280 "define i32 @test(i32 %a, i32 %b) {\n" 1281 " %aa = shl i32 %a, 5\n" 1282 " %bb = shl i32 %b, 5\n" 1283 " %aaa = or i32 %aa, 24\n" 1284 " %bbb = or i32 %bb, 28\n" 1285 " %A = mul i32 %aaa, %bbb\n" 1286 " ret i32 %A\n" 1287 "}\n"); 1288 expectKnownBits(/*zero*/ 95u, /*one*/ 32u); 1289 } 1290 1291 TEST_F(ComputeKnownFPClassTest, SelectPos0) { 1292 parseAssembly( 1293 "define float @test(i1 %cond) {\n" 1294 " %A = select i1 %cond, float 0.0, float 0.0" 1295 " ret float %A\n" 1296 "}\n"); 1297 expectKnownFPClass(fcPosZero, false); 1298 } 1299 1300 TEST_F(ComputeKnownFPClassTest, SelectNeg0) { 1301 parseAssembly( 1302 "define float @test(i1 %cond) {\n" 1303 " %A = select i1 %cond, float -0.0, float -0.0" 1304 " ret float %A\n" 1305 "}\n"); 1306 expectKnownFPClass(fcNegZero, true); 1307 } 1308 1309 TEST_F(ComputeKnownFPClassTest, SelectPosOrNeg0) { 1310 parseAssembly( 1311 "define float @test(i1 %cond) {\n" 1312 " %A = select i1 %cond, float 0.0, float -0.0" 1313 " ret float %A\n" 1314 "}\n"); 1315 expectKnownFPClass(fcZero, std::nullopt); 1316 } 1317 1318 TEST_F(ComputeKnownFPClassTest, SelectPosInf) { 1319 parseAssembly( 1320 "define float @test(i1 %cond) {\n" 1321 " %A = select i1 %cond, float 0x7FF0000000000000, float 0x7FF0000000000000" 1322 " ret float %A\n" 1323 "}\n"); 1324 expectKnownFPClass(fcPosInf, false); 1325 } 1326 1327 TEST_F(ComputeKnownFPClassTest, SelectNegInf) { 1328 parseAssembly( 1329 "define float @test(i1 %cond) {\n" 1330 " %A = select i1 %cond, float 0xFFF0000000000000, float 0xFFF0000000000000" 1331 " ret float %A\n" 1332 "}\n"); 1333 expectKnownFPClass(fcNegInf, true); 1334 } 1335 1336 TEST_F(ComputeKnownFPClassTest, SelectPosOrNegInf) { 1337 parseAssembly( 1338 "define float @test(i1 %cond) {\n" 1339 " %A = select i1 %cond, float 0x7FF0000000000000, float 0xFFF0000000000000" 1340 " ret float %A\n" 1341 "}\n"); 1342 expectKnownFPClass(fcInf, std::nullopt); 1343 } 1344 1345 TEST_F(ComputeKnownFPClassTest, SelectNNaN) { 1346 parseAssembly( 1347 "define float @test(i1 %cond, float %arg0, float %arg1) {\n" 1348 " %A = select nnan i1 %cond, float %arg0, float %arg1" 1349 " ret float %A\n" 1350 "}\n"); 1351 expectKnownFPClass(~fcNan, std::nullopt); 1352 } 1353 1354 TEST_F(ComputeKnownFPClassTest, SelectNInf) { 1355 parseAssembly( 1356 "define float @test(i1 %cond, float %arg0, float %arg1) {\n" 1357 " %A = select ninf i1 %cond, float %arg0, float %arg1" 1358 " ret float %A\n" 1359 "}\n"); 1360 expectKnownFPClass(~fcInf, std::nullopt); 1361 } 1362 1363 TEST_F(ComputeKnownFPClassTest, SelectNNaNNInf) { 1364 parseAssembly( 1365 "define float @test(i1 %cond, float %arg0, float %arg1) {\n" 1366 " %A = select nnan ninf i1 %cond, float %arg0, float %arg1" 1367 " ret float %A\n" 1368 "}\n"); 1369 expectKnownFPClass(~(fcNan | fcInf), std::nullopt); 1370 } 1371 1372 TEST_F(ComputeKnownFPClassTest, SelectNoFPClassArgUnionAll) { 1373 parseAssembly( 1374 "define float @test(i1 %cond, float nofpclass(snan ninf nsub pzero pnorm) %arg0, float nofpclass(qnan nnorm nzero psub pinf) %arg1) {\n" 1375 " %A = select i1 %cond, float %arg0, float %arg1" 1376 " ret float %A\n" 1377 "}\n"); 1378 expectKnownFPClass(fcAllFlags, std::nullopt); 1379 } 1380 1381 TEST_F(ComputeKnownFPClassTest, SelectNoFPClassArgNoNan) { 1382 parseAssembly( 1383 "define float @test(i1 %cond, float nofpclass(nan) %arg0, float nofpclass(nan) %arg1) {\n" 1384 " %A = select i1 %cond, float %arg0, float %arg1" 1385 " ret float %A\n" 1386 "}\n"); 1387 expectKnownFPClass(~fcNan, std::nullopt); 1388 } 1389 1390 TEST_F(ComputeKnownFPClassTest, SelectNoFPClassArgNoPInf) { 1391 parseAssembly( 1392 "define float @test(i1 %cond, float nofpclass(inf) %arg0, float nofpclass(pinf) %arg1) {\n" 1393 " %A = select i1 %cond, float %arg0, float %arg1" 1394 " ret float %A\n" 1395 "}\n"); 1396 expectKnownFPClass(~fcPosInf, std::nullopt); 1397 } 1398 1399 TEST_F(ComputeKnownFPClassTest, SelectNoFPClassArgNoNInf) { 1400 parseAssembly( 1401 "define float @test(i1 %cond, float nofpclass(ninf) %arg0, float nofpclass(inf) %arg1) {\n" 1402 " %A = select i1 %cond, float %arg0, float %arg1" 1403 " ret float %A\n" 1404 "}\n"); 1405 expectKnownFPClass(~fcNegInf, std::nullopt); 1406 } 1407 1408 TEST_F(ComputeKnownFPClassTest, SelectNoFPClassCallSiteNoNan) { 1409 parseAssembly( 1410 "declare float @func()\n" 1411 "define float @test() {\n" 1412 " %A = call nofpclass(nan) float @func()\n" 1413 " ret float %A\n" 1414 "}\n"); 1415 expectKnownFPClass(~fcNan, std::nullopt); 1416 } 1417 1418 TEST_F(ComputeKnownFPClassTest, SelectNoFPClassCallSiteNoZeros) { 1419 parseAssembly( 1420 "declare float @func()\n" 1421 "define float @test() {\n" 1422 " %A = call nofpclass(zero) float @func()\n" 1423 " ret float %A\n" 1424 "}\n"); 1425 expectKnownFPClass(~fcZero, std::nullopt); 1426 } 1427 1428 TEST_F(ComputeKnownFPClassTest, SelectNoFPClassDeclarationNoNan) { 1429 parseAssembly( 1430 "declare nofpclass(nan) float @no_nans()\n" 1431 "define float @test() {\n" 1432 " %A = call float @no_nans()\n" 1433 " ret float %A\n" 1434 "}\n"); 1435 expectKnownFPClass(~fcNan, std::nullopt); 1436 } 1437 1438 // Check nofpclass + ninf works on a callsite 1439 TEST_F(ComputeKnownFPClassTest, SelectNoFPClassCallSiteNoZerosNInfFlags) { 1440 parseAssembly( 1441 "declare float @func()\n" 1442 "define float @test() {\n" 1443 " %A = call ninf nofpclass(zero) float @func()\n" 1444 " ret float %A\n" 1445 "}\n"); 1446 expectKnownFPClass(~(fcZero | fcInf), std::nullopt); 1447 } 1448 1449 TEST_F(ComputeKnownFPClassTest, FNegNInf) { 1450 parseAssembly( 1451 "define float @test(float %arg) {\n" 1452 " %A = fneg ninf float %arg" 1453 " ret float %A\n" 1454 "}\n"); 1455 expectKnownFPClass(~fcInf, std::nullopt); 1456 } 1457 1458 TEST_F(ComputeKnownFPClassTest, FabsUnknown) { 1459 parseAssembly( 1460 "declare float @llvm.fabs.f32(float)" 1461 "define float @test(float %arg) {\n" 1462 " %A = call float @llvm.fabs.f32(float %arg)" 1463 " ret float %A\n" 1464 "}\n"); 1465 expectKnownFPClass(fcPositive | fcNan, false); 1466 } 1467 1468 TEST_F(ComputeKnownFPClassTest, FNegFabsUnknown) { 1469 parseAssembly( 1470 "declare float @llvm.fabs.f32(float)" 1471 "define float @test(float %arg) {\n" 1472 " %fabs = call float @llvm.fabs.f32(float %arg)" 1473 " %A = fneg float %fabs" 1474 " ret float %A\n" 1475 "}\n"); 1476 expectKnownFPClass(fcNegative | fcNan, true); 1477 } 1478 1479 TEST_F(ComputeKnownFPClassTest, NegFabsNInf) { 1480 parseAssembly( 1481 "declare float @llvm.fabs.f32(float)" 1482 "define float @test(float %arg) {\n" 1483 " %fabs = call ninf float @llvm.fabs.f32(float %arg)" 1484 " %A = fneg float %fabs" 1485 " ret float %A\n" 1486 "}\n"); 1487 expectKnownFPClass((fcNegative & ~fcNegInf) | fcNan, true); 1488 } 1489 1490 TEST_F(ComputeKnownFPClassTest, FNegFabsNNaN) { 1491 parseAssembly( 1492 "declare float @llvm.fabs.f32(float)" 1493 "define float @test(float %arg) {\n" 1494 " %fabs = call nnan float @llvm.fabs.f32(float %arg)" 1495 " %A = fneg float %fabs" 1496 " ret float %A\n" 1497 "}\n"); 1498 expectKnownFPClass(fcNegative, true); 1499 } 1500 1501 TEST_F(ComputeKnownFPClassTest, CopySignNNanSrc0) { 1502 parseAssembly( 1503 "declare float @llvm.fabs.f32(float)\n" 1504 "declare float @llvm.copysign.f32(float, float)\n" 1505 "define float @test(float %arg0, float %arg1) {\n" 1506 " %fabs = call nnan float @llvm.fabs.f32(float %arg0)" 1507 " %A = call float @llvm.copysign.f32(float %fabs, float %arg1)" 1508 " ret float %A\n" 1509 "}\n"); 1510 expectKnownFPClass(~fcNan, std::nullopt); 1511 } 1512 1513 TEST_F(ComputeKnownFPClassTest, CopySignNInfSrc0_NegSign) { 1514 parseAssembly( 1515 "declare float @llvm.log.f32(float)\n" 1516 "declare float @llvm.copysign.f32(float, float)\n" 1517 "define float @test(float %arg0, float %arg1) {\n" 1518 " %ninf = call ninf float @llvm.log.f32(float %arg0)" 1519 " %A = call float @llvm.copysign.f32(float %ninf, float -1.0)" 1520 " ret float %A\n" 1521 "}\n"); 1522 expectKnownFPClass(fcNegFinite | fcNan, true); 1523 } 1524 1525 TEST_F(ComputeKnownFPClassTest, CopySignNInfSrc0_PosSign) { 1526 parseAssembly( 1527 "declare float @llvm.sqrt.f32(float)\n" 1528 "declare float @llvm.copysign.f32(float, float)\n" 1529 "define float @test(float %arg0, float %arg1) {\n" 1530 " %ninf = call ninf float @llvm.sqrt.f32(float %arg0)" 1531 " %A = call float @llvm.copysign.f32(float %ninf, float 1.0)" 1532 " ret float %A\n" 1533 "}\n"); 1534 expectKnownFPClass(fcPosFinite | fcNan, false); 1535 } 1536 1537 TEST_F(ComputeKnownFPClassTest, UIToFP) { 1538 parseAssembly( 1539 "define float @test(i32 %arg0, i16 %arg1) {\n" 1540 " %A = uitofp i32 %arg0 to float" 1541 " %A2 = uitofp i16 %arg1 to half" 1542 " ret float %A\n" 1543 "}\n"); 1544 expectKnownFPClass(fcPosFinite & ~fcSubnormal, false, A); 1545 expectKnownFPClass(fcPositive & ~fcSubnormal, false, A2); 1546 } 1547 1548 TEST_F(ComputeKnownFPClassTest, SIToFP) { 1549 parseAssembly( 1550 "define float @test(i32 %arg0, i16 %arg1, i17 %arg2) {\n" 1551 " %A = sitofp i32 %arg0 to float" 1552 " %A2 = sitofp i16 %arg1 to half" 1553 " %A3 = sitofp i17 %arg2 to half" 1554 " ret float %A\n" 1555 "}\n"); 1556 expectKnownFPClass(fcFinite & ~fcNegZero & ~fcSubnormal, std::nullopt, A); 1557 expectKnownFPClass(fcFinite & ~fcNegZero & ~fcSubnormal, std::nullopt, A2); 1558 expectKnownFPClass(~(fcNan | fcNegZero | fcSubnormal), std::nullopt, A3); 1559 } 1560 1561 TEST_F(ComputeKnownFPClassTest, FAdd) { 1562 parseAssembly( 1563 "define float @test(float nofpclass(nan inf) %nnan.ninf, float nofpclass(nan) %nnan, float nofpclass(qnan) %no.qnan, float %unknown) {\n" 1564 " %A = fadd float %nnan, %nnan.ninf" 1565 " %A2 = fadd float %nnan.ninf, %nnan" 1566 " %A3 = fadd float %nnan.ninf, %unknown" 1567 " %A4 = fadd float %nnan.ninf, %no.qnan" 1568 " %A5 = fadd float %nnan, %nnan" 1569 " ret float %A\n" 1570 "}\n"); 1571 expectKnownFPClass(fcFinite | fcInf, std::nullopt, A); 1572 expectKnownFPClass(fcFinite | fcInf, std::nullopt, A2); 1573 expectKnownFPClass(fcAllFlags, std::nullopt, A3); 1574 expectKnownFPClass(fcAllFlags, std::nullopt, A4); 1575 expectKnownFPClass(fcAllFlags, std::nullopt, A5); 1576 } 1577 1578 TEST_F(ComputeKnownFPClassTest, FSub) { 1579 parseAssembly( 1580 "define float @test(float nofpclass(nan inf) %nnan.ninf, float nofpclass(nan) %nnan, float nofpclass(qnan) %no.qnan, float %unknown) {\n" 1581 " %A = fsub float %nnan, %nnan.ninf" 1582 " %A2 = fsub float %nnan.ninf, %nnan" 1583 " %A3 = fsub float %nnan.ninf, %unknown" 1584 " %A4 = fsub float %nnan.ninf, %no.qnan" 1585 " %A5 = fsub float %nnan, %nnan" 1586 " ret float %A\n" 1587 "}\n"); 1588 expectKnownFPClass(fcFinite | fcInf, std::nullopt, A); 1589 expectKnownFPClass(fcFinite | fcInf, std::nullopt, A2); 1590 expectKnownFPClass(fcAllFlags, std::nullopt, A3); 1591 expectKnownFPClass(fcAllFlags, std::nullopt, A4); 1592 expectKnownFPClass(fcAllFlags, std::nullopt, A5); 1593 } 1594 1595 TEST_F(ComputeKnownFPClassTest, FMul) { 1596 parseAssembly( 1597 "define float @test(float nofpclass(nan inf) %nnan.ninf0, float nofpclass(nan inf) %nnan.ninf1, float nofpclass(nan) %nnan, float nofpclass(qnan) %no.qnan, float %unknown) {\n" 1598 " %A = fmul float %nnan.ninf0, %nnan.ninf1" 1599 " %A2 = fmul float %nnan.ninf0, %nnan" 1600 " %A3 = fmul float %nnan, %nnan.ninf0" 1601 " %A4 = fmul float %nnan.ninf0, %no.qnan" 1602 " %A5 = fmul float %nnan, %nnan" 1603 " ret float %A\n" 1604 "}\n"); 1605 expectKnownFPClass(fcFinite | fcInf, std::nullopt, A); 1606 expectKnownFPClass(fcAllFlags, std::nullopt, A2); 1607 expectKnownFPClass(fcAllFlags, std::nullopt, A3); 1608 expectKnownFPClass(fcAllFlags, std::nullopt, A4); 1609 expectKnownFPClass(fcPositive | fcNan, std::nullopt, A5); 1610 } 1611 1612 TEST_F(ComputeKnownFPClassTest, FMulNoZero) { 1613 parseAssembly( 1614 "define float @test(float nofpclass(zero) %no.zero, float nofpclass(zero nan) %no.zero.nan0, float nofpclass(zero nan) %no.zero.nan1, float nofpclass(nzero nan) %no.negzero.nan, float nofpclass(pzero nan) %no.poszero.nan, float nofpclass(inf nan) %no.inf.nan, float nofpclass(inf) %no.inf, float nofpclass(nan) %no.nan) {\n" 1615 " %A = fmul float %no.zero.nan0, %no.zero.nan1" 1616 " %A2 = fmul float %no.zero, %no.zero" 1617 " %A3 = fmul float %no.poszero.nan, %no.zero.nan0" 1618 " %A4 = fmul float %no.nan, %no.zero" 1619 " %A5 = fmul float %no.zero, %no.inf" 1620 " %A6 = fmul float %no.zero.nan0, %no.nan" 1621 " %A7 = fmul float %no.nan, %no.zero.nan0" 1622 " ret float %A\n" 1623 "}\n"); 1624 expectKnownFPClass(fcFinite | fcInf, std::nullopt, A); 1625 expectKnownFPClass(fcPositive | fcNan, std::nullopt, A2); 1626 expectKnownFPClass(fcAllFlags, std::nullopt, A3); 1627 expectKnownFPClass(fcAllFlags, std::nullopt, A4); 1628 expectKnownFPClass(fcAllFlags, std::nullopt, A5); 1629 expectKnownFPClass(fcAllFlags, std::nullopt, A6); 1630 expectKnownFPClass(fcAllFlags, std::nullopt, A7); 1631 } 1632 1633 TEST_F(ComputeKnownFPClassTest, Phi) { 1634 parseAssembly( 1635 "define float @test(i1 %cond, float nofpclass(nan inf) %arg0, float nofpclass(nan) %arg1) {\n" 1636 "entry:\n" 1637 " br i1 %cond, label %bb0, label %bb1\n" 1638 "bb0:\n" 1639 " br label %ret\n" 1640 "bb1:\n" 1641 " br label %ret\n" 1642 "ret:\n" 1643 " %A = phi float [ %arg0, %bb0 ], [ %arg1, %bb1 ]\n" 1644 " ret float %A\n" 1645 "}\n"); 1646 expectKnownFPClass(~fcNan, std::nullopt); 1647 } 1648 1649 TEST_F(ComputeKnownFPClassTest, PhiKnownSignFalse) { 1650 parseAssembly( 1651 "declare float @llvm.fabs.f32(float)" 1652 "define float @test(i1 %cond, float nofpclass(nan) %arg0, float nofpclass(nan) %arg1) {\n" 1653 "entry:\n" 1654 " br i1 %cond, label %bb0, label %bb1\n" 1655 "bb0:\n" 1656 " %fabs.arg0 = call float @llvm.fabs.f32(float %arg0)\n" 1657 " br label %ret\n" 1658 "bb1:\n" 1659 " %fabs.arg1 = call float @llvm.fabs.f32(float %arg1)\n" 1660 " br label %ret\n" 1661 "ret:\n" 1662 " %A = phi float [ %fabs.arg0, %bb0 ], [ %fabs.arg1, %bb1 ]\n" 1663 " ret float %A\n" 1664 "}\n"); 1665 expectKnownFPClass(fcPositive, false); 1666 } 1667 1668 TEST_F(ComputeKnownFPClassTest, PhiKnownSignTrue) { 1669 parseAssembly( 1670 "declare float @llvm.fabs.f32(float)" 1671 "define float @test(i1 %cond, float nofpclass(nan) %arg0, float %arg1) {\n" 1672 "entry:\n" 1673 " br i1 %cond, label %bb0, label %bb1\n" 1674 "bb0:\n" 1675 " %fabs.arg0 = call float @llvm.fabs.f32(float %arg0)\n" 1676 " %fneg.fabs.arg0 = fneg float %fabs.arg0\n" 1677 " br label %ret\n" 1678 "bb1:\n" 1679 " %fabs.arg1 = call float @llvm.fabs.f32(float %arg1)\n" 1680 " %fneg.fabs.arg1 = fneg float %fabs.arg1\n" 1681 " br label %ret\n" 1682 "ret:\n" 1683 " %A = phi float [ %fneg.fabs.arg0, %bb0 ], [ %fneg.fabs.arg1, %bb1 ]\n" 1684 " ret float %A\n" 1685 "}\n"); 1686 expectKnownFPClass(fcNegative | fcNan, true); 1687 } 1688 1689 TEST_F(ComputeKnownFPClassTest, UnreachablePhi) { 1690 parseAssembly( 1691 "define float @test(float %arg) {\n" 1692 "entry:\n" 1693 " ret float 0.0\n" 1694 "unreachable:\n" 1695 " %A = phi float\n" 1696 " ret float %A\n" 1697 "}\n"); 1698 expectKnownFPClass(fcAllFlags, std::nullopt); 1699 } 1700 1701 TEST_F(ComputeKnownFPClassTest, SelfPhiOnly) { 1702 parseAssembly( 1703 "define float @test(float %arg) {\n" 1704 "entry:\n" 1705 " ret float 0.0\n" 1706 "loop:\n" 1707 " %A = phi float [ %A, %loop ]\n" 1708 " br label %loop\n" 1709 "}\n"); 1710 expectKnownFPClass(fcAllFlags, std::nullopt); 1711 } 1712 1713 TEST_F(ComputeKnownFPClassTest, SelfPhiFirstArg) { 1714 parseAssembly( 1715 "define float @test(i1 %cond, float nofpclass(inf) %arg) {\n" 1716 "entry:\n" 1717 " br i1 %cond, label %loop, label %ret\n" 1718 "loop:\n" 1719 " %A = phi float [ %arg, %entry ], [ %A, %loop ]\n" 1720 " br label %loop\n" 1721 "ret:\n" 1722 " ret float %A" 1723 "}\n"); 1724 expectKnownFPClass(~fcInf, std::nullopt); 1725 } 1726 1727 TEST_F(ComputeKnownFPClassTest, SelfPhiSecondArg) { 1728 parseAssembly( 1729 "define float @test(i1 %cond, float nofpclass(inf) %arg) {\n" 1730 "entry:\n" 1731 " br i1 %cond, label %loop, label %ret\n" 1732 "loop:\n" 1733 " %A = phi float [ %A, %loop ], [ %arg, %entry ]\n" 1734 " br label %loop\n" 1735 "ret:\n" 1736 " ret float %A" 1737 "}\n"); 1738 expectKnownFPClass(~fcInf, std::nullopt); 1739 } 1740 1741 TEST_F(ComputeKnownFPClassTest, CannotBeOrderedLessThanZero) { 1742 parseAssembly("define float @test(float %arg) {\n" 1743 " %A = fmul float %arg, %arg" 1744 " ret float %A\n" 1745 "}\n"); 1746 1747 Type *FPTy = Type::getDoubleTy(M->getContext()); 1748 const DataLayout &DL = M->getDataLayout(); 1749 1750 EXPECT_TRUE( 1751 computeKnownFPClass(ConstantFP::getZero(FPTy, /*Negative=*/false), DL) 1752 .cannotBeOrderedLessThanZero()); 1753 EXPECT_TRUE( 1754 computeKnownFPClass(ConstantFP::getZero(FPTy, /*Negative=*/true), DL) 1755 .cannotBeOrderedLessThanZero()); 1756 1757 EXPECT_TRUE(computeKnownFPClass(ConstantFP::getInfinity(FPTy, false), DL) 1758 .cannotBeOrderedLessThanZero()); 1759 EXPECT_FALSE(computeKnownFPClass(ConstantFP::getInfinity(FPTy, true), DL) 1760 .cannotBeOrderedLessThanZero()); 1761 1762 EXPECT_TRUE(computeKnownFPClass(ConstantFP::get(FPTy, 1.0), DL) 1763 .cannotBeOrderedLessThanZero()); 1764 EXPECT_FALSE(computeKnownFPClass(ConstantFP::get(FPTy, -1.0), DL) 1765 .cannotBeOrderedLessThanZero()); 1766 1767 EXPECT_TRUE( 1768 computeKnownFPClass( 1769 ConstantFP::get(FPTy, APFloat::getSmallest(FPTy->getFltSemantics(), 1770 /*Negative=*/false)), 1771 DL) 1772 .cannotBeOrderedLessThanZero()); 1773 EXPECT_FALSE( 1774 computeKnownFPClass( 1775 ConstantFP::get(FPTy, APFloat::getSmallest(FPTy->getFltSemantics(), 1776 /*Negative=*/true)), 1777 DL) 1778 .cannotBeOrderedLessThanZero()); 1779 1780 EXPECT_TRUE( 1781 computeKnownFPClass(ConstantFP::getQNaN(FPTy, /*Negative=*/false), DL) 1782 .cannotBeOrderedLessThanZero()); 1783 EXPECT_TRUE( 1784 computeKnownFPClass(ConstantFP::getQNaN(FPTy, /*Negative=*/true), DL) 1785 .cannotBeOrderedLessThanZero()); 1786 EXPECT_TRUE( 1787 computeKnownFPClass(ConstantFP::getSNaN(FPTy, /*Negative=*/false), DL) 1788 .cannotBeOrderedLessThanZero()); 1789 EXPECT_TRUE( 1790 computeKnownFPClass(ConstantFP::getSNaN(FPTy, /*Negative=*/true), DL) 1791 .cannotBeOrderedLessThanZero()); 1792 } 1793 1794 TEST_F(ValueTrackingTest, isNonZeroRecurrence) { 1795 parseAssembly(R"( 1796 define i1 @test(i8 %n, i8 %r) { 1797 entry: 1798 br label %loop 1799 loop: 1800 %p = phi i8 [ -1, %entry ], [ %next, %loop ] 1801 %next = add nsw i8 %p, -1 1802 %cmp1 = icmp eq i8 %p, %n 1803 br i1 %cmp1, label %exit, label %loop 1804 exit: 1805 %A = or i8 %p, %r 1806 %CxtI = icmp eq i8 %A, 0 1807 ret i1 %CxtI 1808 } 1809 )"); 1810 const DataLayout &DL = M->getDataLayout(); 1811 AssumptionCache AC(*F); 1812 EXPECT_TRUE(isKnownNonZero(A, DL, 0, &AC, CxtI)); 1813 } 1814 1815 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond) { 1816 parseAssembly(R"( 1817 declare ptr @f_i8() 1818 define void @test(i1 %c) { 1819 %A = call ptr @f_i8() 1820 %B = call ptr @f_i8() 1821 %c1 = icmp ne ptr %A, null 1822 %cond = and i1 %c1, %c 1823 br i1 %cond, label %T, label %Q 1824 T: 1825 %CxtI = add i32 0, 0 1826 ret void 1827 Q: 1828 %CxtI2 = add i32 0, 0 1829 ret void 1830 } 1831 )"); 1832 AssumptionCache AC(*F); 1833 DominatorTree DT(*F); 1834 const DataLayout &DL = M->getDataLayout(); 1835 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true); 1836 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false); 1837 } 1838 1839 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond2) { 1840 parseAssembly(R"( 1841 declare ptr @f_i8() 1842 define void @test(i1 %c) { 1843 %A = call ptr @f_i8() 1844 %B = call ptr @f_i8() 1845 %c1 = icmp ne ptr %A, null 1846 %cond = select i1 %c, i1 %c1, i1 false 1847 br i1 %cond, label %T, label %Q 1848 T: 1849 %CxtI = add i32 0, 0 1850 ret void 1851 Q: 1852 %CxtI2 = add i32 0, 0 1853 ret void 1854 } 1855 )"); 1856 AssumptionCache AC(*F); 1857 DominatorTree DT(*F); 1858 const DataLayout &DL = M->getDataLayout(); 1859 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true); 1860 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false); 1861 } 1862 1863 TEST_F(ValueTrackingTest, IsImpliedConditionAnd) { 1864 parseAssembly(R"( 1865 define void @test(i32 %x, i32 %y) { 1866 %c1 = icmp ult i32 %x, 10 1867 %c2 = icmp ult i32 %y, 15 1868 %A = and i1 %c1, %c2 1869 ; x < 10 /\ y < 15 1870 %A2 = icmp ult i32 %x, 20 1871 %A3 = icmp uge i32 %y, 20 1872 %A4 = icmp ult i32 %x, 5 1873 ret void 1874 } 1875 )"); 1876 const DataLayout &DL = M->getDataLayout(); 1877 EXPECT_EQ(isImpliedCondition(A, A2, DL), true); 1878 EXPECT_EQ(isImpliedCondition(A, A3, DL), false); 1879 EXPECT_EQ(isImpliedCondition(A, A4, DL), std::nullopt); 1880 } 1881 1882 TEST_F(ValueTrackingTest, IsImpliedConditionAnd2) { 1883 parseAssembly(R"( 1884 define void @test(i32 %x, i32 %y) { 1885 %c1 = icmp ult i32 %x, 10 1886 %c2 = icmp ult i32 %y, 15 1887 %A = select i1 %c1, i1 %c2, i1 false 1888 ; x < 10 /\ y < 15 1889 %A2 = icmp ult i32 %x, 20 1890 %A3 = icmp uge i32 %y, 20 1891 %A4 = icmp ult i32 %x, 5 1892 ret void 1893 } 1894 )"); 1895 const DataLayout &DL = M->getDataLayout(); 1896 EXPECT_EQ(isImpliedCondition(A, A2, DL), true); 1897 EXPECT_EQ(isImpliedCondition(A, A3, DL), false); 1898 EXPECT_EQ(isImpliedCondition(A, A4, DL), std::nullopt); 1899 } 1900 1901 TEST_F(ValueTrackingTest, IsImpliedConditionAndVec) { 1902 parseAssembly(R"( 1903 define void @test(<2 x i8> %x, <2 x i8> %y) { 1904 %A = icmp ult <2 x i8> %x, %y 1905 %A2 = icmp ule <2 x i8> %x, %y 1906 ret void 1907 } 1908 )"); 1909 const DataLayout &DL = M->getDataLayout(); 1910 EXPECT_EQ(isImpliedCondition(A, A2, DL), true); 1911 } 1912 1913 TEST_F(ValueTrackingTest, IsImpliedConditionOr) { 1914 parseAssembly(R"( 1915 define void @test(i32 %x, i32 %y) { 1916 %c1 = icmp ult i32 %x, 10 1917 %c2 = icmp ult i32 %y, 15 1918 %A = or i1 %c1, %c2 ; negated 1919 ; x >= 10 /\ y >= 15 1920 %A2 = icmp ult i32 %x, 5 1921 %A3 = icmp uge i32 %y, 10 1922 %A4 = icmp ult i32 %x, 15 1923 ret void 1924 } 1925 )"); 1926 const DataLayout &DL = M->getDataLayout(); 1927 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false); 1928 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true); 1929 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), std::nullopt); 1930 } 1931 1932 TEST_F(ValueTrackingTest, IsImpliedConditionOr2) { 1933 parseAssembly(R"( 1934 define void @test(i32 %x, i32 %y) { 1935 %c1 = icmp ult i32 %x, 10 1936 %c2 = icmp ult i32 %y, 15 1937 %A = select i1 %c1, i1 true, i1 %c2 ; negated 1938 ; x >= 10 /\ y >= 15 1939 %A2 = icmp ult i32 %x, 5 1940 %A3 = icmp uge i32 %y, 10 1941 %A4 = icmp ult i32 %x, 15 1942 ret void 1943 } 1944 )"); 1945 const DataLayout &DL = M->getDataLayout(); 1946 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false); 1947 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true); 1948 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), std::nullopt); 1949 } 1950 1951 TEST_F(ComputeKnownBitsTest, KnownNonZeroShift) { 1952 // %q is known nonzero without known bits. 1953 // Because %q is nonzero, %A[0] is known to be zero. 1954 parseAssembly( 1955 "define i8 @test(i8 %p, ptr %pq) {\n" 1956 " %q = load i8, ptr %pq, !range !0\n" 1957 " %A = shl i8 %p, %q\n" 1958 " ret i8 %A\n" 1959 "}\n" 1960 "!0 = !{ i8 1, i8 5 }\n"); 1961 expectKnownBits(/*zero*/ 1u, /*one*/ 0u); 1962 } 1963 1964 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) { 1965 // fshl(....1111....0000, 00..1111........, 6) 1966 // = 11....000000..11 1967 parseAssembly( 1968 "define i16 @test(i16 %a, i16 %b) {\n" 1969 " %aa = shl i16 %a, 4\n" 1970 " %bb = lshr i16 %b, 2\n" 1971 " %aaa = or i16 %aa, 3840\n" 1972 " %bbb = or i16 %bb, 3840\n" 1973 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n" 1974 " ret i16 %A\n" 1975 "}\n" 1976 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n"); 1977 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u); 1978 } 1979 1980 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) { 1981 // fshr(....1111....0000, 00..1111........, 26) 1982 // = 11....000000..11 1983 parseAssembly( 1984 "define i16 @test(i16 %a, i16 %b) {\n" 1985 " %aa = shl i16 %a, 4\n" 1986 " %bb = lshr i16 %b, 2\n" 1987 " %aaa = or i16 %aa, 3840\n" 1988 " %bbb = or i16 %bb, 3840\n" 1989 " %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n" 1990 " ret i16 %A\n" 1991 "}\n" 1992 "declare i16 @llvm.fshr.i16(i16, i16, i16)\n"); 1993 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u); 1994 } 1995 1996 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) { 1997 // fshl(....1111....0000, 00..1111........, 0) 1998 // = ....1111....0000 1999 parseAssembly( 2000 "define i16 @test(i16 %a, i16 %b) {\n" 2001 " %aa = shl i16 %a, 4\n" 2002 " %bb = lshr i16 %b, 2\n" 2003 " %aaa = or i16 %aa, 3840\n" 2004 " %bbb = or i16 %bb, 3840\n" 2005 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n" 2006 " ret i16 %A\n" 2007 "}\n" 2008 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n"); 2009 expectKnownBits(/*zero*/ 15u, /*one*/ 3840u); 2010 } 2011 2012 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) { 2013 // uadd.sat(1111...1, ........) 2014 // = 1111.... 2015 parseAssembly( 2016 "define i8 @test(i8 %a, i8 %b) {\n" 2017 " %aa = or i8 %a, 241\n" 2018 " %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n" 2019 " ret i8 %A\n" 2020 "}\n" 2021 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n"); 2022 expectKnownBits(/*zero*/ 0u, /*one*/ 240u); 2023 } 2024 2025 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) { 2026 // uadd.sat(00...011, .1...110) 2027 // = .......1 2028 parseAssembly( 2029 "define i8 @test(i8 %a, i8 %b) {\n" 2030 " %aa = or i8 %a, 3\n" 2031 " %aaa = and i8 %aa, 59\n" 2032 " %bb = or i8 %b, 70\n" 2033 " %bbb = and i8 %bb, 254\n" 2034 " %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n" 2035 " ret i8 %A\n" 2036 "}\n" 2037 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n"); 2038 expectKnownBits(/*zero*/ 0u, /*one*/ 1u); 2039 } 2040 2041 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) { 2042 // usub.sat(0000...0, ........) 2043 // = 0000.... 2044 parseAssembly( 2045 "define i8 @test(i8 %a, i8 %b) {\n" 2046 " %aa = and i8 %a, 14\n" 2047 " %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n" 2048 " ret i8 %A\n" 2049 "}\n" 2050 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 2051 expectKnownBits(/*zero*/ 240u, /*one*/ 0u); 2052 } 2053 2054 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) { 2055 // usub.sat(........, 1111...1) 2056 // = 0000.... 2057 parseAssembly( 2058 "define i8 @test(i8 %a, i8 %b) {\n" 2059 " %bb = or i8 %a, 241\n" 2060 " %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n" 2061 " ret i8 %A\n" 2062 "}\n" 2063 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 2064 expectKnownBits(/*zero*/ 240u, /*one*/ 0u); 2065 } 2066 2067 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) { 2068 // usub.sat(11...011, .1...110) 2069 // = ......0. 2070 parseAssembly( 2071 "define i8 @test(i8 %a, i8 %b) {\n" 2072 " %aa = or i8 %a, 195\n" 2073 " %aaa = and i8 %aa, 251\n" 2074 " %bb = or i8 %b, 70\n" 2075 " %bbb = and i8 %bb, 254\n" 2076 " %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n" 2077 " ret i8 %A\n" 2078 "}\n" 2079 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 2080 expectKnownBits(/*zero*/ 2u, /*one*/ 0u); 2081 } 2082 2083 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntTrunc) { 2084 // ptrtoint truncates the pointer type. 2085 parseAssembly( 2086 "define void @test(ptr %p) {\n" 2087 " %A = load ptr, ptr %p\n" 2088 " %i = ptrtoint ptr %A to i32\n" 2089 " %m = and i32 %i, 31\n" 2090 " %c = icmp eq i32 %m, 0\n" 2091 " call void @llvm.assume(i1 %c)\n" 2092 " ret void\n" 2093 "}\n" 2094 "declare void @llvm.assume(i1)\n"); 2095 AssumptionCache AC(*F); 2096 KnownBits Known = computeKnownBits( 2097 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator()); 2098 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 2099 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2100 } 2101 2102 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntZext) { 2103 // ptrtoint zero extends the pointer type. 2104 parseAssembly( 2105 "define void @test(ptr %p) {\n" 2106 " %A = load ptr, ptr %p\n" 2107 " %i = ptrtoint ptr %A to i128\n" 2108 " %m = and i128 %i, 31\n" 2109 " %c = icmp eq i128 %m, 0\n" 2110 " call void @llvm.assume(i1 %c)\n" 2111 " ret void\n" 2112 "}\n" 2113 "declare void @llvm.assume(i1)\n"); 2114 AssumptionCache AC(*F); 2115 KnownBits Known = computeKnownBits( 2116 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator()); 2117 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 2118 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2119 } 2120 2121 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsFreeze) { 2122 parseAssembly("define void @test() {\n" 2123 " %m = call i32 @any_num()\n" 2124 " %A = freeze i32 %m\n" 2125 " %n = and i32 %m, 31\n" 2126 " %c = icmp eq i32 %n, 0\n" 2127 " call void @llvm.assume(i1 %c)\n" 2128 " ret void\n" 2129 "}\n" 2130 "declare void @llvm.assume(i1)\n" 2131 "declare i32 @any_num()\n"); 2132 AssumptionCache AC(*F); 2133 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2134 F->front().getTerminator()); 2135 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 2136 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2137 } 2138 2139 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRange) { 2140 parseAssembly("define void @test(ptr %p) {\n" 2141 " %A = load i64, ptr %p, !range !{i64 64, i64 65536}\n" 2142 " %APlus512 = add i64 %A, 512\n" 2143 " %c = icmp ugt i64 %APlus512, 523\n" 2144 " call void @llvm.assume(i1 %c)\n" 2145 " ret void\n" 2146 "}\n" 2147 "declare void @llvm.assume(i1)\n"); 2148 AssumptionCache AC(*F); 2149 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2150 F->front().getTerminator()); 2151 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1)); 2152 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2153 Instruction &APlus512 = findInstructionByName(F, "APlus512"); 2154 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC, 2155 F->front().getTerminator()); 2156 // We know of one less zero because 512 may have produced a 1 that 2157 // got carried all the way to the first trailing zero. 2158 EXPECT_EQ(Known.Zero.getZExtValue(), (~(65536llu - 1)) << 1); 2159 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2160 // The known range is not precise given computeKnownBits works 2161 // with the masks of zeros and ones, not the ranges. 2162 EXPECT_EQ(Known.getMinValue(), 0u); 2163 EXPECT_EQ(Known.getMaxValue(), 131071); 2164 } 2165 2166 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsUnknownVScale) { 2167 Module M("", Context); 2168 IRBuilder<> Builder(Context); 2169 Function *TheFn = 2170 Intrinsic::getDeclaration(&M, Intrinsic::vscale, {Builder.getInt32Ty()}); 2171 CallInst *CI = Builder.CreateCall(TheFn, {}, {}, ""); 2172 2173 KnownBits Known = computeKnownBits(CI, M.getDataLayout(), /* Depth */ 0); 2174 // There is no parent function so we cannot look up the vscale_range 2175 // attribute to determine the number of bits. 2176 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2177 EXPECT_EQ(Known.Zero.getZExtValue(), 0u); 2178 2179 BasicBlock *BB = BasicBlock::Create(Context); 2180 CI->insertInto(BB, BB->end()); 2181 Known = computeKnownBits(CI, M.getDataLayout(), /* Depth */ 0); 2182 // There is no parent function so we cannot look up the vscale_range 2183 // attribute to determine the number of bits. 2184 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2185 EXPECT_EQ(Known.Zero.getZExtValue(), 0u); 2186 2187 CI->removeFromParent(); 2188 delete CI; 2189 delete BB; 2190 } 2191 2192 // 512 + [32, 64) doesn't produce overlapping bits. 2193 // Make sure we get all the individual bits properly. 2194 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRangeNoOverlap) { 2195 parseAssembly("define void @test(ptr %p) {\n" 2196 " %A = load i64, ptr %p, !range !{i64 32, i64 64}\n" 2197 " %APlus512 = add i64 %A, 512\n" 2198 " %c = icmp ugt i64 %APlus512, 523\n" 2199 " call void @llvm.assume(i1 %c)\n" 2200 " ret void\n" 2201 "}\n" 2202 "declare void @llvm.assume(i1)\n"); 2203 AssumptionCache AC(*F); 2204 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2205 F->front().getTerminator()); 2206 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1)); 2207 EXPECT_EQ(Known.One.getZExtValue(), 32u); 2208 Instruction &APlus512 = findInstructionByName(F, "APlus512"); 2209 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC, 2210 F->front().getTerminator()); 2211 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1)); 2212 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u); 2213 // The known range is not precise given computeKnownBits works 2214 // with the masks of zeros and ones, not the ranges. 2215 EXPECT_EQ(Known.getMinValue(), 544); 2216 EXPECT_EQ(Known.getMaxValue(), 575); 2217 } 2218 2219 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRange) { 2220 parseAssembly( 2221 "define void @test(ptr %p) {\n" 2222 " %A = load i64, ptr %p, !range !{i64 64, i64 65536}\n" 2223 " %APtr = inttoptr i64 %A to float*" 2224 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n" 2225 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n" 2226 " call void @llvm.assume(i1 %c)\n" 2227 " ret void\n" 2228 "}\n" 2229 "declare void @llvm.assume(i1)\n"); 2230 AssumptionCache AC(*F); 2231 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2232 F->front().getTerminator()); 2233 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1)); 2234 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2235 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512"); 2236 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC, 2237 F->front().getTerminator()); 2238 // We know of one less zero because 512 may have produced a 1 that 2239 // got carried all the way to the first trailing zero. 2240 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1) << 1); 2241 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2242 // The known range is not precise given computeKnownBits works 2243 // with the masks of zeros and ones, not the ranges. 2244 EXPECT_EQ(Known.getMinValue(), 0u); 2245 EXPECT_EQ(Known.getMaxValue(), 131071); 2246 } 2247 2248 // 4*128 + [32, 64) doesn't produce overlapping bits. 2249 // Make sure we get all the individual bits properly. 2250 // This test is useful to check that we account for the scaling factor 2251 // in the gep. Indeed, gep float, [32,64), 128 is not 128 + [32,64). 2252 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRangeNoOverlap) { 2253 parseAssembly( 2254 "define void @test(ptr %p) {\n" 2255 " %A = load i64, ptr %p, !range !{i64 32, i64 64}\n" 2256 " %APtr = inttoptr i64 %A to float*" 2257 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n" 2258 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n" 2259 " call void @llvm.assume(i1 %c)\n" 2260 " ret void\n" 2261 "}\n" 2262 "declare void @llvm.assume(i1)\n"); 2263 AssumptionCache AC(*F); 2264 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2265 F->front().getTerminator()); 2266 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1)); 2267 EXPECT_EQ(Known.One.getZExtValue(), 32u); 2268 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512"); 2269 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC, 2270 F->front().getTerminator()); 2271 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1)); 2272 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u); 2273 // The known range is not precise given computeKnownBits works 2274 // with the masks of zeros and ones, not the ranges. 2275 EXPECT_EQ(Known.getMinValue(), 544); 2276 EXPECT_EQ(Known.getMaxValue(), 575); 2277 } 2278 2279 TEST_F(ValueTrackingTest, HaveNoCommonBitsSet) { 2280 { 2281 // Check for an inverted mask: (X & ~M) op (Y & M). 2282 auto M = parseModule(R"( 2283 define i32 @test(i32 %X, i32 %Y, i32 %M) { 2284 %1 = xor i32 %M, -1 2285 %LHS = and i32 %1, %X 2286 %RHS = and i32 %Y, %M 2287 %Ret = add i32 %LHS, %RHS 2288 ret i32 %Ret 2289 })"); 2290 2291 auto *F = M->getFunction("test"); 2292 auto *LHS = findInstructionByNameOrNull(F, "LHS"); 2293 auto *RHS = findInstructionByNameOrNull(F, "RHS"); 2294 2295 const DataLayout &DL = M->getDataLayout(); 2296 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL)); 2297 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL)); 2298 } 2299 { 2300 // Check for (A & B) and ~(A | B) 2301 auto M = parseModule(R"( 2302 define void @test(i32 %A, i32 %B) { 2303 %LHS = and i32 %A, %B 2304 %or = or i32 %A, %B 2305 %RHS = xor i32 %or, -1 2306 2307 %LHS2 = and i32 %B, %A 2308 %or2 = or i32 %A, %B 2309 %RHS2 = xor i32 %or2, -1 2310 2311 ret void 2312 })"); 2313 2314 auto *F = M->getFunction("test"); 2315 const DataLayout &DL = M->getDataLayout(); 2316 2317 auto *LHS = findInstructionByNameOrNull(F, "LHS"); 2318 auto *RHS = findInstructionByNameOrNull(F, "RHS"); 2319 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL)); 2320 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL)); 2321 2322 auto *LHS2 = findInstructionByNameOrNull(F, "LHS2"); 2323 auto *RHS2 = findInstructionByNameOrNull(F, "RHS2"); 2324 EXPECT_TRUE(haveNoCommonBitsSet(LHS2, RHS2, DL)); 2325 EXPECT_TRUE(haveNoCommonBitsSet(RHS2, LHS2, DL)); 2326 } 2327 { 2328 // Check for (A & B) and ~(A | B) in vector version 2329 auto M = parseModule(R"( 2330 define void @test(<2 x i32> %A, <2 x i32> %B) { 2331 %LHS = and <2 x i32> %A, %B 2332 %or = or <2 x i32> %A, %B 2333 %RHS = xor <2 x i32> %or, <i32 -1, i32 -1> 2334 2335 %LHS2 = and <2 x i32> %B, %A 2336 %or2 = or <2 x i32> %A, %B 2337 %RHS2 = xor <2 x i32> %or2, <i32 -1, i32 -1> 2338 2339 ret void 2340 })"); 2341 2342 auto *F = M->getFunction("test"); 2343 const DataLayout &DL = M->getDataLayout(); 2344 2345 auto *LHS = findInstructionByNameOrNull(F, "LHS"); 2346 auto *RHS = findInstructionByNameOrNull(F, "RHS"); 2347 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL)); 2348 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL)); 2349 2350 auto *LHS2 = findInstructionByNameOrNull(F, "LHS2"); 2351 auto *RHS2 = findInstructionByNameOrNull(F, "RHS2"); 2352 EXPECT_TRUE(haveNoCommonBitsSet(LHS2, RHS2, DL)); 2353 EXPECT_TRUE(haveNoCommonBitsSet(RHS2, LHS2, DL)); 2354 } 2355 } 2356 2357 class IsBytewiseValueTest : public ValueTrackingTest, 2358 public ::testing::WithParamInterface< 2359 std::pair<const char *, const char *>> { 2360 protected: 2361 }; 2362 2363 const std::pair<const char *, const char *> IsBytewiseValueTests[] = { 2364 { 2365 "i8 0", 2366 "i48* null", 2367 }, 2368 { 2369 "i8 undef", 2370 "i48* undef", 2371 }, 2372 { 2373 "i8 0", 2374 "i8 zeroinitializer", 2375 }, 2376 { 2377 "i8 0", 2378 "i8 0", 2379 }, 2380 { 2381 "i8 -86", 2382 "i8 -86", 2383 }, 2384 { 2385 "i8 -1", 2386 "i8 -1", 2387 }, 2388 { 2389 "i8 undef", 2390 "i16 undef", 2391 }, 2392 { 2393 "i8 0", 2394 "i16 0", 2395 }, 2396 { 2397 "", 2398 "i16 7", 2399 }, 2400 { 2401 "i8 -86", 2402 "i16 -21846", 2403 }, 2404 { 2405 "i8 -1", 2406 "i16 -1", 2407 }, 2408 { 2409 "i8 0", 2410 "i48 0", 2411 }, 2412 { 2413 "i8 -1", 2414 "i48 -1", 2415 }, 2416 { 2417 "i8 0", 2418 "i49 0", 2419 }, 2420 { 2421 "", 2422 "i49 -1", 2423 }, 2424 { 2425 "i8 0", 2426 "half 0xH0000", 2427 }, 2428 { 2429 "i8 -85", 2430 "half 0xHABAB", 2431 }, 2432 { 2433 "i8 0", 2434 "float 0.0", 2435 }, 2436 { 2437 "i8 -1", 2438 "float 0xFFFFFFFFE0000000", 2439 }, 2440 { 2441 "i8 0", 2442 "double 0.0", 2443 }, 2444 { 2445 "i8 -15", 2446 "double 0xF1F1F1F1F1F1F1F1", 2447 }, 2448 { 2449 "i8 undef", 2450 "i16* undef", 2451 }, 2452 { 2453 "i8 0", 2454 "i16* inttoptr (i64 0 to i16*)", 2455 }, 2456 { 2457 "i8 -1", 2458 "i16* inttoptr (i64 -1 to i16*)", 2459 }, 2460 { 2461 "i8 -86", 2462 "i16* inttoptr (i64 -6148914691236517206 to i16*)", 2463 }, 2464 { 2465 "", 2466 "i16* inttoptr (i48 -1 to i16*)", 2467 }, 2468 { 2469 "i8 -1", 2470 "i16* inttoptr (i96 -1 to i16*)", 2471 }, 2472 { 2473 "i8 undef", 2474 "[0 x i8] zeroinitializer", 2475 }, 2476 { 2477 "i8 undef", 2478 "[0 x i8] undef", 2479 }, 2480 { 2481 "i8 undef", 2482 "[5 x [0 x i8]] zeroinitializer", 2483 }, 2484 { 2485 "i8 undef", 2486 "[5 x [0 x i8]] undef", 2487 }, 2488 { 2489 "i8 0", 2490 "[6 x i8] zeroinitializer", 2491 }, 2492 { 2493 "i8 undef", 2494 "[6 x i8] undef", 2495 }, 2496 { 2497 "i8 1", 2498 "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]", 2499 }, 2500 { 2501 "", 2502 "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]", 2503 }, 2504 { 2505 "i8 -1", 2506 "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]", 2507 }, 2508 { 2509 "", 2510 "[4 x i8] [i8 1, i8 2, i8 1, i8 1]", 2511 }, 2512 { 2513 "i8 1", 2514 "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]", 2515 }, 2516 { 2517 "i8 0", 2518 "<6 x i8> zeroinitializer", 2519 }, 2520 { 2521 "i8 undef", 2522 "<6 x i8> undef", 2523 }, 2524 { 2525 "i8 1", 2526 "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>", 2527 }, 2528 { 2529 "", 2530 "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>", 2531 }, 2532 { 2533 "i8 -1", 2534 "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>", 2535 }, 2536 { 2537 "", 2538 "<4 x i8> <i8 1, i8 1, i8 2, i8 1>", 2539 }, 2540 { 2541 "i8 5", 2542 "<2 x i8> < i8 5, i8 undef >", 2543 }, 2544 { 2545 "i8 0", 2546 "[2 x [2 x i16]] zeroinitializer", 2547 }, 2548 { 2549 "i8 undef", 2550 "[2 x [2 x i16]] undef", 2551 }, 2552 { 2553 "i8 -86", 2554 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], " 2555 "[2 x i16] [i16 -21846, i16 -21846]]", 2556 }, 2557 { 2558 "", 2559 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], " 2560 "[2 x i16] [i16 -21836, i16 -21846]]", 2561 }, 2562 { 2563 "i8 undef", 2564 "{ } zeroinitializer", 2565 }, 2566 { 2567 "i8 undef", 2568 "{ } undef", 2569 }, 2570 { 2571 "i8 undef", 2572 "{ {}, {} } zeroinitializer", 2573 }, 2574 { 2575 "i8 undef", 2576 "{ {}, {} } undef", 2577 }, 2578 { 2579 "i8 0", 2580 "{i8, i64, i16*} zeroinitializer", 2581 }, 2582 { 2583 "i8 undef", 2584 "{i8, i64, i16*} undef", 2585 }, 2586 { 2587 "i8 -86", 2588 "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}", 2589 }, 2590 { 2591 "", 2592 "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}", 2593 }, 2594 }; 2595 2596 INSTANTIATE_TEST_SUITE_P(IsBytewiseValueParamTests, IsBytewiseValueTest, 2597 ::testing::ValuesIn(IsBytewiseValueTests)); 2598 2599 TEST_P(IsBytewiseValueTest, IsBytewiseValue) { 2600 auto M = parseModule(std::string("@test = global ") + GetParam().second); 2601 GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test")); 2602 Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout()); 2603 std::string Buff; 2604 raw_string_ostream S(Buff); 2605 if (Actual) 2606 S << *Actual; 2607 EXPECT_EQ(GetParam().first, S.str()); 2608 } 2609 2610 TEST_F(ValueTrackingTest, ComputeConstantRange) { 2611 { 2612 // Assumptions: 2613 // * stride >= 5 2614 // * stride < 10 2615 // 2616 // stride = [5, 10) 2617 auto M = parseModule(R"( 2618 declare void @llvm.assume(i1) 2619 2620 define i32 @test(i32 %stride) { 2621 %gt = icmp uge i32 %stride, 5 2622 call void @llvm.assume(i1 %gt) 2623 %lt = icmp ult i32 %stride, 10 2624 call void @llvm.assume(i1 %lt) 2625 %stride.plus.one = add nsw nuw i32 %stride, 1 2626 ret i32 %stride.plus.one 2627 })"); 2628 Function *F = M->getFunction("test"); 2629 2630 AssumptionCache AC(*F); 2631 Value *Stride = &*F->arg_begin(); 2632 ConstantRange CR1 = computeConstantRange(Stride, false, true, &AC, nullptr); 2633 EXPECT_TRUE(CR1.isFullSet()); 2634 2635 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2636 ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I); 2637 EXPECT_EQ(5, CR2.getLower()); 2638 EXPECT_EQ(10, CR2.getUpper()); 2639 } 2640 2641 { 2642 // Assumptions: 2643 // * stride >= 5 2644 // * stride < 200 2645 // * stride == 99 2646 // 2647 // stride = [99, 100) 2648 auto M = parseModule(R"( 2649 declare void @llvm.assume(i1) 2650 2651 define i32 @test(i32 %stride) { 2652 %gt = icmp uge i32 %stride, 5 2653 call void @llvm.assume(i1 %gt) 2654 %lt = icmp ult i32 %stride, 200 2655 call void @llvm.assume(i1 %lt) 2656 %eq = icmp eq i32 %stride, 99 2657 call void @llvm.assume(i1 %eq) 2658 %stride.plus.one = add nsw nuw i32 %stride, 1 2659 ret i32 %stride.plus.one 2660 })"); 2661 Function *F = M->getFunction("test"); 2662 2663 AssumptionCache AC(*F); 2664 Value *Stride = &*F->arg_begin(); 2665 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2666 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I); 2667 EXPECT_EQ(99, *CR.getSingleElement()); 2668 } 2669 2670 { 2671 // Assumptions: 2672 // * stride >= 5 2673 // * stride >= 50 2674 // * stride < 100 2675 // * stride < 200 2676 // 2677 // stride = [50, 100) 2678 auto M = parseModule(R"( 2679 declare void @llvm.assume(i1) 2680 2681 define i32 @test(i32 %stride, i1 %cond) { 2682 %gt = icmp uge i32 %stride, 5 2683 call void @llvm.assume(i1 %gt) 2684 %gt.2 = icmp uge i32 %stride, 50 2685 call void @llvm.assume(i1 %gt.2) 2686 br i1 %cond, label %bb1, label %bb2 2687 2688 bb1: 2689 %lt = icmp ult i32 %stride, 200 2690 call void @llvm.assume(i1 %lt) 2691 %lt.2 = icmp ult i32 %stride, 100 2692 call void @llvm.assume(i1 %lt.2) 2693 %stride.plus.one = add nsw nuw i32 %stride, 1 2694 ret i32 %stride.plus.one 2695 2696 bb2: 2697 ret i32 0 2698 })"); 2699 Function *F = M->getFunction("test"); 2700 2701 AssumptionCache AC(*F); 2702 Value *Stride = &*F->arg_begin(); 2703 Instruction *GT2 = &findInstructionByName(F, "gt.2"); 2704 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, GT2); 2705 EXPECT_EQ(5, CR.getLower()); 2706 EXPECT_EQ(0, CR.getUpper()); 2707 2708 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2709 ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I); 2710 EXPECT_EQ(50, CR2.getLower()); 2711 EXPECT_EQ(100, CR2.getUpper()); 2712 } 2713 2714 { 2715 // Assumptions: 2716 // * stride > 5 2717 // * stride < 5 2718 // 2719 // stride = empty range, as the assumptions contradict each other. 2720 auto M = parseModule(R"( 2721 declare void @llvm.assume(i1) 2722 2723 define i32 @test(i32 %stride, i1 %cond) { 2724 %gt = icmp ugt i32 %stride, 5 2725 call void @llvm.assume(i1 %gt) 2726 %lt = icmp ult i32 %stride, 5 2727 call void @llvm.assume(i1 %lt) 2728 %stride.plus.one = add nsw nuw i32 %stride, 1 2729 ret i32 %stride.plus.one 2730 })"); 2731 Function *F = M->getFunction("test"); 2732 2733 AssumptionCache AC(*F); 2734 Value *Stride = &*F->arg_begin(); 2735 2736 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2737 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I); 2738 EXPECT_TRUE(CR.isEmptySet()); 2739 } 2740 2741 { 2742 // Assumptions: 2743 // * x.1 >= 5 2744 // * x.2 < x.1 2745 // 2746 // stride = [0, -1) 2747 auto M = parseModule(R"( 2748 declare void @llvm.assume(i1) 2749 2750 define i32 @test(i32 %x.1, i32 %x.2) { 2751 %gt = icmp uge i32 %x.1, 5 2752 call void @llvm.assume(i1 %gt) 2753 %lt = icmp ult i32 %x.2, %x.1 2754 call void @llvm.assume(i1 %lt) 2755 %stride.plus.one = add nsw nuw i32 %x.1, 1 2756 ret i32 %stride.plus.one 2757 })"); 2758 Function *F = M->getFunction("test"); 2759 2760 AssumptionCache AC(*F); 2761 Value *X1 = &*(F->arg_begin()); 2762 Value *X2 = &*std::next(F->arg_begin()); 2763 2764 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2765 ConstantRange CR1 = computeConstantRange(X1, false, true, &AC, I); 2766 ConstantRange CR2 = computeConstantRange(X2, false, true, &AC, I); 2767 2768 EXPECT_EQ(5, CR1.getLower()); 2769 EXPECT_EQ(0, CR1.getUpper()); 2770 2771 EXPECT_EQ(0, CR2.getLower()); 2772 EXPECT_EQ(0xffffffff, CR2.getUpper()); 2773 2774 // Check the depth cutoff results in a conservative result (full set) by 2775 // passing Depth == MaxDepth == 6. 2776 ConstantRange CR3 = computeConstantRange(X2, false, true, &AC, I, nullptr, 6); 2777 EXPECT_TRUE(CR3.isFullSet()); 2778 } 2779 { 2780 // Assumptions: 2781 // * x.2 <= x.1 2782 auto M = parseModule(R"( 2783 declare void @llvm.assume(i1) 2784 2785 define i32 @test(i32 %x.1, i32 %x.2) { 2786 %lt = icmp ule i32 %x.2, %x.1 2787 call void @llvm.assume(i1 %lt) 2788 %stride.plus.one = add nsw nuw i32 %x.1, 1 2789 ret i32 %stride.plus.one 2790 })"); 2791 Function *F = M->getFunction("test"); 2792 2793 AssumptionCache AC(*F); 2794 Value *X2 = &*std::next(F->arg_begin()); 2795 2796 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2797 ConstantRange CR1 = computeConstantRange(X2, false, true, &AC, I); 2798 // If we don't know the value of x.2, we don't know the value of x.1. 2799 EXPECT_TRUE(CR1.isFullSet()); 2800 } 2801 } 2802 2803 struct FindAllocaForValueTestParams { 2804 const char *IR; 2805 bool AnyOffsetResult; 2806 bool ZeroOffsetResult; 2807 }; 2808 2809 class FindAllocaForValueTest 2810 : public ValueTrackingTest, 2811 public ::testing::WithParamInterface<FindAllocaForValueTestParams> { 2812 protected: 2813 }; 2814 2815 const FindAllocaForValueTestParams FindAllocaForValueTests[] = { 2816 {R"( 2817 define void @test() { 2818 %a = alloca i64 2819 %r = bitcast ptr %a to ptr 2820 ret void 2821 })", 2822 true, true}, 2823 2824 {R"( 2825 define void @test() { 2826 %a = alloca i32 2827 %r = getelementptr i32, ptr %a, i32 1 2828 ret void 2829 })", 2830 true, false}, 2831 2832 {R"( 2833 define void @test() { 2834 %a = alloca i32 2835 %r = getelementptr i32, ptr %a, i32 0 2836 ret void 2837 })", 2838 true, true}, 2839 2840 {R"( 2841 define void @test(i1 %cond) { 2842 entry: 2843 %a = alloca i32 2844 br label %bb1 2845 2846 bb1: 2847 %r = phi ptr [ %a, %entry ], [ %r, %bb1 ] 2848 br i1 %cond, label %bb1, label %exit 2849 2850 exit: 2851 ret void 2852 })", 2853 true, true}, 2854 2855 {R"( 2856 define void @test(i1 %cond) { 2857 %a = alloca i32 2858 %r = select i1 %cond, ptr %a, ptr %a 2859 ret void 2860 })", 2861 true, true}, 2862 2863 {R"( 2864 define void @test(i1 %cond) { 2865 %a = alloca i32 2866 %b = alloca i32 2867 %r = select i1 %cond, ptr %a, ptr %b 2868 ret void 2869 })", 2870 false, false}, 2871 2872 {R"( 2873 define void @test(i1 %cond) { 2874 entry: 2875 %a = alloca i64 2876 %a32 = bitcast ptr %a to ptr 2877 br label %bb1 2878 2879 bb1: 2880 %x = phi ptr [ %a32, %entry ], [ %x, %bb1 ] 2881 %r = getelementptr i32, ptr %x, i32 1 2882 br i1 %cond, label %bb1, label %exit 2883 2884 exit: 2885 ret void 2886 })", 2887 true, false}, 2888 2889 {R"( 2890 define void @test(i1 %cond) { 2891 entry: 2892 %a = alloca i64 2893 %a32 = bitcast ptr %a to ptr 2894 br label %bb1 2895 2896 bb1: 2897 %x = phi ptr [ %a32, %entry ], [ %r, %bb1 ] 2898 %r = getelementptr i32, ptr %x, i32 1 2899 br i1 %cond, label %bb1, label %exit 2900 2901 exit: 2902 ret void 2903 })", 2904 true, false}, 2905 2906 {R"( 2907 define void @test(i1 %cond, ptr %a) { 2908 entry: 2909 %r = bitcast ptr %a to ptr 2910 ret void 2911 })", 2912 false, false}, 2913 2914 {R"( 2915 define void @test(i1 %cond) { 2916 entry: 2917 %a = alloca i32 2918 %b = alloca i32 2919 br label %bb1 2920 2921 bb1: 2922 %r = phi ptr [ %a, %entry ], [ %b, %bb1 ] 2923 br i1 %cond, label %bb1, label %exit 2924 2925 exit: 2926 ret void 2927 })", 2928 false, false}, 2929 {R"( 2930 declare ptr @retptr(ptr returned) 2931 define void @test(i1 %cond) { 2932 %a = alloca i32 2933 %r = call ptr @retptr(ptr %a) 2934 ret void 2935 })", 2936 true, true}, 2937 {R"( 2938 declare ptr @fun(ptr) 2939 define void @test(i1 %cond) { 2940 %a = alloca i32 2941 %r = call ptr @fun(ptr %a) 2942 ret void 2943 })", 2944 false, false}, 2945 }; 2946 2947 TEST_P(FindAllocaForValueTest, findAllocaForValue) { 2948 auto M = parseModule(GetParam().IR); 2949 Function *F = M->getFunction("test"); 2950 Instruction *I = &findInstructionByName(F, "r"); 2951 const AllocaInst *AI = findAllocaForValue(I); 2952 EXPECT_EQ(!!AI, GetParam().AnyOffsetResult); 2953 } 2954 2955 TEST_P(FindAllocaForValueTest, findAllocaForValueZeroOffset) { 2956 auto M = parseModule(GetParam().IR); 2957 Function *F = M->getFunction("test"); 2958 Instruction *I = &findInstructionByName(F, "r"); 2959 const AllocaInst *AI = findAllocaForValue(I, true); 2960 EXPECT_EQ(!!AI, GetParam().ZeroOffsetResult); 2961 } 2962 2963 INSTANTIATE_TEST_SUITE_P(FindAllocaForValueTest, FindAllocaForValueTest, 2964 ::testing::ValuesIn(FindAllocaForValueTests)); 2965