1//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the DominanceFrontier class, which calculate and holds the 11// dominance frontier for a function. 12// 13// This should be considered deprecated, don't add any more uses of this data 14// structure. 15// 16//===----------------------------------------------------------------------===// 17 18#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H 19#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H 20 21#include "llvm/ADT/GraphTraits.h" 22#include "llvm/IR/PassManager.h" 23#include "llvm/Pass.h" 24#include "llvm/Support/GenericDomTree.h" 25#include <cassert> 26#include <map> 27#include <set> 28#include <utility> 29#include <vector> 30 31namespace llvm { 32 33class Function; 34class raw_ostream; 35 36//===----------------------------------------------------------------------===// 37/// DominanceFrontierBase - Common base class for computing forward and inverse 38/// dominance frontiers for a function. 39/// 40template <class BlockT, bool IsPostDom> 41class DominanceFrontierBase { 42public: 43 using DomSetType = std::set<BlockT *>; // Dom set for a bb 44 using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map 45 46protected: 47 using BlockTraits = GraphTraits<BlockT *>; 48 49 DomSetMapType Frontiers; 50 // Postdominators can have multiple roots. 51 SmallVector<BlockT *, IsPostDom ? 4 : 1> Roots; 52 static constexpr bool IsPostDominators = IsPostDom; 53 54public: 55 DominanceFrontierBase() = default; 56 57 /// getRoots - Return the root blocks of the current CFG. This may include 58 /// multiple blocks if we are computing post dominators. For forward 59 /// dominators, this will always be a single block (the entry node). 60 const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; } 61 62 BlockT *getRoot() const { 63 assert(Roots.size() == 1 && "Should always have entry node!"); 64 return Roots[0]; 65 } 66 67 /// isPostDominator - Returns true if analysis based of postdoms 68 bool isPostDominator() const { 69 return IsPostDominators; 70 } 71 72 void releaseMemory() { 73 Frontiers.clear(); 74 } 75 76 // Accessor interface: 77 using iterator = typename DomSetMapType::iterator; 78 using const_iterator = typename DomSetMapType::const_iterator; 79 80 iterator begin() { return Frontiers.begin(); } 81 const_iterator begin() const { return Frontiers.begin(); } 82 iterator end() { return Frontiers.end(); } 83 const_iterator end() const { return Frontiers.end(); } 84 iterator find(BlockT *B) { return Frontiers.find(B); } 85 const_iterator find(BlockT *B) const { return Frontiers.find(B); } 86 87 iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) { 88 assert(find(BB) == end() && "Block already in DominanceFrontier!"); 89 return Frontiers.insert(std::make_pair(BB, frontier)).first; 90 } 91 92 /// removeBlock - Remove basic block BB's frontier. 93 void removeBlock(BlockT *BB); 94 95 void addToFrontier(iterator I, BlockT *Node); 96 97 void removeFromFrontier(iterator I, BlockT *Node); 98 99 /// compareDomSet - Return false if two domsets match. Otherwise 100 /// return true; 101 bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const; 102 103 /// compare - Return true if the other dominance frontier base matches 104 /// this dominance frontier base. Otherwise return false. 105 bool compare(DominanceFrontierBase &Other) const; 106 107 /// print - Convert to human readable form 108 /// 109 void print(raw_ostream &OS) const; 110 111 /// dump - Dump the dominance frontier to dbgs(). 112#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 113 void dump() const; 114#endif 115}; 116 117//===------------------------------------- 118/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is 119/// used to compute a forward dominator frontiers. 120/// 121template <class BlockT> 122class ForwardDominanceFrontierBase 123 : public DominanceFrontierBase<BlockT, false> { 124private: 125 using BlockTraits = GraphTraits<BlockT *>; 126 127public: 128 using DomTreeT = DomTreeBase<BlockT>; 129 using DomTreeNodeT = DomTreeNodeBase<BlockT>; 130 using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType; 131 132 void analyze(DomTreeT &DT) { 133 assert(DT.getRoots().size() == 1 && 134 "Only one entry block for forward domfronts!"); 135 this->Roots = {DT.getRoot()}; 136 calculate(DT, DT[this->Roots[0]]); 137 } 138 139 const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node); 140}; 141 142class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> { 143public: 144 using DomTreeT = DomTreeBase<BasicBlock>; 145 using DomTreeNodeT = DomTreeNodeBase<BasicBlock>; 146 using DomSetType = DominanceFrontierBase<BasicBlock, false>::DomSetType; 147 using iterator = DominanceFrontierBase<BasicBlock, false>::iterator; 148 using const_iterator = 149 DominanceFrontierBase<BasicBlock, false>::const_iterator; 150 151 /// Handle invalidation explicitly. 152 bool invalidate(Function &F, const PreservedAnalyses &PA, 153 FunctionAnalysisManager::Invalidator &); 154}; 155 156class DominanceFrontierWrapperPass : public FunctionPass { 157 DominanceFrontier DF; 158 159public: 160 static char ID; // Pass ID, replacement for typeid 161 162 DominanceFrontierWrapperPass(); 163 164 DominanceFrontier &getDominanceFrontier() { return DF; } 165 const DominanceFrontier &getDominanceFrontier() const { return DF; } 166 167 void releaseMemory() override; 168 169 bool runOnFunction(Function &) override; 170 171 void getAnalysisUsage(AnalysisUsage &AU) const override; 172 173 void print(raw_ostream &OS, const Module * = nullptr) const override; 174 175 void dump() const; 176}; 177 178extern template class DominanceFrontierBase<BasicBlock, false>; 179extern template class DominanceFrontierBase<BasicBlock, true>; 180extern template class ForwardDominanceFrontierBase<BasicBlock>; 181 182/// \brief Analysis pass which computes a \c DominanceFrontier. 183class DominanceFrontierAnalysis 184 : public AnalysisInfoMixin<DominanceFrontierAnalysis> { 185 friend AnalysisInfoMixin<DominanceFrontierAnalysis>; 186 187 static AnalysisKey Key; 188 189public: 190 /// \brief Provide the result type for this analysis pass. 191 using Result = DominanceFrontier; 192 193 /// \brief Run the analysis pass over a function and produce a dominator tree. 194 DominanceFrontier run(Function &F, FunctionAnalysisManager &AM); 195}; 196 197/// \brief Printer pass for the \c DominanceFrontier. 198class DominanceFrontierPrinterPass 199 : public PassInfoMixin<DominanceFrontierPrinterPass> { 200 raw_ostream &OS; 201 202public: 203 explicit DominanceFrontierPrinterPass(raw_ostream &OS); 204 205 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 206}; 207 208} // end namespace llvm 209 210#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H 211