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