function_behavior.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 FUNCTION_BEHAVIOR_HPP
#define FUNCTION_BEHAVIOR_HPP

#include "config_HAVE_ASSERTS.hpp"
#include "config_HAVE_HOST_PROFILING_BUILT.hpp"

#include "custom_map.hpp"
#include "custom_set.hpp"
#include "graph.hpp"
#include "refcount.hpp"

#include <deque>      // for deque
#include <functional> // for binary_function
#include <iosfwd>     // for ostream, size_t
#include <typeindex>  // for hash

CONSTREF_FORWARD_DECL(application_manager);
REF_FORWARD_DECL(FunctionBehavior);
REF_FORWARD_DECL(BasicBlocksGraphConstructor);
REF_FORWARD_DECL(BBGraph);
CONSTREF_FORWARD_DECL(BBGraph);
REF_FORWARD_DECL(BBGraphsCollection);
REF_FORWARD_DECL(BehavioralHelper);
CONSTREF_FORWARD_DECL(BehavioralHelper);
REF_FORWARD_DECL(EpdGraphsCollection);
REF_FORWARD_DECL(EpdGraph);
REF_FORWARD_DECL(extended_pdg_constructor);
REF_FORWARD_DECL(Loops);
REF_FORWARD_DECL(ParallelRegionsGraph);
REF_FORWARD_DECL(ParallelRegionsGraphConstructor);
REF_FORWARD_DECL(level_constructor);
REF_FORWARD_DECL(OpGraph);
CONSTREF_FORWARD_DECL(OpGraph);
REF_FORWARD_DECL(OpGraphsCollection);
REF_FORWARD_DECL(operations_graph_constructor);
class OpVertexSet;
REF_FORWARD_DECL(ParallelRegionsGraphsCollection);
REF_FORWARD_DECL(Parameter);
#if HAVE_HOST_PROFILING_BUILT
CONSTREF_FORWARD_DECL(ProfilingInformation);
REF_FORWARD_DECL(ProfilingInformation);
#endif
REF_FORWARD_DECL(tree_node);
CONSTREF_FORWARD_DECL(Loops);

template <typename Graph>
class dominance;
class ParallelRegionsGraphsCollection;
class sequence_info;
class xml_element;
enum class MemoryAllocation_ChannelsType;
enum class MemoryAllocation_Policy;
using tree_class = unsigned int;

struct memory_access
{
   unsigned int node_id;

   unsigned int base_address;

   unsigned int offset;

   memory_access(unsigned int _node_id, unsigned int _base_address, unsigned int _offset = 0);
};
using memory_accessRef = refcount<memory_access>;

enum class FunctionBehavior_VariableAccessType
{
   UNKNOWN = 0,
   ADDRESS,
   USE,
   DEFINITION,
   OVER,
   ARG
};

enum class FunctionBehavior_VariableType
{
   UNKNOWN = 0,
   MEMORY,
   SCALAR,
   VIRTUAL
};

#if NO_ABSEIL_HASH

namespace std
{
   template <>
   struct hash<FunctionBehavior_VariableAccessType> : public unary_function<FunctionBehavior_VariableAccessType, size_t>
   {
      size_t operator()(FunctionBehavior_VariableAccessType variable_access_type) const
      {
         hash<int> hasher;
         return hasher(static_cast<int>(variable_access_type));
      }
   };
} // namespace std

namespace std
{
   template <>
   struct hash<FunctionBehavior_VariableType> : public unary_function<FunctionBehavior_VariableType, size_t>
   {
      size_t operator()(FunctionBehavior_VariableType variable_access_type) const
      {
         hash<int> hasher;
         return hasher(static_cast<int>(variable_access_type));
      }
   };
} // namespace std

#endif

class FunctionBehavior
{
 private:
   friend class BasicBlocksProfiling;
   friend class BBCdgComputation;
   friend class OpCdgComputation;
   friend class hpp_profiling;
   friend class loops_computation;
   friend class instr_sequences_detection;
   friend struct loop_regions_computation;
   friend class LoopsProfiling;
   friend class probability_path;
   friend class HostProfiling;
   friend class read_profiling_data;
   friend class tp_profiling;
   friend class BBOrderComputation;
   friend class OpOrderComputation;
   friend class BasicBlocksCfgComputation;

   const BehavioralHelperRef helper;

   const BBGraphsCollectionRef bb_graphs_collection;

   const OpGraphsCollectionRef op_graphs_collection;

   const BBGraphRef bb;

   const BBGraphRef extended_bb;

   const BBGraphRef cdg_bb;

   const BBGraphRef dj;

   const BBGraphRef dt;

   const BBGraphRef fbb;

   const BBGraphRef pdt;

   const BBGraphRef ppg;

   const OpGraphRef cfg;

   const OpGraphRef extended_cfg;

   const OpGraphRef fcfg;

   const OpGraphRef adg;

   const OpGraphRef fadg;

   const OpGraphRef cdg;

   const OpGraphRef fcdg;

   const OpGraphRef dfg;

   const OpGraphRef fdfg;

   const OpGraphRef flg;

   const OpGraphRef odg;

   const OpGraphRef fodg;

   const OpGraphRef flaoddg;

   const OpGraphRef fflaoddg;

   const OpGraphRef flsaodg;

#ifndef NDEBUG
   const OpGraphRef flsaoddg;
#endif

   const OpGraphRef fflsaodg;

   const OpGraphRef saodg;

   const OpGraphRef fsaodg;

   const OpGraphRef sdg;

   const OpGraphRef fsdg;

   const OpGraphRef sg;

   const OpGraphRef agg_virtualg;

#if HAVE_HOST_PROFILING_BUILT
   const ProfilingInformationRef profiling_information;
#endif

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

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

   std::deque<vertex> deque_levels;

   std::deque<vertex> bb_deque_levels;

   LoopsRef loops;

   CustomOrderedSet<unsigned int> mem_nodeID;

   CustomOrderedSet<unsigned int> dynamic_address;

   CustomOrderedSet<unsigned int> parm_decl_copied;

   CustomOrderedSet<unsigned int> parm_decl_loaded;

   CustomOrderedSet<unsigned int> parm_decl_stored;

   const ParameterConstRef parameters;

   bool dereference_unknown_address;

   bool unaligned_accesses;

   unsigned int bb_version;

   unsigned int bitvalue_version;

   bool has_globals;

   bool has_undefined_function_receiveing_pointers;

   CustomOrderedSet<unsigned int> state_variables;

   bool pipeline_enabled;

   bool simple_pipeline;

   int initiation_time;

   unsigned int _channels_number;

   MemoryAllocation_ChannelsType _channels_type;

   MemoryAllocation_Policy _allocation_policy;

 public:
   FunctionBehavior(const application_managerConstRef AppM, const BehavioralHelperRef _helper,
                    const ParameterConstRef parameters);
   FunctionBehavior(const FunctionBehavior&) = delete;

   ~FunctionBehavior();

   enum graph_type
   {
      CFG,     
      ECFG,    
      FCFG,    
      CDG,     
      FCDG,    
      DFG,     
      FDFG,    
      ADG,     
      FADG,    
      ODG,     
      FODG,    
      FLG,     
      SDG,     
      FSDG,    
      SAODG,   
      FSAODG,  
      FLSAODG, 
#ifndef NDEBUG
      FLSAODDG, 
#endif
      FFLSAODG,    
      FLAODDG,     
      FFLAODDG,    
      SG,          
      AGG_VIRTUALG 
   };

   enum bb_graph_type
   {
      BB,     
      FBB,    
      EBB,    
      CDG_BB, 
      DOM_TREE,      
      POST_DOM_TREE, 
      PPG,           
      DJ             
   };

   CustomUnorderedMapStable<vertex, CustomUnorderedSet<vertex>> bb_reachability;

   CustomUnorderedMapStable<vertex, CustomUnorderedSet<vertex>> feedback_bb_reachability;

   const operations_graph_constructorRef ogc;

   const BasicBlocksGraphConstructorRef bbgc;

   const level_constructorRef lm;

   const level_constructorRef bb_lm;

   dominance<BBGraph>* dominators;

   dominance<BBGraph>* post_dominators;

   std::map<unsigned int, memory_accessRef> memory_info;

   bool packed_vars;

   BehavioralHelperRef GetBehavioralHelper();

   const BehavioralHelperConstRef CGetBehavioralHelper() const;

   CustomOrderedSet<unsigned int> get_local_variables(const application_managerConstRef AppM) const;

   const std::deque<vertex>& get_levels() const;

   const std::deque<vertex>& get_bb_levels() const;

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

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

   OpGraphRef GetOpGraph(FunctionBehavior::graph_type gt);

   const OpGraphConstRef CGetOpGraph(FunctionBehavior::graph_type gt) const;

   const OpGraphConstRef CGetOpGraph(FunctionBehavior::graph_type gt, const OpVertexSet& statements) const;

   BBGraphRef GetBBGraph(FunctionBehavior::bb_graph_type gt = FunctionBehavior::BB);

   const BBGraphConstRef CGetBBGraph(FunctionBehavior::bb_graph_type gt = FunctionBehavior::BB) const;

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

   void set_epp(EdgeDescriptor e, unsigned long long value);

   friend std::ostream& operator<<(std::ostream& os, const FunctionBehavior& s)
   {
      s.print(os);
      return os;
   }

