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()), 32u); 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(ComputeKnownFPClassTest, FCmpToClassTest_OrdNan) { 1795 parseAssembly("define i1 @test(double %arg) {\n" 1796 " %A = fcmp ord double %arg, 0x7FF8000000000000" 1797 " %A2 = fcmp uno double %arg, 0x7FF8000000000000" 1798 " %A3 = fcmp oeq double %arg, 0x7FF8000000000000" 1799 " %A4 = fcmp ueq double %arg, 0x7FF8000000000000" 1800 " ret i1 %A\n" 1801 "}\n"); 1802 1803 auto [OrdVal, OrdClass] = fcmpToClassTest( 1804 CmpInst::FCMP_ORD, *A->getFunction(), A->getOperand(0), A->getOperand(1)); 1805 EXPECT_EQ(A->getOperand(0), OrdVal); 1806 EXPECT_EQ(fcNone, OrdClass); 1807 1808 auto [UnordVal, UnordClass] = 1809 fcmpToClassTest(CmpInst::FCMP_UNO, *A2->getFunction(), A2->getOperand(0), 1810 A2->getOperand(1)); 1811 EXPECT_EQ(A2->getOperand(0), UnordVal); 1812 EXPECT_EQ(fcAllFlags, UnordClass); 1813 1814 auto [OeqVal, OeqClass] = 1815 fcmpToClassTest(CmpInst::FCMP_OEQ, *A3->getFunction(), A3->getOperand(0), 1816 A3->getOperand(1)); 1817 EXPECT_EQ(A3->getOperand(0), OeqVal); 1818 EXPECT_EQ(fcNone, OeqClass); 1819 1820 auto [UeqVal, UeqClass] = 1821 fcmpToClassTest(CmpInst::FCMP_UEQ, *A3->getFunction(), A3->getOperand(0), 1822 A3->getOperand(1)); 1823 EXPECT_EQ(A3->getOperand(0), UeqVal); 1824 EXPECT_EQ(fcAllFlags, UeqClass); 1825 } 1826 1827 TEST_F(ComputeKnownFPClassTest, FCmpToClassTest_NInf) { 1828 parseAssembly("define i1 @test(double %arg) {\n" 1829 " %A = fcmp olt double %arg, 0xFFF0000000000000" 1830 " %A2 = fcmp uge double %arg, 0xFFF0000000000000" 1831 " %A3 = fcmp ogt double %arg, 0xFFF0000000000000" 1832 " %A4 = fcmp ule double %arg, 0xFFF0000000000000" 1833 " ret i1 %A\n" 1834 "}\n"); 1835 1836 auto [OltVal, OltClass] = fcmpToClassTest( 1837 CmpInst::FCMP_OLT, *A->getFunction(), A->getOperand(0), A->getOperand(1)); 1838 EXPECT_EQ(A->getOperand(0), OltVal); 1839 EXPECT_EQ(fcNone, OltClass); 1840 1841 auto [UgeVal, UgeClass] = 1842 fcmpToClassTest(CmpInst::FCMP_UGE, *A2->getFunction(), A2->getOperand(0), 1843 A2->getOperand(1)); 1844 EXPECT_EQ(A2->getOperand(0), UgeVal); 1845 EXPECT_EQ(fcAllFlags, UgeClass); 1846 1847 auto [OgtVal, OgtClass] = 1848 fcmpToClassTest(CmpInst::FCMP_OGT, *A3->getFunction(), A3->getOperand(0), 1849 A3->getOperand(1)); 1850 EXPECT_EQ(nullptr, OgtVal); 1851 EXPECT_EQ(fcNone, OgtClass); 1852 1853 auto [UleVal, UleClass] = 1854 fcmpToClassTest(CmpInst::FCMP_ULE, *A4->getFunction(), A4->getOperand(0), 1855 A4->getOperand(1)); 1856 EXPECT_EQ(nullptr, UleVal); 1857 EXPECT_EQ(fcNone, UleClass); 1858 } 1859 1860 TEST_F(ComputeKnownFPClassTest, FCmpToClassTest_PInf) { 1861 parseAssembly("define i1 @test(double %arg) {\n" 1862 " %A = fcmp ogt double %arg, 0x7FF0000000000000" 1863 " %A2 = fcmp ule double %arg, 0x7FF0000000000000" 1864 " %A3 = fcmp ole double %arg, 0x7FF0000000000000" 1865 " %A4 = fcmp ugt double %arg, 0x7FF0000000000000" 1866 " ret i1 %A\n" 1867 "}\n"); 1868 1869 auto [OgtVal, OgtClass] = fcmpToClassTest( 1870 CmpInst::FCMP_OGT, *A->getFunction(), A->getOperand(0), A->getOperand(1)); 1871 EXPECT_EQ(A->getOperand(0), OgtVal); 1872 EXPECT_EQ(fcNone, OgtClass); 1873 1874 auto [UleVal, UleClass] = 1875 fcmpToClassTest(CmpInst::FCMP_ULE, *A2->getFunction(), A2->getOperand(0), 1876 A2->getOperand(1)); 1877 EXPECT_EQ(A2->getOperand(0), UleVal); 1878 EXPECT_EQ(fcAllFlags, UleClass); 1879 1880 auto [OleVal, OleClass] = 1881 fcmpToClassTest(CmpInst::FCMP_OLE, *A3->getFunction(), A3->getOperand(0), 1882 A3->getOperand(1)); 1883 EXPECT_EQ(nullptr, OleVal); 1884 EXPECT_EQ(fcNone, OleClass); 1885 1886 auto [UgtVal, UgtClass] = 1887 fcmpToClassTest(CmpInst::FCMP_UGT, *A4->getFunction(), A4->getOperand(0), 1888 A4->getOperand(1)); 1889 EXPECT_EQ(nullptr, UgtVal); 1890 EXPECT_EQ(fcNone, UgtClass); 1891 } 1892 1893 TEST_F(ComputeKnownFPClassTest, SqrtNszSignBit) { 1894 parseAssembly( 1895 "declare float @llvm.sqrt.f32(float)\n" 1896 "define float @test(float %arg, float nofpclass(nan) %arg.nnan) {\n" 1897 " %A = call float @llvm.sqrt.f32(float %arg)\n" 1898 " %A2 = call nsz float @llvm.sqrt.f32(float %arg)\n" 1899 " %A3 = call float @llvm.sqrt.f32(float %arg.nnan)\n" 1900 " %A4 = call nsz float @llvm.sqrt.f32(float %arg.nnan)\n" 1901 " ret float %A\n" 1902 "}\n"); 1903 1904 const FPClassTest SqrtMask = fcPositive | fcNegZero | fcNan; 1905 const FPClassTest NszSqrtMask = fcPositive | fcNan; 1906 1907 { 1908 KnownFPClass UseInstrInfo = 1909 computeKnownFPClass(A, M->getDataLayout(), fcAllFlags, 0, nullptr, 1910 nullptr, nullptr, nullptr, /*UseInstrInfo=*/true); 1911 EXPECT_EQ(SqrtMask, UseInstrInfo.KnownFPClasses); 1912 EXPECT_EQ(std::nullopt, UseInstrInfo.SignBit); 1913 1914 KnownFPClass NoUseInstrInfo = 1915 computeKnownFPClass(A, M->getDataLayout(), fcAllFlags, 0, nullptr, 1916 nullptr, nullptr, nullptr, /*UseInstrInfo=*/false); 1917 EXPECT_EQ(SqrtMask, NoUseInstrInfo.KnownFPClasses); 1918 EXPECT_EQ(std::nullopt, NoUseInstrInfo.SignBit); 1919 } 1920 1921 { 1922 KnownFPClass UseInstrInfoNSZ = 1923 computeKnownFPClass(A2, M->getDataLayout(), fcAllFlags, 0, nullptr, 1924 nullptr, nullptr, nullptr, /*UseInstrInfo=*/true); 1925 EXPECT_EQ(NszSqrtMask, UseInstrInfoNSZ.KnownFPClasses); 1926 EXPECT_EQ(std::nullopt, UseInstrInfoNSZ.SignBit); 1927 1928 KnownFPClass NoUseInstrInfoNSZ = 1929 computeKnownFPClass(A2, M->getDataLayout(), fcAllFlags, 0, nullptr, 1930 nullptr, nullptr, nullptr, /*UseInstrInfo=*/false); 1931 EXPECT_EQ(SqrtMask, NoUseInstrInfoNSZ.KnownFPClasses); 1932 EXPECT_EQ(std::nullopt, NoUseInstrInfoNSZ.SignBit); 1933 } 1934 1935 { 1936 KnownFPClass UseInstrInfoNoNan = 1937 computeKnownFPClass(A3, M->getDataLayout(), fcAllFlags, 0, nullptr, 1938 nullptr, nullptr, nullptr, /*UseInstrInfo=*/true); 1939 EXPECT_EQ(fcPositive | fcNegZero | fcQNan, 1940 UseInstrInfoNoNan.KnownFPClasses); 1941 EXPECT_EQ(std::nullopt, UseInstrInfoNoNan.SignBit); 1942 1943 KnownFPClass NoUseInstrInfoNoNan = 1944 computeKnownFPClass(A3, M->getDataLayout(), fcAllFlags, 0, nullptr, 1945 nullptr, nullptr, nullptr, /*UseInstrInfo=*/false); 1946 EXPECT_EQ(fcPositive | fcNegZero | fcQNan, 1947 NoUseInstrInfoNoNan.KnownFPClasses); 1948 EXPECT_EQ(std::nullopt, NoUseInstrInfoNoNan.SignBit); 1949 } 1950 1951 { 1952 KnownFPClass UseInstrInfoNSZNoNan = 1953 computeKnownFPClass(A4, M->getDataLayout(), fcAllFlags, 0, nullptr, 1954 nullptr, nullptr, nullptr, /*UseInstrInfo=*/true); 1955 EXPECT_EQ(fcPositive | fcQNan, UseInstrInfoNSZNoNan.KnownFPClasses); 1956 EXPECT_EQ(false, UseInstrInfoNSZNoNan.SignBit); 1957 1958 KnownFPClass NoUseInstrInfoNSZNoNan = 1959 computeKnownFPClass(A4, M->getDataLayout(), fcAllFlags, 0, nullptr, 1960 nullptr, nullptr, nullptr, /*UseInstrInfo=*/false); 1961 EXPECT_EQ(fcPositive | fcNegZero | fcQNan, 1962 NoUseInstrInfoNSZNoNan.KnownFPClasses); 1963 EXPECT_EQ(std::nullopt, NoUseInstrInfoNSZNoNan.SignBit); 1964 } 1965 } 1966 1967 TEST_F(ValueTrackingTest, isNonZeroRecurrence) { 1968 parseAssembly(R"( 1969 define i1 @test(i8 %n, i8 %r) { 1970 entry: 1971 br label %loop 1972 loop: 1973 %p = phi i8 [ -1, %entry ], [ %next, %loop ] 1974 %next = add nsw i8 %p, -1 1975 %cmp1 = icmp eq i8 %p, %n 1976 br i1 %cmp1, label %exit, label %loop 1977 exit: 1978 %A = or i8 %p, %r 1979 %CxtI = icmp eq i8 %A, 0 1980 ret i1 %CxtI 1981 } 1982 )"); 1983 const DataLayout &DL = M->getDataLayout(); 1984 AssumptionCache AC(*F); 1985 EXPECT_TRUE(isKnownNonZero(A, DL, 0, &AC, CxtI)); 1986 } 1987 1988 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond) { 1989 parseAssembly(R"( 1990 declare ptr @f_i8() 1991 define void @test(i1 %c) { 1992 %A = call ptr @f_i8() 1993 %B = call ptr @f_i8() 1994 %c1 = icmp ne ptr %A, null 1995 %cond = and i1 %c1, %c 1996 br i1 %cond, label %T, label %Q 1997 T: 1998 %CxtI = add i32 0, 0 1999 ret void 2000 Q: 2001 %CxtI2 = add i32 0, 0 2002 ret void 2003 } 2004 )"); 2005 AssumptionCache AC(*F); 2006 DominatorTree DT(*F); 2007 const DataLayout &DL = M->getDataLayout(); 2008 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true); 2009 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false); 2010 } 2011 2012 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond2) { 2013 parseAssembly(R"( 2014 declare ptr @f_i8() 2015 define void @test(i1 %c) { 2016 %A = call ptr @f_i8() 2017 %B = call ptr @f_i8() 2018 %c1 = icmp ne ptr %A, null 2019 %cond = select i1 %c, i1 %c1, i1 false 2020 br i1 %cond, label %T, label %Q 2021 T: 2022 %CxtI = add i32 0, 0 2023 ret void 2024 Q: 2025 %CxtI2 = add i32 0, 0 2026 ret void 2027 } 2028 )"); 2029 AssumptionCache AC(*F); 2030 DominatorTree DT(*F); 2031 const DataLayout &DL = M->getDataLayout(); 2032 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI, &DT), true); 2033 EXPECT_EQ(isKnownNonZero(A, DL, 0, &AC, CxtI2, &DT), false); 2034 } 2035 2036 TEST_F(ValueTrackingTest, IsImpliedConditionAnd) { 2037 parseAssembly(R"( 2038 define void @test(i32 %x, i32 %y) { 2039 %c1 = icmp ult i32 %x, 10 2040 %c2 = icmp ult i32 %y, 15 2041 %A = and i1 %c1, %c2 2042 ; x < 10 /\ y < 15 2043 %A2 = icmp ult i32 %x, 20 2044 %A3 = icmp uge i32 %y, 20 2045 %A4 = icmp ult i32 %x, 5 2046 ret void 2047 } 2048 )"); 2049 const DataLayout &DL = M->getDataLayout(); 2050 EXPECT_EQ(isImpliedCondition(A, A2, DL), true); 2051 EXPECT_EQ(isImpliedCondition(A, A3, DL), false); 2052 EXPECT_EQ(isImpliedCondition(A, A4, DL), std::nullopt); 2053 } 2054 2055 TEST_F(ValueTrackingTest, IsImpliedConditionAnd2) { 2056 parseAssembly(R"( 2057 define void @test(i32 %x, i32 %y) { 2058 %c1 = icmp ult i32 %x, 10 2059 %c2 = icmp ult i32 %y, 15 2060 %A = select i1 %c1, i1 %c2, i1 false 2061 ; x < 10 /\ y < 15 2062 %A2 = icmp ult i32 %x, 20 2063 %A3 = icmp uge i32 %y, 20 2064 %A4 = icmp ult i32 %x, 5 2065 ret void 2066 } 2067 )"); 2068 const DataLayout &DL = M->getDataLayout(); 2069 EXPECT_EQ(isImpliedCondition(A, A2, DL), true); 2070 EXPECT_EQ(isImpliedCondition(A, A3, DL), false); 2071 EXPECT_EQ(isImpliedCondition(A, A4, DL), std::nullopt); 2072 } 2073 2074 TEST_F(ValueTrackingTest, IsImpliedConditionAndVec) { 2075 parseAssembly(R"( 2076 define void @test(<2 x i8> %x, <2 x i8> %y) { 2077 %A = icmp ult <2 x i8> %x, %y 2078 %A2 = icmp ule <2 x i8> %x, %y 2079 ret void 2080 } 2081 )"); 2082 const DataLayout &DL = M->getDataLayout(); 2083 EXPECT_EQ(isImpliedCondition(A, A2, DL), true); 2084 } 2085 2086 TEST_F(ValueTrackingTest, IsImpliedConditionOr) { 2087 parseAssembly(R"( 2088 define void @test(i32 %x, i32 %y) { 2089 %c1 = icmp ult i32 %x, 10 2090 %c2 = icmp ult i32 %y, 15 2091 %A = or i1 %c1, %c2 ; negated 2092 ; x >= 10 /\ y >= 15 2093 %A2 = icmp ult i32 %x, 5 2094 %A3 = icmp uge i32 %y, 10 2095 %A4 = icmp ult i32 %x, 15 2096 ret void 2097 } 2098 )"); 2099 const DataLayout &DL = M->getDataLayout(); 2100 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false); 2101 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true); 2102 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), std::nullopt); 2103 } 2104 2105 TEST_F(ValueTrackingTest, IsImpliedConditionOr2) { 2106 parseAssembly(R"( 2107 define void @test(i32 %x, i32 %y) { 2108 %c1 = icmp ult i32 %x, 10 2109 %c2 = icmp ult i32 %y, 15 2110 %A = select i1 %c1, i1 true, i1 %c2 ; negated 2111 ; x >= 10 /\ y >= 15 2112 %A2 = icmp ult i32 %x, 5 2113 %A3 = icmp uge i32 %y, 10 2114 %A4 = icmp ult i32 %x, 15 2115 ret void 2116 } 2117 )"); 2118 const DataLayout &DL = M->getDataLayout(); 2119 EXPECT_EQ(isImpliedCondition(A, A2, DL, false), false); 2120 EXPECT_EQ(isImpliedCondition(A, A3, DL, false), true); 2121 EXPECT_EQ(isImpliedCondition(A, A4, DL, false), std::nullopt); 2122 } 2123 2124 TEST_F(ComputeKnownBitsTest, KnownNonZeroShift) { 2125 // %q is known nonzero without known bits. 2126 // Because %q is nonzero, %A[0] is known to be zero. 2127 parseAssembly( 2128 "define i8 @test(i8 %p, ptr %pq) {\n" 2129 " %q = load i8, ptr %pq, !range !0\n" 2130 " %A = shl i8 %p, %q\n" 2131 " ret i8 %A\n" 2132 "}\n" 2133 "!0 = !{ i8 1, i8 5 }\n"); 2134 expectKnownBits(/*zero*/ 1u, /*one*/ 0u); 2135 } 2136 2137 TEST_F(ComputeKnownBitsTest, ComputeKnownFshl) { 2138 // fshl(....1111....0000, 00..1111........, 6) 2139 // = 11....000000..11 2140 parseAssembly( 2141 "define i16 @test(i16 %a, i16 %b) {\n" 2142 " %aa = shl i16 %a, 4\n" 2143 " %bb = lshr i16 %b, 2\n" 2144 " %aaa = or i16 %aa, 3840\n" 2145 " %bbb = or i16 %bb, 3840\n" 2146 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 6)\n" 2147 " ret i16 %A\n" 2148 "}\n" 2149 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n"); 2150 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u); 2151 } 2152 2153 TEST_F(ComputeKnownBitsTest, ComputeKnownFshr) { 2154 // fshr(....1111....0000, 00..1111........, 26) 2155 // = 11....000000..11 2156 parseAssembly( 2157 "define i16 @test(i16 %a, i16 %b) {\n" 2158 " %aa = shl i16 %a, 4\n" 2159 " %bb = lshr i16 %b, 2\n" 2160 " %aaa = or i16 %aa, 3840\n" 2161 " %bbb = or i16 %bb, 3840\n" 2162 " %A = call i16 @llvm.fshr.i16(i16 %aaa, i16 %bbb, i16 26)\n" 2163 " ret i16 %A\n" 2164 "}\n" 2165 "declare i16 @llvm.fshr.i16(i16, i16, i16)\n"); 2166 expectKnownBits(/*zero*/ 1008u, /*one*/ 49155u); 2167 } 2168 2169 TEST_F(ComputeKnownBitsTest, ComputeKnownFshlZero) { 2170 // fshl(....1111....0000, 00..1111........, 0) 2171 // = ....1111....0000 2172 parseAssembly( 2173 "define i16 @test(i16 %a, i16 %b) {\n" 2174 " %aa = shl i16 %a, 4\n" 2175 " %bb = lshr i16 %b, 2\n" 2176 " %aaa = or i16 %aa, 3840\n" 2177 " %bbb = or i16 %bb, 3840\n" 2178 " %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n" 2179 " ret i16 %A\n" 2180 "}\n" 2181 "declare i16 @llvm.fshl.i16(i16, i16, i16)\n"); 2182 expectKnownBits(/*zero*/ 15u, /*one*/ 3840u); 2183 } 2184 2185 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatLeadingOnes) { 2186 // uadd.sat(1111...1, ........) 2187 // = 1111.... 2188 parseAssembly( 2189 "define i8 @test(i8 %a, i8 %b) {\n" 2190 " %aa = or i8 %a, 241\n" 2191 " %A = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %b)\n" 2192 " ret i8 %A\n" 2193 "}\n" 2194 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n"); 2195 expectKnownBits(/*zero*/ 0u, /*one*/ 240u); 2196 } 2197 2198 TEST_F(ComputeKnownBitsTest, ComputeKnownUAddSatOnesPreserved) { 2199 // uadd.sat(00...011, .1...110) 2200 // = .......1 2201 parseAssembly( 2202 "define i8 @test(i8 %a, i8 %b) {\n" 2203 " %aa = or i8 %a, 3\n" 2204 " %aaa = and i8 %aa, 59\n" 2205 " %bb = or i8 %b, 70\n" 2206 " %bbb = and i8 %bb, 254\n" 2207 " %A = call i8 @llvm.uadd.sat.i8(i8 %aaa, i8 %bbb)\n" 2208 " ret i8 %A\n" 2209 "}\n" 2210 "declare i8 @llvm.uadd.sat.i8(i8, i8)\n"); 2211 expectKnownBits(/*zero*/ 0u, /*one*/ 1u); 2212 } 2213 2214 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatLHSLeadingZeros) { 2215 // usub.sat(0000...0, ........) 2216 // = 0000.... 2217 parseAssembly( 2218 "define i8 @test(i8 %a, i8 %b) {\n" 2219 " %aa = and i8 %a, 14\n" 2220 " %A = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %b)\n" 2221 " ret i8 %A\n" 2222 "}\n" 2223 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 2224 expectKnownBits(/*zero*/ 240u, /*one*/ 0u); 2225 } 2226 2227 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatRHSLeadingOnes) { 2228 // usub.sat(........, 1111...1) 2229 // = 0000.... 2230 parseAssembly( 2231 "define i8 @test(i8 %a, i8 %b) {\n" 2232 " %bb = or i8 %a, 241\n" 2233 " %A = call i8 @llvm.usub.sat.i8(i8 %a, i8 %bb)\n" 2234 " ret i8 %A\n" 2235 "}\n" 2236 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 2237 expectKnownBits(/*zero*/ 240u, /*one*/ 0u); 2238 } 2239 2240 TEST_F(ComputeKnownBitsTest, ComputeKnownUSubSatZerosPreserved) { 2241 // usub.sat(11...011, .1...110) 2242 // = ......0. 2243 parseAssembly( 2244 "define i8 @test(i8 %a, i8 %b) {\n" 2245 " %aa = or i8 %a, 195\n" 2246 " %aaa = and i8 %aa, 251\n" 2247 " %bb = or i8 %b, 70\n" 2248 " %bbb = and i8 %bb, 254\n" 2249 " %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n" 2250 " ret i8 %A\n" 2251 "}\n" 2252 "declare i8 @llvm.usub.sat.i8(i8, i8)\n"); 2253 expectKnownBits(/*zero*/ 2u, /*one*/ 0u); 2254 } 2255 2256 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntTrunc) { 2257 // ptrtoint truncates the pointer type. 2258 parseAssembly( 2259 "define void @test(ptr %p) {\n" 2260 " %A = load ptr, ptr %p\n" 2261 " %i = ptrtoint ptr %A to i32\n" 2262 " %m = and i32 %i, 31\n" 2263 " %c = icmp eq i32 %m, 0\n" 2264 " call void @llvm.assume(i1 %c)\n" 2265 " ret void\n" 2266 "}\n" 2267 "declare void @llvm.assume(i1)\n"); 2268 AssumptionCache AC(*F); 2269 KnownBits Known = computeKnownBits( 2270 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator()); 2271 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 2272 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2273 } 2274 2275 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntZext) { 2276 // ptrtoint zero extends the pointer type. 2277 parseAssembly( 2278 "define void @test(ptr %p) {\n" 2279 " %A = load ptr, ptr %p\n" 2280 " %i = ptrtoint ptr %A to i128\n" 2281 " %m = and i128 %i, 31\n" 2282 " %c = icmp eq i128 %m, 0\n" 2283 " call void @llvm.assume(i1 %c)\n" 2284 " ret void\n" 2285 "}\n" 2286 "declare void @llvm.assume(i1)\n"); 2287 AssumptionCache AC(*F); 2288 KnownBits Known = computeKnownBits( 2289 A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator()); 2290 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 2291 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2292 } 2293 2294 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsFreeze) { 2295 parseAssembly("define void @test() {\n" 2296 " %m = call i32 @any_num()\n" 2297 " %A = freeze i32 %m\n" 2298 " %n = and i32 %m, 31\n" 2299 " %c = icmp eq i32 %n, 0\n" 2300 " call void @llvm.assume(i1 %c)\n" 2301 " ret void\n" 2302 "}\n" 2303 "declare void @llvm.assume(i1)\n" 2304 "declare i32 @any_num()\n"); 2305 AssumptionCache AC(*F); 2306 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2307 F->front().getTerminator()); 2308 EXPECT_EQ(Known.Zero.getZExtValue(), 31u); 2309 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2310 } 2311 2312 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRange) { 2313 parseAssembly("define void @test(ptr %p) {\n" 2314 " %A = load i64, ptr %p, !range !{i64 64, i64 65536}\n" 2315 " %APlus512 = add i64 %A, 512\n" 2316 " %c = icmp ugt i64 %APlus512, 523\n" 2317 " call void @llvm.assume(i1 %c)\n" 2318 " ret void\n" 2319 "}\n" 2320 "declare void @llvm.assume(i1)\n"); 2321 AssumptionCache AC(*F); 2322 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2323 F->front().getTerminator()); 2324 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1)); 2325 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2326 Instruction &APlus512 = findInstructionByName(F, "APlus512"); 2327 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC, 2328 F->front().getTerminator()); 2329 // We know of one less zero because 512 may have produced a 1 that 2330 // got carried all the way to the first trailing zero. 2331 EXPECT_EQ(Known.Zero.getZExtValue(), (~(65536llu - 1)) << 1); 2332 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2333 // The known range is not precise given computeKnownBits works 2334 // with the masks of zeros and ones, not the ranges. 2335 EXPECT_EQ(Known.getMinValue(), 0u); 2336 EXPECT_EQ(Known.getMaxValue(), 131071); 2337 } 2338 2339 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsUnknownVScale) { 2340 Module M("", Context); 2341 IRBuilder<> Builder(Context); 2342 Function *TheFn = 2343 Intrinsic::getDeclaration(&M, Intrinsic::vscale, {Builder.getInt32Ty()}); 2344 CallInst *CI = Builder.CreateCall(TheFn, {}, {}, ""); 2345 2346 KnownBits Known = computeKnownBits(CI, M.getDataLayout(), /* Depth */ 0); 2347 // There is no parent function so we cannot look up the vscale_range 2348 // attribute to determine the number of bits. 2349 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2350 EXPECT_EQ(Known.Zero.getZExtValue(), 0u); 2351 2352 BasicBlock *BB = BasicBlock::Create(Context); 2353 CI->insertInto(BB, BB->end()); 2354 Known = computeKnownBits(CI, M.getDataLayout(), /* Depth */ 0); 2355 // There is no parent function so we cannot look up the vscale_range 2356 // attribute to determine the number of bits. 2357 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2358 EXPECT_EQ(Known.Zero.getZExtValue(), 0u); 2359 2360 CI->removeFromParent(); 2361 delete CI; 2362 delete BB; 2363 } 2364 2365 // 512 + [32, 64) doesn't produce overlapping bits. 2366 // Make sure we get all the individual bits properly. 2367 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAddWithRangeNoOverlap) { 2368 parseAssembly("define void @test(ptr %p) {\n" 2369 " %A = load i64, ptr %p, !range !{i64 32, i64 64}\n" 2370 " %APlus512 = add i64 %A, 512\n" 2371 " %c = icmp ugt i64 %APlus512, 523\n" 2372 " call void @llvm.assume(i1 %c)\n" 2373 " ret void\n" 2374 "}\n" 2375 "declare void @llvm.assume(i1)\n"); 2376 AssumptionCache AC(*F); 2377 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2378 F->front().getTerminator()); 2379 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1)); 2380 EXPECT_EQ(Known.One.getZExtValue(), 32u); 2381 Instruction &APlus512 = findInstructionByName(F, "APlus512"); 2382 Known = computeKnownBits(&APlus512, M->getDataLayout(), /* Depth */ 0, &AC, 2383 F->front().getTerminator()); 2384 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1)); 2385 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u); 2386 // The known range is not precise given computeKnownBits works 2387 // with the masks of zeros and ones, not the ranges. 2388 EXPECT_EQ(Known.getMinValue(), 544); 2389 EXPECT_EQ(Known.getMaxValue(), 575); 2390 } 2391 2392 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRange) { 2393 parseAssembly( 2394 "define void @test(ptr %p) {\n" 2395 " %A = load i64, ptr %p, !range !{i64 64, i64 65536}\n" 2396 " %APtr = inttoptr i64 %A to float*" 2397 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n" 2398 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n" 2399 " call void @llvm.assume(i1 %c)\n" 2400 " ret void\n" 2401 "}\n" 2402 "declare void @llvm.assume(i1)\n"); 2403 AssumptionCache AC(*F); 2404 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2405 F->front().getTerminator()); 2406 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1)); 2407 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2408 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512"); 2409 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC, 2410 F->front().getTerminator()); 2411 // We know of one less zero because 512 may have produced a 1 that 2412 // got carried all the way to the first trailing zero. 2413 EXPECT_EQ(Known.Zero.getZExtValue(), ~(65536llu - 1) << 1); 2414 EXPECT_EQ(Known.One.getZExtValue(), 0u); 2415 // The known range is not precise given computeKnownBits works 2416 // with the masks of zeros and ones, not the ranges. 2417 EXPECT_EQ(Known.getMinValue(), 0u); 2418 EXPECT_EQ(Known.getMaxValue(), 131071); 2419 } 2420 2421 // 4*128 + [32, 64) doesn't produce overlapping bits. 2422 // Make sure we get all the individual bits properly. 2423 // This test is useful to check that we account for the scaling factor 2424 // in the gep. Indeed, gep float, [32,64), 128 is not 128 + [32,64). 2425 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsGEPWithRangeNoOverlap) { 2426 parseAssembly( 2427 "define void @test(ptr %p) {\n" 2428 " %A = load i64, ptr %p, !range !{i64 32, i64 64}\n" 2429 " %APtr = inttoptr i64 %A to float*" 2430 " %APtrPlus512 = getelementptr float, float* %APtr, i32 128\n" 2431 " %c = icmp ugt float* %APtrPlus512, inttoptr (i32 523 to float*)\n" 2432 " call void @llvm.assume(i1 %c)\n" 2433 " ret void\n" 2434 "}\n" 2435 "declare void @llvm.assume(i1)\n"); 2436 AssumptionCache AC(*F); 2437 KnownBits Known = computeKnownBits(A, M->getDataLayout(), /* Depth */ 0, &AC, 2438 F->front().getTerminator()); 2439 EXPECT_EQ(Known.Zero.getZExtValue(), ~(64llu - 1)); 2440 EXPECT_EQ(Known.One.getZExtValue(), 32u); 2441 Instruction &APtrPlus512 = findInstructionByName(F, "APtrPlus512"); 2442 Known = computeKnownBits(&APtrPlus512, M->getDataLayout(), /* Depth */ 0, &AC, 2443 F->front().getTerminator()); 2444 EXPECT_EQ(Known.Zero.getZExtValue(), ~512llu & ~(64llu - 1)); 2445 EXPECT_EQ(Known.One.getZExtValue(), 512u | 32u); 2446 // The known range is not precise given computeKnownBits works 2447 // with the masks of zeros and ones, not the ranges. 2448 EXPECT_EQ(Known.getMinValue(), 544); 2449 EXPECT_EQ(Known.getMaxValue(), 575); 2450 } 2451 2452 TEST_F(ComputeKnownBitsTest, ComputeKnownBitsAbsoluteSymbol) { 2453 auto M = parseModule(R"( 2454 @absolute_0_255 = external global [128 x i32], align 1, !absolute_symbol !0 2455 @absolute_0_256 = external global [128 x i32], align 1, !absolute_symbol !1 2456 @absolute_256_512 = external global [128 x i32], align 1, !absolute_symbol !2 2457 @absolute_0_neg1 = external global [128 x i32], align 1, !absolute_symbol !3 2458 @absolute_neg32_32 = external global [128 x i32], align 1, !absolute_symbol !4 2459 @absolute_neg32_33 = external global [128 x i32], align 1, !absolute_symbol !5 2460 @absolute_neg64_neg32 = external global [128 x i32], align 1, !absolute_symbol !6 2461 @absolute_0_256_align8 = external global [128 x i32], align 8, !absolute_symbol !1 2462 2463 !0 = !{i64 0, i64 255} 2464 !1 = !{i64 0, i64 256} 2465 !2 = !{i64 256, i64 512} 2466 !3 = !{i64 0, i64 -1} 2467 !4 = !{i64 -32, i64 32} 2468 !5 = !{i64 -32, i64 33} 2469 !6 = !{i64 -64, i64 -32} 2470 )"); 2471 2472 GlobalValue *Absolute_0_255 = M->getNamedValue("absolute_0_255"); 2473 GlobalValue *Absolute_0_256 = M->getNamedValue("absolute_0_256"); 2474 GlobalValue *Absolute_256_512 = M->getNamedValue("absolute_256_512"); 2475 GlobalValue *Absolute_0_Neg1 = M->getNamedValue("absolute_0_neg1"); 2476 GlobalValue *Absolute_Neg32_32 = M->getNamedValue("absolute_neg32_32"); 2477 GlobalValue *Absolute_Neg32_33 = M->getNamedValue("absolute_neg32_33"); 2478 GlobalValue *Absolute_Neg64_Neg32 = M->getNamedValue("absolute_neg64_neg32"); 2479 GlobalValue *Absolute_0_256_Align8 = 2480 M->getNamedValue("absolute_0_256_align8"); 2481 2482 KnownBits Known_0_255 = computeKnownBits(Absolute_0_255, M->getDataLayout()); 2483 EXPECT_EQ(64u - 8u, Known_0_255.countMinLeadingZeros()); 2484 EXPECT_EQ(0u, Known_0_255.countMinTrailingZeros()); 2485 EXPECT_EQ(0u, Known_0_255.countMinLeadingOnes()); 2486 EXPECT_EQ(0u, Known_0_255.countMinTrailingOnes()); 2487 2488 KnownBits Known_0_256 = computeKnownBits(Absolute_0_256, M->getDataLayout()); 2489 EXPECT_EQ(64u - 8u, Known_0_256.countMinLeadingZeros()); 2490 EXPECT_EQ(0u, Known_0_256.countMinTrailingZeros()); 2491 EXPECT_EQ(0u, Known_0_256.countMinLeadingOnes()); 2492 EXPECT_EQ(0u, Known_0_256.countMinTrailingOnes()); 2493 2494 KnownBits Known_256_512 = 2495 computeKnownBits(Absolute_256_512, M->getDataLayout()); 2496 EXPECT_EQ(64u - 8u, Known_0_255.countMinLeadingZeros()); 2497 EXPECT_EQ(0u, Known_0_255.countMinTrailingZeros()); 2498 EXPECT_EQ(0u, Known_0_255.countMinLeadingOnes()); 2499 EXPECT_EQ(0u, Known_0_255.countMinTrailingOnes()); 2500 2501 KnownBits Known_0_Neg1 = 2502 computeKnownBits(Absolute_0_Neg1, M->getDataLayout()); 2503 EXPECT_EQ(0u, Known_0_Neg1.countMinLeadingZeros()); 2504 EXPECT_EQ(0u, Known_0_Neg1.countMinTrailingZeros()); 2505 EXPECT_EQ(0u, Known_0_Neg1.countMinLeadingOnes()); 2506 EXPECT_EQ(0u, Known_0_Neg1.countMinTrailingOnes()); 2507 2508 KnownBits Known_Neg32_32 = 2509 computeKnownBits(Absolute_Neg32_32, M->getDataLayout()); 2510 EXPECT_EQ(0u, Known_Neg32_32.countMinLeadingZeros()); 2511 EXPECT_EQ(0u, Known_Neg32_32.countMinTrailingZeros()); 2512 EXPECT_EQ(0u, Known_Neg32_32.countMinLeadingOnes()); 2513 EXPECT_EQ(0u, Known_Neg32_32.countMinTrailingOnes()); 2514 EXPECT_EQ(1u, Known_Neg32_32.countMinSignBits()); 2515 2516 KnownBits Known_Neg32_33 = 2517 computeKnownBits(Absolute_Neg32_33, M->getDataLayout()); 2518 EXPECT_EQ(0u, Known_Neg32_33.countMinLeadingZeros()); 2519 EXPECT_EQ(0u, Known_Neg32_33.countMinTrailingZeros()); 2520 EXPECT_EQ(0u, Known_Neg32_33.countMinLeadingOnes()); 2521 EXPECT_EQ(0u, Known_Neg32_33.countMinTrailingOnes()); 2522 EXPECT_EQ(1u, Known_Neg32_33.countMinSignBits()); 2523 2524 KnownBits Known_Neg32_Neg32 = 2525 computeKnownBits(Absolute_Neg64_Neg32, M->getDataLayout()); 2526 EXPECT_EQ(0u, Known_Neg32_Neg32.countMinLeadingZeros()); 2527 EXPECT_EQ(0u, Known_Neg32_Neg32.countMinTrailingZeros()); 2528 EXPECT_EQ(58u, Known_Neg32_Neg32.countMinLeadingOnes()); 2529 EXPECT_EQ(0u, Known_Neg32_Neg32.countMinTrailingOnes()); 2530 EXPECT_EQ(58u, Known_Neg32_Neg32.countMinSignBits()); 2531 2532 KnownBits Known_0_256_Align8 = 2533 computeKnownBits(Absolute_0_256_Align8, M->getDataLayout()); 2534 EXPECT_EQ(64u - 8u, Known_0_256_Align8.countMinLeadingZeros()); 2535 EXPECT_EQ(3u, Known_0_256_Align8.countMinTrailingZeros()); 2536 EXPECT_EQ(0u, Known_0_256_Align8.countMinLeadingOnes()); 2537 EXPECT_EQ(0u, Known_0_256_Align8.countMinTrailingOnes()); 2538 } 2539 2540 TEST_F(ValueTrackingTest, HaveNoCommonBitsSet) { 2541 { 2542 // Check for an inverted mask: (X & ~M) op (Y & M). 2543 auto M = parseModule(R"( 2544 define i32 @test(i32 %X, i32 %Y, i32 %M) { 2545 %1 = xor i32 %M, -1 2546 %LHS = and i32 %1, %X 2547 %RHS = and i32 %Y, %M 2548 %Ret = add i32 %LHS, %RHS 2549 ret i32 %Ret 2550 })"); 2551 2552 auto *F = M->getFunction("test"); 2553 auto *LHS = findInstructionByNameOrNull(F, "LHS"); 2554 auto *RHS = findInstructionByNameOrNull(F, "RHS"); 2555 2556 const DataLayout &DL = M->getDataLayout(); 2557 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL)); 2558 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL)); 2559 } 2560 { 2561 // Check for (A & B) and ~(A | B) 2562 auto M = parseModule(R"( 2563 define void @test(i32 %A, i32 %B) { 2564 %LHS = and i32 %A, %B 2565 %or = or i32 %A, %B 2566 %RHS = xor i32 %or, -1 2567 2568 %LHS2 = and i32 %B, %A 2569 %or2 = or i32 %A, %B 2570 %RHS2 = xor i32 %or2, -1 2571 2572 ret void 2573 })"); 2574 2575 auto *F = M->getFunction("test"); 2576 const DataLayout &DL = M->getDataLayout(); 2577 2578 auto *LHS = findInstructionByNameOrNull(F, "LHS"); 2579 auto *RHS = findInstructionByNameOrNull(F, "RHS"); 2580 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL)); 2581 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL)); 2582 2583 auto *LHS2 = findInstructionByNameOrNull(F, "LHS2"); 2584 auto *RHS2 = findInstructionByNameOrNull(F, "RHS2"); 2585 EXPECT_TRUE(haveNoCommonBitsSet(LHS2, RHS2, DL)); 2586 EXPECT_TRUE(haveNoCommonBitsSet(RHS2, LHS2, DL)); 2587 } 2588 { 2589 // Check for (A & B) and ~(A | B) in vector version 2590 auto M = parseModule(R"( 2591 define void @test(<2 x i32> %A, <2 x i32> %B) { 2592 %LHS = and <2 x i32> %A, %B 2593 %or = or <2 x i32> %A, %B 2594 %RHS = xor <2 x i32> %or, <i32 -1, i32 -1> 2595 2596 %LHS2 = and <2 x i32> %B, %A 2597 %or2 = or <2 x i32> %A, %B 2598 %RHS2 = xor <2 x i32> %or2, <i32 -1, i32 -1> 2599 2600 ret void 2601 })"); 2602 2603 auto *F = M->getFunction("test"); 2604 const DataLayout &DL = M->getDataLayout(); 2605 2606 auto *LHS = findInstructionByNameOrNull(F, "LHS"); 2607 auto *RHS = findInstructionByNameOrNull(F, "RHS"); 2608 EXPECT_TRUE(haveNoCommonBitsSet(LHS, RHS, DL)); 2609 EXPECT_TRUE(haveNoCommonBitsSet(RHS, LHS, DL)); 2610 2611 auto *LHS2 = findInstructionByNameOrNull(F, "LHS2"); 2612 auto *RHS2 = findInstructionByNameOrNull(F, "RHS2"); 2613 EXPECT_TRUE(haveNoCommonBitsSet(LHS2, RHS2, DL)); 2614 EXPECT_TRUE(haveNoCommonBitsSet(RHS2, LHS2, DL)); 2615 } 2616 } 2617 2618 class IsBytewiseValueTest : public ValueTrackingTest, 2619 public ::testing::WithParamInterface< 2620 std::pair<const char *, const char *>> { 2621 protected: 2622 }; 2623 2624 const std::pair<const char *, const char *> IsBytewiseValueTests[] = { 2625 { 2626 "i8 0", 2627 "i48* null", 2628 }, 2629 { 2630 "i8 undef", 2631 "i48* undef", 2632 }, 2633 { 2634 "i8 0", 2635 "i8 zeroinitializer", 2636 }, 2637 { 2638 "i8 0", 2639 "i8 0", 2640 }, 2641 { 2642 "i8 -86", 2643 "i8 -86", 2644 }, 2645 { 2646 "i8 -1", 2647 "i8 -1", 2648 }, 2649 { 2650 "i8 undef", 2651 "i16 undef", 2652 }, 2653 { 2654 "i8 0", 2655 "i16 0", 2656 }, 2657 { 2658 "", 2659 "i16 7", 2660 }, 2661 { 2662 "i8 -86", 2663 "i16 -21846", 2664 }, 2665 { 2666 "i8 -1", 2667 "i16 -1", 2668 }, 2669 { 2670 "i8 0", 2671 "i48 0", 2672 }, 2673 { 2674 "i8 -1", 2675 "i48 -1", 2676 }, 2677 { 2678 "i8 0", 2679 "i49 0", 2680 }, 2681 { 2682 "", 2683 "i49 -1", 2684 }, 2685 { 2686 "i8 0", 2687 "half 0xH0000", 2688 }, 2689 { 2690 "i8 -85", 2691 "half 0xHABAB", 2692 }, 2693 { 2694 "i8 0", 2695 "float 0.0", 2696 }, 2697 { 2698 "i8 -1", 2699 "float 0xFFFFFFFFE0000000", 2700 }, 2701 { 2702 "i8 0", 2703 "double 0.0", 2704 }, 2705 { 2706 "i8 -15", 2707 "double 0xF1F1F1F1F1F1F1F1", 2708 }, 2709 { 2710 "i8 undef", 2711 "i16* undef", 2712 }, 2713 { 2714 "i8 0", 2715 "i16* inttoptr (i64 0 to i16*)", 2716 }, 2717 { 2718 "i8 -1", 2719 "i16* inttoptr (i64 -1 to i16*)", 2720 }, 2721 { 2722 "i8 -86", 2723 "i16* inttoptr (i64 -6148914691236517206 to i16*)", 2724 }, 2725 { 2726 "", 2727 "i16* inttoptr (i48 -1 to i16*)", 2728 }, 2729 { 2730 "i8 -1", 2731 "i16* inttoptr (i96 -1 to i16*)", 2732 }, 2733 { 2734 "i8 undef", 2735 "[0 x i8] zeroinitializer", 2736 }, 2737 { 2738 "i8 undef", 2739 "[0 x i8] undef", 2740 }, 2741 { 2742 "i8 undef", 2743 "[5 x [0 x i8]] zeroinitializer", 2744 }, 2745 { 2746 "i8 undef", 2747 "[5 x [0 x i8]] undef", 2748 }, 2749 { 2750 "i8 0", 2751 "[6 x i8] zeroinitializer", 2752 }, 2753 { 2754 "i8 undef", 2755 "[6 x i8] undef", 2756 }, 2757 { 2758 "i8 1", 2759 "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]", 2760 }, 2761 { 2762 "", 2763 "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]", 2764 }, 2765 { 2766 "i8 -1", 2767 "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]", 2768 }, 2769 { 2770 "", 2771 "[4 x i8] [i8 1, i8 2, i8 1, i8 1]", 2772 }, 2773 { 2774 "i8 1", 2775 "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]", 2776 }, 2777 { 2778 "i8 0", 2779 "<6 x i8> zeroinitializer", 2780 }, 2781 { 2782 "i8 undef", 2783 "<6 x i8> undef", 2784 }, 2785 { 2786 "i8 1", 2787 "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>", 2788 }, 2789 { 2790 "", 2791 "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>", 2792 }, 2793 { 2794 "i8 -1", 2795 "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>", 2796 }, 2797 { 2798 "", 2799 "<4 x i8> <i8 1, i8 1, i8 2, i8 1>", 2800 }, 2801 { 2802 "i8 5", 2803 "<2 x i8> < i8 5, i8 undef >", 2804 }, 2805 { 2806 "i8 0", 2807 "[2 x [2 x i16]] zeroinitializer", 2808 }, 2809 { 2810 "i8 undef", 2811 "[2 x [2 x i16]] undef", 2812 }, 2813 { 2814 "i8 -86", 2815 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], " 2816 "[2 x i16] [i16 -21846, i16 -21846]]", 2817 }, 2818 { 2819 "", 2820 "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], " 2821 "[2 x i16] [i16 -21836, i16 -21846]]", 2822 }, 2823 { 2824 "i8 undef", 2825 "{ } zeroinitializer", 2826 }, 2827 { 2828 "i8 undef", 2829 "{ } undef", 2830 }, 2831 { 2832 "i8 undef", 2833 "{ {}, {} } zeroinitializer", 2834 }, 2835 { 2836 "i8 undef", 2837 "{ {}, {} } undef", 2838 }, 2839 { 2840 "i8 0", 2841 "{i8, i64, i16*} zeroinitializer", 2842 }, 2843 { 2844 "i8 undef", 2845 "{i8, i64, i16*} undef", 2846 }, 2847 { 2848 "i8 -86", 2849 "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}", 2850 }, 2851 { 2852 "", 2853 "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}", 2854 }, 2855 }; 2856 2857 INSTANTIATE_TEST_SUITE_P(IsBytewiseValueParamTests, IsBytewiseValueTest, 2858 ::testing::ValuesIn(IsBytewiseValueTests)); 2859 2860 TEST_P(IsBytewiseValueTest, IsBytewiseValue) { 2861 auto M = parseModule(std::string("@test = global ") + GetParam().second); 2862 GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test")); 2863 Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout()); 2864 std::string Buff; 2865 raw_string_ostream S(Buff); 2866 if (Actual) 2867 S << *Actual; 2868 EXPECT_EQ(GetParam().first, S.str()); 2869 } 2870 2871 TEST_F(ValueTrackingTest, ComputeConstantRange) { 2872 { 2873 // Assumptions: 2874 // * stride >= 5 2875 // * stride < 10 2876 // 2877 // stride = [5, 10) 2878 auto M = parseModule(R"( 2879 declare void @llvm.assume(i1) 2880 2881 define i32 @test(i32 %stride) { 2882 %gt = icmp uge i32 %stride, 5 2883 call void @llvm.assume(i1 %gt) 2884 %lt = icmp ult i32 %stride, 10 2885 call void @llvm.assume(i1 %lt) 2886 %stride.plus.one = add nsw nuw i32 %stride, 1 2887 ret i32 %stride.plus.one 2888 })"); 2889 Function *F = M->getFunction("test"); 2890 2891 AssumptionCache AC(*F); 2892 Value *Stride = &*F->arg_begin(); 2893 ConstantRange CR1 = computeConstantRange(Stride, false, true, &AC, nullptr); 2894 EXPECT_TRUE(CR1.isFullSet()); 2895 2896 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2897 ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I); 2898 EXPECT_EQ(5, CR2.getLower()); 2899 EXPECT_EQ(10, CR2.getUpper()); 2900 } 2901 2902 { 2903 // Assumptions: 2904 // * stride >= 5 2905 // * stride < 200 2906 // * stride == 99 2907 // 2908 // stride = [99, 100) 2909 auto M = parseModule(R"( 2910 declare void @llvm.assume(i1) 2911 2912 define i32 @test(i32 %stride) { 2913 %gt = icmp uge i32 %stride, 5 2914 call void @llvm.assume(i1 %gt) 2915 %lt = icmp ult i32 %stride, 200 2916 call void @llvm.assume(i1 %lt) 2917 %eq = icmp eq i32 %stride, 99 2918 call void @llvm.assume(i1 %eq) 2919 %stride.plus.one = add nsw nuw i32 %stride, 1 2920 ret i32 %stride.plus.one 2921 })"); 2922 Function *F = M->getFunction("test"); 2923 2924 AssumptionCache AC(*F); 2925 Value *Stride = &*F->arg_begin(); 2926 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2927 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I); 2928 EXPECT_EQ(99, *CR.getSingleElement()); 2929 } 2930 2931 { 2932 // Assumptions: 2933 // * stride >= 5 2934 // * stride >= 50 2935 // * stride < 100 2936 // * stride < 200 2937 // 2938 // stride = [50, 100) 2939 auto M = parseModule(R"( 2940 declare void @llvm.assume(i1) 2941 2942 define i32 @test(i32 %stride, i1 %cond) { 2943 %gt = icmp uge i32 %stride, 5 2944 call void @llvm.assume(i1 %gt) 2945 %gt.2 = icmp uge i32 %stride, 50 2946 call void @llvm.assume(i1 %gt.2) 2947 br i1 %cond, label %bb1, label %bb2 2948 2949 bb1: 2950 %lt = icmp ult i32 %stride, 200 2951 call void @llvm.assume(i1 %lt) 2952 %lt.2 = icmp ult i32 %stride, 100 2953 call void @llvm.assume(i1 %lt.2) 2954 %stride.plus.one = add nsw nuw i32 %stride, 1 2955 ret i32 %stride.plus.one 2956 2957 bb2: 2958 ret i32 0 2959 })"); 2960 Function *F = M->getFunction("test"); 2961 2962 AssumptionCache AC(*F); 2963 Value *Stride = &*F->arg_begin(); 2964 Instruction *GT2 = &findInstructionByName(F, "gt.2"); 2965 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, GT2); 2966 EXPECT_EQ(5, CR.getLower()); 2967 EXPECT_EQ(0, CR.getUpper()); 2968 2969 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2970 ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I); 2971 EXPECT_EQ(50, CR2.getLower()); 2972 EXPECT_EQ(100, CR2.getUpper()); 2973 } 2974 2975 { 2976 // Assumptions: 2977 // * stride > 5 2978 // * stride < 5 2979 // 2980 // stride = empty range, as the assumptions contradict each other. 2981 auto M = parseModule(R"( 2982 declare void @llvm.assume(i1) 2983 2984 define i32 @test(i32 %stride, i1 %cond) { 2985 %gt = icmp ugt i32 %stride, 5 2986 call void @llvm.assume(i1 %gt) 2987 %lt = icmp ult i32 %stride, 5 2988 call void @llvm.assume(i1 %lt) 2989 %stride.plus.one = add nsw nuw i32 %stride, 1 2990 ret i32 %stride.plus.one 2991 })"); 2992 Function *F = M->getFunction("test"); 2993 2994 AssumptionCache AC(*F); 2995 Value *Stride = &*F->arg_begin(); 2996 2997 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 2998 ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I); 2999 EXPECT_TRUE(CR.isEmptySet()); 3000 } 3001 3002 { 3003 // Assumptions: 3004 // * x.1 >= 5 3005 // * x.2 < x.1 3006 // 3007 // stride = [0, -1) 3008 auto M = parseModule(R"( 3009 declare void @llvm.assume(i1) 3010 3011 define i32 @test(i32 %x.1, i32 %x.2) { 3012 %gt = icmp uge i32 %x.1, 5 3013 call void @llvm.assume(i1 %gt) 3014 %lt = icmp ult i32 %x.2, %x.1 3015 call void @llvm.assume(i1 %lt) 3016 %stride.plus.one = add nsw nuw i32 %x.1, 1 3017 ret i32 %stride.plus.one 3018 })"); 3019 Function *F = M->getFunction("test"); 3020 3021 AssumptionCache AC(*F); 3022 Value *X1 = &*(F->arg_begin()); 3023 Value *X2 = &*std::next(F->arg_begin()); 3024 3025 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 3026 ConstantRange CR1 = computeConstantRange(X1, false, true, &AC, I); 3027 ConstantRange CR2 = computeConstantRange(X2, false, true, &AC, I); 3028 3029 EXPECT_EQ(5, CR1.getLower()); 3030 EXPECT_EQ(0, CR1.getUpper()); 3031 3032 EXPECT_EQ(0, CR2.getLower()); 3033 EXPECT_EQ(0xffffffff, CR2.getUpper()); 3034 3035 // Check the depth cutoff results in a conservative result (full set) by 3036 // passing Depth == MaxDepth == 6. 3037 ConstantRange CR3 = computeConstantRange(X2, false, true, &AC, I, nullptr, 6); 3038 EXPECT_TRUE(CR3.isFullSet()); 3039 } 3040 { 3041 // Assumptions: 3042 // * x.2 <= x.1 3043 auto M = parseModule(R"( 3044 declare void @llvm.assume(i1) 3045 3046 define i32 @test(i32 %x.1, i32 %x.2) { 3047 %lt = icmp ule i32 %x.2, %x.1 3048 call void @llvm.assume(i1 %lt) 3049 %stride.plus.one = add nsw nuw i32 %x.1, 1 3050 ret i32 %stride.plus.one 3051 })"); 3052 Function *F = M->getFunction("test"); 3053 3054 AssumptionCache AC(*F); 3055 Value *X2 = &*std::next(F->arg_begin()); 3056 3057 Instruction *I = &findInstructionByName(F, "stride.plus.one"); 3058 ConstantRange CR1 = computeConstantRange(X2, false, true, &AC, I); 3059 // If we don't know the value of x.2, we don't know the value of x.1. 3060 EXPECT_TRUE(CR1.isFullSet()); 3061 } 3062 } 3063 3064 struct FindAllocaForValueTestParams { 3065 const char *IR; 3066 bool AnyOffsetResult; 3067 bool ZeroOffsetResult; 3068 }; 3069 3070 class FindAllocaForValueTest 3071 : public ValueTrackingTest, 3072 public ::testing::WithParamInterface<FindAllocaForValueTestParams> { 3073 protected: 3074 }; 3075 3076 const FindAllocaForValueTestParams FindAllocaForValueTests[] = { 3077 {R"( 3078 define void @test() { 3079 %a = alloca i64 3080 %r = bitcast ptr %a to ptr 3081 ret void 3082 })", 3083 true, true}, 3084 3085 {R"( 3086 define void @test() { 3087 %a = alloca i32 3088 %r = getelementptr i32, ptr %a, i32 1 3089 ret void 3090 })", 3091 true, false}, 3092 3093 {R"( 3094 define void @test() { 3095 %a = alloca i32 3096 %r = getelementptr i32, ptr %a, i32 0 3097 ret void 3098 })", 3099 true, true}, 3100 3101 {R"( 3102 define void @test(i1 %cond) { 3103 entry: 3104 %a = alloca i32 3105 br label %bb1 3106 3107 bb1: 3108 %r = phi ptr [ %a, %entry ], [ %r, %bb1 ] 3109 br i1 %cond, label %bb1, label %exit 3110 3111 exit: 3112 ret void 3113 })", 3114 true, true}, 3115 3116 {R"( 3117 define void @test(i1 %cond) { 3118 %a = alloca i32 3119 %r = select i1 %cond, ptr %a, ptr %a 3120 ret void 3121 })", 3122 true, true}, 3123 3124 {R"( 3125 define void @test(i1 %cond) { 3126 %a = alloca i32 3127 %b = alloca i32 3128 %r = select i1 %cond, ptr %a, ptr %b 3129 ret void 3130 })", 3131 false, false}, 3132 3133 {R"( 3134 define void @test(i1 %cond) { 3135 entry: 3136 %a = alloca i64 3137 %a32 = bitcast ptr %a to ptr 3138 br label %bb1 3139 3140 bb1: 3141 %x = phi ptr [ %a32, %entry ], [ %x, %bb1 ] 3142 %r = getelementptr i32, ptr %x, i32 1 3143 br i1 %cond, label %bb1, label %exit 3144 3145 exit: 3146 ret void 3147 })", 3148 true, false}, 3149 3150 {R"( 3151 define void @test(i1 %cond) { 3152 entry: 3153 %a = alloca i64 3154 %a32 = bitcast ptr %a to ptr 3155 br label %bb1 3156 3157 bb1: 3158 %x = phi ptr [ %a32, %entry ], [ %r, %bb1 ] 3159 %r = getelementptr i32, ptr %x, i32 1 3160 br i1 %cond, label %bb1, label %exit 3161 3162 exit: 3163 ret void 3164 })", 3165 true, false}, 3166 3167 {R"( 3168 define void @test(i1 %cond, ptr %a) { 3169 entry: 3170 %r = bitcast ptr %a to ptr 3171 ret void 3172 })", 3173 false, false}, 3174 3175 {R"( 3176 define void @test(i1 %cond) { 3177 entry: 3178 %a = alloca i32 3179 %b = alloca i32 3180 br label %bb1 3181 3182 bb1: 3183 %r = phi ptr [ %a, %entry ], [ %b, %bb1 ] 3184 br i1 %cond, label %bb1, label %exit 3185 3186 exit: 3187 ret void 3188 })", 3189 false, false}, 3190 {R"( 3191 declare ptr @retptr(ptr returned) 3192 define void @test(i1 %cond) { 3193 %a = alloca i32 3194 %r = call ptr @retptr(ptr %a) 3195 ret void 3196 })", 3197 true, true}, 3198 {R"( 3199 declare ptr @fun(ptr) 3200 define void @test(i1 %cond) { 3201 %a = alloca i32 3202 %r = call ptr @fun(ptr %a) 3203 ret void 3204 })", 3205 false, false}, 3206 }; 3207 3208 TEST_P(FindAllocaForValueTest, findAllocaForValue) { 3209 auto M = parseModule(GetParam().IR); 3210 Function *F = M->getFunction("test"); 3211 Instruction *I = &findInstructionByName(F, "r"); 3212 const AllocaInst *AI = findAllocaForValue(I); 3213 EXPECT_EQ(!!AI, GetParam().AnyOffsetResult); 3214 } 3215 3216 TEST_P(FindAllocaForValueTest, findAllocaForValueZeroOffset) { 3217 auto M = parseModule(GetParam().IR); 3218 Function *F = M->getFunction("test"); 3219 Instruction *I = &findInstructionByName(F, "r"); 3220 const AllocaInst *AI = findAllocaForValue(I, true); 3221 EXPECT_EQ(!!AI, GetParam().ZeroOffsetResult); 3222 } 3223 3224 INSTANTIATE_TEST_SUITE_P(FindAllocaForValueTest, FindAllocaForValueTest, 3225 ::testing::ValuesIn(FindAllocaForValueTests)); 3226