Dominators.cpp revision d75405fe95660877f62064211e252c8c8c4c05ea
14c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner//===- Dominators.cpp - Dominator Calculation -----------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 91715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 104c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// This file implements simple dominator construction algorithms for finding 114c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// forward dominators. Postdominators are available in libanalysis, but are not 124c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// included in libvmcore, because it's not needed. Forward dominators are 134c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// needed to support the Verifier pass. 141715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 151715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 161715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 171715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner#include "llvm/Analysis/Dominators.h" 18221d688a5ef21a22c2368c9fff0e92d7966c95e5Chris Lattner#include "llvm/Support/CFG.h" 19a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner#include "llvm/Assembly/Writer.h" 20551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 21551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h" 222ad28e6c486f91d83b2d5bcd30612049a686ad64Devang Patel#include "llvm/ADT/SmallPtrSet.h" 23b9dbc4deccefc062a29bce49dc60bf9d5627e603Devang Patel#include "llvm/Instructions.h" 2479b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel#include "llvm/Support/Streams.h" 258e72749fc0b44ac8b7a5ffbb275f2ad60f2fa41eChris Lattner#include <algorithm> 2631f8499e83dc4dccbb57ea7e76d1fd49b7010d0cChris Lattnerusing namespace llvm; 27d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 283dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonnamespace llvm { 293dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonstatic std::ostream &operator<<(std::ostream &o, 303dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson const std::set<BasicBlock*> &BBs) { 313dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 323dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson I != E; ++I) 333dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson if (*I) 343dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson WriteAsOperand(o, *I, false); 353dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson else 363dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson o << " <<exit node>>"; 373dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson return o; 383dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson} 393dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson} 403dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 4194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner//===----------------------------------------------------------------------===// 423dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson// DominatorTree Implementation 4316addf87bf331645de63575aa15627c74b9cab66Chris Lattner//===----------------------------------------------------------------------===// 4416addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 453dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson// DominatorTree construction - This pass constructs immediate dominator 4616addf87bf331645de63575aa15627c74b9cab66Chris Lattner// information for a flow-graph based on the algorithm described in this 4716addf87bf331645de63575aa15627c74b9cab66Chris Lattner// document: 4816addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 4916addf87bf331645de63575aa15627c74b9cab66Chris Lattner// A Fast Algorithm for Finding Dominators in a Flowgraph 5016addf87bf331645de63575aa15627c74b9cab66Chris Lattner// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 5116addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 5216addf87bf331645de63575aa15627c74b9cab66Chris Lattner// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and 5316addf87bf331645de63575aa15627c74b9cab66Chris Lattner// LINK, but it turns out that the theoretically slower O(n*log(n)) 5416addf87bf331645de63575aa15627c74b9cab66Chris Lattner// implementation is actually faster than the "efficient" algorithm (even for 5516addf87bf331645de63575aa15627c74b9cab66Chris Lattner// large CFGs) because the constant overheads are substantially smaller. The 5616addf87bf331645de63575aa15627c74b9cab66Chris Lattner// lower-complexity version can be enabled with the following #define: 5716addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 5816addf87bf331645de63575aa15627c74b9cab66Chris Lattner#define BALANCE_IDOM_TREE 0 5916addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 6016addf87bf331645de63575aa15627c74b9cab66Chris Lattner//===----------------------------------------------------------------------===// 6116addf87bf331645de63575aa15627c74b9cab66Chris Lattner 621997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar DominatorTree::ID = 0; 633dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonstatic RegisterPass<DominatorTree> 643dc6776b338f81e2d47daa42cc12c9f91053043dOwen AndersonE("domtree", "Dominator Tree Construction", true); 6516addf87bf331645de63575aa15627c74b9cab66Chris Lattner 663dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonunsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, 6716addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned N) { 68a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // This is more understandable as a recursive algorithm, but we can't use the 69a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // recursive algorithm due to stack depth issues. Keep it here for 70a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // documentation purposes. 71a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner#if 0 7216addf87bf331645de63575aa15627c74b9cab66Chris Lattner VInfo.Semi = ++N; 7316addf87bf331645de63575aa15627c74b9cab66Chris Lattner VInfo.Label = V; 7416addf87bf331645de63575aa15627c74b9cab66Chris Lattner 7516addf87bf331645de63575aa15627c74b9cab66Chris Lattner Vertex.push_back(V); // Vertex[n] = V; 7616addf87bf331645de63575aa15627c74b9cab66Chris Lattner //Info[V].Ancestor = 0; // Ancestor[n] = 0 77a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner //Info[V].Child = 0; // Child[v] = 0 7816addf87bf331645de63575aa15627c74b9cab66Chris Lattner VInfo.Size = 1; // Size[v] = 1 7916addf87bf331645de63575aa15627c74b9cab66Chris Lattner 8016addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { 8116addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec &SuccVInfo = Info[*SI]; 8216addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (SuccVInfo.Semi == 0) { 8316addf87bf331645de63575aa15627c74b9cab66Chris Lattner SuccVInfo.Parent = V; 8416addf87bf331645de63575aa15627c74b9cab66Chris Lattner N = DFSPass(*SI, SuccVInfo, N); 8516addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 8616addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 87a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner#else 88a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner std::vector<std::pair<BasicBlock*, unsigned> > Worklist; 89a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner Worklist.push_back(std::make_pair(V, 0U)); 90a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner while (!Worklist.empty()) { 91a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BasicBlock *BB = Worklist.back().first; 92a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner unsigned NextSucc = Worklist.back().second; 93a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 94a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // First time we visited this BB? 95a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner if (NextSucc == 0) { 96a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner InfoRec &BBInfo = Info[BB]; 97a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BBInfo.Semi = ++N; 98a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BBInfo.Label = BB; 99a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 100a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner Vertex.push_back(BB); // Vertex[n] = V; 101a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0 102a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner //BBInfo[V].Child = 0; // Child[v] = 0 103a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BBInfo.Size = 1; // Size[v] = 1 104a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner } 105a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 106a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // If we are done with this block, remove it from the worklist. 107a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner if (NextSucc == BB->getTerminator()->getNumSuccessors()) { 108a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner Worklist.pop_back(); 109a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner continue; 110a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner } 111a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 112a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // Otherwise, increment the successor number for the next time we get to it. 113a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner ++Worklist.back().second; 114a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 115a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // Visit the successor next, if it isn't already visited. 116a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc); 117a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 118a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner InfoRec &SuccVInfo = Info[Succ]; 119a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner if (SuccVInfo.Semi == 0) { 120a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner SuccVInfo.Parent = BB; 121a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner Worklist.push_back(std::make_pair(Succ, 0U)); 122a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner } 123a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner } 124a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner#endif 12516addf87bf331645de63575aa15627c74b9cab66Chris Lattner return N; 12616addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 12716addf87bf331645de63575aa15627c74b9cab66Chris Lattner 12899c282453af9353ab1be42604414e8f4de338477Devang Patelvoid DominatorTree::Compress(BasicBlock *VIn) { 12916addf87bf331645de63575aa15627c74b9cab66Chris Lattner 13099c282453af9353ab1be42604414e8f4de338477Devang Patel std::vector<BasicBlock *> Work; 13199c282453af9353ab1be42604414e8f4de338477Devang Patel std::set<BasicBlock *> Visited; 13299c282453af9353ab1be42604414e8f4de338477Devang Patel InfoRec &VInInfo = Info[VIn]; 13399c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *VInAncestor = VInInfo.Ancestor; 13499c282453af9353ab1be42604414e8f4de338477Devang Patel InfoRec &VInVAInfo = Info[VInAncestor]; 13516addf87bf331645de63575aa15627c74b9cab66Chris Lattner 13699c282453af9353ab1be42604414e8f4de338477Devang Patel if (VInVAInfo.Ancestor != 0) 13799c282453af9353ab1be42604414e8f4de338477Devang Patel Work.push_back(VIn); 13899c282453af9353ab1be42604414e8f4de338477Devang Patel 13999c282453af9353ab1be42604414e8f4de338477Devang Patel while (!Work.empty()) { 14099c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *V = Work.back(); 14199c282453af9353ab1be42604414e8f4de338477Devang Patel InfoRec &VInfo = Info[V]; 14299c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *VAncestor = VInfo.Ancestor; 14399c282453af9353ab1be42604414e8f4de338477Devang Patel InfoRec &VAInfo = Info[VAncestor]; 14499c282453af9353ab1be42604414e8f4de338477Devang Patel 14599c282453af9353ab1be42604414e8f4de338477Devang Patel // Process Ancestor first 14699c282453af9353ab1be42604414e8f4de338477Devang Patel if (Visited.count(VAncestor) == 0 && VAInfo.Ancestor != 0) { 14799c282453af9353ab1be42604414e8f4de338477Devang Patel Work.push_back(VAncestor); 14899c282453af9353ab1be42604414e8f4de338477Devang Patel Visited.insert(VAncestor); 14999c282453af9353ab1be42604414e8f4de338477Devang Patel continue; 15099c282453af9353ab1be42604414e8f4de338477Devang Patel } 15199c282453af9353ab1be42604414e8f4de338477Devang Patel Work.pop_back(); 15216addf87bf331645de63575aa15627c74b9cab66Chris Lattner 15399c282453af9353ab1be42604414e8f4de338477Devang Patel // Update VINfo based on Ancestor info 15499c282453af9353ab1be42604414e8f4de338477Devang Patel if (VAInfo.Ancestor == 0) 15599c282453af9353ab1be42604414e8f4de338477Devang Patel continue; 15699c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *VAncestorLabel = VAInfo.Label; 15799c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *VLabel = VInfo.Label; 15899c282453af9353ab1be42604414e8f4de338477Devang Patel if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) 15999c282453af9353ab1be42604414e8f4de338477Devang Patel VInfo.Label = VAncestorLabel; 16099c282453af9353ab1be42604414e8f4de338477Devang Patel VInfo.Ancestor = VAInfo.Ancestor; 16199c282453af9353ab1be42604414e8f4de338477Devang Patel } 16216addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 16316addf87bf331645de63575aa15627c74b9cab66Chris Lattner 1643dc6776b338f81e2d47daa42cc12c9f91053043dOwen AndersonBasicBlock *DominatorTree::Eval(BasicBlock *V) { 16516addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec &VInfo = Info[V]; 16616addf87bf331645de63575aa15627c74b9cab66Chris Lattner#if !BALANCE_IDOM_TREE 16716addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Higher-complexity but faster implementation 16816addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (VInfo.Ancestor == 0) 16916addf87bf331645de63575aa15627c74b9cab66Chris Lattner return V; 17099c282453af9353ab1be42604414e8f4de338477Devang Patel Compress(V); 17116addf87bf331645de63575aa15627c74b9cab66Chris Lattner return VInfo.Label; 17216addf87bf331645de63575aa15627c74b9cab66Chris Lattner#else 17316addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Lower-complexity but slower implementation 17416addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (VInfo.Ancestor == 0) 17516addf87bf331645de63575aa15627c74b9cab66Chris Lattner return VInfo.Label; 17699c282453af9353ab1be42604414e8f4de338477Devang Patel Compress(V); 17716addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *VLabel = VInfo.Label; 17816addf87bf331645de63575aa15627c74b9cab66Chris Lattner 17916addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; 18016addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi) 18116addf87bf331645de63575aa15627c74b9cab66Chris Lattner return VLabel; 18216addf87bf331645de63575aa15627c74b9cab66Chris Lattner else 18316addf87bf331645de63575aa15627c74b9cab66Chris Lattner return VAncestorLabel; 18416addf87bf331645de63575aa15627c74b9cab66Chris Lattner#endif 18516addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 18616addf87bf331645de63575aa15627c74b9cab66Chris Lattner 1873dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonvoid DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ 18816addf87bf331645de63575aa15627c74b9cab66Chris Lattner#if !BALANCE_IDOM_TREE 18916addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Higher-complexity but faster implementation 19016addf87bf331645de63575aa15627c74b9cab66Chris Lattner WInfo.Ancestor = V; 19116addf87bf331645de63575aa15627c74b9cab66Chris Lattner#else 19216addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Lower-complexity but slower implementation 19316addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *WLabel = WInfo.Label; 19416addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned WLabelSemi = Info[WLabel].Semi; 19516addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *S = W; 19616addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec *SInfo = &Info[S]; 197fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 19816addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *SChild = SInfo->Child; 19916addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec *SChildInfo = &Info[SChild]; 200fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 20116addf87bf331645de63575aa15627c74b9cab66Chris Lattner while (WLabelSemi < Info[SChildInfo->Label].Semi) { 20216addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *SChildChild = SChildInfo->Child; 20316addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { 20416addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChildInfo->Ancestor = S; 20516addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo->Child = SChild = SChildChild; 20616addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChildInfo = &Info[SChild]; 20716addf87bf331645de63575aa15627c74b9cab66Chris Lattner } else { 20816addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChildInfo->Size = SInfo->Size; 20916addf87bf331645de63575aa15627c74b9cab66Chris Lattner S = SInfo->Ancestor = SChild; 21016addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo = SChildInfo; 21116addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChild = SChildChild; 21216addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChildInfo = &Info[SChild]; 21316addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 21416addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 215fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 21616addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec &VInfo = Info[V]; 21716addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo->Label = WLabel; 218fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 21916addf87bf331645de63575aa15627c74b9cab66Chris Lattner assert(V != W && "The optimization here will not work in this case!"); 22016addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned WSize = WInfo.Size; 22116addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned VSize = (VInfo.Size += WSize); 222fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 22316addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (VSize < 2*WSize) 22416addf87bf331645de63575aa15627c74b9cab66Chris Lattner std::swap(S, VInfo.Child); 225fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 22616addf87bf331645de63575aa15627c74b9cab66Chris Lattner while (S) { 22716addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo = &Info[S]; 22816addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo->Ancestor = V; 22916addf87bf331645de63575aa15627c74b9cab66Chris Lattner S = SInfo->Child; 23016addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 23116addf87bf331645de63575aa15627c74b9cab66Chris Lattner#endif 23216addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 23316addf87bf331645de63575aa15627c74b9cab66Chris Lattner 2343dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonvoid DominatorTree::calculate(Function& F) { 235e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson BasicBlock* Root = Roots[0]; 2369a51157db555395f7a6ad89faec40b3afa121091Devang Patel 2379a51157db555395f7a6ad89faec40b3afa121091Devang Patel // Add a node for the root... 2384d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); 23916addf87bf331645de63575aa15627c74b9cab66Chris Lattner 24016addf87bf331645de63575aa15627c74b9cab66Chris Lattner Vertex.push_back(0); 241fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 24216addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Step #1: Number blocks in depth-first order and initialize variables used 24316addf87bf331645de63575aa15627c74b9cab66Chris Lattner // in later stages of the algorithm. 24416addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned N = 0; 24516addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (unsigned i = 0, e = Roots.size(); i != e; ++i) 24616addf87bf331645de63575aa15627c74b9cab66Chris Lattner N = DFSPass(Roots[i], Info[Roots[i]], 0); 24716addf87bf331645de63575aa15627c74b9cab66Chris Lattner 24816addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (unsigned i = N; i >= 2; --i) { 24916addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *W = Vertex[i]; 25016addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec &WInfo = Info[W]; 25116addf87bf331645de63575aa15627c74b9cab66Chris Lattner 25216addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Step #2: Calculate the semidominators of all vertices 25316addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI) 25416addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (Info.count(*PI)) { // Only if this predecessor is reachable! 25516addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned SemiU = Info[Eval(*PI)].Semi; 25616addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (SemiU < WInfo.Semi) 25716addf87bf331645de63575aa15627c74b9cab66Chris Lattner WInfo.Semi = SemiU; 25816addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 259fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 26016addf87bf331645de63575aa15627c74b9cab66Chris Lattner Info[Vertex[WInfo.Semi]].Bucket.push_back(W); 26116addf87bf331645de63575aa15627c74b9cab66Chris Lattner 26216addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *WParent = WInfo.Parent; 26316addf87bf331645de63575aa15627c74b9cab66Chris Lattner Link(WParent, W, WInfo); 26416addf87bf331645de63575aa15627c74b9cab66Chris Lattner 26516addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Step #3: Implicitly define the immediate dominator of vertices 26616addf87bf331645de63575aa15627c74b9cab66Chris Lattner std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket; 26716addf87bf331645de63575aa15627c74b9cab66Chris Lattner while (!WParentBucket.empty()) { 26816addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *V = WParentBucket.back(); 26916addf87bf331645de63575aa15627c74b9cab66Chris Lattner WParentBucket.pop_back(); 27016addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *U = Eval(V); 27116addf87bf331645de63575aa15627c74b9cab66Chris Lattner IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; 27216addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 27316addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 27416addf87bf331645de63575aa15627c74b9cab66Chris Lattner 27516addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Step #4: Explicitly define the immediate dominator of each vertex 27616addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (unsigned i = 2; i <= N; ++i) { 27716addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *W = Vertex[i]; 27816addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *&WIDom = IDoms[W]; 27916addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (WIDom != Vertex[Info[W].Semi]) 28016addf87bf331645de63575aa15627c74b9cab66Chris Lattner WIDom = IDoms[WIDom]; 28116addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 28216addf87bf331645de63575aa15627c74b9cab66Chris Lattner 2833dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson // Loop over all of the reachable blocks in the function... 2843dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 2853dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson if (BasicBlock *ImmDom = getIDom(I)) { // Reachable block. 286bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel DomTreeNode *&BBNode = DomTreeNodes[I]; 2873dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson if (!BBNode) { // Haven't calculated this node yet? 2883dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson // Get or calculate the node for the immediate dominator 289bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel DomTreeNode *IDomNode = getNodeForBlock(ImmDom); 2903dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 2913dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson // Add a new tree node for this BasicBlock, and link it as a child of 2923dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson // IDomNode 2934d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel DomTreeNode *C = new DomTreeNode(I, IDomNode); 2947d832fe6c1a15c5d0ae65d5c71fd7dcec12c551eDevang Patel DomTreeNodes[I] = C; 2957d832fe6c1a15c5d0ae65d5c71fd7dcec12c551eDevang Patel BBNode = IDomNode->addChild(C); 2963dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson } 2973dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson } 2983dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 29916addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Free temporary memory used to construct idom's 30016addf87bf331645de63575aa15627c74b9cab66Chris Lattner Info.clear(); 301e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson IDoms.clear(); 30216addf87bf331645de63575aa15627c74b9cab66Chris Lattner std::vector<BasicBlock*>().swap(Vertex); 3039a51157db555395f7a6ad89faec40b3afa121091Devang Patel 3049a51157db555395f7a6ad89faec40b3afa121091Devang Patel updateDFSNumbers(); 3059a51157db555395f7a6ad89faec40b3afa121091Devang Patel} 3069a51157db555395f7a6ad89faec40b3afa121091Devang Patel 3079a51157db555395f7a6ad89faec40b3afa121091Devang Patelvoid DominatorTreeBase::updateDFSNumbers() 3089a51157db555395f7a6ad89faec40b3afa121091Devang Patel{ 3099a51157db555395f7a6ad89faec40b3afa121091Devang Patel int dfsnum = 0; 3109a51157db555395f7a6ad89faec40b3afa121091Devang Patel // Iterate over all nodes in depth first order. 3119a51157db555395f7a6ad89faec40b3afa121091Devang Patel for (unsigned i = 0, e = Roots.size(); i != e; ++i) 3129a51157db555395f7a6ad89faec40b3afa121091Devang Patel for (df_iterator<BasicBlock*> I = df_begin(Roots[i]), 3139a51157db555395f7a6ad89faec40b3afa121091Devang Patel E = df_end(Roots[i]); I != E; ++I) { 3149a51157db555395f7a6ad89faec40b3afa121091Devang Patel BasicBlock *BB = *I; 315dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel DomTreeNode *BBNode = getNode(BB); 316dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel if (BBNode) { 3173726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel if (!BBNode->getIDom()) 3183726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel BBNode->assignDFSNumber(dfsnum); 319dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel } 3209a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 3219a51157db555395f7a6ad89faec40b3afa121091Devang Patel SlowQueries = 0; 3229a51157db555395f7a6ad89faec40b3afa121091Devang Patel DFSInfoValid = true; 3236aba48338f67f08637b05f38005059f27aaf69bfChris Lattner} 3246aba48338f67f08637b05f38005059f27aaf69bfChris Lattner 325dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel/// isReachableFromEntry - Return true if A is dominated by the entry 326dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel/// block of the function containing it. 327dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patelconst bool DominatorTreeBase::isReachableFromEntry(BasicBlock* A) { 328d75405fe95660877f62064211e252c8c8c4c05eaDevang Patel assert (!isPostDominator() 329d75405fe95660877f62064211e252c8c8c4c05eaDevang Patel && "This is not implemented for post dominators"); 330dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel return dominates(&A->getParent()->getEntryBlock(), A); 331dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel} 332dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel 333e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel// dominates - Return true if A dominates B. THis performs the 334e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel// special checks necessary if A and B are in the same basic block. 335e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patelbool DominatorTreeBase::dominates(Instruction *A, Instruction *B) { 336e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 337e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel if (BBA != BBB) return dominates(BBA, BBB); 338e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel 339e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // It is not possible to determine dominance between two PHI nodes 340e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // based on their ordering. 341e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel if (isa<PHINode>(A) && isa<PHINode>(B)) 342e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel return false; 343e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel 344e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // Loop through the basic block until we find A or B. 345e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel BasicBlock::iterator I = BBA->begin(); 346e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel for (; &*I != A && &*I != B; ++I) /*empty*/; 347e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel 348e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel if(!IsPostDominators) { 349e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // A dominates B if it is found first in the basic block. 350e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel return &*I == A; 351e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel } else { 352e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // A post-dominates B if B is found first in the basic block. 353e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel return &*I == B; 354e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel } 355e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel} 3569a51157db555395f7a6ad89faec40b3afa121091Devang Patel 357ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner// DominatorTreeBase::reset - Free all of the tree node memory. 3581715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 359fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukmanvoid DominatorTreeBase::reset() { 36087f05a24160805b13bd68f1908589a193497f157Devang Patel for (DomTreeNodeMapType::iterator I = DomTreeNodes.begin(), 36187f05a24160805b13bd68f1908589a193497f157Devang Patel E = DomTreeNodes.end(); I != E; ++I) 3621715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner delete I->second; 363bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel DomTreeNodes.clear(); 364e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson IDoms.clear(); 365e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson Roots.clear(); 3663831c553e33c100b84be8fa95228c315ac4fdc30Devang Patel Vertex.clear(); 367b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner RootNode = 0; 3681715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner} 3691715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 370fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel/// findNearestCommonDominator - Find nearest common dominator basic block 371fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel/// for basic block A and B. If there is no such block then return NULL. 37287f05a24160805b13bd68f1908589a193497f157Devang PatelBasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, 37387f05a24160805b13bd68f1908589a193497f157Devang Patel BasicBlock *B) { 374fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 37587f05a24160805b13bd68f1908589a193497f157Devang Patel assert (!isPostDominator() 37687f05a24160805b13bd68f1908589a193497f157Devang Patel && "This is not implemented for post dominators"); 37787f05a24160805b13bd68f1908589a193497f157Devang Patel assert (A->getParent() == B->getParent() 37887f05a24160805b13bd68f1908589a193497f157Devang Patel && "Two blocks are not in same function"); 379fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 380fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel // If either A or B is a entry block then it is nearest common dominator. 381fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel BasicBlock &Entry = A->getParent()->getEntryBlock(); 382fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel if (A == &Entry || B == &Entry) 383fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel return &Entry; 384fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 3855fd306bf0d75b8dde7e2ff5e42e15e96d5cdfcfeDevang Patel // If B dominates A then B is nearest common dominator. 3865fd306bf0d75b8dde7e2ff5e42e15e96d5cdfcfeDevang Patel if (dominates(B,A)) 38787f05a24160805b13bd68f1908589a193497f157Devang Patel return B; 38887f05a24160805b13bd68f1908589a193497f157Devang Patel 3895fd306bf0d75b8dde7e2ff5e42e15e96d5cdfcfeDevang Patel // If A dominates B then A is nearest common dominator. 3905fd306bf0d75b8dde7e2ff5e42e15e96d5cdfcfeDevang Patel if (dominates(A,B)) 39187f05a24160805b13bd68f1908589a193497f157Devang Patel return A; 39287f05a24160805b13bd68f1908589a193497f157Devang Patel 393de6e1320550bf3a6eb249155fcd14e9a0d84488eDevang Patel DomTreeNode *NodeA = getNode(A); 394de6e1320550bf3a6eb249155fcd14e9a0d84488eDevang Patel DomTreeNode *NodeB = getNode(B); 395de6e1320550bf3a6eb249155fcd14e9a0d84488eDevang Patel 396fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel // Collect NodeA dominators set. 397bdfa1f837cc760da560595b279c171cba8a75781Devang Patel SmallPtrSet<DomTreeNode*, 16> NodeADoms; 398fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel NodeADoms.insert(NodeA); 399fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel DomTreeNode *IDomA = NodeA->getIDom(); 400fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel while(IDomA) { 401fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel NodeADoms.insert(IDomA); 402fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel IDomA = IDomA->getIDom(); 403fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel } 404fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 405fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel // Walk NodeB immediate dominators chain and find common dominator node. 406fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel DomTreeNode *IDomB = NodeB->getIDom(); 407fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel while(IDomB) { 408fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel if (NodeADoms.count(IDomB) != 0) 409fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel return IDomB->getBlock(); 410fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 411fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel IDomB = IDomB->getIDom(); 412fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel } 413fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 414fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel return NULL; 415fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel} 416fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 4173726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel/// assignDFSNumber - Assign In and Out numbers while walking dominator tree 4183726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel/// in dfs order. 4193726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patelvoid DomTreeNode::assignDFSNumber(int num) { 4203726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel std::vector<DomTreeNode *> workStack; 4213726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel std::set<DomTreeNode *> visitedNodes; 4223726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 4233726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel workStack.push_back(this); 4243726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel visitedNodes.insert(this); 4253726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel this->DFSNumIn = num++; 4263726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 4273726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel while (!workStack.empty()) { 4283726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel DomTreeNode *Node = workStack.back(); 4293726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 4303726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel bool visitChild = false; 4313726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel for (std::vector<DomTreeNode*>::iterator DI = Node->begin(), 4323726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel E = Node->end(); DI != E && !visitChild; ++DI) { 4333726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel DomTreeNode *Child = *DI; 4343726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel if (visitedNodes.count(Child) == 0) { 4353726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel visitChild = true; 4363726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel Child->DFSNumIn = num++; 4373726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel workStack.push_back(Child); 4383726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel visitedNodes.insert(Child); 4393726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 4403726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 4413726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel if (!visitChild) { 4423726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel // If we reach here means all children are visited 4433726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel Node->DFSNumOut = num++; 4443726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel workStack.pop_back(); 4453726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 4463726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 4473726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel} 4483726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 44926042420d642e810f5cdfb2da6156b74aaf80945Devang Patelvoid DomTreeNode::setIDom(DomTreeNode *NewIDom) { 450d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner assert(IDom && "No immediate dominator?"); 451d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner if (IDom != NewIDom) { 452bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel std::vector<DomTreeNode*>::iterator I = 453d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner std::find(IDom->Children.begin(), IDom->Children.end(), this); 454d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner assert(I != IDom->Children.end() && 455d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner "Not in immediate dominator children set!"); 456d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner // I am no longer your child... 457d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner IDom->Children.erase(I); 458d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner 459d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner // Switch to new dominator 460d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner IDom = NewIDom; 461d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner IDom->Children.push_back(this); 462d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner } 463d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner} 464d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner 46526042420d642e810f5cdfb2da6156b74aaf80945Devang PatelDomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) { 466bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel DomTreeNode *&BBNode = DomTreeNodes[BB]; 46716addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (BBNode) return BBNode; 46816addf87bf331645de63575aa15627c74b9cab66Chris Lattner 46916addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Haven't calculated this node yet? Get or calculate the node for the 47016addf87bf331645de63575aa15627c74b9cab66Chris Lattner // immediate dominator. 4713dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson BasicBlock *IDom = getIDom(BB); 472bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel DomTreeNode *IDomNode = getNodeForBlock(IDom); 473fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 47416addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Add a new tree node for this BasicBlock, and link it as a child of 47516addf87bf331645de63575aa15627c74b9cab66Chris Lattner // IDomNode 4764d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel DomTreeNode *C = new DomTreeNode(BB, IDomNode); 4777d832fe6c1a15c5d0ae65d5c71fd7dcec12c551eDevang Patel DomTreeNodes[BB] = C; 4787d832fe6c1a15c5d0ae65d5c71fd7dcec12c551eDevang Patel return BBNode = IDomNode->addChild(C); 47916addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 480d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner 4811b0a63fa6450fdf60ae79969ae55fd001cb3b5b3Chris Lattnerstatic std::ostream &operator<<(std::ostream &o, 48226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node) { 483c444a4228f31656f854d15eac671b450df557346Chris Lattner if (Node->getBlock()) 484c444a4228f31656f854d15eac671b450df557346Chris Lattner WriteAsOperand(o, Node->getBlock(), false); 485b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner else 486b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << " <<exit node>>"; 487b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner return o << "\n"; 488a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 489a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner 49026042420d642e810f5cdfb2da6156b74aaf80945Devang Patelstatic void PrintDomTree(const DomTreeNode *N, std::ostream &o, 491a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner unsigned Lev) { 492b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; 49326042420d642e810f5cdfb2da6156b74aaf80945Devang Patel for (DomTreeNode::const_iterator I = N->begin(), E = N->end(); 494b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner I != E; ++I) 495a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner PrintDomTree(*I, o, Lev+1); 496a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 497a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner 498ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid DominatorTreeBase::print(std::ostream &o, const Module* ) const { 499a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner o << "=============================--------------------------------\n" 500a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner << "Inorder Dominator Tree:\n"; 501b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner PrintDomTree(getRootNode(), o, 1); 502a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 5031715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 50479b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patelvoid DominatorTreeBase::dump() { 50579b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel print (llvm::cerr); 50679b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel} 50779b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel 5083dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonbool DominatorTree::runOnFunction(Function &F) { 5093dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson reset(); // Reset from the last time we were run... 510e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson Roots.push_back(&F.getEntryBlock()); 5113dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson calculate(F); 5123dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson return false; 5133dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson} 5141715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 5151715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 5161715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// DominanceFrontier Implementation 5171715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 5181715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 5191997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar DominanceFrontier::ID = 0; 5205d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattnerstatic RegisterPass<DominanceFrontier> 52117689dfe241702cbbbd29cf1e4e4229444f3e9f3Chris LattnerG("domfrontier", "Dominance Frontier Construction", true); 52293193f806378e06092820c099e437886c7309b94Chris Lattner 5238645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattnernamespace { 5248645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner class DFCalculateWorkObject { 5258645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner public: 5268645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, 52726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *N, 52826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *PN) 52926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 5308645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner BasicBlock *currentBB; 5318645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner BasicBlock *parentBB; 53226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node; 53326042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *parentNode; 5348645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner }; 5358645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner} 5368645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner 5371b7f7dc4b45a900fae2e9b062d588a995935727aChris Lattnerconst DominanceFrontier::DomSetType & 538fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha BrukmanDominanceFrontier::calculate(const DominatorTree &DT, 53926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node) { 540c444a4228f31656f854d15eac671b450df557346Chris Lattner BasicBlock *BB = Node->getBlock(); 541cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType *Result = NULL; 542cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 5439be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel std::vector<DFCalculateWorkObject> workList; 5442ad28e6c486f91d83b2d5bcd30612049a686ad64Devang Patel SmallPtrSet<BasicBlock *, 32> visited; 545cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 5469be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); 547cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel do { 5489be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel DFCalculateWorkObject *currentW = &workList.back(); 549cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentW && "Missing work object."); 550cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 551cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *currentBB = currentW->currentBB; 552cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *parentBB = currentW->parentBB; 55326042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *currentNode = currentW->Node; 55426042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *parentNode = currentW->parentNode; 555cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentBB && "Invalid work object. Missing current Basic Block"); 556cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentNode && "Invalid work object. Missing current Node"); 557cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType &S = Frontiers[currentBB]; 558cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 559cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Visit each block only once. 560cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (visited.count(currentBB) == 0) { 561cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel visited.insert(currentBB); 562cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 563cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Loop over CFG successors to calculate DFlocal[currentNode] 564cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); 565cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel SI != SE; ++SI) { 566cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Does Node immediately dominate this successor? 567cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (DT[*SI]->getIDom() != currentNode) 568cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel S.insert(*SI); 569cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 570cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 5711715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 572cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // At this point, S is DFlocal. Now we union in DFup's of our children... 573cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Loop through and visit the nodes that Node immediately dominates (Node's 574cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // children in the IDomTree) 575cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel bool visitChild = false; 57626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel for (DomTreeNode::const_iterator NI = currentNode->begin(), 577cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel NE = currentNode->end(); NI != NE; ++NI) { 57826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *IDominee = *NI; 579cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *childBB = IDominee->getBlock(); 580cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (visited.count(childBB) == 0) { 5818645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner workList.push_back(DFCalculateWorkObject(childBB, currentBB, 5828645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner IDominee, currentNode)); 583cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel visitChild = true; 584cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 585cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 5861715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 587cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // If all children are visited or there is any child then pop this block 588cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // from the workList. 589cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (!visitChild) { 590cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 591cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (!parentBB) { 592cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel Result = &S; 593cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel break; 594cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 595cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 596cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 597cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType &parentSet = Frontiers[parentBB]; 598cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel for (; CDFI != CDFE; ++CDFI) { 5999a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (!DT.properlyDominates(parentNode, DT[*CDFI])) 600cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel parentSet.insert(*CDFI); 601cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 602cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel workList.pop_back(); 6031715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner } 6041715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 605cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } while (!workList.empty()); 606cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 607cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel return *Result; 6081715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner} 60994108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 610ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid DominanceFrontierBase::print(std::ostream &o, const Module* ) const { 611a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 612b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << " DomFrontier for BB"; 613b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner if (I->first) 614b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner WriteAsOperand(o, I->first, false); 615b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner else 616b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << " <<exit node>>"; 617b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << " is:\t" << I->second << "\n"; 618a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner } 619a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 620d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 62179b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patelvoid DominanceFrontierBase::dump() { 62279b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel print (llvm::cerr); 62379b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel} 62479b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel 62579b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel 626ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 627ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner// ETOccurrence Implementation 628ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 629ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 630ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattnervoid ETOccurrence::Splay() { 631ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *father; 632ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *grandfather; 633ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner int occdepth; 634ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner int fatherdepth; 635ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 636ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner while (Parent) { 637ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner occdepth = Depth; 638ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 639ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father = Parent; 640ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner fatherdepth = Parent->Depth; 641ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather = father->Parent; 642ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 643ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // If we have no grandparent, a single zig or zag will do. 644ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (!grandfather) { 645ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setDepthAdd(fatherdepth); 646ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner MinOccurrence = father->MinOccurrence; 647ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Min = father->Min; 648ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 649ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // See what we have to rotate 650ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Left == this) { 651ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Zig 652ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setLeft(Right); 653ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setRight(father); 654ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Left) 655ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->Left->setDepthAdd(occdepth); 656ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } else { 657ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Zag 658ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setRight(Left); 659ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setLeft(father); 660ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Right) 661ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->Right->setDepthAdd(occdepth); 662ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 663ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setDepth(-occdepth); 664ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Parent = NULL; 665ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 666ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->recomputeMin(); 667ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return; 668ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 669ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 670ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // If we have a grandfather, we need to do some 671ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // combination of zig and zag. 672ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner int grandfatherdepth = grandfather->Depth; 673ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 674ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setDepthAdd(fatherdepth + grandfatherdepth); 675ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner MinOccurrence = grandfather->MinOccurrence; 676ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Min = grandfather->Min; 677ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 678ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *greatgrandfather = grandfather->Parent; 679ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 680ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (grandfather->Left == father) { 681ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Left == this) { 682ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Zig zig 683ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->setLeft(father->Right); 684ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setLeft(Right); 685ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setRight(father); 686ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setRight(grandfather); 687ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 688ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setDepth(-occdepth); 689ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 690ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Left) 691ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->Left->setDepthAdd(occdepth); 692ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 693ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->setDepth(-fatherdepth); 694ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (grandfather->Left) 695ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->Left->setDepthAdd(fatherdepth); 696ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } else { 697ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Zag zig 698ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->setLeft(Right); 699ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setRight(Left); 700ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setLeft(father); 701ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setRight(grandfather); 702ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 703ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setDepth(-occdepth); 704ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Right) 705ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->Right->setDepthAdd(occdepth); 706ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->setDepth(-occdepth - fatherdepth); 707ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (grandfather->Left) 708ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->Left->setDepthAdd(occdepth + fatherdepth); 709ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 710ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } else { 711ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Left == this) { 712ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Zig zag 713ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->setRight(Left); 714ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setLeft(Right); 715ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setLeft(grandfather); 716ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setRight(father); 717ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 718ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setDepth(-occdepth); 719ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Left) 720ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->Left->setDepthAdd(occdepth); 721ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->setDepth(-occdepth - fatherdepth); 722ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (grandfather->Right) 723ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->Right->setDepthAdd(occdepth + fatherdepth); 724ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } else { // Zag Zag 725ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->setRight(father->Left); 726ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setRight(Left); 727ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setLeft(father); 728ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setLeft(grandfather); 729ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 730ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->setDepth(-occdepth); 731ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (father->Right) 732ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->Right->setDepthAdd(occdepth); 733ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->setDepth(-fatherdepth); 734ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (grandfather->Right) 735ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->Right->setDepthAdd(fatherdepth); 736ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 737ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 738ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 739ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Might need one more rotate depending on greatgrandfather. 740ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner setParent(greatgrandfather); 741ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (greatgrandfather) { 742ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (greatgrandfather->Left == grandfather) 743ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner greatgrandfather->Left = this; 744ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner else 745ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner greatgrandfather->Right = this; 746ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 747ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 748ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner grandfather->recomputeMin(); 749ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner father->recomputeMin(); 750ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 751ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 752ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 753ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 754ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner// ETNode implementation 755ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 756ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 757ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattnervoid ETNode::Split() { 758ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *right, *left; 759ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *rightmost = RightmostOcc; 760ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *parent; 761ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 762ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Update the occurrence tree first. 763ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner RightmostOcc->Splay(); 764ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 765ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Find the leftmost occurrence in the rightmost subtree, then splay 766ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // around it. 7676b135b74bd611086a2b7ec1da4ab82c18483f993Chris Lattner for (right = rightmost->Right; right->Left; right = right->Left); 768ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 769ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->Splay(); 770ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 771ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Start splitting 772ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->Left->Parent = NULL; 773ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner parent = ParentOcc; 774ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner parent->Splay(); 775ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ParentOcc = NULL; 776ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 777ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left = parent->Left; 778ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner parent->Right->Parent = NULL; 779ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 780ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->setLeft(left); 781ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 782ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->recomputeMin(); 783ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 784ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner rightmost->Splay(); 785ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner rightmost->Depth = 0; 786ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner rightmost->Min = 0; 787ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 788ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner delete parent; 789ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 790ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Now update *our* tree 791ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 792ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (Father->Son == this) 793ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Father->Son = Right; 794ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 795ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (Father->Son == this) 796ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Father->Son = NULL; 797ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner else { 798ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Left->Right = Right; 799ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Right->Left = Left; 800ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 801ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Left = Right = NULL; 802ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Father = NULL; 803ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 804ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 805ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattnervoid ETNode::setFather(ETNode *NewFather) { 806ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *rightmost; 807ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *leftpart; 808ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *NewFatherOcc; 809ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *temp; 810ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 811ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // First update the path in the splay tree 812ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner NewFatherOcc = new ETOccurrence(NewFather); 813ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 814ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner rightmost = NewFather->RightmostOcc; 815ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner rightmost->Splay(); 816ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 817ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner leftpart = rightmost->Left; 818ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 819ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner temp = RightmostOcc; 820ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner temp->Splay(); 821ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 822ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner NewFatherOcc->setLeft(leftpart); 823ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner NewFatherOcc->setRight(temp); 824ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 825ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner temp->Depth++; 826ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner temp->Min++; 827ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner NewFatherOcc->recomputeMin(); 828ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 829ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner rightmost->setLeft(NewFatherOcc); 830ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 831ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) { 832ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner rightmost->Min = NewFatherOcc->Min + rightmost->Depth; 833ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner rightmost->MinOccurrence = NewFatherOcc->MinOccurrence; 834ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 835ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 836bb636274d41596eac607368e4545c5d67e14816aChris Lattner delete ParentOcc; 837ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ParentOcc = NewFatherOcc; 838ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 839ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Update *our* tree 840ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETNode *left; 841ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETNode *right; 842ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 843ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Father = NewFather; 844ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right = Father->Son; 845ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 846ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (right) 847ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left = right->Left; 848ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner else 849ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left = right = this; 850ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 851ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left->Right = this; 852ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->Left = this; 853ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Left = left; 854ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Right = right; 855ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 856ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Father->Son = this; 857ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 858ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 859ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattnerbool ETNode::Below(ETNode *other) { 860ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *up = other->RightmostOcc; 861ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *down = RightmostOcc; 862ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 863ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (this == other) 864ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return true; 865ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 866ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner up->Splay(); 867ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 868ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *left, *right; 869ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left = up->Left; 870ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right = up->Right; 871ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 872ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (!left) 873ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return false; 874ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 875ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left->Parent = NULL; 876ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 877ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (right) 878ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->Parent = NULL; 879ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 880ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner down->Splay(); 881ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 882ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (left == down || left->Parent != NULL) { 883ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (right) 884ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->Parent = up; 885ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner up->setLeft(down); 886ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } else { 887ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left->Parent = up; 888ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 889ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // If the two occurrences are in different trees, put things 890ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // back the way they were. 891ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (right && right->Parent != NULL) 892ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner up->setRight(down); 893ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner else 894ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner up->setRight(right); 895ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return false; 896ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 897ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 898ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (down->Depth <= 0) 899ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return false; 900ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 901ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return !down->Right || down->Right->Min + down->Depth >= 0; 902ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 903ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 904ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris LattnerETNode *ETNode::NCA(ETNode *other) { 905ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *occ1 = RightmostOcc; 906ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *occ2 = other->RightmostOcc; 907ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 908ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *left, *right, *ret; 909ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETOccurrence *occmin; 910ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner int mindepth; 911ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 912ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (this == other) 913ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return this; 914ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 915ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner occ1->Splay(); 916ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left = occ1->Left; 917ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right = occ1->Right; 918ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 919ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (left) 920ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left->Parent = NULL; 921ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 922ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (right) 923ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->Parent = NULL; 924ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner occ2->Splay(); 925ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 926ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (left == occ2 || (left && left->Parent != NULL)) { 927ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ret = occ2->Right; 928ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 929ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner occ1->setLeft(occ2); 930ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (right) 931ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner right->Parent = occ1; 932ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } else { 933ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ret = occ2->Left; 934ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 935ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner occ1->setRight(occ2); 936ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (left) 937ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner left->Parent = occ1; 938ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 939ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 940ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (occ2->Depth > 0) { 941ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner occmin = occ1; 942ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner mindepth = occ1->Depth; 943ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } else { 944ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner occmin = occ2; 945ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner mindepth = occ2->Depth + occ1->Depth; 946ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 947ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 948ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth) 949ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return ret->MinOccurrence->OccFor; 950ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner else 951ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return occmin->OccFor; 952ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 953ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 9548d3ab25335d985665cbf69231811da9e58e27592Devang Patelvoid ETNode::assignDFSNumber(int num) { 9558d3ab25335d985665cbf69231811da9e58e27592Devang Patel std::vector<ETNode *> workStack; 9568d3ab25335d985665cbf69231811da9e58e27592Devang Patel std::set<ETNode *> visitedNodes; 9578d3ab25335d985665cbf69231811da9e58e27592Devang Patel 9588d3ab25335d985665cbf69231811da9e58e27592Devang Patel workStack.push_back(this); 9598d3ab25335d985665cbf69231811da9e58e27592Devang Patel visitedNodes.insert(this); 9608d3ab25335d985665cbf69231811da9e58e27592Devang Patel this->DFSNumIn = num++; 9618d3ab25335d985665cbf69231811da9e58e27592Devang Patel 9628d3ab25335d985665cbf69231811da9e58e27592Devang Patel while (!workStack.empty()) { 9638d3ab25335d985665cbf69231811da9e58e27592Devang Patel ETNode *Node = workStack.back(); 9648d3ab25335d985665cbf69231811da9e58e27592Devang Patel 9658d3ab25335d985665cbf69231811da9e58e27592Devang Patel // If this is leaf node then set DFSNumOut and pop the stack 9668d3ab25335d985665cbf69231811da9e58e27592Devang Patel if (!Node->Son) { 9678d3ab25335d985665cbf69231811da9e58e27592Devang Patel Node->DFSNumOut = num++; 9688d3ab25335d985665cbf69231811da9e58e27592Devang Patel workStack.pop_back(); 9698d3ab25335d985665cbf69231811da9e58e27592Devang Patel continue; 9708d3ab25335d985665cbf69231811da9e58e27592Devang Patel } 9718d3ab25335d985665cbf69231811da9e58e27592Devang Patel 9728d3ab25335d985665cbf69231811da9e58e27592Devang Patel ETNode *son = Node->Son; 9738d3ab25335d985665cbf69231811da9e58e27592Devang Patel 9748d3ab25335d985665cbf69231811da9e58e27592Devang Patel // Visit Node->Son first 9758d3ab25335d985665cbf69231811da9e58e27592Devang Patel if (visitedNodes.count(son) == 0) { 9768d3ab25335d985665cbf69231811da9e58e27592Devang Patel son->DFSNumIn = num++; 9778d3ab25335d985665cbf69231811da9e58e27592Devang Patel workStack.push_back(son); 9788d3ab25335d985665cbf69231811da9e58e27592Devang Patel visitedNodes.insert(son); 9798d3ab25335d985665cbf69231811da9e58e27592Devang Patel continue; 9808d3ab25335d985665cbf69231811da9e58e27592Devang Patel } 9818d3ab25335d985665cbf69231811da9e58e27592Devang Patel 9828d3ab25335d985665cbf69231811da9e58e27592Devang Patel bool visitChild = false; 9838d3ab25335d985665cbf69231811da9e58e27592Devang Patel // Visit remaining children 9848d3ab25335d985665cbf69231811da9e58e27592Devang Patel for (ETNode *s = son->Right; s != son && !visitChild; s = s->Right) { 9858d3ab25335d985665cbf69231811da9e58e27592Devang Patel if (visitedNodes.count(s) == 0) { 9868d3ab25335d985665cbf69231811da9e58e27592Devang Patel visitChild = true; 9878d3ab25335d985665cbf69231811da9e58e27592Devang Patel s->DFSNumIn = num++; 9888d3ab25335d985665cbf69231811da9e58e27592Devang Patel workStack.push_back(s); 989b71f6728eb4b3f0646da350d87eefc83ea35cf24Devang Patel visitedNodes.insert(s); 9908d3ab25335d985665cbf69231811da9e58e27592Devang Patel } 9918d3ab25335d985665cbf69231811da9e58e27592Devang Patel } 9928d3ab25335d985665cbf69231811da9e58e27592Devang Patel 9938d3ab25335d985665cbf69231811da9e58e27592Devang Patel if (!visitChild) { 9948d3ab25335d985665cbf69231811da9e58e27592Devang Patel // If we reach here means all children are visited 9958d3ab25335d985665cbf69231811da9e58e27592Devang Patel Node->DFSNumOut = num++; 9968d3ab25335d985665cbf69231811da9e58e27592Devang Patel workStack.pop_back(); 9978d3ab25335d985665cbf69231811da9e58e27592Devang Patel } 9988d3ab25335d985665cbf69231811da9e58e27592Devang Patel } 9998d3ab25335d985665cbf69231811da9e58e27592Devang Patel} 10008d3ab25335d985665cbf69231811da9e58e27592Devang Patel 1001ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 1002ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner// ETForest implementation 1003ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 1004ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 10051997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar ETForest::ID = 0; 10065d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattnerstatic RegisterPass<ETForest> 1007ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris LattnerD("etforest", "ET Forest Construction", true); 1008ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1009ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattnervoid ETForestBase::reset() { 1010ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) 1011ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner delete I->second; 1012ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Nodes.clear(); 1013ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 1014ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 101525abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattnervoid ETForestBase::updateDFSNumbers() 101625abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner{ 101725abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner int dfsnum = 0; 101825abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner // Iterate over all nodes in depth first order. 101925abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner for (unsigned i = 0, e = Roots.size(); i != e; ++i) 102025abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner for (df_iterator<BasicBlock*> I = df_begin(Roots[i]), 102125abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner E = df_end(Roots[i]); I != E; ++I) { 102225abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner BasicBlock *BB = *I; 102351bc779096f88ef52a12eaf07d6d1df5266007caNick Lewycky ETNode *ETN = getNode(BB); 102451bc779096f88ef52a12eaf07d6d1df5266007caNick Lewycky if (ETN && !ETN->hasFather()) 102551bc779096f88ef52a12eaf07d6d1df5266007caNick Lewycky ETN->assignDFSNumber(dfsnum); 102625abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner } 102725abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner SlowQueries = 0; 102825abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner DFSInfoValid = true; 102925abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner} 103025abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner 10313b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel// dominates - Return true if A dominates B. THis performs the 10323b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel// special checks necessary if A and B are in the same basic block. 10333b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patelbool ETForestBase::dominates(Instruction *A, Instruction *B) { 10343b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 10353b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel if (BBA != BBB) return dominates(BBA, BBB); 10363b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel 10379dea3a340a8e3db7eab92ea78c20e317ac4c2545Devang Patel // It is not possible to determine dominance between two PHI nodes 10389dea3a340a8e3db7eab92ea78c20e317ac4c2545Devang Patel // based on their ordering. 10399dea3a340a8e3db7eab92ea78c20e317ac4c2545Devang Patel if (isa<PHINode>(A) && isa<PHINode>(B)) 10409dea3a340a8e3db7eab92ea78c20e317ac4c2545Devang Patel return false; 10419dea3a340a8e3db7eab92ea78c20e317ac4c2545Devang Patel 1042690c684fc60883171c01da12d826fda6b5678aa8Owen Anderson // Loop through the basic block until we find A or B. 1043690c684fc60883171c01da12d826fda6b5678aa8Owen Anderson BasicBlock::iterator I = BBA->begin(); 1044690c684fc60883171c01da12d826fda6b5678aa8Owen Anderson for (; &*I != A && &*I != B; ++I) /*empty*/; 1045690c684fc60883171c01da12d826fda6b5678aa8Owen Anderson 10463b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel if(!IsPostDominators) { 10473b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel // A dominates B if it is found first in the basic block. 10483b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel return &*I == A; 10493b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel } else { 10503b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel // A post-dominates B if B is found first in the basic block. 10513b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel return &*I == B; 10523b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel } 10533b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel} 10543b57b6f36e906d69cc578f3e2f72dcd263a72a30Devang Patel 10558ea325730c6b914350008f1d8160345bfc4781d6Owen Anderson/// isReachableFromEntry - Return true if A is dominated by the entry 10568ea325730c6b914350008f1d8160345bfc4781d6Owen Anderson/// block of the function containing it. 10578ea325730c6b914350008f1d8160345bfc4781d6Owen Andersonconst bool ETForestBase::isReachableFromEntry(BasicBlock* A) { 10588ea325730c6b914350008f1d8160345bfc4781d6Owen Anderson return dominates(&A->getParent()->getEntryBlock(), A); 10598ea325730c6b914350008f1d8160345bfc4781d6Owen Anderson} 10608ea325730c6b914350008f1d8160345bfc4781d6Owen Anderson 1061055756bf52af37a4930c6023416537aad844e598Devang Patel// FIXME : There is no need to make getNodeForBlock public. Fix 1062055756bf52af37a4930c6023416537aad844e598Devang Patel// predicate simplifier. 1063ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris LattnerETNode *ETForest::getNodeForBlock(BasicBlock *BB) { 1064ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETNode *&BBNode = Nodes[BB]; 1065ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (BBNode) return BBNode; 1066ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1067ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Haven't calculated this node yet? Get or calculate the node for the 1068ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // immediate dominator. 106926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *node= getAnalysis<DominatorTree>().getNode(BB); 1070ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1071ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // If we are unreachable, we may not have an immediate dominator. 10729a341ff3c1cf54af7bda18726a0a30f3de4fa353Owen Anderson if (!node || !node->getIDom()) 1073ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return BBNode = new ETNode(BB); 1074ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner else { 10759a341ff3c1cf54af7bda18726a0a30f3de4fa353Owen Anderson ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock()); 1076ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1077ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Add a new tree node for this BasicBlock, and link it as a child of 1078ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // IDomNode 1079ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner BBNode = new ETNode(BB); 1080ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner BBNode->setFather(IDomNode); 1081ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return BBNode; 1082ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 1083ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 1084ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1085690c684fc60883171c01da12d826fda6b5678aa8Owen Andersonvoid ETForest::calculate(const DominatorTree &DT) { 1086ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner assert(Roots.size() == 1 && "ETForest should have 1 root block!"); 1087ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner BasicBlock *Root = Roots[0]; 1088ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Nodes[Root] = new ETNode(Root); // Add a node for the root 1089ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1090ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Function *F = Root->getParent(); 1091ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Loop over all of the reachable blocks in the function... 1092690c684fc60883171c01da12d826fda6b5678aa8Owen Anderson for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 109326042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode* node = DT.getNode(I); 1094690c684fc60883171c01da12d826fda6b5678aa8Owen Anderson if (node && node->getIDom()) { // Reachable block. 10959a341ff3c1cf54af7bda18726a0a30f3de4fa353Owen Anderson BasicBlock* ImmDom = node->getIDom()->getBlock(); 1096ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETNode *&BBNode = Nodes[I]; 1097ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (!BBNode) { // Haven't calculated this node yet? 1098ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Get or calculate the node for the immediate dominator 1099ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETNode *IDomNode = getNodeForBlock(ImmDom); 1100ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1101ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // Add a new ETNode for this BasicBlock, and set it's parent 1102ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner // to it's immediate dominator. 1103ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner BBNode = new ETNode(I); 1104ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner BBNode->setFather(IDomNode); 1105ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 1106ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 11079a341ff3c1cf54af7bda18726a0a30f3de4fa353Owen Anderson } 1108ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 110925abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner // Make sure we've got nodes around for every block 111025abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 111125abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner ETNode *&BBNode = Nodes[I]; 111225abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner if (!BBNode) 111325abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner BBNode = new ETNode(I); 1114ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 111525abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner 111625abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner updateDFSNumbers (); 1117ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 1118ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1119ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 1120ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner// ETForestBase Implementation 1121ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 1122ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1123ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattnervoid ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) { 1124ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETNode *&BBNode = Nodes[BB]; 1125ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner assert(!BBNode && "BasicBlock already in ET-Forest"); 1126ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1127ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner BBNode = new ETNode(BB); 1128ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner BBNode->setFather(getNode(IDom)); 1129ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner DFSInfoValid = false; 1130ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 1131ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1132ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattnervoid ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) { 1133ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner assert(getNode(BB) && "BasicBlock not in ET-Forest"); 1134ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner assert(getNode(newIDom) && "IDom not in ET-Forest"); 1135ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1136ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner ETNode *Node = getNode(BB); 1137ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (Node->hasFather()) { 1138ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (Node->getFather()->getData<BasicBlock>() == newIDom) 1139ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner return; 1140ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Node->Split(); 1141ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 1142ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Node->setFather(getNode(newIDom)); 1143ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner DFSInfoValid= false; 1144ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 1145ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1146ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattnervoid ETForestBase::print(std::ostream &o, const Module *) const { 1147ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "=============================--------------------------------\n"; 1148ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "ET Forest:\n"; 1149ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "DFS Info "; 1150ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (DFSInfoValid) 1151ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "is"; 1152ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner else 1153ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "is not"; 1154ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << " up to date\n"; 1155ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner 1156ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner Function *F = getRoots()[0]->getParent(); 1157ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 1158ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << " DFS Numbers For Basic Block:"; 1159ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner WriteAsOperand(o, I, false); 1160ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << " are:"; 1161ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner if (ETNode *EN = getNode(I)) { 1162ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "In: " << EN->getDFSNumIn(); 1163ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << " Out: " << EN->getDFSNumOut() << "\n"; 1164ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } else { 1165ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "No associated ETNode"; 1166ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 1167ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "\n"; 1168ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner } 1169ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner o << "\n"; 1170ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner} 117179b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel 117279b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patelvoid ETForestBase::dump() { 117379b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel print (llvm::cerr); 117479b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel} 1175