GenericDomTree.h revision 296417
1274955Ssvnmir//===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===// 2274955Ssvnmir// 3274955Ssvnmir// The LLVM Compiler Infrastructure 4274955Ssvnmir// 5274955Ssvnmir// This file is distributed under the University of Illinois Open Source 6274955Ssvnmir// License. See LICENSE.TXT for details. 7274955Ssvnmir// 8274955Ssvnmir//===----------------------------------------------------------------------===// 9274955Ssvnmir/// \file 10274955Ssvnmir/// 11274955Ssvnmir/// This file defines a set of templates that efficiently compute a dominator 12274955Ssvnmir/// tree over a generic graph. This is used typically in LLVM for fast 13274955Ssvnmir/// dominance queries on the CFG, but is fully generic w.r.t. the underlying 14274955Ssvnmir/// graph types. 15274955Ssvnmir/// 16274955Ssvnmir//===----------------------------------------------------------------------===// 17274955Ssvnmir 18280031Sdim#ifndef LLVM_SUPPORT_GENERICDOMTREE_H 19280031Sdim#define LLVM_SUPPORT_GENERICDOMTREE_H 20274955Ssvnmir 21274955Ssvnmir#include "llvm/ADT/DenseMap.h" 22274955Ssvnmir#include "llvm/ADT/DepthFirstIterator.h" 23274955Ssvnmir#include "llvm/ADT/GraphTraits.h" 24288943Sdim#include "llvm/ADT/STLExtras.h" 25274955Ssvnmir#include "llvm/ADT/SmallPtrSet.h" 26274955Ssvnmir#include "llvm/ADT/SmallVector.h" 27274955Ssvnmir#include "llvm/Support/Compiler.h" 28274955Ssvnmir#include "llvm/Support/raw_ostream.h" 29274955Ssvnmir#include <algorithm> 30274955Ssvnmir 31274955Ssvnmirnamespace llvm { 32274955Ssvnmir 33280031Sdim/// \brief Base class that other, more interesting dominator analyses 34274955Ssvnmir/// inherit from. 35280031Sdimtemplate <class NodeT> class DominatorBase { 36274955Ssvnmirprotected: 37280031Sdim std::vector<NodeT *> Roots; 38280031Sdim bool IsPostDominators; 39280031Sdim explicit DominatorBase(bool isPostDom) 40280031Sdim : Roots(), IsPostDominators(isPostDom) {} 41280031Sdim DominatorBase(DominatorBase &&Arg) 42280031Sdim : Roots(std::move(Arg.Roots)), 43280031Sdim IsPostDominators(std::move(Arg.IsPostDominators)) { 44280031Sdim Arg.Roots.clear(); 45280031Sdim } 46280031Sdim DominatorBase &operator=(DominatorBase &&RHS) { 47280031Sdim Roots = std::move(RHS.Roots); 48280031Sdim IsPostDominators = std::move(RHS.IsPostDominators); 49280031Sdim RHS.Roots.clear(); 50280031Sdim return *this; 51280031Sdim } 52280031Sdim 53274955Ssvnmirpublic: 54274955Ssvnmir /// getRoots - Return the root blocks of the current CFG. This may include 55274955Ssvnmir /// multiple blocks if we are computing post dominators. For forward 56274955Ssvnmir /// dominators, this will always be a single block (the entry node). 57274955Ssvnmir /// 58280031Sdim const std::vector<NodeT *> &getRoots() const { return Roots; } 59274955Ssvnmir 60274955Ssvnmir /// isPostDominator - Returns true if analysis based of postdoms 61274955Ssvnmir /// 62274955Ssvnmir bool isPostDominator() const { return IsPostDominators; } 63274955Ssvnmir}; 64274955Ssvnmir 65280031Sdimtemplate <class NodeT> class DominatorTreeBase; 66274955Ssvnmirstruct PostDominatorTree; 67274955Ssvnmir 68280031Sdim/// \brief Base class for the actual dominator tree node. 69280031Sdimtemplate <class NodeT> class DomTreeNodeBase { 70274955Ssvnmir NodeT *TheBB; 71274955Ssvnmir DomTreeNodeBase<NodeT> *IDom; 72274955Ssvnmir std::vector<DomTreeNodeBase<NodeT> *> Children; 73274955Ssvnmir mutable int DFSNumIn, DFSNumOut; 74274955Ssvnmir 75280031Sdim template <class N> friend class DominatorTreeBase; 76274955Ssvnmir friend struct PostDominatorTree; 77280031Sdim 78274955Ssvnmirpublic: 79274955Ssvnmir typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator; 80274955Ssvnmir typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator 81280031Sdim const_iterator; 82274955Ssvnmir 83280031Sdim iterator begin() { return Children.begin(); } 84280031Sdim iterator end() { return Children.end(); } 85274955Ssvnmir const_iterator begin() const { return Children.begin(); } 86280031Sdim const_iterator end() const { return Children.end(); } 87274955Ssvnmir 88274955Ssvnmir NodeT *getBlock() const { return TheBB; } 89274955Ssvnmir DomTreeNodeBase<NodeT> *getIDom() const { return IDom; } 90280031Sdim const std::vector<DomTreeNodeBase<NodeT> *> &getChildren() const { 91274955Ssvnmir return Children; 92274955Ssvnmir } 93274955Ssvnmir 94274955Ssvnmir DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom) 95280031Sdim : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) {} 96274955Ssvnmir 97288943Sdim std::unique_ptr<DomTreeNodeBase<NodeT>> 98288943Sdim addChild(std::unique_ptr<DomTreeNodeBase<NodeT>> C) { 99288943Sdim Children.push_back(C.get()); 100274955Ssvnmir return C; 101274955Ssvnmir } 102274955Ssvnmir 103280031Sdim size_t getNumChildren() const { return Children.size(); } 104274955Ssvnmir 105280031Sdim void clearAllChildren() { Children.clear(); } 106274955Ssvnmir 107274955Ssvnmir bool compare(const DomTreeNodeBase<NodeT> *Other) const { 108274955Ssvnmir if (getNumChildren() != Other->getNumChildren()) 109274955Ssvnmir return true; 110274955Ssvnmir 111274955Ssvnmir SmallPtrSet<const NodeT *, 4> OtherChildren; 112274955Ssvnmir for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) { 113274955Ssvnmir const NodeT *Nd = (*I)->getBlock(); 114274955Ssvnmir OtherChildren.insert(Nd); 115274955Ssvnmir } 116274955Ssvnmir 117274955Ssvnmir for (const_iterator I = begin(), E = end(); I != E; ++I) { 118274955Ssvnmir const NodeT *N = (*I)->getBlock(); 119274955Ssvnmir if (OtherChildren.count(N) == 0) 120274955Ssvnmir return true; 121274955Ssvnmir } 122274955Ssvnmir return false; 123274955Ssvnmir } 124274955Ssvnmir 125274955Ssvnmir void setIDom(DomTreeNodeBase<NodeT> *NewIDom) { 126274955Ssvnmir assert(IDom && "No immediate dominator?"); 127274955Ssvnmir if (IDom != NewIDom) { 128280031Sdim typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I = 129280031Sdim std::find(IDom->Children.begin(), IDom->Children.end(), this); 130274955Ssvnmir assert(I != IDom->Children.end() && 131274955Ssvnmir "Not in immediate dominator children set!"); 132274955Ssvnmir // I am no longer your child... 133274955Ssvnmir IDom->Children.erase(I); 134274955Ssvnmir 135274955Ssvnmir // Switch to new dominator 136274955Ssvnmir IDom = NewIDom; 137274955Ssvnmir IDom->Children.push_back(this); 138274955Ssvnmir } 139274955Ssvnmir } 140274955Ssvnmir 141274955Ssvnmir /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do 142274955Ssvnmir /// not call them. 143274955Ssvnmir unsigned getDFSNumIn() const { return DFSNumIn; } 144274955Ssvnmir unsigned getDFSNumOut() const { return DFSNumOut; } 145280031Sdim 146274955Ssvnmirprivate: 147274955Ssvnmir // Return true if this node is dominated by other. Use this only if DFS info 148274955Ssvnmir // is valid. 149274955Ssvnmir bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const { 150274955Ssvnmir return this->DFSNumIn >= other->DFSNumIn && 151280031Sdim this->DFSNumOut <= other->DFSNumOut; 152274955Ssvnmir } 153274955Ssvnmir}; 154274955Ssvnmir 155280031Sdimtemplate <class NodeT> 156280031Sdimraw_ostream &operator<<(raw_ostream &o, const DomTreeNodeBase<NodeT> *Node) { 157274955Ssvnmir if (Node->getBlock()) 158274955Ssvnmir Node->getBlock()->printAsOperand(o, false); 159274955Ssvnmir else 160274955Ssvnmir o << " <<exit node>>"; 161274955Ssvnmir 162274955Ssvnmir o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; 163274955Ssvnmir 164274955Ssvnmir return o << "\n"; 165274955Ssvnmir} 166274955Ssvnmir 167280031Sdimtemplate <class NodeT> 168280031Sdimvoid PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o, 169280031Sdim unsigned Lev) { 170280031Sdim o.indent(2 * Lev) << "[" << Lev << "] " << N; 171274955Ssvnmir for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), 172280031Sdim E = N->end(); 173280031Sdim I != E; ++I) 174280031Sdim PrintDomTree<NodeT>(*I, o, Lev + 1); 175274955Ssvnmir} 176274955Ssvnmir 177280031Sdim// The calculate routine is provided in a separate header but referenced here. 178280031Sdimtemplate <class FuncT, class N> 179280031Sdimvoid Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT, 180280031Sdim FuncT &F); 181280031Sdim 182280031Sdim/// \brief Core dominator tree base class. 183274955Ssvnmir/// 184280031Sdim/// This class is a generic template over graph nodes. It is instantiated for 185280031Sdim/// various graphs in the LLVM IR or in the code generator. 186280031Sdimtemplate <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> { 187288943Sdim DominatorTreeBase(const DominatorTreeBase &) = delete; 188288943Sdim DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; 189274955Ssvnmir 190274955Ssvnmir bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 191274955Ssvnmir const DomTreeNodeBase<NodeT> *B) const { 192274955Ssvnmir assert(A != B); 193274955Ssvnmir assert(isReachableFromEntry(B)); 194274955Ssvnmir assert(isReachableFromEntry(A)); 195274955Ssvnmir 196274955Ssvnmir const DomTreeNodeBase<NodeT> *IDom; 197274955Ssvnmir while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) 198280031Sdim B = IDom; // Walk up the tree 199274955Ssvnmir return IDom != nullptr; 200274955Ssvnmir } 201274955Ssvnmir 202280031Sdim /// \brief Wipe this tree's state without releasing any resources. 203280031Sdim /// 204280031Sdim /// This is essentially a post-move helper only. It leaves the object in an 205280031Sdim /// assignable and destroyable state, but otherwise invalid. 206280031Sdim void wipe() { 207280031Sdim DomTreeNodes.clear(); 208280031Sdim IDoms.clear(); 209280031Sdim Vertex.clear(); 210280031Sdim Info.clear(); 211280031Sdim RootNode = nullptr; 212280031Sdim } 213280031Sdim 214274955Ssvnmirprotected: 215288943Sdim typedef DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>> 216288943Sdim DomTreeNodeMapType; 217274955Ssvnmir DomTreeNodeMapType DomTreeNodes; 218274955Ssvnmir DomTreeNodeBase<NodeT> *RootNode; 219274955Ssvnmir 220274955Ssvnmir mutable bool DFSInfoValid; 221274955Ssvnmir mutable unsigned int SlowQueries; 222274955Ssvnmir // Information record used during immediate dominators computation. 223274955Ssvnmir struct InfoRec { 224274955Ssvnmir unsigned DFSNum; 225274955Ssvnmir unsigned Parent; 226274955Ssvnmir unsigned Semi; 227274955Ssvnmir NodeT *Label; 228274955Ssvnmir 229274955Ssvnmir InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {} 230274955Ssvnmir }; 231274955Ssvnmir 232280031Sdim DenseMap<NodeT *, NodeT *> IDoms; 233274955Ssvnmir 234274955Ssvnmir // Vertex - Map the DFS number to the NodeT* 235280031Sdim std::vector<NodeT *> Vertex; 236274955Ssvnmir 237274955Ssvnmir // Info - Collection of information used during the computation of idoms. 238280031Sdim DenseMap<NodeT *, InfoRec> Info; 239274955Ssvnmir 240274955Ssvnmir void reset() { 241274955Ssvnmir DomTreeNodes.clear(); 242274955Ssvnmir IDoms.clear(); 243274955Ssvnmir this->Roots.clear(); 244274955Ssvnmir Vertex.clear(); 245274955Ssvnmir RootNode = nullptr; 246288943Sdim DFSInfoValid = false; 247288943Sdim SlowQueries = 0; 248274955Ssvnmir } 249274955Ssvnmir 250274955Ssvnmir // NewBB is split and now it has one successor. Update dominator tree to 251274955Ssvnmir // reflect this change. 252280031Sdim template <class N, class GraphT> 253280031Sdim void Split(DominatorTreeBase<typename GraphT::NodeType> &DT, 254280031Sdim typename GraphT::NodeType *NewBB) { 255274955Ssvnmir assert(std::distance(GraphT::child_begin(NewBB), 256274955Ssvnmir GraphT::child_end(NewBB)) == 1 && 257274955Ssvnmir "NewBB should have a single successor!"); 258280031Sdim typename GraphT::NodeType *NewBBSucc = *GraphT::child_begin(NewBB); 259274955Ssvnmir 260280031Sdim std::vector<typename GraphT::NodeType *> PredBlocks; 261280031Sdim typedef GraphTraits<Inverse<N>> InvTraits; 262280031Sdim for (typename InvTraits::ChildIteratorType 263280031Sdim PI = InvTraits::child_begin(NewBB), 264280031Sdim PE = InvTraits::child_end(NewBB); 265280031Sdim PI != PE; ++PI) 266274955Ssvnmir PredBlocks.push_back(*PI); 267274955Ssvnmir 268274955Ssvnmir assert(!PredBlocks.empty() && "No predblocks?"); 269274955Ssvnmir 270274955Ssvnmir bool NewBBDominatesNewBBSucc = true; 271280031Sdim for (typename InvTraits::ChildIteratorType 272280031Sdim PI = InvTraits::child_begin(NewBBSucc), 273280031Sdim E = InvTraits::child_end(NewBBSucc); 274280031Sdim PI != E; ++PI) { 275274955Ssvnmir typename InvTraits::NodeType *ND = *PI; 276274955Ssvnmir if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && 277274955Ssvnmir DT.isReachableFromEntry(ND)) { 278274955Ssvnmir NewBBDominatesNewBBSucc = false; 279274955Ssvnmir break; 280274955Ssvnmir } 281274955Ssvnmir } 282274955Ssvnmir 283274955Ssvnmir // Find NewBB's immediate dominator and create new dominator tree node for 284274955Ssvnmir // NewBB. 285274955Ssvnmir NodeT *NewBBIDom = nullptr; 286274955Ssvnmir unsigned i = 0; 287274955Ssvnmir for (i = 0; i < PredBlocks.size(); ++i) 288274955Ssvnmir if (DT.isReachableFromEntry(PredBlocks[i])) { 289274955Ssvnmir NewBBIDom = PredBlocks[i]; 290274955Ssvnmir break; 291274955Ssvnmir } 292274955Ssvnmir 293274955Ssvnmir // It's possible that none of the predecessors of NewBB are reachable; 294274955Ssvnmir // in that case, NewBB itself is unreachable, so nothing needs to be 295274955Ssvnmir // changed. 296274955Ssvnmir if (!NewBBIDom) 297274955Ssvnmir return; 298274955Ssvnmir 299274955Ssvnmir for (i = i + 1; i < PredBlocks.size(); ++i) { 300274955Ssvnmir if (DT.isReachableFromEntry(PredBlocks[i])) 301274955Ssvnmir NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 302274955Ssvnmir } 303274955Ssvnmir 304274955Ssvnmir // Create the new dominator tree node... and set the idom of NewBB. 305274955Ssvnmir DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); 306274955Ssvnmir 307274955Ssvnmir // If NewBB strictly dominates other blocks, then it is now the immediate 308274955Ssvnmir // dominator of NewBBSucc. Update the dominator tree as appropriate. 309274955Ssvnmir if (NewBBDominatesNewBBSucc) { 310274955Ssvnmir DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc); 311274955Ssvnmir DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); 312274955Ssvnmir } 313274955Ssvnmir } 314274955Ssvnmir 315274955Ssvnmirpublic: 316274955Ssvnmir explicit DominatorTreeBase(bool isPostDom) 317280031Sdim : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {} 318274955Ssvnmir 319280031Sdim DominatorTreeBase(DominatorTreeBase &&Arg) 320280031Sdim : DominatorBase<NodeT>( 321280031Sdim std::move(static_cast<DominatorBase<NodeT> &>(Arg))), 322280031Sdim DomTreeNodes(std::move(Arg.DomTreeNodes)), 323280031Sdim RootNode(std::move(Arg.RootNode)), 324280031Sdim DFSInfoValid(std::move(Arg.DFSInfoValid)), 325280031Sdim SlowQueries(std::move(Arg.SlowQueries)), IDoms(std::move(Arg.IDoms)), 326280031Sdim Vertex(std::move(Arg.Vertex)), Info(std::move(Arg.Info)) { 327280031Sdim Arg.wipe(); 328280031Sdim } 329280031Sdim DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { 330280031Sdim DominatorBase<NodeT>::operator=( 331280031Sdim std::move(static_cast<DominatorBase<NodeT> &>(RHS))); 332280031Sdim DomTreeNodes = std::move(RHS.DomTreeNodes); 333280031Sdim RootNode = std::move(RHS.RootNode); 334280031Sdim DFSInfoValid = std::move(RHS.DFSInfoValid); 335280031Sdim SlowQueries = std::move(RHS.SlowQueries); 336280031Sdim IDoms = std::move(RHS.IDoms); 337280031Sdim Vertex = std::move(RHS.Vertex); 338280031Sdim Info = std::move(RHS.Info); 339280031Sdim RHS.wipe(); 340280031Sdim return *this; 341280031Sdim } 342280031Sdim 343274955Ssvnmir /// compare - Return false if the other dominator tree base matches this 344274955Ssvnmir /// dominator tree base. Otherwise return true. 345274955Ssvnmir bool compare(const DominatorTreeBase &Other) const { 346274955Ssvnmir 347274955Ssvnmir const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; 348274955Ssvnmir if (DomTreeNodes.size() != OtherDomTreeNodes.size()) 349274955Ssvnmir return true; 350274955Ssvnmir 351274955Ssvnmir for (typename DomTreeNodeMapType::const_iterator 352280031Sdim I = this->DomTreeNodes.begin(), 353280031Sdim E = this->DomTreeNodes.end(); 354280031Sdim I != E; ++I) { 355274955Ssvnmir NodeT *BB = I->first; 356280031Sdim typename DomTreeNodeMapType::const_iterator OI = 357280031Sdim OtherDomTreeNodes.find(BB); 358274955Ssvnmir if (OI == OtherDomTreeNodes.end()) 359274955Ssvnmir return true; 360274955Ssvnmir 361288943Sdim DomTreeNodeBase<NodeT> &MyNd = *I->second; 362288943Sdim DomTreeNodeBase<NodeT> &OtherNd = *OI->second; 363274955Ssvnmir 364288943Sdim if (MyNd.compare(&OtherNd)) 365274955Ssvnmir return true; 366274955Ssvnmir } 367274955Ssvnmir 368274955Ssvnmir return false; 369274955Ssvnmir } 370274955Ssvnmir 371280031Sdim void releaseMemory() { reset(); } 372274955Ssvnmir 373274955Ssvnmir /// getNode - return the (Post)DominatorTree node for the specified basic 374296417Sdim /// block. This is the same as using operator[] on this class. The result 375296417Sdim /// may (but is not required to) be null for a forward (backwards) 376296417Sdim /// statically unreachable block. 377280031Sdim DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const { 378288943Sdim auto I = DomTreeNodes.find(BB); 379288943Sdim if (I != DomTreeNodes.end()) 380288943Sdim return I->second.get(); 381288943Sdim return nullptr; 382274955Ssvnmir } 383274955Ssvnmir 384296417Sdim /// See getNode. 385280031Sdim DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { return getNode(BB); } 386274955Ssvnmir 387274955Ssvnmir /// getRootNode - This returns the entry node for the CFG of the function. If 388274955Ssvnmir /// this tree represents the post-dominance relations for a function, however, 389274955Ssvnmir /// this root may be a node with the block == NULL. This is the case when 390274955Ssvnmir /// there are multiple exit nodes from a particular function. Consumers of 391274955Ssvnmir /// post-dominance information must be capable of dealing with this 392274955Ssvnmir /// possibility. 393274955Ssvnmir /// 394274955Ssvnmir DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } 395274955Ssvnmir const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } 396274955Ssvnmir 397274955Ssvnmir /// Get all nodes dominated by R, including R itself. 398274955Ssvnmir void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { 399274955Ssvnmir Result.clear(); 400274955Ssvnmir const DomTreeNodeBase<NodeT> *RN = getNode(R); 401274955Ssvnmir if (!RN) 402274955Ssvnmir return; // If R is unreachable, it will not be present in the DOM tree. 403274955Ssvnmir SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; 404274955Ssvnmir WL.push_back(RN); 405274955Ssvnmir 406274955Ssvnmir while (!WL.empty()) { 407274955Ssvnmir const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); 408274955Ssvnmir Result.push_back(N->getBlock()); 409274955Ssvnmir WL.append(N->begin(), N->end()); 410274955Ssvnmir } 411274955Ssvnmir } 412274955Ssvnmir 413274955Ssvnmir /// properlyDominates - Returns true iff A dominates B and A != B. 414274955Ssvnmir /// Note that this is not a constant time operation! 415274955Ssvnmir /// 416274955Ssvnmir bool properlyDominates(const DomTreeNodeBase<NodeT> *A, 417274955Ssvnmir const DomTreeNodeBase<NodeT> *B) const { 418274955Ssvnmir if (!A || !B) 419274955Ssvnmir return false; 420274955Ssvnmir if (A == B) 421274955Ssvnmir return false; 422274955Ssvnmir return dominates(A, B); 423274955Ssvnmir } 424274955Ssvnmir 425274955Ssvnmir bool properlyDominates(const NodeT *A, const NodeT *B) const; 426274955Ssvnmir 427274955Ssvnmir /// isReachableFromEntry - Return true if A is dominated by the entry 428274955Ssvnmir /// block of the function containing it. 429280031Sdim bool isReachableFromEntry(const NodeT *A) const { 430274955Ssvnmir assert(!this->isPostDominator() && 431274955Ssvnmir "This is not implemented for post dominators"); 432274955Ssvnmir return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); 433274955Ssvnmir } 434274955Ssvnmir 435280031Sdim bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; } 436274955Ssvnmir 437274955Ssvnmir /// dominates - Returns true iff A dominates B. Note that this is not a 438274955Ssvnmir /// constant time operation! 439274955Ssvnmir /// 440280031Sdim bool dominates(const DomTreeNodeBase<NodeT> *A, 441280031Sdim const DomTreeNodeBase<NodeT> *B) const { 442274955Ssvnmir // A node trivially dominates itself. 443274955Ssvnmir if (B == A) 444274955Ssvnmir return true; 445274955Ssvnmir 446274955Ssvnmir // An unreachable node is dominated by anything. 447274955Ssvnmir if (!isReachableFromEntry(B)) 448274955Ssvnmir return true; 449274955Ssvnmir 450274955Ssvnmir // And dominates nothing. 451274955Ssvnmir if (!isReachableFromEntry(A)) 452274955Ssvnmir return false; 453274955Ssvnmir 454274955Ssvnmir // Compare the result of the tree walk and the dfs numbers, if expensive 455274955Ssvnmir // checks are enabled. 456274955Ssvnmir#ifdef XDEBUG 457274955Ssvnmir assert((!DFSInfoValid || 458274955Ssvnmir (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && 459274955Ssvnmir "Tree walk disagrees with dfs numbers!"); 460274955Ssvnmir#endif 461274955Ssvnmir 462274955Ssvnmir if (DFSInfoValid) 463274955Ssvnmir return B->DominatedBy(A); 464274955Ssvnmir 465274955Ssvnmir // If we end up with too many slow queries, just update the 466274955Ssvnmir // DFS numbers on the theory that we are going to keep querying. 467274955Ssvnmir SlowQueries++; 468274955Ssvnmir if (SlowQueries > 32) { 469274955Ssvnmir updateDFSNumbers(); 470274955Ssvnmir return B->DominatedBy(A); 471274955Ssvnmir } 472274955Ssvnmir 473274955Ssvnmir return dominatedBySlowTreeWalk(A, B); 474274955Ssvnmir } 475274955Ssvnmir 476274955Ssvnmir bool dominates(const NodeT *A, const NodeT *B) const; 477274955Ssvnmir 478274955Ssvnmir NodeT *getRoot() const { 479274955Ssvnmir assert(this->Roots.size() == 1 && "Should always have entry node!"); 480274955Ssvnmir return this->Roots[0]; 481274955Ssvnmir } 482274955Ssvnmir 483274955Ssvnmir /// findNearestCommonDominator - Find nearest common dominator basic block 484274955Ssvnmir /// for basic block A and B. If there is no such block then return NULL. 485274955Ssvnmir NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { 486274955Ssvnmir assert(A->getParent() == B->getParent() && 487274955Ssvnmir "Two blocks are not in same function"); 488274955Ssvnmir 489274955Ssvnmir // If either A or B is a entry block then it is nearest common dominator 490274955Ssvnmir // (for forward-dominators). 491274955Ssvnmir if (!this->isPostDominator()) { 492274955Ssvnmir NodeT &Entry = A->getParent()->front(); 493274955Ssvnmir if (A == &Entry || B == &Entry) 494274955Ssvnmir return &Entry; 495274955Ssvnmir } 496274955Ssvnmir 497274955Ssvnmir // If B dominates A then B is nearest common dominator. 498274955Ssvnmir if (dominates(B, A)) 499274955Ssvnmir return B; 500274955Ssvnmir 501274955Ssvnmir // If A dominates B then A is nearest common dominator. 502274955Ssvnmir if (dominates(A, B)) 503274955Ssvnmir return A; 504274955Ssvnmir 505274955Ssvnmir DomTreeNodeBase<NodeT> *NodeA = getNode(A); 506274955Ssvnmir DomTreeNodeBase<NodeT> *NodeB = getNode(B); 507274955Ssvnmir 508274955Ssvnmir // If we have DFS info, then we can avoid all allocations by just querying 509274955Ssvnmir // it from each IDom. Note that because we call 'dominates' twice above, we 510274955Ssvnmir // expect to call through this code at most 16 times in a row without 511274955Ssvnmir // building valid DFS information. This is important as below is a *very* 512274955Ssvnmir // slow tree walk. 513274955Ssvnmir if (DFSInfoValid) { 514274955Ssvnmir DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 515274955Ssvnmir while (IDomA) { 516274955Ssvnmir if (NodeB->DominatedBy(IDomA)) 517274955Ssvnmir return IDomA->getBlock(); 518274955Ssvnmir IDomA = IDomA->getIDom(); 519274955Ssvnmir } 520274955Ssvnmir return nullptr; 521274955Ssvnmir } 522274955Ssvnmir 523274955Ssvnmir // Collect NodeA dominators set. 524280031Sdim SmallPtrSet<DomTreeNodeBase<NodeT> *, 16> NodeADoms; 525274955Ssvnmir NodeADoms.insert(NodeA); 526274955Ssvnmir DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 527274955Ssvnmir while (IDomA) { 528274955Ssvnmir NodeADoms.insert(IDomA); 529274955Ssvnmir IDomA = IDomA->getIDom(); 530274955Ssvnmir } 531274955Ssvnmir 532274955Ssvnmir // Walk NodeB immediate dominators chain and find common dominator node. 533274955Ssvnmir DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom(); 534274955Ssvnmir while (IDomB) { 535274955Ssvnmir if (NodeADoms.count(IDomB) != 0) 536274955Ssvnmir return IDomB->getBlock(); 537274955Ssvnmir 538274955Ssvnmir IDomB = IDomB->getIDom(); 539274955Ssvnmir } 540274955Ssvnmir 541274955Ssvnmir return nullptr; 542274955Ssvnmir } 543274955Ssvnmir 544274955Ssvnmir const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { 545274955Ssvnmir // Cast away the const qualifiers here. This is ok since 546274955Ssvnmir // const is re-introduced on the return type. 547274955Ssvnmir return findNearestCommonDominator(const_cast<NodeT *>(A), 548274955Ssvnmir const_cast<NodeT *>(B)); 549274955Ssvnmir } 550274955Ssvnmir 551274955Ssvnmir //===--------------------------------------------------------------------===// 552274955Ssvnmir // API to update (Post)DominatorTree information based on modifications to 553274955Ssvnmir // the CFG... 554274955Ssvnmir 555274955Ssvnmir /// addNewBlock - Add a new node to the dominator tree information. This 556274955Ssvnmir /// creates a new node as a child of DomBB dominator node,linking it into 557274955Ssvnmir /// the children list of the immediate dominator. 558274955Ssvnmir DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 559274955Ssvnmir assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 560274955Ssvnmir DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 561274955Ssvnmir assert(IDomNode && "Not immediate dominator specified for block!"); 562274955Ssvnmir DFSInfoValid = false; 563288943Sdim return (DomTreeNodes[BB] = IDomNode->addChild( 564288943Sdim llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get(); 565274955Ssvnmir } 566274955Ssvnmir 567274955Ssvnmir /// changeImmediateDominator - This method is used to update the dominator 568274955Ssvnmir /// tree information when a node's immediate dominator changes. 569274955Ssvnmir /// 570274955Ssvnmir void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, 571274955Ssvnmir DomTreeNodeBase<NodeT> *NewIDom) { 572274955Ssvnmir assert(N && NewIDom && "Cannot change null node pointers!"); 573274955Ssvnmir DFSInfoValid = false; 574274955Ssvnmir N->setIDom(NewIDom); 575274955Ssvnmir } 576274955Ssvnmir 577274955Ssvnmir void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 578274955Ssvnmir changeImmediateDominator(getNode(BB), getNode(NewBB)); 579274955Ssvnmir } 580274955Ssvnmir 581274955Ssvnmir /// eraseNode - Removes a node from the dominator tree. Block must not 582274955Ssvnmir /// dominate any other blocks. Removes node from its immediate dominator's 583274955Ssvnmir /// children list. Deletes dominator node associated with basic block BB. 584274955Ssvnmir void eraseNode(NodeT *BB) { 585274955Ssvnmir DomTreeNodeBase<NodeT> *Node = getNode(BB); 586274955Ssvnmir assert(Node && "Removing node that isn't in dominator tree."); 587274955Ssvnmir assert(Node->getChildren().empty() && "Node is not a leaf node."); 588274955Ssvnmir 589280031Sdim // Remove node from immediate dominator's children list. 590274955Ssvnmir DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 591274955Ssvnmir if (IDom) { 592280031Sdim typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I = 593280031Sdim std::find(IDom->Children.begin(), IDom->Children.end(), Node); 594274955Ssvnmir assert(I != IDom->Children.end() && 595274955Ssvnmir "Not in immediate dominator children set!"); 596274955Ssvnmir // I am no longer your child... 597274955Ssvnmir IDom->Children.erase(I); 598274955Ssvnmir } 599274955Ssvnmir 600274955Ssvnmir DomTreeNodes.erase(BB); 601274955Ssvnmir } 602274955Ssvnmir 603274955Ssvnmir /// splitBlock - BB is split and now it has one successor. Update dominator 604274955Ssvnmir /// tree to reflect this change. 605280031Sdim void splitBlock(NodeT *NewBB) { 606274955Ssvnmir if (this->IsPostDominators) 607280031Sdim this->Split<Inverse<NodeT *>, GraphTraits<Inverse<NodeT *>>>(*this, 608280031Sdim NewBB); 609274955Ssvnmir else 610280031Sdim this->Split<NodeT *, GraphTraits<NodeT *>>(*this, NewBB); 611274955Ssvnmir } 612274955Ssvnmir 613274955Ssvnmir /// print - Convert to human readable form 614274955Ssvnmir /// 615274955Ssvnmir void print(raw_ostream &o) const { 616274955Ssvnmir o << "=============================--------------------------------\n"; 617274955Ssvnmir if (this->isPostDominator()) 618274955Ssvnmir o << "Inorder PostDominator Tree: "; 619274955Ssvnmir else 620274955Ssvnmir o << "Inorder Dominator Tree: "; 621274955Ssvnmir if (!this->DFSInfoValid) 622274955Ssvnmir o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 623274955Ssvnmir o << "\n"; 624274955Ssvnmir 625274955Ssvnmir // The postdom tree can have a null root if there are no returns. 626274955Ssvnmir if (getRootNode()) 627274955Ssvnmir PrintDomTree<NodeT>(getRootNode(), o, 1); 628274955Ssvnmir } 629274955Ssvnmir 630274955Ssvnmirprotected: 631280031Sdim template <class GraphT> 632280031Sdim friend typename GraphT::NodeType * 633280031Sdim Eval(DominatorTreeBase<typename GraphT::NodeType> &DT, 634280031Sdim typename GraphT::NodeType *V, unsigned LastLinked); 635274955Ssvnmir 636280031Sdim template <class GraphT> 637280031Sdim friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType> &DT, 638280031Sdim typename GraphT::NodeType *V, unsigned N); 639274955Ssvnmir 640280031Sdim template <class FuncT, class N> 641280031Sdim friend void 642280031Sdim Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT, FuncT &F); 643274955Ssvnmir 644288943Sdim 645288943Sdim DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { 646288943Sdim if (DomTreeNodeBase<NodeT> *Node = getNode(BB)) 647288943Sdim return Node; 648288943Sdim 649288943Sdim // Haven't calculated this node yet? Get or calculate the node for the 650288943Sdim // immediate dominator. 651288943Sdim NodeT *IDom = getIDom(BB); 652288943Sdim 653288943Sdim assert(IDom || this->DomTreeNodes[nullptr]); 654288943Sdim DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); 655288943Sdim 656288943Sdim // Add a new tree node for this NodeT, and link it as a child of 657288943Sdim // IDomNode 658288943Sdim return (this->DomTreeNodes[BB] = IDomNode->addChild( 659288943Sdim llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get(); 660288943Sdim } 661288943Sdim 662288943Sdim NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); } 663288943Sdim 664288943Sdim void addRoot(NodeT *BB) { this->Roots.push_back(BB); } 665288943Sdim 666288943Sdimpublic: 667274955Ssvnmir /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 668274955Ssvnmir /// dominator tree in dfs order. 669274955Ssvnmir void updateDFSNumbers() const { 670288943Sdim 671288943Sdim if (DFSInfoValid) { 672288943Sdim SlowQueries = 0; 673288943Sdim return; 674288943Sdim } 675288943Sdim 676274955Ssvnmir unsigned DFSNum = 0; 677274955Ssvnmir 678280031Sdim SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, 679280031Sdim typename DomTreeNodeBase<NodeT>::const_iterator>, 680280031Sdim 32> WorkStack; 681274955Ssvnmir 682274955Ssvnmir const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); 683274955Ssvnmir 684274955Ssvnmir if (!ThisRoot) 685274955Ssvnmir return; 686274955Ssvnmir 687274955Ssvnmir // Even in the case of multiple exits that form the post dominator root 688274955Ssvnmir // nodes, do not iterate over all exits, but start from the virtual root 689274955Ssvnmir // node. Otherwise bbs, that are not post dominated by any exit but by the 690274955Ssvnmir // virtual root node, will never be assigned a DFS number. 691274955Ssvnmir WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); 692274955Ssvnmir ThisRoot->DFSNumIn = DFSNum++; 693274955Ssvnmir 694274955Ssvnmir while (!WorkStack.empty()) { 695274955Ssvnmir const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 696274955Ssvnmir typename DomTreeNodeBase<NodeT>::const_iterator ChildIt = 697280031Sdim WorkStack.back().second; 698274955Ssvnmir 699274955Ssvnmir // If we visited all of the children of this node, "recurse" back up the 700274955Ssvnmir // stack setting the DFOutNum. 701274955Ssvnmir if (ChildIt == Node->end()) { 702274955Ssvnmir Node->DFSNumOut = DFSNum++; 703274955Ssvnmir WorkStack.pop_back(); 704274955Ssvnmir } else { 705274955Ssvnmir // Otherwise, recursively visit this child. 706274955Ssvnmir const DomTreeNodeBase<NodeT> *Child = *ChildIt; 707274955Ssvnmir ++WorkStack.back().second; 708274955Ssvnmir 709274955Ssvnmir WorkStack.push_back(std::make_pair(Child, Child->begin())); 710274955Ssvnmir Child->DFSNumIn = DFSNum++; 711274955Ssvnmir } 712274955Ssvnmir } 713274955Ssvnmir 714274955Ssvnmir SlowQueries = 0; 715274955Ssvnmir DFSInfoValid = true; 716274955Ssvnmir } 717274955Ssvnmir 718274955Ssvnmir /// recalculate - compute a dominator tree for the given function 719280031Sdim template <class FT> void recalculate(FT &F) { 720280031Sdim typedef GraphTraits<FT *> TraitsTy; 721274955Ssvnmir reset(); 722274955Ssvnmir this->Vertex.push_back(nullptr); 723274955Ssvnmir 724274955Ssvnmir if (!this->IsPostDominators) { 725274955Ssvnmir // Initialize root 726274955Ssvnmir NodeT *entry = TraitsTy::getEntryNode(&F); 727296417Sdim addRoot(entry); 728274955Ssvnmir 729280031Sdim Calculate<FT, NodeT *>(*this, F); 730274955Ssvnmir } else { 731274955Ssvnmir // Initialize the roots list 732274955Ssvnmir for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), 733280031Sdim E = TraitsTy::nodes_end(&F); 734296417Sdim I != E; ++I) 735296417Sdim if (TraitsTy::child_begin(&*I) == TraitsTy::child_end(&*I)) 736296417Sdim addRoot(&*I); 737274955Ssvnmir 738280031Sdim Calculate<FT, Inverse<NodeT *>>(*this, F); 739274955Ssvnmir } 740274955Ssvnmir } 741274955Ssvnmir}; 742274955Ssvnmir 743274955Ssvnmir// These two functions are declared out of line as a workaround for building 744274955Ssvnmir// with old (< r147295) versions of clang because of pr11642. 745280031Sdimtemplate <class NodeT> 746274955Ssvnmirbool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const { 747274955Ssvnmir if (A == B) 748274955Ssvnmir return true; 749274955Ssvnmir 750274955Ssvnmir // Cast away the const qualifiers here. This is ok since 751274955Ssvnmir // this function doesn't actually return the values returned 752274955Ssvnmir // from getNode. 753274955Ssvnmir return dominates(getNode(const_cast<NodeT *>(A)), 754274955Ssvnmir getNode(const_cast<NodeT *>(B))); 755274955Ssvnmir} 756280031Sdimtemplate <class NodeT> 757280031Sdimbool DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, 758280031Sdim const NodeT *B) const { 759274955Ssvnmir if (A == B) 760274955Ssvnmir return false; 761274955Ssvnmir 762274955Ssvnmir // Cast away the const qualifiers here. This is ok since 763274955Ssvnmir // this function doesn't actually return the values returned 764274955Ssvnmir // from getNode. 765274955Ssvnmir return dominates(getNode(const_cast<NodeT *>(A)), 766274955Ssvnmir getNode(const_cast<NodeT *>(B))); 767274955Ssvnmir} 768274955Ssvnmir 769274955Ssvnmir} 770274955Ssvnmir 771274955Ssvnmir#endif 772