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