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