1 //===- SeedCollector.cpp -0000000-----------------------------------------===// 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/ADT/STLExtras.h" 11 #include "llvm/Analysis/LoopAccessAnalysis.h" 12 #include "llvm/Analysis/ValueTracking.h" 13 #include "llvm/IR/BasicBlock.h" 14 #include "llvm/IR/Type.h" 15 #include "llvm/SandboxIR/Instruction.h" 16 #include "llvm/SandboxIR/Utils.h" 17 #include "llvm/Support/Debug.h" 18 19 using namespace llvm; 20 namespace llvm::sandboxir { 21 22 cl::opt<unsigned> SeedBundleSizeLimit( 23 "sbvec-seed-bundle-size-limit", cl::init(32), cl::Hidden, 24 cl::desc("Limit the size of the seed bundle to cap compilation time.")); 25 26 MutableArrayRef<Instruction *> SeedBundle::getSlice(unsigned StartIdx, 27 unsigned MaxVecRegBits, 28 bool ForcePowerOf2) { 29 // Use uint32_t here for compatibility with IsPowerOf2_32 30 31 // BitCount tracks the size of the working slice. From that we can tell 32 // when the working slice's size is a power-of-two and when it exceeds 33 // the legal size in MaxVecBits. 34 uint32_t BitCount = 0; 35 uint32_t NumElements = 0; 36 // Tracks the most recent slice where NumElements gave a power-of-2 BitCount 37 uint32_t NumElementsPowerOfTwo = 0; 38 uint32_t BitCountPowerOfTwo = 0; 39 // Can't start a slice with a used instruction. 40 assert(!isUsed(StartIdx) && "Expected unused at StartIdx"); 41 for (auto S : make_range(Seeds.begin() + StartIdx, Seeds.end())) { 42 uint32_t InstBits = Utils::getNumBits(S); 43 // Stop if this instruction is used, or if adding it puts the slice over 44 // the limit. 45 if (isUsed(StartIdx + NumElements) || BitCount + InstBits > MaxVecRegBits) 46 break; 47 NumElements++; 48 BitCount += InstBits; 49 if (ForcePowerOf2 && isPowerOf2_32(BitCount)) { 50 NumElementsPowerOfTwo = NumElements; 51 BitCountPowerOfTwo = BitCount; 52 } 53 } 54 if (ForcePowerOf2) { 55 NumElements = NumElementsPowerOfTwo; 56 BitCount = BitCountPowerOfTwo; 57 } 58 59 assert((!ForcePowerOf2 || isPowerOf2_32(BitCount)) && 60 "Must be a power of two"); 61 // Return any non-empty slice 62 if (NumElements > 1) 63 return MutableArrayRef<Instruction *>(&Seeds[StartIdx], NumElements); 64 else 65 return {}; 66 } 67 68 template <typename LoadOrStoreT> 69 SeedContainer::KeyT SeedContainer::getKey(LoadOrStoreT *LSI) const { 70 assert((isa<LoadInst>(LSI) || isa<StoreInst>(LSI)) && 71 "Expected Load or Store!"); 72 Value *Ptr = Utils::getMemInstructionBase(LSI); 73 Instruction::Opcode Op = LSI->getOpcode(); 74 Type *Ty = Utils::getExpectedType(LSI); 75 if (auto *VTy = dyn_cast<VectorType>(Ty)) 76 Ty = VTy->getElementType(); 77 return {Ptr, Ty, Op}; 78 } 79 80 // Explicit instantiations 81 template SeedContainer::KeyT 82 SeedContainer::getKey<LoadInst>(LoadInst *LSI) const; 83 template SeedContainer::KeyT 84 SeedContainer::getKey<StoreInst>(StoreInst *LSI) const; 85 86 bool SeedContainer::erase(Instruction *I) { 87 assert((isa<LoadInst>(I) || isa<StoreInst>(I)) && "Expected Load or Store!"); 88 auto It = SeedLookupMap.find(I); 89 if (It == SeedLookupMap.end()) 90 return false; 91 SeedBundle *Bndl = It->second; 92 Bndl->setUsed(I); 93 return true; 94 } 95 96 template <typename LoadOrStoreT> void SeedContainer::insert(LoadOrStoreT *LSI) { 97 // Find the bundle containing seeds for this symbol and type-of-access. 98 auto &BundleVec = Bundles[getKey(LSI)]; 99 // Fill this vector of bundles front to back so that only the last bundle in 100 // the vector may have available space. This avoids iteration to find one with 101 // space. 102 if (BundleVec.empty() || BundleVec.back()->size() == SeedBundleSizeLimit) 103 BundleVec.emplace_back(std::make_unique<MemSeedBundle<LoadOrStoreT>>(LSI)); 104 else 105 BundleVec.back()->insert(LSI, SE); 106 107 SeedLookupMap[LSI] = BundleVec.back().get(); 108 } 109 110 // Explicit instantiations 111 template void SeedContainer::insert<LoadInst>(LoadInst *); 112 template void SeedContainer::insert<StoreInst>(StoreInst *); 113 114 #ifndef NDEBUG 115 void SeedContainer::dump() const { 116 for (const auto &Pair : Bundles) { 117 auto [I, Ty, Opc] = Pair.first; 118 const auto &SeedsVec = Pair.second; 119 std::string RefType = dyn_cast<LoadInst>(I) ? "Load" 120 : dyn_cast<StoreInst>(I) ? "Store" 121 : "Other"; 122 dbgs() << "[Inst=" << *I << " Ty=" << Ty << " " << RefType << "]\n"; 123 for (const auto &SeedPtr : SeedsVec) { 124 SeedPtr->dump(dbgs()); 125 dbgs() << "\n"; 126 } 127 } 128 dbgs() << "\n"; 129 } 130 #endif // NDEBUG 131 132 } // namespace llvm::sandboxir 133