LLVM  7.0.0svn
DominanceFrontierImpl.h
Go to the documentation of this file.
1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- 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 is the generic implementation of the DominanceFrontier class, which
11 // calculate and holds the dominance frontier for a function for.
12 //
13 // This should be considered deprecated, don't add any more uses of this data
14 // structure.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
19 #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
20 
21 #include "llvm/ADT/GraphTraits.h"
22 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/Config/llvm-config.h"
25 #include "llvm/Support/Debug.h"
28 #include <cassert>
29 #include <set>
30 #include <utility>
31 #include <vector>
32 
33 namespace llvm {
34 
35 template <class BlockT>
37 public:
39 
40  DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
41  const DomTreeNodeT *PN)
42  : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
43 
44  BlockT *currentBB;
45  BlockT *parentBB;
48 };
49 
50 template <class BlockT, bool IsPostDom>
52  assert(find(BB) != end() && "Block is not in DominanceFrontier!");
53  for (iterator I = begin(), E = end(); I != E; ++I)
54  I->second.erase(BB);
55  Frontiers.erase(BB);
56 }
57 
58 template <class BlockT, bool IsPostDom>
60  BlockT *Node) {
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);
64 }
65 
66 template <class BlockT, bool IsPostDom>
68  iterator I, BlockT *Node) {
69  assert(I != end() && "BB is not in DominanceFrontier!");
70  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
71  I->second.erase(Node);
72 }
73 
74 template <class BlockT, bool IsPostDom>
76  DomSetType &DS1, const DomSetType &DS2) const {
77  std::set<BlockT *> tmpSet;
78  for (BlockT *BB : DS2)
79  tmpSet.insert(BB);
80 
81  for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
82  I != E;) {
83  BlockT *Node = *I++;
84 
85  if (tmpSet.erase(Node) == 0)
86  // Node is in DS1 but tnot in DS2.
87  return true;
88  }
89 
90  if (!tmpSet.empty()) {
91  // There are nodes that are in DS2 but not in DS1.
92  return true;
93  }
94 
95  // DS1 and DS2 matches.
96  return false;
97 }
98 
99 template <class BlockT, bool IsPostDom>
102  DomSetMapType tmpFrontiers;
103  for (typename DomSetMapType::const_iterator I = Other.begin(),
104  E = Other.end();
105  I != E; ++I)
106  tmpFrontiers.insert(std::make_pair(I->first, I->second));
107 
108  for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
109  E = tmpFrontiers.end();
110  I != E;) {
111  BlockT *Node = I->first;
112  const_iterator DFI = find(Node);
113  if (DFI == end())
114  return true;
115 
116  if (compareDomSet(I->second, DFI->second))
117  return true;
118 
119  ++I;
120  tmpFrontiers.erase(Node);
121  }
122 
123  if (!tmpFrontiers.empty())
124  return true;
125 
126  return false;
127 }
128 
129 template <class BlockT, bool IsPostDom>
131  for (const_iterator I = begin(), E = end(); I != E; ++I) {
132  OS << " DomFrontier for BB ";
133  if (I->first)
134  I->first->printAsOperand(OS, false);
135  else
136  OS << " <<exit node>>";
137  OS << " is:\t";
138 
139  const std::set<BlockT *> &BBs = I->second;
140 
141  for (const BlockT *BB : BBs) {
142  OS << ' ';
143  if (BB)
144  BB->printAsOperand(OS, false);
145  else
146  OS << "<<exit node>>";
147  }
148  OS << '\n';
149  }
150 }
151 
152 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
153 template <class BlockT, bool IsPostDom>
155  print(dbgs());
156 }
157 #endif
158 
159 template <class BlockT>
162  const DomTreeNodeT *Node) {
163  BlockT *BB = Node->getBlock();
164  DomSetType *Result = nullptr;
165 
166  std::vector<DFCalculateWorkObject<BlockT>> workList;
168 
169  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
170  do {
171  DFCalculateWorkObject<BlockT> *currentW = &workList.back();
172  assert(currentW && "Missing work object.");
173 
174  BlockT *currentBB = currentW->currentBB;
175  BlockT *parentBB = currentW->parentBB;
176  const DomTreeNodeT *currentNode = currentW->Node;
177  const DomTreeNodeT *parentNode = currentW->parentNode;
178  assert(currentBB && "Invalid work object. Missing current Basic Block");
179  assert(currentNode && "Invalid work object. Missing current Node");
180  DomSetType &S = this->Frontiers[currentBB];
181 
182  // Visit each block only once.
183  if (visited.insert(currentBB).second) {
184  // Loop over CFG successors to calculate DFlocal[currentNode]
185  for (const auto Succ : children<BlockT *>(currentBB)) {
186  // Does Node immediately dominate this successor?
187  if (DT[Succ]->getIDom() != currentNode)
188  S.insert(Succ);
189  }
190  }
191 
192  // At this point, S is DFlocal. Now we union in DFup's of our children...
193  // Loop through and visit the nodes that Node immediately dominates (Node's
194  // children in the IDomTree)
195  bool visitChild = false;
196  for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
197  NE = currentNode->end();
198  NI != NE; ++NI) {
199  DomTreeNodeT *IDominee = *NI;
200  BlockT *childBB = IDominee->getBlock();
201  if (visited.count(childBB) == 0) {
202  workList.push_back(DFCalculateWorkObject<BlockT>(
203  childBB, currentBB, IDominee, currentNode));
204  visitChild = true;
205  }
206  }
207 
208  // If all children are visited or there is any child then pop this block
209  // from the workList.
210  if (!visitChild) {
211  if (!parentBB) {
212  Result = &S;
213  break;
214  }
215 
216  typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
217  DomSetType &parentSet = this->Frontiers[parentBB];
218  for (; CDFI != CDFE; ++CDFI) {
219  if (!DT.properlyDominates(parentNode, DT[*CDFI]))
220  parentSet.insert(*CDFI);
221  }
222  workList.pop_back();
223  }
224 
225  } while (!workList.empty());
226 
227  return *Result;
228 }
229 
230 } // end namespace llvm
231 
232 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:250
typename std::vector< DomTreeNodeBase *>::const_iterator const_iterator
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:241
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void addToFrontier(iterator I, BlockT *Node)
DominanceFrontierBase - Common base class for computing forward and inverse dominance frontiers for a...
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
typename DomSetMapType::const_iterator const_iterator
typename DominanceFrontierBase< BlockT, false >::DomSetType DomSetType
void print(raw_ostream &OS) const
print - Convert to human readable form
std::map< BasicBlock *, DomSetType > DomSetMapType
void dump() const
dump - Dump the dominance frontier to dbgs().
Base class for the actual dominator tree node.
void removeFromFrontier(iterator I, BlockT *Node)
Core dominator tree base class.
Definition: LoopInfo.h:61
NodeT * getBlock() const
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
bool compare(DominanceFrontierBase &Other) const
compare - Return true if the other dominance frontier base matches this dominance frontier base...
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:929
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
void removeBlock(BlockT *BB)
removeBlock - Remove basic block BB&#39;s frontier.
DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N, const DomTreeNodeT *PN)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const DomSetType & calculate(const DomTreeT &DT, const DomTreeNodeT *Node)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const
compareDomSet - Return false if two domsets match.