node.cpp

Go to the documentation of this file.

/*
 * Copyright 2010 2011 2012 2014 2015 Helge Bahmann <hcb@chaoticmind.net>
 * Copyright 2012 2013 2014 2015 2016 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#include <jlm/rvsdg/delta.hpp>
#include <jlm/rvsdg/gamma.hpp>
#include <jlm/rvsdg/lambda.hpp>
#include <jlm/rvsdg/MatchType.hpp>
#include <jlm/rvsdg/Phi.hpp>
#include <jlm/rvsdg/region.hpp>
#include <jlm/rvsdg/substitution.hpp>
#include <jlm/rvsdg/theta.hpp>
 
namespace jlm::rvsdg
{
 
Input::~Input() noexcept
{
  origin()->remove_user(this);
}
 
void
Input::CheckTypes(
    const Region & region,
    const Output & origin,
    const std::shared_ptr<const rvsdg::Type> & type)
{
  if (&region != origin.region())
    throw util::Error("Invalid operand region.");
 
  if (*type != *origin.Type())
    throw util::TypeError(type->debug_string(), origin.Type()->debug_string());
}
 
Input::Input(rvsdg::Node & owner, rvsdg::Output & origin, std::shared_ptr<const rvsdg::Type> type)
    : index_(0),
      Owner_(&owner),
      Type_(std::move(type)),
      UsersList_()
{
  CheckTypes(*owner.region(), origin, Type_);
  origin.add_user(this);
}
 
Input::Input(rvsdg::Region & owner, rvsdg::Output & origin, std::shared_ptr<const rvsdg::Type> type)
    : index_(0),
      Owner_(&owner),
      Type_(std::move(type)),
      UsersList_()
{
  CheckTypes(owner, origin, Type_);
  origin.add_user(this);
}
 
std::string
Input::debug_string() const
{
  return jlm::util::strfmt("i", index());
}
 
void
Input::divert_to(jlm::rvsdg::Output * new_origin)
{
  if (origin() == new_origin)
    return;
 
  if (*Type() != *new_origin->Type())
    throw jlm::util::TypeError(Type()->debug_string(), new_origin->Type()->debug_string());
 
  if (region() != new_origin->region())
    throw util::Error("Invalid operand region.");
 
  auto old_origin = origin();
  old_origin->remove_user(this);
  new_origin->add_user(this);
 
  region()->notifyInputChange(this, old_origin, new_origin);
}
 
[[nodiscard]] rvsdg::Region *
Input::region() const noexcept
{
  if (auto node = std::get_if<Node *>(&Owner_))
  {
    return (*node)->region();
  }
  else if (auto region = std::get_if<Region *>(&Owner_))
  {
    return *region;
  }
  else
  {
    JLM_UNREACHABLE("Unhandled owner case.");
  }
}
 
static Input *
ComputeNextInput(const Input * input)
{
  if (input == nullptr)
    return nullptr;
 
  const auto index = input->index();
  auto owner = input->GetOwner();
 
  if (auto node = std::get_if<Node *>(&owner))
  {
    return index + 1 < (*node)->ninputs() ? (*node)->input(index + 1) : nullptr;
  }
 
  if (auto region = std::get_if<Region *>(&owner))
  {
    return index + 1 < (*region)->nresults() ? (*region)->result(index + 1) : nullptr;
  }
 
  JLM_UNREACHABLE("Unhandled owner case.");
}
 
Input *
Input::Iterator::ComputeNext() const
{
  return ComputeNextInput(Input_);
}
 
Input *
Input::ConstIterator::ComputeNext() const
{
  return ComputeNextInput(Input_);
}
 
Output::~Output() noexcept
{
  JLM_ASSERT(NumUsers_ == 0);
}
 
Output::Output(Node & owner, std::shared_ptr<const rvsdg::Type> type)
    : index_(0),
      Owner_(&owner),
      Type_(std::move(type))
{}
 
Output::Output(rvsdg::Region * owner, std::shared_ptr<const rvsdg::Type> type)
    : index_(0),
      Owner_(owner),
      Type_(std::move(type))
{}
 
[[nodiscard]] rvsdg::Region *
Output::region() const noexcept
{
  if (auto node = std::get_if<Node *>(&Owner_))
  {
    return (*node)->region();
  }
  else if (auto region = std::get_if<Region *>(&Owner_))
  {
    return *region;
  }
  else
  {
    JLM_UNREACHABLE("Unhandled owner case.");
  }
}
 
std::string
Output::debug_string() const
{
  return jlm::util::strfmt("o", index());
}
 
void
Output::remove_user(jlm::rvsdg::Input * user)
{
  JLM_ASSERT(user->origin_ == this);
  user->origin_ = nullptr;
 
  Users_.erase(user);
  NumUsers_ -= 1;
 
  if (auto node = TryGetOwnerNode<Node>(*this))
  {
    node->numSuccessors_ -= 1;
    if (node->IsDead())
    {
      region()->onBottomNodeAdded(*node);
    }
  }
}
 
void
Output::add_user(jlm::rvsdg::Input * user)
{
  JLM_ASSERT(user->origin_ == nullptr);
  user->origin_ = this;
 
  if (auto node = TryGetOwnerNode<Node>(*this))
  {
    if (node->IsDead())
    {
      region()->onBottomNodeRemoved(*node);
    }
    node->numSuccessors_ += 1;
  }
 
  Users_.push_back(user);
  NumUsers_ += 1;
}
 
static Output *
ComputeNextOutput(const Output * output)
{
  if (output == nullptr)
    return nullptr;
 
  const auto index = output->index();
  const auto owner = output->GetOwner();
 
  if (const auto node = std::get_if<Node *>(&owner))
  {
    return index + 1 < (*node)->noutputs() ? (*node)->output(index + 1) : nullptr;
  }
 
  if (const auto region = std::get_if<Region *>(&owner))
  {
    return index + 1 < (*region)->narguments() ? (*region)->argument(index + 1) : nullptr;
  }
 
  JLM_UNREACHABLE("Unhandled owner case.");
}
 
Output *
Output::Iterator::ComputeNext() const
{
  return ComputeNextOutput(Output_);
}
 
Output *
Output::ConstIterator::ComputeNext() const
{
  return ComputeNextOutput(Output_);
}
 
NodeInput::NodeInput(
    jlm::rvsdg::Output * origin,
    Node * node,
    std::shared_ptr<const rvsdg::Type> type)
    : jlm::rvsdg::Input(*node, *origin, std::move(type))
{}
 
NodeOutput::NodeOutput(Node * node, std::shared_ptr<const rvsdg::Type> type)
    : Output(*node, std::move(type))
{}
 
Node::Node(Region * region)
    : Id_(region->generateNodeId()),
      region_(region)
{
  region->onBottomNodeAdded(*this);
  region->onTopNodeAdded(*this);
  region->onNodeAdded(*this);
}
 
Node::~Node()
{
  // Nodes should always be dead before they are removed
  JLM_ASSERT(IsDead());
  outputs_.clear();
  region()->onBottomNodeRemoved(*this);
 
  if (ninputs() == 0)
  {
    region()->onTopNodeRemoved(*this);
  }
  inputs_.clear();
 
  region()->onNodeRemoved(*this);
}
 
Graph *
Node::graph() const noexcept
{
  return region_->graph();
}
 
NodeInput *
Node::addInput(std::unique_ptr<NodeInput> input, bool notifyRegion)
{
  // If we used to be a top node, we no longer are
  if (ninputs() == 0)
  {
    region()->onTopNodeRemoved(*this);
  }
 
  input->index_ = ninputs();
  inputs_.push_back(std::move(input));
  const auto inputPtr = inputs_.back().get();
  if (notifyRegion)
    region()->notifyInputCreate(inputPtr);
 
  return inputPtr;
}
 
size_t
Node::RemoveInputs(const util::HashSet<size_t> & indices)
{
  if (indices.IsEmpty())
  {
    return 0;
  }
 
  size_t numLiveInputs = 0;
  size_t numRemovedInputs = 0;
  for (size_t n = 0; n < ninputs(); n++)
  {
    auto & input = inputs_[n];
    if (indices.Contains(input->index()))
    {
      region()->notifyInputDestroy(input.get());
      input.reset();
      numRemovedInputs++;
    }
    else
    {
      input->index_ = numLiveInputs;
      inputs_[numLiveInputs++] = std::move(input);
    }
  }
  inputs_.resize(numLiveInputs);
 
  // If we no longer have any inputs we are now a top node
  if (numLiveInputs == 0)
  {
    region()->onTopNodeAdded(*this);
  }
 
  return numRemovedInputs;
}
 
size_t
Node::RemoveOutputs(const util::HashSet<size_t> & indices)
{
  if (indices.IsEmpty())
    return 0;
 
  size_t numLiveOutputs = 0;
  size_t numRemovedOutputs = 0;
  for (size_t n = 0; n < noutputs(); n++)
  {
    auto & output = outputs_[n];
    if (output->IsDead() && indices.Contains(output->index()))
    {
      output.reset();
      numRemovedOutputs++;
    }
    else
    {
      output->index_ = numLiveOutputs;
      outputs_[numLiveOutputs++] = std::move(output);
    }
  }
  outputs_.resize(numLiveOutputs);
 
  return numRemovedOutputs;
}
 
Node *
Node::copy(rvsdg::Region * region, const std::vector<jlm::rvsdg::Output *> & operands) const
{
  SubstitutionMap smap;
 
  size_t noperands = std::min(operands.size(), ninputs());
  for (size_t n = 0; n < noperands; n++)
    smap.insert(input(n)->origin(), operands[n]);
 
  return copy(region, smap);
}
 
Output &
RouteToRegion(Output & output, Region & region)
{
  if (&region == output.region())
    return output;
 
  if (&region == &region.graph()->GetRootRegion())
  {
    // We reached the root region and have not found the outputs' region yet.
    // This means that the output comes from a region in the region tree that
    // is not an ancestor of "region".
    throw std::logic_error("Output is not in an ancestor of region.");
  }
 
  auto & origin = RouteToRegion(output, *region.node()->region());
 
  const auto newOrigin = MatchTypeOrFail(
      *region.node(),
      [&origin, &region](GammaNode & gammaNode)
      {
        auto [input, branchArgument] = gammaNode.AddEntryVar(&origin);
        return branchArgument[region.index()];
      },
      [&origin](ThetaNode & thetaNode)
      {
        return thetaNode.AddLoopVar(&origin).pre;
      },
      [&origin](LambdaNode & lambdaNode)
      {
        return lambdaNode.AddContextVar(origin).inner;
      },
      [&origin](PhiNode & phiNode)
      {
        return phiNode.AddContextVar(origin).inner;
      },
      [&origin](DeltaNode & deltaNode)
      {
        return deltaNode.AddContextVar(origin).inner;
      });
 
  return *newOrigin;
}
 
}