GPUOcelot

DataflowGraph.h

Go to the documentation of this file.
00001 
00007 #ifndef DATAFLOW_GRAPH_H_INCLUDED
00008 #define DATAFLOW_GRAPH_H_INCLUDED
00009 
00010 // Ocelot Includes
00011 #include <ocelot/analysis/interface/Analysis.h>
00012 #include <ocelot/ir/interface/ControlFlowGraph.h>
00013 #include <ocelot/ir/interface/PTXInstruction.h>
00014 
00015 // Hydrazine Includes
00016 #include <hydrazine/implementation/debug.h>
00017 
00018 // Standard Library Includes
00019 #include <cassert>
00020 #include <unordered_set>
00021 
00022 #ifdef REPORT_BASE
00023 #undef REPORT_BASE
00024 #endif
00025 
00026 #define REPORT_BASE 0
00027 
00028 // Forward Declarations
00029 namespace analysis { class SSAGraph; }
00030 
00032 namespace analysis
00033 {
00037 class DataflowGraph : public KernelAnalysis
00038 {
00039   friend class SSAGraph;
00040   public:     
00042     typedef ir::PTXOperand::DataType Type;
00044     typedef unsigned int RegisterId;
00046     typedef ir::ControlFlowGraph::InstructionList InstructionList;
00047 
00049     class RegisterPointer
00050     {
00051       public:
00053         Type type;
00055         RegisterId* pointer;
00056         
00057       public:
00059         RegisterPointer( RegisterId* id, Type type );
00060         
00061       public:
00063         bool operator==( const RegisterPointer& r ) const;
00064     };
00065 
00067     class Register
00068     {
00069       public:
00071         Type type;
00073         RegisterId id;
00074         
00075       public:
00077         Register( RegisterId id = 0, 
00078           Type type = ir::PTXOperand::TypeSpecifier_invalid );
00080         Register( const RegisterPointer& r );
00081         
00082       public:
00084         bool operator==( const Register& r ) const;
00085     };
00086 
00087     struct Register_Hash
00088     {
00089       inline std::size_t operator()( Register r ) const
00090       {
00091         return r.id;
00092       }
00093     };
00094     
00096     typedef std::vector< RegisterPointer > RegisterPointerVector;
00098     typedef std::vector< Register > RegisterVector;
00099     
00101     class NoProducerException : public std::exception
00102     {
00103       private:
00104         std::string _message;
00105       
00106       public:
00107         NoProducerException( RegisterId reg );
00108         ~NoProducerException() throw();
00109         const char* what() const throw();
00110     };
00111 
00112     
00113     class Block;
00114     class Instruction;
00115     class PhiInstruction;
00117     typedef std::list< Instruction > InstructionVector;
00119     typedef std::list< PhiInstruction > PhiInstructionVector;
00121     typedef std::list< Block > BlockVector;
00122     typedef std::list<InstructionVector::iterator> InstructionIteratorList;
00123     
00125     class Instruction
00126     {
00127       public:
00129         ir::Instruction* i;
00131         RegisterPointerVector d;
00133         RegisterPointerVector s;
00135         InstructionIteratorList uses;
00137         InstructionIteratorList defs;
00139         typedef InstructionIteratorList::iterator DUIterator;
00140 
00141     };
00142     
00144     class PhiInstruction
00145     {
00146       public:
00148         Register d;
00150         RegisterVector s;
00151     };
00152 
00153     struct BlockVector_Hash
00154     {
00155       inline std::size_t operator()( BlockVector::iterator it ) const
00156       {
00157         return (std::size_t)it->id();
00158       }
00159     };
00160 
00162     typedef std::unordered_set< BlockVector::iterator,
00163       BlockVector_Hash > BlockPointerSet;
00164     
00168     class Block
00169     {
00170       friend class SSAGraph;
00171       friend class DataflowGraph;
00172       friend class SyncEliminationPass;
00173       public:
00175         enum Type
00176         {
00177           Entry,
00178           Exit,
00179           Body,
00180           Invalid
00181         };
00182     
00184         typedef std::unordered_set< Register, Register_Hash > RegisterSet;
00185 
00186       private:
00188         RegisterSet _aliveIn;
00190         RegisterSet _aliveOut;
00192         BlockVector::iterator _fallthrough;
00194         BlockPointerSet _targets;
00196         BlockPointerSet _predecessors;
00198         Type _type;
00200         PhiInstructionVector _phis;
00202         InstructionVector _instructions;
00205         ir::ControlFlowGraph::iterator _block;
00206 
00207       private:
00209         static bool _equal( const RegisterSet& one, 
00210           const RegisterSet& two );
00211 
00212       private:
00214         void _resolveTypes( DataflowGraph::Type& d,
00215           const DataflowGraph::Type& s );
00217         bool compute( bool hasFallthrough );
00218     
00219       public:
00221         Block( DataflowGraph& dfg, 
00222           ir::ControlFlowGraph::iterator block );
00224         Block( DataflowGraph& dfg, Type t = Invalid );
00225         
00226       public:
00228         const RegisterSet& aliveIn() const;
00230         const RegisterSet& aliveOut() const;
00232         RegisterSet& aliveIn();
00234         RegisterSet& aliveOut();
00236         BlockVector::iterator fallthrough() const;
00238         const BlockPointerSet& targets() const;
00240         const BlockPointerSet& predecessors() const;
00242         BlockPointerSet& targets();
00244         BlockPointerSet& predecessors();
00246         Type type() const;
00248         const InstructionVector& instructions() const;
00250         InstructionVector& instructions();
00252         const PhiInstructionVector& phis() const;
00254         PhiInstructionVector& phis();
00256         const std::string& label() const;
00258         ir::ControlFlowGraph::BasicBlock::Id id() const;
00260         ir::ControlFlowGraph::iterator block();
00261 
00262       public:
00264         const std::string* producer( const Register& r ) const;
00267         RegisterSet alive( const 
00268           InstructionVector::const_iterator& i );
00269     };
00270     
00271   public:
00273     typedef BlockVector::iterator iterator;
00275     typedef BlockVector::const_iterator const_iterator;
00277     typedef BlockVector::value_type value_type;
00279     typedef BlockVector::size_type size_type;
00281     typedef Block::RegisterSet RegisterSet;
00283     typedef RegisterSet::const_iterator register_iterator;
00284 
00286     typedef std::vector< iterator > BlockPointerVector;
00288     typedef BlockPointerVector::iterator pointer_iterator;    
00290     typedef BlockPointerVector::reverse_iterator 
00291       reverse_pointer_iterator;
00293     typedef std::unordered_map< ir::ControlFlowGraph::iterator, 
00294       iterator > IteratorMap;
00295 
00296   private:
00297     BlockVector _blocks;
00298     ir::ControlFlowGraph* _cfg;
00299     bool _consistent;
00300     bool _ssa;
00301     RegisterId _maxRegister;
00302 
00303   public:
00305     Instruction convert( ir::PTXInstruction& i );
00306 
00307   public:
00309     void analyze( ir::IRKernel& kernel );
00310 
00311   public:
00313     DataflowGraph();
00315     ~DataflowGraph();
00316     
00317   public:
00318     #ifndef _WIN32
00319     DataflowGraph(const DataflowGraph& ) = delete;
00320     DataflowGraph& operator=(const DataflowGraph& ) = delete;
00321     #endif
00322 
00323   public:
00325     iterator begin();
00327     const_iterator begin() const;
00329     iterator end();
00331     const_iterator end() const;
00332 
00333   public:     
00335     bool empty() const;
00337     size_type size() const;
00339     size_type max_size() const;
00340 
00341   public:
00348     iterator insert( iterator predecessor, const std::string& label );
00357     iterator insert( iterator predecessor, iterator successor, 
00358       const std::string& label );
00361     iterator split( iterator block, unsigned int instruction, 
00362       bool isFallthrough );
00365     iterator split( iterator block, InstructionVector::iterator position, 
00366       bool isFallthrough, const std::string& l );
00368     void redirect( iterator source, 
00369       iterator destination, iterator newTarget );
00371     void target( iterator block, iterator target,
00372       bool fallthrough = false );
00374     iterator erase( iterator block );
00376     void clear();
00377   
00378   public:
00381     void insert( iterator block, const ir::Instruction& instruction, 
00382       unsigned int index );
00385                 InstructionVector::iterator insert( iterator block, const ir::Instruction& instruction, 
00386       InstructionVector::iterator position );
00388     void insert( iterator block, const ir::Instruction& instruction );
00391     void erase( iterator block, InstructionVector::iterator position );
00394     void erase( iterator block, unsigned int index );
00395     
00396   public:
00398     void compute();
00400     void constructDUChains();
00401     void constructBlockDUChains(iterator blockIter);
00403     RegisterId maxRegister() const;
00406     RegisterId newRegister();
00407     
00408   public:
00410     void toSsa();
00412     void fromSsa();
00414     bool ssa() const;
00415     
00416   public:
00418     BlockPointerVector executableSequence();
00420     IteratorMap getCFGtoDFGMap();
00421 };
00422 
00423 std::ostream& operator<<( std::ostream& out, const DataflowGraph& graph );
00424 }
00425 
00426 namespace std
00427 {
00428   template<>
00429   struct hash< analysis::DataflowGraph::iterator >
00430   {
00431     inline size_t operator()(
00432       const analysis::DataflowGraph::iterator& it ) const
00433     {
00434       return ( size_t )it->id();
00435     }
00436   };
00437 
00438   template<>
00439   struct hash< analysis::DataflowGraph::Register >
00440   {
00441     inline size_t operator()(
00442       const analysis::DataflowGraph::Register& r ) const
00443     {
00444       return r.id;
00445     }
00446   };
00447 
00448   template<>
00449   struct hash< analysis::DataflowGraph::RegisterPointer >
00450   {
00451     inline size_t operator()(
00452       const analysis::DataflowGraph::RegisterPointer& r ) const
00453     {
00454       return *r.pointer;
00455     }
00456   };
00457 }
00458 
00459 #endif
00460 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines