136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==// 258ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson// 358ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson// The LLVM Compiler Infrastructure 458ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 758ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson// 858ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \file 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Generic dominator tree construction - This file provides routines to 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// construct immediate dominator information for a flow-graph based on the 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// algorithm described in this document: 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// A Fast Algorithm for Finding Dominators in a Flowgraph 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// out that the theoretically slower O(n*log(n)) implementation is actually 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs. 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 2358ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 2458ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef LLVM_SUPPORT_GENERIC_DOM_TREE_CONSTRUCTION_H 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#define LLVM_SUPPORT_GENERIC_DOM_TREE_CONSTRUCTION_H 27d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallPtrSet.h" 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/GenericDomTree.h" 3058ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 3158ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Andersonnamespace llvm { 3258ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 3358ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Andersontemplate<class GraphT> 3449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Andersonunsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, 3549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typename GraphT::NodeType* V, unsigned N) { 3658ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson // This is more understandable as a recursive algorithm, but we can't use the 3758ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson // recursive algorithm due to stack depth issues. Keep it here for 3858ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson // documentation purposes. 3958ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson#if 0 4058ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson InfoRec &VInfo = DT.Info[DT.Roots[i]]; 411f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson VInfo.DFSNum = VInfo.Semi = ++N; 4258ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson VInfo.Label = V; 4358ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 4458ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson Vertex.push_back(V); // Vertex[n] = V; 4558ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 4658ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { 4758ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson InfoRec &SuccVInfo = DT.Info[*SI]; 4858ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson if (SuccVInfo.Semi == 0) { 4958ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson SuccVInfo.Parent = V; 5058ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson N = DTDFSPass(DT, *SI, N); 5158ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson } 5258ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson } 5358ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson#else 54113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen bool IsChildOfArtificialExit = (N != 0); 551f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 5655be644df6e8b8ba08ae789ee440c798f21974a0Cameron Zwarich SmallVector<std::pair<typename GraphT::NodeType*, 5755be644df6e8b8ba08ae789ee440c798f21974a0Cameron Zwarich typename GraphT::ChildIteratorType>, 32> Worklist; 5858ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson Worklist.push_back(std::make_pair(V, GraphT::child_begin(V))); 5958ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson while (!Worklist.empty()) { 6058ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson typename GraphT::NodeType* BB = Worklist.back().first; 6158ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson typename GraphT::ChildIteratorType NextSucc = Worklist.back().second; 6258ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 631f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo = 641f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson DT.Info[BB]; 651f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 6658ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson // First time we visited this BB? 6758ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson if (NextSucc == GraphT::child_begin(BB)) { 681f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson BBInfo.DFSNum = BBInfo.Semi = ++N; 6958ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson BBInfo.Label = BB; 7058ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 7158ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson DT.Vertex.push_back(BB); // Vertex[n] = V; 721f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 73113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen if (IsChildOfArtificialExit) 741f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson BBInfo.Parent = 1; 751f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 76113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen IsChildOfArtificialExit = false; 7758ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson } 781f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 791f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson // store the DFS number of the current BB - the reference to BBInfo might 801f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson // get invalidated when processing the successors. 811f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson unsigned BBDFSNum = BBInfo.DFSNum; 821f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 8358ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson // If we are done with this block, remove it from the worklist. 8458ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson if (NextSucc == GraphT::child_end(BB)) { 8558ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson Worklist.pop_back(); 8658ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson continue; 8758ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson } 8858ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 8958ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson // Increment the successor number for the next time we get to it. 9058ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson ++Worklist.back().second; 9158ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 9258ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson // Visit the successor next, if it isn't already visited. 9358ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson typename GraphT::NodeType* Succ = *NextSucc; 9458ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 9549b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo = 9649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DT.Info[Succ]; 9758ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson if (SuccVInfo.Semi == 0) { 981f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson SuccVInfo.Parent = BBDFSNum; 9958ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ))); 10058ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson } 10158ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson } 10258ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson#endif 10358ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson return N; 10458ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson} 10558ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 106ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Andersontemplate<class GraphT> 10754cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarichtypename GraphT::NodeType* 10854cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron ZwarichEval(DominatorTreeBase<typename GraphT::NodeType>& DT, 10954cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich typename GraphT::NodeType *VIn, unsigned LastLinked) { 11054cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo = 11154cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich DT.Info[VIn]; 11254cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich if (VInInfo.DFSNum < LastLinked) 11354cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich return VIn; 11454cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich 115a53fe6070cae7d2feccb542b8ba24b37d3fdd027Benjamin Kramer SmallVector<typename GraphT::NodeType*, 32> Work; 116ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson SmallPtrSet<typename GraphT::NodeType*, 32> Visited; 117ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson 11854cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich if (VInInfo.Parent >= LastLinked) 119ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson Work.push_back(VIn); 120ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson 121ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson while (!Work.empty()) { 122ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson typename GraphT::NodeType* V = Work.back(); 12349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo = 12449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DT.Info[V]; 12554cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent]; 126ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson 127ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson // Process Ancestor first 12854cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich if (Visited.insert(VAncestor) && VInfo.Parent >= LastLinked) { 129ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson Work.push_back(VAncestor); 130ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson continue; 131ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson } 132ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson Work.pop_back(); 133ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson 134ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson // Update VInfo based on Ancestor info 13554cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich if (VInfo.Parent < LastLinked) 136ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson continue; 13754cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich 13854cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo = 13954cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich DT.Info[VAncestor]; 140ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson typename GraphT::NodeType* VAncestorLabel = VAInfo.Label; 141ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson typename GraphT::NodeType* VLabel = VInfo.Label; 142ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi) 143ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson VInfo.Label = VAncestorLabel; 14454cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich VInfo.Parent = VAInfo.Parent; 145ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson } 146ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson 14754cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich return VInInfo.Label; 148ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson} 149ab528fe0fb7caa96ce789bf872d7058aec8ae7c8Owen Anderson 1504d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Andersontemplate<class FuncT, class NodeT> 1514d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Andersonvoid Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, 1524d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson FuncT& F) { 1534d6d5783d8f803a9ae1ad64b16643f7ddeacbc1bOwen Anderson typedef GraphTraits<NodeT> GraphT; 1541f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 1551f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson unsigned N = 0; 1561f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson bool MultipleRoots = (DT.Roots.size() > 1); 1571f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson if (MultipleRoots) { 1581f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo = 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DT.Info[nullptr]; 1601f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson BBInfo.DFSNum = BBInfo.Semi = ++N; 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BBInfo.Label = nullptr; 1621f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DT.Vertex.push_back(nullptr); // Vertex[n] = V; 1641f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson } 1651f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 1669cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson // Step #1: Number blocks in depth-first order and initialize variables used 1679cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson // in later stages of the algorithm. 16834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size()); 16934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng i != e; ++i) 17049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson N = DFSPass<GraphT>(DT, DT.Roots[i], N); 1719cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson 17246bb007014414c966586a983dbf24f38490e0f22Owen Anderson // it might be that some blocks did not get a DFS number (e.g., blocks of 17346bb007014414c966586a983dbf24f38490e0f22Owen Anderson // infinite loops). In these cases an artificial exit node is required. 174e15402f92b6949d2474cc82648239fe22e5a2209Anna Zaks MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F)); 17546bb007014414c966586a983dbf24f38490e0f22Owen Anderson 176113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // When naively implemented, the Lengauer-Tarjan algorithm requires a separate 177113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // bucket for each vertex. However, this is unnecessary, because each vertex 178113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // is only placed into a single bucket (that of its semidominator), and each 179113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // vertex's bucket is processed before it is added to any bucket itself. 180113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // 181113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // Instead of using a bucket per vertex, we use a single array Buckets that 182113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // has two purposes. Before the vertex V with preorder number i is processed, 183113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // Buckets[i] stores the index of the first element in V's bucket. After V's 184113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // bucket is processed, Buckets[i] stores the index of the next element in the 185113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // bucket containing V, if any. 186907b56ce7ab26222fa128d5062f8dddf11c81603Cameron Zwarich SmallVector<unsigned, 32> Buckets; 187113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen Buckets.resize(N + 1); 188113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen for (unsigned i = 1; i <= N; ++i) 189113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen Buckets[i] = i; 190113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen 1919cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson for (unsigned i = N; i >= 2; --i) { 19249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typename GraphT::NodeType* W = DT.Vertex[i]; 19349b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo = 19449b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson DT.Info[W]; 1959cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson 196113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // Step #2: Implicitly define the immediate dominator of vertices 197113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) { 198113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; 19954cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich typename GraphT::NodeType* U = Eval<GraphT>(DT, V, i + 1); 200113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen DT.IDoms[V] = DT.Info[U].Semi < i ? U : W; 201113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen } 202113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen 203113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen // Step #3: Calculate the semidominators of all vertices 2041f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 2051f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson // initialize the semi dominator to point to the parent node 2061f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson WInfo.Semi = WInfo.Parent; 207da995609e6e963eaa77346d43b0a33b81e53a785Gabor Greif typedef GraphTraits<Inverse<NodeT> > InvTraits; 208da995609e6e963eaa77346d43b0a33b81e53a785Gabor Greif for (typename InvTraits::ChildIteratorType CI = 209da995609e6e963eaa77346d43b0a33b81e53a785Gabor Greif InvTraits::child_begin(W), 210da995609e6e963eaa77346d43b0a33b81e53a785Gabor Greif E = InvTraits::child_end(W); CI != E; ++CI) { 211da995609e6e963eaa77346d43b0a33b81e53a785Gabor Greif typename InvTraits::NodeType *N = *CI; 212da995609e6e963eaa77346d43b0a33b81e53a785Gabor Greif if (DT.Info.count(N)) { // Only if this predecessor is reachable! 21354cdad97eb77caf841ade5827a1d5da6b2d89df3Cameron Zwarich unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi; 2149cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson if (SemiU < WInfo.Semi) 2159cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson WInfo.Semi = SemiU; 2169cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson } 217da995609e6e963eaa77346d43b0a33b81e53a785Gabor Greif } 2189cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson 2192974b6ffbcffcd7fb02958c7382edf45e4a30f14Cameron Zwarich // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is 2202974b6ffbcffcd7fb02958c7382edf45e4a30f14Cameron Zwarich // necessarily parent(V). In this case, set idom(V) here and avoid placing 2212974b6ffbcffcd7fb02958c7382edf45e4a30f14Cameron Zwarich // V into a bucket. 222113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen if (WInfo.Semi == WInfo.Parent) { 223113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen DT.IDoms[W] = DT.Vertex[WInfo.Parent]; 224113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen } else { 225113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen Buckets[i] = Buckets[WInfo.Semi]; 226113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen Buckets[WInfo.Semi] = i; 227113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen } 228113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen } 2299cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson 230113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen if (N >= 1) { 231113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen typename GraphT::NodeType* Root = DT.Vertex[1]; 232113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) { 233113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; 234113328db1b6c71d6bb8f62ebef193efb1a44f1a4Jakob Stoklund Olesen DT.IDoms[V] = Root; 2359cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson } 2369cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson } 2379cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson 2389cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson // Step #4: Explicitly define the immediate dominator of each vertex 2399cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson for (unsigned i = 2; i <= N; ++i) { 24049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typename GraphT::NodeType* W = DT.Vertex[i]; 24149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson typename GraphT::NodeType*& WIDom = DT.IDoms[W]; 2429cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson if (WIDom != DT.Vertex[DT.Info[W].Semi]) 2439cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson WIDom = DT.IDoms[WIDom]; 2449cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson } 24546bb007014414c966586a983dbf24f38490e0f22Owen Anderson 2469cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson if (DT.Roots.empty()) return; 24746bb007014414c966586a983dbf24f38490e0f22Owen Anderson 2489cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson // Add a node for the root. This node might be the actual root, if there is 2499cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) 25046bb007014414c966586a983dbf24f38490e0f22Owen Anderson // which postdominates all real exits if there are multiple exit blocks, or 25146bb007014414c966586a983dbf24f38490e0f22Owen Anderson // an infinite loop. 252dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : nullptr; 25346bb007014414c966586a983dbf24f38490e0f22Owen Anderson 2545d32ec4cb002973cb12bc21a3fe12364794168c8Owen Anderson DT.DomTreeNodes[Root] = DT.RootNode = 255dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines new DomTreeNodeBase<typename GraphT::NodeType>(Root, nullptr); 25646bb007014414c966586a983dbf24f38490e0f22Owen Anderson 2579cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson // Loop over all of the reachable blocks in the function... 2581f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson for (unsigned i = 2; i <= N; ++i) { 2591f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson typename GraphT::NodeType* W = DT.Vertex[i]; 2601f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 2611f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson DomTreeNodeBase<typename GraphT::NodeType> *BBNode = DT.DomTreeNodes[W]; 2621f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson if (BBNode) continue; // Haven't calculated this node yet? 2631f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 2641f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson typename GraphT::NodeType* ImmDom = DT.getIDom(W); 2651f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 266dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(ImmDom || DT.DomTreeNodes[nullptr]); 2671f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 2681f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson // Get or calculate the node for the immediate dominator 2691f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson DomTreeNodeBase<typename GraphT::NodeType> *IDomNode = 2705d32ec4cb002973cb12bc21a3fe12364794168c8Owen Anderson DT.getNodeForBlock(ImmDom); 2719cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson 2721f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson // Add a new tree node for this BasicBlock, and link it as a child of 2731f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson // IDomNode 2741f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson DomTreeNodeBase<typename GraphT::NodeType> *C = 2751f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson new DomTreeNodeBase<typename GraphT::NodeType>(W, IDomNode); 2761f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson DT.DomTreeNodes[W] = IDomNode->addChild(C); 2771f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson } 2781f23e163190f85e46f2009bf43ee4fe8299044e4Owen Anderson 2799cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson // Free temporary memory used to construct idom's 2809cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson DT.IDoms.clear(); 2819cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson DT.Info.clear(); 28249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson std::vector<typename GraphT::NodeType*>().swap(DT.Vertex); 283365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser 284365ccd3a919b017f79140028dac15ef0c70641ddTobias Grosser DT.updateDFSNumbers(); 2859cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson} 2869cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson 28758ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson} 28858ec8825d46085841a1af55ee7f8117ad25ecf2fOwen Anderson 2893c5f0233e094ec5cea8e0f95af72fe29a7ce851dDuncan Sands#endif 290