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; 2462c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar DFSInfoValid = false; 2472c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar SlowQueries = 0; 24849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 2490aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 2507b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // NewBB is split and now it has one successor. Update dominator tree to 2517b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // reflect this change. 252ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class N, class GraphT> 253ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void Split(DominatorTreeBase<typename GraphT::NodeType> &DT, 254ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename GraphT::NodeType *NewBB) { 25592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(std::distance(GraphT::child_begin(NewBB), 25692d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman GraphT::child_end(NewBB)) == 1 && 25792d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "NewBB should have a single successor!"); 258ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename GraphT::NodeType *NewBBSucc = *GraphT::child_begin(NewBB); 259ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 260ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<typename GraphT::NodeType *> PredBlocks; 261ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef GraphTraits<Inverse<N>> InvTraits; 262ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (typename InvTraits::ChildIteratorType 263ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PI = InvTraits::child_begin(NewBB), 264ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PE = InvTraits::child_end(NewBB); 265ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PI != PE; ++PI) 26667d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman PredBlocks.push_back(*PI); 2677b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 268e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif assert(!PredBlocks.empty() && "No predblocks?"); 269e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman 270e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman bool NewBBDominatesNewBBSucc = true; 271ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (typename InvTraits::ChildIteratorType 272ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PI = InvTraits::child_begin(NewBBSucc), 273ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines E = InvTraits::child_end(NewBBSucc); 274ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PI != E; ++PI) { 2757c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif typename InvTraits::NodeType *ND = *PI; 2767c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && 2777c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif DT.isReachableFromEntry(ND)) { 27815002a2b528e04a5edcfccbec392f5d6b19f7f6aEli Friedman NewBBDominatesNewBBSucc = false; 27915002a2b528e04a5edcfccbec392f5d6b19f7f6aEli Friedman break; 280e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman } 281e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif } 282e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman 2837b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // Find NewBB's immediate dominator and create new dominator tree node for 2847b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // NewBB. 285dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NodeT *NewBBIDom = nullptr; 2867b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson unsigned i = 0; 2877b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson for (i = 0; i < PredBlocks.size(); ++i) 2887b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (DT.isReachableFromEntry(PredBlocks[i])) { 2897b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson NewBBIDom = PredBlocks[i]; 2907b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson break; 2917b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 292a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman 293a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // It's possible that none of the predecessors of NewBB are reachable; 294a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // in that case, NewBB itself is unreachable, so nothing needs to be 295a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // changed. 296a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman if (!NewBBIDom) 297a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman return; 298a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman 2997b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson for (i = i + 1; i < PredBlocks.size(); ++i) { 3007b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (DT.isReachableFromEntry(PredBlocks[i])) 3017b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 3027b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 3037b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 3047b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // Create the new dominator tree node... and set the idom of NewBB. 30508895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); 3067b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 3077b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // If NewBB strictly dominates other blocks, then it is now the immediate 3087b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // dominator of NewBBSucc. Update the dominator tree as appropriate. 3097b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (NewBBDominatesNewBBSucc) { 31008895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc); 3117b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); 3127b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 3137b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 314420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner 3153e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattnerpublic: 316950a4c40b823cd4f09dc71be635229246dfd6cacDan Gohman explicit DominatorTreeBase(bool isPostDom) 317ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {} 318ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 319ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorTreeBase(DominatorTreeBase &&Arg) 320ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : DominatorBase<NodeT>( 321ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::move(static_cast<DominatorBase<NodeT> &>(Arg))), 322ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodes(std::move(Arg.DomTreeNodes)), 323ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RootNode(std::move(Arg.RootNode)), 324ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DFSInfoValid(std::move(Arg.DFSInfoValid)), 325ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SlowQueries(std::move(Arg.SlowQueries)), IDoms(std::move(Arg.IDoms)), 326ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Vertex(std::move(Arg.Vertex)), Info(std::move(Arg.Info)) { 327ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Arg.wipe(); 328ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 329ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { 330ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DominatorBase<NodeT>::operator=( 331ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::move(static_cast<DominatorBase<NodeT> &>(RHS))); 332ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodes = std::move(RHS.DomTreeNodes); 333ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RootNode = std::move(RHS.RootNode); 334ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DFSInfoValid = std::move(RHS.DFSInfoValid); 335ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SlowQueries = std::move(RHS.SlowQueries); 336ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IDoms = std::move(RHS.IDoms); 337ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Vertex = std::move(RHS.Vertex); 338ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Info = std::move(RHS.Info); 339ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RHS.wipe(); 340ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return *this; 341ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 3420cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 343844a3d163bc644085b1d744797da43eb9bf7ee3bDevang Patel /// compare - Return false if the other dominator tree base matches this 3445b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel /// dominator tree base. Otherwise return true. 34536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool compare(const DominatorTreeBase &Other) const { 3465b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 347a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; 348a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (DomTreeNodes.size() != OtherDomTreeNodes.size()) 349a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 350a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 35167d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman for (typename DomTreeNodeMapType::const_iterator 352ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I = this->DomTreeNodes.begin(), 353ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines E = this->DomTreeNodes.end(); 354ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I != E; ++I) { 355a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel NodeT *BB = I->first; 356ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename DomTreeNodeMapType::const_iterator OI = 357ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OtherDomTreeNodes.find(BB); 358a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (OI == OtherDomTreeNodes.end()) 359a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 3605b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 361ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeBase<NodeT> &MyNd = *I->second; 362ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeBase<NodeT> &OtherNd = *OI->second; 3630aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 364ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (MyNd.compare(&OtherNd)) 3655b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel return true; 3665b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel } 367a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 3685b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel return false; 3695b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel } 3705b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 371ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void releaseMemory() { reset(); } 3720cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 3730c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// getNode - return the (Post)DominatorTree node for the specified basic 3740c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// block. This is the same as using operator[] on this class. 3750c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// 376ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const { 377ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto I = DomTreeNodes.find(BB); 378ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I != DomTreeNodes.end()) 379ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return I->second.get(); 380ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return nullptr; 3810cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner } 38297f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner 383ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { return getNode(BB); } 384c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 385dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// getRootNode - This returns the entry node for the CFG of the function. If 386dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// this tree represents the post-dominance relations for a function, however, 387dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// this root may be a node with the block == NULL. This is the case when 388dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// there are multiple exit nodes from a particular function. Consumers of 389dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// post-dominance information must be capable of dealing with this 390dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// possibility. 391dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 39249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } 39349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } 394420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner 39536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Get all nodes dominated by R, including R itself. 3964f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { 39736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Result.clear(); 3984f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang const DomTreeNodeBase<NodeT> *RN = getNode(R); 399dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!RN) 40036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return; // If R is unreachable, it will not be present in the DOM tree. 4014f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; 4024f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang WL.push_back(RN); 4034f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang 4044f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang while (!WL.empty()) { 4054f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); 4064f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang Result.push_back(N->getBlock()); 4074f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang WL.append(N->begin(), N->end()); 4084f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang } 4094f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang } 4104f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang 4114fde2f6a280d0697c31d82e4148a4ba36fc8c0f0Jakub Staszak /// properlyDominates - Returns true iff A dominates B and A != B. 4129a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// Note that this is not a constant time operation! 4139a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// 41449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson bool properlyDominates(const DomTreeNodeBase<NodeT> *A, 41536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *B) const { 416dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!A || !B) 41742c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return false; 41842c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola if (A == B) 41942c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return false; 42042c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return dominates(A, B); 4219a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 4229a51157db555395f7a6ad89faec40b3afa121091Devang Patel 42336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool properlyDominates(const NodeT *A, const NodeT *B) const; 424f11cc5c298b5c2bae45159ebd305e75dd0d5091bDevang Patel 425dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel /// isReachableFromEntry - Return true if A is dominated by the entry 426dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel /// block of the function containing it. 427ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool isReachableFromEntry(const NodeT *A) const { 42892d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(!this->isPostDominator() && 42992d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "This is not implemented for post dominators"); 430092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); 431092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola } 432092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola 433ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; } 4340aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 43594c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru /// dominates - Returns true iff A dominates B. Note that this is not a 4369a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// constant time operation! 4379a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// 438ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool dominates(const DomTreeNodeBase<NodeT> *A, 439ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const DomTreeNodeBase<NodeT> *B) const { 440092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // A node trivially dominates itself. 44167d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman if (B == A) 442092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return true; 443259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 444092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // An unreachable node is dominated by anything. 445092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(B)) 446092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return true; 447092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola 448092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // And dominates nothing. 449092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(A)) 450259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel return false; 4519a51157db555395f7a6ad89faec40b3afa121091Devang Patel 452fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser // Compare the result of the tree walk and the dfs numbers, if expensive 453fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser // checks are enabled. 454fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser#ifdef XDEBUG 45592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert((!DFSInfoValid || 45692d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && 45792d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "Tree walk disagrees with dfs numbers!"); 458fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser#endif 459fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser 4609a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (DFSInfoValid) 4613726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel return B->DominatedBy(A); 4629a51157db555395f7a6ad89faec40b3afa121091Devang Patel 4639a51157db555395f7a6ad89faec40b3afa121091Devang Patel // If we end up with too many slow queries, just update the 4649a51157db555395f7a6ad89faec40b3afa121091Devang Patel // DFS numbers on the theory that we are going to keep querying. 4659a51157db555395f7a6ad89faec40b3afa121091Devang Patel SlowQueries++; 4669a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (SlowQueries > 32) { 4679a51157db555395f7a6ad89faec40b3afa121091Devang Patel updateDFSNumbers(); 4683726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel return B->DominatedBy(A); 4699a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 4704d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel 4719a51157db555395f7a6ad89faec40b3afa121091Devang Patel return dominatedBySlowTreeWalk(A, B); 4729a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 473259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 47436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool dominates(const NodeT *A, const NodeT *B) const; 4750aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 47678daec973e81b1e85c2c3f5882845317da432f21Owen Anderson NodeT *getRoot() const { 47778daec973e81b1e85c2c3f5882845317da432f21Owen Anderson assert(this->Roots.size() == 1 && "Should always have entry node!"); 47878daec973e81b1e85c2c3f5882845317da432f21Owen Anderson return this->Roots[0]; 47978daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 480259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 481fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel /// findNearestCommonDominator - Find nearest common dominator basic block 482fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel /// for basic block A and B. If there is no such block then return NULL. 48349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { 48492d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(A->getParent() == B->getParent() && 48592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "Two blocks are not in same function"); 48649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 48766617633e7dcc14d8808d3118766916b2240722aDan Gohman // If either A or B is a entry block then it is nearest common dominator 48866617633e7dcc14d8808d3118766916b2240722aDan Gohman // (for forward-dominators). 48966617633e7dcc14d8808d3118766916b2240722aDan Gohman if (!this->isPostDominator()) { 49092d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman NodeT &Entry = A->getParent()->front(); 49166617633e7dcc14d8808d3118766916b2240722aDan Gohman if (A == &Entry || B == &Entry) 49266617633e7dcc14d8808d3118766916b2240722aDan Gohman return &Entry; 49366617633e7dcc14d8808d3118766916b2240722aDan Gohman } 49449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 49549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // If B dominates A then B is nearest common dominator. 49649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (dominates(B, A)) 49749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return B; 49849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 49949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // If A dominates B then A is nearest common dominator. 50049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (dominates(A, B)) 50149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return A; 50249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 50349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NodeA = getNode(A); 50449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NodeB = getNode(B); 50549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 506dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If we have DFS info, then we can avoid all allocations by just querying 507dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // it from each IDom. Note that because we call 'dominates' twice above, we 508dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // expect to call through this code at most 16 times in a row without 509dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // building valid DFS information. This is important as below is a *very* 510dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // slow tree walk. 511dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (DFSInfoValid) { 512dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 513dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (IDomA) { 514dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (NodeB->DominatedBy(IDomA)) 515dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return IDomA->getBlock(); 516dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IDomA = IDomA->getIDom(); 517dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 518dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 519dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 520dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 52149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Collect NodeA dominators set. 522ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallPtrSet<DomTreeNodeBase<NodeT> *, 16> NodeADoms; 52349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeADoms.insert(NodeA); 52449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 52549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson while (IDomA) { 52649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeADoms.insert(IDomA); 52749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDomA = IDomA->getIDom(); 52849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 52949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 53049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Walk NodeB immediate dominators chain and find common dominator node. 53149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom(); 53292d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman while (IDomB) { 53349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (NodeADoms.count(IDomB) != 0) 53449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return IDomB->getBlock(); 53549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 53649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDomB = IDomB->getIDom(); 53749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 53849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 539dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 54049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 541fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 542e6098b620531e77b732accbcc21007abd5df927eDan Gohman const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { 543e6098b620531e77b732accbcc21007abd5df927eDan Gohman // Cast away the const qualifiers here. This is ok since 544e6098b620531e77b732accbcc21007abd5df927eDan Gohman // const is re-introduced on the return type. 545e6098b620531e77b732accbcc21007abd5df927eDan Gohman return findNearestCommonDominator(const_cast<NodeT *>(A), 546e6098b620531e77b732accbcc21007abd5df927eDan Gohman const_cast<NodeT *>(B)); 547e6098b620531e77b732accbcc21007abd5df927eDan Gohman } 548e6098b620531e77b732accbcc21007abd5df927eDan Gohman 549420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner //===--------------------------------------------------------------------===// 550420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner // API to update (Post)DominatorTree information based on modifications to 5510c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner // the CFG... 5520c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner 55383beaee227dad622a7e378897c6f29b511388fa0Devang Patel /// addNewBlock - Add a new node to the dominator tree information. This 55467d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman /// creates a new node as a child of DomBB dominator node,linking it into 55583beaee227dad622a7e378897c6f29b511388fa0Devang Patel /// the children list of the immediate dominator. 55649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 557dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 55849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 559934487a9cc05c8c1696b09073a9ff6ecee8ef905Chris Lattner assert(IDomNode && "Not immediate dominator specified for block!"); 5609a51157db555395f7a6ad89faec40b3afa121091Devang Patel DFSInfoValid = false; 561ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return (DomTreeNodes[BB] = IDomNode->addChild( 562ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get(); 5630c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner } 5640c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner 5653a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// changeImmediateDominator - This method is used to update the dominator 5663a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// tree information when a node's immediate dominator changes. 5673a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// 56849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, 56949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NewIDom) { 570d49b12041419709a0690667ce1e2b5e9b9a11610Chris Lattner assert(N && NewIDom && "Cannot change null node pointers!"); 5719a51157db555395f7a6ad89faec40b3afa121091Devang Patel DFSInfoValid = false; 572d49b12041419709a0690667ce1e2b5e9b9a11610Chris Lattner N->setIDom(NewIDom); 5733a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner } 5743a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner 57549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 57626a6908768a0139fff72bc07908d55872cba136bDevang Patel changeImmediateDominator(getNode(BB), getNode(NewBB)); 57726a6908768a0139fff72bc07908d55872cba136bDevang Patel } 57826a6908768a0139fff72bc07908d55872cba136bDevang Patel 57967d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman /// eraseNode - Removes a node from the dominator tree. Block must not 580e2d50046fd29cb3eb2483e080cb7c39b460fbb19Gabor Greif /// dominate any other blocks. Removes node from its immediate dominator's 581441c5ee6cfd4fdec78d7d86536610b2e72519450Devang Patel /// children list. Deletes dominator node associated with basic block BB. 58249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void eraseNode(NodeT *BB) { 58349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *Node = getNode(BB); 58492d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(Node && "Removing node that isn't in dominator tree."); 58592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(Node->getChildren().empty() && "Node is not a leaf node."); 58649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 587ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Remove node from immediate dominator's children list. 58849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 58949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (IDom) { 590ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I = 591ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::find(IDom->Children.begin(), IDom->Children.end(), Node); 59249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson assert(I != IDom->Children.end() && 59349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson "Not in immediate dominator children set!"); 59449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // I am no longer your child... 59549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDom->Children.erase(I); 59649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 59749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 59849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodes.erase(BB); 599f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky } 6000aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 6017b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson /// splitBlock - BB is split and now it has one successor. Update dominator 6027b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson /// tree to reflect this change. 603ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void splitBlock(NodeT *NewBB) { 6047b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (this->IsPostDominators) 605ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines this->Split<Inverse<NodeT *>, GraphTraits<Inverse<NodeT *>>>(*this, 606ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines NewBB); 6077b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson else 608ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines this->Split<NodeT *, GraphTraits<NodeT *>>(*this, NewBB); 6097b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 610f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky 6110c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// print - Convert to human readable form 612dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 613791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner void print(raw_ostream &o) const { 61449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "=============================--------------------------------\n"; 615e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman if (this->isPostDominator()) 616e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman o << "Inorder PostDominator Tree: "; 617e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman else 618e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman o << "Inorder Dominator Tree: "; 6193a723ab344d9835506ed2b52a2ccd75078670fc7Tobias Grosser if (!this->DFSInfoValid) 62049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 62149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "\n"; 62249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 62345336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner // The postdom tree can have a null root if there are no returns. 62445336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner if (getRootNode()) 62545336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner PrintDomTree<NodeT>(getRootNode(), o, 1); 62649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 6270aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 6283e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattnerprotected: 629ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class GraphT> 630ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines friend typename GraphT::NodeType * 631ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Eval(DominatorTreeBase<typename GraphT::NodeType> &DT, 632ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename GraphT::NodeType *V, unsigned LastLinked); 633280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson 634ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class GraphT> 635ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType> &DT, 636ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename GraphT::NodeType *V, unsigned N); 6370aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 638ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class FuncT, class N> 639ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines friend void 640ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT, FuncT &F); 6410aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 6422c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 6432c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { 6442c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar if (DomTreeNodeBase<NodeT> *Node = getNode(BB)) 6452c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar return Node; 6462c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 6472c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar // Haven't calculated this node yet? Get or calculate the node for the 6482c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar // immediate dominator. 6492c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar NodeT *IDom = getIDom(BB); 6502c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 6512c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar assert(IDom || this->DomTreeNodes[nullptr]); 6522c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); 6532c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 6542c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar // Add a new tree node for this NodeT, and link it as a child of 6552c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar // IDomNode 6562c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar return (this->DomTreeNodes[BB] = IDomNode->addChild( 6572c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get(); 6582c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar } 6592c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 6602c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); } 6612c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 6622c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar void addRoot(NodeT *BB) { this->Roots.push_back(BB); } 6632c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 6642c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainarpublic: 6653e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattner /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 6663e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattner /// dominator tree in dfs order. 66736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void updateDFSNumbers() const { 6682c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 6692c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar if (DFSInfoValid) { 6702c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar SlowQueries = 0; 6712c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar return; 6722c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar } 6732c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar 67449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson unsigned DFSNum = 0; 67549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 676ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, 677ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typename DomTreeNodeBase<NodeT>::const_iterator>, 678ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 32> WorkStack; 67949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 68036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); 681ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 682ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser if (!ThisRoot) 683ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser return; 684ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 685ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // Even in the case of multiple exits that form the post dominator root 686ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // nodes, do not iterate over all exits, but start from the virtual root 687ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // node. Otherwise bbs, that are not post dominated by any exit but by the 688ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // virtual root node, will never be assigned a DFS number. 689ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); 690ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser ThisRoot->DFSNumIn = DFSNum++; 691ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 692ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser while (!WorkStack.empty()) { 69336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 69436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typename DomTreeNodeBase<NodeT>::const_iterator ChildIt = 695ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines WorkStack.back().second; 696ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 697ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // If we visited all of the children of this node, "recurse" back up the 698ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // stack setting the DFOutNum. 699ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser if (ChildIt == Node->end()) { 700ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser Node->DFSNumOut = DFSNum++; 701ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.pop_back(); 702ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser } else { 703ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // Otherwise, recursively visit this child. 70436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *Child = *ChildIt; 705ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser ++WorkStack.back().second; 706ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 707ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.push_back(std::make_pair(Child, Child->begin())); 708ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser Child->DFSNumIn = DFSNum++; 70949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 71049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 7110aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 71249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson SlowQueries = 0; 71349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DFSInfoValid = true; 71449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 7150aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 71678daec973e81b1e85c2c3f5882845317da432f21Owen Anderson /// recalculate - compute a dominator tree for the given function 717ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <class FT> void recalculate(FT &F) { 718ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef GraphTraits<FT *> TraitsTy; 719365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser reset(); 720dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->Vertex.push_back(nullptr); 7210aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 722365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser if (!this->IsPostDominators) { 723365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser // Initialize root 724e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks NodeT *entry = TraitsTy::getEntryNode(&F); 725e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks this->Roots.push_back(entry); 726dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->IDoms[entry] = nullptr; 727dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->DomTreeNodes[entry] = nullptr; 7280aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 729ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Calculate<FT, NodeT *>(*this, F); 73078daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } else { 73178daec973e81b1e85c2c3f5882845317da432f21Owen Anderson // Initialize the roots list 732e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), 733ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines E = TraitsTy::nodes_end(&F); 734ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I != E; ++I) { 735aa4e2aea9e8ce01f31a917639bcc7d810b9fe6d1Jakub Staszak if (TraitsTy::child_begin(I) == TraitsTy::child_end(I)) 7365d32ec4cb002973cb12bc21a3fe12364794168c8Owen Anderson addRoot(I); 73778daec973e81b1e85c2c3f5882845317da432f21Owen Anderson 738ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Prepopulate maps so that we don't get iterator invalidation issues 739ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // later. 740dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->IDoms[I] = nullptr; 741dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines this->DomTreeNodes[I] = nullptr; 74278daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 74378daec973e81b1e85c2c3f5882845317da432f21Owen Anderson 744ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Calculate<FT, Inverse<NodeT *>>(*this, F); 74578daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 74678daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 7470cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner}; 7480cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 7495004e9849aff165bcbd953f891b402ad23bdd1acRafael Espindola// These two functions are declared out of line as a workaround for building 7506226c49bdec886a7162e24e152af579df203e163Rafael Espindola// with old (< r147295) versions of clang because of pr11642. 751ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> 75236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const { 7536226c49bdec886a7162e24e152af579df203e163Rafael Espindola if (A == B) 7546226c49bdec886a7162e24e152af579df203e163Rafael Espindola return true; 7556226c49bdec886a7162e24e152af579df203e163Rafael Espindola 7566226c49bdec886a7162e24e152af579df203e163Rafael Espindola // Cast away the const qualifiers here. This is ok since 7576226c49bdec886a7162e24e152af579df203e163Rafael Espindola // this function doesn't actually return the values returned 7586226c49bdec886a7162e24e152af579df203e163Rafael Espindola // from getNode. 7596226c49bdec886a7162e24e152af579df203e163Rafael Espindola return dominates(getNode(const_cast<NodeT *>(A)), 7606226c49bdec886a7162e24e152af579df203e163Rafael Espindola getNode(const_cast<NodeT *>(B))); 7616226c49bdec886a7162e24e152af579df203e163Rafael Espindola} 762ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class NodeT> 763ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesbool DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, 764ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const NodeT *B) const { 7656226c49bdec886a7162e24e152af579df203e163Rafael Espindola if (A == B) 7666226c49bdec886a7162e24e152af579df203e163Rafael Espindola return false; 7676226c49bdec886a7162e24e152af579df203e163Rafael Espindola 7686226c49bdec886a7162e24e152af579df203e163Rafael Espindola // Cast away the const qualifiers here. This is ok since 7696226c49bdec886a7162e24e152af579df203e163Rafael Espindola // this function doesn't actually return the values returned 7706226c49bdec886a7162e24e152af579df203e163Rafael Espindola // from getNode. 7716226c49bdec886a7162e24e152af579df203e163Rafael Espindola return dominates(getNode(const_cast<NodeT *>(A)), 7726226c49bdec886a7162e24e152af579df203e163Rafael Espindola getNode(const_cast<NodeT *>(B))); 7736226c49bdec886a7162e24e152af579df203e163Rafael Espindola} 7746226c49bdec886a7162e24e152af579df203e163Rafael Espindola 77536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 776d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 77770b6337d681b1d0a62922ce806fc15c2b8a31e5fChris Lattner#endif 778