PostDominators.cpp revision 9491195710811cfe2413bbcd04bce2ed56ea121a
1//===- PostDominators.cpp - Post-Dominator Calculation --------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the post-dominator construction algorithms. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "postdomtree" 15 16#include "llvm/Analysis/PostDominators.h" 17#include "llvm/Instructions.h" 18#include "llvm/Support/CFG.h" 19#include "llvm/Support/Debug.h" 20#include "llvm/ADT/DepthFirstIterator.h" 21#include "llvm/ADT/SetOperations.h" 22#include "llvm/Analysis/DominatorInternals.h" 23using namespace llvm; 24 25//===----------------------------------------------------------------------===// 26// PostDominatorTree Implementation 27//===----------------------------------------------------------------------===// 28 29char PostDominatorTree::ID = 0; 30char PostDominanceFrontier::ID = 0; 31static RegisterPass<PostDominatorTree> 32F("postdomtree", "Post-Dominator Tree Construction", true, true); 33 34bool PostDominatorTree::runOnFunction(Function &F) { 35 DT->recalculate(F); 36 DEBUG(DT->dump()); 37 return false; 38} 39 40PostDominatorTree::~PostDominatorTree() 41{ 42 delete DT; 43} 44 45FunctionPass* llvm::createPostDomTree() { 46 return new PostDominatorTree(); 47} 48 49//===----------------------------------------------------------------------===// 50// PostDominanceFrontier Implementation 51//===----------------------------------------------------------------------===// 52 53static RegisterPass<PostDominanceFrontier> 54H("postdomfrontier", "Post-Dominance Frontier Construction", true, true); 55 56const DominanceFrontier::DomSetType & 57PostDominanceFrontier::calculate(const PostDominatorTree &DT, 58 const DomTreeNode *Node) { 59 // Loop over CFG successors to calculate DFlocal[Node] 60 BasicBlock *BB = Node->getBlock(); 61 DomSetType &S = Frontiers[BB]; // The new set to fill in... 62 if (getRoots().empty()) return S; 63 64 if (BB) 65 for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); 66 SI != SE; ++SI) { 67 // Does Node immediately dominate this predecessor? 68 DomTreeNode *SINode = DT[*SI]; 69 if (SINode && SINode->getIDom() != Node) 70 S.insert(*SI); 71 } 72 73 // At this point, S is DFlocal. Now we union in DFup's of our children... 74 // Loop through and visit the nodes that Node immediately dominates (Node's 75 // children in the IDomTree) 76 // 77 for (DomTreeNode::const_iterator 78 NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { 79 DomTreeNode *IDominee = *NI; 80 const DomSetType &ChildDF = calculate(DT, IDominee); 81 82 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 83 for (; CDFI != CDFE; ++CDFI) { 84 if (!DT.properlyDominates(Node, DT[*CDFI])) 85 S.insert(*CDFI); 86 } 87 } 88 89 return S; 90} 91 92FunctionPass* llvm::createPostDomFrontier() { 93 return new PostDominanceFrontier(); 94} 95