aggregation.cpp

Go to the documentation of this file.

/*
 * Copyright 2017 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#include <jlm/llvm/ir/aggregation.hpp>
#include <jlm/llvm/ir/cfg-structure.hpp>
 
#include <deque>
#include <functional>
#include <unordered_map>
 
namespace jlm::llvm
{
 
AggregationNode::~AggregationNode() noexcept = default;
 
void
AggregationNode::normalize(AggregationNode & node)
{
  std::function<std::vector<std::unique_ptr<AggregationNode>>(AggregationNode &)> reduce =
      [&](AggregationNode & node)
  {
    JLM_ASSERT(is<LinearAggregationNode>(&node));
 
    std::vector<std::unique_ptr<AggregationNode>> children;
    for (size_t n = 0; n < node.children_.size(); n++)
    {
      auto & child = node.children_[n];
 
      if (is<LinearAggregationNode>(child.get()))
      {
        auto tmp = reduce(*child);
        std::move(tmp.begin(), tmp.end(), std::back_inserter(children));
      }
      else
      {
        children.push_back(std::move(child));
      }
    }
 
    return children;
  };
 
  if (is<LinearAggregationNode>(&node))
  {
    auto children = reduce(node);
 
    node.remove_children();
    for (auto & child : children)
      node.add_child(std::move(child));
  }
 
  for (auto & child : node)
    normalize(child);
}
 
EntryAggregationNode::~EntryAggregationNode() noexcept = default;
 
EntryAggregationNode::constiterator
EntryAggregationNode::begin() const
{
  return constiterator(arguments_.begin());
}
 
EntryAggregationNode::constiterator
EntryAggregationNode::end() const
{
  return constiterator(arguments_.end());
}
 
std::string
EntryAggregationNode::debug_string() const
{
  return "entry";
}
 
ExitAggregationNode::~ExitAggregationNode() noexcept = default;
 
std::string
ExitAggregationNode::debug_string() const
{
  return "exit";
}
 
BasicBlockAggregationNode::~BasicBlockAggregationNode() noexcept = default;
 
std::string
BasicBlockAggregationNode::debug_string() const
{
  return "block";
}
 
LinearAggregationNode::~LinearAggregationNode() noexcept = default;
 
std::string
LinearAggregationNode::debug_string() const
{
  return "linear";
}
 
BranchAggregationNode::~BranchAggregationNode() noexcept = default;
 
std::string
BranchAggregationNode::debug_string() const
{
  return "branch";
}
 
LoopAggregationNode::~LoopAggregationNode() noexcept = default;
 
std::string
LoopAggregationNode::debug_string() const
{
  return "loop";
}
 
class AggregationMap final
{
public:
  bool
  contains(ControlFlowGraphNode * node) const
  {
    return map_.find(node) != map_.end();
  }
 
  std::unique_ptr<AggregationNode> &
  lookup(ControlFlowGraphNode * node)
  {
    JLM_ASSERT(contains(node));
 
    return map_.at(node);
  }
 
  void
  insert(ControlFlowGraphNode * node, std::unique_ptr<AggregationNode> anode)
  {
    map_[node] = std::move(anode);
  }
 
  void
  remove(ControlFlowGraphNode * node)
  {
    map_.erase(node);
  }
 
  static std::unique_ptr<AggregationMap>
  create(ControlFlowGraph & cfg)
  {
    auto exit = cfg.exit();
    auto entry = cfg.entry();
    auto map = std::make_unique<AggregationMap>();
 
    map->map_[entry] = EntryAggregationNode::create(entry->arguments());
    map->map_[exit] = ExitAggregationNode::create(exit->results());
    for (auto & node : cfg)
    {
      auto bb = static_cast<BasicBlock *>(&node);
      map->map_[&node] = BasicBlockAggregationNode::create(std::move(bb->tacs()));
    }
 
    return map;
  }
 
private:
  std::unordered_map<ControlFlowGraphNode *, std::unique_ptr<AggregationNode>> map_;
};
 
static bool
is_sese_basic_block(const ControlFlowGraphNode * node) noexcept
{
  return node->NumInEdges() == 1 && node->NumOutEdges() == 1;
}
 
static bool
is_branch_split(const ControlFlowGraphNode * node) noexcept
{
  return node->NumOutEdges() > 1;
}
 
static bool
is_branch_join(const ControlFlowGraphNode * node) noexcept
{
  return node->NumInEdges() > 1;
}
 
static bool
is_branch(const ControlFlowGraphNode * split) noexcept
{
  if (split->NumOutEdges() < 2)
    return false;
 
  if (split->OutEdge(0)->sink()->NumOutEdges() != 1)
    return false;
 
  auto join = split->OutEdge(0)->sink()->OutEdge(0)->sink();
  for (auto & edge : split->OutEdges())
  {
    if (edge.sink()->NumInEdges() != 1)
      return false;
    if (edge.sink()->NumOutEdges() != 1)
      return false;
    if (edge.sink()->OutEdge(0)->sink() != join)
      return false;
  }
 
  return true;
}
 
static bool
is_linear(const ControlFlowGraphNode * node) noexcept
{
  if (node->NumOutEdges() != 1)
    return false;
 
  auto exit = node->OutEdge(0)->sink();
  if (exit->NumInEdges() != 1)
    return false;
 
  return true;
}
 
static ControlFlowGraphNode *
aggregate(ControlFlowGraphNode *, ControlFlowGraphNode *, AggregationMap &);
 
static void
reduceLoop(const StronglyConnectedComponentStructure & sccStruct, AggregationMap & map)
{
  JLM_ASSERT(sccStruct.IsTailControlledLoop());
 
  const auto entryNode = *sccStruct.EntryNodes().begin();
  const auto exitNode = (*sccStruct.ExitEdges().begin())->source();
 
  const auto repetitionEdge = *sccStruct.RepetitionEdges().begin();
  // The RVSDG theta node always expects that the repetition of its body happens on control value 1.
  JLM_ASSERT(repetitionEdge->index() == 1);
  repetitionEdge->source()->remove_outedge(repetitionEdge->index());
 
  const auto seseNode = aggregate(entryNode, exitNode, map);
  auto loop = LoopAggregationNode::create(std::move(map.lookup(seseNode)));
  map.insert(seseNode, std::move(loop));
}
 
static ControlFlowGraphNode *
reduce_branch(ControlFlowGraphNode * split, ControlFlowGraphNode ** entry, AggregationMap & map)
{
  /* sanity checks */
  JLM_ASSERT(split->NumOutEdges() > 1);
  JLM_ASSERT(split->OutEdge(0)->sink()->NumOutEdges() == 1);
  JLM_ASSERT(map.contains(split));
 
  auto join = split->OutEdge(0)->sink()->OutEdge(0)->sink();
  for (auto & edge : split->OutEdges())
  {
    JLM_ASSERT(edge.sink()->NumInEdges() == 1);
    JLM_ASSERT(map.contains(edge.sink()));
    JLM_ASSERT(edge.sink()->NumOutEdges() == 1);
    JLM_ASSERT(edge.sink()->OutEdge(0)->sink() == join);
  }
 
  /* perform reduction */
  auto sese = BasicBlock::create(split->cfg());
  split->divert_inedges(sese);
  sese->add_outedge(join);
 
  auto branch = BranchAggregationNode::create();
  for (auto & edge : split->OutEdges())
  {
    edge.sink()->remove_outedge(0);
    branch->add_child(std::move(map.lookup(edge.sink())));
    map.remove(edge.sink());
  }
 
  auto & child = map.lookup(split);
  map.insert(sese, LinearAggregationNode::create(std::move(child), std::move(branch)));
  map.remove(split);
 
  /*
    We need to adjust the SEE subgraphs' entry, in case it was the same as the split and we just
    reduced it. We do not have to adjust the SESE subgraphs' exit node, as the branch join is not
    reduced in this function.
  */
  *entry = split == *entry ? sese : *entry;
  return sese;
}
 
