LCOV - code coverage report
Current view: top level - gcc/analyzer - exploded-graph.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.2 % 159 153
Test Date: 2026-11-14 16:39:50 Functions: 84.2 % 19 16
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Classes for managing a directed graph of <point, state> pairs.
       2              :    Copyright (C) 2019-2026 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              : #include "alloc-pool.h"
      25              : #include "fibonacci_heap.h"
      26              : #include "supergraph.h"
      27              : #include "sbitmap.h"
      28              : #include "shortest-paths.h"
      29              : #include "analyzer/sm.h"
      30              : #include "analyzer/program-state.h"
      31              : #include "analyzer/diagnostic-manager.h"
      32              : #include "analyzer/region-model.h"
      33              : 
      34              : namespace ana {
      35              : 
      36              : /* Concrete implementation of region_model_context, wiring it up to the
      37              :    rest of the analysis engine.  */
      38              : 
      39      1237479 : class impl_region_model_context : public region_model_context
      40              : {
      41              :  public:
      42              :   impl_region_model_context (exploded_graph &eg,
      43              :                              exploded_node *enode_for_diag,
      44              : 
      45              :                              /* TODO: should we be getting the ECs from the
      46              :                                 old state, rather than the new?  */
      47              :                              const program_state *old_state,
      48              :                              program_state *new_state,
      49              :                              uncertainty_t *uncertainty,
      50              :                              path_context *path_ctxt,
      51              :                              const gimple *stmt = nullptr,
      52              :                              bool *out_could_have_done_work = nullptr);
      53              : 
      54              :   impl_region_model_context (program_state *state,
      55              :                              const extrinsic_state &ext_state,
      56              :                              uncertainty_t *uncertainty,
      57              :                              logger *logger = nullptr);
      58              : 
      59              :   bool
      60              :   warn_at (std::unique_ptr<pending_diagnostic> d,
      61              :            pending_location &&ploc) final override;
      62              :   void add_note (std::unique_ptr<pending_note> pn) final override;
      63              :   void add_event (std::unique_ptr<checker_event> event) final override;
      64              :   void on_svalue_leak (const svalue *) override;
      65              :   void on_liveness_change (symbolic::liveness_context &) final override;
      66      1262658 :   logger *get_logger () final override
      67              :   {
      68        12368 :     return m_logger.get_logger ();
      69              :   }
      70              : 
      71              :   void on_state_leak (const state_machine &sm,
      72              :                       const svalue *sval,
      73              :                       state_machine::state_t state);
      74              : 
      75              :   void on_condition (const svalue *lhs,
      76              :                      enum tree_code op,
      77              :                      const svalue *rhs) final override;
      78              : 
      79              :   void on_bounded_ranges (const svalue &sval,
      80              :                           const bounded_ranges &ranges) final override;
      81              : 
      82              :   void on_pop_frame (const frame_region *frame_reg) final override;
      83              : 
      84              :   void on_unknown_change (const symbolic::value_node &val,
      85              :                           bool is_mutable) final override;
      86              : 
      87              :   void on_phi (const gphi *phi, tree rhs) final override;
      88              : 
      89              :   void on_unexpected_tree_code (tree t,
      90              :                                 const dump_location_t &loc) final override;
      91              : 
      92              :   void on_escaped_function (tree fndecl) final override;
      93              : 
      94              :   uncertainty_t *get_uncertainty () final override;
      95              : 
      96              :   void purge_state_involving (const symbolic::node &node) final override;
      97              : 
      98              :   void bifurcate (std::unique_ptr<custom_edge_info> info) final override;
      99              :   void terminate_path () final override;
     100       915763 :   const extrinsic_state *get_ext_state () const final override
     101              :   {
     102       915763 :     return &m_ext_state;
     103              :   }
     104              :   bool
     105              :   get_state_map_by_name (const char *name,
     106              :                          sm_state_map **out_smap,
     107              :                          const state_machine **out_sm,
     108              :                          unsigned *out_sm_idx,
     109              :                          std::unique_ptr<sm_context> *out_sm_context) override;
     110              : 
     111       331486 :   const gimple *get_stmt () const override { return m_stmt; }
     112            0 :   const exploded_graph *get_eg () const override { return m_eg; }
     113              : 
     114          291 :   const program_state *get_state () const override { return m_new_state; }
     115              : 
     116              :   void maybe_did_work () override;
     117        57951 :   bool checking_for_infinite_loop_p () const override { return false; }
     118            0 :   void on_unusable_in_infinite_loop () override {}
     119              : 
     120              :   pending_location
     121              :   get_pending_location_for_diag () const override;
     122              : 
     123              :   exploded_graph *m_eg;
     124              :   log_user m_logger;
     125              :   exploded_node *m_enode_for_diag;
     126              :   const program_state *m_old_state;
     127              :   program_state *m_new_state;
     128              :   const gimple *m_stmt;
     129              :   const extrinsic_state &m_ext_state;
     130              :   uncertainty_t *m_uncertainty;
     131              :   path_context *m_path_ctxt;
     132              :   bool *m_out_could_have_done_work;
     133              : };
     134              : 
     135              : /* A <program_point, program_state> pair, used internally by
     136              :    exploded_node as its immutable data, and as a key for identifying
     137              :    exploded_nodes we've already seen in the graph.  */
     138              : 
     139       376171 : class point_and_state
     140              : {
     141              : public:
     142       376171 :   point_and_state (const program_point &point,
     143              :                    const program_state &state)
     144       376171 :   : m_point (point),
     145       376171 :     m_state (state),
     146       376171 :     m_hash (m_point.hash () ^ m_state.hash ())
     147              :   {
     148              :     /* We shouldn't be building point_and_states and thus exploded_nodes
     149              :        for states that aren't valid.  */
     150       376171 :     gcc_assert (state.m_valid);
     151       376171 :   }
     152              : 
     153            0 :   point_and_state (const point_and_state &other) = default;
     154              : 
     155       371189 :   point_and_state (point_and_state &&other)
     156       371189 :   : m_point (other.m_point),
     157       371189 :     m_state (std::move (other.m_state)),
     158       371189 :     m_hash (other.m_hash)
     159              :   {
     160              :   }
     161              : 
     162      5300399 :   hashval_t hash () const
     163              :   {
     164      5300399 :     return m_hash;
     165              :   }
     166      5004254 :   bool operator== (const point_and_state &other) const
     167              :   {
     168      5034894 :     return m_point == other.m_point && m_state == other.m_state;
     169              :   }
     170              : 
     171       208203 :   const program_point &get_point () const { return m_point; }
     172      1602832 :   const program_state &get_state () const { return m_state; }
     173              : 
     174              :   void set_state (const program_state &state)
     175              :   {
     176              :     m_state = state;
     177              :     m_hash = m_point.hash () ^ m_state.hash ();
     178              :   }
     179              : 
     180        25306 :   void set_state (program_state &&state)
     181              :   {
     182        25306 :     m_state = std::move (state);
     183        25306 :     m_hash = m_point.hash () ^ m_state.hash ();
     184        25306 :   }
     185              : 
     186              :   void validate (const extrinsic_state &ext_state) const;
     187              : 
     188              : private:
     189              :   program_point m_point;
     190              :   program_state m_state;
     191              :   hashval_t m_hash;
     192              : };
     193              : 
     194              : /* A traits class for exploded graphs and their nodes and edges.  */
     195              : 
     196              : struct eg_traits
     197              : {
     198              :   typedef exploded_node node_t;
     199              :   typedef exploded_edge edge_t;
     200              :   typedef exploded_graph graph_t;
     201              :   struct dump_args_t
     202              :   {
     203           12 :     dump_args_t (const exploded_graph &eg) : m_eg (eg) {}
     204              : 
     205              :     bool show_enode_details_p (const exploded_node &enode) const;
     206              : 
     207              :     virtual void
     208          441 :     dump_extra_info (const exploded_node *, pretty_printer *) const {}
     209              : 
     210              :     const exploded_graph &m_eg;
     211              :   };
     212              :   typedef exploded_cluster cluster_t;
     213              : };
     214              : 
     215              : /* An exploded_node is a unique, immutable <point, state> pair within the
     216              :    exploded_graph.
     217              :    Each exploded_node has a unique index within the graph
     218              :    (for ease of debugging).  */
     219              : 
     220              : class exploded_node : public dnode<eg_traits>
     221              : {
     222              :  public:
     223              :   /* Has this enode had exploded_graph::process_node called on it?
     224              :      This allows us to distinguish enodes that were merged during
     225              :      worklist-handling, and thus never had process_node called on them
     226              :      (in favor of processing the merged node).  */
     227              :   enum class status
     228              :   {
     229              :     /* Node is in the worklist.  */
     230              :     worklist,
     231              : 
     232              :     /* Node has had exploded_graph::process_node called on it.  */
     233              :     processed,
     234              : 
     235              :     /* Node was excluded from worklist on creation.
     236              :        e.g. for handling exception-unwinding.  */
     237              :     special,
     238              : 
     239              :     /* Node was left unprocessed due to merger; it won't have had
     240              :        exploded_graph::process_node called on it.  */
     241              :     merger,
     242              : 
     243              :     /* Node was processed by maybe_process_run_of_enodes.  */
     244              :     bulk_merged
     245              :   };
     246              :   static const char * status_to_str (enum status s);
     247              : 
     248              :   exploded_node (const point_and_state &ps, int index);
     249              :   exploded_node (point_and_state &&ps, int index);
     250              : 
     251              :   hashval_t hash () const { return m_ps.hash (); }
     252              : 
     253              :   const char * get_dot_fillcolor () const;
     254              :   void dump_dot (graphviz_out *gv, const dump_args_t &args)
     255              :     const final override;
     256              :   void dump_dot_id (pretty_printer *pp) const;
     257              : 
     258              :   std::unique_ptr<text_art::tree_widget>
     259              :   make_dump_widget (symbolic::node_dump_state &nds) const;
     260              : 
     261              :   void dump () const;
     262              :   void dump_to_pp (pretty_printer *) const;
     263              :   void dump_to_logger (logger &log) const;
     264              : 
     265              :   void dump_processed_stmts (pretty_printer *pp) const;
     266              :   void dump_saved_diagnostics (pretty_printer *pp) const;
     267              : 
     268              :   std::unique_ptr<json::object> to_json (const extrinsic_state &ext_state) const;
     269              : 
     270              :   void on_longjmp (exploded_graph &eg,
     271              :                    const gcall &call,
     272              :                    program_state *new_state,
     273              :                    region_model_context *ctxt);
     274              :   void on_throw (exploded_graph &eg,
     275              :                  const gcall &call,
     276              :                  const program_point &after_throw_point,
     277              :                  program_state *new_state,
     278              :                  bool is_rethrow,
     279              :                  region_model_context *ctxt);
     280              : 
     281              :   void detect_leaks (exploded_graph &eg);
     282              : 
     283      2861882 :   const program_point &get_point () const { return m_ps.get_point (); }
     284      3404662 :   const supernode *get_supernode () const
     285              :   {
     286      1155288 :     return get_point ().get_supernode ();
     287              :   }
     288       402918 :   location_t get_location () const
     289              :   {
     290       797834 :     return get_point ().get_location ();
     291              :   }
     292       411281 :   function *get_function () const
     293              :   {
     294       813705 :     return get_point ().get_function ();
     295              :   }
     296        36053 :   int get_stack_depth () const
     297              :   {
     298        83294 :     return get_point ().get_stack_depth ();
     299              :   }
     300              : 
     301       762886 :   const program_state &get_state () const { return m_ps.get_state (); }
     302              : 
     303       371189 :   const point_and_state *get_ps_key () const { return &m_ps; }
     304              :   const program_point *get_point_key () const { return &m_ps.get_point (); }
     305              : 
     306              :   void dump_succs_and_preds (FILE *outf) const;
     307              : 
     308      1197760 :   enum status get_status () const { return m_status; }
     309       370196 :   void set_status (enum status s)
     310              :   {
     311       370196 :     gcc_assert (m_status == status::worklist);
     312       370196 :     m_status = s;
     313       370196 :   }
     314              : 
     315         6671 :   void add_diagnostic (const saved_diagnostic *sd)
     316              :   {
     317         6671 :     m_saved_diagnostics.safe_push (sd);
     318              :   }
     319          445 :   unsigned get_num_diagnostics () const
     320              :   {
     321          445 :     return m_saved_diagnostics.length ();
     322              :   }
     323            4 :   const saved_diagnostic *get_saved_diagnostic (unsigned idx) const
     324              :   {
     325            4 :     return m_saved_diagnostics[idx];
     326              :   }
     327              : 
     328              : private:
     329              :   DISABLE_COPY_AND_ASSIGN (exploded_node);
     330              : 
     331              :   /* The <program_point, program_state> pair.  This is const, as it
     332              :      is immutable once the exploded_node has been created.  */
     333              :   const point_and_state m_ps;
     334              : 
     335              :   enum status m_status;
     336              : 
     337              :   /* The saved_diagnostics at this enode, borrowed from the
     338              :      diagnostic_manager.  */
     339              :   auto_vec <const saved_diagnostic *> m_saved_diagnostics;
     340              : 
     341              : public:
     342              :   /* The index of this exploded_node.  */
     343              :   const int m_index;
     344              : };
     345              : 
     346              : /* An edge within the exploded graph.
     347              :    Some exploded_edges have an underlying superedge; others don't.  */
     348              : 
     349              : class exploded_edge : public dedge<eg_traits>
     350              : {
     351              :  public:
     352              :   exploded_edge (exploded_node *src, exploded_node *dest,
     353              :                  const superedge *sedge, bool could_do_work,
     354              :                  std::unique_ptr<custom_edge_info> custom_info);
     355              :   void dump_dot (graphviz_out *gv, const dump_args_t &args)
     356              :     const final override;
     357              :   void dump_dot_label (pretty_printer *pp) const;
     358              : 
     359              :   std::unique_ptr<json::object> to_json () const;
     360              : 
     361              :   //private:
     362              :   const superedge *const m_sedge;
     363              : 
     364              :   /* nullptr for most edges; will be non-NULL for special cases
     365              :      such as an unwind from a longjmp to a setjmp, or when
     366              :      a signal is delivered to a signal-handler.  */
     367              :   std::unique_ptr<custom_edge_info> m_custom_info;
     368              : 
     369        20537 :   bool could_do_work_p () const { return m_could_do_work_p; }
     370              : 
     371              :   const gimple *maybe_get_stmt () const;
     372              :   const operation *maybe_get_op () const;
     373              : 
     374              : private:
     375              :   DISABLE_COPY_AND_ASSIGN (exploded_edge);
     376              : 
     377              :   /* For -Wanalyzer-infinite-loop.
     378              :      Set to true during processing if any of the activity along
     379              :      this edge is "externally-visible work" (and thus ruling this
     380              :      out as being part of an infinite loop.
     381              : 
     382              :      For example, given:
     383              : 
     384              :      while (1)
     385              :        do_something ();
     386              : 
     387              :      although it is an infinite loop, presumably the point of the
     388              :      program is the loop body, and thus reporting this as an infinite
     389              :      loop is likely to be unhelpful to the user.  */
     390              :   bool m_could_do_work_p;
     391              : };
     392              : 
     393              : /* Extra data for an exploded_edge that represents an interprocedural
     394              :    call.  */
     395              : 
     396              : class interprocedural_call : public custom_edge_info
     397              : {
     398              : public:
     399         9577 :   interprocedural_call (const call_and_return_op &op,
     400              :                         function &callee_fun)
     401         9577 :   : m_op (op),
     402         9577 :     m_callee_fun (callee_fun)
     403              :   {}
     404              : 
     405              :   void print (pretty_printer *pp) const final override;
     406              : 
     407              :   void get_dot_attrs (const char *&out_style,
     408              :                       const char *&out_color) const final override;
     409              : 
     410              :   bool update_state (program_state *state,
     411              :                      const exploded_edge *eedge,
     412              :                      region_model_context *ctxt) const final override;
     413              : 
     414              :   bool update_model (region_model *model,
     415              :                      const exploded_edge *eedge,
     416              :                      region_model_context *ctxt) const final override;
     417              : 
     418              :   void add_events_to_path (checker_path *emission_path,
     419              :                            const exploded_edge &eedge,
     420              :                            pending_diagnostic &pd,
     421              :                            const state_transition *state_trans) const final override;
     422              : 
     423              :   bool
     424              :   try_to_rewind_data_flow (rewind_context &) const final override;
     425              : 
     426              :   const gcall &get_gcall () const;
     427              : 
     428              : private:
     429              :   const call_and_return_op &m_op;
     430              :   function &m_callee_fun;
     431              : };
     432              : 
     433              : /* Extra data for an exploded_edge that represents an interprocedural
     434              :    return.  */
     435              : 
     436              : class interprocedural_return : public custom_edge_info
     437              : {
     438              : public:
     439         8193 :   interprocedural_return (const gcall &call_stmt)
     440         8193 :   : m_call_stmt (call_stmt)
     441              :   {}
     442              : 
     443              :   void print (pretty_printer *pp) const final override;
     444              : 
     445              :   void get_dot_attrs (const char *&out_style,
     446              :                       const char *&out_color) const final override;
     447              : 
     448              :   bool update_state (program_state *state,
     449              :                      const exploded_edge *eedge,
     450              :                      region_model_context *ctxt) const final override;
     451              : 
     452              :   bool update_model (region_model *model,
     453              :                      const exploded_edge *eedge,
     454              :                      region_model_context *ctxt) const final override;
     455              : 
     456              :   void add_events_to_path (checker_path *emission_path,
     457              :                            const exploded_edge &eedge,
     458              :                            pending_diagnostic &pd,
     459              :                            const state_transition *state_trans) const final override;
     460              : 
     461              :   bool
     462              :   try_to_rewind_data_flow (rewind_context &) const final override;
     463              : 
     464              : private:
     465              :   const gcall &m_call_stmt;
     466              : };
     467              : 
     468              : /* Extra data for an exploded_edge that represents a rewind from a
     469              :    longjmp to a setjmp (or from a siglongjmp to a sigsetjmp).  */
     470              : 
     471           25 : class rewind_info_t : public custom_edge_info
     472              : {
     473              : public:
     474           45 :   rewind_info_t (const setjmp_record &setjmp_record,
     475              :                  const gcall &longjmp_call)
     476           25 :   : m_setjmp_record (setjmp_record),
     477           25 :     m_longjmp_call (longjmp_call)
     478              :   {}
     479              : 
     480            0 :   void print (pretty_printer *pp) const final override
     481              :   {
     482            0 :     pp_string (pp, "rewind");
     483            0 :   }
     484              : 
     485              :   bool update_model (region_model *model,
     486              :                      const exploded_edge *eedge,
     487              :                      region_model_context *ctxt) const final override;
     488              : 
     489              :   void add_events_to_path (checker_path *emission_path,
     490              :                            const exploded_edge &eedge,
     491              :                            pending_diagnostic &pd,
     492              :                            const state_transition *state_trans) const final override;
     493              : 
     494              :   program_point
     495           25 :   get_point_before_setjmp () const
     496              :   {
     497           25 :     return get_enode_origin ()->get_point ();
     498              :   }
     499              : 
     500              :   program_point
     501           25 :   get_point_after_setjmp () const
     502              :   {
     503           25 :     const program_point &origin_point = get_enode_origin ()->get_point ();
     504           25 :     return program_point (m_setjmp_record.m_sedge->m_dest,
     505           25 :                           origin_point.get_call_string ());
     506              :   }
     507              : 
     508           68 :   const gcall &get_setjmp_call () const
     509              :   {
     510           46 :     return *m_setjmp_record.m_setjmp_call;
     511              :   }
     512              : 
     513           68 :   const gcall &get_longjmp_call () const
     514              :   {
     515           83 :     return m_longjmp_call;
     516              :   }
     517              : 
     518           40 :   const exploded_node *get_enode_origin () const
     519              :   {
     520           40 :     return m_setjmp_record.m_enode;
     521              :   }
     522              : 
     523              : private:
     524              :   setjmp_record m_setjmp_record;
     525              :   const gcall &m_longjmp_call;
     526              : };
     527              : 
     528              : /* Statistics about aspects of an exploded_graph.  */
     529              : 
     530              : struct stats
     531              : {
     532              :   stats (int num_supernodes);
     533              :   void log (logger *logger) const;
     534              :   void dump (FILE *out) const;
     535              : 
     536              :   int get_total_enodes () const;
     537              : 
     538              :   int m_num_nodes;
     539              :   int m_node_reuse_count;
     540              :   int m_node_reuse_after_merge_count;
     541              :   int m_num_supernodes;
     542              : };
     543              : 
     544              : /* Traits class for ensuring uniqueness of point_and_state data within
     545              :    an exploded_graph.  */
     546              : 
     547              : struct eg_hash_map_traits
     548              : {
     549              :   typedef const point_and_state *key_type;
     550              :   typedef exploded_node *value_type;
     551              :   typedef exploded_node *compare_type;
     552              : 
     553      5300399 :   static inline hashval_t hash (const key_type &k)
     554              :   {
     555      5300399 :     gcc_assert (k != nullptr);
     556      5300399 :     gcc_assert (k != reinterpret_cast<key_type> (1));
     557      5300399 :     return k->hash ();
     558              :   }
     559      5004254 :   static inline bool equal_keys (const key_type &k1, const key_type &k2)
     560              :   {
     561      5004254 :     gcc_assert (k1 != nullptr);
     562      5004254 :     gcc_assert (k2 != nullptr);
     563      5004254 :     gcc_assert (k1 != reinterpret_cast<key_type> (1));
     564      5004254 :     gcc_assert (k2 != reinterpret_cast<key_type> (1));
     565      5004254 :     if (k1 && k2)
     566      5004254 :       return *k1 == *k2;
     567              :     else
     568              :       /* Otherwise they must both be non-NULL.  */
     569              :       return k1 == k2;
     570              :   }
     571              :   template <typename T>
     572              :   static inline void remove (T &)
     573              :   {
     574              :     /* empty; the nodes are handled elsewhere.  */
     575              :   }
     576              :   template <typename T>
     577              :   static inline void mark_deleted (T &entry)
     578              :   {
     579              :     entry.m_key = reinterpret_cast<key_type> (1);
     580              :   }
     581              :   template <typename T>
     582      1345639 :   static inline void mark_empty (T &entry)
     583              :   {
     584      1345639 :     entry.m_key = nullptr;
     585              :   }
     586              :   template <typename T>
     587      5979598 :   static inline bool is_deleted (const T &entry)
     588              :   {
     589      5979598 :     return entry.m_key == reinterpret_cast<key_type> (1);
     590              :   }
     591              :   template <typename T>
     592     18899571 :   static inline bool is_empty (const T &entry)
     593              :   {
     594     18899571 :     return entry.m_key == nullptr;
     595              :   }
     596              :   static const bool empty_zero_p = false;
     597              : };
     598              : 
     599              : /* Per-program_point data for an exploded_graph.  */
     600              : 
     601       276080 : struct per_program_point_data
     602              : {
     603       276080 :   per_program_point_data (const program_point &key)
     604       276080 :   : m_key (key), m_excess_enodes (0)
     605              :   {}
     606              : 
     607              :   const program_point m_key;
     608              :   auto_vec<exploded_node *> m_enodes;
     609              :   /* The number of attempts to create an enode for this point
     610              :      after exceeding --param=analyzer-max-enodes-per-program-point.  */
     611              :   int m_excess_enodes;
     612              : };
     613              : 
     614              : /* Traits class for storing per-program_point data within
     615              :    an exploded_graph.  */
     616              : 
     617              : struct eg_point_hash_map_traits
     618              : {
     619              :   typedef const program_point *key_type;
     620              :   typedef per_program_point_data *value_type;
     621              :   typedef per_program_point_data *compare_type;
     622              : 
     623      4329831 :   static inline hashval_t hash (const key_type &k)
     624              :   {
     625      4329831 :     gcc_assert (k != nullptr);
     626      4329831 :     gcc_assert (k != reinterpret_cast<key_type> (1));
     627      4329831 :     return k->hash ();
     628              :   }
     629      4181840 :   static inline bool equal_keys (const key_type &k1, const key_type &k2)
     630              :   {
     631      4181840 :     gcc_assert (k1 != nullptr);
     632      4181840 :     gcc_assert (k2 != nullptr);
     633      4181840 :     gcc_assert (k1 != reinterpret_cast<key_type> (1));
     634      4181840 :     gcc_assert (k2 != reinterpret_cast<key_type> (1));
     635      4181840 :     if (k1 && k2)
     636      4181840 :       return *k1 == *k2;
     637              :     else
     638              :       /* Otherwise they must both be non-NULL.  */
     639              :       return k1 == k2;
     640              :   }
     641              :   template <typename T>
     642              :   static inline void remove (T &)
     643              :   {
     644              :     /* empty; the nodes are handled elsewhere.  */
     645              :   }
     646              :   template <typename T>
     647              :   static inline void mark_deleted (T &entry)
     648              :   {
     649              :     entry.m_key = reinterpret_cast<key_type> (1);
     650              :   }
     651              :   template <typename T>
     652       974582 :   static inline void mark_empty (T &entry)
     653              :   {
     654       974582 :     entry.m_key = nullptr;
     655              :   }
     656              :   template <typename T>
     657      5169739 :   static inline bool is_deleted (const T &entry)
     658              :   {
     659      5169739 :     return entry.m_key == reinterpret_cast<key_type> (1);
     660              :   }
     661              :   template <typename T>
     662     16197840 :   static inline bool is_empty (const T &entry)
     663              :   {
     664     16197840 :     return entry.m_key == nullptr;
     665              :   }
     666              :   static const bool empty_zero_p = false;
     667              : };
     668              : 
     669              : /* Data about a particular call_string within an exploded_graph.  */
     670              : 
     671              : struct per_call_string_data
     672              : {
     673        11554 :   per_call_string_data (const call_string &key, int num_supernodes)
     674        11554 :   : m_key (key), m_stats (num_supernodes)
     675              :   {}
     676              : 
     677              :   const call_string &m_key;
     678              :   stats m_stats;
     679              : };
     680              : 
     681              : /* Data about a particular function within an exploded_graph.  */
     682              : 
     683              : struct per_function_data
     684              : {
     685          351 :   per_function_data () {}
     686              :   ~per_function_data ();
     687              : 
     688              :   void add_call_summary (exploded_node *node);
     689              : 
     690              :   auto_vec<call_summary *> m_summaries;
     691              : };
     692              : 
     693              : /* The strongly connected components of a supergraph.
     694              :    In particular, this allows us to compute a partial ordering
     695              :    of supernodes.  */
     696              : 
     697              : class strongly_connected_components
     698              : {
     699              : public:
     700              :   strongly_connected_components (const supergraph &sg, logger *logger);
     701              : 
     702      2121134 :   int get_scc_id (int node_index) const
     703              :   {
     704          392 :     return m_per_node[node_index].m_lowlink;
     705              :   }
     706              : 
     707              :   void dump () const;
     708              : 
     709              :   std::unique_ptr<json::array> to_json () const;
     710              : 
     711              : private:
     712              :   struct per_node_data
     713              :   {
     714       201441 :     per_node_data ()
     715       201441 :     : m_id (-1), m_lowlink (-1), m_on_stack (false)
     716              :     {}
     717              : 
     718              :     int m_id;
     719              :     int m_lowlink;
     720              :     bool m_on_stack;
     721              :   };
     722              : 
     723              :   void strong_connect (unsigned index, logger *logger);
     724              : 
     725              :   const supergraph &m_sg;
     726              :   auto_vec<unsigned> m_stack;
     727              :   auto_vec<per_node_data> m_per_node;
     728              : };
     729              : 
     730              : /* The worklist of exploded_node instances that have been added to
     731              :    an exploded_graph, but that haven't yet been processed to find
     732              :    their successors (or warnings).
     733              : 
     734              :    The enodes are stored in a priority queue, ordered by a topological
     735              :    sort of the SCCs in the supergraph, so that enodes for the same
     736              :    program_point should appear at the front of the queue together.
     737              :    This allows for state-merging at CFG join-points, so that
     738              :    sufficiently-similar enodes can be merged into one.  */
     739              : 
     740              : class worklist
     741              : {
     742              : public:
     743              :   worklist (const exploded_graph &eg, const analysis_plan &plan);
     744              :   unsigned length () const;
     745              :   exploded_node *take_next ();
     746              :   exploded_node *peek_next ();
     747              :   void add_node (exploded_node *enode);
     748          628 :   int get_scc_id (const supernode &snode) const
     749              :   {
     750         1256 :     return m_scc.get_scc_id (snode.m_id);
     751              :   }
     752              : 
     753              :   std::unique_ptr<json::object> to_json () const;
     754              : 
     755              : private:
     756              :   class key_t
     757              :   {
     758              :   public:
     759       367272 :     key_t (const worklist &w, exploded_node *enode)
     760       367272 :     : m_worklist (w), m_enode (enode)
     761              :     {}
     762              : 
     763      1029650 :     bool operator< (const key_t &other) const
     764              :     {
     765      1029650 :       return cmp (*this, other) < 0;
     766              :     }
     767              : 
     768       277424 :     bool operator== (const key_t &other) const
     769              :     {
     770       277424 :       return cmp (*this, other) == 0;
     771              :     }
     772              : 
     773       277424 :     bool operator> (const key_t &other) const
     774              :     {
     775       554848 :       return !(*this == other || *this < other);
     776              :     }
     777              : 
     778              :   private:
     779              :     static int cmp (const key_t &ka, const key_t &kb);
     780              : 
     781      2132008 :     int get_scc_id (const exploded_node *enode) const
     782              :     {
     783      2132008 :       const supernode *snode = enode->get_supernode ();
     784      2132008 :       if (snode == nullptr)
     785              :         return 0;
     786      2120496 :       return m_worklist.m_scc.get_scc_id (snode->m_id);
     787              :     }
     788              : 
     789              :     const worklist &m_worklist;
     790              :     exploded_node *m_enode;
     791              :   };
     792              : 
     793              :   /* The order is important here: m_scc needs to stick around
     794              :      until after m_queue has finished being cleaned up (the dtor
     795              :      calls the ordering fns).  */
     796              :   strongly_connected_components m_scc;
     797              :   const analysis_plan &m_plan;
     798              : 
     799              :   /* Priority queue, backed by a fibonacci_heap.  */
     800              :   typedef fibonacci_heap<key_t, exploded_node> queue_t;
     801              :   queue_t m_queue;
     802              : };
     803              : 
     804              : /* An exploded_graph is a directed graph of unique <point, state> pairs.
     805              :    It also has a worklist of nodes that are waiting for their successors
     806              :    to be added to the graph.  */
     807              : 
     808              : class exploded_graph : public digraph<eg_traits>
     809              : {
     810              : public:
     811              :   typedef hash_map <const call_string *,
     812              :                     per_call_string_data *> call_string_data_map_t;
     813              : 
     814              :   exploded_graph (const supergraph &sg, logger *logger,
     815              :                   const extrinsic_state &ext_state,
     816              :                   const state_purge_map *purge_map,
     817              :                   const analysis_plan &plan,
     818              :                   int verbosity);
     819              :   ~exploded_graph ();
     820              : 
     821      5938485 :   logger *get_logger () const { return m_logger.get_logger (); }
     822              : 
     823        69202 :   const supergraph &get_supergraph () const { return m_sg; }
     824      3416616 :   const extrinsic_state &get_ext_state () const { return m_ext_state; }
     825         6671 :   engine *get_engine () const { return m_ext_state.get_engine (); }
     826       372598 :   const state_purge_map *get_purge_map () const { return m_purge_map; }
     827        10029 :   const analysis_plan &get_analysis_plan () const { return m_plan; }
     828              : 
     829         6681 :   exploded_node *get_origin () const { return m_origin; }
     830              : 
     831              :   exploded_node *add_function_entry (const function &fun);
     832              : 
     833              :   void build_initial_worklist ();
     834              :   void process_worklist ();
     835              :   bool maybe_process_run_of_enodes (exploded_node *node);
     836              :   void process_node (exploded_node *node);
     837              : 
     838              :   exploded_node *get_or_create_node (const program_point &point,
     839              :                                      const program_state &state,
     840              :                                      exploded_node *enode_for_diag,
     841              :                                      bool add_to_worklist = true);
     842              :   exploded_edge *add_edge (exploded_node *src, exploded_node *dest,
     843              :                            const superedge *sedge, bool could_do_work,
     844              :                            std::unique_ptr<custom_edge_info> custom = nullptr);
     845              : 
     846              :   per_program_point_data *
     847              :   get_or_create_per_program_point_data (const program_point &);
     848              :   per_program_point_data *
     849              :   get_per_program_point_data (const program_point &) const;
     850              : 
     851              :   per_call_string_data *
     852              :   get_or_create_per_call_string_data (const call_string &);
     853              : 
     854              :   per_function_data *
     855              :   get_or_create_per_function_data (function *);
     856              :   per_function_data *get_per_function_data (function *) const;
     857              : 
     858              :   void save_diagnostic (const state_machine &sm,
     859              :                         const exploded_node *enode,
     860              :                         const supernode *node, const gimple *stmt,
     861              :                         tree var, state_machine::state_t state,
     862              :                         pending_diagnostic *d);
     863              : 
     864        14788 :   diagnostic_manager &get_diagnostic_manager ()
     865              :   {
     866        14808 :     return m_diagnostic_manager;
     867              :   }
     868            1 :   const diagnostic_manager &get_diagnostic_manager () const
     869              :   {
     870            1 :     return m_diagnostic_manager;
     871              :   }
     872              : 
     873              :   stats *get_global_stats () { return &m_global_stats; }
     874              :   stats *get_or_create_function_stats (function *fn);
     875              :   void log_stats () const;
     876              :   void dump_stats (FILE *) const;
     877              :   void dump_exploded_nodes () const;
     878              : 
     879              :   std::unique_ptr<json::object> to_json () const;
     880              : 
     881              :   exploded_node *get_node_by_index (int idx) const;
     882              : 
     883              :   const call_string_data_map_t *get_per_call_string_data () const
     884              :   { return &m_per_call_string_data; }
     885              : 
     886          628 :   int get_scc_id (const supernode &node) const
     887              :   {
     888          628 :     return m_worklist.get_scc_id (node);
     889              :   }
     890              : 
     891              :   void on_escaped_function (tree fndecl);
     892              : 
     893              :   void unwind_from_exception (exploded_node &enode,
     894              :                               const gimple *stmt,
     895              :                               region_model_context *ctxt);
     896              : 
     897              :   /* In infinite-loop.cc */
     898              :   void detect_infinite_loops ();
     899              : 
     900              :   /* In infinite-recursion.cc */
     901              :   void detect_infinite_recursion (exploded_node *enode);
     902              :   exploded_node *find_previous_entry_to (function *top_of_stack_fun,
     903              :                                          exploded_node *enode) const;
     904              : 
     905              :   std::unique_ptr<diagnostics::digraphs::digraph>
     906              :   make_diagnostics_digraph () const;
     907              : 
     908              :   const worklist &
     909            1 :   get_worklist () const { return m_worklist; }
     910              : 
     911              : private:
     912              :   void print_bar_charts (pretty_printer *pp) const;
     913              : 
     914              :   DISABLE_COPY_AND_ASSIGN (exploded_graph);
     915              : 
     916              :   const supergraph &m_sg;
     917              : 
     918              :   log_user m_logger;
     919              : 
     920              :   /* Map from point/state to exploded node.
     921              :      To avoid duplication we store point_and_state
     922              :      *pointers* as keys, rather than point_and_state, using the
     923              :      instance from within the exploded_node, with a custom hasher.  */
     924              :   typedef hash_map <const point_and_state *, exploded_node *,
     925              :                     eg_hash_map_traits> map_t;
     926              :   map_t m_point_and_state_to_node;
     927              : 
     928              :   /* Map from program_point to per-program_point data.  */
     929              :   typedef hash_map <const program_point *, per_program_point_data *,
     930              :                     eg_point_hash_map_traits> point_map_t;
     931              :   point_map_t m_per_point_data;
     932              : 
     933              :   worklist m_worklist;
     934              : 
     935              :   exploded_node *m_origin;
     936              : 
     937              :   const extrinsic_state &m_ext_state;
     938              : 
     939              :   const state_purge_map *const m_purge_map;
     940              : 
     941              :   const analysis_plan &m_plan;
     942              : 
     943              :   typedef hash_map<function *, per_function_data *> per_function_data_t;
     944              :   per_function_data_t m_per_function_data;
     945              : 
     946              :   diagnostic_manager m_diagnostic_manager;
     947              : 
     948              :   /* Stats.  */
     949              :   stats m_global_stats;
     950              :   typedef ordered_hash_map<function *, stats *> function_stat_map_t;
     951              :   function_stat_map_t m_per_function_stats;
     952              :   stats m_functionless_stats;
     953              : 
     954              :   call_string_data_map_t m_per_call_string_data;
     955              : 
     956              :   /* Functions with a top-level enode, to make add_function_entry
     957              :      be idempotent, for use in handling callbacks.  */
     958              :   hash_set<function *> m_functions_with_enodes;
     959              : };
     960              : 
     961              : /* A reason why a particular exploded_path is infeasible.  */
     962              : 
     963            4 : class feasibility_problem
     964              : {
     965              : public:
     966            4 :   feasibility_problem (unsigned eedge_idx,
     967              :                        const exploded_edge &eedge,
     968              :                        std::unique_ptr<rejected_constraint> rc)
     969            4 :   : m_eedge_idx (eedge_idx), m_eedge (eedge),
     970            4 :     m_rc (std::move (rc))
     971              :   {}
     972              : 
     973              :   std::unique_ptr<text_art::tree_widget>
     974              :   make_dump_widget (symbolic::node_dump_state &nds) const;
     975              : 
     976              :   void dump () const;
     977              :   void dump_to_pp (pretty_printer *pp) const;
     978              :   void dump_to_logger (logger &log) const;
     979              : 
     980              :   std::unique_ptr<json::object>
     981              :   to_json () const;
     982              : 
     983              :   unsigned m_eedge_idx;
     984              :   const exploded_edge &m_eedge;
     985              :   std::unique_ptr<rejected_constraint> m_rc;
     986              : };
     987              : 
     988              : /* A class for capturing the state of a node when checking a path
     989              :    through the exploded_graph for feasibility.  */
     990              : 
     991              : class feasibility_state
     992              : {
     993              : public:
     994              :   feasibility_state (region_model_manager *manager,
     995              :                      const supergraph &sg);
     996              :   feasibility_state (const region_model &model,
     997              :                      const supergraph &sg);
     998              :   feasibility_state (const feasibility_state &other);
     999              : 
    1000              :   feasibility_state &operator= (const feasibility_state &other);
    1001              : 
    1002              :   bool maybe_update_for_edge (logger *logger,
    1003              :                               const exploded_edge *eedge,
    1004              :                               region_model_context *ctxt,
    1005              :                               std::unique_ptr<rejected_constraint> *out_rc);
    1006              : 
    1007       141228 :   region_model &get_model () { return m_model; }
    1008         1800 :   const region_model &get_model () const { return m_model; }
    1009              :   auto_sbitmap &get_snodes_visited () { return m_snodes_visited; }
    1010              :   const auto_sbitmap &get_snodes_visited () const { return m_snodes_visited; }
    1011              : 
    1012              :   std::unique_ptr<text_art::tree_widget>
    1013              :   make_dump_widget (symbolic::node_dump_state &nds) const;
    1014              : 
    1015              :   void dump_to_pp (pretty_printer *pp) const;
    1016              : 
    1017              : private:
    1018              :   region_model m_model;
    1019              :   auto_sbitmap m_snodes_visited;
    1020              : };
    1021              : 
    1022              : // TODO: split the above up?
    1023              : 
    1024              : } // namespace ana
    1025              : 
    1026              : #endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.