xref: /freebsd-src/contrib/llvm-project/llvm/lib/Target/SPIRV/Analysis/SPIRVConvergenceRegionAnalysis.h (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
1*0fca6ea1SDimitry Andric //===- SPIRVConvergenceRegionAnalysis.h ------------------------*- C++ -*--===//
2*0fca6ea1SDimitry Andric //
3*0fca6ea1SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*0fca6ea1SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5*0fca6ea1SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*0fca6ea1SDimitry Andric //
7*0fca6ea1SDimitry Andric //===----------------------------------------------------------------------===//
8*0fca6ea1SDimitry Andric //
9*0fca6ea1SDimitry Andric // The analysis determines the convergence region for each basic block of
10*0fca6ea1SDimitry Andric // the module, and provides a tree-like structure describing the region
11*0fca6ea1SDimitry Andric // hierarchy.
12*0fca6ea1SDimitry Andric //
13*0fca6ea1SDimitry Andric //===----------------------------------------------------------------------===//
14*0fca6ea1SDimitry Andric 
15*0fca6ea1SDimitry Andric #ifndef LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H
16*0fca6ea1SDimitry Andric #define LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H
17*0fca6ea1SDimitry Andric 
18*0fca6ea1SDimitry Andric #include "llvm/ADT/SmallPtrSet.h"
19*0fca6ea1SDimitry Andric #include "llvm/Analysis/CFG.h"
20*0fca6ea1SDimitry Andric #include "llvm/Analysis/LoopInfo.h"
21*0fca6ea1SDimitry Andric #include "llvm/IR/Dominators.h"
22*0fca6ea1SDimitry Andric #include "llvm/IR/IntrinsicInst.h"
23*0fca6ea1SDimitry Andric #include <iostream>
24*0fca6ea1SDimitry Andric #include <optional>
25*0fca6ea1SDimitry Andric #include <unordered_set>
26*0fca6ea1SDimitry Andric 
27*0fca6ea1SDimitry Andric namespace llvm {
28*0fca6ea1SDimitry Andric class SPIRVSubtarget;
29*0fca6ea1SDimitry Andric class MachineFunction;
30*0fca6ea1SDimitry Andric class MachineModuleInfo;
31*0fca6ea1SDimitry Andric 
32*0fca6ea1SDimitry Andric namespace SPIRV {
33*0fca6ea1SDimitry Andric 
34*0fca6ea1SDimitry Andric // Returns the first convergence intrinsic found in |BB|, |nullopt| otherwise.
35*0fca6ea1SDimitry Andric std::optional<IntrinsicInst *> getConvergenceToken(BasicBlock *BB);
36*0fca6ea1SDimitry Andric std::optional<const IntrinsicInst *> getConvergenceToken(const BasicBlock *BB);
37*0fca6ea1SDimitry Andric 
38*0fca6ea1SDimitry Andric // Describes a hierarchy of convergence regions.
39*0fca6ea1SDimitry Andric // A convergence region defines a CFG for which the execution flow can diverge
40*0fca6ea1SDimitry Andric // starting from the entry block, but should reconverge back before the end of
41*0fca6ea1SDimitry Andric // the exit blocks.
42*0fca6ea1SDimitry Andric class ConvergenceRegion {
43*0fca6ea1SDimitry Andric   DominatorTree &DT;
44*0fca6ea1SDimitry Andric   LoopInfo &LI;
45*0fca6ea1SDimitry Andric 
46*0fca6ea1SDimitry Andric public:
47*0fca6ea1SDimitry Andric   // The parent region of this region, if any.
48*0fca6ea1SDimitry Andric   ConvergenceRegion *Parent = nullptr;
49*0fca6ea1SDimitry Andric   // The sub-regions contained in this region, if any.
50*0fca6ea1SDimitry Andric   SmallVector<ConvergenceRegion *> Children = {};
51*0fca6ea1SDimitry Andric   // The convergence instruction linked to this region, if any.
52*0fca6ea1SDimitry Andric   std::optional<IntrinsicInst *> ConvergenceToken = std::nullopt;
53*0fca6ea1SDimitry Andric   // The only block with a predecessor outside of this region.
54*0fca6ea1SDimitry Andric   BasicBlock *Entry = nullptr;
55*0fca6ea1SDimitry Andric   // All the blocks with an edge leaving this convergence region.
56*0fca6ea1SDimitry Andric   SmallPtrSet<BasicBlock *, 2> Exits = {};
57*0fca6ea1SDimitry Andric   // All the blocks that belongs to this region, including its subregions'.
58*0fca6ea1SDimitry Andric   SmallPtrSet<BasicBlock *, 8> Blocks = {};
59*0fca6ea1SDimitry Andric 
60*0fca6ea1SDimitry Andric   // Creates a single convergence region encapsulating the whole function |F|.
61*0fca6ea1SDimitry Andric   ConvergenceRegion(DominatorTree &DT, LoopInfo &LI, Function &F);
62*0fca6ea1SDimitry Andric 
63*0fca6ea1SDimitry Andric   // Creates a single convergence region defined by entry and exits nodes, a
64*0fca6ea1SDimitry Andric   // list of blocks, and possibly a convergence token.
65*0fca6ea1SDimitry Andric   ConvergenceRegion(DominatorTree &DT, LoopInfo &LI,
66*0fca6ea1SDimitry Andric                     std::optional<IntrinsicInst *> ConvergenceToken,
67*0fca6ea1SDimitry Andric                     BasicBlock *Entry, SmallPtrSet<BasicBlock *, 8> &&Blocks,
68*0fca6ea1SDimitry Andric                     SmallPtrSet<BasicBlock *, 2> &&Exits);
69*0fca6ea1SDimitry Andric 
70*0fca6ea1SDimitry Andric   ConvergenceRegion(ConvergenceRegion &&CR)
71*0fca6ea1SDimitry Andric       : DT(CR.DT), LI(CR.LI), Parent(std::move(CR.Parent)),
72*0fca6ea1SDimitry Andric         Children(std::move(CR.Children)),
73*0fca6ea1SDimitry Andric         ConvergenceToken(std::move(CR.ConvergenceToken)),
74*0fca6ea1SDimitry Andric         Entry(std::move(CR.Entry)), Exits(std::move(CR.Exits)),
75*0fca6ea1SDimitry Andric         Blocks(std::move(CR.Blocks)) {}
76*0fca6ea1SDimitry Andric 
77*0fca6ea1SDimitry Andric   ConvergenceRegion(const ConvergenceRegion &other) = delete;
78*0fca6ea1SDimitry Andric 
79*0fca6ea1SDimitry Andric   // Returns true if the given basic block belongs to this region, or to one of
80*0fca6ea1SDimitry Andric   // its subregion.
81*0fca6ea1SDimitry Andric   bool contains(const BasicBlock *BB) const { return Blocks.count(BB) != 0; }
82*0fca6ea1SDimitry Andric 
83*0fca6ea1SDimitry Andric   void releaseMemory();
84*0fca6ea1SDimitry Andric 
85*0fca6ea1SDimitry Andric   // Write to the debug output this region's hierarchy.
86*0fca6ea1SDimitry Andric   // |IndentSize| defines the number of tabs to print before any new line.
87*0fca6ea1SDimitry Andric   void dump(const unsigned IndentSize = 0) const;
88*0fca6ea1SDimitry Andric };
89*0fca6ea1SDimitry Andric 
90*0fca6ea1SDimitry Andric // Holds a ConvergenceRegion hierarchy.
91*0fca6ea1SDimitry Andric class ConvergenceRegionInfo {
92*0fca6ea1SDimitry Andric   // The convergence region this structure holds.
93*0fca6ea1SDimitry Andric   ConvergenceRegion *TopLevelRegion;
94*0fca6ea1SDimitry Andric 
95*0fca6ea1SDimitry Andric public:
96*0fca6ea1SDimitry Andric   ConvergenceRegionInfo() : TopLevelRegion(nullptr) {}
97*0fca6ea1SDimitry Andric 
98*0fca6ea1SDimitry Andric   // Creates a new ConvergenceRegionInfo. Ownership of the TopLevelRegion is
99*0fca6ea1SDimitry Andric   // passed to this object.
100*0fca6ea1SDimitry Andric   ConvergenceRegionInfo(ConvergenceRegion *TopLevelRegion)
101*0fca6ea1SDimitry Andric       : TopLevelRegion(TopLevelRegion) {}
102*0fca6ea1SDimitry Andric 
103*0fca6ea1SDimitry Andric   ~ConvergenceRegionInfo() { releaseMemory(); }
104*0fca6ea1SDimitry Andric 
105*0fca6ea1SDimitry Andric   ConvergenceRegionInfo(ConvergenceRegionInfo &&LHS)
106*0fca6ea1SDimitry Andric       : TopLevelRegion(LHS.TopLevelRegion) {
107*0fca6ea1SDimitry Andric     if (TopLevelRegion != LHS.TopLevelRegion) {
108*0fca6ea1SDimitry Andric       releaseMemory();
109*0fca6ea1SDimitry Andric       TopLevelRegion = LHS.TopLevelRegion;
110*0fca6ea1SDimitry Andric     }
111*0fca6ea1SDimitry Andric     LHS.TopLevelRegion = nullptr;
112*0fca6ea1SDimitry Andric   }
113*0fca6ea1SDimitry Andric 
114*0fca6ea1SDimitry Andric   ConvergenceRegionInfo &operator=(ConvergenceRegionInfo &&LHS) {
115*0fca6ea1SDimitry Andric     if (TopLevelRegion != LHS.TopLevelRegion) {
116*0fca6ea1SDimitry Andric       releaseMemory();
117*0fca6ea1SDimitry Andric       TopLevelRegion = LHS.TopLevelRegion;
118*0fca6ea1SDimitry Andric     }
119*0fca6ea1SDimitry Andric     LHS.TopLevelRegion = nullptr;
120*0fca6ea1SDimitry Andric     return *this;
121*0fca6ea1SDimitry Andric   }
122*0fca6ea1SDimitry Andric 
123*0fca6ea1SDimitry Andric   void releaseMemory() {
124*0fca6ea1SDimitry Andric     if (TopLevelRegion == nullptr)
125*0fca6ea1SDimitry Andric       return;
126*0fca6ea1SDimitry Andric 
127*0fca6ea1SDimitry Andric     TopLevelRegion->releaseMemory();
128*0fca6ea1SDimitry Andric     delete TopLevelRegion;
129*0fca6ea1SDimitry Andric     TopLevelRegion = nullptr;
130*0fca6ea1SDimitry Andric   }
131*0fca6ea1SDimitry Andric 
132*0fca6ea1SDimitry Andric   const ConvergenceRegion *getTopLevelRegion() const { return TopLevelRegion; }
133*0fca6ea1SDimitry Andric };
134*0fca6ea1SDimitry Andric 
135*0fca6ea1SDimitry Andric } // namespace SPIRV
136*0fca6ea1SDimitry Andric 
137*0fca6ea1SDimitry Andric // Wrapper around the function above to use it with the legacy pass manager.
138*0fca6ea1SDimitry Andric class SPIRVConvergenceRegionAnalysisWrapperPass : public FunctionPass {
139*0fca6ea1SDimitry Andric   SPIRV::ConvergenceRegionInfo CRI;
140*0fca6ea1SDimitry Andric 
141*0fca6ea1SDimitry Andric public:
142*0fca6ea1SDimitry Andric   static char ID;
143*0fca6ea1SDimitry Andric 
144*0fca6ea1SDimitry Andric   SPIRVConvergenceRegionAnalysisWrapperPass();
145*0fca6ea1SDimitry Andric 
146*0fca6ea1SDimitry Andric   void getAnalysisUsage(AnalysisUsage &AU) const override {
147*0fca6ea1SDimitry Andric     AU.setPreservesAll();
148*0fca6ea1SDimitry Andric     AU.addRequired<LoopInfoWrapperPass>();
149*0fca6ea1SDimitry Andric     AU.addRequired<DominatorTreeWrapperPass>();
150*0fca6ea1SDimitry Andric   };
151*0fca6ea1SDimitry Andric 
152*0fca6ea1SDimitry Andric   bool runOnFunction(Function &F) override;
153*0fca6ea1SDimitry Andric 
154*0fca6ea1SDimitry Andric   SPIRV::ConvergenceRegionInfo &getRegionInfo() { return CRI; }
155*0fca6ea1SDimitry Andric   const SPIRV::ConvergenceRegionInfo &getRegionInfo() const { return CRI; }
156*0fca6ea1SDimitry Andric };
157*0fca6ea1SDimitry Andric 
158*0fca6ea1SDimitry Andric // Wrapper around the function above to use it with the new pass manager.
159*0fca6ea1SDimitry Andric class SPIRVConvergenceRegionAnalysis
160*0fca6ea1SDimitry Andric     : public AnalysisInfoMixin<SPIRVConvergenceRegionAnalysis> {
161*0fca6ea1SDimitry Andric   friend AnalysisInfoMixin<SPIRVConvergenceRegionAnalysis>;
162*0fca6ea1SDimitry Andric   static AnalysisKey Key;
163*0fca6ea1SDimitry Andric 
164*0fca6ea1SDimitry Andric public:
165*0fca6ea1SDimitry Andric   using Result = SPIRV::ConvergenceRegionInfo;
166*0fca6ea1SDimitry Andric 
167*0fca6ea1SDimitry Andric   Result run(Function &F, FunctionAnalysisManager &AM);
168*0fca6ea1SDimitry Andric };
169*0fca6ea1SDimitry Andric 
170*0fca6ea1SDimitry Andric namespace SPIRV {
171*0fca6ea1SDimitry Andric ConvergenceRegionInfo getConvergenceRegions(Function &F, DominatorTree &DT,
172*0fca6ea1SDimitry Andric                                             LoopInfo &LI);
173*0fca6ea1SDimitry Andric } // namespace SPIRV
174*0fca6ea1SDimitry Andric 
175*0fca6ea1SDimitry Andric } // namespace llvm
176*0fca6ea1SDimitry Andric #endif // LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H
177