UnrollTests.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/RvsdgModule.hpp>
#include <jlm/llvm/opt/DeadNodeElimination.hpp>
#include <jlm/llvm/opt/unroll.hpp>
#include <jlm/rvsdg/bitstring/arithmetic.hpp>
#include <jlm/rvsdg/bitstring/comparison.hpp>
#include <jlm/rvsdg/bitstring/constant.hpp>
#include <jlm/rvsdg/gamma.hpp>
#include <jlm/rvsdg/TestOperations.hpp>
#include <jlm/rvsdg/theta.hpp>
#include <jlm/rvsdg/traverser.hpp>
#include <jlm/util/Statistics.hpp>
 
static jlm::util::StatisticsCollector statisticsCollector;
 
static size_t
nthetas(jlm::rvsdg::Region * region)
{
  size_t n = 0;
  for (const auto & node : region->Nodes())
  {
    if (dynamic_cast<const jlm::rvsdg::ThetaNode *>(&node))
      n++;
  }
 
  return n;
}
 
static jlm::rvsdg::ThetaNode *
create_theta(
    const jlm::rvsdg::BitCompareOperation & cop,
    const jlm::rvsdg::BitBinaryOperation & aop,
    jlm::rvsdg::Output * init,
    jlm::rvsdg::Output * step,
    jlm::rvsdg::Output * end)
{
  using namespace jlm::rvsdg;
 
  auto graph = init->region()->graph();
 
  auto theta = ThetaNode::create(&graph->GetRootRegion());
  auto subregion = theta->subregion();
  auto idv = theta->AddLoopVar(init);
  auto lvs = theta->AddLoopVar(step);
  auto lve = theta->AddLoopVar(end);
 
  auto arm = SimpleNode::Create(*subregion, aop.copy(), { idv.pre, lvs.pre }).output(0);
  auto cmp = SimpleNode::Create(*subregion, cop.copy(), { arm, lve.pre }).output(0);
  auto & matchNode = MatchOperation::CreateNode(*cmp, { { 1, 1 } }, 0, 2);
 
  idv.post->divert_to(arm);
  theta->set_predicate(matchNode.output(0));
 
  return theta;
}
 
TEST(LoopUnrollingTests, test_unrollinfo)
{
  auto bt32 = jlm::rvsdg::BitType::Create(32);
  jlm::rvsdg::bitslt_op slt(32);
  jlm::rvsdg::bitult_op ult(32);
  jlm::rvsdg::bitule_op ule(32);
  jlm::rvsdg::bitugt_op ugt(32);
  jlm::rvsdg::bitsge_op sge(32);
  jlm::rvsdg::biteq_op eq(32);
 
  jlm::rvsdg::bitadd_op add(32);
  jlm::rvsdg::bitsub_op sub(32);
 
  {
    jlm::rvsdg::Graph graph;
    auto x = &jlm::rvsdg::GraphImport::Create(graph, bt32, "x");
    auto theta = create_theta(slt, add, x, x, x);
    auto ui = jlm::llvm::LoopUnrollInfo::create(theta);
 
    EXPECT_NE(ui, nullptr);
    EXPECT_TRUE(ui->is_additive());
    EXPECT_FALSE(ui->is_subtractive());
    EXPECT_FALSE(ui->is_known());
    EXPECT_FALSE(ui->niterations());
    EXPECT_EQ(ui->theta(), theta);
    EXPECT_EQ(theta->MapPreLoopVar(*ui->idv()).input->origin(), x);
  }
 
  {
    jlm::rvsdg::Graph graph;
 
    auto init0 = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0 });
    auto init1 = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 1 });
    auto initm1 =
        &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0xFFFFFFFF });
 
    auto step1 = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 1 });
    auto step0 = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0 });
    auto stepm1 =
        &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0xFFFFFFFF });
    auto step2 = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 2 });
 
    auto end100 = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 100 });
 
    auto theta = create_theta(ult, add, init0, step1, end100);
    auto ui = jlm::llvm::LoopUnrollInfo::create(theta);
    EXPECT_TRUE(ui && *ui->niterations() == 100);
 
    theta = create_theta(ule, add, init0, step1, end100);
    ui = jlm::llvm::LoopUnrollInfo::create(theta);
    EXPECT_TRUE(ui && *ui->niterations() == 101);
 
    theta = create_theta(ugt, sub, end100, stepm1, init0);
    ui = jlm::llvm::LoopUnrollInfo::create(theta);
    EXPECT_TRUE(ui && *ui->niterations() == 100);
 
    theta = create_theta(sge, sub, end100, stepm1, init0);
    ui = jlm::llvm::LoopUnrollInfo::create(theta);
    EXPECT_TRUE(ui && *ui->niterations() == 101);
 
    theta = create_theta(ult, add, init0, step0, end100);
    ui = jlm::llvm::LoopUnrollInfo::create(theta);
    EXPECT_TRUE(ui && !ui->niterations());
 
    theta = create_theta(eq, add, initm1, step1, end100);
    ui = jlm::llvm::LoopUnrollInfo::create(theta);
    EXPECT_TRUE(ui && *ui->niterations() == 101);
 
    theta = create_theta(eq, add, init1, step2, end100);
    ui = jlm::llvm::LoopUnrollInfo::create(theta);
    EXPECT_TRUE(ui && !ui->niterations());
  }
}
 
