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