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