GenericDomTree.h revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
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 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef LLVM_SUPPORT_GENERIC_DOM_TREE_H 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#define LLVM_SUPPORT_GENERIC_DOM_TREE_H 2070b6337d681b1d0a62922ce806fc15c2b8a31e5fChris Lattner 2149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/ADT/DenseMap.h" 22f0d24f1f597a84b1a164019ab81831ccd7aea47fChris Lattner#include "llvm/ADT/DepthFirstIterator.h" 2378daec973e81b1e85c2c3f5882845317da432f21Owen Anderson#include "llvm/ADT/GraphTraits.h" 2449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 2549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/ADT/SmallVector.h" 2649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/Support/Compiler.h" 27791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner#include "llvm/Support/raw_ostream.h" 281aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson#include <algorithm> 297a73b80b9052136c8cd2234eb3433a07df7cf38eJohn Criswell 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3270b6337d681b1d0a62922ce806fc15c2b8a31e5fChris Lattner//===----------------------------------------------------------------------===// 33dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman/// DominatorBase - Base class that other, more interesting dominator analyses 34dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman/// inherit from. 35dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman/// 3649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Andersontemplate <class NodeT> 377feb3be0b76c72134c515995b1a37466171cf83bOwen Andersonclass DominatorBase { 38c348d21bf6160c1f1d1511cc432bc8a7ede66244Chris Lattnerprotected: 3949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson std::vector<NodeT*> Roots; 40facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner const bool IsPostDominators; 41950a4c40b823cd4f09dc71be635229246dfd6cacDan Gohman inline explicit DominatorBase(bool isPostDom) : 427feb3be0b76c72134c515995b1a37466171cf83bOwen Anderson Roots(), IsPostDominators(isPostDom) {} 43c348d21bf6160c1f1d1511cc432bc8a7ede66244Chris Lattnerpublic: 44794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 4567d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman /// getRoots - Return the root blocks of the current CFG. This may include 46dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// multiple blocks if we are computing post dominators. For forward 47dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// dominators, this will always be a single block (the entry node). 48dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 4949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson inline const std::vector<NodeT*> &getRoots() const { return Roots; } 50facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 51dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// isPostDominator - Returns true if analysis based of postdoms 52dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 53facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner bool isPostDominator() const { return IsPostDominators; } 54c348d21bf6160c1f1d1511cc432bc8a7ede66244Chris Lattner}; 55c348d21bf6160c1f1d1511cc432bc8a7ede66244Chris Lattner 5626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel 5726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel//===----------------------------------------------------------------------===// 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// DomTreeNodeBase - Dominator Tree Node 5949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Andersontemplate<class NodeT> class DominatorTreeBase; 60efd4a5144b03f61ebfd53d0245176f95e1170fb8Hartmut Kaiserstruct PostDominatorTree; 611aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson 621aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Andersontemplate <class NodeT> 631aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Andersonclass DomTreeNodeBase { 641aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson NodeT *TheBB; 651aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson DomTreeNodeBase<NodeT> *IDom; 661aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson std::vector<DomTreeNodeBase<NodeT> *> Children; 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines mutable int DFSNumIn, DFSNumOut; 683726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 6949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson template<class N> friend class DominatorTreeBase; 70efd4a5144b03f61ebfd53d0245176f95e1170fb8Hartmut Kaiser friend struct PostDominatorTree; 7126042420d642e810f5cdfb2da6156b74aaf80945Devang Patelpublic: 721aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator; 731aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator 741aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson const_iterator; 750aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 7626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel iterator begin() { return Children.begin(); } 7726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel iterator end() { return Children.end(); } 7826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const_iterator begin() const { return Children.begin(); } 7926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const_iterator end() const { return Children.end(); } 800aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 811aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson NodeT *getBlock() const { return TheBB; } 821aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson DomTreeNodeBase<NodeT> *getIDom() const { return IDom; } 831aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const { 841aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson return Children; 851aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson } 86a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 871aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom) 884d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } 890aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 901aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) { 911aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson Children.push_back(C); 921aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson return C; 931aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson } 945b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 95e5ffa900f8cf486fae4f542d72d84e6bab0129aeOwen Anderson size_t getNumChildren() const { 96e5ffa900f8cf486fae4f542d72d84e6bab0129aeOwen Anderson return Children.size(); 97e5ffa900f8cf486fae4f542d72d84e6bab0129aeOwen Anderson } 98a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 99a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel void clearAllChildren() { 100a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel Children.clear(); 101a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel } 1020aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 103fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak bool compare(const DomTreeNodeBase<NodeT> *Other) const { 104a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (getNumChildren() != Other->getNumChildren()) 105a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 106a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 107fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak SmallPtrSet<const NodeT *, 4> OtherChildren; 108fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) { 109fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak const NodeT *Nd = (*I)->getBlock(); 110a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel OtherChildren.insert(Nd); 111a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel } 112a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 113fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak for (const_iterator I = begin(), E = end(); I != E; ++I) { 114fe0c244633aff93111063224317ec9c20d3dbcf4Jakub Staszak const NodeT *N = (*I)->getBlock(); 115a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (OtherChildren.count(N) == 0) 116a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 117a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel } 118a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return false; 119a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel } 120a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 1211aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson void setIDom(DomTreeNodeBase<NodeT> *NewIDom) { 1221aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson assert(IDom && "No immediate dominator?"); 1231aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson if (IDom != NewIDom) { 12408895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I = 1251aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson std::find(IDom->Children.begin(), IDom->Children.end(), this); 1261aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson assert(I != IDom->Children.end() && 1271aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson "Not in immediate dominator children set!"); 1281aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson // I am no longer your child... 1291aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson IDom->Children.erase(I); 1301aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson 1311aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson // Switch to new dominator 1321aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson IDom = NewIDom; 1331aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson IDom->Children.push_back(this); 1341aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson } 1351aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson } 1360aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 137c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do 138c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner /// not call them. 139c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner unsigned getDFSNumIn() const { return DFSNumIn; } 140c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner unsigned getDFSNumOut() const { return DFSNumOut; } 1419c7ee6b19fab7a269994264bc19bf4d19c33b3c3Devang Patelprivate: 142c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner // Return true if this node is dominated by other. Use this only if DFS info 143c385ae6ff5d6a978f7a1317e0069853a0e5dca2bChris Lattner // is valid. 1441aad74c9e8aba2ad0493620d35966ee3964c1ecbOwen Anderson bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const { 1453726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel return this->DFSNumIn >= other->DFSNumIn && 1463726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel this->DFSNumOut <= other->DFSNumOut; 1473726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 14826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel}; 14926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel 15049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Andersontemplate<class NodeT> 151305b515c2787f47adecbe120e4b4bef55c5e5525Chandler Carruthinline raw_ostream &operator<<(raw_ostream &o, 152791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner const DomTreeNodeBase<NodeT> *Node) { 15349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (Node->getBlock()) 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Node->getBlock()->printAsOperand(o, false); 15549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson else 15649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << " <<exit node>>"; 1570aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 15849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; 1590aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 16049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return o << "\n"; 16149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson} 16249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 16349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Andersontemplate<class NodeT> 164305b515c2787f47adecbe120e4b4bef55c5e5525Chandler Carruthinline void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o, 16549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson unsigned Lev) { 166791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner o.indent(2*Lev) << "[" << Lev << "] " << N; 16749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), 16849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson E = N->end(); I != E; ++I) 16949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson PrintDomTree<NodeT>(*I, o, Lev+1); 17049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson} 17149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 17231b935357d1396d3be32fdf24dcb0319a6908c6fChris Lattner//===----------------------------------------------------------------------===// 1733dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson/// DominatorTree - Calculate the immediate dominator tree for a function. 174dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman/// 17549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 1764d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Andersontemplate<class FuncT, class N> 1774d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Andersonvoid Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT, 1784d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson FuncT& F); 17905d2318fbde7b603bd6de690f18d48e0ef44d81dOwen Anderson 18049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Andersontemplate<class NodeT> 18149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Andersonclass DominatorTreeBase : public DominatorBase<NodeT> { 1821c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 1831c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola const DomTreeNodeBase<NodeT> *B) const { 1841c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola assert(A != B); 1851c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola assert(isReachableFromEntry(B)); 1861c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola assert(isReachableFromEntry(A)); 1871c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola 1881c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola const DomTreeNodeBase<NodeT> *IDom; 1891c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) 1901c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola B = IDom; // Walk up the tree 1911c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola return IDom != 0; 1921c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola } 1931c8cf21d0c96cee0d55b619be58b1b400675e6acRafael Espindola 19431b935357d1396d3be32fdf24dcb0319a6908c6fChris Lattnerprotected: 19549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType; 1969a51157db555395f7a6ad89faec40b3afa121091Devang Patel DomTreeNodeMapType DomTreeNodes; 19749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *RootNode; 1983dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 19936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines mutable bool DFSInfoValid; 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines mutable unsigned int SlowQueries; 20126a6908768a0139fff72bc07908d55872cba136bDevang Patel // Information record used during immediate dominators computation. 202e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson struct InfoRec { 2031f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson unsigned DFSNum; 20454cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich unsigned Parent; 20526d5d16a2c8ef6c0763afbfe06c940c40c461d6eNate Begeman unsigned Semi; 20611e222da1fe498a3c528d197ab57982e3bb5762dCameron Zwarich NodeT *Label; 2073dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 20854cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {} 20926d5d16a2c8ef6c0763afbfe06c940c40c461d6eNate Begeman }; 2103dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 21149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DenseMap<NodeT*, NodeT*> IDoms; 21226d5d16a2c8ef6c0763afbfe06c940c40c461d6eNate Begeman 21336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Vertex - Map the DFS number to the NodeT* 21449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson std::vector<NodeT*> Vertex; 2153dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 21626d5d16a2c8ef6c0763afbfe06c940c40c461d6eNate Begeman // Info - Collection of information used during the computation of idoms. 21749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DenseMap<NodeT*, InfoRec> Info; 21849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 21949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void reset() { 22067d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), 22149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson E = DomTreeNodes.end(); I != E; ++I) 22249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson delete I->second; 22349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodes.clear(); 22449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDoms.clear(); 22549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson this->Roots.clear(); 22649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson Vertex.clear(); 22749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson RootNode = 0; 22849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 2290aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 2307b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // NewBB is split and now it has one successor. Update dominator tree to 2317b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // reflect this change. 2327b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson template<class N, class GraphT> 2337b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson void Split(DominatorTreeBase<typename GraphT::NodeType>& DT, 2347b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson typename GraphT::NodeType* NewBB) { 23592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(std::distance(GraphT::child_begin(NewBB), 23692d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman GraphT::child_end(NewBB)) == 1 && 23792d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "NewBB should have a single successor!"); 2387b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB); 2397b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 2407b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson std::vector<typename GraphT::NodeType*> PredBlocks; 241e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif typedef GraphTraits<Inverse<N> > InvTraits; 242e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif for (typename InvTraits::ChildIteratorType PI = 243e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif InvTraits::child_begin(NewBB), 244e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif PE = InvTraits::child_end(NewBB); PI != PE; ++PI) 24567d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman PredBlocks.push_back(*PI); 2467b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 247e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif assert(!PredBlocks.empty() && "No predblocks?"); 248e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman 249e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman bool NewBBDominatesNewBBSucc = true; 250e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif for (typename InvTraits::ChildIteratorType PI = 251e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif InvTraits::child_begin(NewBBSucc), 252e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif E = InvTraits::child_end(NewBBSucc); PI != E; ++PI) { 2537c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif typename InvTraits::NodeType *ND = *PI; 2547c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && 2557c71b81a4fccd236e191dbbd6926b35fb4ac9b1eGabor Greif DT.isReachableFromEntry(ND)) { 25615002a2b528e04a5edcfccbec392f5d6b19f7f6aEli Friedman NewBBDominatesNewBBSucc = false; 25715002a2b528e04a5edcfccbec392f5d6b19f7f6aEli Friedman break; 258e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman } 259e07c3c46d0b5adb7d7af876fd3ea3703aebc47c1Gabor Greif } 260e528fca6735158caefe5d6bb58dcbd0c108845c5Eli Friedman 2617b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // Find NewBB's immediate dominator and create new dominator tree node for 2627b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // NewBB. 26308895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson NodeT *NewBBIDom = 0; 2647b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson unsigned i = 0; 2657b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson for (i = 0; i < PredBlocks.size(); ++i) 2667b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (DT.isReachableFromEntry(PredBlocks[i])) { 2677b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson NewBBIDom = PredBlocks[i]; 2687b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson break; 2697b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 270a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman 271a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // It's possible that none of the predecessors of NewBB are reachable; 272a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // in that case, NewBB itself is unreachable, so nothing needs to be 273a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman // changed. 274a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman if (!NewBBIDom) 275a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman return; 276a8ba2c25e9ea7b0d213b485debe5d044efde66a4Eli Friedman 2777b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson for (i = i + 1; i < PredBlocks.size(); ++i) { 2787b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (DT.isReachableFromEntry(PredBlocks[i])) 2797b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 2807b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 2817b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 2827b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // Create the new dominator tree node... and set the idom of NewBB. 28308895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); 2847b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson 2857b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // If NewBB strictly dominates other blocks, then it is now the immediate 2867b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson // dominator of NewBBSucc. Update the dominator tree as appropriate. 2877b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (NewBBDominatesNewBBSucc) { 28808895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc); 2897b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); 2907b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 2917b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 292420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner 2933e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattnerpublic: 294950a4c40b823cd4f09dc71be635229246dfd6cacDan Gohman explicit DominatorTreeBase(bool isPostDom) 2957feb3be0b76c72134c515995b1a37466171cf83bOwen Anderson : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {} 2967feb3be0b76c72134c515995b1a37466171cf83bOwen Anderson virtual ~DominatorTreeBase() { reset(); } 2970cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 298844a3d163bc644085b1d744797da43eb9bf7ee3bDevang Patel /// compare - Return false if the other dominator tree base matches this 2995b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel /// dominator tree base. Otherwise return true. 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool compare(const DominatorTreeBase &Other) const { 3015b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 302a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; 303a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (DomTreeNodes.size() != OtherDomTreeNodes.size()) 304a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 305a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 30667d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman for (typename DomTreeNodeMapType::const_iterator 3075b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel I = this->DomTreeNodes.begin(), 3085b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel E = this->DomTreeNodes.end(); I != E; ++I) { 309a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel NodeT *BB = I->first; 310a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB); 311a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (OI == OtherDomTreeNodes.end()) 312a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel return true; 3135b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 314a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel DomTreeNodeBase<NodeT>* MyNd = I->second; 315a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel DomTreeNodeBase<NodeT>* OtherNd = OI->second; 3160aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 317a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel if (MyNd->compare(OtherNd)) 3185b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel return true; 3195b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel } 320a45a9e416fb24b55c1a0af2369bfda8560edcb50Devang Patel 3215b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel return false; 3225b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel } 3235b57e720c875277131ed0d4f3b72a582979d1afeDevang Patel 3240cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner virtual void releaseMemory() { reset(); } 3250cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 3260c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// getNode - return the (Post)DominatorTree node for the specified basic 3270c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// block. This is the same as using operator[] on this class. 3280c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// 32949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const { 33034b5f0437b9bf67bcbeb166a1c092dbbe3786157Benjamin Kramer return DomTreeNodes.lookup(BB); 3310cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner } 33297f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner 333dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// getRootNode - This returns the entry node for the CFG of the function. If 334dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// this tree represents the post-dominance relations for a function, however, 335dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// this root may be a node with the block == NULL. This is the case when 336dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// there are multiple exit nodes from a particular function. Consumers of 337dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// post-dominance information must be capable of dealing with this 338dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// possibility. 339dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 34049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } 34149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } 342420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner 34336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Get all nodes dominated by R, including R itself. 3444f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { 34536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Result.clear(); 3464f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang const DomTreeNodeBase<NodeT> *RN = getNode(R); 34736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RN == NULL) 34836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return; // If R is unreachable, it will not be present in the DOM tree. 3494f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; 3504f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang WL.push_back(RN); 3514f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang 3524f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang while (!WL.empty()) { 3534f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); 3544f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang Result.push_back(N->getBlock()); 3554f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang WL.append(N->begin(), N->end()); 3564f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang } 3574f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang } 3584f77a21d6ca2d560a7508fd54581b12dfc01630bShuxin Yang 3594fde2f6a280d0697c31d82e4148a4ba36fc8c0f0Jakub Staszak /// properlyDominates - Returns true iff A dominates B and A != B. 3609a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// Note that this is not a constant time operation! 3619a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// 36249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson bool properlyDominates(const DomTreeNodeBase<NodeT> *A, 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *B) const { 36442c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola if (A == 0 || B == 0) 36542c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return false; 36642c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola if (A == B) 36742c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return false; 36842c487d2e529489648176ebb8e9ef022c07ef785Rafael Espindola return dominates(A, B); 3699a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 3709a51157db555395f7a6ad89faec40b3afa121091Devang Patel 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool properlyDominates(const NodeT *A, const NodeT *B) const; 372f11cc5c298b5c2bae45159ebd305e75dd0d5091bDevang Patel 373dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel /// isReachableFromEntry - Return true if A is dominated by the entry 374dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel /// block of the function containing it. 375092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola bool isReachableFromEntry(const NodeT* A) const { 37692d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(!this->isPostDominator() && 37792d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "This is not implemented for post dominators"); 378092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); 379092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola } 380092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola 381092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola inline bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { 382092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return A; 38349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 3840aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 38594c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru /// dominates - Returns true iff A dominates B. Note that this is not a 3869a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// constant time operation! 3879a51157db555395f7a6ad89faec40b3afa121091Devang Patel /// 38849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson inline bool dominates(const DomTreeNodeBase<NodeT> *A, 38936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *B) const { 390092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // A node trivially dominates itself. 39167d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman if (B == A) 392092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return true; 393259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 394092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // An unreachable node is dominated by anything. 395092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(B)) 396092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return true; 397092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola 398092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // And dominates nothing. 399092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(A)) 400259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel return false; 4019a51157db555395f7a6ad89faec40b3afa121091Devang Patel 402fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser // Compare the result of the tree walk and the dfs numbers, if expensive 403fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser // checks are enabled. 404fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser#ifdef XDEBUG 40592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert((!DFSInfoValid || 40692d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && 40792d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "Tree walk disagrees with dfs numbers!"); 408fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser#endif 409fde781b8d6020c78bb2f3a59845dba251e84808dTobias Grosser 4109a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (DFSInfoValid) 4113726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel return B->DominatedBy(A); 4129a51157db555395f7a6ad89faec40b3afa121091Devang Patel 4139a51157db555395f7a6ad89faec40b3afa121091Devang Patel // If we end up with too many slow queries, just update the 4149a51157db555395f7a6ad89faec40b3afa121091Devang Patel // DFS numbers on the theory that we are going to keep querying. 4159a51157db555395f7a6ad89faec40b3afa121091Devang Patel SlowQueries++; 4169a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (SlowQueries > 32) { 4179a51157db555395f7a6ad89faec40b3afa121091Devang Patel updateDFSNumbers(); 4183726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel return B->DominatedBy(A); 4199a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 4204d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel 4219a51157db555395f7a6ad89faec40b3afa121091Devang Patel return dominatedBySlowTreeWalk(A, B); 4229a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 423259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 42436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool dominates(const NodeT *A, const NodeT *B) const; 4250aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 42678daec973e81b1e85c2c3f5882845317da432f21Owen Anderson NodeT *getRoot() const { 42778daec973e81b1e85c2c3f5882845317da432f21Owen Anderson assert(this->Roots.size() == 1 && "Should always have entry node!"); 42878daec973e81b1e85c2c3f5882845317da432f21Owen Anderson return this->Roots[0]; 42978daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 430259e6cf1911a91ed80f77b132d1509fd0581a4a1Devang Patel 431fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel /// findNearestCommonDominator - Find nearest common dominator basic block 432fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel /// for basic block A and B. If there is no such block then return NULL. 43349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { 43492d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(A->getParent() == B->getParent() && 43592d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman "Two blocks are not in same function"); 43649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 43766617633e7dcc14d8808d3118766916b2240722aDan Gohman // If either A or B is a entry block then it is nearest common dominator 43866617633e7dcc14d8808d3118766916b2240722aDan Gohman // (for forward-dominators). 43966617633e7dcc14d8808d3118766916b2240722aDan Gohman if (!this->isPostDominator()) { 44092d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman NodeT &Entry = A->getParent()->front(); 44166617633e7dcc14d8808d3118766916b2240722aDan Gohman if (A == &Entry || B == &Entry) 44266617633e7dcc14d8808d3118766916b2240722aDan Gohman return &Entry; 44366617633e7dcc14d8808d3118766916b2240722aDan Gohman } 44449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 44549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // If B dominates A then B is nearest common dominator. 44649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (dominates(B, A)) 44749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return B; 44849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 44949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // If A dominates B then A is nearest common dominator. 45049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (dominates(A, B)) 45149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return A; 45249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 45349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NodeA = getNode(A); 45449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NodeB = getNode(B); 45549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 45649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Collect NodeA dominators set. 45749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms; 45849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeADoms.insert(NodeA); 45949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 46049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson while (IDomA) { 46149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeADoms.insert(IDomA); 46249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDomA = IDomA->getIDom(); 46349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 46449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 46549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Walk NodeB immediate dominators chain and find common dominator node. 46649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom(); 46792d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman while (IDomB) { 46849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (NodeADoms.count(IDomB) != 0) 46949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return IDomB->getBlock(); 47049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 47149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDomB = IDomB->getIDom(); 47249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 47349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 47449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return NULL; 47549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 476fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 477e6098b620531e77b732accbcc21007abd5df927eDan Gohman const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { 478e6098b620531e77b732accbcc21007abd5df927eDan Gohman // Cast away the const qualifiers here. This is ok since 479e6098b620531e77b732accbcc21007abd5df927eDan Gohman // const is re-introduced on the return type. 480e6098b620531e77b732accbcc21007abd5df927eDan Gohman return findNearestCommonDominator(const_cast<NodeT *>(A), 481e6098b620531e77b732accbcc21007abd5df927eDan Gohman const_cast<NodeT *>(B)); 482e6098b620531e77b732accbcc21007abd5df927eDan Gohman } 483e6098b620531e77b732accbcc21007abd5df927eDan Gohman 484420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner //===--------------------------------------------------------------------===// 485420a8bf2b2276acdb4d7004ae251a2460999c0e4Chris Lattner // API to update (Post)DominatorTree information based on modifications to 4860c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner // the CFG... 4870c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner 48883beaee227dad622a7e378897c6f29b511388fa0Devang Patel /// addNewBlock - Add a new node to the dominator tree information. This 48967d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman /// creates a new node as a child of DomBB dominator node,linking it into 49083beaee227dad622a7e378897c6f29b511388fa0Devang Patel /// the children list of the immediate dominator. 49149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 4920c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner assert(getNode(BB) == 0 && "Block already in dominator tree!"); 49349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 494934487a9cc05c8c1696b09073a9ff6ecee8ef905Chris Lattner assert(IDomNode && "Not immediate dominator specified for block!"); 4959a51157db555395f7a6ad89faec40b3afa121091Devang Patel DFSInfoValid = false; 49667d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman return DomTreeNodes[BB] = 49708895f886655d7d8368d2fdb513dcc963b681a74Owen Anderson IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode)); 4980c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner } 4990c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner 5003a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// changeImmediateDominator - This method is used to update the dominator 5013a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// tree information when a node's immediate dominator changes. 5023a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner /// 50349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, 50449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *NewIDom) { 505d49b12041419709a0690667ce1e2b5e9b9a11610Chris Lattner assert(N && NewIDom && "Cannot change null node pointers!"); 5069a51157db555395f7a6ad89faec40b3afa121091Devang Patel DFSInfoValid = false; 507d49b12041419709a0690667ce1e2b5e9b9a11610Chris Lattner N->setIDom(NewIDom); 5083a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner } 5093a294d6085c69ad7ac1572a2c976624efe66a082Chris Lattner 51049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 51126a6908768a0139fff72bc07908d55872cba136bDevang Patel changeImmediateDominator(getNode(BB), getNode(NewBB)); 51226a6908768a0139fff72bc07908d55872cba136bDevang Patel } 51326a6908768a0139fff72bc07908d55872cba136bDevang Patel 51467d9bf9dc4df036aad330ba5cdb663d8a7c4af11Dan Gohman /// eraseNode - Removes a node from the dominator tree. Block must not 515e2d50046fd29cb3eb2483e080cb7c39b460fbb19Gabor Greif /// dominate any other blocks. Removes node from its immediate dominator's 516441c5ee6cfd4fdec78d7d86536610b2e72519450Devang Patel /// children list. Deletes dominator node associated with basic block BB. 51749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void eraseNode(NodeT *BB) { 51849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *Node = getNode(BB); 51992d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(Node && "Removing node that isn't in dominator tree."); 52092d7b35bd07f590f6767398294cc7587ccb73f24Dan Gohman assert(Node->getChildren().empty() && "Node is not a leaf node."); 52149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 52249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Remove node from immediate dominator's children list. 52349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 52449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson if (IDom) { 52549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I = 52649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson std::find(IDom->Children.begin(), IDom->Children.end(), Node); 52749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson assert(I != IDom->Children.end() && 52849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson "Not in immediate dominator children set!"); 52949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // I am no longer your child... 53049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson IDom->Children.erase(I); 53149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 53249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 53349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodes.erase(BB); 53449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson delete Node; 53549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 536441c5ee6cfd4fdec78d7d86536610b2e72519450Devang Patel 537f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky /// removeNode - Removes a node from the dominator tree. Block must not 538f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky /// dominate any other blocks. Invalidates any node pointing to removed 539f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky /// block. 54049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson void removeNode(NodeT *BB) { 541f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky assert(getNode(BB) && "Removing node that isn't in dominator tree."); 542bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel DomTreeNodes.erase(BB); 543f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky } 5440aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 5457b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson /// splitBlock - BB is split and now it has one successor. Update dominator 5467b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson /// tree to reflect this change. 5477b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson void splitBlock(NodeT* NewBB) { 5487b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson if (this->IsPostDominators) 54978daec973e81b1e85c2c3f5882845317da432f21Owen Anderson this->Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB); 5507b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson else 55178daec973e81b1e85c2c3f5882845317da432f21Owen Anderson this->Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB); 5527b714321df4d286018d594c9c9f132f343dbabdcOwen Anderson } 553f19fb9b4f45acce221ba3c20f37d66ffc1735b54Nick Lewycky 5540c5d27e4a1c7ade2ab8af379f13417359d9d6614Chris Lattner /// print - Convert to human readable form 555dd298c8c6eb036baf35bf5a559c59d2afd2c7944Misha Brukman /// 556791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner void print(raw_ostream &o) const { 55749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "=============================--------------------------------\n"; 558e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman if (this->isPostDominator()) 559e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman o << "Inorder PostDominator Tree: "; 560e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman else 561e8ae2fe2a8cc767f4d7ac55db13bf9adb8e7df70Dan Gohman o << "Inorder Dominator Tree: "; 5623a723ab344d9835506ed2b52a2ccd75078670fc7Tobias Grosser if (!this->DFSInfoValid) 56349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 56449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson o << "\n"; 56549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 56645336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner // The postdom tree can have a null root if there are no returns. 56745336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner if (getRootNode()) 56845336a6f22de93b38d693fbdde0c96aa84f1e70fChris Lattner PrintDomTree<NodeT>(getRootNode(), o, 1); 56949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 5700aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 5713e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattnerprotected: 572280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson template<class GraphT> 573280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson friend typename GraphT::NodeType* Eval( 574280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson DominatorTreeBase<typename GraphT::NodeType>& DT, 57554cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich typename GraphT::NodeType* V, 57654cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich unsigned LastLinked); 577280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson 578280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson template<class GraphT> 579280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, 580280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson typename GraphT::NodeType* V, 581280f8a2ecedc213372402fe221e2b1a613816f7dOwen Anderson unsigned N); 5820aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 5834d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson template<class FuncT, class N> 5844d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT, 5854d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson FuncT& F); 5860aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 5873e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattner /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 5883e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattner /// dominator tree in dfs order. 58936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void updateDFSNumbers() const { 59049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson unsigned DFSNum = 0; 59149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 59236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<std::pair<const DomTreeNodeBase<NodeT>*, 59336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typename DomTreeNodeBase<NodeT>::const_iterator>, 32> WorkStack; 59449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 59536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); 596ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 597ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser if (!ThisRoot) 598ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser return; 599ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 600ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // Even in the case of multiple exits that form the post dominator root 601ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // nodes, do not iterate over all exits, but start from the virtual root 602ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // node. Otherwise bbs, that are not post dominated by any exit but by the 603ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // virtual root node, will never be assigned a DFS number. 604ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); 605ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser ThisRoot->DFSNumIn = DFSNum++; 606ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 607ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser while (!WorkStack.empty()) { 60836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 60936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typename DomTreeNodeBase<NodeT>::const_iterator ChildIt = 610ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.back().second; 611ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 612ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // If we visited all of the children of this node, "recurse" back up the 613ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // stack setting the DFOutNum. 614ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser if (ChildIt == Node->end()) { 615ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser Node->DFSNumOut = DFSNum++; 616ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.pop_back(); 617ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser } else { 618ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser // Otherwise, recursively visit this child. 61936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNodeBase<NodeT> *Child = *ChildIt; 620ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser ++WorkStack.back().second; 621ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser 622ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser WorkStack.push_back(std::make_pair(Child, Child->begin())); 623ecd4694458796d8d9dd205a8eb43ff7163425bcaTobias Grosser Child->DFSNumIn = DFSNum++; 62449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 62549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 6260aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 62749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson SlowQueries = 0; 62849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DFSInfoValid = true; 62949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 6300aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 63149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { 63234b5f0437b9bf67bcbeb166a1c092dbbe3786157Benjamin Kramer if (DomTreeNodeBase<NodeT> *Node = getNode(BB)) 63334b5f0437b9bf67bcbeb166a1c092dbbe3786157Benjamin Kramer return Node; 63449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 63549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // Haven't calculated this node yet? Get or calculate the node for the 63649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // immediate dominator. 63749b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson NodeT *IDom = getIDom(BB); 6381f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 63946bb007014414c966586a983dbf24f38490e0f22Owen Anderson assert(IDom || this->DomTreeNodes[NULL]); 64049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); 64149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 64236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Add a new tree node for this NodeT, and link it as a child of 64349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson // IDomNode 64449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode); 64549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson return this->DomTreeNodes[BB] = IDomNode->addChild(C); 64649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson } 6470aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 64849b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson inline NodeT *getIDom(NodeT *BB) const { 64934b5f0437b9bf67bcbeb166a1c092dbbe3786157Benjamin Kramer return IDoms.lookup(BB); 650d20c824b201b1408d7ea7a4e2d601aee14db5cecOwen Anderson } 6510aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 6525d32ec4cb002973cb12bc21a3fe12364794168c8Owen Anderson inline void addRoot(NodeT* BB) { 6531f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson this->Roots.push_back(BB); 6545d32ec4cb002973cb12bc21a3fe12364794168c8Owen Anderson } 6550aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 65678daec973e81b1e85c2c3f5882845317da432f21Owen Andersonpublic: 65778daec973e81b1e85c2c3f5882845317da432f21Owen Anderson /// recalculate - compute a dominator tree for the given function 6584d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson template<class FT> 6594d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson void recalculate(FT& F) { 660e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks typedef GraphTraits<FT*> TraitsTy; 661365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser reset(); 662365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser this->Vertex.push_back(0); 6630aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 664365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser if (!this->IsPostDominators) { 665365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser // Initialize root 666e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks NodeT *entry = TraitsTy::getEntryNode(&F); 667e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks this->Roots.push_back(entry); 668e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks this->IDoms[entry] = 0; 669e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks this->DomTreeNodes[entry] = 0; 6700aeed044d6c9849351918f0535b8ce30ba2c4200Dan Gohman 6714d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson Calculate<FT, NodeT*>(*this, F); 67278daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } else { 67378daec973e81b1e85c2c3f5882845317da432f21Owen Anderson // Initialize the roots list 674e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), 675e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks E = TraitsTy::nodes_end(&F); I != E; ++I) { 676aa4e2aea9e8ce01f31a917639bcc7d810b9fe6d1Jakub Staszak if (TraitsTy::child_begin(I) == TraitsTy::child_end(I)) 6775d32ec4cb002973cb12bc21a3fe12364794168c8Owen Anderson addRoot(I); 67878daec973e81b1e85c2c3f5882845317da432f21Owen Anderson 67978daec973e81b1e85c2c3f5882845317da432f21Owen Anderson // Prepopulate maps so that we don't get iterator invalidation issues later. 68078daec973e81b1e85c2c3f5882845317da432f21Owen Anderson this->IDoms[I] = 0; 68178daec973e81b1e85c2c3f5882845317da432f21Owen Anderson this->DomTreeNodes[I] = 0; 68278daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 68378daec973e81b1e85c2c3f5882845317da432f21Owen Anderson 6844d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson Calculate<FT, Inverse<NodeT*> >(*this, F); 68578daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 68678daec973e81b1e85c2c3f5882845317da432f21Owen Anderson } 6870cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner}; 6880cbc6c2fd8470c62d824667fc600d80a494d26cdChris Lattner 6895004e9849aff165bcbd953f891b402ad23bdd1acRafael Espindola// These two functions are declared out of line as a workaround for building 6906226c49bdec886a7162e24e152af579df203e163Rafael Espindola// with old (< r147295) versions of clang because of pr11642. 6916226c49bdec886a7162e24e152af579df203e163Rafael Espindolatemplate<class NodeT> 69236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const { 6936226c49bdec886a7162e24e152af579df203e163Rafael Espindola if (A == B) 6946226c49bdec886a7162e24e152af579df203e163Rafael Espindola return true; 6956226c49bdec886a7162e24e152af579df203e163Rafael Espindola 6966226c49bdec886a7162e24e152af579df203e163Rafael Espindola // Cast away the const qualifiers here. This is ok since 6976226c49bdec886a7162e24e152af579df203e163Rafael Espindola // this function doesn't actually return the values returned 6986226c49bdec886a7162e24e152af579df203e163Rafael Espindola // from getNode. 6996226c49bdec886a7162e24e152af579df203e163Rafael Espindola return dominates(getNode(const_cast<NodeT *>(A)), 7006226c49bdec886a7162e24e152af579df203e163Rafael Espindola getNode(const_cast<NodeT *>(B))); 7016226c49bdec886a7162e24e152af579df203e163Rafael Espindola} 7026226c49bdec886a7162e24e152af579df203e163Rafael Espindolatemplate<class NodeT> 7036226c49bdec886a7162e24e152af579df203e163Rafael Espindolabool 70436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesDominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) const { 7056226c49bdec886a7162e24e152af579df203e163Rafael Espindola if (A == B) 7066226c49bdec886a7162e24e152af579df203e163Rafael Espindola return false; 7076226c49bdec886a7162e24e152af579df203e163Rafael Espindola 7086226c49bdec886a7162e24e152af579df203e163Rafael Espindola // Cast away the const qualifiers here. This is ok since 7096226c49bdec886a7162e24e152af579df203e163Rafael Espindola // this function doesn't actually return the values returned 7106226c49bdec886a7162e24e152af579df203e163Rafael Espindola // from getNode. 7116226c49bdec886a7162e24e152af579df203e163Rafael Espindola return dominates(getNode(const_cast<NodeT *>(A)), 7126226c49bdec886a7162e24e152af579df203e163Rafael Espindola getNode(const_cast<NodeT *>(B))); 7136226c49bdec886a7162e24e152af579df203e163Rafael Espindola} 7146226c49bdec886a7162e24e152af579df203e163Rafael Espindola 71536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 716d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 71770b6337d681b1d0a62922ce806fc15c2b8a31e5fChris Lattner#endif 718