37#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
38#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
50#define DEBUG_TYPE "dom-tree-builder"
53namespace DomTreeBuilder {
55template <
typename DomTreeT>
57 using NodePtr =
typename DomTreeT::NodePtr;
58 using NodeT =
typename DomTreeT::NodeType;
60 using RootsT =
decltype(DomTreeT::Roots);
61 static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
79 using UpdateT =
typename DomTreeT::UpdateType;
108 template <
bool Inversed>
111 return BUI->
PreViewCFG.template getChildren<Inversed>(
N);
112 return getChildren<Inversed>(
N);
115 template <
bool Inversed>
117 using DirectedNodeT =
118 std::conditional_t<Inversed, Inverse<NodePtr>,
NodePtr>;
119 auto R = children<DirectedNodeT>(
N);
129 if (InfoIt ==
NodeToInfo.end())
return nullptr;
131 return InfoIt->second.IDom;
141 assert(IDom || DT.DomTreeNodes[
nullptr]);
146 return DT.createChild(BB, IDomNode);
161 BP.
N->printAsOperand(O,
false);
179 template <
bool IsReverse = false,
typename DescendCondition>
181 unsigned AttachToNum,
187 while (!WorkList.
empty()) {
192 if (BBInfo.DFSNum != 0)
continue;
193 BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
198 auto Successors = getChildren<Direction>(BB,
BatchUpdates);
199 if (SuccOrder && Successors.size() > 1)
202 return SuccOrder->find(A)->second < SuccOrder->find(B)->second;
205 for (
const NodePtr Succ : Successors) {
209 if (SIT !=
NodeToInfo.end() && SIT->second.DFSNum != 0) {
210 if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
214 if (!Condition(BB, Succ))
continue;
220 SuccInfo.Parent = LastNum;
221 SuccInfo.ReverseChildren.push_back(BB);
244 if (VInfo->
Parent < LastLinked)
250 Stack.push_back(VInfo);
252 }
while (VInfo->
Parent >= LastLinked);
259 VInfo = Stack.pop_back_val();
262 if (PLabelInfo->
Semi < VLabelInfo->
Semi)
265 PLabelInfo = VLabelInfo;
267 }
while (!Stack.empty());
273 const unsigned NextDFSNum(
NumToNode.size());
275 for (
unsigned i = 1; i < NextDFSNum; ++i) {
283 for (
unsigned i = NextDFSNum - 1; i >= 2; --i) {
288 WInfo.Semi = WInfo.Parent;
289 for (
const auto &
N : WInfo.ReverseChildren) {
295 if (TN && TN->
getLevel() < MinLevel)
299 if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
307 for (
unsigned i = 2; i < NextDFSNum; ++i) {
311 NodePtr WIDomCandidate = WInfo.IDom;
312 while (
NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
313 WIDomCandidate =
NodeToInfo[WIDomCandidate].IDom;
315 WInfo.IDom = WIDomCandidate;
326 assert(
NumToNode.size() == 1 &&
"SNCAInfo must be freshly constructed");
329 BBInfo.DFSNum = BBInfo.Semi = 1;
330 BBInfo.Label =
nullptr;
339 assert(
N &&
"N must be a valid node");
340 return !getChildren<false>(
N, BUI).empty();
344 assert(DT.Parent &&
"Parent not set");
352 assert(DT.Parent &&
"Parent pointer is not set");
396 bool HasNonTrivialRoots =
false;
399 if (
Total + 1 != Num) {
400 HasNonTrivialRoots =
true;
407 std::optional<NodeOrderMap> SuccOrder;
408 auto InitSuccOrderOnce = [&]() {
413 SuccOrder->try_emplace(Succ, 0);
416 unsigned NodeNum = 0;
417 for (
const auto Node :
nodes(DT.Parent)) {
419 auto Order = SuccOrder->find(
Node);
420 if (Order != SuccOrder->end()) {
421 assert(Order->second == 0);
422 Order->second = NodeNum;
454 const unsigned NewNum =
458 <<
"(non-trivial root): "
460 Roots.push_back(FurthestAway);
461 LLVM_DEBUG(
dbgs() <<
"\t\t\tPrev DFSNum: " << Num <<
", new DFSNum: "
462 << NewNum <<
"\n\t\t\tRemoving DFS info\n");
463 for (
unsigned i = NewNum; i > Num; --i) {
470 const unsigned PrevNum = Num;
473 for (
unsigned i = PrevNum + 1; i <= Num; ++i)
485 assert((
Total + 1 == Num) &&
"Everything should have been visited");
514 for (
unsigned i = 0; i < Roots.size(); ++i) {
515 auto &Root = Roots[i];
519 <<
" remains a root\n");
525 for (
unsigned x = 2; x <= Num; ++x) {
546 template <
typename DescendCondition>
549 assert(DT.Roots.size() == 1 &&
"Dominators should have a singe root");
550 runDFS(DT.Roots[0], 0, DC, 0);
556 for (
const NodePtr Root : DT.Roots) Num =
runDFS(Root, Num, DC, 0);
560 auto *Parent = DT.Parent;
584 dbgs() <<
"DomTree recalculated, skipping future batch updates\n");
587 if (DT.Roots.empty())
return;
594 DT.RootNode = DT.createNode(Root);
602 for (
size_t i = 1, e =
NumToNode.size(); i != e; ++i) {
606 if (DT.DomTreeNodes[W])
continue;
615 DT.createChild(W, IDomNode);
621 for (
size_t i = 1, e =
NumToNode.size(); i != e; ++i) {
634 return LHS->getLevel() <
RHS->getLevel();
640 std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,
645#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
653 "From has to be a valid CFG node or a virtual root");
654 assert(To &&
"Cannot be a nullptr");
665 FromTN = DT.createChild(
From, VirtualRoot);
666 DT.Roots.push_back(
From);
669 DT.DFSInfoValid =
false;
686 if (!DT.isVirtualRoot(To->
getIDom()))
return false;
692 <<
" is no longer a root\n\t\tRebuilding the tree!!!\n");
700 if (
A.size() !=
B.size())
717 return HasForwardSuccessors(N, BUI);
730 <<
"The entire tree needs to be rebuilt\n");
748 ? DT.findNearestCommonDominator(
From->getBlock(), To->
getBlock())
750 assert(NCDBlock || DT.isPostDominator());
755 const unsigned NCDLevel = NCD->
getLevel();
775 while (!II.
Bucket.empty()) {
780 const unsigned CurrentLevel = TN->
getLevel();
782 "as affected, CurrentLevel " << CurrentLevel <<
"\n");
795 for (
const NodePtr Succ : getChildren<IsPostDom>(TN->
getBlock(), BUI)) {
798 "Unreachable successor found at reachable insertion");
799 const unsigned SuccLevel = SuccTN->
getLevel();
802 <<
", level = " << SuccLevel <<
"\n");
811 if (SuccLevel <= NCDLevel + 1 || !II.
Visited.insert(SuccTN).second)
814 if (SuccLevel > CurrentLevel) {
819 UnaffectedOnCurrentLevel.
push_back(SuccTN);
821 II.VisitedUnaffected.push_back(SuccTN);
827 <<
" to a Bucket\n");
832 if (UnaffectedOnCurrentLevel.
empty())
854#if defined(LLVM_ENABLE_ABI_BREAKING_CHECKS) && !defined(NDEBUG)
857 "TN should have been updated by an affected ancestor");
880 for (
const auto &Edge : DiscoveredEdgesToReachable) {
893 &DiscoveredConnectingEdges) {
894 assert(!DT.getNode(Root) &&
"Root must not be reachable");
897 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](
NodePtr From,
900 if (!ToTN)
return true;
902 DiscoveredConnectingEdges.push_back({
From, ToTN});
907 SNCA.
runDFS(Root, 0, UnreachableDescender, 0);
916 assert(
From && To &&
"Cannot disconnect nullptrs");
920#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
924 auto IsSuccessor = [BUI](
const NodePtr SuccCandidate,
const NodePtr Of) {
925 auto Successors = getChildren<IsPostDom>(Of, BUI);
929 assert(!IsSuccessor(To,
From) &&
"Deleted edge still exists in the CFG!");
940 <<
") already unreachable -- there is no edge to delete\n");
944 const NodePtr NCDBlock = DT.findNearestCommonDominator(
From, To);
949 DT.DFSInfoValid =
false;
978 assert(ToIDom || DT.isPostDominator());
984 if (!PrevIDomSubTree) {
991 const unsigned Level = ToIDomTN->
getLevel();
993 return DT.getNode(To)->getLevel() > Level;
1000 SNCA.
runDFS(ToIDom, 0, DescendBelow, 0);
1013 for (
const NodePtr Pred : getChildren<!IsPostDom>(TNB, BUI)) {
1015 if (!DT.getNode(Pred))
continue;
1017 const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);
1019 if (Support != TNB) {
1021 <<
" is reachable from support "
1043 LLVM_DEBUG(
dbgs() <<
"\tDeletion made a region reverse-unreachable\n");
1046 DT.Roots.push_back(ToTN->
getBlock());
1052 const unsigned Level = ToTN->
getLevel();
1056 auto DescendAndCollect = [Level, &AffectedQueue, &DT](
NodePtr,
NodePtr To) {
1059 if (TN->
getLevel() > Level)
return true;
1067 unsigned LastDFSNum =
1074 for (
const NodePtr N : AffectedQueue) {
1078 assert(NCDBlock || DT.isPostDominator());
1097 for (
unsigned i = LastDFSNum; i > 0; --i) {
1106 if (MinNode == ToTN)
return;
1108 LLVM_DEBUG(
dbgs() <<
"DeleteUnreachable: running DFS with MinNode = "
1110 const unsigned MinLevel = MinNode->
getLevel();
1118 return ToTN && ToTN->
getLevel() > MinLevel;
1139 assert(ChIt != IDom->Children.end());
1140 std::swap(*ChIt, IDom->Children.back());
1141 IDom->Children.pop_back();
1143 DT.DomTreeNodes.erase(TN->
getBlock());
1155 if (NumUpdates == 0)
1160 if (NumUpdates == 1) {
1163 if (Update.getKind() == UpdateKind::Insert)
1164 InsertEdge(DT,
nullptr, Update.getFrom(), Update.getTo());
1166 DeleteEdge(DT,
nullptr, Update.getFrom(), Update.getTo());
1169 if (Update.getKind() == UpdateKind::Insert)
1170 InsertEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1172 DeleteEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1186 if (DT.DomTreeNodes.size() <= 100) {
1189 }
else if (BUI.
NumLegalized > DT.DomTreeNodes.size() / 40)
1210 if (CurrentUpdate.getKind() == UpdateKind::Insert)
1211 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1213 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1226 if (!DT.Parent && !DT.Roots.empty()) {
1227 errs() <<
"Tree has no parent but has roots!\n";
1233 if (DT.Roots.empty()) {
1234 errs() <<
"Tree doesn't have a root!\n";
1240 errs() <<
"Tree's root is not its parent's entry node!\n";
1248 errs() <<
"Tree has different roots than freshly computed ones!\n";
1249 errs() <<
"\tPDT roots: ";
1251 errs() <<
"\n\tComputed roots: ";
1252 for (
const NodePtr N : ComputedRoots)
1268 for (
auto &NodeToTN : DT.DomTreeNodes) {
1273 if (DT.isVirtualRoot(TN))
continue;
1277 <<
" not found by DFS walk!\n";
1285 if (
N && !DT.getNode(
N)) {
1287 <<
" not found in the DomTree!\n";
1301 for (
auto &NodeToTN : DT.DomTreeNodes) {
1307 if (!IDom && TN->
getLevel() != 0) {
1309 <<
" has a nonzero level " << TN->
getLevel() <<
"!\n";
1317 << TN->
getLevel() <<
" while its IDom "
1333 if (!DT.DFSInfoValid || !DT.Parent)
1339 auto PrintNodeAndDFSNums = [](
const TreeNodePtr TN) {
1341 << TN->getDFSNumOut() <<
'}';
1347 errs() <<
"DFSIn number for the tree root is not:\n\t";
1348 PrintNodeAndDFSNums(Root);
1356 for (
const auto &NodeToTN : DT.DomTreeNodes) {
1360 if (
Node->isLeaf()) {
1361 if (
Node->getDFSNumIn() + 1 !=
Node->getDFSNumOut()) {
1362 errs() <<
"Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1363 PrintNodeAndDFSNums(
Node);
1379 auto PrintChildrenError = [
Node, &Children, PrintNodeAndDFSNums](
1383 errs() <<
"Incorrect DFS numbers for:\n\tParent ";
1384 PrintNodeAndDFSNums(
Node);
1386 errs() <<
"\n\tChild ";
1387 PrintNodeAndDFSNums(FirstCh);
1390 errs() <<
"\n\tSecond child ";
1391 PrintNodeAndDFSNums(SecondCh);
1394 errs() <<
"\nAll children: ";
1396 PrintNodeAndDFSNums(Ch);
1404 if (Children.front()->getDFSNumIn() !=
Node->getDFSNumIn() + 1) {
1405 PrintChildrenError(Children.front(),
nullptr);
1409 if (Children.back()->getDFSNumOut() + 1 !=
Node->getDFSNumOut()) {
1410 PrintChildrenError(Children.back(),
nullptr);
1414 for (
size_t i = 0, e = Children.size() - 1; i != e; ++i) {
1415 if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
1416 PrintChildrenError(Children[i], Children[i + 1]);
1469 for (
auto &NodeToTN : DT.DomTreeNodes) {
1479 return From != BB && To != BB;
1483 if (
NodeToInfo.count(Child->getBlock()) != 0) {
1486 <<
" is removed!\n";
1503 for (
auto &NodeToTN : DT.DomTreeNodes) {
1513 return From != BBN && To != BBN;
1517 if (S ==
N)
continue;
1522 <<
" is removed!\n";
1543 FreshTree.recalculate(*DT.Parent);
1544 const bool Different = DT.compare(FreshTree);
1547 errs() << (DT.isPostDominator() ?
"Post" :
"")
1548 <<
"DominatorTree is different than a freshly computed one!\n"
1551 errs() <<
"\n\tFreshly computed tree:\n";
1552 FreshTree.print(
errs());
1560template <
class DomTreeT>
1565template <
typename DomTreeT>
1576template <
class DomTreeT>
1578 typename DomTreeT::NodePtr To) {
1583template <
class DomTreeT>
1585 typename DomTreeT::NodePtr To) {
1590template <
class DomTreeT>
1593 DomTreeT::IsPostDominator> &PreViewCFG,
1595 DomTreeT::IsPostDominator> *PostViewCFG) {
1599template <
class DomTreeT>
1600bool Verify(
const DomTreeT &DT,
typename DomTreeT::VerificationLevel VL) {
1614 if (VL == DomTreeT::VerificationLevel::Basic ||
1615 VL == DomTreeT::VerificationLevel::Full)
1618 if (VL == DomTreeT::VerificationLevel::Full)
Unify divergent function exit nodes
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
Loop::LoopBounds::Direction Direction
ppc ctr loops PowerPC CTR Loops Verify
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Base class for the actual dominator tree node.
iterator_range< iterator > children()
void setIDom(DomTreeNodeBase *NewIDom)
DomTreeNodeBase * getIDom() const
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
size_t getNumChildren() const
unsigned getLevel() const
cfg::Update< NodePtr > popUpdateForIncrementalUpdates()
unsigned getNumLegalizedUpdates() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This class implements an extremely fast bulk output stream that can only output to a stream.
void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
void Calculate(DomTreeT &DT)
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.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
BatchUpdateInfo(GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG=nullptr)
const size_t NumLegalized
friend raw_ostream & operator<<(raw_ostream &O, const BlockNamePrinter &BP)
BlockNamePrinter(NodePtr Block)
BlockNamePrinter(TreeNodePtr TN)
SmallVector< NodePtr, 2 > ReverseChildren
bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const
std::priority_queue< TreeNodePtr, SmallVector< TreeNodePtr, 8 >, Compare > Bucket
SmallVector< TreeNodePtr, 8 > Affected
SmallDenseSet< TreeNodePtr, 8 > Visited
NodePtr getIDom(NodePtr BB) const
SemiNCAInfo(BatchUpdatePtr BUI)
static SmallVector< NodePtr, 8 > getChildren(NodePtr N)
static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr NCD, InsertionInfo &II)
static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC)
DenseMap< NodePtr, unsigned > NodeOrderMap
static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI)
static SmallVector< NodePtr, 8 > getChildren(NodePtr N, BatchUpdatePtr BUI)
static void ComputeUnreachableDominators(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, const TreeNodePtr Incoming, SmallVectorImpl< std::pair< NodePtr, TreeNodePtr > > &DiscoveredConnectingEdges)
static bool VerifyLevels(const DomTreeT &DT)
decltype(DomTreeT::Roots) RootsT
bool verifyReachability(const DomTreeT &DT)
static bool IsSameAsFreshTree(const DomTreeT &DT)
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN)
static constexpr bool IsPostDom
typename DomTreeT::NodePtr NodePtr
static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG)
void runSemiNCA(DomTreeT &DT, const unsigned MinLevel=0)
typename DomTreeT::UpdateKind UpdateKind
static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
bool verifySiblingProperty(const DomTreeT &DT)
typename DomTreeT::NodeType NodeT
void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
static NodePtr GetEntryNode(const DomTreeT &DT)
static bool AlwaysDescend(NodePtr, NodePtr)
static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI)
unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum, const NodeOrderMap *SuccOrder=nullptr)
static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr FromTN, const TreeNodePtr ToTN)
static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, RootsT &Roots)
static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN)
static bool isPermutation(const SmallVectorImpl< NodePtr > &A, const SmallVectorImpl< NodePtr > &B)
static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI)
std::vector< NodePtr > NumToNode
TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT)
typename DomTreeT::UpdateType UpdateT
static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI)
static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const NodePtr To)
static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI)
DenseMap< NodePtr, InfoRec > NodeToInfo
static bool VerifyDFSNumbers(const DomTreeT &DT)
static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr ToTN)
void attachNewSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
NodePtr eval(NodePtr V, unsigned LastLinked, SmallVectorImpl< InfoRec * > &Stack)
static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
BatchUpdateInfo * BatchUpdates
bool verifyParentProperty(const DomTreeT &DT)
bool verifyRoots(const DomTreeT &DT)