Line data Source code
1 : //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : /// \file
10 : ///
11 : /// This file defines a set of templates that efficiently compute a dominator
12 : /// tree over a generic graph. This is used typically in LLVM for fast
13 : /// dominance queries on the CFG, but is fully generic w.r.t. the underlying
14 : /// graph types.
15 : ///
16 : /// Unlike ADT/* graph algorithms, generic dominator tree has more requirements
17 : /// on the graph's NodeRef. The NodeRef should be a pointer and,
18 : /// NodeRef->getParent() must return the parent node that is also a pointer.
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"
28 : #include "llvm/ADT/GraphTraits.h"
29 : #include "llvm/ADT/PointerIntPair.h"
30 : #include "llvm/ADT/STLExtras.h"
31 : #include "llvm/ADT/SmallPtrSet.h"
32 : #include "llvm/ADT/SmallVector.h"
33 : #include "llvm/Support/CFGUpdate.h"
34 : #include "llvm/Support/raw_ostream.h"
35 : #include <algorithm>
36 : #include <cassert>
37 : #include <cstddef>
38 : #include <iterator>
39 : #include <memory>
40 : #include <type_traits>
41 : #include <utility>
42 : #include <vector>
43 :
44 : namespace llvm {
45 :
46 : template <typename NodeT, bool IsPostDom>
47 : class DominatorTreeBase;
48 :
49 : namespace DomTreeBuilder {
50 : template <typename DomTreeT>
51 : struct SemiNCAInfo;
52 : } // namespace DomTreeBuilder
53 :
54 : /// Base class for the actual dominator tree node.
55 0 : template <class NodeT> class DomTreeNodeBase {
56 : friend class PostDominatorTree;
57 : friend class DominatorTreeBase<NodeT, false>;
58 : friend class DominatorTreeBase<NodeT, true>;
59 : friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
60 : friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
61 :
62 : NodeT *TheBB;
63 : DomTreeNodeBase *IDom;
64 : unsigned Level;
65 : std::vector<DomTreeNodeBase *> Children;
66 : mutable unsigned DFSNumIn = ~0;
67 : mutable unsigned DFSNumOut = ~0;
68 :
69 : public:
70 0 : DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
71 0 : : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
72 :
73 : using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
74 : using const_iterator =
75 : typename std::vector<DomTreeNodeBase *>::const_iterator;
76 :
77 0 : iterator begin() { return Children.begin(); }
78 0 : iterator end() { return Children.end(); }
79 9951995 : const_iterator begin() const { return Children.begin(); }
80 12098378 : const_iterator end() const { return Children.end(); }
81 :
82 4342821 : NodeT *getBlock() const { return TheBB; }
83 711452 : DomTreeNodeBase *getIDom() const { return IDom; }
84 3371597 : unsigned getLevel() const { return Level; }
85 :
86 0 : const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
87 :
88 0 : std::unique_ptr<DomTreeNodeBase> addChild(
89 : std::unique_ptr<DomTreeNodeBase> C) {
90 33023775 : Children.push_back(C.get());
91 0 : return C;
92 : }
93 :
94 6713 : size_t getNumChildren() const { return Children.size(); }
95 :
96 0 : void clearAllChildren() { Children.clear(); }
97 :
98 6713 : bool compare(const DomTreeNodeBase *Other) const {
99 6713 : if (getNumChildren() != Other->getNumChildren())
100 : return true;
101 :
102 6712 : if (Level != Other->Level) return true;
103 :
104 : SmallPtrSet<const NodeT *, 4> OtherChildren;
105 12709 : for (const DomTreeNodeBase *I : *Other) {
106 : const NodeT *Nd = I->getBlock();
107 5997 : OtherChildren.insert(Nd);
108 : }
109 :
110 12709 : for (const DomTreeNodeBase *I : *this) {
111 : const NodeT *N = I->getBlock();
112 5997 : if (OtherChildren.count(N) == 0)
113 : return true;
114 : }
115 : return false;
116 : }
117 :
118 1287786 : void setIDom(DomTreeNodeBase *NewIDom) {
119 : assert(IDom && "No immediate dominator?");
120 1287786 : if (IDom == NewIDom) return;
121 :
122 43404 : auto I = find(IDom->Children, this);
123 : assert(I != IDom->Children.end() &&
124 : "Not in immediate dominator children set!");
125 : // I am no longer your child...
126 43404 : IDom->Children.erase(I);
127 :
128 : // Switch to new dominator
129 43404 : IDom = NewIDom;
130 43404 : IDom->Children.push_back(this);
131 :
132 43404 : UpdateLevel();
133 : }
134 :
135 : /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
136 : /// in the dominator tree. They are only guaranteed valid if
137 : /// updateDFSNumbers() has been called.
138 195 : unsigned getDFSNumIn() const { return DFSNumIn; }
139 192 : unsigned getDFSNumOut() const { return DFSNumOut; }
140 :
141 : private:
142 : // Return true if this node is dominated by other. Use this only if DFS info
143 : // is valid.
144 0 : bool DominatedBy(const DomTreeNodeBase *other) const {
145 2188481 : return this->DFSNumIn >= other->DFSNumIn &&
146 1141458 : this->DFSNumOut <= other->DFSNumOut;
147 : }
148 :
149 299079 : void UpdateLevel() {
150 : assert(IDom);
151 299079 : if (Level == IDom->Level + 1) return;
152 :
153 45458 : SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
154 :
155 590211 : while (!WorkStack.empty()) {
156 : DomTreeNodeBase *Current = WorkStack.pop_back_val();
157 544753 : Current->Level = Current->IDom->Level + 1;
158 :
159 1044048 : for (DomTreeNodeBase *C : *Current) {
160 : assert(C->IDom);
161 499295 : if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
162 : }
163 : }
164 : }
165 : };
166 :
167 : template <class NodeT>
168 183 : raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
169 183 : if (Node->getBlock())
170 167 : Node->getBlock()->printAsOperand(O, false);
171 : else
172 16 : O << " <<exit node>>";
173 :
174 549 : O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
175 183 : << Node->getLevel() << "]\n";
176 :
177 183 : return O;
178 : }
179 :
180 : template <class NodeT>
181 183 : void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
182 : unsigned Lev) {
183 366 : O.indent(2 * Lev) << "[" << Lev << "] " << N;
184 : for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
185 : E = N->end();
186 339 : I != E; ++I)
187 156 : PrintDomTree<NodeT>(*I, O, Lev + 1);
188 183 : }
189 :
190 : namespace DomTreeBuilder {
191 : // The routines below are provided in a separate header but referenced here.
192 : template <typename DomTreeT>
193 : void Calculate(DomTreeT &DT);
194 :
195 : template <typename DomTreeT>
196 : void CalculateWithUpdates(DomTreeT &DT,
197 : ArrayRef<typename DomTreeT::UpdateType> Updates);
198 :
199 : template <typename DomTreeT>
200 : void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
201 : typename DomTreeT::NodePtr To);
202 :
203 : template <typename DomTreeT>
204 : void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
205 : typename DomTreeT::NodePtr To);
206 :
207 : template <typename DomTreeT>
208 : void ApplyUpdates(DomTreeT &DT,
209 : ArrayRef<typename DomTreeT::UpdateType> Updates);
210 :
211 : template <typename DomTreeT>
212 : bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
213 : } // namespace DomTreeBuilder
214 :
215 : /// Core dominator tree base class.
216 : ///
217 : /// This class is a generic template over graph nodes. It is instantiated for
218 : /// various graphs in the LLVM IR or in the code generator.
219 : template <typename NodeT, bool IsPostDom>
220 : class DominatorTreeBase {
221 : public:
222 : static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
223 : "Currently DominatorTreeBase supports only pointer nodes");
224 : using NodeType = NodeT;
225 : using NodePtr = NodeT *;
226 : using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
227 : static_assert(std::is_pointer<ParentPtr>::value,
228 : "Currently NodeT's parent must be a pointer type");
229 : using ParentType = typename std::remove_pointer<ParentPtr>::type;
230 : static constexpr bool IsPostDominator = IsPostDom;
231 :
232 : using UpdateType = cfg::Update<NodePtr>;
233 : using UpdateKind = cfg::UpdateKind;
234 : static constexpr UpdateKind Insert = UpdateKind::Insert;
235 : static constexpr UpdateKind Delete = UpdateKind::Delete;
236 :
237 : enum class VerificationLevel { Fast, Basic, Full };
238 :
239 : protected:
240 : // Dominators always have a single root, postdominators can have more.
241 : SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
242 :
243 : using DomTreeNodeMapType =
244 : DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
245 : DomTreeNodeMapType DomTreeNodes;
246 : DomTreeNodeBase<NodeT> *RootNode;
247 : ParentPtr Parent = nullptr;
248 :
249 : mutable bool DFSInfoValid = false;
250 : mutable unsigned int SlowQueries = 0;
251 :
252 : friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
253 :
254 : public:
255 3867124 : DominatorTreeBase() {}
256 :
257 0 : DominatorTreeBase(DominatorTreeBase &&Arg)
258 : : Roots(std::move(Arg.Roots)),
259 0 : DomTreeNodes(std::move(Arg.DomTreeNodes)),
260 0 : RootNode(Arg.RootNode),
261 0 : Parent(Arg.Parent),
262 0 : DFSInfoValid(Arg.DFSInfoValid),
263 0 : SlowQueries(Arg.SlowQueries) {
264 : Arg.wipe();
265 0 : }
266 0 :
267 0 : DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
268 0 : Roots = std::move(RHS.Roots);
269 0 : DomTreeNodes = std::move(RHS.DomTreeNodes);
270 0 : RootNode = RHS.RootNode;
271 0 : Parent = RHS.Parent;
272 0 : DFSInfoValid = RHS.DFSInfoValid;
273 0 : SlowQueries = RHS.SlowQueries;
274 0 : RHS.wipe();
275 0 : return *this;
276 : }
277 0 :
278 0 : DominatorTreeBase(const DominatorTreeBase &) = delete;
279 0 : DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
280 0 :
281 0 : /// getRoots - Return the root blocks of the current CFG. This may include
282 : /// multiple blocks if we are computing post dominators. For forward
283 0 : /// dominators, this will always be a single block (the entry node).
284 : ///
285 0 : const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
286 :
287 0 : /// isPostDominator - Returns true if analysis based of postdoms
288 0 : ///
289 0 : bool isPostDominator() const { return IsPostDominator; }
290 0 :
291 0 : /// compare - Return false if the other dominator tree base matches this
292 : /// dominator tree base. Otherwise return true.
293 0 : bool compare(const DominatorTreeBase &Other) const {
294 0 : if (Parent != Other.Parent) return true;
295 0 :
296 0 : if (Roots.size() != Other.Roots.size())
297 0 : return true;
298 0 :
299 0 : if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
300 0 : return true;
301 0 :
302 0 : const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
303 0 : if (DomTreeNodes.size() != OtherDomTreeNodes.size())
304 : return true;
305 0 :
306 0 : for (const auto &DomTreeNode : DomTreeNodes) {
307 0 : NodeT *BB = DomTreeNode.first;
308 0 : typename DomTreeNodeMapType::const_iterator OI =
309 0 : OtherDomTreeNodes.find(BB);
310 0 : if (OI == OtherDomTreeNodes.end())
311 0 : return true;
312 :
313 0 : DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
314 : DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
315 :
316 0 : if (MyNd.compare(&OtherNd))
317 : return true;
318 : }
319 :
320 0 : return false;
321 : }
322 :
323 0 : void releaseMemory() { reset(); }
324 :
325 : /// getNode - return the (Post)DominatorTree node for the specified basic
326 : /// block. This is the same as using operator[] on this class. The result
327 0 : /// may (but is not required to) be null for a forward (backwards)
328 : /// statically unreachable block.
329 0 : DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
330 20900274 : auto I = DomTreeNodes.find(BB);
331 20901003 : if (I != DomTreeNodes.end())
332 717 : return I->second.get();
333 : return nullptr;
334 2151 : }
335 :
336 : /// See getNode.
337 717 : DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
338 0 : return getNode(BB);
339 : }
340 717 :
341 717 : /// getRootNode - This returns the entry node for the CFG of the function. If
342 : /// this tree represents the post-dominance relations for a function, however,
343 : /// this root may be a node with the block == NULL. This is the case when
344 7428 : /// there are multiple exit nodes from a particular function. Consumers of
345 6713 : /// post-dominance information must be capable of dealing with this
346 6713 : /// possibility.
347 : ///
348 6713 : DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
349 3350 : const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
350 :
351 : /// Get all nodes dominated by R, including R itself.
352 0 : void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
353 : Result.clear();
354 6713 : const DomTreeNodeBase<NodeT> *RN = getNode(R);
355 0 : if (!RN)
356 0 : return; // If R is unreachable, it will not be present in the DOM tree.
357 : SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
358 715 : WL.push_back(RN);
359 :
360 351 : while (!WL.empty()) {
361 351 : const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
362 0 : Result.push_back(N->getBlock());
363 1053 : WL.append(N->begin(), N->end());
364 : }
365 : }
366 351 :
367 : /// properlyDominates - Returns true iff A dominates B and A != B.
368 : /// Note that this is not a constant time operation!
369 351 : ///
370 351 : bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
371 : const DomTreeNodeBase<NodeT> *B) const {
372 22992 : if (!A || !B)
373 4210 : return false;
374 26852 : if (A == B)
375 3860 : return false;
376 19471 : return dominates(A, B);
377 3860 : }
378 1 :
379 : bool properlyDominates(const NodeT *A, const NodeT *B) const;
380 :
381 : /// isReachableFromEntry - Return true if A is dominated by the entry
382 : /// block of the function containing it.
383 3892 : bool isReachableFromEntry(const NodeT *A) const {
384 : assert(!this->isPostDominator() &&
385 : "This is not implemented for post dominators");
386 32 : return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
387 350 : }
388 :
389 398 : bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
390 366 :
391 : /// dominates - Returns true iff A dominates B. Note that this is not a
392 1098 : /// constant time operation!
393 : ///
394 2552944 : bool dominates(const DomTreeNodeBase<NodeT> *A,
395 366 : const DomTreeNodeBase<NodeT> *B) const {
396 : // A node trivially dominates itself.
397 2552944 : if (B == A)
398 366 : return true;
399 366 :
400 : // An unreachable node is dominated by anything.
401 2552717 : if (!isReachableFromEntry(B))
402 3218 : return true;
403 2853 :
404 2853 : // And dominates nothing.
405 2552705 : if (!isReachableFromEntry(A))
406 2853 : return false;
407 0 :
408 2514108 : if (B->getIDom() == A) return true;
409 :
410 2381220 : if (A->getIDom() == B) return false;
411 :
412 2853 : // A can only dominate B if it is higher in the tree.
413 1235699 : if (A->getLevel() >= B->getLevel()) return false;
414 :
415 : // Compare the result of the tree walk and the dfs numbers, if expensive
416 365 : // checks are enabled.
417 : #ifdef EXPENSIVE_CHECKS
418 : assert((!DFSInfoValid ||
419 0 : (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
420 : "Tree walk disagrees with dfs numbers!");
421 : #endif
422 :
423 476076 : if (DFSInfoValid)
424 0 : return B->DominatedBy(A);
425 0 :
426 60575003 : // If we end up with too many slow queries, just update the
427 60575155 : // DFS numbers on the theory that we are going to keep querying.
428 254961 : SlowQueries++;
429 254961 : if (SlowQueries > 32) {
430 3347 : updateDFSNumbers();
431 0 : return B->DominatedBy(A);
432 0 : }
433 0 :
434 251614 : return dominatedBySlowTreeWalk(A, B);
435 : }
436 :
437 0 : bool dominates(const NodeT *A, const NodeT *B) const;
438 0 :
439 0 : NodeT *getRoot() const {
440 0 : assert(this->Roots.size() == 1 && "Should always have entry node!");
441 140654 : return this->Roots[0];
442 : }
443 :
444 : /// findNearestCommonDominator - Find nearest common dominator basic block
445 0 : /// for basic block A and B. If there is no such block then return nullptr.
446 36 : NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
447 : assert(A && B && "Pointers are not valid");
448 0 : assert(A->getParent() == B->getParent() &&
449 0 : "Two blocks are not in same function");
450 :
451 0 : // If either A or B is a entry block then it is nearest common dominator
452 0 : // (for forward-dominators).
453 : if (!isPostDominator()) {
454 36 : NodeT &Entry = A->getParent()->front();
455 36 : if (A == &Entry || B == &Entry)
456 : return &Entry;
457 : }
458 :
459 : DomTreeNodeBase<NodeT> *NodeA = getNode(A);
460 : DomTreeNodeBase<NodeT> *NodeB = getNode(B);
461 :
462 25 : if (!NodeA || !NodeB) return nullptr;
463 56202 :
464 : // Use level information to go up the tree until the levels match. Then
465 : // continue going up til we arrive at the same node.
466 551 : while (NodeA && NodeA != NodeB) {
467 36 : if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
468 490 :
469 526 : NodeA = NodeA->IDom;
470 1 : }
471 :
472 514 : return NodeA ? NodeA->getBlock() : nullptr;
473 : }
474 1113 :
475 0 : const NodeT *findNearestCommonDominator(const NodeT *A,
476 624 : const NodeT *B) const {
477 624 : // Cast away the const qualifiers here. This is ok since
478 : // const is re-introduced on the return type.
479 : return findNearestCommonDominator(const_cast<NodeT *>(A),
480 0 : const_cast<NodeT *>(B));
481 : }
482 0 :
483 0 : bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
484 0 : return isPostDominator() && !A->getBlock();
485 : }
486 0 :
487 : //===--------------------------------------------------------------------===//
488 0 : // API to update (Post)DominatorTree information based on modifications to
489 : // the CFG...
490 0 :
491 0 : /// Inform the dominator tree about a sequence of CFG edge insertions and
492 : /// deletions and perform a batch update on the tree.
493 : ///
494 490 : /// This function should be used when there were multiple CFG updates after
495 : /// the last dominator tree update. It takes care of performing the updates
496 490 : /// in sync with the CFG and optimizes away the redundant operations that
497 490 : /// cancel each other.
498 1 : /// The functions expects the sequence of updates to be balanced. Eg.:
499 : /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
500 489 : /// logically it results in a single insertions.
501 : /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
502 1113 : /// sense to insert the same edge twice.
503 : ///
504 624 : /// What's more, the functions assumes that it's safe to ask every node in the
505 624 : /// CFG about its children and inverse children. This implies that deletions
506 : /// of CFG edges must not delete the CFG nodes before calling this function.
507 : ///
508 : /// The applyUpdates function can reorder the updates and remove redundant
509 : /// ones internally. The batch updater is also able to detect sequences of
510 : /// zero and exactly one update -- it's optimized to do less work in these
511 : /// cases.
512 0 : ///
513 : /// Note that for postdominators it automatically takes care of applying
514 0 : /// updates on reverse edges internally (so there's no need to swap the
515 : /// From and To pointers when constructing DominatorTree::UpdateType).
516 0 : /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
517 : /// with the same template parameter T.
518 0 : ///
519 : /// \param Updates An unordered sequence of updates to perform.
520 0 : ///
521 0 : void applyUpdates(ArrayRef<UpdateType> Updates) {
522 17699 : DomTreeBuilder::ApplyUpdates(*this, Updates);
523 0 : }
524 0 :
525 : /// Inform the dominator tree about a CFG edge insertion and update the tree.
526 0 : ///
527 : /// This function has to be called just before or just after making the update
528 0 : /// on the actual CFG. There cannot be any other updates that the dominator
529 : /// tree doesn't know about.
530 0 : ///
531 : /// Note that for postdominators it automatically takes care of inserting
532 0 : /// a reverse edge internally (so there's no need to swap the parameters).
533 : ///
534 0 : void insertEdge(NodeT *From, NodeT *To) {
535 : assert(From);
536 : assert(To);
537 : assert(From->getParent() == Parent);
538 : assert(To->getParent() == Parent);
539 432 : DomTreeBuilder::InsertEdge(*this, From, To);
540 0 : }
541 4074417 :
542 : /// Inform the dominator tree about a CFG edge deletion and update the tree.
543 : ///
544 4074417 : /// This function has to be called just after making the update on the actual
545 : /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
546 0 : /// DEBUG mode. There cannot be any other updates that the
547 : /// dominator tree doesn't know about.
548 : ///
549 0 : /// Note that for postdominators it automatically takes care of deleting
550 : /// a reverse edge internally (so there's no need to swap the parameters).
551 4074417 : ///
552 0 : void deleteEdge(NodeT *From, NodeT *To) {
553 : assert(From);
554 4074417 : assert(To);
555 : assert(From->getParent() == Parent);
556 : assert(To->getParent() == Parent);
557 4075723 : DomTreeBuilder::DeleteEdge(*this, From, To);
558 0 : }
559 :
560 : /// Add a new node to the dominator tree information.
561 : ///
562 12989621 : /// This creates a new node as a child of DomBB dominator node, linking it
563 : /// into the children list of the immediate dominator.
564 : ///
565 12989621 : /// \param BB New node in CFG.
566 : /// \param DomBB CFG node that is dominator for BB.
567 : /// \returns New dominator tree node that represents new CFG node.
568 : ///
569 13023249 : DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
570 : assert(getNode(BB) == nullptr && "Block already in dominator tree!");
571 : DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
572 : assert(IDomNode && "Not immediate dominator specified for block!");
573 13023097 : DFSInfoValid = false;
574 33628 : return (DomTreeNodes[BB] = IDomNode->addChild(
575 33628 : llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
576 12988823 : }
577 :
578 12229433 : /// Add a new node to the forward dominator tree and make it a new root.
579 : ///
580 : /// \param BB New node in CFG.
581 7266338 : /// \returns New dominator tree node that represents new CFG node.
582 : ///
583 0 : DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
584 : assert(getNode(BB) == nullptr && "Block already in dominator tree!");
585 : assert(!this->isPostDominator() &&
586 : "Cannot change root of post-dominator tree");
587 0 : DFSInfoValid = false;
588 0 : DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
589 : llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
590 0 : if (Roots.empty()) {
591 2922708 : addRoot(BB);
592 : } else {
593 : assert(Roots.size() == 1);
594 0 : NodeT *OldRoot = Roots.front();
595 : auto &OldNode = DomTreeNodes[OldRoot];
596 970357 : OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
597 970357 : OldNode->IDom = NewNode;
598 11668 : OldNode->UpdateLevel();
599 0 : Roots[0] = BB;
600 : }
601 0 : return RootNode = NewNode;
602 958689 : }
603 :
604 775 : /// changeImmediateDominator - This method is used to update the dominator
605 : /// tree information when a node's immediate dominator changes.
606 : ///
607 775 : void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
608 : DomTreeNodeBase<NodeT> *NewIDom) {
609 : assert(N && NewIDom && "Cannot change null node pointers!");
610 16804 : DFSInfoValid = false;
611 17579 : N->setIDom(NewIDom);
612 0 : }
613 :
614 0 : void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
615 775 : changeImmediateDominator(getNode(BB), getNode(NewBB));
616 0 : }
617 :
618 775 : /// eraseNode - Removes a node from the dominator tree. Block must not
619 : /// dominate any other blocks. Removes node from its immediate dominator's
620 587 : /// children list. Deletes dominator node associated with basic block BB.
621 0 : void eraseNode(NodeT *BB) {
622 0 : DomTreeNodeBase<NodeT> *Node = getNode(BB);
623 552 : assert(Node && "Removing node that isn't in dominator tree.");
624 : assert(Node->getChildren().empty() && "Node is not a leaf node.");
625 :
626 0 : DFSInfoValid = false;
627 :
628 : // Remove node from immediate dominator's children list.
629 0 : DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
630 0 : if (IDom) {
631 : const auto I = find(IDom->Children, Node);
632 : assert(I != IDom->Children.end() &&
633 111 : "Not in immediate dominator children set!");
634 : // I am no longer your child...
635 0 : IDom->Children.erase(I);
636 : }
637 :
638 111 : DomTreeNodes.erase(BB);
639 111 :
640 0 : if (!IsPostDom) return;
641 :
642 : // Remember to update PostDominatorTree roots.
643 : auto RIt = llvm::find(Roots, BB);
644 111 : if (RIt != Roots.end()) {
645 : std::swap(*RIt, Roots.back());
646 12988846 : Roots.pop_back();
647 : }
648 : }
649 12988846 :
650 : /// splitBlock - BB is split and now it has one successor. Update dominator
651 : /// tree to reflect this change.
652 0 : void splitBlock(NodeT *NewBB) {
653 12988846 : if (IsPostDominator)
654 0 : Split<Inverse<NodeT *>>(NewBB);
655 : else
656 26242 : Split<NodeT *>(NewBB);
657 12988694 : }
658 :
659 : /// print - Convert to human readable form
660 12988048 : ///
661 0 : void print(raw_ostream &O) const {
662 12228846 : O << "=============================--------------------------------\n";
663 : if (IsPostDominator)
664 0 : O << "Inorder PostDominator Tree: ";
665 7265786 : else
666 0 : O << "Inorder Dominator Tree: ";
667 0 : if (!DFSInfoValid)
668 0 : O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
669 0 : O << "\n";
670 :
671 : // The postdom tree can have a null root if there are no returns.
672 0 : if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
673 : if (IsPostDominator) {
674 0 : O << "Roots: ";
675 2922597 : for (const NodePtr Block : Roots) {
676 0 : Block->printAsOperand(O, false);
677 0 : O << " ";
678 : }
679 0 : O << "\n";
680 970246 : }
681 970246 : }
682 11668 :
683 : public:
684 : /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
685 : /// dominator tree in dfs order.
686 961927 : void updateDFSNumbers() const {
687 3349 : if (DFSInfoValid) {
688 0 : SlowQueries = 0;
689 0 : return;
690 : }
691 0 :
692 : SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
693 362 : typename DomTreeNodeBase<NodeT>::const_iterator>,
694 : 32> WorkStack;
695 0 :
696 0 : const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
697 0 : assert((!Parent || ThisRoot) && "Empty constructed DomTree");
698 3349 : if (!ThisRoot)
699 0 : return;
700 :
701 0 : // Both dominators and postdominators have a single root node. In the case
702 : // case of PostDominatorTree, this node is a virtual root.
703 3349 : WorkStack.push_back({ThisRoot, ThisRoot->begin()});
704 :
705 : unsigned DFSNum = 0;
706 147833 : ThisRoot->DFSNumIn = DFSNum++;
707 :
708 1439708 : while (!WorkStack.empty()) {
709 1436359 : const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
710 1436359 : const auto ChildIt = WorkStack.back().second;
711 :
712 : // If we visited all of the children of this node, "recurse" back up the
713 : // stack setting the DFOutNum.
714 1580524 : if (ChildIt == Node->end()) {
715 864019 : Node->DFSNumOut = DFSNum++;
716 : WorkStack.pop_back();
717 : } else {
718 : // Otherwise, recursively visit this child.
719 716505 : const DomTreeNodeBase<NodeT> *Child = *ChildIt;
720 : ++WorkStack.back().second;
721 :
722 851788 : WorkStack.push_back({Child, Child->begin()});
723 716505 : Child->DFSNumIn = DFSNum++;
724 : }
725 : }
726 1006265 :
727 874331 : SlowQueries = 0;
728 3349 : DFSInfoValid = true;
729 870982 : }
730 :
731 : /// recalculate - compute a dominator tree for the given function
732 135283 : void recalculate(ParentType &Func) {
733 3159953 : Parent = &Func;
734 997844 : DomTreeBuilder::Calculate(*this);
735 0 : }
736 :
737 0 : void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
738 0 : Parent = &Func;
739 0 : DomTreeBuilder::CalculateWithUpdates(*this, Updates);
740 0 : }
741 :
742 : /// verify - checks if the tree is correct. There are 3 level of verification:
743 : /// - Full -- verifies if the tree is correct by making sure all the
744 : /// properties (including the parent and the sibling property)
745 : /// hold.
746 : /// Takes O(N^3) time.
747 : ///
748 : /// - Basic -- checks if the tree is correct, but compares it to a freshly
749 : /// constructed tree instead of checking the sibling property.
750 319 : /// Takes O(N^2) time.
751 : ///
752 : /// - Fast -- checks basic tree structure and compares it with a freshly
753 : /// constructed tree.
754 1070 : /// Takes O(N^2) time worst case, but is faster in practise (same
755 751 : /// as tree construction).
756 0 : bool verify(VerificationLevel VL = VerificationLevel::Full) const {
757 1365 : return DomTreeBuilder::Verify(*this, VL);
758 : }
759 :
760 319 : protected:
761 0 : void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
762 144165 :
763 0 : void reset() {
764 2315981 : DomTreeNodes.clear();
765 : Roots.clear();
766 2315981 : RootNode = nullptr;
767 153541 : Parent = nullptr;
768 2315981 : DFSInfoValid = false;
769 2315981 : SlowQueries = 0;
770 144165 : }
771 144165 :
772 : // NewBB is split and now it has one successor. Update dominator tree to
773 : // reflect this change.
774 : template <class N>
775 0 : void Split(typename GraphTraits<N>::NodeRef NewBB) {
776 : using GraphT = GraphTraits<N>;
777 : using NodeRef = typename GraphT::NodeRef;
778 134964 : assert(std::distance(GraphT::child_begin(NewBB),
779 : GraphT::child_end(NewBB)) == 1 &&
780 : "NewBB should have a single successor!");
781 0 : NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
782 1005195 :
783 870231 : std::vector<NodeRef> PredBlocks;
784 0 : for (const auto &Pred : children<Inverse<N>>(NewBB))
785 870231 : PredBlocks.push_back(Pred);
786 :
787 : assert(!PredBlocks.empty() && "No predblocks?");
788 134964 :
789 : bool NewBBDominatesNewBBSucc = true;
790 0 : for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
791 0 : if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
792 : isReachableFromEntry(Pred)) {
793 : NewBBDominatesNewBBSucc = false;
794 : break;
795 : }
796 0 : }
797 :
798 0 : // Find NewBB's immediate dominator and create new dominator tree node for
799 : // NewBB.
800 : NodeT *NewBBIDom = nullptr;
801 : unsigned i = 0;
802 0 : for (i = 0; i < PredBlocks.size(); ++i)
803 0 : if (isReachableFromEntry(PredBlocks[i])) {
804 0 : NewBBIDom = PredBlocks[i];
805 0 : break;
806 : }
807 :
808 : // It's possible that none of the predecessors of NewBB are reachable;
809 : // in that case, NewBB itself is unreachable, so nothing needs to be
810 0 : // changed.
811 0 : if (!NewBBIDom) return;
812 :
813 0 : for (i = i + 1; i < PredBlocks.size(); ++i) {
814 4064 : if (isReachableFromEntry(PredBlocks[i]))
815 0 : NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
816 0 : }
817 0 :
818 : // Create the new dominator tree node... and set the idom of NewBB.
819 0 : DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
820 0 :
821 : // If NewBB strictly dominates other blocks, then it is now the immediate
822 : // dominator of NewBBSucc. Update the dominator tree as appropriate.
823 0 : if (NewBBDominatesNewBBSucc) {
824 : DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
825 : changeImmediateDominator(NewBBSuccNode, NewBBNode);
826 : }
827 : }
828 :
829 : private:
830 0 : bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
831 : const DomTreeNodeBase<NodeT> *B) const {
832 : assert(A != B);
833 : assert(isReachableFromEntry(B));
834 : assert(isReachableFromEntry(A));
835 :
836 314 : const unsigned ALevel = A->getLevel();
837 : const DomTreeNodeBase<NodeT> *IDom;
838 :
839 : // Don't walk nodes above A's subtree. When we reach A's level, we must
840 : // either find A or be in some other subtree not dominated by A.
841 1014455 : while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
842 : B = IDom; // Walk up the tree
843 :
844 251614 : return B == A;
845 : }
846 :
847 : /// Wipe this tree's state without releasing any resources.
848 : ///
849 : /// This is essentially a post-move helper only. It leaves the object in an
850 : /// assignable and destroyable state, but otherwise invalid.
851 0 : void wipe() {
852 0 : DomTreeNodes.clear();
853 0 : RootNode = nullptr;
854 0 : Parent = nullptr;
855 0 : }
856 : };
857 0 :
858 0 : template <typename T>
859 0 : using DomTreeBase = DominatorTreeBase<T, false>;
860 0 :
861 0 : template <typename T>
862 0 : using PostDomTreeBase = DominatorTreeBase<T, true>;
863 0 :
864 0 : // These two functions are declared out of line as a workaround for building
865 0 : // with old (< r147295) versions of clang because of pr11642.
866 : template <typename NodeT, bool IsPostDom>
867 2727682 : bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
868 : const NodeT *B) const {
869 2727682 : if (A == B)
870 : return true;
871 :
872 : // Cast away the const qualifiers here. This is ok since
873 : // this function doesn't actually return the values returned
874 : // from getNode.
875 : return dominates(getNode(const_cast<NodeT *>(A)),
876 2505783 : getNode(const_cast<NodeT *>(B)));
877 : }
878 : template <typename NodeT, bool IsPostDom>
879 13747 : bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
880 : const NodeT *A, const NodeT *B) const {
881 13950 : if (A == B)
882 0 : return false;
883 0 :
884 : // Cast away the const qualifiers here. This is ok since
885 : // this function doesn't actually return the values returned
886 : // from getNode.
887 : return dominates(getNode(const_cast<NodeT *>(A)),
888 13492 : getNode(const_cast<NodeT *>(B)));
889 0 : }
890 0 :
891 : } // end namespace llvm
892 :
893 : #endif // LLVM_SUPPORT_GENERICDOMTREE_H
|
