PandA-2024.02
|
#include <BB_based_stg.hpp>
Public Member Functions | |
BB_based_stg (const ParameterConstRef _parameters, const HLS_managerRef HLSMgr, unsigned int funId, const DesignFlowManagerConstRef design_flow_manager) | |
Constructor. More... | |
DesignFlowStep_Status | InternalExec () override |
Execute the step. More... | |
void | Initialize () override |
Initialize the step (i.e., like a constructor, but executed just before exec. More... | |
Public Member Functions inherited from STG_creator | |
STG_creator (const ParameterConstRef Param, const HLS_managerRef HLSMgr, unsigned int funId, const DesignFlowManagerConstRef design_flow_manager, const HLSFlowStep_Type hls_flow_step_type) | |
Constructor. More... | |
~STG_creator () override | |
Destructor. More... | |
Public Member Functions inherited from HLSFunctionStep | |
HLSFunctionStep (const ParameterConstRef Param, const HLS_managerRef HLSMgr, unsigned int funId, const DesignFlowManagerConstRef design_flow_manager, const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization=HLSFlowStepSpecializationConstRef()) | |
Constructor. More... | |
~HLSFunctionStep () override | |
Destructor. More... | |
bool | HasToBeExecuted () const override |
Check if this step has actually to be executed. More... | |
std::string | GetSignature () const final |
Return a unified identifier of this design step. More... | |
std::string | GetName () const final |
Return the name of this design step. More... | |
DesignFlowStep_Status | Exec () final |
Execute the step. More... | |
Public Member Functions inherited from HLS_step | |
HLS_step (const ParameterConstRef _parameters, const HLS_managerRef HLSMgr, const DesignFlowManagerConstRef design_flow_manager, const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization=HLSFlowStepSpecializationConstRef()) | |
Constructor. More... | |
~HLS_step () override | |
Destructor. More... | |
std::string | GetSignature () const override |
Return a unified identifier of this design step. More... | |
std::string | GetName () const override |
Return the name of this design step. More... | |
virtual std::string | GetKindText () const |
Return the name of the type of this frontend flow step. More... | |
DesignFlowStepFactoryConstRef | CGetDesignFlowStepFactory () const final |
Return the factory to create this type of steps. More... | |
void | ComputeRelationships (DesignFlowStepSet &design_flow_step_set, const DesignFlowStep::RelationshipType relationship_type) override |
Compute the relationships of a step with other steps. More... | |
Public Member Functions inherited from DesignFlowStep | |
DesignFlowStep (const DesignFlowManagerConstRef design_flow_manager, const ParameterConstRef parameters) | |
Constructor. More... | |
virtual | ~DesignFlowStep () |
Destructor. More... | |
DesignFlowStep_Status | GetStatus () const |
Return the status of this design step. More... | |
virtual void | WriteDot (std::ostream &out) const |
Write the label for a dot graph. More... | |
bool | IsComposed () const |
Returns if this step is composed. More... | |
int | CGetDebugLevel () const |
Return the debug level of the step. More... | |
virtual void | PrintInitialIR () const |
Dump the initial intermediate representation. More... | |
virtual void | PrintFinalIR () const |
Dump the final intermediate representation. More... | |
Protected Member Functions | |
const CustomUnorderedSet< std::tuple< HLSFlowStep_Type, HLSFlowStepSpecializationConstRef, HLSFlowStep_Relationship > > | ComputeHLSRelationships (const DesignFlowStep::RelationshipType relationship_type) const override |
Return the set of analyses in relationship with this design step. More... | |
Protected Member Functions inherited from HLSFunctionStep | |
void | ComputeRelationships (DesignFlowStepSet &design_flow_step_set, const DesignFlowStep::RelationshipType relationship_type) override |
Compute the relationships of a step with other steps. More... | |
Private Member Functions | |
void | optimize_cycles (vertex bbEndingCycle, CustomUnorderedMap< vertex, vertex > &first_state, CustomUnorderedMap< vertex, vertex > &last_state, std::map< vertex, std::list< vertex >> &global_starting_ops, std::map< vertex, std::list< vertex >> &global_ending_ops, std::map< vertex, std::list< vertex >> &global_executing_ops, std::map< vertex, std::list< vertex >> &global_onfly_ops) |
Given two bb linked by a forwarding edge, this method tries to move overlap the execution of the last state of the bb ending the cycle with the execution of the first state of the bb that begins the cycle. More... | |
bool | can_be_moved (std::list< vertex > &lastStateEndingOp, std::list< vertex > &lastStateConditionalOpList, vertex firstStateNextBb, std::map< vertex, std::list< vertex >> &global_starting_ops, std::map< vertex, std::list< vertex >> &global_executing_ops) |
Returns true if all the operations in the list can be moved to the state specified. More... | |
vertex | check_data_dependency (vertex operation, vertex state, std::map< vertex, std::list< vertex >> &global_starting_ops, std::map< vertex, std::list< vertex >> &global_executing_ops) |
This method takes as parameters an operation and a state of the STG graph, and returns the operation that needs the output of the given operation in the given state, NULL otherwise. More... | |
bool | is_instantaneous_operation (vertex operation) |
returns true if the operation takes no time More... | |
bool | res_const_operation (vertex &operation, std::list< vertex > &lastStateExecutingOpList, vertex lastSt) |
returns true if the number of fu available prevents us from moving that operation in the next state More... | |
void | compute_use_def (const std::list< vertex > &opEndingList, const std::list< vertex > &opRuningList, const std::list< vertex > &ignoreList, CustomOrderedSet< unsigned int > &useSet, CustomOrderedSet< unsigned int > &defSet, const OpGraphConstRef data) |
computes the variables used and defined in the by the given list of operations, and saves them in the two sets. More... | |
void | move_without_duplication (const vertex stateToMove, const vertex secondLastState, const vertex destinationState, const std::map< vertex, std::list< vertex >> &global_starting_ops, const std::map< vertex, std::list< vertex >> &global_executing_ops, const std::map< vertex, std::list< vertex >> &global_ending_ops, const CustomOrderedSet< unsigned int > &defSet, const CustomOrderedSet< unsigned int > &useSet) |
Copies all the operations of the state to move in the following. More... | |
void | move_with_duplication (const vertex stateToMove, const vertex secondLastState, const vertex stateToClone, const std::map< vertex, std::list< vertex >> &global_starting_ops, const std::map< vertex, std::list< vertex >> &global_executing_ops, const std::map< vertex, std::list< vertex >> &global_ending_ops, const CustomOrderedSet< unsigned int > &defSet, const CustomOrderedSet< unsigned int > &useSet) |
Duplicates the first state of the destination bb and copies all the operations of the state to move in the new state. More... | |
void | compute_EPP_edge_increments (const std::map< vertex, std::list< vertex >> &starting_ops) const |
If hardware discrepancy analysis is activated, use this function to compute the edge increments for the Efficient Path Profiling (EPP) on the STG. More... | |
Additional Inherited Members | |
Public Types inherited from DesignFlowStep | |
enum | RelationshipType { DEPENDENCE_RELATIONSHIP, INVALIDATION_RELATIONSHIP, PRECEDENCE_RELATIONSHIP } |
The relationship type. More... | |
Static Public Member Functions inherited from HLSFunctionStep | |
static std::string | ComputeSignature (const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization, const unsigned int function_id) |
Compute the signature of a hls flow step. More... | |
Static Public Member Functions inherited from HLS_step | |
static std::string | EnumToName (const HLSFlowStep_Type hls_flow_step_type) |
Given a HLS flow step type, return the name of the type. More... | |
static const std::string | ComputeSignature (const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization) |
Compute the signature of a hls flow step. More... | |
Protected Attributes inherited from HLSFunctionStep | |
std::map< unsigned int, unsigned int > | last_bb_ver |
last bb version of the called functions More... | |
std::map< unsigned int, unsigned int > | last_bitvalue_ver |
The version of bit value IR representation on which this step was applied. More... | |
const unsigned int | funId |
identifier of the function to be processed (0 means that it is a global step) More... | |
hlsRef | HLS |
HLS data structure of the function to be analyzed. More... | |
unsigned int | bb_version |
The version of bb intermediate representation on which this step was applied. More... | |
unsigned int | bitvalue_version |
The version of bitvalue on which this step was applied. More... | |
unsigned int | memory_version |
The version of memory representation on which this step was applied. More... | |
Protected Attributes inherited from HLS_step | |
const HLS_managerRef | HLSMgr |
information about all the HLS synthesis More... | |
const HLSFlowStep_Type | hls_flow_step_type |
The type of this step. More... | |
const HLSFlowStepSpecializationConstRef | hls_flow_step_specialization |
The information about specialization. More... | |
Protected Attributes inherited from DesignFlowStep | |
bool | composed |
True if this step represents a composition of design flow steps (e.g., a flow); must be set by specialized constructors. More... | |
const Wrefcount< const DesignFlowManager > | design_flow_manager |
The design flow manager. More... | |
const ParameterConstRef | parameters |
Set of input parameters. More... | |
int | debug_level |
The debug level. More... | |
const int | output_level |
The output level. More... | |
Static Protected Attributes inherited from HLS_step | |
static CustomUnorderedMap< std::string, HLSFlowStep_Type > | command_line_name_to_enum |
Map hls step name to enum. More... | |
Definition at line 50 of file BB_based_stg.hpp.
BB_based_stg::BB_based_stg | ( | const ParameterConstRef | _parameters, |
const HLS_managerRef | HLSMgr, | ||
unsigned int | funId, | ||
const DesignFlowManagerConstRef | design_flow_manager | ||
) |
Constructor.
design_flow_manager | is the design flow manager |
Definition at line 113 of file BB_based_stg.cpp.
References DesignFlowStep::debug_level, and GET_CLASS.
|
private |
Returns true if all the operations in the list can be moved to the state specified.
Operations contained in the vertx list lastStateConditionalOpList will be ignored in the analysis. This method works fine only if the list of operation contains all the operations executed in a state preceding the one passed as a parameter.
Definition at line 1549 of file BB_based_stg.cpp.
References check_data_dependency(), and is_instantaneous_operation().
Referenced by optimize_cycles().
|
private |
This method takes as parameters an operation and a state of the STG graph, and returns the operation that needs the output of the given operation in the given state, NULL otherwise.
This method takes as parameters an operation and a state of the STG graph, and returns the operation that needs the output of the given operation in the given state, nullptr otherwise.
If the result of the given operation is read by a phi operation chained with a second operation, a pointer to that second operation is returned. In case the result of the given operation is read by a phi which is not chained to any other operation, and no other operation needs the output of the given operation, a pointer to the phi itself is returned.
NOTICE that a phi is treated as a weaker dependance, because it can be solved via chaining. A phi is returned only if no stronger data dependency is found.
If the result of the given operation is read by a phi operation chained with a second operation, a pointer to that second operation is returned. In case the result of the given operation is read by a phi which is not chained to any other operation, and no other operation needs the output of the given operation, a pointer to the phi itself is returned.
NOTICE that an instantaneous operation is treated as a weaker dependence, because it can be solved via chaining. An instantaneous operation is returned only if no stronger data dependency is found.
Definition at line 1599 of file BB_based_stg.cpp.
References FunctionBehavior::DFG, HLSFunctionStep::funId, HLS_step::HLSMgr, and is_instantaneous_operation().
Referenced by can_be_moved().
|
private |
If hardware discrepancy analysis is activated, use this function to compute the edge increments for the Efficient Path Profiling (EPP) on the STG.
Details on EPP and on the algorithm to compute edge increments are here: Thomas Ball and James R. Larus. 1996. Efficient path profiling. In Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture (MICRO 29). IEEE Computer Society, Washington, DC, USA, 46-57.
starting_ops | maps every state to a list of operations starting in that state. They are necessary to compute a set of states when the HW discrepancy analysis has to check the EPP trace, in addition to states before taking feedback edges. |
Definition at line 931 of file BB_based_stg.cpp.
References add_EPP_edges(), hls::allocation_information, StateTransitionGraphManager::CGetEPPStg(), StateTransitionGraphManager::CGetStg(), compute_edge_increments(), DesignFlowStep::debug_level, DEBUG_LEVEL_PEDANTIC, DEBUG_LEVEL_VERBOSE, FunctionBehavior::DFG, edges, HLSFunctionStep::funId, fu_binding::get_assign(), AllocationInformation::get_fu(), HLSFunctionStep::HLS, HLS_step::HLSMgr, INDENT_DBG_MEX, tree_helper::NormalizeTypename(), DesignFlowStep::parameters, hls::Rfu, hls::STG, STR, lenet_tvm::target, and THROW_ASSERT.
Referenced by InternalExec().
|
private |
computes the variables used and defined in the by the given list of operations, and saves them in the two sets.
operations included in the ignoreList will not be considered in this analysis.
Definition at line 1718 of file BB_based_stg.cpp.
References OpGraph::CGetOpNodeInfo(), DEFINITION, HLS_step::HLSMgr, SCALAR, and USE.
Referenced by optimize_cycles().
|
overrideprotectedvirtual |
Return the set of analyses in relationship with this design step.
relationship_type | is the type of relationship to be considered |
Reimplemented from HLS_step.
Definition at line 121 of file BB_based_stg.cpp.
References DesignFlowStep::DEPENDENCE_RELATIONSHIP, DesignFlowStep::INVALIDATION_RELATIONSHIP, LIST_BASED_SCHEDULING, DesignFlowStep::parameters, DesignFlowStep::PRECEDENCE_RELATIONSHIP, SAME_FUNCTION, and THROW_UNREACHABLE.
|
overridevirtual |
Initialize the step (i.e., like a constructor, but executed just before exec.
Reimplemented from HLSFunctionStep.
Definition at line 156 of file BB_based_stg.cpp.
References HLSFunctionStep::HLS, HLS_step::HLSMgr, HLSFunctionStep::Initialize(), DesignFlowStep::parameters, and hls::STG.
|
overridevirtual |
Execute the step.
first state of a basic-block
last state of a basic-block
get entry and exit basic block
contains the list of operations which are executing, starting, ending and "on-fly" in every state of the STG
the analysis has to be performed only on the reachable functions functions to be analyzed
build portion of STG associated with each BBs
for basic block connected only to entry bb
add an empty state before the current basic block
check if virtual phi can be removed and so its basic block
connect two states belonging to different basic blocks concurrently manage entry and exit state and completely merged basic blocks
removed the edge from entry to exit
compute the controlling vertex
Call optimize_cycles for every cycle in the stg
check for unbounded op executed in the last step this ops creates problems with done port registering
Implements HLSFunctionStep.
Definition at line 162 of file BB_based_stg.cpp.
References StateTransitionGraphManager::add_multi_unbounded_obj(), ALL_FINISHED, hls::allocation_information, FunctionBehavior::BB, hls::call_sites_number, FunctionBehavior::CFG, CFG_SELECTOR, StateTransitionGraphManager::CGetStg(), compute_EPP_edge_increments(), StateTransitionGraphManager::ComputeCyclesCount(), DesignFlowStep::debug_level, DEBUG_LEVEL_VERY_PEDANTIC, default_COND, delay(), FunctionBehavior::DFG, edges, AllocationInformation::EstimateControllerDelay(), F_COND, FALSE_COND, FB_CFG_SELECTOR, FunctionBehavior::FBB, HLSFunctionStep::funId, fu_binding::get_assign(), Schedule::get_cstep(), Schedule::get_cstep_end(), StateTransitionGraphManager::get_entry_state(), StateTransitionGraphManager::get_exit_state(), AllocationInformation::get_fu(), AllocationInformation::get_initiation_time(), GET_NAME, StateTransitionGraphManager::get_state_name(), GET_TYPE, functions::GetFUName(), AllocationInformation::getMinimumSlack(), StateTransitionGraphManager::GetStg(), HLSFunctionStep::HLS, HLS_step::HLSMgr, INDENT_DBG_MEX, INDENT_OUT_MEX, max, min, AllocationInformation::mux_time_unit(), tree_helper::NormalizeTypename(), NOT_ALL_FINISHED, optimize_cycles(), DesignFlowStep::output_level, OUTPUT_LEVEL_MINIMUM, OUTPUT_LEVEL_PEDANTIC, OUTPUT_LEVEL_VERBOSE, hls::Param, DesignFlowStep::parameters, print_cpu_time(), PRINT_DBG_MEX, StateTransitionGraphManager::print_statistics(), hls::registered_done_port, hls::registered_inputs, hls::Rfu, hls::Rsch, START_TIME, hls::STG, StateTransitionGraphManager::STG_builder, STOP_TIME, STR, SUCCESS, T_COND, lenet_tvm::target, THROW_ASSERT, TRUE_COND, TYPE_GOTO, TYPE_PHI, and TYPE_VPHI.
returns true if the operation takes no time
Definition at line 1646 of file BB_based_stg.cpp.
References ASSIGN, CONVERT_EXPR, FunctionBehavior::DFG, HLSFunctionStep::funId, GET_TYPE, HLS_step::HLSMgr, NOP_EXPR, TYPE_PHI, and VIEW_CONVERT_EXPR.
Referenced by can_be_moved(), and check_data_dependency().
|
private |
Duplicates the first state of the destination bb and copies all the operations of the state to move in the new state.
An edge is created from the second last state to the new state, and outgoing edges are created from the new state to all the states that follows the first state of the destination bb. The state to move, and all the edges to/from it are not modified by this method.
Definition at line 1860 of file BB_based_stg.cpp.
References DesignFlowStep::debug_level, DEBUG_LEVEL_VERY_PEDANTIC, StateTransitionGraphManager::GetStg(), HLSFunctionStep::HLS, INDENT_DBG_MEX, hls::STG, StateTransitionGraphManager::STG_builder, lenet_tvm::target, and THROW_ASSERT.
Referenced by optimize_cycles().
|
private |
Copies all the operations of the state to move in the following.
An edge is created from the second last state to the destination state. The state to move, and all the edges to/from it are not modified by this method.
Definition at line 1779 of file BB_based_stg.cpp.
References DesignFlowStep::debug_level, DEBUG_LEVEL_VERY_PEDANTIC, StateTransitionGraphManager::GetStg(), HLSFunctionStep::HLS, INDENT_DBG_MEX, hls::STG, and StateTransitionGraphManager::STG_builder.
Referenced by optimize_cycles().
|
private |
Given two bb linked by a forwarding edge, this method tries to move overlap the execution of the last state of the bb ending the cycle with the execution of the first state of the bb that begins the cycle.
Given two bb linked by a forwarding edge, this method tries to overlap the execution of the last state of the bb ending the cycle with the execution of the first state of the bb that begins the cycle.
interface operations cannot be copied or moved
If the exit vertex follows the ending bb, I cannot perform any optimization. The same happen for next BBs having a multi way if, load, store or return operations.
check if first state duplication is required
Definition at line 1047 of file BB_based_stg.cpp.
References hls::allocation_information, can_be_moved(), StateTransitionGraphManager::CGetStg(), compute_use_def(), DesignFlowStep::debug_level, DEBUG_LEVEL_VERY_PEDANTIC, DEFINITION, FunctionBehavior::DFG, FunctionBehavior::FBB, HLSFunctionStep::funId, fu_binding::get_assign(), AllocationInformation::get_fu(), AllocationInformation::get_fu_name(), GET_TYPE, StateTransitionGraphManager::GetStg(), HLSFunctionStep::HLS, HLS_step::HLSMgr, INDENT_DBG_MEX, INTERFACE_LIBRARY, move_with_duplication(), move_without_duplication(), tree_helper::NormalizeTypename(), DesignFlowStep::parameters, res_const_operation(), hls::Rfu, SCALAR, hls::STG, StateTransitionGraphManager::STG_builder, STR, lenet_tvm::target, TYPE_EXTERNAL, TYPE_IF, TYPE_LOAD, TYPE_MULTIIF, TYPE_PHI, TYPE_RET, TYPE_RW, TYPE_STORE, TYPE_SWITCH, TYPE_VPHI, and WORK_LIBRARY.
Referenced by InternalExec().
|
private |
returns true if the number of fu available prevents us from moving that operation in the next state
Definition at line 1668 of file BB_based_stg.cpp.
References hls::allocation_information, StateTransitionGraphManager::CGetStg(), fu_binding::get_assign(), AllocationInformation::get_number_fu(), StateTransitionGraphManager::GetStg(), HLSFunctionStep::HLS, INFINITE_UINT, hls::Rfu, hls::STG, and lenet_tvm::target.
Referenced by optimize_cycles().