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
14using namespace llvm;
15
16namespace {
17
18// Whether we're able to compile
19TEST(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
39static_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.
44TEST(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

source code of llvm/unittests/ADT/PostOrderIteratorTest.cpp