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 "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 /* A region_model encapsulates a representation of the state of memory, with
 240    a tree of regions, along with their associated values.
 241    The representation is graph-like because values can be pointers to
 242    regions.
 243    It also stores:
 244    - a constraint_manager, capturing relationships between the values, and
 245    - dynamic extents, mapping dynamically-allocated regions to svalues (their
 246    capacities).  */
 247
 248 class region_model
 249 {
 250  public:
 251   typedef region_to_value_map dynamic_extents_t;
 252
 253   region_model (region_model_manager *mgr);
 254   region_model (const region_model &other);
 255   ~region_model ();
 256   region_model &operator= (const region_model &other);
 257
 258   bool operator== (const region_model &other) const;
 259   bool operator!= (const region_model &other) const
 260   {
 261     return !(*this == other);
 262   }
 263
 264   hashval_t hash () const;
 265
 266   void print (pretty_printer *pp) const;
 267
 268   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 269   void dump (FILE *fp, bool simple, bool multiline) const;
 270   void dump (bool simple) const;
 271
 272   void debug () const;
 273
 274   void validate () const;
 275
 276   void canonicalize ();
 277   bool canonicalized_p () const;
 278
 279   void
 280   on_stmt_pre (const gimple *stmt,
 281                bool *out_unknown_side_effects,
 282                region_model_context *ctxt);
 283
 284   void on_assignment (const gassign *stmt, region_model_context *ctxt);
 285   const svalue *get_gassign_result (const gassign *assign,
 286                                     region_model_context *ctxt);
 287   void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
 288   bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
 289   void on_call_post (const gcall *stmt,
 290                      bool unknown_side_effects,
 291                      region_model_context *ctxt);
 292
 293   void purge_state_involving (const svalue *sval, region_model_context *ctxt);
 294
 295   void impl_deallocation_call (const call_details &cd);
 296
 297   const svalue *maybe_get_copy_bounds (const region *src_reg,
 298                                        const svalue *num_bytes_sval);
 299   void update_for_int_cst_return (const call_details &cd,
 300                                   int retval,
 301                                   bool unmergeable);
 302   void update_for_zero_return (const call_details &cd,
 303                                bool unmergeable);
 304   void update_for_nonzero_return (const call_details &cd);
 305
 306   void handle_unrecognized_call (const gcall *call,
 307                                  region_model_context *ctxt);
 308   void get_reachable_svalues (svalue_set *out,
 309                               const svalue *extra_sval,
 310                               const uncertainty_t *uncertainty);
 311
 312   void on_return (const greturn *stmt, region_model_context *ctxt);
 313   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 314                   region_model_context *ctxt);
 315   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 316                    int setjmp_stack_depth, region_model_context *ctxt);
 317
 318   void update_for_phis (const supernode *snode,
 319                         const cfg_superedge *last_cfg_superedge,
 320                         region_model_context *ctxt);
 321
 322   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 323                    const region_model &old_state,
 324                    region_model_context *ctxt);
 325
 326   bool maybe_update_for_edge (const superedge &edge,
 327                               const gimple *last_stmt,
 328                               region_model_context *ctxt,
 329                               rejected_constraint **out);
 330
 331   void update_for_gcall (const gcall *call_stmt,
 332                          region_model_context *ctxt,
 333                          function *callee = NULL);
 334
 335   void update_for_return_gcall (const gcall *call_stmt,
 336                                 region_model_context *ctxt);
 337
 338   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 339                             region_model_context *ctxt);
 340   const frame_region *get_current_frame () const { return m_current_frame; }
 341   function * get_current_function () const;
 342   void pop_frame (tree result_lvalue,
 343                   const svalue **out_result,
 344                   region_model_context *ctxt);
 345   int get_stack_depth () const;
 346   const frame_region *get_frame_at_index (int index) const;
 347
 348   const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
 349   const region *get_lvalue (tree expr, region_model_context *ctxt) const;
 350   const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
 351   const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
 352
 353   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 354                                region_model_context *ctxt) const;
 355
 356   const svalue *get_rvalue_for_bits (tree type,
 357                                      const region *reg,
 358                                      const bit_range &bits,
 359                                      region_model_context *ctxt) const;
 360
 361   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 362                   region_model_context *ctxt);
 363   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 364   void clobber_region (const region *reg);
 365   void purge_region (const region *reg);
 366   void fill_region (const region *reg, const svalue *sval);
 367   void zero_fill_region (const region *reg);
 368   void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 369
 370   tristate eval_condition (const svalue *lhs,
 371                            enum tree_code op,
 372                            const svalue *rhs) const;
 373   tristate compare_initial_and_pointer (const initial_svalue *init,
 374                                         const region_svalue *ptr) const;
 375   tristate symbolic_greater_than (const binop_svalue *a,
 376                                   const svalue *b) const;
 377   tristate structural_equality (const svalue *a, const svalue *b) const;
 378   tristate eval_condition (tree lhs,
 379                            enum tree_code op,
 380                            tree rhs,
 381                            region_model_context *ctxt) const;
 382   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 383                        region_model_context *ctxt);
 384   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 385                        region_model_context *ctxt,
 386                        rejected_constraint **out);
 387
 388   const region *
 389   get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
 390                                        region_model_context *ctxt);
 391   const region *create_region_for_alloca (const svalue *size_in_bytes,
 392                                           region_model_context *ctxt);
 393   void get_referenced_base_regions (auto_bitmap &out_ids) const;
 394
 395   tree get_representative_tree (const svalue *sval) const;
 396   tree get_representative_tree (const region *reg) const;
 397   path_var
 398   get_representative_path_var (const svalue *sval,
 399                                svalue_set *visited) const;
 400   path_var
 401   get_representative_path_var (const region *reg,
 402                                svalue_set *visited) const;
 403
 404   /* For selftests.  */
 405   constraint_manager *get_constraints ()
 406   {
 407     return m_constraints;
 408   }
 409
 410   store *get_store () { return &m_store; }
 411   const store *get_store () const { return &m_store; }
 412
 413   const dynamic_extents_t &
 414   get_dynamic_extents () const
 415   {
 416     return m_dynamic_extents;
 417   }
 418   const svalue *get_dynamic_extents (const region *reg) const;
 419   void set_dynamic_extents (const region *reg,
 420                             const svalue *size_in_bytes,
 421                             region_model_context *ctxt);
 422   void unset_dynamic_extents (const region *reg);
 423
 424   region_model_manager *get_manager () const { return m_mgr; }
 425   bounded_ranges_manager *get_range_manager () const
 426   {
 427     return m_mgr->get_range_manager ();
 428   }
 429
 430   void unbind_region_and_descendents (const region *reg,
 431                                       enum poison_kind pkind);
 432
 433   bool can_merge_with_p (const region_model &other_model,
 434                          const program_point &point,
 435                          region_model *out_model,
 436                          const extrinsic_state *ext_state = NULL,
 437                          const program_state *state_a = NULL,
 438                          const program_state *state_b = NULL) const;
 439
 440   tree get_fndecl_for_call (const gcall *call,
 441                             region_model_context *ctxt);
 442
 443   void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
 444   static void append_regions_cb (const region *base_reg,
 445                                  struct append_regions_cb_data *data);
 446
 447   const svalue *get_store_value (const region *reg,
 448                                  region_model_context *ctxt) const;
 449
 450   bool region_exists_p (const region *reg) const;
 451
 452   void loop_replay_fixup (const region_model *dst_state);
 453
 454   const svalue *get_capacity (const region *reg) const;
 455
 456   const svalue *get_string_size (const svalue *sval) const;
 457   const svalue *get_string_size (const region *reg) const;
 458
 459   bool replay_call_summary (call_summary_replay &r,
 460                             const region_model &summary);
 461
 462   void maybe_complain_about_infoleak (const region *dst_reg,
 463                                       const svalue *copied_sval,
 464                                       const region *src_reg,
 465                                       region_model_context *ctxt);
 466
 467   void set_errno (const call_details &cd);
 468
 469   /* Implemented in sm-fd.cc  */
 470   void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
 471
 472   /* Implemented in sm-malloc.cc  */
 473   void on_realloc_with_move (const call_details &cd,
 474                              const svalue *old_ptr_sval,
 475                              const svalue *new_ptr_sval);
 476
 477   /* Implemented in sm-taint.cc.  */
 478   void mark_as_tainted (const svalue *sval,
 479                         region_model_context *ctxt);
 480
 481   bool add_constraint (const svalue *lhs,
 482                        enum tree_code op,
 483                        const svalue *rhs,
 484                        region_model_context *ctxt);
 485
 486   const svalue *check_for_poison (const svalue *sval,
 487                                   tree expr,
 488                                   const region *src_region,
 489                                   region_model_context *ctxt) const;
 490
 491   void check_region_for_write (const region *dest_reg,
 492                                region_model_context *ctxt) const;
 493
 494 private:
 495   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 496   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 497
 498   path_var
 499   get_representative_path_var_1 (const svalue *sval,
 500                                  svalue_set *visited) const;
 501   path_var
 502   get_representative_path_var_1 (const region *reg,
 503                                  svalue_set *visited) const;
 504
 505   const known_function *get_known_function (tree fndecl,
 506                                             const call_details &cd) const;
 507   const known_function *get_known_function (enum internal_fn) const;
 508
 509   bool add_constraints_from_binop (const svalue *outer_lhs,
 510                                    enum tree_code outer_op,
 511                                    const svalue *outer_rhs,
 512                                    bool *out,
 513                                    region_model_context *ctxt);
 514
 515   void update_for_call_superedge (const call_superedge &call_edge,
 516                                   region_model_context *ctxt);
 517   void update_for_return_superedge (const return_superedge &return_edge,
 518                                     region_model_context *ctxt);
 519   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 520                                     const gcond *cond_stmt,
 521                                     region_model_context *ctxt,
 522                                     rejected_constraint **out);
 523   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 524                                       const gswitch *switch_stmt,
 525                                       region_model_context *ctxt,
 526                                       rejected_constraint **out);
 527   bool apply_constraints_for_exception (const gimple *last_stmt,
 528                                         region_model_context *ctxt,
 529                                         rejected_constraint **out);
 530
 531   int poison_any_pointers_to_descendents (const region *reg,
 532                                           enum poison_kind pkind);
 533
 534   void on_top_level_param (tree param,
 535                            bool nonnull,
 536                            region_model_context *ctxt);
 537
 538   bool called_from_main_p () const;
 539   const svalue *get_initial_value_for_global (const region *reg) const;
 540
 541   const region * get_region_for_poisoned_expr (tree expr) const;
 542
 543   void check_dynamic_size_for_taint (enum memory_space mem_space,
 544                                      const svalue *size_in_bytes,
 545                                      region_model_context *ctxt) const;
 546   void check_dynamic_size_for_floats (const svalue *size_in_bytes,
 547                                       region_model_context *ctxt) const;
 548
 549   void check_region_for_taint (const region *reg,
 550                                enum access_direction dir,
 551                                region_model_context *ctxt) const;
 552
 553   void check_for_writable_region (const region* dest_reg,
 554                                   region_model_context *ctxt) const;
 555   void check_region_access (const region *reg,
 556                             enum access_direction dir,
 557                             region_model_context *ctxt) const;
 558   void check_region_for_read (const region *src_reg,
 559                               region_model_context *ctxt) const;
 560   void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
 561                           region_model_context *ctxt) const;
 562
 563   /* Implemented in bounds-checking.cc  */
 564   void check_symbolic_bounds (const region *base_reg,
 565                               const svalue *sym_byte_offset,
 566                               const svalue *num_bytes_sval,
 567                               const svalue *capacity,
 568                               enum access_direction dir,
 569                               region_model_context *ctxt) const;
 570   void check_region_bounds (const region *reg, enum access_direction dir,
 571                             region_model_context *ctxt) const;
 572
 573   void check_call_args (const call_details &cd) const;
 574   void check_external_function_for_access_attr (const gcall *call,
 575                                                 tree callee_fndecl,
 576                                                 region_model_context *ctxt) const;
 577
 578   /* Storing this here to avoid passing it around everywhere.  */
 579   region_model_manager *const m_mgr;
 580
 581   store m_store;
 582
 583   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 584
 585   const frame_region *m_current_frame;
 586
 587   /* Map from base region to size in bytes, for tracking the sizes of
 588      dynamically-allocated regions.
 589      This is part of the region_model rather than the region to allow for
 590      memory regions to be resized (e.g. by realloc).  */
 591   dynamic_extents_t m_dynamic_extents;
 592 };
 593
 594 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 595    uninitialized value).  This abstract base class encapsulates an interface
 596    for the region model to use when emitting such warnings.
 597
 598    Having this as an abstract base class allows us to support the various
 599    operations needed by program_state in the analyzer within region_model,
 600    whilst keeping them somewhat modularized.  */
 601
 602 class region_model_context
 603 {
 604  public:
 605   /* Hook for clients to store pending diagnostics.
 606      Return true if the diagnostic was stored, or false if it was deleted.  */
 607   virtual bool warn (std::unique_ptr<pending_diagnostic> d) = 0;
 608
 609   /* Hook for clients to add a note to the last previously stored
 610      pending diagnostic.  */
 611   virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
 612
 613   /* Hook for clients to be notified when an SVAL that was reachable
 614      in a previous state is no longer live, so that clients can emit warnings
 615      about leaks.  */
 616   virtual void on_svalue_leak (const svalue *sval) = 0;
 617
 618   /* Hook for clients to be notified when the set of explicitly live
 619      svalues changes, so that they can purge state relating to dead
 620      svalues.  */
 621   virtual void on_liveness_change (const svalue_set &live_svalues,
 622                                    const region_model *model) = 0;
 623
 624   virtual logger *get_logger () = 0;
 625
 626   /* Hook for clients to be notified when the condition
 627      "LHS OP RHS" is added to the region model.
 628      This exists so that state machines can detect tests on edges,
 629      and use them to trigger sm-state transitions (e.g. transitions due
 630      to ptrs becoming known to be NULL or non-NULL, rather than just
 631      "unchecked") */
 632   virtual void on_condition (const svalue *lhs,
 633                              enum tree_code op,
 634                              const svalue *rhs) = 0;
 635
 636   /* Hook for clients to be notified when the condition that
 637      SVAL is within RANGES is added to the region model.
 638      Similar to on_condition, but for use when handling switch statements.
 639      RANGES is non-empty.  */
 640   virtual void on_bounded_ranges (const svalue &sval,
 641                                   const bounded_ranges &ranges) = 0;
 642
 643   /* Hook for clients to be notified when a frame is popped from the stack.  */
 644   virtual void on_pop_frame (const frame_region *) = 0;
 645
 646   /* Hooks for clients to be notified when an unknown change happens
 647      to SVAL (in response to a call to an unknown function).  */
 648   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 649
 650   /* Hooks for clients to be notified when a phi node is handled,
 651      where RHS is the pertinent argument.  */
 652   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 653
 654   /* Hooks for clients to be notified when the region model doesn't
 655      know how to handle the tree code of T at LOC.  */
 656   virtual void on_unexpected_tree_code (tree t,
 657                                         const dump_location_t &loc) = 0;
 658
 659   /* Hook for clients to be notified when a function_decl escapes.  */
 660   virtual void on_escaped_function (tree fndecl) = 0;
 661
 662   virtual uncertainty_t *get_uncertainty () = 0;
 663
 664   /* Hook for clients to purge state involving SVAL.  */
 665   virtual void purge_state_involving (const svalue *sval) = 0;
 666
 667   /* Hook for clients to split state with a non-standard path.  */
 668   virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
 669
 670   /* Hook for clients to terminate the standard path.  */
 671   virtual void terminate_path () = 0;
 672
 673   virtual const extrinsic_state *get_ext_state () const = 0;
 674
 675   /* Hook for clients to access the a specific state machine in
 676      any underlying program_state.  */
 677   virtual bool
 678   get_state_map_by_name (const char *name,
 679                          sm_state_map **out_smap,
 680                          const state_machine **out_sm,
 681                          unsigned *out_sm_idx,
 682                          std::unique_ptr<sm_context> *out_sm_context) = 0;
 683
 684   /* Precanned ways for clients to access specific state machines.  */
 685   bool get_fd_map (sm_state_map **out_smap,
 686                    const state_machine **out_sm,
 687                    unsigned *out_sm_idx,
 688                    std::unique_ptr<sm_context> *out_sm_context)
 689   {
 690     return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
 691                                   out_sm_idx, out_sm_context);
 692   }
 693   bool get_malloc_map (sm_state_map **out_smap,
 694                        const state_machine **out_sm,
 695                        unsigned *out_sm_idx)
 696   {
 697     return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx, NULL);
 698   }
 699   bool get_taint_map (sm_state_map **out_smap,
 700                       const state_machine **out_sm,
 701                       unsigned *out_sm_idx)
 702   {
 703     return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx, NULL);
 704   }
 705
 706   bool possibly_tainted_p (const svalue *sval);
 707
 708   /* Get the current statement, if any.  */
 709   virtual const gimple *get_stmt () const = 0;
 710 };
 711
 712 /* A "do nothing" subclass of region_model_context.  */
 713
 714 class noop_region_model_context : public region_model_context
 715 {
 716 public:
 717   bool warn (std::unique_ptr<pending_diagnostic>) override { return false; }
 718   void add_note (std::unique_ptr<pending_note>) override;
 719   void on_svalue_leak (const svalue *) override {}
 720   void on_liveness_change (const svalue_set &,
 721                            const region_model *) override {}
 722   logger *get_logger () override { return NULL; }
 723   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
 724                      enum tree_code op ATTRIBUTE_UNUSED,
 725                      const svalue *rhs ATTRIBUTE_UNUSED) override
 726   {
 727   }
 728   void on_bounded_ranges (const svalue &,
 729                           const bounded_ranges &) override
 730   {
 731   }
 732   void on_pop_frame (const frame_region *) override {}
 733   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 734                           bool is_mutable ATTRIBUTE_UNUSED) override
 735   {
 736   }
 737   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 738                tree rhs ATTRIBUTE_UNUSED) override
 739   {
 740   }
 741   void on_unexpected_tree_code (tree, const dump_location_t &) override {}
 742
 743   void on_escaped_function (tree) override {}
 744
 745   uncertainty_t *get_uncertainty () override { return NULL; }
 746
 747   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
 748
 749   void bifurcate (std::unique_ptr<custom_edge_info> info) override;
 750   void terminate_path () override;
 751
 752   const extrinsic_state *get_ext_state () const override { return NULL; }
 753
 754   bool get_state_map_by_name (const char *,
 755                               sm_state_map **,
 756                               const state_machine **,
 757                               unsigned *,
 758                               std::unique_ptr<sm_context> *) override
 759   {
 760     return false;
 761   }
 762
 763   const gimple *get_stmt () const override { return NULL; }
 764 };
 765
 766 /* A subclass of region_model_context for determining if operations fail
 767    e.g. "can we generate a region for the lvalue of EXPR?".  */
 768
 769 class tentative_region_model_context : public noop_region_model_context
 770 {
 771 public:
 772   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 773
 774   void on_unexpected_tree_code (tree, const dump_location_t &)
 775     final override
 776   {
 777     m_num_unexpected_codes++;
 778   }
 779
 780   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 781
 782 private:
 783   int m_num_unexpected_codes;
 784 };
 785
 786 /* Subclass of region_model_context that wraps another context, allowing
 787    for extra code to be added to the various hooks.  */
 788
 789 class region_model_context_decorator : public region_model_context
 790 {
 791  public:
 792   bool warn (std::unique_ptr<pending_diagnostic> d) override
 793   {
 794     return m_inner->warn (std::move (d));
 795   }
 796
 797   void add_note (std::unique_ptr<pending_note> pn) override
 798   {
 799     m_inner->add_note (std::move (pn));
 800   }
 801
 802   void on_svalue_leak (const svalue *sval) override
 803   {
 804     m_inner->on_svalue_leak (sval);
 805   }
 806
 807   void on_liveness_change (const svalue_set &live_svalues,
 808                            const region_model *model) override
 809   {
 810     m_inner->on_liveness_change (live_svalues, model);
 811   }
 812
 813   logger *get_logger () override
 814   {
 815     return m_inner->get_logger ();
 816   }
 817
 818   void on_condition (const svalue *lhs,
 819                      enum tree_code op,
 820                      const svalue *rhs) override
 821   {
 822     m_inner->on_condition (lhs, op, rhs);
 823   }
 824
 825   void on_bounded_ranges (const svalue &sval,
 826                           const bounded_ranges &ranges) override
 827   {
 828     m_inner->on_bounded_ranges (sval, ranges);
 829   }
 830
 831   void on_pop_frame (const frame_region *frame_reg) override
 832   {
 833     m_inner->on_pop_frame (frame_reg);
 834   }
 835
 836   void on_unknown_change (const svalue *sval, bool is_mutable) override
 837   {
 838     m_inner->on_unknown_change (sval, is_mutable);
 839   }
 840
 841   void on_phi (const gphi *phi, tree rhs) override
 842   {
 843     m_inner->on_phi (phi, rhs);
 844   }
 845
 846   void on_unexpected_tree_code (tree t,
 847                                 const dump_location_t &loc) override
 848   {
 849     m_inner->on_unexpected_tree_code (t, loc);
 850   }
 851
 852   void on_escaped_function (tree fndecl) override
 853   {
 854     m_inner->on_escaped_function (fndecl);
 855   }
 856
 857   uncertainty_t *get_uncertainty () override
 858   {
 859     return m_inner->get_uncertainty ();
 860   }
 861
 862   void purge_state_involving (const svalue *sval) override
 863   {
 864     m_inner->purge_state_involving (sval);
 865   }
 866
 867   void bifurcate (std::unique_ptr<custom_edge_info> info) override
 868   {
 869     m_inner->bifurcate (std::move (info));
 870   }
 871
 872   void terminate_path () override
 873   {
 874     m_inner->terminate_path ();
 875   }
 876
 877   const extrinsic_state *get_ext_state () const override
 878   {
 879     return m_inner->get_ext_state ();
 880   }
 881
 882   bool get_state_map_by_name (const char *name,
 883                               sm_state_map **out_smap,
 884                               const state_machine **out_sm,
 885                               unsigned *out_sm_idx,
 886                               std::unique_ptr<sm_context> *out_sm_context)
 887     override
 888   {
 889     return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
 890                                            out_sm_context);
 891   }
 892
 893   const gimple *get_stmt () const override
 894   {
 895     return m_inner->get_stmt ();
 896   }
 897
 898 protected:
 899   region_model_context_decorator (region_model_context *inner)
 900   : m_inner (inner)
 901   {
 902     gcc_assert (m_inner);
 903   }
 904
 905   region_model_context *m_inner;
 906 };
 907
 908 /* Subclass of region_model_context_decorator that adds a note
 909    when saving diagnostics.  */
 910
 911 class note_adding_context : public region_model_context_decorator
 912 {
 913 public:
 914   bool warn (std::unique_ptr<pending_diagnostic> d) override
 915   {
 916     if (m_inner->warn (std::move (d)))
 917       {
 918         add_note (make_note ());
 919         return true;
 920       }
 921     else
 922       return false;
 923   }
 924
 925   /* Hook to make the new note.  */
 926   virtual std::unique_ptr<pending_note> make_note () = 0;
 927
 928 protected:
 929   note_adding_context (region_model_context *inner)
 930   : region_model_context_decorator (inner)
 931   {
 932   }
 933 };
 934
 935 /* A bundle of data for use when attempting to merge two region_model
 936    instances to make a third.  */
 937
 938 struct model_merger
 939 {
 940   model_merger (const region_model *model_a,
 941                 const region_model *model_b,
 942                 const program_point &point,
 943                 region_model *merged_model,
 944                 const extrinsic_state *ext_state,
 945                 const program_state *state_a,
 946                 const program_state *state_b)
 947   : m_model_a (model_a), m_model_b (model_b),
 948     m_point (point),
 949     m_merged_model (merged_model),
 950     m_ext_state (ext_state),
 951     m_state_a (state_a), m_state_b (state_b)
 952   {
 953   }
 954
 955   void dump_to_pp (pretty_printer *pp, bool simple) const;
 956   void dump (FILE *fp, bool simple) const;
 957   void dump (bool simple) const;
 958
 959   region_model_manager *get_manager () const
 960   {
 961     return m_model_a->get_manager ();
 962   }
 963
 964   bool mergeable_svalue_p (const svalue *) const;
 965   const function_point &get_function_point () const
 966   {
 967     return m_point.get_function_point ();
 968   }
 969
 970   const region_model *m_model_a;
 971   const region_model *m_model_b;
 972   const program_point &m_point;
 973   region_model *m_merged_model;
 974
 975   const extrinsic_state *m_ext_state;
 976   const program_state *m_state_a;
 977   const program_state *m_state_b;
 978 };
 979
 980 /* A record that can (optionally) be written out when
 981    region_model::add_constraint fails.  */
 982
 983 class rejected_constraint
 984 {
 985 public:
 986   virtual ~rejected_constraint () {}
 987   virtual void dump_to_pp (pretty_printer *pp) const = 0;
 988
 989   const region_model &get_model () const { return m_model; }
 990
 991 protected:
 992   rejected_constraint (const region_model &model)
 993   : m_model (model)
 994   {}
 995
 996   region_model m_model;
 997 };
 998
 999 class rejected_op_constraint : public rejected_constraint
