op_graph.hpp

Go to the documentation of this file.

/*
 *
 *                   _/_/_/    _/_/   _/    _/ _/_/_/    _/_/
 *                  _/   _/ _/    _/ _/_/  _/ _/   _/ _/    _/
 *                 _/_/_/  _/_/_/_/ _/  _/_/ _/   _/ _/_/_/_/
 *                _/      _/    _/ _/    _/ _/   _/ _/    _/
 *               _/      _/    _/ _/    _/ _/_/_/  _/    _/
 *
 *             ***********************************************
 *                              PandA Project
 *                     URL: http://panda.dei.polimi.it
 *                       Politecnico di Milano - DEIB
 *                        System Architectures Group
 *             ***********************************************
 *              Copyright (C) 2004-2024 Politecnico di Milano
 *
 *   This file is part of the PandA framework.
 *
 *   The PandA framework is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
#ifndef OP_GRAPH_HPP
#define OP_GRAPH_HPP

#include "config_HAVE_HLS_BUILT.hpp"
#include "config_HAVE_UNORDERED.hpp"

#include "cdfg_edge_info.hpp"
#include "graph.hpp"
#include "typed_node_info.hpp"

#include "function_behavior.hpp"

#include <boost/graph/graph_traits.hpp> // for graph_traits<>::...
#include <iosfwd>                       // for ostream
#include <limits>                       // for numeric_limits
#include <list>                         // for list
#include <set>                          // for set
#include <string>                       // for string

#include "custom_map.hpp"
#include "custom_set.hpp"
#include "refcount.hpp"
#include "strong_typedef.hpp" // for UINT_STRONG_TYPEDEF

CONSTREF_FORWARD_DECL(BehavioralHelper);
enum class FunctionBehavior_VariableAccessType;
CONSTREF_FORWARD_DECL(hls);
class OpVertexSet;

UINT_STRONG_TYPEDEF(MemoryAddress);
#define ENTRY_ID (std::numeric_limits<unsigned int>::max())
#define EXIT_ID (std::numeric_limits<unsigned int>::max() - 1)

#define TYPE_OPAQUE 1 << 0

#define TYPE_EXTERNAL 1 << 4

#define TYPE_IF 1 << 5

#define TYPE_SWITCH 1 << 6

#define TYPE_WHILE 1 << 7

#define TYPE_FOR 1 << 8

#define TYPE_DO 1 << 9

#define TYPE_ASSIGN 1 << 10

#define TYPE_NOP 1 << 11

#define TYPE_PHI 1 << 12

#define TYPE_RET 1 << 13

#define TYPE_TO_BE_REMOVED 1 << 14

#define TYPE_LABEL 1 << 15

#define TYPE_GOTO 1 << 16

#define TYPE_VPHI 1 << 17

#define TYPE_INIT 1 << 18

#define TYPE_LOAD 1 << 19

#define TYPE_STORE 1 << 20

#define TYPE_MEMCPY 1 << 21

#define TYPE_WAS_GIMPLE_PHI 1 << 22

#define TYPE_FIRST_OP 1 << 23

#define TYPE_LAST_OP 1 << 24

#define TYPE_MULTIIF 1 << 25

#define TYPE_ATOMIC 1 << 26

#define TYPE_PREDICATED 1 << 27

#define TYPE_RW 1 << 28


#define ASSIGN "ASSIGN"
#if 0

#define STORE "STORE"
#define PREDICATED_STORE "PREDICATED_STORE"

#define LOAD "LOAD"
#define PREDICATED_LOAD "PREDICATED_LOAD"
#endif

#define ASSERT_EXPR "assert_expr"

#define EXTRACT_BIT_EXPR "extract_bit_expr"

#define LUT_EXPR "lut_expr"

#define READ_COND "READ_COND"

#define MULTI_READ_COND "MULTI_READ_COND"

#define SWITCH_COND "SWITCH_COND"

#define GIMPLE_LABEL "gimple_label"

#define GIMPLE_GOTO "gimple_goto"

#define NOP "NOP"

#define GIMPLE_RETURN "gimple_return"

#define GIMPLE_NOP "gimple_nop"

#define GIMPLE_PHI "gimple_phi"

#define GIMPLE_ASM "gimple_asm"

#define GIMPLE_PRAGMA "gimple_pragma"

#define MEMCPY "__internal_bambu_memcpy"

#define MEMCMP "memcmp"

#define MEMSET "__internal_bambu_memset"

#define VECT_CONCATENATION "VECT_CONCATENATION"

#define ADDR_EXPR "addr_expr"

#define NOP_EXPR "nop_expr"

#define FLOAT_EXPR "float_expr"

#define FIX_TRUNC_EXPR "fix_trunc_expr"

#define CONVERT_EXPR "convert_expr"

#define VIEW_CONVERT_EXPR "view_convert_expr"

#define BUILTIN_WAIT_CALL "__builtin_wait_call"

struct OpNodeInfo : public TypedNodeInfo
{
   CustomSet<unsigned int> cited_variables;

   CustomMap<FunctionBehavior_VariableType, CustomMap<FunctionBehavior_VariableAccessType, CustomSet<unsigned int>>>
       variables;

   std::list<unsigned int> actual_parameters;

   tree_nodeRef node;

   CustomSet<unsigned int> called;

   unsigned int bb_index;

   unsigned int cer;

   OpNodeInfo();

   ~OpNodeInfo() override;

   void Initialize();

   const CustomSet<unsigned int>& GetVariables(const FunctionBehavior_VariableType variable_type,
                                               const FunctionBehavior_VariableAccessType access_type) const;

   const std::string GetOperation() const;

   unsigned int GetNodeId() const;

   void Print(std::ostream& stream, const BehavioralHelperConstRef behavioral_helper, const bool dotty_format) const;
};
using OpNodeInfoRef = refcount<OpNodeInfo>;
using OpNodeInfoConstRef = refcount<const OpNodeInfo>;

#define GET_BB_INDEX(data, vertex_index) Cget_node_info<OpNodeInfo>(vertex_index, *(data))->bb_index

#define GET_CER(data, vertex_index) Cget_node_info<OpNodeInfo>(vertex_index, *(data))->cer

#define DFG_SCA_SELECTOR 1 << 7
#define DFG_AGG_SELECTOR 1 << 8
#define DFG_SELECTOR (DFG_SCA_SELECTOR | DFG_AGG_SELECTOR)
#define FB_DFG_SCA_SELECTOR 1 << 9
#define FB_DFG_AGG_SELECTOR 1 << 10
#define FB_DFG_SELECTOR (FB_DFG_SCA_SELECTOR | FB_DFG_AGG_SELECTOR)
#define FDFG_SELECTOR (DFG_SELECTOR | FB_DFG_SELECTOR)

#define ADG_SCA_SELECTOR 1 << 11
#define ADG_AGG_SELECTOR 1 << 12
#define ADG_SELECTOR (ADG_SCA_SELECTOR | ADG_AGG_SELECTOR)
#define FB_ADG_SCA_SELECTOR 1 << 13
#define FB_ADG_AGG_SELECTOR 1 << 14
#define FB_ADG_SELECTOR (FB_ADG_SCA_SELECTOR | FB_ADG_AGG_SELECTOR)
#define FADG_SELECTOR (ADG_SELECTOR | FB_ADG_SELECTOR)

#define ODG_SCA_SELECTOR 1 << 15
#define ODG_AGG_SELECTOR 1 << 16
#define ODG_SELECTOR (ODG_SCA_SELECTOR | ODG_AGG_SELECTOR)
#define FB_ODG_SCA_SELECTOR 1 << 17
#define FB_ODG_AGG_SELECTOR 1 << 18
#define FB_ODG_SELECTOR (FB_ODG_SCA_SELECTOR | FB_ODG_AGG_SELECTOR)
#define FODG_SELECTOR (ODG_SELECTOR | FB_ODG_SELECTOR)

#define SDG_SELECTOR (CDG_SELECTOR | DFG_SELECTOR)
#define FSDG_SELECTOR (FCDG_SELECTOR | FDFG_SELECTOR)
#define RSDG_SELECTOR (TRED_SELECTOR)

#define FSADG_SELECTOR \
   (CDG_SELECTOR | DFG_SELECTOR | ADG_SELECTOR | FB_CDG_SELECTOR | FB_DFG_SELECTOR | FB_ADG_SELECTOR)
#define SAODG_SELECTOR (CDG_SELECTOR | DFG_SELECTOR | ADG_SELECTOR | ODG_SELECTOR)
#define FADFG_SELECTOR (DFG_SELECTOR | ADG_SELECTOR)

#define CSG_SELECTOR 1 << 19
#define SG_SELECTOR (CSG_SELECTOR | DFG_SELECTOR | ADG_SELECTOR | ODG_SELECTOR | FLG_SELECTOR)

#define RPDG_SELECTOR 1 << 20

#define FLG_SELECTOR 1 << 21

#define FB_FLG_SELECTOR 1 << 22

#define DEBUG_SELECTOR 1 << 23

class OpEdgeInfo : public CdfgEdgeInfo
{
 public:
   OpEdgeInfo();

   ~OpEdgeInfo() override;

   bool FlgEdgeT() const;

   bool FlgEdgeF() const;
};
using OpEdgeInfoRef = refcount<OpEdgeInfo>;
using OpEdgeInfoConstRef = refcount<const OpEdgeInfo>;

struct OpGraphInfo : public GraphInfo
{
   OpGraphInfo();

   ~OpGraphInfo() override;

   vertex entry_vertex;

   vertex exit_vertex;

   const BehavioralHelperConstRef BH;

   CustomMap<unsigned int, vertex> tree_node_to_operation;

   explicit OpGraphInfo(const BehavioralHelperConstRef BH);
};

using OpGraphInfoRef = refcount<OpGraphInfo>;
using OpGraphInfoConstRef = refcount<const OpGraphInfo>;

#if HAVE_UNORDERED

class OpVertexSet : public CustomUnorderedSet<vertex>
{
 public:
   explicit OpVertexSet(const OpGraphConstRef op_graph);
};

template <typename value>
class OpVertexMap : public CustomUnorderedMap<vertex, value>
{
 public:
   explicit OpVertexMap(const OpGraphConstRef) : CustomUnorderedMap<vertex, value>()
   {
   }
};

class OpEdgeSet : public CustomUnorderedSet<EdgeDescriptor>
{
 public:
   explicit OpEdgeSet(const OpGraphConstRef op_graph);
};
#else
class OpVertexSorter : std::binary_function<vertex, vertex, bool>
{
 private:
   OpGraphConstRef op_graph;

 public:
   explicit OpVertexSorter(const OpGraphConstRef op_graph);

   bool operator()(const vertex x, const vertex y) const;
};

class OpVertexSet : public std::set<vertex, OpVertexSorter>
{
 public:
   explicit OpVertexSet(const OpGraphConstRef op_graph);
};

template <typename value>
class OpVertexMap : public std::map<vertex, value, OpVertexSorter>
{
 public:
   explicit OpVertexMap(const OpGraphConstRef op_graph)
       : std::map<vertex, value, OpVertexSorter>(OpVertexSorter(op_graph))
   {
   }
};

class OpEdgeSorter : std::binary_function<EdgeDescriptor, EdgeDescriptor, bool>
{
 private:
   OpGraphConstRef op_graph;

 public:
   explicit OpEdgeSorter(const OpGraphConstRef op_graph);

   bool operator()(const EdgeDescriptor x, const EdgeDescriptor y) const;
};

class OpEdgeSet : public std::set<EdgeDescriptor, OpEdgeSorter>
{
 public:
   explicit OpEdgeSet(const OpGraphConstRef op_graph);
};
#endif

class OpGraphsCollection : public graphs_collection
{
 protected:
   OpVertexSet operations;

 public:
   OpGraphsCollection(const OpGraphInfoRef info, const ParameterConstRef parameters);

   ~OpGraphsCollection() override;

   inline EdgeDescriptor AddEdge(const vertex source, const vertex target, const int selector)
   {
      if(ExistsEdge(source, target))
      {
         return AddSelector(source, target, selector);
      }
      else
      {
         return InternalAddEdge(source, target, selector, EdgeInfoRef(new OpEdgeInfo()));
      }
   }

   boost::graph_traits<boost_graphs_collection>::vertex_descriptor AddVertex(const NodeInfoRef info) override;

   void RemoveVertex(boost::graph_traits<boost_graphs_collection>::vertex_descriptor v) override;

   const OpVertexSet CGetOperations() const;

   void Clear();
};

using OpGraphsCollectionRef = refcount<OpGraphsCollection>;

struct OpGraph : public graph
{
   friend class Schedule;

 public:
   OpGraph(const OpGraphsCollectionRef _op_graphs_collection, int selector);

   OpGraph(const OpGraphsCollectionRef _op_graphs_collection, int selector,
           const CustomUnorderedSet<boost::graph_traits<OpGraphsCollection>::vertex_descriptor>& sub);

   ~OpGraph() override;

   void WriteDot(const std::string& file_name, const int detail_level = 0) const;

#if HAVE_HLS_BUILT

   void WriteDot(const std::string& file_name, const hlsConstRef HLS,
                 const CustomSet<unsigned int> critical_paths) const;
#endif

   inline OpNodeInfoRef GetOpNodeInfo(const vertex node)
   {
      return RefcountCast<OpNodeInfo>(graph::GetNodeInfo(node));
   }

   inline const OpNodeInfoConstRef CGetOpNodeInfo(const vertex node) const
   {
      return RefcountCast<const OpNodeInfo>(graph::CGetNodeInfo(node));
   }

   inline const OpEdgeInfoConstRef CGetOpEdgeInfo(const EdgeDescriptor edge) const
   {
      return RefcountCast<const OpEdgeInfo>(graph::CGetEdgeInfo(edge));
   }

   inline OpGraphInfoRef GetOpGraphInfo()
   {
      return RefcountCast<OpGraphInfo>(GetGraphInfo());
   }

   inline const OpGraphInfoConstRef CGetOpGraphInfo() const
   {
      return RefcountCast<const OpGraphInfo>(CGetGraphInfo());
   }

   inline OpGraphInfoRef CGetOpGraphInfo()
   {
      return RefcountCast<OpGraphInfo>(GetGraphInfo());
   }

   CustomUnorderedMap<vertex, OpVertexSet> GetSrcVertices(const OpVertexSet& toCheck, int edgeType) const;

   const OpVertexSet CGetOperations() const;

#if HAVE_UNORDERED
   boost::iterator_range<InEdgeIterator> CGetInEdges(const vertex v) const;
#else
   OpEdgeSet CGetInEdges(const vertex v) const;
#endif

#if HAVE_UNORDERED
   boost::iterator_range<OutEdgeIterator> CGetOutEdges(const vertex v) const;
#else
   OpEdgeSet CGetOutEdges(const vertex v) const;
#endif
};
using OpGraphRef = refcount<OpGraph>;
using OpGraphConstRef = refcount<const OpGraph>;

#endif