46 #include "config_HAVE_ASSERTS.hpp" 99 #define INTEGER_PTR // Pointers are considered as integers 100 #define BITVALUE_UPDATE // Read/write bitvalue information during the analysis 102 #define RA_EXEC_NORMAL 0 103 #define RA_EXEC_READONLY 1 104 #define RA_EXEC_SKIP 2 110 #define CASE_MISCELLANEOUS \ 112 case case_label_expr_K: \ 114 case target_expr_K: \ 115 case target_mem_ref_K: \ 116 case target_mem_ref461_K: \ 119 case constructor_K: \ 121 case identifier_node_K: \ 123 case statement_list_K: \ 135 #if __BYTE_ORDER == __BIG_ENDIAN 150 #if __BYTE_ORDER == __BIG_ENDIAN 163 static_cast<const tree_reindex*>(rhs.
get())->actual_tree_node->index;
173 std::string pestring;
174 std::stringstream pseudoEdgesString(pestring);
203 case ceil_div_expr_K:
204 case ceil_mod_expr_K:
206 case compound_expr_K:
207 case eh_filter_expr_K:
208 case exact_div_expr_K:
210 case floor_div_expr_K:
211 case floor_mod_expr_K:
212 case goto_subroutine_K:
223 case mult_highpart_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:
233 case round_div_expr_K:
234 case round_mod_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:
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:
284 return static_cast<kind>(-1);
318 case ceil_div_expr_K:
319 case ceil_mod_expr_K:
321 case compound_expr_K:
322 case eh_filter_expr_K:
323 case exact_div_expr_K:
325 case floor_div_expr_K:
326 case floor_mod_expr_K:
327 case goto_subroutine_K:
338 case mult_highpart_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:
348 case round_div_expr_K:
349 case round_mod_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:
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:
400 return static_cast<kind>(-1);
434 case ceil_div_expr_K:
435 case ceil_mod_expr_K:
437 case compound_expr_K:
438 case eh_filter_expr_K:
439 case exact_div_expr_K:
441 case floor_div_expr_K:
442 case floor_mod_expr_K:
443 case goto_subroutine_K:
454 case mult_highpart_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:
464 case round_div_expr_K:
465 case round_mod_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:
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:
516 return static_cast<kind>(-1);
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;
532 if(
const auto* nop = GetPointer<const nop_expr>(op))
536 else if(
const auto* ce = GetPointer<const convert_expr>(op))
540 else if(
const auto* ssa = GetPointer<const ssa_name>(op))
543 if(
const auto* gp = GetPointer<const gimple_phi>(DefStmt))
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);
549 else if(
const auto* ga = GetPointer<const gimple_assign>(DefStmt))
553 else if(GetPointer<const gimple_nop>(DefStmt) !=
nullptr)
558 THROW_UNREACHABLE(
"Branch var definition statement not handled (" + DefStmt->get_kind_text() +
" " +
559 DefStmt->ToString() +
")");
561 else if(op->get_kind() == tree_reindex_K)
576 const auto tn = _tn->get_kind() == tree_reindex_K ?
GET_CONST_NODE(_tn) : _tn;
577 switch(tn->get_kind())
580 case enumeral_type_K:
598 case type_pack_expansion_K:
600 case function_type_K:
607 case qual_union_type_K:
609 case reference_type_K:
611 case template_type_parm_K:
612 case typename_type_K:
613 case type_argument_pack_K:
620 case aggr_init_expr_K:
621 case case_label_expr_K:
624 case target_mem_ref_K:
625 case target_mem_ref461_K:
630 case identifier_node_K:
631 case statement_list_K:
644 THROW_UNREACHABLE(
"Unhandled node type (" + tn->get_kind_text() +
" " + tn->ToString() +
")");
654 case gimple_assign_K:
687 case view_convert_expr_K:
689 const auto* ue = GetPointer<const unary_expr>(
GET_CONST_NODE(ga->op1));
702 case widen_mult_expr_K:
703 case trunc_div_expr_K:
704 case trunc_mod_expr_K:
717 case pointer_plus_expr_K:
721 case sat_plus_expr_K:
722 case sat_minus_expr_K:
724 const auto bin_op = GetPointer<const binary_expr>(
GET_CONST_NODE(ga->op1));
725 if(!isValidType(bin_op->op0) || !isValidType(bin_op->op1))
752 case cleanup_point_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:
760 case imagpart_expr_K:
762 case misaligned_indirect_ref_K:
764 case non_lvalue_expr_K:
765 case realpart_expr_K:
766 case reference_expr_K:
767 case reinterpret_cast_expr_K:
769 case static_cast_expr_K:
771 case truth_not_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:
783 case pointer_plus_expr_K:
787 case ceil_div_expr_K:
788 case ceil_mod_expr_K:
790 case compound_expr_K:
791 case eh_filter_expr_K:
792 case exact_div_expr_K:
794 case floor_div_expr_K:
795 case floor_mod_expr_K:
796 case goto_subroutine_K:
802 case mult_highpart_expr_K:
804 case postdecrement_expr_K:
805 case postincrement_expr_K:
806 case predecrement_expr_K:
807 case preincrement_expr_K:
811 case round_div_expr_K:
812 case round_mod_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:
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:
847 case component_ref_K:
848 case bit_field_ref_K:
849 case bit_ior_concat_expr_K:
851 case with_cleanup_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:
873 case aggr_init_expr_K:
874 case case_label_expr_K:
877 case target_mem_ref_K:
878 case target_mem_ref461_K:
883 case identifier_node_K:
884 case statement_list_K:
889 case insertvalue_expr_K:
890 case insertelement_expr_K:
911 case gimple_multi_way_if_K:
913 case gimple_pragma_K:
914 case gimple_predict_K:
916 case gimple_return_K:
917 case gimple_switch_K:
933 return isValidType(Type);
938 const auto tn = _tn->get_kind() == tree_reindex_K ?
GET_CONST_NODE(_tn) : _tn;
939 switch(tn->get_kind())
941 case enumeral_type_K:
942 return !GetPointer<const enumeral_type>(tn)->unsigned_flag;
944 return !GetPointer<const integer_type>(tn)->unsigned_flag;
951 case type_pack_expansion_K:
953 case function_type_K:
958 case qual_union_type_K:
960 case reference_type_K:
962 case template_type_parm_K:
963 case typename_type_K:
967 case type_argument_pack_K:
973 case aggr_init_expr_K:
974 case case_label_expr_K:
977 case target_mem_ref_K:
978 case target_mem_ref461_K:
983 case identifier_node_K:
984 case statement_list_K:
997 THROW_UNREACHABLE(
"Unhandled node type (" + tn->get_kind_text() +
" " + tn->ToString() +
")");
1004 if(tn->get_kind() == tree_reindex_K)
1008 if(
const auto* gp = GetPointer<const gimple_phi>(tn))
1012 if(
const auto* gr = GetPointer<const gimple_return>(tn))
1021 const auto type = getGIMPLE_Type(tn);
1024 "Unhandled type (" +
type->get_kind_text() +
") for " + tn->get_kind_text() +
" " + tn->ToString());
1025 return static_cast<bw_t>(size);
1031 if(tn->get_kind() == tree_reindex_K)
1036 const auto type = getGIMPLE_Type(tn);
1039 "Unhandled type (" +
type->get_kind_text() +
") for " + tn->get_kind_text() +
" " + tn->ToString());
1041 return RangeRef(
new Range(rType, bw));
1046 if(tn->get_kind() == tree_reindex_K)
1051 const auto type = getGIMPLE_Type(tn);
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() +
" " +
1056 #ifdef BITVALUE_UPDATE 1060 if(
const auto* ic = GetPointer<const integer_cst>(tn))
1065 else if(
const auto* sc = GetPointer<const string_cst>(tn))
1069 for(
const auto& c : sc->strg)
1071 r = r->unionWith(RangeRef(
new Range(
Regular, bw, c, c)));
1075 else if(
const auto* rc = GetPointer<const real_cst>(tn))
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())
1087 else if(
const auto* vc = GetPointer<const vector_cst>(tn))
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)
1097 auto curr_el = getGIMPLE_range(vc->list_of_valu.at(i * stride));
1098 for(
size_t j = 1; j < stride; ++j)
1100 curr_el = getGIMPLE_range(vc->list_of_valu.at(i * stride + j))
1102 ->shl(RangeRef(
new Range(
Regular, bw, el_bw * j, el_bw * j)))
1105 r = r->unionWith(curr_el);
1111 #ifdef BITVALUE_UPDATE 1112 sign = !it->unsigned_flag;
1119 #ifdef BITVALUE_UPDATE 1120 sign = !et->unsigned_flag;
1147 "record_type has no size");
1158 #ifdef BITVALUE_UPDATE 1159 if(
const auto* ssa = GetPointer<const ssa_name>(tn))
1161 if(!ssa->bit_values.empty())
1163 const auto bvSize =
static_cast<bw_t>(ssa->bit_values.size());
1165 const auto varRange = RangeRef(
new Range(
Regular, bw, min, max))->truncate(bvSize)->intersectWith(bvRange);
1166 return sign ? varRange->sextOrTrunc(bw) : varRange->zextOrTrunc(bw);
1206 void init(
bool outside);
1223 return interval->getBitWidth();
1229 interval.reset(newInterval->clone());
1234 return getRangeFor(V,
Regular);
1239 return abstractState;
1242 void storeAbstractState();
1247 void print(std::ostream& OS)
const;
1253 : V(_V), function_id(_function_id), abstractState(0)
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");
1287 auto* SSA = GetPointer<ssa_name>(
GET_NODE(ssa_node));
1288 if(SSA ==
nullptr ||
interval->isUnknown())
1293 #ifdef BITVALUE_UPDATE 1294 auto updateBitValue = [&](
ssa_name* ssa,
const std::deque<bit_lattice>& bv) ->
int {
1308 const bool isSigned = isSignedType(SSA->type);
1309 if(SSA->range !=
nullptr)
1311 if(SSA->range->isSameRange(
interval))
1315 if(not AppM->ApplyNewTransformation())
1320 "Modified range " + SSA->range->ToString() +
" to " +
interval->ToString() +
" for " +
1321 SSA->ToString() +
" " +
GET_CONST_NODE(SSA->type)->get_kind_text());
1340 const auto currentBW = getGIMPLE_BW(V);
1341 if(newBW >= currentBW)
1349 "Anti range " +
interval->ToString() +
" not stored for " + SSA->ToString() +
" " +
1356 "Empty range not stored for " + SSA->ToString() +
" " +
1361 if(!AppM->ApplyNewTransformation())
1395 "Added range " +
interval->ToString() +
"<" +
STR(newBW) +
"> for " + SSA->ToString() +
" " +
1409 #ifdef BITVALUE_UPDATE 1410 bit_values =
interval->getBitValues(isSigned);
1417 #ifdef BITVALUE_UPDATE 1418 if(!bit_values.empty())
1420 auto range_bv =
interval->getBitValues(isSigned);
1423 if(bit_values != sup_bv)
1425 bit_values = sup_bv;
1432 bit_values =
interval->getBitValues(isSigned);
1439 if(!AppM->ApplyNewTransformation())
1443 auto resUpdate = updateBitValue(SSA, bit_values);
1448 AppM->RegisterTransformation(
"RangeAnalysis", V);
1450 "---BitValue updated for " + SSA->ToString() +
" " +
GET_CONST_NODE(SSA->type)->get_kind_text() +
1454 if(
const auto* gp = GetPointer<const gimple_phi>(
GET_NODE(SSA->CGetDefStmt())))
1456 if(gp->CGetDefEdgesList().size() == 1)
1459 "---Sigma defined variable not considered for invalidation loop...");
1475 printVarName(V, OS);
1483 std::stringstream ss;
1534 return T::classof(t) ?
static_cast<T*
>(t) :
nullptr;
1543 explicit ValueRange(
const RangeConstRef& range);
1568 this->range.reset(newRange->clone());
1572 virtual void print(std::ostream& OS)
const;
1588 std::stringstream ss;
1648 RangeConstRef solveFuture(
const VarNode* bound,
const VarNode* sink)
const;
1651 void print(std::ostream& OS)
const override;
1655 :
ValueRange(_range), bound(_bound), pred(_pred)
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");
1668 auto IsAnti = boundRange->isAnti() || sinkRange->isAnti();
1670 IsAnti ? (boundRange->isUnknown() ?
Range::Min : boundRange->getUnsignedMin()) : boundRange->getLower();
1672 IsAnti ? (boundRange->isUnknown() ?
Range::Max : boundRange->getUnsignedMax()) : boundRange->getUpper();
1676 IsAnti ? (sinkRange->isUnknown() ?
Range::Min : sinkRange->getUnsignedMin()) : sinkRange->getLower();
1678 IsAnti ? (sinkRange->isUnknown() ?
Range::Max : sinkRange->getUnsignedMax()) : sinkRange->getUpper();
1680 const auto bw =
getRange()->getBitWidth();
1749 case bit_and_expr_K:
1750 case bit_ior_expr_K:
1751 case bit_xor_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:
1760 case floor_div_expr_K:
1761 case floor_mod_expr_K:
1762 case goto_subroutine_K:
1765 case lrotate_expr_K:
1773 case mult_highpart_expr_K:
1774 case ordered_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:
1783 case round_div_expr_K:
1784 case round_mod_expr_K:
1785 case rrotate_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:
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:
1846 printVarName(bnd, OS);
1848 printVarName(bnd, OS);
1853 printVarName(bnd, OS);
1858 printVarName(bnd, OS);
1863 printVarName(bnd, OS);
1868 printVarName(bnd, OS);
1874 printVarName(bnd, OS);
1880 printVarName(bnd, OS);
1881 OS <<
" - 1), +inf]";
1885 printVarName(bnd, OS);
1889 case bit_and_expr_K:
1890 case bit_ior_expr_K:
1891 case bit_xor_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:
1900 case floor_div_expr_K:
1901 case floor_mod_expr_K:
1902 case goto_subroutine_K:
1905 case lrotate_expr_K:
1913 case mult_highpart_expr_K:
1914 case ordered_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:
1923 case round_div_expr_K:
1924 case round_mod_expr_K:
1925 case rrotate_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:
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:
1971 OS <<
"Unknown Instruction.";
1982 std::map<unsigned int, ValueRangeRef>
bbVR;
1986 : V(_V), bbVR(_bbVR)
1990 const ValueRangeRef& TrueVR,
const ValueRangeRef& FalseVR)
1991 : V(_V), bbVR({{FalseBBI, FalseVR}, {TrueBBI, TrueVR}})
1999 const std::map<unsigned int, ValueRangeRef>&
getVR()
const 2009 void addVR(
unsigned int bbi,
const ValueRangeRef& cvr)
2011 if(!static_cast<bool>(bbVR.count(bbi)))
2013 bbVR.insert(std::make_pair(bbi, cvr));
2026 template <
typename T>
2029 return T::classof(t) ?
static_cast<T*
>(t) :
nullptr;
2031 template <
typename T>
2034 return T::classof(t) ?
static_cast<const T*
>(t) :
nullptr;
2074 virtual ~
OpNode() =
default;
2090 virtual RangeRef eval()
const = 0;
2106 this->intersect->setRange(newIntersect);
2115 virtual std::vector<tree_nodeConstRef> getSources()
const = 0;
2118 virtual void print(std::ostream& OS)
const = 0;
2119 virtual void printDot(std::ostream& OS)
const = 0;
2130 : intersect(_intersect), sink(_sink), inst(_inst)
2136 if(
const auto SI = RefcountCast<const SymbRange>(
getIntersect()))
2144 std::stringstream ss;
2154 using VarNodes = std::map<tree_nodeConstRef, VarNode*, tree_reindexCompare>;
2158 using DefMap = std::map<tree_nodeConstRef, OpNode*, tree_reindexCompare>;
2165 static const std::vector<std::function<std::function<OpNode*(NodeContainer*)>(
2189 for(
const auto& varNode : _varNodes)
2191 delete varNode.second;
2193 for(
const auto& op : _opNodes)
2207 auto vit = _varNodes.find(V);
2208 if(vit != _varNodes.end())
2213 auto* node =
new VarNode(V, function_id);
2214 _varNodes.insert(std::make_pair(V, node));
2218 _useMap.insert(std::make_pair(V, useList));
2229 auto cvrIt = _cvrMap.find(cvr.getVar());
2230 if(cvrIt != _cvrMap.end())
2232 for(
const auto& BBIvr : cvr.getVR())
2234 cvrIt->second.addVR(BBIvr.first, BBIvr.second);
2239 _cvrMap.insert(std::make_pair(cvr.getVar(), cvr));
2252 _opNodes.insert(op);
2256 _useMap[tn].insert(op);
2262 OpNode*
addOperation(
const tree_nodeConstRef& stmt,
unsigned int function_id,
const FunctionBehaviorConstRef& FB,
2265 for(
const auto& generateCtorFor : _opCtorGenerators)
2267 if(
auto generateOpFor = generateCtorFor(stmt, function_id, FB, TM, AppM))
2269 return pushOperation(generateOpFor(
this));
2322 #define OPERATION_OPTION(opts, X) \ 2323 if((opts).erase("no_" #X)) \ 2325 INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "Range analysis: " #X " operation disabled"); \ 2326 enable_##X = false; \ 2328 #define RETURN_DISABLED_OPTION(x, bw) \ 2331 return RangeRef(new Range(Regular, bw)); \ 2333 #define RESULT_DISABLED_OPTION(x, var, stdResult) enable_##x ? (stdResult) : getRangeFor(var, Regular) 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 2353 RangeRef
eval()
const override;
2366 sources.push_back(newsrc);
2371 return sources[
index];
2376 return sources.size();
2381 std::vector<tree_nodeConstRef> tSources;
2382 std::transform(sources.begin(), sources.end(), std::back_inserter(tSources),
2401 void print(std::ostream& OS)
const override;
2402 void printDot(std::ostream& OS)
const override;
2404 static std::function<OpNode*(NodeContainer*)> opCtorGenerator(
const tree_nodeConstRef& stmt,
unsigned int,
2412 :
OpNode(_intersect, _sink, _inst)
2430 result = result->unionWith(varNode->getRange());
2438 auto _intersect = result->intersectWith(aux);
2439 if(!_intersect->isEmpty())
2442 "---aux = " + aux->ToString() +
" from " +
getIntersect()->ToString());
2444 result = _intersect;
2451 std::function<OpNode*(NodeContainer*)>
2456 if(!
phi ||
phi->CGetDefEdgesList().size() <= 1)
2461 if(phi->virtual_flag)
2464 return static_cast<PhiOpNode*
>(
nullptr);
2467 "Analysing phi operation " + phi->ToString());
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);
2475 "---Added PhiOp with range " + BI->ToString() +
" and " +
STR(phi->CGetDefEdgesList().size()) +
2479 for(
const auto& operandBBI : phi->CGetDefEdgesList())
2481 VarNode* source = NC->addVarNode(operandBBI.first, function_id);
2482 phiOp->addSource(source);
2492 for(; i < static_cast<int>(
sources.size() - 1); ++i)
2501 const char* quot = R
"(")"; 2502 OS << " " << quot <<
this << quot << R
"( [label=")"; 2507 const auto& V = varNode->getValue();
2515 printVarName(V, OS);
2516 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
2520 OS <<
" " << quot <<
this << quot <<
" -> " << quot;
2521 printVarName(VS, OS);
2540 RangeRef
eval()
const override;
2580 void print(std::ostream& OS)
const override;
2581 void printDot(std::ostream& OS)
const override;
2591 :
OpNode(_intersect, _sink, _inst), source(_source), opcode(_opcode)
2603 const auto resultType = getGIMPLE_Type(
getSink()->getValue());
2606 if(oprnd->isEmpty())
2610 else if(oprnd->isRegular() || oprnd->isAnti())
2616 THROW_ASSERT(oprndSigned,
"Absolute value of unsigned operand should not happen");
2620 case bit_not_expr_K:
2622 result = oprnd->Not();
2625 case convert_expr_K:
2643 case view_convert_expr_K:
2660 case alignof_expr_K:
2664 case cleanup_point_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:
2672 case imagpart_expr_K:
2673 case indirect_ref_K:
2674 case misaligned_indirect_ref_K:
2676 case non_lvalue_expr_K:
2677 case realpart_expr_K:
2678 case reference_expr_K:
2679 case reinterpret_cast_expr_K:
2681 case static_cast_expr_K:
2683 case truth_not_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:
2712 oprnd->ToString() +
" )");
2718 auto _intersect = result->intersectWith(aux);
2719 if(!_intersect->isEmpty())
2722 "---aux = " + aux->ToString() +
" from " +
getIntersect()->ToString());
2724 result = _intersect;
2730 std::function<OpNode*(NodeContainer*)>
2734 const auto* assign = GetPointer<const gimple_assign>(
GET_CONST_NODE(stmt));
2735 if(assign ==
nullptr)
2739 if(GetPointer<const ssa_name>(
GET_CONST_NODE(assign->op1)) !=
nullptr ||
2744 "Analysing assign operation " + assign->ToString());
2746 VarNode*
sink = NC->addVarNode(assign->op0, function_id);
2747 VarNode* _source = NC->addVarNode(assign->op1, function_id);
2749 auto BI = ValueRangeRef(
new ValueRange(getGIMPLE_range(stmt)));
2751 "---Added assign operation with range " + BI->ToString());
2752 return new UnaryOpNode(BI, sink, stmt, _source, nop_expr_K);
2755 const auto* un_op = GetPointer<const unary_expr>(
GET_CONST_NODE(assign->op1));
2756 if(un_op ==
nullptr)
2760 return [stmt, assign, un_op, function_id](
NodeContainer* NC) {
2762 "Analysing unary operation " + un_op->get_kind_text() +
" " + assign->ToString());
2765 auto*
sink = NC->addVarNode(assign->op0, function_id);
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();
2772 "---Added UnaryOp for " + un_op->get_kind_text() +
" with range " + BI->ToString());
2773 return new UnaryOpNode(BI, sink, stmt, _source, op_kind);
2785 const char* quot = R
"(")"; 2786 OS << " " << quot <<
this << quot << R
"( [label=")"; 2796 OS <<
"trunc i" << bw;
2802 OS <<
"ptr_cast i" << bw;
2808 OS <<
"sext i" << bw;
2812 OS <<
"zext i" << bw;
2817 else if(
opcode == fix_trunc_expr_K)
2819 const auto type = getGIMPLE_Type(
getSink()->getValue());
2822 if(int_type->unsigned_flag)
2824 OS <<
"fptoui i" << bw;
2828 OS <<
"fptosi i" << bw;
2852 printVarName(V, OS);
2853 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
2857 OS <<
" " << quot <<
this << quot <<
" -> " << quot;
2858 printVarName(VS, OS);
2871 RangeRef
eval()
const override;
2907 if(SymbolicSource !=
nullptr)
2909 s.push_back(SymbolicSource->
getValue());
2927 void print(std::ostream& OS)
const override;
2928 void printDot(std::ostream& OS)
const override;
2938 :
UnaryOpNode(_intersect, _sink, _inst, _source, _opcode), SymbolicSource(_SymbolicSource), unresolved(
false)
2950 if(!aux->isUnknown())
2952 auto _intersect = result->intersectWith(aux);
2953 if(!_intersect->isEmpty())
2956 "---aux = " + aux->ToString() +
" from " +
getIntersect()->ToString());
2959 if(_intersect->getSpan() < result->getSpan())
2962 result = _intersect;
2971 "---" + result->ToString() +
" = SIGMA< " +
getSource()->
getRange()->ToString() +
" >");
2975 std::function<OpNode*(NodeContainer*)>
2980 if(!
phi ||
phi->CGetDefEdgesList().size() != 1)
2985 const auto BBI = phi->bb_index;
2987 "Analysing sigma operation " + phi->ToString());
2988 const auto& sourceTN = phi->CGetDefEdgesList().front().first;
2991 VarNode*
sink = NC->addVarNode(phi->res, function_id);
2994 auto vsmit = NC->getCVR().find(sourceTN);
2995 if(vsmit == NC->getCVR().end())
3000 auto condRangeIt = vsmit->second.getVR().find(BBI);
3001 if(condRangeIt != vsmit->second.getVR().end())
3003 const auto& CondRange = condRangeIt->second;
3005 if(
auto symb = RefcountCast<SymbRange>(CondRange))
3007 const auto& bound = symb->getBound();
3008 SymbSrc = NC->addVarNode(bound, function_id);
3011 "---Added SigmaOp with " + std::string(SymbSrc ?
"symbolic " :
"") +
"range " +
3012 CondRange->ToString());
3013 return new SigmaOpNode(CondRange, sink, stmt, source, SymbSrc, phi->get_kind());
3017 auto BI = ValueRangeRef(
new ValueRange(getGIMPLE_range(stmt)));
3019 "---Added SigmaOp with range " + BI->ToString());
3020 return new SigmaOpNode(BI, sink, stmt, source,
nullptr, phi->get_kind());
3033 const char* quot = R
"(")"; 3034 OS << " " << quot <<
this << quot << R
"( [label=")" 3046 printVarName(V, OS);
3047 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
3059 printVarName(_V, OS);
3060 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
3065 OS <<
" " << quot <<
this << quot <<
" -> " << quot;
3066 printVarName(VS, OS);
3085 RangeRef
eval()
const override;
3110 static RangeRef evaluate(
kind opcode,
bw_t bw,
const RangeConstRef& op1,
const RangeConstRef& op2,
bool opSigned);
3132 void print(std::ostream& OS)
const override;
3133 void printDot(std::ostream& OS)
const override;
3144 :
OpNode(_intersect, _sink, _inst), source1(_source1), source2(_source2),
opcode(_opcode)
3146 THROW_ASSERT(isValidType(_sink->
getValue()),
"Binary operation sink should be of valid type (" +
3155 case pointer_plus_expr_K:
3159 return op1->add(op2);
3162 return op1->sub(op2);
3165 return op1->mul(op2);
3166 case widen_mult_expr_K:
3168 return opSigned ? op1->sextOrTrunc(bw)->mul(op2->sextOrTrunc(bw)) :
3169 op1->zextOrTrunc(bw)->mul(op2->sextOrTrunc(bw));
3170 case trunc_div_expr_K:
3174 return op1->sdiv(op2);
3179 return op1->udiv(op2);
3181 case trunc_mod_expr_K:
3185 const auto res = op1->srem(op2);
3186 if(!res->isUnknown() && !res->isEmpty() && res->getSignedMin() == 0)
3188 const auto consRes = res->unionWith(res->negate());
3190 "---Being conservative on signed modulo operator: " + res->ToString() +
" -> " +
3191 consRes->ToString());
3199 return op1->urem(op2);
3203 return opSigned ? op1->sextOrTrunc(bw)->shl(op2) : op1->zextOrTrunc(bw)->shl(op2);
3206 return opSigned ? op1->shr(op2,
true)->sextOrTrunc(bw) : op1->shr(op2,
false)->zextOrTrunc(bw);
3207 case bit_and_expr_K:
3209 return op1->And(op2);
3210 case bit_ior_expr_K:
3212 return op1->Or(op2);
3213 case bit_xor_expr_K:
3215 return op1->Xor(op2);
3217 if(op1->getBitWidth() < op2->getBitWidth())
3219 return opSigned ? op1->sextOrTrunc(op2->getBitWidth())->Eq(op2, bw) :
3220 op1->zextOrTrunc(op2->getBitWidth())->Eq(op2, bw);
3222 else if(op2->getBitWidth() < op1->getBitWidth())
3224 return opSigned ? op2->sextOrTrunc(op1->getBitWidth())->Eq(op1, bw) :
3225 op2->zextOrTrunc(op1->getBitWidth())->Eq(op1, bw);
3227 return op1->Eq(op2, bw);
3229 return op1->Ne(op2, bw);
3231 return opSigned ? op1->Sgt(op2, bw) : op1->Ugt(op2, bw);
3233 return opSigned ? op1->Sge(op2, bw) : op1->Uge(op2, bw);
3235 return opSigned ? op1->Slt(op2, bw) : op1->Ult(op2, bw);
3237 return opSigned ? op1->Sle(op2, bw) : op1->Ule(op2, bw);
3240 return opSigned ? op1->SMin(op2) : op1->UMin(op2);
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:
3249 return opSigned ? op1->sat_sub(op2) : op1->usat_sub(op2);
3252 case pointer_plus_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:
3263 case floor_div_expr_K:
3264 case floor_mod_expr_K:
3265 case goto_subroutine_K:
3268 case lrotate_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:
3280 case round_div_expr_K:
3281 case round_mod_expr_K:
3282 case rrotate_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:
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:
3347 if((op1->isRegular() || op1->isAnti()) && (op2->isRegular() || op2->isAnti()))
3349 const auto opSigned = isSignedType(
getSource1()->getValue());
3357 const auto sinkSigned = isSignedType(
getSink()->getValue());
3358 const auto bvRange = [&]() {
3359 if(ssa->bit_values.empty() || ssa->bit_values.front() ==
'X')
3365 for(
auto it = ssa->bit_values.crbegin(); it != ssa->bit_values.crend(); ++it, ++i)
3369 bits |=
APInt(1) << i;
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");
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 ))
3383 "---Result range " +
result->ToString() +
" filtered with mask " +
3385 STR(bvRange->getBitWidth()) +
"> from " + ssa->bit_values +
"<" +
3386 (sinkSigned ?
"signed" :
"unsigned") +
"> " + bvRange->ToString());
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;
3402 if(
result->getBitWidth() != sinkBW)
3407 else if(op1->isEmpty() || op2->isEmpty())
3413 " " + op2->ToString());
3419 auto _intersect =
result->intersectWith(aux);
3420 if(!_intersect->isEmpty())
3423 "---aux = " + aux->ToString() +
" from " +
getIntersect()->ToString());
3431 std::function<OpNode*(NodeContainer*)>
3435 const auto* assign = GetPointer<const gimple_assign>(
GET_CONST_NODE(stmt));
3436 if(assign ==
nullptr)
3440 const auto* bin_op = GetPointer<const binary_expr>(
GET_CONST_NODE(assign->op1));
3441 if(bin_op ==
nullptr)
3445 return [stmt, assign, bin_op, function_id](
NodeContainer* NC) {
3447 "Analysing binary operation " + bin_op->get_kind_text() +
" " + assign->ToString());
3450 auto*
sink = NC->addVarNode(assign->op0, function_id);
3451 auto op_kind = bin_op->get_kind();
3454 auto* _source1 = NC->addVarNode(bin_op->op0, function_id);
3455 auto* _source2 = NC->addVarNode(bin_op->op1, function_id);
3457 auto BI = ValueRangeRef(
new ValueRange(getGIMPLE_range(stmt)));
3462 return static_cast<OpNode*
>(
new BinaryOpNode(BI, sink, stmt, _source1, _source2, op_kind));
3475 const char* quot = R
"(")"; 3477 OS << " " << quot <<
this << quot << R
"( [label=")" << opcodeName << "\"]\n";
3486 printVarName(V1, OS);
3487 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
3497 printVarName(V2, OS);
3498 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
3501 OS <<
" " << quot <<
this << quot <<
" -> " << quot;
3502 printVarName(VS, OS);
3520 "Branch variable value is " +
STR(branchValue) +
", false edge BB" +
STR(branchBB->false_edge) +
3522 return branchBB->false_edge;
3527 "Branch variable value is " +
STR(branchValue) +
", true edge BB" +
STR(branchBB->true_edge) +
3529 return branchBB->true_edge;
3532 else if(
const auto* bin_op = GetPointer<const binary_expr>(
GET_CONST_NODE(br_op)))
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)
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())
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;
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;
3560 "Branch condition has non-integer cst_node operands, skipping...");
3584 RangeRef
eval()
const override;
3634 void print(std::ostream& OS)
const override;
3635 void printDot(std::ostream& OS)
const override;
3649 const auto* ga = GetPointer<const gimple_assign>(
GET_CONST_NODE(_inst));
3651 const auto* I = GetPointer<const ternary_expr>(
GET_CONST_NODE(ga->op1));
3652 THROW_ASSERT(I,
"TernaryOp operator should be a ternary_expr");
3677 if((op1->isRegular() || op1->isAnti()) && (op2->isRegular() || op2->isAnti()) &&
3678 (op3->isRegular() || op3->isAnti()))
3683 if(op1->isSameRange(RangeRef(
new Range(
Regular, op1->getBitWidth(), 1, 1))))
3685 result = RangeRef(op2->clone());
3687 else if(op1->isSameRange(RangeRef(
new Range(
Regular, op1->getBitWidth(), 0, 0))))
3689 result = RangeRef(op3->clone());
3694 const auto* I = GetPointer<const ternary_expr>(
GET_CONST_NODE(ga->op1));
3696 std::vector<const struct binary_expr*> BranchConds;
3698 if(GetPointer<const gimple_phi>(BranchVar) !=
nullptr)
3703 else if(
const auto* BranchExpr = GetPointer<const binary_expr>(BranchVar))
3705 BranchConds.push_back(BranchExpr);
3708 for(
const auto* be : BranchConds)
3712 const auto& CondOp0 = be->op0;
3713 const auto& CondOp1 = be->op1;
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;
3724 const auto CR = getGIMPLE_range(constant);
3725 THROW_ASSERT(CR->isConstant(),
"Range from constant should be constant (" +
3727 CR->ToString() +
")");
3728 kind pred = isSignedType(CondOp0) ? be->get_kind() : op_unsigned(be->get_kind());
3729 kind swappred = op_swap(pred);
3737 RangeRef FValues(
new Range(*tmpT->getAnti()));
3738 op3 = op3->intersectWith(FValues);
3742 op2 = op2->intersectWith(tmpT);
3748 result = op2->unionWith(op3);
3754 if(op1->isEmpty() || op2->isEmpty() || op3->isEmpty())
3763 "---" +
result->ToString() +
" = " + op1->ToString() +
" ? " + op2->ToString() +
" : " +
3770 auto _intersect =
result->intersectWith(aux);
3771 if(!_intersect->isEmpty())
3774 "---aux = " + aux->ToString() +
" from " +
getIntersect()->ToString());
3782 std::function<OpNode*(NodeContainer*)>
3786 const auto* assign = GetPointer<const gimple_assign>(
GET_CONST_NODE(stmt));
3787 if(assign ==
nullptr)
3791 const auto* ter_op = GetPointer<const ternary_expr>(
GET_CONST_NODE(assign->op1));
3792 if(ter_op ==
nullptr)
3796 return [stmt, assign, ter_op, function_id](
NodeContainer* NC) {
3798 "Analysing ternary operation " + ter_op->get_kind_text() +
" " + assign->ToString());
3800 VarNode*
sink = NC->addVarNode(assign->op0, function_id);
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);
3808 auto BI = ValueRangeRef(
new ValueRange(getGIMPLE_range(stmt)));
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());
3825 const char* quot = R
"(")"; 3827 OS << " " << quot <<
this << quot << R
"( [label=")" << opcodeName << "\"]\n";
3837 printVarName(V1, OS);
3838 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
3848 printVarName(V2, OS);
3849 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
3860 printVarName(V3, OS);
3861 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
3864 OS <<
" " << quot <<
this << quot <<
" -> " << quot;
3865 printVarName(VS, OS);
3877 RangeRef
eval()
const override;
3904 sources.push_back(newsrc);
3909 return sources[
index];
3914 return sources.size();
3918 std::vector<tree_nodeConstRef> sourceTNs;
3919 for(
const auto& s : sources)
3921 sourceTNs.push_back(s->getValue());
3926 void print(std::ostream& OS)
const override;
3927 void printDot(std::ostream& OS)
const override;
3929 static std::function<OpNode*(NodeContainer*)>
3935 :
OpNode(_intersect, _sink, _inst)
3951 STR(
getSink()->getBitWidth()) +
" while intersect has bitwidth " +
3963 " ->" + varNode->getRange()->ToString() +
" " + varNode->ToString());
3964 result = result->unionWith(varNode->getRange());
3972 auto _intersect =
result->intersectWith(aux);
3973 if(!_intersect->isEmpty())
3976 "---aux = " + aux->ToString() +
" from " +
getIntersect()->ToString());
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;
3991 unsigned int initialized_elements = 0;
3992 auto ctor_range = RangeRef(init->clone());
3993 for(
const auto& i : c->list_of_idx_valu)
4001 "invalid nested constructors:" + tn->ToString() +
" " +
STR(array_dims.size()));
4006 const auto init_range = getGIMPLE_range(
el);
4007 if(init_range->getBitWidth() >
static_cast<Range::bw_t>(elements_bitsize))
4010 "---Initializer value not compliant " +
el->ToString());
4015 "---Initializer value is " +
el->ToString());
4016 ctor_range = ctor_range->unionWith(init_range);
4019 initialized_elements++;
4021 if(initialized_elements < array_dims.front())
4024 ctor_range->unionWith(RangeRef(
new Range(
Regular, static_cast<Range::bw_t>(elements_bitsize), 0, 0)));
4029 std::function<OpNode*(NodeContainer*)>
4033 const auto* ga = GetPointer<const gimple_assign>(
GET_CONST_NODE(stmt));
4042 return [stmt, ga, function_id, FB, TM, AppM](
NodeContainer* NC) {
4044 "Analysing load operation " + ga->ToString());
4046 const auto bw = getGIMPLE_BW(ga->op0);
4047 VarNode*
sink = NC->addVarNode(ga->op0, function_id);
4049 "Sink variable is " +
GET_CONST_NODE(ga->op0)->get_kind_text() +
" (size = " +
STR(bw) +
")");
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)
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))
4061 const auto* vd = GetPointer<const var_decl>(TM->get_tree_node_const(base_index));
4064 if(
GET_NODE(vd->init)->get_kind() == constructor_K)
4070 auto init_range = getGIMPLE_range(
GET_NODE(vd->init));
4071 if(init_range->getBitWidth() != bw)
4074 "---Initializer value not compliant " +
GET_NODE(vd->init)->ToString());
4079 "---Initializer value is " +
GET_NODE(vd->init)->ToString());
4080 intersection = init_range;
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))
4089 const auto* vd = GetPointer<const var_decl>(TM->get_tree_node_const(base_index));
4092 if(
GET_NODE(vd->init)->get_kind() == constructor_K)
4099 if(init_range->getBitWidth() != bw)
4102 "---Initializer value not compliant " +
GET_NODE(vd->init)->ToString());
4107 "---Initializer value is " +
GET_NODE(vd->init)->ToString());
4108 intersection = init_range;
4116 for(
const auto& cur_var : hm->Rmem->get_source_values(base_index))
4118 const auto cur_node = TM->get_tree_node_const(cur_var);
4120 auto init_range = getGIMPLE_range(cur_node);
4121 if(init_range->getBitWidth() != bw)
4124 "---Initializer value not compliant " + cur_node->ToString());
4129 "---Initializer value is " + cur_node->ToString());
4130 intersection = intersection->unionWith(init_range);
4135 if(intersection->isEmpty())
4137 intersection = getGIMPLE_range(stmt);
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)
4144 intersection = intersection->zextOrTrunc(bw);
4146 auto BI = ValueRangeRef(
new ValueRange(intersection));
4150 BI = ValueRangeRef(
new ValueRange(getGIMPLE_range(stmt)));
4154 "<--Added LoadOp with range " + BI->ToString());
4166 const char* quot = R
"(")"; 4167 OS << " " << quot <<
this << quot << R
"( [label=")"; 4168 OS << "LoadOp\"]\n";
4172 const auto& V = src->getValue();
4180 printVarName(V, OS);
4181 OS << quot <<
" -> " << quot <<
this << quot <<
"\n";
4186 OS <<
" " << quot <<
this << quot <<
" -> " << quot;
4187 printVarName(VS, OS);
4191 const std::vector<std::function<std::function<OpNode*(NodeContainer*)>(
4207 RangeRef
eval()
const override;
4241 void print(std::ostream& OS)
const override;
4242 void printDot(std::ostream& OS)
const override;
4246 :
OpNode(ValueRangeRef(new
ValueRange(_sink->getMaxRange())), _sink, nullptr), source(_source)
4269 using SymbMap = std::map<tree_nodeConstRef, CustomSet<OpNode*>, tree_reindexCompare>;
4276 bool checkWorklist()
const;
4277 bool checkComponents()
const;
4278 bool checkTopologicalSort(
const UseMap& useMap)
const;
4280 const UseMap& useMap)
const;
4286 std::map<tree_nodeConstRef, int, tree_reindexCompare>
dfs;
4287 std::map<tree_nodeConstRef, tree_nodeConstRef, tree_reindexCompare>
root;
4289 std::map<tree_nodeConstRef, CustomSet<VarNode*>, tree_reindexCompare>
components;
4306 void delControlDependenceEdges(
UseMap& useMap);
4307 void visit(
const tree_nodeConstRef& V, std::stack<tree_nodeConstRef>&
stack,
const UseMap& useMap);
4312 "Required component not found (" +
GET_CONST_NODE(n)->ToString() +
")");
4313 return components.at(n);
4316 using iterator = std::deque<tree_nodeConstRef>::reverse_iterator;
4320 return worklist.rbegin();
4324 return worklist.crbegin();
4328 return worklist.rend();
4332 return worklist.crend();
4357 for(
const auto& vNode : varNodes)
4360 dfs[vNode.first] = -1;
4364 for(
const auto& vNode : varNodes)
4367 if(
dfs[vNode.first] < 0)
4371 std::stack<tree_nodeConstRef> pilha;
4373 visit(vNode.first, pilha, useMap);
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");
4395 for(
const auto& varOps : symbMap)
4397 for(
const auto& op : varOps.second)
4399 THROW_ASSERT(static_cast<bool>(vars.count(varOps.first)),
"Variable should be stored in VarNodes map");
4400 auto* source = vars.at(varOps.first);
4402 useMap[varOps.first].insert(cdedge);
4412 for(
auto& varOps : useMap)
4414 std::deque<ControlDepNode*> cds;
4415 for(
auto sit : varOps.second)
4417 if(
auto* cd = GetOp<ControlDepNode>(sit))
4427 const auto& V = cd->getSource()->getValue();
4434 pseudoEdgesString <<
" " <<
'"';
4435 printVarName(V, pseudoEdgesString);
4436 pseudoEdgesString <<
'"' <<
" -> ";
4438 const auto& VS = cd->getSink()->getValue();
4439 pseudoEdgesString <<
'"';
4440 printVarName(VS, pseudoEdgesString);
4441 pseudoEdgesString <<
'"';
4442 pseudoEdgesString <<
" [style=dashed]\n";
4445 varOps.second.erase(cd);
4464 for(
const auto& op : useMap.at(V))
4467 const auto& sink = op->getSink()->getValue();
4471 visit(sink, stack, useMap);
4476 root[V] = root[sink];
4490 while(!stack.empty() && (
dfs[stack.top()] >
dfs[V]))
4492 auto node = stack.top();
4505 bool Nuutila::checkWorklist()
const 4507 bool consistent =
true;
4508 for(
auto nit =
cbegin(), nend =
cend(); nit != nend;)
4511 for(
const auto& v2 : boost::make_iterator_range(++nit,
cend()))
4524 bool Nuutila::checkComponents()
const 4526 bool isConsistent =
true;
4527 for(
auto n1it =
cbegin(), n1end =
cend(); n1it != n1end;)
4529 const auto& component1 =
components.at(*n1it);
4530 for(
const auto& n2 : boost::make_iterator_range(++n1it,
cend()))
4533 if(&component1 == &component2)
4536 "[Nuutila::checkComponent] Component [" +
STR(&component1) +
", " +
STR(component1.size()) +
4538 isConsistent =
false;
4542 return isConsistent;
4549 const UseMap& useMap)
const 4551 for(
const auto& v : componentFrom)
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))
4557 if(static_cast<bool>(componentTo.count(op->getSink())))
4566 bool Nuutila::checkTopologicalSort(
const UseMap& useMap)
const 4568 bool isConsistent =
true;
4569 for(
auto n1it =
cbegin(), nend =
cend(); n1it != nend; ++n1it)
4571 const auto& curr_component =
components.at(*n1it);
4574 for(
const auto& n2 : boost::make_iterator_range(
cbegin(), n1it))
4576 const auto& prev_component =
components.at(n2);
4577 if(hasEdge(curr_component, prev_component, useMap))
4579 isConsistent =
false;
4583 return isConsistent;
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);
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);
4618 for(
const auto& vapint : constantvector)
4633 for(
auto vit = constantvector.rbegin(), vend = constantvector.rend(); vit != vend; ++vit)
4635 const auto& vapint = *vit;
4647 const auto newInterval = op->
eval();
4654 " -> " + newInterval->ToString());
4659 "FIXED::%artificial phi : " + oldInterval->ToString() +
" -> " + newInterval->ToString());
4661 return !oldInterval->isSameRange(newInterval);
4673 const auto newRange = op->
eval();
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())
4680 if(oldInterval->isAnti() && newInterval->isAnti() && !newInterval->isSameRange(oldInterval))
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);
4691 if(newLower > oldLower || newUpper < oldUpper)
4693 const auto& l = newLower > oldLower ? nlconstant : oldLower;
4694 const auto& u = newUpper < oldUpper ? nuconstant : oldUpper;
4699 return RangeRef(
new Range(
Anti, bw, l, u));
4706 if(!oldInterval->isUnknown() && oldInterval->isFullSet() && newInterval->isAnti())
4708 return RangeRef(oldInterval->clone());
4710 if(oldInterval->isRegular() && newInterval->isAnti())
4712 return oldInterval->unionWith(newInterval);
4714 return RangeRef(newInterval->clone());
4719 const auto& oldLower = oldInterval->getLower();
4720 const auto& oldUpper = oldInterval->getUpper();
4721 const auto& newLower = newInterval->getLower();
4722 const auto& newUpper = newInterval->getUpper();
4725 const auto& nlconstant = getFirstLessFromVector(constantvector, newLower);
4726 const auto& nuconstant = getFirstGreaterFromVector(constantvector, newUpper);
4728 if(newLower < oldLower || newUpper > oldUpper)
4730 return RangeRef(
new Range(
Regular, bw, newLower < oldLower ? nlconstant : oldLower,
4731 newUpper > oldUpper ? nuconstant : oldUpper));
4735 return RangeRef(oldInterval->clone());
4738 const auto widen = intervalWiden(oldRange, newRange);
4749 " -> " + newRange->ToString() +
" -> " + sinkRange->ToString());
4754 "WIDEN::@artificial phi : " + oldRange->ToString() +
" -> " + newRange->ToString() +
" -> " +
4755 sinkRange->ToString());
4757 return !oldRange->isSameRange(sinkRange);
4763 const auto newRange = op->
eval();
4765 auto intervalGrowth = [](RangeConstRef oldInterval, RangeConstRef newInterval) {
4766 if(oldInterval->isUnknown() || oldInterval->isEmpty() || oldInterval->isAnti() || newInterval->isEmpty() ||
4767 newInterval->isAnti())
4769 return RangeRef(newInterval->clone());
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();
4779 if(newLower < oldLower || newUpper > oldUpper)
4782 newUpper > oldUpper ?
Range::Max : oldUpper));
4786 return RangeRef(oldInterval->clone());
4796 " -> " + sinkRange->ToString());
4801 "GROWTH::%artificial phi : " + oldRange->ToString() +
" -> " + sinkRange->ToString());
4803 return !oldRange->isSameRange(sinkRange);
4813 const auto newRange = op->
eval();
4815 auto intervalNarrow = [&](RangeConstRef oldInterval, RangeConstRef newInterval) {
4816 if(newInterval->isConstant())
4818 return RangeRef(newInterval->clone());
4820 const auto bw = oldInterval->getBitWidth();
4821 if(oldInterval->isAnti() || newInterval->isAnti() || oldInterval->isEmpty() || newInterval->isEmpty())
4823 if(oldInterval->isAnti() && newInterval->isAnti() && !newInterval->isSameRange(oldInterval))
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);
4834 if(oldLower < nlconstant && oldUpper > nuconstant)
4836 if(nlconstant <= nuconstant)
4838 return RangeRef(
new Range(
Anti, bw, nlconstant, nuconstant));
4842 if(oldLower < nlconstant)
4844 return RangeRef(
new Range(
Anti, bw, nlconstant, oldUpper));
4846 if(oldUpper > nuconstant)
4848 return RangeRef(
new Range(
Anti, bw, oldLower, nuconstant));
4851 else if(newInterval->isUnknown() || !newInterval->isFullSet())
4853 return RangeRef(newInterval->clone());
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());
4865 sinkInterval = RangeRef(
new Range(
Regular, bw, nLower, oUpper));
4867 else if(nLower < oLower)
4869 sinkInterval = RangeRef(
new Range(
Regular, bw, nLower, oUpper));
4871 if(!sinkInterval->isAnti())
4875 sinkInterval = RangeRef(
new Range(
Regular, bw, sinkInterval->getLower(), nUpper));
4877 else if(oUpper < nUpper)
4879 sinkInterval = RangeRef(
new Range(
Regular, bw, sinkInterval->getLower(), nUpper));
4882 return sinkInterval;
4884 return RangeRef(oldInterval->clone());
4887 const auto narrow = intervalNarrow(oldRange, newRange);
4897 " -> " + sinkRange->ToString());
4902 "NARROW::%artificial phi : " + oldRange->ToString() +
" -> " + sinkRange->ToString());
4904 return !oldRange->isSameRange(sinkRange);
4910 const auto newRange = op->
eval();
4913 auto intervalCrop = [](RangeConstRef oldInterval, RangeConstRef newInterval,
char abstractState) {
4914 if(oldInterval->isAnti() || newInterval->isAnti() || oldInterval->isEmpty() || newInterval->isEmpty())
4916 return RangeRef(newInterval->clone());
4920 const auto bw = oldInterval->getBitWidth();
4921 if((abstractState ==
'-' || abstractState ==
'?') && (newInterval->getLower() > oldInterval->getLower()))
4923 return RangeRef(
new Range(
Regular, bw, newInterval->getLower(), oldInterval->getUpper()));
4926 if((abstractState ==
'+' || abstractState ==
'?') && (newInterval->getUpper() < oldInterval->getUpper()))
4928 return RangeRef(
new Range(
Regular, bw, oldInterval->getLower(), newInterval->getUpper()));
4930 return RangeRef(oldInterval->clone());
4934 op->
getSink()->
setRange(intervalCrop(oldRange, newRange, _abstractState));
4941 " -> " + sinkRange->ToString());
4946 "CROP::%artificial phi : " + oldRange->ToString() +
" -> " + sinkRange->ToString());
4948 return !oldRange->isSameRange(sinkRange);
4962 void update(
const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& actv,
4963 std::function<
bool(
OpNode*,
const std::vector<APInt>&)> meet)
4965 while(!actv.empty())
4967 const auto V = *actv.begin();
4972 const auto&
L = compUseMap.at(V);
4978 if(meet(op, constantvector))
4982 const auto& val = op->getSink()->getValue();
4990 void update(
size_t nIterations,
const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& actv)
4992 std::deque<tree_nodeConstRef> queue(actv.begin(), actv.end());
4994 while(!queue.empty())
4996 const auto V = queue.front();
4999 const auto&
L = compUseMap.at(V);
5002 if(nIterations == 0)
5009 const auto& next = op->getSink()->getValue();
5010 if(std::find(queue.begin(), queue.end(), next) == queue.end())
5012 queue.push_back(next);
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,
5042 std::vector<APInt> constantvector;
5054 unsigned int buildCVR(
const gimple_cond* br,
const blocRef branchBB,
unsigned int function_id)
5066 "Non SSA variable found in branch (" +
GET_CONST_NODE(br->
op0)->get_kind_text() +
" " +
5071 "Branch condition is " + Cond->get_kind_text() +
" " + Cond->ToString());
5073 if(
const auto* bin_op = GetPointer<const binary_expr>(Cond))
5081 if(!isValidType(bin_op->op0) || !isValidType(bin_op->op1))
5088 addVarNode(bin_op->op0, function_id);
5089 addVarNode(bin_op->op1, function_id);
5092 const auto TrueBBI = branchBB->true_edge;
5093 const auto FalseBBI = branchBB->false_edge;
5098 tree_nodeConstRef constant =
nullptr;
5099 tree_nodeConstRef variable =
nullptr;
5102 "Op0 is " + Op0->get_kind_text() +
" and Op1 is " + Op1->get_kind_text());
5105 if(GetPointer<const cst_node>(Op0) !=
nullptr && GetPointer<const cst_node>(Op1) !=
nullptr)
5120 if(GetPointer<const cst_node>(Op0) !=
nullptr)
5123 variable = bin_op->op1;
5126 else if(GetPointer<const cst_node>(Op1) !=
nullptr)
5129 variable = bin_op->op0;
5134 if(constant !=
nullptr)
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());
5147 auto FValues = TValues->isFullSet() ? getRangeFor(variable,
Empty) : TValues->getAnti();
5149 if(bin_op->get_kind() == eq_expr_K)
5151 FValues = getRangeFor(variable,
Regular);
5153 else if(bin_op->get_kind() == ne_expr_K)
5155 TValues = getRangeFor(variable,
Regular);
5159 const auto BT = ValueRangeRef(
new ValueRange(TValues));
5160 const auto BF = ValueRangeRef(
new ValueRange(FValues));
5166 if(
const auto* Var = GetPointer<const ssa_name>(
GET_CONST_NODE(variable)))
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 ||
5172 const auto* cast_inst = GetPointer<const unary_expr>(
GET_CONST_NODE(VDef->op1));
5177 "Op0 comes from a cast expression " + cast_inst->ToString());
5182 "Op1 comes from a cast expression" + cast_inst->ToString());
5186 const auto _BT = ValueRangeRef(
new ValueRange(TValues));
5187 const auto _BF = ValueRangeRef(
new ValueRange(FValues));
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);
5200 #if !defined(NDEBUG) or HAVE_ASSERTS 5201 const auto bw0 = getGIMPLE_BW(bin_op->op0);
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) +
").");
5209 const auto CR = getRangeFor(bin_op->op0,
Unknown);
5213 const auto STOp0 = ValueRangeRef(
new SymbRange(CR, bin_op->op1, pred));
5214 const auto SFOp0 = ValueRangeRef(
new SymbRange(CR, bin_op->op1, invPred));
5219 if(
const auto* Var = GetPointer<const ssa_name>(Op0))
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 ||
5225 const auto* cast_inst = GetPointer<const unary_expr>(
GET_CONST_NODE(VDef->op1));
5227 "Op0 comes from a cast expression " + cast_inst->ToString());
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));
5232 addConditionalValueRange(
ConditionalValueRange(cast_inst->op, TrueBBI, FalseBBI, STOp0_0, SFOp0_0));
5237 const auto STOp1 = ValueRangeRef(
new SymbRange(CR, bin_op->op0, swappred));
5238 const auto SFOp1 = ValueRangeRef(
new SymbRange(CR, bin_op->op0, invSwappred));
5242 if(
const auto* Var = GetPointer<const ssa_name>(Op1))
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 ||
5248 const auto* cast_inst = GetPointer<const unary_expr>(
GET_CONST_NODE(VDef->op1));
5250 "Op1 comes from a cast expression" + cast_inst->ToString());
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));
5255 addConditionalValueRange(
ConditionalValueRange(cast_inst->op, TrueBBI, FalseBBI, STOp1_1, SFOp1_1));
5271 "Multi-way if with " +
STR(mwi->
list_of_cond.size()) +
" conditions");
5275 unsigned int DefaultBBI = 0;
5280 DefaultBBI = condBBI.second;
5295 if(GetPointer<const cst_node>(
GET_CONST_NODE(condBBI.first)) !=
nullptr)
5298 "Branch variable is a cst_node, dead code elimination necessary!");
5304 "Case conditional variable should be an ssa_name (" +
5308 if(
const auto* cmp_op = GetPointer<const binary_expr>(case_compare))
5316 if(!isValidType(cmp_op->op0) || !isValidType(cmp_op->op1))
5323 addVarNode(cmp_op->op0, function_id);
5324 addVarNode(cmp_op->op1, function_id);
5330 tree_nodeConstRef variable =
nullptr;
5333 "Op0 is " + Op0->get_kind_text() +
" and Op1 is " + Op1->get_kind_text());
5336 if(GetPointer<const cst_node>(Op0) !=
nullptr && GetPointer<const cst_node>(Op1) !=
nullptr)
5339 "Both operands are constants, dead code elimination necessary!");
5349 if((constant = GetPointer<const integer_cst>(Op0)) !=
nullptr)
5351 variable = cmp_op->op1;
5353 else if((constant = GetPointer<const integer_cst>(Op1)) !=
nullptr)
5356 variable = cmp_op->op0;
5361 if(constant !=
nullptr)
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);
5368 "Variable bitwidth is " +
STR(bw) +
" and constant value is " +
STR(constant->
value));
5375 RangeRef TValues = tmpT->isFullSet() ? RangeRef(
new Range(
Regular, bw)) : tmpT;
5378 auto BT = ValueRangeRef(
new ValueRange(TValues));
5379 switchSSAMap[variable].insert(std::make_pair(condBBI.second, BT));
5383 if(
const auto* Var = GetPointer<const ssa_name>(
GET_CONST_NODE(variable)))
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 ||
5389 const auto* cast_inst = GetPointer<const unary_expr>(
GET_CONST_NODE(VDef->op1));
5394 "Op0 comes from a cast expression " + cast_inst->ToString());
5399 "Op1 comes from a cast expression" + cast_inst->ToString());
5403 auto _BT = ValueRangeRef(
new ValueRange(TValues));
5404 switchSSAMap[cast_inst->op].insert(std::make_pair(condBBI.second, _BT));
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);
5413 #if !defined(NDEBUG) or HAVE_ASSERTS 5414 const auto bw0 = getGIMPLE_BW(cmp_op->op0);
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) +
").");
5422 const auto CR = getRangeFor(cmp_op->op0,
Unknown);
5426 const auto STOp0 = ValueRangeRef(
new SymbRange(CR, cmp_op->op1, pred));
5427 switchSSAMap[cmp_op->op0].insert(std::make_pair(condBBI.second, STOp0));
5430 if(
const auto* Var = GetPointer<const ssa_name>(Op0))
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 ||
5436 const auto* cast_inst = GetPointer<const unary_expr>(
GET_CONST_NODE(VDef->op1));
5438 "Op0 comes from a cast expression" + cast_inst->ToString());
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));
5446 const auto STOp1 = ValueRangeRef(
new SymbRange(CR, cmp_op->op0, swappred));
5447 switchSSAMap[cmp_op->op1].insert(std::make_pair(condBBI.second, STOp1));
5450 if(
const auto* Var = GetPointer<const ssa_name>(Op1))
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 ||
5456 const auto* cast_inst = GetPointer<const unary_expr>(
GET_CONST_NODE(VDef->op1));
5458 "Op1 comes from a cast expression" + cast_inst->ToString());
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));
5469 "Multi-way condition different from binary_expr not handled, skipping... (" +
5470 case_compare->get_kind_text() +
" " + case_compare->ToString() +
")");
5478 if(static_cast<bool>(DefaultBBI))
5480 for(
auto& varVSM : switchSSAMap)
5482 auto elseRange = getRangeFor(varVSM.first,
Empty);
5483 for(
const auto& BBIinterval : varVSM.second)
5485 elseRange = elseRange->unionWith(BBIinterval.second->getRange());
5487 elseRange = elseRange->getAnti();
5488 varVSM.second.insert(std::make_pair(DefaultBBI, ValueRangeRef(
new ValueRange(elseRange))));
5492 for(
const auto& varVSM : switchSSAMap)
5508 for(
auto vit = component.begin(), vend = component.end(); vit != vend; ++vit)
5513 auto& list = compUseMap[V];
5515 auto p = getUses().find(V);
5517 for(
auto* opit : p->second)
5519 VarNode* sink = opit->getSink();
5521 if(static_cast<bool>(component.count(sink)))
5533 void insertConstantIntoVector(
const APInt& constantval,
bw_t bw)
5535 constantvector.push_back(constantval.
extOrTrunc(bw,
true));
5548 constantvector.clear();
5553 for(
const auto* varNode : component)
5555 const auto& V = varNode->getValue();
5556 if(
const auto* ic = GetPointer<const integer_cst>(
GET_CONST_NODE(V)))
5564 for(
const auto* varNode : component)
5566 const auto& V = varNode->getValue();
5567 auto dfit = getDefs().find(V);
5568 if(dfit == getDefs().
end())
5573 auto pushConstFor = [
this](
const APInt& cst,
bw_t bw,
kind pred) {
5576 if(pred == eq_expr_K || pred == ne_expr_K)
5578 insertConstantIntoVector(cst, bw);
5579 insertConstantIntoVector(cst - 1, bw);
5580 insertConstantIntoVector(cst + 1, bw);
5582 else if(pred == uneq_expr_K)
5585 insertConstantIntoVector(ucst, bw);
5586 insertConstantIntoVector(ucst - 1, bw);
5587 insertConstantIntoVector(ucst + 1, bw);
5589 else if(pred == gt_expr_K || pred == le_expr_K)
5591 insertConstantIntoVector(cst, bw);
5592 insertConstantIntoVector(cst + 1, bw);
5594 else if(pred == ge_expr_K || pred == lt_expr_K)
5596 insertConstantIntoVector(cst, bw);
5597 insertConstantIntoVector(cst - 1, bw);
5599 else if(pred == ungt_expr_K || pred == unle_expr_K)
5602 insertConstantIntoVector(ucst, bw);
5603 insertConstantIntoVector(ucst + 1, bw);
5605 else if(pred == unge_expr_K || pred == unlt_expr_K)
5608 insertConstantIntoVector(ucst, bw);
5609 insertConstantIntoVector(ucst - 1, bw);
5618 insertConstantIntoVector(cst, bw);
5623 if(
const auto* bop = GetOp<BinaryOpNode>(dfit->second))
5625 const auto* source1 = bop->getSource1();
5626 const auto& sourceval1 = source1->getValue();
5627 const auto* source2 = bop->getSource2();
5628 const auto& sourceval2 = source2->getValue();
5630 const auto pred = bop->getOpcode();
5632 if(
const auto* const1 = GetPointer<const integer_cst>(
GET_CONST_NODE(sourceval1)))
5634 const auto bw = source1->getBitWidth();
5636 pushConstFor(cst_val, bw, pred);
5638 if(
const auto* const2 = GetPointer<const integer_cst>(
GET_CONST_NODE(sourceval2)))
5640 const auto bw = source2->getBitWidth();
5642 pushConstFor(cst_val, bw, pred);
5646 else if(
const auto*
pop = GetOp<PhiOpNode>(dfit->second))
5648 for(
size_t i = 0, e =
pop->getNumSources(); i < e; ++i)
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)))
5661 for(
const auto& varOps : compusemap)
5663 for(
const auto* op : varOps.second)
5665 const auto* sigma = GetOp<SigmaOpNode>(op);
5671 const auto rintersect = op->getIntersect()->getRange();
5672 const auto bw = rintersect->getBitWidth();
5673 if(rintersect->isAnti())
5675 const auto anti = rintersect->getAnti();
5676 const auto& lb = anti->getLower();
5677 const auto& ub = anti->getUpper();
5680 insertConstantIntoVector(lb - 1, bw);
5681 insertConstantIntoVector(lb, bw);
5685 insertConstantIntoVector(ub, bw);
5686 insertConstantIntoVector(ub + 1, bw);
5691 const auto& lb = rintersect->getLower();
5692 const auto& ub = rintersect->getUpper();
5695 insertConstantIntoVector(lb - 1, bw);
5696 insertConstantIntoVector(lb, bw);
5700 insertConstantIntoVector(ub, bw);
5701 insertConstantIntoVector(ub + 1, bw);
5708 std::sort(constantvector.begin(), constantvector.end(), [](
const APInt& i1,
const APInt& i2) {
return i1 < i2; });
5714 auto last = std::unique(constantvector.begin(), constantvector.end());
5715 constantvector.erase(last, constantvector.end());
5723 void buildSymbolicIntersectMap()
5729 for(
auto* op : getOpNodes())
5732 auto* uop = GetOp<UnaryOpNode>(op);
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())
5740 p->second.insert(uop);
5746 symbMap.insert(std::make_pair(V, l));
5759 const auto& uses = getUses();
5760 for(
const auto& var : component)
5762 const auto& V = var->getValue();
5763 const auto& p = uses.at(V);
5768 if(component.contains(op->getSink()))
5772 auto* sigmaop = GetOp<SigmaOpNode>(op);
5773 op->getSink()->setRange(op->eval());
5774 if((sigmaop !=
nullptr) && sigmaop->getIntersect()->getRange()->isUnknown())
5776 sigmaop->markUnresolved();
5783 std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints)
5786 for(
VarNode* varNode : component)
5788 const auto& V = varNode->getValue();
5789 if(
const auto* ssa = GetPointer<const ssa_name>(
GET_CONST_NODE(V)))
5791 if(
const auto* phi_def = GetPointer<const gimple_phi>(
GET_CONST_NODE(ssa->CGetDefStmt())))
5793 if(phi_def->CGetDefEdgesList().size() == 1)
5795 auto dit = getDefs().find(V);
5796 if(dit != getDefs().
end())
5798 auto* bop = dit->second;
5799 auto* defop = GetOp<SigmaOpNode>(bop);
5801 if((defop !=
nullptr) && defop->isUnresolved())
5803 defop->getSink()->setRange(bop->eval());
5804 defop->markResolved();
5810 if(!varNode->getRange()->isUnknown())
5812 entryPoints.insert(V);
5820 for(
auto* varNode : component)
5822 solveFuturesSC(varNode);
5826 void solveFuturesSC(
VarNode* varNode)
5828 const auto& V = varNode->
getValue();
5829 auto sit = symbMap.find(V);
5830 if(sit != symbMap.end())
5833 for(
auto* op : sit->second)
5836 op->solveFuture(varNode);
5843 std::set<tree_nodeConstRef, tree_reindexCompare>& activeVars)
5845 for(
auto* varNode : component)
5847 const auto& V = varNode->
getValue();
5848 const auto* CI = GetPointer<const integer_cst>(
GET_CONST_NODE(V));
5853 activeVars.insert(V);
5860 auto parmMapIt = parmMap.find(FD->
index);
5861 if(parmMapIt == parmMap.end())
5864 .insert(std::make_pair(
5865 FD->
index, std::make_pair(
false, std::vector<tree_nodeConstRef>(
args.size(),
nullptr))))
5868 auto& foundAll = parmMapIt->second.first;
5875 auto& parmBind = parmMapIt->second.second;
5877 for(
const auto& ssa_use_counter : ssa_uses)
5879 auto ssa = ssa_use_counter.first;
5880 const auto* SSA = GetPointer<const ssa_name>(
GET_CONST_NODE(ssa));
5883 if(SSA->var !=
nullptr && GET_CONST_NODE(SSA->var)->get_kind() == parm_decl_K &&
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();
5901 bool storeFunctionCall(
const tree_nodeConstRef tn)
5905 if(
const auto* ga = GetPointer<const gimple_assign>(
GET_CONST_NODE(tn)))
5907 if(
const auto* ce = GetPointer<const call_expr>(
GET_CONST_NODE(ga->op1)))
5912 if(
const auto* ce = GetPointer<const gimple_call>(
GET_CONST_NODE(tn)))
5921 const auto* ue = GetPointer<const unary_expr>(
GET_NODE(fun_node));
5924 else if(
GET_NODE(fun_node)->get_kind() == obj_type_ref_K)
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");
5933 "Analysing function call to " +
5936 AppM->CGetFunctionBehavior(FD->
index)->CGetBehavioralHelper()))));
5938 auto it = callMap.find(FD->
index);
5939 if(it == callMap.end())
5941 it = callMap.insert(std::make_pair(FD->
index, std::list<tree_nodeConstRef>())).first;
5943 it->second.emplace_back(tn);
5953 int _debug_level,
int _graph_debug
5962 graph_debug(_graph_debug),
5971 ~ConstraintGraph()
override =
default;
5983 bool buildGraph(
unsigned int function_id)
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));
5990 std::string fn_name =
5995 "Analysing function " + fn_name +
" with " +
STR(SL->list_of_bloc.size()) +
" blocks");
5999 for(
const auto& idxBB : SL->list_of_bloc)
6001 const auto& stmt_list = idxBB.second->CGetStmtList();
6002 if(stmt_list.empty())
6009 "BB" +
STR(idxBB.first) +
" has terminator type " + terminator->get_kind_text() +
" " +
6010 terminator->ToString());
6012 if(
const auto* br = GetPointer<const gimple_cond>(terminator))
6014 #ifdef EARLY_DEAD_CODE_RESTART 6015 if(buildCVR(br, idxBB.second, function_id))
6023 buildCVR(br, idxBB.second, function_id);
6026 else if(
const auto* mwi = GetPointer<const gimple_multi_way_if>(terminator))
6028 #ifdef EARLY_DEAD_CODE_RESTART 6029 if(buildCVR(mwi, idxBB.second, function_id))
6035 buildCVR(mwi, idxBB.second, function_id);
6042 for(
const auto& idxBB : SL->list_of_bloc)
6044 const auto& phi_list = idxBB.second->CGetPhiList();
6047 for(
const auto& stmt : phi_list)
6049 parametersBinding(stmt, FD);
6050 if(isValidInstruction(stmt, FB))
6052 addOperation(stmt, function_id, FB, TM, AppM);
6057 const auto& stmt_list = idxBB.second->CGetStmtList();
6058 if(stmt_list.size())
6060 for(
const auto& stmt : stmt_list)
6062 if(!isValidInstruction(stmt, FB))
6064 parametersBinding(stmt, FD);
6065 if(!storeFunctionCall(stmt))
6072 addOperation(stmt, function_id, FB, TM, AppM);
6073 parametersBinding(stmt, FD);
6082 void buildVarNodes()
6085 for(
auto& pair : getVarNodes())
6087 pair.second->init(!static_cast<bool>(getDefs().count(pair.first)));
6097 buildSymbolicIntersectMap();
6100 Nuutila sccList(getVarNodes(), getUses(), symbMap, graph_debug);
6102 Nuutila sccList(getVarNodes(), getUses(), symbMap);
6105 for(
const auto& n : sccList)
6107 const auto& component = sccList.getComponent(n);
6114 for(
const auto* var : component)
6121 if(component.size() == 1)
6123 VarNode* var = *component.begin();
6124 solveFuturesSC(var);
6125 auto varDef = getDefs().find(var->
getValue());
6126 if(varDef != getDefs().end())
6128 auto* op = varDef->second;
6138 const auto compUseMap = buildUseMap(component);
6143 buildConstantVector(component, compUseMap);
6147 std::stringstream ss;
6148 for(
const auto& cnst : constantvector)
6152 if(!constantvector.empty())
6155 "Constant lattice: {-inf, " + ss.str() +
"+inf}");
6162 std::set<tree_nodeConstRef, tree_reindexCompare> entryPoints;
6164 auto printEntryFor = [&](
const std::string& mType) {
6169 for(
const auto&
el : entryPoints)
6178 generateEntryPoints(component, entryPoints);
6180 printEntryFor(
"Fixed");
6183 update(static_cast<size_t>(component.size() * 16
L), compUseMap, entryPoints);
6186 "Printed constraint graph to " +
6189 generateEntryPoints(component, entryPoints);
6191 printEntryFor(
"Widen");
6194 preUpdate(compUseMap, entryPoints);
6196 solveFutures(component);
6199 "Printed constraint graph to " +
6203 for(
VarNode* varNode : component)
6205 if(varNode->
getRange()->isUnknown())
6214 "Printed constraint graph to " +
6218 std::set<tree_nodeConstRef, tree_reindexCompare> activeVars;
6219 generateActivesVars(component, activeVars);
6221 printEntryFor(
"Narrow");
6223 posUpdate(compUseMap, activeVars, component);
6225 propagateToNextSCC(component);
6229 "Printed final constraint graph to " + printToFile(step_name +
".constraints.dot", parameters));
6233 std::string printToFile(
const std::string& file_name,
const ParameterConstRef parameters)
const 6235 std::string output_directory = parameters->getOption<std::string>(OPT_dot_directory) +
"RangeAnalysis/";
6236 if(!std::filesystem::exists(output_directory))
6238 std::filesystem::create_directories(output_directory);
6240 const std::string
full_name = output_directory + file_name;
6241 std::ofstream
file(full_name);
6248 void printDot(std::ostream& OS)
const 6250 const char* quot = R
"(")"; 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";
6258 for(
const auto& varNode : getVarNodes())
6267 printVarName(varNode.first, OS);
6270 OS << R
"( [label=")" << varNode.second << "\"]\n";
6273 for(
auto* op : getOpNodes())
6278 OS << pseudoEdgesString.str();
6288 class Cousot :
public ConstraintGraph
6291 void preUpdate(
const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints)
override 6296 void posUpdate(
const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints,
6304 : ConstraintGraph(_AppM, _debug_level, _graph_debug)
6312 class CropDFS :
public ConstraintGraph
6315 void preUpdate(
const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& entryPoints)
override 6320 void posUpdate(
const UseMap& compUseMap, std::set<tree_nodeConstRef, tree_reindexCompare>& ,
6323 storeAbstractStates(component);
6324 for(
const auto& op : getOpNodes())
6326 if(static_cast<bool>(component.count(op->getSink())))
6328 crop(compUseMap, op);
6335 for(
const auto& varNode : component)
6337 varNode->storeAbstractState();
6347 activeOps.insert(op);
6349 while(!activeOps.empty())
6351 auto* V = *activeOps.begin();
6353 const VarNode* sink = V->getSink();
6356 if(static_cast<bool>(visitedOps.count(sink)))
6362 visitedOps.insert(sink);
6365 const auto&
L = compUseMap.at(sink->
getValue());
6368 activeOps.insert(opr);
6375 : ConstraintGraph(_AppM, _debug_level, _graph_debug)
6381 const ConstraintGraphRef CG,
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);
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)
6400 if(
const auto& p = parmBind.at(i))
6402 const auto pType = getGIMPLE_Type(p);
6403 if(!isValidType(pType))
6406 "Parameter " +
STR(i) +
" is of non-valid type (" +
GET_CONST_NODE(pType)->get_kind_text() +
6413 VarNode* sink = CG->addVarNode(p, function_id);
6416 const auto parm = GetPointer<const parm_decl>(
GET_CONST_NODE(
FD->list_of_args.at(i)));
6417 if(parm->range !=
nullptr)
6421 "---User-defined hints found " + parm->range->ToString());
6433 const ConstraintGraphRef CG,
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 6445 TM, function_id,
false,
true,
false, 0
U,
6449 "Parameters and return value propagation on function " + fn_name);
6452 if(!static_cast<bool>(CG->getCallMap()->count(function_id)))
6458 const auto& functionCalls = CG->getCallMap()->at(function_id);
6463 std::vector<std::pair<tree_nodeConstRef, tree_nodeConstRef>>
parameters(
FD->list_of_args.size());
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;
6472 std::vector<PhiOpNode*> matchers(
parameters.size(),
nullptr);
6473 for(
size_t i = 0; i <
parameters.size(); ++i)
6475 if(
const auto& p = parmBind.at(i))
6477 const auto pType = getGIMPLE_Type(p);
6478 if(!isValidType(pType))
6481 "Parameter " +
STR(i) +
" is of non-valid type (" +
GET_CONST_NODE(pType)->get_kind_text() +
6489 VarNode* sink = CG->addVarNode(p, function_id);
6492 const auto parm = GetPointer<const parm_decl>(
GET_CONST_NODE(
FD->list_of_args.at(i)));
6493 if(parm->range !=
nullptr)
6497 "---User-defined hints found " + parm->range->ToString());
6515 bool noReturn = ret_type ==
nullptr || !isValidType(ret_type);
6518 (noReturn ?
"no return type" : (
"return type " +
GET_CONST_NODE(ret_type)->get_kind_text())));
6522 std::vector<VarNode*> returnVars;
6525 const auto* SL = GetPointer<const statement_list>(
GET_CONST_NODE(
FD->body));
6526 for(
const auto& idxBB : SL->list_of_bloc)
6528 const auto& stmt_list = idxBB.second->CGetStmtList();
6530 if(stmt_list.size())
6532 if(
const auto* gr = GetPointer<const gimple_return>(
GET_CONST_NODE(stmt_list.back())))
6534 if(gr->op !=
nullptr)
6536 returnVars.push_back(CG->addVarNode(gr->op, function_id));
6542 if(returnVars.empty() && !noReturn)
6545 if(isValidType(ret_type))
6548 "---Function should return, but no return statement was found");
6558 std::string(
"Function ") + (noReturn ?
"has no" :
"has explicit") +
" return statement" +
6559 (returnVars.size() > 1 ?
"s" :
""));
6561 for(
const auto& call : functionCalls)
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)))
6568 const auto* ce = GetPointer<const call_expr>(
GET_CONST_NODE(ga->op1));
6572 else if(
const auto* gc = GetPointer<const gimple_call>(
GET_CONST_NODE(call)))
6582 for(
size_t i = 0; i <
parameters.size(); ++i)
6593 for(
size_t i = 0; i <
parameters.size(); ++i)
6598 "Parameter " +
STR(i) +
" was constant, matching not necessary");
6605 from = CG->addVarNode(
parameters[i].second, function_id);
6608 matchers[i]->addSource(from);
6613 if(!noReturn &&
GET_CONST_NODE(call)->get_kind() != gimple_call_K)
6616 to = CG->addVarNode(ret_var, function_id);
6620 for(
VarNode* var : returnVars)
6624 CG->pushOperation(phiOp);
6629 std::string phiString =
6631 for(
size_t i = 0; i < phiOp->getNumSources(); ++i)
6635 phiString[phiString.size() - 2] =
'>';
6645 pair.second =
nullptr;
6649 for(
auto* m : matchers)
6655 CG->pushOperation(m);
6660 for(
size_t i = 0; i < m->getNumSources(); ++i)
6664 phiString[phiString.size() - 2] =
'>';
6681 stop_iteration(std::numeric_limits<decltype(stop_iteration)>::
max()),
6682 stop_transformation(std::numeric_limits<decltype(stop_transformation)>::
max())
6692 for(
const auto& opt : opts)
6696 ra_mode.insert(opt);
6699 if(ra_mode.erase(
"crop"))
6703 if(ra_mode.erase(
"noESSA"))
6706 requireESSA =
false;
6709 if(ra_mode.erase(
"ro"))
6715 if(ra_mode.erase(
"skip"))
6721 if(ra_mode.erase(
"debug_op"))
6726 if(ra_mode.erase(
"debug_graph"))
6757 if(ra_mode.size() && ra_mode.begin()->size())
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)
6763 auto tr = ++ra_mode.begin();
6764 if(it->front() ==
't')
6766 it = ++ra_mode.begin();
6767 tr = ra_mode.begin();
6770 stop_transformation = std::strtoull(
tr->data() +
sizeof(char),
nullptr, 10);
6771 if(stop_transformation == 0)
6776 "Range analysis: only " +
STR(stop_transformation) +
" transformation" +
6777 (stop_transformation > 1 ?
"s" :
"") +
" will run on last iteration");
6779 if(it->front() ==
'i')
6781 stop_iteration = std::strtoull(it->data() +
sizeof(char),
nullptr, 10);
6785 stop_iteration = std::strtoull(it->data(),
nullptr, 10);
6787 if(stop_iteration == 0)
6789 THROW_ERROR(
"Invalid range analysis option: " + *it);
6792 "Range analysis: only " +
STR(stop_iteration) +
" iteration" + (stop_iteration > 1 ?
"s" :
"") +
6796 THROW_ASSERT(ra_mode.empty(),
"Invalid range analysis mode falgs. (" + *ra_mode.begin() +
")");
6808 return relationships;
6810 switch(relationship_type)
6812 case DEPENDENCE_RELATIONSHIP:
6814 if(!
parameters->getOption<
int>(OPT_gcc_openmp_simd))
6816 relationships.insert(std::make_pair(BIT_VALUE_OPT,
ALL_FUNCTIONS));
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));
6828 relationships.insert(std::make_pair(IR_LOWERING,
ALL_FUNCTIONS));
6831 relationships.insert(std::make_pair(SOFT_FLOAT_CG_EXT,
ALL_FUNCTIONS));
6833 relationships.insert(std::make_pair(USE_COUNTING,
ALL_FUNCTIONS));
6836 case PRECEDENCE_RELATIONSHIP:
6838 relationships.insert(std::make_pair(UN_COMPARISON_LOWERING,
ALL_FUNCTIONS));
6841 case INVALIDATION_RELATIONSHIP:
6850 return relationships;
6856 if(relationship_type == INVALIDATION_RELATIONSHIP)
6858 if(!
parameters->getOption<
int>(OPT_gcc_openmp_simd))
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)
6865 const auto frontend_bv = dfm->GetDesignFlowStep(bv_signature);
6867 const auto bv = design_flow_graph->CGetDesignFlowStepInfo(frontend_bv)->design_flow_step;
6868 relationships.insert(bv);
6871 fun_id_to_restart.clear();
6879 if(iteration >= stop_iteration || execution_mode ==
RA_EXEC_SKIP)
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())
6891 const auto FB = AppM->CGetFunctionBehavior(i);
6895 return cur_bb_ver != last_bb_ver || cur_bitvalue_ver != last_bitvalue_ver;
6901 fun_id_to_restart.clear();
6907 if(iteration >= stop_iteration || execution_mode ==
RA_EXEC_SKIP)
6918 ConstraintGraphRef CG;
6923 CG.reset(
new Cousot(AppM,
6932 CG.reset(
new CropDFS(AppM,
6934 debug_level, graph_debug));
6945 #if defined(EARLY_DEAD_CODE_RESTART) || !defined(NDEBUG) 6946 const auto TM = AppM->get_tree_manager();
6950 #ifdef EARLY_DEAD_CODE_RESTART 6951 for(
const auto f : rb_funcs)
6953 bool dead_code_necessary = CG->buildGraph(f);
6954 if(dead_code_necessary)
6956 fun_id_to_restart.insert(f);
6959 if(fun_id_to_restart.size())
6963 for(
const auto f_id : fun_id_to_restart)
6965 const auto FB = AppM->GetFunctionBehavior(f_id);
6977 for(
const auto& f : rb_funcs)
6985 for(
const auto& top_fn : AppM->CGetCallGraphManager()->GetRootFunctions())
6990 AppM->CGetFunctionBehavior(top_fn)->CGetBehavioralHelper()))) +
6991 " is top function");
6992 TopFunctionUserHits(top_fn, AppM, CG,
debug_level);
6993 rb_funcs.erase(top_fn);
6997 for(
const auto f : rb_funcs)
6999 ParmAndRetValPropagation(f, AppM, CG,
debug_level);
7002 CG->buildVarNodes();
7005 CG->findIntervals(
parameters, GetName() +
"(" +
STR(iteration) +
")");
7008 CG->findIntervals();
7013 const auto modified = finalize(CG);
7014 if(stop_iteration != std::numeric_limits<decltype(stop_iteration)>::
max())
7017 "Iteration " +
STR(iteration) +
"/" +
STR(stop_iteration) +
"completed (" +
7018 STR(stop_iteration - iteration) +
" to go)");
7037 const auto& vars = std::static_pointer_cast<
const ConstraintGraph>(CG)->getVarNodes();
7045 for(
const auto& varNode : vars)
7048 "Range " + varNode.second->getRange()->ToString() +
" for " +
7057 const auto TM = AppM->get_tree_manager();
7060 unsigned long long updated = 0;
7064 for(
const auto& varNode : vars)
7067 if(iteration == stop_iteration && updated >= stop_transformation)
7070 "Max required transformations performed. IR update aborted.");
7074 if(
const auto ut = varNode.second->updateIR(TM,
debug_level, AppM))
7078 const auto funID = varNode.second->getFunctionId();
7079 modifiedFunctionsBit.insert(funID);
7088 "Bounds updated for " +
STR(updated) +
"/" +
STR(vars.size()) +
" variables");
7093 const auto rbf = AppM->CGetCallGraphManager()->GetReachedBodyFunctions();
7094 const auto cgm = AppM->CGetCallGraphManager();
7095 const auto cg = cgm->CGetCallGraph();
7097 const auto TM = AppM->get_tree_manager();
7101 "Modified BitValues " +
STR(modifiedFunctionsBit.size()) +
" functions:");
7103 for(
const auto fUT : modifiedFunctionsBit)
7108 AppM->CGetFunctionBehavior(fUT)->CGetBehavioralHelper()))));
7109 fun_id_to_restart.insert(fUT);
7113 for(
const auto f : rbf)
7115 const auto FB = AppM->GetFunctionBehavior(f);
7116 auto isInBit = fun_id_to_restart.count(f);
7128 return !fun_id_to_restart.empty();
#define GET_NODE(t)
Macro used to hide implementation details when accessing a tree_node from another tree_node...
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.
APInt & extOrTrunc(bw_t bw, bool sign)
kind getOpcode() const
Return the opcode of the operation.
integer_cst_t value
The value of the integer cast.
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.
Data structure representing the entire HLS information.
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 APInt getSignedMinValue(bw_t bw)
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 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 *)
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
Step successfully executed.
ValueRange & operator=(const ValueRange &)=delete
#define CASE_BINARY_EXPRESSION
This macro collects all case labels for binary_expr objects.
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)
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.
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...
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
size_t getNumSources() const
return the number of sources
RelationshipType
The relationship type.
struct definition of the function_decl tree node.
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.
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.
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
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
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)
A simple interface to token object of the raw files.
std::vector< tree_nodeConstRef > getSources() const override
static bool classof(OpNode const *BO)
ValueRange(const RangeConstRef &range)
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...
std::deque< tree_nodeConstRef >::const_reverse_iterator const_iterator
This struct specifies the gimple_cond node.
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)
struct vcFloat::_FP_STRUCT_LAYOUT __attribute__((packed))
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)
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 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 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
#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.
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 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
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.
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.
const CustomSet< VarNode * > & getComponent(const tree_nodeConstRef &n) const
static bool classof(UnaryOpNode const *)
Specific type of OpNode used in Nuutila's strongly connected components algorithm.
#define CASE_UNARY_EXPRESSION
This macro collects all case labels for unary_expr objects.
std::deque< tree_nodeConstRef > worklist
static RangeRef makeSatisfyingCmpRegion(kind pred, const RangeConstRef &Other)
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.
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.
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...
static const bw_t max_digits
Classes to describe design flow graph.
tree_nodeRef body
body field is the saved representation of the body of the entire function.
static APInt getMaxValue(bw_t bw)
VarNode * getSink() const
Returns the target of the operation, that is, where the result will be stored.
static bool classof(OpNode const *BO)
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)
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.
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.
std::string ToString() const
virtual void print(std::ostream &OS) const =0
Prints the content of the operation.
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
SigmaOpNode & operator=(const SigmaOpNode &)=delete
CONSTREF_FORWARD_DECL(ValueRange)
static bool classof(OpNode const *BO)
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.
This file collects some utility functions.
static void constrainSSA(ssa_name *op_ssa, tree_managerRef TM)
std::vector< tree_nodeRef > list_of_args
args field holds a chain of parm_decl nodes for the arguments.
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)
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
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])
virtual OperationId getValueId() const =0
UnaryOpNode(const ValueRangeRef &intersect, VarNode *sink, const tree_nodeConstRef &inst, VarNode *source, kind opcode)
std::string ToString() const
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)
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.
static const APInt & getFirstLessFromVector(const std::vector< APInt > &constantvector, const APInt &val)
static bool classof(LoadOpNode const *)
static bool classof(OpNode const *)
void printDot(std::ostream &OS) const override
void * pop(node_stack **head)
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.
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.
static bool classof(OpNode const *BO)
static bw_t neededBits(const APInt &a, const APInt &b, bool sign)
std::map< tree_nodeConstRef, tree_nodeConstRef, tree_reindexCompare > root
static APInt getMinValue(bw_t bw)
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.
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)
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.
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.
static unsigned int get_base_index(const tree_managerConstRef &TM, const unsigned int index)
Retrun the base address of a memory access.
std::string bit_values
for each bit of the SSA variable tells if it is equal to U,X,0,1
This struct specifies the ssa_name node.
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.
CustomMap< unsigned int, std::list< tree_nodeConstRef > > CallMap
std::vector< tree_nodeConstRef > getSources() const override
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.
bool isUnresolved() const
VarNode & operator=(const VarNode &)=delete
tree_nodeRef type
starting from GCC 4.7.2 ssa_name has a type
#define GET_INDEX_CONST_NODE(t)
const UseMap & getUses() const
struct definition of the binary node structures.
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)
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
const VarNodes & getVarNodes() const
OperationId getValueId() const override
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)
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
std::map< tree_nodeConstRef, ConditionalValueRange, tree_reindexCompare > ConditionalValueRanges
#define NULL_VERTEX
null vertex definition
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 CASE_TERNARY_EXPRESSION
This macro collects all case labels for ternary_expr objects.
Class specification of the manager of the tree structures extracted from the raw file.
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.
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 ...