ControlFlowGraph.h

Go to the documentation of this file.

#ifndef IR_CONTROL_FLOW_GRAPH_H
#define IR_CONTROL_FLOW_GRAPH_H

#include <iostream>
#include <deque>
#include <vector>
#include <list>
#include <unordered_map>

namespace ir {

class Instruction;

class BasicBlock {
public:
  typedef std::list< BasicBlock >   BlockList;
  typedef BlockList::iterator       Pointer;
  typedef BlockList::const_iterator ConstPointer;

  class Edge {
  public:
    enum Type {
      Branch, //< target of a branch
      FallThrough, //< edge when bb continues execution without jump
      Dummy, //< does not actually represent true control flow
      Invalid //< edge is not valid
    };
  
  public:
    Edge(BlockList::iterator h = BlockList::iterator(), 
      BlockList::iterator t = BlockList::iterator(), 
      Type y = FallThrough);

    BlockList::iterator head;
    BlockList::iterator tail;
    Type type;
  };

  typedef std::list<Edge>                 EdgeList;
  typedef std::vector<Pointer>            BlockPointerVector;
  typedef std::vector<ConstPointer>       ConstBlockPointerVector;
  typedef std::vector<EdgeList::iterator> EdgePointerVector;
  typedef std::list<Instruction*>         InstructionList;
  typedef InstructionList::iterator       instruction_iterator;
  typedef InstructionList::const_iterator const_instruction_iterator;
  typedef unsigned int                    Id;

public:
  BasicBlock(const std::string& l = "", Id i = 0, 
    const InstructionList& instructions = InstructionList(),
    const std::string& c = "");
  ~BasicBlock();

  void clear();

  EdgeList::iterator get_fallthrough_edge();
  EdgeList::const_iterator get_fallthrough_edge() const;
  bool has_fallthrough_edge() const;

  EdgeList::iterator get_branch_edge();
  EdgeList::const_iterator get_branch_edge() const;
  bool has_branch_edge() const;

  EdgeList::iterator get_edge(BlockList::iterator b);
  EdgeList::const_iterator get_edge(BlockList::const_iterator b) const;

public:
  EdgePointerVector::iterator find_in_edge(
    BlockList::const_iterator head);
  EdgePointerVector::iterator find_out_edge(
    BlockList::const_iterator tail);

public:
  InstructionList instructions;

  std::string label;
  std::string comment;
  Id id;

  BlockPointerVector successors;
  BlockPointerVector predecessors;

  EdgePointerVector in_edges;
  EdgePointerVector out_edges;

public:

  class DotFormatter {
  public:
    DotFormatter();
    virtual ~DotFormatter();

  public:   
    virtual std::string entryLabel(const BasicBlock *block);
    
    virtual std::string exitLabel(const BasicBlock *block);
  
    virtual std::string toString(const BasicBlock *block);

    virtual std::string toString(const Edge *edge);
  };
};

typedef BasicBlock::Edge Edge;

class ControlFlowGraph {
public:
  typedef ir::BasicBlock BasicBlock;

  typedef BasicBlock::BlockList BlockList;
  typedef BasicBlock::EdgeList EdgeList;
  typedef BasicBlock::EdgePointerVector EdgePointerVector;
  typedef BasicBlock::BlockPointerVector BlockPointerVector;
  typedef BasicBlock::ConstBlockPointerVector ConstBlockPointerVector;
  
  typedef BlockList::iterator iterator;
  typedef BlockList::const_iterator const_iterator;
  
  typedef BlockPointerVector::iterator pointer_iterator;
  typedef BlockPointerVector::const_iterator const_pointer_iterator;
  typedef BlockPointerVector::reverse_iterator reverse_pointer_iterator;  
  
  typedef EdgeList::iterator edge_iterator;
  typedef EdgeList::const_iterator const_edge_iterator;
  typedef std::pair<edge_iterator, edge_iterator> EdgePair;

  typedef EdgePointerVector::iterator edge_pointer_iterator;
  typedef EdgePointerVector::const_iterator const_edge_pointer_iterator;

  typedef std::unordered_map<const_iterator, unsigned int> BlockMap;
  typedef BasicBlock::Edge Edge;

  typedef BasicBlock::InstructionList InstructionList;
  typedef InstructionList::iterator instruction_iterator;

  typedef std::unordered_map<std::string, unsigned int> BasicBlockColorMap;

public:
  ControlFlowGraph();
  ~ControlFlowGraph();

public:
  static std::string toString( Edge::Type t );
  
public:
  void computeNewBlockId();

  BasicBlock::Id newId();

  size_t size() const;
  
  bool empty() const;

  iterator insert_block(const BasicBlock& b);
  
  iterator clone_block(iterator block, std::string suffix);
  
  void remove_block(iterator block);

  edge_iterator insert_edge(const Edge& e);
  
  void remove_edge(edge_iterator edge);
  
  EdgePair split_edge(edge_iterator edge, const BasicBlock& newBlock);

  iterator split_block(iterator block, unsigned int instruction, 
    Edge::Type type, const std::string& label = "");

  iterator get_entry_block();

  iterator get_exit_block();
  
  const_iterator get_entry_block() const;

  const_iterator get_exit_block() const;
  
  std::ostream& write(std::ostream& out) const;

  std::ostream& write(std::ostream& out, 
    BasicBlock::DotFormatter& blockFormatter) const;
  
  void clear();
  
  BlockPointerVector pre_order_sequence();
  
  BlockPointerVector post_order_sequence();

  BlockPointerVector topological_sequence();

  BlockPointerVector reverse_topological_sequence();

  BlockPointerVector executable_sequence();
  
  ControlFlowGraph& operator=(const ControlFlowGraph &);

public:
  iterator begin();
  iterator end();
  
  const_iterator begin() const;
  const_iterator end() const;

  edge_iterator edges_begin();
  edge_iterator edges_end();

  const_edge_iterator edges_begin() const;
  const_edge_iterator edges_end() const;

private:
  BlockList _blocks;
  EdgeList  _edges;

  iterator _entry;
  iterator _exit;
  
  BasicBlock::Id _nextId;
};

}

namespace std
{
  template<> 
  struct hash<ir::ControlFlowGraph::iterator>
  {
  public:
    size_t operator()(const ir::ControlFlowGraph::iterator& it) const
    {
      return (size_t)it->id;
    }
  };

  template<> 
  struct hash<ir::ControlFlowGraph::const_iterator>
  {
  public:
    size_t operator()(const ir::ControlFlowGraph::const_iterator& it) const
    {
      return (size_t)it->id;
    }
  };

  template<> 
  struct hash<ir::ControlFlowGraph::InstructionList::iterator>
  {
  public:
    size_t operator()( 
      const ir::ControlFlowGraph::InstructionList::iterator& it) const
    {
      return (size_t)&(*it);
    }
  };

  template<> 
  struct hash<ir::ControlFlowGraph::InstructionList::const_iterator>
  {
  public:
    typedef ir::ControlFlowGraph::InstructionList::const_iterator type;
  
    size_t operator()(const type& it) const
    {
      return (size_t)&(*it);
    }
  };
}


#endif