1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This is the generic implementation of the DominanceFrontier class, which
10 // calculate and holds the dominance frontier for a function for.
11 //
12 // This should be considered deprecated, don't add any more uses of this data
13 // structure.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
18 #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
19 
20 #include "llvm/ADT/GraphTraits.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/Analysis/DominanceFrontier.h"
23 #include "llvm/Config/llvm-config.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/GenericDomTree.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include <cassert>
28 #include <set>
29 #include <utility>
30 #include <vector>
31 
32 namespace llvm {
33 
34 template <class BlockT>
35 class DFCalculateWorkObject {
36 public:
37   using DomTreeNodeT = DomTreeNodeBase<BlockT>;
38 
39   DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
40                         const DomTreeNodeT *PN)
41       : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
42 
43   BlockT *currentBB;
44   BlockT *parentBB;
45   const DomTreeNodeT *Node;
46   const DomTreeNodeT *parentNode;
47 };
48 
49 template <class BlockT, bool IsPostDom>
50 void DominanceFrontierBase<BlockT, IsPostDom>::removeBlock(BlockT *BB) {
51   assert(find(BB) != end() && "Block is not in DominanceFrontier!");
52   for (iterator I = begin(), E = end(); I != E; ++I)
53     I->second.erase(BB);
54   Frontiers.erase(BB);
55 }
56 
57 template <class BlockT, bool IsPostDom>
58 void DominanceFrontierBase<BlockT, IsPostDom>::addToFrontier(iterator I,
59                                                              BlockT *Node) {
60   assert(I != end() && "BB is not in DominanceFrontier!");
61   assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
62   I->second.erase(Node);
63 }
64 
65 template <class BlockT, bool IsPostDom>
66 void DominanceFrontierBase<BlockT, IsPostDom>::removeFromFrontier(
67     iterator I, BlockT *Node) {
68   assert(I != end() && "BB is not in DominanceFrontier!");
69   assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
70   I->second.erase(Node);
71 }
72 
73 template <class BlockT, bool IsPostDom>
74 bool DominanceFrontierBase<BlockT, IsPostDom>::compareDomSet(
75     DomSetType &DS1, const DomSetType &DS2) const {
76   std::set<BlockT *> tmpSet;
77   for (BlockT *BB : DS2)
78     tmpSet.insert(BB);
79 
80   for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
81        I != E;) {
82     BlockT *Node = *I++;
83 
84     if (tmpSet.erase(Node) == 0)
85       // Node is in DS1 but tnot in DS2.
86       return true;
87   }
88 
89   if (!tmpSet.empty()) {
90     // There are nodes that are in DS2 but not in DS1.
91     return true;
92   }
93 
94   // DS1 and DS2 matches.
95   return false;
96 }
97 
98 template <class BlockT, bool IsPostDom>
99 bool DominanceFrontierBase<BlockT, IsPostDom>::compare(
100     DominanceFrontierBase<BlockT, IsPostDom> &Other) const {
101   DomSetMapType tmpFrontiers;
102   for (typename DomSetMapType::const_iterator I = Other.begin(),
103                                               E = Other.end();
104        I != E; ++I)
105     tmpFrontiers.insert(std::make_pair(I->first, I->second));
106 
107   for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
108                                         E = tmpFrontiers.end();
109        I != E;) {
110     BlockT *Node = I->first;
111     const_iterator DFI = find(Node);
112     if (DFI == end())
113       return true;
114 
115     if (compareDomSet(I->second, DFI->second))
116       return true;
117 
118     ++I;
119     tmpFrontiers.erase(Node);
120   }
121 
122   if (!tmpFrontiers.empty())
123     return true;
124 
125   return false;
126 }
127 
128 template <class BlockT, bool IsPostDom>
129 void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {
130   for (const_iterator I = begin(), E = end(); I != E; ++I) {
131     OS << "  DomFrontier for BB ";
132     if (I->first)
133       I->first->printAsOperand(OS, false);
134     else
135       OS << " <<exit node>>";
136     OS << " is:\t";
137 
138     const std::set<BlockT *> &BBs = I->second;
139 
140     for (const BlockT *BB : BBs) {
141       OS << ' ';
142       if (BB)
143         BB->printAsOperand(OS, false);
144       else
145         OS << "<<exit node>>";
146     }
147     OS << '\n';
148   }
149 }
150 
151 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
152 template <class BlockT, bool IsPostDom>
153 void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
154   print(dbgs());
155 }
156 #endif
157 
158 template <class BlockT>
159 const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
160 ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
161                                                 const DomTreeNodeT *Node) {
162   BlockT *BB = Node->getBlock();
163   DomSetType *Result = nullptr;
164 
165   std::vector<DFCalculateWorkObject<BlockT>> workList;
166   SmallPtrSet<BlockT *, 32> visited;
167 
168   workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
169   do {
170     DFCalculateWorkObject<BlockT> *currentW = &workList.back();
171     assert(currentW && "Missing work object.");
172 
173     BlockT *currentBB = currentW->currentBB;
174     BlockT *parentBB = currentW->parentBB;
175     const DomTreeNodeT *currentNode = currentW->Node;
176     const DomTreeNodeT *parentNode = currentW->parentNode;
177     assert(currentBB && "Invalid work object. Missing current Basic Block");
178     assert(currentNode && "Invalid work object. Missing current Node");
179     DomSetType &S = this->Frontiers[currentBB];
180 
181     // Visit each block only once.
182     if (visited.insert(currentBB).second) {
183       // Loop over CFG successors to calculate DFlocal[currentNode]
184       for (const auto Succ : children<BlockT *>(currentBB)) {
185         // Does Node immediately dominate this successor?
186         if (DT[Succ]->getIDom() != currentNode)
187           S.insert(Succ);
188       }
189     }
190 
191     // At this point, S is DFlocal.  Now we union in DFup's of our children...
192     // Loop through and visit the nodes that Node immediately dominates (Node's
193     // children in the IDomTree)
194     bool visitChild = false;
195     for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
196                                                NE = currentNode->end();
197          NI != NE; ++NI) {
198       DomTreeNodeT *IDominee = *NI;
199       BlockT *childBB = IDominee->getBlock();
200       if (visited.count(childBB) == 0) {
201         workList.push_back(DFCalculateWorkObject<BlockT>(
202             childBB, currentBB, IDominee, currentNode));
203         visitChild = true;
204       }
205     }
206 
207     // If all children are visited or there is any child then pop this block
208     // from the workList.
209     if (!visitChild) {
210       if (!parentBB) {
211         Result = &S;
212         break;
213       }
214 
215       typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
216       DomSetType &parentSet = this->Frontiers[parentBB];
217       for (; CDFI != CDFE; ++CDFI) {
218         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
219           parentSet.insert(*CDFI);
220       }
221       workList.pop_back();
222     }
223 
224   } while (!workList.empty());
225 
226   return *Result;
227 }
228 
229 } // end namespace llvm
230 
231 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
232