allocation_information.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 ALLOCATION_SOLUTION_HPP
#define ALLOCATION_SOLUTION_HPP

#include "hls_function_ir.hpp"

#include "graph.hpp" // for vertex
#include "hash_helper.hpp"
#include "hls_manager.hpp" // for HLS_manager, HLS_manager::io_binding_type
#include "op_graph.hpp"    // for OpGraphConstRef
#include "refcount.hpp"    // for CONSTREF_FORWARD_DECL, REF_FORWARD_DECL
#include "schedule.hpp"
#include "strong_typedef.hpp" // for UINT_STRONG_TYPEDEF_FORWARD_DECL

#include <cstddef> // for size_t
#include <iosfwd>  // for ostream
#include <string>  // for string
#include <utility> // for pair

CONSTREF_FORWARD_DECL(AllocationInformation);
CONSTREF_FORWARD_DECL(BehavioralHelper);
UINT_STRONG_TYPEDEF_FORWARD_DECL(ControlStep);
CONSTREF_FORWARD_DECL(HLS_constraints);
CONSTREF_FORWARD_DECL(HLS_manager);
CONSTREF_FORWARD_DECL(HLS_device);
CONSTREF_FORWARD_DECL(Parameter);
CONSTREF_FORWARD_DECL(Schedule);
enum class Allocation_MinMax;
CONSTREF_FORWARD_DECL(hls);
CONSTREF_FORWARD_DECL(memory);
REF_FORWARD_DECL(node_kind_prec_info);
REF_FORWARD_DECL(technology_node);
CONSTREF_FORWARD_DECL(tree_manager);
struct updatecopy_HLS_constraints_functor;
struct operation;

#define GIMPLE_RETURN_STD "gimple_return_FU"
#define GIMPLE_PHI_STD "gimple_phi_FU"
#define GIMPLE_ASM_STD "gimple_asm_FU"
#define GIMPLE_LABEL_STD "gimple_label_FU"
#define GIMPLE_GOTO_STD "gimple_goto_FU"
#define GIMPLE_NOP_STD "gimple_nop_FU"
#define GIMPLE_PRAGMA_STD "gimple_pragma_FU"
#define READ_COND_STD "read_cond_FU"
#define MULTI_READ_COND_STD "multi_read_cond_FU"
#define SWITCH_COND_STD "switch_cond_FU"
#define ENTRY_STD "entry_FU"
#define EXIT_STD "exit_FU"
#define NOP_STD "nop_FU"

#define ALLOCATION_MUX_MARGIN 1.0

class AllocationInformation : public HLSFunctionIR
{
 private:
   friend class allocation;
   friend struct updatecopy_HLS_constraints_functor;

   double connection_time_ratio;

   double controller_delay_multiplier;

   double setup_multiplier;

   double time_multiplier;

   double mux_time_multiplier;

   double memory_correction_coefficient;

   double connection_offset;

   double output_DSP_connection_time;

   double output_carry_connection_time;

   double fanout_coefficient;

   size_t max_fanout_size{0};

   double DSPs_margin;

   double DSPs_margin_stage;

   double DSP_allocation_coefficient;

   OpGraphConstRef op_graph;

   HLS_constraintsConstRef HLS_C;

   HLS_deviceConstRef HLS_D;

   BehavioralHelperConstRef behavioral_helper;

   memoryConstRef Rmem;

   const unsigned int& address_bitsize;

   tree_managerConstRef TreeM;

   double minimumSlack;

   unsigned int n_complex_operations{0};

   CustomUnorderedMap<unsigned int, std::pair<std::string, std::string>> id_to_fu_names;

   CustomOrderedSet<unsigned int> is_vertex_bounded_rel;

   std::vector<technology_nodeRef> list_of_FU;

   std::map<unsigned int, unsigned int> memory_units;

   std::map<unsigned int, unsigned int> nports_map;

   std::map<unsigned int, unsigned long long> precision_map;

   std::map<unsigned int, std::string> proxy_function_units;

   std::map<unsigned int, unsigned int> proxy_memory_units;

   std::map<unsigned int, std::string> proxy_wrapped_units;

   std::vector<unsigned int> tech_constraints;

   CustomUnorderedMap<std::pair<unsigned int, std::string>, CustomOrderedSet<unsigned int>> node_id_to_fus;

