analyzer: fix false positives from -Wanalyzer-infinite-recursion [PR108524]

Reject -Wanalyzer-infinite-recursion diagnostics in which control flow
has been affected by conjured_svalues between the initial call to a
function and the subsequent entry to that function.  This prevents false
positives such as in qemu's recursive JSON parser where function calls are
changing state in the rest of the program (e.g. consuming tokens), despite
the modelled state being effectively identical at both nested entrypoints.

gcc/analyzer/ChangeLog:
	PR analyzer/108524
	* analyzer.h (class feasible_node): New forward decl.
	* diagnostic-manager.cc (epath_finder::get_best_epath): Add "pd"
	param.
	(epath_finder::explore_feasible_paths): Likewise.
	(epath_finder::process_worklist_item): Likewise.  Use it to call
	pending_diagnostic::check_valid_fpath_p on the final fpath to
	give pending_diagnostic a way to add additional restrictions on
	feasibility.
	(saved_diagnostic::calc_best_epath): Pass pending_diagnostic to
	epath_finder::get_best_epath.
	* infinite-recursion.cc: Include "analyzer/feasible-graph.h".
	(infinite_recursion_diagnostic::check_valid_fpath_p): New.
	(infinite_recursion_diagnostic::fedge_uses_conjured_svalue_p): New.
	(infinite_recursion_diagnostic::expr_uses_conjured_svalue_p): New.
	* pending-diagnostic.h (pending_diagnostic::check_valid_fpath_p):
	New vfunc.

gcc/testsuite/ChangeLog:
	PR analyzer/108524
	* gcc.dg/analyzer/infinite-recursion-pr108524-1.c: New test.
	* gcc.dg/analyzer/infinite-recursion-pr108524-2.c: New test.
	* gcc.dg/analyzer/infinite-recursion-pr108524-qobject-json-parser.c:
	New test.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

4 files changed, 132 insertions, 5 deletions

diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h
index 8f79e4b..a161952 100644
--- a/gcc/analyzer/analyzer.h
+++ b/gcc/analyzer/analyzer.h
@@ -126,6 +126,8 @@ class call_summary_replay;
 struct per_function_data;
 struct interesting_t;
 
+class feasible_node;
+
 /* Forward decls of functions.  */
 
 extern void dump_tree (pretty_printer *pp, tree t);
diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index 1227d6c..4f036a6 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -88,6 +88,7 @@ public:
 
   std::unique_ptr<exploded_path>
   get_best_epath (const exploded_node *target_enode,
+		  const pending_diagnostic &pd,
 		  const char *desc, unsigned diag_idx,
 		  std::unique_ptr<feasibility_problem> *out_problem);
 