static ControlFlowGraphNode *
reduce_linear(
    ControlFlowGraphNode * source,
    ControlFlowGraphNode ** entry,
    ControlFlowGraphNode ** exit,
    AggregationMap & map)
{
  JLM_ASSERT(is_linear(source));
  auto sink = source->OutEdge(0)->sink();
 
  auto sese = BasicBlock::create(source->cfg());
  source->divert_inedges(sese);
  for (auto & edge : sink->OutEdges())
    sese->add_outedge(edge.sink());
  sink->remove_outedges();
 
  auto child0 = std::move(map.lookup(source));
  auto child1 = std::move(map.lookup(sink));
  map.insert(sese, LinearAggregationNode::create(std::move(child0), std::move(child1)));
  map.remove(source);
  map.remove(sink);
 
  /*
    We need to adjust the SESE subgraphs' entry and exit, in case we have just reduced either of
    them.
  */
  *entry = source == *entry ? sese : *entry;
  *exit = sink == *exit ? sese : *exit;
 
  return sese;
}
 
static void
aggregate_loops(ControlFlowGraphNode * entry, ControlFlowGraphNode * exit, AggregationMap & map)
{
  auto sccs = find_sccs(entry, exit);
  for (auto scc : sccs)
  {
    auto sccStructure = StronglyConnectedComponentStructure::Create(scc);
 
    if (sccStructure->IsTailControlledLoop())
    {
      reduceLoop(*sccStructure, map);
      continue;
    }
 
    JLM_UNREACHABLE("We should have never reached this point!");
  }
}
 