   CustomUnorderedMap<unsigned int, CustomOrderedSet<unsigned int>> fus_to_node_id;

   CustomUnorderedMap<unsigned int, std::pair<std::string, unsigned int>> binding;

   std::map<unsigned int, unsigned long long> memory_units_sizes;

   std::map<unsigned int, unsigned int> vars_to_memory_units;

   std::map<std::string, std::string> precomputed_pipeline_unit;

   CustomUnorderedSet<unsigned int> single_bool_test_cond_expr_units;

   CustomUnorderedSet<unsigned int> simple_pointer_plus_expr;

   mutable CustomMap<unsigned int, CustomSet<unsigned int>> ssa_roots;

   mutable CustomMap<unsigned int, std::pair<unsigned int, AbsControlStep>> ssa_bb_versions;

   mutable CustomMap<unsigned int, CustomSet<unsigned int>> ssa_cond_exprs;

   mutable CustomMap<unsigned int, unsigned int> cond_expr_bb_versions;

   mutable CustomMap<unsigned int, CustomSet<unsigned int>> zero_distance_ops;

   mutable CustomMap<unsigned int, unsigned int> zero_distance_ops_bb_version;

   CustomMap<unsigned long long, CustomUnorderedMapStable<unsigned int, double>> mux_timing_db;

   CustomMap<unsigned long long, CustomUnorderedMapStable<unsigned int, double>> mux_area_db;

   std::vector<unsigned int> DSP_x_db;

   std::vector<unsigned int> DSP_y_db;

   std::map<unsigned int, std::string> sync_ram_var_latency;

   std::string get_latency_string(const std::string& lat) const;

   double time_m_execution_time(operation* op) const;

   double time_m_stage_period(operation* op) const;

   double get_execution_time_dsp_modified(const unsigned int fu_name, const technology_nodeRef& node_op) const;

   double get_stage_period_dsp_modified(const unsigned int fu_name, const technology_nodeRef& node_op) const;

   double get_worst_stage_period(const unsigned int fu_name) const;

   void set_number_channels(unsigned int fu_name, unsigned int n_ports);

   void GetNodeTypePrec(const vertex node, const OpGraphConstRef g, node_kind_prec_infoRef info,
                        HLS_manager::io_binding_type& constant_id, bool is_constrained) const;

   static technology_nodeRef get_fu(const std::string& fu_name, const HLS_managerConstRef hls_manager);

   double GetPhiConnectionLatency(const unsigned int statement_index) const;

   bool CanBeMerged(const unsigned int first_operation, const unsigned int second_operation) const;

   CustomSet<unsigned int> ComputeRoots(const unsigned int ssa, const AbsControlStep cs) const;

   CustomSet<unsigned int> ComputeDrivenCondExpr(const unsigned int ssa) const;

   static const std::pair<const CustomMap<unsigned long long, CustomUnorderedMapStable<unsigned int, double>>&,
                          const CustomMap<unsigned long long, CustomUnorderedMapStable<unsigned int, double>>&>
   InitializeMuxDB(const AllocationInformationConstRef allocation_information);

   static const std::tuple<const std::vector<unsigned int>&, const std::vector<unsigned int>&>
   InitializeDSPDB(const AllocationInformationConstRef allocation_information);

   double GetToDspRegisterDelay(const unsigned int statement_index) const;

   CustomSet<unsigned int> GetZeroDistanceOperations(const unsigned int statement_index) const;

 public:
   AllocationInformation(const HLS_managerRef _hls_manager, const unsigned int _function_index,
                         const ParameterConstRef parameters);

   void Initialize() override;

   void Clear() override;

   enum op_target
   {
      initiation_time,
      power_consumption,
      execution_time
   };

   ~AllocationInformation() override;

   const CustomOrderedSet<unsigned int>& can_implement_set(const vertex v) const;
   const CustomOrderedSet<unsigned int>& can_implement_set(const unsigned int v) const;

   bool CanImplementSetNotEmpty(const unsigned int v) const;

   std::pair<std::string, std::string> get_fu_name(unsigned int id) const;

   unsigned int get_number_fu(unsigned int fu_name) const;

   unsigned int get_number_fu_types() const;

   double get_execution_time(const unsigned int fu_name, const vertex v, const OpGraphConstRef g) const;
   double get_execution_time(const unsigned int fu_name, const unsigned int v) const;

