gcc/analyzer/region-model.h

   1 /* Classes for modeling the state of memory.
   2    Copyright (C) 2019-2022 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #ifndef GCC_ANALYZER_REGION_MODEL_H
  22 #define GCC_ANALYZER_REGION_MODEL_H
  23
  24 /* Implementation of the region-based ternary model described in:
  25      "A Memory Model for Static Analysis of C Programs"
  26       (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
  27      http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf  */
  28
  29 #include "analyzer/svalue.h"
  30 #include "analyzer/region.h"
  31
  32 using namespace ana;
  33
  34 namespace inchash
  35 {
  36   extern void add_path_var (path_var pv, hash &hstate);
  37 } // namespace inchash
  38
  39 namespace ana {
  40
  41 template <typename T>
  42 class one_way_id_map
  43 {
  44  public:
  45   one_way_id_map (int num_ids);
  46   void put (T src, T dst);
  47   T get_dst_for_src (T src) const;
  48   void dump_to_pp (pretty_printer *pp) const;
  49   void dump () const;
  50   void update (T *) const;
  51
  52  private:
  53   auto_vec<T> m_src_to_dst;
  54  };
  55
  56 /* class one_way_id_map.  */
  57
  58 /* one_way_id_map's ctor, which populates the map with dummy null values.  */
  59
  60 template <typename T>
  61 inline one_way_id_map<T>::one_way_id_map (int num_svalues)
  62 : m_src_to_dst (num_svalues)
  63 {
  64   for (int i = 0; i < num_svalues; i++)
  65     m_src_to_dst.quick_push (T::null ());
  66 }
  67
  68 /* Record that SRC is to be mapped to DST.  */
  69
  70 template <typename T>
  71 inline void
  72 one_way_id_map<T>::put (T src, T dst)
  73 {
  74   m_src_to_dst[src.as_int ()] = dst;
  75 }
  76
  77 /* Get the new value for SRC within the map.  */
  78
  79 template <typename T>
  80 inline T
  81 one_way_id_map<T>::get_dst_for_src (T src) const
  82 {
  83   if (src.null_p ())
  84     return src;
  85   return m_src_to_dst[src.as_int ()];
  86 }
  87
  88 /* Dump this map to PP.  */
  89
  90 template <typename T>
  91 inline void
  92 one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
  93 {
  94   pp_string (pp, "src to dst: {");
  95   unsigned i;
  96   T *dst;
  97   FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
  98     {
  99       if (i > 0)
 100         pp_string (pp, ", ");
 101       T src (T::from_int (i));
 102       src.print (pp);
 103       pp_string (pp, " -> ");
 104       dst->print (pp);
 105     }
 106   pp_string (pp, "}");
 107   pp_newline (pp);
 108 }
 109
 110 /* Dump this map to stderr.  */
 111
 112 template <typename T>
 113 DEBUG_FUNCTION inline void
 114 one_way_id_map<T>::dump () const
 115 {
 116   pretty_printer pp;
 117   pp.buffer->stream = stderr;
 118   dump_to_pp (&pp);
 119   pp_flush (&pp);
 120 }
 121
 122 /* Update *ID from the old value to its new value in this map.  */
 123
 124 template <typename T>
 125 inline void
 126 one_way_id_map<T>::update (T *id) const
 127 {
 128   *id = get_dst_for_src (*id);
 129 }
 130
 131 /* A mapping from region to svalue for use when tracking state.  */
 132
 133 class region_to_value_map
 134 {
 135 public:
 136   typedef hash_map<const region *, const svalue *> hash_map_t;
 137   typedef hash_map_t::iterator iterator;
 138
 139   region_to_value_map () : m_hash_map () {}
 140   region_to_value_map (const region_to_value_map &other)
 141   : m_hash_map (other.m_hash_map) {}
 142   region_to_value_map &operator= (const region_to_value_map &other);
 143
 144   bool operator== (const region_to_value_map &other) const;
 145   bool operator!= (const region_to_value_map &other) const
 146   {
 147     return !(*this == other);
 148   }
 149
 150   iterator begin () const { return m_hash_map.begin (); }
 151   iterator end () const { return m_hash_map.end (); }
 152
 153   const svalue * const *get (const region *reg) const
 154   {
 155     return const_cast <hash_map_t &> (m_hash_map).get (reg);
 156   }
 157   void put (const region *reg, const svalue *sval)
 158   {
 159     m_hash_map.put (reg, sval);
 160   }
 161   void remove (const region *reg)
 162   {
 163     m_hash_map.remove (reg);
 164   }
 165
 166   bool is_empty () const { return m_hash_map.is_empty (); }
 167
 168   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 169   void dump (bool simple) const;
 170
 171   bool can_merge_with_p (const region_to_value_map &other,
 172                          region_to_value_map *out) const;
 173
 174   void purge_state_involving (const svalue *sval);
 175
 176 private:
 177   hash_map_t m_hash_map;
 178 };
 179
 180 /* Various operations delete information from a region_model.
 181
 182    This struct tracks how many of each kind of entity were purged (e.g.
 183    for selftests, and for debugging).  */
 184
 185 struct purge_stats
 186 {
 187   purge_stats ()
 188   : m_num_svalues (0),
 189     m_num_regions (0),
 190     m_num_equiv_classes (0),
 191     m_num_constraints (0),
 192     m_num_bounded_ranges_constraints (0),
 193     m_num_client_items (0)
 194   {}
 195
 196   int m_num_svalues;
 197   int m_num_regions;
 198   int m_num_equiv_classes;
 199   int m_num_constraints;
 200   int m_num_bounded_ranges_constraints;
 201   int m_num_client_items;
 202 };
 203
 204 /* A base class for visiting regions and svalues, with do-nothing
 205    base implementations of the per-subclass vfuncs.  */
 206
 207 class visitor
 208 {
 209 public:
 210   virtual void visit_region_svalue (const region_svalue *) {}
 211   virtual void visit_constant_svalue (const constant_svalue *) {}
 212   virtual void visit_unknown_svalue (const unknown_svalue *) {}
 213   virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
 214   virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
 215   virtual void visit_initial_svalue (const initial_svalue *) {}
 216   virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
 217   virtual void visit_binop_svalue (const binop_svalue *) {}
 218   virtual void visit_sub_svalue (const sub_svalue *) {}
 219   virtual void visit_repeated_svalue (const repeated_svalue *) {}
 220   virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
 221   virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
 222   virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
 223   virtual void visit_widening_svalue (const widening_svalue *) {}
 224   virtual void visit_compound_svalue (const compound_svalue *) {}
 225   virtual void visit_conjured_svalue (const conjured_svalue *) {}
 226   virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
 227   virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
 228
 229   virtual void visit_region (const region *) {}
 230 };
 231
 232 } // namespace ana
 233
 234 namespace ana {
 235
 236 /* A class responsible for owning and consolidating region and svalue
 237    instances.
 238    region and svalue instances are immutable as far as clients are
 239    concerned, so they are provided as "const" ptrs.  */
 240
 241 class region_model_manager
 242 {
 243 public:
 244   region_model_manager (logger *logger = NULL);
 245   ~region_model_manager ();
 246
 247   /* call_string consolidation.  */
 248   const call_string &get_empty_call_string () const
 249   {
 250     return m_empty_call_string;
 251   }
 252
 253   /* svalue consolidation.  */
 254   const svalue *get_or_create_constant_svalue (tree cst_expr);
 255   const svalue *get_or_create_int_cst (tree type, poly_int64);
 256   const svalue *get_or_create_unknown_svalue (tree type);
 257   const svalue *get_or_create_setjmp_svalue (const setjmp_record &r,
 258                                              tree type);
 259   const svalue *get_or_create_poisoned_svalue (enum poison_kind kind,
 260                                                tree type);
 261   const svalue *get_or_create_initial_value (const region *reg);
 262   const svalue *get_ptr_svalue (tree ptr_type, const region *pointee);
 263   const svalue *get_or_create_unaryop (tree type, enum tree_code op,
 264                                        const svalue *arg);
 265   const svalue *get_or_create_cast (tree type, const svalue *arg);
 266   const svalue *get_or_create_binop (tree type,
 267                                      enum tree_code op,
 268                                      const svalue *arg0, const svalue *arg1);
 269   const svalue *get_or_create_sub_svalue (tree type,
 270                                           const svalue *parent_svalue,
 271                                           const region *subregion);
 272   const svalue *get_or_create_repeated_svalue (tree type,
 273                                                const svalue *outer_size,
 274                                                const svalue *inner_svalue);
 275   const svalue *get_or_create_bits_within (tree type,
 276                                            const bit_range &bits,
 277                                            const svalue *inner_svalue);
 278   const svalue *get_or_create_unmergeable (const svalue *arg);
 279   const svalue *get_or_create_widening_svalue (tree type,
 280                                                const program_point &point,
 281                                                const svalue *base_svalue,
 282                                                const svalue *iter_svalue);
 283   const svalue *get_or_create_compound_svalue (tree type,
 284                                                const binding_map &map);
 285   const svalue *get_or_create_conjured_svalue (tree type, const gimple *stmt,
 286                                                const region *id_reg,
 287                                                const conjured_purge &p);
 288   const svalue *
 289   get_or_create_asm_output_svalue (tree type,
 290                                    const gasm *asm_stmt,
 291                                    unsigned output_idx,
 292                                    const vec<const svalue *> &inputs);
 293   const svalue *
 294   get_or_create_const_fn_result_svalue (tree type,
 295                                         tree fndecl,
 296                                         const vec<const svalue *> &inputs);
 297
 298   const svalue *maybe_get_char_from_string_cst (tree string_cst,
 299                                                 tree byte_offset_cst);
 300
 301   /* Dynamically-allocated svalue instances.
 302      The number of these within the analysis can grow arbitrarily.
 303      They are still owned by the manager.  */
 304   const svalue *create_unique_svalue (tree type);
 305
 306   /* region consolidation.  */
 307   const stack_region * get_stack_region () const { return &m_stack_region; }
 308   const heap_region *get_heap_region () const { return &m_heap_region; }
 309   const code_region *get_code_region () const { return &m_code_region; }
 310   const globals_region *get_globals_region () const
 311   {
 312     return &m_globals_region;
 313   }
 314   const function_region *get_region_for_fndecl (tree fndecl);
 315   const label_region *get_region_for_label (tree label);
 316   const decl_region *get_region_for_global (tree expr);
 317   const region *get_field_region (const region *parent, tree field);
 318   const region *get_element_region (const region *parent,
 319                                     tree element_type,
 320                                     const svalue *index);
 321   const region *get_offset_region (const region *parent,
 322                                    tree type,
 323                                    const svalue *byte_offset);
 324   const region *get_sized_region (const region *parent,
 325                                   tree type,
 326                                   const svalue *byte_size_sval);
 327   const region *get_cast_region (const region *original_region,
 328                                  tree type);
 329   const frame_region *get_frame_region (const frame_region *calling_frame,
 330                                         function *fun);
 331   const region *get_symbolic_region (const svalue *sval);
 332   const string_region *get_region_for_string (tree string_cst);
 333   const region *get_bit_range (const region *parent, tree type,
 334                                const bit_range &bits);
 335   const var_arg_region *get_var_arg_region (const frame_region *parent,
 336                                             unsigned idx);
 337
 338   const region *get_unknown_symbolic_region (tree region_type);
 339
 340   const region *
 341   get_region_for_unexpected_tree_code (region_model_context *ctxt,
 342                                        tree t,
 343                                        const dump_location_t &loc);
 344
 345   unsigned alloc_region_id () { return m_next_region_id++; }
 346
 347   store_manager *get_store_manager () { return &m_store_mgr; }
 348   bounded_ranges_manager *get_range_manager () const { return m_range_mgr; }
 349
 350   /* Dynamically-allocated region instances.
 351      The number of these within the analysis can grow arbitrarily.
 352      They are still owned by the manager.  */
 353   const region *create_region_for_heap_alloc ();
 354   const region *create_region_for_alloca (const frame_region *frame);
 355
 356   void log_stats (logger *logger, bool show_objs) const;
 357
 358   void begin_checking_feasibility (void) { m_checking_feasibility = true; }
 359   void end_checking_feasibility (void) { m_checking_feasibility = false; }
 360
 361   logger *get_logger () const { return m_logger; }
 362
 363   void dump_untracked_regions () const;
 364
 365 private:
 366   bool too_complex_p (const complexity &c) const;
 367   bool reject_if_too_complex (svalue *sval);
 368
 369   const svalue *maybe_fold_unaryop (tree type, enum tree_code op,
 370                                     const svalue *arg);
 371   const svalue *maybe_fold_binop (tree type, enum tree_code op,
 372                                   const svalue *arg0, const svalue *arg1);
 373   const svalue *maybe_fold_sub_svalue (tree type,
 374                                        const svalue *parent_svalue,
 375                                        const region *subregion);
 376   const svalue *maybe_fold_repeated_svalue (tree type,
 377                                             const svalue *outer_size,
 378                                             const svalue *inner_svalue);
 379   const svalue *maybe_fold_bits_within_svalue (tree type,
 380                                                const bit_range &bits,
 381                                                const svalue *inner_svalue);
 382   const svalue *maybe_undo_optimize_bit_field_compare (tree type,
 383                                                        const compound_svalue *compound_sval,
 384                                                        tree cst, const svalue *arg1);
 385   const svalue *maybe_fold_asm_output_svalue (tree type,
 386                                               const vec<const svalue *> &inputs);
 387
 388   logger *m_logger;
 389
 390   const call_string m_empty_call_string;
 391
 392   unsigned m_next_region_id;
 393   root_region m_root_region;
 394   stack_region m_stack_region;
 395   heap_region m_heap_region;
 396
 397   /* svalue consolidation.  */
 398   typedef hash_map<tree, constant_svalue *> constants_map_t;
 399   constants_map_t m_constants_map;
 400
 401   typedef hash_map<tree, unknown_svalue *> unknowns_map_t;
 402   unknowns_map_t m_unknowns_map;
 403   const unknown_svalue *m_unknown_NULL;
 404
 405   typedef hash_map<poisoned_svalue::key_t,
 406                    poisoned_svalue *> poisoned_values_map_t;
 407   poisoned_values_map_t m_poisoned_values_map;
 408
 409   typedef hash_map<setjmp_svalue::key_t,
 410                    setjmp_svalue *> setjmp_values_map_t;
 411   setjmp_values_map_t m_setjmp_values_map;
 412
 413   typedef hash_map<const region *, initial_svalue *> initial_values_map_t;
 414   initial_values_map_t m_initial_values_map;
 415
 416   typedef hash_map<region_svalue::key_t, region_svalue *> pointer_values_map_t;
 417   pointer_values_map_t m_pointer_values_map;
 418
 419   typedef hash_map<unaryop_svalue::key_t,
 420                    unaryop_svalue *> unaryop_values_map_t;
 421   unaryop_values_map_t m_unaryop_values_map;
 422
 423   typedef hash_map<binop_svalue::key_t, binop_svalue *> binop_values_map_t;
 424   binop_values_map_t m_binop_values_map;
 425
 426   typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t;
 427   sub_values_map_t m_sub_values_map;
 428
 429   typedef hash_map<repeated_svalue::key_t,
 430                    repeated_svalue *> repeated_values_map_t;
 431   repeated_values_map_t m_repeated_values_map;
 432
 433   typedef hash_map<bits_within_svalue::key_t,
 434                    bits_within_svalue *> bits_within_values_map_t;
 435   bits_within_values_map_t m_bits_within_values_map;
 436
 437   typedef hash_map<const svalue *,
 438                    unmergeable_svalue *> unmergeable_values_map_t;
 439   unmergeable_values_map_t m_unmergeable_values_map;
 440
 441   typedef hash_map<widening_svalue::key_t,
 442                    widening_svalue */*,
 443                    widening_svalue::key_t::hash_map_traits*/>
 444     widening_values_map_t;
 445   widening_values_map_t m_widening_values_map;
 446
 447   typedef hash_map<compound_svalue::key_t,
 448                    compound_svalue *> compound_values_map_t;
 449   compound_values_map_t m_compound_values_map;
 450
 451   typedef hash_map<conjured_svalue::key_t,
 452                    conjured_svalue *> conjured_values_map_t;
 453   conjured_values_map_t m_conjured_values_map;
 454
 455   typedef hash_map<asm_output_svalue::key_t,
 456                    asm_output_svalue *> asm_output_values_map_t;
 457   asm_output_values_map_t m_asm_output_values_map;
 458
 459   typedef hash_map<const_fn_result_svalue::key_t,
 460                    const_fn_result_svalue *> const_fn_result_values_map_t;
 461   const_fn_result_values_map_t m_const_fn_result_values_map;
 462
 463   bool m_checking_feasibility;
 464
 465   /* "Dynamically-allocated" svalue instances.
 466      The number of these within the analysis can grow arbitrarily.
 467      They are still owned by the manager.  */
 468   auto_delete_vec<svalue> m_managed_dynamic_svalues;
 469
 470   /* Maximum complexity of svalues that weren't rejected.  */
 471   complexity m_max_complexity;
 472
 473   /* region consolidation.  */
 474
 475   code_region m_code_region;
 476   typedef hash_map<tree, function_region *> fndecls_map_t;
 477   typedef fndecls_map_t::iterator fndecls_iterator_t;
 478   fndecls_map_t m_fndecls_map;
 479
 480   typedef hash_map<tree, label_region *> labels_map_t;
 481   typedef labels_map_t::iterator labels_iterator_t;
 482   labels_map_t m_labels_map;
 483
 484   globals_region m_globals_region;
 485   typedef hash_map<tree, decl_region *> globals_map_t;
 486   typedef globals_map_t::iterator globals_iterator_t;
 487   globals_map_t m_globals_map;
 488
 489   consolidation_map<field_region> m_field_regions;
 490   consolidation_map<element_region> m_element_regions;
 491   consolidation_map<offset_region> m_offset_regions;
 492   consolidation_map<sized_region> m_sized_regions;
 493   consolidation_map<cast_region> m_cast_regions;
 494   consolidation_map<frame_region> m_frame_regions;
 495   consolidation_map<symbolic_region> m_symbolic_regions;
 496
 497   typedef hash_map<tree, string_region *> string_map_t;
 498   string_map_t m_string_map;
 499
 500   consolidation_map<bit_range_region> m_bit_range_regions;
 501   consolidation_map<var_arg_region> m_var_arg_regions;
 502
 503   store_manager m_store_mgr;
 504
 505   bounded_ranges_manager *m_range_mgr;
 506
 507   /* "Dynamically-allocated" region instances.
 508      The number of these within the analysis can grow arbitrarily.
 509      They are still owned by the manager.  */
 510   auto_delete_vec<region> m_managed_dynamic_regions;
 511 };
 512
 513 struct append_regions_cb_data;
 514
 515 /* Helper class for handling calls to functions with known behavior.
 516    Implemented in region-model-impl-calls.c.  */
 517
 518 class call_details
 519 {
 520 public:
 521   call_details (const gcall *call, region_model *model,
 522                 region_model_context *ctxt);
 523
 524   region_model_manager *get_manager () const;
 525   region_model_context *get_ctxt () const { return m_ctxt; }
 526   uncertainty_t *get_uncertainty () const;
 527   tree get_lhs_type () const { return m_lhs_type; }
 528   const region *get_lhs_region () const { return m_lhs_region; }
 529
 530   bool maybe_set_lhs (const svalue *result) const;
 531
 532   unsigned num_args () const;
 533
 534   const gcall *get_call_stmt () const { return m_call; }
 535
 536   tree get_arg_tree (unsigned idx) const;
 537   tree get_arg_type (unsigned idx) const;
 538   const svalue *get_arg_svalue (unsigned idx) const;
 539   const char *get_arg_string_literal (unsigned idx) const;
 540
 541   tree get_fndecl_for_call () const;
 542
 543   void dump_to_pp (pretty_printer *pp, bool simple) const;
 544   void dump (bool simple) const;
 545
 546   const svalue *get_or_create_conjured_svalue (const region *) const;
 547
 548 private:
 549   const gcall *m_call;
 550   region_model *m_model;
 551   region_model_context *m_ctxt;
 552   tree m_lhs_type;
 553   const region *m_lhs_region;
 554 };
 555
 556 /* A region_model encapsulates a representation of the state of memory, with
 557    a tree of regions, along with their associated values.
 558    The representation is graph-like because values can be pointers to
 559    regions.
 560    It also stores:
 561    - a constraint_manager, capturing relationships between the values, and
 562    - dynamic extents, mapping dynamically-allocated regions to svalues (their
 563    capacities).  */
 564
 565 class region_model
 566 {
 567  public:
 568   typedef region_to_value_map dynamic_extents_t;
 569
 570   region_model (region_model_manager *mgr);
 571   region_model (const region_model &other);
 572   ~region_model ();
 573   region_model &operator= (const region_model &other);
 574
 575   bool operator== (const region_model &other) const;
 576   bool operator!= (const region_model &other) const
 577   {
 578     return !(*this == other);
 579   }
 580
 581   hashval_t hash () const;
 582
 583   void print (pretty_printer *pp) const;
 584
 585   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 586   void dump (FILE *fp, bool simple, bool multiline) const;
 587   void dump (bool simple) const;
 588
 589   void debug () const;
 590
 591   void validate () const;
 592
 593   void canonicalize ();
 594   bool canonicalized_p () const;
 595
 596   void
 597   on_stmt_pre (const gimple *stmt,
 598                bool *out_terminate_path,
 599                bool *out_unknown_side_effects,
 600                region_model_context *ctxt);
 601
 602   void on_assignment (const gassign *stmt, region_model_context *ctxt);
 603   const svalue *get_gassign_result (const gassign *assign,
 604                                     region_model_context *ctxt);
 605   void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
 606   bool on_call_pre (const gcall *stmt, region_model_context *ctxt,
 607                     bool *out_terminate_path);
 608   void on_call_post (const gcall *stmt,
 609                      bool unknown_side_effects,
 610                      region_model_context *ctxt);
 611
 612   void purge_state_involving (const svalue *sval, region_model_context *ctxt);
 613
 614   /* Specific handling for on_call_pre.  */
 615   void impl_call_alloca (const call_details &cd);
 616   void impl_call_analyzer_describe (const gcall *call,
 617                                     region_model_context *ctxt);
 618   void impl_call_analyzer_dump_capacity (const gcall *call,
 619                                          region_model_context *ctxt);
 620   void impl_call_analyzer_dump_escaped (const gcall *call);
 621   void impl_call_analyzer_eval (const gcall *call,
 622                                 region_model_context *ctxt);
 623   void impl_call_builtin_expect (const call_details &cd);
 624   void impl_call_calloc (const call_details &cd);
 625   bool impl_call_error (const call_details &cd, unsigned min_args,
 626                         bool *out_terminate_path);
 627   void impl_call_fgets (const call_details &cd);
 628   void impl_call_fread (const call_details &cd);
 629   void impl_call_free (const call_details &cd);
 630   void impl_call_malloc (const call_details &cd);
 631   void impl_call_memcpy (const call_details &cd);
 632   void impl_call_memset (const call_details &cd);
 633   void impl_call_putenv (const call_details &cd);
 634   void impl_call_realloc (const call_details &cd);
 635   void impl_call_strchr (const call_details &cd);
 636   void impl_call_strcpy (const call_details &cd);
 637   void impl_call_strlen (const call_details &cd);
 638   void impl_call_operator_new (const call_details &cd);
 639   void impl_call_operator_delete (const call_details &cd);
 640   void impl_deallocation_call (const call_details &cd);
 641
 642   /* Implemented in varargs.cc.  */
 643   void impl_call_va_start (const call_details &cd);
 644   void impl_call_va_copy (const call_details &cd);
 645   void impl_call_va_arg (const call_details &cd);
 646   void impl_call_va_end (const call_details &cd);
 647
 648   void handle_unrecognized_call (const gcall *call,
 649                                  region_model_context *ctxt);
 650   void get_reachable_svalues (svalue_set *out,
 651                               const svalue *extra_sval,
 652                               const uncertainty_t *uncertainty);
 653
 654   void on_return (const greturn *stmt, region_model_context *ctxt);
 655   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 656                   region_model_context *ctxt);
 657   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 658                    int setjmp_stack_depth, region_model_context *ctxt);
 659
 660   void update_for_phis (const supernode *snode,
 661                         const cfg_superedge *last_cfg_superedge,
 662                         region_model_context *ctxt);
 663
 664   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 665                    const region_model &old_state,
 666                    region_model_context *ctxt);
 667
 668   bool maybe_update_for_edge (const superedge &edge,
 669                               const gimple *last_stmt,
 670                               region_model_context *ctxt,
 671                               rejected_constraint **out);
 672
 673   void update_for_gcall (const gcall *call_stmt,
 674                          region_model_context *ctxt,
 675                          function *callee = NULL);
 676
 677   void update_for_return_gcall (const gcall *call_stmt,
 678                                 region_model_context *ctxt);
 679
 680   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 681                             region_model_context *ctxt);
 682   const frame_region *get_current_frame () const { return m_current_frame; }
 683   function * get_current_function () const;
 684   void pop_frame (tree result_lvalue,
 685                   const svalue **out_result,
 686                   region_model_context *ctxt);
 687   int get_stack_depth () const;
 688   const frame_region *get_frame_at_index (int index) const;
 689
 690   const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
 691   const region *get_lvalue (tree expr, region_model_context *ctxt) const;
 692   const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
 693   const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
 694
 695   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 696                                region_model_context *ctxt) const;
 697
 698   const svalue *get_rvalue_for_bits (tree type,
 699                                      const region *reg,
 700                                      const bit_range &bits,
 701                                      region_model_context *ctxt) const;
 702
 703   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 704                   region_model_context *ctxt);
 705   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 706   void clobber_region (const region *reg);
 707   void purge_region (const region *reg);
 708   void fill_region (const region *reg, const svalue *sval);
 709   void zero_fill_region (const region *reg);
 710   void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 711
 712   tristate eval_condition (const svalue *lhs,
 713                            enum tree_code op,
 714                            const svalue *rhs) const;
 715   tristate eval_condition_without_cm (const svalue *lhs,
 716                                       enum tree_code op,
 717                                       const svalue *rhs) const;
 718   tristate compare_initial_and_pointer (const initial_svalue *init,
 719                                         const region_svalue *ptr) const;
 720   tristate symbolic_greater_than (const binop_svalue *a,
 721                                   const svalue *b) const;
 722   tristate structural_equality (const svalue *a, const svalue *b) const;
 723   tristate eval_condition (tree lhs,
 724                            enum tree_code op,
 725                            tree rhs,
 726                            region_model_context *ctxt);
 727   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 728                        region_model_context *ctxt);
 729   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 730                        region_model_context *ctxt,
 731                        rejected_constraint **out);
 732
 733   const region *create_region_for_heap_alloc (const svalue *size_in_bytes,
 734                                               region_model_context *ctxt);
 735   const region *create_region_for_alloca (const svalue *size_in_bytes,
 736                                           region_model_context *ctxt);
 737
 738   tree get_representative_tree (const svalue *sval) const;
 739   tree get_representative_tree (const region *reg) const;
 740   path_var
 741   get_representative_path_var (const svalue *sval,
 742                                svalue_set *visited) const;
 743   path_var
 744   get_representative_path_var (const region *reg,
 745                                svalue_set *visited) const;
 746
 747   /* For selftests.  */
 748   constraint_manager *get_constraints ()
 749   {
 750     return m_constraints;
 751   }
 752
 753   store *get_store () { return &m_store; }
 754   const store *get_store () const { return &m_store; }
 755
 756   const dynamic_extents_t &
 757   get_dynamic_extents () const
 758   {
 759     return m_dynamic_extents;
 760   }
 761   const svalue *get_dynamic_extents (const region *reg) const;
 762   void set_dynamic_extents (const region *reg,
 763                             const svalue *size_in_bytes,
 764                             region_model_context *ctxt);
 765   void unset_dynamic_extents (const region *reg);
 766
 767   region_model_manager *get_manager () const { return m_mgr; }
 768   bounded_ranges_manager *get_range_manager () const
 769   {
 770     return m_mgr->get_range_manager ();
 771   }
 772
 773   void unbind_region_and_descendents (const region *reg,
 774                                       enum poison_kind pkind);
 775
 776   bool can_merge_with_p (const region_model &other_model,
 777                          const program_point &point,
 778                          region_model *out_model,
 779                          const extrinsic_state *ext_state = NULL,
 780                          const program_state *state_a = NULL,
 781                          const program_state *state_b = NULL) const;
 782
 783   tree get_fndecl_for_call (const gcall *call,
 784                             region_model_context *ctxt);
 785
 786   void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
 787   static void append_regions_cb (const region *base_reg,
 788                                  struct append_regions_cb_data *data);
 789
 790   const svalue *get_store_value (const region *reg,
 791                                  region_model_context *ctxt) const;
 792
 793   bool region_exists_p (const region *reg) const;
 794
 795   void loop_replay_fixup (const region_model *dst_state);
 796
 797   const svalue *get_capacity (const region *reg) const;
 798
 799   const svalue *get_string_size (const svalue *sval) const;
 800   const svalue *get_string_size (const region *reg) const;
 801
 802   /* Implemented in sm-malloc.cc  */
 803   void on_realloc_with_move (const call_details &cd,
 804                              const svalue *old_ptr_sval,
 805                              const svalue *new_ptr_sval);
 806
 807  private:
 808   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 809   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 810
 811   path_var
 812   get_representative_path_var_1 (const svalue *sval,
 813                                  svalue_set *visited) const;
 814   path_var
 815   get_representative_path_var_1 (const region *reg,
 816                                  svalue_set *visited) const;
 817
 818   bool add_constraint (const svalue *lhs,
 819                        enum tree_code op,
 820                        const svalue *rhs,
 821                        region_model_context *ctxt);
 822   bool add_constraints_from_binop (const svalue *outer_lhs,
 823                                    enum tree_code outer_op,
 824                                    const svalue *outer_rhs,
 825                                    bool *out,
 826                                    region_model_context *ctxt);
 827
 828   void update_for_call_superedge (const call_superedge &call_edge,
 829                                   region_model_context *ctxt);
 830   void update_for_return_superedge (const return_superedge &return_edge,
 831                                     region_model_context *ctxt);
 832   void update_for_call_summary (const callgraph_superedge &cg_sedge,
 833                                 region_model_context *ctxt);
 834   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 835                                     const gcond *cond_stmt,
 836                                     region_model_context *ctxt,
 837                                     rejected_constraint **out);
 838   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 839                                       const gswitch *switch_stmt,
 840                                       region_model_context *ctxt,
 841                                       rejected_constraint **out);
 842   bool apply_constraints_for_exception (const gimple *last_stmt,
 843                                         region_model_context *ctxt,
 844                                         rejected_constraint **out);
 845
 846   int poison_any_pointers_to_descendents (const region *reg,
 847                                           enum poison_kind pkind);
 848
 849   void on_top_level_param (tree param, region_model_context *ctxt);
 850
 851   bool called_from_main_p () const;
 852   const svalue *get_initial_value_for_global (const region *reg) const;
 853
 854   const svalue *check_for_poison (const svalue *sval,
 855                                   tree expr,
 856                                   region_model_context *ctxt) const;
 857   const region * get_region_for_poisoned_expr (tree expr) const;
 858
 859   void check_dynamic_size_for_taint (enum memory_space mem_space,
 860                                      const svalue *size_in_bytes,
 861                                      region_model_context *ctxt) const;
 862   void check_dynamic_size_for_floats (const svalue *size_in_bytes,
 863                                       region_model_context *ctxt) const;
 864
 865   void check_region_for_taint (const region *reg,
 866                                enum access_direction dir,
 867                                region_model_context *ctxt) const;
 868
 869   void check_for_writable_region (const region* dest_reg,
 870                                   region_model_context *ctxt) const;
 871   void check_region_access (const region *reg,
 872                             enum access_direction dir,
 873                             region_model_context *ctxt) const;
 874   void check_region_for_write (const region *dest_reg,
 875                                region_model_context *ctxt) const;
 876   void check_region_for_read (const region *src_reg,
 877                               region_model_context *ctxt) const;
 878   void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
 879                           region_model_context *ctxt) const;
 880   void check_symbolic_bounds (const region *base_reg,
 881                               const svalue *sym_byte_offset,
 882                               const svalue *num_bytes_sval,
 883                               const svalue *capacity,
 884                               enum access_direction dir,
 885                               region_model_context *ctxt) const;
 886   void check_region_bounds (const region *reg, enum access_direction dir,
 887                             region_model_context *ctxt) const;
 888
 889   void check_call_args (const call_details &cd) const;
 890   void check_external_function_for_access_attr (const gcall *call,
 891                                                 tree callee_fndecl,
 892                                                 region_model_context *ctxt) const;
 893
 894   /* Storing this here to avoid passing it around everywhere.  */
 895   region_model_manager *const m_mgr;
 896
 897   store m_store;
 898
 899   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 900
 901   const frame_region *m_current_frame;
 902
 903   /* Map from base region to size in bytes, for tracking the sizes of
 904      dynamically-allocated regions.
 905      This is part of the region_model rather than the region to allow for
 906      memory regions to be resized (e.g. by realloc).  */
 907   dynamic_extents_t m_dynamic_extents;
 908 };
 909
 910 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 911    uninitialized value).  This abstract base class encapsulates an interface
 912    for the region model to use when emitting such warnings.
 913
 914    Having this as an abstract base class allows us to support the various
 915    operations needed by program_state in the analyzer within region_model,
 916    whilst keeping them somewhat modularized.  */
 917
 918 class region_model_context
 919 {
 920  public:
 921   /* Hook for clients to store pending diagnostics.
 922      Return true if the diagnostic was stored, or false if it was deleted.  */
 923   virtual bool warn (pending_diagnostic *d) = 0;
 924
 925   /* Hook for clients to add a note to the last previously stored pending diagnostic.
 926      Takes ownership of the pending_node (or deletes it).  */
 927   virtual void add_note (pending_note *pn) = 0;
 928
 929   /* Hook for clients to be notified when an SVAL that was reachable
 930      in a previous state is no longer live, so that clients can emit warnings
 931      about leaks.  */
 932   virtual void on_svalue_leak (const svalue *sval) = 0;
 933
 934   /* Hook for clients to be notified when the set of explicitly live
 935      svalues changes, so that they can purge state relating to dead
 936      svalues.  */
 937   virtual void on_liveness_change (const svalue_set &live_svalues,
 938                                    const region_model *model) = 0;
 939
 940   virtual logger *get_logger () = 0;
 941
 942   /* Hook for clients to be notified when the condition
 943      "LHS OP RHS" is added to the region model.
 944      This exists so that state machines can detect tests on edges,
 945      and use them to trigger sm-state transitions (e.g. transitions due
 946      to ptrs becoming known to be NULL or non-NULL, rather than just
 947      "unchecked") */
 948   virtual void on_condition (const svalue *lhs,
 949                              enum tree_code op,
 950                              const svalue *rhs) = 0;
 951
 952   /* Hook for clients to be notified when the condition that
 953      SVAL is within RANGES is added to the region model.
 954      Similar to on_condition, but for use when handling switch statements.
 955      RANGES is non-empty.  */
 956   virtual void on_bounded_ranges (const svalue &sval,
 957                                   const bounded_ranges &ranges) = 0;
 958
 959   /* Hooks for clients to be notified when an unknown change happens
 960      to SVAL (in response to a call to an unknown function).  */
 961   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 962
 963   /* Hooks for clients to be notified when a phi node is handled,
 964      where RHS is the pertinent argument.  */
 965   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 966
 967   /* Hooks for clients to be notified when the region model doesn't
 968      know how to handle the tree code of T at LOC.  */
 969   virtual void on_unexpected_tree_code (tree t,
 970                                         const dump_location_t &loc) = 0;
 971
 972   /* Hook for clients to be notified when a function_decl escapes.  */
 973   virtual void on_escaped_function (tree fndecl) = 0;
 974
 975   virtual uncertainty_t *get_uncertainty () = 0;
 976
 977   /* Hook for clients to purge state involving SVAL.  */
 978   virtual void purge_state_involving (const svalue *sval) = 0;
 979
 980   /* Hook for clients to split state with a non-standard path.
 981      Take ownership of INFO.  */
 982   virtual void bifurcate (custom_edge_info *info) = 0;
 983
 984   /* Hook for clients to terminate the standard path.  */
 985   virtual void terminate_path () = 0;
 986
 987   virtual const extrinsic_state *get_ext_state () const = 0;
 988
 989   /* Hook for clients to access the "malloc" state machine in
 990      any underlying program_state.  */
 991   virtual bool get_malloc_map (sm_state_map **out_smap,
 992                                const state_machine **out_sm,
 993                                unsigned *out_sm_idx) = 0;
 994   /* Likewise for the "taint" state machine.  */
 995   virtual bool get_taint_map (sm_state_map **out_smap,
 996                               const state_machine **out_sm,
 997                               unsigned *out_sm_idx) = 0;
 998
 999   /* Get the current statement, if any.  */
1000   virtual const gimple *get_stmt () const = 0;
1001 };
1002
1003 /* A "do nothing" subclass of region_model_context.  */
1004
1005 class noop_region_model_context : public region_model_context
1006 {
1007 public:
1008   bool warn (pending_diagnostic *) override { return false; }
1009   void add_note (pending_note *pn) override;
1010   void on_svalue_leak (const svalue *) override {}
1011   void on_liveness_change (const svalue_set &,
1012                            const region_model *) override {}
1013   logger *get_logger () override { return NULL; }
1014   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
1015                      enum tree_code op ATTRIBUTE_UNUSED,
1016                      const svalue *rhs ATTRIBUTE_UNUSED) override
1017   {
1018   }
1019   void on_bounded_ranges (const svalue &,
1020                           const bounded_ranges &) override
1021   {
1022   }
1023   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
1024                           bool is_mutable ATTRIBUTE_UNUSED) override
1025   {
1026   }
1027   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
1028                tree rhs ATTRIBUTE_UNUSED) override
1029   {
1030   }
1031   void on_unexpected_tree_code (tree, const dump_location_t &) override {}
1032
1033   void on_escaped_function (tree) override {}
1034
1035   uncertainty_t *get_uncertainty () override { return NULL; }
1036
1037   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
1038
1039   void bifurcate (custom_edge_info *info) override;
1040   void terminate_path () override;
1041
1042   const extrinsic_state *get_ext_state () const override { return NULL; }
1043
1044   bool get_malloc_map (sm_state_map **,
1045                        const state_machine **,
1046                        unsigned *) override
1047   {
1048     return false;
1049   }
1050   bool get_taint_map (sm_state_map **,
1051                       const state_machine **,
1052                       unsigned *) override
1053   {
1054     return false;
1055   }
1056
1057   const gimple *get_stmt () const override { return NULL; }
1058 };
1059
1060 /* A subclass of region_model_context for determining if operations fail
1061    e.g. "can we generate a region for the lvalue of EXPR?".  */
1062
1063 class tentative_region_model_context : public noop_region_model_context
1064 {
1065 public:
1066   tentative_region_model_context () : m_num_unexpected_codes (0) {}
1067
1068   void on_unexpected_tree_code (tree, const dump_location_t &)
1069     final override
1070   {
1071     m_num_unexpected_codes++;
1072   }
1073
1074   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
1075
1076 private:
1077   int m_num_unexpected_codes;
1078 };
1079
1080 /* Subclass of region_model_context that wraps another context, allowing
1081    for extra code to be added to the various hooks.  */
1082
1083 class region_model_context_decorator : public region_model_context
1084 {
1085  public:
1086   bool warn (pending_diagnostic *d) override
1087   {
1088     return m_inner->warn (d);
1089   }
1090
1091   void add_note (pending_note *pn) override
1092   {
1093     m_inner->add_note (pn);
1094   }
1095
1096   void on_svalue_leak (const svalue *sval) override
1097   {
1098     m_inner->on_svalue_leak (sval);
1099   }
1100
1101   void on_liveness_change (const svalue_set &live_svalues,
1102                            const region_model *model) override
1103   {
1104     m_inner->on_liveness_change (live_svalues, model);
1105   }
1106
1107   logger *get_logger () override
1108   {
1109     return m_inner->get_logger ();
1110   }
1111
1112   void on_condition (const svalue *lhs,
1113                      enum tree_code op,
1114                      const svalue *rhs) override
1115   {
1116     m_inner->on_condition (lhs, op, rhs);
1117   }
1118
1119   void on_bounded_ranges (const svalue &sval,
1120                           const bounded_ranges &ranges) override
1121   {
1122     m_inner->on_bounded_ranges (sval, ranges);
1123   }
1124
1125   void on_unknown_change (const svalue *sval, bool is_mutable) override
1126   {
1127     m_inner->on_unknown_change (sval, is_mutable);
1128   }
1129
1130   void on_phi (const gphi *phi, tree rhs) override
1131   {
1132     m_inner->on_phi (phi, rhs);
1133   }
1134
1135   void on_unexpected_tree_code (tree t,
1136                                 const dump_location_t &loc) override
1137   {
1138     m_inner->on_unexpected_tree_code (t, loc);
1139   }
1140
1141   void on_escaped_function (tree fndecl) override
1142   {
1143     m_inner->on_escaped_function (fndecl);
1144   }
1145
1146   uncertainty_t *get_uncertainty () override
1147   {
1148     return m_inner->get_uncertainty ();
1149   }
1150
1151   void purge_state_involving (const svalue *sval) override
1152   {
1153     m_inner->purge_state_involving (sval);
1154   }
1155
1156   void bifurcate (custom_edge_info *info) override
1157   {
1158     m_inner->bifurcate (info);
1159   }
1160
1161   void terminate_path () override
1162   {
1163     m_inner->terminate_path ();
1164   }
1165
1166   const extrinsic_state *get_ext_state () const override
1167   {
1168     return m_inner->get_ext_state ();
1169   }
1170
1171   bool get_malloc_map (sm_state_map **out_smap,
1172                        const state_machine **out_sm,
1173                        unsigned *out_sm_idx) override
1174   {
1175     return m_inner->get_malloc_map (out_smap, out_sm, out_sm_idx);
1176   }
1177
1178   bool get_taint_map (sm_state_map **out_smap,
1179                       const state_machine **out_sm,
1180                       unsigned *out_sm_idx) override
1181   {
1182     return m_inner->get_taint_map (out_smap, out_sm, out_sm_idx);
1183   }
1184
1185   const gimple *get_stmt () const override
1186   {
1187     return m_inner->get_stmt ();
1188   }
1189
1190 protected:
1191   region_model_context_decorator (region_model_context *inner)
1192   : m_inner (inner)
1193   {
1194     gcc_assert (m_inner);
1195   }
1196
1197   region_model_context *m_inner;
1198 };
1199
1200 /* Subclass of region_model_context_decorator that adds a note
1201    when saving diagnostics.  */
1202
1203 class note_adding_context : public region_model_context_decorator
1204 {
1205 public:
1206   bool warn (pending_diagnostic *d) override
1207   {
1208     if (m_inner->warn (d))
1209       {
1210         add_note (make_note ());
1211         return true;
1212       }
1213     else
1214       return false;
1215   }
1216
1217   /* Hook to make the new note.  */
1218   virtual pending_note *make_note () = 0;
1219
1220 protected:
1221   note_adding_context (region_model_context *inner)
1222   : region_model_context_decorator (inner)
1223   {
1224   }
1225 };
1226
1227 /* A bundle of data for use when attempting to merge two region_model
1228    instances to make a third.  */
1229
1230 struct model_merger
1231 {
1232   model_merger (const region_model *model_a,
1233                 const region_model *model_b,
1234                 const program_point &point,
1235                 region_model *merged_model,
1236                 const extrinsic_state *ext_state,
1237                 const program_state *state_a,
1238                 const program_state *state_b)
1239   : m_model_a (model_a), m_model_b (model_b),
1240     m_point (point),
1241     m_merged_model (merged_model),
1242     m_ext_state (ext_state),
1243     m_state_a (state_a), m_state_b (state_b)
1244   {
1245   }
1246
1247   void dump_to_pp (pretty_printer *pp, bool simple) const;
1248   void dump (FILE *fp, bool simple) const;
1249   void dump (bool simple) const;
1250
1251   region_model_manager *get_manager () const
1252   {
1253     return m_model_a->get_manager ();
1254   }
1255
1256   bool mergeable_svalue_p (const svalue *) const;
1257
1258   const region_model *m_model_a;
1259   const region_model *m_model_b;
1260   const program_point &m_point;
1261   region_model *m_merged_model;
1262
1263   const extrinsic_state *m_ext_state;
1264   const program_state *m_state_a;
1265   const program_state *m_state_b;
1266 };
1267
1268 /* A record that can (optionally) be written out when
1269    region_model::add_constraint fails.  */
1270
1271 class rejected_constraint
1272 {
1273 public:
1274   virtual ~rejected_constraint () {}
1275   virtual void dump_to_pp (pretty_printer *pp) const = 0;
1276
1277   const region_model &get_model () const { return m_model; }
1278
1279 protected:
1280   rejected_constraint (const region_model &model)
1281   : m_model (model)
1282   {}
1283
1284   region_model m_model;
1285 };
1286
1287 class rejected_op_constraint : public rejected_constraint
1288 {
1289 public:
1290   rejected_op_constraint (const region_model &model,
1291                           tree lhs, enum tree_code op, tree rhs)
1292   : rejected_constraint (model),
1293     m_lhs (lhs), m_op (op), m_rhs (rhs)
1294   {}
1295
1296   void dump_to_pp (pretty_printer *pp) const final override;
1297
1298   tree m_lhs;
1299   enum tree_code m_op;
1300   tree m_rhs;
1301 };
1302
1303 class rejected_ranges_constraint : public rejected_constraint
1304 {
1305 public:
1306   rejected_ranges_constraint (const region_model &model,
1307                               tree expr, const bounded_ranges *ranges)
1308   : rejected_constraint (model),
1309     m_expr (expr), m_ranges (ranges)
1310   {}
1311
1312   void dump_to_pp (pretty_printer *pp) const final override;
1313
1314 private:
1315   tree m_expr;
1316   const bounded_ranges *m_ranges;
1317 };
1318
1319 /* A bundle of state.  */
1320
1321 class engine
1322 {
1323 public:
1324   engine (const supergraph *sg = NULL, logger *logger = NULL);
1325   const supergraph *get_supergraph () { return m_sg; }
1326   region_model_manager *get_model_manager () { return &m_mgr; }
1327
1328   void log_stats (logger *logger) const;
1329
1330 private:
1331   const supergraph *m_sg;
1332   region_model_manager m_mgr;
1333 };
1334
1335 } // namespace ana
1336
1337 extern void debug (const region_model &rmodel);
1338
1339 namespace ana {
1340
1341 #if CHECKING_P
1342
1343 namespace selftest {
1344
1345 using namespace ::selftest;
1346
1347 /* An implementation of region_model_context for use in selftests, which
1348    stores any pending_diagnostic instances passed to it.  */
1349
1350 class test_region_model_context : public noop_region_model_context
1351 {
1352 public:
1353   bool warn (pending_diagnostic *d) final override
1354   {
1355     m_diagnostics.safe_push (d);
1356     return true;
1357   }
1358
1359   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1360
1361   void on_unexpected_tree_code (tree t, const dump_location_t &)
1362     final override
1363   {
1364     internal_error ("unhandled tree code: %qs",
1365                     get_tree_code_name (TREE_CODE (t)));
1366   }
1367
1368 private:
1369   /* Implicitly delete any diagnostics in the dtor.  */
1370   auto_delete_vec<pending_diagnostic> m_diagnostics;
1371 };
1372
1373 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1374    Verify that MODEL remains satisfiable.  */
1375
1376 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1377   SELFTEST_BEGIN_STMT                                   \
1378     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1379     ASSERT_TRUE (sat);                                  \
1380   SELFTEST_END_STMT
1381
1382 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1383    Verify that the result is not satisfiable.  */
1384
1385 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
1386   SELFTEST_BEGIN_STMT                                   \
1387     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1388     ASSERT_FALSE (sat);                         \
1389   SELFTEST_END_STMT
1390
1391 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
1392
1393 void assert_condition (const location &loc,
1394                        region_model &model,
1395                        const svalue *lhs, tree_code op, const svalue *rhs,
1396                        tristate expected);
1397
1398 void assert_condition (const location &loc,
1399                        region_model &model,
1400                        tree lhs, tree_code op, tree rhs,
1401                        tristate expected);
1402
1403 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1404    as "true".  */
1405
1406 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1407   SELFTEST_BEGIN_STMT                                                   \
1408   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1409                     tristate (tristate::TS_TRUE));              \
1410   SELFTEST_END_STMT
1411
1412 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1413    as "false".  */
1414
1415 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1416   SELFTEST_BEGIN_STMT                                                   \
1417   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1418                     tristate (tristate::TS_FALSE));             \
1419   SELFTEST_END_STMT
1420
1421 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1422    as "unknown".  */
1423
1424 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1425   SELFTEST_BEGIN_STMT                                                   \
1426   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1427                     tristate (tristate::TS_UNKNOWN));           \
1428   SELFTEST_END_STMT
1429
1430 } /* end of namespace selftest.  */
1431
1432 #endif /* #if CHECKING_P */
1433
1434 } // namespace ana
1435
1436 #endif /* GCC_ANALYZER_REGION_MODEL_H */