[ADT] Update RPOT to work with specializations of different types.

[fhahn]

Summary

At the moment, ReversePostOrderTraversal performs a post-order walk on
the entry node of the passed in graph, rather than the graph type
itself.

If GT::NodeRef is the same as GraphT, everything works as expected and
this is the case for the current uses in-tree. But it does not work as
expected if GraphT != GT::NodeRef. In that case, we either fail to build
(if there is no GraphTrait specialization for GT:NodeRef) or we pick the
GraphTrait specialization for GT::NodeRef, instead of the specialization
of GraphT.

Both the depth-first and post-order iterators pick the expected
specalization and this patch updates ReversePostOrderTraversal to
delegate to po_begin & po_end to pick the right specialization, rather
than forcing using GraphTraits<GT::NodeRef>, by first getting the entry
node.

This makes ReversePostOrderTraversal<Graph<6>> RPOT(G); build and
work as expected in the test.

The patch also updates a couple of functions that unnecessarily took the
input graph by value, when it was not needed. They can take the graph by
const-reference instead, which does not require GraphT to provide a copy
constructor. This technically is a separate change, but is required to
be able to use Graph<> from TestGraph in the test, because it does not
provide a copy constructor. If desired, I can split this out as a
separate change.

[dexonsmith]

Looks like a nice clean up; LGTM.

The patch also updates a couple of functions that unnecessarily took the
input graph by value, when it was not needed. They can take the graph by
const-reference instead, which does not require GraphT to provide a copy
constructor. This technically is a separate change, but is required to
be able to use Graph<> from TestGraph in the test, because it does not
provide a copy constructor. If desired, I can split this out as a
separate change.

My tendency would usually be an NFC prep commit as you suggest, but at the same time it's nice to land a coincident, motivating use case (which would be the Graph test). Either way seems fine.

[fhahn]

Thanks Duncan! I'll commit the changes const & changes to the post-order iterators separately.

[fhahn]

Rebased after landing the post-order iterator fixes in bbf01f96b5ccc1dcb4d1d47cb55292c27c698dbb.

llvm/include/llvm/ADT/PostOrderIterator.h

while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
         // If the block is not visited...
         VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
       }
     }
   }
 
 public:
   // Provide static "constructors"...
-  static po_iterator begin(GraphT G) {
+  static po_iterator begin(const GraphT &G) {
     return po_iterator(GT::getEntryNode(G));
   }
-  static po_iterator end(GraphT G) { return po_iterator(); }
+  static po_iterator end(const GraphT &G) { return po_iterator(); }
 
-  static po_iterator begin(GraphT G, SetType &S) {
+  static po_iterator begin(const GraphT &G, SetType &S) {
     return po_iterator(GT::getEntryNode(G), S);
   }
-  static po_iterator end(GraphT G, SetType &S) { return po_iterator(S); }
+  static po_iterator end(const GraphT &G, SetType &S) { return po_iterator(S); }
 
   bool operator==(const po_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
   bool operator!=(const po_iterator &x) const { return !(*this == x); }
 
   const NodeRef &operator*() const { return VisitStack.back().first; }
 

 //
 
 template<class GraphT, class GT = GraphTraits<GraphT>>
 class ReversePostOrderTraversal {
   using NodeRef = typename GT::NodeRef;
 
   std::vector<NodeRef> Blocks; // Block list in normal PO order
 
-  void Initialize(NodeRef BB) {
-    std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks));
+  void Initialize(const GraphT &G) {
+    std::copy(po_begin(G), po_end(G), std::back_inserter(Blocks));
   }
 
 public:
   using rpo_iterator = typename std::vector<NodeRef>::reverse_iterator;
   using const_rpo_iterator = typename std::vector<NodeRef>::const_reverse_iterator;
 
-  ReversePostOrderTraversal(GraphT G) { Initialize(GT::getEntryNode(G)); }
+  ReversePostOrderTraversal(const GraphT &G) { Initialize(G); }
 
   // Because we want a reverse post order, use reverse iterators from the vector
   rpo_iterator begin() { return Blocks.rbegin(); }
   const_rpo_iterator begin() const { return Blocks.crbegin(); }
   rpo_iterator end() { return Blocks.rend(); }
   const_rpo_iterator end() const { return Blocks.crend(); }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_POSTORDERITERATOR_H

llvm/unittests/ADT/PostOrderIteratorTest.cpp

 //===- PostOrderIteratorTest.cpp - PostOrderIterator unit tests -----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/ADT/PostOrderIterator.h"
+#include "TestGraph.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "gtest/gtest.h"
 using namespace llvm;
 
 namespace {
 
 // Whether we're able to compile
TEST(PostOrderIteratorTest, Compiles) {
   // Test above, but going through po_iterator (which inherits from template
   // base)
   BasicBlock *NullBB = nullptr;
   auto PI = po_end(NullBB);
   PI.insertEdge(Optional<BasicBlock *>(), NullBB);
   auto PIExt = po_ext_end(NullBB, Ext);
   PIExt.insertEdge(Optional<BasicBlock *>(), NullBB);
 }
+
+// Test post-order and reverse post-order traversals for simple graph type.
+TEST(PostOrderIteratorTest, PostOrderAndReversePostOrderTraverrsal) {
+  Graph<6> G;
+  G.AddEdge(0, 1);
+  G.AddEdge(0, 2);
+  G.AddEdge(0, 3);
+  G.AddEdge(1, 4);
+  G.AddEdge(2, 5);
+  G.AddEdge(5, 2);
+  G.AddEdge(2, 4);
+  G.AddEdge(1, 4);
+
+  SmallVector<int> FromIterator;
+  for (auto N : post_order(G))
+    FromIterator.push_back(N->first);
+  EXPECT_EQ(6u, FromIterator.size());
+  EXPECT_EQ(4, FromIterator[0]);
+  EXPECT_EQ(1, FromIterator[1]);
+  EXPECT_EQ(5, FromIterator[2]);
+  EXPECT_EQ(2, FromIterator[3]);
+  EXPECT_EQ(3, FromIterator[4]);
+  EXPECT_EQ(0, FromIterator[5]);
+  FromIterator.clear();
+
+  ReversePostOrderTraversal<Graph<6>> RPOT(G);
+  for (auto N : RPOT)
+    FromIterator.push_back(N->first);
+  EXPECT_EQ(6u, FromIterator.size());
+  EXPECT_EQ(0, FromIterator[0]);
+  EXPECT_EQ(3, FromIterator[1]);
+  EXPECT_EQ(2, FromIterator[2]);
+  EXPECT_EQ(5, FromIterator[3]);
+  EXPECT_EQ(1, FromIterator[4]);
+  EXPECT_EQ(4, FromIterator[5]);
+}
 }