gcc/analyzer/region-model.h

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