diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -7,11 +7,11 @@ //===----------------------------------------------------------------------===// /// \file /// -/// Generic dominator tree construction - This file provides routines to +/// Generic dominator tree construction - this file provides routines to /// construct immediate dominator information for a flow-graph based on the /// Semi-NCA algorithm described in this dissertation: /// -/// Linear-Time Algorithms for Dominators and Related Problems +/// [1] Linear-Time Algorithms for Dominators and Related Problems /// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23: /// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf /// @@ -20,13 +20,15 @@ /// /// 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. +/// ever turns out to be an issue, consider implementing a hybrid algorithm +/// that uses SLT to perform full constructions and SemiNCA for incremental +/// updates. /// /// The file uses the Depth Based Search algorithm to perform incremental /// updates (insertion and deletions). The implemented algorithm is based on /// this publication: /// -/// An Experimental Study of Dynamic Dominators +/// [2] An Experimental Study of Dynamic Dominators /// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10: /// https://arxiv.org/pdf/1604.02711.pdf /// @@ -732,7 +734,7 @@ LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n" << "The entire tree needs to be rebuilt\n"); // 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. + // we do not know yet how to do it, and it happens rarely in practice. CalculateFromScratch(DT, BUI); } } @@ -757,13 +759,13 @@ LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n"); const unsigned NCDLevel = NCD->getLevel(); - // 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) + // Based on Lemma 2.5 from [2], 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). + // Dijkstra with a bucket queue (named depth-based search in [2]). // To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing // affected if this does not hold. @@ -957,7 +959,7 @@ << BlockNamePrinter(ToIDom) << "\n"); // To remains reachable after deletion. - // (Based on the caption under Figure 4. from the second paper.) + // (Based on the caption under Figure 4. from [2].) if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) DeleteReachable(DT, BUI, FromTN, ToTN); else @@ -976,7 +978,7 @@ LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n"); // Find the top of the subtree that needs to be rebuilt. - // (Based on the lemma 2.6 from the second paper.) + // (Based on the lemma 2.6 from [2].) const NodePtr ToIDom = DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock()); assert(ToIDom || DT.isPostDominator()); @@ -1008,7 +1010,7 @@ } // Checks if a node has proper support, as defined on the page 3 and later - // explained on the page 7 of the second paper. + // explained on the page 7 of [2]. static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN) { LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) @@ -1033,7 +1035,7 @@ } // Handle deletions that make destination node unreachable. - // (Based on the lemma 2.7 from the second paper.) + // (Based on the lemma 2.7 from the [2].) static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr ToTN) { LLVM_DEBUG(dbgs() << "Deleting unreachable subtree " @@ -1493,9 +1495,9 @@ // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of // RIGHT, not a sibling. - // It is possible to verify the parent and sibling properties in - // linear time, but the algorithms are complex. Instead, we do it in a - // straightforward N^2 and N^3 way below, using direct path reachability. + // It is possible to verify the parent and sibling properties in linear time, + // but the algorithms are complex. Instead, we do it in a straightforward + // N^2 and N^3 way below, using direct path reachability. // Checks if the tree has the parent property: if for all edges from V to W in // the input graph, such that V is reachable, the parent of W in the tree is @@ -1571,7 +1573,7 @@ // Check if the given tree is the same as a freshly computed one for the same // Parent. - // Running time: O(N^2), but faster in practise (same as tree construction). + // Running time: O(N^2), but faster in practice (same as tree construction). // // Note that this does not check if that the tree construction algorithm is // correct and should be only used for fast (but possibly unsound) @@ -1648,12 +1650,12 @@ if (!SNCA.IsSameAsFreshTree(DT)) return false; - // Common checks to verify the properties of the tree. O(N log N) at worst + // Common checks to verify the properties of the tree. O(N log N) at worst. if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) || !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT)) return false; - // Extra checks depending on VerificationLevel. Up to O(N^3) + // Extra checks depending on VerificationLevel. Up to O(N^3). if (VL == DomTreeT::VerificationLevel::Basic || VL == DomTreeT::VerificationLevel::Full) if (!SNCA.verifyParentProperty(DT))