PandA-2024.02
sdc_scheduling.cpp
Go to the documentation of this file.
1 /*
2  *
3  * _/_/_/ _/_/ _/ _/ _/_/_/ _/_/
4  * _/ _/ _/ _/ _/_/ _/ _/ _/ _/ _/
5  * _/_/_/ _/_/_/_/ _/ _/_/ _/ _/ _/_/_/_/
6  * _/ _/ _/ _/ _/ _/ _/ _/ _/
7  * _/ _/ _/ _/ _/ _/_/_/ _/ _/
8  *
9  * ***********************************************
10  * PandA Project
11  * URL: http://panda.dei.polimi.it
12  * Politecnico di Milano - DEIB
13  * System Architectures Group
14  * ***********************************************
15  * Copyright (C) 2014-2024 Politecnico di Milano
16  *
17  * This file is part of the PandA framework.
18  *
19  * The PandA framework is free software; you can redistribute it and/or modify
20  * it under the terms of the GNU General Public License as published by
21  * the Free Software Foundation; either version 3 of the License, or
22  * (at your option) any later version.
23  *
24  * This program is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27  * GNU General Public License for more details.
28  *
29  * You should have received a copy of the GNU General Public License
30  * along with this program. If not, see <http://www.gnu.org/licenses/>.
31  *
32  */
40 #include "sdc_scheduling.hpp"
41 
42 #include "ASLAP.hpp"
43 #include "Parameter.hpp"
44 #include "allocation.hpp"
45 #include "allocation_information.hpp"
46 #include "basic_block.hpp"
47 #include "behavioral_helper.hpp"
48 #include "cpu_time.hpp"
49 #include "design_flow_graph.hpp"
50 #include "design_flow_manager.hpp"
51 #include "frontend_flow_step.hpp"
52 #include "frontend_flow_step_factory.hpp"
53 #include "fu_binding.hpp"
54 #include "function_frontend_flow_step.hpp"
55 #include "hls.hpp"
56 #include "hls_constraints.hpp"
57 #include "loop.hpp"
58 #include "loops.hpp"
59 #include "meilp_solver.hpp"
60 #include "memory.hpp"
61 #include "op_graph.hpp"
62 #include "operations_graph_constructor.hpp"
63 #include "schedule.hpp"
64 #include "simple_code_motion.hpp"
65 #include "string_manipulation.hpp"
66 #include "tree_basic_block.hpp"
67 #include "tree_helper.hpp"
68 #include "tree_manager.hpp"
69 #include "utility.hpp"
70 
71 #include <boost/range/adaptor/reversed.hpp>
72 
73 #include <list>
74 
75 CONSTREF_FORWARD_DECL(Schedule);
76 
80 class SDCSorter : std::binary_function<vertex, vertex, bool>
81 {
82  private:
84  const ScheduleConstRef asap;
85 
87  const ScheduleConstRef alap;
88 
90  const FunctionBehaviorConstRef function_behavior;
91 
93  const BBGraphConstRef basic_block_graph;
94 
96  const OpGraphConstRef op_graph;
97 
99  CustomMap<vertex, CustomSet<vertex>> reachability_map;
100 
102  const CustomUnorderedMap<unsigned int, vertex>& bb_index_map;
103 
105  CustomMap<vertex, size_t> op_levels;
106 
108  const ParameterConstRef parameters;
109 
111  const int debug_level;
112 
113  public:
123  SDCSorter(const ScheduleConstRef _asap, const ScheduleConstRef _alap,
124  const FunctionBehaviorConstRef _function_behavior, const OpGraphConstRef _op_graph,
125  std::set<vertex, bb_vertex_order_by_map> loop_bbs, const ParameterConstRef _parameters)
126  : asap(_asap),
127  alap(_alap),
128  function_behavior(_function_behavior),
129  basic_block_graph(_function_behavior->CGetBBGraph(FunctionBehavior::BB)),
130  op_graph(_op_graph),
131  bb_index_map(basic_block_graph->CGetBBGraphInfo()->bb_index_map),
132  parameters(_parameters),
133  debug_level(_parameters->get_class_debug_level(GET_CLASS(*this)))
134  {
135  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->SDC sorter constructor");
136 
137  for(const auto& loop_bb : loop_bbs)
138  {
139  const auto& statements_list = basic_block_graph->CGetBBNodeInfo(loop_bb)->statements_list;
141  for(const auto vertex_to_be_analyzed : boost::adaptors::reverse(statements_list))
142  {
143  OutEdgeIterator eo, eo_end;
144  for(boost::tie(eo, eo_end) = boost::out_edges(vertex_to_be_analyzed, *op_graph); eo != eo_end; eo++)
145  {
146  vertex target = boost::target(*eo, *op_graph);
147  reachability_map[vertex_to_be_analyzed].insert(target);
148  reachability_map[vertex_to_be_analyzed].insert(reachability_map[target].begin(),
149  reachability_map[target].end());
150  }
151  }
152  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Computed reachability");
153 
155  std::map<ControlStep, std::map<ControlStep, CustomSet<vertex>>> alap_asap_cluster;
156 
157  VertexIterator op, op_end;
158  for(boost::tie(op, op_end) = boost::vertices(*op_graph); op != op_end; op++)
159  {
160  alap_asap_cluster[alap->get_cstep(*op).second][asap->get_cstep(*op).second].insert(*op);
161  }
162 
164  for(const auto& alap_cluster : alap_asap_cluster)
165  {
166  for(const auto& asap_cluster : alap_cluster.second)
167  {
168  auto to_process = std::set<vertex, op_vertex_order_by_map>(
169  op_vertex_order_by_map(function_behavior->get_map_levels(), op_graph.get()));
170  for(const auto cluster_op : asap_cluster.second)
171  {
172  to_process.insert(cluster_op);
173  }
174  for(const auto cluster_op : to_process)
175  {
176  op_levels[cluster_op] = static_cast<size_t>(op_levels.size());
177  }
178  }
179  }
180  }
181  }
182 
189  bool operator()(const vertex x, const vertex y) const
190  {
191  const auto first_bb_index = op_graph->CGetOpNodeInfo(x)->bb_index;
192  const auto second_bb_index = op_graph->CGetOpNodeInfo(y)->bb_index;
193  const auto first_bb_vertex = bb_index_map.at(first_bb_index);
194  const auto second_bb_vertex = bb_index_map.at(second_bb_index);
195  if(function_behavior->CheckBBReachability(first_bb_vertex, second_bb_vertex))
196  {
197  return true;
198  }
199  if(function_behavior->CheckBBReachability(second_bb_vertex, first_bb_vertex))
200  {
201  return false;
202  }
203  THROW_ASSERT(op_levels.count(x), "");
204  THROW_ASSERT(op_levels.count(y), "");
205  return op_levels.at(x) < op_levels.at(y);
206  }
207 };
208 
209 SDCScheduling::SDCScheduling(const ParameterConstRef _parameters, const HLS_managerRef _HLSMgr,
210  unsigned int _function_id, const DesignFlowManagerConstRef _design_flow_manager,
211  const HLSFlowStepSpecializationConstRef _hls_flow_step_specialization)
212  : Scheduling(_parameters, _HLSMgr, _function_id, _design_flow_manager, HLSFlowStep_Type::SDC_SCHEDULING,
213  _hls_flow_step_specialization),
214  clock_period(0.0),
215  margin(0.0)
216 {
217  debug_level = parameters->get_class_debug_level(GET_CLASS(*this));
218 }
219 
220 SDCScheduling::~SDCScheduling() = default;
221 
222 void SDCScheduling::AddDelayConstraints(const meilp_solverRef solver, const OpGraphConstRef filtered_op_graph,
223 #ifndef NDEBUG
224  const OpGraphConstRef debug_filtered_op_graph,
225 #endif
226  const std::set<vertex, bb_vertex_order_by_map>& loop_bbs)
227 {
228  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Adding delay constraints");
229  const auto FB = HLSMgr->CGetFunctionBehavior(funId);
230 
232  CustomUnorderedMap<vertex, double> starting_times, ending_times;
233 
235  OpVertexMap<OpVertexSet> reverse_reachability(filtered_op_graph);
236 
238  OpVertexMap<OpVertexSet> live_operations(filtered_op_graph);
239 
241  OpVertexMap<OpVertexSet> constraints(filtered_op_graph);
242 
243  std::list<vertex> basic_blocks;
244  basic_block_graph->TopologicalSort(basic_blocks);
245 
246  for(const auto basic_block : basic_blocks)
247  {
248  if(loop_bbs.count(basic_block))
249  {
250  const auto bb_node_info = basic_block_graph->CGetBBNodeInfo(basic_block);
251  const auto& statements_list = bb_node_info->statements_list;
252  for(const auto current : statements_list)
253  {
254  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
255  "-->Processing " + GET_NAME(filtered_op_graph, current));
258  const double current_op_execution_time = [&]() -> double {
259  if(!allocation_information->is_operation_bounded(filtered_op_graph, current,
260  allocation_information->GetFuType(current)))
261  {
262  return clock_period;
263  }
264  if(GET_TYPE(filtered_op_graph, current) & TYPE_PHI)
265  {
266  return allocation_information->GetCondExprTimeLatency(
267  filtered_op_graph->CGetOpNodeInfo(current)->GetNodeId());
268  }
269  auto timeLatency = allocation_information->GetTimeLatency(
270  current, fu_binding::UNKNOWN, allocation_information->GetCycleLatency(current) - 1);
272  return allocation_information->get_initiation_time(allocation_information->GetFuType(current), current) >
273  0 ?
274  (allocation_information->is_operation_PI_registered(
275  filtered_op_graph, current, allocation_information->GetFuType(current)) ?
276  0.0 :
277  timeLatency.second) :
278  timeLatency.first;
279  }();
280  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
281  "---Its execution time is " + STR(current_op_execution_time));
283  starting_times[current] = 0.0;
284  InEdgeIterator ie, ie_end;
285  reverse_reachability.insert(std::make_pair(current, OpVertexSet(filtered_op_graph)));
286  live_operations.insert(std::make_pair(current, OpVertexSet(filtered_op_graph)));
287  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Computing starting time");
288  for(boost::tie(ie, ie_end) = boost::in_edges(current, *filtered_op_graph); ie != ie_end; ie++)
289  {
290  if(((filtered_op_graph->GetSelector(*ie) & ~CDG_SELECTOR) == 0) &&
291  behavioral_helper->CanBeSpeculated(
292  filtered_op_graph->CGetOpNodeInfo(boost::target(*ie, *filtered_op_graph))->GetNodeId()))
293  {
294  continue;
295  }
296  const auto source = boost::source(*ie, *filtered_op_graph);
297  const auto connection_time = allocation_information->GetConnectionTime(
298  source, current, AbsControlStep(bb_node_info->block->number, AbsControlStep::UNKNOWN));
299  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
300  "---Considering " + GET_NAME(filtered_op_graph, source));
301  if(ending_times.count(source) && ending_times.at(source) + connection_time > starting_times.at(current))
302  {
303  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
304  "---New starting time is " + STR(ending_times.at(source) + connection_time));
305  starting_times[current] = ending_times.at(source) + connection_time;
306  }
307  reverse_reachability.at(current).insert(reverse_reachability.at(source).begin(),
308  reverse_reachability.at(source).end());
309  }
310  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
311  "<--Starting time is " + STR(starting_times.at(current)));
312  ending_times[current] = starting_times.at(current) + current_op_execution_time;
313 
314  OpVertexSet dead_operations(filtered_op_graph);
315 
316  for(boost::tie(ie, ie_end) = boost::in_edges(current, *filtered_op_graph); ie != ie_end; ie++)
317  {
318  if(((filtered_op_graph->GetSelector(*ie) & ~CDG_SELECTOR) == 0) &&
319  behavioral_helper->CanBeSpeculated(
320  filtered_op_graph->CGetOpNodeInfo(boost::target(*ie, *filtered_op_graph))->GetNodeId()))
321  {
322  continue;
323  }
324  const auto source = boost::source(*ie, *filtered_op_graph);
325  if(dead_operations.count(source))
326  {
327  continue;
328  }
329  auto CheckChaining = [&](const vertex other) -> bool {
330  bool constraint_to_be_added = false;
332  if(ending_times.at(current) - starting_times.at(other) > clock_period - margin)
333  {
334  constraint_to_be_added = true;
335  }
336  else if(!HLS->allocation_information->CanBeChained(other, current))
337  {
338  constraint_to_be_added = true;
339  }
340  if(constraint_to_be_added)
341  {
342  bool skip = false;
343  InEdgeIterator ie2, ie2_end;
344  for(boost::tie(ie2, ie2_end) = boost::in_edges(current, *filtered_op_graph);
345  ie2 != ie2_end && !skip; ie2++)
346  {
347  const vertex other_source = boost::source(*ie2, *filtered_op_graph);
348  if(other_source == other)
349  {
350  continue;
351  }
352  if(reverse_reachability.at(other_source).count(other) == 0)
353  {
354  continue;
355  }
356  if(((GET_TYPE(op_graph, other) & TYPE_STORE) != 0) ||
357  (!allocation_information->is_operation_bounded(filtered_op_graph, other,
358  allocation_information->GetFuType(other))))
359  {
360  skip = true;
361  continue;
362  }
363  if(ending_times.at(other_source) - starting_times.at(other) < clock_period)
364  {
365  continue;
366  }
369  skip = true;
370  }
371  if(!skip)
372  {
373  if(constraints.count(other) == 0)
374  {
375  constraints.insert(std::make_pair(other, OpVertexSet(filtered_op_graph)));
376  }
377  constraints.at(other).insert(current);
378  }
379  dead_operations.insert(other);
380  }
381  else
382  {
383  live_operations.at(current).insert(other);
384  }
385  return constraint_to_be_added;
386  };
387  const bool added_constraint = CheckChaining(source);
388  if(!added_constraint)
389  {
390  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
391  "-->Considering operations coming from " + GET_NAME(filtered_op_graph, source));
392  for(const auto& pred_live_operation : live_operations.at(source))
393  {
394  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
395  "-->Considering operation " + GET_NAME(filtered_op_graph, pred_live_operation));
396  CheckChaining(pred_live_operation);
397  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
398  "<--Considered operation " + GET_NAME(filtered_op_graph, pred_live_operation));
399  }
400  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
401  "<--Considered operations coming from " + GET_NAME(filtered_op_graph, source));
402  }
403  }
404  for(const auto& dead_operation : dead_operations)
405  {
406  if(live_operations.at(current).count(dead_operation))
407  {
408  live_operations.at(current).erase(live_operations.at(current).find(dead_operation));
409  }
410  }
411  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
412  "<--Processed " + GET_NAME(filtered_op_graph, current));
413  }
414  }
415  }
416  for(const auto& constraint : constraints)
417  {
418  for(const auto& second : constraint.second)
419  {
420  const auto source_cycle_latency = allocation_information->GetCycleLatency(constraint.first);
421  const auto name = "Path_" + GET_NAME(op_graph, constraint.first) + "-" + GET_NAME(op_graph, second);
422  std::map<int, double> coeffs;
423  coeffs[static_cast<int>(
424  operation_to_varindex.at(std::make_pair(constraint.first, source_cycle_latency - 1)))] = 1.0;
425  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(second, 0)))] = -1.0;
426  solver->add_row(coeffs, -1.0, meilp_solver::L, name);
427 #ifndef NDEBUG
428  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
429  {
430  if(!op_graph->ExistsEdge(constraint.first, second))
431  {
432  temp_edges.insert(FB->ogc->AddEdge(constraint.first, second, DEBUG_SELECTOR));
433  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
434  "---Adding edge " + GET_NAME(filtered_op_graph, constraint.first) + "-->" +
435  GET_NAME(filtered_op_graph, second));
436  try
437  {
438  std::list<vertex> vertices;
439  debug_filtered_op_graph->TopologicalSort(vertices);
440  }
441  catch(const char* msg)
442  {
443  debug_filtered_op_graph->WriteDot("Error.dot");
444  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, constraint.first) + "-->" +
445  GET_NAME(op_graph, second));
446  }
447  catch(const std::string& msg)
448  {
449  debug_filtered_op_graph->WriteDot("Error.dot");
450  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, constraint.first) + "-->" +
451  GET_NAME(op_graph, second));
452  }
453  catch(const std::exception& ex)
454  {
455  debug_filtered_op_graph->WriteDot("Error.dot");
456  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, constraint.first) + "-->" +
457  GET_NAME(op_graph, second));
458  }
459  catch(...)
460  {
461  debug_filtered_op_graph->WriteDot("Error.dot");
462  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, constraint.first) + "-->" +
463  GET_NAME(op_graph, second));
464  }
465  }
466  }
467 #endif
468  }
469  }
470  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Added delay constraints");
471 }
472 
473 void SDCScheduling::AddDependenceConstraint(const meilp_solverRef solver, const vertex source, const vertex target,
474  bool simultaneous) const
475 {
476  const unsigned int source_cycle_latency = allocation_information->GetCycleLatency(source);
477  const std::string name = GET_NAME(op_graph, source) + "-" + GET_NAME(op_graph, target);
478  std::map<int, double> coeffs;
479  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(source, source_cycle_latency - 1)))] = 1.0;
480  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(target, 0)))] = -1.0;
481  solver->add_row(coeffs, simultaneous ? 0.0 : -1.0, meilp_solver::L, name);
482  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Added dependence constraint " + name);
483 }
484 
485 void SDCScheduling::AddStageConstraints(const meilp_solverRef solver, const vertex operation) const
486 {
487  const unsigned int cycle_latency = allocation_information->GetCycleLatency(operation);
488  for(unsigned int stage = 1; stage < cycle_latency; stage++)
489  {
490  const std::string name = "Stage_" + GET_NAME(op_graph, operation) + "_" + STR(stage - 1) + "-" + STR(stage);
491  std::map<int, double> coeffs;
492  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, stage)))] = 1.0;
493  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, stage - 1)))] = -1.0;
494  solver->add_row(coeffs, 1.0, meilp_solver::E, name);
495  }
496 }
497 
498 void SDCScheduling::ComputeRelationships(DesignFlowStepSet& relationship,
499  const DesignFlowStep::RelationshipType relationship_type)
500 {
501  const FunctionBehaviorConstRef FB = HLSMgr->CGetFunctionBehavior(funId);
502  if(GetStatus() == DesignFlowStep_Status::SUCCESS)
503  {
504  if(relationship_type == INVALIDATION_RELATIONSHIP)
505  {
506  {
507  vertex frontend_step = design_flow_manager.lock()->GetDesignFlowStep(
508  FunctionFrontendFlowStep::ComputeSignature(FrontendFlowStepType::SDC_CODE_MOTION, funId));
509  const DesignFlowGraphConstRef design_flow_graph = design_flow_manager.lock()->CGetDesignFlowGraph();
510  const DesignFlowStepRef design_flow_step =
511  frontend_step != NULL_VERTEX ?
512  design_flow_graph->CGetDesignFlowStepInfo(frontend_step)->design_flow_step :
513  GetPointer<const FrontendFlowStepFactory>(
514  design_flow_manager.lock()->CGetDesignFlowStepFactory("Frontend"))
515  ->CreateFunctionFrontendFlowStep(FrontendFlowStepType::SDC_CODE_MOTION, funId);
516  relationship.insert(design_flow_step);
517  }
518  }
519  }
520  Scheduling::ComputeRelationships(relationship, relationship_type);
521 }
522 
523 const CustomUnorderedSet<std::tuple<HLSFlowStep_Type, HLSFlowStepSpecializationConstRef, HLSFlowStep_Relationship>>
524 SDCScheduling::ComputeHLSRelationships(const DesignFlowStep::RelationshipType relationship_type) const
525 {
526  CustomUnorderedSet<std::tuple<HLSFlowStep_Type, HLSFlowStepSpecializationConstRef, HLSFlowStep_Relationship>> ret =
527  Scheduling::ComputeHLSRelationships(relationship_type);
528  switch(relationship_type)
529  {
530  case DEPENDENCE_RELATIONSHIP:
531  {
532  ret.insert(std::make_tuple(HLSFlowStep_Type::DOMINATOR_ALLOCATION, HLSFlowStepSpecializationConstRef(),
533  HLSFlowStep_Relationship::WHOLE_APPLICATION));
534  break;
535  }
536  case INVALIDATION_RELATIONSHIP:
537  {
538  break;
539  }
540  case PRECEDENCE_RELATIONSHIP:
541  {
542 #if HAVE_FROM_PRAGMA_BUILT
543  if(parameters->getOption<bool>(OPT_parse_pragma))
544  {
545  ret.insert(std::make_tuple(HLSFlowStep_Type::OMP_ALLOCATION, HLSFlowStepSpecializationConstRef(),
546  HLSFlowStep_Relationship::CALLED_FUNCTIONS));
547  }
548  else
549 #endif
550  {
551  ret.insert(std::make_tuple(HLSFlowStep_Type::ALLOCATION, HLSFlowStepSpecializationConstRef(),
552  HLSFlowStep_Relationship::SAME_FUNCTION));
553  }
554  break;
555  }
556  default:
557  THROW_UNREACHABLE("");
558  }
559  return ret;
560 }
561 
562 bool SDCScheduling::HasToBeExecuted() const
563 {
564  if(bb_version == 0)
565  {
566  return Scheduling::HasToBeExecuted();
567  }
568  else
569  {
570  return false;
571  }
572 }
573 
574 DesignFlowStep_Status SDCScheduling::InternalExec()
575 {
576  const auto TM = HLSMgr->get_tree_manager();
577  auto fnode = TM->get_tree_node_const(funId);
578  auto fd = GetPointer<function_decl>(fnode);
579  const auto fname = tree_helper::GetMangledFunctionName(fd);
580  const FunctionBehaviorConstRef FB = HLSMgr->CGetFunctionBehavior(funId);
581  const BBGraphConstRef dominators = FB->CGetBBGraph(FunctionBehavior::DOM_TREE);
582  const LoopsConstRef loops = FB->CGetLoops();
583  const std::map<vertex, unsigned int>& bb_map_levels = FB->get_bb_map_levels();
584  auto initial_ctrl_step = ControlStep(0u);
585  auto flow_graph = FB->CGetOpGraph(FunctionBehavior::FLSAODG);
586  CustomUnorderedSet<vertex> RW_stmts;
587  if(HLSMgr->design_interface_io.find(fname) != HLSMgr->design_interface_io.end())
588  {
589  for(const auto& bb2arg2stmtsR : HLSMgr->design_interface_io.at(fname))
590  {
591  for(const auto& arg2stms : bb2arg2stmtsR.second)
592  {
593  if(arg2stms.second.size() > 0)
594  {
595  for(const auto& stmt : arg2stms.second)
596  {
597  const auto op_it = flow_graph->CGetOpGraphInfo()->tree_node_to_operation.find(stmt);
598  if(op_it != flow_graph->CGetOpGraphInfo()->tree_node_to_operation.end())
599  {
600  RW_stmts.insert(op_it->second);
601  }
602  }
603  }
604  }
605  }
606  }
607  for(const auto& loop : loops->GetList())
608  {
609  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Scheduling loop " + STR(loop->GetId()));
610  operation_to_varindex.clear();
611  const unsigned int loop_id = loop->GetId();
612 
614  const bb_vertex_order_by_map comp_i(bb_map_levels);
615  std::set<vertex, bb_vertex_order_by_map> loop_bbs(comp_i);
616  OpVertexSet loop_operations(op_graph);
617  CustomUnorderedSet<vertex> Loop_operations;
618  VertexIterator bb, bb_end;
619  for(boost::tie(bb, bb_end) = boost::vertices(*basic_block_graph); bb != bb_end; bb++)
620  {
621  if(basic_block_graph->CGetBBNodeInfo(*bb)->loop_id == loop_id)
622  {
623  loop_bbs.insert(*bb);
624  auto vit = basic_block_graph->CGetBBNodeInfo(*bb)->statements_list.begin();
625  auto vit_end = basic_block_graph->CGetBBNodeInfo(*bb)->statements_list.end();
626  loop_operations.insert(vit, vit_end);
627  Loop_operations.insert(vit, vit_end);
628  }
629  }
631  const OpGraphConstRef filtered_op_graph = FB->CGetOpGraph(FunctionBehavior::FLSAODG, loop_operations);
632 #ifndef NDEBUG
633  const OpGraphConstRef debug_filtered_op_graph = FB->CGetOpGraph(FunctionBehavior::FLSAODDG, loop_operations);
634 #endif
635  meilp_solverRef solver(meilp_solver::create_solver(
637  static_cast<meilp_solver::supported_solvers>(parameters->getOption<int>(OPT_ilp_solver))));
638  if(parameters->getOption<int>(OPT_ilp_max_time))
639  {
640  solver->setMaximumSeconds(parameters->getOption<int>(OPT_ilp_max_time));
641  }
642 
643  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
644  {
645  filtered_op_graph->WriteDot("Loop_" + STR(loop_id) + "_to_be_scheduled.dot");
646  }
647  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Computing variables");
650  unsigned int next_var_index = 0;
651  for(const auto loop_operation : loop_operations)
652  {
653  const unsigned int cycle_latency = allocation_information->GetCycleLatency(loop_operation);
654  for(unsigned int stage = 0; stage < cycle_latency; stage++)
655  {
656  INDENT_DBG_MEX(
657  DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
658  "---Creating variables for " + GET_NAME(filtered_op_graph, loop_operation) + " (executed by " + " " +
659  allocation_information->get_fu_name(allocation_information->GetFuType(loop_operation)).first +
660  ") stage " + STR(stage) + ": " + STR(next_var_index + 1));
661  operation_to_varindex[std::pair<vertex, unsigned int>(loop_operation, stage)] = next_var_index;
662  next_var_index++;
663  }
664  }
665 
668  CustomMap<vertex, unsigned int> path_end_to_varindex;
669  for(const auto basic_block : loop_bbs)
670  {
671  OutEdgeIterator oe, oe_end;
672  for(boost::tie(oe, oe_end) = boost::out_edges(basic_block, *basic_block_graph); oe != oe_end; oe++)
673  {
674  const auto target = boost::target(*oe, *basic_block_graph);
675  if(boost::in_degree(target, *basic_block_graph) < 2)
676  {
677  continue;
678  }
679  path_end_to_varindex[basic_block] = next_var_index;
680  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
681  "---Creating variable for path ending in BB" +
682  STR(basic_block_graph->CGetBBNodeInfo(basic_block)->block->number));
683  next_var_index++;
684  }
685  }
686 #if 0
687  CustomMap<vertex, unsigned> bb_to_begin, bb_to_end;
689  if(!speculation)
690  {
691  for(const auto basic_block : loop_bbs)
692  {
693  bb_to_begin[basic_block] = next_var_index;
694  next_var_index++;
695  bb_to_end[basic_block] = next_var_index;
696  next_var_index++;
697  }
698  }
699 #endif
700  const size_t num_variables = next_var_index;
702 
703  solver->make(static_cast<int>(num_variables));
704 
706  for(size_t var_index = 0; var_index < num_variables; var_index++)
707  {
708  solver->set_int(static_cast<int>(var_index));
709  solver->set_lowbo(static_cast<int>(var_index), 0);
710  }
711 
712  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Computed " + STR(num_variables) + " variables");
713  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Adding consecutive stages constraints");
714 
716  for(auto const operation : loop_operations)
717  {
718  AddStageConstraints(solver, operation);
719  }
720  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Added consecutive stages constraints");
721  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Adding dependencies constraints");
722 
724  for(const auto operation : loop_operations)
725  {
726  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
727  "-->Adding dependencies starting from " + GET_NAME(filtered_op_graph, operation));
728  OutEdgeIterator oe, oe_end;
729  for(boost::tie(oe, oe_end) = boost::out_edges(operation, *filtered_op_graph); oe != oe_end; oe++)
730  {
732  if(filtered_op_graph->GetSelector(*oe) & ~CDG_SELECTOR)
733  {
734  AddDependenceConstraint(solver, boost::source(*oe, *filtered_op_graph),
735  boost::target(*oe, *filtered_op_graph), true);
736  }
738  else if(!behavioral_helper->CanBeSpeculated(
739  filtered_op_graph->CGetOpNodeInfo(boost::target(*oe, *filtered_op_graph))->GetNodeId()))
740  {
741  AddDependenceConstraint(solver, boost::source(*oe, *filtered_op_graph),
742  boost::target(*oe, *filtered_op_graph), false);
743  }
744  else
745  {
746  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
747  "---Skipped dependence -> " +
748  GET_NAME(filtered_op_graph, boost::target(*oe, *filtered_op_graph)));
749  }
750  }
751  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
752  "<--Added dependencies starting from " + GET_NAME(filtered_op_graph, operation));
753  }
754  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Added dependencies constraints");
755  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Adding delay constraint");
757  AddDelayConstraints(solver, filtered_op_graph,
758 #ifndef NDEBUG
759  debug_filtered_op_graph,
760 #endif
761  loop_bbs);
762  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Added delay constraint");
763  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Adding sorting constraint");
764  const ASLAPRef aslap(new ASLAP(HLSMgr, HLS, true, Loop_operations, parameters, 1000));
765  aslap->compute_ASAP();
766  aslap->compute_ALAP(ASLAP::ALAP_fast);
767  SDCSorter sdc_sorter =
768  SDCSorter(aslap->CGetASAP(), aslap->CGetALAP(), FB, filtered_op_graph, loop_bbs, parameters);
769 
771  CustomMap<vertex, OpVertexSet> loop_unbounded_operations;
772 
774  CustomMap<vertex, OpVertexSet> loop_pipelined_operations;
775 
778  CustomMap<vertex, CustomMap<unsigned int, CustomOrderedSet<std::list<vertex>>>> constrained_operations_sequences;
779  for(const auto basic_block : loop_bbs)
780  {
781  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
782  "-->Adding sorting constraints for BB" +
783  STR(basic_block_graph->CGetBBNodeInfo(basic_block)->block->number));
784  loop_unbounded_operations.insert(std::pair<vertex, OpVertexSet>(basic_block, OpVertexSet(filtered_op_graph)));
785  loop_pipelined_operations.insert(std::pair<vertex, OpVertexSet>(basic_block, OpVertexSet(filtered_op_graph)));
786  InEdgeIterator ie, ie_end;
787  for(boost::tie(ie, ie_end) = boost::in_edges(basic_block, *basic_block_graph); ie != ie_end; ie++)
788  {
789  const auto source = boost::source(*ie, *basic_block_graph);
790  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
791  "-->Considering source BB" + STR(basic_block_graph->CGetBBNodeInfo(source)->block->number));
792  if(loop_bbs.count(source))
793  {
794  loop_unbounded_operations.at(basic_block)
795  .insert(loop_unbounded_operations.at(source).begin(), loop_unbounded_operations.at(source).end());
796  loop_pipelined_operations.at(basic_block)
797  .insert(loop_pipelined_operations.at(source).begin(), loop_pipelined_operations.at(source).end());
798  for(const auto& fu_type : constrained_operations_sequences[source])
799  {
800  constrained_operations_sequences[basic_block][fu_type.first].insert(fu_type.second.begin(),
801  fu_type.second.end());
802  }
803  }
804  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
805  }
806  std::set<vertex, SDCSorter> basic_block_sorted_operations(sdc_sorter);
807  for(const auto operation : basic_block_graph->CGetBBNodeInfo(basic_block)->statements_list)
808  {
809  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
810  "-->Inserting operation " + GET_NAME(filtered_op_graph, operation));
811  basic_block_sorted_operations.insert(operation);
812 #ifndef NDEBUG
813  for(const auto debug_operation : basic_block_sorted_operations)
814  {
815  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
816  "---" + GET_NAME(filtered_op_graph, debug_operation));
817  }
818 #endif
819  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
820  "<--Inserted operation " + GET_NAME(filtered_op_graph, operation));
821  }
822  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
823  {
824  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Ordered statements");
825 #ifndef NDEBUG
826  for(const auto debug_operation : basic_block_sorted_operations)
827  {
828  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
829  "---" + GET_NAME(filtered_op_graph, debug_operation));
830  }
831 #endif
832  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
833  }
834  for(const auto operation : basic_block_sorted_operations)
835  {
836  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
837  "-->Considering " + GET_NAME(filtered_op_graph, operation));
838  if(!allocation_information->is_operation_bounded(op_graph, operation,
839  allocation_information->GetFuType(operation)))
840  {
841  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Adding constraints for unbounded operations");
842  for(const auto other_unbounded_operation : loop_unbounded_operations.at(basic_block))
843  {
844  std::map<int, double> coeffs;
845  const bool other_before = sdc_sorter(other_unbounded_operation, operation);
846  if(other_before)
847  {
848  const std::string name =
849  "UU1_" + GET_NAME(op_graph, other_unbounded_operation) + "_" + GET_NAME(op_graph, operation);
850  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, 0)))] = 1.0;
851  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(other_unbounded_operation, 0)))] =
852  -1.0;
853  solver->add_row(coeffs, 1.0, meilp_solver::G, name);
854 #ifndef NDEBUG
855  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
856  {
857  if(!op_graph->ExistsEdge(other_unbounded_operation, operation))
858  {
859  temp_edges.insert(FB->ogc->AddEdge(other_unbounded_operation, operation, DEBUG_SELECTOR));
860  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
861  "---Adding edge " + GET_NAME(filtered_op_graph, other_unbounded_operation) +
862  "-->" + GET_NAME(filtered_op_graph, operation));
863  try
864  {
865  std::list<vertex> vertices;
866  debug_filtered_op_graph->TopologicalSort(vertices);
867  }
868  catch(const char* msg)
869  {
870  debug_filtered_op_graph->WriteDot("Error.dot");
871  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, other_unbounded_operation) + "-->" +
872  GET_NAME(op_graph, operation));
873  }
874  catch(const std::string& msg)
875  {
876  debug_filtered_op_graph->WriteDot("Error.dot");
877  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, other_unbounded_operation) + "-->" +
878  GET_NAME(op_graph, operation));
879  }
880  catch(const std::exception& ex)
881  {
882  debug_filtered_op_graph->WriteDot("Error.dot");
883  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, other_unbounded_operation) + "-->" +
884  GET_NAME(op_graph, operation));
885  }
886  catch(...)
887  {
888  debug_filtered_op_graph->WriteDot("Error.dot");
889  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, other_unbounded_operation) + "-->" +
890  GET_NAME(op_graph, operation));
891  }
892  }
893  }
894 #endif
895  }
896  else
897  {
899  const std::string name =
900  "UU2_" + GET_NAME(op_graph, operation) + "_" + GET_NAME(op_graph, other_unbounded_operation);
901  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(other_unbounded_operation, 0)))] =
902  1.0;
903  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, 0)))] = -1.0;
904  solver->add_row(coeffs, 0.0, meilp_solver::G, name);
905 #ifndef NDEBUG
906  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
907  {
908  if(!op_graph->ExistsEdge(operation, other_unbounded_operation))
909  {
910  temp_edges.insert(FB->ogc->AddEdge(operation, other_unbounded_operation, DEBUG_SELECTOR));
911  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
912  "---Adding edge " + GET_NAME(filtered_op_graph, operation) + "-->" +
913  GET_NAME(filtered_op_graph, other_unbounded_operation));
914  try
915  {
916  std::list<vertex> vertices;
917  debug_filtered_op_graph->TopologicalSort(vertices);
918  }
919  catch(const char* msg)
920  {
921  debug_filtered_op_graph->WriteDot("Error.dot");
922  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
923  GET_NAME(op_graph, other_unbounded_operation));
924  }
925  catch(const std::string& msg)
926  {
927  debug_filtered_op_graph->WriteDot("Error.dot");
928  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
929  GET_NAME(op_graph, other_unbounded_operation));
930  }
931  catch(const std::exception& ex)
932  {
933  debug_filtered_op_graph->WriteDot("Error.dot");
934  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
935  GET_NAME(op_graph, other_unbounded_operation));
936  }
937  catch(...)
938  {
939  debug_filtered_op_graph->WriteDot("Error.dot");
940  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
941  GET_NAME(op_graph, other_unbounded_operation));
942  }
943  }
944  }
945 #endif
946  }
947  }
948  loop_unbounded_operations.at(basic_block).insert(operation);
949  for(const auto loop_pipelined_operation : loop_pipelined_operations.at(basic_block))
950  {
951  std::map<int, double> coeffs;
952  const bool pipelined_before = sdc_sorter(loop_pipelined_operation, operation);
953  if(pipelined_before)
954  {
955  const std::string name =
956  "PU_" + GET_NAME(op_graph, loop_pipelined_operation) + "_" + GET_NAME(op_graph, operation);
957  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, 0)))] = 1.0;
958  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(
959  loop_pipelined_operation,
960  allocation_information->GetCycleLatency(loop_pipelined_operation) - 1)))] = -1.0;
961  solver->add_row(coeffs, 1.0, meilp_solver::G, name);
962 #ifndef NDEBUG
963  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
964  {
965  if(!op_graph->ExistsEdge(loop_pipelined_operation, operation))
966  {
967  temp_edges.insert(FB->ogc->AddEdge(loop_pipelined_operation, operation, DEBUG_SELECTOR));
968  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
969  "---Adding edge " + GET_NAME(filtered_op_graph, loop_pipelined_operation) +
970  "-->" + GET_NAME(filtered_op_graph, operation));
971  try
972  {
973  std::list<vertex> vertices;
974  debug_filtered_op_graph->TopologicalSort(vertices);
975  }
976  catch(const char* msg)
977  {
978  debug_filtered_op_graph->WriteDot("Error.dot");
979  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, loop_pipelined_operation) + "-->" +
980  GET_NAME(op_graph, operation));
981  }
982  catch(const std::string& msg)
983  {
984  debug_filtered_op_graph->WriteDot("Error.dot");
985  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, loop_pipelined_operation) + "-->" +
986  GET_NAME(op_graph, operation));
987  }
988  catch(const std::exception& ex)
989  {
990  debug_filtered_op_graph->WriteDot("Error.dot");
991  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, loop_pipelined_operation) + "-->" +
992  GET_NAME(op_graph, operation));
993  }
994  catch(...)
995  {
996  debug_filtered_op_graph->WriteDot("Error.dot");
997  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, loop_pipelined_operation) + "-->" +
998  GET_NAME(op_graph, operation));
999  }
1000  }
1001  }
1002 #endif
1003  }
1004  else
1005  {
1007  const std::string name =
1008  "UP_" + GET_NAME(op_graph, operation) + "_" + GET_NAME(op_graph, loop_pipelined_operation);
1009  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(loop_pipelined_operation, 0)))] =
1010  1.0;
1011  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, 0)))] = -1.0;
1012  solver->add_row(coeffs, 0.0, meilp_solver::G, name);
1013 #ifndef NDEBUG
1014  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
1015  {
1016  if(!op_graph->ExistsEdge(operation, loop_pipelined_operation))
1017  {
1018  temp_edges.insert(FB->ogc->AddEdge(operation, loop_pipelined_operation, DEBUG_SELECTOR));
1019  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1020  "---Adding edge " + GET_NAME(filtered_op_graph, operation) + "-->" +
1021  GET_NAME(filtered_op_graph, loop_pipelined_operation));
1022  try
1023  {
1024  std::list<vertex> vertices;
1025  debug_filtered_op_graph->TopologicalSort(vertices);
1026  }
1027  catch(const char* msg)
1028  {
1029  debug_filtered_op_graph->WriteDot("Error.dot");
1030  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
1031  GET_NAME(op_graph, loop_pipelined_operation));
1032  }
1033  catch(const std::string& msg)
1034  {
1035  debug_filtered_op_graph->WriteDot("Error.dot");
1036  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
1037  GET_NAME(op_graph, loop_pipelined_operation));
1038  }
1039  catch(const std::exception& ex)
1040  {
1041  debug_filtered_op_graph->WriteDot("Error.dot");
1042  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
1043  GET_NAME(op_graph, loop_pipelined_operation));
1044  }
1045  catch(...)
1046  {
1047  debug_filtered_op_graph->WriteDot("Error.dot");
1048  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
1049  GET_NAME(op_graph, loop_pipelined_operation));
1050  }
1051  }
1052  }
1053 #endif
1054  }
1055  }
1056  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Added constraints for unbounded operations");
1057  }
1058  if(allocation_information->GetCycleLatency(operation) > 1)
1059  {
1060  loop_pipelined_operations.at(basic_block).insert(operation);
1061  for(const auto loop_unbounded_operation : loop_unbounded_operations.at(basic_block))
1062  {
1063  std::map<int, double> coeffs;
1064  const bool unbounded_before = sdc_sorter(loop_unbounded_operation, operation);
1065  if(unbounded_before)
1066  {
1067  const std::string name =
1068  "UM_" + GET_NAME(op_graph, loop_unbounded_operation) + "_" + GET_NAME(op_graph, operation);
1069  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, 0)))] = 1.0;
1070  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(loop_unbounded_operation, 0)))] =
1071  -1.0;
1072  solver->add_row(coeffs, 1.0, meilp_solver::G, name);
1073 #ifndef NDEBUG
1074  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
1075  {
1076  if(!op_graph->ExistsEdge(loop_unbounded_operation, operation))
1077  {
1078  temp_edges.insert(FB->ogc->AddEdge(loop_unbounded_operation, operation, DEBUG_SELECTOR));
1079  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1080  "---Adding edge " + GET_NAME(filtered_op_graph, loop_unbounded_operation) +
1081  "-->" + GET_NAME(filtered_op_graph, operation));
1082  try
1083  {
1084  std::list<vertex> vertices;
1085  debug_filtered_op_graph->TopologicalSort(vertices);
1086  }
1087  catch(const char* msg)
1088  {
1089  debug_filtered_op_graph->WriteDot("Error.dot");
1090  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, loop_unbounded_operation) + "-->" +
1091  GET_NAME(op_graph, operation));
1092  }
1093  catch(const std::string& msg)
1094  {
1095  debug_filtered_op_graph->WriteDot("Error.dot");
1096  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, loop_unbounded_operation) + "-->" +
1097  GET_NAME(op_graph, operation));
1098  }
1099  catch(const std::exception& ex)
1100  {
1101  debug_filtered_op_graph->WriteDot("Error.dot");
1102  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, loop_unbounded_operation) + "-->" +
1103  GET_NAME(op_graph, operation));
1104  }
1105  catch(...)
1106  {
1107  debug_filtered_op_graph->WriteDot("Error.dot");
1108  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, loop_unbounded_operation) + "-->" +
1109  GET_NAME(op_graph, operation));
1110  }
1111  }
1112  }
1113 #endif
1114  }
1115  else
1116  {
1118  const std::string name =
1119  "MU_" + GET_NAME(op_graph, operation) + "_" + GET_NAME(op_graph, loop_unbounded_operation);
1120  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(loop_unbounded_operation, 0)))] =
1121  1.0;
1122  coeffs[static_cast<int>(operation_to_varindex.at(
1123  std::make_pair(operation, allocation_information->GetCycleLatency(operation) - 1)))] = -1.0;
1124  solver->add_row(coeffs, 0.0, meilp_solver::G, name);
1125 #ifndef NDEBUG
1126  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
1127  {
1128  if(!op_graph->ExistsEdge(operation, loop_unbounded_operation))
1129  {
1130  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1131  "---Adding edge " + GET_NAME(filtered_op_graph, operation) + "-->" +
1132  GET_NAME(filtered_op_graph, loop_unbounded_operation));
1133  temp_edges.insert(FB->ogc->AddEdge(operation, loop_unbounded_operation, DEBUG_SELECTOR));
1134  try
1135  {
1136  std::list<vertex> vertices;
1137  debug_filtered_op_graph->TopologicalSort(vertices);
1138  }
1139  catch(const char* msg)
1140  {
1141  debug_filtered_op_graph->WriteDot("Error.dot");
1142  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
1143  GET_NAME(op_graph, loop_unbounded_operation));
1144  }
1145  catch(const std::string& msg)
1146  {
1147  debug_filtered_op_graph->WriteDot("Error.dot");
1148  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
1149  GET_NAME(op_graph, loop_unbounded_operation));
1150  }
1151  catch(const std::exception& ex)
1152  {
1153  debug_filtered_op_graph->WriteDot("Error.dot");
1154  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
1155  GET_NAME(op_graph, loop_unbounded_operation));
1156  }
1157  catch(...)
1158  {
1159  debug_filtered_op_graph->WriteDot("Error.dot");
1160  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, operation) + "-->" +
1161  GET_NAME(op_graph, loop_unbounded_operation));
1162  }
1163  }
1164  }
1165 #endif
1166  }
1167  }
1168  }
1170  const auto fu_type = allocation_information->GetFuType(operation);
1171  const unsigned int resources_number = allocation_information->get_number_fu(fu_type);
1172  if(limited_resources.count(fu_type))
1173  {
1174  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Mapped on a shared resource");
1175  const auto& old_sequences = constrained_operations_sequences[basic_block][fu_type];
1176  if(old_sequences.size())
1177  {
1178  CustomOrderedSet<std::list<vertex>> new_sequences;
1179  for(auto old_sequence : old_sequences)
1180  {
1181  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
1182  {
1183  std::string old_sequence_string;
1184  for(const auto temp : old_sequence)
1185  {
1186  old_sequence_string += GET_NAME(filtered_op_graph, temp) + "-";
1187  }
1188  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1189  "-->Considering sequence " + old_sequence_string);
1190  }
1191  old_sequence.push_back(operation);
1192  if(old_sequence.size() > resources_number)
1193  {
1194  const auto front = old_sequence.front();
1195  old_sequence.pop_front();
1196  const std::string name = allocation_information->get_fu_name(fu_type).first + "_" +
1197  GET_NAME(op_graph, front) + "_" + GET_NAME(op_graph, operation);
1198  std::map<int, double> coeffs;
1199  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, 0)))] = 1.0;
1200  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(front, 0)))] = -1.0;
1201  solver->add_row(coeffs, 1.0, meilp_solver::G, name);
1202 #ifndef NDEBUG
1203  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
1204  {
1205  if(!op_graph->ExistsEdge(front, operation))
1206  {
1207  temp_edges.insert(FB->ogc->AddEdge(front, operation, DEBUG_SELECTOR));
1208  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1209  "---Adding edge " + GET_NAME(filtered_op_graph, front) + "-->" +
1210  GET_NAME(filtered_op_graph, operation));
1211  try
1212  {
1213  std::list<vertex> vertices;
1214  debug_filtered_op_graph->TopologicalSort(vertices);
1215  }
1216  catch(const char* msg)
1217  {
1218  debug_filtered_op_graph->WriteDot("Error.dot");
1219  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, front) + "-->" +
1220  GET_NAME(op_graph, operation));
1221  }
1222  catch(const std::string& msg)
1223  {
1224  debug_filtered_op_graph->WriteDot("Error.dot");
1225  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, front) + "-->" +
1226  GET_NAME(op_graph, operation));
1227  }
1228  catch(const std::exception& ex)
1229  {
1230  debug_filtered_op_graph->WriteDot("Error.dot");
1231  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, front) + "-->" +
1232  GET_NAME(op_graph, operation));
1233  }
1234  catch(...)
1235  {
1236  debug_filtered_op_graph->WriteDot("Error.dot");
1237  THROW_UNREACHABLE("Edge " + GET_NAME(op_graph, front) + "-->" +
1238  GET_NAME(op_graph, operation));
1239  }
1240  }
1241  }
1242 #endif
1243  }
1244  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
1245  {
1246  std::string old_sequence_string;
1247  for(const auto temp : old_sequence)
1248  {
1249  old_sequence_string += GET_NAME(filtered_op_graph, temp) + "-";
1250  }
1251  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1252  "<--New sequence " + old_sequence_string);
1253  }
1254  new_sequences.insert(old_sequence);
1255  }
1256  constrained_operations_sequences[basic_block][fu_type] = new_sequences;
1257  }
1258  else
1259  {
1260  std::list<vertex> temp;
1261  temp.push_back(operation);
1262  constrained_operations_sequences[basic_block][fu_type].insert(temp);
1263  }
1264  }
1265  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1266  "<--Considered " + GET_NAME(filtered_op_graph, operation));
1267  }
1268  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1269  "<--Added sorting constraints for BB" +
1270  STR(basic_block_graph->CGetBBNodeInfo(basic_block)->block->number));
1271  }
1272 
1274  for(const auto operation : loop_operations)
1275  {
1276  if((GET_TYPE(filtered_op_graph, operation) & (TYPE_RET)) != 0)
1277  {
1278  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1279  "-->Adding constraint for return " + GET_NAME(filtered_op_graph, operation));
1280  for(const auto other_operation : loop_operations)
1281  {
1282  if(operation == other_operation || !FB->CheckReachability(other_operation, operation))
1283  {
1284  continue;
1285  }
1286  const std::string name =
1287  "last_" + GET_NAME(op_graph, other_operation) + "_" + GET_NAME(op_graph, operation);
1288  std::map<int, double> coeffs;
1289  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, 0)))] = 1.0;
1290  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(
1291  other_operation, allocation_information->GetCycleLatency(other_operation) - 1)))] = -1.0;
1293  if(!allocation_information->is_operation_bounded(filtered_op_graph, other_operation,
1294  allocation_information->GetFuType(other_operation)))
1295  {
1296  solver->add_row(coeffs, 1.0, meilp_solver::G, name);
1297  }
1298  else
1299  {
1300  solver->add_row(coeffs, 0.0, meilp_solver::G, name);
1301  }
1302  }
1303  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1304  "<--Added constraint for return " + GET_NAME(filtered_op_graph, operation));
1305  }
1306  }
1307  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Added sorting constraints");
1308  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Forcing path end");
1310  for(auto const path_end : path_end_to_varindex)
1311  {
1312  for(auto const operation : basic_block_graph->CGetBBNodeInfo(path_end.first)->statements_list)
1313  {
1314  const unsigned int source_cycle_latency = allocation_information->GetCycleLatency(operation);
1315  const std::string name = GET_NAME(op_graph, operation) + "_to_BB" +
1316  STR(basic_block_graph->CGetBBNodeInfo(path_end.first)->block->number) + "_end";
1317  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Adding constraint " + name);
1318  std::map<int, double> coeffs;
1319  coeffs[static_cast<int>(path_end.second)] = 1.0;
1320  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, source_cycle_latency - 1)))] =
1321  -1.0;
1322  solver->add_row(coeffs, 0.0, meilp_solver::G, name);
1323  }
1324  }
1325  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Forced path end");
1326 #if 0
1327  if(!speculation)
1328  {
1330  for(const auto basic_block : loop_bbs)
1331  {
1332  for(const auto operation : basic_block_graph->CGetBBNodeInfo(basic_block)->statements_list)
1333  {
1334  const auto name = "BB" + STR(basic_block_graph->CGetBBNodeInfo(basic_block)->block->number) + "_Begin_" + GET_NAME(op_graph, operation);
1335  std::map<int, double> coeffs;
1336  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, 0)))] = 1.0;
1337  coeffs[static_cast<int>(bb_to_begin.at(basic_block))] = -1.0;
1338  solver->add_row(coeffs, 0.0, meilp_solver::G, name);
1339  }
1340  for(const auto operation : basic_block_graph->CGetBBNodeInfo(basic_block)->statements_list)
1341  {
1342  const unsigned int source_cycle_latency = allocation_information->GetCycleLatency(operation);
1343  const auto name = "BB" + STR(basic_block_graph->CGetBBNodeInfo(basic_block)->block->number) + "_End_" + GET_NAME(op_graph, operation);
1344  std::map<int, double> coeffs;
1345  coeffs[static_cast<int>(bb_to_end.at(basic_block))] = 1.0;
1346  coeffs[static_cast<int>(operation_to_varindex.at(std::make_pair(operation, source_cycle_latency-1)))] = -1.0;
1347  solver->add_row(coeffs, 0.0, meilp_solver::G, name);
1348  }
1349  OutEdgeIterator oe, oe_end;
1350  for(boost::tie(oe, oe_end) = boost::out_edges(basic_block, *basic_block_graph); oe != oe_end; oe++)
1351  {
1352  const auto target = boost::target(*oe, *basic_block_graph);
1353  const auto target_bb_node_info = basic_block_graph->CGetBBNodeInfo(target);
1354  if(target_bb_node_info->loop_id == loop_id)
1355  {
1356  const auto name = "CFG_BB" + STR(basic_block_graph->CGetBBNodeInfo(basic_block)->block->number) + "_" + STR(target_bb_node_info->block->number);
1357  std::map<int, double> coeffs;
1358  coeffs[static_cast<int>(bb_to_begin.at(target))] = 1.0;
1359  coeffs[static_cast<int>(bb_to_end.at(basic_block))] = -1.0;
1360  solver->add_row(coeffs, 0.0, meilp_solver::G, name);
1361  }
1362  }
1363  }
1364  }
1365 #endif
1366  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Setting objective function");
1368  std::map<int, double> objective_coeffs;
1369  for(auto const& path_end : path_end_to_varindex)
1370  {
1371  objective_coeffs[static_cast<int>(path_end.second)] += 1.0;
1372  }
1373  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1374  solver->objective_add(objective_coeffs, meilp_solver::min);
1375  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC && loop_operations.size() > 2)
1376  {
1377  solver->print_to_file(parameters->getOption<std::string>(OPT_output_temporary_directory) + "/" +
1378  FB->CGetBehavioralHelper()->get_function_name() + "_SDC_formulation_Loop_" +
1379  STR(loop_id));
1380  }
1381 #ifndef NDEBUG
1382  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
1383  {
1384  filtered_op_graph->WriteDot("HLS_SDC_" + STR(loop_id) + ".dot");
1385  }
1386 #endif
1387  int ilp_result = solver->solve_ilp();
1388  if(ilp_result != 0)
1389  {
1390  THROW_ERROR("Error in finding ilp solution");
1391  }
1392 
1393 #ifndef NDEBUG
1394  for(auto const& temp_edge : temp_edges)
1395  {
1396  FB->ogc->RemoveSelector(temp_edge, DEBUG_SELECTOR);
1397  }
1398  temp_edges.clear();
1399 #endif
1400 
1401  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Solution:");
1402  std::map<int, double> vals;
1403  solver->get_vars_solution(vals);
1404  auto last_relative_step = ControlStep(0u);
1405  for(const auto operation : loop_operations)
1406  {
1407  const unsigned int begin_variable = operation_to_varindex[std::pair<vertex, unsigned int>(operation, 0)];
1408  ControlStep current_control_step =
1409  ControlStep(static_cast<unsigned int>(vals[static_cast<int>(begin_variable)]));
1410  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1411  "---" + GET_NAME(filtered_op_graph, operation) + " scheduled at relative step " +
1412  STR(current_control_step));
1413  HLS->Rsch->set_execution(operation, current_control_step + initial_ctrl_step);
1414  HLS->Rsch->set_execution_end(operation, current_control_step + initial_ctrl_step +
1415  allocation_information->GetCycleLatency(operation) - 1);
1416  const unsigned int cycle_latency = allocation_information->GetCycleLatency(operation);
1417  if(last_relative_step < current_control_step + cycle_latency)
1418  {
1419  last_relative_step = current_control_step + cycle_latency;
1420  }
1422  if(HLS->HLS_C->has_binding_to_fu(GET_NAME(filtered_op_graph, operation)))
1423  {
1424  res_binding->bind(operation, allocation_information->GetFuType(operation), 0);
1425  }
1426  else
1427  {
1428  res_binding->bind(operation, allocation_information->GetFuType(operation));
1429  }
1430  }
1431  initial_ctrl_step = last_relative_step + 1u;
1432  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1437  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Checking which operations have to be moved");
1438  CustomMap<vertex, CustomSet<vertex>> bb_barrier;
1439  for(const auto loop_bb : loop_bbs)
1440  {
1441  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1442  "-->Checking if operations of BB" +
1443  STR(basic_block_graph->CGetBBNodeInfo(loop_bb)->block->number) + " can be moved");
1445  OpVertexSet blocked_ops = OpVertexSet(filtered_op_graph);
1446 
1447  for(const auto loop_operation : basic_block_graph->CGetBBNodeInfo(loop_bb)->statements_list)
1448  {
1449  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1450  "---Checking if " + GET_NAME(filtered_op_graph, loop_operation) + " has to be moved");
1451  auto curr_vertex_type = GET_TYPE(filtered_op_graph, loop_operation);
1452  if((curr_vertex_type & (TYPE_IF | TYPE_MULTIIF)) != 0)
1453  {
1455  continue;
1456  }
1457  if((curr_vertex_type & TYPE_PHI) != 0)
1458  {
1459  bb_barrier[loop_operation].insert(loop_bb);
1460  continue;
1461  }
1462  if((curr_vertex_type & (TYPE_SWITCH | TYPE_RET | TYPE_VPHI | TYPE_LAST_OP | TYPE_LABEL)) != 0)
1463  {
1464  bb_barrier[loop_operation].insert(loop_bb);
1465  continue;
1466  }
1467  if((curr_vertex_type & (TYPE_STORE)) != 0)
1468  {
1469  bb_barrier[loop_operation].insert(loop_bb);
1470  continue;
1471  }
1472  if(RW_stmts.find(loop_operation) != RW_stmts.end())
1473  {
1474  bb_barrier[loop_operation].insert(loop_bb);
1475  continue;
1476  }
1477  if((curr_vertex_type & TYPE_EXTERNAL) && (curr_vertex_type & TYPE_RW))
1478  {
1479  bb_barrier[loop_operation].insert(loop_bb);
1480  continue;
1481  }
1484  if(((curr_vertex_type & TYPE_LOAD) != 0) &&
1485  limited_resources.count(allocation_information->GetFuType(loop_operation)))
1486  {
1487  bb_barrier[loop_operation].insert(loop_bb);
1488  continue;
1489  }
1490  if(!allocation_information->is_operation_bounded(op_graph, loop_operation,
1491  allocation_information->GetFuType(loop_operation)))
1492  {
1493  bb_barrier[loop_operation].insert(loop_bb);
1494  continue;
1495  }
1496  if(loop_operation == filtered_op_graph->CGetOpGraphInfo()->entry_vertex)
1497  {
1498  bb_barrier[loop_operation].insert(loop_bb);
1499  continue;
1500  }
1501  if(loop_operation == filtered_op_graph->CGetOpGraphInfo()->exit_vertex)
1502  {
1503  bb_barrier[loop_operation].insert(loop_bb);
1504  continue;
1505  }
1506  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Type is ok");
1507 
1509  InEdgeIterator ie, ie_end;
1510  for(boost::tie(ie, ie_end) = boost::in_edges(loop_operation, *filtered_op_graph); ie != ie_end; ie++)
1511  {
1512  const auto source = boost::source(*ie, *filtered_op_graph);
1513  if(bb_barrier.count(source))
1514  {
1515  for(const auto pred_bb_barrier : bb_barrier.at(source))
1516  {
1517  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1518  "---Inserting BB" +
1519  STR(basic_block_graph->CGetBBNodeInfo(pred_bb_barrier)->block->number) +
1520  " because of " + GET_NAME(filtered_op_graph, source));
1521  bb_barrier[loop_operation].insert(pred_bb_barrier);
1522  }
1523  }
1524  }
1525  if(bb_barrier.count(loop_operation) && bb_barrier.at(loop_operation).count(loop_bb))
1526  {
1527  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1528  "<--Cannot be moved because depends from a phi in the same bb");
1529  continue;
1530  }
1531 
1532  const auto operation_step = HLS->Rsch->get_cstep(loop_operation).second +
1533  (allocation_information->GetCycleLatency(loop_operation) - 1u);
1534  const auto operation_bb = basic_block_graph->CGetBBGraphInfo()->bb_index_map.at(
1535  filtered_op_graph->CGetOpNodeInfo(loop_operation)->bb_index);
1536  auto current_bb_dominator = operation_bb;
1537  THROW_ASSERT(boost::in_degree(current_bb_dominator, *dominators) == 1,
1538  "Dominator is not a tree or entry was reached");
1539  boost::tie(ie, ie_end) = boost::in_edges(current_bb_dominator, *dominators);
1540  auto candidate_bb = boost::source(*ie, *dominators);
1541  while(true)
1542  {
1543  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1544  "---Checking if it can be bemove in BB" +
1545  STR(basic_block_graph->CGetBBNodeInfo(candidate_bb)->block->number));
1546  if(candidate_bb == basic_block_graph->CGetBBGraphInfo()->entry_vertex ||
1547  loop_bbs.count(candidate_bb) == 0)
1548  {
1549  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "No because it is in other loop");
1550  break;
1551  }
1552  bool overlapping = false;
1553  for(const auto dominator_op : basic_block_graph->CGetBBNodeInfo(candidate_bb)->statements_list)
1554  {
1555  if((HLS->Rsch->get_cstep(dominator_op).second +
1556  (allocation_information->GetCycleLatency(dominator_op) - 1u)) >= operation_step)
1557  {
1558  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1559  "---" + GET_NAME(filtered_op_graph, dominator_op) + " ends at " +
1560  STR(HLS->Rsch->get_cstep(dominator_op).second +
1561  (allocation_information->GetCycleLatency(dominator_op) - 1u)) +
1562  " - " + GET_NAME(filtered_op_graph, loop_operation) + " ends at " +
1563  STR(operation_step));
1564  overlapping = true;
1565  break;
1566  }
1567  }
1568  if(not overlapping)
1569  {
1570  break;
1571  }
1573  current_bb_dominator = candidate_bb;
1574  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1575  "---Updating dominator to BB" +
1576  STR(basic_block_graph->CGetBBNodeInfo(current_bb_dominator)->block->number));
1577  THROW_ASSERT(boost::in_degree(current_bb_dominator, *dominators) == 1,
1578  "Dominator is not a tree or entry was reached");
1579  boost::tie(ie, ie_end) = boost::in_edges(current_bb_dominator, *dominators);
1580  candidate_bb = boost::source(*ie, *dominators);
1582  if(bb_barrier.count(loop_operation) && bb_barrier.at(loop_operation).count(current_bb_dominator))
1583  {
1584  break;
1585  }
1586  }
1587  if(current_bb_dominator != operation_bb)
1588  {
1589  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1590  "---Operation " + GET_NAME(filtered_op_graph, loop_operation) + " has to be moved in BB" +
1591  STR(basic_block_graph->CGetBBNodeInfo(current_bb_dominator)->block->number));
1592  std::vector<unsigned int> movement;
1593  movement.push_back(op_graph->CGetOpNodeInfo(loop_operation)->GetNodeId());
1594  movement.push_back(op_graph->CGetOpNodeInfo(loop_operation)->bb_index);
1595  movement.push_back(basic_block_graph->CGetBBNodeInfo(current_bb_dominator)->block->number);
1596  movements_list.push_back(movement);
1597  }
1598  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1599  }
1600  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1601  }
1602  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Updating execution times");
1603  std::list<vertex> sorted_vertices;
1604  filtered_op_graph->TopologicalSort(sorted_vertices);
1605  for(const auto sorted_vertex : sorted_vertices)
1606  {
1607  HLS->Rsch->UpdateTime(filtered_op_graph->CGetOpNodeInfo(sorted_vertex)->GetNodeId(), false);
1608  }
1609  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Updated execution time");
1610  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Checked which operations have to be moved");
1611  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Scheduled loop " + STR(loop->GetId()));
1612  }
1613  HLS->Rsch->set_csteps(initial_ctrl_step);
1614  return DesignFlowStep_Status::SUCCESS;
1615 }
1616 
1617 void SDCScheduling::Initialize()
1618 {
1619  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Initializing SDCScheduling");
1620  Scheduling::Initialize();
1621  const FunctionBehaviorConstRef FB = HLSMgr->CGetFunctionBehavior(funId);
1622  op_graph = FB->CGetOpGraph(FunctionBehavior::FLSAODG);
1623  behavioral_helper = FB->CGetBehavioralHelper();
1624  feedback_op_graph = FB->CGetOpGraph(FunctionBehavior::FFLSAODG);
1625  allocation_information = HLS->allocation_information;
1626  res_binding = HLS->Rfu;
1627  clock_period = HLS->HLS_C->get_clock_period() * HLS->HLS_C->get_clock_period_resource_fraction();
1628  margin = allocation_information->GetClockPeriodMargin();
1630  // full_reachability_map.clear();
1631  // INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Creating reachability map");
1632  // std::deque<vertex> vertices_to_be_analyzed;
1633  // op_graph->ReverseTopologicalSort(vertices_to_be_analyzed);
1634  // for(const auto vertex_to_be_analyzed : vertices_to_be_analyzed)
1635  // {
1636  // OutEdgeIterator eo, eo_end;
1637  // for(boost::tie(eo, eo_end) = boost::out_edges(vertex_to_be_analyzed, *op_graph); eo != eo_end; eo++)
1638  // {
1639  // vertex target = boost::target(*eo, *op_graph);
1640  // full_reachability_map[vertex_to_be_analyzed].insert(target);
1641  // full_reachability_map[vertex_to_be_analyzed].insert(full_reachability_map[target].begin(),
1642  // full_reachability_map[target].end());
1643  // }
1644  // }
1645  // INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Created reachability map");
1646  // unbounded_operations.clear();
1647  basic_block_graph = FB->CGetBBGraph(FunctionBehavior::BB);
1648  // INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Computing unbounded operations");
1649  VertexIterator basic_block, basic_block_end;
1650  // for(boost::tie(basic_block, basic_block_end) = boost::vertices(*basic_block_graph); basic_block !=
1651  // basic_block_end; basic_block++)
1652  // {
1653  // OpVertexSet filtered_operations(op_graph);
1654  // for(auto const operation : basic_block_graph->CGetBBNodeInfo(*basic_block)->statements_list)
1655  // {
1656  // if(HLS->operations.count(operation) && !allocation_information->is_operation_bounded(op_graph, operation,
1657  // allocation_information->GetFuType(operation)))
1658  // {
1659  // INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---" + GET_NAME(op_graph, operation));
1660  // unbounded_operations.insert(operation);
1661  // }
1662  // }
1663  // }
1664  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Computed unbounded operations");
1665  limited_resources.clear();
1666  const auto resource_types_number = allocation_information->get_number_fu_types();
1667  for(auto resource_type = 0U; resource_type != resource_types_number; resource_type++)
1668  {
1669  const auto resources_number = allocation_information->get_number_fu(resource_type);
1670  if(resources_number < INFINITE_UINT && !allocation_information->is_vertex_bounded(resource_type))
1671  {
1672  limited_resources.insert(resource_type);
1673  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1674  "---There are only " + STR(resources_number) + " of type " +
1675  allocation_information->get_fu_name(resource_type).first);
1676  }
1677  else
1678  {
1679  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1680  "---There are " + STR(resources_number) + " of type " +
1681  allocation_information->get_fu_name(resource_type).first);
1682  }
1683  }
1684  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Computed limited resources");
1685  sharing_operations.clear();
1687  for(boost::tie(basic_block, basic_block_end) = boost::vertices(*basic_block_graph); basic_block != basic_block_end;
1688  basic_block++)
1689  {
1690  OpVertexSet filtered_operations(op_graph);
1691  for(auto const operation : basic_block_graph->CGetBBNodeInfo(*basic_block)->statements_list)
1692  {
1693  if(HLS->operations.count(operation))
1694  {
1695  filtered_operations.insert(operation);
1696  }
1697  }
1698  for(const auto operation : filtered_operations)
1699  {
1700  const auto fu_type = allocation_information->GetFuType(operation);
1701  if(limited_resources.count(fu_type))
1702  {
1703  sharing_operations[fu_type].insert(operation);
1704  }
1705  }
1706  }
1707 
1709  CustomUnorderedSet<unsigned int> not_limited_resources;
1710  for(auto limited_resource : limited_resources)
1711  {
1712  if(sharing_operations[limited_resource].size() <= allocation_information->get_number_fu(limited_resource))
1713  {
1714  not_limited_resources.insert(limited_resource);
1715  }
1716  }
1717 
1719  for(const auto not_limited_resource : not_limited_resources)
1720  {
1721  sharing_operations.erase(not_limited_resource);
1722  limited_resources.erase(not_limited_resource);
1723  }
1724 #ifndef NDEBUG
1725  if(debug_level >= DEBUG_LEVEL_VERY_PEDANTIC)
1726  {
1727  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Shared resources:");
1728  for(const auto& shared_resource : sharing_operations)
1729  {
1730  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1731  "-->" + STR(allocation_information->get_number_fu(shared_resource.first)) + " " +
1732  allocation_information->get_fu_name(shared_resource.first).first);
1733  for(const auto operation : shared_resource.second)
1734  {
1735  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---" + GET_NAME(op_graph, operation));
1736  }
1737  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1738  }
1739  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1740  }
1741 #endif
1742  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Initialized SDCScheduling");
1743 }
TYPE_SWITCH
#define TYPE_SWITCH
constant identifying the node type of a SWITCH operation.
Definition: op_graph.hpp:105
meilp_solver::L
Less then.
Definition: meilp_solver.hpp:82
AllocationInformation::GetCondExprTimeLatency
double GetCondExprTimeLatency(const unsigned int operation_index) const
Return the execution time of a cond expr corresponding to the gimple_phi.
Definition: allocation_information.cpp:2336
BehavioralHelper::CanBeSpeculated
bool CanBeSpeculated(const unsigned int node_index) const
Return true if an operation can be speculated.
Definition: behavioral_helper.cpp:6294
HLSFunctionStep::HasToBeExecuted
bool HasToBeExecuted() const override
Check if this step has actually to be executed.
Definition: hls_function_step.cpp:71
DEBUG_LEVEL_VERY_PEDANTIC
#define DEBUG_LEVEL_VERY_PEDANTIC
extremely verbose debugging print is performed.
Definition: dbgPrintHelper.hpp:86
HLS_step::HLSMgr
const HLS_managerRef HLSMgr
information about all the HLS synthesis
Definition: hls_step.hpp:205
graph::GetSelector
int GetSelector() const
Return the selector of this graph.
Definition: graph.hpp:922
INDENT_DBG_MEX
#define INDENT_DBG_MEX(dbgLevel, curDbgLevel, mex)
We are producing a debug version of the program, so the message is printed;.
Definition: dbgPrintHelper.hpp:140
SDCSorter
Class used to sort operation using ALAP in ascending order as primary key and ASAP ascending order as...
Definition: sdc_scheduling.cpp:80
OutEdgeIterator
boost::graph_traits< graph >::out_edge_iterator OutEdgeIterator
out_edge_iterator definition.
Definition: graph.hpp:1312
AllocationInformation::GetCycleLatency
unsigned int GetCycleLatency(const unsigned int operationID) const
Return the latency of an operation in cycle.
Definition: allocation_information.cpp:1935
SDCScheduling::HasToBeExecuted
bool HasToBeExecuted() const override
Check if this step has actually to be executed.
Definition: sdc_scheduling.cpp:562
GET_TYPE
#define GET_TYPE(data, vertex_index)
Helper macro returning the type associated with a node.
Definition: typed_node_info.hpp:186
SDCScheduling::clock_period
double clock_period
The clock period.
Definition: sdc_scheduling.hpp:86
SDCScheduling::~SDCScheduling
~SDCScheduling() override
Destructor.
FunctionBehavior::BB
Basic block control flow graph.
Definition: function_behavior.hpp:440
SDCScheduling::InternalExec
DesignFlowStep_Status InternalExec() override
Execute the step.
Definition: sdc_scheduling.cpp:574
SDCSorter::bb_index_map
const CustomUnorderedMap< unsigned int, vertex > & bb_index_map
The index basic block map.
Definition: sdc_scheduling.cpp:102
behavioral_helper.hpp
meilp_solver::min
Minimization.
Definition: meilp_solver.hpp:165
TYPE_MULTIIF
#define TYPE_MULTIIF
constant identifying the a multi-way if
Definition: op_graph.hpp:202
TYPE_VPHI
#define TYPE_VPHI
constant string identifying an operation node of type virtual phi-nodes
Definition: op_graph.hpp:162
lenet_tvm.target
string target
Definition: lenet_tvm.py:16
GET_CLASS
#define GET_CLASS(obj)
Macro returning the actual type of an object.
Definition: string_manipulation.hpp:178
BehavioralHelper::get_function_name
std::string get_function_name() const
Return the name of the function.
Definition: behavioral_helper.cpp:1032
FunctionBehavior::ogc
const operations_graph_constructorRef ogc
reference to the operations graph constructor
Definition: function_behavior.hpp:458
TYPE_IF
#define TYPE_IF
constant identifying the node type of an IF operation.
Definition: op_graph.hpp:100
Schedule
Class managing the schedule of the operations.
Definition: schedule.hpp:118
SDCSorter::parameters
const ParameterConstRef parameters
The set of input parameters.
Definition: sdc_scheduling.cpp:108
DesignFlowStep::RelationshipType
RelationshipType
The relationship type.
Definition: design_flow_step.hpp:135
DesignFlowStep::INVALIDATION_RELATIONSHIP
Source must be executed to satisfy target.
Definition: design_flow_step.hpp:138
BBGraph::CGetBBGraphInfo
const BBGraphInfoConstRef CGetBBGraphInfo() const
Returns the property associated with the graph.
Definition: basic_block.hpp:417
Schedule::get_cstep
AbsControlStep get_cstep(const vertex &op) const
Returns the clock cycle where the given operation has been scheduled.
Definition: schedule.cpp:270
HLSFunctionStep::funId
const unsigned int funId
identifier of the function to be processed (0 means that it is a global step)
Definition: hls_function_step.hpp:57
Schedule::set_csteps
void set_csteps(ControlStep cs)
This method sets the number of control steps.
Definition: schedule.hpp:225
GET_NAME
#define GET_NAME(data, vertex_index)
Helper macro returning the name associated with a node.
Definition: typed_node_info.hpp:178
AllocationInformation::get_fu_name
std::pair< std::string, std::string > get_fu_name(unsigned int id) const
Returns the name of the functional unit, associated with the name of the library, given the correspon...
Definition: allocation_information.cpp:268
SDCScheduling::basic_block_graph
BBGraphConstRef basic_block_graph
The basic block cfg graph.
Definition: sdc_scheduling.hpp:71
CustomMap
CustomOrderedMap< T, U > CustomMap
Definition: custom_map.hpp:167
InEdgeIterator
boost::graph_traits< graph >::in_edge_iterator InEdgeIterator
in_edge_iterator definition.
Definition: graph.hpp:1310
Scheduling::Initialize
void Initialize() override
Initialize the step (i.e., like a constructor, but executed just before exec.
Definition: scheduling.cpp:73
DEBUG_SELECTOR
#define DEBUG_SELECTOR
Debug selector.
Definition: op_graph.hpp:521
SDCScheduling::feedback_op_graph
OpGraphConstRef feedback_op_graph
The operation graph with feedback used to perform scheduling.
Definition: sdc_scheduling.hpp:74
hls::allocation_information
AllocationInformationRef allocation_information
Store the technology information.
Definition: hls.hpp:115
SDCScheduling::temp_edges
CustomUnorderedSet< EdgeDescriptor > temp_edges
The set of temporary flow edges added to the op_graph.
Definition: sdc_scheduling.hpp:108
AbsControlStep::UNKNOWN
static const ControlStep UNKNOWN
Constant used to specify unknown control step.
Definition: schedule.hpp:93
hls::operations
OpVertexSet operations
Set representing the subset of operations in the specification to be implemented. ...
Definition: hls.hpp:102
DesignFlowStep_Status::SUCCESS
Step skipped.
graph::ExistsEdge
bool ExistsEdge(const boost::graph_traits< graphs_collection >::vertex_descriptor source, const boost::graph_traits< graphs_collection >::vertex_descriptor target) const
Check if an edge exists.
Definition: graph.hpp:1090
SDCScheduling::operation_to_varindex
CustomUnorderedMap< std::pair< vertex, unsigned int >, unsigned int > operation_to_varindex
Map operation-stage to variable index.
Definition: sdc_scheduling.hpp:92
AllocationInformation::GetClockPeriodMargin
double GetClockPeriodMargin() const
Return the margin to be considered when performing scheduling.
Definition: allocation_information.cpp:3064
function_frontend_flow_step.hpp
This class contains the base representation for a generic frontend flow step which works on a single ...
SDCScheduling::ComputeHLSRelationships
const CustomUnorderedSet< std::tuple< HLSFlowStep_Type, HLSFlowStepSpecializationConstRef, HLSFlowStep_Relationship > > ComputeHLSRelationships(const DesignFlowStep::RelationshipType relationship_type) const override
Compute the relationship of this step.
Definition: sdc_scheduling.cpp:524
tree_basic_block.hpp
Data structure describing a basic block at tree level.
meilp_solver::E
Equal to.
Definition: meilp_solver.hpp:83
AllocationInformation::GetTimeLatency
std::pair< double, double > GetTimeLatency(const unsigned int operation, const unsigned int functional_unit, const unsigned int stage=0) const
Return the execution time of (a stage of) an operation.
Definition: allocation_information.cpp:2011
HLSFunctionStep::ComputeRelationships
void ComputeRelationships(DesignFlowStepSet &design_flow_step_set, const DesignFlowStep::RelationshipType relationship_type) override
Compute the relationships of a step with other steps.
Definition: hls_function_step.cpp:144
AbsControlStep
Absolute Control step First field is the basic block Second field is the relative control step...
Definition: schedule.hpp:89
cpu_time.hpp
Include a set of utilities used to manage CPU time measures.
TYPE_LOAD
#define TYPE_LOAD
Constant string identifying a memory load operation.
Definition: op_graph.hpp:172
OpVertexSet
A set of operation vertices.
Definition: op_graph.hpp:654
FunctionBehavior::get_bb_map_levels
const std::map< vertex, unsigned int > & get_bb_map_levels() const
Return the map of bb vertex index sorted in topological order.
Definition: function_behavior.cpp:543
TYPE_PHI
#define TYPE_PHI
constant string identifying an operation node of type PHI
Definition: op_graph.hpp:135
OpGraph::WriteDot
void WriteDot(const std::string &file_name, const int detail_level=0) const
Writes this graph in dot format.
Definition: op_graph.cpp:335
SDCSorter::op_levels
CustomMap< vertex, size_t > op_levels
For each operation its level.
Definition: sdc_scheduling.cpp:105
tree_helper::GetMangledFunctionName
static std::string GetMangledFunctionName(const function_decl *fd)
Return the mangled function name.
Definition: tree_helper.cpp:445
STR
#define STR(s)
Macro which performs a lexical_cast to a string.
Definition: string_manipulation.hpp:52
string_manipulation.hpp
Auxiliary methods for manipulating string.
SDCSorter::asap
const ScheduleConstRef asap
ASAP.
Definition: sdc_scheduling.cpp:84
FunctionBehavior::FLSAODDG
System dependence + anti-dependence + output dependence graph + flow graph + debug graph...
Definition: function_behavior.hpp:426
op_vertex_order_by_map
The key comparison function for vertices set based on levels.
Definition: function_behavior.hpp:900
TYPE_LABEL
#define TYPE_LABEL
A vertex is of type TYPE_LABEL when it is a target of a goto expression.
Definition: op_graph.hpp:151
OpGraph::CGetOpNodeInfo
const OpNodeInfoConstRef CGetOpNodeInfo(const vertex node) const
Returns the info associated with a node.
Definition: op_graph.hpp:843
ASLAP.hpp
Class specifying ALAP and ASAP algorithms.
THROW_UNREACHABLE
#define THROW_UNREACHABLE(str_expr)
helper function used to specify that some points should never be reached
Definition: exceptions.hpp:292
hls::Rfu
fu_bindingRef Rfu
Store the refcounted functional unit binding of the operations.
Definition: hls.hpp:121
hls::Rsch
ScheduleRef Rsch
Store the refcounted scheduling of the operations.
Definition: hls.hpp:118
Schedule::UpdateTime
void UpdateTime(const unsigned int operation_index, bool update_cs=true)
Compute the starting and the ending time of a statement.
Definition: schedule.cpp:337
operation
This class specifies the characteristic of a particular operation working on a given functional unit...
Definition: technology_node.hpp:364
CustomUnorderedMap
absl::flat_hash_map< T, U, Hash, Eq, Alloc > CustomUnorderedMap
Definition: custom_map.hpp:148
CDG_SELECTOR
#define CDG_SELECTOR
Control dependence edge selector.
Definition: cdfg_edge_info.hpp:70
SDCSorter::reachability_map
CustomMap< vertex, CustomSet< vertex > > reachability_map
The reachability map built on the basis of dependencies, consolidated choices and current choice...
Definition: sdc_scheduling.cpp:99
AllocationInformation::is_operation_PI_registered
bool is_operation_PI_registered(const OpGraphConstRef g, const vertex &op, unsigned int fu_type) const
Checks if the given operation has its primary input registered or not.
Definition: allocation_information.cpp:814
schedule.hpp
Data structure used to store the schedule of the operations.
HLSFlowStep_Type
HLSFlowStep_Type
Definition: hls_step.hpp:95
TYPE_EXTERNAL
#define TYPE_EXTERNAL
constant identifying the node type of a EXTERNAL operation (a function call)
Definition: op_graph.hpp:95
SDCSorter::debug_level
const int debug_level
The debug level.
Definition: sdc_scheduling.cpp:111
FunctionBehavior::DOM_TREE
Basic block dominator tree.
Definition: function_behavior.hpp:445
HLSFunctionStep::bb_version
unsigned int bb_version
The version of bb intermediate representation on which this step was applied.
Definition: hls_function_step.hpp:63
design_flow_graph.hpp
Classes to describe design flow graph.
Schedule::set_execution_end
void set_execution_end(const vertex &op, ControlStep c_step_end)
Sets the ending clock cycle for the given operation.
Definition: schedule.cpp:246
fu_binding::bind
void bind(const vertex &v, unsigned int unit, unsigned int index=std::numeric_limits< unsigned int >::max())
Binds an operation vertex to a functional unit.
Definition: fu_binding.cpp:173
SDCScheduling::behavioral_helper
BehavioralHelperConstRef behavioral_helper
The behavioral helper.
Definition: sdc_scheduling.hpp:77
TYPE_STORE
#define TYPE_STORE
Constant string identifying a memory store operation.
Definition: op_graph.hpp:177
vertex
boost::graph_traits< graph >::vertex_descriptor vertex
vertex definition.
Definition: graph.hpp:1303
DesignFlowStep::design_flow_manager
const Wrefcount< const DesignFlowManager > design_flow_manager
The design flow manager.
Definition: design_flow_step.hpp:120
sdc_scheduling.hpp
Class definition of the sdc scheduling.
OpVertexMap
Map from operation vertices to value.
Definition: op_graph.hpp:667
TYPE_RW
#define TYPE_RW
Constant identifying if a TYPE_EXTERNAL write or read memory.
Definition: op_graph.hpp:217
SDCScheduling::res_binding
fu_bindingRef res_binding
The binding.
Definition: sdc_scheduling.hpp:83
frontend_flow_step.hpp
This class contains the base representation for a generic frontend flow step.
FunctionBehavior::CGetBehavioralHelper
const BehavioralHelperConstRef CGetBehavioralHelper() const
Returns the helper associated with the function.
Definition: function_behavior.cpp:375
VertexIterator
boost::graph_traits< graph >::vertex_iterator VertexIterator
vertex_iterator definition.
Definition: graph.hpp:1307
DesignFlowStep::GetStatus
DesignFlowStep_Status GetStatus() const
Return the status of this design step.
Definition: design_flow_step.cpp:80
SDCScheduling::allocation_information
AllocationInformationConstRef allocation_information
The allocation.
Definition: sdc_scheduling.hpp:80
SDCScheduling::Initialize
void Initialize() override
Initialize the step.
Definition: sdc_scheduling.cpp:1617
DesignFlowStep::parameters
const ParameterConstRef parameters
Set of input parameters.
Definition: design_flow_step.hpp:123
DesignFlowStep_Status
DesignFlowStep_Status
The status of a step.
Definition: design_flow_step.hpp:97
HLSFlowStep_Type::DOMINATOR_ALLOCATION
allocation_information.hpp
This package is used by all HLS packages to manage resource constraints and characteristics.
utility.hpp
This file collects some utility functions and macros.
CONSTREF_FORWARD_DECL
CONSTREF_FORWARD_DECL(Schedule)
ASLAP
Class managing ALAP and ASAP algorithms.
Definition: ASLAP.hpp:75
bb_vertex_order_by_map
The key comparison function for vertices set based on levels.
Definition: basic_block.hpp:480
THROW_ERROR
#define THROW_ERROR(str_expr)
helper function used to throw an error in a standard way
Definition: exceptions.hpp:263
design_flow_manager.hpp
Wrapper of design_flow.
bit_lattice::U
fu_binding::UNKNOWN
static const unsigned int UNKNOWN
The value used to identified unknown functional unit.
Definition: fu_binding.hpp:178
SDCSorter::SDCSorter
SDCSorter(const ScheduleConstRef _asap, const ScheduleConstRef _alap, const FunctionBehaviorConstRef _function_behavior, const OpGraphConstRef _op_graph, std::set< vertex, bb_vertex_order_by_map > loop_bbs, const ParameterConstRef _parameters)
Constructor.
Definition: sdc_scheduling.cpp:123
hls_constraints.hpp
Data structure definition for HLS constraints.
SDCSorter::alap
const ScheduleConstRef alap
ALAP.
Definition: sdc_scheduling.cpp:87
SDCScheduling::limited_resources
CustomUnorderedSet< unsigned int > limited_resources
Set of reachable operations (in scheduling graph)
Definition: sdc_scheduling.hpp:104
AllocationInformation::is_operation_bounded
bool is_operation_bounded(const OpGraphConstRef g, const vertex &op, unsigned int fu_type) const
Checks if the given operation has a bounded execution time or not.
Definition: allocation_information.cpp:792
FunctionBehavior::CheckReachability
bool CheckReachability(const vertex first_operation, const vertex second_operation) const
Check if a path from first_operation to second_operation exists in control flow graph (without feedba...
Definition: function_behavior.cpp:718
tree_helper.hpp
This file collects some utility functions.
HLSFlowStep_Relationship::CALLED_FUNCTIONS
graph::TopologicalSort
void TopologicalSort(std::list< boost::graph_traits< graphs_collection >::vertex_descriptor > &sorted_vertices) const
Compute the topological order of the graph.
Definition: graph.hpp:996
SDCSorter::function_behavior
const FunctionBehaviorConstRef function_behavior
The function behavior.
Definition: sdc_scheduling.cpp:90
HLSFlowStep_Relationship::WHOLE_APPLICATION
Wrefcount::lock
refcount< T > lock() const
Definition: refcount.hpp:212
SDCScheduling::sharing_operations
CustomUnorderedMap< unsigned int, CustomSet< vertex > > sharing_operations
The set of unbounded operations.
Definition: sdc_scheduling.hpp:98
SDCScheduling::AddStageConstraints
void AddStageConstraints(const meilp_solverRef solver, const vertex operation) const
Add constraints to force consecutive execution of different pipeline stages.
Definition: sdc_scheduling.cpp:485
simple_code_motion.hpp
Analysis step that performs some simple code motions over the IR.
meilp_solver::create_solver
static meilp_solverRef create_solver(supported_solvers solver_type)
Factory static member function.
Definition: meilp_solver.cpp:113
SDCSorter::operator()
bool operator()(const vertex x, const vertex y) const
Compare position of two vertices.
Definition: sdc_scheduling.cpp:189
meilp_solver::G
Greater then.
Definition: meilp_solver.hpp:81
AllocationInformation::CanBeChained
bool CanBeChained(const unsigned int first_statement_index, const unsigned int second_statement_index) const
Check if two statements can be chained.
Definition: allocation_information.cpp:3830
fu_binding.hpp
Data structure used to store the functional-unit binding of the vertexes.
FunctionBehavior::CGetOpGraph
const OpGraphConstRef CGetOpGraph(FunctionBehavior::graph_type gt) const
This method returns the operation graphs.
Definition: function_behavior.cpp:312
basic_block.hpp
Class specification of the basic_block structure.
HLSFunctionStep::HLS
hlsRef HLS
HLS data structure of the function to be analyzed.
Definition: hls_function_step.hpp:60
loop.hpp
interface of a loop
frontend_flow_step_factory.hpp
This class contains the methods to create a frontend flow step.
SDCScheduling::SDCScheduling
SDCScheduling(const ParameterConstRef parameters, const HLS_managerRef HLSMgr, unsigned int function_id, const DesignFlowManagerConstRef design_flow_manager, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization)
Constructor.
Definition: sdc_scheduling.cpp:209
BBGraph::CGetBBNodeInfo
const BBNodeInfoConstRef CGetBBNodeInfo(const vertex node) const
Return the info associated with a basic block.
Definition: basic_block.hpp:383
op_graph.hpp
Data structures used in operations graph.
refcount
Template borrowed from the ANTLR library by Terence Parr (http://www.jGuru.com - Software rights: htt...
Definition: refcount.hpp:94
refcount::get
T * get() const
Definition: refcount.hpp:169
FunctionBehavior::CGetBBGraph
const BBGraphConstRef CGetBBGraph(FunctionBehavior::bb_graph_type gt=FunctionBehavior::BB) const
This method returns the basic block graphs.
Definition: function_behavior.cpp:495
FunctionBehavior::CGetLoops
const LoopsConstRef CGetLoops() const
Return the loops.
Definition: function_behavior.cpp:553
SDCScheduling::AddDelayConstraints
void AddDelayConstraints(const meilp_solverRef solver, const OpGraphConstRef filtered_op_graph, const OpGraphConstRef debug_filtered_op_graph, const std::set< vertex, bb_vertex_order_by_map > &loop_bbs)
Add constraints to force execution in different steps of operations which cannot be chained...
Definition: sdc_scheduling.cpp:222
AllocationInformation::get_number_fu
unsigned int get_number_fu(unsigned int fu_name) const
Returns the number of functional unit given its id.
Definition: allocation_information.cpp:279
loops.hpp
interface of loops finding algorithm
FunctionBehavior::FLSAODG
System dependence + anti-dependence + output dependence graph + flow graph.
Definition: function_behavior.hpp:424
Parameter.hpp
this class is used to manage the command-line or XML options.
AllocationInformation::GetConnectionTime
double GetConnectionTime(const unsigned int first_operation, const unsigned int second_operation, const AbsControlStep cs) const
Return the connection time for a couple of operations or the phi overhead for a single operation...
Definition: allocation_information.cpp:3340
SDCScheduling::AddDependenceConstraint
void AddDependenceConstraint(const meilp_solverRef solver, const vertex source, const vertex target, const bool simultaneous) const
Add constraints to force consecutive execution of dependent operations.
Definition: sdc_scheduling.cpp:473
Scheduling
Generic class managing scheduling algorithms.
Definition: scheduling.hpp:64
x
x
Return the smallest n such that 2^n >= _x.
Definition: math_function.hpp:170
hls::HLS_C
const HLS_constraintsRef HLS_C
store the HLS constraints
Definition: hls.hpp:110
DesignFlowStep::debug_level
int debug_level
The debug level.
Definition: design_flow_step.hpp:126
allocation.hpp
This package is used by all HLS packages to manage resource constraints and characteristics.
HLSFlowStepSpecializationConstRef
refcount< const HLSFlowStepSpecialization > HLSFlowStepSpecializationConstRef
const refcount definition of the class
Definition: hls_step.hpp:93
operations_graph_constructor.hpp
This class provides methods to build an operations graph.
SDCSorter::basic_block_graph
const BBGraphConstRef basic_block_graph
The basic block graph.
Definition: sdc_scheduling.cpp:93
TYPE_RET
#define TYPE_RET
constant string identifying an operation node of type return expr
Definition: op_graph.hpp:140
Scheduling::ComputeHLSRelationships
virtual const CustomUnorderedSet< std::tuple< HLSFlowStep_Type, HLSFlowStepSpecializationConstRef, HLSFlowStep_Relationship > > ComputeHLSRelationships(const DesignFlowStep::RelationshipType relationship_type) const override
Compute the relationship of this step.
Definition: scheduling.cpp:96
HLSFlowStep_Type::ALLOCATION
AllocationInformation::get_initiation_time
ControlStep get_initiation_time(const unsigned int fu_name, const vertex v) const
Returns the initiation time for a given vertex and a given functional unit.
Definition: allocation_information.cpp:766
hls.hpp
Data structure definition for high-level synthesis flow.
FunctionBehavior::FFLSAODG
System dependence + anti-dependence + output dependence graph + flow graph with feedback.
Definition: function_behavior.hpp:428
Schedule::set_execution
void set_execution(const vertex &op, ControlStep c_step)
Sets the starting clock cycle for the given operation.
Definition: schedule.cpp:232
NULL_VERTEX
#define NULL_VERTEX
null vertex definition
Definition: graph.hpp:1305
SDCScheduling::movements_list
std::list< std::vector< unsigned int > > movements_list
Result of SPECULATIVE_LOOP: the list of movement to be performed (first element is the operation...
Definition: sdc_scheduling.hpp:164
SDCScheduling::ComputeRelationships
void ComputeRelationships(DesignFlowStepSet &relationship, const DesignFlowStep::RelationshipType relationship_type) override
Compute the relationships of a step with other steps.
Definition: sdc_scheduling.cpp:498
memory.hpp
Datastructure to represent memory information in high-level synthesis.
SDCScheduling::op_graph
OpGraphConstRef op_graph
The operation graph used to perform scheduling.
Definition: sdc_scheduling.hpp:68
tree_manager.hpp
Class specification of the manager of the tree structures extracted from the raw file.
SDCSorter::op_graph
const OpGraphConstRef op_graph
The operation graph.
Definition: sdc_scheduling.cpp:96
Scheduling::speculation
const bool speculation
flag to check speculation
Definition: scheduling.hpp:84
HLSFlowStep_Relationship::SAME_FUNCTION
AllocationInformation::get_number_fu_types
unsigned int get_number_fu_types() const
Returns the number of functional units types.
Definition: allocation_information.cpp:274
SDCScheduling::margin
double margin
The margin which has to be introduced with respect to clock period.
Definition: sdc_scheduling.hpp:89
FunctionFrontendFlowStep::ComputeSignature
static const std::string ComputeSignature(const FrontendFlowStepType frontend_flow_step_type, const unsigned int function_id)
Compute the signature of a function frontend flow step.
Definition: function_frontend_flow_step.cpp:98
AllocationInformation::GetFuType
unsigned int GetFuType(const unsigned int operation) const
Return the functional unit type used to execute an operation.
Definition: allocation_information.cpp:2354
TYPE_LAST_OP
#define TYPE_LAST_OP
A vertex of type LAST_OP if it is the last operation of the application.
Definition: op_graph.hpp:197
meilp_solver.hpp
This class provide an interface to different solvers.
THROW_ASSERT
#define THROW_ASSERT(cond, str_expr)
helper function used to check an assert and if needed to throw an error in a standard way ...
Definition: exceptions.hpp:289
Generated on Mon Feb 12 2024 13:02:54 for PandA-2024.02 by doxygen 1.8.13