1 //===- PostOrderIteratorTest.cpp - PostOrderIterator unit tests -----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 #include "llvm/ADT/PostOrderIterator.h"
9 #include "llvm/IR/BasicBlock.h"
10 #include "llvm/IR/CFG.h"
11 #include "gtest/gtest.h"
12 #include "TestGraph.h"
13 
14 using namespace llvm;
15 
16 namespace {
17 
18 // Whether we're able to compile
19 TEST(PostOrderIteratorTest, Compiles) {
20   typedef SmallPtrSet<void *, 4> ExtSetTy;
21 
22   // Tests that template specializations are kept up to date
23   void *Null = nullptr;
24   po_iterator_storage<std::set<void *>, false> PIS;
25   PIS.insertEdge(Optional<void *>(), Null);
26   ExtSetTy Ext;
27   po_iterator_storage<ExtSetTy, true> PISExt(Ext);
28   PIS.insertEdge(Optional<void *>(), Null);
29 
30   // Test above, but going through po_iterator (which inherits from template
31   // base)
32   BasicBlock *NullBB = nullptr;
33   auto PI = po_end(NullBB);
34   PI.insertEdge(Optional<BasicBlock *>(), NullBB);
35   auto PIExt = po_ext_end(NullBB, Ext);
36   PIExt.insertEdge(Optional<BasicBlock *>(), NullBB);
37 }
38 
39 // Test post-order and reverse post-order traversals for simple graph type.
40 TEST(PostOrderIteratorTest, PostOrderAndReversePostOrderTraverrsal) {
41   Graph<6> G;
42   G.AddEdge(0, 1);
43   G.AddEdge(0, 2);
44   G.AddEdge(0, 3);
45   G.AddEdge(1, 4);
46   G.AddEdge(2, 5);
47   G.AddEdge(5, 2);
48   G.AddEdge(2, 4);
49   G.AddEdge(1, 4);
50 
51   SmallVector<int> FromIterator;
52   for (auto N : post_order(G))
53     FromIterator.push_back(N->first);
54   EXPECT_EQ(6u, FromIterator.size());
55   EXPECT_EQ(4, FromIterator[0]);
56   EXPECT_EQ(1, FromIterator[1]);
57   EXPECT_EQ(5, FromIterator[2]);
58   EXPECT_EQ(2, FromIterator[3]);
59   EXPECT_EQ(3, FromIterator[4]);
60   EXPECT_EQ(0, FromIterator[5]);
61   FromIterator.clear();
62 
63   ReversePostOrderTraversal<Graph<6>> RPOT(G);
64   for (auto N : RPOT)
65     FromIterator.push_back(N->first);
66   EXPECT_EQ(6u, FromIterator.size());
67   EXPECT_EQ(0, FromIterator[0]);
68   EXPECT_EQ(3, FromIterator[1]);
69   EXPECT_EQ(2, FromIterator[2]);
70   EXPECT_EQ(5, FromIterator[3]);
71   EXPECT_EQ(1, FromIterator[4]);
72   EXPECT_EQ(4, FromIterator[5]);
73 }
74 }
75