gcc/analyzer/svalue.h

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