1 /* Trimming an exploded graph to a subset of nodes and edges. 2 Copyright (C) 2021-2022 Free Software Foundation, Inc. 3 Contributed by David Malcolm <dmalcolm (at) 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 */ 173
Indexes created Sat Feb 28 05:31:39 UTC 2026