| 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(std::optional<void *>(), Null); |
| 26 |
ExtSetTy Ext; |
| 27 |
po_iterator_storage<ExtSetTy, true> PISExt(Ext); |
| 28 |
PIS.insertEdge(std::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(std::optional<BasicBlock *>(), NullBB); |
| 35 |
auto PIExt = po_ext_end(NullBB, Ext); |
| 36 |
PIExt.insertEdge(std::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 |
} |