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