566 lines · cpp
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-exception6//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 23using namespace llvm;24 25// TODO: gcc-10 has a bug that causes the below line not to compile due to some26// macro-magic in gunit in combination with a class with pure-virtual27// function. Once gcc-10 is no longer supported, replace this function with28// something like the following:29//30// EXPECT_THAT(SB, testing::ElementsAre(St0, St1, St2, St3));31static void32ExpectThatElementsAre(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 41struct 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.60class SeedBundleForTest : public sandboxir::SeedBundle {61public:62 using sandboxir::SeedBundle::SeedBundle;63 void insert(sandboxir::Instruction *I, ScalarEvolution &SE) override {64 insertAt(Seeds.end(), I);65 }66};67 68TEST_F(SeedBundleTest, SeedBundle) {69 parseIR(C, R"IR(70define void @foo(float %v0, i32 %i0, i16 %i1, i8 %i2) {71bb:72 %add0 = fadd float %v0, %v073 %add1 = fadd float %v0, %v074 %add2 = add i8 %i2, %i275 %add3 = add i16 %i1, %i176 %add4 = add i32 %i0, %i077 %add5 = add i16 %i1, %i178 %add6 = add i8 %i2, %i279 %add7 = add i8 %i2, %i280 ret void81}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 // Constructor94 SeedBundleForTest SBO(I0);95 EXPECT_EQ(*SBO.begin(), I0);96 // getNumUnusedBits after constructor97 EXPECT_EQ(SBO.getNumUnusedBits(), IOBits);98 // setUsed99 SBO.setUsed(I0);100 // allUsed101 EXPECT_TRUE(SBO.allUsed());102 // isUsed103 EXPECT_TRUE(SBO.isUsed(0));104 // getNumUnusedBits after setUsed105 EXPECT_EQ(SBO.getNumUnusedBits(), 0u);106 // insertAt107 SBO.insertAt(SBO.end(), I1);108 EXPECT_NE(*SBO.begin(), I1);109 // getNumUnusedBits after insertAt110 EXPECT_EQ(SBO.getNumUnusedBits(), IOBits);111 // allUsed112 EXPECT_FALSE(SBO.allUsed());113 // getFirstUnusedElement114 EXPECT_EQ(SBO.getFirstUnusedElementIdx(), 1u);115 116 SmallVector<sandboxir::Instruction *> Insts;117 // add2 through add7118 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 // Constructor131 SeedBundleForTest SB1(std::move(Seeds));132 // getNumUnusedBits after constructor133 EXPECT_EQ(SB1.getNumUnusedBits(), BundleBits);134 // setUsed with index135 SB1.setUsed(1);136 // getFirstUnusedElementIdx137 EXPECT_EQ(SB1.getFirstUnusedElementIdx(), 0u);138 SB1.setUsed(unsigned(0));139 // getFirstUnusedElementIdx not at end140 EXPECT_EQ(SB1.getFirstUnusedElementIdx(), 2u);141 142 // getSlice is (StartIdx, MaxVecRegBits, ForcePowerOf2). It's easier to143 // 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 case158 SB1.setUsed(3);159 auto Slice4 = SB1.getSlice(4, /* MaxVecRegBits */ 8,160 /* ForcePowerOf2 */ true);161 EXPECT_EQ(Slice4.size(), 0u);162}163 164TEST_F(SeedBundleTest, MemSeedBundle) {165 parseIR(C, R"IR(166define void @foo(ptr %ptrA, float %val, ptr %ptr) {167bb:168 %gep0 = getelementptr float, ptr %ptr, i32 0169 %gep1 = getelementptr float, ptr %ptr, i32 1170 %gep2 = getelementptr float, ptr %ptr, i32 3171 %gep3 = getelementptr float, ptr %ptr, i32 4172 store float %val, ptr %gep0173 store float %val, ptr %gep1174 store float %val, ptr %gep2175 store float %val, ptr %gep3176 177 load float, ptr %gep0178 load float, ptr %gep1179 load float, ptr %gep2180 load float, ptr %gep3181 182 ret void183}184)IR");185 Function &LLVMF = *M->getFunction("foo");186 187 DominatorTree DT(LLVMF);188 TargetLibraryInfoImpl TLII(M->getTargetTriple());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 order205 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 order212 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 225TEST_F(SeedBundleTest, Container) {226 parseIR(C, R"IR(227define void @foo(ptr %ptrA, float %val, ptr %ptrB) {228bb:229 %gepA0 = getelementptr float, ptr %ptrA, i32 0230 %gepA1 = getelementptr float, ptr %ptrA, i32 1231 %gepB0 = getelementptr float, ptr %ptrB, i32 0232 %gepB1 = getelementptr float, ptr %ptrB, i32 1233 store float %val, ptr %gepA0234 store float %val, ptr %gepA1235 store float %val, ptr %gepB0236 store float %val, ptr %gepB1237 ret void238}239)IR");240 Function &LLVMF = *M->getFunction("foo");241 242 DominatorTree DT(LLVMF);243 TargetLibraryInfoImpl TLII(M->getTargetTriple());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, /*AllowDiffTypes=*/false);263 SC.insert(S1, /*AllowDiffTypes=*/false);264 SC.insert(S2, /*AllowDiffTypes=*/false);265 SC.insert(S3, /*AllowDiffTypes=*/false);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 288TEST_F(SeedBundleTest, ConsecutiveStores) {289 // Where "Consecutive" means the stores address consecutive locations in290 // memory, but not in program order. Check to see that the collector puts them291 // in the proper order for vectorization.292 parseIR(C, R"IR(293define void @foo(ptr noalias %ptr, float %val) {294bb:295 %ptr0 = getelementptr float, ptr %ptr, i32 0296 %ptr1 = getelementptr float, ptr %ptr, i32 1297 %ptr2 = getelementptr float, ptr %ptr, i32 2298 %ptr3 = getelementptr float, ptr %ptr, i32 3299 store float %val, ptr %ptr0300 store float %val, ptr %ptr2301 store float %val, ptr %ptr1302 store float %val, ptr %ptr3303 ret void304}305)IR");306 Function &LLVMF = *M->getFunction("foo");307 DominatorTree DT(LLVMF);308 TargetLibraryInfoImpl TLII(M->getTargetTriple());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, /*CollectStores=*/true,319 /*CollectLoads=*/false);320 321 // Find the stores322 auto It = std::next(BB->begin(), 4);323 // StX with X as the order by offset in memory324 auto *St0 = &*It++;325 auto *St2 = &*It++;326 auto *St1 = &*It++;327 auto *St3 = &*It++;328 329 auto StoreSeedsRange = SC.getStoreSeeds();330 auto &SB = *StoreSeedsRange.begin();331 // Expect just one vector of store seeds332 EXPECT_EQ(range_size(StoreSeedsRange), 1u);333 ExpectThatElementsAre(SB, {St0, St1, St2, St3});334}335 336TEST_F(SeedBundleTest, StoresWithGaps) {337 parseIR(C, R"IR(338define void @foo(ptr noalias %ptr, float %val) {339bb:340 %ptr0 = getelementptr float, ptr %ptr, i32 0341 %ptr1 = getelementptr float, ptr %ptr, i32 3342 %ptr2 = getelementptr float, ptr %ptr, i32 5343 %ptr3 = getelementptr float, ptr %ptr, i32 7344 store float %val, ptr %ptr0345 store float %val, ptr %ptr2346 store float %val, ptr %ptr1347 store float %val, ptr %ptr3348 ret void349}350)IR");351 Function &LLVMF = *M->getFunction("foo");352 DominatorTree DT(LLVMF);353 TargetLibraryInfoImpl TLII(M->getTargetTriple());354 TargetLibraryInfo TLI(TLII);355 DataLayout DL(M->getDataLayout());356 LoopInfo LI(DT);357 AssumptionCache AC(LLVMF);358 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI);359 360 sandboxir::Context Ctx(C);361 auto &F = *Ctx.createFunction(&LLVMF);362 auto BB = F.begin();363 sandboxir::SeedCollector SC(&*BB, SE, /*CollectStores=*/true,364 /*CollectLoads=*/false);365 366 // Find the stores367 auto It = std::next(BB->begin(), 4);368 // StX with X as the order by offset in memory369 auto *St0 = &*It++;370 auto *St2 = &*It++;371 auto *St1 = &*It++;372 auto *St3 = &*It++;373 374 auto StoreSeedsRange = SC.getStoreSeeds();375 auto &SB = *StoreSeedsRange.begin();376 // Expect just one vector of store seeds377 EXPECT_EQ(range_size(StoreSeedsRange), 1u);378 ExpectThatElementsAre(SB, {St0, St1, St2, St3});379 // Check that the EraseInstr callback works.380 381 // TODO: Range_size counts fully used-bundles even though the iterator skips382 // them. Further, iterating over anything other than the Bundles in a383 // SeedContainer includes used seeds. So for now just check that removing all384 // the seeds from a bundle also empties the bundle.385 St0->eraseFromParent();386 St1->eraseFromParent();387 St2->eraseFromParent();388 St3->eraseFromParent();389 size_t nonEmptyBundleCount = 0;390 for (auto &B : SC.getStoreSeeds()) {391 (void)B;392 nonEmptyBundleCount++;393 }394 EXPECT_EQ(nonEmptyBundleCount, 0u);395}396 397TEST_F(SeedBundleTest, VectorStores) {398 parseIR(C, R"IR(399define void @foo(ptr noalias %ptr, <2 x float> %val0, i64 %val1) {400bb:401 %ptr0 = getelementptr float, ptr %ptr, i32 0402 %ptr1 = getelementptr float, ptr %ptr, i32 1403 %ptr2 = getelementptr i64, ptr %ptr, i32 2404 store <2 x float> %val0, ptr %ptr1405 store <2 x float> %val0, ptr %ptr0406 store atomic i64 %val1, ptr %ptr2 unordered, align 8407 store volatile i64 %val1, ptr %ptr2408 409 ret void410}411)IR");412 Function &LLVMF = *M->getFunction("foo");413 DominatorTree DT(LLVMF);414 TargetLibraryInfoImpl TLII(M->getTargetTriple());415 TargetLibraryInfo TLI(TLII);416 DataLayout DL(M->getDataLayout());417 LoopInfo LI(DT);418 AssumptionCache AC(LLVMF);419 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI);420 421 sandboxir::Context Ctx(C);422 auto &F = *Ctx.createFunction(&LLVMF);423 auto BB = F.begin();424 sandboxir::SeedCollector SC(&*BB, SE, /*CollectStores=*/true,425 /*CollectLoads=*/false);426 427 // Find the stores428 auto It = std::next(BB->begin(), 3);429 // StX with X as the order by offset in memory430 auto *St1 = &*It++;431 auto *St0 = &*It++;432 433 auto StoreSeedsRange = SC.getStoreSeeds();434 EXPECT_EQ(range_size(StoreSeedsRange), 1u);435 auto &SB = *StoreSeedsRange.begin();436 // isValidMemSeed check: The atomic and volatile stores should not437 // be included in the bundle, but the vector stores should be.438 ExpectThatElementsAre(SB, {St0, St1});439}440 441TEST_F(SeedBundleTest, MixedScalarVectors) {442 parseIR(C, R"IR(443define void @foo(ptr noalias %ptr, float %v, <2 x float> %val) {444bb:445 %ptr0 = getelementptr float, ptr %ptr, i32 0446 %ptr1 = getelementptr float, ptr %ptr, i32 1447 %ptr3 = getelementptr float, ptr %ptr, i32 3448 store float %v, ptr %ptr0449 store float %v, ptr %ptr3450 store <2 x float> %val, ptr %ptr1451 ret void452}453)IR");454 Function &LLVMF = *M->getFunction("foo");455 DominatorTree DT(LLVMF);456 TargetLibraryInfoImpl TLII(M->getTargetTriple());457 TargetLibraryInfo TLI(TLII);458 DataLayout DL(M->getDataLayout());459 LoopInfo LI(DT);460 AssumptionCache AC(LLVMF);461 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI);462 463 sandboxir::Context Ctx(C);464 auto &F = *Ctx.createFunction(&LLVMF);465 auto BB = F.begin();466 sandboxir::SeedCollector SC(&*BB, SE, /*CollectStores=*/true,467 /*CollectLoads=*/false);468 469 // Find the stores470 auto It = std::next(BB->begin(), 3);471 // StX with X as the order by offset in memory472 auto *St0 = &*It++;473 auto *St3 = &*It++;474 auto *St1 = &*It++;475 476 auto StoreSeedsRange = SC.getStoreSeeds();477 EXPECT_EQ(range_size(StoreSeedsRange), 1u);478 auto &SB = *StoreSeedsRange.begin();479 // isValidMemSeedCheck here: all of the three stores should be included.480 ExpectThatElementsAre(SB, {St0, St1, St3});481}482 483TEST_F(SeedBundleTest, DiffTypes) {484 parseIR(C, R"IR(485define void @foo(ptr noalias %ptr, i8 %v, i16 %v16) {486bb:487 %ptr0 = getelementptr i8, ptr %ptr, i32 0488 %ptr1 = getelementptr i8, ptr %ptr, i32 1489 %ptr3 = getelementptr i8, ptr %ptr, i32 3490 store i8 %v, ptr %ptr0491 store i8 %v, ptr %ptr3492 store i16 %v16, ptr %ptr1493 ret void494}495)IR");496 Function &LLVMF = *M->getFunction("foo");497 DominatorTree DT(LLVMF);498 TargetLibraryInfoImpl TLII(M->getTargetTriple());499 TargetLibraryInfo TLI(TLII);500 DataLayout DL(M->getDataLayout());501 LoopInfo LI(DT);502 AssumptionCache AC(LLVMF);503 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI);504 505 sandboxir::Context Ctx(C);506 auto &F = *Ctx.createFunction(&LLVMF);507 auto BB = F.begin();508 auto It = std::next(BB->begin(), 3);509 auto *St0 = &*It++;510 auto *St3 = &*It++;511 auto *St1 = &*It++;512 513 sandboxir::SeedCollector SC(&*BB, SE, /*CollectStores=*/true,514 /*CollectLoads=*/false, /*AllowDiffTypes=*/true);515 516 auto StoreSeedsRange = SC.getStoreSeeds();517 EXPECT_EQ(range_size(StoreSeedsRange), 1u);518 auto &SB = *StoreSeedsRange.begin();519 ExpectThatElementsAre(SB, {St0, St1, St3});520}521 522TEST_F(SeedBundleTest, VectorLoads) {523 parseIR(C, R"IR(524define void @foo(ptr noalias %ptr, <2 x float> %val0) {525bb:526 %ptr0 = getelementptr float, ptr %ptr, i32 0527 %ptr1 = getelementptr float, ptr %ptr, i32 1528 %r0 = load <2 x float>, ptr %ptr0529 %r1 = load <2 x float>, ptr %ptr1530 %r2 = load atomic i64, ptr %ptr0 unordered, align 8531 %r3 = load volatile i64, ptr %ptr1532 %r4 = load void()*, ptr %ptr1533 534 ret void535}536)IR");537 Function &LLVMF = *M->getFunction("foo");538 DominatorTree DT(LLVMF);539 TargetLibraryInfoImpl TLII(M->getTargetTriple());540 TargetLibraryInfo TLI(TLII);541 DataLayout DL(M->getDataLayout());542 LoopInfo LI(DT);543 AssumptionCache AC(LLVMF);544 ScalarEvolution SE(LLVMF, TLI, AC, DT, LI);545 546 sandboxir::Context Ctx(C);547 auto &F = *Ctx.createFunction(&LLVMF);548 auto BB = F.begin();549 sandboxir::SeedCollector SC(&*BB, SE, /*CollectStores=*/false,550 /*CollectLoads=*/true);551 552 // Find the loads553 auto It = std::next(BB->begin(), 2);554 // StX with X as the order by offset in memory555 auto *Ld0 = cast<sandboxir::LoadInst>(&*It++);556 auto *Ld1 = cast<sandboxir::LoadInst>(&*It++);557 558 auto LoadSeedsRange = SC.getLoadSeeds();559 EXPECT_EQ(range_size(LoadSeedsRange), 2u);560 auto &SB = *LoadSeedsRange.begin();561 // isValidMemSeed check: The atomic and volatile loads should not562 // be included in the bundle, the vector stores should be, but the563 // void-typed load should not.564 ExpectThatElementsAre(SB, {Ld0, Ld1});565}566