GPUOcelot
|
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