[ADT] Update RPOT to work with specializations of different types.
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.
Reviewed By: dexonsmith
Differential Revision: https://reviews.llvm.org/D100169
GitOrigin-RevId: d91f864ced6eebe8db35c092c8da29e87cd882b2
diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h
index 3ab76d7..74314d3 100644
--- a/include/llvm/ADT/PostOrderIterator.h
+++ b/include/llvm/ADT/PostOrderIterator.h
@@ -292,15 +292,15 @@
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(); }
diff --git a/unittests/ADT/PostOrderIteratorTest.cpp b/unittests/ADT/PostOrderIteratorTest.cpp
index 8e53247..e9ab251 100644
--- a/unittests/ADT/PostOrderIteratorTest.cpp
+++ b/unittests/ADT/PostOrderIteratorTest.cpp
@@ -9,6 +9,8 @@
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "gtest/gtest.h"
+#include "TestGraph.h"
+
using namespace llvm;
namespace {
@@ -33,4 +35,40 @@
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]);
+}
}
