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:
DFCalculateWorkObject(BasicBlock * B,BasicBlock * P,const DomTreeNode * N,const DomTreeNode * PN)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
anchor()38 void DominanceFrontier::anchor() { }
39
40 const DominanceFrontier::DomSetType &
calculate(const DominatorTree & DT,const DomTreeNode * Node)41 DominanceFrontier::calculate(const DominatorTree &DT,
42 const DomTreeNode *Node) {
43 BasicBlock *BB = Node->getBlock();
44 DomSetType *Result = NULL;
45
46 std::vector<DFCalculateWorkObject> workList;
47 SmallPtrSet<BasicBlock *, 32> visited;
48
49 workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
50 do {
51 DFCalculateWorkObject *currentW = &workList.back();
52 assert (currentW && "Missing work object.");
53
54 BasicBlock *currentBB = currentW->currentBB;
55 BasicBlock *parentBB = currentW->parentBB;
56 const DomTreeNode *currentNode = currentW->Node;
57 const DomTreeNode *parentNode = currentW->parentNode;
58 assert (currentBB && "Invalid work object. Missing current Basic Block");
59 assert (currentNode && "Invalid work object. Missing current Node");
60 DomSetType &S = Frontiers[currentBB];
61
62 // Visit each block only once.
63 if (visited.count(currentBB) == 0) {
64 visited.insert(currentBB);
65
66 // Loop over CFG successors to calculate DFlocal[currentNode]
67 for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
68 SI != SE; ++SI) {
69 // Does Node immediately dominate this successor?
70 if (DT[*SI]->getIDom() != currentNode)
71 S.insert(*SI);
72 }
73 }
74
75 // At this point, S is DFlocal. Now we union in DFup's of our children...
76 // Loop through and visit the nodes that Node immediately dominates (Node's
77 // children in the IDomTree)
78 bool visitChild = false;
79 for (DomTreeNode::const_iterator NI = currentNode->begin(),
80 NE = currentNode->end(); NI != NE; ++NI) {
81 DomTreeNode *IDominee = *NI;
82 BasicBlock *childBB = IDominee->getBlock();
83 if (visited.count(childBB) == 0) {
84 workList.push_back(DFCalculateWorkObject(childBB, currentBB,
85 IDominee, currentNode));
86 visitChild = true;
87 }
88 }
89
90 // If all children are visited or there is any child then pop this block
91 // from the workList.
92 if (!visitChild) {
93
94 if (!parentBB) {
95 Result = &S;
96 break;
97 }
98
99 DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
100 DomSetType &parentSet = Frontiers[parentBB];
101 for (; CDFI != CDFE; ++CDFI) {
102 if (!DT.properlyDominates(parentNode, DT[*CDFI]))
103 parentSet.insert(*CDFI);
104 }
105 workList.pop_back();
106 }
107
108 } while (!workList.empty());
109
110 return *Result;
111 }
112
print(raw_ostream & OS,const Module *) const113 void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const {
114 for (const_iterator I = begin(), E = end(); I != E; ++I) {
115 OS << " DomFrontier for BB ";
116 if (I->first)
117 WriteAsOperand(OS, I->first, false);
118 else
119 OS << " <<exit node>>";
120 OS << " is:\t";
121
122 const std::set<BasicBlock*> &BBs = I->second;
123
124 for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
125 I != E; ++I) {
126 OS << ' ';
127 if (*I)
128 WriteAsOperand(OS, *I, false);
129 else
130 OS << "<<exit node>>";
131 }
132 OS << "\n";
133 }
134 }
135
136 #ifndef NDEBUG
dump() const137 void DominanceFrontierBase::dump() const {
138 print(dbgs());
139 }
140 #endif
141
142