1 //===- SeedCollectorTest.cpp ----------------------------------------===// 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/Transforms/Vectorize/SandboxVectorizer/SeedCollector.h" 10 #include "llvm/Analysis/AliasAnalysis.h" 11 #include "llvm/Analysis/AssumptionCache.h" 12 #include "llvm/Analysis/BasicAliasAnalysis.h" 13 #include "llvm/Analysis/LoopInfo.h" 14 #include "llvm/Analysis/TargetLibraryInfo.h" 15 #include "llvm/AsmParser/Parser.h" 16 #include "llvm/IR/Dominators.h" 17 #include "llvm/SandboxIR/Function.h" 18 #include "llvm/SandboxIR/Instruction.h" 19 #include "llvm/Support/SourceMgr.h" 20 #include "llvm/Testing/Support/SupportHelpers.h" 21 #include "gtest/gtest.h" 22 23 using namespace llvm; 24 25 // TODO: gcc-10 has a bug that causes the below line not to compile due to some 26 // macro-magic in gunit in combination with a class with pure-virtual 27 // function. Once gcc-10 is no longer supported, replace this function with 28 // something like the following: 29 // 30 // EXPECT_THAT(SB, testing::ElementsAre(St0, St1, St2, St3)); 31 static void 32 ExpectThatElementsAre(sandboxir::SeedBundle &SR, 33 llvm::ArrayRef<sandboxir::Instruction *> Contents) { 34 EXPECT_EQ(range_size(SR), Contents.size()); 35 auto CI = Contents.begin(); 36 if (range_size(SR) == Contents.size()) 37 for (auto &S : SR) 38 EXPECT_EQ(S, *CI++); 39 } 40 41 struct SeedBundleTest : public testing::Test { 42 LLVMContext C; 43 std::unique_ptr<Module> M; 44 45 void parseIR(LLVMContext &C, const char *IR) { 46 SMDiagnostic Err; 47 M = parseAssemblyString(IR, Err, C); 48 if (!M) 49 Err.print("LegalityTest", errs()); 50 } 51 BasicBlock *getBasicBlockByName(Function &F, StringRef Name) { 52 for (BasicBlock &BB : F) 53 if (BB.getName() == Name) 54 return &BB; 55 llvm_unreachable("Expected to find basic block!"); 56 } 57 }; 58 59 // Stub class to make the abstract base class testable. 60 class SeedBundleForTest : public sandboxir::SeedBundle { 61 public: 62 using sandboxir::SeedBundle::SeedBundle; 63 void insert(sandboxir::Instruction *I, ScalarEvolution &SE) override { 64 insertAt(Seeds.end(), I); 65 } 66 }; 67 68 TEST_F(SeedBundleTest, SeedBundle) { 69 parseIR(C, R"IR( 70 define void @foo(float %v0, i32 %i0, i16 %i1, i8 %i2) { 71 bb: 72 %add0 = fadd float %v0, %v0 73 %add1 = fadd float %v0, %v0 74 %add2 = add i8 %i2, %i2 75 %add3 = add i16 %i1, %i1 76 %add4 = add i32 %i0, %i0 77 %add5 = add i16 %i1, %i1 78 %add6 = add i8 %i2, %i2 79 %add7 = add i8 %i2, %i2 80 ret void 81 } 82 )IR"); 83 Function &LLVMF = *M->getFunction("foo"); 84 sandboxir::Context Ctx(C); 85 auto &F = *Ctx.createFunction(&LLVMF); 86 DataLayout DL(M->getDataLayout()); 87 auto *BB = &*F.begin(); 88 auto It = BB->begin(); 89 auto *I0 = &*It++; 90 auto *I1 = &*It++; 91 // Assume first two instructions are identical in the number of bits. 92 const unsigned IOBits = sandboxir::Utils::getNumBits(I0, DL); 93 // Constructor 94 SeedBundleForTest SBO(I0); 95 EXPECT_EQ(*SBO.begin(), I0); 96 // getNumUnusedBits after constructor 97 EXPECT_EQ(SBO.getNumUnusedBits(), IOBits); 98 // setUsed 99 SBO.setUsed(I0); 100 // allUsed 101 EXPECT_TRUE(SBO.allUsed()); 102 // isUsed 103 EXPECT_TRUE(SBO.isUsed(0)); 104 // getNumUnusedBits after setUsed 105 EXPECT_EQ(SBO.getNumUnusedBits(), 0u); 106 // insertAt 107 SBO.insertAt(SBO.end(), I1); 108 EXPECT_NE(*SBO.begin(), I1); 109 // getNumUnusedBits after insertAt 110 EXPECT_EQ(SBO.getNumUnusedBits(), IOBits); 111 // allUsed 112 EXPECT_FALSE(SBO.allUsed()); 113 // getFirstUnusedElement 114 EXPECT_EQ(SBO.getFirstUnusedElementIdx(), 1u); 115 116 SmallVector<sandboxir::Instruction *> Insts; 117 // add2 through add7 118 Insts.push_back(&*It++); 119 Insts.push_back(&*It++); 120 Insts.push_back(&*It++); 121 Insts.push_back(&*It++); 122 Insts.push_back(&*It++); 123 Insts.push_back(&*It++); 124 unsigned BundleBits = 0; 125 for (auto &S : Insts) 126 BundleBits += sandboxir::Utils::getNumBits(S); 127 // Ensure the instructions are as expected. 128 EXPECT_EQ(BundleBits, 88u); 129 auto Seeds = Insts; 130 // Constructor 131 SeedBundleForTest SB1(std::move(Seeds)); 132 // getNumUnusedBits after constructor 133 EXPECT_EQ(SB1.getNumUnusedBits(), BundleBits); 134 // setUsed with index 135 SB1.setUsed(1); 136 // getFirstUnusedElementIdx 137 EXPECT_EQ(SB1.getFirstUnusedElementIdx(), 0u); 138 SB1.setUsed(unsigned(0)); 139 // getFirstUnusedElementIdx not at end 140 EXPECT_EQ(SB1.getFirstUnusedElementIdx(), 2u); 141 142 // getSlice is (StartIdx, MaxVecRegBits, ForcePowerOf2). It's easier to 143 // compare test cases without the parameter-name comments inline. 144 auto Slice0 = SB1.getSlice(2, 64, true); 145 EXPECT_THAT(Slice0, 146 testing::ElementsAre(Insts[2], Insts[3], Insts[4], Insts[5])); 147 auto Slice1 = SB1.getSlice(2, 72, true); 148 EXPECT_THAT(Slice1, 149 testing::ElementsAre(Insts[2], Insts[3], Insts[4], Insts[5])); 150 auto Slice2 = SB1.getSlice(2, 80, true); 151 EXPECT_THAT(Slice2, 152 testing::ElementsAre(Insts[2], Insts[3], Insts[4], Insts[5])); 153 154 SB1.setUsed(2); 155 auto Slice3 = SB1.getSlice(3, 64, false); 156 EXPECT_THAT(Slice3, testing::ElementsAre(Insts[3], Insts[4], Insts[5])); 157 // getSlice empty case 158 SB1.setUsed(3); 159 auto Slice4 = SB1.getSlice(4, /* MaxVecRegBits */ 8, 160 /* ForcePowerOf2 */ true); 161 EXPECT_EQ(Slice4.size(), 0u); 162 } 163 164 TEST_F(SeedBundleTest, MemSeedBundle) { 165 parseIR(C, R"IR( 166 define void @foo(ptr %ptrA, float %val, ptr %ptr) { 167 bb: 168 %gep0 = getelementptr float, ptr %ptr, i32 0 169 %gep1 = getelementptr float, ptr %ptr, i32 1 170 %gep2 = getelementptr float, ptr %ptr, i32 3 171 %gep3 = getelementptr float, ptr %ptr, i32 4 172 store float %val, ptr %gep0 173 store float %val, ptr %gep1 174 store float %val, ptr %gep2 175 store float %val, ptr %gep3 176 177 load float, ptr %gep0 178 load float, ptr %gep1 179 load float, ptr %gep2 180 load float, ptr %gep3 181 182 ret void 183 } 184 )IR"); 185 Function &LLVMF = *M->getFunction("foo"); 186 187 DominatorTree DT(LLVMF); 188 TargetLibraryInfoImpl TLII; 189 TargetLibraryInfo TLI(TLII); 190 DataLayout DL(M->getDataLayout()); 191 LoopInfo LI(DT); 192 AssumptionCache AC(LLVMF); 193 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI); 194 195 sandboxir::Context Ctx(C); 196 auto &F = *Ctx.createFunction(&LLVMF); 197 auto *BB = &*F.begin(); 198 auto It = std::next(BB->begin(), 4); 199 auto *S0 = cast<sandboxir::StoreInst>(&*It++); 200 auto *S1 = cast<sandboxir::StoreInst>(&*It++); 201 auto *S2 = cast<sandboxir::StoreInst>(&*It++); 202 auto *S3 = cast<sandboxir::StoreInst>(&*It++); 203 204 // Single instruction constructor; test insert out of memory order 205 sandboxir::StoreSeedBundle SB(S3); 206 SB.insert(S1, SE); 207 SB.insert(S2, SE); 208 SB.insert(S0, SE); 209 EXPECT_THAT(SB, testing::ElementsAre(S0, S1, S2, S3)); 210 211 // Instruction list constructor; test list out of order 212 auto *L0 = cast<sandboxir::LoadInst>(&*It++); 213 auto *L1 = cast<sandboxir::LoadInst>(&*It++); 214 auto *L2 = cast<sandboxir::LoadInst>(&*It++); 215 auto *L3 = cast<sandboxir::LoadInst>(&*It++); 216 SmallVector<sandboxir::Instruction *> Loads; 217 Loads.push_back(L1); 218 Loads.push_back(L3); 219 Loads.push_back(L2); 220 Loads.push_back(L0); 221 sandboxir::LoadSeedBundle LB(std::move(Loads), SE); 222 EXPECT_THAT(LB, testing::ElementsAre(L0, L1, L2, L3)); 223 } 224 225 TEST_F(SeedBundleTest, Container) { 226 parseIR(C, R"IR( 227 define void @foo(ptr %ptrA, float %val, ptr %ptrB) { 228 bb: 229 %gepA0 = getelementptr float, ptr %ptrA, i32 0 230 %gepA1 = getelementptr float, ptr %ptrA, i32 1 231 %gepB0 = getelementptr float, ptr %ptrB, i32 0 232 %gepB1 = getelementptr float, ptr %ptrB, i32 1 233 store float %val, ptr %gepA0 234 store float %val, ptr %gepA1 235 store float %val, ptr %gepB0 236 store float %val, ptr %gepB1 237 ret void 238 } 239 )IR"); 240 Function &LLVMF = *M->getFunction("foo"); 241 242 DominatorTree DT(LLVMF); 243 TargetLibraryInfoImpl TLII; 244 TargetLibraryInfo TLI(TLII); 245 DataLayout DL(M->getDataLayout()); 246 LoopInfo LI(DT); 247 AssumptionCache AC(LLVMF); 248 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI); 249 250 sandboxir::Context Ctx(C); 251 auto &F = *Ctx.createFunction(&LLVMF); 252 auto &BB = *F.begin(); 253 auto It = std::next(BB.begin(), 4); 254 auto *S0 = cast<sandboxir::StoreInst>(&*It++); 255 auto *S1 = cast<sandboxir::StoreInst>(&*It++); 256 auto *S2 = cast<sandboxir::StoreInst>(&*It++); 257 auto *S3 = cast<sandboxir::StoreInst>(&*It++); 258 sandboxir::SeedContainer SC(SE); 259 // Check begin() end() when empty. 260 EXPECT_EQ(SC.begin(), SC.end()); 261 262 SC.insert(S0); 263 SC.insert(S1); 264 SC.insert(S2); 265 SC.insert(S3); 266 unsigned Cnt = 0; 267 SmallVector<sandboxir::SeedBundle *> Bndls; 268 for (auto &SeedBndl : SC) { 269 EXPECT_EQ(SeedBndl.size(), 2u); 270 ++Cnt; 271 Bndls.push_back(&SeedBndl); 272 } 273 EXPECT_EQ(Cnt, 2u); 274 275 // Mark them "Used" to check if operator++ skips them in the next loop. 276 for (auto *SeedBndl : Bndls) 277 for (auto Lane : seq<unsigned>(SeedBndl->size())) 278 SeedBndl->setUsed(Lane); 279 // Check if iterator::operator++ skips used lanes. 280 Cnt = 0; 281 for (auto &SeedBndl : SC) { 282 (void)SeedBndl; 283 ++Cnt; 284 } 285 EXPECT_EQ(Cnt, 0u); 286 } 287 288 TEST_F(SeedBundleTest, ConsecutiveStores) { 289 // Where "Consecutive" means the stores address consecutive locations in 290 // memory, but not in program order. Check to see that the collector puts them 291 // in the proper order for vectorization. 292 parseIR(C, R"IR( 293 define void @foo(ptr noalias %ptr, float %val) { 294 bb: 295 %ptr0 = getelementptr float, ptr %ptr, i32 0 296 %ptr1 = getelementptr float, ptr %ptr, i32 1 297 %ptr2 = getelementptr float, ptr %ptr, i32 2 298 %ptr3 = getelementptr float, ptr %ptr, i32 3 299 store float %val, ptr %ptr0 300 store float %val, ptr %ptr2 301 store float %val, ptr %ptr1 302 store float %val, ptr %ptr3 303 ret void 304 } 305 )IR"); 306 Function &LLVMF = *M->getFunction("foo"); 307 DominatorTree DT(LLVMF); 308 TargetLibraryInfoImpl TLII; 309 TargetLibraryInfo TLI(TLII); 310 DataLayout DL(M->getDataLayout()); 311 LoopInfo LI(DT); 312 AssumptionCache AC(LLVMF); 313 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI); 314 315 sandboxir::Context Ctx(C); 316 auto &F = *Ctx.createFunction(&LLVMF); 317 auto BB = F.begin(); 318 sandboxir::SeedCollector SC(&*BB, SE); 319 320 // Find the stores 321 auto It = std::next(BB->begin(), 4); 322 // StX with X as the order by offset in memory 323 auto *St0 = &*It++; 324 auto *St2 = &*It++; 325 auto *St1 = &*It++; 326 auto *St3 = &*It++; 327 328 auto StoreSeedsRange = SC.getStoreSeeds(); 329 auto &SB = *StoreSeedsRange.begin(); 330 // Expect just one vector of store seeds 331 EXPECT_EQ(range_size(StoreSeedsRange), 1u); 332 ExpectThatElementsAre(SB, {St0, St1, St2, St3}); 333 } 334 335 TEST_F(SeedBundleTest, StoresWithGaps) { 336 parseIR(C, R"IR( 337 define void @foo(ptr noalias %ptr, float %val) { 338 bb: 339 %ptr0 = getelementptr float, ptr %ptr, i32 0 340 %ptr1 = getelementptr float, ptr %ptr, i32 3 341 %ptr2 = getelementptr float, ptr %ptr, i32 5 342 %ptr3 = getelementptr float, ptr %ptr, i32 7 343 store float %val, ptr %ptr0 344 store float %val, ptr %ptr2 345 store float %val, ptr %ptr1 346 store float %val, ptr %ptr3 347 ret void 348 } 349 )IR"); 350 Function &LLVMF = *M->getFunction("foo"); 351 DominatorTree DT(LLVMF); 352 TargetLibraryInfoImpl TLII; 353 TargetLibraryInfo TLI(TLII); 354 DataLayout DL(M->getDataLayout()); 355 LoopInfo LI(DT); 356 AssumptionCache AC(LLVMF); 357 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI); 358 359 sandboxir::Context Ctx(C); 360 auto &F = *Ctx.createFunction(&LLVMF); 361 auto BB = F.begin(); 362 sandboxir::SeedCollector SC(&*BB, SE); 363 364 // Find the stores 365 auto It = std::next(BB->begin(), 4); 366 // StX with X as the order by offset in memory 367 auto *St0 = &*It++; 368 auto *St2 = &*It++; 369 auto *St1 = &*It++; 370 auto *St3 = &*It++; 371 372 auto StoreSeedsRange = SC.getStoreSeeds(); 373 auto &SB = *StoreSeedsRange.begin(); 374 // Expect just one vector of store seeds 375 EXPECT_EQ(range_size(StoreSeedsRange), 1u); 376 ExpectThatElementsAre(SB, {St0, St1, St2, St3}); 377 // Check that the EraseInstr callback works. 378 379 // TODO: Range_size counts fully used-bundles even though the iterator skips 380 // them. Further, iterating over anything other than the Bundles in a 381 // SeedContainer includes used seeds. So for now just check that removing all 382 // the seeds from a bundle also empties the bundle. 383 St0->eraseFromParent(); 384 St1->eraseFromParent(); 385 St2->eraseFromParent(); 386 St3->eraseFromParent(); 387 size_t nonEmptyBundleCount = 0; 388 for (auto &B : SC.getStoreSeeds()) { 389 (void)B; 390 nonEmptyBundleCount++; 391 } 392 EXPECT_EQ(nonEmptyBundleCount, 0u); 393 } 394 395 TEST_F(SeedBundleTest, VectorStores) { 396 parseIR(C, R"IR( 397 define void @foo(ptr noalias %ptr, <2 x float> %val0, i64 %val1) { 398 bb: 399 %ptr0 = getelementptr float, ptr %ptr, i32 0 400 %ptr1 = getelementptr float, ptr %ptr, i32 1 401 %ptr2 = getelementptr i64, ptr %ptr, i32 2 402 store <2 x float> %val0, ptr %ptr1 403 store <2 x float> %val0, ptr %ptr0 404 store atomic i64 %val1, ptr %ptr2 unordered, align 8 405 store volatile i64 %val1, ptr %ptr2 406 407 ret void 408 } 409 )IR"); 410 Function &LLVMF = *M->getFunction("foo"); 411 DominatorTree DT(LLVMF); 412 TargetLibraryInfoImpl TLII; 413 TargetLibraryInfo TLI(TLII); 414 DataLayout DL(M->getDataLayout()); 415 LoopInfo LI(DT); 416 AssumptionCache AC(LLVMF); 417 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI); 418 419 sandboxir::Context Ctx(C); 420 auto &F = *Ctx.createFunction(&LLVMF); 421 auto BB = F.begin(); 422 sandboxir::SeedCollector SC(&*BB, SE); 423 424 // Find the stores 425 auto It = std::next(BB->begin(), 3); 426 // StX with X as the order by offset in memory 427 auto *St1 = &*It++; 428 auto *St0 = &*It++; 429 430 auto StoreSeedsRange = SC.getStoreSeeds(); 431 EXPECT_EQ(range_size(StoreSeedsRange), 1u); 432 auto &SB = *StoreSeedsRange.begin(); 433 // isValidMemSeed check: The atomic and volatile stores should not 434 // be included in the bundle, but the vector stores should be. 435 ExpectThatElementsAre(SB, {St0, St1}); 436 } 437 438 TEST_F(SeedBundleTest, MixedScalarVectors) { 439 parseIR(C, R"IR( 440 define void @foo(ptr noalias %ptr, float %v, <2 x float> %val) { 441 bb: 442 %ptr0 = getelementptr float, ptr %ptr, i32 0 443 %ptr1 = getelementptr float, ptr %ptr, i32 1 444 %ptr3 = getelementptr float, ptr %ptr, i32 3 445 store float %v, ptr %ptr0 446 store float %v, ptr %ptr3 447 store <2 x float> %val, ptr %ptr1 448 ret void 449 } 450 )IR"); 451 Function &LLVMF = *M->getFunction("foo"); 452 DominatorTree DT(LLVMF); 453 TargetLibraryInfoImpl TLII; 454 TargetLibraryInfo TLI(TLII); 455 DataLayout DL(M->getDataLayout()); 456 LoopInfo LI(DT); 457 AssumptionCache AC(LLVMF); 458 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI); 459 460 sandboxir::Context Ctx(C); 461 auto &F = *Ctx.createFunction(&LLVMF); 462 auto BB = F.begin(); 463 sandboxir::SeedCollector SC(&*BB, SE); 464 465 // Find the stores 466 auto It = std::next(BB->begin(), 3); 467 // StX with X as the order by offset in memory 468 auto *St0 = &*It++; 469 auto *St3 = &*It++; 470 auto *St1 = &*It++; 471 472 auto StoreSeedsRange = SC.getStoreSeeds(); 473 EXPECT_EQ(range_size(StoreSeedsRange), 1u); 474 auto &SB = *StoreSeedsRange.begin(); 475 // isValidMemSeedCheck here: all of the three stores should be included. 476 ExpectThatElementsAre(SB, {St0, St1, St3}); 477 } 478 479 TEST_F(SeedBundleTest, VectorLoads) { 480 parseIR(C, R"IR( 481 define void @foo(ptr noalias %ptr, <2 x float> %val0) { 482 bb: 483 %ptr0 = getelementptr float, ptr %ptr, i32 0 484 %ptr1 = getelementptr float, ptr %ptr, i32 1 485 %r0 = load <2 x float>, ptr %ptr0 486 %r1 = load <2 x float>, ptr %ptr1 487 %r2 = load atomic i64, ptr %ptr0 unordered, align 8 488 %r3 = load volatile i64, ptr %ptr1 489 %r4 = load void()*, ptr %ptr1 490 491 ret void 492 } 493 )IR"); 494 Function &LLVMF = *M->getFunction("foo"); 495 DominatorTree DT(LLVMF); 496 TargetLibraryInfoImpl TLII; 497 TargetLibraryInfo TLI(TLII); 498 DataLayout DL(M->getDataLayout()); 499 LoopInfo LI(DT); 500 AssumptionCache AC(LLVMF); 501 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI); 502 503 sandboxir::Context Ctx(C); 504 auto &F = *Ctx.createFunction(&LLVMF); 505 auto BB = F.begin(); 506 sandboxir::SeedCollector SC(&*BB, SE); 507 508 // Find the loads 509 auto It = std::next(BB->begin(), 2); 510 // StX with X as the order by offset in memory 511 auto *Ld0 = cast<sandboxir::LoadInst>(&*It++); 512 auto *Ld1 = cast<sandboxir::LoadInst>(&*It++); 513 514 auto LoadSeedsRange = SC.getLoadSeeds(); 515 EXPECT_EQ(range_size(LoadSeedsRange), 2u); 516 auto &SB = *LoadSeedsRange.begin(); 517 // isValidMemSeed check: The atomic and volatile loads should not 518 // be included in the bundle, the vector stores should be, but the 519 // void-typed load should not. 520 ExpectThatElementsAre(SB, {Ld0, Ld1}); 521 } 522