TraverserTests.cpp

Go to the documentation of this file.

/*
 * Copyright 2017 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#include <gtest/gtest.h>
 
#include <jlm/rvsdg/TestOperations.hpp>
#include <jlm/rvsdg/TestType.hpp>
#include <jlm/rvsdg/traverser.hpp>
 
TEST(TopDownTraverserTests, testInitialization)
{
  using namespace jlm::rvsdg;
 
  auto vtype = jlm::rvsdg::TestType::createValueType();
 
  jlm::rvsdg::Graph graph;
  auto i = &jlm::rvsdg::GraphImport::Create(graph, vtype, "i");
 
  auto constant = TestOperation::createNode(&graph.GetRootRegion(), {}, { vtype });
  auto unary = TestOperation::createNode(&graph.GetRootRegion(), { i }, { vtype });
  auto binary =
      TestOperation::createNode(&graph.GetRootRegion(), { i, unary->output(0) }, { vtype });
 
  jlm::rvsdg::GraphExport::Create(*constant->output(0), "c");
  jlm::rvsdg::GraphExport::Create(*unary->output(0), "u");
  jlm::rvsdg::GraphExport::Create(*binary->output(0), "b");
 
  bool unary_visited = false;
  bool binary_visited = false;
  bool constant_visited = false;
  for (const auto & node : jlm::rvsdg::TopDownTraverser(&graph.GetRootRegion()))
  {
    if (node == unary)
      unary_visited = true;
    if (node == constant)
      constant_visited = true;
    if (node == binary && unary_visited)
      binary_visited = true;
  }
 
  EXPECT_TRUE(unary_visited);
  EXPECT_TRUE(binary_visited);
  EXPECT_TRUE(constant_visited);
}
 
TEST(TopDownTraverserTests, testBasicTraversal)
{
  using namespace jlm::rvsdg;
 
  jlm::rvsdg::Graph graph;
  auto type = jlm::rvsdg::TestType::createValueType();
 
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type, type });
  auto n2 =
      TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0), n1->output(1) }, { type });
 
  jlm::rvsdg::GraphExport::Create(*n2->output(0), "dummy");
 
  {
    const jlm::rvsdg::Node * tmp = nullptr;
    jlm::rvsdg::TopDownTraverser trav(&graph.GetRootRegion());
 
    tmp = trav.next();
    EXPECT_EQ(tmp, n1);
    tmp = trav.next();
    EXPECT_EQ(tmp, n2);
    tmp = trav.next();
    EXPECT_EQ(tmp, nullptr);
  }
}
 
TEST(TopDownTraverserTests, testOrderEnforcement)
{
  using namespace jlm::rvsdg;
 
  jlm::rvsdg::Graph graph;
  auto type = jlm::rvsdg::TestType::createValueType();
 
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type, type });
  auto n2 = TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0) }, { type });
  auto n3 =
      TestOperation::createNode(&graph.GetRootRegion(), { n2->output(0), n1->output(1) }, { type });
 
  {
    const jlm::rvsdg::Node * tmp = nullptr;
    jlm::rvsdg::TopDownTraverser trav(&graph.GetRootRegion());
 
    tmp = trav.next();
    EXPECT_EQ(tmp, n1);
    tmp = trav.next();
    EXPECT_EQ(tmp, n2);
    tmp = trav.next();
    EXPECT_EQ(tmp, n3);
    tmp = trav.next();
    EXPECT_EQ(tmp, nullptr);
  }
}
 
TEST(TopDownTraverserTests, testInsertion)
{
  using namespace jlm::rvsdg;
 
  jlm::rvsdg::Graph graph;
  auto type = jlm::rvsdg::TestType::createValueType();
 
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type, type });
  auto n2 =
      TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0), n1->output(1) }, { type });
  auto n3 = TestOperation::createNode(&graph.GetRootRegion(), { n2->output(0) }, { type });
 
  auto & graphExport = jlm::rvsdg::GraphExport::Create(*n3->output(0), "dummy");
 
  {
    const jlm::rvsdg::Node * node = nullptr;
    jlm::rvsdg::TopDownTraverser trav(&graph.GetRootRegion());
 
    node = trav.next();
    EXPECT_EQ(node, n1);
 
    /* At this point, n1 has been visited, make the transformation */
 
    auto nX = TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0) }, { type });
    n3->input(0)->divert_to(n1->output(1));
    auto nY = TestOperation::createNode(&graph.GetRootRegion(), { n3->output(0) }, { type });
 
    n2->input(0)->divert_to(nX->output(0));
    n2->input(1)->divert_to(nY->output(0));
 
    graphExport.divert_to(n2->output(0));
 
    // The newly created nX and nY should not be visited, but n3 must come before n2
 
    node = trav.next();
    EXPECT_EQ(node, n3);
    node = trav.next();
    EXPECT_EQ(node, n2);
    node = trav.next();
    EXPECT_EQ(node, nullptr);
  }
}
 
TEST(TopDownTraverserTests, testInsertingTopNode)
{
  // Starts with a graph like
  // n1 -> n2 -> GraphExport
  //
  // when n1 is visited, the graph is converted into
  //
  // n1
  // nX -> n2 -> GraphExport
  //
  // Since nX is created without any unvisited predecessors, it should not be visited.
  // n2 should be visited, however.
 
  using namespace jlm::rvsdg;
 
  jlm::rvsdg::Graph graph;
  auto type = jlm::rvsdg::TestType::createValueType();
 
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type });
  auto n2 = TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0) }, { type });
 
  jlm::rvsdg::GraphExport::Create(*n2->output(0), "dummy");
 
  // Act and assert
  jlm::rvsdg::TopDownTraverser trav(&graph.GetRootRegion());
  auto node = trav.next();
  EXPECT_EQ(node, n1);
 
  auto nX = TestOperation::createNode(&graph.GetRootRegion(), {}, { type });
  n1->output(0)->divert_users(nX->output(0));
 
  node = trav.next();
  EXPECT_EQ(node, n2);
 
  node = trav.next();
  EXPECT_EQ(node, nullptr);
}
 
TEST(TopDownTraverserTests, testMutating)
{
  using namespace jlm::rvsdg;
 
  auto test = [](jlm::rvsdg::Graph * graph,
                 jlm::rvsdg::Node * n1,
                 jlm::rvsdg::Node * n2,
                 jlm::rvsdg::Node * n3)
  {
    bool seen_n1 = false;
    bool seen_n2 = false;
    bool seen_n3 = false;
 
    for (const auto & tmp : jlm::rvsdg::TopDownTraverser(&graph->GetRootRegion()))
    {
      seen_n1 = seen_n1 || (tmp == n1);
      seen_n2 = seen_n2 || (tmp == n2);
      seen_n3 = seen_n3 || (tmp == n3);
      if (n3->input(0)->origin() == n1->output(0))
        n3->input(0)->divert_to(n2->output(0));
      else
        n3->input(0)->divert_to(n1->output(0));
    }
 
    EXPECT_TRUE(seen_n1);
    EXPECT_TRUE(seen_n2);
    EXPECT_TRUE(seen_n3);
  };
 
  jlm::rvsdg::Graph graph;
  auto type = jlm::rvsdg::TestType::createValueType();
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type });
  auto n2 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type });
  auto n3 = TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0) }, {});
 
  test(&graph, n1, n2, n3);
  test(&graph, n1, n2, n3);
}
 
