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(From: std::optional<void *>(), To: Null); |
26 | ExtSetTy Ext; |
27 | po_iterator_storage<ExtSetTy, true> PISExt(Ext); |
28 | PIS.insertEdge(From: std::optional<void *>(), To: 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(G: NullBB); |
34 | PI.insertEdge(From: std::optional<BasicBlock *>(), To: NullBB); |
35 | auto PIExt = po_ext_end(G: NullBB, S&: Ext); |
36 | PIExt.insertEdge(From: std::optional<BasicBlock *>(), To: NullBB); |
37 | } |
38 | |
39 | static_assert( |
40 | std::is_convertible_v<decltype(*std::declval<po_iterator<Graph<3>>>()), |
41 | typename po_iterator<Graph<3>>::reference>); |
42 | |
43 | // Test post-order and reverse post-order traversals for simple graph type. |
44 | TEST(PostOrderIteratorTest, PostOrderAndReversePostOrderTraverrsal) { |
45 | Graph<6> G; |
46 | G.AddEdge(FromIdx: 0, ToIdx: 1); |
47 | G.AddEdge(FromIdx: 0, ToIdx: 2); |
48 | G.AddEdge(FromIdx: 0, ToIdx: 3); |
49 | G.AddEdge(FromIdx: 1, ToIdx: 4); |
50 | G.AddEdge(FromIdx: 2, ToIdx: 5); |
51 | G.AddEdge(FromIdx: 5, ToIdx: 2); |
52 | G.AddEdge(FromIdx: 2, ToIdx: 4); |
53 | G.AddEdge(FromIdx: 1, ToIdx: 4); |
54 | |
55 | SmallVector<int> FromIterator; |
56 | for (auto N : post_order(G)) |
57 | FromIterator.push_back(Elt: N->first); |
58 | EXPECT_EQ(6u, FromIterator.size()); |
59 | EXPECT_EQ(4, FromIterator[0]); |
60 | EXPECT_EQ(1, FromIterator[1]); |
61 | EXPECT_EQ(5, FromIterator[2]); |
62 | EXPECT_EQ(2, FromIterator[3]); |
63 | EXPECT_EQ(3, FromIterator[4]); |
64 | EXPECT_EQ(0, FromIterator[5]); |
65 | FromIterator.clear(); |
66 | |
67 | ReversePostOrderTraversal<Graph<6>> RPOT(G); |
68 | for (auto N : RPOT) |
69 | FromIterator.push_back(Elt: N->first); |
70 | EXPECT_EQ(6u, FromIterator.size()); |
71 | EXPECT_EQ(0, FromIterator[0]); |
72 | EXPECT_EQ(3, FromIterator[1]); |
73 | EXPECT_EQ(2, FromIterator[2]); |
74 | EXPECT_EQ(5, FromIterator[3]); |
75 | EXPECT_EQ(1, FromIterator[4]); |
76 | EXPECT_EQ(4, FromIterator[5]); |
77 | } |
78 | } |
79 | |