Google Git
Sign in
gnu / gcc / refs/tags/basepoints/gcc-13 / . / gcc / analyzer / constraint-manager.cc
blob: 9c8c60429f4af447d9b8a891c3762d3d2355e80c [file] [log] [blame]
/* Tracking equivalence classes and constraints at a point on an execution path.
Copyright (C) 2019-2022 Free Software Foundation, Inc.
Contributed by David Malcolm <dmalcolm@redhat.com>.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tree.h"
#include "function.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "fold-const.h"
#include "selftest.h"
#include "diagnostic-core.h"
#include "graphviz.h"
#include "function.h"
#include "json.h"
#include "analyzer/analyzer.h"
#include "ordered-hash-map.h"
#include "options.h"
#include "cgraph.h"
#include "cfg.h"
#include "digraph.h"
#include "analyzer/supergraph.h"
#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
namespace ana {
static tristate
compare_constants (tree lhs_const, enum tree_code op, tree rhs_const)
{
tree comparison
= fold_binary (op, boolean_type_node, lhs_const, rhs_const);
if (comparison == boolean_true_node)
return tristate (tristate::TS_TRUE);
if (comparison == boolean_false_node)
return tristate (tristate::TS_FALSE);
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
closed one. */
void
bound::ensure_closed (enum bound_kind bound_kind)
{
if (!m_closed)
{
/* Offset by 1 in the appropriate direction.
For example, convert 3 < x into 4 <= x,
and convert x < 5 into x <= 4. */
gcc_assert (CONSTANT_CLASS_P (m_constant));
m_constant = fold_build2 (bound_kind == BK_UPPER ? MINUS_EXPR : PLUS_EXPR,
TREE_TYPE (m_constant),
m_constant, integer_one_node);
gcc_assert (CONSTANT_CLASS_P (m_constant));
m_closed = true;
}
}
/* Get "<=" vs "<" for this bound. */
const char *
bound::get_relation_as_str () const
{
if (m_closed)
return "<=";
else
return "<";
}
/* struct range. */
/* Dump this range to PP, which must support %E for tree. */
void
range::dump_to_pp (pretty_printer *pp) const
{
if (m_lower_bound.m_constant)
{
if (m_upper_bound.m_constant)
pp_printf (pp, "%qE %s x %s %qE",
m_lower_bound.m_constant,
m_lower_bound.get_relation_as_str (),
m_upper_bound.get_relation_as_str (),
m_upper_bound.m_constant);
else
pp_printf (pp, "%qE %s x",
m_lower_bound.m_constant,
m_lower_bound.get_relation_as_str ());
}
else
{
if (m_upper_bound.m_constant)
pp_printf (pp, "x %s %qE",
m_upper_bound.get_relation_as_str (),
m_upper_bound.m_constant);
else
pp_string (pp, "x");
}
}
/* Dump this range to stderr. */
DEBUG_FUNCTION void
range::dump () 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);
pp_newline (&pp);
pp_flush (&pp);
}
/* Determine if there is only one possible value for this range.
If so, return the constant; otherwise, return NULL_TREE. */
tree
range::constrained_to_single_element ()
{
if (m_lower_bound.m_constant == NULL_TREE
|| m_upper_bound.m_constant == NULL_TREE)
return NULL_TREE;
if (!INTEGRAL_TYPE_P (TREE_TYPE (m_lower_bound.m_constant)))
return NULL_TREE;
if (!INTEGRAL_TYPE_P (TREE_TYPE (m_upper_bound.m_constant)))
return NULL_TREE;
/* Convert any open bounds to closed bounds. */
m_lower_bound.ensure_closed (BK_LOWER);
m_upper_bound.ensure_closed (BK_UPPER);
// Are they equal?
tree comparison = fold_binary (EQ_EXPR, boolean_type_node,
m_lower_bound.m_constant,
m_upper_bound.m_constant);
if (comparison == boolean_true_node)
return m_lower_bound.m_constant;
else
return NULL_TREE;
}
/* Eval the condition "X OP RHS_CONST" for X within the range. */
tristate
range::eval_condition (enum tree_code op, tree rhs_const) const
{
range copy (*this);
if (tree single_element = copy.constrained_to_single_element ())
return compare_constants (single_element, op, rhs_const);
switch (op)
{
case EQ_EXPR:
if (below_lower_bound (rhs_const))
return tristate (tristate::TS_FALSE);
if (above_upper_bound (rhs_const))
return tristate (tristate::TS_FALSE);
break;
case LT_EXPR:
case LE_EXPR:
/* Qn: "X </<= RHS_CONST". */
/* If RHS_CONST > upper bound, then it's true.
If RHS_CONST < lower bound, then it's false.
Otherwise unknown. */
if (above_upper_bound (rhs_const))
return tristate (tristate::TS_TRUE);
if (below_lower_bound (rhs_const))
return tristate (tristate::TS_FALSE);
break;
case NE_EXPR:
/* Qn: "X != RHS_CONST". */
/* If RHS_CONST < lower bound, then it's true.
If RHS_CONST > upper bound, then it's false.
Otherwise unknown. */
if (below_lower_bound (rhs_const))
return tristate (tristate::TS_TRUE);
if (above_upper_bound (rhs_const))
return tristate (tristate::TS_TRUE);
break;
case GE_EXPR:
case GT_EXPR:
/* Qn: "X >=/> RHS_CONST". */
if (above_upper_bound (rhs_const))
return tristate (tristate::TS_FALSE);
if (below_lower_bound (rhs_const))
return tristate (tristate::TS_TRUE);
break;
default:
gcc_unreachable ();
break;
}
return tristate (tristate::TS_UNKNOWN);
}
/* Return true if RHS_CONST is below the lower bound of this range. */
bool
range::below_lower_bound (tree rhs_const) const
{
if (!m_lower_bound.m_constant)
return false;
return compare_constants (rhs_const,
m_lower_bound.m_closed ? LT_EXPR : LE_EXPR,
m_lower_bound.m_constant).is_true ();
}
/* Return true if RHS_CONST is above the upper bound of this range. */
bool
range::above_upper_bound (tree rhs_const) const
{
if (!m_upper_bound.m_constant)
return false;
return compare_constants (rhs_const,
m_upper_bound.m_closed ? GT_EXPR : GE_EXPR,
m_upper_bound.m_constant).is_true ();
}
/* Attempt to add B to the bound of the given kind of this range.
Return true if feasible; false if infeasible. */
bool
range::add_bound (bound b, enum bound_kind bound_kind)
{
b.ensure_closed (bound_kind);
switch (bound_kind)
{
default:
gcc_unreachable ();
case BK_LOWER:
/* Discard redundant bounds. */
if (m_lower_bound.m_constant)
{
m_lower_bound.ensure_closed (BK_LOWER);
if (tree_int_cst_le (b.m_constant,
m_lower_bound.m_constant))
return true;
}
if (m_upper_bound.m_constant)
{
m_upper_bound.ensure_closed (BK_UPPER);
/* Reject B <= V <= UPPER when B > UPPER. */
if (!tree_int_cst_le (b.m_constant,
m_upper_bound.m_constant))
return false;
}
m_lower_bound = b;
break;
case BK_UPPER:
/* Discard redundant bounds. */
if (m_upper_bound.m_constant)
{
m_upper_bound.ensure_closed (BK_UPPER);
if (!tree_int_cst_lt (b.m_constant,
m_upper_bound.m_constant))
return true;
}
if (m_lower_bound.m_constant)
{
m_lower_bound.ensure_closed (BK_LOWER);
/* Reject LOWER <= V <= B when LOWER > B. */
if (!tree_int_cst_le (m_lower_bound.m_constant,
b.m_constant))
return false;
}
m_upper_bound = b;
break;
}
return true;
}
/* Attempt to add (RANGE OP RHS_CONST) as a bound to this range.
Return true if feasible; false if infeasible. */
bool
range::add_bound (enum tree_code op, tree rhs_const)
{
switch (op)
{
default:
return true;
case LT_EXPR:
/* "V < RHS_CONST" */
return add_bound (bound (rhs_const, false), BK_UPPER);
case LE_EXPR:
/* "V <= RHS_CONST" */
return add_bound (bound (rhs_const, true), BK_UPPER);
case GE_EXPR:
/* "V >= RHS_CONST" */
return add_bound (bound (rhs_const, true), BK_LOWER);
case GT_EXPR:
/* "V > RHS_CONST" */
return add_bound (bound (rhs_const, false), BK_LOWER);
}
}
/* 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_TYPE (m_lower) == TREE_TYPE (other.m_lower)
&& TREE_TYPE (m_upper) == TREE_TYPE (other.m_upper)
&& 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", (long)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. */
equiv_class::equiv_class ()
: m_constant (NULL_TREE), m_cst_sval (NULL), m_vars ()
{
}
/* equiv_class's copy ctor. */
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 ())
{
for (const svalue *sval : other.m_vars)
m_vars.quick_push (sval);
}
/* Print an all-on-one-line representation of this equiv_class to PP,
which must support %E for trees. */
void
equiv_class::print (pretty_printer *pp) const
{
pp_character (pp, '{');
int i;
const svalue *sval;
FOR_EACH_VEC_ELT (m_vars, i, sval)
{
if (i > 0)
pp_string (pp, " == ");
sval->dump_to_pp (pp, true);
}
if (m_constant)
{
if (i > 0)
pp_string (pp, " == ");
pp_printf (pp, "[m_constant]%qE", m_constant);
}
pp_character (pp, '}');
}
/* Return a new json::object of the form
{"svals" : [str],
"constant" : optional str}. */
json::object *
equiv_class::to_json () const
{
json::object *ec_obj = new json::object ();
json::array *sval_arr = new json::array ();
for (const svalue *sval : m_vars)
sval_arr->append (sval->to_json ());
ec_obj->set ("svals", sval_arr);
if (m_constant)
{
pretty_printer pp;
pp_format_decoder (&pp) = default_tree_printer;
pp_printf (&pp, "%qE", m_constant);
ec_obj->set ("constant", new json::string (pp_formatted_text (&pp)));
}
return ec_obj;
}
/* Generate a hash value for this equiv_class.
This relies on the ordering of m_vars, and so this object needs to
have been canonicalized for this to be meaningful. */
hashval_t
equiv_class::hash () const
{
inchash::hash hstate;
inchash::add_expr (m_constant, hstate);
for (const svalue * sval : m_vars)
hstate.add_ptr (sval);
return hstate.end ();
}
/* Equality operator for equiv_class.
This relies on the ordering of m_vars, and so this object
and OTHER need to have been canonicalized for this to be
meaningful. */
bool
equiv_class::operator== (const equiv_class &other)
{
if (m_constant != other.m_constant)
return false; // TODO: use tree equality here?
/* FIXME: should we compare m_cst_sval? */
if (m_vars.length () != other.m_vars.length ())
return false;
int i;
const svalue *sval;
FOR_EACH_VEC_ELT (m_vars, i, sval)
if (sval != other.m_vars[i])
return false;
return true;
}
/* Add SID to this equiv_class, using CM to check if it's a constant. */
void
equiv_class::add (const svalue *sval)
{
gcc_assert (sval);
if (tree cst = sval->maybe_get_constant ())
{
gcc_assert (CONSTANT_CLASS_P (cst));
/* FIXME: should we canonicalize which svalue is the constant
when there are multiple equal constants? */
m_constant = cst;
m_cst_sval = sval;
}
m_vars.safe_push (sval);
}
/* Remove SID from this equivalence class.
Return true if SID was the last var in the equivalence class (suggesting
a possible leak). */
bool
equiv_class::del (const svalue *sval)
{
gcc_assert (sval);
gcc_assert (sval != m_cst_sval);
int i;
const svalue *iv;
FOR_EACH_VEC_ELT (m_vars, i, iv)
{
if (iv == sval)
{
m_vars[i] = m_vars[m_vars.length () - 1];
m_vars.pop ();
return m_vars.length () == 0;
}
}
/* SVAL must be in the class. */
gcc_unreachable ();
return false;
}
/* Get a representative member of this class, for handling cases
where the IDs can change mid-traversal. */
const svalue *
equiv_class::get_representative () const
{
gcc_assert (m_vars.length () > 0);
return m_vars[0];
}
/* Sort the svalues within this equiv_class. */
void
equiv_class::canonicalize ()
{
m_vars.qsort (svalue::cmp_ptr_ptr);
}
/* Return true if this EC contains a variable, false if it merely
contains constants.
Subroutine of constraint_manager::canonicalize, for removing
redundant ECs. */
bool
equiv_class::contains_non_constant_p () const
{
if (m_constant)
{
for (auto iter : m_vars)
if (iter->maybe_get_constant ())
continue;
else
/* We have {non-constant == constant}. */
return true;
/* We only have constants. */
return false;
}
else
/* Return true if we have {non-constant == non-constant}. */
return m_vars.length () > 1;
}
/* Get a debug string for C_OP. */
const char *
constraint_op_code (enum constraint_op c_op)
{
switch (c_op)
{
default:
gcc_unreachable ();
case CONSTRAINT_NE: return "!=";
case CONSTRAINT_LT: return "<";
case CONSTRAINT_LE: return "<=";
}
}
/* Convert C_OP to an enum tree_code. */
enum tree_code
constraint_tree_code (enum constraint_op c_op)
{
switch (c_op)
{
default:
gcc_unreachable ();
case CONSTRAINT_NE: return NE_EXPR;
case CONSTRAINT_LT: return LT_EXPR;
case CONSTRAINT_LE: return LE_EXPR;
}
}
/* Given "lhs C_OP rhs", determine "lhs T_OP rhs".
For example, given "x < y", then "x > y" is false. */
static tristate
eval_constraint_op_for_op (enum constraint_op c_op, enum tree_code t_op)
{
switch (c_op)
{
default:
gcc_unreachable ();
case CONSTRAINT_NE:
if (t_op == EQ_EXPR)
return tristate (tristate::TS_FALSE);
if (t_op == NE_EXPR)
return tristate (tristate::TS_TRUE);
break;
case CONSTRAINT_LT:
if (t_op == LT_EXPR || t_op == LE_EXPR || t_op == NE_EXPR)
return tristate (tristate::TS_TRUE);
if (t_op == EQ_EXPR || t_op == GT_EXPR || t_op == GE_EXPR)
return tristate (tristate::TS_FALSE);
break;
case CONSTRAINT_LE:
if (t_op == LE_EXPR)
return tristate (tristate::TS_TRUE);
if (t_op == GT_EXPR)
return tristate (tristate::TS_FALSE);
break;
}
return tristate (tristate::TS_UNKNOWN);
}
/* class constraint. */
/* Print this constraint to PP (which must support %E for trees),
using CM to look up equiv_class instances from ids. */
void
constraint::print (pretty_printer *pp, const constraint_manager &cm) const
{
m_lhs.print (pp);
pp_string (pp, ": ");
m_lhs.get_obj (cm).print (pp);
pp_string (pp, " ");
pp_string (pp, constraint_op_code (m_op));
pp_string (pp, " ");
m_rhs.print (pp);
pp_string (pp, ": ");
m_rhs.get_obj (cm).print (pp);
}
/* Return a new json::object of the form
{"lhs" : int, the EC index
"op" : str,
"rhs" : int, the EC index}. */
json::object *
constraint::to_json () const
{
json::object *con_obj = new json::object ();
con_obj->set ("lhs", new json::integer_number (m_lhs.as_int ()));
con_obj->set ("op", new json::string (constraint_op_code (m_op)));
con_obj->set ("rhs", new json::integer_number (m_rhs.as_int ()));
return con_obj;
}
/* Generate a hash value for this constraint. */
hashval_t
constraint::hash () const
{
inchash::hash hstate;
hstate.add_int (m_lhs.m_idx);
hstate.add_int (m_op);
hstate.add_int (m_rhs.m_idx);
return hstate.end ();
}
/* Equality operator for constraints. */
bool
constraint::operator== (const constraint &other) const
{
if (m_lhs != other.m_lhs)
return false;
if (m_op != other.m_op)
return false;
if (m_rhs != other.m_rhs)
return false;
return true;
}
/* Return true if this constraint is implied by OTHER. */
bool
constraint::implied_by (const constraint &other,
const constraint_manager &cm) const
{
if (m_lhs == other.m_lhs)
if (tree rhs_const = m_rhs.get_obj (cm).get_any_constant ())
if (tree other_rhs_const = other.m_rhs.get_obj (cm).get_any_constant ())
if (m_lhs.get_obj (cm).get_any_constant () == NULL_TREE)
if (m_op == other.m_op)
switch (m_op)
{
default:
break;
case CONSTRAINT_LE:
case CONSTRAINT_LT:
if (compare_constants (rhs_const,
GE_EXPR,
other_rhs_const).is_true ())
return true;
break;
}
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. */
const equiv_class &
equiv_class_id::get_obj (const constraint_manager &cm) const
{
return cm.get_equiv_class_by_index (m_idx);
}
/* Access the underlying equiv_class for this ID from CM. */
equiv_class &
equiv_class_id::get_obj (constraint_manager &cm) const
{
return cm.get_equiv_class_by_index (m_idx);
}
/* Print this equiv_class_id to PP. */
void
equiv_class_id::print (pretty_printer *pp) const
{
if (null_p ())
pp_printf (pp, "null");
else
pp_printf (pp, "ec%i", m_idx);
}
/* class constraint_manager. */
/* constraint_manager's copy ctor. */
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;
equiv_class *ec;
FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
m_equiv_classes.quick_push (new equiv_class (*ec));
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. */
constraint_manager&
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;
m_equiv_classes.reserve (other.m_equiv_classes.length ());
FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
m_equiv_classes.quick_push (new equiv_class (*ec));
constraint *c;
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;
}
/* Generate a hash value for this constraint_manager. */
hashval_t
constraint_manager::hash () const
{
inchash::hash hstate;
int i;
equiv_class *ec;
constraint *c;
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
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 ();
}
/* Equality operator for constraint_manager. */
bool
constraint_manager::operator== (const constraint_manager &other) const
{
if (m_equiv_classes.length () != other.m_equiv_classes.length ())
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;
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
if (!(*ec == *other.m_equiv_classes[i]))
return false;
constraint *c;
FOR_EACH_VEC_ELT (m_constraints, i, c)
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;
}
/* Print this constraint_manager to PP (which must support %E for trees). */
void
constraint_manager::print (pretty_printer *pp) const
{
pp_string (pp, "{");
int i;
equiv_class *ec;
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
{
if (i > 0)
pp_string (pp, ", ");
equiv_class_id (i).print (pp);
pp_string (pp, ": ");
ec->print (pp);
}
pp_string (pp, " | ");
constraint *c;
FOR_EACH_VEC_ELT (m_constraints, i, c)
{
if (i > 0)
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, "}");
}
/* Dump a representation of this constraint_manager to PP
(which must support %E for trees). */
void
constraint_manager::dump_to_pp (pretty_printer *pp, bool multiline) const
{
if (multiline)
pp_string (pp, " ");
pp_string (pp, "equiv classes:");
if (multiline)
pp_newline (pp);
else
pp_string (pp, " {");
int i;
equiv_class *ec;
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
{
if (multiline)
pp_string (pp, " ");
else if (i > 0)
pp_string (pp, ", ");
equiv_class_id (i).print (pp);
pp_string (pp, ": ");
ec->print (pp);
if (multiline)
pp_newline (pp);
}
if (multiline)
pp_string (pp, " ");
else
pp_string (pp, "}");
pp_string (pp, "constraints:");
if (multiline)
pp_newline (pp);
else
pp_string (pp, "{");
constraint *c;
FOR_EACH_VEC_ELT (m_constraints, i, c)
{
if (multiline)
pp_string (pp, " ");
pp_printf (pp, "%i: ", i);
c->print (pp, *this);
if (multiline)
pp_newline (pp);
}
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. */
void
constraint_manager::dump (FILE *fp) const
{
pretty_printer pp;
pp_format_decoder (&pp) = default_tree_printer;
pp_show_color (&pp) = pp_show_color (global_dc->printer);
pp.buffer->stream = fp;
dump_to_pp (&pp, true);
pp_flush (&pp);
}
/* Dump a multiline representation of this constraint_manager to stderr. */
DEBUG_FUNCTION void
constraint_manager::dump () const
{
dump (stderr);
}
/* Dump a multiline representation of CM to stderr. */
DEBUG_FUNCTION void
debug (const constraint_manager &cm)
{
cm.dump ();
}
/* Return a new json::object of the form
{"ecs" : array of objects, one per equiv_class
"constraints" : array of objects, one per constraint}. */
json::object *
constraint_manager::to_json () const
{
json::object *cm_obj = new json::object ();
/* Equivalence classes. */
{
json::array *ec_arr = new json::array ();
for (const equiv_class *ec : m_equiv_classes)
ec_arr->append (ec->to_json ());
cm_obj->set ("ecs", ec_arr);
}
/* Constraints. */
{
json::array *con_arr = new json::array ();
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;
}
/* Attempt to add the constraint LHS OP RHS to this constraint_manager.
Return true if the constraint could be added (or is already true).
Return false if the constraint contradicts existing knowledge. */
bool
constraint_manager::add_constraint (const svalue *lhs,
enum tree_code op,
const svalue *rhs)
{
lhs = lhs->unwrap_any_unmergeable ();
rhs = rhs->unwrap_any_unmergeable ();
/* 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;
/* Check the conditions on svalues. */
{
tristate t_cond = eval_condition (lhs, op, rhs);
/* If we already have the condition, do nothing. */
if (t_cond.is_true ())
return true;
/* Reject a constraint that would contradict existing knowledge, as
unsatisfiable. */
if (t_cond.is_false ())
return false;
}
equiv_class_id lhs_ec_id = get_or_add_equiv_class (lhs);
equiv_class_id rhs_ec_id = get_or_add_equiv_class (rhs);
/* Check the stronger conditions on ECs. */
{
tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
/* Discard constraints that are already known. */
if (t.is_true ())
return true;
/* Reject unsatisfiable constraints. */
if (t.is_false ())
return false;
}
/* If adding
(SVAL + OFFSET) > CST,
then that can imply:
SVAL > (CST - OFFSET). */
if (const binop_svalue *lhs_binop = lhs->dyn_cast_binop_svalue ())
if (tree rhs_cst = rhs->maybe_get_constant ())
if (tree offset = lhs_binop->get_arg1 ()->maybe_get_constant ())
if ((op == GT_EXPR || op == LT_EXPR
|| op == GE_EXPR || op == LE_EXPR)
&& lhs_binop->get_op () == PLUS_EXPR)
{
tree offset_of_cst = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs_cst),
rhs_cst, offset);
const svalue *implied_lhs = lhs_binop->get_arg0 ();
enum tree_code implied_op = op;
const svalue *implied_rhs
= m_mgr->get_or_create_constant_svalue (offset_of_cst);
if (!add_constraint (implied_lhs, implied_op, implied_rhs))
return false;
/* The above add_constraint could lead to EC merger, so we need
to refresh the EC IDs. */
lhs_ec_id = get_or_add_equiv_class (lhs);
rhs_ec_id = get_or_add_equiv_class (rhs);
}
add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
return true;
}
/* Attempt to add the constraint LHS_EC_ID OP RHS_EC_ID to this
constraint_manager.
Return true if the constraint could be added (or is already true).
Return false if the constraint contradicts existing knowledge. */
bool
constraint_manager::add_constraint (equiv_class_id lhs_ec_id,
enum tree_code op,
equiv_class_id rhs_ec_id)
{
tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
/* Discard constraints that are already known. */
if (t.is_true ())
return true;
/* Reject unsatisfiable constraints. */
if (t.is_false ())
return false;
add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
return true;
}
/* Add the constraint LHS_EC_ID OP RHS_EC_ID to this constraint_manager,
where the constraint has already been checked for being "unknown". */
void
constraint_manager::add_unknown_constraint (equiv_class_id lhs_ec_id,
enum tree_code op,
equiv_class_id rhs_ec_id)
{
gcc_assert (lhs_ec_id != rhs_ec_id);
/* For now, simply accumulate constraints, without attempting any further
optimization. */
switch (op)
{
case EQ_EXPR:
{
/* Merge rhs_ec into lhs_ec. */
equiv_class &lhs_ec_obj = lhs_ec_id.get_obj (*this);
const equiv_class &rhs_ec_obj = rhs_ec_id.get_obj (*this);
int i;
const svalue *sval;
FOR_EACH_VEC_ELT (rhs_ec_obj.m_vars, i, sval)
lhs_ec_obj.add (sval);
if (rhs_ec_obj.m_constant)
{
lhs_ec_obj.m_constant = rhs_ec_obj.m_constant;
lhs_ec_obj.m_cst_sval = rhs_ec_obj.m_cst_sval;
}
/* Drop rhs equivalence class, overwriting it with the
final ec (which might be the same one). */
equiv_class_id final_ec_id = m_equiv_classes.length () - 1;
equiv_class *old_ec = m_equiv_classes[rhs_ec_id.m_idx];
equiv_class *final_ec = m_equiv_classes.pop ();
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;
FOR_EACH_VEC_ELT (m_constraints, i, c)
{
/* Update references to the rhs_ec so that
they refer to the lhs_ec. */
if (c->m_lhs == rhs_ec_id)
c->m_lhs = lhs_ec_id;
if (c->m_rhs == rhs_ec_id)
c->m_rhs = lhs_ec_id;
/* Renumber all constraints that refer to the final rhs_ec
to the old rhs_ec, where the old final_ec now lives. */
if (c->m_lhs == final_ec_id)
c->m_lhs = rhs_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. */
unsigned read_index, write_index;
VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
(c->m_lhs == c->m_rhs));
}
break;
case GE_EXPR:
add_constraint_internal (rhs_ec_id, CONSTRAINT_LE, lhs_ec_id);
break;
case LE_EXPR:
add_constraint_internal (lhs_ec_id, CONSTRAINT_LE, rhs_ec_id);
break;
case NE_EXPR:
add_constraint_internal (lhs_ec_id, CONSTRAINT_NE, rhs_ec_id);
break;
case GT_EXPR:
add_constraint_internal (rhs_ec_id, CONSTRAINT_LT, lhs_ec_id);
break;
case LT_EXPR:
add_constraint_internal (lhs_ec_id, CONSTRAINT_LT, rhs_ec_id);
break;
default:
/* do nothing. */
break;
}
validate ();
}
/* Subroutine of constraint_manager::add_constraint, for handling all
operations other than equality (for which equiv classes are merged). */
void
constraint_manager::add_constraint_internal (equiv_class_id lhs_id,
enum constraint_op c_op,
equiv_class_id rhs_id)
{
if (m_constraints.length () >= (unsigned)param_analyzer_max_constraints)
return;
constraint new_c (lhs_id, c_op, rhs_id);
/* Remove existing constraints that would be implied by the
new constraint. */
unsigned read_index, write_index;
constraint *c;
VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
(c->implied_by (new_c, *this)));
/* 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;
if (c_op != CONSTRAINT_NE)
{
/* The following can potentially add EQ_EXPR facts, which could lead
to ECs being merged, which would change the meaning of the EC IDs.
Hence we need to do this via representatives. */
const svalue *lhs = lhs_id.get_obj (*this).get_representative ();
const svalue *rhs = rhs_id.get_obj (*this).get_representative ();
/* We have LHS </<= RHS */
/* Handle transitivity of ordering by adding additional constraints
based on what we already knew.
So if we have already have:
(a < b)
(c < d)
Then adding:
(b < c)
will also add:
(a < c)
(b < d)
We need to recurse to ensure we also add:
(a < d).
We call the checked add_constraint to avoid adding constraints
that are already present. Doing so also ensures termination
in the case of cycles.
We also check for single-element ranges, adding EQ_EXPR facts
where we discover them. For example 3 < x < 5 implies
that x == 4 (if x is an integer). */
for (unsigned i = 0; i < m_constraints.length (); i++)
{
const constraint *other = &m_constraints[i];
if (other->is_ordering_p ())
{
/* Refresh the EC IDs, in case any mergers have happened. */
lhs_id = get_or_add_equiv_class (lhs);
rhs_id = get_or_add_equiv_class (rhs);
tree lhs_const = lhs_id.get_obj (*this).m_constant;
tree rhs_const = rhs_id.get_obj (*this).m_constant;
tree other_lhs_const
= other->m_lhs.get_obj (*this).m_constant;
tree other_rhs_const
= other->m_rhs.get_obj (*this).m_constant;
/* We have "LHS </<= RHS" and "other.lhs </<= other.rhs". */
/* If we have LHS </<= RHS and RHS </<= LHS, then we have a
cycle. */
if (rhs_id == other->m_lhs
&& other->m_rhs == lhs_id)
{
/* We must have equality for this to be possible. */
gcc_assert (c_op == CONSTRAINT_LE
&& other->m_op == CONSTRAINT_LE);
add_constraint (lhs_id, EQ_EXPR, rhs_id);
/* Adding an equality will merge the two ECs and potentially
reorganize the constraints. Stop iterating. */
return;
}
/* Otherwise, check for transitivity. */
if (rhs_id == other->m_lhs)
{
/* With RHS == other.lhs, we have:
"LHS </<= (RHS, other.lhs) </<= other.rhs"
and thus this implies "LHS </<= other.rhs". */
/* Do we have a tightly-constrained range? */
if (lhs_const
&& !rhs_const
&& other_rhs_const)
{
range r (bound (lhs_const, c_op == CONSTRAINT_LE),
bound (other_rhs_const,
other->m_op == CONSTRAINT_LE));
if (tree constant = r.constrained_to_single_element ())
{
const svalue *cst_sval
= m_mgr->get_or_create_constant_svalue (constant);
add_constraint
(rhs_id, EQ_EXPR,
get_or_add_equiv_class (cst_sval));
return;
}
}
/* Otherwise, add the constraint implied by transitivity. */
enum tree_code new_op
= ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
? LE_EXPR : LT_EXPR);
add_constraint (lhs_id, new_op, other->m_rhs);
}
else if (other->m_rhs == lhs_id)
{
/* With other.rhs == LHS, we have:
"other.lhs </<= (other.rhs, LHS) </<= RHS"
and thus this implies "other.lhs </<= RHS". */
/* Do we have a tightly-constrained range? */
if (other_lhs_const
&& !lhs_const
&& rhs_const)
{
range r (bound (other_lhs_const,
other->m_op == CONSTRAINT_LE),
bound (rhs_const,
c_op == CONSTRAINT_LE));
if (tree constant = r.constrained_to_single_element ())
{
const svalue *cst_sval
= m_mgr->get_or_create_constant_svalue (constant);
add_constraint
(lhs_id, EQ_EXPR,
get_or_add_equiv_class (cst_sval));
return;
}
}
/* Otherwise, add the constraint implied by transitivity. */
enum tree_code new_op
= ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
? LE_EXPR : LT_EXPR);
add_constraint (other->m_lhs, new_op, rhs_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. */
bool
constraint_manager::get_equiv_class_by_svalue (const svalue *sval,
equiv_class_id *out) const
{
/* TODO: should we have a map, rather than these searches? */
int i;
equiv_class *ec;
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
{
int j;
const svalue *iv;
FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
if (iv == sval)
{
if (out)
*out = equiv_class_id (i);
return true;
}
}
return false;
}
/* Ensure that SVAL has an equivalence class within this constraint_manager;
return the ID of the class. */
equiv_class_id
constraint_manager::get_or_add_equiv_class (const svalue *sval)
{
equiv_class_id result (-1);
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 (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))
return result;
/* Try equality of constants. */
if (tree cst = sval->maybe_get_constant ())
{
int i;
equiv_class *ec;
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
if (ec->m_constant
&& types_compatible_p (TREE_TYPE (cst),
TREE_TYPE (ec->m_constant)))
{
tree eq = fold_binary (EQ_EXPR, boolean_type_node,
cst, ec->m_constant);
if (eq == boolean_true_node)
{
ec->add (sval);
return equiv_class_id (i);
}
}
}
/* Not found. */
equiv_class *new_ec = new equiv_class ();
new_ec->add (sval);
m_equiv_classes.safe_push (new_ec);
equiv_class_id new_id (m_equiv_classes.length () - 1);
return new_id;
}
/* Evaluate the condition LHS_EC OP RHS_EC. */
tristate
constraint_manager::eval_condition (equiv_class_id lhs_ec,
enum tree_code op,
equiv_class_id rhs_ec) const
{
if (lhs_ec == rhs_ec)
{
switch (op)
{
case EQ_EXPR:
case GE_EXPR:
case LE_EXPR:
return tristate (tristate::TS_TRUE);
case NE_EXPR:
case GT_EXPR:
case LT_EXPR:
return tristate (tristate::TS_FALSE);
default:
break;
}
}
tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ();
tree rhs_const = rhs_ec.get_obj (*this).get_any_constant ();
if (lhs_const && rhs_const)
{
tristate result_for_constants
= compare_constants (lhs_const, op, rhs_const);
if (result_for_constants.is_known ())
return result_for_constants;
}
enum tree_code swapped_op = swap_tree_comparison (op);
int i;
constraint *c;
FOR_EACH_VEC_ELT (m_constraints, i, c)
{
if (c->m_lhs == lhs_ec
&& c->m_rhs == rhs_ec)
{
tristate result_for_constraint
= eval_constraint_op_for_op (c->m_op, op);
if (result_for_constraint.is_known ())
return result_for_constraint;
}
/* Swapped operands. */
if (c->m_lhs == rhs_ec
&& c->m_rhs == lhs_ec)
{
tristate result_for_constraint
= eval_constraint_op_for_op (c->m_op, swapped_op);
if (result_for_constraint.is_known ())
return result_for_constraint;
}
}
/* We don't use m_bounded_ranges_constraints here yet. */
return tristate (tristate::TS_UNKNOWN);
}
range
constraint_manager::get_ec_bounds (equiv_class_id ec_id) const
{
range result;
int i;
constraint *c;
FOR_EACH_VEC_ELT (m_constraints, i, c)
{
if (c->m_lhs == ec_id)
{
if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
switch (c->m_op)
{
default:
gcc_unreachable ();
case CONSTRAINT_NE:
continue;
case CONSTRAINT_LT:
/* We have "EC_ID < OTHER_CST". */
result.add_bound (bound (other_cst, false), BK_UPPER);
break;
case CONSTRAINT_LE:
/* We have "EC_ID <= OTHER_CST". */
result.add_bound (bound (other_cst, true), BK_UPPER);
break;
}
}
if (c->m_rhs == ec_id)
{
if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
switch (c->m_op)
{
default:
gcc_unreachable ();
case CONSTRAINT_NE:
continue;
case CONSTRAINT_LT:
/* We have "OTHER_CST < EC_ID"
i.e. "EC_ID > OTHER_CST". */
result.add_bound (bound (other_cst, false), BK_LOWER);
break;
case CONSTRAINT_LE:
/* We have "OTHER_CST <= EC_ID"
i.e. "EC_ID >= OTHER_CST". */
result.add_bound (bound (other_cst, true), BK_LOWER);
break;
}
}
}
return result;
}
/* Evaluate the condition LHS_EC OP RHS_CONST, avoiding the creation
of equiv_class instances. */
tristate
constraint_manager::eval_condition (equiv_class_id lhs_ec,
enum tree_code op,
tree rhs_const) const
{
gcc_assert (!lhs_ec.null_p ());
gcc_assert (CONSTANT_CLASS_P (rhs_const));
if (tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ())
return compare_constants (lhs_const, op, rhs_const);
/* Check for known inequalities of the form
(LHS_EC != OTHER_CST) or (OTHER_CST != LHS_EC).
If RHS_CONST == OTHER_CST, then we also know that LHS_EC != OTHER_CST.
For example, we might have the constraint
ptr != (void *)0
so we want the condition
ptr == (foo *)0
to be false. */
int i;
constraint *c;
FOR_EACH_VEC_ELT (m_constraints, i, c)
{
if (c->m_op == CONSTRAINT_NE)
{
if (c->m_lhs == lhs_ec)
{
if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
if (compare_constants
(rhs_const, EQ_EXPR, other_cst).is_true ())
{
switch (op)
{
case EQ_EXPR:
return tristate (tristate::TS_FALSE);
case NE_EXPR:
return tristate (tristate::TS_TRUE);
default:
break;
}
}
}
if (c->m_rhs == lhs_ec)
{
if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
if (compare_constants
(rhs_const, EQ_EXPR, other_cst).is_true ())
{
switch (op)
{
case EQ_EXPR:
return tristate (tristate::TS_FALSE);
case NE_EXPR:
return tristate (tristate::TS_TRUE);
default:
break;
}
}
}
}
}
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);
tristate result = lhs_bounds.eval_condition (op, rhs_const);
if (result.is_known ())
return result;
/* Also reject if range::add_bound fails. */
if (!lhs_bounds.add_bound (op, rhs_const))
return tristate (false);
return tristate::unknown ();
}
/* Evaluate the condition LHS OP RHS, without modifying this
constraint_manager (avoiding the creation of equiv_class instances). */
tristate
constraint_manager::eval_condition (const svalue *lhs,
enum tree_code op,
const svalue *rhs) const
{
lhs = lhs->unwrap_any_unmergeable ();
rhs = rhs->unwrap_any_unmergeable ();
/* Nothing can be known about unknown or poisoned values. */
if (lhs->get_kind () == SK_UNKNOWN
|| lhs->get_kind () == SK_POISONED
|| rhs->get_kind () == SK_UNKNOWN
|| rhs->get_kind () == SK_POISONED)
return tristate (tristate::TS_UNKNOWN);
if (lhs == rhs
&& !(FLOAT_TYPE_P (lhs->get_type ())
|| FLOAT_TYPE_P (rhs->get_type ())))
{
switch (op)
{
case EQ_EXPR:
case GE_EXPR:
case LE_EXPR:
return tristate (tristate::TS_TRUE);
case NE_EXPR:
case GT_EXPR:
case LT_EXPR:
return tristate (tristate::TS_FALSE);
default:
break;
}
}
equiv_class_id lhs_ec (-1);
equiv_class_id rhs_ec (-1);
get_equiv_class_by_svalue (lhs, &lhs_ec);
get_equiv_class_by_svalue (rhs, &rhs_ec);
if (!lhs_ec.null_p () && !rhs_ec.null_p ())
{
tristate result_for_ecs
= eval_condition (lhs_ec, op, rhs_ec);
if (result_for_ecs.is_known ())
return result_for_ecs;
}
/* If at least one is not in an EC, we have no constraints
comparing LHS and RHS yet.
They might still be comparable if one (or both) is a constant.
Alternatively, we can also get here if we had ECs but they weren't
comparable. Again, constant comparisons might give an answer. */
tree lhs_const = lhs->maybe_get_constant ();
tree rhs_const = rhs->maybe_get_constant ();
if (lhs_const && rhs_const)
{
tristate result_for_constants
= compare_constants (lhs_const, op, rhs_const);
if (result_for_constants.is_known ())
return result_for_constants;
}
if (!lhs_ec.null_p ())
{
if (rhs_const)
return eval_condition (lhs_ec, op, rhs_const);
}
if (!rhs_ec.null_p ())
{
if (lhs_const)
{
enum tree_code swapped_op = swap_tree_comparison (op);
return eval_condition (rhs_ec, swapped_op, lhs_const);
}
}
return tristate (tristate::TS_UNKNOWN);
}
/* Delete any information about svalues identified by P.
Such instances are removed from equivalence classes, and any
redundant ECs and constraints are also removed.
Accumulate stats into STATS. */
template <typename PurgeCriteria>
void
constraint_manager::purge (const PurgeCriteria &p, purge_stats *stats)
{
/* Delete any svalues identified by P within the various equivalence
classes. */
for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
{
equiv_class *ec = m_equiv_classes[ec_idx];
int i;
const svalue *sval;
bool delete_ec = false;
FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
{
if (sval == ec->m_cst_sval)
continue;
if (p.should_purge_p (sval))
{
if (ec->del (sval))
if (!ec->m_constant)
delete_ec = true;
}
}
if (delete_ec)
{
delete ec;
m_equiv_classes.ordered_remove (ec_idx);
if (stats)
stats->m_num_equiv_classes++;
/* Update the constraints, potentially removing some. */
for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
{
constraint *c = &m_constraints[con_idx];
/* Remove constraints that refer to the deleted EC. */
if (c->m_lhs == ec_idx
|| c->m_rhs == ec_idx)
{
m_constraints.ordered_remove (con_idx);
if (stats)
stats->m_num_constraints++;
}
else
{
/* Renumber constraints that refer to ECs that have
had their idx changed. */
c->m_lhs.update_for_removal (ec_idx);
c->m_rhs.update_for_removal (ec_idx);
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++;
}
/* Now delete any constraints that are purely between constants. */
for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
{
constraint *c = &m_constraints[con_idx];
if (m_equiv_classes[c->m_lhs.m_idx]->m_vars.length () == 0
&& m_equiv_classes[c->m_rhs.m_idx]->m_vars.length () == 0)
{
m_constraints.ordered_remove (con_idx);
if (stats)
stats->m_num_constraints++;
}
else
{
con_idx++;
}
}
/* Finally, delete any ECs that purely contain constants and aren't
referenced by any constraints. */
for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
{
equiv_class *ec = m_equiv_classes[ec_idx];
if (ec->m_vars.length () == 0)
{
equiv_class_id ec_id (ec_idx);
bool has_constraint = false;
for (unsigned con_idx = 0; con_idx < m_constraints.length ();
con_idx++)
{
constraint *c = &m_constraints[con_idx];
if (c->m_lhs == ec_id
|| c->m_rhs == ec_id)
{
has_constraint = true;
break;
}
}
if (!has_constraint)
{
delete ec;
m_equiv_classes.ordered_remove (ec_idx);
if (stats)
stats->m_num_equiv_classes++;
/* Renumber constraints that refer to ECs that have
had their idx changed. */
for (unsigned con_idx = 0; con_idx < m_constraints.length ();
con_idx++)
{
constraint *c = &m_constraints[con_idx];
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;
}
}
ec_idx++;
}
validate ();
}
/* Implementation of PurgeCriteria: purge svalues that are not live
with respect to LIVE_SVALUES and MODEL. */
class dead_svalue_purger
{
public:
dead_svalue_purger (const svalue_set &live_svalues,
const region_model *model)
: m_live_svalues (live_svalues), m_model (model)
{
}
bool should_purge_p (const svalue *sval) const
{
return !sval->live_p (&m_live_svalues, m_model);
}
private:
const svalue_set &m_live_svalues;
const region_model *m_model;
};
/* Purge dead svalues from equivalence classes and update constraints
accordingly. */
void
constraint_manager::
on_liveness_change (const svalue_set &live_svalues,
const region_model *model)
{
dead_svalue_purger p (live_svalues, model);
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. */
static int
equiv_class_cmp (const void *p1, const void *p2)
{
const equiv_class *ec1 = *(const equiv_class * const *)p1;
const equiv_class *ec2 = *(const equiv_class * const *)p2;
const svalue *rep1 = ec1->get_representative ();
const svalue *rep2 = ec2->get_representative ();
gcc_assert (rep1);
gcc_assert (rep2);
return svalue::cmp_ptr (rep1, rep2);
}
/* Comparator for use by constraint_manager::canonicalize.
Sort a pair of constraint instances. */
static int
constraint_cmp (const void *p1, const void *p2)
{
const constraint *c1 = (const constraint *)p1;
const constraint *c2 = (const constraint *)p2;
int lhs_cmp = c1->m_lhs.as_int () - c2->m_lhs.as_int ();
if (lhs_cmp)
return lhs_cmp;
int rhs_cmp = c1->m_rhs.as_int () - c2->m_rhs.as_int ();
if (rhs_cmp)
return rhs_cmp;
return c1->m_op - c2->m_op;
}
/* Purge redundant equivalence classes and constraints, and reorder them
within this constraint_manager into a canonical order, to increase the
chances of finding equality with another instance. */
void
constraint_manager::canonicalize ()
{
/* First, sort svalues within the ECs. */
unsigned i;
equiv_class *ec;
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
ec->canonicalize ();
/* TODO: remove constraints where both sides have a constant, and are
thus implicit. But does this break transitivity? */
/* We will be purging and reordering ECs.
We will need to remap the equiv_class_ids in the constraints,
so we need to store the original index of each EC.
Build a lookup table, mapping from the representative svalue
to the original equiv_class_id of that svalue. */
hash_map<const svalue *, equiv_class_id> original_ec_id;
const unsigned orig_num_equiv_classes = m_equiv_classes.length ();
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
{
const svalue *rep = ec->get_representative ();
gcc_assert (rep);
original_ec_id.put (rep, i);
}
/* Find ECs used by constraints. */
hash_set<const equiv_class *> used_ecs;
constraint *c;
FOR_EACH_VEC_ELT (m_constraints, i, c)
{
used_ecs.add (m_equiv_classes[c->m_lhs.as_int ()]);
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). */
{
/* "unordered remove if" from a vec. */
unsigned i = 0;
while (i < m_equiv_classes.length ())
{
equiv_class *ec = m_equiv_classes[i];
if (!used_ecs.contains (ec)
&& !ec->contains_non_constant_p ())
{
m_equiv_classes.unordered_remove (i);
delete ec;
}
else
i++;
}
}
/* Next, sort the surviving ECs into a canonical order. */
m_equiv_classes.qsort (equiv_class_cmp);
/* Populate ec_id_map based on the old vs new EC ids. */
one_way_id_map<equiv_class_id> ec_id_map (orig_num_equiv_classes);
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
{
const svalue *rep = ec->get_representative ();
gcc_assert (rep);
ec_id_map.put (*original_ec_id.get (rep), i);
}
/* Use ec_id_map to update the EC ids within the constraints. */
FOR_EACH_VEC_ELT (m_constraints, i, c)
{
ec_id_map.update (&c->m_lhs);
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);
}
/* Concrete subclass of fact_visitor for use by constraint_manager::merge.
For every fact in CM_A, see if it is also true in *CM_B. Add such
facts to *OUT. */
class merger_fact_visitor : public fact_visitor
{
public:
merger_fact_visitor (const constraint_manager *cm_b,
constraint_manager *out)
: m_cm_b (cm_b), m_out (out)
{}
void on_fact (const svalue *lhs, enum tree_code code, const svalue *rhs)
FINAL OVERRIDE
{
/* Special-case for widening. */
if (lhs->get_kind () == SK_WIDENING)
if (!m_cm_b->get_equiv_class_by_svalue (lhs, NULL))
{
/* LHS isn't constrained within m_cm_b. */
bool sat = m_out->add_constraint (lhs, code, rhs);
gcc_assert (sat);
return;
}
if (m_cm_b->eval_condition (lhs, code, rhs).is_true ())
{
bool sat = m_out->add_constraint (lhs, code, rhs);
if (!sat)
{
/* If -fanalyzer-transitivity is off, we can encounter cases
where at least one of the two constraint_managers being merged
is infeasible, but we only discover that infeasibility
during merging (PR analyzer/96650).
Silently drop such constraints. */
gcc_assert (!flag_analyzer_transitivity);
}
}
}
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;
};
/* Use MERGER to merge CM_A and CM_B into *OUT.
If one thinks of a constraint_manager as a subset of N-dimensional
space, this takes the union of the points of CM_A and CM_B, and
expresses that into *OUT. Alternatively, it can be thought of
as the intersection of the constraints. */
void
constraint_manager::merge (const constraint_manager &cm_a,
const constraint_manager &cm_b,
constraint_manager *out)
{
/* Merge the equivalence classes and constraints.
The easiest way to do this seems to be to enumerate all of the facts
in cm_a, see which are also true in cm_b,
and add those to *OUT. */
merger_fact_visitor v (&cm_b, out);
cm_a.for_each_fact (&v);
}
/* Call VISITOR's on_fact vfunc repeatedly to express the various
equivalence classes and constraints.
This is used by constraint_manager::merge to find the common
facts between two input constraint_managers. */
void
constraint_manager::for_each_fact (fact_visitor *visitor) const
{
/* First, call EQ_EXPR within the various equivalence classes. */
unsigned ec_idx;
equiv_class *ec;
FOR_EACH_VEC_ELT (m_equiv_classes, ec_idx, ec)
{
if (ec->m_cst_sval)
{
unsigned i;
const svalue *sval;
FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
visitor->on_fact (ec->m_cst_sval, EQ_EXPR, sval);
}
for (unsigned i = 0; i < ec->m_vars.length (); i++)
for (unsigned j = i + 1; j < ec->m_vars.length (); j++)
visitor->on_fact (ec->m_vars[i], EQ_EXPR, ec->m_vars[j]);
}
/* Now, express the various constraints. */
unsigned con_idx;
constraint *c;
FOR_EACH_VEC_ELT (m_constraints, con_idx, c)
{
const equiv_class &ec_lhs = c->m_lhs.get_obj (*this);
const equiv_class &ec_rhs = c->m_rhs.get_obj (*this);
enum tree_code code = constraint_tree_code (c->m_op);
if (ec_lhs.m_cst_sval)
{
for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
{
visitor->on_fact (ec_lhs.m_cst_sval, code, ec_rhs.m_vars[j]);
}
}
for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
{
if (ec_rhs.m_cst_sval)
visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_cst_sval);
for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
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. */
void
constraint_manager::validate () const
{
/* Skip this in a release build. */
#if !CHECKING_P
return;
#endif
int i;
equiv_class *ec;
FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
{
gcc_assert (ec);
int j;
const svalue *sval;
FOR_EACH_VEC_ELT (ec->m_vars, j, sval)
gcc_assert (sval);
if (ec->m_constant)
{
gcc_assert (CONSTANT_CLASS_P (ec->m_constant));
gcc_assert (ec->m_cst_sval);
}
#if 0
else
gcc_assert (ec->m_vars.length () > 0);
#endif
}
constraint *c;
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_rhs.null_p ());
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 {
/* Various constraint_manager selftests.
These have to be written in terms of a region_model, since
the latter is responsible for managing svalue instances. */
/* Verify that range::add_bound works as expected. */
static void
test_range ()
{
tree int_0 = build_int_cst (integer_type_node, 0);
tree int_1 = build_int_cst (integer_type_node, 1);
tree int_2 = build_int_cst (integer_type_node, 2);
tree int_5 = build_int_cst (integer_type_node, 5);
{
range r;
ASSERT_FALSE (r.constrained_to_single_element ());
/* (r >= 1). */
ASSERT_TRUE (r.add_bound (GE_EXPR, int_1));
/* Redundant. */
ASSERT_TRUE (r.add_bound (GE_EXPR, int_0));
ASSERT_TRUE (r.add_bound (GT_EXPR, int_0));
ASSERT_FALSE (r.constrained_to_single_element ());
/* Contradiction. */
ASSERT_FALSE (r.add_bound (LT_EXPR, int_1));
/* (r < 5). */
ASSERT_TRUE (r.add_bound (LT_EXPR, int_5));
ASSERT_FALSE (r.constrained_to_single_element ());
/* Contradiction. */
ASSERT_FALSE (r.add_bound (GE_EXPR, int_5));
/* (r < 2). */
ASSERT_TRUE (r.add_bound (LT_EXPR, int_2));
ASSERT_TRUE (r.constrained_to_single_element ());
/* Redundant. */
ASSERT_TRUE (r.add_bound (LE_EXPR, int_1));
ASSERT_TRUE (r.constrained_to_single_element ());
}
}
/* Verify that setting and getting simple conditions within a region_model
work (thus exercising the underlying constraint_manager). */
static void
test_constraint_conditions ()
{
tree int_42 = build_int_cst (integer_type_node, 42);
tree int_0 = build_int_cst (integer_type_node, 0);
tree x = build_global_decl ("x", integer_type_node);
tree y = build_global_decl ("y", integer_type_node);
tree z = build_global_decl ("z", integer_type_node);
/* Self-comparisons. */
{
region_model_manager mgr;
region_model model (&mgr);
ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, x);
ASSERT_CONDITION_TRUE (model, x, LE_EXPR, x);
ASSERT_CONDITION_TRUE (model, x, GE_EXPR, x);
ASSERT_CONDITION_FALSE (model, x, NE_EXPR, x);
ASSERT_CONDITION_FALSE (model, x, LT_EXPR, x);
ASSERT_CONDITION_FALSE (model, x, GT_EXPR, x);
}
/* Adding self-equality shouldn't add equiv classes. */
{
region_model_manager mgr;
region_model model (&mgr);
ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, x);
ADD_SAT_CONSTRAINT (model, int_42, EQ_EXPR, int_42);
/* ...even when done directly via svalues: */
const svalue *sval_int_42 = model.get_rvalue (int_42, NULL);
bool sat = model.get_constraints ()->add_constraint (sval_int_42,
EQ_EXPR,
sval_int_42);
ASSERT_TRUE (sat);
ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
}
/* x == y. */
{
region_model_manager mgr;
region_model model (&mgr);
ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, y);
ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
ASSERT_CONDITION_FALSE (model, x, NE_EXPR, y);
ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
/* Swapped operands. */
ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, x);
ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
ASSERT_CONDITION_FALSE (model, y, NE_EXPR, x);
ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
/* Comparison with other var. */
ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
}
/* x == y, then y == z */
{
region_model_manager mgr;
region_model model (&mgr);
ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, z);
ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, z);
ASSERT_CONDITION_TRUE (model, x, LE_EXPR, z);
ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
ASSERT_CONDITION_FALSE (model, x, NE_EXPR, z);
ASSERT_CONDITION_FALSE (model, x, LT_EXPR, z);
ASSERT_CONDITION_FALSE (model, x, GT_EXPR, z);
}