diff options
Diffstat (limited to 'contrib/llvm/include/llvm/Support/GenericDomTreeConstruction.h')
| -rw-r--r-- | contrib/llvm/include/llvm/Support/GenericDomTreeConstruction.h | 333 |
1 files changed, 172 insertions, 161 deletions
diff --git a/contrib/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/contrib/llvm/include/llvm/Support/GenericDomTreeConstruction.h index 971e8305a112..ccceba881718 100644 --- a/contrib/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/contrib/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -1,9 +1,8 @@ //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// \file @@ -16,9 +15,12 @@ /// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23: /// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf /// -/// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns -/// out that the theoretically slower O(n*log(n)) implementation is actually -/// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs. +/// Semi-NCA algorithm runs in O(n^2) worst-case time but usually slightly +/// faster than Simple Lengauer-Tarjan in practice. +/// +/// O(n^2) worst cases happen when the computation of nearest common ancestors +/// requires O(n) average time, which is very unlikely in real world. If this +/// ever turns out to be an issue, consider implementing a hybrid algorithm. /// /// The file uses the Depth Based Search algorithm to perform incremental /// updates (insertion and deletions). The implemented algorithm is based on @@ -255,42 +257,47 @@ struct SemiNCAInfo { return LastNum; } - NodePtr eval(NodePtr VIn, unsigned LastLinked) { - auto &VInInfo = NodeToInfo[VIn]; - if (VInInfo.DFSNum < LastLinked) - return VIn; - - SmallVector<NodePtr, 32> Work; - SmallPtrSet<NodePtr, 32> Visited; - - if (VInInfo.Parent >= LastLinked) - Work.push_back(VIn); - - while (!Work.empty()) { - NodePtr V = Work.back(); - auto &VInfo = NodeToInfo[V]; - NodePtr VAncestor = NumToNode[VInfo.Parent]; - - // Process Ancestor first - if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) { - Work.push_back(VAncestor); - continue; - } - Work.pop_back(); - - // Update VInfo based on Ancestor info - if (VInfo.Parent < LastLinked) - continue; - - auto &VAInfo = NodeToInfo[VAncestor]; - NodePtr VAncestorLabel = VAInfo.Label; - NodePtr VLabel = VInfo.Label; - if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi) - VInfo.Label = VAncestorLabel; - VInfo.Parent = VAInfo.Parent; - } - - return VInInfo.Label; + // V is a predecessor of W. eval() returns V if V < W, otherwise the minimum + // of sdom(U), where U > W and there is a virtual forest path from U to V. The + // virtual forest consists of linked edges of processed vertices. + // + // We can follow Parent pointers (virtual forest edges) to determine the + // ancestor U with minimum sdom(U). But it is slow and thus we employ the path + // compression technique to speed up to O(m*log(n)). Theoretically the virtual + // forest can be organized as balanced trees to achieve almost linear + // O(m*alpha(m,n)) running time. But it requires two auxiliary arrays (Size + // and Child) and is unlikely to be faster than the simple implementation. + // + // For each vertex V, its Label points to the vertex with the minimal sdom(U) + // (Semi) in its path from V (included) to NodeToInfo[V].Parent (excluded). + NodePtr eval(NodePtr V, unsigned LastLinked, + SmallVectorImpl<InfoRec *> &Stack) { + InfoRec *VInfo = &NodeToInfo[V]; + if (VInfo->Parent < LastLinked) + return VInfo->Label; + + // Store ancestors except the last (root of a virtual tree) into a stack. + assert(Stack.empty()); + do { + Stack.push_back(VInfo); + VInfo = &NodeToInfo[NumToNode[VInfo->Parent]]; + } while (VInfo->Parent >= LastLinked); + + // Path compression. Point each vertex's Parent to the root and update its + // Label if any of its ancestors (PInfo->Label) has a smaller Semi. + const InfoRec *PInfo = VInfo; + const InfoRec *PLabelInfo = &NodeToInfo[PInfo->Label]; + do { + VInfo = Stack.pop_back_val(); + VInfo->Parent = PInfo->Parent; + const InfoRec *VLabelInfo = &NodeToInfo[VInfo->Label]; + if (PLabelInfo->Semi < VLabelInfo->Semi) + VInfo->Label = PInfo->Label; + else + PLabelInfo = VLabelInfo; + PInfo = VInfo; + } while (!Stack.empty()); + return VInfo->Label; } // This function requires DFS to be run before calling it. @@ -304,6 +311,7 @@ struct SemiNCAInfo { } // Step #1: Calculate the semidominators of all vertices. + SmallVector<InfoRec *, 32> EvalStack; for (unsigned i = NextDFSNum - 1; i >= 2; --i) { NodePtr W = NumToNode[i]; auto &WInfo = NodeToInfo[W]; @@ -319,7 +327,7 @@ struct SemiNCAInfo { if (TN && TN->getLevel() < MinLevel) continue; - unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi; + unsigned SemiU = NodeToInfo[eval(N, i + 1, EvalStack)].Semi; if (SemiU < WInfo.Semi) WInfo.Semi = SemiU; } } @@ -620,21 +628,22 @@ struct SemiNCAInfo { // Helper struct used during edge insertions. struct InsertionInfo { - using BucketElementTy = std::pair<unsigned, TreeNodePtr>; - struct DecreasingLevel { - bool operator()(const BucketElementTy &First, - const BucketElementTy &Second) const { - return First.first > Second.first; + struct Compare { + bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const { + return LHS->getLevel() < RHS->getLevel(); } }; - std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>, - DecreasingLevel> - Bucket; // Queue of tree nodes sorted by level in descending order. - SmallDenseSet<TreeNodePtr, 8> Affected; - SmallDenseMap<TreeNodePtr, unsigned, 8> Visited; - SmallVector<TreeNodePtr, 8> AffectedQueue; - SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue; + // Bucket queue of tree nodes ordered by descending level. For simplicity, + // we use a priority_queue here. + std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>, + Compare> + Bucket; + SmallDenseSet<TreeNodePtr, 8> Visited; + SmallVector<TreeNodePtr, 8> Affected; +#ifndef NDEBUG + SmallVector<TreeNodePtr, 8> VisitedUnaffected; +#endif }; static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, @@ -689,6 +698,17 @@ struct SemiNCAInfo { return true; } + static bool isPermutation(const SmallVectorImpl<NodePtr> &A, + const SmallVectorImpl<NodePtr> &B) { + if (A.size() != B.size()) + return false; + SmallPtrSet<NodePtr, 4> Set(A.begin(), A.end()); + for (NodePtr N : B) + if (Set.count(N) == 0) + return false; + return true; + } + // Updates the set of roots after insertion or deletion. This ensures that // roots are the same when after a series of updates and when the tree would // be built from scratch. @@ -702,9 +722,8 @@ struct SemiNCAInfo { return; // Recalculate the set of roots. - auto Roots = FindRoots(DT, BUI); - if (DT.Roots.size() != Roots.size() || - !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), Roots.begin())) { + RootsT Roots = FindRoots(DT, BUI); + if (!isPermutation(DT.Roots, Roots)) { // The roots chosen in the CFG have changed. This is because the // incremental algorithm does not really know or use the set of roots and // can make a different (implicit) decision about which node within an @@ -715,7 +734,6 @@ struct SemiNCAInfo { // It may be possible to update the tree without recalculating it, but // we do not know yet how to do it, and it happens rarely in practise. CalculateFromScratch(DT, BUI); - return; } } @@ -737,128 +755,113 @@ struct SemiNCAInfo { assert(NCD); LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n"); - const TreeNodePtr ToIDom = To->getIDom(); + const unsigned NCDLevel = NCD->getLevel(); - // Nothing affected -- NCA property holds. - // (Based on the lemma 2.5 from the second paper.) - if (NCD == To || NCD == ToIDom) return; + // Based on Lemma 2.5 from the second paper, after insertion of (From,To), v + // is affected iff depth(NCD)+1 < depth(v) && a path P from To to v exists + // where every w on P s.t. depth(v) <= depth(w) + // + // This reduces to a widest path problem (maximizing the depth of the + // minimum vertex in the path) which can be solved by a modified version of + // Dijkstra with a bucket queue (named depth-based search in the paper). + + // To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing + // affected if this does not hold. + if (NCDLevel + 1 >= To->getLevel()) + return; - // Identify and collect affected nodes. InsertionInfo II; - LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To) - << " as affected\n"); - II.Affected.insert(To); - const unsigned ToLevel = To->getLevel(); - LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To) - << " into a Bucket\n"); - II.Bucket.push({ToLevel, To}); + SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel; + II.Bucket.push(To); + II.Visited.insert(To); while (!II.Bucket.empty()) { - const TreeNodePtr CurrentNode = II.Bucket.top().second; - const unsigned CurrentLevel = CurrentNode->getLevel(); + TreeNodePtr TN = II.Bucket.top(); II.Bucket.pop(); - LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: " - << BlockNamePrinter(CurrentNode) << "\n"); - - II.Visited.insert({CurrentNode, CurrentLevel}); - II.AffectedQueue.push_back(CurrentNode); + II.Affected.push_back(TN); + + const unsigned CurrentLevel = TN->getLevel(); + LLVM_DEBUG(dbgs() << "Mark " << BlockNamePrinter(TN) << + "as affected, CurrentLevel " << CurrentLevel << "\n"); + + assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!"); + + while (true) { + // Unlike regular Dijkstra, we have an inner loop to expand more + // vertices. The first iteration is for the (affected) vertex popped + // from II.Bucket and the rest are for vertices in + // UnaffectedOnCurrentLevel, which may eventually expand to affected + // vertices. + // + // Invariant: there is an optimal path from `To` to TN with the minimum + // depth being CurrentLevel. + for (const NodePtr Succ : + ChildrenGetter<IsPostDom>::Get(TN->getBlock(), BUI)) { + const TreeNodePtr SuccTN = DT.getNode(Succ); + assert(SuccTN && + "Unreachable successor found at reachable insertion"); + const unsigned SuccLevel = SuccTN->getLevel(); + + LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ) + << ", level = " << SuccLevel << "\n"); + + // There is an optimal path from `To` to Succ with the minimum depth + // being min(CurrentLevel, SuccLevel). + // + // If depth(NCD)+1 < depth(Succ) is not satisfied, Succ is unaffected + // and no affected vertex may be reached by a path passing through it. + // Stop here. Also, Succ may be visited by other predecessors but the + // first visit has the optimal path. Stop if Succ has been visited. + if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second) + continue; + + if (SuccLevel > CurrentLevel) { + // Succ is unaffected but it may (transitively) expand to affected + // vertices. Store it in UnaffectedOnCurrentLevel. + LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected " + << BlockNamePrinter(Succ) << "\n"); + UnaffectedOnCurrentLevel.push_back(SuccTN); +#ifndef NDEBUG + II.VisitedUnaffected.push_back(SuccTN); +#endif + } else { + // The condition is satisfied (Succ is affected). Add Succ to the + // bucket queue. + LLVM_DEBUG(dbgs() << "\t\tAdd " << BlockNamePrinter(Succ) + << " to a Bucket\n"); + II.Bucket.push(SuccTN); + } + } - // Discover and collect affected successors of the current node. - VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II); + if (UnaffectedOnCurrentLevel.empty()) + break; + TN = UnaffectedOnCurrentLevel.pop_back_val(); + LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n"); + } } // Finish by updating immediate dominators and levels. UpdateInsertion(DT, BUI, NCD, II); } - // Visits an affected node and collect its affected successors. - static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, - const TreeNodePtr TN, const unsigned RootLevel, - const TreeNodePtr NCD, InsertionInfo &II) { - const unsigned NCDLevel = NCD->getLevel(); - LLVM_DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ", RootLevel " - << RootLevel << "\n"); - - SmallVector<TreeNodePtr, 8> Stack = {TN}; - assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!"); - - SmallPtrSet<TreeNodePtr, 8> Processed; - - do { - TreeNodePtr Next = Stack.pop_back_val(); - LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n"); - - for (const NodePtr Succ : - ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) { - const TreeNodePtr SuccTN = DT.getNode(Succ); - assert(SuccTN && "Unreachable successor found at reachable insertion"); - const unsigned SuccLevel = SuccTN->getLevel(); - - LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ) - << ", level = " << SuccLevel << "\n"); - - // Do not process the same node multiple times. - if (Processed.count(Next) > 0) - continue; - - // Succ dominated by subtree From -- not affected. - // (Based on the lemma 2.5 from the second paper.) - if (SuccLevel > RootLevel) { - LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n"); - if (II.Visited.count(SuccTN) != 0) { - LLVM_DEBUG(dbgs() << "\t\t\talready visited at level " - << II.Visited[SuccTN] << "\n\t\t\tcurrent level " - << RootLevel << ")\n"); - - // A node can be necessary to visit again if we see it again at - // a lower level than before. - if (II.Visited[SuccTN] >= RootLevel) - continue; - } - - LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected " - << BlockNamePrinter(Succ) << "\n"); - II.Visited.insert({SuccTN, RootLevel}); - II.VisitedNotAffectedQueue.push_back(SuccTN); - Stack.push_back(SuccTN); - } else if ((SuccLevel > NCDLevel + 1) && - II.Affected.count(SuccTN) == 0) { - LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding " - << BlockNamePrinter(Succ) << " to a Bucket\n"); - II.Affected.insert(SuccTN); - II.Bucket.push({SuccLevel, SuccTN}); - } - } - - Processed.insert(Next); - } while (!Stack.empty()); - } - // Updates immediate dominators and levels after insertion. static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr NCD, InsertionInfo &II) { LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n"); - for (const TreeNodePtr TN : II.AffectedQueue) { + for (const TreeNodePtr TN : II.Affected) { LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN) << ") = " << BlockNamePrinter(NCD) << "\n"); TN->setIDom(NCD); } - UpdateLevelsAfterInsertion(II); - if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); - } - - static void UpdateLevelsAfterInsertion(InsertionInfo &II) { - LLVM_DEBUG( - dbgs() << "Updating levels for visited but not affected nodes\n"); +#ifndef NDEBUG + for (const TreeNodePtr TN : II.VisitedUnaffected) + assert(TN->getLevel() == TN->getIDom()->getLevel() + 1 && + "TN should have been updated by an affected ancestor"); +#endif - for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) { - LLVM_DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = (" - << BlockNamePrinter(TN->getIDom()) << ") " - << TN->getIDom()->getLevel() << " + 1\n"); - TN->UpdateLevel(); - } + if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); } // Handles insertion to previously unreachable nodes. @@ -1182,6 +1185,10 @@ struct SemiNCAInfo { BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()}); } +#if 0 + // FIXME: The LLVM_DEBUG macro only plays well with a modular + // build of LLVM when the header is marked as textual, but doing + // so causes redefinition errors. LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n"); LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U : reverse(BUI.Updates)) { @@ -1190,6 +1197,7 @@ struct SemiNCAInfo { dbgs() << "\n"; }); LLVM_DEBUG(dbgs() << "\n"); +#endif // Recalculate the DominatorTree when the number of updates // exceeds a threshold, which usually makes direct updating slower than @@ -1215,8 +1223,13 @@ struct SemiNCAInfo { static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) { assert(!BUI.Updates.empty() && "No updates to apply!"); UpdateT CurrentUpdate = BUI.Updates.pop_back_val(); +#if 0 + // FIXME: The LLVM_DEBUG macro only plays well with a modular + // build of LLVM when the header is marked as textual, but doing + // so causes redefinition errors. LLVM_DEBUG(dbgs() << "Applying update: "); LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n"); +#endif // Move to the next snapshot of the CFG by removing the reverse-applied // current update. Since updates are performed in the same order they are @@ -1270,9 +1283,7 @@ struct SemiNCAInfo { } RootsT ComputedRoots = FindRoots(DT, nullptr); - if (DT.Roots.size() != ComputedRoots.size() || - !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), - ComputedRoots.begin())) { + if (!isPermutation(DT.Roots, ComputedRoots)) { errs() << "Tree has different roots than freshly computed ones!\n"; errs() << "\tPDT roots: "; for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", "; |