LCOV - code coverage report
Current view: top level - gcc/analyzer - diagnostic-manager.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 85.3 % 1242 1060
Test Date: 2024-03-23 14:05:01 Functions: 86.6 % 82 71
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

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

Generated by: LCOV version 2.0-1

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.