gcc/analyzer/region-model.h

   1 /* Classes for modeling the state of memory.
   2    Copyright (C) 2019-2021 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #ifndef GCC_ANALYZER_REGION_MODEL_H
  22 #define GCC_ANALYZER_REGION_MODEL_H
  23
  24 /* Implementation of the region-based ternary model described in:
  25      "A Memory Model for Static Analysis of C Programs"
  26       (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
  27      http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf  */
  28
  29 #include "analyzer/svalue.h"
  30 #include "analyzer/region.h"
  31
  32 using namespace ana;
  33
  34 namespace inchash
  35 {
  36   extern void add_path_var (path_var pv, hash &hstate);
  37 } // namespace inchash
  38
  39 namespace ana {
  40
  41 template <typename T>
  42 class one_way_id_map
  43 {
  44  public:
  45   one_way_id_map (int num_ids);
  46   void put (T src, T dst);
  47   T get_dst_for_src (T src) const;
  48   void dump_to_pp (pretty_printer *pp) const;
  49   void dump () const;
  50   void update (T *) const;
  51
  52  private:
  53   auto_vec<T> m_src_to_dst;
  54  };
  55
  56 /* class one_way_id_map.  */
  57
  58 /* one_way_id_map's ctor, which populates the map with dummy null values.  */
  59
  60 template <typename T>
  61 inline one_way_id_map<T>::one_way_id_map (int num_svalues)
  62 : m_src_to_dst (num_svalues)
  63 {
  64   for (int i = 0; i < num_svalues; i++)
  65     m_src_to_dst.quick_push (T::null ());
  66 }
  67
  68 /* Record that SRC is to be mapped to DST.  */
  69
  70 template <typename T>
  71 inline void
  72 one_way_id_map<T>::put (T src, T dst)
  73 {
  74   m_src_to_dst[src.as_int ()] = dst;
  75 }
  76
  77 /* Get the new value for SRC within the map.  */
  78
  79 template <typename T>
  80 inline T
  81 one_way_id_map<T>::get_dst_for_src (T src) const
  82 {
  83   if (src.null_p ())
  84     return src;
  85   return m_src_to_dst[src.as_int ()];
  86 }
  87
  88 /* Dump this map to PP.  */
  89
  90 template <typename T>
  91 inline void
  92 one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
  93 {
  94   pp_string (pp, "src to dst: {");
  95   unsigned i;
  96   T *dst;
  97   FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
  98     {
  99       if (i > 0)
 100         pp_string (pp, ", ");
 101       T src (T::from_int (i));
 102       src.print (pp);
 103       pp_string (pp, " -> ");
 104       dst->print (pp);
 105     }
 106   pp_string (pp, "}");
 107   pp_newline (pp);
 108 }
 109
 110 /* Dump this map to stderr.  */
 111
 112 template <typename T>
 113 DEBUG_FUNCTION inline void
 114 one_way_id_map<T>::dump () const
 115 {
 116   pretty_printer pp;
 117   pp.buffer->stream = stderr;
 118   dump_to_pp (&pp);
 119   pp_flush (&pp);
 120 }
 121
 122 /* Update *ID from the old value to its new value in this map.  */
 123
 124 template <typename T>
 125 inline void
 126 one_way_id_map<T>::update (T *id) const
 127 {
 128   *id = get_dst_for_src (*id);
 129 }
 130
 131 /* A mapping from region to svalue for use when tracking state.  */
 132
 133 class region_to_value_map
 134 {
 135 public:
 136   typedef hash_map<const region *, const svalue *> hash_map_t;
 137   typedef hash_map_t::iterator iterator;
 138
 139   region_to_value_map () : m_hash_map () {}
 140   region_to_value_map (const region_to_value_map &other)
 141   : m_hash_map (other.m_hash_map) {}
 142   region_to_value_map &operator= (const region_to_value_map &other);
 143
 144   bool operator== (const region_to_value_map &other) const;
 145   bool operator!= (const region_to_value_map &other) const
 146   {
 147     return !(*this == other);
 148   }
 149
 150   iterator begin () const { return m_hash_map.begin (); }
 151   iterator end () const { return m_hash_map.end (); }
 152
 153   const svalue * const *get (const region *reg) const
 154   {
 155     return const_cast <hash_map_t &> (m_hash_map).get (reg);
 156   }
 157   void put (const region *reg, const svalue *sval)
 158   {
 159     m_hash_map.put (reg, sval);
 160   }
 161   void remove (const region *reg)
 162   {
 163     m_hash_map.remove (reg);
 164   }
 165
 166   bool is_empty () const { return m_hash_map.is_empty (); }
 167
 168   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 169   void dump (bool simple) const;
 170
 171   bool can_merge_with_p (const region_to_value_map &other,
 172                          region_to_value_map *out) const;
 173
 174   void purge_state_involving (const svalue *sval);
 175
 176 private:
 177   hash_map_t m_hash_map;
 178 };
 179
 180 /* Various operations delete information from a region_model.
 181
 182    This struct tracks how many of each kind of entity were purged (e.g.
 183    for selftests, and for debugging).  */
 184
 185 struct purge_stats
 186 {
 187   purge_stats ()
 188   : m_num_svalues (0),
 189     m_num_regions (0),
 190     m_num_equiv_classes (0),
 191     m_num_constraints (0),
 192     m_num_client_items (0)
 193   {}
 194
 195   int m_num_svalues;
 196   int m_num_regions;
 197   int m_num_equiv_classes;
 198   int m_num_constraints;
 199   int m_num_client_items;
 200 };
 201
 202 /* A base class for visiting regions and svalues, with do-nothing
 203    base implementations of the per-subclass vfuncs.  */
 204
 205 class visitor
 206 {
 207 public:
 208   virtual void visit_region_svalue (const region_svalue *) {}
 209   virtual void visit_constant_svalue (const constant_svalue *) {}
 210   virtual void visit_unknown_svalue (const unknown_svalue *) {}
 211   virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
 212   virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
 213   virtual void visit_initial_svalue (const initial_svalue *) {}
 214   virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
 215   virtual void visit_binop_svalue (const binop_svalue *) {}
 216   virtual void visit_sub_svalue (const sub_svalue *) {}
 217   virtual void visit_repeated_svalue (const repeated_svalue *) {}
 218   virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
 219   virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
 220   virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
 221   virtual void visit_widening_svalue (const widening_svalue *) {}
 222   virtual void visit_compound_svalue (const compound_svalue *) {}
 223   virtual void visit_conjured_svalue (const conjured_svalue *) {}
 224
 225   virtual void visit_region (const region *) {}
 226 };
 227
 228 } // namespace ana
 229
 230 namespace ana {
 231
 232 /* A class responsible for owning and consolidating region and svalue
 233    instances.
 234    region and svalue instances are immutable as far as clients are
 235    concerned, so they are provided as "const" ptrs.  */
 236
 237 class region_model_manager
 238 {
 239 public:
 240   region_model_manager ();
 241   ~region_model_manager ();
 242
 243   /* svalue consolidation.  */
 244   const svalue *get_or_create_constant_svalue (tree cst_expr);
 245   const svalue *get_or_create_int_cst (tree type, poly_int64);
 246   const svalue *get_or_create_unknown_svalue (tree type);
 247   const svalue *get_or_create_setjmp_svalue (const setjmp_record &r,
 248                                              tree type);
 249   const svalue *get_or_create_poisoned_svalue (enum poison_kind kind,
 250                                                tree type);
 251   const svalue *get_or_create_initial_value (const region *reg);
 252   const svalue *get_ptr_svalue (tree ptr_type, const region *pointee);
 253   const svalue *get_or_create_unaryop (tree type, enum tree_code op,
 254                                        const svalue *arg);
 255   const svalue *get_or_create_cast (tree type, const svalue *arg);
 256   const svalue *get_or_create_binop (tree type,
 257                                      enum tree_code op,
 258                                      const svalue *arg0, const svalue *arg1);
 259   const svalue *get_or_create_sub_svalue (tree type,
 260                                           const svalue *parent_svalue,
 261                                           const region *subregion);
 262   const svalue *get_or_create_repeated_svalue (tree type,
 263                                                const svalue *outer_size,
 264                                                const svalue *inner_svalue);
 265   const svalue *get_or_create_bits_within (tree type,
 266                                            const bit_range &bits,
 267                                            const svalue *inner_svalue);
 268   const svalue *get_or_create_unmergeable (const svalue *arg);
 269   const svalue *get_or_create_widening_svalue (tree type,
 270                                                const program_point &point,
 271                                                const svalue *base_svalue,
 272                                                const svalue *iter_svalue);
 273   const svalue *get_or_create_compound_svalue (tree type,
 274                                                const binding_map &map);
 275   const svalue *get_or_create_conjured_svalue (tree type, const gimple *stmt,
 276                                                const region *id_reg);
 277
 278   const svalue *maybe_get_char_from_string_cst (tree string_cst,
 279                                                 tree byte_offset_cst);
 280
 281   /* region consolidation.  */
 282   const stack_region * get_stack_region () const { return &m_stack_region; }
 283   const heap_region *get_heap_region () const { return &m_heap_region; }
 284   const code_region *get_code_region () const { return &m_code_region; }
 285   const globals_region *get_globals_region () const
 286   {
 287     return &m_globals_region;
 288   }
 289   const function_region *get_region_for_fndecl (tree fndecl);
 290   const label_region *get_region_for_label (tree label);
 291   const decl_region *get_region_for_global (tree expr);
 292   const region *get_field_region (const region *parent, tree field);
 293   const region *get_element_region (const region *parent,
 294                                     tree element_type,
 295                                     const svalue *index);
 296   const region *get_offset_region (const region *parent,
 297                                    tree type,
 298                                    const svalue *byte_offset);
 299   const region *get_sized_region (const region *parent,
 300                                   tree type,
 301                                   const svalue *byte_size_sval);
 302   const region *get_cast_region (const region *original_region,
 303                                  tree type);
 304   const frame_region *get_frame_region (const frame_region *calling_frame,
 305                                         function *fun);
 306   const region *get_symbolic_region (const svalue *sval);
 307   const string_region *get_region_for_string (tree string_cst);
 308
 309   const region *
 310   get_region_for_unexpected_tree_code (region_model_context *ctxt,
 311                                        tree t,
 312                                        const dump_location_t &loc);
 313
 314   unsigned alloc_region_id () { return m_next_region_id++; }
 315
 316   store_manager *get_store_manager () { return &m_store_mgr; }
 317
 318   /* Dynamically-allocated region instances.
 319      The number of these within the analysis can grow arbitrarily.
 320      They are still owned by the manager.  */
 321   const region *create_region_for_heap_alloc ();
 322   const region *create_region_for_alloca (const frame_region *frame);
 323
 324   void log_stats (logger *logger, bool show_objs) const;
 325
 326   void enable_complexity_check (void) { m_check_complexity = true; }
 327   void disable_complexity_check (void) { m_check_complexity = false; }
 328
 329 private:
 330   bool too_complex_p (const complexity &c) const;
 331   bool reject_if_too_complex (svalue *sval);
 332
 333   const svalue *maybe_fold_unaryop (tree type, enum tree_code op,
 334                                     const svalue *arg);
 335   const svalue *maybe_fold_binop (tree type, enum tree_code op,
 336                                   const svalue *arg0, const svalue *arg1);
 337   const svalue *maybe_fold_sub_svalue (tree type,
 338                                        const svalue *parent_svalue,
 339                                        const region *subregion);
 340   const svalue *maybe_fold_repeated_svalue (tree type,
 341                                             const svalue *outer_size,
 342                                             const svalue *inner_svalue);
 343   const svalue *maybe_fold_bits_within_svalue (tree type,
 344                                                const bit_range &bits,
 345                                                const svalue *inner_svalue);
 346   const svalue *maybe_undo_optimize_bit_field_compare (tree type,
 347                                                        const compound_svalue *compound_sval,
 348                                                        tree cst, const svalue *arg1);
 349
 350   unsigned m_next_region_id;
 351   root_region m_root_region;
 352   stack_region m_stack_region;
 353   heap_region m_heap_region;
 354
 355   /* svalue consolidation.  */
 356   typedef hash_map<tree, constant_svalue *> constants_map_t;
 357   constants_map_t m_constants_map;
 358
 359   typedef hash_map<tree, unknown_svalue *> unknowns_map_t;
 360   unknowns_map_t m_unknowns_map;
 361   const unknown_svalue *m_unknown_NULL;
 362
 363   typedef hash_map<poisoned_svalue::key_t,
 364                    poisoned_svalue *> poisoned_values_map_t;
 365   poisoned_values_map_t m_poisoned_values_map;
 366
 367   typedef hash_map<setjmp_svalue::key_t,
 368                    setjmp_svalue *> setjmp_values_map_t;
 369   setjmp_values_map_t m_setjmp_values_map;
 370
 371   typedef hash_map<const region *, initial_svalue *> initial_values_map_t;
 372   initial_values_map_t m_initial_values_map;
 373
 374   typedef hash_map<region_svalue::key_t, region_svalue *> pointer_values_map_t;
 375   pointer_values_map_t m_pointer_values_map;
 376
 377   typedef hash_map<unaryop_svalue::key_t,
 378                    unaryop_svalue *> unaryop_values_map_t;
 379   unaryop_values_map_t m_unaryop_values_map;
 380
 381   typedef hash_map<binop_svalue::key_t, binop_svalue *> binop_values_map_t;
 382   binop_values_map_t m_binop_values_map;
 383
 384   typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t;
 385   sub_values_map_t m_sub_values_map;
 386
 387   typedef hash_map<repeated_svalue::key_t,
 388                    repeated_svalue *> repeated_values_map_t;
 389   repeated_values_map_t m_repeated_values_map;
 390
 391   typedef hash_map<bits_within_svalue::key_t,
 392                    bits_within_svalue *> bits_within_values_map_t;
 393   bits_within_values_map_t m_bits_within_values_map;
 394
 395   typedef hash_map<const svalue *,
 396                    unmergeable_svalue *> unmergeable_values_map_t;
 397   unmergeable_values_map_t m_unmergeable_values_map;
 398
 399   typedef hash_map<widening_svalue::key_t,
 400                    widening_svalue */*,
 401                    widening_svalue::key_t::hash_map_traits*/>
 402     widening_values_map_t;
 403   widening_values_map_t m_widening_values_map;
 404
 405   typedef hash_map<compound_svalue::key_t,
 406                    compound_svalue *> compound_values_map_t;
 407   compound_values_map_t m_compound_values_map;
 408
 409   typedef hash_map<conjured_svalue::key_t,
 410                    conjured_svalue *> conjured_values_map_t;
 411   conjured_values_map_t m_conjured_values_map;
 412
 413   bool m_check_complexity;
 414
 415   /* Maximum complexity of svalues that weren't rejected.  */
 416   complexity m_max_complexity;
 417
 418   /* region consolidation.  */
 419
 420   code_region m_code_region;
 421   typedef hash_map<tree, function_region *> fndecls_map_t;
 422   typedef fndecls_map_t::iterator fndecls_iterator_t;
 423   fndecls_map_t m_fndecls_map;
 424
 425   typedef hash_map<tree, label_region *> labels_map_t;
 426   typedef labels_map_t::iterator labels_iterator_t;
 427   labels_map_t m_labels_map;
 428
 429   globals_region m_globals_region;
 430   typedef hash_map<tree, decl_region *> globals_map_t;
 431   typedef globals_map_t::iterator globals_iterator_t;
 432   globals_map_t m_globals_map;
 433
 434   consolidation_map<field_region> m_field_regions;
 435   consolidation_map<element_region> m_element_regions;
 436   consolidation_map<offset_region> m_offset_regions;
 437   consolidation_map<sized_region> m_sized_regions;
 438   consolidation_map<cast_region> m_cast_regions;
 439   consolidation_map<frame_region> m_frame_regions;
 440   consolidation_map<symbolic_region> m_symbolic_regions;
 441
 442   typedef hash_map<tree, string_region *> string_map_t;
 443   string_map_t m_string_map;
 444
 445   store_manager m_store_mgr;
 446
 447   /* "Dynamically-allocated" region instances.
 448      The number of these within the analysis can grow arbitrarily.
 449      They are still owned by the manager.  */
 450   auto_delete_vec<region> m_managed_dynamic_regions;
 451 };
 452
 453 struct append_ssa_names_cb_data;
 454
 455 /* Helper class for handling calls to functions with known behavior.
 456    Implemented in region-model-impl-calls.c.  */
 457
 458 class call_details
 459 {
 460 public:
 461   call_details (const gcall *call, region_model *model,
 462                 region_model_context *ctxt);
 463
 464   region_model_context *get_ctxt () const { return m_ctxt; }
 465   uncertainty_t *get_uncertainty () const;
 466   tree get_lhs_type () const { return m_lhs_type; }
 467   const region *get_lhs_region () const { return m_lhs_region; }
 468
 469   bool maybe_set_lhs (const svalue *result) const;
 470
 471   unsigned num_args () const;
 472
 473   tree get_arg_tree (unsigned idx) const;
 474   tree get_arg_type (unsigned idx) const;
 475   const svalue *get_arg_svalue (unsigned idx) const;
 476   const char *get_arg_string_literal (unsigned idx) const;
 477
 478   void dump_to_pp (pretty_printer *pp, bool simple) const;
 479   void dump (bool simple) const;
 480
 481   const svalue *get_or_create_conjured_svalue (const region *) const;
 482
 483 private:
 484   const gcall *m_call;
 485   region_model *m_model;
 486   region_model_context *m_ctxt;
 487   tree m_lhs_type;
 488   const region *m_lhs_region;
 489 };
 490
 491 /* A region_model encapsulates a representation of the state of memory, with
 492    a tree of regions, along with their associated values.
 493    The representation is graph-like because values can be pointers to
 494    regions.
 495    It also stores:
 496    - a constraint_manager, capturing relationships between the values, and
 497    - dynamic extents, mapping dynamically-allocated regions to svalues (their
 498    capacities).  */
 499
 500 class region_model
 501 {
 502  public:
 503   typedef region_to_value_map dynamic_extents_t;
 504
 505   region_model (region_model_manager *mgr);
 506   region_model (const region_model &other);
 507   ~region_model ();
 508   region_model &operator= (const region_model &other);
 509
 510   bool operator== (const region_model &other) const;
 511   bool operator!= (const region_model &other) const
 512   {
 513     return !(*this == other);
 514   }
 515
 516   hashval_t hash () const;
 517
 518   void print (pretty_printer *pp) const;
 519
 520   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 521   void dump (FILE *fp, bool simple, bool multiline) const;
 522   void dump (bool simple) const;
 523
 524   void debug () const;
 525
 526   void validate () const;
 527
 528   void canonicalize ();
 529   bool canonicalized_p () const;
 530
 531   void
 532   on_stmt_pre (const gimple *stmt,
 533                bool *out_terminate_path,
 534                bool *out_unknown_side_effects,
 535                region_model_context *ctxt);
 536
 537   void on_assignment (const gassign *stmt, region_model_context *ctxt);
 538   const svalue *get_gassign_result (const gassign *assign,
 539                                     region_model_context *ctxt);
 540   bool on_call_pre (const gcall *stmt, region_model_context *ctxt,
 541                     bool *out_terminate_path);
 542   void on_call_post (const gcall *stmt,
 543                      bool unknown_side_effects,
 544                      region_model_context *ctxt);
 545
 546   void purge_state_involving (const svalue *sval, region_model_context *ctxt);
 547
 548   /* Specific handling for on_call_pre.  */
 549   void impl_call_alloca (const call_details &cd);
 550   void impl_call_analyzer_describe (const gcall *call,
 551                                     region_model_context *ctxt);
 552   void impl_call_analyzer_dump_capacity (const gcall *call,
 553                                          region_model_context *ctxt);
 554   void impl_call_analyzer_eval (const gcall *call,
 555                                 region_model_context *ctxt);
 556   void impl_call_builtin_expect (const call_details &cd);
 557   void impl_call_calloc (const call_details &cd);
 558   bool impl_call_error (const call_details &cd, unsigned min_args,
 559                         bool *out_terminate_path);
 560   void impl_call_fgets (const call_details &cd);
 561   void impl_call_fread (const call_details &cd);
 562   void impl_call_free (const call_details &cd);
 563   void impl_call_malloc (const call_details &cd);
 564   void impl_call_memcpy (const call_details &cd);
 565   void impl_call_memset (const call_details &cd);
 566   void impl_call_realloc (const call_details &cd);
 567   void impl_call_strcpy (const call_details &cd);
 568   void impl_call_strlen (const call_details &cd);
 569   void impl_call_operator_new (const call_details &cd);
 570   void impl_call_operator_delete (const call_details &cd);
 571   void impl_deallocation_call (const call_details &cd);
 572
 573   void handle_unrecognized_call (const gcall *call,
 574                                  region_model_context *ctxt);
 575   void get_reachable_svalues (svalue_set *out,
 576                               const svalue *extra_sval,
 577                               const uncertainty_t *uncertainty);
 578
 579   void on_return (const greturn *stmt, region_model_context *ctxt);
 580   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 581                   region_model_context *ctxt);
 582   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 583                    int setjmp_stack_depth, region_model_context *ctxt);
 584
 585   void update_for_phis (const supernode *snode,
 586                         const cfg_superedge *last_cfg_superedge,
 587                         region_model_context *ctxt);
 588
 589   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 590                    const region_model &old_state,
 591                    region_model_context *ctxt);
 592
 593   bool maybe_update_for_edge (const superedge &edge,
 594                               const gimple *last_stmt,
 595                               region_model_context *ctxt,
 596                               rejected_constraint **out);
 597
 598   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 599                             region_model_context *ctxt);
 600   const frame_region *get_current_frame () const { return m_current_frame; }
 601   function * get_current_function () const;
 602   void pop_frame (const region *result_dst,
 603                   const svalue **out_result,
 604                   region_model_context *ctxt);
 605   int get_stack_depth () const;
 606   const frame_region *get_frame_at_index (int index) const;
 607
 608   const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
 609   const region *get_lvalue (tree expr, region_model_context *ctxt) const;
 610   const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
 611   const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
 612
 613   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 614                                region_model_context *ctxt) const;
 615
 616   const svalue *get_rvalue_for_bits (tree type,
 617                                      const region *reg,
 618                                      const bit_range &bits,
 619                                      region_model_context *ctxt) const;
 620
 621   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 622                   region_model_context *ctxt);
 623   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 624   void clobber_region (const region *reg);
 625   void purge_region (const region *reg);
 626   void fill_region (const region *reg, const svalue *sval);
 627   void zero_fill_region (const region *reg);
 628   void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 629
 630   void copy_region (const region *dst_reg, const region *src_reg,
 631                     region_model_context *ctxt);
 632   tristate eval_condition (const svalue *lhs,
 633                            enum tree_code op,
 634                            const svalue *rhs) const;
 635   tristate eval_condition_without_cm (const svalue *lhs,
 636                                       enum tree_code op,
 637                                       const svalue *rhs) const;
 638   tristate compare_initial_and_pointer (const initial_svalue *init,
 639                                         const region_svalue *ptr) const;
 640   tristate eval_condition (tree lhs,
 641                            enum tree_code op,
 642                            tree rhs,
 643                            region_model_context *ctxt);
 644   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 645                        region_model_context *ctxt);
 646   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 647                        region_model_context *ctxt,
 648                        rejected_constraint **out);
 649
 650   const region *create_region_for_heap_alloc (const svalue *size_in_bytes);
 651   const region *create_region_for_alloca (const svalue *size_in_bytes);
 652
 653   tree get_representative_tree (const svalue *sval) const;
 654   path_var
 655   get_representative_path_var (const svalue *sval,
 656                                svalue_set *visited) const;
 657   path_var
 658   get_representative_path_var (const region *reg,
 659                                svalue_set *visited) const;
 660
 661   /* For selftests.  */
 662   constraint_manager *get_constraints ()
 663   {
 664     return m_constraints;
 665   }
 666
 667   store *get_store () { return &m_store; }
 668   const store *get_store () const { return &m_store; }
 669
 670   const dynamic_extents_t &
 671   get_dynamic_extents () const
 672   {
 673     return m_dynamic_extents;
 674   }
 675   const svalue *get_dynamic_extents (const region *reg) const;
 676   void set_dynamic_extents (const region *reg,
 677                             const svalue *size_in_bytes);
 678   void unset_dynamic_extents (const region *reg);
 679
 680   region_model_manager *get_manager () const { return m_mgr; }
 681
 682   void unbind_region_and_descendents (const region *reg,
 683                                       enum poison_kind pkind);
 684
 685   bool can_merge_with_p (const region_model &other_model,
 686                          const program_point &point,
 687                          region_model *out_model) const;
 688
 689   tree get_fndecl_for_call (const gcall *call,
 690                             region_model_context *ctxt);
 691
 692   void get_ssa_name_regions_for_current_frame
 693     (auto_vec<const decl_region *> *out) const;
 694   static void append_ssa_names_cb (const region *base_reg,
 695                                    struct append_ssa_names_cb_data *data);
 696
 697   const svalue *get_store_value (const region *reg,
 698                                  region_model_context *ctxt) const;
 699
 700   bool region_exists_p (const region *reg) const;
 701
 702   void loop_replay_fixup (const region_model *dst_state);
 703
 704   const svalue *get_capacity (const region *reg) const;
 705
 706  private:
 707   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 708   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 709
 710   path_var
 711   get_representative_path_var_1 (const svalue *sval,
 712                                  svalue_set *visited) const;
 713   path_var
 714   get_representative_path_var_1 (const region *reg,
 715                                  svalue_set *visited) const;
 716
 717   bool add_constraint (const svalue *lhs,
 718                        enum tree_code op,
 719                        const svalue *rhs,
 720                        region_model_context *ctxt);
 721   bool add_constraints_from_binop (const svalue *outer_lhs,
 722                                    enum tree_code outer_op,
 723                                    const svalue *outer_rhs,
 724                                    bool *out,
 725                                    region_model_context *ctxt);
 726
 727   void update_for_call_superedge (const call_superedge &call_edge,
 728                                   region_model_context *ctxt);
 729   void update_for_return_superedge (const return_superedge &return_edge,
 730                                     region_model_context *ctxt);
 731   void update_for_call_summary (const callgraph_superedge &cg_sedge,
 732                                 region_model_context *ctxt);
 733   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 734                                     const gcond *cond_stmt,
 735                                     region_model_context *ctxt,
 736                                     rejected_constraint **out);
 737   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 738                                       const gswitch *switch_stmt,
 739                                       region_model_context *ctxt,
 740                                       rejected_constraint **out);
 741   bool apply_constraints_for_exception (const gimple *last_stmt,
 742                                         region_model_context *ctxt,
 743                                         rejected_constraint **out);
 744
 745   int poison_any_pointers_to_descendents (const region *reg,
 746                                           enum poison_kind pkind);
 747
 748   void on_top_level_param (tree param, region_model_context *ctxt);
 749
 750   bool called_from_main_p () const;
 751   const svalue *get_initial_value_for_global (const region *reg) const;
 752
 753   const svalue *check_for_poison (const svalue *sval,
 754                                   tree expr,
 755                                   region_model_context *ctxt) const;
 756
 757   void check_for_writable_region (const region* dest_reg,
 758                                   region_model_context *ctxt) const;
 759   void check_region_access (const region *reg,
 760                             enum access_direction dir,
 761                             region_model_context *ctxt) const;
 762   void check_region_for_write (const region *dest_reg,
 763                                region_model_context *ctxt) const;
 764   void check_region_for_read (const region *src_reg,
 765                               region_model_context *ctxt) const;
 766
 767   /* Storing this here to avoid passing it around everywhere.  */
 768   region_model_manager *const m_mgr;
 769
 770   store m_store;
 771
 772   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 773
 774   const frame_region *m_current_frame;
 775
 776   /* Map from base region to size in bytes, for tracking the sizes of
 777      dynamically-allocated regions.
 778      This is part of the region_model rather than the region to allow for
 779      memory regions to be resized (e.g. by realloc).  */
 780   dynamic_extents_t m_dynamic_extents;
 781 };
 782
 783 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 784    uninitialized value).  This abstract base class encapsulates an interface
 785    for the region model to use when emitting such warnings.
 786
 787    Having this as an abstract base class allows us to support the various
 788    operations needed by program_state in the analyzer within region_model,
 789    whilst keeping them somewhat modularized.  */
 790
 791 class region_model_context
 792 {
 793  public:
 794   /* Hook for clients to store pending diagnostics.
 795      Return true if the diagnostic was stored, or false if it was deleted.  */
 796   virtual bool warn (pending_diagnostic *d) = 0;
 797
 798   /* Hook for clients to be notified when an SVAL that was reachable
 799      in a previous state is no longer live, so that clients can emit warnings
 800      about leaks.  */
 801   virtual void on_svalue_leak (const svalue *sval) = 0;
 802
 803   /* Hook for clients to be notified when the set of explicitly live
 804      svalues changes, so that they can purge state relating to dead
 805      svalues.  */
 806   virtual void on_liveness_change (const svalue_set &live_svalues,
 807                                    const region_model *model) = 0;
 808
 809   virtual logger *get_logger () = 0;
 810
 811   /* Hook for clients to be notified when the condition
 812      "LHS OP RHS" is added to the region model.
 813      This exists so that state machines can detect tests on edges,
 814      and use them to trigger sm-state transitions (e.g. transitions due
 815      to ptrs becoming known to be NULL or non-NULL, rather than just
 816      "unchecked") */
 817   virtual void on_condition (const svalue *lhs,
 818                              enum tree_code op,
 819                              const svalue *rhs) = 0;
 820
 821   /* Hooks for clients to be notified when an unknown change happens
 822      to SVAL (in response to a call to an unknown function).  */
 823   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 824
 825   /* Hooks for clients to be notified when a phi node is handled,
 826      where RHS is the pertinent argument.  */
 827   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 828
 829   /* Hooks for clients to be notified when the region model doesn't
 830      know how to handle the tree code of T at LOC.  */
 831   virtual void on_unexpected_tree_code (tree t,
 832                                         const dump_location_t &loc) = 0;
 833
 834   /* Hook for clients to be notified when a function_decl escapes.  */
 835   virtual void on_escaped_function (tree fndecl) = 0;
 836
 837   virtual uncertainty_t *get_uncertainty () = 0;
 838
 839   /* Hook for clients to purge state involving SVAL.  */
 840   virtual void purge_state_involving (const svalue *sval) = 0;
 841 };
 842
 843 /* A "do nothing" subclass of region_model_context.  */
 844
 845 class noop_region_model_context : public region_model_context
 846 {
 847 public:
 848   bool warn (pending_diagnostic *) OVERRIDE { return false; }
 849   void on_svalue_leak (const svalue *) OVERRIDE {}
 850   void on_liveness_change (const svalue_set &,
 851                            const region_model *) OVERRIDE {}
 852   logger *get_logger () OVERRIDE { return NULL; }
 853   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
 854                      enum tree_code op ATTRIBUTE_UNUSED,
 855                      const svalue *rhs ATTRIBUTE_UNUSED) OVERRIDE
 856   {
 857   }
 858   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 859                           bool is_mutable ATTRIBUTE_UNUSED) OVERRIDE
 860   {
 861   }
 862   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 863                tree rhs ATTRIBUTE_UNUSED) OVERRIDE
 864   {
 865   }
 866   void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
 867
 868   void on_escaped_function (tree) OVERRIDE {}
 869
 870   uncertainty_t *get_uncertainty () OVERRIDE { return NULL; }
 871
 872   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) OVERRIDE {}
 873 };
 874
 875 /* A subclass of region_model_context for determining if operations fail
 876    e.g. "can we generate a region for the lvalue of EXPR?".  */
 877
 878 class tentative_region_model_context : public noop_region_model_context
 879 {
 880 public:
 881   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 882
 883   void on_unexpected_tree_code (tree, const dump_location_t &)
 884     FINAL OVERRIDE
 885   {
 886     m_num_unexpected_codes++;
 887   }
 888
 889   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 890
 891 private:
 892   int m_num_unexpected_codes;
 893 };
 894
 895 /* A bundle of data for use when attempting to merge two region_model
 896    instances to make a third.  */
 897
 898 struct model_merger
 899 {
 900   model_merger (const region_model *model_a,
 901                 const region_model *model_b,
 902                 const program_point &point,
 903                 region_model *merged_model)
 904   : m_model_a (model_a), m_model_b (model_b),
 905     m_point (point),
 906     m_merged_model (merged_model)
 907   {
 908   }
 909
 910   void dump_to_pp (pretty_printer *pp, bool simple) const;
 911   void dump (FILE *fp, bool simple) const;
 912   void dump (bool simple) const;
 913
 914   region_model_manager *get_manager () const
 915   {
 916     return m_model_a->get_manager ();
 917   }
 918
 919   const region_model *m_model_a;
 920   const region_model *m_model_b;
 921   const program_point &m_point;
 922   region_model *m_merged_model;
 923 };
 924
 925 /* A record that can (optionally) be written out when
 926    region_model::add_constraint fails.  */
 927
 928 struct rejected_constraint
 929 {
 930   rejected_constraint (const region_model &model,
 931                      tree lhs, enum tree_code op, tree rhs)
 932   : m_model (model), m_lhs (lhs), m_op (op), m_rhs (rhs)
 933   {}
 934
 935   void dump_to_pp (pretty_printer *pp) const;
 936
 937   region_model m_model;
 938   tree m_lhs;
 939   enum tree_code m_op;
 940   tree m_rhs;
 941 };
 942
 943 /* A bundle of state.  */
 944
 945 class engine
 946 {
 947 public:
 948   region_model_manager *get_model_manager () { return &m_mgr; }
 949
 950   void log_stats (logger *logger) const;
 951
 952 private:
 953   region_model_manager m_mgr;
 954
 955 };
 956
 957 } // namespace ana
 958
 959 extern void debug (const region_model &rmodel);
 960
 961 namespace ana {
 962
 963 #if CHECKING_P
 964
 965 namespace selftest {
 966
 967 using namespace ::selftest;
 968
 969 /* An implementation of region_model_context for use in selftests, which
 970    stores any pending_diagnostic instances passed to it.  */
 971
 972 class test_region_model_context : public noop_region_model_context
 973 {
 974 public:
 975   bool warn (pending_diagnostic *d) FINAL OVERRIDE
 976   {
 977     m_diagnostics.safe_push (d);
 978     return true;
 979   }
 980
 981   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
 982
 983   void on_unexpected_tree_code (tree t, const dump_location_t &)
 984     FINAL OVERRIDE
 985   {
 986     internal_error ("unhandled tree code: %qs",
 987                     get_tree_code_name (TREE_CODE (t)));
 988   }
 989
 990 private:
 991   /* Implicitly delete any diagnostics in the dtor.  */
 992   auto_delete_vec<pending_diagnostic> m_diagnostics;
 993 };
 994
 995 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
 996    Verify that MODEL remains satisfiable.  */
 997
 998 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
 999   SELFTEST_BEGIN_STMT                                   \
1000     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1001     ASSERT_TRUE (sat);                                  \
1002   SELFTEST_END_STMT
1003
1004 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1005    Verify that the result is not satisfiable.  */
1006
1007 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
1008   SELFTEST_BEGIN_STMT                                   \
1009     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1010     ASSERT_FALSE (sat);                         \
1011   SELFTEST_END_STMT
1012
1013 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
1014
1015 void assert_condition (const location &loc,
1016                        region_model &model,
1017                        const svalue *lhs, tree_code op, const svalue *rhs,
1018                        tristate expected);
1019
1020 void assert_condition (const location &loc,
1021                        region_model &model,
1022                        tree lhs, tree_code op, tree rhs,
1023                        tristate expected);
1024
1025 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1026    as "true".  */
1027
1028 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1029   SELFTEST_BEGIN_STMT                                                   \
1030   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1031                     tristate (tristate::TS_TRUE));              \
1032   SELFTEST_END_STMT
1033
1034 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1035    as "false".  */
1036
1037 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1038   SELFTEST_BEGIN_STMT                                                   \
1039   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1040                     tristate (tristate::TS_FALSE));             \
1041   SELFTEST_END_STMT
1042
1043 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1044    as "unknown".  */
1045
1046 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1047   SELFTEST_BEGIN_STMT                                                   \
1048   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1049                     tristate (tristate::TS_UNKNOWN));           \
1050   SELFTEST_END_STMT
1051
1052 } /* end of namespace selftest.  */
1053
1054 #endif /* #if CHECKING_P */
1055
1056 } // namespace ana
1057
1058 #endif /* GCC_ANALYZER_REGION_MODEL_H */