1 //==- Dominators.cpp - Construct the Dominance Tree Given CFG ----*- C++ --*-==// 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 a simple, fast dominance algorithm for source-level CFGs. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/Analysis/Analyses/Dominators.h" 15 #include "clang/Analysis/CFG.h" 16 #include "clang/Analysis/AnalysisContext.h" 17 #include "clang/Analysis/Analyses/PostOrderCFGView.h" 18 19 using namespace clang; 20 21 DominatorTree::~DominatorTree() { 22 IDoms.clear(); 23 RootNode = 0; 24 } 25 26 CFGBlock * DominatorTree::getNode(const CFGBlock *B) const { 27 CFGBlockMapTy::const_iterator I = IDoms.find(B); 28 return I != IDoms.end() ? I->second : 0; 29 } 30 31 bool DominatorTree::properlyDominates(const CFGBlock *A, 32 const CFGBlock *B) const { 33 if (0 == A || 0 == B || A == B) 34 return false; 35 36 // The EntryBlock dominates every other block. 37 if (A == RootNode) 38 return true; 39 40 // Note: The dominator of the EntryBlock is itself. 41 CFGBlock *IDom = getNode(B); 42 while (IDom != A && IDom != RootNode) 43 IDom = getNode(IDom); 44 45 return IDom != RootNode; 46 } 47 48 bool DominatorTree::dominates(const CFGBlock *A, 49 const CFGBlock *B) const { 50 if (A == B) 51 return true; 52 53 return properlyDominates(A, B); 54 } 55 56 const CFGBlock * DominatorTree::findNearestCommonDominator 57 (const CFGBlock *A, const CFGBlock *B) const { 58 //If A dominates B, then A is the nearest common dominator 59 if (dominates(A, B)) 60 return A; 61 62 //If B dominates A, then B is the nearest common dominator 63 if (dominates(B, A)) 64 return B; 65 66 //Collect all A's dominators 67 llvm::SmallPtrSet<CFGBlock *, 16> ADoms; 68 ADoms.insert(RootNode); 69 CFGBlock *ADom = getNode(A); 70 while (ADom != RootNode) { 71 ADoms.insert(ADom); 72 ADom = getNode(ADom); 73 } 74 75 //Check all B's dominators against ADoms 76 CFGBlock *BDom = getNode(B); 77 while (BDom != RootNode){ 78 if (ADoms.count(BDom) != 0) 79 return BDom; 80 81 BDom = getNode(BDom); 82 } 83 84 //The RootNode dominates every other node 85 return RootNode; 86 } 87 88 /// Constructs immediate dominator tree for a given CFG based on the algorithm 89 /// described in this paper: 90 /// 91 /// A Simple, Fast Dominance Algorithm 92 /// Keith D. Cooper, Timothy J. Harvey and Ken Kennedy 93 /// Software-Practice and Expreience, 2001;4:1-10. 94 /// 95 /// This implementation is simple and runs faster in practice than the classis 96 /// Lengauer-Tarjan algorithm. For detailed discussions, refer to the paper. 97 void DominatorTree::BuildDominatorTree() { 98 CFG *cfg = AC.getCFG(); 99 CFGBlock *EntryBlk = &cfg->getEntry(); 100 101 //Sort all CFGBlocks in reverse order 102 PostOrderCFGView *rpocfg = AC.getAnalysis<PostOrderCFGView>(); 103 104 //Set the root of the dominance tree 105 RootNode = EntryBlk; 106 107 //Compute the immediate dominator for each CFGBlock 108 IDoms[EntryBlk] = EntryBlk; 109 bool changed = true; 110 while (changed){ 111 changed = false; 112 113 for (PostOrderCFGView::iterator I = rpocfg->begin(), 114 E = rpocfg->end(); I != E; ++I){ 115 if (EntryBlk == *I) 116 continue; 117 if (const CFGBlock *B = *I) { 118 //Compute immediate dominance information for CFGBlock B 119 CFGBlock *IDom = 0; 120 for (CFGBlock::const_pred_iterator J = B->pred_begin(), 121 K = B->pred_end(); J != K; ++J) 122 if( CFGBlock *P = *J) { 123 if (IDoms.find(P) == IDoms.end()) 124 continue; 125 if (!IDom) 126 IDom = P; 127 else { 128 //intersect IDom and P 129 CFGBlock *B1 = IDom, *B2 = P; 130 while (B1 != B2) { 131 while ((rpocfg->getComparator())(B2,B1)) 132 B1 = IDoms[B1]; 133 while ((rpocfg->getComparator())(B1,B2)) 134 B2 = IDoms[B2]; 135 } 136 IDom = B1; 137 } 138 } 139 if (IDoms[B] != IDom) { 140 IDoms[B] = IDom; 141 changed = true; 142 } 143 } 144 } 145 }//while 146 } 147 148 void DominatorTree::dump() { 149 CFG *cfg = AC.getCFG(); 150 151 llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n"; 152 for (CFG::const_iterator I = cfg->begin(), 153 E = cfg->end(); I != E; ++I) { 154 assert(IDoms[(*I)] && 155 "Failed to find the immediate dominator for all CFG blocks."); 156 llvm::errs() << "(" << (*I)->getBlockID() 157 << "," << IDoms[(*I)]->getBlockID() << ")\n"; 158 } 159 } 160 161