TEST(TopDownTraverserTests, testReplacement)
{
  // Starts with a graph like
  // n1 -> n2 -> n3 -> n4 -> GraphExport
  //         \-> n5 -> GraphExport
  //
  // when n2 is visited, the graph is converted into
  //
  // n1 -> n2 -> n3
  //   \-> nX -> nY -> n4 -> GraphExport
  //         \-> n5 -> GraphExport
  //
  // Since nX and nY are new, they are not visited.
  // n3, n4 and n5 should be visited, however.
 
  using namespace jlm::rvsdg;
 
  jlm::rvsdg::Graph graph;
  auto type = jlm::rvsdg::TestType::createValueType();
 
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type });
  auto n2 = TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0) }, { type });
  auto n3 = TestOperation::createNode(&graph.GetRootRegion(), { n2->output(0) }, { type });
  auto n4 = TestOperation::createNode(&graph.GetRootRegion(), { n3->output(0) }, { type });
  auto n5 = TestOperation::createNode(&graph.GetRootRegion(), { n2->output(0) }, { type });
 
  jlm::rvsdg::GraphExport::Create(*n4->output(0), "dummy");
 
  // Act and assert
  jlm::rvsdg::TopDownTraverser trav(&graph.GetRootRegion());
  auto node = trav.next();
  EXPECT_EQ(node, n1);
 
  node = trav.next();
  EXPECT_EQ(node, n2);
  auto nX = TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0) }, { type });
  auto nY = TestOperation::createNode(&graph.GetRootRegion(), { nX->output(0) }, { type });
  n3->output(0)->divert_users(nY->output(0));
  n5->input(0)->divert_to(nX->output(0));
 
  auto next1 = trav.next();
  auto next2 = trav.next();
  auto next3 = trav.next();
  EXPECT_TRUE(n3 == next1 || n3 == next2 || n3 == next3);
  EXPECT_TRUE(n4 == next1 || n4 == next2 || n4 == next3);
  EXPECT_TRUE(n5 == next1 || n5 == next2 || n5 == next3);
 
  auto next4 = trav.next();
  EXPECT_EQ(next4, nullptr);
}
 
TEST(BottomUpTraverserTests, testInitialization)
{
  using namespace jlm::rvsdg;
 
  jlm::rvsdg::Graph graph;
  auto vtype = jlm::rvsdg::TestType::createValueType();
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, {});
  auto n2 = TestOperation::createNode(&graph.GetRootRegion(), {}, { vtype });
 
  jlm::rvsdg::GraphExport::Create(*n2->output(0), "dummy");
 
  bool n1_visited = false;
  bool n2_visited = false;
  for (const auto & node : jlm::rvsdg::BottomUpTraverser(&graph.GetRootRegion()))
  {
    if (node == n1)
      n1_visited = true;
    if (node == n2)
      n2_visited = true;
  }
 
  EXPECT_TRUE(n1_visited);
  EXPECT_TRUE(n2_visited);
}
 
TEST(BottomUpTraverserTests, testBasicTraversal)
{
  using namespace jlm::rvsdg;
 
  jlm::rvsdg::Graph graph;
  auto type = jlm::rvsdg::TestType::createValueType();
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type, type });
  auto n2 =
      TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0), n1->output(1) }, { type });
 
  jlm::rvsdg::GraphExport::Create(*n2->output(0), "dummy");
 
  {
    const jlm::rvsdg::Node * tmp = nullptr;
    jlm::rvsdg::BottomUpTraverser trav(&graph.GetRootRegion());
    tmp = trav.next();
    EXPECT_EQ(tmp, n2);
    tmp = trav.next();
    EXPECT_EQ(tmp, n1);
    tmp = trav.next();
    EXPECT_EQ(tmp, nullptr);
  }
}
 
TEST(BottomUpTraverserTests, testOrderEnforcement)
{
  using namespace jlm::rvsdg;
 
  jlm::rvsdg::Graph graph;
  auto type = jlm::rvsdg::TestType::createValueType();
  auto n1 = TestOperation::createNode(&graph.GetRootRegion(), {}, { type, type });
  auto n2 = TestOperation::createNode(&graph.GetRootRegion(), { n1->output(0) }, { type });
  auto n3 =
      TestOperation::createNode(&graph.GetRootRegion(), { n2->output(0), n1->output(1) }, { type });
 
  {
    const jlm::rvsdg::Node * tmp = nullptr;
    jlm::rvsdg::BottomUpTraverser trav(&graph.GetRootRegion());
 
    tmp = trav.next();
    EXPECT_EQ(tmp, n3);
    tmp = trav.next();
    EXPECT_EQ(tmp, n2);
    tmp = trav.next();
    EXPECT_EQ(tmp, n1);
    tmp = trav.next();
    EXPECT_EQ(tmp, nullptr);
  }
}