@@ -96,12 +97,14 @@ private:
 
   std::unique_ptr<exploded_path>
   explore_feasible_paths (const exploded_node *target_enode,
+			  const pending_diagnostic &pd,
 			  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,
+			 const pending_diagnostic &pd,
 			 unsigned diag_idx,
 			 std::unique_ptr<exploded_path> *out_best_path) const;
   void dump_trimmed_graph (const exploded_node *target_enode,
@@ -138,6 +141,7 @@ private:
 
 std::unique_ptr<exploded_path>
 epath_finder::get_best_epath (const exploded_node *enode,
+			      const pending_diagnostic &pd,
 			      const char *desc, unsigned diag_idx,
 			      std::unique_ptr<feasibility_problem> *out_problem)
 {
@@ -161,7 +165,7 @@ epath_finder::get_best_epath (const exploded_node *enode,
       if (logger)
 	logger->log ("trying to find shortest feasible path");
       if (std::unique_ptr<exploded_path> epath
-	    = explore_feasible_paths (enode, desc, diag_idx))
+	    = explore_feasible_paths (enode, pd, desc, diag_idx))
 	{
 	  if (logger)
 	    logger->log ("accepting %qs at EN: %i, SN: %i (sd: %i)"
@@ -374,6 +378,7 @@ private:
 
 std::unique_ptr<exploded_path>
 epath_finder::explore_feasible_paths (const exploded_node *target_enode,
+				      const pending_diagnostic &pd,
 				      const char *desc, unsigned diag_idx)
 {
   logger *logger = get_logger ();
@@ -415,8 +420,8 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
   {
     auto_checking_feasibility sentinel (mgr);
 
-    while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx,
-				  &best_path))
+    while (process_worklist_item (&worklist, tg, &fg, target_enode, pd,
+				  diag_idx, &best_path))
       {
 	/* Empty; the work is done within process_worklist_item.  */
       }
@@ -449,7 +454,10 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
    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.  */
+   to TARGET_ENODE.
+   Use PD to provide additional restrictions on feasibility of
+   the final path in the feasible_graph before converting to
+   an exploded_path.  */
 
 bool
 epath_finder::
@@ -457,6 +465,7 @@ process_worklist_item (feasible_worklist *worklist,
 		       const trimmed_graph &tg,
 		       feasible_graph *fg,
 		       const exploded_node *target_enode,
+		       const pending_diagnostic &pd,
 		       unsigned diag_idx,
 		       std::unique_ptr<exploded_path> *out_best_path) const
 {
@@ -514,6 +523,13 @@ process_worklist_item (feasible_worklist *worklist,
 			     " (length: %i)",
 			     target_enode->m_index, diag_idx,
 			     succ_fnode->get_path_length ());
+	      if (!pd.check_valid_fpath_p (succ_fnode))
+		{
+		  if (logger)
+		    logger->log ("rejecting feasible path due to"
+				 " pending_diagnostic");
+		  return false;
+		}
 	      *out_best_path = fg->make_epath (succ_fnode);
 	      if (flag_dump_analyzer_feasibility)
 		dump_feasible_path (target_enode, diag_idx, *fg, *succ_fnode);
@@ -808,7 +824,7 @@ saved_diagnostic::calc_best_epath (epath_finder *pf)
   LOG_SCOPE (logger);
   m_problem = NULL;
 
-  m_best_epath = pf->get_best_epath (m_enode, m_d->get_kind (), m_idx,
+  m_best_epath = pf->get_best_epath (m_enode, *m_d, m_d->get_kind (), m_idx,
 				     &m_problem);
 
   /* Handle failure to find a feasible path.  */
diff --git a/gcc/analyzer/infinite-recursion.cc b/gcc/analyzer/infinite-recursion.cc
index c4e85bf..8d101d1 100644
--- a/gcc/analyzer/infinite-recursion.cc
+++ b/gcc/analyzer/infinite-recursion.cc
@@ -62,6 +62,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "analyzer/exploded-graph.h"
 #include "make-unique.h"
 #include "analyzer/checker-path.h"
+#include "analyzer/feasible-graph.h"
 
 /* A subclass of pending_diagnostic for complaining about suspected
    infinite recursion.  */
@@ -199,7 +200,106 @@ public:
 	NULL, NULL, NULL));
   }
 
+  /* Reject paths in which conjured svalues have affected control flow
+     since m_prev_entry_enode.  */
+
+  bool check_valid_fpath_p (const feasible_node *final_fnode)
+    const final override
+  {
+    /* Reject paths in which calls with unknown side effects have occurred
+       since m_prev_entry_enode.
+       Find num calls with side effects.  Walk backward until we reach the
+       pref */
+    gcc_assert (final_fnode->get_inner_node () == m_new_entry_enode);
+
+    /* FG is actually a tree.  Walk backwards from FINAL_FNODE until we
+       reach the prev_entry_enode (or the origin).  */
+    const feasible_node *iter_fnode = final_fnode;
+    while (iter_fnode->get_inner_node ()->m_index != 0)
+      {
+	gcc_assert (iter_fnode->m_preds.length () == 1);
+
+	feasible_edge *pred_fedge
+	  = static_cast <feasible_edge *> (iter_fnode->m_preds[0]);
+
+	/* Determine if conjured svalues have affected control flow
+	   since the prev entry node.  */
+	if (fedge_uses_conjured_svalue_p (pred_fedge))
+	  /* If so, then reject this diagnostic.  */
+	  return false;
+	iter_fnode = static_cast <feasible_node *> (pred_fedge->m_src);
+	if (iter_fnode->get_inner_node () == m_prev_entry_enode)
+	  /* Accept this diagnostic.  */
+	  return true;
+    }
+
+    /* We shouldn't get here; if we do, reject the diagnostic.  */
+    gcc_unreachable ();
+    return false;
+  }
+
 private:
+  /* Return true iff control flow along FEDGE was affected by
+     a conjured_svalue.  */
+  static bool fedge_uses_conjured_svalue_p (feasible_edge *fedge)
+  {
+    const exploded_edge *eedge = fedge->get_inner_edge ();
+    const superedge *sedge = eedge->m_sedge;
+    if (!sedge)
+      return false;
+    const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
+    if (!cfg_sedge)
+      return false;
+    const gimple *last_stmt = sedge->m_src->get_last_stmt ();
+    if (!last_stmt)
+      return false;
+
+    const feasible_node *dst_fnode
+      = static_cast<const feasible_node *> (fedge->m_dest);
+    const region_model &model = dst_fnode->get_state ().get_model ();
+
+    if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt))
+      {
+	if (expr_uses_conjured_svalue_p (model, gimple_cond_lhs (cond_stmt)))
+	  return true;
+	if (expr_uses_conjured_svalue_p (model, gimple_cond_rhs (cond_stmt)))
+	  return true;
+      }
+    else if (const gswitch *switch_stmt
+	       = dyn_cast <const gswitch *> (last_stmt))
+      {
+	if (expr_uses_conjured_svalue_p (model,
+					 gimple_switch_index (switch_stmt)))
+	  return true;
+      }
+    return false;
+  }
+
+  /* Return true iff EXPR is affected by a conjured_svalue.  */
+  static bool expr_uses_conjured_svalue_p (const region_model &model,
+					   tree expr)
+  {
+    class conjured_svalue_finder : public visitor
+    {
+    public:
+      conjured_svalue_finder () : m_found_conjured_svalues (false)
+      {
+      }
+      void
+      visit_conjured_svalue (const conjured_svalue *) final override
+      {
+	m_found_conjured_svalues = true;
+      }
+
+      bool m_found_conjured_svalues;
+    };
+
+    const svalue *sval = model.get_rvalue (expr, NULL);
+    conjured_svalue_finder v;
+    sval->accept (&v);
+    return v.m_found_conjured_svalues;
+  }
+
   const exploded_node *m_prev_entry_enode;
   const exploded_node *m_new_entry_enode;
   tree m_callee_fndecl;
diff --git a/gcc/analyzer/pending-diagnostic.h b/gcc/analyzer/pending-diagnostic.h
index de79890..b919d5b 100644
--- a/gcc/analyzer/pending-diagnostic.h
+++ b/gcc/analyzer/pending-diagnostic.h
@@ -347,6 +347,15 @@ class pending_diagnostic
   {
     /* Default no-op implementation.  */
   }
+
+  /* Vfunc to give diagnostic subclasses the opportunity to reject diagnostics
+     by imposing their own additional feasibility checks on the path to a
+     given feasible_node.  */
+  virtual bool check_valid_fpath_p (const feasible_node *) const
+  {
+    /* Default implementation: accept this path.  */
+    return true;
+  }
 };
 
 /* A template to make it easier to make subclasses of pending_diagnostic.