LLVM  8.0.0svn
GenericDomTreeConstruction.h
Go to the documentation of this file.
1 //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- 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 /// \file
10 ///
11 /// Generic dominator tree construction - This file provides routines to
12 /// construct immediate dominator information for a flow-graph based on the
13 /// Semi-NCA algorithm described in this dissertation:
14 ///
15 /// Linear-Time Algorithms for Dominators and Related Problems
16 /// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
17 /// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
18 ///
19 /// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
20 /// out that the theoretically slower O(n*log(n)) implementation is actually
21 /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
22 ///
23 /// The file uses the Depth Based Search algorithm to perform incremental
24 /// updates (insertion and deletions). The implemented algorithm is based on
25 /// this publication:
26 ///
27 /// An Experimental Study of Dynamic Dominators
28 /// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10:
29 /// https://arxiv.org/pdf/1604.02711.pdf
30 ///
31 //===----------------------------------------------------------------------===//
32 
33 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
34 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
35 
36 #include <queue>
37 #include "llvm/ADT/ArrayRef.h"
38 #include "llvm/ADT/DenseSet.h"
41 #include "llvm/ADT/SmallPtrSet.h"
42 #include "llvm/Support/Debug.h"
44 
45 #define DEBUG_TYPE "dom-tree-builder"
46 
47 namespace llvm {
48 namespace DomTreeBuilder {
49 
50 template <typename DomTreeT>
51 struct SemiNCAInfo {
52  using NodePtr = typename DomTreeT::NodePtr;
53  using NodeT = typename DomTreeT::NodeType;
55  using RootsT = decltype(DomTreeT::Roots);
56  static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
57 
58  // Information record used by Semi-NCA during tree construction.
59  struct InfoRec {
60  unsigned DFSNum = 0;
61  unsigned Parent = 0;
62  unsigned Semi = 0;
63  NodePtr Label = nullptr;
64  NodePtr IDom = nullptr;
66  };
67 
68  // Number to node mapping is 1-based. Initialize the mapping to start with
69  // a dummy element.
70  std::vector<NodePtr> NumToNode = {nullptr};
72 
73  using UpdateT = typename DomTreeT::UpdateType;
74  using UpdateKind = typename DomTreeT::UpdateKind;
75  struct BatchUpdateInfo {
78 
79  // In order to be able to walk a CFG that is out of sync with the CFG
80  // DominatorTree last knew about, use the list of updates to reconstruct
81  // previous CFG versions of the current CFG. For each node, we store a set
82  // of its virtually added/deleted future successors and predecessors.
83  // Note that these children are from the future relative to what the
84  // DominatorTree knows about -- using them to gets us some snapshot of the
85  // CFG from the past (relative to the state of the CFG).
88  // Remembers if the whole tree was recalculated at some point during the
89  // current batch update.
90  bool IsRecalculated = false;
91  };
92 
95 
96  // If BUI is a nullptr, then there's no batch update in progress.
97  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
98 
99  void clear() {
100  NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
101  NodeToInfo.clear();
102  // Don't reset the pointer to BatchUpdateInfo here -- if there's an update
103  // in progress, we need this information to continue it.
104  }
105 
106  template <bool Inverse>
107  struct ChildrenGetter {
109 
110  static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
111  auto RChildren = reverse(children<NodePtr>(N));
112  return ResultTy(RChildren.begin(), RChildren.end());
113  }
114 
115  static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
116  auto IChildren = inverse_children<NodePtr>(N);
117  return ResultTy(IChildren.begin(), IChildren.end());
118  }
119 
120  using Tag = std::integral_constant<bool, Inverse>;
121 
122  // The function below is the core part of the batch updater. It allows the
123  // Depth Based Search algorithm to perform incremental updates in lockstep
124  // with updates to the CFG. We emulated lockstep CFG updates by getting its
125  // next snapshots by reverse-applying future updates.
127  ResultTy Res = Get(N, Tag());
128  // If there's no batch update in progress, simply return node's children.
129  if (!BUI) return Res;
130 
131  // CFG children are actually its *most current* children, and we have to
132  // reverse-apply the future updates to get the node's children at the
133  // point in time the update was performed.
134  auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
135  : BUI->FutureSuccessors;
136  auto FCIt = FutureChildren.find(N);
137  if (FCIt == FutureChildren.end()) return Res;
138 
139  for (auto ChildAndKind : FCIt->second) {
140  const NodePtr Child = ChildAndKind.getPointer();
141  const UpdateKind UK = ChildAndKind.getInt();
142 
143  // Reverse-apply the future update.
144  if (UK == UpdateKind::Insert) {
145  // If there's an insertion in the future, it means that the edge must
146  // exist in the current CFG, but was not present in it before.
147  assert(llvm::find(Res, Child) != Res.end()
148  && "Expected child not found in the CFG");
149  Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end());
150  LLVM_DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
151  << BlockNamePrinter(Child) << "\n");
152  } else {
153  // If there's an deletion in the future, it means that the edge cannot
154  // exist in the current CFG, but existed in it before.
155  assert(llvm::find(Res, Child) == Res.end() &&
156  "Unexpected child found in the CFG");
157  LLVM_DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N)
158  << " -> " << BlockNamePrinter(Child) << "\n");
159  Res.push_back(Child);
160  }
161  }
162 
163  return Res;
164  }
165  };
166 
167  NodePtr getIDom(NodePtr BB) const {
168  auto InfoIt = NodeToInfo.find(BB);
169  if (InfoIt == NodeToInfo.end()) return nullptr;
170 
171  return InfoIt->second.IDom;
172  }
173 
174  TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
175  if (TreeNodePtr Node = DT.getNode(BB)) return Node;
176 
177  // Haven't calculated this node yet? Get or calculate the node for the
178  // immediate dominator.
179  NodePtr IDom = getIDom(BB);
180 
181  assert(IDom || DT.DomTreeNodes[nullptr]);
182  TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
183 
184  // Add a new tree node for this NodeT, and link it as a child of
185  // IDomNode
186  return (DT.DomTreeNodes[BB] = IDomNode->addChild(
188  .get();
189  }
190 
191  static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
192 
195 
196  BlockNamePrinter(NodePtr Block) : N(Block) {}
197  BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}
198 
200  if (!BP.N)
201  O << "nullptr";
202  else
203  BP.N->printAsOperand(O, false);
204 
205  return O;
206  }
207  };
208 
209  // Custom DFS implementation which can skip nodes based on a provided
210  // predicate. It also collects ReverseChildren so that we don't have to spend
211  // time getting predecessors in SemiNCA.
212  //
213  // If IsReverse is set to true, the DFS walk will be performed backwards
214  // relative to IsPostDom -- using reverse edges for dominators and forward
215  // edges for postdominators.
216  template <bool IsReverse = false, typename DescendCondition>
217  unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
218  unsigned AttachToNum) {
219  assert(V);
220  SmallVector<NodePtr, 64> WorkList = {V};
221  if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
222 
223  while (!WorkList.empty()) {
224  const NodePtr BB = WorkList.pop_back_val();
225  auto &BBInfo = NodeToInfo[BB];
226 
227  // Visited nodes always have positive DFS numbers.
228  if (BBInfo.DFSNum != 0) continue;
229  BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
230  BBInfo.Label = BB;
231  NumToNode.push_back(BB);
232 
233  constexpr bool Direction = IsReverse != IsPostDom; // XOR.
234  for (const NodePtr Succ :
235  ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
236  const auto SIT = NodeToInfo.find(Succ);
237  // Don't visit nodes more than once but remember to collect
238  // ReverseChildren.
239  if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
240  if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
241  continue;
242  }
243 
244  if (!Condition(BB, Succ)) continue;
245 
246  // It's fine to add Succ to the map, because we know that it will be
247  // visited later.
248  auto &SuccInfo = NodeToInfo[Succ];
249  WorkList.push_back(Succ);
250  SuccInfo.Parent = LastNum;
251  SuccInfo.ReverseChildren.push_back(BB);
252  }
253  }
254 
255  return LastNum;
256  }
257 
258  NodePtr eval(NodePtr VIn, unsigned LastLinked) {
259  auto &VInInfo = NodeToInfo[VIn];
260  if (VInInfo.DFSNum < LastLinked)
261  return VIn;
262 
264  SmallPtrSet<NodePtr, 32> Visited;
265 
266  if (VInInfo.Parent >= LastLinked)
267  Work.push_back(VIn);
268 
269  while (!Work.empty()) {
270  NodePtr V = Work.back();
271  auto &VInfo = NodeToInfo[V];
272  NodePtr VAncestor = NumToNode[VInfo.Parent];
273 
274  // Process Ancestor first
275  if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
276  Work.push_back(VAncestor);
277  continue;
278  }
279  Work.pop_back();
280 
281  // Update VInfo based on Ancestor info
282  if (VInfo.Parent < LastLinked)
283  continue;
284 
285  auto &VAInfo = NodeToInfo[VAncestor];
286  NodePtr VAncestorLabel = VAInfo.Label;
287  NodePtr VLabel = VInfo.Label;
288  if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
289  VInfo.Label = VAncestorLabel;
290  VInfo.Parent = VAInfo.Parent;
291  }
292 
293  return VInInfo.Label;
294  }
295 
296  // This function requires DFS to be run before calling it.
297  void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
298  const unsigned NextDFSNum(NumToNode.size());
299  // Initialize IDoms to spanning tree parents.
300  for (unsigned i = 1; i < NextDFSNum; ++i) {
301  const NodePtr V = NumToNode[i];
302  auto &VInfo = NodeToInfo[V];
303  VInfo.IDom = NumToNode[VInfo.Parent];
304  }
305 
306  // Step #1: Calculate the semidominators of all vertices.
307  for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
308  NodePtr W = NumToNode[i];
309  auto &WInfo = NodeToInfo[W];
310 
311  // Initialize the semi dominator to point to the parent node.
312  WInfo.Semi = WInfo.Parent;
313  for (const auto &N : WInfo.ReverseChildren) {
314  if (NodeToInfo.count(N) == 0) // Skip unreachable predecessors.
315  continue;
316 
317  const TreeNodePtr TN = DT.getNode(N);
318  // Skip predecessors whose level is above the subtree we are processing.
319  if (TN && TN->getLevel() < MinLevel)
320  continue;
321 
322  unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
323  if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
324  }
325  }
326 
327  // Step #2: Explicitly define the immediate dominator of each vertex.
328  // IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
329  // Note that the parents were stored in IDoms and later got invalidated
330  // during path compression in Eval.
331  for (unsigned i = 2; i < NextDFSNum; ++i) {
332  const NodePtr W = NumToNode[i];
333  auto &WInfo = NodeToInfo[W];
334  const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
335  NodePtr WIDomCandidate = WInfo.IDom;
336  while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
337  WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
338 
339  WInfo.IDom = WIDomCandidate;
340  }
341  }
342 
343  // PostDominatorTree always has a virtual root that represents a virtual CFG
344  // node that serves as a single exit from the function. All the other exits
345  // (CFG nodes with terminators and nodes in infinite loops are logically
346  // connected to this virtual CFG exit node).
347  // This functions maps a nullptr CFG node to the virtual root tree node.
348  void addVirtualRoot() {
349  assert(IsPostDom && "Only postdominators have a virtual root");
350  assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
351 
352  auto &BBInfo = NodeToInfo[nullptr];
353  BBInfo.DFSNum = BBInfo.Semi = 1;
354  BBInfo.Label = nullptr;
355 
356  NumToNode.push_back(nullptr); // NumToNode[1] = nullptr;
357  }
358 
359  // For postdominators, nodes with no forward successors are trivial roots that
360  // are always selected as tree roots. Roots with forward successors correspond
361  // to CFG nodes within infinite loops.
362  static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
363  assert(N && "N must be a valid node");
364  return !ChildrenGetter<false>::Get(N, BUI).empty();
365  }
366 
367  static NodePtr GetEntryNode(const DomTreeT &DT) {
368  assert(DT.Parent && "Parent not set");
370  }
371 
372  // Finds all roots without relaying on the set of roots already stored in the
373  // tree.
374  // We define roots to be some non-redundant set of the CFG nodes
375  static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
376  assert(DT.Parent && "Parent pointer is not set");
377  RootsT Roots;
378 
379  // For dominators, function entry CFG node is always a tree root node.
380  if (!IsPostDom) {
381  Roots.push_back(GetEntryNode(DT));
382  return Roots;
383  }
384 
385  SemiNCAInfo SNCA(BUI);
386 
387  // PostDominatorTree always has a virtual root.
388  SNCA.addVirtualRoot();
389  unsigned Num = 1;
390 
391  LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
392 
393  // Step #1: Find all the trivial roots that are going to will definitely
394  // remain tree roots.
395  unsigned Total = 0;
396  // It may happen that there are some new nodes in the CFG that are result of
397  // the ongoing batch update, but we cannot really pretend that they don't
398  // exist -- we won't see any outgoing or incoming edges to them, so it's
399  // fine to discover them here, as they would end up appearing in the CFG at
400  // some point anyway.
401  for (const NodePtr N : nodes(DT.Parent)) {
402  ++Total;
403  // If it has no *successors*, it is definitely a root.
404  if (!HasForwardSuccessors(N, BUI)) {
405  Roots.push_back(N);
406  // Run DFS not to walk this part of CFG later.
407  Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
408  LLVM_DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
409  << "\n");
410  LLVM_DEBUG(dbgs() << "Last visited node: "
411  << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
412  }
413  }
414 
415  LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");
416 
417  // Step #2: Find all non-trivial root candidates. Those are CFG nodes that
418  // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG
419  // nodes in infinite loops).
420  bool HasNonTrivialRoots = false;
421  // Accounting for the virtual exit, see if we had any reverse-unreachable
422  // nodes.
423  if (Total + 1 != Num) {
424  HasNonTrivialRoots = true;
425  // Make another DFS pass over all other nodes to find the
426  // reverse-unreachable blocks, and find the furthest paths we'll be able
427  // to make.
428  // Note that this looks N^2, but it's really 2N worst case, if every node
429  // is unreachable. This is because we are still going to only visit each
430  // unreachable node once, we may just visit it in two directions,
431  // depending on how lucky we get.
432  SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
433  for (const NodePtr I : nodes(DT.Parent)) {
434  if (SNCA.NodeToInfo.count(I) == 0) {
435  LLVM_DEBUG(dbgs()
436  << "\t\t\tVisiting node " << BlockNamePrinter(I) << "\n");
437  // Find the furthest away we can get by following successors, then
438  // follow them in reverse. This gives us some reasonable answer about
439  // the post-dom tree inside any infinite loop. In particular, it
440  // guarantees we get to the farthest away point along *some*
441  // path. This also matches the GCC's behavior.
442  // If we really wanted a totally complete picture of dominance inside
443  // this infinite loop, we could do it with SCC-like algorithms to find
444  // the lowest and highest points in the infinite loop. In theory, it
445  // would be nice to give the canonical backedge for the loop, but it's
446  // expensive and does not always lead to a minimal set of roots.
447  LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
448 
449  const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num);
450  const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
451  LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
452  << "(non-trivial root): "
453  << BlockNamePrinter(FurthestAway) << "\n");
454  ConnectToExitBlock.insert(FurthestAway);
455  Roots.push_back(FurthestAway);
456  LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
457  << NewNum << "\n\t\t\tRemoving DFS info\n");
458  for (unsigned i = NewNum; i > Num; --i) {
459  const NodePtr N = SNCA.NumToNode[i];
460  LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
461  << BlockNamePrinter(N) << "\n");
462  SNCA.NodeToInfo.erase(N);
463  SNCA.NumToNode.pop_back();
464  }
465  const unsigned PrevNum = Num;
466  LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
467  Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
468  for (unsigned i = PrevNum + 1; i <= Num; ++i)
469  LLVM_DEBUG(dbgs() << "\t\t\t\tfound node "
470  << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
471  }
472  }
473  }
474 
475  LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
476  LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n");
477  LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
478  << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
479 
480  assert((Total + 1 == Num) && "Everything should have been visited");
481 
482  // Step #3: If we found some non-trivial roots, make them non-redundant.
483  if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
484 
485  LLVM_DEBUG(dbgs() << "Found roots: ");
486  LLVM_DEBUG(for (auto *Root
487  : Roots) dbgs()
488  << BlockNamePrinter(Root) << " ");
489  LLVM_DEBUG(dbgs() << "\n");
490 
491  return Roots;
492  }
493 
494  // This function only makes sense for postdominators.
495  // We define roots to be some set of CFG nodes where (reverse) DFS walks have
496  // to start in order to visit all the CFG nodes (including the
497  // reverse-unreachable ones).
498  // When the search for non-trivial roots is done it may happen that some of
499  // the non-trivial roots are reverse-reachable from other non-trivial roots,
500  // which makes them redundant. This function removes them from the set of
501  // input roots.
502  static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
503  RootsT &Roots) {
504  assert(IsPostDom && "This function is for postdominators only");
505  LLVM_DEBUG(dbgs() << "Removing redundant roots\n");
506 
507  SemiNCAInfo SNCA(BUI);
508 
509  for (unsigned i = 0; i < Roots.size(); ++i) {
510  auto &Root = Roots[i];
511  // Trivial roots are always non-redundant.
512  if (!HasForwardSuccessors(Root, BUI)) continue;
513  LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
514  << " remains a root\n");
515  SNCA.clear();
516  // Do a forward walk looking for the other roots.
517  const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
518  // Skip the start node and begin from the second one (note that DFS uses
519  // 1-based indexing).
520  for (unsigned x = 2; x <= Num; ++x) {
521  const NodePtr N = SNCA.NumToNode[x];
522  // If we wound another root in a (forward) DFS walk, remove the current
523  // root from the set of roots, as it is reverse-reachable from the other
524  // one.
525  if (llvm::find(Roots, N) != Roots.end()) {
526  LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "
527  << BlockNamePrinter(N) << "\n\tRemoving root "
528  << BlockNamePrinter(Root) << "\n");
529  std::swap(Root, Roots.back());
530  Roots.pop_back();
531 
532  // Root at the back takes the current root's place.
533  // Start the next loop iteration with the same index.
534  --i;
535  break;
536  }
537  }
538  }
539  }
540 
541  template <typename DescendCondition>
542  void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
543  if (!IsPostDom) {
544  assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
545  runDFS(DT.Roots[0], 0, DC, 0);
546  return;
547  }
548 
549  addVirtualRoot();
550  unsigned Num = 1;
551  for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
552  }
553 
554  static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
555  auto *Parent = DT.Parent;
556  DT.reset();
557  DT.Parent = Parent;
558  SemiNCAInfo SNCA(nullptr); // Since we are rebuilding the whole tree,
559  // there's no point doing it incrementally.
560 
561  // Step #0: Number blocks in depth-first order and initialize variables used
562  // in later stages of the algorithm.
563  DT.Roots = FindRoots(DT, nullptr);
564  SNCA.doFullDFSWalk(DT, AlwaysDescend);
565 
566  SNCA.runSemiNCA(DT);
567  if (BUI) {
568  BUI->IsRecalculated = true;
569  LLVM_DEBUG(
570  dbgs() << "DomTree recalculated, skipping future batch updates\n");
571  }
572 
573  if (DT.Roots.empty()) return;
574 
575  // Add a node for the root. If the tree is a PostDominatorTree it will be
576  // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
577  // all real exits (including multiple exit blocks, infinite loops).
578  NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
579 
580  DT.RootNode = (DT.DomTreeNodes[Root] =
581  llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
582  .get();
583  SNCA.attachNewSubtree(DT, DT.RootNode);
584  }
585 
586  void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
587  // Attach the first unreachable block to AttachTo.
588  NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
589  // Loop over all of the discovered blocks in the function...
590  for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
591  NodePtr W = NumToNode[i];
592  LLVM_DEBUG(dbgs() << "\tdiscovered a new reachable node "
593  << BlockNamePrinter(W) << "\n");
594 
595  // Don't replace this with 'count', the insertion side effect is important
596  if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet?
597 
598  NodePtr ImmDom = getIDom(W);
599 
600  // Get or calculate the node for the immediate dominator.
601  TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
602 
603  // Add a new tree node for this BasicBlock, and link it as a child of
604  // IDomNode.
605  DT.DomTreeNodes[W] = IDomNode->addChild(
607  }
608  }
609 
610  void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
611  NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
612  for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
613  const NodePtr N = NumToNode[i];
614  const TreeNodePtr TN = DT.getNode(N);
615  assert(TN);
616  const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
617  TN->setIDom(NewIDom);
618  }
619  }
620 
621  // Helper struct used during edge insertions.
622  struct InsertionInfo {
623  using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
625  bool operator()(const BucketElementTy &First,
626  const BucketElementTy &Second) const {
627  return First.first > Second.first;
628  }
629  };
630 
631  std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
633  Bucket; // Queue of tree nodes sorted by level in descending order.
638  };
639 
640  static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
641  const NodePtr From, const NodePtr To) {
642  assert((From || IsPostDom) &&
643  "From has to be a valid CFG node or a virtual root");
644  assert(To && "Cannot be a nullptr");
645  LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
646  << BlockNamePrinter(To) << "\n");
647  TreeNodePtr FromTN = DT.getNode(From);
648 
649  if (!FromTN) {
650  // Ignore edges from unreachable nodes for (forward) dominators.
651  if (!IsPostDom) return;
652 
653  // The unreachable node becomes a new root -- a tree node for it.
654  TreeNodePtr VirtualRoot = DT.getNode(nullptr);
655  FromTN =
656  (DT.DomTreeNodes[From] = VirtualRoot->addChild(
657  llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
658  .get();
659  DT.Roots.push_back(From);
660  }
661 
662  DT.DFSInfoValid = false;
663 
664  const TreeNodePtr ToTN = DT.getNode(To);
665  if (!ToTN)
666  InsertUnreachable(DT, BUI, FromTN, To);
667  else
668  InsertReachable(DT, BUI, FromTN, ToTN);
669  }
670 
671  // Determines if some existing root becomes reverse-reachable after the
672  // insertion. Rebuilds the whole tree if that situation happens.
673  static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
674  const TreeNodePtr From,
675  const TreeNodePtr To) {
676  assert(IsPostDom && "This function is only for postdominators");
677  // Destination node is not attached to the virtual root, so it cannot be a
678  // root.
679  if (!DT.isVirtualRoot(To->getIDom())) return false;
680 
681  auto RIt = llvm::find(DT.Roots, To->getBlock());
682  if (RIt == DT.Roots.end())
683  return false; // To is not a root, nothing to update.
684 
685  LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
686  << " is no longer a root\n\t\tRebuilding the tree!!!\n");
687 
688  CalculateFromScratch(DT, BUI);
689  return true;
690  }
691 
692  // Updates the set of roots after insertion or deletion. This ensures that
693  // roots are the same when after a series of updates and when the tree would
694  // be built from scratch.
695  static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
696  assert(IsPostDom && "This function is only for postdominators");
697 
698  // The tree has only trivial roots -- nothing to update.
699  if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
700  return HasForwardSuccessors(N, BUI);
701  }))
702  return;
703 
704  // Recalculate the set of roots.
705  auto Roots = FindRoots(DT, BUI);
706  if (DT.Roots.size() != Roots.size() ||
707  !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), Roots.begin())) {
708  // The roots chosen in the CFG have changed. This is because the
709  // incremental algorithm does not really know or use the set of roots and
710  // can make a different (implicit) decision about which node within an
711  // infinite loop becomes a root.
712 
713  LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"
714  << "The entire tree needs to be rebuilt\n");
715  // It may be possible to update the tree without recalculating it, but
716  // we do not know yet how to do it, and it happens rarely in practise.
717  CalculateFromScratch(DT, BUI);
718  return;
719  }
720  }
721 
722  // Handles insertion to a node already in the dominator tree.
723  static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
724  const TreeNodePtr From, const TreeNodePtr To) {
725  LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
726  << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
727  if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
728  // DT.findNCD expects both pointers to be valid. When From is a virtual
729  // root, then its CFG block pointer is a nullptr, so we have to 'compute'
730  // the NCD manually.
731  const NodePtr NCDBlock =
732  (From->getBlock() && To->getBlock())
733  ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
734  : nullptr;
735  assert(NCDBlock || DT.isPostDominator());
736  const TreeNodePtr NCD = DT.getNode(NCDBlock);
737  assert(NCD);
738 
739  LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
740  const TreeNodePtr ToIDom = To->getIDom();
741 
742  // Nothing affected -- NCA property holds.
743  // (Based on the lemma 2.5 from the second paper.)
744  if (NCD == To || NCD == ToIDom) return;
745 
746  // Identify and collect affected nodes.
747  InsertionInfo II;
748  LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To)
749  << " as affected\n");
750  II.Affected.insert(To);
751  const unsigned ToLevel = To->getLevel();
752  LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To)
753  << " into a Bucket\n");
754  II.Bucket.push({ToLevel, To});
755 
756  while (!II.Bucket.empty()) {
757  const TreeNodePtr CurrentNode = II.Bucket.top().second;
758  const unsigned CurrentLevel = CurrentNode->getLevel();
759  II.Bucket.pop();
760  LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
761  << BlockNamePrinter(CurrentNode) << "\n");
762 
763  II.Visited.insert({CurrentNode, CurrentLevel});
764  II.AffectedQueue.push_back(CurrentNode);
765 
766  // Discover and collect affected successors of the current node.
767  VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
768  }
769 
770  // Finish by updating immediate dominators and levels.
771  UpdateInsertion(DT, BUI, NCD, II);
772  }
773 
774  // Visits an affected node and collect its affected successors.
775  static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
776  const TreeNodePtr TN, const unsigned RootLevel,
777  const TreeNodePtr NCD, InsertionInfo &II) {
778  const unsigned NCDLevel = NCD->getLevel();
779  LLVM_DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ", RootLevel "
780  << RootLevel << "\n");
781 
782  SmallVector<TreeNodePtr, 8> Stack = {TN};
783  assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
784 
785  SmallPtrSet<TreeNodePtr, 8> Processed;
786 
787  do {
788  TreeNodePtr Next = Stack.pop_back_val();
789  LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n");
790 
791  for (const NodePtr Succ :
793  const TreeNodePtr SuccTN = DT.getNode(Succ);
794  assert(SuccTN && "Unreachable successor found at reachable insertion");
795  const unsigned SuccLevel = SuccTN->getLevel();
796 
797  LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
798  << ", level = " << SuccLevel << "\n");
799 
800  // Do not process the same node multiple times.
801  if (Processed.count(Next) > 0)
802  continue;
803 
804  // Succ dominated by subtree From -- not affected.
805  // (Based on the lemma 2.5 from the second paper.)
806  if (SuccLevel > RootLevel) {
807  LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n");
808  if (II.Visited.count(SuccTN) != 0) {
809  LLVM_DEBUG(dbgs() << "\t\t\talready visited at level "
810  << II.Visited[SuccTN] << "\n\t\t\tcurrent level "
811  << RootLevel << ")\n");
812 
813  // A node can be necessary to visit again if we see it again at
814  // a lower level than before.
815  if (II.Visited[SuccTN] >= RootLevel)
816  continue;
817  }
818 
819  LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
820  << BlockNamePrinter(Succ) << "\n");
821  II.Visited.insert({SuccTN, RootLevel});
822  II.VisitedNotAffectedQueue.push_back(SuccTN);
823  Stack.push_back(SuccTN);
824  } else if ((SuccLevel > NCDLevel + 1) &&
825  II.Affected.count(SuccTN) == 0) {
826  LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding "
827  << BlockNamePrinter(Succ) << " to a Bucket\n");
828  II.Affected.insert(SuccTN);
829  II.Bucket.push({SuccLevel, SuccTN});
830  }
831  }
832 
833  Processed.insert(Next);
834  } while (!Stack.empty());
835  }
836 
837  // Updates immediate dominators and levels after insertion.
838  static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
839  const TreeNodePtr NCD, InsertionInfo &II) {
840  LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
841 
842  for (const TreeNodePtr TN : II.AffectedQueue) {
843  LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
844  << ") = " << BlockNamePrinter(NCD) << "\n");
845  TN->setIDom(NCD);
846  }
847 
849  if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
850  }
851 
853  LLVM_DEBUG(
854  dbgs() << "Updating levels for visited but not affected nodes\n");
855 
856  for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
857  LLVM_DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
858  << BlockNamePrinter(TN->getIDom()) << ") "
859  << TN->getIDom()->getLevel() << " + 1\n");
860  TN->UpdateLevel();
861  }
862  }
863 
864  // Handles insertion to previously unreachable nodes.
865  static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
866  const TreeNodePtr From, const NodePtr To) {
867  LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
868  << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
869 
870  // Collect discovered edges to already reachable nodes.
871  SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
872  // Discover and connect nodes that became reachable with the insertion.
873  ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
874 
875  LLVM_DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
876  << " -> (prev unreachable) " << BlockNamePrinter(To)
877  << "\n");
878 
879  // Used the discovered edges and inset discovered connecting (incoming)
880  // edges.
881  for (const auto &Edge : DiscoveredEdgesToReachable) {
882  LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "
883  << BlockNamePrinter(Edge.first) << " -> "
884  << BlockNamePrinter(Edge.second) << "\n");
885  InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
886  }
887  }
888 
889  // Connects nodes that become reachable with an insertion.
891  DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
892  const TreeNodePtr Incoming,
893  SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
894  &DiscoveredConnectingEdges) {
895  assert(!DT.getNode(Root) && "Root must not be reachable");
896 
897  // Visit only previously unreachable nodes.
898  auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
899  NodePtr To) {
900  const TreeNodePtr ToTN = DT.getNode(To);
901  if (!ToTN) return true;
902 
903  DiscoveredConnectingEdges.push_back({From, ToTN});
904  return false;
905  };
906 
907  SemiNCAInfo SNCA(BUI);
908  SNCA.runDFS(Root, 0, UnreachableDescender, 0);
909  SNCA.runSemiNCA(DT);
910  SNCA.attachNewSubtree(DT, Incoming);
911 
912  LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");
913  }
914 
915  static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
916  const NodePtr From, const NodePtr To) {
917  assert(From && To && "Cannot disconnect nullptrs");
918  LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
919  << BlockNamePrinter(To) << "\n");
920 
921 #ifndef NDEBUG
922  // Ensure that the edge was in fact deleted from the CFG before informing
923  // the DomTree about it.
924  // The check is O(N), so run it only in debug configuration.
925  auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
926  auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
927  return llvm::find(Successors, SuccCandidate) != Successors.end();
928  };
929  (void)IsSuccessor;
930  assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
931 #endif
932 
933  const TreeNodePtr FromTN = DT.getNode(From);
934  // Deletion in an unreachable subtree -- nothing to do.
935  if (!FromTN) return;
936 
937  const TreeNodePtr ToTN = DT.getNode(To);
938  if (!ToTN) {
939  LLVM_DEBUG(
940  dbgs() << "\tTo (" << BlockNamePrinter(To)
941  << ") already unreachable -- there is no edge to delete\n");
942  return;
943  }
944 
945  const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
946  const TreeNodePtr NCD = DT.getNode(NCDBlock);
947 
948  // If To dominates From -- nothing to do.
949  if (ToTN != NCD) {
950  DT.DFSInfoValid = false;
951 
952  const TreeNodePtr ToIDom = ToTN->getIDom();
953  LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
954  << BlockNamePrinter(ToIDom) << "\n");
955 
956  // To remains reachable after deletion.
957  // (Based on the caption under Figure 4. from the second paper.)
958  if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
959  DeleteReachable(DT, BUI, FromTN, ToTN);
960  else
961  DeleteUnreachable(DT, BUI, ToTN);
962  }
963 
964  if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
965  }
966 
967  // Handles deletions that leave destination nodes reachable.
968  static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
969  const TreeNodePtr FromTN,
970  const TreeNodePtr ToTN) {
971  LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN)
972  << " -> " << BlockNamePrinter(ToTN) << "\n");
973  LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n");
974 
975  // Find the top of the subtree that needs to be rebuilt.
976  // (Based on the lemma 2.6 from the second paper.)
977  const NodePtr ToIDom =
978  DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
979  assert(ToIDom || DT.isPostDominator());
980  const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
981  assert(ToIDomTN);
982  const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
983  // Top of the subtree to rebuild is the root node. Rebuild the tree from
984  // scratch.
985  if (!PrevIDomSubTree) {
986  LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
987  CalculateFromScratch(DT, BUI);
988  return;
989  }
990 
991  // Only visit nodes in the subtree starting at To.
992  const unsigned Level = ToIDomTN->getLevel();
993  auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
994  return DT.getNode(To)->getLevel() > Level;
995  };
996 
997  LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN)
998  << "\n");
999 
1000  SemiNCAInfo SNCA(BUI);
1001  SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
1002  LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
1003  SNCA.runSemiNCA(DT, Level);
1004  SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
1005  }
1006 
1007  // Checks if a node has proper support, as defined on the page 3 and later
1008  // explained on the page 7 of the second paper.
1009  static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
1010  const TreeNodePtr TN) {
1011  LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
1012  << "\n");
1013  for (const NodePtr Pred :
1015  LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
1016  if (!DT.getNode(Pred)) continue;
1017 
1018  const NodePtr Support =
1019  DT.findNearestCommonDominator(TN->getBlock(), Pred);
1020  LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
1021  if (Support != TN->getBlock()) {
1022  LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
1023  << " is reachable from support "
1024  << BlockNamePrinter(Support) << "\n");
1025  return true;
1026  }
1027  }
1028 
1029  return false;
1030  }
1031 
1032  // Handle deletions that make destination node unreachable.
1033  // (Based on the lemma 2.7 from the second paper.)
1034  static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
1035  const TreeNodePtr ToTN) {
1036  LLVM_DEBUG(dbgs() << "Deleting unreachable subtree "
1037  << BlockNamePrinter(ToTN) << "\n");
1038  assert(ToTN);
1039  assert(ToTN->getBlock());
1040 
1041  if (IsPostDom) {
1042  // Deletion makes a region reverse-unreachable and creates a new root.
1043  // Simulate that by inserting an edge from the virtual root to ToTN and
1044  // adding it as a new root.
1045  LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
1046  LLVM_DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN)
1047  << "\n");
1048  DT.Roots.push_back(ToTN->getBlock());
1049  InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
1050  return;
1051  }
1052 
1053  SmallVector<NodePtr, 16> AffectedQueue;
1054  const unsigned Level = ToTN->getLevel();
1055 
1056  // Traverse destination node's descendants with greater level in the tree
1057  // and collect visited nodes.
1058  auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
1059  const TreeNodePtr TN = DT.getNode(To);
1060  assert(TN);
1061  if (TN->getLevel() > Level) return true;
1062  if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
1063  AffectedQueue.push_back(To);
1064 
1065  return false;
1066  };
1067 
1068  SemiNCAInfo SNCA(BUI);
1069  unsigned LastDFSNum =
1070  SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
1071 
1072  TreeNodePtr MinNode = ToTN;
1073 
1074  // Identify the top of the subtree to rebuild by finding the NCD of all
1075  // the affected nodes.
1076  for (const NodePtr N : AffectedQueue) {
1077  const TreeNodePtr TN = DT.getNode(N);
1078  const NodePtr NCDBlock =
1079  DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
1080  assert(NCDBlock || DT.isPostDominator());
1081  const TreeNodePtr NCD = DT.getNode(NCDBlock);
1082  assert(NCD);
1083 
1084  LLVM_DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
1085  << " with NCD = " << BlockNamePrinter(NCD)
1086  << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
1087  if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
1088  }
1089 
1090  // Root reached, rebuild the whole tree from scratch.
1091  if (!MinNode->getIDom()) {
1092  LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
1093  CalculateFromScratch(DT, BUI);
1094  return;
1095  }
1096 
1097  // Erase the unreachable subtree in reverse preorder to process all children
1098  // before deleting their parent.
1099  for (unsigned i = LastDFSNum; i > 0; --i) {
1100  const NodePtr N = SNCA.NumToNode[i];
1101  const TreeNodePtr TN = DT.getNode(N);
1102  LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
1103 
1104  EraseNode(DT, TN);
1105  }
1106 
1107  // The affected subtree start at the To node -- there's no extra work to do.
1108  if (MinNode == ToTN) return;
1109 
1110  LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
1111  << BlockNamePrinter(MinNode) << "\n");
1112  const unsigned MinLevel = MinNode->getLevel();
1113  const TreeNodePtr PrevIDom = MinNode->getIDom();
1114  assert(PrevIDom);
1115  SNCA.clear();
1116 
1117  // Identify nodes that remain in the affected subtree.
1118  auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
1119  const TreeNodePtr ToTN = DT.getNode(To);
1120  return ToTN && ToTN->getLevel() > MinLevel;
1121  };
1122  SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
1123 
1124  LLVM_DEBUG(dbgs() << "Previous IDom(MinNode) = "
1125  << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n");
1126 
1127  // Rebuild the remaining part of affected subtree.
1128  SNCA.runSemiNCA(DT, MinLevel);
1129  SNCA.reattachExistingSubtree(DT, PrevIDom);
1130  }
1131 
1132  // Removes leaf tree nodes from the dominator tree.
1133  static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
1134  assert(TN);
1135  assert(TN->getNumChildren() == 0 && "Not a tree leaf");
1136 
1137  const TreeNodePtr IDom = TN->getIDom();
1138  assert(IDom);
1139 
1140  auto ChIt = llvm::find(IDom->Children, TN);
1141  assert(ChIt != IDom->Children.end());
1142  std::swap(*ChIt, IDom->Children.back());
1143  IDom->Children.pop_back();
1144 
1145  DT.DomTreeNodes.erase(TN->getBlock());
1146  }
1147 
1148  //~~
1149  //===--------------------- DomTree Batch Updater --------------------------===
1150  //~~
1151 
1152  static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
1153  const size_t NumUpdates = Updates.size();
1154  if (NumUpdates == 0)
1155  return;
1156 
1157  // Take the fast path for a single update and avoid running the batch update
1158  // machinery.
1159  if (NumUpdates == 1) {
1160  const auto &Update = Updates.front();
1161  if (Update.getKind() == UpdateKind::Insert)
1162  DT.insertEdge(Update.getFrom(), Update.getTo());
1163  else
1164  DT.deleteEdge(Update.getFrom(), Update.getTo());
1165 
1166  return;
1167  }
1168 
1169  BatchUpdateInfo BUI;
1170  LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
1171  cfg::LegalizeUpdates<NodePtr>(Updates, BUI.Updates, IsPostDom);
1172 
1173  const size_t NumLegalized = BUI.Updates.size();
1174  BUI.FutureSuccessors.reserve(NumLegalized);
1175  BUI.FuturePredecessors.reserve(NumLegalized);
1176 
1177  // Use the legalized future updates to initialize future successors and
1178  // predecessors. Note that these sets will only decrease size over time, as
1179  // the next CFG snapshots slowly approach the actual (current) CFG.
1180  for (UpdateT &U : BUI.Updates) {
1181  BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
1182  BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
1183  }
1184 
1185  LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
1186  LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U
1187  : reverse(BUI.Updates)) {
1188  dbgs() << "\t";
1189  U.dump();
1190  dbgs() << "\n";
1191  });
1192  LLVM_DEBUG(dbgs() << "\n");
1193 
1194  // Recalculate the DominatorTree when the number of updates
1195  // exceeds a threshold, which usually makes direct updating slower than
1196  // recalculation. We select this threshold proportional to the
1197  // size of the DominatorTree. The constant is selected
1198  // by choosing the one with an acceptable performance on some real-world
1199  // inputs.
1200 
1201  // Make unittests of the incremental algorithm work
1202  if (DT.DomTreeNodes.size() <= 100) {
1203  if (NumLegalized > DT.DomTreeNodes.size())
1204  CalculateFromScratch(DT, &BUI);
1205  } else if (NumLegalized > DT.DomTreeNodes.size() / 40)
1206  CalculateFromScratch(DT, &BUI);
1207 
1208  // If the DominatorTree was recalculated at some point, stop the batch
1209  // updates. Full recalculations ignore batch updates and look at the actual
1210  // CFG.
1211  for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
1212  ApplyNextUpdate(DT, BUI);
1213  }
1214 
1215  static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
1216  assert(!BUI.Updates.empty() && "No updates to apply!");
1217  UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
1218  LLVM_DEBUG(dbgs() << "Applying update: ");
1219  LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n");
1220 
1221  // Move to the next snapshot of the CFG by removing the reverse-applied
1222  // current update. Since updates are performed in the same order they are
1223  // legalized it's sufficient to pop the last item here.
1224  auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
1225  assert(FS.back().getPointer() == CurrentUpdate.getTo() &&
1226  FS.back().getInt() == CurrentUpdate.getKind());
1227  FS.pop_back();
1228  if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
1229 
1230  auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
1231  assert(FP.back().getPointer() == CurrentUpdate.getFrom() &&
1232  FP.back().getInt() == CurrentUpdate.getKind());
1233  FP.pop_back();
1234  if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
1235 
1236  if (CurrentUpdate.getKind() == UpdateKind::Insert)
1237  InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1238  else
1239  DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1240  }
1241 
1242  //~~
1243  //===--------------- DomTree correctness verification ---------------------===
1244  //~~
1245 
1246  // Check if the tree has correct roots. A DominatorTree always has a single
1247  // root which is the function's entry node. A PostDominatorTree can have
1248  // multiple roots - one for each node with no successors and for infinite
1249  // loops.
1250  // Running time: O(N).
1251  bool verifyRoots(const DomTreeT &DT) {
1252  if (!DT.Parent && !DT.Roots.empty()) {
1253  errs() << "Tree has no parent but has roots!\n";
1254  errs().flush();
1255  return false;
1256  }
1257 
1258  if (!IsPostDom) {
1259  if (DT.Roots.empty()) {
1260  errs() << "Tree doesn't have a root!\n";
1261  errs().flush();
1262  return false;
1263  }
1264 
1265  if (DT.getRoot() != GetEntryNode(DT)) {
1266  errs() << "Tree's root is not its parent's entry node!\n";
1267  errs().flush();
1268  return false;
1269  }
1270  }
1271 
1272  RootsT ComputedRoots = FindRoots(DT, nullptr);
1273  if (DT.Roots.size() != ComputedRoots.size() ||
1274  !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
1275  ComputedRoots.begin())) {
1276  errs() << "Tree has different roots than freshly computed ones!\n";
1277  errs() << "\tPDT roots: ";
1278  for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
1279  errs() << "\n\tComputed roots: ";
1280  for (const NodePtr N : ComputedRoots)
1281  errs() << BlockNamePrinter(N) << ", ";
1282  errs() << "\n";
1283  errs().flush();
1284  return false;
1285  }
1286 
1287  return true;
1288  }
1289 
1290  // Checks if the tree contains all reachable nodes in the input graph.
1291  // Running time: O(N).
1292  bool verifyReachability(const DomTreeT &DT) {
1293  clear();
1295 
1296  for (auto &NodeToTN : DT.DomTreeNodes) {
1297  const TreeNodePtr TN = NodeToTN.second.get();
1298  const NodePtr BB = TN->getBlock();
1299 
1300  // Virtual root has a corresponding virtual CFG node.
1301  if (DT.isVirtualRoot(TN)) continue;
1302 
1303  if (NodeToInfo.count(BB) == 0) {
1304  errs() << "DomTree node " << BlockNamePrinter(BB)
1305  << " not found by DFS walk!\n";
1306  errs().flush();
1307 
1308  return false;
1309  }
1310  }
1311 
1312  for (const NodePtr N : NumToNode) {
1313  if (N && !DT.getNode(N)) {
1314  errs() << "CFG node " << BlockNamePrinter(N)
1315  << " not found in the DomTree!\n";
1316  errs().flush();
1317 
1318  return false;
1319  }
1320  }
1321 
1322  return true;
1323  }
1324 
1325  // Check if for every parent with a level L in the tree all of its children
1326  // have level L + 1.
1327  // Running time: O(N).
1328  static bool VerifyLevels(const DomTreeT &DT) {
1329  for (auto &NodeToTN : DT.DomTreeNodes) {
1330  const TreeNodePtr TN = NodeToTN.second.get();
1331  const NodePtr BB = TN->getBlock();
1332  if (!BB) continue;
1333 
1334  const TreeNodePtr IDom = TN->getIDom();
1335  if (!IDom && TN->getLevel() != 0) {
1336  errs() << "Node without an IDom " << BlockNamePrinter(BB)
1337  << " has a nonzero level " << TN->getLevel() << "!\n";
1338  errs().flush();
1339 
1340  return false;
1341  }
1342 
1343  if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
1344  errs() << "Node " << BlockNamePrinter(BB) << " has level "
1345  << TN->getLevel() << " while its IDom "
1346  << BlockNamePrinter(IDom->getBlock()) << " has level "
1347  << IDom->getLevel() << "!\n";
1348  errs().flush();
1349 
1350  return false;
1351  }
1352  }
1353 
1354  return true;
1355  }
1356 
1357  // Check if the computed DFS numbers are correct. Note that DFS info may not
1358  // be valid, and when that is the case, we don't verify the numbers.
1359  // Running time: O(N log(N)).
1360  static bool VerifyDFSNumbers(const DomTreeT &DT) {
1361  if (!DT.DFSInfoValid || !DT.Parent)
1362  return true;
1363 
1364  const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
1365  const TreeNodePtr Root = DT.getNode(RootBB);
1366 
1367  auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
1368  errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
1369  << TN->getDFSNumOut() << '}';
1370  };
1371 
1372  // Verify the root's DFS In number. Although DFS numbering would also work
1373  // if we started from some other value, we assume 0-based numbering.
1374  if (Root->getDFSNumIn() != 0) {
1375  errs() << "DFSIn number for the tree root is not:\n\t";
1376  PrintNodeAndDFSNums(Root);
1377  errs() << '\n';
1378  errs().flush();
1379  return false;
1380  }
1381 
1382  // For each tree node verify if children's DFS numbers cover their parent's
1383  // DFS numbers with no gaps.
1384  for (const auto &NodeToTN : DT.DomTreeNodes) {
1385  const TreeNodePtr Node = NodeToTN.second.get();
1386 
1387  // Handle tree leaves.
1388  if (Node->getChildren().empty()) {
1389  if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
1390  errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1391  PrintNodeAndDFSNums(Node);
1392  errs() << '\n';
1393  errs().flush();
1394  return false;
1395  }
1396 
1397  continue;
1398  }
1399 
1400  // Make a copy and sort it such that it is possible to check if there are
1401  // no gaps between DFS numbers of adjacent children.
1402  SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
1403  llvm::sort(Children, [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
1404  return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
1405  });
1406 
1407  auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
1408  const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
1409  assert(FirstCh);
1410 
1411  errs() << "Incorrect DFS numbers for:\n\tParent ";
1412  PrintNodeAndDFSNums(Node);
1413 
1414  errs() << "\n\tChild ";
1415  PrintNodeAndDFSNums(FirstCh);
1416 
1417  if (SecondCh) {
1418  errs() << "\n\tSecond child ";
1419  PrintNodeAndDFSNums(SecondCh);
1420  }
1421 
1422  errs() << "\nAll children: ";
1423  for (const TreeNodePtr Ch : Children) {
1424  PrintNodeAndDFSNums(Ch);
1425  errs() << ", ";
1426  }
1427 
1428  errs() << '\n';
1429  errs().flush();
1430  };
1431 
1432  if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
1433  PrintChildrenError(Children.front(), nullptr);
1434  return false;
1435  }
1436 
1437  if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
1438  PrintChildrenError(Children.back(), nullptr);
1439  return false;
1440  }
1441 
1442  for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
1443  if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
1444  PrintChildrenError(Children[i], Children[i + 1]);
1445  return false;
1446  }
1447  }
1448  }
1449 
1450  return true;
1451  }
1452 
1453  // The below routines verify the correctness of the dominator tree relative to
1454  // the CFG it's coming from. A tree is a dominator tree iff it has two
1455  // properties, called the parent property and the sibling property. Tarjan
1456  // and Lengauer prove (but don't explicitly name) the properties as part of
1457  // the proofs in their 1972 paper, but the proofs are mostly part of proving
1458  // things about semidominators and idoms, and some of them are simply asserted
1459  // based on even earlier papers (see, e.g., lemma 2). Some papers refer to
1460  // these properties as "valid" and "co-valid". See, e.g., "Dominators,
1461  // directed bipolar orders, and independent spanning trees" by Loukas
1462  // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
1463  // and Vertex-Disjoint Paths " by the same authors.
1464 
1465  // A very simple and direct explanation of these properties can be found in
1466  // "An Experimental Study of Dynamic Dominators", found at
1467  // https://arxiv.org/abs/1604.02711
1468 
1469  // The easiest way to think of the parent property is that it's a requirement
1470  // of being a dominator. Let's just take immediate dominators. For PARENT to
1471  // be an immediate dominator of CHILD, all paths in the CFG must go through
1472  // PARENT before they hit CHILD. This implies that if you were to cut PARENT
1473  // out of the CFG, there should be no paths to CHILD that are reachable. If
1474  // there are, then you now have a path from PARENT to CHILD that goes around
1475  // PARENT and still reaches CHILD, which by definition, means PARENT can't be
1476  // a dominator of CHILD (let alone an immediate one).
1477 
1478  // The sibling property is similar. It says that for each pair of sibling
1479  // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
1480  // other. If sibling LEFT dominated sibling RIGHT, it means there are no
1481  // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
1482  // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
1483  // RIGHT, not a sibling.
1484 
1485  // It is possible to verify the parent and sibling properties in
1486  // linear time, but the algorithms are complex. Instead, we do it in a
1487  // straightforward N^2 and N^3 way below, using direct path reachability.
1488 
1489  // Checks if the tree has the parent property: if for all edges from V to W in
1490  // the input graph, such that V is reachable, the parent of W in the tree is
1491  // an ancestor of V in the tree.
1492  // Running time: O(N^2).
1493  //
1494  // This means that if a node gets disconnected from the graph, then all of
1495  // the nodes it dominated previously will now become unreachable.
1496  bool verifyParentProperty(const DomTreeT &DT) {
1497  for (auto &NodeToTN : DT.DomTreeNodes) {
1498  const TreeNodePtr TN = NodeToTN.second.get();
1499  const NodePtr BB = TN->getBlock();
1500  if (!BB || TN->getChildren().empty()) continue;
1501 
1502  LLVM_DEBUG(dbgs() << "Verifying parent property of node "
1503  << BlockNamePrinter(TN) << "\n");
1504  clear();
1505  doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
1506  return From != BB && To != BB;
1507  });
1508 
1509  for (TreeNodePtr Child : TN->getChildren())
1510  if (NodeToInfo.count(Child->getBlock()) != 0) {
1511  errs() << "Child " << BlockNamePrinter(Child)
1512  << " reachable after its parent " << BlockNamePrinter(BB)
1513  << " is removed!\n";
1514  errs().flush();
1515 
1516  return false;
1517  }
1518  }
1519 
1520  return true;
1521  }
1522 
1523  // Check if the tree has sibling property: if a node V does not dominate a
1524  // node W for all siblings V and W in the tree.
1525  // Running time: O(N^3).
1526  //
1527  // This means that if a node gets disconnected from the graph, then all of its
1528  // siblings will now still be reachable.
1529  bool verifySiblingProperty(const DomTreeT &DT) {
1530  for (auto &NodeToTN : DT.DomTreeNodes) {
1531  const TreeNodePtr TN = NodeToTN.second.get();
1532  const NodePtr BB = TN->getBlock();
1533  if (!BB || TN->getChildren().empty()) continue;
1534 
1535  const auto &Siblings = TN->getChildren();
1536  for (const TreeNodePtr N : Siblings) {
1537  clear();
1538  NodePtr BBN = N->getBlock();
1539  doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
1540  return From != BBN && To != BBN;
1541  });
1542 
1543  for (const TreeNodePtr S : Siblings) {
1544  if (S == N) continue;
1545 
1546  if (NodeToInfo.count(S->getBlock()) == 0) {
1547  errs() << "Node " << BlockNamePrinter(S)
1548  << " not reachable when its sibling " << BlockNamePrinter(N)
1549  << " is removed!\n";
1550  errs().flush();
1551 
1552  return false;
1553  }
1554  }
1555  }
1556  }
1557 
1558  return true;
1559  }
1560 
1561  // Check if the given tree is the same as a freshly computed one for the same
1562  // Parent.
1563  // Running time: O(N^2), but faster in practise (same as tree construction).
1564  //
1565  // Note that this does not check if that the tree construction algorithm is
1566  // correct and should be only used for fast (but possibly unsound)
1567  // verification.
1568  static bool IsSameAsFreshTree(const DomTreeT &DT) {
1569  DomTreeT FreshTree;
1570  FreshTree.recalculate(*DT.Parent);
1571  const bool Different = DT.compare(FreshTree);
1572 
1573  if (Different) {
1574  errs() << (DT.isPostDominator() ? "Post" : "")
1575  << "DominatorTree is different than a freshly computed one!\n"
1576  << "\tCurrent:\n";
1577  DT.print(errs());
1578  errs() << "\n\tFreshly computed tree:\n";
1579  FreshTree.print(errs());
1580  errs().flush();
1581  }
1582 
1583  return !Different;
1584  }
1585 };
1586 
1587 template <class DomTreeT>
1588 void Calculate(DomTreeT &DT) {
1590 }
1591 
1592 template <typename DomTreeT>
1593 void CalculateWithUpdates(DomTreeT &DT,
1595  // TODO: Move BUI creation in common method, reuse in ApplyUpdates.
1597  LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
1598  cfg::LegalizeUpdates<typename DomTreeT::NodePtr>(Updates, BUI.Updates,
1599  DomTreeT::IsPostDominator);
1600  const size_t NumLegalized = BUI.Updates.size();
1601  BUI.FutureSuccessors.reserve(NumLegalized);
1602  BUI.FuturePredecessors.reserve(NumLegalized);
1603  for (auto &U : BUI.Updates) {
1604  BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
1605  BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
1606  }
1607 
1609 }
1610 
1611 template <class DomTreeT>
1612 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1613  typename DomTreeT::NodePtr To) {
1614  if (DT.isPostDominator()) std::swap(From, To);
1615  SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
1616 }
1617 
1618 template <class DomTreeT>
1619 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1620  typename DomTreeT::NodePtr To) {
1621  if (DT.isPostDominator()) std::swap(From, To);
1622  SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
1623 }
1624 
1625 template <class DomTreeT>
1626 void ApplyUpdates(DomTreeT &DT,
1629 }
1630 
1631 template <class DomTreeT>
1632 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
1633  SemiNCAInfo<DomTreeT> SNCA(nullptr);
1634 
1635  // Simplist check is to compare against a new tree. This will also
1636  // usefully print the old and new trees, if they are different.
1637  if (!SNCA.IsSameAsFreshTree(DT))
1638  return false;
1639 
1640  // Common checks to verify the properties of the tree. O(N log N) at worst
1641  if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1642  !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1643  return false;
1644 
1645  // Extra checks depending on VerificationLevel. Up to O(N^3)
1648  if (!SNCA.verifyParentProperty(DT))
1649  return false;
1651  if (!SNCA.verifySiblingProperty(DT))
1652  return false;
1653 
1654  return true;
1655 }
1656 
1657 } // namespace DomTreeBuilder
1658 } // namespace llvm
1659 
1660 #undef DEBUG_TYPE
1661 
1662 #endif
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:152
static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr NCD, InsertionInfo &II)
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
DenseMap< NodePtr, InfoRec > NodeToInfo
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN)
This class represents lattice values for constants.
Definition: AllocatorList.h:24
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI)
void push_back(const T &Elt)
Definition: SmallVector.h:218
void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC)
SmallDenseMap< TreeNodePtr, unsigned, 8 > Visited
std::enable_if<!std::is_array< T >::value, std::unique_ptr< T > >::type make_unique(Args &&... args)
Constructs a new T() with the given args and returns a unique_ptr<T> which owns the object...
Definition: STLExtras.h:1343
std::priority_queue< BucketElementTy, SmallVector< BucketElementTy, 8 >, DecreasingLevel > Bucket
static bool VerifyLevels(const DomTreeT &DT)
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:39
static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI)
NodePtr eval(NodePtr VIn, unsigned LastLinked)
void runSemiNCA(DomTreeT &DT, const unsigned MinLevel=0)
static ManagedStatic< DebugCounter > DC
static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, RootsT &Roots)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1194
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
static bool IsSameAsFreshTree(const DomTreeT &DT)
bool operator()(const BucketElementTy &First, const BucketElementTy &Second) const
static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
Base class for the actual dominator tree node.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
const std::vector< DomTreeNodeBase * > & getChildren() const
static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI)
unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum)
typename DomTreeT::UpdateKind UpdateKind
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree...
NodeT * getBlock() const
static ResultTy Get(NodePtr N, std::integral_constant< bool, true >)
typename DomTreeT::UpdateType UpdateT
PointerIntPair - This class implements a pair of a pointer and small integer.
std::shared_ptr< Node > NodePtr
Short-hand for a Node pointer.
Definition: MsgPackTypes.h:33
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
DomTreeNodeBase * getIDom() const
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
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 ResultTy Get(NodePtr N, BatchUpdatePtr BUI)
static void UpdateLevelsAfterInsertion(InsertionInfo &II)
static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI)
unsigned getDFSNumOut() const
iterator erase(const_iterator CI)
Definition: SmallVector.h:445
size_t size() const
Definition: SmallVector.h:53
static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr FromTN, const TreeNodePtr ToTN)
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:1201
static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1110
static void ApplyUpdates(DomTreeT &DT, ArrayRef< UpdateT > Updates)
void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN, const unsigned RootLevel, const TreeNodePtr NCD, InsertionInfo &II)
static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
BlockVerifier::State From
size_t getNumChildren() const
static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN)
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
static bool VerifyDFSNumbers(const DomTreeT &DT)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:268
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr ToTN)
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)
static bool AlwaysDescend(NodePtr, NodePtr)
friend raw_ostream & operator<<(raw_ostream &O, const BlockNamePrinter &BP)
std::unique_ptr< DomTreeNodeBase > addChild(std::unique_ptr< DomTreeNodeBase > C)
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Definition: GraphTraits.h:109
void attachNewSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static NodePtr GetEntryNode(const DomTreeT &DT)
static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
static void ComputeUnreachableDominators(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, const TreeNodePtr Incoming, SmallVectorImpl< std::pair< NodePtr, TreeNodePtr >> &DiscoveredConnectingEdges)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
unsigned getLevel() const
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const NodePtr To)
#define LLVM_DEBUG(X)
Definition: Debug.h:123
TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT)
DenseMap< NodePtr, SmallVector< NodePtrAndKind, 4 > > FutureSuccessors
DenseMap< NodePtr, SmallVector< NodePtrAndKind, 4 > > FuturePredecessors
static ResultTy Get(NodePtr N, std::integral_constant< bool, false >)
void setIDom(DomTreeNodeBase *NewIDom)