[committed] analyzer: eliminate dedupe_candidate [PR96374]

[committed] analyzer: eliminate dedupe_candidate [PR96374]

[David Malcolm]

In gcc/analyzer/diagnostic-manager.cc the code partitions
saved_diagnostic instances by dedupe_key, and tries to find the "best"
saved_diagnostic for each dedupe_key.

Ideally we would find the shortest feasible path for each
saved_diagnostic and pick the winner in each deduplication set.

Currently we merely approximate that by finding the shortest path for
each saved_diagnostic, and checking to see if it feasible, rejecting
the saved_diagnostic if it is not.  The "shortest path, or nothing if
it's infeasible" is not the same as the "shortest feasible path", and
this leads to false negatives, where we reject valid diagnostics,
tracked as PR analyzer/96374.

I have been attempting various fixes for this, but in doing so I
found that the existing structure of the code makes things unnecessarily
awkward: each dedupe_set had a a dedupe_candidate which stored the
best epath for that set, creating it from the shortest path when that
dedupe_candidate was constructed.

This patch eliminates the dedupe_candidate, instead storing the best
epath for each saved_diagnostic within the saved_diagnostic itself,
along with any feasibility_problem, and eliminating a redundant "status"
field.  The logic for finding the best epath is moved to a new
epath_finder::get_best_epath subroutine, introducing an epath_finder
class to give a place to cache state.

This patch merely copies over the existing logic to
epath_finder::get_best_epath, so no functional change is intended,
but the patch simplifies the logic and makes it much easier to
experiment with alternate implementations as I try to fix
PR analyzer/96374.

I attempted another version of this patch in which I added a dedupe_set
class and partitioned saved_diagnostics into them as the diagnostics were
added, but in this earlier iteration of the patch there were regressions
e.g. from gcc.dg/analyzer/zlib-4.c where 4 deduplication sets became 3.
The issue was that the deduplication logic needs source locations, which
need gimple statements, and the stmt_finder needs epaths to run.  Finding
the epaths needs the full egraph (as opposed to the egraph in its state
at the time when the diagnostic is saved).  Hence the partitioning needs to
happen after the egraph is fully explored.  I backed up the earlier patch
kit to:
  https://dmalcolm.fedorapeople.org/gcc/2021-02-23/feasibility-v0.3-relative-to-72d78655a91bb2f89ac4432cfd6374380d6f9987/

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
Pushed to trunk as r11-7410-ga505fad4dd4d93b6d642995d7df320aa40949568.

gcc/analyzer/ChangeLog:
	PR analyzer/96374
	* diagnostic-manager.cc (class epath_finder): New.
	(epath_finder::get_best_epath): New.
	(saved_diagnostic::saved_diagnostic): Update for replacement of
	m_state and m_epath_length with m_best_epath.
	(saved_diagnostic::~saved_diagnostic): Delete m_best_epath.
	(saved_diagnostic::to_json): Update "path_length" to be optional.
	(saved_diagnostic::calc_best_epath): New, based on
	dedupe_winners::add and parts of dedupe_key::dedupe_key.
	(saved_diagnostic::get_epath_length): New.
	(saved_diagnostic::add_duplicate): New.
	(dedupe_key::dedupe_key): Drop epath param.  Move invocation of
	stmt_finder to saved_diagnostic::calc_best_epath.
	(class dedupe_candidate): Delete.
	(class dedupe_hash_map_traits): Update to use saved_diagnotic *
	rather than dedupe_candidate * as the value_type/compare_type.
	(dedupe_winners::~dedupe_winners): Don't delete the values.
	(dedupe_winners::add): Convert param from shortest_exploded_paths to
	epath_finder.  Drop "eg" param.  Drop dedupe_candidate, moving
	path generation and feasiblity checking to
	epath_finder::get_best_epath.  Update winner-selection for move
	of epaths from dedupe_candidate to saved_diagnostic.
	(dedupe_winners::emit_best):  Update for removal of class
	dedupe_candidate.
	(dedupe_winners::map_t): Update to use saved_diagnotic * rather
	than dedupe_candidate * as the value_type/compare_type.
	(diagnostic_manager::emit_saved_diagnostics): Move
	shortest_exploded_paths instance into epath_finder and pass that
	around instead.
	(diagnostic_manager::emit_saved_diagnostic): Drop epath, stmt
	and num_dupes params, instead getting these from the
	saved_diagnostic.  Use correct location in inform_n call.
	* diagnostic-manager.h (class epath_finder): New forward decl.
	(saved_diagnostic::status): Drop enum.
	(saved_diagnostic::set_feasible): Drop.
	(saved_diagnostic::set_infeasible): Drop.
	(saved_diagnostic::get_status): Drop.
	(saved_diagnostic::calc_best_epath): New decl.
	(saved_diagnostic::get_best_epath): New decl.
	(saved_diagnostic::get_epath_length): New decl.
	(saved_diagnostic::set_epath_length): Drop.
	(saved_diagnostic::get_epath_length): Drop inline implementation.
	(saved_diagnostic::add_duplicate): New.
	(saved_diagnostic::get_num_dupes): New.
	(saved_diagnostic::m_d): Document ownership.
	(saved_diagnostic::m_trailing_eedge): Make const.
	(saved_diagnostic::m_status): Drop field.
	(saved_diagnostic::m_epath_length): Drop field.
	(saved_diagnostic::m_best_epath): New field.
	(saved_diagnostic::m_problem): Document ownership.
	(saved_diagnostic::m_duplicates): New field.
	(diagnostic_manager::emit_saved_diagnostic): Drop params epath,
	stmt, and num_dupes.
	* engine.cc (exploded_graph_annotator::print_saved_diagnostic):
	Update for changes to saved_diagnostic class.
	* exploded-graph.h (exploded_path::feasible_p): Drop unused
	overloaded decl.
