DataflowGraph.h

Go to the documentation of this file.

#ifndef DATAFLOW_GRAPH_H_INCLUDED
#define DATAFLOW_GRAPH_H_INCLUDED

// Ocelot Includes
#include <ocelot/analysis/interface/Analysis.h>
#include <ocelot/ir/interface/ControlFlowGraph.h>
#include <ocelot/ir/interface/PTXInstruction.h>

// Hydrazine Includes
#include <hydrazine/implementation/debug.h>

// Standard Library Includes
#include <cassert>
#include <unordered_set>

#ifdef REPORT_BASE
#undef REPORT_BASE
#endif

#define REPORT_BASE 0

// Forward Declarations
namespace analysis { class SSAGraph; }

namespace analysis
{
class DataflowGraph : public KernelAnalysis
{
  friend class SSAGraph;
  public:     
    typedef ir::PTXOperand::DataType Type;
    typedef unsigned int RegisterId;
    typedef ir::ControlFlowGraph::InstructionList InstructionList;

    class RegisterPointer
    {
      public:
        Type type;
        RegisterId* pointer;
        
      public:
        RegisterPointer( RegisterId* id, Type type );
        
      public:
        bool operator==( const RegisterPointer& r ) const;
    };

    class Register
    {
      public:
        Type type;
        RegisterId id;
        
      public:
        Register( RegisterId id = 0, 
          Type type = ir::PTXOperand::TypeSpecifier_invalid );
        Register( const RegisterPointer& r );
        
      public:
        bool operator==( const Register& r ) const;
    };

    struct Register_Hash
    {
      inline std::size_t operator()( Register r ) const
      {
        return r.id;
      }
    };
    
    typedef std::vector< RegisterPointer > RegisterPointerVector;
    typedef std::vector< Register > RegisterVector;
    
    class NoProducerException : public std::exception
    {
      private:
        std::string _message;
      
      public:
        NoProducerException( RegisterId reg );
        ~NoProducerException() throw();
        const char* what() const throw();
    };

    
    class Block;
    class Instruction;
    class PhiInstruction;
    typedef std::list< Instruction > InstructionVector;
    typedef std::list< PhiInstruction > PhiInstructionVector;
    typedef std::list< Block > BlockVector;
    typedef std::list<InstructionVector::iterator> InstructionIteratorList;
    
    class Instruction
    {
      public:
        ir::Instruction* i;
        RegisterPointerVector d;
        RegisterPointerVector s;
        InstructionIteratorList uses;
        InstructionIteratorList defs;
        typedef InstructionIteratorList::iterator DUIterator;

    };
    
    class PhiInstruction
    {
      public:
        Register d;
        RegisterVector s;
    };

    struct BlockVector_Hash
    {
      inline std::size_t operator()( BlockVector::iterator it ) const
      {
        return (std::size_t)it->id();
      }
    };

    typedef std::unordered_set< BlockVector::iterator,
      BlockVector_Hash > BlockPointerSet;
    
    class Block
    {
      friend class SSAGraph;
      friend class DataflowGraph;
      friend class SyncEliminationPass;
      public:
        enum Type
        {
          Entry,
          Exit,
          Body,
          Invalid
        };
    
        typedef std::unordered_set< Register, Register_Hash > RegisterSet;

      private:
        RegisterSet _aliveIn;
        RegisterSet _aliveOut;
        BlockVector::iterator _fallthrough;
        BlockPointerSet _targets;
        BlockPointerSet _predecessors;
        Type _type;
        PhiInstructionVector _phis;
        InstructionVector _instructions;
        ir::ControlFlowGraph::iterator _block;

      private:
        static bool _equal( const RegisterSet& one, 
          const RegisterSet& two );

      private:
        void _resolveTypes( DataflowGraph::Type& d,
          const DataflowGraph::Type& s );
        bool compute( bool hasFallthrough );
    
      public:
        Block( DataflowGraph& dfg, 
          ir::ControlFlowGraph::iterator block );
        Block( DataflowGraph& dfg, Type t = Invalid );
        
