1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This is the generic implementation of the DominanceFrontier class, which
11 // calculate and holds the dominance frontier for a function for.
13 // This should be considered deprecated, don't add any more uses of this data
16 //===----------------------------------------------------------------------===//
18 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
19 #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/Support/Debug.h"
27 template <class BlockT>
28 class DFCalculateWorkObject {
30 typedef DomTreeNodeBase<BlockT> DomTreeNodeT;
32 DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
33 const DomTreeNodeT *PN)
34 : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
37 const DomTreeNodeT *Node;
38 const DomTreeNodeT *parentNode;
42 template <class BlockT>
43 void DominanceFrontierBase<BlockT>::removeBlock(BlockT *BB) {
44 assert(find(BB) != end() && "Block is not in DominanceFrontier!");
45 for (iterator I = begin(), E = end(); I != E; ++I)
50 template <class BlockT>
51 void DominanceFrontierBase<BlockT>::addToFrontier(iterator I,
53 assert(I != end() && "BB is not in DominanceFrontier!");
54 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
55 I->second.erase(Node);
58 template <class BlockT>
59 void DominanceFrontierBase<BlockT>::removeFromFrontier(iterator I,
61 assert(I != end() && "BB is not in DominanceFrontier!");
62 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
63 I->second.erase(Node);
66 template <class BlockT>
67 bool DominanceFrontierBase<BlockT>::compareDomSet(DomSetType &DS1,
68 const DomSetType &DS2) const {
69 std::set<BlockT *> tmpSet;
70 for (BlockT *BB : DS2)
73 for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
77 if (tmpSet.erase(Node) == 0)
78 // Node is in DS1 but tnot in DS2.
82 if (!tmpSet.empty()) {
83 // There are nodes that are in DS2 but not in DS1.
87 // DS1 and DS2 matches.
91 template <class BlockT>
92 bool DominanceFrontierBase<BlockT>::compare(
93 DominanceFrontierBase<BlockT> &Other) const {
94 DomSetMapType tmpFrontiers;
95 for (typename DomSetMapType::const_iterator I = Other.begin(),
98 tmpFrontiers.insert(std::make_pair(I->first, I->second));
100 for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
101 E = tmpFrontiers.end();
103 BlockT *Node = I->first;
104 const_iterator DFI = find(Node);
108 if (compareDomSet(I->second, DFI->second))
112 tmpFrontiers.erase(Node);
115 if (!tmpFrontiers.empty())
121 template <class BlockT>
122 void DominanceFrontierBase<BlockT>::print(raw_ostream &OS) const {
123 for (const_iterator I = begin(), E = end(); I != E; ++I) {
124 OS << " DomFrontier for BB ";
126 I->first->printAsOperand(OS, false);
128 OS << " <<exit node>>";
131 const std::set<BlockT *> &BBs = I->second;
133 for (const BlockT *BB : BBs) {
136 BB->printAsOperand(OS, false);
138 OS << "<<exit node>>";
144 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
145 template <class BlockT>
146 void DominanceFrontierBase<BlockT>::dump() const {
151 template <class BlockT>
152 const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
153 ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
154 const DomTreeNodeT *Node) {
155 BlockT *BB = Node->getBlock();
156 DomSetType *Result = nullptr;
158 std::vector<DFCalculateWorkObject<BlockT>> workList;
159 SmallPtrSet<BlockT *, 32> visited;
161 workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
163 DFCalculateWorkObject<BlockT> *currentW = &workList.back();
164 assert(currentW && "Missing work object.");
166 BlockT *currentBB = currentW->currentBB;
167 BlockT *parentBB = currentW->parentBB;
168 const DomTreeNodeT *currentNode = currentW->Node;
169 const DomTreeNodeT *parentNode = currentW->parentNode;
170 assert(currentBB && "Invalid work object. Missing current Basic Block");
171 assert(currentNode && "Invalid work object. Missing current Node");
172 DomSetType &S = this->Frontiers[currentBB];
174 // Visit each block only once.
175 if (visited.count(currentBB) == 0) {
176 visited.insert(currentBB);
178 // Loop over CFG successors to calculate DFlocal[currentNode]
179 for (auto SI = BlockTraits::child_begin(currentBB),
180 SE = BlockTraits::child_end(currentBB);
182 // Does Node immediately dominate this successor?
183 if (DT[*SI]->getIDom() != currentNode)
188 // At this point, S is DFlocal. Now we union in DFup's of our children...
189 // Loop through and visit the nodes that Node immediately dominates (Node's
190 // children in the IDomTree)
191 bool visitChild = false;
192 for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
193 NE = currentNode->end();
195 DomTreeNodeT *IDominee = *NI;
196 BlockT *childBB = IDominee->getBlock();
197 if (visited.count(childBB) == 0) {
198 workList.push_back(DFCalculateWorkObject<BlockT>(
199 childBB, currentBB, IDominee, currentNode));
204 // If all children are visited or there is any child then pop this block
205 // from the workList.
212 typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
213 DomSetType &parentSet = this->Frontiers[parentBB];
214 for (; CDFI != CDFE; ++CDFI) {
215 if (!DT.properlyDominates(parentNode, DT[*CDFI]))
216 parentSet.insert(*CDFI);
221 } while (!workList.empty());
226 } // End llvm namespace