---
 gcc/analyzer/diagnostic-manager.cc | 350 +++++++++++++++++------------
 gcc/analyzer/diagnostic-manager.h  |  44 ++--
 gcc/analyzer/engine.cc             |  55 ++---
 gcc/analyzer/exploded-graph.h      |   1 -
 4 files changed, 244 insertions(+), 206 deletions(-)

diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index cbb76d89e0d..f0f447f14dc 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -64,6 +64,104 @@ along with GCC; see the file COPYING3.  If not see
 
 namespace ana {
 
+/* State for finding the shortest feasible exploded_path for a
+   saved_diagnostic.
+   This is shared between all diagnostics, so that we avoid repeating work.  */
+
+class epath_finder
+{
+public:
+  epath_finder (const exploded_graph &eg)
+  : m_eg (eg),
+    m_sep (eg, eg.get_origin ())
+  {
+  }
+
+  logger *get_logger () const { return m_eg.get_logger (); }
+
+  exploded_path *get_best_epath (const exploded_node *enode,
+				 const char *desc,
+				 feasibility_problem **out_problem);
+
+private:
+  const exploded_graph &m_eg;
+  shortest_exploded_paths m_sep;
+};
+
+/* class epath_finder.  */
+
+/* Get the "best" exploded_path for reaching ENODE from the origin,
+   returning ownership of it to the caller.
+
+   Ideally we want to report the shortest feasible path.
+   Return NULL if we could not find a feasible path
+   (when flag_analyzer_feasibility is true).
+
+   If flag_analyzer_feasibility is false, then simply return the
+   shortest path.
+
+   Use DESC when logging.
+
+   Write any feasiblity_problem to *OUT_PROBLEM.  */
+
+exploded_path *
+epath_finder::get_best_epath (const exploded_node *enode,
+			      const char *desc,
+			      feasibility_problem **out_problem)
+{
+  logger *logger = get_logger ();
+  LOG_SCOPE (logger);
+
+  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);
+
+  /* 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.
+
+     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 (logger)
+	logger->log ("accepting %qs at EN: %i, SN: %i with feasible path",
+		     desc, enode->m_index,
+		     snode_idx);
+    }
+  else
+    {
+      if (flag_analyzer_feasibility)
+	{
+	  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;
+	}
+      else
+	{
+	  if (logger)
+	    logger->log ("accepting %qs at EN: %i, SN: %i"
+			 " despite infeasible path (due to %qs)",
+			 desc, enode->m_index,
+			 snode_idx,
+			 "-fno-analyzer-feasibility");
+	}
+    }
+
+  return epath;
+}
+
 /* class saved_diagnostic.  */
 
 /* saved_diagnostic's ctor.
@@ -83,7 +181,7 @@ saved_diagnostic::saved_diagnostic (const state_machine *sm,
   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_status (STATUS_NEW), m_epath_length (0), m_problem (NULL)
+  m_best_epath (NULL), m_problem (NULL)
 {
   gcc_assert (m_stmt || m_stmt_finder);
 
@@ -98,6 +196,7 @@ saved_diagnostic::~saved_diagnostic ()
 {
   delete m_stmt_finder;
   delete m_d;
+  delete m_best_epath;
   delete m_problem;
 }
 
@@ -121,7 +220,7 @@ saved_diagnostic::operator== (const saved_diagnostic &other) const
     "snode": int,
     "sval": optional str,
     "state": optional str,
-    "path_length": int,
+    "path_length": optional int,
     "pending_diagnostic": str}.  */
 
 json::object *
@@ -137,7 +236,8 @@ saved_diagnostic::to_json () const
     sd_obj->set ("sval", m_sval->to_json ());
   if (m_state)
     sd_obj->set ("state", m_state->to_json ());
-  sd_obj->set ("path_length", new json::integer_number (m_epath_length));
+  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 ()));
 
   /* We're not yet JSONifying the following fields:
@@ -152,6 +252,64 @@ saved_diagnostic::to_json () const
   return sd_obj;
 }
 
+/* Use PF to find the best exploded_path for this saved_diagnostic,
+   and store it in m_best_epath.
+   If m_stmt is still NULL, use m_stmt_finder on the epath to populate
+   m_stmt.
+   Return true if a best path was found.  */
+
+bool
+saved_diagnostic::calc_best_epath (epath_finder *pf)
+{
+  logger *logger = pf->get_logger ();
+  LOG_SCOPE (logger);
+  delete m_best_epath;
+  delete m_problem;
+  m_problem = NULL;
+
+  m_best_epath = pf->get_best_epath (m_enode, m_d->get_kind (),
+				     &m_problem);
+
+  /* Handle failure to find a feasible path.  */
+  if (m_best_epath == NULL)
+    {
+      gcc_assert (m_problem);
+      return false;
+    }
+
+  gcc_assert (m_best_epath);
+  if (m_stmt == NULL)
+    {
+      gcc_assert (m_stmt_finder);
+      m_stmt = m_stmt_finder->find_stmt (*m_best_epath);
+    }
+  gcc_assert (m_stmt);
+
+  return true;
+}
+
+unsigned
+saved_diagnostic::get_epath_length () const
+{
+  gcc_assert (m_best_epath);
+  return m_best_epath->length ();
+}
+
+/* Record that OTHER (and its duplicates) are duplicates
+   of this saved_diagnostic.  */
+
+void
+saved_diagnostic::add_duplicate (saved_diagnostic *other)
+{
+  gcc_assert (other);
+  m_duplicates.reserve (m_duplicates.length ()
+			+ other->m_duplicates.length ()
+			+ 1);
+  m_duplicates.splice (other->m_duplicates);
+  other->m_duplicates.truncate (0);
+  m_duplicates.safe_push (other);
+}
+
 /* 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 path be found to the diagnostic enode.  */
