region.hpp

Go to the documentation of this file.

/*
 * Copyright 2010 2011 2012 Helge Bahmann <hcb@chaoticmind.net>
 * Copyright 2011 2012 2013 2014 2015 2016 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_RVSDG_REGION_HPP
#define JLM_RVSDG_REGION_HPP
 
#include <jlm/rvsdg/node.hpp>
#include <jlm/util/common.hpp>
#include <jlm/util/iterator_range.hpp>
 
namespace jlm::util
{
class Annotation;
class AnnotationMap;
}
 
namespace jlm::rvsdg
{
 
class Node;
class SimpleNode;
class SimpleOperation;
class StructuralInput;
class StructuralNode;
class StructuralOutput;
class SubstitutionMap;
class RegionObserver;
 
class RegionArgument : public Output
{
  util::IntrusiveListAnchor<RegionArgument> structural_input_anchor_{};
 
public:
  typedef util::IntrusiveListAccessor<RegionArgument, &RegionArgument::structural_input_anchor_>
      structural_input_accessor;
 
  ~RegionArgument() noexcept override;
 
  RegionArgument(
      rvsdg::Region * region,
      StructuralInput * input,
      std::shared_ptr<const rvsdg::Type> type);
 
  RegionArgument(const RegionArgument &) = delete;
 
  RegionArgument(RegionArgument &&) = delete;
 
  RegionArgument &
  operator=(const RegionArgument &) = delete;
 
  RegionArgument &
  operator=(RegionArgument &&) = delete;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] StructuralInput *
  input() const noexcept
  {
    return input_;
  }
 
  virtual RegionArgument &
  Copy(Region & region, StructuralInput * input) const;
 
  static RegionArgument &
  Create(rvsdg::Region & region, StructuralInput * input, std::shared_ptr<const rvsdg::Type> type);
 
private:
  StructuralInput * input_;
};
 
class RegionResult : public Input
{
  util::IntrusiveListAnchor<RegionResult> structural_output_anchor_{};
 
public:
  typedef util::IntrusiveListAccessor<RegionResult, &RegionResult::structural_output_anchor_>
      structural_output_accessor;
 
  ~RegionResult() noexcept override;
 
  RegionResult(
      rvsdg::Region * region,
      rvsdg::Output * origin,
      StructuralOutput * output,
      std::shared_ptr<const rvsdg::Type> type);
 
  RegionResult(const RegionResult &) = delete;
 
  RegionResult(RegionResult &&) = delete;
 
  RegionResult &
  operator=(const RegionResult &) = delete;
 
  RegionResult &
  operator=(RegionResult &&) = delete;
 
  [[nodiscard]] std::string
  debug_string() const override;
 
  [[nodiscard]] StructuralOutput *
  output() const noexcept
  {
    return output_;
  }
 
  virtual RegionResult &
  Copy(rvsdg::Output & origin, StructuralOutput * output) const;
 
  static RegionResult &
  Create(
      rvsdg::Region & region,
      rvsdg::Output & origin,
      StructuralOutput * output,
      std::shared_ptr<const rvsdg::Type> type);
 
private:
  StructuralOutput * output_;
};
 
class Region
{
  using RegionArgumentIterator = std::vector<RegionArgument *>::iterator;
  using RegionArgumentConstIterator = std::vector<RegionArgument *>::const_iterator;
  using RegionArgumentRange = util::IteratorRange<RegionArgumentIterator>;
  using RegionArgumentConstRange = util::IteratorRange<RegionArgumentConstIterator>;
 
  using RegionResultIterator = std::vector<RegionResult *>::iterator;
  using RegionResultConstIterator = std::vector<RegionResult *>::const_iterator;
  using RegionResultRange = util::IteratorRange<RegionResultIterator>;
  using RegionResultConstRange = util::IteratorRange<RegionResultConstIterator>;
 
  using region_nodes_list = util::IntrusiveList<Node, Node::region_node_list_accessor>;
  using region_top_node_list = util::IntrusiveList<Node, Node::region_top_node_list_accessor>;
  using region_bottom_node_list = util::IntrusiveList<Node, Node::region_bottom_node_list_accessor>;
 
  using TopNodeIterator = region_top_node_list::Iterator;
  using TopNodeConstIterator = region_top_node_list::ConstIterator;
  using TopNodeRange = util::IteratorRange<TopNodeIterator>;
  using TopNodeConstRange = util::IteratorRange<TopNodeConstIterator>;
 
  using NodeIterator = region_nodes_list::Iterator;
  using NodeConstIterator = region_nodes_list::ConstIterator;
  using NodeRange = util::IteratorRange<NodeIterator>;
  using NodeConstRange = util::IteratorRange<NodeConstIterator>;
 
  using BottomNodeIterator = region_bottom_node_list::Iterator;
  using BottomNodeConstIterator = region_bottom_node_list::ConstIterator;
  using BottomNodeRange = util::IteratorRange<BottomNodeIterator>;
  using BottomNodeConstRange = util::IteratorRange<BottomNodeConstIterator>;
 
public:
  using Id = uint64_t;
 
  ~Region() noexcept;
 
  Region(Graph * graph);
 
  Region(rvsdg::StructuralNode * node, size_t index);
 
  Region(const Region &) = delete;
 
  Region &
  operator=(const Region &) = delete;
 
  [[nodiscard]] Graph *
  graph() const noexcept
  {
    return graph_;
  }
 
  [[nodiscard]] Id
  getRegionId() const noexcept
  {
    return id_;
  }
 
  [[nodiscard]] size_t
  getDepth() const noexcept
  {
    return depth_;
  }
 
  [[nodiscard]] rvsdg::StructuralNode *
  node() const noexcept
  {
    return node_;
  }
 
  [[nodiscard]] size_t
  index() const noexcept
  {
    return index_;
  }
 
  [[nodiscard]] RegionArgumentRange
  Arguments() noexcept
  {
    return { arguments_.begin(), arguments_.end() };
  }
 
  [[nodiscard]] RegionArgumentConstRange
  Arguments() const noexcept
  {
    return { arguments_.begin(), arguments_.end() };
  }
 
  [[nodiscard]] RegionResultRange
  Results() noexcept
  {
    return { results_.begin(), results_.end() };
  }
 
  [[nodiscard]] RegionResultConstRange
  Results() const noexcept
  {
    return { results_.begin(), results_.end() };
  }
 
  [[nodiscard]] TopNodeRange
  TopNodes() noexcept
  {
    return { topNodes_.begin(), topNodes_.end() };
  }
 
  [[nodiscard]] TopNodeConstRange
  TopNodes() const noexcept
  {
    return { topNodes_.begin(), topNodes_.end() };
  }
 
  [[nodiscard]] NodeRange
  Nodes() noexcept
  {
    return { nodes_.begin(), nodes_.end() };
  }
 
  [[nodiscard]] NodeConstRange
  Nodes() const noexcept
  {
    return { nodes_.begin(), nodes_.end() };
  }
 
  [[nodiscard]] BottomNodeRange
  BottomNodes() noexcept
  {
    return { bottomNodes_.begin(), bottomNodes_.end() };
  }
 
  [[nodiscard]] BottomNodeConstRange
  BottomNodes() const noexcept
  {
    return { bottomNodes_.begin(), bottomNodes_.end() };
  }
 
  [[nodiscard]] bool
  IsRootRegion() const noexcept;
 
  RegionArgument &
  addArgument(std::unique_ptr<RegionArgument> argument);
 
  RegionArgument &
  insertArgument(size_t index, std::unique_ptr<RegionArgument> argument);
 
  size_t
  RemoveArguments(const util::HashSet<size_t> & indices);
 
  size_t
  PruneArguments();
 
  inline size_t
  narguments() const noexcept
  {
    return arguments_.size();
  }
 
  inline RegionArgument *
  argument(size_t index) const noexcept
  {
    JLM_ASSERT(index < narguments());
    return arguments_[index];
  }
 
  RegionResult &
  addResult(std::unique_ptr<RegionResult> result);
 
  size_t
  RemoveResults(const util::HashSet<size_t> & indices);
 
  inline size_t
  nresults() const noexcept
  {
    return results_.size();
  }
 
  [[nodiscard]] RegionResult *
  result(size_t index) const noexcept
  {
    JLM_ASSERT(index < nresults());
    return results_[index];
  }
 
  [[nodiscard]] size_t
  numNodes() const noexcept
  {
    return numNodes_;
  }
 
  [[nodiscard]] size_t
  numTopNodes() const noexcept
  {
    return numTopNodes_;
  }
 
  [[nodiscard]] size_t
  numBottomNodes() const noexcept
  {
    return numBottomNodes_;
  }
 
  void
  removeNode(Node * node);
 
  void
  copy(Region * target, SubstitutionMap & smap) const;
 
  void
  prune(bool recursive);
 
  void
  view() const;
 
  [[nodiscard]] Node::Id
  getNextNodeId() const noexcept
  {
    return nextNodeId_;
  }
 
private:
  void
  onTopNodeAdded(Node & node);
 
  void
  onTopNodeRemoved(Node & node);
 
  void
  onBottomNodeAdded(Node & node);
 
  void
  onBottomNodeRemoved(Node & node);
 
  void
  onNodeAdded(Node & node);
 
  void
  onNodeRemoved(Node & node);
 
  [[nodiscard]] Node::Id
  generateNodeId() noexcept
  {
    const auto nodeId = nextNodeId_;
    nextNodeId_++;
    return nodeId;
  }
 
  void
  notifyNodeCreate(Node * node);
 
  void
  notifyNodeDestroy(Node * node);
 
  void
  notifyInputCreate(Input * input);
 
  void
  notifyInputChange(Input * input, Output * old_origin, Output * new_origin);
 
  void
  notifyInputDestroy(Input * input);
 
public:
  template<class TOperation>
  static bool
  containsOperation(const Region & region, bool checkSubregions);
 
  template<class TNodeType>
  static bool
  containsNodeType(const Region & region, bool checkSubregions);
 
  [[nodiscard]] static size_t
  NumRegions(const rvsdg::Region & region) noexcept;
 
  [[nodiscard]] static bool
  isAncestor(const rvsdg::Region & region, const rvsdg::Region & ancestor) noexcept;
 
  [[nodiscard]] static std::string
  ToTree(const rvsdg::Region & region, const util::AnnotationMap & annotationMap) noexcept;
 
  [[nodiscard]] static std::string
  ToTree(const rvsdg::Region & region) noexcept;
 
  [[nodiscard]] static std::string
  toJson(const Region & region, const util::AnnotationMap & annotationMap) noexcept;
 
  [[nodiscard]] static std::string
  toJson(const Region & region) noexcept;
 
private:
  static void
  ToTree(
      const rvsdg::Region & region,
      const util::AnnotationMap & annotationMap,
      size_t indentationDepth,
      std::stringstream & stream) noexcept;
 
  static void
  toJson(
      const Region & region,
      const util::AnnotationMap & annotationMap,
      std::stringstream & stream) noexcept;
 
  static void
  toJson(
      const StructuralNode & structuralNode,
      const util::AnnotationMap & annotationMap,
      std::stringstream & stream) noexcept;
 
  [[nodiscard]] static std::string
  toJsonKeyValue(const util::Annotation & annotation) noexcept;
 
  [[nodiscard]] static std::string
  GetAnnotationString(
      const void * key,
      const util::AnnotationMap & annotationMap,
      char annotationSeparator,
      char labelValueSeparator);
 
  [[nodiscard]] static std::string
  ToString(
      const std::vector<util::Annotation> & annotations,
      char annotationSeparator,
      char labelValueSeparator);
 
  [[nodiscard]] static std::string
  ToString(const util::Annotation & annotation, char labelValueSeparator);
 
  Graph * const graph_;
  const Id id_;
  const size_t depth_;
 
  rvsdg::StructuralNode * const node_;
  const size_t index_;
 
  Node::Id nextNodeId_;
 
  // The region owns its results, arguments and nodes
  std::vector<RegionResult *> results_;
  std::vector<RegionArgument *> arguments_;
  region_top_node_list topNodes_;
  size_t numTopNodes_;
  region_bottom_node_list bottomNodes_;
  size_t numBottomNodes_;
  region_nodes_list nodes_;
  size_t numNodes_;
 
  mutable RegionObserver * observers_ = nullptr;
 
  friend class Node;
  friend class RegionObserver;
  friend class SimpleNode;
  friend class StructuralNode;
  friend class Input;
  friend class Output;
  friend class RegionResult;
};
 
class RegionObserver
{
public:
  virtual ~RegionObserver() noexcept;
 
  explicit RegionObserver(const Region & region);
 
  RegionObserver(const RegionObserver &) = delete;
 
  RegionObserver &
  operator=(const RegionObserver &) = delete;
 
  virtual void
  onNodeCreate(Node * node) = 0;
 
  virtual void
  onNodeDestroy(Node * node) = 0;
 
  virtual void
  onInputCreate(Input * input) = 0;
 
  virtual void
  onInputChange(Input * input, Output * old_origin, Output * new_origin) = 0;
 
  virtual void
  onInputDestroy(Input * input) = 0;
 
private:
  RegionObserver ** pprev_;
  RegionObserver * next_;
 
  friend class Region;
};
 
class RecordingObserver final : public RegionObserver
{
public:
  ~RecordingObserver() noexcept override = default;
 
  explicit RecordingObserver(const Region & region)
      : RegionObserver(region)
  {}
 
  void
  onInputDestroy(Input * input) override
  {
    destroyedInputIndices_.push_back(input->index());
  }
 
  const std::vector<size_t> &
  destroyedInputIndices() const noexcept
  {
    return destroyedInputIndices_;
  }
 
  void
  onNodeCreate(Node * node) override
  {
    createNodes_.push_back(node->GetNodeId());
  }
 
  const std::vector<Node::Id> &
  createdNodes() const noexcept
  {
    return createNodes_;
  }
 
  void
  onNodeDestroy(Node * node) override
  {
    destroyedNodes_.push_back(node->GetNodeId());
  }
 
  const std::vector<Node::Id> &
  destroyedNodes() const noexcept
  {
    return destroyedNodes_;
  }
 
  void
  onInputCreate(Input * input) override
  {
    createdInputIndices_.push_back(input->index());
  }
 
  const std::vector<size_t> &
  createdInputIndices() const noexcept
  {
    return createdInputIndices_;
  }
 
  void
  onInputChange(Input * input, Output *, Output *) override
  {
    changedInputIndices_.push_back(input->index());
  }
 
  const std::vector<size_t> &
  changedInputIndices() const noexcept
  {
    return changedInputIndices_;
  }
 
private:
  std::vector<Node::Id> createNodes_{};
  std::vector<Node::Id> destroyedNodes_{};
  std::vector<size_t> createdInputIndices_{};
  std::vector<size_t> changedInputIndices_{};
  std::vector<size_t> destroyedInputIndices_{};
};
 
std::unordered_map<const Node *, size_t>
computeDepthMap(const Region & region);
 
static inline void
remove(Node * node)
{
  return node->region()->removeNode(node);
}
 
size_t
nnodes(const rvsdg::Region * region) noexcept;
 
size_t
nstructnodes(const rvsdg::Region * region) noexcept;
 
size_t
nsimpnodes(const rvsdg::Region * region) noexcept;
 
size_t
ninputs(const rvsdg::Region * region) noexcept;
 
template<typename NodeType>
inline NodeType *
TryGetRegionParentNode(const rvsdg::Input & input) noexcept
{
  auto region = TryGetOwnerRegion(input);
  if (region)
  {
    return dynamic_cast<NodeType *>(region->node());
  }
  else
  {
    return nullptr;
  }
}
 
template<typename NodeType>
inline NodeType *
TryGetRegionParentNode(const rvsdg::Output & output) noexcept
{
  auto region = TryGetOwnerRegion(output);
  if (region)
  {
    return dynamic_cast<NodeType *>(region->node());
  }
  else
  {
    return nullptr;
  }
}
 
template<typename NodeType>
inline NodeType &
AssertGetRegionParentNode(const rvsdg::Input & input)
{
  auto node = TryGetRegionParentNode<NodeType>(input);
  if (!node)
  {
    throw std::logic_error(std::string("expected node of type ") + typeid(NodeType).name());
  }
  return *node;
}
 
template<typename NodeType>
inline NodeType &
AssertGetRegionParentNode(const rvsdg::Output & output)
{
  auto node = TryGetRegionParentNode<NodeType>(output);
  if (!node)
  {
    throw std::logic_error(std::string("expected node of type ") + typeid(NodeType).name());
  }
  return *node;
}
 
} // namespace
 
#endif