PostDominators.cpp revision cd7c2877307bc82fdda978dc6f97d4c608e77a80
14c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner//===- PostDominators.cpp - Post-Dominator Calculation --------------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 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. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 91715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 104c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// This file implements the post-dominator construction algorithms. 111715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 121715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 131715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 14a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#include "llvm/Analysis/PostDominators.h" 15706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner#include "llvm/iTerminators.h" 16221d688a5ef21a22c2368c9fff0e92d7966c95e5Chris Lattner#include "llvm/Support/CFG.h" 17cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner#include "Support/DepthFirstIterator.h" 18eb5230c4f98bd94c019bc2faed9432ca892e2f11Chris Lattner#include "Support/SetOperations.h" 19cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattnerusing namespace llvm; 20d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner//===----------------------------------------------------------------------===// 224c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// PostDominatorSet Implementation 2394108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner//===----------------------------------------------------------------------===// 2494108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 251e43516dcf4aa152432447397334cd43744d63e1Chris Lattnerstatic RegisterAnalysis<PostDominatorSet> 2617689dfe241702cbbbd29cf1e4e4229444f3e9f3Chris LattnerB("postdomset", "Post-Dominator Set Construction", true); 2794108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 28ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner// Postdominator set construction. This converts the specified function to only 29ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner// have a single exit node (return stmt), then calculates the post dominance 30ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner// sets for the function. 3194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner// 32ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattnerbool PostDominatorSet::runOnFunction(Function &F) { 33ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner Doms.clear(); // Reset from the last time we were run... 3494108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 35706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // Scan the function looking for the root nodes of the post-dominance 36706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // relationships. These blocks end with return and unwind instructions. 37706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // While we are iterating over the function, we also initialize all of the 38706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // domsets to empty. 39706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner Roots.clear(); 40706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 41706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner Doms[I]; // Initialize to empty 42706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 43706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (isa<ReturnInst>(I->getTerminator()) || 44706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner isa<UnwindInst>(I->getTerminator())) 45706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner Roots.push_back(I); 46384e5b1595fbc766552f2f2f74586d7b53519623Chris Lattner } 471715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 48706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // If there are no exit nodes for the function, postdomsets are all empty. 49706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // This can happen if the function just contains an infinite loop, for 50706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // example. 51706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (Roots.empty()) return false; 52706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 53706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // If we have more than one root, we insert an artificial "null" exit, which 54706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // has "virtual edges" to each of the real exit nodes. 55706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (Roots.size() > 1) 56706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner Doms[0].insert(0); 57706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 5894108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner bool Changed; 5994108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner do { 6094108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner Changed = false; 6194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 6250b5d71cb73144823dba1e0521f8ac2eab7dec66Chris Lattner std::set<BasicBlock*> Visited; 6394108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner DomSetType WorkingSet; 64706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 65706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner for (unsigned i = 0, e = Roots.size(); i != e; ++i) 6650b5d71cb73144823dba1e0521f8ac2eab7dec66Chris Lattner for (idf_ext_iterator<BasicBlock*> It = idf_ext_begin(Roots[i], Visited), 6750b5d71cb73144823dba1e0521f8ac2eab7dec66Chris Lattner E = idf_ext_end(Roots[i], Visited); It != E; ++It) { 68706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner BasicBlock *BB = *It; 69706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 70706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (SI != SE) { // Is there SOME successor? 71706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // Loop until we get to a successor that has had it's dom set filled 72706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // in at least once. We are guaranteed to have this because we are 73706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // traversing the graph in DFO and have handled start nodes specially. 74706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // 75706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner while (Doms[*SI].size() == 0) ++SI; 76706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner WorkingSet = Doms[*SI]; 77706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 78706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner for (++SI; SI != SE; ++SI) { // Intersect all of the successor sets 79706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner DomSetType &SuccSet = Doms[*SI]; 80706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (SuccSet.size()) 81706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner set_intersect(WorkingSet, SuccSet); 82706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner } 83706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner } else { 84706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // If this node has no successors, it must be one of the root nodes. 85706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // We will already take care of the notion that the node 86706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // post-dominates itself. The only thing we have to add is that if 87706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // there are multiple root nodes, we want to insert a special "null" 88706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // exit node which dominates the roots as well. 89706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (Roots.size() > 1) 90706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner WorkingSet.insert(0); 91706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner } 9294108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 93706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner WorkingSet.insert(BB); // A block always dominates itself 94706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner DomSetType &BBSet = Doms[BB]; 95706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (BBSet != WorkingSet) { 96706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner BBSet.swap(WorkingSet); // Constant time operation! 97706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner Changed = true; // The sets changed. 98706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner } 99706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner WorkingSet.clear(); // Clear out the set for next iteration 10094108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner } 10194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner } while (Changed); 102ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner return false; 1031715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner} 1041715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 1051715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 1064c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// ImmediatePostDominators Implementation 1071715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 1081715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 1091e43516dcf4aa152432447397334cd43744d63e1Chris Lattnerstatic RegisterAnalysis<ImmediatePostDominators> 11017689dfe241702cbbbd29cf1e4e4229444f3e9f3Chris LattnerD("postidom", "Immediate Post-Dominators Construction", true); 11193193f806378e06092820c099e437886c7309b94Chris Lattner 112cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner 113cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner// calcIDoms - Calculate the immediate dominator mapping, given a set of 114cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner// dominators for every basic block. 115cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattnervoid ImmediatePostDominators::calcIDoms(const DominatorSetBase &DS) { 116cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // Loop over all of the nodes that have dominators... figuring out the IDOM 117cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // for each node... 118cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // 119cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner for (DominatorSet::const_iterator DI = DS.begin(), DEnd = DS.end(); 120cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner DI != DEnd; ++DI) { 121cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner BasicBlock *BB = DI->first; 122cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner const DominatorSet::DomSetType &Dominators = DI->second; 123cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner unsigned DomSetSize = Dominators.size(); 124cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner if (DomSetSize == 1) continue; // Root node... IDom = null 125cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner 126cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // Loop over all dominators of this node. This corresponds to looping over 127cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // nodes in the dominator chain, looking for a node whose dominator set is 128cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // equal to the current nodes, except that the current node does not exist 129cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // in it. This means that it is one level higher in the dom chain than the 130cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // current node, and it is our idom! 131cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // 132cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner DominatorSet::DomSetType::const_iterator I = Dominators.begin(); 133cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner DominatorSet::DomSetType::const_iterator End = Dominators.end(); 134cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner for (; I != End; ++I) { // Iterate over dominators... 135cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // All of our dominators should form a chain, where the number of elements 136cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // in the dominator set indicates what level the node is at in the chain. 137cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // We want the node immediately above us, so it will have an identical 138cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // dominator set, except that BB will not dominate it... therefore it's 139cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // dominator set size will be one less than BB's... 140cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner // 141cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner if (DS.getDominators(*I).size() == DomSetSize - 1) { 142cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner IDoms[BB] = *I; 143cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner break; 144cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner } 145cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner } 146cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner } 147cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner} 148cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattner 1491715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 1504c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// PostDominatorTree Implementation 1511715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 1521715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 1531e43516dcf4aa152432447397334cd43744d63e1Chris Lattnerstatic RegisterAnalysis<PostDominatorTree> 15417689dfe241702cbbbd29cf1e4e4229444f3e9f3Chris LattnerF("postdomtree", "Post-Dominator Tree Construction", true); 15593193f806378e06092820c099e437886c7309b94Chris Lattner 156ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattnervoid PostDominatorTree::calculate(const PostDominatorSet &DS) { 157706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (Roots.empty()) return; 158706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0; 159706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 160706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root... 1611715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 162706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // Iterate over all nodes in depth first order... 163706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner for (unsigned i = 0, e = Roots.size(); i != e; ++i) 164706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]), 165706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner E = idf_end(Roots[i]); I != E; ++I) { 166a298d27808ecb8ffb574d6e50f56601db2ec5fdaChris Lattner BasicBlock *BB = *I; 16794108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); 16894108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner unsigned DomSetSize = Dominators.size(); 16994108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner if (DomSetSize == 1) continue; // Root node... IDom = null 170706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 171706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // If we have already computed the immediate dominator for this node, 172706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // don't revisit. This can happen due to nodes reachable from multiple 173706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // roots, but which the idf_iterator doesn't know about. 174706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (Nodes.find(BB) != Nodes.end()) continue; 175706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 1763ff4387113d7e74a8aa73f80c3518cb95f09a64bChris Lattner // Loop over all dominators of this node. This corresponds to looping 1773ff4387113d7e74a8aa73f80c3518cb95f09a64bChris Lattner // over nodes in the dominator chain, looking for a node whose dominator 1783ff4387113d7e74a8aa73f80c3518cb95f09a64bChris Lattner // set is equal to the current nodes, except that the current node does 1793ff4387113d7e74a8aa73f80c3518cb95f09a64bChris Lattner // not exist in it. This means that it is one level higher in the dom 1803ff4387113d7e74a8aa73f80c3518cb95f09a64bChris Lattner // chain than the current node, and it is our idom! We know that we have 1813ff4387113d7e74a8aa73f80c3518cb95f09a64bChris Lattner // already added a DominatorTree node for our idom, because the idom must 1823ff4387113d7e74a8aa73f80c3518cb95f09a64bChris Lattner // be a predecessor in the depth first order that we are iterating through 1832fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner // the function. 18494108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // 18594108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner DominatorSet::DomSetType::const_iterator I = Dominators.begin(); 18694108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner DominatorSet::DomSetType::const_iterator End = Dominators.end(); 18794108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner for (; I != End; ++I) { // Iterate over dominators... 188706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // All of our dominators should form a chain, where the number 189706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // of elements in the dominator set indicates what level the 190706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // node is at in the chain. We want the node immediately 191706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // above us, so it will have an identical dominator set, 192706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // except that BB will not dominate it... therefore it's 193706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // dominator set size will be one less than BB's... 194706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // 195706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (DS.getDominators(*I).size() == DomSetSize - 1) { 196706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // We know that the immediate dominator should already have a node, 197706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // because we are traversing the CFG in depth first order! 198706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // 199706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner Node *IDomNode = Nodes[*I]; 200706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner assert(IDomNode && "No node for IDOM?"); 20194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 202706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // Add a new tree node for this BasicBlock, and link it as a child of 203706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner // IDomNode 204706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 205706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner break; 206706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner } 2071715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner } 2081715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner } 2091715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner} 2101715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 2111715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 2124c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// PostDominanceFrontier Implementation 2131715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 2141715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 2151e43516dcf4aa152432447397334cd43744d63e1Chris Lattnerstatic RegisterAnalysis<PostDominanceFrontier> 21617689dfe241702cbbbd29cf1e4e4229444f3e9f3Chris LattnerH("postdomfrontier", "Post-Dominance Frontier Construction", true); 21793193f806378e06092820c099e437886c7309b94Chris Lattner 2181b7f7dc4b45a900fae2e9b062d588a995935727aChris Lattnerconst DominanceFrontier::DomSetType & 219ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris LattnerPostDominanceFrontier::calculate(const PostDominatorTree &DT, 220ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner const DominatorTree::Node *Node) { 22194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // Loop over CFG successors to calculate DFlocal[Node] 222c444a4228f31656f854d15eac671b450df557346Chris Lattner BasicBlock *BB = Node->getBlock(); 22394108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner DomSetType &S = Frontiers[BB]; // The new set to fill in... 224706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (getRoots().empty()) return S; 225706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 226706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (BB) 227706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); 228706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner SI != SE; ++SI) 2292f2d06506c9167dada05b11debe717334de972d4Misha Brukman // Does Node immediately dominate this predecessor? 230706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (DT[*SI]->getIDom() != Node) 231706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner S.insert(*SI); 23294108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 23394108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // At this point, S is DFlocal. Now we union in DFup's of our children... 23494108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // Loop through and visit the nodes that Node immediately dominates (Node's 23594108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // children in the IDomTree) 23694108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // 237ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner for (PostDominatorTree::Node::const_iterator 238ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { 23994108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner DominatorTree::Node *IDominee = *NI; 240ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner const DomSetType &ChildDF = calculate(DT, IDominee); 24194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 24294108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 24394108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner for (; CDFI != CDFE; ++CDFI) { 24494108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner if (!Node->dominates(DT[*CDFI])) 24594108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner S.insert(*CDFI); 24694108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner } 24794108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner } 24894108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 24994108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner return S; 25094108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner} 251a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 252a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner// stub - a dummy function to make linking work ok. 253a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattnervoid PostDominanceFrontier::stub() { 254a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner} 255d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 256