LLVM 20.0.0git
SPIRVConvergenceRegionAnalysis.h
Go to the documentation of this file.
1//===- SPIRVConvergenceRegionAnalysis.h ------------------------*- C++ -*--===//
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#ifndef LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H
16#define LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H
17
19#include "llvm/Analysis/CFG.h"
21#include "llvm/IR/Dominators.h"
23#include <iostream>
24#include <optional>
25#include <unordered_set>
26
27namespace llvm {
28class SPIRVSubtarget;
29class MachineFunction;
30class MachineModuleInfo;
31
32namespace SPIRV {
33
34// Returns the first convergence intrinsic found in |BB|, |nullopt| otherwise.
35std::optional<IntrinsicInst *> getConvergenceToken(BasicBlock *BB);
36std::optional<const IntrinsicInst *> getConvergenceToken(const BasicBlock *BB);
37
38// Describes a hierarchy of convergence regions.
39// A convergence region defines a CFG for which the execution flow can diverge
40// starting from the entry block, but should reconverge back before the end of
41// the exit blocks.
43 DominatorTree &DT;
44 LoopInfo &LI;
45
46public:
47 // The parent region of this region, if any.
49 // The sub-regions contained in this region, if any.
51 // The convergence instruction linked to this region, if any.
52 std::optional<IntrinsicInst *> ConvergenceToken = std::nullopt;
53 // The only block with a predecessor outside of this region.
54 BasicBlock *Entry = nullptr;
55 // All the blocks with an edge leaving this convergence region.
57 // All the blocks that belongs to this region, including its subregions'.
59
60 // Creates a single convergence region encapsulating the whole function |F|.
62
63 // Creates a single convergence region defined by entry and exits nodes, a
64 // list of blocks, and possibly a convergence token.
66 std::optional<IntrinsicInst *> ConvergenceToken,
69
71 : DT(CR.DT), LI(CR.LI), Parent(std::move(CR.Parent)),
74 Entry(std::move(CR.Entry)), Exits(std::move(CR.Exits)),
75 Blocks(std::move(CR.Blocks)) {}
76
77 ConvergenceRegion(const ConvergenceRegion &other) = delete;
78
79 // Returns true if the given basic block belongs to this region, or to one of
80 // its subregion.
81 bool contains(const BasicBlock *BB) const { return Blocks.count(BB) != 0; }
82
83 void releaseMemory();
84
85 // Write to the debug output this region's hierarchy.
86 // |IndentSize| defines the number of tabs to print before any new line.
87 void dump(const unsigned IndentSize = 0) const;
88};
89
90// Holds a ConvergenceRegion hierarchy.
92 // The convergence region this structure holds.
93 ConvergenceRegion *TopLevelRegion;
94
95public:
96 ConvergenceRegionInfo() : TopLevelRegion(nullptr) {}
97
98 // Creates a new ConvergenceRegionInfo. Ownership of the TopLevelRegion is
99 // passed to this object.
101 : TopLevelRegion(TopLevelRegion) {}
102
104
106 : TopLevelRegion(LHS.TopLevelRegion) {
107 if (TopLevelRegion != LHS.TopLevelRegion) {
109 TopLevelRegion = LHS.TopLevelRegion;
110 }
111 LHS.TopLevelRegion = nullptr;
112 }
113
115 if (TopLevelRegion != LHS.TopLevelRegion) {
117 TopLevelRegion = LHS.TopLevelRegion;
118 }
119 LHS.TopLevelRegion = nullptr;
120 return *this;
121 }
122
124 if (TopLevelRegion == nullptr)
125 return;
126
127 TopLevelRegion->releaseMemory();
128 delete TopLevelRegion;
129 TopLevelRegion = nullptr;
130 }
131
132 const ConvergenceRegion *getTopLevelRegion() const { return TopLevelRegion; }
133};
134
135} // namespace SPIRV
136
137// Wrapper around the function above to use it with the legacy pass manager.
140
141public:
142 static char ID;
143
145
146 void getAnalysisUsage(AnalysisUsage &AU) const override {
147 AU.setPreservesAll();
150 };
151
152 bool runOnFunction(Function &F) override;
153
155 const SPIRV::ConvergenceRegionInfo &getRegionInfo() const { return CRI; }
156};
157
158// Wrapper around the function above to use it with the new pass manager.
160 : public AnalysisInfoMixin<SPIRVConvergenceRegionAnalysis> {
162 static AnalysisKey Key;
163
164public:
166
168};
169
170namespace SPIRV {
171ConvergenceRegionInfo getConvergenceRegions(Function &F, DominatorTree &DT,
172 LoopInfo &LI);
173} // namespace SPIRV
174
175} // namespace llvm
176#endif // LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H
#define F(x, y, z)
Definition: MD5.cpp:55
This file defines the SmallPtrSet class.
Value * LHS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:593
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
const SPIRV::ConvergenceRegionInfo & getRegionInfo() const
Result run(Function &F, FunctionAnalysisManager &AM)
ConvergenceRegionInfo(ConvergenceRegionInfo &&LHS)
const ConvergenceRegion * getTopLevelRegion() const
ConvergenceRegionInfo & operator=(ConvergenceRegionInfo &&LHS)
ConvergenceRegionInfo(ConvergenceRegion *TopLevelRegion)
SmallVector< ConvergenceRegion * > Children
bool contains(const BasicBlock *BB) const
ConvergenceRegion(const ConvergenceRegion &other)=delete
SmallPtrSet< BasicBlock *, 2 > Exits
std::optional< IntrinsicInst * > ConvergenceToken
void dump(const unsigned IndentSize=0) const
SmallPtrSet< BasicBlock *, 8 > Blocks
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:502
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
ConvergenceRegionInfo getConvergenceRegions(Function &F, DominatorTree &DT, LoopInfo &LI)
std::optional< IntrinsicInst * > getConvergenceToken(BasicBlock *BB)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1856
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:92
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28