   friend std::ostream& operator<<(std::ostream& os, const FunctionBehaviorRef& s)
   {
      if(s)
      {
         s->print(os);
      }
      return os;
   }

   const LoopsConstRef CGetLoops() const;

   const LoopsRef GetLoops() const;

#if HAVE_HOST_PROFILING_BUILT

   const ProfilingInformationConstRef CGetProfilingInformation() const;
#endif

   void add_parm_decl_copied(unsigned int node_id);

   void add_parm_decl_loaded(unsigned int node_id);

   void add_parm_decl_stored(unsigned int node_id);

   void add_function_mem(unsigned int node_id);

   void add_dynamic_address(unsigned int node_id);

   void clean_dynamic_address();

   bool is_variable_mem(unsigned int node_id) const;

   const CustomOrderedSet<unsigned int>& get_function_mem() const;

   void clean_function_mem();

   const CustomOrderedSet<unsigned int>& get_dynamic_address() const;

   const CustomOrderedSet<unsigned int>& get_parm_decl_copied() const;

   void clean_parm_decl_copied();

   const CustomOrderedSet<unsigned int>& get_parm_decl_loaded() const;

   void clean_parm_decl_loaded();

   const CustomOrderedSet<unsigned int>& get_parm_decl_stored() const;

   void clean_parm_decl_stored();

   inline void set_dereference_unknown_addr(bool f)
   {
      dereference_unknown_address = f;
   }

   inline bool get_dereference_unknown_addr() const
   {
      return dereference_unknown_address;
   }

   inline void set_unaligned_accesses(bool f)
   {
      unaligned_accesses = f;
   }

   inline bool get_unaligned_accesses() const
   {
      return unaligned_accesses;
   }

   inline void set_has_globals(bool f)
   {
      has_globals = f;
   }

   inline bool get_has_globals() const
   {
      return has_globals;
   }

   inline void set_has_undefined_function_receiveing_pointers(bool f)
   {
      has_undefined_function_receiveing_pointers = f;
   }

   inline bool get_has_undefined_function_receiving_pointers() const
   {
      return has_undefined_function_receiveing_pointers;
   }

   void add_state_variable(unsigned int node_id)
   {
      state_variables.insert(node_id);
   }

   bool is_a_state_variable(unsigned int node_id) const
   {
      return state_variables.count(node_id);
   }

   void clean_state_variable()
   {
      state_variables.clear();
   }

   const CustomOrderedSet<unsigned int>& get_state_variables()
   {
      return state_variables;
   }

   void set_packed_vars(bool packed)
   {
      packed_vars = packed_vars || packed;
   }

   bool has_packed_vars() const
   {
      return packed_vars;
   }

   bool is_pipeline_enabled() const
   {
      return pipeline_enabled;
   }

   bool is_simple_pipeline() const
   {
      if(simple_pipeline)
      {
         THROW_ASSERT(pipeline_enabled, "Simple pipeline is true but pipeline is not enabled");
      }
      return simple_pipeline;
   }

   int get_initiation_time() const
   {
      THROW_ASSERT(pipeline_enabled && !simple_pipeline,
                   "Should not request initiation time when pipeline is not enabled or simple pipeline is requested");
      return initiation_time;
   }

   bool CheckReachability(const vertex first_operation, const vertex second_operation) const;

   bool CheckBBReachability(const vertex first_basic_block, const vertex second_basic_block) const;

   bool CheckFeedbackReachability(const vertex first_operation, const vertex second_operation) const;

   bool CheckBBFeedbackReachability(const vertex first_basic_block, const vertex second_basic_block) const;

   unsigned int GetBBVersion() const;

   unsigned int UpdateBBVersion();

   unsigned int GetBitValueVersion() const;

   unsigned int UpdateBitValueVersion();

   unsigned int GetChannelsNumber() const;

   void SetChannelsNumber(unsigned int val);

   MemoryAllocation_ChannelsType GetChannelsType() const;

   void SetChannelsType(MemoryAllocation_ChannelsType val);

   MemoryAllocation_Policy GetMemoryAllocationPolicy() const;

   void SetMemoryAllocationPolicy(MemoryAllocation_Policy val);
};

using FunctionBehaviorRef = refcount<FunctionBehavior>;
using FunctionBehaviorConstRef = refcount<const FunctionBehavior>;

class op_vertex_order_by_map : std::binary_function<vertex, vertex, bool>
{
 private:
   const std::map<vertex, unsigned int>& ref;

#if HAVE_ASSERTS
   const graph* g;
#endif

 public:
   op_vertex_order_by_map(const std::map<vertex, unsigned int>& ref_, const graph*
#if HAVE_ASSERTS
                                                                          g_)
       : ref(ref_), g(g_)
#else
                          )
       : ref(ref_)
#endif
   {
   }

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

#endif