1000 {
1001 public:
1002   rejected_op_constraint (const region_model &model,
1003                           tree lhs, enum tree_code op, tree rhs)
1004   : rejected_constraint (model),
1005     m_lhs (lhs), m_op (op), m_rhs (rhs)
1006   {}
1007
1008   void dump_to_pp (pretty_printer *pp) const final override;
1009
1010   tree m_lhs;
1011   enum tree_code m_op;
1012   tree m_rhs;
1013 };
1014
1015 class rejected_default_case : public rejected_constraint
1016 {
1017 public:
1018   rejected_default_case (const region_model &model)
1019   : rejected_constraint (model)
1020   {}
1021
1022   void dump_to_pp (pretty_printer *pp) const final override;
1023 };
1024
1025 class rejected_ranges_constraint : public rejected_constraint
1026 {
1027 public:
1028   rejected_ranges_constraint (const region_model &model,
1029                               tree expr, const bounded_ranges *ranges)
1030   : rejected_constraint (model),
1031     m_expr (expr), m_ranges (ranges)
1032   {}
1033
1034   void dump_to_pp (pretty_printer *pp) const final override;
1035
1036 private:
1037   tree m_expr;
1038   const bounded_ranges *m_ranges;
1039 };
1040
1041 /* A bundle of state.  */
1042
1043 class engine
1044 {
1045 public:
1046   engine (const supergraph *sg = NULL, logger *logger = NULL);
1047   const supergraph *get_supergraph () { return m_sg; }
1048   region_model_manager *get_model_manager () { return &m_mgr; }
1049   known_function_manager *get_known_function_manager ()
1050   {
1051     return m_mgr.get_known_function_manager ();
1052   }
1053
1054   void log_stats (logger *logger) const;
1055
1056 private:
1057   const supergraph *m_sg;
1058   region_model_manager m_mgr;
1059 };
1060
1061 } // namespace ana
1062
1063 extern void debug (const region_model &rmodel);
1064
1065 namespace ana {
1066
1067 #if CHECKING_P
1068
1069 namespace selftest {
1070
1071 using namespace ::selftest;
1072
1073 /* An implementation of region_model_context for use in selftests, which
1074    stores any pending_diagnostic instances passed to it.  */
1075
1076 class test_region_model_context : public noop_region_model_context
1077 {
1078 public:
1079   bool warn (std::unique_ptr<pending_diagnostic> d) final override
1080   {
1081     m_diagnostics.safe_push (d.release ());
1082     return true;
1083   }
1084
1085   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1086
1087   void on_unexpected_tree_code (tree t, const dump_location_t &)
1088     final override
1089   {
1090     internal_error ("unhandled tree code: %qs",
1091                     get_tree_code_name (TREE_CODE (t)));
1092   }
1093
1094 private:
1095   /* Implicitly delete any diagnostics in the dtor.  */
1096   auto_delete_vec<pending_diagnostic> m_diagnostics;
1097 };
1098
1099 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1100    Verify that MODEL remains satisfiable.  */
1101
1102 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1103   SELFTEST_BEGIN_STMT                                   \
1104     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1105     ASSERT_TRUE (sat);                                  \
1106   SELFTEST_END_STMT
1107
1108 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1109    Verify that the result is not satisfiable.  */
1110
1111 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
1112   SELFTEST_BEGIN_STMT                                   \
1113     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1114     ASSERT_FALSE (sat);                         \
1115   SELFTEST_END_STMT
1116
1117 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
1118
1119 void assert_condition (const location &loc,
1120                        region_model &model,
1121                        const svalue *lhs, tree_code op, const svalue *rhs,
1122                        tristate expected);
1123
1124 void assert_condition (const location &loc,
1125                        region_model &model,
1126                        tree lhs, tree_code op, tree rhs,
1127                        tristate expected);
1128
1129 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1130    as "true".  */
1131
1132 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1133   SELFTEST_BEGIN_STMT                                                   \
1134   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1135                     tristate (tristate::TS_TRUE));              \
1136   SELFTEST_END_STMT
1137
1138 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1139    as "false".  */
1140
1141 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1142   SELFTEST_BEGIN_STMT                                                   \
1143   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1144                     tristate (tristate::TS_FALSE));             \
1145   SELFTEST_END_STMT
1146
1147 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1148    as "unknown".  */
1149
1150 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1151   SELFTEST_BEGIN_STMT                                                   \
1152   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1153                     tristate (tristate::TS_UNKNOWN));           \
1154   SELFTEST_END_STMT
1155
1156 } /* end of namespace selftest.  */
1157
1158 #endif /* #if CHECKING_P */
1159
1160 } // namespace ana
1161
1162 #endif /* GCC_ANALYZER_REGION_MODEL_H */