   ControlStep op_et_to_cycles(double et, double clock_period) const;

   unsigned int max_number_of_resources(const vertex v) const;

   unsigned int max_number_of_operations(unsigned int fu) const;

   double get_attribute_of_fu_per_op(const vertex v, const OpGraphConstRef g,
                                     const Allocation_MinMax allocation_min_max, op_target target,
                                     unsigned int& fu_name, bool& flag,
                                     const updatecopy_HLS_constraints_functor* CF = nullptr) const;

   double get_attribute_of_fu_per_op(const vertex v, const OpGraphConstRef g,
                                     const Allocation_MinMax allocation_min_max, op_target target) const;

   unsigned int min_number_of_resources(const vertex v) const;

   double get_setup_hold_time() const;

   bool is_indirect_access_memory_unit(unsigned int fu) const;

   double get_worst_execution_time(const unsigned int fu_name) const;

   double get_area(const unsigned int fu_name) const;

   double GetStatementArea(const unsigned int statement_index) const;

   unsigned long long get_prec(const unsigned int fu_name) const;

   double get_DSPs(const unsigned int fu_name) const;

   ControlStep get_initiation_time(const unsigned int fu_name, const vertex v) const;

   ControlStep get_initiation_time(const unsigned int fu_name, const unsigned int statement_index) const;

   bool is_operation_bounded(const OpGraphConstRef g, const vertex& op, unsigned int fu_type) const;

   bool is_operation_bounded(const unsigned int index, unsigned int fu_type) const;

   bool is_operation_bounded(const unsigned int index) const;

   bool is_operation_PI_registered(const OpGraphConstRef g, const vertex& op, unsigned int fu_type) const;

   bool is_operation_PI_registered(const unsigned int index, unsigned int fu_type) const;

   bool is_operation_PI_registered(const unsigned int index) const;

   bool is_direct_access_memory_unit(unsigned int fu_type) const;

   bool is_dual_port_memory(unsigned int fu_type) const;

   bool is_direct_proxy_memory_unit(unsigned int fu_type) const;

   bool is_read_cond(const unsigned int fu_name) const;

   bool is_assign(const unsigned int fu_name) const;

   bool is_return(const unsigned int fu_name) const;

   bool is_memory_unit(const unsigned int fu_name) const;

   bool is_proxy_unit(const unsigned int fu_name) const;

   bool is_proxy_function_unit(const unsigned int fu_name) const;

   bool is_proxy_wrapped_unit(const unsigned int fu_name) const;

   unsigned int get_memory_var(const unsigned int fu_name) const;

   const std::map<unsigned int, unsigned int>& get_proxy_memory_units() const;

   unsigned int get_proxy_memory_var(const unsigned int fu_name) const;

   const std::map<unsigned int, std::string>& get_proxy_function_units() const;

   const std::map<unsigned int, std::string>& get_proxy_wrapped_units() const;

   double get_stage_period(const unsigned int fu_name, const vertex v, const OpGraphConstRef g) const;
   double get_stage_period(const unsigned int fu_name, const unsigned int v) const;

   double get_correction_time(unsigned int fu, const std::string& operation_name, unsigned int n_ins) const;

   double estimate_mux_time(unsigned int fu_name) const;

   double estimate_muxNto1_delay(unsigned long long fu_prec, unsigned int mux_ins) const;

   double estimate_muxNto1_area(unsigned long long fu_prec, unsigned int mux_ins) const;

   double mux_time_unit(unsigned long long fu_prec) const;
   double mux_time_unit_raw(unsigned long long fu_prec) const;

   unsigned int get_cycles(const unsigned int fu_name, const unsigned int v) const;
   unsigned int get_cycles(const unsigned int fu_name, const vertex v, const OpGraphConstRef g) const;

   bool is_vertex_bounded_with(const unsigned int v, unsigned int& fu_name) const;
   bool is_vertex_bounded_with(const vertex v, unsigned int& fu_name) const;

   bool is_vertex_bounded(const unsigned int fu_name) const;

   technology_nodeRef get_fu(unsigned int fu_name) const;

   unsigned int get_number_channels(unsigned int fu_name) const;

   double EstimateControllerDelay() const;

   double estimate_controller_delay_fb() const;

   std::string get_string_name(unsigned int fu_name) const;

   double compute_normalized_area(unsigned int fu_s1) const;

   std::map<unsigned int, unsigned int> get_memory_units() const;

