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 private:
 327   bool too_complex_p (const complexity &c) const;
 328   bool reject_if_too_complex (svalue *sval);
 329
 330   const svalue *maybe_fold_unaryop (tree type, enum tree_code op,
 331                                     const svalue *arg);
 332   const svalue *maybe_fold_binop (tree type, enum tree_code op,
 333                                   const svalue *arg0, const svalue *arg1);
 334   const svalue *maybe_fold_sub_svalue (tree type,
 335                                        const svalue *parent_svalue,
 336                                        const region *subregion);
 337   const svalue *maybe_fold_repeated_svalue (tree type,
 338                                             const svalue *outer_size,
 339                                             const svalue *inner_svalue);
 340   const svalue *maybe_fold_bits_within_svalue (tree type,
 341                                                const bit_range &bits,
 342                                                const svalue *inner_svalue);
 343   const svalue *maybe_undo_optimize_bit_field_compare (tree type,
 344                                                        const compound_svalue *compound_sval,
 345                                                        tree cst, const svalue *arg1);
 346
 347   unsigned m_next_region_id;
 348   root_region m_root_region;
 349   stack_region m_stack_region;
 350   heap_region m_heap_region;
 351
 352   /* svalue consolidation.  */
 353   typedef hash_map<tree, constant_svalue *> constants_map_t;
 354   constants_map_t m_constants_map;
 355
 356   typedef hash_map<tree, unknown_svalue *> unknowns_map_t;
 357   unknowns_map_t m_unknowns_map;
 358   const unknown_svalue *m_unknown_NULL;
 359
 360   typedef hash_map<poisoned_svalue::key_t,
 361                    poisoned_svalue *> poisoned_values_map_t;
 362   poisoned_values_map_t m_poisoned_values_map;
 363
 364   typedef hash_map<setjmp_svalue::key_t,
 365                    setjmp_svalue *> setjmp_values_map_t;
 366   setjmp_values_map_t m_setjmp_values_map;
 367
 368   typedef hash_map<const region *, initial_svalue *> initial_values_map_t;
 369   initial_values_map_t m_initial_values_map;
 370
 371   typedef hash_map<region_svalue::key_t, region_svalue *> pointer_values_map_t;
 372   pointer_values_map_t m_pointer_values_map;
 373
 374   typedef hash_map<unaryop_svalue::key_t,
 375                    unaryop_svalue *> unaryop_values_map_t;
 376   unaryop_values_map_t m_unaryop_values_map;
 377
 378   typedef hash_map<binop_svalue::key_t, binop_svalue *> binop_values_map_t;
 379   binop_values_map_t m_binop_values_map;
 380
 381   typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t;
 382   sub_values_map_t m_sub_values_map;
 383
 384   typedef hash_map<repeated_svalue::key_t,
 385                    repeated_svalue *> repeated_values_map_t;
 386   repeated_values_map_t m_repeated_values_map;
 387
 388   typedef hash_map<bits_within_svalue::key_t,
 389                    bits_within_svalue *> bits_within_values_map_t;
 390   bits_within_values_map_t m_bits_within_values_map;
 391
 392   typedef hash_map<const svalue *,
 393                    unmergeable_svalue *> unmergeable_values_map_t;
 394   unmergeable_values_map_t m_unmergeable_values_map;
 395
 396   typedef hash_map<widening_svalue::key_t,
 397                    widening_svalue */*,
 398                    widening_svalue::key_t::hash_map_traits*/>
 399     widening_values_map_t;
 400   widening_values_map_t m_widening_values_map;
 401
 402   typedef hash_map<compound_svalue::key_t,
 403                    compound_svalue *> compound_values_map_t;
 404   compound_values_map_t m_compound_values_map;
 405
 406   typedef hash_map<conjured_svalue::key_t,
 407                    conjured_svalue *> conjured_values_map_t;
 408   conjured_values_map_t m_conjured_values_map;
 409
 410   /* Maximum complexity of svalues that weren't rejected.  */
 411   complexity m_max_complexity;
 412
 413   /* region consolidation.  */
 414
 415   code_region m_code_region;
 416   typedef hash_map<tree, function_region *> fndecls_map_t;
 417   typedef fndecls_map_t::iterator fndecls_iterator_t;
 418   fndecls_map_t m_fndecls_map;
 419
 420   typedef hash_map<tree, label_region *> labels_map_t;
 421   typedef labels_map_t::iterator labels_iterator_t;
 422   labels_map_t m_labels_map;
 423
 424   globals_region m_globals_region;
 425   typedef hash_map<tree, decl_region *> globals_map_t;
 426   typedef globals_map_t::iterator globals_iterator_t;
 427   globals_map_t m_globals_map;
 428
 429   consolidation_map<field_region> m_field_regions;
 430   consolidation_map<element_region> m_element_regions;
 431   consolidation_map<offset_region> m_offset_regions;
 432   consolidation_map<sized_region> m_sized_regions;
 433   consolidation_map<cast_region> m_cast_regions;
 434   consolidation_map<frame_region> m_frame_regions;
 435   consolidation_map<symbolic_region> m_symbolic_regions;
 436
 437   typedef hash_map<tree, string_region *> string_map_t;
 438   string_map_t m_string_map;
 439
 440   store_manager m_store_mgr;
 441
 442   /* "Dynamically-allocated" region instances.
 443      The number of these within the analysis can grow arbitrarily.
 444      They are still owned by the manager.  */
 445   auto_delete_vec<region> m_managed_dynamic_regions;
 446 };
 447
 448 struct append_ssa_names_cb_data;
 449
 450 /* Helper class for handling calls to functions with known behavior.
 451    Implemented in region-model-impl-calls.c.  */
 452
 453 class call_details
 454 {
 455 public:
 456   call_details (const gcall *call, region_model *model,
 457                 region_model_context *ctxt);
 458
 459   region_model_context *get_ctxt () const { return m_ctxt; }
 460   uncertainty_t *get_uncertainty () const;
 461   tree get_lhs_type () const { return m_lhs_type; }
 462   const region *get_lhs_region () const { return m_lhs_region; }
 463
 464   bool maybe_set_lhs (const svalue *result) const;
 465
 466   unsigned num_args () const;
 467
 468   tree get_arg_tree (unsigned idx) const;
 469   tree get_arg_type (unsigned idx) const;
 470   const svalue *get_arg_svalue (unsigned idx) const;
 471   const char *get_arg_string_literal (unsigned idx) const;
 472
 473   void dump_to_pp (pretty_printer *pp, bool simple) const;
 474   void dump (bool simple) const;
 475
 476   const svalue *get_or_create_conjured_svalue (const region *) const;
 477
 478 private:
 479   const gcall *m_call;
 480   region_model *m_model;
 481   region_model_context *m_ctxt;
 482   tree m_lhs_type;
 483   const region *m_lhs_region;
 484 };
 485
 486 /* A region_model encapsulates a representation of the state of memory, with
 487    a tree of regions, along with their associated values.
 488    The representation is graph-like because values can be pointers to
 489    regions.
 490    It also stores:
 491    - a constraint_manager, capturing relationships between the values, and
 492    - dynamic extents, mapping dynamically-allocated regions to svalues (their
 493    capacities).  */
 494
 495 class region_model
 496 {
 497  public:
 498   typedef region_to_value_map dynamic_extents_t;
 499
 500   region_model (region_model_manager *mgr);
 501   region_model (const region_model &other);
 502   ~region_model ();
 503   region_model &operator= (const region_model &other);
 504
 505   bool operator== (const region_model &other) const;
 506   bool operator!= (const region_model &other) const
 507   {
 508     return !(*this == other);
 509   }
 510
 511   hashval_t hash () const;
 512
 513   void print (pretty_printer *pp) const;
 514
 515   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 516   void dump (FILE *fp, bool simple, bool multiline) const;
 517   void dump (bool simple) const;
 518
 519   void debug () const;
 520
 521   void validate () const;
 522
 523   void canonicalize ();
 524   bool canonicalized_p () const;
 525
 526   void
 527   on_stmt_pre (const gimple *stmt,
 528                bool *out_terminate_path,
 529                bool *out_unknown_side_effects,
 530                region_model_context *ctxt);
 531
 532   void on_assignment (const gassign *stmt, region_model_context *ctxt);
 533   const svalue *get_gassign_result (const gassign *assign,
 534                                     region_model_context *ctxt);
 535   bool on_call_pre (const gcall *stmt, region_model_context *ctxt,
 536                     bool *out_terminate_path);
 537   void on_call_post (const gcall *stmt,
 538                      bool unknown_side_effects,
 539                      region_model_context *ctxt);
 540
 541   void purge_state_involving (const svalue *sval, region_model_context *ctxt);
 542
 543   /* Specific handling for on_call_pre.  */
 544   bool impl_call_alloca (const call_details &cd);
 545   void impl_call_analyzer_describe (const gcall *call,
 546                                     region_model_context *ctxt);
 547   void impl_call_analyzer_dump_capacity (const gcall *call,
 548                                          region_model_context *ctxt);
 549   void impl_call_analyzer_eval (const gcall *call,
 550                                 region_model_context *ctxt);
 551   bool impl_call_builtin_expect (const call_details &cd);
 552   bool impl_call_calloc (const call_details &cd);
 553   bool impl_call_error (const call_details &cd, unsigned min_args,
 554                         bool *out_terminate_path);
 555   void impl_call_fgets (const call_details &cd);
 556   void impl_call_fread (const call_details &cd);
 557   void impl_call_free (const call_details &cd);
 558   bool impl_call_malloc (const call_details &cd);
 559   void impl_call_memcpy (const call_details &cd);
 560   bool impl_call_memset (const call_details &cd);
 561   void impl_call_realloc (const call_details &cd);
 562   void impl_call_strcpy (const call_details &cd);
 563   bool impl_call_strlen (const call_details &cd);
 564   bool impl_call_operator_new (const call_details &cd);
 565   bool impl_call_operator_delete (const call_details &cd);
 566   void impl_deallocation_call (const call_details &cd);
 567
 568   void handle_unrecognized_call (const gcall *call,
 569                                  region_model_context *ctxt);
 570   void get_reachable_svalues (svalue_set *out,
 571                               const svalue *extra_sval,
 572                               const uncertainty_t *uncertainty);
 573
 574   void on_return (const greturn *stmt, region_model_context *ctxt);
 575   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 576                   region_model_context *ctxt);
 577   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 578                    int setjmp_stack_depth, region_model_context *ctxt);
 579
 580   void update_for_phis (const supernode *snode,
 581                         const cfg_superedge *last_cfg_superedge,
 582                         region_model_context *ctxt);
 583
 584   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 585                    region_model_context *ctxt);
 586
 587   bool maybe_update_for_edge (const superedge &edge,
 588                               const gimple *last_stmt,
 589                               region_model_context *ctxt,
 590                               rejected_constraint **out);
 591
 592   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 593                             region_model_context *ctxt);
 594   const frame_region *get_current_frame () const { return m_current_frame; }
 595   function * get_current_function () const;
 596   void pop_frame (const region *result_dst,
 597                   const svalue **out_result,
 598                   region_model_context *ctxt);
 599   int get_stack_depth () const;
 600   const frame_region *get_frame_at_index (int index) const;
 601
 602   const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
 603   const region *get_lvalue (tree expr, region_model_context *ctxt) const;
 604   const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
 605   const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
 606
 607   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 608                                region_model_context *ctxt) const;
 609
 610   const svalue *get_rvalue_for_bits (tree type,
 611                                      const region *reg,
 612                                      const bit_range &bits) const;
 613
 614   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 615                   region_model_context *ctxt);
 616   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 617   void clobber_region (const region *reg);
 618   void purge_region (const region *reg);
 619   void fill_region (const region *reg, const svalue *sval);
 620   void zero_fill_region (const region *reg);
 621   void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 622
 623   void copy_region (const region *dst_reg, const region *src_reg,
 624                     region_model_context *ctxt);
 625   tristate eval_condition (const svalue *lhs,
 626                            enum tree_code op,
 627                            const svalue *rhs) const;
 628   tristate eval_condition_without_cm (const svalue *lhs,
 629                                       enum tree_code op,
 630                                       const svalue *rhs) const;
 631   tristate compare_initial_and_pointer (const initial_svalue *init,
 632                                         const region_svalue *ptr) const;
 633   tristate eval_condition (tree lhs,
 634                            enum tree_code op,
 635                            tree rhs,
 636                            region_model_context *ctxt);
 637   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 638                        region_model_context *ctxt);
 639   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 640                        region_model_context *ctxt,
 641                        rejected_constraint **out);
 642
 643   const region *create_region_for_heap_alloc (const svalue *size_in_bytes);
 644   const region *create_region_for_alloca (const svalue *size_in_bytes);
 645
 646   tree get_representative_tree (const svalue *sval) const;
 647   path_var
 648   get_representative_path_var (const svalue *sval,
 649                                svalue_set *visited) const;
 650   path_var
 651   get_representative_path_var (const region *reg,
 652                                svalue_set *visited) const;
 653
 654   /* For selftests.  */
 655   constraint_manager *get_constraints ()
 656   {
 657     return m_constraints;
 658   }
 659
 660   store *get_store () { return &m_store; }
 661   const store *get_store () const { return &m_store; }
 662
 663   const dynamic_extents_t &
 664   get_dynamic_extents () const
 665   {
 666     return m_dynamic_extents;
 667   }
 668   const svalue *get_dynamic_extents (const region *reg) const;
 669   void set_dynamic_extents (const region *reg,
 670                             const svalue *size_in_bytes);
 671   void unset_dynamic_extents (const region *reg);
 672
 673   region_model_manager *get_manager () const { return m_mgr; }
 674
 675   void unbind_region_and_descendents (const region *reg,
 676                                       enum poison_kind pkind);
 677
 678   bool can_merge_with_p (const region_model &other_model,
 679                          const program_point &point,
 680                          region_model *out_model) const;
 681
 682   tree get_fndecl_for_call (const gcall *call,
 683                             region_model_context *ctxt);
 684
 685   void get_ssa_name_regions_for_current_frame
 686     (auto_vec<const decl_region *> *out) const;
 687   static void append_ssa_names_cb (const region *base_reg,
 688                                    struct append_ssa_names_cb_data *data);
 689
 690   const svalue *get_store_value (const region *reg) const;
 691
 692   bool region_exists_p (const region *reg) const;
 693
 694   void loop_replay_fixup (const region_model *dst_state);
 695
 696   const svalue *get_capacity (const region *reg) const;
 697
 698  private:
 699   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 700   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 701
 702   path_var
 703   get_representative_path_var_1 (const svalue *sval,
 704                                  svalue_set *visited) const;
 705   path_var
 706   get_representative_path_var_1 (const region *reg,
 707                                  svalue_set *visited) const;
 708
 709   bool add_constraint (const svalue *lhs,
 710                        enum tree_code op,
 711                        const svalue *rhs,
 712                        region_model_context *ctxt);
 713   bool add_constraints_from_binop (const svalue *outer_lhs,
 714                                    enum tree_code outer_op,
 715                                    const svalue *outer_rhs,
 716                                    bool *out,
 717                                    region_model_context *ctxt);
 718
 719   void update_for_call_superedge (const call_superedge &call_edge,
 720                                   region_model_context *ctxt);
 721   void update_for_return_superedge (const return_superedge &return_edge,
 722                                     region_model_context *ctxt);
 723   void update_for_call_summary (const callgraph_superedge &cg_sedge,
 724                                 region_model_context *ctxt);
 725   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 726                                     const gcond *cond_stmt,
 727                                     region_model_context *ctxt,
 728                                     rejected_constraint **out);
 729   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 730                                       const gswitch *switch_stmt,
 731                                       region_model_context *ctxt,
 732                                       rejected_constraint **out);
 733   bool apply_constraints_for_exception (const gimple *last_stmt,
 734                                         region_model_context *ctxt,
 735                                         rejected_constraint **out);
 736
 737   int poison_any_pointers_to_descendents (const region *reg,
 738                                           enum poison_kind pkind);
 739
 740   void on_top_level_param (tree param, region_model_context *ctxt);
 741
 742   bool called_from_main_p () const;
 743   const svalue *get_initial_value_for_global (const region *reg) const;
 744
 745   const svalue *check_for_poison (const svalue *sval,
 746                                   tree expr,
 747                                   region_model_context *ctxt) const;
 748
 749   void check_for_writable_region (const region* dest_reg,
 750                                   region_model_context *ctxt) const;
 751
 752   /* Storing this here to avoid passing it around everywhere.  */
 753   region_model_manager *const m_mgr;
 754
 755   store m_store;
 756
 757   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 758
 759   const frame_region *m_current_frame;
 760
 761   /* Map from base region to size in bytes, for tracking the sizes of
 762      dynamically-allocated regions.
 763      This is part of the region_model rather than the region to allow for
 764      memory regions to be resized (e.g. by realloc).  */
 765   dynamic_extents_t m_dynamic_extents;
 766 };
 767
 768 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 769    uninitialized value).  This abstract base class encapsulates an interface
 770    for the region model to use when emitting such warnings.
 771
 772    Having this as an abstract base class allows us to support the various
 773    operations needed by program_state in the analyzer within region_model,
 774    whilst keeping them somewhat modularized.  */
 775
 776 class region_model_context
 777 {
 778  public:
 779   /* Hook for clients to store pending diagnostics.
 780      Return true if the diagnostic was stored, or false if it was deleted.  */
 781   virtual bool warn (pending_diagnostic *d) = 0;
 782
 783   /* Hook for clients to be notified when an SVAL that was reachable
 784      in a previous state is no longer live, so that clients can emit warnings
 785      about leaks.  */
 786   virtual void on_svalue_leak (const svalue *sval) = 0;
 787
 788   /* Hook for clients to be notified when the set of explicitly live
 789      svalues changes, so that they can purge state relating to dead
 790      svalues.  */
 791   virtual void on_liveness_change (const svalue_set &live_svalues,
 792                                    const region_model *model) = 0;
 793
 794   virtual logger *get_logger () = 0;
 795
 796   /* Hook for clients to be notified when the condition
 797      "LHS OP RHS" is added to the region model.
 798      This exists so that state machines can detect tests on edges,
 799      and use them to trigger sm-state transitions (e.g. transitions due
 800      to ptrs becoming known to be NULL or non-NULL, rather than just
 801      "unchecked") */
 802   virtual void on_condition (const svalue *lhs,
 803                              enum tree_code op,
 804                              const svalue *rhs) = 0;
 805
 806   /* Hooks for clients to be notified when an unknown change happens
 807      to SVAL (in response to a call to an unknown function).  */
 808   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 809
 810   /* Hooks for clients to be notified when a phi node is handled,
 811      where RHS is the pertinent argument.  */
 812   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 813
 814   /* Hooks for clients to be notified when the region model doesn't
 815      know how to handle the tree code of T at LOC.  */
 816   virtual void on_unexpected_tree_code (tree t,
 817                                         const dump_location_t &loc) = 0;
 818
 819   /* Hook for clients to be notified when a function_decl escapes.  */
 820   virtual void on_escaped_function (tree fndecl) = 0;
 821
 822   virtual uncertainty_t *get_uncertainty () = 0;
 823
 824   /* Hook for clients to purge state involving SVAL.  */
 825   virtual void purge_state_involving (const svalue *sval) = 0;
 826 };
 827
 828 /* A "do nothing" subclass of region_model_context.  */
 829
 830 class noop_region_model_context : public region_model_context
 831 {
 832 public:
 833   bool warn (pending_diagnostic *) OVERRIDE { return false; }
 834   void on_svalue_leak (const svalue *) OVERRIDE {}
 835   void on_liveness_change (const svalue_set &,
 836                            const region_model *) OVERRIDE {}
 837   logger *get_logger () OVERRIDE { return NULL; }
 838   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
 839                      enum tree_code op ATTRIBUTE_UNUSED,
 840                      const svalue *rhs ATTRIBUTE_UNUSED) OVERRIDE
 841   {
 842   }
 843   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 844                           bool is_mutable ATTRIBUTE_UNUSED) OVERRIDE
 845   {
 846   }
 847   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 848                tree rhs ATTRIBUTE_UNUSED) OVERRIDE
 849   {
 850   }
 851   void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
 852
 853   void on_escaped_function (tree) OVERRIDE {}
 854
 855   uncertainty_t *get_uncertainty () OVERRIDE { return NULL; }
 856
 857   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) OVERRIDE {}
 858 };
 859
 860 /* A subclass of region_model_context for determining if operations fail
 861    e.g. "can we generate a region for the lvalue of EXPR?".  */
 862
 863 class tentative_region_model_context : public noop_region_model_context
 864 {
 865 public:
 866   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 867
 868   void on_unexpected_tree_code (tree, const dump_location_t &)
 869     FINAL OVERRIDE
 870   {
 871     m_num_unexpected_codes++;
 872   }
 873
 874   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 875
 876 private:
 877   int m_num_unexpected_codes;
 878 };
 879
 880 /* A bundle of data for use when attempting to merge two region_model
 881    instances to make a third.  */
 882
 883 struct model_merger
 884 {
 885   model_merger (const region_model *model_a,
 886                 const region_model *model_b,
 887                 const program_point &point,
 888                 region_model *merged_model)
 889   : m_model_a (model_a), m_model_b (model_b),
 890     m_point (point),
 891     m_merged_model (merged_model)
 892   {
 893   }
 894
 895   void dump_to_pp (pretty_printer *pp, bool simple) const;
 896   void dump (FILE *fp, bool simple) const;
 897   void dump (bool simple) const;
 898
 899   region_model_manager *get_manager () const
 900   {
 901     return m_model_a->get_manager ();
 902   }
 903
 904   const region_model *m_model_a;
 905   const region_model *m_model_b;
 906   const program_point &m_point;
 907   region_model *m_merged_model;
 908 };
 909
 910 /* A record that can (optionally) be written out when
 911    region_model::add_constraint fails.  */
 912
 913 struct rejected_constraint
 914 {
 915   rejected_constraint (const region_model &model,
 916                      tree lhs, enum tree_code op, tree rhs)
 917   : m_model (model), m_lhs (lhs), m_op (op), m_rhs (rhs)
 918   {}
 919
 920   void dump_to_pp (pretty_printer *pp) const;
 921
 922   region_model m_model;
 923   tree m_lhs;
 924   enum tree_code m_op;
 925   tree m_rhs;
 926 };
 927
 928 /* A bundle of state.  */
 929
 930 class engine
 931 {
 932 public:
 933   region_model_manager *get_model_manager () { return &m_mgr; }
 934
 935   void log_stats (logger *logger) const;
 936
 937 private:
 938   region_model_manager m_mgr;
 939
 940 };
 941
 942 } // namespace ana
 943
 944 extern void debug (const region_model &rmodel);
 945
 946 namespace ana {
 947
 948 #if CHECKING_P
 949
 950 namespace selftest {
 951
 952 using namespace ::selftest;
 953
 954 /* An implementation of region_model_context for use in selftests, which
 955    stores any pending_diagnostic instances passed to it.  */
 956
 957 class test_region_model_context : public noop_region_model_context
 958 {
 959 public:
 960   bool warn (pending_diagnostic *d) FINAL OVERRIDE
 961   {
 962     m_diagnostics.safe_push (d);
 963     return true;
 964   }
 965
 966   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
 967
 968   void on_unexpected_tree_code (tree t, const dump_location_t &)
 969     FINAL OVERRIDE
 970   {
 971     internal_error ("unhandled tree code: %qs",
 972                     get_tree_code_name (TREE_CODE (t)));
 973   }
 974
 975 private:
 976   /* Implicitly delete any diagnostics in the dtor.  */
 977   auto_delete_vec<pending_diagnostic> m_diagnostics;
 978 };
 979
 980 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
 981    Verify that MODEL remains satisfiable.  */
 982
 983 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
 984   SELFTEST_BEGIN_STMT                                   \
 985     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
 986     ASSERT_TRUE (sat);                                  \
 987   SELFTEST_END_STMT
 988
 989 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
 990    Verify that the result is not satisfiable.  */
 991
 992 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
 993   SELFTEST_BEGIN_STMT                                   \
 994     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
 995     ASSERT_FALSE (sat);                         \
 996   SELFTEST_END_STMT
 997
 998 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
 999
1000 void assert_condition (const location &loc,
1001                        region_model &model,
1002                        const svalue *lhs, tree_code op, const svalue *rhs,
1003                        tristate expected);
1004
1005 void assert_condition (const location &loc,
1006                        region_model &model,
1007                        tree lhs, tree_code op, tree rhs,
1008                        tristate expected);
1009
1010 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1011    as "true".  */
1012
1013 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1014   SELFTEST_BEGIN_STMT                                                   \
1015   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1016                     tristate (tristate::TS_TRUE));              \
1017   SELFTEST_END_STMT
1018
1019 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1020    as "false".  */
1021
1022 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1023   SELFTEST_BEGIN_STMT                                                   \
1024   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1025                     tristate (tristate::TS_FALSE));             \
1026   SELFTEST_END_STMT
1027
1028 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1029    as "unknown".  */
1030
1031 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1032   SELFTEST_BEGIN_STMT                                                   \
1033   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1034                     tristate (tristate::TS_UNKNOWN));           \
1035   SELFTEST_END_STMT
1036
1037 } /* end of namespace selftest.  */
1038
1039 #endif /* #if CHECKING_P */
1040
1041 } // namespace ana
1042
1043 #endif /* GCC_ANALYZER_REGION_MODEL_H */