[Dominators] Fixup comments in GenericDominatorTreeConstruction. NFC.

[NutshellySima]

Thank you. LGTM.

[asbirlea]

Thank you!

llvm/include/llvm/Support/GenericDomTreeConstruction.h

1509

No new line between method description and method declaration?

[kuhar]

llvm/include/llvm/Support/GenericDomTreeConstruction.h

1509

Good catch, thanks!

llvm/include/llvm/Support/GenericDomTreeConstruction.h

 //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//
 //
 // 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
 ///
-/// 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
 ///
 /// 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.
+/// 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
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
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
       // infinite loop becomes a root.
 
       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);
     }
   }
 
   // Handles insertion to a node already in the dominator tree.
   static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
                               const TreeNodePtr From, const TreeNodePtr To) {
     LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
                       << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
     if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
     // DT.findNCD expects both pointers to be valid. When From is a virtual
     // root, then its CFG block pointer is a nullptr, so we have to 'compute'
     // the NCD manually.
     const NodePtr NCDBlock =
         (From->getBlock() && To->getBlock())
             ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
             : nullptr;
     assert(NCDBlock || DT.isPostDominator());
     const TreeNodePtr NCD = DT.getNode(NCDBlock);
     assert(NCD);
 
     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.
     if (NCDLevel + 1 >= To->getLevel())
       return;
 
     InsertionInfo II;
     SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel;
#endif
     if (ToTN != NCD) {
       DT.DFSInfoValid = false;
 
       const TreeNodePtr ToIDom = ToTN->getIDom();
       LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
                         << 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
         DeleteUnreachable(DT, BUI, ToTN);
     }
 
     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
   }
 
   // Handles deletions that leave destination nodes reachable.
   static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
                               const TreeNodePtr FromTN,
                               const TreeNodePtr ToTN) {
     LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN)
                       << " -> " << BlockNamePrinter(ToTN) << "\n");
     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());
     const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
     assert(ToIDomTN);
     const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
     // Top of the subtree to rebuild is the root node. Rebuild the tree from
     // scratch.
static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
     SemiNCAInfo SNCA(BUI);
     SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
     LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
     SNCA.runSemiNCA(DT, Level);
     SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
   }
 
   // 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)
                       << "\n");
     for (const NodePtr Pred :
          ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
       LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
       if (!DT.getNode(Pred)) continue;
 
       const NodePtr Support =
           DT.findNearestCommonDominator(TN->getBlock(), Pred);
       LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
       if (Support != TN->getBlock()) {
         LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
                           << " is reachable from support "
                           << BlockNamePrinter(Support) << "\n");
         return true;
       }
     }
 
     return false;
   }
 
   // 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 "
                       << BlockNamePrinter(ToTN) << "\n");
     assert(ToTN);
     assert(ToTN->getBlock());
 
     if (IsPostDom) {
#endif
 
   // The sibling property is similar.  It says that for each pair of sibling
   // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
   // other.  If sibling LEFT dominated sibling RIGHT, it means there are no
   // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
   // 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
   // an ancestor of V in the tree.
   // Running time: O(N^2).
   //
   // This means that if a node gets disconnected from the graph, then all of
   // the nodes it dominated previously will now become unreachable.
   bool verifyParentProperty(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
       const NodePtr BB = TN->getBlock();
       if (!BB || TN->getChildren().empty()) continue;
 
       LLVM_DEBUG(dbgs() << "Verifying parent property of node "
                         << BlockNamePrinter(TN) << "\n");
       clear();
for (auto &NodeToTN : DT.DomTreeNodes) {
       }
     }
 
     return true;
   }
 
   // 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)
   // verification.
   static bool IsSameAsFreshTree(const DomTreeT &DT) {
     DomTreeT FreshTree;
     FreshTree.recalculate(*DT.Parent);
     const bool Different = DT.compare(FreshTree);

 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
   SemiNCAInfo<DomTreeT> SNCA(nullptr);
 
   // Simplist check is to compare against a new tree. This will also
   // usefully print the old and new trees, if they are different.
   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))
       return false;
   if (VL == DomTreeT::VerificationLevel::Full)
     if (!SNCA.verifySiblingProperty(DT))
       return false;