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