static void
aggregate_acyclic_sese(
    ControlFlowGraphNode * node,
    ControlFlowGraphNode ** entry,
    ControlFlowGraphNode ** exit,
    AggregationMap & map)
{
  /*
    We reduced the entire subgraph to a single node. We are done here.
  */
  if (*entry == *exit)
  {
    JLM_ASSERT(node == *entry);
    return;
  }
 
  /*
    We traversed the entire subgraph until the end. Turn around.
  */
  if (node == *exit)
    return;
 
  /*
    Reduce linear subgraph
  */
  if (is_linear(node))
  {
    auto sese = reduce_linear(node, entry, exit, map);
    aggregate_acyclic_sese(sese, entry, exit, map);
    return;
  }
 
  /*
    Reduce branch subgraph
  */
  if (is_branch_split(node))
  {
    /*
      First, greedily reduce all branches of the branch subgraph...
    */
    for (auto & edge : node->OutEdges())
      aggregate_acyclic_sese(edge.sink(), entry, exit, map);
 
    /*
      ..., then try to reduce the branch subgraph itself.
    */
    if (is_branch(node))
    {
      auto sese = reduce_branch(node, entry, map);
      aggregate_acyclic_sese(sese, entry, exit, map);
      return;
    }
 
    JLM_UNREACHABLE("We should have never reached this point!");
  }
 
  /*
    It is only a single basic block with one incoming and outgoing edge, simply step over it.
  */
  if (is_sese_basic_block(node))
  {
    aggregate_acyclic_sese(node->OutEdge(0)->sink(), entry, exit, map);
    return;
  }
 
  /*
    It is a branch join, turn around to the branch split such that we can reduce it.
  */
  if (is_branch_join(node))
    return;
 
  JLM_UNREACHABLE("We should have never reached this point!");
}
 
static ControlFlowGraphNode *
aggregate(ControlFlowGraphNode * entry, ControlFlowGraphNode * exit, AggregationMap & map)
{
  aggregate_loops(entry, exit, map);
  aggregate_acyclic_sese(entry, &entry, &exit, map);
  JLM_ASSERT(entry == exit);
 
  return entry;
}
 
std::unique_ptr<AggregationNode>
aggregate(ControlFlowGraph & cfg)
{
  JLM_ASSERT(is_proper_structured(cfg));
 
  auto map = AggregationMap::create(cfg);
  auto root = aggregate(cfg.entry(), cfg.exit(), *map);
 
  return std::move(map->lookup(root));
}
 
size_t
ntacs(const AggregationNode & root)
{
  size_t n = 0;
  for (auto & child : root)
    n += ntacs(child);
 
  if (auto bb = dynamic_cast<const BasicBlockAggregationNode *>(&root))
    n += bb->tacs().ntacs();
 
  return n;
}
 
}