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 /* Various operations delete information from a region_model.
 132
 133    This struct tracks how many of each kind of entity were purged (e.g.
 134    for selftests, and for debugging).  */
 135
 136 struct purge_stats
 137 {
 138   purge_stats ()
 139   : m_num_svalues (0),
 140     m_num_regions (0),
 141     m_num_equiv_classes (0),
 142     m_num_constraints (0),
 143     m_num_client_items (0)
 144   {}
 145
 146   int m_num_svalues;
 147   int m_num_regions;
 148   int m_num_equiv_classes;
 149   int m_num_constraints;
 150   int m_num_client_items;
 151 };
 152
 153 /* A base class for visiting regions and svalues, with do-nothing
 154    base implementations of the per-subclass vfuncs.  */
 155
 156 class visitor
 157 {
 158 public:
 159   virtual void visit_region_svalue (const region_svalue *) {}
 160   virtual void visit_constant_svalue (const constant_svalue *) {}
 161   virtual void visit_unknown_svalue (const unknown_svalue *) {}
 162   virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
 163   virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
 164   virtual void visit_initial_svalue (const initial_svalue *) {}
 165   virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
 166   virtual void visit_binop_svalue (const binop_svalue *) {}
 167   virtual void visit_sub_svalue (const sub_svalue *) {}
 168   virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
 169   virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
 170   virtual void visit_widening_svalue (const widening_svalue *) {}
 171   virtual void visit_compound_svalue (const compound_svalue *) {}
 172   virtual void visit_conjured_svalue (const conjured_svalue *) {}
 173
 174   virtual void visit_region (const region *) {}
 175 };
 176
 177 } // namespace ana
 178
 179 namespace ana {
 180
 181 /* A class responsible for owning and consolidating region and svalue
 182    instances.
 183    region and svalue instances are immutable as far as clients are
 184    concerned, so they are provided as "const" ptrs.  */
 185
 186 class region_model_manager
 187 {
 188 public:
 189   region_model_manager ();
 190   ~region_model_manager ();
 191
 192   /* svalue consolidation.  */
 193   const svalue *get_or_create_constant_svalue (tree cst_expr);
 194   const svalue *get_or_create_unknown_svalue (tree type);
 195   const svalue *get_or_create_setjmp_svalue (const setjmp_record &r,
 196                                              tree type);
 197   const svalue *get_or_create_poisoned_svalue (enum poison_kind kind,
 198                                                tree type);
 199   const svalue *get_or_create_initial_value (const region *reg);
 200   const svalue *get_ptr_svalue (tree ptr_type, const region *pointee);
 201   const svalue *get_or_create_unaryop (tree type, enum tree_code op,
 202                                        const svalue *arg);
 203   const svalue *get_or_create_cast (tree type, const svalue *arg);
 204   const svalue *get_or_create_binop (tree type,
 205                                      enum tree_code op,
 206                                      const svalue *arg0, const svalue *arg1);
 207   const svalue *get_or_create_sub_svalue (tree type,
 208                                           const svalue *parent_svalue,
 209                                           const region *subregion);
 210   const svalue *get_or_create_unmergeable (const svalue *arg);
 211   const svalue *get_or_create_widening_svalue (tree type,
 212                                                const program_point &point,
 213                                                const svalue *base_svalue,
 214                                                const svalue *iter_svalue);
 215   const svalue *get_or_create_compound_svalue (tree type,
 216                                                const binding_map &map);
 217   const svalue *get_or_create_conjured_svalue (tree type, const gimple *stmt,
 218                                                const region *id_reg);
 219
 220   const svalue *maybe_get_char_from_string_cst (tree string_cst,
 221                                                 tree byte_offset_cst);
 222
 223   /* region consolidation.  */
 224   const stack_region * get_stack_region () const { return &m_stack_region; }
 225   const heap_region *get_heap_region () const { return &m_heap_region; }
 226   const code_region *get_code_region () const { return &m_code_region; }
 227   const globals_region *get_globals_region () const
 228   {
 229     return &m_globals_region;
 230   }
 231   const function_region *get_region_for_fndecl (tree fndecl);
 232   const label_region *get_region_for_label (tree label);
 233   const decl_region *get_region_for_global (tree expr);
 234   const region *get_field_region (const region *parent, tree field);
 235   const region *get_element_region (const region *parent,
 236                                     tree element_type,
 237                                     const svalue *index);
 238   const region *get_offset_region (const region *parent,
 239                                    tree type,
 240                                    const svalue *byte_offset);
 241   const region *get_cast_region (const region *original_region,
 242                                  tree type);
 243   const frame_region *get_frame_region (const frame_region *calling_frame,
 244                                         function *fun);
 245   const region *get_symbolic_region (const svalue *sval);
 246   const string_region *get_region_for_string (tree string_cst);
 247
 248   const region *
 249   get_region_for_unexpected_tree_code (region_model_context *ctxt,
 250                                        tree t,
 251                                        const dump_location_t &loc);
 252
 253   unsigned alloc_region_id () { return m_next_region_id++; }
 254
 255   store_manager *get_store_manager () { return &m_store_mgr; }
 256
 257   /* Dynamically-allocated region instances.
 258      The number of these within the analysis can grow arbitrarily.
 259      They are still owned by the manager.  */
 260   const region *create_region_for_heap_alloc ();
 261   const region *create_region_for_alloca (const frame_region *frame);
 262
 263   void log_stats (logger *logger, bool show_objs) const;
 264
 265 private:
 266   bool too_complex_p (const complexity &c) const;
 267   bool reject_if_too_complex (svalue *sval);
 268
 269   const svalue *maybe_fold_unaryop (tree type, enum tree_code op,
 270                                     const svalue *arg);
 271   const svalue *maybe_fold_binop (tree type, enum tree_code op,
 272                                   const svalue *arg0, const svalue *arg1);
 273   const svalue *maybe_fold_sub_svalue (tree type,
 274                                        const svalue *parent_svalue,
 275                                        const region *subregion);
 276
 277   unsigned m_next_region_id;
 278   root_region m_root_region;
 279   stack_region m_stack_region;
 280   heap_region m_heap_region;
 281
 282   /* svalue consolidation.  */
 283   typedef hash_map<tree, constant_svalue *> constants_map_t;
 284   constants_map_t m_constants_map;
 285
 286   typedef hash_map<tree, unknown_svalue *> unknowns_map_t;
 287   unknowns_map_t m_unknowns_map;
 288   const unknown_svalue *m_unknown_NULL;
 289
 290   typedef hash_map<poisoned_svalue::key_t,
 291                    poisoned_svalue *> poisoned_values_map_t;
 292   poisoned_values_map_t m_poisoned_values_map;
 293
 294   typedef hash_map<setjmp_svalue::key_t,
 295                    setjmp_svalue *> setjmp_values_map_t;
 296   setjmp_values_map_t m_setjmp_values_map;
 297
 298   typedef hash_map<const region *, initial_svalue *> initial_values_map_t;
 299   initial_values_map_t m_initial_values_map;
 300
 301   typedef hash_map<region_svalue::key_t, region_svalue *> pointer_values_map_t;
 302   pointer_values_map_t m_pointer_values_map;
 303
 304   typedef hash_map<unaryop_svalue::key_t,
 305                    unaryop_svalue *> unaryop_values_map_t;
 306   unaryop_values_map_t m_unaryop_values_map;
 307
 308   typedef hash_map<binop_svalue::key_t, binop_svalue *> binop_values_map_t;
 309   binop_values_map_t m_binop_values_map;
 310
 311   typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t;
 312   sub_values_map_t m_sub_values_map;
 313
 314   typedef hash_map<const svalue *,
 315                    unmergeable_svalue *> unmergeable_values_map_t;
 316   unmergeable_values_map_t m_unmergeable_values_map;
 317
 318   typedef hash_map<widening_svalue::key_t,
 319                    widening_svalue */*,
 320                    widening_svalue::key_t::hash_map_traits*/>
 321     widening_values_map_t;
 322   widening_values_map_t m_widening_values_map;
 323
 324   typedef hash_map<compound_svalue::key_t,
 325                    compound_svalue *> compound_values_map_t;
 326   compound_values_map_t m_compound_values_map;
 327
 328   typedef hash_map<conjured_svalue::key_t,
 329                    conjured_svalue *> conjured_values_map_t;
 330   conjured_values_map_t m_conjured_values_map;
 331
 332   /* Maximum complexity of svalues that weren't rejected.  */
 333   complexity m_max_complexity;
 334
 335   /* region consolidation.  */
 336
 337   code_region m_code_region;
 338   typedef hash_map<tree, function_region *> fndecls_map_t;
 339   typedef fndecls_map_t::iterator fndecls_iterator_t;
 340   fndecls_map_t m_fndecls_map;
 341
 342   typedef hash_map<tree, label_region *> labels_map_t;
 343   typedef labels_map_t::iterator labels_iterator_t;
 344   labels_map_t m_labels_map;
 345
 346   globals_region m_globals_region;
 347   typedef hash_map<tree, decl_region *> globals_map_t;
 348   typedef globals_map_t::iterator globals_iterator_t;
 349   globals_map_t m_globals_map;
 350
 351   consolidation_map<field_region> m_field_regions;
 352   consolidation_map<element_region> m_element_regions;
 353   consolidation_map<offset_region> m_offset_regions;
 354   consolidation_map<cast_region> m_cast_regions;
 355   consolidation_map<frame_region> m_frame_regions;
 356   consolidation_map<symbolic_region> m_symbolic_regions;
 357
 358   typedef hash_map<tree, string_region *> string_map_t;
 359   string_map_t m_string_map;
 360
 361   store_manager m_store_mgr;
 362
 363   /* "Dynamically-allocated" region instances.
 364      The number of these within the analysis can grow arbitrarily.
 365      They are still owned by the manager.  */
 366   auto_delete_vec<region> m_managed_dynamic_regions;
 367 };
 368
 369 struct append_ssa_names_cb_data;
 370
 371 /* Helper class for handling calls to functions with known behavior.
 372    Implemented in region-model-impl-calls.c.  */
 373
 374 class call_details
 375 {
 376 public:
 377   call_details (const gcall *call, region_model *model,
 378                 region_model_context *ctxt);
 379
 380   region_model_context *get_ctxt () const { return m_ctxt; }
 381   tree get_lhs_type () const { return m_lhs_type; }
 382   const region *get_lhs_region () const { return m_lhs_region; }
 383
 384   bool maybe_set_lhs (const svalue *result) const;
 385
 386   tree get_arg_tree (unsigned idx) const;
 387   tree get_arg_type (unsigned idx) const;
 388   const svalue *get_arg_svalue (unsigned idx) const;
 389
 390   void dump_to_pp (pretty_printer *pp, bool simple) const;
 391   void dump (bool simple) const;
 392
 393 private:
 394   const gcall *m_call;
 395   region_model *m_model;
 396   region_model_context *m_ctxt;
 397   tree m_lhs_type;
 398   const region *m_lhs_region;
 399 };
 400
 401 /* A region_model encapsulates a representation of the state of memory, with
 402    a tree of regions, along with their associated values.
 403    The representation is graph-like because values can be pointers to
 404    regions.
 405    It also stores a constraint_manager, capturing relationships between
 406    the values.  */
 407
 408 class region_model
 409 {
 410  public:
 411   region_model (region_model_manager *mgr);
 412   region_model (const region_model &other);
 413   ~region_model ();
 414
 415 #if 0//__cplusplus >= 201103
 416   region_model (region_model &&other);
 417 #endif
 418
 419   region_model &operator= (const region_model &other);
 420
 421   bool operator== (const region_model &other) const;
 422   bool operator!= (const region_model &other) const
 423   {
 424     return !(*this == other);
 425   }
 426
 427   hashval_t hash () const;
 428
 429   void print (pretty_printer *pp) const;
 430
 431   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 432   void dump (FILE *fp, bool simple, bool multiline) const;
 433   void dump (bool simple) const;
 434
 435   void debug () const;
 436
 437   void validate () const;
 438
 439   void canonicalize ();
 440   bool canonicalized_p () const;
 441
 442   void on_assignment (const gassign *stmt, region_model_context *ctxt);
 443   const svalue *get_gassign_result (const gassign *assign,
 444                                     region_model_context *ctxt);
 445   bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
 446   void on_call_post (const gcall *stmt,
 447                      bool unknown_side_effects,
 448                      region_model_context *ctxt);
 449
 450   /* Specific handling for on_call_pre.  */
 451   bool impl_call_alloca (const call_details &cd);
 452   void impl_call_analyzer_describe (const gcall *call,
 453                                     region_model_context *ctxt);
 454   void impl_call_analyzer_eval (const gcall *call,
 455                                 region_model_context *ctxt);
 456   bool impl_call_builtin_expect (const call_details &cd);
 457   bool impl_call_calloc (const call_details &cd);
 458   void impl_call_free (const call_details &cd);
 459   bool impl_call_malloc (const call_details &cd);
 460   void impl_call_memcpy (const call_details &cd);
 461   bool impl_call_memset (const call_details &cd);
 462   void impl_call_strcpy (const call_details &cd);
 463   bool impl_call_strlen (const call_details &cd);
 464   bool impl_call_operator_new (const call_details &cd);
 465   bool impl_call_operator_delete (const call_details &cd);
 466   void impl_deallocation_call (const call_details &cd);
 467
 468   void handle_unrecognized_call (const gcall *call,
 469                                  region_model_context *ctxt);
 470   void get_reachable_svalues (svalue_set *out,
 471                               const svalue *extra_sval);
 472
 473   void on_return (const greturn *stmt, region_model_context *ctxt);
 474   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 475                   region_model_context *ctxt);
 476   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 477                    int setjmp_stack_depth, region_model_context *ctxt);
 478
 479   void update_for_phis (const supernode *snode,
 480                         const cfg_superedge *last_cfg_superedge,
 481                         region_model_context *ctxt);
 482
 483   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 484                    region_model_context *ctxt);
 485
 486   bool maybe_update_for_edge (const superedge &edge,
 487                               const gimple *last_stmt,
 488                               region_model_context *ctxt,
 489                               rejected_constraint **out);
 490
 491   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 492                             region_model_context *ctxt);
 493   const frame_region *get_current_frame () const { return m_current_frame; }
 494   function * get_current_function () const;
 495   void pop_frame (const region *result_dst,
 496                   const svalue **out_result,
 497                   region_model_context *ctxt);
 498   int get_stack_depth () const;
 499   const frame_region *get_frame_at_index (int index) const;
 500
 501   const region *get_lvalue (path_var pv, region_model_context *ctxt);
 502   const region *get_lvalue (tree expr, region_model_context *ctxt);
 503   const svalue *get_rvalue (path_var pv, region_model_context *ctxt);
 504   const svalue *get_rvalue (tree expr, region_model_context *ctxt);
 505
 506   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 507                                region_model_context *ctxt);
 508
 509   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 510                   region_model_context *ctxt);
 511   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 512   void clobber_region (const region *reg);
 513   void purge_region (const region *reg);
 514   void zero_fill_region (const region *reg);
 515   void mark_region_as_unknown (const region *reg);
 516
 517   void copy_region (const region *dst_reg, const region *src_reg,
 518                     region_model_context *ctxt);
 519   tristate eval_condition (const svalue *lhs,
 520                            enum tree_code op,
 521                            const svalue *rhs) const;
 522   tristate eval_condition_without_cm (const svalue *lhs,
 523                                       enum tree_code op,
 524                                       const svalue *rhs) const;
 525   tristate compare_initial_and_pointer (const initial_svalue *init,
 526                                         const region_svalue *ptr) const;
 527   tristate eval_condition (tree lhs,
 528                            enum tree_code op,
 529                            tree rhs,
 530                            region_model_context *ctxt);
 531   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 532                        region_model_context *ctxt);
 533   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 534                        region_model_context *ctxt,
 535                        rejected_constraint **out);
 536
 537   const region *create_region_for_heap_alloc (const svalue *size_in_bytes);
 538   const region *create_region_for_alloca (const svalue *size_in_bytes);
 539
 540   tree get_representative_tree (const svalue *sval) const;
 541   path_var
 542   get_representative_path_var (const svalue *sval,
 543                                svalue_set *visited) const;
 544   path_var
 545   get_representative_path_var (const region *reg,
 546                                svalue_set *visited) const;
 547
 548   /* For selftests.  */
 549   constraint_manager *get_constraints ()
 550   {
 551     return m_constraints;
 552   }
 553
 554   store *get_store () { return &m_store; }
 555   const store *get_store () const { return &m_store; }
 556
 557   region_model_manager *get_manager () const { return m_mgr; }
 558
 559   void unbind_region_and_descendents (const region *reg,
 560                                       enum poison_kind pkind);
 561
 562   bool can_merge_with_p (const region_model &other_model,
 563                          const program_point &point,
 564                          region_model *out_model) const;
 565
 566   tree get_fndecl_for_call (const gcall *call,
 567                             region_model_context *ctxt);
 568
 569   void get_ssa_name_regions_for_current_frame
 570     (auto_vec<const decl_region *> *out) const;
 571   static void append_ssa_names_cb (const region *base_reg,
 572                                    struct append_ssa_names_cb_data *data);
 573
 574   const svalue *get_store_value (const region *reg) const;
 575
 576   bool region_exists_p (const region *reg) const;
 577
 578   void loop_replay_fixup (const region_model *dst_state);
 579
 580  private:
 581   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt);
 582   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt);
 583
 584   void add_any_constraints_from_ssa_def_stmt (tree lhs,
 585                                               enum tree_code op,
 586                                               tree rhs,
 587                                               region_model_context *ctxt);
 588   void add_any_constraints_from_gassign (enum tree_code op,
 589                                          tree rhs,
 590                                          const gassign *assign,
 591                                          region_model_context *ctxt);
 592   void add_any_constraints_from_gcall (enum tree_code op,
 593                                        tree rhs,
 594                                        const gcall *call,
 595                                        region_model_context *ctxt);
 596
 597   void update_for_call_superedge (const call_superedge &call_edge,
 598                                   region_model_context *ctxt);
 599   void update_for_return_superedge (const return_superedge &return_edge,
 600                                     region_model_context *ctxt);
 601   void update_for_call_summary (const callgraph_superedge &cg_sedge,
 602                                 region_model_context *ctxt);
 603   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 604                                     const gcond *cond_stmt,
 605                                     region_model_context *ctxt,
 606                                     rejected_constraint **out);
 607   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 608                                       const gswitch *switch_stmt,
 609                                       region_model_context *ctxt,
 610                                       rejected_constraint **out);
 611   bool apply_constraints_for_exception (const gimple *last_stmt,
 612                                         region_model_context *ctxt,
 613                                         rejected_constraint **out);
 614
 615   int poison_any_pointers_to_descendents (const region *reg,
 616                                           enum poison_kind pkind);
 617
 618   void on_top_level_param (tree param, region_model_context *ctxt);
 619
 620   void record_dynamic_extents (const region *reg,
 621                                const svalue *size_in_bytes);
 622
 623   bool called_from_main_p () const;
 624   const svalue *get_initial_value_for_global (const region *reg) const;
 625
 626   void check_for_writable_region (const region* dest_reg,
 627                                   region_model_context *ctxt) const;
 628
 629   /* Storing this here to avoid passing it around everywhere.  */
 630   region_model_manager *const m_mgr;
 631
 632   store m_store;
 633
 634   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 635
 636   const frame_region *m_current_frame;
 637 };
 638
 639 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 640    uninitialized value).  This abstract base class encapsulates an interface
 641    for the region model to use when emitting such warnings.
 642
 643    Having this as an abstract base class allows us to support the various
 644    operations needed by program_state in the analyzer within region_model,
 645    whilst keeping them somewhat modularized.  */
 646
 647 class region_model_context
 648 {
 649  public:
 650   virtual void warn (pending_diagnostic *d) = 0;
 651
 652   /* Hook for clients to be notified when an SVAL that was reachable
 653      in a previous state is no longer live, so that clients can emit warnings
 654      about leaks.  */
 655   virtual void on_svalue_leak (const svalue *sval) = 0;
 656
 657   /* Hook for clients to be notified when the set of explicitly live
 658      svalues changes, so that they can purge state relating to dead
 659      svalues.  */
 660   virtual void on_liveness_change (const svalue_set &live_svalues,
 661                                    const region_model *model) = 0;
 662
 663   virtual logger *get_logger () = 0;
 664
 665   /* Hook for clients to be notified when the condition
 666      "LHS OP RHS" is added to the region model.
 667      This exists so that state machines can detect tests on edges,
 668      and use them to trigger sm-state transitions (e.g. transitions due
 669      to ptrs becoming known to be NULL or non-NULL, rather than just
 670      "unchecked") */
 671   virtual void on_condition (tree lhs, enum tree_code op, tree rhs) = 0;
 672
 673   /* Hooks for clients to be notified when an unknown change happens
 674      to SVAL (in response to a call to an unknown function).  */
 675   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 676
 677   /* Hooks for clients to be notified when a phi node is handled,
 678      where RHS is the pertinent argument.  */
 679   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 680
 681   /* Hooks for clients to be notified when the region model doesn't
 682      know how to handle the tree code of T at LOC.  */
 683   virtual void on_unexpected_tree_code (tree t,
 684                                         const dump_location_t &loc) = 0;
 685
 686   /* Hook for clients to be notified when a function_decl escapes.  */
 687   virtual void on_escaped_function (tree fndecl) = 0;
 688 };
 689
 690 /* A "do nothing" subclass of region_model_context.  */
 691
 692 class noop_region_model_context : public region_model_context
 693 {
 694 public:
 695   void warn (pending_diagnostic *) OVERRIDE {}
 696   void on_svalue_leak (const svalue *) OVERRIDE {}
 697   void on_liveness_change (const svalue_set &,
 698                            const region_model *) OVERRIDE {}
 699   logger *get_logger () OVERRIDE { return NULL; }
 700   void on_condition (tree lhs ATTRIBUTE_UNUSED,
 701                      enum tree_code op ATTRIBUTE_UNUSED,
 702                      tree rhs ATTRIBUTE_UNUSED) OVERRIDE
 703   {
 704   }
 705   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 706                           bool is_mutable ATTRIBUTE_UNUSED) OVERRIDE
 707   {
 708   }
 709   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 710                tree rhs ATTRIBUTE_UNUSED) OVERRIDE
 711   {
 712   }
 713   void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
 714
 715   void on_escaped_function (tree) OVERRIDE {}
 716 };
 717
 718 /* A subclass of region_model_context for determining if operations fail
 719    e.g. "can we generate a region for the lvalue of EXPR?".  */
 720
 721 class tentative_region_model_context : public noop_region_model_context
 722 {
 723 public:
 724   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 725
 726   void on_unexpected_tree_code (tree, const dump_location_t &)
 727     FINAL OVERRIDE
 728   {
 729     m_num_unexpected_codes++;
 730   }
 731
 732   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 733
 734 private:
 735   int m_num_unexpected_codes;
 736 };
 737
 738 /* A bundle of data for use when attempting to merge two region_model
 739    instances to make a third.  */
 740
 741 struct model_merger
 742 {
 743   model_merger (const region_model *model_a,
 744                 const region_model *model_b,
 745                 const program_point &point,
 746                 region_model *merged_model)
 747   : m_model_a (model_a), m_model_b (model_b),
 748     m_point (point),
 749     m_merged_model (merged_model)
 750   {
 751   }
 752
 753   void dump_to_pp (pretty_printer *pp, bool simple) const;
 754   void dump (FILE *fp, bool simple) const;
 755   void dump (bool simple) const;
 756
 757   region_model_manager *get_manager () const
 758   {
 759     return m_model_a->get_manager ();
 760   }
 761
 762   const region_model *m_model_a;
 763   const region_model *m_model_b;
 764   const program_point &m_point;
 765   region_model *m_merged_model;
 766 };
 767
 768 /* A record that can (optionally) be written out when
 769    region_model::add_constraint fails.  */
 770
 771 struct rejected_constraint
 772 {
 773   rejected_constraint (const region_model &model,
 774                      tree lhs, enum tree_code op, tree rhs)
 775   : m_model (model), m_lhs (lhs), m_op (op), m_rhs (rhs)
 776   {}
 777
 778   void dump_to_pp (pretty_printer *pp) const;
 779
 780   region_model m_model;
 781   tree m_lhs;
 782   enum tree_code m_op;
 783   tree m_rhs;
 784 };
 785
 786 /* A bundle of state.  */
 787
 788 class engine
 789 {
 790 public:
 791   region_model_manager *get_model_manager () { return &m_mgr; }
 792
 793   void log_stats (logger *logger) const;
 794
 795 private:
 796   region_model_manager m_mgr;
 797
 798 };
 799
 800 } // namespace ana
 801
 802 extern void debug (const region_model &rmodel);
 803
 804 namespace ana {
 805
 806 #if CHECKING_P
 807
 808 namespace selftest {
 809
 810 using namespace ::selftest;
 811
 812 /* An implementation of region_model_context for use in selftests, which
 813    stores any pending_diagnostic instances passed to it.  */
 814
 815 class test_region_model_context : public noop_region_model_context
 816 {
 817 public:
 818   void warn (pending_diagnostic *d) FINAL OVERRIDE
 819   {
 820     m_diagnostics.safe_push (d);
 821   }
 822
 823   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
 824
 825   void on_unexpected_tree_code (tree t, const dump_location_t &)
 826     FINAL OVERRIDE
 827   {
 828     internal_error ("unhandled tree code: %qs",
 829                     get_tree_code_name (TREE_CODE (t)));
 830   }
 831
 832 private:
 833   /* Implicitly delete any diagnostics in the dtor.  */
 834   auto_delete_vec<pending_diagnostic> m_diagnostics;
 835 };
 836
 837 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
 838    Verify that MODEL remains satisfiable.  */
 839
 840 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
 841   SELFTEST_BEGIN_STMT                                   \
 842     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
 843     ASSERT_TRUE (sat);                                  \
 844   SELFTEST_END_STMT
 845
 846 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
 847    Verify that the result is not satisfiable.  */
 848
 849 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
 850   SELFTEST_BEGIN_STMT                                   \
 851     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
 852     ASSERT_FALSE (sat);                         \
 853   SELFTEST_END_STMT
 854
 855 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
 856
 857 void assert_condition (const location &loc,
 858                        region_model &model,
 859                        const svalue *lhs, tree_code op, const svalue *rhs,
 860                        tristate expected);
 861
 862 void assert_condition (const location &loc,
 863                        region_model &model,
 864                        tree lhs, tree_code op, tree rhs,
 865                        tristate expected);
 866
 867 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
 868    as "true".  */
 869
 870 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
 871   SELFTEST_BEGIN_STMT                                                   \
 872   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
 873                     tristate (tristate::TS_TRUE));              \
 874   SELFTEST_END_STMT
 875
 876 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
 877    as "false".  */
 878
 879 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
 880   SELFTEST_BEGIN_STMT                                                   \
 881   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
 882                     tristate (tristate::TS_FALSE));             \
 883   SELFTEST_END_STMT
 884
 885 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
 886    as "unknown".  */
 887
 888 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
 889   SELFTEST_BEGIN_STMT                                                   \
 890   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
 891                     tristate (tristate::TS_UNKNOWN));           \
 892   SELFTEST_END_STMT
 893
 894 } /* end of namespace selftest.  */
 895
 896 #endif /* #if CHECKING_P */
 897
 898 } // namespace ana
 899
 900 #endif /* GCC_ANALYZER_REGION_MODEL_H */