LCOV - code coverage report
Current view: top level - gcc/analyzer - constraint-manager.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 89.8 % 2473 2221
Test Date: 2026-11-14 16:39:50 Functions: 83.0 % 147 122
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Tracking equivalence classes and constraints at a point on an execution path.
       2              :    Copyright (C) 2019-2026 Free Software Foundation, Inc.
       3              :    Contributed by David Malcolm <dmalcolm@redhat.com>.
       4              : 
       5              : This file is part of GCC.
       6              : 
       7              : GCC is free software; you can redistribute it and/or modify it
       8              : under the terms of the GNU General Public License as published by
       9              : the Free Software Foundation; either version 3, or (at your option)
      10              : any later version.
      11              : 
      12              : GCC is distributed in the hope that it will be useful, but
      13              : WITHOUT ANY WARRANTY; without even the implied warranty of
      14              : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      15              : General Public License for more details.
      16              : 
      17              : You should have received a copy of the GNU General Public License
      18              : along with GCC; see the file COPYING3.  If not see
      19              : <http://www.gnu.org/licenses/>.  */
      20              : 
      21              : #include "analyzer/common.h"
      22              : 
      23              : #include "fold-const.h"
      24              : #include "ordered-hash-map.h"
      25              : #include "cgraph.h"
      26              : #include "cfg.h"
      27              : #include "digraph.h"
      28              : #include "sbitmap.h"
      29              : #include "tree-pretty-print.h"
      30              : 
      31              : #include "analyzer/supergraph.h"
      32              : #include "analyzer/analyzer-logging.h"
      33              : #include "analyzer/call-string.h"
      34              : #include "analyzer/program-point.h"
      35              : #include "analyzer/store.h"
      36              : #include "analyzer/region-model.h"
      37              : #include "analyzer/constraint-manager.h"
      38              : #include "analyzer/call-summary.h"
      39              : #include "analyzer/analyzer-selftests.h"
      40              : #include "analyzer/liveness-context.h"
      41              : 
      42              : #if ENABLE_ANALYZER
      43              : 
      44              : namespace ana {
      45              : 
      46              : tristate
      47        96329 : compare_constants (tree lhs_const, enum tree_code op, tree rhs_const)
      48              : {
      49        96329 :   tree comparison
      50        96329 :     = fold_binary (op, boolean_type_node, lhs_const, rhs_const);
      51        96329 :   if (comparison == boolean_true_node)
      52        74325 :     return tristate (tristate::TS_TRUE);
      53        22004 :   if (comparison == boolean_false_node)
      54        22004 :     return tristate (tristate::TS_FALSE);
      55            0 :   return tristate (tristate::TS_UNKNOWN);
      56              : }
      57              : 
      58              : /* Return true iff CST is below the maximum value for its type.  */
      59              : 
      60              : static bool
      61        25787 : can_plus_one_p (tree cst)
      62              : {
      63        25787 :   gcc_assert (CONSTANT_CLASS_P (cst));
      64        25787 :   return tree_int_cst_lt (cst, TYPE_MAX_VALUE (TREE_TYPE (cst)));
      65              : }
      66              : 
      67              : /* Return (CST + 1).  */
      68              : 
      69              : static tree
      70        12928 : plus_one (tree cst)
      71              : {
      72        12928 :   gcc_assert (CONSTANT_CLASS_P (cst));
      73        12928 :   gcc_assert (can_plus_one_p (cst));
      74        12928 :   tree result = fold_build2 (PLUS_EXPR, TREE_TYPE (cst),
      75              :                              cst, integer_one_node);
      76        12928 :   gcc_assert (CONSTANT_CLASS_P (result));
      77        12928 :   return result;
      78              : }
      79              : 
      80              : /* Return true iff CST is above the minimum value for its type.  */
      81              : 
      82              : static bool
      83         2842 : can_minus_one_p (tree cst)
      84              : {
      85         2842 :   gcc_assert (CONSTANT_CLASS_P (cst));
      86         2842 :   return tree_int_cst_lt (TYPE_MIN_VALUE (TREE_TYPE (cst)), cst);
      87              : }
      88              : 
      89              : /* Return (CST - 1).  */
      90              : 
      91              : static tree
      92         1436 : minus_one (tree cst)
      93              : {
      94         1436 :   gcc_assert (CONSTANT_CLASS_P (cst));
      95         1436 :   gcc_assert (can_minus_one_p (cst));
      96         1436 :   tree result = fold_build2 (MINUS_EXPR, TREE_TYPE (cst),
      97              :                              cst, integer_one_node);
      98         1436 :   gcc_assert (CONSTANT_CLASS_P (result));
      99         1436 :   return result;
     100              : }
     101              : 
     102              : /* struct bound.  */
     103              : 
     104              : /* Ensure that this bound is closed by converting an open bound to a
     105              :    closed one.  */
     106              : 
     107              : void
     108        22071 : bound::ensure_closed (enum bound_kind bnd_kind)
     109              : {
     110        22071 :   if (!m_closed)
     111              :     {
     112              :       /* Offset by 1 in the appropriate direction.
     113              :          For example, convert 3 < x into 4 <= x,
     114              :          and convert x < 5 into x <= 4.  */
     115         8891 :       gcc_assert (CONSTANT_CLASS_P (m_constant));
     116         8891 :       gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (m_constant)));
     117        17285 :       m_constant = fold_build2 (bnd_kind == bound_kind::upper ? MINUS_EXPR : PLUS_EXPR,
     118              :                                 TREE_TYPE (m_constant),
     119              :                                 m_constant, integer_one_node);
     120         8891 :       gcc_assert (CONSTANT_CLASS_P (m_constant));
     121         8891 :       gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (m_constant)));
     122         8891 :       m_closed = true;
     123              :     }
     124        22071 : }
     125              : 
     126              : /* Get "<=" vs "<" for this bound.  */
     127              : 
     128              : const char *
     129            0 : bound::get_relation_as_str () const
     130              : {
     131            0 :   if (m_closed)
     132              :     return "<=";
     133              :   else
     134            0 :     return "<";
     135              : }
     136              : 
     137              : /* struct range.  */
     138              : 
     139              : /* Dump this range to PP, which must support %E for tree.  */
     140              : 
     141              : void
     142            0 : range::dump_to_pp (pretty_printer *pp) const
     143              : {
     144            0 :   if (m_lower_bound.m_constant)
     145              :     {
     146            0 :       if (m_upper_bound.m_constant)
     147            0 :         pp_printf (pp, "%qE %s x %s %qE",
     148            0 :                    m_lower_bound.m_constant,
     149              :                    m_lower_bound.get_relation_as_str (),
     150              :                    m_upper_bound.get_relation_as_str (),
     151              :                    m_upper_bound.m_constant);
     152              :       else
     153            0 :         pp_printf (pp, "%qE %s x",
     154            0 :                    m_lower_bound.m_constant,
     155              :                    m_lower_bound.get_relation_as_str ());
     156              :     }
     157              :   else
     158              :     {
     159            0 :       if (m_upper_bound.m_constant)
     160            0 :         pp_printf (pp, "x %s %qE",
     161              :                    m_upper_bound.get_relation_as_str (),
     162              :                    m_upper_bound.m_constant);
     163              :       else
     164            0 :         pp_string (pp, "x");
     165              :     }
     166            0 : }
     167              : 
     168              : /* Dump this range to stderr.  */
     169              : 
     170              : DEBUG_FUNCTION void
     171            0 : range::dump () const
     172              : {
     173            0 :   tree_dump_pretty_printer pp (stderr);
     174            0 :   dump_to_pp (&pp);
     175            0 :   pp_newline (&pp);
     176            0 : }
     177              : 
     178              : /* Determine if there is only one possible value for this range.
     179              :    If so, return the constant; otherwise, return NULL_TREE.  */
     180              : 
     181              : tree
     182        13855 : range::constrained_to_single_element ()
     183              : {
     184        13855 :   if (m_lower_bound.m_constant == NULL_TREE
     185         4173 :       || m_upper_bound.m_constant == NULL_TREE)
     186              :     return NULL_TREE;
     187              : 
     188          587 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (m_lower_bound.m_constant)))
     189              :     return NULL_TREE;
     190          587 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (m_upper_bound.m_constant)))
     191              :     return NULL_TREE;
     192              : 
     193              :   /* Convert any open bounds to closed bounds.  */
     194          587 :   m_lower_bound.ensure_closed (bound_kind::lower);
     195          587 :   m_upper_bound.ensure_closed (bound_kind::upper);
     196              : 
     197              :   // Are they equal?
     198          587 :   tree comparison = fold_binary (EQ_EXPR, boolean_type_node,
     199              :                                  m_lower_bound.m_constant,
     200              :                                  m_upper_bound.m_constant);
     201          587 :   if (comparison == boolean_true_node)
     202          248 :     return m_lower_bound.m_constant;
     203              :   else
     204              :     return NULL_TREE;
     205              : }
     206              : 
     207              : /* Eval the condition "X OP RHS_CONST" for X within the range.  */
     208              : 
     209              : tristate
     210        13695 : range::eval_condition (enum tree_code op, tree rhs_const) const
     211              : {
     212        13695 :   range copy (*this);
     213        13695 :   if (tree single_element = copy.constrained_to_single_element ())
     214          152 :     return compare_constants (single_element, op, rhs_const);
     215              : 
     216        13543 :   switch (op)
     217              :     {
     218         1295 :     case EQ_EXPR:
     219         1295 :       if (below_lower_bound (rhs_const))
     220          124 :         return tristate (tristate::TS_FALSE);
     221         1171 :       if (above_upper_bound (rhs_const))
     222           16 :         return tristate (tristate::TS_FALSE);
     223              :       break;
     224              : 
     225         3156 :     case LT_EXPR:
     226         3156 :     case LE_EXPR:
     227              :       /* Qn: "X </<= RHS_CONST".  */
     228              :       /* If RHS_CONST > upper bound, then it's true.
     229              :          If RHS_CONST < lower bound, then it's false.
     230              :          Otherwise unknown.  */
     231         3156 :       if (above_upper_bound (rhs_const))
     232          195 :         return tristate (tristate::TS_TRUE);
     233         2961 :       if (below_lower_bound (rhs_const))
     234          252 :         return tristate (tristate::TS_FALSE);
     235              :       break;
     236              : 
     237         6019 :     case NE_EXPR:
     238              :       /* Qn: "X != RHS_CONST".  */
     239              :       /* If RHS_CONST < lower bound, then it's true.
     240              :          If RHS_CONST > upper bound, then it's false.
     241              :          Otherwise unknown.  */
     242         6019 :       if (below_lower_bound (rhs_const))
     243          140 :         return tristate (tristate::TS_TRUE);
     244         5879 :       if (above_upper_bound (rhs_const))
     245            4 :         return tristate (tristate::TS_TRUE);
     246              :       break;
     247              : 
     248         3073 :     case GE_EXPR:
     249         3073 :     case GT_EXPR:
     250              :       /* Qn: "X >=/> RHS_CONST".  */
     251         3073 :       if (above_upper_bound (rhs_const))
     252          239 :         return tristate (tristate::TS_FALSE);
     253         2834 :       if (below_lower_bound (rhs_const))
     254          456 :         return tristate (tristate::TS_TRUE);
     255              :       break;
     256              : 
     257            0 :     default:
     258            0 :       gcc_unreachable ();
     259        12117 :       break;
     260              :     }
     261        12117 :   return tristate (tristate::TS_UNKNOWN);
     262              : }
     263              : 
     264              : /* Return true if RHS_CONST is below the lower bound of this range.  */
     265              : 
     266              : bool
     267        13109 : range::below_lower_bound (tree rhs_const) const
     268              : {
     269        13109 :   if (!m_lower_bound.m_constant)
     270              :     return false;
     271              : 
     272         3867 :   return compare_constants (rhs_const,
     273         3867 :                             m_lower_bound.m_closed ? LT_EXPR : LE_EXPR,
     274         3867 :                             m_lower_bound.m_constant).is_true ();
     275              : }
     276              : 
     277              : /* Return true if RHS_CONST is above the upper bound of this range.  */
     278              : 
     279              : bool
     280        13279 : range::above_upper_bound (tree rhs_const) const
     281              : {
     282        13279 :   if (!m_upper_bound.m_constant)
     283              :     return false;
     284              : 
     285         1775 :   return compare_constants (rhs_const,
     286         1775 :                             m_upper_bound.m_closed ? GT_EXPR : GE_EXPR,
     287         1775 :                             m_upper_bound.m_constant).is_true ();
     288              : }
     289              : 
     290              : /* Attempt to add B to the bound of the given kind of this range.
     291              :    Return true if feasible; false if infeasible.  */
     292              : 
     293              : bool
     294        13963 : range::add_bound (bound b, enum bound_kind bnd_kind)
     295              : {
     296              :   /* Bail out on floating point constants.  */
     297        13963 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (b.m_constant)))
     298              :     return true;
     299              : 
     300        13955 :   b.ensure_closed (bnd_kind);
     301              : 
     302        13955 :   switch (bnd_kind)
     303              :     {
     304            0 :     default:
     305            0 :       gcc_unreachable ();
     306         9227 :     case bound_kind::lower:
     307              :       /* Discard redundant bounds.  */
     308         9227 :       if (m_lower_bound.m_constant)
     309              :         {
     310         4434 :           m_lower_bound.ensure_closed (bound_kind::lower);
     311         4434 :           if (tree_int_cst_le (b.m_constant,
     312         4434 :                                m_lower_bound.m_constant))
     313              :             return true;
     314              :         }
     315         9139 :       if (m_upper_bound.m_constant)
     316              :         {
     317          684 :           m_upper_bound.ensure_closed (bound_kind::upper);
     318              :           /* Reject B <= V <= UPPER when B > UPPER.  */
     319          684 :           if (!tree_int_cst_le (b.m_constant,
     320          684 :                                 m_upper_bound.m_constant))
     321              :             return false;
     322              :         }
     323         9093 :       m_lower_bound = b;
     324         9093 :       break;
     325              : 
     326         4728 :     case bound_kind::upper:
     327              :       /* Discard redundant bounds.  */
     328         4728 :       if (m_upper_bound.m_constant)
     329              :         {
     330          386 :           m_upper_bound.ensure_closed (bound_kind::upper);
     331          386 :           if (!tree_int_cst_lt (b.m_constant,
     332          386 :                                 m_upper_bound.m_constant))
     333              :             return true;
     334              :         }
     335         4698 :       if (m_lower_bound.m_constant)
     336              :         {
     337         1438 :           m_lower_bound.ensure_closed (bound_kind::lower);
     338              :           /* Reject LOWER <= V <= B when LOWER > B.  */
     339         1438 :           if (!tree_int_cst_le (m_lower_bound.m_constant,
     340         1438 :                                 b.m_constant))
     341              :             return false;
     342              :         }
     343         4650 :       m_upper_bound = b;
     344         4650 :       break;
     345              :     }
     346              : 
     347              :   return true;
     348              : }
     349              : 
     350              : /* Attempt to add (RANGE OP RHS_CONST) as a bound to this range.
     351              :    Return true if feasible; false if infeasible.  */
     352              : 
     353              : bool
     354        12181 : range::add_bound (enum tree_code op, tree rhs_const)
     355              : {
     356        12181 :   switch (op)
     357              :     {
     358              :     default:
     359              :       return true;
     360          291 :     case LT_EXPR:
     361              :       /* "V < RHS_CONST"  */
     362          291 :       return add_bound (bound (rhs_const, false), bound_kind::upper);
     363         2450 :     case LE_EXPR:
     364              :       /* "V <= RHS_CONST"  */
     365         2450 :       return add_bound (bound (rhs_const, true), bound_kind::upper);
     366          282 :     case GE_EXPR:
     367              :       /* "V >= RHS_CONST"  */
     368          282 :       return add_bound (bound (rhs_const, true), bound_kind::lower);
     369         2128 :     case GT_EXPR:
     370              :       /* "V > RHS_CONST"  */
     371         2128 :       return add_bound (bound (rhs_const, false), bound_kind::lower);
     372              :     }
     373              : }
     374              : 
     375              : /* struct bounded_range.  */
     376              : 
     377        10662 : bounded_range::bounded_range (const_tree lower, const_tree upper)
     378        10662 : : m_lower (const_cast<tree> (lower)),
     379        10662 :   m_upper (const_cast<tree> (upper))
     380              : {
     381        10662 :   if (lower && upper)
     382              :     {
     383         9472 :       gcc_assert (TREE_CODE (m_lower) == INTEGER_CST);
     384         9472 :       gcc_assert (TREE_CODE (m_upper) == INTEGER_CST);
     385              :       /* We should have lower <= upper.  */
     386         9472 :       gcc_assert (!tree_int_cst_lt (m_upper, m_lower));
     387              :     }
     388              :   else
     389              :     {
     390              :       /* Purely for pending on-stack values, for
     391              :          writing back to.  */
     392         1190 :       gcc_assert (m_lower == NULL_TREE);
     393              :       gcc_assert (m_lower == NULL_TREE);
     394              :     }
     395        10662 : }
     396              : 
     397              : static void
     398          701 : dump_cst (pretty_printer *pp, tree cst, bool show_types)
     399              : {
     400          701 :   gcc_assert (cst);
     401          701 :   if (show_types)
     402              :     {
     403           21 :       pp_character (pp, '(');
     404           21 :       dump_generic_node (pp, TREE_TYPE (cst), 0, (dump_flags_t)0, false);
     405           21 :       pp_character (pp, ')');
     406              :     }
     407          701 :   dump_generic_node (pp, cst, 0, (dump_flags_t)0, false);
     408          701 : }
     409              : 
     410              : /* Dump this object to PP.  */
     411              : 
     412              : void
     413          414 : bounded_range::dump_to_pp (pretty_printer *pp, bool show_types) const
     414              : {
     415          414 :   if (singleton_p ())
     416          127 :     dump_cst (pp, m_lower, show_types);
     417              :   else
     418              :     {
     419          287 :       pp_character (pp, '[');
     420          287 :       dump_cst (pp, m_lower, show_types);
     421          287 :       pp_string (pp, ", ");
     422          287 :       dump_cst (pp, m_upper, show_types);
     423          287 :       pp_character (pp, ']');
     424              :     }
     425          414 : }
     426              : 
     427              : /* Dump this object to stderr.  */
     428              : 
     429              : void
     430            0 : bounded_range::dump (bool show_types) const
     431              : {
     432            0 :   tree_dump_pretty_printer pp (stderr);
     433            0 :   dump_to_pp (&pp, show_types);
     434            0 :   pp_newline (&pp);
     435            0 : }
     436              : 
     437              : std::unique_ptr<json::object>
     438            0 : bounded_range::to_json () const
     439              : {
     440            0 :   auto range_obj = std::make_unique<json::object> ();
     441            0 :   set_json_attr (*range_obj, "lower", m_lower);
     442            0 :   set_json_attr (*range_obj, "upper", m_upper);
     443            0 :   return range_obj;
     444              : }
     445              : 
     446              : std::unique_ptr<text_art::widget>
     447          146 : bounded_range::make_dump_widget (const text_art::dump_widget_info &dwi) const
     448              : {
     449          146 :   using text_art::tree_widget;
     450          146 :   return tree_widget::from_fmt (dwi, default_tree_printer,
     451          146 :                                 "%qE ... %qE", m_lower, m_upper);
     452              : }
     453              : 
     454              : /* Subroutine of bounded_range::to_json.  */
     455              : 
     456              : void
     457            0 : bounded_range::set_json_attr (json::object &obj, const char *name, tree value)
     458              : {
     459            0 :   pretty_printer pp;
     460            0 :   pp_format_decoder (&pp) = default_tree_printer;
     461            0 :   pp_printf (&pp, "%E", value);
     462            0 :   obj.set_string (name, pp_formatted_text (&pp));
     463            0 : }
     464              : 
     465              : 
     466              : /* Return true iff CST is within this range.  */
     467              : 
     468              : bool
     469          369 : bounded_range::contains_p (tree cst) const
     470              : {
     471              :   /* Reject if below lower bound.  */
     472          369 :   if (tree_int_cst_lt (cst, m_lower))
     473              :     return false;
     474              :   /* Reject if above lower bound.  */
     475          311 :   if (tree_int_cst_lt (m_upper, cst))
     476          162 :     return false;
     477              :   return true;
     478              : }
     479              : 
     480              : /* If this range intersects OTHER, return true, writing
     481              :    the intersection to *OUT if OUT is non-NULL.
     482              :    Return false if they do not intersect.  */
     483              : 
     484              : bool
     485         8214 : bounded_range::intersects_p (const bounded_range &other,
     486              :                              bounded_range *out) const
     487              : {
     488         8214 :   const tree max_lower
     489         8214 :     = (tree_int_cst_le (m_lower, other.m_lower)
     490         8214 :        ? other.m_lower : m_lower);
     491         8214 :   gcc_assert (TREE_CODE (max_lower) == INTEGER_CST);
     492         8214 :   const tree min_upper
     493         8214 :     = (tree_int_cst_le (m_upper, other.m_upper)
     494         8214 :        ? m_upper : other.m_upper);
     495         8214 :   gcc_assert (TREE_CODE (min_upper) == INTEGER_CST);
     496              : 
     497         8214 :   if (tree_int_cst_le (max_lower, min_upper))
     498              :     {
     499          677 :       if (out)
     500          359 :         *out = bounded_range (max_lower, min_upper);
     501              :       return true;
     502              :     }
     503              :   else
     504              :     return false;
     505              : }
     506              : 
     507              : bool
     508        53005 : bounded_range::operator== (const bounded_range &other) const
     509              : {
     510        53005 :   return (TREE_TYPE (m_lower) == TREE_TYPE (other.m_lower)
     511        51445 :           && TREE_TYPE (m_upper) == TREE_TYPE (other.m_upper)
     512        50639 :           && tree_int_cst_equal (m_lower, other.m_lower)
     513        63251 :           && tree_int_cst_equal (m_upper, other.m_upper));
     514              : }
     515              : 
     516              : int
     517       159385 : bounded_range::cmp (const bounded_range &br1, const bounded_range &br2)
     518              : {
     519       159385 :   if (int cmp_lower = tree_int_cst_compare (br1.m_lower, br2.m_lower))
     520              :     return cmp_lower;
     521          897 :   if (int cmp_upper = tree_int_cst_compare (br1.m_upper, br2.m_upper))
     522              :     return cmp_upper;
     523          683 :   if (int cmp_lower_type = cmp_types (TREE_TYPE (br1.m_lower),
     524          683 :                                       TREE_TYPE (br2.m_lower)))
     525              :     return cmp_lower_type;
     526          678 :   if (int cmp_upper_type = cmp_types (TREE_TYPE (br1.m_upper),
     527          678 :                                       TREE_TYPE (br2.m_upper)))
     528              :     return cmp_upper_type;
     529              :   return 0;
     530              : }
     531              : 
     532              : /* struct bounded_ranges.  */
     533              : 
     534              : /* Construct a bounded_ranges instance from a single range.  */
     535              : 
     536         6562 : bounded_ranges::bounded_ranges (const bounded_range &range)
     537         6562 : : m_ranges (1)
     538              : {
     539         6562 :   m_ranges.quick_push (range);
     540         6562 :   canonicalize ();
     541         6562 :   validate ();
     542         6562 : }
     543              : 
     544              : /* Construct a bounded_ranges instance from multiple ranges.  */
     545              : 
     546         4628 : bounded_ranges::bounded_ranges (const vec<bounded_range> &ranges)
     547         8871 : : m_ranges (ranges.length ())
     548              : {
     549         4628 :   m_ranges.safe_splice (ranges);
     550         4628 :   canonicalize ();
     551         4628 :   validate ();
     552         4628 : }
     553              : 
     554              : /* Construct a bounded_ranges instance for values of LHS for which
     555              :    (LHS OP RHS_CONST) is true (e.g. "(LHS > 3)".  */
     556              : 
     557          710 : bounded_ranges::bounded_ranges (enum tree_code op, tree rhs_const)
     558          710 : : m_ranges ()
     559              : {
     560          710 :   gcc_assert (TREE_CODE (rhs_const) == INTEGER_CST);
     561          710 :   tree type = TREE_TYPE (rhs_const);
     562          710 :   switch (op)
     563              :     {
     564            0 :     default:
     565            0 :       gcc_unreachable ();
     566          538 :     case EQ_EXPR:
     567          538 :       m_ranges.safe_push (bounded_range (rhs_const, rhs_const));
     568          538 :       break;
     569              : 
     570           16 :     case GE_EXPR:
     571           16 :       m_ranges.safe_push (bounded_range (rhs_const, TYPE_MAX_VALUE (type)));
     572           16 :       break;
     573              : 
     574           50 :     case LE_EXPR:
     575           50 :       m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type), rhs_const));
     576           50 :       break;
     577              : 
     578           52 :     case NE_EXPR:
     579           52 :       if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const))
     580           88 :         m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type),
     581           88 :                                            minus_one (rhs_const)));
     582           52 :       if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type)))
     583           44 :         m_ranges.safe_push (bounded_range (plus_one (rhs_const),
     584           44 :                                            TYPE_MAX_VALUE (type)));
     585              :       break;
     586           38 :     case GT_EXPR:
     587           38 :       if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type)))
     588           30 :         m_ranges.safe_push (bounded_range (plus_one (rhs_const),
     589           30 :                                            TYPE_MAX_VALUE (type)));
     590              :       break;
     591           16 :     case LT_EXPR:
     592           16 :       if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const))
     593           16 :         m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type),
     594           16 :                                            minus_one (rhs_const)));
     595              :       break;
     596              :     }
     597          710 :   canonicalize ();
     598          710 :   validate ();
     599          710 : }
     600              : 
     601              : /* Subroutine of ctors for fixing up m_ranges.
     602              :    Also, initialize m_hash.  */
     603              : 
     604              : void
     605        11900 : bounded_ranges::canonicalize ()
     606              : {
     607              :   /* Sort the ranges.  */
     608        11900 :   m_ranges.qsort ([](const void *p1, const void *p2) -> int
     609              :                   {
     610              :                     const bounded_range &br1 = *(const bounded_range *)p1;
     611              :                     const bounded_range &br2 = *(const bounded_range *)p2;
     612              :                     return bounded_range::cmp (br1, br2);
     613              :                   });
     614              : 
     615              :   /* Merge ranges that are touching or overlapping.  */
     616        18900 :   for (unsigned i = 1; i < m_ranges.length (); )
     617              :     {
     618         7000 :       bounded_range *prev = &m_ranges[i - 1];
     619         7000 :       const bounded_range *next = &m_ranges[i];
     620         7000 :       if (prev->intersects_p (*next, nullptr)
     621         7000 :           || (can_plus_one_p (prev->m_upper)
     622         6682 :               && tree_int_cst_equal (plus_one (prev->m_upper),
     623         6682 :                                      next->m_lower)))
     624              :         {
     625         2280 :           prev->m_upper = next->m_upper;
     626         2280 :           m_ranges.ordered_remove (i);
     627              :         }
     628              :       else
     629         4720 :         i++;
     630              :     }
     631              : 
     632              :   /* Initialize m_hash.  */
     633        11900 :   inchash::hash hstate (0);
     634        51117 :   for (const auto &iter : m_ranges)
     635              :     {
     636        16219 :       inchash::add_expr (iter.m_lower, hstate);
     637        16219 :       inchash::add_expr (iter.m_upper, hstate);
     638              :     }
     639        11900 :   m_hash = hstate.end ();
     640        11900 : }
     641              : 
     642              : /* Assert that this object is valid.  */
     643              : 
     644              : void
     645        11900 : bounded_ranges::validate () const
     646              : {
     647              :   /* Skip this in a release build.  */
     648              : #if !CHECKING_P
     649              :   return;
     650              : #endif
     651              : 
     652        16620 :   for (unsigned i = 1; i < m_ranges.length (); i++)
     653              :     {
     654         4720 :       const bounded_range &prev = m_ranges[i - 1];
     655         4720 :       const bounded_range &next = m_ranges[i];
     656              : 
     657              :       /* Give up if we somehow have incompatible different types.  */
     658         4720 :       if (!types_compatible_p (TREE_TYPE (prev.m_upper),
     659         4720 :                                TREE_TYPE (next.m_lower)))
     660            0 :         continue;
     661              : 
     662              :       /* Verify sorted.  */
     663         4720 :       gcc_assert (tree_int_cst_lt (prev.m_upper, next.m_lower));
     664              : 
     665         4720 :       gcc_assert (can_plus_one_p (prev.m_upper));
     666              :       /* otherwise there's no room for "next".  */
     667              : 
     668              :       /* Verify no ranges touch each other.  */
     669         4720 :       gcc_assert (tree_int_cst_lt (plus_one (prev.m_upper), next.m_lower));
     670              :     }
     671        11900 : }
     672              : 
     673              : /* bounded_ranges equality operator.  */
     674              : 
     675              : bool
     676        68507 : bounded_ranges::operator== (const bounded_ranges &other) const
     677              : {
     678       201888 :   if (m_ranges.length () != other.m_ranges.length ())
     679              :     return false;
     680        60650 :   for (unsigned i = 0; i < m_ranges.length (); i++)
     681              :     {
     682        53005 :       if (m_ranges[i] != other.m_ranges[i])
     683              :         return false;
     684              :     }
     685              :   return true;
     686              : }
     687              : 
     688              : /* Dump this object to PP.  */
     689              : 
     690              : void
     691          314 : bounded_ranges::dump_to_pp (pretty_printer *pp, bool show_types) const
     692              : {
     693          314 :   pp_character (pp, '{');
     694          978 :   for (unsigned i = 0; i < m_ranges.length (); ++i)
     695              :     {
     696          350 :       if (i > 0)
     697           68 :         pp_string (pp, ", ");
     698          350 :       m_ranges[i].dump_to_pp (pp, show_types);
     699              :     }
     700          314 :   pp_character (pp, '}');
     701          314 : }
     702              : 
     703              : /* Dump this object to stderr.  */
     704              : 
     705              : DEBUG_FUNCTION void
     706            0 : bounded_ranges::dump (bool show_types) const
     707              : {
     708            0 :   tree_dump_pretty_printer pp (stderr);
     709            0 :   dump_to_pp (&pp, show_types);
     710            0 :   pp_newline (&pp);
     711            0 : }
     712              : 
     713              : std::unique_ptr<json::value>
     714            0 : bounded_ranges::to_json () const
     715              : {
     716            0 :   auto arr_obj = std::make_unique<json::array> ();
     717              : 
     718            0 :   for (unsigned i = 0; i < m_ranges.length (); ++i)
     719            0 :     arr_obj->append (m_ranges[i].to_json ());
     720              : 
     721            0 :   return arr_obj;
     722            0 : }
     723              : 
     724              : void
     725           65 : bounded_ranges::add_to_dump_widget (text_art::tree_widget &parent,
     726              :                                     const text_art::dump_widget_info &dwi) const
     727              : {
     728          341 :   for (auto &range : m_ranges)
     729          292 :     parent.add_child (range.make_dump_widget (dwi));
     730           65 : }
     731              : 
     732              : /* Determine whether (X OP RHS_CONST) is known to be true or false
     733              :    for all X in the ranges expressed by this object.  */
     734              : 
     735              : tristate
     736          614 : bounded_ranges::eval_condition (enum tree_code op,
     737              :                                 tree rhs_const,
     738              :                                 bounded_ranges_manager *mgr) const
     739              : {
     740              :   /* Convert (X OP RHS_CONST) to a bounded_ranges instance and find
     741              :      the intersection of that with this object.  */
     742          614 :   bounded_ranges other (op, rhs_const);
     743          614 :   const bounded_ranges *intersection
     744          614 :     = mgr->get_or_create_intersection (this, &other);
     745              : 
     746          614 :   if (intersection->m_ranges.length () > 0)
     747              :     {
     748              :       /* We can use pointer equality to check for equality,
     749              :          due to instance consolidation.  */
     750          260 :       if (intersection == this)
     751           50 :         return tristate (tristate::TS_TRUE);
     752              :       else
     753          210 :         return tristate (tristate::TS_UNKNOWN);
     754              :     }
     755              :   else
     756              :     /* No intersection.  */
     757          354 :     return tristate (tristate::TS_FALSE);
     758          614 : }
     759              : 
     760              : /* Return true if CST is within any of the ranges.  */
     761              : 
     762              : bool
     763          251 : bounded_ranges::contain_p (tree cst) const
     764              : {
     765          251 :   gcc_assert (TREE_CODE (cst) == INTEGER_CST);
     766          909 :   for (const auto &iter : m_ranges)
     767              :     {
     768              :       /* TODO: should we optimize this based on sorting?  */
     769          337 :       if (iter.contains_p (cst))
     770              :         return true;
     771              :     }
     772              :   return false;
     773              : }
     774              : 
     775              : int
     776          124 : bounded_ranges::cmp (const bounded_ranges *a, const bounded_ranges *b)
     777              : {
     778          124 :   if (int cmp_length = ((int)a->m_ranges.length ()
     779          248 :                         - (int)b->m_ranges.length ()))
     780              :     return cmp_length;
     781           70 :   for (unsigned i = 0; i < a->m_ranges.length (); i++)
     782              :     {
     783           70 :       if (int cmp_range = bounded_range::cmp (a->m_ranges[i], b->m_ranges[i]))
     784              :         return cmp_range;
     785              :     }
     786              :   /* They are equal.  They ought to have been consolidated, so we should
     787              :      have two pointers to the same object.  */
     788            0 :   gcc_assert (a == b);
     789              :   return 0;
     790              : }
     791              : 
     792              : /* class bounded_ranges_manager.  */
     793              : 
     794              : /* bounded_ranges_manager's dtor.  */
     795              : 
     796         4417 : bounded_ranges_manager::~bounded_ranges_manager ()
     797              : {
     798              :   /* Delete the managed objects.  */
     799         7954 :   for (const auto &iter : m_map)
     800         3537 :     delete iter.second;
     801         4417 : }
     802              : 
     803              : /* Get the bounded_ranges instance for the empty set,  creating it if
     804              :    necessary.  */
     805              : 
     806              : const bounded_ranges *
     807            8 : bounded_ranges_manager::get_or_create_empty ()
     808              : {
     809            8 :   auto_vec<bounded_range> empty_vec;
     810              : 
     811            8 :   return consolidate (new bounded_ranges (empty_vec));
     812            8 : }
     813              : 
     814              : /* Get the bounded_ranges instance for {CST}, creating it if necessary.  */
     815              : 
     816              : const bounded_ranges *
     817         5906 : bounded_ranges_manager::get_or_create_point (const_tree cst)
     818              : {
     819         5906 :   gcc_assert (TREE_CODE (cst) == INTEGER_CST);
     820              : 
     821         5906 :   return get_or_create_range (cst, cst);
     822              : }
     823              : 
     824              : /* Get the bounded_ranges instance for {[LOWER_BOUND..UPPER_BOUND]},
     825              :    creating it if necessary.  */
     826              : 
     827              : const bounded_ranges *
     828         6562 : bounded_ranges_manager::get_or_create_range (const_tree lower_bound,
     829              :                                              const_tree upper_bound)
     830              : {
     831         6562 :   gcc_assert (TREE_CODE (lower_bound) == INTEGER_CST);
     832         6562 :   gcc_assert (TREE_CODE (upper_bound) == INTEGER_CST);
     833              : 
     834         6562 :   return consolidate
     835         6562 :     (new bounded_ranges (bounded_range (lower_bound, upper_bound)));
     836              : }
     837              : 
     838              : /* Get the bounded_ranges instance for the union of OTHERS,
     839              :    creating it if necessary.  */
     840              : 
     841              : const bounded_ranges *
     842         3578 : bounded_ranges_manager::
     843              : get_or_create_union (const vec <const bounded_ranges *> &others)
     844              : {
     845         3578 :   auto_vec<bounded_range> ranges;
     846        18028 :   for (const auto &r : others)
     847         7294 :     ranges.safe_splice (r->m_ranges);
     848         3578 :   return consolidate (new bounded_ranges (ranges));
     849         3578 : }
     850              : 
     851              : /* Get the bounded_ranges instance for the intersection of A and B,
     852              :    creating it if necessary.  */
     853              : 
     854              : const bounded_ranges *
     855          650 : bounded_ranges_manager::get_or_create_intersection (const bounded_ranges *a,
     856              :                                                     const bounded_ranges *b)
     857              : {
     858          650 :   auto_vec<bounded_range> ranges;
     859          650 :   unsigned a_idx = 0;
     860          650 :   unsigned b_idx = 0;
     861          650 :   while (a_idx < a->m_ranges.length ()
     862         1832 :          && b_idx < b->m_ranges.length ())
     863              :     {
     864         1182 :       const bounded_range &r_a = a->m_ranges[a_idx];
     865         1182 :       const bounded_range &r_b = b->m_ranges[b_idx];
     866              : 
     867         1182 :       bounded_range intersection (NULL_TREE, NULL_TREE);
     868         1182 :       if (r_a.intersects_p (r_b, &intersection))
     869              :         {
     870          343 :           ranges.safe_push (intersection);
     871              :         }
     872         1182 :       if (tree_int_cst_lt (r_a.m_lower, r_b.m_lower))
     873              :         {
     874          659 :           a_idx++;
     875              :         }
     876              :       else
     877              :         {
     878          523 :           if (tree_int_cst_lt (r_a.m_upper, r_b.m_upper))
     879           36 :             a_idx++;
     880              :           else
     881          487 :             b_idx++;
     882              :         }
     883              :     }
     884              : 
     885          650 :   return consolidate (new bounded_ranges (ranges));
     886          650 : }
     887              : 
     888              : /* Get the bounded_ranges instance for the inverse of OTHER relative
     889              :    to TYPE, creating it if necessary.
     890              :    This is for use when handling "default" in switch statements, where
     891              :    OTHER represents all the other cases.  */
     892              : 
     893              : const bounded_ranges *
     894          384 : bounded_ranges_manager::get_or_create_inverse (const bounded_ranges *other,
     895              :                                                tree type)
     896              : {
     897          384 :   tree min_val = TYPE_MIN_VALUE (type);
     898          384 :   tree max_val = TYPE_MAX_VALUE (type);
     899          384 :   if (other->m_ranges.length () == 0)
     900            0 :     return get_or_create_range (min_val, max_val);
     901          384 :   auto_vec<bounded_range> ranges;
     902          384 :   tree first_lb = other->m_ranges[0].m_lower;
     903          384 :   if (tree_int_cst_lt (min_val, first_lb)
     904          384 :       && can_minus_one_p (first_lb))
     905          297 :     ranges.safe_push (bounded_range (min_val,
     906          297 :                                      minus_one (first_lb)));
     907         1471 :   for (unsigned i = 1; i < other->m_ranges.length (); i++)
     908              :     {
     909         1087 :       tree prev_ub = other->m_ranges[i - 1].m_upper;
     910         1087 :       tree iter_lb = other->m_ranges[i].m_lower;
     911         1087 :       gcc_assert (tree_int_cst_lt (prev_ub, iter_lb));
     912         1087 :       if (can_plus_one_p (prev_ub) && can_minus_one_p (iter_lb))
     913         2174 :         ranges.safe_push (bounded_range (plus_one (prev_ub),
     914         2174 :                                          minus_one (iter_lb)));
     915              :     }
     916          384 :   tree last_ub
     917          768 :     = other->m_ranges[other->m_ranges.length () - 1].m_upper;
     918          384 :   if (tree_int_cst_lt (last_ub, max_val)
     919          384 :       && can_plus_one_p (last_ub))
     920          365 :     ranges.safe_push (bounded_range (plus_one (last_ub), max_val));
     921              : 
     922          384 :   return consolidate (new bounded_ranges (ranges));
     923          384 : }
     924              : 
     925              : /* If an object equal to INST is already present, delete INST and
     926              :    return the existing object.
     927              :    Otherwise add INST and return it.  */
     928              : 
     929              : const bounded_ranges *
     930        11182 : bounded_ranges_manager::consolidate (bounded_ranges *inst)
     931              : {
     932        11182 :   if (bounded_ranges **slot = m_map.get (inst))
     933              :     {
     934        15290 :       delete inst;
     935         7645 :       return *slot;
     936              :     }
     937         3537 :   m_map.put (inst, inst);
     938         3537 :   return inst;
     939              : }
     940              : 
     941              : /* Get the bounded_ranges instance for CASE_LABEL within
     942              :    SWITCH_STMT.  */
     943              : 
     944              : const bounded_ranges *
     945         6770 : bounded_ranges_manager::
     946              : make_case_label_ranges (const gswitch *switch_stmt,
     947              :                         tree case_label)
     948              : {
     949         6770 :   gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
     950         6770 :   tree lower_bound = CASE_LOW (case_label);
     951         6770 :   tree upper_bound = CASE_HIGH (case_label);
     952         6770 :   if (lower_bound)
     953              :     {
     954         6434 :       if (upper_bound)
     955              :         /* Range.  */
     956          584 :         return get_or_create_range (lower_bound, upper_bound);
     957              :       else
     958              :         /* Single-value.  */
     959         5850 :         return get_or_create_point (lower_bound);
     960              :     }
     961              :   else
     962              :     {
     963              :       /* The default case.
     964              :          Add exclusions based on the other cases.  */
     965          336 :       auto_vec <const bounded_ranges *> other_case_ranges
     966          336 :         (gimple_switch_num_labels (switch_stmt));
     967          336 :       for (unsigned other_idx = 1;
     968         3553 :            other_idx < gimple_switch_num_labels (switch_stmt);
     969              :            other_idx++)
     970              :         {
     971         3217 :           tree other_label = gimple_switch_label (switch_stmt,
     972              :                                                   other_idx);
     973         3217 :           const bounded_ranges *other_ranges
     974         3217 :             = make_case_label_ranges (switch_stmt, other_label);
     975         3217 :           other_case_ranges.quick_push (other_ranges);
     976              :         }
     977          336 :       const bounded_ranges *other_cases_ranges
     978          336 :         = get_or_create_union (other_case_ranges);
     979          336 :       tree type = TREE_TYPE (gimple_switch_index (switch_stmt));
     980          336 :       return get_or_create_inverse (other_cases_ranges, type);
     981          336 :     }
     982              : }
     983              : 
     984              : /* Dump the number of objects of each class that were managed by this
     985              :    manager to LOGGER.
     986              :    If SHOW_OBJS is true, also dump the objects themselves.  */
     987              : 
     988              : void
     989            5 : bounded_ranges_manager::log_stats (logger *logger, bool show_objs) const
     990              : {
     991            5 :   LOG_SCOPE (logger);
     992            5 :   logger->log ("  # %s: %li", "ranges", (long)m_map.elements ());
     993            5 :   if (!show_objs)
     994            0 :     return;
     995              : 
     996            5 :   auto_vec<const bounded_ranges *> vec_objs (m_map.elements ());
     997           15 :   for (const auto &iter : m_map)
     998           10 :     vec_objs.quick_push (iter.second);
     999            5 :   vec_objs.qsort
    1000              :     ([](const void *p1, const void *p2) -> int
    1001              :      {
    1002              :        const bounded_ranges *br1 = *(const bounded_ranges * const *)p1;
    1003              :        const bounded_ranges *br2 = *(const bounded_ranges * const *)p2;
    1004              :        return bounded_ranges::cmp (br1, br2);
    1005              :      });
    1006              : 
    1007           17 :   for (const auto &iter : vec_objs)
    1008              :     {
    1009           10 :       logger->start_log_line ();
    1010           10 :       pretty_printer *pp = logger->get_printer ();
    1011           10 :       pp_string (pp, "    ");
    1012           10 :       iter->dump_to_pp (pp, true);
    1013           10 :       logger->end_log_line ();
    1014              :     }
    1015            5 : }
    1016              : 
    1017              : /* class equiv_class.  */
    1018              : 
    1019              : /* equiv_class's default ctor.  */
    1020              : 
    1021       254522 : equiv_class::equiv_class ()
    1022       254522 : : m_constant (NULL_TREE), m_cst_sval (nullptr), m_vars ()
    1023              : {
    1024       254522 : }
    1025              : 
    1026              : /* equiv_class's copy ctor.  */
    1027              : 
    1028      8578416 : equiv_class::equiv_class (const equiv_class &other)
    1029      8578416 : : m_constant (other.m_constant), m_cst_sval (other.m_cst_sval),
    1030     17156832 :   m_vars (other.m_vars.length ())
    1031              : {
    1032     35033167 :   for (const svalue *sval : other.m_vars)
    1033      9297919 :     m_vars.quick_push (sval);
    1034      8578416 : }
    1035              : 
    1036              : /* Print an all-on-one-line representation of this equiv_class to PP,
    1037              :    which must support %E for trees.  */
    1038              : 
    1039              : void
    1040         1564 : equiv_class::print (pretty_printer *pp) const
    1041              : {
    1042         1564 :   pp_character (pp, '{');
    1043         1564 :   int i;
    1044         1564 :   const svalue *sval;
    1045         5040 :   FOR_EACH_VEC_ELT (m_vars, i, sval)
    1046              :     {
    1047         1912 :       if (i > 0)
    1048          348 :         pp_string (pp, " == ");
    1049         1912 :       sval->dump_to_pp (pp, true);
    1050              :     }
    1051         1564 :   if (m_constant)
    1052              :     {
    1053          782 :       if (i > 0)
    1054          782 :         pp_string (pp, " == ");
    1055          782 :       pp_printf (pp, "[m_constant]%qE", m_constant);
    1056              :     }
    1057         1564 :   pp_character (pp, '}');
    1058         1564 : }
    1059              : 
    1060              : /* Return a new json::object of the form
    1061              :    {"svals" : [str],
    1062              :     "constant" : optional str}.  */
    1063              : 
    1064              : std::unique_ptr<json::object>
    1065           19 : equiv_class::to_json () const
    1066              : {
    1067           19 :   auto ec_obj = std::make_unique<json::object> ();
    1068              : 
    1069           19 :   auto sval_arr = std::make_unique<json::array> ();
    1070           81 :   for (const svalue *sval : m_vars)
    1071           24 :     sval_arr->append (sval->to_json ());
    1072           19 :   ec_obj->set ("svals", std::move (sval_arr));
    1073              : 
    1074           19 :   if (m_constant)
    1075              :     {
    1076           12 :       pretty_printer pp;
    1077           12 :       pp_format_decoder (&pp) = default_tree_printer;
    1078           12 :       pp_printf (&pp, "%qE", m_constant);
    1079           12 :       ec_obj->set_string ("constant", pp_formatted_text (&pp));
    1080           12 :     }
    1081              : 
    1082           38 :   return ec_obj;
    1083           19 : }
    1084              : 
    1085              : std::unique_ptr<text_art::tree_widget>
    1086         1259 : equiv_class::make_dump_widget (const text_art::dump_widget_info &dwi,
    1087              :                                unsigned id) const
    1088              : {
    1089         1259 :   using text_art::tree_widget;
    1090         1259 :   std::unique_ptr<tree_widget> ec_widget;
    1091              : 
    1092         1259 :   {
    1093         1259 :     pretty_printer pp;
    1094         1259 :     pp_string (&pp, "Equivalence class ");
    1095         1259 :     equiv_class_id (id).print (&pp);
    1096         1259 :     ec_widget = tree_widget::make (dwi, &pp);
    1097         1259 :   }
    1098              : 
    1099         5182 :   for (const svalue *sval : m_vars)
    1100              :     {
    1101         1405 :       pretty_printer pp;
    1102         1405 :       pp_format_decoder (&pp) = default_tree_printer;
    1103         1405 :       sval->dump_to_pp (&pp, true);
    1104         2810 :       ec_widget->add_child (tree_widget::make (dwi, &pp));
    1105         1405 :     }
    1106              : 
    1107         1259 :   if (m_constant)
    1108              :     {
    1109          412 :       pretty_printer pp;
    1110          412 :       pp_format_decoder (&pp) = default_tree_printer;
    1111          412 :       pp_printf (&pp, "%qE", m_constant);
    1112          824 :       ec_widget->add_child (tree_widget::make (dwi, &pp));
    1113          412 :     }
    1114              : 
    1115         1259 :   return ec_widget;
    1116              : }
    1117              : 
    1118              : /* Generate a hash value for this equiv_class.
    1119              :    This relies on the ordering of m_vars, and so this object needs to
    1120              :    have been canonicalized for this to be meaningful.  */
    1121              : 
    1122              : hashval_t
    1123      3431551 : equiv_class::hash () const
    1124              : {
    1125      3431551 :   inchash::hash hstate;
    1126              : 
    1127      3431551 :   inchash::add_expr (m_constant, hstate);
    1128     13991363 :   for (const svalue * sval : m_vars)
    1129      3696710 :     hstate.add_ptr (sval);
    1130      3431551 :   return hstate.end ();
    1131              : }
    1132              : 
    1133              : /* Equality operator for equiv_class.
    1134              :    This relies on the ordering of m_vars, and so this object
    1135              :    and OTHER need to have been canonicalized for this to be
    1136              :    meaningful.  */
    1137              : 
    1138              : bool
    1139      1103994 : equiv_class::operator== (const equiv_class &other) const
    1140              : {
    1141      1103994 :   if (m_constant != other.m_constant)
    1142              :     return false; // TODO: use tree equality here?
    1143              : 
    1144              :   /* FIXME: should we compare m_cst_sval?  */
    1145              : 
    1146      3311538 :   if (m_vars.length () != other.m_vars.length ())
    1147              :     return false;
    1148              : 
    1149              :   int i;
    1150              :   const svalue *sval;
    1151      2292922 :   FOR_EACH_VEC_ELT (m_vars, i, sval)
    1152      1189189 :     if (sval != other.m_vars[i])
    1153              :       return false;
    1154              : 
    1155              :   return true;
    1156              : }
    1157              : 
    1158              : /* Add SID to this equiv_class, using CM to check if it's a constant.  */
    1159              : 
    1160              : void
    1161       280585 : equiv_class::add (const svalue *sval)
    1162              : {
    1163       280585 :   gcc_assert (sval);
    1164       280585 :   if (tree cst = sval->maybe_get_constant ())
    1165              :     {
    1166        97340 :       gcc_assert (CONSTANT_CLASS_P (cst));
    1167              :       /* FIXME: should we canonicalize which svalue is the constant
    1168              :          when there are multiple equal constants?  */
    1169        97340 :       m_constant = cst;
    1170        97340 :       m_cst_sval = sval;
    1171              :     }
    1172       280585 :   m_vars.safe_push (sval);
    1173       280585 : }
    1174              : 
    1175              : /* Remove SID from this equivalence class.
    1176              :    Return true if SID was the last var in the equivalence class (suggesting
    1177              :    a possible leak).  */
    1178              : 
    1179              : bool
    1180        28501 : equiv_class::del (const svalue *sval)
    1181              : {
    1182        28501 :   gcc_assert (sval);
    1183        28501 :   gcc_assert (sval != m_cst_sval);
    1184              : 
    1185              :   int i;
    1186              :   const svalue *iv;
    1187        29056 :   FOR_EACH_VEC_ELT (m_vars, i, iv)
    1188              :     {
    1189        29056 :       if (iv == sval)
    1190              :         {
    1191        28501 :           m_vars[i] = m_vars[m_vars.length () - 1];
    1192        28501 :           m_vars.pop ();
    1193        28501 :           return m_vars.length () == 0;
    1194              :         }
    1195              :     }
    1196              : 
    1197              :   /* SVAL must be in the class.  */
    1198            0 :   gcc_unreachable ();
    1199              :   return false;
    1200              : }
    1201              : 
    1202              : /* Get a representative member of this class, for handling cases
    1203              :    where the IDs can change mid-traversal.  */
    1204              : 
    1205              : const svalue *
    1206     42661059 : equiv_class::get_representative () const
    1207              : {
    1208     42661059 :   gcc_assert (m_vars.length () > 0);
    1209     42661059 :   return m_vars[0];
    1210              : }
    1211              : 
    1212              : /* Sort the svalues within this equiv_class.  */
    1213              : 
    1214              : void
    1215      2322698 : equiv_class::canonicalize ()
    1216              : {
    1217      2322698 :   m_vars.qsort (svalue::cmp_ptr_ptr);
    1218      2322698 : }
    1219              : 
    1220              : /* Return true if this EC contains a variable, false if it merely
    1221              :    contains constants.
    1222              :    Subroutine of constraint_manager::canonicalize, for removing
    1223              :    redundant ECs.  */
    1224              : 
    1225              : bool
    1226       138578 : equiv_class::contains_non_constant_p () const
    1227              : {
    1228       138578 :   if (m_constant)
    1229              :     {
    1230       410084 :       for (auto iter : m_vars)
    1231       156674 :         if (iter->maybe_get_constant ())
    1232        46928 :           continue;
    1233              :         else
    1234              :           /* We have {non-constant == constant}.  */
    1235              :           return true;
    1236              :       /* We only have constants.  */
    1237              :       return false;
    1238              :     }
    1239              :   else
    1240              :     /* Return true if we have {non-constant == non-constant}.  */
    1241        35052 :     return m_vars.length () > 1;
    1242              : }
    1243              : 
    1244              : /* Get a debug string for C_OP.  */
    1245              : 
    1246              : const char *
    1247          789 : constraint_op_code (enum constraint_op c_op)
    1248              : {
    1249          789 :   switch (c_op)
    1250              :     {
    1251            0 :     default:
    1252            0 :       gcc_unreachable ();
    1253              :     case CONSTRAINT_NE: return "!=";
    1254            0 :     case CONSTRAINT_LT: return "<";
    1255            0 :     case CONSTRAINT_LE: return "<=";
    1256              :     }
    1257              : }
    1258              : 
    1259              : /* Convert C_OP to an enum tree_code.  */
    1260              : 
    1261              : enum tree_code
    1262        87688 : constraint_tree_code (enum constraint_op c_op)
    1263              : {
    1264        87688 :   switch (c_op)
    1265              :     {
    1266            0 :     default:
    1267            0 :       gcc_unreachable ();
    1268              :     case CONSTRAINT_NE: return NE_EXPR;
    1269              :     case CONSTRAINT_LT: return LT_EXPR;
    1270              :     case CONSTRAINT_LE: return LE_EXPR;
    1271              :     }
    1272              : }
    1273              : 
    1274              : /* Given "lhs C_OP rhs", determine "lhs T_OP rhs".
    1275              : 
    1276              :    For example, given "x < y", then "x > y" is false.  */
    1277              : 
    1278              : static tristate
    1279       219274 : eval_constraint_op_for_op (enum constraint_op c_op, enum tree_code t_op)
    1280              : {
    1281       219274 :   switch (c_op)
    1282              :     {
    1283            0 :     default:
    1284            0 :       gcc_unreachable ();
    1285       192779 :     case CONSTRAINT_NE:
    1286       192779 :       if (t_op == EQ_EXPR)
    1287         2178 :         return tristate (tristate::TS_FALSE);
    1288       190601 :       if (t_op == NE_EXPR)
    1289       190183 :         return tristate (tristate::TS_TRUE);
    1290              :       break;
    1291        13440 :     case CONSTRAINT_LT:
    1292        13440 :       if (t_op == LT_EXPR || t_op == LE_EXPR || t_op == NE_EXPR)
    1293        12501 :         return tristate (tristate::TS_TRUE);
    1294          939 :       if (t_op == EQ_EXPR || t_op == GT_EXPR || t_op == GE_EXPR)
    1295          939 :         return tristate (tristate::TS_FALSE);
    1296              :       break;
    1297        13055 :     case CONSTRAINT_LE:
    1298        13055 :       if (t_op == LE_EXPR)
    1299        10928 :         return tristate (tristate::TS_TRUE);
    1300         2127 :       if (t_op == GT_EXPR)
    1301         1026 :         return tristate (tristate::TS_FALSE);
    1302              :       break;
    1303              :     }
    1304         1519 :   return tristate (tristate::TS_UNKNOWN);
    1305              : }
    1306              : 
    1307              : /* class constraint.  */
    1308              : 
    1309              : /* Print this constraint to PP (which must support %E for trees),
    1310              :    using CM to look up equiv_class instances from ids.  */
    1311              : 
    1312              : void
    1313          782 : constraint::print (pretty_printer *pp, const constraint_manager &cm) const
    1314              : {
    1315          782 :   m_lhs.print (pp);
    1316          782 :   pp_string (pp, ": ");
    1317          782 :   m_lhs.get_obj (cm).print (pp);
    1318          782 :   pp_string (pp, " ");
    1319          782 :   pp_string (pp, constraint_op_code (m_op));
    1320          782 :   pp_string (pp, " ");
    1321          782 :   m_rhs.print (pp);
    1322          782 :   pp_string (pp, ": ");
    1323          782 :   m_rhs.get_obj (cm).print (pp);
    1324          782 : }
    1325              : 
    1326              : /* Return a new json::object of the form
    1327              :    {"lhs" : int, the EC index
    1328              :     "op"  : str,
    1329              :     "rhs" : int, the EC index}.  */
    1330              : 
    1331              : std::unique_ptr<json::object>
    1332            7 : constraint::to_json () const
    1333              : {
    1334            7 :   auto con_obj = std::make_unique<json::object> ();
    1335              : 
    1336            7 :   con_obj->set_integer ("lhs", m_lhs.as_int ());
    1337            7 :   con_obj->set_string ("op", constraint_op_code (m_op));
    1338            7 :   con_obj->set_integer ("rhs", m_rhs.as_int ());
    1339              : 
    1340            7 :   return con_obj;
    1341              : }
    1342              : 
    1343              : std::unique_ptr<text_art::widget>
    1344          782 : constraint::make_dump_widget (const text_art::dump_widget_info &dwi,
    1345              :                               const constraint_manager &cm) const
    1346              : {
    1347          782 :   pretty_printer pp;
    1348          782 :   pp_format_decoder (&pp) = default_tree_printer;
    1349          782 :   pp_show_color (&pp) = true;
    1350          782 :   print (&pp, cm);
    1351          782 :   return text_art::tree_widget::make (dwi, &pp);
    1352          782 : }
    1353              : 
    1354              : /* Generate a hash value for this constraint.  */
    1355              : 
    1356              : hashval_t
    1357      2294845 : constraint::hash () const
    1358              : {
    1359      2294845 :   inchash::hash hstate;
    1360      2294845 :   hstate.add_int (m_lhs.m_idx);
    1361      2294845 :   hstate.add_int (m_op);
    1362      2294845 :   hstate.add_int (m_rhs.m_idx);
    1363      2294845 :   return hstate.end ();
    1364              : }
    1365              : 
    1366              : /* Equality operator for constraints.  */
    1367              : 
    1368              : bool
    1369       739487 : constraint::operator== (const constraint &other) const
    1370              : {
    1371       739487 :   if (m_lhs != other.m_lhs)
    1372              :     return false;
    1373       739475 :   if (m_op != other.m_op)
    1374              :     return false;
    1375       739475 :   if (m_rhs != other.m_rhs)
    1376            0 :     return false;
    1377              :   return true;
    1378              : }
    1379              : 
    1380              : /* Return true if this constraint is implied by OTHER.  */
    1381              : 
    1382              : bool
    1383       271301 : constraint::implied_by (const constraint &other,
    1384              :                          const constraint_manager &cm) const
    1385              : {
    1386       271301 :   if (m_lhs == other.m_lhs)
    1387        17047 :     if (tree rhs_const = m_rhs.get_obj (cm).get_any_constant ())
    1388        14598 :       if (tree other_rhs_const = other.m_rhs.get_obj (cm).get_any_constant ())
    1389        13973 :         if (m_lhs.get_obj (cm).get_any_constant () == NULL_TREE)
    1390        13973 :           if (m_op == other.m_op)
    1391        12849 :             switch (m_op)
    1392              :               {
    1393              :               default:
    1394              :                 break;
    1395           79 :               case CONSTRAINT_LE:
    1396           79 :               case CONSTRAINT_LT:
    1397           79 :                 if (compare_constants (rhs_const,
    1398              :                                        GE_EXPR,
    1399           79 :                                        other_rhs_const).is_true ())
    1400           79 :                   return true;
    1401              :                 break;
    1402              :               }
    1403              :   return false;
    1404              : }
    1405              : 
    1406              : /* class bounded_ranges_constraint.  */
    1407              : 
    1408              : void
    1409            0 : bounded_ranges_constraint::print (pretty_printer *pp,
    1410              :                                   const constraint_manager &cm) const
    1411              : {
    1412            0 :   m_ec_id.print (pp);
    1413            0 :   pp_string (pp, ": ");
    1414            0 :   m_ec_id.get_obj (cm).print (pp);
    1415            0 :   pp_string (pp, ": ");
    1416            0 :   m_ranges->dump_to_pp (pp, true);
    1417            0 : }
    1418              : 
    1419              : std::unique_ptr<json::object>
    1420            0 : bounded_ranges_constraint::to_json () const
    1421              : {
    1422            0 :   auto con_obj = std::make_unique<json::object> ();
    1423              : 
    1424            0 :   con_obj->set_integer ("ec", m_ec_id.as_int ());
    1425            0 :   con_obj->set ("ranges", m_ranges->to_json ());
    1426              : 
    1427            0 :   return con_obj;
    1428              : }
    1429              : 
    1430              : std::unique_ptr<text_art::tree_widget>
    1431           65 : bounded_ranges_constraint::
    1432              : make_dump_widget (const text_art::dump_widget_info &dwi) const
    1433              : {
    1434           65 :   using text_art::tree_widget;
    1435           65 :   std::unique_ptr<tree_widget> brc_widget
    1436              :     (tree_widget::from_fmt (dwi, nullptr,
    1437           65 :                             "ec%i bounded ranges", m_ec_id.as_int ()));
    1438           65 :   m_ranges->add_to_dump_widget (*brc_widget.get (), dwi);
    1439           65 :   return brc_widget;
    1440              : }
    1441              : 
    1442              : bool
    1443         4829 : bounded_ranges_constraint::
    1444              : operator== (const bounded_ranges_constraint &other) const
    1445              : {
    1446         4829 :   if (m_ec_id != other.m_ec_id)
    1447              :     return false;
    1448              : 
    1449              :   /* We can compare by pointer, since the bounded_ranges_manager
    1450              :      consolidates instances.  */
    1451         4829 :   return m_ranges == other.m_ranges;
    1452              : }
    1453              : 
    1454              : void
    1455        14518 : bounded_ranges_constraint::add_to_hash (inchash::hash *hstate) const
    1456              : {
    1457        14518 :   hstate->add_int (m_ec_id.m_idx);
    1458        14518 :   hstate->merge_hash (m_ranges->get_hash ());
    1459        14518 : }
    1460              : 
    1461              : /* class equiv_class_id.  */
    1462              : 
    1463              : /* Get the underlying equiv_class for this ID from CM.  */
    1464              : 
    1465              : const equiv_class &
    1466      1172407 : equiv_class_id::get_obj (const constraint_manager &cm) const
    1467              : {
    1468      1172407 :   return cm.get_equiv_class_by_index (m_idx);
    1469              : }
    1470              : 
    1471              : /* Access the underlying equiv_class for this ID from CM.  */
    1472              : 
    1473              : equiv_class &
    1474       115508 : equiv_class_id::get_obj (constraint_manager &cm) const
    1475              : {
    1476       115508 :   return cm.get_equiv_class_by_index (m_idx);
    1477              : }
    1478              : 
    1479              : /* Print this equiv_class_id to PP.  */
    1480              : 
    1481              : void
    1482         2823 : equiv_class_id::print (pretty_printer *pp) const
    1483              : {
    1484         2823 :   if (null_p ())
    1485            0 :     pp_printf (pp, "null");
    1486              :   else
    1487         2823 :     pp_printf (pp, "ec%i", m_idx);
    1488         2823 : }
    1489              : 
    1490              : /* class constraint_manager.  */
    1491              : 
    1492              : /* constraint_manager's copy ctor.  */
    1493              : 
    1494      2779458 : constraint_manager::constraint_manager (const constraint_manager &other)
    1495      2779458 : : m_equiv_classes (other.m_equiv_classes.length ()),
    1496      4416787 :   m_constraints (other.m_constraints.length ()),
    1497      2814562 :   m_bounded_ranges_constraints (other.m_bounded_ranges_constraints.length ()),
    1498      2779458 :   m_mgr (other.m_mgr)
    1499              : {
    1500      2779458 :   int i;
    1501      2779458 :   equiv_class *ec;
    1502     11357874 :   FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
    1503      8578416 :     m_equiv_classes.quick_push (new equiv_class (*ec));
    1504              :   constraint *c;
    1505      8601434 :   FOR_EACH_VEC_ELT (other.m_constraints, i, c)
    1506      5821976 :     m_constraints.quick_push (*c);
    1507      2895611 :   for (const auto &iter : other.m_bounded_ranges_constraints)
    1508        45945 :     m_bounded_ranges_constraints.quick_push (iter);
    1509      2779458 : }
    1510              : 
    1511              : /* constraint_manager's assignment operator.  */
    1512              : 
    1513              : constraint_manager&
    1514            0 : constraint_manager::operator= (const constraint_manager &other)
    1515              : {
    1516            0 :   gcc_assert (m_equiv_classes.length () == 0);
    1517            0 :   gcc_assert (m_constraints.length () == 0);
    1518            0 :   gcc_assert (m_bounded_ranges_constraints.length () == 0);
    1519              : 
    1520            0 :   int i;
    1521            0 :   equiv_class *ec;
    1522            0 :   m_equiv_classes.reserve (other.m_equiv_classes.length ());
    1523            0 :   FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
    1524            0 :     m_equiv_classes.quick_push (new equiv_class (*ec));
    1525            0 :   constraint *c;
    1526            0 :   m_constraints.reserve (other.m_constraints.length ());
    1527            0 :   FOR_EACH_VEC_ELT (other.m_constraints, i, c)
    1528            0 :     m_constraints.quick_push (*c);
    1529            0 :   for (const auto &iter : other.m_bounded_ranges_constraints)
    1530            0 :     m_bounded_ranges_constraints.quick_push (iter);
    1531              : 
    1532            0 :   return *this;
    1533              : }
    1534              : 
    1535              : /* Generate a hash value for this constraint_manager.  */
    1536              : 
    1537              : hashval_t
    1538      1174759 : constraint_manager::hash () const
    1539              : {
    1540      1174759 :   inchash::hash hstate;
    1541      1174759 :   int i;
    1542      1174759 :   equiv_class *ec;
    1543      1174759 :   constraint *c;
    1544              : 
    1545      4606310 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1546      3431551 :     hstate.merge_hash (ec->hash ());
    1547      3469604 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    1548      2294845 :     hstate.merge_hash (c->hash ());
    1549      1215623 :   for (const auto &iter : m_bounded_ranges_constraints)
    1550        14518 :     iter.add_to_hash (&hstate);
    1551      1174759 :   return hstate.end ();
    1552              : }
    1553              : 
    1554              : /* Equality operator for constraint_manager.  */
    1555              : 
    1556              : bool
    1557       384456 : constraint_manager::operator== (const constraint_manager &other) const
    1558              : {
    1559       871645 :   if (m_equiv_classes.length () != other.m_equiv_classes.length ())
    1560              :     return false;
    1561       826243 :   if (m_constraints.length () != other.m_constraints.length ())
    1562              :     return false;
    1563       380049 :   if (m_bounded_ranges_constraints.length ()
    1564       384432 :       != other.m_bounded_ranges_constraints.length ())
    1565              :     return false;
    1566              : 
    1567              :   int i;
    1568              :   equiv_class *ec;
    1569              : 
    1570      1483730 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1571      1103994 :     if (!(*ec == *other.m_equiv_classes[i]))
    1572              :       return false;
    1573              : 
    1574              :   constraint *c;
    1575              : 
    1576      1119211 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    1577       739487 :     if (!(*c == other.m_constraints[i]))
    1578              :       return false;
    1579              : 
    1580       384506 :   for (unsigned i = 0; i < m_bounded_ranges_constraints.length (); i++)
    1581              :     {
    1582         4829 :       if (m_bounded_ranges_constraints[i]
    1583         9658 :           != other.m_bounded_ranges_constraints[i])
    1584              :         return false;
    1585              :     }
    1586              : 
    1587              :   return true;
    1588              : }
    1589              : 
    1590              : /* Print this constraint_manager to PP (which must support %E for trees).  */
    1591              : 
    1592              : void
    1593            0 : constraint_manager::print (pretty_printer *pp) const
    1594              : {
    1595            0 :   pp_string (pp, "{");
    1596            0 :   int i;
    1597            0 :   equiv_class *ec;
    1598            0 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1599              :     {
    1600            0 :       if (i > 0)
    1601            0 :         pp_string (pp, ", ");
    1602            0 :       equiv_class_id (i).print (pp);
    1603            0 :       pp_string (pp, ": ");
    1604            0 :       ec->print (pp);
    1605              :     }
    1606            0 :   pp_string (pp, "  |  ");
    1607            0 :   constraint *c;
    1608            0 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    1609              :     {
    1610            0 :       if (i > 0)
    1611            0 :         pp_string (pp, " && ");
    1612            0 :       c->print (pp, *this);
    1613              :     }
    1614            0 :   if (m_bounded_ranges_constraints.length ())
    1615              :     {
    1616            0 :       pp_string (pp, "  |  ");
    1617            0 :       i = 0;
    1618            0 :       for (const auto &iter : m_bounded_ranges_constraints)
    1619              :         {
    1620            0 :           if (i > 0)
    1621            0 :             pp_string (pp, " && ");
    1622            0 :           iter.print (pp, *this);
    1623            0 :           i++;
    1624              :         }
    1625              :     }
    1626            0 :   pp_printf (pp, "}");
    1627            0 : }
    1628              : 
    1629              : /* Dump a representation of this constraint_manager to PP
    1630              :    (which must support %E for trees).  */
    1631              : 
    1632              : void
    1633            0 : constraint_manager::dump_to_pp (pretty_printer *pp, bool multiline) const
    1634              : {
    1635            0 :   if (multiline)
    1636            0 :     pp_string (pp, "  ");
    1637            0 :   pp_string (pp, "equiv classes:");
    1638            0 :   if (multiline)
    1639            0 :     pp_newline (pp);
    1640              :   else
    1641            0 :     pp_string (pp, " {");
    1642            0 :   int i;
    1643            0 :   equiv_class *ec;
    1644            0 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1645              :     {
    1646            0 :       if (multiline)
    1647            0 :         pp_string (pp, "    ");
    1648            0 :       else if (i > 0)
    1649            0 :         pp_string (pp, ", ");
    1650            0 :       equiv_class_id (i).print (pp);
    1651            0 :       pp_string (pp, ": ");
    1652            0 :       ec->print (pp);
    1653            0 :       if (multiline)
    1654            0 :         pp_newline (pp);
    1655              :     }
    1656            0 :   if (multiline)
    1657            0 :     pp_string (pp, "  ");
    1658              :   else
    1659            0 :     pp_string (pp, "}");
    1660            0 :   pp_string (pp, "constraints:");
    1661            0 :   if (multiline)
    1662            0 :     pp_newline (pp);
    1663              :   else
    1664            0 :     pp_string (pp, "{");
    1665            0 :   constraint *c;
    1666            0 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    1667              :     {
    1668            0 :       if (multiline)
    1669            0 :         pp_string (pp, "    ");
    1670            0 :       pp_printf (pp, "%i: ", i);
    1671            0 :       c->print (pp, *this);
    1672            0 :       if (multiline)
    1673            0 :         pp_newline (pp);
    1674              :     }
    1675            0 :   if (!multiline)
    1676            0 :     pp_string (pp, "}");
    1677            0 :   if (m_bounded_ranges_constraints.length ())
    1678              :     {
    1679            0 :       if (multiline)
    1680            0 :         pp_string (pp, "  ");
    1681            0 :       pp_string (pp, "ranges:");
    1682            0 :       if (multiline)
    1683            0 :         pp_newline (pp);
    1684              :       else
    1685            0 :         pp_string (pp, "{");
    1686            0 :       i = 0;
    1687            0 :       for (const auto &iter : m_bounded_ranges_constraints)
    1688              :         {
    1689            0 :           if (multiline)
    1690            0 :             pp_string (pp, "    ");
    1691            0 :           else if (i > 0)
    1692            0 :             pp_string (pp, " && ");
    1693            0 :           iter.print (pp, *this);
    1694            0 :           if (multiline)
    1695            0 :             pp_newline (pp);
    1696            0 :           i++;
    1697              :         }
    1698            0 :       if (!multiline)
    1699            0 :         pp_string (pp, "}");
    1700              :       }
    1701            0 : }
    1702              : 
    1703              : /* Dump a multiline representation of this constraint_manager to FP.  */
    1704              : 
    1705              : void
    1706            0 : constraint_manager::dump (FILE *fp) const
    1707              : {
    1708            0 :   tree_dump_pretty_printer pp (fp);
    1709            0 :   dump_to_pp (&pp, true);
    1710            0 : }
    1711              : 
    1712              : /* Dump a multiline representation of this constraint_manager to stderr.  */
    1713              : 
    1714              : DEBUG_FUNCTION void
    1715            0 : constraint_manager::dump () const
    1716              : {
    1717            0 :   dump (stderr);
    1718            0 : }
    1719              : 
    1720              : /* Dump a multiline representation of CM to stderr.  */
    1721              : 
    1722              : DEBUG_FUNCTION void
    1723            0 : debug (const constraint_manager &cm)
    1724              : {
    1725            0 :   cm.dump ();
    1726            0 : }
    1727              : 
    1728              : /* Return a new json::object of the form
    1729              :    {"ecs" : array of objects, one per equiv_class
    1730              :     "constraints" : array of objects, one per constraint}.  */
    1731              : 
    1732              : std::unique_ptr<json::object>
    1733           19 : constraint_manager::to_json () const
    1734              : {
    1735           19 :   auto cm_obj = std::make_unique<json::object> ();
    1736              : 
    1737              :   /* Equivalence classes.  */
    1738           19 :   {
    1739           19 :     auto ec_arr = std::make_unique<json::array> ();
    1740           62 :     for (const equiv_class *ec : m_equiv_classes)
    1741           19 :       ec_arr->append (ec->to_json ());
    1742           19 :     cm_obj->set ("ecs", std::move (ec_arr));
    1743           19 :   }
    1744              : 
    1745              :   /* Constraints.  */
    1746           19 :   {
    1747           19 :     auto con_arr = std::make_unique<json::array> ();
    1748           40 :     for (const constraint &c : m_constraints)
    1749            7 :       con_arr->append (c.to_json ());
    1750           19 :     cm_obj->set ("constraints", std::move (con_arr));
    1751           19 :   }
    1752              : 
    1753              :   /* m_bounded_ranges_constraints.  */
    1754           19 :   {
    1755           19 :     auto con_arr = std::make_unique<json::array> ();
    1756           19 :     for (const auto &c : m_bounded_ranges_constraints)
    1757            0 :       con_arr->append (c.to_json ());
    1758           19 :     cm_obj->set ("bounded_ranges_constraints", std::move (con_arr));
    1759           19 :   }
    1760              : 
    1761           19 :   return cm_obj;
    1762              : }
    1763              : 
    1764              : std::unique_ptr<text_art::tree_widget>
    1765          720 : constraint_manager::make_dump_widget (const text_art::dump_widget_info &dwi) const
    1766              : {
    1767          720 :   using text_art::tree_widget;
    1768          720 :   std::unique_ptr<tree_widget> cm_widget
    1769          720 :     (tree_widget::make (dwi, "Constraints"));
    1770              : 
    1771              :   /* Equivalence classes.  */
    1772          720 :   unsigned i;
    1773          720 :   equiv_class *ec;
    1774         2699 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1775         2518 :     cm_widget->add_child (ec->make_dump_widget (dwi, i));
    1776              : 
    1777              :   /* Constraints.  */
    1778         2282 :   for (const constraint &c : m_constraints)
    1779         1564 :     cm_widget->add_child (c.make_dump_widget (dwi, *this));
    1780              : 
    1781              :   /* m_bounded_ranges_constraints.  */
    1782          915 :   for (const auto &brc : m_bounded_ranges_constraints)
    1783          130 :     cm_widget->add_child (brc.make_dump_widget (dwi));
    1784              : 
    1785          720 :   if (cm_widget->get_num_children () == 0)
    1786          243 :     return nullptr;
    1787              : 
    1788          477 :   return cm_widget;
    1789          720 : }
    1790              : 
    1791              : /* Attempt to add the constraint LHS OP RHS to this constraint_manager.
    1792              :    Return true if the constraint could be added (or is already true).
    1793              :    Return false if the constraint contradicts existing knowledge.  */
    1794              : 
    1795              : bool
    1796       369485 : constraint_manager::add_constraint (const svalue *lhs,
    1797              :                                      enum tree_code op,
    1798              :                                      const svalue *rhs)
    1799              : {
    1800       369485 :   lhs = lhs->unwrap_any_unmergeable ();
    1801       369485 :   rhs = rhs->unwrap_any_unmergeable ();
    1802              : 
    1803              :   /* Nothing can be known about unknown/poisoned values.  */
    1804       369485 :   if (!lhs->can_have_associated_state_p ()
    1805       369485 :       || !rhs->can_have_associated_state_p ())
    1806              :     /* Not a contradiction.  */
    1807              :     return true;
    1808              : 
    1809              :   /* Check the conditions on svalues.  */
    1810       354237 :   {
    1811       354237 :     tristate t_cond = eval_condition (lhs, op, rhs);
    1812              : 
    1813              :     /* If we already have the condition, do nothing.  */
    1814       354237 :     if (t_cond.is_true ())
    1815       369485 :       return true;
    1816              : 
    1817              :     /* Reject a constraint that would contradict existing knowledge, as
    1818              :        unsatisfiable.  */
    1819       154694 :     if (t_cond.is_false ())
    1820              :       return false;
    1821              :   }
    1822              : 
    1823       152890 :   equiv_class_id lhs_ec_id = get_or_add_equiv_class (lhs);
    1824       152890 :   equiv_class_id rhs_ec_id = get_or_add_equiv_class (rhs);
    1825              : 
    1826              :   /* Check the stronger conditions on ECs.  */
    1827       152890 :   {
    1828       152890 :     tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
    1829              : 
    1830              :     /* Discard constraints that are already known.  */
    1831       152890 :     if (t.is_true ())
    1832       369485 :       return true;
    1833              : 
    1834              :     /* Reject unsatisfiable constraints.  */
    1835       152890 :     if (t.is_false ())
    1836              :       return false;
    1837              :   }
    1838              : 
    1839              :   /* If adding
    1840              :        (SVAL + OFFSET) > CST,
    1841              :      then that can imply:
    1842              :        SVAL > (CST - OFFSET).  */
    1843       152890 :   if (const binop_svalue *lhs_binop = lhs->dyn_cast_binop_svalue ())
    1844        10035 :     if (tree rhs_cst = rhs->maybe_get_constant ())
    1845         9445 :       if (tree offset = lhs_binop->get_arg1 ()->maybe_get_constant ())
    1846         4840 :         if ((op == GT_EXPR || op == LT_EXPR
    1847         4437 :              || op == GE_EXPR || op == LE_EXPR)
    1848         5401 :             && lhs_binop->get_op () == PLUS_EXPR)
    1849              :           {
    1850          857 :             tree offset_of_cst = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs_cst),
    1851              :                                               rhs_cst, offset);
    1852          857 :             const svalue *implied_lhs = lhs_binop->get_arg0 ();
    1853          857 :             enum tree_code implied_op = op;
    1854          857 :             const svalue *implied_rhs
    1855          857 :               = m_mgr->get_or_create_constant_svalue (offset_of_cst);
    1856          857 :             if (!add_constraint (implied_lhs, implied_op, implied_rhs))
    1857              :               return false;
    1858              :             /* The above add_constraint could lead to EC merger, so we need
    1859              :                to refresh the EC IDs.  */
    1860          769 :             lhs_ec_id = get_or_add_equiv_class (lhs);
    1861          769 :             rhs_ec_id = get_or_add_equiv_class (rhs);
    1862              :           }
    1863              : 
    1864       152802 :   add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
    1865       152802 :   return true;
    1866              : }
    1867              : 
    1868              : /* Attempt to add the constraint LHS_EC_ID OP RHS_EC_ID to this
    1869              :    constraint_manager.
    1870              :    Return true if the constraint could be added (or is already true).
    1871              :    Return false if the constraint contradicts existing knowledge.  */
    1872              : 
    1873              : bool
    1874          678 : constraint_manager::add_constraint (equiv_class_id lhs_ec_id,
    1875              :                                      enum tree_code op,
    1876              :                                      equiv_class_id rhs_ec_id)
    1877              : {
    1878          678 :   tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
    1879              : 
    1880              :   /* Discard constraints that are already known.  */
    1881          678 :   if (t.is_true ())
    1882              :     return true;
    1883              : 
    1884              :   /* Reject unsatisfiable constraints.  */
    1885          549 :   if (t.is_false ())
    1886              :     return false;
    1887              : 
    1888          549 :   add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
    1889          549 :   return true;
    1890              : }
    1891              : 
    1892              : /* Add the constraint LHS_EC_ID OP RHS_EC_ID to this constraint_manager,
    1893              :    where the constraint has already been checked for being "unknown".  */
    1894              : 
    1895              : void
    1896       153351 : constraint_manager::add_unknown_constraint (equiv_class_id lhs_ec_id,
    1897              :                                              enum tree_code op,
    1898              :                                              equiv_class_id rhs_ec_id)
    1899              : {
    1900       153351 :   gcc_assert (lhs_ec_id != rhs_ec_id);
    1901              : 
    1902              :   /* For now, simply accumulate constraints, without attempting any further
    1903              :      optimization.  */
    1904       153351 :   switch (op)
    1905              :     {
    1906        23851 :     case EQ_EXPR:
    1907        23851 :       {
    1908              :         /* Merge rhs_ec into lhs_ec.  */
    1909        23851 :         equiv_class &lhs_ec_obj = lhs_ec_id.get_obj (*this);
    1910        23851 :         const equiv_class &rhs_ec_obj = rhs_ec_id.get_obj (*this);
    1911              : 
    1912        23851 :         int i;
    1913        23851 :         const svalue *sval;
    1914        73748 :         FOR_EACH_VEC_ELT (rhs_ec_obj.m_vars, i, sval)
    1915        26046 :           lhs_ec_obj.add (sval);
    1916              : 
    1917        23851 :         if (rhs_ec_obj.m_constant)
    1918              :           {
    1919        16276 :             lhs_ec_obj.m_constant = rhs_ec_obj.m_constant;
    1920        16276 :             lhs_ec_obj.m_cst_sval = rhs_ec_obj.m_cst_sval;
    1921              :           }
    1922              : 
    1923              :         /* Drop rhs equivalence class, overwriting it with the
    1924              :            final ec (which might be the same one).  */
    1925        47702 :         equiv_class_id final_ec_id = m_equiv_classes.length () - 1;
    1926        23851 :         equiv_class *old_ec = m_equiv_classes[rhs_ec_id.m_idx];
    1927        23851 :         equiv_class *final_ec = m_equiv_classes.pop ();
    1928        23851 :         if (final_ec != old_ec)
    1929         4999 :           m_equiv_classes[rhs_ec_id.m_idx] = final_ec;
    1930        47702 :         delete old_ec;
    1931        23851 :         if (lhs_ec_id == final_ec_id)
    1932         4933 :           lhs_ec_id = rhs_ec_id;
    1933              : 
    1934              :         /* Update the constraints.  */
    1935        23851 :         constraint *c;
    1936        70759 :         FOR_EACH_VEC_ELT (m_constraints, i, c)
    1937              :           {
    1938              :             /* Update references to the rhs_ec so that
    1939              :                they refer to the lhs_ec.  */
    1940        37876 :             if (c->m_lhs == rhs_ec_id)
    1941          278 :               c->m_lhs = lhs_ec_id;
    1942        37876 :             if (c->m_rhs == rhs_ec_id)
    1943        11001 :               c->m_rhs = lhs_ec_id;
    1944              : 
    1945              :             /* Renumber all constraints that refer to the final rhs_ec
    1946              :                to the old rhs_ec, where the old final_ec now lives.  */
    1947        37876 :             if (c->m_lhs == final_ec_id)
    1948           89 :               c->m_lhs = rhs_ec_id;
    1949        37876 :             if (c->m_rhs == final_ec_id)
    1950           19 :               c->m_rhs = rhs_ec_id;
    1951              :           }
    1952              :         bounded_ranges_constraint *brc;
    1953        24718 :         FOR_EACH_VEC_ELT (m_bounded_ranges_constraints, i, brc)
    1954              :           {
    1955          867 :             if (brc->m_ec_id == rhs_ec_id)
    1956            0 :               brc->m_ec_id = lhs_ec_id;
    1957          867 :             if (brc->m_ec_id == final_ec_id)
    1958            3 :               brc->m_ec_id = rhs_ec_id;
    1959              :           }
    1960              : 
    1961              :         /* We may now have self-comparisons due to the merger; these
    1962              :            constraints should be removed.  */
    1963              :         unsigned read_index, write_index;
    1964        61727 :         VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
    1965              :                                (c->m_lhs == c->m_rhs));
    1966              :       }
    1967              :       break;
    1968         2619 :     case GE_EXPR:
    1969         2619 :       add_constraint_internal (rhs_ec_id, CONSTRAINT_LE, lhs_ec_id);
    1970         2619 :       break;
    1971         7458 :     case LE_EXPR:
    1972         7458 :       add_constraint_internal (lhs_ec_id, CONSTRAINT_LE, rhs_ec_id);
    1973         7458 :       break;
    1974       106805 :     case NE_EXPR:
    1975       106805 :       add_constraint_internal (lhs_ec_id, CONSTRAINT_NE, rhs_ec_id);
    1976       106805 :       break;
    1977         2747 :     case GT_EXPR:
    1978         2747 :       add_constraint_internal (rhs_ec_id, CONSTRAINT_LT, lhs_ec_id);
    1979         2747 :       break;
    1980         9871 :     case LT_EXPR:
    1981         9871 :       add_constraint_internal (lhs_ec_id, CONSTRAINT_LT, rhs_ec_id);
    1982         9871 :       break;
    1983              :     default:
    1984              :       /* do nothing.  */
    1985              :       break;
    1986              :     }
    1987       153351 :   validate ();
    1988       153351 : }
    1989              : 
    1990              : /* Subroutine of constraint_manager::add_constraint, for handling all
    1991              :    operations other than equality (for which equiv classes are merged).  */
    1992              : 
    1993              : void
    1994       129500 : constraint_manager::add_constraint_internal (equiv_class_id lhs_id,
    1995              :                                              enum constraint_op c_op,
    1996              :                                              equiv_class_id rhs_id)
    1997              : {
    1998       211982 :   if (m_constraints.length () >= (unsigned)param_analyzer_max_constraints)
    1999       125369 :     return;
    2000              : 
    2001       129378 :   constraint new_c (lhs_id, c_op, rhs_id);
    2002              : 
    2003              :   /* Remove existing constraints that would be implied by the
    2004              :      new constraint.  */
    2005       129378 :   unsigned read_index, write_index;
    2006       129378 :   constraint *c;
    2007       400679 :   VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
    2008       129378 :                          (c->implied_by (new_c, *this)));
    2009              : 
    2010              :   /* Add the constraint.  */
    2011       129378 :   m_constraints.safe_push (new_c);
    2012              : 
    2013              :   /* We don't yet update m_bounded_ranges_constraints here yet.  */
    2014              : 
    2015       129378 :   if (!flag_analyzer_transitivity)
    2016              :     return;
    2017              : 
    2018         4229 :   if (c_op != CONSTRAINT_NE)
    2019              :     {
    2020              :       /* The following can potentially add EQ_EXPR facts, which could lead
    2021              :          to ECs being merged, which would change the meaning of the EC IDs.
    2022              :          Hence we need to do this via representatives.  */
    2023         2529 :       const svalue *lhs = lhs_id.get_obj (*this).get_representative ();
    2024         2529 :       const svalue *rhs = rhs_id.get_obj (*this).get_representative ();
    2025              : 
    2026              :       /* We have LHS </<= RHS */
    2027              : 
    2028              :       /* Handle transitivity of ordering by adding additional constraints
    2029              :          based on what we already knew.
    2030              : 
    2031              :          So if we have already have:
    2032              :            (a < b)
    2033              :            (c < d)
    2034              :          Then adding:
    2035              :            (b < c)
    2036              :          will also add:
    2037              :            (a < c)
    2038              :            (b < d)
    2039              :          We need to recurse to ensure we also add:
    2040              :            (a < d).
    2041              :          We call the checked add_constraint to avoid adding constraints
    2042              :          that are already present.  Doing so also ensures termination
    2043              :          in the case of cycles.
    2044              : 
    2045              :          We also check for single-element ranges, adding EQ_EXPR facts
    2046              :          where we discover them.  For example 3 < x < 5 implies
    2047              :          that x == 4 (if x is an integer).  */
    2048        15816 :       for (unsigned i = 0; i < m_constraints.length (); i++)
    2049              :         {
    2050         9156 :           const constraint *other = &m_constraints[i];
    2051         9156 :           if (other->is_ordering_p ())
    2052              :             {
    2053              :               /* Refresh the EC IDs, in case any mergers have happened.  */
    2054         7025 :               lhs_id = get_or_add_equiv_class (lhs);
    2055         7025 :               rhs_id = get_or_add_equiv_class (rhs);
    2056              : 
    2057         7025 :               tree lhs_const = lhs_id.get_obj (*this).m_constant;
    2058         7025 :               tree rhs_const = rhs_id.get_obj (*this).m_constant;
    2059         7025 :               tree other_lhs_const
    2060         7025 :                 = other->m_lhs.get_obj (*this).m_constant;
    2061         7025 :               tree other_rhs_const
    2062         7025 :                 = other->m_rhs.get_obj (*this).m_constant;
    2063              : 
    2064              :               /* We have "LHS </<= RHS" and "other.lhs </<= other.rhs".  */
    2065              : 
    2066              :               /* If we have LHS </<= RHS and RHS </<= LHS, then we have a
    2067              :                  cycle.  */
    2068         7025 :               if (rhs_id == other->m_lhs
    2069         7025 :                   && other->m_rhs == lhs_id)
    2070              :                 {
    2071              :                   /* We must have equality for this to be possible.  */
    2072           18 :                   gcc_assert (c_op == CONSTRAINT_LE
    2073              :                               && other->m_op == CONSTRAINT_LE);
    2074           18 :                   add_constraint (lhs_id, EQ_EXPR, rhs_id);
    2075              :                   /* Adding an equality will merge the two ECs and potentially
    2076              :                      reorganize the constraints.  Stop iterating.  */
    2077           18 :                   return;
    2078              :                 }
    2079              :               /* Otherwise, check for transitivity.  */
    2080         7007 :               if (rhs_id == other->m_lhs)
    2081              :                 {
    2082              :                   /* With RHS == other.lhs, we have:
    2083              :                      "LHS </<= (RHS, other.lhs) </<= other.rhs"
    2084              :                      and thus this implies "LHS </<= other.rhs".  */
    2085              : 
    2086              :                   /* Do we have a tightly-constrained range?  */
    2087          174 :                   if (lhs_const
    2088          174 :                       && !rhs_const
    2089           48 :                       && other_rhs_const)
    2090              :                     {
    2091           48 :                       range r (bound (lhs_const, c_op == CONSTRAINT_LE),
    2092              :                                bound (other_rhs_const,
    2093           48 :                                       other->m_op == CONSTRAINT_LE));
    2094           48 :                       if (tree constant = r.constrained_to_single_element ())
    2095              :                         {
    2096           20 :                           const svalue *cst_sval
    2097           20 :                             = m_mgr->get_or_create_constant_svalue (constant);
    2098           20 :                           add_constraint
    2099           20 :                             (rhs_id, EQ_EXPR,
    2100              :                              get_or_add_equiv_class (cst_sval));
    2101           20 :                           return;
    2102              :                         }
    2103              :                     }
    2104              : 
    2105              :                   /* Otherwise, add the constraint implied by transitivity.  */
    2106          144 :                   enum tree_code new_op
    2107           10 :                     = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
    2108          154 :                        ? LE_EXPR : LT_EXPR);
    2109          154 :                   add_constraint (lhs_id, new_op, other->m_rhs);
    2110              :                 }
    2111         6833 :               else if (other->m_rhs == lhs_id)
    2112              :                 {
    2113              :                   /* With other.rhs == LHS, we have:
    2114              :                      "other.lhs </<= (other.rhs, LHS) </<= RHS"
    2115              :                      and thus this implies "other.lhs </<= RHS".  */
    2116              : 
    2117              :                   /* Do we have a tightly-constrained range?  */
    2118          486 :                   if (other_lhs_const
    2119          486 :                       && !lhs_const
    2120          257 :                       && rhs_const)
    2121              :                     {
    2122           72 :                       range r (bound (other_lhs_const,
    2123           72 :                                       other->m_op == CONSTRAINT_LE),
    2124              :                                bound (rhs_const,
    2125           72 :                                       c_op == CONSTRAINT_LE));
    2126           72 :                       if (tree constant = r.constrained_to_single_element ())
    2127              :                         {
    2128           60 :                           const svalue *cst_sval
    2129           60 :                             = m_mgr->get_or_create_constant_svalue (constant);
    2130           60 :                           add_constraint
    2131           60 :                             (lhs_id, EQ_EXPR,
    2132              :                              get_or_add_equiv_class (cst_sval));
    2133           60 :                           return;
    2134              :                         }
    2135              :                     }
    2136              : 
    2137              :                   /* Otherwise, add the constraint implied by transitivity.  */
    2138          417 :                   enum tree_code new_op
    2139          394 :                     = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
    2140          426 :                        ? LE_EXPR : LT_EXPR);
    2141          426 :                   add_constraint (other->m_lhs, new_op, rhs_id);
    2142              :                 }
    2143              :             }
    2144              :         }
    2145              :     }
    2146              : }
    2147              : 
    2148              : /* Attempt to add the constraint that SVAL is within RANGES to this
    2149              :    constraint_manager.
    2150              : 
    2151              :    Return true if the constraint was successfully added (or is already
    2152              :    known to be true).
    2153              :    Return false if the constraint contradicts existing knowledge.  */
    2154              : 
    2155              : bool
    2156         7886 : constraint_manager::add_bounded_ranges (const svalue *sval,
    2157              :                                         const bounded_ranges *ranges)
    2158              : {
    2159              :   /* If RANGES is just a singleton, convert this to adding the constraint:
    2160              :      "SVAL == {the singleton}".  */
    2161         7886 :   if (ranges->get_count () == 1
    2162        14264 :       && ranges->get_range (0).singleton_p ())
    2163              :     {
    2164         6117 :       tree range_cst = ranges->get_range (0).m_lower;
    2165         6117 :       const svalue *range_sval
    2166         6117 :         = m_mgr->get_or_create_constant_svalue (range_cst);
    2167         6117 :       return add_constraint (sval, EQ_EXPR, range_sval);
    2168              :     }
    2169              : 
    2170         1769 :   sval = sval->unwrap_any_unmergeable ();
    2171              : 
    2172              :   /* Nothing can be known about unknown/poisoned values.  */
    2173         1769 :   if (!sval->can_have_associated_state_p ())
    2174              :     /* Not a contradiction.  */
    2175              :     return true;
    2176              : 
    2177              :   /* If SVAL is a constant, then we can look at RANGES directly.  */
    2178         1693 :   if (tree cst = sval->maybe_get_constant ())
    2179              :     {
    2180              :       /* If the ranges contain CST, then it's a successful no-op;
    2181              :          otherwise it's a contradiction.  */
    2182          115 :       return ranges->contain_p (cst);
    2183              :     }
    2184              : 
    2185         1578 :   equiv_class_id ec_id = get_or_add_equiv_class (sval);
    2186              : 
    2187              :   /* If the EC has a constant, it's either true or false.  */
    2188         1578 :   const equiv_class &ec = ec_id.get_obj (*this);
    2189         1578 :   if (tree ec_cst = ec.get_any_constant ())
    2190              :     {
    2191           16 :       if (ranges->contain_p (ec_cst))
    2192              :         /* We already have SVAL == EC_CST, within RANGES, so
    2193              :            we can discard RANGES and succeed.  */
    2194              :         return true;
    2195              :       else
    2196              :         /* We already have SVAL == EC_CST, not within RANGES, so
    2197              :            we can reject RANGES as a contradiction.  */
    2198              :         return false;
    2199              :     }
    2200              : 
    2201              :   /* We have at most one per ec_id.  */
    2202              :   /* Iterate through each range in RANGES.  */
    2203         2633 :   for (auto iter : m_bounded_ranges_constraints)
    2204              :     {
    2205          497 :       if (iter.m_ec_id == ec_id)
    2206              :         {
    2207              :           /* Update with intersection, or fail if empty.  */
    2208           28 :           bounded_ranges_manager *mgr = get_range_manager ();
    2209           28 :           const bounded_ranges *intersection
    2210           28 :             = mgr->get_or_create_intersection (iter.m_ranges, ranges);
    2211           28 :           if (intersection->empty_p ())
    2212              :             {
    2213              :               /* No intersection; fail.  */
    2214         7886 :               return false;
    2215              :             }
    2216              :           else
    2217              :             {
    2218              :               /* Update with intersection; succeed.  */
    2219           25 :               iter.m_ranges = intersection;
    2220           25 :               validate ();
    2221           25 :               return true;
    2222              :             }
    2223              :         }
    2224              :     }
    2225         1534 :   m_bounded_ranges_constraints.safe_push
    2226         1534 :     (bounded_ranges_constraint (ec_id, ranges));
    2227              : 
    2228         1534 :   validate ();
    2229              : 
    2230         1534 :   return true;
    2231              : }
    2232              : 
    2233              : /* Look for SVAL within the equivalence classes of this constraint_manager;
    2234              :    if found, return true, writing the id to *OUT if OUT is non-NULL,
    2235              :    otherwise return false.  */
    2236              : 
    2237              : bool
    2238      1515413 : constraint_manager::get_equiv_class_by_svalue (const svalue *sval,
    2239              :                                                equiv_class_id *out) const
    2240              : {
    2241              :   /* TODO: should we have a map, rather than these searches?  */
    2242      1515413 :   int i;
    2243      1515413 :   equiv_class *ec;
    2244     10435085 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    2245              :     {
    2246              :       int j;
    2247              :       const svalue *iv;
    2248     13600893 :       FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
    2249      5434203 :         if (iv == sval)
    2250              :           {
    2251       752982 :             if (out)
    2252       751020 :               *out = equiv_class_id (i);
    2253      1515413 :             return true;
    2254              :           }
    2255              :     }
    2256              :   return false;
    2257              : }
    2258              : 
    2259              : /* Tries to find a svalue inside another svalue.  */
    2260              : 
    2261              : class sval_finder : public visitor
    2262              : {
    2263              : public:
    2264          220 :   sval_finder (const svalue *query) : m_query (query), m_found (false)
    2265              :   {
    2266              :   }
    2267              : 
    2268          451 :   bool found_query_p ()
    2269              :   {
    2270          451 :     return m_found;
    2271              :   }
    2272              : 
    2273          119 :   void visit_pointer_svalue (const pointer_svalue *sval)
    2274              :   {
    2275          119 :     m_found |= m_query == sval;
    2276          119 :   }
    2277              : 
    2278          170 :   void visit_constant_svalue (const constant_svalue  *sval)
    2279              :   {
    2280          170 :     m_found |= m_query == sval;
    2281          170 :   }
    2282              : 
    2283            0 :   void visit_unknown_svalue (const unknown_svalue  *sval)
    2284              :   {
    2285            0 :     m_found |= m_query == sval;
    2286            0 :   }
    2287              : 
    2288            0 :   void visit_poisoned_svalue (const poisoned_svalue  *sval)
    2289              :   {
    2290            0 :     m_found |= m_query == sval;
    2291            0 :   }
    2292              : 
    2293            0 :   void visit_setjmp_svalue (const setjmp_svalue  *sval)
    2294              :   {
    2295            0 :     m_found |= m_query == sval;
    2296            0 :   }
    2297              : 
    2298          210 :   void visit_initial_svalue (const initial_svalue  *sval)
    2299              :   {
    2300          210 :     m_found |= m_query == sval;
    2301          210 :   }
    2302              : 
    2303            6 :   void visit_unaryop_svalue (const unaryop_svalue  *sval)
    2304              :   {
    2305            6 :     m_found |= m_query == sval;
    2306            6 :   }
    2307              : 
    2308           68 :   void visit_binop_svalue (const binop_svalue  *sval)
    2309              :   {
    2310           68 :     m_found |= m_query == sval;
    2311           68 :   }
    2312              : 
    2313            0 :   void visit_unmergeable_svalue (const unmergeable_svalue  *sval)
    2314              :   {
    2315            0 :     m_found |= m_query == sval;
    2316            0 :   }
    2317              : 
    2318            0 :   void visit_placeholder_svalue (const placeholder_svalue  *sval)
    2319              :   {
    2320            0 :     m_found |= m_query == sval;
    2321            0 :   }
    2322              : 
    2323            0 :   void visit_widening_svalue (const widening_svalue  *sval)
    2324              :   {
    2325            0 :     m_found |= m_query == sval;
    2326            0 :   }
    2327              : 
    2328            0 :   void visit_asm_output_svalue (const asm_output_svalue  *sval)
    2329              :   {
    2330            0 :     m_found |= m_query == sval;
    2331            0 :   }
    2332              : 
    2333            0 :   void visit_const_fn_result_svalue (const const_fn_result_svalue  *sval)
    2334              :   {
    2335            0 :     m_found |= m_query == sval;
    2336            0 :   }
    2337              : 
    2338              : private:
    2339              :   const svalue *m_query;
    2340              :   bool m_found;
    2341              : };
    2342              : 
    2343              : /* Returns true if SVAL is constrained.  */
    2344              : 
    2345              : bool
    2346          220 : constraint_manager::sval_constrained_p (const svalue *sval) const
    2347              : {
    2348          220 :   int i;
    2349          220 :   equiv_class *ec;
    2350          220 :   sval_finder finder (sval);
    2351         1036 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    2352              :     {
    2353              :       int j;
    2354              :       const svalue *iv;
    2355         1213 :       FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
    2356              :         {
    2357          451 :           iv->accept (&finder);
    2358          451 :           if (finder.found_query_p ())
    2359          220 :             return true;
    2360              :         }
    2361              :     }
    2362              :   return false;
    2363              : }
    2364              : 
    2365              : /* Ensure that SVAL has an equivalence class within this constraint_manager;
    2366              :    return the ID of the class.  */
    2367              : 
    2368              : equiv_class_id
    2369       356020 : constraint_manager::get_or_add_equiv_class (const svalue *sval)
    2370              : {
    2371       356020 :   equiv_class_id result (-1);
    2372              : 
    2373       356020 :   gcc_assert (sval->can_have_associated_state_p ());
    2374              : 
    2375              :   /* Convert all NULL pointers to (void *) to avoid state explosions
    2376              :      involving all of the various (foo *)NULL vs (bar *)NULL.  */
    2377       356020 :   if (sval->get_type ())
    2378       355976 :     if (POINTER_TYPE_P (sval->get_type ()))
    2379       222308 :       if (tree cst = sval->maybe_get_constant ())
    2380        95825 :         if (zerop (cst))
    2381        95825 :           sval = m_mgr->get_or_create_constant_svalue (null_pointer_node);
    2382              : 
    2383              :   /* Try svalue match.  */
    2384       356020 :   if (get_equiv_class_by_svalue (sval, &result))
    2385       101481 :     return result;
    2386              : 
    2387              :   /* Try equality of constants.  */
    2388       254539 :   if (tree cst = sval->maybe_get_constant ())
    2389              :     {
    2390              :       int i;
    2391              :       equiv_class *ec;
    2392       270769 :       FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    2393       189730 :         if (ec->m_constant
    2394       245612 :             && types_compatible_p (TREE_TYPE (cst),
    2395        55882 :                                    TREE_TYPE (ec->m_constant)))
    2396              :           {
    2397        26651 :             tree eq = fold_binary (EQ_EXPR, boolean_type_node,
    2398              :                                    cst, ec->m_constant);
    2399        26651 :             if (eq == boolean_true_node)
    2400              :               {
    2401           17 :                 ec->add (sval);
    2402           17 :                 return equiv_class_id (i);
    2403              :               }
    2404              :           }
    2405              :     }
    2406              : 
    2407              : 
    2408              :   /* Not found.  */
    2409       254522 :   equiv_class *new_ec = new equiv_class ();
    2410       254522 :   new_ec->add (sval);
    2411       254522 :   m_equiv_classes.safe_push (new_ec);
    2412              : 
    2413       509044 :   equiv_class_id new_id (m_equiv_classes.length () - 1);
    2414              : 
    2415       254522 :   return new_id;
    2416              : }
    2417              : 
    2418              : /* Evaluate the condition LHS_EC OP RHS_EC.  */
    2419              : 
    2420              : tristate
    2421       405291 : constraint_manager::eval_condition (equiv_class_id lhs_ec,
    2422              :                                     enum tree_code op,
    2423              :                                     equiv_class_id rhs_ec) const
    2424              : {
    2425       405291 :   if (lhs_ec == rhs_ec)
    2426              :     {
    2427        30307 :       switch (op)
    2428              :         {
    2429        27120 :         case EQ_EXPR:
    2430        27120 :         case GE_EXPR:
    2431        27120 :         case LE_EXPR:
    2432        27120 :           return tristate (tristate::TS_TRUE);
    2433              : 
    2434         3187 :         case NE_EXPR:
    2435         3187 :         case GT_EXPR:
    2436         3187 :         case LT_EXPR:
    2437         3187 :           return tristate (tristate::TS_FALSE);
    2438              :         default:
    2439              :           break;
    2440              :         }
    2441              :     }
    2442              : 
    2443       374984 :   tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ();
    2444       374984 :   tree rhs_const = rhs_ec.get_obj (*this).get_any_constant ();
    2445       374984 :   if (lhs_const && rhs_const)
    2446              :     {
    2447         1250 :       tristate result_for_constants
    2448         1250 :         = compare_constants (lhs_const, op, rhs_const);
    2449         1250 :       if (result_for_constants.is_known ())
    2450         1250 :         return result_for_constants;
    2451              :     }
    2452              : 
    2453       373734 :   enum tree_code swapped_op = swap_tree_comparison (op);
    2454              : 
    2455       373734 :   int i;
    2456       373734 :   constraint *c;
    2457      1482124 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    2458              :     {
    2459       952411 :       if (c->m_lhs == lhs_ec
    2460       952411 :           && c->m_rhs == rhs_ec)
    2461              :         {
    2462       215249 :           tristate result_for_constraint
    2463       215249 :             = eval_constraint_op_for_op (c->m_op, op);
    2464       215249 :           if (result_for_constraint.is_known ())
    2465       214194 :             return result_for_constraint;
    2466              :         }
    2467              :       /* Swapped operands.  */
    2468       738217 :       if (c->m_lhs == rhs_ec
    2469       738217 :           && c->m_rhs == lhs_ec)
    2470              :         {
    2471         4025 :           tristate result_for_constraint
    2472         4025 :             = eval_constraint_op_for_op (c->m_op, swapped_op);
    2473         4025 :           if (result_for_constraint.is_known ())
    2474         3561 :             return result_for_constraint;
    2475              :         }
    2476              :     }
    2477              : 
    2478              :   /* We don't use m_bounded_ranges_constraints here yet.  */
    2479              : 
    2480       155979 :   return tristate (tristate::TS_UNKNOWN);
    2481              : }
    2482              : 
    2483              : range
    2484        13695 : constraint_manager::get_ec_bounds (equiv_class_id ec_id) const
    2485              : {
    2486        13695 :   range result;
    2487              : 
    2488        13695 :   int i;
    2489        13695 :   constraint *c;
    2490        72955 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    2491              :     {
    2492        59260 :       if (c->m_lhs == ec_id)
    2493              :         {
    2494        20675 :           if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
    2495        18701 :             switch (c->m_op)
    2496              :               {
    2497            0 :               default:
    2498            0 :                 gcc_unreachable ();
    2499        16710 :               case CONSTRAINT_NE:
    2500        16710 :                 continue;
    2501              : 
    2502          186 :               case CONSTRAINT_LT:
    2503              :                 /* We have "EC_ID < OTHER_CST".  */
    2504          186 :                 result.add_bound (bound (other_cst, false), bound_kind::upper);
    2505          186 :                 break;
    2506              : 
    2507         1805 :               case CONSTRAINT_LE:
    2508              :                 /* We have "EC_ID <= OTHER_CST".  */
    2509         1805 :                 result.add_bound (bound (other_cst, true), bound_kind::upper);
    2510         1805 :                 break;
    2511              :               }
    2512              :         }
    2513        42550 :       if (c->m_rhs == ec_id)
    2514              :         {
    2515         7414 :           if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
    2516         6845 :             switch (c->m_op)
    2517              :               {
    2518            0 :               default:
    2519            0 :                 gcc_unreachable ();
    2520           24 :               case CONSTRAINT_NE:
    2521           24 :                 continue;
    2522              : 
    2523         6154 :               case CONSTRAINT_LT:
    2524              :                 /* We have "OTHER_CST < EC_ID"
    2525              :                    i.e. "EC_ID > OTHER_CST".  */
    2526         6154 :                 result.add_bound (bound (other_cst, false), bound_kind::lower);
    2527         6154 :                 break;
    2528              : 
    2529          667 :               case CONSTRAINT_LE:
    2530              :                 /* We have "OTHER_CST <= EC_ID"
    2531              :                    i.e. "EC_ID >= OTHER_CST".  */
    2532          667 :                 result.add_bound (bound (other_cst, true), bound_kind::lower);
    2533          667 :                 break;
    2534              :               }
    2535              :         }
    2536              :     }
    2537              : 
    2538        13695 :   return result;
    2539              : }
    2540              : 
    2541              : /* Evaluate the condition LHS_EC OP RHS_CONST, avoiding the creation
    2542              :    of equiv_class instances.  */
    2543              : 
    2544              : tristate
    2545        84631 : constraint_manager::eval_condition (equiv_class_id lhs_ec,
    2546              :                                     enum tree_code op,
    2547              :                                     tree rhs_const) const
    2548              : {
    2549        84631 :   gcc_assert (!lhs_ec.null_p ());
    2550        84631 :   gcc_assert (CONSTANT_CLASS_P (rhs_const));
    2551              : 
    2552        84631 :   if (tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ())
    2553         1220 :     return compare_constants (lhs_const, op, rhs_const);
    2554              : 
    2555              :   /* Check for known inequalities of the form
    2556              :        (LHS_EC != OTHER_CST) or (OTHER_CST != LHS_EC).
    2557              :      If RHS_CONST == OTHER_CST, then we also know that LHS_EC != OTHER_CST.
    2558              :      For example, we might have the constraint
    2559              :        ptr != (void *)0
    2560              :      so we want the condition
    2561              :        ptr == (foo *)0
    2562              :      to be false.  */
    2563              :   int i;
    2564              :   constraint *c;
    2565       241868 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    2566              :     {
    2567       227559 :       if (c->m_op == CONSTRAINT_NE)
    2568              :         {
    2569       203239 :           if (c->m_lhs == lhs_ec)
    2570              :             {
    2571        86144 :               if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
    2572        85735 :                 if (compare_constants
    2573        85735 :                       (rhs_const, EQ_EXPR, other_cst).is_true ())
    2574              :                   {
    2575        69171 :                     switch (op)
    2576              :                       {
    2577         1432 :                       case EQ_EXPR:
    2578         1432 :                         return tristate (tristate::TS_FALSE);
    2579        67593 :                       case NE_EXPR:
    2580        67593 :                         return tristate (tristate::TS_TRUE);
    2581              :                       default:
    2582              :                         break;
    2583              :                       }
    2584              :                   }
    2585              :             }
    2586       134214 :           if (c->m_rhs == lhs_ec)
    2587              :             {
    2588          256 :               if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
    2589          101 :                 if (compare_constants
    2590          101 :                       (rhs_const, EQ_EXPR, other_cst).is_true ())
    2591              :                   {
    2592           81 :                     switch (op)
    2593              :                       {
    2594            0 :                       case EQ_EXPR:
    2595            0 :                         return tristate (tristate::TS_FALSE);
    2596           77 :                       case NE_EXPR:
    2597           77 :                         return tristate (tristate::TS_TRUE);
    2598              :                       default:
    2599              :                         break;
    2600              :                       }
    2601              :                   }
    2602              :             }
    2603              :         }
    2604              :     }
    2605              : 
    2606        14309 :   bounded_ranges_manager *mgr = get_range_manager ();
    2607        15561 :   for (const auto &iter : m_bounded_ranges_constraints)
    2608          622 :     if (iter.m_ec_id == lhs_ec)
    2609          614 :       return iter.m_ranges->eval_condition (op, rhs_const, mgr);
    2610              : 
    2611              :   /* Look at existing bounds on LHS_EC.  */
    2612        13695 :   range lhs_bounds = get_ec_bounds (lhs_ec);
    2613        13695 :   tristate result = lhs_bounds.eval_condition (op, rhs_const);
    2614        13695 :   if (result.is_known ())
    2615         1578 :     return result;
    2616              : 
    2617              :   /* Also reject if range::add_bound fails.  */
    2618        12117 :   if (!lhs_bounds.add_bound (op, rhs_const))
    2619           78 :     return tristate (false);
    2620              : 
    2621        12039 :   return tristate::unknown ();
    2622              : }
    2623              : 
    2624              : /* Return true iff "LHS == RHS" is known to be impossible due to
    2625              :    derived conditions.
    2626              : 
    2627              :    Look for an EC containing an EC_VAL of the form (LHS OP CST).
    2628              :    If found, see if (LHS OP CST) == EC_VAL is false.
    2629              :    If so, we know this condition is false.
    2630              : 
    2631              :    For example, if we already know that
    2632              :      (X & CST_MASK) == Y
    2633              :    and we're evaluating X == Z, we can test to see if
    2634              :      (Z & CST_MASK) == EC_VAL
    2635              :    and thus if:
    2636              :      (Z & CST_MASK) == Y
    2637              :    and reject this if we know that's false.  */
    2638              : 
    2639              : bool
    2640        52329 : constraint_manager::impossible_derived_conditions_p (const svalue *lhs,
    2641              :                                                      const svalue *rhs) const
    2642              : {
    2643        52329 :   int i;
    2644        52329 :   equiv_class *ec;
    2645       202647 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    2646              :     {
    2647       625048 :       for (const svalue *ec_sval : ec->m_vars)
    2648       173848 :         switch (ec_sval->get_kind ())
    2649              :           {
    2650              :           default:
    2651              :             break;
    2652        14545 :           case SK_BINOP:
    2653        14545 :             {
    2654        14545 :               const binop_svalue *iter_binop
    2655        14545 :                 = as_a <const binop_svalue *> (ec_sval);
    2656        14545 :               if (lhs == iter_binop->get_arg0 ()
    2657        14545 :                   && iter_binop->get_type ())
    2658          548 :                 if (iter_binop->get_arg1 ()->get_kind () == SK_CONSTANT)
    2659              :                   {
    2660              :                     /* Try evaluating EC_SVAL with LHS
    2661              :                        as the value of EC_SVAL's lhs, and see if it's
    2662              :                        consistent with existing knowledge.  */
    2663          305 :                     const svalue *subst_bin_op
    2664          305 :                       = m_mgr->get_or_create_binop
    2665          305 :                       (iter_binop->get_type (),
    2666              :                        iter_binop->get_op (),
    2667              :                        rhs,
    2668              :                        iter_binop->get_arg1 ());
    2669          305 :                     tristate t = eval_condition (subst_bin_op,
    2670              :                                                  EQ_EXPR,
    2671              :                                                  ec_sval);
    2672          305 :                     if (t.is_false ())
    2673          123 :                       return true; /* Impossible.  */
    2674              :                   }
    2675              :             }
    2676              :             break;
    2677              :           }
    2678              :     }
    2679              :   /* Not known to be impossible.  */
    2680              :   return false;
    2681              : }
    2682              : 
    2683              : 
    2684              : /* Evaluate the condition LHS OP RHS, without modifying this
    2685              :    constraint_manager (avoiding the creation of equiv_class instances).  */
    2686              : 
    2687              : tristate
    2688       738459 : constraint_manager::eval_condition (const svalue *lhs,
    2689              :                                     enum tree_code op,
    2690              :                                     const svalue *rhs) const
    2691              : {
    2692       738459 :   lhs = lhs->unwrap_any_unmergeable ();
    2693       738459 :   rhs = rhs->unwrap_any_unmergeable ();
    2694              : 
    2695              :   /* Nothing can be known about unknown or poisoned values.  */
    2696       738459 :   if (lhs->get_kind () == SK_UNKNOWN
    2697       696576 :       || lhs->get_kind () == SK_POISONED
    2698       696576 :       || rhs->get_kind () == SK_UNKNOWN
    2699      1422393 :       || rhs->get_kind () == SK_POISONED)
    2700        54525 :     return tristate (tristate::TS_UNKNOWN);
    2701              : 
    2702       683934 :   if (lhs == rhs
    2703       683934 :       && !(FLOAT_TYPE_P (lhs->get_type ())
    2704       110186 :            || FLOAT_TYPE_P (rhs->get_type ())))
    2705              :     {
    2706       110186 :       switch (op)
    2707              :         {
    2708       109658 :         case EQ_EXPR:
    2709       109658 :         case GE_EXPR:
    2710       109658 :         case LE_EXPR:
    2711       109658 :           return tristate (tristate::TS_TRUE);
    2712              : 
    2713          528 :         case NE_EXPR:
    2714          528 :         case GT_EXPR:
    2715          528 :         case LT_EXPR:
    2716          528 :           return tristate (tristate::TS_FALSE);
    2717              :         default:
    2718              :           break;
    2719              :         }
    2720              :     }
    2721              : 
    2722       573748 :   equiv_class_id lhs_ec (-1);
    2723       573748 :   equiv_class_id rhs_ec (-1);
    2724       573748 :   get_equiv_class_by_svalue (lhs, &lhs_ec);
    2725       573748 :   get_equiv_class_by_svalue (rhs, &rhs_ec);
    2726       573748 :   if (!lhs_ec.null_p () && !rhs_ec.null_p ())
    2727              :     {
    2728       251723 :       tristate result_for_ecs
    2729       251723 :         = eval_condition (lhs_ec, op, rhs_ec);
    2730       251723 :       if (result_for_ecs.is_known ())
    2731       249183 :         return result_for_ecs;
    2732              :     }
    2733              : 
    2734       324565 :   if (op == EQ_EXPR
    2735       324565 :       && impossible_derived_conditions_p (lhs, rhs))
    2736          123 :     return false;
    2737              : 
    2738              :   /* If at least one is not in an EC, we have no constraints
    2739              :      comparing LHS and RHS yet.
    2740              :      They might still be comparable if one (or both) is a constant.
    2741              : 
    2742              :      Alternatively, we can also get here if we had ECs but they weren't
    2743              :      comparable.  Again, constant comparisons might give an answer.  */
    2744       324442 :   tree lhs_const = lhs->maybe_get_constant ();
    2745       324442 :   tree rhs_const = rhs->maybe_get_constant ();
    2746       324442 :   if (lhs_const && rhs_const)
    2747              :     {
    2748         1961 :       tristate result_for_constants
    2749         1961 :         = compare_constants (lhs_const, op, rhs_const);
    2750         1961 :       if (result_for_constants.is_known ())
    2751         1961 :         return result_for_constants;
    2752              :     }
    2753              : 
    2754       322481 :   if (!lhs_ec.null_p ())
    2755              :     {
    2756        89916 :       if (rhs_const)
    2757        82687 :         return eval_condition (lhs_ec, op, rhs_const);
    2758              :     }
    2759       239794 :   if (!rhs_ec.null_p ())
    2760              :     {
    2761        58476 :       if (lhs_const)
    2762              :         {
    2763         1944 :           enum tree_code swapped_op = swap_tree_comparison (op);
    2764         1944 :           return eval_condition (rhs_ec, swapped_op, lhs_const);
    2765              :         }
    2766              :     }
    2767              : 
    2768       237850 :   return tristate (tristate::TS_UNKNOWN);
    2769              : }
    2770              : 
    2771              : /* Delete any information about svalues identified by P.
    2772              :    Such instances are removed from equivalence classes, and any
    2773              :    redundant ECs and constraints are also removed.
    2774              :    Accumulate stats into STATS.  */
    2775              : 
    2776              : template <typename PurgeCriteria>
    2777              : void
    2778       459565 : constraint_manager::purge (const PurgeCriteria &p, purge_stats *stats)
    2779              : {
    2780              :   /* Delete any svalues identified by P within the various equivalence
    2781              :      classes.  */
    2782      4186905 :   for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
    2783              :     {
    2784      1686413 :       equiv_class *ec = m_equiv_classes[ec_idx];
    2785              : 
    2786              :       int i;
    2787              :       const svalue *sval;
    2788      1686413 :       bool delete_ec = false;
    2789      3514009 :       FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
    2790              :         {
    2791      1827596 :           if (sval == ec->m_cst_sval)
    2792       550083 :             continue;
    2793      1277513 :           if (p.should_purge_p (sval))
    2794              :             {
    2795        28501 :               if (ec->del (sval))
    2796        24078 :                 if (!ec->m_constant)
    2797      1827596 :                   delete_ec = true;
    2798              :             }
    2799              :         }
    2800              : 
    2801      1686413 :       if (delete_ec)
    2802              :         {
    2803        24078 :           delete ec;
    2804        24078 :           m_equiv_classes.ordered_remove (ec_idx);
    2805        24078 :           if (stats)
    2806            0 :             stats->m_num_equiv_classes++;
    2807              : 
    2808              :           /* Update the constraints, potentially removing some.  */
    2809       180151 :           for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
    2810              :             {
    2811        68384 :               constraint *c = &m_constraints[con_idx];
    2812              : 
    2813              :               /* Remove constraints that refer to the deleted EC.  */
    2814        68384 :               if (c->m_lhs == ec_idx
    2815        68384 :                   || c->m_rhs == ec_idx)
    2816              :                 {
    2817        18961 :                   m_constraints.ordered_remove (con_idx);
    2818        18961 :                   if (stats)
    2819            0 :                     stats->m_num_constraints++;
    2820              :                 }
    2821              :               else
    2822              :                 {
    2823              :                   /* Renumber constraints that refer to ECs that have
    2824              :                      had their idx changed.  */
    2825        49423 :                   c->m_lhs.update_for_removal (ec_idx);
    2826        49423 :                   c->m_rhs.update_for_removal (ec_idx);
    2827              : 
    2828        49423 :                   con_idx++;
    2829              :                 }
    2830              :             }
    2831              : 
    2832              :           /* Update bounded_ranges_constraint instances.  */
    2833              :           for (unsigned r_idx = 0;
    2834      1687325 :                r_idx < m_bounded_ranges_constraints.length (); )
    2835              :             {
    2836              :               bounded_ranges_constraint *brc
    2837          912 :                 = &m_bounded_ranges_constraints[r_idx];
    2838              : 
    2839              :               /* Remove if it refers to the deleted EC.  */
    2840          912 :               if (brc->m_ec_id == ec_idx)
    2841              :                 {
    2842          313 :                   m_bounded_ranges_constraints.ordered_remove (r_idx);
    2843          313 :                   if (stats)
    2844            0 :                     stats->m_num_bounded_ranges_constraints++;
    2845              :                 }
    2846              :               else
    2847              :                 {
    2848              :                   /* Renumber any EC ids that refer to ECs that have
    2849              :                      had their idx changed.  */
    2850          599 :                   brc->m_ec_id.update_for_removal (ec_idx);
    2851          599 :                   r_idx++;
    2852              :                 }
    2853              :             }
    2854              :         }
    2855              :       else
    2856      1662335 :         ec_idx++;
    2857              :     }
    2858              : 
    2859              :   /* Now delete any constraints that are purely between constants.  */
    2860      2963739 :   for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
    2861              :     {
    2862      1096877 :       constraint *c = &m_constraints[con_idx];
    2863      1096877 :       if (m_equiv_classes[c->m_lhs.m_idx]->m_vars.length () == 0
    2864      1096877 :           && m_equiv_classes[c->m_rhs.m_idx]->m_vars.length () == 0)
    2865              :         {
    2866            0 :           m_constraints.ordered_remove (con_idx);
    2867            0 :           if (stats)
    2868            0 :             stats->m_num_constraints++;
    2869              :         }
    2870              :       else
    2871              :         {
    2872      1096877 :           con_idx++;
    2873              :         }
    2874              :     }
    2875              : 
    2876              :   /* Finally, delete any ECs that purely contain constants and aren't
    2877              :      referenced by any constraints.  */
    2878      2121900 :   for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
    2879              :     {
    2880      1662335 :       equiv_class *ec = m_equiv_classes[ec_idx];
    2881      1662335 :       if (ec->m_vars.length () == 0)
    2882              :         {
    2883            0 :           equiv_class_id ec_id (ec_idx);
    2884            0 :           bool has_constraint = false;
    2885            0 :           for (unsigned con_idx = 0; con_idx < m_constraints.length ();
    2886              :                con_idx++)
    2887              :             {
    2888            0 :               constraint *c = &m_constraints[con_idx];
    2889            0 :               if (c->m_lhs == ec_id
    2890            0 :                   || c->m_rhs == ec_id)
    2891              :                 {
    2892              :                   has_constraint = true;
    2893              :                   break;
    2894              :                 }
    2895              :             }
    2896            0 :           if (!has_constraint)
    2897              :             {
    2898            0 :               delete ec;
    2899            0 :               m_equiv_classes.ordered_remove (ec_idx);
    2900            0 :               if (stats)
    2901            0 :                 stats->m_num_equiv_classes++;
    2902              : 
    2903              :               /* Renumber constraints that refer to ECs that have
    2904              :                  had their idx changed.  */
    2905            0 :               for (unsigned con_idx = 0; con_idx < m_constraints.length ();
    2906              :                    con_idx++)
    2907              :                 {
    2908            0 :                   constraint *c = &m_constraints[con_idx];
    2909            0 :                   c->m_lhs.update_for_removal (ec_idx);
    2910            0 :                   c->m_rhs.update_for_removal (ec_idx);
    2911              :                 }
    2912              : 
    2913              :               /* Likewise for m_bounded_ranges_constraints.  */
    2914            0 :               for (unsigned r_idx = 0;
    2915            0 :                    r_idx < m_bounded_ranges_constraints.length ();
    2916              :                    r_idx++)
    2917              :                 {
    2918              :                   bounded_ranges_constraint *brc
    2919            0 :                     = &m_bounded_ranges_constraints[r_idx];
    2920            0 :                   brc->m_ec_id.update_for_removal (ec_idx);
    2921              :                 }
    2922              : 
    2923            0 :               continue;
    2924            0 :             }
    2925              :         }
    2926      1662335 :       ec_idx++;
    2927              :     }
    2928              : 
    2929       459565 :   validate ();
    2930       459565 : }
    2931              : 
    2932              : /* Implementation of PurgeCriteria: purge svalues that are not live
    2933              :    with respect to LIVENESS_CTXT.  */
    2934              : 
    2935              : class dead_svalue_purger
    2936              : {
    2937              : public:
    2938       433757 :   dead_svalue_purger (symbolic::liveness_context &liveness_ctxt)
    2939       433757 :   : m_liveness_ctxt (liveness_ctxt)
    2940              :   {
    2941              :   }
    2942              : 
    2943      1161189 :   bool should_purge_p (const svalue *sval) const
    2944              :   {
    2945      1161189 :     return !m_liveness_ctxt.node_live_p (*sval);
    2946              :   }
    2947              : 
    2948              : private:
    2949              :   symbolic::liveness_context &m_liveness_ctxt;
    2950              : };
    2951              : 
    2952              : /* Purge dead values from equivalence classes and update constraints
    2953              :    accordingly.  */
    2954              : 
    2955              : void
    2956       433757 : constraint_manager::
    2957              : on_liveness_change (symbolic::liveness_context &liveness_ctxt)
    2958              : {
    2959       433757 :   dead_svalue_purger p (liveness_ctxt);
    2960       433757 :   purge (p, nullptr);
    2961       433757 : }
    2962              : 
    2963              : class node_purger
    2964              : {
    2965              : public:
    2966        25808 :   node_purger (const symbolic::node &node) : m_node (node) {}
    2967              : 
    2968       116324 :   bool should_purge_p (const svalue *sval) const
    2969              :   {
    2970       116324 :     return sval->involves_p (m_node);
    2971              :   }
    2972              : 
    2973              : private:
    2974              :   const symbolic::node &m_node;
    2975              : };
    2976              : 
    2977              : /* Purge any state involving SVAL.  */
    2978              : 
    2979              : void
    2980        25808 : constraint_manager::purge_state_involving (const symbolic::node &node)
    2981              : {
    2982        25808 :   node_purger p (node);
    2983        25808 :   purge (p, nullptr);
    2984        25808 : }
    2985              : 
    2986              : /* Comparator for use by constraint_manager::canonicalize.
    2987              :    Sort a pair of equiv_class instances, using the representative
    2988              :    svalue as a sort key.  */
    2989              : 
    2990              : static int
    2991     19018905 : equiv_class_cmp (const void *p1, const void *p2)
    2992              : {
    2993     19018905 :   const equiv_class *ec1 = *(const equiv_class * const *)p1;
    2994     19018905 :   const equiv_class *ec2 = *(const equiv_class * const *)p2;
    2995              : 
    2996     19018905 :   const svalue *rep1 = ec1->get_representative ();
    2997     19018905 :   const svalue *rep2 = ec2->get_representative ();
    2998              : 
    2999     19018905 :   gcc_assert (rep1);
    3000     19018905 :   gcc_assert (rep2);
    3001              : 
    3002     19018905 :   return svalue::cmp_ptr (rep1, rep2);
    3003              : }
    3004              : 
    3005              : /* Comparator for use by constraint_manager::canonicalize.
    3006              :    Sort a pair of constraint instances.  */
    3007              : 
    3008              : static int
    3009     10128405 : constraint_cmp (const void *p1, const void *p2)
    3010              : {
    3011     10128405 :   const constraint *c1 = (const constraint *)p1;
    3012     10128405 :   const constraint *c2 = (const constraint *)p2;
    3013     10128405 :   int lhs_cmp = c1->m_lhs.as_int () - c2->m_lhs.as_int ();
    3014     10128405 :   if (lhs_cmp)
    3015              :     return lhs_cmp;
    3016       236272 :   int rhs_cmp = c1->m_rhs.as_int () - c2->m_rhs.as_int ();
    3017       236272 :   if (rhs_cmp)
    3018              :     return rhs_cmp;
    3019        15479 :   return c1->m_op - c2->m_op;
    3020              : }
    3021              : 
    3022              : /* Purge redundant equivalence classes and constraints, and reorder them
    3023              :    within this constraint_manager into a canonical order, to increase the
    3024              :    chances of finding equality with another instance.  */
    3025              : 
    3026              : void
    3027       781679 : constraint_manager::canonicalize ()
    3028              : {
    3029              :   /* First, sort svalues within the ECs.  */
    3030       781679 :   unsigned i;
    3031       781679 :   equiv_class *ec;
    3032      3104377 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    3033      2322698 :     ec->canonicalize ();
    3034              : 
    3035              :   /* TODO: remove constraints where both sides have a constant, and are
    3036              :      thus implicit.  But does this break transitivity?  */
    3037              : 
    3038              :   /* We will be purging and reordering ECs.
    3039              :      We will need to remap the equiv_class_ids in the constraints,
    3040              :      so we need to store the original index of each EC.
    3041              :      Build a lookup table, mapping from the representative svalue
    3042              :      to the original equiv_class_id of that svalue.  */
    3043       781679 :   hash_map<const svalue *, equiv_class_id> original_ec_id;
    3044       781679 :   const unsigned orig_num_equiv_classes = m_equiv_classes.length ();
    3045      3104377 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    3046              :     {
    3047      2322698 :       const svalue *rep = ec->get_representative ();
    3048      2322698 :       gcc_assert (rep);
    3049      2322698 :       original_ec_id.put (rep, i);
    3050              :     }
    3051              : 
    3052              :   /* Find ECs used by constraints.  */
    3053       781679 :   hash_set<const equiv_class *> used_ecs;
    3054       781679 :   constraint *c;
    3055      3098178 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    3056              :     {
    3057      1534820 :       used_ecs.add (m_equiv_classes[c->m_lhs.as_int ()]);
    3058      1534820 :       used_ecs.add (m_equiv_classes[c->m_rhs.as_int ()]);
    3059              :     }
    3060              : 
    3061       809852 :   for (const auto &iter : m_bounded_ranges_constraints)
    3062         9885 :     used_ecs.add (m_equiv_classes[iter.m_ec_id.as_int ()]);
    3063              : 
    3064              :   /* Purge unused ECs: those that aren't used by constraints and
    3065              :      that effectively have only one svalue (either in m_constant
    3066              :      or in m_vars).  */
    3067              :   {
    3068              :     /* "unordered remove if" from a vec.  */
    3069              :     unsigned i = 0;
    3070      3104377 :     while (i < m_equiv_classes.length ())
    3071              :       {
    3072      2322698 :         equiv_class *ec = m_equiv_classes[i];
    3073      2322698 :         if (!used_ecs.contains (ec)
    3074      2322698 :             && !ec->contains_non_constant_p ())
    3075              :           {
    3076        27205 :             m_equiv_classes.unordered_remove (i);
    3077        27205 :             delete ec;
    3078              :           }
    3079              :         else
    3080      2295493 :           i++;
    3081              :       }
    3082              :   }
    3083              : 
    3084              :   /* Next, sort the surviving ECs into a canonical order.  */
    3085       781679 :   m_equiv_classes.qsort (equiv_class_cmp);
    3086              : 
    3087              :   /* Populate ec_id_map based on the old vs new EC ids.  */
    3088       781679 :   one_way_id_map<equiv_class_id> ec_id_map (orig_num_equiv_classes);
    3089      3858851 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    3090              :     {
    3091      2295493 :       const svalue *rep = ec->get_representative ();
    3092      2295493 :       gcc_assert (rep);
    3093      2295493 :       ec_id_map.put (*original_ec_id.get (rep), i);
    3094              :     }
    3095              : 
    3096              :   /* Use ec_id_map to update the EC ids within the constraints.  */
    3097      2316499 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    3098              :     {
    3099      1534820 :       ec_id_map.update (&c->m_lhs);
    3100      1534820 :       ec_id_map.update (&c->m_rhs);
    3101              :     }
    3102              : 
    3103       809852 :   for (auto &iter : m_bounded_ranges_constraints)
    3104         9885 :     ec_id_map.update (&iter.m_ec_id);
    3105              : 
    3106              :   /* Finally, sort the constraints. */
    3107      1248258 :   m_constraints.qsort (constraint_cmp);
    3108       781679 : }
    3109              : 
    3110              : /* Concrete subclass of fact_visitor for use by constraint_manager::merge.
    3111              :    For every fact in CM_A, see if it is also true in *CM_B.  Add such
    3112              :    facts to *OUT.  */
    3113              : 
    3114        42343 : class merger_fact_visitor : public fact_visitor
    3115              : {
    3116              : public:
    3117        42343 :   merger_fact_visitor (const constraint_manager *cm_b,
    3118              :                        constraint_manager *out)
    3119        42343 :   : m_cm_b (cm_b), m_out (out)
    3120              :   {}
    3121              : 
    3122       254655 :   void on_fact (const svalue *lhs, enum tree_code code, const svalue *rhs)
    3123              :     final override
    3124              :   {
    3125              :     /* Special-case for widening.  */
    3126       254655 :     if (lhs->get_kind () == SK_WIDENING)
    3127        11584 :       if (!m_cm_b->get_equiv_class_by_svalue (lhs, nullptr))
    3128              :         {
    3129              :           /* LHS isn't constrained within m_cm_b.  */
    3130         9622 :           bool sat = m_out->add_constraint (lhs, code, rhs);
    3131         9622 :           gcc_assert (sat);
    3132              :           return;
    3133              :         }
    3134              : 
    3135       245033 :     if (m_cm_b->eval_condition (lhs, code, rhs).is_true ())
    3136              :       {
    3137       206830 :         bool sat = m_out->add_constraint (lhs, code, rhs);
    3138       206830 :         if (!sat)
    3139              :           {
    3140              :             /* If -fanalyzer-transitivity is off, we can encounter cases
    3141              :                where at least one of the two constraint_managers being merged
    3142              :                is infeasible, but we only discover that infeasibility
    3143              :                during merging (PR analyzer/96650).
    3144              :                Silently drop such constraints.  */
    3145            8 :             gcc_assert (!flag_analyzer_transitivity);
    3146              :           }
    3147              :       }
    3148              :   }
    3149              : 
    3150          523 :   void on_ranges (const svalue *lhs_sval,
    3151              :                   const bounded_ranges *ranges) final override
    3152              :   {
    3153         1450 :     for (const auto &iter : m_cm_b->m_bounded_ranges_constraints)
    3154              :       {
    3155          309 :         const equiv_class &ec_rhs = iter.m_ec_id.get_obj (*m_cm_b);
    3156          929 :         for (unsigned i = 0; i < ec_rhs.m_vars.length (); i++)
    3157              :           {
    3158          311 :             const svalue *rhs_sval = ec_rhs.m_vars[i];
    3159          311 :             if (lhs_sval == rhs_sval)
    3160              :               {
    3161              :                 /* Union of the two ranges.  */
    3162          218 :                 auto_vec <const bounded_ranges *> pair (2);
    3163          218 :                 pair.quick_push (ranges);
    3164          218 :                 pair.quick_push (iter.m_ranges);
    3165          218 :                 bounded_ranges_manager *ranges_mgr
    3166          218 :                   = m_cm_b->get_range_manager ();
    3167          218 :                 const bounded_ranges *union_
    3168          218 :                   = ranges_mgr->get_or_create_union (pair);
    3169          218 :                 bool sat = m_out->add_bounded_ranges (lhs_sval, union_);
    3170          218 :                 gcc_assert (sat);
    3171          218 :               }
    3172              :           }
    3173              :       }
    3174          523 :   }
    3175              : 
    3176              : private:
    3177              :   const constraint_manager *m_cm_b;
    3178              :   constraint_manager *m_out;
    3179              : };
    3180              : 
    3181              : /* Use MERGER to merge CM_A and CM_B into *OUT.
    3182              :    If one thinks of a constraint_manager as a subset of N-dimensional
    3183              :    space, this takes the union of the points of CM_A and CM_B, and
    3184              :    expresses that into *OUT.  Alternatively, it can be thought of
    3185              :    as the intersection of the constraints.  */
    3186              : 
    3187              : void
    3188        42343 : constraint_manager::merge (const constraint_manager &cm_a,
    3189              :                            const constraint_manager &cm_b,
    3190              :                            constraint_manager *out)
    3191              : {
    3192              :   /* Merge the equivalence classes and constraints.
    3193              :      The easiest way to do this seems to be to enumerate all of the facts
    3194              :      in cm_a, see which are also true in cm_b,
    3195              :      and add those to *OUT.  */
    3196        42343 :   merger_fact_visitor v (&cm_b, out);
    3197        42343 :   cm_a.for_each_fact (&v);
    3198        42343 : }
    3199              : 
    3200              : /* Call VISITOR's on_fact vfunc repeatedly to express the various
    3201              :    equivalence classes and constraints.
    3202              :    This is used by constraint_manager::merge to find the common
    3203              :    facts between two input constraint_managers.  */
    3204              : 
    3205              : void
    3206        42850 : constraint_manager::for_each_fact (fact_visitor *visitor) const
    3207              : {
    3208              :   /* First, call EQ_EXPR within the various equivalence classes.  */
    3209        42850 :   unsigned ec_idx;
    3210        42850 :   equiv_class *ec;
    3211       185315 :   FOR_EACH_VEC_ELT (m_equiv_classes, ec_idx, ec)
    3212              :     {
    3213       142465 :       if (ec->m_cst_sval)
    3214              :         {
    3215              :           unsigned i;
    3216              :           const svalue *sval;
    3217       122762 :           FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
    3218        67786 :             visitor->on_fact (ec->m_cst_sval, EQ_EXPR, sval);
    3219              :         }
    3220       297847 :       for (unsigned i = 0; i < ec->m_vars.length (); i++)
    3221       171397 :         for (unsigned j = i + 1; j < ec->m_vars.length (); j++)
    3222        16015 :           visitor->on_fact (ec->m_vars[i], EQ_EXPR, ec->m_vars[j]);
    3223              :     }
    3224              : 
    3225              :   /* Now, express the various constraints.  */
    3226              :   unsigned con_idx;
    3227              :   constraint *c;
    3228       130538 :   FOR_EACH_VEC_ELT (m_constraints, con_idx, c)
    3229              :     {
    3230        87688 :       const equiv_class &ec_lhs = c->m_lhs.get_obj (*this);
    3231        87688 :       const equiv_class &ec_rhs = c->m_rhs.get_obj (*this);
    3232        87688 :       enum tree_code code = constraint_tree_code (c->m_op);
    3233              : 
    3234        87688 :       if (ec_lhs.m_cst_sval)
    3235              :         {
    3236        13281 :           for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
    3237              :             {
    3238         6661 :               visitor->on_fact (ec_lhs.m_cst_sval, code, ec_rhs.m_vars[j]);
    3239              :             }
    3240              :         }
    3241       175907 :       for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
    3242              :         {
    3243        88219 :           if (ec_rhs.m_cst_sval)
    3244        75230 :             visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_cst_sval);
    3245       178666 :           for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
    3246        90447 :             visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_vars[j]);
    3247              :         }
    3248              :     }
    3249              : 
    3250        44218 :   for (const auto &iter : m_bounded_ranges_constraints)
    3251              :     {
    3252          452 :       const equiv_class &ec_lhs = iter.m_ec_id.get_obj (*this);
    3253         1427 :       for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
    3254              :         {
    3255          523 :           const svalue *lhs_sval = ec_lhs.m_vars[i];
    3256          523 :           visitor->on_ranges (lhs_sval, iter.m_ranges);
    3257              :         }
    3258              :     }
    3259        42850 : }
    3260              : 
    3261              : /* Subclass of fact_visitor for use by
    3262              :    constraint_manager::replay_call_summary.  */
    3263              : 
    3264          507 : class replay_fact_visitor : public fact_visitor
    3265              : {
    3266              : public:
    3267          507 :   replay_fact_visitor (call_summary_replay &r,
    3268              :                        constraint_manager *out)
    3269          507 :   : m_r (r), m_out (out), m_feasible (true)
    3270              :   {}
    3271              : 
    3272          507 :   bool feasible_p () const { return m_feasible; }
    3273              : 
    3274         1484 :   void on_fact (const svalue *lhs, enum tree_code code, const svalue *rhs)
    3275              :     final override
    3276              :   {
    3277         1484 :     const svalue *caller_lhs = m_r.convert_svalue_from_summary (lhs);
    3278         1484 :     if (!caller_lhs)
    3279              :       return;
    3280         1316 :     const svalue *caller_rhs = m_r.convert_svalue_from_summary (rhs);
    3281         1316 :     if (!caller_rhs)
    3282              :       return;
    3283         1308 :     if (!m_out->add_constraint (caller_lhs, code, caller_rhs))
    3284          102 :       m_feasible = false;
    3285              :   }
    3286              : 
    3287            0 :   void on_ranges (const svalue *lhs_sval,
    3288              :                   const bounded_ranges *ranges) final override
    3289              :   {
    3290            0 :     const svalue *caller_lhs = m_r.convert_svalue_from_summary (lhs_sval);
    3291            0 :     if (!caller_lhs)
    3292              :       return;
    3293            0 :     if (!m_out->add_bounded_ranges (caller_lhs, ranges))
    3294            0 :       m_feasible = false;
    3295              :   }
    3296              : 
    3297              : private:
    3298              :   call_summary_replay &m_r;
    3299              :   constraint_manager *m_out;
    3300              :   bool m_feasible;
    3301              : };
    3302              : 
    3303              : /* Attempt to use R to replay the constraints from SUMMARY into this object.
    3304              :    Return true if it is feasible.  */
    3305              : 
    3306              : bool
    3307          507 : constraint_manager::replay_call_summary (call_summary_replay &r,
    3308              :                                          const constraint_manager &summary)
    3309              : {
    3310          507 :   replay_fact_visitor v (r, this);
    3311          507 :   summary.for_each_fact (&v);
    3312          507 :   return v.feasible_p ();
    3313          507 : }
    3314              : 
    3315              : /* Assert that this object is valid.  */
    3316              : 
    3317              : void
    3318       614475 : constraint_manager::validate () const
    3319              : {
    3320              :   /* Skip this in a release build.  */
    3321              : #if !CHECKING_P
    3322              :   return;
    3323              : #endif
    3324              : 
    3325       614475 :   int i;
    3326       614475 :   equiv_class *ec;
    3327      3486790 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    3328              :     {
    3329      2362891 :       gcc_assert (ec);
    3330              : 
    3331              :       int j;
    3332              :       const svalue *sval;
    3333      4958441 :       FOR_EACH_VEC_ELT (ec->m_vars, j, sval)
    3334      2595550 :         gcc_assert (sval);
    3335      2362891 :       if (ec->m_constant)
    3336              :         {
    3337       816931 :           gcc_assert (CONSTANT_CLASS_P (ec->m_constant));
    3338       816931 :           gcc_assert (ec->m_cst_sval);
    3339              :         }
    3340              : #if 0
    3341              :       else
    3342              :         gcc_assert (ec->m_vars.length () > 0);
    3343              : #endif
    3344              :     }
    3345              : 
    3346              :   constraint *c;
    3347      2155680 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    3348              :     {
    3349      1541205 :       gcc_assert (!c->m_lhs.null_p ());
    3350      3082410 :       gcc_assert (c->m_lhs.as_int () < (int)m_equiv_classes.length ());
    3351      1541205 :       gcc_assert (!c->m_rhs.null_p ());
    3352      1541205 :       gcc_assert (c->m_rhs.as_int () < (int)m_equiv_classes.length ());
    3353              :     }
    3354              : 
    3355       643183 :   for (const auto &iter : m_bounded_ranges_constraints)
    3356              :     {
    3357        11002 :       gcc_assert (!iter.m_ec_id.null_p ());
    3358        22004 :       gcc_assert (iter.m_ec_id.as_int () < (int)m_equiv_classes.length ());
    3359              :     }
    3360       614475 : }
    3361              : 
    3362              : bounded_ranges_manager *
    3363        14555 : constraint_manager::get_range_manager () const
    3364              : {
    3365        14555 :   return m_mgr->get_range_manager ();
    3366              : }
    3367              : 
    3368              : #if CHECKING_P
    3369              : 
    3370              : namespace selftest {
    3371              : 
    3372              : /* Various constraint_manager selftests.
    3373              :    These have to be written in terms of a region_model, since
    3374              :    the latter is responsible for managing svalue instances.  */
    3375              : 
    3376              : /* Verify that range::add_bound works as expected.  */
    3377              : 
    3378              : static void
    3379            8 : test_range ()
    3380              : {
    3381            8 :   tree int_0 = integer_zero_node;
    3382            8 :   tree int_1 = integer_one_node;
    3383            8 :   tree int_2 = build_int_cst (integer_type_node, 2);
    3384            8 :   tree int_5 = build_int_cst (integer_type_node, 5);
    3385              : 
    3386            8 :   {
    3387            8 :     range r;
    3388            8 :     ASSERT_FALSE (r.constrained_to_single_element ());
    3389              : 
    3390              :     /* (r >= 1).  */
    3391            8 :     ASSERT_TRUE (r.add_bound (GE_EXPR, int_1));
    3392              : 
    3393              :     /* Redundant.  */
    3394            8 :     ASSERT_TRUE (r.add_bound (GE_EXPR, int_0));
    3395            8 :     ASSERT_TRUE (r.add_bound (GT_EXPR, int_0));
    3396              : 
    3397            8 :     ASSERT_FALSE (r.constrained_to_single_element ());
    3398              : 
    3399              :     /* Contradiction.  */
    3400            8 :     ASSERT_FALSE (r.add_bound (LT_EXPR, int_1));
    3401              : 
    3402              :     /* (r < 5).  */
    3403            8 :     ASSERT_TRUE (r.add_bound (LT_EXPR, int_5));
    3404            8 :     ASSERT_FALSE (r.constrained_to_single_element ());
    3405              : 
    3406              :     /* Contradiction.  */
    3407            8 :     ASSERT_FALSE (r.add_bound (GE_EXPR, int_5));
    3408              : 
    3409              :     /* (r < 2).  */
    3410            8 :     ASSERT_TRUE (r.add_bound (LT_EXPR, int_2));
    3411            8 :     ASSERT_TRUE (r.constrained_to_single_element ());
    3412              : 
    3413              :     /* Redundant.  */
    3414            8 :     ASSERT_TRUE (r.add_bound (LE_EXPR, int_1));
    3415            8 :     ASSERT_TRUE (r.constrained_to_single_element ());
    3416              :   }
    3417            8 : }
    3418              : 
    3419              : /* Verify that setting and getting simple conditions within a region_model
    3420              :    work (thus exercising the underlying constraint_manager).  */
    3421              : 
    3422              : static void
    3423            8 : test_constraint_conditions ()
    3424              : {
    3425            8 :   tree int_42 = build_int_cst (integer_type_node, 42);
    3426            8 :   tree int_0 = integer_zero_node;
    3427              : 
    3428            8 :   tree x = build_global_decl ("x", integer_type_node);
    3429            8 :   tree y = build_global_decl ("y", integer_type_node);
    3430            8 :   tree z = build_global_decl ("z", integer_type_node);
    3431              : 
    3432              :   /* Self-comparisons.  */
    3433            8 :   {
    3434            8 :     symbolic::node_manager node_mgr;
    3435            8 :     region_model model (node_mgr);
    3436            8 :     ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, x);
    3437            8 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, x);
    3438            8 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, x);
    3439            8 :     ASSERT_CONDITION_FALSE (model, x, NE_EXPR, x);
    3440            8 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, x);
    3441            8 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, x);
    3442            8 :   }
    3443              : 
    3444              :   /* Adding self-equality shouldn't add equiv classes.  */
    3445            8 :   {
    3446            8 :     symbolic::node_manager node_mgr;
    3447            8 :     region_model model (node_mgr);
    3448            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, x);
    3449            8 :     ADD_SAT_CONSTRAINT (model, int_42, EQ_EXPR, int_42);
    3450              :     /* ...even when done directly via svalues: */
    3451            8 :     const svalue *sval_int_42 = model.get_rvalue (int_42, nullptr);
    3452            8 :     bool sat = model.get_constraints ()->add_constraint (sval_int_42,
    3453              :                                                          EQ_EXPR,
    3454              :                                                          sval_int_42);
    3455            8 :     ASSERT_TRUE (sat);
    3456            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
    3457            8 :   }
    3458              : 
    3459              :   /* x == y.  */
    3460            8 :   {
    3461            8 :     symbolic::node_manager node_mgr;
    3462            8 :     region_model model (node_mgr);
    3463            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    3464              : 
    3465            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    3466              : 
    3467            8 :     ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, y);
    3468            8 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    3469            8 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    3470            8 :     ASSERT_CONDITION_FALSE (model, x, NE_EXPR, y);
    3471            8 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    3472            8 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    3473              : 
    3474              :     /* Swapped operands.  */
    3475            8 :     ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, x);
    3476            8 :     ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
    3477            8 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
    3478            8 :     ASSERT_CONDITION_FALSE (model, y, NE_EXPR, x);
    3479            8 :     ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    3480            8 :     ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
    3481              : 
    3482              :     /* Comparison with other var.  */
    3483            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
    3484            8 :     ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
    3485            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    3486            8 :     ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
    3487            8 :     ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
    3488            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
    3489            8 :   }
    3490              : 
    3491              :   /* x == y, then y == z  */
    3492            8 :   {
    3493            8 :     symbolic::node_manager node_mgr;
    3494            8 :     region_model model (node_mgr);
    3495            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    3496              : 
    3497            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    3498            8 :     ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, z);
    3499              : 
    3500            8 :     ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, z);
    3501            8 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, z);
    3502            8 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
    3503            8 :     ASSERT_CONDITION_FALSE (model, x, NE_EXPR, z);
    3504            8 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, z);
    3505            8 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, z);
    3506            8 :   }
    3507              : 
    3508              :   /* x != y.  */
    3509            8 :   {
    3510            8 :     symbolic::node_manager node_mgr;
    3511            8 :     region_model model (node_mgr);
    3512              : 
    3513            8 :     ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
    3514              : 
    3515            8 :     ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    3516            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    3517            8 :     ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
    3518            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
    3519            8 :     ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
    3520            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
    3521              : 
    3522              :     /* Swapped operands.  */
    3523            8 :     ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    3524            8 :     ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    3525            8 :     ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
    3526            8 :     ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
    3527            8 :     ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
    3528            8 :     ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
    3529              : 
    3530              :     /* Comparison with other var.  */
    3531            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
    3532            8 :     ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
    3533            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    3534            8 :     ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
    3535            8 :     ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
    3536            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
    3537            8 :   }
    3538              : 
    3539              :   /* x < y.  */
    3540            8 :   {
    3541            8 :     symbolic::node_manager node_mgr;
    3542            8 :     region_model model (node_mgr);
    3543              : 
    3544            8 :     ADD_SAT_CONSTRAINT (model, x, LT_EXPR, y);
    3545              : 
    3546            8 :     ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
    3547            8 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    3548            8 :     ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    3549            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    3550            8 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    3551            8 :     ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
    3552              : 
    3553              :     /* Swapped operands.  */
    3554            8 :     ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    3555            8 :     ASSERT_CONDITION_FALSE (model, y, LE_EXPR, x);
    3556            8 :     ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    3557            8 :     ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    3558            8 :     ASSERT_CONDITION_TRUE (model, y, GT_EXPR, x);
    3559            8 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
    3560            8 :   }
    3561              : 
    3562              :   /* x <= y.  */
    3563            8 :   {
    3564            8 :     symbolic::node_manager node_mgr;
    3565            8 :     region_model model (node_mgr);
    3566              : 
    3567            8 :     ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
    3568              : 
    3569            8 :     ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
    3570            8 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    3571            8 :     ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
    3572            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    3573            8 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    3574            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
    3575              : 
    3576              :     /* Swapped operands.  */
    3577            8 :     ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    3578            8 :     ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
    3579            8 :     ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
    3580            8 :     ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
    3581            8 :     ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
    3582            8 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
    3583            8 :   }
    3584              : 
    3585              :   /* x > y.  */
    3586            8 :   {
    3587            8 :     symbolic::node_manager node_mgr;
    3588            8 :     region_model model (node_mgr);
    3589              : 
    3590            8 :     ADD_SAT_CONSTRAINT (model, x, GT_EXPR, y);
    3591              : 
    3592            8 :     ASSERT_CONDITION_TRUE (model, x, GT_EXPR, y);
    3593            8 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    3594            8 :     ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    3595            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    3596            8 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    3597            8 :     ASSERT_CONDITION_FALSE (model, x, LE_EXPR, y);
    3598              : 
    3599              :     /* Swapped operands.  */
    3600            8 :     ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
    3601            8 :     ASSERT_CONDITION_FALSE (model, y, GE_EXPR, x);
    3602            8 :     ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    3603            8 :     ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    3604            8 :     ASSERT_CONDITION_TRUE (model, y, LT_EXPR, x);
    3605            8 :     ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
    3606            8 :   }
    3607              : 
    3608              :   /* x >= y.  */
    3609            8 :   {
    3610            8 :     symbolic::node_manager node_mgr;
    3611            8 :     region_model model (node_mgr);
    3612              : 
    3613            8 :     ADD_SAT_CONSTRAINT (model, x, GE_EXPR, y);
    3614              : 
    3615            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
    3616            8 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    3617            8 :     ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
    3618            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    3619            8 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    3620            8 :     ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
    3621              : 
    3622              :     /* Swapped operands.  */
    3623            8 :     ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
    3624            8 :     ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
    3625            8 :     ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
    3626            8 :     ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
    3627            8 :     ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
    3628            8 :     ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
    3629            8 :   }
    3630              : 
    3631              :   // TODO: implied orderings
    3632              : 
    3633              :   /* Constants.  */
    3634            8 :   {
    3635            8 :     symbolic::node_manager node_mgr;
    3636            8 :     region_model model (node_mgr);
    3637              : 
    3638            8 :     ASSERT_CONDITION_FALSE (model, int_0, EQ_EXPR, int_42);
    3639            8 :     ASSERT_CONDITION_TRUE (model, int_0, NE_EXPR, int_42);
    3640            8 :     ASSERT_CONDITION_TRUE (model, int_0, LT_EXPR, int_42);
    3641            8 :     ASSERT_CONDITION_TRUE (model, int_0, LE_EXPR, int_42);
    3642            8 :     ASSERT_CONDITION_FALSE (model, int_0, GT_EXPR, int_42);
    3643            8 :     ASSERT_CONDITION_FALSE (model, int_0, GE_EXPR, int_42);
    3644            8 :   }
    3645              : 
    3646              :   /* x == 0, y == 42.  */
    3647            8 :   {
    3648            8 :     symbolic::node_manager node_mgr;
    3649            8 :     region_model model (node_mgr);
    3650              : 
    3651            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    3652            8 :     ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, int_42);
    3653              : 
    3654            8 :     ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    3655            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    3656            8 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    3657            8 :     ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
    3658            8 :     ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
    3659            8 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    3660            8 :   }
    3661              : 
    3662              :   /* Unsatisfiable combinations.  */
    3663              : 
    3664              :   /* x == y && x != y.  */
    3665            8 :   {
    3666            8 :     symbolic::node_manager node_mgr;
    3667            8 :     region_model model (node_mgr);
    3668              : 
    3669            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    3670            8 :     ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, y);
    3671            8 :   }
    3672              : 
    3673              :   /* x == 0 then x == 42.  */
    3674            8 :   {
    3675            8 :     symbolic::node_manager node_mgr;
    3676            8 :     region_model model (node_mgr);
    3677              : 
    3678            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    3679            8 :     ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, int_42);
    3680            8 :   }
    3681              : 
    3682              :   /* x == 0 then x != 0.  */
    3683            8 :   {
    3684            8 :     symbolic::node_manager node_mgr;
    3685            8 :     region_model model (node_mgr);
    3686              : 
    3687            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    3688            8 :     ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, int_0);
    3689            8 :   }
    3690              : 
    3691              :   /* x == 0 then x > 0.  */
    3692            8 :   {
    3693            8 :     symbolic::node_manager node_mgr;
    3694            8 :     region_model model (node_mgr);
    3695              : 
    3696            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    3697            8 :     ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, int_0);
    3698            8 :   }
    3699              : 
    3700              :   /* x != y && x == y.  */
    3701            8 :   {
    3702            8 :     symbolic::node_manager node_mgr;
    3703            8 :     region_model model (node_mgr);
    3704              : 
    3705            8 :     ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
    3706            8 :     ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, y);
    3707            8 :   }
    3708              : 
    3709              :   /* x <= y && x > y.  */
    3710            8 :   {
    3711            8 :     symbolic::node_manager node_mgr;
    3712            8 :     region_model model (node_mgr);
    3713              : 
    3714            8 :     ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
    3715            8 :     ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, y);
    3716            8 :   }
    3717              : 
    3718              :   // etc
    3719            8 : }
    3720              : 
    3721              : /* Test transitivity of conditions.  */
    3722              : 
    3723              : static void
    3724            4 : test_transitivity ()
    3725              : {
    3726            4 :   tree a = build_global_decl ("a", integer_type_node);
    3727            4 :   tree b = build_global_decl ("b", integer_type_node);
    3728            4 :   tree c = build_global_decl ("c", integer_type_node);
    3729            4 :   tree d = build_global_decl ("d", integer_type_node);
    3730              : 
    3731              :   /* a == b, then c == d, then c == b.  */
    3732            4 :   {
    3733            4 :     symbolic::node_manager node_mgr;
    3734            4 :     region_model model (node_mgr);
    3735              : 
    3736            4 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, b);
    3737            4 :     ASSERT_CONDITION_UNKNOWN (model, b, EQ_EXPR, c);
    3738            4 :     ASSERT_CONDITION_UNKNOWN (model, c, EQ_EXPR, d);
    3739            4 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);
    3740              : 
    3741            4 :     ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, b);
    3742            4 :     ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);
    3743              : 
    3744            4 :     ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, d);
    3745            4 :     ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, d);
    3746            4 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);
    3747              : 
    3748            4 :     ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, b);
    3749            4 :     ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, b);
    3750            4 :     ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, d);
    3751            4 :   }
    3752              : 
    3753              :   /* Transitivity: "a < b", "b < c" should imply "a < c".  */
    3754            4 :   {
    3755            4 :     symbolic::node_manager node_mgr;
    3756            4 :     region_model model (node_mgr);
    3757              : 
    3758            4 :     ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
    3759            4 :     ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
    3760              : 
    3761            4 :     ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    3762            4 :     ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
    3763            4 :   }
    3764              : 
    3765              :   /* Transitivity: "a <= b", "b < c" should imply "a < c".  */
    3766            4 :   {
    3767            4 :     symbolic::node_manager node_mgr;
    3768            4 :     region_model model (node_mgr);
    3769              : 
    3770            4 :     ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
    3771            4 :     ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
    3772              : 
    3773            4 :     ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    3774            4 :     ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
    3775            4 :   }
    3776              : 
    3777              :   /* Transitivity: "a <= b", "b <= c" should imply "a <= c".  */
    3778            4 :   {
    3779            4 :     symbolic::node_manager node_mgr;
    3780            4 :     region_model model (node_mgr);
    3781              : 
    3782            4 :     ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
    3783            4 :     ADD_SAT_CONSTRAINT (model, b, LE_EXPR, c);
    3784              : 
    3785            4 :     ASSERT_CONDITION_TRUE (model, a, LE_EXPR, c);
    3786            4 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
    3787            4 :   }
    3788              : 
    3789              :   /* Transitivity: "a > b", "b > c" should imply "a > c".  */
    3790            4 :   {
    3791            4 :     symbolic::node_manager node_mgr;
    3792            4 :     region_model model (node_mgr);
    3793              : 
    3794            4 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    3795            4 :     ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
    3796              : 
    3797            4 :     ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
    3798            4 :     ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
    3799            4 :   }
    3800              : 
    3801              :   /* Transitivity: "a >= b", "b > c" should imply " a > c".  */
    3802            4 :   {
    3803            4 :     symbolic::node_manager node_mgr;
    3804            4 :     region_model model (node_mgr);
    3805              : 
    3806            4 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    3807            4 :     ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
    3808              : 
    3809            4 :     ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
    3810            4 :     ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
    3811            4 :   }
    3812              : 
    3813              :   /* Transitivity: "a >= b", "b >= c" should imply "a >= c".  */
    3814            4 :   {
    3815            4 :     symbolic::node_manager node_mgr;
    3816            4 :     region_model model (node_mgr);
    3817              : 
    3818            4 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    3819            4 :     ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
    3820              : 
    3821            4 :     ASSERT_CONDITION_TRUE (model, a, GE_EXPR, c);
    3822            4 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
    3823            4 :   }
    3824              : 
    3825              :   /* Transitivity: "(a < b)", "(c < d)", "(b < c)" should
    3826              :      imply the easy cases:
    3827              :        (a < c)
    3828              :        (b < d)
    3829              :      but also that:
    3830              :        (a < d).  */
    3831            4 :   {
    3832            4 :     symbolic::node_manager node_mgr;
    3833            4 :     region_model model (node_mgr);
    3834              : 
    3835            4 :     ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
    3836            4 :     ADD_SAT_CONSTRAINT (model, c, LT_EXPR, d);
    3837            4 :     ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
    3838              : 
    3839            4 :     ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    3840            4 :     ASSERT_CONDITION_TRUE (model, b, LT_EXPR, d);
    3841            4 :     ASSERT_CONDITION_TRUE (model, a, LT_EXPR, d);
    3842            4 :   }
    3843              : 
    3844              :   /* Transitivity: "a >= b", "b >= a" should imply that a == b.  */
    3845            4 :   {
    3846            4 :     symbolic::node_manager node_mgr;
    3847            4 :     region_model model (node_mgr);
    3848              : 
    3849            4 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    3850            4 :     ADD_SAT_CONSTRAINT (model, b, GE_EXPR, a);
    3851              : 
    3852              :     // TODO:
    3853            4 :     ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);
    3854              : 
    3855              :     /* The ECs for a and b should have merged, and any constraints removed.  */
    3856            4 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
    3857            4 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
    3858            4 :   }
    3859              : 
    3860              :   /* Transitivity: "a >= b", "b > a" should be impossible.  */
    3861            4 :   {
    3862            4 :     symbolic::node_manager node_mgr;
    3863            4 :     region_model model (node_mgr);
    3864              : 
    3865            4 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    3866            4 :     ADD_UNSAT_CONSTRAINT (model, b, GT_EXPR, a);
    3867            4 :   }
    3868              : 
    3869              :   /* Transitivity: "a >= b", "b >= c", "c >= a" should imply
    3870              :      that a == b == c.  */
    3871            4 :   {
    3872            4 :     symbolic::node_manager node_mgr;
    3873            4 :     region_model model (node_mgr);
    3874              : 
    3875            4 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    3876            4 :     ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
    3877            4 :     ADD_SAT_CONSTRAINT (model, c, GE_EXPR, a);
    3878              : 
    3879            4 :     ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, c);
    3880            4 :   }
    3881              : 
    3882              :   /* Transitivity: "a > b", "b > c", "c > a"
    3883              :      should be impossible.  */
    3884            4 :   {
    3885            4 :     symbolic::node_manager node_mgr;
    3886            4 :     region_model model (node_mgr);
    3887              : 
    3888            4 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    3889            4 :     ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
    3890            4 :     ADD_UNSAT_CONSTRAINT (model, c, GT_EXPR, a);
    3891            4 :   }
    3892              : 
    3893            4 : }
    3894              : 
    3895              : /* Test various conditionals involving constants where the results
    3896              :    ought to be implied based on the values of the constants.  */
    3897              : 
    3898              : static void
    3899            8 : test_constant_comparisons ()
    3900              : {
    3901            8 :   tree int_1 = integer_one_node;
    3902            8 :   tree int_3 = build_int_cst (integer_type_node, 3);
    3903            8 :   tree int_4 = build_int_cst (integer_type_node, 4);
    3904            8 :   tree int_5 = build_int_cst (integer_type_node, 5);
    3905              : 
    3906            8 :   tree int_1023 = build_int_cst (integer_type_node, 1023);
    3907            8 :   tree int_1024 = build_int_cst (integer_type_node, 1024);
    3908              : 
    3909            8 :   tree a = build_global_decl ("a", integer_type_node);
    3910            8 :   tree b = build_global_decl ("b", integer_type_node);
    3911              : 
    3912            8 :   tree a_plus_one = build2 (PLUS_EXPR, integer_type_node, a, int_1);
    3913              : 
    3914              :   /* Given a >= 1024, then a <= 1023 should be impossible.  */
    3915            8 :   {
    3916            8 :     symbolic::node_manager node_mgr;
    3917            8 :     region_model model (node_mgr);
    3918              : 
    3919            8 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_1024);
    3920            8 :     ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_1023);
    3921            8 :   }
    3922              : 
    3923              :   /* a > 4.  */
    3924            8 :   {
    3925            8 :     symbolic::node_manager node_mgr;
    3926            8 :     region_model model (node_mgr);
    3927              : 
    3928            8 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_4);
    3929            8 :     ASSERT_CONDITION_TRUE (model, a, GT_EXPR, int_4);
    3930            8 :     ASSERT_CONDITION_TRUE (model, a, NE_EXPR, int_3);
    3931            8 :     ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_5);
    3932            8 :   }
    3933              : 
    3934              :   /* a <= 4.  */
    3935            8 :   {
    3936            8 :     symbolic::node_manager node_mgr;
    3937            8 :     region_model model (node_mgr);
    3938              : 
    3939            8 :     ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    3940            8 :     ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_4);
    3941            8 :     ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_5);
    3942            8 :     ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_3);
    3943            8 :   }
    3944              : 
    3945              :   /* If "a > b" and "a == 3", then "b == 4" ought to be unsatisfiable.  */
    3946            8 :   {
    3947            8 :     symbolic::node_manager node_mgr;
    3948            8 :     region_model model (node_mgr);
    3949              : 
    3950            8 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    3951            8 :     ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_3);
    3952            8 :     ADD_UNSAT_CONSTRAINT (model, b, EQ_EXPR, int_4);
    3953            8 :   }
    3954              : 
    3955              :   /* Various tests of int ranges where there is only one possible candidate.  */
    3956            8 :   {
    3957              :     /* If "a <= 4" && "a > 3", then "a == 4",
    3958              :        assuming a is of integral type.  */
    3959            8 :     {
    3960            8 :       symbolic::node_manager node_mgr;
    3961            8 :       region_model model (node_mgr);
    3962            8 :       ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    3963            8 :       ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    3964            8 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    3965            8 :     }
    3966              : 
    3967              :     /* If "a > 3" && "a <= 4", then "a == 4",
    3968              :        assuming a is of integral type.  */
    3969            8 :     {
    3970            8 :       symbolic::node_manager node_mgr;
    3971            8 :       region_model model (node_mgr);
    3972            8 :       ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    3973            8 :       ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    3974            8 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    3975            8 :     }
    3976              :     /* If "a > 3" && "a < 5", then "a == 4",
    3977              :        assuming a is of integral type.  */
    3978            8 :     {
    3979            8 :       symbolic::node_manager node_mgr;
    3980            8 :       region_model model (node_mgr);
    3981              : 
    3982            8 :       ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    3983            8 :       ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
    3984            8 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    3985            8 :     }
    3986              :     /* If "a >= 4" && "a < 5", then "a == 4",
    3987              :        assuming a is of integral type.  */
    3988            8 :     {
    3989            8 :       symbolic::node_manager node_mgr;
    3990            8 :       region_model model (node_mgr);
    3991              : 
    3992            8 :       ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
    3993            8 :       ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
    3994            8 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    3995            8 :     }
    3996              :     /* If "a >= 4" && "a <= 4", then "a == 4".  */
    3997            8 :     {
    3998            8 :       symbolic::node_manager node_mgr;
    3999            8 :       region_model model (node_mgr);
    4000              : 
    4001            8 :       ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
    4002            8 :       ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    4003            8 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    4004            8 :     }
    4005              :   }
    4006              : 
    4007              :   /* As above, but for floating-point:
    4008              :      if "f > 3" && "f <= 4" we don't know that f == 4.  */
    4009            8 :   {
    4010            8 :     tree f = build_global_decl ("f", double_type_node);
    4011            8 :     tree float_3 = build_real_from_int_cst (double_type_node, int_3);
    4012            8 :     tree float_4 = build_real_from_int_cst (double_type_node, int_4);
    4013              : 
    4014            8 :     symbolic::node_manager node_mgr;
    4015            8 :     region_model model (node_mgr);
    4016              : 
    4017            8 :     ADD_SAT_CONSTRAINT (model, f, GT_EXPR, float_3);
    4018            8 :     ADD_SAT_CONSTRAINT (model, f, LE_EXPR, float_4);
    4019            8 :     ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, float_4);
    4020            8 :     ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, int_4);
    4021            8 :   }
    4022              : 
    4023              :   /* "a > 3 && a <= 3" should be impossible.  */
    4024            8 :   {
    4025            8 :     symbolic::node_manager node_mgr;
    4026            8 :     region_model model (node_mgr);
    4027              : 
    4028            8 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    4029            8 :     ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_3);
    4030            8 :   }
    4031              : 
    4032              :   /* "(a + 1) > 3 && a < 3" should be impossible.  */
    4033            8 :   {
    4034            8 :     symbolic::node_manager node_mgr;
    4035            8 :     {
    4036            8 :       region_model model (node_mgr);
    4037            8 :       ADD_SAT_CONSTRAINT (model, a_plus_one, GT_EXPR, int_3);
    4038            8 :       ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_3);
    4039            8 :     }
    4040            8 :     {
    4041            8 :       region_model model (node_mgr);
    4042            8 :       ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_3);
    4043            8 :       ADD_UNSAT_CONSTRAINT (model, a_plus_one, GT_EXPR, int_3);
    4044            8 :     }
    4045            8 :   }
    4046              : 
    4047              :   /* "3 < a < 4" should be impossible for integer a.  */
    4048            8 :   {
    4049            8 :     symbolic::node_manager node_mgr;
    4050            8 :     {
    4051            8 :       region_model model (node_mgr);
    4052            8 :       ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a);
    4053            8 :       ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4);
    4054            8 :     }
    4055            8 :     {
    4056            8 :       region_model model (node_mgr);
    4057            8 :       ADD_SAT_CONSTRAINT (model, int_1, LT_EXPR, a);
    4058            8 :       ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a);
    4059            8 :       ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
    4060            8 :       ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4);
    4061            8 :     }
    4062            8 :     {
    4063            8 :       region_model model (node_mgr);
    4064            8 :       ADD_SAT_CONSTRAINT (model, int_1, LT_EXPR, a);
    4065            8 :       ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
    4066            8 :       ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a);
    4067            8 :       ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4);
    4068            8 :     }
    4069            8 :     {
    4070            8 :       region_model model (node_mgr);
    4071            8 :       ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_4);
    4072            8 :       ADD_UNSAT_CONSTRAINT (model, int_3, LT_EXPR, a);
    4073            8 :     }
    4074            8 :     {
    4075            8 :       region_model model (node_mgr);
    4076            8 :       ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    4077            8 :       ADD_UNSAT_CONSTRAINT (model, int_4, GT_EXPR, a);
    4078            8 :     }
    4079            8 :     {
    4080            8 :       region_model model (node_mgr);
    4081            8 :       ADD_SAT_CONSTRAINT (model, int_4, GT_EXPR, a);
    4082            8 :       ADD_UNSAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    4083            8 :     }
    4084            8 :   }
    4085            8 : }
    4086              : 
    4087              : /* Verify various lower-level implementation details about
    4088              :    constraint_manager.  */
    4089              : 
    4090              : static void
    4091            8 : test_constraint_impl ()
    4092              : {
    4093            8 :   tree int_42 = build_int_cst (integer_type_node, 42);
    4094            8 :   tree int_0 = integer_zero_node;
    4095              : 
    4096            8 :   tree x = build_global_decl ("x", integer_type_node);
    4097            8 :   tree y = build_global_decl ("y", integer_type_node);
    4098            8 :   tree z = build_global_decl ("z", integer_type_node);
    4099              : 
    4100              :   /* x == y.  */
    4101            8 :   {
    4102            8 :     symbolic::node_manager node_mgr;
    4103            8 :     region_model model (node_mgr);
    4104              : 
    4105            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    4106              : 
    4107              :     /* Assert various things about the insides of model.  */
    4108            8 :     constraint_manager *cm = model.get_constraints ();
    4109            8 :     ASSERT_EQ (cm->m_constraints.length (), 0);
    4110            8 :     ASSERT_EQ (cm->m_equiv_classes.length (), 1);
    4111            8 :   }
    4112              : 
    4113              :   /* y <= z; x == y.  */
    4114            8 :   {
    4115            8 :     symbolic::node_manager node_mgr;
    4116            8 :     region_model model (node_mgr);
    4117              : 
    4118            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    4119            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    4120              : 
    4121            8 :     ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
    4122            8 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
    4123            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    4124              : 
    4125            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    4126              : 
    4127              :     /* Assert various things about the insides of model.  */
    4128            8 :     constraint_manager *cm = model.get_constraints ();
    4129            8 :     ASSERT_EQ (cm->m_constraints.length (), 1);
    4130            8 :     ASSERT_EQ (cm->m_equiv_classes.length (), 2);
    4131              : 
    4132              :     /* Ensure that we merged the constraints.  */
    4133            8 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
    4134            8 :   }
    4135              : 
    4136              :   /* y <= z; y == x.  */
    4137            8 :   {
    4138            8 :     symbolic::node_manager node_mgr;
    4139            8 :     region_model model (node_mgr);
    4140              : 
    4141            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    4142            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    4143              : 
    4144            8 :     ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
    4145            8 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
    4146            8 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    4147              : 
    4148            8 :     ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, x);
    4149              : 
    4150              :     /* Assert various things about the insides of model.  */
    4151            8 :     constraint_manager *cm = model.get_constraints ();
    4152            8 :     ASSERT_EQ (cm->m_constraints.length (), 1);
    4153            8 :     ASSERT_EQ (cm->m_equiv_classes.length (), 2);
    4154              : 
    4155              :     /* Ensure that we merged the constraints.  */
    4156            8 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
    4157            8 :   }
    4158              : 
    4159              :   /* x == 0, then x != 42.  */
    4160            8 :   {
    4161            8 :     symbolic::node_manager node_mgr;
    4162            8 :     region_model model (node_mgr);
    4163              : 
    4164            8 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    4165            8 :     ADD_SAT_CONSTRAINT (model, x, NE_EXPR, int_42);
    4166              : 
    4167              :     /* Assert various things about the insides of model.  */
    4168            8 :     constraint_manager *cm = model.get_constraints ();
    4169            8 :     ASSERT_EQ (cm->m_constraints.length (), 0);
    4170            8 :     ASSERT_EQ (cm->m_equiv_classes.length (), 1);
    4171            8 :   }
    4172              : 
    4173              :   // TODO: selftest for merging ecs "in the middle"
    4174              :   // where a non-final one gets overwritten
    4175              : 
    4176              :   // TODO: selftest where there are pre-existing constraints
    4177            8 : }
    4178              : 
    4179              : /* Check that operator== and hashing works as expected for the
    4180              :    various types.  */
    4181              : 
    4182              : static void
    4183            8 : test_equality ()
    4184              : {
    4185            8 :   tree x = build_global_decl ("x", integer_type_node);
    4186            8 :   tree y = build_global_decl ("y", integer_type_node);
    4187              : 
    4188            8 :   {
    4189            8 :     symbolic::node_manager node_mgr;
    4190              : 
    4191            8 :     region_model model0 (node_mgr);
    4192            8 :     region_model model1 (node_mgr);
    4193              : 
    4194            8 :     constraint_manager *cm0 = model0.get_constraints ();
    4195            8 :     constraint_manager *cm1 = model1.get_constraints ();
    4196              : 
    4197            8 :     ASSERT_EQ (cm0->hash (), cm1->hash ());
    4198            8 :     ASSERT_EQ (*cm0, *cm1);
    4199              : 
    4200            8 :     ASSERT_EQ (model0.hash (), model1.hash ());
    4201            8 :     ASSERT_EQ (model0, model1);
    4202              : 
    4203            8 :     ADD_SAT_CONSTRAINT (model1, x, EQ_EXPR, y);
    4204            8 :     ASSERT_NE (cm0->hash (), cm1->hash ());
    4205            8 :     ASSERT_NE (*cm0, *cm1);
    4206              : 
    4207            8 :     ASSERT_NE (model0.hash (), model1.hash ());
    4208            8 :     ASSERT_NE (model0, model1);
    4209              : 
    4210            8 :     region_model model2 (node_mgr);
    4211            8 :     constraint_manager *cm2 = model2.get_constraints ();
    4212              :     /* Make the same change to cm2.  */
    4213            8 :     ADD_SAT_CONSTRAINT (model2, x, EQ_EXPR, y);
    4214            8 :     ASSERT_EQ (cm1->hash (), cm2->hash ());
    4215            8 :     ASSERT_EQ (*cm1, *cm2);
    4216              : 
    4217            8 :     ASSERT_EQ (model1.hash (), model2.hash ());
    4218            8 :     ASSERT_EQ (model1, model2);
    4219            8 :   }
    4220            8 : }
    4221              : 
    4222              : /* Verify tracking inequality of a variable against many constants.  */
    4223              : 
    4224              : static void
    4225            8 : test_many_constants ()
    4226              : {
    4227            8 :   symbolic::node_manager node_mgr;
    4228            8 :   auto &mgr = node_mgr.get_region_model_manager ();
    4229            8 :   program_point point (program_point::origin (mgr));
    4230            8 :   tree a = build_global_decl ("a", integer_type_node);
    4231              : 
    4232            8 :   region_model model (node_mgr);
    4233            8 :   auto_vec<tree> constants;
    4234          168 :   for (int i = 0; i < 20; i++)
    4235              :     {
    4236          160 :       tree constant = build_int_cst (integer_type_node, i);
    4237          160 :       constants.safe_push (constant);
    4238          160 :       ADD_SAT_CONSTRAINT (model, a, NE_EXPR, constant);
    4239              : 
    4240              :       /* Merge, and check the result.  */
    4241          160 :       region_model other (model);
    4242              : 
    4243          160 :       region_model merged (node_mgr);
    4244          160 :       ASSERT_TRUE (model.can_merge_with_p (other, point, &merged));
    4245          160 :       model.canonicalize ();
    4246          160 :       merged.canonicalize ();
    4247          160 :       ASSERT_EQ (model, merged);
    4248              : 
    4249         1840 :       for (int j = 0; j <= i; j++)
    4250         1680 :         ASSERT_CONDITION_TRUE (model, a, NE_EXPR, constants[j]);
    4251          160 :     }
    4252            8 : }
    4253              : 
    4254              : /* Verify that purging state relating to a variable doesn't leave stray
    4255              :    equivalence classes (after canonicalization).  */
    4256              : 
    4257              : static void
    4258            8 : test_purging (void)
    4259              : {
    4260            8 :   tree int_0 = integer_zero_node;
    4261            8 :   tree a = build_global_decl ("a", integer_type_node);
    4262            8 :   tree b = build_global_decl ("b", integer_type_node);
    4263              : 
    4264              :   /*  "a != 0".  */
    4265            8 :   {
    4266            8 :     symbolic::node_manager node_mgr;
    4267            8 :     region_model model (node_mgr);
    4268              : 
    4269            8 :     ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0);
    4270            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
    4271            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
    4272              : 
    4273              :     /* Purge state for "a".  */
    4274            8 :     const svalue *sval_a = model.get_rvalue (a, nullptr);
    4275            8 :     model.purge_state_involving (*sval_a, nullptr);
    4276            8 :     model.canonicalize ();
    4277              :     /* We should have an empty constraint_manager.  */
    4278            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
    4279            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
    4280            8 :   }
    4281              : 
    4282              :   /*  "a != 0" && "b != 0".  */
    4283            8 :   {
    4284            8 :     symbolic::node_manager node_mgr;
    4285            8 :     region_model model (node_mgr);
    4286              : 
    4287            8 :     ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0);
    4288            8 :     ADD_SAT_CONSTRAINT (model, b, NE_EXPR, int_0);
    4289            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 3);
    4290            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 2);
    4291              : 
    4292              :     /* Purge state for "a".  */
    4293            8 :     const svalue *sval_a = model.get_rvalue (a, nullptr);
    4294            8 :     model.purge_state_involving (*sval_a, nullptr);
    4295            8 :     model.canonicalize ();
    4296              :     /* We should just have the constraint/ECs involving b != 0.  */
    4297            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
    4298            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
    4299            8 :     ASSERT_CONDITION_TRUE (model, b, NE_EXPR, int_0);
    4300            8 :   }
    4301              : 
    4302              :   /*  "a != 0" && "b == 0".  */
    4303            8 :   {
    4304            8 :     symbolic::node_manager node_mgr;
    4305            8 :     region_model model (node_mgr);
    4306              : 
    4307            8 :     ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0);
    4308            8 :     ADD_SAT_CONSTRAINT (model, b, EQ_EXPR, int_0);
    4309            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
    4310            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
    4311              : 
    4312              :     /* Purge state for "a".  */
    4313            8 :     const svalue *sval_a = model.get_rvalue (a, nullptr);
    4314            8 :     model.purge_state_involving (*sval_a, nullptr);
    4315            8 :     model.canonicalize ();
    4316              :     /* We should just have the EC involving b == 0.  */
    4317            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
    4318            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
    4319            8 :     ASSERT_CONDITION_TRUE (model, b, EQ_EXPR, int_0);
    4320            8 :   }
    4321              : 
    4322              :   /*  "a == 0".  */
    4323            8 :   {
    4324            8 :     symbolic::node_manager node_mgr;
    4325            8 :     region_model model (node_mgr);
    4326              : 
    4327            8 :     ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0);
    4328            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
    4329            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
    4330              : 
    4331              :     /* Purge state for "a".  */
    4332            8 :     const svalue *sval_a = model.get_rvalue (a, nullptr);
    4333            8 :     model.purge_state_involving (*sval_a, nullptr);
    4334            8 :     model.canonicalize ();
    4335              :     /* We should have an empty constraint_manager.  */
    4336            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
    4337            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
    4338            8 :   }
    4339              : 
    4340              :   /*  "a == 0" && "b != 0".  */
    4341            8 :   {
    4342            8 :     symbolic::node_manager node_mgr;
    4343            8 :     region_model model (node_mgr);
    4344              : 
    4345            8 :     ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0);
    4346            8 :     ADD_SAT_CONSTRAINT (model, b, NE_EXPR, int_0);
    4347            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
    4348            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
    4349              : 
    4350              :     /* Purge state for "a".  */
    4351            8 :     const svalue *sval_a = model.get_rvalue (a, nullptr);
    4352            8 :     model.purge_state_involving (*sval_a, nullptr);
    4353            8 :     model.canonicalize ();
    4354              :     /* We should just have the constraint/ECs involving b != 0.  */
    4355            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
    4356            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
    4357            8 :     ASSERT_CONDITION_TRUE (model, b, NE_EXPR, int_0);
    4358            8 :   }
    4359              : 
    4360              :   /*  "a == 0" && "b == 0".  */
    4361            8 :   {
    4362            8 :     symbolic::node_manager node_mgr;
    4363            8 :     region_model model (node_mgr);
    4364              : 
    4365            8 :     ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0);
    4366            8 :     ADD_SAT_CONSTRAINT (model, b, EQ_EXPR, int_0);
    4367            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
    4368            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
    4369              : 
    4370              :     /* Purge state for "a".  */
    4371            8 :     const svalue *sval_a = model.get_rvalue (a, nullptr);
    4372            8 :     model.purge_state_involving (*sval_a, nullptr);
    4373            8 :     model.canonicalize ();
    4374              :     /* We should just have the EC involving b == 0.  */
    4375            8 :     ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
    4376            8 :     ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
    4377            8 :     ASSERT_CONDITION_TRUE (model, b, EQ_EXPR, int_0);
    4378            8 :   }
    4379            8 : }
    4380              : 
    4381              : /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ.  */
    4382              : 
    4383              : static void
    4384           64 : assert_dump_bounded_range_eq (const location &loc,
    4385              :                               const bounded_range &range,
    4386              :                               const char *expected)
    4387              : {
    4388           64 :   auto_fix_quotes sentinel;
    4389           64 :   pretty_printer pp;
    4390           64 :   pp_format_decoder (&pp) = default_tree_printer;
    4391           64 :   range.dump_to_pp (&pp, false);
    4392           64 :   ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
    4393           64 : }
    4394              : 
    4395              : /* Assert that BR.dump (false) is EXPECTED.  */
    4396              : 
    4397              : #define ASSERT_DUMP_BOUNDED_RANGE_EQ(BR, EXPECTED) \
    4398              :   SELFTEST_BEGIN_STMT                                                   \
    4399              :   assert_dump_bounded_range_eq ((SELFTEST_LOCATION), (BR), (EXPECTED)); \
    4400              :   SELFTEST_END_STMT
    4401              : 
    4402              : /* Verify that bounded_range works as expected.  */
    4403              : 
    4404              : static void
    4405            8 : test_bounded_range ()
    4406              : {
    4407            8 :   tree u8_0 = build_int_cst (unsigned_char_type_node, 0);
    4408            8 :   tree u8_1 = build_int_cst (unsigned_char_type_node, 1);
    4409            8 :   tree u8_64 = build_int_cst (unsigned_char_type_node, 64);
    4410            8 :   tree u8_128 = build_int_cst (unsigned_char_type_node, 128);
    4411            8 :   tree u8_255 = build_int_cst (unsigned_char_type_node, 255);
    4412              : 
    4413            8 :   tree s8_0 = build_int_cst (signed_char_type_node, 0);
    4414            8 :   tree s8_1 = build_int_cst (signed_char_type_node, 1);
    4415            8 :   tree s8_2 = build_int_cst (signed_char_type_node, 2);
    4416              : 
    4417            8 :   bounded_range br_u8_0 (u8_0, u8_0);
    4418            8 :   ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0, "0");
    4419            8 :   ASSERT_TRUE (br_u8_0.contains_p (u8_0));
    4420            8 :   ASSERT_FALSE (br_u8_0.contains_p (u8_1));
    4421            8 :   ASSERT_TRUE (br_u8_0.contains_p (s8_0));
    4422            8 :   ASSERT_FALSE (br_u8_0.contains_p (s8_1));
    4423              : 
    4424            8 :   bounded_range br_u8_0_1 (u8_0, u8_1);
    4425            8 :   ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0_1, "[0, 1]");
    4426              : 
    4427            8 :   bounded_range tmp (NULL_TREE, NULL_TREE);
    4428            8 :   ASSERT_TRUE (br_u8_0.intersects_p (br_u8_0_1, &tmp));
    4429            8 :   ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "0");
    4430              : 
    4431            8 :   bounded_range br_u8_64_128 (u8_64, u8_128);
    4432            8 :   ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_64_128, "[64, 128]");
    4433              : 
    4434            8 :   ASSERT_FALSE (br_u8_0.intersects_p (br_u8_64_128, nullptr));
    4435            8 :   ASSERT_FALSE (br_u8_64_128.intersects_p (br_u8_0, nullptr));
    4436              : 
    4437            8 :   bounded_range br_u8_128_255 (u8_128, u8_255);
    4438            8 :   ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_128_255, "[128, 255]");
    4439            8 :   ASSERT_TRUE (br_u8_128_255.intersects_p (br_u8_64_128, &tmp));
    4440            8 :   ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "128");
    4441              : 
    4442            8 :   bounded_range br_s8_2 (s8_2, s8_2);
    4443            8 :   ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2, "2");
    4444            8 :   bounded_range br_s8_2_u8_255 (s8_2, u8_255);
    4445            8 :   ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2_u8_255, "[2, 255]");
    4446            8 : }
    4447              : 
    4448              : /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ.  */
    4449              : 
    4450              : static void
    4451          208 : assert_dump_bounded_ranges_eq (const location &loc,
    4452              :                                const bounded_ranges *ranges,
    4453              :                                const char *expected)
    4454              : {
    4455          208 :   auto_fix_quotes sentinel;
    4456          208 :   pretty_printer pp;
    4457          208 :   pp_format_decoder (&pp) = default_tree_printer;
    4458          208 :   ranges->dump_to_pp (&pp, false);
    4459          208 :   ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
    4460          208 : }
    4461              : 
    4462              : /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ.  */
    4463              : 
    4464              : static void
    4465           96 : assert_dump_bounded_ranges_eq (const location &loc,
    4466              :                                const bounded_ranges &ranges,
    4467              :                                const char *expected)
    4468              : {
    4469           96 :   auto_fix_quotes sentinel;
    4470           96 :   pretty_printer pp;
    4471           96 :   pp_format_decoder (&pp) = default_tree_printer;
    4472           96 :   ranges.dump_to_pp (&pp, false);
    4473           96 :   ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
    4474           96 : }
    4475              : 
    4476              : /* Assert that BRS.dump (false) is EXPECTED.  */
    4477              : 
    4478              : #define ASSERT_DUMP_BOUNDED_RANGES_EQ(BRS, EXPECTED) \
    4479              :   SELFTEST_BEGIN_STMT                                                   \
    4480              :   assert_dump_bounded_ranges_eq ((SELFTEST_LOCATION), (BRS), (EXPECTED)); \
    4481              :   SELFTEST_END_STMT
    4482              : 
    4483              : /* Verify that the bounded_ranges class works as expected.  */
    4484              : 
    4485              : static void
    4486            8 : test_bounded_ranges ()
    4487              : {
    4488            8 :   bounded_ranges_manager mgr;
    4489              : 
    4490            8 :   tree ch0 = build_int_cst (unsigned_char_type_node, 0);
    4491            8 :   tree ch1 = build_int_cst (unsigned_char_type_node, 1);
    4492            8 :   tree ch2 = build_int_cst (unsigned_char_type_node, 2);
    4493            8 :   tree ch3 = build_int_cst (unsigned_char_type_node, 3);
    4494            8 :   tree ch128 = build_int_cst (unsigned_char_type_node, 128);
    4495            8 :   tree ch129 = build_int_cst (unsigned_char_type_node, 129);
    4496            8 :   tree ch254 = build_int_cst (unsigned_char_type_node, 254);
    4497            8 :   tree ch255 = build_int_cst (unsigned_char_type_node, 255);
    4498              : 
    4499            8 :   const bounded_ranges *empty = mgr.get_or_create_empty ();
    4500            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (empty, "{}");
    4501              : 
    4502            8 :   const bounded_ranges *point0 = mgr.get_or_create_point (ch0);
    4503            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (point0, "{0}");
    4504              : 
    4505            8 :   const bounded_ranges *point1 = mgr.get_or_create_point (ch1);
    4506            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (point1, "{1}");
    4507              : 
    4508            8 :   const bounded_ranges *point2 = mgr.get_or_create_point (ch2);
    4509            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (point2, "{2}");
    4510              : 
    4511            8 :   const bounded_ranges *range0_128 = mgr.get_or_create_range (ch0, ch128);
    4512            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_128, "{[0, 128]}");
    4513              : 
    4514            8 :   const bounded_ranges *range0_255 = mgr.get_or_create_range (ch0, ch255);
    4515            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_255, "{[0, 255]}");
    4516              : 
    4517            8 :   ASSERT_FALSE (empty->contain_p (ch0));
    4518            8 :   ASSERT_FALSE (empty->contain_p (ch1));
    4519            8 :   ASSERT_FALSE (empty->contain_p (ch255));
    4520              : 
    4521            8 :   ASSERT_TRUE (point0->contain_p (ch0));
    4522            8 :   ASSERT_FALSE (point0->contain_p (ch1));
    4523            8 :   ASSERT_FALSE (point0->contain_p (ch255));
    4524              : 
    4525            8 :   ASSERT_FALSE (point1->contain_p (ch0));
    4526            8 :   ASSERT_TRUE (point1->contain_p (ch1));
    4527            8 :   ASSERT_FALSE (point0->contain_p (ch255));
    4528              : 
    4529            8 :   ASSERT_TRUE (range0_128->contain_p (ch0));
    4530            8 :   ASSERT_TRUE (range0_128->contain_p (ch1));
    4531            8 :   ASSERT_TRUE (range0_128->contain_p (ch128));
    4532            8 :   ASSERT_FALSE (range0_128->contain_p (ch129));
    4533            8 :   ASSERT_FALSE (range0_128->contain_p (ch254));
    4534            8 :   ASSERT_FALSE (range0_128->contain_p (ch255));
    4535              : 
    4536            8 :   const bounded_ranges *inv0_128
    4537            8 :     = mgr.get_or_create_inverse (range0_128, unsigned_char_type_node);
    4538            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (inv0_128, "{[129, 255]}");
    4539              : 
    4540            8 :   const bounded_ranges *range128_129 = mgr.get_or_create_range (ch128, ch129);
    4541            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (range128_129, "{[128, 129]}");
    4542              : 
    4543            8 :   const bounded_ranges *inv128_129
    4544            8 :     = mgr.get_or_create_inverse (range128_129, unsigned_char_type_node);
    4545            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (inv128_129, "{[0, 127], [130, 255]}");
    4546              : 
    4547              :   /* Intersection.  */
    4548            8 :   {
    4549              :     /* Intersection of disjoint ranges should be empty set.  */
    4550            8 :     const bounded_ranges *intersect0_1
    4551            8 :       = mgr.get_or_create_intersection (point0, point1);
    4552            8 :     ASSERT_DUMP_BOUNDED_RANGES_EQ (intersect0_1, "{}");
    4553              :   }
    4554              : 
    4555              :   /* Various tests of "union of ranges".  */
    4556            8 :   {
    4557            8 :     {
    4558              :       /* Touching points should be merged into a range.  */
    4559            8 :       auto_vec <const bounded_ranges *> v;
    4560            8 :       v.safe_push (point0);
    4561            8 :       v.safe_push (point1);
    4562            8 :       const bounded_ranges *union_0_and_1 = mgr.get_or_create_union (v);
    4563            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (union_0_and_1, "{[0, 1]}");
    4564            8 :     }
    4565              : 
    4566            8 :     {
    4567              :       /* Overlapping and out-of-order.  */
    4568            8 :       auto_vec <const bounded_ranges *> v;
    4569            8 :       v.safe_push (inv0_128); // {[129, 255]}
    4570            8 :       v.safe_push (range128_129);
    4571            8 :       const bounded_ranges *union_129_255_and_128_129
    4572            8 :         = mgr.get_or_create_union (v);
    4573            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (union_129_255_and_128_129, "{[128, 255]}");
    4574            8 :     }
    4575              : 
    4576            8 :     {
    4577              :       /* Union of R and inverse(R) should be full range of type.  */
    4578            8 :       auto_vec <const bounded_ranges *> v;
    4579            8 :       v.safe_push (range128_129);
    4580            8 :       v.safe_push (inv128_129);
    4581            8 :       const bounded_ranges *union_ = mgr.get_or_create_union (v);
    4582            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{[0, 255]}");
    4583            8 :     }
    4584              : 
    4585              :     /* Union with an endpoint.  */
    4586            8 :     {
    4587            8 :       const bounded_ranges *range2_to_255
    4588            8 :         = mgr.get_or_create_range (ch2, ch255);
    4589            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (range2_to_255, "{[2, 255]}");
    4590            8 :       auto_vec <const bounded_ranges *> v;
    4591            8 :       v.safe_push (point0);
    4592            8 :       v.safe_push (point2);
    4593            8 :       v.safe_push (range2_to_255);
    4594            8 :       const bounded_ranges *union_ = mgr.get_or_create_union (v);
    4595            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{0, [2, 255]}");
    4596            8 :     }
    4597              : 
    4598              :     /* Construct from vector of bounded_range.  */
    4599            8 :     {
    4600            8 :       auto_vec<bounded_range> v;
    4601            8 :       v.safe_push (bounded_range (ch2, ch2));
    4602            8 :       v.safe_push (bounded_range (ch0, ch0));
    4603            8 :       v.safe_push (bounded_range (ch2, ch255));
    4604            8 :       bounded_ranges br (v);
    4605            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (&br, "{0, [2, 255]}");
    4606            8 :     }
    4607              :   }
    4608              : 
    4609              :   /* Various tests of "inverse".  */
    4610            8 :   {
    4611            8 :     {
    4612            8 :       const bounded_ranges *range_1_to_3 = mgr.get_or_create_range (ch1, ch3);
    4613            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_3, "{[1, 3]}");
    4614            8 :       const bounded_ranges *inv
    4615            8 :         = mgr.get_or_create_inverse (range_1_to_3, unsigned_char_type_node);
    4616            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0, [4, 255]}");
    4617              :     }
    4618            8 :     {
    4619            8 :       const bounded_ranges *range_1_to_255
    4620            8 :         = mgr.get_or_create_range (ch1, ch255);
    4621            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_255, "{[1, 255]}");
    4622            8 :       const bounded_ranges *inv
    4623            8 :         = mgr.get_or_create_inverse (range_1_to_255, unsigned_char_type_node);
    4624            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0}");
    4625              :     }
    4626            8 :     {
    4627            8 :       const bounded_ranges *range_0_to_254
    4628            8 :         = mgr.get_or_create_range (ch0, ch254);
    4629            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (range_0_to_254, "{[0, 254]}");
    4630            8 :       const bounded_ranges *inv
    4631            8 :         = mgr.get_or_create_inverse (range_0_to_254, unsigned_char_type_node);
    4632            8 :       ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{255}");
    4633              :     }
    4634              :   }
    4635              : 
    4636              :   /* "case 'a'-'z': case 'A-Z':" vs "default:", for ASCII.  */
    4637            8 :   {
    4638            8 :     tree ch65 = build_int_cst (unsigned_char_type_node, 65);
    4639            8 :     tree ch90 = build_int_cst (unsigned_char_type_node, 90);
    4640              : 
    4641            8 :     tree ch97 = build_int_cst (unsigned_char_type_node, 97);
    4642            8 :     tree ch122 = build_int_cst (unsigned_char_type_node, 122);
    4643              : 
    4644            8 :     const bounded_ranges *A_to_Z = mgr.get_or_create_range (ch65, ch90);
    4645            8 :     ASSERT_DUMP_BOUNDED_RANGES_EQ (A_to_Z, "{[65, 90]}");
    4646            8 :     const bounded_ranges *a_to_z = mgr.get_or_create_range (ch97, ch122);
    4647            8 :     ASSERT_DUMP_BOUNDED_RANGES_EQ (a_to_z, "{[97, 122]}");
    4648            8 :     auto_vec <const bounded_ranges *> v;
    4649            8 :     v.safe_push (A_to_Z);
    4650            8 :     v.safe_push (a_to_z);
    4651            8 :     const bounded_ranges *label_ranges = mgr.get_or_create_union (v);
    4652            8 :     ASSERT_DUMP_BOUNDED_RANGES_EQ (label_ranges, "{[65, 90], [97, 122]}");
    4653            8 :     const bounded_ranges *default_ranges
    4654            8 :       = mgr.get_or_create_inverse (label_ranges, unsigned_char_type_node);
    4655            8 :     ASSERT_DUMP_BOUNDED_RANGES_EQ (default_ranges,
    4656              :                                    "{[0, 64], [91, 96], [123, 255]}");
    4657            8 :   }
    4658              : 
    4659              :   /* Verify ranges from ops.  */
    4660            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (EQ_EXPR, ch128),
    4661              :                                  "{128}");
    4662            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch128),
    4663              :                                  "{[0, 127], [129, 255]}");
    4664            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch128),
    4665              :                                  "{[0, 127]}");
    4666            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch128),
    4667              :                                  "{[0, 128]}");
    4668            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch128),
    4669              :                                  "{[128, 255]}");
    4670            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch128),
    4671              :                                  "{[129, 255]}");
    4672              :   /* Ops at endpoints of type ranges.  */
    4673            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch0),
    4674              :                                  "{0}");
    4675            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch0),
    4676              :                                  "{}");
    4677            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch0),
    4678              :                                  "{[1, 255]}");
    4679            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch255),
    4680              :                                  "{255}");
    4681            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch255),
    4682              :                                  "{}");
    4683            8 :   ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch255),
    4684              :                                  "{[0, 254]}");
    4685              : 
    4686              :   /* Verify that instances are consolidated by mgr.  */
    4687            8 :   ASSERT_EQ (mgr.get_or_create_point (ch0),
    4688              :              mgr.get_or_create_point (ch0));
    4689            8 :   ASSERT_NE (mgr.get_or_create_point (ch0),
    4690              :              mgr.get_or_create_point (ch1));
    4691            8 : }
    4692              : 
    4693              : /* Verify that we can handle sufficiently simple bitmasking operations.  */
    4694              : 
    4695              : static void
    4696            8 : test_bits (void)
    4697              : {
    4698            8 :   symbolic::node_manager node_mgr;
    4699              : 
    4700            8 :   tree int_0 = integer_zero_node;
    4701            8 :   tree int_0x80 = build_int_cst (integer_type_node, 0x80);
    4702            8 :   tree int_0xff = build_int_cst (integer_type_node, 0xff);
    4703            8 :   tree x = build_global_decl ("x", integer_type_node);
    4704              : 
    4705            8 :   tree x_bit_and_0x80 = build2 (BIT_AND_EXPR, integer_type_node, x, int_0x80);
    4706            8 :   tree x_bit_and_0xff = build2 (BIT_AND_EXPR, integer_type_node, x, int_0xff);
    4707              : 
    4708              :   /* "x & 0x80 == 0x80".  */
    4709            8 :   {
    4710            8 :     region_model model (node_mgr);
    4711            8 :     ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, EQ_EXPR, int_0x80);
    4712            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
    4713            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
    4714            8 :   }
    4715              : 
    4716              :   /* "x & 0x80 != 0x80".  */
    4717            8 :   {
    4718            8 :     region_model model (node_mgr);
    4719            8 :     ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, NE_EXPR, int_0x80);
    4720            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
    4721            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
    4722            8 :   }
    4723              : 
    4724              :   /* "x & 0x80 == 0".  */
    4725            8 :   {
    4726            8 :     region_model model (node_mgr);
    4727              : 
    4728            8 :     ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, EQ_EXPR, int_0);
    4729            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
    4730            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
    4731            8 :   }
    4732              : 
    4733              :   /* "x & 0x80 != 0".  */
    4734            8 :   {
    4735            8 :     region_model model (node_mgr);
    4736            8 :     ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, NE_EXPR, int_0);
    4737            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
    4738            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
    4739            8 :   }
    4740              : 
    4741              :   /* More that one bit in the mask.  */
    4742              : 
    4743              :   /* "x & 0xff == 0x80".  */
    4744            8 :   {
    4745            8 :     region_model model (node_mgr);
    4746            8 :     ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, EQ_EXPR, int_0x80);
    4747            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
    4748            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
    4749            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0xff);
    4750            8 :   }
    4751              : 
    4752              :   /* "x & 0xff != 0x80".  */
    4753            8 :   {
    4754            8 :     region_model model (node_mgr);
    4755            8 :     ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, NE_EXPR, int_0x80);
    4756            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
    4757            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
    4758            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0xff);
    4759            8 :   }
    4760              : 
    4761              :   /* "x & 0xff == 0".  */
    4762            8 :   {
    4763            8 :     region_model model (node_mgr);
    4764              : 
    4765            8 :     ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, EQ_EXPR, int_0);
    4766            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
    4767            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
    4768            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0xff);
    4769            8 :   }
    4770              : 
    4771              :   /* "x & 0xff != 0".  */
    4772            8 :   {
    4773            8 :     region_model model (node_mgr);
    4774            8 :     ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, NE_EXPR, int_0);
    4775            8 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
    4776            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
    4777            8 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0xff);
    4778            8 :   }
    4779            8 : }
    4780              : 
    4781              : /* Run the selftests in this file, temporarily overriding
    4782              :    flag_analyzer_transitivity with TRANSITIVITY.  */
    4783              : 
    4784              : static void
    4785            8 : run_constraint_manager_tests (bool transitivity)
    4786              : {
    4787            8 :   int saved_flag_analyzer_transitivity = flag_analyzer_transitivity;
    4788            8 :   flag_analyzer_transitivity = transitivity;
    4789              : 
    4790            8 :   test_range ();
    4791            8 :   test_constraint_conditions ();
    4792            8 :   if (flag_analyzer_transitivity)
    4793              :     {
    4794              :       /* These selftests assume transitivity.  */
    4795            4 :       test_transitivity ();
    4796              :     }
    4797            8 :   test_constant_comparisons ();
    4798            8 :   test_constraint_impl ();
    4799            8 :   test_equality ();
    4800            8 :   test_many_constants ();
    4801            8 :   test_purging ();
    4802            8 :   test_bounded_range ();
    4803            8 :   test_bounded_ranges ();
    4804            8 :   test_bits ();
    4805              : 
    4806            8 :   flag_analyzer_transitivity = saved_flag_analyzer_transitivity;
    4807            8 : }
    4808              : 
    4809              : /* Run all of the selftests within this file.  */
    4810              : 
    4811              : void
    4812            4 : analyzer_constraint_manager_cc_tests ()
    4813              : {
    4814              :   /* Run the tests twice: with and without transitivity.  */
    4815            4 :   run_constraint_manager_tests (true);
    4816            4 :   run_constraint_manager_tests (false);
    4817            4 : }
    4818              : 
    4819              : } // namespace selftest
    4820              : 
    4821              : #endif /* CHECKING_P */
    4822              : 
    4823              : } // namespace ana
    4824              : 
    4825              : #endif /* #if ENABLE_ANALYZER */
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.