LCOV - code coverage report
Current view: top level - gcc/analyzer - constraint-manager.cc (source / functions) Hit Total Coverage
Test: gcc.info Lines: 944 1064 88.7 %
Date: 2020-03-28 11:57:23 Functions: 51 62 82.3 %
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-2020 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                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "tree.h"
      25                 :            : #include "function.h"
      26                 :            : #include "basic-block.h"
      27                 :            : #include "gimple.h"
      28                 :            : #include "gimple-iterator.h"
      29                 :            : #include "fold-const.h"
      30                 :            : #include "selftest.h"
      31                 :            : #include "diagnostic-core.h"
      32                 :            : #include "graphviz.h"
      33                 :            : #include "function.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 "tristate.h"
      43                 :            : #include "analyzer/region-model.h"
      44                 :            : #include "analyzer/constraint-manager.h"
      45                 :            : #include "analyzer/analyzer-selftests.h"
      46                 :            : 
      47                 :            : #if ENABLE_ANALYZER
      48                 :            : 
      49                 :            : namespace ana {
      50                 :            : 
      51                 :            : /* One of the end-points of a range.  */
      52                 :            : 
      53                 :            : struct bound
      54                 :            : {
      55                 :            :   bound () : m_constant (NULL_TREE), m_closed (false) {}
      56                 :        100 :   bound (tree constant, bool closed)
      57                 :        100 :   : m_constant (constant), m_closed (closed) {}
      58                 :            : 
      59                 :            :   void ensure_closed (bool is_upper);
      60                 :            : 
      61                 :            :   const char * get_relation_as_str () const;
      62                 :            : 
      63                 :            :   tree m_constant;
      64                 :            :   bool m_closed;
      65                 :            : };
      66                 :            : 
      67                 :            : /* A range of values, used for determining if a value has been
      68                 :            :    constrained to just one possible constant value.  */
      69                 :            : 
      70                 :            : struct range
      71                 :            : {
      72                 :            :   range () : m_lower_bound (), m_upper_bound () {}
      73                 :        100 :   range (const bound &lower, const bound &upper)
      74                 :        100 :   : m_lower_bound (lower), m_upper_bound (upper) {}
      75                 :            : 
      76                 :            :   void dump (pretty_printer *pp) const;
      77                 :            : 
      78                 :            :   bool constrained_to_single_element (tree *out);
      79                 :            : 
      80                 :            :   bound m_lower_bound;
      81                 :            :   bound m_upper_bound;
      82                 :            : };
      83                 :            : 
      84                 :            : /* struct bound.  */
      85                 :            : 
      86                 :            : /* Ensure that this bound is closed by converting an open bound to a
      87                 :            :    closed one.  */
      88                 :            : 
      89                 :            : void
      90                 :        200 : bound::ensure_closed (bool is_upper)
      91                 :            : {
      92                 :        200 :   if (!m_closed)
      93                 :            :     {
      94                 :            :       /* Offset by 1 in the appropriate direction.
      95                 :            :          For example, convert 3 < x into 4 <= x,
      96                 :            :          and convert x < 5 into x <= 4.  */
      97                 :        101 :       gcc_assert (CONSTANT_CLASS_P (m_constant));
      98                 :        198 :       m_constant = fold_build2 (is_upper ? MINUS_EXPR : PLUS_EXPR,
      99                 :            :                                 TREE_TYPE (m_constant),
     100                 :            :                                 m_constant, integer_one_node);
     101                 :        101 :       gcc_assert (CONSTANT_CLASS_P (m_constant));
     102                 :        101 :       m_closed = true;
     103                 :            :     }
     104                 :        200 : }
     105                 :            : 
     106                 :            : /* Get "<=" vs "<" for this bound.  */
     107                 :            : 
     108                 :            : const char *
     109                 :          0 : bound::get_relation_as_str () const
     110                 :            : {
     111                 :          0 :   if (m_closed)
     112                 :            :     return "<=";
     113                 :            :   else
     114                 :          0 :     return "<";
     115                 :            : }
     116                 :            : 
     117                 :            : /* struct range.  */
     118                 :            : 
     119                 :            : /* Dump this range to PP, which must support %E for tree.  */
     120                 :            : 
     121                 :            : void
     122                 :          0 : range::dump (pretty_printer *pp) const
     123                 :            : {
     124                 :          0 :   pp_printf (pp, "%qE %s x %s %qE",
     125                 :          0 :              m_lower_bound.m_constant,
     126                 :            :              m_lower_bound.get_relation_as_str (),
     127                 :            :              m_upper_bound.get_relation_as_str (),
     128                 :          0 :              m_upper_bound.m_constant);
     129                 :          0 : }
     130                 :            : 
     131                 :            : /* Determine if there is only one possible value for this range.
     132                 :            :    If so, return true and write the constant to *OUT.
     133                 :            :    Otherwise, return false.  */
     134                 :            : 
     135                 :            : bool
     136                 :        100 : range::constrained_to_single_element (tree *out)
     137                 :            : {
     138                 :        100 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (m_lower_bound.m_constant)))
     139                 :            :     return false;
     140                 :        100 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (m_upper_bound.m_constant)))
     141                 :            :     return false;
     142                 :            : 
     143                 :            :   /* Convert any open bounds to closed bounds.  */
     144                 :        100 :   m_lower_bound.ensure_closed (false);
     145                 :        100 :   m_upper_bound.ensure_closed (true);
     146                 :            : 
     147                 :            :   // Are they equal?
     148                 :        100 :   tree comparison = fold_binary (EQ_EXPR, boolean_type_node,
     149                 :            :                                  m_lower_bound.m_constant,
     150                 :            :                                  m_upper_bound.m_constant);
     151                 :        100 :   if (comparison == boolean_true_node)
     152                 :            :     {
     153                 :         16 :       *out = m_lower_bound.m_constant;
     154                 :         16 :       return true;
     155                 :            :     }
     156                 :            :   else
     157                 :            :     return false;
     158                 :            : }
     159                 :            : 
     160                 :            : /* class equiv_class.  */
     161                 :            : 
     162                 :            : /* equiv_class's default ctor.  */
     163                 :            : 
     164                 :    1148720 : equiv_class::equiv_class ()
     165                 :    1148720 : : m_constant (NULL_TREE), m_cst_sid (svalue_id::null ()),
     166                 :    1148720 :   m_vars ()
     167                 :            : {
     168                 :    1148720 : }
     169                 :            : 
     170                 :            : /* equiv_class's copy ctor.  */
     171                 :            : 
     172                 :    1474980 : equiv_class::equiv_class (const equiv_class &other)
     173                 :    1474980 : : m_constant (other.m_constant), m_cst_sid (other.m_cst_sid),
     174                 :    1474980 :   m_vars (other.m_vars.length ())
     175                 :            : {
     176                 :            :   int i;
     177                 :            :   svalue_id *sid;
     178                 :    2290640 :   FOR_EACH_VEC_ELT (other.m_vars, i, sid)
     179                 :     815655 :     m_vars.quick_push (*sid);
     180                 :    1474980 : }
     181                 :            : 
     182                 :            : /* Print an all-on-one-line representation of this equiv_class to PP,
     183                 :            :    which must support %E for trees.  */
     184                 :            : 
     185                 :            : void
     186                 :          0 : equiv_class::print (pretty_printer *pp) const
     187                 :            : {
     188                 :          0 :   pp_character (pp, '{');
     189                 :          0 :   int i;
     190                 :          0 :   svalue_id *sid;
     191                 :          0 :   FOR_EACH_VEC_ELT (m_vars, i, sid)
     192                 :            :     {
     193                 :          0 :       if (i > 0)
     194                 :          0 :         pp_string (pp, " == ");
     195                 :          0 :       sid->print (pp);
     196                 :            :     }
     197                 :          0 :   if (m_constant)
     198                 :            :     {
     199                 :          0 :       if (i > 0)
     200                 :          0 :         pp_string (pp, " == ");
     201                 :          0 :       pp_printf (pp, "%qE", m_constant);
     202                 :            :     }
     203                 :          0 :   pp_character (pp, '}');
     204                 :          0 : }
     205                 :            : 
     206                 :            : /* Generate a hash value for this equiv_class.  */
     207                 :            : 
     208                 :            : hashval_t
     209                 :     235425 : equiv_class::hash () const
     210                 :            : {
     211                 :     235425 :   inchash::hash hstate;
     212                 :     235425 :   int i;
     213                 :     235425 :   svalue_id *sid;
     214                 :            : 
     215                 :     235425 :   inchash::add_expr (m_constant, hstate);
     216                 :     496670 :   FOR_EACH_VEC_ELT (m_vars, i, sid)
     217                 :     261245 :     inchash::add (*sid, hstate);
     218                 :     235425 :   return hstate.end ();
     219                 :            : }
     220                 :            : 
     221                 :            : /* Equality operator for equiv_class.  */
     222                 :            : 
     223                 :            : bool
     224                 :      78920 : equiv_class::operator== (const equiv_class &other)
     225                 :            : {
     226                 :      78920 :   if (m_constant != other.m_constant)
     227                 :            :     return false; // TODO: use tree equality here?
     228                 :            : 
     229                 :            :   /* FIXME: should we compare m_cst_sid?  */
     230                 :            : 
     231                 :     236667 :   if (m_vars.length () != other.m_vars.length ())
     232                 :            :     return false;
     233                 :            : 
     234                 :            :   int i;
     235                 :            :   svalue_id *sid;
     236                 :     166142 :   FOR_EACH_VEC_ELT (m_vars, i, sid)
     237                 :      87293 :     if (! (*sid == other.m_vars[i]))
     238                 :            :       return false;
     239                 :            : 
     240                 :            :   return true;
     241                 :            : }
     242                 :            : 
     243                 :            : /* Add SID to this equiv_class, using CM to check if it's a constant.  */
     244                 :            : 
     245                 :            : void
     246                 :     111181 : equiv_class::add (svalue_id sid, const constraint_manager &cm)
     247                 :            : {
     248                 :     111181 :   gcc_assert (!sid.null_p ());
     249                 :     111181 :   if (tree cst = cm.maybe_get_constant (sid))
     250                 :            :     {
     251                 :      68071 :       gcc_assert (CONSTANT_CLASS_P (cst));
     252                 :            :       /* FIXME: should we canonicalize which svalue is the constant
     253                 :            :          when there are multiple equal constants?  */
     254                 :      68071 :       m_constant = cst;
     255                 :      68071 :       m_cst_sid = sid;
     256                 :            :     }
     257                 :     111181 :   m_vars.safe_push (sid);
     258                 :     111181 : }
     259                 :            : 
     260                 :            : /* Remove SID from this equivalence class.
     261                 :            :    Return true if SID was the last var in the equivalence class (suggesting
     262                 :            :    a possible leak).  */
     263                 :            : 
     264                 :            : bool
     265                 :       5895 : equiv_class::del (svalue_id sid)
     266                 :            : {
     267                 :       5895 :   gcc_assert (!sid.null_p ());
     268                 :       5895 :   gcc_assert (sid != m_cst_sid);
     269                 :            : 
     270                 :            :   int i;
     271                 :            :   svalue_id *iv;
     272                 :       6313 :   FOR_EACH_VEC_ELT (m_vars, i, iv)
     273                 :            :     {
     274                 :       6313 :       if (*iv == sid)
     275                 :            :         {
     276                 :       5895 :           m_vars[i] = m_vars[m_vars.length () - 1];
     277                 :       5895 :           m_vars.pop ();
     278                 :       5895 :           return m_vars.length () == 0;
     279                 :            :         }
     280                 :            :     }
     281                 :            : 
     282                 :            :   /* SID must be in the class.  */
     283                 :          0 :   gcc_unreachable ();
     284                 :            :   return false;
     285                 :            : }
     286                 :            : 
     287                 :            : /* Get a representative member of this class, for handling cases
     288                 :            :    where the IDs can change mid-traversal.  */
     289                 :            : 
     290                 :            : svalue_id
     291                 :    2865710 : equiv_class::get_representative () const
     292                 :            : {
     293                 :    2865710 :   if (!m_cst_sid.null_p ())
     294                 :    1527120 :     return m_cst_sid;
     295                 :            :   else
     296                 :            :     {
     297                 :    1338590 :       gcc_assert (m_vars.length () > 0);
     298                 :    1338590 :       return m_vars[0];
     299                 :            :     }
     300                 :            : }
     301                 :            : 
     302                 :            : /* Remap all svalue_ids within this equiv_class using MAP.  */
     303                 :            : 
     304                 :            : void
     305                 :     244279 : equiv_class::remap_svalue_ids (const svalue_id_map &map)
     306                 :            : {
     307                 :     244279 :   int i;
     308                 :     244279 :   svalue_id *iv;
     309                 :     514813 :   FOR_EACH_VEC_ELT (m_vars, i, iv)
     310                 :     270534 :     map.update (iv);
     311                 :     244279 :   map.update (&m_cst_sid);
     312                 :     244279 : }
     313                 :            : 
     314                 :            : /* Comparator for use by equiv_class::canonicalize.  */
     315                 :            : 
     316                 :            : static int
     317                 :      78156 : svalue_id_cmp_by_id (const void *p1, const void *p2)
     318                 :            : {
     319                 :      78156 :   const svalue_id *sid1 = (const svalue_id *)p1;
     320                 :      78156 :   const svalue_id *sid2 = (const svalue_id *)p2;
     321                 :      78156 :   return sid1->as_int () - sid2->as_int ();
     322                 :            : }
     323                 :            : 
     324                 :            : /* Sort the svalues_ids within this equiv_class.  */
     325                 :            : 
     326                 :            : void
     327                 :     159231 : equiv_class::canonicalize ()
     328                 :            : {
     329                 :     159231 :   m_vars.qsort (svalue_id_cmp_by_id);
     330                 :     159231 : }
     331                 :            : 
     332                 :            : /* Get a debug string for C_OP.  */
     333                 :            : 
     334                 :            : const char *
     335                 :         30 : constraint_op_code (enum constraint_op c_op)
     336                 :            : {
     337                 :         30 :   switch (c_op)
     338                 :            :     {
     339                 :          0 :     default:
     340                 :          0 :       gcc_unreachable ();
     341                 :            :     case CONSTRAINT_NE: return "!=";
     342                 :         10 :     case CONSTRAINT_LT: return "<";
     343                 :         15 :     case CONSTRAINT_LE: return "<=";
     344                 :            :     }
     345                 :            : }
     346                 :            : 
     347                 :            : /* Convert C_OP to an enum tree_code.  */
     348                 :            : 
     349                 :            : enum tree_code
     350                 :     670734 : constraint_tree_code (enum constraint_op c_op)
     351                 :            : {
     352                 :     670734 :   switch (c_op)
     353                 :            :     {
     354                 :          0 :     default:
     355                 :          0 :       gcc_unreachable ();
     356                 :            :     case CONSTRAINT_NE: return NE_EXPR;
     357                 :            :     case CONSTRAINT_LT: return LT_EXPR;
     358                 :            :     case CONSTRAINT_LE: return LE_EXPR;
     359                 :            :     }
     360                 :            : }
     361                 :            : 
     362                 :            : /* Given "lhs C_OP rhs", determine "lhs T_OP rhs".
     363                 :            : 
     364                 :            :    For example, given "x < y", then "x > y" is false.  */
     365                 :            : 
     366                 :            : static tristate
     367                 :      32619 : eval_constraint_op_for_op (enum constraint_op c_op, enum tree_code t_op)
     368                 :            : {
     369                 :      32619 :   switch (c_op)
     370                 :            :     {
     371                 :          0 :     default:
     372                 :          0 :       gcc_unreachable ();
     373                 :      12852 :     case CONSTRAINT_NE:
     374                 :      12852 :       if (t_op == EQ_EXPR)
     375                 :       1181 :         return tristate (tristate::TS_FALSE);
     376                 :      11671 :       if (t_op == NE_EXPR)
     377                 :      11638 :         return tristate (tristate::TS_TRUE);
     378                 :            :       break;
     379                 :       8238 :     case CONSTRAINT_LT:
     380                 :       8238 :       if (t_op == LT_EXPR || t_op == LE_EXPR || t_op == NE_EXPR)
     381                 :       7043 :         return tristate (tristate::TS_TRUE);
     382                 :       1195 :       if (t_op == EQ_EXPR || t_op == GT_EXPR || t_op == GE_EXPR)
     383                 :       1195 :         return tristate (tristate::TS_FALSE);
     384                 :            :       break;
     385                 :      11529 :     case CONSTRAINT_LE:
     386                 :      11529 :       if (t_op == LE_EXPR)
     387                 :       9242 :         return tristate (tristate::TS_TRUE);
     388                 :       2287 :       if (t_op == GT_EXPR)
     389                 :       1956 :         return tristate (tristate::TS_FALSE);
     390                 :            :       break;
     391                 :            :     }
     392                 :        364 :   return tristate (tristate::TS_UNKNOWN);
     393                 :            : }
     394                 :            : 
     395                 :            : /* class constraint.  */
     396                 :            : 
     397                 :            : /* Print this constraint to PP (which must support %E for trees),
     398                 :            :    using CM to look up equiv_class instances from ids.  */
     399                 :            : 
     400                 :            : void
     401                 :          0 : constraint::print (pretty_printer *pp, const constraint_manager &cm) const
     402                 :            : {
     403                 :          0 :   m_lhs.print (pp);
     404                 :          0 :   pp_string (pp, ": ");
     405                 :          0 :   m_lhs.get_obj (cm).print (pp);
     406                 :          0 :   pp_string (pp, " ");
     407                 :          0 :   pp_string (pp, constraint_op_code (m_op));
     408                 :          0 :   pp_string (pp, " ");
     409                 :          0 :   m_rhs.print (pp);
     410                 :          0 :   pp_string (pp, ": ");
     411                 :          0 :   m_rhs.get_obj (cm).print (pp);
     412                 :          0 : }
     413                 :            : 
     414                 :            : /* Generate a hash value for this constraint.  */
     415                 :            : 
     416                 :            : hashval_t
     417                 :     169238 : constraint::hash () const
     418                 :            : {
     419                 :     169238 :   inchash::hash hstate;
     420                 :     169238 :   hstate.add_int (m_lhs.m_idx);
     421                 :     169238 :   hstate.add_int (m_op);
     422                 :     169238 :   hstate.add_int (m_rhs.m_idx);
     423                 :     169238 :   return hstate.end ();
     424                 :            : }
     425                 :            : 
     426                 :            : /* Equality operator for constraints.  */
     427                 :            : 
     428                 :            : bool
     429                 :      58102 : constraint::operator== (const constraint &other) const
     430                 :            : {
     431                 :      58102 :   if (m_lhs != other.m_lhs)
     432                 :            :     return false;
     433                 :      58102 :   if (m_op != other.m_op)
     434                 :            :     return false;
     435                 :      58102 :   if (m_rhs != other.m_rhs)
     436                 :          0 :     return false;
     437                 :            :   return true;
     438                 :            : }
     439                 :            : 
     440                 :            : /* class equiv_class_id.  */
     441                 :            : 
     442                 :            : /* Get the underlying equiv_class for this ID from CM.  */
     443                 :            : 
     444                 :            : const equiv_class &
     445                 :    1341470 : equiv_class_id::get_obj (const constraint_manager &cm) const
     446                 :            : {
     447                 :    1341470 :   return cm.get_equiv_class_by_index (m_idx);
     448                 :            : }
     449                 :            : 
     450                 :            : /* Access the underlying equiv_class for this ID from CM.  */
     451                 :            : 
     452                 :            : equiv_class &
     453                 :    1321580 : equiv_class_id::get_obj (constraint_manager &cm) const
     454                 :            : {
     455                 :    1321580 :   return cm.get_equiv_class_by_index (m_idx);
     456                 :            : }
     457                 :            : 
     458                 :            : /* Print this equiv_class_id to PP.  */
     459                 :            : 
     460                 :            : void
     461                 :          0 : equiv_class_id::print (pretty_printer *pp) const
     462                 :            : {
     463                 :          0 :   if (null_p ())
     464                 :          0 :     pp_printf (pp, "null");
     465                 :            :   else
     466                 :          0 :     pp_printf (pp, "ec%i", m_idx);
     467                 :          0 : }
     468                 :            : 
     469                 :            : /* class constraint_manager.  */
     470                 :            : 
     471                 :            : /* constraint_manager's copy ctor.  */
     472                 :            : 
     473                 :     162761 : constraint_manager::constraint_manager (const constraint_manager &other)
     474                 :     162761 : : m_equiv_classes (other.m_equiv_classes.length ()),
     475                 :     276379 :   m_constraints (other.m_constraints.length ())
     476                 :            : {
     477                 :            :   int i;
     478                 :            :   equiv_class *ec;
     479                 :     621856 :   FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
     480                 :     459095 :     m_equiv_classes.quick_push (new equiv_class (*ec));
     481                 :            :   constraint *c;
     482                 :     473788 :   FOR_EACH_VEC_ELT (other.m_constraints, i, c)
     483                 :     311027 :     m_constraints.quick_push (*c);
     484                 :     162761 : }
     485                 :            : 
     486                 :            : /* constraint_manager's assignment operator.  */
     487                 :            : 
     488                 :            : constraint_manager&
     489                 :          0 : constraint_manager::operator= (const constraint_manager &other)
     490                 :            : {
     491                 :          0 :   gcc_assert (m_equiv_classes.length () == 0);
     492                 :          0 :   gcc_assert (m_constraints.length () == 0);
     493                 :            : 
     494                 :          0 :   int i;
     495                 :          0 :   equiv_class *ec;
     496                 :          0 :   m_equiv_classes.reserve (other.m_equiv_classes.length ());
     497                 :          0 :   FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
     498                 :          0 :     m_equiv_classes.quick_push (new equiv_class (*ec));
     499                 :          0 :   constraint *c;
     500                 :          0 :   m_constraints.reserve (other.m_constraints.length ());
     501                 :          0 :   FOR_EACH_VEC_ELT (other.m_constraints, i, c)
     502                 :          0 :     m_constraints.quick_push (*c);
     503                 :            : 
     504                 :          0 :   return *this;
     505                 :            : }
     506                 :            : 
     507                 :            : /* Generate a hash value for this constraint_manager.  */
     508                 :            : 
     509                 :            : hashval_t
     510                 :      94224 : constraint_manager::hash () const
     511                 :            : {
     512                 :      94224 :   inchash::hash hstate;
     513                 :      94224 :   int i;
     514                 :      94224 :   equiv_class *ec;
     515                 :      94224 :   constraint *c;
     516                 :            : 
     517                 :     329649 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
     518                 :     235425 :     hstate.merge_hash (ec->hash ());
     519                 :     263462 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
     520                 :     169238 :     hstate.merge_hash (c->hash ());
     521                 :      94224 :   return hstate.end ();
     522                 :            : }
     523                 :            : 
     524                 :            : /* Equality operator for constraint_manager.  */
     525                 :            : 
     526                 :            : bool
     527                 :      32939 : constraint_manager::operator== (const constraint_manager &other) const
     528                 :            : {
     529                 :      73937 :   if (m_equiv_classes.length () != other.m_equiv_classes.length ())
     530                 :            :     return false;
     531                 :      57014 :   if (m_constraints.length () != other.m_constraints.length ())
     532                 :            :     return false;
     533                 :            : 
     534                 :            :   int i;
     535                 :            :   equiv_class *ec;
     536                 :            : 
     537                 :     110985 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
     538                 :      78920 :     if (!(*ec == *other.m_equiv_classes[i]))
     539                 :            :       return false;
     540                 :            : 
     541                 :            :   constraint *c;
     542                 :            : 
     543                 :      90167 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
     544                 :      58102 :     if (!(*c == other.m_constraints[i]))
     545                 :            :       return false;
     546                 :            : 
     547                 :            :   return true;
     548                 :            : }
     549                 :            : 
     550                 :            : /* Print this constraint_manager to PP (which must support %E for trees).  */
     551                 :            : 
     552                 :            : void
     553                 :          0 : constraint_manager::print (pretty_printer *pp) const
     554                 :            : {
     555                 :          0 :   pp_string (pp, "{");
     556                 :          0 :   int i;
     557                 :          0 :   equiv_class *ec;
     558                 :          0 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
     559                 :            :     {
     560                 :          0 :       if (i > 0)
     561                 :          0 :         pp_string (pp, ", ");
     562                 :          0 :       equiv_class_id (i).print (pp);
     563                 :          0 :       pp_string (pp, ": ");
     564                 :          0 :       ec->print (pp);
     565                 :            :     }
     566                 :          0 :   pp_string (pp, "  |  ");
     567                 :          0 :   constraint *c;
     568                 :          0 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
     569                 :            :     {
     570                 :          0 :       if (i > 0)
     571                 :          0 :         pp_string (pp, " && ");
     572                 :          0 :       c->print (pp, *this);
     573                 :            :     }
     574                 :          0 :   pp_printf (pp, "}");
     575                 :          0 : }
     576                 :            : 
     577                 :            : /* Dump a multiline representation of this constraint_manager to PP
     578                 :            :    (which must support %E for trees).  */
     579                 :            : 
     580                 :            : void
     581                 :         10 : constraint_manager::dump_to_pp (pretty_printer *pp) const
     582                 :            : {
     583                 :            :   // TODO
     584                 :         10 :   pp_string (pp, "  equiv classes:");
     585                 :         10 :   pp_newline (pp);
     586                 :         10 :   int i;
     587                 :         10 :   equiv_class *ec;
     588                 :         10 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
     589                 :            :     {
     590                 :          0 :       pp_string (pp, "    ");
     591                 :          0 :       equiv_class_id (i).print (pp);
     592                 :          0 :       pp_string (pp, ": ");
     593                 :          0 :       ec->print (pp);
     594                 :          0 :       pp_newline (pp);
     595                 :            :     }
     596                 :         10 :   pp_string (pp, "  constraints:");
     597                 :         10 :   pp_newline (pp);
     598                 :         10 :   constraint *c;
     599                 :         10 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
     600                 :            :     {
     601                 :          0 :       pp_printf (pp, "    %i: ", i);
     602                 :          0 :       c->print (pp, *this);
     603                 :          0 :       pp_newline (pp);
     604                 :            :     }
     605                 :         10 : }
     606                 :            : 
     607                 :            : /* Dump a multiline representation of this constraint_manager to FP.  */
     608                 :            : 
     609                 :            : void
     610                 :          0 : constraint_manager::dump (FILE *fp) const
     611                 :            : {
     612                 :          0 :   pretty_printer pp;
     613                 :          0 :   pp_format_decoder (&pp) = default_tree_printer;
     614                 :          0 :   pp_show_color (&pp) = pp_show_color (global_dc->printer);
     615                 :          0 :   pp.buffer->stream = fp;
     616                 :          0 :   dump_to_pp (&pp);
     617                 :          0 :   pp_flush (&pp);
     618                 :          0 : }
     619                 :            : 
     620                 :            : /* Dump a multiline representation of this constraint_manager to stderr.  */
     621                 :            : 
     622                 :            : DEBUG_FUNCTION void
     623                 :          0 : constraint_manager::dump () const
     624                 :            : {
     625                 :          0 :   dump (stderr);
     626                 :          0 : }
     627                 :            : 
     628                 :            : /* Dump a multiline representation of CM to stderr.  */
     629                 :            : 
     630                 :            : DEBUG_FUNCTION void
     631                 :          0 : debug (const constraint_manager &cm)
     632                 :            : {
     633                 :          0 :   cm.dump ();
     634                 :          0 : }
     635                 :            : 
     636                 :            : /* Attempt to add the constraint LHS OP RHS to this constraint_manager.
     637                 :            :    Return true if the constraint could be added (or is already true).
     638                 :            :    Return false if the constraint contradicts existing knowledge.  */
     639                 :            : 
     640                 :            : bool
     641                 :      69204 : constraint_manager::add_constraint (svalue_id lhs,
     642                 :            :                                     enum tree_code op,
     643                 :            :                                     svalue_id rhs)
     644                 :            : {
     645                 :      69204 :   equiv_class_id lhs_ec_id = get_or_add_equiv_class (lhs);
     646                 :      69204 :   equiv_class_id rhs_ec_id = get_or_add_equiv_class (rhs);
     647                 :      69204 :   return add_constraint (lhs_ec_id, op,rhs_ec_id);
     648                 :            : }
     649                 :            : 
     650                 :            : /* Attempt to add the constraint LHS_EC_ID OP RHS_EC_ID to this
     651                 :            :    constraint_manager.
     652                 :            :    Return true if the constraint could be added (or is already true).
     653                 :            :    Return false if the constraint contradicts existing knowledge.  */
     654                 :            : 
     655                 :            : bool
     656                 :      83962 : constraint_manager::add_constraint (equiv_class_id lhs_ec_id,
     657                 :            :                                     enum tree_code op,
     658                 :            :                                     equiv_class_id rhs_ec_id)
     659                 :            : {
     660                 :      83962 :   tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
     661                 :            : 
     662                 :            :   /* Discard constraints that are already known.  */
     663                 :      83962 :   if (t.is_true ())
     664                 :            :     return true;
     665                 :            : 
     666                 :            :   /* Reject unsatisfiable constraints.  */
     667                 :      36370 :   if (t.is_false ())
     668                 :            :     return false;
     669                 :            : 
     670                 :      36370 :   gcc_assert (lhs_ec_id != rhs_ec_id);
     671                 :            : 
     672                 :            :   /* For now, simply accumulate constraints, without attempting any further
     673                 :            :      optimization.  */
     674                 :      36370 :   switch (op)
     675                 :            :     {
     676                 :       8698 :     case EQ_EXPR:
     677                 :       8698 :       {
     678                 :            :         /* Merge rhs_ec into lhs_ec.  */
     679                 :       8698 :         equiv_class &lhs_ec_obj = lhs_ec_id.get_obj (*this);
     680                 :       8698 :         const equiv_class &rhs_ec_obj = rhs_ec_id.get_obj (*this);
     681                 :            : 
     682                 :       8698 :         int i;
     683                 :       8698 :         svalue_id *sid;
     684                 :      17686 :         FOR_EACH_VEC_ELT (rhs_ec_obj.m_vars, i, sid)
     685                 :       8988 :           lhs_ec_obj.add (*sid, *this);
     686                 :            : 
     687                 :       8698 :         if (rhs_ec_obj.m_constant)
     688                 :            :           {
     689                 :       2346 :             lhs_ec_obj.m_constant = rhs_ec_obj.m_constant;
     690                 :       2346 :             lhs_ec_obj.m_cst_sid = rhs_ec_obj.m_cst_sid;
     691                 :            :           }
     692                 :            : 
     693                 :            :         /* Drop rhs equivalence class, overwriting it with the
     694                 :            :            final ec (which might be the same one).  */
     695                 :      17396 :         equiv_class_id final_ec_id = m_equiv_classes.length () - 1;
     696                 :       8698 :         equiv_class *old_ec = m_equiv_classes[rhs_ec_id.m_idx];
     697                 :       8698 :         equiv_class *final_ec = m_equiv_classes.pop ();
     698                 :       8698 :         if (final_ec != old_ec)
     699                 :       1365 :           m_equiv_classes[rhs_ec_id.m_idx] = final_ec;
     700                 :      17396 :         delete old_ec;
     701                 :            : 
     702                 :            :         /* Update the constraints.  */
     703                 :            :         constraint *c;
     704                 :      18441 :         FOR_EACH_VEC_ELT (m_constraints, i, c)
     705                 :            :           {
     706                 :            :             /* Update references to the rhs_ec so that
     707                 :            :                they refer to the lhs_ec.  */
     708                 :       9743 :             if (c->m_lhs == rhs_ec_id)
     709                 :        889 :               c->m_lhs = lhs_ec_id;
     710                 :       9743 :             if (c->m_rhs == rhs_ec_id)
     711                 :       2056 :               c->m_rhs = lhs_ec_id;
     712                 :            : 
     713                 :            :             /* Renumber all constraints that refer to the final rhs_ec
     714                 :            :                to the old rhs_ec, where the old final_ec now lives.  */
     715                 :       9743 :             if (c->m_lhs == final_ec_id)
     716                 :        665 :               c->m_lhs = rhs_ec_id;
     717                 :       9743 :             if (c->m_rhs == final_ec_id)
     718                 :        820 :               c->m_rhs = rhs_ec_id;
     719                 :            :           }
     720                 :            :       }
     721                 :            :       break;
     722                 :        232 :     case GE_EXPR:
     723                 :        232 :       add_constraint_internal (rhs_ec_id, CONSTRAINT_LE, lhs_ec_id);
     724                 :        232 :       break;
     725                 :       9259 :     case LE_EXPR:
     726                 :       9259 :       add_constraint_internal (lhs_ec_id, CONSTRAINT_LE, rhs_ec_id);
     727                 :       9259 :       break;
     728                 :      11825 :     case NE_EXPR:
     729                 :      11825 :       add_constraint_internal (lhs_ec_id, CONSTRAINT_NE, rhs_ec_id);
     730                 :      11825 :       break;
     731                 :        292 :     case GT_EXPR:
     732                 :        292 :       add_constraint_internal (rhs_ec_id, CONSTRAINT_LT, lhs_ec_id);
     733                 :        292 :       break;
     734                 :       6064 :     case LT_EXPR:
     735                 :       6064 :       add_constraint_internal (lhs_ec_id, CONSTRAINT_LT, rhs_ec_id);
     736                 :       6064 :       break;
     737                 :            :     default:
     738                 :            :       /* do nothing.  */
     739                 :            :       break;
     740                 :            :     }
     741                 :      36370 :   validate ();
     742                 :      36370 :   return true;
     743                 :            : }
     744                 :            : 
     745                 :            : /* Subroutine of constraint_manager::add_constraint, for handling all
     746                 :            :    operations other than equality (for which equiv classes are merged).  */
     747                 :            : 
     748                 :            : void
     749                 :      97720 : constraint_manager::add_constraint_internal (equiv_class_id lhs_id,
     750                 :            :                                              enum constraint_op c_op,
     751                 :            :                                              equiv_class_id rhs_id)
     752                 :            : {
     753                 :            :   /* Add the constraint.  */
     754                 :      97720 :   m_constraints.safe_push (constraint (lhs_id, c_op, rhs_id));
     755                 :            : 
     756                 :      97720 :   if (!flag_analyzer_transitivity)
     757                 :            :     return;
     758                 :            : 
     759                 :       5505 :   if (c_op != CONSTRAINT_NE)
     760                 :            :     {
     761                 :            :       /* The following can potentially add EQ_EXPR facts, which could lead
     762                 :            :          to ECs being merged, which would change the meaning of the EC IDs.
     763                 :            :          Hence we need to do this via representatives.  */
     764                 :       5028 :       svalue_id lhs = lhs_id.get_obj (*this).get_representative ();
     765                 :       5028 :       svalue_id rhs = rhs_id.get_obj (*this).get_representative ();
     766                 :            : 
     767                 :            :       /* We have LHS </<= RHS */
     768                 :            : 
     769                 :            :       /* Handle transitivity of ordering by adding additional constraints
     770                 :            :          based on what we already knew.
     771                 :            : 
     772                 :            :          So if we have already have:
     773                 :            :            (a < b)
     774                 :            :            (c < d)
     775                 :            :          Then adding:
     776                 :            :            (b < c)
     777                 :            :          will also add:
     778                 :            :            (a < c)
     779                 :            :            (b < d)
     780                 :            :          We need to recurse to ensure we also add:
     781                 :            :            (a < d).
     782                 :            :          We call the checked add_constraint to avoid adding constraints
     783                 :            :          that are already present.  Doing so also ensures termination
     784                 :            :          in the case of cycles.
     785                 :            : 
     786                 :            :          We also check for single-element ranges, adding EQ_EXPR facts
     787                 :            :          where we discover them.  For example 3 < x < 5 implies
     788                 :            :          that x == 4 (if x is an integer).  */
     789                 :     476486 :       for (unsigned i = 0; i < m_constraints.length (); i++)
     790                 :            :         {
     791                 :     233241 :           const constraint *other = &m_constraints[i];
     792                 :     233241 :           if (other->is_ordering_p ())
     793                 :            :             {
     794                 :            :               /* Refresh the EC IDs, in case any mergers have happened.  */
     795                 :     201654 :               lhs_id = get_or_add_equiv_class (lhs);
     796                 :     201654 :               rhs_id = get_or_add_equiv_class (rhs);
     797                 :            : 
     798                 :     201654 :               tree lhs_const = lhs_id.get_obj (*this).m_constant;
     799                 :     201654 :               tree rhs_const = rhs_id.get_obj (*this).m_constant;
     800                 :     201654 :               tree other_lhs_const
     801                 :     201654 :                 = other->m_lhs.get_obj (*this).m_constant;
     802                 :     201654 :               tree other_rhs_const
     803                 :     201654 :                 = other->m_rhs.get_obj (*this).m_constant;
     804                 :            : 
     805                 :            :               /* We have "LHS </<= RHS" and "other.lhs </<= other.rhs".  */
     806                 :            : 
     807                 :            :               /* If we have LHS </<= RHS and RHS </<= LHS, then we have a
     808                 :            :                  cycle.  */
     809                 :     201654 :               if (rhs_id == other->m_lhs
     810                 :     201654 :                   && other->m_rhs == lhs_id)
     811                 :            :                 {
     812                 :            :                   /* We must have equality for this to be possible.  */
     813                 :         10 :                   gcc_assert (c_op == CONSTRAINT_LE
     814                 :            :                               && other->m_op == CONSTRAINT_LE);
     815                 :         10 :                   add_constraint (lhs_id, EQ_EXPR, rhs_id);
     816                 :            :                   /* Adding an equality will merge the two ECs and potentially
     817                 :            :                      reorganize the constraints.  Stop iterating.  */
     818                 :         36 :                   return;
     819                 :            :                 }
     820                 :            :               /* Otherwise, check for transitivity.  */
     821                 :     201644 :               if (rhs_id == other->m_lhs)
     822                 :            :                 {
     823                 :            :                   /* With RHS == other.lhs, we have:
     824                 :            :                      "LHS </<= (RHS, other.lhs) </<= other.rhs"
     825                 :            :                      and thus this implies "LHS </<= other.rhs".  */
     826                 :            : 
     827                 :            :                   /* Do we have a tightly-constrained range?  */
     828                 :        171 :                   if (lhs_const
     829                 :        171 :                       && !rhs_const
     830                 :         10 :                       && other_rhs_const)
     831                 :            :                     {
     832                 :         10 :                       range r (bound (lhs_const, c_op == CONSTRAINT_LE),
     833                 :         10 :                                bound (other_rhs_const,
     834                 :         10 :                                       other->m_op == CONSTRAINT_LE));
     835                 :         10 :                       tree constant;
     836                 :         10 :                       if (r.constrained_to_single_element (&constant))
     837                 :            :                         {
     838                 :          4 :                           svalue_id cst_sid = get_sid_for_constant (constant);
     839                 :          4 :                           add_constraint
     840                 :          4 :                             (rhs_id, EQ_EXPR,
     841                 :            :                              get_or_add_equiv_class (cst_sid));
     842                 :          4 :                           return;
     843                 :            :                         }
     844                 :            :                     }
     845                 :            : 
     846                 :            :                   /* Otherwise, add the constraint implied by transitivity.  */
     847                 :        334 :                   enum tree_code new_op
     848                 :         48 :                     = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
     849                 :        167 :                        ? LE_EXPR : LT_EXPR);
     850                 :        167 :                   add_constraint (lhs_id, new_op, other->m_rhs);
     851                 :            :                 }
     852                 :     201473 :               else if (other->m_rhs == lhs_id)
     853                 :            :                 {
     854                 :            :                   /* With other.rhs == LHS, we have:
     855                 :            :                      "other.lhs </<= (other.rhs, LHS) </<= RHS"
     856                 :            :                      and thus this implies "other.lhs </<= RHS".  */
     857                 :            : 
     858                 :            :                   /* Do we have a tightly-constrained range?  */
     859                 :      14577 :                   if (other_lhs_const
     860                 :      14577 :                       && !lhs_const
     861                 :        120 :                       && rhs_const)
     862                 :            :                     {
     863                 :         90 :                       range r (bound (other_lhs_const,
     864                 :         90 :                                       other->m_op == CONSTRAINT_LE),
     865                 :         90 :                                bound (rhs_const,
     866                 :         90 :                                       c_op == CONSTRAINT_LE));
     867                 :         90 :                       tree constant;
     868                 :         90 :                       if (r.constrained_to_single_element (&constant))
     869                 :            :                         {
     870                 :         12 :                           svalue_id cst_sid = get_sid_for_constant (constant);
     871                 :         12 :                           add_constraint
     872                 :         12 :                             (lhs_id, EQ_EXPR,
     873                 :            :                              get_or_add_equiv_class (cst_sid));
     874                 :         12 :                           return;
     875                 :            :                         }
     876                 :            :                     }
     877                 :            : 
     878                 :            :                   /* Otherwise, add the constraint implied by transitivity.  */
     879                 :      29130 :                   enum tree_code new_op
     880                 :        116 :                     = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
     881                 :      14565 :                        ? LE_EXPR : LT_EXPR);
     882                 :      14565 :                   add_constraint (other->m_lhs, new_op, rhs_id);
     883                 :            :                 }
     884                 :            :             }
     885                 :            :         }
     886                 :            :     }
     887                 :            : }
     888                 :            : 
     889                 :            : /* Look for SID within the equivalence classes of this constraint_manager;
     890                 :            :    if found, write the id to *OUT and return true, otherwise return false.  */
     891                 :            : 
     892                 :            : bool
     893                 :     816049 : constraint_manager::get_equiv_class_by_sid (svalue_id sid, equiv_class_id *out) const
     894                 :            : {
     895                 :            :   /* TODO: should we have a map, rather than these searches?  */
     896                 :     816049 :   int i;
     897                 :     816049 :   equiv_class *ec;
     898                 :   14370800 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
     899                 :            :     {
     900                 :            :       int j;
     901                 :            :       svalue_id *iv;
     902                 :   19591100 :       FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
     903                 :    7129220 :         if (*iv == sid)
     904                 :            :           {
     905                 :     713856 :             *out = equiv_class_id (i);
     906                 :     713856 :             return true;
     907                 :            :           }
     908                 :            :     }
     909                 :            :   return false;
     910                 :            : }
     911                 :            : 
     912                 :            : /* Ensure that SID has an equivalence class within this constraint_manager;
     913                 :            :    return the ID of the class.  */
     914                 :            : 
     915                 :            : equiv_class_id
     916                 :     816049 : constraint_manager::get_or_add_equiv_class (svalue_id sid)
     917                 :            : {
     918                 :     816049 :   equiv_class_id result (-1);
     919                 :            : 
     920                 :            :   /* Try svalue_id match.  */
     921                 :     816049 :   if (get_equiv_class_by_sid (sid, &result))
     922                 :     713856 :     return result;
     923                 :            : 
     924                 :            :   /* Try equality of constants.  */
     925                 :     102193 :   if (tree cst = maybe_get_constant (sid))
     926                 :            :     {
     927                 :            :       int i;
     928                 :            :       equiv_class *ec;
     929                 :     283868 :       FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
     930                 :     244562 :         if (ec->m_constant
     931                 :     443285 :             && types_compatible_p (TREE_TYPE (cst),
     932                 :     198723 :                                    TREE_TYPE (ec->m_constant)))
     933                 :            :           {
     934                 :     136233 :             tree eq = fold_binary (EQ_EXPR, boolean_type_node,
     935                 :            :                                    cst, ec->m_constant);
     936                 :     136233 :             if (eq == boolean_true_node)
     937                 :            :               {
     938                 :      26410 :                 ec->add (sid, *this);
     939                 :      26410 :                 return equiv_class_id (i);
     940                 :            :               }
     941                 :            :           }
     942                 :            :     }
     943                 :            : 
     944                 :            : 
     945                 :            :   /* Not found.  */
     946                 :      75783 :   equiv_class *new_ec = new equiv_class ();
     947                 :      75783 :   new_ec->add (sid, *this);
     948                 :      75783 :   m_equiv_classes.safe_push (new_ec);
     949                 :            : 
     950                 :     151566 :   equiv_class_id new_id (m_equiv_classes.length () - 1);
     951                 :            : 
     952                 :      75783 :   if (maybe_get_constant (sid))
     953                 :            :     {
     954                 :            :       /* If we have a new EC for a constant, add constraints comparing this
     955                 :            :          to other constants we may have (so that we accumulate the transitive
     956                 :            :          closure of all constraints on constants as the constants are
     957                 :            :          added).  */
     958                 :     184754 :       for (equiv_class_id other_id (0); other_id.m_idx < new_id.m_idx;
     959                 :     145448 :            other_id.m_idx++)
     960                 :            :         {
     961                 :     145448 :           const equiv_class &other_ec = other_id.get_obj (*this);
     962                 :     145448 :           if (other_ec.m_constant
     963                 :     245265 :               && types_compatible_p (TREE_TYPE (new_ec->m_constant),
     964                 :      99817 :                                      TREE_TYPE (other_ec.m_constant)))
     965                 :            :             {
     966                 :            :               /* If we have two ECs, both with constants, the constants must be
     967                 :            :                  non-equal (or they would be in the same EC).
     968                 :            :                  Determine the direction of the inequality, and record that
     969                 :            :                  fact.  */
     970                 :      70058 :               tree lt
     971                 :      70058 :                 = fold_binary (LT_EXPR, boolean_type_node,
     972                 :            :                                new_ec->m_constant, other_ec.m_constant);
     973                 :      70058 :               if (lt == boolean_true_node)
     974                 :      19004 :                 add_constraint_internal (new_id, CONSTRAINT_LT, other_id);
     975                 :      51054 :               else if (lt == boolean_false_node)
     976                 :      51044 :                 add_constraint_internal (other_id, CONSTRAINT_LT, new_id);
     977                 :            :               /* Refresh new_id, in case ECs were merged.  SID should always
     978                 :            :                  be present by now, so this should never lead to a
     979                 :            :                  recursion.  */
     980                 :      70058 :               new_id = get_or_add_equiv_class (sid);
     981                 :            :             }
     982                 :            :         }
     983                 :            :     }
     984                 :            : 
     985                 :      75783 :   return new_id;
     986                 :            : }
     987                 :            : 
     988                 :            : /* Evaluate the condition LHS_EC OP RHS_EC.  */
     989                 :            : 
     990                 :            : tristate
     991                 :     178556 : constraint_manager::eval_condition (equiv_class_id lhs_ec,
     992                 :            :                                     enum tree_code op,
     993                 :            :                                     equiv_class_id rhs_ec)
     994                 :            : {
     995                 :     178556 :   if (lhs_ec == rhs_ec)
     996                 :            :     {
     997                 :      15090 :       switch (op)
     998                 :            :         {
     999                 :      13887 :         case EQ_EXPR:
    1000                 :      13887 :         case GE_EXPR:
    1001                 :      13887 :         case LE_EXPR:
    1002                 :      13887 :           return tristate (tristate::TS_TRUE);
    1003                 :            : 
    1004                 :       1203 :         case NE_EXPR:
    1005                 :       1203 :         case GT_EXPR:
    1006                 :       1203 :         case LT_EXPR:
    1007                 :       1203 :           return tristate (tristate::TS_FALSE);
    1008                 :            :         default:
    1009                 :            :           break;
    1010                 :            :         }
    1011                 :            :     }
    1012                 :            : 
    1013                 :     163466 :   tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ();
    1014                 :     163466 :   tree rhs_const = rhs_ec.get_obj (*this).get_any_constant ();
    1015                 :     163466 :   if (lhs_const && rhs_const)
    1016                 :            :     {
    1017                 :      70400 :       tree comparison
    1018                 :      70400 :         = fold_binary (op, boolean_type_node, lhs_const, rhs_const);
    1019                 :      70400 :       if (comparison == boolean_true_node)
    1020                 :      70039 :         return tristate (tristate::TS_TRUE);
    1021                 :        361 :       if (comparison == boolean_false_node)
    1022                 :        361 :         return tristate (tristate::TS_FALSE);
    1023                 :            :     }
    1024                 :            : 
    1025                 :      93066 :   enum tree_code swapped_op = swap_tree_comparison (op);
    1026                 :            : 
    1027                 :      93066 :   int i;
    1028                 :      93066 :   constraint *c;
    1029                 :    1226760 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    1030                 :            :     {
    1031                 :    1165950 :       if (c->m_lhs == lhs_ec
    1032                 :    1165950 :           && c->m_rhs == rhs_ec)
    1033                 :            :         {
    1034                 :      28339 :           tristate result_for_constraint
    1035                 :      28339 :             = eval_constraint_op_for_op (c->m_op, op);
    1036                 :      28339 :           if (result_for_constraint.is_known ())
    1037                 :      28056 :             return result_for_constraint;
    1038                 :            :         }
    1039                 :            :       /* Swapped operands.  */
    1040                 :    1137900 :       if (c->m_lhs == rhs_ec
    1041                 :    1137900 :           && c->m_rhs == lhs_ec)
    1042                 :            :         {
    1043                 :       4280 :           tristate result_for_constraint
    1044                 :       4280 :             = eval_constraint_op_for_op (c->m_op, swapped_op);
    1045                 :       4280 :           if (result_for_constraint.is_known ())
    1046                 :       4199 :             return result_for_constraint;
    1047                 :            :         }
    1048                 :            :     }
    1049                 :            : 
    1050                 :      60811 :   return tristate (tristate::TS_UNKNOWN);
    1051                 :            : }
    1052                 :            : 
    1053                 :            : /* Evaluate the condition LHS OP RHS, creating equiv_class instances for
    1054                 :            :    LHS and RHS if they aren't already in equiv_classes.  */
    1055                 :            : 
    1056                 :            : tristate
    1057                 :      94594 : constraint_manager::eval_condition (svalue_id lhs,
    1058                 :            :                                     enum tree_code op,
    1059                 :            :                                     svalue_id rhs)
    1060                 :            : {
    1061                 :      94594 :   return eval_condition (get_or_add_equiv_class (lhs),
    1062                 :            :                          op,
    1063                 :      94594 :                          get_or_add_equiv_class (rhs));
    1064                 :            : }
    1065                 :            : 
    1066                 :            : /* Delete any information about svalue_id instances identified by P.
    1067                 :            :    Such instances are removed from equivalence classes, and any
    1068                 :            :    redundant ECs and constraints are also removed.
    1069                 :            :    Accumulate stats into STATS.  */
    1070                 :            : 
    1071                 :            : void
    1072                 :      29980 : constraint_manager::purge (const purge_criteria &p, purge_stats *stats)
    1073                 :            : {
    1074                 :            :   /* Delete any svalue_ids identified by P within the various equivalence
    1075                 :            :      classes.  */
    1076                 :     229333 :   for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
    1077                 :            :     {
    1078                 :      88719 :       equiv_class *ec = m_equiv_classes[ec_idx];
    1079                 :            : 
    1080                 :      88719 :       int i;
    1081                 :      88719 :       svalue_id *pv;
    1082                 :      88719 :       bool delete_ec = false;
    1083                 :     186669 :       FOR_EACH_VEC_ELT (ec->m_vars, i, pv)
    1084                 :            :         {
    1085                 :      97950 :           if (*pv == ec->m_cst_sid)
    1086                 :      44067 :             continue;
    1087                 :      53883 :           if (p.should_purge_p (*pv))
    1088                 :            :             {
    1089                 :       5895 :               if (ec->del (*pv))
    1090                 :       3653 :                 if (!ec->m_constant)
    1091                 :       3653 :                   delete_ec = true;
    1092                 :            :             }
    1093                 :            :         }
    1094                 :            : 
    1095                 :      88719 :       if (delete_ec)
    1096                 :            :         {
    1097                 :       7306 :           delete ec;
    1098                 :       3653 :           m_equiv_classes.ordered_remove (ec_idx);
    1099                 :       3653 :           if (stats)
    1100                 :       3650 :             stats->m_num_equiv_classes++;
    1101                 :            : 
    1102                 :            :           /* Update the constraints, potentially removing some.  */
    1103                 :      47266 :           for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
    1104                 :            :             {
    1105                 :      20401 :               constraint *c = &m_constraints[con_idx];
    1106                 :            : 
    1107                 :            :               /* Remove constraints that refer to the deleted EC.  */
    1108                 :      20401 :               if (c->m_lhs == ec_idx
    1109                 :      20401 :                   || c->m_rhs == ec_idx)
    1110                 :            :                 {
    1111                 :       2441 :                   m_constraints.ordered_remove (con_idx);
    1112                 :       2441 :                   if (stats)
    1113                 :       2441 :                     stats->m_num_constraints++;
    1114                 :            :                 }
    1115                 :            :               else
    1116                 :            :                 {
    1117                 :            :                   /* Renumber constraints that refer to ECs that have
    1118                 :            :                      had their idx changed.  */
    1119                 :      17960 :                   c->m_lhs.update_for_removal (ec_idx);
    1120                 :      17960 :                   c->m_rhs.update_for_removal (ec_idx);
    1121                 :            : 
    1122                 :      17960 :                   con_idx++;
    1123                 :            :                 }
    1124                 :            :             }
    1125                 :            :         }
    1126                 :            :       else
    1127                 :      85066 :         ec_idx++;
    1128                 :            :     }
    1129                 :            : 
    1130                 :            :   /* Now delete any constraints that are purely between constants.  */
    1131                 :     164875 :   for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
    1132                 :            :     {
    1133                 :      60552 :       constraint *c = &m_constraints[con_idx];
    1134                 :      60552 :       if (m_equiv_classes[c->m_lhs.m_idx]->m_vars.length () == 0
    1135                 :      60552 :           && m_equiv_classes[c->m_rhs.m_idx]->m_vars.length () == 0)
    1136                 :            :         {
    1137                 :          0 :           m_constraints.ordered_remove (con_idx);
    1138                 :          0 :           if (stats)
    1139                 :          0 :             stats->m_num_constraints++;
    1140                 :            :         }
    1141                 :            :       else
    1142                 :            :         {
    1143                 :      60552 :           con_idx++;
    1144                 :            :         }
    1145                 :            :     }
    1146                 :            : 
    1147                 :            :   /* Finally, delete any ECs that purely contain constants and aren't
    1148                 :            :      referenced by any constraints.  */
    1149                 :     222027 :   for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
    1150                 :            :     {
    1151                 :      85066 :       equiv_class *ec = m_equiv_classes[ec_idx];
    1152                 :      85066 :       if (ec->m_vars.length () == 0)
    1153                 :            :         {
    1154                 :          0 :           equiv_class_id ec_id (ec_idx);
    1155                 :          0 :           bool has_constraint = false;
    1156                 :          0 :           for (unsigned con_idx = 0; con_idx < m_constraints.length ();
    1157                 :            :                con_idx++)
    1158                 :            :             {
    1159                 :          0 :               constraint *c = &m_constraints[con_idx];
    1160                 :          0 :               if (c->m_lhs == ec_id
    1161                 :          0 :                   || c->m_rhs == ec_id)
    1162                 :            :                 {
    1163                 :            :                   has_constraint = true;
    1164                 :            :                   break;
    1165                 :            :                 }
    1166                 :            :             }
    1167                 :          0 :           if (!has_constraint)
    1168                 :            :             {
    1169                 :          0 :               delete ec;
    1170                 :          0 :               m_equiv_classes.ordered_remove (ec_idx);
    1171                 :          0 :               if (stats)
    1172                 :          0 :                 stats->m_num_equiv_classes++;
    1173                 :            : 
    1174                 :            :               /* Renumber constraints that refer to ECs that have
    1175                 :            :                  had their idx changed.  */
    1176                 :          0 :               for (unsigned con_idx = 0; con_idx < m_constraints.length ();
    1177                 :            :                    con_idx++)
    1178                 :            :                 {
    1179                 :          0 :                   constraint *c = &m_constraints[con_idx];
    1180                 :          0 :                   c->m_lhs.update_for_removal (ec_idx);
    1181                 :          0 :                   c->m_rhs.update_for_removal (ec_idx);
    1182                 :            :                 }
    1183                 :          0 :               continue;
    1184                 :            :             }
    1185                 :            :         }
    1186                 :      85066 :       ec_idx++;
    1187                 :            :     }
    1188                 :            : 
    1189                 :      29980 :   validate ();
    1190                 :      29980 : }
    1191                 :            : 
    1192                 :            : /* Remap all svalue_ids within this constraint_manager using MAP.  */
    1193                 :            : 
    1194                 :            : void
    1195                 :      89913 : constraint_manager::remap_svalue_ids (const svalue_id_map &map)
    1196                 :            : {
    1197                 :      89913 :   int i;
    1198                 :      89913 :   equiv_class *ec;
    1199                 :     334192 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1200                 :     244279 :     ec->remap_svalue_ids (map);
    1201                 :      89913 : }
    1202                 :            : 
    1203                 :            : /* Comparator for use by constraint_manager::canonicalize.
    1204                 :            :    Sort a pair of equiv_class instances, using the representative
    1205                 :            :    svalue_id as a sort key.  */
    1206                 :            : 
    1207                 :            : static int
    1208                 :    1268560 : equiv_class_cmp (const void *p1, const void *p2)
    1209                 :            : {
    1210                 :    1268560 :   const equiv_class *ec1 = *(const equiv_class * const *)p1;
    1211                 :    1268560 :   const equiv_class *ec2 = *(const equiv_class * const *)p2;
    1212                 :            : 
    1213                 :    1268560 :   svalue_id rep1 = ec1->get_representative ();
    1214                 :    1268560 :   svalue_id rep2 = ec2->get_representative ();
    1215                 :            : 
    1216                 :    1268560 :   return rep1.as_int () - rep2.as_int ();
    1217                 :            : }
    1218                 :            : 
    1219                 :            : /* Comparator for use by constraint_manager::canonicalize.
    1220                 :            :    Sort a pair of constraint instances.  */
    1221                 :            : 
    1222                 :            : static int
    1223                 :    1924630 : constraint_cmp (const void *p1, const void *p2)
    1224                 :            : {
    1225                 :    1924630 :   const constraint *c1 = (const constraint *)p1;
    1226                 :    1924630 :   const constraint *c2 = (const constraint *)p2;
    1227                 :    1924630 :   int lhs_cmp = c1->m_lhs.as_int () - c2->m_lhs.as_int ();
    1228                 :    1924630 :   if (lhs_cmp)
    1229                 :            :     return lhs_cmp;
    1230                 :     452799 :   int rhs_cmp = c1->m_rhs.as_int () - c2->m_rhs.as_int ();
    1231                 :     452799 :   if (rhs_cmp)
    1232                 :            :     return rhs_cmp;
    1233                 :       1326 :   return c1->m_op - c2->m_op;
    1234                 :            : }
    1235                 :            : 
    1236                 :            : /* Reorder the equivalence classes and constraints within this
    1237                 :            :    constraint_manager into a canonical order, to increase the
    1238                 :            :    chances of finding equality with another instance.  */
    1239                 :            : 
    1240                 :            : void
    1241                 :      59945 : constraint_manager::canonicalize (unsigned num_svalue_ids)
    1242                 :            : {
    1243                 :            :   /* First, sort svalue_ids within the ECs.  */
    1244                 :      59945 :   unsigned i;
    1245                 :      59945 :   equiv_class *ec;
    1246                 :     219176 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1247                 :     159231 :     ec->canonicalize ();
    1248                 :            : 
    1249                 :            :   /* Next, sort the ECs into a canonical order.  */
    1250                 :            : 
    1251                 :            :   /* We will need to remap the equiv_class_ids in the constraints,
    1252                 :            :      so we need to store the original index of each EC.
    1253                 :            :      Build a lookup table, mapping from representative svalue_id
    1254                 :            :      to the original equiv_class_id of that svalue_id.  */
    1255                 :      59945 :   auto_vec<equiv_class_id> original_ec_id (num_svalue_ids);
    1256                 :     572527 :   for (i = 0; i < num_svalue_ids; i++)
    1257                 :     512582 :     original_ec_id.quick_push (equiv_class_id::null ());
    1258                 :     219176 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1259                 :            :     {
    1260                 :     159231 :       svalue_id rep = ec->get_representative ();
    1261                 :     159231 :       gcc_assert (!rep.null_p ());
    1262                 :     159231 :       original_ec_id[rep.as_int ()] = i;
    1263                 :            :     }
    1264                 :            : 
    1265                 :            :   /* Sort the equivalence classes.  */
    1266                 :      59945 :   m_equiv_classes.qsort (equiv_class_cmp);
    1267                 :            : 
    1268                 :            :   /* Populate ec_id_map based on the old vs new EC ids.  */
    1269                 :     119890 :   one_way_id_map<equiv_class_id> ec_id_map (m_equiv_classes.length ());
    1270                 :     219176 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1271                 :            :     {
    1272                 :     159231 :       svalue_id rep = ec->get_representative ();
    1273                 :     159231 :       ec_id_map.put (original_ec_id[rep.as_int ()], i);
    1274                 :            :     }
    1275                 :            : 
    1276                 :            :   /* Update the EC ids within the constraints.  */
    1277                 :            :   constraint *c;
    1278                 :     180566 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    1279                 :            :     {
    1280                 :     120621 :       ec_id_map.update (&c->m_lhs);
    1281                 :     120621 :       ec_id_map.update (&c->m_rhs);
    1282                 :            :     }
    1283                 :            : 
    1284                 :            :   /* Finally, sort the constraints. */
    1285                 :      85441 :   m_constraints.qsort (constraint_cmp);
    1286                 :      59945 : }
    1287                 :            : 
    1288                 :            : /* A concrete subclass of constraint_manager for use when
    1289                 :            :    merging two constraint_manager into a third constraint_manager,
    1290                 :            :    each of which has its own region_model.
    1291                 :            :    Calls are delegated to the constraint_manager for the merged model,
    1292                 :            :    and thus affect its region_model.  */
    1293                 :            : 
    1294                 :     330694 : class cleaned_constraint_manager : public constraint_manager
    1295                 :            : {
    1296                 :            : public:
    1297                 :     330694 :   cleaned_constraint_manager (constraint_manager *merged) : m_merged (merged) {}
    1298                 :            : 
    1299                 :          0 :   constraint_manager *clone (region_model *) const FINAL OVERRIDE
    1300                 :            :   {
    1301                 :          0 :     gcc_unreachable ();
    1302                 :            :   }
    1303                 :      74627 :   tree maybe_get_constant (svalue_id sid) const FINAL OVERRIDE
    1304                 :            :   {
    1305                 :      74627 :     return m_merged->maybe_get_constant (sid);
    1306                 :            :   }
    1307                 :     736308 :   svalue_id get_sid_for_constant (tree cst) const FINAL OVERRIDE
    1308                 :            :   {
    1309                 :     736308 :     return m_merged->get_sid_for_constant (cst);
    1310                 :            :   }
    1311                 :         61 :   virtual int get_num_svalues () const FINAL OVERRIDE
    1312                 :            :   {
    1313                 :         61 :     return m_merged->get_num_svalues ();
    1314                 :            :   }
    1315                 :            : private:
    1316                 :            :   constraint_manager *m_merged;
    1317                 :            : };
    1318                 :            : 
    1319                 :            : /* Concrete subclass of fact_visitor for use by constraint_manager::merge.
    1320                 :            :    For every fact in CM_A, see if it is also true in *CM_B.  Add such
    1321                 :            :    facts to *OUT.  */
    1322                 :            : 
    1323                 :     165347 : class merger_fact_visitor : public fact_visitor
    1324                 :            : {
    1325                 :            : public:
    1326                 :     165347 :   merger_fact_visitor (constraint_manager *cm_b,
    1327                 :            :                        constraint_manager *out)
    1328                 :     165347 :   : m_cm_b (cm_b), m_out (out)
    1329                 :            :   {}
    1330                 :            : 
    1331                 :      85767 :   void on_fact (svalue_id lhs, enum tree_code code, svalue_id rhs)
    1332                 :            :     FINAL OVERRIDE
    1333                 :            :   {
    1334                 :      85767 :     if (m_cm_b->eval_condition (lhs, code, rhs).is_true ())
    1335                 :            :       {
    1336                 :      62777 :         bool sat = m_out->add_constraint (lhs, code, rhs);
    1337                 :      62777 :         gcc_assert (sat);
    1338                 :            :       }
    1339                 :      85767 :   }
    1340                 :            : 
    1341                 :            : private:
    1342                 :            :   constraint_manager *m_cm_b;
    1343                 :            :   constraint_manager *m_out;
    1344                 :            : };
    1345                 :            : 
    1346                 :            : /* Use MERGER to merge CM_A and CM_B into *OUT.
    1347                 :            :    If one thinks of a constraint_manager as a subset of N-dimensional
    1348                 :            :    space, this takes the union of the points of CM_A and CM_B, and
    1349                 :            :    expresses that into *OUT.  Alternatively, it can be thought of
    1350                 :            :    as the intersection of the constraints.  */
    1351                 :            : 
    1352                 :            : void
    1353                 :     165347 : constraint_manager::merge (const constraint_manager &cm_a,
    1354                 :            :                            const constraint_manager &cm_b,
    1355                 :            :                            constraint_manager *out,
    1356                 :            :                            const model_merger &merger)
    1357                 :            : {
    1358                 :     165347 :   gcc_assert (merger.m_sid_mapping);
    1359                 :            : 
    1360                 :            :   /* Map svalue_ids in each equiv class from both sources
    1361                 :            :      to the merged region_model, dropping ids that don't survive merger,
    1362                 :            :      and potentially creating svalues in *OUT for constants.  */
    1363                 :     165347 :   cleaned_constraint_manager cleaned_cm_a (out);
    1364                 :     165347 :   const one_way_svalue_id_map &map_a_to_m
    1365                 :            :     = merger.m_sid_mapping->m_map_from_a_to_m;
    1366                 :     165347 :   clean_merger_input (cm_a, map_a_to_m, &cleaned_cm_a);
    1367                 :            : 
    1368                 :     330694 :   cleaned_constraint_manager cleaned_cm_b (out);
    1369                 :     165347 :   const one_way_svalue_id_map &map_b_to_m
    1370                 :     165347 :     = merger.m_sid_mapping->m_map_from_b_to_m;
    1371                 :     165347 :   clean_merger_input (cm_b, map_b_to_m, &cleaned_cm_b);
    1372                 :            : 
    1373                 :            :   /* At this point, the two cleaned CMs have ECs and constraints referring
    1374                 :            :      to svalues in the merged region model, but both of them have separate
    1375                 :            :      ECs.  */
    1376                 :            : 
    1377                 :            :   /* Merge the equivalence classes and constraints.
    1378                 :            :      The easiest way to do this seems to be to enumerate all of the facts
    1379                 :            :      in cleaned_cm_a, see which are also true in cleaned_cm_b,
    1380                 :            :      and add those to *OUT.  */
    1381                 :     165347 :   merger_fact_visitor v (&cleaned_cm_b, out);
    1382                 :     165347 :   cleaned_cm_a.for_each_fact (&v);
    1383                 :     165347 : }
    1384                 :            : 
    1385                 :            : /* A subroutine of constraint_manager::merge.
    1386                 :            :    Use MAP_SID_TO_M to map equivalence classes and constraints from
    1387                 :            :    SM_IN to *OUT.  Purge any non-constant svalue_id that don't appear
    1388                 :            :    in the result of MAP_SID_TO_M, purging any ECs and their constraints
    1389                 :            :    that become empty as a result.  Potentially create svalues in
    1390                 :            :    the merged region_model for constants that weren't already in use there.  */
    1391                 :            : 
    1392                 :            : void
    1393                 :     330694 : constraint_manager::
    1394                 :            : clean_merger_input (const constraint_manager &cm_in,
    1395                 :            :                     const one_way_svalue_id_map &map_sid_to_m,
    1396                 :            :                     constraint_manager *out)
    1397                 :            : {
    1398                 :     330694 :   one_way_id_map<equiv_class_id> map_ec_to_m
    1399                 :     330694 :     (cm_in.m_equiv_classes.length ());
    1400                 :     330694 :   unsigned ec_idx;
    1401                 :     330694 :   equiv_class *ec;
    1402                 :    1403630 :   FOR_EACH_VEC_ELT (cm_in.m_equiv_classes, ec_idx, ec)
    1403                 :            :     {
    1404                 :    2145870 :       equiv_class cleaned_ec;
    1405                 :    1072940 :       if (tree cst = ec->get_any_constant ())
    1406                 :            :         {
    1407                 :     736308 :           cleaned_ec.m_constant = cst;
    1408                 :            :           /* Lazily create the constant in the out region_model.  */
    1409                 :     736308 :           cleaned_ec.m_cst_sid = out->get_sid_for_constant (cst);
    1410                 :            :         }
    1411                 :            :       unsigned var_idx;
    1412                 :            :       svalue_id *var_in_sid;
    1413                 :    2168780 :       FOR_EACH_VEC_ELT (ec->m_vars, var_idx, var_in_sid)
    1414                 :            :         {
    1415                 :    1095840 :           svalue_id var_m_sid = map_sid_to_m.get_dst_for_src (*var_in_sid);
    1416                 :    1095840 :           if (!var_m_sid.null_p ())
    1417                 :     305106 :             cleaned_ec.m_vars.safe_push (var_m_sid);
    1418                 :            :         }
    1419                 :    1072940 :       if (cleaned_ec.get_any_constant () || !cleaned_ec.m_vars.is_empty ())
    1420                 :            :         {
    1421                 :    1772270 :           map_ec_to_m.put (ec_idx, out->m_equiv_classes.length ());
    1422                 :    1015880 :           out->m_equiv_classes.safe_push (new equiv_class (cleaned_ec));
    1423                 :            :         }
    1424                 :            :     }
    1425                 :            : 
    1426                 :            :   /* Write out to *OUT any constraints for which both sides survived
    1427                 :            :      cleaning, using the new EC IDs.  */
    1428                 :            :   unsigned con_idx;
    1429                 :            :   constraint *c;
    1430                 :    1847890 :   FOR_EACH_VEC_ELT (cm_in.m_constraints, con_idx, c)
    1431                 :            :     {
    1432                 :    1337860 :       equiv_class_id new_lhs = map_ec_to_m.get_dst_for_src (c->m_lhs);
    1433                 :    1337860 :       if (new_lhs.null_p ())
    1434                 :      11020 :         continue;
    1435                 :    1326860 :       equiv_class_id new_rhs = map_ec_to_m.get_dst_for_src (c->m_rhs);
    1436                 :    1326860 :       if (new_rhs.null_p ())
    1437                 :         16 :         continue;
    1438                 :    1326840 :       out->m_constraints.safe_push (constraint (new_lhs,
    1439                 :            :                                                 c->m_op,
    1440                 :            :                                                 new_rhs));
    1441                 :            :     }
    1442                 :     330694 : }
    1443                 :            : 
    1444                 :            : /* Call VISITOR's on_fact vfunc repeatedly to express the various
    1445                 :            :    equivalence classes and constraints.
    1446                 :            :    This is used by constraint_manager::merge to find the common
    1447                 :            :    facts between two input constraint_managers.  */
    1448                 :            : 
    1449                 :            : void
    1450                 :     165347 : constraint_manager::for_each_fact (fact_visitor *visitor) const
    1451                 :            : {
    1452                 :            :   /* First, call EQ_EXPR within the various equivalence classes.  */
    1453                 :     165347 :   unsigned ec_idx;
    1454                 :     165347 :   equiv_class *ec;
    1455                 :     702700 :   FOR_EACH_VEC_ELT (m_equiv_classes, ec_idx, ec)
    1456                 :            :     {
    1457                 :     537353 :       if (!ec->m_cst_sid.null_p ())
    1458                 :            :         {
    1459                 :            :           unsigned i;
    1460                 :            :           svalue_id *sid;
    1461                 :     407428 :           FOR_EACH_VEC_ELT (ec->m_vars, i, sid)
    1462                 :      11244 :             visitor->on_fact (ec->m_cst_sid, EQ_EXPR, *sid);
    1463                 :            :         }
    1464                 :     997073 :       for (unsigned i = 0; i < ec->m_vars.length (); i++)
    1465                 :     310732 :         for (unsigned j = i + 1; j < ec->m_vars.length (); j++)
    1466                 :       1598 :           visitor->on_fact (ec->m_vars[i], EQ_EXPR, ec->m_vars[j]);
    1467                 :            :     }
    1468                 :            : 
    1469                 :            :   /* Now, express the various constraints.  */
    1470                 :            :   unsigned con_idx;
    1471                 :            :   constraint *c;
    1472                 :     836081 :   FOR_EACH_VEC_ELT (m_constraints, con_idx, c)
    1473                 :            :     {
    1474                 :     670734 :       const equiv_class &ec_lhs = c->m_lhs.get_obj (*this);
    1475                 :     670734 :       const equiv_class &ec_rhs = c->m_rhs.get_obj (*this);
    1476                 :     670734 :       enum tree_code code = constraint_tree_code (c->m_op);
    1477                 :            : 
    1478                 :     670734 :       if (!ec_lhs.m_cst_sid.null_p ())
    1479                 :            :         {
    1480                 :     744847 :           for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
    1481                 :            :             {
    1482                 :      31315 :               visitor->on_fact (ec_lhs.m_cst_sid, code, ec_rhs.m_vars[j]);
    1483                 :            :             }
    1484                 :            :         }
    1485                 :     779284 :       for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
    1486                 :            :         {
    1487                 :      36507 :           if (!ec_rhs.m_cst_sid.null_p ())
    1488                 :      32880 :             visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_cst_sid);
    1489                 :      62518 :           for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
    1490                 :       8730 :             visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_vars[j]);
    1491                 :            :         }
    1492                 :            :     }
    1493                 :     165347 : }
    1494                 :            : 
    1495                 :            : /* Assert that this object is valid.  */
    1496                 :            : 
    1497                 :            : void
    1498                 :     437305 : constraint_manager::validate () const
    1499                 :            : {
    1500                 :            :   /* Skip this in a release build.  */
    1501                 :            : #if !CHECKING_P
    1502                 :            :   return;
    1503                 :            : #endif
    1504                 :            : 
    1505                 :     437305 :   int i;
    1506                 :     437305 :   equiv_class *ec;
    1507                 :    1569330 :   FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    1508                 :            :     {
    1509                 :     920987 :       gcc_assert (ec);
    1510                 :            : 
    1511                 :            :       int j;
    1512                 :            :       svalue_id *sid;
    1513                 :    1960900 :       FOR_EACH_VEC_ELT (ec->m_vars, j, sid)
    1514                 :            :         {
    1515                 :    1039910 :           gcc_assert (!sid->null_p ());
    1516                 :    1039910 :           gcc_assert (sid->as_int () < get_num_svalues ());
    1517                 :            :         }
    1518                 :     920987 :       if (ec->m_constant)
    1519                 :            :         {
    1520                 :     518809 :           gcc_assert (CONSTANT_CLASS_P (ec->m_constant));
    1521                 :     518809 :           gcc_assert (!ec->m_cst_sid.null_p ());
    1522                 :     518809 :           gcc_assert (ec->m_cst_sid.as_int () < get_num_svalues ());
    1523                 :            :         }
    1524                 :            : #if 0
    1525                 :            :       else
    1526                 :            :         gcc_assert (ec->m_vars.length () > 0);
    1527                 :            : #endif
    1528                 :            :     }
    1529                 :            : 
    1530                 :            :   constraint *c;
    1531                 :    1340400 :   FOR_EACH_VEC_ELT (m_constraints, i, c)
    1532                 :            :     {
    1533                 :     903095 :       gcc_assert (!c->m_lhs.null_p ());
    1534                 :    1806190 :       gcc_assert (c->m_lhs.as_int () <= (int)m_equiv_classes.length ());
    1535                 :     903095 :       gcc_assert (!c->m_rhs.null_p ());
    1536                 :     903095 :       gcc_assert (c->m_rhs.as_int () <= (int)m_equiv_classes.length ());
    1537                 :            :     }
    1538                 :     437305 : }
    1539                 :            : 
    1540                 :            : #if CHECKING_P
    1541                 :            : 
    1542                 :            : namespace selftest {
    1543                 :            : 
    1544                 :            : /* Various constraint_manager selftests.
    1545                 :            :    These have to be written in terms of a region_model, since
    1546                 :            :    the latter is responsible for managing svalue and svalue_id
    1547                 :            :    instances.  */
    1548                 :            : 
    1549                 :            : /* Verify that setting and getting simple conditions within a region_model
    1550                 :            :    work (thus exercising the underlying constraint_manager).  */
    1551                 :            : 
    1552                 :            : static void
    1553                 :          4 : test_constraint_conditions ()
    1554                 :            : {
    1555                 :          4 :   tree int_42 = build_int_cst (integer_type_node, 42);
    1556                 :          4 :   tree int_0 = build_int_cst (integer_type_node, 0);
    1557                 :            : 
    1558                 :          4 :   tree x = build_global_decl ("x", integer_type_node);
    1559                 :          4 :   tree y = build_global_decl ("y", integer_type_node);
    1560                 :          4 :   tree z = build_global_decl ("z", integer_type_node);
    1561                 :            : 
    1562                 :            :   /* Self-comparisons.  */
    1563                 :          4 :   {
    1564                 :          4 :     region_model model;
    1565                 :          4 :     ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, x);
    1566                 :          4 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, x);
    1567                 :          4 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, x);
    1568                 :          4 :     ASSERT_CONDITION_FALSE (model, x, NE_EXPR, x);
    1569                 :          4 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, x);
    1570                 :          4 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, x);
    1571                 :            :   }
    1572                 :            : 
    1573                 :            :   /* x == y.  */
    1574                 :          4 :   {
    1575                 :          4 :     region_model model;
    1576                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    1577                 :            : 
    1578                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    1579                 :            : 
    1580                 :          4 :     ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, y);
    1581                 :          4 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    1582                 :          4 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    1583                 :          4 :     ASSERT_CONDITION_FALSE (model, x, NE_EXPR, y);
    1584                 :          4 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    1585                 :          4 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    1586                 :            : 
    1587                 :            :     /* Swapped operands.  */
    1588                 :          4 :     ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, x);
    1589                 :          4 :     ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
    1590                 :          4 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
    1591                 :          4 :     ASSERT_CONDITION_FALSE (model, y, NE_EXPR, x);
    1592                 :          4 :     ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    1593                 :          4 :     ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
    1594                 :            : 
    1595                 :            :     /* Comparison with other var.  */
    1596                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
    1597                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
    1598                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    1599                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
    1600                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
    1601                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
    1602                 :            :   }
    1603                 :            : 
    1604                 :            :   /* x == y, then y == z  */
    1605                 :          4 :   {
    1606                 :          4 :     region_model model;
    1607                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    1608                 :            : 
    1609                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    1610                 :          4 :     ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, z);
    1611                 :            : 
    1612                 :          4 :     ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, z);
    1613                 :          4 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, z);
    1614                 :          4 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
    1615                 :          4 :     ASSERT_CONDITION_FALSE (model, x, NE_EXPR, z);
    1616                 :          4 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, z);
    1617                 :          4 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, z);
    1618                 :            :   }
    1619                 :            : 
    1620                 :            :   /* x != y.  */
    1621                 :          4 :   {
    1622                 :          4 :     region_model model;
    1623                 :            : 
    1624                 :          4 :     ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
    1625                 :            : 
    1626                 :          4 :     ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    1627                 :          4 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    1628                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
    1629                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
    1630                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
    1631                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
    1632                 :            : 
    1633                 :            :     /* Swapped operands.  */
    1634                 :          4 :     ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    1635                 :          4 :     ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    1636                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
    1637                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
    1638                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
    1639                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
    1640                 :            : 
    1641                 :            :     /* Comparison with other var.  */
    1642                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
    1643                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
    1644                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    1645                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
    1646                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
    1647                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
    1648                 :            :   }
    1649                 :            : 
    1650                 :            :   /* x < y.  */
    1651                 :          4 :   {
    1652                 :          4 :     region_model model;
    1653                 :            : 
    1654                 :          4 :     ADD_SAT_CONSTRAINT (model, x, LT_EXPR, y);
    1655                 :            : 
    1656                 :          4 :     ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
    1657                 :          4 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    1658                 :          4 :     ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    1659                 :          4 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    1660                 :          4 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    1661                 :          4 :     ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
    1662                 :            : 
    1663                 :            :     /* Swapped operands.  */
    1664                 :          4 :     ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    1665                 :          4 :     ASSERT_CONDITION_FALSE (model, y, LE_EXPR, x);
    1666                 :          4 :     ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    1667                 :          4 :     ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    1668                 :          4 :     ASSERT_CONDITION_TRUE (model, y, GT_EXPR, x);
    1669                 :          4 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
    1670                 :            :   }
    1671                 :            : 
    1672                 :            :   /* x <= y.  */
    1673                 :          4 :   {
    1674                 :          4 :     region_model model;
    1675                 :            : 
    1676                 :          4 :     ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
    1677                 :            : 
    1678                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
    1679                 :          4 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    1680                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
    1681                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    1682                 :          4 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    1683                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
    1684                 :            : 
    1685                 :            :     /* Swapped operands.  */
    1686                 :          4 :     ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    1687                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
    1688                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
    1689                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
    1690                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
    1691                 :          4 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
    1692                 :            :   }
    1693                 :            : 
    1694                 :            :   /* x > y.  */
    1695                 :          4 :   {
    1696                 :          4 :     region_model model;
    1697                 :            : 
    1698                 :          4 :     ADD_SAT_CONSTRAINT (model, x, GT_EXPR, y);
    1699                 :            : 
    1700                 :          4 :     ASSERT_CONDITION_TRUE (model, x, GT_EXPR, y);
    1701                 :          4 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    1702                 :          4 :     ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    1703                 :          4 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    1704                 :          4 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    1705                 :          4 :     ASSERT_CONDITION_FALSE (model, x, LE_EXPR, y);
    1706                 :            : 
    1707                 :            :     /* Swapped operands.  */
    1708                 :          4 :     ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
    1709                 :          4 :     ASSERT_CONDITION_FALSE (model, y, GE_EXPR, x);
    1710                 :          4 :     ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    1711                 :          4 :     ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    1712                 :          4 :     ASSERT_CONDITION_TRUE (model, y, LT_EXPR, x);
    1713                 :          4 :     ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
    1714                 :            :   }
    1715                 :            : 
    1716                 :            :   /* x >= y.  */
    1717                 :          4 :   {
    1718                 :          4 :     region_model model;
    1719                 :            : 
    1720                 :          4 :     ADD_SAT_CONSTRAINT (model, x, GE_EXPR, y);
    1721                 :            : 
    1722                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
    1723                 :          4 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    1724                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
    1725                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    1726                 :          4 :     ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    1727                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
    1728                 :            : 
    1729                 :            :     /* Swapped operands.  */
    1730                 :          4 :     ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
    1731                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
    1732                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
    1733                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
    1734                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
    1735                 :          4 :     ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
    1736                 :            :   }
    1737                 :            : 
    1738                 :            :   // TODO: implied orderings
    1739                 :            : 
    1740                 :            :   /* Constants.  */
    1741                 :          4 :   {
    1742                 :          4 :     region_model model;
    1743                 :          4 :     ASSERT_CONDITION_FALSE (model, int_0, EQ_EXPR, int_42);
    1744                 :          4 :     ASSERT_CONDITION_TRUE (model, int_0, NE_EXPR, int_42);
    1745                 :          4 :     ASSERT_CONDITION_TRUE (model, int_0, LT_EXPR, int_42);
    1746                 :          4 :     ASSERT_CONDITION_TRUE (model, int_0, LE_EXPR, int_42);
    1747                 :          4 :     ASSERT_CONDITION_FALSE (model, int_0, GT_EXPR, int_42);
    1748                 :          4 :     ASSERT_CONDITION_FALSE (model, int_0, GE_EXPR, int_42);
    1749                 :            :   }
    1750                 :            : 
    1751                 :            :   /* x == 0, y == 42.  */
    1752                 :          4 :   {
    1753                 :          4 :     region_model model;
    1754                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    1755                 :          4 :     ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, int_42);
    1756                 :            : 
    1757                 :          4 :     ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    1758                 :          4 :     ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    1759                 :          4 :     ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    1760                 :          4 :     ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
    1761                 :          4 :     ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
    1762                 :          4 :     ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    1763                 :            :   }
    1764                 :            : 
    1765                 :            :   /* Unsatisfiable combinations.  */
    1766                 :            : 
    1767                 :            :   /* x == y && x != y.  */
    1768                 :          4 :   {
    1769                 :          4 :     region_model model;
    1770                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    1771                 :          4 :     ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, y);
    1772                 :            :   }
    1773                 :            : 
    1774                 :            :   /* x == 0 then x == 42.  */
    1775                 :          4 :   {
    1776                 :          4 :     region_model model;
    1777                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    1778                 :          4 :     ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, int_42);
    1779                 :            :   }
    1780                 :            : 
    1781                 :            :   /* x == 0 then x != 0.  */
    1782                 :          4 :   {
    1783                 :          4 :     region_model model;
    1784                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    1785                 :          4 :     ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, int_0);
    1786                 :            :   }
    1787                 :            : 
    1788                 :            :   /* x == 0 then x > 0.  */
    1789                 :          4 :   {
    1790                 :          4 :     region_model model;
    1791                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    1792                 :          4 :     ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, int_0);
    1793                 :            :   }
    1794                 :            : 
    1795                 :            :   /* x != y && x == y.  */
    1796                 :          4 :   {
    1797                 :          4 :     region_model model;
    1798                 :          4 :     ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
    1799                 :          4 :     ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, y);
    1800                 :            :   }
    1801                 :            : 
    1802                 :            :   /* x <= y && x > y.  */
    1803                 :          4 :   {
    1804                 :          4 :     region_model model;
    1805                 :          4 :     ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
    1806                 :          4 :     ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, y);
    1807                 :            :   }
    1808                 :            : 
    1809                 :            :   // etc
    1810                 :          4 : }
    1811                 :            : 
    1812                 :            : /* Test transitivity of conditions.  */
    1813                 :            : 
    1814                 :            : static void
    1815                 :          2 : test_transitivity ()
    1816                 :            : {
    1817                 :          2 :   tree a = build_global_decl ("a", integer_type_node);
    1818                 :          2 :   tree b = build_global_decl ("b", integer_type_node);
    1819                 :          2 :   tree c = build_global_decl ("c", integer_type_node);
    1820                 :          2 :   tree d = build_global_decl ("d", integer_type_node);
    1821                 :            : 
    1822                 :            :   /* a == b, then c == d, then c == b.  */
    1823                 :          2 :   {
    1824                 :          2 :     region_model model;
    1825                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, b);
    1826                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, b, EQ_EXPR, c);
    1827                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, c, EQ_EXPR, d);
    1828                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);
    1829                 :            : 
    1830                 :          2 :     ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, b);
    1831                 :          2 :     ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);
    1832                 :            : 
    1833                 :          2 :     ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, d);
    1834                 :          2 :     ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, d);
    1835                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);
    1836                 :            : 
    1837                 :          2 :     ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, b);
    1838                 :          2 :     ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, b);
    1839                 :          2 :     ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, d);
    1840                 :            :   }
    1841                 :            : 
    1842                 :            :   /* Transitivity: "a < b", "b < c" should imply "a < c".  */
    1843                 :          2 :   {
    1844                 :          2 :     region_model model;
    1845                 :          2 :     ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
    1846                 :          2 :     ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
    1847                 :            : 
    1848                 :          2 :     ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    1849                 :          2 :     ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
    1850                 :            :   }
    1851                 :            : 
    1852                 :            :   /* Transitivity: "a <= b", "b < c" should imply "a < c".  */
    1853                 :          2 :   {
    1854                 :          2 :     region_model model;
    1855                 :          2 :     ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
    1856                 :          2 :     ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
    1857                 :            : 
    1858                 :          2 :     ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    1859                 :          2 :     ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
    1860                 :            :   }
    1861                 :            : 
    1862                 :            :   /* Transitivity: "a <= b", "b <= c" should imply "a <= c".  */
    1863                 :          2 :   {
    1864                 :          2 :     region_model model;
    1865                 :          2 :     ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
    1866                 :          2 :     ADD_SAT_CONSTRAINT (model, b, LE_EXPR, c);
    1867                 :            : 
    1868                 :          2 :     ASSERT_CONDITION_TRUE (model, a, LE_EXPR, c);
    1869                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
    1870                 :            :   }
    1871                 :            : 
    1872                 :            :   /* Transitivity: "a > b", "b > c" should imply "a > c".  */
    1873                 :          2 :   {
    1874                 :          2 :     region_model model;
    1875                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    1876                 :          2 :     ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
    1877                 :            : 
    1878                 :          2 :     ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
    1879                 :          2 :     ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
    1880                 :            :   }
    1881                 :            : 
    1882                 :            :   /* Transitivity: "a >= b", "b > c" should imply " a > c".  */
    1883                 :          2 :   {
    1884                 :          2 :     region_model model;
    1885                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    1886                 :          2 :     ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
    1887                 :            : 
    1888                 :          2 :     ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
    1889                 :          2 :     ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
    1890                 :            :   }
    1891                 :            : 
    1892                 :            :   /* Transitivity: "a >= b", "b >= c" should imply "a >= c".  */
    1893                 :          2 :   {
    1894                 :          2 :     region_model model;
    1895                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    1896                 :          2 :     ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
    1897                 :            : 
    1898                 :          2 :     ASSERT_CONDITION_TRUE (model, a, GE_EXPR, c);
    1899                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
    1900                 :            :   }
    1901                 :            : 
    1902                 :            :   /* Transitivity: "(a < b)", "(c < d)", "(b < c)" should
    1903                 :            :      imply the easy cases:
    1904                 :            :        (a < c)
    1905                 :            :        (b < d)
    1906                 :            :      but also that:
    1907                 :            :        (a < d).  */
    1908                 :          2 :   {
    1909                 :          2 :     region_model model;
    1910                 :          2 :     ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
    1911                 :          2 :     ADD_SAT_CONSTRAINT (model, c, LT_EXPR, d);
    1912                 :          2 :     ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
    1913                 :            : 
    1914                 :          2 :     ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    1915                 :          2 :     ASSERT_CONDITION_TRUE (model, b, LT_EXPR, d);
    1916                 :          2 :     ASSERT_CONDITION_TRUE (model, a, LT_EXPR, d);
    1917                 :            :   }
    1918                 :            : 
    1919                 :            :   /* Transitivity: "a >= b", "b >= a" should imply that a == b.  */
    1920                 :          2 :   {
    1921                 :          2 :     region_model model;
    1922                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    1923                 :          2 :     ADD_SAT_CONSTRAINT (model, b, GE_EXPR, a);
    1924                 :            : 
    1925                 :            :     // TODO:
    1926                 :          2 :     ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);
    1927                 :            :   }
    1928                 :            : 
    1929                 :            :   /* Transitivity: "a >= b", "b > a" should be impossible.  */
    1930                 :          2 :   {
    1931                 :          2 :     region_model model;
    1932                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    1933                 :          2 :     ADD_UNSAT_CONSTRAINT (model, b, GT_EXPR, a);
    1934                 :            :   }
    1935                 :            : 
    1936                 :            :   /* Transitivity: "a >= b", "b >= c", "c >= a" should imply
    1937                 :            :      that a == b == c.  */
    1938                 :          2 :   {
    1939                 :          2 :     region_model model;
    1940                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    1941                 :          2 :     ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
    1942                 :          2 :     ADD_SAT_CONSTRAINT (model, c, GE_EXPR, a);
    1943                 :            : 
    1944                 :          2 :     ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, c);
    1945                 :            :   }
    1946                 :            : 
    1947                 :            :   /* Transitivity: "a > b", "b > c", "c > a"
    1948                 :            :      should be impossible.  */
    1949                 :          2 :   {
    1950                 :          2 :     region_model model;
    1951                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    1952                 :          2 :     ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
    1953                 :          2 :     ADD_UNSAT_CONSTRAINT (model, c, GT_EXPR, a);
    1954                 :            :   }
    1955                 :            : 
    1956                 :          2 : }
    1957                 :            : 
    1958                 :            : /* Test various conditionals involving constants where the results
    1959                 :            :    ought to be implied based on the values of the constants.  */
    1960                 :            : 
    1961                 :            : static void
    1962                 :          2 : test_constant_comparisons ()
    1963                 :            : {
    1964                 :          2 :   tree int_3 = build_int_cst (integer_type_node, 3);
    1965                 :          2 :   tree int_4 = build_int_cst (integer_type_node, 4);
    1966                 :          2 :   tree int_5 = build_int_cst (integer_type_node, 5);
    1967                 :            : 
    1968                 :          2 :   tree int_1023 = build_int_cst (integer_type_node, 1023);
    1969                 :          2 :   tree int_1024 = build_int_cst (integer_type_node, 1024);
    1970                 :            : 
    1971                 :          2 :   tree a = build_global_decl ("a", integer_type_node);
    1972                 :          2 :   tree b = build_global_decl ("b", integer_type_node);
    1973                 :            : 
    1974                 :            :   /* Given a >= 1024, then a <= 1023 should be impossible.  */
    1975                 :          2 :   {
    1976                 :          2 :     region_model model;
    1977                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_1024);
    1978                 :          2 :     ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_1023);
    1979                 :            :   }
    1980                 :            : 
    1981                 :            :   /* a > 4.  */
    1982                 :          2 :   {
    1983                 :          2 :     region_model model;
    1984                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_4);
    1985                 :          2 :     ASSERT_CONDITION_TRUE (model, a, GT_EXPR, int_4);
    1986                 :          2 :     ASSERT_CONDITION_TRUE (model, a, NE_EXPR, int_3);
    1987                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_5);
    1988                 :            :   }
    1989                 :            : 
    1990                 :            :   /* a <= 4.  */
    1991                 :          2 :   {
    1992                 :          2 :     region_model model;
    1993                 :          2 :     ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    1994                 :          2 :     ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_4);
    1995                 :          2 :     ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_5);
    1996                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_3);
    1997                 :            :   }
    1998                 :            : 
    1999                 :            :   /* If "a > b" and "a == 3", then "b == 4" ought to be unsatisfiable.  */
    2000                 :          2 :   {
    2001                 :          2 :     region_model model;
    2002                 :          2 :     ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    2003                 :          2 :     ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_3);
    2004                 :          2 :     ADD_UNSAT_CONSTRAINT (model, b, EQ_EXPR, int_4);
    2005                 :            :   }
    2006                 :            : 
    2007                 :            :   /* Various tests of int ranges where there is only one possible candidate.  */
    2008                 :          2 :   {
    2009                 :            :     /* If "a <= 4" && "a > 3", then "a == 4",
    2010                 :            :        assuming a is of integral type.  */
    2011                 :          2 :     {
    2012                 :          2 :       region_model model;
    2013                 :          2 :       ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    2014                 :          2 :       ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    2015                 :          2 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    2016                 :            :     }
    2017                 :            : 
    2018                 :            :     /* If "a > 3" && "a <= 4", then "a == 4",
    2019                 :            :        assuming a is of integral type.  */
    2020                 :          2 :     {
    2021                 :          2 :       region_model model;
    2022                 :          2 :       ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    2023                 :          2 :       ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    2024                 :          2 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    2025                 :            :     }
    2026                 :            :     /* If "a > 3" && "a < 5", then "a == 4",
    2027                 :            :        assuming a is of integral type.  */
    2028                 :          2 :     {
    2029                 :          2 :       region_model model;
    2030                 :          2 :       ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
    2031                 :          2 :       ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
    2032                 :          2 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    2033                 :            :     }
    2034                 :            :     /* If "a >= 4" && "a < 5", then "a == 4",
    2035                 :            :        assuming a is of integral type.  */
    2036                 :          2 :     {
    2037                 :          2 :       region_model model;
    2038                 :          2 :       ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
    2039                 :          2 :       ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
    2040                 :          2 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    2041                 :            :     }
    2042                 :            :     /* If "a >= 4" && "a <= 4", then "a == 4".  */
    2043                 :          2 :     {
    2044                 :          2 :       region_model model;
    2045                 :          2 :       ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
    2046                 :          2 :       ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    2047                 :          2 :       ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    2048                 :            :     }
    2049                 :            :   }
    2050                 :            : 
    2051                 :            :   /* As above, but for floating-point:
    2052                 :            :      if "f > 3" && "f <= 4" we don't know that f == 4.  */
    2053                 :          2 :   {
    2054                 :          2 :     tree f = build_global_decl ("f", double_type_node);
    2055                 :          2 :     tree float_3 = build_real_from_int_cst (double_type_node, int_3);
    2056                 :          2 :     tree float_4 = build_real_from_int_cst (double_type_node, int_4);
    2057                 :            : 
    2058                 :          2 :     region_model model;
    2059                 :          2 :     ADD_SAT_CONSTRAINT (model, f, GT_EXPR, float_3);
    2060                 :          2 :     ADD_SAT_CONSTRAINT (model, f, LE_EXPR, float_4);
    2061                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, float_4);
    2062                 :          2 :     ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, int_4);
    2063                 :            :   }
    2064                 :          2 : }
    2065                 :            : 
    2066                 :            : /* Verify various lower-level implementation details about
    2067                 :            :    constraint_manager.  */
    2068                 :            : 
    2069                 :            : static void
    2070                 :          4 : test_constraint_impl ()
    2071                 :            : {
    2072                 :          4 :   tree int_42 = build_int_cst (integer_type_node, 42);
    2073                 :          4 :   tree int_0 = build_int_cst (integer_type_node, 0);
    2074                 :            : 
    2075                 :          4 :   tree x = build_global_decl ("x", integer_type_node);
    2076                 :          4 :   tree y = build_global_decl ("y", integer_type_node);
    2077                 :          4 :   tree z = build_global_decl ("z", integer_type_node);
    2078                 :            : 
    2079                 :            :   /* x == y.  */
    2080                 :          4 :   {
    2081                 :          4 :     region_model model;
    2082                 :            : 
    2083                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    2084                 :            : 
    2085                 :            :     /* Assert various things about the insides of model.  */
    2086                 :          4 :     constraint_manager *cm = model.get_constraints ();
    2087                 :          4 :     ASSERT_EQ (cm->m_constraints.length (), 0);
    2088                 :          4 :     ASSERT_EQ (cm->m_equiv_classes.length (), 1);
    2089                 :            :   }
    2090                 :            : 
    2091                 :            :   /* y <= z; x == y.  */
    2092                 :          4 :   {
    2093                 :          4 :     region_model model;
    2094                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    2095                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    2096                 :            : 
    2097                 :          4 :     ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
    2098                 :          4 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
    2099                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    2100                 :            : 
    2101                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    2102                 :            : 
    2103                 :            :     /* Assert various things about the insides of model.  */
    2104                 :          4 :     constraint_manager *cm = model.get_constraints ();
    2105                 :          4 :     ASSERT_EQ (cm->m_constraints.length (), 1);
    2106                 :          4 :     ASSERT_EQ (cm->m_equiv_classes.length (), 2);
    2107                 :            : 
    2108                 :            :     /* Ensure that we merged the constraints.  */
    2109                 :          4 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
    2110                 :            :   }
    2111                 :            : 
    2112                 :            :   /* y <= z; y == x.  */
    2113                 :          4 :   {
    2114                 :          4 :     region_model model;
    2115                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    2116                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    2117                 :            : 
    2118                 :          4 :     ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
    2119                 :          4 :     ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
    2120                 :          4 :     ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    2121                 :            : 
    2122                 :          4 :     ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, x);
    2123                 :            : 
    2124                 :            :     /* Assert various things about the insides of model.  */
    2125                 :          4 :     constraint_manager *cm = model.get_constraints ();
    2126                 :          4 :     ASSERT_EQ (cm->m_constraints.length (), 1);
    2127                 :          4 :     ASSERT_EQ (cm->m_equiv_classes.length (), 2);
    2128                 :            : 
    2129                 :            :     /* Ensure that we merged the constraints.  */
    2130                 :          4 :     ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
    2131                 :            :   }
    2132                 :            : 
    2133                 :            :   /* x == 0, then x != 42.  */
    2134                 :          4 :   {
    2135                 :          4 :     region_model model;
    2136                 :            : 
    2137                 :          4 :     ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    2138                 :          4 :     ADD_SAT_CONSTRAINT (model, x, NE_EXPR, int_42);
    2139                 :            : 
    2140                 :            :     /* Assert various things about the insides of model.  */
    2141                 :          4 :     constraint_manager *cm = model.get_constraints ();
    2142                 :          4 :     ASSERT_EQ (cm->m_constraints.length (), 1);
    2143                 :          4 :     ASSERT_EQ (cm->m_equiv_classes.length (), 2);
    2144                 :          4 :     ASSERT_EQ (cm->m_constraints[0].m_lhs,
    2145                 :            :                cm->get_or_add_equiv_class (model.get_rvalue (int_0, NULL)));
    2146                 :          4 :     ASSERT_EQ (cm->m_constraints[0].m_rhs,
    2147                 :            :                cm->get_or_add_equiv_class (model.get_rvalue (int_42, NULL)));
    2148                 :          4 :     ASSERT_EQ (cm->m_constraints[0].m_op, CONSTRAINT_LT);
    2149                 :            :   }
    2150                 :            : 
    2151                 :            :   // TODO: selftest for merging ecs "in the middle"
    2152                 :            :   // where a non-final one gets overwritten
    2153                 :            : 
    2154                 :            :   // TODO: selftest where there are pre-existing constraints
    2155                 :          4 : }
    2156                 :            : 
    2157                 :            : /* Check that operator== and hashing works as expected for the
    2158                 :            :    various types.  */
    2159                 :            : 
    2160                 :            : static void
    2161                 :          4 : test_equality ()
    2162                 :            : {
    2163                 :          4 :   tree x = build_global_decl ("x", integer_type_node);
    2164                 :          4 :   tree y = build_global_decl ("y", integer_type_node);
    2165                 :            : 
    2166                 :          4 :   {
    2167                 :          8 :     region_model model0;
    2168                 :          8 :     region_model model1;
    2169                 :            : 
    2170                 :          4 :     constraint_manager *cm0 = model0.get_constraints ();
    2171                 :          4 :     constraint_manager *cm1 = model1.get_constraints ();
    2172                 :            : 
    2173                 :          4 :     ASSERT_EQ (cm0->hash (), cm1->hash ());
    2174                 :          4 :     ASSERT_EQ (*cm0, *cm1);
    2175                 :            : 
    2176                 :          4 :     ASSERT_EQ (model0.hash (), model1.hash ());
    2177                 :          4 :     ASSERT_EQ (model0, model1);
    2178                 :            : 
    2179                 :          4 :     ADD_SAT_CONSTRAINT (model1, x, EQ_EXPR, y);
    2180                 :          4 :     ASSERT_NE (cm0->hash (), cm1->hash ());
    2181                 :          4 :     ASSERT_NE (*cm0, *cm1);
    2182                 :            : 
    2183                 :          4 :     ASSERT_NE (model0.hash (), model1.hash ());
    2184                 :          4 :     ASSERT_NE (model0, model1);
    2185                 :            : 
    2186                 :          4 :     region_model model2;
    2187                 :          4 :     constraint_manager *cm2 = model2.get_constraints ();
    2188                 :            :     /* Make the same change to cm2.  */
    2189                 :          4 :     ADD_SAT_CONSTRAINT (model2, x, EQ_EXPR, y);
    2190                 :          4 :     ASSERT_EQ (cm1->hash (), cm2->hash ());
    2191                 :          4 :     ASSERT_EQ (*cm1, *cm2);
    2192                 :            : 
    2193                 :          4 :     ASSERT_EQ (model1.hash (), model2.hash ());
    2194                 :          4 :     ASSERT_EQ (model1, model2);
    2195                 :            :   }
    2196                 :          4 : }
    2197                 :            : 
    2198                 :            : /* Verify tracking inequality of a variable against many constants.  */
    2199                 :            : 
    2200                 :            : static void
    2201                 :          4 : test_many_constants ()
    2202                 :            : {
    2203                 :          4 :   tree a = build_global_decl ("a", integer_type_node);
    2204                 :            : 
    2205                 :          4 :   region_model model;
    2206                 :          8 :   auto_vec<tree> constants;
    2207                 :         84 :   for (int i = 0; i < 20; i++)
    2208                 :            :     {
    2209                 :         80 :       tree constant = build_int_cst (integer_type_node, i);
    2210                 :         80 :       constants.safe_push (constant);
    2211                 :         80 :       ADD_SAT_CONSTRAINT (model, a, NE_EXPR, constant);
    2212                 :            : 
    2213                 :            :       /* Merge, and check the result.  */
    2214                 :        160 :       region_model other (model);
    2215                 :            : 
    2216                 :        160 :       region_model merged;
    2217                 :         80 :       ASSERT_TRUE (model.can_merge_with_p (other, &merged));
    2218                 :         80 :       model.canonicalize (NULL);
    2219                 :         80 :       merged.canonicalize (NULL);
    2220                 :         80 :       ASSERT_EQ (model, merged);
    2221                 :            : 
    2222                 :        920 :       for (int j = 0; j <= i; j++)
    2223                 :        840 :         ASSERT_CONDITION_TRUE (model, a, NE_EXPR, constants[j]);
    2224                 :            :     }
    2225                 :          4 : }
    2226                 :            : 
    2227                 :            : /* Run the selftests in this file, temporarily overriding
    2228                 :            :    flag_analyzer_transitivity with TRANSITIVITY.  */
    2229                 :            : 
    2230                 :            : static void
    2231                 :          4 : run_constraint_manager_tests (bool transitivity)
    2232                 :            : {
    2233                 :          4 :   int saved_flag_analyzer_transitivity = flag_analyzer_transitivity;
    2234                 :          4 :   flag_analyzer_transitivity = transitivity;
    2235                 :            : 
    2236                 :          4 :   test_constraint_conditions ();
    2237                 :          4 :   if (flag_analyzer_transitivity)
    2238                 :            :     {
    2239                 :            :       /* These selftests assume transitivity.  */
    2240                 :          2 :       test_transitivity ();
    2241                 :          2 :       test_constant_comparisons ();
    2242                 :            :     }
    2243                 :          4 :   test_constraint_impl ();
    2244                 :          4 :   test_equality ();
    2245                 :          4 :   test_many_constants ();
    2246                 :            : 
    2247                 :          4 :   flag_analyzer_transitivity = saved_flag_analyzer_transitivity;
    2248                 :          4 : }
    2249                 :            : 
    2250                 :            : /* Run all of the selftests within this file.  */
    2251                 :            : 
    2252                 :            : void
    2253                 :          2 : analyzer_constraint_manager_cc_tests ()
    2254                 :            : {
    2255                 :            :   /* Run the tests twice: with and without transitivity.  */
    2256                 :          2 :   run_constraint_manager_tests (true);
    2257                 :          2 :   run_constraint_manager_tests (false);
    2258                 :          2 : }
    2259                 :            : 
    2260                 :            : } // namespace selftest
    2261                 :            : 
    2262                 :            : #endif /* CHECKING_P */
    2263                 :            : 
    2264                 :            : } // namespace ana
    2265                 :            : 
    2266                 :            : #endif /* #if ENABLE_ANALYZER */

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.