@@ -279,23 +437,15 @@ diagnostic_manager::to_json () const
 
 /* A class for identifying sets of duplicated pending_diagnostic.
 
-   We want to find the simplest dedupe_candidate amongst those that share a
+   We want to find the simplest saved_diagnostic amongst those that share a
    dedupe_key.  */
 
 class dedupe_key
 {
 public:
-  dedupe_key (const saved_diagnostic &sd,
-	      const exploded_path &epath)
+  dedupe_key (const saved_diagnostic &sd)
   : m_sd (sd), m_stmt (sd.m_stmt)
   {
-    /* Support deferring the choice of stmt until after an emission path has
-     been built, using an optional stmt_finder.  */
-    if (m_stmt == NULL)
-      {
-	gcc_assert (sd.m_stmt_finder);
-	m_stmt = sd.m_stmt_finder->find_stmt (epath);
-      }
     gcc_assert (m_stmt);
   }
 
@@ -344,41 +494,14 @@ public:
   const gimple *m_stmt;
 };
 
-/* The value of a slot for a dedupe_key within dedupe_winners:
-   the exploded_path for the best candidate for that key, and the
-   number of duplicates seen so far.  */
-
-class dedupe_candidate
-{
-public:
-  // has the exploded_path
-  dedupe_candidate (const shortest_exploded_paths &sp,
-		    saved_diagnostic *sd)
-  : m_epath (sp.get_shortest_path (sd->m_enode)),
-    m_num_dupes (0)
-  {
-  }
-
-  unsigned length () const { return m_epath.length (); }
-  const exploded_path &get_path () const { return m_epath; }
-
-  void add_duplicate () { m_num_dupes++; }
-  int get_num_dupes () const { return m_num_dupes; }
-
-private:
-  exploded_path m_epath;
-public:
-  int m_num_dupes;
-};
-
 /* Traits for use by dedupe_winners.  */
 
 class dedupe_hash_map_traits
 {
 public:
   typedef const dedupe_key *key_type;
-  typedef dedupe_candidate *value_type;
-  typedef dedupe_candidate *compare_type;
+  typedef saved_diagnostic *value_type;
+  typedef saved_diagnostic *compare_type;
 
   static inline hashval_t hash (const key_type &v)
   {
@@ -417,7 +540,7 @@ public:
 };
 
 /* A class for deduplicating diagnostics and finding (and emitting) the
-   best diagnostic within each partition.  */
+   best saved_diagnostic within each partition.  */
 
 class dedupe_winners
 {
@@ -426,113 +549,62 @@ public:
 
   ~dedupe_winners ()
   {
-    /* Delete all keys and candidates.  */
+    /* Delete all keys, but not the saved_diagnostics.  */
     for (map_t::iterator iter = m_map.begin ();
 	 iter != m_map.end ();
 	 ++iter)
-      {
-	delete (*iter).first;
-	delete (*iter).second;
-      }
+      delete (*iter).first;
   }
 
-  /* Determine an exploded_path for SD using SP and, if it's feasible,
-     determine if it's the best seen so far for its dedupe_key.
-     Retain the winner for each dedupe_key, and discard the rest.  */
+  /* Determine an exploded_path for SD using PF and, if it's feasible,
+     determine if SD is the best seen so far for its dedupe_key.
+     Record the winning SD for each dedupe_key.  */
 
   void add (logger *logger,
-	    const shortest_exploded_paths &sp,
-	    const exploded_graph *eg,
+	    epath_finder *pf,
 	    saved_diagnostic *sd)
   {
-    /* Build a dedupe_candidate for SD.
-       This uses SP to build an exploded_path.  */
-    dedupe_candidate *dc = new dedupe_candidate (sp, sd);
-
-    sd->set_epath_length (dc->length ());
-
-    /* Verify that the epath is feasible.
-       State-merging means that not every path in the epath corresponds
-       to a feasible one w.r.t. states.
-       Here we simply check each duplicate saved_diagnostic's
-       shortest_path, and reject any that aren't feasible.
-       This could introduce false negatives, as there could be longer
-       feasible paths within the egraph.  */
-    if (logger)
-      logger->log ("considering %qs at EN: %i, SN: %i",
-		   sd->m_d->get_kind (), sd->m_enode->m_index,
-		   sd->m_snode->m_index);
-
-    feasibility_problem *p = NULL;
-    if (dc->get_path ().feasible_p (logger, &p, m_engine, eg))
-      {
-	if (logger)
-	  logger->log ("accepting %qs at EN: %i, SN: %i with feasible path",
-		       sd->m_d->get_kind (), sd->m_enode->m_index,
-		       sd->m_snode->m_index);
-	sd->set_feasible ();
-      }
-    else
-      {
-	if (flag_analyzer_feasibility)
-	  {
-	    if (logger)
-	      logger->log ("rejecting %qs at EN: %i, SN: %i"
-			   " due to infeasible path",
-			   sd->m_d->get_kind (), sd->m_enode->m_index,
-			   sd->m_snode->m_index);
-	    sd->set_infeasible (p);
-	    delete dc;
-	    return;
-	  }
-	else
-	  {
-	    if (logger)
-	      logger->log ("accepting %qs at EN: %i, SN: %i"
-			   " despite infeasible path (due to %qs)",
-			   sd->m_d->get_kind (), sd->m_enode->m_index,
-			   sd->m_snode->m_index,
-			   "-fno-analyzer-feasibility");
-	    sd->set_infeasible (p);
-	  }
-      }
+    /* Determine best epath for SD.  */
+    if (!sd->calc_best_epath (pf))
+      return;
 
-    dedupe_key *key = new dedupe_key (*sd, dc->get_path ());
-    if (dedupe_candidate **slot = m_map.get (key))
+    dedupe_key *key = new dedupe_key (*sd);
+    if (saved_diagnostic **slot = m_map.get (key))
       {
 	if (logger)
 	  logger->log ("already have this dedupe_key");
 
-	(*slot)->add_duplicate ();
+	saved_diagnostic *cur_best_sd = *slot;
 
-	if (dc->length () < (*slot)->length ())
+	if (sd->get_epath_length () < cur_best_sd->get_epath_length ())
 	  {
 	    /* We've got a shorter path for the key; replace
-	       the current candidate.  */
+	       the current candidate, marking it as a duplicate of SD.  */
 	    if (logger)
 	      logger->log ("length %i is better than existing length %i;"
 			   " taking over this dedupe_key",
-			   dc->length (), (*slot)->length ());
-	    dc->m_num_dupes = (*slot)->get_num_dupes ();
-	    delete *slot;
-	    *slot = dc;
+			   sd->get_epath_length (),
+			   cur_best_sd->get_epath_length ());
+	    sd->add_duplicate (cur_best_sd);
+	    *slot = sd;
 	  }
 	else
-	  /* We haven't beaten the current best candidate;
-	     drop the new candidate.  */
+	  /* We haven't beaten the current best candidate; add SD
+	     as a duplicate of it.  */
 	  {
 	    if (logger)
 	      logger->log ("length %i isn't better than existing length %i;"
 			   " dropping this candidate",
-			   dc->length (), (*slot)->length ());
-	    delete dc;
+			   sd->get_epath_length (),
+			   cur_best_sd->get_epath_length ());
+	    cur_best_sd->add_duplicate (sd);
 	  }
 	delete key;
       }
     else
       {
 	/* This is the first candidate for this key.  */
-	m_map.put (key, dc);
+	m_map.put (key, sd);
 	if (logger)
 	  logger->log ("first candidate for this dedupe_key");
       }
@@ -557,27 +629,24 @@ public:
     /* Sort into a good emission order.  */
     keys.qsort (dedupe_key::comparator);
 
-    /* Emit the best candidate for each key.  */
+    /* Emit the best saved_diagnostics for each key.  */
     int i;
     const dedupe_key *key;
     FOR_EACH_VEC_ELT (keys, i, key)
       {
-	dedupe_candidate **slot = m_map.get (key);
+	saved_diagnostic **slot = m_map.get (key);
 	gcc_assert (*slot);
-	const dedupe_candidate &dc = **slot;
-
-	dm->emit_saved_diagnostic (eg, key->m_sd,
-				   dc.get_path (), key->m_stmt,
-				   dc.get_num_dupes ());
+	const saved_diagnostic *sd = *slot;
+	dm->emit_saved_diagnostic (eg, *sd);
       }
   }
 
 private:
   engine *m_engine;
 
