llvm/unittests/ADT/PostOrderIteratorTest.cpp

   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 }