gcc/analyzer/svalue.h

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