   bool has_to_be_synthetized(const unsigned int fu_name) const;

   double estimate_call_delay() const;

   bool has_to_be_shared(const unsigned int fu_name) const;

   void check_library();

   bool is_one_cycle_direct_access_memory_unit(unsigned int fu_type) const;

#ifndef NDEBUG

   void print_allocated_resources() const;
#endif

   static std::string extract_bambu_provided_name(unsigned long long prec_in, unsigned long long prec_out,
                                                  const HLS_managerConstRef hls_manager,
                                                  technology_nodeRef& current_fu);

   void print(std::ostream& os) const;

   bool is_artificial_fu(const unsigned int fu_name) const;

   bool can_implement(const unsigned int fu_id, const vertex v) const;

   std::pair<double, double> GetTimeLatency(const unsigned int operation, const unsigned int functional_unit,
                                            const unsigned int stage = 0) const;
   std::pair<double, double> GetTimeLatency(const vertex operation, const unsigned int functional_unit,
                                            const unsigned int stage = 0) const;

   double GetConnectionTime(const unsigned int first_operation, const unsigned int second_operation,
                            const AbsControlStep cs) const;
   double GetConnectionTime(const vertex first_operation, const vertex second_operation, const AbsControlStep cs) const;

   bool IsVariableExecutionTime(const unsigned int operation_index) const;

   double getMinimumSlack() const
   {
      return minimumSlack;
   }

   void setMinimumSlack(const double slack)
   {
      minimumSlack = slack;
   }

   double GetCondExprTimeLatency(const unsigned int operation_index) const;

   unsigned int GetCycleLatency(const unsigned int operationID) const;
   unsigned int GetCycleLatency(const vertex operationID) const;

   unsigned int GetFuType(const unsigned int operation) const;
   unsigned int GetFuType(const vertex operation) const;

   unsigned int get_n_complex_operations() const;

   double get_connection_time(unsigned fu_type, bool add_delay1, bool add_delay2, size_t n_complex_ops,
                              size_t n_mem_ops) const;

   double mux_area_unit_raw(unsigned long long fu_prec) const;

   double estimate_mux_area(unsigned int fu_name) const;

   unsigned int get_worst_number_of_cycles(const unsigned int fu_name) const;

   bool has_constant_in(unsigned int fu_name) const;

   bool is_proxy_memory_unit(const unsigned int fu_name) const;

   bool is_readonly_memory_unit(const unsigned int fu_name) const;

   double GetClockPeriodMargin() const;

   bool is_single_bool_test_cond_expr_units(const unsigned int fu_name) const;

   bool is_simple_pointer_plus_expr(const unsigned int fu_name) const;

   bool can_be_asynchronous_ram(tree_managerConstRef TM, unsigned int var, unsigned int threshold,
                                bool is_read_only_variable, unsigned int channel_number);

   bool CanBeChained(const unsigned int first_statement_index, const unsigned int second_statement_index) const;

   bool CanBeChained(const vertex first_statement, const vertex second_statement) const;

   double getConnectionOffset() const
   {
      return std::max(connection_offset, get_setup_hold_time());
   }
};
using AllocationInformationRef = refcount<AllocationInformation>;
using AllocationInformationConstRef = refcount<const AllocationInformation>;

struct updatecopy_HLS_constraints_functor
{
   unsigned int operator()(const unsigned int name) const;

   void update(const unsigned int name, int delta);

   explicit updatecopy_HLS_constraints_functor(const AllocationInformationRef allocation_information);

   ~updatecopy_HLS_constraints_functor() = default;

 private:
   std::vector<unsigned int> tech;
};

struct node_kind_prec_info
{
   std::string node_kind;
   std::vector<unsigned long long> input_prec;
   std::vector<unsigned long long> base128_input_nelem;

   std::vector<unsigned long long> real_input_nelem;

   unsigned long long output_prec;

   unsigned long long base128_output_nelem;

   unsigned long long real_output_nelem;

   bool is_single_bool_test_cond_expr;

   bool is_simple_pointer_plus_expr;

   node_kind_prec_info()
       : output_prec(0),
         base128_output_nelem(0),
         real_output_nelem(0),
         is_single_bool_test_cond_expr(false),
         is_simple_pointer_plus_expr(false)
   {
   }
   void print(std::ostream& os) const;
};
#endif