[DominatorTree] Simplify ChildrenGetter.

[asbirlea]

Summary

Simplify ChildrenGetter to a simple wrapper around a GraphDiff call.
GraphDiff already handles nullptr in children, so the special casing in
clang can also be removed.

[kuhar]

LGTM.

One tiny nit: the function name ChildrenGet sounds kind of backwards to me, but it seems like the other direction is already taken.

[dblaikie]

In D84713#2177408, @kuhar wrote:

LGTM.

One tiny nit: the function name ChildrenGet sounds kind of backwards to me, but it seems like the other direction is already taken.

If there are both "ChildrenGet" and "GetChildren" in the same scope, seems like we probably should address that rather than having one awkwardly named & the ensuing lack of clarity.

[asbirlea]

Renamed ChildrenGet to getChildren. The same name only exists in GraphDiff, it's ok to keep a consistent naming.

[nikic]

This change had a significant negative compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=0b161def6cacff1a63d3cf1a1efe95b550814d7a&to=e22de4e46d1dd1aacc3a7060d24bcbe89908ba6c&stat=instructions

[asbirlea]

I'm looking into it. If needed this can be reverted as it's not blocking the work for DomTree updates with a CFGView.

[nikic]

The regression here seems to be because operations on an empty GraphDiff don't optimize out. Not going through GraphDiff but using the same basic logic (https://github.com/llvm/llvm-project/commit/4c6a5de8131183ff88f52cc3dda67180e31501a1 -- going through a separate method seems to be necessary for NRVO) we get back at least part of it: https://llvm-compile-time-tracker.com/compare.php?from=38537307e502c1ac9a09e6f75f9208db1327a0bf&to=4c6a5de8131183ff88f52cc3dda67180e31501a1&stat=instructions

[asbirlea]

Done in https://reviews.llvm.org/rG7ea0ee30588,

clang/include/clang/Analysis/Analyses/Dominators.h

LLVM_DUMP_METHOD void dump() {
     }
   }
 };
 
 } // namespace clang
 
 namespace llvm {
 
-/// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
-/// if statement's condition is always false, it's 'then' branch is represented
-/// with a nullptr. This however will result in a nullpointer derefernece for
-/// dominator tree calculation.
-///
-/// To circumvent this, let's just crudely specialize the children getters
-/// used in LLVM's dominator tree builder.
-namespace DomTreeBuilder {
-
-using ClangCFGDomChildrenGetter =
-SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
-                                                             /*Inverse=*/false>;
-
-template <>
-template <>
-inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
-    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
-  auto RChildren = reverse(children<NodePtr>(N));
-  ResultTy Ret(RChildren.begin(), RChildren.end());
-  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
-  return Ret;
-}
-
-using ClangCFGDomReverseChildrenGetter =
-SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
-                                                              /*Inverse=*/true>;
-
-template <>
-template <>
-inline ClangCFGDomReverseChildrenGetter::ResultTy
-ClangCFGDomReverseChildrenGetter::Get(
-    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
-  auto IChildren = inverse_children<NodePtr>(N);
-  ResultTy Ret(IChildren.begin(), IChildren.end());
-  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
-  return Ret;
-}
-
-using ClangCFGPostDomChildrenGetter =
-SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
-                                                             /*Inverse=*/false>;
-
-template <>
-template <>
-inline ClangCFGPostDomChildrenGetter::ResultTy
-ClangCFGPostDomChildrenGetter::Get(
-    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
-  auto RChildren = reverse(children<NodePtr>(N));
-  ResultTy Ret(RChildren.begin(), RChildren.end());
-  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
-  return Ret;
-}
-
-using ClangCFGPostDomReverseChildrenGetter =
-SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
-                                                              /*Inverse=*/true>;
-
-template <>
-template <>
-inline ClangCFGPostDomReverseChildrenGetter::ResultTy
-ClangCFGPostDomReverseChildrenGetter::Get(
-    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
-  auto IChildren = inverse_children<NodePtr>(N);
-  ResultTy Ret(IChildren.begin(), IChildren.end());
-  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
-  return Ret;
-}
-
-} // end of namespace DomTreeBuilder
-
 //===-------------------------------------
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 ///
 template <> struct GraphTraits<clang::DomTreeNode *> {
   using NodeRef = ::clang::DomTreeNode *;
   using ChildIteratorType = ::clang::DomTreeNode::const_iterator;
 

llvm/include/llvm/Support/GenericDomTreeConstruction.h

struct SemiNCAInfo {
 
   void clear() {
     NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
     NodeToInfo.clear();
     // Don't reset the pointer to BatchUpdateInfo here -- if there's an update
     // in progress, we need this information to continue it.
   }
 
-  template <bool Inversed> struct ChildrenGetter {
-    using ResultTy = SmallVector<NodePtr, 8>;
-
-    static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
-      auto RChildren = reverse(children<NodePtr>(N));
-      return ResultTy(RChildren.begin(), RChildren.end());
-    }
-
-    static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
-      auto IChildren = inverse_children<NodePtr>(N);
-      return ResultTy(IChildren.begin(), IChildren.end());
-    }
-
-    using Tag = std::integral_constant<bool, Inversed>;
-
-    // The function below is the core part of the batch updater. It allows the
-    // Depth Based Search algorithm to perform incremental updates in lockstep
-    // with updates to the CFG. We emulated lockstep CFG updates by getting its
-    // next snapshots by reverse-applying future updates.
-    static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
-      if (!BUI)
-        return Get(N, Tag());
+  template <bool Inversed>
+  static SmallVector<NodePtr, 8> ChildrenGet(NodePtr N, BatchUpdatePtr BUI) {
+    if (BUI)
       return BUI->PreViewCFG.template getChildren<Inversed>(N);
-    }
-  };
+    GraphDiffT GD;
+    return GD.template getChildren<Inversed>(N);
 
   NodePtr getIDom(NodePtr BB) const {
     auto InfoIt = NodeToInfo.find(BB);
     if (InfoIt == NodeToInfo.end()) return nullptr;
 
     return InfoIt->second.IDom;
   }
 
