LCOV - code coverage report
Current view: top level - gcc/analyzer - engine.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 82.1 % 2394 1965
Test Date: 2026-11-14 16:39:50 Functions: 82.4 % 176 145
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* The analysis "engine".
       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              : #include "analyzer/common.h"
      22              : 
      23              : #include <zlib.h>
      24              : 
      25              : #include "cfg.h"
      26              : #include "gcc-rich-location.h"
      27              : #include "gimple-iterator.h"
      28              : #include "gimple-pretty-print.h"
      29              : #include "cgraph.h"
      30              : #include "fold-const.h"
      31              : #include "digraph.h"
      32              : #include "plugin.h"
      33              : #include "target.h"
      34              : #include "stringpool.h"
      35              : #include "attribs.h"
      36              : #include "tree-dfa.h"
      37              : #include "gimple-predict.h"
      38              : #include "context.h"
      39              : #include "channels.h"
      40              : #include "pretty-print-markup.h"
      41              : 
      42              : #include "text-art/dump.h"
      43              : 
      44              : #include "analyzer/analyzer-logging.h"
      45              : #include "analyzer/call-string.h"
      46              : #include "analyzer/program-point.h"
      47              : #include "analyzer/store.h"
      48              : #include "analyzer/region-model.h"
      49              : #include "analyzer/constraint-manager.h"
      50              : #include "analyzer/sm.h"
      51              : #include "analyzer/pending-diagnostic.h"
      52              : #include "analyzer/diagnostic-manager.h"
      53              : #include "analyzer/supergraph.h"
      54              : #include "analyzer/program-state.h"
      55              : #include "analyzer/exploded-graph.h"
      56              : #include "analyzer/exploded-path.h"
      57              : #include "analyzer/analysis-plan.h"
      58              : #include "analyzer/checker-path.h"
      59              : #include "analyzer/state-purge.h"
      60              : #include "analyzer/bar-chart.h"
      61              : #include "analyzer/call-info.h"
      62              : #include "analyzer/known-function-manager.h"
      63              : #include "analyzer/call-summary.h"
      64              : #include "analyzer/impl-sm-context.h"
      65              : 
      66              : /* For an overview, see gcc/doc/analyzer.texi.  */
      67              : 
      68              : #if ENABLE_ANALYZER
      69              : 
      70              : namespace ana {
      71              : 
      72              : /* class impl_region_model_context : public region_model_context.  */
      73              : 
      74      1237475 : impl_region_model_context::
      75              : impl_region_model_context (exploded_graph &eg,
      76              :                            exploded_node *enode_for_diag,
      77              :                            const program_state *old_state,
      78              :                            program_state *new_state,
      79              :                            uncertainty_t *uncertainty,
      80              :                            path_context *path_ctxt,
      81              :                            const gimple *stmt,
      82              :                            bool *out_could_have_done_work)
      83      1237475 : : m_eg (&eg), m_logger (eg.get_logger ()),
      84      1237475 :   m_enode_for_diag (enode_for_diag),
      85      1237475 :   m_old_state (old_state),
      86      1237475 :   m_new_state (new_state),
      87      1237475 :   m_stmt (stmt),
      88      1237475 :   m_ext_state (eg.get_ext_state ()),
      89      1237475 :   m_uncertainty (uncertainty),
      90      1237475 :   m_path_ctxt (path_ctxt),
      91      1237475 :   m_out_could_have_done_work (out_could_have_done_work)
      92              : {
      93      1237475 : }
      94              : 
      95            4 : impl_region_model_context::
      96              : impl_region_model_context (program_state *state,
      97              :                            const extrinsic_state &ext_state,
      98              :                            uncertainty_t *uncertainty,
      99              :                            logger *logger)
     100            4 : : m_eg (nullptr), m_logger (logger), m_enode_for_diag (nullptr),
     101            4 :   m_old_state (nullptr),
     102            4 :   m_new_state (state),
     103            4 :   m_stmt (nullptr),
     104            4 :   m_ext_state (ext_state),
     105            4 :   m_uncertainty (uncertainty),
     106            4 :   m_path_ctxt (nullptr),
     107            4 :   m_out_could_have_done_work (nullptr)
     108              : {
     109            4 : }
     110              : 
     111              : bool
     112         3372 : impl_region_model_context::warn_at (std::unique_ptr<pending_diagnostic> d,
     113              :                                     pending_location &&ploc)
     114              : {
     115         3372 :   LOG_FUNC (get_logger ());
     116         3372 :   if (m_eg)
     117              :     {
     118         3372 :       bool terminate_path = d->terminate_path_p ();
     119         3372 :       if (m_eg->get_diagnostic_manager ().add_diagnostic (std::move (ploc),
     120              :                                                           std::move (d)))
     121              :         {
     122         3289 :           if (m_path_ctxt
     123         2290 :               && terminate_path
     124          883 :               && flag_analyzer_suppress_followups)
     125          684 :             m_path_ctxt->terminate_path ();
     126              :           return true;
     127              :         }
     128              :     }
     129              :   return false;
     130         3372 : }
     131              : 
     132              : void
     133          214 : impl_region_model_context::add_note (std::unique_ptr<pending_note> pn)
     134              : {
     135          214 :   LOG_FUNC (get_logger ());
     136          214 :   if (m_eg)
     137          214 :     m_eg->get_diagnostic_manager ().add_note (std::move (pn));
     138          214 : }
     139              : 
     140              : void
     141          179 : impl_region_model_context::add_event (std::unique_ptr<checker_event> event)
     142              : {
     143          179 :   LOG_FUNC (get_logger ());
     144          179 :   if (m_eg)
     145          179 :     m_eg->get_diagnostic_manager ().add_event (std::move (event));
     146          179 : }
     147              : 
     148              : void
     149        24808 : impl_region_model_context::on_svalue_leak (const svalue *sval)
     150              : {
     151        24808 :   sval = sm_state_map::canonicalize_svalue (sval, m_ext_state);
     152       247966 :   for (sm_state_map *smap : m_new_state->m_checker_states)
     153       173542 :     smap->on_svalue_leak (sval, this);
     154        24808 : }
     155              : 
     156              : void
     157       433757 : impl_region_model_context::
     158              : on_liveness_change (symbolic::liveness_context &liveness_ctxt)
     159              : {
     160      4335397 :   for (sm_state_map *smap : m_new_state->m_checker_states)
     161      3034126 :     smap->on_liveness_change (liveness_ctxt, m_ext_state, this);
     162       433757 : }
     163              : 
     164              : void
     165        30321 : impl_region_model_context::on_unknown_change (const symbolic::value_node &val,
     166              :                                               bool is_mutable)
     167              : {
     168        30321 :   if (auto *sval = val.dyn_cast_svalue ())
     169        23639 :     if (!sval->can_have_associated_state_p ())
     170              :       return;
     171       294639 :   for (sm_state_map *smap : m_new_state->m_checker_states)
     172       206220 :     smap->on_unknown_change (val, is_mutable, m_ext_state);
     173              : }
     174              : 
     175              : void
     176          309 : impl_region_model_context::on_escaped_function (tree fndecl)
     177              : {
     178          309 :   m_eg->on_escaped_function (fndecl);
     179          309 : }
     180              : 
     181              : uncertainty_t *
     182      3667559 : impl_region_model_context::get_uncertainty ()
     183              : {
     184      3667559 :   return m_uncertainty;
     185              : }
     186              : 
     187              : /* Purge state involving SVAL.  The region_model has already been purged,
     188              :    so we only need to purge other state in the program_state:
     189              :    the sm-state.  */
     190              : 
     191              : void
     192        11666 : impl_region_model_context::purge_state_involving (const symbolic::node &node)
     193              : {
     194        11666 :   int i;
     195        11666 :   sm_state_map *smap;
     196        93328 :   FOR_EACH_VEC_ELT (m_new_state->m_checker_states, i, smap)
     197        81662 :     smap->purge_state_involving (node, m_ext_state);
     198        11666 : }
     199              : 
     200              : void
     201         7942 : impl_region_model_context::bifurcate (std::unique_ptr<custom_edge_info> info)
     202              : {
     203         7942 :   if (m_path_ctxt)
     204         7942 :     m_path_ctxt->bifurcate (std::move (info));
     205         7942 : }
     206              : 
     207              : void
     208         1139 : impl_region_model_context::terminate_path ()
     209              : {
     210         1139 :   if (m_path_ctxt)
     211         1102 :     return m_path_ctxt->terminate_path ();
     212              : }
     213              : 
     214              : bool
     215       630998 : impl_region_model_context::
     216              : get_state_map_by_name (const char *name,
     217              :                        sm_state_map **out_smap,
     218              :                        const state_machine **out_sm,
     219              :                        unsigned *out_sm_idx,
     220              :                        std::unique_ptr<sm_context> *out_sm_context)
     221              : {
     222       630998 :   if (!m_new_state)
     223              :     return false;
     224              : 
     225       626972 :   unsigned sm_idx;
     226       626972 :   if (!m_ext_state.get_sm_idx_by_name (name, &sm_idx))
     227              :     return false;
     228              : 
     229       626505 :   const state_machine *sm = &m_ext_state.get_sm (sm_idx);
     230       626505 :   sm_state_map *new_smap = m_new_state->m_checker_states[sm_idx];
     231              : 
     232       626505 :   *out_smap = new_smap;
     233       626505 :   *out_sm = sm;
     234       626505 :   if (out_sm_idx)
     235       625858 :     *out_sm_idx = sm_idx;
     236       626505 :   if (out_sm_context)
     237              :     {
     238          577 :       const sm_state_map *old_smap = m_old_state->m_checker_states[sm_idx];
     239          577 :       *out_sm_context
     240          577 :         = std::make_unique<impl_sm_context> (*m_eg,
     241              :                                              sm_idx,
     242              :                                              *sm,
     243          577 :                                              m_enode_for_diag,
     244          577 :                                              m_old_state,
     245          577 :                                              m_new_state,
     246              :                                              old_smap,
     247              :                                              new_smap,
     248          577 :                                              m_path_ctxt,
     249         1154 :                                              false);
     250              :     }
     251              :   return true;
     252              : }
     253              : 
     254              : /* Subclass of pending_location::fixer_for_epath for finding the best stmt
     255              :    to report the leak at, given the emission path.  */
     256              : 
     257              : class leak_ploc_fixer_for_epath : public pending_location::fixer_for_epath
     258              : {
     259              : public:
     260         1148 :   leak_ploc_fixer_for_epath (const exploded_graph &eg, tree var)
     261         1148 :   : m_eg (eg), m_var (var)
     262              :   {}
     263              : 
     264              :   void
     265         1070 :   fixup_for_epath (const exploded_path &epath,
     266              :                    pending_location &ploc) const final override
     267              :   {
     268         1070 :     logger * const logger = m_eg.get_logger ();
     269         1070 :     LOG_FUNC (logger);
     270              : 
     271              :     /* Handle the interprocedural case where we leak the retval at a return
     272              :        because the caller discards the return value.  */
     273         1070 :     if (m_var
     274          924 :         && TREE_CODE (m_var) == RESULT_DECL)
     275              :       {
     276            6 :         auto &point = ploc.m_enode->get_point ();
     277           12 :         if (point.get_stack_depth () > 1)
     278            6 :           if (point.get_supernode ()->exit_p ())
     279              :             {
     280              :               /* Get the program_point for the call within the caller.  */
     281            6 :               auto &cs = point.get_call_string ();
     282            6 :               auto caller_snode = cs.get_return_node_in_caller ();
     283            6 :               gcc_assert (caller_snode);
     284            6 :               program_point caller_point (caller_snode, *cs.get_parent ());
     285            6 :               ploc.m_event_loc_info = event_loc_info (caller_point);
     286            6 :               return;
     287              :             }
     288              :       }
     289              : 
     290              :     /* Handle the case where we have e.g.:
     291              :        |   var = malloc (N);
     292              :        |   var = NULL;
     293              :        which with SSA becomes e.g.:
     294              :        |   var_0 = malloc (N);
     295              :        |   var_1 = nullptr;
     296              :        and thus leads to the leak being found at the enode where "var_0" goes
     297              :        out of scope.
     298              :        Fix up the location of the leak to report it at the write of NULL.  */
     299         1064 :     if (m_var && TREE_CODE (m_var) == SSA_NAME)
     300              :       {
     301          696 :         log_scope sentinel (logger, "looking for write to sibling SSA name");
     302              :         /* Locate the final write to this SSA name in the path.  */
     303          696 :         const gimple *def_stmt = SSA_NAME_DEF_STMT (m_var);
     304              : 
     305          696 :         int idx_of_def_stmt;
     306          696 :         if (epath.find_stmt_backwards (def_stmt, &idx_of_def_stmt))
     307              :           {
     308              :             /* What was the next write to the underlying var
     309              :                after the SSA name was set? (if any).  */
     310              : 
     311          631 :             for (unsigned idx = idx_of_def_stmt + 1;
     312        10702 :                  idx < epath.m_elements.size ();
     313              :                  ++idx)
     314              :               {
     315        10073 :                 const exploded_edge *eedge = epath.m_elements[idx].m_eedge;
     316        10073 :                 if (logger)
     317            0 :                   logger->log ("eedge[%i]: EN %i -> EN %i",
     318              :                                idx,
     319            0 :                                eedge->m_src->m_index,
     320            0 :                                eedge->m_dest->m_index);
     321        10073 :                 const gimple *stmt = eedge->maybe_get_stmt ();
     322        10073 :                 if (!stmt)
     323         2862 :                   continue;
     324        12910 :                 if (const gassign *assign = dyn_cast <const gassign *> (stmt))
     325              :                   {
     326         2839 :                     tree lhs = gimple_assign_lhs (assign);
     327         2839 :                     if (TREE_CODE (lhs) == SSA_NAME
     328         4655 :                         && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (m_var))
     329              :                       {
     330            2 :                         if (logger)
     331            0 :                           logger->log ("using location 0%lx from gassign",
     332            0 :                                        assign->location);
     333            2 :                         ploc.m_event_loc_info.m_loc = assign->location;
     334            2 :                         return;
     335              :                       }
     336              :                   }
     337              :               }
     338              :           }
     339          696 :       }
     340              : 
     341              :     /* If the epath ends at a function exit node, the location is at
     342              :        the final "}".  Try walking backward along EPATH, looking for a
     343              :        the first suitable stmt with a better location.  */
     344         1062 :     gcc_assert (ploc.m_enode->get_supernode ());
     345         1062 :     const greturn *return_stmt = nullptr;
     346         1062 :     if (ploc.m_enode->get_supernode ()->exit_p ()
     347         1062 :         && has_return_stmt_p (epath, return_stmt, logger))
     348              :       {
     349              :         /* If we have "return SSA_NAME;" on EPATH, keep track of the
     350              :            pertinent SSA name as we walk backwards through EPATH.  */
     351          652 :         tree retval = NULL_TREE;
     352          652 :         if (return_stmt)
     353          652 :           retval = gimple_return_retval (return_stmt);
     354              : 
     355          652 :         log_scope sentinel (logger, "walking backward along epath");
     356         2701 :         for (int idx = epath.m_elements.size () - 1; idx >= 0; --idx)
     357              :           {
     358         2652 :             const exploded_path::element_t &element = epath.m_elements[idx];
     359         2652 :             const exploded_edge *eedge = element.m_eedge;
     360         2652 :             if (logger)
     361              :               {
     362            0 :                 logger->log ("eedge[%i]: EN %i -> EN %i",
     363              :                              idx,
     364            0 :                              eedge->m_src->m_index,
     365            0 :                              eedge->m_dest->m_index);
     366            0 :                 if (retval)
     367            0 :                   logger->log ("  retval: %qE", retval);
     368              :               }
     369         2652 :             if (auto op = eedge->maybe_get_op ())
     370              :               {
     371         1769 :                 if (retval)
     372          350 :                   if (auto phis = op->dyn_cast_phis_for_edge_op ())
     373              :                     {
     374          148 :                       for (auto iter : phis->get_pairs ())
     375           74 :                         if (retval == iter.m_dst)
     376              :                           {
     377              :                             /* We have "PHI(RETVAL = SRC);"
     378              :                                Track SRC instead  */
     379           74 :                             retval = iter.m_src;
     380           74 :                             if (logger)
     381            0 :                               logger->log ("updating retval to %qE", retval);
     382              :                           }
     383              :                     }
     384         1769 :                 if (const gimple *stmt = op->maybe_get_stmt ())
     385         1681 :                   if (consider_stmt_location_p (*stmt, retval))
     386          816 :                     if (useful_location_p (stmt->location))
     387              :                       {
     388          603 :                         if (logger)
     389            0 :                           logger->log ("using location 0x%lx from stmt",
     390            0 :                                        stmt->location);
     391          603 :                         ploc.m_event_loc_info.m_loc = stmt->location;
     392          603 :                         return;
     393              :                       }
     394              :               }
     395              :           }
     396          652 :       }
     397         1070 :   }
     398              : 
     399              : private:
     400              :   static bool
     401          652 :   has_return_stmt_p (const exploded_path &epath,
     402              :                      const greturn *&out_greturn,
     403              :                      logger *logger)
     404              :   {
     405          652 :     LOG_SCOPE (logger);
     406              : 
     407         1097 :     for (int idx = epath.m_elements.size () - 1; idx >= 0; --idx)
     408              :       {
     409         1097 :         const exploded_path::element_t &element = epath.m_elements[idx];
     410         1097 :         const exploded_edge *eedge = element.m_eedge;
     411         1097 :         if (eedge->m_src->get_stack_depth ()
     412         2194 :             != eedge->m_dest->get_stack_depth ())
     413              :           {
     414              :             /* We have interprocedural activity, and
     415              :                presumably are no longer in the function where
     416              :                EPATH terminates.
     417              :                Give up.  */
     418              :             return false;
     419              :           }
     420         1097 :         if (auto op = eedge->maybe_get_op ())
     421              :           {
     422          652 :             switch (op->get_kind ())
     423              :               {
     424              :               default:
     425              :                 break;
     426          652 :               case operation::kind::return_stmt:
     427          652 :                 if (logger)
     428            0 :                   logger->log ("found return_stmt");
     429          652 :                 out_greturn = &((const greturn_op *)op)->get_greturn ();
     430          652 :                 return true;
     431            0 :               case operation::kind::predict_stmt:
     432            0 :                 {
     433            0 :                   auto &stmt = ((const gimple_stmt_op *)op)->get_stmt ();
     434            0 :                   switch (gimple_predict_predictor (&stmt))
     435              :                     {
     436            0 :                     case PRED_TREE_EARLY_RETURN:
     437              :                       /* Assume this is due to a "return;" in the user's
     438              :                          code.  */
     439            0 :                       if (logger)
     440            0 :                         logger->log ("assuming a return: PRED_TREE_EARLY_RETURN");
     441              :                       return true;
     442              :                     default:
     443              :                       break;
     444              :                     }
     445              :                 }
     446              :                 break;
     447              :               }
     448              :           }
     449              :       }
     450              :     return false;
     451          652 :   }
     452              : 
     453              :   /* When certain statements show up on the epath of a leak
     454              :      at an exit node, if they have locations, these locations
     455              :      tend to be better locations for the leak.
     456              :      Return true for such statements (but without checking their
     457              :      locations).  */
     458              :   static bool
     459         1681 :   consider_stmt_location_p (const gimple &stmt,
     460              :                             tree retval)
     461              :   {
     462         1681 :     if (retval && TREE_CODE (retval) == SSA_NAME)
     463          274 :       if (&stmt == SSA_NAME_DEF_STMT (retval))
     464              :         return true;
     465              : 
     466         1655 :     switch (stmt.code)
     467              :       {
     468              :       default:
     469              :         break;
     470          506 :       case GIMPLE_CALL:
     471          506 :         {
     472          506 :           const gcall &call = *as_a <const gcall *> (&stmt);
     473          506 :           if (is_cxa_end_catch_p (call))
     474              :             return true;
     475              :         }
     476              :         break;
     477              :       case GIMPLE_PREDICT:
     478              :       case GIMPLE_RETURN:
     479              :         return true;
     480              :       }
     481              :     return false;
     482              :   }
     483              : 
     484              :   const exploded_graph &m_eg;
     485              :   tree m_var;
     486              : };
     487              : 
     488              : std::unique_ptr<pending_location::fixer_for_epath>
     489            0 : make_ploc_fixer_for_epath_for_leak_diagnostic (const exploded_graph &eg,
     490              :                                           tree var)
     491              : {
     492            0 :   return std::make_unique<leak_ploc_fixer_for_epath> (eg, var);
     493              : }
     494              : 
     495              : /* A measurement of how good EXPR is for presenting to the user, so
     496              :    that e.g. we can say prefer printing
     497              :      "leak of 'tmp.m_ptr'"
     498              :    over:
     499              :      "leak of '<unknown>'".  */
     500              : 
     501              : static int
     502        20002 : readability (const_tree expr)
     503              : {
     504              :   /* Arbitrarily-chosen "high readability" value.  */
     505        43662 :   const int HIGH_READABILITY = 65536;
     506              : 
     507        43662 :   gcc_assert (expr);
     508        43662 :   switch (TREE_CODE (expr))
     509              :     {
     510         8685 :     case COMPONENT_REF:
     511         8685 :     case MEM_REF:
     512              :       /* Impose a slight readability penalty relative to that of
     513              :          operand 0.  */
     514         8685 :       return readability (TREE_OPERAND (expr, 0)) - 16;
     515              : 
     516        14083 :     case SSA_NAME:
     517        14083 :       {
     518        14083 :         if (tree var = SSA_NAME_VAR (expr))
     519              :           {
     520         8815 :             if (DECL_ARTIFICIAL (var))
     521              :               {
     522              :                 /* If we have an SSA name for an artificial var,
     523              :                    only use it if it has a debug expr associated with
     524              :                    it that fixup_tree_for_diagnostic can use.  */
     525          713 :                 if (VAR_P (var) && DECL_HAS_DEBUG_EXPR_P (var))
     526            0 :                   return readability (DECL_DEBUG_EXPR (var)) - 1;
     527              :               }
     528              :             else
     529              :               {
     530              :                 /* Slightly favor the underlying var over the SSA name to
     531              :                    avoid having them compare equal.  */
     532         8102 :                 return readability (var) - 1;
     533              :               }
     534              :           }
     535              :         /* Avoid printing '<unknown>' for SSA names for temporaries.  */
     536              :         return -1;
     537              :       }
     538        11321 :       break;
     539              : 
     540        11321 :     case PARM_DECL:
     541        11321 :     case VAR_DECL:
     542        11321 :       if (DECL_NAME (expr))
     543              :         return HIGH_READABILITY;
     544              :       else
     545              :         /* We don't want to print temporaries.  For example, the C FE
     546              :            prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
     547              :            of the tree pointer (see pp_c_tree_decl_identifier).  */
     548              :         return -1;
     549              : 
     550              :     case RESULT_DECL:
     551              :       /* Printing "<return-value>" isn't ideal, but is less awful than
     552              :          trying to print a temporary.  */
     553              :       return HIGH_READABILITY / 2;
     554              : 
     555         6873 :     case NOP_EXPR:
     556         6873 :       {
     557              :         /* Impose a moderate readability penalty for casts.  */
     558         6873 :         const int CAST_PENALTY = 32;
     559         6873 :         return readability (TREE_OPERAND (expr, 0)) - CAST_PENALTY;
     560              :       }
     561              : 
     562              :     case INTEGER_CST:
     563              :       return HIGH_READABILITY;
     564              : 
     565          380 :     default:
     566          380 :       return 0;
     567              :     }
     568              : 
     569              :   return 0;
     570              : }
     571              : 
     572              : /* A qsort comparator for trees to sort them into most user-readable to
     573              :    least user-readable.  */
     574              : 
     575              : int
     576        10001 : readability_comparator (const void *p1, const void *p2)
     577              : {
     578        10001 :   path_var pv1 = *(path_var const *)p1;
     579        10001 :   path_var pv2 = *(path_var const *)p2;
     580              : 
     581        10001 :   const int tree_r1 = readability (pv1.m_tree);
     582        10001 :   const int tree_r2 = readability (pv2.m_tree);
     583              : 
     584              :   /* Favor items that are deeper on the stack and hence more recent;
     585              :      this also favors locals over globals.  */
     586        10001 :   const int COST_PER_FRAME = 64;
     587        10001 :   const int depth_r1 = pv1.m_stack_depth * COST_PER_FRAME;
     588        10001 :   const int depth_r2 = pv2.m_stack_depth * COST_PER_FRAME;
     589              : 
     590              :   /* Combine the scores from the tree and from the stack depth.
     591              :      This e.g. lets us have a slightly penalized cast in the most
     592              :      recent stack frame "beat" an uncast value in an older stack frame.  */
     593        10001 :   const int sum_r1 = tree_r1 + depth_r1;
     594        10001 :   const int sum_r2 = tree_r2 + depth_r2;
     595        10001 :   if (int cmp = sum_r2 - sum_r1)
     596              :     return cmp;
     597              : 
     598              :   /* Otherwise, more readable trees win.  */
     599         1061 :   if (int cmp = tree_r2 - tree_r1)
     600              :     return cmp;
     601              : 
     602              :   /* Otherwise, if they have the same readability, then impose an
     603              :      arbitrary deterministic ordering on them.  */
     604              : 
     605         1061 :   if (int cmp = TREE_CODE (pv1.m_tree) - TREE_CODE (pv2.m_tree))
     606              :     return cmp;
     607              : 
     608          985 :   switch (TREE_CODE (pv1.m_tree))
     609              :     {
     610              :     default:
     611              :       break;
     612          529 :     case SSA_NAME:
     613          529 :       if (int cmp = (SSA_NAME_VERSION (pv1.m_tree)
     614          529 :                      - SSA_NAME_VERSION (pv2.m_tree)))
     615              :         return cmp;
     616              :       break;
     617            0 :     case PARM_DECL:
     618            0 :     case VAR_DECL:
     619            0 :     case RESULT_DECL:
     620            0 :       if (int cmp = DECL_UID (pv1.m_tree) - DECL_UID (pv2.m_tree))
     621              :         return cmp;
     622              :       break;
     623              :     }
     624              : 
     625              :   /* TODO: We ought to find ways of sorting such cases.  */
     626              :   return 0;
     627              : }
     628              : 
     629              : /* Return true is SNODE is the EXIT node of a function, or is one
     630              :    of the final snodes within its function.
     631              : 
     632              :    Specifically, handle the final supernodes before the EXIT node,
     633              :    for the case of clobbers that happen immediately before exiting.
     634              :    We need a run of snodes leading to the return_p snode, where all edges are
     635              :    intraprocedural, and every snode has just one successor.
     636              : 
     637              :    We use this when suppressing leak reports at the end of "main".  */
     638              : 
     639              : static bool
     640         1251 : returning_from_function_p (const supernode *snode)
     641              : {
     642         1251 :   if (!snode)
     643              :     return false;
     644              : 
     645              :   unsigned count = 0;
     646              :   const supernode *iter = snode;
     647         1965 :   while (true)
     648              :     {
     649         1965 :       if (iter->exit_p ())
     650              :         return true;
     651         1236 :       if (iter->m_succs.length () != 1)
     652              :         return false;
     653         1131 :       const superedge *sedge = iter->m_succs[0];
     654              : 
     655         1131 :       if (auto op = sedge->get_op ())
     656          988 :         if (op->get_kind () == operation::kind::return_stmt)
     657              :           return true;
     658              : 
     659          737 :       iter = sedge->m_dest;
     660              : 
     661              :       /* Impose a limit to ensure we terminate for pathological cases.
     662              : 
     663              :          We only care about the final 3 nodes, due to cases like:
     664              :            BB:
     665              :              (clobber causing leak)
     666              : 
     667              :            BB:
     668              :            <label>:
     669              :            return _val;
     670              : 
     671              :            EXIT BB.*/
     672          737 :       if (++count > 4)
     673              :         return false;
     674              :     }
     675              : }
     676              : 
     677              : /* Find the best tree for SVAL and call SM's on_leak vfunc with it.
     678              :    If on_leak returns a pending_diagnostic, queue it up to be reported,
     679              :    so that we potentially complain about a leak of SVAL in the given STATE.  */
     680              : 
     681              : void
     682         1251 : impl_region_model_context::on_state_leak (const state_machine &sm,
     683              :                                           const svalue *sval,
     684              :                                           state_machine::state_t state)
     685              : {
     686         1251 :   logger * const logger = get_logger ();
     687         1251 :   LOG_SCOPE (logger);
     688         1251 :   if (logger)
     689              :     {
     690            0 :       logger->start_log_line ();
     691            0 :       logger->log_partial ("considering leak of ");
     692            0 :       sval->dump_to_pp (logger->get_printer (), true);
     693            0 :       logger->end_log_line ();
     694              :     }
     695              : 
     696         1251 :   if (!m_eg)
     697              :     return;
     698              : 
     699              :   /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
     700              :      up the old state of SVAL.  */
     701         1251 :   gcc_assert (m_old_state);
     702              : 
     703              :   /* SVAL has leaked within the new state: it is not used by any reachable
     704              :      regions.
     705              :      We need to convert it back to a tree, but since it's likely no regions
     706              :      use it, we have to find the "best" tree for it in the old_state.  */
     707         1251 :   value_set visited;
     708         1251 :   path_var leaked_pv
     709         1251 :     = m_old_state->m_region_model->get_representative_path_var (sval,
     710              :                                                                 &visited,
     711              :                                                                 nullptr);
     712              : 
     713              :   /* Strip off top-level casts  */
     714         1251 :   if (leaked_pv.m_tree && TREE_CODE (leaked_pv.m_tree) == NOP_EXPR)
     715          458 :     leaked_pv.m_tree = TREE_OPERAND (leaked_pv.m_tree, 0);
     716              : 
     717              :   /* This might be NULL; the pending_diagnostic subclasses need to cope
     718              :      with this.  */
     719         1251 :   tree leaked_tree = leaked_pv.m_tree;
     720         1251 :   if (logger)
     721              :     {
     722            0 :       if (leaked_tree)
     723            0 :         logger->log ("best leaked_tree: %qE", leaked_tree);
     724              :       else
     725            0 :         logger->log ("best leaked_tree: NULL");
     726              :     }
     727              : 
     728         1251 :   gcc_assert (m_enode_for_diag);
     729              : 
     730              :   /* Don't complain about leaks when returning from "main".  */
     731         1251 :   if (returning_from_function_p (m_enode_for_diag->get_supernode ()))
     732              :     {
     733         1123 :       tree fndecl = m_enode_for_diag->get_function ()->decl;
     734         1123 :       if (id_equal (DECL_NAME (fndecl), "main"))
     735              :         {
     736           39 :           if (logger)
     737            0 :             logger->log ("not reporting leak from main");
     738           39 :           return;
     739              :         }
     740              :     }
     741              : 
     742         1212 :   tree leaked_tree_for_diag = fixup_tree_for_diagnostic (leaked_tree);
     743         1212 :   std::unique_ptr<pending_diagnostic> pd = sm.on_leak (leaked_tree_for_diag,
     744              :                                                        m_old_state,
     745         1212 :                                                        m_new_state);
     746         1212 :   if (pd)
     747              :     {
     748         1148 :       pending_location ploc (get_pending_location_for_diag ());
     749         1148 :       ploc.m_fixer_for_epath
     750         1148 :         = std::make_unique<leak_ploc_fixer_for_epath> (*m_eg, leaked_tree);
     751         1148 :       m_eg->get_diagnostic_manager ().add_diagnostic
     752         1148 :         (&sm, std::move (ploc),
     753              :          leaked_tree_for_diag, sval, state, std::move (pd));
     754         1148 :     }
     755         1251 : }
     756              : 
     757              : /* Implementation of region_model_context::on_condition vfunc.
     758              :    Notify all state machines about the condition, which could lead to
     759              :    state transitions.  */
     760              : 
     761              : void
     762        30617 : impl_region_model_context::on_condition (const svalue *lhs,
     763              :                                          enum tree_code op,
     764              :                                          const svalue *rhs)
     765              : {
     766        30617 :   int sm_idx;
     767        30617 :   sm_state_map *smap;
     768       244726 :   FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
     769              :     {
     770       214109 :       const state_machine &sm = m_ext_state.get_sm (sm_idx);
     771       428218 :       impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
     772              :                                m_old_state, m_new_state,
     773       428218 :                                m_old_state->m_checker_states[sm_idx],
     774       428218 :                                m_new_state->m_checker_states[sm_idx],
     775       214109 :                                m_path_ctxt);
     776       214109 :       sm.on_condition (sm_ctxt, lhs, op, rhs);
     777       214109 :     }
     778        30617 : }
     779              : 
     780              : /* Implementation of region_model_context::on_bounded_ranges vfunc.
     781              :    Notify all state machines about the ranges, which could lead to
     782              :    state transitions.  */
     783              : 
     784              : void
     785         5836 : impl_region_model_context::on_bounded_ranges (const svalue &sval,
     786              :                                               const bounded_ranges &ranges)
     787              : {
     788         5836 :   int sm_idx;
     789         5836 :   sm_state_map *smap;
     790        46688 :   FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
     791              :     {
     792        40852 :       const state_machine &sm = m_ext_state.get_sm (sm_idx);
     793        81704 :       impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
     794              :                                m_old_state, m_new_state,
     795        81704 :                                m_old_state->m_checker_states[sm_idx],
     796        81704 :                                m_new_state->m_checker_states[sm_idx],
     797        40852 :                                m_path_ctxt);
     798        40852 :       sm.on_bounded_ranges (sm_ctxt, sval, ranges);
     799        40852 :     }
     800         5836 : }
     801              : 
     802              : /* Implementation of region_model_context::on_pop_frame vfunc.
     803              :    Notify all state machines about the frame being popped, which
     804              :    could lead to states being discarded.  */
     805              : 
     806              : void
     807        27017 : impl_region_model_context::on_pop_frame (const frame_region *frame_reg)
     808              : {
     809        27017 :   int sm_idx;
     810        27017 :   sm_state_map *smap;
     811       215764 :   FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
     812              :     {
     813       188747 :       const state_machine &sm = m_ext_state.get_sm (sm_idx);
     814       188747 :       sm.on_pop_frame (smap, frame_reg);
     815              :     }
     816        27017 : }
     817              : 
     818              : /* Implementation of region_model_context::on_phi vfunc.
     819              :    Notify all state machines about the phi, which could lead to
     820              :    state transitions.  */
     821              : 
     822              : void
     823            0 : impl_region_model_context::on_phi (const gphi *phi, tree rhs)
     824              : {
     825            0 :   int sm_idx;
     826            0 :   sm_state_map *smap;
     827            0 :   FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
     828              :     {
     829            0 :       const state_machine &sm = m_ext_state.get_sm (sm_idx);
     830            0 :       impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
     831              :                                m_old_state, m_new_state,
     832            0 :                                m_old_state->m_checker_states[sm_idx],
     833            0 :                                m_new_state->m_checker_states[sm_idx],
     834            0 :                                m_path_ctxt);
     835            0 :       sm.on_phi (sm_ctxt, phi, rhs);
     836            0 :     }
     837            0 : }
     838              : 
     839              : /* Implementation of region_model_context::on_unexpected_tree_code vfunc.
     840              :    Mark the new state as being invalid for further exploration.
     841              :    TODO(stage1): introduce a warning for when this occurs.  */
     842              : 
     843              : void
     844           52 : impl_region_model_context::on_unexpected_tree_code (tree t,
     845              :                                                     const dump_location_t &loc)
     846              : {
     847           52 :   logger * const logger = get_logger ();
     848           52 :   if (logger)
     849              :     {
     850            2 :       const dump_impl_location_t &impl_loc = loc.get_impl_location ();
     851            2 :       const char *unknown = "<unknown>";
     852            2 :       logger->log ("unhandled tree code: %qs in %qs at %s:%i",
     853            2 :                    get_tree_code_name (TREE_CODE (t)),
     854            2 :                    impl_loc.m_function ? impl_loc.m_function : unknown,
     855            2 :                    impl_loc.m_file ? impl_loc.m_file : unknown,
     856            2 :                    impl_loc.m_line);
     857              :     }
     858           52 :   if (m_new_state)
     859           52 :     m_new_state->m_valid = false;
     860           52 : }
     861              : 
     862              : /* Implementation of region_model_context::maybe_did_work vfunc.
     863              :    Mark that "externally visible work" has occurred, and thus we
     864              :    shouldn't report an infinite loop here.  */
     865              : 
     866              : void
     867        24437 : impl_region_model_context::maybe_did_work ()
     868              : {
     869        24437 :   if (m_out_could_have_done_work)
     870        23972 :     *m_out_could_have_done_work = true;
     871        24437 : }
     872              : 
     873              : pending_location
     874         4520 : impl_region_model_context::get_pending_location_for_diag () const
     875              : {
     876         4520 :   if (m_stmt && useful_location_p (m_stmt->location))
     877         3342 :     return pending_location (m_enode_for_diag, m_stmt->location);
     878              :   else
     879         1178 :     return pending_location (m_enode_for_diag);
     880              : }
     881              : 
     882              : /* struct point_and_state.  */
     883              : 
     884              : /* Assert that this object is sane.  */
     885              : 
     886              : void
     887       747360 : point_and_state::validate (const extrinsic_state &ext_state) const
     888              : {
     889              :   /* Skip this in a release build.  */
     890              : #if !CHECKING_P
     891              :   return;
     892              : #endif
     893              : 
     894       747360 :   m_point.validate ();
     895              : 
     896       747360 :   m_state.validate (ext_state);
     897              : 
     898              :   /* Verify that the callstring's model of the stack corresponds to that
     899              :      of the region_model.  */
     900              :   /* They should have the same depth.  */
     901      1487578 :   gcc_assert (m_point.get_stack_depth ()
     902              :               == m_state.m_region_model->get_stack_depth ());
     903              :   /* Check the functions in the callstring vs those in the frames
     904              :      at each depth.  */
     905      1192937 :   for (const frame_region *iter_frame
     906       747360 :          = m_state.m_region_model->get_current_frame ();
     907      1940297 :        iter_frame; iter_frame = iter_frame->get_calling_frame ())
     908              :     {
     909      1192937 :       int index = iter_frame->get_index ();
     910      1192937 :       gcc_assert (m_point.get_function_at_depth (index)
     911              :                   == &iter_frame->get_function ());
     912              :     }
     913       747360 : }
     914              : 
     915              : /* Subroutine of print_enode_indices: print a run of indices from START_IDX
     916              :    to END_IDX to PP, using and updating *FIRST_RUN.  */
     917              : 
     918              : static void
     919         6745 : print_run (pretty_printer *pp, int start_idx, int end_idx,
     920              :            bool *first_run)
     921              : {
     922         6745 :   if (!(*first_run))
     923         4915 :     pp_string (pp, ", ");
     924         6745 :   *first_run = false;
     925         6745 :   if (start_idx == end_idx)
     926         5417 :     pp_printf (pp, "EN: %i", start_idx);
     927              :   else
     928         1328 :     pp_printf (pp, "EN: %i-%i", start_idx, end_idx);
     929         6745 : }
     930              : 
     931              : /* Print the indices within ENODES to PP, collecting them as
     932              :    runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42".  */
     933              : 
     934              : static void
     935         1842 : print_enode_indices (pretty_printer *pp,
     936              :                      const auto_vec<exploded_node *> &enodes)
     937              : {
     938         1842 :   int cur_start_idx = -1;
     939         1842 :   int cur_finish_idx = -1;
     940         1842 :   bool first_run = true;
     941         1842 :   unsigned i;
     942         1842 :   exploded_node *enode;
     943        11707 :   FOR_EACH_VEC_ELT (enodes, i, enode)
     944              :     {
     945         9865 :       if (cur_start_idx == -1)
     946              :         {
     947         1830 :           gcc_assert (cur_finish_idx == -1);
     948         1830 :           cur_start_idx = cur_finish_idx = enode->m_index;
     949              :         }
     950              :       else
     951              :         {
     952         8035 :           if (enode->m_index == cur_finish_idx + 1)
     953              :             /* Continuation of a run.  */
     954              :             cur_finish_idx = enode->m_index;
     955              :           else
     956              :             {
     957              :               /* Finish existing run, start a new one.  */
     958         4915 :               gcc_assert (cur_start_idx >= 0);
     959         4915 :               gcc_assert (cur_finish_idx >= 0);
     960         4915 :               print_run (pp, cur_start_idx, cur_finish_idx,
     961              :                          &first_run);
     962         4915 :               cur_start_idx = cur_finish_idx = enode->m_index;
     963              :             }
     964              :         }
     965              :     }
     966              :   /* Finish any existing run.  */
     967         1842 :   if (cur_start_idx >= 0)
     968              :     {
     969         1830 :       gcc_assert (cur_finish_idx >= 0);
     970         1830 :       print_run (pp, cur_start_idx, cur_finish_idx,
     971              :                  &first_run);
     972              :     }
     973         1842 : }
     974              : 
     975              : /* struct eg_traits::dump_args_t.  */
     976              : 
     977              : /* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
     978              :    full details for all enodes (both in terms of CPU time to render it,
     979              :    and in terms of being meaningful to a human viewing it).
     980              : 
     981              :    If we show just the IDs then the resulting graph is usually viewable,
     982              :    but then we have to keep switching back and forth between the .dot
     983              :    view and other dumps.
     984              : 
     985              :    This function implements a heuristic for showing detail at the enodes
     986              :    that (we hope) matter, and just the ID at other enodes, fixing the CPU
     987              :    usage of the .dot viewer, and drawing the attention of the viewer
     988              :    to these enodes.
     989              : 
     990              :    Return true if ENODE should be shown in detail in .dot output.
     991              :    Return false if no detail should be shown for ENODE.  */
     992              : 
     993              : bool
     994          515 : eg_traits::dump_args_t::show_enode_details_p (const exploded_node &enode) const
     995              : {
     996              :   /* If the number of exploded nodes isn't too large, we may as well show
     997              :      all enodes in full detail in the .dot output.  */
     998          515 :   if (m_eg.m_nodes.length ()
     999          515 :         <= (unsigned) param_analyzer_max_enodes_for_full_dump)
    1000              :     return true;
    1001              : 
    1002              :   /* Otherwise, assume that what's most interesting are state explosions,
    1003              :      and thus the places where this happened.
    1004              :      Expand enodes at program points where we hit the per-enode limit, so we
    1005              :      can investigate what exploded.  */
    1006            0 :   const per_program_point_data *per_point_data
    1007            0 :     = m_eg.get_per_program_point_data (enode.get_point ());
    1008            0 :   return per_point_data->m_excess_enodes > 0;
    1009              : }
    1010              : 
    1011              : /* class exploded_node : public dnode<eg_traits>.  */
    1012              : 
    1013              : const char *
    1014           15 : exploded_node::status_to_str (enum status s)
    1015              : {
    1016           15 :   switch (s)
    1017              :     {
    1018            0 :     default: gcc_unreachable ();
    1019              :     case status::worklist: return "worklist";
    1020           13 :     case status::processed: return "processed";
    1021            0 :     case status::special: return "special";
    1022            0 :     case status::merger: return "merger";
    1023            2 :     case status::bulk_merged: return "bulk_merged";
    1024              :     }
    1025              : }
    1026              : 
    1027              : /* exploded_node's ctor.  */
    1028              : 
    1029            0 : exploded_node::exploded_node (const point_and_state &ps,
    1030              :                               int index)
    1031            0 : : m_ps (ps), m_status (status::worklist), m_index (index)
    1032              : {
    1033            0 :   gcc_checking_assert (m_ps.get_state ().m_region_model->canonicalized_p ());
    1034            0 : }
    1035              : 
    1036       371189 : exploded_node::exploded_node (point_and_state &&ps,
    1037              :                               int index)
    1038       371189 : : m_ps (std::move (ps)), m_status (status::worklist), m_index (index)
    1039              : {
    1040       371189 :   gcc_checking_assert (m_ps.get_state ().m_region_model->canonicalized_p ());
    1041       371189 : }
    1042              : 
    1043              : /* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
    1044              :    Colorize by sm-state, to make it easier to see how sm-state propagates
    1045              :    through the exploded_graph.  */
    1046              : 
    1047              : const char *
    1048         1030 : exploded_node::get_dot_fillcolor () const
    1049              : {
    1050         1030 :   const program_state &state = get_state ();
    1051              : 
    1052              :   /* We want to be able to easily distinguish the no-sm-state case,
    1053              :      and to be able to distinguish cases where there's a single state
    1054              :      from each other.
    1055              : 
    1056              :      Sum the sm_states, and use the result to choose from a table,
    1057              :      modulo table-size, special-casing the "no sm-state" case.   */
    1058         1030 :   int total_sm_state = 0;
    1059         1030 :   int i;
    1060         1030 :   sm_state_map *smap;
    1061         8240 :   FOR_EACH_VEC_ELT (state.m_checker_states, i, smap)
    1062              :     {
    1063         8594 :       for (sm_state_map::iterator_t iter = smap->begin ();
    1064         8594 :            iter != smap->end ();
    1065         1384 :            ++iter)
    1066         1384 :         total_sm_state += (*iter).second.m_state->get_id ();
    1067         7210 :       total_sm_state += smap->get_global_state ()->get_id ();
    1068              :     }
    1069              : 
    1070         1030 :   if (total_sm_state > 0)
    1071              :     {
    1072              :       /* An arbitrarily-picked collection of light colors.  */
    1073          768 :       const char * const colors[]
    1074              :         = {"azure", "coral", "cornsilk", "lightblue", "yellow",
    1075              :            "honeydew", "lightpink", "lightsalmon", "palegreen1",
    1076              :            "wheat", "seashell"};
    1077          768 :       const int num_colors = ARRAY_SIZE (colors);
    1078          768 :       return colors[total_sm_state % num_colors];
    1079              :     }
    1080              :   else
    1081              :     /* No sm-state.   */
    1082              :     return "lightgrey";
    1083              : }
    1084              : 
    1085              : /* Implementation of dnode::dump_dot vfunc for exploded_node.  */
    1086              : 
    1087              : void
    1088          515 : exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
    1089              : {
    1090          515 :   pretty_printer *pp = gv->get_pp ();
    1091              : 
    1092          515 :   dump_dot_id (pp);
    1093          515 :   pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,fontname=\"Monospace\",label=\"",
    1094              :              get_dot_fillcolor ());
    1095          515 :   pp_write_text_to_stream (pp);
    1096              : 
    1097          515 :   pp_printf (pp, "EN: %i", m_index);
    1098          515 :   if (m_status == status::merger)
    1099           12 :     pp_string (pp, " (merger)");
    1100          503 :   else if (m_status == status::bulk_merged)
    1101            0 :     pp_string (pp, " (bulk merged)");
    1102          515 :   pp_newline (pp);
    1103              : 
    1104          515 :   if (args.show_enode_details_p (*this))
    1105              :     {
    1106          515 :       format f (true);
    1107          515 :       m_ps.get_point ().print (pp, f);
    1108          515 :       pp_newline (pp);
    1109              : 
    1110          515 :       bool show_state = true;
    1111              : 
    1112              :       /* Don't show the state if we have a single predecessor
    1113              :          and the state hasn't changed.  */
    1114          515 :       if (m_preds.length () == 1
    1115          507 :           && get_state () == m_preds[0]->m_src->get_state ())
    1116          118 :         show_state = false;
    1117              : 
    1118          515 :       if (show_state)
    1119              :         {
    1120          397 :           const program_state &state = m_ps.get_state ();
    1121          397 :           text_art::theme *theme = global_dc->get_diagram_theme ();
    1122          397 :           symbolic::dump_node_tree_to_pp (state, theme, pp, true, true);
    1123          397 :           pp_newline (pp);
    1124              :         }
    1125              :       else
    1126              :         {
    1127          118 :           pp_string (pp, "(same state as predecessor)");
    1128          118 :           pp_newline (pp);
    1129              :         }
    1130              :     }
    1131              : 
    1132          515 :   dump_saved_diagnostics (pp);
    1133              : 
    1134          515 :   args.dump_extra_info (this, pp);
    1135              : 
    1136          515 :   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
    1137              : 
    1138          515 :   pp_string (pp, "\"];\n\n");
    1139              : 
    1140              :   /* It can be hard to locate the saved diagnostics as text within the
    1141              :      enode nodes, so add extra nodes to the graph for each saved_diagnostic,
    1142              :      highlighted in red.
    1143              :      Compare with dump_saved_diagnostics.  */
    1144          515 :   {
    1145          515 :     unsigned i;
    1146          515 :     const saved_diagnostic *sd;
    1147         1038 :     FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
    1148              :       {
    1149            8 :         sd->dump_as_dot_node (pp);
    1150              : 
    1151              :         /* Add edge connecting this enode to the saved_diagnostic.  */
    1152            8 :         dump_dot_id (pp);
    1153            8 :         pp_string (pp, " -> ");
    1154            8 :         sd->dump_dot_id (pp);
    1155            8 :         pp_string (pp, " [style=\"dotted\" arrowhead=\"none\"];");
    1156            8 :         pp_newline (pp);
    1157              :       }
    1158              :   }
    1159              : 
    1160          515 :   pp_flush (pp);
    1161          515 : }
    1162              : 
    1163              : /* Dump any saved_diagnostics at this enode to PP.  */
    1164              : 
    1165              : void
    1166          589 : exploded_node::dump_saved_diagnostics (pretty_printer *pp) const
    1167              : {
    1168          589 :   unsigned i;
    1169          589 :   const saved_diagnostic *sd;
    1170          601 :   FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
    1171              :     {
    1172           12 :       pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)",
    1173           12 :                  sd->m_d->get_kind (), sd->get_index ());
    1174           12 :       pp_newline (pp);
    1175              :     }
    1176          589 : }
    1177              : 
    1178              : /* Dump this to PP in a form suitable for use as an id in .dot output.  */
    1179              : 
    1180              : void
    1181         1584 : exploded_node::dump_dot_id (pretty_printer *pp) const
    1182              : {
    1183         1584 :   pp_printf (pp, "exploded_node_%i", m_index);
    1184         1584 : }
    1185              : 
    1186              : /* Dump a tree-like representation of this exploded_node to stderr.  */
    1187              : 
    1188              : DEBUG_FUNCTION void
    1189            0 : exploded_node::dump () const
    1190              : {
    1191            0 :   symbolic::dump_node_tree_to_stderr<exploded_node> (*this);
    1192            0 : }
    1193              : 
    1194              : /* Dump a tree-like representation of this exploded_node to PP.  */
    1195              : 
    1196              : void
    1197            0 : exploded_node::dump_to_pp (pretty_printer *pp) const
    1198              : {
    1199            0 :   text_art::theme *theme = global_dc->get_diagram_theme ();
    1200            0 :   symbolic::dump_node_tree_to_pp<exploded_node> (*this, theme, pp, true, true);
    1201            0 : }
    1202              : 
    1203              : /* Dump a tree-like representation of this exploded_node to LOG.  */
    1204              : 
    1205              : void
    1206            0 : exploded_node::dump_to_logger (logger &log) const
    1207              : {
    1208            0 :   symbolic::dump_node_tree_to_logger<exploded_node> (*this, log);
    1209            0 : }
    1210              : 
    1211              : std::unique_ptr<text_art::tree_widget>
    1212            0 : exploded_node::make_dump_widget (symbolic::node_dump_state &nds) const
    1213              : {
    1214            0 :   pretty_printer pp;
    1215            0 :   pp_printf (&pp, "EN: %i", m_index);
    1216            0 :   std::unique_ptr<text_art::tree_widget> w
    1217            0 :     (text_art::tree_widget::make (nds, &pp));
    1218              : 
    1219            0 :   w->add_child (m_ps.get_point ().make_dump_widget (nds));
    1220            0 :   w->add_child (m_ps.get_state ().make_dump_widget (nds));
    1221              : 
    1222            0 :   return w;
    1223            0 : }
    1224              : 
    1225              : /* Return a new json::object of the form
    1226              :    {"point"  : object for program_point,
    1227              :     "state"  : object for program_state,
    1228              :     "status" : str,
    1229              :     "idx"    : int}.  */
    1230              : 
    1231              : std::unique_ptr<json::object>
    1232            0 : exploded_node::to_json (const extrinsic_state &ext_state) const
    1233              : {
    1234            0 :   auto enode_obj = std::make_unique<json::object> ();
    1235              : 
    1236            0 :   enode_obj->set ("point", get_point ().to_json ());
    1237            0 :   enode_obj->set ("state", get_state ().to_json (ext_state));
    1238            0 :   enode_obj->set_string ("status", status_to_str (m_status));
    1239            0 :   enode_obj->set_integer ("idx", m_index);
    1240              : 
    1241            0 :   return enode_obj;
    1242              : }
    1243              : 
    1244              : } // namespace ana
    1245              : 
    1246              : /* Return true if FNDECL has a gimple body.  */
    1247              : // TODO: is there a pre-canned way to do this?
    1248              : 
    1249              : bool
    1250        17617 : fndecl_has_gimple_body_p (tree fndecl)
    1251              : {
    1252        17617 :   if (fndecl == NULL_TREE)
    1253              :     return false;
    1254              : 
    1255        17617 :   cgraph_node *n = cgraph_node::get (fndecl);
    1256        17617 :   if (!n)
    1257              :     return false;
    1258              : 
    1259        17617 :   return n->has_gimple_body_p ();
    1260              : }
    1261              : 
    1262              : namespace ana {
    1263              : 
    1264              : /* Subclass of call_info for exploded edges that express
    1265              :    a throw or rethrow of an exception (actually a call
    1266              :    to __cxa_throw or __cxa_rethrow).  */
    1267              : 
    1268              : class throw_custom_edge : public call_info
    1269              : {
    1270              : public:
    1271          224 :   throw_custom_edge (const call_details &cd,
    1272              :                      tree type,
    1273              :                      bool is_rethrow)
    1274              :   : call_info (cd),
    1275          224 :     m_type (type),
    1276          224 :     m_is_rethrow (is_rethrow)
    1277              :   {
    1278              :   }
    1279              : 
    1280            0 :   void print (pretty_printer *pp) const final override
    1281              :   {
    1282            0 :     if (m_is_rethrow)
    1283              :       {
    1284            0 :         if (m_type)
    1285            0 :           pp_printf (pp, "rethrowing %qT", m_type);
    1286              :         else
    1287            0 :           pp_printf (pp, "rethrowing");
    1288              :       }
    1289              :     else
    1290              :       {
    1291            0 :         if (m_type)
    1292            0 :           pp_printf (pp, "throwing %qT", m_type);
    1293              :         else
    1294            0 :           pp_printf (pp, "throwing");
    1295              :       }
    1296            0 :   }
    1297              : 
    1298            0 :   void print_desc (pretty_printer &pp) const final override
    1299              :   {
    1300            0 :     print (&pp);
    1301            0 :   }
    1302              : 
    1303          422 :   bool update_model (region_model *model,
    1304              :                      const exploded_edge *,
    1305              :                      region_model_context *ctxt) const final override
    1306              :   {
    1307          422 :     if (m_is_rethrow)
    1308              :       {
    1309          117 :         if (auto eh_node = model->get_current_caught_exception ())
    1310           84 :           model->push_thrown_exception (*eh_node);
    1311              :         else
    1312              :           {
    1313              :             /* We have a rethrow of some unknown exception.
    1314              :                We don't have a good way of representing this;
    1315              :                leave the exception stack empty.  */
    1316              :           }
    1317              :       }
    1318              :     else
    1319              :       {
    1320          305 :         call_details cd (get_call_details (model, ctxt));
    1321              : 
    1322          305 :         const svalue *exception_sval = cd.get_arg_svalue (0);
    1323          305 :         const svalue *tinfo_sval = cd.get_arg_svalue (1);
    1324          305 :         const svalue *destructor_sval = cd.get_arg_svalue (2);
    1325              : 
    1326              :         /* Push a new exception_node on the model's m_exception_stack.  */
    1327          305 :         exception_node eh_node (exception_sval, tinfo_sval, destructor_sval);
    1328          305 :         model->push_thrown_exception (eh_node);
    1329              :       }
    1330              : 
    1331          422 :     return true;
    1332              :   }
    1333              : 
    1334           90 :   void add_events_to_path (checker_path *emission_path,
    1335              :                            const exploded_edge &eedge,
    1336              :                            pending_diagnostic &,
    1337              :                            const state_transition *) const final override
    1338              :   {
    1339           90 :     const exploded_node *dst_node = eedge.m_dest;
    1340           90 :     const program_point &dst_point = dst_node->get_point ();
    1341           90 :     const int dst_stack_depth = dst_point.get_stack_depth ();
    1342              : 
    1343           90 :     const gcall &call = get_call_stmt ();
    1344              : 
    1345           90 :     emission_path->add_event
    1346           90 :       (std::make_unique<explicit_throw_event>
    1347           90 :          (event_loc_info (call.location,
    1348              :                           dst_point.get_fndecl (),
    1349           90 :                           dst_stack_depth),
    1350              :           dst_node,
    1351              :           call,
    1352           90 :           m_type,
    1353           90 :           m_is_rethrow));
    1354           90 :   }
    1355              : 
    1356              : private:
    1357              :   tree m_type;
    1358              :   bool m_is_rethrow;
    1359              : };
    1360              : 
    1361              : /* Subclass of custom_edge_info for an exploded edge that expresses
    1362              :    unwinding one stack frame during exception handling.  */
    1363              : 
    1364              : class unwind_custom_edge : public custom_edge_info
    1365              : {
    1366              : public:
    1367         6631 :   unwind_custom_edge (location_t loc)
    1368         6631 :   : m_loc (loc)
    1369              :   {
    1370              :   }
    1371              : 
    1372            0 :   void print (pretty_printer *pp) const final override
    1373              :   {
    1374            0 :     pp_printf (pp, "unwinding frame");
    1375            0 :   }
    1376              : 
    1377         6663 :   bool update_model (region_model *model,
    1378              :                      const exploded_edge *,
    1379              :                      region_model_context *ctxt) const final override
    1380              :   {
    1381         6663 :     model->pop_frame (NULL_TREE, nullptr, ctxt, nullptr, false);
    1382         6663 :     return true;
    1383              :   }
    1384              : 
    1385           16 :   void add_events_to_path (checker_path *emission_path,
    1386              :                            const exploded_edge &eedge,
    1387              :                            pending_diagnostic &,
    1388              :                            const state_transition *) const final override
    1389              :   {
    1390           16 :     const exploded_node *src_node = eedge.m_src;
    1391           16 :     const program_point &src_point = src_node->get_point ();
    1392           16 :     const int src_stack_depth = src_point.get_stack_depth ();
    1393           16 :     emission_path->add_event
    1394           32 :       (std::make_unique<unwind_event> (event_loc_info (m_loc,
    1395              :                                                        src_point.get_fndecl (),
    1396           16 :                                                        src_stack_depth)));
    1397           16 :   }
    1398              : 
    1399              : private:
    1400              :   location_t m_loc;
    1401              : };
    1402              : 
    1403              : /* Locate an SNODE that's a CFG edge with the EH flag,
    1404              :    or return nullptr. */
    1405              : 
    1406              : static const superedge *
    1407         7565 : get_eh_outedge (const supernode &snode)
    1408              : {
    1409        27299 :   for (auto out_sedge : snode.m_succs)
    1410         6926 :     if (::edge cfg_edge = out_sedge->get_any_cfg_edge ())
    1411         1385 :       if (cfg_edge->flags & EDGE_EH)
    1412              :         return out_sedge;
    1413              : 
    1414              :   // Not found
    1415              :   return nullptr;
    1416              : }
    1417              : 
    1418              : /* Given THROWN_ENODE, which expresses a throw or rethrow occurring at
    1419              :    THROW_STMT, unwind intraprocedurally and interprocedurally to find
    1420              :    the next eh_dispatch statement to handle exceptions, if any.
    1421              : 
    1422              :    Add eedges and enodes to this graph expressing the actions taken
    1423              :    to reach an enode containing the eh_dispatch stmt, if any.
    1424              :    Only the final enode is added to this graph's worklist.
    1425              : 
    1426              :    Use CTXT to warn about problems e.g. memory leaks due to stack frames
    1427              :    being unwound.  */
    1428              : 
    1429              : void
    1430         6301 : exploded_graph::unwind_from_exception (exploded_node &thrown_enode,
    1431              :                                        const gimple *throw_stmt,
    1432              :                                        region_model_context *ctxt)
    1433              : {
    1434         6301 :   logger * const logger = get_logger ();
    1435         6301 :   LOG_FUNC_1 (logger, "thrown EN: %i", thrown_enode.m_index);
    1436              : 
    1437              :   /* Iteratively unwind the stack looking for an out-cfg-edge
    1438              :      flagged EH.  */
    1439         6301 :   exploded_node *iter_enode = &thrown_enode;
    1440         6301 :   while (iter_enode)
    1441              :     {
    1442              :       /* If we have an out-cfg-edge flagged EH, follow that,
    1443              :          presumably to a bb with a label and an eh_dispatch stmt.
    1444              :          Otherwise assume no out-cfgs-edges, and we are unwinding to the
    1445              :          caller.  */
    1446         7565 :       if (auto sedge = get_eh_outedge (*iter_enode->get_supernode ()))
    1447              :         {
    1448              :           /* Intraprocedural case.
    1449              :              Assume we have an out-edge flagged with EH leading to
    1450              :              code for dispatch to catch handlers.  */
    1451          934 :           const program_point next_point
    1452          934 :             (sedge->m_dest,
    1453          934 :              iter_enode->get_point ().get_call_string ());
    1454          934 :           exploded_node *next_enode
    1455          934 :             = get_or_create_node (next_point,
    1456              :                                   iter_enode->get_state (),
    1457              :                                   iter_enode,
    1458              :                                   /* Add this enode to the worklist.  */
    1459              :                                   true);
    1460          934 :           if (!next_enode)
    1461              :             return;
    1462              : 
    1463          934 :           add_edge (iter_enode, next_enode, nullptr, false, nullptr);
    1464          934 :           return;
    1465              :         }
    1466              :       else
    1467              :         {
    1468              :           /* Interprocedural case.
    1469              :              No out-cfg-edge.  Unwind one stack frame.  */
    1470         6631 :           program_state unwound_state (iter_enode->get_state ());
    1471         6631 :           location_t loc = throw_stmt ? throw_stmt->location : UNKNOWN_LOCATION;
    1472         6631 :           auto unwind_edge_info
    1473         6631 :             = std::make_unique<unwind_custom_edge> (loc);
    1474         6631 :           unwind_edge_info->update_model (unwound_state.m_region_model, nullptr,
    1475              :                                           ctxt);
    1476              : 
    1477              :           /* Detect leaks in the new state relative to the old state.
    1478              :              Use an alternate ctxt that uses the original enode and the stmt
    1479              :              (if any) for the location of any diagnostics.  */
    1480         6631 :           {
    1481         6631 :             uncertainty_t uncertainty;
    1482         6631 :             impl_region_model_context ctxt (*this,
    1483              :                                             &thrown_enode,
    1484         6631 :                                             &iter_enode->get_state (),
    1485              :                                             &unwound_state,
    1486              :                                             &uncertainty,
    1487              :                                             nullptr,
    1488         6631 :                                             throw_stmt);
    1489         6631 :             program_state::detect_leaks (iter_enode->get_state (),
    1490              :                                          unwound_state,
    1491              :                                          nullptr,
    1492              :                                          get_ext_state (), &ctxt);
    1493         6631 :           }
    1494         6631 :           const call_string &cs = iter_enode->get_point ().get_call_string ();
    1495         6631 :           if (cs.empty_p ())
    1496              :             {
    1497              :               /* Top-level stack frame in analysis: unwinding
    1498              :                  to the outside world that called us.  */
    1499              :               return;
    1500              :             }
    1501              :           else
    1502              :             {
    1503              :               /* Nested function in analysis: unwinding to
    1504              :                  the callsite in the analysis (or beyond).  */
    1505         1671 :               program_point unwound_point (cs.get_return_node_in_caller (), cs);
    1506         1671 :               unwound_point.pop_from_call_stack ();
    1507              : 
    1508         1671 :               exploded_node *after_unwind_enode
    1509         1671 :                 = get_or_create_node (unwound_point,
    1510              :                                       unwound_state,
    1511              :                                       iter_enode,
    1512              :                                       /* Don't add this enode to the
    1513              :                                          worklist; we will process it
    1514              :                                          on the next iteration.  */
    1515              :                                       false);
    1516              : 
    1517         1671 :               if (!after_unwind_enode)
    1518          407 :                 return;
    1519              : 
    1520         1264 :               add_edge (iter_enode, after_unwind_enode, nullptr, true,
    1521         1264 :                         std::move (unwind_edge_info));
    1522         1264 :               iter_enode = after_unwind_enode;
    1523              :             }
    1524         6631 :         }
    1525              :     }
    1526         6301 : }
    1527              : 
    1528              : /* Handle THROW_CALL, a call to __cxa_throw or __cxa_rethrow.
    1529              : 
    1530              :    Create an eedge and destination enode for the throw/rethrow, adding
    1531              :    them to this egraph.  The new enode isn't added to the worklist, but
    1532              :    instead exploded_graph::unwind_from_exception is immediately called
    1533              :    on it, potentially creating more eedges and enodes leading to an
    1534              :    eh_handler stmt.  */
    1535              : 
    1536              : void
    1537          227 : exploded_node::on_throw (exploded_graph &eg,
    1538              :                          const gcall &throw_call,
    1539              :                          const program_point &after_throw_point,
    1540              :                          program_state *new_state,
    1541              :                          bool is_rethrow,
    1542              :                          region_model_context *ctxt)
    1543              : {
    1544          227 :   region_model *model = new_state->m_region_model;
    1545          227 :   call_details cd (throw_call, model, ctxt);
    1546              : 
    1547          227 :   if (!cd.get_fndecl_for_call ())
    1548            3 :     return;
    1549              : 
    1550              :   /* Create an enode and eedge for the "throw".  */
    1551          224 :   tree type = NULL_TREE;
    1552          224 :   if (is_rethrow)
    1553              :     {
    1554           81 :       const exception_node *eh_node = model->get_current_caught_exception ();
    1555           66 :       if (eh_node)
    1556           66 :         type = eh_node->maybe_get_type ();
    1557              :       else
    1558              :         {
    1559              :           /* We have a "throw;" but no exception to rethrow.
    1560              :              Presumably the top-level of the analysis is an
    1561              :              entrypoint for handling exceptions, so we will
    1562              :              simulate fully unwinding.  */
    1563              :         }
    1564              :     }
    1565              :   else
    1566              :     {
    1567          143 :       const svalue *tinfo_sval = cd.get_arg_svalue (1);
    1568          143 :       type = tinfo_sval->maybe_get_type_from_typeinfo ();
    1569              :     }
    1570              : 
    1571          224 :   auto throw_edge_info
    1572          224 :     = std::make_unique<throw_custom_edge> (cd, type, is_rethrow);
    1573          224 :   throw_edge_info->update_model (model, nullptr, ctxt);
    1574              : 
    1575          224 :   exploded_node *after_throw_enode
    1576          224 :     = eg.get_or_create_node (after_throw_point, *new_state, this,
    1577              :                              /* Don't add to worklist; we process
    1578              :                                 this immediately below.  */
    1579              :                              false);
    1580              : 
    1581          224 :   if (!after_throw_enode)
    1582            0 :     return;
    1583              : 
    1584              :   /* Create custom exploded_edge for a throw.  */
    1585          224 :   eg.add_edge (this, after_throw_enode, nullptr, true,
    1586          224 :                std::move (throw_edge_info));
    1587              : 
    1588          224 :   eg.unwind_from_exception (*after_throw_enode, &throw_call, ctxt);
    1589          224 : }
    1590              : 
    1591              : /* Subroutine of exploded_graph::process_node for finding the successors
    1592              :    of the supernode for a function exit basic block.
    1593              : 
    1594              :    Ensure that pop_frame is called, potentially queuing diagnostics about
    1595              :    leaks.  */
    1596              : 
    1597              : void
    1598        12171 : exploded_node::detect_leaks (exploded_graph &eg)
    1599              : {
    1600        12171 :   LOG_FUNC_1 (eg.get_logger (), "EN: %i", m_index);
    1601              : 
    1602        12171 :   gcc_assert (get_point ().get_supernode ()->exit_p ());
    1603              : 
    1604              :   /* If we're not a "top-level" function, do nothing; pop_frame
    1605              :      will be called when handling the return superedge.  */
    1606        12171 :   if (get_point ().get_stack_depth () > 1)
    1607            0 :     return;
    1608              : 
    1609              :   /* We have a "top-level" function.  */
    1610        12171 :   gcc_assert (get_point ().get_stack_depth () == 1);
    1611              : 
    1612        12171 :   const program_state &old_state = get_state ();
    1613              : 
    1614              :   /* Work with a temporary copy of the state: pop the frame, and see
    1615              :      what leaks (via purge_unused_svalues).  */
    1616        12171 :   program_state new_state (old_state);
    1617              : 
    1618        12171 :   gcc_assert (new_state.m_region_model);
    1619              : 
    1620        12171 :   uncertainty_t uncertainty;
    1621        12171 :   impl_region_model_context ctxt (eg, this,
    1622              :                                   &old_state, &new_state, &uncertainty, nullptr,
    1623        12171 :                                   nullptr);
    1624        12171 :   const svalue *result = nullptr;
    1625        12171 :   new_state.m_region_model->pop_frame (nullptr, &result, &ctxt, nullptr);
    1626        12171 :   program_state::detect_leaks (old_state, new_state, result,
    1627              :                                eg.get_ext_state (), &ctxt);
    1628        24342 : }
    1629              : 
    1630              : /* Dump the successors and predecessors of this enode to OUTF.  */
    1631              : 
    1632              : void
    1633            0 : exploded_node::dump_succs_and_preds (FILE *outf) const
    1634              : {
    1635            0 :   unsigned i;
    1636            0 :   exploded_edge *e;
    1637            0 :   {
    1638            0 :     auto_vec<exploded_node *> preds (m_preds.length ());
    1639            0 :     FOR_EACH_VEC_ELT (m_preds, i, e)
    1640            0 :       preds.quick_push (e->m_src);
    1641            0 :     pretty_printer pp;
    1642            0 :     print_enode_indices (&pp, preds);
    1643            0 :     fprintf (outf, "preds: %s\n",
    1644              :              pp_formatted_text (&pp));
    1645            0 :   }
    1646            0 :   {
    1647            0 :     auto_vec<exploded_node *> succs (m_succs.length ());
    1648            0 :     FOR_EACH_VEC_ELT (m_succs, i, e)
    1649            0 :       succs.quick_push (e->m_dest);
    1650            0 :     pretty_printer pp;
    1651            0 :     print_enode_indices (&pp, succs);
    1652            0 :     fprintf (outf, "succs: %s\n",
    1653              :              pp_formatted_text (&pp));
    1654            0 :   }
    1655            0 : }
    1656              : 
    1657              : // class interprocedural_call : public custom_edge_info
    1658              : 
    1659              : void
    1660            8 : interprocedural_call::print (pretty_printer *pp) const
    1661              : {
    1662            8 :   pp_string (pp, "call to ");
    1663            8 :   pp_gimple_stmt_1 (pp, &get_gcall (), 0, (dump_flags_t)0);
    1664            8 : }
    1665              : 
    1666              : void
    1667            8 : interprocedural_call::get_dot_attrs (const char *&/*out_style*/,
    1668              :                                      const char *&out_color) const
    1669              : {
    1670            8 :   out_color = "red";
    1671            8 : }
    1672              : 
    1673              : bool
    1674         9577 : interprocedural_call::update_state (program_state *state,
    1675              :                                     const exploded_edge *eedge,
    1676              :                                     region_model_context *ctxt) const
    1677              : {
    1678         9577 :   return update_model (state->m_region_model, eedge, ctxt);
    1679              : }
    1680              : 
    1681              : bool
    1682        14799 : interprocedural_call::update_model (region_model *model,
    1683              :                                     const exploded_edge */*eedge*/,
    1684              :                                     region_model_context *ctxt) const
    1685              : {
    1686        14799 :   model->update_for_gcall (get_gcall (), ctxt, &m_callee_fun);
    1687        14799 :   return true;
    1688              : }
    1689              : 
    1690              : void
    1691         1397 : interprocedural_call::add_events_to_path (checker_path *emission_path,
    1692              :                                           const exploded_edge &eedge,
    1693              :                                           pending_diagnostic &pd,
    1694              :                                           const state_transition *state_trans) const
    1695              : {
    1696         1420 :   pd.add_call_event (eedge, get_gcall (), *emission_path,
    1697              :                      (state_trans
    1698           23 :                       ? state_trans->dyn_cast_state_transition_at_call ()
    1699              :                       : nullptr));
    1700         1397 : }
    1701              : 
    1702              : bool
    1703         1292 : interprocedural_call::try_to_rewind_data_flow (rewind_context &ctxt) const
    1704              : {
    1705         1292 :   auto logger = ctxt.m_logger;
    1706              : 
    1707              :   // Rewind from params to arguments
    1708         1292 :   if (ctxt.m_input.m_region_holding_value)
    1709              :     {
    1710           58 :       const region_model &dst_enode_model = ctxt.get_dst_region_model ();
    1711           58 :       tree dst_tree
    1712              :         = dst_enode_model.get_representative_tree
    1713           58 :             (ctxt.m_input.m_region_holding_value);
    1714           58 :       if (dst_tree)
    1715              :         {
    1716           52 :           callsite_expr expr;
    1717           52 :           tree src_tree
    1718           52 :             = m_op.map_expr_from_callee_to_caller (m_callee_fun.decl,
    1719              :                                                    dst_tree,
    1720              :                                                    &expr);
    1721           52 :           if (src_tree)
    1722              :             {
    1723           23 :               const region_model &src_enode_model = ctxt.get_src_region_model ();
    1724           23 :               ctxt.m_output.m_region_holding_value
    1725           23 :                 = src_enode_model.get_lvalue (src_tree, nullptr);
    1726              : 
    1727           23 :               ctxt.add_state_transition
    1728           23 :                 (std::make_unique<state_transition_at_call> (expr));
    1729              : 
    1730           23 :               if (logger)
    1731              :                 {
    1732            0 :                   callsite_expr_element e (expr);
    1733            0 :                   logger->log ("updating m_region_holding_value from %qE to %qE"
    1734              :                                " (callsite_expr: %e)",
    1735              :                                dst_tree, src_tree, &e);
    1736            0 :                 }
    1737              :             }
    1738              :         }
    1739              :     }
    1740              : 
    1741         1292 :   return true;
    1742              : }
    1743              : 
    1744              : const gcall &
    1745        16204 : interprocedural_call::get_gcall () const
    1746              : {
    1747        16204 :   return m_op.get_gcall ();
    1748              : }
    1749              : 
    1750              : // class interprocedural_return : public custom_edge_info
    1751              : 
    1752              : void
    1753           16 : interprocedural_return::print (pretty_printer *pp) const
    1754              : {
    1755           16 :   pp_string (pp, "return from ");
    1756           16 :   pp_gimple_stmt_1 (pp, &m_call_stmt, 0, (dump_flags_t)0);
    1757           16 : }
    1758              : 
    1759              : void
    1760            8 : interprocedural_return::get_dot_attrs (const char *&/*out_style*/,
    1761              :                                        const char *&out_color) const
    1762              : {
    1763            8 :   out_color = "green";
    1764            8 : }
    1765              : 
    1766              : bool
    1767         8193 : interprocedural_return::update_state (program_state *state,
    1768              :                                       const exploded_edge *eedge,
    1769              :                                       region_model_context *ctxt) const
    1770              : {
    1771         8193 :   return update_model (state->m_region_model, eedge, ctxt);
    1772              : }
    1773              : 
    1774              : bool
    1775        11050 : interprocedural_return::update_model (region_model *model,
    1776              :                                       const exploded_edge */*eedge*/,
    1777              :                                       region_model_context *ctxt) const
    1778              : {
    1779        11050 :   model->update_for_return_gcall (m_call_stmt, ctxt);
    1780        11050 :   return true;
    1781              : }
    1782              : 
    1783              : void
    1784          818 : interprocedural_return::add_events_to_path (checker_path *emission_path,
    1785              :                                             const exploded_edge &eedge,
    1786              :                                             pending_diagnostic &,
    1787              :                                             const state_transition *state_trans) const
    1788              : {
    1789          818 :   const program_point &dst_point = eedge.m_dest->get_point ();
    1790          818 :   emission_path->add_event
    1791          818 :     (std::make_unique<return_event>
    1792          818 :        (eedge,
    1793         1636 :         event_loc_info (m_call_stmt.location,
    1794              :                         dst_point.get_fndecl (),
    1795         1636 :                         dst_point.get_stack_depth ()),
    1796              :         (state_trans
    1797          818 :          ? state_trans->dyn_cast_state_transition_at_return ()
    1798              :          : nullptr)));
    1799          818 : }
    1800              : 
    1801              : bool
    1802          778 : interprocedural_return::try_to_rewind_data_flow (rewind_context &ctxt) const
    1803              : {
    1804          778 :   auto logger = ctxt.m_logger;
    1805              : 
    1806          778 :   tree lhs = gimple_call_lhs (&m_call_stmt);
    1807          778 :   if (!lhs)
    1808              :     return true;
    1809              : 
    1810          445 :   const region_model &src_enode_model = ctxt.get_src_region_model ();
    1811          445 :   tree fndecl = src_enode_model.get_current_function ()->decl;
    1812          445 :   tree fn_result = DECL_RESULT (fndecl);
    1813              : 
    1814          445 :   ctxt.on_data_flow (DECL_RESULT (fndecl), lhs);
    1815              : 
    1816          445 :   return true;
    1817              : }
    1818              : 
    1819              : /* class exploded_edge : public dedge<eg_traits>.  */
    1820              : 
    1821              : /* exploded_edge's ctor.  */
    1822              : 
    1823       383640 : exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest,
    1824              :                               const superedge *sedge, bool could_do_work,
    1825              :                               std::unique_ptr<custom_edge_info> custom_info)
    1826       383640 : : dedge<eg_traits> (src, dest), m_sedge (sedge),
    1827       383640 :   m_custom_info (std::move (custom_info)),
    1828       383640 :   m_could_do_work_p (could_do_work)
    1829              : {
    1830       383640 : }
    1831              : 
    1832              : /* Implementation of dedge::dump_dot vfunc for exploded_edge.
    1833              :    Use the label of the underlying superedge, if any.  */
    1834              : 
    1835              : void
    1836          523 : exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
    1837              : {
    1838          523 :   pretty_printer *pp = gv->get_pp ();
    1839              : 
    1840          523 :   m_src->dump_dot_id (pp);
    1841          523 :   pp_string (pp, " -> ");
    1842          523 :   m_dest->dump_dot_id (pp);
    1843          523 :   dump_dot_label (pp);
    1844          523 : }
    1845              : 
    1846              : /* Second half of exploded_edge::dump_dot.  This is split out
    1847              :    for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot.  */
    1848              : 
    1849              : void
    1850          593 : exploded_edge::dump_dot_label (pretty_printer *pp) const
    1851              : {
    1852          593 :   const char *style = "\"solid,bold\"";
    1853          593 :   const char *color = "black";
    1854          593 :   int weight = 10;
    1855          593 :   const char *constraint = "true";
    1856              : 
    1857          593 :   if (m_sedge)
    1858              :     {
    1859          547 :       if (m_sedge->get_op ())
    1860          434 :         style = "\"solid\"";
    1861              :       else
    1862          113 :         style = "\"dotted\"";
    1863              :     }
    1864          593 :   if (m_custom_info)
    1865           22 :     m_custom_info->get_dot_attrs (style, color);
    1866              : 
    1867          593 :   pp_printf (pp,
    1868              :              (" [style=%s, color=%s, weight=%d, constraint=%s,"
    1869              :               " headlabel=\""),
    1870              :              style, color, weight, constraint);
    1871          593 :   pp_flush (pp);
    1872              : 
    1873          593 :   if (m_sedge)
    1874          547 :     m_sedge->dump_label_to_pp (pp, false);
    1875           46 :   else if (m_custom_info)
    1876           14 :     m_custom_info->print (pp);
    1877              : 
    1878         1148 :   pp_printf (pp, "%s",
    1879          593 :              could_do_work_p () ? "(could do work)" : "DOES NO WORK");
    1880              : 
    1881          593 :   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
    1882              : 
    1883          593 :   pp_printf (pp, "\"];\n");
    1884          593 : }
    1885              : 
    1886              : /* Return a new json::object of the form
    1887              :    {"src_idx": int, the index of the source exploded edge,
    1888              :     "dst_idx": int, the index of the destination exploded edge,
    1889              :     "sedge": (optional) object for the superedge, if any,
    1890              :     "custom": (optional) str, a description, if this is a custom edge}.  */
    1891              : 
    1892              : std::unique_ptr<json::object>
    1893            0 : exploded_edge::to_json () const
    1894              : {
    1895            0 :   auto eedge_obj = std::make_unique<json::object> ();
    1896            0 :   eedge_obj->set_integer ("src_idx", m_src->m_index);
    1897            0 :   eedge_obj->set_integer ("dst_idx", m_dest->m_index);
    1898            0 :   if (m_sedge)
    1899            0 :     eedge_obj->set ("sedge", m_sedge->to_json ());
    1900            0 :   if (m_custom_info)
    1901              :     {
    1902            0 :       pretty_printer pp;
    1903            0 :       pp_format_decoder (&pp) = default_tree_printer;
    1904            0 :       m_custom_info->print (&pp);
    1905            0 :       eedge_obj->set_string ("custom", pp_formatted_text (&pp));
    1906            0 :     }
    1907            0 :   return eedge_obj;
    1908              : }
    1909              : 
    1910              : const gimple *
    1911        24623 : exploded_edge::maybe_get_stmt () const
    1912              : {
    1913        24623 :   auto op = maybe_get_op ();
    1914        24623 :   if (!op)
    1915              :     return nullptr;
    1916        19348 :   return op->maybe_get_stmt ();
    1917              : }
    1918              : 
    1919              : const operation *
    1920        64635 : exploded_edge::maybe_get_op () const
    1921              : {
    1922        64635 :   if (!m_sedge)
    1923              :     return nullptr;
    1924        58787 :   return m_sedge->get_op ();
    1925              : }
    1926              : 
    1927              : /* A way to export the exploded_graph as a diagnostics::digraphs::digraph,
    1928              :    and thus to export it to SARIF diagnostic sinks.  */
    1929              : 
    1930              : class exploded_graph_diagnostic_digraph : public diagnostics::digraphs::digraph
    1931              : {
    1932              : public:
    1933            1 :   exploded_graph_diagnostic_digraph (const exploded_graph &eg)
    1934            1 :   : m_eg (eg)
    1935              :   {
    1936            1 :     set_graph_kind ("exploded_graph");
    1937              : 
    1938            1 :     int i;
    1939            1 :     exploded_node *n;
    1940           17 :     FOR_EACH_VEC_ELT (m_eg.m_nodes, i, n)
    1941           15 :       add_node_for_enode (*n);
    1942              : 
    1943              :     exploded_edge *e;
    1944           15 :     FOR_EACH_VEC_ELT (m_eg.m_edges, i, e)
    1945           14 :       add_edge_for_eedge (*e);
    1946              : 
    1947            1 :     const json::json_property worklist_prop
    1948            1 :       ("gcc/analyzer/exploded_graph/worklist");
    1949            1 :     set_property (worklist_prop,
    1950            1 :                   m_eg.get_worklist ().to_json ());
    1951              : 
    1952              :     /* The following are global, rather than part of the
    1953              :        exploded graph; we add them as part of the exploded graph's
    1954              :        diagnostic digraph for convenience.  */
    1955              : 
    1956              :     // TODO: analysis_plan
    1957              : 
    1958            1 :     const json::json_property diagnostic_manager_prop
    1959            1 :       ("gcc/analyzer/diagnostic_manager");
    1960            1 :     set_property (diagnostic_manager_prop,
    1961            1 :                   m_eg.get_diagnostic_manager ().to_json ());
    1962              : 
    1963            1 :     auto model_mgr = m_eg.get_ext_state ().get_model_manager ();
    1964              : 
    1965            1 :     const json::json_property known_functions_prop
    1966            1 :       ("gcc/analyzer/known_functions");
    1967            1 :     set_property (known_functions_prop,
    1968            1 :                   model_mgr->get_known_function_manager ()->to_json ());
    1969              : 
    1970            1 :     const json::json_property ext_state_prop
    1971            1 :       ("gcc/analyzer/extrinsic_state");
    1972            1 :     set_property (ext_state_prop,
    1973            1 :                   m_eg.get_ext_state ().to_json ());
    1974            1 :   }
    1975              : 
    1976              : private:
    1977              :   void
    1978           15 :   add_node_for_enode (const exploded_node &enode)
    1979              :   {
    1980           15 :     pretty_printer pp;
    1981           15 :     enode.dump_dot_id (&pp);
    1982           15 :     auto node_for_enode
    1983              :       = std::make_unique<diagnostics::digraphs::node> (*this,
    1984           15 :                                                        pp_formatted_text (&pp));
    1985              : 
    1986           15 :     if (auto fun = enode.get_function ())
    1987           14 :       node_for_enode->set_logical_loc
    1988           14 :         (tree_logical_location_manager::key_from_tree (fun->decl));
    1989           29 :     node_for_enode->set_physical_loc (enode.get_location ());
    1990              : 
    1991           15 :     auto &point = enode.get_point ();
    1992           15 :     if (auto snode = point.get_supernode ())
    1993              :       {
    1994           14 :         const json::string_property enode_prop_supernode
    1995           14 :           ("gcc/analyzer/exploded_node/supernode");
    1996           14 :         pretty_printer pp;
    1997           14 :         snode->dump_dot_id (&pp);
    1998           14 :         node_for_enode->set_property
    1999           14 :           (enode_prop_supernode,
    2000              :            pp_formatted_text (&pp));
    2001           14 :       }
    2002              : 
    2003           15 :     auto &cs = point.get_call_string ();
    2004           15 :     auto cs_arr = std::make_unique<json::array> ();
    2005           30 :     for (int i = 0; i < cs.length (); ++i)
    2006              :       {
    2007            0 :         auto e = cs[i];
    2008            0 :         auto obj = std::make_unique<json::object> ();
    2009              : 
    2010            0 :         {
    2011            0 :           pretty_printer pp;
    2012            0 :           e.m_call_sedge->m_src->dump_dot_id (&pp);
    2013            0 :           obj->set_string ("source supernode", pp_formatted_text (&pp));
    2014            0 :         }
    2015            0 :         {
    2016            0 :           pretty_printer pp;
    2017            0 :           e.m_call_sedge->m_dest->dump_dot_id (&pp);
    2018            0 :           obj->set_string ("destination supernode", pp_formatted_text (&pp));
    2019            0 :         }
    2020            0 :         {
    2021            0 :           pretty_printer pp;
    2022            0 :           pp_format_decoder (&pp) = default_tree_printer;
    2023            0 :           e.m_call_op->print_as_edge_label (&pp, false);
    2024            0 :           obj->set_string ("call operation", pp_formatted_text (&pp));
    2025            0 :         }
    2026            0 :         cs_arr->append (std::move (obj));
    2027            0 :       }
    2028           15 :     const json::json_property enode_prop_call_string
    2029           15 :       ("gcc/analyzer/exploded_node/call_string");
    2030           15 :     node_for_enode->set_property (enode_prop_call_string,
    2031           15 :                                   std::move (cs_arr));
    2032              : 
    2033           15 :     const json::json_property enode_prop_program_state
    2034           15 :       ("gcc/analyzer/exploded_node/program_state");
    2035           15 :     node_for_enode->set_property
    2036           15 :       (enode_prop_program_state,
    2037           15 :        enode.get_state ().to_json (m_eg.get_ext_state ()));
    2038              : 
    2039           15 :     const json::string_property enode_prop_status
    2040           15 :       ("gcc/analyzer/exploded_node/status");
    2041           15 :     node_for_enode->set_property
    2042           15 :       (enode_prop_status,
    2043              :        exploded_node::status_to_str (enode.get_status ()));
    2044              : 
    2045           15 :     m_node_for_enode.insert ({&enode, node_for_enode.get ()});
    2046           15 :     add_node (std::move (node_for_enode));
    2047           15 :   }
    2048              : 
    2049              :   void
    2050           14 :   add_edge_for_eedge (const exploded_edge &eedge)
    2051              :   {
    2052           14 :     diagnostics::digraphs::node *src_node
    2053           14 :       = get_node_for_enode (eedge.m_src);
    2054           14 :     diagnostics::digraphs::node *dst_node
    2055           14 :       = get_node_for_enode (eedge.m_dest);
    2056           14 :     auto e = std::make_unique<diagnostics::digraphs::edge> (*this,
    2057           28 :                                                             nullptr,
    2058              :                                                             *src_node,
    2059           14 :                                                             *dst_node);
    2060           14 :     if (auto *sedge = eedge.m_sedge)
    2061              :       {
    2062           13 :         const json::string_property eedge_prop_superedge
    2063           13 :           ("gcc/analyzer/exploded_edge/superedge");
    2064           13 :         pretty_printer pp;
    2065           13 :         pp_format_decoder (&pp) = default_tree_printer;
    2066           13 :         sedge->dump_label_to_pp (&pp, false);
    2067           13 :         e->set_property (eedge_prop_superedge,
    2068              :                          pp_formatted_text (&pp));
    2069           13 :       }
    2070           14 :     if (auto *custom_info = eedge.m_custom_info.get ())
    2071              :       {
    2072            0 :         const json::string_property eedge_prop_custom_edge_info
    2073            0 :           ("gcc/analyzer/exploded_edge/custom_edge_info");
    2074            0 :         pretty_printer pp;
    2075            0 :         pp_format_decoder (&pp) = default_tree_printer;
    2076            0 :         custom_info->print (&pp);
    2077            0 :         e->set_property (eedge_prop_custom_edge_info,
    2078              :                          pp_formatted_text (&pp));
    2079            0 :       }
    2080           14 :     add_edge (std::move (e));
    2081           14 :   }
    2082              : 
    2083              :   diagnostics::digraphs::node *
    2084           28 :   get_node_for_enode (const exploded_node *enode)
    2085              :   {
    2086           28 :     auto iter = m_node_for_enode.find (enode);
    2087           28 :     gcc_assert (iter != m_node_for_enode.end ());
    2088           28 :     return iter->second;
    2089              :   }
    2090              : 
    2091              :   const exploded_graph &m_eg;
    2092              :   std::map<const exploded_node *,
    2093              :            diagnostics::digraphs::node *> m_node_for_enode;
    2094              : };
    2095              : 
    2096              : std::unique_ptr<diagnostics::digraphs::digraph>
    2097            1 : exploded_graph::make_diagnostics_digraph () const
    2098              : {
    2099            1 :   return std::make_unique<exploded_graph_diagnostic_digraph> (*this);
    2100              : }
    2101              : 
    2102              : /* struct stats.  */
    2103              : 
    2104              : /* stats' ctor.  */
    2105              : 
    2106        30357 : stats::stats (int num_supernodes)
    2107        30357 : : m_num_nodes (0),
    2108        30357 :   m_node_reuse_count (0),
    2109        30357 :   m_node_reuse_after_merge_count (0),
    2110        30357 :   m_num_supernodes (num_supernodes)
    2111              : {
    2112        30357 : }
    2113              : 
    2114              : /* Log these stats in multiline form to LOGGER.  */
    2115              : 
    2116              : void
    2117           11 : stats::log (logger *logger) const
    2118              : {
    2119           11 :   gcc_assert (logger);
    2120           11 :   logger->log ("m_num_nodes: %i", m_num_nodes);
    2121           11 :   logger->log ("m_node_reuse_count: %i", m_node_reuse_count);
    2122           11 :   logger->log ("m_node_reuse_after_merge_count: %i",
    2123           11 :                m_node_reuse_after_merge_count);
    2124           11 : }
    2125              : 
    2126              : /* Dump these stats in multiline form to OUT.  */
    2127              : 
    2128              : void
    2129            0 : stats::dump (FILE *out) const
    2130              : {
    2131            0 :   fprintf (out, "m_num_nodes: %i\n", m_num_nodes);
    2132            0 :   fprintf (out, "m_node_reuse_count: %i\n", m_node_reuse_count);
    2133            0 :   fprintf (out, "m_node_reuse_after_merge_count: %i\n",
    2134            0 :            m_node_reuse_after_merge_count);
    2135              : 
    2136            0 :   if (m_num_supernodes > 0)
    2137            0 :     fprintf (out, "enodes per supernode: %.2f\n",
    2138            0 :              (float)m_num_nodes / (float)m_num_supernodes);
    2139            0 : }
    2140              : 
    2141              : /* Return the total number of enodes recorded within this object.  */
    2142              : 
    2143              : int
    2144            6 : stats::get_total_enodes () const
    2145              : {
    2146            6 :   return m_num_nodes;
    2147              : }
    2148              : 
    2149              : /* struct per_function_data.  */
    2150              : 
    2151          351 : per_function_data::~per_function_data ()
    2152              : {
    2153         1495 :   for (auto iter : m_summaries)
    2154          442 :     delete iter;
    2155          351 : }
    2156              : 
    2157              : void
    2158          442 : per_function_data::add_call_summary (exploded_node *node)
    2159              : {
    2160          442 :   m_summaries.safe_push (new call_summary (this, node));
    2161          442 : }
    2162              : 
    2163              : /* strongly_connected_components's ctor.  Tarjan's SCC algorithm.  */
    2164              : 
    2165         3573 : strongly_connected_components::
    2166              : strongly_connected_components (const supergraph &sg, logger *logger)
    2167         7142 : : m_sg (sg), m_per_node (m_sg.m_nodes.length ())
    2168              : {
    2169         3573 :   LOG_SCOPE (logger);
    2170         3573 :   auto_timevar tv (TV_ANALYZER_SCC);
    2171              : 
    2172       208587 :   for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
    2173       201441 :     m_per_node.quick_push (per_node_data ());
    2174              : 
    2175       212152 :   for (auto snode : m_sg.m_nodes)
    2176       201441 :     if (m_per_node[snode->m_id].m_id == -1)
    2177        11661 :       strong_connect (snode->m_id, logger);
    2178              : 
    2179         3573 :   if (0)
    2180              :     dump ();
    2181         3573 : }
    2182              : 
    2183              : /* Dump this object to stderr.  */
    2184              : 
    2185              : DEBUG_FUNCTION void
    2186            0 : strongly_connected_components::dump () const
    2187              : {
    2188            0 :   fprintf (stderr, "Stack: [");
    2189            0 :   bool first = true;
    2190            0 :   for (auto i : m_stack)
    2191              :     {
    2192            0 :       if (first)
    2193              :         first = false;
    2194              :       else
    2195            0 :         fprintf (stderr, ", ");
    2196            0 :       fprintf (stderr, "%i", i);
    2197              :     }
    2198            0 :   fprintf (stderr, "]\n");
    2199            0 :   for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
    2200              :     {
    2201            0 :       const per_node_data &v = m_per_node[i];
    2202            0 :       fprintf (stderr, "SN %lu: index: %i lowlink: %i on_stack: %i\n",
    2203            0 :                i, v.m_id, v.m_lowlink, v.m_on_stack);
    2204              :     }
    2205            0 : }
    2206              : 
    2207              : /* Return a new json::array of per-snode SCC ids.  */
    2208              : 
    2209              : std::unique_ptr<json::array>
    2210            1 : strongly_connected_components::to_json () const
    2211              : {
    2212            1 :   auto scc_arr = std::make_unique<json::array> ();
    2213           12 :   for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
    2214           10 :     scc_arr->append (std::make_unique<json::integer_number> (get_scc_id (i)));
    2215            1 :   return scc_arr;
    2216              : }
    2217              : 
    2218              : /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
    2219              :    SCC algorithm.  */
    2220              : 
    2221              : void
    2222       201441 : strongly_connected_components::strong_connect (unsigned id,
    2223              :                                                logger *logger)
    2224              : {
    2225       201441 :   supernode *v_snode = m_sg.m_nodes[id];
    2226       201441 :   if (!v_snode)
    2227       201441 :     return;
    2228              : 
    2229              :   /* Set the depth index for v to the smallest unused index.  */
    2230       201441 :   per_node_data *v = &m_per_node[id];
    2231       201441 :   v->m_id = id;
    2232       201441 :   v->m_lowlink = id;
    2233       201441 :   m_stack.safe_push (id);
    2234       201441 :   v->m_on_stack = true;
    2235       201441 :   id++;
    2236              : 
    2237              :   /* Consider successors of v.  */
    2238       201441 :   unsigned i;
    2239       201441 :   superedge *sedge;
    2240       401724 :   FOR_EACH_VEC_ELT (v_snode->m_succs, i, sedge)
    2241              :     {
    2242       200283 :       supernode *w_snode = sedge->m_dest;
    2243       200283 :       per_node_data *w = &m_per_node[w_snode->m_id];
    2244       200283 :       if (w->m_id == -1)
    2245              :         {
    2246              :           /* Successor w has not yet been visited; recurse on it.  */
    2247       189780 :           strong_connect (w_snode->m_id, logger);
    2248       189780 :           v->m_lowlink = MIN (v->m_lowlink, w->m_lowlink);
    2249              :         }
    2250        10503 :       else if (w->m_on_stack)
    2251              :         {
    2252              :           /* Successor w is in stack S and hence in the current SCC
    2253              :              If w is not on stack, then (v, w) is a cross-edge in the DFS
    2254              :              tree and must be ignored.  */
    2255         2194 :           v->m_lowlink = MIN (v->m_lowlink, w->m_id);
    2256              :         }
    2257              :     }
    2258              : 
    2259              :   /* If v is a root node, pop the stack and generate an SCC.  */
    2260              : 
    2261       201441 :   if (v->m_lowlink == v->m_id)
    2262              :     {
    2263       185027 :       if (logger)
    2264           50 :         logger->log ("got SCC root node: SN %i", v->m_id);
    2265       201441 :       per_node_data *w;
    2266       201441 :       do {
    2267       201441 :         int id = m_stack.pop ();
    2268       201441 :         w = &m_per_node[id];
    2269       201441 :         w->m_on_stack = false;
    2270       201441 :         if (logger)
    2271           80 :           logger->log ("  popping SN %i", w->m_id);
    2272       201441 :       } while (w != v);
    2273              :     }
    2274              : }
    2275              : 
    2276              : /* worklist's ctor.  */
    2277              : 
    2278         3573 : worklist::worklist (const exploded_graph &eg, const analysis_plan &plan)
    2279         3573 : : m_scc (eg.get_supergraph (), eg.get_logger ()),
    2280         3573 :   m_plan (plan),
    2281         3573 :   m_queue (key_t (*this, nullptr))
    2282              : {
    2283         3573 : }
    2284              : 
    2285              : /* Return the number of nodes in the worklist.  */
    2286              : 
    2287              : unsigned
    2288       349992 : worklist::length () const
    2289              : {
    2290       349992 :   return m_queue.nodes ();
    2291              : }
    2292              : 
    2293              : /* Return the next node in the worklist, removing it.  */
    2294              : 
    2295              : exploded_node *
    2296       362778 : worklist::take_next ()
    2297              : {
    2298       362778 :   return m_queue.extract_min ();
    2299              : }
    2300              : 
    2301              : /* Return the next node in the worklist without removing it.  */
    2302              : 
    2303              : exploded_node *
    2304       387406 : worklist::peek_next ()
    2305              : {
    2306       387406 :   return m_queue.min ();
    2307              : }
    2308              : 
    2309              : /* Add ENODE to the worklist.  */
    2310              : 
    2311              : void
    2312       363699 : worklist::add_node (exploded_node *enode)
    2313              : {
    2314       363699 :   gcc_assert (enode->get_status () == exploded_node::status::worklist);
    2315       363699 :   m_queue.insert (key_t (*this, enode), enode);
    2316       363699 : }
    2317              : 
    2318              : /* Comparator for implementing worklist::key_t comparison operators.
    2319              :    Return negative if KA is before KB
    2320              :    Return positive if KA is after KB
    2321              :    Return 0 if they are equal.
    2322              : 
    2323              :    The ordering of the worklist is critical for performance and for
    2324              :    avoiding node explosions.  Ideally we want all enodes at a CFG join-point
    2325              :    with the same callstring to be sorted next to each other in the worklist
    2326              :    so that a run of consecutive enodes can be merged and processed "in bulk"
    2327              :    rather than individually or pairwise, minimizing the number of new enodes
    2328              :    created.  */
    2329              : 
    2330              : int
    2331      1307074 : worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
    2332              : {
    2333      1307074 :   const program_point &point_a = ka.m_enode->get_point ();
    2334      1307074 :   const program_point &point_b = kb.m_enode->get_point ();
    2335      1307074 :   const call_string &call_string_a = point_a.get_call_string ();
    2336      1307074 :   const call_string &call_string_b = point_b.get_call_string ();
    2337              : 
    2338              :   /* Order empty-callstring points with different functions based on the
    2339              :      analysis_plan, so that we generate summaries before they are used.  */
    2340      1307074 :   if (flag_analyzer_call_summaries
    2341       100408 :       && call_string_a.empty_p ()
    2342        88760 :       && call_string_b.empty_p ()
    2343        88760 :       && point_a.get_function () != nullptr
    2344        88379 :       && point_b.get_function () != nullptr
    2345      1395453 :       && point_a.get_function () != point_b.get_function ())
    2346              :     {
    2347        41390 :       if (int cmp = ka.m_worklist.m_plan.cmp_function (point_a.get_function (),
    2348              :                                                        point_b.get_function ()))
    2349              :         return cmp;
    2350              :     }
    2351              : 
    2352              :   /* Sort by callstring, so that nodes with deeper call strings are processed
    2353              :      before those with shallower call strings.
    2354              :      If we have
    2355              :          splitting BB
    2356              :              /  \
    2357              :             /    \
    2358              :        fn call   no fn call
    2359              :             \    /
    2360              :              \  /
    2361              :             join BB
    2362              :      then we want the path inside the function call to be fully explored up
    2363              :      to the return to the join BB before we explore on the "no fn call" path,
    2364              :      so that both enodes at the join BB reach the front of the worklist at
    2365              :      the same time and thus have a chance of being merged.  */
    2366      1265684 :   int cs_cmp = call_string::cmp (call_string_a, call_string_b);
    2367      1265684 :   if (cs_cmp)
    2368              :     return cs_cmp;
    2369              : 
    2370              :   /* Order by SCC.  */
    2371      1066004 :   int scc_id_a = ka.get_scc_id (ka.m_enode);
    2372      1066004 :   int scc_id_b = kb.get_scc_id (kb.m_enode);
    2373      1066004 :   if (scc_id_a != scc_id_b)
    2374       941455 :     return scc_id_a - scc_id_b;
    2375              : 
    2376              :   /* If in same SCC, order by supernode index (an arbitrary but stable
    2377              :      ordering).  */
    2378       124549 :   const supernode *snode_a = ka.m_enode->get_supernode ();
    2379       124549 :   const supernode *snode_b = kb.m_enode->get_supernode ();
    2380       124549 :   if (snode_a == nullptr)
    2381              :     {
    2382            0 :       if (snode_b != nullptr)
    2383              :         /* One is nullptr.  */
    2384              :         return -1;
    2385              :       else
    2386              :         /* Both are nullptr.  */
    2387            0 :         return 0;
    2388              :     }
    2389       124549 :   if (snode_b == nullptr)
    2390              :     /* One is nullptr.  */
    2391              :     return 1;
    2392              :   /* Neither are nullptr.  */
    2393       120986 :   gcc_assert (snode_a && snode_b);
    2394       120986 :   if (snode_a->m_bb->index != snode_b->m_bb->index)
    2395        16255 :     return snode_a->m_bb->index - snode_b->m_bb->index;
    2396       104731 :   if (snode_a->m_id != snode_b->m_id)
    2397         7741 :     return snode_a->m_id - snode_b->m_id;
    2398              : 
    2399        96990 :   gcc_assert (snode_a == snode_b);
    2400              : 
    2401              :   /* Otherwise, we ought to have the same program_point.  */
    2402        96990 :   gcc_assert (point_a == point_b);
    2403              : 
    2404              :   const program_state &state_a = ka.m_enode->get_state ();
    2405              :   const program_state &state_b = kb.m_enode->get_state ();
    2406              : 
    2407              :   /* Sort by sm-state, so that identical sm-states are grouped
    2408              :      together in the worklist.  */
    2409       384085 :   for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length ();
    2410              :        ++sm_idx)
    2411              :     {
    2412       346306 :       sm_state_map *smap_a = state_a.m_checker_states[sm_idx];
    2413       346306 :       sm_state_map *smap_b = state_b.m_checker_states[sm_idx];
    2414              : 
    2415       346306 :       if (int smap_cmp = sm_state_map::cmp (*smap_a, *smap_b))
    2416              :         return smap_cmp;
    2417              :     }
    2418              : 
    2419              :   /* Otherwise, we have two enodes at the same program point but with
    2420              :      different states.  We don't have a good total ordering on states,
    2421              :      so order them by enode index, so that we have at least have a
    2422              :      stable sort.  */
    2423        37779 :   return ka.m_enode->m_index - kb.m_enode->m_index;
    2424              : }
    2425              : 
    2426              : /* Return a new json::object of the form
    2427              :    {"scc" : [per-snode-IDs]},  */
    2428              : 
    2429              : std::unique_ptr<json::object>
    2430            1 : worklist::to_json () const
    2431              : {
    2432            1 :   auto worklist_obj = std::make_unique<json::object> ();
    2433              : 
    2434            1 :   worklist_obj->set ("scc", m_scc.to_json ());
    2435              : 
    2436              :   /* The following field isn't yet being JSONified:
    2437              :      queue_t m_queue;  */
    2438              : 
    2439            1 :   return worklist_obj;
    2440              : }
    2441              : 
    2442              : /* exploded_graph's ctor.  */
    2443              : 
    2444         3573 : exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
    2445              :                                 const extrinsic_state &ext_state,
    2446              :                                 const state_purge_map *purge_map,
    2447              :                                 const analysis_plan &plan,
    2448              :                                 int verbosity)
    2449         3573 : : m_sg (sg), m_logger (logger),
    2450         3573 :   m_worklist (*this, plan),
    2451         3573 :   m_ext_state (ext_state),
    2452         3573 :   m_purge_map (purge_map),
    2453         3573 :   m_plan (plan),
    2454         3573 :   m_diagnostic_manager (logger, ext_state.get_engine (), verbosity),
    2455         7142 :   m_global_stats (m_sg.m_nodes.length ()),
    2456        10715 :   m_functionless_stats (m_sg.m_nodes.length ())
    2457              : {
    2458         7146 :   m_origin = get_or_create_node
    2459         3573 :     (program_point::origin (*ext_state.get_model_manager ()),
    2460         7146 :      program_state (ext_state), nullptr);
    2461         3573 : }
    2462              : 
    2463              : /* exploded_graph's dtor.  */
    2464              : 
    2465         3573 : exploded_graph::~exploded_graph ()
    2466              : {
    2467       279653 :   for (auto iter : m_per_point_data)
    2468       552160 :     delete iter.second;
    2469         3924 :   for (auto iter : m_per_function_data)
    2470          351 :     delete iter.second;
    2471        18799 :   for (auto iter : m_per_function_stats)
    2472        11657 :     delete iter.second;
    2473        15127 :   for (auto iter : m_per_call_string_data)
    2474        11554 :     delete iter.second;
    2475         7146 : }
    2476              : 
    2477              : /* Subroutine for use when implementing __attribute__((tainted_args))
    2478              :    on functions and on function pointer fields in structs.
    2479              : 
    2480              :    Called on STATE representing a call to FNDECL.
    2481              :    Mark all params of FNDECL in STATE as "tainted".  Mark the value of all
    2482              :    regions pointed to by params of FNDECL as "tainted".
    2483              : 
    2484              :    Return true if successful; return false if the "taint" state machine
    2485              :    was not found.  */
    2486              : 
    2487              : static bool
    2488          212 : mark_params_as_tainted (program_state *state, tree fndecl,
    2489              :                         const extrinsic_state &ext_state)
    2490              : {
    2491          212 :   unsigned taint_sm_idx;
    2492          212 :   if (!ext_state.get_sm_idx_by_name ("taint", &taint_sm_idx))
    2493              :     return false;
    2494          212 :   sm_state_map *smap = state->m_checker_states[taint_sm_idx];
    2495              : 
    2496          212 :   const state_machine &sm = ext_state.get_sm (taint_sm_idx);
    2497          212 :   state_machine::state_t tainted = sm.get_state_by_name ("tainted");
    2498              : 
    2499          212 :   region_model_manager *mgr = ext_state.get_model_manager ();
    2500              : 
    2501          212 :   function *fun = DECL_STRUCT_FUNCTION (fndecl);
    2502          212 :   gcc_assert (fun);
    2503              : 
    2504          503 :   for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm;
    2505          291 :        iter_parm = DECL_CHAIN (iter_parm))
    2506              :     {
    2507          291 :       tree param = iter_parm;
    2508          291 :       if (tree parm_default_ssa = ssa_default_def (fun, iter_parm))
    2509          229 :         param = parm_default_ssa;
    2510          291 :       const region *param_reg = state->m_region_model->get_lvalue (param, nullptr);
    2511          291 :       const svalue *init_sval = mgr->get_or_create_initial_value (param_reg);
    2512          291 :       smap->set_state (state->m_region_model, init_sval,
    2513              :                        tainted, nullptr /*origin_new_sval*/, ext_state);
    2514          291 :       if (POINTER_TYPE_P (TREE_TYPE (param)))
    2515              :         {
    2516           56 :           const region *pointee_reg = mgr->get_symbolic_region (init_sval);
    2517              :           /* Mark "*param" as tainted.  */
    2518           56 :           const svalue *init_pointee_sval
    2519           56 :             = mgr->get_or_create_initial_value (pointee_reg);
    2520           56 :           smap->set_state (state->m_region_model, init_pointee_sval,
    2521              :                            tainted, nullptr /*origin_new_sval*/, ext_state);
    2522              :         }
    2523              :     }
    2524              : 
    2525              :   return true;
    2526              : }
    2527              : 
    2528              : /* Custom event for use by tainted_args_function_info when a function
    2529              :    has been marked with __attribute__((tainted_args)).  */
    2530              : 
    2531              : class tainted_args_function_custom_event : public custom_event
    2532              : {
    2533              : public:
    2534          109 :   tainted_args_function_custom_event (const event_loc_info &loc_info)
    2535              :   : custom_event (loc_info),
    2536          109 :     m_fndecl (loc_info.m_fndecl)
    2537              :   {
    2538              :   }
    2539              : 
    2540              :   void
    2541          218 :   print_desc (pretty_printer &pp) const final override
    2542              :   {
    2543          218 :     pp_printf (&pp,
    2544              :                "function %qE marked with %<__attribute__((tainted_args))%>",
    2545          218 :                m_fndecl);
    2546          218 :   }
    2547              : 
    2548              : private:
    2549              :   tree m_fndecl;
    2550              : };
    2551              : 
    2552              : /* Custom exploded_edge info for top-level calls to a function
    2553              :    marked with __attribute__((tainted_args)).  */
    2554              : 
    2555              : class tainted_args_function_info : public custom_edge_info
    2556              : {
    2557              : public:
    2558          202 :   tainted_args_function_info (tree fndecl)
    2559          202 :   : m_fndecl (fndecl)
    2560              :   {}
    2561              : 
    2562            0 :   void print (pretty_printer *pp) const final override
    2563              :   {
    2564            0 :     pp_string (pp, "call to tainted_args function");
    2565            0 :   };
    2566              : 
    2567          274 :   bool update_model (region_model *model,
    2568              :                      const exploded_edge *eedge,
    2569              :                      region_model_context *ctxt) const final override
    2570              :   {
    2571          274 :     function *fun = eedge->m_dest->get_function ();
    2572          274 :     gcc_assert (fun);
    2573          274 :     model->push_frame (*fun, nullptr, nullptr, ctxt);
    2574          274 :     return true;
    2575              :   }
    2576              : 
    2577          109 :   void add_events_to_path (checker_path *emission_path,
    2578              :                            const exploded_edge &,
    2579              :                            pending_diagnostic &,
    2580              :                            const state_transition *) const final override
    2581              :   {
    2582          109 :     emission_path->add_event
    2583          109 :       (std::make_unique<tainted_args_function_custom_event>
    2584          109 :          (event_loc_info (DECL_SOURCE_LOCATION (m_fndecl), m_fndecl, 0)));
    2585          109 :   }
    2586              : 
    2587              : private:
    2588              :   tree m_fndecl;
    2589              : };
    2590              : 
    2591              : /* Ensure that there is an exploded_node representing an external call to
    2592              :    FUN, adding it to the worklist if creating it.
    2593              : 
    2594              :    Add an edge from the origin exploded_node to the function entrypoint
    2595              :    exploded_node.
    2596              : 
    2597              :    Return the exploded_node for the entrypoint to the function.  */
    2598              : 
    2599              : exploded_node *
    2600        11815 : exploded_graph::add_function_entry (const function &fun)
    2601              : {
    2602        11815 :   gcc_assert (gimple_has_body_p (fun.decl));
    2603              : 
    2604              :   /* Be idempotent.  */
    2605        11815 :   function *key = const_cast<function *> (&fun);
    2606        11815 :   if (m_functions_with_enodes.contains (key))
    2607              :     {
    2608          305 :       logger * const logger = get_logger ();
    2609          305 :        if (logger)
    2610            0 :         logger->log ("entrypoint for %qE already exists", fun.decl);
    2611              :       return nullptr;
    2612              :     }
    2613              : 
    2614        11510 :   program_point point
    2615        11510 :     = program_point::from_function_entry (*m_ext_state.get_model_manager (),
    2616              :                                           m_sg, fun);
    2617        11510 :   program_state state (m_ext_state);
    2618        11510 :   state.push_frame (m_ext_state, fun);
    2619              : 
    2620        11510 :   std::unique_ptr<custom_edge_info> edge_info = nullptr;
    2621              : 
    2622        11510 :   if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (fun.decl)))
    2623              :     {
    2624          202 :       if (mark_params_as_tainted (&state, fun.decl, m_ext_state))
    2625          202 :         edge_info = std::make_unique<tainted_args_function_info> (fun.decl);
    2626              :     }
    2627              : 
    2628        11510 :   if (!state.m_valid)
    2629              :     return nullptr;
    2630              : 
    2631        11510 :   exploded_node *enode = get_or_create_node (point, state, nullptr);
    2632        11510 :   if (!enode)
    2633              :     return nullptr;
    2634              : 
    2635        11502 :   add_edge (m_origin, enode, nullptr, false, std::move (edge_info));
    2636              : 
    2637        11502 :   m_functions_with_enodes.add (key);
    2638              : 
    2639        11502 :   return enode;
    2640        11510 : }
    2641              : 
    2642              : /* Get or create an exploded_node for (POINT, STATE).
    2643              :    If a new node is created and ADD_TO_WORKLIST is true,
    2644              :    it is added to the worklist.
    2645              : 
    2646              :    Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
    2647              :    that need to be emitted (e.g. when purging state *before* we have
    2648              :    a new enode).  */
    2649              : 
    2650              : exploded_node *
    2651       376761 : exploded_graph::get_or_create_node (const program_point &point,
    2652              :                                     const program_state &state,
    2653              :                                     exploded_node *enode_for_diag,
    2654              :                                     bool add_to_worklist)
    2655              : {
    2656       376761 :   logger * const logger = get_logger ();
    2657       376761 :   LOG_FUNC (logger);
    2658       376761 :   if (logger)
    2659              :     {
    2660          119 :       format f (false);
    2661          119 :       pretty_printer *pp = logger->get_printer ();
    2662          119 :       logger->start_log_line ();
    2663          119 :       pp_string (pp, "point: ");
    2664          119 :       point.print (pp, f);
    2665          119 :       logger->end_log_line ();
    2666          119 :       state.dump_to_logger (*logger);
    2667              :     }
    2668              : 
    2669              :   /* Stop exploring paths for which we don't know how to effectively
    2670              :      model the state.  */
    2671       376761 :   if (!state.m_valid)
    2672              :     {
    2673            0 :       if (logger)
    2674            0 :         logger->log ("invalid state; not creating node");
    2675              :       return nullptr;
    2676              :     }
    2677              : 
    2678       376761 :   if (point.get_call_string ().calc_recursion_depth ()
    2679       376761 :       > param_analyzer_max_recursion_depth)
    2680              :     {
    2681          590 :       if (logger)
    2682            0 :         logger->log ("rejecting node: recursion limit exceeded");
    2683              :       return nullptr;
    2684              :     }
    2685              : 
    2686       748769 :   auto_cfun sentinel (point.get_function ());
    2687              : 
    2688       376171 :   state.validate (get_ext_state ());
    2689              : 
    2690              :   //state.dump (get_ext_state ());
    2691              : 
    2692              :   /* Prune state to try to improve the chances of a cache hit,
    2693              :      avoiding generating redundant nodes.  */
    2694       376171 :   uncertainty_t uncertainty;
    2695       376171 :   program_state pruned_state
    2696       376171 :     = state.prune_for_point (*this, point, enode_for_diag, &uncertainty);
    2697              : 
    2698       376171 :   pruned_state.validate (get_ext_state ());
    2699              : 
    2700              :   //pruned_state.dump (get_ext_state ());
    2701              : 
    2702       376171 :   if (logger)
    2703          119 :     pruned_state.dump_to_logger (*logger, "pruned_state");
    2704              : 
    2705       748769 :   stats *per_fn_stats = get_or_create_function_stats (point.get_function ());
    2706              : 
    2707       376171 :   stats *per_cs_stats
    2708       376171 :     = &get_or_create_per_call_string_data (point.get_call_string ())->m_stats;
    2709              : 
    2710       376171 :   point_and_state ps (point, pruned_state);
    2711       376171 :   ps.validate (m_ext_state);
    2712       376171 :   if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
    2713              :     {
    2714              :       /* An exploded_node for PS already exists.  */
    2715         2480 :       if (logger)
    2716            3 :         logger->log ("reused EN: %i", (*slot)->m_index);
    2717         2480 :       m_global_stats.m_node_reuse_count++;
    2718         2480 :       per_fn_stats->m_node_reuse_count++;
    2719         2480 :       per_cs_stats->m_node_reuse_count++;
    2720         2480 :       return *slot;
    2721              :     }
    2722              : 
    2723       373691 :   per_program_point_data *per_point_data
    2724       373691 :     = get_or_create_per_program_point_data (point);
    2725              : 
    2726              :   /* Consider merging state with another enode at this program_point.  */
    2727       891072 :   if (flag_analyzer_state_merge && point.state_merge_at_p ())
    2728              :     {
    2729              :       exploded_node *existing_enode;
    2730              :       unsigned i;
    2731       221453 :       FOR_EACH_VEC_ELT (per_point_data->m_enodes, i, existing_enode)
    2732              :         {
    2733        73952 :           if (logger)
    2734           23 :             logger->log ("considering merging with existing EN: %i for point",
    2735           23 :                          existing_enode->m_index);
    2736        73952 :           gcc_assert (existing_enode->get_point () == point);
    2737        73952 :           const program_state &existing_state = existing_enode->get_state ();
    2738              : 
    2739              :           /* This merges successfully within the loop.  */
    2740              : 
    2741        73952 :           program_state merged_state (m_ext_state);
    2742        73952 :           if (pruned_state.can_merge_with_p (existing_state, m_ext_state, point,
    2743              :                                              &merged_state))
    2744              :             {
    2745        25306 :               merged_state.validate (m_ext_state);
    2746        25306 :               if (logger)
    2747           23 :                 logger->log ("merging new state with that of EN: %i",
    2748           23 :                              existing_enode->m_index);
    2749              : 
    2750              :               /* Try again for a cache hit.
    2751              :                  Whether we get one or not, merged_state's value_ids have no
    2752              :                  relationship to those of the input state, and thus to those
    2753              :                  of CHANGE, so we must purge any svalue_ids from *CHANGE.  */
    2754        25306 :               ps.set_state (std::move (merged_state));
    2755              : 
    2756        25306 :               if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
    2757              :                 {
    2758              :                   /* An exploded_node for PS already exists.  */
    2759         1405 :                   if (logger)
    2760            4 :                     logger->log ("reused EN: %i", (*slot)->m_index);
    2761         1405 :                   m_global_stats.m_node_reuse_after_merge_count++;
    2762         1405 :                   per_fn_stats->m_node_reuse_after_merge_count++;
    2763         1405 :                   per_cs_stats->m_node_reuse_after_merge_count++;
    2764         1405 :                   return *slot;
    2765              :                 }
    2766              :             }
    2767              :           else
    2768        48646 :             if (logger)
    2769            0 :               logger->log ("not merging new state with that of EN: %i",
    2770            0 :                            existing_enode->m_index);
    2771        73952 :         }
    2772              :     }
    2773              : 
    2774              :   /* Impose a limit on the number of enodes per program point, and
    2775              :      simply stop if we exceed it.  */
    2776       372286 :   if ((int)per_point_data->m_enodes.length ()
    2777       372286 :       >= param_analyzer_max_enodes_per_program_point)
    2778              :     {
    2779         1097 :       pretty_printer pp;
    2780         1097 :       point.print (&pp, format (false));
    2781         1097 :       print_enode_indices (&pp, per_point_data->m_enodes);
    2782         1097 :       if (logger)
    2783            0 :         logger->log ("not creating enode; too many at program point: %s",
    2784              :                      pp_formatted_text (&pp));
    2785         2190 :       warning_at (point.get_location (), OPT_Wanalyzer_too_complex,
    2786              :                   "terminating analysis for this program point: %s",
    2787              :                   pp_formatted_text (&pp));
    2788         1097 :       per_point_data->m_excess_enodes++;
    2789         1097 :       return nullptr;
    2790         1097 :     }
    2791              : 
    2792       371189 :   ps.validate (m_ext_state);
    2793              : 
    2794              :   /* An exploded_node for "ps" doesn't already exist; create one.  */
    2795       738809 :   exploded_node *node = new exploded_node (std::move (ps), m_nodes.length ());
    2796       371189 :   add_node (node);
    2797       371189 :   m_point_and_state_to_node.put (node->get_ps_key (), node);
    2798              : 
    2799              :   /* Update per-program_point data.  */
    2800       371189 :   per_point_data->m_enodes.safe_push (node);
    2801              : 
    2802       371189 :   m_global_stats.m_num_nodes++;
    2803       371189 :   per_fn_stats->m_num_nodes++;
    2804       371189 :   per_cs_stats->m_num_nodes++;
    2805              : 
    2806       371189 :   if (logger)
    2807              :     {
    2808          112 :       format f (false);
    2809          112 :       pretty_printer *pp = logger->get_printer ();
    2810          112 :       logger->log ("created EN: %i", node->m_index);
    2811          112 :       logger->start_log_line ();
    2812          112 :       pp_string (pp, "point: ");
    2813          112 :       point.print (pp, f);
    2814          112 :       logger->end_log_line ();
    2815          112 :       node->get_state ().dump_to_logger (*logger);
    2816              :     }
    2817              : 
    2818              :   /* Add the new node to the worlist.  */
    2819       371189 :   if (add_to_worklist)
    2820       363693 :     m_worklist.add_node (node);
    2821              :   else
    2822         7496 :     node->set_status (exploded_node::status::special);
    2823              :   return node;
    2824       752932 : }
    2825              : 
    2826              : /* Add an exploded_edge from SRC to DEST, recording its association
    2827              :    with SEDGE (which may be NULL), and, if non-NULL, taking ownership
    2828              :    of CUSTOM_INFO.  COULD_DO_WORK is used for detecting infinite loops.
    2829              :    Return the newly-created eedge.  */
    2830              : 
    2831              : exploded_edge *
    2832       383640 : exploded_graph::add_edge (exploded_node *src, exploded_node *dest,
    2833              :                           const superedge *sedge, bool could_do_work,
    2834              :                           std::unique_ptr<custom_edge_info> custom_info)
    2835              : {
    2836       383640 :   if (get_logger ())
    2837          116 :     get_logger ()->log ("creating edge EN: %i -> EN: %i",
    2838          116 :                         src->m_index, dest->m_index);
    2839       383640 :   exploded_edge *e
    2840              :     = new exploded_edge (src, dest, sedge, could_do_work,
    2841       383640 :                          std::move (custom_info));
    2842       383640 :   digraph<eg_traits>::add_edge (e);
    2843       383640 :   return e;
    2844              : }
    2845              : 
    2846              : /* Ensure that this graph has per-program_point-data for POINT;
    2847              :    borrow a pointer to it.  */
    2848              : 
    2849              : per_program_point_data *
    2850       373691 : exploded_graph::
    2851              : get_or_create_per_program_point_data (const program_point &point)
    2852              : {
    2853       373691 :   if (per_program_point_data **slot = m_per_point_data.get (&point))
    2854        97611 :     return *slot;
    2855              : 
    2856       276080 :   per_program_point_data *per_point_data = new per_program_point_data (point);
    2857       276080 :   m_per_point_data.put (&per_point_data->m_key, per_point_data);
    2858       276080 :   return per_point_data;
    2859              : }
    2860              : 
    2861              : /* Get this graph's per-program-point-data for POINT if there is any,
    2862              :    otherwise nullptr.  */
    2863              : 
    2864              : per_program_point_data *
    2865            0 : exploded_graph::get_per_program_point_data (const program_point &point) const
    2866              : {
    2867            0 :   if (per_program_point_data **slot
    2868            0 :       = const_cast <point_map_t &> (m_per_point_data).get (&point))
    2869            0 :     return *slot;
    2870              : 
    2871              :   return nullptr;
    2872              : }
    2873              : 
    2874              : /* Ensure that this graph has per-call_string-data for CS;
    2875              :    borrow a pointer to it.  */
    2876              : 
    2877              : per_call_string_data *
    2878       376171 : exploded_graph::get_or_create_per_call_string_data (const call_string &cs)
    2879              : {
    2880       376171 :   if (per_call_string_data **slot = m_per_call_string_data.get (&cs))
    2881       364617 :     return *slot;
    2882              : 
    2883        23104 :   per_call_string_data *data = new per_call_string_data (cs, m_sg.m_nodes.length ());
    2884        11554 :   m_per_call_string_data.put (&data->m_key,
    2885              :                               data);
    2886        11554 :   return data;
    2887              : }
    2888              : 
    2889              : /* Ensure that this graph has per-function-data for FUN;
    2890              :    borrow a pointer to it.  */
    2891              : 
    2892              : per_function_data *
    2893          442 : exploded_graph::get_or_create_per_function_data (function *fun)
    2894              : {
    2895          442 :   if (per_function_data **slot = m_per_function_data.get (fun))
    2896           91 :     return *slot;
    2897              : 
    2898          351 :   per_function_data *data = new per_function_data ();
    2899          351 :   m_per_function_data.put (fun, data);
    2900          351 :   return data;
    2901              : }
    2902              : 
    2903              : /* Get this graph's per-function-data for FUN if there is any,
    2904              :    otherwise nullptr.  */
    2905              : 
    2906              : per_function_data *
    2907          541 : exploded_graph::get_per_function_data (function *fun) const
    2908              : {
    2909         1082 :   if (per_function_data **slot
    2910          541 :         = const_cast <per_function_data_t &> (m_per_function_data).get (fun))
    2911          452 :     return *slot;
    2912              : 
    2913              :   return nullptr;
    2914              : }
    2915              : 
    2916              : /* Return true if FUN should be traversed directly, rather than only as
    2917              :    called via other functions.  */
    2918              : 
    2919              : static bool
    2920        11661 : toplevel_function_p (const function &fun, logger *logger)
    2921              : {
    2922              :   /* Don't directly traverse into functions that have an "__analyzer_"
    2923              :      prefix.  Doing so is useful for the analyzer test suite, allowing
    2924              :      us to have functions that are called in traversals, but not directly
    2925              :      explored, thus testing how the analyzer handles calls and returns.
    2926              :      With this, we can have DejaGnu directives that cover just the case
    2927              :      of where a function is called by another function, without generating
    2928              :      excess messages from the case of the first function being traversed
    2929              :      directly.  */
    2930              : #define ANALYZER_PREFIX "__analyzer_"
    2931        11661 :   if (!strncmp (IDENTIFIER_POINTER (DECL_NAME (fun.decl)), ANALYZER_PREFIX,
    2932              :                 strlen (ANALYZER_PREFIX)))
    2933              :     {
    2934          151 :       if (logger)
    2935            0 :         logger->log ("not traversing %qE (starts with %qs)",
    2936              :                      fun.decl, ANALYZER_PREFIX);
    2937              :       return false;
    2938              :     }
    2939              : 
    2940        11510 :   if (logger)
    2941            6 :     logger->log ("traversing %qE (all checks passed)", fun.decl);
    2942              : 
    2943              :   return true;
    2944              : }
    2945              : 
    2946              : /* Custom event for use by tainted_call_info when a callback field has been
    2947              :    marked with __attribute__((tainted_args)), for labelling the field.  */
    2948              : 
    2949              : class tainted_args_field_custom_event : public custom_event
    2950              : {
    2951              : public:
    2952            4 :   tainted_args_field_custom_event (tree field)
    2953            4 :   : custom_event (event_loc_info (DECL_SOURCE_LOCATION (field), NULL_TREE, 0)),
    2954            4 :     m_field (field)
    2955              :   {
    2956            4 :   }
    2957              : 
    2958            8 :   void print_desc (pretty_printer &pp) const final override
    2959              :   {
    2960            8 :     pp_printf (&pp,
    2961              :                "field %qE of %qT"
    2962              :                " is marked with %<__attribute__((tainted_args))%>",
    2963            8 :                m_field, DECL_CONTEXT (m_field));
    2964            8 :   }
    2965              : 
    2966              : private:
    2967              :   tree m_field;
    2968              : };
    2969              : 
    2970              : /* Custom event for use by tainted_call_info when a callback field has been
    2971              :    marked with __attribute__((tainted_args)), for labelling the function used
    2972              :    in that callback.  */
    2973              : 
    2974              : class tainted_args_callback_custom_event : public custom_event
    2975              : {
    2976              : public:
    2977            4 :   tainted_args_callback_custom_event (const event_loc_info &loc_info,
    2978              :                                       tree field)
    2979              :   : custom_event (loc_info),
    2980            4 :     m_field (field)
    2981              :   {
    2982              :   }
    2983              : 
    2984            8 :   void print_desc (pretty_printer &pp) const final override
    2985              :   {
    2986            8 :     pp_printf (&pp,
    2987              :                "function %qE used as initializer for field %qE"
    2988              :                " marked with %<__attribute__((tainted_args))%>",
    2989            8 :                get_fndecl (), m_field);
    2990            8 :   }
    2991              : 
    2992              : private:
    2993              :   tree m_field;
    2994              : };
    2995              : 
    2996              : /* Custom edge info for use when adding a function used by a callback field
    2997              :    marked with '__attribute__((tainted_args))'.   */
    2998              : 
    2999              : class tainted_args_call_info : public custom_edge_info
    3000              : {
    3001              : public:
    3002           10 :   tainted_args_call_info (tree field, tree fndecl, location_t loc)
    3003           10 :   : m_field (field), m_fndecl (fndecl), m_loc (loc)
    3004              :   {}
    3005              : 
    3006            0 :   void print (pretty_printer *pp) const final override
    3007              :   {
    3008            0 :     pp_string (pp, "call to tainted field");
    3009            0 :   };
    3010              : 
    3011           13 :   bool update_model (region_model *model,
    3012              :                      const exploded_edge *eedge,
    3013              :                      region_model_context *) const final override
    3014              :   {
    3015           26 :     model->push_frame (*eedge->m_dest->get_function (),
    3016              :                        nullptr, nullptr, nullptr);
    3017           13 :     return true;
    3018              :   }
    3019              : 
    3020            4 :   void add_events_to_path (checker_path *emission_path,
    3021              :                            const exploded_edge &,
    3022              :                            pending_diagnostic &,
    3023              :                            const state_transition *) const final override
    3024              :   {
    3025              :     /* Show the field in the struct declaration, e.g.
    3026              :        "(1) field 'store' is marked with '__attribute__((tainted_args))'"  */
    3027            4 :     emission_path->add_event
    3028            4 :       (std::make_unique<tainted_args_field_custom_event> (m_field));
    3029              : 
    3030              :     /* Show the callback in the initializer
    3031              :        e.g.
    3032              :        "(2) function 'gadget_dev_desc_UDC_store' used as initializer
    3033              :        for field 'store' marked with '__attribute__((tainted_args))'".  */
    3034            4 :     emission_path->add_event
    3035            4 :       (std::make_unique<tainted_args_callback_custom_event>
    3036            4 :          (event_loc_info (m_loc, m_fndecl, 0),
    3037              :           m_field));
    3038            4 :   }
    3039              : 
    3040              : private:
    3041              :   tree m_field;
    3042              :   tree m_fndecl;
    3043              :   location_t m_loc;
    3044              : };
    3045              : 
    3046              : /* Given an initializer at LOC for FIELD marked with
    3047              :    '__attribute__((tainted_args))' initialized with FNDECL, add an
    3048              :    entrypoint to FNDECL to EG (and to its worklist) where the params to
    3049              :    FNDECL are marked as tainted.  */
    3050              : 
    3051              : static void
    3052           10 : add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl,
    3053              :                            location_t loc)
    3054              : {
    3055           10 :   logger *logger = eg->get_logger ();
    3056              : 
    3057           10 :   LOG_SCOPE (logger);
    3058              : 
    3059           10 :   if (!gimple_has_body_p (fndecl))
    3060              :     return;
    3061              : 
    3062           10 :   const extrinsic_state &ext_state = eg->get_ext_state ();
    3063              : 
    3064           10 :   function *fun = DECL_STRUCT_FUNCTION (fndecl);
    3065           10 :   gcc_assert (fun);
    3066              : 
    3067           10 :   program_point point
    3068           10 :     = program_point::from_function_entry (*ext_state.get_model_manager (),
    3069              :                                           eg->get_supergraph (), *fun);
    3070           10 :   program_state state (ext_state);
    3071           10 :   state.push_frame (ext_state, *fun);
    3072              : 
    3073           10 :   if (!mark_params_as_tainted (&state, fndecl, ext_state))
    3074              :     return;
    3075              : 
    3076           10 :   if (!state.m_valid)
    3077              :     return;
    3078              : 
    3079           10 :   exploded_node *enode = eg->get_or_create_node (point, state, nullptr);
    3080           10 :   if (logger)
    3081              :     {
    3082            0 :       if (enode)
    3083            0 :         logger->log ("created EN %i for tainted_args %qE entrypoint",
    3084            0 :                      enode->m_index, fndecl);
    3085              :       else
    3086              :         {
    3087            0 :           logger->log ("did not create enode for tainted_args %qE entrypoint",
    3088              :                        fndecl);
    3089            0 :           return;
    3090              :         }
    3091              :     }
    3092              : 
    3093           10 :   eg->add_edge (eg->get_origin (), enode, nullptr, false,
    3094           10 :                 std::make_unique<tainted_args_call_info> (field, fndecl, loc));
    3095           10 : }
    3096              : 
    3097              : /* Callback for walk_tree for finding callbacks within initializers;
    3098              :    ensure that any callback initializer where the corresponding field is
    3099              :    marked with '__attribute__((tainted_args))' is treated as an entrypoint
    3100              :    to the analysis, special-casing that the inputs to the callback are
    3101              :    untrustworthy.  */
    3102              : 
    3103              : static tree
    3104        33296 : add_any_callbacks (tree *tp, int *, void *data)
    3105              : {
    3106        33296 :   exploded_graph *eg = (exploded_graph *)data;
    3107        33296 :   if (TREE_CODE (*tp) == CONSTRUCTOR)
    3108              :     {
    3109              :       /* Find fields with the "tainted_args" attribute.
    3110              :          walk_tree only walks the values, not the index values;
    3111              :          look at the index values.  */
    3112              :       unsigned HOST_WIDE_INT idx;
    3113              :       constructor_elt *ce;
    3114              : 
    3115        21815 :       for (idx = 0; vec_safe_iterate (CONSTRUCTOR_ELTS (*tp), idx, &ce);
    3116              :            idx++)
    3117        16264 :         if (ce->index && TREE_CODE (ce->index) == FIELD_DECL)
    3118        13935 :           if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (ce->index)))
    3119              :             {
    3120           10 :               tree value = ce->value;
    3121           10 :               if (TREE_CODE (value) == ADDR_EXPR
    3122           10 :                   && TREE_CODE (TREE_OPERAND (value, 0)) == FUNCTION_DECL)
    3123           20 :                 add_tainted_args_callback (eg, ce->index,
    3124           10 :                                            TREE_OPERAND (value, 0),
    3125           10 :                                            EXPR_LOCATION (value));
    3126              :             }
    3127              :     }
    3128              : 
    3129        33296 :   return NULL_TREE;
    3130              : }
    3131              : 
    3132              : /* Add initial nodes to EG, with entrypoints for externally-callable
    3133              :    functions.  */
    3134              : 
    3135              : void
    3136         3573 : exploded_graph::build_initial_worklist ()
    3137              : {
    3138         3573 :   logger * const logger = get_logger ();
    3139         3573 :   LOG_SCOPE (logger);
    3140              : 
    3141         3573 :   cgraph_node *node;
    3142        15234 :   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
    3143              :   {
    3144        11661 :     function *fun = node->get_fun ();
    3145        11661 :     gcc_assert (fun);
    3146        11661 :     if (!toplevel_function_p (*fun, logger))
    3147          151 :       continue;
    3148        11510 :     exploded_node *enode = add_function_entry (*fun);
    3149        11510 :     if (logger)
    3150              :       {
    3151            6 :         if (enode)
    3152            6 :           logger->log ("created EN %i for %qE entrypoint",
    3153            6 :                        enode->m_index, fun->decl);
    3154              :         else
    3155            0 :           logger->log ("did not create enode for %qE entrypoint", fun->decl);
    3156              :       }
    3157              :   }
    3158              : 
    3159              :   /* Find callbacks that are reachable from global initializers.  */
    3160         3573 :   varpool_node *vpnode;
    3161        10325 :   FOR_EACH_VARIABLE (vpnode)
    3162              :     {
    3163         6752 :       tree decl = vpnode->decl;
    3164         6752 :       tree init = DECL_INITIAL (decl);
    3165         6752 :       if (!init)
    3166         1387 :         continue;
    3167         5365 :       walk_tree (&init, add_any_callbacks, this, nullptr);
    3168              :     }
    3169         3573 : }
    3170              : 
    3171              : /* The main loop of the analysis.
    3172              :    Take freshly-created exploded_nodes from the worklist, calling
    3173              :    process_node on them to explore the <point, state> graph.
    3174              :    Add edges to their successors, potentially creating new successors
    3175              :    (which are also added to the worklist).  */
    3176              : 
    3177              : void
    3178         3573 : exploded_graph::process_worklist ()
    3179              : {
    3180         3573 :   logger * const logger = get_logger ();
    3181         3573 :   LOG_SCOPE (logger);
    3182         3573 :   auto_timevar tv (TV_ANALYZER_WORKLIST);
    3183              : 
    3184       353560 :   while (m_worklist.length () > 0)
    3185              :     {
    3186       346479 :       exploded_node *node = m_worklist.take_next ();
    3187       346479 :       gcc_assert (node->get_status () == exploded_node::status::worklist);
    3188              : 
    3189       346479 :       if (logger)
    3190          110 :         logger->log ("next to process: EN: %i", node->m_index);
    3191              : 
    3192              :       /* If we have a run of nodes at the same point, try merging and
    3193              :          processing them together, rather than pairwise or individually.  */
    3194       346479 :       if (flag_analyzer_state_merge
    3195       346479 :           && node->get_point ().state_merge_at_p ())
    3196       131072 :         if (maybe_process_run_of_enodes (node))
    3197         6972 :           goto handle_limit;
    3198              : 
    3199              :       /* Avoid exponential explosions of nodes by attempting to merge
    3200              :          nodes that are at the same program point and which have
    3201              :          sufficiently similar state.  */
    3202       339507 :       if (flag_analyzer_state_merge && node != m_origin)
    3203       332330 :         if (exploded_node *node_2 = m_worklist.peek_next ())
    3204              :           {
    3205       281411 :             gcc_assert (node_2->get_status ()
    3206              :                         == exploded_node::status::worklist);
    3207       281411 :             gcc_assert (node != node_2);
    3208              : 
    3209       281411 :             if (logger)
    3210           57 :               logger->log ("peek worklist: EN: %i", node_2->m_index);
    3211              : 
    3212       281411 :             if (node->get_point () == node_2->get_point ())
    3213              :               {
    3214        28609 :                 const program_point &point = node->get_point ();
    3215        28609 :                 if (logger)
    3216              :                   {
    3217            2 :                     format f (false);
    3218            2 :                     pretty_printer *pp = logger->get_printer ();
    3219            2 :                     logger->start_log_line ();
    3220            2 :                     logger->log_partial
    3221            2 :                       ("got potential merge EN: %i and EN: %i at ",
    3222            2 :                        node->m_index, node_2->m_index);
    3223            2 :                     point.print (pp, f);
    3224            2 :                     logger->end_log_line ();
    3225              :                   }
    3226        28609 :                 const program_state &state = node->get_state ();
    3227        28609 :                 const program_state &state_2 = node_2->get_state ();
    3228              : 
    3229              :                 /* They shouldn't be equal, or we wouldn't have two
    3230              :                    separate nodes.  */
    3231        28609 :                 gcc_assert (state != state_2);
    3232              : 
    3233        28609 :                 program_state merged_state (m_ext_state);
    3234        28609 :                 if (state.can_merge_with_p (state_2, m_ext_state,
    3235              :                                             point, &merged_state))
    3236              :                   {
    3237         2722 :                     if (logger)
    3238            2 :                       logger->log ("merging EN: %i and EN: %i",
    3239            2 :                                    node->m_index, node_2->m_index);
    3240              : 
    3241         2722 :                     if (merged_state == state)
    3242              :                       {
    3243              :                         /* Then merge node_2 into node by adding an edge.  */
    3244          376 :                         add_edge (node_2, node, nullptr, false);
    3245              : 
    3246              :                         /* Remove node_2 from the worklist.  */
    3247          376 :                         m_worklist.take_next ();
    3248          376 :                         node_2->set_status (exploded_node::status::merger);
    3249              : 
    3250              :                         /* Continue processing "node" below.  */
    3251              :                       }
    3252         2346 :                     else if (merged_state == state_2)
    3253              :                       {
    3254              :                         /* Then merge node into node_2, and leave node_2
    3255              :                            in the worklist, to be processed on the next
    3256              :                            iteration.  */
    3257         1367 :                         add_edge (node, node_2, nullptr, false);
    3258         1367 :                         node->set_status (exploded_node::status::merger);
    3259         1367 :                         continue;
    3260              :                       }
    3261              :                     else
    3262              :                       {
    3263              :                         /* We have a merged state that differs from
    3264              :                            both state and state_2.  */
    3265              : 
    3266              :                         /* Remove node_2 from the worklist.  */
    3267          979 :                         m_worklist.take_next ();
    3268              : 
    3269              :                         /* Create (or get) an exploded node for the merged
    3270              :                            states, adding to the worklist.  */
    3271          979 :                         exploded_node *merged_enode
    3272          979 :                           = get_or_create_node (node->get_point (),
    3273              :                                                 merged_state, node);
    3274          979 :                         if (merged_enode == nullptr)
    3275           36 :                           continue;
    3276              : 
    3277          943 :                         if (logger)
    3278            2 :                           logger->log ("merged EN: %i and EN: %i into EN: %i",
    3279            2 :                                        node->m_index, node_2->m_index,
    3280            2 :                                        merged_enode->m_index);
    3281              : 
    3282              :                         /* "node" and "node_2" have both now been removed
    3283              :                            from the worklist; we should not process them.
    3284              : 
    3285              :                            "merged_enode" may be a new node; if so it will be
    3286              :                            processed in a subsequent iteration.
    3287              :                            Alternatively, "merged_enode" could be an existing
    3288              :                            node; one way the latter can
    3289              :                            happen is if we end up merging a succession of
    3290              :                            similar nodes into one.  */
    3291              : 
    3292              :                         /* If merged_node is one of the two we were merging,
    3293              :                            add it back to the worklist to ensure it gets
    3294              :                            processed.
    3295              : 
    3296              :                            Add edges from the merged nodes to it (but not a
    3297              :                            self-edge).  */
    3298          943 :                         if (merged_enode == node)
    3299            1 :                           m_worklist.add_node (merged_enode);
    3300              :                         else
    3301              :                           {
    3302          942 :                             add_edge (node, merged_enode, nullptr, false);
    3303          942 :                             node->set_status (exploded_node::status::merger);
    3304              :                           }
    3305              : 
    3306          943 :                         if (merged_enode == node_2)
    3307            5 :                           m_worklist.add_node (merged_enode);
    3308              :                         else
    3309              :                           {
    3310          938 :                             add_edge (node_2, merged_enode, nullptr, false);
    3311          938 :                             node_2->set_status (exploded_node::status::merger);
    3312              :                           }
    3313              : 
    3314          943 :                         continue;
    3315          943 :                       }
    3316              :                   }
    3317              : 
    3318              :                 /* TODO: should we attempt more than two nodes,
    3319              :                    or just do pairs of nodes?  (and hope that we get
    3320              :                    a cascade of mergers).  */
    3321        28609 :               }
    3322              :         }
    3323              : 
    3324       337161 :       process_node (node);
    3325              : 
    3326       344133 :     handle_limit:
    3327              :       /* Impose a hard limit on the number of exploded nodes, to ensure
    3328              :          that the analysis terminates in the face of pathological state
    3329              :          explosion (or bugs).  */
    3330       344133 :       const int limit
    3331              :         = (// Per-supernode limit:
    3332       344133 :            (m_sg.num_nodes () * param_analyzer_supernode_explosion_factor)
    3333              :            // Allow one for the "origin" enode:
    3334       344133 :            + 1);
    3335       344133 :       if (m_global_stats.m_num_nodes > limit)
    3336              :         {
    3337           65 :           if (logger)
    3338            0 :             logger->log ("bailing out; too many nodes");
    3339          195 :           warning_at (node->get_point ().get_location (),
    3340           65 :                       OPT_Wanalyzer_too_complex,
    3341              :                       "analysis bailed out early"
    3342              :                       " (%i enodes for %i snodes)",
    3343              :                       m_nodes.length (),
    3344           65 :                       m_sg.num_nodes ());
    3345           65 :           return;
    3346              :         }
    3347              :     }
    3348         3573 : }
    3349              : 
    3350              : /* Attempt to process a consecutive run of sufficiently-similar nodes in
    3351              :    the worklist at a point flagged with state_merge_at_p (having already
    3352              :    popped ENODE from the head of the worklist).
    3353              : 
    3354              :    If we have a consecutive run of enodes in the worklist all of which have
    3355              :    a single out-edge where all these out-edges are supports_bulk_merge_p and
    3356              :    all have the same successor snode and call string, then
    3357              :    process them all together, setting their status to status::bulk_merged,
    3358              :    and return true.
    3359              :    Otherwise, return false, in which case ENODE must be processed in the
    3360              :    normal way.
    3361              : 
    3362              :    When processing them all together, generate successor states based
    3363              :    on the edge op update_state_for_bulk_merger, and then attempt to merge
    3364              :    these states into a minimal set of merged successor states, partitioning
    3365              :    the inputs by merged successor state.
    3366              : 
    3367              :    Create new exploded nodes for all of the merged states, and add edges
    3368              :    connecting the input enodes to the corresponding merger exploded nodes.
    3369              : 
    3370              :    We hope we have a much smaller number of merged successor states
    3371              :    compared to the number of input enodes - ideally just one,
    3372              :    if all successor states can be merged.
    3373              : 
    3374              :    Processing and merging many together as one operation rather than as
    3375              :    pairs avoids scaling issues where per-pair mergers could bloat the
    3376              :    graph with merger nodes (especially so after switch statements).  */
    3377              : 
    3378              : bool
    3379       131072 : exploded_graph::
    3380              : maybe_process_run_of_enodes (exploded_node *enode)
    3381              : {
    3382              :   /* A struct for tracking per-input state.  */
    3383        21916 :   struct item
    3384              :   {
    3385        21916 :     item (exploded_node *input_enode)
    3386        21916 :     : m_input_enode (input_enode),
    3387        21916 :       m_processed_state (input_enode->get_state ()),
    3388        21916 :       m_merger_idx (-1)
    3389              :     {}
    3390              : 
    3391              :     exploded_node *m_input_enode;
    3392              :     program_state m_processed_state;
    3393              :     int m_merger_idx;
    3394              :   };
    3395              : 
    3396       131072 :   gcc_assert (enode->get_status () == exploded_node::status::worklist);
    3397              : 
    3398       131072 :   const program_point &src_point = enode->get_point ();
    3399       131072 :   const supernode *src_snode = src_point.get_supernode ();
    3400              : 
    3401       131072 :   logger * const logger = get_logger ();
    3402       131072 :   LOG_SCOPE (logger);
    3403              : 
    3404       131072 :   if (src_snode->m_succs.length () != 1)
    3405              :     return false;
    3406              : 
    3407       103974 :   auto sedge = src_snode->m_succs[0];
    3408              : 
    3409       103974 :   if (!sedge->supports_bulk_merge_p ())
    3410              :     return false;
    3411              : 
    3412        40132 :   const supernode *dst_snode = src_snode->m_succs[0]->m_dest;
    3413              : 
    3414              :   /* Find a run of enodes in the worklist that all have single out-sedges
    3415              :      go to the same supernode, all of which are bulk-mergeable (i.e. have
    3416              :      a simple single intraprocedural outcome).  */
    3417        40132 :   auto_vec <exploded_node *> enodes;
    3418        40132 :   enodes.safe_push (enode);
    3419        55076 :   while (exploded_node *enode_2 = m_worklist.peek_next ())
    3420              :     {
    3421        49021 :       gcc_assert (enode_2->get_status ()
    3422              :                   == exploded_node::status::worklist);
    3423        49021 :       gcc_assert (enode_2->m_succs.length () == 0);
    3424              : 
    3425        49021 :       const program_point &point_2 = enode_2->get_point ();
    3426        49021 :       const supernode *src_snode_2 = point_2.get_supernode ();
    3427              : 
    3428        49021 :       if (src_snode_2->m_succs.length () != 1)
    3429              :         break;
    3430        48207 :       auto sedge_2 = src_snode_2->m_succs[0];
    3431        48207 :       if (sedge_2->m_dest != dst_snode)
    3432              :         break;
    3433        16521 :       if (&point_2.get_call_string () != &src_point.get_call_string ())
    3434              :         break;
    3435        14944 :       if (!sedge_2->supports_bulk_merge_p ())
    3436              :         break;
    3437              : 
    3438        14944 :       enodes.safe_push (enode_2);
    3439        14944 :       m_worklist.take_next ();
    3440        14944 :     }
    3441              : 
    3442              :   /* If the only node is ENODE, then give up.  */
    3443        40132 :   if (enodes.length () == 1)
    3444              :     return false;
    3445              : 
    3446         6972 :   if (logger)
    3447            1 :     logger->log ("got run of %i bulk-mergeable enodes going to SN: %i",
    3448            1 :                  enodes.length (), dst_snode->m_id);
    3449              : 
    3450              :   /* All of these enodes have a shared intraprocedural successor point
    3451              :      (even if they were for different in-edges).  */
    3452         6972 :   program_point next_point (sedge->m_dest,
    3453         6972 :                             src_point.get_call_string ());
    3454              : 
    3455              :   /* Calculate the successor state for each enode in enodes.  */
    3456        13944 :   auto_delete_vec<item> items (enodes.length ());
    3457         6972 :   unsigned i;
    3458         6972 :   exploded_node *iter_enode;
    3459        35860 :   FOR_EACH_VEC_ELT (enodes, i, iter_enode)
    3460              :     {
    3461        21916 :       item *it = new item (iter_enode);
    3462        21916 :       items.quick_push (it);
    3463        21916 :       const program_state &state = iter_enode->get_state ();
    3464        21916 :       program_state *next_state = &it->m_processed_state;
    3465        21916 :       next_state->validate (m_ext_state);
    3466        21916 :       gcc_assert (iter_enode->get_supernode ()->m_succs.length () == 1);
    3467        21916 :       const superedge *iter_sedge = iter_enode->get_supernode ()->m_succs[0];
    3468        21916 :       if (auto op = iter_sedge->get_op ())
    3469          196 :         op->update_state_for_bulk_merger (state, *next_state);
    3470        21916 :       next_state->validate (m_ext_state);
    3471              :     }
    3472              : 
    3473              :   /* Attempt to partition the items into a set of merged states.
    3474              :      We hope we have a much smaller number of merged states
    3475              :      compared to the number of input enodes - ideally just one,
    3476              :      if all can be merged.  */
    3477         6972 :   auto_delete_vec <program_state> merged_states;
    3478         6972 :   auto_vec<item *> first_item_for_each_merged_state;
    3479         6972 :   item *it;
    3480        35860 :   FOR_EACH_VEC_ELT (items, i, it)
    3481              :     {
    3482        21916 :       const program_state &it_state = it->m_processed_state;
    3483        21916 :       program_state *merged_state;
    3484        21916 :       unsigned iter_merger_idx;
    3485        33705 :       FOR_EACH_VEC_ELT (merged_states, iter_merger_idx, merged_state)
    3486              :         {
    3487        21253 :           merged_state->validate (m_ext_state);
    3488        21253 :           program_state merge (m_ext_state);
    3489        21253 :           if (it_state.can_merge_with_p (*merged_state, m_ext_state,
    3490              :                                          next_point, &merge))
    3491              :             {
    3492         9464 :               *merged_state = merge;
    3493         9464 :               merged_state->validate (m_ext_state);
    3494         9464 :               it->m_merger_idx = iter_merger_idx;
    3495         9464 :               if (logger)
    3496            1 :                 logger->log ("reusing merger state %i for item %i (EN: %i)",
    3497            1 :                              it->m_merger_idx, i, it->m_input_enode->m_index);
    3498         9464 :               goto got_merger;
    3499              :             }
    3500        21253 :         }
    3501              :       /* If it couldn't be merged with any existing merged_states,
    3502              :          create a new one.  */
    3503        12452 :       if (it->m_merger_idx == -1)
    3504              :         {
    3505        12452 :           it->m_merger_idx = merged_states.length ();
    3506        12452 :           merged_states.safe_push (new program_state (it_state));
    3507        12452 :           first_item_for_each_merged_state.safe_push (it);
    3508        12452 :           if (logger)
    3509            1 :             logger->log ("using new merger state %i for item %i (EN: %i)",
    3510            1 :                          it->m_merger_idx, i, it->m_input_enode->m_index);
    3511              :         }
    3512            0 :     got_merger:
    3513        21916 :       gcc_assert (it->m_merger_idx >= 0);
    3514        21916 :       gcc_assert ((unsigned)it->m_merger_idx < merged_states.length ());
    3515              :     }
    3516              : 
    3517              :   /* Create merger nodes.  */
    3518        20916 :   auto_vec<exploded_node *> next_enodes (merged_states.length ());
    3519         6972 :   program_state *merged_state;
    3520        26396 :   FOR_EACH_VEC_ELT (merged_states, i, merged_state)
    3521              :     {
    3522        12452 :       exploded_node *src_enode
    3523        12452 :         = first_item_for_each_merged_state[i]->m_input_enode;
    3524        12452 :       exploded_node *next
    3525        12452 :         = get_or_create_node (next_point, *merged_state, src_enode);
    3526              :       /* "next" could be nullptr; we handle that when adding the edges below.  */
    3527        12452 :       next_enodes.quick_push (next);
    3528        12452 :       if (logger)
    3529              :         {
    3530            1 :           if (next)
    3531            1 :             logger->log ("using EN: %i for merger state %i", next->m_index, i);
    3532              :           else
    3533            0 :             logger->log ("using NULL enode for merger state %i", i);
    3534              :         }
    3535              :     }
    3536              : 
    3537              :   /* Create edges from each input enode to the appropriate successor enode.
    3538              :      Update the status of the now-processed input enodes.  */
    3539        35860 :   FOR_EACH_VEC_ELT (items, i, it)
    3540              :     {
    3541        21916 :       exploded_node *next = next_enodes[it->m_merger_idx];
    3542        21916 :       if (next)
    3543              :         {
    3544        21623 :           gcc_assert (it->m_input_enode->get_supernode ()->m_succs.length ()
    3545              :                       == 1);
    3546        21623 :           const superedge *sedge
    3547        21623 :             = it->m_input_enode->get_supernode ()->m_succs[0];
    3548        21623 :           add_edge (it->m_input_enode, next, sedge,
    3549              :                     false); /* no "work" is done during merger.  */
    3550              :         }
    3551        21916 :       it->m_input_enode->set_status (exploded_node::status::bulk_merged);
    3552              :     }
    3553              : 
    3554         6972 :   if (logger)
    3555            2 :     logger->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
    3556            1 :                  items.length (), merged_states.length (), dst_snode->m_id);
    3557              : 
    3558         6972 :   return true;
    3559       138044 : }
    3560              : 
    3561              : /* The core of exploded_graph::process_worklist (the main analysis loop),
    3562              :    handling one node in the worklist.
    3563              : 
    3564              :    Get successor <point, state> pairs for NODE, calling get_or_create on
    3565              :    them, and adding an exploded_edge to each successors.
    3566              : 
    3567              :    Freshly-created nodes will be added to the worklist.  */
    3568              : 
    3569              : void
    3570       337161 : exploded_graph::process_node (exploded_node *node)
    3571              : {
    3572       337161 :   logger * const logger = get_logger ();
    3573       337161 :   LOG_FUNC_1 (logger, "EN: %i", node->m_index);
    3574              : 
    3575       337161 :   node->set_status (exploded_node::status::processed);
    3576              : 
    3577       337161 :   const program_point &point = node->get_point ();
    3578              : 
    3579              :   /* Update cfun and input_location in case of an ICE: make it easier to
    3580              :      track down which source construct we're failing to handle.  */
    3581       670753 :   auto_cfun sentinel (node->get_function ());
    3582              : 
    3583       337161 :   input_location = node->get_location ();
    3584              : 
    3585       337161 :   const program_state &state = node->get_state ();
    3586       337161 :   if (logger)
    3587              :     {
    3588          107 :       pretty_printer *pp = logger->get_printer ();
    3589          107 :       logger->start_log_line ();
    3590          107 :       pp_string (pp, "point: ");
    3591          107 :       point.print (pp, format (false));
    3592          107 :       logger->end_log_line ();
    3593          107 :       state.dump_to_logger (*logger);
    3594              :     }
    3595              : 
    3596              :   /* Don't do anything for the origin enode; the initial population of the
    3597              :      worklist has already added successor enodes.  */
    3598       337161 :   if (point.get_supernode () == nullptr)
    3599              :     return;
    3600              : 
    3601              :   /* Specialcase for EXIT BBs, which don't have out-edges.  */
    3602       333592 :   if (point.get_supernode ()->exit_p ())
    3603              :     {
    3604        20364 :       gcc_assert (point.get_supernode ()->m_succs.length () == 0);
    3605              : 
    3606        20364 :       if (point.get_stack_depth () > 1)
    3607              :         {
    3608              :           /* Interprocedural return.  */
    3609         8193 :           auto &src_call_string = point.get_call_string ();
    3610              : 
    3611         8193 :           const call_string::element_t &top_of_stack
    3612         8193 :             = src_call_string.get_top_of_stack ();
    3613         8193 :           const call_string *dst_call_string = src_call_string.get_parent ();
    3614         8193 :           const program_point dst_point
    3615              :             (top_of_stack.get_return_snode_in_caller (),
    3616         8193 :              *dst_call_string);
    3617         8193 :           auto edge_info
    3618         8193 :             = std::make_unique<interprocedural_return> (top_of_stack.get_call_stmt ());
    3619              : 
    3620         8193 :           const program_state &src_state (node->get_state ());
    3621         8193 :           program_state dst_state (src_state);
    3622         8193 :           uncertainty_t uncertainty;
    3623         8193 :           impl_region_model_context ctxt (*this, node,
    3624              :                                           &src_state, &dst_state, &uncertainty,
    3625              :                                           nullptr,
    3626         8193 :                                           nullptr);
    3627         8193 :           edge_info->update_state (&dst_state, nullptr, &ctxt);
    3628              : 
    3629         8193 :           program_state::detect_leaks (src_state, dst_state,
    3630              :                                        nullptr, get_ext_state (),
    3631              :                                        &ctxt);
    3632              : 
    3633        16386 :           if (exploded_node *next
    3634         8193 :               = get_or_create_node (dst_point, dst_state, node))
    3635         8109 :             add_edge (node, next, nullptr, false,
    3636         8109 :                       std::move (edge_info));
    3637        16386 :         }
    3638              :       else
    3639              :         {
    3640              :           /* End of top-level of analysis for this function.
    3641              :              Detect leaks, and potentially create a function summary.  */
    3642        12171 :           node->detect_leaks (*this);
    3643              : 
    3644        12171 :           if (flag_analyzer_call_summaries
    3645        24375 :               && point.get_call_string ().empty_p ())
    3646              :             {
    3647              :               /* TODO: create function summary
    3648              :                  There can be more than one; each corresponds to a different
    3649              :                  final enode in the function.  */
    3650          442 :               if (logger)
    3651              :                 {
    3652            0 :                   pretty_printer *pp = logger->get_printer ();
    3653            0 :                   logger->log
    3654            0 :                     ("would create function summary for %qE; state: ",
    3655              :                      point.get_fndecl ());
    3656            0 :                   state.dump_to_logger (*logger);
    3657              :                 }
    3658          442 :               per_function_data *per_fn_data
    3659          442 :                 = get_or_create_per_function_data (point.get_function ());
    3660          442 :               per_fn_data->add_call_summary (node);
    3661              :             }
    3662              :         }
    3663              : 
    3664              :       return;
    3665              :     }
    3666              : 
    3667              :   /* Traverse into successors of the supernode.  */
    3668              :   int i;
    3669              :   superedge *succ;
    3670       964168 :   FOR_EACH_VEC_ELT (point.get_supernode ()->m_succs, i, succ)
    3671              :     {
    3672       338749 :       if (logger)
    3673              :         {
    3674          107 :           label_text succ_desc (succ->get_description (false));
    3675          107 :           logger->log ("considering SN: %i -> SN: %i (%s)",
    3676          107 :                        succ->m_src->m_id, succ->m_dest->m_id,
    3677              :                        succ_desc.get ());
    3678          107 :         }
    3679              : 
    3680       338749 :       program_point next_point (succ->m_dest, point.get_call_string ());
    3681       338749 :       program_state next_state (state);
    3682       338749 :       uncertainty_t uncertainty;
    3683              : 
    3684              :       /* Find the outcome(s) of any operation on the edge.  */
    3685       338749 :       operation_context op_ctxt (*this, *node, *succ);
    3686              : 
    3687              :       /* Skip EH edges.  */
    3688       338749 :       if (auto cfg_edge = succ->get_any_cfg_edge ())
    3689       116265 :         if (cfg_edge->flags & EDGE_EH)
    3690          900 :           continue;
    3691              : 
    3692       337849 :       if (auto op = succ->get_op ())
    3693       272710 :         op->execute (op_ctxt);
    3694              :       else
    3695              :         {
    3696              :           /* No-op.
    3697              :              Unconditional goto to the dst point, which
    3698              :              must be in same function.
    3699              :              The supernode changes, but the callstring and
    3700              :              state do not change.  */
    3701        65139 :           if (logger)
    3702           29 :             logger->log ("handling no-op edge");
    3703        65139 :           auto dst_point (op_ctxt.get_next_intraprocedural_point ());
    3704        65139 :           if (exploded_node *next
    3705        65139 :               = get_or_create_node (dst_point,
    3706              :                                     node->get_state (),
    3707              :                                     node))
    3708        65093 :             add_edge (node, next, succ, false);
    3709              :         }
    3710       338749 :     }
    3711       337161 : }
    3712              : 
    3713              : /* Ensure that this graph has a stats instance for FN, return it.
    3714              :    FN can be nullptr, in which case a stats instances is returned covering
    3715              :    "functionless" parts of the graph (the origin node).  */
    3716              : 
    3717              : stats *
    3718       376171 : exploded_graph::get_or_create_function_stats (function *fn)
    3719              : {
    3720       376171 :   if (!fn)
    3721         3573 :     return &m_functionless_stats;
    3722              : 
    3723       372598 :   if (stats **slot = m_per_function_stats.get (fn))
    3724       360941 :     return *slot;
    3725              :   else
    3726              :     {
    3727        11657 :       int num_supernodes = 0;
    3728      1967858 :       for (auto snode : m_sg.m_nodes)
    3729      1932887 :         if (snode->get_function () == fn)
    3730       201407 :           ++num_supernodes;
    3731        11657 :       stats *new_stats = new stats (num_supernodes);
    3732        11657 :       m_per_function_stats.put (fn, new_stats);
    3733        11657 :       return new_stats;
    3734              :     }
    3735              : }
    3736              : 
    3737              : /* Print bar charts to PP showing:
    3738              :    - the number of enodes per function, and
    3739              :    - for each function:
    3740              :      - the number of enodes per supernode/BB
    3741              :      - the number of excess enodes per supernode/BB beyond the
    3742              :        per-program-point limit, if there were any.  */
    3743              : 
    3744              : void
    3745            5 : exploded_graph::print_bar_charts (pretty_printer *pp) const
    3746              : {
    3747            5 :   cgraph_node *cgnode;
    3748              : 
    3749            5 :   pp_string (pp, "enodes per function:");
    3750            5 :   pp_newline (pp);
    3751            5 :   bar_chart enodes_per_function;
    3752           11 :   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
    3753              :     {
    3754            6 :       function *fn = cgnode->get_fun ();
    3755            6 :       const stats * const *s_ptr
    3756            6 :         = const_cast <function_stat_map_t &> (m_per_function_stats).get (fn);
    3757           12 :       enodes_per_function.add_item (function_name (fn),
    3758            6 :                                     s_ptr ? (*s_ptr)->get_total_enodes () : 0);
    3759              :     }
    3760            5 :   enodes_per_function.print (pp);
    3761              : 
    3762              :   /* Accumulate number of enodes per supernode.  */
    3763           10 :   auto_vec<unsigned> enodes_per_supernode (m_sg.m_nodes.length ());
    3764          175 :   for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
    3765           80 :     enodes_per_supernode.quick_push (0);
    3766              :   int i;
    3767              :   exploded_node *enode;
    3768          117 :   FOR_EACH_VEC_ELT (m_nodes, i, enode)
    3769              :     {
    3770          112 :       const supernode *iter_snode = enode->get_supernode ();
    3771          112 :       if (!iter_snode)
    3772            5 :         continue;
    3773          107 :       enodes_per_supernode[iter_snode->m_id]++;
    3774              :     }
    3775              : 
    3776              :   /* Accumulate excess enodes per supernode.  */
    3777           10 :   auto_vec<unsigned> excess_enodes_per_supernode (m_sg.m_nodes.length ());
    3778           90 :   for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
    3779           80 :     excess_enodes_per_supernode.quick_push (0);
    3780           83 :   for (point_map_t::iterator iter = m_per_point_data.begin ();
    3781           83 :        iter != m_per_point_data.end (); ++iter)
    3782              :     {
    3783           78 :       const program_point *point = (*iter).first;
    3784           78 :       const supernode *iter_snode = point->get_supernode ();
    3785           78 :       if (!iter_snode)
    3786            5 :         continue;
    3787           73 :       const per_program_point_data *point_data = (*iter).second;
    3788           73 :       excess_enodes_per_supernode[iter_snode->m_id]
    3789           73 :         += point_data->m_excess_enodes;
    3790              :     }
    3791              : 
    3792              :   /* Show per-function bar_charts of enodes per supernode/BB.  */
    3793            5 :   pp_string (pp, "per-function enodes per supernode/BB:");
    3794            5 :   pp_newline (pp);
    3795           11 :   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
    3796              :     {
    3797            6 :       function *fn = cgnode->get_fun ();
    3798            6 :       pp_printf (pp, "function: %qs", function_name (fn));
    3799            6 :       pp_newline (pp);
    3800              : 
    3801            6 :       bar_chart enodes_per_snode;
    3802            6 :       bar_chart excess_enodes_per_snode;
    3803            6 :       bool have_excess_enodes = false;
    3804          112 :       for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
    3805              :         {
    3806          106 :           const supernode *iter_snode = m_sg.m_nodes[i];
    3807          106 :           if (iter_snode->get_function () != fn)
    3808           26 :             continue;
    3809           80 :           pretty_printer tmp_pp;
    3810           80 :           pp_printf (&tmp_pp, "sn %i (bb %i)",
    3811           80 :                      iter_snode->m_id, iter_snode->m_bb->index);
    3812           80 :           enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
    3813           80 :                                      enodes_per_supernode[iter_snode->m_id]);
    3814           80 :           const int num_excess
    3815           80 :             = excess_enodes_per_supernode[iter_snode->m_id];
    3816           80 :           excess_enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
    3817              :                                             num_excess);
    3818           80 :           if (num_excess)
    3819            0 :             have_excess_enodes = true;
    3820           80 :         }
    3821            6 :       enodes_per_snode.print (pp);
    3822            6 :       if (have_excess_enodes)
    3823              :         {
    3824            0 :           pp_printf (pp, "EXCESS ENODES:");
    3825            0 :           pp_newline (pp);
    3826            0 :           excess_enodes_per_snode.print (pp);
    3827              :         }
    3828            6 :     }
    3829            5 : }
    3830              : 
    3831              : /* Write all stats information to this graph's logger, if any.  */
    3832              : 
    3833              : void
    3834         3573 : exploded_graph::log_stats () const
    3835              : {
    3836         3573 :   logger * const logger = get_logger ();
    3837         3573 :   if (!logger)
    3838         3568 :     return;
    3839              : 
    3840            5 :   LOG_SCOPE (logger);
    3841              : 
    3842            5 :   m_ext_state.get_engine ()->log_stats (logger);
    3843              : 
    3844           10 :   logger->log ("m_sg.num_nodes (): %i", m_sg.num_nodes ());
    3845           10 :   logger->log ("m_nodes.length (): %i", m_nodes.length ());
    3846           10 :   logger->log ("m_edges.length (): %i", m_edges.length ());
    3847            5 :   logger->log ("remaining enodes in worklist: %i", m_worklist.length ());
    3848              : 
    3849            5 :   logger->log ("global stats:");
    3850            5 :   m_global_stats.log (logger);
    3851              : 
    3852            5 :   for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
    3853           22 :        iter != m_per_function_stats.end ();
    3854            6 :        ++iter)
    3855              :     {
    3856            6 :       function *fn = (*iter).first;
    3857            6 :       log_scope s (logger, function_name (fn));
    3858            6 :       (*iter).second->log (logger);
    3859            6 :     }
    3860              : 
    3861            5 :   print_bar_charts (logger->get_printer ());
    3862            5 : }
    3863              : 
    3864              : /* Dump all stats information to OUT.  */
    3865              : 
    3866              : void
    3867            0 : exploded_graph::dump_stats (FILE *out) const
    3868              : {
    3869            0 :   fprintf (out, "m_sg.num_nodes (): %i\n", m_sg.num_nodes ());
    3870            0 :   fprintf (out, "m_nodes.length (): %i\n", m_nodes.length ());
    3871            0 :   fprintf (out, "m_edges.length (): %i\n", m_edges.length ());
    3872            0 :   fprintf (out, "remaining enodes in worklist: %i", m_worklist.length ());
    3873              : 
    3874            0 :   fprintf (out, "global stats:\n");
    3875            0 :   m_global_stats.dump (out);
    3876              : 
    3877            0 :   for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
    3878            0 :        iter != m_per_function_stats.end ();
    3879            0 :        ++iter)
    3880              :     {
    3881            0 :       function *fn = (*iter).first;
    3882            0 :       fprintf (out, "function: %s\n", function_name (fn));
    3883            0 :       (*iter).second->dump (out);
    3884              :     }
    3885            0 : }
    3886              : 
    3887              : /* Return a new json::object of the form
    3888              :    {"nodes" : [objs for enodes],
    3889              :     "edges" : [objs for eedges],
    3890              :     "ext_state": object for extrinsic_state,
    3891              :     "diagnostic_manager": object for diagnostic_manager}.  */
    3892              : 
    3893              : std::unique_ptr<json::object>
    3894            0 : exploded_graph::to_json () const
    3895              : {
    3896            0 :   auto egraph_obj = std::make_unique<json::object> ();
    3897              : 
    3898              :   /* Nodes.  */
    3899            0 :   {
    3900            0 :     auto nodes_arr = std::make_unique<json::array> ();
    3901            0 :     unsigned i;
    3902            0 :     exploded_node *n;
    3903            0 :     FOR_EACH_VEC_ELT (m_nodes, i, n)
    3904            0 :       nodes_arr->append (n->to_json (m_ext_state));
    3905            0 :     egraph_obj->set ("nodes", std::move (nodes_arr));
    3906            0 :   }
    3907              : 
    3908              :   /* Edges.  */
    3909            0 :   {
    3910            0 :     auto edges_arr = std::make_unique<json::array> ();
    3911            0 :     unsigned i;
    3912            0 :     exploded_edge *n;
    3913            0 :     FOR_EACH_VEC_ELT (m_edges, i, n)
    3914            0 :       edges_arr->append (n->to_json ());
    3915            0 :     egraph_obj->set ("edges", std::move (edges_arr));
    3916            0 :   }
    3917              : 
    3918              :   /* m_sg is JSONified at the top-level.  */
    3919              : 
    3920            0 :   egraph_obj->set ("ext_state", m_ext_state.to_json ());
    3921            0 :   egraph_obj->set ("worklist", m_worklist.to_json ());
    3922            0 :   egraph_obj->set ("diagnostic_manager", m_diagnostic_manager.to_json ());
    3923              : 
    3924              :   /* The following fields aren't yet being JSONified:
    3925              :      const state_purge_map *const m_purge_map;
    3926              :      const analysis_plan &m_plan;
    3927              :      stats m_global_stats;
    3928              :      function_stat_map_t m_per_function_stats;
    3929              :      stats m_functionless_stats;
    3930              :      call_string_data_map_t m_per_call_string_data;  */
    3931              : 
    3932            0 :   return egraph_obj;
    3933              : }
    3934              : 
    3935              : /* class feasibility_problem.  */
    3936              : 
    3937              : std::unique_ptr<text_art::tree_widget>
    3938            0 : feasibility_problem::make_dump_widget (symbolic::node_dump_state &nds) const
    3939              : {
    3940            0 :   std::unique_ptr<text_art::tree_widget> w
    3941            0 :     (text_art::tree_widget::make (nds, "feasibility_problem"));
    3942              : 
    3943            0 :   {
    3944            0 :     pretty_printer pp;
    3945            0 :     pp_printf (&pp, "edge from EN: %i to EN: %i",
    3946            0 :                m_eedge.m_src->m_index, m_eedge.m_dest->m_index);
    3947            0 :     w->add_child (text_art::tree_widget::make (nds, &pp));
    3948            0 :   }
    3949              : 
    3950            0 :   if (m_rc)
    3951              :     {
    3952            0 :       auto rc_w = (text_art::tree_widget::make (nds, "rejected_constraint"));
    3953            0 :       pretty_printer pp;
    3954            0 :       pp_format_decoder (&pp) = default_tree_printer;
    3955            0 :       m_rc->dump_to_pp (&pp);
    3956            0 :       rc_w->add_child (text_art::tree_widget::make (nds, &pp));
    3957            0 :       rc_w->add_child (m_rc->get_model ().make_dump_widget (nds));
    3958            0 :       w->add_child (std::move (rc_w));
    3959            0 :     }
    3960              : 
    3961            0 :   return w;
    3962              : }
    3963              : 
    3964              : DEBUG_FUNCTION void
    3965            0 : feasibility_problem::dump () const
    3966              : {
    3967            0 :   symbolic::dump_node_tree_to_stderr<feasibility_problem> (*this);
    3968            0 : }
    3969              : 
    3970              : void
    3971            4 : feasibility_problem::dump_to_pp (pretty_printer *pp) const
    3972              : {
    3973            4 :   text_art::theme *theme = global_dc->get_diagram_theme ();
    3974            4 :   symbolic::dump_node_tree_to_pp<feasibility_problem> (*this, theme, pp,
    3975              :                                                        true, true);
    3976            4 : }
    3977              : 
    3978              : void
    3979            0 : feasibility_problem::dump_to_logger (logger &log) const
    3980              : {
    3981            0 :   symbolic::dump_node_tree_to_logger<feasibility_problem> (*this, log);
    3982            0 : }
    3983              : 
    3984              : std::unique_ptr<json::object>
    3985            0 : feasibility_problem::to_json () const
    3986              : {
    3987            0 :   auto obj = std::make_unique<json::object> ();
    3988              : 
    3989            0 :   obj->set_integer ("eedge_idx", m_eedge_idx);
    3990            0 :   obj->set_integer ("eedge src enode", m_eedge.m_src->m_index);
    3991            0 :   obj->set_integer ("eedge dst enode", m_eedge.m_dest->m_index);
    3992            0 :   if (m_rc)
    3993            0 :     obj->set <json::object> ("rejected_constraint", m_rc->to_json ());
    3994              : 
    3995            0 :   return obj;
    3996              : }
    3997              : 
    3998              : /* class feasibility_state.  */
    3999              : 
    4000              : /* Ctor for feasibility_state, at the beginning of a path.  */
    4001              : 
    4002         6671 : feasibility_state::feasibility_state (region_model_manager *manager,
    4003              :                                       const supergraph &sg)
    4004         6671 : : m_model (manager->get_node_manager ()),
    4005        13342 :   m_snodes_visited (sg.m_nodes.length ())
    4006              : {
    4007         6671 :   bitmap_clear (m_snodes_visited);
    4008         6671 : }
    4009              : 
    4010              : /* Copy ctor for feasibility_state, for extending a path.  */
    4011              : 
    4012       296501 : feasibility_state::feasibility_state (const feasibility_state &other)
    4013       296501 : : m_model (other.m_model),
    4014       296501 :   m_snodes_visited (const_sbitmap (other.m_snodes_visited)->n_bits)
    4015              : {
    4016       296501 :   bitmap_copy (m_snodes_visited, other.m_snodes_visited);
    4017       296501 : }
    4018              : 
    4019        31207 : feasibility_state::feasibility_state (const region_model &model,
    4020              :                                       const supergraph &sg)
    4021        31207 : : m_model (model),
    4022        62414 :   m_snodes_visited (sg.m_nodes.length ())
    4023              : {
    4024        31207 :   bitmap_clear (m_snodes_visited);
    4025        31207 : }
    4026              : 
    4027              : feasibility_state &
    4028        19297 : feasibility_state::operator= (const feasibility_state &other)
    4029              : {
    4030        19297 :   m_model = other.m_model;
    4031        19297 :   bitmap_copy (m_snodes_visited, other.m_snodes_visited);
    4032        19297 :   return *this;
    4033              : }
    4034              : 
    4035              : /* The heart of feasibility-checking.
    4036              : 
    4037              :    Attempt to update this state in-place based on traversing EEDGE
    4038              :    in a path.
    4039              :    Update the model for the stmts in the src enode.
    4040              :    Attempt to add constraints for EEDGE.
    4041              : 
    4042              :    If feasible, return true.
    4043              :    Otherwise, return false and write to *OUT_RC.  */
    4044              : 
    4045              : bool
    4046       137613 : feasibility_state::
    4047              : maybe_update_for_edge (logger *logger,
    4048              :                        const exploded_edge *eedge,
    4049              :                        region_model_context *ctxt,
    4050              :                        std::unique_ptr<rejected_constraint> *out_rc)
    4051              : {
    4052       137613 :   const exploded_node &src_enode = *eedge->m_src;
    4053       137613 :   const program_point &src_point = src_enode.get_point ();
    4054       137613 :   if (logger)
    4055              :     {
    4056           44 :       logger->start_log_line ();
    4057           44 :       src_point.print (logger->get_printer (), format (false));
    4058           44 :       logger->end_log_line ();
    4059              :     }
    4060              : 
    4061       137613 :   if (eedge->m_custom_info)
    4062         7770 :     eedge->m_custom_info->update_model (&m_model, eedge, ctxt);
    4063              :   else
    4064              :     {
    4065       129843 :       const superedge *sedge = eedge->m_sedge;
    4066       129843 :       if (sedge)
    4067              :         {
    4068       122255 :           if (logger)
    4069              :             {
    4070           42 :               label_text desc (sedge->get_description (false));
    4071           42 :               logger->log ("  sedge: SN:%i -> SN:%i %s",
    4072           42 :                            sedge->m_src->m_id,
    4073           42 :                            sedge->m_dest->m_id,
    4074              :                            desc.get ());
    4075           42 :             }
    4076              : 
    4077       122255 :           if (sedge->get_op ())
    4078        91378 :             if (!sedge->get_op ()->execute_for_feasibility (*eedge,
    4079              :                                                             *this,
    4080              :                                                             ctxt,
    4081              :                                                             out_rc))
    4082              :               {
    4083         5795 :                 if (logger)
    4084              :                   {
    4085            3 :                     logger->log ("rejecting due to region model: ");
    4086            3 :                     m_model.dump_to_logger (*logger);
    4087              :                   }
    4088              :                 return false;
    4089              :               }
    4090              :         }
    4091              :       else
    4092              :         {
    4093              :           /* Special-case the initial eedge from the origin node to the
    4094              :              initial function by pushing a frame for it.  */
    4095         7588 :           if (eedge->m_src->m_index == 0)
    4096              :             {
    4097         6497 :               function *fun = eedge->m_dest->get_function ();
    4098         6497 :               gcc_assert (fun);
    4099         6497 :               m_model.push_frame (*fun, nullptr, nullptr, ctxt);
    4100         6497 :               if (logger)
    4101            2 :                 logger->log ("  pushing frame for %qD", fun->decl);
    4102              :             }
    4103              :         }
    4104              :     }
    4105              : 
    4106              : 
    4107       131818 :   {
    4108       131818 :     const exploded_node &dst_enode = *eedge->m_dest;
    4109       131818 :     const unsigned dst_snode_idx = dst_enode.get_supernode ()->m_id;
    4110       131818 :     bitmap_set_bit (m_snodes_visited, dst_snode_idx);
    4111              :   }
    4112              : 
    4113       131818 :   return true;
    4114              : }
    4115              : 
    4116              : std::unique_ptr<text_art::tree_widget>
    4117            0 : feasibility_state::make_dump_widget (symbolic::node_dump_state &nds) const
    4118              : {
    4119            0 :   using text_art::tree_widget;
    4120            0 :   std::unique_ptr<tree_widget> fs_widget
    4121            0 :     (tree_widget::from_fmt (nds, nullptr, "feasibility_state"));
    4122              : 
    4123            0 :   fs_widget->add_child (m_model.make_dump_widget (nds));
    4124              :   // TODO: m_snodes_visited;
    4125            0 :   return fs_widget;
    4126              : }
    4127              : 
    4128              : /* Dump a tree-like representation of this feasibility_state to PP.  */
    4129              : 
    4130              : void
    4131           70 : feasibility_state::dump_to_pp (pretty_printer *pp) const
    4132              : {
    4133           70 :   text_art::theme *theme = global_dc->get_diagram_theme ();
    4134           70 :   symbolic::dump_node_tree_to_pp<feasibility_state> (*this, theme, pp, true, true);
    4135           70 : }
    4136              : 
    4137              : /* A family of cluster subclasses for use when generating .dot output for
    4138              :    exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
    4139              :    enodes into hierarchical boxes.
    4140              : 
    4141              :    All functionless enodes appear in the top-level graph.
    4142              :    Every (function, call_string) pair gets its own cluster.  Within that
    4143              :    cluster, each supernode gets its own cluster.
    4144              : 
    4145              :    Hence all enodes relating to a particular function with a particular
    4146              :    callstring will be in a cluster together; all enodes for the same
    4147              :    function but with a different callstring will be in a different
    4148              :    cluster.  */
    4149              : 
    4150              : /* Base class of cluster for clustering exploded_node instances in .dot
    4151              :    output, based on various subclass-specific criteria.  */
    4152              : 
    4153         1315 : class exploded_cluster : public cluster<eg_traits>
    4154              : {
    4155              : };
    4156              : 
    4157              : /* Cluster containing all exploded_node instances for one supernode.  */
    4158              : 
    4159              : class supernode_cluster : public exploded_cluster
    4160              : {
    4161              : public:
    4162          437 :   supernode_cluster (const supernode *supernode) : m_supernode (supernode) {}
    4163              : 
    4164              :   // TODO: dtor?
    4165              : 
    4166          437 :   void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
    4167              :   {
    4168          437 :     gv->println ("subgraph \"cluster_supernode_%i\" {", m_supernode->m_id);
    4169          437 :     gv->indent ();
    4170          437 :     gv->println ("style=\"dashed\";");
    4171          874 :     gv->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
    4172          437 :                  m_supernode->m_id, m_supernode->m_bb->index,
    4173          437 :                  args.m_eg.get_scc_id (*m_supernode));
    4174              : 
    4175          437 :     int i;
    4176          437 :     exploded_node *enode;
    4177         1311 :     FOR_EACH_VEC_ELT (m_enodes, i, enode)
    4178          437 :       enode->dump_dot (gv, args);
    4179              : 
    4180              :     /* Terminate subgraph.  */
    4181          437 :     gv->outdent ();
    4182          437 :     gv->println ("}");
    4183          437 :   }
    4184              : 
    4185          437 :   void add_node (exploded_node *en) final override
    4186              :   {
    4187            0 :     m_enodes.safe_push (en);
    4188            0 :   }
    4189              : 
    4190              :   /* Comparator for use by auto_vec<supernode_cluster *>::qsort.  */
    4191              : 
    4192            0 :   static int cmp_ptr_ptr (const void *p1, const void *p2)
    4193              :   {
    4194            0 :     const supernode_cluster *c1
    4195              :       = *(const supernode_cluster * const *)p1;
    4196            0 :     const supernode_cluster *c2
    4197              :       = *(const supernode_cluster * const *)p2;
    4198            0 :     return c1->m_supernode->m_id - c2->m_supernode->m_id;
    4199              :   }
    4200              : 
    4201              : private:
    4202              :   const supernode *m_supernode;
    4203              :   auto_vec <exploded_node *> m_enodes;
    4204              : };
    4205              : 
    4206              : /* Cluster containing all supernode_cluster instances for one
    4207              :    (function, call_string) pair.  */
    4208              : 
    4209              : class function_call_string_cluster : public exploded_cluster
    4210              : {
    4211              : public:
    4212          437 :   function_call_string_cluster (function *fun, const call_string &cs)
    4213          437 :   : m_fun (fun), m_cs (cs) {}
    4214              : 
    4215          874 :   ~function_call_string_cluster ()
    4216          437 :   {
    4217          437 :     for (map_t::iterator iter = m_map.begin ();
    4218         1748 :          iter != m_map.end ();
    4219          437 :          ++iter)
    4220          437 :       delete (*iter).second;
    4221          874 :   }
    4222              : 
    4223          437 :   void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
    4224              :   {
    4225          437 :     const char *funcname = function_name (m_fun);
    4226              : 
    4227          874 :     gv->println ("subgraph \"cluster_function_%s\" {",
    4228          437 :                  IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun->decl)));
    4229          437 :     gv->indent ();
    4230          437 :     gv->write_indent ();
    4231          437 :     gv->print ("label=\"call string: ");
    4232          437 :     m_cs.print (gv->get_pp ());
    4233          437 :     gv->print (" function: %s \";", funcname);
    4234          437 :     gv->print ("\n");
    4235              : 
    4236              :     /* Dump m_map, sorting it to avoid churn when comparing dumps.  */
    4237          437 :     auto_vec<supernode_cluster *> child_clusters (m_map.elements ());
    4238          437 :     for (map_t::iterator iter = m_map.begin ();
    4239         1748 :          iter != m_map.end ();
    4240          437 :          ++iter)
    4241          437 :       child_clusters.quick_push ((*iter).second);
    4242              : 
    4243          437 :     child_clusters.qsort (supernode_cluster::cmp_ptr_ptr);
    4244              : 
    4245          437 :     unsigned i;
    4246          437 :     supernode_cluster *child_cluster;
    4247          874 :     FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
    4248          437 :       child_cluster->dump_dot (gv, args);
    4249              : 
    4250              :     /* Terminate subgraph.  */
    4251          437 :     gv->outdent ();
    4252          437 :     gv->println ("}");
    4253          437 :   }
    4254              : 
    4255          437 :   void add_node (exploded_node *en) final override
    4256              :   {
    4257          437 :     const supernode *supernode = en->get_supernode ();
    4258          437 :     gcc_assert (supernode);
    4259          437 :     supernode_cluster **slot = m_map.get (supernode);
    4260          437 :     if (slot)
    4261            0 :       (*slot)->add_node (en);
    4262              :     else
    4263              :       {
    4264          437 :         supernode_cluster *child = new supernode_cluster (supernode);
    4265          437 :         m_map.put (supernode, child);
    4266          437 :         child->add_node (en);
    4267              :       }
    4268          437 :   }
    4269              : 
    4270              :   /* Comparator for use by auto_vec<function_call_string_cluster *>.  */
    4271              : 
    4272        18054 :   static int cmp_ptr_ptr (const void *p1, const void *p2)
    4273              :   {
    4274        18054 :     const function_call_string_cluster *c1
    4275              :       = *(const function_call_string_cluster * const *)p1;
    4276        18054 :     const function_call_string_cluster *c2
    4277              :       = *(const function_call_string_cluster * const *)p2;
    4278        36108 :     if (int cmp_names
    4279        18054 :         = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1->m_fun->decl)),
    4280        18054 :                   IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2->m_fun->decl))))
    4281              :       return cmp_names;
    4282         5071 :     return call_string::cmp (c1->m_cs, c2->m_cs);
    4283              :   }
    4284              : 
    4285              : private:
    4286              :   function *m_fun;
    4287              :   const call_string &m_cs;
    4288              :   typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
    4289              :   map_t m_map;
    4290              : };
    4291              : 
    4292              : /* Keys for root_cluster.  */
    4293              : 
    4294              : struct function_call_string
    4295              : {
    4296          437 :   function_call_string (function *fun, const call_string *cs)
    4297          437 :   : m_fun (fun), m_cs (cs)
    4298              :   {
    4299          437 :     gcc_assert (fun);
    4300          437 :     gcc_assert (cs);
    4301          437 :   }
    4302              : 
    4303              :   function *m_fun;
    4304              :   const call_string *m_cs;
    4305              : };
    4306              : 
    4307              : } // namespace ana
    4308              : 
    4309              : template <> struct default_hash_traits<function_call_string>
    4310              : : public pod_hash_traits<function_call_string>
    4311              : {
    4312              :   static const bool empty_zero_p = false;
    4313              : };
    4314              : 
    4315              : template <>
    4316              : inline hashval_t
    4317         6421 : pod_hash_traits<function_call_string>::hash (value_type v)
    4318              : {
    4319         6421 :   return (pointer_hash <function>::hash (v.m_fun)
    4320         6421 :           ^ pointer_hash <const call_string>::hash (v.m_cs));
    4321              : }
    4322              : 
    4323              : template <>
    4324              : inline bool
    4325        31400 : pod_hash_traits<function_call_string>::equal (const value_type &existing,
    4326              :                                               const value_type &candidate)
    4327              : {
    4328        31400 :   return existing.m_fun == candidate.m_fun && &existing.m_cs == &candidate.m_cs;
    4329              : }
    4330              : template <>
    4331              : inline void
    4332              : pod_hash_traits<function_call_string>::mark_deleted (value_type &v)
    4333              : {
    4334              :   v.m_fun = reinterpret_cast<function *> (1);
    4335              : }
    4336              : template <>
    4337              : inline void
    4338         1932 : pod_hash_traits<function_call_string>::mark_empty (value_type &v)
    4339              : {
    4340         1932 :   v.m_fun = nullptr;
    4341              : }
    4342              : template <>
    4343              : inline bool
    4344        49193 : pod_hash_traits<function_call_string>::is_deleted (value_type v)
    4345              : {
    4346        49193 :   return v.m_fun == reinterpret_cast<function *> (1);
    4347              : }
    4348              : template <>
    4349              : inline bool
    4350       107971 : pod_hash_traits<function_call_string>::is_empty (value_type v)
    4351              : {
    4352       107534 :   return v.m_fun == nullptr;
    4353              : }
    4354              : 
    4355              : namespace ana {
    4356              : 
    4357              : /* Top-level cluster for generating .dot output for exploded graphs,
    4358              :    handling the functionless nodes, and grouping the remaining nodes by
    4359              :    callstring.  */
    4360              : 
    4361              : class root_cluster : public exploded_cluster
    4362              : {
    4363              : public:
    4364            4 :   ~root_cluster ()
    4365            4 :   {
    4366          441 :     for (map_t::iterator iter = m_map.begin ();
    4367          441 :          iter != m_map.end ();
    4368          437 :          ++iter)
    4369          437 :       delete (*iter).second;
    4370            4 :   }
    4371              : 
    4372            4 :   void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
    4373              :   {
    4374            4 :     int i;
    4375            4 :     exploded_node *enode;
    4376            8 :     FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode)
    4377            4 :       enode->dump_dot (gv, args);
    4378              : 
    4379              :     /* Dump m_map, sorting it to avoid churn when comparing dumps.  */
    4380            4 :     auto_vec<function_call_string_cluster *> child_clusters (m_map.elements ());
    4381            4 :     for (map_t::iterator iter = m_map.begin ();
    4382          441 :          iter != m_map.end ();
    4383          437 :          ++iter)
    4384          437 :       child_clusters.quick_push ((*iter).second);
    4385              : 
    4386            4 :     child_clusters.qsort (function_call_string_cluster::cmp_ptr_ptr);
    4387              : 
    4388            4 :     function_call_string_cluster *child_cluster;
    4389          445 :     FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
    4390          437 :       child_cluster->dump_dot (gv, args);
    4391            4 :   }
    4392              : 
    4393          441 :   void add_node (exploded_node *en) final override
    4394              :   {
    4395          441 :     function *fun = en->get_function ();
    4396          437 :     if (!fun)
    4397              :       {
    4398            4 :         m_functionless_enodes.safe_push (en);
    4399            4 :         return;
    4400              :       }
    4401              : 
    4402          437 :     const call_string &cs = en->get_point ().get_call_string ();
    4403          437 :     function_call_string key (fun, &cs);
    4404          437 :     function_call_string_cluster **slot = m_map.get (key);
    4405          437 :     if (slot)
    4406            0 :       (*slot)->add_node (en);
    4407              :     else
    4408              :       {
    4409          437 :         function_call_string_cluster *child
    4410          437 :           = new function_call_string_cluster (fun, cs);
    4411          437 :         m_map.put (key, child);
    4412          437 :         child->add_node (en);
    4413              :       }
    4414              :   }
    4415              : 
    4416              : private:
    4417              :   typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
    4418              :   map_t m_map;
    4419              : 
    4420              :   /* This should just be the origin exploded_node.  */
    4421              :   auto_vec <exploded_node *> m_functionless_enodes;
    4422              : };
    4423              : 
    4424              : /* Subclass of range_label for use within
    4425              :    exploded_graph::dump_exploded_nodes for implementing
    4426              :    -fdump-analyzer-exploded-nodes: a label for a specific
    4427              :    exploded_node.  */
    4428              : 
    4429              : class enode_label : public range_label
    4430              : {
    4431              :  public:
    4432            0 :   enode_label (const extrinsic_state &ext_state,
    4433              :                exploded_node *enode)
    4434            0 :   : m_ext_state (ext_state), m_enode (enode) {}
    4435              : 
    4436            0 :   label_text get_text (unsigned) const final override
    4437              :   {
    4438            0 :     return make_label_text (false, "EN: %i", m_enode->m_index);
    4439              :   }
    4440              : 
    4441              : private:
    4442              :   const extrinsic_state &m_ext_state;
    4443              :   exploded_node *m_enode;
    4444              : };
    4445              : 
    4446              : /* Postprocessing support for dumping the exploded nodes.
    4447              :    Handle -fdump-analyzer-exploded-nodes,
    4448              :    -fdump-analyzer-exploded-nodes-2, and the
    4449              :    "__analyzer_dump_exploded_nodes" builtin.  */
    4450              : 
    4451              : void
    4452         3573 : exploded_graph::dump_exploded_nodes () const
    4453              : {
    4454              :   // TODO
    4455              :   /* Locate calls to __analyzer_dump_exploded_nodes.  */
    4456              :   // Print how many egs there are for them?
    4457              :   /* Better: log them as we go, and record the exploded nodes
    4458              :      in question.  */
    4459              : 
    4460              :   /* Show every enode.  */
    4461              : 
    4462              :   /* Gather them by stmt, so that we can more clearly see the
    4463              :      "hotspots" requiring numerous exploded nodes.  */
    4464              : 
    4465              :   /* Alternatively, simply throw them all into one big rich_location
    4466              :      and see if the label-printing will sort it out...
    4467              :      This requires them all to be in the same source file.  */
    4468              : 
    4469         3573 :   if (flag_dump_analyzer_exploded_nodes)
    4470              :     {
    4471            0 :       auto_timevar tv (TV_ANALYZER_DUMP);
    4472            0 :       gcc_rich_location richloc (UNKNOWN_LOCATION);
    4473            0 :       unsigned i;
    4474            0 :       exploded_node *enode;
    4475            0 :       FOR_EACH_VEC_ELT (m_nodes, i, enode)
    4476              :         {
    4477            0 :           location_t loc = enode->get_location ();
    4478            0 :           if (get_pure_location (richloc.get_loc ()) == UNKNOWN_LOCATION)
    4479            0 :             richloc.set_range (0, loc, SHOW_RANGE_WITH_CARET);
    4480              :           else
    4481            0 :             richloc.add_range (loc,
    4482              :                                SHOW_RANGE_WITHOUT_CARET,
    4483            0 :                                new enode_label (m_ext_state, enode));
    4484              :         }
    4485            0 :       warning_at (&richloc, 0, "%i exploded nodes", m_nodes.length ());
    4486              : 
    4487              :       /* Repeat the warning without all the labels, so that message is visible
    4488              :          (the other one may well have scrolled past the terminal limit).  */
    4489            0 :       warning_at (richloc.get_loc (), 0,
    4490              :                   "%i exploded nodes", m_nodes.length ());
    4491              : 
    4492            0 :       if (m_worklist.length () > 0)
    4493            0 :         warning_at (richloc.get_loc (), 0,
    4494              :                     "worklist still contains %i nodes", m_worklist.length ());
    4495            0 :     }
    4496              : 
    4497              :   /* Dump the egraph in textual form to a dump file.  */
    4498         3573 :   if (flag_dump_analyzer_exploded_nodes_2)
    4499              :     {
    4500            0 :       auto_timevar tv (TV_ANALYZER_DUMP);
    4501            0 :       char *filename
    4502            0 :         = concat (dump_base_name, ".eg.txt", nullptr);
    4503            0 :       FILE *outf = fopen (filename, "w");
    4504            0 :       if (!outf)
    4505            0 :         error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
    4506            0 :       free (filename);
    4507              : 
    4508            0 :       fprintf (outf, "exploded graph for %s\n", dump_base_name);
    4509            0 :       fprintf (outf, "  nodes: %i\n", m_nodes.length ());
    4510            0 :       fprintf (outf, "  edges: %i\n", m_edges.length ());
    4511              : 
    4512            0 :       unsigned i;
    4513            0 :       exploded_node *enode;
    4514            0 :       FOR_EACH_VEC_ELT (m_nodes, i, enode)
    4515              :         {
    4516            0 :           fprintf (outf, "\nEN %i:\n", enode->m_index);
    4517            0 :           enode->dump_succs_and_preds (outf);
    4518            0 :           pretty_printer pp;
    4519            0 :           enode->get_point ().print (&pp, format (true));
    4520            0 :           fprintf (outf, "%s\n", pp_formatted_text (&pp));
    4521            0 :           symbolic::dump_node_tree_to_file<program_state> (enode->get_state (), outf);
    4522            0 :         }
    4523              : 
    4524            0 :       fclose (outf);
    4525            0 :     }
    4526              : 
    4527              :   /* Dump the egraph in textual form to multiple dump files, one per enode.  */
    4528         3573 :   if (flag_dump_analyzer_exploded_nodes_3)
    4529              :     {
    4530            0 :       auto_timevar tv (TV_ANALYZER_DUMP);
    4531              : 
    4532            0 :       unsigned i;
    4533            0 :       exploded_node *enode;
    4534            0 :       FOR_EACH_VEC_ELT (m_nodes, i, enode)
    4535              :         {
    4536            0 :           char *filename
    4537            0 :             = xasprintf ("%s.en-%i.txt", dump_base_name, i);
    4538            0 :           FILE *outf = fopen (filename, "w");
    4539            0 :           if (!outf)
    4540            0 :             error_at (UNKNOWN_LOCATION, "unable to open %qs for writing",
    4541              :                       filename);
    4542            0 :           free (filename);
    4543              : 
    4544            0 :           fprintf (outf, "EN %i:\n", enode->m_index);
    4545            0 :           enode->dump_succs_and_preds (outf);
    4546            0 :           pretty_printer pp;
    4547            0 :           enode->get_point ().print (&pp, format (true));
    4548            0 :           fprintf (outf, "%s\n", pp_formatted_text (&pp));
    4549            0 :           symbolic::dump_node_tree_to_file<program_state> (enode->get_state (), outf);
    4550              : 
    4551            0 :           fclose (outf);
    4552            0 :         }
    4553            0 :     }
    4554              : 
    4555              :   /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
    4556              :      giving the number of processed exploded nodes at the snode before
    4557              :      the call, and the IDs of processed, merger, and worklist enodes.
    4558              : 
    4559              :      We highlight the count of *processed* enodes since this is of most
    4560              :      interest in DejaGnu tests for ensuring that state merger has
    4561              :      happened.
    4562              : 
    4563              :      We don't show the count of merger and worklist enodes, as this is
    4564              :      more of an implementation detail of the merging/worklist that we
    4565              :      don't want to bake into our expected DejaGnu messages.  */
    4566              : 
    4567         3573 :   unsigned i;
    4568         3573 :   exploded_node *enode;
    4569         3573 :   hash_set<const gimple *> seen;
    4570       381904 :   FOR_EACH_VEC_ELT (m_nodes, i, enode)
    4571              :     {
    4572       371189 :       const supernode *snode = enode->get_supernode ();
    4573       371189 :       if (!snode)
    4574         3569 :         continue;
    4575       367620 :       if (snode->m_succs.length () != 1)
    4576        44724 :         continue;
    4577       322896 :       const superedge *sedge = snode->m_succs[0];
    4578       322896 :       if (!sedge->get_op ())
    4579        87307 :         continue;
    4580       235589 :       const call_and_return_op *op
    4581       235589 :         = sedge->get_op ()->dyn_cast_call_and_return_op ();
    4582       235589 :       if (!op)
    4583       171457 :         continue;
    4584        64132 :       const gcall &call = op->get_gcall ();
    4585        64132 :       if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes", 1))
    4586              :         {
    4587         1185 :           if (seen.contains (&call))
    4588          484 :             continue;
    4589              : 
    4590          701 :           auto_vec<exploded_node *> processed_enodes;
    4591          701 :           auto_vec<exploded_node *> merger_enodes;
    4592          701 :           auto_vec<exploded_node *> worklist_enodes;
    4593              :           /* This is O(N^2).  */
    4594          701 :           unsigned j;
    4595          701 :           exploded_node *other_enode;
    4596       126449 :           FOR_EACH_VEC_ELT (m_nodes, j, other_enode)
    4597              :             {
    4598       125047 :               if (other_enode->get_supernode () == snode)
    4599         1185 :                 switch (other_enode->get_status ())
    4600              :                   {
    4601            0 :                   default:
    4602            0 :                     gcc_unreachable ();
    4603            0 :                   case exploded_node::status::worklist:
    4604            0 :                     worklist_enodes.safe_push (other_enode);
    4605            0 :                     break;
    4606         1116 :                   case exploded_node::status::processed:
    4607         1116 :                     processed_enodes.safe_push (other_enode);
    4608         1116 :                     break;
    4609           69 :                   case exploded_node::status::merger:
    4610           69 :                     merger_enodes.safe_push (other_enode);
    4611           69 :                     break;
    4612              :                   }
    4613              :             }
    4614              : 
    4615         1402 :           pretty_printer pp;
    4616          701 :           pp_character (&pp, '[');
    4617          701 :           print_enode_indices (&pp, processed_enodes);
    4618          701 :           if (merger_enodes.length () > 0)
    4619              :             {
    4620           44 :               pp_string (&pp, "] merger(s): [");
    4621           44 :               print_enode_indices (&pp, merger_enodes);
    4622              :             }
    4623          701 :           if (worklist_enodes.length () > 0)
    4624              :             {
    4625            0 :               pp_string (&pp, "] worklist: [");
    4626            0 :               print_enode_indices (&pp, worklist_enodes);
    4627              :             }
    4628          701 :           pp_character (&pp, ']');
    4629              : 
    4630         1402 :           warning_n (call.location, 0, processed_enodes.length (),
    4631              :                      "%i processed enode: %s",
    4632              :                      "%i processed enodes: %s",
    4633              :                      processed_enodes.length (), pp_formatted_text (&pp));
    4634          701 :           seen.add (&call);
    4635              : 
    4636              :           /* If the argument is non-zero, then print all of the states
    4637              :              of the various enodes.  */
    4638          701 :           tree t_arg = fold (gimple_call_arg (&call, 0));
    4639          701 :           if (TREE_CODE (t_arg) != INTEGER_CST)
    4640              :             {
    4641            0 :               error_at (snode->m_loc,
    4642              :                         "integer constant required for arg 1");
    4643            0 :               return;
    4644              :             }
    4645          701 :           int i_arg = TREE_INT_CST_LOW (t_arg);
    4646          701 :           if (i_arg)
    4647              :             {
    4648              :               exploded_node *other_enode;
    4649          701 :               FOR_EACH_VEC_ELT (processed_enodes, j, other_enode)
    4650              :                 {
    4651            0 :                   fprintf (stderr, "%i of %i: EN %i:\n",
    4652              :                            j + 1, processed_enodes.length (),
    4653            0 :                            other_enode->m_index);
    4654            0 :                   other_enode->dump_succs_and_preds (stderr);
    4655              :                   /* Dump state.  */
    4656            0 :                   other_enode->get_state ().dump ();
    4657              :                 }
    4658              :             }
    4659          701 :         }
    4660              :     }
    4661         3573 : }
    4662              : 
    4663              : DEBUG_FUNCTION exploded_node *
    4664            0 : exploded_graph::get_node_by_index (int idx) const
    4665              : {
    4666            0 :   exploded_node *enode = m_nodes[idx];
    4667            0 :   gcc_assert (enode->m_index == idx);
    4668            0 :   return enode;
    4669              : }
    4670              : 
    4671              : /* Ensure that there is an exploded_node for a top-level call to FNDECL.  */
    4672              : 
    4673              : void
    4674          309 : exploded_graph::on_escaped_function (tree fndecl)
    4675              : {
    4676          309 :   logger * const logger = get_logger ();
    4677          309 :   LOG_FUNC_1 (logger, "%qE", fndecl);
    4678              : 
    4679          309 :   cgraph_node *cgnode = cgraph_node::get (fndecl);
    4680          309 :   if (!cgnode)
    4681              :     return;
    4682              : 
    4683          309 :   function *fun = cgnode->get_fun ();
    4684          309 :   if (!fun)
    4685              :     return;
    4686              : 
    4687          305 :   if (!gimple_has_body_p (fndecl))
    4688              :     return;
    4689              : 
    4690          305 :   exploded_node *enode = add_function_entry (*fun);
    4691          305 :   if (logger)
    4692              :     {
    4693            0 :       if (enode)
    4694            0 :         logger->log ("created EN %i for %qE entrypoint",
    4695            0 :                      enode->m_index, fun->decl);
    4696              :       else
    4697            0 :         logger->log ("did not create enode for %qE entrypoint", fun->decl);
    4698              :     }
    4699          309 : }
    4700              : 
    4701              : /* Subclass of dot_annotator for implementing
    4702              :    DUMP_BASE_NAME.supergraph.N.eg.dot, a post-analysis dump of the supergraph.
    4703              : 
    4704              :    Annotate the supergraph nodes by printing the exploded nodes in concise
    4705              :    form within them, colorizing the exploded nodes based on sm-state.
    4706              :    Also show saved diagnostics within the exploded nodes, giving information
    4707              :    on whether they were feasible, and, if infeasible, where the problem
    4708              :    was.  */
    4709              : 
    4710            4 : class exploded_graph_annotator : public dot_annotator
    4711              : {
    4712              : public:
    4713            4 :   exploded_graph_annotator (const exploded_graph &eg)
    4714            4 :   : m_eg (eg)
    4715              :   {
    4716              :     /* Avoid O(N^2) by prepopulating m_enodes_per_snode_id.  */
    4717          390 :     for (size_t i = 0; i < eg.get_supergraph ().m_nodes.length (); ++i)
    4718          191 :       m_enodes_per_snode_id.push_back (std::vector<exploded_node *> ());
    4719              :     exploded_node *enode;
    4720              :     unsigned i;
    4721          445 :     FOR_EACH_VEC_ELT (m_eg.m_nodes, i, enode)
    4722          441 :       if (enode->get_supernode ())
    4723          437 :         m_enodes_per_snode_id[enode->get_supernode ()->m_id].push_back (enode);
    4724            4 :   }
    4725              : 
    4726              :   /* Show exploded nodes for N.  */
    4727          191 :   void add_node_annotations (graphviz_out *gv, const supernode &n)
    4728              :     const final override
    4729              :   {
    4730          191 :     gv->begin_tr ();
    4731          191 :     pretty_printer *pp = gv->get_pp ();
    4732              : 
    4733          191 :     if (m_enodes_per_snode_id[n.m_id].empty ())
    4734            4 :       pp_string (pp, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
    4735              :     else
    4736              :       {
    4737              :         /* Adding an empty TD here makes the actual enodes
    4738              :            be right-aligned and tightly packed, greatly
    4739              :            improving the readability of the graph.  */
    4740          187 :         pp_string (pp, "<TD></TD>");
    4741          624 :         for (auto enode : m_enodes_per_snode_id[n.m_id])
    4742              :           {
    4743          437 :             gcc_assert (enode->get_supernode () == &n);
    4744          437 :             print_enode (gv, enode);
    4745              :           }
    4746              :       }
    4747              : 
    4748          191 :     pp_flush (pp);
    4749          191 :     gv->end_tr ();
    4750          191 :   }
    4751              : 
    4752              :   void
    4753            4 :   add_extra_objects (graphviz_out *gv) const final override
    4754              :   {
    4755            4 :     pretty_printer *pp = gv->get_pp ();
    4756              : 
    4757            4 :     pp_string (pp, "en_0 [shape=none,margin=0,style=filled,label=<<TABLE><TR>");
    4758            4 :     print_enode (gv, m_eg.m_nodes[0]);
    4759            4 :     pp_string (pp, "</TR></TABLE>>];\n\n");
    4760            4 :     pp_flush (pp);
    4761              : 
    4762            4 :     unsigned i;
    4763            4 :     exploded_edge *eedge;
    4764          461 :     FOR_EACH_VEC_ELT (m_eg.m_edges, i, eedge)
    4765              :       {
    4766          453 :         print_enode_port (pp, *eedge->m_src, "s");
    4767          453 :         pp_string (pp, " -> ");
    4768          453 :         print_enode_port (pp, *eedge->m_dest, "n");
    4769          453 :         dot::attr_list attrs;
    4770          453 :         attrs.add (dot::id ("style"), dot::id ("dotted"));
    4771          453 :         if (eedge->m_custom_info)
    4772              :           {
    4773           22 :             pretty_printer info_pp;
    4774           22 :             pp_format_decoder (&info_pp) = default_tree_printer;
    4775           22 :             eedge->m_custom_info->print (&info_pp);
    4776           22 :             attrs.add (dot::id ("label"),
    4777           44 :                        dot::id (pp_formatted_text (&info_pp)));
    4778           22 :           }
    4779          453 :         dot::writer w (*pp);
    4780          453 :         attrs.print (w);
    4781          453 :         pp_newline (pp);
    4782          453 :       }
    4783            4 :   }
    4784              : 
    4785              : private:
    4786              :   void
    4787          906 :   print_enode_port (pretty_printer *pp,
    4788              :                     const exploded_node &enode,
    4789              :                     const char *compass_pt) const
    4790              :   {
    4791          906 :     if (const supernode *snode = enode.get_supernode ())
    4792              :       {
    4793          894 :         snode->dump_dot_id (pp);
    4794          894 :         pp_printf (pp, ":en_%i:%s",
    4795          894 :                    enode.m_index, compass_pt);
    4796              :       }
    4797              :     else
    4798           12 :       pp_printf (pp, "en_%i:%s",
    4799           12 :                  enode.m_index, compass_pt);
    4800          906 :   }
    4801              : 
    4802              :   /* Concisely print a TD element for ENODE, showing the index, status,
    4803              :      and any saved_diagnostics at the enode.  Colorize it to show sm-state.
    4804              : 
    4805              :      Ideally we'd dump ENODE's state here, hidden behind some kind of
    4806              :      interactive disclosure method like a tooltip, so that the states
    4807              :      can be explored without overwhelming the graph.
    4808              :      However, I wasn't able to get graphviz/xdot to show tooltips on
    4809              :      individual elements within a HTML-like label.  */
    4810          441 :   void print_enode (graphviz_out *gv, const exploded_node *enode) const
    4811              :   {
    4812          441 :     pretty_printer *pp = gv->get_pp ();
    4813          441 :     pp_printf (pp, "<TD BGCOLOR=\"%s\">",
    4814              :                enode->get_dot_fillcolor ());
    4815          441 :     pp_printf (pp, "<TABLE BORDER=\"0\" PORT=\"en_%i\">", enode->m_index);
    4816          441 :     gv->begin_trtd ();
    4817          441 :     pp_printf (pp, "EN: %i", enode->m_index);
    4818          441 :     switch (enode->get_status ())
    4819              :       {
    4820            0 :       default:
    4821            0 :         gcc_unreachable ();
    4822            0 :       case exploded_node::status::worklist:
    4823            0 :         pp_string (pp, "(W)");
    4824            0 :         break;
    4825              :       case exploded_node::status::processed:
    4826              :         break;
    4827            6 :       case exploded_node::status::special:
    4828            6 :         pp_string (pp, "(S)");
    4829            6 :         break;
    4830           12 :       case exploded_node::status::merger:
    4831           12 :         pp_string (pp, "(M)");
    4832           12 :         break;
    4833            0 :       case exploded_node::status::bulk_merged:
    4834            0 :         pp_string (pp, "(BM)");
    4835            0 :         break;
    4836              :       }
    4837          441 :     gv->end_tdtr ();
    4838              : 
    4839              :     /* Dump any saved_diagnostics at this enode.  */
    4840          886 :     for (unsigned i = 0; i < enode->get_num_diagnostics (); i++)
    4841              :       {
    4842            4 :         const saved_diagnostic *sd = enode->get_saved_diagnostic (i);
    4843            4 :         print_saved_diagnostic (gv, sd);
    4844              :       }
    4845          441 :     pp_printf (pp, "</TABLE>");
    4846          441 :     pp_printf (pp, "</TD>");
    4847          441 :   }
    4848              : 
    4849              :   /* Print a TABLE element for SD, showing the kind, the length of the
    4850              :      exploded_path, whether the path was feasible, and if infeasible,
    4851              :      what the problem was.  */
    4852            4 :   void print_saved_diagnostic (graphviz_out *gv,
    4853              :                                const saved_diagnostic *sd) const
    4854              :   {
    4855            4 :     pretty_printer *pp = gv->get_pp ();
    4856            4 :     gv->begin_trtd ();
    4857            4 :     pp_printf (pp, "<TABLE BORDER=\"0\">");
    4858            4 :     gv->begin_tr ();
    4859            4 :     pp_string (pp, "<TD BGCOLOR=\"green\">");
    4860            4 :     pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
    4861            4 :     gv->end_tdtr ();
    4862            4 :     gv->begin_trtd ();
    4863            4 :     if (sd->get_best_epath ())
    4864            4 :       pp_printf (pp, "epath length: %i", sd->get_epath_length ());
    4865              :     else
    4866            0 :       pp_printf (pp, "no best epath");
    4867            4 :     gv->end_tdtr ();
    4868            4 :     if (const feasibility_problem *p = sd->get_feasibility_problem ())
    4869              :       {
    4870            0 :         gv->begin_trtd ();
    4871            0 :         pp_printf (pp, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
    4872            0 :                    p->m_eedge_idx,
    4873            0 :                    p->m_eedge.m_src->m_index,
    4874            0 :                    p->m_eedge.m_dest->m_index);
    4875            0 :         pp_write_text_as_html_like_dot_to_stream (pp);
    4876            0 :         gv->end_tdtr ();
    4877            0 :         gv->begin_trtd ();
    4878            0 :         p->m_eedge.m_sedge->dump (pp);
    4879            0 :         pp_write_text_as_html_like_dot_to_stream (pp);
    4880            0 :         gv->end_tdtr ();
    4881              :         /* Ideally we'd print p->m_model here; see the notes above about
    4882              :            tooltips.  */
    4883              :       }
    4884            4 :     pp_printf (pp, "</TABLE>");
    4885            4 :     gv->end_tdtr ();
    4886            4 :   }
    4887              : 
    4888              :   const exploded_graph &m_eg;
    4889              :   std::vector<std::vector <exploded_node *> > m_enodes_per_snode_id;
    4890              : };
    4891              : 
    4892              : /* Implement -fdump-analyzer-json.  */
    4893              : 
    4894              : static void
    4895            0 : dump_analyzer_json (const supergraph &sg,
    4896              :                     const exploded_graph &eg)
    4897              : {
    4898            0 :   auto_timevar tv (TV_ANALYZER_DUMP);
    4899            0 :   char *filename = concat (dump_base_name, ".analyzer.json.gz", nullptr);
    4900            0 :   gzFile output = gzopen (filename, "w");
    4901            0 :   if (!output)
    4902              :     {
    4903            0 :       error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
    4904            0 :       free (filename);
    4905            0 :       return;
    4906              :     }
    4907              : 
    4908            0 :   auto toplev_obj = std::make_unique<json::object> ();
    4909            0 :   toplev_obj->set ("sgraph", sg.to_json ());
    4910            0 :   toplev_obj->set ("egraph", eg.to_json ());
    4911              : 
    4912            0 :   pretty_printer pp;
    4913            0 :   toplev_obj->print (&pp, flag_diagnostics_json_formatting);
    4914            0 :   pp_formatted_text (&pp);
    4915              : 
    4916            0 :   if (gzputs (output, pp_formatted_text (&pp)) == EOF
    4917            0 :       || gzclose (output))
    4918            0 :     error_at (UNKNOWN_LOCATION, "error writing %qs", filename);
    4919              : 
    4920            0 :   free (filename);
    4921            0 : }
    4922              : 
    4923              : /* Concrete subclass of on_ana_init, allowing plugins to register
    4924              :    new state machines.  */
    4925              : 
    4926              : class impl_on_ana_init : public gcc::topics::analyzer_events::on_ana_init
    4927              : {
    4928              : public:
    4929           38 :   impl_on_ana_init (std::vector<std::unique_ptr<state_machine>> &checkers,
    4930              :                     known_function_manager &known_fn_mgr,
    4931              :                     logger *logger)
    4932           38 :   : m_checkers (checkers),
    4933           38 :     m_known_fn_mgr (known_fn_mgr),
    4934           38 :     m_logger (logger)
    4935              :   {}
    4936              : 
    4937              :   void
    4938            1 :   register_state_machine (std::unique_ptr<state_machine> sm)
    4939              :     const final override
    4940              :   {
    4941            1 :     LOG_SCOPE (m_logger);
    4942            1 :     m_checkers.push_back (std::move (sm));
    4943            1 :   }
    4944              : 
    4945              :   void
    4946          107 :   register_known_function (const char *name,
    4947              :                            std::unique_ptr<known_function> kf)
    4948              :     const final override
    4949              :   {
    4950          107 :     LOG_SCOPE (m_logger);
    4951          107 :     m_known_fn_mgr.add (name, std::move (kf));
    4952          107 :   }
    4953              : 
    4954              :   logger *
    4955           38 :   get_logger () const final override
    4956              :   {
    4957           38 :     return m_logger;
    4958              :   }
    4959              : 
    4960              : private:
    4961              :   std::vector<std::unique_ptr<state_machine>> &m_checkers;
    4962              :   known_function_manager &m_known_fn_mgr;
    4963              :   logger *m_logger;
    4964              : };
    4965              : 
    4966              : static void
    4967        14296 : maybe_dump_supergraph (const supergraph &sg, const char *name,
    4968              :                        const dot_annotator *annotator = nullptr,
    4969              :                        const exploded_graph *eg = nullptr)
    4970              : {
    4971        14296 :   static int dump_idx = 0;
    4972        14296 :   if (!flag_dump_analyzer_supergraph)
    4973        14276 :     return;
    4974              : 
    4975           20 :   auto_timevar tv (TV_ANALYZER_DUMP);
    4976           20 :   std::string filename (dump_base_name);
    4977           20 :   filename += ".supergraph.";
    4978           40 :   filename += std::to_string (dump_idx++);
    4979           20 :   filename += ".";
    4980           20 :   filename += name;
    4981           20 :   filename += ".dot";
    4982           20 :   supergraph::dump_args_t args
    4983              :     ((enum supergraph_dot_flags)SUPERGRAPH_DOT_SHOW_BBS,
    4984              :      annotator,
    4985           20 :      eg);
    4986           20 :   sg.dump_dot (filename.c_str (), args);
    4987           20 : }
    4988              : 
    4989              : /* Run the analysis "engine".  */
    4990              : 
    4991              : void
    4992         3573 : impl_run_checkers (logger *logger)
    4993              : {
    4994         3573 :   LOG_SCOPE (logger);
    4995              : 
    4996         3573 :   if (logger)
    4997              :     {
    4998            5 :       logger->log ("BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN ? 1 : 0);
    4999            5 :       logger->log ("BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN ? 1 : 0);
    5000            5 :       logger->log ("WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN ? 1 : 0);
    5001            5 :       log_stashed_constants (logger);
    5002              :     }
    5003              : 
    5004              :   /* If using LTO, ensure that the cgraph nodes have function bodies.  */
    5005         3573 :   cgraph_node *node;
    5006        15234 :   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
    5007        11661 :     node->get_untransformed_body ();
    5008              : 
    5009         3573 :   symbolic::node_manager node_mgr;
    5010         3573 :   auto &mgr = node_mgr.get_region_model_manager ();
    5011              : 
    5012              :   /* Create the supergraph.  */
    5013         3573 :   supergraph sg (mgr, logger);
    5014              : 
    5015         3573 :   maybe_dump_supergraph (sg, "original");
    5016              : 
    5017         3573 :   sg.fixup_locations (logger);
    5018              : 
    5019         3573 :   maybe_dump_supergraph (sg, "fixup-locations");
    5020              : 
    5021         3573 :   engine eng (node_mgr, &sg);
    5022              : 
    5023         3573 :   state_purge_map *purge_map = nullptr;
    5024         3573 :   if (flag_analyzer_state_purge)
    5025         3562 :     purge_map = new state_purge_map (sg, eng.get_model_manager (), logger);
    5026              : 
    5027         3573 :   if (flag_analyzer_simplify_supergraph)
    5028              :     {
    5029         3573 :       sg.simplify (logger);
    5030         3573 :       maybe_dump_supergraph (sg, "simplified");
    5031              :     }
    5032              : 
    5033         3573 :   sg.sort_nodes (logger);
    5034         3573 :   maybe_dump_supergraph (sg, "sorted");
    5035              : 
    5036         3573 :   if (flag_dump_analyzer_state_purge)
    5037              :     {
    5038            4 :       auto_timevar tv (TV_ANALYZER_DUMP);
    5039            4 :       state_purge_annotator a (purge_map);
    5040            4 :       char *filename = concat (dump_base_name, ".state-purge.dot", nullptr);
    5041            4 :       supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a, nullptr);
    5042            4 :       sg.dump_dot (filename, args);
    5043            4 :       free (filename);
    5044            4 :     }
    5045              : 
    5046         3573 :   auto checkers = make_checkers (logger);
    5047              : 
    5048         3573 :   register_known_functions (*eng.get_known_function_manager (),
    5049         3573 :                             *eng.get_model_manager ());
    5050              : 
    5051         3573 :   if (auto channel
    5052         3573 :         = g->get_channels ().analyzer_events_channel.get_if_active ())
    5053           38 :     channel->publish (impl_on_ana_init (checkers,
    5054           38 :                                         *eng.get_known_function_manager (),
    5055           38 :                                         logger));
    5056              : 
    5057         3573 :   if (logger)
    5058              :     {
    5059            5 :       int i = 0;
    5060           40 :       for (auto &sm : checkers)
    5061           35 :         logger->log ("checkers[%i]: %s", ++i, sm->get_name ());
    5062              :     }
    5063              : 
    5064              :   /* Extrinsic state shared by nodes in the graph.  */
    5065         3573 :   const extrinsic_state ext_state (std::move (checkers), &eng, logger);
    5066              : 
    5067         3573 :   const analysis_plan plan (sg, logger);
    5068              : 
    5069              :   /* The exploded graph.  */
    5070         3573 :   exploded_graph eg (sg, logger, ext_state, purge_map, plan,
    5071         3573 :                      analyzer_verbosity);
    5072              : 
    5073              :   /* Add entrypoints to the graph for externally-callable functions.  */
    5074         3573 :   eg.build_initial_worklist ();
    5075              : 
    5076              :   /* Now process the worklist, exploring the <point, state> graph.  */
    5077         3573 :   eg.process_worklist ();
    5078              : 
    5079         3573 :   if (warn_analyzer_infinite_loop)
    5080         3573 :     eg.detect_infinite_loops ();
    5081              : 
    5082         3573 :   if (flag_dump_analyzer_exploded_graph)
    5083              :     {
    5084            4 :       auto_timevar tv (TV_ANALYZER_DUMP);
    5085            4 :       char *filename
    5086            4 :         = concat (dump_base_name, ".eg.dot", nullptr);
    5087            4 :       exploded_graph::dump_args_t args (eg);
    5088            4 :       root_cluster c;
    5089            4 :       eg.dump_dot (filename, &c, args);
    5090            4 :       free (filename);
    5091            4 :     }
    5092              : 
    5093              :   /* Now emit any saved diagnostics.  */
    5094         3573 :   eg.get_diagnostic_manager ().emit_saved_diagnostics (eg);
    5095              : 
    5096         3573 :   eg.dump_exploded_nodes ();
    5097              : 
    5098         3573 :   eg.log_stats ();
    5099              : 
    5100         3573 :   if (flag_dump_analyzer_supergraph)
    5101              :     {
    5102              :       /* Dump post-analysis form of supergraph.  */
    5103            4 :       exploded_graph_annotator a (eg);
    5104            4 :       maybe_dump_supergraph (sg, "eg", &a, &eg);
    5105            4 :     }
    5106              : 
    5107         3573 :   if (flag_dump_analyzer_json)
    5108            0 :     dump_analyzer_json (sg, eg);
    5109              : 
    5110         3573 :   if (flag_dump_analyzer_untracked)
    5111           23 :     eng.get_model_manager ()->dump_untracked_regions ();
    5112              : 
    5113         3573 :   if (auto channel
    5114         3573 :         = g->get_channels ().analyzer_events_channel.get_if_active ())
    5115           38 :     channel->publish (gcc::topics::analyzer_events::on_ana_done {eng, eg});
    5116              : 
    5117         3573 :   delete purge_map;
    5118              : 
    5119              :   /* Free up any dominance info that we may have created.  */
    5120        15234 :   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
    5121              :     {
    5122        11661 :       function *fun = node->get_fun ();
    5123        11661 :       free_dominance_info (fun, CDI_DOMINATORS);
    5124              :     }
    5125         3573 : }
    5126              : 
    5127              : /* Handle -fdump-analyzer and -fdump-analyzer-stderr.  */
    5128              : static FILE *dump_fout = nullptr;
    5129              : 
    5130              : /* Track if we're responsible for closing dump_fout.  */
    5131              : static bool owns_dump_fout = false;
    5132              : 
    5133              : /* If dumping is enabled, attempt to create dump_fout if it hasn't already
    5134              :    been opened.  Return it.  */
    5135              : 
    5136              : FILE *
    5137         7189 : get_or_create_any_logfile ()
    5138              : {
    5139         7189 :   if (!dump_fout)
    5140              :     {
    5141         7184 :       if (flag_dump_analyzer_stderr)
    5142            0 :         dump_fout = stderr;
    5143         7184 :       else if (flag_dump_analyzer)
    5144              :         {
    5145            5 :           char *dump_filename = concat (dump_base_name, ".analyzer.txt", nullptr);
    5146            5 :           dump_fout = fopen (dump_filename, "w");
    5147            5 :           free (dump_filename);
    5148            5 :           if (dump_fout)
    5149            5 :             owns_dump_fout = true;
    5150              :         }
    5151              :      }
    5152         7189 :   return dump_fout;
    5153              : }
    5154              : 
    5155              : /* External entrypoint to the analysis "engine".
    5156              :    Set up any dumps, then call impl_run_checkers.  */
    5157              : 
    5158              : void
    5159         3573 : run_checkers ()
    5160              : {
    5161              :   /* Save input_location.  */
    5162         3573 :   location_t saved_input_location = input_location;
    5163              : 
    5164         3573 :   {
    5165         3573 :     log_user the_logger (nullptr);
    5166         3573 :     get_or_create_any_logfile ();
    5167         3573 :     if (dump_fout)
    5168            5 :       the_logger.set_logger (new logger (dump_fout, 0, 0,
    5169            5 :                                          *global_dc->get_reference_printer ()));
    5170         3573 :     LOG_SCOPE (the_logger.get_logger ());
    5171              : 
    5172         3573 :     impl_run_checkers (the_logger.get_logger ());
    5173              : 
    5174              :     /* end of lifetime of the_logger (so that dump file is closed after the
    5175              :        various dtors run).  */
    5176         3573 :   }
    5177              : 
    5178         3573 :   if (owns_dump_fout)
    5179              :     {
    5180            5 :       fclose (dump_fout);
    5181            5 :       owns_dump_fout = false;
    5182            5 :       dump_fout = nullptr;
    5183              :     }
    5184              : 
    5185              :   /* Restore input_location.  Subsequent passes may assume that input_location
    5186              :      is some arbitrary value *not* in the block tree, which might be violated
    5187              :      if we didn't restore it.  */
    5188         3573 :   input_location = saved_input_location;
    5189         3573 : }
    5190              : 
    5191              : } // namespace ana
    5192              : 
    5193              : #endif /* #if ENABLE_ANALYZER */
        

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.