LLVM  6.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/Support/Debug.h"
27 #include <cassert>
28 #include <set>
29 #include <utility>
30 #include <vector>
31 
32 namespace llvm {
33 
34 template <class BlockT>
36 public:
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;
47 };
48 
49 template <class BlockT, bool IsPostDom>
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>
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>
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>
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>
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>
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>
154  print(dbgs());
155 }
156 #endif
157 
158 template <class BlockT>
161  const DomTreeNodeT *Node) {
162  BlockT *BB = Node->getBlock();
163  DomSetType *Result = nullptr;
164 
165  std::vector<DFCalculateWorkObject<BlockT>> workList;
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
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:244
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:235
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:834
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:132
#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:44
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.