1274955Ssvnmir//===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===// 2274955Ssvnmir// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6274955Ssvnmir// 7274955Ssvnmir//===----------------------------------------------------------------------===// 8274955Ssvnmir/// \file 9274955Ssvnmir/// 10274955Ssvnmir/// This file defines a set of templates that efficiently compute a dominator 11274955Ssvnmir/// tree over a generic graph. This is used typically in LLVM for fast 12274955Ssvnmir/// dominance queries on the CFG, but is fully generic w.r.t. the underlying 13274955Ssvnmir/// graph types. 14274955Ssvnmir/// 15321369Sdim/// Unlike ADT/* graph algorithms, generic dominator tree has more requirements 16327952Sdim/// on the graph's NodeRef. The NodeRef should be a pointer and, 17327952Sdim/// NodeRef->getParent() must return the parent node that is also a pointer. 18314564Sdim/// 19314564Sdim/// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits. 20314564Sdim/// 21274955Ssvnmir//===----------------------------------------------------------------------===// 22274955Ssvnmir 23280031Sdim#ifndef LLVM_SUPPORT_GENERICDOMTREE_H 24280031Sdim#define LLVM_SUPPORT_GENERICDOMTREE_H 25274955Ssvnmir 26344779Sdim#include "llvm/ADT/DenseMap.h" 27344779Sdim#include "llvm/ADT/GraphTraits.h" 28344779Sdim#include "llvm/ADT/PointerIntPair.h" 29344779Sdim#include "llvm/ADT/STLExtras.h" 30344779Sdim#include "llvm/ADT/SmallPtrSet.h" 31344779Sdim#include "llvm/ADT/SmallVector.h" 32344779Sdim#include "llvm/Support/CFGUpdate.h" 33344779Sdim#include "llvm/Support/raw_ostream.h" 34274955Ssvnmir#include <algorithm> 35321369Sdim#include <cassert> 36321369Sdim#include <cstddef> 37321369Sdim#include <iterator> 38321369Sdim#include <memory> 39321369Sdim#include <type_traits> 40321369Sdim#include <utility> 41321369Sdim#include <vector> 42274955Ssvnmir 43274955Ssvnmirnamespace llvm { 44274955Ssvnmir 45321369Sdimtemplate <typename NodeT, bool IsPostDom> 46321369Sdimclass DominatorTreeBase; 47314564Sdim 48321369Sdimnamespace DomTreeBuilder { 49327952Sdimtemplate <typename DomTreeT> 50321369Sdimstruct SemiNCAInfo; 51321369Sdim} // namespace DomTreeBuilder 52314564Sdim 53341825Sdim/// Base class for the actual dominator tree node. 54280031Sdimtemplate <class NodeT> class DomTreeNodeBase { 55341825Sdim friend class PostDominatorTree; 56321369Sdim friend class DominatorTreeBase<NodeT, false>; 57321369Sdim friend class DominatorTreeBase<NodeT, true>; 58321369Sdim friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>; 59321369Sdim friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>; 60321369Sdim 61274955Ssvnmir NodeT *TheBB; 62321369Sdim DomTreeNodeBase *IDom; 63321369Sdim unsigned Level; 64321369Sdim std::vector<DomTreeNodeBase *> Children; 65321369Sdim mutable unsigned DFSNumIn = ~0; 66321369Sdim mutable unsigned DFSNumOut = ~0; 67274955Ssvnmir 68321369Sdim public: 69321369Sdim DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) 70321369Sdim : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {} 71280031Sdim 72321369Sdim using iterator = typename std::vector<DomTreeNodeBase *>::iterator; 73321369Sdim using const_iterator = 74321369Sdim typename std::vector<DomTreeNodeBase *>::const_iterator; 75274955Ssvnmir 76280031Sdim iterator begin() { return Children.begin(); } 77280031Sdim iterator end() { return Children.end(); } 78274955Ssvnmir const_iterator begin() const { return Children.begin(); } 79280031Sdim const_iterator end() const { return Children.end(); } 80274955Ssvnmir 81274955Ssvnmir NodeT *getBlock() const { return TheBB; } 82321369Sdim DomTreeNodeBase *getIDom() const { return IDom; } 83321369Sdim unsigned getLevel() const { return Level; } 84274955Ssvnmir 85321369Sdim const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; } 86274955Ssvnmir 87321369Sdim std::unique_ptr<DomTreeNodeBase> addChild( 88321369Sdim std::unique_ptr<DomTreeNodeBase> C) { 89288943Sdim Children.push_back(C.get()); 90274955Ssvnmir return C; 91274955Ssvnmir } 92274955Ssvnmir 93280031Sdim size_t getNumChildren() const { return Children.size(); } 94274955Ssvnmir 95280031Sdim void clearAllChildren() { Children.clear(); } 96274955Ssvnmir 97321369Sdim bool compare(const DomTreeNodeBase *Other) const { 98274955Ssvnmir if (getNumChildren() != Other->getNumChildren()) 99274955Ssvnmir return true; 100274955Ssvnmir 101321369Sdim if (Level != Other->Level) return true; 102321369Sdim 103274955Ssvnmir SmallPtrSet<const NodeT *, 4> OtherChildren; 104309124Sdim for (const DomTreeNodeBase *I : *Other) { 105309124Sdim const NodeT *Nd = I->getBlock(); 106274955Ssvnmir OtherChildren.insert(Nd); 107274955Ssvnmir } 108274955Ssvnmir 109309124Sdim for (const DomTreeNodeBase *I : *this) { 110309124Sdim const NodeT *N = I->getBlock(); 111274955Ssvnmir if (OtherChildren.count(N) == 0) 112274955Ssvnmir return true; 113274955Ssvnmir } 114274955Ssvnmir return false; 115274955Ssvnmir } 116274955Ssvnmir 117321369Sdim void setIDom(DomTreeNodeBase *NewIDom) { 118274955Ssvnmir assert(IDom && "No immediate dominator?"); 119321369Sdim if (IDom == NewIDom) return; 120274955Ssvnmir 121321369Sdim auto I = find(IDom->Children, this); 122321369Sdim assert(I != IDom->Children.end() && 123321369Sdim "Not in immediate dominator children set!"); 124321369Sdim // I am no longer your child... 125321369Sdim IDom->Children.erase(I); 126321369Sdim 127321369Sdim // Switch to new dominator 128321369Sdim IDom = NewIDom; 129321369Sdim IDom->Children.push_back(this); 130321369Sdim 131321369Sdim UpdateLevel(); 132274955Ssvnmir } 133274955Ssvnmir 134309124Sdim /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes 135309124Sdim /// in the dominator tree. They are only guaranteed valid if 136309124Sdim /// updateDFSNumbers() has been called. 137274955Ssvnmir unsigned getDFSNumIn() const { return DFSNumIn; } 138274955Ssvnmir unsigned getDFSNumOut() const { return DFSNumOut; } 139280031Sdim 140274955Ssvnmirprivate: 141274955Ssvnmir // Return true if this node is dominated by other. Use this only if DFS info 142274955Ssvnmir // is valid. 143321369Sdim bool DominatedBy(const DomTreeNodeBase *other) const { 144274955Ssvnmir return this->DFSNumIn >= other->DFSNumIn && 145280031Sdim this->DFSNumOut <= other->DFSNumOut; 146274955Ssvnmir } 147321369Sdim 148321369Sdim void UpdateLevel() { 149321369Sdim assert(IDom); 150321369Sdim if (Level == IDom->Level + 1) return; 151321369Sdim 152321369Sdim SmallVector<DomTreeNodeBase *, 64> WorkStack = {this}; 153321369Sdim 154321369Sdim while (!WorkStack.empty()) { 155321369Sdim DomTreeNodeBase *Current = WorkStack.pop_back_val(); 156321369Sdim Current->Level = Current->IDom->Level + 1; 157321369Sdim 158321369Sdim for (DomTreeNodeBase *C : *Current) { 159321369Sdim assert(C->IDom); 160321369Sdim if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C); 161321369Sdim } 162321369Sdim } 163321369Sdim } 164274955Ssvnmir}; 165274955Ssvnmir 166280031Sdimtemplate <class NodeT> 167321369Sdimraw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) { 168274955Ssvnmir if (Node->getBlock()) 169321369Sdim Node->getBlock()->printAsOperand(O, false); 170274955Ssvnmir else 171321369Sdim O << " <<exit node>>"; 172274955Ssvnmir 173321369Sdim O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} [" 174321369Sdim << Node->getLevel() << "]\n"; 175274955Ssvnmir 176321369Sdim return O; 177274955Ssvnmir} 178274955Ssvnmir 179280031Sdimtemplate <class NodeT> 180321369Sdimvoid PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O, 181280031Sdim unsigned Lev) { 182321369Sdim O.indent(2 * Lev) << "[" << Lev << "] " << N; 183274955Ssvnmir for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), 184280031Sdim E = N->end(); 185280031Sdim I != E; ++I) 186321369Sdim PrintDomTree<NodeT>(*I, O, Lev + 1); 187274955Ssvnmir} 188274955Ssvnmir 189321369Sdimnamespace DomTreeBuilder { 190321369Sdim// The routines below are provided in a separate header but referenced here. 191327952Sdimtemplate <typename DomTreeT> 192327952Sdimvoid Calculate(DomTreeT &DT); 193280031Sdim 194327952Sdimtemplate <typename DomTreeT> 195344779Sdimvoid CalculateWithUpdates(DomTreeT &DT, 196344779Sdim ArrayRef<typename DomTreeT::UpdateType> Updates); 197344779Sdim 198344779Sdimtemplate <typename DomTreeT> 199321369Sdimvoid InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, 200321369Sdim typename DomTreeT::NodePtr To); 201321369Sdim 202327952Sdimtemplate <typename DomTreeT> 203321369Sdimvoid DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, 204321369Sdim typename DomTreeT::NodePtr To); 205321369Sdim 206321369Sdimtemplate <typename DomTreeT> 207327952Sdimvoid ApplyUpdates(DomTreeT &DT, 208327952Sdim ArrayRef<typename DomTreeT::UpdateType> Updates); 209327952Sdim 210327952Sdimtemplate <typename DomTreeT> 211341825Sdimbool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL); 212321369Sdim} // namespace DomTreeBuilder 213321369Sdim 214341825Sdim/// Core dominator tree base class. 215274955Ssvnmir/// 216280031Sdim/// This class is a generic template over graph nodes. It is instantiated for 217280031Sdim/// various graphs in the LLVM IR or in the code generator. 218321369Sdimtemplate <typename NodeT, bool IsPostDom> 219321369Sdimclass DominatorTreeBase { 220327952Sdim public: 221327952Sdim static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value, 222327952Sdim "Currently DominatorTreeBase supports only pointer nodes"); 223327952Sdim using NodeType = NodeT; 224327952Sdim using NodePtr = NodeT *; 225327952Sdim using ParentPtr = decltype(std::declval<NodeT *>()->getParent()); 226327952Sdim static_assert(std::is_pointer<ParentPtr>::value, 227327952Sdim "Currently NodeT's parent must be a pointer type"); 228327952Sdim using ParentType = typename std::remove_pointer<ParentPtr>::type; 229327952Sdim static constexpr bool IsPostDominator = IsPostDom; 230327952Sdim 231344779Sdim using UpdateType = cfg::Update<NodePtr>; 232344779Sdim using UpdateKind = cfg::UpdateKind; 233327952Sdim static constexpr UpdateKind Insert = UpdateKind::Insert; 234327952Sdim static constexpr UpdateKind Delete = UpdateKind::Delete; 235327952Sdim 236341825Sdim enum class VerificationLevel { Fast, Basic, Full }; 237341825Sdim 238341825Sdimprotected: 239327952Sdim // Dominators always have a single root, postdominators can have more. 240327952Sdim SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots; 241274955Ssvnmir 242321369Sdim using DomTreeNodeMapType = 243321369Sdim DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>; 244274955Ssvnmir DomTreeNodeMapType DomTreeNodes; 245360784Sdim DomTreeNodeBase<NodeT> *RootNode = nullptr; 246321369Sdim ParentPtr Parent = nullptr; 247274955Ssvnmir 248321369Sdim mutable bool DFSInfoValid = false; 249321369Sdim mutable unsigned int SlowQueries = 0; 250274955Ssvnmir 251321369Sdim friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>; 252274955Ssvnmir 253321369Sdim public: 254321369Sdim DominatorTreeBase() {} 255274955Ssvnmir 256280031Sdim DominatorTreeBase(DominatorTreeBase &&Arg) 257321369Sdim : Roots(std::move(Arg.Roots)), 258280031Sdim DomTreeNodes(std::move(Arg.DomTreeNodes)), 259321369Sdim RootNode(Arg.RootNode), 260321369Sdim Parent(Arg.Parent), 261321369Sdim DFSInfoValid(Arg.DFSInfoValid), 262321369Sdim SlowQueries(Arg.SlowQueries) { 263280031Sdim Arg.wipe(); 264280031Sdim } 265321369Sdim 266280031Sdim DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { 267321369Sdim Roots = std::move(RHS.Roots); 268280031Sdim DomTreeNodes = std::move(RHS.DomTreeNodes); 269321369Sdim RootNode = RHS.RootNode; 270321369Sdim Parent = RHS.Parent; 271321369Sdim DFSInfoValid = RHS.DFSInfoValid; 272321369Sdim SlowQueries = RHS.SlowQueries; 273280031Sdim RHS.wipe(); 274280031Sdim return *this; 275280031Sdim } 276280031Sdim 277321369Sdim DominatorTreeBase(const DominatorTreeBase &) = delete; 278321369Sdim DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; 279321369Sdim 280321369Sdim /// getRoots - Return the root blocks of the current CFG. This may include 281321369Sdim /// multiple blocks if we are computing post dominators. For forward 282321369Sdim /// dominators, this will always be a single block (the entry node). 283321369Sdim /// 284327952Sdim const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; } 285321369Sdim 286321369Sdim /// isPostDominator - Returns true if analysis based of postdoms 287321369Sdim /// 288321369Sdim bool isPostDominator() const { return IsPostDominator; } 289321369Sdim 290274955Ssvnmir /// compare - Return false if the other dominator tree base matches this 291274955Ssvnmir /// dominator tree base. Otherwise return true. 292274955Ssvnmir bool compare(const DominatorTreeBase &Other) const { 293321369Sdim if (Parent != Other.Parent) return true; 294274955Ssvnmir 295341825Sdim if (Roots.size() != Other.Roots.size()) 296341825Sdim return true; 297341825Sdim 298341825Sdim if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin())) 299341825Sdim return true; 300341825Sdim 301274955Ssvnmir const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; 302274955Ssvnmir if (DomTreeNodes.size() != OtherDomTreeNodes.size()) 303274955Ssvnmir return true; 304274955Ssvnmir 305321369Sdim for (const auto &DomTreeNode : DomTreeNodes) { 306309124Sdim NodeT *BB = DomTreeNode.first; 307280031Sdim typename DomTreeNodeMapType::const_iterator OI = 308280031Sdim OtherDomTreeNodes.find(BB); 309274955Ssvnmir if (OI == OtherDomTreeNodes.end()) 310274955Ssvnmir return true; 311274955Ssvnmir 312309124Sdim DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second; 313288943Sdim DomTreeNodeBase<NodeT> &OtherNd = *OI->second; 314274955Ssvnmir 315288943Sdim if (MyNd.compare(&OtherNd)) 316274955Ssvnmir return true; 317274955Ssvnmir } 318274955Ssvnmir 319274955Ssvnmir return false; 320274955Ssvnmir } 321274955Ssvnmir 322280031Sdim void releaseMemory() { reset(); } 323274955Ssvnmir 324274955Ssvnmir /// getNode - return the (Post)DominatorTree node for the specified basic 325296417Sdim /// block. This is the same as using operator[] on this class. The result 326296417Sdim /// may (but is not required to) be null for a forward (backwards) 327296417Sdim /// statically unreachable block. 328341825Sdim DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const { 329288943Sdim auto I = DomTreeNodes.find(BB); 330288943Sdim if (I != DomTreeNodes.end()) 331288943Sdim return I->second.get(); 332288943Sdim return nullptr; 333274955Ssvnmir } 334274955Ssvnmir 335296417Sdim /// See getNode. 336341825Sdim DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const { 337341825Sdim return getNode(BB); 338341825Sdim } 339274955Ssvnmir 340274955Ssvnmir /// getRootNode - This returns the entry node for the CFG of the function. If 341274955Ssvnmir /// this tree represents the post-dominance relations for a function, however, 342274955Ssvnmir /// this root may be a node with the block == NULL. This is the case when 343274955Ssvnmir /// there are multiple exit nodes from a particular function. Consumers of 344274955Ssvnmir /// post-dominance information must be capable of dealing with this 345274955Ssvnmir /// possibility. 346274955Ssvnmir /// 347274955Ssvnmir DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } 348274955Ssvnmir const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } 349274955Ssvnmir 350274955Ssvnmir /// Get all nodes dominated by R, including R itself. 351274955Ssvnmir void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { 352274955Ssvnmir Result.clear(); 353274955Ssvnmir const DomTreeNodeBase<NodeT> *RN = getNode(R); 354274955Ssvnmir if (!RN) 355274955Ssvnmir return; // If R is unreachable, it will not be present in the DOM tree. 356274955Ssvnmir SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; 357274955Ssvnmir WL.push_back(RN); 358274955Ssvnmir 359274955Ssvnmir while (!WL.empty()) { 360274955Ssvnmir const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); 361274955Ssvnmir Result.push_back(N->getBlock()); 362274955Ssvnmir WL.append(N->begin(), N->end()); 363274955Ssvnmir } 364274955Ssvnmir } 365274955Ssvnmir 366274955Ssvnmir /// properlyDominates - Returns true iff A dominates B and A != B. 367274955Ssvnmir /// Note that this is not a constant time operation! 368274955Ssvnmir /// 369274955Ssvnmir bool properlyDominates(const DomTreeNodeBase<NodeT> *A, 370274955Ssvnmir const DomTreeNodeBase<NodeT> *B) const { 371274955Ssvnmir if (!A || !B) 372274955Ssvnmir return false; 373274955Ssvnmir if (A == B) 374274955Ssvnmir return false; 375274955Ssvnmir return dominates(A, B); 376274955Ssvnmir } 377274955Ssvnmir 378274955Ssvnmir bool properlyDominates(const NodeT *A, const NodeT *B) const; 379274955Ssvnmir 380274955Ssvnmir /// isReachableFromEntry - Return true if A is dominated by the entry 381274955Ssvnmir /// block of the function containing it. 382280031Sdim bool isReachableFromEntry(const NodeT *A) const { 383274955Ssvnmir assert(!this->isPostDominator() && 384274955Ssvnmir "This is not implemented for post dominators"); 385274955Ssvnmir return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); 386274955Ssvnmir } 387274955Ssvnmir 388280031Sdim bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; } 389274955Ssvnmir 390274955Ssvnmir /// dominates - Returns true iff A dominates B. Note that this is not a 391274955Ssvnmir /// constant time operation! 392274955Ssvnmir /// 393280031Sdim bool dominates(const DomTreeNodeBase<NodeT> *A, 394280031Sdim const DomTreeNodeBase<NodeT> *B) const { 395274955Ssvnmir // A node trivially dominates itself. 396274955Ssvnmir if (B == A) 397274955Ssvnmir return true; 398274955Ssvnmir 399274955Ssvnmir // An unreachable node is dominated by anything. 400274955Ssvnmir if (!isReachableFromEntry(B)) 401274955Ssvnmir return true; 402274955Ssvnmir 403274955Ssvnmir // And dominates nothing. 404274955Ssvnmir if (!isReachableFromEntry(A)) 405274955Ssvnmir return false; 406274955Ssvnmir 407321369Sdim if (B->getIDom() == A) return true; 408321369Sdim 409321369Sdim if (A->getIDom() == B) return false; 410321369Sdim 411321369Sdim // A can only dominate B if it is higher in the tree. 412321369Sdim if (A->getLevel() >= B->getLevel()) return false; 413321369Sdim 414274955Ssvnmir // Compare the result of the tree walk and the dfs numbers, if expensive 415274955Ssvnmir // checks are enabled. 416309124Sdim#ifdef EXPENSIVE_CHECKS 417274955Ssvnmir assert((!DFSInfoValid || 418274955Ssvnmir (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && 419274955Ssvnmir "Tree walk disagrees with dfs numbers!"); 420274955Ssvnmir#endif 421274955Ssvnmir 422274955Ssvnmir if (DFSInfoValid) 423274955Ssvnmir return B->DominatedBy(A); 424274955Ssvnmir 425274955Ssvnmir // If we end up with too many slow queries, just update the 426274955Ssvnmir // DFS numbers on the theory that we are going to keep querying. 427274955Ssvnmir SlowQueries++; 428274955Ssvnmir if (SlowQueries > 32) { 429274955Ssvnmir updateDFSNumbers(); 430274955Ssvnmir return B->DominatedBy(A); 431274955Ssvnmir } 432274955Ssvnmir 433274955Ssvnmir return dominatedBySlowTreeWalk(A, B); 434274955Ssvnmir } 435274955Ssvnmir 436274955Ssvnmir bool dominates(const NodeT *A, const NodeT *B) const; 437274955Ssvnmir 438274955Ssvnmir NodeT *getRoot() const { 439274955Ssvnmir assert(this->Roots.size() == 1 && "Should always have entry node!"); 440274955Ssvnmir return this->Roots[0]; 441274955Ssvnmir } 442274955Ssvnmir 443274955Ssvnmir /// findNearestCommonDominator - Find nearest common dominator basic block 444327952Sdim /// for basic block A and B. If there is no such block then return nullptr. 445321369Sdim NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { 446327952Sdim assert(A && B && "Pointers are not valid"); 447274955Ssvnmir assert(A->getParent() == B->getParent() && 448274955Ssvnmir "Two blocks are not in same function"); 449274955Ssvnmir 450274955Ssvnmir // If either A or B is a entry block then it is nearest common dominator 451274955Ssvnmir // (for forward-dominators). 452327952Sdim if (!isPostDominator()) { 453274955Ssvnmir NodeT &Entry = A->getParent()->front(); 454274955Ssvnmir if (A == &Entry || B == &Entry) 455274955Ssvnmir return &Entry; 456274955Ssvnmir } 457274955Ssvnmir 458274955Ssvnmir DomTreeNodeBase<NodeT> *NodeA = getNode(A); 459274955Ssvnmir DomTreeNodeBase<NodeT> *NodeB = getNode(B); 460274955Ssvnmir 461321369Sdim if (!NodeA || !NodeB) return nullptr; 462274955Ssvnmir 463321369Sdim // Use level information to go up the tree until the levels match. Then 464321369Sdim // continue going up til we arrive at the same node. 465321369Sdim while (NodeA && NodeA != NodeB) { 466321369Sdim if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB); 467274955Ssvnmir 468321369Sdim NodeA = NodeA->IDom; 469274955Ssvnmir } 470274955Ssvnmir 471321369Sdim return NodeA ? NodeA->getBlock() : nullptr; 472274955Ssvnmir } 473274955Ssvnmir 474321369Sdim const NodeT *findNearestCommonDominator(const NodeT *A, 475321369Sdim const NodeT *B) const { 476274955Ssvnmir // Cast away the const qualifiers here. This is ok since 477274955Ssvnmir // const is re-introduced on the return type. 478274955Ssvnmir return findNearestCommonDominator(const_cast<NodeT *>(A), 479274955Ssvnmir const_cast<NodeT *>(B)); 480274955Ssvnmir } 481274955Ssvnmir 482321369Sdim bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const { 483321369Sdim return isPostDominator() && !A->getBlock(); 484321369Sdim } 485321369Sdim 486274955Ssvnmir //===--------------------------------------------------------------------===// 487274955Ssvnmir // API to update (Post)DominatorTree information based on modifications to 488274955Ssvnmir // the CFG... 489274955Ssvnmir 490327952Sdim /// Inform the dominator tree about a sequence of CFG edge insertions and 491327952Sdim /// deletions and perform a batch update on the tree. 492327952Sdim /// 493327952Sdim /// This function should be used when there were multiple CFG updates after 494327952Sdim /// the last dominator tree update. It takes care of performing the updates 495327952Sdim /// in sync with the CFG and optimizes away the redundant operations that 496327952Sdim /// cancel each other. 497327952Sdim /// The functions expects the sequence of updates to be balanced. Eg.: 498327952Sdim /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because 499327952Sdim /// logically it results in a single insertions. 500327952Sdim /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make 501327952Sdim /// sense to insert the same edge twice. 502327952Sdim /// 503327952Sdim /// What's more, the functions assumes that it's safe to ask every node in the 504327952Sdim /// CFG about its children and inverse children. This implies that deletions 505327952Sdim /// of CFG edges must not delete the CFG nodes before calling this function. 506327952Sdim /// 507341825Sdim /// The applyUpdates function can reorder the updates and remove redundant 508341825Sdim /// ones internally. The batch updater is also able to detect sequences of 509341825Sdim /// zero and exactly one update -- it's optimized to do less work in these 510341825Sdim /// cases. 511327952Sdim /// 512327952Sdim /// Note that for postdominators it automatically takes care of applying 513327952Sdim /// updates on reverse edges internally (so there's no need to swap the 514327952Sdim /// From and To pointers when constructing DominatorTree::UpdateType). 515327952Sdim /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T> 516327952Sdim /// with the same template parameter T. 517327952Sdim /// 518327952Sdim /// \param Updates An unordered sequence of updates to perform. 519327952Sdim /// 520327952Sdim void applyUpdates(ArrayRef<UpdateType> Updates) { 521327952Sdim DomTreeBuilder::ApplyUpdates(*this, Updates); 522327952Sdim } 523327952Sdim 524321369Sdim /// Inform the dominator tree about a CFG edge insertion and update the tree. 525321369Sdim /// 526321369Sdim /// This function has to be called just before or just after making the update 527321369Sdim /// on the actual CFG. There cannot be any other updates that the dominator 528321369Sdim /// tree doesn't know about. 529321369Sdim /// 530321369Sdim /// Note that for postdominators it automatically takes care of inserting 531321369Sdim /// a reverse edge internally (so there's no need to swap the parameters). 532321369Sdim /// 533321369Sdim void insertEdge(NodeT *From, NodeT *To) { 534321369Sdim assert(From); 535321369Sdim assert(To); 536321369Sdim assert(From->getParent() == Parent); 537321369Sdim assert(To->getParent() == Parent); 538321369Sdim DomTreeBuilder::InsertEdge(*this, From, To); 539321369Sdim } 540321369Sdim 541321369Sdim /// Inform the dominator tree about a CFG edge deletion and update the tree. 542321369Sdim /// 543327952Sdim /// This function has to be called just after making the update on the actual 544327952Sdim /// CFG. An internal functions checks if the edge doesn't exist in the CFG in 545327952Sdim /// DEBUG mode. There cannot be any other updates that the 546327952Sdim /// dominator tree doesn't know about. 547321369Sdim /// 548321369Sdim /// Note that for postdominators it automatically takes care of deleting 549321369Sdim /// a reverse edge internally (so there's no need to swap the parameters). 550321369Sdim /// 551321369Sdim void deleteEdge(NodeT *From, NodeT *To) { 552321369Sdim assert(From); 553321369Sdim assert(To); 554321369Sdim assert(From->getParent() == Parent); 555321369Sdim assert(To->getParent() == Parent); 556321369Sdim DomTreeBuilder::DeleteEdge(*this, From, To); 557321369Sdim } 558321369Sdim 559314564Sdim /// Add a new node to the dominator tree information. 560314564Sdim /// 561314564Sdim /// This creates a new node as a child of DomBB dominator node, linking it 562314564Sdim /// into the children list of the immediate dominator. 563314564Sdim /// 564314564Sdim /// \param BB New node in CFG. 565314564Sdim /// \param DomBB CFG node that is dominator for BB. 566314564Sdim /// \returns New dominator tree node that represents new CFG node. 567314564Sdim /// 568274955Ssvnmir DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 569274955Ssvnmir assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 570274955Ssvnmir DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 571274955Ssvnmir assert(IDomNode && "Not immediate dominator specified for block!"); 572274955Ssvnmir DFSInfoValid = false; 573288943Sdim return (DomTreeNodes[BB] = IDomNode->addChild( 574360784Sdim std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get(); 575274955Ssvnmir } 576274955Ssvnmir 577314564Sdim /// Add a new node to the forward dominator tree and make it a new root. 578314564Sdim /// 579314564Sdim /// \param BB New node in CFG. 580314564Sdim /// \returns New dominator tree node that represents new CFG node. 581314564Sdim /// 582314564Sdim DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) { 583314564Sdim assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 584314564Sdim assert(!this->isPostDominator() && 585314564Sdim "Cannot change root of post-dominator tree"); 586314564Sdim DFSInfoValid = false; 587314564Sdim DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] = 588360784Sdim std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get(); 589314564Sdim if (Roots.empty()) { 590314564Sdim addRoot(BB); 591314564Sdim } else { 592314564Sdim assert(Roots.size() == 1); 593314564Sdim NodeT *OldRoot = Roots.front(); 594321369Sdim auto &OldNode = DomTreeNodes[OldRoot]; 595321369Sdim OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot])); 596321369Sdim OldNode->IDom = NewNode; 597321369Sdim OldNode->UpdateLevel(); 598314564Sdim Roots[0] = BB; 599314564Sdim } 600314564Sdim return RootNode = NewNode; 601314564Sdim } 602314564Sdim 603274955Ssvnmir /// changeImmediateDominator - This method is used to update the dominator 604274955Ssvnmir /// tree information when a node's immediate dominator changes. 605274955Ssvnmir /// 606274955Ssvnmir void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, 607274955Ssvnmir DomTreeNodeBase<NodeT> *NewIDom) { 608274955Ssvnmir assert(N && NewIDom && "Cannot change null node pointers!"); 609274955Ssvnmir DFSInfoValid = false; 610274955Ssvnmir N->setIDom(NewIDom); 611274955Ssvnmir } 612274955Ssvnmir 613274955Ssvnmir void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 614274955Ssvnmir changeImmediateDominator(getNode(BB), getNode(NewBB)); 615274955Ssvnmir } 616274955Ssvnmir 617274955Ssvnmir /// eraseNode - Removes a node from the dominator tree. Block must not 618274955Ssvnmir /// dominate any other blocks. Removes node from its immediate dominator's 619274955Ssvnmir /// children list. Deletes dominator node associated with basic block BB. 620274955Ssvnmir void eraseNode(NodeT *BB) { 621274955Ssvnmir DomTreeNodeBase<NodeT> *Node = getNode(BB); 622274955Ssvnmir assert(Node && "Removing node that isn't in dominator tree."); 623274955Ssvnmir assert(Node->getChildren().empty() && "Node is not a leaf node."); 624274955Ssvnmir 625327952Sdim DFSInfoValid = false; 626327952Sdim 627280031Sdim // Remove node from immediate dominator's children list. 628274955Ssvnmir DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 629274955Ssvnmir if (IDom) { 630327952Sdim const auto I = find(IDom->Children, Node); 631274955Ssvnmir assert(I != IDom->Children.end() && 632274955Ssvnmir "Not in immediate dominator children set!"); 633274955Ssvnmir // I am no longer your child... 634274955Ssvnmir IDom->Children.erase(I); 635274955Ssvnmir } 636274955Ssvnmir 637274955Ssvnmir DomTreeNodes.erase(BB); 638327952Sdim 639327952Sdim if (!IsPostDom) return; 640327952Sdim 641327952Sdim // Remember to update PostDominatorTree roots. 642327952Sdim auto RIt = llvm::find(Roots, BB); 643327952Sdim if (RIt != Roots.end()) { 644327952Sdim std::swap(*RIt, Roots.back()); 645327952Sdim Roots.pop_back(); 646327952Sdim } 647274955Ssvnmir } 648274955Ssvnmir 649274955Ssvnmir /// splitBlock - BB is split and now it has one successor. Update dominator 650274955Ssvnmir /// tree to reflect this change. 651280031Sdim void splitBlock(NodeT *NewBB) { 652321369Sdim if (IsPostDominator) 653321369Sdim Split<Inverse<NodeT *>>(NewBB); 654274955Ssvnmir else 655321369Sdim Split<NodeT *>(NewBB); 656274955Ssvnmir } 657274955Ssvnmir 658274955Ssvnmir /// print - Convert to human readable form 659274955Ssvnmir /// 660321369Sdim void print(raw_ostream &O) const { 661321369Sdim O << "=============================--------------------------------\n"; 662327952Sdim if (IsPostDominator) 663321369Sdim O << "Inorder PostDominator Tree: "; 664274955Ssvnmir else 665321369Sdim O << "Inorder Dominator Tree: "; 666321369Sdim if (!DFSInfoValid) 667321369Sdim O << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 668321369Sdim O << "\n"; 669274955Ssvnmir 670274955Ssvnmir // The postdom tree can have a null root if there are no returns. 671321369Sdim if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1); 672353358Sdim O << "Roots: "; 673353358Sdim for (const NodePtr Block : Roots) { 674353358Sdim Block->printAsOperand(O, false); 675353358Sdim O << " "; 676327952Sdim } 677353358Sdim O << "\n"; 678274955Ssvnmir } 679274955Ssvnmir 680288943Sdimpublic: 681274955Ssvnmir /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 682274955Ssvnmir /// dominator tree in dfs order. 683274955Ssvnmir void updateDFSNumbers() const { 684288943Sdim if (DFSInfoValid) { 685288943Sdim SlowQueries = 0; 686288943Sdim return; 687288943Sdim } 688288943Sdim 689280031Sdim SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, 690280031Sdim typename DomTreeNodeBase<NodeT>::const_iterator>, 691280031Sdim 32> WorkStack; 692274955Ssvnmir 693274955Ssvnmir const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); 694327952Sdim assert((!Parent || ThisRoot) && "Empty constructed DomTree"); 695274955Ssvnmir if (!ThisRoot) 696274955Ssvnmir return; 697274955Ssvnmir 698327952Sdim // Both dominators and postdominators have a single root node. In the case 699327952Sdim // case of PostDominatorTree, this node is a virtual root. 700327952Sdim WorkStack.push_back({ThisRoot, ThisRoot->begin()}); 701327952Sdim 702327952Sdim unsigned DFSNum = 0; 703274955Ssvnmir ThisRoot->DFSNumIn = DFSNum++; 704274955Ssvnmir 705274955Ssvnmir while (!WorkStack.empty()) { 706274955Ssvnmir const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 707327952Sdim const auto ChildIt = WorkStack.back().second; 708274955Ssvnmir 709274955Ssvnmir // If we visited all of the children of this node, "recurse" back up the 710274955Ssvnmir // stack setting the DFOutNum. 711274955Ssvnmir if (ChildIt == Node->end()) { 712274955Ssvnmir Node->DFSNumOut = DFSNum++; 713274955Ssvnmir WorkStack.pop_back(); 714274955Ssvnmir } else { 715274955Ssvnmir // Otherwise, recursively visit this child. 716274955Ssvnmir const DomTreeNodeBase<NodeT> *Child = *ChildIt; 717274955Ssvnmir ++WorkStack.back().second; 718274955Ssvnmir 719327952Sdim WorkStack.push_back({Child, Child->begin()}); 720274955Ssvnmir Child->DFSNumIn = DFSNum++; 721274955Ssvnmir } 722274955Ssvnmir } 723274955Ssvnmir 724274955Ssvnmir SlowQueries = 0; 725274955Ssvnmir DFSInfoValid = true; 726274955Ssvnmir } 727274955Ssvnmir 728274955Ssvnmir /// recalculate - compute a dominator tree for the given function 729327952Sdim void recalculate(ParentType &Func) { 730327952Sdim Parent = &Func; 731327952Sdim DomTreeBuilder::Calculate(*this); 732321369Sdim } 733321369Sdim 734344779Sdim void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) { 735344779Sdim Parent = &Func; 736344779Sdim DomTreeBuilder::CalculateWithUpdates(*this, Updates); 737344779Sdim } 738344779Sdim 739341825Sdim /// verify - checks if the tree is correct. There are 3 level of verification: 740341825Sdim /// - Full -- verifies if the tree is correct by making sure all the 741341825Sdim /// properties (including the parent and the sibling property) 742341825Sdim /// hold. 743341825Sdim /// Takes O(N^3) time. 744341825Sdim /// 745341825Sdim /// - Basic -- checks if the tree is correct, but compares it to a freshly 746341825Sdim /// constructed tree instead of checking the sibling property. 747341825Sdim /// Takes O(N^2) time. 748341825Sdim /// 749341825Sdim /// - Fast -- checks basic tree structure and compares it with a freshly 750341825Sdim /// constructed tree. 751341825Sdim /// Takes O(N^2) time worst case, but is faster in practise (same 752341825Sdim /// as tree construction). 753341825Sdim bool verify(VerificationLevel VL = VerificationLevel::Full) const { 754341825Sdim return DomTreeBuilder::Verify(*this, VL); 755341825Sdim } 756321369Sdim 757341825Sdimprotected: 758321369Sdim void addRoot(NodeT *BB) { this->Roots.push_back(BB); } 759321369Sdim 760321369Sdim void reset() { 761321369Sdim DomTreeNodes.clear(); 762321369Sdim Roots.clear(); 763321369Sdim RootNode = nullptr; 764321369Sdim Parent = nullptr; 765321369Sdim DFSInfoValid = false; 766321369Sdim SlowQueries = 0; 767321369Sdim } 768321369Sdim 769321369Sdim // NewBB is split and now it has one successor. Update dominator tree to 770321369Sdim // reflect this change. 771321369Sdim template <class N> 772321369Sdim void Split(typename GraphTraits<N>::NodeRef NewBB) { 773321369Sdim using GraphT = GraphTraits<N>; 774321369Sdim using NodeRef = typename GraphT::NodeRef; 775321369Sdim assert(std::distance(GraphT::child_begin(NewBB), 776321369Sdim GraphT::child_end(NewBB)) == 1 && 777321369Sdim "NewBB should have a single successor!"); 778321369Sdim NodeRef NewBBSucc = *GraphT::child_begin(NewBB); 779321369Sdim 780321369Sdim std::vector<NodeRef> PredBlocks; 781360784Sdim for (auto Pred : children<Inverse<N>>(NewBB)) 782321369Sdim PredBlocks.push_back(Pred); 783321369Sdim 784321369Sdim assert(!PredBlocks.empty() && "No predblocks?"); 785321369Sdim 786321369Sdim bool NewBBDominatesNewBBSucc = true; 787360784Sdim for (auto Pred : children<Inverse<N>>(NewBBSucc)) { 788321369Sdim if (Pred != NewBB && !dominates(NewBBSucc, Pred) && 789321369Sdim isReachableFromEntry(Pred)) { 790321369Sdim NewBBDominatesNewBBSucc = false; 791321369Sdim break; 792321369Sdim } 793274955Ssvnmir } 794321369Sdim 795321369Sdim // Find NewBB's immediate dominator and create new dominator tree node for 796321369Sdim // NewBB. 797321369Sdim NodeT *NewBBIDom = nullptr; 798321369Sdim unsigned i = 0; 799321369Sdim for (i = 0; i < PredBlocks.size(); ++i) 800321369Sdim if (isReachableFromEntry(PredBlocks[i])) { 801321369Sdim NewBBIDom = PredBlocks[i]; 802321369Sdim break; 803321369Sdim } 804321369Sdim 805321369Sdim // It's possible that none of the predecessors of NewBB are reachable; 806321369Sdim // in that case, NewBB itself is unreachable, so nothing needs to be 807321369Sdim // changed. 808321369Sdim if (!NewBBIDom) return; 809321369Sdim 810321369Sdim for (i = i + 1; i < PredBlocks.size(); ++i) { 811321369Sdim if (isReachableFromEntry(PredBlocks[i])) 812321369Sdim NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 813321369Sdim } 814321369Sdim 815321369Sdim // Create the new dominator tree node... and set the idom of NewBB. 816321369Sdim DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom); 817321369Sdim 818321369Sdim // If NewBB strictly dominates other blocks, then it is now the immediate 819321369Sdim // dominator of NewBBSucc. Update the dominator tree as appropriate. 820321369Sdim if (NewBBDominatesNewBBSucc) { 821321369Sdim DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc); 822321369Sdim changeImmediateDominator(NewBBSuccNode, NewBBNode); 823321369Sdim } 824274955Ssvnmir } 825321369Sdim 826321369Sdim private: 827321369Sdim bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 828321369Sdim const DomTreeNodeBase<NodeT> *B) const { 829321369Sdim assert(A != B); 830321369Sdim assert(isReachableFromEntry(B)); 831321369Sdim assert(isReachableFromEntry(A)); 832321369Sdim 833341825Sdim const unsigned ALevel = A->getLevel(); 834321369Sdim const DomTreeNodeBase<NodeT> *IDom; 835341825Sdim 836341825Sdim // Don't walk nodes above A's subtree. When we reach A's level, we must 837341825Sdim // either find A or be in some other subtree not dominated by A. 838341825Sdim while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) 839321369Sdim B = IDom; // Walk up the tree 840341825Sdim 841341825Sdim return B == A; 842321369Sdim } 843321369Sdim 844341825Sdim /// Wipe this tree's state without releasing any resources. 845321369Sdim /// 846321369Sdim /// This is essentially a post-move helper only. It leaves the object in an 847321369Sdim /// assignable and destroyable state, but otherwise invalid. 848321369Sdim void wipe() { 849321369Sdim DomTreeNodes.clear(); 850321369Sdim RootNode = nullptr; 851321369Sdim Parent = nullptr; 852321369Sdim } 853274955Ssvnmir}; 854274955Ssvnmir 855321369Sdimtemplate <typename T> 856321369Sdimusing DomTreeBase = DominatorTreeBase<T, false>; 857321369Sdim 858321369Sdimtemplate <typename T> 859321369Sdimusing PostDomTreeBase = DominatorTreeBase<T, true>; 860321369Sdim 861274955Ssvnmir// These two functions are declared out of line as a workaround for building 862274955Ssvnmir// with old (< r147295) versions of clang because of pr11642. 863321369Sdimtemplate <typename NodeT, bool IsPostDom> 864321369Sdimbool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A, 865321369Sdim const NodeT *B) const { 866274955Ssvnmir if (A == B) 867274955Ssvnmir return true; 868274955Ssvnmir 869274955Ssvnmir // Cast away the const qualifiers here. This is ok since 870274955Ssvnmir // this function doesn't actually return the values returned 871274955Ssvnmir // from getNode. 872274955Ssvnmir return dominates(getNode(const_cast<NodeT *>(A)), 873274955Ssvnmir getNode(const_cast<NodeT *>(B))); 874274955Ssvnmir} 875321369Sdimtemplate <typename NodeT, bool IsPostDom> 876321369Sdimbool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates( 877321369Sdim const NodeT *A, const NodeT *B) const { 878274955Ssvnmir if (A == B) 879274955Ssvnmir return false; 880274955Ssvnmir 881274955Ssvnmir // Cast away the const qualifiers here. This is ok since 882274955Ssvnmir // this function doesn't actually return the values returned 883274955Ssvnmir // from getNode. 884274955Ssvnmir return dominates(getNode(const_cast<NodeT *>(A)), 885274955Ssvnmir getNode(const_cast<NodeT *>(B))); 886274955Ssvnmir} 887274955Ssvnmir 888321369Sdim} // end namespace llvm 889274955Ssvnmir 890321369Sdim#endif // LLVM_SUPPORT_GENERICDOMTREE_H 891