gcc/analyzer/exploded-graph.h

   1 /* Classes for managing a directed graph of <point, state> pairs.
   2    Copyright (C) 2019-2020 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_EXPLODED_GRAPH_H
  22 #define GCC_ANALYZER_EXPLODED_GRAPH_H
  23
  24 namespace ana {
  25
  26 /* Concrete implementation of region_model_context, wiring it up to the
  27    rest of the analysis engine.  */
  28
  29 class impl_region_model_context : public region_model_context
  30 {
  31  public:
  32   impl_region_model_context (exploded_graph &eg,
  33                              const exploded_node *enode_for_diag,
  34
  35                              /* TODO: should we be getting the ECs from the
  36                                 old state, rather than the new?  */
  37                              const program_state *old_state,
  38                              program_state *new_state,
  39                              state_change *change,
  40
  41                              const gimple *stmt,
  42                              stmt_finder *stmt_finder = NULL);
  43
  44   impl_region_model_context (program_state *state,
  45                              state_change *change,
  46                              const extrinsic_state &ext_state,
  47                              logger *logger = NULL);
  48
  49   void warn (pending_diagnostic *d) FINAL OVERRIDE;
  50
  51   void remap_svalue_ids (const svalue_id_map &map) FINAL OVERRIDE;
  52
  53   int on_svalue_purge (svalue_id first_unused_sid,
  54                        const svalue_id_map &map) FINAL OVERRIDE;
  55
  56   logger *get_logger () FINAL OVERRIDE
  57   {
  58     return m_logger.get_logger ();
  59   }
  60
  61   void on_state_leak (const state_machine &sm,
  62                       int sm_idx,
  63                       svalue_id sid,
  64                       svalue_id first_unused_sid,
  65                       const svalue_id_map &map,
  66                       state_machine::state_t state);
  67
  68   void on_inherited_svalue (svalue_id parent_sid,
  69                             svalue_id child_sid) FINAL OVERRIDE;
  70
  71   void on_cast (svalue_id src_sid,
  72                 svalue_id dst_sid) FINAL OVERRIDE;
  73
  74   void on_condition (tree lhs, enum tree_code op, tree rhs) FINAL OVERRIDE;
  75
  76   void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) FINAL OVERRIDE;
  77
  78   void on_phi (const gphi *phi, tree rhs) FINAL OVERRIDE;
  79
  80   void on_unexpected_tree_code (tree t,
  81                                 const dump_location_t &loc) FINAL OVERRIDE;
  82
  83   exploded_graph *m_eg;
  84   log_user m_logger;
  85   const exploded_node *m_enode_for_diag;
  86   const program_state *m_old_state;
  87   program_state *m_new_state;
  88   state_change *m_change;
  89   const gimple *m_stmt;
  90   stmt_finder *m_stmt_finder;
  91   const extrinsic_state &m_ext_state;
  92 };
  93
  94 /* A <program_point, program_state> pair, used internally by
  95    exploded_node as its immutable data, and as a key for identifying
  96    exploded_nodes we've already seen in the graph.  */
  97
  98 class point_and_state
  99 {
 100 public:
 101   point_and_state (const program_point &point,
 102                    const program_state &state)
 103   : m_point (point),
 104     m_state (state),
 105     m_hash (m_point.hash () ^ m_state.hash ())
 106   {
 107     /* We shouldn't be building point_and_states and thus exploded_nodes
 108        for states that aren't valid.  */
 109     gcc_assert (state.m_valid);
 110   }
 111
 112   hashval_t hash () const
 113   {
 114     return m_hash;
 115   }
 116   bool operator== (const point_and_state &other) const
 117   {
 118     return m_point == other.m_point && m_state == other.m_state;
 119   }
 120
 121   const program_point &get_point () const { return m_point; }
 122   const program_state &get_state () const { return m_state; }
 123
 124   void set_state (const program_state &state)
 125   {
 126     m_state = state;
 127     m_hash = m_point.hash () ^ m_state.hash ();
 128   }
 129
 130   void validate (const extrinsic_state &ext_state) const;
 131
 132 private:
 133   program_point m_point;
 134   program_state m_state;
 135   hashval_t m_hash;
 136 };
 137
 138 /* A traits class for exploded graphs and their nodes and edges.  */
 139
 140 struct eg_traits
 141 {
 142   typedef exploded_node node_t;
 143   typedef exploded_edge edge_t;
 144   typedef exploded_graph graph_t;
 145   struct dump_args_t
 146   {
 147     dump_args_t (const exploded_graph &eg) : m_eg (eg) {}
 148     const exploded_graph &m_eg;
 149   };
 150   typedef exploded_cluster cluster_t;
 151 };
 152
 153 /* An exploded_node is a unique, immutable <point, state> pair within the
 154    exploded_graph.
 155    Each exploded_node has a unique index within the graph
 156    (for ease of debugging).  */
 157
 158 class exploded_node : public dnode<eg_traits>
 159 {
 160  public:
 161   /* Has this enode had exploded_graph::process_node called on it?
 162      This allows us to distinguish enodes that were merged during
 163      worklist-handling, and thus never had process_node called on them
 164      (in favor of processing the merged node).  */
 165   enum status
 166   {
 167     /* Node is in the worklist.  */
 168     STATUS_WORKLIST,
 169
 170     /* Node has had exploded_graph::process_node called on it.  */
 171     STATUS_PROCESSED,
 172
 173     /* Node was left unprocessed due to merger; it won't have had
 174        exploded_graph::process_node called on it.  */
 175     STATUS_MERGER
 176   };
 177
 178   exploded_node (const point_and_state &ps, int index);
 179
 180   hashval_t hash () const { return m_ps.hash (); }
 181
 182   void dump_dot (graphviz_out *gv, const dump_args_t &args)
 183     const FINAL OVERRIDE;
 184   void dump_dot_id (pretty_printer *pp) const;
 185
 186   void dump_to_pp (pretty_printer *pp, const extrinsic_state &ext_state) const;
 187   void dump (FILE *fp, const extrinsic_state &ext_state) const;
 188   void dump (const extrinsic_state &ext_state) const;
 189
 190   /* The result of on_stmt.  */
 191   struct on_stmt_flags
 192   {
 193     on_stmt_flags (bool sm_changes)
 194     : m_sm_changes (sm_changes),
 195       m_terminate_path (false)
 196     {}
 197
 198     static on_stmt_flags terminate_path ()
 199     {
 200       return on_stmt_flags (true, true);
 201     }
 202
 203     static on_stmt_flags state_change (bool any_sm_changes)
 204     {
 205       return on_stmt_flags (any_sm_changes, false);
 206     }
 207
 208     /* Did any sm-changes occur handling the stmt.  */
 209     bool m_sm_changes : 1;
 210
 211     /* Should we stop analyzing this path (on_stmt may have already
 212        added nodes/edges, e.g. when handling longjmp).  */
 213     bool m_terminate_path : 1;
 214
 215   private:
 216     on_stmt_flags (bool sm_changes,
 217                    bool terminate_path)
 218     : m_sm_changes (sm_changes),
 219       m_terminate_path (terminate_path)
 220     {}
 221   };
 222
 223   on_stmt_flags on_stmt (exploded_graph &eg,
 224                          const supernode *snode,
 225                          const gimple *stmt,
 226                          program_state *state,
 227                          state_change *change) const;
 228   bool on_edge (exploded_graph &eg,
 229                 const superedge *succ,
 230                 program_point *next_point,
 231                 program_state *next_state,
 232                 state_change *change) const;
 233   void on_longjmp (exploded_graph &eg,
 234                    const gcall *call,
 235                    program_state *new_state,
 236                    region_model_context *ctxt) const;
 237
 238   void detect_leaks (exploded_graph &eg) const;
 239
 240   const program_point &get_point () const { return m_ps.get_point (); }
 241   const supernode *get_supernode () const
 242   {
 243     return get_point ().get_supernode ();
 244   }
 245   function *get_function () const
 246   {
 247     return get_point ().get_function ();
 248   }
 249   int get_stack_depth () const
 250   {
 251     return get_point ().get_stack_depth ();
 252   }
 253   const gimple *get_stmt () const { return get_point ().get_stmt (); }
 254
 255   const program_state &get_state () const { return m_ps.get_state (); }
 256
 257   const point_and_state *get_ps_key () const { return &m_ps; }
 258   const program_point *get_point_key () const { return &m_ps.get_point (); }
 259
 260   void dump_succs_and_preds (FILE *outf) const;
 261
 262   enum status get_status () const { return m_status; }
 263   void set_status (enum status status)
 264   {
 265     gcc_assert (m_status == STATUS_WORKLIST);
 266     m_status = status;
 267   }
 268
 269 private:
 270   DISABLE_COPY_AND_ASSIGN (exploded_node);
 271
 272   const char * get_dot_fillcolor () const;
 273
 274   /* The <program_point, program_state> pair.  This is const, as it
 275      is immutable once the exploded_node has been created.  */
 276   const point_and_state m_ps;
 277
 278   enum status m_status;
 279
 280 public:
 281   /* The index of this exploded_node.  */
 282   const int m_index;
 283 };
 284
 285 /* An edge within the exploded graph.
 286    Some exploded_edges have an underlying superedge; others don't.  */
 287
 288 class exploded_edge : public dedge<eg_traits>
 289 {
 290  public:
 291   /* Abstract base class for associating custom data with an
 292      exploded_edge, for handling non-standard edges such as
 293      rewinding from a longjmp, signal handlers, etc.  */
 294   class custom_info_t
 295   {
 296   public:
 297     virtual ~custom_info_t () {}
 298
 299     /* Hook for making .dot label more readable .  */
 300     virtual void print (pretty_printer *pp) = 0;
 301
 302     /* Hook for updating MODEL within exploded_path::feasible_p.  */
 303     virtual void update_model (region_model *model,
 304                                const exploded_edge &eedge) = 0;
 305
 306     virtual void add_events_to_path (checker_path *emission_path,
 307                                      const exploded_edge &eedge) = 0;
 308   };
 309
 310   exploded_edge (exploded_node *src, exploded_node *dest,
 311                  const extrinsic_state &ext_state,
 312                  const superedge *sedge,
 313                  const state_change &change,
 314                  custom_info_t *custom_info);
 315   ~exploded_edge ();
 316   void dump_dot (graphviz_out *gv, const dump_args_t &args)
 317     const FINAL OVERRIDE;
 318
 319   //private:
 320   const superedge *const m_sedge;
 321
 322   const state_change m_change;
 323
 324   /* NULL for most edges; will be non-NULL for special cases
 325      such as an unwind from a longjmp to a setjmp, or when
 326      a signal is delivered to a signal-handler.
 327
 328      Owned by this class.  */
 329   custom_info_t *m_custom_info;
 330
 331 private:
 332   DISABLE_COPY_AND_ASSIGN (exploded_edge);
 333 };
 334
 335 /* Extra data for an exploded_edge that represents a rewind from a
 336    longjmp to a setjmp (or from a siglongjmp to a sigsetjmp).  */
 337
 338 class rewind_info_t : public exploded_edge::custom_info_t
 339 {
 340 public:
 341   rewind_info_t (const setjmp_record &setjmp_record,
 342                  const gcall *longjmp_call)
 343   : m_setjmp_record (setjmp_record),
 344     m_longjmp_call (longjmp_call)
 345   {}
 346
 347   void print (pretty_printer *pp) FINAL OVERRIDE
 348   {
 349     pp_string (pp, "rewind");
 350   }
 351
 352   void update_model (region_model *model,
 353                      const exploded_edge &eedge) FINAL OVERRIDE;
 354
 355   void add_events_to_path (checker_path *emission_path,
 356                            const exploded_edge &eedge) FINAL OVERRIDE;
 357
 358   const program_point &get_setjmp_point () const
 359   {
 360     const program_point &origin_point = get_enode_origin ()->get_point ();
 361
 362     /* "origin_point" ought to be before the call to "setjmp".  */
 363     gcc_assert (origin_point.get_kind () == PK_BEFORE_STMT);
 364
 365     /* TODO: assert that it's the final stmt in its supernode.  */
 366
 367     return origin_point;
 368   }
 369
 370   const gcall *get_setjmp_call () const
 371   {
 372     return m_setjmp_record.m_setjmp_call;
 373   }
 374
 375   const gcall *get_longjmp_call () const
 376   {
 377     return m_longjmp_call;
 378   }
 379
 380   const exploded_node *get_enode_origin () const
 381   {
 382     return m_setjmp_record.m_enode;
 383   }
 384
 385 private:
 386   setjmp_record m_setjmp_record;
 387   const gcall *m_longjmp_call;
 388 };
 389
 390 /* Statistics about aspects of an exploded_graph.  */
 391
 392 struct stats
 393 {
 394   stats (int num_supernodes);
 395   void log (logger *logger) const;
 396   void dump (FILE *out) const;
 397
 398   int get_total_enodes () const;
 399
 400   int m_num_nodes[NUM_POINT_KINDS];
 401   int m_node_reuse_count;
 402   int m_node_reuse_after_merge_count;
 403   int m_num_supernodes;
 404 };
 405
 406 /* Traits class for ensuring uniqueness of point_and_state data within
 407    an exploded_graph.  */
 408
 409 struct eg_hash_map_traits
 410 {
 411   typedef const point_and_state *key_type;
 412   typedef exploded_node *value_type;
 413   typedef exploded_node *compare_type;
 414
 415   static inline hashval_t hash (const key_type &k)
 416   {
 417     gcc_assert (k != NULL);
 418     gcc_assert (k != reinterpret_cast<key_type> (1));
 419     return k->hash ();
 420   }
 421   static inline bool equal_keys (const key_type &k1, const key_type &k2)
 422   {
 423     gcc_assert (k1 != NULL);
 424     gcc_assert (k2 != NULL);
 425     gcc_assert (k1 != reinterpret_cast<key_type> (1));
 426     gcc_assert (k2 != reinterpret_cast<key_type> (1));
 427     if (k1 && k2)
 428       return *k1 == *k2;
 429     else
 430       /* Otherwise they must both be non-NULL.  */
 431       return k1 == k2;
 432   }
 433   template <typename T>
 434   static inline void remove (T &)
 435   {
 436     /* empty; the nodes are handled elsewhere.  */
 437   }
 438   template <typename T>
 439   static inline void mark_deleted (T &entry)
 440   {
 441     entry.m_key = reinterpret_cast<key_type> (1);
 442   }
 443   template <typename T>
 444   static inline void mark_empty (T &entry)
 445   {
 446     entry.m_key = NULL;
 447   }
 448   template <typename T>
 449   static inline bool is_deleted (const T &entry)
 450   {
 451     return entry.m_key == reinterpret_cast<key_type> (1);
 452   }
 453   template <typename T>
 454   static inline bool is_empty (const T &entry)
 455   {
 456     return entry.m_key == NULL;
 457   }
 458   static const bool empty_zero_p = false;
 459 };
 460
 461 /* Per-program_point data for an exploded_graph.  */
 462
 463 struct per_program_point_data
 464 {
 465   per_program_point_data (const program_point &key)
 466   : m_key (key), m_excess_enodes (0)
 467   {}
 468
 469   const program_point m_key;
 470   auto_vec<exploded_node *> m_enodes;
 471   /* The number of attempts to create an enode for this point
 472      after exceeding --param=analyzer-max-enodes-per-program-point.  */
 473   int m_excess_enodes;
 474 };
 475
 476 /* Traits class for storing per-program_point data within
 477    an exploded_graph.  */
 478
 479 struct eg_point_hash_map_traits
 480 {
 481   typedef const program_point *key_type;
 482   typedef per_program_point_data *value_type;
 483   typedef per_program_point_data *compare_type;
 484
 485   static inline hashval_t hash (const key_type &k)
 486   {
 487     gcc_assert (k != NULL);
 488     gcc_assert (k != reinterpret_cast<key_type> (1));
 489     return k->hash ();
 490   }
 491   static inline bool equal_keys (const key_type &k1, const key_type &k2)
 492   {
 493     gcc_assert (k1 != NULL);
 494     gcc_assert (k2 != NULL);
 495     gcc_assert (k1 != reinterpret_cast<key_type> (1));
 496     gcc_assert (k2 != reinterpret_cast<key_type> (1));
 497     if (k1 && k2)
 498       return *k1 == *k2;
 499     else
 500       /* Otherwise they must both be non-NULL.  */
 501       return k1 == k2;
 502   }
 503   template <typename T>
 504   static inline void remove (T &)
 505   {
 506     /* empty; the nodes are handled elsewhere.  */
 507   }
 508   template <typename T>
 509   static inline void mark_deleted (T &entry)
 510   {
 511     entry.m_key = reinterpret_cast<key_type> (1);
 512   }
 513   template <typename T>
 514   static inline void mark_empty (T &entry)
 515   {
 516     entry.m_key = NULL;
 517   }
 518   template <typename T>
 519   static inline bool is_deleted (const T &entry)
 520   {
 521     return entry.m_key == reinterpret_cast<key_type> (1);
 522   }
 523   template <typename T>
 524   static inline bool is_empty (const T &entry)
 525   {
 526     return entry.m_key == NULL;
 527   }
 528   static const bool empty_zero_p = false;
 529 };
 530
 531 /* Data about a particular call_string within an exploded_graph.  */
 532
 533 struct per_call_string_data
 534 {
 535   per_call_string_data (const call_string &key, int num_supernodes)
 536   : m_key (key), m_stats (num_supernodes)
 537   {}
 538
 539   const call_string m_key;
 540   stats m_stats;
 541 };
 542
 543 /* Traits class for storing per-call_string data within
 544    an exploded_graph.  */
 545
 546 struct eg_call_string_hash_map_traits
 547 {
 548   typedef const call_string *key_type;
 549   typedef per_call_string_data *value_type;
 550   typedef per_call_string_data *compare_type;
 551
 552   static inline hashval_t hash (const key_type &k)
 553   {
 554     gcc_assert (k != NULL);
 555     gcc_assert (k != reinterpret_cast<key_type> (1));
 556     return k->hash ();
 557   }
 558   static inline bool equal_keys (const key_type &k1, const key_type &k2)
 559   {
 560     gcc_assert (k1 != NULL);
 561     gcc_assert (k2 != NULL);
 562     gcc_assert (k1 != reinterpret_cast<key_type> (1));
 563     gcc_assert (k2 != reinterpret_cast<key_type> (1));
 564     if (k1 && k2)
 565       return *k1 == *k2;
 566     else
 567       /* Otherwise they must both be non-NULL.  */
 568       return k1 == k2;
 569   }
 570   template <typename T>
 571   static inline void remove (T &)
 572   {
 573     /* empty; the nodes are handled elsewhere.  */
 574   }
 575   template <typename T>
 576   static inline void mark_deleted (T &entry)
 577   {
 578     entry.m_key = reinterpret_cast<key_type> (1);
 579   }
 580   template <typename T>
 581   static inline void mark_empty (T &entry)
 582   {
 583     entry.m_key = NULL;
 584   }
 585   template <typename T>
 586   static inline bool is_deleted (const T &entry)
 587   {
 588     return entry.m_key == reinterpret_cast<key_type> (1);
 589   }
 590   template <typename T>
 591   static inline bool is_empty (const T &entry)
 592   {
 593     return entry.m_key == NULL;
 594   }
 595   static const bool empty_zero_p = false;
 596 };
 597
 598 /* Data about a particular function within an exploded_graph.  */
 599
 600 struct per_function_data
 601 {
 602   per_function_data () {}
 603
 604   void add_call_summary (exploded_node *node)
 605   {
 606     m_summaries.safe_push (node);
 607   }
 608
 609   auto_vec<exploded_node *> m_summaries;
 610 };
 611
 612
 613 /* The strongly connected components of a supergraph.
 614    In particular, this allows us to compute a partial ordering
 615    of supernodes.  */
 616
 617 class strongly_connected_components
 618 {
 619 public:
 620   strongly_connected_components (const supergraph &sg, logger *logger);
 621
 622   int get_scc_id (int node_index) const
 623   {
 624     return m_per_node[node_index].m_lowlink;
 625   }
 626
 627   void dump () const;
 628
 629 private:
 630   struct per_node_data
 631   {
 632     per_node_data ()
 633       : m_index (-1), m_lowlink (-1), m_on_stack (false)
 634     {}
 635
 636     int m_index;
 637     int m_lowlink;
 638     bool m_on_stack;
 639   };
 640
 641   void strong_connect (unsigned index);
 642
 643   const supergraph &m_sg;
 644   auto_vec<unsigned> m_stack;
 645   auto_vec<per_node_data> m_per_node;
 646 };
 647
 648 /* The worklist of exploded_node instances that have been added to
 649    an exploded_graph, but that haven't yet been processed to find
 650    their successors (or warnings).
 651
 652    The enodes are stored in a priority queue, ordered by a topological
 653    sort of the SCCs in the supergraph, so that enodes for the same
 654    program_point should appear at the front of the queue together.
 655    This allows for state-merging at CFG join-points, so that
 656    sufficiently-similar enodes can be merged into one.  */
 657
 658 class worklist
 659 {
 660 public:
 661   worklist (const exploded_graph &eg, const analysis_plan &plan);
 662   unsigned length () const;
 663   exploded_node *take_next ();
 664   exploded_node *peek_next ();
 665   void add_node (exploded_node *enode);
 666
 667 private:
 668   class key_t
 669   {
 670   public:
 671     key_t (const worklist &w, exploded_node *enode)
 672     : m_worklist (w), m_enode (enode)
 673     {}
 674
 675     bool operator< (const key_t &other) const
 676     {
 677       return cmp (*this, other) < 0;
 678     }
 679
 680     bool operator== (const key_t &other) const
 681     {
 682       return cmp (*this, other) == 0;
 683     }
 684
 685     bool operator> (const key_t &other) const
 686     {
 687       return !(*this == other || *this < other);
 688     }
 689
 690   private:
 691     static int cmp (const key_t &ka, const key_t &kb);
 692
 693     int get_scc_id (const exploded_node *enode) const
 694     {
 695       const supernode *snode = enode->get_supernode ();
 696       if (snode == NULL)
 697         return 0;
 698       return m_worklist.m_scc.get_scc_id (snode->m_index);
 699     }
 700
 701     const worklist &m_worklist;
 702     exploded_node *m_enode;
 703   };
 704
 705   /* The order is important here: m_scc needs to stick around
 706      until after m_queue has finished being cleaned up (the dtor
 707      calls the ordering fns).  */
 708   strongly_connected_components m_scc;
 709   const analysis_plan &m_plan;
 710
 711   /* Priority queue, backed by a fibonacci_heap.  */
 712   typedef fibonacci_heap<key_t, exploded_node> queue_t;
 713   queue_t m_queue;
 714 };
 715
 716 /* An exploded_graph is a directed graph of unique <point, state> pairs.
 717    It also has a worklist of nodes that are waiting for their successors
 718    to be added to the graph.  */
 719
 720 class exploded_graph : public digraph<eg_traits>
 721 {
 722 public:
 723   typedef hash_map <const call_string *, per_call_string_data *,
 724                     eg_call_string_hash_map_traits> call_string_data_map_t;
 725
 726   exploded_graph (const supergraph &sg, logger *logger,
 727                   const extrinsic_state &ext_state,
 728                   const state_purge_map *purge_map,
 729                   const analysis_plan &plan,
 730                   int verbosity);
 731   ~exploded_graph ();
 732
 733   logger *get_logger () const { return m_logger.get_logger (); }
 734
 735   const supergraph &get_supergraph () const { return m_sg; }
 736   const extrinsic_state &get_ext_state () const { return m_ext_state; }
 737   const state_purge_map *get_purge_map () const { return m_purge_map; }
 738   const analysis_plan &get_analysis_plan () const { return m_plan; }
 739
 740   exploded_node *get_origin () const { return m_origin; }
 741
 742   exploded_node *add_function_entry (function *fun);
 743
 744   void build_initial_worklist ();
 745   void process_worklist ();
 746   void process_node (exploded_node *node);
 747
 748   exploded_node *get_or_create_node (const program_point &point,
 749                                      const program_state &state,
 750                                      state_change *change);
 751   exploded_edge *add_edge (exploded_node *src, exploded_node *dest,
 752                            const superedge *sedge,
 753                            const state_change &change,
 754                            exploded_edge::custom_info_t *custom = NULL);
 755
 756   per_program_point_data *
 757   get_or_create_per_program_point_data (const program_point &);
 758
 759   per_call_string_data *
 760   get_or_create_per_call_string_data (const call_string &);
 761
 762   per_function_data *
 763   get_or_create_per_function_data (function *);
 764   per_function_data *get_per_function_data (function *) const;
 765
 766   void save_diagnostic (const state_machine &sm,
 767                         const exploded_node *enode,
 768                         const supernode *node, const gimple *stmt,
 769                         stmt_finder *finder,
 770                         tree var, state_machine::state_t state,
 771                         pending_diagnostic *d);
 772
 773   diagnostic_manager &get_diagnostic_manager ()
 774   {
 775     return m_diagnostic_manager;
 776   }
 777   const diagnostic_manager &get_diagnostic_manager () const
 778   {
 779     return m_diagnostic_manager;
 780   }
 781
 782   stats *get_global_stats () { return &m_global_stats; }
 783   stats *get_or_create_function_stats (function *fn);
 784   void log_stats () const;
 785   void dump_stats (FILE *) const;
 786   void dump_states_for_supernode (FILE *, const supernode *snode) const;
 787   void dump_exploded_nodes () const;
 788
 789   const call_string_data_map_t *get_per_call_string_data () const
 790   { return &m_per_call_string_data; }
 791
 792 private:
 793   void print_bar_charts (pretty_printer *pp) const;
 794
 795   DISABLE_COPY_AND_ASSIGN (exploded_graph);
 796
 797   const supergraph &m_sg;
 798
 799   log_user m_logger;
 800
 801   /* Map from point/state to exploded node.
 802      To avoid duplication we store point_and_state
 803      *pointers* as keys, rather than point_and_state, using the
 804      instance from within the exploded_node, with a custom hasher.  */
 805   typedef hash_map <const point_and_state *, exploded_node *,
 806                     eg_hash_map_traits> map_t;
 807   map_t m_point_and_state_to_node;
 808
 809   /* Map from program_point to per-program_point data.  */
 810   typedef hash_map <const program_point *, per_program_point_data *,
 811                     eg_point_hash_map_traits> point_map_t;
 812   point_map_t m_per_point_data;
 813
 814   worklist m_worklist;
 815
 816   exploded_node *m_origin;
 817
 818   const extrinsic_state &m_ext_state;
 819
 820   const state_purge_map *const m_purge_map;
 821
 822   const analysis_plan &m_plan;
 823
 824   typedef hash_map<function *, per_function_data *> per_function_data_t;
 825   per_function_data_t m_per_function_data;
 826
 827   diagnostic_manager m_diagnostic_manager;
 828
 829   /* Stats.  */
 830   stats m_global_stats;
 831   typedef ordered_hash_map<function *, stats *> function_stat_map_t;
 832   function_stat_map_t m_per_function_stats;
 833   stats m_functionless_stats;
 834
 835   call_string_data_map_t m_per_call_string_data;
 836
 837   auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode;
 838 };
 839
 840 /* A path within an exploded_graph: a sequence of edges.  */
 841
 842 class exploded_path
 843 {
 844 public:
 845   exploded_path () : m_edges () {}
 846   exploded_path (const exploded_path &other);
 847   exploded_path & operator= (const exploded_path &other);
 848
 849   unsigned length () const { return m_edges.length (); }
 850
 851   bool find_stmt_backwards (const gimple *search_stmt,
 852                             int *out_idx) const;
 853
 854   exploded_node *get_final_enode () const;
 855
 856   void dump_to_pp (pretty_printer *pp) const;
 857   void dump (FILE *fp) const;
 858   void dump () const;
 859
 860   bool feasible_p (logger *logger) const;
 861
 862   auto_vec<const exploded_edge *> m_edges;
 863 };
 864
 865 /* Finding the shortest exploded_path within an exploded_graph.  */
 866
 867 typedef shortest_paths<eg_traits, exploded_path> shortest_exploded_paths;
 868
 869 /* Abstract base class for use when passing NULL as the stmt for
 870    a possible warning, allowing the choice of stmt to be deferred
 871    until after we have an emission path (and know we're emitting a
 872    warning).  */
 873
 874 class stmt_finder
 875 {
 876 public:
 877   virtual ~stmt_finder () {}
 878   virtual stmt_finder *clone () const = 0;
 879   virtual const gimple *find_stmt (const exploded_path &epath) = 0;
 880 };
 881
 882 // TODO: split the above up?
 883
 884 } // namespace ana
 885
 886 #endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */