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/Analysis/Dominators.h" 22 #include <map> 23 #include <set> 24 25 namespace llvm { 26 27 //===----------------------------------------------------------------------===// 28 /// DominanceFrontierBase - Common base class for computing forward and inverse 29 /// dominance frontiers for a function. 30 /// 31 class DominanceFrontierBase : public FunctionPass { 32 public: 33 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 34 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 35 protected: 36 DomSetMapType Frontiers; 37 std::vector<BasicBlock*> Roots; 38 const bool IsPostDominators; 39 40 public: 41 DominanceFrontierBase(char &ID, bool isPostDom) 42 : FunctionPass(ID), IsPostDominators(isPostDom) {} 43 44 /// getRoots - Return the root blocks of the current CFG. This may include 45 /// multiple blocks if we are computing post dominators. For forward 46 /// dominators, this will always be a single block (the entry node). 47 /// 48 inline const std::vector<BasicBlock*> &getRoots() const { return Roots; } 49 50 /// isPostDominator - Returns true if analysis based of postdoms 51 /// 52 bool isPostDominator() const { return IsPostDominators; } 53 54 virtual void releaseMemory() { Frontiers.clear(); } 55 56 // Accessor interface: 57 typedef DomSetMapType::iterator iterator; 58 typedef DomSetMapType::const_iterator const_iterator; 59 iterator begin() { return Frontiers.begin(); } 60 const_iterator begin() const { return Frontiers.begin(); } 61 iterator end() { return Frontiers.end(); } 62 const_iterator end() const { return Frontiers.end(); } 63 iterator find(BasicBlock *B) { return Frontiers.find(B); } 64 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } 65 66 iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 67 assert(find(BB) == end() && "Block already in DominanceFrontier!"); 68 return Frontiers.insert(std::make_pair(BB, frontier)).first; 69 } 70 71 /// removeBlock - Remove basic block BB's frontier. 72 void removeBlock(BasicBlock *BB) { 73 assert(find(BB) != end() && "Block is not in DominanceFrontier!"); 74 for (iterator I = begin(), E = end(); I != E; ++I) 75 I->second.erase(BB); 76 Frontiers.erase(BB); 77 } 78 79 void addToFrontier(iterator I, BasicBlock *Node) { 80 assert(I != end() && "BB is not in DominanceFrontier!"); 81 I->second.insert(Node); 82 } 83 84 void removeFromFrontier(iterator I, BasicBlock *Node) { 85 assert(I != end() && "BB is not in DominanceFrontier!"); 86 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 87 I->second.erase(Node); 88 } 89 90 /// compareDomSet - Return false if two domsets match. Otherwise 91 /// return true; 92 bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { 93 std::set<BasicBlock *> tmpSet; 94 for (DomSetType::const_iterator I = DS2.begin(), 95 E = DS2.end(); I != E; ++I) 96 tmpSet.insert(*I); 97 98 for (DomSetType::const_iterator I = DS1.begin(), 99 E = DS1.end(); I != E; ) { 100 BasicBlock *Node = *I++; 101 102 if (tmpSet.erase(Node) == 0) 103 // Node is in DS1 but not in DS2. 104 return true; 105 } 106 107 if (!tmpSet.empty()) 108 // There are nodes that are in DS2 but not in DS1. 109 return true; 110 111 // DS1 and DS2 matches. 112 return false; 113 } 114 115 /// compare - Return true if the other dominance frontier base matches 116 /// this dominance frontier base. Otherwise return false. 117 bool compare(DominanceFrontierBase &Other) const { 118 DomSetMapType tmpFrontiers; 119 for (DomSetMapType::const_iterator I = Other.begin(), 120 E = Other.end(); I != E; ++I) 121 tmpFrontiers.insert(std::make_pair(I->first, I->second)); 122 123 for (DomSetMapType::iterator I = tmpFrontiers.begin(), 124 E = tmpFrontiers.end(); I != E; ) { 125 BasicBlock *Node = I->first; 126 const_iterator DFI = find(Node); 127 if (DFI == end()) 128 return true; 129 130 if (compareDomSet(I->second, DFI->second)) 131 return true; 132 133 ++I; 134 tmpFrontiers.erase(Node); 135 } 136 137 if (!tmpFrontiers.empty()) 138 return true; 139 140 return false; 141 } 142 143 /// print - Convert to human readable form 144 /// 145 virtual void print(raw_ostream &OS, const Module* = 0) const; 146 147 /// dump - Dump the dominance frontier to dbgs(). 148 void dump() const; 149 }; 150 151 152 //===------------------------------------- 153 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is 154 /// used to compute a forward dominator frontiers. 155 /// 156 class DominanceFrontier : public DominanceFrontierBase { 157 public: 158 static char ID; // Pass ID, replacement for typeid 159 DominanceFrontier() : 160 DominanceFrontierBase(ID, false) { 161 initializeDominanceFrontierPass(*PassRegistry::getPassRegistry()); 162 } 163 164 BasicBlock *getRoot() const { 165 assert(Roots.size() == 1 && "Should always have entry node!"); 166 return Roots[0]; 167 } 168 169 virtual bool runOnFunction(Function &) { 170 Frontiers.clear(); 171 DominatorTree &DT = getAnalysis<DominatorTree>(); 172 Roots = DT.getRoots(); 173 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); 174 calculate(DT, DT[Roots[0]]); 175 return false; 176 } 177 178 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 179 AU.setPreservesAll(); 180 AU.addRequired<DominatorTree>(); 181 } 182 183 const DomSetType &calculate(const DominatorTree &DT, 184 const DomTreeNode *Node); 185 }; 186 187 } // End llvm namespace 188 189 #endif 190
