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