gcc/analyzer/region-model.h

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