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