gcc/analyzer/svalue.h

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