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
TEST(PostOrderIteratorTest,Compiles)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.
TEST(PostOrderIteratorTest,PostOrderAndReversePostOrderTraverrsal)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