LCOV - code coverage report
Current view: top level - gcc/analyzer - svalue.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 94.4 % 426 402
Test Date: 2024-03-23 14:05:01 Functions: 90.8 % 87 79
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Symbolic values.
       2                 :             :    Copyright (C) 2019-2024 Free Software Foundation, Inc.
       3                 :             :    Contributed by David Malcolm <dmalcolm@redhat.com>.
       4                 :             : 
       5                 :             : This file is part of GCC.
       6                 :             : 
       7                 :             : GCC is free software; you can redistribute it and/or modify it
       8                 :             : under the terms of the GNU General Public License as published by
       9                 :             : the Free Software Foundation; either version 3, or (at your option)
      10                 :             : any later version.
      11                 :             : 
      12                 :             : GCC is distributed in the hope that it will be useful, but
      13                 :             : WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :             : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      15                 :             : General Public License for more details.
      16                 :             : 
      17                 :             : You should have received a copy of the GNU General Public License
      18                 :             : along with GCC; see the file COPYING3.  If not see
      19                 :             : <http://www.gnu.org/licenses/>.  */
      20                 :             : 
      21                 :             : #ifndef GCC_ANALYZER_SVALUE_H
      22                 :             : #define GCC_ANALYZER_SVALUE_H
      23                 :             : 
      24                 :             : #include "analyzer/symbol.h"
      25                 :             : #include "analyzer/store.h"
      26                 :             : #include "analyzer/program-point.h"
      27                 :             : 
      28                 :             : using namespace ana;
      29                 :             : 
      30                 :             : namespace ana {
      31                 :             : 
      32                 :             : /* An enum for discriminating between the different concrete subclasses
      33                 :             :    of svalue.  */
      34                 :             : 
      35                 :             : enum svalue_kind
      36                 :             : {
      37                 :             :   SK_REGION,
      38                 :             :   SK_CONSTANT,
      39                 :             :   SK_UNKNOWN,
      40                 :             :   SK_POISONED,
      41                 :             :   SK_SETJMP,
      42                 :             :   SK_INITIAL,
      43                 :             :   SK_UNARYOP,
      44                 :             :   SK_BINOP,
      45                 :             :   SK_SUB,
      46                 :             :   SK_REPEATED,
      47                 :             :   SK_BITS_WITHIN,
      48                 :             :   SK_UNMERGEABLE,
      49                 :             :   SK_PLACEHOLDER,
      50                 :             :   SK_WIDENING,
      51                 :             :   SK_COMPOUND,
      52                 :             :   SK_CONJURED,
      53                 :             :   SK_ASM_OUTPUT,
      54                 :             :   SK_CONST_FN_RESULT
      55                 :             : };
      56                 :             : 
      57                 :             : /* svalue and its subclasses.
      58                 :             : 
      59                 :             :    The class hierarchy looks like this (using indentation to show
      60                 :             :    inheritance, and with svalue_kinds shown for the concrete subclasses):
      61                 :             : 
      62                 :             :    svalue
      63                 :             :      region_svalue (SK_REGION): a pointer to a region
      64                 :             :      constant_svalue (SK_CONSTANT): a constant
      65                 :             :      unknown_svalue (SK_UNKNOWN): an unknowable value
      66                 :             :      poisoned_svalue (SK_POISONED): a unusable value (undefined)
      67                 :             :      setjmp_svalue (SK_SETJMP): a setjmp/longjmp buffer
      68                 :             :      initial_svalue (SK_INITIAL): the initial value of a region
      69                 :             :      unaryop_svalue (SK_UNARYOP): unary operation on another svalue
      70                 :             :      binop_svalue (SK_BINOP): binary operation on two svalues
      71                 :             :      sub_svalue (SK_SUB): the result of accessing a subregion
      72                 :             :      repeated_svalue (SK_REPEATED): repeating an svalue to fill a larger region
      73                 :             :      bits_within_svalue (SK_BITS_WITHIN): a range of bits/bytes within a larger
      74                 :             :        svalue
      75                 :             :      unmergeable_svalue (SK_UNMERGEABLE): a value that is so interesting
      76                 :             :        from a control-flow perspective that it can inhibit state-merging
      77                 :             :      placeholder_svalue (SK_PLACEHOLDER): for use in selftests.
      78                 :             :      widening_svalue (SK_WIDENING): a merger of two svalues (possibly
      79                 :             :        in an iteration).
      80                 :             :      compound_svalue (SK_COMPOUND): a mapping of bit-ranges to svalues
      81                 :             :      conjured_svalue (SK_CONJURED): a value arising from a stmt
      82                 :             :      asm_output_svalue (SK_ASM_OUTPUT): an output from a deterministic
      83                 :             :        asm stmt.
      84                 :             :      const_fn_result_svalue (SK_CONST_FN_RESULT): the return value from
      85                 :             :        a function with __attribute((const)) for given inputs.  */
      86                 :             : 
      87                 :             : /* An abstract base class representing a value held by a region of memory.  */
      88                 :             : 
      89                 :             : class svalue : public symbol
      90                 :             : {
      91                 :             : public:
      92                 :          28 :   virtual ~svalue () {}
      93                 :             : 
      94                 :    43077043 :   tree get_type () const { return m_type; }
      95                 :             : 
      96                 :             :   virtual enum svalue_kind get_kind () const = 0;
      97                 :             : 
      98                 :             :   void print (const region_model &model,
      99                 :             :               pretty_printer *pp) const;
     100                 :             : 
     101                 :             :   virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
     102                 :             :   void dump (bool simple=true) const;
     103                 :             :   label_text get_desc (bool simple=true) const;
     104                 :             : 
     105                 :             :   json::value *to_json () const;
     106                 :             : 
     107                 :             :   virtual const region_svalue *
     108                 :    11400432 :   dyn_cast_region_svalue () const { return NULL; }
     109                 :             :   virtual const constant_svalue *
     110                 :    10092472 :   dyn_cast_constant_svalue () const { return NULL; }
     111                 :             :   virtual const poisoned_svalue *
     112                 :     1933992 :   dyn_cast_poisoned_svalue () const { return NULL; }
     113                 :             :   virtual const setjmp_svalue *
     114                 :          45 :   dyn_cast_setjmp_svalue () const { return NULL; }
     115                 :             :   virtual const initial_svalue *
     116                 :     2945174 :   dyn_cast_initial_svalue () const { return NULL; }
     117                 :             :   virtual const unaryop_svalue *
     118                 :    11110516 :   dyn_cast_unaryop_svalue () const { return NULL; }
     119                 :             :   virtual const binop_svalue *
     120                 :     1019105 :   dyn_cast_binop_svalue () const { return NULL; }
     121                 :             :   virtual const sub_svalue *
     122                 :     2578910 :   dyn_cast_sub_svalue () const { return NULL; }
     123                 :             :   virtual const repeated_svalue *
     124                 :       17018 :   dyn_cast_repeated_svalue () const { return NULL; }
     125                 :             :   virtual const bits_within_svalue *
     126                 :           0 :   dyn_cast_bits_within_svalue () const { return NULL; }
     127                 :             :   virtual const unmergeable_svalue *
     128                 :    17982225 :   dyn_cast_unmergeable_svalue () const { return NULL; }
     129                 :             :   virtual const widening_svalue *
     130                 :      486404 :   dyn_cast_widening_svalue () const { return NULL; }
     131                 :             :   virtual const compound_svalue *
     132                 :    11018374 :   dyn_cast_compound_svalue () const { return NULL; }
     133                 :             :   virtual const conjured_svalue *
     134                 :           0 :   dyn_cast_conjured_svalue () const { return NULL; }
     135                 :             :   virtual const asm_output_svalue *
     136                 :           0 :   dyn_cast_asm_output_svalue () const { return NULL; }
     137                 :             :   virtual const const_fn_result_svalue *
     138                 :           0 :   dyn_cast_const_fn_result_svalue () const { return NULL; }
     139                 :             : 
     140                 :             :   tree maybe_get_constant () const;
     141                 :             :   const region *maybe_get_region () const;
     142                 :             :   const svalue *maybe_undo_cast () const;
     143                 :             :   const svalue *unwrap_any_unmergeable () const;
     144                 :             : 
     145                 :             :   const svalue *can_merge_p (const svalue *other,
     146                 :             :                               region_model_manager *mgr,
     147                 :             :                               model_merger *merger) const;
     148                 :             : 
     149                 :             :   virtual void accept (visitor *v) const  = 0;
     150                 :             : 
     151                 :             :   bool live_p (const svalue_set *live_svalues,
     152                 :             :                const region_model *model) const;
     153                 :             :   virtual bool implicitly_live_p (const svalue_set *live_svalues,
     154                 :             :                                   const region_model *model) const;
     155                 :             : 
     156                 :             :   static int cmp_ptr (const svalue *, const svalue *);
     157                 :             :   static int cmp_ptr_ptr (const void *, const void *);
     158                 :             : 
     159                 :             :   bool involves_p (const svalue *other) const;
     160                 :             : 
     161                 :             :   const svalue *
     162                 :             :   extract_bit_range (tree type,
     163                 :             :                      const bit_range &subrange,
     164                 :             :                      region_model_manager *mgr) const;
     165                 :             : 
     166                 :             :   virtual const svalue *
     167                 :             :   maybe_fold_bits_within (tree type,
     168                 :             :                           const bit_range &subrange,
     169                 :             :                           region_model_manager *mgr) const;
     170                 :             : 
     171                 :             :   virtual bool all_zeroes_p () const;
     172                 :             : 
     173                 :             :   /* Can this svalue be involved in constraints and sm-state?
     174                 :             :      Most can, but UNKNOWN and POISONED svalues are singletons
     175                 :             :      per-type and thus it's meaningless for them to "have state".  */
     176                 :     2600050 :   virtual bool can_have_associated_state_p () const { return true; }
     177                 :             : 
     178                 :             :   const region *maybe_get_deref_base_region () const;
     179                 :             : 
     180                 :             :   bool maybe_print_for_user (pretty_printer *pp,
     181                 :             :                              const region_model &model,
     182                 :             :                              const svalue *outer_sval = nullptr) const;
     183                 :             : 
     184                 :             :  protected:
     185                 :      210473 :   svalue (complexity c, symbol::id_t id, tree type)
     186                 :       99383 :   : symbol (c, id), m_type (type)
     187                 :             :   {}
     188                 :             : 
     189                 :             :  private:
     190                 :             :   tree m_type;
     191                 :             : };
     192                 :             : 
     193                 :             : /* Concrete subclass of svalue representing a pointer value that points to
     194                 :             :    a known region  */
     195                 :             : 
     196                 :             : class region_svalue : public svalue
     197                 :             : {
     198                 :             : public:
     199                 :             :   /* A support class for uniquifying instances of region_svalue.  */
     200                 :             :   struct key_t
     201                 :             :   {
     202                 :     1108751 :     key_t (tree type, const region *reg)
     203                 :     1108751 :     : m_type (type), m_reg (reg)
     204                 :             :     {}
     205                 :             : 
     206                 :     5680535 :     hashval_t hash () const
     207                 :             :     {
     208                 :     5680535 :       inchash::hash hstate;
     209                 :     5680535 :       hstate.add_ptr (m_type);
     210                 :     5680535 :       hstate.add_ptr (m_reg);
     211                 :     5680535 :       return hstate.end ();
     212                 :             :     }
     213                 :             : 
     214                 :     5395998 :     bool operator== (const key_t &other) const
     215                 :             :     {
     216                 :     5395998 :       return (m_type == other.m_type && m_reg == other.m_reg);
     217                 :             :     }
     218                 :             : 
     219                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
     220                 :      107752 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     221                 :     6033888 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
     222                 :    20281692 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
     223                 :             : 
     224                 :             :     tree m_type;
     225                 :             :     const region *m_reg;
     226                 :             :   };
     227                 :             : 
     228                 :       27594 :   region_svalue (symbol::id_t id, tree type, const region *reg)
     229                 :       27594 :   : svalue (complexity (reg), id, type),
     230                 :       27594 :     m_reg (reg)
     231                 :             :   {
     232                 :       27594 :     gcc_assert (m_reg != NULL);
     233                 :       27594 :   }
     234                 :             : 
     235                 :    12285467 :   enum svalue_kind get_kind () const final override { return SK_REGION; }
     236                 :             :   const region_svalue *
     237                 :     2590888 :   dyn_cast_region_svalue () const final override { return this; }
     238                 :             : 
     239                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     240                 :             :   void accept (visitor *v) const final override;
     241                 :             :   bool implicitly_live_p (const svalue_set *,
     242                 :             :                           const region_model *) const final override;
     243                 :             : 
     244                 :     4930014 :   const region * get_pointee () const { return m_reg; }
     245                 :             : 
     246                 :             :   static tristate eval_condition (const region_svalue *lhs_ptr,
     247                 :             :                                   enum tree_code op,
     248                 :             :                                   const region_svalue *rhs_ptr);
     249                 :             : 
     250                 :             :  private:
     251                 :             :   const region *m_reg;
     252                 :             : };
     253                 :             : 
     254                 :             : } // namespace ana
     255                 :             : 
     256                 :             : template <>
     257                 :             : template <>
     258                 :             : inline bool
     259                 :       63842 : is_a_helper <const region_svalue *>::test (const svalue *sval)
     260                 :             : {
     261                 :       63842 :   return sval->get_kind () == SK_REGION;
     262                 :             : }
     263                 :             : 
     264                 :             : template <> struct default_hash_traits<region_svalue::key_t>
     265                 :             : : public member_function_hash_traits<region_svalue::key_t>
     266                 :             : {
     267                 :             :   static const bool empty_zero_p = false;
     268                 :             : };
     269                 :             : 
     270                 :             : namespace ana {
     271                 :             : 
     272                 :             : /* Concrete subclass of svalue representing a specific constant value.
     273                 :             :    The type will either be the same as that of the underlying tree constant,
     274                 :             :    or NULL_TREE indicating the constant is intended to be "typeless".  */
     275                 :             : 
     276                 :             : class constant_svalue : public svalue
     277                 :             : {
     278                 :             : public:
     279                 :             :   /* A support class for uniquifying instances of region_svalue.  */
     280                 :             :   struct key_t
     281                 :             :   {
     282                 :     2539564 :     key_t (tree type, tree cst)
     283                 :     2539564 :     : m_type (type), m_cst (cst)
     284                 :             :     {}
     285                 :             : 
     286                 :    16369485 :     hashval_t hash () const
     287                 :             :     {
     288                 :    16369485 :       inchash::hash hstate;
     289                 :    16369485 :       hstate.add_ptr (m_type);
     290                 :    16369485 :       hstate.add_ptr (m_cst);
     291                 :    16369485 :       return hstate.end ();
     292                 :             :     }
     293                 :             : 
     294                 :    16399683 :     bool operator== (const key_t &other) const
     295                 :             :     {
     296                 :    16399683 :       return (m_type == other.m_type && m_cst == other.m_cst);
     297                 :             :     }
     298                 :             : 
     299                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
     300                 :      189481 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     301                 :    17164130 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
     302                 :    49638632 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
     303                 :             : 
     304                 :             :     tree m_type;
     305                 :             :     tree m_cst;
     306                 :             :   };
     307                 :             : 
     308                 :       60799 :   constant_svalue (symbol::id_t id, tree type, tree cst_expr)
     309                 :       60799 :   : svalue (complexity (1, 1), id, type),
     310                 :       60799 :     m_cst_expr (cst_expr)
     311                 :             :   {
     312                 :       60799 :     gcc_assert (cst_expr);
     313                 :       60799 :     gcc_assert (CONSTANT_CLASS_P (cst_expr));
     314                 :       60799 :     gcc_assert (type == TREE_TYPE (cst_expr) || type == NULL_TREE);
     315                 :       60799 :   }
     316                 :             : 
     317                 :    27841189 :   enum svalue_kind get_kind () const final override { return SK_CONSTANT; }
     318                 :             :   const constant_svalue *
     319                 :     4288745 :   dyn_cast_constant_svalue () const final override { return this; }
     320                 :             : 
     321                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     322                 :             :   void accept (visitor *v) const final override;
     323                 :             :   bool implicitly_live_p (const svalue_set *,
     324                 :             :                           const region_model *) const final override;
     325                 :             : 
     326                 :     5995830 :   tree get_constant () const { return m_cst_expr; }
     327                 :             :   static tristate eval_condition (const constant_svalue *lhs,
     328                 :             :                                   enum tree_code op,
     329                 :             :                                   const constant_svalue *rhs);
     330                 :             : 
     331                 :             :   const svalue *
     332                 :             :   maybe_fold_bits_within (tree type,
     333                 :             :                           const bit_range &subrange,
     334                 :             :                           region_model_manager *mgr) const final override;
     335                 :             : 
     336                 :             :   bool all_zeroes_p () const final override;
     337                 :             : 
     338                 :             :  private:
     339                 :             :   tree m_cst_expr;
     340                 :             : };
     341                 :             : 
     342                 :             : } // namespace ana
     343                 :             : 
     344                 :             : template <>
     345                 :             : template <>
     346                 :             : inline bool
     347                 :        2084 : is_a_helper <const constant_svalue *>::test (const svalue *sval)
     348                 :             : {
     349                 :        2084 :   return sval->get_kind () == SK_CONSTANT;
     350                 :             : }
     351                 :             : 
     352                 :             : template <> struct default_hash_traits<constant_svalue::key_t>
     353                 :             : : public member_function_hash_traits<constant_svalue::key_t>
     354                 :             : {
     355                 :             :   static const bool empty_zero_p = false;
     356                 :             : };
     357                 :             : 
     358                 :             : namespace ana {
     359                 :             : 
     360                 :             : /* Concrete subclass of svalue representing an unknowable value, the bottom
     361                 :             :    value when thinking of svalues as a lattice.
     362                 :             :    This is a singleton (w.r.t. its manager): there is a single unknown_svalue
     363                 :             :    per type.  Self-comparisons of such instances yield "unknown".  */
     364                 :             : 
     365                 :             : class unknown_svalue : public svalue
     366                 :             : {
     367                 :             : public:
     368                 :       10884 :   unknown_svalue (symbol::id_t id, tree type)
     369                 :       10884 :   : svalue (complexity (1, 1), id, type)
     370                 :             :   {}
     371                 :             : 
     372                 :     4906312 :   enum svalue_kind get_kind () const final override { return SK_UNKNOWN; }
     373                 :             : 
     374                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     375                 :             :   void accept (visitor *v) const final override;
     376                 :             : 
     377                 :             :   const svalue *
     378                 :             :   maybe_fold_bits_within (tree type,
     379                 :             :                           const bit_range &subrange,
     380                 :             :                           region_model_manager *mgr) const final override;
     381                 :             : 
     382                 :             :   /* Unknown values are singletons per-type, so can't have state.  */
     383                 :      134221 :   bool can_have_associated_state_p () const final override { return false; }
     384                 :             : };
     385                 :             : 
     386                 :             : /* An enum describing a particular kind of "poisoned" value.  */
     387                 :             : 
     388                 :             : enum poison_kind
     389                 :             : {
     390                 :             :   /* For use to describe uninitialized memory.  */
     391                 :             :   POISON_KIND_UNINIT,
     392                 :             : 
     393                 :             :   /* For use to describe freed memory.  */
     394                 :             :   POISON_KIND_FREED,
     395                 :             : 
     396                 :             :   /* For use to describe deleted memory.  */
     397                 :             :   POISON_KIND_DELETED,
     398                 :             : 
     399                 :             :   /* For use on pointers to regions within popped stack frames.  */
     400                 :             :   POISON_KIND_POPPED_STACK
     401                 :             : };
     402                 :             : 
     403                 :             : extern const char *poison_kind_to_str (enum poison_kind);
     404                 :             : 
     405                 :             : /* Concrete subclass of svalue representing a value that should not
     406                 :             :    be used (e.g. uninitialized memory, freed memory).  */
     407                 :             : 
     408                 :             : class poisoned_svalue : public svalue
     409                 :             : {
     410                 :             : public:
     411                 :             :   /* A support class for uniquifying instances of poisoned_svalue.  */
     412                 :             :   struct key_t
     413                 :             :   {
     414                 :      289818 :     key_t (enum poison_kind kind, tree type)
     415                 :      289818 :     : m_kind (kind), m_type (type)
     416                 :             :     {}
     417                 :             : 
     418                 :     1115102 :     hashval_t hash () const
     419                 :             :     {
     420                 :     1115102 :       inchash::hash hstate;
     421                 :     1115102 :       hstate.add_int (m_kind);
     422                 :     1115102 :       hstate.add_ptr (m_type);
     423                 :     1115102 :       return hstate.end ();
     424                 :             :     }
     425                 :             : 
     426                 :      874406 :     bool operator== (const key_t &other) const
     427                 :             :     {
     428                 :      874406 :       return (m_kind == other.m_kind && m_type == other.m_type);
     429                 :             :     }
     430                 :             : 
     431                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
     432                 :       56207 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     433                 :     1150564 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
     434                 :     4858131 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
     435                 :             : 
     436                 :             :     enum poison_kind m_kind;
     437                 :             :     tree m_type;
     438                 :             :   };
     439                 :             : 
     440                 :        5849 :   poisoned_svalue (enum poison_kind kind, symbol::id_t id, tree type)
     441                 :        5849 :   : svalue (complexity (1, 1), id, type), m_kind (kind) {}
     442                 :             : 
     443                 :      352487 :   enum svalue_kind get_kind () const final override { return SK_POISONED; }
     444                 :             :   const poisoned_svalue *
     445                 :        6110 :   dyn_cast_poisoned_svalue () const final override { return this; }
     446                 :             : 
     447                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     448                 :             :   void accept (visitor *v) const final override;
     449                 :             : 
     450                 :             :   const svalue *
     451                 :             :   maybe_fold_bits_within (tree type,
     452                 :             :                           const bit_range &subrange,
     453                 :             :                           region_model_manager *mgr) const final override;
     454                 :             : 
     455                 :        6175 :   enum poison_kind get_poison_kind () const { return m_kind; }
     456                 :             : 
     457                 :             :   /* Poisoned svalues are singletons per-type, so can't have state.  */
     458                 :       19532 :   bool can_have_associated_state_p () const final override { return false; }
     459                 :             : 
     460                 :             :  private:
     461                 :             :   enum poison_kind m_kind;
     462                 :             : };
     463                 :             : 
     464                 :             : } // namespace ana
     465                 :             : 
     466                 :             : template <>
     467                 :             : template <>
     468                 :             : inline bool
     469                 :          57 : is_a_helper <const poisoned_svalue *>::test (const svalue *sval)
     470                 :             : {
     471                 :          57 :   return sval->get_kind () == SK_POISONED;
     472                 :             : }
     473                 :             : 
     474                 :             : template <> struct default_hash_traits<poisoned_svalue::key_t>
     475                 :             : : public member_function_hash_traits<poisoned_svalue::key_t>
     476                 :             : {
     477                 :             :   static const bool empty_zero_p = false;
     478                 :             : };
     479                 :             : 
     480                 :             : namespace ana {
     481                 :             : 
     482                 :             : /* A bundle of information recording a setjmp/sigsetjmp call, corresponding
     483                 :             :    roughly to a jmp_buf.  */
     484                 :             : 
     485                 :             : struct setjmp_record
     486                 :             : {
     487                 :          40 :   setjmp_record (const exploded_node *enode,
     488                 :             :                  const gcall *setjmp_call)
     489                 :          40 :   : m_enode (enode), m_setjmp_call (setjmp_call)
     490                 :             :   {
     491                 :             :   }
     492                 :             : 
     493                 :          14 :   bool operator== (const setjmp_record &other) const
     494                 :             :   {
     495                 :          14 :     return (m_enode == other.m_enode
     496                 :           0 :             && m_setjmp_call == other.m_setjmp_call);
     497                 :             :   }
     498                 :             : 
     499                 :          94 :   void add_to_hash (inchash::hash *hstate) const
     500                 :             :   {
     501                 :          94 :     hstate->add_ptr (m_enode);
     502                 :          94 :     hstate->add_ptr (m_setjmp_call);
     503                 :          94 :   }
     504                 :             : 
     505                 :             :   static int cmp (const setjmp_record &rec1, const setjmp_record &rec2);
     506                 :             : 
     507                 :             :   const exploded_node *m_enode;
     508                 :             :   const gcall *m_setjmp_call;
     509                 :             : };
     510                 :             : 
     511                 :             : /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
     512                 :             :    so that longjmp/siglongjmp can potentially "return" to an entirely
     513                 :             :    different function.  */
     514                 :             : 
     515                 :             : class setjmp_svalue : public svalue
     516                 :             : {
     517                 :             : public:
     518                 :             :   /* A support class for uniquifying instances of poisoned_svalue.  */
     519                 :             :   struct key_t
     520                 :             :   {
     521                 :          40 :     key_t (const setjmp_record &record, tree type)
     522                 :          40 :     : m_record (record), m_type (type)
     523                 :             :     {}
     524                 :             : 
     525                 :          94 :     hashval_t hash () const
     526                 :             :     {
     527                 :          94 :       inchash::hash hstate;
     528                 :          94 :       m_record.add_to_hash (&hstate);
     529                 :          94 :       hstate.add_ptr (m_type);
     530                 :          94 :       return hstate.end ();
     531                 :             :     }
     532                 :             : 
     533                 :          14 :     bool operator== (const key_t &other) const
     534                 :             :     {
     535                 :         800 :       return (m_record == other.m_record && m_type == other.m_type);
     536                 :             :     }
     537                 :             : 
     538                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
     539                 :       55835 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     540                 :          94 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
     541                 :      112924 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
     542                 :             : 
     543                 :             :     setjmp_record m_record;
     544                 :             :     tree m_type;
     545                 :             :   };
     546                 :             : 
     547                 :          40 :   setjmp_svalue (const setjmp_record &setjmp_record,
     548                 :             :                  symbol::id_t id,
     549                 :             :                  tree type)
     550                 :          40 :   : svalue (complexity (1, 1), id, type), m_setjmp_record (setjmp_record)
     551                 :             :   {}
     552                 :             : 
     553                 :        1987 :   enum svalue_kind get_kind () const final override { return SK_SETJMP; }
     554                 :             :   const setjmp_svalue *
     555                 :          29 :   dyn_cast_setjmp_svalue () const final override { return this; }
     556                 :             : 
     557                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     558                 :             :   void accept (visitor *v) const final override;
     559                 :             : 
     560                 :             :   int get_enode_index () const;
     561                 :             : 
     562                 :           0 :   const setjmp_record &get_setjmp_record () const { return m_setjmp_record; }
     563                 :             : 
     564                 :             :  private:
     565                 :             :   setjmp_record m_setjmp_record;
     566                 :             : };
     567                 :             : 
     568                 :             : } // namespace ana
     569                 :             : 
     570                 :             : template <>
     571                 :             : template <>
     572                 :             : inline bool
     573                 :             : is_a_helper <const setjmp_svalue *>::test (const svalue *sval)
     574                 :             : {
     575                 :             :   return sval->get_kind () == SK_SETJMP;
     576                 :             : }
     577                 :             : 
     578                 :             : template <> struct default_hash_traits<setjmp_svalue::key_t>
     579                 :             : : public member_function_hash_traits<setjmp_svalue::key_t>
     580                 :             : {
     581                 :             :   static const bool empty_zero_p = false;
     582                 :             : };
     583                 :             : 
     584                 :             : namespace ana {
     585                 :             : 
     586                 :             : /* Concrete subclass of svalue representing the initial value of a
     587                 :             :    specific region.
     588                 :             : 
     589                 :             :    This represents the initial value at the start of the analysis path,
     590                 :             :    as opposed to the first time the region is accessed during the path.
     591                 :             :    Hence as soon as we have a call to an unknown function, all previously
     592                 :             :    unmodelled globals become implicitly "unknown" rathen than "initial".  */
     593                 :             : 
     594                 :             : class initial_svalue : public svalue
     595                 :             : {
     596                 :             : public:
     597                 :       28915 :   initial_svalue (symbol::id_t id, tree type, const region *reg)
     598                 :       28915 :   : svalue (complexity (reg), id, type), m_reg (reg)
     599                 :             :   {
     600                 :       28915 :     gcc_assert (m_reg != NULL);
     601                 :       28915 :   }
     602                 :             : 
     603                 :    26800922 :   enum svalue_kind get_kind () const final override { return SK_INITIAL; }
     604                 :             :   const initial_svalue *
     605                 :      386825 :   dyn_cast_initial_svalue () const final override { return this; }
     606                 :             : 
     607                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     608                 :             :   void accept (visitor *v) const final override;
     609                 :             :   bool implicitly_live_p (const svalue_set *,
     610                 :             :                           const region_model *) const final override;
     611                 :             : 
     612                 :             :   bool initial_value_of_param_p () const;
     613                 :             : 
     614                 :     5244252 :   const region *get_region () const { return m_reg; }
     615                 :             : 
     616                 :             :  private:
     617                 :             :   const region *m_reg;
     618                 :             : };
     619                 :             : 
     620                 :             : } // namespace ana
     621                 :             : 
     622                 :             : template <>
     623                 :             : template <>
     624                 :             : inline bool
     625                 :     1562729 : is_a_helper <const initial_svalue *>::test (const svalue *sval)
     626                 :             : {
     627                 :     1562729 :   return sval->get_kind () == SK_INITIAL;
     628                 :             : }
     629                 :             : 
     630                 :             : namespace ana {
     631                 :             : 
     632                 :             : /* Concrete subclass of svalue representing a unary operation on
     633                 :             :    another svalues (e.g. a cast).  */
     634                 :             : 
     635                 :             : class unaryop_svalue : public svalue
     636                 :             : {
     637                 :             : public:
     638                 :             :   /* A support class for uniquifying instances of unaryop_svalue.  */
     639                 :             :   struct key_t
     640                 :             :   {
     641                 :       70841 :     key_t (tree type, enum tree_code op, const svalue *arg)
     642                 :       70841 :     : m_type (type), m_op (op), m_arg (arg)
     643                 :             :     {}
     644                 :             : 
     645                 :      415705 :     hashval_t hash () const
     646                 :             :     {
     647                 :      415705 :       inchash::hash hstate;
     648                 :      415705 :       hstate.add_ptr (m_type);
     649                 :      415705 :       hstate.add_int (m_op);
     650                 :      415705 :       hstate.add_ptr (m_arg);
     651                 :      415705 :       return hstate.end ();
     652                 :             :     }
     653                 :             : 
     654                 :      401914 :     bool operator== (const key_t &other) const
     655                 :             :     {
     656                 :      401914 :       return (m_type == other.m_type
     657                 :      180061 :               && m_op == other.m_op
     658                 :      580043 :               && m_arg == other.m_arg);
     659                 :             :     }
     660                 :             : 
     661                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
     662                 :       72891 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     663                 :      458664 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
     664                 :     1634125 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
     665                 :             : 
     666                 :             :     tree m_type;
     667                 :             :     enum tree_code m_op;
     668                 :             :     const svalue *m_arg;
     669                 :             :   };
     670                 :             : 
     671                 :        9955 :   unaryop_svalue (symbol::id_t id, tree type, enum tree_code op,
     672                 :             :                   const svalue *arg)
     673                 :        9955 :   : svalue (complexity (arg), id, type), m_op (op), m_arg (arg)
     674                 :             :   {
     675                 :        9955 :     gcc_assert (arg->can_have_associated_state_p ());
     676                 :        9955 :   }
     677                 :             : 
     678                 :     2259990 :   enum svalue_kind get_kind () const final override { return SK_UNARYOP; }
     679                 :             :   const unaryop_svalue *
     680                 :      167755 :   dyn_cast_unaryop_svalue () const final override { return this; }
     681                 :             : 
     682                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     683                 :             :   void accept (visitor *v) const final override;
     684                 :             :   bool implicitly_live_p (const svalue_set *,
     685                 :             :                           const region_model *) const final override;
     686                 :             : 
     687                 :      398650 :   enum tree_code get_op () const { return m_op; }
     688                 :      516913 :   const svalue *get_arg () const { return m_arg; }
     689                 :             : 
     690                 :             :   const svalue *
     691                 :             :   maybe_fold_bits_within (tree type,
     692                 :             :                           const bit_range &subrange,
     693                 :             :                           region_model_manager *mgr) const final override;
     694                 :             : 
     695                 :             :  private:
     696                 :             :   enum tree_code m_op;
     697                 :             :   const svalue *m_arg;
     698                 :             : };
     699                 :             : 
     700                 :             : } // namespace ana
     701                 :             : 
     702                 :             : template <>
     703                 :             : template <>
     704                 :             : inline bool
     705                 :      272926 : is_a_helper <const unaryop_svalue *>::test (const svalue *sval)
     706                 :             : {
     707                 :      272926 :   return sval->get_kind () == SK_UNARYOP;
     708                 :             : }
     709                 :             : 
     710                 :             : template <> struct default_hash_traits<unaryop_svalue::key_t>
     711                 :             : : public member_function_hash_traits<unaryop_svalue::key_t>
     712                 :             : {
     713                 :             :   static const bool empty_zero_p = false;
     714                 :             : };
     715                 :             : 
     716                 :             : namespace ana {
     717                 :             : 
     718                 :             : /* Concrete subclass of svalue representing a binary operation of
     719                 :             :    two svalues.  */
     720                 :             : 
     721                 :             : class binop_svalue : public svalue
     722                 :             : {
     723                 :             : public:
     724                 :             :   /* A support class for uniquifying instances of binop_svalue.  */
     725                 :             :   struct key_t
     726                 :             :   {
     727                 :      108658 :     key_t (tree type, enum tree_code op,
     728                 :             :            const svalue *arg0, const svalue *arg1)
     729                 :      108658 :     : m_type (type), m_op (op), m_arg0 (arg0), m_arg1 (arg1)
     730                 :             :     {}
     731                 :             : 
     732                 :      803316 :     hashval_t hash () const
     733                 :             :     {
     734                 :      803316 :       inchash::hash hstate;
     735                 :      803316 :       hstate.add_ptr (m_type);
     736                 :      803316 :       hstate.add_int (m_op);
     737                 :      803316 :       hstate.add_ptr (m_arg0);
     738                 :      803316 :       hstate.add_ptr (m_arg1);
     739                 :      803316 :       return hstate.end ();
     740                 :             :     }
     741                 :             : 
     742                 :      794837 :     bool operator== (const key_t &other) const
     743                 :             :     {
     744                 :      794837 :       return (m_type == other.m_type
     745                 :      337932 :               && m_op == other.m_op
     746                 :      251641 :               && m_arg0 == other.m_arg0
     747                 :      900829 :               && m_arg1 == other.m_arg1);
     748                 :             :     }
     749                 :             : 
     750                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
     751                 :      122374 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     752                 :      894783 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
     753                 :     2873102 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
     754                 :             : 
     755                 :             :     tree m_type;
     756                 :             :     enum tree_code m_op;
     757                 :             :     const svalue *m_arg0;
     758                 :             :     const svalue *m_arg1;
     759                 :             :   };
     760                 :             : 
     761                 :       24841 :   binop_svalue (symbol::id_t id, tree type, enum tree_code op,
     762                 :             :                 const svalue *arg0, const svalue *arg1)
     763                 :       24841 :   : svalue (complexity::from_pair (arg0->get_complexity (),
     764                 :             :                                     arg1->get_complexity ()),
     765                 :             :             id,
     766                 :             :             type),
     767                 :       24841 :     m_op (op), m_arg0 (arg0), m_arg1 (arg1)
     768                 :             :   {
     769                 :       24841 :     gcc_assert (arg0->can_have_associated_state_p ());
     770                 :       24841 :     gcc_assert (arg1->can_have_associated_state_p ());
     771                 :       24841 :   }
     772                 :             : 
     773                 :    12523488 :   enum svalue_kind get_kind () const final override { return SK_BINOP; }
     774                 :      137127 :   const binop_svalue *dyn_cast_binop_svalue () const final override
     775                 :             :   {
     776                 :      137127 :     return this;
     777                 :             :   }
     778                 :             : 
     779                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     780                 :             :   void accept (visitor *v) const final override;
     781                 :             :   bool implicitly_live_p (const svalue_set *,
     782                 :             :                           const region_model *) const final override;
     783                 :             : 
     784                 :     2476579 :   enum tree_code get_op () const { return m_op; }
     785                 :     2426206 :   const svalue *get_arg0 () const { return m_arg0; }
     786                 :     2183090 :   const svalue *get_arg1 () const { return m_arg1; }
     787                 :             : 
     788                 :             :  private:
     789                 :             :   enum tree_code m_op;
     790                 :             :   const svalue *m_arg0;
     791                 :             :   const svalue *m_arg1;
     792                 :             : };
     793                 :             : 
     794                 :             : } // namespace ana
     795                 :             : 
     796                 :             : template <>
     797                 :             : template <>
     798                 :             : inline bool
     799                 :      230796 : is_a_helper <const binop_svalue *>::test (const svalue *sval)
     800                 :             : {
     801                 :      230796 :   return sval->get_kind () == SK_BINOP;
     802                 :             : }
     803                 :             : 
     804                 :             : template <> struct default_hash_traits<binop_svalue::key_t>
     805                 :             : : public member_function_hash_traits<binop_svalue::key_t>
     806                 :             : {
     807                 :             :   static const bool empty_zero_p = false;
     808                 :             : };
     809                 :             : 
     810                 :             : namespace ana {
     811                 :             : 
     812                 :             : /* Concrete subclass of svalue representing the result of accessing a subregion
     813                 :             :    of another svalue (the value of a component/field of a struct, or an element
     814                 :             :    from an array).  */
     815                 :             : 
     816                 :             : class sub_svalue : public svalue
     817                 :             : {
     818                 :             : public:
     819                 :             :   /* A support class for uniquifying instances of sub_svalue.  */
     820                 :             :   struct key_t
     821                 :             :   {
     822                 :       17023 :     key_t (tree type, const svalue *parent_svalue, const region *subregion)
     823                 :       17023 :     : m_type (type), m_parent_svalue (parent_svalue), m_subregion (subregion)
     824                 :             :     {}
     825                 :             : 
     826                 :      106437 :     hashval_t hash () const
     827                 :             :     {
     828                 :      106437 :       inchash::hash hstate;
     829                 :      106437 :       hstate.add_ptr (m_type);
     830                 :      106437 :       hstate.add_ptr (m_parent_svalue);
     831                 :      106437 :       hstate.add_ptr (m_subregion);
     832                 :      106437 :       return hstate.end ();
     833                 :             :     }
     834                 :             : 
     835                 :      107328 :     bool operator== (const key_t &other) const
     836                 :             :     {
     837                 :      107328 :       return (m_type == other.m_type
     838                 :       47986 :               && m_parent_svalue == other.m_parent_svalue
     839                 :      128944 :               && m_subregion == other.m_subregion);
     840                 :             :     }
     841                 :             : 
     842                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
     843                 :       59572 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     844                 :      120722 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
     845                 :      495723 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
     846                 :             : 
     847                 :             :     tree m_type;
     848                 :             :     const svalue *m_parent_svalue;
     849                 :             :     const region *m_subregion;
     850                 :             :   };
     851                 :             :   sub_svalue (symbol::id_t id, tree type, const svalue *parent_svalue,
     852                 :             :               const region *subregion);
     853                 :             : 
     854                 :      152020 :   enum svalue_kind get_kind () const final override { return SK_SUB; }
     855                 :       11911 :   const sub_svalue *dyn_cast_sub_svalue () const final override
     856                 :             :   {
     857                 :       11911 :     return this;
     858                 :             :   }
     859                 :             : 
     860                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     861                 :             :   void accept (visitor *v) const final override;
     862                 :             :   bool implicitly_live_p (const svalue_set *,
     863                 :             :                           const region_model *) const final override;
     864                 :             : 
     865                 :       77761 :   const svalue *get_parent () const { return m_parent_svalue; }
     866                 :       17511 :   const region *get_subregion () const { return m_subregion; }
     867                 :             : 
     868                 :             :  private:
     869                 :             :   const svalue *m_parent_svalue;
     870                 :             :   const region *m_subregion;
     871                 :             : };
     872                 :             : 
     873                 :             : } // namespace ana
     874                 :             : 
     875                 :             : template <>
     876                 :             : template <>
     877                 :             : inline bool
     878                 :           0 : is_a_helper <const sub_svalue *>::test (const svalue *sval)
     879                 :             : {
     880                 :           0 :   return sval->get_kind () == SK_SUB;
     881                 :             : }
     882                 :             : 
     883                 :             : template <> struct default_hash_traits<sub_svalue::key_t>
     884                 :             : : public member_function_hash_traits<sub_svalue::key_t>
     885                 :             : {
     886                 :             :   static const bool empty_zero_p = false;
     887                 :             : };
     888                 :             : 
     889                 :             : namespace ana {
     890                 :             : 
     891                 :             : /* Concrete subclass of svalue representing repeating an inner svalue
     892                 :             :    (possibly not a whole number of times) to fill a larger region of
     893                 :             :    type TYPE of size OUTER_SIZE bytes.  */
     894                 :             : 
     895                 :             : class repeated_svalue : public svalue
     896                 :             : {
     897                 :             : public:
     898                 :             :   /* A support class for uniquifying instances of repeated_svalue.  */
     899                 :             :   struct key_t
     900                 :             :   {
     901                 :        2498 :     key_t (tree type,
     902                 :             :            const svalue *outer_size,
     903                 :             :            const svalue *inner_svalue)
     904                 :        2498 :     : m_type (type), m_outer_size (outer_size), m_inner_svalue (inner_svalue)
     905                 :             :     {}
     906                 :             : 
     907                 :       14102 :     hashval_t hash () const
     908                 :             :     {
     909                 :       14102 :       inchash::hash hstate;
     910                 :       14102 :       hstate.add_ptr (m_type);
     911                 :       14102 :       hstate.add_ptr (m_outer_size);
     912                 :       14102 :       hstate.add_ptr (m_inner_svalue);
     913                 :       14102 :       return hstate.end ();
     914                 :             :     }
     915                 :             : 
     916                 :       12450 :     bool operator== (const key_t &other) const
     917                 :             :     {
     918                 :       12450 :       return (m_type == other.m_type
     919                 :       12300 :               && m_outer_size == other.m_outer_size
     920                 :       14447 :               && m_inner_svalue == other.m_inner_svalue);
     921                 :             :     }
     922                 :             : 
     923                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
     924                 :       56455 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     925                 :       14909 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
     926                 :      166940 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
     927                 :             : 
     928                 :             :     tree m_type;
     929                 :             :     const svalue *m_outer_size;
     930                 :             :     const svalue *m_inner_svalue;
     931                 :             :   };
     932                 :             :   repeated_svalue (symbol::id_t id,
     933                 :             :                    tree type,
     934                 :             :                    const svalue *outer_size,
     935                 :             :                    const svalue *inner_svalue);
     936                 :             : 
     937                 :      119548 :   enum svalue_kind get_kind () const final override { return SK_REPEATED; }
     938                 :         128 :   const repeated_svalue *dyn_cast_repeated_svalue () const final override
     939                 :             :   {
     940                 :         128 :     return this;
     941                 :             :   }
     942                 :             : 
     943                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
     944                 :             :   void accept (visitor *v) const final override;
     945                 :             : 
     946                 :          43 :   const svalue *get_outer_size () const { return m_outer_size; }
     947                 :         881 :   const svalue *get_inner_svalue () const { return m_inner_svalue; }
     948                 :             : 
     949                 :             :   bool all_zeroes_p () const final override;
     950                 :             : 
     951                 :             :   const svalue *
     952                 :             :   maybe_fold_bits_within (tree type,
     953                 :             :                           const bit_range &subrange,
     954                 :             :                           region_model_manager *mgr) const final override;
     955                 :             : 
     956                 :             :  private:
     957                 :             :   const svalue *m_outer_size;
     958                 :             :   const svalue *m_inner_svalue;
     959                 :             : };
     960                 :             : 
     961                 :             : } // namespace ana
     962                 :             : 
     963                 :             : template <>
     964                 :             : template <>
     965                 :             : inline bool
     966                 :          43 : is_a_helper <const repeated_svalue *>::test (const svalue *sval)
     967                 :             : {
     968                 :          43 :   return sval->get_kind () == SK_REPEATED;
     969                 :             : }
     970                 :             : 
     971                 :             : template <> struct default_hash_traits<repeated_svalue::key_t>
     972                 :             : : public member_function_hash_traits<repeated_svalue::key_t>
     973                 :             : {
     974                 :             :   static const bool empty_zero_p = false;
     975                 :             : };
     976                 :             : 
     977                 :             : namespace ana {
     978                 :             : 
     979                 :             : /* A range of bits/bytes within another svalue
     980                 :             :    e.g. bytes 5-39 of INITIAL_SVALUE(R).
     981                 :             :    These can be generated for prefixes and suffixes when part of a binding
     982                 :             :    is clobbered, so that we don't lose too much information.  */
     983                 :             : 
     984                 :             : class bits_within_svalue : public svalue
     985                 :             : {
     986                 :             : public:
     987                 :             :   /* A support class for uniquifying instances of bits_within_svalue.  */
     988                 :             :   struct key_t
     989                 :             :   {
     990                 :        1229 :     key_t (tree type,
     991                 :             :            const bit_range &bits,
     992                 :             :            const svalue *inner_svalue)
     993                 :        1229 :     : m_type (type), m_bits (bits), m_inner_svalue (inner_svalue)
     994                 :             :     {}
     995                 :             : 
     996                 :        5756 :     hashval_t hash () const
     997                 :             :     {
     998                 :        5756 :       inchash::hash hstate;
     999                 :        5756 :       hstate.add_ptr (m_type);
    1000                 :        5756 :       hstate.add_ptr (m_inner_svalue);
    1001                 :        5756 :       return hstate.end ();
    1002                 :             :     }
    1003                 :             : 
    1004                 :        4899 :     bool operator== (const key_t &other) const
    1005                 :             :     {
    1006                 :        4899 :       return (m_type == other.m_type
    1007                 :        3976 :               && m_bits == other.m_bits
    1008                 :        6369 :               && m_inner_svalue == other.m_inner_svalue);
    1009                 :             :     }
    1010                 :             : 
    1011                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
    1012                 :       56112 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
    1013                 :        7770 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
    1014                 :      144872 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
    1015                 :             : 
    1016                 :             :     tree m_type;
    1017                 :             :     bit_range m_bits;
    1018                 :             :     const svalue *m_inner_svalue;
    1019                 :             :   };
    1020                 :             :   bits_within_svalue (symbol::id_t id,
    1021                 :             :                       tree type,
    1022                 :             :                       const bit_range &bits,
    1023                 :             :                       const svalue *inner_svalue);
    1024                 :             : 
    1025                 :       45851 :   enum svalue_kind get_kind () const final override { return SK_BITS_WITHIN; }
    1026                 :             :   const bits_within_svalue *
    1027                 :           0 :   dyn_cast_bits_within_svalue () const final override
    1028                 :             :   {
    1029                 :           0 :     return this;
    1030                 :             :   }
    1031                 :             : 
    1032                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
    1033                 :             :   void accept (visitor *v) const final override;
    1034                 :             :   bool implicitly_live_p (const svalue_set *,
    1035                 :             :                           const region_model *) const final override;
    1036                 :             : 
    1037                 :         341 :   const bit_range &get_bits () const { return m_bits; }
    1038                 :          52 :   const svalue *get_inner_svalue () const { return m_inner_svalue; }
    1039                 :             : 
    1040                 :             :   const svalue *
    1041                 :             :   maybe_fold_bits_within (tree type,
    1042                 :             :                           const bit_range &subrange,
    1043                 :             :                           region_model_manager *mgr) const final override;
    1044                 :             : 
    1045                 :             :  private:
    1046                 :             :   const bit_range m_bits;
    1047                 :             :   const svalue *m_inner_svalue;
    1048                 :             : };
    1049                 :             : 
    1050                 :             : } // namespace ana
    1051                 :             : 
    1052                 :             : template <>
    1053                 :             : template <>
    1054                 :             : inline bool
    1055                 :           0 : is_a_helper <const bits_within_svalue *>::test (const svalue *sval)
    1056                 :             : {
    1057                 :           0 :   return sval->get_kind () == SK_BITS_WITHIN;
    1058                 :             : }
    1059                 :             : 
    1060                 :             : template <> struct default_hash_traits<bits_within_svalue::key_t>
    1061                 :             : : public member_function_hash_traits<bits_within_svalue::key_t>
    1062                 :             : {
    1063                 :             :   static const bool empty_zero_p = false;
    1064                 :             : };
    1065                 :             : 
    1066                 :             : namespace ana {
    1067                 :             : 
    1068                 :             : /* Concrete subclass of svalue: decorate another svalue,
    1069                 :             :    so that the resulting svalue can be identified as being
    1070                 :             :    "interesting to control flow".
    1071                 :             :    For example, consider the return value from setjmp.  We
    1072                 :             :    don't want to merge states in which the result is 0 with
    1073                 :             :    those in which the result is non-zero.  By using an
    1074                 :             :    unmergeable_svalue for the result, we can inhibit such merges
    1075                 :             :    and have separate exploded nodes for those states, keeping
    1076                 :             :    the first and second returns from setjmp distinct in the exploded
    1077                 :             :    graph.  */
    1078                 :             : 
    1079                 :             : class unmergeable_svalue : public svalue
    1080                 :             : {
    1081                 :             : public:
    1082                 :         228 :   unmergeable_svalue (symbol::id_t id, const svalue *arg)
    1083                 :         228 :   : svalue (complexity (arg), id, arg->get_type ()), m_arg (arg)
    1084                 :             :   {
    1085                 :         228 :   }
    1086                 :             : 
    1087                 :       27287 :   enum svalue_kind get_kind () const final override { return SK_UNMERGEABLE; }
    1088                 :             :   const unmergeable_svalue *
    1089                 :        5767 :   dyn_cast_unmergeable_svalue () const final override { return this; }
    1090                 :             : 
    1091                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
    1092                 :             :   void accept (visitor *v) const final override;
    1093                 :             :   bool implicitly_live_p (const svalue_set *,
    1094                 :             :                           const region_model *) const final override;
    1095                 :             : 
    1096                 :        7177 :   const svalue *get_arg () const { return m_arg; }
    1097                 :             : 
    1098                 :             :  private:
    1099                 :             :   const svalue *m_arg;
    1100                 :             : };
    1101                 :             : 
    1102                 :             : } // namespace ana
    1103                 :             : 
    1104                 :             : template <>
    1105                 :             : template <>
    1106                 :             : inline bool
    1107                 :           0 : is_a_helper <const unmergeable_svalue *>::test (const svalue *sval)
    1108                 :             : {
    1109                 :           0 :   return sval->get_kind () == SK_UNMERGEABLE;
    1110                 :             : }
    1111                 :             : 
    1112                 :             : namespace ana {
    1113                 :             : 
    1114                 :             : /* Concrete subclass of svalue for use in selftests, where
    1115                 :             :    we want a specific but unknown svalue.
    1116                 :             :    Unlike other svalue subclasses these aren't managed by
    1117                 :             :    region_model_manager.  */
    1118                 :             : 
    1119                 :          28 : class placeholder_svalue : public svalue
    1120                 :             : {
    1121                 :             : public:
    1122                 :       17222 :   placeholder_svalue (symbol::id_t id, tree type, const char *name)
    1123                 :       17222 :   : svalue (complexity (1, 1), id, type), m_name (name)
    1124                 :             :   {
    1125                 :             :   }
    1126                 :             : 
    1127                 :       38938 :   enum svalue_kind get_kind () const final override { return SK_PLACEHOLDER; }
    1128                 :             : 
    1129                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
    1130                 :             :   void accept (visitor *v) const final override;
    1131                 :             : 
    1132                 :           0 :   const char *get_name () const { return m_name; }
    1133                 :             : 
    1134                 :             :  private:
    1135                 :             :   const char *m_name;
    1136                 :             : };
    1137                 :             : 
    1138                 :             : } // namespace ana
    1139                 :             : 
    1140                 :             : template <>
    1141                 :             : template <>
    1142                 :             : inline bool
    1143                 :             : is_a_helper <const placeholder_svalue *>::test (const svalue *sval)
    1144                 :             : {
    1145                 :             :   return sval->get_kind () == SK_PLACEHOLDER;
    1146                 :             : }
    1147                 :             : 
    1148                 :             : namespace ana {
    1149                 :             : 
    1150                 :             : /* Concrete subclass of svalue representing a "widening" seen when merging
    1151                 :             :    states, widening from a base value to {base value, iter value} and thus
    1152                 :             :    representing a possible fixed point in an iteration from the base to
    1153                 :             :    +ve infinity, or -ve infinity, and thus useful for representing a value
    1154                 :             :    within a loop.
    1155                 :             :    We also need to capture the program_point at which the merger happens,
    1156                 :             :    so that distinguish between different iterators, and thus handle
    1157                 :             :    nested loops.  (currently we capture the function_point instead, for
    1158                 :             :    simplicity of hashing).  */
    1159                 :             : 
    1160                 :             : class widening_svalue : public svalue
    1161                 :             : {
    1162                 :             : public:
    1163                 :             :   /* A support class for uniquifying instances of widening_svalue.  */
    1164                 :             :   struct key_t
    1165                 :             :   {
    1166                 :        5419 :     key_t (tree type, const function_point &point,
    1167                 :             :            const svalue *base_sval, const svalue *iter_sval)
    1168                 :        5419 :     : m_type (type), m_point (point),
    1169                 :        5419 :       m_base_sval (base_sval), m_iter_sval (iter_sval)
    1170                 :             :     {}
    1171                 :             : 
    1172                 :       33816 :     hashval_t hash () const
    1173                 :             :     {
    1174                 :       33816 :       inchash::hash hstate;
    1175                 :       33816 :       hstate.add_ptr (m_base_sval);
    1176                 :       33816 :       hstate.add_ptr (m_iter_sval);
    1177                 :       33816 :       return hstate.end ();
    1178                 :             :     }
    1179                 :             : 
    1180                 :       38964 :     bool operator== (const key_t &other) const
    1181                 :             :     {
    1182                 :       38964 :       return (m_type == other.m_type
    1183                 :       21952 :               && m_point == other.m_point
    1184                 :        3707 :               && m_base_sval == other.m_base_sval
    1185                 :       41779 :               && m_iter_sval == other.m_iter_sval);
    1186                 :             :     }
    1187                 :             : 
    1188                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
    1189                 :       58363 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
    1190                 :       57871 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
    1191                 :      302157 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
    1192                 :             : 
    1193                 :             :     tree m_type;
    1194                 :             :     function_point m_point;
    1195                 :             :     const svalue *m_base_sval;
    1196                 :             :     const svalue *m_iter_sval;
    1197                 :             :   };
    1198                 :             : 
    1199                 :             :   enum direction_t
    1200                 :             :     {
    1201                 :             :      DIR_ASCENDING,
    1202                 :             :      DIR_DESCENDING,
    1203                 :             :      DIR_UNKNOWN
    1204                 :             :     };
    1205                 :             : 
    1206                 :        2766 :   widening_svalue (symbol::id_t id, tree type, const function_point &point,
    1207                 :             :                    const svalue *base_sval, const svalue *iter_sval)
    1208                 :        2766 :   : svalue (complexity::from_pair (base_sval->get_complexity (),
    1209                 :             :                                    iter_sval->get_complexity ()),
    1210                 :             :             id,
    1211                 :             :             type),
    1212                 :        2766 :     m_point (point),
    1213                 :        2766 :     m_base_sval (base_sval), m_iter_sval (iter_sval)
    1214                 :             :   {
    1215                 :        2766 :     gcc_assert (base_sval->can_have_associated_state_p ());
    1216                 :        2766 :     gcc_assert (iter_sval->can_have_associated_state_p ());
    1217                 :        2766 :   }
    1218                 :             : 
    1219                 :     1107101 :   enum svalue_kind get_kind () const final override { return SK_WIDENING; }
    1220                 :       38038 :   const widening_svalue *dyn_cast_widening_svalue () const final override
    1221                 :             :   {
    1222                 :       38038 :     return this;
    1223                 :             :   }
    1224                 :             : 
    1225                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
    1226                 :             :   void accept (visitor *v) const final override;
    1227                 :             : 
    1228                 :        5512 :   const function_point &get_point () const { return m_point; }
    1229                 :       32794 :   const svalue *get_base_svalue () const { return m_base_sval; }
    1230                 :        7869 :   const svalue *get_iter_svalue () const { return m_iter_sval; }
    1231                 :             : 
    1232                 :             :   enum direction_t get_direction () const;
    1233                 :             : 
    1234                 :             :   tristate eval_condition_without_cm (enum tree_code op,
    1235                 :             :                                       tree rhs_cst) const;
    1236                 :             : 
    1237                 :             :  private:
    1238                 :             :   function_point m_point;
    1239                 :             :   const svalue *m_base_sval;
    1240                 :             :   const svalue *m_iter_sval;
    1241                 :             : };
    1242                 :             : 
    1243                 :             : } // namespace ana
    1244                 :             : 
    1245                 :             : template <>
    1246                 :             : template <>
    1247                 :             : inline bool
    1248                 :         672 : is_a_helper <const widening_svalue *>::test (const svalue *sval)
    1249                 :             : {
    1250                 :         672 :   return sval->get_kind () == SK_WIDENING;
    1251                 :             : }
    1252                 :             : 
    1253                 :             : template <> struct default_hash_traits<widening_svalue::key_t>
    1254                 :             : : public member_function_hash_traits<widening_svalue::key_t>
    1255                 :             : {
    1256                 :             :   static const bool empty_zero_p = false;
    1257                 :             : };
    1258                 :             : 
    1259                 :             : namespace ana {
    1260                 :             : 
    1261                 :             : /* Concrete subclass of svalue representing a mapping of bit-ranges
    1262                 :             :    to svalues, analogous to a cluster within the store.
    1263                 :             : 
    1264                 :             :    This is for use in places where we want to represent a store-like
    1265                 :             :    mapping, but are required to use an svalue, such as when handling
    1266                 :             :    compound assignments and compound return values.
    1267                 :             : 
    1268                 :             :    All keys within the underlying binding_map are required to be concrete,
    1269                 :             :    not symbolic.
    1270                 :             : 
    1271                 :             :    Instances of this class shouldn't be bound as-is into the store;
    1272                 :             :    instead they should be unpacked.  Similarly, they should not be
    1273                 :             :    nested.  */
    1274                 :             : 
    1275                 :             : class compound_svalue : public svalue
    1276                 :             : {
    1277                 :             : public:
    1278                 :             :   typedef binding_map::iterator_t iterator_t;
    1279                 :             : 
    1280                 :             :   /* A support class for uniquifying instances of compound_svalue.
    1281                 :             :      Note that to avoid copies, keys store pointers to binding_maps,
    1282                 :             :      rather than the maps themselves.  */
    1283                 :             :   struct key_t
    1284                 :             :   {
    1285                 :        7944 :     key_t (tree type, const binding_map *map_ptr)
    1286                 :        7224 :     : m_type (type), m_map_ptr (map_ptr)
    1287                 :             :     {}
    1288                 :             : 
    1289                 :       38153 :     hashval_t hash () const
    1290                 :             :     {
    1291                 :       38153 :       inchash::hash hstate;
    1292                 :       38153 :       hstate.add_ptr (m_type);
    1293                 :             :       //hstate.add_ptr (m_map_ptr); // TODO
    1294                 :       38153 :       return hstate.end ();
    1295                 :             :     }
    1296                 :             : 
    1297                 :       39828 :     bool operator== (const key_t &other) const
    1298                 :             :     {
    1299                 :       39828 :       return (m_type == other.m_type
    1300                 :       39828 :               && *m_map_ptr == *other.m_map_ptr);
    1301                 :             :     }
    1302                 :             : 
    1303                 :             :     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
    1304                 :       56240 :     void mark_empty () { m_type = reinterpret_cast<tree> (2); }
    1305                 :       66249 :     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
    1306                 :      303576 :     bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
    1307                 :             : 
    1308                 :             :     tree m_type;
    1309                 :             :     const binding_map *m_map_ptr;
    1310                 :             :   };
    1311                 :             : 
    1312                 :             :   compound_svalue (symbol::id_t id, tree type, const binding_map &map);
    1313                 :             : 
    1314                 :       13862 :   enum svalue_kind get_kind () const final override { return SK_COMPOUND; }
    1315                 :        7325 :   const compound_svalue *dyn_cast_compound_svalue () const final override
    1316                 :             :   {
    1317                 :        7325 :     return this;
    1318                 :             :   }
    1319                 :             : 
    1320                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
    1321                 :             :   void accept (visitor *v) const final override;
    1322                 :             : 
    1323                 :         726 :   const binding_map &get_map () const { return m_map; }
    1324                 :             : 
    1325                 :        8360 :   iterator_t begin () const { return m_map.begin (); }
    1326                 :       32949 :   iterator_t end () const { return m_map.end (); }
    1327                 :             : 
    1328                 :         720 :   struct key_t make_key () const
    1329                 :             :   {
    1330                 :         720 :     return key_t (get_type (), &m_map);
    1331                 :             :   }
    1332                 :             : 
    1333                 :             :   const svalue *
    1334                 :             :   maybe_fold_bits_within (tree type,
    1335                 :             :                           const bit_range &subrange,
    1336                 :             :                           region_model_manager *mgr) const final override;
    1337                 :             : 
    1338                 :             :  private:
    1339                 :             :   static complexity calc_complexity (const binding_map &map);
    1340                 :             : 
    1341                 :             :   binding_map m_map;
    1342                 :             : };
    1343                 :             : 
    1344                 :             : } // namespace ana
    1345                 :             : 
    1346                 :             : template <>
    1347                 :             : template <>
    1348                 :             : inline bool
    1349                 :         378 : is_a_helper <const compound_svalue *>::test (const svalue *sval)
    1350                 :             : {
    1351                 :         378 :   return sval->get_kind () == SK_COMPOUND;
    1352                 :             : }
    1353                 :             : 
    1354                 :             : template <> struct default_hash_traits<compound_svalue::key_t>
    1355                 :             : : public member_function_hash_traits<compound_svalue::key_t>
    1356                 :             : {
    1357                 :             :   static const bool empty_zero_p = false;
    1358                 :             : };
    1359                 :             : 
    1360                 :             : namespace ana {
    1361                 :             : 
    1362                 :             : /* A bundle of state for purging information from a program_state about
    1363                 :             :    a conjured_svalue.  We pass this whenever calling
    1364                 :             :    get_or_create_conjured_svalue, so that if the program_state already
    1365                 :             :    has information about this conjured_svalue on an execution path, we
    1366                 :             :    can purge that information, to avoid the analyzer confusing the two
    1367                 :             :    values as being the same.  */
    1368                 :             : 
    1369                 :             : class conjured_purge
    1370                 :             : {
    1371                 :             : public:
    1372                 :       46478 :   conjured_purge (region_model *model, region_model_context *ctxt)
    1373                 :       46311 :   : m_model (model), m_ctxt (ctxt)
    1374                 :             :   {
    1375                 :             :   }
    1376                 :             :   void purge (const conjured_svalue *sval) const;
    1377                 :             : 
    1378                 :             : private:
    1379                 :             :   region_model *m_model;
    1380                 :             :   region_model_context *m_ctxt;
    1381                 :             : };
    1382                 :             : 
    1383                 :             : /* A defined value arising from a statement, where we want to identify a
    1384                 :             :    particular unknown value, rather than resorting to the unknown_value
    1385                 :             :    singleton, so that the value can have sm-state.
    1386                 :             : 
    1387                 :             :    Comparisons of variables that share the same conjured_svalue are known
    1388                 :             :    to be equal, even if we don't know what the value is.
    1389                 :             : 
    1390                 :             :    For example, this is used for the values of regions that may have been
    1391                 :             :    touched when calling an unknown function.
    1392                 :             : 
    1393                 :             :    The value captures a region as well as a stmt in order to avoid falsely
    1394                 :             :    aliasing the various values that could arise in one statement.  For
    1395                 :             :    example, after:
    1396                 :             :       unknown_fn (&a, &b);
    1397                 :             :    we want values to clobber a and b with, but we don't want to use the
    1398                 :             :    same value, or it would falsely implicitly assume that a == b.  */
    1399                 :             : 
    1400                 :             : class conjured_svalue : public svalue
    1401                 :             : {
    1402                 :             : public:
    1403                 :             :   /* A support class for uniquifying instances of conjured_svalue.  */
    1404                 :             :   struct key_t
    1405                 :             :   {
    1406                 :       56016 :     key_t (tree type, const gimple *stmt, const region *id_reg, unsigned idx)
    1407                 :       56016 :     : m_type (type), m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
    1408                 :             :     {}
    1409                 :             : 
    1410                 :      415929 :     hashval_t hash () const
    1411                 :             :     {
    1412                 :      415929 :       inchash::hash hstate;
    1413                 :      415929 :       hstate.add_ptr (m_type);
    1414                 :      415929 :       hstate.add_ptr (m_stmt);
    1415                 :      415929 :       hstate.add_ptr (m_id_reg);
    1416                 :      415929 :       return hstate.end ();
    1417                 :             :     }
    1418                 :             : 
    1419                 :      409055 :     bool operator== (const key_t &other) const
    1420                 :             :     {
    1421                 :      409055 :       return (m_type == other.m_type
    1422                 :      156579 :               && m_stmt == other.m_stmt
    1423                 :       54737 :               && m_id_reg == other.m_id_reg
    1424                 :      449075 :               && m_idx == other.m_idx);
    1425                 :             :     }
    1426                 :             : 
    1427                 :             :     /* Use m_stmt to mark empty/deleted, as m_type can be NULL for
    1428                 :             :        legitimate instances.  */
    1429                 :             :     void mark_deleted () { m_stmt = reinterpret_cast<const gimple *> (1); }
    1430                 :           0 :     void mark_empty () { m_stmt = NULL; }
    1431                 :      465078 :     bool is_deleted () const
    1432                 :             :     {
    1433                 :      465078 :       return m_stmt == reinterpret_cast<const gimple *> (1);
    1434                 :             :     }
    1435                 :     1582304 :     bool is_empty () const { return m_stmt == NULL; }
    1436                 :             : 
    1437                 :             :     tree m_type;
    1438                 :             :     const gimple *m_stmt;
    1439                 :             :     const region *m_id_reg;
    1440                 :             :     unsigned m_idx;
    1441                 :             :   };
    1442                 :             : 
    1443                 :       16297 :   conjured_svalue (symbol::id_t id, tree type, const gimple *stmt,
    1444                 :             :                    const region *id_reg, unsigned idx)
    1445                 :       16297 :   : svalue (complexity (id_reg), id, type),
    1446                 :       16297 :     m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
    1447                 :             :   {
    1448                 :       16297 :     gcc_assert (m_stmt != NULL);
    1449                 :       16297 :   }
    1450                 :             : 
    1451                 :     8146417 :   enum svalue_kind get_kind () const final override { return SK_CONJURED; }
    1452                 :           0 :   const conjured_svalue *dyn_cast_conjured_svalue () const final override
    1453                 :             :   {
    1454                 :           0 :     return this;
    1455                 :             :   }
    1456                 :             : 
    1457                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
    1458                 :             :   void accept (visitor *v) const final override;
    1459                 :             : 
    1460                 :      253695 :   const gimple *get_stmt () const { return m_stmt; }
    1461                 :      145390 :   const region *get_id_region () const { return m_id_reg; }
    1462                 :             :   bool lhs_value_p () const;
    1463                 :             : 
    1464                 :             :  private:
    1465                 :             :   const gimple *m_stmt;
    1466                 :             :   const region *m_id_reg;
    1467                 :             :   unsigned m_idx;
    1468                 :             : };
    1469                 :             : 
    1470                 :             : } // namespace ana
    1471                 :             : 
    1472                 :             : template <>
    1473                 :             : template <>
    1474                 :             : inline bool
    1475                 :             : is_a_helper <const conjured_svalue *>::test (const svalue *sval)
    1476                 :             : {
    1477                 :             :   return sval->get_kind () == SK_CONJURED;
    1478                 :             : }
    1479                 :             : 
    1480                 :             : template <> struct default_hash_traits<conjured_svalue::key_t>
    1481                 :             : : public member_function_hash_traits<conjured_svalue::key_t>
    1482                 :             : {
    1483                 :             :   static const bool empty_zero_p = true;
    1484                 :             : };
    1485                 :             : 
    1486                 :             : namespace ana {
    1487                 :             : 
    1488                 :             : /* An output from a deterministic asm stmt, where we want to identify a
    1489                 :             :    particular unknown value, rather than resorting to the unknown_value
    1490                 :             :    singleton.
    1491                 :             : 
    1492                 :             :    Comparisons of variables that share the same asm_output_svalue are known
    1493                 :             :    to be equal, even if we don't know what the value is.  */
    1494                 :             : 
    1495                 :             : class asm_output_svalue : public svalue
    1496                 :             : {
    1497                 :             : public:
    1498                 :             :   /* Imposing an upper limit and using a (small) array allows key_t
    1499                 :             :      to avoid memory management.  */
    1500                 :             :   static const unsigned MAX_INPUTS = 2;
    1501                 :             : 
    1502                 :             :   /* A support class for uniquifying instances of asm_output_svalue.  */
    1503                 :             :   struct key_t
    1504                 :             :   {
    1505                 :         408 :     key_t (tree type,
    1506                 :             :            const char *asm_string,
    1507                 :             :            unsigned output_idx,
    1508                 :             :            const vec<const svalue *> &inputs)
    1509                 :         408 :     : m_type (type), m_asm_string (asm_string), m_output_idx (output_idx),
    1510                 :         408 :       m_num_inputs (inputs.length ())
    1511                 :             :     {
    1512                 :         408 :       gcc_assert (inputs.length () <= MAX_INPUTS);
    1513                 :        1090 :       for (unsigned i = 0; i < m_num_inputs; i++)
    1514                 :         682 :         m_input_arr[i] = inputs[i];
    1515                 :         408 :     }
    1516                 :             : 
    1517                 :        1647 :     hashval_t hash () const
    1518                 :             :     {
    1519                 :        1647 :       inchash::hash hstate;
    1520                 :        1647 :       hstate.add_ptr (m_type);
    1521                 :             :       /* We don't bother hashing m_asm_str.  */
    1522                 :        1647 :       hstate.add_int (m_output_idx);
    1523                 :        4516 :       for (unsigned i = 0; i < m_num_inputs; i++)
    1524                 :        2869 :         hstate.add_ptr (m_input_arr[i]);
    1525                 :        1647 :       return hstate.end ();
    1526                 :             :     }
    1527                 :             : 
    1528                 :        1218 :     bool operator== (const key_t &other) const
    1529                 :             :     {
    1530                 :        2075 :       if (!(m_type == other.m_type
    1531                 :         930 :             && 0 == (strcmp (m_asm_string, other.m_asm_string))
    1532                 :             :             && m_output_idx == other.m_output_idx
    1533                 :             :             && m_num_inputs == other.m_num_inputs))
    1534                 :             :         return false;
    1535                 :        1279 :       for (unsigned i = 0; i < m_num_inputs; i++)
    1536                 :        1072 :         if (m_input_arr[i] != other.m_input_arr[i])
    1537                 :             :           return false;
    1538                 :             :       return true;
    1539                 :             :     }
    1540                 :             : 
    1541                 :             :     /* Use m_asm_string to mark empty/deleted, as m_type can be NULL for
    1542                 :             :        legitimate instances.  */
    1543                 :             :     void mark_deleted () { m_asm_string = reinterpret_cast<const char *> (1); }
    1544                 :           0 :     void mark_empty () { m_asm_string = NULL; }
    1545                 :        1755 :     bool is_deleted () const
    1546                 :             :     {
    1547                 :        1755 :       return m_asm_string == reinterpret_cast<const char *> (1);
    1548                 :             :     }
    1549                 :      121204 :     bool is_empty () const { return m_asm_string == NULL; }
    1550                 :             : 
    1551                 :             :     tree m_type;
    1552                 :             :     const char *m_asm_string;
    1553                 :             :     unsigned m_output_idx;
    1554                 :             :     unsigned m_num_inputs;
    1555                 :             :     const svalue *m_input_arr[MAX_INPUTS];
    1556                 :             :   };
    1557                 :             : 
    1558                 :         201 :   asm_output_svalue (symbol::id_t id,
    1559                 :             :                      tree type,
    1560                 :             :                      const char *asm_string,
    1561                 :             :                      unsigned output_idx,
    1562                 :             :                      unsigned num_outputs,
    1563                 :             :                      const vec<const svalue *> &inputs)
    1564                 :         201 :   : svalue (complexity::from_vec_svalue (inputs), id, type),
    1565                 :         201 :     m_asm_string (asm_string),
    1566                 :         201 :     m_output_idx (output_idx),
    1567                 :         201 :     m_num_outputs (num_outputs),
    1568                 :         201 :     m_num_inputs (inputs.length ())
    1569                 :             :   {
    1570                 :         201 :     gcc_assert (inputs.length () <= MAX_INPUTS);
    1571                 :         504 :     for (unsigned i = 0; i < m_num_inputs; i++)
    1572                 :         303 :       m_input_arr[i] = inputs[i];
    1573                 :         201 :   }
    1574                 :             : 
    1575                 :       11730 :   enum svalue_kind get_kind () const final override { return SK_ASM_OUTPUT; }
    1576                 :             :   const asm_output_svalue *
    1577                 :           0 :   dyn_cast_asm_output_svalue () const final override
    1578                 :             :   {
    1579                 :           0 :     return this;
    1580                 :             :   }
    1581                 :             : 
    1582                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
    1583                 :             :   void accept (visitor *v) const final override;
    1584                 :             : 
    1585                 :         128 :   const char *get_asm_string () const { return m_asm_string; }
    1586                 :         204 :   unsigned get_output_idx () const { return m_output_idx; }
    1587                 :         104 :   unsigned get_num_outputs () const { return m_num_outputs; }
    1588                 :         410 :   unsigned get_num_inputs () const { return m_num_inputs; }
    1589                 :         212 :   const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
    1590                 :             : 
    1591                 :             :  private:
    1592                 :             :   void dump_input (pretty_printer *pp,
    1593                 :             :                    unsigned input_idx,
    1594                 :             :                    const svalue *sval,
    1595                 :             :                    bool simple) const;
    1596                 :             :   unsigned input_idx_to_asm_idx (unsigned input_idx) const;
    1597                 :             : 
    1598                 :             :   const char *m_asm_string;
    1599                 :             :   unsigned m_output_idx;
    1600                 :             : 
    1601                 :             :   /* We capture this so that we can offset the input indices
    1602                 :             :      to match the %0, %1, %2 in the asm_string when dumping.  */
    1603                 :             :   unsigned m_num_outputs;
    1604                 :             : 
    1605                 :             :   unsigned m_num_inputs;
    1606                 :             :   const svalue *m_input_arr[MAX_INPUTS];
    1607                 :             : };
    1608                 :             : 
    1609                 :             : } // namespace ana
    1610                 :             : 
    1611                 :             : template <>
    1612                 :             : template <>
    1613                 :             : inline bool
    1614                 :          10 : is_a_helper <const asm_output_svalue *>::test (const svalue *sval)
    1615                 :             : {
    1616                 :          10 :   return sval->get_kind () == SK_ASM_OUTPUT;
    1617                 :             : }
    1618                 :             : 
    1619                 :             : template <> struct default_hash_traits<asm_output_svalue::key_t>
    1620                 :             : : public member_function_hash_traits<asm_output_svalue::key_t>
    1621                 :             : {
    1622                 :             :   static const bool empty_zero_p = true;
    1623                 :             : };
    1624                 :             : 
    1625                 :             : namespace ana {
    1626                 :             : 
    1627                 :             : /* The return value from a function with __attribute((const)) for given
    1628                 :             :    inputs, provided that we don't have too many inputs, and all of them
    1629                 :             :    are deterministic.
    1630                 :             : 
    1631                 :             :    Comparisons of variables that share the same const_fn_result_svalue are known
    1632                 :             :    to be equal, even if we don't know what the value is.  */
    1633                 :             : 
    1634                 :             : class const_fn_result_svalue : public svalue
    1635                 :             : {
    1636                 :             : public:
    1637                 :             :   /* Imposing an upper limit and using a (small) array allows key_t
    1638                 :             :      to avoid memory management.  */
    1639                 :             :   static const unsigned MAX_INPUTS = 2;
    1640                 :             : 
    1641                 :             :   /* A support class for uniquifying instances of const_fn_result_svalue.  */
    1642                 :             :   struct key_t
    1643                 :             :   {
    1644                 :        1347 :     key_t (tree type,
    1645                 :             :            tree fndecl,
    1646                 :             :            const vec<const svalue *> &inputs)
    1647                 :        1347 :     : m_type (type), m_fndecl (fndecl),
    1648                 :        1347 :       m_num_inputs (inputs.length ())
    1649                 :             :     {
    1650                 :        1347 :       gcc_assert (inputs.length () <= MAX_INPUTS);
    1651                 :        2089 :       for (unsigned i = 0; i < m_num_inputs; i++)
    1652                 :         742 :         m_input_arr[i] = inputs[i];
    1653                 :        1347 :     }
    1654                 :             : 
    1655                 :        4753 :     hashval_t hash () const
    1656                 :             :     {
    1657                 :        4753 :       inchash::hash hstate;
    1658                 :        4753 :       hstate.add_ptr (m_type);
    1659                 :        4753 :       hstate.add_ptr (m_fndecl);
    1660                 :        8435 :       for (unsigned i = 0; i < m_num_inputs; i++)
    1661                 :        3682 :         hstate.add_ptr (m_input_arr[i]);
    1662                 :        4753 :       return hstate.end ();
    1663                 :             :     }
    1664                 :             : 
    1665                 :        3463 :     bool operator== (const key_t &other) const
    1666                 :             :     {
    1667                 :        3463 :       if (!(m_type == other.m_type
    1668                 :        3404 :             && m_fndecl == other.m_fndecl
    1669                 :        1998 :             && m_num_inputs == other.m_num_inputs))
    1670                 :             :         return false;
    1671                 :        2619 :       for (unsigned i = 0; i < m_num_inputs; i++)
    1672                 :        1565 :         if (m_input_arr[i] != other.m_input_arr[i])
    1673                 :             :           return false;
    1674                 :             :       return true;
    1675                 :             :     }
    1676                 :             : 
    1677                 :             :     /* Use m_fndecl to mark empty/deleted.  */
    1678                 :             :     void mark_deleted () { m_fndecl = reinterpret_cast<tree> (1); }
    1679                 :           0 :     void mark_empty () { m_fndecl = NULL; }
    1680                 :        5042 :     bool is_deleted () const
    1681                 :             :     {
    1682                 :        5042 :       return m_fndecl == reinterpret_cast<tree> (1);
    1683                 :             :     }
    1684                 :      137705 :     bool is_empty () const { return m_fndecl == NULL; }
    1685                 :             : 
    1686                 :             :     tree m_type;
    1687                 :             :     tree m_fndecl;
    1688                 :             :     unsigned m_num_inputs;
    1689                 :             :     const svalue *m_input_arr[MAX_INPUTS];
    1690                 :             :   };
    1691                 :             : 
    1692                 :         293 :   const_fn_result_svalue (symbol::id_t id,
    1693                 :             :                           tree type,
    1694                 :             :                           tree fndecl,
    1695                 :             :                           const vec<const svalue *> &inputs)
    1696                 :         293 :   : svalue (complexity::from_vec_svalue (inputs), id, type),
    1697                 :         293 :     m_fndecl (fndecl),
    1698                 :         293 :     m_num_inputs (inputs.length ())
    1699                 :             :   {
    1700                 :         293 :     gcc_assert (inputs.length () <= MAX_INPUTS);
    1701                 :         580 :     for (unsigned i = 0; i < m_num_inputs; i++)
    1702                 :         287 :       m_input_arr[i] = inputs[i];
    1703                 :         293 :   }
    1704                 :             : 
    1705                 :       60434 :   enum svalue_kind get_kind () const final override
    1706                 :             :   {
    1707                 :       60434 :     return SK_CONST_FN_RESULT;
    1708                 :             :   }
    1709                 :             :   const const_fn_result_svalue *
    1710                 :           0 :   dyn_cast_const_fn_result_svalue () const final override
    1711                 :             :   {
    1712                 :           0 :     return this;
    1713                 :             :   }
    1714                 :             : 
    1715                 :             :   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
    1716                 :             :   void accept (visitor *v) const final override;
    1717                 :             : 
    1718                 :         122 :   tree get_fndecl () const { return m_fndecl; }
    1719                 :         142 :   unsigned get_num_inputs () const { return m_num_inputs; }
    1720                 :          82 :   const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
    1721                 :             : 
    1722                 :             :  private:
    1723                 :             :   void dump_input (pretty_printer *pp,
    1724                 :             :                    unsigned input_idx,
    1725                 :             :                    const svalue *sval,
    1726                 :             :                    bool simple) const;
    1727                 :             : 
    1728                 :             :   tree m_fndecl;
    1729                 :             :   unsigned m_num_inputs;
    1730                 :             :   const svalue *m_input_arr[MAX_INPUTS];
    1731                 :             : };
    1732                 :             : 
    1733                 :             : } // namespace ana
    1734                 :             : 
    1735                 :             : template <>
    1736                 :             : template <>
    1737                 :             : inline bool
    1738                 :           2 : is_a_helper <const const_fn_result_svalue *>::test (const svalue *sval)
    1739                 :             : {
    1740                 :           2 :   return sval->get_kind () == SK_CONST_FN_RESULT;
    1741                 :             : }
    1742                 :             : 
    1743                 :             : template <> struct default_hash_traits<const_fn_result_svalue::key_t>
    1744                 :             : : public member_function_hash_traits<const_fn_result_svalue::key_t>
    1745                 :             : {
    1746                 :             :   static const bool empty_zero_p = true;
    1747                 :             : };
    1748                 :             : 
    1749                 :             : #endif /* GCC_ANALYZER_SVALUE_H */
        

Generated by: LCOV version 2.0-1

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