| 1 | //===----------------------------------------------------------------------===// |
| 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 | // The analysis determines the convergence region for each basic block of |
| 10 | // the module, and provides a tree-like structure describing the region |
| 11 | // hierarchy. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "SPIRVConvergenceRegionAnalysis.h" |
| 16 | #include "SPIRV.h" |
| 17 | #include "llvm/ADT/PostOrderIterator.h" |
| 18 | #include "llvm/ADT/SmallPtrSet.h" |
| 19 | #include "llvm/ADT/SmallVector.h" |
| 20 | #include "llvm/Analysis/LoopInfo.h" |
| 21 | #include "llvm/IR/Dominators.h" |
| 22 | #include "llvm/IR/IntrinsicInst.h" |
| 23 | #include "llvm/InitializePasses.h" |
| 24 | #include "llvm/Transforms/Utils/LoopSimplify.h" |
| 25 | #include <optional> |
| 26 | #include <queue> |
| 27 | |
| 28 | #define DEBUG_TYPE "spirv-convergence-region-analysis" |
| 29 | |
| 30 | using namespace llvm; |
| 31 | using namespace SPIRV; |
| 32 | |
| 33 | INITIALIZE_PASS_BEGIN(SPIRVConvergenceRegionAnalysisWrapperPass, |
| 34 | "convergence-region" , |
| 35 | "SPIRV convergence regions analysis" , true, true) |
| 36 | INITIALIZE_PASS_DEPENDENCY(LoopSimplify) |
| 37 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
| 38 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) |
| 39 | INITIALIZE_PASS_END(SPIRVConvergenceRegionAnalysisWrapperPass, |
| 40 | "convergence-region" , "SPIRV convergence regions analysis" , |
| 41 | true, true) |
| 42 | |
| 43 | namespace { |
| 44 | |
| 45 | template <typename BasicBlockType, typename IntrinsicInstType> |
| 46 | std::optional<IntrinsicInstType *> |
| 47 | getConvergenceTokenInternal(BasicBlockType *BB) { |
| 48 | static_assert(std::is_const_v<IntrinsicInstType> == |
| 49 | std::is_const_v<BasicBlockType>, |
| 50 | "Constness must match between input and output." ); |
| 51 | static_assert(std::is_same_v<BasicBlock, std::remove_const_t<BasicBlockType>>, |
| 52 | "Input must be a basic block." ); |
| 53 | static_assert( |
| 54 | std::is_same_v<IntrinsicInst, std::remove_const_t<IntrinsicInstType>>, |
| 55 | "Output type must be an intrinsic instruction." ); |
| 56 | |
| 57 | for (auto &I : *BB) { |
| 58 | if (auto *CI = dyn_cast<ConvergenceControlInst>(&I)) { |
| 59 | // Make sure that the anchor or entry intrinsics did not reach here with a |
| 60 | // parent token. This should have failed the verifier. |
| 61 | assert(CI->isLoop() || |
| 62 | !CI->getOperandBundle(LLVMContext::OB_convergencectrl)); |
| 63 | return CI; |
| 64 | } |
| 65 | |
| 66 | if (auto *CI = dyn_cast<CallInst>(&I)) { |
| 67 | auto OB = CI->getOperandBundle(LLVMContext::OB_convergencectrl); |
| 68 | if (!OB.has_value()) |
| 69 | continue; |
| 70 | return dyn_cast<IntrinsicInst>(OB.value().Inputs[0]); |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | return std::nullopt; |
| 75 | } |
| 76 | } // anonymous namespace |
| 77 | |
| 78 | // Given a ConvergenceRegion tree with |Start| as its root, finds the smallest |
| 79 | // region |Entry| belongs to. If |Entry| does not belong to the region defined |
| 80 | // by |Start|, this function returns |nullptr|. |
| 81 | static ConvergenceRegion *findParentRegion(ConvergenceRegion *Start, |
| 82 | BasicBlock *Entry) { |
| 83 | ConvergenceRegion *Candidate = nullptr; |
| 84 | ConvergenceRegion *NextCandidate = Start; |
| 85 | |
| 86 | while (Candidate != NextCandidate && NextCandidate != nullptr) { |
| 87 | Candidate = NextCandidate; |
| 88 | NextCandidate = nullptr; |
| 89 | |
| 90 | // End of the search, we can return. |
| 91 | if (Candidate->Children.size() == 0) |
| 92 | return Candidate; |
| 93 | |
| 94 | for (auto *Child : Candidate->Children) { |
| 95 | if (Child->Blocks.count(Ptr: Entry) != 0) { |
| 96 | NextCandidate = Child; |
| 97 | break; |
| 98 | } |
| 99 | } |
| 100 | } |
| 101 | |
| 102 | return Candidate; |
| 103 | } |
| 104 | |
| 105 | std::optional<IntrinsicInst *> |
| 106 | llvm::SPIRV::getConvergenceToken(BasicBlock *BB) { |
| 107 | return getConvergenceTokenInternal<BasicBlock, IntrinsicInst>(BB); |
| 108 | } |
| 109 | |
| 110 | std::optional<const IntrinsicInst *> |
| 111 | llvm::SPIRV::getConvergenceToken(const BasicBlock *BB) { |
| 112 | return getConvergenceTokenInternal<const BasicBlock, const IntrinsicInst>(BB); |
| 113 | } |
| 114 | |
| 115 | ConvergenceRegion::ConvergenceRegion(DominatorTree &DT, LoopInfo &LI, |
| 116 | Function &F) |
| 117 | : DT(DT), LI(LI), Parent(nullptr) { |
| 118 | Entry = &F.getEntryBlock(); |
| 119 | ConvergenceToken = getConvergenceToken(BB: Entry); |
| 120 | for (auto &B : F) { |
| 121 | Blocks.insert(Ptr: &B); |
| 122 | if (isa<ReturnInst>(Val: B.getTerminator())) |
| 123 | Exits.insert(Ptr: &B); |
| 124 | } |
| 125 | } |
| 126 | |
| 127 | ConvergenceRegion::ConvergenceRegion( |
| 128 | DominatorTree &DT, LoopInfo &LI, |
| 129 | std::optional<IntrinsicInst *> ConvergenceToken, BasicBlock *Entry, |
| 130 | SmallPtrSet<BasicBlock *, 8> &&Blocks, SmallPtrSet<BasicBlock *, 2> &&Exits) |
| 131 | : DT(DT), LI(LI), ConvergenceToken(ConvergenceToken), Entry(Entry), |
| 132 | Exits(std::move(Exits)), Blocks(std::move(Blocks)) { |
| 133 | for ([[maybe_unused]] auto *BB : this->Exits) |
| 134 | assert(this->Blocks.count(BB) != 0); |
| 135 | assert(this->Blocks.count(this->Entry) != 0); |
| 136 | } |
| 137 | |
| 138 | void ConvergenceRegion::releaseMemory() { |
| 139 | // Parent memory is owned by the parent. |
| 140 | Parent = nullptr; |
| 141 | for (auto *Child : Children) { |
| 142 | Child->releaseMemory(); |
| 143 | delete Child; |
| 144 | } |
| 145 | Children.resize(N: 0); |
| 146 | } |
| 147 | |
| 148 | void ConvergenceRegion::dump(const unsigned IndentSize) const { |
| 149 | const std::string Indent(IndentSize, '\t'); |
| 150 | dbgs() << Indent << this << ": {\n" ; |
| 151 | dbgs() << Indent << " Parent: " << Parent << "\n" ; |
| 152 | |
| 153 | if (ConvergenceToken.value_or(u: nullptr)) { |
| 154 | dbgs() << Indent |
| 155 | << " ConvergenceToken: " << ConvergenceToken.value()->getName() |
| 156 | << "\n" ; |
| 157 | } |
| 158 | |
| 159 | if (Entry->getName() != "" ) |
| 160 | dbgs() << Indent << " Entry: " << Entry->getName() << "\n" ; |
| 161 | else |
| 162 | dbgs() << Indent << " Entry: " << Entry << "\n" ; |
| 163 | |
| 164 | dbgs() << Indent << " Exits: { " ; |
| 165 | for (const auto &Exit : Exits) { |
| 166 | if (Exit->getName() != "" ) |
| 167 | dbgs() << Exit->getName() << ", " ; |
| 168 | else |
| 169 | dbgs() << Exit << ", " ; |
| 170 | } |
| 171 | dbgs() << " }\n" ; |
| 172 | |
| 173 | dbgs() << Indent << " Blocks: { " ; |
| 174 | for (const auto &Block : Blocks) { |
| 175 | if (Block->getName() != "" ) |
| 176 | dbgs() << Block->getName() << ", " ; |
| 177 | else |
| 178 | dbgs() << Block << ", " ; |
| 179 | } |
| 180 | dbgs() << " }\n" ; |
| 181 | |
| 182 | dbgs() << Indent << " Children: {\n" ; |
| 183 | for (const auto Child : Children) |
| 184 | Child->dump(IndentSize: IndentSize + 2); |
| 185 | dbgs() << Indent << " }\n" ; |
| 186 | |
| 187 | dbgs() << Indent << "}\n" ; |
| 188 | } |
| 189 | |
| 190 | namespace { |
| 191 | class ConvergenceRegionAnalyzer { |
| 192 | public: |
| 193 | ConvergenceRegionAnalyzer(Function &F, DominatorTree &DT, LoopInfo &LI) |
| 194 | : DT(DT), LI(LI), F(F) {} |
| 195 | |
| 196 | private: |
| 197 | bool isBackEdge(const BasicBlock *From, const BasicBlock *To) const { |
| 198 | if (From == To) |
| 199 | return true; |
| 200 | |
| 201 | // We only handle loop in the simplified form. This means: |
| 202 | // - a single back-edge, a single latch. |
| 203 | // - meaning the back-edge target can only be the loop header. |
| 204 | // - meaning the From can only be the loop latch. |
| 205 | if (!LI.isLoopHeader(BB: To)) |
| 206 | return false; |
| 207 | |
| 208 | auto *L = LI.getLoopFor(BB: To); |
| 209 | if (L->contains(BB: From) && L->isLoopLatch(BB: From)) |
| 210 | return true; |
| 211 | |
| 212 | return false; |
| 213 | } |
| 214 | |
| 215 | class ForwardPostOrderTraversal |
| 216 | : public PostOrderTraversalBase<ForwardPostOrderTraversal, |
| 217 | GraphTraits<BasicBlock *>> { |
| 218 | const ConvergenceRegionAnalyzer &Analyzer; |
| 219 | |
| 220 | public: |
| 221 | ForwardPostOrderTraversal(const ConvergenceRegionAnalyzer &Analyzer, |
| 222 | BasicBlock *From) |
| 223 | : Analyzer(Analyzer) { |
| 224 | init(Start: From); |
| 225 | } |
| 226 | |
| 227 | bool insertEdge(std::optional<BasicBlock *> From, BasicBlock *To) { |
| 228 | return !(From && Analyzer.isBackEdge(From: *From, To)) && |
| 229 | Visited.insert(Ptr: To).second; |
| 230 | } |
| 231 | |
| 232 | private: |
| 233 | SmallPtrSet<BasicBlock *, 16> Visited; |
| 234 | }; |
| 235 | |
| 236 | SmallPtrSet<BasicBlock *, 0> |
| 237 | findPathsToMatch(LoopInfo &LI, BasicBlock *From, |
| 238 | std::function<bool(const BasicBlock *)> isMatch) const { |
| 239 | ForwardPostOrderTraversal Traversal(*this, From); |
| 240 | |
| 241 | // Postorder visits successors before predecessors, so reachability to a |
| 242 | // match propagates in one linear scan instead of per-path recursion. |
| 243 | SmallPtrSet<BasicBlock *, 0> Output; |
| 244 | for (auto *BB : Traversal) { |
| 245 | bool ReachesMatch = false; |
| 246 | auto *Terminator = BB->getTerminator(); |
| 247 | for (unsigned i = 0; i < Terminator->getNumSuccessors(); ++i) { |
| 248 | auto *To = Terminator->getSuccessor(Idx: i); |
| 249 | if (!isBackEdge(From: BB, To) && Output.contains(Ptr: To)) |
| 250 | ReachesMatch = true; |
| 251 | } |
| 252 | |
| 253 | if (isMatch(BB) || ReachesMatch) |
| 254 | Output.insert(Ptr: BB); |
| 255 | |
| 256 | // A qualifying path through a loop header brings in the whole loop. |
| 257 | if (ReachesMatch && LI.isLoopHeader(BB)) { |
| 258 | auto *L = LI.getLoopFor(BB); |
| 259 | for (auto *LoopBB : L->getBlocks()) |
| 260 | Output.insert(Ptr: LoopBB); |
| 261 | } |
| 262 | } |
| 263 | |
| 264 | return Output; |
| 265 | } |
| 266 | |
| 267 | SmallPtrSet<BasicBlock *, 2> |
| 268 | findExitNodes(const SmallPtrSetImpl<BasicBlock *> &RegionBlocks) { |
| 269 | SmallPtrSet<BasicBlock *, 2> Exits; |
| 270 | |
| 271 | for (auto *B : RegionBlocks) { |
| 272 | auto *Terminator = B->getTerminator(); |
| 273 | for (unsigned i = 0; i < Terminator->getNumSuccessors(); ++i) { |
| 274 | auto *Child = Terminator->getSuccessor(Idx: i); |
| 275 | if (RegionBlocks.count(Ptr: Child) == 0) |
| 276 | Exits.insert(Ptr: B); |
| 277 | } |
| 278 | } |
| 279 | |
| 280 | return Exits; |
| 281 | } |
| 282 | |
| 283 | public: |
| 284 | ConvergenceRegionInfo analyze() { |
| 285 | ConvergenceRegion *TopLevelRegion = new ConvergenceRegion(DT, LI, F); |
| 286 | std::queue<Loop *> ToProcess; |
| 287 | for (auto *L : LI.getLoopsInPreorder()) |
| 288 | ToProcess.push(x: L); |
| 289 | |
| 290 | while (ToProcess.size() != 0) { |
| 291 | auto *L = ToProcess.front(); |
| 292 | ToProcess.pop(); |
| 293 | |
| 294 | auto CT = getConvergenceToken(BB: L->getHeader()); |
| 295 | SmallPtrSet<BasicBlock *, 8> RegionBlocks(llvm::from_range, L->blocks()); |
| 296 | SmallVector<BasicBlock *> LoopExits; |
| 297 | L->getExitingBlocks(ExitingBlocks&: LoopExits); |
| 298 | if (CT.has_value()) { |
| 299 | for (auto *Exit : LoopExits) { |
| 300 | auto N = findPathsToMatch(LI, From: Exit, isMatch: [&CT](const BasicBlock *block) { |
| 301 | auto Token = getConvergenceToken(BB: block); |
| 302 | if (Token == std::nullopt) |
| 303 | return false; |
| 304 | return Token.value() == CT.value(); |
| 305 | }); |
| 306 | RegionBlocks.insert_range(R&: N); |
| 307 | } |
| 308 | } |
| 309 | |
| 310 | auto RegionExits = findExitNodes(RegionBlocks); |
| 311 | ConvergenceRegion *Region = new ConvergenceRegion( |
| 312 | DT, LI, CT, L->getHeader(), std::move(RegionBlocks), |
| 313 | std::move(RegionExits)); |
| 314 | Region->Parent = findParentRegion(Start: TopLevelRegion, Entry: Region->Entry); |
| 315 | assert(Region->Parent != nullptr && "This is impossible." ); |
| 316 | Region->Parent->Children.push_back(Elt: Region); |
| 317 | } |
| 318 | |
| 319 | return ConvergenceRegionInfo(TopLevelRegion); |
| 320 | } |
| 321 | |
| 322 | private: |
| 323 | DominatorTree &DT; |
| 324 | LoopInfo &LI; |
| 325 | Function &F; |
| 326 | }; |
| 327 | } // anonymous namespace |
| 328 | |
| 329 | ConvergenceRegionInfo llvm::SPIRV::getConvergenceRegions(Function &F, |
| 330 | DominatorTree &DT, |
| 331 | LoopInfo &LI) { |
| 332 | ConvergenceRegionAnalyzer Analyzer(F, DT, LI); |
| 333 | return Analyzer.analyze(); |
| 334 | } |
| 335 | |
| 336 | char SPIRVConvergenceRegionAnalysisWrapperPass::ID = 0; |
| 337 | |
| 338 | SPIRVConvergenceRegionAnalysisWrapperPass:: |
| 339 | SPIRVConvergenceRegionAnalysisWrapperPass() |
| 340 | : FunctionPass(ID) {} |
| 341 | |
| 342 | bool SPIRVConvergenceRegionAnalysisWrapperPass::runOnFunction(Function &F) { |
| 343 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
| 344 | LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
| 345 | |
| 346 | CRI = SPIRV::getConvergenceRegions(F, DT, LI); |
| 347 | // Nothing was modified. |
| 348 | return false; |
| 349 | } |
| 350 | |
| 351 | SPIRVConvergenceRegionAnalysis::Result |
| 352 | SPIRVConvergenceRegionAnalysis::run(Function &F, FunctionAnalysisManager &AM) { |
| 353 | Result CRI; |
| 354 | auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F); |
| 355 | auto &LI = AM.getResult<LoopAnalysis>(IR&: F); |
| 356 | CRI = SPIRV::getConvergenceRegions(F, DT, LI); |
| 357 | return CRI; |
| 358 | } |
| 359 | |
| 360 | AnalysisKey SPIRVConvergenceRegionAnalysis::Key; |
| 361 | |