llvm/Support/GenericDomTreeConstruction.h

176   TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
177     if (TreeNodePtr Node = DT.getNode(BB)) return Node;
183     assert(IDom || DT.DomTreeNodes[nullptr]);
184     TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
188     return (DT.DomTreeNodes[BB] = IDomNode->addChild(
304   void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
325         const TreeNodePtr TN = DT.getNode(N);
375   static NodePtr GetEntryNode(const DomTreeT &DT) {
376     assert(DT.Parent && "Parent not set");
377     return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
383   static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
384     assert(DT.Parent && "Parent pointer is not set");
389       Roots.push_back(GetEntryNode(DT));
409     for (const NodePtr N : nodes(DT.Parent)) {
441       for (const NodePtr I : nodes(DT.Parent)) {
491     if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
510   static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
550   void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
552       assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
553       runDFS(DT.Roots[0], 0, DC, 0);
559     for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
562   static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
563     auto *Parent = DT.Parent;
564     DT.reset();
565     DT.Parent = Parent;
571     DT.Roots = FindRoots(DT, nullptr);
572     SNCA.doFullDFSWalk(DT, AlwaysDescend);
574     SNCA.runSemiNCA(DT);
581     if (DT.Roots.empty()) return;
586     NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
588     DT.RootNode = (DT.DomTreeNodes[Root] =
591     SNCA.attachNewSubtree(DT, DT.RootNode);
594   void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
604       if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
609       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
613       DT.DomTreeNodes[W] = IDomNode->addChild(
618   void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
622       const TreeNodePtr TN = DT.getNode(N);
624       const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
649   static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
656     TreeNodePtr FromTN = DT.getNode(From);
663       TreeNodePtr VirtualRoot = DT.getNode(nullptr);
665           (DT.DomTreeNodes[From] = VirtualRoot->addChild(
668       DT.Roots.push_back(From);
671     DT.DFSInfoValid = false;
673     const TreeNodePtr ToTN = DT.getNode(To);
675       InsertUnreachable(DT, BUI, FromTN, To);
677       InsertReachable(DT, BUI, FromTN, ToTN);
682   static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
688     if (!DT.isVirtualRoot(To->getIDom())) return false;
690     auto RIt = llvm::find(DT.Roots, To->getBlock());
691     if (RIt == DT.Roots.end())
697     CalculateFromScratch(DT, BUI);
715   static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
719     if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
725     RootsT Roots = FindRoots(DT, BUI);
726     if (!isPermutation(DT.Roots, Roots)) {
736       CalculateFromScratch(DT, BUI);
741   static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
745     if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
746     // DT.findNCD expects both pointers to be valid. When From is a virtual
751             ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
753     assert(NCDBlock || DT.isPostDominator());
754     const TreeNodePtr NCD = DT.getNode(NCDBlock);
800           const TreeNodePtr SuccTN = DT.getNode(Succ);
844     UpdateInsertion(DT, BUI, NCD, II);
848   static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
864     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
868   static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
876     ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
888       InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
894       DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
898     assert(!DT.getNode(Root) && "Root must not be reachable");
901     auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
903       const TreeNodePtr ToTN = DT.getNode(To);
912     SNCA.runSemiNCA(DT);
913     SNCA.attachNewSubtree(DT, Incoming);
918   static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
936     const TreeNodePtr FromTN = DT.getNode(From);
940     const TreeNodePtr ToTN = DT.getNode(To);
948     const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
949     const TreeNodePtr NCD = DT.getNode(NCDBlock);
953       DT.DFSInfoValid = false;
961       if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
962         DeleteReachable(DT, BUI, FromTN, ToTN);
964         DeleteUnreachable(DT, BUI, ToTN);
967     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
971   static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
981         DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
982     assert(ToIDom || DT.isPostDominator());
983     const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
990       CalculateFromScratch(DT, BUI);
996     auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
997       return DT.getNode(To)->getLevel() > Level;
1006     SNCA.runSemiNCA(DT, Level);
1007     SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
1012   static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
1019       if (!DT.getNode(Pred)) continue;
1022           DT.findNearestCommonDominator(TN->getBlock(), Pred);
1037   static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
1051       DT.Roots.push_back(ToTN->getBlock());
1052       InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
1061     auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
1062       const TreeNodePtr TN = DT.getNode(To);
1080       const TreeNodePtr TN = DT.getNode(N);
1082           DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
1083       assert(NCDBlock || DT.isPostDominator());
1084       const TreeNodePtr NCD = DT.getNode(NCDBlock);
1096       CalculateFromScratch(DT, BUI);
1104       const TreeNodePtr TN = DT.getNode(N);
1107       EraseNode(DT, TN);
1121     auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
1122       const TreeNodePtr ToTN = DT.getNode(To);
1131     SNCA.runSemiNCA(DT, MinLevel);
1132     SNCA.reattachExistingSubtree(DT, PrevIDom);
1136   static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
1148     DT.DomTreeNodes.erase(TN->getBlock());
1155   static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
1165         DT.insertEdge(Update.getFrom(), Update.getTo());
1167         DT.deleteEdge(Update.getFrom(), Update.getTo());
1210     if (DT.DomTreeNodes.size() <= 100) {
1211       if (NumLegalized > DT.DomTreeNodes.size())
1212         CalculateFromScratch(DT, &BUI);
1213     } else if (NumLegalized > DT.DomTreeNodes.size() / 40)
1214       CalculateFromScratch(DT, &BUI);
1220       ApplyNextUpdate(DT, BUI);
1223   static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
1250       InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1252       DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1264   bool verifyRoots(const DomTreeT &DT) {
1265     if (!DT.Parent && !DT.Roots.empty()) {
1272       if (DT.Roots.empty()) {
1278       if (DT.getRoot() != GetEntryNode(DT)) {
1285     RootsT ComputedRoots = FindRoots(DT, nullptr);
1286     if (!isPermutation(DT.Roots, ComputedRoots)) {
1289       for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
1303   bool verifyReachability(const DomTreeT &DT) {
1305     doFullDFSWalk(DT, AlwaysDescend);
1307     for (auto &NodeToTN : DT.DomTreeNodes) {
1312       if (DT.isVirtualRoot(TN)) continue;
1324       if (N && !DT.getNode(N)) {
1339   static bool VerifyLevels(const DomTreeT &DT) {
1340     for (auto &NodeToTN : DT.DomTreeNodes) {
1371   static bool VerifyDFSNumbers(const DomTreeT &DT) {
1372     if (!DT.DFSInfoValid || !DT.Parent)
1375     const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
1376     const TreeNodePtr Root = DT.getNode(RootBB);
1395     for (const auto &NodeToTN : DT.DomTreeNodes) {
1507   bool verifyParentProperty(const DomTreeT &DT) {
1508     for (auto &NodeToTN : DT.DomTreeNodes) {
1516       doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
1540   bool verifySiblingProperty(const DomTreeT &DT) {
1541     for (auto &NodeToTN : DT.DomTreeNodes) {
1550         doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
1579   static bool IsSameAsFreshTree(const DomTreeT &DT) {
1581     FreshTree.recalculate(*DT.Parent);
1582     const bool Different = DT.compare(FreshTree);
1585       errs() << (DT.isPostDominator() ? "Post" : "")
1588       DT.print(errs());
1599 void Calculate(DomTreeT &DT) {
1600   SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
1604 void CalculateWithUpdates(DomTreeT &DT,
1619   SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, &BUI);
1623 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1625   if (DT.isPostDominator()) std::swap(From, To);
1626   SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
1630 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1632   if (DT.isPostDominator()) std::swap(From, To);
1633   SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
1637 void ApplyUpdates(DomTreeT &DT,
1639   SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
1643 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
1648   if (!SNCA.IsSameAsFreshTree(DT))
1652   if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1653       !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1659     if (!SNCA.verifyParentProperty(DT))
1662     if (!SNCA.verifySiblingProperty(DT))