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