traverser.hpp

Go to the documentation of this file.

/*
 * Copyright 2010 2011 2012 2015 Helge Bahmann <hcb@chaoticmind.net>
 * Copyright 2014 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_RVSDG_TRAVERSER_HPP
#define JLM_RVSDG_TRAVERSER_HPP
 
#include <jlm/rvsdg/region.hpp>
 
#include <list>
#include <unordered_map>
 
namespace jlm::rvsdg
{
 
class Graph;
class Input;
class Node;
class Output;
class Region;
 
namespace detail
{
 
enum class TraversalNodeState : uint8_t
{
  // Nodes that are not ready to be visited
  ahead = 0,
  // Nodes that are ready to be visited
  frontier = 1,
  // Nodes that have been visited
  behind = 2
};
 
template<typename NodeType>
class TraversalTracker final
{
public:
  bool
  isNodeVisited(NodeType * node) const;
 
  void
  checkNodeActivation(NodeType * node, std::size_t threshold);
 
  void
  checkNodeDeactivation(NodeType * node, std::size_t threshold);
 
  void
  checkMarkNodeVisitedIfFrontier(NodeType * node);
 
  void
  incActivationCount(NodeType * node, std::size_t threshold);
 
  void
  decActivationCount(NodeType * node, std::size_t threshold);
 
  void
  removeNode(NodeType * node);
 
  NodeType *
  peek();
 
private:
  using FrontierList = std::list<NodeType *>;
 
  struct State
  {
    TraversalNodeState state = TraversalNodeState::ahead;
    uint32_t activationCount = 0;
    typename FrontierList::iterator pos = {};
  };
 
  std::unordered_map<NodeType *, State> states_;
  FrontierList frontier_;
};
 
template<typename Traverser, typename NodeType>
class TraverserIterator
{
public:
  using iterator_category = std::input_iterator_tag;
  using value_type = NodeType *;
  using difference_type = ssize_t;
  using pointer = value_type *;
  using reference = value_type &;
 
  constexpr TraverserIterator(Traverser & traverser, NodeType * node) noexcept
      : traverser_(traverser),
        node_(node)
  {}
 
  const TraverserIterator &
  operator++() noexcept
  {
    node_ = traverser_.next();
    return *this;
  }
 
  bool
  operator==(const TraverserIterator & other) const noexcept
  {
    return &traverser_ == &other.traverser_ && node_ == other.node_;
  }
 
  bool
  operator!=(const TraverserIterator & other) const noexcept
  {
    return !(*this == other);
  }
 
  reference
  operator*() noexcept
  {
    return node_;
  }
 
  pointer
  operator->() noexcept
  {
    return &node_;
  }
 
private:
  Traverser & traverser_;
  NodeType * node_;
};
 
template<typename Traverser>
class ForwardingObserver final : public RegionObserver
{
public:
  ~ForwardingObserver() noexcept override;
 
  ForwardingObserver(const Region & region, Traverser & traverser);
 
  void
  onNodeCreate(Node * node) override;
 
  void
  onNodeDestroy(Node * node) override;
 
  void
  onInputCreate(Input * input) override;
 
  void
  onInputChange(Input * input, Output * oldOrigin, Output * newOrigin) override;
 
  void
  onInputDestroy(Input * input) override;
 
private:
  Traverser & traverser_;
};
 
template<bool IsConst>
class TopDownTraverserGeneric final
{
public:
  using NodeType = std::conditional_t<IsConst, const Node, Node>;
  using RegionType = std::conditional_t<IsConst, const Region, Region>;
  using ObserverType = ForwardingObserver<TopDownTraverserGeneric>;
  using iterator = TraverserIterator<TopDownTraverserGeneric, NodeType>;
 
  friend class ForwardingObserver<TopDownTraverserGeneric>;
 
  ~TopDownTraverserGeneric() noexcept;
 
  explicit TopDownTraverserGeneric(RegionType * region);
 
  NodeType *
  next();
 
  iterator
  begin()
  {
    return iterator(*this, next());
  }
 
  iterator
  end()
  {
    return iterator(*this, nullptr);
  }
 
private:
  bool
  isOutputActivated(const Output & output) const;
 
  void
  markAsVisited(NodeType & node);
 
  void
  onNodeCreate(NodeType * node);
 
  void
  onNodeDestroy(NodeType * node);
 
  void
  onInputCreate(Input * input);
 
  void
  onInputChange(Input * in, Output * old_origin, Output * new_origin);
 
  void
  onInputDestroy(Input * input);
 
  TraversalTracker<NodeType> tracker_;
  ObserverType observer_;
  // Any node with Id >= this cutoff was created after traversal began and will be skipped
  Node::Id nodeIdCutoff_;
};
 
template<bool IsConst>
class BottomUpTraverserGeneric final
{
public:
  using NodeType = std::conditional_t<IsConst, const Node, Node>;
  using RegionType = std::conditional_t<IsConst, const Region, Region>;
  using ObserverType = ForwardingObserver<BottomUpTraverserGeneric>;
  using iterator = TraverserIterator<BottomUpTraverserGeneric, NodeType>;
 
  friend class ForwardingObserver<BottomUpTraverserGeneric>;
 
  ~BottomUpTraverserGeneric() noexcept;
 
  explicit BottomUpTraverserGeneric(RegionType * region);
 
  NodeType *
  next();
 
  iterator
  begin()
  {
    return iterator(*this, next());
  }
 
  iterator
  end()
  {
    return iterator(*this, nullptr);
  }
 
private:
  bool
  isInputActivated(const Input & input) const;
 
  void
  markAsVisited(NodeType & node);
 
  void
  onNodeCreate(NodeType * node);
 
  void
  onNodeDestroy(NodeType * node);
 
  void
  onInputCreate(Input * input);
 
  void
  onInputChange(Input * input, Output * oldOrigin, Output * newOrigin);
 
  void
  onInputDestroy(Input * input);
 
  TraversalTracker<NodeType> tracker_;
  ObserverType observer_;
};
 
}
 
using TopDownTraverser = detail::TopDownTraverserGeneric<false>;
 
using TopDownConstTraverser = detail::TopDownTraverserGeneric<true>;
 
using BottomUpTraverser = detail::BottomUpTraverserGeneric<false>;
 
using BottomUpConstTraverser = detail::BottomUpTraverserGeneric<true>;
 
}
 
#endif