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_bounded_ranges_constraints (0),
 193     m_num_client_items (0)
 194   {}
 195
 196   int m_num_svalues;
 197   int m_num_regions;
 198   int m_num_equiv_classes;
 199   int m_num_constraints;
 200   int m_num_bounded_ranges_constraints;
 201   int m_num_client_items;
 202 };
 203
 204 /* A base class for visiting regions and svalues, with do-nothing
 205    base implementations of the per-subclass vfuncs.  */
 206
 207 class visitor
 208 {
 209 public:
 210   virtual void visit_region_svalue (const region_svalue *) {}
 211   virtual void visit_constant_svalue (const constant_svalue *) {}
 212   virtual void visit_unknown_svalue (const unknown_svalue *) {}
 213   virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
 214   virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
 215   virtual void visit_initial_svalue (const initial_svalue *) {}
 216   virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
 217   virtual void visit_binop_svalue (const binop_svalue *) {}
 218   virtual void visit_sub_svalue (const sub_svalue *) {}
 219   virtual void visit_repeated_svalue (const repeated_svalue *) {}
 220   virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
 221   virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
 222   virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
 223   virtual void visit_widening_svalue (const widening_svalue *) {}
 224   virtual void visit_compound_svalue (const compound_svalue *) {}
 225   virtual void visit_conjured_svalue (const conjured_svalue *) {}
 226   virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
 227
 228   virtual void visit_region (const region *) {}
 229 };
 230
 231 } // namespace ana
 232
 233 namespace ana {
 234
 235 /* A class responsible for owning and consolidating region and svalue
 236    instances.
 237    region and svalue instances are immutable as far as clients are
 238    concerned, so they are provided as "const" ptrs.  */
 239
 240 class region_model_manager
 241 {
 242 public:
 243   region_model_manager ();
 244   ~region_model_manager ();
 245
 246   /* svalue consolidation.  */
 247   const svalue *get_or_create_constant_svalue (tree cst_expr);
 248   const svalue *get_or_create_int_cst (tree type, poly_int64);
 249   const svalue *get_or_create_unknown_svalue (tree type);
 250   const svalue *get_or_create_setjmp_svalue (const setjmp_record &r,
 251                                              tree type);
 252   const svalue *get_or_create_poisoned_svalue (enum poison_kind kind,
 253                                                tree type);
 254   const svalue *get_or_create_initial_value (const region *reg);
 255   const svalue *get_ptr_svalue (tree ptr_type, const region *pointee);
 256   const svalue *get_or_create_unaryop (tree type, enum tree_code op,
 257                                        const svalue *arg);
 258   const svalue *get_or_create_cast (tree type, const svalue *arg);
 259   const svalue *get_or_create_binop (tree type,
 260                                      enum tree_code op,
 261                                      const svalue *arg0, const svalue *arg1);
 262   const svalue *get_or_create_sub_svalue (tree type,
 263                                           const svalue *parent_svalue,
 264                                           const region *subregion);
 265   const svalue *get_or_create_repeated_svalue (tree type,
 266                                                const svalue *outer_size,
 267                                                const svalue *inner_svalue);
 268   const svalue *get_or_create_bits_within (tree type,
 269                                            const bit_range &bits,
 270                                            const svalue *inner_svalue);
 271   const svalue *get_or_create_unmergeable (const svalue *arg);
 272   const svalue *get_or_create_widening_svalue (tree type,
 273                                                const program_point &point,
 274                                                const svalue *base_svalue,
 275                                                const svalue *iter_svalue);
 276   const svalue *get_or_create_compound_svalue (tree type,
 277                                                const binding_map &map);
 278   const svalue *get_or_create_conjured_svalue (tree type, const gimple *stmt,
 279                                                const region *id_reg);
 280   const svalue *
 281   get_or_create_asm_output_svalue (tree type,
 282                                    const gasm *asm_stmt,
 283                                    unsigned output_idx,
 284                                    const vec<const svalue *> &inputs);
 285
 286   const svalue *maybe_get_char_from_string_cst (tree string_cst,
 287                                                 tree byte_offset_cst);
 288
 289   /* region consolidation.  */
 290   const stack_region * get_stack_region () const { return &m_stack_region; }
 291   const heap_region *get_heap_region () const { return &m_heap_region; }
 292   const code_region *get_code_region () const { return &m_code_region; }
 293   const globals_region *get_globals_region () const
 294   {
 295     return &m_globals_region;
 296   }
 297   const function_region *get_region_for_fndecl (tree fndecl);
 298   const label_region *get_region_for_label (tree label);
 299   const decl_region *get_region_for_global (tree expr);
 300   const region *get_field_region (const region *parent, tree field);
 301   const region *get_element_region (const region *parent,
 302                                     tree element_type,
 303                                     const svalue *index);
 304   const region *get_offset_region (const region *parent,
 305                                    tree type,
 306                                    const svalue *byte_offset);
 307   const region *get_sized_region (const region *parent,
 308                                   tree type,
 309                                   const svalue *byte_size_sval);
 310   const region *get_cast_region (const region *original_region,
 311                                  tree type);
 312   const frame_region *get_frame_region (const frame_region *calling_frame,
 313                                         function *fun);
 314   const region *get_symbolic_region (const svalue *sval);
 315   const string_region *get_region_for_string (tree string_cst);
 316
 317   const region *
 318   get_region_for_unexpected_tree_code (region_model_context *ctxt,
 319                                        tree t,
 320                                        const dump_location_t &loc);
 321
 322   unsigned alloc_region_id () { return m_next_region_id++; }
 323
 324   store_manager *get_store_manager () { return &m_store_mgr; }
 325   bounded_ranges_manager *get_range_manager () const { return m_range_mgr; }
 326
 327   /* Dynamically-allocated region instances.
 328      The number of these within the analysis can grow arbitrarily.
 329      They are still owned by the manager.  */
 330   const region *create_region_for_heap_alloc ();
 331   const region *create_region_for_alloca (const frame_region *frame);
 332
 333   void log_stats (logger *logger, bool show_objs) const;
 334
 335   void enable_complexity_check (void) { m_check_complexity = true; }
 336   void disable_complexity_check (void) { m_check_complexity = false; }
 337
 338 private:
 339   bool too_complex_p (const complexity &c) const;
 340   bool reject_if_too_complex (svalue *sval);
 341
 342   const svalue *maybe_fold_unaryop (tree type, enum tree_code op,
 343                                     const svalue *arg);
 344   const svalue *maybe_fold_binop (tree type, enum tree_code op,
 345                                   const svalue *arg0, const svalue *arg1);
 346   const svalue *maybe_fold_sub_svalue (tree type,
 347                                        const svalue *parent_svalue,
 348                                        const region *subregion);
 349   const svalue *maybe_fold_repeated_svalue (tree type,
 350                                             const svalue *outer_size,
 351                                             const svalue *inner_svalue);
 352   const svalue *maybe_fold_bits_within_svalue (tree type,
 353                                                const bit_range &bits,
 354                                                const svalue *inner_svalue);
 355   const svalue *maybe_undo_optimize_bit_field_compare (tree type,
 356                                                        const compound_svalue *compound_sval,
 357                                                        tree cst, const svalue *arg1);
 358   const svalue *maybe_fold_asm_output_svalue (tree type,
 359                                               const vec<const svalue *> &inputs);
 360
 361   unsigned m_next_region_id;
 362   root_region m_root_region;
 363   stack_region m_stack_region;
 364   heap_region m_heap_region;
 365
 366   /* svalue consolidation.  */
 367   typedef hash_map<tree, constant_svalue *> constants_map_t;
 368   constants_map_t m_constants_map;
 369
 370   typedef hash_map<tree, unknown_svalue *> unknowns_map_t;
 371   unknowns_map_t m_unknowns_map;
 372   const unknown_svalue *m_unknown_NULL;
 373
 374   typedef hash_map<poisoned_svalue::key_t,
 375                    poisoned_svalue *> poisoned_values_map_t;
 376   poisoned_values_map_t m_poisoned_values_map;
 377
 378   typedef hash_map<setjmp_svalue::key_t,
 379                    setjmp_svalue *> setjmp_values_map_t;
 380   setjmp_values_map_t m_setjmp_values_map;
 381
 382   typedef hash_map<const region *, initial_svalue *> initial_values_map_t;
 383   initial_values_map_t m_initial_values_map;
 384
 385   typedef hash_map<region_svalue::key_t, region_svalue *> pointer_values_map_t;
 386   pointer_values_map_t m_pointer_values_map;
 387
 388   typedef hash_map<unaryop_svalue::key_t,
 389                    unaryop_svalue *> unaryop_values_map_t;
 390   unaryop_values_map_t m_unaryop_values_map;
 391
 392   typedef hash_map<binop_svalue::key_t, binop_svalue *> binop_values_map_t;
 393   binop_values_map_t m_binop_values_map;
 394
 395   typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t;
 396   sub_values_map_t m_sub_values_map;
 397
 398   typedef hash_map<repeated_svalue::key_t,
 399                    repeated_svalue *> repeated_values_map_t;
 400   repeated_values_map_t m_repeated_values_map;
 401
 402   typedef hash_map<bits_within_svalue::key_t,
 403                    bits_within_svalue *> bits_within_values_map_t;
 404   bits_within_values_map_t m_bits_within_values_map;
 405
 406   typedef hash_map<const svalue *,
 407                    unmergeable_svalue *> unmergeable_values_map_t;
 408   unmergeable_values_map_t m_unmergeable_values_map;
 409
 410   typedef hash_map<widening_svalue::key_t,
 411                    widening_svalue */*,
 412                    widening_svalue::key_t::hash_map_traits*/>
 413     widening_values_map_t;
 414   widening_values_map_t m_widening_values_map;
 415
 416   typedef hash_map<compound_svalue::key_t,
 417                    compound_svalue *> compound_values_map_t;
 418   compound_values_map_t m_compound_values_map;
 419
 420   typedef hash_map<conjured_svalue::key_t,
 421                    conjured_svalue *> conjured_values_map_t;
 422   conjured_values_map_t m_conjured_values_map;
 423
 424   typedef hash_map<asm_output_svalue::key_t,
 425                    asm_output_svalue *> asm_output_values_map_t;
 426   asm_output_values_map_t m_asm_output_values_map;
 427
 428   bool m_check_complexity;
 429
 430   /* Maximum complexity of svalues that weren't rejected.  */
 431   complexity m_max_complexity;
 432
 433   /* region consolidation.  */
 434
 435   code_region m_code_region;
 436   typedef hash_map<tree, function_region *> fndecls_map_t;
 437   typedef fndecls_map_t::iterator fndecls_iterator_t;
 438   fndecls_map_t m_fndecls_map;
 439
 440   typedef hash_map<tree, label_region *> labels_map_t;
 441   typedef labels_map_t::iterator labels_iterator_t;
 442   labels_map_t m_labels_map;
 443
 444   globals_region m_globals_region;
 445   typedef hash_map<tree, decl_region *> globals_map_t;
 446   typedef globals_map_t::iterator globals_iterator_t;
 447   globals_map_t m_globals_map;
 448
 449   consolidation_map<field_region> m_field_regions;
 450   consolidation_map<element_region> m_element_regions;
 451   consolidation_map<offset_region> m_offset_regions;
 452   consolidation_map<sized_region> m_sized_regions;
 453   consolidation_map<cast_region> m_cast_regions;
 454   consolidation_map<frame_region> m_frame_regions;
 455   consolidation_map<symbolic_region> m_symbolic_regions;
 456
 457   typedef hash_map<tree, string_region *> string_map_t;
 458   string_map_t m_string_map;
 459
 460   store_manager m_store_mgr;
 461
 462   bounded_ranges_manager *m_range_mgr;
 463
 464   /* "Dynamically-allocated" region instances.
 465      The number of these within the analysis can grow arbitrarily.
 466      They are still owned by the manager.  */
 467   auto_delete_vec<region> m_managed_dynamic_regions;
 468 };
 469
 470 struct append_ssa_names_cb_data;
 471
 472 /* Helper class for handling calls to functions with known behavior.
 473    Implemented in region-model-impl-calls.c.  */
 474
 475 class call_details
 476 {
 477 public:
 478   call_details (const gcall *call, region_model *model,
 479                 region_model_context *ctxt);
 480
 481   region_model_context *get_ctxt () const { return m_ctxt; }
 482   uncertainty_t *get_uncertainty () const;
 483   tree get_lhs_type () const { return m_lhs_type; }
 484   const region *get_lhs_region () const { return m_lhs_region; }
 485
 486   bool maybe_set_lhs (const svalue *result) const;
 487
 488   unsigned num_args () const;
 489
 490   const gcall *get_call_stmt () const { return m_call; }
 491
 492   tree get_arg_tree (unsigned idx) const;
 493   tree get_arg_type (unsigned idx) const;
 494   const svalue *get_arg_svalue (unsigned idx) const;
 495   const char *get_arg_string_literal (unsigned idx) const;
 496
 497   tree get_fndecl_for_call () const;
 498
 499   void dump_to_pp (pretty_printer *pp, bool simple) const;
 500   void dump (bool simple) const;
 501
 502   const svalue *get_or_create_conjured_svalue (const region *) const;
 503
 504 private:
 505   const gcall *m_call;
 506   region_model *m_model;
 507   region_model_context *m_ctxt;
 508   tree m_lhs_type;
 509   const region *m_lhs_region;
 510 };
 511
 512 /* A region_model encapsulates a representation of the state of memory, with
 513    a tree of regions, along with their associated values.
 514    The representation is graph-like because values can be pointers to
 515    regions.
 516    It also stores:
 517    - a constraint_manager, capturing relationships between the values, and
 518    - dynamic extents, mapping dynamically-allocated regions to svalues (their
 519    capacities).  */
 520
 521 class region_model
 522 {
 523  public:
 524   typedef region_to_value_map dynamic_extents_t;
 525
 526   region_model (region_model_manager *mgr);
 527   region_model (const region_model &other);
 528   ~region_model ();
 529   region_model &operator= (const region_model &other);
 530
 531   bool operator== (const region_model &other) const;
 532   bool operator!= (const region_model &other) const
 533   {
 534     return !(*this == other);
 535   }
 536
 537   hashval_t hash () const;
 538
 539   void print (pretty_printer *pp) const;
 540
 541   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 542   void dump (FILE *fp, bool simple, bool multiline) const;
 543   void dump (bool simple) const;
 544
 545   void debug () const;
 546
 547   void validate () const;
 548
 549   void canonicalize ();
 550   bool canonicalized_p () const;
 551
 552   void
 553   on_stmt_pre (const gimple *stmt,
 554                bool *out_terminate_path,
 555                bool *out_unknown_side_effects,
 556                region_model_context *ctxt);
 557
 558   void on_assignment (const gassign *stmt, region_model_context *ctxt);
 559   const svalue *get_gassign_result (const gassign *assign,
 560                                     region_model_context *ctxt);
 561   void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
 562   bool on_call_pre (const gcall *stmt, region_model_context *ctxt,
 563                     bool *out_terminate_path);
 564   void on_call_post (const gcall *stmt,
 565                      bool unknown_side_effects,
 566                      region_model_context *ctxt);
 567
 568   void purge_state_involving (const svalue *sval, region_model_context *ctxt);
 569
 570   /* Specific handling for on_call_pre.  */
 571   void impl_call_alloca (const call_details &cd);
 572   void impl_call_analyzer_describe (const gcall *call,
 573                                     region_model_context *ctxt);
 574   void impl_call_analyzer_dump_capacity (const gcall *call,
 575                                          region_model_context *ctxt);
 576   void impl_call_analyzer_eval (const gcall *call,
 577                                 region_model_context *ctxt);
 578   void impl_call_builtin_expect (const call_details &cd);
 579   void impl_call_calloc (const call_details &cd);
 580   bool impl_call_error (const call_details &cd, unsigned min_args,
 581                         bool *out_terminate_path);
 582   void impl_call_fgets (const call_details &cd);
 583   void impl_call_fread (const call_details &cd);
 584   void impl_call_free (const call_details &cd);
 585   void impl_call_malloc (const call_details &cd);
 586   void impl_call_memcpy (const call_details &cd);
 587   void impl_call_memset (const call_details &cd);
 588   void impl_call_realloc (const call_details &cd);
 589   void impl_call_strchr (const call_details &cd);
 590   void impl_call_strcpy (const call_details &cd);
 591   void impl_call_strlen (const call_details &cd);
 592   void impl_call_operator_new (const call_details &cd);
 593   void impl_call_operator_delete (const call_details &cd);
 594   void impl_deallocation_call (const call_details &cd);
 595
 596   void handle_unrecognized_call (const gcall *call,
 597                                  region_model_context *ctxt);
 598   void get_reachable_svalues (svalue_set *out,
 599                               const svalue *extra_sval,
 600                               const uncertainty_t *uncertainty);
 601
 602   void on_return (const greturn *stmt, region_model_context *ctxt);
 603   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 604                   region_model_context *ctxt);
 605   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 606                    int setjmp_stack_depth, region_model_context *ctxt);
 607
 608   void update_for_phis (const supernode *snode,
 609                         const cfg_superedge *last_cfg_superedge,
 610                         region_model_context *ctxt);
 611
 612   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 613                    const region_model &old_state,
 614                    region_model_context *ctxt);
 615
 616   bool maybe_update_for_edge (const superedge &edge,
 617                               const gimple *last_stmt,
 618                               region_model_context *ctxt,
 619                               rejected_constraint **out);
 620
 621   void update_for_gcall (const gcall *call_stmt,
 622                          region_model_context *ctxt,
 623                          function *callee = NULL);
 624
 625   void update_for_return_gcall (const gcall *call_stmt,
 626                                 region_model_context *ctxt);
 627
 628   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 629                             region_model_context *ctxt);
 630   const frame_region *get_current_frame () const { return m_current_frame; }
 631   function * get_current_function () const;
 632   void pop_frame (const region *result_dst,
 633                   const svalue **out_result,
 634                   region_model_context *ctxt);
 635   int get_stack_depth () const;
 636   const frame_region *get_frame_at_index (int index) const;
 637
 638   const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
 639   const region *get_lvalue (tree expr, region_model_context *ctxt) const;
 640   const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
 641   const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
 642
 643   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 644                                region_model_context *ctxt) const;
 645
 646   const svalue *get_rvalue_for_bits (tree type,
 647                                      const region *reg,
 648                                      const bit_range &bits,
 649                                      region_model_context *ctxt) const;
 650
 651   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 652                   region_model_context *ctxt);
 653   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 654   void clobber_region (const region *reg);
 655   void purge_region (const region *reg);
 656   void fill_region (const region *reg, const svalue *sval);
 657   void zero_fill_region (const region *reg);
 658   void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 659
 660   void copy_region (const region *dst_reg, const region *src_reg,
 661                     region_model_context *ctxt);
 662   tristate eval_condition (const svalue *lhs,
 663                            enum tree_code op,
 664                            const svalue *rhs) const;
 665   tristate eval_condition_without_cm (const svalue *lhs,
 666                                       enum tree_code op,
 667                                       const svalue *rhs) const;
 668   tristate compare_initial_and_pointer (const initial_svalue *init,
 669                                         const region_svalue *ptr) const;
 670   tristate eval_condition (tree lhs,
 671                            enum tree_code op,
 672                            tree rhs,
 673                            region_model_context *ctxt);
 674   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 675                        region_model_context *ctxt);
 676   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 677                        region_model_context *ctxt,
 678                        rejected_constraint **out);
 679
 680   const region *create_region_for_heap_alloc (const svalue *size_in_bytes,
 681                                               region_model_context *ctxt);
 682   const region *create_region_for_alloca (const svalue *size_in_bytes,
 683                                           region_model_context *ctxt);
 684
 685   tree get_representative_tree (const svalue *sval) const;
 686   path_var
 687   get_representative_path_var (const svalue *sval,
 688                                svalue_set *visited) const;
 689   path_var
 690   get_representative_path_var (const region *reg,
 691                                svalue_set *visited) const;
 692
 693   /* For selftests.  */
 694   constraint_manager *get_constraints ()
 695   {
 696     return m_constraints;
 697   }
 698
 699   store *get_store () { return &m_store; }
 700   const store *get_store () const { return &m_store; }
 701
 702   const dynamic_extents_t &
 703   get_dynamic_extents () const
 704   {
 705     return m_dynamic_extents;
 706   }
 707   const svalue *get_dynamic_extents (const region *reg) const;
 708   void set_dynamic_extents (const region *reg,
 709                             const svalue *size_in_bytes,
 710                             region_model_context *ctxt);
 711   void unset_dynamic_extents (const region *reg);
 712
 713   region_model_manager *get_manager () const { return m_mgr; }
 714   bounded_ranges_manager *get_range_manager () const
 715   {
 716     return m_mgr->get_range_manager ();
 717   }
 718
 719   void unbind_region_and_descendents (const region *reg,
 720                                       enum poison_kind pkind);
 721
 722   bool can_merge_with_p (const region_model &other_model,
 723                          const program_point &point,
 724                          region_model *out_model,
 725                          const extrinsic_state *ext_state = NULL,
 726                          const program_state *state_a = NULL,
 727                          const program_state *state_b = NULL) const;
 728
 729   tree get_fndecl_for_call (const gcall *call,
 730                             region_model_context *ctxt);
 731
 732   void get_ssa_name_regions_for_current_frame
 733     (auto_vec<const decl_region *> *out) const;
 734   static void append_ssa_names_cb (const region *base_reg,
 735                                    struct append_ssa_names_cb_data *data);
 736
 737   const svalue *get_store_value (const region *reg,
 738                                  region_model_context *ctxt) const;
 739
 740   bool region_exists_p (const region *reg) const;
 741
 742   void loop_replay_fixup (const region_model *dst_state);
 743
 744   const svalue *get_capacity (const region *reg) const;
 745
 746   /* Implemented in sm-malloc.cc  */
 747   void on_realloc_with_move (const call_details &cd,
 748                              const svalue *old_ptr_sval,
 749                              const svalue *new_ptr_sval);
 750
 751  private:
 752   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 753   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 754
 755   path_var
 756   get_representative_path_var_1 (const svalue *sval,
 757                                  svalue_set *visited) const;
 758   path_var
 759   get_representative_path_var_1 (const region *reg,
 760                                  svalue_set *visited) const;
 761
 762   bool add_constraint (const svalue *lhs,
 763                        enum tree_code op,
 764                        const svalue *rhs,
 765                        region_model_context *ctxt);
 766   bool add_constraints_from_binop (const svalue *outer_lhs,
 767                                    enum tree_code outer_op,
 768                                    const svalue *outer_rhs,
 769                                    bool *out,
 770                                    region_model_context *ctxt);
 771
 772   void update_for_call_superedge (const call_superedge &call_edge,
 773                                   region_model_context *ctxt);
 774   void update_for_return_superedge (const return_superedge &return_edge,
 775                                     region_model_context *ctxt);
 776   void update_for_call_summary (const callgraph_superedge &cg_sedge,
 777                                 region_model_context *ctxt);
 778   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 779                                     const gcond *cond_stmt,
 780                                     region_model_context *ctxt,
 781                                     rejected_constraint **out);
 782   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 783                                       const gswitch *switch_stmt,
 784                                       region_model_context *ctxt,
 785                                       rejected_constraint **out);
 786   bool apply_constraints_for_exception (const gimple *last_stmt,
 787                                         region_model_context *ctxt,
 788                                         rejected_constraint **out);
 789
 790   int poison_any_pointers_to_descendents (const region *reg,
 791                                           enum poison_kind pkind);
 792
 793   void on_top_level_param (tree param, region_model_context *ctxt);
 794
 795   bool called_from_main_p () const;
 796   const svalue *get_initial_value_for_global (const region *reg) const;
 797
 798   const svalue *check_for_poison (const svalue *sval,
 799                                   tree expr,
 800                                   region_model_context *ctxt) const;
 801
 802   void check_dynamic_size_for_taint (enum memory_space mem_space,
 803                                      const svalue *size_in_bytes,
 804                                      region_model_context *ctxt) const;
 805
 806   void check_region_for_taint (const region *reg,
 807                                enum access_direction dir,
 808                                region_model_context *ctxt) const;
 809
 810   void check_for_writable_region (const region* dest_reg,
 811                                   region_model_context *ctxt) const;
 812   void check_region_access (const region *reg,
 813                             enum access_direction dir,
 814                             region_model_context *ctxt) const;
 815   void check_region_for_write (const region *dest_reg,
 816                                region_model_context *ctxt) const;
 817   void check_region_for_read (const region *src_reg,
 818                               region_model_context *ctxt) const;
 819
 820   /* Storing this here to avoid passing it around everywhere.  */
 821   region_model_manager *const m_mgr;
 822
 823   store m_store;
 824
 825   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 826
 827   const frame_region *m_current_frame;
 828
 829   /* Map from base region to size in bytes, for tracking the sizes of
 830      dynamically-allocated regions.
 831      This is part of the region_model rather than the region to allow for
 832      memory regions to be resized (e.g. by realloc).  */
 833   dynamic_extents_t m_dynamic_extents;
 834 };
 835
 836 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 837    uninitialized value).  This abstract base class encapsulates an interface
 838    for the region model to use when emitting such warnings.
 839
 840    Having this as an abstract base class allows us to support the various
 841    operations needed by program_state in the analyzer within region_model,
 842    whilst keeping them somewhat modularized.  */
 843
 844 class region_model_context
 845 {
 846  public:
 847   /* Hook for clients to store pending diagnostics.
 848      Return true if the diagnostic was stored, or false if it was deleted.  */
 849   virtual bool warn (pending_diagnostic *d) = 0;
 850
 851   /* Hook for clients to be notified when an SVAL that was reachable
 852      in a previous state is no longer live, so that clients can emit warnings
 853      about leaks.  */
 854   virtual void on_svalue_leak (const svalue *sval) = 0;
 855
 856   /* Hook for clients to be notified when the set of explicitly live
 857      svalues changes, so that they can purge state relating to dead
 858      svalues.  */
 859   virtual void on_liveness_change (const svalue_set &live_svalues,
 860                                    const region_model *model) = 0;
 861
 862   virtual logger *get_logger () = 0;
 863
 864   /* Hook for clients to be notified when the condition
 865      "LHS OP RHS" is added to the region model.
 866      This exists so that state machines can detect tests on edges,
 867      and use them to trigger sm-state transitions (e.g. transitions due
 868      to ptrs becoming known to be NULL or non-NULL, rather than just
 869      "unchecked") */
 870   virtual void on_condition (const svalue *lhs,
 871                              enum tree_code op,
 872                              const svalue *rhs) = 0;
 873
 874   /* Hooks for clients to be notified when an unknown change happens
 875      to SVAL (in response to a call to an unknown function).  */
 876   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 877
 878   /* Hooks for clients to be notified when a phi node is handled,
 879      where RHS is the pertinent argument.  */
 880   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 881
 882   /* Hooks for clients to be notified when the region model doesn't
 883      know how to handle the tree code of T at LOC.  */
 884   virtual void on_unexpected_tree_code (tree t,
 885                                         const dump_location_t &loc) = 0;
 886
 887   /* Hook for clients to be notified when a function_decl escapes.  */
 888   virtual void on_escaped_function (tree fndecl) = 0;
 889
 890   virtual uncertainty_t *get_uncertainty () = 0;
 891
 892   /* Hook for clients to purge state involving SVAL.  */
 893   virtual void purge_state_involving (const svalue *sval) = 0;
 894
 895   /* Hook for clients to split state with a non-standard path.
 896      Take ownership of INFO.  */
 897   virtual void bifurcate (custom_edge_info *info) = 0;
 898
 899   /* Hook for clients to terminate the standard path.  */
 900   virtual void terminate_path () = 0;
 901
 902   virtual const extrinsic_state *get_ext_state () const = 0;
 903
 904   /* Hook for clients to access the "malloc" state machine in
 905      any underlying program_state.  */
 906   virtual bool get_malloc_map (sm_state_map **out_smap,
 907                                const state_machine **out_sm,
 908                                unsigned *out_sm_idx) = 0;
 909   /* Likewise for the "taint" state machine.  */
 910   virtual bool get_taint_map (sm_state_map **out_smap,
 911                               const state_machine **out_sm,
 912                               unsigned *out_sm_idx) = 0;
 913 };
 914
 915 /* A "do nothing" subclass of region_model_context.  */
 916
 917 class noop_region_model_context : public region_model_context
 918 {
 919 public:
 920   bool warn (pending_diagnostic *) OVERRIDE { return false; }
 921   void on_svalue_leak (const svalue *) OVERRIDE {}
 922   void on_liveness_change (const svalue_set &,
 923                            const region_model *) OVERRIDE {}
 924   logger *get_logger () OVERRIDE { return NULL; }
 925   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
 926                      enum tree_code op ATTRIBUTE_UNUSED,
 927                      const svalue *rhs ATTRIBUTE_UNUSED) OVERRIDE
 928   {
 929   }
 930   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 931                           bool is_mutable ATTRIBUTE_UNUSED) OVERRIDE
 932   {
 933   }
 934   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 935                tree rhs ATTRIBUTE_UNUSED) OVERRIDE
 936   {
 937   }
 938   void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
 939
 940   void on_escaped_function (tree) OVERRIDE {}
 941
 942   uncertainty_t *get_uncertainty () OVERRIDE { return NULL; }
 943
 944   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) OVERRIDE {}
 945
 946   void bifurcate (custom_edge_info *info) OVERRIDE;
 947   void terminate_path () OVERRIDE;
 948
 949   const extrinsic_state *get_ext_state () const OVERRIDE { return NULL; }
 950
 951   bool get_malloc_map (sm_state_map **,
 952                        const state_machine **,
 953                        unsigned *) OVERRIDE
 954   {
 955     return false;
 956   }
 957   bool get_taint_map (sm_state_map **,
 958                       const state_machine **,
 959                       unsigned *) OVERRIDE
 960   {
 961     return false;
 962   }
 963 };
 964
 965 /* A subclass of region_model_context for determining if operations fail
 966    e.g. "can we generate a region for the lvalue of EXPR?".  */
 967
 968 class tentative_region_model_context : public noop_region_model_context
 969 {
 970 public:
 971   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 972
 973   void on_unexpected_tree_code (tree, const dump_location_t &)
 974     FINAL OVERRIDE
 975   {
 976     m_num_unexpected_codes++;
 977   }
 978
 979   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 980
 981 private:
 982   int m_num_unexpected_codes;
 983 };
 984
 985 /* A bundle of data for use when attempting to merge two region_model
 986    instances to make a third.  */
 987
 988 struct model_merger
 989 {
 990   model_merger (const region_model *model_a,
 991                 const region_model *model_b,
 992                 const program_point &point,
 993                 region_model *merged_model,
 994                 const extrinsic_state *ext_state,
 995                 const program_state *state_a,
 996                 const program_state *state_b)
 997   : m_model_a (model_a), m_model_b (model_b),
 998     m_point (point),
 999     m_merged_model (merged_model),
1000     m_ext_state (ext_state),
1001     m_state_a (state_a), m_state_b (state_b)
1002   {
1003   }
1004
1005   void dump_to_pp (pretty_printer *pp, bool simple) const;
1006   void dump (FILE *fp, bool simple) const;
1007   void dump (bool simple) const;
1008
1009   region_model_manager *get_manager () const
1010   {
1011     return m_model_a->get_manager ();
1012   }
1013
1014   bool mergeable_svalue_p (const svalue *) const;
1015
1016   const region_model *m_model_a;
1017   const region_model *m_model_b;
1018   const program_point &m_point;
1019   region_model *m_merged_model;
1020
1021   const extrinsic_state *m_ext_state;
1022   const program_state *m_state_a;
1023   const program_state *m_state_b;
1024 };
1025
1026 /* A record that can (optionally) be written out when
1027    region_model::add_constraint fails.  */
1028
1029 class rejected_constraint
1030 {
1031 public:
1032   virtual ~rejected_constraint () {}
1033   virtual void dump_to_pp (pretty_printer *pp) const = 0;
1034
1035   const region_model &get_model () const { return m_model; }
1036
1037 protected:
1038   rejected_constraint (const region_model &model)
1039   : m_model (model)
1040   {}
1041
1042   region_model m_model;
1043 };
1044
1045 class rejected_op_constraint : public rejected_constraint
1046 {
1047 public:
1048   rejected_op_constraint (const region_model &model,
1049                           tree lhs, enum tree_code op, tree rhs)
1050   : rejected_constraint (model),
1051     m_lhs (lhs), m_op (op), m_rhs (rhs)
1052   {}
1053
1054   void dump_to_pp (pretty_printer *pp) const FINAL OVERRIDE;
1055
1056   tree m_lhs;
1057   enum tree_code m_op;
1058   tree m_rhs;
1059 };
1060
1061 class rejected_ranges_constraint : public rejected_constraint
1062 {
1063 public:
1064   rejected_ranges_constraint (const region_model &model,
1065                               tree expr, const bounded_ranges *ranges)
1066   : rejected_constraint (model),
1067     m_expr (expr), m_ranges (ranges)
1068   {}
1069
1070   void dump_to_pp (pretty_printer *pp) const FINAL OVERRIDE;
1071
1072 private:
1073   tree m_expr;
1074   const bounded_ranges *m_ranges;
1075 };
1076
1077 /* A bundle of state.  */
1078
1079 class engine
1080 {
1081 public:
1082   region_model_manager *get_model_manager () { return &m_mgr; }
1083
1084   void log_stats (logger *logger) const;
1085
1086 private:
1087   region_model_manager m_mgr;
1088
1089 };
1090
1091 } // namespace ana
1092
1093 extern void debug (const region_model &rmodel);
1094
1095 namespace ana {
1096
1097 #if CHECKING_P
1098
1099 namespace selftest {
1100
1101 using namespace ::selftest;
1102
1103 /* An implementation of region_model_context for use in selftests, which
1104    stores any pending_diagnostic instances passed to it.  */
1105
1106 class test_region_model_context : public noop_region_model_context
1107 {
1108 public:
1109   bool warn (pending_diagnostic *d) FINAL OVERRIDE
1110   {
1111     m_diagnostics.safe_push (d);
1112     return true;
1113   }
1114
1115   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1116
1117   void on_unexpected_tree_code (tree t, const dump_location_t &)
1118     FINAL OVERRIDE
1119   {
1120     internal_error ("unhandled tree code: %qs",
1121                     get_tree_code_name (TREE_CODE (t)));
1122   }
1123
1124 private:
1125   /* Implicitly delete any diagnostics in the dtor.  */
1126   auto_delete_vec<pending_diagnostic> m_diagnostics;
1127 };
1128
1129 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1130    Verify that MODEL remains satisfiable.  */
1131
1132 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1133   SELFTEST_BEGIN_STMT                                   \
1134     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1135     ASSERT_TRUE (sat);                                  \
1136   SELFTEST_END_STMT
1137
1138 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1139    Verify that the result is not satisfiable.  */
1140
1141 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
1142   SELFTEST_BEGIN_STMT                                   \
1143     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1144     ASSERT_FALSE (sat);                         \
1145   SELFTEST_END_STMT
1146
1147 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
1148
1149 void assert_condition (const location &loc,
1150                        region_model &model,
1151                        const svalue *lhs, tree_code op, const svalue *rhs,
1152                        tristate expected);
1153
1154 void assert_condition (const location &loc,
1155                        region_model &model,
1156                        tree lhs, tree_code op, tree rhs,
1157                        tristate expected);
1158
1159 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1160    as "true".  */
1161
1162 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1163   SELFTEST_BEGIN_STMT                                                   \
1164   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1165                     tristate (tristate::TS_TRUE));              \
1166   SELFTEST_END_STMT
1167
1168 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1169    as "false".  */
1170
1171 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1172   SELFTEST_BEGIN_STMT                                                   \
1173   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1174                     tristate (tristate::TS_FALSE));             \
1175   SELFTEST_END_STMT
1176
1177 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1178    as "unknown".  */
1179
1180 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1181   SELFTEST_BEGIN_STMT                                                   \
1182   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1183                     tristate (tristate::TS_UNKNOWN));           \
1184   SELFTEST_END_STMT
1185
1186 } /* end of namespace selftest.  */
1187
1188 #endif /* #if CHECKING_P */
1189
1190 } // namespace ana
1191
1192 #endif /* GCC_ANALYZER_REGION_MODEL_H */