LCOV - code coverage report
Current view: top level - gcc/analyzer - region-model.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 283 343 82.5 %
Date: 2020-03-28 11:57:23 Functions: 81 98 82.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Classes for modeling the state of memory.
       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                 :            : #ifndef GCC_ANALYZER_REGION_MODEL_H
      22                 :            : #define GCC_ANALYZER_REGION_MODEL_H
      23                 :            : 
      24                 :            : /* Implementation of the region-based ternary model described in:
      25                 :            :      "A Memory Model for Static Analysis of C Programs"
      26                 :            :       (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
      27                 :            :      http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf  */
      28                 :            : 
      29                 :            : /* A tree, extended with stack frame information for locals, so that
      30                 :            :    we can distinguish between different values of locals within a potentially
      31                 :            :    recursive callstack.  */
      32                 :            : // TODO: would this be better as a new tree code?
      33                 :            : 
      34                 :            : using namespace ana;
      35                 :            : 
      36                 :            : namespace ana {
      37                 :            : 
      38                 :            : class path_var
      39                 :            : {
      40                 :            : public:
      41                 :     354484 :   path_var (tree t, int stack_depth)
      42                 :     882863 :   : m_tree (t), m_stack_depth (stack_depth)
      43                 :            :   {
      44                 :            :     // TODO: ignore stack depth for globals and constants
      45                 :            :   }
      46                 :            : 
      47                 :       2202 :   bool operator== (const path_var &other) const
      48                 :            :   {
      49                 :       2202 :     return (m_tree == other.m_tree
      50                 :       2202 :             && m_stack_depth == other.m_stack_depth);
      51                 :            :   }
      52                 :            : 
      53                 :            :   void dump (pretty_printer *pp) const;
      54                 :            : 
      55                 :            :   tree m_tree;
      56                 :            :   int m_stack_depth; // or -1 for globals?
      57                 :            : };
      58                 :            : 
      59                 :            : } // namespace ana
      60                 :            : 
      61                 :            : namespace inchash
      62                 :            : {
      63                 :            :   extern void add_path_var (path_var pv, hash &hstate);
      64                 :            : } // namespace inchash
      65                 :            : 
      66                 :            : 
      67                 :            : namespace ana {
      68                 :            : 
      69                 :            : /* A region_model is effectively a graph of regions and symbolic values.
      70                 :            :    We store per-model IDs rather than pointers to make it easier to clone
      71                 :            :    and to compare graphs.  */
      72                 :            : 
      73                 :            : /* An ID for an svalue within a region_model.  Internally, this is an index
      74                 :            :    into a vector of svalue * within the region_model.  */
      75                 :            : 
      76                 :            : class svalue_id
      77                 :            : {
      78                 :            : public:
      79                 :   31166480 :   static svalue_id null () { return svalue_id (-1); }
      80                 :            : 
      81                 :    1196880 :   svalue_id () : m_idx (-1) {}
      82                 :            : 
      83                 :    7806476 :   bool operator== (const svalue_id &other) const
      84                 :            :   {
      85                 :    7724717 :     return m_idx == other.m_idx;
      86                 :            :   }
      87                 :            : 
      88                 :    1272555 :   bool operator!= (const svalue_id &other) const
      89                 :            :   {
      90                 :    1272555 :     return m_idx != other.m_idx;
      91                 :            :   }
      92                 :            : 
      93                 :   83576463 :   bool null_p () const { return m_idx == -1; }
      94                 :            : 
      95                 :    4435910 :   static svalue_id from_int (int idx) { return svalue_id (idx); }
      96                 :   19552980 :   int as_int () const { return m_idx; }
      97                 :            : 
      98                 :            :   void print (pretty_printer *pp) const;
      99                 :            :   void dump_node_name_to_pp (pretty_printer *pp) const;
     100                 :            : 
     101                 :            :   void validate (const region_model &model) const;
     102                 :            : 
     103                 :            : private:
     104                 :   26552567 :   svalue_id (int idx) : m_idx (idx) {}
     105                 :            : 
     106                 :            :   int m_idx;
     107                 :            : };
     108                 :            : 
     109                 :            : /* An ID for a region within a region_model.  Internally, this is an index
     110                 :            :    into a vector of region * within the region_model.  */
     111                 :            : 
     112                 :            : class region_id
     113                 :            : {
     114                 :            : public:
     115                 :   10783500 :   static region_id null () { return region_id (-1); }
     116                 :            : 
     117                 :     178446 :   region_id () : m_idx (-1) {}
     118                 :            : 
     119                 :    1368184 :   bool operator== (const region_id &other) const
     120                 :            :   {
     121                 :     476502 :     return m_idx == other.m_idx;
     122                 :            :   }
     123                 :            : 
     124                 :    1068040 :   bool operator!= (const region_id &other) const
     125                 :            :   {
     126                 :     972354 :     return m_idx != other.m_idx;
     127                 :            :   }
     128                 :            : 
     129                 :   35926795 :   bool null_p () const { return m_idx == -1; }
     130                 :            : 
     131                 :    6645580 :   static region_id from_int (int idx) { return region_id (idx); }
     132                 :   14884400 :   int as_int () const { return m_idx; }
     133                 :            : 
     134                 :            :   void print (pretty_printer *pp) const;
     135                 :            :   void dump_node_name_to_pp (pretty_printer *pp) const;
     136                 :            : 
     137                 :            :   void validate (const region_model &model) const;
     138                 :            : 
     139                 :            : private:
     140                 :    6826240 :   region_id (int idx) : m_idx (idx) {}
     141                 :            : 
     142                 :            :   int m_idx;
     143                 :            : };
     144                 :            : 
     145                 :            : /* A class for renumbering IDs within a region_model, mapping old IDs
     146                 :            :    to new IDs (e.g. when removing one or more elements, thus needing to
     147                 :            :    renumber).  */
     148                 :            : // TODO: could this be useful for equiv_class_ids?
     149                 :            : 
     150                 :            : template <typename T>
     151                 :            : class id_map
     152                 :            : {
     153                 :            :  public:
     154                 :            :   id_map (int num_ids);
     155                 :            :   void put (T src, T dst);
     156                 :            :   T get_dst_for_src (T src) const;
     157                 :            :   T get_src_for_dst (T dst) const;
     158                 :            :   void dump_to_pp (pretty_printer *pp) const;
     159                 :            :   void dump () const;
     160                 :            :   void update (T *) const;
     161                 :            : 
     162                 :            :  private:
     163                 :            :   auto_vec<T> m_src_to_dst;
     164                 :            :   auto_vec<T> m_dst_to_src;
     165                 :            : };
     166                 :            : 
     167                 :            : typedef id_map<svalue_id> svalue_id_map;
     168                 :            : typedef id_map<region_id> region_id_map;
     169                 :            : 
     170                 :            : /* class id_map.  */
     171                 :            : 
     172                 :            : /* id_map's ctor, which populates the map with dummy null values.  */
     173                 :            : 
     174                 :            : template <typename T>
     175                 :     179629 : inline id_map<T>::id_map (int num_svalues)
     176                 :            : : m_src_to_dst (num_svalues),
     177                 :     358881 :   m_dst_to_src (num_svalues)
     178                 :            : {
     179                 :    2356700 :   for (int i = 0; i < num_svalues; i++)
     180                 :            :     {
     181                 :    2177075 :       m_src_to_dst.quick_push (T::null ());
     182                 :    2177075 :       m_dst_to_src.quick_push (T::null ());
     183                 :            :     }
     184                 :     179629 : }
     185                 :            : 
     186                 :            : /* Record that SRC is to be mapped to DST.  */
     187                 :            : 
     188                 :            : template <typename T>
     189                 :            : inline void
     190                 :    2177075 : id_map<T>::put (T src, T dst)
     191                 :            : {
     192                 :    2177075 :   m_src_to_dst[src.as_int ()] = dst;
     193                 :    2177075 :   m_dst_to_src[dst.as_int ()] = src;
     194                 :    2177075 : }
     195                 :            : 
     196                 :            : /* Get the new value for SRC within the map.  */
     197                 :            : 
     198                 :            : template <typename T>
     199                 :            : inline T
     200                 :    9402467 : id_map<T>::get_dst_for_src (T src) const
     201                 :            : {
     202                 :    9402467 :   if (src.null_p ())
     203                 :    2678413 :     return src;
     204                 :    6724048 :   return m_src_to_dst[src.as_int ()];
     205                 :            : }
     206                 :            : 
     207                 :            : /* Given DST, a new value, determine which old value will be mapped to it
     208                 :            :    (the inverse of the map).  */
     209                 :            : 
     210                 :            : template <typename T>
     211                 :            : inline T
     212                 :    2177293 : id_map<T>::get_src_for_dst (T dst) const
     213                 :            : {
     214                 :    2177293 :   if (dst.null_p ())
     215                 :          0 :     return dst;
     216                 :    2177293 :   return m_dst_to_src[dst.as_int ()];
     217                 :            : }
     218                 :            : 
     219                 :            : /* Dump this id_map to PP.  */
     220                 :            : 
     221                 :            : template <typename T>
     222                 :            : inline void
     223                 :          0 : id_map<T>::dump_to_pp (pretty_printer *pp) const
     224                 :            : {
     225                 :          0 :   pp_string (pp, "src to dst: {");
     226                 :            :   unsigned i;
     227                 :            :   T *dst;
     228                 :          0 :   FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
     229                 :            :     {
     230                 :          0 :       if (i > 0)
     231                 :          0 :         pp_string (pp, ", ");
     232                 :          0 :       T src (T::from_int (i));
     233                 :          0 :       src.print (pp);
     234                 :          0 :       pp_string (pp, " -> ");
     235                 :          0 :       dst->print (pp);
     236                 :            :     }
     237                 :          0 :   pp_string (pp, "}");
     238                 :          0 :   pp_newline (pp);
     239                 :            : 
     240                 :          0 :   pp_string (pp, "dst to src: {");
     241                 :            :   T *src;
     242                 :          0 :   FOR_EACH_VEC_ELT (m_dst_to_src, i, src)
     243                 :            :     {
     244                 :          0 :       if (i > 0)
     245                 :          0 :         pp_string (pp, ", ");
     246                 :          0 :       T dst (T::from_int (i));
     247                 :          0 :       dst.print (pp);
     248                 :          0 :       pp_string (pp, " <- ");
     249                 :          0 :       src->print (pp);
     250                 :            :     }
     251                 :          0 :   pp_string (pp, "}");
     252                 :          0 :   pp_newline (pp);
     253                 :          0 : }
     254                 :            : 
     255                 :            : /* Dump this id_map to stderr.  */
     256                 :            : 
     257                 :            : template <typename T>
     258                 :            : DEBUG_FUNCTION inline void
     259                 :          0 : id_map<T>::dump () const
     260                 :            : {
     261                 :          0 :   pretty_printer pp;
     262                 :          0 :   pp.buffer->stream = stderr;
     263                 :          0 :   dump_to_pp (&pp);
     264                 :          0 :   pp_flush (&pp);
     265                 :          0 : }
     266                 :            : 
     267                 :            : /* Update *ID from the old value to its new value in this map.  */
     268                 :            : 
     269                 :            : template <typename T>
     270                 :            : inline void
     271                 :    5998017 : id_map<T>::update (T *id) const
     272                 :            : {
     273                 :    5667363 :   *id = get_dst_for_src (*id);
     274                 :     761572 : }
     275                 :            : 
     276                 :            : /* Variant of the above, which only stores things in one direction.
     277                 :            :    (e.g. for merging, when the number of destination regions is not
     278                 :            :    the same of the src regions, and can grow).  */
     279                 :            : 
     280                 :            : template <typename T>
     281                 :     430700 : class one_way_id_map
     282                 :            : {
     283                 :            :  public:
     284                 :            :   one_way_id_map (int num_ids);
     285                 :            :   void put (T src, T dst);
     286                 :            :   T get_dst_for_src (T src) const;
     287                 :            :   void dump_to_pp (pretty_printer *pp) const;
     288                 :            :   void dump () const;
     289                 :            :   void update (T *) const;
     290                 :            : 
     291                 :            :  private:
     292                 :            :   auto_vec<T> m_src_to_dst;
     293                 :            : };
     294                 :            : 
     295                 :            : typedef one_way_id_map<svalue_id> one_way_svalue_id_map;
     296                 :            : typedef one_way_id_map<region_id> one_way_region_id_map;
     297                 :            : 
     298                 :            : /* class one_way_id_map.  */
     299                 :            : 
     300                 :            : /* one_way_id_map's ctor, which populates the map with dummy null values.  */
     301                 :            : 
     302                 :            : template <typename T>
     303                 :    1084467 : inline one_way_id_map<T>::one_way_id_map (int num_svalues)
     304                 :    1084467 : : m_src_to_dst (num_svalues)
     305                 :            : {
     306                 :   11856470 :   for (int i = 0; i < num_svalues; i++)
     307                 :   10772010 :     m_src_to_dst.quick_push (T::null ());
     308                 :    1084467 : }
     309                 :            : 
     310                 :            : /* Record that SRC is to be mapped to DST.  */
     311                 :            : 
     312                 :            : template <typename T>
     313                 :            : inline void
     314                 :    2076231 : one_way_id_map<T>::put (T src, T dst)
     315                 :            : {
     316                 :    2076231 :   m_src_to_dst[src.as_int ()] = dst;
     317                 :            : }
     318                 :            : 
     319                 :            : /* Get the new value for SRC within the map.  */
     320                 :            : 
     321                 :            : template <typename T>
     322                 :            : inline T
     323                 :    6679718 : one_way_id_map<T>::get_dst_for_src (T src) const
     324                 :            : {
     325                 :    6679718 :   if (src.null_p ())
     326                 :     349041 :     return src;
     327                 :    6330677 :   return m_src_to_dst[src.as_int ()];
     328                 :            : }
     329                 :            : 
     330                 :            : /* Dump this map to PP.  */
     331                 :            : 
     332                 :            : template <typename T>
     333                 :            : inline void
     334                 :          0 : one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
     335                 :            : {
     336                 :          0 :   pp_string (pp, "src to dst: {");
     337                 :            :   unsigned i;
     338                 :            :   T *dst;
     339                 :          0 :   FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
     340                 :            :     {
     341                 :          0 :       if (i > 0)
     342                 :          0 :         pp_string (pp, ", ");
     343                 :          0 :       T src (T::from_int (i));
     344                 :          0 :       src.print (pp);
     345                 :          0 :       pp_string (pp, " -> ");
     346                 :          0 :       dst->print (pp);
     347                 :            :     }
     348                 :          0 :   pp_string (pp, "}");
     349                 :          0 :   pp_newline (pp);
     350                 :          0 : }
     351                 :            : 
     352                 :            : /* Dump this map to stderr.  */
     353                 :            : 
     354                 :            : template <typename T>
     355                 :            : DEBUG_FUNCTION inline void
     356                 :          0 : one_way_id_map<T>::dump () const
     357                 :            : {
     358                 :          0 :   pretty_printer pp;
     359                 :          0 :   pp.buffer->stream = stderr;
     360                 :          0 :   dump_to_pp (&pp);
     361                 :          0 :   pp_flush (&pp);
     362                 :          0 : }
     363                 :            : 
     364                 :            : /* Update *ID from the old value to its new value in this map.  */
     365                 :            : 
     366                 :            : template <typename T>
     367                 :            : inline void
     368                 :     590283 : one_way_id_map<T>::update (T *id) const
     369                 :            : {
     370                 :     469662 :   *id = get_dst_for_src (*id);
     371                 :            : }
     372                 :            : 
     373                 :            : /* A set of IDs within a region_model (either svalue_id or region_id).  */
     374                 :            : 
     375                 :            : template <typename T>
     376                 :      30523 : class id_set
     377                 :            : {
     378                 :            : public:
     379                 :            :   id_set (const region_model *model);
     380                 :            : 
     381                 :      28943 :   void add_region (T id)
     382                 :            :   {
     383                 :      28943 :     if (!id.null_p ())
     384                 :      28943 :       bitmap_set_bit (m_bitmap, id.as_int ());
     385                 :      28943 :   }
     386                 :            : 
     387                 :     873927 :   bool region_p (T id) const
     388                 :            :   {
     389                 :     873927 :     gcc_assert (!id.null_p ());
     390                 :     873927 :     return bitmap_bit_p (const_cast <auto_sbitmap &> (m_bitmap),
     391                 :     873927 :                          id.as_int ());
     392                 :            :   }
     393                 :            : 
     394                 :          2 :   unsigned int num_regions ()
     395                 :            :   {
     396                 :          2 :     return bitmap_count_bits (m_bitmap);
     397                 :            :   }
     398                 :            : 
     399                 :            : private:
     400                 :            :   auto_sbitmap m_bitmap;
     401                 :            : };
     402                 :            : 
     403                 :            : typedef id_set<region_id> region_id_set;
     404                 :            : 
     405                 :            : /* Various operations delete information from a region_model.
     406                 :            : 
     407                 :            :    This struct tracks how many of each kind of entity were purged (e.g.
     408                 :            :    for selftests, and for debugging).  */
     409                 :            : 
     410                 :            : struct purge_stats
     411                 :            : {
     412                 :      29966 :   purge_stats ()
     413                 :      29966 :   : m_num_svalues (0),
     414                 :            :     m_num_regions (0),
     415                 :            :     m_num_equiv_classes (0),
     416                 :            :     m_num_constraints (0),
     417                 :      29966 :     m_num_client_items (0)
     418                 :            :   {}
     419                 :            : 
     420                 :            :   int m_num_svalues;
     421                 :            :   int m_num_regions;
     422                 :            :   int m_num_equiv_classes;
     423                 :            :   int m_num_constraints;
     424                 :            :   int m_num_client_items;
     425                 :            : };
     426                 :            : 
     427                 :            : /* An enum for discriminating between the different concrete subclasses
     428                 :            :    of svalue.  */
     429                 :            : 
     430                 :            : enum svalue_kind
     431                 :            : {
     432                 :            :   SK_REGION,
     433                 :            :   SK_CONSTANT,
     434                 :            :   SK_UNKNOWN,
     435                 :            :   SK_POISONED,
     436                 :            :   SK_SETJMP
     437                 :            : };
     438                 :            : 
     439                 :            : /* svalue and its subclasses.
     440                 :            : 
     441                 :            :    The class hierarchy looks like this (using indentation to show
     442                 :            :    inheritance, and with svalue_kinds shown for the concrete subclasses):
     443                 :            : 
     444                 :            :    svalue
     445                 :            :      region_svalue (SK_REGION)
     446                 :            :      constant_svalue (SK_CONSTANT)
     447                 :            :      unknown_svalue (SK_UNKNOWN)
     448                 :            :      poisoned_svalue (SK_POISONED)
     449                 :            :      setjmp_svalue (SK_SETJMP).  */
     450                 :            : 
     451                 :            : /* An abstract base class representing a value held by a region of memory.  */
     452                 :            : 
     453                 :            : class svalue
     454                 :            : {
     455                 :            : public:
     456                 :            :   virtual ~svalue () {}
     457                 :            : 
     458                 :            :   bool operator== (const svalue &other) const;
     459                 :         30 :   bool operator!= (const svalue &other) const { return !(*this == other); }
     460                 :            : 
     461                 :            :   virtual svalue *clone () const = 0;
     462                 :            : 
     463                 :    4158879 :   tree get_type () const { return m_type; }
     464                 :            : 
     465                 :            :   virtual enum svalue_kind get_kind () const = 0;
     466                 :            : 
     467                 :            :   hashval_t hash () const;
     468                 :            : 
     469                 :            :   void print (const region_model &model,
     470                 :            :               svalue_id this_sid,
     471                 :            :               pretty_printer *pp) const;
     472                 :            : 
     473                 :            :   virtual void dump_dot_to_pp (const region_model &model,
     474                 :            :                                svalue_id this_sid,
     475                 :            :                                pretty_printer *pp) const;
     476                 :            : 
     477                 :     694410 :   virtual region_svalue *dyn_cast_region_svalue () { return NULL; }
     478                 :      23554 :   virtual constant_svalue *dyn_cast_constant_svalue () { return NULL; }
     479                 :    4604930 :   virtual const constant_svalue *dyn_cast_constant_svalue () const
     480                 :    4604930 :   { return NULL; }
     481                 :          0 :   virtual poisoned_svalue *dyn_cast_poisoned_svalue () { return NULL; }
     482                 :        161 :   virtual unknown_svalue *dyn_cast_unknown_svalue () { return NULL; }
     483                 :          1 :   virtual setjmp_svalue *dyn_cast_setjmp_svalue () { return NULL; }
     484                 :            : 
     485                 :            :   virtual void remap_region_ids (const region_id_map &map);
     486                 :            : 
     487                 :            :   virtual void walk_for_canonicalization (canonicalization *c) const;
     488                 :            : 
     489                 :            :   virtual svalue_id get_child_sid (region *parent, region *child,
     490                 :            :                                    region_model &model,
     491                 :            :                                    region_model_context *ctxt);
     492                 :            : 
     493                 :            :   tree maybe_get_constant () const;
     494                 :            : 
     495                 :            :  protected:
     496                 :    3118319 :   svalue (tree type) : m_type (type) {}
     497                 :            : 
     498                 :            :   virtual void add_to_hash (inchash::hash &hstate) const = 0;
     499                 :            : 
     500                 :            :  private:
     501                 :            :   virtual void print_details (const region_model &model,
     502                 :            :                               svalue_id this_sid,
     503                 :            :                               pretty_printer *pp) const = 0;
     504                 :            :   tree m_type;
     505                 :            : };
     506                 :            : 
     507                 :            : /* Concrete subclass of svalue representing a pointer value that points to
     508                 :            :    a known region  */
     509                 :            : 
     510                 :            : class region_svalue : public svalue
     511                 :            : {
     512                 :            : public:
     513                 :     320110 :   region_svalue (tree type, region_id rid) : svalue (type), m_rid (rid)
     514                 :            :   {
     515                 :            :     /* Should we support NULL ptrs here?  */
     516                 :     161249 :     gcc_assert (!rid.null_p ());
     517                 :            :   }
     518                 :            : 
     519                 :            :   bool compare_fields (const region_svalue &other) const;
     520                 :            : 
     521                 :     158859 :   svalue *clone () const FINAL OVERRIDE
     522                 :     158859 :   { return new region_svalue (get_type (), m_rid); }
     523                 :            : 
     524                 :    1541580 :   enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_REGION; }
     525                 :            : 
     526                 :            :   void dump_dot_to_pp (const region_model &model,
     527                 :            :                        svalue_id this_sid,
     528                 :            :                        pretty_printer *pp) const
     529                 :            :     FINAL OVERRIDE;
     530                 :            : 
     531                 :     195590 :   region_svalue *dyn_cast_region_svalue () FINAL OVERRIDE { return this; }
     532                 :            : 
     533                 :     362328 :   region_id get_pointee () const { return m_rid; }
     534                 :            : 
     535                 :            :   void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
     536                 :            : 
     537                 :            :   static void merge_values (const region_svalue &region_sval_a,
     538                 :            :                             const region_svalue &region_sval_b,
     539                 :            :                             svalue_id *merged_sid,
     540                 :            :                             tree type,
     541                 :            :                             model_merger *merger);
     542                 :            : 
     543                 :            :   void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
     544                 :            : 
     545                 :            :   static tristate eval_condition (region_svalue *lhs_ptr,
     546                 :            :                                   enum tree_code op,
     547                 :            :                                   region_svalue *rhs_ptr);
     548                 :            : 
     549                 :            :   void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
     550                 :            : 
     551                 :            :  private:
     552                 :            :   void print_details (const region_model &model,
     553                 :            :                       svalue_id this_sid,
     554                 :            :                       pretty_printer *pp) const
     555                 :            :     FINAL OVERRIDE;
     556                 :            : 
     557                 :            :   region_id m_rid;
     558                 :            : };
     559                 :            : 
     560                 :            : } // namespace ana
     561                 :            : 
     562                 :            : template <>
     563                 :            : template <>
     564                 :            : inline bool
     565                 :     355413 : is_a_helper <region_svalue *>::test (svalue *sval)
     566                 :            : {
     567                 :     355413 :   return sval->get_kind () == SK_REGION;
     568                 :            : }
     569                 :            : 
     570                 :            : namespace ana {
     571                 :            : 
     572                 :            : /* Concrete subclass of svalue representing a specific constant value.  */
     573                 :            : 
     574                 :            : class constant_svalue : public svalue
     575                 :            : {
     576                 :            : public:
     577                 :     963607 :   constant_svalue (tree cst_expr)
     578                 :     963607 :   : svalue (TREE_TYPE (cst_expr)), m_cst_expr (cst_expr)
     579                 :            :   {
     580                 :     963607 :     gcc_assert (cst_expr);
     581                 :     963607 :     gcc_assert (CONSTANT_CLASS_P (cst_expr));
     582                 :     963607 :   }
     583                 :            : 
     584                 :            :   bool compare_fields (const constant_svalue &other) const;
     585                 :            : 
     586                 :     378110 :   svalue *clone () const FINAL OVERRIDE
     587                 :     378110 :   { return new constant_svalue (m_cst_expr); }
     588                 :            : 
     589                 :    2063820 :   enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_CONSTANT; }
     590                 :            : 
     591                 :            :   void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
     592                 :            : 
     593                 :       7911 :   constant_svalue *dyn_cast_constant_svalue () FINAL OVERRIDE { return this; }
     594                 :    2173640 :   const constant_svalue *dyn_cast_constant_svalue () const FINAL OVERRIDE
     595                 :    2173640 :   { return this; }
     596                 :            : 
     597                 :    3022770 :   tree get_constant () const { return m_cst_expr; }
     598                 :            : 
     599                 :            :   static void merge_values (const constant_svalue &cst_sval_a,
     600                 :            :                             const constant_svalue &cst_sval_b,
     601                 :            :                             svalue_id *merged_sid,
     602                 :            :                             model_merger *merger);
     603                 :            : 
     604                 :            :   static tristate eval_condition (constant_svalue *lhs,
     605                 :            :                                   enum tree_code op,
     606                 :            :                                   constant_svalue *rhs);
     607                 :            : 
     608                 :            :   svalue_id get_child_sid (region *parent, region *child,
     609                 :            :                            region_model &model,
     610                 :            :                            region_model_context *ctxt) FINAL OVERRIDE;
     611                 :            : 
     612                 :            :  private:
     613                 :            :   void print_details (const region_model &model,
     614                 :            :                       svalue_id this_sid,
     615                 :            :                       pretty_printer *pp) const
     616                 :            :     FINAL OVERRIDE;
     617                 :            : 
     618                 :            :   tree m_cst_expr;
     619                 :            : };
     620                 :            : 
     621                 :            : } // namespace ana
     622                 :            : 
     623                 :            : template <>
     624                 :            : template <>
     625                 :            : inline bool
     626                 :      25910 : is_a_helper <constant_svalue *>::test (svalue *sval)
     627                 :            : {
     628                 :      25910 :   return sval->get_kind () == SK_CONSTANT;
     629                 :            : }
     630                 :            : 
     631                 :            : namespace ana {
     632                 :            : 
     633                 :            : /* Concrete subclass of svalue representing a unique but unknown value.
     634                 :            :    Comparisons of variables that share the same unknown value are known
     635                 :            :    to be equal, even if we don't know what the value is.  */
     636                 :            : 
     637                 :            : class unknown_svalue : public svalue
     638                 :            : {
     639                 :            : public:
     640                 :    1211420 :   unknown_svalue (tree type)
     641                 :     588932 :   : svalue (type)
     642                 :            :   {}
     643                 :            : 
     644                 :            :   bool compare_fields (const unknown_svalue &other) const;
     645                 :            : 
     646                 :     622482 :   svalue *clone () const FINAL OVERRIDE
     647                 :     622482 :   { return new unknown_svalue (get_type ()); }
     648                 :            : 
     649                 :    2046500 :   enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNKNOWN; }
     650                 :            : 
     651                 :            :   void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
     652                 :            : 
     653                 :        229 :   unknown_svalue *dyn_cast_unknown_svalue () FINAL OVERRIDE { return this; }
     654                 :            : 
     655                 :            :  private:
     656                 :            :   void print_details (const region_model &model,
     657                 :            :                       svalue_id this_sid,
     658                 :            :                       pretty_printer *pp) const
     659                 :            :     FINAL OVERRIDE;
     660                 :            : };
     661                 :            : 
     662                 :            : /* An enum describing a particular kind of "poisoned" value.  */
     663                 :            : 
     664                 :            : enum poison_kind
     665                 :            : {
     666                 :            :   /* For use to describe uninitialized memory.  */
     667                 :            :   POISON_KIND_UNINIT,
     668                 :            : 
     669                 :            :   /* For use to describe freed memory.  */
     670                 :            :   POISON_KIND_FREED,
     671                 :            : 
     672                 :            :   /* For use on pointers to regions within popped stack frames.  */
     673                 :            :   POISON_KIND_POPPED_STACK
     674                 :            : };
     675                 :            : 
     676                 :            : extern const char *poison_kind_to_str (enum poison_kind);
     677                 :            : 
     678                 :            : /* Concrete subclass of svalue representing a value that should not
     679                 :            :    be used (e.g. uninitialized memory, freed memory).  */
     680                 :            : 
     681                 :            : class poisoned_svalue : public svalue
     682                 :            : {
     683                 :            : public:
     684                 :     621802 :   poisoned_svalue (enum poison_kind kind, tree type)
     685                 :     309938 :   : svalue (type), m_kind (kind) {}
     686                 :            : 
     687                 :            :   bool compare_fields (const poisoned_svalue &other) const;
     688                 :            : 
     689                 :     311862 :   svalue *clone () const FINAL OVERRIDE
     690                 :     311862 :   { return new poisoned_svalue (m_kind, get_type ()); }
     691                 :            : 
     692                 :     647271 :   enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_POISONED; }
     693                 :            : 
     694                 :            :   void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
     695                 :            : 
     696                 :     368776 :   poisoned_svalue *dyn_cast_poisoned_svalue () FINAL OVERRIDE { return this; }
     697                 :            : 
     698                 :     368788 :   enum poison_kind get_poison_kind () const { return m_kind; }
     699                 :            : 
     700                 :            :  private:
     701                 :            :   void print_details (const region_model &model,
     702                 :            :                       svalue_id this_sid,
     703                 :            :                       pretty_printer *pp) const
     704                 :            :     FINAL OVERRIDE;
     705                 :            : 
     706                 :            :   enum poison_kind m_kind;
     707                 :            : };
     708                 :            : 
     709                 :            : } // namespace ana
     710                 :            : 
     711                 :            : template <>
     712                 :            : template <>
     713                 :            : inline bool
     714                 :         12 : is_a_helper <poisoned_svalue *>::test (svalue *sval)
     715                 :            : {
     716                 :         12 :   return sval->get_kind () == SK_POISONED;
     717                 :            : }
     718                 :            : 
     719                 :            : namespace ana {
     720                 :            : 
     721                 :            : /* A bundle of information recording a setjmp/sigsetjmp call, corresponding
     722                 :            :    roughly to a jmp_buf.  */
     723                 :            : 
     724                 :            : struct setjmp_record
     725                 :            : {
     726                 :         11 :   setjmp_record (const exploded_node *enode,
     727                 :            :                  const gcall *setjmp_call)
     728                 :         11 :   : m_enode (enode), m_setjmp_call (setjmp_call)
     729                 :            :   {
     730                 :            :   }
     731                 :            : 
     732                 :        235 :   bool operator== (const setjmp_record &other) const
     733                 :            :   {
     734                 :        235 :     return (m_enode == other.m_enode
     735                 :        235 :             && m_setjmp_call == other.m_setjmp_call);
     736                 :            :   }
     737                 :            : 
     738                 :            :   const exploded_node *m_enode;
     739                 :            :   const gcall *m_setjmp_call;
     740                 :            : };
     741                 :            : 
     742                 :            : /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
     743                 :            :    so that longjmp/siglongjmp can potentially "return" to an entirely
     744                 :            :    different function.  */
     745                 :            : 
     746                 :            : class setjmp_svalue : public svalue
     747                 :            : {
     748                 :            : public:
     749                 :       1380 :   setjmp_svalue (const setjmp_record &setjmp_record,
     750                 :            :                  tree type)
     751                 :       1380 :   : svalue (type), m_setjmp_record (setjmp_record)
     752                 :            :   {}
     753                 :            : 
     754                 :            :   bool compare_fields (const setjmp_svalue &other) const;
     755                 :            : 
     756                 :       1369 :   svalue *clone () const FINAL OVERRIDE
     757                 :       1369 :   { return new setjmp_svalue (m_setjmp_record, get_type ()); }
     758                 :            : 
     759                 :       1170 :   enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_SETJMP; }
     760                 :            : 
     761                 :            :   void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
     762                 :            : 
     763                 :         10 :   setjmp_svalue *dyn_cast_setjmp_svalue () FINAL OVERRIDE { return this; }
     764                 :            : 
     765                 :            :   int get_enode_index () const;
     766                 :            : 
     767                 :         10 :   const setjmp_record &get_setjmp_record () const { return m_setjmp_record; }
     768                 :            : 
     769                 :            :  private:
     770                 :            :   void print_details (const region_model &model,
     771                 :            :                       svalue_id this_sid,
     772                 :            :                       pretty_printer *pp) const
     773                 :            :     FINAL OVERRIDE;
     774                 :            : 
     775                 :            :   setjmp_record m_setjmp_record;
     776                 :            : };
     777                 :            : 
     778                 :            : /* An enum for discriminating between the different concrete subclasses
     779                 :            :    of region.  */
     780                 :            : 
     781                 :            : enum region_kind
     782                 :            : {
     783                 :            :   RK_PRIMITIVE,
     784                 :            :   RK_STRUCT,
     785                 :            :   RK_UNION,
     786                 :            :   RK_FRAME,
     787                 :            :   RK_GLOBALS,
     788                 :            :   RK_CODE,
     789                 :            :   RK_FUNCTION,
     790                 :            :   RK_ARRAY,
     791                 :            :   RK_STACK,
     792                 :            :   RK_HEAP,
     793                 :            :   RK_ROOT,
     794                 :            :   RK_SYMBOLIC
     795                 :            : };
     796                 :            : 
     797                 :            : extern const char *region_kind_to_str (enum region_kind);
     798                 :            : 
     799                 :            : /* Region and its subclasses.
     800                 :            : 
     801                 :            :    The class hierarchy looks like this (using indentation to show
     802                 :            :    inheritance, and with region_kinds shown for the concrete subclasses):
     803                 :            : 
     804                 :            :    region
     805                 :            :      primitive_region (RK_PRIMITIVE)
     806                 :            :      map_region
     807                 :            :        struct_or_union_region
     808                 :            :          struct_region (RK_STRUCT)
     809                 :            :          union_region (RK_UNION)
     810                 :            :        scope_region
     811                 :            :          frame_region (RK_FRAME)
     812                 :            :          globals_region (RK_GLOBALS)
     813                 :            :        code_region (RK_CODE)
     814                 :            :        function_region (RK_FUNCTION)
     815                 :            :      array_region (RK_ARRAY)
     816                 :            :      stack_region (RK_STACK)
     817                 :            :      heap_region (RK_HEAP)
     818                 :            :      root_region (RK_ROOT)
     819                 :            :      label_region (RK_FUNCTION)
     820                 :            :      symbolic_region (RK_SYMBOLIC).  */
     821                 :            : 
     822                 :            : /* Abstract base class representing a chunk of memory.
     823                 :            : 
     824                 :            :    Regions form a tree-like hierarchy, with a root region at the base,
     825                 :            :    with memory space regions within it, representing the stack and
     826                 :            :    globals, with frames within the stack, and regions for variables
     827                 :            :    within the frames and the "globals" region.  Regions for structs
     828                 :            :    can have subregions for fields.
     829                 :            : 
     830                 :            :    A region can optionally have a value, or inherit its value from
     831                 :            :    the first ancestor with a value.  For example, the stack region
     832                 :            :    has a "uninitialized" poison value which is inherited by all
     833                 :            :    descendent regions that don't themselves have a value.  */
     834                 :            : 
     835                 :            : class region
     836                 :            : {
     837                 :            : public:
     838                 :            :   virtual ~region () {}
     839                 :            : 
     840                 :            :   bool operator== (const region &other) const;
     841                 :          2 :   bool operator!= (const region &other) const { return !(*this == other); }
     842                 :            : 
     843                 :            :   virtual region *clone () const = 0;
     844                 :            : 
     845                 :            :   virtual enum region_kind get_kind () const = 0;
     846                 :     813435 :   virtual map_region *dyn_cast_map_region () { return NULL; }
     847                 :     351712 :   virtual array_region *dyn_cast_array_region () { return NULL; }
     848                 :          0 :   virtual symbolic_region *dyn_cast_symbolic_region () { return NULL; }
     849                 :        319 :   virtual const symbolic_region *dyn_cast_symbolic_region () const { return NULL; }
     850                 :            : 
     851                 :    1411580 :   region_id get_parent () const { return m_parent_rid; }
     852                 :            :   region *get_parent_region (const region_model &model) const;
     853                 :            : 
     854                 :            :   void set_value (region_model &model, region_id this_rid, svalue_id rhs_sid,
     855                 :            :                   region_model_context *ctxt);
     856                 :            :   svalue_id get_value (region_model &model, bool non_null,
     857                 :            :                        region_model_context *ctxt);
     858                 :    3396468 :   svalue_id get_value_direct () const { return m_sval_id; }
     859                 :            : 
     860                 :            :   svalue_id get_inherited_child_sid (region *child,
     861                 :            :                                      region_model &model,
     862                 :            :                                      region_model_context *ctxt);
     863                 :            : 
     864                 :    2499650 :   tree get_type () const { return m_type; }
     865                 :            : 
     866                 :            :   hashval_t hash () const;
     867                 :            : 
     868                 :            :   void print (const region_model &model,
     869                 :            :               region_id this_rid,
     870                 :            :               pretty_printer *pp) const;
     871                 :            : 
     872                 :            :   virtual void dump_dot_to_pp (const region_model &model,
     873                 :            :                                region_id this_rid,
     874                 :            :                                pretty_printer *pp) const;
     875                 :            : 
     876                 :            :   void dump_to_pp (const region_model &model,
     877                 :            :                    region_id this_rid,
     878                 :            :                    pretty_printer *pp,
     879                 :            :                    const char *prefix,
     880                 :            :                    bool is_last_child) const;
     881                 :            :   virtual void dump_child_label (const region_model &model,
     882                 :            :                                  region_id this_rid,
     883                 :            :                                  region_id child_rid,
     884                 :            :                                  pretty_printer *pp) const;
     885                 :            : 
     886                 :            :   void remap_svalue_ids (const svalue_id_map &map);
     887                 :            :   virtual void remap_region_ids (const region_id_map &map);
     888                 :            : 
     889                 :            :   virtual void walk_for_canonicalization (canonicalization *c) const = 0;
     890                 :            : 
     891                 :            :   void add_view (region_id view_rid, region_model *model);
     892                 :            :   region_id get_view (tree type, region_model *model) const;
     893                 :     355132 :   bool is_view_p () const { return m_is_view; }
     894                 :            : 
     895                 :            :   virtual void validate (const region_model &model) const;
     896                 :            : 
     897                 :            :   bool non_null_p (const region_model &model) const;
     898                 :            : 
     899                 :            :  protected:
     900                 :            :   region (region_id parent_rid, svalue_id sval_id, tree type);
     901                 :            :   region (const region &other);
     902                 :            : 
     903                 :            :   virtual void add_to_hash (inchash::hash &hstate) const;
     904                 :            :   virtual void print_fields (const region_model &model,
     905                 :            :                              region_id this_rid,
     906                 :            :                              pretty_printer *pp) const;
     907                 :            : 
     908                 :            :  private:
     909                 :            :   void become_active_view (region_model &model, region_id this_rid);
     910                 :            :   void deactivate_any_active_view (region_model &model);
     911                 :            :   void deactivate_view (region_model &model, region_id this_view_rid);
     912                 :            : 
     913                 :            :   region_id m_parent_rid;
     914                 :            :   svalue_id m_sval_id;
     915                 :            :   tree m_type;
     916                 :            :   /* Child regions that are "views" (one per type).  */
     917                 :            :   auto_vec<region_id> m_view_rids;
     918                 :            : 
     919                 :            :   bool m_is_view;
     920                 :            :   region_id m_active_view_rid;
     921                 :            : };
     922                 :            : 
     923                 :            : } // namespace ana
     924                 :            : 
     925                 :            : template <>
     926                 :            : template <>
     927                 :            : inline bool
     928                 :            : is_a_helper <region *>::test (region *)
     929                 :            : {
     930                 :            :   return true;
     931                 :            : }
     932                 :            : 
     933                 :            : namespace ana {
     934                 :            : 
     935                 :            : /* Concrete region subclass for storing "primitive" types (integral types,
     936                 :            :    pointers, etc).  */
     937                 :            : 
     938                 :    1128550 : class primitive_region : public region
     939                 :            : {
     940                 :            : public:
     941                 :     816424 :   primitive_region (region_id parent_rid, tree type)
     942                 :     816422 :   : region (parent_rid, svalue_id::null (), type)
     943                 :            :   {}
     944                 :            : 
     945                 :            :   region *clone () const FINAL OVERRIDE;
     946                 :            : 
     947                 :    1954220 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_PRIMITIVE; }
     948                 :            : 
     949                 :            :   void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
     950                 :            : };
     951                 :            : 
     952                 :            : /* A region that has children identified by tree keys.
     953                 :            :    For example a stack frame has subregions per local, and a region
     954                 :            :    for a struct has subregions per field.  */
     955                 :            : 
     956                 :            : class map_region : public region
     957                 :            : {
     958                 :            : public:
     959                 :            :   typedef ordered_hash_map<tree, region_id> map_t;
     960                 :            :   typedef map_t::iterator iterator_t;
     961                 :            : 
     962                 :     729361 :   map_region (region_id parent_rid, tree type)
     963                 :     729361 :   : region (parent_rid, svalue_id::null (), type)
     964                 :     729361 :   {}
     965                 :            :   map_region (const map_region &other);
     966                 :            : 
     967                 :    1124800 :   map_region *dyn_cast_map_region () FINAL OVERRIDE { return this; }
     968                 :            : 
     969                 :            :   void dump_dot_to_pp (const region_model &model,
     970                 :            :                        region_id this_rid,
     971                 :            :                        pretty_printer *pp) const
     972                 :            :     FINAL OVERRIDE;
     973                 :            : 
     974                 :            :   void dump_child_label (const region_model &model,
     975                 :            :                          region_id this_rid,
     976                 :            :                          region_id child_rid,
     977                 :            :                          pretty_printer *pp) const
     978                 :            :     FINAL OVERRIDE;
     979                 :            : 
     980                 :            :   region_id get_or_create (region_model *model,
     981                 :            :                            region_id this_rid,
     982                 :            :                            tree expr, tree type,
     983                 :            :                            region_model_context *ctxt);
     984                 :            :   void unbind (tree expr);
     985                 :            :   region_id *get (tree expr);
     986                 :            : 
     987                 :            :   void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
     988                 :            : 
     989                 :            :   tree get_tree_for_child_region (region_id child_rid) const;
     990                 :            : 
     991                 :            :   tree get_tree_for_child_region (region *child,
     992                 :            :                                   const region_model &model) const;
     993                 :            : 
     994                 :            :   static bool can_merge_p (const map_region *map_region_a,
     995                 :            :                            const map_region *map_region_b,
     996                 :            :                            map_region *merged_map_region,
     997                 :            :                            region_id merged_rid,
     998                 :            :                            model_merger *merger);
     999                 :            : 
    1000                 :            :   void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
    1001                 :            : 
    1002                 :            :   virtual bool valid_key_p (tree key) const = 0;
    1003                 :            : 
    1004                 :            :   svalue_id get_value_by_name (tree identifier,
    1005                 :            :                                const region_model &model) const;
    1006                 :            : 
    1007                 :      28071 :   iterator_t begin () { return m_map.begin (); }
    1008                 :     334521 :   iterator_t end () { return m_map.end (); }
    1009                 :            :   size_t elements () const { return m_map.elements (); }
    1010                 :            : 
    1011                 :            :  protected:
    1012                 :            :   bool compare_fields (const map_region &other) const;
    1013                 :            :   void add_to_hash (inchash::hash &hstate) const OVERRIDE;
    1014                 :            :   void print_fields (const region_model &model,
    1015                 :            :                      region_id this_rid,
    1016                 :            :                      pretty_printer *pp) const
    1017                 :            :     OVERRIDE;
    1018                 :            :   void validate (const region_model &model) const FINAL OVERRIDE;
    1019                 :            : 
    1020                 :            :  private:
    1021                 :            :   /* Mapping from tree to child region.  */
    1022                 :            :   map_t m_map;
    1023                 :            : };
    1024                 :            : 
    1025                 :            : } // namespace ana
    1026                 :            : 
    1027                 :            : template <>
    1028                 :            : template <>
    1029                 :            : inline bool
    1030                 :     751064 : is_a_helper <map_region *>::test (region *reg)
    1031                 :            : {
    1032                 :     751064 :   return (reg->dyn_cast_map_region () != NULL);
    1033                 :            : }
    1034                 :            : 
    1035                 :            : namespace ana {
    1036                 :            : 
    1037                 :            : /* Abstract subclass representing a region with fields
    1038                 :            :    (either a struct or a union).  */
    1039                 :            : 
    1040                 :     100280 : class struct_or_union_region : public map_region
    1041                 :            : {
    1042                 :            : public:
    1043                 :            :   bool valid_key_p (tree key) const FINAL OVERRIDE;
    1044                 :            : 
    1045                 :            :  protected:
    1046                 :       8930 :   struct_or_union_region (region_id parent_rid, tree type)
    1047                 :       8930 :   : map_region (parent_rid, type)
    1048                 :            :   {}
    1049                 :            : 
    1050                 :            :   bool compare_fields (const struct_or_union_region &other) const;
    1051                 :            : };
    1052                 :            : 
    1053                 :            : } // namespace ana
    1054                 :            : 
    1055                 :            : template <>
    1056                 :            : template <>
    1057                 :            : inline bool
    1058                 :       3083 : is_a_helper <struct_or_union_region *>::test (region *reg)
    1059                 :            : {
    1060                 :       3083 :   return (reg->get_kind () == RK_STRUCT
    1061                 :       3083 :           || reg->get_kind () == RK_UNION);
    1062                 :            : }
    1063                 :            : 
    1064                 :            : namespace ana {
    1065                 :            : 
    1066                 :            : /* Concrete region subclass.  A map_region representing a struct, using
    1067                 :            :    FIELD_DECLs for its keys.  */
    1068                 :            : 
    1069                 :      99805 : class struct_region : public struct_or_union_region
    1070                 :            : {
    1071                 :            : public:
    1072                 :       8894 :   struct_region (region_id parent_rid, tree type)
    1073                 :       8894 :   : struct_or_union_region (parent_rid, type)
    1074                 :            :   {
    1075                 :       8894 :     gcc_assert (TREE_CODE (type) == RECORD_TYPE);
    1076                 :       8894 :   }
    1077                 :            : 
    1078                 :            :   region *clone () const FINAL OVERRIDE;
    1079                 :            : 
    1080                 :      56309 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_STRUCT; }
    1081                 :            : 
    1082                 :            :   bool compare_fields (const struct_region &other) const;
    1083                 :            : };
    1084                 :            : 
    1085                 :            : } // namespace ana
    1086                 :            : 
    1087                 :            : template <>
    1088                 :            : template <>
    1089                 :            : inline bool
    1090                 :            : is_a_helper <struct_region *>::test (region *reg)
    1091                 :            : {
    1092                 :            :   return reg->get_kind () == RK_STRUCT;
    1093                 :            : }
    1094                 :            : 
    1095                 :            : namespace ana {
    1096                 :            : 
    1097                 :            : /* Concrete region subclass.  A map_region representing a union, using
    1098                 :            :    FIELD_DECLs for its keys.  */
    1099                 :            : 
    1100                 :        475 : class union_region : public struct_or_union_region
    1101                 :            : {
    1102                 :            : public:
    1103                 :         36 :   union_region (region_id parent_rid, tree type)
    1104                 :         36 :   : struct_or_union_region (parent_rid, type)
    1105                 :            :   {
    1106                 :         36 :     gcc_assert (TREE_CODE (type) == UNION_TYPE);
    1107                 :         36 :   }
    1108                 :            : 
    1109                 :            :   region *clone () const FINAL OVERRIDE;
    1110                 :            : 
    1111                 :        325 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_UNION; }
    1112                 :            : 
    1113                 :            :   bool compare_fields (const union_region &other) const;
    1114                 :            : };
    1115                 :            : 
    1116                 :            : } // namespace ana
    1117                 :            : 
    1118                 :            : template <>
    1119                 :            : template <>
    1120                 :            : inline bool
    1121                 :            : is_a_helper <union_region *>::test (region *reg)
    1122                 :            : {
    1123                 :            :   return reg->get_kind () == RK_UNION;
    1124                 :            : }
    1125                 :            : 
    1126                 :            : namespace ana {
    1127                 :            : 
    1128                 :            : /* Abstract map_region subclass for accessing decls, used as a base class
    1129                 :            :    for function frames and for the globals region.  */
    1130                 :            : 
    1131                 :            : class scope_region : public map_region
    1132                 :            : {
    1133                 :            :  public:
    1134                 :            : 
    1135                 :            :  protected:
    1136                 :     189120 :   scope_region (region_id parent_rid)
    1137                 :     189120 :   : map_region (parent_rid, NULL_TREE)
    1138                 :            :   {}
    1139                 :            : 
    1140                 :     249135 :   scope_region (const scope_region &other)
    1141                 :     249135 :   : map_region (other)
    1142                 :            :   {
    1143                 :            :   }
    1144                 :            : 
    1145                 :            :   bool compare_fields (const scope_region &other) const;
    1146                 :            : };
    1147                 :            : 
    1148                 :            : /* Concrete region subclass, representing a function frame on the stack,
    1149                 :            :    to contain the locals.  */
    1150                 :            : 
    1151                 :            : class frame_region : public scope_region
    1152                 :            : {
    1153                 :            : public:
    1154                 :     183398 :   frame_region (region_id parent_rid, function *fun, int depth)
    1155                 :     183398 :   : scope_region (parent_rid), m_fun (fun), m_depth (depth)
    1156                 :            :   {}
    1157                 :            : 
    1158                 :     222206 :   frame_region (const frame_region &other)
    1159                 :     222206 :   : scope_region (other), m_fun (other.m_fun), m_depth (other.m_depth)
    1160                 :            :   {
    1161                 :            :   }
    1162                 :            : 
    1163                 :            :   /* region vfuncs.  */
    1164                 :            :   region *clone () const FINAL OVERRIDE;
    1165                 :    1164400 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_FRAME; }
    1166                 :            :   void print_fields (const region_model &model,
    1167                 :            :                      region_id this_rid,
    1168                 :            :                      pretty_printer *pp) const
    1169                 :            :     FINAL OVERRIDE;
    1170                 :            :   void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
    1171                 :            : 
    1172                 :            :   /* map_region vfuncs.  */
    1173                 :            :   bool valid_key_p (tree key) const FINAL OVERRIDE;
    1174                 :            : 
    1175                 :            :   /* Accessors.  */
    1176                 :     182885 :   function *get_function () const { return m_fun; }
    1177                 :     192119 :   int get_depth () const { return m_depth; }
    1178                 :            : 
    1179                 :            :   bool compare_fields (const frame_region &other) const;
    1180                 :            : 
    1181                 :            :  private:
    1182                 :            :   function *m_fun;
    1183                 :            :   int m_depth;
    1184                 :            : };
    1185                 :            : 
    1186                 :            : } // namespace ana
    1187                 :            : 
    1188                 :            : template <>
    1189                 :            : template <>
    1190                 :            : inline bool
    1191                 :    1078761 : is_a_helper <frame_region *>::test (region *reg)
    1192                 :            : {
    1193                 :    1078761 :   return reg->get_kind () == RK_FRAME;
    1194                 :            : }
    1195                 :            : 
    1196                 :            : namespace ana {
    1197                 :            : 
    1198                 :            : /* Concrete region subclass, to hold global variables (data and bss).  */
    1199                 :            : 
    1200                 :            : class globals_region : public scope_region
    1201                 :            : {
    1202                 :            :  public:
    1203                 :       5722 :   globals_region (region_id parent_rid)
    1204                 :       5722 :   : scope_region (parent_rid)
    1205                 :            :   {}
    1206                 :            : 
    1207                 :      26929 :   globals_region (const globals_region &other)
    1208                 :      26929 :   : scope_region (other)
    1209                 :            :   {
    1210                 :            :   }
    1211                 :            : 
    1212                 :            :   /* region vfuncs.  */
    1213                 :            :   region *clone () const FINAL OVERRIDE;
    1214                 :      25431 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_GLOBALS; }
    1215                 :            : 
    1216                 :            :   /* map_region vfuncs.  */
    1217                 :            :   bool valid_key_p (tree key) const FINAL OVERRIDE;
    1218                 :            : 
    1219                 :            :   bool compare_fields (const globals_region &other) const;
    1220                 :            : };
    1221                 :            : 
    1222                 :            : } // namespace ana
    1223                 :            : 
    1224                 :            : template <>
    1225                 :            : template <>
    1226                 :            : inline bool
    1227                 :      16071 : is_a_helper <globals_region *>::test (region *reg)
    1228                 :            : {
    1229                 :      16071 :   return reg->get_kind () == RK_GLOBALS;
    1230                 :            : }
    1231                 :            : 
    1232                 :            : namespace ana {
    1233                 :            : 
    1234                 :            : /* Concrete region subclass.  A map_region representing the code, using
    1235                 :            :    FUNCTION_DECLs for its keys.  */
    1236                 :            : 
    1237                 :            : class code_region : public map_region
    1238                 :            : {
    1239                 :            : public:
    1240                 :     160516 :   code_region (region_id parent_rid)
    1241                 :     160516 :   : map_region (parent_rid, NULL_TREE)
    1242                 :            :   {}
    1243                 :     116788 :   code_region (const code_region &other)
    1244                 :     116788 :   : map_region (other)
    1245                 :            :   {}
    1246                 :            : 
    1247                 :            :   /* region vfuncs.  */
    1248                 :            :   region *clone () const FINAL OVERRIDE;
    1249                 :     594066 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_CODE; }
    1250                 :            : 
    1251                 :            :   /* map_region vfunc.  */
    1252                 :            :   bool valid_key_p (tree key) const FINAL OVERRIDE;
    1253                 :            : 
    1254                 :            :   region_id get_element (region_model *model,
    1255                 :            :                          region_id this_rid,
    1256                 :            :                          svalue_id index_sid,
    1257                 :            :                          region_model_context *ctxt);
    1258                 :            : 
    1259                 :            :   bool compare_fields (const code_region &other) const;
    1260                 :            : };
    1261                 :            : 
    1262                 :            : } // namespace ana
    1263                 :            : 
    1264                 :            : template <>
    1265                 :            : template <>
    1266                 :            : inline bool
    1267                 :     553124 : is_a_helper <code_region *>::test (region *reg)
    1268                 :            : {
    1269                 :     553124 :   return reg->get_kind () == RK_CODE;
    1270                 :            : }
    1271                 :            : 
    1272                 :            : namespace ana {
    1273                 :            : 
    1274                 :            : /* Concrete region subclass.  A map_region representing the code for
    1275                 :            :    a particular function, using LABEL_DECLs for its keys.  */
    1276                 :            : 
    1277                 :            : class function_region : public map_region
    1278                 :            : {
    1279                 :            : public:
    1280                 :     370795 :   function_region (region_id parent_rid, tree type)
    1281                 :     370795 :   : map_region (parent_rid, type)
    1282                 :            :   {
    1283                 :     370795 :     gcc_assert (FUNC_OR_METHOD_TYPE_P (type));
    1284                 :     370795 :   }
    1285                 :     299160 :   function_region (const function_region &other)
    1286                 :     299160 :   : map_region (other)
    1287                 :            :   {}
    1288                 :            : 
    1289                 :            :   /* region vfuncs.  */
    1290                 :            :   region *clone () const FINAL OVERRIDE;
    1291                 :     841358 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_FUNCTION; }
    1292                 :            : 
    1293                 :            :   /* map_region vfunc.  */
    1294                 :            :   bool valid_key_p (tree key) const FINAL OVERRIDE;
    1295                 :            : 
    1296                 :            :   region_id get_element (region_model *model,
    1297                 :            :                          region_id this_rid,
    1298                 :            :                          svalue_id index_sid,
    1299                 :            :                          region_model_context *ctxt);
    1300                 :            : 
    1301                 :            :   bool compare_fields (const function_region &other) const;
    1302                 :            : };
    1303                 :            : 
    1304                 :            : } // namespace ana
    1305                 :            : 
    1306                 :            : template <>
    1307                 :            : template <>
    1308                 :            : inline bool
    1309                 :         10 : is_a_helper <function_region *>::test (region *reg)
    1310                 :            : {
    1311                 :         10 :   return reg->get_kind () == RK_FUNCTION;
    1312                 :            : }
    1313                 :            : 
    1314                 :            : namespace ana {
    1315                 :            : 
    1316                 :            : /* Concrete region subclass representing an array (or an array-like view
    1317                 :            :    of a parent region of memory.
    1318                 :            :    This can't be a map_region as we can't use trees as the keys: there's
    1319                 :            :    no guarantee about the uniqueness of an INTEGER_CST.  */
    1320                 :            : 
    1321                 :            : class array_region : public region
    1322                 :            : {
    1323                 :            : public:
    1324                 :            : #if 0
    1325                 :            :   wide_int m_test;
    1326                 :            : 
    1327                 :            :   typedef wide_int key_t;
    1328                 :            :   typedef int_hash <wide_int, -1, -2> hash_t;
    1329                 :            :   typedef ordered_hash_map<hash_t, region_id> map_t;
    1330                 :            : #else
    1331                 :            :   typedef int key_t;
    1332                 :            :   typedef int_hash <int, -1, -2> int_hash_t;
    1333                 :            :   typedef ordered_hash_map<int_hash_t, region_id> map_t;
    1334                 :            : #endif
    1335                 :            :   typedef map_t::iterator iterator_t;
    1336                 :            : 
    1337                 :      23192 :   array_region (region_id parent_rid, tree type)
    1338                 :      23192 :   : region (parent_rid, svalue_id::null (), type)
    1339                 :            :   {
    1340                 :      23192 :     gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
    1341                 :      23192 :   }
    1342                 :            :   array_region (const array_region &other);
    1343                 :            : 
    1344                 :            :   void dump_dot_to_pp (const region_model &model,
    1345                 :            :                        region_id this_rid,
    1346                 :            :                        pretty_printer *pp) const
    1347                 :            :     FINAL OVERRIDE;
    1348                 :            : 
    1349                 :            :   void dump_child_label (const region_model &model,
    1350                 :            :                          region_id this_rid,
    1351                 :            :                          region_id child_rid,
    1352                 :            :                          pretty_printer *pp) const
    1353                 :            :     FINAL OVERRIDE;
    1354                 :            : 
    1355                 :            :   /* region vfuncs.  */
    1356                 :            :   region *clone () const FINAL OVERRIDE;
    1357                 :     106271 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_ARRAY; }
    1358                 :       2327 :   array_region *dyn_cast_array_region () { return this; }
    1359                 :            : 
    1360                 :            :   region_id get_element (region_model *model,
    1361                 :            :                          region_id this_rid,
    1362                 :            :                          svalue_id index_sid,
    1363                 :            :                          region_model_context *ctxt);
    1364                 :            : 
    1365                 :            :   bool compare_fields (const array_region &other) const;
    1366                 :            : 
    1367                 :            :   static bool can_merge_p (const array_region *array_region_a,
    1368                 :            :                            const array_region *array_region_b,
    1369                 :            :                            array_region *merged_array_region,
    1370                 :            :                            region_id merged_rid,
    1371                 :            :                            model_merger *merger);
    1372                 :            : 
    1373                 :            :   void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
    1374                 :            : 
    1375                 :            :   iterator_t begin () { return m_map.begin (); }
    1376                 :            :   iterator_t end () { return m_map.end (); }
    1377                 :            :   size_t elements () const { return m_map.elements (); }
    1378                 :            : 
    1379                 :            :   region_id get_or_create (region_model *model,
    1380                 :            :                            region_id this_rid,
    1381                 :            :                            key_t key, tree type,
    1382                 :            :                            region_model_context *ctxt);
    1383                 :            : //  void unbind (int expr);
    1384                 :            :   region_id *get (key_t key);
    1385                 :            : 
    1386                 :            :   void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
    1387                 :            : 
    1388                 :            :   bool get_key_for_child_region (region_id child_rid,
    1389                 :            :                                  key_t *out) const;
    1390                 :            : 
    1391                 :            : #if 0
    1392                 :            :   bool get_key_for_child_region (region *child,
    1393                 :            :                                  const region_model &model,
    1394                 :            :                                  key_t *out) const;
    1395                 :            : #endif
    1396                 :            : 
    1397                 :            :   void add_to_hash (inchash::hash &hstate) const OVERRIDE;
    1398                 :            :   void print_fields (const region_model &model,
    1399                 :            :                      region_id this_rid,
    1400                 :            :                      pretty_printer *pp) const
    1401                 :            :     OVERRIDE;
    1402                 :            :   void validate (const region_model &model) const FINAL OVERRIDE;
    1403                 :            : 
    1404                 :            :   static key_t key_from_constant (tree cst);
    1405                 :            :   tree constant_from_key (key_t key);
    1406                 :            : 
    1407                 :            :  private:
    1408                 :            :   static int key_cmp (const void *, const void *);
    1409                 :            : 
    1410                 :            :   /* Mapping from tree to child region.  */
    1411                 :            :   map_t m_map;
    1412                 :            : };
    1413                 :            : 
    1414                 :            : } // namespace ana
    1415                 :            : 
    1416                 :            : template <>
    1417                 :            : template <>
    1418                 :            : inline bool
    1419                 :        600 : is_a_helper <array_region *>::test (region *reg)
    1420                 :            : {
    1421                 :        600 :   return reg->get_kind () == RK_ARRAY;
    1422                 :            : }
    1423                 :            : 
    1424                 :            : namespace ana {
    1425                 :            : 
    1426                 :            : /* Concrete region subclass representing a stack, containing all stack
    1427                 :            :    frames, and implicitly providing a POISON_KIND_UNINIT value to all
    1428                 :            :    child regions by default.  */
    1429                 :            : 
    1430                 :            : class stack_region : public region
    1431                 :            : {
    1432                 :            : public:
    1433                 :     174755 :   stack_region (region_id parent_rid, svalue_id sval_id)
    1434                 :     174755 :   : region (parent_rid, sval_id, NULL_TREE)
    1435                 :            :   {}
    1436                 :            : 
    1437                 :            :   stack_region (const stack_region &other);
    1438                 :            : 
    1439                 :            :   bool compare_fields (const stack_region &other) const;
    1440                 :            : 
    1441                 :            :   region *clone () const FINAL OVERRIDE;
    1442                 :            : 
    1443                 :    2076200 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_STACK; }
    1444                 :            : 
    1445                 :            :   void dump_child_label (const region_model &model,
    1446                 :            :                          region_id this_rid,
    1447                 :            :                          region_id child_rid,
    1448                 :            :                          pretty_printer *pp) const
    1449                 :            :     FINAL OVERRIDE;
    1450                 :            : 
    1451                 :            :   void push_frame (region_id frame_rid);
    1452                 :            :   region_id get_current_frame_id () const;
    1453                 :            :   svalue_id pop_frame (region_model *model, bool purge, purge_stats *stats,
    1454                 :            :                        region_model_context *ctxt);
    1455                 :            : 
    1456                 :            :   void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
    1457                 :            : 
    1458                 :    1983360 :   unsigned get_num_frames () const { return m_frame_rids.length (); }
    1459                 :     512108 :   region_id get_frame_rid (unsigned i) const { return m_frame_rids[i]; }
    1460                 :            : 
    1461                 :            :   static bool can_merge_p (const stack_region *stack_region_a,
    1462                 :            :                            const stack_region *stack_region_b,
    1463                 :            :                            model_merger *merger);
    1464                 :            : 
    1465                 :            :   void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
    1466                 :            : 
    1467                 :            :   svalue_id get_value_by_name (tree identifier,
    1468                 :            :                                const region_model &model) const;
    1469                 :            : 
    1470                 :            :   void validate (const region_model &model) const FINAL OVERRIDE;
    1471                 :            : 
    1472                 :            :  private:
    1473                 :            :   void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
    1474                 :            :   void print_fields (const region_model &model,
    1475                 :            :                      region_id this_rid,
    1476                 :            :                      pretty_printer *pp) const
    1477                 :            :     FINAL OVERRIDE;
    1478                 :            : 
    1479                 :            :   auto_vec<region_id> m_frame_rids;
    1480                 :            : };
    1481                 :            : 
    1482                 :            : } // namespace ana
    1483                 :            : 
    1484                 :            : template <>
    1485                 :            : template <>
    1486                 :            : inline bool
    1487                 :    2013300 : is_a_helper <stack_region *>::test (region *reg)
    1488                 :            : {
    1489                 :    2013300 :   return reg->get_kind () == RK_STACK;
    1490                 :            : }
    1491                 :            : 
    1492                 :            : namespace ana {
    1493                 :            : 
    1494                 :            : /* Concrete region subclass: a region within which regions can be
    1495                 :            :    dynamically allocated.  */
    1496                 :            : 
    1497                 :            : class heap_region : public region
    1498                 :            : {
    1499                 :            : public:
    1500                 :     135038 :   heap_region (region_id parent_rid, svalue_id sval_id)
    1501                 :     135038 :   : region (parent_rid, sval_id, NULL_TREE)
    1502                 :            :   {}
    1503                 :            :   heap_region (const heap_region &other);
    1504                 :            : 
    1505                 :            :   bool compare_fields (const heap_region &other) const;
    1506                 :            : 
    1507                 :            :   region *clone () const FINAL OVERRIDE;
    1508                 :            : 
    1509                 :     921756 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_HEAP; }
    1510                 :            : 
    1511                 :            :   static bool can_merge_p (const heap_region *heap_a, region_id heap_a_rid,
    1512                 :            :                            const heap_region *heap_b, region_id heap_b_rid,
    1513                 :            :                            heap_region *merged_heap, region_id merged_heap_rid,
    1514                 :            :                            model_merger *merger);
    1515                 :            : 
    1516                 :            :   void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
    1517                 :            : 
    1518                 :            : };
    1519                 :            : 
    1520                 :            : } // namespace ana
    1521                 :            : 
    1522                 :            : template <>
    1523                 :            : template <>
    1524                 :            : inline bool
    1525                 :     290294 : is_a_helper <heap_region *>::test (region *reg)
    1526                 :            : {
    1527                 :     290294 :   return reg->get_kind () == RK_HEAP;
    1528                 :            : }
    1529                 :            : 
    1530                 :            : namespace ana {
    1531                 :            : 
    1532                 :            : /* Concrete region subclass.  The root region, containing all regions
    1533                 :            :    (either directly, or as descendents).
    1534                 :            :    Unique within a region_model.  */
    1535                 :            : 
    1536                 :            : class root_region : public region
    1537                 :            : {
    1538                 :            : public:
    1539                 :            :   root_region ();
    1540                 :            :   root_region (const root_region &other);
    1541                 :            : 
    1542                 :            :   bool compare_fields (const root_region &other) const;
    1543                 :            : 
    1544                 :            :   region *clone () const FINAL OVERRIDE;
    1545                 :            : 
    1546                 :    3305420 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_ROOT; }
    1547                 :            : 
    1548                 :            :   void dump_child_label (const region_model &model,
    1549                 :            :                          region_id this_rid,
    1550                 :            :                          region_id child_rid,
    1551                 :            :                          pretty_printer *pp) const
    1552                 :            :     FINAL OVERRIDE;
    1553                 :            : 
    1554                 :            :   region_id push_frame (region_model *model, function *fun,
    1555                 :            :                         vec<svalue_id> *arg_sids,
    1556                 :            :                         region_model_context *ctxt);
    1557                 :            :   region_id get_current_frame_id (const region_model &model) const;
    1558                 :            :   svalue_id pop_frame (region_model *model, bool purge, purge_stats *stats,
    1559                 :            :                        region_model_context *ctxt);
    1560                 :            : 
    1561                 :            :   region_id ensure_stack_region (region_model *model);
    1562                 :     365292 :   region_id get_stack_region_id () const { return m_stack_rid; }
    1563                 :            :   stack_region *get_stack_region (const region_model *model) const;
    1564                 :            : 
    1565                 :            :   region_id ensure_globals_region (region_model *model);
    1566                 :     355697 :   region_id get_globals_region_id () const { return m_globals_rid; }
    1567                 :            :   globals_region *get_globals_region (const region_model *model) const;
    1568                 :            : 
    1569                 :            :   region_id ensure_code_region (region_model *model);
    1570                 :            :   code_region *get_code_region (const region_model *model) const;
    1571                 :            : 
    1572                 :            :   region_id ensure_heap_region (region_model *model);
    1573                 :            :   heap_region *get_heap_region (const region_model *model) const;
    1574                 :            : 
    1575                 :            :   void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
    1576                 :            : 
    1577                 :            :   static bool can_merge_p (const root_region *root_region_a,
    1578                 :            :                            const root_region *root_region_b,
    1579                 :            :                            root_region *merged_root_region,
    1580                 :            :                            model_merger *merger);
    1581                 :            : 
    1582                 :            :   void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
    1583                 :            : 
    1584                 :            :   svalue_id get_value_by_name (tree identifier,
    1585                 :            :                                const region_model &model) const;
    1586                 :            : 
    1587                 :            :   void validate (const region_model &model) const FINAL OVERRIDE;
    1588                 :            : 
    1589                 :            : private:
    1590                 :            :   void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
    1591                 :            :   void print_fields (const region_model &model,
    1592                 :            :                      region_id this_rid,
    1593                 :            :                      pretty_printer *pp) const
    1594                 :            :     FINAL OVERRIDE;
    1595                 :            : 
    1596                 :            :   region_id m_stack_rid;
    1597                 :            :   region_id m_globals_rid;
    1598                 :            :   region_id m_code_rid;
    1599                 :            :   region_id m_heap_rid;
    1600                 :            : };
    1601                 :            : 
    1602                 :            : } // namespace ana
    1603                 :            : 
    1604                 :            : template <>
    1605                 :            : template <>
    1606                 :            : inline bool
    1607                 :    3181420 : is_a_helper <root_region *>::test (region *reg)
    1608                 :            : {
    1609                 :    3181420 :   return reg->get_kind () == RK_ROOT;
    1610                 :            : }
    1611                 :            : 
    1612                 :            : namespace ana {
    1613                 :            : 
    1614                 :            : /* Concrete region subclass: a region to use when dereferencing an unknown
    1615                 :            :    pointer.  */
    1616                 :            : 
    1617                 :            : class symbolic_region : public region
    1618                 :            : {
    1619                 :            : public:
    1620                 :     154696 :   symbolic_region (region_id parent_rid, tree type, bool possibly_null)
    1621                 :     154696 :   : region (parent_rid, svalue_id::null (), type),
    1622                 :     154696 :     m_possibly_null (possibly_null)
    1623                 :            :   {}
    1624                 :            :   symbolic_region (const symbolic_region &other);
    1625                 :            : 
    1626                 :        553 :   const symbolic_region *dyn_cast_symbolic_region () const FINAL OVERRIDE
    1627                 :        553 :   { return this; }
    1628                 :         49 :   symbolic_region *dyn_cast_symbolic_region () FINAL OVERRIDE
    1629                 :         49 :   { return this; }
    1630                 :            : 
    1631                 :            :   bool compare_fields (const symbolic_region &other) const;
    1632                 :            : 
    1633                 :            :   region *clone () const FINAL OVERRIDE;
    1634                 :            : 
    1635                 :      50269 :   enum region_kind get_kind () const FINAL OVERRIDE { return RK_SYMBOLIC; }
    1636                 :            : 
    1637                 :            :   void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
    1638                 :            : 
    1639                 :            :   void print_fields (const region_model &model,
    1640                 :            :                      region_id this_rid,
    1641                 :            :                      pretty_printer *pp) const FINAL OVERRIDE;
    1642                 :            : 
    1643                 :            :   bool m_possibly_null;
    1644                 :            : };
    1645                 :            : 
    1646                 :            : /* A region_model encapsulates a representation of the state of memory, with
    1647                 :            :    a tree of regions, along with their associated values.
    1648                 :            :    The representation is graph-like because values can be pointers to
    1649                 :            :    regions.
    1650                 :            :    It also stores a constraint_manager, capturing relationships between
    1651                 :            :    the values.  */
    1652                 :            : 
    1653                 :            : class region_model
    1654                 :            : {
    1655                 :            :  public:
    1656                 :            :   region_model ();
    1657                 :            :   region_model (const region_model &other);
    1658                 :            :   ~region_model ();
    1659                 :            : 
    1660                 :            : #if 0//__cplusplus >= 201103
    1661                 :            :   region_model (region_model &&other);
    1662                 :            : #endif
    1663                 :            : 
    1664                 :            :   region_model &operator= (const region_model &other);
    1665                 :            : 
    1666                 :            :   bool operator== (const region_model &other) const;
    1667                 :         20 :   bool operator!= (const region_model &other) const
    1668                 :            :   {
    1669                 :         20 :     return !(*this == other);
    1670                 :            :   }
    1671                 :            : 
    1672                 :            :   hashval_t hash () const;
    1673                 :            : 
    1674                 :            :   void print (pretty_printer *pp) const;
    1675                 :            : 
    1676                 :            :   void print_svalue (svalue_id sid, pretty_printer *pp) const;
    1677                 :            : 
    1678                 :            :   void dump_dot_to_pp (pretty_printer *pp) const;
    1679                 :            :   void dump_dot_to_file (FILE *fp) const;
    1680                 :            :   void dump_dot (const char *path) const;
    1681                 :            : 
    1682                 :            :   void dump_to_pp (pretty_printer *pp, bool summarize) const;
    1683                 :            :   void dump (FILE *fp, bool summarize) const;
    1684                 :            :   void dump (bool summarize) const;
    1685                 :            : 
    1686                 :            :   void debug () const;
    1687                 :            : 
    1688                 :            :   void validate () const;
    1689                 :            : 
    1690                 :            :   void canonicalize (region_model_context *ctxt);
    1691                 :            :   bool canonicalized_p () const;
    1692                 :            : 
    1693                 :            :   void check_for_poison (tree expr, region_model_context *ctxt);
    1694                 :            :   void on_assignment (const gassign *stmt, region_model_context *ctxt);
    1695                 :            :   bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
    1696                 :            :   void on_call_post (const gcall *stmt,
    1697                 :            :                      bool unknown_side_effects,
    1698                 :            :                      region_model_context *ctxt);
    1699                 :            :   void handle_unrecognized_call (const gcall *call,
    1700                 :            :                                  region_model_context *ctxt);
    1701                 :            :   void on_return (const greturn *stmt, region_model_context *ctxt);
    1702                 :            :   void on_setjmp (const gcall *stmt, const exploded_node *enode,
    1703                 :            :                   region_model_context *ctxt);
    1704                 :            :   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
    1705                 :            :                    int setjmp_stack_depth, region_model_context *ctxt);
    1706                 :            : 
    1707                 :            :   void update_for_phis (const supernode *snode,
    1708                 :            :                         const cfg_superedge *last_cfg_superedge,
    1709                 :            :                         region_model_context *ctxt);
    1710                 :            : 
    1711                 :            :   void handle_phi (const gphi *phi,
    1712                 :            :                    tree lhs, tree rhs, bool is_back_edge,
    1713                 :            :                    region_model_context *ctxt);
    1714                 :            : 
    1715                 :            :   bool maybe_update_for_edge (const superedge &edge,
    1716                 :            :                               const gimple *last_stmt,
    1717                 :            :                               region_model_context *ctxt);
    1718                 :            : 
    1719                 :     476031 :   region_id get_root_rid () const { return m_root_rid; }
    1720                 :            :   root_region *get_root_region () const;
    1721                 :            : 
    1722                 :            :   region_id get_stack_region_id () const;
    1723                 :            :   region_id push_frame (function *fun, vec<svalue_id> *arg_sids,
    1724                 :            :                         region_model_context *ctxt);
    1725                 :            :   region_id get_current_frame_id () const;
    1726                 :            :   function * get_current_function () const;
    1727                 :            :   svalue_id pop_frame (bool purge, purge_stats *stats,
    1728                 :            :                        region_model_context *ctxt);
    1729                 :            :   int get_stack_depth () const;
    1730                 :            :   function *get_function_at_depth (unsigned depth) const;
    1731                 :            : 
    1732                 :            :   region_id get_globals_region_id () const;
    1733                 :            : 
    1734                 :            :   svalue_id add_svalue (svalue *sval);
    1735                 :            :   void replace_svalue (svalue_id sid, svalue *new_sval);
    1736                 :            : 
    1737                 :            :   region_id add_region (region *r);
    1738                 :            : 
    1739                 :            :   region_id add_region_for_type (region_id parent_rid, tree type,
    1740                 :            :                                  region_model_context *ctxt);
    1741                 :            : 
    1742                 :            :   svalue *get_svalue (svalue_id sval_id) const;
    1743                 :            :   region *get_region (region_id rid) const;
    1744                 :            : 
    1745                 :            :   template <typename Subclass>
    1746                 :    9910517 :   Subclass *get_region (region_id rid) const
    1747                 :            :   {
    1748                 :    9910517 :     region *result = get_region (rid);
    1749                 :    7519947 :     if (result)
    1750                 :    7137168 :       gcc_assert (is_a<Subclass *> (result));
    1751                 :    7519947 :     return (Subclass *)result;
    1752                 :            :   }
    1753                 :            : 
    1754                 :            :   region_id get_lvalue (path_var pv, region_model_context *ctxt);
    1755                 :            :   region_id get_lvalue (tree expr, region_model_context *ctxt);
    1756                 :            :   svalue_id get_rvalue (path_var pv, region_model_context *ctxt);
    1757                 :            :   svalue_id get_rvalue (tree expr, region_model_context *ctxt);
    1758                 :            : 
    1759                 :            :   svalue_id get_or_create_ptr_svalue (tree ptr_type, region_id id);
    1760                 :            :   svalue_id get_or_create_constant_svalue (tree cst_expr);
    1761                 :            :   svalue_id get_svalue_for_fndecl (tree ptr_type, tree fndecl,
    1762                 :            :                                    region_model_context *ctxt);
    1763                 :            :   svalue_id get_svalue_for_label (tree ptr_type, tree label,
    1764                 :            :                                   region_model_context *ctxt);
    1765                 :            : 
    1766                 :            :   region_id get_region_for_fndecl (tree fndecl, region_model_context *ctxt);
    1767                 :            :   region_id get_region_for_label (tree label, region_model_context *ctxt);
    1768                 :            : 
    1769                 :            :   svalue_id maybe_cast (tree type, svalue_id sid, region_model_context *ctxt);
    1770                 :            :   svalue_id maybe_cast_1 (tree type, svalue_id sid);
    1771                 :            : 
    1772                 :            :   region_id get_field_region (region_id rid, tree field,
    1773                 :            :                               region_model_context *ctxt);
    1774                 :            : 
    1775                 :            :   region_id deref_rvalue (svalue_id ptr_sid, region_model_context *ctxt);
    1776                 :            :   region_id deref_rvalue (tree ptr, region_model_context *ctxt);
    1777                 :            : 
    1778                 :            :   void set_value (region_id lhs_rid, svalue_id rhs_sid,
    1779                 :            :                   region_model_context *ctxt);
    1780                 :            :   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
    1781                 :            :   svalue_id set_to_new_unknown_value (region_id dst_rid, tree type,
    1782                 :            :                                       region_model_context *ctxt);
    1783                 :            : 
    1784                 :            :   tristate eval_condition (svalue_id lhs,
    1785                 :            :                            enum tree_code op,
    1786                 :            :                            svalue_id rhs) const;
    1787                 :            :   tristate eval_condition_without_cm (svalue_id lhs,
    1788                 :            :                                       enum tree_code op,
    1789                 :            :                                       svalue_id rhs) const;
    1790                 :            :   tristate eval_condition (tree lhs,
    1791                 :            :                            enum tree_code op,
    1792                 :            :                            tree rhs,
    1793                 :            :                            region_model_context *ctxt);
    1794                 :            :   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
    1795                 :            :                        region_model_context *ctxt);
    1796                 :            : 
    1797                 :            :   tree maybe_get_constant (svalue_id sid) const;
    1798                 :            : 
    1799                 :            :   region_id add_new_malloc_region ();
    1800                 :            : 
    1801                 :            :   tree get_representative_tree (svalue_id sid) const;
    1802                 :            :   path_var get_representative_path_var (region_id rid) const;
    1803                 :            :   void get_path_vars_for_svalue (svalue_id sid, vec<path_var> *out) const;
    1804                 :            : 
    1805                 :            :   void purge_unused_svalues (purge_stats *out,
    1806                 :            :                              region_model_context *ctxt,
    1807                 :            :                              svalue_id *known_used_sid = NULL);
    1808                 :            :   void remap_svalue_ids (const svalue_id_map &map);
    1809                 :            :   void remap_region_ids (const region_id_map &map);
    1810                 :            : 
    1811                 :            :   void purge_regions (const region_id_set &set,
    1812                 :            :                       purge_stats *stats,
    1813                 :            :                       logger *logger);
    1814                 :            : 
    1815                 :    5329337 :   unsigned get_num_svalues () const { return m_svalues.length (); }
    1816                 :    9389010 :   unsigned get_num_regions () const { return m_regions.length (); }
    1817                 :            : 
    1818                 :            :   /* For selftests.  */
    1819                 :      14874 :   constraint_manager *get_constraints ()
    1820                 :            :   {
    1821                 :      14874 :     return m_constraints;
    1822                 :            :   }
    1823                 :            : 
    1824                 :            :   void get_descendents (region_id rid, region_id_set *out,
    1825                 :            :                         region_id exclude_rid) const;
    1826                 :            : 
    1827                 :            :   void delete_region_and_descendents (region_id rid,
    1828                 :            :                                       enum poison_kind pkind,
    1829                 :            :                                       purge_stats *stats,
    1830                 :            :                                       logger *logger);
    1831                 :            : 
    1832                 :            :   bool can_merge_with_p (const region_model &other_model,
    1833                 :            :                          region_model *out_model,
    1834                 :            :                          svalue_id_merger_mapping *out) const;
    1835                 :            :   bool can_merge_with_p (const region_model &other_model,
    1836                 :            :                          region_model *out_model) const;
    1837                 :            : 
    1838                 :            :   svalue_id get_value_by_name (const char *name) const;
    1839                 :            : 
    1840                 :            :   svalue_id convert_byte_offset_to_array_index (tree ptr_type,
    1841                 :            :                                                 svalue_id offset_sid);
    1842                 :            : 
    1843                 :            :   region_id get_or_create_mem_ref (tree type,
    1844                 :            :                                    svalue_id ptr_sid,
    1845                 :            :                                    svalue_id offset_sid,
    1846                 :            :                                    region_model_context *ctxt);
    1847                 :            :   region_id get_or_create_pointer_plus_expr (tree type,
    1848                 :            :                                              svalue_id ptr_sid,
    1849                 :            :                                              svalue_id offset_sid,
    1850                 :            :                                              region_model_context *ctxt);
    1851                 :            :   region_id get_or_create_view (region_id raw_rid, tree type,
    1852                 :            :                                 region_model_context *ctxt);
    1853                 :            : 
    1854                 :            :   tree get_fndecl_for_call (const gcall *call,
    1855                 :            :                             region_model_context *ctxt);
    1856                 :            : 
    1857                 :            :  private:
    1858                 :            :   region_id get_lvalue_1 (path_var pv, region_model_context *ctxt);
    1859                 :            :   svalue_id get_rvalue_1 (path_var pv, region_model_context *ctxt);
    1860                 :            : 
    1861                 :            :   region_id make_region_for_unexpected_tree_code (region_model_context *ctxt,
    1862                 :            :                                                   tree t,
    1863                 :            :                                                   const dump_location_t &loc);
    1864                 :            : 
    1865                 :            :   void add_any_constraints_from_ssa_def_stmt (tree lhs,
    1866                 :            :                                               enum tree_code op,
    1867                 :            :                                               tree rhs,
    1868                 :            :                                               region_model_context *ctxt);
    1869                 :            :   void add_any_constraints_from_gassign (enum tree_code op,
    1870                 :            :                                          tree rhs,
    1871                 :            :                                          const gassign *assign,
    1872                 :            :                                          region_model_context *ctxt);
    1873                 :            :   void add_any_constraints_from_gcall (enum tree_code op,
    1874                 :            :                                        tree rhs,
    1875                 :            :                                        const gcall *call,
    1876                 :            :                                        region_model_context *ctxt);
    1877                 :            : 
    1878                 :            :   void update_for_call_superedge (const call_superedge &call_edge,
    1879                 :            :                                   region_model_context *ctxt);
    1880                 :            :   void update_for_return_superedge (const return_superedge &return_edge,
    1881                 :            :                                     region_model_context *ctxt);
    1882                 :            :   void update_for_call_summary (const callgraph_superedge &cg_sedge,
    1883                 :            :                                 region_model_context *ctxt);
    1884                 :            :   bool apply_constraints_for_gcond (const cfg_superedge &edge,
    1885                 :            :                                     const gcond *cond_stmt,
    1886                 :            :                                     region_model_context *ctxt);
    1887                 :            :   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
    1888                 :            :                                       const gswitch *switch_stmt,
    1889                 :            :                                       region_model_context *ctxt);
    1890                 :            : 
    1891                 :            :   void poison_any_pointers_to_bad_regions (const region_id_set &bad_regions,
    1892                 :            :                                            enum poison_kind pkind);
    1893                 :            : 
    1894                 :            :   void dump_summary_of_rep_path_vars (pretty_printer *pp,
    1895                 :            :                                       auto_vec<path_var> *rep_path_vars,
    1896                 :            :                                       bool *is_first);
    1897                 :            : 
    1898                 :            :   auto_delete_vec<svalue> m_svalues;
    1899                 :            :   auto_delete_vec<region> m_regions;
    1900                 :            :   region_id m_root_rid;
    1901                 :            :   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
    1902                 :            : };
    1903                 :            : 
    1904                 :            : /* Some region_model activity could lead to warnings (e.g. attempts to use an
    1905                 :            :    uninitialized value).  This abstract base class encapsulates an interface
    1906                 :            :    for the region model to use when emitting such warnings.
    1907                 :            : 
    1908                 :            :    It also provides an interface for being notified about svalue_ids being
    1909                 :            :    remapped, and being deleted.
    1910                 :            : 
    1911                 :            :    Having this as an abstract base class allows us to support the various
    1912                 :            :    operations needed by program_state in the analyzer within region_model,
    1913                 :            :    whilst keeping them somewhat modularized.  */
    1914                 :            : 
    1915                 :     114902 : class region_model_context
    1916                 :            : {
    1917                 :            :  public:
    1918                 :            :   virtual void warn (pending_diagnostic *d) = 0;
    1919                 :            : 
    1920                 :            :   /* Hook for clients that store svalue_id instances, so that they
    1921                 :            :      can remap their IDs when the underlying region_model renumbers
    1922                 :            :      the IDs.  */
    1923                 :            :   virtual void remap_svalue_ids (const svalue_id_map &map) = 0;
    1924                 :            : 
    1925                 :            : #if 0
    1926                 :            :   /* Return true if if's OK to purge SID when simplifying state.
    1927                 :            :      Subclasses can return false for values that have sm state,
    1928                 :            :      to avoid generating "leak" false positives.  */
    1929                 :            :   virtual bool can_purge_p (svalue_id sid) = 0;
    1930                 :            : #endif
    1931                 :            : 
    1932                 :            :   /* Hook for clients to be notified when a range of SIDs have
    1933                 :            :      been purged, so that they can purge state relating to those
    1934                 :            :      values (and potentially emit warnings about leaks).
    1935                 :            :      All SIDs from FIRST_PURGED_SID numerically upwards are being
    1936                 :            :      purged.
    1937                 :            :      The return values is a count of how many items of data the client
    1938                 :            :      has purged (potentially for use in selftests).
    1939                 :            :      MAP has already been applied to the IDs, but is provided in case
    1940                 :            :      the client needs to figure out the old IDs.  */
    1941                 :            :   virtual int on_svalue_purge (svalue_id first_purged_sid,
    1942                 :            :                                const svalue_id_map &map) = 0;
    1943                 :            : 
    1944                 :            :   virtual logger *get_logger () = 0;
    1945                 :            : 
    1946                 :            :   /* Hook for clients to be notified when CHILD_SID is created
    1947                 :            :      from PARENT_SID, when "inheriting" a value for a region from a
    1948                 :            :      parent region.
    1949                 :            :      This exists so that state machines that inherit state can
    1950                 :            :      propagate the state from parent to child.  */
    1951                 :            :   virtual void on_inherited_svalue (svalue_id parent_sid,
    1952                 :            :                                     svalue_id child_sid) = 0;
    1953                 :            : 
    1954                 :            :   /* Hook for clients to be notified when DST_SID is created
    1955                 :            :      (or reused) as a cast from SRC_SID.
    1956                 :            :      This exists so that state machines can propagate the state
    1957                 :            :      from SRC_SID to DST_SID.  */
    1958                 :            :   virtual void on_cast (svalue_id src_sid,
    1959                 :            :                         svalue_id dst_sid) = 0;
    1960                 :            : 
    1961                 :            :   /* Hook for clients to be notified when the condition
    1962                 :            :      "LHS OP RHS" is added to the region model.
    1963                 :            :      This exists so that state machines can detect tests on edges,
    1964                 :            :      and use them to trigger sm-state transitions (e.g. transitions due
    1965                 :            :      to ptrs becoming known to be NULL or non-NULL, rather than just
    1966                 :            :      "unchecked") */
    1967                 :            :   virtual void on_condition (tree lhs, enum tree_code op, tree rhs) = 0;
    1968                 :            : 
    1969                 :            :   /* Hooks for clients to be notified when an unknown change happens
    1970                 :            :      to SID (in response to a call to an unknown function).  */
    1971                 :            :   virtual void on_unknown_change (svalue_id sid) = 0;
    1972                 :            : 
    1973                 :            :   /* Hooks for clients to be notified when a phi node is handled,
    1974                 :            :      where RHS is the pertinent argument.  */
    1975                 :            :   virtual void on_phi (const gphi *phi, tree rhs) = 0;
    1976                 :            : 
    1977                 :            :   /* Hooks for clients to be notified when the region model doesn't
    1978                 :            :      know how to handle the tree code of T at LOC.  */
    1979                 :            :   virtual void on_unexpected_tree_code (tree t,
    1980                 :            :                                         const dump_location_t &loc) = 0;
    1981                 :            : };
    1982                 :            : 
    1983                 :            : /* A "do nothing" subclass of region_model_context.  */
    1984                 :            : 
    1985                 :       6634 : class noop_region_model_context : public region_model_context
    1986                 :            : {
    1987                 :            : public:
    1988                 :          3 :   void warn (pending_diagnostic *) OVERRIDE {}
    1989                 :          6 :   void remap_svalue_ids (const svalue_id_map &) OVERRIDE {}
    1990                 :          2 :   int on_svalue_purge (svalue_id, const svalue_id_map &) OVERRIDE
    1991                 :            :   {
    1992                 :          2 :     return 0;
    1993                 :            :   }
    1994                 :          4 :   logger *get_logger () OVERRIDE { return NULL; }
    1995                 :        826 :   void on_inherited_svalue (svalue_id parent_sid ATTRIBUTE_UNUSED,
    1996                 :            :                             svalue_id child_sid  ATTRIBUTE_UNUSED)
    1997                 :            :     OVERRIDE
    1998                 :            :   {
    1999                 :        826 :   }
    2000                 :          4 :   void on_cast (svalue_id src_sid ATTRIBUTE_UNUSED,
    2001                 :            :                 svalue_id dst_sid ATTRIBUTE_UNUSED) OVERRIDE
    2002                 :            :   {
    2003                 :          4 :   }
    2004                 :         14 :   void on_condition (tree lhs ATTRIBUTE_UNUSED,
    2005                 :            :                      enum tree_code op ATTRIBUTE_UNUSED,
    2006                 :            :                      tree rhs ATTRIBUTE_UNUSED) OVERRIDE
    2007                 :            :   {
    2008                 :         14 :   }
    2009                 :          0 :   void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) OVERRIDE
    2010                 :            :   {
    2011                 :          0 :   }
    2012                 :          0 :   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
    2013                 :            :                tree rhs ATTRIBUTE_UNUSED) OVERRIDE
    2014                 :            :   {
    2015                 :          0 :   }
    2016                 :          0 :   void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
    2017                 :            : };
    2018                 :            : 
    2019                 :            : /* A subclass of region_model_context for determining if operations fail
    2020                 :            :    e.g. "can we generate a region for the lvalue of EXPR?".  */
    2021                 :            : 
    2022                 :            : class tentative_region_model_context : public noop_region_model_context
    2023                 :            : {
    2024                 :            : public:
    2025                 :       6602 :   tentative_region_model_context () : m_num_unexpected_codes (0) {}
    2026                 :            : 
    2027                 :          6 :   void on_unexpected_tree_code (tree, const dump_location_t &)
    2028                 :            :     FINAL OVERRIDE
    2029                 :            :   {
    2030                 :          6 :     m_num_unexpected_codes++;
    2031                 :          6 :   }
    2032                 :            : 
    2033                 :       6162 :   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
    2034                 :            : 
    2035                 :            : private:
    2036                 :            :   int m_num_unexpected_codes;
    2037                 :            : };
    2038                 :            : 
    2039                 :            : /* A bundle of data for use when attempting to merge two region_model
    2040                 :            :    instances to make a third.  */
    2041                 :            : 
    2042                 :            : struct model_merger
    2043                 :            : {
    2044                 :     173457 :   model_merger (const region_model *model_a,
    2045                 :            :                 const region_model *model_b,
    2046                 :            :                 region_model *merged_model,
    2047                 :            :                 svalue_id_merger_mapping *sid_mapping)
    2048                 :     173457 :   : m_model_a (model_a), m_model_b (model_b),
    2049                 :            :     m_merged_model (merged_model),
    2050                 :     173457 :     m_map_regions_from_a_to_m (model_a->get_num_regions ()),
    2051                 :     173457 :     m_map_regions_from_b_to_m (model_b->get_num_regions ()),
    2052                 :     520371 :     m_sid_mapping (sid_mapping)
    2053                 :            :   {
    2054                 :     173457 :     gcc_assert (sid_mapping);
    2055                 :     173457 :   }
    2056                 :            : 
    2057                 :            :   void dump_to_pp (pretty_printer *pp) const;
    2058                 :            :   void dump (FILE *fp) const;
    2059                 :            :   void dump () const;
    2060                 :            : 
    2061                 :            :   template <typename Subclass>
    2062                 :    1553470 :   Subclass *get_region_a (region_id rid_a) const
    2063                 :            :   {
    2064                 :    1553470 :     return m_model_a->get_region <Subclass> (rid_a);
    2065                 :            :   }
    2066                 :            : 
    2067                 :            :   template <typename Subclass>
    2068                 :    1553470 :   Subclass *get_region_b (region_id rid_b) const
    2069                 :            :   {
    2070                 :    1553470 :     return m_model_b->get_region <Subclass> (rid_b);
    2071                 :            :   }
    2072                 :            : 
    2073                 :            :   bool can_merge_values_p (svalue_id sid_a,
    2074                 :            :                            svalue_id sid_b,
    2075                 :            :                            svalue_id *merged_sid);
    2076                 :            : 
    2077                 :            :   void record_regions (region_id a_rid,
    2078                 :            :                        region_id b_rid,
    2079                 :            :                        region_id merged_rid);
    2080                 :            : 
    2081                 :            :   void record_svalues (svalue_id a_sid,
    2082                 :            :                        svalue_id b_sid,
    2083                 :            :                        svalue_id merged_sid);
    2084                 :            : 
    2085                 :            :   const region_model *m_model_a;
    2086                 :            :   const region_model *m_model_b;
    2087                 :            :   region_model *m_merged_model;
    2088                 :            : 
    2089                 :            :   one_way_region_id_map m_map_regions_from_a_to_m;
    2090                 :            :   one_way_region_id_map m_map_regions_from_b_to_m;
    2091                 :            :   svalue_id_merger_mapping *m_sid_mapping;
    2092                 :            : };
    2093                 :            : 
    2094                 :            : /* A bundle of data that can be optionally generated during merger of two
    2095                 :            :    region_models that describes how svalue_ids in each of the two inputs
    2096                 :            :    are mapped to svalue_ids in the merged output.
    2097                 :            : 
    2098                 :            :    For use when merging sm-states within program_state.  */
    2099                 :            : 
    2100                 :            : struct svalue_id_merger_mapping
    2101                 :            : {
    2102                 :            :   svalue_id_merger_mapping (const region_model &a,
    2103                 :            :                             const region_model &b);
    2104                 :            : 
    2105                 :            :   void dump_to_pp (pretty_printer *pp) const;
    2106                 :            :   void dump (FILE *fp) const;
    2107                 :            :   void dump () const;
    2108                 :            : 
    2109                 :            :   one_way_svalue_id_map m_map_from_a_to_m;
    2110                 :            :   one_way_svalue_id_map m_map_from_b_to_m;
    2111                 :            : };
    2112                 :            : 
    2113                 :            : /* A bundle of data used when canonicalizing a region_model so that the
    2114                 :            :    order of regions and svalues is in a predictable order (thus increasing
    2115                 :            :    the chance of two region_models being equal).
    2116                 :            : 
    2117                 :            :    This object is used to keep track of a recursive traversal across the
    2118                 :            :    svalues and regions within the model, made in a deterministic order,
    2119                 :            :    assigning new ids the first time each region or svalue is
    2120                 :            :    encountered.  */
    2121                 :            : 
    2122                 :      59945 : struct canonicalization
    2123                 :            : {
    2124                 :            :   canonicalization (const region_model &model);
    2125                 :            :   void walk_rid (region_id rid);
    2126                 :            :   void walk_sid (svalue_id sid);
    2127                 :            : 
    2128                 :            :   void dump_to_pp (pretty_printer *pp) const;
    2129                 :            :   void dump (FILE *fp) const;
    2130                 :            :   void dump () const;
    2131                 :            : 
    2132                 :            :   const region_model &m_model;
    2133                 :            :   /* Maps from existing IDs to new IDs.  */
    2134                 :            :   region_id_map m_rid_map;
    2135                 :            :   svalue_id_map m_sid_map;
    2136                 :            :   /* The next IDs to hand out.  */
    2137                 :            :   int m_next_rid_int;
    2138                 :            :   int m_next_sid_int;
    2139                 :            : };
    2140                 :            : 
    2141                 :            : } // namespace ana
    2142                 :            : 
    2143                 :            : namespace inchash
    2144                 :            : {
    2145                 :            :   extern void add (svalue_id sid, hash &hstate);
    2146                 :            :   extern void add (region_id rid, hash &hstate);
    2147                 :            : } // namespace inchash
    2148                 :            : 
    2149                 :            : extern void debug (const region_model &rmodel);
    2150                 :            : 
    2151                 :            : namespace ana {
    2152                 :            : 
    2153                 :            : #if CHECKING_P
    2154                 :            : 
    2155                 :            : namespace selftest {
    2156                 :            : 
    2157                 :            : using namespace ::selftest;
    2158                 :            : 
    2159                 :            : /* An implementation of region_model_context for use in selftests, which
    2160                 :            :    stores any pending_diagnostic instances passed to it.  */
    2161                 :            : 
    2162                 :         58 : class test_region_model_context : public noop_region_model_context
    2163                 :            : {
    2164                 :            : public:
    2165                 :          0 :   void warn (pending_diagnostic *d) FINAL OVERRIDE
    2166                 :            :   {
    2167                 :          0 :     m_diagnostics.safe_push (d);
    2168                 :          0 :   }
    2169                 :            : 
    2170                 :          4 :   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
    2171                 :            : 
    2172                 :          0 :   void on_unexpected_tree_code (tree t, const dump_location_t &)
    2173                 :            :     FINAL OVERRIDE
    2174                 :            :   {
    2175                 :          0 :     internal_error ("unhandled tree code: %qs",
    2176                 :          0 :                     get_tree_code_name (TREE_CODE (t)));
    2177                 :            :   }
    2178                 :            : 
    2179                 :            : private:
    2180                 :            :   /* Implicitly delete any diagnostics in the dtor.  */
    2181                 :            :   auto_delete_vec<pending_diagnostic> m_diagnostics;
    2182                 :            : };
    2183                 :            : 
    2184                 :            : /* Attempt to add the constraint (LHS OP RHS) to MODEL.
    2185                 :            :    Verify that MODEL remains satisfiable.  */
    2186                 :            : 
    2187                 :            : #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
    2188                 :            :   SELFTEST_BEGIN_STMT                                   \
    2189                 :            :     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
    2190                 :            :     ASSERT_TRUE (sat);                                  \
    2191                 :            :   SELFTEST_END_STMT
    2192                 :            : 
    2193                 :            : /* Attempt to add the constraint (LHS OP RHS) to MODEL.
    2194                 :            :    Verify that the result is not satisfiable.  */
    2195                 :            : 
    2196                 :            : #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
    2197                 :            :   SELFTEST_BEGIN_STMT                                   \
    2198                 :            :     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
    2199                 :            :     ASSERT_FALSE (sat);                         \
    2200                 :            :   SELFTEST_END_STMT
    2201                 :            : 
    2202                 :            : /* Implementation detail of the ASSERT_CONDITION_* macros.  */
    2203                 :            : 
    2204                 :            : void assert_condition (const location &loc,
    2205                 :            :                        region_model &model,
    2206                 :            :                        tree lhs, tree_code op, tree rhs,
    2207                 :            :                        tristate expected);
    2208                 :            : 
    2209                 :            : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
    2210                 :            :    as "true".  */
    2211                 :            : 
    2212                 :            : #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
    2213                 :            :   SELFTEST_BEGIN_STMT                                                   \
    2214                 :            :   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
    2215                 :            :                     tristate (tristate::TS_TRUE));              \
    2216                 :            :   SELFTEST_END_STMT
    2217                 :            : 
    2218                 :            : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
    2219                 :            :    as "false".  */
    2220                 :            : 
    2221                 :            : #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
    2222                 :            :   SELFTEST_BEGIN_STMT                                                   \
    2223                 :            :   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
    2224                 :            :                     tristate (tristate::TS_FALSE));             \
    2225                 :            :   SELFTEST_END_STMT
    2226                 :            : 
    2227                 :            : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
    2228                 :            :    as "unknown".  */
    2229                 :            : 
    2230                 :            : #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
    2231                 :            :   SELFTEST_BEGIN_STMT                                                   \
    2232                 :            :   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
    2233                 :            :                     tristate (tristate::TS_UNKNOWN));           \
    2234                 :            :   SELFTEST_END_STMT
    2235                 :            : 
    2236                 :            : } /* end of namespace selftest.  */
    2237                 :            : 
    2238                 :            : #endif /* #if CHECKING_P */
    2239                 :            : 
    2240                 :            : } // namespace ana
    2241                 :            : 
    2242                 :            : #endif /* GCC_ANALYZER_REGION_MODEL_H */

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.