state_transition_graph_manager.cpp

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/>.
 *
 */
#include "state_transition_graph_manager.hpp"

#include "behavioral_helper.hpp"
#include "op_graph.hpp"

#include "generic_device.hpp"
#include "structural_manager.hpp"
#include "technology_manager.hpp"
#include "technology_node.hpp"

#include "fu_binding.hpp"
#include "function_behavior.hpp"
#include "hls.hpp"
#include "hls_device.hpp"
#include "hls_manager.hpp"

#include "Parameter.hpp"

#include "StateTransitionGraph_constructor.hpp"
#include "state_transition_graph.hpp"

#include "funit_obj.hpp"
#include "multi_unbounded_obj.hpp"

#include "var_pp_functor.hpp"

#include "dbgPrintHelper.hpp" // for DEBUG_LEVEL_
#include <boost/graph/topological_sort.hpp>

#define PP_MAX_CYCLES_BOUNDED "max-cycles-bounded"
#define DEFAULT_MAX_CYCLES_BOUNDED (8)

StateTransitionGraphManager::StateTransitionGraphManager(const HLS_managerConstRef _HLSMgr, hlsRef _HLS,
                                                         const ParameterConstRef _Param)
    : state_transition_graphs_collection(StateTransitionGraphsCollectionRef(new StateTransitionGraphsCollection(
          StateTransitionGraphInfoRef(new StateTransitionGraphInfo(
              _HLSMgr->CGetFunctionBehavior(_HLS->functionId)->CGetOpGraph(FunctionBehavior::CFG))),
          _Param))),
      ACYCLIC_STG_graph(StateTransitionGraphRef(new StateTransitionGraph(
          state_transition_graphs_collection, TransitionInfo::StateTransitionType::ST_EDGE_NORMAL))),
      STG_graph(StateTransitionGraphRef(new StateTransitionGraph(
          state_transition_graphs_collection, TransitionInfo::StateTransitionType::ST_EDGE_NORMAL |
                                                  TransitionInfo::StateTransitionType::ST_EDGE_FEEDBACK))),
      EPP_STG_graph(StateTransitionGraphRef(new StateTransitionGraph(
          state_transition_graphs_collection,
          TransitionInfo::StateTransitionType::ST_EDGE_NORMAL | TransitionInfo::StateTransitionType::ST_EDGE_EPP))),
      op_function_graph(_HLSMgr->CGetFunctionBehavior(_HLS->functionId)->CGetOpGraph(FunctionBehavior::CFG)),
      Param(_Param),
      output_level(_Param->getOption<int>(OPT_output_level)),
      debug_level(_Param->getOption<int>(OPT_debug_level)),
      _max_cycles_bounded(_Param->IsParameter(PP_MAX_CYCLES_BOUNDED) ?
                              _Param->GetParameter<unsigned int>(PP_MAX_CYCLES_BOUNDED) :
                              DEFAULT_MAX_CYCLES_BOUNDED),
      HLS(_HLS),
      STG_builder(StateTransitionGraph_constructorRef(
          new StateTransitionGraph_constructor(state_transition_graphs_collection, _HLSMgr, _HLS->functionId)))
{
   STG_builder->create_entry_state();
   STG_builder->create_exit_state();
}

StateTransitionGraphManager::~StateTransitionGraphManager() = default;

const StateTransitionGraphConstRef StateTransitionGraphManager::CGetAstg() const
{
   return ACYCLIC_STG_graph;
}

const StateTransitionGraphConstRef StateTransitionGraphManager::CGetStg() const
{
   return STG_graph;
}

const StateTransitionGraphConstRef StateTransitionGraphManager::CGetEPPStg() const
{
   return EPP_STG_graph;
}

