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
30using namespace llvm;
31using namespace SPIRV;
32
33INITIALIZE_PASS_BEGIN(SPIRVConvergenceRegionAnalysisWrapperPass,
34 "convergence-region",
35 "SPIRV convergence regions analysis", true, true)
36INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
37INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
38INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
39INITIALIZE_PASS_END(SPIRVConvergenceRegionAnalysisWrapperPass,
40 "convergence-region", "SPIRV convergence regions analysis",
41 true, true)
42
43namespace {
44
45template <typename BasicBlockType, typename IntrinsicInstType>
46std::optional<IntrinsicInstType *>
47getConvergenceTokenInternal(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|.
81static 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
105std::optional<IntrinsicInst *>
106llvm::SPIRV::getConvergenceToken(BasicBlock *BB) {
107 return getConvergenceTokenInternal<BasicBlock, IntrinsicInst>(BB);
108}
109
110std::optional<const IntrinsicInst *>
111llvm::SPIRV::getConvergenceToken(const BasicBlock *BB) {
112 return getConvergenceTokenInternal<const BasicBlock, const IntrinsicInst>(BB);
113}
114
115ConvergenceRegion::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
127ConvergenceRegion::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
138void 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
148void 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
190namespace {
191class ConvergenceRegionAnalyzer {
192public:
193 ConvergenceRegionAnalyzer(Function &F, DominatorTree &DT, LoopInfo &LI)
194 : DT(DT), LI(LI), F(F) {}
195
196private:
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
283public:
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
322private:
323 DominatorTree &DT;
324 LoopInfo &LI;
325 Function &F;
326};
327} // anonymous namespace
328
329ConvergenceRegionInfo llvm::SPIRV::getConvergenceRegions(Function &F,
330 DominatorTree &DT,
331 LoopInfo &LI) {
332 ConvergenceRegionAnalyzer Analyzer(F, DT, LI);
333 return Analyzer.analyze();
334}
335
336char SPIRVConvergenceRegionAnalysisWrapperPass::ID = 0;
337
338SPIRVConvergenceRegionAnalysisWrapperPass::
339 SPIRVConvergenceRegionAnalysisWrapperPass()
340 : FunctionPass(ID) {}
341
342bool 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
351SPIRVConvergenceRegionAnalysis::Result
352SPIRVConvergenceRegionAnalysis::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
360AnalysisKey SPIRVConvergenceRegionAnalysis::Key;
361