while (!WorkList.empty()) {
 
       // Visited nodes always have positive DFS numbers.
       if (BBInfo.DFSNum != 0) continue;
       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
       BBInfo.Label = BB;
       NumToNode.push_back(BB);
 
       constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
-      for (const NodePtr Succ :
-           ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
+      for (const NodePtr Succ : ChildrenGet<Direction>(BB, BatchUpdates)) {
         const auto SIT = NodeToInfo.find(Succ);
         // Don't visit nodes more than once but remember to collect
         // ReverseChildren.
         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
           continue;
         }
 
void addVirtualRoot() {
     NumToNode.push_back(nullptr);  // NumToNode[1] = nullptr;
   }
 
   // For postdominators, nodes with no forward successors are trivial roots that
   // are always selected as tree roots. Roots with forward successors correspond
   // to CFG nodes within infinite loops.
   static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
     assert(N && "N must be a valid node");
-    return !ChildrenGetter<false>::Get(N, BUI).empty();
+    return !ChildrenGet<false>(N, BUI).empty();
   }
 
   static NodePtr GetEntryNode(const DomTreeT &DT) {
     assert(DT.Parent && "Parent not set");
     return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
   }
 
   // Finds all roots without relaying on the set of roots already stored in the
while (!II.Bucket.empty()) {
         // 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)) {
+        for (const NodePtr Succ : ChildrenGet<IsPostDom>(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");
 
static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
     LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
                       << BlockNamePrinter(To) << "\n");
 
 #ifndef NDEBUG
     // Ensure that the edge was in fact deleted from the CFG before informing
     // the DomTree about it.
     // The check is O(N), so run it only in debug configuration.
     auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
-      auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
+      auto Successors = ChildrenGet<IsPostDom>(Of, BUI);
       return llvm::find(Successors, SuccCandidate) != Successors.end();
     };
     (void)IsSuccessor;
     assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
 #endif
 
     const TreeNodePtr FromTN = DT.getNode(From);
     // Deletion in an unreachable subtree -- nothing to do.
#endif
 
   // Checks if a node has proper support, as defined on the page 3 and later
   // 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");
     auto TNB = TN->getBlock();
-    for (const NodePtr Pred : ChildrenGetter<!IsPostDom>::Get(TNB, BUI)) {
+    for (const NodePtr Pred : ChildrenGet<!IsPostDom>(TNB, BUI)) {
       LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
       if (!DT.getNode(Pred)) continue;
 
       const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);
       LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
       if (Support != TNB) {
         LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
                           << " is reachable from support "