GenericDomTree.h revision ebe69fe11e48d322045d5949c83283927a0d790b
136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \file 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This file defines a set of templates that efficiently compute a dominator 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// tree over a generic graph. This is used typically in LLVM for fast 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// dominance queries on the CFG, but is fully generic w.r.t. the underlying 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// graph types. 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1670b6337d681b1d0a62922ce806fc15c2b8a31e5fChris Lattner//===----------------------------------------------------------------------===// 1770b6337d681b1d0a62922ce806fc15c2b8a31e5fChris Lattner 1837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#ifndef LLVM_SUPPORT_GENERICDOMTREE_H 1937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#define LLVM_SUPPORT_GENERICDOMTREE_H 2070b6337d681b1d0a62922ce806fc15c2b8a31e5fChris Lattner 2149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/ADT/DenseMap.h" 22f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner#include "llvm/ADT/DepthFirstIterator.h" 2378daec973e81b1e85c2c3f5882845317da432f21Owen Anderson#include "llvm/ADT/GraphTraits.h" 24ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/ADT/STLExtras.h" 2549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 2649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/ADT/SmallVector.h" 2749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/Support/Compiler.h" 28791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner#include "llvm/Support/raw_ostream.h" 291aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson#include <algorithm> 307a73b80b9052136c8cd2234eb3433a07df7cf38eJohn Criswell 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 33ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// \brief Base class that other, more interesting dominator analyses 34dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman/// inherit from. 35ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> class DominatorBase { 36c348d21bf6160c1f1d1511cc432bc8a7ede66244Chris Lattnerprotected: 37ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<NodeT *> Roots; 38ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool IsPostDominators; 39ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines explicit DominatorBase(bool isPostDom) 40ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : Roots(), IsPostDominators(isPostDom) {} 41ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorBase(DominatorBase &&Arg) 42ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : Roots(std::move(Arg.Roots)), 43ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IsPostDominators(std::move(Arg.IsPostDominators)) { 44ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Arg.Roots.clear(); 45ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 46ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorBase &operator=(DominatorBase &&RHS) { 47ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Roots = std::move(RHS.Roots); 48ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IsPostDominators = std::move(RHS.IsPostDominators); 49ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RHS.Roots.clear(); 50ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return *this; 51ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 52794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 53ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinespublic: 5467d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman /// getRoots - Return the root blocks of the current CFG. This may include 55dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// multiple blocks if we are computing post dominators. For forward 56dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// dominators, this will always be a single block (the entry node). 57dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 58ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const std::vector<NodeT *> &getRoots() const { return Roots; } 59facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 60dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// isPostDominator - Returns true if analysis based of postdoms 61dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 62facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner bool isPostDominator() const { return IsPostDominators; } 63c348d21bf6160c1f1d1511cc432bc8a7ede66244Chris Lattner}; 64c348d21bf6160c1f1d1511cc432bc8a7ede66244Chris Lattner 65ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> class DominatorTreeBase; 66efd4a5144b03f61ebfd53d0245176f95e1170fb8Hartmut Kaiserstruct PostDominatorTree; 671aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson 68ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// \brief Base class for the actual dominator tree node. 69ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> class DomTreeNodeBase { 701aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson NodeT *TheBB; 711aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson DomTreeNodeBase<NodeT> *IDom; 721aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson std::vector<DomTreeNodeBase<NodeT> *> Children; 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines mutable int DFSNumIn, DFSNumOut; 743726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 75ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class N> friend class DominatorTreeBase; 76efd4a5144b03f61ebfd53d0245176f95e1170fb8Hartmut Kaiser friend struct PostDominatorTree; 77ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7826042420d642e810f5cdfb2da6156b74aaf80945Devang Patelpublic: 791aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator; 801aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator 81ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const_iterator; 820aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 83ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines iterator begin() { return Children.begin(); } 84ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines iterator end() { return Children.end(); } 8526042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const_iterator begin() const { return Children.begin(); } 86ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const_iterator end() const { return Children.end(); } 870aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 881aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson NodeT *getBlock() const { return TheBB; } 891aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson DomTreeNodeBase<NodeT> *getIDom() const { return IDom; } 90ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const std::vector<DomTreeNodeBase<NodeT> *> &getChildren() const { 911aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson return Children; 921aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson } 93a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 941aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom) 95ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) {} 960aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 97ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::unique_ptr<DomTreeNodeBase<NodeT>> 98ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines addChild(std::unique_ptr<DomTreeNodeBase<NodeT>> C) { 99ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Children.push_back(C.get()); 1001aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson return C; 1011aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson } 1025b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 103ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines size_t getNumChildren() const { return Children.size(); } 104a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 105ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void clearAllChildren() { Children.clear(); } 1060aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 107fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak bool compare(const DomTreeNodeBase<NodeT> *Other) const { 108a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (getNumChildren() != Other->getNumChildren()) 109a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 110a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 111fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak SmallPtrSet<const NodeT *, 4> OtherChildren; 112fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) { 113fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak const NodeT *Nd = (*I)->getBlock(); 114a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel OtherChildren.insert(Nd); 115a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel } 116a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 117fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak for (const_iterator I = begin(), E = end(); I != E; ++I) { 118fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak const NodeT *N = (*I)->getBlock(); 119a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (OtherChildren.count(N) == 0) 120a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 121a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel } 122a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return false; 123a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel } 124a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 1251aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson void setIDom(DomTreeNodeBase<NodeT> *NewIDom) { 1261aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson assert(IDom && "No immediate dominator?"); 1271aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson if (IDom != NewIDom) { 128ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I = 129ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::find(IDom->Children.begin(), IDom->Children.end(), this); 1301aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson assert(I != IDom->Children.end() && 1311aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson "Not in immediate dominator children set!"); 1321aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson // I am no longer your child... 1331aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson IDom->Children.erase(I); 1341aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson 1351aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson // Switch to new dominator 1361aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson IDom = NewIDom; 1371aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson IDom->Children.push_back(this); 1381aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson } 1391aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson } 1400aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 141c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do 142c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner /// not call them. 143c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner unsigned getDFSNumIn() const { return DFSNumIn; } 144c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner unsigned getDFSNumOut() const { return DFSNumOut; } 145ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1469c7ee6b19fab7a269994264bc19bf4d19c33b3c3Devang Patelprivate: 147c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner // Return true if this node is dominated by other. Use this only if DFS info 148c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner // is valid. 1491aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const { 1503726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel return this->DFSNumIn >= other->DFSNumIn && 151ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines this->DFSNumOut <= other->DFSNumOut; 1523726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 15326042420d642e810f5cdfb2da6156b74aaf80945Devang Patel}; 15426042420d642e810f5cdfb2da6156b74aaf80945Devang Patel 155ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> 156ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesraw_ostream &operator<<(raw_ostream &o, const DomTreeNodeBase<NodeT> *Node) { 15749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (Node->getBlock()) 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Node->getBlock()->printAsOperand(o, false); 15949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson else 16049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << " <<exit node>>"; 1610aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 16249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; 1630aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 16449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return o << "\n"; 16549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson} 16649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 167ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> 168ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesvoid PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o, 169ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned Lev) { 170ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines o.indent(2 * Lev) << "[" << Lev << "] " << N; 17149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), 172ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines E = N->end(); 173ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I != E; ++I) 174ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PrintDomTree<NodeT>(*I, o, Lev + 1); 17549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson} 17649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 177ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// The calculate routine is provided in a separate header but referenced here. 178ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class FuncT, class N> 179ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesvoid Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT, 180ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FuncT &F); 18149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 182ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// \brief Core dominator tree base class. 183ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 184ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// This class is a generic template over graph nodes. It is instantiated for 185ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// various graphs in the LLVM IR or in the code generator. 186ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> { 187ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorTreeBase(const DominatorTreeBase &) = delete; 188ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; 18905d2318fbde7b603bd6de690f18d48e0ef44d81dOwen Anderson 1901c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 1911c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola const DomTreeNodeBase<NodeT> *B) const { 1921c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola assert(A != B); 1931c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola assert(isReachableFromEntry(B)); 1941c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola assert(isReachableFromEntry(A)); 1951c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola 1961c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola const DomTreeNodeBase<NodeT> *IDom; 197dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) 198ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines B = IDom; // Walk up the tree 199dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return IDom != nullptr; 2001c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola } 2011c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola 202ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// \brief Wipe this tree's state without releasing any resources. 203ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// 204ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// This is essentially a post-move helper only. It leaves the object in an 205ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// assignable and destroyable state, but otherwise invalid. 206ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void wipe() { 207ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodes.clear(); 208ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IDoms.clear(); 209ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Vertex.clear(); 210ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Info.clear(); 211ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RootNode = nullptr; 212ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 213ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 21431b935357d1396d3be32fdf24dcb0319a6908c6fChris Lattnerprotected: 215ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>> 216ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeMapType; 2179a51157db555395f7a6ad89faec40b3afa121091Devang Patel DomTreeNodeMapType DomTreeNodes; 21849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *RootNode; 2193dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 22036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines mutable bool DFSInfoValid; 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines mutable unsigned int SlowQueries; 22226a6908768a0139fff72bc07908d55872cba136bDevang Patel // Information record used during immediate dominators computation. 223e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson struct InfoRec { 2241f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson unsigned DFSNum; 22554cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich unsigned Parent; 22626d5d16a2c8ef6c0763afbfe06c940c40c461d6eNate Begeman unsigned Semi; 22711e222da1fe498a3c528d197ab57982e3bb5762dCameron Zwarich NodeT *Label; 2283dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 229dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {} 23026d5d16a2c8ef6c0763afbfe06c940c40c461d6eNate Begeman }; 2313dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 232ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DenseMap<NodeT *, NodeT *> IDoms; 23326d5d16a2c8ef6c0763afbfe06c940c40c461d6eNate Begeman 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Vertex - Map the DFS number to the NodeT* 235ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<NodeT *> Vertex; 2363dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 23726d5d16a2c8ef6c0763afbfe06c940c40c461d6eNate Begeman // Info - Collection of information used during the computation of idoms. 238ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DenseMap<NodeT *, InfoRec> Info; 23949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 24049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void reset() { 24149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodes.clear(); 24249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDoms.clear(); 24349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson this->Roots.clear(); 24449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson Vertex.clear(); 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RootNode = nullptr; 24649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 2470aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 2487b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // NewBB is split and now it has one successor. Update dominator tree to 2497b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // reflect this change. 250ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class N, class GraphT> 251ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void Split(DominatorTreeBase<typename GraphT::NodeType> &DT, 252ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename GraphT::NodeType *NewBB) { 25392d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(std::distance(GraphT::child_begin(NewBB), 25492d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman GraphT::child_end(NewBB)) == 1 && 25592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "NewBB should have a single successor!"); 256ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename GraphT::NodeType *NewBBSucc = *GraphT::child_begin(NewBB); 257ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 258ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<typename GraphT::NodeType *> PredBlocks; 259ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef GraphTraits<Inverse<N>> InvTraits; 260ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (typename InvTraits::ChildIteratorType 261ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PI = InvTraits::child_begin(NewBB), 262ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PE = InvTraits::child_end(NewBB); 263ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PI != PE; ++PI) 26467d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman PredBlocks.push_back(*PI); 2657b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 266e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif assert(!PredBlocks.empty() && "No predblocks?"); 267e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman 268e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman bool NewBBDominatesNewBBSucc = true; 269ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (typename InvTraits::ChildIteratorType 270ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PI = InvTraits::child_begin(NewBBSucc), 271ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines E = InvTraits::child_end(NewBBSucc); 272ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PI != E; ++PI) { 2737c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif typename InvTraits::NodeType *ND = *PI; 2747c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && 2757c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif DT.isReachableFromEntry(ND)) { 27615002a2b528e04a5edcfccbec392f5d6b19f7f6aEli Friedman NewBBDominatesNewBBSucc = false; 27715002a2b528e04a5edcfccbec392f5d6b19f7f6aEli Friedman break; 278e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman } 279e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif } 280e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman 2817b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // Find NewBB's immediate dominator and create new dominator tree node for 2827b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // NewBB. 283dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NodeT *NewBBIDom = nullptr; 2847b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson unsigned i = 0; 2857b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson for (i = 0; i < PredBlocks.size(); ++i) 2867b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (DT.isReachableFromEntry(PredBlocks[i])) { 2877b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson NewBBIDom = PredBlocks[i]; 2887b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson break; 2897b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 290a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman 291a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // It's possible that none of the predecessors of NewBB are reachable; 292a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // in that case, NewBB itself is unreachable, so nothing needs to be 293a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // changed. 294a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman if (!NewBBIDom) 295a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman return; 296a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman 2977b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson for (i = i + 1; i < PredBlocks.size(); ++i) { 2987b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (DT.isReachableFromEntry(PredBlocks[i])) 2997b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 3007b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 3017b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 3027b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // Create the new dominator tree node... and set the idom of NewBB. 30308895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); 3047b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 3057b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // If NewBB strictly dominates other blocks, then it is now the immediate 3067b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // dominator of NewBBSucc. Update the dominator tree as appropriate. 3077b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (NewBBDominatesNewBBSucc) { 30808895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc); 3097b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); 3107b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 3117b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 312420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner 3133e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattnerpublic: 314950a4c40b823cd4f09dc71be635229246dfd6cacDan Gohman explicit DominatorTreeBase(bool isPostDom) 315ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {} 316ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 317ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorTreeBase(DominatorTreeBase &&Arg) 318ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : DominatorBase<NodeT>( 319ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::move(static_cast<DominatorBase<NodeT> &>(Arg))), 320ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodes(std::move(Arg.DomTreeNodes)), 321ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RootNode(std::move(Arg.RootNode)), 322ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DFSInfoValid(std::move(Arg.DFSInfoValid)), 323ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SlowQueries(std::move(Arg.SlowQueries)), IDoms(std::move(Arg.IDoms)), 324ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Vertex(std::move(Arg.Vertex)), Info(std::move(Arg.Info)) { 325ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Arg.wipe(); 326ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 327ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { 328ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorBase<NodeT>::operator=( 329ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::move(static_cast<DominatorBase<NodeT> &>(RHS))); 330ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodes = std::move(RHS.DomTreeNodes); 331ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RootNode = std::move(RHS.RootNode); 332ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DFSInfoValid = std::move(RHS.DFSInfoValid); 333ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SlowQueries = std::move(RHS.SlowQueries); 334ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IDoms = std::move(RHS.IDoms); 335ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Vertex = std::move(RHS.Vertex); 336ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Info = std::move(RHS.Info); 337ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RHS.wipe(); 338ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return *this; 339ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 3400cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 341844a3d163bc644085b1d744797da43eb9bf7ee3bDevang Patel /// compare - Return false if the other dominator tree base matches this 3425b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel /// dominator tree base. Otherwise return true. 34336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool compare(const DominatorTreeBase &Other) const { 3445b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 345a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; 346a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (DomTreeNodes.size() != OtherDomTreeNodes.size()) 347a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 348a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 34967d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman for (typename DomTreeNodeMapType::const_iterator 350ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I = this->DomTreeNodes.begin(), 351ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines E = this->DomTreeNodes.end(); 352ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I != E; ++I) { 353a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel NodeT *BB = I->first; 354ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename DomTreeNodeMapType::const_iterator OI = 355ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OtherDomTreeNodes.find(BB); 356a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (OI == OtherDomTreeNodes.end()) 357a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 3585b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 359ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeBase<NodeT> &MyNd = *I->second; 360ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeBase<NodeT> &OtherNd = *OI->second; 3610aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 362ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (MyNd.compare(&OtherNd)) 3635b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel return true; 3645b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel } 365a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 3665b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel return false; 3675b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel } 3685b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 369ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void releaseMemory() { reset(); } 3700cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 3710c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// getNode - return the (Post)DominatorTree node for the specified basic 3720c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// block. This is the same as using operator[] on this class. 3730c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// 374ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const { 375ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto I = DomTreeNodes.find(BB); 376ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I != DomTreeNodes.end()) 377ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return I->second.get(); 378ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return nullptr; 3790cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner } 38097f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner 381ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { return getNode(BB); } 382c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 383dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// getRootNode - This returns the entry node for the CFG of the function. If 384dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// this tree represents the post-dominance relations for a function, however, 385dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// this root may be a node with the block == NULL. This is the case when 386dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// there are multiple exit nodes from a particular function. Consumers of 387dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// post-dominance information must be capable of dealing with this 388dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// possibility. 389dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 39049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } 39149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } 392420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner 39336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Get all nodes dominated by R, including R itself. 3944f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { 39536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Result.clear(); 3964f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang const DomTreeNodeBase<NodeT> *RN = getNode(R); 397dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!RN) 39836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return; // If R is unreachable, it will not be present in the DOM tree. 3994f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; 4004f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang WL.push_back(RN); 4014f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang 4024f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang while (!WL.empty()) { 4034f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); 4044f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang Result.push_back(N->getBlock()); 4054f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang WL.append(N->begin(), N->end()); 4064f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang } 4074f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang } 4084f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang 4094fde2f6a280d0697c31d82e4148a4ba36fc8c0f0Jakub Staszak /// properlyDominates - Returns true iff A dominates B and A != B. 4109a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// Note that this is not a constant time operation! 4119a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// 41249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson bool properlyDominates(const DomTreeNodeBase<NodeT> *A, 41336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *B) const { 414dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!A || !B) 41542c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return false; 41642c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola if (A == B) 41742c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return false; 41842c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return dominates(A, B); 4199a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 4209a51157db555395f7a6ad89faec40b3afa121091Devang Patel 42136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool properlyDominates(const NodeT *A, const NodeT *B) const; 422f11cc5c298b5c2bae45159ebd305e75dd0d5091bDevang Patel 423dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel /// isReachableFromEntry - Return true if A is dominated by the entry 424dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel /// block of the function containing it. 425ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool isReachableFromEntry(const NodeT *A) const { 42692d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(!this->isPostDominator() && 42792d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "This is not implemented for post dominators"); 428092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); 429092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola } 430092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola 431ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; } 4320aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 43394c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru /// dominates - Returns true iff A dominates B. Note that this is not a 4349a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// constant time operation! 4359a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// 436ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool dominates(const DomTreeNodeBase<NodeT> *A, 437ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const DomTreeNodeBase<NodeT> *B) const { 438092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // A node trivially dominates itself. 43967d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman if (B == A) 440092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return true; 441259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 442092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // An unreachable node is dominated by anything. 443092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(B)) 444092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return true; 445092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola 446092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // And dominates nothing. 447092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(A)) 448259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel return false; 4499a51157db555395f7a6ad89faec40b3afa121091Devang Patel 450fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser // Compare the result of the tree walk and the dfs numbers, if expensive 451fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser // checks are enabled. 452fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser#ifdef XDEBUG 45392d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert((!DFSInfoValid || 45492d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && 45592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "Tree walk disagrees with dfs numbers!"); 456fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser#endif 457fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser 4589a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (DFSInfoValid) 4593726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel return B->DominatedBy(A); 4609a51157db555395f7a6ad89faec40b3afa121091Devang Patel 4619a51157db555395f7a6ad89faec40b3afa121091Devang Patel // If we end up with too many slow queries, just update the 4629a51157db555395f7a6ad89faec40b3afa121091Devang Patel // DFS numbers on the theory that we are going to keep querying. 4639a51157db555395f7a6ad89faec40b3afa121091Devang Patel SlowQueries++; 4649a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (SlowQueries > 32) { 4659a51157db555395f7a6ad89faec40b3afa121091Devang Patel updateDFSNumbers(); 4663726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel return B->DominatedBy(A); 4679a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 4684d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel 4699a51157db555395f7a6ad89faec40b3afa121091Devang Patel return dominatedBySlowTreeWalk(A, B); 4709a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 471259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 47236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool dominates(const NodeT *A, const NodeT *B) const; 4730aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 47478daec973e81b1e85c2c3f5882845317da432f21Owen Anderson NodeT *getRoot() const { 47578daec973e81b1e85c2c3f5882845317da432f21Owen Anderson assert(this->Roots.size() == 1 && "Should always have entry node!"); 47678daec973e81b1e85c2c3f5882845317da432f21Owen Anderson return this->Roots[0]; 47778daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 478259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 479fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel /// findNearestCommonDominator - Find nearest common dominator basic block 480fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel /// for basic block A and B. If there is no such block then return NULL. 48149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { 48292d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(A->getParent() == B->getParent() && 48392d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "Two blocks are not in same function"); 48449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 48566617633e7dcc14d8808d3118766916b2240722aDan Gohman // If either A or B is a entry block then it is nearest common dominator 48666617633e7dcc14d8808d3118766916b2240722aDan Gohman // (for forward-dominators). 48766617633e7dcc14d8808d3118766916b2240722aDan Gohman if (!this->isPostDominator()) { 48892d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman NodeT &Entry = A->getParent()->front(); 48966617633e7dcc14d8808d3118766916b2240722aDan Gohman if (A == &Entry || B == &Entry) 49066617633e7dcc14d8808d3118766916b2240722aDan Gohman return &Entry; 49166617633e7dcc14d8808d3118766916b2240722aDan Gohman } 49249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 49349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // If B dominates A then B is nearest common dominator. 49449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (dominates(B, A)) 49549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return B; 49649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 49749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // If A dominates B then A is nearest common dominator. 49849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (dominates(A, B)) 49949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return A; 50049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 50149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NodeA = getNode(A); 50249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NodeB = getNode(B); 50349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 504dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If we have DFS info, then we can avoid all allocations by just querying 505dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // it from each IDom. Note that because we call 'dominates' twice above, we 506dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // expect to call through this code at most 16 times in a row without 507dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // building valid DFS information. This is important as below is a *very* 508dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // slow tree walk. 509dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (DFSInfoValid) { 510dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 511dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (IDomA) { 512dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (NodeB->DominatedBy(IDomA)) 513dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return IDomA->getBlock(); 514dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IDomA = IDomA->getIDom(); 515dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 516dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 517dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 518dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 51949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Collect NodeA dominators set. 520ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallPtrSet<DomTreeNodeBase<NodeT> *, 16> NodeADoms; 52149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeADoms.insert(NodeA); 52249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 52349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson while (IDomA) { 52449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeADoms.insert(IDomA); 52549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDomA = IDomA->getIDom(); 52649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 52749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 52849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Walk NodeB immediate dominators chain and find common dominator node. 52949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom(); 53092d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman while (IDomB) { 53149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (NodeADoms.count(IDomB) != 0) 53249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return IDomB->getBlock(); 53349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 53449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDomB = IDomB->getIDom(); 53549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 53649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 537dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 53849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 539fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 540e6098b620531e77b732accbcc21007abd5df927eDan Gohman const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { 541e6098b620531e77b732accbcc21007abd5df927eDan Gohman // Cast away the const qualifiers here. This is ok since 542e6098b620531e77b732accbcc21007abd5df927eDan Gohman // const is re-introduced on the return type. 543e6098b620531e77b732accbcc21007abd5df927eDan Gohman return findNearestCommonDominator(const_cast<NodeT *>(A), 544e6098b620531e77b732accbcc21007abd5df927eDan Gohman const_cast<NodeT *>(B)); 545e6098b620531e77b732accbcc21007abd5df927eDan Gohman } 546e6098b620531e77b732accbcc21007abd5df927eDan Gohman 547420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner //===--------------------------------------------------------------------===// 548420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner // API to update (Post)DominatorTree information based on modifications to 5490c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner // the CFG... 5500c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner 55183beaee227dad622a7e378897c6f29b511388fa0Devang Patel /// addNewBlock - Add a new node to the dominator tree information. This 55267d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman /// creates a new node as a child of DomBB dominator node,linking it into 55383beaee227dad622a7e378897c6f29b511388fa0Devang Patel /// the children list of the immediate dominator. 55449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 555dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 55649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 557934487a9cc05c8c1696b09073a9ff6ecee8ef905Chris Lattner assert(IDomNode && "Not immediate dominator specified for block!"); 5589a51157db555395f7a6ad89faec40b3afa121091Devang Patel DFSInfoValid = false; 559ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return (DomTreeNodes[BB] = IDomNode->addChild( 560ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get(); 5610c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner } 5620c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner 5633a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// changeImmediateDominator - This method is used to update the dominator 5643a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// tree information when a node's immediate dominator changes. 5653a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// 56649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, 56749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NewIDom) { 568d49b12041419709a0690667ce1e2b5e9b9a11610Chris Lattner assert(N && NewIDom && "Cannot change null node pointers!"); 5699a51157db555395f7a6ad89faec40b3afa121091Devang Patel DFSInfoValid = false; 570d49b12041419709a0690667ce1e2b5e9b9a11610Chris Lattner N->setIDom(NewIDom); 5713a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner } 5723a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner 57349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 57426a6908768a0139fff72bc07908d55872cba136bDevang Patel changeImmediateDominator(getNode(BB), getNode(NewBB)); 57526a6908768a0139fff72bc07908d55872cba136bDevang Patel } 57626a6908768a0139fff72bc07908d55872cba136bDevang Patel 57767d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman /// eraseNode - Removes a node from the dominator tree. Block must not 578e2d50046fd29cb3eb2483e080cb7c39b460fbb19Gabor Greif /// dominate any other blocks. Removes node from its immediate dominator's 579441c5ee6cfd4fdec78d7d86536610b2e72519450Devang Patel /// children list. Deletes dominator node associated with basic block BB. 58049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void eraseNode(NodeT *BB) { 58149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *Node = getNode(BB); 58292d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(Node && "Removing node that isn't in dominator tree."); 58392d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(Node->getChildren().empty() && "Node is not a leaf node."); 58449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 585ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Remove node from immediate dominator's children list. 58649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 58749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (IDom) { 588ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I = 589ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::find(IDom->Children.begin(), IDom->Children.end(), Node); 59049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson assert(I != IDom->Children.end() && 59149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson "Not in immediate dominator children set!"); 59249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // I am no longer your child... 59349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDom->Children.erase(I); 59449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 59549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 59649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodes.erase(BB); 597f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky } 5980aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 5997b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson /// splitBlock - BB is split and now it has one successor. Update dominator 6007b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson /// tree to reflect this change. 601ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void splitBlock(NodeT *NewBB) { 6027b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (this->IsPostDominators) 603ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines this->Split<Inverse<NodeT *>, GraphTraits<Inverse<NodeT *>>>(*this, 604ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines NewBB); 6057b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson else 606ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines this->Split<NodeT *, GraphTraits<NodeT *>>(*this, NewBB); 6077b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 608f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky 6090c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// print - Convert to human readable form 610dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 611791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner void print(raw_ostream &o) const { 61249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "=============================--------------------------------\n"; 613e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman if (this->isPostDominator()) 614e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman o << "Inorder PostDominator Tree: "; 615e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman else 616e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman o << "Inorder Dominator Tree: "; 6173a723ab344d9835506ed2b52a2ccd75078670fc7Tobias Grosser if (!this->DFSInfoValid) 61849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 61949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "\n"; 62049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 62145336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner // The postdom tree can have a null root if there are no returns. 62245336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner if (getRootNode()) 62345336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner PrintDomTree<NodeT>(getRootNode(), o, 1); 62449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 6250aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 6263e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattnerprotected: 627ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class GraphT> 628ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines friend typename GraphT::NodeType * 629ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Eval(DominatorTreeBase<typename GraphT::NodeType> &DT, 630ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename GraphT::NodeType *V, unsigned LastLinked); 631280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson 632ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class GraphT> 633ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType> &DT, 634ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename GraphT::NodeType *V, unsigned N); 6350aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 636ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class FuncT, class N> 637ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines friend void 638ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT, FuncT &F); 6390aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 6403e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattner /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 6413e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattner /// dominator tree in dfs order. 64236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void updateDFSNumbers() const { 64349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson unsigned DFSNum = 0; 64449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 645ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, 646ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename DomTreeNodeBase<NodeT>::const_iterator>, 647ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 32> WorkStack; 64849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 64936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); 650ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 651ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser if (!ThisRoot) 652ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser return; 653ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 654ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // Even in the case of multiple exits that form the post dominator root 655ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // nodes, do not iterate over all exits, but start from the virtual root 656ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // node. Otherwise bbs, that are not post dominated by any exit but by the 657ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // virtual root node, will never be assigned a DFS number. 658ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); 659ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser ThisRoot->DFSNumIn = DFSNum++; 660ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 661ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser while (!WorkStack.empty()) { 66236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 66336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typename DomTreeNodeBase<NodeT>::const_iterator ChildIt = 664ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines WorkStack.back().second; 665ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 666ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // If we visited all of the children of this node, "recurse" back up the 667ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // stack setting the DFOutNum. 668ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser if (ChildIt == Node->end()) { 669ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser Node->DFSNumOut = DFSNum++; 670ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.pop_back(); 671ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser } else { 672ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // Otherwise, recursively visit this child. 67336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *Child = *ChildIt; 674ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser ++WorkStack.back().second; 675ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 676ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.push_back(std::make_pair(Child, Child->begin())); 677ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser Child->DFSNumIn = DFSNum++; 67849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 67949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 6800aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 68149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson SlowQueries = 0; 68249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DFSInfoValid = true; 68349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 6840aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 68549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { 68634b5f0437b9bf67bcbeb166a1c092dbbe3786157Benjamin Kramer if (DomTreeNodeBase<NodeT> *Node = getNode(BB)) 68734b5f0437b9bf67bcbeb166a1c092dbbe3786157Benjamin Kramer return Node; 68849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 68949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Haven't calculated this node yet? Get or calculate the node for the 69049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // immediate dominator. 69149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeT *IDom = getIDom(BB); 6921f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 693dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(IDom || this->DomTreeNodes[nullptr]); 69449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); 69549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 69636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Add a new tree node for this NodeT, and link it as a child of 69749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // IDomNode 698ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return (this->DomTreeNodes[BB] = IDomNode->addChild( 699ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get(); 70049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 7010aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 702ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); } 7030aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 704ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void addRoot(NodeT *BB) { this->Roots.push_back(BB); } 7050aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 70678daec973e81b1e85c2c3f5882845317da432f21Owen Andersonpublic: 70778daec973e81b1e85c2c3f5882845317da432f21Owen Anderson /// recalculate - compute a dominator tree for the given function 708ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class FT> void recalculate(FT &F) { 709ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef GraphTraits<FT *> TraitsTy; 710365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser reset(); 711dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->Vertex.push_back(nullptr); 7120aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 713365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser if (!this->IsPostDominators) { 714365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser // Initialize root 715e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks NodeT *entry = TraitsTy::getEntryNode(&F); 716e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks this->Roots.push_back(entry); 717dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->IDoms[entry] = nullptr; 718dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->DomTreeNodes[entry] = nullptr; 7190aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 720ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Calculate<FT, NodeT *>(*this, F); 72178daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } else { 72278daec973e81b1e85c2c3f5882845317da432f21Owen Anderson // Initialize the roots list 723e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), 724ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines E = TraitsTy::nodes_end(&F); 725ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I != E; ++I) { 726aa4e2aea9e8ce01f31a917639bcc7d810b9fe6d1Jakub Staszak if (TraitsTy::child_begin(I) == TraitsTy::child_end(I)) 7275d32ec4cb002973cb12bc21a3fe12364794168c8Owen Anderson addRoot(I); 72878daec973e81b1e85c2c3f5882845317da432f21Owen Anderson 729ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Prepopulate maps so that we don't get iterator invalidation issues 730ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // later. 731dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->IDoms[I] = nullptr; 732dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->DomTreeNodes[I] = nullptr; 73378daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 73478daec973e81b1e85c2c3f5882845317da432f21Owen Anderson 735ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Calculate<FT, Inverse<NodeT *>>(*this, F); 73678daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 73778daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 7380cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner}; 7390cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 7405004e9849aff165bcbd953f891b402ad23bdd1acRafael Espindola// These two functions are declared out of line as a workaround for building 7416226c49bdec886a7162e24e152af579df203e163Rafael Espindola// with old (< r147295) versions of clang because of pr11642. 742ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> 74336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const { 7446226c49bdec886a7162e24e152af579df203e163Rafael Espindola if (A == B) 7456226c49bdec886a7162e24e152af579df203e163Rafael Espindola return true; 7466226c49bdec886a7162e24e152af579df203e163Rafael Espindola 7476226c49bdec886a7162e24e152af579df203e163Rafael Espindola // Cast away the const qualifiers here. This is ok since 7486226c49bdec886a7162e24e152af579df203e163Rafael Espindola // this function doesn't actually return the values returned 7496226c49bdec886a7162e24e152af579df203e163Rafael Espindola // from getNode. 7506226c49bdec886a7162e24e152af579df203e163Rafael Espindola return dominates(getNode(const_cast<NodeT *>(A)), 7516226c49bdec886a7162e24e152af579df203e163Rafael Espindola getNode(const_cast<NodeT *>(B))); 7526226c49bdec886a7162e24e152af579df203e163Rafael Espindola} 753ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> 754ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesbool DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, 755ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const NodeT *B) const { 7566226c49bdec886a7162e24e152af579df203e163Rafael Espindola if (A == B) 7576226c49bdec886a7162e24e152af579df203e163Rafael Espindola return false; 7586226c49bdec886a7162e24e152af579df203e163Rafael Espindola 7596226c49bdec886a7162e24e152af579df203e163Rafael Espindola // Cast away the const qualifiers here. This is ok since 7606226c49bdec886a7162e24e152af579df203e163Rafael Espindola // this function doesn't actually return the values returned 7616226c49bdec886a7162e24e152af579df203e163Rafael Espindola // from getNode. 7626226c49bdec886a7162e24e152af579df203e163Rafael Espindola return dominates(getNode(const_cast<NodeT *>(A)), 7636226c49bdec886a7162e24e152af579df203e163Rafael Espindola getNode(const_cast<NodeT *>(B))); 7646226c49bdec886a7162e24e152af579df203e163Rafael Espindola} 7656226c49bdec886a7162e24e152af579df203e163Rafael Espindola 76636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 767d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 76870b6337d681b1d0a62922ce806fc15c2b8a31e5fChris Lattner#endif 769