LLVM  14.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 aleady 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  SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
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  ConnectToExitBlock.insert(FurthestAway);
461  Roots.push_back(FurthestAway);
462  LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
463  << NewNum << "\n\t\t\tRemoving DFS info\n");
464  for (unsigned i = NewNum; i > Num; --i) {
465  const NodePtr N = SNCA.NumToNode[i];
466  LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
467  << BlockNamePrinter(N) << "\n");
468  SNCA.NodeToInfo.erase(N);
469  SNCA.NumToNode.pop_back();
470  }
471  const unsigned PrevNum = Num;
472  LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
473  Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
474  for (unsigned i = PrevNum + 1; i <= Num; ++i)
475  LLVM_DEBUG(dbgs() << "\t\t\t\tfound node "
476  << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
477  }
478  }
479  }
480 
481  LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
482  LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n");
483  LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
484  << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
485 
486  assert((Total + 1 == Num) && "Everything should have been visited");
487 
488  // Step #3: If we found some non-trivial roots, make them non-redundant.
489  if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
490 
491  LLVM_DEBUG(dbgs() << "Found roots: ");
492  LLVM_DEBUG(for (auto *Root
493  : Roots) dbgs()
494  << BlockNamePrinter(Root) << " ");
495  LLVM_DEBUG(dbgs() << "\n");
496 
497  return Roots;
498  }
499 
500  // This function only makes sense for postdominators.
501  // We define roots to be some set of CFG nodes where (reverse) DFS walks have
502  // to start in order to visit all the CFG nodes (including the
503  // reverse-unreachable ones).
504  // When the search for non-trivial roots is done it may happen that some of
505  // the non-trivial roots are reverse-reachable from other non-trivial roots,
506  // which makes them redundant. This function removes them from the set of
507  // input roots.
508  static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
509  RootsT &Roots) {
510  assert(IsPostDom && "This function is for postdominators only");
511  LLVM_DEBUG(dbgs() << "Removing redundant roots\n");
512 
513  SemiNCAInfo SNCA(BUI);
514 
515  for (unsigned i = 0; i < Roots.size(); ++i) {
516  auto &Root = Roots[i];
517  // Trivial roots are always non-redundant.
518  if (!HasForwardSuccessors(Root, BUI)) continue;
519  LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
520  << " remains a root\n");
521  SNCA.clear();
522  // Do a forward walk looking for the other roots.
523  const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
524  // Skip the start node and begin from the second one (note that DFS uses
525  // 1-based indexing).
526  for (unsigned x = 2; x <= Num; ++x) {
527  const NodePtr N = SNCA.NumToNode[x];
528  // If we wound another root in a (forward) DFS walk, remove the current
529  // root from the set of roots, as it is reverse-reachable from the other
530  // one.
531  if (llvm::is_contained(Roots, N)) {
532  LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "
533  << BlockNamePrinter(N) << "\n\tRemoving root "
534  << BlockNamePrinter(Root) << "\n");
535  std::swap(Root, Roots.back());
536  Roots.pop_back();
537 
538  // Root at the back takes the current root's place.
539  // Start the next loop iteration with the same index.
540  --i;
541  break;
542  }
543  }
544  }
545  }
546 
547  template <typename DescendCondition>
548  void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
549  if (!IsPostDom) {
550  assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
551  runDFS(DT.Roots[0], 0, DC, 0);
552  return;
553  }
554 
555  addVirtualRoot();
556  unsigned Num = 1;
557  for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
558  }
559 
560  static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
561  auto *Parent = DT.Parent;
562  DT.reset();
563  DT.Parent = Parent;
564  // If the update is using the actual CFG, BUI is null. If it's using a view,
565  // BUI is non-null and the PreCFGView is used. When calculating from
566  // scratch, make the PreViewCFG equal to the PostCFGView, so Post is used.
567  BatchUpdatePtr PostViewBUI = nullptr;
568  if (BUI && BUI->PostViewCFG) {
569  BUI->PreViewCFG = *BUI->PostViewCFG;
570  PostViewBUI = BUI;
571  }
572  // This is rebuilding the whole tree, not incrementally, but PostViewBUI is
573  // used in case the caller needs a DT update with a CFGView.
574  SemiNCAInfo SNCA(PostViewBUI);
575 
576  // Step #0: Number blocks in depth-first order and initialize variables used
577  // in later stages of the algorithm.
578  DT.Roots = FindRoots(DT, PostViewBUI);
579  SNCA.doFullDFSWalk(DT, AlwaysDescend);
580 
581  SNCA.runSemiNCA(DT);
582  if (BUI) {
583  BUI->IsRecalculated = true;
584  LLVM_DEBUG(
585  dbgs() << "DomTree recalculated, skipping future batch updates\n");
586  }
587 
588  if (DT.Roots.empty()) return;
589 
590  // Add a node for the root. If the tree is a PostDominatorTree it will be
591  // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
592  // all real exits (including multiple exit blocks, infinite loops).
593  NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
594 
595  DT.RootNode = DT.createNode(Root);
596  SNCA.attachNewSubtree(DT, DT.RootNode);
597  }
598 
599  void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
600  // Attach the first unreachable block to AttachTo.
601  NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
602  // Loop over all of the discovered blocks in the function...
603  for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
604  NodePtr W = NumToNode[i];
605 
606  // Don't replace this with 'count', the insertion side effect is important
607  if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet?
608 
609  NodePtr ImmDom = getIDom(W);
610 
611  // Get or calculate the node for the immediate dominator.
612  TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
613 
614  // Add a new tree node for this BasicBlock, and link it as a child of
615  // IDomNode.
616  DT.createChild(W, IDomNode);
617  }
618  }
619 
620  void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
621  NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
622  for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
623  const NodePtr N = NumToNode[i];
624  const TreeNodePtr TN = DT.getNode(N);
625  assert(TN);
626  const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
627  TN->setIDom(NewIDom);
628  }
629  }
630 
631  // Helper struct used during edge insertions.
632  struct InsertionInfo {
633  struct Compare {
634  bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const {
635  return LHS->getLevel() < RHS->getLevel();
636  }
637  };
638 
639  // Bucket queue of tree nodes ordered by descending level. For simplicity,
640  // we use a priority_queue here.
641  std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,
642  Compare>
646 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
647  SmallVector<TreeNodePtr, 8> VisitedUnaffected;
648 #endif
649  };
650 
651  static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
652  const NodePtr From, const NodePtr To) {
653  assert((From || IsPostDom) &&
654  "From has to be a valid CFG node or a virtual root");
655  assert(To && "Cannot be a nullptr");
656  LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
657  << BlockNamePrinter(To) << "\n");
658  TreeNodePtr FromTN = DT.getNode(From);
659 
660  if (!FromTN) {
661  // Ignore edges from unreachable nodes for (forward) dominators.
662  if (!IsPostDom) return;
663 
664  // The unreachable node becomes a new root -- a tree node for it.
665  TreeNodePtr VirtualRoot = DT.getNode(nullptr);
666  FromTN = DT.createChild(From, VirtualRoot);
667  DT.Roots.push_back(From);
668  }
669 
670  DT.DFSInfoValid = false;
671 
672  const TreeNodePtr ToTN = DT.getNode(To);
673  if (!ToTN)
674  InsertUnreachable(DT, BUI, FromTN, To);
675  else
676  InsertReachable(DT, BUI, FromTN, ToTN);
677  }
678 
679  // Determines if some existing root becomes reverse-reachable after the
680  // insertion. Rebuilds the whole tree if that situation happens.
681  static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
682  const TreeNodePtr From,
683  const TreeNodePtr To) {
684  assert(IsPostDom && "This function is only for postdominators");
685  // Destination node is not attached to the virtual root, so it cannot be a
686  // root.
687  if (!DT.isVirtualRoot(To->getIDom())) return false;
688 
689  if (!llvm::is_contained(DT.Roots, To->getBlock()))
690  return false; // To is not a root, nothing to update.
691 
692  LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
693  << " is no longer a root\n\t\tRebuilding the tree!!!\n");
694 
695  CalculateFromScratch(DT, BUI);
696  return true;
697  }
698 
700  const SmallVectorImpl<NodePtr> &B) {
701  if (A.size() != B.size())
702  return false;
703  SmallPtrSet<NodePtr, 4> Set(A.begin(), A.end());
704  for (NodePtr N : B)
705  if (Set.count(N) == 0)
706  return false;
707  return true;
708  }
709 
710  // Updates the set of roots after insertion or deletion. This ensures that
711  // roots are the same when after a series of updates and when the tree would
712  // be built from scratch.
713  static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
714  assert(IsPostDom && "This function is only for postdominators");
715 
716  // The tree has only trivial roots -- nothing to update.
717  if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
718  return HasForwardSuccessors(N, BUI);
719  }))
720  return;
721 
722  // Recalculate the set of roots.
723  RootsT Roots = FindRoots(DT, BUI);
724  if (!isPermutation(DT.Roots, Roots)) {
725  // The roots chosen in the CFG have changed. This is because the
726  // incremental algorithm does not really know or use the set of roots and
727  // can make a different (implicit) decision about which node within an
728  // infinite loop becomes a root.
729 
730  LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"
731  << "The entire tree needs to be rebuilt\n");
732  // It may be possible to update the tree without recalculating it, but
733  // we do not know yet how to do it, and it happens rarely in practice.
734  CalculateFromScratch(DT, BUI);
735  }
736  }
737 
738  // Handles insertion to a node already in the dominator tree.
739  static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
740  const TreeNodePtr From, const TreeNodePtr To) {
741  LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
742  << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
743  if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
744  // DT.findNCD expects both pointers to be valid. When From is a virtual
745  // root, then its CFG block pointer is a nullptr, so we have to 'compute'
746  // the NCD manually.
747  const NodePtr NCDBlock =
748  (From->getBlock() && To->getBlock())
749  ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
750  : nullptr;
751  assert(NCDBlock || DT.isPostDominator());
752  const TreeNodePtr NCD = DT.getNode(NCDBlock);
753  assert(NCD);
754 
755  LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
756  const unsigned NCDLevel = NCD->getLevel();
757 
758  // Based on Lemma 2.5 from [2], after insertion of (From,To), v is affected
759  // iff depth(NCD)+1 < depth(v) && a path P from To to v exists where every
760  // w on P s.t. depth(v) <= depth(w)
761  //
762  // This reduces to a widest path problem (maximizing the depth of the
763  // minimum vertex in the path) which can be solved by a modified version of
764  // Dijkstra with a bucket queue (named depth-based search in [2]).
765 
766  // To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing
767  // affected if this does not hold.
768  if (NCDLevel + 1 >= To->getLevel())
769  return;
770 
771  InsertionInfo II;
772  SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel;
773  II.Bucket.push(To);
774  II.Visited.insert(To);
775 
776  while (!II.Bucket.empty()) {
777  TreeNodePtr TN = II.Bucket.top();
778  II.Bucket.pop();
779  II.Affected.push_back(TN);
780 
781  const unsigned CurrentLevel = TN->getLevel();
782  LLVM_DEBUG(dbgs() << "Mark " << BlockNamePrinter(TN) <<
783  "as affected, CurrentLevel " << CurrentLevel << "\n");
784 
785  assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
786 
787  while (true) {
788  // Unlike regular Dijkstra, we have an inner loop to expand more
789  // vertices. The first iteration is for the (affected) vertex popped
790  // from II.Bucket and the rest are for vertices in
791  // UnaffectedOnCurrentLevel, which may eventually expand to affected
792  // vertices.
793  //
794  // Invariant: there is an optimal path from `To` to TN with the minimum
795  // depth being CurrentLevel.
796  for (const NodePtr Succ : getChildren<IsPostDom>(TN->getBlock(), BUI)) {
797  const TreeNodePtr SuccTN = DT.getNode(Succ);
798  assert(SuccTN &&
799  "Unreachable successor found at reachable insertion");
800  const unsigned SuccLevel = SuccTN->getLevel();
801 
802  LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
803  << ", level = " << SuccLevel << "\n");
804 
805  // There is an optimal path from `To` to Succ with the minimum depth
806  // being min(CurrentLevel, SuccLevel).
807  //
808  // If depth(NCD)+1 < depth(Succ) is not satisfied, Succ is unaffected
809  // and no affected vertex may be reached by a path passing through it.
810  // Stop here. Also, Succ may be visited by other predecessors but the
811  // first visit has the optimal path. Stop if Succ has been visited.
812  if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)
813  continue;
814 
815  if (SuccLevel > CurrentLevel) {
816  // Succ is unaffected but it may (transitively) expand to affected
817  // vertices. Store it in UnaffectedOnCurrentLevel.
818  LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
819  << BlockNamePrinter(Succ) << "\n");
820  UnaffectedOnCurrentLevel.push_back(SuccTN);
821 #ifndef NDEBUG
822  II.VisitedUnaffected.push_back(SuccTN);
823 #endif
824  } else {
825  // The condition is satisfied (Succ is affected). Add Succ to the
826  // bucket queue.
827  LLVM_DEBUG(dbgs() << "\t\tAdd " << BlockNamePrinter(Succ)
828  << " to a Bucket\n");
829  II.Bucket.push(SuccTN);
830  }
831  }
832 
833  if (UnaffectedOnCurrentLevel.empty())
834  break;
835  TN = UnaffectedOnCurrentLevel.pop_back_val();
836  LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n");
837  }
838  }
839 
840  // Finish by updating immediate dominators and levels.
841  UpdateInsertion(DT, BUI, NCD, II);
842  }
843 
844  // Updates immediate dominators and levels after insertion.
845  static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
846  const TreeNodePtr NCD, InsertionInfo &II) {
847  LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
848 
849  for (const TreeNodePtr TN : II.Affected) {
850  LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
851  << ") = " << BlockNamePrinter(NCD) << "\n");
852  TN->setIDom(NCD);
853  }
854 
855 #if defined(LLVM_ENABLE_ABI_BREAKING_CHECKS) && !defined(NDEBUG)
856  for (const TreeNodePtr TN : II.VisitedUnaffected)
857  assert(TN->getLevel() == TN->getIDom()->getLevel() + 1 &&
858  "TN should have been updated by an affected ancestor");
859 #endif
860 
861  if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
862  }
863 
864  // Handles insertion to previously unreachable nodes.
865  static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
866  const TreeNodePtr From, const NodePtr To) {
867  LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
868  << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
869 
870  // Collect discovered edges to already reachable nodes.
871  SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
872  // Discover and connect nodes that became reachable with the insertion.
873  ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
874 
875  LLVM_DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
876  << " -> (prev unreachable) " << BlockNamePrinter(To)
877  << "\n");
878 
879  // Used the discovered edges and inset discovered connecting (incoming)
880  // edges.
881  for (const auto &Edge : DiscoveredEdgesToReachable) {
882  LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "
883  << BlockNamePrinter(Edge.first) << " -> "
884  << BlockNamePrinter(Edge.second) << "\n");
885  InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
886  }
887  }
888 
889  // Connects nodes that become reachable with an insertion.
891  DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
892  const TreeNodePtr Incoming,
893  SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
894  &DiscoveredConnectingEdges) {
895  assert(!DT.getNode(Root) && "Root must not be reachable");
896 
897  // Visit only previously unreachable nodes.
898  auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
899  NodePtr To) {
900  const TreeNodePtr ToTN = DT.getNode(To);
901  if (!ToTN) return true;
902 
903  DiscoveredConnectingEdges.push_back({From, ToTN});
904  return false;
905  };
906 
907  SemiNCAInfo SNCA(BUI);
908  SNCA.runDFS(Root, 0, UnreachableDescender, 0);
909  SNCA.runSemiNCA(DT);
910  SNCA.attachNewSubtree(DT, Incoming);
911 
912  LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");
913  }
914 
915  static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
916  const NodePtr From, const NodePtr To) {
917  assert(From && To && "Cannot disconnect nullptrs");
918  LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
919  << BlockNamePrinter(To) << "\n");
920 
921 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
922  // Ensure that the edge was in fact deleted from the CFG before informing
923  // the DomTree about it.
924  // The check is O(N), so run it only in debug configuration.
925  auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
926  auto Successors = getChildren<IsPostDom>(Of, BUI);
927  return llvm::is_contained(Successors, SuccCandidate);
928  };
929  (void)IsSuccessor;
930  assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
931 #endif
932 
933  const TreeNodePtr FromTN = DT.getNode(From);
934  // Deletion in an unreachable subtree -- nothing to do.
935  if (!FromTN) return;
936 
937  const TreeNodePtr ToTN = DT.getNode(To);
938  if (!ToTN) {
939  LLVM_DEBUG(
940  dbgs() << "\tTo (" << BlockNamePrinter(To)
941  << ") already unreachable -- there is no edge to delete\n");
942  return;
943  }
944 
945  const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
946  const TreeNodePtr NCD = DT.getNode(NCDBlock);
947 
948  // If To dominates From -- nothing to do.
949  if (ToTN != NCD) {
950  DT.DFSInfoValid = false;
951 
952  const TreeNodePtr ToIDom = ToTN->getIDom();
953  LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
954  << BlockNamePrinter(ToIDom) << "\n");
955 
956  // To remains reachable after deletion.
957  // (Based on the caption under Figure 4. from [2].)
958  if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
959  DeleteReachable(DT, BUI, FromTN, ToTN);
960  else
961  DeleteUnreachable(DT, BUI, ToTN);
962  }
963 
964  if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
965  }
966 
967  // Handles deletions that leave destination nodes reachable.
968  static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
969  const TreeNodePtr FromTN,
970  const TreeNodePtr ToTN) {
971  LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN)
972  << " -> " << BlockNamePrinter(ToTN) << "\n");
973  LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n");
974 
975  // Find the top of the subtree that needs to be rebuilt.
976  // (Based on the lemma 2.6 from [2].)
977  const NodePtr ToIDom =
978  DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
979  assert(ToIDom || DT.isPostDominator());
980  const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
981  assert(ToIDomTN);
982  const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
983  // Top of the subtree to rebuild is the root node. Rebuild the tree from
984  // scratch.
985  if (!PrevIDomSubTree) {
986  LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
987  CalculateFromScratch(DT, BUI);
988  return;
989  }
990 
991  // Only visit nodes in the subtree starting at To.
992  const unsigned Level = ToIDomTN->getLevel();
993  auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
994  return DT.getNode(To)->getLevel() > Level;
995  };
996 
997  LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN)
998  << "\n");
999 
1000  SemiNCAInfo SNCA(BUI);
1001  SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
1002  LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
1003  SNCA.runSemiNCA(DT, Level);
1004  SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
1005  }
1006 
1007  // Checks if a node has proper support, as defined on the page 3 and later
1008  // explained on the page 7 of [2].
1009  static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
1010  const TreeNodePtr TN) {
1011  LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
1012  << "\n");
1013  auto TNB = TN->getBlock();
1014  for (const NodePtr Pred : getChildren<!IsPostDom>(TNB, BUI)) {
1015  LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
1016  if (!DT.getNode(Pred)) continue;
1017 
1018  const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);
1019  LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
1020  if (Support != TNB) {
1021  LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
1022  << " is reachable from support "
1023  << BlockNamePrinter(Support) << "\n");
1024  return true;
1025  }
1026  }
1027 
1028  return false;
1029  }
1030 
1031  // Handle deletions that make destination node unreachable.
1032  // (Based on the lemma 2.7 from the [2].)
1033  static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
1034  const TreeNodePtr ToTN) {
1035  LLVM_DEBUG(dbgs() << "Deleting unreachable subtree "
1036  << BlockNamePrinter(ToTN) << "\n");
1037  assert(ToTN);
1038  assert(ToTN->getBlock());
1039 
1040  if (IsPostDom) {
1041  // Deletion makes a region reverse-unreachable and creates a new root.
1042  // Simulate that by inserting an edge from the virtual root to ToTN and
1043  // adding it as a new root.
1044  LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
1045  LLVM_DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN)
1046  << "\n");
1047  DT.Roots.push_back(ToTN->getBlock());
1048  InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
1049  return;
1050  }
1051 
1052  SmallVector<NodePtr, 16> AffectedQueue;
1053  const unsigned Level = ToTN->getLevel();
1054 
1055  // Traverse destination node's descendants with greater level in the tree
1056  // and collect visited nodes.
1057  auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
1058  const TreeNodePtr TN = DT.getNode(To);
1059  assert(TN);
1060  if (TN->getLevel() > Level) return true;
1061  if (!llvm::is_contained(AffectedQueue, To))
1062  AffectedQueue.push_back(To);
1063 
1064  return false;
1065  };
1066 
1067  SemiNCAInfo SNCA(BUI);
1068  unsigned LastDFSNum =
1069  SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
1070 
1071  TreeNodePtr MinNode = ToTN;
1072 
1073  // Identify the top of the subtree to rebuild by finding the NCD of all
1074  // the affected nodes.
1075  for (const NodePtr N : AffectedQueue) {
1076  const TreeNodePtr TN = DT.getNode(N);
1077  const NodePtr NCDBlock =
1078  DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
1079  assert(NCDBlock || DT.isPostDominator());
1080  const TreeNodePtr NCD = DT.getNode(NCDBlock);
1081  assert(NCD);
1082 
1083  LLVM_DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
1084  << " with NCD = " << BlockNamePrinter(NCD)
1085  << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
1086  if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
1087  }
1088 
1089  // Root reached, rebuild the whole tree from scratch.
1090  if (!MinNode->getIDom()) {
1091  LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
1092  CalculateFromScratch(DT, BUI);
1093  return;
1094  }
1095 
1096  // Erase the unreachable subtree in reverse preorder to process all children
1097  // before deleting their parent.
1098  for (unsigned i = LastDFSNum; i > 0; --i) {
1099  const NodePtr N = SNCA.NumToNode[i];
1100  const TreeNodePtr TN = DT.getNode(N);
1101  LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
1102 
1103  EraseNode(DT, TN);
1104  }
1105 
1106  // The affected subtree start at the To node -- there's no extra work to do.
1107  if (MinNode == ToTN) return;
1108 
1109  LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
1110  << BlockNamePrinter(MinNode) << "\n");
1111  const unsigned MinLevel = MinNode->getLevel();
1112  const TreeNodePtr PrevIDom = MinNode->getIDom();
1113  assert(PrevIDom);
1114  SNCA.clear();
1115 
1116  // Identify nodes that remain in the affected subtree.
1117  auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
1118  const TreeNodePtr ToTN = DT.getNode(To);
1119  return ToTN && ToTN->getLevel() > MinLevel;
1120  };
1121  SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
1122 
1123  LLVM_DEBUG(dbgs() << "Previous IDom(MinNode) = "
1124  << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n");
1125 
1126  // Rebuild the remaining part of affected subtree.
1127  SNCA.runSemiNCA(DT, MinLevel);
1128  SNCA.reattachExistingSubtree(DT, PrevIDom);
1129  }
1130 
1131  // Removes leaf tree nodes from the dominator tree.
1132  static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
1133  assert(TN);
1134  assert(TN->getNumChildren() == 0 && "Not a tree leaf");
1135 
1136  const TreeNodePtr IDom = TN->getIDom();
1137  assert(IDom);
1138 
1139  auto ChIt = llvm::find(IDom->Children, TN);
1140  assert(ChIt != IDom->Children.end());
1141  std::swap(*ChIt, IDom->Children.back());
1142  IDom->Children.pop_back();
1143 
1144  DT.DomTreeNodes.erase(TN->getBlock());
1145  }
1146 
1147  //~~
1148  //===--------------------- DomTree Batch Updater --------------------------===
1149  //~~
1150 
1151  static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG,
1152  GraphDiffT *PostViewCFG) {
1153  // Note: the PostViewCFG is only used when computing from scratch. It's data
1154  // should already included in the PreViewCFG for incremental updates.
1155  const size_t NumUpdates = PreViewCFG.getNumLegalizedUpdates();
1156  if (NumUpdates == 0)
1157  return;
1158 
1159  // Take the fast path for a single update and avoid running the batch update
1160  // machinery.
1161  if (NumUpdates == 1) {
1162  UpdateT Update = PreViewCFG.popUpdateForIncrementalUpdates();
1163  if (!PostViewCFG) {
1164  if (Update.getKind() == UpdateKind::Insert)
1165  InsertEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo());
1166  else
1167  DeleteEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo());
1168  } else {
1169  BatchUpdateInfo BUI(*PostViewCFG, PostViewCFG);
1170  if (Update.getKind() == UpdateKind::Insert)
1171  InsertEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1172  else
1173  DeleteEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1174  }
1175  return;
1176  }
1177 
1178  BatchUpdateInfo BUI(PreViewCFG, PostViewCFG);
1179  // Recalculate the DominatorTree when the number of updates
1180  // exceeds a threshold, which usually makes direct updating slower than
1181  // recalculation. We select this threshold proportional to the
1182  // size of the DominatorTree. The constant is selected
1183  // by choosing the one with an acceptable performance on some real-world
1184  // inputs.
1185 
1186  // Make unittests of the incremental algorithm work
1187  if (DT.DomTreeNodes.size() <= 100) {
1188  if (BUI.NumLegalized > DT.DomTreeNodes.size())
1189  CalculateFromScratch(DT, &BUI);
1190  } else if (BUI.NumLegalized > DT.DomTreeNodes.size() / 40)
1191  CalculateFromScratch(DT, &BUI);
1192 
1193  // If the DominatorTree was recalculated at some point, stop the batch
1194  // updates. Full recalculations ignore batch updates and look at the actual
1195  // CFG.
1196  for (size_t i = 0; i < BUI.NumLegalized && !BUI.IsRecalculated; ++i)
1197  ApplyNextUpdate(DT, BUI);
1198  }
1199 
1200  static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
1201  // Popping the next update, will move the PreViewCFG to the next snapshot.
1202  UpdateT CurrentUpdate = BUI.PreViewCFG.popUpdateForIncrementalUpdates();
1203 #if 0
1204  // FIXME: The LLVM_DEBUG macro only plays well with a modular
1205  // build of LLVM when the header is marked as textual, but doing
1206  // so causes redefinition errors.
1207  LLVM_DEBUG(dbgs() << "Applying update: ");
1208  LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n");
1209 #endif
1210 
1211  if (CurrentUpdate.getKind() == UpdateKind::Insert)
1212  InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1213  else
1214  DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1215  }
1216 
1217  //~~
1218  //===--------------- DomTree correctness verification ---------------------===
1219  //~~
1220 
1221  // Check if the tree has correct roots. A DominatorTree always has a single
1222  // root which is the function's entry node. A PostDominatorTree can have
1223  // multiple roots - one for each node with no successors and for infinite
1224  // loops.
1225  // Running time: O(N).
1226  bool verifyRoots(const DomTreeT &DT) {
1227  if (!DT.Parent && !DT.Roots.empty()) {
1228  errs() << "Tree has no parent but has roots!\n";
1229  errs().flush();
1230  return false;
1231  }
1232 
1233  if (!IsPostDom) {
1234  if (DT.Roots.empty()) {
1235  errs() << "Tree doesn't have a root!\n";
1236  errs().flush();
1237  return false;
1238  }
1239 
1240  if (DT.getRoot() != GetEntryNode(DT)) {
1241  errs() << "Tree's root is not its parent's entry node!\n";
1242  errs().flush();
1243  return false;
1244  }
1245  }
1246 
1247  RootsT ComputedRoots = FindRoots(DT, nullptr);
1248  if (!isPermutation(DT.Roots, ComputedRoots)) {
1249  errs() << "Tree has different roots than freshly computed ones!\n";
1250  errs() << "\tPDT roots: ";
1251  for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
1252  errs() << "\n\tComputed roots: ";
1253  for (const NodePtr N : ComputedRoots)
1254  errs() << BlockNamePrinter(N) << ", ";
1255  errs() << "\n";
1256  errs().flush();
1257  return false;
1258  }
1259 
1260  return true;
1261  }
1262 
1263  // Checks if the tree contains all reachable nodes in the input graph.
1264  // Running time: O(N).
1265  bool verifyReachability(const DomTreeT &DT) {
1266  clear();
1268 
1269  for (auto &NodeToTN : DT.DomTreeNodes) {
1270  const TreeNodePtr TN = NodeToTN.second.get();
1271  const NodePtr BB = TN->getBlock();
1272 
1273  // Virtual root has a corresponding virtual CFG node.
1274  if (DT.isVirtualRoot(TN)) continue;
1275 
1276  if (NodeToInfo.count(BB) == 0) {
1277  errs() << "DomTree node " << BlockNamePrinter(BB)
1278  << " not found by DFS walk!\n";
1279  errs().flush();
1280 
1281  return false;
1282  }
1283  }
1284 
1285  for (const NodePtr N : NumToNode) {
1286  if (N && !DT.getNode(N)) {
1287  errs() << "CFG node " << BlockNamePrinter(N)
1288  << " not found in the DomTree!\n";
1289  errs().flush();
1290 
1291  return false;
1292  }
1293  }
1294 
1295  return true;
1296  }
1297 
1298  // Check if for every parent with a level L in the tree all of its children
1299  // have level L + 1.
1300  // Running time: O(N).
1301  static bool VerifyLevels(const DomTreeT &DT) {
1302  for (auto &NodeToTN : DT.DomTreeNodes) {
1303  const TreeNodePtr TN = NodeToTN.second.get();
1304  const NodePtr BB = TN->getBlock();
1305  if (!BB) continue;
1306 
1307  const TreeNodePtr IDom = TN->getIDom();
1308  if (!IDom && TN->getLevel() != 0) {
1309  errs() << "Node without an IDom " << BlockNamePrinter(BB)
1310  << " has a nonzero level " << TN->getLevel() << "!\n";
1311  errs().flush();
1312 
1313  return false;
1314  }
1315 
1316  if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
1317  errs() << "Node " << BlockNamePrinter(BB) << " has level "
1318  << TN->getLevel() << " while its IDom "
1319  << BlockNamePrinter(IDom->getBlock()) << " has level "
1320  << IDom->getLevel() << "!\n";
1321  errs().flush();
1322 
1323  return false;
1324  }
1325  }
1326 
1327  return true;
1328  }
1329 
1330  // Check if the computed DFS numbers are correct. Note that DFS info may not
1331  // be valid, and when that is the case, we don't verify the numbers.
1332  // Running time: O(N log(N)).
1333  static bool VerifyDFSNumbers(const DomTreeT &DT) {
1334  if (!DT.DFSInfoValid || !DT.Parent)
1335  return true;
1336 
1337  const NodePtr RootBB = IsPostDom ? nullptr : *DT.root_begin();
1338  const TreeNodePtr Root = DT.getNode(RootBB);
1339 
1340  auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
1341  errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
1342  << TN->getDFSNumOut() << '}';
1343  };
1344 
1345  // Verify the root's DFS In number. Although DFS numbering would also work
1346  // if we started from some other value, we assume 0-based numbering.
1347  if (Root->getDFSNumIn() != 0) {
1348  errs() << "DFSIn number for the tree root is not:\n\t";
1349  PrintNodeAndDFSNums(Root);
1350  errs() << '\n';
1351  errs().flush();
1352  return false;
1353  }
1354 
1355  // For each tree node verify if children's DFS numbers cover their parent's
1356  // DFS numbers with no gaps.
1357  for (const auto &NodeToTN : DT.DomTreeNodes) {
1358  const TreeNodePtr Node = NodeToTN.second.get();
1359 
1360  // Handle tree leaves.
1361  if (Node->isLeaf()) {
1362  if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
1363  errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1364  PrintNodeAndDFSNums(Node);
1365  errs() << '\n';
1366  errs().flush();
1367  return false;
1368  }
1369 
1370  continue;
1371  }
1372 
1373  // Make a copy and sort it such that it is possible to check if there are
1374  // no gaps between DFS numbers of adjacent children.
1375  SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
1376  llvm::sort(Children, [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
1377  return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
1378  });
1379 
1380  auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
1381  const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
1382  assert(FirstCh);
1383 
1384  errs() << "Incorrect DFS numbers for:\n\tParent ";
1385  PrintNodeAndDFSNums(Node);
1386 
1387  errs() << "\n\tChild ";
1388  PrintNodeAndDFSNums(FirstCh);
1389 
1390  if (SecondCh) {
1391  errs() << "\n\tSecond child ";
1392  PrintNodeAndDFSNums(SecondCh);
1393  }
1394 
1395  errs() << "\nAll children: ";
1396  for (const TreeNodePtr Ch : Children) {
1397  PrintNodeAndDFSNums(Ch);
1398  errs() << ", ";
1399  }
1400 
1401  errs() << '\n';
1402  errs().flush();
1403  };
1404 
1405  if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
1406  PrintChildrenError(Children.front(), nullptr);
1407  return false;
1408  }
1409 
1410  if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
1411  PrintChildrenError(Children.back(), nullptr);
1412  return false;
1413  }
1414 
1415  for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
1416  if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
1417  PrintChildrenError(Children[i], Children[i + 1]);
1418  return false;
1419  }
1420  }
1421  }
1422 
1423  return true;
1424  }
1425 
1426  // The below routines verify the correctness of the dominator tree relative to
1427  // the CFG it's coming from. A tree is a dominator tree iff it has two
1428  // properties, called the parent property and the sibling property. Tarjan
1429  // and Lengauer prove (but don't explicitly name) the properties as part of
1430  // the proofs in their 1972 paper, but the proofs are mostly part of proving
1431  // things about semidominators and idoms, and some of them are simply asserted
1432  // based on even earlier papers (see, e.g., lemma 2). Some papers refer to
1433  // these properties as "valid" and "co-valid". See, e.g., "Dominators,
1434  // directed bipolar orders, and independent spanning trees" by Loukas
1435  // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
1436  // and Vertex-Disjoint Paths " by the same authors.
1437 
1438  // A very simple and direct explanation of these properties can be found in
1439  // "An Experimental Study of Dynamic Dominators", found at
1440  // https://arxiv.org/abs/1604.02711
1441 
1442  // The easiest way to think of the parent property is that it's a requirement
1443  // of being a dominator. Let's just take immediate dominators. For PARENT to
1444  // be an immediate dominator of CHILD, all paths in the CFG must go through
1445  // PARENT before they hit CHILD. This implies that if you were to cut PARENT
1446  // out of the CFG, there should be no paths to CHILD that are reachable. If
1447  // there are, then you now have a path from PARENT to CHILD that goes around
1448  // PARENT and still reaches CHILD, which by definition, means PARENT can't be
1449  // a dominator of CHILD (let alone an immediate one).
1450 
1451  // The sibling property is similar. It says that for each pair of sibling
1452  // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
1453  // other. If sibling LEFT dominated sibling RIGHT, it means there are no
1454  // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
1455  // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
1456  // RIGHT, not a sibling.
1457 
1458  // It is possible to verify the parent and sibling properties in linear time,
1459  // but the algorithms are complex. Instead, we do it in a straightforward
1460  // N^2 and N^3 way below, using direct path reachability.
1461 
1462  // Checks if the tree has the parent property: if for all edges from V to W in
1463  // the input graph, such that V is reachable, the parent of W in the tree is
1464  // an ancestor of V in the tree.
1465  // Running time: O(N^2).
1466  //
1467  // This means that if a node gets disconnected from the graph, then all of
1468  // the nodes it dominated previously will now become unreachable.
1469  bool verifyParentProperty(const DomTreeT &DT) {
1470  for (auto &NodeToTN : DT.DomTreeNodes) {
1471  const TreeNodePtr TN = NodeToTN.second.get();
1472  const NodePtr BB = TN->getBlock();
1473  if (!BB || TN->isLeaf())
1474  continue;
1475 
1476  LLVM_DEBUG(dbgs() << "Verifying parent property of node "
1477  << BlockNamePrinter(TN) << "\n");
1478  clear();
1479  doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
1480  return From != BB && To != BB;
1481  });
1482 
1483  for (TreeNodePtr Child : TN->children())
1484  if (NodeToInfo.count(Child->getBlock()) != 0) {
1485  errs() << "Child " << BlockNamePrinter(Child)
1486  << " reachable after its parent " << BlockNamePrinter(BB)
1487  << " is removed!\n";
1488  errs().flush();
1489 
1490  return false;
1491  }
1492  }
1493 
1494  return true;
1495  }
1496 
1497  // Check if the tree has sibling property: if a node V does not dominate a
1498  // node W for all siblings V and W in the tree.
1499  // Running time: O(N^3).
1500  //
1501  // This means that if a node gets disconnected from the graph, then all of its
1502  // siblings will now still be reachable.
1503  bool verifySiblingProperty(const DomTreeT &DT) {
1504  for (auto &NodeToTN : DT.DomTreeNodes) {
1505  const TreeNodePtr TN = NodeToTN.second.get();
1506  const NodePtr BB = TN->getBlock();
1507  if (!BB || TN->isLeaf())
1508  continue;
1509 
1510  for (const TreeNodePtr N : TN->children()) {
1511  clear();
1512  NodePtr BBN = N->getBlock();
1513  doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
1514  return From != BBN && To != BBN;
1515  });
1516 
1517  for (const TreeNodePtr S : TN->children()) {
1518  if (S == N) continue;
1519 
1520  if (NodeToInfo.count(S->getBlock()) == 0) {
1521  errs() << "Node " << BlockNamePrinter(S)
1522  << " not reachable when its sibling " << BlockNamePrinter(N)
1523  << " is removed!\n";
1524  errs().flush();
1525 
1526  return false;
1527  }
1528  }
1529  }
1530  }
1531 
1532  return true;
1533  }
1534 
1535  // Check if the given tree is the same as a freshly computed one for the same
1536  // Parent.
1537  // Running time: O(N^2), but faster in practice (same as tree construction).
1538  //
1539  // Note that this does not check if that the tree construction algorithm is
1540  // correct and should be only used for fast (but possibly unsound)
1541  // verification.
1542  static bool IsSameAsFreshTree(const DomTreeT &DT) {
1543  DomTreeT FreshTree;
1544  FreshTree.recalculate(*DT.Parent);
1545  const bool Different = DT.compare(FreshTree);
1546 
1547  if (Different) {
1548  errs() << (DT.isPostDominator() ? "Post" : "")
1549  << "DominatorTree is different than a freshly computed one!\n"
1550  << "\tCurrent:\n";
1551  DT.print(errs());
1552  errs() << "\n\tFreshly computed tree:\n";
1553  FreshTree.print(errs());
1554  errs().flush();
1555  }
1556 
1557  return !Different;
1558  }
1559 };
1560 
1561 template <class DomTreeT>
1562 void Calculate(DomTreeT &DT) {
1564 }
1565 
1566 template <typename DomTreeT>
1567 void CalculateWithUpdates(DomTreeT &DT,
1569  // FIXME: Updated to use the PreViewCFG and behave the same as until now.
1570  // This behavior is however incorrect; this actually needs the PostViewCFG.
1572  Updates, /*ReverseApplyUpdates=*/true);
1573  typename SemiNCAInfo<DomTreeT>::BatchUpdateInfo BUI(PreViewCFG);
1575 }
1576 
1577 template <class DomTreeT>
1578 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1579  typename DomTreeT::NodePtr To) {
1580  if (DT.isPostDominator()) std::swap(From, To);
1581  SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
1582 }
1583 
1584 template <class DomTreeT>
1585 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1586  typename DomTreeT::NodePtr To) {
1587  if (DT.isPostDominator()) std::swap(From, To);
1588  SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
1589 }
1590 
1591 template <class DomTreeT>
1592 void ApplyUpdates(DomTreeT &DT,
1593  GraphDiff<typename DomTreeT::NodePtr,
1594  DomTreeT::IsPostDominator> &PreViewCFG,
1595  GraphDiff<typename DomTreeT::NodePtr,
1596  DomTreeT::IsPostDominator> *PostViewCFG) {
1597  SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, PreViewCFG, PostViewCFG);
1598 }
1599 
1600 template <class DomTreeT>
1601 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
1602  SemiNCAInfo<DomTreeT> SNCA(nullptr);
1603 
1604  // Simplist check is to compare against a new tree. This will also
1605  // usefully print the old and new trees, if they are different.
1606  if (!SNCA.IsSameAsFreshTree(DT))
1607  return false;
1608 
1609  // Common checks to verify the properties of the tree. O(N log N) at worst.
1610  if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1611  !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1612  return false;
1613 
1614  // Extra checks depending on VerificationLevel. Up to O(N^3).
1617  if (!SNCA.verifyParentProperty(DT))
1618  return false;
1620  if (!SNCA.verifySiblingProperty(DT))
1621  return false;
1622 
1623  return true;
1624 }
1625 
1626 } // namespace DomTreeBuilder
1627 } // namespace llvm
1628 
1629 #undef DEBUG_TYPE
1630 
1631 #endif
i
i
Definition: README.txt:29
llvm::DomTreeBuilder::SemiNCAInfo::InsertionInfo::Compare::operator()
bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const
Definition: GenericDomTreeConstruction.h:634
llvm::DomTreeBuilder::Verify
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)
Definition: GenericDomTreeConstruction.h:1601
llvm::DomTreeBuilder::SemiNCAInfo::FindRoots
static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI)
Definition: GenericDomTreeConstruction.h:350
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:1565
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:845
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:651
llvm::DomTreeBuilder::SemiNCAInfo::reattachExistingSubtree
void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
Definition: GenericDomTreeConstruction.h:620
llvm::SmallVector< NodePtr, 2 >
llvm::DomTreeBuilder::SemiNCAInfo::addVirtualRoot
void addVirtualRoot()
Definition: GenericDomTreeConstruction.h:323
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:199
llvm::DomTreeBuilder::SemiNCAInfo::InsertionInfo::Bucket
std::priority_queue< TreeNodePtr, SmallVector< TreeNodePtr, 8 >, Compare > Bucket
Definition: GenericDomTreeConstruction.h:643
llvm::DomTreeBuilder::SemiNCAInfo::InsertionInfo::Compare
Definition: GenericDomTreeConstruction.h:633
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:1301
llvm::Optional
Definition: APInt.h:33
llvm::DomTreeBuilder::SemiNCAInfo::UpdateRootsAfterUpdate
static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI)
Definition: GenericDomTreeConstruction.h:713
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::DomTreeBuilder::SemiNCAInfo::DeleteEdge
static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
Definition: GenericDomTreeConstruction.h:915
llvm::DomTreeBuilder::SemiNCAInfo::ApplyUpdates
static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG)
Definition: GenericDomTreeConstruction.h:1151
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:892
llvm::DomTreeBuilder::SemiNCAInfo::eval
NodePtr eval(NodePtr V, unsigned LastLinked, SmallVectorImpl< InfoRec * > &Stack)
Definition: GenericDomTreeConstruction.h:240
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
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:739
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:1200
llvm::DomTreeBuilder::DeleteEdge
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
Definition: GenericDomTreeConstruction.h:1585
llvm::DomTreeBuilder::SemiNCAInfo::RemoveRedundantRoots
static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, RootsT &Roots)
Definition: GenericDomTreeConstruction.h:508
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:1567
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:53
llvm::raw_ostream::flush
void flush()
Definition: raw_ostream.h:186
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:548
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:865
llvm::erase_value
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:1740
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::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:1033
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:968
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:1132
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
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:1592
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:1571
llvm::DomTreeBuilder::SemiNCAInfo::InfoRec
Definition: GenericDomTreeConstruction.h:64
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::nodes
iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Definition: GraphTraits.h:108
llvm::DomTreeBuilder::SemiNCAInfo::IsSameAsFreshTree
static bool IsSameAsFreshTree(const DomTreeT &DT)
Definition: GenericDomTreeConstruction.h:1542
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:1616
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:840
llvm::DomTreeBuilder::SemiNCAInfo::verifySiblingProperty
bool verifySiblingProperty(const DomTreeT &DT)
Definition: GenericDomTreeConstruction.h:1503
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:1333
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:382
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:644
llvm::DomTreeBuilder::SemiNCAInfo::verifyReachability
bool verifyReachability(const DomTreeT &DT)
Definition: GenericDomTreeConstruction.h:1265
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:632
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:70
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:235
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:1226
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:1009
llvm::DomTreeBuilder::SemiNCAInfo::verifyParentProperty
bool verifyParentProperty(const DomTreeT &DT)
Definition: GenericDomTreeConstruction.h:1469
llvm::DomTreeBuilder::SemiNCAInfo::CalculateFromScratch
static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI)
Definition: GenericDomTreeConstruction.h:560
llvm::DomTreeBuilder::SemiNCAInfo::clear
void clear()
Definition: GenericDomTreeConstruction.h:100
llvm::DomTreeBuilder::Calculate
void Calculate(DomTreeT &DT)
Definition: GenericDomTreeConstruction.h:1562
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:890
llvm::DomTreeBuilder::SemiNCAInfo::UpdateRootsBeforeInsertion
static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
Definition: GenericDomTreeConstruction.h:681
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:83
GenericDomTree.h
llvm::DomTreeBuilder::SemiNCAInfo::BatchUpdateInfo::PreViewCFG
GraphDiffT & PreViewCFG
Definition: GenericDomTreeConstruction.h:89
Direction
Loop::LoopBounds::Direction Direction
Definition: LoopInfo.cpp:230
llvm::DomTreeBuilder::SemiNCAInfo::RootsT
decltype(DomTreeT::Roots) RootsT
Definition: GenericDomTreeConstruction.h:59
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
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:1578
llvm::DomTreeBuilder::SemiNCAInfo::attachNewSubtree
void attachNewSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
Definition: GenericDomTreeConstruction.h:599
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::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:43
llvm::DomTreeBuilder::SemiNCAInfo::InsertionInfo::Affected
SmallVector< TreeNodePtr, 8 > Affected
Definition: GenericDomTreeConstruction.h:645
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:699
llvm::GraphTraits
Definition: GraphTraits.h:35
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
Debug.h
llvm::DomTreeBuilder::SemiNCAInfo
Definition: GenericDomTree.h:49
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364