TEST(LoopUnrollingTests, test_known_boundaries)
{
  jlm::rvsdg::bitult_op ult(32);
  jlm::rvsdg::bitsgt_op sgt(32);
  jlm::rvsdg::bitadd_op add(32);
  jlm::rvsdg::bitsub_op sub(32);
 
  {
    jlm::rvsdg::Graph graph;
 
    auto init = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0 });
    auto step = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 1 });
    auto end = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 4 });
 
    auto theta = create_theta(ult, add, init, step, end);
    //      jlm::rvsdg::view(graph, stdout);
    jlm::llvm::unroll(theta, 4);
    //      jlm::rvsdg::view(graph, stdout);
    /*
      The unroll factor is greater than or equal the number of iterations.
      The loop should be fully unrolled and the theta removed.
    */
    EXPECT_EQ(nthetas(&graph.GetRootRegion()), 0u);
  }
 
  {
    jlm::rvsdg::Graph graph;
 
    auto init = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0 });
    auto step = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 1 });
    auto end = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 100 });
 
    auto theta = create_theta(ult, add, init, step, end);
    //      jlm::rvsdg::view(graph, stdout);
    jlm::llvm::unroll(theta, 2);
    //      jlm::rvsdg::view(graph, stdout);
    /*
      The unroll factor is a multiple of the number of iterations.
      We should only find one (unrolled) theta.
    */
    EXPECT_EQ(nthetas(&graph.GetRootRegion()), 1u);
  }
 
  {
    jlm::rvsdg::Graph graph;
 
    auto init = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0 });
    auto step = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 1 });
    auto end = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 100 });
 
    auto theta = create_theta(ult, add, init, step, end);
    //      jlm::rvsdg::view(graph, stdout);
    jlm::llvm::unroll(theta, 3);
    //      jlm::rvsdg::view(graph, stdout);
    /*
      The unroll factor is NOT a multiple of the number of iterations
      and we have one remaining iteration. We should find only the
      unrolled theta and the body of the old theta as epilogue.
    */
    EXPECT_EQ(nthetas(&graph.GetRootRegion()), 1u);
  }
 
  {
    jlm::rvsdg::Graph graph;
 
    auto init = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 100 });
    auto step = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, -1 });
    auto end = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0 });
 
    auto theta = create_theta(sgt, sub, init, step, end);
    //      jlm::rvsdg::view(graph, stdout);
    jlm::llvm::unroll(theta, 6);
    //      jlm::rvsdg::view(graph, stdout);
    /*
      The unroll factor is NOT a multiple of the number of iterations
      and we have four remaining iterations. We should find two thetas:
      one unrolled theta and one theta for the residual iterations.
    */
    EXPECT_EQ(nthetas(&graph.GetRootRegion()), 2u);
  }
}
 
