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