LCOV - code coverage report
Current view: top level - gcc/analyzer - diagnostic-manager.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 87.2 % 1337 1166
Test Date: 2026-11-14 16:39:50 Functions: 96.2 % 78 75
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Classes for saving, deduplicating, and emitting analyzer diagnostics.
       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 "cfg.h"
      24              : #include "gimple-pretty-print.h"
      25              : #include "gimple-iterator.h"
      26              : #include "inlining-iterator.h"
      27              : #include "cgraph.h"
      28              : #include "digraph.h"
      29              : #include "gcc-rich-location.h"
      30              : #include "diagnostics/sarif-sink.h"
      31              : 
      32              : #include "analyzer/analyzer-logging.h"
      33              : #include "analyzer/sm.h"
      34              : #include "analyzer/pending-diagnostic.h"
      35              : #include "analyzer/diagnostic-manager.h"
      36              : #include "analyzer/call-string.h"
      37              : #include "analyzer/program-point.h"
      38              : #include "analyzer/store.h"
      39              : #include "analyzer/region-model.h"
      40              : #include "analyzer/constraint-manager.h"
      41              : #include "analyzer/supergraph.h"
      42              : #include "analyzer/program-state.h"
      43              : #include "analyzer/exploded-graph.h"
      44              : #include "analyzer/exploded-path.h"
      45              : #include "analyzer/trimmed-graph.h"
      46              : #include "analyzer/feasible-graph.h"
      47              : #include "analyzer/checker-path.h"
      48              : #include "analyzer/reachability.h"
      49              : 
      50              : #if ENABLE_ANALYZER
      51              : 
      52              : namespace ana {
      53              : 
      54              : class feasible_worklist;
      55              : 
      56              : // struct pending_location
      57              : 
      58          755 : pending_location::pending_location ()
      59          755 : : m_enode (nullptr),
      60          755 :   m_event_loc_info (UNKNOWN_LOCATION, NULL_TREE, 0)
      61              : {
      62          755 : }
      63              : 
      64         7073 : pending_location::pending_location (exploded_node *enode)
      65         7073 : : m_enode (enode),
      66         7073 :   m_event_loc_info (enode)
      67              : {
      68         7073 : }
      69              : 
      70         3915 : pending_location::pending_location (exploded_node *enode,
      71              :                                     location_t loc)
      72         3915 : : m_enode (enode),
      73         3915 :   m_event_loc_info (enode)
      74              : {
      75         3915 :   m_event_loc_info.m_loc = loc;
      76         3915 : }
      77              : 
      78              : std::unique_ptr<json::object>
      79           38 : pending_location::to_json () const
      80              : {
      81           38 :   auto ploc_obj = std::make_unique<json::object> ();
      82              : 
      83           38 :   if (m_enode)
      84           38 :     ploc_obj->set_integer ("enode", m_enode->m_index);
      85              :   // TODO: also store m_event_loc_info
      86           38 :   return ploc_obj;
      87              : }
      88              : 
      89              : /* State for finding the shortest feasible exploded_path for a
      90              :    saved_diagnostic.
      91              :    This is shared between all diagnostics, so that we avoid repeating work.  */
      92              : 
      93              : class epath_finder
      94              : {
      95              : public:
      96         1650 :   epath_finder (const exploded_graph &eg)
      97         1650 :   : m_eg (eg),
      98         1650 :     m_sep (nullptr)
      99              :   {
     100              :     /* This is shared by all diagnostics, but only needed if
     101              :        !flag_analyzer_feasibility.  */
     102         1650 :     if (!flag_analyzer_feasibility)
     103            4 :       m_sep = new shortest_exploded_paths (eg, eg.get_origin (),
     104            4 :                                            SPS_FROM_GIVEN_ORIGIN);
     105         1650 :   }
     106              : 
     107         1654 :   ~epath_finder () { delete m_sep; }
     108              : 
     109       129594 :   logger *get_logger () const { return m_eg.get_logger (); }
     110              : 
     111              :   std::unique_ptr<exploded_path>
     112              :   get_best_epath (const exploded_node *target_enode,
     113              :                   const pending_diagnostic &pd,
     114              :                   const char *desc, unsigned diag_idx,
     115              :                   std::unique_ptr<feasibility_problem> *out_problem);
     116              : 
     117              : private:
     118              :   DISABLE_COPY_AND_ASSIGN(epath_finder);
     119              : 
     120              :   std::unique_ptr<exploded_path>
     121              :   explore_feasible_paths (const exploded_node *target_enode,
     122              :                           const pending_diagnostic &pd,
     123              :                           const char *desc, unsigned diag_idx);
     124              :   bool
     125              :   process_worklist_item (feasible_worklist *worklist,
     126              :                          const trimmed_graph &tg,
     127              :                          feasible_graph *fg,
     128              :                          const exploded_node *target_enode,
     129              :                          const pending_diagnostic &pd,
     130              :                          unsigned diag_idx,
     131              :                          std::unique_ptr<exploded_path> *out_best_path) const;
     132              :   void dump_trimmed_graph (const exploded_node *target_enode,
     133              :                            const char *desc, unsigned diag_idx,
     134              :                            const trimmed_graph &tg,
     135              :                            const shortest_paths<eg_traits, exploded_path> &sep);
     136              :   void dump_feasible_graph (const exploded_node *target_enode,
     137              :                             const char *desc, unsigned diag_idx,
     138              :                             const feasible_graph &fg);
     139              :   void dump_feasible_path (const exploded_node *target_enode,
     140              :                            unsigned diag_idx,
     141              :                            const feasible_graph &fg,
     142              :                            const feasible_node &fnode) const;
     143              : 
     144              :   const exploded_graph &m_eg;
     145              :   shortest_exploded_paths *m_sep;
     146              : };
     147              : 
     148              : /* class epath_finder.  */
     149              : 
     150              : /* Get the "best" exploded_path for reaching TARGET_ENODE from the origin,
     151              :    returning ownership of it to the caller.
     152              : 
     153              :    Ideally we want to report the shortest feasible path.
     154              :    Return nullptr if we could not find a feasible path
     155              :    (when flag_analyzer_feasibility is true).
     156              : 
     157              :    If flag_analyzer_feasibility is false, then simply return the
     158              :    shortest path.
     159              : 
     160              :    Use DESC and DIAG_IDX when logging.
     161              : 
     162              :    Write any feasibility_problem to *OUT_PROBLEM.  */
     163              : 
     164              : std::unique_ptr<exploded_path>
     165         6671 : epath_finder::get_best_epath (const exploded_node *target_enode,
     166              :                               const pending_diagnostic &pd,
     167              :                               const char *desc, unsigned diag_idx,
     168              :                               std::unique_ptr<feasibility_problem> *out_problem)
     169              : {
     170         6671 :   logger *logger = get_logger ();
     171         6671 :   LOG_SCOPE (logger);
     172              : 
     173         6671 :   unsigned snode_id = target_enode->get_supernode ()->m_id;
     174         6671 :   if (logger)
     175            2 :     logger->log ("considering %qs at EN: %i, SN: %i (sd: %i)",
     176            2 :                  desc, target_enode->m_index, snode_id, diag_idx);
     177              : 
     178              :   /* State-merging means that not every path in the egraph corresponds
     179              :      to a feasible one w.r.t. states.
     180              : 
     181              :      We want to find the shortest feasible path from the origin to ENODE
     182              :      in the egraph.  */
     183              : 
     184         6671 :   if (flag_analyzer_feasibility)
     185              :     {
     186              :       /* Attempt to find the shortest feasible path using feasible_graph.  */
     187         6667 :       if (logger)
     188            2 :         logger->log ("trying to find shortest feasible path");
     189         6667 :       if (std::unique_ptr<exploded_path> epath
     190         6667 :             = explore_feasible_paths (target_enode, pd, desc, diag_idx))
     191              :         {
     192         6447 :           if (logger)
     193            2 :             logger->log ("accepting %qs at EN: %i, SN: %i (sd: %i)"
     194              :                          " with feasible path (length: %i)",
     195            2 :                          desc, target_enode->m_index, snode_id, diag_idx,
     196              :                          epath->length ());
     197         6447 :           return epath;
     198              :         }
     199              :       else
     200              :         {
     201          220 :           if (logger)
     202            0 :             logger->log ("rejecting %qs at EN: %i, SN: %i (sd: %i)"
     203              :                          " due to not finding feasible path",
     204            0 :                          desc, target_enode->m_index, snode_id, diag_idx);
     205          220 :           return nullptr;
     206         6667 :         }
     207              :     }
     208              :   else
     209              :     {
     210              :       /* As a crude approximation to shortest feasible path, simply find
     211              :          the shortest path, and note whether it is feasible.
     212              :          There could be longer feasible paths within the egraph, so this
     213              :          approach would lead to diagnostics being falsely rejected
     214              :          (PR analyzer/96374).  */
     215            4 :       if (logger)
     216            0 :         logger->log ("trying to find shortest path ignoring feasibility");
     217            4 :       gcc_assert (m_sep);
     218            4 :       auto epath
     219              :         = std::make_unique<exploded_path>
     220            4 :             (m_sep->get_shortest_path (target_enode));
     221            4 :       if (epath->feasible_p (logger, out_problem, m_eg.get_engine (), &m_eg))
     222              :         {
     223            0 :           if (logger)
     224            0 :             logger->log ("accepting %qs at EN: %i, SN: %i (sn: %i)"
     225              :                          " with feasible path (length: %i)",
     226            0 :                          desc, target_enode->m_index, snode_id, diag_idx,
     227              :                          epath->length ());
     228              :         }
     229              :       else
     230              :         {
     231            4 :           if (logger)
     232            0 :             logger->log ("accepting %qs at EN: %i, SN: %i (sn: %i) (length: %i)"
     233              :                          " despite infeasible path (due to %qs)",
     234            0 :                          desc, target_enode->m_index, snode_id, diag_idx,
     235              :                          epath->length (),
     236              :                          "-fno-analyzer-feasibility");
     237              :         }
     238            4 :       return epath;
     239            4 :     }
     240         6671 : }
     241              : 
     242              : /* A class for managing the worklist of feasible_nodes in
     243              :    epath_finder::explore_feasible_paths, prioritizing them
     244              :    so that shorter paths appear earlier in the queue.  */
     245              : 
     246        13334 : class feasible_worklist
     247              : {
     248              : public:
     249         6667 :   feasible_worklist (const shortest_paths<eg_traits, exploded_path> &sep)
     250        13334 :   : m_queue (key_t (*this, nullptr)),
     251         6667 :     m_sep (sep)
     252              :   {
     253         6667 :   }
     254              : 
     255       109585 :   feasible_node *take_next () { return m_queue.extract_min (); }
     256              : 
     257       111660 :   void add_node (feasible_node *fnode)
     258              :   {
     259       223320 :     m_queue.insert (key_t (*this, fnode), fnode);
     260              :   }
     261              : 
     262              : private:
     263              :   struct key_t
     264              :   {
     265       118327 :     key_t (const feasible_worklist &w, feasible_node *fnode)
     266         6667 :     : m_worklist (w), m_fnode (fnode)
     267              :     {}
     268              : 
     269        60736 :     bool operator< (const key_t &other) const
     270              :     {
     271        60736 :       return cmp (*this, other) < 0;
     272              :     }
     273              : 
     274        14262 :     bool operator== (const key_t &other) const
     275              :     {
     276        14262 :       return cmp (*this, other) == 0;
     277              :     }
     278              : 
     279        14262 :     bool operator> (const key_t &other) const
     280              :     {
     281        14262 :       return !(*this == other || *this < other);
     282              :     }
     283              : 
     284              :   private:
     285        74998 :     static int cmp (const key_t &ka, const key_t &kb)
     286              :     {
     287              :       /* Choose the node for which if the remaining path were feasible,
     288              :          it would be the shortest path (summing the length of the
     289              :          known-feasible path so far with that of the remaining
     290              :          possibly-feasible path).  */
     291        74998 :       int ca = ka.m_worklist.get_estimated_cost (ka.m_fnode);
     292        74998 :       int cb = kb.m_worklist.get_estimated_cost (kb.m_fnode);
     293        74998 :       return ca - cb;
     294              :     }
     295              : 
     296              :     const feasible_worklist &m_worklist;
     297              :     feasible_node *m_fnode;
     298              :   };
     299              : 
     300              :   /* Get the estimated length of a path involving FNODE from
     301              :      the origin to the target enode.
     302              :      Sum the length of the known-feasible path so far with
     303              :      that of the remaining possibly-feasible path.  */
     304              : 
     305       149996 :   int get_estimated_cost (const feasible_node *fnode) const
     306              :   {
     307       149996 :     unsigned length_so_far = fnode->get_path_length ();
     308       149996 :     int shortest_remaining_path
     309       149996 :       = m_sep.get_shortest_distance (fnode->get_inner_node ());
     310              : 
     311       149996 :     gcc_assert (shortest_remaining_path >= 0);
     312              :     /* This should be true since we're only exploring nodes within
     313              :        the trimmed graph (and we anticipate it being much smaller
     314              :        than this, and thus not overflowing the sum).  */
     315       149996 :     gcc_assert (shortest_remaining_path < INT_MAX);
     316              : 
     317       149996 :     return length_so_far + shortest_remaining_path;
     318              :   }
     319              : 
     320              :   /* Priority queue, backed by a fibonacci_heap.  */
     321              :   typedef fibonacci_heap<key_t, feasible_node> queue_t;
     322              :   queue_t m_queue;
     323              :   const shortest_paths<eg_traits, exploded_path> &m_sep;
     324              : };
     325              : 
     326              : /* When we're building the exploded graph we want to simplify
     327              :    overly-complicated symbolic values down to "UNKNOWN" to try to avoid
     328              :    state explosions and unbounded chains of exploration.
     329              : 
     330              :    However, when we're building the feasibility graph for a diagnostic
     331              :    (actually a tree), we don't want UNKNOWN values, as conditions on them
     332              :    are also unknown: we don't want to have a contradiction such as a path
     333              :    where (VAL != 0) and then (VAL == 0) along the same path.
     334              : 
     335              :    Hence this is an RAII class for temporarily disabling complexity-checking
     336              :    in the region_model_manager, for use within
     337              :    epath_finder::explore_feasible_paths.
     338              : 
     339              :    We also disable the creation of unknown_svalue instances during feasibility
     340              :    checking, instead creating unique svalues, to avoid paradoxes in paths.  */
     341              : 
     342              : class auto_checking_feasibility
     343              : {
     344              : public:
     345         6667 :   auto_checking_feasibility (region_model_manager *mgr) : m_mgr (mgr)
     346              :   {
     347         6667 :     m_mgr->begin_checking_feasibility ();
     348              :   }
     349         6667 :   ~auto_checking_feasibility ()
     350              :   {
     351         6667 :     m_mgr->end_checking_feasibility ();
     352              :   }
     353              : private:
     354              :   region_model_manager *m_mgr;
     355              : };
     356              : 
     357              : /* Attempt to find the shortest feasible path from the origin to
     358              :    TARGET_ENODE by iteratively building a feasible_graph, in which
     359              :    every path to a feasible_node is feasible by construction.
     360              : 
     361              :    We effectively explore the tree of feasible paths in order of shortest
     362              :    path until we either find a feasible path to TARGET_ENODE, or hit
     363              :    a limit and give up.
     364              : 
     365              :    Preliminaries:
     366              :    - Find the shortest path from each node to the TARGET_ENODE (without
     367              :    checking feasibility), so that we can prioritize our worklist.
     368              :    - Construct a trimmed_graph: the subset of nodes/edges that
     369              :    are on a path that eventually reaches TARGET_ENODE.  We will only need
     370              :    to consider these when considering the shortest feasible path.
     371              : 
     372              :    Build a feasible_graph, in which every path to a feasible_node
     373              :    is feasible by construction.
     374              :    We use a worklist to flatten the exploration into an iteration.
     375              :    Starting at the origin, find feasible out-edges within the trimmed graph.
     376              :    At each stage, choose the node for which if the remaining path were feasible,
     377              :    it would be the shortest path (summing the length of the known-feasible path
     378              :    so far with that of the remaining possibly-feasible path).
     379              :    This way, the first feasible path we find to TARGET_ENODE is the shortest.
     380              :    We start by trying the shortest possible path, but if that fails,
     381              :    we explore progressively longer paths, eventually trying iterations through
     382              :    loops.  The exploration is captured in the feasible_graph, which can be
     383              :    dumped as a .dot file to visualize the exploration.  The indices of the
     384              :    feasible_nodes show the order in which they were created.
     385              : 
     386              :    This is something of a brute-force approach, but the trimmed_graph
     387              :    hopefully keeps the complexity manageable.
     388              : 
     389              :    Terminate with failure when the number of infeasible edges exceeds
     390              :    a threshold (--param=analyzer-max-infeasible-edges=).
     391              :    This is guaranteed to eventually lead to terminatation, as
     392              :    we can't keep creating feasible nodes without eventually
     393              :    either reaching an infeasible edge, or reaching the
     394              :    TARGET_ENODE.  Specifically, there can't be a cycle of
     395              :    feasible edges that doesn't reach the target_enode without
     396              :    an out-edge that either fails feasibility or gets closer
     397              :    to the TARGET_ENODE: on each iteration we are either:
     398              :    - effectively getting closer to the TARGET_ENODE (which can't
     399              :      continue forever without reaching the target), or
     400              :    - getting monotonically closer to the termination threshold.  */
     401              : 
     402              : std::unique_ptr<exploded_path>
     403         6667 : epath_finder::explore_feasible_paths (const exploded_node *target_enode,
     404              :                                       const pending_diagnostic &pd,
     405              :                                       const char *desc, unsigned diag_idx)
     406              : {
     407         6667 :   logger *logger = get_logger ();
     408         6667 :   LOG_SCOPE (logger);
     409              : 
     410         6667 :   region_model_manager *mgr = m_eg.get_engine ()->get_model_manager ();
     411              : 
     412              :   /* Determine the shortest path to TARGET_ENODE from each node in
     413              :      the exploded graph.  */
     414         6667 :   shortest_paths<eg_traits, exploded_path> sep
     415         6667 :     (m_eg, target_enode, SPS_TO_GIVEN_TARGET);
     416              : 
     417              :   /* Construct a trimmed_graph: the subset of nodes/edges that
     418              :      are on a path that eventually reaches TARGET_ENODE.
     419              :      We only need to consider these when considering the shortest
     420              :      feasible path.  */
     421         6667 :   trimmed_graph tg (m_eg, target_enode);
     422              : 
     423         6667 :   if (flag_dump_analyzer_feasibility)
     424            4 :     dump_trimmed_graph (target_enode, desc, diag_idx, tg, sep);
     425              : 
     426         6667 :   feasible_graph fg;
     427         6667 :   feasible_worklist worklist (sep);
     428              : 
     429              :   /* Populate the worklist with the origin node.  */
     430         6667 :   {
     431         6667 :     feasibility_state init_state (mgr, m_eg.get_supergraph ());
     432         6667 :     feasible_node *origin = fg.add_node (m_eg.get_origin (), init_state, 0);
     433         6667 :     worklist.add_node (origin);
     434         6667 :   }
     435              : 
     436              :   /* Iteratively explore the tree of feasible paths in order of shortest
     437              :      path until we either find a feasible path to TARGET_ENODE, or hit
     438              :      a limit.  */
     439              : 
     440              :   /* Set this if we find a feasible path to TARGET_ENODE.  */
     441         6667 :   std::unique_ptr<exploded_path> best_path = nullptr;
     442              : 
     443         6667 :   {
     444         6667 :     auto_checking_feasibility sentinel (mgr);
     445              : 
     446       109585 :     while (process_worklist_item (&worklist, tg, &fg, target_enode,
     447              :                                   pd, diag_idx, &best_path))
     448              :       {
     449              :         /* Empty; the work is done within process_worklist_item.  */
     450              :       }
     451         6667 :   }
     452              : 
     453         6667 :   if (logger)
     454              :     {
     455            2 :       logger->log ("tg for sd: %i:", diag_idx);
     456            2 :       logger->inc_indent ();
     457            2 :       tg.log_stats (logger);
     458            2 :       logger->dec_indent ();
     459              : 
     460            2 :       logger->log ("fg for sd: %i:", diag_idx);
     461            2 :       logger->inc_indent ();
     462            2 :       fg.log_stats (logger);
     463            2 :       logger->dec_indent ();
     464              :     }
     465              : 
     466              :   /* Dump the feasible_graph.  */
     467         6667 :   if (flag_dump_analyzer_feasibility)
     468            4 :     dump_feasible_graph (target_enode, desc, diag_idx, fg);
     469              : 
     470         6667 :   return best_path;
     471        13334 : }
     472              : 
     473              : /* Process the next item in WORKLIST, potentially adding new items
     474              :    based on feasible out-edges, and extending FG accordingly.
     475              :    Use TG to ignore out-edges that don't lead to TARGET_ENODE.
     476              :    Return true if the worklist processing should continue.
     477              :    Return false if the processing of the worklist should stop
     478              :    (either due to reaching TARGET_ENODE, or hitting a limit).
     479              :    Write to *OUT_BEST_PATH if stopping due to finding a feasible path
     480              :    to TARGET_ENODE.
     481              :    Use PD to provide additional restrictions on feasibility of
     482              :    the final path in the feasible_graph before converting to
     483              :    an exploded_path.  */
     484              : 
     485              : bool
     486       109585 : epath_finder::
     487              : process_worklist_item (feasible_worklist *worklist,
     488              :                        const trimmed_graph &tg,
     489              :                        feasible_graph *fg,
     490              :                        const exploded_node *target_enode,
     491              :                        const pending_diagnostic &pd,
     492              :                        unsigned diag_idx,
     493              :                        std::unique_ptr<exploded_path> *out_best_path) const
     494              : {
     495       109585 :   logger *logger = get_logger ();
     496              : 
     497       109585 :   feasible_node *fnode = worklist->take_next ();
     498       109585 :   if (!fnode)
     499              :     {
     500           38 :       if (logger)
     501            0 :         logger->log ("drained worklist for sd: %i"
     502              :                      " without finding feasible path",
     503              :                      diag_idx);
     504              :       return false;
     505              :     }
     506              : 
     507       109547 :   log_scope s (logger, "fg worklist item",
     508              :                "considering FN: %i (EN: %i) for sd: %i",
     509       109547 :                fnode->get_index (), fnode->get_inner_node ()->m_index,
     510       109547 :                diag_idx);
     511              : 
     512              :   /* Iterate through all out-edges from this item.  */
     513       109547 :   unsigned i;
     514       109547 :   exploded_edge *succ_eedge;
     515       380485 :   FOR_EACH_VEC_ELT (fnode->get_inner_node ()->m_succs, i, succ_eedge)
     516              :     {
     517       168020 :       log_scope s (logger, "edge", "considering edge: EN:%i -> EN:%i",
     518       168020 :                    succ_eedge->m_src->m_index,
     519       168020 :                    succ_eedge->m_dest->m_index);
     520              :       /* Reject edges that aren't in the trimmed graph.  */
     521       168020 :       if (!tg.contains_p (succ_eedge))
     522              :         {
     523        54899 :           if (logger)
     524            1 :             logger->log ("rejecting: not in trimmed graph");
     525        54899 :           continue;
     526              :         }
     527              : 
     528       113121 :       feasibility_state succ_state (fnode->get_state ());
     529       113121 :       std::unique_ptr<rejected_constraint> rc;
     530       113121 :       if (succ_state.maybe_update_for_edge (logger, succ_eedge, nullptr, &rc))
     531              :         {
     532       111501 :           gcc_assert (rc == nullptr);
     533       111501 :           feasible_node *succ_fnode
     534       111501 :             = fg->add_node (succ_eedge->m_dest,
     535              :                             succ_state,
     536       111501 :                             fnode->get_path_length () + 1);
     537       111501 :           if (logger)
     538           14 :             logger->log ("accepting as FN: %i", succ_fnode->get_index ());
     539       111501 :           fg->add_edge (new feasible_edge (fnode, succ_fnode, succ_eedge));
     540              : 
     541              :           /* Have we reached TARGET_ENODE?  */
     542       111501 :           if (succ_fnode->get_inner_node () == target_enode)
     543              :             {
     544         6508 :               if (logger)
     545            2 :                 logger->log ("success: got feasible path to EN: %i (sd: %i)"
     546              :                              " (length: %i)",
     547            2 :                              target_enode->m_index, diag_idx,
     548              :                              succ_fnode->get_path_length ());
     549         6508 :               if (!pd.check_valid_fpath_p (*succ_fnode))
     550              :                 {
     551           61 :                   if (logger)
     552            0 :                     logger->log ("rejecting feasible path due to"
     553              :                                  " pending_diagnostic");
     554              :                   return false;
     555              :                 }
     556         6447 :               *out_best_path = fg->make_epath (succ_fnode);
     557         6447 :               if (flag_dump_analyzer_feasibility)
     558            4 :                 dump_feasible_path (target_enode, diag_idx, *fg, *succ_fnode);
     559              : 
     560              :               /* Success: stop the worklist iteration.  */
     561              :               return false;
     562              :             }
     563              :           else
     564       104993 :             worklist->add_node (succ_fnode);
     565              :         }
     566              :       else
     567              :         {
     568         1620 :           if (logger)
     569            0 :             logger->log ("infeasible");
     570         1620 :           gcc_assert (rc);
     571         1620 :           fg->add_feasibility_problem (fnode,
     572              :                                        succ_eedge,
     573              :                                        std::move (rc));
     574              : 
     575              :           /* Give up if there have been too many infeasible edges.  */
     576         1620 :           if (fg->get_num_infeasible ()
     577         1620 :               > (unsigned)param_analyzer_max_infeasible_edges)
     578              :             {
     579          121 :               if (logger)
     580            0 :                 logger->log ("too many infeasible edges (%i); giving up",
     581              :                              fg->get_num_infeasible ());
     582              :               return false;
     583              :             }
     584              :         }
     585       168020 :     }
     586              : 
     587              :   /* Continue the worklist iteration.  */
     588              :   return true;
     589       109547 : }
     590              : 
     591              : /* Helper class for epath_finder::dump_trimmed_graph
     592              :    to dump extra per-node information.
     593              :    Use SEP to add the length of the shortest path from each
     594              :    node to the target node to each node's dump.  */
     595              : 
     596              : class dump_eg_with_shortest_path : public eg_traits::dump_args_t
     597              : {
     598              : public:
     599            4 :   dump_eg_with_shortest_path
     600              :     (const exploded_graph &eg,
     601              :      const shortest_paths<eg_traits, exploded_path> &sep)
     602              :   : dump_args_t (eg),
     603            4 :     m_sep (sep)
     604              :   {
     605              :   }
     606              : 
     607           74 :   void dump_extra_info (const exploded_node *enode,
     608              :                         pretty_printer *pp) const final override
     609              :   {
     610           74 :     pp_printf (pp, "sp: %i", m_sep.get_shortest_path (enode).length ());
     611           74 :     pp_newline (pp);
     612           74 :   }
     613              : 
     614              : private:
     615              :   const shortest_paths<eg_traits, exploded_path> &m_sep;
     616              : };
     617              : 
     618              : /* Dump TG to "BASE_NAME.DESC.DIAG_IDX.to-enN.tg.dot",
     619              :    annotating each node with the length of the shortest path
     620              :    from that node to TARGET_ENODE (using SEP).  */
     621              : 
     622              : void
     623            4 : epath_finder::
     624              : dump_trimmed_graph (const exploded_node *target_enode,
     625              :                     const char *desc, unsigned diag_idx,
     626              :                     const trimmed_graph &tg,
     627              :                     const shortest_paths<eg_traits, exploded_path> &sep)
     628              : {
     629            4 :   auto_timevar tv (TV_ANALYZER_DUMP);
     630            4 :   dump_eg_with_shortest_path inner_args (m_eg, sep);
     631            4 :   trimmed_graph::dump_args_t args (inner_args);
     632            4 :   pretty_printer pp;
     633            4 :   pp_printf (&pp, "%s.%s.%i.to-en%i.tg.dot",
     634            4 :              dump_base_name, desc, diag_idx, target_enode->m_index);
     635            4 :   char *filename = xstrdup (pp_formatted_text (&pp));
     636            4 :   tg.dump_dot (filename, nullptr, args);
     637            4 :   free (filename);
     638            4 : }
     639              : 
     640              : /* Dump FG to "BASE_NAME.DESC.DIAG_IDX.to-enN.fg.dot".  */
     641              : 
     642              : void
     643            4 : epath_finder::dump_feasible_graph (const exploded_node *target_enode,
     644              :                                    const char *desc, unsigned diag_idx,
     645              :                                    const feasible_graph &fg)
     646              : {
     647            4 :   auto_timevar tv (TV_ANALYZER_DUMP);
     648            4 :   exploded_graph::dump_args_t inner_args (m_eg);
     649            4 :   feasible_graph::dump_args_t args (inner_args);
     650            4 :   pretty_printer pp;
     651            4 :   pp_printf (&pp, "%s.%s.%i.to-en%i.fg.dot",
     652            4 :              dump_base_name, desc, diag_idx, target_enode->m_index);
     653            4 :   char *filename = xstrdup (pp_formatted_text (&pp));
     654            4 :   fg.dump_dot (filename, nullptr, args);
     655            4 :   free (filename);
     656            4 : }
     657              : 
     658              : /* Dump the path to FNODE to "BASE_NAME.DIAG_IDX.to-enN.fpath.txt".  */
     659              : 
     660              : void
     661            4 : epath_finder::dump_feasible_path (const exploded_node *target_enode,
     662              :                                   unsigned diag_idx,
     663              :                                   const feasible_graph &fg,
     664              :                                   const feasible_node &fnode) const
     665              : {
     666            4 :   auto_timevar tv (TV_ANALYZER_DUMP);
     667            4 :   pretty_printer pp;
     668            4 :   pp_printf (&pp, "%s.%i.to-en%i.fpath.txt",
     669            4 :              dump_base_name, diag_idx, target_enode->m_index);
     670            4 :   char *filename = xstrdup (pp_formatted_text (&pp));
     671            4 :   fg.dump_feasible_path (fnode, filename);
     672            4 :   free (filename);
     673            4 : }
     674              : 
     675              : /* class saved_diagnostic.  */
     676              : 
     677              : /* saved_diagnostic's ctor.  */
     678              : 
     679         6671 : saved_diagnostic::saved_diagnostic (const state_machine *sm,
     680              :                                     pending_location &&ploc,
     681              :                                     tree var,
     682              :                                     const svalue *sval,
     683              :                                     state_machine::state_t state,
     684              :                                     std::unique_ptr<pending_diagnostic> d,
     685              :                                     unsigned idx)
     686         6671 : : m_sm (sm),
     687         6671 :   m_ploc (std::move (ploc)),
     688         6671 :   m_var (var), m_sval (sval), m_state (state),
     689         6671 :   m_d (std::move (d)), m_trailing_eedge (nullptr),
     690         6671 :   m_idx (idx),
     691         6671 :   m_best_epath (nullptr), m_problem (nullptr),
     692         6671 :   m_notes ()
     693              : {
     694              :   /* We must have an enode in order to be able to look for paths
     695              :      through the exploded_graph to this diagnostic.  */
     696         6671 :   gcc_assert (m_ploc.m_enode);
     697         6671 : }
     698              : 
     699              : const supernode *
     700       159218 : saved_diagnostic::get_supernode () const
     701              : {
     702       159218 :   return m_ploc.m_enode->get_supernode ();
     703              : }
     704              : 
     705              : bool
     706        53108 : saved_diagnostic::operator== (const saved_diagnostic &other) const
     707              : {
     708        55548 :   if (m_notes.length () != other.m_notes.length ())
     709              :     return false;
     710        52698 :   for (unsigned i = 0; i < m_notes.length (); i++)
     711          892 :     if (!m_notes[i]->equal_p (*other.m_notes[i]))
     712              :       return false;
     713              : 
     714              :   // Don't deduplicate dump_path_diagnostic instances
     715        51806 :   if (!strcmp (m_d->get_kind (), "dump_path_diagnostic"))
     716         1560 :     return this == &other;
     717              : 
     718        50246 :   return (m_sm == other.m_sm
     719              :           /* We don't compare m_enode.  */
     720        43666 :           && get_supernode () == other.get_supernode ()
     721         9188 :           && (m_ploc.m_event_loc_info.m_loc
     722         9188 :               == other.m_ploc.m_event_loc_info.m_loc)
     723         7161 :           && pending_diagnostic::same_tree_p (m_var, other.m_var)
     724         6507 :           && m_state == other.m_state
     725         6463 :           && m_d->equal_p (*other.m_d)
     726        56437 :           && m_trailing_eedge == other.m_trailing_eedge);
     727              : }
     728              : 
     729              : /* Add PN to this diagnostic, taking ownership of it.  */
     730              : 
     731              : void
     732          214 : saved_diagnostic::add_note (std::unique_ptr<pending_note> pn)
     733              : {
     734          214 :   gcc_assert (pn);
     735          214 :   m_notes.safe_push (pn.release ());
     736          214 : }
     737              : 
     738              : /* Add EVENT to this diagnostic.  */
     739              : 
     740              : void
     741          179 : saved_diagnostic::add_event (std::unique_ptr<checker_event> event)
     742              : {
     743          179 :   gcc_assert (event);
     744          179 :   m_saved_events.safe_push (event.release ());
     745          179 : }
     746              : 
     747              : /* Return a new json::object of the form
     748              :    {"sm": optional str,
     749              :     "ploc": {},
     750              :     "sval": optional str,
     751              :     "state": optional str,
     752              :     "path_length": optional int,
     753              :     "pending_diagnostic": str,
     754              :     "idx": int}.  */
     755              : 
     756              : std::unique_ptr<json::object>
     757            1 : saved_diagnostic::to_json () const
     758              : {
     759            1 :   auto sd_obj = std::make_unique<json::object> ();
     760              : 
     761            1 :   if (m_sm)
     762            1 :     sd_obj->set_string ("sm", m_sm->get_name ());
     763            1 :   sd_obj->set ("ploc", m_ploc.to_json ());
     764            1 :   if (m_sval)
     765            1 :     sd_obj->set ("sval", m_sval->to_json ());
     766            1 :   if (m_state)
     767            1 :     sd_obj->set ("state", m_state->to_json ());
     768            1 :   if (m_best_epath)
     769            1 :     sd_obj->set_integer ("path_length", get_epath_length ());
     770            1 :   sd_obj->set<json::object> ("pending_diagnostic", m_d->to_json ());
     771            1 :   sd_obj->set_integer ("idx", m_idx);
     772            1 :   if (m_problem)
     773            0 :     sd_obj->set<json::object> ("feasibility_problem", m_problem->to_json ());
     774            1 :   if (!m_duplicates.is_empty ())
     775              :     {
     776            0 :       auto arr = std::make_unique<json::array> ();
     777              : 
     778            0 :       for (auto &dup : m_duplicates)
     779            0 :         arr->append (std::make_unique <json::integer_number> (dup->m_idx));
     780              : 
     781            0 :       sd_obj->set<json::array> ("duplicates", std::move (arr));
     782            0 :     }
     783              : 
     784            1 :   return sd_obj;
     785              : }
     786              : 
     787              : /* Dump this to PP in a form suitable for use as an id in .dot output.  */
     788              : 
     789              : void
     790           16 : saved_diagnostic::dump_dot_id (pretty_printer *pp) const
     791              : {
     792           16 :   pp_printf (pp, "sd_%i", m_idx);
     793           16 : }
     794              : 
     795              : /* Dump this to PP in a form suitable for use as a node in .dot output.  */
     796              : 
     797              : void
     798            8 : saved_diagnostic::dump_as_dot_node (pretty_printer *pp) const
     799              : {
     800            8 :   dump_dot_id (pp);
     801            8 :   pp_printf (pp,
     802              :              " [shape=none,margin=0,style=filled,fillcolor=\"red\",label=\"");
     803            8 :   pp_write_text_to_stream (pp);
     804              : 
     805              :   /* Node label.  */
     806            8 :   pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)\n",
     807            8 :              m_d->get_kind (), m_idx);
     808            8 :   if (m_sm)
     809              :     {
     810            8 :       pp_printf (pp, "sm: %s", m_sm->get_name ());
     811            8 :       if (m_state)
     812              :         {
     813            8 :           pp_printf (pp, "; state: ");
     814            8 :           m_state->dump_to_pp (pp);
     815              :         }
     816            8 :       pp_newline (pp);
     817              :     }
     818            8 :   if (m_var)
     819            8 :     pp_printf (pp, "var: %qE\n", m_var);
     820            8 :   if (m_sval)
     821              :     {
     822            8 :       pp_string (pp, "sval: ");
     823            8 :       m_sval->symbolic::node::dump_to_pp (pp);
     824            8 :       pp_newline (pp);
     825              :     }
     826            8 :   if (m_best_epath)
     827            0 :     pp_printf (pp, "path length: %i\n", get_epath_length ());
     828              : 
     829            8 :   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
     830            8 :   pp_string (pp, "\"];\n\n");
     831              : 
     832              :   /* Show links to duplicates.  */
     833            8 :   for (auto iter : m_duplicates)
     834              :     {
     835            0 :       dump_dot_id (pp);
     836            0 :       pp_string (pp, " -> ");
     837            0 :       iter->dump_dot_id (pp);
     838            0 :       pp_string (pp, " [style=\"dotted\" arrowhead=\"none\"];");
     839            0 :       pp_newline (pp);
     840              :     }
     841            8 : }
     842              : 
     843              : /* Use PF to find the best exploded_path for this saved_diagnostic, if any,
     844              :    and store it in m_best_epath.
     845              :    Return true if a best path was found.  */
     846              : 
     847              : bool
     848         6671 : saved_diagnostic::calc_best_epath (epath_finder *pf)
     849              : {
     850         6671 :   logger *logger = pf->get_logger ();
     851         6671 :   LOG_SCOPE (logger);
     852         6671 :   m_problem = nullptr;
     853              : 
     854         6671 :   m_best_epath = pf->get_best_epath (m_ploc.m_enode,
     855         6671 :                                      *m_d, m_d->get_kind (), m_idx,
     856         6671 :                                      &m_problem);
     857              : 
     858              :   /* Handle failure to find a feasible path.  */
     859         6671 :   if (m_best_epath == nullptr)
     860          220 :     return false;
     861              : 
     862              :   gcc_assert (m_best_epath);
     863              : 
     864              :   return true;
     865         6671 : }
     866              : 
     867              : unsigned
     868         6607 : saved_diagnostic::get_epath_length () const
     869              : {
     870         6607 :   gcc_assert (m_best_epath);
     871         6607 :   return m_best_epath->length ();
     872              : }
     873              : 
     874              : /* Record that OTHER (and its duplicates) are duplicates
     875              :    of this saved_diagnostic.  */
     876              : 
     877              : void
     878         1999 : saved_diagnostic::add_duplicate (saved_diagnostic *other)
     879              : {
     880         1999 :   gcc_assert (other);
     881         1999 :   m_duplicates.reserve (m_duplicates.length ()
     882         2096 :                         + other->m_duplicates.length ()
     883              :                         + 1);
     884         1999 :   m_duplicates.splice (other->m_duplicates);
     885         1999 :   other->m_duplicates.truncate (0);
     886         1999 :   m_duplicates.safe_push (other);
     887         1999 : }
     888              : 
     889              : /* Walk up the sedges of each of the two paths.
     890              :    If the two sequences of sedges do not perfectly correspond,
     891              :    then paths are incompatible.
     892              :    If there is at least one sedge that either cannot be paired up
     893              :    or its counterpart is not equal, then the paths are incompatible
     894              :    and this function returns FALSE.
     895              :    Otherwise return TRUE.
     896              : 
     897              :    Incompatible paths:
     898              : 
     899              :        <cond Y>
     900              :        /      \
     901              :       /        \
     902              :     true      false
     903              :      |          |
     904              :     ...        ...
     905              :      |          |
     906              :     ...       stmt x
     907              :      |
     908              :    stmt x
     909              : 
     910              :    Both LHS_PATH and RHS_PATH final enodes should be
     911              :    over the same gimple statement.  */
     912              : 
     913              : static bool
     914           98 : compatible_epath_p (const exploded_path *lhs_path,
     915              :                     const exploded_path *rhs_path)
     916              : {
     917           98 :   gcc_assert (lhs_path);
     918           98 :   gcc_assert (rhs_path);
     919           98 :   gcc_assert (rhs_path->length () > 0);
     920           98 :   gcc_assert (rhs_path->length () > 0);
     921           98 :   int lhs_eedge_idx = lhs_path->length () - 1;
     922           98 :   int rhs_eedge_idx = rhs_path->length () - 1;
     923           98 :   const exploded_edge *lhs_eedge;
     924           98 :   const exploded_edge *rhs_eedge;
     925              : 
     926         2209 :   while (lhs_eedge_idx >= 0 && rhs_eedge_idx >= 0)
     927              :     {
     928         2406 :       while (lhs_eedge_idx >= 0)
     929              :         {
     930              :           /* Find LHS_PATH's next superedge.  */
     931         2340 :           lhs_eedge = lhs_path->m_elements[lhs_eedge_idx].m_eedge;
     932         2340 :           if (lhs_eedge->m_sedge)
     933              :             break;
     934              :           else
     935          197 :             lhs_eedge_idx--;
     936              :         }
     937         2406 :       while (rhs_eedge_idx >= 0)
     938              :         {
     939              :           /* Find RHS_PATH's next superedge.  */
     940         2340 :           rhs_eedge = rhs_path->m_elements[rhs_eedge_idx].m_eedge;
     941         2340 :           if (rhs_eedge->m_sedge)
     942              :             break;
     943              :           else
     944          197 :             rhs_eedge_idx--;
     945              :         }
     946              : 
     947         2209 :       if (lhs_eedge->m_sedge && rhs_eedge->m_sedge)
     948              :         {
     949         2143 :           if (lhs_eedge->m_sedge != rhs_eedge->m_sedge)
     950              :             /* Both superedges do not match.
     951              :                Superedges are not dependent on the exploded path, so even
     952              :                different epaths will have similar sedges if they follow
     953              :                the same outcome of a conditional node.  */
     954              :             return false;
     955              : 
     956         2111 :           lhs_eedge_idx--;
     957         2111 :           rhs_eedge_idx--;
     958         2111 :           continue;
     959              :         }
     960           66 :       else if (lhs_eedge->m_sedge == nullptr && rhs_eedge->m_sedge == nullptr)
     961              :         /* Both paths were drained up entirely.
     962              :            No discriminant was found.  */
     963           66 :         return true;
     964              : 
     965              :       /* A superedge was found for only one of the two paths.  */
     966              :       return false;
     967              :     }
     968              : 
     969              :   /* A superedge was found for only one of the two paths.  */
     970            0 :   if (lhs_eedge_idx >= 0 || rhs_eedge_idx >= 0)
     971            0 :     return false;
     972              : 
     973              :   /* Both paths were drained up entirely.
     974              :      No discriminant was found.  */
     975              :   return true;
     976              : }
     977              : 
     978              : 
     979              : /* Return true if this diagnostic supercedes OTHER, and that OTHER should
     980              :    therefore not be emitted.  */
     981              : 
     982              : bool
     983        31555 : saved_diagnostic::supercedes_p (const saved_diagnostic &other) const
     984              : {
     985        31555 :   if (get_supernode () != other.get_supernode ())
     986              :     return false;
     987              : 
     988              :   /* return early if OTHER won't be superseded anyway.  */
     989         6298 :   if (!m_d->supercedes_p (*other.m_d))
     990              :     return false;
     991              : 
     992              :   /* If the two saved_diagnostics' path are not compatible
     993              :      then they cannot supersede one another.  */
     994           98 :   return compatible_epath_p (m_best_epath.get (), other.m_best_epath.get ());
     995              : }
     996              : 
     997              : /* Move any saved checker_events from this saved_diagnostic to
     998              :    the end of DST_PATH.  */
     999              : 
    1000              : void
    1001         4386 : saved_diagnostic::add_any_saved_events (checker_path &dst_path)
    1002              : {
    1003         4887 :   for (auto &event : m_saved_events)
    1004              :     {
    1005          167 :       dst_path.add_event (std::unique_ptr<checker_event> (event));
    1006          167 :       event = nullptr;
    1007              :     }
    1008         4386 : }
    1009              : 
    1010              : /* Emit any pending notes owned by this diagnostic.  */
    1011              : 
    1012              : void
    1013         4327 : saved_diagnostic::emit_any_notes () const
    1014              : {
    1015         4905 :   for (auto pn : m_notes)
    1016          198 :     pn->emit ();
    1017         4327 : }
    1018              : 
    1019              : /* For SARIF output, add additional properties to the "result" object
    1020              :    for this diagnostic.
    1021              :    This extra data is intended for use when debugging the analyzer.  */
    1022              : 
    1023              : void
    1024           37 : saved_diagnostic::
    1025              : maybe_add_sarif_properties (diagnostics::sarif_object &result_obj) const
    1026              : {
    1027           37 :   auto &props = result_obj.get_or_create_properties ();
    1028              : #define PROPERTY_PREFIX "gcc/analyzer/saved_diagnostic/"
    1029           37 :   if (m_sm)
    1030           17 :     props.set_string (PROPERTY_PREFIX "sm", m_sm->get_name ());
    1031           37 :   props.set (PROPERTY_PREFIX "ploc", m_ploc.to_json ());
    1032           37 :   if (m_var)
    1033           17 :     props.set (PROPERTY_PREFIX "var", tree_to_json (m_var));
    1034           37 :   if (m_sval)
    1035           17 :     props.set (PROPERTY_PREFIX "sval", m_sval->to_json ());
    1036           37 :   if (m_state)
    1037           17 :     props.set (PROPERTY_PREFIX "state", m_state->to_json ());
    1038              :   // TODO: m_best_epath
    1039           37 :   props.set_integer (PROPERTY_PREFIX "idx", m_idx);
    1040           37 :   if (m_duplicates.length () > 0)
    1041              :     {
    1042            4 :       auto duplicates_arr = std::make_unique<json::array> ();
    1043           16 :       for (auto iter : m_duplicates)
    1044              :         {
    1045            4 :           auto sd_obj = std::make_unique<diagnostics::sarif_object> ();
    1046            4 :           iter->maybe_add_sarif_properties (*sd_obj);
    1047            4 :           duplicates_arr->append (std::move (sd_obj));
    1048            4 :         }
    1049            4 :       props.set<json::array> (PROPERTY_PREFIX "duplicates",
    1050              :                               std::move (duplicates_arr));
    1051            4 :     }
    1052              : #undef PROPERTY_PREFIX
    1053              : 
    1054              : #define PROPERTY_PREFIX "gcc/analyzer/pending_diagnostic/"
    1055           37 :   props.set_string (PROPERTY_PREFIX "kind", m_d->get_kind ());
    1056              : #undef PROPERTY_PREFIX
    1057              : 
    1058              :   /* Potentially add pending_diagnostic-specific properties.  */
    1059           37 :   m_d->maybe_add_sarif_properties (result_obj);
    1060           37 : }
    1061              : 
    1062              : /* State for building a checker_path from a particular exploded_path.
    1063              :    In particular, this precomputes reachability information: the set of
    1064              :    source enodes for which a path be found to the diagnostic enode.  */
    1065              : 
    1066         4386 : class path_builder
    1067              : {
    1068              : public:
    1069         4386 :   path_builder (const exploded_graph &eg,
    1070              :                 const exploded_path &epath,
    1071              :                 const feasibility_problem *problem,
    1072              :                 const saved_diagnostic &sd)
    1073         4386 :   : m_eg (eg),
    1074         4386 :     m_diag_enode (epath.get_final_enode ()),
    1075         4386 :     m_sd (sd),
    1076         4386 :     m_reachability (eg, m_diag_enode),
    1077         4386 :     m_feasibility_problem (problem)
    1078         4386 :   {}
    1079              : 
    1080            0 :   const exploded_node *get_diag_node () const { return m_diag_enode; }
    1081              : 
    1082        59852 :   pending_diagnostic *get_pending_diagnostic () const
    1083              :   {
    1084          255 :     return m_sd.m_d.get ();
    1085              :   }
    1086              : 
    1087        33992 :   bool reachable_from_p (const exploded_node *src_enode) const
    1088              :   {
    1089        67984 :     return m_reachability.reachable_from_p (src_enode);
    1090              :   }
    1091              : 
    1092        88054 :   const extrinsic_state &get_ext_state () const { return m_eg.get_ext_state (); }
    1093              : 
    1094        42347 :   const feasibility_problem *get_feasibility_problem () const
    1095              :   {
    1096        42347 :     return m_feasibility_problem;
    1097              :   }
    1098              : 
    1099         5104 :   const state_machine *get_sm () const { return m_sd.m_sm; }
    1100              : 
    1101              :   const supergraph &
    1102        44025 :   get_supergraph () const { return m_eg.get_supergraph (); }
    1103              : 
    1104              : private:
    1105              :   typedef reachability<eg_traits> enode_reachability;
    1106              : 
    1107              :   const exploded_graph &m_eg;
    1108              : 
    1109              :   /* The enode where the diagnostic occurs.  */
    1110              :   const exploded_node *m_diag_enode;
    1111              : 
    1112              :   const saved_diagnostic &m_sd;
    1113              : 
    1114              :   /* Precompute all enodes from which the diagnostic is reachable.  */
    1115              :   enode_reachability m_reachability;
    1116              : 
    1117              :   const feasibility_problem *m_feasibility_problem;
    1118              : };
    1119              : 
    1120              : /* class diagnostic_manager.  */
    1121              : 
    1122              : /* diagnostic_manager's ctor.  */
    1123              : 
    1124         3573 : diagnostic_manager::diagnostic_manager (logger *logger, engine *eng,
    1125              :                                         int verbosity)
    1126         3573 : : log_user (logger), m_eng (eng), m_verbosity (verbosity),
    1127         3573 :   m_num_disabled_diagnostics (0)
    1128              : {
    1129         3573 : }
    1130              : 
    1131              : /* Queue pending_diagnostic D at ENODE for later emission.
    1132              :    Return true/false signifying if the diagnostic was actually added.  */
    1133              : 
    1134              : bool
    1135        10822 : diagnostic_manager::add_diagnostic (const state_machine *sm,
    1136              :                                     pending_location &&ploc,
    1137              :                                     tree var,
    1138              :                                     const svalue *sval,
    1139              :                                     state_machine::state_t state,
    1140              :                                     std::unique_ptr<pending_diagnostic> d)
    1141              : {
    1142        10822 :   LOG_FUNC (get_logger ());
    1143              : 
    1144              :   /* We must have an enode in order to be able to look for paths
    1145              :      through the exploded_graph to the diagnostic.  */
    1146        10822 :   gcc_assert (ploc.m_enode);
    1147              : 
    1148              :   /* If this warning is ultimately going to be rejected by a -Wno-analyzer-*
    1149              :      flag, reject it now.  */
    1150        10822 :   {
    1151        10822 :     location_t loc = ploc.m_event_loc_info.m_loc;
    1152        10822 :     loc = d->fixup_location (loc, true);
    1153        10822 :     int option = d->get_controlling_option ();
    1154        10822 :     if (!warning_enabled_at (loc, option))
    1155              :       {
    1156         4151 :         if (get_logger ())
    1157            0 :           get_logger ()->log ("rejecting disabled warning %qs",
    1158            0 :                               d->get_kind ());
    1159         4151 :         m_num_disabled_diagnostics++;
    1160         4151 :         return false;
    1161              :       }
    1162              :   }
    1163              : 
    1164         6671 :   saved_diagnostic *sd
    1165              :     = new saved_diagnostic (sm,
    1166              :                             std::move (ploc),
    1167              :                             var,
    1168              :                             sval,
    1169              :                             state,
    1170              :                             std::move (d),
    1171        11692 :                             m_saved_diagnostics.length ());
    1172         6671 :   m_saved_diagnostics.safe_push (sd);
    1173         6671 :   sd->m_ploc.m_enode->add_diagnostic (sd);
    1174         6671 :   if (get_logger ())
    1175            4 :     log ("adding saved diagnostic %i at SN %i to EN %i: %qs",
    1176              :          sd->get_index (),
    1177            2 :          sd->get_supernode ()->m_id,
    1178            2 :          sd->m_ploc.m_enode->m_index,
    1179            2 :          sd->m_d->get_kind ());
    1180              :   return true;
    1181        10822 : }
    1182              : 
    1183              : /* Queue pending_diagnostic D at ENODE for later emission.
    1184              :    Return true/false signifying if the diagnostic was actually added.
    1185              :    Take ownership of D (or delete it).  */
    1186              : 
    1187              : bool
    1188         3945 : diagnostic_manager::add_diagnostic (pending_location &&ploc,
    1189              :                                     std::unique_ptr<pending_diagnostic> d)
    1190              : {
    1191         3945 :   gcc_assert (ploc.m_enode);
    1192         3945 :   return add_diagnostic (nullptr, std::move (ploc),
    1193         3945 :                          NULL_TREE, nullptr, 0, std::move (d));
    1194              : }
    1195              : 
    1196              : /* Add PN to the most recent saved_diagnostic.  */
    1197              : 
    1198              : void
    1199          214 : diagnostic_manager::add_note (std::unique_ptr<pending_note> pn)
    1200              : {
    1201          214 :   LOG_FUNC (get_logger ());
    1202          214 :   gcc_assert (pn);
    1203              : 
    1204              :   /* Get most recent saved_diagnostic.  */
    1205          214 :   gcc_assert (m_saved_diagnostics.length () > 0);
    1206          214 :   saved_diagnostic *sd = m_saved_diagnostics[m_saved_diagnostics.length () - 1];
    1207          214 :   sd->add_note (std::move (pn));
    1208          214 : }
    1209              : 
    1210              : /* Add EVENT to the most recent saved_diagnostic.  */
    1211              : 
    1212              : void
    1213          179 : diagnostic_manager::add_event (std::unique_ptr<checker_event> event)
    1214              : {
    1215          179 :   LOG_FUNC (get_logger ());
    1216          179 :   gcc_assert (event);
    1217              : 
    1218              :   /* Get most recent saved_diagnostic.  */
    1219          179 :   gcc_assert (m_saved_diagnostics.length () > 0);
    1220          179 :   saved_diagnostic *sd = m_saved_diagnostics[m_saved_diagnostics.length () - 1];
    1221          179 :   sd->add_event (std::move (event));
    1222          179 : }
    1223              : 
    1224              : /* Return a new json::object of the form
    1225              :    {"diagnostics"  : [obj for saved_diagnostic]}.  */
    1226              : 
    1227              : std::unique_ptr<json::object>
    1228            1 : diagnostic_manager::to_json () const
    1229              : {
    1230            1 :   auto dm_obj = std::make_unique<json::object> ();
    1231              : 
    1232            1 :   {
    1233            1 :     auto sd_arr = std::make_unique<json::array> ();
    1234            1 :     int i;
    1235            1 :     saved_diagnostic *sd;
    1236            3 :     FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
    1237            1 :       sd_arr->append (sd->to_json ());
    1238            1 :     dm_obj->set ("diagnostics", std::move (sd_arr));
    1239            1 :   }
    1240              : 
    1241            1 :   return dm_obj;
    1242              : }
    1243              : 
    1244              : /* A class for identifying sets of duplicated pending_diagnostic.
    1245              : 
    1246              :    We want to find the simplest saved_diagnostic amongst those that share a
    1247              :    dedupe_key.  */
    1248              : 
    1249              : class dedupe_key
    1250              : {
    1251              : public:
    1252         6451 :   dedupe_key (const saved_diagnostic &sd)
    1253         6451 :   : m_sd (sd),
    1254         6451 :     m_loc (sd.m_ploc.m_event_loc_info.m_loc)
    1255              :   {
    1256              :   }
    1257              : 
    1258        68389 :   hashval_t hash () const
    1259              :   {
    1260        68389 :     inchash::hash hstate;
    1261              :     // TODO: m_sd
    1262        68389 :     return hstate.end ();
    1263              :   }
    1264        53108 :   bool operator== (const dedupe_key &other) const
    1265              :   {
    1266        53108 :     return (m_sd == other.m_sd
    1267        53108 :             && m_loc == other.m_loc);
    1268              :   }
    1269              : 
    1270        33322 :   location_t get_location () const { return m_loc; }
    1271              : 
    1272              :   /* A qsort comparator for use by dedupe_winners::emit_best
    1273              :      to sort them into location_t order.  */
    1274              : 
    1275              :   static int
    1276        33322 :   comparator (const void *p1, const void *p2)
    1277              :   {
    1278        33322 :     const dedupe_key *pk1 = *(const dedupe_key * const *)p1;
    1279        33322 :     const dedupe_key *pk2 = *(const dedupe_key * const *)p2;
    1280              : 
    1281        33322 :     location_t loc1 = pk1->get_location ();
    1282        33322 :     location_t loc2 = pk2->get_location ();
    1283              : 
    1284        33322 :     if (int cmp = linemap_compare_locations (line_table, loc2, loc1))
    1285              :       return cmp;
    1286         1302 :     if (int cmp = ((int)pk1->m_sd.get_epath_length ()
    1287         1302 :                    - (int)pk2->m_sd.get_epath_length ()))
    1288              :       return cmp;
    1289          882 :     if (int cmp = strcmp (pk1->m_sd.m_d->get_kind (),
    1290          882 :                           pk2->m_sd.m_d->get_kind ()))
    1291              :       return cmp;
    1292              :     return 0;
    1293              :   }
    1294              : 
    1295              :   const saved_diagnostic &m_sd;
    1296              :   location_t m_loc;
    1297              : };
    1298              : 
    1299              : /* Traits for use by dedupe_winners.  */
    1300              : 
    1301              : class dedupe_hash_map_traits
    1302              : {
    1303              : public:
    1304              :   typedef const dedupe_key *key_type;
    1305              :   typedef saved_diagnostic *value_type;
    1306              :   typedef saved_diagnostic *compare_type;
    1307              : 
    1308        68389 :   static inline hashval_t hash (const key_type &v)
    1309              :   {
    1310        68389 :     return v->hash ();
    1311              :   }
    1312        53108 :   static inline bool equal_keys (const key_type &k1, const key_type &k2)
    1313              :   {
    1314        53108 :     return *k1 == *k2;
    1315              :   }
    1316              :   template <typename T>
    1317              :   static inline void remove (T &)
    1318              :   {
    1319              :     // TODO
    1320              :   }
    1321              :   template <typename T>
    1322           66 :   static inline void mark_deleted (T &entry)
    1323              :   {
    1324           66 :     entry.m_key = reinterpret_cast<key_type> (1);
    1325              :   }
    1326              :   template <typename T>
    1327            0 :   static inline void mark_empty (T &entry)
    1328              :   {
    1329            0 :     entry.m_key = nullptr;
    1330              :   }
    1331              :   template <typename T>
    1332       159640 :   static inline bool is_deleted (const T &entry)
    1333              :   {
    1334       159640 :     return entry.m_key == reinterpret_cast<key_type> (1);
    1335              :   }
    1336              :   template <typename T>
    1337       571986 :   static inline bool is_empty (const T &entry)
    1338              :   {
    1339       571986 :     return entry.m_key == nullptr;
    1340              :   }
    1341              :   static const bool empty_zero_p = true;
    1342              : };
    1343              : 
    1344              : /* A class for deduplicating diagnostics and finding (and emitting) the
    1345              :    best saved_diagnostic within each partition.  */
    1346              : 
    1347              : class dedupe_winners
    1348              : {
    1349              : public:
    1350         1650 :   ~dedupe_winners ()
    1351              :   {
    1352              :     /* Delete all keys, but not the saved_diagnostics.  */
    1353         6036 :     for (map_t::iterator iter = m_map.begin ();
    1354         6036 :          iter != m_map.end ();
    1355         4386 :          ++iter)
    1356         4386 :       delete (*iter).first;
    1357         1650 :   }
    1358              : 
    1359              :   /* Determine an exploded_path for SD using PF and, if it's feasible,
    1360              :      determine if SD is the best seen so far for its dedupe_key.
    1361              :      Record the winning SD for each dedupe_key.  */
    1362              : 
    1363         6671 :   void add (logger *logger,
    1364              :             epath_finder *pf,
    1365              :             saved_diagnostic *sd)
    1366              :   {
    1367              :     /* Determine best epath for SD.  */
    1368         6671 :     if (!sd->calc_best_epath (pf))
    1369          220 :       return;
    1370              : 
    1371         6451 :     const exploded_path *epath = sd->get_best_epath ();
    1372         6451 :     gcc_assert (epath);
    1373              : 
    1374              :     /* Now we have an exploded path, use it for pending_locations that are
    1375              :        affected by such things, and for deduplication.  */
    1376         6451 :     if (sd->m_ploc.m_fixer_for_epath)
    1377         1070 :       sd->m_ploc.m_fixer_for_epath->fixup_for_epath (*epath, sd->m_ploc);
    1378              : 
    1379         6451 :     dedupe_key *key = new dedupe_key (*sd);
    1380         6451 :     if (saved_diagnostic **slot = m_map.get (key))
    1381              :       {
    1382         1999 :         if (logger)
    1383            0 :           logger->log ("already have this dedupe_key");
    1384              : 
    1385         1999 :         saved_diagnostic *cur_best_sd = *slot;
    1386              : 
    1387         1999 :         if (sd->get_epath_length () < cur_best_sd->get_epath_length ())
    1388              :           {
    1389              :             /* We've got a shorter path for the key; replace
    1390              :                the current candidate, marking it as a duplicate of SD.  */
    1391          144 :             if (logger)
    1392            0 :               logger->log ("length %i is better than existing length %i;"
    1393              :                            " taking over this dedupe_key",
    1394              :                            sd->get_epath_length (),
    1395              :                            cur_best_sd->get_epath_length ());
    1396          144 :             sd->add_duplicate (cur_best_sd);
    1397          144 :             *slot = sd;
    1398              :           }
    1399              :         else
    1400              :           /* We haven't beaten the current best candidate; add SD
    1401              :              as a duplicate of it.  */
    1402              :           {
    1403         1855 :             if (logger)
    1404            0 :               logger->log ("length %i isn't better than existing length %i;"
    1405              :                            " dropping this candidate",
    1406              :                            sd->get_epath_length (),
    1407              :                            cur_best_sd->get_epath_length ());
    1408         1855 :             cur_best_sd->add_duplicate (sd);
    1409              :           }
    1410         1999 :         delete key;
    1411              :       }
    1412              :     else
    1413              :       {
    1414              :         /* This is the first candidate for this key.  */
    1415         4452 :         m_map.put (key, sd);
    1416         4452 :         if (logger)
    1417            2 :           logger->log ("first candidate for this dedupe_key");
    1418              :       }
    1419              :   }
    1420              : 
    1421              :   /* Handle interactions between the dedupe winners, so that some
    1422              :      diagnostics can supercede others (of different kinds).
    1423              : 
    1424              :      We want use-after-free to supercede use-of-uninitialized-value,
    1425              :      so that if we have these at the same stmt, we don't emit
    1426              :      a use-of-uninitialized, just the use-after-free.  */
    1427              : 
    1428         1650 :   void handle_interactions (diagnostic_manager *dm)
    1429              :   {
    1430         1650 :     LOG_SCOPE (dm->get_logger ());
    1431         1650 :     auto_vec<const dedupe_key *> superceded;
    1432         6102 :     for (auto outer : m_map)
    1433              :       {
    1434         4452 :         const saved_diagnostic *outer_sd = outer.second;
    1435        40393 :         for (auto inner : m_map)
    1436              :           {
    1437        31555 :             const saved_diagnostic *inner_sd = inner.second;
    1438        31555 :             if (inner_sd->supercedes_p (*outer_sd))
    1439              :               {
    1440           66 :                 superceded.safe_push (outer.first);
    1441           66 :                 if (dm->get_logger ())
    1442            0 :                   dm->log ("sd[%i] \"%s\" superceded by sd[%i] \"%s\"",
    1443            0 :                            outer_sd->get_index (), outer_sd->m_d->get_kind (),
    1444            0 :                            inner_sd->get_index (), inner_sd->m_d->get_kind ());
    1445              :                 break;
    1446              :               }
    1447              :           }
    1448              :       }
    1449         1826 :     for (auto iter : superceded)
    1450           66 :       m_map.remove (iter);
    1451         1650 :   }
    1452              : 
    1453              :  /* Emit the simplest diagnostic within each set.  */
    1454              : 
    1455         1650 :   void emit_best (diagnostic_manager *dm,
    1456              :                   const exploded_graph &eg)
    1457              :   {
    1458         1650 :     LOG_SCOPE (dm->get_logger ());
    1459              : 
    1460              :     /* Get keys into a vec for sorting.  */
    1461         1650 :     auto_vec<const dedupe_key *> keys (m_map.elements ());
    1462         1650 :     for (map_t::iterator iter = m_map.begin ();
    1463         6036 :          iter != m_map.end ();
    1464         4386 :          ++iter)
    1465         4386 :       keys.quick_push ((*iter).first);
    1466              : 
    1467         3252 :     dm->log ("# keys after de-duplication: %i", keys.length ());
    1468              : 
    1469              :     /* Sort into a good emission order.  */
    1470         1650 :     keys.qsort (dedupe_key::comparator);
    1471              : 
    1472              :     /* Emit the best saved_diagnostics for each key.  */
    1473         1650 :     int i;
    1474         1650 :     const dedupe_key *key;
    1475         7638 :     FOR_EACH_VEC_ELT (keys, i, key)
    1476              :       {
    1477         4386 :         saved_diagnostic **slot = m_map.get (key);
    1478         4386 :         gcc_assert (*slot);
    1479         4386 :         saved_diagnostic *sd = *slot;
    1480         4386 :         dm->emit_saved_diagnostic (eg, *sd);
    1481              :       }
    1482         1650 :   }
    1483              : 
    1484              : private:
    1485              :   /* This maps from each dedupe_key to a current best saved_diagnostic.  */
    1486              : 
    1487              :   typedef hash_map<const dedupe_key *, saved_diagnostic *,
    1488              :                    dedupe_hash_map_traits> map_t;
    1489              :   map_t m_map;
    1490              : };
    1491              : 
    1492              : /* Emit all saved diagnostics.  */
    1493              : 
    1494              : void
    1495         3573 : diagnostic_manager::emit_saved_diagnostics (const exploded_graph &eg)
    1496              : {
    1497         3573 :   LOG_SCOPE (get_logger ());
    1498         3573 :   auto_timevar tv (TV_ANALYZER_DIAGNOSTICS);
    1499         5223 :   log ("# saved diagnostics: %i", m_saved_diagnostics.length ());
    1500         3573 :   log ("# disabled diagnostics: %i", m_num_disabled_diagnostics);
    1501         3573 :   if (get_logger ())
    1502              :     {
    1503              :       unsigned i;
    1504              :       saved_diagnostic *sd;
    1505            7 :       FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
    1506            2 :         log ("[%i] sd: %qs at EN: %i, SN: %i",
    1507            2 :              i, sd->m_d->get_kind (), sd->m_ploc.m_enode->m_index,
    1508            2 :              sd->get_supernode ()->m_id);
    1509              :     }
    1510              : 
    1511         3573 :   if (m_saved_diagnostics.length () == 0)
    1512         1923 :     return;
    1513              : 
    1514              :   /* Compute the shortest_paths once, sharing it between all diagnostics.  */
    1515         1650 :   epath_finder pf (eg);
    1516              : 
    1517              :   /* Iterate through all saved diagnostics, adding them to a dedupe_winners
    1518              :      instance.  This partitions the saved diagnostics by dedupe_key,
    1519              :      generating exploded_paths for them, and retaining the best one in each
    1520              :      partition.  */
    1521         1650 :   dedupe_winners best_candidates;
    1522              : 
    1523         1650 :   int i;
    1524         1650 :   saved_diagnostic *sd;
    1525         9971 :   FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
    1526         6671 :     best_candidates.add (get_logger (), &pf, sd);
    1527              : 
    1528         1650 :   best_candidates.handle_interactions (this);
    1529              : 
    1530              :   /* For each dedupe-key, call emit_saved_diagnostic on the "best"
    1531              :      saved_diagnostic.  */
    1532         1650 :   best_candidates.emit_best (this, eg);
    1533         3573 : }
    1534              : 
    1535              : /* Custom subclass of diagnostics::metadata which, for SARIF output,
    1536              :    populates the property bag of the diagnostic's "result" object
    1537              :    with information from the saved_diagnostic and the
    1538              :    pending_diagnostic.  */
    1539              : 
    1540         4386 : class pending_diagnostic_metadata : public diagnostics::metadata
    1541              : {
    1542              : public:
    1543         4386 :   pending_diagnostic_metadata (const saved_diagnostic &sd)
    1544         4386 :   : m_sd (sd)
    1545              :   {
    1546              :   }
    1547              : 
    1548              :   void
    1549           33 :   maybe_add_sarif_properties (diagnostics::sarif_object &result_obj)
    1550              :     const override
    1551              :   {
    1552           33 :     m_sd.maybe_add_sarif_properties (result_obj);
    1553           33 :   }
    1554              : 
    1555              : private:
    1556              :   const saved_diagnostic &m_sd;
    1557              : };
    1558              : 
    1559              : /* Given a saved_diagnostic SD with m_best_epath through EG,
    1560              :    create an checker_path of suitable events and use it to call
    1561              :    SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic.  */
    1562              : 
    1563              : void
    1564         4386 : diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
    1565              :                                            saved_diagnostic &sd)
    1566              : {
    1567         4386 :   LOG_SCOPE (get_logger ());
    1568         4386 :   log ("sd[%i]: %qs at SN: %i",
    1569         4386 :        sd.get_index (), sd.m_d->get_kind (), sd.get_supernode ()->m_id);
    1570         5739 :   log ("num dupes: %i", sd.get_num_dupes ());
    1571              : 
    1572         4386 :   exploded_path *epath = sd.get_best_epath ();
    1573         4386 :   gcc_assert (epath);
    1574              : 
    1575         4386 :   epath->maybe_log (get_logger (), "best epath");
    1576              : 
    1577              :   /* Precompute all enodes from which the diagnostic is reachable.  */
    1578         4386 :   path_builder pb (eg, *epath, sd.get_feasibility_problem (), sd);
    1579              : 
    1580              :   /* Annotate EPATH with information specific to the diagnostic, such
    1581              :      as pertinent data flow events.  */
    1582         4386 :   annotate_exploded_path (pb, *epath);
    1583         4386 :   epath->maybe_log (get_logger (), "best epath with annotations");
    1584              : 
    1585              :   /* This is the diagnostics::paths::path instance that will be built for
    1586              :      the diagnostic.  */
    1587         4386 :   checker_path emission_path (get_logical_location_manager (),
    1588              :                               eg.get_ext_state (),
    1589         4386 :                               get_logger ());
    1590              : 
    1591              :   /* Populate emission_path with a full description of EPATH.  */
    1592         4386 :   build_emission_path (pb, *epath, &emission_path);
    1593              : 
    1594              :   /* Now prune it to just cover the most pertinent events.  */
    1595         4386 :   prune_path (&emission_path, sd.m_sm, sd.m_sval, sd.m_state);
    1596              : 
    1597              :   /* Add any saved events to the path, giving contextual information
    1598              :      about what the analyzer was simulating as the diagnostic was
    1599              :      generated.  These don't get pruned, as they are probably pertinent.  */
    1600         4386 :   sd.add_any_saved_events (emission_path);
    1601              : 
    1602              :   /* Add a final event to the path, covering the diagnostic itself.  */
    1603         4386 :   {
    1604         4386 :     const exploded_node *const enode = epath->get_final_enode ();
    1605         4386 :     sd.m_d->add_final_event (sd.m_sm, enode, sd.m_ploc.m_event_loc_info,
    1606              :                              sd.m_var, sd.m_state, &emission_path);
    1607              :   }
    1608              : 
    1609              :   /* The "final" event might not be final; if the saved_diagnostic has a
    1610              :      trailing eedge stashed, add any events for it.  This is for use
    1611              :      in handling longjmp, to show where a longjmp is rewinding to.  */
    1612         4386 :   if (sd.m_trailing_eedge)
    1613            4 :     add_events_for_eedge (pb, *sd.m_trailing_eedge, &emission_path, nullptr,
    1614              :                           nullptr);
    1615              : 
    1616         4386 :   emission_path.inject_any_inlined_call_events (get_logger ());
    1617              : 
    1618         4386 :   emission_path.prepare_for_emission (sd.m_d.get ());
    1619              : 
    1620         4386 :   location_t loc = sd.m_ploc.m_event_loc_info.m_loc;
    1621         4386 :   loc = sd.m_d->fixup_location (loc, true);
    1622              : 
    1623              :   /* Allow the pending_diagnostic to fix up the locations of events.  */
    1624         4386 :   emission_path.fixup_locations (sd.m_d.get ());
    1625              : 
    1626         4386 :   gcc_rich_location rich_loc (loc);
    1627         4386 :   rich_loc.set_path (&emission_path);
    1628              : 
    1629         4386 :   auto_diagnostic_group d;
    1630         4386 :   auto_cfun sentinel (sd.get_supernode ()->m_fun);
    1631         4386 :   pending_diagnostic_metadata m (sd);
    1632         4386 :   diagnostic_emission_context diag_ctxt (sd, rich_loc, m, get_logger ());
    1633         4386 :   if (sd.m_d->emit (diag_ctxt))
    1634              :     {
    1635         4327 :       sd.emit_any_notes ();
    1636              : 
    1637         4327 :       unsigned num_dupes = sd.get_num_dupes ();
    1638         4327 :       if (flag_analyzer_show_duplicate_count && num_dupes > 0)
    1639            4 :         inform_n (loc, num_dupes,
    1640              :                   "%i duplicate", "%i duplicates",
    1641              :                   num_dupes);
    1642         4327 :       if (flag_dump_analyzer_exploded_paths)
    1643              :         {
    1644            0 :           auto_timevar tv (TV_ANALYZER_DUMP);
    1645            0 :           pretty_printer pp;
    1646            0 :           pp_printf (&pp, "%s.%i.%s.epath.txt",
    1647            0 :                      dump_base_name, sd.get_index (), sd.m_d->get_kind ());
    1648            0 :           char *filename = xstrdup (pp_formatted_text (&pp));
    1649            0 :           epath->dump_to_file (filename, eg.get_ext_state ());
    1650            0 :           inform (loc, "exploded path written to %qs", filename);
    1651            0 :           free (filename);
    1652            0 :         }
    1653              :     }
    1654         4386 : }
    1655              : 
    1656              : const diagnostics::logical_locations::manager &
    1657         4386 : diagnostic_manager::get_logical_location_manager () const
    1658              : {
    1659         4386 :   gcc_assert (global_dc);
    1660         4386 :   auto mgr = global_dc->get_logical_location_manager ();
    1661         4386 :   gcc_assert (mgr);
    1662         4386 :   return *mgr;
    1663              : }
    1664              : 
    1665              : /* Dump C to this logger, indenting each line by the current
    1666              :    indentation level.  */
    1667              : 
    1668              : void
    1669         2575 : logger::log_canvas (const text_art::canvas &c)
    1670              : {
    1671         2575 :   std::string per_line_prefix (m_indent_level, ' ');
    1672         2575 :   c.print_to_pp (get_printer (), per_line_prefix.c_str ());
    1673         2575 :   pp_flush (get_printer ());
    1674         2575 : }
    1675              : 
    1676              : /* Dump OBJ to LOGGER, using OBJ's make_dump_widget member function.  */
    1677              : 
    1678              : template <typename T>
    1679              : void
    1680        26095 : dump_to_logger (const T &obj,
    1681              :                 logger *logger,
    1682              :                 const char *label)
    1683              : {
    1684        26095 :   if (!logger)
    1685        26095 :     return;
    1686           34 :   text_art::theme *theme = global_dc->get_diagram_theme ();
    1687           34 :   if (!theme)
    1688              :     return;
    1689              : 
    1690            0 :   logger->log ("%s:", label);
    1691            0 :   logger->inc_indent ();
    1692              : 
    1693            0 :   text_art::style_manager sm;
    1694            0 :   text_art::style tree_style (text_art::get_style_from_color_cap_name ("note"));
    1695              : 
    1696            0 :   text_art::style::id_t tree_style_id (sm.get_or_create_id (tree_style));
    1697              : 
    1698            0 :   symbolic::node_dump_state nds (sm, *theme, tree_style_id, true, true);
    1699            0 :   if (auto w = obj.make_dump_widget (nds))
    1700              :     {
    1701            0 :       text_art::canvas c (w->to_canvas (nds.m_sm));
    1702            0 :       logger->log_canvas (c);
    1703            0 :     }
    1704              : 
    1705            0 :   logger->dec_indent ();
    1706            0 : }
    1707              : 
    1708              : static void
    1709        26095 : log_region_model (logger *logger,
    1710              :                   const char *label,
    1711              :                   const region_model &model)
    1712              : {
    1713           13 :   dump_to_logger<region_model> (model, logger, label);
    1714            0 : }
    1715              : 
    1716        38217 : class epath_rewind_context : public rewind_context
    1717              : {
    1718              : public:
    1719        38217 :   epath_rewind_context (logger *logger,
    1720              :                         diagnostic_state input_state,
    1721              :                         state_transition *&last_state_transition,
    1722              :                         exploded_path::element_t &epath_element,
    1723              :                         const region_model &src_model,
    1724              :                         const region_model &dst_model)
    1725              :   : rewind_context (logger, input_state),
    1726        38217 :     m_last_state_transition (last_state_transition),
    1727        38217 :     m_epath_element (epath_element),
    1728        38217 :     m_src_model (src_model),
    1729        38217 :     m_dst_model (dst_model)
    1730              :   {
    1731        38217 :   }
    1732              : 
    1733              :   const region_model &
    1734         1077 :   get_src_region_model () const final override
    1735              :   {
    1736         1077 :     return m_src_model;
    1737              :   }
    1738              : 
    1739              :   const region_model &
    1740         2746 :   get_dst_region_model () const final override
    1741              :   {
    1742         2746 :     return m_dst_model;
    1743              :   }
    1744              : 
    1745              :   bool
    1746        10954 :   could_be_affected_by_write_p (tree lhs) final override
    1747              :   {
    1748        10954 :     if (!m_input.m_region_holding_value)
    1749              :       return false;
    1750              : 
    1751          426 :     if (TREE_CODE (lhs) == SSA_NAME)
    1752          372 :       if (tree decl = m_input.m_region_holding_value->maybe_get_decl ())
    1753          197 :         return decl == lhs;
    1754              : 
    1755              :     return true;
    1756              :   }
    1757              : 
    1758              :   void
    1759           79 :   add_state_transition (std::unique_ptr<state_transition> st) final override
    1760              :   {
    1761           79 :     gcc_assert (st.get ());
    1762           79 :     if (m_logger)
    1763              :       {
    1764            0 :         m_logger->start_log_line ();
    1765            0 :         m_logger->log_partial ("adding state transition: ");
    1766            0 :         st->dump_to_pp (m_logger->get_printer ());
    1767            0 :         m_logger->end_log_line ();
    1768              :       }
    1769              : 
    1770              :     /* Chain up the state_transition instances, so that each state transition
    1771              :        has a pointer to the one that occurred before it (but was created after
    1772              :        it, since we are rewinding the epath).  */
    1773           79 :     if (m_last_state_transition)
    1774           32 :       m_last_state_transition->m_prev_state_transition = st.get ();
    1775           79 :     m_last_state_transition = st.get ();
    1776              : 
    1777           79 :     m_epath_element.m_state_transition = std::move (st);
    1778           79 :   }
    1779              : 
    1780              : private:
    1781              :   state_transition *&m_last_state_transition;
    1782              :   exploded_path::element_t &m_epath_element;
    1783              :   const region_model &m_src_model;
    1784              :   const region_model &m_dst_model;
    1785              : };
    1786              : 
    1787              : /* Return a region_model for the state after any operation/custom_edge_info
    1788              :    on EEDGE, but without state purging or state merging.  Use SRC_MODEL as
    1789              :    the source state.
    1790              : 
    1791              :    We do this to make it easier to rewind state transitions in
    1792              :    diagnostic_manager::annotate_exploded_path.  */
    1793              : 
    1794              : static region_model
    1795        44025 : make_raw_dst_region_model (logger *logger,
    1796              :                            const exploded_edge *eedge,
    1797              :                            const region_model &src_model,
    1798              :                            const supergraph &sg)
    1799              : {
    1800        44025 :   LOG_SCOPE (logger);
    1801              : 
    1802              :   /* Update cfun and input_location in case of an ICE: make it easier to
    1803              :      track down which source construct we're failing to handle.  */
    1804        83664 :   auto_cfun sentinel (eedge->m_src->get_function ());
    1805        44025 :   input_location = eedge->m_src->get_location ();
    1806              : 
    1807        44025 :   region_model_context *const ctxt = nullptr;
    1808              : 
    1809        44025 :   if (logger)
    1810              :     {
    1811           13 :       log_region_model (logger, "src_model", src_model);
    1812           13 :       log_region_model (logger, "dst_model",
    1813           13 :                         *eedge->m_dest->get_state ().m_region_model);
    1814              :     }
    1815              : 
    1816        44025 :   if (eedge->m_custom_info)
    1817              :     {
    1818         2891 :       if (logger)
    1819              :         {
    1820            0 :           logger->start_log_line ();
    1821            0 :           eedge->m_custom_info->print (logger->get_printer ());
    1822            0 :           logger->end_log_line ();
    1823              :         }
    1824         2891 :       region_model new_model (src_model);
    1825         2891 :       eedge->m_custom_info->update_model (&new_model, eedge, ctxt);
    1826         2891 :       if (logger)
    1827            0 :         log_region_model (logger, "new model after custom_info", new_model);
    1828              :       return new_model;
    1829              :     }
    1830              :   else
    1831              :     {
    1832        41134 :       const superedge *sedge = eedge->m_sedge;
    1833        41134 :       if (sedge)
    1834              :         {
    1835        36471 :           if (logger)
    1836              :             {
    1837           11 :               label_text desc (sedge->get_description (false));
    1838           11 :               logger->log ("  sedge: SN:%i -> SN:%i %s",
    1839           11 :                            sedge->m_src->m_id,
    1840           11 :                            sedge->m_dest->m_id,
    1841              :                            desc.get ());
    1842           11 :             }
    1843              : 
    1844        36471 :           if (auto op = sedge->get_op ())
    1845              :             {
    1846        26067 :               if (logger)
    1847              :                 {
    1848            6 :                   logger->start_log_line ();
    1849            6 :                   op->print_as_edge_label (logger->get_printer (), false);
    1850            6 :                   logger->end_log_line ();
    1851              :                 }
    1852        26067 :               feasibility_state fs (src_model, sg);
    1853        26067 :               op->execute_for_feasibility (*eedge,
    1854              :                                            fs,
    1855              :                                            ctxt,
    1856              :                                            nullptr);
    1857        26067 :               log_region_model (logger, "after operation, fs model",
    1858        26067 :                                 fs.get_model ());
    1859        26067 :               return fs.get_model ();
    1860        26067 :             }
    1861              :           else
    1862              :             {
    1863        10404 :               if (logger)
    1864            5 :                 logger->log ("null operation, using src_model");
    1865        10404 :               return src_model;
    1866              :             }
    1867              :         }
    1868              :       else
    1869              :         {
    1870              :           /* Special-case the initial eedge from the origin node to the
    1871              :              initial function by pushing a frame for it.  */
    1872         4663 :           if (eedge->m_src->m_index == 0)
    1873              :             {
    1874         4273 :               function *fun = eedge->m_dest->get_function ();
    1875         4273 :               gcc_assert (fun);
    1876         4273 :               region_model new_model (src_model);
    1877         4273 :               new_model.push_frame (*fun, nullptr, nullptr, ctxt);
    1878         4273 :               if (logger)
    1879              :                 {
    1880            2 :                   logger->log ("  pushing frame for %qD", fun->decl);
    1881            2 :                   log_region_model (logger, "new model", new_model);
    1882              :                 }
    1883         4273 :               return new_model;
    1884         4273 :             }
    1885              :         }
    1886              :     }
    1887              : 
    1888          390 :   return src_model;
    1889        44025 : }
    1890              : 
    1891              : /* Populate the elements of EPATH with diagnostic_state and state_transition
    1892              :    information pertinent to the pending diagnostic.  */
    1893              : 
    1894              : void
    1895         4386 : diagnostic_manager::annotate_exploded_path (const path_builder &pb,
    1896              :                                             exploded_path &epath) const
    1897              : {
    1898         4386 :   auto logger = get_logger ();
    1899         4386 :   LOG_SCOPE (logger);
    1900              : 
    1901              :   // TODO: consolidate this with build_emission_path?
    1902         4386 :   interesting_t interest;
    1903         4386 :   pb.get_pending_diagnostic ()->mark_interesting_stuff (&interest);
    1904              : 
    1905         4386 :   gcc_assert (epath.m_elements.size () > 0);
    1906              : 
    1907         4386 :   diagnostic_state curr_state;
    1908         4386 :   state_transition *last_state_transition = nullptr;
    1909              : 
    1910         4386 :   if (interest.m_read_regions.size () > 0)
    1911          601 :     curr_state = interest.m_read_regions[0];
    1912              : 
    1913              :   /* Walk EPATH forwards, generating region_model instances for the elements
    1914              :      of EPATH without state purging or merging, so that we can reliably
    1915              :      rewind state.  */
    1916         4386 :   std::vector<region_model> src_models;
    1917         4386 :   std::vector<region_model> dst_models;
    1918        48411 :   for (int idx = 0; idx < epath.m_elements.size (); ++idx)
    1919              :     {
    1920        44025 :       auto eedge = epath.m_elements[idx].m_eedge;
    1921        44025 :       if (logger)
    1922           13 :         logger->log ("edge[%i]: considering EN %i -> EN %i",
    1923              :                      idx,
    1924           13 :                      eedge->m_src->m_index,
    1925           13 :                      eedge->m_dest->m_index);
    1926        44025 :       region_model src_model (pb.get_ext_state ().get_node_manager ());
    1927        44025 :       if (idx > 0)
    1928        39639 :         src_model = dst_models[idx - 1];
    1929        44025 :       src_models.push_back (src_model);
    1930        44025 :       dst_models.push_back
    1931        44025 :         (make_raw_dst_region_model (logger,
    1932              :                                     eedge,
    1933              :                                     src_model,
    1934              :                                     pb.get_supergraph ()));
    1935        44025 :     }
    1936              : 
    1937              :   /* Walk EPATH backwards, using the region_models we just built,
    1938              :      propagating annotation information backwards.  */
    1939        41972 :   for (int idx = epath.m_elements.size () - 1; idx >= 0; --idx)
    1940              :     {
    1941        38217 :       exploded_path::element_t &iter_element = epath.m_elements[idx];
    1942        38217 :       if (logger)
    1943              :         {
    1944           11 :           logger->log ("edge[%i]: considering rewinding EN %i -> EN %i",
    1945              :                        idx,
    1946           11 :                        iter_element.m_eedge->m_src->m_index,
    1947           11 :                        iter_element.m_eedge->m_dest->m_index);
    1948           11 :           logger->start_log_line ();
    1949           11 :           logger->log_partial ("curr_state: ");
    1950           11 :           curr_state.dump_to_pp (logger->get_printer ());
    1951           11 :           logger->end_log_line ();
    1952              :         }
    1953        38217 :       iter_element.m_state_at_dst = curr_state;
    1954        38217 :       const exploded_edge *eedge = iter_element.m_eedge;
    1955        38217 :       gcc_assert (eedge);
    1956              : 
    1957        38217 :       epath_rewind_context ctxt (logger, curr_state,
    1958              :                                  last_state_transition, iter_element,
    1959        38217 :                                  src_models[idx], dst_models[idx]);
    1960        38217 :       if (eedge->m_custom_info)
    1961              :         {
    1962         2586 :           if (logger)
    1963              :             {
    1964            0 :               logger->start_log_line ();
    1965            0 :               logger->log_partial ("custom_edge_info: ");
    1966            0 :               eedge->m_custom_info->print (logger->get_printer ());
    1967            0 :               logger->end_log_line ();
    1968              :             }
    1969         2586 :           if (!eedge->m_custom_info->try_to_rewind_data_flow (ctxt))
    1970              :             {
    1971          516 :               if (logger)
    1972            0 :                 logger->log ("could not rewind custom info");
    1973              :               return;
    1974              :             }
    1975              :         }
    1976        35631 :       else if (const operation *op = eedge->maybe_get_op ())
    1977              :         {
    1978        22122 :           if (logger)
    1979              :             {
    1980            6 :               logger->start_log_line ();
    1981            6 :               logger->log_partial ("op: ");
    1982            6 :               op->print_as_edge_label (logger->get_printer (), false);
    1983            6 :               logger->end_log_line ();
    1984              :             }
    1985        22122 :           if (!op->try_to_rewind_data_flow (ctxt))
    1986              :             {
    1987          115 :               if (logger)
    1988            1 :                 logger->log ("could not rewind op");
    1989              :               return;
    1990              :             }
    1991              :         }
    1992              : 
    1993        37586 :       iter_element.m_state_at_src = ctxt.m_output;
    1994        37586 :       curr_state = ctxt.m_output;
    1995        37586 :       if (logger)
    1996              :         {
    1997           10 :           logger->log ("rewound");
    1998           10 :           logger->start_log_line ();
    1999           10 :           logger->log_partial ("curr_state: ");
    2000           10 :           curr_state.dump_to_pp (logger->get_printer ());
    2001           10 :           logger->end_log_line ();
    2002              :         }
    2003        37586 :     }
    2004         8772 : }
    2005              : 
    2006              : /* Emit a "path" of events to EMISSION_PATH describing the exploded path
    2007              :    EPATH within EG.  */
    2008              : 
    2009              : void
    2010         4386 : diagnostic_manager::build_emission_path (const path_builder &pb,
    2011              :                                          const exploded_path &epath,
    2012              :                                          checker_path *emission_path) const
    2013              : {
    2014         4386 :   LOG_SCOPE (get_logger ());
    2015              : 
    2016         4386 :   interesting_t interest;
    2017         4386 :   pb.get_pending_diagnostic ()->mark_interesting_stuff (&interest);
    2018              : 
    2019              :   /* Add region creation events for any globals of interest, at the
    2020              :      beginning of the path.  */
    2021         4386 :   {
    2022         8539 :     for (auto reg : interest.m_region_creation)
    2023         1403 :       switch (reg->get_memory_space ())
    2024              :         {
    2025         1138 :         default:
    2026         1138 :           continue;
    2027          265 :         case MEMSPACE_CODE:
    2028          265 :         case MEMSPACE_GLOBALS:
    2029          265 :         case MEMSPACE_READONLY_DATA:
    2030          265 :           {
    2031          265 :             const region *base_reg = reg->get_base_region ();
    2032          265 :             if (tree decl = base_reg->maybe_get_decl ())
    2033          255 :               if (DECL_P (decl)
    2034          255 :                   && useful_location_p (DECL_SOURCE_LOCATION (decl)))
    2035              :                 {
    2036          255 :                   emission_path->add_region_creation_events
    2037          255 :                     (pb.get_pending_diagnostic (),
    2038              :                      reg, nullptr,
    2039          255 :                      event_loc_info (DECL_SOURCE_LOCATION (decl),
    2040              :                                      NULL_TREE,
    2041          255 :                                      0),
    2042          255 :                      m_verbosity > 3);
    2043              :                 }
    2044              :           }
    2045         1138 :         }
    2046              :   }
    2047              : 
    2048              :   /* Walk EPATH, adding events as appropriate.  */
    2049        48411 :   for (unsigned i = 0; i < epath.m_elements.size (); ++i)
    2050              :     {
    2051        44025 :       const exploded_edge *eedge = epath.m_elements[i].m_eedge;
    2052        44025 :       gcc_assert (eedge);
    2053        44025 :       add_events_for_eedge (pb, *eedge, emission_path, &interest,
    2054        44025 :                             epath.m_elements[i].m_state_transition.get ());
    2055              :     }
    2056         4386 :   add_event_on_final_node (pb, epath.get_final_enode (),
    2057              :                            emission_path, &interest);
    2058         4386 : }
    2059              : 
    2060              : /* Emit a region_creation_event when requested on the last statement in
    2061              :    the path.
    2062              : 
    2063              :    If a region_creation_event should be emitted on the last statement of the
    2064              :    path, we need to peek to the successors to get whether the final enode
    2065              :    created a region.
    2066              : */
    2067              : 
    2068              : void
    2069         4386 : diagnostic_manager::add_event_on_final_node (const path_builder &pb,
    2070              :                                              const exploded_node *final_enode,
    2071              :                                              checker_path *emission_path,
    2072              :                                              interesting_t *interest) const
    2073              : {
    2074         4386 :   const program_point &src_point = final_enode->get_point ();
    2075         4386 :   const int src_stack_depth = src_point.get_stack_depth ();
    2076         4386 :   const program_state &src_state = final_enode->get_state ();
    2077         4386 :   const region_model *src_model = src_state.m_region_model;
    2078              : 
    2079         4386 :   unsigned j;
    2080         4386 :   exploded_edge *e;
    2081         7863 :   FOR_EACH_VEC_ELT (final_enode->m_succs, j, e)
    2082              :   {
    2083         3554 :     exploded_node *dst = e->m_dest;
    2084         3554 :     const program_state &dst_state = dst->get_state ();
    2085         3554 :     const region_model *dst_model = dst_state.m_region_model;
    2086         3554 :     if (src_model->get_dynamic_extents ()
    2087         3554 :         != dst_model->get_dynamic_extents ())
    2088              :       {
    2089              :         unsigned i;
    2090              :         const region *reg;
    2091              :         bool emitted = false;
    2092          423 :         FOR_EACH_VEC_ELT (interest->m_region_creation, i, reg)
    2093              :           {
    2094           93 :             const region *base_reg = reg->get_base_region ();
    2095           93 :             const svalue *old_extents
    2096           93 :         = src_model->get_dynamic_extents (base_reg);
    2097           93 :             const svalue *new_extents
    2098           93 :         = dst_model->get_dynamic_extents (base_reg);
    2099           93 :             if (old_extents == nullptr && new_extents != nullptr)
    2100           81 :               switch (base_reg->get_kind ())
    2101              :                 {
    2102              :                 default:
    2103              :                   break;
    2104           77 :                 case RK_HEAP_ALLOCATED:
    2105           77 :                 case RK_ALLOCA:
    2106           77 :                   emission_path->add_region_creation_events
    2107          154 :                     (pb.get_pending_diagnostic (),
    2108              :                      reg,
    2109              :                      dst_model,
    2110           77 :                      event_loc_info (src_point.get_location (),
    2111              :                                      src_point.get_fndecl (),
    2112          154 :                                      src_stack_depth),
    2113              :                      false);
    2114           77 :                   emitted = true;
    2115           77 :                   break;
    2116              :                 }
    2117              :           }
    2118          330 :         if (emitted)
    2119              :           break;
    2120              :       }
    2121              :   }
    2122         4386 : }
    2123              : 
    2124              : /* Subclass of state_change_visitor that creates state_change_event
    2125              :    instances.  */
    2126              : 
    2127        44029 : class state_change_event_creator : public state_change_visitor
    2128              : {
    2129              : public:
    2130        44029 :   state_change_event_creator (const path_builder &pb,
    2131              :                               const exploded_edge &eedge,
    2132              :                               checker_path *emission_path)
    2133        44029 :     : m_pb (pb),
    2134        44029 :       m_eedge (eedge),
    2135        44029 :       m_emission_path (emission_path)
    2136              :   {}
    2137              : 
    2138          120 :   bool on_global_state_change (const state_machine &sm,
    2139              :                                state_machine::state_t src_sm_val,
    2140              :                                state_machine::state_t dst_sm_val)
    2141              :     final override
    2142              :   {
    2143          120 :     if (&sm != m_pb.get_sm ())
    2144              :       return false;
    2145           56 :     const exploded_node *src_node = m_eedge.m_src;
    2146           56 :     const exploded_node *dst_node = m_eedge.m_dest;
    2147           56 :     const gimple *stmt = m_eedge.maybe_get_stmt ();
    2148           56 :     const program_state &dst_state = dst_node->get_state ();
    2149              : 
    2150           56 :     m_emission_path->add_event
    2151           56 :       (std::make_unique<state_change_event> (m_eedge.m_src,
    2152              :                                              stmt,
    2153              :                                              sm,
    2154          112 :                                              nullptr,
    2155              :                                              src_sm_val,
    2156              :                                              dst_sm_val,
    2157           56 :                                              nullptr,
    2158              :                                              dst_state,
    2159              :                                              src_node));
    2160           56 :     return false;
    2161              :   }
    2162              : 
    2163         4984 :   bool on_state_change (const state_machine &sm,
    2164              :                         state_machine::state_t src_sm_val,
    2165              :                         state_machine::state_t dst_sm_val,
    2166              :                         const svalue *sval,
    2167              :                         const svalue *dst_origin_sval) final override
    2168              :   {
    2169         4984 :     if (&sm != m_pb.get_sm ())
    2170              :       return false;
    2171              : 
    2172         3964 :     const exploded_node *src_node = m_eedge.m_src;
    2173         3964 :     const exploded_node *dst_node = m_eedge.m_dest;
    2174         3964 :     const gimple *stmt = m_eedge.maybe_get_stmt ();
    2175         3964 :     const program_state &dst_state = dst_node->get_state ();
    2176              : 
    2177         3964 :     m_emission_path->add_event
    2178         3964 :       (std::make_unique<state_change_event> (m_eedge.m_src,
    2179              :                                              stmt,
    2180              :                                              sm,
    2181              :                                              sval,
    2182              :                                              src_sm_val,
    2183              :                                              dst_sm_val,
    2184              :                                              dst_origin_sval,
    2185              :                                              dst_state,
    2186              :                                              src_node));
    2187         3964 :     return false;
    2188              :   }
    2189              : 
    2190              :   const path_builder &m_pb;
    2191              :   const exploded_edge &m_eedge;
    2192              :   checker_path *m_emission_path;
    2193              : };
    2194              : 
    2195              : /* Compare SRC_STATE and DST_STATE (which use EXT_STATE), and call
    2196              :    VISITOR's on_state_change for every sm-state change that occurs
    2197              :    to a tree, and on_global_state_change for every global state change
    2198              :    that occurs.
    2199              : 
    2200              :    This determines the state changes that ought to be reported to
    2201              :    the user: a combination of the effects of changes to sm_state_map
    2202              :    (which maps svalues to sm-states), and of region_model changes
    2203              :    (which map trees to svalues).
    2204              : 
    2205              :    Bail out early and return true if any call to on_global_state_change
    2206              :    or on_state_change returns true, otherwise return false.
    2207              : 
    2208              :    This is split out to make it easier to experiment with changes to
    2209              :    exploded_node granularity (so that we can observe what state changes
    2210              :    lead to state_change_events being emitted).  */
    2211              : 
    2212              : bool
    2213        44029 : for_each_state_change (const program_state &src_state,
    2214              :                        const program_state &dst_state,
    2215              :                        const extrinsic_state &ext_state,
    2216              :                        state_change_visitor *visitor)
    2217              : {
    2218        88058 :   gcc_assert (src_state.m_checker_states.length ()
    2219              :               == ext_state.get_num_checkers ());
    2220        88058 :   gcc_assert (dst_state.m_checker_states.length ()
    2221              :               == ext_state.get_num_checkers ());
    2222       350700 :   for (unsigned i = 0; i < ext_state.get_num_checkers (); i++)
    2223              :     {
    2224       306671 :       const state_machine &sm = ext_state.get_sm (i);
    2225       306671 :       const sm_state_map &src_smap = *src_state.m_checker_states[i];
    2226       306671 :       const sm_state_map &dst_smap = *dst_state.m_checker_states[i];
    2227              : 
    2228              :       /* Add events for any global state changes.  */
    2229       306671 :       if (src_smap.get_global_state () != dst_smap.get_global_state ())
    2230          120 :         if (visitor->on_global_state_change (sm,
    2231              :                                              src_smap.get_global_state (),
    2232              :                                              dst_smap.get_global_state ()))
    2233              :           return true;
    2234              : 
    2235              :       /* Add events for per-svalue state changes.  */
    2236       352431 :       for (sm_state_map::iterator_t iter = dst_smap.begin ();
    2237       659102 :            iter != dst_smap.end ();
    2238        45760 :            ++iter)
    2239              :         {
    2240        45760 :           const svalue *sval = (*iter).first;
    2241        45760 :           state_machine::state_t dst_sm_val = (*iter).second.m_state;
    2242        45760 :           state_machine::state_t src_sm_val
    2243        45760 :             = src_smap.get_state (sval, ext_state);
    2244        45760 :           if (dst_sm_val != src_sm_val)
    2245              :             {
    2246         4984 :               const svalue *origin_sval = (*iter).second.m_origin;
    2247         4984 :               if (visitor->on_state_change (sm, src_sm_val, dst_sm_val,
    2248              :                                             sval, origin_sval))
    2249            0 :                 return true;
    2250              :             }
    2251              :         }
    2252              :     }
    2253              :   return false;
    2254              : }
    2255              : 
    2256              : /* Subroutine of diagnostic_manager::build_emission_path.
    2257              :    Add any events for EEDGE to EMISSION_PATH.  */
    2258              : 
    2259              : void
    2260        44029 : diagnostic_manager::add_events_for_eedge (const path_builder &pb,
    2261              :                                           const exploded_edge &eedge,
    2262              :                                           checker_path *emission_path,
    2263              :                                           interesting_t *interest,
    2264              :                                           const state_transition *state_trans) const
    2265              : {
    2266        44029 :   const exploded_node *src_node = eedge.m_src;
    2267        44029 :   const program_point &src_point = src_node->get_point ();
    2268        44029 :   const int src_stack_depth = src_point.get_stack_depth ();
    2269        44029 :   const exploded_node *dst_node = eedge.m_dest;
    2270        44029 :   const program_point &dst_point = dst_node->get_point ();
    2271        44029 :   const int dst_stack_depth = dst_point.get_stack_depth ();
    2272        44029 :   if (get_logger ())
    2273              :     {
    2274           13 :       get_logger ()->start_log_line ();
    2275           13 :       pretty_printer *pp = get_logger ()->get_printer ();
    2276           13 :       pp_printf (pp, "EN %i -> EN %i: ",
    2277           13 :                  eedge.m_src->m_index,
    2278           13 :                  eedge.m_dest->m_index);
    2279           13 :       src_point.print (pp, format (false));
    2280           13 :       pp_string (pp, "-> ");
    2281           13 :       dst_point.print (pp, format (false));
    2282           13 :       if (state_trans)
    2283              :         {
    2284            0 :           pp_string (pp, " {");
    2285            0 :           state_trans->dump_to_pp (pp);
    2286            0 :           pp_string (pp, "}");
    2287              :         }
    2288           13 :       get_logger ()->end_log_line ();
    2289              :     }
    2290        44029 :   const program_state &src_state = src_node->get_state ();
    2291        44029 :   const program_state &dst_state = dst_node->get_state ();
    2292              : 
    2293        44029 :   bool created_event_for_state_trans = false;
    2294              : 
    2295              :   /* Add state change events for the states that have changed.
    2296              :      We add these before events for superedges, so that if we have a
    2297              :      state_change_event due to following an edge, we'll get this sequence
    2298              :      of events:
    2299              : 
    2300              :       | if (!ptr)
    2301              :       |    ~
    2302              :       |    |
    2303              :       |    (1) assuming 'ptr' is non-NULL  (state_change_event)
    2304              :       |    (2) following 'false' branch... (start_cfg_edge_event)
    2305              :      ...
    2306              :       | do_something (ptr);
    2307              :       | ~~~~~~~~~~~~~^~~~~
    2308              :       |              |
    2309              :       |              (3) ...to here        (end_cfg_edge_event).  */
    2310        44029 :   state_change_event_creator visitor (pb, eedge, emission_path);
    2311        44029 :   for_each_state_change (src_state, dst_state, pb.get_ext_state (),
    2312              :                          &visitor);
    2313              : 
    2314              :   /* Give diagnostics an opportunity to inject extra events, or
    2315              :      to override the rest of this function.  */
    2316        44029 :   pending_diagnostic *pd = pb.get_pending_diagnostic ();
    2317        44029 :   if (pd->maybe_add_custom_events_for_eedge (eedge, emission_path))
    2318              :     return;
    2319              : 
    2320              :   /* Allow non-standard edges to add events, e.g. when rewinding from
    2321              :      longjmp to a setjmp.  */
    2322        43052 :   if (eedge.m_custom_info)
    2323              :     {
    2324         2889 :       eedge.m_custom_info->add_events_to_path (emission_path, eedge, *pd,
    2325              :                                                state_trans);
    2326         2889 :       created_event_for_state_trans = true;
    2327              :     }
    2328              : 
    2329              :   /* Don't add events for insignificant edges at verbosity levels below 3.  */
    2330        43052 :   if (m_verbosity < 3)
    2331        42827 :     if (!significant_edge_p (pb, eedge) && !state_trans)
    2332              :       return;
    2333              : 
    2334              :   /* Add events for operations.  */
    2335        42343 :   if (eedge.m_sedge)
    2336        36435 :     if (auto op = eedge.m_sedge->get_op ())
    2337        26339 :       op->add_any_events_for_eedge (eedge, *emission_path);
    2338              : 
    2339              :   /* Add events for function entry.  */
    2340        42343 :   if (dst_point.get_supernode ()->entry_p ())
    2341              :     {
    2342         5703 :       pb.get_pending_diagnostic ()->add_function_entry_event
    2343         5703 :         (eedge, emission_path,
    2344         5703 :          (state_trans
    2345           23 :           ? state_trans->dyn_cast_state_transition_at_call ()
    2346              :           : nullptr));
    2347         5703 :       created_event_for_state_trans = true;
    2348              :       /* Create region_creation_events for on-stack regions within
    2349              :          this frame.  */
    2350         5703 :       if (interest)
    2351              :         {
    2352              :           unsigned i;
    2353              :           const region *reg;
    2354         7256 :           FOR_EACH_VEC_ELT (interest->m_region_creation, i, reg)
    2355         1553 :             if (const frame_region *frame = reg->maybe_get_frame_region ())
    2356         1964 :               if (frame->get_fndecl () == dst_point.get_fndecl ())
    2357              :                 {
    2358          862 :                   const region *base_reg = reg->get_base_region ();
    2359          862 :                   if (tree decl = base_reg->maybe_get_decl ())
    2360          761 :                     if (DECL_P (decl)
    2361          761 :                         && useful_location_p (DECL_SOURCE_LOCATION (decl)))
    2362              :                       {
    2363          757 :                         emission_path->add_region_creation_events
    2364         1514 :                           (pb.get_pending_diagnostic (),
    2365          757 :                            reg, dst_state.m_region_model,
    2366          757 :                            event_loc_info (DECL_SOURCE_LOCATION (decl),
    2367              :                                            dst_point.get_fndecl (),
    2368          757 :                                            dst_stack_depth),
    2369          757 :                            m_verbosity > 3);
    2370              :                       }
    2371              :                 }
    2372              :         }
    2373              :     }
    2374              : 
    2375              :   /* Look for changes in dynamic extents, which will identify
    2376              :      the creation of heap-based regions and alloca regions.  */
    2377        42343 :   if (interest)
    2378              :     {
    2379        42339 :       const region_model *src_model = src_state.m_region_model;
    2380        42339 :       const region_model *dst_model = dst_state.m_region_model;
    2381        42339 :       if (src_model->get_dynamic_extents ()
    2382        42339 :           != dst_model->get_dynamic_extents ())
    2383              :         {
    2384              :           unsigned i;
    2385              :           const region *reg;
    2386         2813 :           FOR_EACH_VEC_ELT (interest->m_region_creation, i, reg)
    2387              :             {
    2388          437 :               const region *base_reg = reg->get_base_region ();
    2389          437 :               const svalue *old_extents
    2390          437 :                 = src_model->get_dynamic_extents (base_reg);
    2391          437 :               const svalue *new_extents
    2392          437 :                 = dst_model->get_dynamic_extents (base_reg);
    2393          437 :               if (old_extents == nullptr && new_extents != nullptr)
    2394          295 :                 switch (base_reg->get_kind ())
    2395              :                   {
    2396              :                   default:
    2397              :                     break;
    2398          259 :                   case RK_HEAP_ALLOCATED:
    2399          259 :                   case RK_ALLOCA:
    2400          259 :                     emission_path->add_region_creation_events
    2401          259 :                       (pb.get_pending_diagnostic (),
    2402              :                        reg, dst_model,
    2403          259 :                        event_loc_info (src_point.get_location (),
    2404              :                                        src_point.get_fndecl (),
    2405          518 :                                        src_stack_depth),
    2406          259 :                        m_verbosity > 3);
    2407          259 :                     break;
    2408              :                   }
    2409              :             }
    2410              :         }
    2411              :     }
    2412              : 
    2413              :   /* If we have a state transition and haven't yet created an
    2414              :      event that describes it, do so now.  */
    2415        42343 :   if (state_trans && !created_event_for_state_trans)
    2416           44 :     emission_path->add_event
    2417           44 :       (std::make_unique<state_transition_event>
    2418           44 :        (eedge.m_src->get_point (),
    2419              :         state_trans));
    2420              : 
    2421        42343 :   if (pb.get_feasibility_problem ()
    2422        42343 :       && &pb.get_feasibility_problem ()->m_eedge == &eedge)
    2423              :     {
    2424            4 :       pretty_printer pp;
    2425            4 :       pp_format_decoder (&pp) = default_tree_printer;
    2426            4 :       pp_string (&pp,
    2427              :                  "this path would have been rejected as infeasible"
    2428              :                  " at this edge: ");
    2429            4 :       pb.get_feasibility_problem ()->dump_to_pp (&pp);
    2430            4 :       emission_path->add_event
    2431            4 :         (std::make_unique<precanned_custom_event>
    2432            4 :            (event_loc_info (dst_point.get_location (),
    2433              :                             dst_point.get_fndecl (),
    2434            8 :                             dst_stack_depth),
    2435            4 :             pp_formatted_text (&pp)));
    2436            4 :     }
    2437        44029 : }
    2438              : 
    2439              : /* Return true if EEDGE is a significant edge in the path to the diagnostic
    2440              :    for PB.
    2441              : 
    2442              :    Consider all of the sibling out-eedges from the same source enode
    2443              :    as EEDGE.
    2444              :    If there's no path from the destinations of those eedges to the
    2445              :    diagnostic enode, then we have to take this eedge and thus it's
    2446              :    significant.
    2447              : 
    2448              :    Conversely if there is a path from the destination of any other sibling
    2449              :    eedge to the diagnostic enode, then this edge is insignificant.
    2450              : 
    2451              :    Example 1: redundant if-else:
    2452              : 
    2453              :      (A) if (...)            A
    2454              :      (B)   ...              / \
    2455              :          else              B   C
    2456              :      (C)   ...              \ /
    2457              :      (D) [DIAGNOSTIC]        D
    2458              : 
    2459              :      D is reachable by either B or C, so neither of these edges
    2460              :      are significant.
    2461              : 
    2462              :    Example 2: pertinent if-else:
    2463              : 
    2464              :      (A) if (...)                         A
    2465              :      (B)   ...                           / \
    2466              :          else                           B   C
    2467              :      (C)   [NECESSARY CONDITION]        |   |
    2468              :      (D) [POSSIBLE DIAGNOSTIC]          D1  D2
    2469              : 
    2470              :      D becomes D1 and D2 in the exploded graph, where the diagnostic occurs
    2471              :      at D2.  D2 is only reachable via C, so the A -> C edge is significant.
    2472              : 
    2473              :    Example 3: redundant loop:
    2474              : 
    2475              :      (A) while (...)          +-->A
    2476              :      (B)   ...                |  / \
    2477              :      (C) ...                  +-B  C
    2478              :      (D) [DIAGNOSTIC]              |
    2479              :                                    D
    2480              : 
    2481              :      D is reachable from both B and C, so the A->C edge is not significant.  */
    2482              : 
    2483              : bool
    2484        42827 : diagnostic_manager::significant_edge_p (const path_builder &pb,
    2485              :                                         const exploded_edge &eedge) const
    2486              : {
    2487        42827 :   int i;
    2488        42827 :   exploded_edge *sibling;
    2489       118543 :   FOR_EACH_VEC_ELT (eedge.m_src->m_succs, i, sibling)
    2490              :     {
    2491        76425 :       if (sibling == &eedge)
    2492        42433 :         continue;
    2493        33992 :       if (pb.reachable_from_p (sibling->m_dest))
    2494              :         {
    2495          709 :           if (get_logger ())
    2496            0 :             get_logger ()->log ("  edge EN: %i -> EN: %i is insignificant as"
    2497              :                                 " EN: %i is also reachable via"
    2498              :                                 " EN: %i -> EN: %i",
    2499            0 :                                 eedge.m_src->m_index, eedge.m_dest->m_index,
    2500            0 :                                 pb.get_diag_node ()->m_index,
    2501            0 :                                 sibling->m_src->m_index,
    2502              :                                 sibling->m_dest->m_index);
    2503              :           return false;
    2504              :         }
    2505              :     }
    2506              : 
    2507              :   return true;
    2508              : }
    2509              : 
    2510              : /* Prune PATH, based on the verbosity level, to the most pertinent
    2511              :    events for a diagnostic that involves VAR ending in state STATE
    2512              :    (for state machine SM).
    2513              : 
    2514              :    PATH is updated in place, and the redundant checker_events are deleted.
    2515              : 
    2516              :    As well as deleting events, call record_critical_state on events in
    2517              :    which state critical to the pending_diagnostic is being handled; see
    2518              :    the comment for diagnostic_manager::prune_for_sm_diagnostic.  */
    2519              : 
    2520              : void
    2521         4386 : diagnostic_manager::prune_path (checker_path *path,
    2522              :                                 const state_machine *sm,
    2523              :                                 const svalue *sval,
    2524              :                                 state_machine::state_t state) const
    2525              : {
    2526         4386 :   LOG_FUNC (get_logger ());
    2527         4386 :   path->maybe_log (get_logger (), "path");
    2528         4386 :   prune_for_sm_diagnostic (path, sm, sval, state);
    2529         4386 :   prune_interproc_events (path);
    2530         4386 :   if (! flag_analyzer_show_events_in_system_headers)
    2531         4384 :     prune_system_headers (path);
    2532         4386 :   consolidate_conditions (path);
    2533         4386 :   consolidate_unwind_events (path);
    2534         4386 :   finish_pruning (path);
    2535         4386 :   path->maybe_log (get_logger (), "pruned");
    2536         4386 : }
    2537              : 
    2538              : /* A cheap test to determine if EXPR can be the expression of interest in
    2539              :    an sm-diagnostic, so that we can reject cases where we have a non-lvalue.
    2540              :    We don't have always have a model when calling this, so we can't use
    2541              :    tentative_region_model_context, so there can be false positives.  */
    2542              : 
    2543              : static bool
    2544            0 : can_be_expr_of_interest_p (tree expr)
    2545              : {
    2546            0 :   if (!expr)
    2547              :     return false;
    2548              : 
    2549              :   /* Reject constants.  */
    2550            0 :   if (CONSTANT_CLASS_P (expr))
    2551            0 :     return false;
    2552              : 
    2553              :   /* Otherwise assume that it can be an lvalue.  */
    2554              :   return true;
    2555              : }
    2556              : 
    2557              : /* First pass of diagnostic_manager::prune_path: apply verbosity level,
    2558              :    pruning unrelated state change events.
    2559              : 
    2560              :    Iterate backwards through PATH, skipping state change events that aren't
    2561              :    VAR but update the pertinent VAR when state-copying occurs.
    2562              : 
    2563              :    As well as deleting events, call record_critical_state on events in
    2564              :    which state critical to the pending_diagnostic is being handled, so
    2565              :    that the event's get_desc vfunc can potentially supply a more precise
    2566              :    description of the event to the user.
    2567              :    e.g. improving
    2568              :      "calling 'foo' from 'bar'"
    2569              :    to
    2570              :      "passing possibly-NULL pointer 'ptr' to 'foo' from 'bar' as param 1"
    2571              :    when the diagnostic relates to later dereferencing 'ptr'.  */
    2572              : 
    2573              : void
    2574         4386 : diagnostic_manager::prune_for_sm_diagnostic (checker_path *path,
    2575              :                                              const state_machine *sm,
    2576              :                                              const svalue *uncanonicalized_sval,
    2577              :                                              state_machine::state_t state) const
    2578              : {
    2579         4386 :   auto &ext_state = path->get_ext_state ();
    2580         4386 :   const svalue *canonicalized_sval
    2581         4386 :     = sm_state_map::canonicalize_svalue (uncanonicalized_sval, ext_state);
    2582              : 
    2583         4386 :   int idx = path->num_events () - 1;
    2584        70210 :   while (idx >= 0 && idx < (signed)path->num_events ())
    2585              :     {
    2586        32912 :       checker_event *base_event = path->get_checker_event (idx);
    2587        32912 :       if (get_logger ())
    2588              :         {
    2589            6 :           if (sm)
    2590              :             {
    2591            0 :               if (uncanonicalized_sval)
    2592              :                 {
    2593            0 :                   label_text sval_desc = uncanonicalized_sval->get_desc ();
    2594            0 :                   log ("considering event %i (%s), with sval: %qs, state: %qs",
    2595              :                        idx, event_kind_to_string (base_event->get_kind ()),
    2596              :                        sval_desc.get (), state->get_name ());
    2597            0 :                 }
    2598              :               else
    2599            0 :                 log ("considering event %i (%s), with global state: %qs",
    2600              :                      idx, event_kind_to_string (base_event->get_kind ()),
    2601              :                      state->get_name ());
    2602              :             }
    2603              :           else
    2604            6 :             log ("considering event %i", idx);
    2605              :         }
    2606              : 
    2607        32912 :       switch (base_event->get_kind ())
    2608              :         {
    2609            0 :         default:
    2610            0 :           gcc_unreachable ();
    2611              : 
    2612            0 :         case event_kind::debug:
    2613            0 :           if (m_verbosity < 4)
    2614              :             {
    2615            0 :               log ("filtering event %i: debug event", idx);
    2616            0 :               path->delete_event (idx);
    2617              :             }
    2618              :           break;
    2619              : 
    2620              :         case event_kind::custom:
    2621              :           /* Don't filter custom events.  */
    2622              :           break;
    2623              : 
    2624        12854 :         case event_kind::stmt:
    2625        12854 :           {
    2626        12854 :             if (m_verbosity < 4)
    2627              :               {
    2628        12854 :                 log ("filtering event %i: statement event", idx);
    2629        12854 :                 path->delete_event (idx);
    2630              :               }
    2631              :           }
    2632              :           break;
    2633              : 
    2634              :         case event_kind::region_creation:
    2635              :           /* Don't filter these.  */
    2636              :           break;
    2637              : 
    2638           44 :         case event_kind::state_transition:
    2639              :           /* Prune these if they have an empty description.  */
    2640           44 :           {
    2641           44 :             tree_dump_pretty_printer pp (nullptr);
    2642           44 :             base_event->print_desc (pp);
    2643           44 :             if (strlen (pp_formatted_text (&pp)) == 0)
    2644              :               {
    2645            0 :                 log (("filtering event %i:"
    2646              :                       " state_transition_event with empty description"),
    2647              :                      idx);
    2648            0 :                 path->delete_event (idx);
    2649              :               }
    2650           44 :           }
    2651           44 :           break;
    2652              : 
    2653         5703 :         case event_kind::function_entry:
    2654         5703 :           if (m_verbosity < 1)
    2655              :             {
    2656           33 :               log ("filtering event %i: function entry", idx);
    2657           33 :               path->delete_event (idx);
    2658              :             }
    2659              :           break;
    2660              : 
    2661         4483 :         case event_kind::state_change:
    2662         4483 :           {
    2663         4483 :             state_change_event *state_change = (state_change_event *)base_event;
    2664         4483 :             gcc_assert (state_change->m_dst_state.m_region_model);
    2665              : 
    2666         4483 :             if (canonicalized_sval
    2667         4483 :                 == sm_state_map::canonicalize_svalue (state_change->m_sval,
    2668              :                                                       ext_state))
    2669              :               {
    2670         2450 :                 if (state_change->m_origin)
    2671              :                   {
    2672            0 :                     if (get_logger ())
    2673              :                       {
    2674            0 :                         label_text sval_desc = uncanonicalized_sval->get_desc ();
    2675            0 :                         label_text origin_sval_desc
    2676            0 :                           = state_change->m_origin->get_desc ();
    2677            0 :                         log ("event %i:"
    2678              :                              " switching var of interest from %qs to %qs",
    2679              :                              idx, sval_desc.get (),
    2680              :                              origin_sval_desc.get ());
    2681            0 :                       }
    2682            0 :                     uncanonicalized_sval = state_change->m_origin;
    2683            0 :                     canonicalized_sval
    2684            0 :                       = sm_state_map::canonicalize_svalue (uncanonicalized_sval,
    2685              :                                                            ext_state);
    2686              : 
    2687              :                   }
    2688         2450 :                 log ("event %i: switching state of interest from %qs to %qs",
    2689         2450 :                      idx, state_change->m_to->get_name (),
    2690         2450 :                      state_change->m_from->get_name ());
    2691         2450 :                 state = state_change->m_from;
    2692              :               }
    2693         2033 :             else if (m_verbosity < 4)
    2694              :               {
    2695         2033 :                 if (get_logger ())
    2696              :                   {
    2697            0 :                     if (state_change->m_sval)
    2698              :                       {
    2699            0 :                         label_text change_sval_desc
    2700            0 :                           = state_change->m_sval->get_desc ();
    2701            0 :                         if (uncanonicalized_sval)
    2702              :                           {
    2703            0 :                             label_text sval_desc = uncanonicalized_sval->get_desc ();
    2704            0 :                             log ("filtering event %i:"
    2705              :                                  " state change to %qs unrelated to %qs",
    2706              :                                  idx, change_sval_desc.get (),
    2707              :                                  sval_desc.get ());
    2708            0 :                           }
    2709              :                         else
    2710            0 :                           log ("filtering event %i: state change to %qs",
    2711              :                                idx, change_sval_desc.get ());
    2712            0 :                       }
    2713              :                     else
    2714            0 :                       log ("filtering event %i: global state change", idx);
    2715              :                   }
    2716         2033 :                 path->delete_event (idx);
    2717              :               }
    2718              :           }
    2719              :           break;
    2720              : 
    2721         2599 :         case event_kind::start_cfg_edge:
    2722         2599 :           {
    2723         2599 :             cfg_edge_event *event = (cfg_edge_event *)base_event;
    2724              : 
    2725              :             /* TODO: is this edge significant to var?
    2726              :                See if var can be in other states in the dest, but not
    2727              :                in other states in the src?
    2728              :                Must have multiple sibling edges.  */
    2729              : 
    2730         2599 :             if (event->should_filter_p (m_verbosity))
    2731              :               {
    2732           35 :                 log ("filtering events %i and %i: CFG edge", idx, idx + 1);
    2733           35 :                 path->delete_event (idx);
    2734              :                 /* Also delete the corresponding event_kind::end_cfg_edge.  */
    2735           35 :                 gcc_assert (path->get_checker_event (idx)->get_kind ()
    2736              :                             == event_kind::end_cfg_edge);
    2737           35 :                 path->delete_event (idx);
    2738              :               }
    2739              :           }
    2740              :           break;
    2741              : 
    2742              :         case event_kind::end_cfg_edge:
    2743              :           /* These come in pairs with event_kind::start_cfg_edge events and are
    2744              :              filtered when their start event is filtered.  */
    2745              :           break;
    2746              : 
    2747              :         case event_kind::catch_:
    2748              :         case event_kind::throw_:
    2749              :         case event_kind::unwind:
    2750              :           /* Don't filter these.  */
    2751              :           break;
    2752              : 
    2753         1397 :         case event_kind::call_:
    2754         1397 :           {
    2755         1397 :             call_event *event = (call_event *)base_event;
    2756         1397 :             const region_model *callee_model
    2757         1397 :               = event->m_eedge.m_dest->get_state ().m_region_model;
    2758         1397 :             const region_model *caller_model
    2759         1397 :               = event->m_eedge.m_src->get_state ().m_region_model;
    2760         1397 :             tree callee_var
    2761         1397 :               = callee_model->get_representative_tree (uncanonicalized_sval);
    2762         1397 :             callsite_expr expr;
    2763              : 
    2764         1397 :             tree caller_var;
    2765         1397 :             if (auto op = event->get_call_and_return_op ())
    2766              :               {
    2767         1397 :                 tree callee_fndecl
    2768         1397 :                   = event->m_eedge.m_dest->get_point ().get_fndecl ();
    2769         1397 :                 caller_var
    2770         1397 :                   = op->map_expr_from_callee_to_caller (callee_fndecl,
    2771              :                                                         callee_var,
    2772              :                                                         &expr);
    2773              :               }
    2774              :             else
    2775            0 :               caller_var
    2776            0 :                 = caller_model->get_representative_tree (uncanonicalized_sval);
    2777              : 
    2778         1397 :             if (caller_var)
    2779              :               {
    2780          228 :                 if (get_logger ())
    2781              :                   {
    2782            0 :                     label_text sval_desc = uncanonicalized_sval->get_desc ();
    2783            0 :                     log ("event %i:"
    2784              :                          " recording critical state for %qs at call"
    2785              :                          " from %qE in callee to %qE in caller",
    2786              :                          idx, sval_desc.get (), callee_var, caller_var);
    2787            0 :                   }
    2788          228 :                 if (expr.param_p ())
    2789          228 :                   event->record_critical_state (caller_var, state);
    2790              :               }
    2791              :           }
    2792         1397 :           break;
    2793              : 
    2794          818 :         case event_kind::return_:
    2795          818 :           {
    2796          818 :             if (uncanonicalized_sval)
    2797              :               {
    2798          628 :                 return_event *event = (return_event *)base_event;
    2799          628 :                 const region_model *caller_model
    2800          628 :                   = event->m_eedge.m_dest->get_state ().m_region_model;
    2801          628 :                 tree caller_var
    2802          628 :                   = caller_model->get_representative_tree (uncanonicalized_sval);
    2803          628 :                 const region_model *callee_model
    2804          628 :                   = event->m_eedge.m_src->get_state ().m_region_model;
    2805          628 :                 callsite_expr expr;
    2806              : 
    2807          628 :                 tree callee_var;
    2808              : 
    2809          628 :                 if (auto op = event->get_call_and_return_op ())
    2810              :                   {
    2811          628 :                     tree callee_fndecl
    2812          628 :                       = event->m_eedge.m_src->get_point ().get_fndecl ();
    2813          628 :                     callee_var
    2814          628 :                       = op->map_expr_from_caller_to_callee (callee_fndecl,
    2815              :                                                             caller_var,
    2816              :                                                             &expr);
    2817              :                   }
    2818              :                 else
    2819            0 :                   callee_var
    2820            0 :                     = callee_model->get_representative_tree (uncanonicalized_sval);
    2821              : 
    2822          628 :                 if (callee_var)
    2823              :                   {
    2824          157 :                     if (get_logger ())
    2825              :                       {
    2826            0 :                         label_text sval_desc
    2827            0 :                           = uncanonicalized_sval->get_desc ();
    2828            0 :                         log ("event %i:"
    2829              :                              " recording critical state for %qs at return"
    2830              :                              " from %qE in caller to %qE in callee",
    2831              :                              idx, sval_desc.get (), callee_var, callee_var);
    2832            0 :                       }
    2833          157 :                     if (expr.return_value_p ())
    2834           70 :                       event->record_critical_state (callee_var, state);
    2835              :                   }
    2836              :               }
    2837              :           }
    2838              :           break;
    2839              : 
    2840              :         case event_kind::inlined_call:
    2841              :           /* We don't expect to see these yet, as they're added later.
    2842              :              We'd want to keep them around.  */
    2843              :           break;
    2844              : 
    2845              :         case event_kind::setjmp_:
    2846              :           /* TODO: only show setjmp_events that matter i.e. those for which
    2847              :              there is a later rewind event using them.  */
    2848              :         case event_kind::rewind_from_longjmp:
    2849              :         case event_kind::rewind_to_setjmp:
    2850              :           break;
    2851              : 
    2852              :         case event_kind::warning:
    2853              :           /* Always show the final "warning" event in the path.  */
    2854              :           break;
    2855              :         }
    2856        32912 :       idx--;
    2857              :     }
    2858         4386 : }
    2859              : 
    2860              : /* Subroutine of diagnostic_manager::prune_for_sm_diagnostic.
    2861              :    If *EXPR is not suitable to be the expression of interest in
    2862              :    an sm-diagnostic, set *EXPR to NULL and log.  */
    2863              : 
    2864              : void
    2865            0 : diagnostic_manager::update_for_unsuitable_sm_exprs (tree *expr) const
    2866              : {
    2867            0 :   gcc_assert (expr);
    2868            0 :   if (*expr && !can_be_expr_of_interest_p (*expr))
    2869              :     {
    2870            0 :       log ("new var %qE is unsuitable; setting var to NULL", *expr);
    2871            0 :       *expr = NULL_TREE;
    2872              :     }
    2873            0 : }
    2874              : 
    2875              : /* Second pass of diagnostic_manager::prune_path: remove redundant
    2876              :    interprocedural information.
    2877              : 
    2878              :    For example, given:
    2879              :      (1)- calling "f2" from "f1"
    2880              :      (2)--- entry to "f2"
    2881              :      (3)--- calling "f3" from "f2"
    2882              :      (4)----- entry to "f3"
    2883              :      (5)--- returning to "f2" to "f3"
    2884              :      (6)- returning to "f1" to "f2"
    2885              :    with no other intervening events, then none of these events are
    2886              :    likely to be interesting to the user.
    2887              : 
    2888              :    Prune [..., call, function-entry, return, ...] triples repeatedly
    2889              :    until nothing has changed.  For the example above, this would
    2890              :    remove events (3, 4, 5), and then remove events (1, 2, 6).  */
    2891              : 
    2892              : void
    2893         4386 : diagnostic_manager::prune_interproc_events (checker_path *path) const
    2894              : {
    2895         4386 :   bool changed = false;
    2896         4632 :   do
    2897              :     {
    2898         4632 :       changed = false;
    2899         4632 :       int idx = (signed)path->num_events () - 1;
    2900        23896 :       while (idx >= 0)
    2901              :         {
    2902              :           /* Prune [..., call, function-entry, return, ...] triples.  */
    2903        19264 :           if (idx + 2 < (signed)path->num_events ()
    2904        10290 :               && path->get_checker_event (idx)->is_call_p ()
    2905         1104 :               && path->get_checker_event (idx + 1)->is_function_entry_p ()
    2906        20360 :               && path->get_checker_event (idx + 2)->is_return_p ())
    2907              :             {
    2908          533 :               if (get_logger ())
    2909              :                 {
    2910            0 :                   label_text desc
    2911            0 :                     (path->get_checker_event (idx)->get_desc
    2912            0 :                        (*global_dc->get_reference_printer ()));
    2913            0 :                   log ("filtering events %i-%i:"
    2914              :                        " irrelevant call/entry/return: %s",
    2915              :                        idx, idx + 2, desc.get ());
    2916            0 :                 }
    2917          533 :               path->delete_event (idx + 2);
    2918          533 :               path->delete_event (idx + 1);
    2919          533 :               path->delete_event (idx);
    2920          533 :               changed = true;
    2921          533 :               idx--;
    2922          533 :               continue;
    2923          533 :             }
    2924              : 
    2925              :           /* Prune [..., call, return, ...] pairs
    2926              :              (for -fanalyzer-verbosity=0).  */
    2927        18731 :           if (idx + 1 < (signed)path->num_events ()
    2928        13965 :               && path->get_checker_event (idx)->is_call_p ()
    2929        19669 :               && path->get_checker_event (idx + 1)->is_return_p ())
    2930              :             {
    2931            4 :               if (get_logger ())
    2932              :                 {
    2933            0 :                   label_text desc
    2934            0 :                     (path->get_checker_event (idx)->get_desc
    2935            0 :                      (*global_dc->get_reference_printer ()));
    2936            0 :                   log ("filtering events %i-%i:"
    2937              :                        " irrelevant call/return: %s",
    2938              :                        idx, idx + 1, desc.get ());
    2939            0 :                 }
    2940            4 :               path->delete_event (idx + 1);
    2941            4 :               path->delete_event (idx);
    2942            4 :               changed = true;
    2943            4 :               idx--;
    2944            4 :               continue;
    2945            4 :             }
    2946              : 
    2947        18727 :           idx--;
    2948              :         }
    2949              : 
    2950              :     }
    2951              :   while (changed);
    2952         4386 : }
    2953              : 
    2954              : /* Remove everything within [call point, IDX]. For consistency,
    2955              :    IDX should represent the return event of the frame to delete,
    2956              :    or if there is none it should be the last event of the frame.
    2957              :    After this function, IDX designates the event prior to calling
    2958              :    this frame.  */
    2959              : 
    2960              : static void
    2961            0 : prune_frame (checker_path *path, int &idx)
    2962              : {
    2963            0 :   gcc_assert (idx >= 0);
    2964            0 :   int nesting = 1;
    2965            0 :   if (path->get_checker_event (idx)->is_return_p ())
    2966            0 :     nesting = 0;
    2967            0 :   do
    2968              :     {
    2969            0 :       if (path->get_checker_event (idx)->is_call_p ())
    2970            0 :         nesting--;
    2971            0 :       else if (path->get_checker_event (idx)->is_return_p ())
    2972            0 :         nesting++;
    2973              : 
    2974            0 :       path->delete_event (idx--);
    2975            0 :     } while (idx >= 0 && nesting != 0);
    2976            0 : }
    2977              : 
    2978              : /* This function is called when fanalyzer-show-events-in-system-headers
    2979              :    is disabled and will prune the diagnostic of all events within a
    2980              :    system header, only keeping the entry and exit events to the header.
    2981              :    This should be called after diagnostic_manager::prune_interproc_events
    2982              :    so that successive events [system header call, system header return]
    2983              :    are preserved thereafter.
    2984              : 
    2985              :    Given a diagnostics path diving into a system header in the form
    2986              :    [
    2987              :      prefix events...,
    2988              :      system header call,
    2989              :        system header entry,
    2990              :        events within system headers...,
    2991              :      system header return,
    2992              :      suffix events...
    2993              :    ]
    2994              : 
    2995              :    then transforms it into
    2996              :    [
    2997              :      prefix events...,
    2998              :      system header call,
    2999              :      system header return,
    3000              :      suffix events...
    3001              :    ].  */
    3002              : 
    3003              : void
    3004         4384 : diagnostic_manager::prune_system_headers (checker_path *path) const
    3005              : {
    3006         4384 :   int idx = (signed)path->num_events () - 1;
    3007        20697 :   while (idx >= 0)
    3008              :     {
    3009        16313 :       const checker_event *event = path->get_checker_event (idx);
    3010              :       /* Prune everything between
    3011              :          [..., system entry, (...), system return, ...].  */
    3012        16313 :       if (event->is_return_p ()
    3013        16313 :           && in_system_header_at (event->get_location ()))
    3014              :       {
    3015            0 :         int ret_idx = idx;
    3016            0 :         prune_frame (path, idx);
    3017              : 
    3018            0 :         if (get_logger ())
    3019              :         {
    3020            0 :           log ("filtering system headers events %i-%i:",
    3021              :                idx, ret_idx);
    3022              :         }
    3023              :         // Delete function entry within system headers.
    3024            0 :         if (idx >= 0)
    3025              :           {
    3026            0 :             event = path->get_checker_event (idx);
    3027            0 :             if (event->is_function_entry_p ()
    3028            0 :                 && in_system_header_at (event->get_location ()))
    3029              :               {
    3030            0 :                 if (get_logger ())
    3031              :                   {
    3032            0 :                     label_text desc
    3033            0 :                       (event->get_desc (*global_dc->get_reference_printer ()));
    3034            0 :                     log ("filtering event %i:"
    3035              :                          "system header entry event: %s",
    3036              :                          idx, desc.get ());
    3037            0 :                   }
    3038              : 
    3039            0 :                 path->delete_event (idx);
    3040              :               }
    3041              :           }
    3042              :       }
    3043              : 
    3044        16313 :       idx--;
    3045              :     }
    3046         4384 : }
    3047              : 
    3048              : /* Return true iff event IDX within PATH is on the same line as REF_EXP_LOC.  */
    3049              : 
    3050              : static bool
    3051         2694 : same_line_as_p (const expanded_location &ref_exp_loc,
    3052              :                 checker_path *path, unsigned idx)
    3053              : {
    3054         2694 :   const checker_event *ev = path->get_checker_event (idx);
    3055         2694 :   expanded_location idx_exp_loc = expand_location (ev->get_location ());
    3056         2694 :   gcc_assert (ref_exp_loc.file);
    3057         2694 :   if (idx_exp_loc.file == nullptr)
    3058              :     return false;
    3059         2671 :   if (strcmp (ref_exp_loc.file, idx_exp_loc.file))
    3060              :     return false;
    3061         2667 :   return ref_exp_loc.line == idx_exp_loc.line;
    3062              : }
    3063              : 
    3064              : /* This path-readability optimization reduces the verbosity of compound
    3065              :    conditional statements (without needing to reconstruct the AST, which
    3066              :    has already been lost).
    3067              : 
    3068              :    For example, it converts:
    3069              : 
    3070              :     |   61 |   if (cp[0] != '\0' && cp[0] != '#')
    3071              :     |      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    3072              :     |      |      |              |    |
    3073              :     |      |      |              |    (6) ...to here
    3074              :     |      |      |              (7) following ‘true’ branch...
    3075              :     |      |      (5) following ‘true’ branch...
    3076              :     |   62 |     {
    3077              :     |   63 |       alias = cp++;
    3078              :     |      |               ~~~~
    3079              :     |      |                 |
    3080              :     |      |                 (8) ...to here
    3081              : 
    3082              :    into:
    3083              : 
    3084              :     |   61 |   if (cp[0] != '\0' && cp[0] != '#')
    3085              :     |      |      ~
    3086              :     |      |      |
    3087              :     |      |      (5) following ‘true’ branch...
    3088              :     |   62 |     {
    3089              :     |   63 |       alias = cp++;
    3090              :     |      |               ~~~~
    3091              :     |      |                 |
    3092              :     |      |                 (6) ...to here
    3093              : 
    3094              :    by combining events 5-8 into new events 5-6.
    3095              : 
    3096              :    Find runs of consecutive (start_cfg_edge_event, end_cfg_edge_event) pairs
    3097              :    in which all events apart from the final end_cfg_edge_event are on the same
    3098              :    line, and for which either all the CFG edges are TRUE edges, or all are
    3099              :    FALSE edges.
    3100              : 
    3101              :    Consolidate each such run into a
    3102              :      (start_consolidated_cfg_edges_event, end_consolidated_cfg_edges_event)
    3103              :    pair.  */
    3104              : 
    3105              : void
    3106         4386 : diagnostic_manager::consolidate_conditions (checker_path *path) const
    3107              : {
    3108              :   /* Don't simplify edges if we're debugging them.  */
    3109         4386 :   if (flag_analyzer_verbose_edges)
    3110              :     return;
    3111              : 
    3112        11852 :   for (int start_idx = 0;
    3113        32385 :        start_idx < (signed)path->num_events () - 1;
    3114              :        start_idx++)
    3115              :     {
    3116        11852 :       if (path->cfg_edge_pair_at_p (start_idx))
    3117              :         {
    3118         2480 :           const checker_event *old_start_ev
    3119         2480 :             = path->get_checker_event (start_idx);
    3120         2480 :           expanded_location start_exp_loc
    3121         2480 :             = expand_location (old_start_ev->get_location ());
    3122         2480 :           if (start_exp_loc.file == nullptr)
    3123         2150 :             continue;
    3124         2480 :           if (!same_line_as_p (start_exp_loc, path, start_idx + 1))
    3125         2150 :             continue;
    3126              : 
    3127              :           /* Are we looking for a run of all TRUE edges, or all FALSE edges?  */
    3128          330 :           gcc_assert (old_start_ev->get_kind () == event_kind::start_cfg_edge);
    3129          330 :           const start_cfg_edge_event *old_start_cfg_ev
    3130              :             = (const start_cfg_edge_event *)old_start_ev;
    3131          330 :           bool edge_sense;
    3132          330 :           if (!old_start_cfg_ev->maybe_get_edge_sense (&edge_sense))
    3133            0 :             continue;
    3134              : 
    3135              :           /* Find a run of CFG start/end event pairs from
    3136              :                [start_idx, next_idx)
    3137              :              where all apart from the final event are on the same line,
    3138              :              and all are either TRUE or FALSE edges, matching the initial.  */
    3139          330 :           int next_idx = start_idx + 2;
    3140          330 :           while (path->cfg_edge_pair_at_p (next_idx)
    3141          414 :                  && same_line_as_p (start_exp_loc, path, next_idx))
    3142              :             {
    3143          119 :               const checker_event *iter_ev
    3144          119 :                 = path->get_checker_event (next_idx);
    3145          119 :               gcc_assert (iter_ev->get_kind () == event_kind::start_cfg_edge);
    3146          119 :               const start_cfg_edge_event *iter_cfg_ev
    3147              :                 = (const start_cfg_edge_event *)iter_ev;
    3148          119 :               bool iter_edge_sense;
    3149          119 :               if (!iter_cfg_ev->maybe_get_edge_sense (&iter_edge_sense))
    3150              :                 break;
    3151          113 :               if (iter_edge_sense != edge_sense)
    3152              :                 break;
    3153           84 :               next_idx += 2;
    3154              :             }
    3155              : 
    3156              :           /* If we have more than one pair in the run, consolidate.  */
    3157          330 :           if (next_idx > start_idx + 2)
    3158              :             {
    3159           79 :               const checker_event *old_end_ev
    3160           79 :                 = path->get_checker_event (next_idx - 1);
    3161           79 :               log ("consolidating CFG edge events %i-%i into %i-%i",
    3162              :                    start_idx, next_idx - 1, start_idx, start_idx +1);
    3163           79 :               auto new_start_ev
    3164              :                 = std::make_unique<start_consolidated_cfg_edges_event>
    3165           79 :                     (event_loc_info (old_start_ev->get_location (),
    3166              :                                      old_start_ev->get_fndecl (),
    3167           79 :                                      old_start_ev->get_stack_depth ()),
    3168           79 :                  edge_sense);
    3169           79 :               auto new_end_ev
    3170              :                 = std::make_unique<end_consolidated_cfg_edges_event>
    3171           79 :                     (event_loc_info (old_end_ev->get_location (),
    3172              :                                      old_end_ev->get_fndecl (),
    3173           79 :                                      old_end_ev->get_stack_depth ()));
    3174           79 :               path->replace_event (start_idx, std::move (new_start_ev));
    3175           79 :               path->replace_event (start_idx + 1, std::move (new_end_ev));
    3176           79 :               path->delete_events (start_idx + 2, next_idx - (start_idx + 2));
    3177           79 :             }
    3178              :         }
    3179              :     }
    3180              : }
    3181              : 
    3182              : /* Consolidate runs of consecutive unwind_event.  */
    3183              : 
    3184              : void
    3185         4386 : diagnostic_manager::consolidate_unwind_events (checker_path *path) const
    3186              : {
    3187              :   /* Don't simplify edges if we're debugging them.  */
    3188         4386 :   if (flag_analyzer_verbose_edges)
    3189              :     return;
    3190              : 
    3191        11846 :   for (int start_idx = 0;
    3192        32373 :        start_idx < (signed)path->num_events () - 1;
    3193              :        start_idx++)
    3194              :     {
    3195              :       /* Find a run of consecutive unwind_event instances.  */
    3196        11846 :       if (path->get_checker_event (start_idx)->get_kind ()
    3197              :           != event_kind::unwind)
    3198        11837 :         continue;
    3199            9 :       int iter_idx = start_idx + 1;
    3200           15 :       while (iter_idx < (int)path->num_events ())
    3201           15 :         if (path->get_checker_event (iter_idx)->get_kind ()
    3202              :             == event_kind::unwind)
    3203            6 :           ++iter_idx;
    3204              :         else
    3205              :           break;
    3206              : 
    3207              :       /* iter_idx should now be one after the last unwind_event in the run.  */
    3208            9 :       const int last_idx = iter_idx - 1;
    3209            9 :       if (last_idx == start_idx)
    3210            3 :         continue;
    3211              : 
    3212            6 :       gcc_assert (last_idx > start_idx);
    3213              : 
    3214            6 :       log ("consolidating unwind events %i-%i into %i",
    3215              :            start_idx, last_idx, start_idx);
    3216              : 
    3217            6 :       unwind_event *first_event
    3218            6 :         = (unwind_event *)path->get_checker_event (start_idx);
    3219            6 :       const unwind_event *last_event
    3220            6 :         = (const unwind_event *)path->get_checker_event (last_idx);
    3221            6 :       first_event->m_num_frames += last_event->m_num_frames;
    3222            6 :       path->delete_events (start_idx + 1, last_idx - start_idx);
    3223              :     }
    3224              : }
    3225              : 
    3226              : /* Final pass of diagnostic_manager::prune_path.
    3227              : 
    3228              :    If all we're left with is in one function, then filter function entry
    3229              :    events.  */
    3230              : 
    3231              : void
    3232         4386 : diagnostic_manager::finish_pruning (checker_path *path) const
    3233              : {
    3234         4386 :   if (!path->interprocedural_p ())
    3235              :     {
    3236         3599 :       int idx = path->num_events () - 1;
    3237        26403 :       while (idx >= 0 && idx < (signed)path->num_events ())
    3238              :         {
    3239        11402 :           checker_event *base_event = path->get_checker_event (idx);
    3240        11402 :           if (base_event->get_kind () == event_kind::function_entry)
    3241              :             {
    3242         3503 :               log ("filtering event %i:"
    3243              :                    " function entry for purely intraprocedural path", idx);
    3244         3503 :               path->delete_event (idx);
    3245              :             }
    3246        11402 :           idx--;
    3247              :         }
    3248              :     }
    3249         4386 : }
    3250              : 
    3251              : } // namespace ana
    3252              : 
    3253              : #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.