Cameron Zwarich | 4676599 | 2011-01-18 06:06:27 +0000 | [diff] [blame] | 1 | //===- DominanceFrontier.cpp - Dominance Frontier 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 | #include "llvm/Analysis/DominanceFrontier.h" |
| 11 | #include "llvm/Support/Debug.h" |
| 12 | #include "llvm/ADT/SmallPtrSet.h" |
| 13 | #include "llvm/Assembly/Writer.h" |
| 14 | #include "llvm/Support/raw_ostream.h" |
| 15 | using namespace llvm; |
| 16 | |
| 17 | char DominanceFrontier::ID = 0; |
| 18 | INITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier", |
| 19 | "Dominance Frontier Construction", true, true) |
| 20 | INITIALIZE_PASS_DEPENDENCY(DominatorTree) |
| 21 | INITIALIZE_PASS_END(DominanceFrontier, "domfrontier", |
| 22 | "Dominance Frontier Construction", true, true) |
| 23 | |
| 24 | namespace { |
| 25 | class DFCalculateWorkObject { |
| 26 | public: |
| 27 | DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, |
| 28 | const DomTreeNode *N, |
| 29 | const DomTreeNode *PN) |
| 30 | : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} |
| 31 | BasicBlock *currentBB; |
| 32 | BasicBlock *parentBB; |
| 33 | const DomTreeNode *Node; |
| 34 | const DomTreeNode *parentNode; |
| 35 | }; |
| 36 | } |
| 37 | |
| 38 | const DominanceFrontier::DomSetType & |
| 39 | DominanceFrontier::calculate(const DominatorTree &DT, |
| 40 | const DomTreeNode *Node) { |
| 41 | BasicBlock *BB = Node->getBlock(); |
| 42 | DomSetType *Result = NULL; |
| 43 | |
| 44 | std::vector<DFCalculateWorkObject> workList; |
| 45 | SmallPtrSet<BasicBlock *, 32> visited; |
| 46 | |
| 47 | workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); |
| 48 | do { |
| 49 | DFCalculateWorkObject *currentW = &workList.back(); |
| 50 | assert (currentW && "Missing work object."); |
| 51 | |
| 52 | BasicBlock *currentBB = currentW->currentBB; |
| 53 | BasicBlock *parentBB = currentW->parentBB; |
| 54 | const DomTreeNode *currentNode = currentW->Node; |
| 55 | const DomTreeNode *parentNode = currentW->parentNode; |
| 56 | assert (currentBB && "Invalid work object. Missing current Basic Block"); |
| 57 | assert (currentNode && "Invalid work object. Missing current Node"); |
| 58 | DomSetType &S = Frontiers[currentBB]; |
| 59 | |
| 60 | // Visit each block only once. |
| 61 | if (visited.count(currentBB) == 0) { |
| 62 | visited.insert(currentBB); |
| 63 | |
| 64 | // Loop over CFG successors to calculate DFlocal[currentNode] |
| 65 | for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); |
| 66 | SI != SE; ++SI) { |
| 67 | // Does Node immediately dominate this successor? |
| 68 | if (DT[*SI]->getIDom() != currentNode) |
| 69 | S.insert(*SI); |
| 70 | } |
| 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 | bool visitChild = false; |
| 77 | for (DomTreeNode::const_iterator NI = currentNode->begin(), |
| 78 | NE = currentNode->end(); NI != NE; ++NI) { |
| 79 | DomTreeNode *IDominee = *NI; |
| 80 | BasicBlock *childBB = IDominee->getBlock(); |
| 81 | if (visited.count(childBB) == 0) { |
| 82 | workList.push_back(DFCalculateWorkObject(childBB, currentBB, |
| 83 | IDominee, currentNode)); |
| 84 | visitChild = true; |
| 85 | } |
| 86 | } |
| 87 | |
| 88 | // If all children are visited or there is any child then pop this block |
| 89 | // from the workList. |
| 90 | if (!visitChild) { |
| 91 | |
| 92 | if (!parentBB) { |
| 93 | Result = &S; |
| 94 | break; |
| 95 | } |
| 96 | |
| 97 | DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); |
| 98 | DomSetType &parentSet = Frontiers[parentBB]; |
| 99 | for (; CDFI != CDFE; ++CDFI) { |
| 100 | if (!DT.properlyDominates(parentNode, DT[*CDFI])) |
| 101 | parentSet.insert(*CDFI); |
| 102 | } |
| 103 | workList.pop_back(); |
| 104 | } |
| 105 | |
| 106 | } while (!workList.empty()); |
| 107 | |
| 108 | return *Result; |
| 109 | } |
| 110 | |
| 111 | void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { |
| 112 | for (const_iterator I = begin(), E = end(); I != E; ++I) { |
| 113 | OS << " DomFrontier for BB "; |
| 114 | if (I->first) |
| 115 | WriteAsOperand(OS, I->first, false); |
| 116 | else |
| 117 | OS << " <<exit node>>"; |
| 118 | OS << " is:\t"; |
| 119 | |
| 120 | const std::set<BasicBlock*> &BBs = I->second; |
| 121 | |
| 122 | for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); |
| 123 | I != E; ++I) { |
| 124 | OS << ' '; |
| 125 | if (*I) |
| 126 | WriteAsOperand(OS, *I, false); |
| 127 | else |
| 128 | OS << "<<exit node>>"; |
| 129 | } |
| 130 | OS << "\n"; |
| 131 | } |
| 132 | } |
| 133 | |
| 134 | void DominanceFrontierBase::dump() const { |
| 135 | print(dbgs()); |
| 136 | } |
| 137 | |