PandA-2024.02
phi_opt.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) 2004-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  */
43 #include "phi_opt.hpp"
44 
45 #include "Parameter.hpp"
46 #include "application_manager.hpp"
47 #include "behavioral_helper.hpp"
48 #include "dbgPrintHelper.hpp"
49 #include "ext_tree_node.hpp"
50 #include "function_behavior.hpp"
51 #include "string_manipulation.hpp"
52 #include "token_interface.hpp"
53 #include "tree_basic_block.hpp"
54 #include "tree_helper.hpp"
55 #include "tree_manager.hpp"
56 #include "tree_manipulation.hpp"
57 #include "tree_node.hpp"
58 #include "tree_reindex.hpp"
59 
60 #if HAVE_ILP_BUILT
61 #include "allocation_information.hpp"
62 #include "hls.hpp"
63 #include "hls_constraints.hpp"
64 #include "hls_manager.hpp"
65 #include "hls_step.hpp"
66 #include "schedule.hpp"
67 #endif
68 
69 #include <boost/range/adaptor/reversed.hpp>
70 
71 #include <fstream>
72 
73 PhiOpt::PhiOpt(const application_managerRef _AppM, unsigned int _function_id,
74  const DesignFlowManagerConstRef _design_flow_manager, const ParameterConstRef _parameters)
75  : FunctionFrontendFlowStep(_AppM, _function_id, PHI_OPT, _design_flow_manager, _parameters), bb_modified(false)
76 {
77  debug_level = _parameters->get_class_debug_level(GET_CLASS(*this), DEBUG_LEVEL_NONE);
78 }
79 
80 PhiOpt::~PhiOpt() = default;
81 
82 const CustomUnorderedSet<std::pair<FrontendFlowStepType, FunctionFrontendFlowStep::FunctionRelationship>>
83 PhiOpt::ComputeFrontendRelationships(const DesignFlowStep::RelationshipType relationship_type) const
84 {
85  CustomUnorderedSet<std::pair<FrontendFlowStepType, FunctionRelationship>> relationships;
86  switch(relationship_type)
87  {
88  case(DEPENDENCE_RELATIONSHIP):
89  {
90  relationships.insert(std::make_pair(BLOCK_FIX, SAME_FUNCTION));
91  relationships.insert(std::make_pair(MULTI_WAY_IF, SAME_FUNCTION));
92  relationships.insert(std::make_pair(SHORT_CIRCUIT_TAF, SAME_FUNCTION));
93  relationships.insert(std::make_pair(SWITCH_FIX, SAME_FUNCTION));
94  relationships.insert(std::make_pair(USE_COUNTING, SAME_FUNCTION));
95  break;
96  }
97  case(PRECEDENCE_RELATIONSHIP):
98  {
99  break;
100  }
101  case(INVALIDATION_RELATIONSHIP):
102  {
103  break;
104  }
105  default:
106  {
107  THROW_UNREACHABLE("");
108  }
109  }
110  return relationships;
111 }
112 
113 void PhiOpt::Initialize()
114 {
115  bb_modified = false;
116  TM = AppM->get_tree_manager();
117  tree_man = tree_manipulationConstRef(new tree_manipulation(TM, parameters, AppM));
118  const auto fd = GetPointerS<const function_decl>(TM->CGetTreeNode(function_id));
119  sl = GetPointerS<statement_list>(GET_NODE(fd->body));
120 #if HAVE_ILP_BUILT
121  if(parameters->getOption<HLSFlowStep_Type>(OPT_scheduling_algorithm) == HLSFlowStep_Type::SDC_SCHEDULING &&
122  GetPointer<const HLS_manager>(AppM) && GetPointer<const HLS_manager>(AppM)->get_HLS(function_id) and
123  GetPointer<const HLS_manager>(AppM)->get_HLS(function_id)->Rsch)
124  {
125  schedule = GetPointerS<const HLS_manager>(AppM)->get_HLS(function_id)->Rsch;
126  }
127 #endif
128 }
129 
130 DesignFlowStep_Status PhiOpt::InternalExec()
131 {
132  bool restart = true;
133 
135  while(restart)
136  {
137  restart = false;
138 
139  for(const auto& block : sl->list_of_bloc)
140  {
141  std::list<tree_nodeRef> phis_to_be_removed;
142  for(const auto& phi : block.second->CGetPhiList())
143  {
144  const auto gp = GetPointer<const gimple_phi>(GET_CONST_NODE(phi));
145  const auto sn = GetPointer<const ssa_name>(GET_CONST_NODE(gp->res));
146  if(sn->CGetUseStmts().empty())
147  {
148  phis_to_be_removed.push_back(phi);
149  }
150  }
151  for(const auto& phi : phis_to_be_removed)
152  {
153  if(AppM->ApplyNewTransformation())
154  {
155  AppM->RegisterTransformation(GetName(), tree_nodeConstRef());
156  block.second->RemovePhi(phi);
157  bb_modified = true;
158  restart = true;
159  }
160  }
161  }
162  }
163 
164  auto removePhiOnly = [&]() {
165  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Merging phis");
167  CustomSet<unsigned int> blocks_to_be_removed;
168  for(const auto& block : sl->list_of_bloc)
169  {
170  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Checking BB" + STR(block.first));
171  if(block.second->list_of_pred.size() >= 2 && block.second->CGetPhiList().size() &&
172  block.second->CGetStmtList().empty())
173  {
174  const auto successor = block.second->list_of_succ.front();
175  THROW_ASSERT(sl->list_of_bloc.count(successor), "");
176  const auto succ_block = sl->list_of_bloc.at(successor);
178  const bool common_predecessor = [&]() {
179  for(auto predecessor : block.second->list_of_pred)
180  {
181  if(std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), predecessor) !=
182  succ_block->list_of_pred.end())
183  {
184  return true;
185  }
186  }
187  return false;
188  }();
189  if(common_predecessor)
190  {
191  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Skipped because of common predecessor");
192  continue;
193  }
194 
195  // True if the variables defined in the first basic block are only used in the phi of the second basic block
196  const bool only_phi_use = [&]() {
198  for(const auto& phi : block.second->CGetPhiList())
199  {
200  const auto gp = GetPointer<const gimple_phi>(GET_CONST_NODE(phi));
201  const auto sn = GetPointer<const ssa_name>(GET_CONST_NODE(gp->res));
202  for(const auto& use : sn->CGetUseStmts())
203  {
204  const auto gn = GetPointer<const gimple_node>(GET_CONST_NODE(use.first));
205  if(gn->get_kind() != gimple_phi_K)
206  {
207  return false;
208  }
209  if(gn->bb_index != successor)
210  {
211  return false;
212  }
213  }
214  }
215  return true;
216  }();
217  if(!only_phi_use)
218  {
219  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
220  "<--Skipped because not used only in the second phi");
221  continue;
222  }
223  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Added to the basic block to be merged");
224  blocks_to_be_removed.insert(block.first);
225  }
226  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
227  }
228  for(auto block_to_be_removed : blocks_to_be_removed)
229  {
230  if(AppM->ApplyNewTransformation())
231  {
232  AppM->RegisterTransformation(GetName(), tree_nodeConstRef());
233  MergePhi(block_to_be_removed);
234  if(debug_level >= DEBUG_LEVEL_PEDANTIC &&
235  (!parameters->IsParameter("print-dot-FF") || parameters->GetParameter<unsigned int>("print-dot-FF")))
236  {
237  WriteBBGraphDot("BB_During_" + GetName() + "_AfterMerge_BB" + STR(block_to_be_removed) + ".dot");
238  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
239  "---Written BB_During_" + GetName() + "_AfterMerge_BB" + STR(block_to_be_removed) +
240  ".dot");
241  }
242  }
243  }
244  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Merged phis");
245  };
246  removePhiOnly();
247 
248  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing single input phis");
250  for(const auto& block : sl->list_of_bloc)
251  {
252  if(block.second->list_of_pred.size() == 1 && block.second->CGetPhiList().size())
253  {
254  if(AppM->ApplyNewTransformation())
255  {
256  AppM->RegisterTransformation(GetName(), tree_nodeConstRef());
257  SinglePhiOptimization(block.first);
258  bb_modified = true;
259  }
260  }
261  }
262  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed single input phis");
263  if(debug_level >= DEBUG_LEVEL_PEDANTIC)
264  {
265  WriteBBGraphDot("BB_Removed_Single_Input_Phis_" + GetName() + "_chain.dot");
266  }
267 
268  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing chains of BBs");
269 
270  while(restart)
271  {
272  restart = false;
274  for(const auto& block : sl->list_of_bloc)
275  {
276  if(block.first == bloc::ENTRY_BLOCK_ID)
277  {
278  continue;
279  }
280  if(block.second->list_of_succ.size() == 1)
281  {
282  const auto succ_block = block.second->list_of_succ.front();
283  THROW_ASSERT(sl->list_of_bloc.count(succ_block),
284  "Successor block BB" + STR(succ_block) + " does not exist");
285  if(sl->list_of_bloc.at(succ_block)->list_of_pred.size() == 1)
286  {
287  if(AppM->ApplyNewTransformation())
288  {
289  AppM->RegisterTransformation(GetName(), tree_nodeConstRef());
290  ChainOptimization(block.first);
291  bb_modified = true;
292  restart = true;
293  break;
294  }
295  }
296  }
297  }
298  }
299  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed chains of BBs");
300 
301  if(debug_level >= DEBUG_LEVEL_PEDANTIC)
302  {
303  WriteBBGraphDot("BB_Removed_Chains_" + GetName() + "_chain.dot");
304  }
305 
306  restart = true;
307  while(restart)
308  {
309  bool removePhiOnlyP = false;
310  restart = false;
312  CustomSet<decltype(sl->list_of_bloc)::key_type> blocks_to_be_analyzed;
313  for(const auto& block : sl->list_of_bloc)
314  {
315  blocks_to_be_analyzed.insert(block.first);
316  }
317 
319  for(auto bloc_to_be_analyzed : blocks_to_be_analyzed)
320  {
321  THROW_ASSERT(sl->list_of_bloc.count(bloc_to_be_analyzed), "");
322  const auto& block = sl->list_of_bloc.at(bloc_to_be_analyzed);
323  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
324  "-->Analyzing BB" + STR(block->number) + " Stmts= " + STR(block->CGetStmtList().size()) +
325  " Phis=" + STR(block->CGetPhiList().size()));
326 
328  if(block->CGetStmtList().size() == 1 &&
329  GET_CONST_NODE(block->CGetStmtList().front())->get_kind() == gimple_nop_K)
330  {
331  block->RemoveStmt(block->CGetStmtList().front(), AppM);
332  bb_modified = true;
333  }
334  if(block->list_of_pred.size() >= 2 && block->CGetPhiList().size() && block->CGetStmtList().empty())
335  {
336  removePhiOnlyP = true;
337  }
338 
339  if(block->CGetStmtList().size() || block->CGetPhiList().size())
340  {
341  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Basic block is not empty");
342  continue;
343  }
344  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Basic block is empty");
345  if(block->number == bloc::ENTRY_BLOCK_ID)
346  {
347  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Basic block is Entry");
348  continue;
349  }
350  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Basic block is not Entry");
351  if(block->number == bloc::EXIT_BLOCK_ID)
352  {
353  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Basic block is Exit");
354  continue;
355  }
356 #if HAVE_PRAGMA_BUILT
357  if(parameters->getOption<int>(OPT_gcc_openmp_simd))
358  {
359  if(block->list_of_pred.size() == 1)
360  {
361  const auto pred_block_id = block->list_of_pred.front();
362  THROW_ASSERT(sl->list_of_bloc.count(pred_block_id), "");
363  const auto pred_block = sl->list_of_bloc.at(pred_block_id);
364  if(pred_block->loop_id != block->loop_id)
365  {
366  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Basic block is Landing pad");
367  continue;
368  }
369  }
370  }
371 #endif
372  if(!AppM->ApplyNewTransformation())
373  {
374  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Reached limit of cfg transformations");
375  continue;
376  }
377  AppM->RegisterTransformation(GetName(), tree_nodeConstRef());
378  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Basic block is not Exit");
379  if(debug_level >= DEBUG_LEVEL_PEDANTIC &&
380  (!parameters->IsParameter("print-dot-FF") || parameters->GetParameter<unsigned int>("print-dot-FF")))
381  {
382  WriteBBGraphDot("BB_Before_" + GetName() + "_Before_BB" + STR(block->number) + ".dot");
383  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
384  "---Written BB_Before_" + GetName() + "_Before_BB" + STR(block->number) + ".dot");
385  }
386  const auto pattern_type = IdentifyPattern(block->number);
387  switch(pattern_type)
388  {
389  case PhiOpt_PatternType::GIMPLE_NOTHING:
390  {
391  ApplyGimpleNothing(block->number);
392  bb_modified = true;
393  break;
394  }
395  case PhiOpt_PatternType::DIFF_NOTHING:
396  {
397  ApplyDiffNothing(block->number);
398  bb_modified = true;
399  restart = true;
400  break;
401  }
402  case PhiOpt_PatternType::IF_MERGE:
403  {
404  ApplyIfMerge(block->number);
405  bb_modified = true;
406  break;
407  }
408  case PhiOpt_PatternType::IF_NOTHING:
409  {
410  ApplyIfNothing(block->number);
411  bb_modified = true;
412  break;
413  }
414  case PhiOpt_PatternType::IF_REMOVE:
415  {
416  ApplyIfRemove(block->number);
417  bb_modified = true;
418  break;
419  }
420  case PhiOpt_PatternType::MULTI_MERGE:
421  {
422  ApplyMultiMerge(block->number);
423  bb_modified = true;
424  break;
425  }
426  case PhiOpt_PatternType::MULTI_NOTHING:
427  {
428  ApplyMultiNothing(block->number);
429  bb_modified = true;
430  break;
431  }
432  case PhiOpt_PatternType::MULTI_REMOVE:
433  {
434  ApplyMultiRemove(block->number);
435  bb_modified = true;
436  break;
437  }
438  case PhiOpt_PatternType::UNCHANGED:
439  {
440  break;
441  }
442  case PhiOpt_PatternType::UNKNOWN:
443  {
444  THROW_UNREACHABLE("Found an unknown pattern in CFG");
445  break;
446  }
447  default:
448  {
449  THROW_UNREACHABLE("");
450  break;
451  }
452  }
453  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed BB" + STR(block->number));
454  }
455  if(removePhiOnlyP)
456  {
457  removePhiOnly();
458  }
459  }
460 
461  TreeNodeSet ces_to_be_removed;
462 
463  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing redundant cond_expr");
464  for(const auto& block : sl->list_of_bloc)
465  {
466  for(const auto& statement : block.second->CGetStmtList())
467  {
468  const auto* ga = GetPointer<const gimple_assign>(GET_CONST_NODE(statement));
469  if(ga && GET_CONST_NODE(ga->op1)->get_kind() == cond_expr_K)
470  {
471  const auto* ce = GetPointer<const cond_expr>(GET_CONST_NODE(ga->op1));
472  if(ce && ce->op1->index == ce->op2->index)
473  {
474  ces_to_be_removed.insert(statement);
475  }
476  }
477  }
478  }
479  if(!ces_to_be_removed.empty())
480  {
481  bb_modified = true;
482  }
483  for(const auto& ce_to_be_removed : ces_to_be_removed)
484  {
485  RemoveCondExpr(ce_to_be_removed);
486  }
487 
488  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed redundant cond_expr");
489 
490  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing chains of BBs");
491  restart = true;
492 
493  while(restart)
494  {
495  restart = false;
497  for(const auto& block : sl->list_of_bloc)
498  {
499  if(block.first == bloc::ENTRY_BLOCK_ID)
500  {
501  continue;
502  }
503  if(block.second->list_of_succ.size() == 1)
504  {
505  const auto succ_block = block.second->list_of_succ.front();
506  THROW_ASSERT(sl->list_of_bloc.count(succ_block),
507  "Successor block BB" + STR(succ_block) + " does not exist");
508  if(sl->list_of_bloc.at(succ_block)->list_of_pred.size() == 1)
509  {
510  if(AppM->ApplyNewTransformation())
511  {
512  AppM->RegisterTransformation(GetName(), tree_nodeConstRef());
513  ChainOptimization(block.first);
514  bb_modified = true;
515  restart = true;
516  break;
517  }
518  }
519  }
520  }
521  }
522  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed chains of BB");
523 
524  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing nop with virtual operands");
525  for(const auto& block : sl->list_of_bloc)
526  {
527  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Analyzing BB" + STR(block.first));
528  TreeNodeSet to_be_removeds;
529  for(const auto& stmt : block.second->CGetStmtList())
530  {
531  const auto gn = GetPointerS<gimple_node>(GET_NODE(stmt));
532  if(gn->get_kind() != gimple_nop_K || !gn->vdef ||
533  (gn->vovers.find(gn->vdef) != gn->vovers.end() && gn->vovers.size() > 1) ||
534  (gn->vovers.find(gn->vdef) == gn->vovers.end() && (!gn->vovers.empty())))
535  {
536  if(gn->get_kind() == gimple_nop_K)
537  {
538  INDENT_DBG_MEX(
539  DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
540  "---skipped gimple nop " + STR(gn->index) + (!gn->vdef ? "NOVDEF " : "VDEF ") +
541  ((gn->vovers.find(gn->vdef) != gn->vovers.end() && gn->vovers.size() > 1) ? "cond1 " :
542  "not cond1 ") +
543  ((gn->vovers.find(gn->vdef) == gn->vovers.end() && (!gn->vovers.empty())) ? "cond2 " :
544  "not cond2 "));
545  }
546  continue;
547  }
548  if(AppM->ApplyNewTransformation())
549  {
550  const auto virtual_ssa = GetPointerS<ssa_name>(GET_NODE(gn->vdef));
551  THROW_ASSERT(virtual_ssa && virtual_ssa->virtual_flag, "unexpected condition");
552 
554  if(gn->vuses.size() == 1)
555  {
556  const auto vuse = *(gn->vuses.begin());
557  const auto uses = virtual_ssa->CGetUseStmts();
558  for(const auto& use : uses)
559  {
560  TM->ReplaceTreeNode(use.first, gn->vdef, vuse);
561  }
562  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Removing gimple nop " + STR(gn->index));
563  to_be_removeds.insert(stmt);
564  AppM->RegisterTransformation(GetName(), tree_nodeConstRef());
565  }
566  else
567  {
569  const auto canBeProp = [&]() -> bool {
570  for(const auto& use_stmt : virtual_ssa->CGetUseStmts())
571  {
572  if(GET_CONST_NODE(use_stmt.first)->get_kind() == gimple_phi_K)
573  {
574  return false;
575  }
576  if(GET_INDEX_CONST_NODE(use_stmt.first) == GET_INDEX_CONST_NODE(stmt))
577  {
578  return false;
579  }
580  }
581  return true;
582  }();
583  if(canBeProp)
584  {
585  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
586  "-->Virtual ssa " + GET_CONST_NODE(gn->vdef)->ToString() + " not used in any phi");
587  ReplaceVirtualUses(gn->vdef, gn->vuses);
588  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Removing gimple nop " + STR(gn->index));
589  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
590  to_be_removeds.insert(stmt);
591  AppM->RegisterTransformation(GetName(), tree_nodeConstRef());
592  }
593  }
594  }
595  }
596  for(const auto& to_be_removed : to_be_removeds)
597  {
598  block.second->RemoveStmt(to_be_removed, AppM);
599  }
600  if(!to_be_removeds.empty())
601  {
602  bb_modified = true;
603  }
604  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Analyzed BB" + STR(block.first));
605  }
606  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed nop with virtual operands");
607  bb_modified ? function_behavior->UpdateBBVersion() : 0;
608  return bb_modified ? DesignFlowStep_Status::SUCCESS : DesignFlowStep_Status::UNCHANGED;
609 }
610 
611 void PhiOpt::ApplyDiffNothing(const unsigned int bb_index)
612 {
613  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Duplicating empty basic block");
614  const auto& curr_block = sl->list_of_bloc.at(bb_index);
615  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
616  THROW_ASSERT(std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index) !=
617  succ_block->list_of_pred.end(),
618  "bb_index not included in the list of pred: " + STR(bb_index) + " succ: " + STR(succ_block->number));
619  succ_block->list_of_pred.erase(
620  std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index));
621 
622  CustomSet<unsigned int> created_bbs;
623 
624  for(auto pred : curr_block->list_of_pred)
625  {
626  const auto& pred_block = sl->list_of_bloc.at(pred);
627 
629  const auto new_basic_block_index = (sl->list_of_bloc.rbegin())->first + 1;
630  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
631  "-->Created BB" + STR(new_basic_block_index) + " as new successor of BB" + STR(pred));
632  created_bbs.insert(new_basic_block_index);
633  const auto new_block = blocRef(new bloc(new_basic_block_index));
634  sl->list_of_bloc[new_basic_block_index] = new_block;
635 
636  new_block->loop_id = curr_block->loop_id;
637  new_block->SetSSAUsesComputed();
638  new_block->schedule = pred_block->schedule;
639 
641  new_block->list_of_pred.push_back(pred);
642 
644  new_block->list_of_succ.push_back(succ_block->number);
645 
647  pred_block->list_of_succ.erase(
648  std::find(pred_block->list_of_succ.begin(), pred_block->list_of_succ.end(), bb_index));
649  pred_block->list_of_succ.push_back(new_basic_block_index);
650  if(pred_block->true_edge == bb_index)
651  {
652  pred_block->true_edge = new_basic_block_index;
653  }
654  if(pred_block->false_edge == bb_index)
655  {
656  pred_block->false_edge = new_basic_block_index;
657  }
658 
660  succ_block->list_of_pred.push_back(new_basic_block_index);
661 
663  if(pred_block->CGetStmtList().size())
664  {
665  auto pred_last_stmt = GET_NODE(pred_block->CGetStmtList().back());
666  if(pred_last_stmt->get_kind() == gimple_multi_way_if_K)
667  {
668  const auto gmwi = GetPointerS<gimple_multi_way_if>(pred_last_stmt);
669  for(auto& cond : gmwi->list_of_cond)
670  {
671  if(cond.second == curr_block->number)
672  {
673  cond.second = new_basic_block_index;
674  }
675  }
676  }
677  }
678  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
679  }
680 
681  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Fixing phis");
683  for(const auto& phi : succ_block->CGetPhiList())
684  {
685  const auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
686  gimple_phi::DefEdgeList new_list_of_def_edge;
687  auto curr_value = tree_nodeRef();
688 
689  for(auto& def : gp->CGetDefEdgesList())
690  {
691  if(def.second != curr_block->number)
692  {
693  new_list_of_def_edge.push_back(def);
694  }
695  else
696  {
697  curr_value = def.first;
698  }
699  }
700  for(auto pred : created_bbs)
701  {
702  new_list_of_def_edge.push_back(decltype(new_list_of_def_edge)::value_type(curr_value, pred));
703  }
704  gp->SetDefEdgeList(TM, new_list_of_def_edge);
705  }
706  sl->list_of_bloc.erase(bb_index);
707  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Duplicated BB" + STR(bb_index));
708 }
709 
710 void PhiOpt::ApplyIfMerge(const unsigned int bb_index)
711 {
712  const auto& curr_block = sl->list_of_bloc.at(bb_index);
713  const auto& pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
714  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
715 
716  const auto pred_stmt_list = pred_block->CGetStmtList();
717 
719  const auto true_edge = pred_block->true_edge == bb_index;
720 
722  const auto condition = tree_man->ExtractCondition(pred_stmt_list.back(), pred_block, function_id);
723 
725  pred_block->RemoveStmt(pred_stmt_list.back(), AppM);
726  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Condition is " + condition->ToString());
727 
729  for(const auto& phi : succ_block->CGetPhiList())
730  {
731  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Modifying " + phi->ToString());
733  tree_nodeRef true_value = nullptr;
734 
736  tree_nodeRef false_value = nullptr;
737 
738  const auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
739 
741  const auto type_node = tree_helper::CGetType(gp->res);
742 
743  for(const auto& def : gp->CGetDefEdgesList())
744  {
745  if((true_edge && bb_index == def.second) || (!true_edge && pred_block->number == def.second))
746  {
747  THROW_ASSERT(!true_value, "True value already found");
748  true_value = def.first;
749  }
750  else if((!true_edge && bb_index == def.second) || (true_edge && pred_block->number == def.second))
751  {
752  THROW_ASSERT(!false_value, "True value already found");
753  false_value = def.first;
754  }
755  }
756  THROW_ASSERT(true_value, "True value not found");
757  THROW_ASSERT(false_value, "False value not found");
758  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
759  "---From true edge " + GET_CONST_NODE(true_value)->ToString());
760  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
761  "---From false edge " + GET_CONST_NODE(false_value)->ToString());
762 
763  tree_nodeRef gimple_node;
764 
766  tree_nodeRef var = nullptr;
767  if(GET_CONST_NODE(true_value)->get_kind() == ssa_name_K && GET_CONST_NODE(false_value)->get_kind() == ssa_name_K)
768  {
769  const auto sn1 = GetPointerS<const ssa_name>(GET_CONST_NODE(true_value));
770  const auto sn2 = GetPointerS<const ssa_name>(GET_CONST_NODE(false_value));
771  if(sn1->var && sn2->var && sn1->var->index == sn2->var->index)
772  {
773  var = sn1->var;
774  }
775  }
776  const auto gp_res = GetPointer<const ssa_name>(GET_CONST_NODE(gp->res));
777  const auto ssa_node =
778  tree_man->create_ssa_name(var, type_node, gp_res->min, gp_res->max, false, gp->virtual_flag);
779  GetPointerS<ssa_name>(GET_NODE(ssa_node))->bit_values = gp_res->bit_values;
780  if(gp->virtual_flag)
781  {
783  std::map<TreeVocabularyTokenTypes_TokenEnum, std::string> gimple_nop_schema;
784  gimple_nop_schema[TOK(TOK_SRCP)] = BUILTIN_SRCP;
785  gimple_nop_schema[TOK(TOK_SCPE)] = STR(function_id);
786  const auto gimple_node_id = TM->new_tree_node_id();
787  TM->create_tree_node(gimple_node_id, gimple_nop_K, gimple_nop_schema);
788  gimple_node = TM->GetTreeReindex(gimple_node_id);
789  const auto gn = GetPointer<gimple_nop>(GET_NODE(gimple_node));
790  gn->SetVdef(ssa_node);
791  gn->AddVuse(true_value);
792  gn->AddVuse(false_value);
793  }
794  else
795  {
797  auto condition_type = tree_helper::CGetType(condition);
798  auto isAVectorType = tree_helper::is_a_vector(TM, GET_INDEX_CONST_NODE(condition_type));
799  const auto cond_expr_node =
800  tree_man->create_ternary_operation(type_node, condition, true_value, false_value, BUILTIN_SRCP,
801  (isAVectorType ? vec_cond_expr_K : cond_expr_K));
802  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
803  "---Created cond_expr " + GET_CONST_NODE(cond_expr_node)->ToString());
804 
806  gimple_node = tree_man->create_gimple_modify_stmt(ssa_node, cond_expr_node, function_id, BUILTIN_SRCP);
807  }
808  pred_block->PushBack(gimple_node, AppM);
809  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Created " + GET_CONST_NODE(gimple_node)->ToString());
810 
812  gimple_phi::DefEdgeList new_list_of_def_edge;
813  for(const auto& def : gp->CGetDefEdgesList())
814  {
815  if(def.second == pred_block->number)
816  {
817  new_list_of_def_edge.push_back(gimple_phi::DefEdge(ssa_node, pred_block->number));
818  }
819  else if(def.second == bb_index)
820  {
822  }
823  else
824  {
825  new_list_of_def_edge.push_back(def);
826  }
827  }
828  gp->SetDefEdgeList(TM, new_list_of_def_edge);
829  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Modified " + phi->ToString());
830  }
831 
833  pred_block->list_of_succ.clear();
834  pred_block->true_edge = 0;
835  pred_block->false_edge = 0;
836  pred_block->list_of_succ.push_back(succ_block->number);
837 
839  succ_block->list_of_pred.erase(
840  std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index));
841 
843  sl->list_of_bloc.erase(bb_index);
844 }
845 
846 void PhiOpt::ApplyIfNothing(const unsigned int bb_index)
847 {
848  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing empty basic block");
849  const auto& curr_block = sl->list_of_bloc.at(bb_index);
850  const auto& pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
851  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
852  for(const auto& phi : succ_block->CGetPhiList())
853  {
854  const auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
855  for(auto& def_edge : gp->CGetDefEdgesList())
856  {
857  if(def_edge.second == curr_block->number)
858  {
859  gp->ReplaceDefEdge(TM, def_edge, gimple_phi::DefEdge(def_edge.first, pred_block->number));
860  break;
861  }
862  }
863  }
864 
866  if(pred_block->true_edge == bb_index)
867  {
868  pred_block->true_edge = succ_block->number;
869  }
870  else if(pred_block->false_edge == bb_index)
871  {
872  pred_block->false_edge = succ_block->number;
873  }
874  else
875  {
876  THROW_UNREACHABLE("");
877  }
878  pred_block->list_of_succ.clear();
879  pred_block->list_of_succ.push_back(pred_block->true_edge);
880  pred_block->list_of_succ.push_back(pred_block->false_edge);
881 
883  succ_block->list_of_pred.erase(
884  std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index));
885  succ_block->list_of_pred.push_back(pred_block->number);
886 
888  sl->list_of_bloc.erase(bb_index);
889  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed BB" + STR(bb_index));
890 }
891 
892 void PhiOpt::ApplyGimpleNothing(const unsigned int bb_index)
893 {
894  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing empty basic block");
895  const auto& curr_block = sl->list_of_bloc.at(bb_index);
896  const auto& pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
897  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
898  for(const auto& phi : succ_block->CGetPhiList())
899  {
900  const auto gp = GetPointer<gimple_phi>(GET_NODE(phi));
901  for(auto& def_edge : gp->CGetDefEdgesList())
902  {
903  if(def_edge.second == curr_block->number)
904  {
905  gp->ReplaceDefEdge(TM, def_edge, gimple_phi::DefEdge(def_edge.first, pred_block->number));
906  break;
907  }
908  }
909  }
910 
912  pred_block->list_of_succ.erase(
913  std::find(pred_block->list_of_succ.begin(), pred_block->list_of_succ.end(), bb_index));
914  pred_block->list_of_succ.push_back(succ_block->number);
915 
917  succ_block->list_of_pred.erase(
918  std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index));
919  succ_block->list_of_pred.push_back(pred_block->number);
920 
922  sl->list_of_bloc.erase(bb_index);
923  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed BB" + STR(bb_index));
924 }
925 
926 void PhiOpt::ApplyIfRemove(const unsigned int bb_index)
927 {
928  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing phis dominated by if");
929  const auto& curr_block = sl->list_of_bloc.at(bb_index);
930  const auto& pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
931  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
932 
934  const auto true_edge = pred_block->true_edge == bb_index;
935 
937  THROW_ASSERT(pred_block->CGetStmtList().size(), "Statement list of predecessor is empty");
938 
940  const auto last_stmt = pred_block->CGetStmtList().back();
941  const auto condition = tree_man->ExtractCondition(last_stmt, pred_block, function_id);
942  pred_block->RemoveStmt(last_stmt, AppM);
943  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Condition is " + condition->ToString());
944 
946  for(const auto& phi : succ_block->CGetPhiList())
947  {
948  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing " + phi->ToString());
950  tree_nodeRef true_value = nullptr;
951 
953  tree_nodeRef false_value = nullptr;
954 
955  const auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
956 
958  const auto type_node = tree_helper::CGetType(gp->res);
959 
960  for(const auto& def_edge : gp->CGetDefEdgesList())
961  {
962  if((true_edge && bb_index == def_edge.second) || (!true_edge && pred_block->number == def_edge.second))
963  {
964  THROW_ASSERT(!true_value, "True value already found");
965  true_value = def_edge.first;
966  }
967  else if((!true_edge && bb_index == def_edge.second) || (true_edge && pred_block->number == def_edge.second))
968  {
969  THROW_ASSERT(!false_value, "False value already found");
970  false_value = def_edge.first;
971  }
972  else
973  {
974  THROW_UNREACHABLE(std::string(true_edge ? "BB is on the true edge" : "BB is on the false edge") +
975  " - Condition comes from BB" + STR(def_edge.second) + " - If basic block is BB" +
976  STR((pred_block->number)));
977  }
978  }
979  THROW_ASSERT(true_value, "True value not found");
980  THROW_ASSERT(false_value, "False value not found");
981  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
982  "---From true edge " + GET_CONST_NODE(true_value)->ToString());
983  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
984  "---From false edge " + GET_CONST_NODE(false_value)->ToString());
985 
986  if(gp->virtual_flag)
987  {
988  const auto virtual_ssa = GetPointerS<ssa_name>(GET_NODE(gp->res));
989  bool create_gimple_nop = false;
990  for(const auto& use_stmt : virtual_ssa->CGetUseStmts())
991  {
992  if(GET_NODE(use_stmt.first)->get_kind() == gimple_phi_K)
993  {
994  create_gimple_nop = true;
995  }
996  }
997  if(create_gimple_nop)
998  {
999  const auto gimple_node_id = TM->new_tree_node_id();
1000  {
1001  std::map<TreeVocabularyTokenTypes_TokenEnum, std::string> gimple_nop_schema;
1002  gimple_nop_schema[TOK(TOK_SRCP)] = BUILTIN_SRCP;
1003  gimple_nop_schema[TOK(TOK_SCPE)] = STR(function_id);
1004  TM->create_tree_node(gimple_node_id, gimple_nop_K, gimple_nop_schema);
1005  }
1006  const auto gn = GetPointerS<gimple_nop>(TM->GetTreeNode(gimple_node_id));
1007  gn->SetVdef(gp->res);
1008  gn->AddVuse(true_value);
1009  gn->AddVuse(false_value);
1010  succ_block->PushFront(TM->GetTreeReindex(gimple_node_id), AppM);
1011  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Created " + gn->ToString());
1012  }
1013  else
1014  {
1015  TreeNodeSet new_ssas;
1016  for(const auto& def_edge : gp->CGetDefEdgesList())
1017  {
1018  new_ssas.insert(def_edge.first);
1019  }
1020  ReplaceVirtualUses(gp->res, new_ssas);
1021  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Substituted vuses ");
1022  }
1023  }
1024  else
1025  {
1027  auto condition_type = tree_helper::CGetType(condition);
1028  auto isAVectorType = tree_helper::is_a_vector(TM, GET_INDEX_CONST_NODE(condition_type));
1029  const auto cond_expr_node =
1030  tree_man->create_ternary_operation(type_node, condition, true_value, false_value, BUILTIN_SRCP,
1031  (isAVectorType ? vec_cond_expr_K : cond_expr_K));
1032  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1033  "---Created cond_expr " + GET_CONST_NODE(cond_expr_node)->ToString());
1034 
1036  const auto gimple_node =
1037  tree_man->create_gimple_modify_stmt(gp->res, cond_expr_node, function_id, BUILTIN_SRCP);
1038  succ_block->PushFront(gimple_node, AppM);
1039  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1040  "<--Created " + GET_CONST_NODE(gimple_node)->ToString());
1041  }
1042  }
1043 
1044  while(succ_block->CGetPhiList().size())
1045  {
1046  succ_block->RemovePhi(succ_block->CGetPhiList().front());
1047  }
1048 
1050  pred_block->list_of_succ.clear();
1051  pred_block->true_edge = 0;
1052  pred_block->false_edge = 0;
1053  pred_block->list_of_succ.push_back(succ_block->number);
1054 
1056  succ_block->list_of_pred.erase(
1057  std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index));
1058 
1060  sl->list_of_bloc.erase(bb_index);
1061  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed phis");
1062 }
1063 
1064 void PhiOpt::ApplyMultiMerge(const unsigned int bb_index)
1065 {
1066  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing BB" + STR(bb_index));
1067  const auto& curr_block = sl->list_of_bloc.at(bb_index);
1068  const auto& pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
1069  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
1070 
1071  auto& pred_stmt_list = pred_block->CGetStmtList();
1072 
1074  auto first_edge = false;
1075 
1077  THROW_ASSERT(GET_NODE(pred_stmt_list.back())->get_kind() == gimple_multi_way_if_K, "");
1078  const auto gmwi = GetPointerS<gimple_multi_way_if>(GET_NODE(pred_stmt_list.back()));
1079 
1081  pred_block->RemoveStmt(pred_stmt_list.back(), AppM);
1082 
1084  auto first_condition = std::pair<tree_nodeRef, unsigned int>(tree_nodeRef(), 0);
1085 
1087  auto second_condition = std::pair<tree_nodeRef, unsigned int>(tree_nodeRef(), 0);
1088 
1089  for(const auto& cond : gmwi->list_of_cond)
1090  {
1091  if(cond.second == curr_block->number)
1092  {
1093  if(!first_condition.first)
1094  {
1095  first_condition = cond;
1096  first_edge = true;
1097  }
1098  else
1099  {
1100  second_condition = cond;
1101  break;
1102  }
1103  }
1104  else if(cond.second == succ_block->number)
1105  {
1106  if(!first_condition.first)
1107  {
1108  first_condition = cond;
1109  first_edge = false;
1110  }
1111  else
1112  {
1113  second_condition = cond;
1114  break;
1115  }
1116  }
1117  }
1118 
1119  const auto new_cond = [&]() -> unsigned int {
1120  if(second_condition.first)
1121  {
1122  const auto new_node =
1123  tree_man->CreateOrExpr(first_condition.first, second_condition.first, pred_block, function_id);
1124  return new_node->index;
1125  }
1126  else
1127  {
1128  return 0;
1129  }
1130  }();
1131 
1132  decltype(gmwi->list_of_cond) new_list_of_cond;
1133  for(const auto& cond : gmwi->list_of_cond)
1134  {
1135  if(cond == first_condition)
1136  {
1137  if(second_condition.first)
1138  {
1139  new_list_of_cond.push_front(gimple_phi::DefEdge(TM->GetTreeReindex(new_cond), succ_block->number));
1140  }
1141  else
1142  {
1143  new_list_of_cond.push_back(gimple_phi::DefEdge(tree_nodeRef(), succ_block->number));
1144  }
1145  }
1146  else if(cond != second_condition)
1147  {
1148  if(cond.first)
1149  {
1150  new_list_of_cond.push_front(cond);
1151  }
1152  else
1153  {
1154  new_list_of_cond.push_back(cond);
1155  }
1156  }
1157  }
1158  gmwi->list_of_cond = new_list_of_cond;
1159  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---New gimple multi way if " + gmwi->ToString());
1160 
1162  for(const auto& phi : succ_block->CGetPhiList())
1163  {
1164  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Modifying phi " + phi->ToString());
1166  tree_nodeRef first_value = nullptr;
1167 
1169  tree_nodeRef second_value = nullptr;
1170 
1171  auto gp = GetPointer<gimple_phi>(GET_NODE(phi));
1172 
1174  const auto type_node = tree_helper::CGetType(gp->res);
1175 
1176  for(const auto& def_edge : gp->CGetDefEdgesList())
1177  {
1178  if((first_edge && bb_index == def_edge.second) || (!first_edge && pred_block->number == def_edge.second))
1179  {
1180  first_value = def_edge.first;
1181  }
1182  else if((!first_edge && bb_index == def_edge.second) || (first_edge && pred_block->number == def_edge.second))
1183  {
1184  second_value = def_edge.first;
1185  }
1186  }
1187 
1189  tree_nodeRef var;
1190  if(GET_CONST_NODE(first_value)->get_kind() == ssa_name_K &&
1191  GET_CONST_NODE(second_value)->get_kind() == ssa_name_K)
1192  {
1193  const auto sn1 = GetPointer<const ssa_name>(GET_CONST_NODE(first_value));
1194  const auto sn2 = GetPointer<const ssa_name>(GET_CONST_NODE(second_value));
1195  if(sn1->var && sn2->var && sn1->var->index == sn2->var->index)
1196  {
1197  var = sn1->var;
1198  }
1199  }
1200  const auto gp_res = GetPointer<const ssa_name>(GET_NODE(gp->res));
1201  const auto ssa_node =
1202  tree_man->create_ssa_name(var, type_node, gp_res->min, gp_res->max, false, gp->virtual_flag);
1203  GetPointer<ssa_name>(GET_NODE(ssa_node))->bit_values = gp_res->bit_values;
1204  tree_nodeRef gimple_node;
1205  if(gp->virtual_flag)
1206  {
1208  std::map<TreeVocabularyTokenTypes_TokenEnum, std::string> gimple_nop_schema;
1209  gimple_nop_schema[TOK(TOK_SRCP)] = BUILTIN_SRCP;
1210  gimple_nop_schema[TOK(TOK_SCPE)] = STR(function_id);
1211  const auto gimple_node_id = TM->new_tree_node_id();
1212  TM->create_tree_node(gimple_node_id, gimple_nop_K, gimple_nop_schema);
1213  gimple_node = TM->GetTreeReindex(gimple_node_id);
1214  auto gn = GetPointer<gimple_nop>(GET_NODE(gimple_node));
1215  gn->SetVdef(ssa_node);
1216  gn->AddVuse(first_value);
1217  gn->AddVuse(second_value);
1218  }
1219  else
1220  {
1222  auto condition_type = tree_helper::CGetType(first_condition.first);
1223  auto isAVectorType = tree_helper::is_a_vector(TM, GET_INDEX_CONST_NODE(condition_type));
1224  const auto cond_expr_node =
1225  tree_man->create_ternary_operation(type_node, first_condition.first, first_value, second_value,
1226  BUILTIN_SRCP, (isAVectorType ? vec_cond_expr_K : cond_expr_K));
1227 
1229  gimple_node = tree_man->create_gimple_modify_stmt(ssa_node, cond_expr_node, function_id, BUILTIN_SRCP);
1230  }
1231  pred_block->PushBack(gimple_node, AppM);
1232 
1234  gimple_phi::DefEdgeList new_list_of_def_edge;
1235  for(const auto& def_edge : gp->CGetDefEdgesList())
1236  {
1237  if(def_edge.second == pred_block->number)
1238  {
1239  new_list_of_def_edge.push_back(gimple_phi::DefEdge(ssa_node, pred_block->number));
1240  }
1241  else if(def_edge.second == bb_index)
1242  {
1244  }
1245  else
1246  {
1247  new_list_of_def_edge.push_back(def_edge);
1248  }
1249  }
1250  gp->SetDefEdgeList(TM, new_list_of_def_edge);
1251  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Modified phi " + phi->ToString());
1252  }
1253 
1255  if(gmwi->list_of_cond.size() >= 2)
1256  {
1257  pred_block->PushBack(TM->GetTreeReindex(gmwi->index), AppM);
1258  }
1259 
1261  pred_block->list_of_succ.erase(
1262  std::find(pred_block->list_of_succ.begin(), pred_block->list_of_succ.end(), bb_index));
1263 
1265  succ_block->list_of_pred.erase(
1266  std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index));
1267 
1269  sl->list_of_bloc.erase(bb_index);
1270  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed BB" + STR(bb_index));
1271 }
1272 
1273 void PhiOpt::ApplyMultiNothing(const unsigned int bb_index)
1274 {
1275  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing empty basic block");
1276  const auto& curr_block = sl->list_of_bloc.at(bb_index);
1277  const auto& pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
1278  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
1279 
1280  THROW_ASSERT(GET_NODE(pred_block->CGetStmtList().back())->get_kind() == gimple_multi_way_if_K, "");
1281  const auto gmwi = GetPointerS<gimple_multi_way_if>(GET_NODE(pred_block->CGetStmtList().back()));
1282  for(auto& cond : gmwi->list_of_cond)
1283  {
1284  if(cond.second == bb_index)
1285  {
1286  cond.second = succ_block->number;
1287  break;
1288  }
1289  }
1290 
1291  for(const auto& phi : succ_block->CGetPhiList())
1292  {
1293  const auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
1294  for(auto& def_edge : gp->CGetDefEdgesList())
1295  {
1296  if(def_edge.second == curr_block->number)
1297  {
1298  gp->ReplaceDefEdge(TM, def_edge, gimple_phi::DefEdge(def_edge.first, pred_block->number));
1299  break;
1300  }
1301  }
1302  }
1303 
1305  pred_block->list_of_succ.erase(
1306  std::find(pred_block->list_of_succ.begin(), pred_block->list_of_succ.end(), bb_index));
1307  pred_block->list_of_succ.push_back(succ_block->number);
1308 
1310  succ_block->list_of_pred.erase(
1311  std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index));
1312  succ_block->list_of_pred.push_back(pred_block->number);
1313 
1315  sl->list_of_bloc.erase(bb_index);
1316  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed BB" + STR(bb_index));
1317 }
1318 
1319 void PhiOpt::ApplyMultiRemove(const unsigned int bb_index)
1320 {
1321  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing BB" + STR(bb_index));
1322  const auto& curr_block = sl->list_of_bloc.at(bb_index);
1323  const auto& pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
1324  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
1325 
1326  const auto& pred_stmt_list = pred_block->CGetStmtList();
1327 
1329  auto first_edge = false;
1330 
1332  THROW_ASSERT(GET_NODE(pred_stmt_list.back())->get_kind() == gimple_multi_way_if_K, "");
1333  const auto gmwi = GetPointerS<gimple_multi_way_if>(GET_NODE(pred_stmt_list.back()));
1334  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Multi way if is " + gmwi->ToString());
1335 
1337  pred_block->RemoveStmt(pred_stmt_list.back(), AppM);
1338 
1340  auto first_condition = std::pair<tree_nodeRef, unsigned int>(tree_nodeRef(), 0);
1341 
1343  auto second_condition = std::pair<tree_nodeRef, unsigned int>(tree_nodeRef(), 0);
1344 
1345  for(const auto& cond : gmwi->list_of_cond)
1346  {
1347  if(cond.second == curr_block->number)
1348  {
1349  if(!first_condition.first)
1350  {
1351  first_condition = cond;
1352  first_edge = true;
1353  }
1354  else
1355  {
1356  second_condition = cond;
1357  break;
1358  }
1359  }
1360  else if(cond.second == succ_block->number)
1361  {
1362  if(!first_condition.first)
1363  {
1364  first_condition = cond;
1365  first_edge = false;
1366  }
1367  else
1368  {
1369  second_condition = cond;
1370  break;
1371  }
1372  }
1373  }
1374  THROW_ASSERT(first_condition.first, "First condition is empty");
1375  const auto new_cond = [&]() -> tree_nodeRef {
1376  if(second_condition.first)
1377  {
1378  const auto new_node =
1379  tree_man->CreateOrExpr(first_condition.first, second_condition.first, pred_block, function_id);
1380  return new_node;
1381  }
1382  return nullptr;
1383  }();
1384 
1385  decltype(gmwi->list_of_cond) new_list_of_cond;
1386  for(const auto& cond : gmwi->list_of_cond)
1387  {
1388  if(cond == first_condition)
1389  {
1390  if(second_condition.first)
1391  {
1392  new_list_of_cond.push_front(gimple_phi::DefEdge(new_cond, succ_block->number));
1393  }
1394  else
1395  {
1396  new_list_of_cond.push_back(gimple_phi::DefEdge(nullptr, succ_block->number));
1397  }
1398  }
1399  else if(cond != second_condition)
1400  {
1401  if(cond.first)
1402  {
1403  new_list_of_cond.push_front(cond);
1404  }
1405  else
1406  {
1407  new_list_of_cond.push_back(cond);
1408  }
1409  }
1410  }
1411  gmwi->list_of_cond = new_list_of_cond;
1412  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Rewritten gimple multi way if as " + gmwi->ToString());
1413 
1415  for(const auto& phi : succ_block->CGetPhiList())
1416  {
1418  tree_nodeRef first_value = nullptr;
1419 
1421  tree_nodeRef second_value = nullptr;
1422 
1423  const auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
1424 
1426  const auto type_node = tree_helper::CGetType(gp->res);
1427 
1428  for(const auto& def_edge : gp->CGetDefEdgesList())
1429  {
1430  if((first_edge && bb_index == def_edge.second) || (!first_edge && pred_block->number == def_edge.second))
1431  {
1432  first_value = def_edge.first;
1433  }
1434  else if((!first_edge && bb_index == def_edge.second) || (first_edge && pred_block->number == def_edge.second))
1435  {
1436  second_value = def_edge.first;
1437  }
1438  else
1439  {
1440  THROW_UNREACHABLE("");
1441  }
1442  }
1443  tree_nodeRef new_gimple_node = nullptr;
1444  bool create_gimple_nop = false;
1445  if(gp->virtual_flag)
1446  {
1447  const auto virtual_ssa = GetPointerS<ssa_name>(GET_NODE(gp->res));
1448  for(const auto& use_stmt : virtual_ssa->CGetUseStmts())
1449  {
1450  if(GET_CONST_NODE(use_stmt.first)->get_kind() == gimple_phi_K)
1451  {
1452  create_gimple_nop = true;
1453  }
1454  }
1455  if(create_gimple_nop)
1456  {
1458  const auto gimple_node_id = TM->new_tree_node_id();
1459  std::map<TreeVocabularyTokenTypes_TokenEnum, std::string> gimple_nop_schema;
1460  gimple_nop_schema[TOK(TOK_SRCP)] = BUILTIN_SRCP;
1461  gimple_nop_schema[TOK(TOK_SCPE)] = STR(function_id);
1462  TM->create_tree_node(gimple_node_id, gimple_nop_K, gimple_nop_schema);
1463  new_gimple_node = TM->GetTreeReindex(gimple_node_id);
1464  const auto gn = GetPointerS<gimple_nop>(GET_NODE(new_gimple_node));
1465  gn->SetVdef(gp->res);
1466  gn->AddVuse(first_value);
1467  gn->AddVuse(second_value);
1468  }
1469  else
1470  {
1471  TreeNodeSet new_ssas;
1472  new_ssas.insert(first_value);
1473  new_ssas.insert(second_value);
1474  ReplaceVirtualUses(gp->res, new_ssas);
1475  }
1476  }
1477  else
1478  {
1480  auto condition_type = tree_helper::CGetType(first_condition.first);
1481  auto isAVectorType = tree_helper::is_a_vector(TM, GET_INDEX_CONST_NODE(condition_type));
1482  const auto cond_expr_node =
1483  tree_man->create_ternary_operation(type_node, first_condition.first, first_value, second_value,
1484  BUILTIN_SRCP, (isAVectorType ? vec_cond_expr_K : cond_expr_K));
1485 
1487  new_gimple_node = tree_man->create_gimple_modify_stmt(gp->res, cond_expr_node, function_id, BUILTIN_SRCP);
1488  }
1489  if(!gp->virtual_flag || create_gimple_nop)
1490  {
1491  succ_block->PushFront(new_gimple_node, AppM);
1492  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1493  "---Added gimple assignment " + GET_CONST_NODE(new_gimple_node)->ToString());
1494  }
1495  }
1496 
1498  if(gmwi->list_of_cond.size() >= 2)
1499  {
1500  pred_block->PushBack(TM->GetTreeReindex(gmwi->index), AppM);
1501  }
1502 
1503  while(succ_block->CGetPhiList().size())
1504  {
1505  succ_block->RemovePhi(succ_block->CGetPhiList().front());
1506  }
1507 
1509  pred_block->list_of_succ.erase(
1510  std::find(pred_block->list_of_succ.begin(), pred_block->list_of_succ.end(), bb_index));
1511 
1513  succ_block->list_of_pred.clear();
1514  succ_block->list_of_pred.push_back(pred_block->number);
1515 
1517  sl->list_of_bloc.erase(bb_index);
1518  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed BB" + STR(bb_index));
1519 }
1520 
1521 PhiOpt_PatternType PhiOpt::IdentifyPattern(const unsigned int bb_index) const
1522 {
1523  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Identifying pattern starting from BB" + STR(bb_index));
1524  const auto& curr_block = sl->list_of_bloc.at(bb_index);
1525  if(curr_block->list_of_pred.size() == 1 && curr_block->list_of_pred.front() == bloc::ENTRY_BLOCK_ID)
1526  {
1527  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Empty basic block connected to Entry");
1528  return PhiOpt_PatternType::UNCHANGED;
1529  }
1530  if(std::find(curr_block->list_of_succ.begin(), curr_block->list_of_succ.end(), bb_index) !=
1531  curr_block->list_of_succ.end())
1532  {
1533  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Sink BB");
1534  return PhiOpt_PatternType::UNCHANGED;
1535  }
1536  if(curr_block->CGetStmtList().empty() && curr_block->list_of_pred.size() == 2 &&
1537  curr_block->list_of_succ.size() == 1)
1538  {
1539  const auto succ_bbi = curr_block->list_of_succ.front();
1540  const auto loop_bb = std::find(curr_block->list_of_pred.begin(), curr_block->list_of_pred.end(), succ_bbi);
1541  const auto infinite_empty_loop =
1542  sl->list_of_bloc.at(succ_bbi)->CGetStmtList().empty() && loop_bb != curr_block->list_of_pred.end();
1543  if(infinite_empty_loop)
1544  {
1545  INDENT_OUT_MEX(OUTPUT_LEVEL_MINIMUM, output_level,
1546  "Infinite empty loop is present in the code in function " +
1547  function_behavior->CGetBehavioralHelper()->GetMangledFunctionName());
1548  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Infinite empty loop");
1549  return PhiOpt_PatternType::UNCHANGED;
1550  }
1551  }
1552  if(curr_block->list_of_pred.size() != 1)
1553  {
1554  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Multiple empty paths");
1555  return PhiOpt_PatternType::DIFF_NOTHING;
1556  }
1557  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
1558  THROW_ASSERT(succ_block->number != bloc::EXIT_BLOCK_ID, "");
1559  const auto& pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
1560  const auto phi_size = succ_block->list_of_pred.size();
1561  for(const auto& phi : succ_block->CGetPhiList())
1562  {
1563  const auto gp = GetPointerS<const gimple_phi>(GET_CONST_NODE(phi));
1564  if(phi_size != gp->CGetDefEdgesList().size())
1565  {
1566  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1567  "<--Unknown because successor contain phi " + STR(phi) +
1568  " with different size: " + STR(phi_size) + " vs. " + STR(gp->CGetDefEdgesList().size()));
1569  return PhiOpt_PatternType::UNKNOWN;
1570  }
1571  }
1572  if(std::find(pred_block->list_of_succ.begin(), pred_block->list_of_succ.end(), succ_block->number) ==
1573  pred_block->list_of_succ.end())
1574  {
1575  if(pred_block->list_of_succ.size() == 1)
1576  {
1577  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1578  "<--Empty basic block with predecessor with single Exit");
1579  return PhiOpt_PatternType::GIMPLE_NOTHING;
1580  }
1581  if(pred_block->CGetStmtList().size())
1582  {
1583  const auto pred_last_stmt = GET_CONST_NODE(pred_block->CGetStmtList().back());
1584  if(pred_last_stmt->get_kind() == gimple_cond_K)
1585  {
1586  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1587  "<--Basic block dominated by if which can be removed");
1588  return PhiOpt_PatternType::IF_NOTHING;
1589  }
1590  if(pred_last_stmt->get_kind() == gimple_multi_way_if_K)
1591  {
1592  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1593  "<--Basic block dominated by multi way if which can be removed");
1594  return PhiOpt_PatternType::MULTI_NOTHING;
1595  }
1596  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1597  "<--Unknown because it can be removed but it is controlled by " +
1598  pred_last_stmt->get_kind_text());
1599  return PhiOpt_PatternType::UNKNOWN;
1600  }
1601  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1602  "<--Unknown because it can be removed but predecessor is empty");
1603  return PhiOpt_PatternType::UNKNOWN;
1604  }
1605  if(phi_size == 0)
1606  {
1607  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Unknown because it does not contain phi");
1608  return PhiOpt_PatternType::UNKNOWN;
1609  }
1610  if(phi_size == 1)
1611  {
1612  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Unknown because of single phi");
1613  return PhiOpt_PatternType::UNKNOWN;
1614  }
1615  if(phi_size == 2)
1616  {
1617  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Phis with size 2");
1618  if(pred_block->CGetStmtList().empty())
1619  {
1620  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Unknown because predecessor is empty");
1621  return PhiOpt_PatternType::UNKNOWN;
1622  }
1623  const auto pred_last_stmt = GET_CONST_NODE(pred_block->CGetStmtList().back());
1624  if(pred_last_stmt->get_kind() == gimple_cond_K)
1625  {
1626  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Empty then or empty else");
1627  return PhiOpt_PatternType::IF_REMOVE;
1628  }
1629  if(pred_last_stmt->get_kind() == gimple_multi_way_if_K)
1630  {
1631  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Controlled by multi way if");
1632  if(schedule)
1633  {
1635  const auto gmwi = GetPointer<const gimple_multi_way_if>(pred_last_stmt);
1636 
1638  auto first_condition = tree_nodeRef();
1639  auto second_condition = tree_nodeRef();
1640 
1641  for(const auto& cond : gmwi->list_of_cond)
1642  {
1643  if(cond.second == curr_block->number || cond.second == succ_block->number)
1644  {
1645  if(!first_condition)
1646  {
1647  first_condition = cond.first;
1648  }
1649  else
1650  {
1651  second_condition = cond.first;
1652  }
1653  }
1654  }
1655  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1656  "---First condition is " + (first_condition ? first_condition->ToString() : "default"));
1657  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1658  "---Second condition is " + (second_condition ? second_condition->ToString() : "default"));
1659  if(!first_condition || !second_condition ||
1660  schedule->EvaluateCondsMerging(pred_last_stmt->index, first_condition->index, second_condition->index,
1661  function_id))
1662  {
1663  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Empty path to phi to be removed");
1664  return PhiOpt_PatternType::MULTI_REMOVE;
1665  }
1666  else
1667  {
1668  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1669  "<--New gimple multi way if would increase basic block latency");
1670  return PhiOpt_PatternType::UNCHANGED;
1671  }
1672  }
1673  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Empty path to phi to be removed");
1674  return PhiOpt_PatternType::MULTI_REMOVE;
1675  }
1676  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1677  "<--Unknown because dominator of phi is " + pred_last_stmt->ToString());
1678  return PhiOpt_PatternType::UNKNOWN;
1679  }
1680  if(pred_block->CGetStmtList().empty())
1681  {
1682  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Unknown because predecessor is empty");
1683  return PhiOpt_PatternType::UNKNOWN;
1684  }
1685  const auto pred_last_stmt = GET_CONST_NODE(pred_block->CGetStmtList().back());
1686  if(pred_last_stmt->get_kind() == gimple_cond_K)
1687  {
1688  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Empty nested then || empty else");
1689  return PhiOpt_PatternType::IF_MERGE;
1690  }
1691  if(pred_last_stmt->get_kind() == gimple_multi_way_if_K)
1692  {
1694  if(succ_block->CGetStmtList().size() == 1 &&
1695  GetPointer<const gimple_return>(GET_CONST_NODE(succ_block->CGetStmtList().front())))
1696  {
1697  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Empty path to phi to be merged");
1698  return PhiOpt_PatternType::MULTI_MERGE;
1699  }
1700  if(schedule)
1701  {
1702  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1703  "-->Potentially is a path to phi to be merged. Checking timing");
1705 
1707  THROW_ASSERT(GET_CONST_NODE(pred_block->CGetStmtList().back())->get_kind() == gimple_multi_way_if_K, "");
1708  const auto gmwi = GetPointerS<const gimple_multi_way_if>(GET_CONST_NODE(pred_block->CGetStmtList().back()));
1709 
1711  auto condition = tree_nodeRef();
1712 
1713  for(const auto& cond : gmwi->list_of_cond)
1714  {
1715  if(cond.second == curr_block->number || cond.second == succ_block->number)
1716  {
1717  condition = cond.first;
1718  break;
1719  }
1720  }
1721  THROW_ASSERT(condition, "Condition not found");
1722  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Condition is " + condition->ToString());
1723 
1724  const auto& list_of_phi = succ_block->CGetPhiList();
1725  for(const auto& phi : list_of_phi)
1726  {
1728  tree_nodeRef first_value = nullptr;
1729 
1731  tree_nodeRef second_value = nullptr;
1732 
1734  auto first_edge = false;
1735 
1736  const auto gp = GetPointerS<const gimple_phi>(GET_CONST_NODE(phi));
1737 
1739  const auto type_node = tree_helper::CGetType(gp->res);
1740 
1741  for(const auto& def_edge : gp->CGetDefEdgesList())
1742  {
1743  if((first_edge && bb_index == def_edge.second) || (!first_edge && pred_block->number == def_edge.second))
1744  {
1745  first_value = def_edge.first;
1746  }
1747  else if((!first_edge && bb_index == def_edge.second) ||
1748  (first_edge && pred_block->number == def_edge.second))
1749  {
1750  second_value = def_edge.first;
1751  }
1752  }
1753 
1755  auto condition_type = tree_helper::CGetType(condition);
1756  auto isAVectorType = tree_helper::is_a_vector(TM, GET_INDEX_CONST_NODE(condition_type));
1757  const auto cond_expr_node =
1758  tree_man->create_ternary_operation(type_node, condition, first_value, second_value, BUILTIN_SRCP,
1759  (isAVectorType ? vec_cond_expr_K : cond_expr_K));
1760 
1764  const auto gimple_assign_node =
1765  tree_man->create_gimple_modify_stmt(first_value, cond_expr_node, function_id, BUILTIN_SRCP);
1766 
1768  if(schedule && schedule->CanBeMoved(GET_INDEX_CONST_NODE(gimple_assign_node), pred_block->number) !=
1769  FunctionFrontendFlowStep_Movable::MOVABLE)
1770  {
1771  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1772  INDENT_DBG_MEX(
1773  DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1774  "<--Empty path to phi to be merged, but modifying would increase the latency of predecessor");
1775  return PhiOpt_PatternType::UNCHANGED;
1776  }
1777  }
1778  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1779  }
1780  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Empty path to phi to be merged");
1781  return PhiOpt_PatternType::MULTI_MERGE;
1782  }
1783  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1784  "<--Unknown because dominator of phi is " + pred_last_stmt->ToString());
1785  return PhiOpt_PatternType::UNKNOWN;
1786 }
1787 
1788 void PhiOpt::SinglePhiOptimization(const unsigned int bb_index)
1789 {
1790  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing phis of BB" + STR(bb_index));
1791  const auto curr_block = sl->list_of_bloc.at(bb_index);
1792  THROW_ASSERT(curr_block->list_of_pred.size() == 1, "Basic block with single phis but not a single predecessor");
1793  const auto pred_block = sl->list_of_bloc.at(curr_block->list_of_pred.front());
1794  for(const auto& phi : boost::adaptors::reverse(curr_block->CGetPhiList()))
1795  {
1796  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Fixing using of ssa defined in " + phi->ToString());
1797  const auto gp = GetPointerS<const gimple_phi>(GET_CONST_NODE(phi));
1798  const auto& left_part = gp->res;
1799  THROW_ASSERT(gp->CGetDefEdgesList().size() == 1, "");
1800  const auto right_part = gp->CGetDefEdgesList().front().first;
1801  const auto left_ssa = GetPointerS<const ssa_name>(GET_CONST_NODE(gp->res));
1803  TreeNodeSet use_stmts;
1804  for(const auto& use_stmt : left_ssa->CGetUseStmts())
1805  {
1806  if(use_stmt.first->index != gp->index)
1807  {
1808  use_stmts.insert(use_stmt.first);
1809  }
1810  }
1811 
1812  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1813  "-->Replacing " + left_part->ToString() + " with " + right_part->ToString());
1814  for(const auto& use_stmt : use_stmts)
1815  {
1816  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Before ssa replacement " + use_stmt->ToString());
1817  TM->ReplaceTreeNode(use_stmt, left_part, right_part);
1818  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---After ssa replacement " + use_stmt->ToString());
1819  }
1820  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
1821  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Fixed using of ssa defined in " + phi->ToString());
1822  }
1823  while(curr_block->CGetPhiList().size())
1824  {
1825  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1826  "---Removing " + curr_block->CGetPhiList().front()->ToString());
1827  curr_block->RemovePhi(curr_block->CGetPhiList().front());
1828  }
1829  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed phis of BB" + STR(bb_index));
1830 }
1831 
1832 void PhiOpt::ChainOptimization(const unsigned int bb_index)
1833 {
1834  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1835  "-->Applying chaining optimization starting from BB" + STR(bb_index));
1836  const auto& curr_block = sl->list_of_bloc.at(bb_index);
1837  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
1838 
1840  THROW_ASSERT(succ_block->CGetPhiList().empty(), "Second element of the chain has phi");
1841 
1843  while(succ_block->CGetStmtList().size())
1844  {
1845  const auto statement = succ_block->CGetStmtList().front();
1846  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Moving " + STR(statement));
1847  succ_block->RemoveStmt(statement, AppM);
1848  curr_block->PushBack(statement, AppM);
1849  }
1850  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Moved statement");
1851 
1853  curr_block->true_edge = succ_block->true_edge;
1854  curr_block->false_edge = succ_block->false_edge;
1855  curr_block->list_of_succ = succ_block->list_of_succ;
1856 
1858  for(auto succ_succ : succ_block->list_of_succ)
1859  {
1860  if(succ_succ != bloc::EXIT_BLOCK_ID)
1861  {
1862  const auto& succ_succ_block = sl->list_of_bloc.at(succ_succ);
1863  succ_succ_block->list_of_pred.erase(
1864  std::find(succ_succ_block->list_of_pred.begin(), succ_succ_block->list_of_pred.end(), succ_block->number));
1865  succ_succ_block->list_of_pred.push_back(curr_block->number);
1866  for(const auto& phi : succ_succ_block->CGetPhiList())
1867  {
1868  const auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
1869  for(auto& def_edge : gp->CGetDefEdgesList())
1870  {
1871  if(def_edge.second == succ_block->number)
1872  {
1873  gp->ReplaceDefEdge(TM, def_edge, gimple_phi::DefEdge(def_edge.first, curr_block->number));
1874  break;
1875  }
1876  }
1877  }
1878  }
1879  }
1880 
1882  sl->list_of_bloc.erase(succ_block->number);
1883  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed BB" + STR(succ_block->number));
1884 }
1885 
1886 void PhiOpt::MergePhi(const unsigned int bb_index)
1887 {
1888  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Merging phi of BB" + STR(bb_index));
1889  const auto& curr_block = sl->list_of_bloc.at(bb_index);
1890  THROW_ASSERT(curr_block->list_of_succ.size() == 1,
1891  "BB" + STR(bb_index) + " has " + STR(curr_block->list_of_succ.size()));
1892  const auto& succ_block = sl->list_of_bloc.at(curr_block->list_of_succ.front());
1893  const auto& pred_succ_block = succ_block->list_of_pred;
1894  // This check has to be performed here since the structure of the basic block may be changed in the meanwhile
1895  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Checking common predecessor");
1896  for(const auto& predecessor : curr_block->list_of_pred)
1897  {
1898  if(std::find(pred_succ_block.begin(), pred_succ_block.end(), predecessor) != pred_succ_block.end())
1899  {
1900  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Found common predecessor BB" + STR(predecessor));
1901  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Skipped merging phi of BB" + STR(bb_index));
1902  return;
1903  }
1904  }
1905 
1906  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Checked common predecessors");
1907  bb_modified = true;
1909  for(const auto& phi : succ_block->CGetPhiList())
1910  {
1911  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Fixing " + phi->ToString());
1912  auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
1913  gimple_phi::DefEdgeList new_list_of_def_edge;
1914  for(auto def_edge : gp->CGetDefEdgesList())
1915  {
1916  if(def_edge.second == bb_index)
1917  {
1918  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1919  "---Found " + def_edge.first->ToString() + " coming from BB" + STR(def_edge.second));
1920  const auto def_to_be_removed = GET_CONST_NODE(def_edge.first);
1921  if(def_to_be_removed->get_kind() == ssa_name_K)
1922  {
1923  const auto def_stmt = GetPointerS<const ssa_name>(def_to_be_removed)->CGetDefStmt();
1924  const auto phi_to_be_removed = GetPointer<const gimple_phi>(GET_CONST_NODE(def_stmt));
1925  if(phi_to_be_removed && phi_to_be_removed->bb_index == bb_index)
1926  {
1927  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1928  "---" + def_edge.first->ToString() + " comes from a phi to be removed");
1930  if(GetPointerS<const ssa_name>(def_to_be_removed)->CGetNumberUses() == 1)
1931  {
1932  curr_block->RemovePhi(def_stmt);
1933  }
1934  for(const auto& curr_def_edge : phi_to_be_removed->CGetDefEdgesList())
1935  {
1936  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1937  "---Adding from phi of predecessor <" + curr_def_edge.first->ToString() + ", BB" +
1938  STR(curr_def_edge.second) + ">");
1939  new_list_of_def_edge.push_back(curr_def_edge);
1940  }
1941  }
1942  else
1943  {
1944  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1945  "---" + def_edge.first->ToString() + " is defined in a " +
1946  GET_CONST_NODE(def_stmt)->get_kind_text() + " in BB" +
1947  STR(GetPointer<const gimple_node>(GET_CONST_NODE(def_stmt))->bb_index));
1948  for(auto predecessor : curr_block->list_of_pred)
1949  {
1950  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1951  "---Adding from predecessor <" + def_edge.first->ToString() + ", BB" +
1952  STR(predecessor) + ">");
1953  new_list_of_def_edge.push_back(decltype(def_edge)(def_edge.first, predecessor));
1954  }
1955  }
1956  }
1957  else
1958  {
1959  for(auto predecessor : curr_block->list_of_pred)
1960  {
1961  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1962  "---Adding from predecessor <" + def_edge.first->ToString() + ", BB" +
1963  STR(predecessor) + ">");
1964  new_list_of_def_edge.push_back(decltype(def_edge)(def_edge.first, predecessor));
1965  }
1966  }
1967  }
1968  else
1969  {
1970  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1971  "---Readding <" + def_edge.first->ToString() + ", BB" + STR(def_edge.second) + ">");
1972  new_list_of_def_edge.push_back(def_edge);
1973  }
1974  }
1975  gp->SetDefEdgeList(TM, new_list_of_def_edge);
1976  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Fixed phi is " + gp->ToString());
1977  }
1978 
1980  const auto curr_phis = curr_block->CGetPhiList();
1981  for(const auto& phi : curr_phis)
1982  {
1983  const auto gp = GetPointerS<gimple_phi>(GET_NODE(phi));
1984  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Adding " + gp->ToString());
1985  for(auto predecessor : succ_block->list_of_pred)
1986  {
1987  if(predecessor != bb_index)
1988  {
1989  gp->AddDefEdge(TM, gimple_phi::DefEdge(gp->res, predecessor));
1990  }
1991  }
1992  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Added modified " + gp->ToString());
1993  gp->bb_index = succ_block->number;
1994  curr_block->RemovePhi(phi);
1995  succ_block->AddPhi(phi);
1996  }
1997 
1999  for(auto predecessor : curr_block->list_of_pred)
2000  {
2001  const auto& pred_block = sl->list_of_bloc.at(predecessor);
2002  pred_block->list_of_succ.erase(
2003  std::find(pred_block->list_of_succ.begin(), pred_block->list_of_succ.end(), bb_index));
2004  pred_block->list_of_succ.push_back(succ_block->number);
2005  if(pred_block->true_edge == bb_index)
2006  {
2007  pred_block->true_edge = succ_block->number;
2008  }
2009  if(pred_block->false_edge == bb_index)
2010  {
2011  pred_block->false_edge = succ_block->number;
2012  }
2014  if(pred_block->CGetStmtList().size())
2015  {
2016  const auto& last_stmt = pred_block->CGetStmtList().back();
2017  if(GET_NODE(last_stmt)->get_kind() == gimple_multi_way_if_K)
2018  {
2019  const auto gmw = GetPointerS<gimple_multi_way_if>(GET_NODE(last_stmt));
2020  for(auto& cond : gmw->list_of_cond)
2021  {
2022  if(cond.second == bb_index)
2023  {
2024  cond.second = succ_block->number;
2025  }
2026  }
2027  }
2028  }
2029  }
2030 
2032  succ_block->list_of_pred.erase(
2033  std::find(succ_block->list_of_pred.begin(), succ_block->list_of_pred.end(), bb_index));
2034  std::copy(curr_block->list_of_pred.begin(), curr_block->list_of_pred.end(),
2035  std::back_inserter(succ_block->list_of_pred));
2036 
2038  sl->list_of_bloc.erase(bb_index);
2039  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Merged phi of BB" + STR(bb_index));
2040 }
2041 
2042 void PhiOpt::RemoveCondExpr(const tree_nodeRef statement)
2043 {
2044  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Removing " + statement->ToString());
2045  THROW_ASSERT(GET_CONST_NODE(statement)->get_kind() == gimple_assign_K, "");
2046  const auto ga = GetPointerS<const gimple_assign>(GET_CONST_NODE(statement));
2047  const auto sn = GetPointer<const ssa_name>(GET_CONST_NODE(ga->op0));
2048  THROW_ASSERT(sn, "cond expression defines " + GET_CONST_NODE(ga->op0)->ToString());
2049  THROW_ASSERT(GET_CONST_NODE(ga->op1)->get_kind() == cond_expr_K, "");
2050  const auto new_sn = GetPointerS<const cond_expr>(GET_CONST_NODE(ga->op1))->op1;
2051  const auto uses = sn->CGetUseStmts();
2052  for(const auto& use : uses)
2053  {
2054  TM->ReplaceTreeNode(use.first, ga->op0, new_sn);
2055  }
2056  THROW_ASSERT(sl->list_of_bloc.count(ga->bb_index), "");
2057  sl->list_of_bloc.at(ga->bb_index)->RemoveStmt(statement, AppM);
2058  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Removed " + statement->ToString());
2059 }
2060 
2061 void PhiOpt::ReplaceVirtualUses(const tree_nodeRef& old_vssa, const TreeNodeSet& new_vssa) const
2062 {
2063  const auto virtual_ssa = GetPointerS<ssa_name>(GET_NODE(old_vssa));
2064  while(virtual_ssa->CGetUseStmts().size())
2065  {
2066  const auto use_stmt = virtual_ssa->CGetUseStmts().begin()->first;
2067  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, " use stmt " + GET_NODE(use_stmt)->ToString());
2068  const auto gn = GetPointerS<gimple_node>(GET_NODE(use_stmt));
2069  const auto has_vuses = gn->vuses.find(old_vssa) != gn->vuses.end();
2070  const auto has_vovers = gn->vovers.find(old_vssa) != gn->vovers.end();
2071  THROW_ASSERT(has_vuses || has_vovers,
2072  old_vssa->ToString() + " is not in the vuses/vovers of " + use_stmt->ToString());
2073 
2074  if(has_vuses)
2075  {
2076  gn->vuses.erase(old_vssa);
2077  }
2078  if(has_vovers)
2079  {
2080  gn->vovers.erase(old_vssa);
2081  }
2082  for(auto uses = virtual_ssa->CGetUseStmts().begin()->second; uses > 0; --uses)
2083  {
2084  virtual_ssa->RemoveUse(use_stmt);
2085  }
2086  for(const auto& vssa : new_vssa)
2087  {
2088  if(has_vuses)
2089  {
2090  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---add vuse " + GET_CONST_NODE(vssa)->ToString());
2091  if(gn->AddVuse(vssa))
2092  {
2093  GetPointerS<ssa_name>(GET_NODE(vssa))->AddUseStmt(use_stmt);
2094  }
2095  }
2096  if(has_vovers)
2097  {
2098  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---add vover " + GET_CONST_NODE(vssa)->ToString());
2099  if(gn->AddVover(vssa))
2100  {
2101  GetPointerS<ssa_name>(GET_NODE(vssa))->AddUseStmt(use_stmt);
2102  }
2103  }
2104  }
2105  }
2106 }
GET_NODE
#define GET_NODE(t)
Macro used to hide implementation details when accessing a tree_node from another tree_node...
Definition: tree_node.hpp:343
PhiOpt::ChainOptimization
void ChainOptimization(const unsigned int bb_index)
Remove chains of basic blocks.
Definition: phi_opt.cpp:1832
tree_manipulation::CreateOrExpr
tree_nodeRef CreateOrExpr(const tree_nodeConstRef &first_condition, const tree_nodeConstRef &second_condition, const blocRef &block, unsigned int function_decl_nid) const
Create an or expression.
Definition: tree_manipulation.cpp:2336
PhiOpt::ReplaceVirtualUses
void ReplaceVirtualUses(const tree_nodeRef &old_vssa, const TreeNodeSet &new_ssa) const
Definition: phi_opt.cpp:2061
test_panda.restart
restart
Definition: test_panda.py:538
DEBUG_LEVEL_VERY_PEDANTIC
#define DEBUG_LEVEL_VERY_PEDANTIC
extremely verbose debugging print is performed.
Definition: dbgPrintHelper.hpp:86
tree_manipulation::ExtractCondition
tree_nodeRef ExtractCondition(const tree_nodeRef &condition, const blocRef &block, unsigned int function_decl_nid) const
Extract computation of condition from a gimple_cond.
Definition: tree_manipulation.cpp:2460
hls_manager.hpp
Data structure representing the entire HLS information.
bloc
This struct specifies the field bloc (basic block).
Definition: tree_basic_block.hpp:84
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
dbgPrintHelper.hpp
File containing functions and utilities to support the printing of debug messagges.
tree_node::ToString
std::string ToString() const
Print this node as string in gimple format.
DEBUG_LEVEL_PEDANTIC
#define DEBUG_LEVEL_PEDANTIC
very verbose debugging print is performed.
Definition: dbgPrintHelper.hpp:84
behavioral_helper.hpp
DesignFlowStep_Status::UNCHANGED
Step successfully executed.
PhiOpt::TM
tree_managerRef TM
The tree manager.
Definition: phi_opt.hpp:93
GET_CLASS
#define GET_CLASS(obj)
Macro returning the actual type of an object.
Definition: string_manipulation.hpp:178
tree_manager::ReplaceTreeNode
void ReplaceTreeNode(const tree_nodeRef &stmt, const tree_nodeRef &old_node, const tree_nodeRef &new_node)
Replace the occurrences of tree node old_node with new_node in statement identified by tn...
Definition: tree_manager.cpp:953
PhiOpt::ApplyMultiMerge
void ApplyMultiMerge(const unsigned int bb_index)
Transform the control flow graph by merging a gimple_phi dominated by a gimple_multi_way_if.
Definition: phi_opt.cpp:1064
application_manager.hpp
Definition of the class representing a generic C application.
DesignFlowStep::output_level
const int output_level
The output level.
Definition: design_flow_step.hpp:129
PhiOpt::~PhiOpt
~PhiOpt() override
Destructor.
FunctionFrontendFlowStep::GetName
std::string GetName() const override
Return the name of this design step.
Definition: function_frontend_flow_step.cpp:104
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
INDENT_OUT_MEX
#define INDENT_OUT_MEX(outLevel, curOutLevel, mex)
Definition: dbgPrintHelper.hpp:170
gimple_phi::DefEdgeList
std::list< DefEdge > DefEdgeList
The type of the def edge list.
Definition: tree_node.hpp:3753
PhiOpt::tree_man
tree_manipulationConstRef tree_man
The tree manipulation.
Definition: phi_opt.hpp:96
token_interface.hpp
A simple interface to token object of the raw files.
phi_opt.hpp
Analysis step that optimize the phis starting from the IR.
statement_list::list_of_bloc
std::map< unsigned int, blocRef > list_of_bloc
list_of_bloc field is the list of basic block. If this field is null then the list_of_stmt field is n...
Definition: tree_node.hpp:4673
bloc::EXIT_BLOCK_ID
static const unsigned int EXIT_BLOCK_ID
constant identifying the exit basic block
Definition: tree_basic_block.hpp:253
DesignFlowStep_Status::SUCCESS
Step skipped.
PhiOpt::bb_modified
bool bb_modified
flag used to restart code motion step
Definition: phi_opt.hpp:105
tree_basic_block.hpp
Data structure describing a basic block at tree level.
TreeVocabularyTokenTypes_TokenEnum::TOK_SRCP
OUTPUT_LEVEL_MINIMUM
#define OUTPUT_LEVEL_MINIMUM
minimum debugging print is performed.
Definition: dbgPrintHelper.hpp:62
TOK
#define TOK(token)
Macro used to convert a token symbol into a treeVocabularyTokenTypes.
Definition: token_interface.hpp:765
tree_manager::CGetTreeNode
const tree_nodeConstRef CGetTreeNode(const unsigned int i) const
Definition: tree_manager.cpp:162
PhiOpt_PatternType::MULTI_MERGE
Phi dominated by gimple_multi_way_if to be merged.
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.
PhiOpt::ApplyMultiRemove
void ApplyMultiRemove(const unsigned int bb_index)
Transform the control flow graph by removing a gimple_phi dominated by a gimple_multi_way_if.
Definition: phi_opt.cpp:1319
ToString
std::string ToString(ActorGraphBackend_Type actor_graph_backend_type)
Header include.
Definition: actor_graph_backend.cpp:52
PhiOpt::MergePhi
void MergePhi(const unsigned int bb_index)
Remove a basic block composed only of phis my merging with the successor.
Definition: phi_opt.cpp:1886
phi
Definition: cdfc_module_binding.hpp:367
THROW_UNREACHABLE
#define THROW_UNREACHABLE(str_expr)
helper function used to specify that some points should never be reached
Definition: exceptions.hpp:292
PhiOpt::IdentifyPattern
PhiOpt_PatternType IdentifyPattern(const unsigned int bb_index) const
Identify to which pattern an empty basic block belongs.
Definition: phi_opt.cpp:1521
PhiOpt::SinglePhiOptimization
void SinglePhiOptimization(const unsigned int bb_index)
Transform single input phi in assignment.
Definition: phi_opt.cpp:1788
schedule.hpp
Data structure used to store the schedule of the operations.
Schedule::CanBeMoved
FunctionFrontendFlowStep_Movable CanBeMoved(const unsigned int statement_index, const unsigned int basic_block) const
Check if a statement can be moved at the end of a basic block.
Definition: schedule.cpp:601
tree_manager::new_tree_node_id
unsigned int new_tree_node_id(const unsigned int ask=0)
Return a new node id in the intermediate representation.
Definition: tree_manager.cpp:323
PhiOpt::ComputeFrontendRelationships
const CustomUnorderedSet< std::pair< FrontendFlowStepType, FunctionRelationship > > ComputeFrontendRelationships(const DesignFlowStep::RelationshipType relationship_type) const override
Return the set of analyses in relationship with this design step.
Definition: phi_opt.cpp:83
HLSFlowStep_Type
HLSFlowStep_Type
Definition: hls_step.hpp:95
hls_step.hpp
PhiOpt::ApplyIfMerge
void ApplyIfMerge(const unsigned int bb_index)
Transform the control flow graph by merging a gimple_phi dominated by a gimple_cond.
Definition: phi_opt.cpp:710
FunctionFrontendFlowStep::WriteBBGraphDot
void WriteBBGraphDot(const std::string &filename) const
Write the current version of statement list in dot format.
Definition: function_frontend_flow_step.cpp:296
PhiOpt_PatternType::IF_REMOVE
Phi dominated by gimple_cond to be removed.
tree_node::index
const unsigned int index
Represent the index read from the raw file and the index-1 of the vector of tree_node associated to t...
Definition: tree_node.hpp:146
tree_manager::create_tree_node
void create_tree_node(const unsigned int node_id, enum kind tree_node_type, std::map< TreeVocabularyTokenTypes_TokenEnum, std::string > &tree_node_schema)
Factory method.
Definition: tree_manager.cpp:314
gimple_phi::DefEdge
std::pair< tree_nodeRef, unsigned int > DefEdge
The type of the def edge.
Definition: tree_node.hpp:3750
tree_manager::GetTreeReindex
tree_nodeRef GetTreeReindex(const unsigned int i)
Return a tree_reindex wrapping the i-th tree_node.
Definition: tree_manager.cpp:129
GET_CONST_NODE
#define GET_CONST_NODE(t)
Definition: tree_node.hpp:347
PhiOpt::PhiOpt
PhiOpt(const application_managerRef AppM, unsigned int function_id, const DesignFlowManagerConstRef design_flow_manager, const ParameterConstRef parameters)
Constructor.
Definition: phi_opt.cpp:73
tree_nodeConstRef
refcount< const tree_node > tree_nodeConstRef
Definition: tree_node.hpp:213
tree_node.hpp
Classes specification of the tree_node data structures.
PhiOpt_PatternType::DIFF_NOTHING
Empty basic block with multiple input.
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
allocation_information.hpp
This package is used by all HLS packages to manage resource constraints and characteristics.
tree_manipulation.hpp
Class defining some useful functions to create tree nodes and to manipulate the tree manager...
DEBUG_LEVEL_NONE
#define DEBUG_LEVEL_NONE
no debugging print is performed.
Definition: dbgPrintHelper.hpp:78
PhiOpt::ApplyGimpleNothing
void ApplyGimpleNothing(const unsigned int bb_index)
Remove an empty basic block dominated by gimple assign.
Definition: phi_opt.cpp:892
Schedule::EvaluateCondsMerging
bool EvaluateCondsMerging(const unsigned statement_index, const unsigned int first_condition, const unsigned second_condition, unsigned int function_decl_nid) const
Check if a further condition can be added to gimple multi way if without increasing basic block laten...
Definition: schedule.cpp:787
hls_constraints.hpp
Data structure definition for HLS constraints.
block
This struct specifies the block node.
Definition: tree_node.hpp:1820
tree_helper.hpp
This file collects some utility functions.
PhiOpt::Initialize
void Initialize() override
Initialize the step (i.e., like a constructor, but executed just before exec.
Definition: phi_opt.cpp:113
tree_manager::GetTreeNode
tree_nodeRef GetTreeNode(const unsigned int index) const
Return the index-th tree_node (modifiable version)
Definition: tree_manager.cpp:147
PhiOpt_PatternType::MULTI_NOTHING
Basic block dominated by multi way if can be removed without further changes.
PhiOpt::ApplyIfNothing
void ApplyIfNothing(const unsigned int bb_index)
Transform the control flow graph by eliminating an empty basic block dominated by gimple_cond without...
Definition: phi_opt.cpp:846
PhiOpt_PatternType
PhiOpt_PatternType
Identifier of patterns to be transformed by phi_opt.
Definition: phi_opt.hpp:70
BUILTIN_SRCP
#define BUILTIN_SRCP
Definition: tree_manager.hpp:79
tree_manipulation::create_ternary_operation
tree_nodeRef create_ternary_operation(const tree_nodeConstRef &type, const tree_nodeRef &op0, const tree_nodeRef &op1, const tree_nodeRef &op2, const std::string &srcp, enum kind operation_kind) const
Function used to create a ternary expression.
Definition: tree_manipulation.cpp:363
FunctionFrontendFlowStep::function_id
const unsigned int function_id
The index of the function to be analyzed.
Definition: function_frontend_flow_step.hpp:80
PhiOpt::InternalExec
DesignFlowStep_Status InternalExec() override
Updates the tree to have a more compliant CFG.
Definition: phi_opt.cpp:130
PhiOpt_PatternType::IF_NOTHING
Basic block dominated by if can be removed without further changes.
FrontendFlowStep::AppM
const application_managerRef AppM
The application manager.
Definition: frontend_flow_step.hpp:218
type_node
struct definition of the type node structures.
Definition: tree_node.hpp:1318
tree_reindex.hpp
Class specification of the tree_reindex support class.
bloc::ENTRY_BLOCK_ID
static const unsigned int ENTRY_BLOCK_ID
constant identifying the entry basic block
Definition: tree_basic_block.hpp:250
PhiOpt_PatternType::GIMPLE_NOTHING
Empty basic block dominated by assign can be removed without further changes.
TreeVocabularyTokenTypes_TokenEnum::TOK_SCPE
gimple_node
struct definition of the common part of a gimple with virtual operands
Definition: tree_node.hpp:1078
refcount
Template borrowed from the ANTLR library by Terence Parr (http://www.jGuru.com - Software rights: htt...
Definition: refcount.hpp:94
tree_helper::CGetType
static tree_nodeConstRef CGetType(const tree_nodeConstRef &node)
Return the treenode of the type of node.
Definition: tree_helper.cpp:2167
tree_manipulationConstRef
refcount< const tree_manipulation > tree_manipulationConstRef
Definition: tree_manipulation.hpp:758
ext_tree_node.hpp
Classes specification of the tree_node data structures not present in the gcc.
Parameter.hpp
this class is used to manage the command-line or XML options.
PhiOpt::ApplyDiffNothing
void ApplyDiffNothing(const unsigned int bb_index)
Remove an empty basic block with multiple input edges.
Definition: phi_opt.cpp:611
tree_manipulation::create_ssa_name
tree_nodeRef create_ssa_name(const tree_nodeConstRef &var, const tree_nodeConstRef &type, const tree_nodeConstRef &min, const tree_nodeConstRef &max, bool volatile_flag=false, bool virtual_flag=false) const
MISCELLANEOUS_OBJ_TREE_NODES.
Definition: tree_manipulation.cpp:1608
tree_nodeRef
refcount< tree_node > tree_nodeRef
RefCount type definition of the tree_node class structure.
Definition: tree_node.hpp:212
PhiOpt_PatternType::MULTI_REMOVE
Phi dominated by gimple_multi_way_if to be removed.
PhiOpt::sl
statement_list * sl
The basic block graph of the function.
Definition: phi_opt.hpp:99
tree_helper::is_a_vector
static bool is_a_vector(const tree_managerConstRef &TM, const unsigned int index)
Return true if the treenode index is a vector.
Definition: tree_helper.cpp:2524
PhiOpt::RemoveCondExpr
void RemoveCondExpr(const tree_nodeRef statement)
Remove a redundant cond expr.
Definition: phi_opt.cpp:2042
PhiOpt::schedule
ScheduleRef schedule
The scheduling solution.
Definition: phi_opt.hpp:108
PhiOpt_PatternType::UNCHANGED
Transformation blocked by timing.
PhiOpt::ApplyMultiNothing
void ApplyMultiNothing(const unsigned int bb_index)
Transform the control flow graph by eliminating an empty basic block dominated by gimple_multi_way_if...
Definition: phi_opt.cpp:1273
DesignFlowStep::debug_level
int debug_level
The debug level.
Definition: design_flow_step.hpp:126
FunctionFrontendFlowStep_Movable::MOVABLE
Operation can be moved.
PhiOpt_PatternType::IF_MERGE
Edges coming from if to be merged.
GET_INDEX_CONST_NODE
#define GET_INDEX_CONST_NODE(t)
Definition: tree_node.hpp:363
hls.hpp
Data structure definition for high-level synthesis flow.
tree_manipulation::create_gimple_modify_stmt
tree_nodeRef create_gimple_modify_stmt(const tree_nodeRef &op0, const tree_nodeRef &op1, unsigned int function_decl_nid, const std::string &srcp) const
GIMPLE_ASSIGN.
Definition: tree_manipulation.cpp:1684
tree_manipulation
This class creates a layer to add nodes and to manipulate the tree_nodes manager. ...
Definition: tree_manipulation.hpp:115
PhiOpt_PatternType::UNKNOWN
Unknown pattern.
tree_manager.hpp
Class specification of the manager of the tree structures extracted from the raw file.
function_behavior.hpp
A brief description of the C++ Header File.
FunctionFrontendFlowStep::function_behavior
const FunctionBehaviorRef function_behavior
The function behavior of the function to be analyzed.
Definition: function_frontend_flow_step.hpp:77
HLSFlowStep_Relationship::SAME_FUNCTION
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
PhiOpt::ApplyIfRemove
void ApplyIfRemove(const unsigned int bb_index)
Transform the control flow graph by removing a gimple_phi dominated by a gimple_cond.
Definition: phi_opt.cpp:926
Generated on Mon Feb 12 2024 13:02:52 for PandA-2024.02 by doxygen 1.8.13