TEST(LoopUnrollingTests, test_unknown_boundaries)
{
  using namespace jlm::llvm;
  using namespace jlm::rvsdg;
 
  auto bt = jlm::rvsdg::BitType::Create(32);
  TestOperation op({ bt }, { bt });
 
  jlm::llvm::LlvmRvsdgModule rm(jlm::util::FilePath(""), "", "");
  auto & graph = rm.Rvsdg();
 
  auto x = &jlm::rvsdg::GraphImport::Create(graph, bt, "x");
  auto y = &jlm::rvsdg::GraphImport::Create(graph, bt, "y");
 
  auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
  auto lv1 = theta->AddLoopVar(x);
  auto lv2 = theta->AddLoopVar(y);
 
  auto one = &BitConstantOperation::create(*theta->subregion(), { 32, 1 });
  auto add = jlm::rvsdg::bitadd_op::create(32, lv1.pre, one);
  auto cmp = jlm::rvsdg::bitult_op::create(32, add, lv2.pre);
  auto & matchNode = MatchOperation::CreateNode(*cmp, { { 1, 0 } }, 1, 2);
 
  lv1.post->divert_to(add);
 
  theta->set_predicate(matchNode.output(0));
 
  auto & ex1 = GraphExport::Create(*lv1.output, "x");
 
  //    jlm::rvsdg::view(graph, stdout);
  jlm::llvm::LoopUnrolling loopunroll(2);
  loopunroll.Run(rm, statisticsCollector);
  //    jlm::rvsdg::view(graph, stdout);
 
  auto node = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::GammaNode>(*ex1.origin());
  EXPECT_NE(node, nullptr);
  node = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::GammaNode>(*node->input(1)->origin());
  EXPECT_NE(node, nullptr);
 
  /* Create cleaner output */
  DeadNodeElimination dne;
  dne.Run(rm, statisticsCollector);
  //    jlm::rvsdg::view(graph, stdout);
}
 
static std::vector<jlm::rvsdg::ThetaNode *>
find_thetas(jlm::rvsdg::Region * region)
{
  std::vector<jlm::rvsdg::ThetaNode *> thetas;
  for (auto & node : jlm::rvsdg::TopDownTraverser(region))
  {
    if (auto theta = dynamic_cast<jlm::rvsdg::ThetaNode *>(node))
      thetas.push_back(theta);
  }
 
  return thetas;
}
 
