gcc/analyzer/trimmed-graph.cc

   1 /* Trimming an exploded graph to a subset of nodes and edges.
   2    Copyright (C) 2021 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 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tree.h"
  25 #include "pretty-print.h"
  26 #include "gcc-rich-location.h"
  27 #include "gimple-pretty-print.h"
  28 #include "function.h"
  29 #include "diagnostic-core.h"
  30 #include "diagnostic-event-id.h"
  31 #include "diagnostic-path.h"
  32 #include "alloc-pool.h"
  33 #include "fibonacci_heap.h"
  34 #include "shortest-paths.h"
  35 #include "sbitmap.h"
  36 #include "bitmap.h"
  37 #include "tristate.h"
  38 #include "selftest.h"
  39 #include "ordered-hash-map.h"
  40 #include "json.h"
  41 #include "analyzer/analyzer.h"
  42 #include "analyzer/analyzer-logging.h"
  43 #include "analyzer/sm.h"
  44 #include "analyzer/pending-diagnostic.h"
  45 #include "analyzer/diagnostic-manager.h"
  46 #include "analyzer/call-string.h"
  47 #include "analyzer/program-point.h"
  48 #include "analyzer/store.h"
  49 #include "analyzer/region-model.h"
  50 #include "analyzer/constraint-manager.h"
  51 #include "cfg.h"
  52 #include "basic-block.h"
  53 #include "gimple.h"
  54 #include "gimple-iterator.h"
  55 #include "cgraph.h"
  56 #include "digraph.h"
  57 #include "analyzer/supergraph.h"
  58 #include "analyzer/program-state.h"
  59 #include "analyzer/exploded-graph.h"
  60 #include "analyzer/trimmed-graph.h"
  61
  62 #if ENABLE_ANALYZER
  63
  64 namespace ana {
  65
  66 /* class trimmed_node : public dnode<tg_traits>.  */
  67
  68 /* Implementation of dump_dot vfunc, delegating to the inner node.  */
  69
  70 void
  71 trimmed_node::dump_dot (graphviz_out *gv,
  72                         const dump_args_t &args) const
  73 {
  74   m_inner_node->dump_dot (gv, args.m_inner_args);
  75 }
  76
  77 /* class trimmed_edge : public dedge<tg_traits>.  */
  78
  79 /* trimmed_edge's ctor.  */
  80
  81 trimmed_edge::trimmed_edge (trimmed_node *src, trimmed_node *dest,
  82                             const exploded_edge *inner_edge)
  83 : dedge<tg_traits> (src, dest), m_inner_edge (inner_edge)
  84 {
  85 }
  86
  87 /* Implementation of dump_dot vfunc, delegating to the inner edge.  */
  88
  89 void
  90 trimmed_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const
  91 {
  92   m_inner_edge->dump_dot (gv, args.m_inner_args);
  93 }
  94
  95 /* class trimmed_graph : public digraph <tg_traits>.  */
  96
  97 /* Ctor for trimmed_graph: construct a graph equivalent to trimming
  98    INNER_GRAPH to all nodes that can reach INNER_DST_NODE.  */
  99
 100 trimmed_graph::trimmed_graph (const exploded_graph &inner_graph,
 101                               const exploded_node *inner_dst_node)
 102 : m_enodes (), m_eedges ()
 103 {
 104   /* Determine what subset of nodes and edges to include in the
 105      trimmed graph.
 106      Walk backwards from INNER_DST_NODE, finding nodes that reach it,
 107      iteratively building the set of nodes and edges.  */
 108   auto_vec <const exploded_node *> worklist;
 109   worklist.safe_push (inner_dst_node);
 110   m_enodes.add (inner_dst_node);
 111   while (worklist.length () > 0)
 112     {
 113       const exploded_node *inner_node = worklist.pop ();
 114       exploded_edge *inner_pred;
 115       unsigned i;
 116       FOR_EACH_VEC_ELT (inner_node->m_preds, i, inner_pred)
 117         {
 118           if (!m_enodes.contains (inner_pred->m_src))
 119             {
 120               worklist.safe_push (inner_pred->m_src);
 121               m_enodes.add (inner_pred->m_src);
 122             }
 123           m_eedges.add (inner_pred);
 124         }
 125     }
 126
 127   /* Create trimmed nodes for all enodes in the set.  */
 128   {
 129     /* Iterate over the vec rather than the hash_set
 130        to ensure deterministic order.  */
 131     exploded_node *inner_node;
 132     unsigned i;
 133     FOR_EACH_VEC_ELT (inner_graph.m_nodes, i, inner_node)
 134       if (m_enodes.contains (inner_node))
 135         {
 136           trimmed_node *tnode = new trimmed_node (inner_node);
 137           add_node (tnode);
 138           m_map_from_enode_to_tnode.put (inner_node, tnode);
 139         }
 140   }
 141
 142   /* Create trimmed edges for all edges in the set.  */
 143   {
 144     /* Iterate over the vec rather than the hash_set
 145        to ensure deterministic order.  */
 146     exploded_edge *inner_edge;
 147     unsigned i;
 148     FOR_EACH_VEC_ELT (inner_graph.m_edges, i, inner_edge)
 149       if (m_eedges.contains (inner_edge))
 150         {
 151           const exploded_node *inner_src = inner_edge->m_src;
 152           const exploded_node *inner_dest = inner_edge->m_dest;
 153           trimmed_node *tsrc = *m_map_from_enode_to_tnode.get (inner_src);
 154           trimmed_node *tdest = *m_map_from_enode_to_tnode.get (inner_dest);
 155           trimmed_edge *tedge = new trimmed_edge (tsrc, tdest, inner_edge);
 156           add_edge (tedge);
 157         }
 158   }
 159 }
 160
 161 /* Dump stats about this graph to LOGGER.  */
 162
 163 void
 164 trimmed_graph::log_stats (logger *logger) const
 165 {
 166   logger->log ("#nodes: %i", m_nodes.length ());
 167   logger->log ("#edges: %i", m_edges.length ());
 168 }
 169
 170 } // namespace ana
 171
 172 #endif /* #if ENABLE_ANALYZER */