DomTree: Define GraphTraits for GenericDomTreeBase

[nhaehnle]

Summary

Allow generic graph algorithms to operate on the type-erased base classes.

Change-Id: I59735dfcea41f89d30dfa304bdfe07050b7a5a7d

llvm/include/llvm/IR/Dominators.h

 //===- Dominators.h - Dominator Info 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
 //
 //===----------------------------------------------------------------------===//
 //
public:
   void viewGraph(const Twine &Name, const Twine &Title);
   void viewGraph();
 };
 
 //===-------------------------------------
 // DominatorTree GraphTraits specializations so the DominatorTree can be
 // iterable by generic graph iterators.
 
-template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
-  using NodeRef = Node *;
-  using ChildIteratorType = ChildIterator;
-  using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node*>>;
-
-  static NodeRef getEntryNode(NodeRef N) { return N; }
-  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
-  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
-
-  static nodes_iterator nodes_begin(NodeRef N) {
-    return df_begin(getEntryNode(N));
-  }
-
-  static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
-};
-
 template <>
 struct GraphTraits<DomTreeNode *>
     : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::const_iterator> {
 };
 
 template <>
 struct GraphTraits<const DomTreeNode *>
     : public DomTreeGraphTraitsBase<const DomTreeNode,

llvm/include/llvm/Support/GenericDomTree.h

 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- 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

 /// FIXME: Should GenericDomTree be implemented entirely in terms of CfgTraits?
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
 #define LLVM_SUPPORT_GENERICDOMTREE_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/CFGUpdate.h"
 #include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>

 };
 
 template <typename T>
 using DomTreeBase = DominatorTreeBase<T, false>;
 
 template <typename T>
 using PostDomTreeBase = DominatorTreeBase<T, true>;
 
+//===-------------------------------------
+// GraphTraits specializations so that the generic type-erased dominator tree
+// can be iterated by generic graph iterators.
+
+template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
+  using NodeRef = Node *;
+  using ChildIteratorType = ChildIterator;
+  using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node *>>;
+
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
+
+  static nodes_iterator nodes_begin(NodeRef N) {
+    return df_begin(getEntryNode(N));
+  }
+
+  static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
+};
+
+template <>
+struct GraphTraits<GenericDomTreeNodeBase *>
+    : public DomTreeGraphTraitsBase<GenericDomTreeNodeBase,
+                                    GenericDomTreeNodeBase::iterator> {};
+
+template <>
+struct GraphTraits<const GenericDomTreeNodeBase *>
+    : public DomTreeGraphTraitsBase<const GenericDomTreeNodeBase,
+                                    GenericDomTreeNodeBase::const_iterator> {};
+
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_GENERICDOMTREE_H