diff options
Diffstat (limited to 'gcc/analyzer/constraint-manager.cc')
| -rw-r--r-- | gcc/analyzer/constraint-manager.cc | 1385 |
1 files changed, 1359 insertions, 26 deletions
diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc index 4dadd20..6df23fb 100644 --- a/gcc/analyzer/constraint-manager.cc +++ b/gcc/analyzer/constraint-manager.cc @@ -42,12 +42,14 @@ along with GCC; see the file COPYING3. If not see #include "sbitmap.h" #include "bitmap.h" #include "tristate.h" +#include "analyzer/analyzer-logging.h" #include "analyzer/call-string.h" #include "analyzer/program-point.h" #include "analyzer/store.h" #include "analyzer/region-model.h" #include "analyzer/constraint-manager.h" #include "analyzer/analyzer-selftests.h" +#include "tree-pretty-print.h" #if ENABLE_ANALYZER @@ -65,6 +67,50 @@ compare_constants (tree lhs_const, enum tree_code op, tree rhs_const) return tristate (tristate::TS_UNKNOWN); } +/* Return true iff CST is below the maximum value for its type. */ + +static bool +can_plus_one_p (tree cst) +{ + gcc_assert (CONSTANT_CLASS_P (cst)); + return tree_int_cst_lt (cst, TYPE_MAX_VALUE (TREE_TYPE (cst))); +} + +/* Return (CST + 1). */ + +static tree +plus_one (tree cst) +{ + gcc_assert (CONSTANT_CLASS_P (cst)); + gcc_assert (can_plus_one_p (cst)); + tree result = fold_build2 (PLUS_EXPR, TREE_TYPE (cst), + cst, integer_one_node); + gcc_assert (CONSTANT_CLASS_P (result)); + return result; +} + +/* Return true iff CST is above the minimum value for its type. */ + +static bool +can_minus_one_p (tree cst) +{ + gcc_assert (CONSTANT_CLASS_P (cst)); + return tree_int_cst_lt (TYPE_MIN_VALUE (TREE_TYPE (cst)), cst); +} + +/* Return (CST - 1). */ + +static tree +minus_one (tree cst) +{ + gcc_assert (CONSTANT_CLASS_P (cst)); + gcc_assert (can_minus_one_p (cst)); + tree result = fold_build2 (MINUS_EXPR, TREE_TYPE (cst), + cst, integer_one_node); + gcc_assert (CONSTANT_CLASS_P (result)); + return result; +} + /* struct bound. */ /* Ensure that this bound is closed by converting an open bound to a @@ -255,6 +301,678 @@ range::above_upper_bound (tree rhs_const) const m_upper_bound.m_constant).is_true (); } +/* struct bounded_range. */ + +bounded_range::bounded_range (const_tree lower, const_tree upper) +: m_lower (const_cast<tree> (lower)), + m_upper (const_cast<tree> (upper)) +{ + if (lower && upper) + { + gcc_assert (TREE_CODE (m_lower) == INTEGER_CST); + gcc_assert (TREE_CODE (m_upper) == INTEGER_CST); + /* We should have lower <= upper. */ + gcc_assert (!tree_int_cst_lt (m_upper, m_lower)); + } + else + { + /* Purely for pending on-stack values, for + writing back to. */ + gcc_assert (m_lower == NULL_TREE); + gcc_assert (m_lower == NULL_TREE); + } +} + +static void +dump_cst (pretty_printer *pp, tree cst, bool show_types) +{ + gcc_assert (cst); + if (show_types) + { + pp_character (pp, '('); + dump_generic_node (pp, TREE_TYPE (cst), 0, (dump_flags_t)0, false); + pp_character (pp, ')'); + } + dump_generic_node (pp, cst, 0, (dump_flags_t)0, false); +} + +/* Dump this object to PP. */ + +void +bounded_range::dump_to_pp (pretty_printer *pp, bool show_types) const +{ + if (tree_int_cst_equal (m_lower, m_upper)) + dump_cst (pp, m_lower, show_types); + else + { + pp_character (pp, '['); + dump_cst (pp, m_lower, show_types); + pp_string (pp, ", "); + dump_cst (pp, m_upper, show_types); + pp_character (pp, ']'); + } +} + +/* Dump this object to stderr. */ + +void +bounded_range::dump (bool show_types) const +{ + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + pp_show_color (&pp) = pp_show_color (global_dc->printer); + pp.buffer->stream = stderr; + dump_to_pp (&pp, show_types); + pp_newline (&pp); + pp_flush (&pp); +} + +json::object * +bounded_range::to_json () const +{ + json::object *range_obj = new json::object (); + set_json_attr (range_obj, "lower", m_lower); + set_json_attr (range_obj, "upper", m_upper); + return range_obj; +} + +/* Subroutine of bounded_range::to_json. */ + +void +bounded_range::set_json_attr (json::object *obj, const char *name, tree value) +{ + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + pp_printf (&pp, "%E", value); + obj->set (name, new json::string (pp_formatted_text (&pp))); +} + + +/* Return true iff CST is within this range. */ + +bool +bounded_range::contains_p (tree cst) const +{ + /* Reject if below lower bound. */ + if (tree_int_cst_lt (cst, m_lower)) + return false; + /* Reject if above lower bound. */ + if (tree_int_cst_lt (m_upper, cst)) + return false; + return true; +} + +/* If this range intersects OTHER, return true, writing + the intersection to *OUT if OUT is non-NULL. + Return false if they do not intersect. */ + +bool +bounded_range::intersects_p (const bounded_range &other, + bounded_range *out) const +{ + const tree max_lower + = (tree_int_cst_le (m_lower, other.m_lower) + ? other.m_lower : m_lower); + gcc_assert (TREE_CODE (max_lower) == INTEGER_CST); + const tree min_upper + = (tree_int_cst_le (m_upper, other.m_upper) + ? m_upper : other.m_upper); + gcc_assert (TREE_CODE (min_upper) == INTEGER_CST); + + if (tree_int_cst_le (max_lower, min_upper)) + { + if (out) + *out = bounded_range (max_lower, min_upper); + return true; + } + else + return false; +} + +bool +bounded_range::operator== (const bounded_range &other) const +{ + return (tree_int_cst_equal (m_lower, other.m_lower) + && tree_int_cst_equal (m_upper, other.m_upper)); +} + +int +bounded_range::cmp (const bounded_range &br1, const bounded_range &br2) +{ + if (int cmp_lower = tree_int_cst_compare (br1.m_lower, + br2.m_lower)) + return cmp_lower; + return tree_int_cst_compare (br1.m_upper, br2.m_upper); +} + +/* struct bounded_ranges. */ + +/* Construct a bounded_ranges instance from a single range. */ + +bounded_ranges::bounded_ranges (const bounded_range &range) +: m_ranges (1) +{ + m_ranges.quick_push (range); + canonicalize (); + validate (); +} + +/* Construct a bounded_ranges instance from multiple ranges. */ + +bounded_ranges::bounded_ranges (const vec<bounded_range> &ranges) +: m_ranges (ranges.length ()) +{ + m_ranges.safe_splice (ranges); + canonicalize (); + validate (); +} + +/* Construct a bounded_ranges instance for values of LHS for which + (LHS OP RHS_CONST) is true (e.g. "(LHS > 3)". */ + +bounded_ranges::bounded_ranges (enum tree_code op, tree rhs_const) +: m_ranges () +{ + gcc_assert (TREE_CODE (rhs_const) == INTEGER_CST); + tree type = TREE_TYPE (rhs_const); + switch (op) + { + default: + gcc_unreachable (); + case EQ_EXPR: + m_ranges.safe_push (bounded_range (rhs_const, rhs_const)); + break; + + case GE_EXPR: + m_ranges.safe_push (bounded_range (rhs_const, TYPE_MAX_VALUE (type))); + break; + + case LE_EXPR: + m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type), rhs_const)); + break; + + case NE_EXPR: + if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const)) + m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type), + minus_one (rhs_const))); + if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type))) + m_ranges.safe_push (bounded_range (plus_one (rhs_const), + TYPE_MAX_VALUE (type))); + break; + case GT_EXPR: + if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type))) + m_ranges.safe_push (bounded_range (plus_one (rhs_const), + TYPE_MAX_VALUE (type))); + break; + case LT_EXPR: + if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const)) + m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type), + minus_one (rhs_const))); + break; + } + canonicalize (); + validate (); +} + +/* Subroutine of ctors for fixing up m_ranges. + Also, initialize m_hash. */ + +void +bounded_ranges::canonicalize () +{ + /* Sort the ranges. */ + m_ranges.qsort ([](const void *p1, const void *p2) -> int + { + const bounded_range &br1 = *(const bounded_range *)p1; + const bounded_range &br2 = *(const bounded_range *)p2; + return bounded_range::cmp (br1, br2); + }); + + /* Merge ranges that are touching or overlapping. */ + for (unsigned i = 1; i < m_ranges.length (); ) + { + bounded_range *prev = &m_ranges[i - 1]; + const bounded_range *next = &m_ranges[i]; + if (prev->intersects_p (*next, NULL) + || (can_plus_one_p (prev->m_upper) + && tree_int_cst_equal (plus_one (prev->m_upper), + next->m_lower))) + { + prev->m_upper = next->m_upper; + m_ranges.ordered_remove (i); + } + else + i++; + } + + /* Initialize m_hash. */ + inchash::hash hstate (0); + for (const auto &iter : m_ranges) + { + inchash::add_expr (iter.m_lower, hstate); + inchash::add_expr (iter.m_upper, hstate); + } + m_hash = hstate.end (); +} + +/* Assert that this object is valid. */ + +void +bounded_ranges::validate () const +{ + /* Skip this in a release build. */ +#if !CHECKING_P + return; +#endif + + for (unsigned i = 1; i < m_ranges.length (); i++) + { + const bounded_range &prev = m_ranges[i - 1]; + const bounded_range &next = m_ranges[i]; + + /* Give up if we somehow have incompatible different types. */ + if (!types_compatible_p (TREE_TYPE (prev.m_upper), + TREE_TYPE (next.m_lower))) + continue; + + /* Verify sorted. */ + gcc_assert (tree_int_cst_lt (prev.m_upper, next.m_lower)); + + gcc_assert (can_plus_one_p (prev.m_upper)); + /* otherwise there's no room for "next". */ + + /* Verify no ranges touch each other. */ + gcc_assert (tree_int_cst_lt (plus_one (prev.m_upper), next.m_lower)); + } +} + +/* bounded_ranges equality operator. */ + +bool +bounded_ranges::operator== (const bounded_ranges &other) const +{ + if (m_ranges.length () != other.m_ranges.length ()) + return false; + for (unsigned i = 0; i < m_ranges.length (); i++) + { + if (m_ranges[i] != other.m_ranges[i]) + return false; + } + return true; +} + +/* Dump this object to PP. */ + +void +bounded_ranges::dump_to_pp (pretty_printer *pp, bool show_types) const +{ + pp_character (pp, '{'); + for (unsigned i = 0; i < m_ranges.length (); ++i) + { + if (i > 0) + pp_string (pp, ", "); + m_ranges[i].dump_to_pp (pp, show_types); + } + pp_character (pp, '}'); +} + +/* Dump this object to stderr. */ + +DEBUG_FUNCTION void +bounded_ranges::dump (bool show_types) const +{ + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + pp_show_color (&pp) = pp_show_color (global_dc->printer); + pp.buffer->stream = stderr; + dump_to_pp (&pp, show_types); + pp_newline (&pp); + pp_flush (&pp); +} + +json::value * +bounded_ranges::to_json () const +{ + json::array *arr_obj = new json::array (); + + for (unsigned i = 0; i < m_ranges.length (); ++i) + arr_obj->append (m_ranges[i].to_json ()); + + return arr_obj; +} + +/* Determine whether (X OP RHS_CONST) is known to be true or false + for all X in the ranges expressed by this object. */ + +tristate +bounded_ranges::eval_condition (enum tree_code op, + tree rhs_const, + bounded_ranges_manager *mgr) const +{ + /* Convert (X OP RHS_CONST) to a bounded_ranges instance and find + the intersection of that with this object. */ + bounded_ranges other (op, rhs_const); + const bounded_ranges *intersection + = mgr->get_or_create_intersection (this, &other); + + if (intersection->m_ranges.length () > 0) + { + /* We can use pointer equality to check for equality, + due to instance consolidation. */ + if (intersection == this) + return tristate (tristate::TS_TRUE); + else + return tristate (tristate::TS_UNKNOWN); + } + else + /* No intersection. */ + return tristate (tristate::TS_FALSE); +} + +/* Return true if CST is within any of the ranges. */ + +bool +bounded_ranges::contain_p (tree cst) const +{ + gcc_assert (TREE_CODE (cst) == INTEGER_CST); + for (const auto &iter : m_ranges) + { + /* TODO: should we optimize this based on sorting? */ + if (iter.contains_p (cst)) + return true; + } + return false; +} + +int +bounded_ranges::cmp (const bounded_ranges *a, const bounded_ranges *b) +{ + if (int cmp_length = ((int)a->m_ranges.length () + - (int)b->m_ranges.length ())) + return cmp_length; + for (unsigned i = 0; i < a->m_ranges.length (); i++) + { + if (int cmp_range = bounded_range::cmp (a->m_ranges[i], b->m_ranges[i])) + return cmp_range; + } + /* They are equal. They ought to have been consolidated, so we should + have two pointers to the same object. */ + gcc_assert (a == b); + return 0; +} + +/* class bounded_ranges_manager. */ + +/* bounded_ranges_manager's dtor. */ + +bounded_ranges_manager::~bounded_ranges_manager () +{ + /* Delete the managed objects. */ + for (const auto &iter : m_map) + delete iter.second; +} + +/* Get the bounded_ranges instance for the empty set, creating it if + necessary. */ + +const bounded_ranges * +bounded_ranges_manager::get_or_create_empty () +{ + auto_vec<bounded_range> empty_vec; + + return consolidate (new bounded_ranges (empty_vec)); +} + +/* Get the bounded_ranges instance for {CST}, creating it if necessary. */ + +const bounded_ranges * +bounded_ranges_manager::get_or_create_point (const_tree cst) +{ + gcc_assert (TREE_CODE (cst) == INTEGER_CST); + + return get_or_create_range (cst, cst); +} + +/* Get the bounded_ranges instance for {[LOWER_BOUND..UPPER_BOUND]}, + creating it if necessary. */ + +const bounded_ranges * +bounded_ranges_manager::get_or_create_range (const_tree lower_bound, + const_tree upper_bound) +{ + gcc_assert (TREE_CODE (lower_bound) == INTEGER_CST); + gcc_assert (TREE_CODE (upper_bound) == INTEGER_CST); + + return consolidate + (new bounded_ranges (bounded_range (lower_bound, upper_bound))); +} + +/* Get the bounded_ranges instance for the union of OTHERS, + creating it if necessary. */ + +const bounded_ranges * +bounded_ranges_manager:: +get_or_create_union (const vec <const bounded_ranges *> &others) +{ + auto_vec<bounded_range> ranges; + for (const auto &r : others) + ranges.safe_splice (r->m_ranges); + return consolidate (new bounded_ranges (ranges)); +} + +/* Get the bounded_ranges instance for the intersection of A and B, + creating it if necessary. */ + +const bounded_ranges * +bounded_ranges_manager::get_or_create_intersection (const bounded_ranges *a, + const bounded_ranges *b) +{ + auto_vec<bounded_range> ranges; + unsigned a_idx = 0; + unsigned b_idx = 0; + while (a_idx < a->m_ranges.length () + && b_idx < b->m_ranges.length ()) + { + const bounded_range &r_a = a->m_ranges[a_idx]; + const bounded_range &r_b = b->m_ranges[b_idx]; + + bounded_range intersection (NULL_TREE, NULL_TREE); + if (r_a.intersects_p (r_b, &intersection)) + { + ranges.safe_push (intersection); + } + if (tree_int_cst_lt (r_a.m_lower, r_b.m_lower)) + { + a_idx++; + } + else + { + if (tree_int_cst_lt (r_a.m_upper, r_b.m_upper)) + a_idx++; + else + b_idx++; + } + } + + return consolidate (new bounded_ranges (ranges)); +} + +/* Get the bounded_ranges instance for the inverse of OTHER relative + to TYPE, creating it if necessary. + This is for use when handling "default" in switch statements, where + OTHER represents all the other cases. */ + +const bounded_ranges * +bounded_ranges_manager::get_or_create_inverse (const bounded_ranges *other, + tree type) +{ + tree min_val = TYPE_MIN_VALUE (type); + tree max_val = TYPE_MAX_VALUE (type); + if (other->m_ranges.length () == 0) + return get_or_create_range (min_val, max_val); + auto_vec<bounded_range> ranges; + tree first_lb = other->m_ranges[0].m_lower; + if (tree_int_cst_lt (min_val, first_lb) + && can_minus_one_p (first_lb)) + ranges.safe_push (bounded_range (min_val, + minus_one (first_lb))); + for (unsigned i = 1; i < other->m_ranges.length (); i++) + { + tree prev_ub = other->m_ranges[i - 1].m_upper; + tree iter_lb = other->m_ranges[i].m_lower; + gcc_assert (tree_int_cst_lt (prev_ub, iter_lb)); + if (can_plus_one_p (prev_ub) && can_minus_one_p (iter_lb)) + ranges.safe_push (bounded_range (plus_one (prev_ub), + minus_one (iter_lb))); + } + tree last_ub + = other->m_ranges[other->m_ranges.length () - 1].m_upper; + if (tree_int_cst_lt (last_ub, max_val) + && can_plus_one_p (last_ub)) + ranges.safe_push (bounded_range (plus_one (last_ub), max_val)); + + return consolidate (new bounded_ranges (ranges)); +} + +/* If an object equal to INST is already present, delete INST and + return the existing object. + Otherwise add INST and return it. */ + +const bounded_ranges * +bounded_ranges_manager::consolidate (bounded_ranges *inst) +{ + if (bounded_ranges **slot = m_map.get (inst)) + { + delete inst; + return *slot; + } + m_map.put (inst, inst); + return inst; +} + +/* Get the bounded_ranges instance for EDGE of SWITCH_STMT, + creating it if necessary, and caching it by edge. */ + +const bounded_ranges * +bounded_ranges_manager:: +get_or_create_ranges_for_switch (const switch_cfg_superedge *edge, + const gswitch *switch_stmt) +{ + /* Look in per-edge cache. */ + if (const bounded_ranges ** slot = m_edge_cache.get (edge)) + return *slot; + + /* Not yet in cache. */ + const bounded_ranges *all_cases_ranges + = create_ranges_for_switch (*edge, switch_stmt); + m_edge_cache.put (edge, all_cases_ranges); + return all_cases_ranges; +} + +/* Get the bounded_ranges instance for EDGE of SWITCH_STMT, + creating it if necessary, for edges for which the per-edge + cache has not yet been populated. */ + +const bounded_ranges * +bounded_ranges_manager:: +create_ranges_for_switch (const switch_cfg_superedge &edge, + const gswitch *switch_stmt) +{ + /* Get the ranges for each case label. */ + auto_vec <const bounded_ranges *> case_ranges_vec + (gimple_switch_num_labels (switch_stmt)); + + for (tree case_label : edge.get_case_labels ()) + { + /* Get the ranges for this case label. */ + const bounded_ranges *case_ranges + = make_case_label_ranges (switch_stmt, case_label); + case_ranges_vec.quick_push (case_ranges); + } + + /* Combine all the ranges for each case label into a single collection + of ranges. */ + const bounded_ranges *all_cases_ranges + = get_or_create_union (case_ranges_vec); + return all_cases_ranges; +} + +/* Get the bounded_ranges instance for CASE_LABEL within + SWITCH_STMT. */ + +const bounded_ranges * +bounded_ranges_manager:: +make_case_label_ranges (const gswitch *switch_stmt, + tree case_label) +{ + gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR); + tree lower_bound = CASE_LOW (case_label); + tree upper_bound = CASE_HIGH (case_label); + if (lower_bound) + { + if (upper_bound) + /* Range. */ + return get_or_create_range (lower_bound, upper_bound); + else + /* Single-value. */ + return get_or_create_point (lower_bound); + } + else + { + /* The default case. + Add exclusions based on the other cases. */ + auto_vec <const bounded_ranges *> other_case_ranges + (gimple_switch_num_labels (switch_stmt)); + for (unsigned other_idx = 1; + other_idx < gimple_switch_num_labels (switch_stmt); + other_idx++) + { + tree other_label = gimple_switch_label (switch_stmt, + other_idx); + const bounded_ranges *other_ranges + = make_case_label_ranges (switch_stmt, other_label); + other_case_ranges.quick_push (other_ranges); + } + const bounded_ranges *other_cases_ranges + = get_or_create_union (other_case_ranges); + tree type = TREE_TYPE (gimple_switch_index (switch_stmt)); + return get_or_create_inverse (other_cases_ranges, type); + } +} + +/* Dump the number of objects of each class that were managed by this + manager to LOGGER. + If SHOW_OBJS is true, also dump the objects themselves. */ + +void +bounded_ranges_manager::log_stats (logger *logger, bool show_objs) const +{ + LOG_SCOPE (logger); + logger->log (" # %s: %li", "ranges", m_map.elements ()); + if (!show_objs) + return; + + auto_vec<const bounded_ranges *> vec_objs (m_map.elements ()); + for (const auto &iter : m_map) + vec_objs.quick_push (iter.second); + vec_objs.qsort + ([](const void *p1, const void *p2) -> int + { + const bounded_ranges *br1 = *(const bounded_ranges * const *)p1; + const bounded_ranges *br2 = *(const bounded_ranges * const *)p2; + return bounded_ranges::cmp (br1, br2); + }); + + for (const auto &iter : vec_objs) + { + logger->start_log_line (); + pretty_printer *pp = logger->get_printer (); + pp_string (pp, " "); + iter->dump_to_pp (pp, true); + logger->end_log_line (); + } +} + /* class equiv_class. */ /* equiv_class's default ctor. */ @@ -270,9 +988,7 @@ equiv_class::equiv_class (const equiv_class &other) : m_constant (other.m_constant), m_cst_sval (other.m_cst_sval), m_vars (other.m_vars.length ()) { - int i; - const svalue *sval; - FOR_EACH_VEC_ELT (other.m_vars, i, sval) + for (const svalue *sval : other.m_vars) m_vars.quick_push (sval); } @@ -310,9 +1026,7 @@ equiv_class::to_json () const json::object *ec_obj = new json::object (); json::array *sval_arr = new json::array (); - int i; - const svalue *sval; - FOR_EACH_VEC_ELT (m_vars, i, sval) + for (const svalue *sval : m_vars) sval_arr->append (sval->to_json ()); ec_obj->set ("svals", sval_arr); @@ -337,9 +1051,7 @@ equiv_class::hash () const inchash::hash hstate; inchash::add_expr (m_constant, hstate); - int i; - const svalue *sval; - FOR_EACH_VEC_ELT (m_vars, i, sval) + for (const svalue * sval : m_vars) hstate.add_ptr (sval); return hstate.end (); } @@ -582,6 +1294,49 @@ constraint::implied_by (const constraint &other, return false; } +/* class bounded_ranges_constraint. */ + +void +bounded_ranges_constraint::print (pretty_printer *pp, + const constraint_manager &cm) const +{ + m_ec_id.print (pp); + pp_string (pp, ": "); + m_ec_id.get_obj (cm).print (pp); + pp_string (pp, ": "); + m_ranges->dump_to_pp (pp, true); +} + +json::object * +bounded_ranges_constraint::to_json () const +{ + json::object *con_obj = new json::object (); + + con_obj->set ("ec", new json::integer_number (m_ec_id.as_int ())); + con_obj->set ("ranges", m_ranges->to_json ()); + + return con_obj; +} + +bool +bounded_ranges_constraint:: +operator== (const bounded_ranges_constraint &other) const +{ + if (m_ec_id != other.m_ec_id) + return false; + + /* We can compare by pointer, since the bounded_ranges_manager + consolidates instances. */ + return m_ranges == other.m_ranges; +} + +void +bounded_ranges_constraint::add_to_hash (inchash::hash *hstate) const +{ + hstate->add_int (m_ec_id.m_idx); + hstate->merge_hash (m_ranges->get_hash ()); +} + /* class equiv_class_id. */ /* Get the underlying equiv_class for this ID from CM. */ @@ -618,6 +1373,7 @@ equiv_class_id::print (pretty_printer *pp) const constraint_manager::constraint_manager (const constraint_manager &other) : m_equiv_classes (other.m_equiv_classes.length ()), m_constraints (other.m_constraints.length ()), + m_bounded_ranges_constraints (other.m_bounded_ranges_constraints.length ()), m_mgr (other.m_mgr) { int i; @@ -627,6 +1383,8 @@ constraint_manager::constraint_manager (const constraint_manager &other) constraint *c; FOR_EACH_VEC_ELT (other.m_constraints, i, c) m_constraints.quick_push (*c); + for (const auto &iter : other.m_bounded_ranges_constraints) + m_bounded_ranges_constraints.quick_push (iter); } /* constraint_manager's assignment operator. */ @@ -636,6 +1394,7 @@ constraint_manager::operator= (const constraint_manager &other) { gcc_assert (m_equiv_classes.length () == 0); gcc_assert (m_constraints.length () == 0); + gcc_assert (m_bounded_ranges_constraints.length () == 0); int i; equiv_class *ec; @@ -646,6 +1405,8 @@ constraint_manager::operator= (const constraint_manager &other) m_constraints.reserve (other.m_constraints.length ()); FOR_EACH_VEC_ELT (other.m_constraints, i, c) m_constraints.quick_push (*c); + for (const auto &iter : other.m_bounded_ranges_constraints) + m_bounded_ranges_constraints.quick_push (iter); return *this; } @@ -664,6 +1425,8 @@ constraint_manager::hash () const hstate.merge_hash (ec->hash ()); FOR_EACH_VEC_ELT (m_constraints, i, c) hstate.merge_hash (c->hash ()); + for (const auto &iter : m_bounded_ranges_constraints) + iter.add_to_hash (&hstate); return hstate.end (); } @@ -676,6 +1439,9 @@ constraint_manager::operator== (const constraint_manager &other) const return false; if (m_constraints.length () != other.m_constraints.length ()) return false; + if (m_bounded_ranges_constraints.length () + != other.m_bounded_ranges_constraints.length ()) + return false; int i; equiv_class *ec; @@ -690,6 +1456,13 @@ constraint_manager::operator== (const constraint_manager &other) const if (!(*c == other.m_constraints[i])) return false; + for (unsigned i = 0; i < m_bounded_ranges_constraints.length (); i++) + { + if (m_bounded_ranges_constraints[i] + != other.m_bounded_ranges_constraints[i]) + return false; + } + return true; } @@ -717,6 +1490,18 @@ constraint_manager::print (pretty_printer *pp) const pp_string (pp, " && "); c->print (pp, *this); } + if (m_bounded_ranges_constraints.length ()) + { + pp_string (pp, " | "); + i = 0; + for (const auto &iter : m_bounded_ranges_constraints) + { + if (i > 0) + pp_string (pp, " && "); + iter.print (pp, *this); + i++; + } + } pp_printf (pp, "}"); } @@ -768,6 +1553,30 @@ constraint_manager::dump_to_pp (pretty_printer *pp, bool multiline) const } if (!multiline) pp_string (pp, "}"); + if (m_bounded_ranges_constraints.length ()) + { + if (multiline) + pp_string (pp, " "); + pp_string (pp, "ranges:"); + if (multiline) + pp_newline (pp); + else + pp_string (pp, "{"); + i = 0; + for (const auto &iter : m_bounded_ranges_constraints) + { + if (multiline) + pp_string (pp, " "); + else if (i > 0) + pp_string (pp, " && "); + iter.print (pp, *this); + if (multiline) + pp_newline (pp); + i++; + } + if (!multiline) + pp_string (pp, "}"); + } } /* Dump a multiline representation of this constraint_manager to FP. */ @@ -811,9 +1620,7 @@ constraint_manager::to_json () const /* Equivalence classes. */ { json::array *ec_arr = new json::array (); - int i; - equiv_class *ec; - FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) + for (const equiv_class *ec : m_equiv_classes) ec_arr->append (ec->to_json ()); cm_obj->set ("ecs", ec_arr); } @@ -821,13 +1628,19 @@ constraint_manager::to_json () const /* Constraints. */ { json::array *con_arr = new json::array (); - int i; - constraint *c; - FOR_EACH_VEC_ELT (m_constraints, i, c) - con_arr->append (c->to_json ()); + for (const constraint &c : m_constraints) + con_arr->append (c.to_json ()); cm_obj->set ("constraints", con_arr); } + /* m_bounded_ranges_constraints. */ + { + json::array *con_arr = new json::array (); + for (const auto &c : m_bounded_ranges_constraints) + con_arr->append (c.to_json ()); + cm_obj->set ("bounded_ranges_constraints", con_arr); + } + return cm_obj; } @@ -843,9 +1656,9 @@ constraint_manager::add_constraint (const svalue *lhs, lhs = lhs->unwrap_any_unmergeable (); rhs = rhs->unwrap_any_unmergeable (); - /* Nothing can be known about unknown values. */ - if (lhs->get_kind () == SK_UNKNOWN - || rhs->get_kind () == SK_UNKNOWN) + /* Nothing can be known about unknown/poisoned values. */ + if (!lhs->can_have_associated_state_p () + || !rhs->can_have_associated_state_p ()) /* Not a contradiction. */ return true; @@ -946,6 +1759,8 @@ constraint_manager::add_unknown_constraint (equiv_class_id lhs_ec_id, if (final_ec != old_ec) m_equiv_classes[rhs_ec_id.m_idx] = final_ec; delete old_ec; + if (lhs_ec_id == final_ec_id) + lhs_ec_id = rhs_ec_id; /* Update the constraints. */ constraint *c; @@ -965,6 +1780,14 @@ constraint_manager::add_unknown_constraint (equiv_class_id lhs_ec_id, if (c->m_rhs == final_ec_id) c->m_rhs = rhs_ec_id; } + bounded_ranges_constraint *brc; + FOR_EACH_VEC_ELT (m_bounded_ranges_constraints, i, brc) + { + if (brc->m_ec_id == rhs_ec_id) + brc->m_ec_id = lhs_ec_id; + if (brc->m_ec_id == final_ec_id) + brc->m_ec_id = rhs_ec_id; + } /* We may now have self-comparisons due to the merger; these constraints should be removed. */ @@ -1018,6 +1841,8 @@ constraint_manager::add_constraint_internal (equiv_class_id lhs_id, /* Add the constraint. */ m_constraints.safe_push (new_c); + /* We don't yet update m_bounded_ranges_constraints here yet. */ + if (!flag_analyzer_transitivity) return; @@ -1151,6 +1976,80 @@ constraint_manager::add_constraint_internal (equiv_class_id lhs_id, } } +/* Attempt to add the constraint that SVAL is within RANGES to this + constraint_manager. + + Return true if the constraint was successfully added (or is already + known to be true). + Return false if the constraint contradicts existing knowledge. */ + +bool +constraint_manager::add_bounded_ranges (const svalue *sval, + const bounded_ranges *ranges) +{ + sval = sval->unwrap_any_unmergeable (); + + /* Nothing can be known about unknown/poisoned values. */ + if (!sval->can_have_associated_state_p ()) + /* Not a contradiction. */ + return true; + + /* If SVAL is a constant, then we can look at RANGES directly. */ + if (tree cst = sval->maybe_get_constant ()) + { + /* If the ranges contain CST, then it's a successful no-op; + otherwise it's a contradiction. */ + return ranges->contain_p (cst); + } + + equiv_class_id ec_id = get_or_add_equiv_class (sval); + + /* If the EC has a constant, it's either true or false. */ + const equiv_class &ec = ec_id.get_obj (*this); + if (tree ec_cst = ec.get_any_constant ()) + { + if (ranges->contain_p (ec_cst)) + /* We already have SVAL == EC_CST, within RANGES, so + we can discard RANGES and succeed. */ + return true; + else + /* We already have SVAL == EC_CST, not within RANGES, so + we can reject RANGES as a contradiction. */ + return false; + } + + /* We have at most one per ec_id. */ + /* Iterate through each range in RANGES. */ + for (auto iter : m_bounded_ranges_constraints) + { + if (iter.m_ec_id == ec_id) + { + /* Update with intersection, or fail if empty. */ + bounded_ranges_manager *mgr = get_range_manager (); + const bounded_ranges *intersection + = mgr->get_or_create_intersection (iter.m_ranges, ranges); + if (intersection->empty_p ()) + { + /* No intersection; fail. */ + return false; + } + else + { + /* Update with intersection; succeed. */ + iter.m_ranges = intersection; + validate (); + return true; + } + } + } + m_bounded_ranges_constraints.safe_push + (bounded_ranges_constraint (ec_id, ranges)); + + validate (); + + return true; +} + /* Look for SVAL within the equivalence classes of this constraint_manager; if found, return true, writing the id to *OUT if OUT is non-NULL, otherwise return false. */ @@ -1185,14 +2084,15 @@ constraint_manager::get_or_add_equiv_class (const svalue *sval) { equiv_class_id result (-1); - gcc_assert (sval->get_kind () != SK_UNKNOWN); + gcc_assert (sval->can_have_associated_state_p ()); /* Convert all NULL pointers to (void *) to avoid state explosions involving all of the various (foo *)NULL vs (bar *)NULL. */ - if (POINTER_TYPE_P (sval->get_type ())) - if (tree cst = sval->maybe_get_constant ()) - if (zerop (cst)) - sval = m_mgr->get_or_create_constant_svalue (null_pointer_node); + if (sval->get_type ()) + if (POINTER_TYPE_P (sval->get_type ())) + if (tree cst = sval->maybe_get_constant ()) + if (zerop (cst)) + sval = m_mgr->get_or_create_constant_svalue (null_pointer_node); /* Try svalue match. */ if (get_equiv_class_by_svalue (sval, &result)) @@ -1289,6 +2189,8 @@ constraint_manager::eval_condition (equiv_class_id lhs_ec, } } + /* We don't use m_bounded_ranges_constraints here yet. */ + return tristate (tristate::TS_UNKNOWN); } @@ -1414,6 +2316,12 @@ constraint_manager::eval_condition (equiv_class_id lhs_ec, } } } + + bounded_ranges_manager *mgr = get_range_manager (); + for (const auto &iter : m_bounded_ranges_constraints) + if (iter.m_ec_id == lhs_ec) + return iter.m_ranges->eval_condition (op, rhs_const, mgr); + /* Look at existing bounds on LHS_EC. */ range lhs_bounds = get_ec_bounds (lhs_ec); return lhs_bounds.eval_condition (op, rhs_const); @@ -1562,6 +2470,29 @@ constraint_manager::purge (const PurgeCriteria &p, purge_stats *stats) con_idx++; } } + + /* Update bounded_ranges_constraint instances. */ + for (unsigned r_idx = 0; + r_idx < m_bounded_ranges_constraints.length (); ) + { + bounded_ranges_constraint *brc + = &m_bounded_ranges_constraints[r_idx]; + + /* Remove if it refers to the deleted EC. */ + if (brc->m_ec_id == ec_idx) + { + m_bounded_ranges_constraints.ordered_remove (r_idx); + if (stats) + stats->m_num_bounded_ranges_constraints++; + } + else + { + /* Renumber any EC ids that refer to ECs that have + had their idx changed. */ + brc->m_ec_id.update_for_removal (ec_idx); + r_idx++; + } + } } else ec_idx++; @@ -1620,6 +2551,17 @@ constraint_manager::purge (const PurgeCriteria &p, purge_stats *stats) c->m_lhs.update_for_removal (ec_idx); c->m_rhs.update_for_removal (ec_idx); } + + /* Likewise for m_bounded_ranges_constraints. */ + for (unsigned r_idx = 0; + r_idx < m_bounded_ranges_constraints.length (); + r_idx++) + { + bounded_ranges_constraint *brc + = &m_bounded_ranges_constraints[r_idx]; + brc->m_ec_id.update_for_removal (ec_idx); + } + continue; } } @@ -1663,6 +2605,29 @@ on_liveness_change (const svalue_set &live_svalues, purge (p, NULL); } +class svalue_purger +{ +public: + svalue_purger (const svalue *sval) : m_sval (sval) {} + + bool should_purge_p (const svalue *sval) const + { + return sval->involves_p (m_sval); + } + +private: + const svalue *m_sval; +}; + +/* Purge any state involving SVAL. */ + +void +constraint_manager::purge_state_involving (const svalue *sval) +{ + svalue_purger p (sval); + purge (p, NULL); +} + /* Comparator for use by constraint_manager::canonicalize. Sort a pair of equiv_class instances, using the representative svalue as a sort key. */ @@ -1738,6 +2703,9 @@ constraint_manager::canonicalize () used_ecs.add (m_equiv_classes[c->m_rhs.as_int ()]); } + for (const auto &iter : m_bounded_ranges_constraints) + used_ecs.add (m_equiv_classes[iter.m_ec_id.as_int ()]); + /* Purge unused ECs: those that aren't used by constraints and that effectively have only one svalue (either in m_constant or in m_vars). */ @@ -1778,6 +2746,9 @@ constraint_manager::canonicalize () ec_id_map.update (&c->m_rhs); } + for (auto &iter : m_bounded_ranges_constraints) + ec_id_map.update (&iter.m_ec_id); + /* Finally, sort the constraints. */ m_constraints.qsort (constraint_cmp); } @@ -1822,6 +2793,32 @@ public: } } + void on_ranges (const svalue *lhs_sval, + const bounded_ranges *ranges) FINAL OVERRIDE + { + for (const auto &iter : m_cm_b->m_bounded_ranges_constraints) + { + const equiv_class &ec_rhs = iter.m_ec_id.get_obj (*m_cm_b); + for (unsigned i = 0; i < ec_rhs.m_vars.length (); i++) + { + const svalue *rhs_sval = ec_rhs.m_vars[i]; + if (lhs_sval == rhs_sval) + { + /* Union of the two ranges. */ + auto_vec <const bounded_ranges *> pair (2); + pair.quick_push (ranges); + pair.quick_push (iter.m_ranges); + bounded_ranges_manager *ranges_mgr + = m_cm_b->get_range_manager (); + const bounded_ranges *union_ + = ranges_mgr->get_or_create_union (pair); + bool sat = m_out->add_bounded_ranges (lhs_sval, union_); + gcc_assert (sat); + } + } + } + } + private: const constraint_manager *m_cm_b; constraint_manager *m_out; @@ -1895,6 +2892,16 @@ constraint_manager::for_each_fact (fact_visitor *visitor) const visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_vars[j]); } } + + for (const auto &iter : m_bounded_ranges_constraints) + { + const equiv_class &ec_lhs = iter.m_ec_id.get_obj (*this); + for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++) + { + const svalue *lhs_sval = ec_lhs.m_vars[i]; + visitor->on_ranges (lhs_sval, iter.m_ranges); + } + } } /* Assert that this object is valid. */ @@ -1932,12 +2939,24 @@ constraint_manager::validate () const FOR_EACH_VEC_ELT (m_constraints, i, c) { gcc_assert (!c->m_lhs.null_p ()); - gcc_assert (c->m_lhs.as_int () <= (int)m_equiv_classes.length ()); + gcc_assert (c->m_lhs.as_int () < (int)m_equiv_classes.length ()); gcc_assert (!c->m_rhs.null_p ()); - gcc_assert (c->m_rhs.as_int () <= (int)m_equiv_classes.length ()); + gcc_assert (c->m_rhs.as_int () < (int)m_equiv_classes.length ()); + } + + for (const auto &iter : m_bounded_ranges_constraints) + { + gcc_assert (!iter.m_ec_id.null_p ()); + gcc_assert (iter.m_ec_id.as_int () < (int)m_equiv_classes.length ()); } } +bounded_ranges_manager * +constraint_manager::get_range_manager () const +{ + return m_mgr->get_range_manager (); +} + #if CHECKING_P namespace selftest { @@ -2683,6 +3702,318 @@ test_many_constants () } } +/* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */ + +static void +assert_dump_bounded_range_eq (const location &loc, + const bounded_range &range, + const char *expected) +{ + auto_fix_quotes sentinel; + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + range.dump_to_pp (&pp, false); + ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected); +} + +/* Assert that BR.dump (false) is EXPECTED. */ + +#define ASSERT_DUMP_BOUNDED_RANGE_EQ(BR, EXPECTED) \ + SELFTEST_BEGIN_STMT \ + assert_dump_bounded_range_eq ((SELFTEST_LOCATION), (BR), (EXPECTED)); \ + SELFTEST_END_STMT + +/* Verify that bounded_range works as expected. */ + +static void +test_bounded_range () +{ + tree u8_0 = build_int_cst (unsigned_char_type_node, 0); + tree u8_1 = build_int_cst (unsigned_char_type_node, 1); + tree u8_64 = build_int_cst (unsigned_char_type_node, 64); + tree u8_128 = build_int_cst (unsigned_char_type_node, 128); + tree u8_255 = build_int_cst (unsigned_char_type_node, 255); + + tree s8_0 = build_int_cst (signed_char_type_node, 0); + tree s8_1 = build_int_cst (signed_char_type_node, 1); + tree s8_2 = build_int_cst (signed_char_type_node, 2); + + bounded_range br_u8_0 (u8_0, u8_0); + ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0, "0"); + ASSERT_TRUE (br_u8_0.contains_p (u8_0)); + ASSERT_FALSE (br_u8_0.contains_p (u8_1)); + ASSERT_TRUE (br_u8_0.contains_p (s8_0)); + ASSERT_FALSE (br_u8_0.contains_p (s8_1)); + + bounded_range br_u8_0_1 (u8_0, u8_1); + ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0_1, "[0, 1]"); + + bounded_range tmp (NULL_TREE, NULL_TREE); + ASSERT_TRUE (br_u8_0.intersects_p (br_u8_0_1, &tmp)); + ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "0"); + + bounded_range br_u8_64_128 (u8_64, u8_128); + ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_64_128, "[64, 128]"); + + ASSERT_FALSE (br_u8_0.intersects_p (br_u8_64_128, NULL)); + ASSERT_FALSE (br_u8_64_128.intersects_p (br_u8_0, NULL)); + + bounded_range br_u8_128_255 (u8_128, u8_255); + ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_128_255, "[128, 255]"); + ASSERT_TRUE (br_u8_128_255.intersects_p (br_u8_64_128, &tmp)); + ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "128"); + + bounded_range br_s8_2 (s8_2, s8_2); + ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2, "2"); + bounded_range br_s8_2_u8_255 (s8_2, u8_255); + ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2_u8_255, "[2, 255]"); +} + +/* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */ + +static void +assert_dump_bounded_ranges_eq (const location &loc, + const bounded_ranges *ranges, + const char *expected) +{ + auto_fix_quotes sentinel; + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + ranges->dump_to_pp (&pp, false); + ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected); +} + +/* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */ + +static void +assert_dump_bounded_ranges_eq (const location &loc, + const bounded_ranges &ranges, + const char *expected) +{ + auto_fix_quotes sentinel; + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + ranges.dump_to_pp (&pp, false); + ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected); +} + +/* Assert that BRS.dump (false) is EXPECTED. */ + +#define ASSERT_DUMP_BOUNDED_RANGES_EQ(BRS, EXPECTED) \ + SELFTEST_BEGIN_STMT \ + assert_dump_bounded_ranges_eq ((SELFTEST_LOCATION), (BRS), (EXPECTED)); \ + SELFTEST_END_STMT + +/* Verify that the bounded_ranges class works as expected. */ + +static void +test_bounded_ranges () +{ + bounded_ranges_manager mgr; + + tree ch0 = build_int_cst (unsigned_char_type_node, 0); + tree ch1 = build_int_cst (unsigned_char_type_node, 1); + tree ch2 = build_int_cst (unsigned_char_type_node, 2); + tree ch3 = build_int_cst (unsigned_char_type_node, 3); + tree ch128 = build_int_cst (unsigned_char_type_node, 128); + tree ch129 = build_int_cst (unsigned_char_type_node, 129); + tree ch254 = build_int_cst (unsigned_char_type_node, 254); + tree ch255 = build_int_cst (unsigned_char_type_node, 255); + + const bounded_ranges *empty = mgr.get_or_create_empty (); + ASSERT_DUMP_BOUNDED_RANGES_EQ (empty, "{}"); + + const bounded_ranges *point0 = mgr.get_or_create_point (ch0); + ASSERT_DUMP_BOUNDED_RANGES_EQ (point0, "{0}"); + + const bounded_ranges *point1 = mgr.get_or_create_point (ch1); + ASSERT_DUMP_BOUNDED_RANGES_EQ (point1, "{1}"); + + const bounded_ranges *point2 = mgr.get_or_create_point (ch2); + ASSERT_DUMP_BOUNDED_RANGES_EQ (point2, "{2}"); + + const bounded_ranges *range0_128 = mgr.get_or_create_range (ch0, ch128); + ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_128, "{[0, 128]}"); + + const bounded_ranges *range0_255 = mgr.get_or_create_range (ch0, ch255); + ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_255, "{[0, 255]}"); + + ASSERT_FALSE (empty->contain_p (ch0)); + ASSERT_FALSE (empty->contain_p (ch1)); + ASSERT_FALSE (empty->contain_p (ch255)); + + ASSERT_TRUE (point0->contain_p (ch0)); + ASSERT_FALSE (point0->contain_p (ch1)); + ASSERT_FALSE (point0->contain_p (ch255)); + + ASSERT_FALSE (point1->contain_p (ch0)); + ASSERT_TRUE (point1->contain_p (ch1)); + ASSERT_FALSE (point0->contain_p (ch255)); + + ASSERT_TRUE (range0_128->contain_p (ch0)); + ASSERT_TRUE (range0_128->contain_p (ch1)); + ASSERT_TRUE (range0_128->contain_p (ch128)); + ASSERT_FALSE (range0_128->contain_p (ch129)); + ASSERT_FALSE (range0_128->contain_p (ch254)); + ASSERT_FALSE (range0_128->contain_p (ch255)); + + const bounded_ranges *inv0_128 + = mgr.get_or_create_inverse (range0_128, unsigned_char_type_node); + ASSERT_DUMP_BOUNDED_RANGES_EQ (inv0_128, "{[129, 255]}"); + + const bounded_ranges *range128_129 = mgr.get_or_create_range (ch128, ch129); + ASSERT_DUMP_BOUNDED_RANGES_EQ (range128_129, "{[128, 129]}"); + + const bounded_ranges *inv128_129 + = mgr.get_or_create_inverse (range128_129, unsigned_char_type_node); + ASSERT_DUMP_BOUNDED_RANGES_EQ (inv128_129, "{[0, 127], [130, 255]}"); + + /* Intersection. */ + { + /* Intersection of disjoint ranges should be empty set. */ + const bounded_ranges *intersect0_1 + = mgr.get_or_create_intersection (point0, point1); + ASSERT_DUMP_BOUNDED_RANGES_EQ (intersect0_1, "{}"); + } + + /* Various tests of "union of ranges". */ + { + { + /* Touching points should be merged into a range. */ + auto_vec <const bounded_ranges *> v; + v.safe_push (point0); + v.safe_push (point1); + const bounded_ranges *union_0_and_1 = mgr.get_or_create_union (v); + ASSERT_DUMP_BOUNDED_RANGES_EQ (union_0_and_1, "{[0, 1]}"); + } + + { + /* Overlapping and out-of-order. */ + auto_vec <const bounded_ranges *> v; + v.safe_push (inv0_128); // {[129, 255]} + v.safe_push (range128_129); + const bounded_ranges *union_129_255_and_128_129 + = mgr.get_or_create_union (v); + ASSERT_DUMP_BOUNDED_RANGES_EQ (union_129_255_and_128_129, "{[128, 255]}"); + } + + { + /* Union of R and inverse(R) should be full range of type. */ + auto_vec <const bounded_ranges *> v; + v.safe_push (range128_129); + v.safe_push (inv128_129); + const bounded_ranges *union_ = mgr.get_or_create_union (v); + ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{[0, 255]}"); + } + + /* Union with an endpoint. */ + { + const bounded_ranges *range2_to_255 + = mgr.get_or_create_range (ch2, ch255); + ASSERT_DUMP_BOUNDED_RANGES_EQ (range2_to_255, "{[2, 255]}"); + auto_vec <const bounded_ranges *> v; + v.safe_push (point0); + v.safe_push (point2); + v.safe_push (range2_to_255); + const bounded_ranges *union_ = mgr.get_or_create_union (v); + ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{0, [2, 255]}"); + } + + /* Construct from vector of bounded_range. */ + { + auto_vec<bounded_range> v; + v.safe_push (bounded_range (ch2, ch2)); + v.safe_push (bounded_range (ch0, ch0)); + v.safe_push (bounded_range (ch2, ch255)); + bounded_ranges br (v); + ASSERT_DUMP_BOUNDED_RANGES_EQ (&br, "{0, [2, 255]}"); + } + } + + /* Various tests of "inverse". */ + { + { + const bounded_ranges *range_1_to_3 = mgr.get_or_create_range (ch1, ch3); + ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_3, "{[1, 3]}"); + const bounded_ranges *inv + = mgr.get_or_create_inverse (range_1_to_3, unsigned_char_type_node); + ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0, [4, 255]}"); + } + { + const bounded_ranges *range_1_to_255 + = mgr.get_or_create_range (ch1, ch255); + ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_255, "{[1, 255]}"); + const bounded_ranges *inv + = mgr.get_or_create_inverse (range_1_to_255, unsigned_char_type_node); + ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0}"); + } + { + const bounded_ranges *range_0_to_254 + = mgr.get_or_create_range (ch0, ch254); + ASSERT_DUMP_BOUNDED_RANGES_EQ (range_0_to_254, "{[0, 254]}"); + const bounded_ranges *inv + = mgr.get_or_create_inverse (range_0_to_254, unsigned_char_type_node); + ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{255}"); + } + } + + /* "case 'a'-'z': case 'A-Z':" vs "default:", for ASCII. */ + { + tree ch65 = build_int_cst (unsigned_char_type_node, 65); + tree ch90 = build_int_cst (unsigned_char_type_node, 90); + + tree ch97 = build_int_cst (unsigned_char_type_node, 97); + tree ch122 = build_int_cst (unsigned_char_type_node, 122); + + const bounded_ranges *A_to_Z = mgr.get_or_create_range (ch65, ch90); + ASSERT_DUMP_BOUNDED_RANGES_EQ (A_to_Z, "{[65, 90]}"); + const bounded_ranges *a_to_z = mgr.get_or_create_range (ch97, ch122); + ASSERT_DUMP_BOUNDED_RANGES_EQ (a_to_z, "{[97, 122]}"); + auto_vec <const bounded_ranges *> v; + v.safe_push (A_to_Z); + v.safe_push (a_to_z); + const bounded_ranges *label_ranges = mgr.get_or_create_union (v); + ASSERT_DUMP_BOUNDED_RANGES_EQ (label_ranges, "{[65, 90], [97, 122]}"); + const bounded_ranges *default_ranges + = mgr.get_or_create_inverse (label_ranges, unsigned_char_type_node); + ASSERT_DUMP_BOUNDED_RANGES_EQ (default_ranges, + "{[0, 64], [91, 96], [123, 255]}"); + } + + /* Verify ranges from ops. */ + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (EQ_EXPR, ch128), + "{128}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch128), + "{[0, 127], [129, 255]}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch128), + "{[0, 127]}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch128), + "{[0, 128]}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch128), + "{[128, 255]}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch128), + "{[129, 255]}"); + /* Ops at endpoints of type ranges. */ + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch0), + "{0}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch0), + "{}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch0), + "{[1, 255]}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch255), + "{255}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch255), + "{}"); + ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch255), + "{[0, 254]}"); + + /* Verify that instances are consolidated by mgr. */ + ASSERT_EQ (mgr.get_or_create_point (ch0), + mgr.get_or_create_point (ch0)); + ASSERT_NE (mgr.get_or_create_point (ch0), + mgr.get_or_create_point (ch1)); +} + /* Run the selftests in this file, temporarily overriding flag_analyzer_transitivity with TRANSITIVITY. */ @@ -2702,6 +4033,8 @@ run_constraint_manager_tests (bool transitivity) test_constraint_impl (); test_equality (); test_many_constants (); + test_bounded_range (); + test_bounded_ranges (); flag_analyzer_transitivity = saved_flag_analyzer_transitivity; } |