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