PandA-2024.02
Range_Analysis.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  */
44 #include "Range_Analysis.hpp"
45 
46 #include "config_HAVE_ASSERTS.hpp"
47 
49 #include "Parameter.hpp"
50 
52 #include "application_manager.hpp"
53 #include "basic_block.hpp"
54 #include "call_graph.hpp"
55 #include "call_graph_manager.hpp"
56 #include "function_behavior.hpp"
57 #include "graph.hpp"
58 #include "op_graph.hpp"
59 #include "var_pp_functor.hpp"
60 
61 #include "design_flow_graph.hpp"
62 #include "design_flow_manager.hpp"
64 
66 
68 #include "hls_device.hpp"
69 #include "hls_manager.hpp"
70 
72 #include "memory.hpp"
73 
75 #include "custom_map.hpp"
76 #include <map>
77 #include <set>
78 #include <sstream>
79 #include <vector>
80 
82 #include "ext_tree_node.hpp"
83 #include "token_interface.hpp"
84 #include "tree_basic_block.hpp"
85 #include "tree_helper.hpp"
86 #include "tree_manager.hpp"
87 #include "tree_manipulation.hpp"
88 #include "tree_reindex.hpp"
89 
90 #include "Bit_Value_opt.hpp"
91 #include "bit_lattice.hpp"
92 
93 #include "dbgPrintHelper.hpp" // for DEBUG_LEVEL_
94 #include "string_manipulation.hpp" // for GET_CLASS
95 #include <filesystem> // for create_directories
96 
97 #define RA_JUMPSET
98 // #define EARLY_DEAD_CODE_RESTART // Abort analysis when dead code is detected instead of waiting step's end
99 #define INTEGER_PTR // Pointers are considered as integers
100 #define BITVALUE_UPDATE // Read/write bitvalue information during the analysis
101 
102 #define RA_EXEC_NORMAL 0
103 #define RA_EXEC_READONLY 1
104 #define RA_EXEC_SKIP 2
105 #ifndef NDEBUG
106 // #define DEBUG_RANGE_OP
107 // #define SCC_DEBUG
108 #endif
109 
110 #define CASE_MISCELLANEOUS \
111  aggr_init_expr_K: \
112  case case_label_expr_K: \
113  case lut_expr_K: \
114  case target_expr_K: \
115  case target_mem_ref_K: \
116  case target_mem_ref461_K: \
117  case binfo_K: \
118  case block_K: \
119  case constructor_K: \
120  case error_mark_K: \
121  case identifier_node_K: \
122  case ssa_name_K: \
123  case statement_list_K: \
124  case tree_list_K: \
125  case tree_vec_K: \
126  case call_expr_K
127 
129 
130 union vcFloat
131 {
132  float flt;
134  {
135 #if __BYTE_ORDER == __BIG_ENDIAN
136  uint32_t sign : 1;
137  uint32_t exp : 8;
138  uint32_t frac : 23;
139 #else
140  uint32_t coded;
141 #endif
142  } bits __attribute__((packed));
143 };
144 
145 union vcDouble
146 {
147  double dub;
149  {
150 #if __BYTE_ORDER == __BIG_ENDIAN
151  uint64_t sign : 1;
152  uint64_t exp : 11;
153  uint64_t frac : 52;
154 #else
155  uint64_t coded;
156 #endif
157  } bits __attribute__((packed));
158 };
159 
161 {
162  return static_cast<const tree_reindex*>(lhs.get())->actual_tree_node->index <
163  static_cast<const tree_reindex*>(rhs.get())->actual_tree_node->index;
164 }
165 
166 namespace
167 {
168  // ========================================================================== //
169  // Static global functions and definitions
170  // ========================================================================== //
171 
172  // Used to print pseudo-edges in the Constraint Graph dot
173  std::string pestring;
174  std::stringstream pseudoEdgesString(pestring);
175 
176  kind op_unsigned(kind op)
177  {
178  switch(op)
179  {
180  case ge_expr_K:
181  return unge_expr_K;
182  case gt_expr_K:
183  return ungt_expr_K;
184  case le_expr_K:
185  return unle_expr_K;
186  case lt_expr_K:
187  return unlt_expr_K;
188  case eq_expr_K:
189  return uneq_expr_K;
190  case unge_expr_K:
191  case ungt_expr_K:
192  case unle_expr_K:
193  case unlt_expr_K:
194  case uneq_expr_K:
195  case ne_expr_K:
196  return op;
197 
198  case assert_expr_K:
199  case bit_and_expr_K:
200  case bit_ior_expr_K:
201  case bit_xor_expr_K:
202  case catch_expr_K:
203  case ceil_div_expr_K:
204  case ceil_mod_expr_K:
205  case complex_expr_K:
206  case compound_expr_K:
207  case eh_filter_expr_K:
208  case exact_div_expr_K:
209  case fdesc_expr_K:
210  case floor_div_expr_K:
211  case floor_mod_expr_K:
212  case goto_subroutine_K:
213  case in_expr_K:
214  case init_expr_K:
215  case lrotate_expr_K:
216  case lshift_expr_K:
217  case max_expr_K:
218  case mem_ref_K:
219  case min_expr_K:
220  case minus_expr_K:
221  case modify_expr_K:
222  case mult_expr_K:
223  case mult_highpart_expr_K:
224  case ordered_expr_K:
225  case plus_expr_K:
226  case pointer_plus_expr_K:
227  case postdecrement_expr_K:
228  case postincrement_expr_K:
229  case predecrement_expr_K:
230  case preincrement_expr_K:
231  case range_expr_K:
232  case rdiv_expr_K:
233  case round_div_expr_K:
234  case round_mod_expr_K:
235  case rrotate_expr_K:
236  case rshift_expr_K:
237  case set_le_expr_K:
238  case trunc_div_expr_K:
239  case trunc_mod_expr_K:
240  case truth_and_expr_K:
241  case truth_andif_expr_K:
242  case truth_or_expr_K:
243  case truth_orif_expr_K:
244  case truth_xor_expr_K:
245  case try_catch_expr_K:
246  case try_finally_K:
247  case ltgt_expr_K:
248  case unordered_expr_K:
249  case widen_sum_expr_K:
250  case widen_mult_expr_K:
251  case with_size_expr_K:
252  case vec_lshift_expr_K:
253  case vec_rshift_expr_K:
254  case widen_mult_hi_expr_K:
255  case widen_mult_lo_expr_K:
256  case vec_pack_trunc_expr_K:
257  case vec_pack_sat_expr_K:
258  case vec_pack_fix_trunc_expr_K:
259  case vec_extracteven_expr_K:
260  case vec_extractodd_expr_K:
261  case vec_interleavehigh_expr_K:
262  case vec_interleavelow_expr_K:
263  case extract_bit_expr_K:
264  case sat_plus_expr_K:
265  case sat_minus_expr_K:
266  case extractvalue_expr_K:
267  case extractelement_expr_K:
268  case frem_expr_K:
272  case CASE_TYPE_NODES:
273  case CASE_CST_NODES:
274  case CASE_DECL_NODES:
275  case CASE_FAKE_NODES:
276  case CASE_GIMPLE_NODES:
277  case CASE_PRAGMA_NODES:
278  case CASE_CPP_NODES:
279  case CASE_MISCELLANEOUS:
280  default:
281  break;
282  }
283  THROW_UNREACHABLE("Unhandled predicate (" + STR(op) + ")");
284  return static_cast<kind>(-1);
285  }
286 
287  kind op_inv(kind op)
288  {
289  switch(op)
290  {
291  case ge_expr_K:
292  return lt_expr_K;
293  case gt_expr_K:
294  return le_expr_K;
295  case le_expr_K:
296  return gt_expr_K;
297  case lt_expr_K:
298  return ge_expr_K;
299  case unge_expr_K:
300  return unlt_expr_K;
301  case ungt_expr_K:
302  return unle_expr_K;
303  case unle_expr_K:
304  return ungt_expr_K;
305  case unlt_expr_K:
306  return unge_expr_K;
307  case eq_expr_K:
308  case uneq_expr_K:
309  return ne_expr_K;
310  case ne_expr_K:
311  return eq_expr_K;
312 
313  case assert_expr_K:
314  case bit_and_expr_K:
315  case bit_ior_expr_K:
316  case bit_xor_expr_K:
317  case catch_expr_K:
318  case ceil_div_expr_K:
319  case ceil_mod_expr_K:
320  case complex_expr_K:
321  case compound_expr_K:
322  case eh_filter_expr_K:
323  case exact_div_expr_K:
324  case fdesc_expr_K:
325  case floor_div_expr_K:
326  case floor_mod_expr_K:
327  case goto_subroutine_K:
328  case in_expr_K:
329  case init_expr_K:
330  case lrotate_expr_K:
331  case lshift_expr_K:
332  case max_expr_K:
333  case mem_ref_K:
334  case min_expr_K:
335  case minus_expr_K:
336  case modify_expr_K:
337  case mult_expr_K:
338  case mult_highpart_expr_K:
339  case ordered_expr_K:
340  case plus_expr_K:
341  case pointer_plus_expr_K:
342  case postdecrement_expr_K:
343  case postincrement_expr_K:
344  case predecrement_expr_K:
345  case preincrement_expr_K:
346  case range_expr_K:
347  case rdiv_expr_K:
348  case round_div_expr_K:
349  case round_mod_expr_K:
350  case rrotate_expr_K:
351  case rshift_expr_K:
352  case set_le_expr_K:
353  case trunc_div_expr_K:
354  case trunc_mod_expr_K:
355  case truth_and_expr_K:
356  case truth_andif_expr_K:
357  case truth_or_expr_K:
358  case truth_orif_expr_K:
359  case truth_xor_expr_K:
360  case try_catch_expr_K:
361  case try_finally_K:
362  case ltgt_expr_K:
363  case unordered_expr_K:
364  case widen_sum_expr_K:
365  case widen_mult_expr_K:
366  case with_size_expr_K:
367  case vec_lshift_expr_K:
368  case vec_rshift_expr_K:
369  case widen_mult_hi_expr_K:
370  case widen_mult_lo_expr_K:
371  case vec_pack_trunc_expr_K:
372  case vec_pack_sat_expr_K:
373  case vec_pack_fix_trunc_expr_K:
374  case vec_extracteven_expr_K:
375  case vec_extractodd_expr_K:
376  case vec_interleavehigh_expr_K:
377  case vec_interleavelow_expr_K:
378  case extract_bit_expr_K:
379  case sat_plus_expr_K:
380  case sat_minus_expr_K:
381  case extractvalue_expr_K:
382  case extractelement_expr_K:
383  case frem_expr_K:
387  case CASE_TYPE_NODES:
388  case CASE_CST_NODES:
389  case CASE_DECL_NODES:
390  case CASE_FAKE_NODES:
391  case CASE_GIMPLE_NODES:
392  case CASE_PRAGMA_NODES:
393  case CASE_CPP_NODES:
394  case CASE_MISCELLANEOUS:
395  default:
396  break;
397  }
398 
399  THROW_UNREACHABLE("Unhandled predicate (" + STR(op) + ")");
400  return static_cast<kind>(-1);
401  }
402 
403  kind op_swap(kind op)
404  {
405  switch(op)
406  {
407  case ge_expr_K:
408  return le_expr_K;
409  case gt_expr_K:
410  return lt_expr_K;
411  case le_expr_K:
412  return ge_expr_K;
413  case lt_expr_K:
414  return gt_expr_K;
415  case unge_expr_K:
416  return unle_expr_K;
417  case ungt_expr_K:
418  return unlt_expr_K;
419  case unle_expr_K:
420  return unge_expr_K;
421  case unlt_expr_K:
422  return ungt_expr_K;
423 
424  case bit_and_expr_K:
425  case bit_ior_expr_K:
426  case bit_xor_expr_K:
427  case eq_expr_K:
428  case ne_expr_K:
429  case uneq_expr_K:
430  return op;
431 
432  case assert_expr_K:
433  case catch_expr_K:
434  case ceil_div_expr_K:
435  case ceil_mod_expr_K:
436  case complex_expr_K:
437  case compound_expr_K:
438  case eh_filter_expr_K:
439  case exact_div_expr_K:
440  case fdesc_expr_K:
441  case floor_div_expr_K:
442  case floor_mod_expr_K:
443  case goto_subroutine_K:
444  case in_expr_K:
445  case init_expr_K:
446  case lrotate_expr_K:
447  case lshift_expr_K:
448  case max_expr_K:
449  case mem_ref_K:
450  case min_expr_K:
451  case minus_expr_K:
452  case modify_expr_K:
453  case mult_expr_K:
454  case mult_highpart_expr_K:
455  case ordered_expr_K:
456  case plus_expr_K:
457  case pointer_plus_expr_K:
458  case postdecrement_expr_K:
459  case postincrement_expr_K:
460  case predecrement_expr_K:
461  case preincrement_expr_K:
462  case range_expr_K:
463  case rdiv_expr_K:
464  case round_div_expr_K:
465  case round_mod_expr_K:
466  case rrotate_expr_K:
467  case rshift_expr_K:
468  case set_le_expr_K:
469  case trunc_div_expr_K:
470  case trunc_mod_expr_K:
471  case truth_and_expr_K:
472  case truth_andif_expr_K:
473  case truth_or_expr_K:
474  case truth_orif_expr_K:
475  case truth_xor_expr_K:
476  case try_catch_expr_K:
477  case try_finally_K:
478  case ltgt_expr_K:
479  case unordered_expr_K:
480  case widen_sum_expr_K:
481  case widen_mult_expr_K:
482  case with_size_expr_K:
483  case vec_lshift_expr_K:
484  case vec_rshift_expr_K:
485  case widen_mult_hi_expr_K:
486  case widen_mult_lo_expr_K:
487  case vec_pack_trunc_expr_K:
488  case vec_pack_sat_expr_K:
489  case vec_pack_fix_trunc_expr_K:
490  case vec_extracteven_expr_K:
491  case vec_extractodd_expr_K:
492  case vec_interleavehigh_expr_K:
493  case vec_interleavelow_expr_K:
494  case extract_bit_expr_K:
495  case sat_plus_expr_K:
496  case sat_minus_expr_K:
497  case extractvalue_expr_K:
498  case extractelement_expr_K:
499  case frem_expr_K:
503  case CASE_TYPE_NODES:
504  case CASE_CST_NODES:
505  case CASE_DECL_NODES:
506  case CASE_FAKE_NODES:
507  case CASE_GIMPLE_NODES:
508  case CASE_PRAGMA_NODES:
509  case CASE_CPP_NODES:
510  case CASE_MISCELLANEOUS:
511  default:
512  break;
513  }
514 
515  THROW_UNREACHABLE("Unhandled predicate (" + STR(op) + ")");
516  return static_cast<kind>(-1);
517  }
518 
519  bool isCompare(kind c_type)
520  {
521  return c_type == eq_expr_K || c_type == ne_expr_K || c_type == gt_expr_K || c_type == lt_expr_K ||
522  c_type == ge_expr_K || c_type == le_expr_K;
523  }
524 
525  bool isCompare(const struct binary_expr* condition)
526  {
527  return isCompare(condition->get_kind());
528  }
529 
531  {
532  if(const auto* nop = GetPointer<const nop_expr>(op))
533  {
534  return branchOpRecurse(nop->op);
535  }
536  else if(const auto* ce = GetPointer<const convert_expr>(op))
537  {
538  return branchOpRecurse(ce->op);
539  }
540  else if(const auto* ssa = GetPointer<const ssa_name>(op))
541  {
542  const auto DefStmt = GET_CONST_NODE(ssa->CGetDefStmt());
543  if(const auto* gp = GetPointer<const gimple_phi>(DefStmt))
544  {
545  const auto& defEdges = gp->CGetDefEdgesList();
546  THROW_ASSERT(not defEdges.empty(), "Branch variable definition from nowhere");
547  return defEdges.size() > 1 ? DefStmt : branchOpRecurse(defEdges.front().first);
548  }
549  else if(const auto* ga = GetPointer<const gimple_assign>(DefStmt))
550  {
551  return branchOpRecurse(ga->op1);
552  }
553  else if(GetPointer<const gimple_nop>(DefStmt) != nullptr)
554  {
555  // Branch variable is a function parameter
556  return DefStmt;
557  }
558  THROW_UNREACHABLE("Branch var definition statement not handled (" + DefStmt->get_kind_text() + " " +
559  DefStmt->ToString() + ")");
560  }
561  else if(op->get_kind() == tree_reindex_K)
562  {
563  return branchOpRecurse(GET_CONST_NODE(op));
564  }
565  return op;
566  }
567 
568  // Print name of variable according to its type
569  void printVarName(const tree_nodeConstRef& V, std::ostream& OS)
570  {
571  OS << GET_CONST_NODE(V)->ToString();
572  }
573 
574  bool isValidType(const tree_nodeConstRef& _tn)
575  {
576  const auto tn = _tn->get_kind() == tree_reindex_K ? GET_CONST_NODE(_tn) : _tn;
577  switch(tn->get_kind())
578  {
579  case boolean_type_K:
580  case enumeral_type_K:
581  case integer_type_K:
582 #ifdef INTEGER_PTR
583  case pointer_type_K:
584 #endif
585  return true;
586  case array_type_K:
587  return isValidType(tree_helper::CGetElements(tn));
588  case integer_cst_K:
589  case string_cst_K:
590  case CASE_DECL_NODES:
591  case ssa_name_K:
592  return isValidType(tree_helper::CGetType(tn));
593  case real_type_K:
594  case real_cst_K:
595  case vector_type_K:
596  case CharType_K:
597  case nullptr_type_K:
598  case type_pack_expansion_K:
599  case complex_type_K:
600  case function_type_K:
601  case lang_type_K:
602  case method_type_K:
603  case offset_type_K:
604 #ifndef INTEGER_PTR
605  case pointer_type_K:
606 #endif
607  case qual_union_type_K:
608  case record_type_K:
609  case reference_type_K:
610  case set_type_K:
611  case template_type_parm_K:
612  case typename_type_K:
613  case type_argument_pack_K:
614  case union_type_K:
615  case void_type_K:
616  return false;
617  case complex_cst_K:
618  case vector_cst_K:
619  case void_cst_K:
620  case aggr_init_expr_K:
621  case case_label_expr_K:
622  case lut_expr_K:
623  case target_expr_K:
624  case target_mem_ref_K:
625  case target_mem_ref461_K:
626  case binfo_K:
627  case block_K:
628  case constructor_K:
629  case error_mark_K:
630  case identifier_node_K:
631  case statement_list_K:
632  case tree_list_K:
633  case tree_vec_K:
634  case call_expr_K:
635  case CASE_FAKE_NODES:
640  case CASE_PRAGMA_NODES:
641  case CASE_CPP_NODES:
642  case CASE_GIMPLE_NODES:
643  default:
644  THROW_UNREACHABLE("Unhandled node type (" + tn->get_kind_text() + " " + tn->ToString() + ")");
645  }
646  return false;
647  }
648 
649  bool isValidInstruction(const tree_nodeConstRef& stmt, const FunctionBehaviorConstRef& FB)
650  {
651  tree_nodeConstRef Type = nullptr;
652  switch(GET_CONST_NODE(stmt)->get_kind())
653  {
654  case gimple_assign_K:
655  {
656  auto* ga = GetPointer<const gimple_assign>(GET_CONST_NODE(stmt));
657  if(GET_CONST_NODE(tree_helper::CGetType(ga->op0))->get_kind() == vector_type_K)
658  {
659  // Vector arithmetic not yet supported
660  return false;
661  }
662  if(tree_helper::IsLoad(stmt, FB->get_function_mem()))
663  {
664  Type = tree_helper::CGetType(ga->op0);
665  break;
666  }
667  else if(tree_helper::IsStore(stmt, FB->get_function_mem()))
668  {
669  Type = tree_helper::CGetType(ga->op1);
670  break;
671  }
672  Type = tree_helper::CGetType(ga->op0);
673 
674  switch(GET_CONST_NODE(ga->op1)->get_kind())
675  {
677  case integer_cst_K:
678  case string_cst_K:
679  break;
680 
682  case nop_expr_K:
683  case abs_expr_K:
684  case bit_not_expr_K:
685  case convert_expr_K:
686  case negate_expr_K:
687  case view_convert_expr_K:
688  {
689  const auto* ue = GetPointer<const unary_expr>(GET_CONST_NODE(ga->op1));
690  if(GetPointer<const expr_node>(GET_CONST_NODE(ue->op)))
691  {
692  // Nested operations not supported
693  return false;
694  }
695  break;
696  }
697 
699  case plus_expr_K:
700  case minus_expr_K:
701  case mult_expr_K:
702  case widen_mult_expr_K:
703  case trunc_div_expr_K:
704  case trunc_mod_expr_K:
705  case lshift_expr_K:
706  case rshift_expr_K:
707  case bit_and_expr_K:
708  case bit_ior_expr_K:
709  case bit_xor_expr_K:
710  case eq_expr_K:
711  case ne_expr_K:
712  case gt_expr_K:
713  case ge_expr_K:
714  case lt_expr_K:
715  case le_expr_K:
716 #ifdef INTEGER_PTR
717  case pointer_plus_expr_K:
718 #endif
719  case min_expr_K:
720  case max_expr_K:
721  case sat_plus_expr_K:
722  case sat_minus_expr_K:
723  {
724  const auto bin_op = GetPointer<const binary_expr>(GET_CONST_NODE(ga->op1));
725  if(!isValidType(bin_op->op0) || !isValidType(bin_op->op1))
726  {
727  return false;
728  }
729  break;
730  }
731 
733  case cond_expr_K:
734  break;
735 
736  case ssa_name_K:
737  {
738  if(!isValidType(GET_CONST_NODE(ga->op1)))
739  {
740  return false;
741  }
742  break;
743  }
744 
745  // Unary case
746  case addr_expr_K:
747  case paren_expr_K:
748  case alignof_expr_K:
749  case arrow_expr_K:
750  case buffer_ref_K:
751  case card_expr_K:
752  case cleanup_point_expr_K:
753  case conj_expr_K:
754  case exit_expr_K:
755  case fix_ceil_expr_K:
756  case fix_floor_expr_K:
757  case fix_round_expr_K:
758  case fix_trunc_expr_K:
759  case float_expr_K:
760  case imagpart_expr_K:
761  case indirect_ref_K:
762  case misaligned_indirect_ref_K:
763  case loop_expr_K:
764  case non_lvalue_expr_K:
765  case realpart_expr_K:
766  case reference_expr_K:
767  case reinterpret_cast_expr_K:
768  case sizeof_expr_K:
769  case static_cast_expr_K:
770  case throw_expr_K:
771  case truth_not_expr_K:
772  case unsave_expr_K:
773  case va_arg_expr_K:
774  case reduc_max_expr_K:
775  case reduc_min_expr_K:
776  case reduc_plus_expr_K:
777  case vec_unpack_hi_expr_K:
778  case vec_unpack_lo_expr_K:
779  case vec_unpack_float_hi_expr_K:
780  case vec_unpack_float_lo_expr_K:
781 // Binary case
782 #ifndef INTEGER_PTR
783  case pointer_plus_expr_K:
784 #endif
785  case assert_expr_K:
786  case catch_expr_K:
787  case ceil_div_expr_K:
788  case ceil_mod_expr_K:
789  case complex_expr_K:
790  case compound_expr_K:
791  case eh_filter_expr_K:
792  case exact_div_expr_K:
793  case fdesc_expr_K:
794  case floor_div_expr_K:
795  case floor_mod_expr_K:
796  case goto_subroutine_K:
797  case in_expr_K:
798  case init_expr_K:
799  case lrotate_expr_K:
800  case mem_ref_K:
801  case modify_expr_K:
802  case mult_highpart_expr_K:
803  case ordered_expr_K:
804  case postdecrement_expr_K:
805  case postincrement_expr_K:
806  case predecrement_expr_K:
807  case preincrement_expr_K:
808  case range_expr_K:
809  case rdiv_expr_K:
810  case frem_expr_K:
811  case round_div_expr_K:
812  case round_mod_expr_K:
813  case rrotate_expr_K:
814  case set_le_expr_K:
815  case truth_and_expr_K:
816  case truth_andif_expr_K:
817  case truth_or_expr_K:
818  case truth_orif_expr_K:
819  case truth_xor_expr_K:
820  case try_catch_expr_K:
821  case try_finally_K:
822  case unge_expr_K:
823  case ungt_expr_K:
824  case unlt_expr_K:
825  case unle_expr_K:
826  case uneq_expr_K:
827  case ltgt_expr_K:
828  case unordered_expr_K:
829  case widen_sum_expr_K:
830  case with_size_expr_K:
831  case vec_lshift_expr_K:
832  case vec_rshift_expr_K:
833  case widen_mult_hi_expr_K:
834  case widen_mult_lo_expr_K:
835  case vec_pack_trunc_expr_K:
836  case vec_pack_sat_expr_K:
837  case vec_pack_fix_trunc_expr_K:
838  case vec_extracteven_expr_K:
839  case vec_extractodd_expr_K:
840  case vec_interleavehigh_expr_K:
841  case vec_interleavelow_expr_K:
842  case extract_bit_expr_K:
843  case extractvalue_expr_K:
844  case extractelement_expr_K:
845 
846  // Ternary case
847  case component_ref_K:
848  case bit_field_ref_K:
849  case bit_ior_concat_expr_K:
850  case vtable_ref_K:
851  case with_cleanup_expr_K:
852  case obj_type_ref_K:
853  case save_expr_K:
854  case vec_cond_expr_K:
855  case vec_perm_expr_K:
856  case dot_prod_expr_K:
857  case ternary_plus_expr_K:
858  case ternary_pm_expr_K:
859  case ternary_mp_expr_K:
860  case ternary_mm_expr_K:
861  case fshl_expr_K:
862  case fshr_expr_K:
864  case CASE_TYPE_NODES:
865  case complex_cst_K:
866  case real_cst_K:
867  case void_cst_K:
868  case CASE_DECL_NODES:
869  case CASE_FAKE_NODES:
870  case CASE_GIMPLE_NODES:
871  case CASE_PRAGMA_NODES:
872  case CASE_CPP_NODES:
873  case aggr_init_expr_K:
874  case case_label_expr_K:
875  case lut_expr_K:
876  case target_expr_K:
877  case target_mem_ref_K:
878  case target_mem_ref461_K:
879  case binfo_K:
880  case block_K:
881  case constructor_K:
882  case error_mark_K:
883  case identifier_node_K:
884  case statement_list_K:
885  case tree_list_K:
886  case tree_vec_K:
887  case call_expr_K:
888  case vector_cst_K:
889  case insertvalue_expr_K:
890  case insertelement_expr_K:
891  default:
892  return false;
893  }
894  }
895  break;
896 
897  case gimple_phi_K:
898  {
899  const auto* phi = GetPointer<const gimple_phi>(GET_CONST_NODE(stmt));
900  Type = tree_helper::CGetType(phi->res);
901  }
902  break;
903 
904  case gimple_asm_K:
905  case gimple_bind_K:
906  case gimple_call_K:
907  case gimple_cond_K:
908  case gimple_for_K:
909  case gimple_goto_K:
910  case gimple_label_K:
911  case gimple_multi_way_if_K:
912  case gimple_nop_K:
913  case gimple_pragma_K:
914  case gimple_predict_K:
915  case gimple_resx_K:
916  case gimple_return_K:
917  case gimple_switch_K:
918  case gimple_while_K:
923  case CASE_TYPE_NODES:
924  case CASE_CST_NODES:
925  case CASE_DECL_NODES:
926  case CASE_FAKE_NODES:
927  case CASE_PRAGMA_NODES:
928  case CASE_CPP_NODES:
929  case CASE_MISCELLANEOUS:
930  default:
931  return false;
932  }
933  return isValidType(Type);
934  }
935 
936  bool isSignedType(const tree_nodeConstRef& _tn)
937  {
938  const auto tn = _tn->get_kind() == tree_reindex_K ? GET_CONST_NODE(_tn) : _tn;
939  switch(tn->get_kind())
940  {
941  case enumeral_type_K:
942  return !GetPointer<const enumeral_type>(tn)->unsigned_flag;
943  case integer_type_K:
944  return !GetPointer<const integer_type>(tn)->unsigned_flag;
945  case real_type_K:
946  return true;
947  case boolean_type_K:
948  case array_type_K:
949  case CharType_K:
950  case nullptr_type_K:
951  case type_pack_expansion_K:
952  case complex_type_K:
953  case function_type_K:
954  case lang_type_K:
955  case method_type_K:
956  case offset_type_K:
957  case pointer_type_K:
958  case qual_union_type_K:
959  case record_type_K:
960  case reference_type_K:
961  case set_type_K:
962  case template_type_parm_K:
963  case typename_type_K:
964  case union_type_K:
965  case vector_type_K:
966  case void_type_K:
967  case type_argument_pack_K:
968  return false;
969  case CASE_CST_NODES:
970  case CASE_DECL_NODES:
971  case ssa_name_K:
972  return isSignedType(tree_helper::CGetType(tn));
973  case aggr_init_expr_K:
974  case case_label_expr_K:
975  case lut_expr_K:
976  case target_expr_K:
977  case target_mem_ref_K:
978  case target_mem_ref461_K:
979  case binfo_K:
980  case block_K:
981  case constructor_K:
982  case error_mark_K:
983  case identifier_node_K:
984  case statement_list_K:
985  case tree_list_K:
986  case tree_vec_K:
987  case call_expr_K:
988  case CASE_FAKE_NODES:
993  case CASE_PRAGMA_NODES:
994  case CASE_CPP_NODES:
995  case CASE_GIMPLE_NODES:
996  default:
997  THROW_UNREACHABLE("Unhandled node type (" + tn->get_kind_text() + " " + tn->ToString() + ")");
998  }
999  return true;
1000  }
1001 
1002  tree_nodeConstRef getGIMPLE_Type(const tree_nodeConstRef& tn)
1003  {
1004  if(tn->get_kind() == tree_reindex_K)
1005  {
1006  return getGIMPLE_Type(GET_CONST_NODE(tn));
1007  }
1008  if(const auto* gp = GetPointer<const gimple_phi>(tn))
1009  {
1010  return getGIMPLE_Type(GET_CONST_NODE(gp->res));
1011  }
1012  if(const auto* gr = GetPointer<const gimple_return>(tn))
1013  {
1014  return getGIMPLE_Type(GET_CONST_NODE(gr->op));
1015  }
1016  return tree_helper::CGetType(tn);
1017  }
1018 
1019  bw_t getGIMPLE_BW(const tree_nodeConstRef& tn)
1020  {
1021  const auto type = getGIMPLE_Type(tn);
1022  const auto size = BitLatticeManipulator::Size(type);
1023  THROW_ASSERT(static_cast<bool>(size),
1024  "Unhandled type (" + type->get_kind_text() + ") for " + tn->get_kind_text() + " " + tn->ToString());
1025  return static_cast<bw_t>(size);
1026  }
1027 
1028  RangeRef getRangeFor(const tree_nodeConstRef& tn, RangeType rType)
1029  {
1030  THROW_ASSERT(rType != Anti, "");
1031  if(tn->get_kind() == tree_reindex_K)
1032  {
1033  return getRangeFor(GET_CONST_NODE(tn), rType);
1034  }
1035 
1036  const auto type = getGIMPLE_Type(tn);
1037  const auto bw = static_cast<bw_t>(BitLatticeManipulator::Size(type));
1038  THROW_ASSERT(static_cast<bool>(bw),
1039  "Unhandled type (" + type->get_kind_text() + ") for " + tn->get_kind_text() + " " + tn->ToString());
1040 
1041  return RangeRef(new Range(rType, bw));
1042  }
1043 
1044  RangeRef getGIMPLE_range(const tree_nodeConstRef& tn)
1045  {
1046  if(tn->get_kind() == tree_reindex_K)
1047  {
1048  return getGIMPLE_range(GET_CONST_NODE(tn));
1049  }
1050 
1051  const auto type = getGIMPLE_Type(tn);
1052  bw_t bw = static_cast<bw_t>(BitLatticeManipulator::Size(type));
1053  THROW_ASSERT(static_cast<bool>(bw) || tn->get_kind() == string_cst_K,
1054  "Unhandled type (" + GET_CONST_NODE(type)->get_kind_text() + ") for " + tn->get_kind_text() + " " +
1055  tn->ToString());
1056 #ifdef BITVALUE_UPDATE
1057  bool sign = false;
1058 #endif
1059  APInt min, max;
1060  if(const auto* ic = GetPointer<const integer_cst>(tn))
1061  {
1062  min = max = tree_helper::get_integer_cst_value(ic);
1063  return RangeRef(new Range(Regular, bw, min, max));
1064  }
1065  else if(const auto* sc = GetPointer<const string_cst>(tn))
1066  {
1067  bw = 8;
1068  RangeRef r(new Range(Regular, bw, 0, 0)); // Zero is the string terminator, thus it should always be included
1069  for(const auto& c : sc->strg)
1070  {
1071  r = r->unionWith(RangeRef(new Range(Regular, bw, c, c)));
1072  }
1073  return r;
1074  }
1075  else if(const auto* rc = GetPointer<const real_cst>(tn))
1076  {
1077  THROW_ASSERT(bw == 64 || bw == 32, "Floating point variable with unhandled bitwidth (" + STR(bw) + ")");
1078  if(rc->valx.front() == '-' && rc->valr.front() != rc->valx.front())
1079  {
1080  return Range::fromBitValues(string_to_bitstring(convert_fp_to_string("-" + rc->valr, bw)), bw, false);
1081  }
1082  else
1083  {
1084  return Range::fromBitValues(string_to_bitstring(convert_fp_to_string(rc->valr, bw)), bw, false);
1085  }
1086  }
1087  else if(const auto* vc = GetPointer<const vector_cst>(tn))
1088  {
1089  const auto el_type = tree_helper::CGetElements(type);
1090  const auto el_bw = BitLatticeManipulator::Size(el_type);
1091  RangeRef r(new Range(Empty, bw));
1092  const auto stride = static_cast<size_t>(bw / el_bw);
1093  const auto strides = vc->list_of_valu.size() / stride;
1094  THROW_ASSERT(strides * stride == vc->list_of_valu.size(), "");
1095  for(size_t i = 0; i < strides; ++i)
1096  {
1097  auto curr_el = getGIMPLE_range(vc->list_of_valu.at(i * stride));
1098  for(size_t j = 1; j < stride; ++j)
1099  {
1100  curr_el = getGIMPLE_range(vc->list_of_valu.at(i * stride + j))
1101  ->zextOrTrunc(bw)
1102  ->shl(RangeRef(new Range(Regular, bw, el_bw * j, el_bw * j)))
1103  ->Or(curr_el);
1104  }
1105  r = r->unionWith(curr_el);
1106  }
1107  return r;
1108  }
1109  else if(const auto* it = GetPointer<const integer_type>(GET_CONST_NODE(type)))
1110  {
1111 #ifdef BITVALUE_UPDATE
1112  sign = !it->unsigned_flag;
1113 #endif
1114  min = it->unsigned_flag ? APInt::getMinValue(bw) : APInt::getSignedMinValue(bw);
1115  max = it->unsigned_flag ? APInt::getMaxValue(bw) : APInt::getSignedMaxValue(bw);
1116  }
1117  else if(const auto* et = GetPointer<const enumeral_type>(GET_CONST_NODE(type)))
1118  {
1119 #ifdef BITVALUE_UPDATE
1120  sign = !et->unsigned_flag;
1121 #endif
1122  min = et->unsigned_flag ? APInt::getMinValue(bw) : APInt::getSignedMinValue(bw);
1123  max = et->unsigned_flag ? APInt::getMaxValue(bw) : APInt::getSignedMaxValue(bw);
1124  }
1125  else if(GET_CONST_NODE(type)->get_kind() == boolean_type_K)
1126  {
1127  min = 0;
1128  max = 1;
1129  bw = 1;
1130  }
1131 #ifdef INTEGER_PTR
1132  else if(GetPointer<const pointer_type>(GET_CONST_NODE(type)) != nullptr)
1133  {
1134  min = APInt::getMinValue(bw);
1135  max = APInt::getMaxValue(bw);
1136  }
1137 #endif
1138  else if(GET_CONST_NODE(type)->get_kind() == vector_type_K || GET_CONST_NODE(type)->get_kind() == array_type_K)
1139  {
1141  return RangeRef(new Range(Regular, bw));
1142  }
1143  else if(const auto* rt = GetPointer<const record_type>(GET_CONST_NODE(type)))
1144  {
1145  THROW_ASSERT(GET_CONST_NODE(rt->size)->get_kind() == integer_cst_K &&
1146  tree_helper::GetConstValue(rt->size) >= 0,
1147  "record_type has no size");
1148  bw = static_cast<bw_t>(tree_helper::GetConstValue(rt->size));
1149  THROW_ASSERT(bw, "Invalid bitwidth");
1150  return RangeRef(new Range(Regular, bw));
1151  }
1152  else
1153  {
1154  THROW_UNREACHABLE("Unable to define range for type " + GET_CONST_NODE(type)->get_kind_text() + " of " +
1155  tn->ToString());
1156  }
1157 
1158 #ifdef BITVALUE_UPDATE
1159  if(const auto* ssa = GetPointer<const ssa_name>(tn))
1160  {
1161  if(!ssa->bit_values.empty())
1162  {
1163  const auto bvSize = static_cast<bw_t>(ssa->bit_values.size());
1164  const auto bvRange = Range::fromBitValues(string_to_bitstring(ssa->bit_values), bvSize, sign);
1165  const auto varRange = RangeRef(new Range(Regular, bw, min, max))->truncate(bvSize)->intersectWith(bvRange);
1166  return sign ? varRange->sextOrTrunc(bw) : varRange->zextOrTrunc(bw);
1167  }
1168  }
1169 #endif
1170  return RangeRef(new Range(Regular, bw, min, max));
1171  }
1172 } // namespace
1173 
1174 // ========================================================================== //
1175 // VarNode
1176 // ========================================================================== //
1178 {
1179  ut_None = 0,
1182 };
1183 
1184 class VarNode
1185 {
1189  unsigned int function_id;
1192  RangeConstRef interval;
1193 
1196 
1197  public:
1198  explicit VarNode(const tree_nodeConstRef& _V, unsigned int _function_id);
1199  ~VarNode() = default;
1200  VarNode(const VarNode&) = delete;
1201  VarNode(VarNode&&) = delete;
1202  VarNode& operator=(const VarNode&) = delete;
1203  VarNode& operator=(VarNode&&) = delete;
1204 
1206  void init(bool outside);
1208  RangeConstRef getRange() const
1209  {
1210  return interval;
1211  }
1214  {
1215  return V;
1216  }
1217  unsigned int getFunctionId() const
1218  {
1219  return function_id;
1220  }
1222  {
1223  return interval->getBitWidth();
1224  }
1225 
1227  void setRange(const RangeConstRef& newInterval)
1228  {
1229  interval.reset(newInterval->clone());
1230  }
1231 
1232  RangeRef getMaxRange() const
1233  {
1234  return getRangeFor(V, Regular);
1235  }
1236 
1238  {
1239  return abstractState;
1240  }
1241  // The possible states are '0', '+', '-' and '?'.
1242  void storeAbstractState();
1243 
1244  int updateIR(const tree_managerRef& TM, int debug_level, application_managerRef AppM);
1245 
1247  void print(std::ostream& OS) const;
1248  std::string ToString() const;
1249 };
1250 
1252 VarNode::VarNode(const tree_nodeConstRef& _V, unsigned int _function_id)
1253  : V(_V), function_id(_function_id), abstractState(0)
1254 {
1255  THROW_ASSERT(_V != nullptr, "Variable cannot be null");
1256  THROW_ASSERT(_V->get_kind() == tree_reindex_K, "Variable should be a tree_reindex node");
1257  interval = getRangeFor(_V, Unknown);
1258 }
1259 
1261 void VarNode::init(bool outside)
1262 {
1263  THROW_ASSERT(getGIMPLE_BW(V), "Bitwidth not valid");
1264  THROW_ASSERT(interval, "Interval should be initialized during VarNode construction");
1265  if(interval->isUnknown()) // Ranges already initialized come from user defined hints and shouldn't be overwritten
1266  {
1267  if(GetPointer<const cst_node>(GET_CONST_NODE(V)) != nullptr)
1268  {
1269  interval = getGIMPLE_range(V);
1270  }
1271  else
1272  {
1273  interval = getRangeFor(V, outside ? Regular : Unknown);
1274  }
1275  }
1276 }
1277 
1279  int
1280 #ifndef NDEBUG
1281  debug_level
1282 #endif
1283  ,
1285 {
1286  const auto ssa_node = TM->GetTreeReindex(GET_INDEX_CONST_NODE(V));
1287  auto* SSA = GetPointer<ssa_name>(GET_NODE(ssa_node));
1288  if(SSA == nullptr || interval->isUnknown())
1289  {
1290  return ut_None;
1291  }
1292 
1293 #ifdef BITVALUE_UPDATE
1294  auto updateBitValue = [&](ssa_name* ssa, const std::deque<bit_lattice>& bv) -> int {
1295  const auto curr_bv = string_to_bitstring(ssa->bit_values);
1297  {
1298  ssa->bit_values = bitstring_to_string(bv);
1300  "BitValue updated for " + ssa->ToString() + " " + GET_CONST_NODE(ssa->type)->get_kind_text() +
1301  ": " + SSA->bit_values + " <= " + bitstring_to_string(curr_bv));
1302  return ut_BitValue;
1303  }
1304  return ut_None;
1305  };
1306 #endif
1307 
1308  const bool isSigned = isSignedType(SSA->type);
1309  if(SSA->range != nullptr)
1310  {
1311  if(SSA->range->isSameRange(interval))
1312  {
1313  return ut_None;
1314  }
1315  if(not AppM->ApplyNewTransformation())
1316  {
1317  return ut_None;
1318  }
1320  "Modified range " + SSA->range->ToString() + " to " + interval->ToString() + " for " +
1321  SSA->ToString() + " " + GET_CONST_NODE(SSA->type)->get_kind_text());
1322  }
1323  else
1324  {
1325  bw_t newBW = interval->getBitWidth();
1326  if(interval->isFullSet())
1327  {
1328  return ut_None;
1329  }
1330  if(interval->isConstant())
1331  {
1332  newBW = 0U;
1333  }
1334  else
1335  {
1336  if(interval->isRegular())
1337  {
1338  newBW = isSigned ? Range::neededBits(interval->getSignedMin(), interval->getSignedMax(), true) :
1339  Range::neededBits(interval->getUnsignedMin(), interval->getUnsignedMax(), false);
1340  const auto currentBW = getGIMPLE_BW(V);
1341  if(newBW >= currentBW)
1342  {
1343  return ut_None;
1344  }
1345  }
1346  else if(interval->isAnti())
1347  {
1349  "Anti range " + interval->ToString() + " not stored for " + SSA->ToString() + " " +
1350  GET_CONST_NODE(SSA->type)->get_kind_text());
1351  return ut_None;
1352  }
1353  else if(interval->isEmpty())
1354  {
1356  "Empty range not stored for " + SSA->ToString() + " " +
1357  GET_CONST_NODE(SSA->type)->get_kind_text());
1358  return ut_None;
1359  }
1360  }
1361  if(!AppM->ApplyNewTransformation())
1362  {
1363  return ut_None;
1364  }
1365  // const auto hasBetterSuper = [&]() {
1366  // if(SSA->min && SSA->max)
1367  // {
1368  // RangeRef superRange(
1369  // new Range(Regular, interval->getBitWidth(), tree_helper::GetConstValue(SSA->min),
1370  // tree_helper::GetConstValue(SSA->max)));
1371  // if(superRange->isRegular())
1372  // {
1373  // // Intersect with computed range, because range computed from LLVM range analysis may not be valid
1374  // any more superRange = superRange->intersectWith(interval); if(superRange->isRegular() &&
1375  // superRange->getSpan() < interval->getSpan())
1376  // {
1377  // const auto superBW = isSigned ? Range::neededBits(superRange->getSignedMin(),
1378  // superRange->getSignedMax(), true) : Range::neededBits(superRange->getUnsignedMin(),
1379  // superRange->getUnsignedMax(), false); INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
1380  // "Current range " + superRange->ToString() + "<" + STR(superBW) + ">" + " was
1381  // better than computed range " + interval->ToString() + "<" + STR(newBW) + "> for "
1382  // + SSA->ToString() + " " +
1383  // GET_CONST_NODE(SSA->type)->get_kind_text() + "<" + SSA->bit_values + ">");
1384  // interval = superRange;
1385  // return true;
1386  // }
1387  // }
1388  // }
1389  // return false;
1390  // }();
1391 
1392  // if(!hasBetterSuper)
1393  // {
1395  "Added range " + interval->ToString() + "<" + STR(newBW) + "> for " + SSA->ToString() + " " +
1396  GET_CONST_NODE(SSA->type)->get_kind_text());
1397  // }
1398  }
1399 
1400  int updateState = ut_None;
1401  auto bit_values = string_to_bitstring(SSA->bit_values);
1402  if(interval->isAnti() || interval->isEmpty())
1403  {
1404  updateState = ut_Range;
1405  }
1406  else if(interval->isFullSet())
1407  {
1408  updateState = ut_Range;
1409 #ifdef BITVALUE_UPDATE
1410  bit_values = interval->getBitValues(isSigned);
1411 #endif
1412  }
1413  else
1414  {
1415  updateState = ut_Range;
1416 
1417 #ifdef BITVALUE_UPDATE
1418  if(!bit_values.empty())
1419  {
1420  auto range_bv = interval->getBitValues(isSigned);
1421  const auto sup_bv = BitLatticeManipulator::sup(bit_values, range_bv, interval->getBitWidth(), isSigned,
1422  interval->getBitWidth() == 1);
1423  if(bit_values != sup_bv)
1424  {
1425  bit_values = sup_bv;
1427  "---Range bit_values: " + bitstring_to_string(range_bv));
1428  }
1429  }
1430  else
1431  {
1432  bit_values = interval->getBitValues(isSigned);
1434  "---Range bit_values: " + bitstring_to_string(bit_values));
1435  }
1436 #endif
1437  }
1438 
1439  if(!AppM->ApplyNewTransformation())
1440  {
1441  return ut_None;
1442  }
1443  auto resUpdate = updateBitValue(SSA, bit_values);
1444  if(resUpdate == ut_BitValue)
1445  {
1446  updateState |= ut_BitValue;
1447  Bit_Value_opt::constrainSSA(SSA, TM);
1448  AppM->RegisterTransformation("RangeAnalysis", V);
1450  "---BitValue updated for " + SSA->ToString() + " " + GET_CONST_NODE(SSA->type)->get_kind_text() +
1451  ": " + bitstring_to_string(bit_values) + " <= " + SSA->bit_values);
1452  }
1453 
1454  if(const auto* gp = GetPointer<const gimple_phi>(GET_NODE(SSA->CGetDefStmt())))
1455  {
1456  if(gp->CGetDefEdgesList().size() == 1)
1457  {
1459  "---Sigma defined variable not considered for invalidation loop...");
1460  return ut_None;
1461  }
1462  }
1463  return updateState;
1464 }
1465 
1467 void VarNode::print(std::ostream& OS) const
1468 {
1469  if(GET_CONST_NODE(V)->get_kind() == integer_cst_K)
1470  {
1471  OS << tree_helper::GetConstValue(V);
1472  }
1473  else
1474  {
1475  printVarName(V, OS);
1476  }
1477  OS << " ";
1478  this->getRange()->print(OS);
1479 }
1480 
1481 std::string VarNode::ToString() const
1482 {
1483  std::stringstream ss;
1484  print(ss);
1485  return ss.str();
1486 }
1487 
1489 {
1490  THROW_ASSERT(!this->interval->isUnknown(), "storeAbstractState doesn't handle empty set");
1491 
1492  if(this->interval->getLower() == Range::Min)
1493  {
1494  if(this->interval->getUpper() == Range::Max)
1495  {
1496  this->abstractState = '?';
1497  }
1498  else
1499  {
1500  this->abstractState = '-';
1501  }
1502  }
1503  else if(this->interval->getUpper() == Range::Max)
1504  {
1505  this->abstractState = '+';
1506  }
1507  else
1508  {
1509  this->abstractState = '0';
1510  }
1511 }
1512 
1513 std::ostream& operator<<(std::ostream& OS, const VarNode* VN)
1514 {
1515  VN->print(OS);
1516  return OS;
1517 }
1518 
1519 // ========================================================================== //
1520 // ValueRange
1521 // ========================================================================== //
1523 {
1526 };
1527 
1530 
1531 template <class T>
1532 inline T* GetVR(const ValueRange* t)
1533 {
1534  return T::classof(t) ? static_cast<T*>(t) : nullptr;
1535 }
1536 
1538 {
1539  private:
1540  RangeConstRef range;
1541 
1542  public:
1543  explicit ValueRange(const RangeConstRef& range);
1544  virtual ~ValueRange() = default;
1545  ValueRange(const ValueRange&) = delete;
1546  ValueRange(ValueRange&&) = delete;
1547  ValueRange& operator=(const ValueRange&) = delete;
1548  ValueRange& operator=(ValueRange&&) = delete;
1549 
1550  // Methods for RTTI
1551  virtual ValueRangeType getValueId() const
1552  {
1553  return ValueRangeId;
1554  }
1555  static bool classof(ValueRange const* /*unused*/)
1556  {
1557  return true;
1558  }
1559 
1561  RangeConstRef getRange() const
1562  {
1563  return this->range;
1564  }
1566  void setRange(const RangeConstRef& newRange)
1567  {
1568  this->range.reset(newRange->clone());
1569  }
1570 
1572  virtual void print(std::ostream& OS) const;
1573  std::string ToString() const;
1574 };
1575 
1576 ValueRange::ValueRange(const RangeConstRef& _range) : range(_range->clone())
1577 {
1578 }
1579 
1581 void ValueRange::print(std::ostream& OS) const
1582 {
1583  this->getRange()->print(OS);
1584 }
1585 
1586 std::string ValueRange::ToString() const
1587 {
1588  std::stringstream ss;
1589  print(ss);
1590  return ss.str();
1591 }
1592 
1593 std::ostream& operator<<(std::ostream& OS, const ValueRange* BI)
1594 {
1595  BI->print(OS);
1596  return OS;
1597 }
1598 
1599 // ========================================================================== //
1600 // SymbRange
1601 // ========================================================================== //
1602 
1605 class SymbRange : public ValueRange
1606 {
1607  private:
1614 
1615  public:
1616  SymbRange(const RangeConstRef& range, const tree_nodeConstRef& bound, kind pred);
1617  ~SymbRange() override = default;
1618  SymbRange(const SymbRange&) = delete;
1619  SymbRange(SymbRange&&) = delete;
1620  SymbRange& operator=(const SymbRange&) = delete;
1621  SymbRange& operator=(SymbRange&&) = delete;
1622 
1623  // Methods for RTTI
1624  ValueRangeType getValueId() const override
1625  {
1626  return SymbRangeId;
1627  }
1628  static bool classof(SymbRange const* /*unused*/)
1629  {
1630  return true;
1631  }
1632  static bool classof(ValueRange const* BI)
1633  {
1634  return BI->getValueId() == SymbRangeId;
1635  }
1636 
1639  {
1640  return this->pred;
1641  }
1644  {
1645  return this->bound;
1646  }
1648  RangeConstRef solveFuture(const VarNode* bound, const VarNode* sink) const;
1649 
1651  void print(std::ostream& OS) const override;
1652 };
1653 
1654 SymbRange::SymbRange(const RangeConstRef& _range, const tree_nodeConstRef& _bound, kind _pred)
1655  : ValueRange(_range), bound(_bound), pred(_pred)
1656 {
1657 }
1658 
1659 RangeConstRef SymbRange::solveFuture(const VarNode* _bound, const VarNode* _sink) const
1660 {
1661  // Get the lower and the upper bound of the
1662  // node which bounds this intersection.
1663  const auto boundRange = _bound->getRange();
1664  const auto sinkRange = _sink->getRange();
1665  THROW_ASSERT(!boundRange->isEmpty(), "Bound range should not be empty");
1666  THROW_ASSERT(!sinkRange->isEmpty(), "Sink range should not be empty");
1667 
1668  auto IsAnti = boundRange->isAnti() || sinkRange->isAnti();
1669  const auto l =
1670  IsAnti ? (boundRange->isUnknown() ? Range::Min : boundRange->getUnsignedMin()) : boundRange->getLower();
1671  const auto u =
1672  IsAnti ? (boundRange->isUnknown() ? Range::Max : boundRange->getUnsignedMax()) : boundRange->getUpper();
1673 
1674  // Get the lower and upper bound of the interval of this operation
1675  const auto lower =
1676  IsAnti ? (sinkRange->isUnknown() ? Range::Min : sinkRange->getUnsignedMin()) : sinkRange->getLower();
1677  const auto upper =
1678  IsAnti ? (sinkRange->isUnknown() ? Range::Max : sinkRange->getUnsignedMax()) : sinkRange->getUpper();
1679 
1680  const auto bw = getRange()->getBitWidth();
1681  switch(this->getOperation())
1682  {
1683  case uneq_expr_K:
1684  case eq_expr_K: // equal
1685  return RangeRef(new Range(Regular, bw, l, u));
1686  case le_expr_K: // signed less or equal
1687  if(lower > u)
1688  {
1689  return RangeRef(new Range(Empty, bw));
1690  }
1691  else
1692  {
1693  return RangeRef(new Range(Regular, bw, lower, u));
1694  }
1695  case lt_expr_K: // signed less than
1696  if(u != Range::Max && u != APInt::getSignedMaxValue(bw))
1697  {
1698  if(lower > (u - 1))
1699  {
1700  return RangeRef(new Range(Empty, bw));
1701  }
1702 
1703  return RangeRef(new Range(Regular, bw, lower, u - 1));
1704  }
1705  else
1706  {
1707  if(lower > u)
1708  {
1709  return RangeRef(new Range(Empty, bw));
1710  }
1711 
1712  return RangeRef(new Range(Regular, bw, lower, u));
1713  }
1714  case ge_expr_K: // signed greater or equal
1715  if(l > upper)
1716  {
1717  return RangeRef(new Range(Empty, bw));
1718  }
1719  else
1720  {
1721  return RangeRef(new Range(Regular, bw, l, upper));
1722  }
1723  case gt_expr_K: // signed greater than
1724  if(l != Range::Min && l != APInt::getSignedMinValue(bw))
1725  {
1726  if((l + 1) > upper)
1727  {
1728  return RangeRef(new Range(Empty, bw));
1729  }
1730 
1731  return RangeRef(new Range(Regular, bw, l + 1, upper));
1732  }
1733  else
1734  {
1735  if(l > upper)
1736  {
1737  return RangeRef(new Range(Empty, bw));
1738  }
1739 
1740  return RangeRef(new Range(Regular, bw, l, upper));
1741  }
1742  case ne_expr_K:
1743  case unge_expr_K:
1744  case ungt_expr_K:
1745  case unle_expr_K:
1746  case unlt_expr_K:
1747  break;
1748  case assert_expr_K:
1749  case bit_and_expr_K:
1750  case bit_ior_expr_K:
1751  case bit_xor_expr_K:
1752  case catch_expr_K:
1753  case ceil_div_expr_K:
1754  case ceil_mod_expr_K:
1755  case complex_expr_K:
1756  case compound_expr_K:
1757  case eh_filter_expr_K:
1758  case exact_div_expr_K:
1759  case fdesc_expr_K:
1760  case floor_div_expr_K:
1761  case floor_mod_expr_K:
1762  case goto_subroutine_K:
1763  case in_expr_K:
1764  case init_expr_K:
1765  case lrotate_expr_K:
1766  case lshift_expr_K:
1767  case max_expr_K:
1768  case mem_ref_K:
1769  case min_expr_K:
1770  case minus_expr_K:
1771  case modify_expr_K:
1772  case mult_expr_K:
1773  case mult_highpart_expr_K:
1774  case ordered_expr_K:
1775  case plus_expr_K:
1776  case pointer_plus_expr_K:
1777  case postdecrement_expr_K:
1778  case postincrement_expr_K:
1779  case predecrement_expr_K:
1780  case preincrement_expr_K:
1781  case range_expr_K:
1782  case rdiv_expr_K:
1783  case round_div_expr_K:
1784  case round_mod_expr_K:
1785  case rrotate_expr_K:
1786  case rshift_expr_K:
1787  case set_le_expr_K:
1788  case trunc_div_expr_K:
1789  case trunc_mod_expr_K:
1790  case truth_and_expr_K:
1791  case truth_andif_expr_K:
1792  case truth_or_expr_K:
1793  case truth_orif_expr_K:
1794  case truth_xor_expr_K:
1795  case try_catch_expr_K:
1796  case try_finally_K:
1797  case ltgt_expr_K:
1798  case unordered_expr_K:
1799  case widen_sum_expr_K:
1800  case widen_mult_expr_K:
1801  case with_size_expr_K:
1802  case vec_lshift_expr_K:
1803  case vec_rshift_expr_K:
1804  case widen_mult_hi_expr_K:
1805  case widen_mult_lo_expr_K:
1806  case vec_pack_trunc_expr_K:
1807  case vec_pack_sat_expr_K:
1808  case vec_pack_fix_trunc_expr_K:
1809  case vec_extracteven_expr_K:
1810  case vec_extractodd_expr_K:
1811  case vec_interleavehigh_expr_K:
1812  case vec_interleavelow_expr_K:
1813  case extract_bit_expr_K:
1814  case sat_plus_expr_K:
1815  case sat_minus_expr_K:
1816  case extractvalue_expr_K:
1817  case extractelement_expr_K:
1818  case frem_expr_K:
1819  case CASE_UNARY_EXPRESSION:
1822  case CASE_TYPE_NODES:
1823  case CASE_CST_NODES:
1824  case CASE_DECL_NODES:
1825  case CASE_FAKE_NODES:
1826  case CASE_GIMPLE_NODES:
1827  case CASE_PRAGMA_NODES:
1828  case CASE_CPP_NODES:
1829  case CASE_MISCELLANEOUS:
1830  default:
1831  THROW_UNREACHABLE("Unexpected operation: " + tree_node::GetString(this->getOperation()));
1832  break;
1833  }
1834  return getRangeFor(_sink->getValue(), Regular);
1835 }
1836 
1838 void SymbRange::print(std::ostream& OS) const
1839 {
1840  const auto bnd = getBound();
1841  switch(this->getOperation())
1842  {
1843  case uneq_expr_K:
1844  case eq_expr_K: // equal
1845  OS << "[lb(";
1846  printVarName(bnd, OS);
1847  OS << "), ub(";
1848  printVarName(bnd, OS);
1849  OS << ")]";
1850  break;
1851  case unle_expr_K:
1852  OS << "[0, ub(";
1853  printVarName(bnd, OS);
1854  OS << ")]";
1855  break;
1856  case le_expr_K: // sign less or equal
1857  OS << "[-inf, ub(";
1858  printVarName(bnd, OS);
1859  OS << ")]";
1860  break;
1861  case unlt_expr_K:
1862  OS << "[0, ub(";
1863  printVarName(bnd, OS);
1864  OS << ") - 1]";
1865  break;
1866  case lt_expr_K: // sign less than
1867  OS << "[-inf, ub(";
1868  printVarName(bnd, OS);
1869  OS << ") - 1]";
1870  break;
1871  case unge_expr_K:
1872  case ge_expr_K: // sign greater or equal
1873  OS << "[lb(";
1874  printVarName(bnd, OS);
1875  OS << "), +inf]";
1876  break;
1877  case ungt_expr_K:
1878  case gt_expr_K: // sign greater than
1879  OS << "[lb(";
1880  printVarName(bnd, OS);
1881  OS << " - 1), +inf]";
1882  break;
1883  case ne_expr_K:
1884  OS << ")b(";
1885  printVarName(bnd, OS);
1886  OS << ")(";
1887  break;
1888  case assert_expr_K:
1889  case bit_and_expr_K:
1890  case bit_ior_expr_K:
1891  case bit_xor_expr_K:
1892  case catch_expr_K:
1893  case ceil_div_expr_K:
1894  case ceil_mod_expr_K:
1895  case complex_expr_K:
1896  case compound_expr_K:
1897  case eh_filter_expr_K:
1898  case exact_div_expr_K:
1899  case fdesc_expr_K:
1900  case floor_div_expr_K:
1901  case floor_mod_expr_K:
1902  case goto_subroutine_K:
1903  case in_expr_K:
1904  case init_expr_K:
1905  case lrotate_expr_K:
1906  case lshift_expr_K:
1907  case max_expr_K:
1908  case mem_ref_K:
1909  case min_expr_K:
1910  case minus_expr_K:
1911  case modify_expr_K:
1912  case mult_expr_K:
1913  case mult_highpart_expr_K:
1914  case ordered_expr_K:
1915  case plus_expr_K:
1916  case pointer_plus_expr_K:
1917  case postdecrement_expr_K:
1918  case postincrement_expr_K:
1919  case predecrement_expr_K:
1920  case preincrement_expr_K:
1921  case range_expr_K:
1922  case rdiv_expr_K:
1923  case round_div_expr_K:
1924  case round_mod_expr_K:
1925  case rrotate_expr_K:
1926  case rshift_expr_K:
1927  case set_le_expr_K:
1928  case trunc_div_expr_K:
1929  case trunc_mod_expr_K:
1930  case truth_and_expr_K:
1931  case truth_andif_expr_K:
1932  case truth_or_expr_K:
1933  case truth_orif_expr_K:
1934  case truth_xor_expr_K:
1935  case try_catch_expr_K:
1936  case try_finally_K:
1937  case ltgt_expr_K:
1938  case unordered_expr_K:
1939  case widen_sum_expr_K:
1940  case widen_mult_expr_K:
1941  case with_size_expr_K:
1942  case vec_lshift_expr_K:
1943  case vec_rshift_expr_K:
1944  case widen_mult_hi_expr_K:
1945  case widen_mult_lo_expr_K:
1946  case vec_pack_trunc_expr_K:
1947  case vec_pack_sat_expr_K:
1948  case vec_pack_fix_trunc_expr_K:
1949  case vec_extracteven_expr_K:
1950  case vec_extractodd_expr_K:
1951  case vec_interleavehigh_expr_K:
1952  case vec_interleavelow_expr_K:
1953  case extract_bit_expr_K:
1954  case sat_plus_expr_K:
1955  case sat_minus_expr_K:
1956  case extractvalue_expr_K:
1957  case extractelement_expr_K:
1958  case frem_expr_K:
1959  case CASE_UNARY_EXPRESSION:
1962  case CASE_TYPE_NODES:
1963  case CASE_CST_NODES:
1964  case CASE_DECL_NODES:
1965  case CASE_FAKE_NODES:
1966  case CASE_GIMPLE_NODES:
1967  case CASE_PRAGMA_NODES:
1968  case CASE_CPP_NODES:
1969  case CASE_MISCELLANEOUS:
1970  default:
1971  OS << "Unknown Instruction.";
1972  }
1973 }
1974 
1975 // ========================================================================== //
1976 // ConditionalValueRange
1977 // ========================================================================== //
1979 {
1980  private:
1982  std::map<unsigned int, ValueRangeRef> bbVR;
1983 
1984  public:
1985  ConditionalValueRange(const tree_nodeConstRef& _V, const std::map<unsigned int, ValueRangeRef>& _bbVR)
1986  : V(_V), bbVR(_bbVR)
1987  {
1988  }
1989  ConditionalValueRange(const tree_nodeConstRef& _V, unsigned int TrueBBI, unsigned int FalseBBI,
1990  const ValueRangeRef& TrueVR, const ValueRangeRef& FalseVR)
1991  : V(_V), bbVR({{FalseBBI, FalseVR}, {TrueBBI, TrueVR}})
1992  {
1993  }
1994  ~ConditionalValueRange() = default;
1995  ConditionalValueRange(const ConditionalValueRange&) = default;
1997 
1999  const std::map<unsigned int, ValueRangeRef>& getVR() const
2000  {
2001  return bbVR;
2002  }
2004  const tree_nodeConstRef& getVar() const
2005  {
2006  return V;
2007  }
2009  void addVR(unsigned int bbi, const ValueRangeRef& cvr)
2010  {
2011  if(!static_cast<bool>(bbVR.count(bbi)))
2012  {
2013  bbVR.insert(std::make_pair(bbi, cvr));
2014  }
2015  // TODO: maybe find some way to combine two ValueRange instances (difficult because of symbolic ranges)
2016  }
2017 };
2018 
2019 using ConditionalValueRanges = std::map<tree_nodeConstRef, ConditionalValueRange, tree_reindexCompare>;
2020 
2021 // ========================================================================== //
2022 // OpNode
2023 // ========================================================================== //
2024 
2025 class OpNode;
2026 template <typename T>
2027 inline T* GetOp(OpNode* t)
2028 {
2029  return T::classof(t) ? static_cast<T*>(t) : nullptr;
2030 }
2031 template <typename T>
2032 inline const T* GetOp(const OpNode* t)
2033 {
2034  return T::classof(t) ? static_cast<const T*>(t) : nullptr;
2035 }
2036 
2038 class OpNode
2039 {
2040  private:
2044  ValueRangeRef intersect;
2045  // The target of the operation, that is, the node which
2046  // will store the result of the operation.
2048  // The instruction that originated this op node
2050 
2051  protected:
2054  OpNode(const ValueRangeRef& intersect, VarNode* sink, const tree_nodeConstRef& inst);
2055 
2056  public:
2057  enum class OperationId
2058  {
2059  UnaryOpId,
2060  SigmaOpId,
2061  BinaryOpId,
2062  TernaryOpId,
2063  PhiOpId,
2064  ControlDepId,
2065  LoadOpId,
2066  StoreOpId
2067  };
2068 
2069 #ifndef NDEBUG
2070  static int debug_level;
2071 #endif
2072 
2074  virtual ~OpNode() = default;
2075  // We do not want people creating objects of this class.
2076  OpNode(const OpNode&) = delete;
2077  OpNode(OpNode&&) = delete;
2078  OpNode& operator=(const OpNode&) = delete;
2079  OpNode& operator=(OpNode&&) = delete;
2080 
2081  // Methods for RTTI
2082  virtual OperationId getValueId() const = 0;
2083  static bool classof(OpNode const* /*unused*/)
2084  {
2085  return true;
2086  }
2087 
2090  virtual RangeRef eval() const = 0;
2093  {
2094  return inst;
2095  }
2097  void solveFuture(VarNode* future);
2099  ValueRangeConstRef getIntersect() const
2100  {
2101  return intersect;
2102  }
2104  void setIntersect(const RangeConstRef& newIntersect)
2105  {
2106  this->intersect->setRange(newIntersect);
2107  }
2110  VarNode* getSink() const
2111  {
2112  return sink;
2113  }
2114 
2115  virtual std::vector<tree_nodeConstRef> getSources() const = 0;
2116 
2118  virtual void print(std::ostream& OS) const = 0;
2119  virtual void printDot(std::ostream& OS) const = 0;
2120  std::string ToString() const;
2121 };
2122 
2123 #ifndef NDEBUG
2125 #endif
2126 
2129 OpNode::OpNode(const ValueRangeRef& _intersect, VarNode* _sink, const tree_nodeConstRef& _inst)
2130  : intersect(_intersect), sink(_sink), inst(_inst)
2131 {
2132 }
2133 
2135 {
2136  if(const auto SI = RefcountCast<const SymbRange>(getIntersect()))
2137  {
2138  this->setIntersect(SI->solveFuture(future, getSink()));
2139  }
2140 }
2141 
2142 std::string OpNode::ToString() const
2143 {
2144  std::stringstream ss;
2145  print(ss);
2146  return ss.str();
2147 }
2148 
2149 // ========================================================================== //
2150 // NodeContainer
2151 // ========================================================================== //
2152 
2153 // The VarNodes type.
2154 using VarNodes = std::map<tree_nodeConstRef, VarNode*, tree_reindexCompare>;
2155 // The Operations type.
2157 // A map from varnodes to the operation in which this variable is defined
2158 using DefMap = std::map<tree_nodeConstRef, OpNode*, tree_reindexCompare>;
2159 // A map from variables to the operations where these variables are used.
2160 using UseMap = std::map<tree_nodeConstRef, CustomSet<OpNode*>, tree_reindexCompare>;
2161 
2163 {
2164  private:
2165  static const std::vector<std::function<std::function<OpNode*(NodeContainer*)>(
2166  const tree_nodeConstRef&, unsigned int, const FunctionBehaviorConstRef&, const tree_managerConstRef&,
2167  const application_managerRef&)>>
2168  _opCtorGenerators;
2169 
2171 
2173 
2175 
2177 
2179 
2180  protected:
2182  {
2183  return _useMap;
2184  }
2185 
2186  public:
2187  virtual ~NodeContainer()
2188  {
2189  for(const auto& varNode : _varNodes)
2190  {
2191  delete varNode.second;
2192  }
2193  for(const auto& op : _opNodes)
2194  {
2195  delete op;
2196  }
2197  }
2198 
2199  const VarNodes& getVarNodes() const
2200  {
2201  return _varNodes;
2202  }
2203 
2204  VarNode* addVarNode(const tree_nodeConstRef& V, unsigned int function_id)
2205  {
2206  THROW_ASSERT(V, "Can't insert nullptr as variable");
2207  auto vit = _varNodes.find(V);
2208  if(vit != _varNodes.end())
2209  {
2210  return vit->second;
2211  }
2212 
2213  auto* node = new VarNode(V, function_id);
2214  _varNodes.insert(std::make_pair(V, node));
2215 
2216  // Inserts the node in the use map list.
2217  CustomSet<OpNode*> useList;
2218  _useMap.insert(std::make_pair(V, useList));
2219  return node;
2220  }
2221 
2223  {
2224  return _cvrMap;
2225  }
2226 
2228  {
2229  auto cvrIt = _cvrMap.find(cvr.getVar());
2230  if(cvrIt != _cvrMap.end())
2231  {
2232  for(const auto& BBIvr : cvr.getVR())
2233  {
2234  cvrIt->second.addVR(BBIvr.first, BBIvr.second);
2235  }
2236  }
2237  else
2238  {
2239  _cvrMap.insert(std::make_pair(cvr.getVar(), cvr));
2240  }
2241  }
2242 
2243  const OpNodes& getOpNodes() const
2244  {
2245  return _opNodes;
2246  }
2247 
2249  {
2250  if(op)
2251  {
2252  _opNodes.insert(op);
2253  _defMap.insert({op->getSink()->getValue(), op});
2254  for(const auto& tn : op->getSources())
2255  {
2256  _useMap[tn].insert(op);
2257  }
2258  }
2259  return op;
2260  }
2261 
2262  OpNode* addOperation(const tree_nodeConstRef& stmt, unsigned int function_id, const FunctionBehaviorConstRef& FB,
2263  const tree_managerConstRef& TM, const application_managerRef& AppM)
2264  {
2265  for(const auto& generateCtorFor : _opCtorGenerators)
2266  {
2267  if(auto generateOpFor = generateCtorFor(stmt, function_id, FB, TM, AppM))
2268  {
2269  return pushOperation(generateOpFor(this));
2270  }
2271  }
2272  return nullptr;
2273  }
2274 
2275  const DefMap& getDefs() const
2276  {
2277  return _defMap;
2278  }
2279 
2280  const UseMap& getUses() const
2281  {
2282  return _useMap;
2283  }
2284 
2285 #ifndef NDEBUG
2286  static int debug_level;
2287 #endif
2288 };
2289 
2290 #ifndef NDEBUG
2292 #endif
2293 
2294 #ifndef NDEBUG
2295 static bool enable_add = true;
2296 static bool enable_sub = true;
2297 static bool enable_mul = true;
2298 static bool enable_sdiv = true;
2299 static bool enable_udiv = true;
2300 static bool enable_srem = true;
2301 static bool enable_urem = true;
2302 static bool enable_shl = true;
2303 static bool enable_shr = true;
2304 static bool enable_abs = true;
2305 static bool enable_negate = true;
2306 static bool enable_not = true;
2307 static bool enable_and = true;
2308 static bool enable_or = true;
2309 static bool enable_xor = true;
2310 static bool enable_sext = true;
2311 static bool enable_zext = true;
2312 static bool enable_trunc = true;
2313 static bool enable_min = true;
2314 static bool enable_max = true;
2315 static bool enable_load = true;
2316 static bool enable_float_pack = true;
2317 static bool enable_view_convert = true;
2318 static bool enable_ternary =
2319  false; // TODO: disable because of problem with reduced precision fdiv/f64div operator (fix before enabling back)
2320 static bool enable_bit_phi = true;
2321 
2322 #define OPERATION_OPTION(opts, X) \
2323  if((opts).erase("no_" #X)) \
2324  { \
2325  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Range analysis: " #X " operation disabled"); \
2326  enable_##X = false; \
2327  }
2328 #define RETURN_DISABLED_OPTION(x, bw) \
2329  if(!enable_##x) \
2330  { \
2331  return RangeRef(new Range(Regular, bw)); \
2332  }
2333 #define RESULT_DISABLED_OPTION(x, var, stdResult) enable_##x ? (stdResult) : getRangeFor(var, Regular)
2334 #else
2335 
2336 #define OPERATION_OPTION(opts, X) void(0)
2337 #define RETURN_DISABLED_OPTION(x, bw) void(0)
2338 #define RESULT_DISABLED_OPTION(x, var, stdResult) stdResult
2339 #endif
2340 
2341 // ========================================================================== //
2342 // PhiOp
2343 // ========================================================================== //
2344 
2346 class PhiOpNode : public OpNode
2347 {
2348  private:
2349  // Vector of sources
2350  std::vector<const VarNode*> sources;
2353  RangeRef eval() const override;
2354 
2355  public:
2356  PhiOpNode(const ValueRangeRef& intersect, VarNode* sink, const tree_nodeConstRef& inst);
2357  ~PhiOpNode() override = default;
2358  PhiOpNode(const PhiOpNode&) = delete;
2359  PhiOpNode(PhiOpNode&&) = delete;
2360  PhiOpNode& operator=(const PhiOpNode&) = delete;
2361  PhiOpNode& operator=(PhiOpNode&&) = delete;
2362 
2364  void addSource(const VarNode* newsrc)
2365  {
2366  sources.push_back(newsrc);
2367  }
2369  const VarNode* getSource(size_t index) const
2370  {
2371  return sources[index];
2372  }
2374  size_t getNumSources() const
2375  {
2376  return sources.size();
2377  }
2378 
2379  std::vector<tree_nodeConstRef> getSources() const override
2380  {
2381  std::vector<tree_nodeConstRef> tSources;
2382  std::transform(sources.begin(), sources.end(), std::back_inserter(tSources),
2383  [](const VarNode* vn) -> tree_nodeConstRef { return vn->getValue(); });
2384  return tSources;
2385  }
2386 
2387  // Methods for RTTI
2388  OperationId getValueId() const override
2389  {
2390  return OperationId::PhiOpId;
2391  }
2392  static bool classof(PhiOpNode const* /*unused*/)
2393  {
2394  return true;
2395  }
2396  static bool classof(OpNode const* BO)
2397  {
2398  return BO->getValueId() == OperationId::PhiOpId;
2399  }
2400 
2401  void print(std::ostream& OS) const override;
2402  void printDot(std::ostream& OS) const override;
2403 
2404  static std::function<OpNode*(NodeContainer*)> opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int,
2405  const FunctionBehaviorConstRef& FB,
2406  const tree_managerConstRef& TM,
2407  const application_managerRef& AppM);
2408 };
2409 
2410 // The ctor.
2411 PhiOpNode::PhiOpNode(const ValueRangeRef& _intersect, VarNode* _sink, const tree_nodeConstRef& _inst)
2412  : OpNode(_intersect, _sink, _inst)
2413 {
2414 }
2415 
2419 RangeRef PhiOpNode::eval() const
2420 {
2421  THROW_ASSERT(sources.size() > 0, "Phi operation sources list empty");
2422  auto result = getRangeFor(getSink()->getValue(), Empty);
2423 
2426  // Iterate over the sources of the phiop
2427  for(const VarNode* varNode : sources)
2428  {
2429  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, " ->" + varNode->ToString());
2430  result = result->unionWith(varNode->getRange());
2431  }
2432  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<-- = " + result->ToString());
2433 
2434  bool test = this->getIntersect()->getRange()->isFullSet();
2435  if(!test)
2436  {
2437  const auto aux = this->getIntersect()->getRange();
2438  auto _intersect = result->intersectWith(aux);
2439  if(!_intersect->isEmpty())
2440  {
2442  "---aux = " + aux->ToString() + " from " + getIntersect()->ToString());
2443  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---result = " + _intersect->ToString());
2444  result = _intersect;
2445  }
2446  }
2447  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---res = " + result->ToString());
2448  return result;
2449 }
2450 
2451 std::function<OpNode*(NodeContainer*)>
2452 PhiOpNode::opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int function_id, const FunctionBehaviorConstRef&,
2454 {
2455  const auto* phi = GetPointer<const gimple_phi>(GET_CONST_NODE(stmt));
2456  if(!phi || phi->CGetDefEdgesList().size() <= 1)
2457  {
2458  return nullptr;
2459  }
2460  return [stmt, phi, function_id](NodeContainer* NC) {
2461  if(phi->virtual_flag)
2462  {
2463  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level, "---This is a virtual phi, skipping...");
2464  return static_cast<PhiOpNode*>(nullptr);
2465  }
2466  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
2467  "Analysing phi operation " + phi->ToString());
2468 
2469  // Create the sink.
2470  VarNode* sink = NC->addVarNode(phi->res, function_id);
2471  auto BI = ValueRangeRef(new ValueRange(getGIMPLE_range(stmt)));
2472  auto* phiOp = new PhiOpNode(BI, sink, stmt);
2473 
2474  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
2475  "---Added PhiOp with range " + BI->ToString() + " and " + STR(phi->CGetDefEdgesList().size()) +
2476  " sources");
2477 
2478  // Create the sources.
2479  for(const auto& operandBBI : phi->CGetDefEdgesList())
2480  {
2481  VarNode* source = NC->addVarNode(operandBBI.first, function_id);
2482  phiOp->addSource(source);
2483  }
2484  return phiOp;
2485  };
2486 }
2487 
2488 void PhiOpNode::print(std::ostream& OS) const
2489 {
2490  OS << GET_CONST_NODE(getSink()->getValue())->ToString() << " = PHI<";
2491  int i = 0;
2492  for(; i < static_cast<int>(sources.size() - 1); ++i)
2493  {
2494  OS << GET_CONST_NODE(sources.at(static_cast<decltype(sources.size())>(i))->getValue())->ToString() << ", ";
2495  }
2496  OS << GET_CONST_NODE(sources.at(static_cast<decltype(sources.size())>(i))->getValue())->ToString() << ">";
2497 }
2498 
2499 void PhiOpNode::printDot(std::ostream& OS) const
2500 {
2501  const char* quot = R"(")";
2502  OS << " " << quot << this << quot << R"( [label=")";
2503  OS << "phi";
2504  OS << "\"]\n";
2505  for(const VarNode* varNode : sources)
2506  {
2507  const auto& V = varNode->getValue();
2508  if(GET_CONST_NODE(V)->get_kind() == integer_cst_K)
2509  {
2510  OS << " " << tree_helper::GetConstValue(V) << " -> " << quot << this << quot << "\n";
2511  }
2512  else
2513  {
2514  OS << " " << quot;
2515  printVarName(V, OS);
2516  OS << quot << " -> " << quot << this << quot << "\n";
2517  }
2518  }
2519  const auto& VS = this->getSink()->getValue();
2520  OS << " " << quot << this << quot << " -> " << quot;
2521  printVarName(VS, OS);
2522  OS << quot << "\n";
2523 }
2524 
2525 // ========================================================================== //
2526 // UnaryOp
2527 // ========================================================================== //
2531 class UnaryOpNode : public OpNode
2532 {
2533  private:
2534  // The source node of the operation.
2536  // The opcode of the operation.
2540  RangeRef eval() const override;
2541 
2542  public:
2543  UnaryOpNode(const ValueRangeRef& intersect, VarNode* sink, const tree_nodeConstRef& inst, VarNode* source,
2544  kind opcode);
2545  ~UnaryOpNode() override = default;
2546  UnaryOpNode(const UnaryOpNode&) = delete;
2547  UnaryOpNode(UnaryOpNode&&) = delete;
2548  UnaryOpNode& operator=(const UnaryOpNode&) = delete;
2549  UnaryOpNode& operator=(UnaryOpNode&&) = delete;
2550 
2551  // Methods for RTTI
2552  OperationId getValueId() const override
2553  {
2554  return OperationId::UnaryOpId;
2555  }
2556  static bool classof(UnaryOpNode const* /*unused*/)
2557  {
2558  return true;
2559  }
2560  static bool classof(OpNode const* BO)
2561  {
2563  }
2564 
2566  kind getOpcode() const
2567  {
2568  return opcode;
2569  }
2572  {
2573  return source;
2574  }
2575  std::vector<tree_nodeConstRef> getSources() const override
2576  {
2577  return {source->getValue()};
2578  }
2579 
2580  void print(std::ostream& OS) const override;
2581  void printDot(std::ostream& OS) const override;
2582 
2583  static std::function<OpNode*(NodeContainer*)> opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int,
2584  const FunctionBehaviorConstRef& FB,
2585  const tree_managerConstRef& TM,
2586  const application_managerRef& AppM);
2587 };
2588 
2589 UnaryOpNode::UnaryOpNode(const ValueRangeRef& _intersect, VarNode* _sink, const tree_nodeConstRef& _inst,
2590  VarNode* _source, kind _opcode)
2591  : OpNode(_intersect, _sink, _inst), source(_source), opcode(_opcode)
2592 {
2593 }
2594 
2597 RangeRef UnaryOpNode::eval() const
2598 {
2600 
2601  const auto bw = getSink()->getBitWidth();
2602  const auto oprnd = source->getRange();
2603  const auto resultType = getGIMPLE_Type(getSink()->getValue());
2604  const bool oprndSigned = isSignedType(source->getValue());
2605  auto result = getRangeFor(getSink()->getValue(), Unknown);
2606  if(oprnd->isEmpty())
2607  {
2608  result = RangeRef(new Range(Empty, bw));
2609  }
2610  else if(oprnd->isRegular() || oprnd->isAnti())
2611  {
2612  switch(this->getOpcode())
2613  {
2614  case abs_expr_K:
2615  {
2616  THROW_ASSERT(oprndSigned, "Absolute value of unsigned operand should not happen");
2617  result = RESULT_DISABLED_OPTION(abs, getSink()->getValue(), oprnd->abs());
2618  break;
2619  }
2620  case bit_not_expr_K:
2621  {
2622  result = oprnd->Not();
2623  break;
2624  }
2625  case convert_expr_K:
2626  case nop_expr_K:
2627  {
2628  if(oprndSigned)
2629  {
2630  result = RESULT_DISABLED_OPTION(sext, getSink()->getValue(), oprnd->sextOrTrunc(bw));
2631  }
2632  else
2633  {
2634  result = RESULT_DISABLED_OPTION(zext, getSink()->getValue(), oprnd->zextOrTrunc(bw));
2635  }
2636  break;
2637  }
2638  case negate_expr_K:
2639  {
2640  result = RESULT_DISABLED_OPTION(negate, getSink()->getValue(), oprnd->negate());
2641  break;
2642  }
2643  case view_convert_expr_K:
2644  {
2645  if(GET_CONST_NODE(resultType)->get_kind() != real_type_K)
2646  {
2647  if(oprndSigned)
2648  {
2649  result = RESULT_DISABLED_OPTION(sext, getSink()->getValue(), oprnd->sextOrTrunc(bw));
2650  }
2651  else
2652  {
2653  result = RESULT_DISABLED_OPTION(zext, getSink()->getValue(), oprnd->zextOrTrunc(bw));
2654  }
2655  }
2656  break;
2657  }
2658  case addr_expr_K:
2659  case paren_expr_K:
2660  case alignof_expr_K:
2661  case arrow_expr_K:
2662  case buffer_ref_K:
2663  case card_expr_K:
2664  case cleanup_point_expr_K:
2665  case conj_expr_K:
2666  case exit_expr_K:
2667  case fix_ceil_expr_K:
2668  case fix_floor_expr_K:
2669  case fix_round_expr_K:
2670  case fix_trunc_expr_K:
2671  case float_expr_K:
2672  case imagpart_expr_K:
2673  case indirect_ref_K:
2674  case misaligned_indirect_ref_K:
2675  case loop_expr_K:
2676  case non_lvalue_expr_K:
2677  case realpart_expr_K:
2678  case reference_expr_K:
2679  case reinterpret_cast_expr_K:
2680  case sizeof_expr_K:
2681  case static_cast_expr_K:
2682  case throw_expr_K:
2683  case truth_not_expr_K:
2684  case unsave_expr_K:
2685  case va_arg_expr_K:
2686  case reduc_max_expr_K:
2687  case reduc_min_expr_K:
2688  case reduc_plus_expr_K:
2689  case vec_unpack_hi_expr_K:
2690  case vec_unpack_lo_expr_K:
2691  case vec_unpack_float_hi_expr_K:
2692  case vec_unpack_float_lo_expr_K:
2696  case CASE_TYPE_NODES:
2697  case CASE_CST_NODES:
2698  case CASE_DECL_NODES:
2699  case CASE_FAKE_NODES:
2700  case CASE_GIMPLE_NODES:
2701  case CASE_PRAGMA_NODES:
2702  case CASE_CPP_NODES:
2703  case CASE_MISCELLANEOUS:
2704  default:
2705  THROW_UNREACHABLE("Unhandled unary operation");
2706  break;
2707  }
2708  }
2709  THROW_ASSERT(result, "Result should be set now");
2711  "---" + result->ToString() + " = " + tree_node::GetString(this->getOpcode()) + "( " +
2712  oprnd->ToString() + " )");
2713 
2714  auto test = this->getIntersect()->getRange()->isFullSet();
2715  if(!test)
2716  {
2717  const auto aux = this->getIntersect()->getRange();
2718  auto _intersect = result->intersectWith(aux);
2719  if(!_intersect->isEmpty())
2720  {
2722  "---aux = " + aux->ToString() + " from " + getIntersect()->ToString());
2723  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---result = " + _intersect->ToString());
2724  result = _intersect;
2725  }
2726  }
2727  return result;
2728 }
2729 
2730 std::function<OpNode*(NodeContainer*)>
2731 UnaryOpNode::opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int function_id, const FunctionBehaviorConstRef&,
2733 {
2734  const auto* assign = GetPointer<const gimple_assign>(GET_CONST_NODE(stmt));
2735  if(assign == nullptr)
2736  {
2737  return nullptr;
2738  }
2739  if(GetPointer<const ssa_name>(GET_CONST_NODE(assign->op1)) != nullptr ||
2740  GetPointer<const cst_node>(GET_CONST_NODE(assign->op1)))
2741  {
2742  return [function_id, stmt, assign](NodeContainer* NC) {
2743  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
2744  "Analysing assign operation " + assign->ToString());
2745 
2746  VarNode* sink = NC->addVarNode(assign->op0, function_id);
2747  VarNode* _source = NC->addVarNode(assign->op1, function_id);
2748 
2749  auto BI = ValueRangeRef(new ValueRange(getGIMPLE_range(stmt)));
2750  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
2751  "---Added assign operation with range " + BI->ToString());
2752  return new UnaryOpNode(BI, sink, stmt, _source, nop_expr_K);
2753  };
2754  }
2755  const auto* un_op = GetPointer<const unary_expr>(GET_CONST_NODE(assign->op1));
2756  if(un_op == nullptr)
2757  {
2758  return nullptr;
2759  }
2760  return [stmt, assign, un_op, function_id](NodeContainer* NC) {
2761  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
2762  "Analysing unary operation " + un_op->get_kind_text() + " " + assign->ToString());
2763 
2764  // Create the sink.
2765  auto* sink = NC->addVarNode(assign->op0, function_id);
2766  // Create the source.
2767  auto* _source = NC->addVarNode(un_op->op, function_id);
2768  auto BI = ValueRangeRef(new ValueRange(getGIMPLE_range(stmt)));
2769  const auto op_kind = un_op->get_kind();
2770 
2771  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
2772  "---Added UnaryOp for " + un_op->get_kind_text() + " with range " + BI->ToString());
2773  return new UnaryOpNode(BI, sink, stmt, _source, op_kind);
2774  };
2775 }
2776 
2777 void UnaryOpNode::print(std::ostream& OS) const
2778 {
2779  OS << GET_CONST_NODE(getSink()->getValue())->ToString() << " = " << tree_node::GetString(this->getOpcode()) << "( "
2780  << GET_CONST_NODE(getSource()->getValue())->ToString() << " )";
2781 }
2782 
2783 void UnaryOpNode::printDot(std::ostream& OS) const
2784 {
2785  const char* quot = R"(")";
2786  OS << " " << quot << this << quot << R"( [label=")";
2787 
2788  // Instruction bitwidth
2789  const auto bw = getSink()->getBitWidth();
2790  const bool oprndSigned = isSignedType(source->getValue());
2791 
2792  if(opcode == nop_expr_K || opcode == convert_expr_K)
2793  {
2794  if(bw < getSource()->getBitWidth())
2795  {
2796  OS << "trunc i" << bw;
2797  }
2798  else
2799  {
2800  if(GET_CONST_NODE(getGIMPLE_Type(getSource()->getValue()))->get_kind() == pointer_type_K)
2801  {
2802  OS << "ptr_cast i" << bw;
2803  }
2804  else
2805  {
2806  if(oprndSigned)
2807  {
2808  OS << "sext i" << bw;
2809  }
2810  else
2811  {
2812  OS << "zext i" << bw;
2813  }
2814  }
2815  }
2816  }
2817  else if(opcode == fix_trunc_expr_K)
2818  {
2819  const auto type = getGIMPLE_Type(getSink()->getValue());
2820  if(const auto* int_type = GetPointer<const integer_type>(GET_CONST_NODE(type)))
2821  {
2822  if(int_type->unsigned_flag)
2823  {
2824  OS << "fptoui i" << bw;
2825  }
2826  else
2827  {
2828  OS << "fptosi i" << bw;
2829  }
2830  }
2831  else
2832  {
2833  THROW_UNREACHABLE("Sink should be of type integer");
2834  }
2835  }
2836  else
2837  {
2838  // Phi functions, Loads and Stores are handled here.
2839  this->getIntersect()->print(OS);
2840  }
2841 
2842  OS << "\"]\n";
2843 
2844  const auto& V = this->getSource()->getValue();
2845  if(GET_CONST_NODE(V)->get_kind() == integer_cst_K)
2846  {
2847  OS << " " << tree_helper::GetConstValue(V) << " -> " << quot << this << quot << "\n";
2848  }
2849  else
2850  {
2851  OS << " " << quot;
2852  printVarName(V, OS);
2853  OS << quot << " -> " << quot << this << quot << "\n";
2854  }
2855 
2856  const auto& VS = this->getSink()->getValue();
2857  OS << " " << quot << this << quot << " -> " << quot;
2858  printVarName(VS, OS);
2859  OS << quot << "\n";
2860 }
2861 
2862 // ========================================================================== //
2863 // SigmaOp
2864 // ========================================================================== //
2866 class SigmaOpNode : public UnaryOpNode
2867 {
2868  private:
2871  RangeRef eval() const override;
2872 
2873  // The symbolic source node of the operation.
2875 
2877 
2878  public:
2879  SigmaOpNode(const ValueRangeRef& intersect, VarNode* sink, const tree_nodeConstRef& inst, VarNode* source,
2880  VarNode* SymbolicSource, kind opcode);
2881  ~SigmaOpNode() override = default;
2882  SigmaOpNode(const SigmaOpNode&) = delete;
2883  SigmaOpNode(SigmaOpNode&&) = delete;
2884  SigmaOpNode& operator=(const SigmaOpNode&) = delete;
2885  SigmaOpNode& operator=(SigmaOpNode&&) = delete;
2886 
2887  // Methods for RTTI
2888  OperationId getValueId() const override
2889  {
2890  return OperationId::SigmaOpId;
2891  }
2892  static bool classof(SigmaOpNode const* /*unused*/)
2893  {
2894  return true;
2895  }
2896  static bool classof(UnaryOpNode const* UO)
2897  {
2898  return UO->getValueId() == OperationId::SigmaOpId;
2899  }
2900  static bool classof(OpNode const* BO)
2901  {
2902  return BO->getValueId() == OperationId::SigmaOpId;
2903  }
2904  std::vector<tree_nodeConstRef> getSources() const override
2905  {
2906  std::vector<tree_nodeConstRef> s = UnaryOpNode::getSources();
2907  if(SymbolicSource != nullptr)
2908  {
2909  s.push_back(SymbolicSource->getValue());
2910  }
2911  return s;
2912  }
2913 
2914  bool isUnresolved() const
2915  {
2916  return unresolved;
2917  }
2919  {
2920  unresolved = false;
2921  }
2923  {
2924  unresolved = true;
2925  }
2926 
2927  void print(std::ostream& OS) const override;
2928  void printDot(std::ostream& OS) const override;
2929 
2930  static std::function<OpNode*(NodeContainer*)> opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int,
2931  const FunctionBehaviorConstRef& FB,
2932  const tree_managerConstRef& TM,
2933  const application_managerRef& AppM);
2934 };
2935 
2936 SigmaOpNode::SigmaOpNode(const ValueRangeRef& _intersect, VarNode* _sink, const tree_nodeConstRef& _inst,
2937  VarNode* _source, VarNode* _SymbolicSource, kind _opcode)
2938  : UnaryOpNode(_intersect, _sink, _inst, _source, _opcode), SymbolicSource(_SymbolicSource), unresolved(false)
2939 {
2940 }
2941 
2944 RangeRef SigmaOpNode::eval() const
2945 {
2947 
2948  RangeRef result(this->getSource()->getRange()->clone());
2949  const auto aux = this->getIntersect()->getRange();
2950  if(!aux->isUnknown())
2951  {
2952  auto _intersect = result->intersectWith(aux);
2953  if(!_intersect->isEmpty())
2954  {
2956  "---aux = " + aux->ToString() + " from " + getIntersect()->ToString());
2957  // Sigma operations are used to enhance live range split after conditional statements,
2958  // thus it is useful to intersect their range only if it actually produces tighter interval
2959  if(_intersect->getSpan() < result->getSpan())
2960  {
2961  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---result = " + _intersect->ToString());
2962  result = _intersect;
2963  }
2964  else
2965  {
2966  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---result not changed because not improved");
2967  }
2968  }
2969  }
2971  "---" + result->ToString() + " = SIGMA< " + getSource()->getRange()->ToString() + " >");
2972  return result;
2973 }
2974 
2975 std::function<OpNode*(NodeContainer*)>
2976 SigmaOpNode::opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int function_id, const FunctionBehaviorConstRef&,
2978 {
2979  const auto* phi = GetPointer<const gimple_phi>(GET_CONST_NODE(stmt));
2980  if(!phi || phi->CGetDefEdgesList().size() != 1)
2981  {
2982  return nullptr;
2983  }
2984  return [stmt, phi, function_id](NodeContainer* NC) {
2985  const auto BBI = phi->bb_index;
2986  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
2987  "Analysing sigma operation " + phi->ToString());
2988  const auto& sourceTN = phi->CGetDefEdgesList().front().first;
2989 
2990  // Create the sink.
2991  VarNode* sink = NC->addVarNode(phi->res, function_id);
2992  VarNode* source = NC->addVarNode(sourceTN, function_id);
2993 
2994  auto vsmit = NC->getCVR().find(sourceTN);
2995  if(vsmit == NC->getCVR().end())
2996  {
2997  return static_cast<SigmaOpNode*>(nullptr);
2998  }
2999 
3000  auto condRangeIt = vsmit->second.getVR().find(BBI);
3001  if(condRangeIt != vsmit->second.getVR().end())
3002  {
3003  const auto& CondRange = condRangeIt->second;
3004  VarNode* SymbSrc = nullptr;
3005  if(auto symb = RefcountCast<SymbRange>(CondRange))
3006  {
3007  const auto& bound = symb->getBound();
3008  SymbSrc = NC->addVarNode(bound, function_id);
3009  }
3010  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
3011  "---Added SigmaOp with " + std::string(SymbSrc ? "symbolic " : "") + "range " +
3012  CondRange->ToString());
3013  return new SigmaOpNode(CondRange, sink, stmt, source, SymbSrc, phi->get_kind());
3014  }
3015  else
3016  {
3017  auto BI = ValueRangeRef(new ValueRange(getGIMPLE_range(stmt)));
3018  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
3019  "---Added SigmaOp with range " + BI->ToString());
3020  return new SigmaOpNode(BI, sink, stmt, source, nullptr, phi->get_kind());
3021  }
3022  };
3023 }
3024 
3025 void SigmaOpNode::print(std::ostream& OS) const
3026 {
3027  OS << GET_CONST_NODE(getSink()->getValue())->ToString() << " = SIGMA< "
3028  << GET_CONST_NODE(getSource()->getValue())->ToString() << " >";
3029 }
3030 
3031 void SigmaOpNode::printDot(std::ostream& OS) const
3032 {
3033  const char* quot = R"(")";
3034  OS << " " << quot << this << quot << R"( [label=")"
3035  << "SigmaOp:";
3036  this->getIntersect()->print(OS);
3037  OS << "\"]\n";
3038  const auto& V = this->getSource()->getValue();
3039  if(GET_CONST_NODE(V)->get_kind() == integer_cst_K)
3040  {
3041  OS << " " << tree_helper::GetConstValue(V) << " -> " << quot << this << quot << "\n";
3042  }
3043  else
3044  {
3045  OS << " " << quot;
3046  printVarName(V, OS);
3047  OS << quot << " -> " << quot << this << quot << "\n";
3048  }
3049  if(SymbolicSource)
3050  {
3051  const auto& _V = SymbolicSource->getValue();
3052  if(GET_CONST_NODE(_V)->get_kind() == integer_cst_K)
3053  {
3054  OS << " " << tree_helper::GetConstValue(_V) << " -> " << quot << this << quot << "\n";
3055  }
3056  else
3057  {
3058  OS << " " << quot;
3059  printVarName(_V, OS);
3060  OS << quot << " -> " << quot << this << quot << "\n";
3061  }
3062  }
3063 
3064  const auto& VS = this->getSink()->getValue();
3065  OS << " " << quot << this << quot << " -> " << quot;
3066  printVarName(VS, OS);
3067  OS << quot << "\n";
3068 }
3069 
3070 // ========================================================================== //
3071 // BinaryOp
3072 // ========================================================================== //
3074 class BinaryOpNode : public OpNode
3075 {
3076  private:
3077  // The first operand.
3079  // The second operand.
3081  // The opcode of the operation.
3085  RangeRef eval() const override;
3086 
3087  public:
3088  BinaryOpNode(const ValueRangeRef& intersect, VarNode* sink, const tree_nodeConstRef& inst, VarNode* source1,
3089  VarNode* source2, kind opcode);
3090  ~BinaryOpNode() override = default;
3091  BinaryOpNode(const BinaryOpNode&) = delete;
3092  BinaryOpNode(BinaryOpNode&&) = delete;
3093  BinaryOpNode& operator=(const BinaryOpNode&) = delete;
3094  BinaryOpNode& operator=(BinaryOpNode&&) = delete;
3095 
3096  // Methods for RTTI
3097  OperationId getValueId() const override
3098  {
3099  return OperationId::BinaryOpId;
3100  }
3101  static bool classof(BinaryOpNode const* /*unused*/)
3102  {
3103  return true;
3104  }
3105  static bool classof(OpNode const* BO)
3106  {
3107  return BO->getValueId() == OperationId::BinaryOpId;
3108  }
3109 
3110  static RangeRef evaluate(kind opcode, bw_t bw, const RangeConstRef& op1, const RangeConstRef& op2, bool opSigned);
3111 
3113  kind getOpcode() const
3114  {
3115  return opcode;
3116  }
3119  {
3120  return source1;
3121  }
3124  {
3125  return source2;
3126  }
3127  std::vector<tree_nodeConstRef> getSources() const override
3128  {
3129  return {source1->getValue(), source2->getValue()};
3130  }
3131 
3132  void print(std::ostream& OS) const override;
3133  void printDot(std::ostream& OS) const override;
3134 
3135  static std::function<OpNode*(NodeContainer*)> opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int,
3136  const FunctionBehaviorConstRef& FB,
3137  const tree_managerConstRef& TM,
3138  const application_managerRef& AppM);
3139 };
3140 
3141 // The ctor.
3142 BinaryOpNode::BinaryOpNode(const ValueRangeRef& _intersect, VarNode* _sink, const tree_nodeConstRef& _inst,
3143  VarNode* _source1, VarNode* _source2, kind _opcode)
3144  : OpNode(_intersect, _sink, _inst), source1(_source1), source2(_source2), opcode(_opcode)
3145 {
3146  THROW_ASSERT(isValidType(_sink->getValue()), "Binary operation sink should be of valid type (" +
3147  GET_CONST_NODE(_sink->getValue())->ToString() + ")");
3148 }
3149 
3150 RangeRef BinaryOpNode::evaluate(kind opcode, bw_t bw, const RangeConstRef& op1, const RangeConstRef& op2, bool opSigned)
3151 {
3152  switch(opcode)
3153  {
3154 #ifdef INTEGER_PTR
3155  case pointer_plus_expr_K:
3156 #endif
3157  case plus_expr_K:
3159  return op1->add(op2);
3160  case minus_expr_K:
3161  RETURN_DISABLED_OPTION(sub, bw);
3162  return op1->sub(op2);
3163  case mult_expr_K:
3164  RETURN_DISABLED_OPTION(mul, bw);
3165  return op1->mul(op2);
3166  case widen_mult_expr_K:
3167  RETURN_DISABLED_OPTION(mul, bw);
3168  return opSigned ? op1->sextOrTrunc(bw)->mul(op2->sextOrTrunc(bw)) :
3169  op1->zextOrTrunc(bw)->mul(op2->sextOrTrunc(bw));
3170  case trunc_div_expr_K:
3171  if(opSigned)
3172  {
3173  RETURN_DISABLED_OPTION(sdiv, bw);
3174  return op1->sdiv(op2);
3175  }
3176  else
3177  {
3178  RETURN_DISABLED_OPTION(udiv, bw);
3179  return op1->udiv(op2);
3180  }
3181  case trunc_mod_expr_K:
3182  if(opSigned)
3183  {
3184  RETURN_DISABLED_OPTION(srem, bw);
3185  const auto res = op1->srem(op2);
3186  if(!res->isUnknown() && !res->isEmpty() && res->getSignedMin() == 0)
3187  {
3188  const auto consRes = res->unionWith(res->negate());
3190  "---Being conservative on signed modulo operator: " + res->ToString() + " -> " +
3191  consRes->ToString());
3192  return consRes;
3193  }
3194  return res;
3195  }
3196  else
3197  {
3198  RETURN_DISABLED_OPTION(urem, bw);
3199  return op1->urem(op2);
3200  }
3201  case lshift_expr_K:
3203  return opSigned ? op1->sextOrTrunc(bw)->shl(op2) : op1->zextOrTrunc(bw)->shl(op2);
3204  case rshift_expr_K:
3206  return opSigned ? op1->shr(op2, true)->sextOrTrunc(bw) : op1->shr(op2, false)->zextOrTrunc(bw);
3207  case bit_and_expr_K:
3208  RETURN_DISABLED_OPTION(and, bw);
3209  return op1->And(op2);
3210  case bit_ior_expr_K:
3211  RETURN_DISABLED_OPTION(or, bw);
3212  return op1->Or(op2);
3213  case bit_xor_expr_K:
3214  RETURN_DISABLED_OPTION(xor, bw);
3215  return op1->Xor(op2);
3216  case eq_expr_K:
3217  if(op1->getBitWidth() < op2->getBitWidth())
3218  {
3219  return opSigned ? op1->sextOrTrunc(op2->getBitWidth())->Eq(op2, bw) :
3220  op1->zextOrTrunc(op2->getBitWidth())->Eq(op2, bw);
3221  }
3222  else if(op2->getBitWidth() < op1->getBitWidth())
3223  {
3224  return opSigned ? op2->sextOrTrunc(op1->getBitWidth())->Eq(op1, bw) :
3225  op2->zextOrTrunc(op1->getBitWidth())->Eq(op1, bw);
3226  }
3227  return op1->Eq(op2, bw);
3228  case ne_expr_K:
3229  return op1->Ne(op2, bw);
3230  case gt_expr_K:
3231  return opSigned ? op1->Sgt(op2, bw) : op1->Ugt(op2, bw);
3232  case ge_expr_K:
3233  return opSigned ? op1->Sge(op2, bw) : op1->Uge(op2, bw);
3234  case lt_expr_K:
3235  return opSigned ? op1->Slt(op2, bw) : op1->Ult(op2, bw);
3236  case le_expr_K:
3237  return opSigned ? op1->Sle(op2, bw) : op1->Ule(op2, bw);
3238  case min_expr_K:
3239  RETURN_DISABLED_OPTION(min, bw);
3240  return opSigned ? op1->SMin(op2) : op1->UMin(op2);
3241  case max_expr_K:
3242  RETURN_DISABLED_OPTION(max, bw);
3243  return opSigned ? op1->SMax(op2) : op1->UMax(op2);
3244  case sat_plus_expr_K:
3246  return opSigned ? op1->sat_add(op2) : op1->usat_add(op2);
3247  case sat_minus_expr_K:
3248  RETURN_DISABLED_OPTION(sub, bw);
3249  return opSigned ? op1->sat_sub(op2) : op1->usat_sub(op2);
3250 
3251 #ifndef INTEGER_PTR
3252  case pointer_plus_expr_K:
3253 #endif
3254  case assert_expr_K:
3255  case catch_expr_K:
3256  case ceil_div_expr_K:
3257  case ceil_mod_expr_K:
3258  case complex_expr_K:
3259  case compound_expr_K:
3260  case eh_filter_expr_K:
3261  case exact_div_expr_K:
3262  case fdesc_expr_K:
3263  case floor_div_expr_K:
3264  case floor_mod_expr_K:
3265  case goto_subroutine_K:
3266  case in_expr_K:
3267  case init_expr_K:
3268  case lrotate_expr_K:
3269  case mem_ref_K:
3270  case modify_expr_K:
3271  case mult_highpart_expr_K:
3272  case ordered_expr_K:
3273  case postdecrement_expr_K:
3274  case postincrement_expr_K:
3275  case predecrement_expr_K:
3276  case preincrement_expr_K:
3277  case range_expr_K:
3278  case rdiv_expr_K:
3279  case frem_expr_K:
3280  case round_div_expr_K:
3281  case round_mod_expr_K:
3282  case rrotate_expr_K:
3283  case set_le_expr_K:
3284  case truth_and_expr_K:
3285  case truth_andif_expr_K:
3286  case truth_or_expr_K:
3287  case truth_orif_expr_K:
3288  case truth_xor_expr_K:
3289  case try_catch_expr_K:
3290  case try_finally_K:
3291  case ltgt_expr_K:
3292  case uneq_expr_K:
3293  case unge_expr_K:
3294  case ungt_expr_K:
3295  case unlt_expr_K:
3296  case unle_expr_K:
3297  case unordered_expr_K:
3298  case widen_sum_expr_K:
3299  case with_size_expr_K:
3300  case vec_lshift_expr_K:
3301  case vec_rshift_expr_K:
3302  case widen_mult_hi_expr_K:
3303  case widen_mult_lo_expr_K:
3304  case vec_pack_trunc_expr_K:
3305  case vec_pack_sat_expr_K:
3306  case vec_pack_fix_trunc_expr_K:
3307  case vec_extracteven_expr_K:
3308  case vec_extractodd_expr_K:
3309  case vec_interleavehigh_expr_K:
3310  case vec_interleavelow_expr_K:
3311  case extract_bit_expr_K:
3312  case extractvalue_expr_K:
3313  case extractelement_expr_K:
3314  case CASE_UNARY_EXPRESSION:
3317  case CASE_TYPE_NODES:
3318  case CASE_CST_NODES:
3319  case CASE_DECL_NODES:
3320  case CASE_FAKE_NODES:
3321  case CASE_GIMPLE_NODES:
3322  case CASE_PRAGMA_NODES:
3323  case CASE_CPP_NODES:
3324  case CASE_MISCELLANEOUS:
3325  default:
3326  THROW_UNREACHABLE("Unhandled binary operation (" + tree_node::GetString(opcode) + ")");
3327  break;
3328  }
3329  return nullptr;
3330 }
3331 
3336 RangeRef BinaryOpNode::eval() const
3337 {
3338  const auto op1 = this->getSource1()->getRange();
3339  const auto op2 = this->getSource2()->getRange();
3340  // Instruction bitwidth
3341  const auto sinkBW = getSink()->getBitWidth();
3342  auto result = getRangeFor(getSink()->getValue(), Unknown);
3343 
3345 
3346  // only evaluate if all operands are Regular
3347  if((op1->isRegular() || op1->isAnti()) && (op2->isRegular() || op2->isAnti()))
3348  {
3349  const auto opSigned = isSignedType(getSource1()->getValue());
3350 
3351  result = evaluate(this->getOpcode(), sinkBW, op1, op2, opSigned);
3352 
3353  // Bitvalue may consider only lower bits for some variables, thus it is necessary to perform evaluation on
3354  // truncated opernds to obtain valid results
3355  if(const auto* ssa = GetPointer<const ssa_name>(GET_CONST_NODE(getSink()->getValue())))
3356  {
3357  const auto sinkSigned = isSignedType(getSink()->getValue());
3358  const auto bvRange = [&]() {
3359  if(ssa->bit_values.empty() || ssa->bit_values.front() == 'X')
3360  {
3361  return RangeRef(new Range(Regular, sinkBW));
3362  }
3363  APInt bits(0);
3364  uint8_t i = 0;
3365  for(auto it = ssa->bit_values.crbegin(); it != ssa->bit_values.crend(); ++it, ++i)
3366  {
3367  if(*it != '0')
3368  {
3369  bits |= APInt(1) << i;
3370  }
3371  }
3372  const auto r = RangeRef(new Range(Regular, static_cast<bw_t>(ssa->bit_values.size()), bits, bits));
3373  THROW_ASSERT(r->isConstant(), "Range derived from <" + ssa->bit_values + "> should be constant");
3374  return r;
3375  }();
3376  const auto op_code = this->getOpcode();
3377  if(bvRange->isConstant() &&
3378  (bvRange->getSignedMax() != -1 || bvRange->getBitWidth() < result->getBitWidth()) &&
3379  (op_code == mult_expr_K || op_code == widen_mult_expr_K ||
3380  op_code == plus_expr_K /* || op_code == minus_expr_K || op_code == pointer_plus_expr_K */))
3381  {
3383  "---Result range " + result->ToString() + " filtered with mask " +
3384  bitstring_to_string(bvRange->getBitValues(sinkSigned)) + "<" +
3385  STR(bvRange->getBitWidth()) + "> from " + ssa->bit_values + "<" +
3386  (sinkSigned ? "signed" : "unsigned") + "> " + bvRange->ToString());
3387  // #if HAVE_ASSERTS
3388  // const auto resEmpty = result->isEmpty();
3389  // #endif
3390  const auto truncRes = sinkSigned ?
3391  result->truncate(bvRange->getBitWidth())->sextOrTrunc(result->getBitWidth()) :
3392  result->truncate(bvRange->getBitWidth())->zextOrTrunc(result->getBitWidth());
3393  const auto maskRes = sinkSigned ? result->And(bvRange->zextOrTrunc(result->getBitWidth()))
3394  ->truncate(bvRange->getBitWidth())
3395  ->sextOrTrunc(result->getBitWidth()) :
3396  result->And(bvRange->zextOrTrunc(result->getBitWidth()));
3397  result = truncRes->getSpan() < maskRes->getSpan() ? truncRes : maskRes;
3398  // THROW_ASSERT(result->isEmpty() == resEmpty, "");
3399  }
3400  }
3401 
3402  if(result->getBitWidth() != sinkBW)
3403  {
3404  result = result->zextOrTrunc(sinkBW);
3405  }
3406  }
3407  else if(op1->isEmpty() || op2->isEmpty())
3408  {
3409  result = getRangeFor(getSink()->getValue(), Empty);
3410  }
3412  "---" + result->ToString() + " = " + op1->ToString() + " " + tree_node::GetString(this->getOpcode()) +
3413  " " + op2->ToString());
3414 
3415  bool test = this->getIntersect()->getRange()->isFullSet();
3416  if(!test)
3417  {
3418  const auto aux = this->getIntersect()->getRange();
3419  auto _intersect = result->intersectWith(aux);
3420  if(!_intersect->isEmpty())
3421  {
3423  "---aux = " + aux->ToString() + " from " + getIntersect()->ToString());
3424  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---result = " + _intersect->ToString());
3425  result = _intersect;
3426  }
3427  }
3428  return result;
3429 }
3430 
3431 std::function<OpNode*(NodeContainer*)>
3432 BinaryOpNode::opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int function_id, const FunctionBehaviorConstRef&,
3434 {
3435  const auto* assign = GetPointer<const gimple_assign>(GET_CONST_NODE(stmt));
3436  if(assign == nullptr)
3437  {
3438  return nullptr;
3439  }
3440  const auto* bin_op = GetPointer<const binary_expr>(GET_CONST_NODE(assign->op1));
3441  if(bin_op == nullptr)
3442  {
3443  return nullptr;
3444  }
3445  return [stmt, assign, bin_op, function_id](NodeContainer* NC) {
3446  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
3447  "Analysing binary operation " + bin_op->get_kind_text() + " " + assign->ToString());
3448 
3449  // Create the sink.
3450  auto* sink = NC->addVarNode(assign->op0, function_id);
3451  auto op_kind = bin_op->get_kind();
3452 
3453  // Create the sources.
3454  auto* _source1 = NC->addVarNode(bin_op->op0, function_id);
3455  auto* _source2 = NC->addVarNode(bin_op->op1, function_id);
3456 
3457  auto BI = ValueRangeRef(new ValueRange(getGIMPLE_range(stmt)));
3458 
3459  // Create the operation using the intersect to constrain sink's interval.
3460  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
3461  "---Added BinaryOp for " + tree_node::GetString(op_kind) + " with range " + BI->ToString());
3462  return static_cast<OpNode*>(new BinaryOpNode(BI, sink, stmt, _source1, _source2, op_kind));
3463  };
3464 }
3465 
3466 void BinaryOpNode::print(std::ostream& OS) const
3467 {
3468  OS << GET_CONST_NODE(getSink()->getValue())->ToString() << " = ("
3469  << GET_CONST_NODE(getSource1()->getValue())->ToString() << ")" << tree_node::GetString(this->getOpcode()) + "("
3470  << GET_CONST_NODE(getSource2()->getValue())->ToString() << ")";
3471 }
3472 
3473 void BinaryOpNode::printDot(std::ostream& OS) const
3474 {
3475  const char* quot = R"(")";
3476  std::string opcodeName = tree_node::GetString(opcode);
3477  OS << " " << quot << this << quot << R"( [label=")" << opcodeName << "\"]\n";
3478  const auto& V1 = this->getSource1()->getValue();
3479  if(GET_CONST_NODE(V1)->get_kind() == integer_cst_K)
3480  {
3481  OS << " " << tree_helper::GetConstValue(V1) << " -> " << quot << this << quot << "\n";
3482  }
3483  else
3484  {
3485  OS << " " << quot;
3486  printVarName(V1, OS);
3487  OS << quot << " -> " << quot << this << quot << "\n";
3488  }
3489  const auto& V2 = this->getSource2()->getValue();
3490  if(GET_CONST_NODE(V2)->get_kind() == integer_cst_K)
3491  {
3492  OS << " " << tree_helper::GetConstValue(V2) << " -> " << quot << this << quot << "\n";
3493  }
3494  else
3495  {
3496  OS << " " << quot;
3497  printVarName(V2, OS);
3498  OS << quot << " -> " << quot << this << quot << "\n";
3499  }
3500  const auto& VS = this->getSink()->getValue();
3501  OS << " " << quot << this << quot << " -> " << quot;
3502  printVarName(VS, OS);
3503  OS << quot << "\n";
3504 }
3505 
3506 unsigned int evaluateBranch(const tree_nodeRef br_op, const blocRef branchBB
3507 #ifndef NDEBUG
3508  ,
3509  int debug_level
3510 #endif
3511 )
3512 {
3513  // Evaluate condition variable if possible
3514  if(GET_CONST_NODE(br_op)->get_kind() == integer_cst_K)
3515  {
3516  const auto branchValue = tree_helper::GetConstValue(br_op);
3517  if(branchValue)
3518  {
3520  "Branch variable value is " + STR(branchValue) + ", false edge BB" + STR(branchBB->false_edge) +
3521  " to be removed");
3522  return branchBB->false_edge;
3523  }
3524  else
3525  {
3527  "Branch variable value is " + STR(branchValue) + ", true edge BB" + STR(branchBB->true_edge) +
3528  " to be removed");
3529  return branchBB->true_edge;
3530  }
3531  }
3532  else if(const auto* bin_op = GetPointer<const binary_expr>(GET_CONST_NODE(br_op)))
3533  {
3534  const auto* l = GetPointer<const integer_cst>(GET_CONST_NODE(bin_op->op0));
3535  const auto* r = GetPointer<const integer_cst>(GET_CONST_NODE(bin_op->op1));
3536  if(l != nullptr && r != nullptr)
3537  {
3538  const auto lc = tree_helper::get_integer_cst_value(l);
3539  const auto rc = tree_helper::get_integer_cst_value(r);
3540  RangeRef lhs(new Range(Regular, Range::max_digits, lc, lc));
3541  RangeRef rhs(new Range(Regular, Range::max_digits, rc, rc));
3542  const auto branchValue = BinaryOpNode::evaluate(bin_op->get_kind(), 1, lhs, rhs, isSignedType(bin_op->op0));
3543  THROW_ASSERT(branchValue->isConstant(), "Constant binary operation should resolve to either true or false");
3544  if(branchValue->getUnsignedMax())
3545  {
3547  "Branch condition " + STR(lc) + " " + bin_op->get_kind_text() + " " + STR(rc) + " == " +
3548  STR(branchValue) + ", false edge BB" + STR(branchBB->false_edge) + " to be removed");
3549  return branchBB->false_edge;
3550  }
3551  else
3552  {
3554  "Branch condition " + STR(lc) + " " + bin_op->get_kind_text() + " " + STR(rc) + " == " +
3555  STR(branchValue) + ", false edge BB" + STR(branchBB->false_edge) + " to be removed");
3556  return branchBB->true_edge;
3557  }
3558  }
3560  "Branch condition has non-integer cst_node operands, skipping...");
3561  return bloc::EXIT_BLOCK_ID;
3562  }
3563 
3564  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Branch variable is a non-integer cst_node, skipping...");
3565  return bloc::EXIT_BLOCK_ID;
3566 }
3567 
3568 // ========================================================================== //
3569 // TernaryOp
3570 // ========================================================================== //
3571 class TernaryOpNode : public OpNode
3572 {
3573  private:
3574  // The first operand.
3576  // The second operand.
3578  // The third operand.
3580  // The opcode of the operation.
3584  RangeRef eval() const override;
3585 
3586  public:
3587  TernaryOpNode(const ValueRangeRef& intersect, VarNode* sink, const tree_nodeConstRef& inst, VarNode* source1,
3588  VarNode* source2, VarNode* source3, kind opcode);
3589  ~TernaryOpNode() override = default;
3590  TernaryOpNode(const TernaryOpNode&) = delete;
3591  TernaryOpNode(TernaryOpNode&&) = delete;
3592  TernaryOpNode& operator=(const TernaryOpNode&) = delete;
3593  TernaryOpNode& operator=(TernaryOpNode&&) = delete;
3594 
3595  // Methods for RTTI
3596  OperationId getValueId() const override
3597  {
3598  return OperationId::TernaryOpId;
3599  }
3600  static bool classof(TernaryOpNode const* /*unused*/)
3601  {
3602  return true;
3603  }
3604  static bool classof(OpNode const* BO)
3605  {
3606  return BO->getValueId() == OperationId::TernaryOpId;
3607  }
3608 
3610  kind getOpcode() const
3611  {
3612  return opcode;
3613  }
3616  {
3617  return source1;
3618  }
3621  {
3622  return source2;
3623  }
3626  {
3627  return source3;
3628  }
3629  std::vector<tree_nodeConstRef> getSources() const override
3630  {
3631  return {source1->getValue(), source2->getValue(), source3->getValue()};
3632  }
3633 
3634  void print(std::ostream& OS) const override;
3635  void printDot(std::ostream& OS) const override;
3636 
3637  static std::function<OpNode*(NodeContainer*)> opCtorGenerator(const tree_nodeConstRef&, unsigned int,
3638  const FunctionBehaviorConstRef&,
3639  const tree_managerConstRef&,
3640  const application_managerRef&);
3641 };
3642 
3643 // The ctor.
3644 TernaryOpNode::TernaryOpNode(const ValueRangeRef& _intersect, VarNode* _sink, const tree_nodeConstRef& _inst,
3645  VarNode* _source1, VarNode* _source2, VarNode* _source3, kind _opcode)
3646  : OpNode(_intersect, _sink, _inst), source1(_source1), source2(_source2), source3(_source3), opcode(_opcode)
3647 {
3648 #if HAVE_ASSERTS
3649  const auto* ga = GetPointer<const gimple_assign>(GET_CONST_NODE(_inst));
3650  THROW_ASSERT(ga, "TernaryOp associated statement should be a gimple_assign " + GET_CONST_NODE(_inst)->ToString());
3651  const auto* I = GetPointer<const ternary_expr>(GET_CONST_NODE(ga->op1));
3652  THROW_ASSERT(I, "TernaryOp operator should be a ternary_expr");
3653  THROW_ASSERT(_sink->getBitWidth() >= _source2->getBitWidth(), STR("Operator bitwidth overflow ") + ga->ToString() +
3654  " (sink= " + STR(+_sink->getBitWidth()) +
3655  ", op2= " + STR(+_source2->getBitWidth()) + ")");
3656  THROW_ASSERT(_sink->getBitWidth() >= _source3->getBitWidth(), STR("Operator bitwidth overflow ") + ga->ToString() +
3657  " (sink= " + STR(+_sink->getBitWidth()) +
3658  ", op3= " + STR(+_source3->getBitWidth()) + ")");
3659 #endif
3660 }
3661 
3662 RangeRef TernaryOpNode::eval() const
3663 {
3664  const auto op1 = this->getSource1()->getRange();
3665  auto op2 = this->getSource2()->getRange();
3666  auto op3 = this->getSource3()->getRange();
3667 
3668  auto result = getRangeFor(getSink()->getValue(), Regular);
3669 
3671 
3672 #ifndef NDEBUG
3673  if(enable_ternary)
3674  {
3675  // #endif
3676  // only evaluate if all operands are Regular
3677  if((op1->isRegular() || op1->isAnti()) && (op2->isRegular() || op2->isAnti()) &&
3678  (op3->isRegular() || op3->isAnti()))
3679  {
3680  if(this->getOpcode() == cond_expr_K)
3681  {
3682  // Source1 is the selector
3683  if(op1->isSameRange(RangeRef(new Range(Regular, op1->getBitWidth(), 1, 1))))
3684  {
3685  result = RangeRef(op2->clone());
3686  }
3687  else if(op1->isSameRange(RangeRef(new Range(Regular, op1->getBitWidth(), 0, 0))))
3688  {
3689  result = RangeRef(op3->clone());
3690  }
3691  else
3692  {
3693  const auto* ga = GetPointer<const gimple_assign>(GET_CONST_NODE(getInstruction()));
3694  const auto* I = GetPointer<const ternary_expr>(GET_CONST_NODE(ga->op1));
3695  const auto BranchVar = branchOpRecurse(I->op0);
3696  std::vector<const struct binary_expr*> BranchConds;
3697  // Check if branch variable is correlated with op1 or op2
3698  if(GetPointer<const gimple_phi>(BranchVar) != nullptr)
3699  {
3700  // TODO: find a way to propagate range from all phi edges when phi->res is one of the two result of
3701  // the cond_expr
3702  }
3703  else if(const auto* BranchExpr = GetPointer<const binary_expr>(BranchVar))
3704  {
3705  BranchConds.push_back(BranchExpr);
3706  }
3707 
3708  for(const auto* be : BranchConds)
3709  {
3710  if(isCompare(be))
3711  {
3712  const auto& CondOp0 = be->op0;
3713  const auto& CondOp1 = be->op1;
3714  if(GET_CONST_NODE(CondOp0)->get_kind() == integer_cst_K ||
3715  GET_CONST_NODE(CondOp1)->get_kind() == integer_cst_K)
3716  {
3717  const auto& variable = GET_CONST_NODE(CondOp0)->get_kind() == integer_cst_K ? CondOp1 : CondOp0;
3718  const auto& constant = GET_CONST_NODE(CondOp0)->get_kind() == integer_cst_K ? CondOp0 : CondOp1;
3719  const auto& opV1 = I->op1;
3720  const auto& opV2 = I->op2;
3721  if(GET_INDEX_CONST_NODE(variable) == GET_INDEX_CONST_NODE(opV1) ||
3722  GET_INDEX_CONST_NODE(variable) == GET_INDEX_CONST_NODE(opV2))
3723  {
3724  const auto CR = getGIMPLE_range(constant);
3725  THROW_ASSERT(CR->isConstant(), "Range from constant should be constant (" +
3726  GET_CONST_NODE(constant)->ToString() + " => " +
3727  CR->ToString() + ")");
3728  kind pred = isSignedType(CondOp0) ? be->get_kind() : op_unsigned(be->get_kind());
3729  kind swappred = op_swap(pred);
3730 
3731  auto tmpT = (variable == CondOp0) ? Range::makeSatisfyingCmpRegion(pred, CR) :
3732  Range::makeSatisfyingCmpRegion(swappred, CR);
3733  THROW_ASSERT(!tmpT->isFullSet(), "");
3734 
3735  if(GET_INDEX_CONST_NODE(variable) == GET_INDEX_CONST_NODE(opV2))
3736  {
3737  RangeRef FValues(new Range(*tmpT->getAnti()));
3738  op3 = op3->intersectWith(FValues);
3739  }
3740  else
3741  {
3742  op2 = op2->intersectWith(tmpT);
3743  }
3744  }
3745  }
3746  }
3747  }
3748  result = op2->unionWith(op3);
3749  }
3750  }
3751  }
3752  else
3753  {
3754  if(op1->isEmpty() || op2->isEmpty() || op3->isEmpty())
3755  {
3756  result = getRangeFor(getSink()->getValue(), Empty);
3757  }
3758  }
3759  // #ifndef NDEBUG
3760  }
3761 #endif
3763  "---" + result->ToString() + " = " + op1->ToString() + " ? " + op2->ToString() + " : " +
3764  op3->ToString());
3765 
3766  bool test = this->getIntersect()->getRange()->isFullSet();
3767  if(!test)
3768  {
3769  const auto aux = this->getIntersect()->getRange();
3770  auto _intersect = result->intersectWith(aux);
3771  if(!_intersect->isEmpty())
3772  {
3774  "---aux = " + aux->ToString() + " from " + getIntersect()->ToString());
3775  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---result = " + _intersect->ToString());
3776  result = _intersect;
3777  }
3778  }
3779  return result;
3780 }
3781 
3782 std::function<OpNode*(NodeContainer*)>
3783 TernaryOpNode::opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int function_id, const FunctionBehaviorConstRef&,
3785 {
3786  const auto* assign = GetPointer<const gimple_assign>(GET_CONST_NODE(stmt));
3787  if(assign == nullptr)
3788  {
3789  return nullptr;
3790  }
3791  const auto* ter_op = GetPointer<const ternary_expr>(GET_CONST_NODE(assign->op1));
3792  if(ter_op == nullptr)
3793  {
3794  return nullptr;
3795  }
3796  return [stmt, assign, ter_op, function_id](NodeContainer* NC) {
3797  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
3798  "Analysing ternary operation " + ter_op->get_kind_text() + " " + assign->ToString());
3799  // Create the sink.
3800  VarNode* sink = NC->addVarNode(assign->op0, function_id);
3801 
3802  // Create the sources.
3803  VarNode* _source1 = NC->addVarNode(ter_op->op0, function_id);
3804  VarNode* _source2 = NC->addVarNode(ter_op->op1, function_id);
3805  VarNode* _source3 = NC->addVarNode(ter_op->op2, function_id);
3806 
3807  // Create the operation using the intersect to constrain sink's interval.
3808  auto BI = ValueRangeRef(new ValueRange(getGIMPLE_range(stmt)));
3809  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
3810  "---Added TernaryOp for " + ter_op->get_kind_text() + " with range " + BI->ToString());
3811  return new TernaryOpNode(BI, sink, stmt, _source1, _source2, _source3, ter_op->get_kind());
3812  };
3813 }
3814 
3815 void TernaryOpNode::print(std::ostream& OS) const
3816 {
3817  OS << GET_CONST_NODE(getSink()->getValue())->ToString() << " = "
3818  << GET_CONST_NODE(getSource1()->getValue())->ToString() << " ? "
3819  << GET_CONST_NODE(getSource2()->getValue())->ToString() << " : "
3820  << GET_CONST_NODE(getSource3()->getValue())->ToString();
3821 }
3822 
3823 void TernaryOpNode::printDot(std::ostream& OS) const
3824 {
3825  const char* quot = R"(")";
3826  std::string opcodeName = tree_node::GetString(this->getOpcode());
3827  OS << " " << quot << this << quot << R"( [label=")" << opcodeName << "\"]\n";
3828 
3829  const auto& V1 = this->getSource1()->getValue();
3830  if(GET_CONST_NODE(V1)->get_kind() == integer_cst_K)
3831  {
3832  OS << " " << tree_helper::GetConstValue(V1) << " -> " << quot << this << quot << "\n";
3833  }
3834  else
3835  {
3836  OS << " " << quot;
3837  printVarName(V1, OS);
3838  OS << quot << " -> " << quot << this << quot << "\n";
3839  }
3840  const auto& V2 = this->getSource2()->getValue();
3841  if(GET_CONST_NODE(V2)->get_kind() == integer_cst_K)
3842  {
3843  OS << " " << tree_helper::GetConstValue(V2) << " -> " << quot << this << quot << "\n";
3844  }
3845  else
3846  {
3847  OS << " " << quot;
3848  printVarName(V2, OS);
3849  OS << quot << " -> " << quot << this << quot << "\n";
3850  }
3851 
3852  const auto& V3 = this->getSource3()->getValue();
3853  if(GET_CONST_NODE(V3)->get_kind() == integer_cst_K)
3854  {
3855  OS << " " << tree_helper::GetConstValue(V3) << " -> " << quot << this << quot << "\n";
3856  }
3857  else
3858  {
3859  OS << " " << quot;
3860  printVarName(V3, OS);
3861  OS << quot << " -> " << quot << this << quot << "\n";
3862  }
3863  const auto& VS = this->getSink()->getValue();
3864  OS << " " << quot << this << quot << " -> " << quot;
3865  printVarName(VS, OS);
3866  OS << quot << "\n";
3867 }
3868 
3869 // ========================================================================== //
3870 // LoadOp
3871 // ========================================================================== //
3872 class LoadOpNode : public OpNode
3873 {
3874  private:
3876  std::vector<const VarNode*> sources;
3877  RangeRef eval() const override;
3878 
3879  public:
3880  LoadOpNode(const ValueRangeRef& intersect, VarNode* sink, const tree_nodeConstRef& inst);
3881  ~LoadOpNode() override = default;
3882  LoadOpNode(const LoadOpNode&) = delete;
3883  LoadOpNode(LoadOpNode&&) = delete;
3884  LoadOpNode& operator=(const LoadOpNode&) = delete;
3885  LoadOpNode& operator=(LoadOpNode&&) = delete;
3886 
3887  // Methods for RTTI
3888  OperationId getValueId() const override
3889  {
3890  return OperationId::LoadOpId;
3891  }
3892  static bool classof(LoadOpNode const* /*unused*/)
3893  {
3894  return true;
3895  }
3896  static bool classof(OpNode const* BO)
3897  {
3898  return BO->getValueId() == OperationId::LoadOpId;
3899  }
3900 
3902  void addSource(const VarNode* newsrc)
3903  {
3904  sources.push_back(newsrc);
3905  }
3907  const VarNode* getSource(size_t index) const
3908  {
3909  return sources[index];
3910  }
3912  size_t getNumSources() const
3913  {
3914  return sources.size();
3915  }
3916  std::vector<tree_nodeConstRef> getSources() const override
3917  {
3918  std::vector<tree_nodeConstRef> sourceTNs;
3919  for(const auto& s : sources)
3920  {
3921  sourceTNs.push_back(s->getValue());
3922  }
3923  return sourceTNs;
3924  }
3925 
3926  void print(std::ostream& OS) const override;
3927  void printDot(std::ostream& OS) const override;
3928 
3929  static std::function<OpNode*(NodeContainer*)>
3930  opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int function_id, const FunctionBehaviorConstRef& FB,
3931  const tree_managerConstRef& TM, const application_managerRef& AppM);
3932 };
3933 
3934 LoadOpNode::LoadOpNode(const ValueRangeRef& _intersect, VarNode* _sink, const tree_nodeConstRef& _inst)
3935  : OpNode(_intersect, _sink, _inst)
3936 {
3937 }
3938 
3939 RangeRef LoadOpNode::eval() const
3940 {
3942 
3943 #ifndef NDEBUG
3944  if(getNumSources() == 0 || !enable_load)
3945 #else
3946  if(getNumSources() == 0)
3947 #endif
3948  {
3949  THROW_ASSERT(getSink()->getBitWidth() == getIntersect()->getRange()->getBitWidth(),
3950  "Sink (" + GET_CONST_NODE(getSink()->getValue())->ToString() + ") has bitwidth " +
3951  STR(getSink()->getBitWidth()) + " while intersect has bitwidth " +
3952  STR(getIntersect()->getRange()->getBitWidth()));
3954  return RangeRef(getIntersect()->getRange()->clone());
3955  }
3956 
3957  // Iterate over the sources of the load
3958  auto result = getRangeFor(getSink()->getValue(), Empty);
3960  for(const VarNode* varNode : sources)
3961  {
3963  " ->" + varNode->getRange()->ToString() + " " + varNode->ToString());
3964  result = result->unionWith(varNode->getRange());
3965  }
3966  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<-- = " + result->ToString());
3967 
3968  bool test = this->getIntersect()->getRange()->isFullSet();
3969  if(!test)
3970  {
3971  const auto aux = this->getIntersect()->getRange();
3972  auto _intersect = result->intersectWith(aux);
3973  if(!_intersect->isEmpty())
3974  {
3976  "---aux = " + aux->ToString() + " from " + getIntersect()->ToString());
3977  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---result = " + _intersect->ToString());
3978  result = _intersect;
3979  }
3980  }
3981  return result;
3982 }
3983 
3984 static RangeRef constructor_range(const tree_managerConstRef TM, const tree_nodeConstRef tn, const RangeConstRef init)
3985 {
3986  THROW_ASSERT(tn->get_kind() == constructor_K, "tn is not constructor node");
3987  const auto* c = GetPointer<const constructor>(tn);
3988  std::vector<unsigned long long> array_dims;
3989  unsigned long long elements_bitsize;
3990  tree_helper::get_array_dim_and_bitsize(TM, GET_INDEX_CONST_NODE(c->type), array_dims, elements_bitsize);
3991  unsigned int initialized_elements = 0;
3992  auto ctor_range = RangeRef(init->clone());
3993  for(const auto& i : c->list_of_idx_valu)
3994  {
3995  const auto el = GET_CONST_NODE(i.second);
3996  THROW_ASSERT(el, "unexpected condition");
3997 
3998  if(el->get_kind() == constructor_K && tree_helper::IsArrayEquivType(GetPointerS<const constructor>(el)->type))
3999  {
4000  THROW_ASSERT(array_dims.size() > 1 || GET_CONST_NODE(c->type)->get_kind() == record_type_K,
4001  "invalid nested constructors:" + tn->ToString() + " " + STR(array_dims.size()));
4002  ctor_range = ctor_range->unionWith(constructor_range(TM, el, ctor_range));
4003  }
4004  else
4005  {
4006  const auto init_range = getGIMPLE_range(el);
4007  if(init_range->getBitWidth() > static_cast<Range::bw_t>(elements_bitsize))
4008  {
4009  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4010  "---Initializer value not compliant " + el->ToString());
4011  }
4012  else
4013  {
4014  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4015  "---Initializer value is " + el->ToString());
4016  ctor_range = ctor_range->unionWith(init_range);
4017  }
4018  }
4019  initialized_elements++;
4020  }
4021  if(initialized_elements < array_dims.front())
4022  {
4023  ctor_range =
4024  ctor_range->unionWith(RangeRef(new Range(Regular, static_cast<Range::bw_t>(elements_bitsize), 0, 0)));
4025  }
4026  return ctor_range;
4027 }
4028 
4029 std::function<OpNode*(NodeContainer*)>
4030 LoadOpNode::opCtorGenerator(const tree_nodeConstRef& stmt, unsigned int function_id, const FunctionBehaviorConstRef& FB,
4031  const tree_managerConstRef& TM, const application_managerRef& AppM)
4032 {
4033  const auto* ga = GetPointer<const gimple_assign>(GET_CONST_NODE(stmt));
4034  if(ga == nullptr)
4035  {
4036  return nullptr;
4037  }
4038  if(!tree_helper::IsLoad(stmt, FB->get_function_mem()))
4039  {
4040  return nullptr;
4041  }
4042  return [stmt, ga, function_id, FB, TM, AppM](NodeContainer* NC) {
4043  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4044  "Analysing load operation " + ga->ToString());
4045  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level, "-->");
4046  const auto bw = getGIMPLE_BW(ga->op0);
4047  VarNode* sink = NC->addVarNode(ga->op0, function_id);
4048  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4049  "Sink variable is " + GET_CONST_NODE(ga->op0)->get_kind_text() + " (size = " + STR(bw) + ")");
4050 
4051  auto intersection = getRangeFor(sink->getValue(), Empty);
4052  if(GET_NODE(ga->op1)->get_kind() == array_ref_K || GET_NODE(ga->op1)->get_kind() == mem_ref_K ||
4053  GET_NODE(ga->op1)->get_kind() == target_mem_ref_K || GET_NODE(ga->op1)->get_kind() == target_mem_ref461_K ||
4054  GET_NODE(ga->op1)->get_kind() == var_decl_K)
4055  {
4056  auto base_index = tree_helper::get_base_index(TM, GET_INDEX_NODE(ga->op1));
4057  const auto* hm = GetPointer<HLS_manager>(AppM);
4058  if(base_index && AppM->get_written_objects().find(base_index) == AppM->get_written_objects().end() && hm &&
4059  hm->Rmem && FB->is_variable_mem(base_index) && hm->Rmem->is_sds_var(base_index))
4060  {
4061  const auto* vd = GetPointer<const var_decl>(TM->get_tree_node_const(base_index));
4062  if(vd && vd->init)
4063  {
4064  if(GET_NODE(vd->init)->get_kind() == constructor_K)
4065  {
4066  intersection = constructor_range(TM, GET_CONST_NODE(vd->init), intersection);
4067  }
4068  else if(GetPointer<const cst_node>(GET_CONST_NODE(vd->init)))
4069  {
4070  auto init_range = getGIMPLE_range(GET_NODE(vd->init));
4071  if(init_range->getBitWidth() != bw)
4072  {
4073  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4074  "---Initializer value not compliant " + GET_NODE(vd->init)->ToString());
4075  }
4076  else
4077  {
4078  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4079  "---Initializer value is " + GET_NODE(vd->init)->ToString());
4080  intersection = init_range;
4081  }
4082  }
4083  }
4084  }
4085  if(base_index && AppM->get_written_objects().find(base_index) != AppM->get_written_objects().end() && hm &&
4086  hm->Rmem && hm->Rmem->get_enable_hls_bit_value() && FB->is_variable_mem(base_index) &&
4087  hm->Rmem->is_private_memory(base_index) && hm->Rmem->is_sds_var(base_index))
4088  {
4089  const auto* vd = GetPointer<const var_decl>(TM->get_tree_node_const(base_index));
4090  if(vd && vd->init)
4091  {
4092  if(GET_NODE(vd->init)->get_kind() == constructor_K)
4093  {
4094  intersection = constructor_range(TM, GET_CONST_NODE(vd->init), intersection);
4095  }
4096  else if(GetPointer<const cst_node>(GET_CONST_NODE(vd->init)))
4097  {
4098  auto init_range = getGIMPLE_range(GET_CONST_NODE(vd->init));
4099  if(init_range->getBitWidth() != bw)
4100  {
4101  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4102  "---Initializer value not compliant " + GET_NODE(vd->init)->ToString());
4103  }
4104  else
4105  {
4106  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4107  "---Initializer value is " + GET_NODE(vd->init)->ToString());
4108  intersection = init_range;
4109  }
4110  }
4111  }
4112  else
4113  {
4114  intersection = RangeRef(new Range(Regular, bw, 0, 0));
4115  }
4116  for(const auto& cur_var : hm->Rmem->get_source_values(base_index))
4117  {
4118  const auto cur_node = TM->get_tree_node_const(cur_var);
4119  THROW_ASSERT(cur_node, "");
4120  auto init_range = getGIMPLE_range(cur_node);
4121  if(init_range->getBitWidth() != bw)
4122  {
4123  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4124  "---Initializer value not compliant " + cur_node->ToString());
4125  }
4126  else
4127  {
4128  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4129  "---Initializer value is " + cur_node->ToString());
4130  intersection = intersection->unionWith(init_range);
4131  }
4132  }
4133  }
4134  }
4135  if(intersection->isEmpty())
4136  {
4137  intersection = getGIMPLE_range(stmt);
4138  }
4139  THROW_ASSERT(intersection->getBitWidth() <= bw,
4140  "Pointed variables range should have bitwidth contained in sink bitwidth");
4141  THROW_ASSERT(!intersection->isEmpty(), "Variable range should not be empty");
4142  if(intersection->getBitWidth() < bw)
4143  {
4144  intersection = intersection->zextOrTrunc(bw);
4145  }
4146  auto BI = ValueRangeRef(new ValueRange(intersection));
4147 #ifndef NDEBUG
4148  if(!enable_load)
4149  {
4150  BI = ValueRangeRef(new ValueRange(getGIMPLE_range(stmt)));
4151  }
4152 #endif
4153  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, NodeContainer::debug_level,
4154  "<--Added LoadOp with range " + BI->ToString());
4155  return new LoadOpNode(BI, sink, stmt);
4156  };
4157 }
4158 
4159 void LoadOpNode::print(std::ostream& OS) const
4160 {
4161  OS << GET_CONST_NODE(getSink()->getValue())->ToString() << " = LOAD()";
4162 }
4163 
4164 void LoadOpNode::printDot(std::ostream& OS) const
4165 {
4166  const char* quot = R"(")";
4167  OS << " " << quot << this << quot << R"( [label=")";
4168  OS << "LoadOp\"]\n";
4169 
4170  for(auto src : sources)
4171  {
4172  const auto& V = src->getValue();
4173  if(GET_CONST_NODE(V)->get_kind() == integer_cst_K)
4174  {
4175  OS << " " << tree_helper::GetConstValue(V) << " -> " << quot << this << quot << "\n";
4176  }
4177  else
4178  {
4179  OS << " " << quot;
4180  printVarName(V, OS);
4181  OS << quot << " -> " << quot << this << quot << "\n";
4182  }
4183  }
4184 
4185  const auto& VS = this->getSink()->getValue();
4186  OS << " " << quot << this << quot << " -> " << quot;
4187  printVarName(VS, OS);
4188  OS << quot << "\n";
4189 }
4190 
4191 const std::vector<std::function<std::function<OpNode*(NodeContainer*)>(
4192  const tree_nodeConstRef&, unsigned int, const FunctionBehaviorConstRef&, const tree_managerConstRef&,
4193  const application_managerRef&)>>
4197 
4198 // ========================================================================== //
4199 // ControlDep
4200 // ========================================================================== //
4203 class ControlDepNode : public OpNode
4204 {
4205  private:
4207  RangeRef eval() const override;
4208 
4209  public:
4210  ControlDepNode(VarNode* sink, VarNode* source);
4211  ~ControlDepNode() override = default;
4212  ControlDepNode(const ControlDepNode&) = delete;
4213  ControlDepNode(ControlDepNode&&) = delete;
4214  ControlDepNode& operator=(const ControlDepNode&) = delete;
4216 
4217  // Methods for RTTI
4218  OperationId getValueId() const override
4219  {
4221  }
4222  static bool classof(ControlDepNode const* /*unused*/)
4223  {
4224  return true;
4225  }
4226  static bool classof(OpNode const* BO)
4227  {
4228  return BO->getValueId() == OperationId::ControlDepId;
4229  }
4230 
4233  {
4234  return source;
4235  }
4236  std::vector<tree_nodeConstRef> getSources() const override
4237  {
4238  return {source->getValue()};
4239  }
4240 
4241  void print(std::ostream& OS) const override;
4242  void printDot(std::ostream& OS) const override;
4243 };
4244 
4246  : OpNode(ValueRangeRef(new ValueRange(_sink->getMaxRange())), _sink, nullptr), source(_source)
4247 {
4248 }
4249 
4250 RangeRef ControlDepNode::eval() const
4251 {
4252  return RangeRef(new Range(Regular, Range::max_digits));
4253 }
4254 
4255 void ControlDepNode::print(std::ostream& /*OS*/) const
4256 {
4257 }
4258 
4259 void ControlDepNode::printDot(std::ostream& /*OS*/) const
4260 {
4261 }
4262 
4263 // ========================================================================== //
4264 // Nuutila
4265 // ========================================================================== //
4266 
4267 // A map from variables to the operations where these
4268 // variables are present as bounds
4269 using SymbMap = std::map<tree_nodeConstRef, CustomSet<OpNode*>, tree_reindexCompare>;
4270 
4271 class Nuutila
4272 {
4273 #ifndef NDEBUG
4275 #ifdef SCC_DEBUG
4276  bool checkWorklist() const;
4277  bool checkComponents() const;
4278  bool checkTopologicalSort(const UseMap& useMap) const;
4279  bool hasEdge(const CustomSet<VarNode*>& componentFrom, const CustomSet<VarNode*>& componentTo,
4280  const UseMap& useMap) const;
4281 #endif
4282 #endif
4283 
4285  int index;
4286  std::map<tree_nodeConstRef, int, tree_reindexCompare> dfs;
4287  std::map<tree_nodeConstRef, tree_nodeConstRef, tree_reindexCompare> root;
4288  std::set<tree_nodeConstRef, tree_reindexCompare> inComponent;
4289  std::map<tree_nodeConstRef, CustomSet<VarNode*>, tree_reindexCompare> components;
4290  std::deque<tree_nodeConstRef> worklist;
4291 
4292  public:
4293  Nuutila(const VarNodes& varNodes, UseMap& useMap, const SymbMap& symbMap
4294 #ifndef NDEBUG
4295  ,
4296  int _debug_level
4297 #endif
4298  );
4299  ~Nuutila() = default;
4300  Nuutila(const Nuutila&) = delete;
4301  Nuutila(Nuutila&&) = delete;
4302  Nuutila& operator=(const Nuutila&) = delete;
4303  Nuutila& operator=(Nuutila&&) = delete;
4304 
4305  void addControlDependenceEdges(UseMap& useMap, const SymbMap& symbMap, const VarNodes& vars);
4306  void delControlDependenceEdges(UseMap& useMap);
4307  void visit(const tree_nodeConstRef& V, std::stack<tree_nodeConstRef>& stack, const UseMap& useMap);
4308 
4309  const CustomSet<VarNode*>& getComponent(const tree_nodeConstRef& n) const
4310  {
4311  THROW_ASSERT(static_cast<bool>(components.count(n)),
4312  "Required component not found (" + GET_CONST_NODE(n)->ToString() + ")");
4313  return components.at(n);
4314  }
4315 
4316  using iterator = std::deque<tree_nodeConstRef>::reverse_iterator;
4317  using const_iterator = std::deque<tree_nodeConstRef>::const_reverse_iterator;
4319  {
4320  return worklist.rbegin();
4321  }
4323  {
4324  return worklist.crbegin();
4325  }
4327  {
4328  return worklist.rend();
4329  }
4331  {
4332  return worklist.crend();
4333  }
4334 };
4335 
4336 /*
4337  * Finds the strongly connected components in the constraint graph formed
4338  * by Variables and UseMap. The class receives the map of futures to insert
4339  * the control dependence edges in the constraint graph. These edges are removed
4340  * after the class is done computing the SCCs.
4341  */
4342 Nuutila::Nuutila(const VarNodes& varNodes, UseMap& useMap, const SymbMap& symbMap
4343 #ifndef NDEBUG
4344  ,
4345  int _debug_level)
4346  : debug_level(_debug_level),
4347 #else
4348  )
4349  :
4350 #endif
4351  variables(varNodes)
4352 {
4353  // Copy structures
4354  this->index = 0;
4355 
4356  // Iterate over all varnodes of the constraint graph
4357  for(const auto& vNode : varNodes)
4358  {
4359  // Initialize DFS control variable for each Value in the graph
4360  dfs[vNode.first] = -1;
4361  }
4362  addControlDependenceEdges(useMap, symbMap, varNodes);
4363  // Iterate again over all varnodes of the constraint graph
4364  for(const auto& vNode : varNodes)
4365  {
4366  // If the Value has not been visited yet, call visit for him
4367  if(dfs[vNode.first] < 0)
4368  {
4370  "Start visit from " + GET_CONST_NODE(vNode.first)->ToString());
4371  std::stack<tree_nodeConstRef> pilha;
4373  visit(vNode.first, pilha, useMap);
4375  }
4376  }
4377  delControlDependenceEdges(useMap);
4378 
4379 #ifdef SCC_DEBUG
4380  THROW_ASSERT(checkWorklist(), "An inconsistency in SCC worklist have been found");
4381  THROW_ASSERT(checkComponents(), "A component has been used more than once");
4382  THROW_ASSERT(checkTopologicalSort(useMap), "Topological sort is incorrect");
4383 #endif
4384 }
4385 
4386 /*
4387  * Adds the edges that ensure that we solve a future before fixing its
4388  * interval. I have created a new class: ControlDep edges, to represent
4389  * the control dependencies. In this way, in order to delete these edges,
4390  * one just need to go over the map of uses removing every instance of the
4391  * ControlDep class.
4392  */
4393 void Nuutila::addControlDependenceEdges(UseMap& useMap, const SymbMap& symbMap, const VarNodes& vars)
4394 {
4395  for(const auto& varOps : symbMap)
4396  {
4397  for(const auto& op : varOps.second)
4398  {
4399  THROW_ASSERT(static_cast<bool>(vars.count(varOps.first)), "Variable should be stored in VarNodes map");
4400  auto* source = vars.at(varOps.first);
4401  auto* cdedge = new ControlDepNode(op->getSink(), source);
4402  useMap[varOps.first].insert(cdedge);
4403  }
4404  }
4405 }
4406 
4407 /*
4408  * Removes the control dependence edges from the constraint graph.
4409  */
4411 {
4412  for(auto& varOps : useMap)
4413  {
4414  std::deque<ControlDepNode*> cds;
4415  for(auto sit : varOps.second)
4416  {
4417  if(auto* cd = GetOp<ControlDepNode>(sit))
4418  {
4419  cds.push_back(cd);
4420  }
4421  }
4422 
4423  for(auto* cd : cds)
4424  {
4425 #ifndef NDEBUG
4426  // Add pseudo edge to the string
4427  const auto& V = cd->getSource()->getValue();
4428  if(GET_CONST_NODE(V)->get_kind() == integer_cst_K)
4429  {
4430  pseudoEdgesString << " " << tree_helper::GetConstValue(V) << " -> ";
4431  }
4432  else
4433  {
4434  pseudoEdgesString << " " << '"';
4435  printVarName(V, pseudoEdgesString);
4436  pseudoEdgesString << '"' << " -> ";
4437  }
4438  const auto& VS = cd->getSink()->getValue();
4439  pseudoEdgesString << '"';
4440  printVarName(VS, pseudoEdgesString);
4441  pseudoEdgesString << '"';
4442  pseudoEdgesString << " [style=dashed]\n";
4443 #endif
4444  // Remove pseudo edge from the map
4445  varOps.second.erase(cd);
4446  delete cd;
4447  }
4448  }
4449 }
4450 
4451 /*
4452  * Finds SCCs using Nuutila's algorithm. This algorithm is divided in
4453  * two parts. The first calls the recursive visit procedure on every node
4454  * in the constraint graph. The second phase revisits these nodes,
4455  * grouping them in components.
4456  */
4457 void Nuutila::visit(const tree_nodeConstRef& V, std::stack<tree_nodeConstRef>& stack, const UseMap& useMap)
4458 {
4459  dfs[V] = index;
4460  ++index;
4461  root[V] = V;
4462 
4463  // Visit every node defined in an instruction that uses V
4464  for(const auto& op : useMap.at(V))
4465  {
4467  const auto& sink = op->getSink()->getValue();
4468  if(dfs[sink] < 0)
4469  {
4471  visit(sink, stack, useMap);
4473  }
4474  if((!static_cast<bool>(inComponent.count(sink))) && (dfs[root[V]] >= dfs[root[sink]]))
4475  {
4476  root[V] = root[sink];
4477  }
4478  }
4479 
4480  // The second phase of the algorithm assigns components to stacked nodes
4482  {
4483  // Neither the worklist nor the map of components is part of Nuutila's
4484  // original algorithm. We are using these data structures to get a
4485  // topological ordering of the SCCs without having to go over the root
4486  // list once more.
4487  worklist.push_back(V);
4488  components[V].insert(variables.at(V));
4489  inComponent.insert(V);
4490  while(!stack.empty() && (dfs[stack.top()] > dfs[V]))
4491  {
4492  auto node = stack.top();
4493  stack.pop();
4494  inComponent.insert(node);
4495  components[V].insert(variables.at(node));
4496  }
4497  }
4498  else
4499  {
4500  stack.push(V);
4501  }
4502 }
4503 
4504 #ifdef SCC_DEBUG
4505 bool Nuutila::checkWorklist() const
4506 {
4507  bool consistent = true;
4508  for(auto nit = cbegin(), nend = cend(); nit != nend;)
4509  {
4510  auto v1 = *nit;
4511  for(const auto& v2 : boost::make_iterator_range(++nit, cend()))
4512  {
4514  {
4516  "[Nuutila::checkWorklist] Duplicated entry in worklist " + GET_CONST_NODE(v1)->ToString());
4517  consistent = false;
4518  }
4519  }
4520  }
4521  return consistent;
4522 }
4523 
4524 bool Nuutila::checkComponents() const
4525 {
4526  bool isConsistent = true;
4527  for(auto n1it = cbegin(), n1end = cend(); n1it != n1end;)
4528  {
4529  const auto& component1 = components.at(*n1it);
4530  for(const auto& n2 : boost::make_iterator_range(++n1it, cend()))
4531  {
4532  const auto& component2 = components.at(n2);
4533  if(&component1 == &component2)
4534  {
4536  "[Nuutila::checkComponent] Component [" + STR(&component1) + ", " + STR(component1.size()) +
4537  "]");
4538  isConsistent = false;
4539  }
4540  }
4541  }
4542  return isConsistent;
4543 }
4544 
4548 bool Nuutila::hasEdge(const CustomSet<VarNode*>& componentFrom, const CustomSet<VarNode*>& componentTo,
4549  const UseMap& useMap) const
4550 {
4551  for(const auto& v : componentFrom)
4552  {
4553  const auto& source = v->getValue();
4554  THROW_ASSERT(static_cast<bool>(useMap.count(source)), "Variable should be in use map");
4555  for(const auto& op : useMap.at(source))
4556  {
4557  if(static_cast<bool>(componentTo.count(op->getSink())))
4558  {
4559  return true;
4560  }
4561  }
4562  }
4563  return false;
4564 }
4565 
4566 bool Nuutila::checkTopologicalSort(const UseMap& useMap) const
4567 {
4568  bool isConsistent = true;
4569  for(auto n1it = cbegin(), nend = cend(); n1it != nend; ++n1it)
4570  {
4571  const auto& curr_component = components.at(*n1it);
4572  // check if this component points to another component that has already
4573  // been visited
4574  for(const auto& n2 : boost::make_iterator_range(cbegin(), n1it))
4575  {
4576  const auto& prev_component = components.at(n2);
4577  if(hasEdge(curr_component, prev_component, useMap))
4578  {
4579  isConsistent = false;
4580  }
4581  }
4582  }
4583  return isConsistent;
4584 }
4585 
4586 #endif
4587 
4588 // ========================================================================== //
4589 // Meet
4590 // ========================================================================== //
4591 class Meet
4592 {
4593  private:
4594  static const APInt& getFirstGreaterFromVector(const std::vector<APInt>& constantvector, const APInt& val);
4595  static const APInt& getFirstLessFromVector(const std::vector<APInt>& constantvector, const APInt& val);
4596 
4597  public:
4598  static bool widen(OpNode* op, const std::vector<APInt>& constantvector);
4599  static bool narrow(OpNode* op, const std::vector<APInt>& constantvector);
4600  static bool crop(OpNode* op);
4601  static bool growth(OpNode* op);
4602  static bool fixed(OpNode* op);
4603 
4604 #ifndef NDEBUG
4605  static int debug_level;
4606 #endif
4607 };
4608 
4609 #ifndef NDEBUG
4611 #endif
4612 
4613 /*
4614  * Get the first constant from vector greater than val
4615  */
4616 const APInt& Meet::getFirstGreaterFromVector(const std::vector<APInt>& constantvector, const APInt& val)
4617 {
4618  for(const auto& vapint : constantvector)
4619  {
4620  if(vapint >= val)
4621  {
4622  return vapint;
4623  }
4624  }
4625  return Range::Max;
4626 }
4627 
4628 /*
4629  * Get the first constant from vector less than val
4630  */
4631 const APInt& Meet::getFirstLessFromVector(const std::vector<APInt>& constantvector, const APInt& val)
4632 {
4633  for(auto vit = constantvector.rbegin(), vend = constantvector.rend(); vit != vend; ++vit)
4634  {
4635  const auto& vapint = *vit;
4636  if(vapint <= val)
4637  {
4638  return vapint;
4639  }
4640  }
4641  return Range::Min;
4642 }
4643 
4645 {
4646  const auto oldInterval = op->getSink()->getRange();
4647  const auto newInterval = op->eval();
4648 
4649  op->getSink()->setRange(newInterval);
4650  if(op->getInstruction())
4651  {
4653  "FIXED::@" + STR(GET_INDEX_CONST_NODE(op->getInstruction())) + ": " + oldInterval->ToString() +
4654  " -> " + newInterval->ToString());
4655  }
4656  else
4657  {
4659  "FIXED::%artificial phi : " + oldInterval->ToString() + " -> " + newInterval->ToString());
4660  }
4661  return !oldInterval->isSameRange(newInterval);
4662 }
4663 
4670 bool Meet::widen(OpNode* op, const std::vector<APInt>& constantvector)
4671 {
4672  const auto oldRange = op->getSink()->getRange();
4673  const auto newRange = op->eval();
4674 
4675  auto intervalWiden = [&](RangeConstRef oldInterval, RangeConstRef newInterval) {
4676  const auto bw = oldInterval->getBitWidth();
4677  if(oldInterval->isUnknown() || oldInterval->isEmpty() || oldInterval->isAnti() || newInterval->isEmpty() ||
4678  newInterval->isAnti())
4679  {
4680  if(oldInterval->isAnti() && newInterval->isAnti() && !newInterval->isSameRange(oldInterval))
4681  {
4682  const auto oldAnti = oldInterval->getAnti();
4683  const auto newAnti = newInterval->getAnti();
4684  const auto& oldLower = oldAnti->getLower();
4685  const auto& oldUpper = oldAnti->getUpper();
4686  const auto& newLower = newAnti->getLower();
4687  const auto& newUpper = newAnti->getUpper();
4688  const auto& nlconstant = getFirstGreaterFromVector(constantvector, newLower);
4689  const auto& nuconstant = getFirstLessFromVector(constantvector, newUpper);
4690 
4691  if(newLower > oldLower || newUpper < oldUpper)
4692  {
4693  const auto& l = newLower > oldLower ? nlconstant : oldLower;
4694  const auto& u = newUpper < oldUpper ? nuconstant : oldUpper;
4695  if(l > u)
4696  {
4697  return RangeRef(new Range(Regular, bw));
4698  }
4699  return RangeRef(new Range(Anti, bw, l, u));
4700  }
4701  }
4702  else
4703  {
4704  // Sometimes sigma operation could cause confusion after maximum widening has been reached and generate
4705  // loops
4706  if(!oldInterval->isUnknown() && oldInterval->isFullSet() && newInterval->isAnti())
4707  {
4708  return RangeRef(oldInterval->clone());
4709  }
4710  if(oldInterval->isRegular() && newInterval->isAnti())
4711  {
4712  return oldInterval->unionWith(newInterval);
4713  }
4714  return RangeRef(newInterval->clone());
4715  }
4716  }
4717  else
4718  {
4719  const auto& oldLower = oldInterval->getLower();
4720  const auto& oldUpper = oldInterval->getUpper();
4721  const auto& newLower = newInterval->getLower();
4722  const auto& newUpper = newInterval->getUpper();
4723 
4724  // Jump-set
4725  const auto& nlconstant = getFirstLessFromVector(constantvector, newLower);
4726  const auto& nuconstant = getFirstGreaterFromVector(constantvector, newUpper);
4727 
4728  if(newLower < oldLower || newUpper > oldUpper)
4729  {
4730  return RangeRef(new Range(Regular, bw, newLower < oldLower ? nlconstant : oldLower,
4731  newUpper > oldUpper ? nuconstant : oldUpper));
4732  }
4733  }
4734  // THROW_UNREACHABLE("Meet::widen unreachable state");
4735  return RangeRef(oldInterval->clone());
4736  };
4737 
4738  const auto widen = intervalWiden(oldRange, newRange);
4739  // THROW_ASSERT(oldRange->getSpan() <= widen->getSpan(), "Widening should produce bigger range: " +
4740  // oldRange->ToString() + " > " + widen->ToString());
4741  op->getSink()->setRange(widen);
4742 
4743  const auto sinkRange = op->getSink()->getRange();
4744 
4745  if(op->getInstruction())
4746  {
4748  "WIDEN::@" + STR(GET_INDEX_CONST_NODE(op->getInstruction())) + ": " + oldRange->ToString() +
4749  " -> " + newRange->ToString() + " -> " + sinkRange->ToString());
4750  }
4751  else
4752  {
4754  "WIDEN::@artificial phi : " + oldRange->ToString() + " -> " + newRange->ToString() + " -> " +
4755  sinkRange->ToString());
4756  }
4757  return !oldRange->isSameRange(sinkRange);
4758 }
4759 
4761 {
4762  const auto oldRange = op->getSink()->getRange();
4763  const auto newRange = op->eval();
4764 
4765  auto intervalGrowth = [](RangeConstRef oldInterval, RangeConstRef newInterval) {
4766  if(oldInterval->isUnknown() || oldInterval->isEmpty() || oldInterval->isAnti() || newInterval->isEmpty() ||
4767  newInterval->isAnti())
4768  {
4769  return RangeRef(newInterval->clone());
4770  }
4771  else
4772  {
4773  auto bw = oldInterval->getBitWidth();
4774  const auto& oldLower = oldInterval->getLower();
4775  const auto& oldUpper = oldInterval->getUpper();
4776  const auto& newLower = newInterval->getLower();
4777  const auto& newUpper = newInterval->getUpper();
4778 
4779  if(newLower < oldLower || newUpper > oldUpper)
4780  {
4781  return RangeRef(new Range(Regular, bw, newLower < oldLower ? Range::Min : oldLower,
4782  newUpper > oldUpper ? Range::Max : oldUpper));
4783  }
4784  }
4785  // THROW_UNREACHABLE("Meet::growth unreachable state");
4786  return RangeRef(oldInterval->clone());
4787  };
4788 
4789  op->getSink()->setRange(intervalGrowth(oldRange, newRange));
4790 
4791  const auto sinkRange = op->getSink()->getRange();
4792  if(op->getInstruction())
4793  {
4795  "GROWTH::@" + STR(GET_INDEX_CONST_NODE(op->getInstruction())) + ": " + oldRange->ToString() +
4796  " -> " + sinkRange->ToString());
4797  }
4798  else
4799  {
4801  "GROWTH::%artificial phi : " + oldRange->ToString() + " -> " + sinkRange->ToString());
4802  }
4803  return !oldRange->isSameRange(sinkRange);
4804 }
4805 
4810 bool Meet::narrow(OpNode* op, const std::vector<APInt>& constantvector)
4811 {
4812  const auto oldRange = op->getSink()->getRange();
4813  const auto newRange = op->eval();
4814 
4815  auto intervalNarrow = [&](RangeConstRef oldInterval, RangeConstRef newInterval) {
4816  if(newInterval->isConstant())
4817  {
4818  return RangeRef(newInterval->clone());
4819  }
4820  const auto bw = oldInterval->getBitWidth();
4821  if(oldInterval->isAnti() || newInterval->isAnti() || oldInterval->isEmpty() || newInterval->isEmpty())
4822  {
4823  if(oldInterval->isAnti() && newInterval->isAnti() && !newInterval->isSameRange(oldInterval))
4824  {
4825  const auto oldAnti = oldInterval->getAnti();
4826  const auto newAnti = newInterval->getAnti();
4827  const auto& oldLower = oldAnti->getLower();
4828  const auto& oldUpper = oldAnti->getUpper();
4829  const auto& newLower = newAnti->getLower();
4830  const auto& newUpper = newAnti->getUpper();
4831  const auto& nlconstant = getFirstGreaterFromVector(constantvector, newLower);
4832  const auto& nuconstant = getFirstLessFromVector(constantvector, newUpper);
4833 
4834  if(oldLower < nlconstant && oldUpper > nuconstant)
4835  {
4836  if(nlconstant <= nuconstant)
4837  {
4838  return RangeRef(new Range(Anti, bw, nlconstant, nuconstant));
4839  }
4840  return RangeRef(new Range(Regular, bw));
4841  }
4842  if(oldLower < nlconstant)
4843  {
4844  return RangeRef(new Range(Anti, bw, nlconstant, oldUpper));
4845  }
4846  if(oldUpper > nuconstant)
4847  {
4848  return RangeRef(new Range(Anti, bw, oldLower, nuconstant));
4849  }
4850  }
4851  else if(newInterval->isUnknown() || !newInterval->isFullSet())
4852  {
4853  return RangeRef(newInterval->clone());
4854  }
4855  }
4856  else
4857  {
4858  const auto& oLower = oldInterval->isFullSet() ? Range::Min : oldInterval->getLower();
4859  const auto& oUpper = oldInterval->isFullSet() ? Range::Max : oldInterval->getUpper();
4860  const auto& nLower = newInterval->isFullSet() ? Range::Min : newInterval->getLower();
4861  const auto& nUpper = newInterval->isFullSet() ? Range::Max : newInterval->getUpper();
4862  auto sinkInterval = RangeRef(oldInterval->clone());
4863  if((oLower == Range::Min) && (nLower != Range::Min))
4864  {
4865  sinkInterval = RangeRef(new Range(Regular, bw, nLower, oUpper));
4866  }
4867  else if(nLower < oLower)
4868  {
4869  sinkInterval = RangeRef(new Range(Regular, bw, nLower, oUpper));
4870  }
4871  if(!sinkInterval->isAnti())
4872  {
4873  if((oUpper == Range::Max) && (nUpper != Range::Max))
4874  {
4875  sinkInterval = RangeRef(new Range(Regular, bw, sinkInterval->getLower(), nUpper));
4876  }
4877  else if(oUpper < nUpper)
4878  {
4879  sinkInterval = RangeRef(new Range(Regular, bw, sinkInterval->getLower(), nUpper));
4880  }
4881  }
4882  return sinkInterval;
4883  }
4884  return RangeRef(oldInterval->clone());
4885  };
4886 
4887  const auto narrow = intervalNarrow(oldRange, newRange);
4888  // THROW_ASSERT(oldRange->getSpan() >= narrow->getSpan(), "Narrowing should produce smaller range: " +
4889  // oldRange->ToString() + " < " + narrow->ToString());
4890  op->getSink()->setRange(narrow);
4891 
4892  const auto sinkRange = op->getSink()->getRange();
4893  if(op->getInstruction())
4894  {
4896  "NARROW::@" + STR(GET_INDEX_CONST_NODE(op->getInstruction())) + ": " + oldRange->ToString() +
4897  " -> " + sinkRange->ToString());
4898  }
4899  else
4900  {
4902  "NARROW::%artificial phi : " + oldRange->ToString() + " -> " + sinkRange->ToString());
4903  }
4904  return !oldRange->isSameRange(sinkRange);
4905 }
4906 
4908 {
4909  const auto oldRange = op->getSink()->getRange();
4910  const auto newRange = op->eval();
4911  const char _abstractState = op->getSink()->getAbstractState();
4912 
4913  auto intervalCrop = [](RangeConstRef oldInterval, RangeConstRef newInterval, char abstractState) {
4914  if(oldInterval->isAnti() || newInterval->isAnti() || oldInterval->isEmpty() || newInterval->isEmpty())
4915  {
4916  return RangeRef(newInterval->clone());
4917  }
4918  else
4919  {
4920  const auto bw = oldInterval->getBitWidth();
4921  if((abstractState == '-' || abstractState == '?') && (newInterval->getLower() > oldInterval->getLower()))
4922  {
4923  return RangeRef(new Range(Regular, bw, newInterval->getLower(), oldInterval->getUpper()));
4924  }
4925 
4926  if((abstractState == '+' || abstractState == '?') && (newInterval->getUpper() < oldInterval->getUpper()))
4927  {
4928  return RangeRef(new Range(Regular, bw, oldInterval->getLower(), newInterval->getUpper()));
4929  }
4930  return RangeRef(oldInterval->clone());
4931  }
4932  };
4933 
4934  op->getSink()->setRange(intervalCrop(oldRange, newRange, _abstractState));
4935 
4936  const auto sinkRange = op->getSink()->getRange();
4937  if(op->getInstruction())
4938  {
4940  "CROP::@" + STR(GET_INDEX_CONST_NODE(op->getInstruction())) + ": " + oldRange->ToString() +
4941  " -> " + sinkRange->ToString());
4942  }
4943  else
4944  {
4946  "CROP::%artificial phi : " + oldRange->ToString() + " -> " + sinkRange->ToString());
4947  }
4948  return !oldRange->isSameRange(sinkRange);
4949 }
4950 
4951 // ========================================================================== //
4952 // ConstraintGraph
4953 // ========================================================================== //
4955 
4957 
4958 class ConstraintGraph : public NodeContainer
4959 {
4960  protected:
4961  // Perform the widening and narrowing operations
4962  void update(const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& actv,
4963  std::function<bool(OpNode*, const std::vector<APInt>&)> meet)
4964  {
4965  while(!actv.empty())
4966  {
4967  const auto V = *actv.begin();
4968  actv.erase(V);
4969  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "-> update: " + GET_CONST_NODE(V)->ToString());
4970 
4971  // The use list.
4972  const auto& L = compUseMap.at(V);
4973 
4974  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "-->");
4975  for(auto* op : L)
4976  {
4977  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "> " + op->getSink()->ToString());
4978  if(meet(op, constantvector))
4979  {
4980  // I want to use it as a set, but I also want
4981  // keep an order of insertions and removals.
4982  const auto& val = op->getSink()->getValue();
4983  actv.insert(val);
4984  }
4985  }
4986  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "<--");
4987  }
4988  }
4989 
4990  void update(size_t nIterations, const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& actv)
4991  {
4992  std::deque<tree_nodeConstRef> queue(actv.begin(), actv.end());
4993  actv.clear();
4994  while(!queue.empty())
4995  {
4996  const auto V = queue.front();
4997  queue.pop_front();
4998  // The use list.
4999  const auto& L = compUseMap.at(V);
5000  for(auto op : L)
5001  {
5002  if(nIterations == 0)
5003  {
5004  return;
5005  }
5006  --nIterations;
5007  if(Meet::fixed(op))
5008  {
5009  const auto& next = op->getSink()->getValue();
5010  if(std::find(queue.begin(), queue.end(), next) == queue.end())
5011  {
5012  queue.push_back(next);
5013  }
5014  }
5015  }
5016  }
5017  }
5018 
5019  virtual void preUpdate(const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints) = 0;
5020  virtual void posUpdate(const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& activeVars,
5021  const CustomSet<VarNode*>& component) = 0;
5022 
5023  private:
5024 #ifndef NDEBUG
5025  int debug_level;
5026  int graph_debug;
5027 #endif
5028 
5029  const application_managerRef AppM;
5030 
5031  // A map from variables to the operations where these
5032  // variables are present as bounds
5033  SymbMap symbMap;
5034  // A map from functions to the operations where they are called
5035  CallMap callMap;
5036  // A map from functions to the ssa_name associated with parm_decl (bool value is true when all parameters are
5037  // associated with a variable)
5038  ParmMap parmMap;
5039 
5040  // Vector containing the constants from a SCC
5041  // It is cleared at the beginning of every SCC resolution
5042  std::vector<APInt> constantvector;
5043 
5054  unsigned int buildCVR(const gimple_cond* br, const blocRef branchBB, unsigned int function_id)
5055  {
5056  if(GetPointer<const cst_node>(GET_CONST_NODE(br->op0)) != nullptr)
5057  {
5058  return evaluateBranch(br->op0, branchBB
5059 #ifndef NDEBUG
5060  ,
5061  debug_level
5062 #endif
5063  );
5064  }
5065  THROW_ASSERT(GET_CONST_NODE(br->op0)->get_kind() == ssa_name_K,
5066  "Non SSA variable found in branch (" + GET_CONST_NODE(br->op0)->get_kind_text() + " " +
5067  GET_CONST_NODE(br->op0)->ToString() + ")");
5068  const auto Cond = branchOpRecurse(br->op0);
5069 
5071  "Branch condition is " + Cond->get_kind_text() + " " + Cond->ToString());
5072  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->");
5073  if(const auto* bin_op = GetPointer<const binary_expr>(Cond))
5074  {
5075  if(!isCompare(bin_op))
5076  {
5077  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Not a compare condition, skipping...");
5078  return bloc::ENTRY_BLOCK_ID;
5079  }
5080 
5081  if(!isValidType(bin_op->op0) || !isValidType(bin_op->op1))
5082  {
5083  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Non-integer operands, skipping...");
5084  return bloc::ENTRY_BLOCK_ID;
5085  }
5086 
5087  // Create VarNodes for comparison operands explicitly
5088  addVarNode(bin_op->op0, function_id);
5089  addVarNode(bin_op->op1, function_id);
5090 
5091  // Gets the successors of the current basic block.
5092  const auto TrueBBI = branchBB->true_edge;
5093  const auto FalseBBI = branchBB->false_edge;
5094 
5095  // We have a Variable-Constant comparison.
5096  const auto Op0 = GET_CONST_NODE(bin_op->op0);
5097  const auto Op1 = GET_CONST_NODE(bin_op->op1);
5098  tree_nodeConstRef constant = nullptr;
5099  tree_nodeConstRef variable = nullptr;
5100 
5102  "Op0 is " + Op0->get_kind_text() + " and Op1 is " + Op1->get_kind_text());
5103 
5104  // If both operands are constants, nothing to do here
5105  if(GetPointer<const cst_node>(Op0) != nullptr && GetPointer<const cst_node>(Op1) != nullptr)
5106  {
5107  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
5108  return evaluateBranch(br->op0, branchBB
5109 #ifndef NDEBUG
5110  ,
5111  debug_level
5112 #endif
5113  );
5114  }
5115 
5116  // Then there are two cases: variable being compared to a constant,
5117  // or variable being compared to another variable
5118 
5119  // Op0 is constant, Op1 is variable
5120  if(GetPointer<const cst_node>(Op0) != nullptr)
5121  {
5122  constant = Op0;
5123  variable = bin_op->op1;
5124  // Op0 is variable, Op1 is constant
5125  }
5126  else if(GetPointer<const cst_node>(Op1) != nullptr)
5127  {
5128  constant = Op1;
5129  variable = bin_op->op0;
5130  }
5131  // Both are variables
5132  // which means constant == 0 and variable == 0
5133 
5134  if(constant != nullptr)
5135  {
5136  const kind pred = isSignedType(variable) ? bin_op->get_kind() : op_unsigned(bin_op->get_kind());
5137  const kind swappred = op_swap(pred);
5138  RangeRef CR = getGIMPLE_range(constant);
5140  "Variable bitwidth is " + STR(getGIMPLE_BW(variable)) + " and constant value is " +
5141  constant->ToString());
5142 
5143  auto TValues = (GET_INDEX_CONST_NODE(variable) == GET_INDEX_CONST_NODE(bin_op->op0)) ?
5144  Range::makeSatisfyingCmpRegion(pred, CR) :
5145  Range::makeSatisfyingCmpRegion(swappred, CR);
5146  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Condition is true on " + TValues->ToString());
5147  auto FValues = TValues->isFullSet() ? getRangeFor(variable, Empty) : TValues->getAnti();
5148  // When dealing with eq/ne conditions it is safer to propagate only the constant branch value
5149  if(bin_op->get_kind() == eq_expr_K)
5150  {
5151  FValues = getRangeFor(variable, Regular);
5152  }
5153  else if(bin_op->get_kind() == ne_expr_K)
5154  {
5155  TValues = getRangeFor(variable, Regular);
5156  }
5157 
5158  // Create the interval using the intersection in the branch.
5159  const auto BT = ValueRangeRef(new ValueRange(TValues));
5160  const auto BF = ValueRangeRef(new ValueRange(FValues));
5161 
5162  addConditionalValueRange(ConditionalValueRange(variable, TrueBBI, FalseBBI, BT, BF));
5163 
5164  // Do the same for the operand of variable (if variable is a cast
5165  // instruction)
5166  if(const auto* Var = GetPointer<const ssa_name>(GET_CONST_NODE(variable)))
5167  {
5168  const auto* VDef = GetPointer<const gimple_assign>(GET_CONST_NODE(Var->CGetDefStmt()));
5169  if(VDef && (GET_CONST_NODE(VDef->op1)->get_kind() == nop_expr_K ||
5170  GET_CONST_NODE(VDef->op1)->get_kind() == convert_expr_K))
5171  {
5172  const auto* cast_inst = GetPointer<const unary_expr>(GET_CONST_NODE(VDef->op1));
5173 #ifndef NDEBUG
5174  if(GET_INDEX_CONST_NODE(variable) == GET_INDEX_CONST_NODE(bin_op->op0))
5175  {
5177  "Op0 comes from a cast expression " + cast_inst->ToString());
5178  }
5179  else
5180  {
5182  "Op1 comes from a cast expression" + cast_inst->ToString());
5183  }
5184 #endif
5185 
5186  const auto _BT = ValueRangeRef(new ValueRange(TValues));
5187  const auto _BF = ValueRangeRef(new ValueRange(FValues));
5188 
5189  addConditionalValueRange(ConditionalValueRange(cast_inst->op, TrueBBI, FalseBBI, _BT, _BF));
5190  }
5191  }
5192  }
5193  else
5194  {
5195  const kind pred = isSignedType(bin_op->op0) ? bin_op->get_kind() : op_unsigned(bin_op->get_kind());
5196  const kind invPred = op_inv(pred);
5197  const kind swappred = op_swap(pred);
5198  const kind invSwappred = op_inv(swappred);
5199 
5200 #if !defined(NDEBUG) or HAVE_ASSERTS
5201  const auto bw0 = getGIMPLE_BW(bin_op->op0);
5202 #endif
5203 #if HAVE_ASSERTS
5204  const auto bw1 = getGIMPLE_BW(bin_op->op1);
5205  THROW_ASSERT(bw0 == bw1, "Operands of same operation have different bitwidth (Op0 = " + STR(bw0) +
5206  ", Op1 = " + STR(bw1) + ").");
5207 #endif
5208 
5209  const auto CR = getRangeFor(bin_op->op0, Unknown);
5210  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Variables bitwidth is " + STR(bw0));
5211 
5212  // Symbolic intervals for op0
5213  const auto STOp0 = ValueRangeRef(new SymbRange(CR, bin_op->op1, pred));
5214  const auto SFOp0 = ValueRangeRef(new SymbRange(CR, bin_op->op1, invPred));
5215 
5216  addConditionalValueRange(ConditionalValueRange(bin_op->op0, TrueBBI, FalseBBI, STOp0, SFOp0));
5217 
5218  // Symbolic intervals for operand of op0 (if op0 is a cast instruction)
5219  if(const auto* Var = GetPointer<const ssa_name>(Op0))
5220  {
5221  const auto* VDef = GetPointer<const gimple_assign>(GET_CONST_NODE(Var->CGetDefStmt()));
5222  if(VDef && (GET_CONST_NODE(VDef->op1)->get_kind() == nop_expr_K ||
5223  GET_CONST_NODE(VDef->op1)->get_kind() == convert_expr_K))
5224  {
5225  const auto* cast_inst = GetPointer<const unary_expr>(GET_CONST_NODE(VDef->op1));
5227  "Op0 comes from a cast expression " + cast_inst->ToString());
5228 
5229  const auto STOp0_0 = ValueRangeRef(new SymbRange(CR, bin_op->op1, pred));
5230  const auto SFOp0_0 = ValueRangeRef(new SymbRange(CR, bin_op->op1, invPred));
5231 
5232  addConditionalValueRange(ConditionalValueRange(cast_inst->op, TrueBBI, FalseBBI, STOp0_0, SFOp0_0));
5233  }
5234  }
5235 
5236  // Symbolic intervals for op1
5237  const auto STOp1 = ValueRangeRef(new SymbRange(CR, bin_op->op0, swappred));
5238  const auto SFOp1 = ValueRangeRef(new SymbRange(CR, bin_op->op0, invSwappred));
5239  addConditionalValueRange(ConditionalValueRange(bin_op->op1, TrueBBI, FalseBBI, STOp1, SFOp1));
5240 
5241  // Symbolic intervals for operand of op1 (if op1 is a cast instruction)
5242  if(const auto* Var = GetPointer<const ssa_name>(Op1))
5243  {
5244  const auto* VDef = GetPointer<const gimple_assign>(GET_CONST_NODE(Var->CGetDefStmt()));
5245  if(VDef && (GET_CONST_NODE(VDef->op1)->get_kind() == nop_expr_K ||
5246  GET_CONST_NODE(VDef->op1)->get_kind() == convert_expr_K))
5247  {
5248  const auto* cast_inst = GetPointer<const unary_expr>(GET_CONST_NODE(VDef->op1));
5250  "Op1 comes from a cast expression" + cast_inst->ToString());
5251 
5252  const auto STOp1_1 = ValueRangeRef(new SymbRange(CR, bin_op->op0, swappred));
5253  const auto SFOp1_1 = ValueRangeRef(new SymbRange(CR, bin_op->op0, invSwappred));
5254 
5255  addConditionalValueRange(ConditionalValueRange(cast_inst->op, TrueBBI, FalseBBI, STOp1_1, SFOp1_1));
5256  }
5257  }
5258  }
5259  }
5260  else
5261  {
5262  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Not a compare condition, skipping...");
5263  }
5264  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
5265  return bloc::ENTRY_BLOCK_ID;
5266  }
5267 
5268  bool buildCVR(const gimple_multi_way_if* mwi, const blocRef /*mwifBB*/, unsigned int function_id)
5269  {
5271  "Multi-way if with " + STR(mwi->list_of_cond.size()) + " conditions");
5272  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->");
5273 
5274  // Find else branch BBI if any
5275  unsigned int DefaultBBI = 0;
5276  for(const auto& condBBI : mwi->list_of_cond)
5277  {
5278  if(!condBBI.first)
5279  {
5280  DefaultBBI = condBBI.second;
5281  break;
5282  }
5283  }
5284 
5285  // Analyze each if branch condition
5287  for(const auto& condBBI : mwi->list_of_cond)
5288  {
5289  if(!condBBI.first)
5290  {
5291  // Default branch is handled at the end
5292  continue;
5293  }
5294 
5295  if(GetPointer<const cst_node>(GET_CONST_NODE(condBBI.first)) != nullptr)
5296  {
5298  "Branch variable is a cst_node, dead code elimination necessary!");
5299  // TODO: abort and call dead code elimination to evaluate constant condition
5300  // return true;
5301  continue;
5302  }
5303  THROW_ASSERT(GET_CONST_NODE(condBBI.first)->get_kind() == ssa_name_K,
5304  "Case conditional variable should be an ssa_name (" +
5305  GET_CONST_NODE(condBBI.first)->get_kind_text() + " " +
5306  GET_CONST_NODE(condBBI.first)->ToString() + ")");
5307  const auto case_compare = branchOpRecurse(condBBI.first);
5308  if(const auto* cmp_op = GetPointer<const binary_expr>(case_compare))
5309  {
5310  if(!isCompare(cmp_op))
5311  {
5312  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Not a compare condition, skipping...");
5313  continue;
5314  }
5315 
5316  if(!isValidType(cmp_op->op0) || !isValidType(cmp_op->op1))
5317  {
5318  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Non-integer operands, skipping...");
5319  continue;
5320  }
5321 
5322  // Create VarNodes for comparison operands explicitly
5323  addVarNode(cmp_op->op0, function_id);
5324  addVarNode(cmp_op->op1, function_id);
5325 
5326  // We have a Variable-Constant comparison.
5327  const auto Op0 = GET_CONST_NODE(cmp_op->op0);
5328  const auto Op1 = GET_CONST_NODE(cmp_op->op1);
5329  const struct integer_cst* constant = nullptr;
5330  tree_nodeConstRef variable = nullptr;
5331 
5333  "Op0 is " + Op0->get_kind_text() + " and Op1 is " + Op1->get_kind_text());
5334 
5335  // If both operands are constants, nothing to do here
5336  if(GetPointer<const cst_node>(Op0) != nullptr && GetPointer<const cst_node>(Op1) != nullptr)
5337  {
5339  "Both operands are constants, dead code elimination necessary!");
5340  // TODO: abort and call dead code elimination to evaluate constant condition
5341  // return true;
5342  continue;
5343  }
5344 
5345  // Then there are two cases: variable being compared to a constant,
5346  // or variable being compared to another variable
5347 
5348  // Op0 is constant, Op1 is variable
5349  if((constant = GetPointer<const integer_cst>(Op0)) != nullptr)
5350  {
5351  variable = cmp_op->op1;
5352  }
5353  else if((constant = GetPointer<const integer_cst>(Op1)) != nullptr)
5354  {
5355  // Op0 is variable, Op1 is constant
5356  variable = cmp_op->op0;
5357  }
5358  // Both are variables
5359  // which means constant == 0 and variable == 0
5360 
5361  if(constant != nullptr)
5362  {
5363  const kind pred = isSignedType(variable) ? cmp_op->get_kind() : op_unsigned(cmp_op->get_kind());
5364  const kind swappred = op_swap(pred);
5365  const auto bw = getGIMPLE_BW(variable);
5366  RangeConstRef CR(new Range(Regular, bw, constant->value, constant->value));
5368  "Variable bitwidth is " + STR(bw) + " and constant value is " + STR(constant->value));
5369 
5370  const auto tmpT = (GET_INDEX_CONST_NODE(variable) == GET_INDEX_CONST_NODE(cmp_op->op0)) ?
5371  Range::makeSatisfyingCmpRegion(pred, CR) :
5372  Range::makeSatisfyingCmpRegion(swappred, CR);
5373  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Condition is true on " + tmpT->ToString());
5374 
5375  RangeRef TValues = tmpT->isFullSet() ? RangeRef(new Range(Regular, bw)) : tmpT;
5376 
5377  // Create the interval using the intersection in the branch.
5378  auto BT = ValueRangeRef(new ValueRange(TValues));
5379  switchSSAMap[variable].insert(std::make_pair(condBBI.second, BT));
5380 
5381  // Do the same for the operand of variable (if variable is a cast
5382  // instruction)
5383  if(const auto* Var = GetPointer<const ssa_name>(GET_CONST_NODE(variable)))
5384  {
5385  const auto* VDef = GetPointer<const gimple_assign>(GET_CONST_NODE(Var->CGetDefStmt()));
5386  if(VDef && (GET_CONST_NODE(VDef->op1)->get_kind() == nop_expr_K ||
5387  GET_CONST_NODE(VDef->op1)->get_kind() == convert_expr_K))
5388  {
5389  const auto* cast_inst = GetPointer<const unary_expr>(GET_CONST_NODE(VDef->op1));
5390 #ifndef NDEBUG
5391  if(GET_INDEX_CONST_NODE(variable) == GET_INDEX_CONST_NODE(cmp_op->op0))
5392  {
5394  "Op0 comes from a cast expression " + cast_inst->ToString());
5395  }
5396  else
5397  {
5399  "Op1 comes from a cast expression" + cast_inst->ToString());
5400  }
5401 #endif
5402 
5403  auto _BT = ValueRangeRef(new ValueRange(TValues));
5404  switchSSAMap[cast_inst->op].insert(std::make_pair(condBBI.second, _BT));
5405  }
5406  }
5407  }
5408  else
5409  {
5410  const kind pred = isSignedType(cmp_op->op0) ? cmp_op->get_kind() : op_unsigned(cmp_op->get_kind());
5411  const kind swappred = op_swap(pred);
5412 
5413 #if !defined(NDEBUG) or HAVE_ASSERTS
5414  const auto bw0 = getGIMPLE_BW(cmp_op->op0);
5415 #endif
5416 #if HAVE_ASSERTS
5417  const auto bw1 = getGIMPLE_BW(cmp_op->op1);
5418  THROW_ASSERT(bw0 == bw1, "Operands of same operation have different bitwidth (Op0 = " + STR(bw0) +
5419  ", Op1 = " + STR(bw1) + ").");
5420 #endif
5421 
5422  const auto CR = getRangeFor(cmp_op->op0, Unknown);
5423  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Variables bitwidth is " + STR(bw0));
5424 
5425  // Symbolic intervals for op0
5426  const auto STOp0 = ValueRangeRef(new SymbRange(CR, cmp_op->op1, pred));
5427  switchSSAMap[cmp_op->op0].insert(std::make_pair(condBBI.second, STOp0));
5428 
5429  // Symbolic intervals for operand of op0 (if op0 is a cast instruction)
5430  if(const auto* Var = GetPointer<const ssa_name>(Op0))
5431  {
5432  const auto* VDef = GetPointer<const gimple_assign>(GET_CONST_NODE(Var->CGetDefStmt()));
5433  if(VDef && (GET_CONST_NODE(VDef->op1)->get_kind() == nop_expr_K ||
5434  GET_CONST_NODE(VDef->op1)->get_kind() == convert_expr_K))
5435  {
5436  const auto* cast_inst = GetPointer<const unary_expr>(GET_CONST_NODE(VDef->op1));
5438  "Op0 comes from a cast expression" + cast_inst->ToString());
5439 
5440  const auto STOp0_0 = ValueRangeRef(new SymbRange(CR, cmp_op->op1, pred));
5441  switchSSAMap[cast_inst->op].insert(std::make_pair(condBBI.second, STOp0_0));
5442  }
5443  }
5444 
5445  // Symbolic intervals for op1
5446  const auto STOp1 = ValueRangeRef(new SymbRange(CR, cmp_op->op0, swappred));
5447  switchSSAMap[cmp_op->op1].insert(std::make_pair(condBBI.second, STOp1));
5448 
5449  // Symbolic intervals for operand of op1 (if op1 is a cast instruction)
5450  if(const auto* Var = GetPointer<const ssa_name>(Op1))
5451  {
5452  const auto* VDef = GetPointer<const gimple_assign>(GET_CONST_NODE(Var->CGetDefStmt()));
5453  if(VDef && (GET_CONST_NODE(VDef->op1)->get_kind() == nop_expr_K ||
5454  GET_CONST_NODE(VDef->op1)->get_kind() == convert_expr_K))
5455  {
5456  const auto* cast_inst = GetPointer<const unary_expr>(GET_CONST_NODE(VDef->op1));
5458  "Op1 comes from a cast expression" + cast_inst->ToString());
5459 
5460  const auto STOp1_1 = ValueRangeRef(new SymbRange(CR, cmp_op->op0, swappred));
5461  switchSSAMap[cast_inst->op].insert(std::make_pair(condBBI.second, STOp1_1));
5462  }
5463  }
5464  }
5465  }
5466  else
5467  {
5468  INDENT_DBG_MEX(DEBUG_LEVEL_PEDANTIC, debug_level,
5469  "Multi-way condition different from binary_expr not handled, skipping... (" +
5470  case_compare->get_kind_text() + " " + case_compare->ToString() + ")");
5471  }
5472  }
5473 
5474  // Handle else branch, if there is any
5475  // TODO: maybe it should be better to leave fullset as interval for default edge
5476  // because usign getAnti implies internal values to be excluded while they
5477  // could still be valid values
5478  if(static_cast<bool>(DefaultBBI))
5479  {
5480  for(auto& varVSM : switchSSAMap)
5481  {
5482  auto elseRange = getRangeFor(varVSM.first, Empty);
5483  for(const auto& BBIinterval : varVSM.second)
5484  {
5485  elseRange = elseRange->unionWith(BBIinterval.second->getRange());
5486  }
5487  elseRange = elseRange->getAnti();
5488  varVSM.second.insert(std::make_pair(DefaultBBI, ValueRangeRef(new ValueRange(elseRange))));
5489  }
5490  }
5491 
5492  for(const auto& varVSM : switchSSAMap)
5493  {
5494  addConditionalValueRange(ConditionalValueRange(varVSM.first, varVSM.second));
5495  }
5496  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
5497  return false;
5498  }
5499 
5500  /*
5501  * This method builds a map that binds each variable label to the
5502  * operations
5503  * where this variable is used.
5504  */
5505  UseMap buildUseMap(const CustomSet<VarNode*>& component)
5506  {
5507  UseMap compUseMap;
5508  for(auto vit = component.begin(), vend = component.end(); vit != vend; ++vit)
5509  {
5510  const VarNode* var = *vit;
5511  const auto& V = var->getValue();
5512  // Get the component's use list for V (it does not exist until we try to get it)
5513  auto& list = compUseMap[V];
5514  // Get the use list of the variable in component
5515  auto p = getUses().find(V);
5516  // For each operation in the list, verify if its sink is in the component
5517  for(auto* opit : p->second)
5518  {
5519  VarNode* sink = opit->getSink();
5520  // If it is, add op to the component's use map
5521  if(static_cast<bool>(component.count(sink)))
5522  {
5523  list.insert(opit);
5524  }
5525  }
5526  }
5527  return compUseMap;
5528  }
5529 
5530  /*
5531  * Used to insert constant in the right position
5532  */
5533  void insertConstantIntoVector(const APInt& constantval, bw_t bw)
5534  {
5535  constantvector.push_back(constantval.extOrTrunc(bw, true));
5536  }
5537 
5538  /*
5539  * Create a vector containing all constants related to the component
5540  * They include:
5541  * - Constants inside component
5542  * - Constants that are source of an edge to an entry point
5543  * - Constants from intersections generated by sigmas
5544  */
5545  void buildConstantVector(const CustomSet<VarNode*>& component, const UseMap& compusemap)
5546  {
5547  // Remove all elements from the vector
5548  constantvector.clear();
5549 
5550  // Get constants inside component (TODO: may not be necessary, since
5551  // components with more than 1 node may
5552  // never have a constant inside them)
5553  for(const auto* varNode : component)
5554  {
5555  const auto& V = varNode->getValue();
5556  if(const auto* ic = GetPointer<const integer_cst>(GET_CONST_NODE(V)))
5557  {
5558  insertConstantIntoVector(tree_helper::get_integer_cst_value(ic), varNode->getBitWidth());
5559  }
5560  }
5561 
5562  // Get constants that are sources of operations whose sink belong to the
5563  // component
5564  for(const auto* varNode : component)
5565  {
5566  const auto& V = varNode->getValue();
5567  auto dfit = getDefs().find(V);
5568  if(dfit == getDefs().end())
5569  {
5570  continue;
5571  }
5572 
5573  auto pushConstFor = [this](const APInt& cst, bw_t bw, kind pred) {
5574  if(isCompare(pred))
5575  {
5576  if(pred == eq_expr_K || pred == ne_expr_K)
5577  {
5578  insertConstantIntoVector(cst, bw);
5579  insertConstantIntoVector(cst - 1, bw);
5580  insertConstantIntoVector(cst + 1, bw);
5581  }
5582  else if(pred == uneq_expr_K)
5583  {
5584  const auto ucst = cst.extOrTrunc(bw, false);
5585  insertConstantIntoVector(ucst, bw);
5586  insertConstantIntoVector(ucst - 1, bw);
5587  insertConstantIntoVector(ucst + 1, bw);
5588  }
5589  else if(pred == gt_expr_K || pred == le_expr_K)
5590  {
5591  insertConstantIntoVector(cst, bw);
5592  insertConstantIntoVector(cst + 1, bw);
5593  }
5594  else if(pred == ge_expr_K || pred == lt_expr_K)
5595  {
5596  insertConstantIntoVector(cst, bw);
5597  insertConstantIntoVector(cst - 1, bw);
5598  }
5599  else if(pred == ungt_expr_K || pred == unle_expr_K)
5600  {
5601  const auto ucst = cst.extOrTrunc(bw, false);
5602  insertConstantIntoVector(ucst, bw);
5603  insertConstantIntoVector(ucst + 1, bw);
5604  }
5605  else if(pred == unge_expr_K || pred == unlt_expr_K)
5606  {
5607  const auto ucst = cst.extOrTrunc(bw, false);
5608  insertConstantIntoVector(ucst, bw);
5609  insertConstantIntoVector(ucst - 1, bw);
5610  }
5611  else
5612  {
5613  THROW_UNREACHABLE("unexpected condition (" + tree_node::GetString(pred) + ")");
5614  }
5615  }
5616  else
5617  {
5618  insertConstantIntoVector(cst, bw);
5619  }
5620  };
5621 
5622  // Handle BinaryOp case
5623  if(const auto* bop = GetOp<BinaryOpNode>(dfit->second))
5624  {
5625  const auto* source1 = bop->getSource1();
5626  const auto& sourceval1 = source1->getValue();
5627  const auto* source2 = bop->getSource2();
5628  const auto& sourceval2 = source2->getValue();
5629 
5630  const auto pred = bop->getOpcode();
5631 
5632  if(const auto* const1 = GetPointer<const integer_cst>(GET_CONST_NODE(sourceval1)))
5633  {
5634  const auto bw = source1->getBitWidth();
5635  const auto cst_val = tree_helper::get_integer_cst_value(const1);
5636  pushConstFor(cst_val, bw, pred); // TODO: maybe should swap predicate for lhs constant?
5637  }
5638  if(const auto* const2 = GetPointer<const integer_cst>(GET_CONST_NODE(sourceval2)))
5639  {
5640  const auto bw = source2->getBitWidth();
5641  const auto cst_val = tree_helper::get_integer_cst_value(const2);
5642  pushConstFor(cst_val, bw, pred);
5643  }
5644  }
5645  // Handle PhiOp case
5646  else if(const auto* pop = GetOp<PhiOpNode>(dfit->second))
5647  {
5648  for(size_t i = 0, e = pop->getNumSources(); i < e; ++i)
5649  {
5650  const auto* source = pop->getSource(i);
5651  const auto& sourceval = source->getValue();
5652  if(const auto* ic = GetPointer<const integer_cst>(GET_CONST_NODE(sourceval)))
5653  {
5654  insertConstantIntoVector(tree_helper::get_integer_cst_value(ic), source->getBitWidth());
5655  }
5656  }
5657  }
5658  }
5659 
5660  // Get constants used in intersections
5661  for(const auto& varOps : compusemap)
5662  {
5663  for(const auto* op : varOps.second)
5664  {
5665  const auto* sigma = GetOp<SigmaOpNode>(op);
5666  // Symbolic intervals are discarded, as they don't have fixed values yet
5667  if(sigma == nullptr || SymbRange::classof(sigma->getIntersect().get()))
5668  {
5669  continue;
5670  }
5671  const auto rintersect = op->getIntersect()->getRange();
5672  const auto bw = rintersect->getBitWidth();
5673  if(rintersect->isAnti())
5674  {
5675  const auto anti = rintersect->getAnti();
5676  const auto& lb = anti->getLower();
5677  const auto& ub = anti->getUpper();
5678  if((lb != Range::Min) && (lb != Range::Max))
5679  {
5680  insertConstantIntoVector(lb - 1, bw);
5681  insertConstantIntoVector(lb, bw);
5682  }
5683  if((ub != Range::Min) && (ub != Range::Max))
5684  {
5685  insertConstantIntoVector(ub, bw);
5686  insertConstantIntoVector(ub + 1, bw);
5687  }
5688  }
5689  else
5690  {
5691  const auto& lb = rintersect->getLower();
5692  const auto& ub = rintersect->getUpper();
5693  if((lb != Range::Min) && (lb != Range::Max))
5694  {
5695  insertConstantIntoVector(lb - 1, bw);
5696  insertConstantIntoVector(lb, bw);
5697  }
5698  if((ub != Range::Min) && (ub != Range::Max))
5699  {
5700  insertConstantIntoVector(ub, bw);
5701  insertConstantIntoVector(ub + 1, bw);
5702  }
5703  }
5704  }
5705  }
5706 
5707  // Sort vector in ascending order and remove duplicates
5708  std::sort(constantvector.begin(), constantvector.end(), [](const APInt& i1, const APInt& i2) { return i1 < i2; });
5709 
5710  // std::unique doesn't remove duplicate elements, only
5711  // move them to the end
5712  // This is why erase is necessary. To remove these duplicates
5713  // that will be now at the end.
5714  auto last = std::unique(constantvector.begin(), constantvector.end());
5715  constantvector.erase(last, constantvector.end());
5716  }
5717 
5718  /*
5719  * This method builds a map of variables to the lists of operations where
5720  * these variables are used as futures. Its C++ type should be something like
5721  * map<VarNode, List<Operation>>.
5722  */
5723  void buildSymbolicIntersectMap()
5724  {
5725  // Creates the symbolic intervals map
5726  symbMap = SymbMap();
5727 
5728  // Iterate over the operations set
5729  for(auto* op : getOpNodes())
5730  {
5731  // If the operation is unary and its interval is symbolic
5732  auto* uop = GetOp<UnaryOpNode>(op);
5733  if((uop != nullptr) && SymbRange::classof(uop->getIntersect().get()))
5734  {
5735  const auto symbi = std::static_pointer_cast<const SymbRange>(uop->getIntersect());
5736  const auto V = symbi->getBound();
5737  auto p = symbMap.find(V);
5738  if(p != symbMap.end())
5739  {
5740  p->second.insert(uop);
5741  }
5742  else
5743  {
5745  l.insert(uop);
5746  symbMap.insert(std::make_pair(V, l));
5747  }
5748  }
5749  }
5750  }
5751 
5752  /*
5753  * This method evaluates once each operation that uses a variable in
5754  * component, so that the next SCCs after component will have entry
5755  * points to kick start the range analysis algorithm.
5756  */
5757  void propagateToNextSCC(const CustomSet<VarNode*>& component)
5758  {
5759  const auto& uses = getUses();
5760  for(const auto& var : component)
5761  {
5762  const auto& V = var->getValue();
5763  const auto& p = uses.at(V);
5764  for(auto* op : p)
5765  {
5768  if(component.contains(op->getSink()))
5769  {
5770  continue;
5771  }
5772  auto* sigmaop = GetOp<SigmaOpNode>(op);
5773  op->getSink()->setRange(op->eval());
5774  if((sigmaop != nullptr) && sigmaop->getIntersect()->getRange()->isUnknown())
5775  {
5776  sigmaop->markUnresolved();
5777  }
5778  }
5779  }
5780  }
5781 
5782  void generateEntryPoints(const CustomSet<VarNode*>& component,
5783  std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints)
5784  {
5785  // Iterate over the varnodes in the component
5786  for(VarNode* varNode : component)
5787  {
5788  const auto& V = varNode->getValue();
5789  if(const auto* ssa = GetPointer<const ssa_name>(GET_CONST_NODE(V)))
5790  {
5791  if(const auto* phi_def = GetPointer<const gimple_phi>(GET_CONST_NODE(ssa->CGetDefStmt())))
5792  {
5793  if(phi_def->CGetDefEdgesList().size() == 1)
5794  {
5795  auto dit = getDefs().find(V);
5796  if(dit != getDefs().end())
5797  {
5798  auto* bop = dit->second;
5799  auto* defop = GetOp<SigmaOpNode>(bop);
5800 
5801  if((defop != nullptr) && defop->isUnresolved())
5802  {
5803  defop->getSink()->setRange(bop->eval());
5804  defop->markResolved();
5805  }
5806  }
5807  }
5808  }
5809  }
5810  if(!varNode->getRange()->isUnknown())
5811  {
5812  entryPoints.insert(V);
5813  }
5814  }
5815  }
5816 
5817  void solveFutures(const CustomSet<VarNode*>& component)
5818  {
5819  // Iterate again over the varnodes in the component
5820  for(auto* varNode : component)
5821  {
5822  solveFuturesSC(varNode);
5823  }
5824  }
5825 
5826  void solveFuturesSC(VarNode* varNode)
5827  {
5828  const auto& V = varNode->getValue();
5829  auto sit = symbMap.find(V);
5830  if(sit != symbMap.end())
5831  {
5832  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "Fix intersects: " + varNode->ToString());
5833  for(auto* op : sit->second)
5834  {
5835  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "Op intersects: " + op->ToString());
5836  op->solveFuture(varNode);
5837  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "Sink: " + op->ToString());
5838  }
5839  }
5840  }
5841 
5842  void generateActivesVars(const CustomSet<VarNode*>& component,
5843  std::set<tree_nodeConstRef, tree_reindexCompare>& activeVars)
5844  {
5845  for(auto* varNode : component)
5846  {
5847  const auto& V = varNode->getValue();
5848  const auto* CI = GetPointer<const integer_cst>(GET_CONST_NODE(V));
5849  if(CI != nullptr)
5850  {
5851  continue;
5852  }
5853  activeVars.insert(V);
5854  }
5855  }
5856 
5857  void parametersBinding(const tree_nodeRef stmt, const struct function_decl* FD)
5858  {
5859  const auto& args = FD->list_of_args;
5860  auto parmMapIt = parmMap.find(FD->index);
5861  if(parmMapIt == parmMap.end())
5862  {
5863  parmMapIt = parmMap
5864  .insert(std::make_pair(
5865  FD->index, std::make_pair(false, std::vector<tree_nodeConstRef>(args.size(), nullptr))))
5866  .first;
5867  }
5868  auto& foundAll = parmMapIt->second.first;
5869  // Skip ssa uses computation when all parameters have already been associated with a variable
5870  if(foundAll)
5871  {
5872  return;
5873  }
5874 
5875  auto& parmBind = parmMapIt->second.second;
5876  const auto ssa_uses = tree_helper::ComputeSsaUses(stmt);
5877  for(const auto& ssa_use_counter : ssa_uses)
5878  {
5879  auto ssa = ssa_use_counter.first;
5880  const auto* SSA = GetPointer<const ssa_name>(GET_CONST_NODE(ssa));
5881  // If ssa_name references a parm_decl and is defined by a gimple_nop, it represents the formal function
5882  // parameter inside the function body
5883  if(SSA->var != nullptr && GET_CONST_NODE(SSA->var)->get_kind() == parm_decl_K &&
5884  GET_CONST_NODE(SSA->CGetDefStmt())->get_kind() == gimple_nop_K)
5885  {
5886  auto argIt = std::find_if(args.begin(), args.end(), [&](const tree_nodeRef& arg) {
5887  return GET_INDEX_CONST_NODE(arg) == GET_INDEX_CONST_NODE(SSA->var);
5888  });
5889  THROW_ASSERT(argIt != args.end(), "parm_decl associated with ssa_name not found in function parameters");
5890  size_t arg_pos = static_cast<size_t>(argIt - args.begin());
5891  THROW_ASSERT(arg_pos < args.size(), "Computed parameter position outside actual parameters number");
5893  "Variable " + SSA->ToString() + " is defined from parameter " + STR(arg_pos) +
5894  " of function " + GetPointer<const identifier_node>(GET_CONST_NODE(FD->name))->strg);
5895  parmBind[arg_pos] = ssa;
5896  foundAll = std::find(parmBind.begin(), parmBind.end(), nullptr) == parmBind.end();
5897  }
5898  }
5899  }
5900 
5901  bool storeFunctionCall(const tree_nodeConstRef tn)
5902  {
5903  tree_nodeRef fun_node = nullptr;
5904 
5905  if(const auto* ga = GetPointer<const gimple_assign>(GET_CONST_NODE(tn)))
5906  {
5907  if(const auto* ce = GetPointer<const call_expr>(GET_CONST_NODE(ga->op1)))
5908  {
5909  fun_node = ce->fn;
5910  }
5911  }
5912  if(const auto* ce = GetPointer<const gimple_call>(GET_CONST_NODE(tn)))
5913  {
5914  fun_node = ce->fn;
5915  }
5916 
5917  if(fun_node)
5918  {
5919  if(GET_NODE(fun_node)->get_kind() == addr_expr_K)
5920  {
5921  const auto* ue = GetPointer<const unary_expr>(GET_NODE(fun_node));
5922  fun_node = ue->op;
5923  }
5924  else if(GET_NODE(fun_node)->get_kind() == obj_type_ref_K)
5925  {
5926  fun_node = tree_helper::find_obj_type_ref_function(fun_node);
5927  }
5928 
5929  const auto* FD = GetPointer<const function_decl>(GET_CONST_NODE(fun_node));
5930  THROW_ASSERT(FD, "Function call should reference a function_decl node");
5932  DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
5933  "Analysing function call to " +
5934  tree_helper::print_type(AppM->get_tree_manager(), FD->index, false, true, false, 0U,
5936  AppM->CGetFunctionBehavior(FD->index)->CGetBehavioralHelper()))));
5937 
5938  auto it = callMap.find(FD->index);
5939  if(it == callMap.end())
5940  {
5941  it = callMap.insert(std::make_pair(FD->index, std::list<tree_nodeConstRef>())).first;
5942  }
5943  it->second.emplace_back(tn);
5944  return true;
5945  }
5946  return false;
5947  }
5948 
5949  public:
5950  ConstraintGraph(application_managerRef _AppM
5951 #ifndef NDEBUG
5952  ,
5953  int _debug_level, int _graph_debug
5954 #else
5955  ,
5956  int, int
5957 #endif
5958  )
5959  :
5960 #ifndef NDEBUG
5961  debug_level(_debug_level),
5962  graph_debug(_graph_debug),
5963 #endif
5964  AppM(_AppM)
5965  {
5966 #ifndef NDEBUG
5967  NodeContainer::debug_level = debug_level;
5968 #endif
5969  }
5970 
5971  ~ConstraintGraph() override = default;
5972 
5973  CallMap* getCallMap()
5974  {
5975  return &callMap;
5976  }
5977  const ParmMap& getParmMap()
5978  {
5979  return parmMap;
5980  }
5981 
5983  bool buildGraph(unsigned int function_id)
5984  {
5985  const auto TM = AppM->get_tree_manager();
5986  const auto FB = AppM->CGetFunctionBehavior(function_id);
5987  const auto* FD = GetPointer<const function_decl>(TM->get_tree_node_const(function_id));
5988  const auto* SL = GetPointer<const statement_list>(GET_CONST_NODE(FD->body));
5989 #ifndef NDEBUG
5990  std::string fn_name =
5991  tree_helper::print_type(TM, function_id, false, true, false, 0U,
5993 #endif
5995  "Analysing function " + fn_name + " with " + STR(SL->list_of_bloc.size()) + " blocks");
5996  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->");
5997 
5998  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Branch variables analysis...");
5999  for(const auto& idxBB : SL->list_of_bloc)
6000  {
6001  const auto& stmt_list = idxBB.second->CGetStmtList();
6002  if(stmt_list.empty())
6003  {
6004  continue;
6005  }
6006 
6007  const auto terminator = GET_CONST_NODE(stmt_list.back());
6009  "BB" + STR(idxBB.first) + " has terminator type " + terminator->get_kind_text() + " " +
6010  terminator->ToString());
6011  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->");
6012  if(const auto* br = GetPointer<const gimple_cond>(terminator))
6013  {
6014 #ifdef EARLY_DEAD_CODE_RESTART
6015  if(buildCVR(br, idxBB.second, function_id))
6016  {
6017  // Dead code elimination necessary
6018  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
6019  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
6020  return true;
6021  }
6022 #else
6023  buildCVR(br, idxBB.second, function_id);
6024 #endif
6025  }
6026  else if(const auto* mwi = GetPointer<const gimple_multi_way_if>(terminator))
6027  {
6028 #ifdef EARLY_DEAD_CODE_RESTART
6029  if(buildCVR(mwi, idxBB.second, function_id))
6030  {
6031  // Dead code elimination necessary
6032  return true;
6033  }
6034 #else
6035  buildCVR(mwi, idxBB.second, function_id);
6036 #endif
6037  }
6038  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
6039  }
6040  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Branch variables analysis completed");
6041 
6042  for(const auto& idxBB : SL->list_of_bloc)
6043  {
6044  const auto& phi_list = idxBB.second->CGetPhiList();
6045  if(phi_list.size())
6046  {
6047  for(const auto& stmt : phi_list)
6048  {
6049  parametersBinding(stmt, FD);
6050  if(isValidInstruction(stmt, FB))
6051  {
6052  addOperation(stmt, function_id, FB, TM, AppM);
6053  }
6054  }
6055  }
6056 
6057  const auto& stmt_list = idxBB.second->CGetStmtList();
6058  if(stmt_list.size())
6059  {
6060  for(const auto& stmt : stmt_list)
6061  {
6062  if(!isValidInstruction(stmt, FB))
6063  {
6064  parametersBinding(stmt, FD);
6065  if(!storeFunctionCall(stmt))
6066  {
6068  "Skipping " + GET_NODE(stmt)->get_kind_text() + " " + GET_NODE(stmt)->ToString());
6069  }
6070  continue;
6071  }
6072  addOperation(stmt, function_id, FB, TM, AppM);
6073  parametersBinding(stmt, FD);
6074  }
6075  }
6076  }
6077  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
6078  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Graph built for function " + fn_name);
6079  return false;
6080  }
6081 
6082  void buildVarNodes()
6083  {
6084  // Initializes the nodes and the use map structure.
6085  for(auto& pair : getVarNodes())
6086  {
6087  pair.second->init(!static_cast<bool>(getDefs().count(pair.first)));
6088  }
6089  }
6090 
6091  void findIntervals(
6092 #ifndef NDEBUG
6093  const ParameterConstRef parameters, const std::string& step_name
6094 #endif
6095  )
6096  {
6097  buildSymbolicIntersectMap();
6098 // List of SCCs
6099 #ifndef NDEBUG
6100  Nuutila sccList(getVarNodes(), getUses(), symbMap, graph_debug);
6101 #else
6102  Nuutila sccList(getVarNodes(), getUses(), symbMap);
6103 #endif
6104 
6105  for(const auto& n : sccList)
6106  {
6107  const auto& component = sccList.getComponent(n);
6108 
6109 #ifndef NDEBUG
6110  if(DEBUG_LEVEL_VERY_PEDANTIC <= graph_debug)
6111  {
6112  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "Components:");
6113  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "-->");
6114  for(const auto* var : component)
6115  {
6116  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, var->ToString());
6117  }
6118  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "-------------");
6119  }
6120 #endif
6121  if(component.size() == 1)
6122  {
6123  VarNode* var = *component.begin();
6124  solveFuturesSC(var);
6125  auto varDef = getDefs().find(var->getValue());
6126  if(varDef != getDefs().end())
6127  {
6128  auto* op = varDef->second;
6129  var->setRange(op->eval());
6130  }
6131  if(var->getRange()->isUnknown())
6132  {
6133  var->setRange(var->getMaxRange());
6134  }
6135  }
6136  else
6137  {
6138  const auto compUseMap = buildUseMap(component);
6139 
6140 #ifdef RA_JUMPSET
6141  // Create vector of constants inside component
6142  // Comment this line below to deactivate jump-set
6143  buildConstantVector(component, compUseMap);
6144 #ifndef NDEBUG
6145  if(DEBUG_LEVEL_VERY_PEDANTIC <= graph_debug)
6146  {
6147  std::stringstream ss;
6148  for(const auto& cnst : constantvector)
6149  {
6150  ss << cnst << ", ";
6151  }
6152  if(!constantvector.empty())
6153  {
6155  "Constant lattice: {-inf, " + ss.str() + "+inf}");
6156  }
6157  }
6158 #endif
6159 #endif
6160 
6161  // Get the entry points of the SCC
6162  std::set<tree_nodeConstRef, tree_reindexCompare> entryPoints;
6163 #ifndef NDEBUG
6164  auto printEntryFor = [&](const std::string& mType) {
6165  if(DEBUG_LEVEL_VERY_PEDANTIC <= graph_debug)
6166  {
6167  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, mType + " step entry points:");
6168  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "-->");
6169  for(const auto& el : entryPoints)
6170  {
6172  }
6173  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "<--");
6174  }
6175  };
6176 #endif
6177 
6178  generateEntryPoints(component, entryPoints);
6179 #ifndef NDEBUG
6180  printEntryFor("Fixed");
6181 #endif
6182  // iterate a fixed number of time before widening
6183  update(static_cast<size_t>(component.size() * 16L), compUseMap, entryPoints);
6185  DEBUG_LEVEL_VERY_PEDANTIC, graph_debug,
6186  "Printed constraint graph to " +
6187  printToFile("after_" + step_name + ".fixed." + STR(GET_INDEX_CONST_NODE(n)) + ".dot", parameters));
6188 
6189  generateEntryPoints(component, entryPoints);
6190 #ifndef NDEBUG
6191  printEntryFor("Widen");
6192 #endif
6193  // First iterate till fix point
6194  preUpdate(compUseMap, entryPoints);
6195  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "fixIntersects");
6196  solveFutures(component);
6197  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, " --");
6199  "Printed constraint graph to " +
6200  printToFile("after_" + step_name + ".futures." + STR(GET_INDEX_CONST_NODE(n)) + ".dot",
6201  parameters));
6202 
6203  for(VarNode* varNode : component)
6204  {
6205  if(varNode->getRange()->isUnknown())
6206  {
6207  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "initialize unknown: " + varNode->ToString());
6208  // THROW_UNREACHABLE("unexpected condition");
6209  varNode->setRange(varNode->getMaxRange());
6210  }
6211  }
6213  DEBUG_LEVEL_VERY_PEDANTIC, graph_debug,
6214  "Printed constraint graph to " +
6215  printToFile("after_" + step_name + ".int." + STR(GET_INDEX_CONST_NODE(n)) + ".dot", parameters));
6216 
6217  // Second iterate till fix point
6218  std::set<tree_nodeConstRef, tree_reindexCompare> activeVars;
6219  generateActivesVars(component, activeVars);
6220 #ifndef NDEBUG
6221  printEntryFor("Narrow");
6222 #endif
6223  posUpdate(compUseMap, activeVars, component);
6224  }
6225  propagateToNextSCC(component);
6226  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, graph_debug, "<--");
6227  }
6229  "Printed final constraint graph to " + printToFile(step_name + ".constraints.dot", parameters));
6230  }
6231 
6232 #ifndef NDEBUG
6233  std::string printToFile(const std::string& file_name, const ParameterConstRef parameters) const
6234  {
6235  std::string output_directory = parameters->getOption<std::string>(OPT_dot_directory) + "RangeAnalysis/";
6236  if(!std::filesystem::exists(output_directory))
6237  {
6238  std::filesystem::create_directories(output_directory);
6239  }
6240  const std::string full_name = output_directory + file_name;
6241  std::ofstream file(full_name);
6242  printDot(file);
6243  return full_name;
6244  }
6245 
6248  void printDot(std::ostream& OS) const
6249  {
6250  const char* quot = R"(")";
6251  // Print the header of the .dot file.
6252  OS << "digraph dotgraph {\n";
6253  OS << R"(label="Constraint Graph for ')";
6254  OS << "all\' functions\";\n";
6255  OS << "node [shape=record,fontname=\"Times-Roman\",fontsize=14];\n";
6256 
6257  // Print the body of the .dot file.
6258  for(const auto& varNode : getVarNodes())
6259  {
6260  if(GET_CONST_NODE(varNode.first)->get_kind() == integer_cst_K)
6261  {
6262  OS << " " << tree_helper::GetConstValue(varNode.first);
6263  }
6264  else
6265  {
6266  OS << quot;
6267  printVarName(varNode.first, OS);
6268  OS << quot;
6269  }
6270  OS << R"( [label=")" << varNode.second << "\"]\n";
6271  }
6272 
6273  for(auto* op : getOpNodes())
6274  {
6275  op->printDot(OS);
6276  OS << '\n';
6277  }
6278  OS << pseudoEdgesString.str();
6279  // Print the footer of the .dot file.
6280  OS << "}\n";
6281  }
6282 #endif
6283 };
6284 
6285 // ========================================================================== //
6286 // Cousot
6287 // ========================================================================== //
6288 class Cousot : public ConstraintGraph
6289 {
6290  private:
6291  void preUpdate(const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints) override
6292  {
6293  update(compUseMap, entryPoints, Meet::widen);
6294  }
6295 
6296  void posUpdate(const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints,
6297  const CustomSet<VarNode*>& /*component*/) override
6298  {
6299  update(compUseMap, entryPoints, Meet::narrow);
6300  }
6301 
6302  public:
6303  Cousot(application_managerRef _AppM, int _debug_level, int _graph_debug)
6304  : ConstraintGraph(_AppM, _debug_level, _graph_debug)
6305  {
6306  }
6307 };
6308 
6309 // ========================================================================== //
6310 // CropDFS
6311 // ========================================================================== //
6312 class CropDFS : public ConstraintGraph
6313 {
6314  private:
6315  void preUpdate(const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints) override
6316  {
6317  update(compUseMap, entryPoints, [](OpNode* b, const std::vector<APInt>&) { return Meet::growth(b); });
6318  }
6319 
6320  void posUpdate(const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& /*activeVars*/,
6321  const CustomSet<VarNode*>& component) override
6322  {
6323  storeAbstractStates(component);
6324  for(const auto& op : getOpNodes())
6325  {
6326  if(static_cast<bool>(component.count(op->getSink())))
6327  {
6328  crop(compUseMap, op);
6329  }
6330  }
6331  }
6332 
6333  void storeAbstractStates(const CustomSet<VarNode*>& component)
6334  {
6335  for(const auto& varNode : component)
6336  {
6337  varNode->storeAbstractState();
6338  }
6339  }
6340 
6341  void crop(const UseMap& compUseMap, OpNode* op)
6342  {
6343  CustomSet<OpNode*> activeOps;
6344  CustomSet<const VarNode*> visitedOps;
6345 
6346  // init the activeOps only with the op received
6347  activeOps.insert(op);
6348 
6349  while(!activeOps.empty())
6350  {
6351  auto* V = *activeOps.begin();
6352  activeOps.erase(V);
6353  const VarNode* sink = V->getSink();
6354 
6355  // if the sink has been visited go to the next activeOps
6356  if(static_cast<bool>(visitedOps.count(sink)))
6357  {
6358  continue;
6359  }
6360 
6361  Meet::crop(V);
6362  visitedOps.insert(sink);
6363 
6364  // The use list.of sink
6365  const auto& L = compUseMap.at(sink->getValue());
6366  for(auto* opr : L)
6367  {
6368  activeOps.insert(opr);
6369  }
6370  }
6371  }
6372 
6373  public:
6374  CropDFS(application_managerRef _AppM, int _debug_level, int _graph_debug)
6375  : ConstraintGraph(_AppM, _debug_level, _graph_debug)
6376  {
6377  }
6378 };
6379 
6380 static void TopFunctionUserHits(unsigned int function_id, const application_managerRef AppM,
6381  const ConstraintGraphRef CG,
6382  int
6383 #ifndef NDEBUG
6384  debug_level
6385 #endif
6386 )
6387 {
6388  const auto TM = AppM->get_tree_manager();
6389  const auto fd = TM->get_tree_node_const(function_id);
6390  const auto* FD = GetPointer<const function_decl>(fd);
6391 
6392  const auto& parmMap = CG->getParmMap();
6393  const auto funParm = parmMap.find(function_id);
6394  THROW_ASSERT(funParm != parmMap.end(), "Function parameters binding unavailable");
6395  const auto& parmBind = funParm->second.second;
6396  THROW_ASSERT(parmBind.size() == FD->list_of_args.size(), "Parameters count mismatch");
6398  for(size_t i = 0; i < FD->list_of_args.size(); ++i)
6399  {
6400  if(const auto& p = parmBind.at(i))
6401  {
6402  const auto pType = getGIMPLE_Type(p);
6403  if(!isValidType(pType))
6404  {
6406  "Parameter " + STR(i) + " is of non-valid type (" + GET_CONST_NODE(pType)->get_kind_text() +
6407  ")");
6408  continue;
6409  }
6411  "Parameter " + STR(i) + " defined as " + GET_CONST_NODE(p)->ToString());
6412 
6413  VarNode* sink = CG->addVarNode(p, function_id);
6414 
6415  // Check for pragma mask directives user defined range
6416  const auto parm = GetPointer<const parm_decl>(GET_CONST_NODE(FD->list_of_args.at(i)));
6417  if(parm->range != nullptr)
6418  {
6419  sink->setRange(parm->range);
6421  "---User-defined hints found " + parm->range->ToString());
6422  }
6423  }
6424  else
6425  {
6426  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Parameter " + STR(i) + " missing from function body");
6427  }
6428  }
6430 }
6431 
6432 static void ParmAndRetValPropagation(unsigned int function_id, const application_managerRef AppM,
6433  const ConstraintGraphRef CG,
6434  int
6435 #ifndef NDEBUG
6436  debug_level
6437 #endif
6438 )
6439 {
6440  const auto TM = AppM->get_tree_manager();
6441  const auto fd = TM->get_tree_node_const(function_id);
6442  const auto* FD = GetPointer<const function_decl>(fd);
6443 #if !defined(NDEBUG) or HAVE_ASSERTS
6444  std::string fn_name = tree_helper::print_type(
6445  TM, function_id, false, true, false, 0U,
6446  var_pp_functorConstRef(new std_var_pp_functor(AppM->CGetFunctionBehavior(function_id)->CGetBehavioralHelper())));
6447 #endif
6449  "Parameters and return value propagation on function " + fn_name);
6451 
6452  if(!static_cast<bool>(CG->getCallMap()->count(function_id)))
6453  {
6454  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "No call statements for this function, skipping...");
6456  return;
6457  }
6458  const auto& functionCalls = CG->getCallMap()->at(function_id);
6459 
6460  // Data structure which contains the matches between formal and real parameters
6461  // First: formal parameter
6462  // Second: real parameter
6463  std::vector<std::pair<tree_nodeConstRef, tree_nodeConstRef>> parameters(FD->list_of_args.size());
6464 
6465  // Fetch the function arguments (formal parameters) into the data structure and generate PhiOp nodes for parameters
6466  // call values
6467  const auto& parmMap = CG->getParmMap();
6468  const auto funParm = parmMap.find(function_id);
6469  THROW_ASSERT(funParm != parmMap.end(), "Function parameters binding unavailable");
6470  const auto& parmBind = funParm->second.second;
6471  THROW_ASSERT(parmBind.size() == parameters.size(), "Parameters count mismatch");
6472  std::vector<PhiOpNode*> matchers(parameters.size(), nullptr);
6473  for(size_t i = 0; i < parameters.size(); ++i)
6474  {
6475  if(const auto& p = parmBind.at(i))
6476  {
6477  const auto pType = getGIMPLE_Type(p);
6478  if(!isValidType(pType))
6479  {
6481  "Parameter " + STR(i) + " is of non-valid type (" + GET_CONST_NODE(pType)->get_kind_text() +
6482  ")");
6483  continue;
6484  }
6485  parameters[i].first = p;
6487  "Parameter " + STR(i) + " defined as " + GET_CONST_NODE(p)->ToString());
6488 
6489  VarNode* sink = CG->addVarNode(p, function_id);
6490 
6491  // Check for pragma mask directives user defined range
6492  const auto parm = GetPointer<const parm_decl>(GET_CONST_NODE(FD->list_of_args.at(i)));
6493  if(parm->range != nullptr)
6494  {
6495  sink->setRange(parm->range);
6497  "---User-defined hints found " + parm->range->ToString());
6498  }
6499  else
6500  {
6501  sink->setRange(sink->getMaxRange());
6502  }
6503  matchers[i] = new PhiOpNode(ValueRangeRef(new ValueRange(sink->getRange())), sink, nullptr);
6504  }
6505  else
6506  {
6507  parameters[i].first = nullptr;
6508  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Parameter " + STR(i) + " missing from function body");
6509  }
6510  }
6511 
6512  // Check if the function returns a supported value type. If not, no return
6513  // value matching is done
6514  const auto ret_type = tree_helper::GetFunctionReturnType(fd);
6515  bool noReturn = ret_type == nullptr || !isValidType(ret_type);
6517  "Function has " +
6518  (noReturn ? "no return type" : ("return type " + GET_CONST_NODE(ret_type)->get_kind_text())));
6519 
6520  // Creates the data structure which receives the return values of the
6521  // function, if there is any
6522  std::vector<VarNode*> returnVars;
6523  if(!noReturn)
6524  {
6525  const auto* SL = GetPointer<const statement_list>(GET_CONST_NODE(FD->body));
6526  for(const auto& idxBB : SL->list_of_bloc)
6527  {
6528  const auto& stmt_list = idxBB.second->CGetStmtList();
6529 
6530  if(stmt_list.size())
6531  {
6532  if(const auto* gr = GetPointer<const gimple_return>(GET_CONST_NODE(stmt_list.back())))
6533  {
6534  if(gr->op != nullptr) // Compiler defined return statements may be without argument
6535  {
6536  returnVars.push_back(CG->addVarNode(gr->op, function_id));
6537  }
6538  }
6539  }
6540  }
6541  }
6542  if(returnVars.empty() && !noReturn)
6543  {
6544 #ifndef NDEBUG
6545  if(isValidType(ret_type))
6546  {
6548  "---Function should return, but no return statement was found");
6549  }
6550  else
6551  {
6552  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Function return type not supported");
6553  }
6554 #endif
6555  noReturn = true;
6556  }
6558  std::string("Function ") + (noReturn ? "has no" : "has explicit") + " return statement" +
6559  (returnVars.size() > 1 ? "s" : ""));
6560 
6561  for(const auto& call : functionCalls)
6562  {
6564  const std::vector<tree_nodeRef>* args = nullptr;
6565  tree_nodeConstRef ret_var = nullptr;
6566  if(const auto* ga = GetPointer<const gimple_assign>(GET_CONST_NODE(call)))
6567  {
6568  const auto* ce = GetPointer<const call_expr>(GET_CONST_NODE(ga->op1));
6569  args = &ce->args;
6570  ret_var = ga->op0;
6571  }
6572  else if(const auto* gc = GetPointer<const gimple_call>(GET_CONST_NODE(call)))
6573  {
6574  args = &gc->args;
6575  }
6576  else
6577  {
6578  THROW_UNREACHABLE("Call statement should be a gimple_assign or a gimple_call");
6579  }
6580 
6581  THROW_ASSERT(args->size() == parameters.size(), "Function parameters and call arguments size mismatch");
6582  for(size_t i = 0; i < parameters.size(); ++i)
6583  {
6584  parameters[i].second = args->at(i);
6585  }
6586 
6587  // Do the inter-procedural construction of CG
6588  VarNode* to = nullptr;
6589  VarNode* from = nullptr;
6590 
6591  // Match formal and real parameters
6593  for(size_t i = 0; i < parameters.size(); ++i)
6594  {
6595  if(parameters[i].first == nullptr)
6596  {
6598  "Parameter " + STR(i) + " was constant, matching not necessary");
6599  continue;
6600  }
6602  GET_CONST_NODE(parameters[i].second)->ToString() + " bound to argument " +
6603  GET_CONST_NODE(parameters[i].first)->ToString());
6604  // Add real parameter to the CG
6605  from = CG->addVarNode(parameters[i].second, function_id);
6606 
6607  // Connect nodes
6608  matchers[i]->addSource(from);
6609  }
6611 
6612  // Match return values when return type is stored from caller
6613  if(!noReturn && GET_CONST_NODE(call)->get_kind() != gimple_call_K)
6614  {
6615  // Add caller instruction to the CG (it receives the return value)
6616  to = CG->addVarNode(ret_var, function_id);
6617  to->setRange(to->getMaxRange());
6618 
6619  auto* phiOp = new PhiOpNode(ValueRangeRef(new ValueRange(to->getRange())), to, nullptr);
6620  for(VarNode* var : returnVars)
6621  {
6622  phiOp->addSource(var);
6623  }
6624  CG->pushOperation(phiOp);
6625 
6626 #ifndef NDEBUG
6628  {
6629  std::string phiString =
6630  "Return variable " + GET_CONST_NODE(phiOp->getSink()->getValue())->ToString() + " = PHI<";
6631  for(size_t i = 0; i < phiOp->getNumSources(); ++i)
6632  {
6633  phiString += GET_CONST_NODE(phiOp->getSource(i)->getValue())->ToString() + ", ";
6634  }
6635  phiString[phiString.size() - 2] = '>';
6637  }
6638 #endif
6639  }
6640 
6641  // Real parameters are cleaned before moving to the next use (for safety's
6642  // sake)
6643  for(auto& pair : parameters)
6644  {
6645  pair.second = nullptr;
6646  }
6647  }
6649  for(auto* m : matchers)
6650  {
6651  if(m == nullptr)
6652  {
6653  continue;
6654  }
6655  CG->pushOperation(m);
6656 #ifndef NDEBUG
6658  {
6659  std::string phiString = GET_CONST_NODE(m->getSink()->getValue())->ToString() + " = PHI<";
6660  for(size_t i = 0; i < m->getNumSources(); ++i)
6661  {
6662  phiString += GET_CONST_NODE(m->getSource(i)->getValue())->ToString() + ", ";
6663  }
6664  phiString[phiString.size() - 2] = '>';
6666  }
6667 #endif
6668  }
6669 }
6670 
6671 // ========================================================================== //
6672 // RangeAnalysis
6673 // ========================================================================== //
6674 RangeAnalysis::RangeAnalysis(const application_managerRef AM, const DesignFlowManagerConstRef dfm,
6675  const ParameterConstRef par)
6676  : ApplicationFrontendFlowStep(AM, RANGE_ANALYSIS, dfm, par)
6677 #ifndef NDEBUG
6678  ,
6679  graph_debug(DEBUG_LEVEL_NONE),
6680  iteration(0),
6681  stop_iteration(std::numeric_limits<decltype(stop_iteration)>::max()),
6682  stop_transformation(std::numeric_limits<decltype(stop_transformation)>::max())
6683 #endif
6684  ,
6685  solverType(st_Cousot),
6686  requireESSA(true),
6687  execution_mode(RA_EXEC_NORMAL)
6688 {
6689  debug_level = parameters->get_class_debug_level(GET_CLASS(*this), DEBUG_LEVEL_NONE);
6690  const auto opts = SplitString(parameters->getOption<std::string>(OPT_range_analysis_mode), ",");
6691  CustomSet<std::string> ra_mode;
6692  for(const auto& opt : opts)
6693  {
6694  if(opt.size())
6695  {
6696  ra_mode.insert(opt);
6697  }
6698  }
6699  if(ra_mode.erase("crop"))
6700  {
6701  solverType = st_Crop;
6702  }
6703  if(ra_mode.erase("noESSA"))
6704  {
6705  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Range analysis: no Extended SSA required");
6706  requireESSA = false;
6707  }
6708 #ifndef NDEBUG
6709  if(ra_mode.erase("ro"))
6710  {
6711  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Range analysis: read-only mode enabled");
6712  execution_mode = RA_EXEC_READONLY;
6713  }
6714 #endif
6715  if(ra_mode.erase("skip"))
6716  {
6717  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Range analysis: skip mode enabled");
6718  execution_mode = RA_EXEC_SKIP;
6719  }
6720 #ifndef NDEBUG
6721  if(ra_mode.erase("debug_op"))
6722  {
6723  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Range analysis: range operations debug");
6724  OpNode::debug_level = debug_level;
6725  }
6726  if(ra_mode.erase("debug_graph"))
6727  {
6728  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Range analysis: graph debug");
6729  graph_debug = debug_level;
6730  Meet::debug_level = debug_level;
6731  }
6732  OPERATION_OPTION(ra_mode, add);
6733  OPERATION_OPTION(ra_mode, sub);
6734  OPERATION_OPTION(ra_mode, mul);
6735  OPERATION_OPTION(ra_mode, sdiv);
6736  OPERATION_OPTION(ra_mode, udiv);
6737  OPERATION_OPTION(ra_mode, srem);
6738  OPERATION_OPTION(ra_mode, urem);
6739  OPERATION_OPTION(ra_mode, shl);
6740  OPERATION_OPTION(ra_mode, shr);
6741  OPERATION_OPTION(ra_mode, abs);
6742  OPERATION_OPTION(ra_mode, negate);
6743  OPERATION_OPTION(ra_mode, not );
6744  OPERATION_OPTION(ra_mode, and);
6745  OPERATION_OPTION(ra_mode, or);
6746  OPERATION_OPTION(ra_mode, xor);
6747  OPERATION_OPTION(ra_mode, sext);
6748  OPERATION_OPTION(ra_mode, zext);
6749  OPERATION_OPTION(ra_mode, trunc);
6750  OPERATION_OPTION(ra_mode, min);
6751  OPERATION_OPTION(ra_mode, max);
6752  OPERATION_OPTION(ra_mode, float_pack);
6753  OPERATION_OPTION(ra_mode, view_convert);
6754  OPERATION_OPTION(ra_mode, load);
6755  OPERATION_OPTION(ra_mode, ternary);
6756  OPERATION_OPTION(ra_mode, bit_phi);
6757  if(ra_mode.size() && ra_mode.begin()->size())
6758  {
6759  THROW_ASSERT(ra_mode.size() <= 2, "Too many range analysis options left to parse");
6760  auto it = ra_mode.begin();
6761  if(ra_mode.size() == 2)
6762  {
6763  auto tr = ++ra_mode.begin();
6764  if(it->front() == 't')
6765  {
6766  it = ++ra_mode.begin();
6767  tr = ra_mode.begin();
6768  }
6769  THROW_ASSERT(tr->front() == 't', "Invalid range analysis option: " + *tr);
6770  stop_transformation = std::strtoull(tr->data() + sizeof(char), nullptr, 10);
6771  if(stop_transformation == 0)
6772  {
6773  THROW_ERROR("Invalid range analysis option: " + *tr);
6774  }
6776  "Range analysis: only " + STR(stop_transformation) + " transformation" +
6777  (stop_transformation > 1 ? "s" : "") + " will run on last iteration");
6778  }
6779  if(it->front() == 'i')
6780  {
6781  stop_iteration = std::strtoull(it->data() + sizeof(char), nullptr, 10);
6782  }
6783  else
6784  {
6785  stop_iteration = std::strtoull(it->data(), nullptr, 10);
6786  }
6787  if(stop_iteration == 0)
6788  {
6789  THROW_ERROR("Invalid range analysis option: " + *it);
6790  }
6792  "Range analysis: only " + STR(stop_iteration) + " iteration" + (stop_iteration > 1 ? "s" : "") +
6793  " will run");
6794  }
6795 #else
6796  THROW_ASSERT(ra_mode.empty(), "Invalid range analysis mode falgs. (" + *ra_mode.begin() + ")");
6797 #endif
6798 }
6799 
6800 RangeAnalysis::~RangeAnalysis() = default;
6801 
6804 {
6806  if(execution_mode == RA_EXEC_SKIP)
6807  {
6808  return relationships;
6809  }
6810  switch(relationship_type)
6811  {
6812  case DEPENDENCE_RELATIONSHIP:
6813  {
6814  if(!parameters->getOption<int>(OPT_gcc_openmp_simd))
6815  {
6816  relationships.insert(std::make_pair(BIT_VALUE_OPT, ALL_FUNCTIONS));
6817  }
6818  if(requireESSA)
6819  {
6820  relationships.insert(std::make_pair(ESSA, ALL_FUNCTIONS));
6821  }
6822  relationships.insert(std::make_pair(BLOCK_FIX, ALL_FUNCTIONS));
6823  relationships.insert(std::make_pair(CALL_GRAPH_BUILTIN_CALL, ALL_FUNCTIONS));
6824  relationships.insert(std::make_pair(COMPUTE_IMPLICIT_CALLS, ALL_FUNCTIONS));
6825  relationships.insert(std::make_pair(DETERMINE_MEMORY_ACCESSES, ALL_FUNCTIONS));
6826  relationships.insert(std::make_pair(EXTRACT_GIMPLE_COND_OP, ALL_FUNCTIONS));
6827  relationships.insert(std::make_pair(FUNCTION_ANALYSIS, WHOLE_APPLICATION));
6828  relationships.insert(std::make_pair(IR_LOWERING, ALL_FUNCTIONS));
6829  if(parameters->isOption(OPT_soft_float) && parameters->getOption<bool>(OPT_soft_float))
6830  {
6831  relationships.insert(std::make_pair(SOFT_FLOAT_CG_EXT, ALL_FUNCTIONS));
6832  }
6833  relationships.insert(std::make_pair(USE_COUNTING, ALL_FUNCTIONS));
6834  break;
6835  }
6836  case PRECEDENCE_RELATIONSHIP:
6837  {
6838  relationships.insert(std::make_pair(UN_COMPARISON_LOWERING, ALL_FUNCTIONS));
6839  break;
6840  }
6841  case INVALIDATION_RELATIONSHIP:
6842  {
6843  break;
6844  }
6845  default:
6846  {
6847  THROW_UNREACHABLE("");
6848  }
6849  }
6850  return relationships;
6851 }
6852 
6854  const DesignFlowStep::RelationshipType relationship_type)
6855 {
6856  if(relationship_type == INVALIDATION_RELATIONSHIP)
6857  {
6858  if(!parameters->getOption<int>(OPT_gcc_openmp_simd))
6859  {
6860  const auto dfm = design_flow_manager.lock();
6861  const auto design_flow_graph = dfm->CGetDesignFlowGraph();
6862  for(const auto f_id : fun_id_to_restart)
6863  {
6864  const auto bv_signature = FunctionFrontendFlowStep::ComputeSignature(BIT_VALUE, f_id);
6865  const auto frontend_bv = dfm->GetDesignFlowStep(bv_signature);
6866  THROW_ASSERT(frontend_bv != NULL_VERTEX, "step " + bv_signature + " is not present");
6867  const auto bv = design_flow_graph->CGetDesignFlowStepInfo(frontend_bv)->design_flow_step;
6868  relationships.insert(bv);
6869  }
6870  }
6871  fun_id_to_restart.clear();
6872  }
6873  ApplicationFrontendFlowStep::ComputeRelationships(relationships, relationship_type);
6874 }
6875 
6876 bool RangeAnalysis::HasToBeExecuted() const
6877 {
6878 #ifndef NDEBUG
6879  if(iteration >= stop_iteration || execution_mode == RA_EXEC_SKIP)
6880 #else
6881  if(execution_mode == RA_EXEC_SKIP)
6882 #endif
6883  {
6884  return false;
6885  }
6886  std::map<unsigned int, unsigned int> cur_bitvalue_ver;
6887  std::map<unsigned int, unsigned int> cur_bb_ver;
6888  const auto CGMan = AppM->CGetCallGraphManager();
6889  for(const auto i : CGMan->GetReachedBodyFunctions())
6890  {
6891  const auto FB = AppM->CGetFunctionBehavior(i);
6892  cur_bitvalue_ver[i] = FB->GetBitValueVersion();
6893  cur_bb_ver[i] = FB->GetBBVersion();
6894  }
6895  return cur_bb_ver != last_bb_ver || cur_bitvalue_ver != last_bitvalue_ver;
6896 }
6897 
6899 {
6900  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Range Analysis step");
6901  fun_id_to_restart.clear();
6902 }
6903 
6905 {
6906 #ifndef NDEBUG
6907  if(iteration >= stop_iteration || execution_mode == RA_EXEC_SKIP)
6908 #else
6909  if(execution_mode == RA_EXEC_SKIP)
6910 #endif
6911  {
6912  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Range analysis no execution mode enabled");
6914  }
6916 
6917  // Initialize constraint graph
6918  ConstraintGraphRef CG;
6919  switch(solverType)
6920  {
6921  case st_Cousot:
6922  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Using jump-set abstract operators");
6923  CG.reset(new Cousot(AppM,
6924 #ifndef NDEBUG
6925  debug_level, graph_debug));
6926 #else
6928 #endif
6929  break;
6930  case st_Crop:
6931  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Using standard abstract operators");
6932  CG.reset(new CropDFS(AppM,
6933 #ifndef NDEBUG
6934  debug_level, graph_debug));
6935 #else
6937 #endif
6938  break;
6939  default:
6940  THROW_UNREACHABLE("Unknown solver type " + STR(solverType));
6941  break;
6942  }
6943 
6944  // Analyse only reached functions
6945 #if defined(EARLY_DEAD_CODE_RESTART) || !defined(NDEBUG)
6946  const auto TM = AppM->get_tree_manager();
6947 #endif
6948  CustomOrderedSet<unsigned int> rb_funcs = AppM->CGetCallGraphManager()->GetReachedBodyFunctions();
6949 
6950 #ifdef EARLY_DEAD_CODE_RESTART
6951  for(const auto f : rb_funcs)
6952  {
6953  bool dead_code_necessary = CG->buildGraph(f);
6954  if(dead_code_necessary)
6955  {
6956  fun_id_to_restart.insert(f);
6957  }
6958  }
6959  if(fun_id_to_restart.size())
6960  {
6961  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Following functions have unpropagated constants:");
6963  for(const auto f_id : fun_id_to_restart)
6964  {
6965  const auto FB = AppM->GetFunctionBehavior(f_id);
6968  tree_helper::print_type(TM, f_id, false, true, false, 0U,
6970  FB->UpdateBBVersion();
6971  }
6973  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Unpropagated constants detected, aborting...");
6975  }
6976 #else
6977  for(const auto& f : rb_funcs)
6978  {
6979  CG->buildGraph(f);
6980  }
6981 #endif
6982 
6983  // Top functions are not called by any other functions, so they do not have any call statement to analyse
6984  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Parameters and return value propagation...");
6985  for(const auto& top_fn : AppM->CGetCallGraphManager()->GetRootFunctions())
6986  {
6988  tree_helper::print_type(TM, top_fn, false, true, false, 0U,
6990  AppM->CGetFunctionBehavior(top_fn)->CGetBehavioralHelper()))) +
6991  " is top function");
6992  TopFunctionUserHits(top_fn, AppM, CG, debug_level);
6993  rb_funcs.erase(top_fn);
6994  }
6995  // The two operations are split because the CallMap is built for all functions in buildGraph
6996  // then it is used from ParmAndRetValPropagation
6997  for(const auto f : rb_funcs)
6998  {
6999  ParmAndRetValPropagation(f, AppM, CG, debug_level);
7000  }
7001  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Parameters and return value propagation completed");
7002  CG->buildVarNodes();
7003 
7004 #ifndef NDEBUG
7005  CG->findIntervals(parameters, GetName() + "(" + STR(iteration) + ")");
7006  ++iteration;
7007 #else
7008  CG->findIntervals();
7009 #endif
7010 
7012 #ifndef NDEBUG
7013  const auto modified = finalize(CG);
7014  if(stop_iteration != std::numeric_limits<decltype(stop_iteration)>::max())
7015  {
7017  "Iteration " + STR(iteration) + "/" + STR(stop_iteration) + "completed (" +
7018  STR(stop_iteration - iteration) + " to go)");
7019  }
7020  if(modified)
7021  {
7022  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Variable ranges updated");
7023  }
7024  else
7025  {
7026  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Variable ranges reached fixed point");
7027  }
7029 #else
7031 #endif
7032 }
7033 
7034 bool RangeAnalysis::finalize(ConstraintGraphRef CG)
7035 {
7036  THROW_ASSERT(CG, "");
7037  const auto& vars = std::static_pointer_cast<const ConstraintGraph>(CG)->getVarNodes();
7038  CustomSet<unsigned int> modifiedFunctionsBit;
7039 
7040 #ifndef NDEBUG
7041  if(execution_mode >= RA_EXEC_READONLY)
7042  {
7043  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Bounds for " + STR(vars.size()) + " variables");
7045  for(const auto& varNode : vars)
7046  {
7048  "Range " + varNode.second->getRange()->ToString() + " for " +
7049  GET_CONST_NODE(varNode.first)->ToString());
7050  }
7052  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "IR update not applied in read-only mode");
7053  }
7054  else
7055  {
7056 #endif
7057  const auto TM = AppM->get_tree_manager();
7058 
7059 #ifndef NDEBUG
7060  unsigned long long updated = 0;
7061 #endif
7062  INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Bounds for " + STR(vars.size()) + " variables");
7064  for(const auto& varNode : vars)
7065  {
7066 #ifndef NDEBUG
7067  if(iteration == stop_iteration && updated >= stop_transformation)
7068  {
7070  "Max required transformations performed. IR update aborted.");
7071  break;
7072  }
7073 #endif
7074  if(const auto ut = varNode.second->updateIR(TM, debug_level, AppM))
7075  {
7076  if(ut & ut_BitValue)
7077  {
7078  const auto funID = varNode.second->getFunctionId();
7079  modifiedFunctionsBit.insert(funID);
7080 #ifndef NDEBUG
7081  ++updated;
7082 #endif
7083  }
7084  }
7085  }
7088  "Bounds updated for " + STR(updated) + "/" + STR(vars.size()) + " variables");
7089 #ifndef NDEBUG
7090  }
7091 #endif
7092 
7093  const auto rbf = AppM->CGetCallGraphManager()->GetReachedBodyFunctions();
7094  const auto cgm = AppM->CGetCallGraphManager();
7095  const auto cg = cgm->CGetCallGraph();
7096 #ifndef NDEBUG
7097  const auto TM = AppM->get_tree_manager();
7098 #endif
7099 
7101  "Modified BitValues " + STR(modifiedFunctionsBit.size()) + " functions:");
7103  for(const auto fUT : modifiedFunctionsBit)
7104  {
7106  tree_helper::print_type(TM, fUT, false, true, false, 0U,
7108  AppM->CGetFunctionBehavior(fUT)->CGetBehavioralHelper()))));
7109  fun_id_to_restart.insert(fUT);
7110  }
7112 
7113  for(const auto f : rbf)
7114  {
7115  const auto FB = AppM->GetFunctionBehavior(f);
7116  auto isInBit = fun_id_to_restart.count(f);
7117  if(isInBit)
7118  {
7119  last_bb_ver[f] = FB->GetBBVersion();
7120  last_bitvalue_ver[f] = FB->UpdateBitValueVersion();
7121  }
7122  else
7123  {
7124  last_bb_ver[f] = FB->GetBBVersion();
7125  last_bitvalue_ver[f] = FB->GetBitValueVersion();
7126  }
7127  }
7128  return !fun_id_to_restart.empty();
7129 }
#define GET_NODE(t)
Macro used to hide implementation details when accessing a tree_node from another tree_node...
Definition: tree_node.hpp:343
void setIntersect(const RangeConstRef &newIntersect)
Changes the interval of the operation.
static bool IsStore(const tree_nodeConstRef &tn, const CustomOrderedSet< unsigned int > &fun_mem_data)
Return true if the tree node is a gimple_assign writing something which will be allocated in memory...
const VarNode * getSource(size_t index) const
Return source identified by index.
std::string convert_fp_to_string(std::string num, unsigned long long precision)
convert a real number stored in a string into a string of bits with a given precision ...
This struct specifies the integer_cst node.
Definition: tree_node.hpp:3242
APInt & extOrTrunc(bw_t bw, bool sign)
Definition: APInt.cpp:285
kind getOpcode() const
Return the opcode of the operation.
integer_cst_t value
The value of the integer cast.
Definition: tree_node.hpp:3253
kind getOperation() const
Returns the opcode of the operation that create this interval.
unsigned int evaluateBranch(const tree_nodeRef br_op, const blocRef branchBB, int debug_level)
PhiOpNode & operator=(const PhiOpNode &)=delete
void print(std::ostream &OS) const override
Prints the content of the operation.
#define DEBUG_LEVEL_VERY_PEDANTIC
extremely verbose debugging print is performed.
Definition: Range.hpp:56
Data structure representing the entire HLS information.
Step does not exits.
CustomMap< unsigned int, std::pair< bool, std::vector< tree_nodeConstRef > >> ParmMap
#define INDENT_DBG_MEX(dbgLevel, curDbgLevel, mex)
We are producing a debug version of the program, so the message is printed;.
static bool enable_mul
ValueRangeType
static APInt getSignedMinValue(bw_t bw)
Definition: APInt.cpp:434
unsigned int GetBitValueVersion() const
Return the version of the bitvalue information.
const tree_nodeConstRef bound
The bound. It is a node which limits the interval of this range.
static bool widen(OpNode *op, const std::vector< APInt > &constantvector)
This is the meet operator of the growth analysis.
virtual RangeRef eval() const =0
Given the input of the operation and the operation that will be performed, evaluates the result of th...
static bool enable_sdiv
RangeConstRef range
static std::function< OpNode *(NodeContainer *)> opCtorGenerator(const tree_nodeConstRef &stmt, unsigned int, const FunctionBehaviorConstRef &FB, const tree_managerConstRef &TM, const application_managerRef &AppM)
static const APInt & getFirstGreaterFromVector(const std::vector< APInt > &constantvector, const APInt &val)
File containing functions and utilities to support the printing of debug messagges.
SymbRange & operator=(const SymbRange &)=delete
bool HasToBeExecuted() const override
Check if this step has actually to be executed.
virtual ValueRangeType getValueId() const
unsigned int UpdateBBVersion()
Update the version of the basic block intermediate representation.
static bool classof(ControlDepNode const *)
static int debug_level
static bool enable_udiv
std::map< tree_nodeConstRef, CustomSet< OpNode * >, tree_reindexCompare > UseMap
std::string ToString() const
Print this node as string in gimple format.
#define DEBUG_LEVEL_PEDANTIC
very verbose debugging print is performed.
OperationId getValueId() const override
updateType
Step successfully executed.
ValueRange & operator=(const ValueRange &)=delete
#define CASE_BINARY_EXPRESSION
This macro collects all case labels for binary_expr objects.
Definition: tree_node.hpp:463
A constraint like sink = phi(src1, src2, ..., srcN)
void visit(const tree_nodeConstRef &V, std::stack< tree_nodeConstRef > &stack, const UseMap &useMap)
size_t getNumSources() const
return the number of sources
#define GET_CLASS(obj)
Macro returning the actual type of an object.
tree_nodeRef branchOpRecurse(tree_nodeRef op, tree_nodeRef stmt=nullptr)
Definition: eSSA.cpp:238
PhiOpNode(const ValueRangeRef &intersect, VarNode *sink, const tree_nodeConstRef &inst)
RangeConstRef getRange() const
Returns the range of this interval.
OperationId getValueId() const override
ConditionalValueRange(const tree_nodeConstRef &_V, const std::map< unsigned int, ValueRangeRef > &_bbVR)
static bool enable_bit_phi
kind getOpcode() const
Return the opcode of the operation.
tree_nodeRef name
name field contains an identifier_node used to represent a name.
Definition: tree_node.hpp:883
A constraint like sink = operation(source) [l, u] Examples: unary instructions such as truncation...
VarNode * getSource() const
Returns the source of the operation.
Definition of the class representing a generic C application.
const std::vector< std::string > SplitString(const std::string &input, const std::string &separators)
Function which splits a string into tokens.
static bool IsArrayEquivType(const tree_nodeConstRef &type)
Return true if treenode is an array or it is equivalent to an array (record recursively having a sing...
#define CASE_DECL_NODES
NOTE that cast_expr is a unary expression but it could not be included in the CASE_UNARY_EXPRESSION b...
Definition: tree_node.hpp:672
This is an interval that contains a symbolic limit, which is given by the bounds of a program name...
static std::string print_type(const tree_managerConstRef &TM, unsigned int type, bool global=false, bool print_qualifiers=false, bool print_storage=false, unsigned int var=0, const var_pp_functorConstRef &vppf=var_pp_functorConstRef(), const std::string &prefix="", const std::string &tail="")
Print a type and its variable in case var is not zero.
VarNode * getSource3() const
Returns the third operand of this operation.
const ConditionalValueRanges & getCVR() const
static int debug_level
size_t getNumSources() const
return the number of sources
#define RA_EXEC_READONLY
RelationshipType
The relationship type.
struct definition of the function_decl tree node.
Definition: tree_node.hpp:2759
void setRange(const RangeConstRef &newRange)
Sets the range of this interval to another range.
static bool isBetter(const std::string &a_string, const std::string &b_string)
static bool classof(OpNode const *BO)
static std::string GetString(const enum kind k)
Given a kind, return the corresponding string.
Definition: tree_node.cpp:120
static tree_nodeConstRef CGetElements(const tree_nodeConstRef &type)
Given an array or a vector return the element type.
void print(std::ostream &OS) const override
Prints the content of the interval.
Class specification of the graph structures.
~RangeAnalysis() override
Destructor.
APInt::bw_t bw_t
Definition: Range.hpp:66
static std::function< OpNode *(NodeContainer *)> opCtorGenerator(const tree_nodeConstRef &, unsigned int, const FunctionBehaviorConstRef &, const tree_managerConstRef &, const application_managerRef &)
static bool enable_float_pack
CustomOrderedMap< T, U > CustomMap
Definition: custom_map.hpp:167
Definition: Range.hpp:63
ConditionalValueRanges _cvrMap
static std::function< OpNode *(NodeContainer *)> opCtorGenerator(const tree_nodeConstRef &stmt, unsigned int, const FunctionBehaviorConstRef &FB, const tree_managerConstRef &TM, const application_managerRef &AppM)
void printDot(std::ostream &OS) const override
Range::bw_t bw_t
Definition: Range.cpp:69
RangeRef eval() const override
Computes the interval of the sink based on the interval of the sources, the operation and the interva...
static APInt getSignedMaxValue(bw_t bw)
Definition: APInt.cpp:429
A simple interface to token object of the raw files.
VarNode * SymbolicSource
std::vector< tree_nodeConstRef > getSources() const override
static bool classof(OpNode const *BO)
ValueRange(const RangeConstRef &range)
virtual ~NodeContainer()
static const unsigned int EXIT_BLOCK_ID
constant identifying the exit basic block
std::vector< tree_nodeConstRef > getSources() const override
Nuutila(const VarNodes &varNodes, UseMap &useMap, const SymbMap &symbMap, int _debug_level)
ControlDepNode(VarNode *sink, VarNode *source)
static bool enable_negate
#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
#define min(x, y)
std::deque< tree_nodeConstRef >::const_reverse_iterator const_iterator
static bool enable_trunc
This struct specifies the gimple_cond node.
Definition: tree_node.hpp:2345
static void shl(size_t p[2], int n)
TernaryOpNode(const ValueRangeRef &intersect, VarNode *sink, const tree_nodeConstRef &inst, VarNode *source1, VarNode *source2, VarNode *source3, kind opcode)
This class contains the base representation for a generic frontend flow step which works on a single ...
std::vector< tree_nodeConstRef > getSources() const override
static std::function< OpNode *(NodeContainer *)> opCtorGenerator(const tree_nodeConstRef &stmt, unsigned int function_id, const FunctionBehaviorConstRef &FB, const tree_managerConstRef &TM, const application_managerRef &AppM)
#define abs(x)
Definition: main.c:3
struct vcFloat::_FP_STRUCT_LAYOUT __attribute__((packed))
static const APInt Max
Definition: Range.hpp:163
void ComputeRelationships(DesignFlowStepSet &relationships, const DesignFlowStep::RelationshipType relationship_type) override
Compute the relationships of a step with other steps.
RangeConstRef solveFuture(const VarNode *bound, const VarNode *sink) const
Replace symbolic bound with hard-wired constants.
Data structure describing a basic block at tree level.
struct Intersection intersection(float dist, float3 color)
static bool enable_sub
This class is used to perform the re-index of all tree nodes.
const VarNode * getSource(size_t index) const
Return source identified by index.
static bool enable_min
static RangeRef constructor_range(const tree_managerConstRef TM, const tree_nodeConstRef tn, const RangeConstRef init)
static bool crop(OpNode *op)
void printDot(std::ostream &OS) const override
VarNode * getSource1() const
Returns the first operand of this operation.
static bool classof(TernaryOpNode const *)
void init(bool outside)
Initializes the value of the node.
#define RESULT_DISABLED_OPTION(x, var, stdResult)
redefinition of map to manage ordered/unordered structures
static bool enable_load
static bool classof(OpNode const *BO)
std::map< tree_nodeConstRef, VarNode *, tree_reindexCompare > VarNodes
void printDot(std::ostream &OS) const override
OpNode(const ValueRangeRef &intersect, VarNode *sink, const tree_nodeConstRef &inst)
We do not want people creating objects of this class, but we want to inherit from it...
virtual enum kind get_kind() const =0
Virtual function returning the type of the actual class.
kind getOpcode() const
Return the opcode of the operation.
const VarNodes & variables
static bool enable_shl
#define STR(s)
Macro which performs a lexical_cast to a string.
SigmaOpNode(const ValueRangeRef &intersect, VarNode *sink, const tree_nodeConstRef &inst, VarNode *source, VarNode *SymbolicSource, kind opcode)
Auxiliary methods for manipulating string.
OperationId getValueId() const override
VarNode * getSource2() const
Returns the second operand of this operation.
std::map< tree_nodeConstRef, CustomSet< VarNode * >, tree_reindexCompare > components
void addVR(unsigned int bbi, const ValueRangeRef &cvr)
Add an interval associated to a new basic block.
#define max
Definition: backprop.h:17
VarNode * getSource() const
Returns the source of the operation.
std::string ToString(ActorGraphBackend_Type actor_graph_backend_type)
Header include.
const_iterator cend() const
const tree_nodeConstRef & getInstruction() const
Return the instruction that originated this op node.
std::vector< tree_nodeConstRef > getSources() const override
bool operator()(const tree_nodeConstRef &lhs, const tree_nodeConstRef &rhs) const
static bool fixed(OpNode *op)
static bool classof(PhiOpNode const *)
std::vector< tree_nodeConstRef > getSources() const override
static bool enable_abs
static const std::vector< std::function< std::function< OpNode *(NodeContainer *)> const tree_nodeConstRef &, unsigned int, const FunctionBehaviorConstRef &, const tree_managerConstRef &, const application_managerRef &)> > _opCtorGenerators
RangeConstRef getRange() const
Returns the range of the variable represented by this node.
void storeAbstractState()
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...
unsigned int UpdateBitValueVersion()
Update the version of the bitvalue information.
std::deque< tree_nodeConstRef >::reverse_iterator iterator
#define THROW_UNREACHABLE(str_expr)
helper function used to specify that some points should never be reached
Definition: exceptions.hpp:292
virtual std::string get_kind_text() const =0
Virtual function returning the name of the actual class.
const tree_nodeConstRef inst
const tree_nodeConstRef & getVar() const
Get the value associated to the switch.
void printDot(std::ostream &OS) const override
Standard functor that returns the name of a variable.
static bool enable_zext
VarNode * getSource2() const
Returns the second operand of this operation.
void printDot(std::ostream &OS) const override
const DefMap & getDefs() const
#define CASE_MISCELLANEOUS
void addSource(const VarNode *newsrc)
Add source to the vector of sources.
SymbRange(const RangeConstRef &range, const tree_nodeConstRef &bound, kind pred)
VarNode * addVarNode(const tree_nodeConstRef &V, unsigned int function_id)
BinaryOpNode(const ValueRangeRef &intersect, VarNode *sink, const tree_nodeConstRef &inst, VarNode *source1, VarNode *source2, kind opcode)
Specific type of UnaryOp used to represent sigma functions.
std::map< tree_nodeConstRef, OpNode *, tree_reindexCompare > DefMap
RangeAnalysis(const application_managerRef AM, const DesignFlowManagerConstRef dfm, const ParameterConstRef parameters)
Constructor.
#define CASE_QUATERNARY_EXPRESSION
This macro collects all case labels for quaternary_expr objects.
Definition: tree_node.hpp:574
const CustomSet< VarNode * > & getComponent(const tree_nodeConstRef &n) const
static bool classof(UnaryOpNode const *)
void print(int x)
Specific type of OpNode used in Nuutila&#39;s strongly connected components algorithm.
#define CASE_UNARY_EXPRESSION
This macro collects all case labels for unary_expr objects.
Definition: tree_node.hpp:371
std::deque< tree_nodeConstRef > worklist
static RangeRef makeSatisfyingCmpRegion(kind pred, const RangeConstRef &Other)
Definition: Range.cpp:2529
OpNode * addOperation(const tree_nodeConstRef &stmt, unsigned int function_id, const FunctionBehaviorConstRef &FB, const tree_managerConstRef &TM, const application_managerRef &AppM)
std::string ToString() const
DesignFlowStep_Status Exec() override
perform the range analysis
const tree_nodeConstRef & getValue() const
Returns the variable represented by this node.
static bool enable_sext
This class represents a generic operation in our analysis.
static integer_cst_t get_integer_cst_value(const integer_cst *ic)
Convert a integer_cst in a long long value.
static bool enable_add
std::map< tree_nodeConstRef, CustomSet< OpNode * >, tree_reindexCompare > SymbMap
RangeRef getMaxRange() const
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
static const bw_t max_digits
Definition: Range.hpp:161
#define FD(x)
Definition: aes.c:8
Classes to describe design flow graph.
tree_nodeRef body
body field is the saved representation of the body of the entire function.
Definition: tree_node.hpp:2870
static APInt getMaxValue(bw_t bw)
Definition: APInt.cpp:419
VarNode * getSink() const
Returns the target of the operation, that is, where the result will be stored.
#define index(x, y)
Definition: Keccak.c:74
static bool classof(OpNode const *BO)
kind
std::vector< const VarNode * > sources
reference to the memory access operand
tree_nodeRef GetTreeReindex(const unsigned int i)
Return a tree_reindex wrapping the i-th tree_node.
void print(std::ostream &OS) const override
Prints the content of the operation.
kind pred
The predicate of the operation in which this interval takes part.
std::list< std::pair< tree_nodeRef, unsigned int > > list_of_cond
The list of pair condition basic block.
LoadOpNode(const ValueRangeRef &intersect, VarNode *sink, const tree_nodeConstRef &inst)
bool finalize(ConstraintGraphRef)
RangeRef eval() const override
Computes the interval of the sink based on the interval of the sources, the operation and the interva...
void print(std::ostream &OS) const override
Prints the content of the operation.
const tree_nodeConstRef V
std::map< unsigned int, ValueRangeRef > bbVR
const_iterator cbegin() const
RangeRef eval() const override
Computes the interval of the sink based on the interval of the sources, the operation and the interva...
VarNode(const tree_nodeConstRef &_V, unsigned int _function_id)
The ctor.
#define GET_CONST_NODE(t)
Definition: tree_node.hpp:347
const BehavioralHelperConstRef CGetBehavioralHelper() const
Returns the helper associated with the function.
void addSource(const VarNode *newsrc)
Add source to the vector of sources.
static unsigned long long Size(const tree_nodeConstRef &t)
DesignFlowStep_Status
The status of a step.
ValueRangeRef intersect
The range of the operation.
iterator end()
Eliminate dead code.
OperationId getValueId() const override
void print(std::ostream &OS) const override
Prints the content of the operation.
tree_nodeRef op0
The first operand of the ternary expression.
Definition: tree_node.hpp:2353
std::string ToString() const
virtual void print(std::ostream &OS) const =0
Prints the content of the operation.
Call graph hierarchy.
Class defining some useful functions to create tree nodes and to manipulate the tree manager...
#define DEBUG_LEVEL_NONE
no debugging print is performed.
virtual void printDot(std::ostream &OS) const =0
VarNode * getSource1() const
Returns the first operand of this operation.
#define THROW_ERROR(str_expr)
helper function used to throw an error in a standard way
Definition: exceptions.hpp:263
SigmaOpNode & operator=(const SigmaOpNode &)=delete
Wrapper of design_flow.
CONSTREF_FORWARD_DECL(ValueRange)
static bool classof(OpNode const *BO)
int result[SIZE]
Definition: adpcm.c:800
const std::map< unsigned int, ValueRangeRef > & getVR() const
Get the interval associated to the switch case idx.
void setRange(const RangeConstRef &newInterval)
Changes the status of the variable represented by this node.
RangeRef eval() const override
Given the input of the operation and the operation that will be performed, evaluates the result of th...
static bool growth(OpNode *op)
#define CASE_TYPE_NODES
This macro collects all case labels for type objects.
Definition: tree_node.hpp:581
This file collects some utility functions.
static void constrainSSA(ssa_name *op_ssa, tree_managerRef TM)
#define L
Definition: spmv.h:13
std::vector< tree_nodeRef > list_of_args
args field holds a chain of parm_decl nodes for the arguments.
Definition: tree_node.hpp:2841
static int debug_level
UnaryOpNode & operator=(const UnaryOpNode &)=delete
static bool enable_view_convert
void print(std::ostream &OS) const override
Prints the content of the operation.
std::deque< bit_lattice > string_to_bitstring(const std::string &s)
inverse of bitstring_to_string
static tree_nodeRef find_obj_type_ref_function(const tree_nodeConstRef &tn)
Given the tree_node of an obj_type_ref return the tree_node of the called function.
OperationId getValueId() const override
void addControlDependenceEdges(UseMap &useMap, const SymbMap &symbMap, const VarNodes &vars)
Definition: APInt.hpp:53
const OpNodes & getOpNodes() const
static bool classof(UnaryOpNode const *UO)
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.
BinaryOpNode & operator=(const BinaryOpNode &)=delete
static bool enable_and
ControlDepNode & operator=(const ControlDepNode &)=delete
Class performing some optimizations on the IR exploiting Bit Value analysis.
ConditionalValueRange(const tree_nodeConstRef &_V, unsigned int TrueBBI, unsigned int FalseBBI, const ValueRangeRef &TrueVR, const ValueRangeRef &FalseVR)
void init(int bucket[BUCKETSIZE])
Definition: sort.c:42
virtual OperationId getValueId() const =0
UnaryOpNode(const ValueRangeRef &intersect, VarNode *sink, const tree_nodeConstRef &inst, VarNode *source, kind opcode)
std::string ToString() const
Definition: tree.c:10
ValueRangeConstRef getIntersect() const
Returns the range of the operation.
void ComputeRelationships(DesignFlowStepSet &relationship, const DesignFlowStep::RelationshipType relationship_type) override
Compute the relationships of a step with other steps.
void add(int accelnum, int startidx, int endidx)
Definition: add.c:11
void print(std::ostream &OS) const override
Prints the content of the operation.
static bool enable_ternary
OperationId getValueId() const override
#define CASE_CST_NODES
This macro collects all case labels for cast nodes.
Definition: tree_node.hpp:689
string full_name
Definition: test_panda.py:841
static const APInt & getFirstLessFromVector(const std::vector< APInt > &constantvector, const APInt &val)
char tr[16206]
Definition: TR.h:1
static bool classof(LoadOpNode const *)
static bool classof(OpNode const *)
static bool enable_or
static bool enable_max
static bool enable_not
void printDot(std::ostream &OS) const override
int el
Definition: adpcm.c:105
void * pop(node_stack **head)
Definition: tree.c:62
Class specification of the tree_reindex support class.
static const unsigned int ENTRY_BLOCK_ID
constant identifying the entry basic block
#define CASE_FAKE_NODES
This macro collects all case labels for fake or empty nodes.
Definition: tree_node.hpp:635
char getAbstractState()
VarNode * sink
std::map< tree_nodeConstRef, int, tree_reindexCompare > dfs
RangeRef eval() const override
Computes the interval of the sink based on the interval of the sources, the operation and the interva...
Class specification of the basic_block structure.
unsigned int GetBBVersion() const
Return the version of the basic block intermediate representation.
int updateIR(const tree_managerRef &TM, int debug_level, application_managerRef AppM)
static RangeRef evaluate(kind opcode, bw_t bw, const RangeConstRef &op1, const RangeConstRef &op2, bool opSigned)
static bool narrow(OpNode *op, const std::vector< APInt > &constantvector)
This is the meet operator of the cropping analysis.
ValueRangeType getValueId() const override
int test(NodeId var_2, PropertyId p_var_3, PropertyId p_var_4, PropertyId p_var_5, PropertyId p_var_7, PropertyId p_var_9, PropertyId p_var_11)
This struct specifies a multi-way-if construct.
static bool classof(SigmaOpNode const *)
std::set< tree_nodeConstRef, tree_reindexCompare > inComponent
unsigned int function_id
ID of the associated function.
UseMap & getUses()
static bool classof(OpNode const *BO)
static bw_t neededBits(const APInt &a, const APInt &b, bool sign)
Definition: Range.cpp:360
std::map< tree_nodeConstRef, tree_nodeConstRef, tree_reindexCompare > root
static APInt getMinValue(bw_t bw)
Definition: APInt.cpp:424
Data structures used in operations graph.
REF_FORWARD_DECL(ValueRange)
static tree_nodeConstRef CGetType(const tree_nodeConstRef &node)
Return the treenode of the type of node.
T * get() const
Definition: refcount.hpp:169
char abstractState
Used by the crop meet operator.
#define RETURN_DISABLED_OPTION(x, bw)
std::vector< const VarNode * > sources
virtual std::vector< tree_nodeConstRef > getSources() const =0
A constraint like sink = source1 operation source2 intersect [l, u].
Classes specification of the tree_node data structures not present in the gcc.
this class is used to manage the command-line or XML options.
bool isCompare(const struct binary_expr *condition)
Definition: eSSA.cpp:231
T * GetVR(const ValueRange *t)
RangeRef eval() const override
Computes the interval of the sink based on the interval of the sources, the operation and the interva...
#define CASE_CPP_NODES
This macro collects all case labels for cpp nodes.
Definition: tree_node.hpp:644
void solveFuture(VarNode *future)
Replace symbolic intervals with hard-wired constants.
unsigned int getFunctionId() const
RangeRef eval() const override
Given the input of the operation and the operation that will be performed, evaluates the result of th...
virtual void print(std::ostream &OS) const
Pretty print.
Definition: Range.hpp:59
static unsigned int get_base_index(const tree_managerConstRef &TM, const unsigned int index)
Retrun the base address of a memory access.
static const APInt Min
Definition: Range.hpp:162
std::string bit_values
for each bit of the SSA variable tells if it is equal to U,X,0,1
Definition: tree_node.hpp:4598
This struct specifies the ssa_name node.
Definition: tree_node.hpp:4523
static bool classof(SymbRange const *)
static std::function< OpNode *(NodeContainer *)> opCtorGenerator(const tree_nodeConstRef &stmt, unsigned int, const FunctionBehaviorConstRef &FB, const tree_managerConstRef &TM, const application_managerRef &AppM)
void print(std::ostream &OS) const override
Prints the content of the operation.
Wrapper to call graph.
CustomMap< unsigned int, std::list< tree_nodeConstRef > > CallMap
std::vector< tree_nodeConstRef > getSources() const override
#define RA_EXEC_SKIP
static integer_cst_t GetConstValue(const tree_nodeConstRef &tn, bool is_signed=true)
Get value from integer constant.
#define CASE_GIMPLE_NODES
This macro collects all cases labels for gimple nodes.
Definition: tree_node.hpp:700
RangeType
Definition: Range.hpp:54
static bool enable_srem
bool isUnresolved() const
iterator begin()
VarNode & operator=(const VarNode &)=delete
tree_nodeRef type
starting from GCC 4.7.2 ssa_name has a type
Definition: tree_node.hpp:4540
static bool enable_urem
#define GET_INDEX_CONST_NODE(t)
Definition: tree_node.hpp:363
const UseMap & getUses() const
struct definition of the binary node structures.
Definition: tree_node.hpp:1206
std::vector< tree_nodeConstRef > getSources() const override
static bool classof(BinaryOpNode const *)
static RangeRef fromBitValues(const std::deque< bit_lattice > &bv, bw_t bitwidth, bool isSigned)
Definition: Range.cpp:365
refcount< const var_pp_functor > var_pp_functorConstRef
static bool classof(OpNode const *BO)
const tree_nodeConstRef & getBound() const
Returns the node which is the bound of this interval.
void printDot(std::ostream &OS) const override
T * GetOp(OpNode *t)
const VarNodes & getVarNodes() const
OperationId getValueId() const override
bw_t getBitWidth() const
const CustomOrderedSet< unsigned int > & get_function_mem() const
Returns the set of memory variables.
static void shr(size_t p[2], int n)
void update(int b[SIZE], int bucket[BUCKETSIZE], int a[SIZE], int exp)
Definition: sort.c:63
static tree_nodeConstRef GetFunctionReturnType(const tree_nodeConstRef &function, bool void_as_null=true)
Return the return type of a function.
RangeConstRef interval
A Range associated to the variable, that is, its interval inferred by the analysis.
void delControlDependenceEdges(UseMap &useMap)
OpNode * pushOperation(OpNode *op)
static void ComputeSsaUses(const tree_nodeRef &, TreeNodeMap< size_t > &uses)
recursively compute the references to the ssa_name variables used in a statement
VarNode * source
std::map< tree_nodeConstRef, ConditionalValueRange, tree_reindexCompare > ConditionalValueRanges
#define NULL_VERTEX
null vertex definition
Definition: graph.hpp:1305
LoadOpNode & operator=(const LoadOpNode &)=delete
static bool IsLoad(const tree_nodeConstRef &tn, const CustomOrderedSet< unsigned int > &fun_mem_data)
Return true if the tree node is a gimple_assign reading something which will be allocated in memory...
void Initialize() override
Initialize the step (i.e., like a constructor, but executed just before exec.
TernaryOpNode & operator=(const TernaryOpNode &)=delete
static std::function< OpNode *(NodeContainer *)> opCtorGenerator(const tree_nodeConstRef &stmt, unsigned int, const FunctionBehaviorConstRef &FB, const tree_managerConstRef &TM, const application_managerRef &AppM)
Datastructure to represent memory information in high-level synthesis.
void addConditionalValueRange(const ConditionalValueRange &&cvr)
#define RA_EXEC_NORMAL
static bool enable_xor
#define CASE_TERNARY_EXPRESSION
This macro collects all case labels for ternary_expr objects.
Definition: tree_node.hpp:550
Class specification of the manager of the tree structures extracted from the raw file.
static bool enable_shr
HLS specialization of generic_device.
std::ostream & operator<<(std::ostream &OS, const VarNode *VN)
static bool classof(ValueRange const *)
A brief description of the C++ Header File.
#define OPERATION_OPTION(opts, X)
static void get_array_dim_and_bitsize(const tree_managerConstRef &TM, const unsigned int index, std::vector< unsigned long long > &dims, unsigned long long &elts_bitsize)
Return the dimension of the array.
static const std::string ComputeSignature(const FrontendFlowStepType frontend_flow_step_type, const unsigned int function_id)
Compute the signature of a function frontend flow step.
void print(std::ostream &OS) const
Pretty print.
const tree_nodeConstRef V
The program variable.
OpNode & operator=(const OpNode &)=delete
#define CASE_PRAGMA_NODES
This macro collects all case labels for pragma objects.
Definition: tree_node.hpp:610
static bool classof(ValueRange const *BI)
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.
#define THROW_ASSERT(cond, str_expr)
helper function used to check an assert and if needed to throw an error in a standard way ...
Definition: exceptions.hpp:289

Generated on Mon Feb 12 2024 13:02:52 for PandA-2024.02 by doxygen 1.8.13