gcc/analyzer/region-model.h

   1 /* Classes for modeling the state of memory.
   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_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 "bitmap.h"
  30 #include "selftest.h"
  31 #include "analyzer/svalue.h"
  32 #include "analyzer/region.h"
  33 #include "analyzer/known-function-manager.h"
  34 #include "analyzer/region-model-manager.h"
  35 #include "analyzer/pending-diagnostic.h"
  36
  37 using namespace ana;
  38
  39 namespace inchash
  40 {
  41   extern void add_path_var (path_var pv, hash &hstate);
  42 } // namespace inchash
  43
  44 namespace ana {
  45
  46 template <typename T>
  47 class one_way_id_map
  48 {
  49  public:
  50   one_way_id_map (int num_ids);
  51   void put (T src, T dst);
  52   T get_dst_for_src (T src) const;
  53   void dump_to_pp (pretty_printer *pp) const;
  54   void dump () const;
  55   void update (T *) const;
  56
  57  private:
  58   auto_vec<T> m_src_to_dst;
  59  };
  60
  61 /* class one_way_id_map.  */
  62
  63 /* one_way_id_map's ctor, which populates the map with dummy null values.  */
  64
  65 template <typename T>
  66 inline one_way_id_map<T>::one_way_id_map (int num_svalues)
  67 : m_src_to_dst (num_svalues)
  68 {
  69   for (int i = 0; i < num_svalues; i++)
  70     m_src_to_dst.quick_push (T::null ());
  71 }
  72
  73 /* Record that SRC is to be mapped to DST.  */
  74
  75 template <typename T>
  76 inline void
  77 one_way_id_map<T>::put (T src, T dst)
  78 {
  79   m_src_to_dst[src.as_int ()] = dst;
  80 }
  81
  82 /* Get the new value for SRC within the map.  */
  83
  84 template <typename T>
  85 inline T
  86 one_way_id_map<T>::get_dst_for_src (T src) const
  87 {
  88   if (src.null_p ())
  89     return src;
  90   return m_src_to_dst[src.as_int ()];
  91 }
  92
  93 /* Dump this map to PP.  */
  94
  95 template <typename T>
  96 inline void
  97 one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
  98 {
  99   pp_string (pp, "src to dst: {");
 100   unsigned i;
 101   T *dst;
 102   FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
 103     {
 104       if (i > 0)
 105         pp_string (pp, ", ");
 106       T src (T::from_int (i));
 107       src.print (pp);
 108       pp_string (pp, " -> ");
 109       dst->print (pp);
 110     }
 111   pp_string (pp, "}");
 112   pp_newline (pp);
 113 }
 114
 115 /* Dump this map to stderr.  */
 116
 117 template <typename T>
 118 DEBUG_FUNCTION inline void
 119 one_way_id_map<T>::dump () const
 120 {
 121   pretty_printer pp;
 122   pp.buffer->stream = stderr;
 123   dump_to_pp (&pp);
 124   pp_flush (&pp);
 125 }
 126
 127 /* Update *ID from the old value to its new value in this map.  */
 128
 129 template <typename T>
 130 inline void
 131 one_way_id_map<T>::update (T *id) const
 132 {
 133   *id = get_dst_for_src (*id);
 134 }
 135
 136 /* A mapping from region to svalue for use when tracking state.  */
 137
 138 class region_to_value_map
 139 {
 140 public:
 141   typedef hash_map<const region *, const svalue *> hash_map_t;
 142   typedef hash_map_t::iterator iterator;
 143
 144   region_to_value_map () : m_hash_map () {}
 145   region_to_value_map (const region_to_value_map &other)
 146   : m_hash_map (other.m_hash_map) {}
 147   region_to_value_map &operator= (const region_to_value_map &other);
 148
 149   bool operator== (const region_to_value_map &other) const;
 150   bool operator!= (const region_to_value_map &other) const
 151   {
 152     return !(*this == other);
 153   }
 154
 155   iterator begin () const { return m_hash_map.begin (); }
 156   iterator end () const { return m_hash_map.end (); }
 157
 158   const svalue * const *get (const region *reg) const
 159   {
 160     return const_cast <hash_map_t &> (m_hash_map).get (reg);
 161   }
 162   void put (const region *reg, const svalue *sval)
 163   {
 164     m_hash_map.put (reg, sval);
 165   }
 166   void remove (const region *reg)
 167   {
 168     m_hash_map.remove (reg);
 169   }
 170
 171   bool is_empty () const { return m_hash_map.is_empty (); }
 172
 173   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 174   void dump (bool simple) const;
 175
 176   bool can_merge_with_p (const region_to_value_map &other,
 177                          region_to_value_map *out) const;
 178
 179   void purge_state_involving (const svalue *sval);
 180
 181 private:
 182   hash_map_t m_hash_map;
 183 };
 184
 185 /* Various operations delete information from a region_model.
 186
 187    This struct tracks how many of each kind of entity were purged (e.g.
 188    for selftests, and for debugging).  */
 189
 190 struct purge_stats
 191 {
 192   purge_stats ()
 193   : m_num_svalues (0),
 194     m_num_regions (0),
 195     m_num_equiv_classes (0),
 196     m_num_constraints (0),
 197     m_num_bounded_ranges_constraints (0),
 198     m_num_client_items (0)
 199   {}
 200
 201   int m_num_svalues;
 202   int m_num_regions;
 203   int m_num_equiv_classes;
 204   int m_num_constraints;
 205   int m_num_bounded_ranges_constraints;
 206   int m_num_client_items;
 207 };
 208
 209 /* A base class for visiting regions and svalues, with do-nothing
 210    base implementations of the per-subclass vfuncs.  */
 211
 212 class visitor
 213 {
 214 public:
 215   virtual void visit_region_svalue (const region_svalue *) {}
 216   virtual void visit_constant_svalue (const constant_svalue *) {}
 217   virtual void visit_unknown_svalue (const unknown_svalue *) {}
 218   virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
 219   virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
 220   virtual void visit_initial_svalue (const initial_svalue *) {}
 221   virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
 222   virtual void visit_binop_svalue (const binop_svalue *) {}
 223   virtual void visit_sub_svalue (const sub_svalue *) {}
 224   virtual void visit_repeated_svalue (const repeated_svalue *) {}
 225   virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
 226   virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
 227   virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
 228   virtual void visit_widening_svalue (const widening_svalue *) {}
 229   virtual void visit_compound_svalue (const compound_svalue *) {}
 230   virtual void visit_conjured_svalue (const conjured_svalue *) {}
 231   virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
 232   virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
 233
 234   virtual void visit_region (const region *) {}
 235 };
 236
 237 struct append_regions_cb_data;
 238
 239 typedef void (*pop_frame_callback) (const region_model *model,
 240                                     const region_model *prev_model,
 241                                     const svalue *retval,
 242                                     region_model_context *ctxt);
 243
 244 /* A region_model encapsulates a representation of the state of memory, with
 245    a tree of regions, along with their associated values.
 246    The representation is graph-like because values can be pointers to
 247    regions.
 248    It also stores:
 249    - a constraint_manager, capturing relationships between the values, and
 250    - dynamic extents, mapping dynamically-allocated regions to svalues (their
 251    capacities).  */
 252
 253 class region_model
 254 {
 255  public:
 256   typedef region_to_value_map dynamic_extents_t;
 257
 258   region_model (region_model_manager *mgr);
 259   region_model (const region_model &other);
 260   ~region_model ();
 261   region_model &operator= (const region_model &other);
 262
 263   bool operator== (const region_model &other) const;
 264   bool operator!= (const region_model &other) const
 265   {
 266     return !(*this == other);
 267   }
 268
 269   hashval_t hash () const;
 270
 271   void print (pretty_printer *pp) const;
 272
 273   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 274   void dump (FILE *fp, bool simple, bool multiline) const;
 275   void dump (bool simple) const;
 276
 277   void debug () const;
 278
 279   void validate () const;
 280
 281   void canonicalize ();
 282   bool canonicalized_p () const;
 283
 284   void
 285   on_stmt_pre (const gimple *stmt,
 286                bool *out_unknown_side_effects,
 287                region_model_context *ctxt);
 288
 289   void on_assignment (const gassign *stmt, region_model_context *ctxt);
 290   const svalue *get_gassign_result (const gassign *assign,
 291                                     region_model_context *ctxt);
 292   void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
 293   bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
 294   void on_call_post (const gcall *stmt,
 295                      bool unknown_side_effects,
 296                      region_model_context *ctxt);
 297
 298   void purge_state_involving (const svalue *sval, region_model_context *ctxt);
 299
 300   void impl_deallocation_call (const call_details &cd);
 301
 302   const svalue *maybe_get_copy_bounds (const region *src_reg,
 303                                        const svalue *num_bytes_sval);
 304   void update_for_int_cst_return (const call_details &cd,
 305                                   int retval,
 306                                   bool unmergeable);
 307   void update_for_zero_return (const call_details &cd,
 308                                bool unmergeable);
 309   void update_for_nonzero_return (const call_details &cd);
 310
 311   void handle_unrecognized_call (const gcall *call,
 312                                  region_model_context *ctxt);
 313   void get_reachable_svalues (svalue_set *out,
 314                               const svalue *extra_sval,
 315                               const uncertainty_t *uncertainty);
 316
 317   void on_return (const greturn *stmt, region_model_context *ctxt);
 318   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 319                   region_model_context *ctxt);
 320   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 321                    int setjmp_stack_depth, region_model_context *ctxt);
 322
 323   void update_for_phis (const supernode *snode,
 324                         const cfg_superedge *last_cfg_superedge,
 325                         region_model_context *ctxt);
 326
 327   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 328                    const region_model &old_state,
 329                    region_model_context *ctxt);
 330
 331   bool maybe_update_for_edge (const superedge &edge,
 332                               const gimple *last_stmt,
 333                               region_model_context *ctxt,
 334                               rejected_constraint **out);
 335
 336   void update_for_gcall (const gcall *call_stmt,
 337                          region_model_context *ctxt,
 338                          function *callee = NULL);
 339
 340   void update_for_return_gcall (const gcall *call_stmt,
 341                                 region_model_context *ctxt);
 342
 343   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 344                             region_model_context *ctxt);
 345   const frame_region *get_current_frame () const { return m_current_frame; }
 346   function * get_current_function () const;
 347   void pop_frame (tree result_lvalue,
 348                   const svalue **out_result,
 349                   region_model_context *ctxt,
 350                   bool eval_return_svalue = true);
 351   int get_stack_depth () const;
 352   const frame_region *get_frame_at_index (int index) const;
 353
 354   const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
 355   const region *get_lvalue (tree expr, region_model_context *ctxt) const;
 356   const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
 357   const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
 358
 359   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 360                               region_model_context *ctxt,
 361                               bool add_nonnull_constraint = true) const;
 362
 363   const svalue *get_rvalue_for_bits (tree type,
 364                                      const region *reg,
 365                                      const bit_range &bits,
 366                                      region_model_context *ctxt) const;
 367
 368   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 369                   region_model_context *ctxt);
 370   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 371   void clobber_region (const region *reg);
 372   void purge_region (const region *reg);
 373   void fill_region (const region *reg,
 374                     const svalue *sval,
 375                     region_model_context *ctxt);
 376   void zero_fill_region (const region *reg,
 377                          region_model_context *ctxt);
 378   void write_bytes (const region *dest_reg,
 379                     const svalue *num_bytes_sval,
 380                     const svalue *sval,
 381                     region_model_context *ctxt);
 382   const svalue *read_bytes (const region *src_reg,
 383                             tree src_ptr_expr,
 384                             const svalue *num_bytes_sval,
 385                             region_model_context *ctxt) const;
 386   void copy_bytes (const region *dest_reg,
 387                    const region *src_reg,
 388                    tree src_ptr_expr,
 389                    const svalue *num_bytes_sval,
 390                    region_model_context *ctxt);
 391   void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 392
 393   tristate eval_condition (const svalue *lhs,
 394                            enum tree_code op,
 395                            const svalue *rhs) const;
 396   tristate compare_initial_and_pointer (const initial_svalue *init,
 397                                         const region_svalue *ptr) const;
 398   tristate symbolic_greater_than (const binop_svalue *a,
 399                                   const svalue *b) const;
 400   tristate structural_equality (const svalue *a, const svalue *b) const;
 401   tristate eval_condition (tree lhs,
 402                            enum tree_code op,
 403                            tree rhs,
 404                            region_model_context *ctxt) const;
 405   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 406                        region_model_context *ctxt);
 407   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 408                        region_model_context *ctxt,
 409                        rejected_constraint **out);
 410
 411         const region *
 412         get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
 413                                 region_model_context *ctxt,
 414                                 bool update_state_machine = false,
 415                                 const call_details *cd = nullptr);
 416
 417   const region *create_region_for_alloca (const svalue *size_in_bytes,
 418                                           region_model_context *ctxt);
 419   void get_referenced_base_regions (auto_bitmap &out_ids) const;
 420
 421   tree get_representative_tree (const svalue *sval) const;
 422   tree get_representative_tree (const region *reg) const;
 423   path_var
 424   get_representative_path_var (const svalue *sval,
 425                                svalue_set *visited) const;
 426   path_var
 427   get_representative_path_var (const region *reg,
 428                                svalue_set *visited) const;
 429
 430   /* For selftests.  */
 431   constraint_manager *get_constraints ()
 432   {
 433     return m_constraints;
 434   }
 435
 436   store *get_store () { return &m_store; }
 437   const store *get_store () const { return &m_store; }
 438
 439   const dynamic_extents_t &
 440   get_dynamic_extents () const
 441   {
 442     return m_dynamic_extents;
 443   }
 444   const svalue *get_dynamic_extents (const region *reg) const;
 445   void set_dynamic_extents (const region *reg,
 446                             const svalue *size_in_bytes,
 447                             region_model_context *ctxt);
 448   void unset_dynamic_extents (const region *reg);
 449
 450   region_model_manager *get_manager () const { return m_mgr; }
 451   bounded_ranges_manager *get_range_manager () const
 452   {
 453     return m_mgr->get_range_manager ();
 454   }
 455
 456   void unbind_region_and_descendents (const region *reg,
 457                                       enum poison_kind pkind);
 458
 459   bool can_merge_with_p (const region_model &other_model,
 460                          const program_point &point,
 461                          region_model *out_model,
 462                          const extrinsic_state *ext_state = NULL,
 463                          const program_state *state_a = NULL,
 464                          const program_state *state_b = NULL) const;
 465
 466   tree get_fndecl_for_call (const gcall *call,
 467                             region_model_context *ctxt);
 468
 469   void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
 470   static void append_regions_cb (const region *base_reg,
 471                                  struct append_regions_cb_data *data);
 472
 473   const svalue *get_store_value (const region *reg,
 474                                  region_model_context *ctxt) const;
 475   const svalue *get_store_bytes (const region *base_reg,
 476                                  const byte_range &bytes,
 477                                  region_model_context *ctxt) const;
 478   const svalue *scan_for_null_terminator (const region *reg,
 479                                           tree expr,
 480                                           const svalue **out_sval,
 481                                           region_model_context *ctxt) const;
 482
 483   bool region_exists_p (const region *reg) const;
 484
 485   void loop_replay_fixup (const region_model *dst_state);
 486
 487   const svalue *get_capacity (const region *reg) const;
 488
 489   bool replay_call_summary (call_summary_replay &r,
 490                             const region_model &summary);
 491
 492   void maybe_complain_about_infoleak (const region *dst_reg,
 493                                       const svalue *copied_sval,
 494                                       const region *src_reg,
 495                                       region_model_context *ctxt);
 496
 497   void set_errno (const call_details &cd);
 498
 499   /* Implemented in sm-fd.cc  */
 500   void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
 501
 502   /* Implemented in sm-malloc.cc  */
 503   void on_realloc_with_move (const call_details &cd,
 504                              const svalue *old_ptr_sval,
 505                              const svalue *new_ptr_sval);
 506
 507   /* Implemented in sm-malloc.cc.  */
 508   void
 509   transition_ptr_sval_non_null (region_model_context *ctxt,
 510       const svalue *new_ptr_sval);
 511
 512   /* Implemented in sm-taint.cc.  */
 513   void mark_as_tainted (const svalue *sval,
 514                         region_model_context *ctxt);
 515
 516   bool add_constraint (const svalue *lhs,
 517                        enum tree_code op,
 518                        const svalue *rhs,
 519                        region_model_context *ctxt);
 520
 521   const svalue *check_for_poison (const svalue *sval,
 522                                   tree expr,
 523                                   const region *src_region,
 524                                   region_model_context *ctxt) const;
 525
 526   void check_region_for_write (const region *dest_reg,
 527                                const svalue *sval_hint,
 528                                region_model_context *ctxt) const;
 529
 530   void
 531   check_for_null_terminated_string_arg (const call_details &cd,
 532                                         unsigned idx);
 533   const svalue *
 534   check_for_null_terminated_string_arg (const call_details &cd,
 535                                         unsigned idx,
 536                                         bool include_terminator,
 537                                         const svalue **out_sval);
 538
 539   const builtin_known_function *
 540   get_builtin_kf (const gcall *call,
 541                   region_model_context *ctxt = NULL) const;
 542
 543   static void
 544   register_pop_frame_callback (const pop_frame_callback &callback)
 545   {
 546     pop_frame_callbacks.safe_push (callback);
 547   }
 548
 549   static void
 550   notify_on_pop_frame (const region_model *model,
 551                        const region_model *prev_model,
 552                        const svalue *retval,
 553                        region_model_context *ctxt)
 554   {
 555     for (auto &callback : pop_frame_callbacks)
 556         callback (model, prev_model, retval, ctxt);
 557   }
 558
 559 private:
 560   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 561   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 562
 563   path_var
 564   get_representative_path_var_1 (const svalue *sval,
 565                                  svalue_set *visited) const;
 566   path_var
 567   get_representative_path_var_1 (const region *reg,
 568                                  svalue_set *visited) const;
 569
 570   const known_function *get_known_function (tree fndecl,
 571                                             const call_details &cd) const;
 572   const known_function *get_known_function (enum internal_fn) const;
 573
 574   bool add_constraints_from_binop (const svalue *outer_lhs,
 575                                    enum tree_code outer_op,
 576                                    const svalue *outer_rhs,
 577                                    bool *out,
 578                                    region_model_context *ctxt);
 579
 580   void update_for_call_superedge (const call_superedge &call_edge,
 581                                   region_model_context *ctxt);
 582   void update_for_return_superedge (const return_superedge &return_edge,
 583                                     region_model_context *ctxt);
 584   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 585                                     const gcond *cond_stmt,
 586                                     region_model_context *ctxt,
 587                                     rejected_constraint **out);
 588   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 589                                       const gswitch *switch_stmt,
 590                                       region_model_context *ctxt,
 591                                       rejected_constraint **out);
 592   bool apply_constraints_for_ggoto (const cfg_superedge &edge,
 593                                     const ggoto *goto_stmt,
 594                                     region_model_context *ctxt);
 595   bool apply_constraints_for_exception (const gimple *last_stmt,
 596                                         region_model_context *ctxt,
 597                                         rejected_constraint **out);
 598
 599   int poison_any_pointers_to_descendents (const region *reg,
 600                                           enum poison_kind pkind);
 601
 602   void on_top_level_param (tree param,
 603                            bool nonnull,
 604                            region_model_context *ctxt);
 605
 606   bool called_from_main_p () const;
 607   const svalue *get_initial_value_for_global (const region *reg) const;
 608
 609   const region * get_region_for_poisoned_expr (tree expr) const;
 610
 611   void check_dynamic_size_for_taint (enum memory_space mem_space,
 612                                      const svalue *size_in_bytes,
 613                                      region_model_context *ctxt) const;
 614   void check_dynamic_size_for_floats (const svalue *size_in_bytes,
 615                                       region_model_context *ctxt) const;
 616
 617   void check_region_for_taint (const region *reg,
 618                                enum access_direction dir,
 619                                region_model_context *ctxt) const;
 620
 621   void check_for_writable_region (const region* dest_reg,
 622                                   region_model_context *ctxt) const;
 623   bool check_region_access (const region *reg,
 624                             enum access_direction dir,
 625                             const svalue *sval_hint,
 626                             region_model_context *ctxt) const;
 627   bool check_region_for_read (const region *src_reg,
 628                               region_model_context *ctxt) const;
 629   void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
 630                           region_model_context *ctxt) const;
 631
 632   /* Implemented in bounds-checking.cc  */
 633   bool check_symbolic_bounds (const region *base_reg,
 634                               const svalue *sym_byte_offset,
 635                               const svalue *num_bytes_sval,
 636                               const svalue *capacity,
 637                               enum access_direction dir,
 638                               const svalue *sval_hint,
 639                               region_model_context *ctxt) const;
 640   bool check_region_bounds (const region *reg, enum access_direction dir,
 641                             const svalue *sval_hint,
 642                             region_model_context *ctxt) const;
 643
 644   void check_call_args (const call_details &cd) const;
 645   void check_call_format_attr (const call_details &cd,
 646                                tree format_attr) const;
 647   void check_external_function_for_access_attr (const gcall *call,
 648                                                 tree callee_fndecl,
 649                                                 region_model_context *ctxt) const;
 650
 651   static auto_vec<pop_frame_callback> pop_frame_callbacks;
 652   /* Storing this here to avoid passing it around everywhere.  */
 653   region_model_manager *const m_mgr;
 654
 655   store m_store;
 656
 657   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 658
 659   const frame_region *m_current_frame;
 660
 661   /* Map from base region to size in bytes, for tracking the sizes of
 662      dynamically-allocated regions.
 663      This is part of the region_model rather than the region to allow for
 664      memory regions to be resized (e.g. by realloc).  */
 665   dynamic_extents_t m_dynamic_extents;
 666 };
 667
 668 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 669    uninitialized value).  This abstract base class encapsulates an interface
 670    for the region model to use when emitting such warnings.
 671
 672    Having this as an abstract base class allows us to support the various
 673    operations needed by program_state in the analyzer within region_model,
 674    whilst keeping them somewhat modularized.  */
 675
 676 class region_model_context
 677 {
 678  public:
 679   /* Hook for clients to store pending diagnostics.
 680      Return true if the diagnostic was stored, or false if it was deleted.
 681      Optionally provide a custom stmt_finder.  */
 682   virtual bool warn (std::unique_ptr<pending_diagnostic> d,
 683                      const stmt_finder *custom_finder = NULL) = 0;
 684
 685   /* Hook for clients to add a note to the last previously stored
 686      pending diagnostic.  */
 687   virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
 688
 689   /* Hook for clients to add an event to the last previously stored
 690      pending diagnostic.  */
 691   virtual void add_event (std::unique_ptr<checker_event> event) = 0;
 692
 693   /* Hook for clients to be notified when an SVAL that was reachable
 694      in a previous state is no longer live, so that clients can emit warnings
 695      about leaks.  */
 696   virtual void on_svalue_leak (const svalue *sval) = 0;
 697
 698   /* Hook for clients to be notified when the set of explicitly live
 699      svalues changes, so that they can purge state relating to dead
 700      svalues.  */
 701   virtual void on_liveness_change (const svalue_set &live_svalues,
 702                                    const region_model *model) = 0;
 703
 704   virtual logger *get_logger () = 0;
 705
 706   /* Hook for clients to be notified when the condition
 707      "LHS OP RHS" is added to the region model.
 708      This exists so that state machines can detect tests on edges,
 709      and use them to trigger sm-state transitions (e.g. transitions due
 710      to ptrs becoming known to be NULL or non-NULL, rather than just
 711      "unchecked") */
 712   virtual void on_condition (const svalue *lhs,
 713                              enum tree_code op,
 714                              const svalue *rhs) = 0;
 715
 716   /* Hook for clients to be notified when the condition that
 717      SVAL is within RANGES is added to the region model.
 718      Similar to on_condition, but for use when handling switch statements.
 719      RANGES is non-empty.  */
 720   virtual void on_bounded_ranges (const svalue &sval,
 721                                   const bounded_ranges &ranges) = 0;
 722
 723   /* Hook for clients to be notified when a frame is popped from the stack.  */
 724   virtual void on_pop_frame (const frame_region *) = 0;
 725
 726   /* Hooks for clients to be notified when an unknown change happens
 727      to SVAL (in response to a call to an unknown function).  */
 728   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 729
 730   /* Hooks for clients to be notified when a phi node is handled,
 731      where RHS is the pertinent argument.  */
 732   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 733
 734   /* Hooks for clients to be notified when the region model doesn't
 735      know how to handle the tree code of T at LOC.  */
 736   virtual void on_unexpected_tree_code (tree t,
 737                                         const dump_location_t &loc) = 0;
 738
 739   /* Hook for clients to be notified when a function_decl escapes.  */
 740   virtual void on_escaped_function (tree fndecl) = 0;
 741
 742   virtual uncertainty_t *get_uncertainty () = 0;
 743
 744   /* Hook for clients to purge state involving SVAL.  */
 745   virtual void purge_state_involving (const svalue *sval) = 0;
 746
 747   /* Hook for clients to split state with a non-standard path.  */
 748   virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
 749
 750   /* Hook for clients to terminate the standard path.  */
 751   virtual void terminate_path () = 0;
 752
 753   virtual const extrinsic_state *get_ext_state () const = 0;
 754
 755   /* Hook for clients to access the a specific state machine in
 756      any underlying program_state.  */
 757   virtual bool
 758   get_state_map_by_name (const char *name,
 759                          sm_state_map **out_smap,
 760                          const state_machine **out_sm,
 761                          unsigned *out_sm_idx,
 762                          std::unique_ptr<sm_context> *out_sm_context) = 0;
 763
 764   /* Precanned ways for clients to access specific state machines.  */
 765   bool get_fd_map (sm_state_map **out_smap,
 766                    const state_machine **out_sm,
 767                    unsigned *out_sm_idx,
 768                    std::unique_ptr<sm_context> *out_sm_context)
 769   {
 770     return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
 771                                   out_sm_idx, out_sm_context);
 772   }
 773   bool get_malloc_map (sm_state_map **out_smap,
 774                        const state_machine **out_sm,
 775                        unsigned *out_sm_idx)
 776   {
 777     return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx, NULL);
 778   }
 779   bool get_taint_map (sm_state_map **out_smap,
 780                       const state_machine **out_sm,
 781                       unsigned *out_sm_idx)
 782   {
 783     return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx, NULL);
 784   }
 785
 786   bool possibly_tainted_p (const svalue *sval);
 787
 788   /* Get the current statement, if any.  */
 789   virtual const gimple *get_stmt () const = 0;
 790
 791   virtual const exploded_graph *get_eg () const = 0;
 792 };
 793
 794 /* A "do nothing" subclass of region_model_context.  */
 795
 796 class noop_region_model_context : public region_model_context
 797 {
 798 public:
 799   bool warn (std::unique_ptr<pending_diagnostic>,
 800              const stmt_finder *) override { return false; }
 801   void add_note (std::unique_ptr<pending_note>) override;
 802   void add_event (std::unique_ptr<checker_event>) override;
 803   void on_svalue_leak (const svalue *) override {}
 804   void on_liveness_change (const svalue_set &,
 805                            const region_model *) override {}
 806   logger *get_logger () override { return NULL; }
 807   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
 808                      enum tree_code op ATTRIBUTE_UNUSED,
 809                      const svalue *rhs ATTRIBUTE_UNUSED) override
 810   {
 811   }
 812   void on_bounded_ranges (const svalue &,
 813                           const bounded_ranges &) override
 814   {
 815   }
 816   void on_pop_frame (const frame_region *) override {}
 817   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 818                           bool is_mutable ATTRIBUTE_UNUSED) override
 819   {
 820   }
 821   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 822                tree rhs ATTRIBUTE_UNUSED) override
 823   {
 824   }
 825   void on_unexpected_tree_code (tree, const dump_location_t &) override {}
 826
 827   void on_escaped_function (tree) override {}
 828
 829   uncertainty_t *get_uncertainty () override { return NULL; }
 830
 831   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
 832
 833   void bifurcate (std::unique_ptr<custom_edge_info> info) override;
 834   void terminate_path () override;
 835
 836   const extrinsic_state *get_ext_state () const override { return NULL; }
 837
 838   bool get_state_map_by_name (const char *,
 839                               sm_state_map **,
 840                               const state_machine **,
 841                               unsigned *,
 842                               std::unique_ptr<sm_context> *) override
 843   {
 844     return false;
 845   }
 846
 847   const gimple *get_stmt () const override { return NULL; }
 848   const exploded_graph *get_eg () const override { return NULL; }
 849 };
 850
 851 /* A subclass of region_model_context for determining if operations fail
 852    e.g. "can we generate a region for the lvalue of EXPR?".  */
 853
 854 class tentative_region_model_context : public noop_region_model_context
 855 {
 856 public:
 857   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 858
 859   void on_unexpected_tree_code (tree, const dump_location_t &)
 860     final override
 861   {
 862     m_num_unexpected_codes++;
 863   }
 864
 865   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 866
 867 private:
 868   int m_num_unexpected_codes;
 869 };
 870
 871 /* Subclass of region_model_context that wraps another context, allowing
 872    for extra code to be added to the various hooks.  */
 873
 874 class region_model_context_decorator : public region_model_context
 875 {
 876  public:
 877   bool warn (std::unique_ptr<pending_diagnostic> d,
 878              const stmt_finder *custom_finder)
 879   {
 880     if (m_inner)
 881       return m_inner->warn (std::move (d), custom_finder);
 882     else
 883       return false;
 884   }
 885
 886   void add_note (std::unique_ptr<pending_note> pn) override
 887   {
 888     if (m_inner)
 889       m_inner->add_note (std::move (pn));
 890   }
 891   void add_event (std::unique_ptr<checker_event> event) override;
 892
 893   void on_svalue_leak (const svalue *sval) override
 894   {
 895     if (m_inner)
 896       m_inner->on_svalue_leak (sval);
 897   }
 898
 899   void on_liveness_change (const svalue_set &live_svalues,
 900                            const region_model *model) override
 901   {
 902     if (m_inner)
 903       m_inner->on_liveness_change (live_svalues, model);
 904   }
 905
 906   logger *get_logger () override
 907   {
 908     if (m_inner)
 909       return m_inner->get_logger ();
 910     else
 911       return nullptr;
 912   }
 913
 914   void on_condition (const svalue *lhs,
 915                      enum tree_code op,
 916                      const svalue *rhs) override
 917   {
 918     if (m_inner)
 919       m_inner->on_condition (lhs, op, rhs);
 920   }
 921
 922   void on_bounded_ranges (const svalue &sval,
 923                           const bounded_ranges &ranges) override
 924   {
 925     if (m_inner)
 926       m_inner->on_bounded_ranges (sval, ranges);
 927   }
 928
 929   void on_pop_frame (const frame_region *frame_reg) override
 930   {
 931     if (m_inner)
 932       m_inner->on_pop_frame (frame_reg);
 933   }
 934
 935   void on_unknown_change (const svalue *sval, bool is_mutable) override
 936   {
 937     if (m_inner)
 938       m_inner->on_unknown_change (sval, is_mutable);
 939   }
 940
 941   void on_phi (const gphi *phi, tree rhs) override
 942   {
 943     if (m_inner)
 944       m_inner->on_phi (phi, rhs);
 945   }
 946
 947   void on_unexpected_tree_code (tree t,
 948                                 const dump_location_t &loc) override
 949   {
 950     if (m_inner)
 951       m_inner->on_unexpected_tree_code (t, loc);
 952   }
 953
 954   void on_escaped_function (tree fndecl) override
 955   {
 956     if (m_inner)
 957       m_inner->on_escaped_function (fndecl);
 958   }
 959
 960   uncertainty_t *get_uncertainty () override
 961   {
 962     if (m_inner)
 963       return m_inner->get_uncertainty ();
 964     else
 965       return nullptr;
 966   }
 967
 968   void purge_state_involving (const svalue *sval) override
 969   {
 970     if (m_inner)
 971       m_inner->purge_state_involving (sval);
 972   }
 973
 974   void bifurcate (std::unique_ptr<custom_edge_info> info) override
 975   {
 976     if (m_inner)
 977       m_inner->bifurcate (std::move (info));
 978   }
 979
 980   void terminate_path () override
 981   {
 982     if (m_inner)
 983       m_inner->terminate_path ();
 984   }
 985
 986   const extrinsic_state *get_ext_state () const override
 987   {
 988     if (m_inner)
 989       return m_inner->get_ext_state ();
 990     else
 991       return nullptr;
 992   }
 993
 994   bool get_state_map_by_name (const char *name,
 995                               sm_state_map **out_smap,
 996                               const state_machine **out_sm,
 997                               unsigned *out_sm_idx,
 998                               std::unique_ptr<sm_context> *out_sm_context)
 999     override
1000   {
1001     if (m_inner)
1002       return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
1003                                              out_sm_context);
1004     else
1005       return false;
1006   }
1007
1008   const gimple *get_stmt () const override
1009   {
1010     if (m_inner)
1011       return m_inner->get_stmt ();
1012     else
1013       return nullptr;
1014   }
1015
1016   const exploded_graph *get_eg () const override
1017   {
1018     if (m_inner)
1019         return m_inner->get_eg ();
1020     else
1021         return nullptr;
1022   }
1023
1024 protected:
1025   region_model_context_decorator (region_model_context *inner)
1026   : m_inner (inner)
1027   {
1028   }
1029
1030   region_model_context *m_inner;
1031 };
1032
1033 /* Subclass of region_model_context_decorator with a hook for adding
1034    notes/events when saving diagnostics.  */
1035
1036 class annotating_context : public region_model_context_decorator
1037 {
1038 public:
1039   bool warn (std::unique_ptr<pending_diagnostic> d,
1040              const stmt_finder *custom_finder) override
1041   {
1042     if (m_inner)
1043       if (m_inner->warn (std::move (d), custom_finder))
1044         {
1045           add_annotations ();
1046           return true;
1047         }
1048     return false;
1049   }
1050
1051   /* Hook to add new event(s)/note(s)  */
1052   virtual void add_annotations () = 0;
1053
1054 protected:
1055   annotating_context (region_model_context *inner)
1056   : region_model_context_decorator (inner)
1057   {
1058   }
1059 };
1060
1061 /* A bundle of data for use when attempting to merge two region_model
1062    instances to make a third.  */
1063
1064 struct model_merger
1065 {
1066   model_merger (const region_model *model_a,
1067                 const region_model *model_b,
1068                 const program_point &point,
1069                 region_model *merged_model,
1070                 const extrinsic_state *ext_state,
1071                 const program_state *state_a,
1072                 const program_state *state_b)
1073   : m_model_a (model_a), m_model_b (model_b),
1074     m_point (point),
1075     m_merged_model (merged_model),
1076     m_ext_state (ext_state),
1077     m_state_a (state_a), m_state_b (state_b)
1078   {
1079   }
1080
1081   void dump_to_pp (pretty_printer *pp, bool simple) const;
1082   void dump (FILE *fp, bool simple) const;
1083   void dump (bool simple) const;
1084
1085   region_model_manager *get_manager () const
1086   {
1087     return m_model_a->get_manager ();
1088   }
1089
1090   bool mergeable_svalue_p (const svalue *) const;
1091   const function_point &get_function_point () const
1092   {
1093     return m_point.get_function_point ();
1094   }
1095
1096   const region_model *m_model_a;
1097   const region_model *m_model_b;
1098   const program_point &m_point;
1099   region_model *m_merged_model;
1100
1101   const extrinsic_state *m_ext_state;
1102   const program_state *m_state_a;
1103   const program_state *m_state_b;
1104 };
1105
1106 /* A record that can (optionally) be written out when
1107    region_model::add_constraint fails.  */
1108
1109 class rejected_constraint
1110 {
1111 public:
1112   virtual ~rejected_constraint () {}
1113   virtual void dump_to_pp (pretty_printer *pp) const = 0;
1114
1115   const region_model &get_model () const { return m_model; }
1116
1117 protected:
1118   rejected_constraint (const region_model &model)
1119   : m_model (model)
1120   {}
1121
1122   region_model m_model;
1123 };
1124
1125 class rejected_op_constraint : public rejected_constraint
1126 {
1127 public:
1128   rejected_op_constraint (const region_model &model,
1129                           tree lhs, enum tree_code op, tree rhs)
1130   : rejected_constraint (model),
1131     m_lhs (lhs), m_op (op), m_rhs (rhs)
1132   {}
1133
1134   void dump_to_pp (pretty_printer *pp) const final override;
1135
1136   tree m_lhs;
1137   enum tree_code m_op;
1138   tree m_rhs;
1139 };
1140
1141 class rejected_default_case : public rejected_constraint
1142 {
1143 public:
1144   rejected_default_case (const region_model &model)
1145   : rejected_constraint (model)
1146   {}
1147
1148   void dump_to_pp (pretty_printer *pp) const final override;
1149 };
1150
1151 class rejected_ranges_constraint : public rejected_constraint
1152 {
1153 public:
1154   rejected_ranges_constraint (const region_model &model,
1155                               tree expr, const bounded_ranges *ranges)
1156   : rejected_constraint (model),
1157     m_expr (expr), m_ranges (ranges)
1158   {}
1159
1160   void dump_to_pp (pretty_printer *pp) const final override;
1161
1162 private:
1163   tree m_expr;
1164   const bounded_ranges *m_ranges;
1165 };
1166
1167 /* A bundle of state.  */
1168
1169 class engine
1170 {
1171 public:
1172   engine (const supergraph *sg = NULL, logger *logger = NULL);
1173   const supergraph *get_supergraph () { return m_sg; }
1174   region_model_manager *get_model_manager () { return &m_mgr; }
1175   known_function_manager *get_known_function_manager ()
1176   {
1177     return m_mgr.get_known_function_manager ();
1178   }
1179
1180   void log_stats (logger *logger) const;
1181
1182 private:
1183   const supergraph *m_sg;
1184   region_model_manager m_mgr;
1185 };
1186
1187 } // namespace ana
1188
1189 extern void debug (const region_model &rmodel);
1190
1191 namespace ana {
1192
1193 #if CHECKING_P
1194
1195 namespace selftest {
1196
1197 using namespace ::selftest;
1198
1199 /* An implementation of region_model_context for use in selftests, which
1200    stores any pending_diagnostic instances passed to it.  */
1201
1202 class test_region_model_context : public noop_region_model_context
1203 {
1204 public:
1205   bool warn (std::unique_ptr<pending_diagnostic> d,
1206              const stmt_finder *) final override
1207   {
1208     m_diagnostics.safe_push (d.release ());
1209     return true;
1210   }
1211
1212   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1213
1214   void on_unexpected_tree_code (tree t, const dump_location_t &)
1215     final override
1216   {
1217     internal_error ("unhandled tree code: %qs",
1218                     get_tree_code_name (TREE_CODE (t)));
1219   }
1220
1221 private:
1222   /* Implicitly delete any diagnostics in the dtor.  */
1223   auto_delete_vec<pending_diagnostic> m_diagnostics;
1224 };
1225
1226 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1227    Verify that MODEL remains satisfiable.  */
1228
1229 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1230   SELFTEST_BEGIN_STMT                                   \
1231     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1232     ASSERT_TRUE (sat);                                  \
1233   SELFTEST_END_STMT
1234
1235 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1236    Verify that the result is not satisfiable.  */
1237
1238 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
1239   SELFTEST_BEGIN_STMT                                   \
1240     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1241     ASSERT_FALSE (sat);                         \
1242   SELFTEST_END_STMT
1243
1244 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
1245
1246 void assert_condition (const location &loc,
1247                        region_model &model,
1248                        const svalue *lhs, tree_code op, const svalue *rhs,
1249                        tristate expected);
1250
1251 void assert_condition (const location &loc,
1252                        region_model &model,
1253                        tree lhs, tree_code op, tree rhs,
1254                        tristate expected);
1255
1256 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1257    as "true".  */
1258
1259 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1260   SELFTEST_BEGIN_STMT                                                   \
1261   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1262                     tristate (tristate::TS_TRUE));              \
1263   SELFTEST_END_STMT
1264
1265 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1266    as "false".  */
1267
1268 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1269   SELFTEST_BEGIN_STMT                                                   \
1270   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1271                     tristate (tristate::TS_FALSE));             \
1272   SELFTEST_END_STMT
1273
1274 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1275    as "unknown".  */
1276
1277 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1278   SELFTEST_BEGIN_STMT                                                   \
1279   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1280                     tristate (tristate::TS_UNKNOWN));           \
1281   SELFTEST_END_STMT
1282
1283 } /* end of namespace selftest.  */
1284
1285 #endif /* #if CHECKING_P */
1286
1287 } // namespace ana
1288
1289 #endif /* GCC_ANALYZER_REGION_MODEL_H */