void StateTransitionGraphManager::ComputeCyclesCount(bool is_pipelined)
{
   auto info = STG_graph->GetStateTransitionGraphInfo();
   if(info->is_a_dag && !Param->getOption<bool>(OPT_disable_bounded_function))
   {
      std::list<vertex> sorted_vertices;
      ACYCLIC_STG_graph->TopologicalSort(sorted_vertices);
      CustomUnorderedMap<vertex, unsigned int> CSteps_min, CSteps_max;
      bool has_dummy_state = false;
      for(const auto v : sorted_vertices)
      {
         CSteps_min[v] = 0;
         CSteps_max[v] = 0;
         has_dummy_state |= ACYCLIC_STG_graph->GetStateInfo(v)->is_dummy;
         InEdgeIterator ie, iend;
         boost::tie(ie, iend) = boost::in_edges(v, *ACYCLIC_STG_graph);
         const auto ie_first = ie;
         for(; ie != iend; ie++)
         {
            const auto src = boost::source(*ie, *ACYCLIC_STG_graph);
            CSteps_max[v] = std::max(CSteps_max[v], 1 + CSteps_max[src]);
            if(ie == ie_first)
            {
               CSteps_min[v] = 1 + CSteps_min[src];
            }
            else
            {
               CSteps_min[v] = std::min(CSteps_min[v], 1 + CSteps_max[src]);
            }
         }
      }
      THROW_ASSERT(CSteps_min.find(info->exit_node) != CSteps_min.end(), "Exit node not reachable");
      THROW_ASSERT(CSteps_max.find(info->exit_node) != CSteps_max.end(), "Exit node not reachable");
      info->min_cycles = CSteps_min.find(info->exit_node)->second - 1;
      info->max_cycles = CSteps_max.find(info->exit_node)->second - 1;
      info->bounded =
          is_pipelined || (info->min_cycles == info->max_cycles && info->max_cycles <= _max_cycles_bounded &&
                           info->min_cycles > 0 && !has_dummy_state);
   }
   else
   {
      THROW_ASSERT(Param->getOption<bool>(OPT_disable_bounded_function) || !is_pipelined,
                   "A pipelined function should always generate a DAG");
   }
}

vertex StateTransitionGraphManager::get_entry_state() const
{
   return STG_graph->CGetStateTransitionGraphInfo()->entry_node;
}

CustomOrderedSet<vertex> StateTransitionGraphManager::get_states(const vertex& op, StateTypes statetypes) const
{
   CustomOrderedSet<vertex> vertex_set;
   VertexIterator v, vend;
   for(boost::tie(v, vend) = boost::vertices(*STG_graph); v != vend; v++)
   {
      const std::list<vertex>* operations;
      switch(statetypes)
      {
         case EXECUTING:
            operations = &(STG_graph->CGetStateInfo(*v)->executing_operations);
            break;
         case STARTING:
            operations = &(STG_graph->CGetStateInfo(*v)->starting_operations);
            break;
         case ENDING:
            operations = &(STG_graph->CGetStateInfo(*v)->ending_operations);
            break;
         default:
            THROW_UNREACHABLE("Unknown state type. Which one are you lookig for?");
      }
      auto op_it_end = operations->end();
      bool stop_flag;
      stop_flag = false;
      for(auto op_it = operations->begin(); op_it != op_it_end && !stop_flag; ++op_it)
      {
         if(*op_it == op)
         {
            stop_flag = true;
            vertex_set.insert(*v);
         }
      }
   }
   THROW_ASSERT(vertex_set.size() > 0,
                "Something wrong! Operation " + GET_NAME(op_function_graph, op) + " is executed " + "into no states");
   return vertex_set;
}

CustomOrderedSet<vertex> StateTransitionGraphManager::get_ending_states(const vertex& op) const
{
   return get_states(op, StateTransitionGraphManager::StateTypes::ENDING);
}

CustomOrderedSet<vertex> StateTransitionGraphManager::get_starting_states(const vertex& op) const
{
   return get_states(op, StateTransitionGraphManager::StateTypes::STARTING);
}

CustomOrderedSet<vertex> StateTransitionGraphManager::get_execution_states(const vertex& op) const
{
   return get_states(op, StateTypes::EXECUTING);
}

vertex StateTransitionGraphManager::get_exit_state() const
{
   return STG_graph->CGetStateTransitionGraphInfo()->exit_node;
}

std::string StateTransitionGraphManager::get_state_name(vertex state) const
{
   return STG_graph->CGetStateInfo(state)->name;
}

StateTransitionGraphRef StateTransitionGraphManager::GetAstg()
{
   return ACYCLIC_STG_graph;
}

