LLVM 19.0.0git
GenericDomTree.h
Go to the documentation of this file.
1//===- GenericDomTree.h - Generic dominator trees for graphs ----*- 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/// This file defines a set of templates that efficiently compute a dominator
11/// tree over a generic graph. This is used typically in LLVM for fast
12/// dominance queries on the CFG, but is fully generic w.r.t. the underlying
13/// graph types.
14///
15/// Unlike ADT/* graph algorithms, generic dominator tree has more requirements
16/// on the graph's NodeRef. The NodeRef should be a pointer and,
17/// either NodeRef->getParent() must return the parent node that is also a
18/// pointer or DomTreeNodeTraits needs to be specialized.
19///
20/// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
21///
22//===----------------------------------------------------------------------===//
23
24#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
25#define LLVM_SUPPORT_GENERICDOMTREE_H
26
27#include "llvm/ADT/DenseMap.h"
29#include "llvm/ADT/STLExtras.h"
35#include <algorithm>
36#include <cassert>
37#include <cstddef>
38#include <iterator>
39#include <memory>
40#include <type_traits>
41#include <utility>
42
43namespace llvm {
44
45template <typename NodeT, bool IsPostDom>
46class DominatorTreeBase;
47
48namespace DomTreeBuilder {
49template <typename DomTreeT>
50struct SemiNCAInfo;
51} // namespace DomTreeBuilder
52
53/// Base class for the actual dominator tree node.
54template <class NodeT> class DomTreeNodeBase {
55 friend class PostDominatorTree;
56 friend class DominatorTreeBase<NodeT, false>;
57 friend class DominatorTreeBase<NodeT, true>;
60
61 NodeT *TheBB;
62 DomTreeNodeBase *IDom;
63 unsigned Level;
65 mutable unsigned DFSNumIn = ~0;
66 mutable unsigned DFSNumOut = ~0;
67
68 public:
70 : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
71
75
76 iterator begin() { return Children.begin(); }
77 iterator end() { return Children.end(); }
78 const_iterator begin() const { return Children.begin(); }
79 const_iterator end() const { return Children.end(); }
80
81 DomTreeNodeBase *const &back() const { return Children.back(); }
82 DomTreeNodeBase *&back() { return Children.back(); }
83
86 return make_range(begin(), end());
87 }
88
89 NodeT *getBlock() const { return TheBB; }
90 DomTreeNodeBase *getIDom() const { return IDom; }
91 unsigned getLevel() const { return Level; }
92
93 std::unique_ptr<DomTreeNodeBase> addChild(
94 std::unique_ptr<DomTreeNodeBase> C) {
95 Children.push_back(C.get());
96 return C;
97 }
98
99 bool isLeaf() const { return Children.empty(); }
100 size_t getNumChildren() const { return Children.size(); }
101
102 void clearAllChildren() { Children.clear(); }
103
104 bool compare(const DomTreeNodeBase *Other) const {
105 if (getNumChildren() != Other->getNumChildren())
106 return true;
107
108 if (Level != Other->Level) return true;
109
110 SmallPtrSet<const NodeT *, 4> OtherChildren;
111 for (const DomTreeNodeBase *I : *Other) {
112 const NodeT *Nd = I->getBlock();
113 OtherChildren.insert(Nd);
114 }
115
116 for (const DomTreeNodeBase *I : *this) {
117 const NodeT *N = I->getBlock();
118 if (OtherChildren.count(N) == 0)
119 return true;
120 }
121 return false;
122 }
123
124 void setIDom(DomTreeNodeBase *NewIDom) {
125 assert(IDom && "No immediate dominator?");
126 if (IDom == NewIDom) return;
127
128 auto I = find(IDom->Children, this);
129 assert(I != IDom->Children.end() &&
130 "Not in immediate dominator children set!");
131 // I am no longer your child...
132 IDom->Children.erase(I);
133
134 // Switch to new dominator
135 IDom = NewIDom;
136 IDom->Children.push_back(this);
137
138 UpdateLevel();
139 }
140
141 /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
142 /// in the dominator tree. They are only guaranteed valid if
143 /// updateDFSNumbers() has been called.
144 unsigned getDFSNumIn() const { return DFSNumIn; }
145 unsigned getDFSNumOut() const { return DFSNumOut; }
146
147private:
148 // Return true if this node is dominated by other. Use this only if DFS info
149 // is valid.
150 bool DominatedBy(const DomTreeNodeBase *other) const {
151 return this->DFSNumIn >= other->DFSNumIn &&
152 this->DFSNumOut <= other->DFSNumOut;
153 }
154
155 void UpdateLevel() {
156 assert(IDom);
157 if (Level == IDom->Level + 1) return;
158
159 SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
160
161 while (!WorkStack.empty()) {
162 DomTreeNodeBase *Current = WorkStack.pop_back_val();
163 Current->Level = Current->IDom->Level + 1;
164
165 for (DomTreeNodeBase *C : *Current) {
166 assert(C->IDom);
167 if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
168 }
169 }
170 }
171};
172
173template <class NodeT>
175 if (Node->getBlock())
176 Node->getBlock()->printAsOperand(O, false);
177 else
178 O << " <<exit node>>";
179
180 O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
181 << Node->getLevel() << "]\n";
182
183 return O;
184}
185
186template <class NodeT>
188 unsigned Lev) {
189 O.indent(2 * Lev) << "[" << Lev << "] " << N;
190 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
191 E = N->end();
192 I != E; ++I)
193 PrintDomTree<NodeT>(*I, O, Lev + 1);
194}
195
196namespace DomTreeBuilder {
197// The routines below are provided in a separate header but referenced here.
198template <typename DomTreeT>
199void Calculate(DomTreeT &DT);
200
201template <typename DomTreeT>
202void CalculateWithUpdates(DomTreeT &DT,
203 ArrayRef<typename DomTreeT::UpdateType> Updates);
204
205template <typename DomTreeT>
206void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
207 typename DomTreeT::NodePtr To);
208
209template <typename DomTreeT>
210void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
211 typename DomTreeT::NodePtr To);
212
213template <typename DomTreeT>
214void ApplyUpdates(DomTreeT &DT,
215 GraphDiff<typename DomTreeT::NodePtr,
216 DomTreeT::IsPostDominator> &PreViewCFG,
217 GraphDiff<typename DomTreeT::NodePtr,
218 DomTreeT::IsPostDominator> *PostViewCFG);
219
220template <typename DomTreeT>
221bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
222} // namespace DomTreeBuilder
223
224/// Default DomTreeNode traits for NodeT. The default implementation assume a
225/// Function-like NodeT. Can be specialized to support different node types.
226template <typename NodeT> struct DomTreeNodeTraits {
227 using NodeType = NodeT;
228 using NodePtr = NodeT *;
229 using ParentPtr = decltype(std::declval<NodePtr>()->getParent());
230 static_assert(std::is_pointer_v<ParentPtr>,
231 "Currently NodeT's parent must be a pointer type");
232 using ParentType = std::remove_pointer_t<ParentPtr>;
233
234 static NodeT *getEntryNode(ParentPtr Parent) { return &Parent->front(); }
235 static ParentPtr getParent(NodePtr BB) { return BB->getParent(); }
236};
237
238/// Core dominator tree base class.
239///
240/// This class is a generic template over graph nodes. It is instantiated for
241/// various graphs in the LLVM IR or in the code generator.
242template <typename NodeT, bool IsPostDom>
244 public:
245 static_assert(std::is_pointer_v<typename GraphTraits<NodeT *>::NodeRef>,
246 "Currently DominatorTreeBase supports only pointer nodes");
249 using NodePtr = typename NodeTrait::NodePtr;
251 static_assert(std::is_pointer_v<ParentPtr>,
252 "Currently NodeT's parent must be a pointer type");
253 using ParentType = std::remove_pointer_t<ParentPtr>;
254 static constexpr bool IsPostDominator = IsPostDom;
255
258 static constexpr UpdateKind Insert = UpdateKind::Insert;
259 static constexpr UpdateKind Delete = UpdateKind::Delete;
260
262
263protected:
264 // Dominators always have a single root, postdominators can have more.
266
271 ParentPtr Parent = nullptr;
272
273 mutable bool DFSInfoValid = false;
274 mutable unsigned int SlowQueries = 0;
275
277
278 public:
279 DominatorTreeBase() = default;
280
282 : Roots(std::move(Arg.Roots)),
284 RootNode(Arg.RootNode),
285 Parent(Arg.Parent),
288 Arg.wipe();
289 }
290
292 Roots = std::move(RHS.Roots);
293 DomTreeNodes = std::move(RHS.DomTreeNodes);
294 RootNode = RHS.RootNode;
295 Parent = RHS.Parent;
296 DFSInfoValid = RHS.DFSInfoValid;
297 SlowQueries = RHS.SlowQueries;
298 RHS.wipe();
299 return *this;
300 }
301
304
305 /// Iteration over roots.
306 ///
307 /// This may include multiple blocks if we are computing post dominators.
308 /// For forward dominators, this will always be a single block (the entry
309 /// block).
312
316 const_root_iterator root_end() const { return Roots.end(); }
317
318 size_t root_size() const { return Roots.size(); }
319
321 return make_range(root_begin(), root_end());
322 }
324 return make_range(root_begin(), root_end());
325 }
326
327 /// isPostDominator - Returns true if analysis based of postdoms
328 ///
329 bool isPostDominator() const { return IsPostDominator; }
330
331 /// compare - Return false if the other dominator tree base matches this
332 /// dominator tree base. Otherwise return true.
333 bool compare(const DominatorTreeBase &Other) const {
334 if (Parent != Other.Parent) return true;
335
336 if (Roots.size() != Other.Roots.size())
337 return true;
338
339 if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
340 return true;
341
342 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
343 if (DomTreeNodes.size() != OtherDomTreeNodes.size())
344 return true;
345
346 for (const auto &DomTreeNode : DomTreeNodes) {
347 NodeT *BB = DomTreeNode.first;
349 OtherDomTreeNodes.find(BB);
350 if (OI == OtherDomTreeNodes.end())
351 return true;
352
353 DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
354 DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
355
356 if (MyNd.compare(&OtherNd))
357 return true;
358 }
359
360 return false;
361 }
362
363 /// getNode - return the (Post)DominatorTree node for the specified basic
364 /// block. This is the same as using operator[] on this class. The result
365 /// may (but is not required to) be null for a forward (backwards)
366 /// statically unreachable block.
367 DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
368 auto I = DomTreeNodes.find(BB);
369 if (I != DomTreeNodes.end())
370 return I->second.get();
371 return nullptr;
372 }
373
374 /// See getNode.
375 DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
376 return getNode(BB);
377 }
378
379 /// getRootNode - This returns the entry node for the CFG of the function. If
380 /// this tree represents the post-dominance relations for a function, however,
381 /// this root may be a node with the block == NULL. This is the case when
382 /// there are multiple exit nodes from a particular function. Consumers of
383 /// post-dominance information must be capable of dealing with this
384 /// possibility.
385 ///
387 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
388
389 /// Get all nodes dominated by R, including R itself.
390 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
391 Result.clear();
392 const DomTreeNodeBase<NodeT> *RN = getNode(R);
393 if (!RN)
394 return; // If R is unreachable, it will not be present in the DOM tree.
396 WL.push_back(RN);
397
398 while (!WL.empty()) {
400 Result.push_back(N->getBlock());
401 WL.append(N->begin(), N->end());
402 }
403 }
404
405 /// properlyDominates - Returns true iff A dominates B and A != B.
406 /// Note that this is not a constant time operation!
407 ///
409 const DomTreeNodeBase<NodeT> *B) const {
410 if (!A || !B)
411 return false;
412 if (A == B)
413 return false;
414 return dominates(A, B);
415 }
416
417 bool properlyDominates(const NodeT *A, const NodeT *B) const;
418
419 /// isReachableFromEntry - Return true if A is dominated by the entry
420 /// block of the function containing it.
421 bool isReachableFromEntry(const NodeT *A) const {
422 assert(!this->isPostDominator() &&
423 "This is not implemented for post dominators");
424 return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
425 }
426
427 bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
428
429 /// dominates - Returns true iff A dominates B. Note that this is not a
430 /// constant time operation!
431 ///
433 const DomTreeNodeBase<NodeT> *B) const {
434 // A node trivially dominates itself.
435 if (B == A)
436 return true;
437
438 // An unreachable node is dominated by anything.
440 return true;
441
442 // And dominates nothing.
444 return false;
445
446 if (B->getIDom() == A) return true;
447
448 if (A->getIDom() == B) return false;
449
450 // A can only dominate B if it is higher in the tree.
451 if (A->getLevel() >= B->getLevel()) return false;
452
453 // Compare the result of the tree walk and the dfs numbers, if expensive
454 // checks are enabled.
455#ifdef EXPENSIVE_CHECKS
457 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
458 "Tree walk disagrees with dfs numbers!");
459#endif
460
461 if (DFSInfoValid)
462 return B->DominatedBy(A);
463
464 // If we end up with too many slow queries, just update the
465 // DFS numbers on the theory that we are going to keep querying.
466 SlowQueries++;
467 if (SlowQueries > 32) {
469 return B->DominatedBy(A);
470 }
471
472 return dominatedBySlowTreeWalk(A, B);
473 }
474
475 bool dominates(const NodeT *A, const NodeT *B) const;
476
477 NodeT *getRoot() const {
478 assert(this->Roots.size() == 1 && "Should always have entry node!");
479 return this->Roots[0];
480 }
481
482 /// Find nearest common dominator basic block for basic block A and B. A and B
483 /// must have tree nodes.
484 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
485 assert(A && B && "Pointers are not valid");
487 "Two blocks are not in same function");
488
489 // If either A or B is a entry block then it is nearest common dominator
490 // (for forward-dominators).
491 if (!isPostDominator()) {
492 NodeT &Entry =
494 if (A == &Entry || B == &Entry)
495 return &Entry;
496 }
497
500 assert(NodeA && "A must be in the tree");
501 assert(NodeB && "B must be in the tree");
502
503 // Use level information to go up the tree until the levels match. Then
504 // continue going up til we arrive at the same node.
505 while (NodeA != NodeB) {
506 if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
507
508 NodeA = NodeA->IDom;
509 }
510
511 return NodeA->getBlock();
512 }
513
514 const NodeT *findNearestCommonDominator(const NodeT *A,
515 const NodeT *B) const {
516 // Cast away the const qualifiers here. This is ok since
517 // const is re-introduced on the return type.
518 return findNearestCommonDominator(const_cast<NodeT *>(A),
519 const_cast<NodeT *>(B));
520 }
521
523 return isPostDominator() && !A->getBlock();
524 }
525
526 //===--------------------------------------------------------------------===//
527 // API to update (Post)DominatorTree information based on modifications to
528 // the CFG...
529
530 /// Inform the dominator tree about a sequence of CFG edge insertions and
531 /// deletions and perform a batch update on the tree.
532 ///
533 /// This function should be used when there were multiple CFG updates after
534 /// the last dominator tree update. It takes care of performing the updates
535 /// in sync with the CFG and optimizes away the redundant operations that
536 /// cancel each other.
537 /// The functions expects the sequence of updates to be balanced. Eg.:
538 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
539 /// logically it results in a single insertions.
540 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
541 /// sense to insert the same edge twice.
542 ///
543 /// What's more, the functions assumes that it's safe to ask every node in the
544 /// CFG about its children and inverse children. This implies that deletions
545 /// of CFG edges must not delete the CFG nodes before calling this function.
546 ///
547 /// The applyUpdates function can reorder the updates and remove redundant
548 /// ones internally (as long as it is done in a deterministic fashion). The
549 /// batch updater is also able to detect sequences of zero and exactly one
550 /// update -- it's optimized to do less work in these cases.
551 ///
552 /// Note that for postdominators it automatically takes care of applying
553 /// updates on reverse edges internally (so there's no need to swap the
554 /// From and To pointers when constructing DominatorTree::UpdateType).
555 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
556 /// with the same template parameter T.
557 ///
558 /// \param Updates An ordered sequence of updates to perform. The current CFG
559 /// and the reverse of these updates provides the pre-view of the CFG.
560 ///
563 Updates, /*ReverseApplyUpdates=*/true);
564 DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr);
565 }
566
567 /// \param Updates An ordered sequence of updates to perform. The current CFG
568 /// and the reverse of these updates provides the pre-view of the CFG.
569 /// \param PostViewUpdates An ordered sequence of update to perform in order
570 /// to obtain a post-view of the CFG. The DT will be updated assuming the
571 /// obtained PostViewCFG is the desired end state.
573 ArrayRef<UpdateType> PostViewUpdates) {
574 if (Updates.empty()) {
575 GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
576 DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG);
577 } else {
578 // PreViewCFG needs to merge Updates and PostViewCFG. The updates in
579 // Updates need to be reversed, and match the direction in PostViewCFG.
580 // The PostViewCFG is created with updates reversed (equivalent to changes
581 // made to the CFG), so the PreViewCFG needs all the updates reverse
582 // applied.
583 SmallVector<UpdateType> AllUpdates(Updates.begin(), Updates.end());
584 append_range(AllUpdates, PostViewUpdates);
585 GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates,
586 /*ReverseApplyUpdates=*/true);
587 GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
588 DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG);
589 }
590 }
591
592 /// Inform the dominator tree about a CFG edge insertion and update the tree.
593 ///
594 /// This function has to be called just before or just after making the update
595 /// on the actual CFG. There cannot be any other updates that the dominator
596 /// tree doesn't know about.
597 ///
598 /// Note that for postdominators it automatically takes care of inserting
599 /// a reverse edge internally (so there's no need to swap the parameters).
600 ///
601 void insertEdge(NodeT *From, NodeT *To) {
602 assert(From);
603 assert(To);
607 }
608
609 /// Inform the dominator tree about a CFG edge deletion and update the tree.
610 ///
611 /// This function has to be called just after making the update on the actual
612 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
613 /// DEBUG mode. There cannot be any other updates that the
614 /// dominator tree doesn't know about.
615 ///
616 /// Note that for postdominators it automatically takes care of deleting
617 /// a reverse edge internally (so there's no need to swap the parameters).
618 ///
619 void deleteEdge(NodeT *From, NodeT *To) {
620 assert(From);
621 assert(To);
625 }
626
627 /// Add a new node to the dominator tree information.
628 ///
629 /// This creates a new node as a child of DomBB dominator node, linking it
630 /// into the children list of the immediate dominator.
631 ///
632 /// \param BB New node in CFG.
633 /// \param DomBB CFG node that is dominator for BB.
634 /// \returns New dominator tree node that represents new CFG node.
635 ///
636 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
637 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
638 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
639 assert(IDomNode && "Not immediate dominator specified for block!");
640 DFSInfoValid = false;
641 return createChild(BB, IDomNode);
642 }
643
644 /// Add a new node to the forward dominator tree and make it a new root.
645 ///
646 /// \param BB New node in CFG.
647 /// \returns New dominator tree node that represents new CFG node.
648 ///
650 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
651 assert(!this->isPostDominator() &&
652 "Cannot change root of post-dominator tree");
653 DFSInfoValid = false;
654 DomTreeNodeBase<NodeT> *NewNode = createNode(BB);
655 if (Roots.empty()) {
656 addRoot(BB);
657 } else {
658 assert(Roots.size() == 1);
659 NodeT *OldRoot = Roots.front();
660 auto &OldNode = DomTreeNodes[OldRoot];
661 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
662 OldNode->IDom = NewNode;
663 OldNode->UpdateLevel();
664 Roots[0] = BB;
665 }
666 return RootNode = NewNode;
667 }
668
669 /// changeImmediateDominator - This method is used to update the dominator
670 /// tree information when a node's immediate dominator changes.
671 ///
673 DomTreeNodeBase<NodeT> *NewIDom) {
674 assert(N && NewIDom && "Cannot change null node pointers!");
675 DFSInfoValid = false;
676 N->setIDom(NewIDom);
677 }
678
679 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
681 }
682
683 /// eraseNode - Removes a node from the dominator tree. Block must not
684 /// dominate any other blocks. Removes node from its immediate dominator's
685 /// children list. Deletes dominator node associated with basic block BB.
686 void eraseNode(NodeT *BB) {
688 assert(Node && "Removing node that isn't in dominator tree.");
689 assert(Node->isLeaf() && "Node is not a leaf node.");
690
691 DFSInfoValid = false;
692
693 // Remove node from immediate dominator's children list.
694 DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
695 if (IDom) {
696 const auto I = find(IDom->Children, Node);
697 assert(I != IDom->Children.end() &&
698 "Not in immediate dominator children set!");
699 // I am no longer your child...
700 IDom->Children.erase(I);
701 }
702
704
705 if (!IsPostDom) return;
706
707 // Remember to update PostDominatorTree roots.
708 auto RIt = llvm::find(Roots, BB);
709 if (RIt != Roots.end()) {
710 std::swap(*RIt, Roots.back());
711 Roots.pop_back();
712 }
713 }
714
715 /// splitBlock - BB is split and now it has one successor. Update dominator
716 /// tree to reflect this change.
717 void splitBlock(NodeT *NewBB) {
718 if (IsPostDominator)
719 Split<Inverse<NodeT *>>(NewBB);
720 else
721 Split<NodeT *>(NewBB);
722 }
723
724 /// print - Convert to human readable form
725 ///
726 void print(raw_ostream &O) const {
727 O << "=============================--------------------------------\n";
728 if (IsPostDominator)
729 O << "Inorder PostDominator Tree: ";
730 else
731 O << "Inorder Dominator Tree: ";
732 if (!DFSInfoValid)
733 O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
734 O << "\n";
735
736 // The postdom tree can have a null root if there are no returns.
737 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
738 O << "Roots: ";
739 for (const NodePtr Block : Roots) {
740 Block->printAsOperand(O, false);
741 O << " ";
742 }
743 O << "\n";
744 }
745
746public:
747 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
748 /// dominator tree in dfs order.
749 void updateDFSNumbers() const {
750 if (DFSInfoValid) {
751 SlowQueries = 0;
752 return;
753 }
754
757 32> WorkStack;
758
759 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
760 assert((!Parent || ThisRoot) && "Empty constructed DomTree");
761 if (!ThisRoot)
762 return;
763
764 // Both dominators and postdominators have a single root node. In the case
765 // case of PostDominatorTree, this node is a virtual root.
766 WorkStack.push_back({ThisRoot, ThisRoot->begin()});
767
768 unsigned DFSNum = 0;
769 ThisRoot->DFSNumIn = DFSNum++;
770
771 while (!WorkStack.empty()) {
772 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
773 const auto ChildIt = WorkStack.back().second;
774
775 // If we visited all of the children of this node, "recurse" back up the
776 // stack setting the DFOutNum.
777 if (ChildIt == Node->end()) {
778 Node->DFSNumOut = DFSNum++;
779 WorkStack.pop_back();
780 } else {
781 // Otherwise, recursively visit this child.
782 const DomTreeNodeBase<NodeT> *Child = *ChildIt;
783 ++WorkStack.back().second;
784
785 WorkStack.push_back({Child, Child->begin()});
786 Child->DFSNumIn = DFSNum++;
787 }
788 }
789
790 SlowQueries = 0;
791 DFSInfoValid = true;
792 }
793
794 /// recalculate - compute a dominator tree for the given function
796 Parent = &Func;
798 }
799
801 Parent = &Func;
803 }
804
805 /// verify - checks if the tree is correct. There are 3 level of verification:
806 /// - Full -- verifies if the tree is correct by making sure all the
807 /// properties (including the parent and the sibling property)
808 /// hold.
809 /// Takes O(N^3) time.
810 ///
811 /// - Basic -- checks if the tree is correct, but compares it to a freshly
812 /// constructed tree instead of checking the sibling property.
813 /// Takes O(N^2) time.
814 ///
815 /// - Fast -- checks basic tree structure and compares it with a freshly
816 /// constructed tree.
817 /// Takes O(N^2) time worst case, but is faster in practise (same
818 /// as tree construction).
820 return DomTreeBuilder::Verify(*this, VL);
821 }
822
823 void reset() {
825 Roots.clear();
826 RootNode = nullptr;
827 Parent = nullptr;
828 DFSInfoValid = false;
829 SlowQueries = 0;
830 }
831
832protected:
833 void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
834
836 return (DomTreeNodes[BB] = IDom->addChild(
837 std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom)))
838 .get();
839 }
840
842 return (DomTreeNodes[BB] =
843 std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr))
844 .get();
845 }
846
847 // NewBB is split and now it has one successor. Update dominator tree to
848 // reflect this change.
849 template <class N>
850 void Split(typename GraphTraits<N>::NodeRef NewBB) {
851 using GraphT = GraphTraits<N>;
852 using NodeRef = typename GraphT::NodeRef;
853 assert(llvm::hasSingleElement(children<N>(NewBB)) &&
854 "NewBB should have a single successor!");
855 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
856
857 SmallVector<NodeRef, 4> PredBlocks(inverse_children<N>(NewBB));
858
859 assert(!PredBlocks.empty() && "No predblocks?");
860
861 bool NewBBDominatesNewBBSucc = true;
862 for (auto *Pred : inverse_children<N>(NewBBSucc)) {
863 if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
864 isReachableFromEntry(Pred)) {
865 NewBBDominatesNewBBSucc = false;
866 break;
867 }
868 }
869
870 // Find NewBB's immediate dominator and create new dominator tree node for
871 // NewBB.
872 NodeT *NewBBIDom = nullptr;
873 unsigned i = 0;
874 for (i = 0; i < PredBlocks.size(); ++i)
875 if (isReachableFromEntry(PredBlocks[i])) {
876 NewBBIDom = PredBlocks[i];
877 break;
878 }
879
880 // It's possible that none of the predecessors of NewBB are reachable;
881 // in that case, NewBB itself is unreachable, so nothing needs to be
882 // changed.
883 if (!NewBBIDom) return;
884
885 for (i = i + 1; i < PredBlocks.size(); ++i) {
886 if (isReachableFromEntry(PredBlocks[i]))
887 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
888 }
889
890 // Create the new dominator tree node... and set the idom of NewBB.
891 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
892
893 // If NewBB strictly dominates other blocks, then it is now the immediate
894 // dominator of NewBBSucc. Update the dominator tree as appropriate.
895 if (NewBBDominatesNewBBSucc) {
896 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
897 changeImmediateDominator(NewBBSuccNode, NewBBNode);
898 }
899 }
900
901 private:
902 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
903 const DomTreeNodeBase<NodeT> *B) const {
904 assert(A != B);
907
908 const unsigned ALevel = A->getLevel();
909 const DomTreeNodeBase<NodeT> *IDom;
910
911 // Don't walk nodes above A's subtree. When we reach A's level, we must
912 // either find A or be in some other subtree not dominated by A.
913 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
914 B = IDom; // Walk up the tree
915
916 return B == A;
917 }
918
919 /// Wipe this tree's state without releasing any resources.
920 ///
921 /// This is essentially a post-move helper only. It leaves the object in an
922 /// assignable and destroyable state, but otherwise invalid.
923 void wipe() {
925 RootNode = nullptr;
926 Parent = nullptr;
927 }
928};
929
930template <typename T>
932
933template <typename T>
935
936// These two functions are declared out of line as a workaround for building
937// with old (< r147295) versions of clang because of pr11642.
938template <typename NodeT, bool IsPostDom>
940 const NodeT *B) const {
941 if (A == B)
942 return true;
943
944 // Cast away the const qualifiers here. This is ok since
945 // this function doesn't actually return the values returned
946 // from getNode.
947 return dominates(getNode(const_cast<NodeT *>(A)),
948 getNode(const_cast<NodeT *>(B)));
949}
950template <typename NodeT, bool IsPostDom>
952 const NodeT *A, const NodeT *B) const {
953 if (A == B)
954 return false;
955
956 // Cast away the const qualifiers here. This is ok since
957 // this function doesn't actually return the values returned
958 // from getNode.
959 return dominates(getNode(const_cast<NodeT *>(A)),
960 getNode(const_cast<NodeT *>(B)));
961}
962
963} // end namespace llvm
964
965#endif // LLVM_SUPPORT_GENERICDOMTREE_H
basic Basic Alias true
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
#define I(x, y, z)
Definition: MD5.cpp:58
ppc ctr loops PowerPC CTR Loops Verify
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Value * RHS
void printAsOperand(OutputBuffer &OB, Prec P=Prec::Default, bool StrictlyWorse=false) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:154
iterator begin() const
Definition: ArrayRef.h:153
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
unsigned size() const
Definition: DenseMap.h:99
iterator end()
Definition: DenseMap.h:84
Base class for the actual dominator tree node.
iterator_range< iterator > children()
const_iterator end() const
DomTreeNodeBase *& back()
void setIDom(DomTreeNodeBase *NewIDom)
typename SmallVector< DomTreeNodeBase *, 4 >::iterator iterator
DomTreeNodeBase *const & back() const
DomTreeNodeBase * getIDom() const
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
size_t getNumChildren() const
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
bool compare(const DomTreeNodeBase *Other) const
NodeT * getBlock() const
unsigned getLevel() const
std::unique_ptr< DomTreeNodeBase > addChild(std::unique_ptr< DomTreeNodeBase > C)
iterator_range< const_iterator > children() const
unsigned getDFSNumOut() const
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
const_iterator begin() const
Core dominator tree base class.
bool isReachableFromEntry(const DomTreeNodeBase< NodeT > *A) const
void print(raw_ostream &O) const
print - Convert to human readable form
typename NodeTrait::NodeType NodeType
DomTreeNodeBase< NodeT > * operator[](const NodeT *BB) const
See getNode.
typename SmallVectorImpl< NodeT * >::iterator root_iterator
Iteration over roots.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void changeImmediateDominator(NodeT *BB, NodeT *NewBB)
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
void Split(typename GraphTraits< N >::NodeRef NewBB)
iterator_range< root_iterator > roots()
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
std::remove_pointer_t< ParentPtr > ParentType
DominatorTreeBase(DominatorTreeBase &&Arg)
bool isPostDominator() const
isPostDominator - Returns true if analysis based of postdoms
size_t root_size() const
const NodeT * findNearestCommonDominator(const NodeT *A, const NodeT *B) const
void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const
Get all nodes dominated by R, including R itself.
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
iterator_range< const_root_iterator > roots() const
const_root_iterator root_end() const
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
DomTreeNodeBase< NodeT > * createNode(NodeT *BB)
DominatorTreeBase & operator=(DominatorTreeBase &&RHS)
static constexpr UpdateKind Delete
void recalculate(ParentType &Func, ArrayRef< UpdateType > Updates)
NodeT * getRoot() const
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
typename SmallVectorImpl< NodeT * >::const_iterator const_root_iterator
bool compare(const DominatorTreeBase &Other) const
compare - Return false if the other dominator tree base matches this dominator tree base.
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
root_iterator root_begin()
DominatorTreeBase(const DominatorTreeBase &)=delete
DomTreeNodeMapType DomTreeNodes
static constexpr UpdateKind Insert
const_root_iterator root_begin() const
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
SmallVector< NodeT *, IsPostDom ? 4 :1 > Roots
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
const DomTreeNodeBase< NodeT > * getRootNode() const
DomTreeNodeBase< NodeT > * RootNode
void addRoot(NodeT *BB)
typename NodeTrait::NodePtr NodePtr
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
root_iterator root_end()
void applyUpdates(ArrayRef< UpdateType > Updates, ArrayRef< UpdateType > PostViewUpdates)
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const NodeT *A, const NodeT *B) const
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
bool isVirtualRoot(const DomTreeNodeBase< NodeT > *A) const
typename NodeTrait::ParentPtr ParentPtr
DominatorTreeBase & operator=(const DominatorTreeBase &)=delete
DomTreeNodeBase< NodeT > * createChild(NodeT *BB, DomTreeNodeBase< NodeT > *IDom)
static constexpr bool IsPostDominator
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:591
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
typename SuperClass::iterator iterator
Definition: SmallVector.h:590
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)
void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
void ApplyUpdates(DomTreeT &DT, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1751
void PrintDomTree(const DomTreeNodeBase< NodeT > *N, raw_ostream &O, unsigned Lev)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2082
bool hasSingleElement(ContainerTy &&C)
Returns true if the given container only contains a single element.
Definition: STLExtras.h:322
@ Other
Any other memory.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
Default DomTreeNode traits for NodeT.
static NodeT * getEntryNode(ParentPtr Parent)
std::remove_pointer_t< ParentPtr > ParentType
static ParentPtr getParent(NodePtr BB)
decltype(std::declval< NodePtr >() ->getParent()) ParentPtr
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:80