LLVM: lib/Target/SPIRV/Analysis/SPIRVConvergenceRegionAnalysis.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
22#include
23#include
24#include <unordered_set>
25
26#define DEBUG_TYPE "spirv-convergence-region-analysis"
27
28using namespace llvm;
29using namespace SPIRV;
30
32 "convergence-region",
33 "SPIRV convergence regions analysis", true, true)
38 "convergence-region", "SPIRV convergence regions analysis",
40
41namespace {
42
43template <typename BasicBlockType, typename IntrinsicInstType>
44std::optional<IntrinsicInstType *>
46 static_assert(std::is_const_v ==
47 std::is_const_v,
48 "Constness must match between input and output.");
49 static_assert(std::is_same_v<BasicBlock, std::remove_const_t>,
50 "Input must be a basic block.");
51 static_assert(
52 std::is_same_v<IntrinsicInst, std::remove_const_t>,
53 "Output type must be an intrinsic instruction.");
54
55 for (auto &I : *BB) {
57
58
59 assert(CI->isLoop() ||
61 return CI;
62 }
63
66 if (!OB.has_value())
67 continue;
69 }
70 }
71
72 return std::nullopt;
73}
74}
75
76
77
78
83
84 while (Candidate != NextCandidate && NextCandidate != nullptr) {
85 Candidate = NextCandidate;
86 NextCandidate = nullptr;
87
88
89 if (Candidate->Children.size() == 0)
90 return Candidate;
91
92 for (auto *Child : Candidate->Children) {
93 if (Child->Blocks.count(Entry) != 0) {
94 NextCandidate = Child;
95 break;
96 }
97 }
98 }
99
100 return Candidate;
101}
102
103std::optional<IntrinsicInst *>
105 return getConvergenceTokenInternal<BasicBlock, IntrinsicInst>(BB);
106}
107
108std::optional<const IntrinsicInst *>
110 return getConvergenceTokenInternal<const BasicBlock, const IntrinsicInst>(BB);
111}
112
115 : DT(DT), LI(LI), Parent(nullptr) {
116 Entry = &F.getEntryBlock();
122 }
123}
124
131 for ([[maybe_unused]] auto *BB : this->Exits)
133 assert(this->Blocks.count(this->Entry) != 0);
134}
135
137
139 for (auto *Child : Children) {
140 Child->releaseMemory();
141 delete Child;
142 }
144}
145
147 const std::string Indent(IndentSize, '\t');
148 dbgs() << Indent << this << ": {\n";
149 dbgs() << Indent << " Parent: " << Parent << "\n";
150
152 dbgs() << Indent
153 << " ConvergenceToken: " << ConvergenceToken.value()->getName()
154 << "\n";
155 }
156
157 if (Entry->getName() != "")
158 dbgs() << Indent << " Entry: " << Entry->getName() << "\n";
159 else
160 dbgs() << Indent << " Entry: " << Entry << "\n";
161
162 dbgs() << Indent << " Exits: { ";
163 for (const auto &Exit : Exits) {
164 if (Exit->getName() != "")
165 dbgs() << Exit->getName() << ", ";
166 else
167 dbgs() << Exit << ", ";
168 }
169 dbgs() << " }\n";
170
171 dbgs() << Indent << " Blocks: { ";
173 if (Block->getName() != "")
174 dbgs() << Block->getName() << ", ";
175 else
177 }
178 dbgs() << " }\n";
179
180 dbgs() << Indent << " Children: {\n";
181 for (const auto Child : Children)
182 Child->dump(IndentSize + 2);
183 dbgs() << Indent << " }\n";
184
185 dbgs() << Indent << "}\n";
186}
187
188namespace {
189class ConvergenceRegionAnalyzer {
190public:
193
194private:
196 if (From == To)
197 return true;
198
199
200
201
202
203 if (!LI.isLoopHeader(To))
204 return false;
205
206 auto *L = LI.getLoopFor(To);
207 if (L->contains(From) && L->isLoopLatch(From))
208 return true;
209
210 return false;
211 }
212
213 std::unordered_set<BasicBlock *>
215 std::function<bool(const BasicBlock *)> isMatch) const {
216 std::unordered_set<BasicBlock *> Output;
217
218 if (isMatch(From))
219 Output.insert(From);
220
222 for (unsigned i = 0; i < Terminator->getNumSuccessors(); ++i) {
223 auto *To = Terminator->getSuccessor(i);
224
225 if (isBackEdge(From, To))
226 continue;
227
228 auto ChildSet = findPathsToMatch(LI, To, isMatch);
229 if (ChildSet.size() == 0)
230 continue;
231
232 Output.insert(ChildSet.begin(), ChildSet.end());
233 Output.insert(From);
236 for (auto *BB : L->getBlocks()) {
237 Output.insert(BB);
238 }
239 }
240 }
241
242 return Output;
243 }
244
245 SmallPtrSet<BasicBlock *, 2>
246 findExitNodes(const SmallPtrSetImpl<BasicBlock *> &RegionBlocks) {
247 SmallPtrSet<BasicBlock *, 2> Exits;
248
249 for (auto *B : RegionBlocks) {
251 for (unsigned i = 0; i < Terminator->getNumSuccessors(); ++i) {
252 auto *Child = Terminator->getSuccessor(i);
253 if (RegionBlocks.count(Child) == 0)
255 }
256 }
257
258 return Exits;
259 }
260
261public:
262 ConvergenceRegionInfo analyze() {
263 ConvergenceRegion *TopLevelRegion = new ConvergenceRegion(DT, LI, F);
264 std::queue<Loop *> ToProcess;
266 ToProcess.push(L);
267
268 while (ToProcess.size() != 0) {
269 auto *L = ToProcess.front();
270 ToProcess.pop();
271
273 SmallPtrSet<BasicBlock *, 8> RegionBlocks(llvm::from_range, L->blocks());
275 L->getExitingBlocks(LoopExits);
276 if (CT.has_value()) {
277 for (auto *Exit : LoopExits) {
278 auto N = findPathsToMatch(LI, Exit, [&CT](const BasicBlock *block) {
280 if (Token == std::nullopt)
281 return false;
282 return Token.value() == CT.value();
283 });
284 RegionBlocks.insert_range(N);
285 }
286 }
287
288 auto RegionExits = findExitNodes(RegionBlocks);
289 ConvergenceRegion *Region = new ConvergenceRegion(
290 DT, LI, CT, L->getHeader(), std::move(RegionBlocks),
291 std::move(RegionExits));
293 assert(Region->Parent != nullptr && "This is impossible.");
294 Region->Parent->Children.push_back(Region);
295 }
296
297 return ConvergenceRegionInfo(TopLevelRegion);
298 }
299
300private:
301 DominatorTree &DT;
302 LoopInfo &LI;
304};
305}
306
310 ConvergenceRegionAnalyzer Analyzer(F, DT, LI);
311 return Analyzer.analyze();
312}
313
315
319
323
325
326 return false;
327}
328
337
338AnalysisKey SPIRVConvergenceRegionAnalysis::Key;
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static ConvergenceRegion * findParentRegion(ConvergenceRegion *Start, BasicBlock *Entry)
Definition SPIRVConvergenceRegionAnalysis.cpp:79
unify loop Fixup each natural loop to have a single exit block
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
LLVM Basic Block Representation.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Analysis pass that exposes the LoopInfo for a function.
bool isLoopHeader(const BlockT *BB) const
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
AnalysisType & getAnalysis() const
getAnalysis() - This function is used by subclasses to get to the analysis information ...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition SPIRVConvergenceRegionAnalysis.cpp:320
SPIRVConvergenceRegionAnalysisWrapperPass()
Definition SPIRVConvergenceRegionAnalysis.cpp:317
Result run(Function &F, FunctionAnalysisManager &AM)
Definition SPIRVConvergenceRegionAnalysis.cpp:330
SPIRV::ConvergenceRegionInfo Result
SmallVector< ConvergenceRegion * > Children
ConvergenceRegion(DominatorTree &DT, LoopInfo &LI, Function &F)
Definition SPIRVConvergenceRegionAnalysis.cpp:113
void dump(const unsigned IndentSize=0) const
Definition SPIRVConvergenceRegionAnalysis.cpp:146
void releaseMemory()
Definition SPIRVConvergenceRegionAnalysis.cpp:136
SmallPtrSet< BasicBlock *, 2 > Exits
std::optional< IntrinsicInst * > ConvergenceToken
ConvergenceRegion * Parent
SmallPtrSet< BasicBlock *, 8 > Blocks
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
ConvergenceRegionInfo getConvergenceRegions(Function &F, DominatorTree &DT, LoopInfo &LI)
Definition SPIRVConvergenceRegionAnalysis.cpp:307
std::optional< IntrinsicInst * > getConvergenceToken(BasicBlock *BB)
Definition SPIRVConvergenceRegionAnalysis.cpp:104
This is an optimization pass for GlobalISel generic memory operations.
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
constexpr from_range_t from_range
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Implement std::hash so that hash_code can be used in STL containers.
std::optional< IntrinsicInstType * > getConvergenceTokenInternal(BasicBlockType *BB)
Definition SPIRVConvergenceRegionAnalysis.cpp:45
A special type used by analysis passes to provide an address that identifies that particular analysis...