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