GPUOcelot

ControlFlowGraph.h

Go to the documentation of this file.
00001 
00007 #ifndef IR_CONTROL_FLOW_GRAPH_H
00008 #define IR_CONTROL_FLOW_GRAPH_H
00009 
00010 #include <iostream>
00011 #include <deque>
00012 #include <vector>
00013 #include <list>
00014 #include <unordered_map>
00015 
00016 namespace ir {
00017 
00018 class Instruction;
00019 
00022 class BasicBlock {
00023 public:
00025   typedef std::list< BasicBlock >   BlockList;
00026   typedef BlockList::iterator       Pointer;
00027   typedef BlockList::const_iterator ConstPointer;
00028 
00030   class Edge {
00031   public:
00032     enum Type {
00033       Branch, //< target of a branch
00034       FallThrough, //< edge when bb continues execution without jump
00035       Dummy, //< does not actually represent true control flow
00036       Invalid //< edge is not valid
00037     };
00038   
00039   public:
00040     Edge(BlockList::iterator h = BlockList::iterator(), 
00041       BlockList::iterator t = BlockList::iterator(), 
00042       Type y = FallThrough);
00043 
00045     BlockList::iterator head;
00047     BlockList::iterator tail;
00049     Type type;
00050   };
00051 
00052   typedef std::list<Edge>                 EdgeList;
00053   typedef std::vector<Pointer>            BlockPointerVector;
00054   typedef std::vector<ConstPointer>       ConstBlockPointerVector;
00055   typedef std::vector<EdgeList::iterator> EdgePointerVector;
00056   typedef std::list<Instruction*>         InstructionList;
00057   typedef InstructionList::iterator       instruction_iterator;
00058   typedef InstructionList::const_iterator const_instruction_iterator;
00059   typedef unsigned int                    Id;
00060 
00061 public:
00062   BasicBlock(const std::string& l = "", Id i = 0, 
00063     const InstructionList& instructions = InstructionList(),
00064     const std::string& c = "");
00065   ~BasicBlock();
00066 
00068   void clear();
00069 
00071   EdgeList::iterator get_fallthrough_edge();
00073   EdgeList::const_iterator get_fallthrough_edge() const;
00075   bool has_fallthrough_edge() const;
00076 
00078   EdgeList::iterator get_branch_edge();
00080   EdgeList::const_iterator get_branch_edge() const;
00082   bool has_branch_edge() const;
00083 
00085   EdgeList::iterator get_edge(BlockList::iterator b);
00087   EdgeList::const_iterator get_edge(BlockList::const_iterator b) const;
00088 
00089 public:
00091   EdgePointerVector::iterator find_in_edge(
00092     BlockList::const_iterator head);
00094   EdgePointerVector::iterator find_out_edge(
00095     BlockList::const_iterator tail);
00096 
00097 public:
00099   InstructionList instructions;
00100 
00102   std::string label;
00104   std::string comment;
00106   Id id;
00107 
00109   BlockPointerVector successors;
00111   BlockPointerVector predecessors;
00112 
00114   EdgePointerVector in_edges;
00116   EdgePointerVector out_edges;
00117 
00118 public:
00119 
00124   class DotFormatter {
00125   public:
00126     DotFormatter();
00127     virtual ~DotFormatter();
00128 
00129   public:   
00131     virtual std::string entryLabel(const BasicBlock *block);
00132     
00134     virtual std::string exitLabel(const BasicBlock *block);
00135   
00137     virtual std::string toString(const BasicBlock *block);
00138 
00140     virtual std::string toString(const Edge *edge);
00141   };
00142 };
00143 
00144 typedef BasicBlock::Edge Edge;
00145 
00147 class ControlFlowGraph {
00148 public:
00149   typedef ir::BasicBlock BasicBlock;
00150 
00152   typedef BasicBlock::BlockList BlockList;
00154   typedef BasicBlock::EdgeList EdgeList;
00156   typedef BasicBlock::EdgePointerVector EdgePointerVector;
00158   typedef BasicBlock::BlockPointerVector BlockPointerVector;
00160   typedef BasicBlock::ConstBlockPointerVector ConstBlockPointerVector;
00161   
00163   typedef BlockList::iterator iterator;
00165   typedef BlockList::const_iterator const_iterator;
00166   
00168   typedef BlockPointerVector::iterator pointer_iterator;
00170   typedef BlockPointerVector::const_iterator const_pointer_iterator;
00172   typedef BlockPointerVector::reverse_iterator reverse_pointer_iterator;  
00173   
00175   typedef EdgeList::iterator edge_iterator;
00177   typedef EdgeList::const_iterator const_edge_iterator;
00179   typedef std::pair<edge_iterator, edge_iterator> EdgePair;
00180 
00182   typedef EdgePointerVector::iterator edge_pointer_iterator;
00184   typedef EdgePointerVector::const_iterator const_edge_pointer_iterator;
00185 
00187   typedef std::unordered_map<const_iterator, unsigned int> BlockMap;
00189   typedef BasicBlock::Edge Edge;
00190 
00192   typedef BasicBlock::InstructionList InstructionList;
00194   typedef InstructionList::iterator instruction_iterator;
00195 
00197   typedef std::unordered_map<std::string, unsigned int> BasicBlockColorMap;
00198 
00199 public:
00200   ControlFlowGraph();
00201   ~ControlFlowGraph();
00202 
00203 public:
00205   static std::string toString( Edge::Type t );
00206   
00207 public:
00209   void computeNewBlockId();
00210 
00212   BasicBlock::Id newId();
00213 
00215   size_t size() const;
00216   
00218   bool empty() const;
00219 
00221   iterator insert_block(const BasicBlock& b);
00222   
00225   iterator clone_block(iterator block, std::string suffix);
00226   
00232   void remove_block(iterator block);
00233 
00237   edge_iterator insert_edge(const Edge& e);
00238   
00244   void remove_edge(edge_iterator edge);
00245   
00256   EdgePair split_edge(edge_iterator edge, const BasicBlock& newBlock);
00257 
00270   iterator split_block(iterator block, unsigned int instruction, 
00271     Edge::Type type, const std::string& label = "");
00272 
00274   iterator get_entry_block();
00275 
00277   iterator get_exit_block();
00278   
00280   const_iterator get_entry_block() const;
00281 
00283   const_iterator get_exit_block() const;
00284   
00286   std::ostream& write(std::ostream& out) const;
00287 
00290   std::ostream& write(std::ostream& out, 
00291     BasicBlock::DotFormatter& blockFormatter) const;
00292   
00294   void clear();
00295   
00299   BlockPointerVector pre_order_sequence();
00300   
00304   BlockPointerVector post_order_sequence();
00305 
00310   BlockPointerVector topological_sequence();
00311 
00316   BlockPointerVector reverse_topological_sequence();
00317 
00321   BlockPointerVector executable_sequence();
00322   
00324   ControlFlowGraph& operator=(const ControlFlowGraph &);
00325 
00326 public:
00328   iterator begin();
00330   iterator end();
00331   
00333   const_iterator begin() const;
00335   const_iterator end() const;
00336 
00338   edge_iterator edges_begin();
00340   edge_iterator edges_end();
00341 
00343   const_edge_iterator edges_begin() const;
00345   const_edge_iterator edges_end() const;
00346 
00347 private:
00348   BlockList _blocks;
00349   EdgeList  _edges;
00350 
00351   iterator _entry;
00352   iterator _exit;
00353   
00354   BasicBlock::Id _nextId;
00355 };
00356 
00357 }
00358 
00359 namespace std
00360 {
00361   template<> 
00362   struct hash<ir::ControlFlowGraph::iterator>
00363   {
00364   public:
00365     size_t operator()(const ir::ControlFlowGraph::iterator& it) const
00366     {
00367       return (size_t)it->id;
00368     }
00369   };
00370 
00371   template<> 
00372   struct hash<ir::ControlFlowGraph::const_iterator>
00373   {
00374   public:
00375     size_t operator()(const ir::ControlFlowGraph::const_iterator& it) const
00376     {
00377       return (size_t)it->id;
00378     }
00379   };
00380 
00381   template<> 
00382   struct hash<ir::ControlFlowGraph::InstructionList::iterator>
00383   {
00384   public:
00385     size_t operator()( 
00386       const ir::ControlFlowGraph::InstructionList::iterator& it) const
00387     {
00388       return (size_t)&(*it);
00389     }
00390   };
00391 
00392   template<> 
00393   struct hash<ir::ControlFlowGraph::InstructionList::const_iterator>
00394   {
00395   public:
00396     typedef ir::ControlFlowGraph::InstructionList::const_iterator type;
00397   
00398     size_t operator()(const type& it) const
00399     {
00400       return (size_t)&(*it);
00401     }
00402   };
00403 }
00404 
00405 
00406 #endif
00407 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines