diff options
Diffstat (limited to 'gcc/analyzer')
| -rw-r--r-- | gcc/analyzer/ChangeLog | 29 | ||||
| -rw-r--r-- | gcc/analyzer/checker-path.cc | 2 | ||||
| -rw-r--r-- | gcc/analyzer/diagnostic-manager.cc | 144 | ||||
| -rw-r--r-- | gcc/analyzer/diagnostic-manager.h | 14 | ||||
| -rw-r--r-- | gcc/analyzer/reachability.h | 76 |
5 files changed, 246 insertions, 19 deletions
diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog index d7db6ab..bc70e88 100644 --- a/gcc/analyzer/ChangeLog +++ b/gcc/analyzer/ChangeLog @@ -1,3 +1,32 @@ +2020-02-24 David Malcolm <dmalcolm@redhat.com> + + * checker-path.cc (superedge_event::should_filter_p): Update + filter for empty descriptions to cover verbosity level 3 as well + as 2. + * diagnostic-manager.cc: Include "analyzer/reachability.h". + (class path_builder): New class. + (diagnostic_manager::emit_saved_diagnostic): Create a path_builder + and pass it to build_emission_path, rather passing eg; similarly + for add_events_for_eedge and ext_state. + (diagnostic_manager::build_emission_path): Replace "eg" param + with a path_builder, pass it to add_events_for_eedge. + (diagnostic_manager::add_events_for_eedge): Replace ext_state + param with path_builder; pass it to add_events_for_superedge. + (diagnostic_manager::significant_edge_p): New. + (diagnostic_manager::add_events_for_superedge): Add path_builder + param. Reject insignificant edges at verbosity levels below 3. + (diagnostic_manager::prune_for_sm_diagnostic): Update highest + verbosity level to 4. + * diagnostic-manager.h (class path_builder): New forward decl. + (diagnostic_manager::build_emission_path): Replace "eg" param + with a path_builder. + (diagnostic_manager::add_events_for_eedge): Replace ext_state + param with path_builder. + (diagnostic_manager::significant_edge_p): New. + (diagnostic_manager::add_events_for_superedge): Add path_builder + param. + * reachability.h: New file. + 2020-02-18 David Malcolm <dmalcolm@redhat.com> PR analyzer/93692 diff --git a/gcc/analyzer/checker-path.cc b/gcc/analyzer/checker-path.cc index 7f6cdf5..c781cd8 100644 --- a/gcc/analyzer/checker-path.cc +++ b/gcc/analyzer/checker-path.cc @@ -334,7 +334,7 @@ superedge_event::should_filter_p (int verbosity) const if (verbosity < 2) return true; - if (verbosity == 2) + if (verbosity < 4) { /* Filter events with empty descriptions. This ought to filter FALLTHRU, but retain true/false/switch edges. */ diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index 5801525..78c5890 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -55,6 +55,7 @@ along with GCC; see the file COPYING3. If not see #include "analyzer/program-state.h" #include "analyzer/exploded-graph.h" #include "analyzer/checker-path.h" +#include "analyzer/reachability.h" #if ENABLE_ANALYZER @@ -107,6 +108,41 @@ saved_diagnostic::operator== (const saved_diagnostic &other) const && m_trailing_eedge == other.m_trailing_eedge); } +/* State for building a checker_path from a particular exploded_path. + In particular, this precomputes reachability information: the set of + source enodes for which a a path be found to the diagnostic enode. */ + +class path_builder +{ +public: + path_builder (const exploded_graph &eg, + const exploded_path &epath) + : m_eg (eg), + m_diag_enode (epath.get_final_enode ()), + m_reachability (eg, m_diag_enode) + {} + + const exploded_node *get_diag_node () const { return m_diag_enode; } + + bool reachable_from_p (const exploded_node *src_enode) const + { + return m_reachability.reachable_from_p (src_enode); + } + + const extrinsic_state &get_ext_state () const { return m_eg.get_ext_state (); } + +private: + typedef reachability<eg_traits> enode_reachability; + + const exploded_graph &m_eg; + + /* The enode where the diagnostic occurs. */ + const exploded_node *m_diag_enode; + + /* Precompute all enodes from which the diagnostic is reachable. */ + enode_reachability m_reachability; +}; + /* class diagnostic_manager. */ /* diagnostic_manager's ctor. */ @@ -470,10 +506,15 @@ diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg, pretty_printer *pp = global_dc->printer->clone (); + /* Precompute all enodes from which the diagnostic is reachable. */ + path_builder pb (eg, epath); + + /* This is the diagnostic_path subclass that will be built for + the diagnostic. */ checker_path emission_path; /* Populate emission_path with a full description of EPATH. */ - build_emission_path (eg, epath, &emission_path); + build_emission_path (pb, epath, &emission_path); /* Now prune it to just cover the most pertinent events. */ prune_path (&emission_path, sd.m_sm, sd.m_var, sd.m_state); @@ -489,8 +530,7 @@ diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg, trailing eedge stashed, add any events for it. This is for use in handling longjmp, to show where a longjmp is rewinding to. */ if (sd.m_trailing_eedge) - add_events_for_eedge (*sd.m_trailing_eedge, eg.get_ext_state (), - &emission_path); + add_events_for_eedge (pb, *sd.m_trailing_eedge, &emission_path); emission_path.prepare_for_emission (sd.m_d); @@ -558,16 +598,15 @@ get_any_origin (const gimple *stmt, EPATH within EG. */ void -diagnostic_manager::build_emission_path (const exploded_graph &eg, +diagnostic_manager::build_emission_path (const path_builder &pb, const exploded_path &epath, checker_path *emission_path) const { LOG_SCOPE (get_logger ()); - const extrinsic_state &ext_state = eg.get_ext_state (); for (unsigned i = 0; i < epath.m_edges.length (); i++) { const exploded_edge *eedge = epath.m_edges[i]; - add_events_for_eedge (*eedge, ext_state, emission_path); + add_events_for_eedge (pb, *eedge, emission_path); } } @@ -746,8 +785,8 @@ for_each_state_change (const program_state &src_state, Add any events for EEDGE to EMISSION_PATH. */ void -diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge, - const extrinsic_state &ext_state, +diagnostic_manager::add_events_for_eedge (const path_builder &pb, + const exploded_edge &eedge, checker_path *emission_path) const { const exploded_node *src_node = eedge.m_src; @@ -786,7 +825,7 @@ diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge, | | | (3) ...to here (end_cfg_edge_event). */ state_change_event_creator visitor (eedge, emission_path); - for_each_state_change (src_state, dst_state, ext_state, + for_each_state_change (src_state, dst_state, pb.get_ext_state (), &visitor); /* Allow non-standard edges to add events, e.g. when rewinding from @@ -803,7 +842,7 @@ diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge, if (src_point.get_kind () == PK_AFTER_SUPERNODE) { if (eedge.m_sedge) - add_events_for_superedge (eedge, emission_path); + add_events_for_superedge (pb, eedge, emission_path); } /* Add function entry events. */ if (dst_point.get_supernode ()->entry_p ()) @@ -836,18 +875,95 @@ diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge, } } +/* Return true if EEDGE is a significant edge in the path to the diagnostic + for PB. + + Consider all of the sibling out-eedges from the same source enode + as EEDGE. + If there's no path from the destinations of those eedges to the + diagnostic enode, then we have to take this eedge and thus it's + significant. + + Conversely if there is a path from the destination of any other sibling + eedge to the diagnostic enode, then this edge is insignificant. + + Example 1: redundant if-else: + + (A) if (...) A + (B) ... / \ + else B C + (C) ... \ / + (D) [DIAGNOSTIC] D + + D is reachable by either B or C, so neither of these edges + are significant. + + Example 2: pertinent if-else: + + (A) if (...) A + (B) ... / \ + else B C + (C) [NECESSARY CONDITION] | | + (D) [POSSIBLE DIAGNOSTIC] D1 D2 + + D becomes D1 and D2 in the exploded graph, where the diagnostic occurs + at D2. D2 is only reachable via C, so the A -> C edge is significant. + + Example 3: redundant loop: + + (A) while (...) +-->A + (B) ... | / \ + (C) ... +-B C + (D) [DIAGNOSTIC] | + D + + D is reachable from both B and C, so the A->C edge is not significant. */ + +bool +diagnostic_manager::significant_edge_p (const path_builder &pb, + const exploded_edge &eedge) const +{ + int i; + exploded_edge *sibling; + FOR_EACH_VEC_ELT (eedge.m_src->m_succs, i, sibling) + { + if (sibling == &eedge) + continue; + if (pb.reachable_from_p (sibling->m_dest)) + { + if (get_logger ()) + get_logger ()->log (" edge EN: %i -> EN: %i is insignificant as" + " EN: %i is also reachable via" + " EN: %i -> EN: %i", + eedge.m_src->m_index, eedge.m_dest->m_index, + pb.get_diag_node ()->m_index, + sibling->m_src->m_index, + sibling->m_dest->m_index); + return false; + } + } + + return true; +} + /* Subroutine of diagnostic_manager::add_events_for_eedge where EEDGE has an underlying superedge i.e. a CFG edge, or an interprocedural call/return. Add any events for the superedge to EMISSION_PATH. */ void -diagnostic_manager::add_events_for_superedge (const exploded_edge &eedge, +diagnostic_manager::add_events_for_superedge (const path_builder &pb, + const exploded_edge &eedge, checker_path *emission_path) const { gcc_assert (eedge.m_sedge); + /* Don't add events for insignificant edges at verbosity levels below 3. */ + if (m_verbosity < 3) + if (!significant_edge_p (pb, eedge)) + return; + const exploded_node *src_node = eedge.m_src; const program_point &src_point = src_node->get_point (); const exploded_node *dst_node = eedge.m_dest; @@ -995,7 +1111,7 @@ diagnostic_manager::prune_for_sm_diagnostic (checker_path *path, gcc_unreachable (); case EK_DEBUG: - if (m_verbosity < 3) + if (m_verbosity < 4) { log ("filtering event %i: debug event", idx); path->delete_event (idx); @@ -1021,7 +1137,7 @@ diagnostic_manager::prune_for_sm_diagnostic (checker_path *path, var = new_var; } } - if (m_verbosity < 3) + if (m_verbosity < 4) { log ("filtering event %i: statement event", idx); path->delete_event (idx); @@ -1054,7 +1170,7 @@ diagnostic_manager::prune_for_sm_diagnostic (checker_path *path, sm->get_state_name (state_change->m_from)); state = state_change->m_from; } - else if (m_verbosity < 3) + else if (m_verbosity < 4) { if (var) log ("filtering event %i:" diff --git a/gcc/analyzer/diagnostic-manager.h b/gcc/analyzer/diagnostic-manager.h index 171d279..f32ca75 100644 --- a/gcc/analyzer/diagnostic-manager.h +++ b/gcc/analyzer/diagnostic-manager.h @@ -53,6 +53,8 @@ private: DISABLE_COPY_AND_ASSIGN (saved_diagnostic); }; +class path_builder; + /* A class with responsibility for saving pending diagnostics, so that they can be emitted after the exploded_graph is complete. This lets us de-duplicate diagnostics, and find the shortest path @@ -101,15 +103,19 @@ public: } private: - void build_emission_path (const exploded_graph &eg, + void build_emission_path (const path_builder &pb, const exploded_path &epath, checker_path *emission_path) const; - void add_events_for_eedge (const exploded_edge &eedge, - const extrinsic_state &ext_state, + void add_events_for_eedge (const path_builder &pb, + const exploded_edge &eedge, checker_path *emission_path) const; - void add_events_for_superedge (const exploded_edge &eedge, + bool significant_edge_p (const path_builder &pb, + const exploded_edge &eedge) const; + + void add_events_for_superedge (const path_builder &pb, + const exploded_edge &eedge, checker_path *emission_path) const; void prune_path (checker_path *path, diff --git a/gcc/analyzer/reachability.h b/gcc/analyzer/reachability.h new file mode 100644 index 0000000..445cc7d --- /dev/null +++ b/gcc/analyzer/reachability.h @@ -0,0 +1,76 @@ +/* Digraph reachability. + Copyright (C) 2020 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_ANALYZER_REACHABILITY_H +#define GCC_ANALYZER_REACHABILITY_H + +namespace ana { + +/* The set of nodes from which a target node in a digraph can be reached. */ +// TODO(stage1): move to gcc + +template <typename GraphTraits> +class reachability +{ +public: + typedef typename GraphTraits::graph_t graph_t; + typedef typename GraphTraits::node_t node_t; + typedef typename GraphTraits::edge_t edge_t; + + reachability (const graph_t &graph, + const node_t *target_node) + : m_indices (graph.m_nodes.length ()) + { + bitmap_clear (m_indices); + auto_vec<const node_t *> worklist; + worklist.safe_push (target_node); + bitmap_set_bit (m_indices, target_node->m_index); + + while (worklist.length () > 0) + { + const node_t *next = worklist.pop (); + unsigned i; + edge_t *pred; + FOR_EACH_VEC_ELT (next->m_preds, i, pred) + { + if (!reachable_from_p (pred->m_src)) + { + worklist.safe_push (pred->m_src); + bitmap_set_bit (m_indices, pred->m_src->m_index); + } + } + } + } + + bool reachable_from_p (const node_t *src_node) const + { + return bitmap_bit_p (m_indices, src_node->m_index); + } + +private: + /* The nodes that can reach the target. */ + auto_sbitmap m_indices; +}; + +//TODO: selftests for reachability + +} // namespace ana + +#endif /* GCC_ANALYZER_REACHABILITY_H */ |