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 #include <array> 15 #include <iterator> 16 #include <type_traits> 17 18 #include <cstddef> 19 20 using namespace llvm; 21 22 namespace { 23 24 // Whether we're able to compile 25 TEST(PostOrderIteratorTest, Compiles) { 26 typedef SmallPtrSet<void *, 4> ExtSetTy; 27 28 // Tests that template specializations are kept up to date 29 void *Null = nullptr; 30 po_iterator_storage<std::set<void *>, false> PIS; 31 PIS.insertEdge(std::optional<void *>(), Null); 32 ExtSetTy Ext; 33 po_iterator_storage<ExtSetTy, true> PISExt(Ext); 34 PIS.insertEdge(std::optional<void *>(), Null); 35 36 // Test above, but going through po_iterator (which inherits from template 37 // base) 38 BasicBlock *NullBB = nullptr; 39 auto PI = po_end(NullBB); 40 PI.insertEdge(std::optional<BasicBlock *>(), NullBB); 41 auto PIExt = po_ext_end(NullBB, Ext); 42 PIExt.insertEdge(std::optional<BasicBlock *>(), NullBB); 43 } 44 45 static_assert( 46 std::is_convertible_v<decltype(*std::declval<po_iterator<Graph<3>>>()), 47 typename po_iterator<Graph<3>>::reference>); 48 49 // Test post-order and reverse post-order traversals for simple graph type. 50 TEST(PostOrderIteratorTest, PostOrderAndReversePostOrderTraverrsal) { 51 Graph<6> G; 52 G.AddEdge(0, 1); 53 G.AddEdge(0, 2); 54 G.AddEdge(0, 3); 55 G.AddEdge(1, 4); 56 G.AddEdge(2, 5); 57 G.AddEdge(5, 2); 58 G.AddEdge(2, 4); 59 G.AddEdge(1, 4); 60 61 SmallVector<int> FromIterator; 62 for (auto N : post_order(G)) 63 FromIterator.push_back(N->first); 64 EXPECT_EQ(6u, FromIterator.size()); 65 EXPECT_EQ(4, FromIterator[0]); 66 EXPECT_EQ(1, FromIterator[1]); 67 EXPECT_EQ(5, FromIterator[2]); 68 EXPECT_EQ(2, FromIterator[3]); 69 EXPECT_EQ(3, FromIterator[4]); 70 EXPECT_EQ(0, FromIterator[5]); 71 FromIterator.clear(); 72 73 ReversePostOrderTraversal<Graph<6>> RPOT(G); 74 for (auto N : RPOT) 75 FromIterator.push_back(N->first); 76 EXPECT_EQ(6u, FromIterator.size()); 77 EXPECT_EQ(0, FromIterator[0]); 78 EXPECT_EQ(3, FromIterator[1]); 79 EXPECT_EQ(2, FromIterator[2]); 80 EXPECT_EQ(5, FromIterator[3]); 81 EXPECT_EQ(1, FromIterator[4]); 82 EXPECT_EQ(4, FromIterator[5]); 83 } 84 85 // po_iterator should be (at-least) a forward-iterator 86 static_assert(std::is_base_of_v<std::forward_iterator_tag, 87 po_iterator<Graph<4>>::iterator_category>); 88 89 // po_ext_iterator cannot provide multi-pass guarantee, therefore its only 90 // an input-iterator 91 static_assert(std::is_same_v<po_ext_iterator<Graph<4>>::iterator_category, 92 std::input_iterator_tag>); 93 94 TEST(PostOrderIteratorTest, MultiPassSafeWithInternalSet) { 95 Graph<4> G; 96 G.AddEdge(0, 1); 97 G.AddEdge(1, 2); 98 G.AddEdge(1, 3); 99 100 std::array<decltype(G)::NodeType *, 4> NodesFirstPass, NodesSecondPass; 101 102 auto B = po_begin(G), E = po_end(G); 103 104 std::size_t I = 0; 105 for (auto It = B; It != E; ++It) 106 NodesFirstPass[I++] = *It; 107 108 I = 0; 109 for (auto It = B; It != E; ++It) 110 NodesSecondPass[I++] = *It; 111 112 EXPECT_EQ(NodesFirstPass, NodesSecondPass); 113 } 114 } 115