StateTransitionGraphRef StateTransitionGraphManager::GetStg()
{
   return STG_graph;
}

StateTransitionGraphRef StateTransitionGraphManager::GetEPPStg()
{
   return EPP_STG_graph;
}

unsigned int StateTransitionGraphManager::get_number_of_states() const
{
   return static_cast<unsigned int>(boost::num_vertices(*state_transition_graphs_collection) - 2);
}

void StateTransitionGraphManager::print_statistics() const
{
   INDENT_OUT_MEX(OUTPUT_LEVEL_MINIMUM, output_level, "---Number of states: " + STR(get_number_of_states()));
   INDENT_OUT_MEX(OUTPUT_LEVEL_VERY_PEDANTIC, output_level,
                  "---" + std::string("Is a DAG: ") +
                      (STG_graph->CGetStateTransitionGraphInfo()->is_a_dag ? "T" : "F"));
   if(STG_graph->CGetStateTransitionGraphInfo()->min_cycles != 0 &&
      STG_graph->CGetStateTransitionGraphInfo()->max_cycles != 0)
   {
      INDENT_OUT_MEX(OUTPUT_LEVEL_MINIMUM, output_level,
                     "---Minimum number of cycles: " + STR(STG_graph->CGetStateTransitionGraphInfo()->min_cycles));
      INDENT_OUT_MEX(OUTPUT_LEVEL_MINIMUM, output_level,
                     "---Maximum number of cycles " + STR(STG_graph->CGetStateTransitionGraphInfo()->max_cycles));
   }
}

void StateTransitionGraphManager::add_multi_unbounded_obj(vertex s, const CustomOrderedSet<vertex>& ops)
{
   if(multi_unbounded_table.find(s) == multi_unbounded_table.end())
   {
      multi_unbounded_table[s] =
          generic_objRef(new multi_unbounded_obj(s, ops, std::string("mu_") + STG_graph->CGetStateInfo(s)->name));
   }
}

void StateTransitionGraphManager::specialise_mu(structural_objectRef& mu_mod, generic_objRef mu) const
{
   INDENT_DBG_MEX(DEBUG_LEVEL_VERBOSE, HLS->debug_level, "---Specializing " + mu_mod->get_path());
   auto mut = GetPointer<multi_unbounded_obj>(mu);
   THROW_ASSERT(mut, "unexpected condition");
   structural_objectRef inOps = mu_mod->find_member("ops", port_vector_o_K, mu_mod);
   auto* port = GetPointer<port_o>(inOps);
   const auto& ops = mut->get_ops();
   auto n_in_ports = static_cast<unsigned int>(ops.size());
   port->add_n_ports(n_in_ports, inOps);
}

void StateTransitionGraphManager::add_to_SM(structural_objectRef clock_port, structural_objectRef reset_port)
{
   const auto& SM = HLS->datapath;
   const auto& circuit = SM->get_circ();
   INDENT_DBG_MEX(DEBUG_LEVEL_VERBOSE, debug_level, "-->Adding :multi-unbounded controllers");
   for(const auto& state2mu : multi_unbounded_table)
   {
      auto mu = state2mu.second;
      std::string name = mu->get_string();
      std::string library = HLS->HLS_D->get_technology_manager()->get_library(SIMPLEJOIN_STD);
      structural_objectRef mu_mod = SM->add_module_from_technology_library(name, SIMPLEJOIN_STD, library, circuit,
                                                                           HLS->HLS_D->get_technology_manager());
      specialise_mu(mu_mod, mu);

      structural_objectRef port_ck = mu_mod->find_member(CLOCK_PORT_NAME, port_o_K, mu_mod);
      SM->add_connection(clock_port, port_ck);
      structural_objectRef port_rst = mu_mod->find_member(RESET_PORT_NAME, port_o_K, mu_mod);
      SM->add_connection(reset_port, port_rst);
      mu->set_structural_obj(mu_mod);
      auto p_obj = mu_mod->find_member("sop", port_o_K, mu_mod);
      mu->set_out_sign(p_obj);
   }
   INDENT_DBG_MEX(DEBUG_LEVEL_VERBOSE, debug_level, "<--Adding :multi-unbounded controllers");
}