cfg-structure.hpp

Go to the documentation of this file.

/*
 * Copyright 2017 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_LLVM_IR_CFG_STRUCTURE_HPP
#define JLM_LLVM_IR_CFG_STRUCTURE_HPP
 
#include <jlm/util/HashSet.hpp>
#include <jlm/util/iterator_range.hpp>
#include <jlm/util/IteratorWrapper.hpp>
 
#include <memory>
#include <unordered_set>
#include <vector>
 
namespace jlm::llvm
{
 
class ControlFlowGraph;
class ControlFlowGraphEdge;
class ControlFlowGraphNode;
 
class StronglyConnectedComponent final
{
  using constiterator = util::
      PtrIterator<ControlFlowGraphNode, std::unordered_set<ControlFlowGraphNode *>::const_iterator>;
 
public:
  explicit StronglyConnectedComponent(const std::unordered_set<ControlFlowGraphNode *> & nodes)
      : nodes_(nodes)
  {}
 
  constiterator
  begin() const;
 
  constiterator
  end() const;
 
  bool
  contains(ControlFlowGraphNode * node) const
  {
    return nodes_.find(node) != nodes_.end();
  }
 
  size_t
  nnodes() const noexcept
  {
    return nodes_.size();
  }
 
private:
  std::unordered_set<ControlFlowGraphNode *> nodes_{};
};
 
class StronglyConnectedComponentStructure final
{
  using CfgEdgeConstIterator = util::HashSet<ControlFlowGraphEdge *>::ItemConstIterator;
  using CfgNodeConstIterator = util::HashSet<ControlFlowGraphNode *>::ItemConstIterator;
 
  using EdgeIteratorRange = util::IteratorRange<CfgEdgeConstIterator>;
  using NodeIteratorRange = util::IteratorRange<CfgNodeConstIterator>;
 
public:
  size_t
  NumEntryNodes() const noexcept
  {
    return EntryNodes_.Size();
  }
 
  size_t
  NumExitNodes() const noexcept
  {
    return ExitNodes_.Size();
  }
 
  size_t
  NumEntryEdges() const noexcept
  {
    return EntryEdges_.Size();
  }
 
  size_t
  NumRepetitionEdges() const noexcept
  {
    return RepetitionEdges_.Size();
  }
 
  size_t
  NumExitEdges() const noexcept
  {
    return ExitEdges_.Size();
  }
 
  NodeIteratorRange
  EntryNodes() const
  {
    return { EntryNodes_.Items().begin(), EntryNodes_.Items().end() };
  }
 
  NodeIteratorRange
  ExitNodes() const
  {
    return { ExitNodes_.Items().begin(), ExitNodes_.Items().end() };
  }
 
  EdgeIteratorRange
  EntryEdges() const
  {
    return { EntryEdges_.Items().begin(), EntryEdges_.Items().end() };
  }
 
  EdgeIteratorRange
  RepetitionEdges() const
  {
    return { RepetitionEdges_.Items().begin(), RepetitionEdges_.Items().end() };
  }
 
  EdgeIteratorRange
  ExitEdges() const
  {
    return { ExitEdges_.Items().begin(), ExitEdges_.Items().end() };
  }
 
  static std::unique_ptr<StronglyConnectedComponentStructure>
  Create(const StronglyConnectedComponent & scc);
 
  bool
  IsTailControlledLoop() const noexcept;
 
private:
  util::HashSet<ControlFlowGraphNode *> EntryNodes_{};
  util::HashSet<ControlFlowGraphNode *> ExitNodes_{};
  util::HashSet<ControlFlowGraphEdge *> EntryEdges_{};
  util::HashSet<ControlFlowGraphEdge *> RepetitionEdges_{};
  util::HashSet<ControlFlowGraphEdge *> ExitEdges_{};
};
 
bool
is_valid(const ControlFlowGraph & cfg);
 
bool
is_closed(const ControlFlowGraph & cfg);
 
bool
is_linear(const ControlFlowGraph & cfg);
 
std::vector<StronglyConnectedComponent>
find_sccs(const ControlFlowGraph & cfg);
 
std::vector<StronglyConnectedComponent>
find_sccs(ControlFlowGraphNode * entry, ControlFlowGraphNode * exit);
 
static inline bool
is_acyclic(const ControlFlowGraph & cfg)
{
  auto sccs = find_sccs(cfg);
  return sccs.size() == 0;
}
 
bool
is_structured(const ControlFlowGraph & cfg);
 
bool
is_proper_structured(const ControlFlowGraph & cfg);
 
bool
is_reducible(const ControlFlowGraph & cfg);
 
void
straighten(ControlFlowGraph & cfg);
 
void
purge(ControlFlowGraph & cfg);
 
void
prune(ControlFlowGraph & cfg);
 
}
 
#endif