37 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
38 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
49 #define DEBUG_TYPE "dom-tree-builder"
52 namespace DomTreeBuilder {
54 template <
typename DomTreeT>
56 using NodePtr =
typename DomTreeT::NodePtr;
59 using RootsT = decltype(DomTreeT::Roots);
60 static constexpr
bool IsPostDom = DomTreeT::IsPostDominator;
78 using UpdateT =
typename DomTreeT::UpdateType;
107 template <
bool Inversed>
110 return BUI->
PreViewCFG.template getChildren<Inversed>(
N);
111 return getChildren<Inversed>(
N);
114 template <
bool Inversed>
116 using DirectedNodeT =
117 std::conditional_t<Inversed, Inverse<NodePtr>,
NodePtr>;
118 auto R = children<DirectedNodeT>(
N);
128 if (InfoIt ==
NodeToInfo.end())
return nullptr;
130 return InfoIt->second.IDom;
140 assert(IDom || DT.DomTreeNodes[
nullptr]);
145 return DT.createChild(
BB, IDomNode);
160 BP.
N->printAsOperand(
O,
false);
178 template <
bool IsReverse = false,
typename DescendCondition>
180 unsigned AttachToNum,
186 while (!WorkList.empty()) {
191 if (BBInfo.DFSNum != 0)
continue;
192 BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
198 if (SuccOrder && Successors.size() > 1)
201 return SuccOrder->find(A)->second < SuccOrder->find(B)->second;
204 for (
const NodePtr Succ : Successors) {
208 if (SIT !=
NodeToInfo.end() && SIT->second.DFSNum != 0) {
209 if (Succ !=
BB) SIT->second.ReverseChildren.push_back(
BB);
213 if (!Condition(
BB, Succ))
continue;
218 WorkList.push_back(Succ);
219 SuccInfo.Parent = LastNum;
220 SuccInfo.ReverseChildren.push_back(
BB);
243 if (VInfo->
Parent < LastLinked)
249 Stack.push_back(VInfo);
251 }
while (VInfo->
Parent >= LastLinked);
258 VInfo = Stack.pop_back_val();
261 if (PLabelInfo->
Semi < VLabelInfo->
Semi)
264 PLabelInfo = VLabelInfo;
266 }
while (!Stack.empty());
272 const unsigned NextDFSNum(
NumToNode.size());
274 for (
unsigned i = 1;
i < NextDFSNum; ++
i) {
282 for (
unsigned i = NextDFSNum - 1;
i >= 2; --
i) {
287 WInfo.Semi = WInfo.Parent;
288 for (
const auto &
N : WInfo.ReverseChildren) {
294 if (TN && TN->
getLevel() < MinLevel)
298 if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
306 for (
unsigned i = 2;
i < NextDFSNum; ++
i) {
310 NodePtr WIDomCandidate = WInfo.IDom;
311 while (
NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
312 WIDomCandidate =
NodeToInfo[WIDomCandidate].IDom;
314 WInfo.IDom = WIDomCandidate;
325 assert(
NumToNode.size() == 1 &&
"SNCAInfo must be freshly constructed");
328 BBInfo.DFSNum = BBInfo.Semi = 1;
329 BBInfo.Label =
nullptr;
338 assert(
N &&
"N must be a valid node");
339 return !getChildren<false>(
N, BUI).empty();
343 assert(DT.Parent &&
"Parent not set");
351 assert(DT.Parent &&
"Parent pointer is not set");
363 SNCA.addVirtualRoot();
395 bool HasNonTrivialRoots =
false;
398 if (Total + 1 != Num) {
399 HasNonTrivialRoots =
true;
407 auto InitSuccOrderOnce = [&]() {
410 if (SNCA.NodeToInfo.count(
Node) == 0)
411 for (
const auto Succ : getChildren<false>(
Node, SNCA.BatchUpdates))
415 unsigned NodeNum = 0;
416 for (
const auto Node :
nodes(DT.Parent)) {
419 if (Order != SuccOrder->
end()) {
420 assert(Order->second == 0);
421 Order->second = NodeNum;
434 if (SNCA.NodeToInfo.count(
I) == 0) {
453 const unsigned NewNum =
455 const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
457 <<
"(non-trivial root): "
459 Roots.push_back(FurthestAway);
460 LLVM_DEBUG(
dbgs() <<
"\t\t\tPrev DFSNum: " << Num <<
", new DFSNum: "
461 << NewNum <<
"\n\t\t\tRemoving DFS info\n");
462 for (
unsigned i = NewNum;
i > Num; --
i) {
466 SNCA.NodeToInfo.erase(
N);
467 SNCA.NumToNode.pop_back();
469 const unsigned PrevNum = Num;
472 for (
unsigned i = PrevNum + 1;
i <= Num; ++
i)
479 LLVM_DEBUG(
dbgs() <<
"Total: " << Total <<
", Num: " << Num <<
"\n");
484 assert((Total + 1 == Num) &&
"Everything should have been visited");
513 for (
unsigned i = 0;
i < Roots.size(); ++
i) {
514 auto &Root = Roots[
i];
518 <<
" remains a root\n");
521 const unsigned Num = SNCA.runDFS<
true>(Root, 0,
AlwaysDescend, 0);
524 for (
unsigned x = 2;
x <= Num; ++
x) {
545 template <
typename DescendCondition>
548 assert(DT.Roots.size() == 1 &&
"Dominators should have a singe root");
559 auto *Parent = DT.Parent;
583 dbgs() <<
"DomTree recalculated, skipping future batch updates\n");
586 if (DT.Roots.empty())
return;
593 DT.RootNode = DT.createNode(Root);
594 SNCA.attachNewSubtree(DT, DT.RootNode);
605 if (DT.DomTreeNodes[
W])
continue;
614 DT.createChild(
W, IDomNode);
633 return LHS->getLevel() <
RHS->getLevel();
639 std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,
644 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
652 "From has to be a valid CFG node or a virtual root");
653 assert(To &&
"Cannot be a nullptr");
664 FromTN = DT.createChild(
From, VirtualRoot);
665 DT.Roots.push_back(
From);
668 DT.DFSInfoValid =
false;
685 if (!DT.isVirtualRoot(To->
getIDom()))
return false;
691 <<
" is no longer a root\n\t\tRebuilding the tree!!!\n");
699 if (A.size() !=
B.size())
716 return HasForwardSuccessors(N, BUI);
729 <<
"The entire tree needs to be rebuilt\n");
747 ? DT.findNearestCommonDominator(
From->getBlock(), To->
getBlock())
749 assert(NCDBlock || DT.isPostDominator());
754 const unsigned NCDLevel = NCD->
getLevel();
774 while (!II.
Bucket.empty()) {
779 const unsigned CurrentLevel = TN->
getLevel();
781 "as affected, CurrentLevel " << CurrentLevel <<
"\n");
794 for (
const NodePtr Succ : getChildren<IsPostDom>(TN->
getBlock(), BUI)) {
797 "Unreachable successor found at reachable insertion");
798 const unsigned SuccLevel = SuccTN->
getLevel();
801 <<
", level = " << SuccLevel <<
"\n");
810 if (SuccLevel <= NCDLevel + 1 || !II.
Visited.insert(SuccTN).second)
813 if (SuccLevel > CurrentLevel) {
818 UnaffectedOnCurrentLevel.push_back(SuccTN);
820 II.VisitedUnaffected.push_back(SuccTN);
826 <<
" to a Bucket\n");
831 if (UnaffectedOnCurrentLevel.empty())
853 #if defined(LLVM_ENABLE_ABI_BREAKING_CHECKS) && !defined(NDEBUG)
856 "TN should have been updated by an affected ancestor");
879 for (
const auto &Edge : DiscoveredEdgesToReachable) {
892 &DiscoveredConnectingEdges) {
893 assert(!DT.getNode(Root) &&
"Root must not be reachable");
896 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](
NodePtr From,
899 if (!ToTN)
return true;
901 DiscoveredConnectingEdges.push_back({
From, ToTN});
906 SNCA.runDFS(Root, 0, UnreachableDescender, 0);
908 SNCA.attachNewSubtree(DT, Incoming);
915 assert(
From && To &&
"Cannot disconnect nullptrs");
919 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
923 auto IsSuccessor = [BUI](
const NodePtr SuccCandidate,
const NodePtr Of) {
924 auto Successors = getChildren<IsPostDom>(Of, BUI);
928 assert(!IsSuccessor(To,
From) &&
"Deleted edge still exists in the CFG!");
939 <<
") already unreachable -- there is no edge to delete\n");
943 const NodePtr NCDBlock = DT.findNearestCommonDominator(
From, To);
948 DT.DFSInfoValid =
false;
977 assert(ToIDom || DT.isPostDominator());
983 if (!PrevIDomSubTree) {
992 return DT.getNode(To)->getLevel() >
Level;
999 SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
1001 SNCA.runSemiNCA(DT,
Level);
1002 SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
1012 for (
const NodePtr Pred : getChildren<!IsPostDom>(TNB, BUI)) {
1014 if (!DT.getNode(Pred))
continue;
1016 const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);
1018 if (Support != TNB) {
1020 <<
" is reachable from support "
1042 LLVM_DEBUG(
dbgs() <<
"\tDeletion made a region reverse-unreachable\n");
1045 DT.Roots.push_back(ToTN->
getBlock());
1060 AffectedQueue.push_back(To);
1066 unsigned LastDFSNum =
1067 SNCA.runDFS(ToTN->
getBlock(), 0, DescendAndCollect, 0);
1073 for (
const NodePtr N : AffectedQueue) {
1077 assert(NCDBlock || DT.isPostDominator());
1096 for (
unsigned i = LastDFSNum;
i > 0; --
i) {
1105 if (MinNode == ToTN)
return;
1107 LLVM_DEBUG(
dbgs() <<
"DeleteUnreachable: running DFS with MinNode = "
1109 const unsigned MinLevel = MinNode->
getLevel();
1117 return ToTN && ToTN->
getLevel() > MinLevel;
1119 SNCA.runDFS(MinNode->
getBlock(), 0, DescendBelow, 0);
1125 SNCA.runSemiNCA(DT, MinLevel);
1126 SNCA.reattachExistingSubtree(DT, PrevIDom);
1138 assert(ChIt != IDom->Children.end());
1139 std::swap(*ChIt, IDom->Children.back());
1140 IDom->Children.pop_back();
1142 DT.DomTreeNodes.erase(TN->
getBlock());
1154 if (NumUpdates == 0)
1159 if (NumUpdates == 1) {
1163 InsertEdge(DT,
nullptr, Update.getFrom(), Update.getTo());
1165 DeleteEdge(DT,
nullptr, Update.getFrom(), Update.getTo());
1169 InsertEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1171 DeleteEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1185 if (DT.DomTreeNodes.size() <= 100) {
1188 }
else if (BUI.
NumLegalized > DT.DomTreeNodes.size() / 40)
1210 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1212 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1225 if (!DT.Parent && !DT.Roots.empty()) {
1226 errs() <<
"Tree has no parent but has roots!\n";
1232 if (DT.Roots.empty()) {
1233 errs() <<
"Tree doesn't have a root!\n";
1239 errs() <<
"Tree's root is not its parent's entry node!\n";
1247 errs() <<
"Tree has different roots than freshly computed ones!\n";
1248 errs() <<
"\tPDT roots: ";
1250 errs() <<
"\n\tComputed roots: ";
1251 for (
const NodePtr N : ComputedRoots)
1267 for (
auto &NodeToTN : DT.DomTreeNodes) {
1272 if (DT.isVirtualRoot(TN))
continue;
1276 <<
" not found by DFS walk!\n";
1284 if (
N && !DT.getNode(
N)) {
1286 <<
" not found in the DomTree!\n";
1300 for (
auto &NodeToTN : DT.DomTreeNodes) {
1306 if (!IDom && TN->
getLevel() != 0) {
1308 <<
" has a nonzero level " << TN->
getLevel() <<
"!\n";
1316 << TN->
getLevel() <<
" while its IDom "
1332 if (!DT.DFSInfoValid || !DT.Parent)
1338 auto PrintNodeAndDFSNums = [](
const TreeNodePtr TN) {
1340 << TN->getDFSNumOut() <<
'}';
1346 errs() <<
"DFSIn number for the tree root is not:\n\t";
1347 PrintNodeAndDFSNums(Root);
1355 for (
const auto &NodeToTN : DT.DomTreeNodes) {
1359 if (
Node->isLeaf()) {
1360 if (
Node->getDFSNumIn() + 1 !=
Node->getDFSNumOut()) {
1361 errs() <<
"Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1362 PrintNodeAndDFSNums(
Node);
1378 auto PrintChildrenError = [
Node, &Children, PrintNodeAndDFSNums](
1382 errs() <<
"Incorrect DFS numbers for:\n\tParent ";
1383 PrintNodeAndDFSNums(
Node);
1385 errs() <<
"\n\tChild ";
1386 PrintNodeAndDFSNums(FirstCh);
1389 errs() <<
"\n\tSecond child ";
1390 PrintNodeAndDFSNums(SecondCh);
1393 errs() <<
"\nAll children: ";
1395 PrintNodeAndDFSNums(Ch);
1403 if (Children.front()->getDFSNumIn() !=
Node->getDFSNumIn() + 1) {
1404 PrintChildrenError(Children.front(),
nullptr);
1408 if (Children.back()->getDFSNumOut() + 1 !=
Node->getDFSNumOut()) {
1409 PrintChildrenError(Children.back(),
nullptr);
1413 for (
size_t i = 0,
e = Children.size() - 1;
i !=
e; ++
i) {
1414 if (Children[
i]->getDFSNumOut() + 1 != Children[
i + 1]->getDFSNumIn()) {
1415 PrintChildrenError(Children[
i], Children[
i + 1]);
1468 for (
auto &NodeToTN : DT.DomTreeNodes) {
1482 if (
NodeToInfo.count(Child->getBlock()) != 0) {
1485 <<
" is removed!\n";
1502 for (
auto &NodeToTN : DT.DomTreeNodes) {
1512 return From != BBN && To != BBN;
1516 if (
S ==
N)
continue;
1521 <<
" is removed!\n";
1542 FreshTree.recalculate(*DT.Parent);
1543 const bool Different = DT.compare(FreshTree);
1546 errs() << (DT.isPostDominator() ?
"Post" :
"")
1547 <<
"DominatorTree is different than a freshly computed one!\n"
1550 errs() <<
"\n\tFreshly computed tree:\n";
1551 FreshTree.print(
errs());
1559 template <
class DomTreeT>
1564 template <
typename DomTreeT>
1575 template <
class DomTreeT>
1577 typename DomTreeT::NodePtr To) {
1582 template <
class DomTreeT>
1584 typename DomTreeT::NodePtr To) {
1589 template <
class DomTreeT>
1592 DomTreeT::IsPostDominator> &PreViewCFG,
1594 DomTreeT::IsPostDominator> *PostViewCFG) {
1598 template <
class DomTreeT>
1599 bool Verify(
const DomTreeT &DT,
typename DomTreeT::VerificationLevel VL) {
1604 if (!SNCA.IsSameAsFreshTree(DT))
1608 if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1609 !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1615 if (!SNCA.verifyParentProperty(DT))
1618 if (!SNCA.verifySiblingProperty(DT))