AggregationTests.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/llvm/ir/aggregation.hpp>
#include <jlm/llvm/ir/ipgraph-module.hpp>
#include <jlm/llvm/ir/print.hpp>
 
static bool
is_entry(const jlm::llvm::AggregationNode * node)
{
  return jlm::llvm::is<jlm::llvm::EntryAggregationNode>(node) && node->nchildren() == 0;
}
 
static bool
is_exit(const jlm::llvm::AggregationNode * node)
{
  return jlm::llvm::is<jlm::llvm::ExitAggregationNode>(node) && node->nchildren() == 0;
}
 
static bool
is_block(const jlm::llvm::AggregationNode * node)
{
  return jlm::llvm::is<jlm::llvm::BasicBlockAggregationNode>(node) && node->nchildren() == 0;
}
 
static bool
is_linear(const jlm::llvm::AggregationNode * node, size_t nchildren)
{
  if (!jlm::llvm::is<jlm::llvm::LinearAggregationNode>(node))
    return false;
 
  if (node->nchildren() != nchildren)
    return false;
 
  for (auto & child : *node)
  {
    if (child.parent() != node)
      return false;
  }
 
  return true;
}
 
static bool
is_loop(const jlm::llvm::AggregationNode * node)
{
  return jlm::llvm::is<jlm::llvm::LoopAggregationNode>(node) && node->nchildren() == 1
      && node->child(0)->parent() == node;
}
 
static bool
is_branch(const jlm::llvm::AggregationNode * node, size_t nchildren)
{
  if (!jlm::llvm::is<jlm::llvm::BranchAggregationNode>(node))
    return false;
 
  if (node->nchildren() != nchildren)
    return false;
 
  for (auto & child : *node)
  {
    if (child.parent() != node)
      return false;
  }
 
  return true;
}
 
TEST(ViewTests, test_linear_reduction)
{
  using namespace jlm::llvm;
 
  auto setup_cfg = [](jlm::llvm::InterProceduralGraphModule & module)
  {
    auto cfg = ControlFlowGraph::create(module);
 
    auto bb = jlm::llvm::BasicBlock::create(*cfg);
    cfg->exit()->divert_inedges(bb);
    bb->add_outedge(cfg->exit());
 
    return cfg;
  };
 
  auto verify_aggtree = [](const jlm::llvm::AggregationNode & root)
  {
    EXPECT_TRUE(is_linear(&root, 3));
    {
      EXPECT_TRUE(is_entry(root.child(0)));
      EXPECT_TRUE(is_block(root.child(1)));
      EXPECT_TRUE(is_exit(root.child(2)));
    }
  };
 
  jlm::llvm::InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
  auto cfg = setup_cfg(module);
 
  auto root = jlm::llvm::aggregate(*cfg);
  jlm::llvm::AggregationNode::normalize(*root);
  jlm::llvm::print(*root, stdout);
 
  verify_aggtree(*root);
}
 
TEST(ViewTests, test_loop_reduction)
{
  using namespace jlm::llvm;
 
  auto setup_cfg = [](jlm::llvm::InterProceduralGraphModule & module)
  {
    auto cfg = ControlFlowGraph::create(module);
 
    auto bb1 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb2 = jlm::llvm::BasicBlock::create(*cfg);
 
    cfg->exit()->divert_inedges(bb1);
    bb1->add_outedge(bb2);
    bb2->add_outedge(cfg->exit());
    bb2->add_outedge(bb1);
 
    return cfg;
  };
 
  auto verify_aggtree = [](const jlm::llvm::AggregationNode & root)
  {
    EXPECT_TRUE(is_linear(&root, 3));
    {
      EXPECT_TRUE(is_entry(root.child(0)));
 
      auto loop = root.child(1);
      EXPECT_TRUE(is_loop(loop));
      {
        auto linear = loop->child(0);
        EXPECT_TRUE(is_linear(linear, 2));
        {
          EXPECT_TRUE(is_block(linear->child(0)));
          EXPECT_TRUE(is_block(linear->child(1)));
        }
      }
 
      EXPECT_TRUE(is_exit(root.child(2)));
    }
  };
 
  jlm::llvm::InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
  auto cfg = setup_cfg(module);
 
  auto root = jlm::llvm::aggregate(*cfg);
  jlm::llvm::AggregationNode::normalize(*root);
  jlm::llvm::print(*root, stdout);
 
  verify_aggtree(*root);
}
 
TEST(ViewTests, test_branch_reduction)
{
  using namespace jlm::llvm;
 
  auto setup_cfg = [](jlm::llvm::InterProceduralGraphModule & module)
  {
    auto cfg = ControlFlowGraph::create(module);
 
    auto split = jlm::llvm::BasicBlock::create(*cfg);
    auto bb1 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb2 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb3 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb4 = jlm::llvm::BasicBlock::create(*cfg);
    auto join = jlm::llvm::BasicBlock::create(*cfg);
 
    cfg->exit()->divert_inedges(split);
    split->add_outedge(bb1);
    split->add_outedge(bb3);
    bb1->add_outedge(bb2);
    bb2->add_outedge(join);
    bb3->add_outedge(bb4);
    bb4->add_outedge(join);
    join->add_outedge(cfg->exit());
 
    return cfg;
  };
 
  auto verify_aggtree = [](const jlm::llvm::AggregationNode & root)
  {
    EXPECT_TRUE(is_linear(&root, 5));
    {
      EXPECT_TRUE(is_entry(root.child(0)));
      EXPECT_TRUE(is_block(root.child(1)));
 
      auto branch = root.child(2);
      EXPECT_TRUE(is_branch(branch, 2));
      {
        auto linear = branch->child(0);
        EXPECT_TRUE(is_linear(linear, 2));
        {
          EXPECT_TRUE(is_block(linear->child(0)));
          EXPECT_TRUE(is_block(linear->child(1)));
        }
 
        linear = branch->child(1);
        EXPECT_TRUE(is_linear(linear, 2));
        {
          EXPECT_TRUE(is_block(linear->child(0)));
          EXPECT_TRUE(is_block(linear->child(1)));
        }
      }
 
      EXPECT_TRUE(is_block(root.child(3)));
      EXPECT_TRUE(is_exit(root.child(4)));
    }
  };
 
  jlm::llvm::InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
  auto cfg = setup_cfg(module);
 
  auto root = jlm::llvm::aggregate(*cfg);
  jlm::llvm::AggregationNode::normalize(*root);
  jlm::llvm::print(*root, stdout);
 
  verify_aggtree(*root);
}
 
TEST(ViewTests, test_branch_loop_reduction)
{
  using namespace jlm::llvm;
 
  auto setup_cfg = [](jlm::llvm::InterProceduralGraphModule & module)
  {
    auto cfg = ControlFlowGraph::create(module);
    auto split = jlm::llvm::BasicBlock::create(*cfg);
    auto bb1 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb2 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb3 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb4 = jlm::llvm::BasicBlock::create(*cfg);
    auto join = jlm::llvm::BasicBlock::create(*cfg);
 
    cfg->exit()->divert_inedges(split);
    split->add_outedge(bb1);
    split->add_outedge(bb3);
    bb1->add_outedge(bb2);
    bb2->add_outedge(join);
    bb2->add_outedge(bb1);
    bb3->add_outedge(bb4);
    bb4->add_outedge(join);
    bb4->add_outedge(bb3);
    join->add_outedge(cfg->exit());
 
    return cfg;
  };
 
  auto verify_aggtree = [](const jlm::llvm::AggregationNode & root)
  {
    EXPECT_TRUE(is_linear(&root, 5));
    {
      EXPECT_TRUE(is_entry(root.child(0)));
      EXPECT_TRUE(is_block(root.child(1)));
 
      auto branch = root.child(2);
      EXPECT_TRUE(is_branch(branch, 2));
      {
        auto loop = branch->child(0);
        EXPECT_TRUE(is_loop(loop));
        {
          auto linear = loop->child(0);
          EXPECT_TRUE(is_linear(linear, 2));
          {
            EXPECT_TRUE(is_block(linear->child(0)));
            EXPECT_TRUE(is_block(linear->child(1)));
          }
        }
 
        loop = branch->child(1);
        EXPECT_TRUE(is_loop(loop));
        {
          auto linear = loop->child(0);
          EXPECT_TRUE(is_linear(linear, 2));
          {
            EXPECT_TRUE(is_block(linear->child(0)));
            EXPECT_TRUE(is_block(linear->child(1)));
          }
        }
      }
 
      EXPECT_TRUE(is_block(root.child(3)));
      EXPECT_TRUE(is_exit(root.child(4)));
    }
  };
 
  jlm::llvm::InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
  auto cfg = setup_cfg(module);
 
  auto root = jlm::llvm::aggregate(*cfg);
  jlm::llvm::AggregationNode::normalize(*root);
  jlm::llvm::print(*root, stdout);
 
  verify_aggtree(*root);
}
 
TEST(ViewTests, test_loop_branch_reduction)
{
  using namespace jlm::llvm;
 
  auto setup_cfg = [](jlm::llvm::InterProceduralGraphModule & module)
  {
    auto cfg = ControlFlowGraph::create(module);
 
    auto split = jlm::llvm::BasicBlock::create(*cfg);
    auto bb1 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb2 = jlm::llvm::BasicBlock::create(*cfg);
    auto join = jlm::llvm::BasicBlock::create(*cfg);
    auto bb3 = jlm::llvm::BasicBlock::create(*cfg);
 
    cfg->exit()->divert_inedges(split);
    split->add_outedge(bb1);
    split->add_outedge(bb2);
    bb1->add_outedge(join);
    bb2->add_outedge(join);
    join->add_outedge(bb3);
    bb3->add_outedge(cfg->exit());
    bb3->add_outedge(split);
 
    return cfg;
  };
 
  auto verify_aggtree = [](const jlm::llvm::AggregationNode & root)
  {
    EXPECT_TRUE(is_linear(&root, 3));
    {
      EXPECT_TRUE(is_entry(root.child(0)));
 
      auto loop = root.child(1);
      EXPECT_TRUE(is_loop(loop));
      {
        auto linear = loop->child(0);
        EXPECT_TRUE(is_linear(linear, 4));
        {
          EXPECT_TRUE(is_block(linear->child(0)));
 
          auto branch = linear->child(1);
          EXPECT_TRUE(is_branch(branch, 2));
          {
            EXPECT_TRUE(is_block(branch->child(0)));
            EXPECT_TRUE(is_block(branch->child(1)));
          }
 
          EXPECT_TRUE(is_block(linear->child(2)));
          EXPECT_TRUE(is_block(linear->child(3)));
        }
      }
 
      EXPECT_TRUE(is_exit(root.child(2)));
    }
  };
 
  jlm::llvm::InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
  auto cfg = setup_cfg(module);
 
  auto root = jlm::llvm::aggregate(*cfg);
  jlm::llvm::AggregationNode::normalize(*root);
  jlm::llvm::print(*root, stdout);
 
  verify_aggtree(*root);
}
 
TEST(ViewTests, test_ifthen_reduction)
{
  using namespace jlm::llvm;
 
  auto setup_cfg = [](jlm::llvm::InterProceduralGraphModule & module)
  {
    auto cfg = ControlFlowGraph::create(module);
 
    auto split = jlm::llvm::BasicBlock::create(*cfg);
    auto bb1 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb2 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb3 = jlm::llvm::BasicBlock::create(*cfg);
    auto join = jlm::llvm::BasicBlock::create(*cfg);
 
    cfg->exit()->divert_inedges(split);
    split->add_outedge(bb3);
    split->add_outedge(bb1);
    bb1->add_outedge(bb2);
    bb2->add_outedge(join);
    bb3->add_outedge(join);
    join->add_outedge(cfg->exit());
 
    return cfg;
  };
 
  auto verify_aggtree = [](const jlm::llvm::AggregationNode & root)
  {
    EXPECT_TRUE(is_linear(&root, 5));
    {
      EXPECT_TRUE(is_entry(root.child(0)));
      EXPECT_TRUE(is_block(root.child(1)));
 
      auto branch = root.child(2);
      EXPECT_TRUE(is_branch(branch, 2));
      {
        EXPECT_TRUE(is_block(branch->child(0)));
 
        auto linear = branch->child(1);
        EXPECT_TRUE(is_linear(linear, 2));
        {
          EXPECT_TRUE(is_block(linear->child(0)));
          EXPECT_TRUE(is_block(linear->child(1)));
        }
      }
 
      EXPECT_TRUE(is_block(root.child(3)));
      EXPECT_TRUE(is_exit(root.child(4)));
    }
  };
 
  jlm::llvm::InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
  auto cfg = setup_cfg(module);
 
  auto root = jlm::llvm::aggregate(*cfg);
  jlm::llvm::AggregationNode::normalize(*root);
  jlm::llvm::print(*root, stdout);
 
  verify_aggtree(*root);
}
 
TEST(AggregationTests, test_branch_and_loop)
{
  using namespace jlm::llvm;
 
  auto setup_cfg = [](jlm::llvm::InterProceduralGraphModule & module)
  {
    auto cfg = ControlFlowGraph::create(module);
 
    auto split = jlm::llvm::BasicBlock::create(*cfg);
    auto bb1 = jlm::llvm::BasicBlock::create(*cfg);
    auto bb2 = jlm::llvm::BasicBlock::create(*cfg);
    auto loop = jlm::llvm::BasicBlock::create(*cfg);
 
    cfg->exit()->divert_inedges(split);
    split->add_outedge(bb1);
    split->add_outedge(bb2);
    bb1->add_outedge(loop);
    bb2->add_outedge(loop);
    loop->add_outedge(cfg->exit());
    loop->add_outedge(loop);
 
    return cfg;
  };
 
  auto verify_aggtree = [](const jlm::llvm::AggregationNode & root)
  {
    EXPECT_TRUE(is_linear(&root, 5));
    {
      EXPECT_TRUE(is_entry(root.child(0)));
      EXPECT_TRUE(is_block(root.child(1)));
 
      auto branch = root.child(2);
      EXPECT_TRUE(is_branch(branch, 2));
      {
        EXPECT_TRUE(is_block(branch->child(0)));
        EXPECT_TRUE(is_block(branch->child(1)));
      }
 
      auto loop = root.child(3);
      EXPECT_TRUE(is_loop(loop));
      {
        EXPECT_TRUE(is_block(loop->child(0)));
      }
 
      EXPECT_TRUE(is_exit(root.child(4)));
    }
  };
 
  jlm::llvm::InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
  auto cfg = setup_cfg(module);
 
  auto root = jlm::llvm::aggregate(*cfg);
  jlm::llvm::AggregationNode::normalize(*root);
  jlm::llvm::print(*root, stdout);
 
  verify_aggtree(*root);
}