gcc/analyzer/svalue.h

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