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 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 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(0, 1);
  47   G.AddEdge(0, 2);
  48   G.AddEdge(0, 3);
  49   G.AddEdge(1, 4);
  50   G.AddEdge(2, 5);
  51   G.AddEdge(5, 2);
  52   G.AddEdge(2, 4);
  53   G.AddEdge(1, 4);
  54
  55   SmallVector<int> FromIterator;
  56   for (auto N : post_order(G))
  57     FromIterator.push_back(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(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 }