state_transition_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 STATE_TRANSTION_GRAPH_HPP
#define STATE_TRANSTION_GRAPH_HPP

#include <edge_info.hpp>
#include <graph_info.hpp>
#include <node_info.hpp>

#include <graph.hpp>

#include "custom_set.hpp"

#include "refcount.hpp"
#include "string_manipulation.hpp" // for STR

CONSTREF_FORWARD_DECL(BehavioralHelper);
class HLS_manager;
CONSTREF_FORWARD_DECL(OpGraph);
REF_FORWARD_DECL(Parameter);

struct StateInfo : public NodeInfo
{
   Wrefcount<const HLS_manager> HLSMgr;

   unsigned int funId;

   std::string name;

   std::list<vertex> executing_operations;

   std::list<vertex> starting_operations;

   std::list<vertex> ending_operations;

   std::list<vertex> onfly_operations;

   CustomOrderedSet<unsigned int> BB_ids;

   bool is_dummy;

   bool is_duplicated;

   unsigned int sourceBb;

   bool isOriginalState;

   vertex clonedState;

   bool all_paths;

   CustomOrderedSet<unsigned int> moved_op_def_set;

   CustomOrderedSet<unsigned int> moved_op_use_set;

   std::list<vertex> moved_exec_op;

   std::list<vertex> moved_ending_op;

   unsigned int loopId;

   void print(std::ostream& os, const int detail_level) const override;

   StateInfo()
       : funId(0),
         is_dummy(false),
         is_duplicated(false),
         sourceBb(0),
         isOriginalState(false),
         clonedState(NULL_VERTEX),
         all_paths(false),
         loopId(0)
   {
   }
};
using StateInfoRef = refcount<StateInfo>;
using StateInfoConstRef = refcount<const StateInfo>;

enum transition_type : int
{
   DONTCARE_COND = 0,
   TRUE_COND,
   FALSE_COND,
   CASE_COND,
   ALL_FINISHED,
   NOT_ALL_FINISHED
};

class TransitionInfo : public EdgeInfo
{
 private:
   OpGraphConstRef op_function_graph;

   transition_type t{DONTCARE_COND};
   CustomOrderedSet<vertex> ops;
   bool has_default{false};
   CustomOrderedSet<unsigned> labels;
   vertex ref_state{NULL_VERTEX};
   size_t epp_increment{0};
   bool epp_incrementValid{false};

 public:
   explicit TransitionInfo(OpGraphConstRef g) : op_function_graph(g)
   {
   }

   friend class StateTransitionGraph_constructor;

   void print(std::ostream& os, const int detail_level) const;

   bool get_has_default() const
   {
      return has_default;
   }
   transition_type get_type() const
   {
      return t;
   }
   const CustomOrderedSet<vertex>& get_operations() const
   {
      return ops;
   }
   vertex get_operation() const;
   const CustomOrderedSet<unsigned>& get_labels() const
   {
      return labels;
   }
   vertex get_ref_state() const;

   enum StateTransitionType
   {
      ST_EDGE_NORMAL = 1 << 0,
      ST_EDGE_FEEDBACK = 1 << 1,
      ST_EDGE_EPP = 1 << 2,
   };

   void set_epp_increment(size_t n)
   {
      epp_increment = n;
      epp_incrementValid = true;
   }
   size_t get_epp_increment() const
   {
      return epp_increment;
   }
};
using TransitionInfoRef = refcount<TransitionInfo>;
using TransitionInfoConstRef = refcount<const TransitionInfo>;

struct StateTransitionGraphInfo : public GraphInfo
{
   const OpGraphConstRef op_function_graph;

   vertex entry_node;

   vertex exit_node;

   bool is_a_dag;

   bool bounded;

   unsigned int min_cycles;
   unsigned int max_cycles;

   std::map<unsigned int, vertex> state_id_to_vertex;

   std::map<vertex, unsigned int> vertex_to_state_id;

   explicit StateTransitionGraphInfo(const OpGraphConstRef op_function_graph);

   friend class StateTransitionGraph_constructor;
};
using StateTransitionGraphInfoRef = refcount<StateTransitionGraphInfo>;
using StateTransitionGraphInfoConstRef = refcount<const StateTransitionGraphInfo>;

class StateTransitionGraphsCollection : public graphs_collection
{
 public:
   StateTransitionGraphsCollection(const StateTransitionGraphInfoRef state_transition_graph_info,
                                   const ParameterConstRef parameters);

   ~StateTransitionGraphsCollection() override;

   inline EdgeDescriptor AddEdge(const vertex source, const vertex target, const int selector,
                                 const TransitionInfoRef info)
   {
      THROW_ASSERT(not ExistsEdge(source, target), "Trying to create an already existing edge");
      return InternalAddEdge(source, target, selector, RefcountCast<EdgeInfo>(info));
   }
};
using StateTransitionGraphsCollectionRef = refcount<StateTransitionGraphsCollection>;
using StateTransitionGraphsCollectionConstRef = refcount<const StateTransitionGraphsCollection>;