-  /* This maps from each dedupe_key to a current best dedupe_candidate.  */
+  /* This maps from each dedupe_key to a current best saved_diagnostic.  */
 
-  typedef hash_map<const dedupe_key *, dedupe_candidate *,
+  typedef hash_map<const dedupe_key *, saved_diagnostic *,
 		   dedupe_hash_map_traits> map_t;
   map_t m_map;
 };
@@ -604,7 +673,7 @@ diagnostic_manager::emit_saved_diagnostics (const exploded_graph &eg)
     return;
 
   /* Compute the shortest_paths once, sharing it between all diagnostics.  */
-  shortest_exploded_paths sp (eg, eg.get_origin ());
+  epath_finder pf (eg);
 
   /* Iterate through all saved diagnostics, adding them to a dedupe_winners
      instance.  This partitions the saved diagnostics by dedupe_key,
@@ -615,39 +684,39 @@ diagnostic_manager::emit_saved_diagnostics (const exploded_graph &eg)
   int i;
   saved_diagnostic *sd;
   FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
-    best_candidates.add (get_logger (), sp, &eg, sd);
+    best_candidates.add (get_logger (), &pf, sd);
 
   /* For each dedupe-key, call emit_saved_diagnostic on the "best"
      saved_diagnostic.  */
   best_candidates.emit_best (this, eg);
 }
 
