37 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
38 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
50 #define DEBUG_TYPE "dom-tree-builder"
53 namespace DomTreeBuilder {
55 template <
typename DomTreeT>
57 using NodePtr =
typename DomTreeT::NodePtr;
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;
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;
219 WorkList.push_back(Succ);
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");
364 SNCA.addVirtualRoot();
396 bool HasNonTrivialRoots =
false;
399 if (
Total + 1 != Num) {
400 HasNonTrivialRoots =
true;
407 std::optional<NodeOrderMap> SuccOrder;
408 auto InitSuccOrderOnce = [&]() {
411 if (SNCA.NodeToInfo.count(
Node) == 0)
412 for (
const auto Succ : getChildren<false>(
Node, SNCA.BatchUpdates))
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;
435 if (SNCA.NodeToInfo.count(
I) == 0) {
454 const unsigned NewNum =
456 const NodePtr FurthestAway = SNCA.NumToNode[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) {
467 SNCA.NodeToInfo.erase(
N);
468 SNCA.NumToNode.pop_back();
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");
522 const unsigned Num = SNCA.runDFS<
true>(Root, 0,
AlwaysDescend, 0);
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);
595 SNCA.attachNewSubtree(DT, DT.RootNode);
606 if (DT.DomTreeNodes[
W])
continue;
615 DT.createChild(
W, IDomNode);
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);
909 SNCA.attachNewSubtree(DT, Incoming);
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);
1002 SNCA.runSemiNCA(DT, Level);
1003 SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
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;
1061 AffectedQueue.push_back(To);
1067 unsigned LastDFSNum =
1068 SNCA.runDFS(ToTN->
getBlock(), 0, DescendAndCollect, 0);
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;
1120 SNCA.runDFS(MinNode->
getBlock(), 0, DescendBelow, 0);
1126 SNCA.runSemiNCA(DT, MinLevel);
1127 SNCA.reattachExistingSubtree(DT, PrevIDom);
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) {
1164 InsertEdge(DT,
nullptr, Update.getFrom(), Update.getTo());
1166 DeleteEdge(DT,
nullptr, Update.getFrom(), Update.getTo());
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)
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) {
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());
1560 template <
class DomTreeT>
1565 template <
typename DomTreeT>
1576 template <
class DomTreeT>
1578 typename DomTreeT::NodePtr To) {
1583 template <
class DomTreeT>
1585 typename DomTreeT::NodePtr To) {
1590 template <
class DomTreeT>
1593 DomTreeT::IsPostDominator> &PreViewCFG,
1595 DomTreeT::IsPostDominator> *PostViewCFG) {
1599 template <
class DomTreeT>
1600 bool Verify(
const DomTreeT &DT,
typename DomTreeT::VerificationLevel VL) {
1605 if (!SNCA.IsSameAsFreshTree(DT))
1609 if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1610 !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1616 if (!SNCA.verifyParentProperty(DT))
1619 if (!SNCA.verifySiblingProperty(DT))