struct StateTransitionGraph : public graph
{
 public:
   StateTransitionGraph(const StateTransitionGraphsCollectionRef state_transition_graphs_collection, int selector);

   StateTransitionGraph(const StateTransitionGraphsCollectionRef state_transition_graphs_collection, int selector,
                        CustomUnorderedSet<vertex>& sub);

   ~StateTransitionGraph() override;

   inline StateInfoRef GetStateInfo(const vertex state)
   {
      return RefcountCast<StateInfo>(graph::GetNodeInfo(state));
   }

   inline const StateInfoConstRef CGetStateInfo(const vertex state) const
   {
      return RefcountCast<const StateInfo>(graph::CGetNodeInfo(state));
   }

   inline const StateInfoConstRef CGetStateInfo(unsigned int state_id) const
   {
      return CGetStateInfo(GetVertex(state_id));
   }

   inline vertex GetVertex(unsigned int state_id) const
   {
      THROW_ASSERT(CGetStateTransitionGraphInfo()->state_id_to_vertex.find(state_id) !=
                       CGetStateTransitionGraphInfo()->state_id_to_vertex.end(),
                   "State ID " + STR(state_id) + " was not stored");
      return CGetStateTransitionGraphInfo()->state_id_to_vertex.at(state_id);
   }

   inline TransitionInfoRef GetTransitionInfo(const EdgeDescriptor transition)
   {
      return RefcountCast<TransitionInfo>(graph::GetEdgeInfo(transition));
   }

   inline const TransitionInfoConstRef CGetTransitionInfo(const EdgeDescriptor transition) const
   {
      return RefcountCast<const TransitionInfo>(graph::CGetEdgeInfo(transition));
   }

   inline StateTransitionGraphInfoRef GetStateTransitionGraphInfo()
   {
      return RefcountCast<StateTransitionGraphInfo>(graph::GetGraphInfo());
   }

   inline const StateTransitionGraphInfoConstRef CGetStateTransitionGraphInfo() const
   {
      return RefcountCast<const StateTransitionGraphInfo>(graph::CGetGraphInfo());
   }

   void WriteDot(const std::string& file_name, const int detail_level = 0) const;
};
using StateTransitionGraphRef = refcount<StateTransitionGraph>;
using StateTransitionGraphConstRef = refcount<const StateTransitionGraph>;

class StateWriter : public VertexWriter
{
 private:
   const BehavioralHelperConstRef BH;

   const OpGraphConstRef op_function_graph;

   vertex entry_node;

   vertex exit_node;

 public:
   StateWriter(const graph* _stg, const OpGraphConstRef _op_function_graph, int _detail_level);

   void operator()(std::ostream& out, const vertex& v) const override;
};

class TransitionWriter : public EdgeWriter
{
 private:
   const BehavioralHelperConstRef BH;

   const OpGraphConstRef op_function_graph;

 public:
   TransitionWriter(const graph* stg, const OpGraphConstRef op_function_graph, int _detail_level);

   void operator()(std::ostream& out, const EdgeDescriptor& e) const override;
};

class last_intermediate_state
{
 public:
   last_intermediate_state(StateTransitionGraphConstRef input_state_graph, bool enable)
       : state_graph(input_state_graph), pipeline(enable)
   {
   }

   vertex operator()(vertex top, vertex bottom)
   {
      if(not pipeline)
      {
         return top;
      }
      graph::in_edge_iterator in_edge, in_edge_end;
#if HAVE_ASSERTS
      bool multiple_in_edges = false;
#endif
      vertex ret_v = NULL_VERTEX;
      for(boost::tie(in_edge, in_edge_end) = boost::in_edges(bottom, *state_graph); in_edge != in_edge_end; ++in_edge)
      {
         ret_v = boost::source(*in_edge, *state_graph);
         THROW_ASSERT(not multiple_in_edges, "A pipeline should not contain phi operations");
#if HAVE_ASSERTS
         multiple_in_edges = true;
#endif
      }
      THROW_ASSERT(multiple_in_edges, "No input edge found");
      return ret_v;
   }

 private:
   const StateTransitionGraphConstRef state_graph;
   bool pipeline;
};

class next_unique_state
{
 public:
   explicit next_unique_state(StateTransitionGraphConstRef input_state_graph) : state_graph(input_state_graph)
   {
   }

   vertex operator()(vertex state)
   {
      graph::out_edge_iterator out_edge, out_edge_end;
#if HAVE_ASSERTS
      bool multiple_out_edges = false;
#endif
      vertex next_state = NULL_VERTEX;
      for(boost::tie(out_edge, out_edge_end) = boost::out_edges(state, *state_graph); out_edge != out_edge_end;
          ++out_edge)
      {
         next_state = boost::target(*out_edge, *state_graph);
         THROW_ASSERT(not multiple_out_edges, "First state has multiple out edges");
#if HAVE_ASSERTS
         multiple_out_edges = true;
#endif
      }
      THROW_ASSERT(multiple_out_edges, "No output edge found");
      return next_state;
   }

 private:
   const StateTransitionGraphConstRef state_graph;
};
#endif