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