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