* [committed] analyzer: new implementation of shortest feasible path [PR96374]
@ 2021-03-11 23:06 David Malcolm
0 siblings, 0 replies; only message in thread
From: David Malcolm @ 2021-03-11 23:06 UTC (permalink / raw)
To: gcc-patches
The analyzer builds an exploded graph of (point,state) pairs and when
it finds a problem, records a diagnostic at the relevant exploded node.
Once it has finished exploring the graph, the analyzer needs to generate
the shortest feasible path through the graph to each diagnostic's node.
This is used:
- for rejecting diagnostics that are infeasible (due to impossible sets
of constraints),
- for use in determining which diagnostic to use in each deduplication
set (the one with the shortest path), and
- for building checker_paths for the "winning" diagnostics, giving a
list of events
Prior to this patch the analyzer simply found the shortest path to the
node, and then checked it for feasibility, which could lead to falsely
rejecting diagnostics: "the shortest path, if feasible" is not the same
as "the shortest feasible path" (PR analyzer/96374).
An example is PR analyzer/93355, where this issue causes the analyzer
to fail to emit a leak warning for a missing fclose on an error-handling
path in intl/localealias.c.
This patch implements a new algorithm for finding the shortest feasible
path to an exploded node: instead of simply finding the shortest path,
the new algorithm uses a worklist to iteratively build a tree of path
prefixes, which are feasible paths by construction, until a path to the
target node is found. The worklist is prioritized, so that the first
feasible path discovered is the shortest possible feasible path. The
algorithm continues trying paths until the target node is reached or a
limit is exceeded, in which case the diagnostic is treated as being
infeasible (which could still be a false negative, but is much less
likely to happen than before). Iteratively building a tree of paths
allows for work to be reused, and the tree can be dumped in .dot form
(via a new -fdump-analyzer-feasibility option), making it much easier to
debug compared to other approaches I tried.
Doing so fixes the missing leak warning for PR analyzer/93355 and
various other test cases.
Testing:
- I manually verified that the behavior is determistic using 50 builds
of pr93355-localealias.c. All dumps were identical.
- I manually verified that it still builds with --disable-analyzer.
- Lightly tested with valgrind; no additional issues.
- Lightly performance tested, showing a slight speed regression to the
analyzer relative to before the patch, but correctness for this issue
is more important than the slight performance hit for the analyzer.
Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
I also smoketested that it builds and runs on gcc211.fsffrance.org
(Solaris 11 on SPARC64 with gcc 5.5).
I'm taking some liberties by committing a patch this big at this point
in the GCC 11 cycle, but it fixes a large category of issues in
the analyzer, and the changes are confined to the analyzer; I've
verified that it builds with at least GCC 10 and GCC 5 to (I hope)
reduce the risk of breakage to anyone's build from the patch.
Pushed to trunk as r11-7640-g3857edb5d32dcdc11d9a2fe3ad7c156c52a1ec7f.
gcc/ChangeLog:
PR analyzer/96374
* Makefile.in (ANALYZER_OBJS): Add analyzer/feasible-graph.o and
analyzer/trimmed-graph.o.
* doc/analyzer.texi (Analyzer Paths): Rewrite description of
feasibility checking to reflect new implementation.
* doc/invoke.texi (-fdump-analyzer-feasibility): Document new
option.
* shortest-paths.h (shortest_paths::get_shortest_distance): New.
gcc/analyzer/ChangeLog:
PR analyzer/96374
* analyzer.opt (-param=analyzer-max-infeasible-edges=): New param.
(fdump-analyzer-feasibility): New flag.
* diagnostic-manager.cc: Include "analyzer/trimmed-graph.h" and
"analyzer/feasible-graph.h".
(epath_finder::epath_finder): Convert m_sep to a pointer and
only create it if !flag_analyzer_feasibility.
(epath_finder::~epath_finder): New.
(epath_finder::m_sep): Convert to a pointer.
(epath_finder::get_best_epath): Add param "diag_idx" and use it
when logging. Rather than finding the shortest path and then
checking feasibility, instead use explore_feasible_paths unless
!flag_analyzer_feasibility, in which case simply use the shortest
path, and note if it is infeasible. Update for m_sep becoming a
pointer.
(class feasible_worklist): New.
(epath_finder::explore_feasible_paths): New.
(epath_finder::process_worklist_item): New.
(class dump_eg_with_shortest_path): New.
(epath_finder::dump_trimmed_graph): New.
(epath_finder::dump_feasible_graph): New.
(saved_diagnostic::saved_diagnostic): Add "idx" param, using it
on new field m_idx.
(saved_diagnostic::to_json): Dump m_idx.
(saved_diagnostic::calc_best_epath): Pass m_idx to get_best_epath.
Remove assertion that m_problem was set when m_best_epath is NULL.
(diagnostic_manager::add_diagnostic): Pass an index when created
saved_diagnostic instances.
* diagnostic-manager.h (saved_diagnostic::saved_diagnostic): Add
"idx" param.
(saved_diagnostic::get_index): New accessor.
(saved_diagnostic::m_idx): New field.
* engine.cc (exploded_node::dump_dot): Call args.dump_extra_info.
Move code to...
(exploded_node::dump_processed_stmts): ...this new function and...
(exploded_node::dump_saved_diagnostics): ...this new function.
Add index of each diagnostic.
(exploded_edge::dump_dot): Move bulk of code to...
(exploded_edge::dump_dot_label): ...this new function.
* exploded-graph.h (eg_traits::dump_args_t::dump_extra_info): New
vfunc.
(exploded_node::dump_processed_stmts): New decl.
(exploded_node::dump_saved_diagnostics): New decl.
(exploded_edge::dump_dot_label): New decl.
* feasible-graph.cc: New file.
* feasible-graph.h: New file.
* trimmed-graph.cc: New file.
* trimmed-graph.h: New file.
gcc/testsuite/ChangeLog:
PR analyzer/96374
* gcc.dg/analyzer/dot-output.c: Add -fdump-analyzer-feasibility
to options.
* gcc.dg/analyzer/feasibility-1.c (test_6): Remove xfail.
(test_7): New.
* gcc.dg/analyzer/pr93355-localealias-feasibility-2.c: Remove xfail.
* gcc.dg/analyzer/pr93355-localealias-feasibility-3.c: Remove xfails.
* gcc.dg/analyzer/pr93355-localealias-feasibility.c: Remove
-fno-analyzer-feasibility from options.
* gcc.dg/analyzer/pr93355-localealias.c: Likewise.
* gcc.dg/analyzer/unknown-fns-4.c: Remove xfail.
---
gcc/Makefile.in | 4 +-
gcc/analyzer/analyzer.opt | 8 +
gcc/analyzer/diagnostic-manager.cc | 490 ++++++++++++++++--
gcc/analyzer/diagnostic-manager.h | 6 +-
gcc/analyzer/engine.cc | 99 ++--
gcc/analyzer/exploded-graph.h | 8 +
gcc/analyzer/feasible-graph.cc | 235 +++++++++
gcc/analyzer/feasible-graph.h | 213 ++++++++
gcc/analyzer/trimmed-graph.cc | 172 ++++++
gcc/analyzer/trimmed-graph.h | 122 +++++
gcc/doc/analyzer.texi | 56 +-
gcc/doc/invoke.texi | 8 +
gcc/shortest-paths.h | 13 +
gcc/testsuite/gcc.dg/analyzer/dot-output.c | 2 +-
gcc/testsuite/gcc.dg/analyzer/feasibility-1.c | 16 +-
.../pr93355-localealias-feasibility-2.c | 4 +-
.../pr93355-localealias-feasibility-3.c | 8 +-
.../pr93355-localealias-feasibility.c | 2 -
.../gcc.dg/analyzer/pr93355-localealias.c | 4 +-
gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c | 2 +-
20 files changed, 1366 insertions(+), 106 deletions(-)
create mode 100644 gcc/analyzer/feasible-graph.cc
create mode 100644 gcc/analyzer/feasible-graph.h
create mode 100644 gcc/analyzer/trimmed-graph.cc
create mode 100644 gcc/analyzer/trimmed-graph.h
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index a63c5d9cab6..8a5fb3fd99c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1254,6 +1254,7 @@ ANALYZER_OBJS = \
analyzer/constraint-manager.o \
analyzer/diagnostic-manager.o \
analyzer/engine.o \
+ analyzer/feasible-graph.o \
analyzer/function-set.o \
analyzer/pending-diagnostic.o \
analyzer/program-point.o \
@@ -1273,7 +1274,8 @@ ANALYZER_OBJS = \
analyzer/state-purge.o \
analyzer/store.o \
analyzer/supergraph.o \
- analyzer/svalue.o
+ analyzer/svalue.o \
+ analyzer/trimmed-graph.o
# Language-independent object files.
# We put the *-match.o and insn-*.o files first so that a parallel make
diff --git a/gcc/analyzer/analyzer.opt b/gcc/analyzer/analyzer.opt
index 089d71e5225..dd34495abd5 100644
--- a/gcc/analyzer/analyzer.opt
+++ b/gcc/analyzer/analyzer.opt
@@ -34,6 +34,10 @@ The maximum number of exploded nodes per program point within the analyzer, befo
Common Joined UInteger Var(param_analyzer_max_constraints) Init(20) Param
The maximum number of constraints per state.
+-param=analyzer-max-infeasible-edges=
+Common Joined UInteger Var(param_analyzer_max_infeasible_edges) Init(10) Param
+The maximum number of infeasible edges to reject before declaring a diagnostic as infeasible.
+
-param=analyzer-max-recursion-depth=
Common Joined UInteger Var(param_analyzer_max_recursion_depth) Init(2) Param
The maximum number of times a callsite can appear in a call stack within the analyzer, before terminating analysis of a call that would recurse deeper.
@@ -206,6 +210,10 @@ fdump-analyzer-exploded-nodes-3
Common RejectNegative Var(flag_dump_analyzer_exploded_nodes_3)
Dump a textual representation of the exploded graph to SRCFILE.eg-ID.txt.
+fdump-analyzer-feasibility
+Common RejectNegative Var(flag_dump_analyzer_feasibility)
+Dump various analyzer internals to SRCFILE.*.fg.dot and SRCFILE.*.tg.dot.
+
fdump-analyzer-json
Common RejectNegative Var(flag_dump_analyzer_json)
Dump analyzer-specific data to a SRCFILE.analyzer.json.gz file.
diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index e84953e82ee..1a3535cfeb1 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -57,6 +57,8 @@ along with GCC; see the file COPYING3. If not see
#include "analyzer/supergraph.h"
#include "analyzer/program-state.h"
#include "analyzer/exploded-graph.h"
+#include "analyzer/trimmed-graph.h"
+#include "analyzer/feasible-graph.h"
#include "analyzer/checker-path.h"
#include "analyzer/reachability.h"
@@ -64,6 +66,8 @@ along with GCC; see the file COPYING3. If not see
namespace ana {
+class feasible_worklist;
+
/* State for finding the shortest feasible exploded_path for a
saved_diagnostic.
This is shared between all diagnostics, so that we avoid repeating work. */
@@ -73,19 +77,42 @@ class epath_finder
public:
epath_finder (const exploded_graph &eg)
: m_eg (eg),
- m_sep (eg, eg.get_origin (), SPS_FROM_GIVEN_ORIGIN)
+ m_sep (NULL)
{
+ /* This is shared by all diagnostics, but only needed if
+ !flag_analyzer_feasibility. */
+ if (!flag_analyzer_feasibility)
+ m_sep = new shortest_exploded_paths (eg, eg.get_origin (),
+ SPS_FROM_GIVEN_ORIGIN);
}
+ ~epath_finder () { delete m_sep; }
+
logger *get_logger () const { return m_eg.get_logger (); }
- exploded_path *get_best_epath (const exploded_node *enode,
- const char *desc,
+ exploded_path *get_best_epath (const exploded_node *target_enode,
+ const char *desc, unsigned diag_idx,
feasibility_problem **out_problem);
private:
+ exploded_path *explore_feasible_paths (const exploded_node *target_enode,
+ const char *desc, unsigned diag_idx);
+ bool process_worklist_item (feasible_worklist *worklist,
+ const trimmed_graph &tg,
+ feasible_graph *fg,
+ const exploded_node *target_enode,
+ unsigned diag_idx,
+ exploded_path **out_best_path) const;
+ void dump_trimmed_graph (const exploded_node *target_enode,
+ const char *desc, unsigned diag_idx,
+ const trimmed_graph &tg,
+ const shortest_paths<eg_traits, exploded_path> &sep);
+ void dump_feasible_graph (const exploded_node *target_enode,
+ const char *desc, unsigned diag_idx,
+ const feasible_graph &fg);
+
const exploded_graph &m_eg;
- shortest_exploded_paths m_sep;
+ shortest_exploded_paths *m_sep;
};
/* class epath_finder. */
@@ -100,13 +127,13 @@ private:
If flag_analyzer_feasibility is false, then simply return the
shortest path.
- Use DESC when logging.
+ Use DESC and DIAG_IDX when logging.
- Write any feasiblity_problem to *OUT_PROBLEM. */
+ Write any feasibility_problem to *OUT_PROBLEM. */
exploded_path *
epath_finder::get_best_epath (const exploded_node *enode,
- const char *desc,
+ const char *desc, unsigned diag_idx,
feasibility_problem **out_problem)
{
logger *logger = get_logger ();
@@ -114,52 +141,434 @@ epath_finder::get_best_epath (const exploded_node *enode,
unsigned snode_idx = enode->get_supernode ()->m_index;
if (logger)
- logger->log ("considering %qs at EN: %i, SN: %i",
- desc, enode->m_index, snode_idx);
+ logger->log ("considering %qs at EN: %i, SN: %i (sd: %i)",
+ desc, enode->m_index, snode_idx, diag_idx);
/* State-merging means that not every path in the egraph corresponds
to a feasible one w.r.t. states.
We want to find the shortest feasible path from the origin to ENODE
- in the egraph.
+ in the egraph. */
- As a crude approximation to this, we find the shortest path, and
- determine if it is feasible. This could introduce false negatives,
- as there could be longer feasible paths within the egraph.
- (PR analyzer/96374). */
-
- exploded_path *epath = new exploded_path (m_sep.get_shortest_path (enode));
- if (epath->feasible_p (logger, out_problem, m_eg.get_engine (), &m_eg))
+ if (flag_analyzer_feasibility)
{
+ /* Attempt to find the shortest feasible path using feasible_graph. */
if (logger)
- logger->log ("accepting %qs at EN: %i, SN: %i with feasible path",
- desc, enode->m_index,
- snode_idx);
+ logger->log ("trying to find shortest feasible path");
+ if (exploded_path *epath = explore_feasible_paths (enode, desc, diag_idx))
+ {
+ if (logger)
+ logger->log ("accepting %qs at EN: %i, SN: %i (sd: %i)"
+ " with feasible path (length: %i)",
+ desc, enode->m_index, snode_idx, diag_idx,
+ epath->length ());
+ return epath;
+ }
+ else
+ {
+ if (logger)
+ logger->log ("rejecting %qs at EN: %i, SN: %i (sd: %i)"
+ " due to not finding feasible path",
+ desc, enode->m_index, snode_idx, diag_idx);
+ return NULL;
+ }
}
else
{
- if (flag_analyzer_feasibility)
+ /* As a crude approximation to shortest feasible path, simply find
+ the shortest path, and note whether it is feasible.
+ There could be longer feasible paths within the egraph, so this
+ approach would lead to diagnostics being falsely rejected
+ (PR analyzer/96374). */
+ if (logger)
+ logger->log ("trying to find shortest path ignoring feasibility");
+ gcc_assert (m_sep);
+ exploded_path *epath
+ = new exploded_path (m_sep->get_shortest_path (enode));
+ if (epath->feasible_p (logger, out_problem, m_eg.get_engine (), &m_eg))
{
if (logger)
- logger->log ("rejecting %qs at EN: %i, SN: %i"
- " due to infeasible path",
- desc, enode->m_index,
- snode_idx);
- delete epath;
- return NULL;
+ logger->log ("accepting %qs at EN: %i, SN: %i (sn: %i)"
+ " with feasible path (length: %i)",
+ desc, enode->m_index, snode_idx, diag_idx,
+ epath->length ());
}
else
{
if (logger)
- logger->log ("accepting %qs at EN: %i, SN: %i"
+ logger->log ("accepting %qs at EN: %i, SN: %i (sn: %i) (length: %i)"
" despite infeasible path (due to %qs)",
- desc, enode->m_index,
- snode_idx,
+ desc, enode->m_index, snode_idx, diag_idx,
+ epath->length (),
"-fno-analyzer-feasibility");
}
+ return epath;
+ }
+}
+
+/* A class for managing the worklist of feasible_nodes in
+ epath_finder::explore_feasible_paths, prioritizing them
+ so that shorter paths appear earlier in the queue. */
+
+class feasible_worklist
+{
+public:
+ feasible_worklist (const shortest_paths<eg_traits, exploded_path> &sep)
+ : m_queue (key_t (*this, NULL)),
+ m_sep (sep)
+ {
+ }
+
+ feasible_node *take_next () { return m_queue.extract_min (); }
+
+ void add_node (feasible_node *fnode)
+ {
+ m_queue.insert (key_t (*this, fnode), fnode);
+ }
+
+private:
+ struct key_t
+ {
+ key_t (const feasible_worklist &w, feasible_node *fnode)
+ : m_worklist (w), m_fnode (fnode)
+ {}
+
+ bool operator< (const key_t &other) const
+ {
+ return cmp (*this, other) < 0;
+ }
+
+ bool operator== (const key_t &other) const
+ {
+ return cmp (*this, other) == 0;
+ }
+
+ bool operator> (const key_t &other) const
+ {
+ return !(*this == other || *this < other);
+ }
+
+ private:
+ static int cmp (const key_t &ka, const key_t &kb)
+ {
+ /* Choose the node for which if the remaining path were feasible,
+ it would be the shortest path (summing the length of the
+ known-feasible path so far with that of the remaining
+ possibly-feasible path). */
+ int ca = ka.m_worklist.get_estimated_cost (ka.m_fnode);
+ int cb = kb.m_worklist.get_estimated_cost (kb.m_fnode);
+ return ca - cb;
+ }
+
+ const feasible_worklist &m_worklist;
+ feasible_node *m_fnode;
+ };
+
+ /* Get the estimated length of a path involving FNODE from
+ the origin to the target enode.
+ Sum the length of the known-feasible path so far with
+ that of the remaining possibly-feasible path. */
+
+ int get_estimated_cost (const feasible_node *fnode) const
+ {
+ unsigned length_so_far = fnode->get_path_length ();
+ int shortest_remaining_path
+ = m_sep.get_shortest_distance (fnode->get_inner_node ());
+
+ gcc_assert (shortest_remaining_path >= 0);
+ /* This should be true since we're only exploring nodes within
+ the trimmed graph (and we anticipate it being much smaller
+ than this, and thus not overflowing the sum). */
+ gcc_assert (shortest_remaining_path < INT_MAX);
+
+ return length_so_far + shortest_remaining_path;
+ }
+
+ /* Priority queue, backed by a fibonacci_heap. */
+ typedef fibonacci_heap<key_t, feasible_node> queue_t;
+ queue_t m_queue;
+ const shortest_paths<eg_traits, exploded_path> &m_sep;
+};
+
+/* Attempt to find the shortest feasible path from the origin to
+ TARGET_ENODE by iteratively building a feasible_graph, in which
+ every path to a feasible_node is feasible by construction.
+
+ We effectively explore the tree of feasible paths in order of shortest
+ path until we either find a feasible path to TARGET_ENODE, or hit
+ a limit and give up.
+
+ Preliminaries:
+ - Find the shortest path from each node to the TARGET_ENODE (without
+ checking feasibility), so that we can prioritize our worklist.
+ - Construct a trimmed_graph: the subset of nodes/edges that
+ are on a path that eventually reaches TARGET_ENODE. We will only need
+ to consider these when considering the shortest feasible path.
+
+ Build a feasible_graph, in which every path to a feasible_node
+ is feasible by construction.
+ We use a worklist to flatten the exploration into an iteration.
+ Starting at the origin, find feasible out-edges within the trimmed graph.
+ At each stage, choose the node for which if the remaining path were feasible,
+ it would be the shortest path (summing the length of the known-feasible path
+ so far with that of the remaining possibly-feasible path).
+ This way, the first feasible path we find to TARGET_ENODE is the shortest.
+ We start by trying the shortest possible path, but if that fails,
+ we explore progressively longer paths, eventually trying iterations through
+ loops. The exploration is captured in the feasible_graph, which can be
+ dumped as a .dot file to visualize the exploration. The indices of the
+ feasible_nodes show the order in which they were created.
+
+ This is something of a brute-force approach, but the trimmed_graph
+ hopefully keeps the complexity manageable.
+
+ Terminate with failure when the number of infeasible edges exceeds
+ a threshold (--param=analyzer-max-infeasible-edges=).
+ This is guaranteed to eventually lead to terminatation, as
+ we can't keep creating feasible nodes without eventually
+ either reaching an infeasible edge, or reaching the
+ TARGET_ENODE. Specifically, there can't be a cycle of
+ feasible edges that doesn't reach the target_enode without
+ an out-edge that either fails feasibility or gets closer
+ to the TARGET_ENODE: on each iteration we are either:
+ - effectively getting closer to the TARGET_ENODE (which can't
+ continue forever without reaching the target), or
+ - getting monotonically closer to the termination threshold. */
+
+exploded_path *
+epath_finder::explore_feasible_paths (const exploded_node *target_enode,
+ const char *desc, unsigned diag_idx)
+{
+ logger *logger = get_logger ();
+ LOG_SCOPE (logger);
+
+ /* Determine the shortest path to TARGET_ENODE from each node in
+ the exploded graph. */
+ shortest_paths<eg_traits, exploded_path> sep
+ (m_eg, target_enode, SPS_TO_GIVEN_TARGET);
+
+ /* Construct a trimmed_graph: the subset of nodes/edges that
+ are on a path that eventually reaches TARGET_ENODE.
+ We only need to consider these when considering the shortest
+ feasible path. */
+ trimmed_graph tg (m_eg, target_enode);
+
+ if (flag_dump_analyzer_feasibility)
+ dump_trimmed_graph (target_enode, desc, diag_idx, tg, sep);
+
+ feasible_graph fg;
+ feasible_worklist worklist (sep);
+
+ /* Populate the worklist with the origin node. */
+ {
+ feasibility_state init_state (m_eg.get_engine ()->get_model_manager (),
+ m_eg.get_supergraph ());
+ feasible_node *origin = fg.add_node (m_eg.get_origin (), init_state, 0);
+ worklist.add_node (origin);
+ }
+
+ /* Iteratively explore the tree of feasible paths in order of shortest
+ path until we either find a feasible path to TARGET_ENODE, or hit
+ a limit. */
+
+ /* Set this if we find a feasible path to TARGET_ENODE. */
+ exploded_path *best_path = NULL;
+
+ while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx,
+ &best_path))
+ {
+ /* Empty; the work is done within process_worklist_item. */
}
- return epath;
+ if (logger)
+ {
+ logger->log ("tg for sd: %i:", diag_idx);
+ logger->inc_indent ();
+ tg.log_stats (logger);
+ logger->dec_indent ();
+
+ logger->log ("fg for sd: %i:", diag_idx);
+ logger->inc_indent ();
+ fg.log_stats (logger);
+ logger->dec_indent ();
+ }
+
+ /* Dump the feasible_graph. */
+ if (flag_dump_analyzer_feasibility)
+ dump_feasible_graph (target_enode, desc, diag_idx, fg);
+
+ return best_path;
+}
+
+/* Process the next item in WORKLIST, potentially adding new items
+ based on feasible out-edges, and extending FG accordingly.
+ Use TG to ignore out-edges that don't lead to TARGET_ENODE.
+ Return true if the worklist processing should continue.
+ Return false if the processing of the worklist should stop
+ (either due to reaching TARGET_ENODE, or hitting a limit).
+ Write to *OUT_BEST_PATH if stopping due to finding a feasible path
+ to TARGET_ENODE. */
+
+bool
+epath_finder::process_worklist_item (feasible_worklist *worklist,
+ const trimmed_graph &tg,
+ feasible_graph *fg,
+ const exploded_node *target_enode,
+ unsigned diag_idx,
+ exploded_path **out_best_path) const
+{
+ logger *logger = get_logger ();
+
+ feasible_node *fnode = worklist->take_next ();
+ if (!fnode)
+ {
+ if (logger)
+ logger->log ("drained worklist for sd: %i"
+ " without finding feasible path",
+ diag_idx);
+ return false;
+ }
+
+ log_scope s (logger, "fg worklist item",
+ "considering FN: %i (EN: %i) for sd: %i",
+ fnode->get_index (), fnode->get_inner_node ()->m_index,
+ diag_idx);
+
+ /* Iterate through all out-edges from this item. */
+ unsigned i;
+ exploded_edge *succ_eedge;
+ FOR_EACH_VEC_ELT (fnode->get_inner_node ()->m_succs, i, succ_eedge)
+ {
+ log_scope s (logger, "edge", "considering edge: EN:%i -> EN:%i",
+ succ_eedge->m_src->m_index,
+ succ_eedge->m_dest->m_index);
+ /* Reject edges that aren't in the trimmed graph. */
+ if (!tg.contains_p (succ_eedge))
+ {
+ if (logger)
+ logger->log ("rejecting: not in trimmed graph");
+ continue;
+ }
+
+ feasibility_state succ_state (fnode->get_state ());
+ rejected_constraint *rc = NULL;
+ if (succ_state.maybe_update_for_edge (logger, succ_eedge, &rc))
+ {
+ gcc_assert (rc == NULL);
+ feasible_node *succ_fnode
+ = fg->add_node (succ_eedge->m_dest,
+ succ_state,
+ fnode->get_path_length () + 1);
+ if (logger)
+ logger->log ("accepting as FN: %i", succ_fnode->get_index ());
+ fg->add_edge (new feasible_edge (fnode, succ_fnode, succ_eedge));
+
+ /* Have we reached TARGET_ENODE? */
+ if (succ_fnode->get_inner_node () == target_enode)
+ {
+ if (logger)
+ logger->log ("success: got feasible path to EN: %i (sd: %i)"
+ " (length: %i)",
+ target_enode->m_index, diag_idx,
+ succ_fnode->get_path_length ());
+ *out_best_path = fg->make_epath (succ_fnode);
+ /* Success: stop the worklist iteration. */
+ return false;
+ }
+ else
+ worklist->add_node (succ_fnode);
+ }
+ else
+ {
+ if (logger)
+ logger->log ("infeasible");
+ gcc_assert (rc);
+ fg->add_feasibility_problem (fnode,
+ succ_eedge,
+ *rc);
+ delete rc;
+
+ /* Give up if there have been too many infeasible edges. */
+ if (fg->get_num_infeasible ()
+ > (unsigned)param_analyzer_max_infeasible_edges)
+ {
+ if (logger)
+ logger->log ("too many infeasible edges (%i); giving up",
+ fg->get_num_infeasible ());
+ return false;
+ }
+ }
+ }
+
+ /* Continue the worklist iteration. */
+ return true;
+}
+
+/* Helper class for epath_finder::dump_trimmed_graph
+ to dump extra per-node information.
+ Use SEP to add the length of the shortest path from each
+ node to the target node to each node's dump. */
+
+class dump_eg_with_shortest_path : public eg_traits::dump_args_t
+{
+public:
+ dump_eg_with_shortest_path
+ (const exploded_graph &eg,
+ const shortest_paths<eg_traits, exploded_path> &sep)
+ : dump_args_t (eg),
+ m_sep (sep)
+ {
+ }
+
+ void dump_extra_info (const exploded_node *enode,
+ pretty_printer *pp) const FINAL OVERRIDE
+ {
+ pp_printf (pp, "sp: %i", m_sep.get_shortest_path (enode).length ());
+ pp_newline (pp);
+ }
+
+private:
+ const shortest_paths<eg_traits, exploded_path> &m_sep;
+};
+
+/* Dump TG to "BASE_NAME.DESC.DIAG_IDX.to-enN.tg.dot",
+ annotating each node with the length of the shortest path
+ from that node to TARGET_ENODE (using SEP). */
+
+void
+epath_finder::
+dump_trimmed_graph (const exploded_node *target_enode,
+ const char *desc, unsigned diag_idx,
+ const trimmed_graph &tg,
+ const shortest_paths<eg_traits, exploded_path> &sep)
+{
+ auto_timevar tv (TV_ANALYZER_DUMP);
+ dump_eg_with_shortest_path inner_args (m_eg, sep);
+ trimmed_graph::dump_args_t args (inner_args);
+ pretty_printer pp;
+ pp_printf (&pp, "%s.%s.%i.to-en%i.tg.dot",
+ dump_base_name, desc, diag_idx, target_enode->m_index);
+ char *filename = xstrdup (pp_formatted_text (&pp));
+ tg.dump_dot (filename, NULL, args);
+ free (filename);
+}
+
+/* Dump FG to "BASE_NAME.DESC.DIAG_IDX.to-enN.fg.dot". */
+
+void
+epath_finder::dump_feasible_graph (const exploded_node *target_enode,
+ const char *desc, unsigned diag_idx,
+ const feasible_graph &fg)
+{
+ auto_timevar tv (TV_ANALYZER_DUMP);
+ exploded_graph::dump_args_t inner_args (m_eg);
+ feasible_graph::dump_args_t args (inner_args);
+ pretty_printer pp;
+ pp_printf (&pp, "%s.%s.%i.to-en%i.fg.dot",
+ dump_base_name, desc, diag_idx, target_enode->m_index);
+ char *filename = xstrdup (pp_formatted_text (&pp));
+ fg.dump_dot (filename, NULL, args);
+ free (filename);
}
/* class saved_diagnostic. */
@@ -174,13 +583,15 @@ saved_diagnostic::saved_diagnostic (const state_machine *sm,
tree var,
const svalue *sval,
state_machine::state_t state,
- pending_diagnostic *d)
+ pending_diagnostic *d,
+ unsigned idx)
: m_sm (sm), m_enode (enode), m_snode (snode), m_stmt (stmt),
/* stmt_finder could be on-stack; we want our own copy that can
outlive that. */
m_stmt_finder (stmt_finder ? stmt_finder->clone () : NULL),
m_var (var), m_sval (sval), m_state (state),
m_d (d), m_trailing_eedge (NULL),
+ m_idx (idx),
m_best_epath (NULL), m_problem (NULL)
{
gcc_assert (m_stmt || m_stmt_finder);
@@ -221,7 +632,8 @@ saved_diagnostic::operator== (const saved_diagnostic &other) const
"sval": optional str,
"state": optional str,
"path_length": optional int,
- "pending_diagnostic": str}. */
+ "pending_diagnostic": str,
+ "idx": int}. */
json::object *
saved_diagnostic::to_json () const
@@ -239,6 +651,7 @@ saved_diagnostic::to_json () const
if (m_best_epath)
sd_obj->set ("path_length", new json::integer_number (get_epath_length ()));
sd_obj->set ("pending_diagnostic", new json::string (m_d->get_kind ()));
+ sd_obj->set ("idx", new json::integer_number (m_idx));
/* We're not yet JSONifying the following fields:
const gimple *m_stmt;
@@ -267,15 +680,12 @@ saved_diagnostic::calc_best_epath (epath_finder *pf)
delete m_problem;
m_problem = NULL;
- m_best_epath = pf->get_best_epath (m_enode, m_d->get_kind (),
+ m_best_epath = pf->get_best_epath (m_enode, m_d->get_kind (), m_idx,
&m_problem);
/* Handle failure to find a feasible path. */
if (m_best_epath == NULL)
- {
- gcc_assert (m_problem);
- return false;
- }
+ return false;
gcc_assert (m_best_epath);
if (m_stmt == NULL)
@@ -395,11 +805,11 @@ diagnostic_manager::add_diagnostic (const state_machine *sm,
saved_diagnostic *sd
= new saved_diagnostic (sm, enode, snode, stmt, finder, var, sval,
- state, d);
+ state, d, m_saved_diagnostics.length ());
m_saved_diagnostics.safe_push (sd);
if (get_logger ())
log ("adding saved diagnostic %i at SN %i: %qs",
- m_saved_diagnostics.length () - 1,
+ sd->get_index (),
snode->m_index, d->get_kind ());
}
diff --git a/gcc/analyzer/diagnostic-manager.h b/gcc/analyzer/diagnostic-manager.h
index c55807851fd..14549779549 100644
--- a/gcc/analyzer/diagnostic-manager.h
+++ b/gcc/analyzer/diagnostic-manager.h
@@ -36,7 +36,8 @@ public:
stmt_finder *stmt_finder,
tree var, const svalue *sval,
state_machine::state_t state,
- pending_diagnostic *d);
+ pending_diagnostic *d,
+ unsigned idx);
~saved_diagnostic ();
bool operator== (const saved_diagnostic &other) const;
@@ -55,6 +56,8 @@ public:
void add_duplicate (saved_diagnostic *other);
unsigned get_num_dupes () const { return m_duplicates.length (); }
+ unsigned get_index () const { return m_idx; }
+
//private:
const state_machine *m_sm;
const exploded_node *m_enode;
@@ -70,6 +73,7 @@ public:
private:
DISABLE_COPY_AND_ASSIGN (saved_diagnostic);
+ unsigned m_idx;
exploded_path *m_best_epath; // owned
feasibility_problem *m_problem; // owned
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index fef482364c4..5792c142847 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -946,41 +946,12 @@ exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
state.dump_to_pp (ext_state, false, true, pp);
pp_newline (pp);
- /* Show any stmts that were processed within this enode,
- and their index within the supernode. */
- if (m_num_processed_stmts > 0)
- {
- const program_point &point = get_point ();
- gcc_assert (point.get_kind () == PK_BEFORE_STMT);
- const supernode *snode = get_supernode ();
- const unsigned int point_stmt_idx = point.get_stmt_idx ();
-
- pp_printf (pp, "stmts: %i", m_num_processed_stmts);
- pp_newline (pp);
- for (unsigned i = 0; i < m_num_processed_stmts; i++)
- {
- const unsigned int idx_within_snode = point_stmt_idx + i;
- const gimple *stmt = snode->m_stmts[idx_within_snode];
- pp_printf (pp, " %i: ", idx_within_snode);
- pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
- pp_newline (pp);
- }
- }
+ dump_processed_stmts (pp);
}
- /* Dump any saved_diagnostics at this enode. */
- {
- const diagnostic_manager &dm = args.m_eg.get_diagnostic_manager ();
- for (unsigned i = 0; i < dm.get_num_diagnostics (); i++)
- {
- const saved_diagnostic *sd = dm.get_saved_diagnostic (i);
- if (sd->m_enode == this)
- {
- pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
- pp_newline (pp);
- }
- }
- }
+ dump_saved_diagnostics (pp, args.m_eg.get_diagnostic_manager ());
+
+ args.dump_extra_info (this, pp);
pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
@@ -988,6 +959,49 @@ exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
pp_flush (pp);
}
+/* Show any stmts that were processed within this enode,
+ and their index within the supernode. */
+void
+exploded_node::dump_processed_stmts (pretty_printer *pp) const
+{
+ if (m_num_processed_stmts > 0)
+ {
+ const program_point &point = get_point ();
+ gcc_assert (point.get_kind () == PK_BEFORE_STMT);
+ const supernode *snode = get_supernode ();
+ const unsigned int point_stmt_idx = point.get_stmt_idx ();
+
+ pp_printf (pp, "stmts: %i", m_num_processed_stmts);
+ pp_newline (pp);
+ for (unsigned i = 0; i < m_num_processed_stmts; i++)
+ {
+ const unsigned int idx_within_snode = point_stmt_idx + i;
+ const gimple *stmt = snode->m_stmts[idx_within_snode];
+ pp_printf (pp, " %i: ", idx_within_snode);
+ pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
+ pp_newline (pp);
+ }
+ }
+}
+
+/* Dump any saved_diagnostics at this enode to PP. */
+
+void
+exploded_node::dump_saved_diagnostics (pretty_printer *pp,
+ const diagnostic_manager &dm) const
+{
+ for (unsigned i = 0; i < dm.get_num_diagnostics (); i++)
+ {
+ const saved_diagnostic *sd = dm.get_saved_diagnostic (i);
+ if (sd->m_enode == this)
+ {
+ pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)",
+ sd->m_d->get_kind (), sd->get_index ());
+ pp_newline (pp);
+ }
+ }
+}
+
/* Dump this to PP in a form suitable for use as an id in .dot output. */
void
@@ -1639,6 +1653,18 @@ exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
{
pretty_printer *pp = gv->get_pp ();
+ m_src->dump_dot_id (pp);
+ pp_string (pp, " -> ");
+ m_dest->dump_dot_id (pp);
+ dump_dot_label (pp);
+}
+
+/* Second half of exploded_edge::dump_dot. This is split out
+ for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
+
+void
+exploded_edge::dump_dot_label (pretty_printer *pp) const
+{
const char *style = "\"solid,bold\"";
const char *color = "black";
int weight = 10;
@@ -1669,9 +1695,6 @@ exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
style = "\"dotted\"";
}
- m_src->dump_dot_id (pp);
- pp_string (pp, " -> ");
- m_dest->dump_dot_id (pp);
pp_printf (pp,
(" [style=%s, color=%s, weight=%d, constraint=%s,"
" headlabel=\""),
@@ -3352,6 +3375,10 @@ exploded_graph::to_json () const
return egraph_obj;
}
+/* class exploded_path. */
+
+/* Copy ctor. */
+
exploded_path::exploded_path (const exploded_path &other)
: m_edges (other.m_edges.length ())
{
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index da1cebb1aef..deb739f5572 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -135,6 +135,9 @@ struct eg_traits
bool show_enode_details_p (const exploded_node &enode) const;
+ virtual void
+ dump_extra_info (const exploded_node *, pretty_printer *) const {}
+
const exploded_graph &m_eg;
};
typedef exploded_cluster cluster_t;
@@ -182,6 +185,10 @@ class exploded_node : public dnode<eg_traits>
void dump (FILE *fp, const extrinsic_state &ext_state) const;
void dump (const extrinsic_state &ext_state) const;
+ void dump_processed_stmts (pretty_printer *pp) const;
+ void dump_saved_diagnostics (pretty_printer *pp,
+ const diagnostic_manager &dm) const;
+
json::object *to_json (const extrinsic_state &ext_state) const;
/* The result of on_stmt. */
@@ -311,6 +318,7 @@ class exploded_edge : public dedge<eg_traits>
~exploded_edge ();
void dump_dot (graphviz_out *gv, const dump_args_t &args)
const FINAL OVERRIDE;
+ void dump_dot_label (pretty_printer *pp) const;
json::object *to_json () const;
diff --git a/gcc/analyzer/feasible-graph.cc b/gcc/analyzer/feasible-graph.cc
new file mode 100644
index 00000000000..bb409d61dd2
--- /dev/null
+++ b/gcc/analyzer/feasible-graph.cc
@@ -0,0 +1,235 @@
+/* A graph for exploring trees of feasible paths through the egraph.
+ Copyright (C) 2021 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/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "pretty-print.h"
+#include "gcc-rich-location.h"
+#include "gimple-pretty-print.h"
+#include "function.h"
+#include "diagnostic-core.h"
+#include "diagnostic-event-id.h"
+#include "diagnostic-path.h"
+#include "alloc-pool.h"
+#include "fibonacci_heap.h"
+#include "shortest-paths.h"
+#include "sbitmap.h"
+#include "bitmap.h"
+#include "tristate.h"
+#include "selftest.h"
+#include "ordered-hash-map.h"
+#include "json.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/analyzer-logging.h"
+#include "analyzer/sm.h"
+#include "analyzer/pending-diagnostic.h"
+#include "analyzer/diagnostic-manager.h"
+#include "analyzer/call-string.h"
+#include "analyzer/program-point.h"
+#include "analyzer/store.h"
+#include "analyzer/region-model.h"
+#include "analyzer/constraint-manager.h"
+#include "cfg.h"
+#include "basic-block.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "cgraph.h"
+#include "digraph.h"
+#include "analyzer/supergraph.h"
+#include "analyzer/program-state.h"
+#include "analyzer/exploded-graph.h"
+#include "analyzer/feasible-graph.h"
+
+#if ENABLE_ANALYZER
+
+namespace ana {
+
+/* class base_feasible_node : public dnode<fg_traits>. */
+
+/* Print an id to PP for this node suitable for use in .dot dumps. */
+
+void
+base_feasible_node::dump_dot_id (pretty_printer *pp) const
+{
+ pp_printf (pp, "fnode_%i", m_index);
+}
+
+/* class feasible_node : public base_feasible_node. */
+
+/* Implementation of dump_dot vfunc for feasible_node. */
+
+void
+feasible_node::dump_dot (graphviz_out *gv,
+ const dump_args_t &args) const
+{
+ pretty_printer *pp = gv->get_pp ();
+
+ dump_dot_id (pp);
+ pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
+ m_inner_node->get_dot_fillcolor ());
+ pp_write_text_to_stream (pp);
+
+ pp_printf (pp, "FN: %i (EN: %i); len=%i", m_index, m_inner_node->m_index,
+ m_path_length);
+ pp_newline (pp);
+
+ format f (true);
+ m_inner_node->get_point ().print (pp, f);
+ pp_newline (pp);
+
+ /* Show the model at this point along expansion of the feasible path,
+ rather than the model within the enode. */
+ m_state.get_model ().dump_to_pp (pp, true, true);
+ pp_newline (pp);
+
+ m_inner_node->dump_processed_stmts (pp);
+ m_inner_node->dump_saved_diagnostics
+ (pp, args.m_inner_args.m_eg.get_diagnostic_manager ());
+
+ pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
+
+ pp_string (pp, "\"];\n\n");
+ pp_flush (pp);
+}
+
+/* Implementation of dump_dot vfunc for infeasible_node.
+ In particular, show the rejected constraint. */
+
+void
+infeasible_node::dump_dot (graphviz_out *gv,
+ const dump_args_t &) const
+{
+ pretty_printer *pp = gv->get_pp ();
+
+ dump_dot_id (pp);
+ pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
+ m_inner_node->get_dot_fillcolor ());
+ pp_write_text_to_stream (pp);
+
+ pp_printf (pp, "infeasible edge to EN: %i", m_inner_node->m_index);
+ pp_newline (pp);
+
+ pp_string (pp, "rejected constraint:");
+ pp_newline (pp);
+ m_rc.dump_to_pp (pp);
+
+ pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
+
+ pp_string (pp, "\"];\n\n");
+ pp_flush (pp);
+}
+
+/* class base_feasible_edge : public dedge<fg_traits>. */
+
+/* Implementation of dump_dot vfunc for base_easible_edge. */
+
+void
+base_feasible_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
+{
+ pretty_printer *pp = gv->get_pp ();
+
+ m_src->dump_dot_id (pp);
+ pp_string (pp, " -> ");
+ m_dest->dump_dot_id (pp);
+
+ m_inner_edge->dump_dot_label (pp);
+}
+
+/* class feasible_graph : public digraph <fg_traits>. */
+
+/* Ctor for feasible_graph. */
+
+feasible_graph::feasible_graph ()
+: m_num_infeasible (0)
+{
+}
+
+/* Add a feasible_node to this graph for ENODE, STATE with the
+ given PATH_LENGTH. */
+
+feasible_node *
+feasible_graph::add_node (const exploded_node *enode,
+ const feasibility_state &state,
+ unsigned path_length)
+{
+ /* We don't attempt get_or_create here. */
+ feasible_node *fnode = new feasible_node (enode, m_nodes.length (),
+ state, path_length);
+ digraph<fg_traits>::add_node (fnode);
+ return fnode;
+}
+
+/* Add an infeasible_node to this graph and an infeasible_edge connecting
+ to it from SRC_FNODE, capturing a failure of RC along EEDGE. */
+
+void
+feasible_graph::add_feasibility_problem (feasible_node *src_fnode,
+ const exploded_edge *eedge,
+ const rejected_constraint &rc)
+{
+ infeasible_node *dst_fnode
+ = new infeasible_node (eedge->m_dest, m_nodes.length (), rc);
+ digraph<fg_traits>::add_node (dst_fnode);
+ add_edge (new infeasible_edge (src_fnode, dst_fnode, eedge));
+ m_num_infeasible++;
+}
+
+/* Make an exploded_path from the origin to FNODE's exploded_node,
+ following the edges in the feasible_graph. */
+
+exploded_path *
+feasible_graph::make_epath (feasible_node *fnode) const
+{
+ exploded_path *epath = new exploded_path ();
+
+ /* FG is actually a tree. Built the path backwards, by walking
+ backwards from FNODE until we reach the origin. */
+ while (fnode->get_inner_node ()->m_index != 0)
+ {
+ gcc_assert (fnode->m_preds.length () == 1);
+ feasible_edge *pred_fedge
+ = static_cast <feasible_edge *> (fnode->m_preds[0]);
+ epath->m_edges.safe_push (pred_fedge->get_inner_edge ());
+ fnode = static_cast <feasible_node *> (pred_fedge->m_src);
+ }
+
+ /* Now reverse it. */
+ epath->m_edges.reverse ();
+
+ return epath;
+}
+
+/* Dump stats about this graph to LOGGER. */
+
+void
+feasible_graph::log_stats (logger *logger) const
+{
+ logger->log ("#nodes: %i", m_nodes.length ());
+ logger->log ("#edges: %i", m_edges.length ());
+ logger->log ("#feasible nodes: %i", m_nodes.length () - m_num_infeasible);
+ logger->log ("#feasible edges: %i", m_edges.length () - m_num_infeasible);
+ logger->log ("#infeasible nodes/edges: %i", m_num_infeasible);
+}
+
+} // namespace ana
+
+#endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/feasible-graph.h b/gcc/analyzer/feasible-graph.h
new file mode 100644
index 00000000000..5a580f4b925
--- /dev/null
+++ b/gcc/analyzer/feasible-graph.h
@@ -0,0 +1,213 @@
+/* A graph for exploring trees of feasible paths through the egraph.
+ Copyright (C) 2021 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_FEASIBLE_GRAPH_H
+#define GCC_ANALYZER_FEASIBLE_GRAPH_H
+
+namespace ana {
+
+/* Forward decls. */
+
+class base_feasible_node;
+ class feasible_node;
+ class infeasible_node;
+class base_feasible_edge;
+ class feasible_edge;
+ class infeasible_edge;
+class feasible_graph;
+class feasible_cluster;
+
+/* A traits class for feasible_graph. */
+
+struct fg_traits
+{
+ typedef base_feasible_node node_t;
+ typedef base_feasible_edge edge_t;
+ typedef feasible_graph graph_t;
+ struct dump_args_t
+ {
+ typedef typename eg_traits::dump_args_t inner_args_t;
+
+ dump_args_t (const inner_args_t &inner_args)
+ : m_inner_args (inner_args)
+ {
+ }
+
+ const inner_args_t &m_inner_args;
+ };
+ typedef feasible_cluster cluster_t;
+};
+
+/* Base class of node within a feasible_graph.
+ There can be 0 or more base_feasible_nodes per exploded_node. */
+
+class base_feasible_node : public dnode<fg_traits>
+{
+ public:
+ void dump_dot_id (pretty_printer *pp) const;
+
+ const exploded_node *get_inner_node () const { return m_inner_node; }
+ unsigned get_index () const { return m_index; }
+
+ protected:
+ base_feasible_node (const exploded_node *inner_node, unsigned index)
+ : m_inner_node (inner_node), m_index (index)
+ {}
+
+ const exploded_node *m_inner_node;
+ unsigned m_index;
+};
+
+/* Subclass of base_feasible_node for a node that is reachable via a
+ feasible path, with a particular state. */
+
+class feasible_node : public base_feasible_node
+{
+public:
+ feasible_node (const exploded_node *inner_node, unsigned index,
+ const feasibility_state &state,
+ unsigned path_length)
+ : base_feasible_node (inner_node, index),
+ m_state (state),
+ m_path_length (path_length)
+ {
+ }
+
+ void dump_dot (graphviz_out *gv,
+ const dump_args_t &args) const FINAL OVERRIDE;
+
+ const feasibility_state &get_state () const { return m_state; }
+ const region_model &get_model () const { return m_state.get_model (); }
+ const auto_sbitmap &get_snodes_visited () const
+ {
+ return m_state.get_snodes_visited ();
+ }
+
+ unsigned get_path_length () const { return m_path_length; }
+
+private:
+ feasibility_state m_state;
+ unsigned m_path_length;
+};
+
+/* Subclass of base_feasible_node for a node that requires following
+ an infeasible edge to reach (and thus terminating this part of the
+ exploration). */
+
+class infeasible_node : public base_feasible_node
+{
+public:
+ infeasible_node (const exploded_node *inner_node, unsigned index,
+ const rejected_constraint &rc)
+ : base_feasible_node (inner_node, index),
+ m_rc (rc)
+ {
+ }
+
+ void dump_dot (graphviz_out *gv,
+ const dump_args_t &args) const FINAL OVERRIDE;
+
+private:
+ rejected_constraint m_rc;
+};
+
+/* Base class of edge within a feasible_graph. */
+
+class base_feasible_edge : public dedge<fg_traits>
+{
+ public:
+ void dump_dot (graphviz_out *gv,
+ const dump_args_t &args) const FINAL OVERRIDE;
+
+ const exploded_edge *get_inner_edge () const { return m_inner_edge; }
+
+ protected:
+ base_feasible_edge (base_feasible_node *src, base_feasible_node *dest,
+ const exploded_edge *inner_edge)
+ : dedge<fg_traits> (src, dest), m_inner_edge (inner_edge)
+ {
+ }
+
+ const exploded_edge *m_inner_edge;
+};
+
+/* Subclass of base_feasible_edge for connecting two feasible_nodes. */
+
+class feasible_edge : public base_feasible_edge
+{
+ public:
+ feasible_edge (feasible_node *src, feasible_node *dest,
+ const exploded_edge *inner_edge)
+ : base_feasible_edge (src, dest, inner_edge)
+ {
+ }
+};
+
+/* Subclass of base_feasible_edge for connecting a feasible_node
+ to an infeasible_node (and thus terminating this part of the
+ exploration). */
+
+class infeasible_edge : public base_feasible_edge
+{
+ public:
+ infeasible_edge (feasible_node *src, infeasible_node *dest,
+ const exploded_edge *inner_edge)
+ : base_feasible_edge (src, dest, inner_edge)
+ {
+ }
+};
+
+/* A digraph subclass for exploring trees of feasible paths through
+ the egraph. This is actually a tree.
+
+ The paths within the graph of feasible_nodes express feasible paths
+ through the graph, and it also captures known infeasible edges,
+ which is invaluable for debugging. */
+
+class feasible_graph : public digraph <fg_traits>
+{
+ public:
+ feasible_graph ();
+
+ feasible_node *add_node (const exploded_node *enode,
+ const feasibility_state &state,
+ unsigned path_length);
+
+ void add_feasibility_problem (feasible_node *src_fnode,
+ const exploded_edge *eedge,
+ const rejected_constraint &rc);
+
+ exploded_path *make_epath (feasible_node *fnode) const;
+
+ unsigned get_num_infeasible () const { return m_num_infeasible; }
+
+ void log_stats (logger *logger) const;
+
+private:
+ unsigned m_num_infeasible;
+};
+
+class feasible_cluster : public cluster <fg_traits>
+{
+};
+
+} // namespace ana
+
+#endif /* GCC_ANALYZER_FEASIBLE_GRAPH_H */
diff --git a/gcc/analyzer/trimmed-graph.cc b/gcc/analyzer/trimmed-graph.cc
new file mode 100644
index 00000000000..2e23a0960b6
--- /dev/null
+++ b/gcc/analyzer/trimmed-graph.cc
@@ -0,0 +1,172 @@
+/* Trimming an exploded graph to a subset of nodes and edges.
+ Copyright (C) 2021 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/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "pretty-print.h"
+#include "gcc-rich-location.h"
+#include "gimple-pretty-print.h"
+#include "function.h"
+#include "diagnostic-core.h"
+#include "diagnostic-event-id.h"
+#include "diagnostic-path.h"
+#include "alloc-pool.h"
+#include "fibonacci_heap.h"
+#include "shortest-paths.h"
+#include "sbitmap.h"
+#include "bitmap.h"
+#include "tristate.h"
+#include "selftest.h"
+#include "ordered-hash-map.h"
+#include "json.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/analyzer-logging.h"
+#include "analyzer/sm.h"
+#include "analyzer/pending-diagnostic.h"
+#include "analyzer/diagnostic-manager.h"
+#include "analyzer/call-string.h"
+#include "analyzer/program-point.h"
+#include "analyzer/store.h"
+#include "analyzer/region-model.h"
+#include "analyzer/constraint-manager.h"
+#include "cfg.h"
+#include "basic-block.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "cgraph.h"
+#include "digraph.h"
+#include "analyzer/supergraph.h"
+#include "analyzer/program-state.h"
+#include "analyzer/exploded-graph.h"
+#include "analyzer/trimmed-graph.h"
+
+#if ENABLE_ANALYZER
+
+namespace ana {
+
+/* class trimmed_node : public dnode<tg_traits>. */
+
+/* Implementation of dump_dot vfunc, delegating to the inner node. */
+
+void
+trimmed_node::dump_dot (graphviz_out *gv,
+ const dump_args_t &args) const
+{
+ m_inner_node->dump_dot (gv, args.m_inner_args);
+}
+
+/* class trimmed_edge : public dedge<tg_traits>. */
+
+/* trimmed_edge's ctor. */
+
+trimmed_edge::trimmed_edge (trimmed_node *src, trimmed_node *dest,
+ const exploded_edge *inner_edge)
+: dedge<tg_traits> (src, dest), m_inner_edge (inner_edge)
+{
+}
+
+/* Implementation of dump_dot vfunc, delegating to the inner edge. */
+
+void
+trimmed_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const
+{
+ m_inner_edge->dump_dot (gv, args.m_inner_args);
+}
+
+/* class trimmed_graph : public digraph <tg_traits>. */
+
+/* Ctor for trimmed_graph: construct a graph equivalent to trimming
+ INNER_GRAPH to all nodes that can reach INNER_DST_NODE. */
+
+trimmed_graph::trimmed_graph (const exploded_graph &inner_graph,
+ const exploded_node *inner_dst_node)
+: m_enodes (), m_eedges ()
+{
+ /* Determine what subset of nodes and edges to include in the
+ trimmed graph.
+ Walk backwards from INNER_DST_NODE, finding nodes that reach it,
+ iteratively building the set of nodes and edges. */
+ auto_vec <const exploded_node *> worklist;
+ worklist.safe_push (inner_dst_node);
+ m_enodes.add (inner_dst_node);
+ while (worklist.length () > 0)
+ {
+ const exploded_node *inner_node = worklist.pop ();
+ exploded_edge *inner_pred;
+ unsigned i;
+ FOR_EACH_VEC_ELT (inner_node->m_preds, i, inner_pred)
+ {
+ if (!m_enodes.contains (inner_pred->m_src))
+ {
+ worklist.safe_push (inner_pred->m_src);
+ m_enodes.add (inner_pred->m_src);
+ }
+ m_eedges.add (inner_pred);
+ }
+ }
+
+ /* Create trimmed nodes for all enodes in the set. */
+ {
+ /* Iterate over the vec rather than the hash_set
+ to ensure deterministic order. */
+ exploded_node *inner_node;
+ unsigned i;
+ FOR_EACH_VEC_ELT (inner_graph.m_nodes, i, inner_node)
+ if (m_enodes.contains (inner_node))
+ {
+ trimmed_node *tnode = new trimmed_node (inner_node);
+ add_node (tnode);
+ m_map_from_enode_to_tnode.put (inner_node, tnode);
+ }
+ }
+
+ /* Create trimmed edges for all edges in the set. */
+ {
+ /* Iterate over the vec rather than the hash_set
+ to ensure deterministic order. */
+ exploded_edge *inner_edge;
+ unsigned i;
+ FOR_EACH_VEC_ELT (inner_graph.m_edges, i, inner_edge)
+ if (m_eedges.contains (inner_edge))
+ {
+ const exploded_node *inner_src = inner_edge->m_src;
+ const exploded_node *inner_dest = inner_edge->m_dest;
+ trimmed_node *tsrc = *m_map_from_enode_to_tnode.get (inner_src);
+ trimmed_node *tdest = *m_map_from_enode_to_tnode.get (inner_dest);
+ trimmed_edge *tedge = new trimmed_edge (tsrc, tdest, inner_edge);
+ add_edge (tedge);
+ }
+ }
+}
+
+/* Dump stats about this graph to LOGGER. */
+
+void
+trimmed_graph::log_stats (logger *logger) const
+{
+ logger->log ("#nodes: %i", m_nodes.length ());
+ logger->log ("#edges: %i", m_edges.length ());
+}
+
+} // namespace ana
+
+#endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/trimmed-graph.h b/gcc/analyzer/trimmed-graph.h
new file mode 100644
index 00000000000..bfe243a4e1c
--- /dev/null
+++ b/gcc/analyzer/trimmed-graph.h
@@ -0,0 +1,122 @@
+/* Trimming an exploded graph to a subset of nodes and edges.
+ Copyright (C) 2021 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_TRIMMED_GRAPH_H
+#define GCC_ANALYZER_TRIMMED_GRAPH_H
+
+namespace ana {
+
+/* Forward decls. */
+
+class trimmed_node;
+class trimmed_edge;
+class trimmed_graph;
+class trimmed_cluster;
+
+/* A traits class for trimming a digraph to a subset of nodes and edges. */
+
+struct tg_traits
+{
+ typedef trimmed_node node_t;
+ typedef trimmed_edge edge_t;
+ typedef trimmed_graph graph_t;
+ struct dump_args_t
+ {
+ typedef typename eg_traits::dump_args_t inner_args_t;
+
+ dump_args_t (const inner_args_t &inner_args)
+ : m_inner_args (inner_args)
+ {
+ }
+
+ const inner_args_t &m_inner_args;
+ };
+ typedef trimmed_cluster cluster_t;
+};
+
+/* A node within the trimmed_graph, corresponding to an "inner node"
+ within the original exploded_graph. */
+
+class trimmed_node : public dnode<tg_traits>
+{
+public:
+ trimmed_node (const exploded_node *inner_node)
+ : m_inner_node (inner_node) {}
+
+ void dump_dot (graphviz_out *gv,
+ const dump_args_t &args) const FINAL OVERRIDE;
+
+private:
+ const exploded_node *m_inner_node;
+};
+
+/* An edge within the trimmed_graph, corresponding to an "inner edge"
+ within the original exploded_graph. */
+
+class trimmed_edge : public dedge<tg_traits>
+{
+ public:
+ trimmed_edge (trimmed_node *src, trimmed_node *dest,
+ const exploded_edge *inner_edge);
+
+ void dump_dot (graphviz_out *gv,
+ const dump_args_t &args) const FINAL OVERRIDE;
+
+ private:
+ const exploded_edge *m_inner_edge;
+};
+
+/* A digraph for trimming an exploded_graph to the subset of nodes and edges
+ from which paths reach INNER_DST_NODE (along with a precanned way to print
+ these in .dot form). */
+
+class trimmed_graph : public digraph <tg_traits>
+{
+ public:
+ trimmed_graph (const exploded_graph &inner_graph,
+ const exploded_node *inner_dst_node);
+
+ bool contains_p (const exploded_edge *eedge) const
+ {
+ hash_set <const exploded_edge *> & mut
+ = const_cast <hash_set <const exploded_edge *> &> (m_eedges);
+ return mut.contains (eedge);
+ }
+
+ void log_stats (logger *logger) const;
+
+ private:
+ /* The subset of nodes in the inner graph that are in the
+ trimmed graph. */
+ hash_set <const exploded_node *> m_enodes;
+ /* Likewise for edges. */
+ hash_set <const exploded_edge *> m_eedges;
+
+ typedef hash_map<const exploded_node *, trimmed_node *> map_t;
+ map_t m_map_from_enode_to_tnode;
+};
+
+class trimmed_cluster : public cluster <tg_traits>
+{
+};
+
+} // namespace ana
+
+#endif /* GCC_ANALYZER_TRIMMED_GRAPH_H */
diff --git a/gcc/doc/analyzer.texi b/gcc/doc/analyzer.texi
index 005923178c2..3f7bcf3c115 100644
--- a/gcc/doc/analyzer.texi
+++ b/gcc/doc/analyzer.texi
@@ -320,22 +320,56 @@ feasible
@end itemize
Without state-merging, all paths in the exploded graph are feasible
-(in terms of constraints being satisified).
+(in terms of constraints being satisfied).
With state-merging, paths in the exploded graph can be infeasible.
We collate warnings and only emit them for the simplest path
e.g. for a bug in a utility function, with lots of routes to calling it,
we only emit the simplest path (which could be intraprocedural, if
-it can be reproduced without a caller). We apply a check that
-each duplicate warning's shortest path is feasible, rejecting any
-warnings for which the shortest path is infeasible (which could lead to
-false negatives). This check can be suppressed (for debugging purposes)
-using @option{-fno-analyzer-feasibility}.
-
-We use the shortest feasible @code{exploded_path} through the
-@code{exploded_graph} (a list of @code{exploded_edge *}) to build a
-@code{diagnostic_path} (a list of events for the diagnostic subsystem) -
-specifically a @code{checker_path}.
+it can be reproduced without a caller).
+
+We thus want to find the shortest feasible path through the exploded
+graph from the origin to the exploded node at which the diagnostic was
+saved. Unfortunately, if we simply find the shortest such path and
+check if it's feasible we might falsely reject the diagnostic, as there
+might be a longer path that is feasible. Examples include the cases
+where the diagnostic requires us to go at least once around a loop for a
+later condition to be satisfied, or where for a later condition to be
+satisfied we need to enter a suite of code that the simpler path skips.
+
+We attempt to find the shortest feasible path to each diagnostic by
+first constructing a ``trimmed graph'' from the exploded graph,
+containing only those nodes and edges from which there are paths to
+the target node, and using Dijkstra's algorithm to order the trimmed
+nodes by minimal distance to the target.
+
+We then use a worklist to iteratively build a ``feasible graph''
+(actually a tree), capturing the pertinent state along each path, in
+which every path to a ``feasible node'' is feasible by construction,
+restricting ourselves to the trimmed graph to ensure we stay on target,
+and ordering the worklist so that the first feasible path we find to the
+target node is the shortest possible path. Hence we start by trying the
+shortest possible path, but if that fails, we explore progressively
+longer paths, eventually trying iterations through loops. The
+exploration is captured in the feasible_graph, which can be dumped as a
+.dot file via @option{-fdump-analyzer-feasibility} to visualize the
+exploration. The indices of the feasible nodes show the order in which
+they were created. We effectively explore the tree of feasible paths in
+order of shortest path until we either find a feasible path to the
+target node, or hit a limit and give up.
+
+This is something of a brute-force approach, but the trimmed graph
+hopefully keeps the complexity manageable.
+
+This algorithm can be disabled (for debugging purposes) via
+@option{-fno-analyzer-feasibility}, which simply uses the shortest path,
+and notes if it is infeasible.
+
+The above gives us a shortest feasible @code{exploded_path} through the
+@code{exploded_graph} (a list of @code{exploded_edge *}). We use this
+@code{exploded_path} to build a @code{diagnostic_path} (a list of
+@strong{events} for the diagnostic subsystem) - specifically a
+@code{checker_path}.
Having built the @code{checker_path}, we prune it to try to eliminate
events that aren't relevant, to minimize how much the user has to read.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 4bd4f390ded..4a3c1e2fa0f 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -424,6 +424,7 @@ Objective-C and Objective-C++ Dialects}.
-fdump-analyzer-exploded-nodes @gol
-fdump-analyzer-exploded-nodes-2 @gol
-fdump-analyzer-exploded-nodes-3 @gol
+-fdump-analyzer-feasibility @gol
-fdump-analyzer-json @gol
-fdump-analyzer-state-purge @gol
-fdump-analyzer-supergraph @gol
@@ -9566,6 +9567,13 @@ Dump a textual representation of the ``exploded graph'' to
one dump file per node, to @file{@var{file}.eg-@var{id}.txt}.
This is typically a large number of dump files.
+@item -fdump-analyzer-feasibility
+@opindex dump-analyzer-feasibility
+Dump internal details about the analyzer's search for feasible paths.
+The details are written in a form suitable for viewing with GraphViz
+to filenames of the form @file{@var{file}.*.fg.dot} and
+@file{@var{file}.*.tg.dot}.
+
@item -fdump-analyzer-json
@opindex fdump-analyzer-json
Dump a compressed JSON representation of analyzer internals to
diff --git a/gcc/shortest-paths.h b/gcc/shortest-paths.h
index 40d2c2a015a..f544d7d456d 100644
--- a/gcc/shortest-paths.h
+++ b/gcc/shortest-paths.h
@@ -57,6 +57,7 @@ public:
enum shortest_path_sense sense);
path_t get_shortest_path (const node_t *other_node) const;
+ int get_shortest_distance (const node_t *other_node) const;
private:
const graph_t &m_graph;
@@ -199,4 +200,16 @@ get_shortest_path (const node_t *other_node) const
return result;
}
+/* Get the shortest distance...
+ SPS_FROM_GIVEN_ORIGIN: ...from given origin node to OTHER_NODE
+ SPS_TO_GIVEN_TARGET: ...from OTHER_NODE to given target node. */
+
+template <typename GraphTraits, typename Path_t>
+inline int
+shortest_paths<GraphTraits, Path_t>::
+get_shortest_distance (const node_t *other_node) const
+{
+ return m_dist[other_node->m_index];
+}
+
#endif /* GCC_SHORTEST_PATHS_H */
diff --git a/gcc/testsuite/gcc.dg/analyzer/dot-output.c b/gcc/testsuite/gcc.dg/analyzer/dot-output.c
index ff418b156c0..03405cdf4a0 100644
--- a/gcc/testsuite/gcc.dg/analyzer/dot-output.c
+++ b/gcc/testsuite/gcc.dg/analyzer/dot-output.c
@@ -2,7 +2,7 @@
by .dot. */
/* { dg-require-dot "" } */
-/* { dg-additional-options "-fdump-analyzer-callgraph -fdump-analyzer-exploded-graph -fdump-analyzer-state-purge -fdump-analyzer-supergraph" } */
+/* { dg-additional-options "-fdump-analyzer-callgraph -fdump-analyzer-exploded-graph -fdump-analyzer-state-purge -fdump-analyzer-supergraph -fdump-analyzer-feasibility" } */
#include <stdlib.h>
diff --git a/gcc/testsuite/gcc.dg/analyzer/feasibility-1.c b/gcc/testsuite/gcc.dg/analyzer/feasibility-1.c
index c96844467a5..83ec1cab58b 100644
--- a/gcc/testsuite/gcc.dg/analyzer/feasibility-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/feasibility-1.c
@@ -55,8 +55,7 @@ int test_6 (int a, int b)
{
if (!problem)
problem = 2;
- __analyzer_dump_path (); /* { dg-message "path" "" { xfail *-*-* } } */
- /* XFAIL is PR analyzer/96374. */
+ __analyzer_dump_path (); /* { dg-message "path" } */
}
return problem;
}
@@ -86,3 +85,16 @@ int test_6a (int a, int b, void *ptr)
}
return problem;
}
+
+/* After state-merging, the shortest path skips the loop,
+ but the shortest feasible path enters it. */
+
+void test_7 (int n)
+{
+ int entered_loop = 0;
+ int i;
+ for (i = 0; i < n; i++)
+ entered_loop = 1;
+ if (entered_loop)
+ __analyzer_dump_path (); /* { dg-message "path" } */
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c
index 1afc6df5da1..148429768cd 100644
--- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c
+++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-2.c
@@ -25,7 +25,5 @@ _nl_expand_alias (void)
++locale_alias_path;
if (start < locale_alias_path)
- __analyzer_dump_path (); /* { dg-message "path" "" { xfail *-*-* } } */
- /* XFAIL: PR analyzer/96374
- Use -fno-analyzer-feasibility to see the path. */
+ __analyzer_dump_path (); /* { dg-message "path" } */
}
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c
index a86483113ff..50d338855bc 100644
--- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c
+++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility-3.c
@@ -41,9 +41,7 @@ read_alias_file (const char *fname, char *cp)
{
FILE *fp;
- fp = fopen (fname, "r"); /* { dg-message "opened here" "" { xfail *-*-* } } */
- /* XFAIL: PR analyzer/96374
- Use -fno-analyzer-feasibility to see the path. */
+ fp = fopen (fname, "r"); /* { dg-message "opened here" } */
if (fp == NULL)
return 0;
@@ -54,9 +52,7 @@ read_alias_file (const char *fname, char *cp)
++cp;
if (cp[0] != '\0')
- return 42; /* { dg-warning "leak of FILE 'fp'" "" { xfail *-*-* } } */
- /* XFAIL: PR analyzer/96374
- Use -fno-analyzer-feasibility to see the path. */
+ return 42; /* { dg-warning "leak of FILE 'fp'" } */
fclose(fp);
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c
index 0d470d6602b..1a34d05174a 100644
--- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c
+++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias-feasibility.c
@@ -3,8 +3,6 @@
Adapted from intl/localealias.c, with all #includes removed. */
/* { dg-do "compile" } */
-/* { dg-additional-options "-fno-analyzer-feasibility" } */
-/* TODO: remove the need for this option. */
/* Handle aliases for locale names.
Copyright (C) 1995-1999, 2000-2001, 2003 Free Software Foundation, Inc.
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c
index 043e45f828e..88d0fc1fe43 100644
--- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c
+++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c
@@ -3,8 +3,8 @@
Adapted from intl/localealias.c, with all #includes removed. */
/* { dg-do "compile" } */
-/* { dg-additional-options "-Wno-analyzer-too-complex -fno-analyzer-feasibility" } */
-/* TODO: remove the need for these options. */
+/* { dg-additional-options "-Wno-analyzer-too-complex" } */
+/* TODO: remove the need for this option. */
/* { dg-require-effective-target alloca } */
/* Handle aliases for locale names.
diff --git a/gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c b/gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c
index 3d8f82ee290..bd1ab1e5476 100644
--- a/gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c
+++ b/gcc/testsuite/gcc.dg/analyzer/unknown-fns-4.c
@@ -10,6 +10,6 @@ void test (void)
got = 1;
else
if (got)
- __analyzer_dump_path (); /* { dg-message "path" "" { xfail *-*-* } } */
+ __analyzer_dump_path (); /* { dg-message "path" } */
}
}
--
2.26.2
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2021-03-11 23:07 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-03-11 23:06 [committed] analyzer: new implementation of shortest feasible path [PR96374] David Malcolm
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).