LCOV - code coverage report
Current view: top level - gcc/analyzer - constraint-manager.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 87.7 % 2498 2191
Test Date: 2024-11-30 13:30:02 Functions: 76.6 % 154 118
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

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

Generated by: LCOV version 2.1-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.