-/* Given a saved_diagnostic SD at STMT with feasible path EPATH through EG,
+/* Given a saved_diagnostic SD with m_best_epath through EG,
    create an checker_path of suitable events and use it to call
    SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic.  */
 
 void
 diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
-					   const saved_diagnostic &sd,
-					   const exploded_path &epath,
-					   const gimple *stmt,
-					   int num_dupes)
+					   const saved_diagnostic &sd)
 {
   LOG_SCOPE (get_logger ());
   log ("sd: %qs at SN: %i", sd.m_d->get_kind (), sd.m_snode->m_index);
-  log ("num dupes: %i", num_dupes);
+  log ("num dupes: %i", sd.get_num_dupes ());
 
   pretty_printer *pp = global_dc->printer->clone ();
 
+  const exploded_path *epath = sd.get_best_epath ();
+  gcc_assert (epath);
+
   /* Precompute all enodes from which the diagnostic is reachable.  */
-  path_builder pb (eg, epath, sd.get_feasibility_problem (), sd);
+  path_builder pb (eg, *epath, sd.get_feasibility_problem (), sd);
 
   /* 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 (pb, 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_sval, sd.m_state);
@@ -656,7 +725,7 @@ diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
      We use the final enode from the epath, which might be different from
      the sd.m_enode, as the dedupe code doesn't care about enodes, just
      snodes.  */
-  emission_path.add_final_event (sd.m_sm, epath.get_final_enode (), stmt,
+  emission_path.add_final_event (sd.m_sm, epath->get_final_enode (), sd.m_stmt,
 				 sd.m_var, sd.m_state);
 
   /* The "final" event might not be final; if the saved_diagnostic has a
@@ -667,7 +736,7 @@ diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
 
   emission_path.prepare_for_emission (sd.m_d);
 
-  location_t loc = get_stmt_location (stmt, sd.m_snode->m_fun);
+  location_t loc = get_stmt_location (sd.m_stmt, sd.m_snode->m_fun);
 
   /* Allow the pending_diagnostic to fix up the primary location
      and any locations for events.  */
@@ -681,8 +750,9 @@ diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
   auto_cfun sentinel (sd.m_snode->m_fun);
   if (sd.m_d->emit (&rich_loc))
     {
+      unsigned num_dupes = sd.get_num_dupes ();
       if (flag_analyzer_show_duplicate_count && num_dupes > 0)
-	inform_n (stmt->location, num_dupes,
+	inform_n (loc, num_dupes,
 		  "%i duplicate", "%i duplicates",
 		  num_dupes);
     }
diff --git a/gcc/analyzer/diagnostic-manager.h b/gcc/analyzer/diagnostic-manager.h
index 9fb952b4228..c55807851fd 100644
--- a/gcc/analyzer/diagnostic-manager.h
+++ b/gcc/analyzer/diagnostic-manager.h
@@ -23,18 +23,13 @@ along with GCC; see the file COPYING3.  If not see
 
 namespace ana {
 
+class epath_finder;
+
 /* A to-be-emitted diagnostic stored within diagnostic_manager.  */
 
 class saved_diagnostic
 {
 public:
-  enum status
-  {
-   STATUS_NEW,
-   STATUS_INFEASIBLE_PATH,
-   STATUS_FEASIBLE_PATH
-  };
-
   saved_diagnostic (const state_machine *sm,
 		    const exploded_node *enode,
 		    const supernode *snode, const gimple *stmt,
@@ -48,26 +43,17 @@ public:
 
   json::object *to_json () const;
 
-  void set_feasible ()
-  {
-    gcc_assert (m_status == STATUS_NEW);
-    m_status = STATUS_FEASIBLE_PATH;
-  }
-  void set_infeasible (feasibility_problem *p)
-  {
-    gcc_assert (m_status == STATUS_NEW);
-    m_status = STATUS_INFEASIBLE_PATH;
-    m_problem = p; // take ownership
-  }
   const feasibility_problem *get_feasibility_problem () const
   {
     return m_problem;
   }
 
-  enum status get_status () const { return m_status; }
+  bool calc_best_epath (epath_finder *pf);
+  const exploded_path *get_best_epath () const { return m_best_epath; }
+  unsigned get_epath_length () const;
 
-  void set_epath_length (unsigned length) { m_epath_length = length; }
-  unsigned get_epath_length () const { return m_epath_length; }
+  void add_duplicate (saved_diagnostic *other);
+  unsigned get_num_dupes () const { return m_duplicates.length (); }
 
   //private:
   const state_machine *m_sm;
@@ -78,15 +64,16 @@ public:
   tree m_var;
   const svalue *m_sval;
   state_machine::state_t m_state;
-  pending_diagnostic *m_d;
-  exploded_edge *m_trailing_eedge;
+  pending_diagnostic *m_d; // owned
+  const exploded_edge *m_trailing_eedge;
 
 private:
   DISABLE_COPY_AND_ASSIGN (saved_diagnostic);
 
-  enum status m_status;
-  unsigned m_epath_length;
-  feasibility_problem *m_problem;
+  exploded_path *m_best_epath; // owned
+  feasibility_problem *m_problem; // owned
+
+  auto_vec<const saved_diagnostic *> m_duplicates;
 };
 
 class path_builder;
@@ -126,10 +113,7 @@ public:
   void emit_saved_diagnostics (const exploded_graph &eg);
 
   void emit_saved_diagnostic (const exploded_graph &eg,
-			      const saved_diagnostic &sd,
-			      const exploded_path &epath,
-			      const gimple *stmt,
-			      int num_dupes);
+			      const saved_diagnostic &sd);
 
   unsigned get_num_diagnostics () const
   {
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 0cfa7d51f23..7580f0ba57a 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -4640,45 +4640,30 @@ private:
     pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
     gv->end_tdtr ();
     gv->begin_trtd ();
-    pp_printf (pp, "epath length: %i", sd->get_epath_length ());
+    if (sd->get_best_epath ())
+      pp_printf (pp, "epath length: %i", sd->get_epath_length ());
+    else
+      pp_printf (pp, "no best epath");
     gv->end_tdtr ();
-    switch (sd->get_status ())
+    if (const feasibility_problem *p = sd->get_feasibility_problem ())
       {
-      default:
-      case saved_diagnostic::STATUS_NEW:
-	gcc_unreachable ();
-	break;
-      case saved_diagnostic::STATUS_INFEASIBLE_PATH:
-	{
-	  gv->begin_trtd ();
-	  pp_printf (pp, "INFEASIBLE");
-	  gv->end_tdtr ();
-	  const feasibility_problem *p = sd->get_feasibility_problem ();
-	  gcc_assert (p);
-	  gv->begin_trtd ();
-	  pp_printf (pp, "at eedge %i: EN:%i -> EN:%i",
-		     p->m_eedge_idx,
-		     p->m_eedge.m_src->m_index,
-		     p->m_eedge.m_dest->m_index);
-	  pp_write_text_as_html_like_dot_to_stream (pp);
-	  gv->end_tdtr ();
-	  gv->begin_trtd ();
-	  p->m_eedge.m_sedge->dump (pp);
-	  pp_write_text_as_html_like_dot_to_stream (pp);
-	  gv->end_tdtr ();
-	  gv->begin_trtd ();
-	  pp_gimple_stmt_1 (pp, p->m_last_stmt, 0, (dump_flags_t)0);
-	  pp_write_text_as_html_like_dot_to_stream (pp);
-	  gv->end_tdtr ();
-	  /* Ideally we'd print p->m_model here; see the notes above about
-	     tooltips.  */
-	}
-	break;
-      case saved_diagnostic::STATUS_FEASIBLE_PATH:
 	gv->begin_trtd ();
-	pp_printf (pp, "FEASIBLE");
+	pp_printf (pp, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
+		   p->m_eedge_idx,
+		   p->m_eedge.m_src->m_index,
+		   p->m_eedge.m_dest->m_index);
+	pp_write_text_as_html_like_dot_to_stream (pp);
 	gv->end_tdtr ();
-	break;
+	gv->begin_trtd ();
+	p->m_eedge.m_sedge->dump (pp);
+	pp_write_text_as_html_like_dot_to_stream (pp);
+	gv->end_tdtr ();
+	gv->begin_trtd ();
+	pp_gimple_stmt_1 (pp, p->m_last_stmt, 0, (dump_flags_t)0);
+	pp_write_text_as_html_like_dot_to_stream (pp);
+	gv->end_tdtr ();
+	/* Ideally we'd print p->m_model here; see the notes above about
+	   tooltips.  */
       }
     pp_printf (pp, "</TABLE>");
     gv->end_tdtr ();
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index 894529269fc..45943093434 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -880,7 +880,6 @@ public:
   void dump (FILE *fp) const;
   void dump () const;
 
-  bool feasible_p (logger *logger, feasibility_problem **out) const;
   bool feasible_p (logger *logger, feasibility_problem **out,
 		    engine *eng, const exploded_graph *eg) const;
 
-- 
2.26.2

Re: [committed] analyzer: eliminate dedupe_candidate [PR96374]

[Andreas Schwab]

I'm getting this link failure for all compilers:

analyzer/diagnostic-manager.o: In function `ana::diagnostic_manager::emit_saved_diagnostics(ana::exploded_graph const&)':
diagnostic-manager.cc:(.text+0xd350): undefined reference to `ana::exploded_path::exploded_path(ana::exploded_path const&)'

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

[PATCH] analyzer: implement exploded_path copy ctor

[David Malcolm]

On Fri, 2021-02-26 at 10:24 +0100, Andreas Schwab wrote:
> I'm getting this link failure for all compilers:
> 
> analyzer/diagnostic-manager.o: In function
> `ana::diagnostic_manager::emit_saved_diagnostics(ana::exploded_graph
> const&)':
> diagnostic-manager.cc:(.text+0xd350): undefined reference to
> `ana::exploded_path::exploded_path(ana::exploded_path const&)'
> 
> Andreas.

Sorry about the breakage.

What compiler are you using?
I'm not seeing this (with gcc 4.8.5, or gcc 10.2.1).

Does the following patch fix the build for you?

gcc/analyzer/ChangeLog:
	* engine.cc (exploded_path::exploded_path): New copy-ctor.
	* exploded-graph.h (exploded_path::operator=): Drop decl.
---
 gcc/analyzer/engine.cc        | 9 +++++++++
 gcc/analyzer/exploded-graph.h | 1 -
 2 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 7580f0ba57a..76e2069c935 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -3411,6 +3411,15 @@ exploded_graph::to_json () const
   return egraph_obj;
 }
 
+exploded_path::exploded_path (const exploded_path &other)
+: m_edges (other.m_edges.length ())
+{
+  int i;
+  const exploded_edge *eedge;
+  FOR_EACH_VEC_ELT (other.m_edges, i, eedge)
+    m_edges.quick_push (eedge);
+}
+
 /* Look for the last use of SEARCH_STMT within this path.
    If found write the edge's index to *OUT_IDX and return true, otherwise
    return false.  */
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index 45943093434..bcf58557de2 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -867,7 +867,6 @@ class exploded_path
 public:
   exploded_path () : m_edges () {}
   exploded_path (const exploded_path &other);
-  exploded_path & operator= (const exploded_path &other);
 
   unsigned length () const { return m_edges.length (); }
 
-- 
2.26.2

Re: [PATCH] analyzer: implement exploded_path copy ctor

[Andreas Schwab]

On Feb 26 2021, David Malcolm wrote:

> What compiler are you using?

gcc 5.3.1

> Does the following patch fix the build for you?

Yes, it does.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: [PATCH] analyzer: implement exploded_path copy ctor

[David Malcolm]

On Fri, 2021-02-26 at 19:33 +0100, Andreas Schwab wrote:
> On Feb 26 2021, David Malcolm wrote:
> 
> > What compiler are you using?
> 
> gcc 5.3.1
> 
> > Does the following patch fix the build for you?
> 
> Yes, it does.

Thanks.  I've pushed the patch to trunk.

Sorry again for the breakage.

Dave