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