PandA-2024.02
Bit_Value.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  */
54 #include "Bit_Value.hpp"
56 
58 #include "Dominance.hpp"
59 #include "Parameter.hpp"
60 #include "basic_block.hpp"
61 
63 #include "application_manager.hpp"
64 #include "call_graph.hpp"
65 #include "call_graph_manager.hpp"
66 #include "function_behavior.hpp"
67 #include "op_graph.hpp"
68 
70 #include "design_flow_manager.hpp"
71 
73 #include "Range.hpp"
74 #include "application_frontend_flow_step.hpp"
75 
77 #include "hls_device.hpp"
78 #include "hls_manager.hpp"
79 
81 #include "memory.hpp"
82 
84 #include <cmath>
85 #include <fstream>
86 #include <string>
87 
89 #include <deque>
90 #include <tuple>
91 #include <utility>
92 #include <vector>
93 
94 #include "custom_map.hpp"
95 #include "custom_set.hpp"
96 
98 #include "behavioral_helper.hpp"
99 #include "tree_basic_block.hpp"
100 #include "tree_helper.hpp"
101 #include "tree_manager.hpp"
102 #include "tree_reindex.hpp"
103 
105 #include "compiler_wrapper.hpp"
106 #include "string_manipulation.hpp" // for GET_CLASS
107 
108 const std::map<bit_lattice, std::map<bit_lattice, std::map<bit_lattice, std::deque<bit_lattice>>>>
109  Bit_Value::plus_expr_map = {
110  // a b carry
111  {
112  bit_lattice::X,
113  {
114  {
115  bit_lattice::X,
116  {
117  {
118  bit_lattice::ZERO,
119  {bit_lattice::ZERO, bit_lattice::X},
120  },
121  {
122  bit_lattice::ONE,
123  {bit_lattice::ZERO, bit_lattice::X},
124  },
125  {
126  bit_lattice::U,
127  {bit_lattice::ZERO, bit_lattice::X},
128  },
129  },
130  },
131  {
132  bit_lattice::ZERO,
133  {
134  {
135  bit_lattice::ZERO,
136  {bit_lattice::ZERO, bit_lattice::ZERO},
137  },
138  {
139  bit_lattice::ONE,
140  {bit_lattice::ZERO, bit_lattice::ONE},
141  },
142  {
143  bit_lattice::U,
144  {bit_lattice::ZERO, bit_lattice::U},
145  },
146  },
147  },
148  {
149  bit_lattice::ONE,
150  {
151  {
152  bit_lattice::ZERO,
153  {bit_lattice::ZERO, bit_lattice::ONE},
154  },
155  {
156  bit_lattice::ONE,
157  {bit_lattice::ONE, bit_lattice::ZERO},
158  },
159  {
160  bit_lattice::U,
161  {bit_lattice::U, bit_lattice::U},
162  },
163  },
164  },
165  {
166  bit_lattice::U,
167  {
168  {
169  bit_lattice::ZERO,
170  {bit_lattice::ZERO, bit_lattice::U},
171  },
172  {
173  bit_lattice::ONE,
174  {bit_lattice::U, bit_lattice::U},
175  },
176  {
177  bit_lattice::U,
178  {bit_lattice::U, bit_lattice::U},
179  },
180  },
181  },
182  },
183  },
184  {
185  bit_lattice::ZERO,
186  {
187  {
188  bit_lattice::X,
189  {
190  {
191  bit_lattice::ZERO,
192  {bit_lattice::ZERO, bit_lattice::ZERO},
193  },
194  {
195  bit_lattice::ONE,
196  {bit_lattice::ZERO, bit_lattice::ONE},
197  },
198  {
199  bit_lattice::U,
200  {bit_lattice::ZERO, bit_lattice::U},
201  },
202  },
203  },
204  {
205  bit_lattice::ZERO,
206  {
207  {
208  bit_lattice::ZERO,
209  {bit_lattice::ZERO, bit_lattice::ZERO},
210  },
211  {
212  bit_lattice::ONE,
213  {bit_lattice::ZERO, bit_lattice::ONE},
214  },
215  {
216  bit_lattice::U,
217  {bit_lattice::ZERO, bit_lattice::U},
218  },
219  },
220  },
221  {
222  bit_lattice::ONE,
223  {
224  {
225  bit_lattice::ZERO,
226  {bit_lattice::ZERO, bit_lattice::ONE},
227  },
228  {
229  bit_lattice::ONE,
230  {bit_lattice::ONE, bit_lattice::ZERO},
231  },
232  {
233  bit_lattice::U,
234  {bit_lattice::U, bit_lattice::U},
235  },
236  },
237  },
238  {
239  bit_lattice::U,
240  {
241  {
242  bit_lattice::ZERO,
243  {bit_lattice::ZERO, bit_lattice::U},
244  },
245  {
246  bit_lattice::ONE,
247  {bit_lattice::U, bit_lattice::U},
248  },
249  {
250  bit_lattice::U,
251  {bit_lattice::U, bit_lattice::U},
252  },
253  },
254  },
255  },
256  },
257  {
258  bit_lattice::ONE,
259  {
260  {
261  bit_lattice::X,
262  {
263  {
264  bit_lattice::ZERO,
265  {bit_lattice::ZERO, bit_lattice::ONE},
266  },
267  {
268  bit_lattice::ONE,
269  {bit_lattice::ONE, bit_lattice::ZERO},
270  },
271  {
272  bit_lattice::U,
273  {bit_lattice::U, bit_lattice::U},
274  },
275  },
276  },
277  {
278  bit_lattice::ZERO,
279  {
280  {
281  bit_lattice::ZERO,
282  {bit_lattice::ZERO, bit_lattice::ONE},
283  },
284  {
285  bit_lattice::ONE,
286  {bit_lattice::ONE, bit_lattice::ZERO},
287  },
288  {
289  bit_lattice::U,
290  {bit_lattice::U, bit_lattice::U},
291  },
292  },
293  },
294  {
295  bit_lattice::ONE,
296  {
297  {
298  bit_lattice::ZERO,
299  {bit_lattice::ONE, bit_lattice::ZERO},
300  },
301  {
302  bit_lattice::ONE,
303  {bit_lattice::ONE, bit_lattice::ONE},
304  },
305  {
306  bit_lattice::U,
307  {bit_lattice::ONE, bit_lattice::U},
308  },
309  },
310  },
311  {
312  bit_lattice::U,
313  {
314  {
315  bit_lattice::ZERO,
316  {bit_lattice::U, bit_lattice::U},
317  },
318  {
319  bit_lattice::ONE,
320  {bit_lattice::ONE, bit_lattice::U},
321  },
322  {
323  bit_lattice::U,
324  {bit_lattice::U, bit_lattice::U},
325  },
326  },
327  },
328  },
329  },
330  {
331  bit_lattice::U,
332  {
333  {
334  bit_lattice::X,
335  {
336  {
337  bit_lattice::ZERO,
338  {bit_lattice::ZERO, bit_lattice::U},
339  },
340  {
341  bit_lattice::ONE,
342  {bit_lattice::U, bit_lattice::U},
343  },
344  {
345  bit_lattice::U,
346  {bit_lattice::U, bit_lattice::U},
347  },
348  },
349  },
350  {
351  bit_lattice::ZERO,
352  {
353  {
354  bit_lattice::ZERO,
355  {bit_lattice::ZERO, bit_lattice::U},
356  },
357  {
358  bit_lattice::ONE,
359  {bit_lattice::U, bit_lattice::U},
360  },
361  {
362  bit_lattice::U,
363  {bit_lattice::U, bit_lattice::U},
364  },
365  },
366  },
367  {
368  bit_lattice::ONE,
369  {
370  {
371  bit_lattice::ZERO,
372  {bit_lattice::U, bit_lattice::U},
373  },
374  {
375  bit_lattice::ONE,
376  {bit_lattice::ONE, bit_lattice::U},
377  },
378  {
379  bit_lattice::U,
380  {bit_lattice::U, bit_lattice::U},
381  },
382  },
383  },
384  {
385  bit_lattice::U,
386  {
387  {
388  bit_lattice::ZERO,
389  {bit_lattice::U, bit_lattice::U},
390  },
391  {
392  bit_lattice::ONE,
393  {bit_lattice::U, bit_lattice::U},
394  },
395  {
396  bit_lattice::U,
397  {bit_lattice::U, bit_lattice::U},
398  },
399  },
400  },
401  },
402  },
403 };
404 
405 const std::map<bit_lattice, std::map<bit_lattice, std::map<bit_lattice, std::deque<bit_lattice>>>>
406  Bit_Value::minus_expr_map = {
407  // a b borrow
408  {
409  bit_lattice::X,
410  {
411  {
412  bit_lattice::X,
413  {
414  {
415  bit_lattice::ZERO,
416  {bit_lattice::ZERO, bit_lattice::X},
417  },
418  {
419  bit_lattice::ONE,
420  {bit_lattice::ZERO, bit_lattice::X},
421  },
422  {
423  bit_lattice::U,
424  {bit_lattice::ZERO, bit_lattice::X},
425  },
426  },
427  },
428  {
429  bit_lattice::ZERO,
430  {
431  {
432  bit_lattice::ZERO,
433  {bit_lattice::ZERO, bit_lattice::ZERO},
434  },
435  {
436  bit_lattice::ONE,
437  {bit_lattice::ZERO, bit_lattice::ZERO},
438  },
439  {
440  bit_lattice::U,
441  {bit_lattice::ZERO, bit_lattice::ZERO},
442  },
443  },
444  },
445  {
446  bit_lattice::ONE,
447  {
448  {
449  bit_lattice::ZERO,
450  {bit_lattice::ZERO, bit_lattice::ZERO},
451  },
452  {
453  bit_lattice::ONE,
454  {bit_lattice::ONE, bit_lattice::ZERO},
455  },
456  {
457  bit_lattice::U,
458  {bit_lattice::U, bit_lattice::U},
459  },
460  },
461  },
462  {
463  bit_lattice::U,
464  {
465  {
466  bit_lattice::ZERO,
467  {bit_lattice::ZERO, bit_lattice::ZERO},
468  },
469  {
470  bit_lattice::ONE,
471  {bit_lattice::ZERO, bit_lattice::U},
472  },
473  {
474  bit_lattice::U,
475  {bit_lattice::U, bit_lattice::U},
476  },
477  },
478  },
479  },
480  },
481  {
482  bit_lattice::ZERO,
483  {
484  {
485  bit_lattice::X,
486  {
487  {
488  bit_lattice::ZERO,
489  {bit_lattice::ZERO, bit_lattice::ZERO},
490  },
491  {
492  bit_lattice::ONE,
493  {bit_lattice::ZERO, bit_lattice::ONE},
494  },
495  {
496  bit_lattice::U,
497  {bit_lattice::U, bit_lattice::U},
498  },
499  },
500  },
501  {
502  bit_lattice::ZERO,
503  {
504  {
505  bit_lattice::ZERO,
506  {bit_lattice::ZERO, bit_lattice::ZERO},
507  },
508  {
509  bit_lattice::ONE,
510  {bit_lattice::ONE, bit_lattice::ONE},
511  },
512  {
513  bit_lattice::U,
514  {bit_lattice::U, bit_lattice::U},
515  },
516  },
517  },
518  {
519  bit_lattice::ONE,
520  {
521  {
522  bit_lattice::ZERO,
523  {bit_lattice::ONE, bit_lattice::ONE},
524  },
525  {
526  bit_lattice::ONE,
527  {bit_lattice::ONE, bit_lattice::ZERO},
528  },
529  {
530  bit_lattice::U,
531  {bit_lattice::ONE, bit_lattice::U},
532  },
533  },
534  },
535  {
536  bit_lattice::U,
537  {
538  {
539  bit_lattice::ZERO,
540  {bit_lattice::U, bit_lattice::U},
541  },
542  {
543  bit_lattice::ONE,
544  {bit_lattice::ONE, bit_lattice::U},
545  },
546  {
547  bit_lattice::U,
548  {bit_lattice::U, bit_lattice::U},
549  },
550  },
551  },
552  },
553  },
554  {
555  bit_lattice::ONE,
556  {
557  {
558  bit_lattice::X,
559  {
560  {
561  bit_lattice::ZERO,
562  {bit_lattice::ZERO, bit_lattice::ZERO},
563  },
564  {
565  bit_lattice::ONE,
566  {bit_lattice::ZERO, bit_lattice::ZERO},
567  },
568  {
569  bit_lattice::U,
570  {bit_lattice::ZERO, bit_lattice::U},
571  },
572  },
573  },
574  {
575  bit_lattice::ZERO,
576  {
577  {
578  bit_lattice::ZERO,
579  {bit_lattice::ZERO, bit_lattice::ONE},
580  },
581  {
582  bit_lattice::ONE,
583  {bit_lattice::ZERO, bit_lattice::ZERO},
584  },
585  {
586  bit_lattice::U,
587  {bit_lattice::ZERO, bit_lattice::U},
588  },
589  },
590  },
591  {
592  bit_lattice::ONE,
593  {
594  {
595  bit_lattice::ZERO,
596  {bit_lattice::ZERO, bit_lattice::ZERO},
597  },
598  {
599  bit_lattice::ONE,
600  {bit_lattice::ONE, bit_lattice::ONE},
601  },
602  {
603  bit_lattice::U,
604  {bit_lattice::U, bit_lattice::U},
605  },
606  },
607  },
608  {
609  bit_lattice::U,
610  {
611  {
612  bit_lattice::ZERO,
613  {bit_lattice::ZERO, bit_lattice::U},
614  },
615  {
616  bit_lattice::ONE,
617  {bit_lattice::U, bit_lattice::U},
618  },
619  {
620  bit_lattice::U,
621  {bit_lattice::U, bit_lattice::U},
622  },
623  },
624  },
625  },
626  },
627  {
628  bit_lattice::U,
629  {
630  {
631  bit_lattice::X,
632  {
633  {
634  bit_lattice::ZERO,
635  {bit_lattice::ZERO, bit_lattice::U},
636  },
637  {
638  bit_lattice::ONE,
639  {bit_lattice::U, bit_lattice::U},
640  },
641  {
642  bit_lattice::U,
643  {bit_lattice::U, bit_lattice::U},
644  },
645  },
646  },
647  {
648  bit_lattice::ZERO,
649  {
650  {
651  bit_lattice::ZERO,
652  {bit_lattice::ZERO, bit_lattice::U},
653  },
654  {
655  bit_lattice::ONE,
656  {bit_lattice::U, bit_lattice::U},
657  },
658  {
659  bit_lattice::U,
660  {bit_lattice::U, bit_lattice::U},
661  },
662  },
663  },
664  {
665  bit_lattice::ONE,
666  {
667  {
668  bit_lattice::ZERO,
669  {bit_lattice::U, bit_lattice::U},
670  },
671  {
672  bit_lattice::ONE,
673  {bit_lattice::ONE, bit_lattice::U},
674  },
675  {
676  bit_lattice::U,
677  {bit_lattice::U, bit_lattice::U},
678  },
679  },
680  },
681  {
682  bit_lattice::U,
683  {
684  {
685  bit_lattice::ZERO,
686  {bit_lattice::U, bit_lattice::U},
687  },
688  {
689  bit_lattice::ONE,
690  {bit_lattice::U, bit_lattice::U},
691  },
692  {
693  bit_lattice::U,
694  {bit_lattice::U, bit_lattice::U},
695  },
696  },
697  },
698  },
699  },
700 };
701 
702 const std::map<bit_lattice, std::map<bit_lattice, bit_lattice>> Bit_Value::bit_ior_expr_map = {
703  {
704  bit_lattice::ZERO,
705  {
706  {bit_lattice::ZERO, bit_lattice::ZERO},
707  {bit_lattice::ONE, bit_lattice::ONE},
708  {bit_lattice::U, bit_lattice::U},
709  {bit_lattice::X, bit_lattice::X},
710  },
711  },
712  {
713  bit_lattice::ONE,
714  {
715  {bit_lattice::ZERO, bit_lattice::ONE},
716  {bit_lattice::ONE, bit_lattice::ONE},
717  {bit_lattice::U, bit_lattice::ONE},
718  {bit_lattice::X, bit_lattice::ONE},
719  },
720  },
721  {
722  bit_lattice::U,
723  {
724  {bit_lattice::ZERO, bit_lattice::U},
725  {bit_lattice::ONE, bit_lattice::ONE},
726  {bit_lattice::U, bit_lattice::U},
727  {bit_lattice::X, bit_lattice::X},
728  },
729  },
730  {
731  bit_lattice::X,
732  {
733  {bit_lattice::ZERO, bit_lattice::X},
734  {bit_lattice::ONE, bit_lattice::ONE},
735  {bit_lattice::U, bit_lattice::X},
736  {bit_lattice::X, bit_lattice::X},
737  },
738  },
739 };
740 
741 const std::map<bit_lattice, std::map<bit_lattice, bit_lattice>> Bit_Value::bit_xor_expr_map = {
742  {
743  bit_lattice::ZERO,
744  {
745  {bit_lattice::ZERO, bit_lattice::ZERO},
746  {bit_lattice::ONE, bit_lattice::ONE},
747  {bit_lattice::U, bit_lattice::U},
748  {bit_lattice::X, bit_lattice::X},
749  },
750  },
751  {
752  bit_lattice::ONE,
753  {
754  {bit_lattice::ZERO, bit_lattice::ONE},
755  {bit_lattice::ONE, bit_lattice::ZERO},
756  {bit_lattice::U, bit_lattice::U},
757  {bit_lattice::X, bit_lattice::X},
758  },
759  },
760  {
761  bit_lattice::U,
762  {
763  {bit_lattice::ZERO, bit_lattice::U},
764  {bit_lattice::ONE, bit_lattice::U},
765  {bit_lattice::U, bit_lattice::U},
766  {bit_lattice::X, bit_lattice::X},
767  },
768  },
769  {
770  bit_lattice::X,
771  {
772  {bit_lattice::ZERO, bit_lattice::X},
773  {bit_lattice::ONE, bit_lattice::X},
774  {bit_lattice::U, bit_lattice::X},
775  {bit_lattice::X, bit_lattice::X},
776  },
777  },
778 };
779 
780 const std::map<bit_lattice, std::map<bit_lattice, bit_lattice>> Bit_Value::bit_and_expr_map = {
781  {
782  bit_lattice::ZERO,
783  {
784  {bit_lattice::ZERO, bit_lattice::ZERO},
785  {bit_lattice::ONE, bit_lattice::ZERO},
786  {bit_lattice::U, bit_lattice::ZERO},
787  {bit_lattice::X, bit_lattice::ZERO},
788  },
789  },
790  {
791  bit_lattice::ONE,
792  {
793  {bit_lattice::ZERO, bit_lattice::ZERO},
794  {bit_lattice::ONE, bit_lattice::ONE},
795  {bit_lattice::U, bit_lattice::U},
796  {bit_lattice::X, bit_lattice::X},
797  },
798  },
799  {
800  bit_lattice::U,
801  {
802  {bit_lattice::ZERO, bit_lattice::ZERO},
803  {bit_lattice::ONE, bit_lattice::U},
804  {bit_lattice::U, bit_lattice::U},
805  {bit_lattice::X, bit_lattice::X},
806  },
807  },
808  {
809  bit_lattice::X,
810  {
811  {bit_lattice::ZERO, bit_lattice::ZERO},
812  {bit_lattice::ONE, bit_lattice::X},
813  {bit_lattice::U, bit_lattice::X},
814  {bit_lattice::X, bit_lattice::X},
815  },
816  },
817 };
818 
819 unsigned long long Bit_Value::pointer_resizing(unsigned int output_id) const
820 {
821  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
822  "-->Pointer resizing starting from " + TM->CGetTreeNode(output_id)->ToString());
823  unsigned int var = tree_helper::get_base_index(TM, output_id);
824  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Base variable is " + TM->CGetTreeNode(var)->ToString());
825  unsigned long long address_bitsize;
826  if(not_frontend)
827  {
828  auto* hm = GetPointer<HLS_manager>(AppM);
829  if(hm and hm->Rmem)
830  {
831  if(var and function_behavior->is_variable_mem(var))
832  {
833  unsigned long long int max_addr =
834  hm->Rmem->get_base_address(var, function_id) + BitLatticeManipulator::size(TM, var) / 8;
835  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Maximum address is " + STR(max_addr - 1));
836  for(address_bitsize = 1; max_addr > (1ull << address_bitsize); ++address_bitsize)
837  {
838  ;
839  }
841  if(address_bitsize < 4)
842  {
843  address_bitsize = 4;
844  }
846  auto vd = GetPointer<const var_decl>(TM->CGetTreeNode(var));
847  if(hm->Rmem->get_base_address(var, function_id) == 0 && vd)
848  {
849  auto align = vd->algn;
850  align = align < 8 ? 1 : (align / 8);
851  auto index = 0u;
852  bool found = false;
853  for(; index < address_bitsize; ++index)
854  {
855  if((1ULL << index) & align)
856  {
857  found = true;
858  break;
859  }
860  }
861  if(!found)
862  {
863  ++address_bitsize;
864  }
865  }
866  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Memory variable " + STR(address_bitsize));
867  }
868  else
869  {
870  address_bitsize = hm->get_address_bitsize();
871  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Address bus bitsize " + STR(address_bitsize));
872  }
873  }
874  else
875  {
876  address_bitsize = AppM->get_address_bitsize();
877  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Address bitsize " + STR(address_bitsize));
878  }
879  }
880  else
881  {
882  address_bitsize = static_cast<unsigned int>(CompilerWrapper::CGetPointerSize(parameters));
883  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Pointer bitsize " + STR(address_bitsize));
884  }
885  return address_bitsize;
886 }
887 
888 unsigned int Bit_Value::lsb_to_zero(const addr_expr* ae, bool safe) const
889 {
890  const auto vd = GetPointer<const var_decl>(GET_CONST_NODE(ae->op));
891  if(!vd)
892  {
893  return 0;
894  }
895  auto align = vd->algn;
896  if(safe)
897  {
898  align = 1;
899  }
900  else
901  {
902  align = align < 64 ? 8 : (align / 8);
903  }
904  auto index = 0u;
905  bool found = false;
906  for(; index < AppM->get_address_bitsize(); ++index)
907  {
908  if((1ULL << index) & align)
909  {
910  found = true;
911  break;
912  }
913  }
914  return found ? index : 0;
915 }
916 
917 Bit_Value::Bit_Value(const ParameterConstRef params, const application_managerRef AM, unsigned int f_id,
918  const DesignFlowManagerConstRef dfm)
919  : FunctionFrontendFlowStep(AM, f_id, BIT_VALUE, dfm, params),
920  BitLatticeManipulator(AM->get_tree_manager(), parameters->get_class_debug_level(GET_CLASS(*this))),
921  not_frontend(false)
922 {
923  debug_level = parameters->get_class_debug_level(GET_CLASS(*this), DEBUG_LEVEL_NONE);
924 }
925 
926 Bit_Value::~Bit_Value() = default;
927 
928 const CustomUnorderedSet<std::pair<FrontendFlowStepType, FrontendFlowStep::FunctionRelationship>>
929 Bit_Value::ComputeFrontendRelationships(const DesignFlowStep::RelationshipType relationship_type) const
930 {
931  CustomUnorderedSet<std::pair<FrontendFlowStepType, FunctionRelationship>> relationships;
932  switch(relationship_type)
933  {
934  case DEPENDENCE_RELATIONSHIP:
935  {
936  relationships.insert(std::make_pair(BIT_VALUE, CALLED_FUNCTIONS));
937  relationships.insert(std::make_pair(CALL_GRAPH_BUILTIN_CALL, SAME_FUNCTION));
938  relationships.insert(std::make_pair(COMPUTE_IMPLICIT_CALLS, SAME_FUNCTION));
939  relationships.insert(std::make_pair(DETERMINE_MEMORY_ACCESSES, SAME_FUNCTION));
940  relationships.insert(std::make_pair(ESSA, SAME_FUNCTION));
941  relationships.insert(std::make_pair(EXTRACT_GIMPLE_COND_OP, SAME_FUNCTION));
942  relationships.insert(std::make_pair(FIX_STRUCTS_PASSED_BY_VALUE, SAME_FUNCTION));
943  relationships.insert(std::make_pair(FUNCTION_CALL_TYPE_CLEANUP, SAME_FUNCTION));
944  relationships.insert(std::make_pair(IR_LOWERING, SAME_FUNCTION));
945  relationships.insert(std::make_pair(PARM2SSA, SAME_FUNCTION));
946  if(parameters->isOption(OPT_soft_float) && parameters->getOption<bool>(OPT_soft_float))
947  {
948  relationships.insert(std::make_pair(SOFT_FLOAT_CG_EXT, SAME_FUNCTION));
949  }
950  relationships.insert(std::make_pair(UN_COMPARISON_LOWERING, SAME_FUNCTION));
951  relationships.insert(std::make_pair(USE_COUNTING, SAME_FUNCTION));
952  break;
953  }
954  case(PRECEDENCE_RELATIONSHIP):
955  {
956  break;
957  }
958  case(INVALIDATION_RELATIONSHIP):
959  {
960  break;
961  }
962  default:
963  THROW_UNREACHABLE("");
964  }
965  return relationships;
966 }
967 
968 bool Bit_Value::HasToBeExecuted() const
969 {
970  return (bitvalue_version != function_behavior->GetBitValueVersion()) or FunctionFrontendFlowStep::HasToBeExecuted();
971 }
972 
973 void Bit_Value::Initialize()
974 {
975  const auto bambu_frontend_flow_signature =
976  ApplicationFrontendFlowStep::ComputeSignature(FrontendFlowStepType::BAMBU_FRONTEND_FLOW);
977  not_frontend = design_flow_manager.lock()->GetStatus(bambu_frontend_flow_signature) == DesignFlowStep_Status::EMPTY;
978 
979  const auto tn = TM->CGetTreeNode(function_id);
980  THROW_ASSERT(tn->get_kind() == function_decl_K, "Node is not a function");
981  const auto fd = GetPointerS<const function_decl>(tn);
982  THROW_ASSERT(fd->body, "Function has not a body");
983  const auto sl = GetPointerS<const statement_list>(GET_CONST_NODE(fd->body));
985  BBGraphsCollectionRef bb_graphs_collection(
986  new BBGraphsCollection(BBGraphInfoRef(new BBGraphInfo(AppM, function_id)), parameters));
987  BBGraph cfg(bb_graphs_collection, CFG_SELECTOR);
988  CustomUnorderedMap<unsigned int, vertex> inverse_vertex_map;
990  for(const auto& block : sl->list_of_bloc)
991  {
992  inverse_vertex_map.insert(
993  std::make_pair(block.first, bb_graphs_collection->AddVertex(BBNodeInfoRef(new BBNodeInfo(block.second)))));
994  }
995 
997  for(const auto& curr_bb_pair : sl->list_of_bloc)
998  {
999  const auto curr_bbi = curr_bb_pair.first;
1000  const auto curr_bb = curr_bb_pair.second;
1001  for(const auto& lop : curr_bb->list_of_pred)
1002  {
1003  THROW_ASSERT(static_cast<bool>(inverse_vertex_map.count(lop)),
1004  "BB" + STR(lop) + " (successor of BB" + STR(curr_bbi) + ") does not exist");
1005  bb_graphs_collection->AddEdge(inverse_vertex_map.at(lop), inverse_vertex_map.at(curr_bbi), CFG_SELECTOR);
1006  }
1007 
1008  for(const auto& los : curr_bb->list_of_succ)
1009  {
1010  if(los == bloc::EXIT_BLOCK_ID)
1011  {
1012  bb_graphs_collection->AddEdge(inverse_vertex_map.at(curr_bbi), inverse_vertex_map.at(los), CFG_SELECTOR);
1013  }
1014  }
1015 
1016  if(curr_bb->list_of_succ.empty())
1017  {
1018  bb_graphs_collection->AddEdge(inverse_vertex_map.at(curr_bbi), inverse_vertex_map.at(bloc::EXIT_BLOCK_ID),
1019  CFG_SELECTOR);
1020  }
1021  }
1023  bb_graphs_collection->AddEdge(inverse_vertex_map.at(bloc::ENTRY_BLOCK_ID),
1024  inverse_vertex_map.at(bloc::EXIT_BLOCK_ID), CFG_SELECTOR);
1025  dominance<BBGraph> bb_dominators(cfg, inverse_vertex_map.at(bloc::ENTRY_BLOCK_ID),
1026  inverse_vertex_map.at(bloc::EXIT_BLOCK_ID), parameters);
1027  bb_dominators.calculate_dominance_info(dominance<BBGraph>::CDI_DOMINATORS);
1028 
1029  BBGraphRef dt(new BBGraph(bb_graphs_collection, D_SELECTOR));
1030  for(const auto& it : bb_dominators.get_dominator_map())
1031  {
1032  if(it.first != inverse_vertex_map.at(bloc::ENTRY_BLOCK_ID))
1033  {
1034  bb_graphs_collection->AddEdge(it.second, it.first, D_SELECTOR);
1035  }
1036  }
1037  dt->GetBBGraphInfo()->bb_index_map = std::move(inverse_vertex_map);
1038 
1039  std::list<vertex> v_topological;
1040  dt->TopologicalSort(v_topological);
1041  THROW_ASSERT(v_topological.size(), "");
1042  bb_topological.reserve(v_topological.size());
1043  std::transform(v_topological.begin(), v_topological.end(), std::back_inserter(bb_topological),
1044  [&](const vertex& v) { return dt->CGetBBNodeInfo(v)->block; });
1045 }
1046 
1047 DesignFlowStep_Status Bit_Value::InternalExec()
1048 {
1049  if(parameters->IsParameter("bitvalue") && !parameters->GetParameter<unsigned int>("bitvalue"))
1050  {
1051  return DesignFlowStep_Status::UNCHANGED;
1052  }
1053  initialize();
1054  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Performing initial backward");
1055  backward();
1056  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Performed initial backward");
1057  mix();
1058  PRINT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "best at the end of initial backward:");
1059  print_bitstring_map(best);
1060  PRINT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "");
1061  bool restart;
1062  do
1063  {
1064  clear_current();
1065  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Performing forward");
1066  forward();
1067  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Performed forward");
1068  mix();
1069  PRINT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "best at the end of forward:");
1070  print_bitstring_map(best);
1071  PRINT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "");
1072  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Performing backward");
1073  backward();
1074  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Performed backward");
1075  restart = mix();
1076  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "best at end of backward:");
1077  print_bitstring_map(best);
1078  PRINT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "");
1079  } while(restart);
1080  bb_topological.clear();
1081  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "best at the end of alg:");
1082  print_bitstring_map(best);
1083  auto changed = update_IR();
1084  BitLatticeManipulator::clear();
1085  direct_call_id_to_called_id.clear();
1086  arguments.clear();
1087  if(changed)
1088  {
1089  function_behavior->UpdateBitValueVersion();
1090  }
1091  return changed ? DesignFlowStep_Status::SUCCESS : DesignFlowStep_Status::UNCHANGED;
1092 }
1093 
1094 // prints the content of a bitstring map
1095 void Bit_Value::print_bitstring_map(const CustomMap<unsigned int, std::deque<bit_lattice>>&
1096 #ifndef NDEBUG
1097  map
1098 #endif
1099 ) const
1100 {
1101 #ifndef NDEBUG
1102  const auto BH = function_behavior->CGetBehavioralHelper();
1103  for(const auto& m : map)
1104  {
1105  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1106  "var_uid: " + STR(m.first) + ":" + BH->PrintVariable(m.first) +
1107  " bitstring: " + bitstring_to_string(m.second));
1108  }
1109 #endif
1110 }
1111 
1112 bool Bit_Value::update_IR()
1113 {
1114  bool res = false;
1115  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "-->Updating IR");
1116  for(const auto& b : best)
1117  {
1118  const auto tn_id = b.first;
1119  const auto tn = TM->GetTreeNode(tn_id);
1120  const auto kind = tn->get_kind();
1121  if(kind == ssa_name_K)
1122  {
1123  auto ssa = GetPointerS<ssa_name>(tn);
1124  if(ssa->bit_values.empty() || BitLatticeManipulator::isBetter(bitstring_to_string(b.second), ssa->bit_values))
1125  {
1126  if(!AppM->ApplyNewTransformation())
1127  {
1128  break;
1129  }
1130  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1131  "Variable: " + ssa->ToString() + " bitstring: " + ssa->bit_values + " -> " +
1132  bitstring_to_string(b.second));
1133  ssa->bit_values = bitstring_to_string(b.second);
1134  // ssa->range = Range::fromBitValues(b.second, static_cast<Range::bw_t>(BitLatticeManipulator::Size(tn)),
1135  // signed_var.count(ssa->index));
1136  res = true;
1137  AppM->RegisterTransformation(GetName(), tn);
1138  }
1139  }
1140  else if(kind == function_decl_K)
1141  {
1142  auto fd = GetPointerS<function_decl>(tn);
1143  if(fd->bit_values.empty() || BitLatticeManipulator::isBetter(bitstring_to_string(b.second), fd->bit_values))
1144  {
1145  if(!AppM->ApplyNewTransformation())
1146  {
1147  break;
1148  }
1149  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1150  "Function: " + tree_helper::name_function(TM, b.first) + " bitstring: " + fd->bit_values +
1151  " -> " + bitstring_to_string(b.second));
1152  fd->bit_values = bitstring_to_string(b.second);
1153  res = true;
1154  AppM->RegisterTransformation(GetName(), tn);
1155  }
1156  }
1157  else if(kind == integer_cst_K || kind == real_cst_K)
1158  {
1159  // do nothing, constants are recomputed every time
1160  }
1161  else
1162  {
1163  THROW_ERROR("unexpected condition: variable of kind " + tn->get_kind_text());
1164  }
1165  }
1166  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "<--Updated IR");
1167 
1168  return res;
1169 }
1170 
1171 void Bit_Value::initialize()
1172 {
1173  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Internal initialize");
1174  BitLatticeManipulator::clear();
1175  direct_call_id_to_called_id.clear();
1176  arguments.clear();
1177 
1178  const auto CGMan = AppM->CGetCallGraphManager();
1179  const auto cg = CGMan->CGetCallGraph();
1180  const auto v = CGMan->GetVertex(function_id);
1181 
1182  const auto rbf = CGMan->GetReachedBodyFunctions();
1183  OutEdgeIterator oe_it, oe_end;
1184  boost::tie(oe_it, oe_end) = boost::out_edges(v, *cg);
1185  for(; oe_it != oe_end; oe_it++)
1186  {
1187  const auto call_edge_info = cg->CGetFunctionEdgeInfo(*oe_it);
1188  for(const auto& i : call_edge_info->direct_call_points)
1189  {
1190  const auto called_id = CGMan->get_function(boost::target(*oe_it, *cg));
1191  if(i == 0)
1192  {
1193  // never analyze artificial calls
1194  THROW_ASSERT(AppM->CGetFunctionBehavior(called_id)->CGetBehavioralHelper()->get_function_name() == MEMCPY,
1195  "function " + function_behavior->CGetBehavioralHelper()->get_function_name() +
1196  " calls function " +
1197  AppM->CGetFunctionBehavior(called_id)->CGetBehavioralHelper()->get_function_name() +
1198  " with an artificial call: this should not happen");
1199  continue;
1200  }
1201  if(rbf.find(called_id) != rbf.end())
1202  {
1203  direct_call_id_to_called_id[i] = called_id;
1204  }
1205  }
1206  }
1207 
1208  const auto tn = TM->CGetTreeNode(function_id);
1209  const auto fd = GetPointerS<const function_decl>(tn);
1210 
1211  /*
1212  * loop on the list of arguments and initialize best
1213  */
1214  for(const auto& parm_decl_node : fd->list_of_args)
1215  {
1216  const auto parmssa_id = AppM->getSSAFromParm(function_id, GET_INDEX_CONST_NODE(parm_decl_node));
1217  const auto parm_type = tree_helper::CGetType(parm_decl_node);
1218  if(!IsHandledByBitvalue(parm_type))
1219  {
1220  continue;
1221  }
1222  const auto parmssa = TM->CGetTreeNode(parmssa_id);
1223  const auto p = GetPointerS<const ssa_name>(parmssa);
1224  const auto b = p->CGetUseStmts().empty() ?
1225  create_x_bitstring(1) :
1226  (p->bit_values.empty() ? create_u_bitstring(BitLatticeManipulator::Size(parmssa)) :
1227  string_to_bitstring(p->bit_values));
1228  best[parmssa_id] = b;
1229  arguments.insert(parmssa_id);
1230  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1231  "Parameter " + STR(GET_CONST_NODE(parm_decl_node)) + "(" +
1232  STR(GET_INDEX_CONST_NODE(parm_decl_node)) + ") bound to " + parmssa->ToString() + ": " +
1233  bitstring_to_string(b) + "");
1234  }
1235 
1236  /*
1237  * initialize the bitvalue strings for the return value that have been set on
1238  * the function_decl from the BitValueIPA
1239  */
1240  const auto fu_type = tree_helper::CGetType(tn);
1241  const auto fret_type_node = tree_helper::GetFunctionReturnType(fu_type);
1242 
1243  if(!fret_type_node || !IsHandledByBitvalue(fret_type_node))
1244  {
1245  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1246  "Function returning " + (fret_type_node ? STR(fret_type_node) : "void") + " not considered");
1247  }
1248  else
1249  {
1250  const auto is_signed = tree_helper::IsSignedIntegerType(fret_type_node);
1251  if(fd->bit_values.empty())
1252  {
1253  best[function_id] = fd->range ? fd->range->getBitValues(is_signed) :
1254  create_u_bitstring(BitLatticeManipulator::Size(fret_type_node));
1255  }
1256  else
1257  {
1258  best[function_id] = string_to_bitstring(fd->bit_values);
1259  }
1260 
1261  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Return value: " + bitstring_to_string(best.at(function_id)));
1262  if(is_signed)
1263  {
1264  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---is signed");
1265  signed_var.insert(function_id);
1266  }
1267  }
1268 
1269  {
1270  /*
1271  * Compute initialization bitstrings for ssa loaded from ROMs. This
1272  * initialization has to be performed before the other ssa are initialized
1273  * because we must be sure that bitstrings computed in previous executions
1274  * of bitvalues analysis are not thrown away before computing inf() on
1275  * bitvalues used for ROMs. If this initialization is interleaved with the
1276  * initialization of bitvalues of other ssa we may lose some information,
1277  * because some of the old bitstrings attached to ssa are cleared during the
1278  * initialization. If this happens, optimizations on ROMs cannot be
1279  * aggressive enough, with worse cycles and DSP usage for CHStone benchmarks
1280  */
1281  CustomMap<unsigned int, std::deque<bit_lattice>> private_variables;
1282  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Initializing ROMs loaded ssa bitvalues");
1283  for(const auto& B : bb_topological)
1284  {
1285  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Analyzing BB" + STR(B->number));
1286  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "-->");
1287  for(const auto& stmt : B->CGetStmtList())
1288  {
1289  const auto stmt_node = GET_CONST_NODE(stmt);
1290  if(stmt_node->get_kind() == gimple_assign_K)
1291  {
1292  const auto ga = GetPointerS<const gimple_assign>(stmt_node);
1293  THROW_ASSERT(!ga->clobber, "");
1294  const auto lhs = GET_CONST_NODE(ga->op0);
1295  // handle lhs
1296  if(lhs->get_kind() == ssa_name_K)
1297  {
1298  const auto lhs_nid = GET_INDEX_CONST_NODE(ga->op0);
1299  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1300  "Analyzing " + stmt_node->get_kind_text() + "(" + STR(stmt_node->index) +
1301  "): " + STR(stmt_node));
1302  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---LHS: " + STR(lhs));
1303  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1304  "---RHS: " + GET_CONST_NODE(ga->op1)->get_kind_text());
1305 
1306  if(!IsHandledByBitvalue(lhs))
1307  {
1308  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1309  "---variable " + STR(GetPointerS<const ssa_name>(lhs)) + " of type " +
1310  STR(tree_helper::CGetType(lhs)) + " not considered");
1311  }
1312  else
1313  {
1314  const auto lhs_signed = tree_helper::IsSignedIntegerType(lhs);
1315  if(lhs_signed)
1316  {
1317  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---is signed");
1318  signed_var.insert(lhs_nid);
1319  }
1321  const auto ga_op1_kind = GET_CONST_NODE(ga->op1)->get_kind();
1322  if(ga_op1_kind == array_ref_K || ga_op1_kind == mem_ref_K || ga_op1_kind == target_mem_ref_K ||
1323  ga_op1_kind == target_mem_ref461_K || ga_op1_kind == var_decl_K)
1324  {
1325  const auto hm = GetPointer<const HLS_manager>(AppM);
1326  const auto base_index = tree_helper::get_base_index(TM, GET_INDEX_CONST_NODE(ga->op1));
1327  const auto var_node = TM->GetTreeNode(base_index);
1328  auto vd = GetPointer<var_decl>(var_node);
1329  if(base_index &&
1330  AppM->get_written_objects().find(base_index) == AppM->get_written_objects().end() && hm &&
1331  hm->Rmem && hm->Rmem->get_enable_hls_bit_value() &&
1332  function_behavior->is_variable_mem(base_index) && hm->Rmem->is_sds_var(base_index) && vd &&
1333  vd->init)
1334  {
1335  std::deque<bit_lattice> current_inf;
1336  if(GET_CONST_NODE(vd->init)->get_kind() == constructor_K)
1337  {
1338  current_inf = constructor_bitstring(GET_CONST_NODE(vd->init), lhs_nid);
1339  }
1340  else if(GET_CONST_NODE(vd->init)->get_kind() == integer_cst_K)
1341  {
1342  const auto cst_val = tree_helper::GetConstValue(vd->init);
1343  current_inf = create_bitstring_from_constant(
1344  cst_val, BitLatticeManipulator::Size(GET_CONST_NODE(vd->init)),
1345  tree_helper::IsSignedIntegerType(vd->init));
1346  }
1347  else if(GET_CONST_NODE(vd->init)->get_kind() == string_cst_K)
1348  {
1349  current_inf = string_cst_bitstring(GET_CONST_NODE(vd->init), lhs_nid);
1350  }
1351  else
1352  {
1353  current_inf = create_u_bitstring(BitLatticeManipulator::Size(lhs));
1354  }
1355 
1356  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1357  "---Used the init bitstring " + bitstring_to_string(current_inf));
1358 
1359  vd->bit_values = bitstring_to_string(current_inf);
1360  best[lhs_nid] = current_inf;
1361  }
1362  else
1363  {
1364  best[lhs_nid] = create_u_bitstring(BitLatticeManipulator::Size(lhs));
1365  }
1367  if(base_index &&
1368  AppM->get_written_objects().find(base_index) != AppM->get_written_objects().end() && hm &&
1369  hm->Rmem && hm->Rmem->get_enable_hls_bit_value() &&
1370  function_behavior->is_variable_mem(base_index) && hm->Rmem->is_private_memory(base_index) &&
1371  hm->Rmem->is_sds_var(base_index))
1372  {
1373  if(vd)
1374  {
1375  if(!private_variables.count(base_index))
1376  {
1377  std::deque<bit_lattice> current_inf;
1378  if(vd->init)
1379  {
1380  if(GET_CONST_NODE(vd->init)->get_kind() == constructor_K)
1381  {
1382  current_inf = constructor_bitstring(GET_CONST_NODE(vd->init), lhs_nid);
1383  }
1384  else if(GET_CONST_NODE(vd->init)->get_kind() == integer_cst_K)
1385  {
1386  const auto cst_val = tree_helper::GetConstValue(vd->init);
1387  current_inf = create_bitstring_from_constant(
1388  cst_val, BitLatticeManipulator::Size(GET_CONST_NODE(vd->init)),
1389  tree_helper::IsSignedIntegerType(vd->init));
1390  }
1391  else if(GET_CONST_NODE(vd->init)->get_kind() == string_cst_K)
1392  {
1393  current_inf = string_cst_bitstring(GET_CONST_NODE(vd->init), lhs_nid);
1394  }
1395  else
1396  {
1397  current_inf = create_u_bitstring(BitLatticeManipulator::Size(lhs));
1398  }
1399  }
1400  else
1401  {
1402  current_inf.push_back(bit_lattice::X);
1403  }
1404  INDENT_DBG_MEX(
1405  DEBUG_LEVEL_PEDANTIC, debug_level,
1406  "---Computed the init bitstring for " +
1407  function_behavior->CGetBehavioralHelper()->PrintVariable(base_index) + " = " +
1408  bitstring_to_string(current_inf));
1409  for(const auto& cur_var : hm->Rmem->get_source_values(base_index))
1410  {
1411  const auto cur_node = TM->CGetTreeNode(cur_var);
1412  const auto source_is_signed = tree_helper::IsSignedIntegerType(cur_node);
1413  const auto source_type = tree_helper::CGetType(cur_node);
1414  const auto source_type_size = BitLatticeManipulator::Size(source_type);
1415  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1416  "---source node: " + STR(cur_node) + " source is signed: " +
1417  STR(source_is_signed) + " loaded is signed: " + STR(lhs_signed));
1418  std::deque<bit_lattice> cur_bitstring;
1419  if(cur_node->get_kind() == ssa_name_K)
1420  {
1421  const auto ssa = GetPointerS<const ssa_name>(cur_node);
1422  if(!IsHandledByBitvalue(source_type))
1423  {
1424  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1425  "---Not handled by bitvalue");
1426  cur_bitstring = create_u_bitstring(BitLatticeManipulator::Size(cur_node));
1427  }
1428  else
1429  {
1430  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1431  "---Is handled by bitvalue");
1432  cur_bitstring = string_to_bitstring(ssa->bit_values);
1433  }
1434  }
1435  else if(cur_node->get_kind() == integer_cst_K)
1436  {
1437  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---Integer constant");
1438  const auto cst_val = tree_helper::GetConstValue(cur_node);
1439  cur_bitstring =
1440  create_bitstring_from_constant(cst_val, source_type_size, lhs_signed);
1441  }
1442  else
1443  {
1444  cur_bitstring = create_u_bitstring(BitLatticeManipulator::Size(cur_node));
1445  }
1446  if(cur_bitstring.size() != 0)
1447  {
1448  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1449  "---bitstring = " + bitstring_to_string(cur_bitstring));
1450  if(cur_bitstring.size() < source_type_size && source_is_signed != lhs_signed)
1451  {
1452  cur_bitstring =
1453  sign_extend_bitstring(cur_bitstring, source_is_signed, source_type_size);
1454  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1455  "---bitstring = " + bitstring_to_string(cur_bitstring));
1456  }
1457  sign_reduce_bitstring(cur_bitstring, lhs_signed);
1458  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1459  "---bitstring = " + bitstring_to_string(cur_bitstring));
1460  }
1461  else
1462  {
1463  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1464  "---bitstring empty --> using U");
1465  cur_bitstring = create_u_bitstring(BitLatticeManipulator::Size(cur_node));
1466  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1467  "---bitstring = " + bitstring_to_string(cur_bitstring));
1468  }
1469  current_inf = inf(current_inf, cur_bitstring, lhs);
1470  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1471  "---inf = " + bitstring_to_string(current_inf));
1472  }
1473  while(current_inf.front() == bit_lattice::X)
1474  {
1475  current_inf.pop_front();
1476  }
1477  if(current_inf.empty())
1478  {
1479  current_inf.push_back(bit_lattice::ZERO);
1480  }
1481  THROW_ASSERT(std::find(current_inf.begin(), current_inf.end(), bit_lattice::X) ==
1482  current_inf.end(),
1483  "Init bitstring must not contain X: " + bitstring_to_string(current_inf));
1484  vd->bit_values = bitstring_to_string(current_inf);
1485  INDENT_DBG_MEX(
1486  DEBUG_LEVEL_PEDANTIC, debug_level,
1487  "---Bit Value: variable " +
1488  function_behavior->CGetBehavioralHelper()->PrintVariable(base_index) +
1489  " trimmed to bitsize: " + STR(vd->bit_values.size()) +
1490  " with bit-value pattern: " + vd->bit_values);
1491  private_variables[base_index] = current_inf;
1492  }
1493  const auto var_inf = private_variables.at(base_index);
1494  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1495  "---Init bitstring for a private written memory variable " +
1496  bitstring_to_string(var_inf));
1497  best[lhs_nid] = var_inf;
1498  }
1499  }
1500  }
1501  }
1502  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1503  "Analyzed " + stmt_node->get_kind_text() + ": " + STR(stmt_node));
1504  }
1505  }
1506  else if(stmt_node->get_kind() == gimple_asm_K)
1507  {
1508  const auto ga = GetPointerS<const gimple_asm>(stmt_node);
1509  if(ga->out)
1510  {
1511  const auto tl = GetPointer<const tree_list>(GET_CONST_NODE(ga->out));
1512  THROW_ASSERT(tl->valu, "only the first output and so only single output gimple_asm are supported");
1513  const auto ssa = GetPointer<const ssa_name>(GET_CONST_NODE(tl->valu));
1514  if(ssa && !ssa->CGetUseStmts().empty() && IsHandledByBitvalue(tl->valu))
1515  {
1516  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1517  "Analyzing " + stmt_node->get_kind_text() + "(" + STR(stmt_node->index) + ")");
1518  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1519  "---Initializing bitstring for an asm instruction");
1520  best[GET_INDEX_CONST_NODE(tl->valu)] =
1521  create_u_bitstring(BitLatticeManipulator::Size(GET_CONST_NODE(tl->valu)));
1522  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Analyzed " + stmt_node->get_kind_text());
1523  }
1524  }
1525  }
1526  }
1527  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "<--");
1528  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Analyzed BB" + STR(B->number));
1529  }
1530  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Initialized ROMs loaded ssa bitvalues");
1531  }
1532 
1533  const auto set_value = [&](unsigned int node_id) {
1534  if(node_id == 0)
1535  {
1536  return;
1537  }
1538  auto use_node = TM->GetTreeNode(node_id);
1539  if(!IsHandledByBitvalue(use_node))
1540  {
1541  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1542  "---variable " + STR(use_node) + " of type " + STR(tree_helper::CGetType(use_node)) +
1543  " not considered");
1544  return;
1545  }
1546 
1547  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "-->Use: " + STR(use_node));
1548  if(use_node->get_kind() == ssa_name_K)
1549  {
1550  const auto ssa = GetPointerS<ssa_name>(use_node);
1551  const auto ssa_is_signed = tree_helper::IsSignedIntegerType(use_node);
1552  if(ssa_is_signed)
1553  {
1554  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---is signed");
1555  signed_var.insert(node_id);
1556  }
1557  if(ssa->volatile_flag)
1558  {
1559  ssa->bit_values.clear();
1560  best[node_id] = create_u_bitstring(BitLatticeManipulator::Size(use_node));
1561  }
1562  else
1563  {
1564  const auto def = ssa->CGetDefStmt();
1565  if(!def || (ssa->var != nullptr && ((GET_CONST_NODE(def)->get_kind() == gimple_nop_K)) &&
1566  GET_CONST_NODE(ssa->var)->get_kind() == var_decl_K))
1567  {
1568  ssa->bit_values.clear();
1569  best[node_id] = create_bitstring_from_constant(0, 1, ssa_is_signed);
1570  if(ssa->var)
1571  {
1572  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1573  "---first version of uninitialized var " + STR(GET_CONST_NODE(ssa->var)));
1574  }
1575  else
1576  {
1577  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---uninitialized ssa");
1578  }
1579  if(AppM->ApplyNewTransformation())
1580  {
1581  const auto tree_man = AppM->get_tree_manager();
1582  const auto ssa_node = tree_man->GetTreeReindex(node_id);
1583  const auto cst_value = tree_man->CreateUniqueIntegerCst(0, ssa->type);
1584  const auto uses = ssa->CGetUseStmts();
1585  for(const auto& stmt_use : uses)
1586  {
1587  tree_man->ReplaceTreeNode(stmt_use.first, ssa_node, cst_value);
1588  }
1589  AppM->RegisterTransformation(GetName(), ssa_node);
1590  use_node = GET_NODE(cst_value);
1591  node_id = GET_INDEX_NODE(cst_value);
1592  }
1593  }
1594  }
1595  }
1596 
1597  if(use_node->get_kind() == integer_cst_K)
1598  {
1599  const auto cst_val = tree_helper::GetConstValue(use_node);
1600  const auto is_signed = tree_helper::IsSignedIntegerType(use_node);
1601  best[node_id] = create_bitstring_from_constant(cst_val, BitLatticeManipulator::Size(use_node), is_signed);
1602  if(is_signed)
1603  {
1604  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---is signed");
1605  signed_var.insert(node_id);
1606  }
1607  sign_reduce_bitstring(best.at(node_id), is_signed);
1608  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1609  "---updated bitstring: " + bitstring_to_string(best.at(node_id)));
1610  }
1611  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "<--");
1612  };
1613 
1614  /*
1615  * now do the real initialization on all the basic blocks
1616  */
1617  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Initializing all ssa bitvalues");
1618  for(const auto& B : bb_topological)
1619  {
1620  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Analyzing BB" + STR(B->number));
1621  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "-->");
1622 
1623  for(const auto& phi : B->CGetPhiList())
1624  {
1625  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1626  "Analyzing phi(" + STR(GET_INDEX_CONST_NODE(phi)) + "): " + STR(phi));
1627  const auto pn = GetPointerS<const gimple_phi>(GET_CONST_NODE(phi));
1628  const auto is_virtual = pn->virtual_flag;
1629  if(!is_virtual)
1630  {
1631  const auto res_nid = GET_INDEX_CONST_NODE(pn->res);
1632  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---LHS: " + STR(res_nid));
1633  auto ssa = GetPointer<ssa_name>(GET_NODE(pn->res));
1634  THROW_ASSERT(ssa, "unexpected condition");
1635  if(!IsHandledByBitvalue(pn->res))
1636  {
1637  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1638  "---variable " + STR(ssa) + " of type " + STR(tree_helper::CGetType(pn->res)) +
1639  " not considered id: " + STR(res_nid));
1640  continue;
1641  }
1642  if(tree_helper::IsSignedIntegerType(pn->res))
1643  {
1644  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---is signed");
1645  signed_var.insert(res_nid);
1646  }
1647  if(bb_version == 0 || bb_version != function_behavior->GetBBVersion())
1648  {
1649  ssa->bit_values.clear();
1650  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---bit_values cleared : " + STR(ssa));
1651  }
1652 
1653  if(ssa->CGetUseStmts().empty())
1654  {
1655  best[res_nid] = create_x_bitstring(1);
1656  if(best.count(res_nid))
1657  {
1658  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1659  "---updated bitstring: " + bitstring_to_string(best.at(res_nid)));
1660  }
1661  }
1662  else
1663  {
1664  if(ssa->bit_values.empty())
1665  {
1666  best[res_nid] = create_u_bitstring(BitLatticeManipulator::Size(pn->res));
1667  }
1668  else
1669  {
1670  best[res_nid] = string_to_bitstring(ssa->bit_values);
1671  }
1672  if(best.count(res_nid))
1673  {
1674  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1675  "---updated bitstring: " + bitstring_to_string(best.at(res_nid)));
1676  }
1677 
1678  for(const auto& def_edge : pn->CGetDefEdgesList())
1679  {
1680  set_value(GET_INDEX_CONST_NODE(def_edge.first));
1681  }
1682  }
1683  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Analyzed phi: " + STR(phi));
1684  }
1685  }
1686 
1687  for(const auto& stmt : B->CGetStmtList())
1688  {
1689  // ga->op1 is equal to var_decl when it binds a newly declared variable to an ssa variable. ie. int a;
1690  // we can skip this assignment and focus on the ssa variable
1691  const auto stmt_node = GET_CONST_NODE(stmt);
1692  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1693  "Analyzing " + stmt_node->get_kind_text() + "(" + STR(GET_INDEX_CONST_NODE(stmt)) +
1694  "): " + STR(stmt_node));
1695  if(stmt_node->get_kind() == gimple_assign_K)
1696  {
1697  const auto ga = GetPointerS<const gimple_assign>(stmt_node);
1698  THROW_ASSERT(!ga->clobber, "");
1699 
1700  const auto lhs = GET_NODE(ga->op0);
1701  // handle lhs
1702  if(lhs->get_kind() == ssa_name_K)
1703  {
1704  auto lhs_ssa = GetPointerS<ssa_name>(lhs);
1705  const auto lhs_nid = GET_INDEX_CONST_NODE(ga->op0);
1706  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "-->LHS: " + STR(lhs_ssa));
1707  if(!IsHandledByBitvalue(lhs))
1708  {
1709  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1710  "---variable " + STR(lhs_ssa) + " of type " + STR(tree_helper::CGetType(lhs)) +
1711  " not considered");
1712  }
1713  else
1714  {
1715  if(bb_version == 0 || bb_version != function_behavior->GetBBVersion())
1716  {
1717  lhs_ssa->bit_values.clear();
1718  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---bit_values cleared : " + STR(lhs_ssa));
1719  }
1720  const auto lhs_signed = tree_helper::IsSignedIntegerType(lhs);
1721  if(lhs_signed)
1722  {
1723  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---is signed");
1724  signed_var.insert(lhs_nid);
1725  }
1726 
1727  const auto ga_op1_kind = GET_CONST_NODE(ga->op1)->get_kind();
1728  if(lhs_ssa->CGetUseStmts().empty())
1729  {
1730  best[lhs_nid] = create_x_bitstring(1);
1731  }
1733  else if(ga_op1_kind == array_ref_K || ga_op1_kind == mem_ref_K || ga_op1_kind == target_mem_ref_K ||
1734  ga_op1_kind == target_mem_ref461_K || ga_op1_kind == var_decl_K)
1735  {
1736  // this computation was moved above, to make sure that no
1737  // bitstrings (computed by previous execution of the same
1738  // bitvalue analysis step) are cleared from ssa variables
1739  // before computation of bitvalues for ssa read from ROMs
1740  THROW_ASSERT(best.find(lhs_nid) != best.end(), "");
1741  }
1742  /*if(tree_helper::is_a_pointer(TM, lhs_nid))
1743  {
1744  HLS_manager* hm = GetPointer<HLS_manager>(AppM);
1745  unsigned int var = tree_helper::get_base_index(TM, lhs_nid);
1746  if(var && hm && hm->Rmem && hm->Rmem->get_enable_hls_bit_value() &&
1747  function_behavior->is_variable_mem(var)) best[lhs_nid] = create_u_bitstring(pointer_resizing(AppM,
1748  lhs_nid, function_behavior, function_id, not_frontend, parameters)); else best[lhs_nid] =
1749  create_u_bitstring (BitLatticeManipulator::Size(GET_NODE(ga->op0)));
1750  }*/
1751  else if(ga_op1_kind == call_expr_K || ga_op1_kind == aggr_init_expr_K)
1752  {
1753  const auto ce = GetPointerS<const call_expr>(GET_CONST_NODE(ga->op1));
1754  if(GET_CONST_NODE(ce->fn)->get_kind() == addr_expr_K)
1755  {
1756  const auto addr_node = GET_CONST_NODE(ce->fn);
1757  const auto ae = GetPointerS<const addr_expr>(addr_node);
1758  const auto fu_decl_node = GET_CONST_NODE(ae->op);
1759  THROW_ASSERT(fu_decl_node->get_kind() == function_decl_K, "node " + STR(fu_decl_node) +
1760  " is not function_decl but " +
1761  fu_decl_node->get_kind_text());
1762  const auto ret_type_node = tree_helper::GetFunctionReturnType(fu_decl_node);
1763  if(IsHandledByBitvalue(ret_type_node))
1764  {
1765  const auto called_fd = GetPointer<const function_decl>(fu_decl_node);
1766  const auto new_bitvalue =
1767  called_fd->bit_values.empty() ?
1768  (called_fd->range ?
1769  called_fd->range->getBitValues(
1770  tree_helper::IsSignedIntegerType(ret_type_node)) :
1771  create_u_bitstring(BitLatticeManipulator::Size(GET_CONST_NODE(ga->op0)))) :
1772  string_to_bitstring(called_fd->bit_values);
1773  if(best[lhs_nid].empty())
1774  {
1775  best[lhs_nid] = new_bitvalue;
1776  }
1777  else
1778  {
1779  best[lhs_nid] = sup(new_bitvalue, best[lhs_nid], lhs);
1780  }
1781  }
1782  }
1783  else if(GET_CONST_NODE(ce->fn)->get_kind() != ssa_name_K)
1784  {
1785  THROW_UNREACHABLE("call node " + STR(GET_CONST_NODE(ce->fn)) + " is a " +
1786  GET_CONST_NODE(ce->fn)->get_kind_text());
1787  }
1788  }
1789  else if(ga_op1_kind == lut_expr_K)
1790  {
1791  best[lhs_nid] = create_u_bitstring(1);
1792  }
1793  else if(ga_op1_kind == extract_bit_expr_K)
1794  {
1795  best[lhs_nid] = create_u_bitstring(1);
1796  }
1797  else
1798  {
1799  if(lhs_ssa->bit_values.empty())
1800  {
1801  auto u_string = create_u_bitstring(BitLatticeManipulator::Size(lhs));
1802  if(lhs_signed && tree_helper::is_natural(TM, GET_INDEX_CONST_NODE(ga->op0)))
1803  {
1804  u_string.pop_front();
1805  u_string.push_front(bit_lattice::ZERO);
1806  }
1807  best[lhs_nid] = u_string;
1808  }
1809  else
1810  {
1811  best[lhs_nid] = string_to_bitstring(lhs_ssa->bit_values);
1812  }
1813  }
1814  THROW_ASSERT(best.count(lhs_nid), "");
1815  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1816  "---updated bitstring: " + bitstring_to_string(best.at(lhs_nid)));
1817  }
1818  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "RHS: " + GET_CONST_NODE(ga->op1)->get_kind_text());
1819  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "<--");
1820  }
1821  }
1822  else if(stmt_node->get_kind() == gimple_asm_K)
1823  {
1824  const auto ga = GetPointerS<const gimple_asm>(stmt_node);
1825  if(ga->out)
1826  {
1827  const auto tl = GetPointer<const tree_list>(GET_CONST_NODE(ga->out));
1828  THROW_ASSERT(tl->valu, "only the first output and so only single output gimple_asm are supported");
1829  const auto out_node = GET_CONST_NODE(tl->valu);
1830  auto out_ssa = GetPointer<ssa_name>(out_node);
1831  if(out_ssa && !out_ssa->CGetUseStmts().empty())
1832  {
1833  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "-->out: " + STR(out_ssa));
1834 
1835  if(!IsHandledByBitvalue(out_node))
1836  {
1837  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1838  "---variable of type " + STR(tree_helper::CGetType(out_node)) + " not considered");
1839  }
1840  else
1841  {
1842  out_ssa->bit_values.clear();
1843  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---bit_values cleared : " + STR(out_ssa));
1844  if(tree_helper::IsSignedIntegerType(out_node))
1845  {
1846  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "---is signed");
1847  signed_var.insert(out_node->index);
1848  }
1849  best[out_node->index] = create_u_bitstring(BitLatticeManipulator::Size(out_node));
1850  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1851  "---updated bitstring: " + bitstring_to_string(best.at(out_node->index)));
1852  }
1853  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "<--");
1854  }
1855  }
1856  }
1857  else
1858  {
1859  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1860  "---LHS unhandled for statement kind: " + STR(stmt_node->index));
1861  }
1862 
1863  std::vector<std::tuple<unsigned int, unsigned int>> vars_read;
1864  tree_helper::get_required_values(vars_read, stmt);
1865  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "-->Requires " + STR(vars_read.size()) + " values");
1866  for(const auto& var_pair : vars_read)
1867  {
1868  const auto ssa_use_node_id = std::get<0>(var_pair);
1869  set_value(ssa_use_node_id);
1870  }
1871  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "<--");
1872  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
1873  "Analyzed " + stmt_node->get_kind_text() + ": " + STR(stmt_node));
1874  }
1875  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "<--");
1876  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Analyzed BB" + STR(B->number));
1877  }
1878  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level, "Initialized best with all variables in the function:");
1879  print_bitstring_map(best);
1880  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Ended internal initialize");
1881 }
1882 
1883 void Bit_Value::clear_current()
1884 {
1885  for(const auto& b : best)
1886  {
1887  if(arguments.find(b.first) != arguments.end() || b.first == function_id)
1888  {
1889  current[b.first] = b.second;
1890  }
1891  else
1892  {
1893  const auto position_in_current = current.find(b.first);
1894  if(position_in_current != current.end())
1895  {
1896  current.erase(position_in_current);
1897  }
1898  }
1899  }
1900 }
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
BitLatticeManipulator::string_cst_bitstring
std::deque< bit_lattice > string_cst_bitstring(const tree_nodeRef &strcst_tn, unsigned int ssa_node_id) const
auxiliary function used to build the bitstring lattice for read-only string_cst
Definition: bit_lattice.cpp:487
CompilerWrapper::CGetPointerSize
static size_t CGetPointerSize(const ParameterConstRef parameters)
Return the size of the pointer in bit.
Definition: compiler_wrapper.cpp:2913
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
hls_manager.hpp
Data structure representing the entire HLS information.
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
create_bitstring_from_constant
std::deque< bit_lattice > create_bitstring_from_constant(integer_cst_t value, unsigned long long len, bool signed_value)
Creates a bitstring from a constant input.
Definition: bit_lattice.cpp:582
OutEdgeIterator
boost::graph_traits< graph >::out_edge_iterator OutEdgeIterator
out_edge_iterator definition.
Definition: graph.hpp:1312
tree_helper::name_function
static std::string name_function(const tree_managerConstRef &tm, const unsigned int index)
Return the name of the function.
Definition: tree_helper.cpp:417
Bit_Value::plus_expr_map
static const std::map< bit_lattice, std::map< bit_lattice, std::map< bit_lattice, std::deque< bit_lattice > > > > plus_expr_map
Map storing the implementation of the forward_transfer&#39;s plus_expr.
Definition: Bit_Value.hpp:86
MEMCPY
#define MEMCPY
constant string identifying the operation performed when two objects are memcopied.
Definition: op_graph.hpp:310
PRINT_DBG_MEX
#define PRINT_DBG_MEX(dbgLevel, curDbgLevel, mex)
We are producing a debug version of the program, so the message is printed;.
Definition: dbgPrintHelper.hpp:120
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.
create_x_bitstring
std::deque< bit_lattice > create_x_bitstring(size_t lenght)
Create a bitstring containing bits initialized at <X>
Definition: bit_lattice.cpp:577
BBNodeInfo
Definition of the node_info object for the basic_block graph.
Definition: basic_block.hpp:100
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
BBGraph::GetBBGraphInfo
BBGraphInfoRef GetBBGraphInfo()
Returns the property associated with the graph.
Definition: basic_block.hpp:408
Bit_Value::not_frontend
bool not_frontend
True if this step is not executed in the frontend.
Definition: Bit_Value.hpp:110
application_manager.hpp
Definition of the class representing a generic C application.
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
BitLatticeManipulator::isBetter
static bool isBetter(const std::string &a_string, const std::string &b_string)
Definition: bit_lattice.cpp:842
align
static unsigned long long int align(unsigned long long int address, unsigned long long int alignment)
STL includes.
Definition: memory.cpp:81
tree_helper::is_natural
static bool is_natural(const tree_managerConstRef &TM, const unsigned int index)
Return true if the treenode is a ssa_name greater or equal to zero.
Definition: tree_helper.cpp:2658
CustomMap
CustomOrderedMap< T, U > CustomMap
Definition: custom_map.hpp:167
Bit_Value::InternalExec
DesignFlowStep_Status InternalExec() override
perform the bit value analysis
Definition: Bit_Value.cpp:1047
D_SELECTOR
#define D_SELECTOR
Selectors used only in basic block graphs; numbers continue from cdfg_edge_info.hpp.
Definition: basic_block.hpp:85
Bit_Value.hpp
Full implementation of Bit Value analysis as described in BitValue Inference: Detecting and Exploitin...
BitLatticeManipulator::IsHandledByBitvalue
bool IsHandledByBitvalue(const tree_nodeConstRef &tn) const
Returns true if the type identified by type_id is handled by bitvalue analysis.
Definition: bit_lattice.cpp:503
bloc::EXIT_BLOCK_ID
static const unsigned int EXIT_BLOCK_ID
constant identifying the exit basic block
Definition: tree_basic_block.hpp:253
Bit_Value::backward
void backward()
Applies the backward algorithm, as described in the paper, analyzing each assignment statement starti...
Definition: Bit_Value_backward.cpp:192
DesignFlowStep_Status::SUCCESS
Step skipped.
GET_INDEX_NODE
#define GET_INDEX_NODE(t)
Macro used to hide implementation details when accessing a tree_node from another tree_node...
Definition: tree_node.hpp:361
tree_basic_block.hpp
Data structure describing a basic block at tree level.
FunctionFrontendFlowStep::bb_version
unsigned int bb_version
The version of the basic block intermediate representation on which this step has been applied...
Definition: function_frontend_flow_step.hpp:83
DesignFlowStep_Status::EMPTY
Step aborts.
custom_map.hpp
redefinition of map to manage ordered/unordered structures
bit_lattice::ZERO
tree_helper::get_required_values
static void get_required_values(std::vector< std::tuple< unsigned int, unsigned int >> &required, const tree_nodeRef &tn)
Definition: tree_helper.cpp:8272
Bit_Value::print_bitstring_map
void print_bitstring_map(const CustomMap< unsigned int, std::deque< bit_lattice >> &map) const
Debugging function used to print the contents of the current and best maps.
Definition: Bit_Value.cpp:1095
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.
FunctionFrontendFlowStep::HasToBeExecuted
bool HasToBeExecuted() const override
Check if this step has actually to be executed.
Definition: function_frontend_flow_step.cpp:291
BitLatticeManipulator::sign_reduce_bitstring
static void sign_reduce_bitstring(std::deque< bit_lattice > &bitstring, bool bitstring_is_signed)
Reduce the size of a bitstring erasing all but one most significant zeros in unsigned bitstring and a...
Definition: bit_lattice.cpp:372
Bit_Value::minus_expr_map
static const std::map< bit_lattice, std::map< bit_lattice, std::map< bit_lattice, std::deque< bit_lattice > > > > minus_expr_map
Map storing the implementation of the forward_transfer&#39;s minus_expr.
Definition: Bit_Value.hpp:92
Bit_Value::forward
void forward()
Applies the forward algorithm, as described in the paper, analyzing each assignment statement followi...
Definition: Bit_Value_forward.cpp:81
tree_helper::IsSignedIntegerType
static bool IsSignedIntegerType(const tree_nodeConstRef &type)
Return true if the treenode is of integer type.
Definition: tree_helper.cpp:2683
BitLatticeManipulator::signed_var
CustomSet< unsigned int > signed_var
Set storing the signed ssa.
Definition: bit_lattice.hpp:90
bitstring_to_string
std::string bitstring_to_string(const std::deque< bit_lattice > &bitstring)
Translates a bitstring ( expressed as an std::deque of bit_lattice ) into a string of characters...
Definition: bit_lattice.cpp:602
phi
Definition: cdfc_module_binding.hpp:367
Bit_Value::~Bit_Value
~Bit_Value() override
Destructor.
THROW_UNREACHABLE
#define THROW_UNREACHABLE(str_expr)
helper function used to specify that some points should never be reached
Definition: exceptions.hpp:292
BBGraph
Class used to describe a particular graph with basic blocks as nodes.
Definition: basic_block.hpp:324
BitLatticeManipulator::inf
std::deque< bit_lattice > inf(const std::deque< bit_lattice > &a, const std::deque< bit_lattice > &b, const unsigned int output_uid) const
Computes the inf between two bitstrings.
Definition: bit_lattice.cpp:333
Bit_Value::pointer_resizing
unsigned long long pointer_resizing(unsigned int output_id) const
Definition: Bit_Value.cpp:819
map
unsigned map[NUM_VERTICES]
Definition: bfs.c:12
CustomUnorderedMap
absl::flat_hash_map< T, U, Hash, Eq, Alloc > CustomUnorderedMap
Definition: custom_map.hpp:148
create_u_bitstring
std::deque< bit_lattice > create_u_bitstring(size_t lenght)
Creates a bitstring containing bits initialized at <U>
Definition: bit_lattice.cpp:572
Bit_Value::lsb_to_zero
unsigned int lsb_to_zero(const addr_expr *ae, bool safe) const
Definition: Bit_Value.cpp:888
BitLatticeManipulator::current
CustomMap< unsigned int, std::deque< bit_lattice > > current
Map of the current bit-values of each variable.
Definition: bit_lattice.hpp:78
Bit_Value::Initialize
void Initialize() override
Initialize the step (i.e., like a constructor, but executed just before exec.
Definition: Bit_Value.cpp:973
Bit_Value::bit_and_expr_map
static const std::map< bit_lattice, std::map< bit_lattice, bit_lattice > > bit_and_expr_map
Map storing the implementation of the forward_transfer&#39;s bit_and_expr_map.
Definition: Bit_Value.hpp:107
BBGraphInfo
Information associated with the whole basic-block graph.
Definition: basic_block.hpp:247
Bit_Value::bit_ior_expr_map
static const std::map< bit_lattice, std::map< bit_lattice, bit_lattice > > bit_ior_expr_map
Map storing the implementation of the forward_transfer&#39;s bit_ior_expr_map.
Definition: Bit_Value.hpp:97
index
#define index(x, y)
Definition: Keccak.c:74
kind
kind
Definition: tree_common.hpp:138
custom_set.hpp
redefinition of set to manage ordered/unordered structures
BitLatticeManipulator::size
static unsigned long long size(const tree_managerConstRef tm, unsigned int index)
Definition: bit_lattice.cpp:670
ApplicationFrontendFlowStep::ComputeSignature
static const std::string ComputeSignature(const FrontendFlowStepType frontend_flow_step_type)
Compute the signature of a function frontend flow step.
Definition: application_frontend_flow_step.cpp:67
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
GET_CONST_NODE
#define GET_CONST_NODE(t)
Definition: tree_node.hpp:347
BitLatticeManipulator::Size
static unsigned long long Size(const tree_nodeConstRef &t)
Definition: bit_lattice.cpp:675
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
bit_lattice::X
Bit_Value::update_IR
bool update_IR()
Updates the bitvalues of the intermediate representation with the values taken from the input map...
Definition: Bit_Value.cpp:1112
dominance::calculate_dominance_info
void calculate_dominance_info(enum dominance::cdi_direction dir)
The main entry point into this module.
Definition: Dominance.hpp:701
call_graph.hpp
Call graph hierarchy.
DEBUG_LEVEL_NONE
#define DEBUG_LEVEL_NONE
no debugging print is performed.
Definition: dbgPrintHelper.hpp:78
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
BitLatticeManipulator::TM
const tree_managerConstRef TM
Definition: bit_lattice.hpp:71
Bit_Value::HasToBeExecuted
bool HasToBeExecuted() const override
Check if this step has actually to be executed.
Definition: Bit_Value.cpp:968
block
This struct specifies the block node.
Definition: tree_node.hpp:1820
tree_helper.hpp
This file collects some utility functions.
HLSFlowStep_Relationship::CALLED_FUNCTIONS
BitLatticeManipulator::mix
bool mix()
Mixes the content of current and best using the sup operation, storing the result in the best map...
Definition: bit_lattice.cpp:510
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
string_to_bitstring
std::deque< bit_lattice > string_to_bitstring(const std::string &s)
inverse of bitstring_to_string
Definition: bit_lattice.cpp:629
Bit_Value::direct_call_id_to_called_id
CustomUnorderedMapUnstable< unsigned int, unsigned int > direct_call_id_to_called_id
Maps the id of a gimple statement to the id of the function called in that statement.
Definition: Bit_Value.hpp:122
Bit_Value::initialize
void initialize()
Initializes best with C type as bitstring, signed_var and arguments using the information taken from ...
Definition: Bit_Value.cpp:1171
BitLatticeManipulator::sup
std::deque< bit_lattice > sup(const std::deque< bit_lattice > &a, const std::deque< bit_lattice > &b, const unsigned int output_uid) const
Computes the sup between two bitstrings.
Definition: bit_lattice.cpp:218
Wrefcount::lock
refcount< T > lock() const
Definition: refcount.hpp:212
FunctionFrontendFlowStep::function_id
const unsigned int function_id
The index of the function to be analyzed.
Definition: function_frontend_flow_step.hpp:80
FrontendFlowStep::AppM
const application_managerRef AppM
The application manager.
Definition: frontend_flow_step.hpp:218
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
Bit_Value::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: Bit_Value.cpp:929
Bit_Value::bb_topological
std::vector< blocRef > bb_topological
Topologically ordered basic blocks.
Definition: Bit_Value.hpp:115
basic_block.hpp
Class specification of the basic_block structure.
BitLatticeManipulator::best
CustomMap< unsigned int, std::deque< bit_lattice > > best
Map of the best bit-values of each variable.
Definition: bit_lattice.hpp:85
BitLatticeManipulator::constructor_bitstring
std::deque< bit_lattice > constructor_bitstring(const tree_nodeRef &ctor_tn, unsigned int ssa_node_id) const
auxiliary function used to build the bitstring lattice for read-only arrays
Definition: bit_lattice.cpp:427
BitLatticeManipulator::clear
void clear()
Clean up the internal data structures.
Definition: bit_lattice.cpp:565
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
tree_helper::CGetType
static tree_nodeConstRef CGetType(const tree_nodeConstRef &node)
Return the treenode of the type of node.
Definition: tree_helper.cpp:2167
BitLatticeManipulator::sign_extend_bitstring
static std::deque< bit_lattice > sign_extend_bitstring(const std::deque< bit_lattice > &bitstring, bool bitstring_is_signed, size_t final_size)
Extends a bitstring.
Definition: bit_lattice.cpp:409
Parameter.hpp
this class is used to manage the command-line or XML options.
FunctionFrontendFlowStep::bitvalue_version
unsigned int bitvalue_version
The version of the bitvalue information on which this step has been applied.
Definition: function_frontend_flow_step.hpp:86
tree_helper::get_base_index
static unsigned int get_base_index(const tree_managerConstRef &TM, const unsigned int index)
Retrun the base address of a memory access.
Definition: tree_helper.cpp:3333
Bit_Value::clear_current
void clear_current()
Clears all the entry in the current map, except for the input arguments.
Definition: Bit_Value.cpp:1883
call_graph_manager.hpp
Wrapper to call graph.
tree_helper::GetConstValue
static integer_cst_t GetConstValue(const tree_nodeConstRef &tn, bool is_signed=true)
Get value from integer constant.
Definition: tree_helper.cpp:4358
DesignFlowStep::debug_level
int debug_level
The debug level.
Definition: design_flow_step.hpp:126
Bit_Value::arguments
CustomUnorderedSet< unsigned int > arguments
Contains the input parameters of the function that&#39;s being analyzed.
Definition: Bit_Value.hpp:127
GET_INDEX_CONST_NODE
#define GET_INDEX_CONST_NODE(t)
Definition: tree_node.hpp:363
CFG_SELECTOR
#define CFG_SELECTOR
Control flow graph edge selector.
Definition: cdfg_edge_info.hpp:63
B
#define B
Definition: generate.c:14
tree_helper::GetFunctionReturnType
static tree_nodeConstRef GetFunctionReturnType(const tree_nodeConstRef &function, bool void_as_null=true)
Return the return type of a function.
Definition: tree_helper.cpp:1461
Bit_Value::bit_xor_expr_map
static const std::map< bit_lattice, std::map< bit_lattice, bit_lattice > > bit_xor_expr_map
Map storing the implementation of the forward_transfer&#39;s bit_xor_expr_map.
Definition: Bit_Value.hpp:102
Bit_Value::Bit_Value
Bit_Value(const ParameterConstRef Param, const application_managerRef AM, unsigned int f_id, const DesignFlowManagerConstRef dfm)
Constructor.
Definition: Bit_Value.cpp:917
BBGraphInfoRef
refcount< BBGraphInfo > BBGraphInfoRef
refcount definition of the class
Definition: basic_block.hpp:271
application_frontend_flow_step.hpp
This class contains the base representation for a generic frontend flow step which works on the whole...
memory.hpp
Datastructure to represent memory information in high-level synthesis.
lenet_tvm.params
params
Definition: lenet_tvm.py:13
tree_manager.hpp
Class specification of the manager of the tree structures extracted from the raw file.
bit_lattice::ONE
hls_device.hpp
HLS specialization of generic_device.
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
sl
int sl
Definition: adpcm.c:105
BBGraphsCollection
This structure defines graphs where nodes are basic_blocks.
Definition: basic_block.hpp:280
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
compiler_wrapper.hpp
Implementation of the wrapper to Gcc for C sources.
Generated on Mon Feb 12 2024 13:02:51 for PandA-2024.02 by doxygen 1.8.13