      public:
        const RegisterSet& aliveIn() const;
        const RegisterSet& aliveOut() const;
        RegisterSet& aliveIn();
        RegisterSet& aliveOut();
        BlockVector::iterator fallthrough() const;
        const BlockPointerSet& targets() const;
        const BlockPointerSet& predecessors() const;
        BlockPointerSet& targets();
        BlockPointerSet& predecessors();
        Type type() const;
        const InstructionVector& instructions() const;
        InstructionVector& instructions();
        const PhiInstructionVector& phis() const;
        PhiInstructionVector& phis();
        const std::string& label() const;
        ir::ControlFlowGraph::BasicBlock::Id id() const;
        ir::ControlFlowGraph::iterator block();

      public:
        const std::string* producer( const Register& r ) const;
        RegisterSet alive( const 
          InstructionVector::const_iterator& i );
    };
    
  public:
    typedef BlockVector::iterator iterator;
    typedef BlockVector::const_iterator const_iterator;
    typedef BlockVector::value_type value_type;
    typedef BlockVector::size_type size_type;
    typedef Block::RegisterSet RegisterSet;
    typedef RegisterSet::const_iterator register_iterator;

    typedef std::vector< iterator > BlockPointerVector;
    typedef BlockPointerVector::iterator pointer_iterator;    
    typedef BlockPointerVector::reverse_iterator 
      reverse_pointer_iterator;
    typedef std::unordered_map< ir::ControlFlowGraph::iterator, 
      iterator > IteratorMap;

  private:
    BlockVector _blocks;
    ir::ControlFlowGraph* _cfg;
    bool _consistent;
    bool _ssa;
    RegisterId _maxRegister;

  public:
    Instruction convert( ir::PTXInstruction& i );

  public:
    void analyze( ir::IRKernel& kernel );

  public:
    DataflowGraph();
    ~DataflowGraph();
    
  public:
    #ifndef _WIN32
    DataflowGraph(const DataflowGraph& ) = delete;
    DataflowGraph& operator=(const DataflowGraph& ) = delete;
    #endif

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

  public:     
    bool empty() const;
    size_type size() const;
    size_type max_size() const;

  public:
    iterator insert( iterator predecessor, const std::string& label );
    iterator insert( iterator predecessor, iterator successor, 
      const std::string& label );
    iterator split( iterator block, unsigned int instruction, 
      bool isFallthrough );
    iterator split( iterator block, InstructionVector::iterator position, 
      bool isFallthrough, const std::string& l );
    void redirect( iterator source, 
      iterator destination, iterator newTarget );
    void target( iterator block, iterator target,
      bool fallthrough = false );
    iterator erase( iterator block );
    void clear();
  
  public:
    void insert( iterator block, const ir::Instruction& instruction, 
      unsigned int index );
                InstructionVector::iterator insert( iterator block, const ir::Instruction& instruction, 
      InstructionVector::iterator position );
    void insert( iterator block, const ir::Instruction& instruction );
    void erase( iterator block, InstructionVector::iterator position );
    void erase( iterator block, unsigned int index );
    
  public:
    void compute();
    void constructDUChains();
    void constructBlockDUChains(iterator blockIter);
    RegisterId maxRegister() const;
    RegisterId newRegister();
    
  public:
    void toSsa();
    void fromSsa();
    bool ssa() const;
    
  public:
    BlockPointerVector executableSequence();
    IteratorMap getCFGtoDFGMap();
};

std::ostream& operator<<( std::ostream& out, const DataflowGraph& graph );
}

namespace std
{
  template<>
  struct hash< analysis::DataflowGraph::iterator >
  {
    inline size_t operator()(
      const analysis::DataflowGraph::iterator& it ) const
    {
      return ( size_t )it->id();
    }
  };

  template<>
  struct hash< analysis::DataflowGraph::Register >
  {
    inline size_t operator()(
      const analysis::DataflowGraph::Register& r ) const
    {
      return r.id;
    }
  };

  template<>
  struct hash< analysis::DataflowGraph::RegisterPointer >
  {
    inline size_t operator()(
      const analysis::DataflowGraph::RegisterPointer& r ) const
    {
      return *r.pointer;
    }
  };
}

#endif