TEST(LoopUnrollingTests, test_nested_theta)
{
  jlm::llvm::LlvmRvsdgModule rm(jlm::util::FilePath(""), "", "");
  auto & graph = rm.Rvsdg();
 
  auto init = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 0 });
  auto step = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 1 });
  auto end = &jlm::rvsdg::BitConstantOperation::create(graph.GetRootRegion(), { 32, 97 });
 
  /* Outer loop */
  auto otheta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
 
  auto lvo_init = otheta->AddLoopVar(init);
  auto lvo_step = otheta->AddLoopVar(step);
  auto lvo_end = otheta->AddLoopVar(end);
 
  auto add = jlm::rvsdg::bitadd_op::create(32, lvo_init.pre, lvo_step.pre);
  auto compare = jlm::rvsdg::bitult_op::create(32, add, lvo_end.pre);
  auto & matchNode = jlm::rvsdg::MatchOperation::CreateNode(*compare, { { 1, 1 } }, 0, 2);
  otheta->set_predicate(matchNode.output(0));
  lvo_init.post->divert_to(add);
 
  /* First inner loop in the original loop */
  auto inner_theta = jlm::rvsdg::ThetaNode::create(otheta->subregion());
 
  auto inner_init = &jlm::rvsdg::BitConstantOperation::create(*otheta->subregion(), { 32, 0 });
  auto lvi_init = inner_theta->AddLoopVar(inner_init);
  auto lvi_step = inner_theta->AddLoopVar(lvo_step.pre);
  auto lvi_end = inner_theta->AddLoopVar(lvo_end.pre);
 
  auto inner_add = jlm::rvsdg::bitadd_op::create(32, lvi_init.pre, lvi_step.pre);
  auto inner_compare = jlm::rvsdg::bitult_op::create(32, inner_add, lvi_end.pre);
  auto & innerMatchNode =
      jlm::rvsdg::MatchOperation::CreateNode(*inner_compare, { { 1, 1 } }, 0, 2);
  inner_theta->set_predicate(innerMatchNode.output(0));
  lvi_init.post->divert_to(inner_add);
 
  /* Nested inner loop */
  auto inner_nested_theta = jlm::rvsdg::ThetaNode::create(inner_theta->subregion());
 
  auto inner_nested_init =
      &jlm::rvsdg::BitConstantOperation::create(*inner_theta->subregion(), { 32, 0 });
  auto lvi_nested_init = inner_nested_theta->AddLoopVar(inner_nested_init);
  auto lvi_nested_step = inner_nested_theta->AddLoopVar(lvi_step.pre);
  auto lvi_nested_end = inner_nested_theta->AddLoopVar(lvi_end.pre);
 
  auto inner_nested_add =
      jlm::rvsdg::bitadd_op::create(32, lvi_nested_init.pre, lvi_nested_step.pre);
  auto inner_nested_compare =
      jlm::rvsdg::bitult_op::create(32, inner_nested_add, lvi_nested_end.pre);
  auto & innerNestedMatchNode =
      jlm::rvsdg::MatchOperation::CreateNode(*inner_nested_compare, { { 1, 1 } }, 0, 2);
  inner_nested_theta->set_predicate(innerNestedMatchNode.output(0));
  lvi_nested_init.post->divert_to(inner_nested_add);
 
  /* Second inner loop in the original loop */
  auto inner2_theta = jlm::rvsdg::ThetaNode::create(otheta->subregion());
 
  auto inner2_init = &jlm::rvsdg::BitConstantOperation::create(*otheta->subregion(), { 32, 0 });
  auto lvi2_init = inner2_theta->AddLoopVar(inner2_init);
  auto lvi2_step = inner2_theta->AddLoopVar(lvo_step.pre);
  auto lvi2_end = inner2_theta->AddLoopVar(lvo_end.pre);
 
  auto inner2_add = jlm::rvsdg::bitadd_op::create(32, lvi2_init.pre, lvi2_step.pre);
  auto inner2_compare = jlm::rvsdg::bitult_op::create(32, inner2_add, lvi2_end.pre);
  auto & inner2MatchNode =
      jlm::rvsdg::MatchOperation::CreateNode(*inner2_compare, { { 1, 1 } }, 0, 2);
  inner2_theta->set_predicate(inner2MatchNode.output(0));
  lvi2_init.post->divert_to(inner2_add);
 
  //    jlm::rvsdg::view(graph, stdout);
  jlm::llvm::LoopUnrolling loopunroll(4);
  loopunroll.Run(rm, statisticsCollector);
  /*
    The outher theta should contain two inner thetas
  */
  EXPECT_EQ(nthetas(otheta->subregion()), 2u);
  /*
    The outer theta should not be unrolled and since the
    original graph contains 7 nodes and the unroll factor
    is 4 an unrolled theta should have around 28 nodes. So
    we check for less than 20 nodes in case an updated
    unroll algorithm would hoist code from the inner
    thetas.
  */
  EXPECT_LE(otheta->subregion()->numNodes(), 20u);
  /*
    The inner theta should not be unrolled and since the
    original graph contains 5 nodes and the unroll factor
    is 4 an unrolled theta should have around 20 nodes. So
    we check for less than 15 nodes in case an updated
    unroll algorithm would hoist code from the inner
    thetas.
  */
  EXPECT_LE(inner_theta->subregion()->numNodes(), 15u);
  /*
    The innermost theta should be unrolled and since the
    original graph contains 3 nodes and the unroll factor
    is 4 an unrolled theta should have around 12 nodes. So
    we check for more than 7 nodes in case an updated
    unroll algorithm would hoist code from the inner
    thetas.
  */
  auto thetas = find_thetas(inner_theta->subregion());
  EXPECT_EQ(thetas.size(), 1u);
  EXPECT_GE(thetas[0]->subregion()->numNodes(), 7u);
  /*
    The second inner theta should be unrolled and since
    the original graph contains 3 nodes and the unroll
    factor is 4 an unrolled theta should have around 12
    nodes. So we check for less than 7 nodes in case an
    updated unroll algorithm would hoist code from the
    innner thetas.
  */
  thetas = find_thetas(otheta->subregion());
  EXPECT_EQ(thetas.size(), 2u);
  EXPECT_GE(thetas[1]->subregion()->numNodes(), 7u);
  //    jlm::rvsdg::view(graph, stdout);
  jlm::llvm::unroll(otheta, 4);
  //    jlm::rvsdg::view(graph, stdout);
  /*
    After unrolling the outher theta four times it should
    now contain 8 thetas.
  */
  thetas = find_thetas(&graph.GetRootRegion());
  EXPECT_EQ(thetas.size(), 3u);
  EXPECT_EQ(nthetas(thetas[0]->subregion()), 8u);
}