Cache reverse graph edges during dominator construction to avoid having to look them up later.

[• dberlin]

Summary

We already visit every single successor of the graph, so we don't
actually need to find the inverse edges, we can just store what they
are. This removes the need for inverse traits to compute dominators.

It's also a very slight speedup on large graphs, i'm leaving it here
while I test it on non-x86 platforms.

[davide]

include/llvm/Support/GenericDomTree.h

250

Just wondering, why 2?

[• dberlin]

Mostly empirical testing. By far, most nodes are either unconditional jumps or two block conditionals (be cond, invoke, etc)

[davide]

In D29243#659650, @dberlin wrote:

Mostly empirical testing. By far, most nodes are either unconditional jumps or two block conditionals (be cond, invoke, etc)

Makes sense. I would add a comment to explain, if you don't mind. Most of the times I scratch my head trying to figure out how SmallVector<> initial size was chosen, and guess what, sometimes the choice is quite arbitrary (here we have a rationale, so wouldn't hurt adding that to the code). Assuming your non-x86 testing doesn't reveal any problems, I'd say ship it.

[davide]

include/llvm/Support/GenericDomTreeConstruction.h

206

Nit: I prefer the explicit type when non-obvious from the right hand side, and I just recently realized LLVM coding convention suggests this too. Anyway, this is just splitting hair, so, up to you.

[davide]

Are you landing this one?

[• dberlin]

I will add a comment about the #2 and land this one.

[• dberlin]

include/llvm/Support/GenericDomTree.h

250

commented

include/llvm/Support/GenericDomTreeConstruction.h

206

Making this an explicit type is a bit annoying. The real type is really GraphTraits<Inverse<NodeT> >::NodeRef

You would think it's just NodeT * (since that's what is in the SmallVector) ,but using NodeT causes it to screw up the inference of Calculate everywhere.

So i'm going to leave it auto :)

[davide]

LGTM, thanks.

include/llvm/Support/GenericDomTreeConstruction.h

206

Oh, sure.

[davide]

Dan, you still plan to get this in? FWIW, I ran with it for a while in my local tree.

include/llvm/Support/GenericDomTree.h

protected:
   mutable bool DFSInfoValid;
   mutable unsigned int SlowQueries;
   // Information record used during immediate dominators computation.
   struct InfoRec {
     unsigned DFSNum;
     unsigned Parent;
     unsigned Semi;
     NodeT *Label;
-
+    SmallVector<NodeT *, 2> ReverseChildren;
     InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {}
   };
 
   DenseMap<NodeT *, NodeT *> IDoms;
 
   // Vertex - Map the DFS number to the NodeT*
   std::vector<NodeT *> Vertex;
 

include/llvm/Support/GenericDomTreeConstruction.h

while (!Worklist.empty()) {
 
     // Increment the successor number for the next time we get to it.
     ++Worklist.back().second;
 
     // Visit the successor next, if it isn't already visited.
     typename GraphT::NodeRef Succ = *NextSucc;
 
     auto &SuccVInfo = DT.Info[Succ];
+    SuccVInfo.ReverseChildren.push_back(BB);
+
     if (SuccVInfo.Semi == 0) {
       SuccVInfo.Parent = BBDFSNum;
       Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
     }
   }
 #endif
     return N;
 }
for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) {
       typename GraphT::NodeRef U = Eval<GraphT>(DT, V, i + 1);
       DT.IDoms[V] = DT.Info[U].Semi < i ? U : W;
     }
 
     // Step #3: Calculate the semidominators of all vertices
 
     // initialize the semi dominator to point to the parent node
     WInfo.Semi = WInfo.Parent;
-    typedef GraphTraits<Inverse<NodeT> > InvTraits;
-    for (typename InvTraits::ChildIteratorType CI =
-         InvTraits::child_begin(W),
-         E = InvTraits::child_end(W); CI != E; ++CI) {
-      typename InvTraits::NodeRef N = *CI;
-      if (DT.Info.count(N)) {  // Only if this predecessor is reachable!
+    for (auto *N : WInfo.ReverseChildren) {
         unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
-      }
-    }
 
     // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is
     // necessarily parent(V). In this case, set idom(V) here and avoid placing
     // V into a bucket.
     if (WInfo.Semi == WInfo.Parent) {
       DT.IDoms[W] = DT.Vertex[WInfo.Parent];
     } else {
       Buckets[i] = Buckets[WInfo.Semi];