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 is the generic implementation of the DominanceFrontier class, which 11// calculate and holds the dominance frontier for a function for. 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_DOMINANCEFRONTIERIMPL_H 19#define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H 20 21#include "llvm/ADT/SmallPtrSet.h" 22#include "llvm/Support/Debug.h" 23 24namespace llvm { 25 26template <class BlockT> 27class DFCalculateWorkObject { 28public: 29 typedef DomTreeNodeBase<BlockT> DomTreeNodeT; 30 31 DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N, 32 const DomTreeNodeT *PN) 33 : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 34 BlockT *currentBB; 35 BlockT *parentBB; 36 const DomTreeNodeT *Node; 37 const DomTreeNodeT *parentNode; 38}; 39 40template <class BlockT> 41void DominanceFrontierBase<BlockT>::removeBlock(BlockT *BB) { 42 assert(find(BB) != end() && "Block is not in DominanceFrontier!"); 43 for (iterator I = begin(), E = end(); I != E; ++I) 44 I->second.erase(BB); 45 Frontiers.erase(BB); 46} 47 48template <class BlockT> 49void DominanceFrontierBase<BlockT>::addToFrontier(iterator I, 50 BlockT *Node) { 51 assert(I != end() && "BB is not in DominanceFrontier!"); 52 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 53 I->second.erase(Node); 54} 55 56template <class BlockT> 57void DominanceFrontierBase<BlockT>::removeFromFrontier(iterator I, 58 BlockT *Node) { 59 assert(I != end() && "BB is not in DominanceFrontier!"); 60 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 61 I->second.erase(Node); 62} 63 64template <class BlockT> 65bool DominanceFrontierBase<BlockT>::compareDomSet(DomSetType &DS1, 66 const DomSetType &DS2) const { 67 std::set<BlockT *> tmpSet; 68 for (BlockT *BB : DS2) 69 tmpSet.insert(BB); 70 71 for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end(); 72 I != E;) { 73 BlockT *Node = *I++; 74 75 if (tmpSet.erase(Node) == 0) 76 // Node is in DS1 but tnot in DS2. 77 return true; 78 } 79 80 if (!tmpSet.empty()) { 81 // There are nodes that are in DS2 but not in DS1. 82 return true; 83 } 84 85 // DS1 and DS2 matches. 86 return false; 87} 88 89template <class BlockT> 90bool DominanceFrontierBase<BlockT>::compare( 91 DominanceFrontierBase<BlockT> &Other) const { 92 DomSetMapType tmpFrontiers; 93 for (typename DomSetMapType::const_iterator I = Other.begin(), 94 E = Other.end(); 95 I != E; ++I) 96 tmpFrontiers.insert(std::make_pair(I->first, I->second)); 97 98 for (typename DomSetMapType::iterator I = tmpFrontiers.begin(), 99 E = tmpFrontiers.end(); 100 I != E;) { 101 BlockT *Node = I->first; 102 const_iterator DFI = find(Node); 103 if (DFI == end()) 104 return true; 105 106 if (compareDomSet(I->second, DFI->second)) 107 return true; 108 109 ++I; 110 tmpFrontiers.erase(Node); 111 } 112 113 if (!tmpFrontiers.empty()) 114 return true; 115 116 return false; 117} 118 119template <class BlockT> 120void DominanceFrontierBase<BlockT>::print(raw_ostream &OS) const { 121 for (const_iterator I = begin(), E = end(); I != E; ++I) { 122 OS << " DomFrontier for BB "; 123 if (I->first) 124 I->first->printAsOperand(OS, false); 125 else 126 OS << " <<exit node>>"; 127 OS << " is:\t"; 128 129 const std::set<BlockT *> &BBs = I->second; 130 131 for (const BlockT *BB : BBs) { 132 OS << ' '; 133 if (BB) 134 BB->printAsOperand(OS, false); 135 else 136 OS << "<<exit node>>"; 137 } 138 OS << '\n'; 139 } 140} 141 142#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 143template <class BlockT> 144void DominanceFrontierBase<BlockT>::dump() const { 145 print(dbgs()); 146} 147#endif 148 149template <class BlockT> 150const typename ForwardDominanceFrontierBase<BlockT>::DomSetType & 151ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT, 152 const DomTreeNodeT *Node) { 153 BlockT *BB = Node->getBlock(); 154 DomSetType *Result = nullptr; 155 156 std::vector<DFCalculateWorkObject<BlockT>> workList; 157 SmallPtrSet<BlockT *, 32> visited; 158 159 workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr)); 160 do { 161 DFCalculateWorkObject<BlockT> *currentW = &workList.back(); 162 assert(currentW && "Missing work object."); 163 164 BlockT *currentBB = currentW->currentBB; 165 BlockT *parentBB = currentW->parentBB; 166 const DomTreeNodeT *currentNode = currentW->Node; 167 const DomTreeNodeT *parentNode = currentW->parentNode; 168 assert(currentBB && "Invalid work object. Missing current Basic Block"); 169 assert(currentNode && "Invalid work object. Missing current Node"); 170 DomSetType &S = this->Frontiers[currentBB]; 171 172 // Visit each block only once. 173 if (visited.insert(currentBB).second) { 174 // Loop over CFG successors to calculate DFlocal[currentNode] 175 for (auto SI = BlockTraits::child_begin(currentBB), 176 SE = BlockTraits::child_end(currentBB); 177 SI != SE; ++SI) { 178 // Does Node immediately dominate this successor? 179 if (DT[*SI]->getIDom() != currentNode) 180 S.insert(*SI); 181 } 182 } 183 184 // At this point, S is DFlocal. Now we union in DFup's of our children... 185 // Loop through and visit the nodes that Node immediately dominates (Node's 186 // children in the IDomTree) 187 bool visitChild = false; 188 for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(), 189 NE = currentNode->end(); 190 NI != NE; ++NI) { 191 DomTreeNodeT *IDominee = *NI; 192 BlockT *childBB = IDominee->getBlock(); 193 if (visited.count(childBB) == 0) { 194 workList.push_back(DFCalculateWorkObject<BlockT>( 195 childBB, currentBB, IDominee, currentNode)); 196 visitChild = true; 197 } 198 } 199 200 // If all children are visited or there is any child then pop this block 201 // from the workList. 202 if (!visitChild) { 203 if (!parentBB) { 204 Result = &S; 205 break; 206 } 207 208 typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 209 DomSetType &parentSet = this->Frontiers[parentBB]; 210 for (; CDFI != CDFE; ++CDFI) { 211 if (!DT.properlyDominates(parentNode, DT[*CDFI])) 212 parentSet.insert(*CDFI); 213 } 214 workList.pop_back(); 215 } 216 217 } while (!workList.empty()); 218 219 return *Result; 220} 221 222} // End llvm namespace 223 224#endif 225