analyzer: new warning: -Wanalyzer-infinite-loop [PR106147]

This patch implements a new analyzer warning: -Wanalyzer-infinite-loop.

It works by examining the exploded graph once the latter has been
fully built.  It attempts to detect cycles in the exploded graph in
which:
- no externally visible work occurs
- no escape is possible from the cycle once it has been entered
- the program state is "sufficiently concrete" at each step:
  - no unknown activity could be occurring
  - the worklist was fully drained for each enode in the cycle
    i.e. every enode in the cycle is processed

For example, it correctly complains about this bogus "for" loop:

  int sum = 0;
  for (struct node *iter = n; iter; iter->next)
    sum += n->val;
  return sum;

like this:

infinite-loop-linked-list.c: In function ‘for_loop_noop_next’:
infinite-loop-linked-list.c:110:31: warning: infinite loop [CWE-835] [-Wanalyzer-infinite-loop]
  110 |   for (struct node *iter = n; iter; iter->next)
      |                               ^~~~
  ‘for_loop_noop_next’: events 1-5
    |
    |  110 |   for (struct node *iter = n; iter; iter->next)
    |      |                               ^~~~
    |      |                               |
    |      |                               (1) infinite loop here
    |      |                               (2) when ‘iter’ is non-NULL: always following ‘true’ branch...
    |      |                               (5) ...to here
    |  111 |     sum += n->val;
    |      |     ~~~~~~~~~~~~~
    |      |         |   |
    |      |         |   (3) ...to here
    |      |         (4) looping back...
    |

gcc/ChangeLog:
	PR analyzer/106147
	* Makefile.in (ANALYZER_OBJS): Add analyzer/infinite-loop.o.
	* doc/invoke.texi: Add -fdump-analyzer-infinite-loop and
	-Wanalyzer-infinite-loop.  Add missing CWE link for
	-Wanalyzer-infinite-recursion.
	* timevar.def (TV_ANALYZER_INFINITE_LOOPS): New.

gcc/analyzer/ChangeLog:
	PR analyzer/106147
	* analyzer.opt (Wanalyzer-infinite-loop): New option.
	(fdump-analyzer-infinite-loop): New option.
	* checker-event.h (start_cfg_edge_event::get_desc): Drop "final".
	(start_cfg_edge_event::maybe_describe_condition): Convert from
	private to protected.
	* checker-path.h (checker_path::get_logger): New.
	* diagnostic-manager.cc (process_worklist_item): Update for
	new context param of maybe_update_for_edge.
	* engine.cc
	(impl_region_model_context::impl_region_model_context): Add
	out_could_have_done_work param to both ctors and use it to
	initialize mm_out_could_have_done_work.
	(impl_region_model_context::maybe_did_work): New vfunc
	implementation.
	(exploded_node::on_stmt): Add out_could_have_done_work param and
	pass to ctxt ctor.
	(exploded_node::on_stmt_pre): Treat setjmp and longjmp as "doing
	work".
	(exploded_node::on_longjmp): Likewise.
	(exploded_edge::exploded_edge): Add "could_do_work" param and use
	it to initialize m_could_do_work_p.
	(exploded_edge::dump_dot_label): Add result of could_do_work_p.
	(exploded_graph::add_function_entry): Mark edge as doing no work.
	(exploded_graph::add_edge): Add "could_do_work" param and pass to
	exploded_edge ctor.
	(add_tainted_args_callback): Treat as doing no work.
	(exploded_graph::process_worklist): Likewise when merging nodes.
	(maybe_process_run_of_before_supernode_enodes::item): Likewise.
	(exploded_graph::maybe_create_dynamic_call): Likewise.
	(exploded_graph::process_node): Likewise for phi nodes.
	Pass in a "could_have_done_work" bool when handling stmts and use
	when creating edges.  Assume work is done at bifurcation.
	(exploded_path::feasible_p): Update for new context param of
	maybe_update_for_edge.
	(feasibility_state::feasibility_state): New ctor.
	(feasibility_state::operator=): New.
	(feasibility_state::maybe_update_for_edge): Add ctxt param and use
	it.  Fix missing newline when logging state.
	(impl_run_checkers): Call exploded_graph::detect_infinite_loops.
	* exploded-graph.h
	(impl_region_model_context::impl_region_model_context): Add
	out_could_have_done_work param to both ctors.
	(impl_region_model_context::maybe_did_work): New decl.
	(impl_region_model_context::checking_for_infinite_loop_p): New.
	(impl_region_model_context::on_unusable_in_infinite_loop): New.
	(impl_region_model_context::m_out_could_have_done_work): New
	field.
	(exploded_node::on_stmt): Add "out_could_have_done_work" param.
	(exploded_edge::exploded_edge): Add "could_do_work" param.
	(exploded_edge::could_do_work_p): New accessor.
	(exploded_edge::m_could_do_work_p): New field.
	(exploded_graph::add_edge): Add "could_do_work" param.
	(exploded_graph::detect_infinite_loops): New decl.
	(feasibility_state::feasibility_state): New ctor.
	(feasibility_state::operator=): New decl.
	(feasibility_state::maybe_update_for_edge): Add ctxt param.
	* infinite-loop.cc: New file.
	* program-state.cc (program_state::on_edge): Log the rejected
	constraint when region_model::maybe_update_for_edge fails.
	* region-model.cc (region_model::on_assignment): Treat any writes
	other than to the stack as "doing work".
	(region_model::on_stmt_pre): Treat all asm stmts as "doing work".
	(region_model::on_call_post): Likewise for all calls to functions
	with unknown side effects.
	(region_model::handle_phi): Add svals_changing_meaning param.
	Mark widening svalue in phi nodes as changing meaning.
	(unusable_in_infinite_loop_constraint_p): New.
	(region_model::add_constraint): If we're checking for an infinite
	loop, bail out on unusable svalues, or if we don't have a definite
	true/false for the constraint.
	(region_model::update_for_phis): Gather all svalues changing
	meaning in phi nodes, and purge constraints involving them.
	(region_model::replay_call_summary): Treat all call summaries as
	doing work.
	(region_model::can_merge_with_p): Purge constraints involving
	svalues that change meaning.
	(model_merger::on_widening_reuse): New.
	(test_iteration_1): Likewise.
	(selftest::test_iteration_1): Remove assertion that model6 "knows"
	that i < 157.
	* region-model.h (region_model::handle_phi): Add
	svals_changing_meaning param
	(region_model_context::maybe_did_work): New pure virtual func.
	(region_model_context::checking_for_infinite_loop_p): Likewise.
	(region_model_context::on_unusable_in_infinite_loop): Likewise.
	(noop_region_model_context::maybe_did_work): Implement.
	(noop_region_model_context::checking_for_infinite_loop_p):
	Likewise.
	(noop_region_model_context::on_unusable_in_infinite_loop):
	Likewise.
	(region_model_context_decorator::maybe_did_work): Implement.
	(region_model_context_decorator::checking_for_infinite_loop_p):
	Likewise.
	(region_model_context_decorator::on_unusable_in_infinite_loop):
	Likewise.
	(model_merger::on_widening_reuse): New decl.
	(model_merger::m_svals_changing_meaning): New field.
	* sm-signal.cc (register_signal_handler::impl_transition): Assume
	the edge "does work".
	* supergraph.cc (supernode::get_start_location): Use CFG edge's
	goto_locus if available.
	(supernode::get_end_location): Likewise.
	(cfg_superedge::dump_label_to_pp): Dump edges with a "goto_locus"
	* supergraph.h (cfg_superedge::get_goto_locus): New.
	* svalue.cc (svalue::can_merge_p): Call on_widening_reuse for
	widening values.
	(involvement_visitor::visit_widening_svalue): New.
	(svalue::involves_p): Update assertion to allow widening svalues.

gcc/testsuite/ChangeLog:
	PR analyzer/106147
	* c-c++-common/analyzer/gzio-2.c: Add dg-warning for infinite
	loop, marked as xfail.
	* c-c++-common/analyzer/infinite-loop-2.c: New test.
	* c-c++-common/analyzer/infinite-loop-4.c: New test.
	* c-c++-common/analyzer/infinite-loop-crc32c.c: New test.
	* c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c:
	New test.
	* c-c++-common/analyzer/infinite-loop-doom-v_video.c: New test.
	* c-c++-common/analyzer/infinite-loop-g_error.c: New test.
	* c-c++-common/analyzer/infinite-loop-linked-list.c: New test.
	* c-c++-common/analyzer/infinite-recursion-inlining.c: Add
	dg-warning directives for infinite loop.
	* c-c++-common/analyzer/inlining-4-multiline.c: Update expected
	paths for event 5 having a location.
	* gcc.dg/analyzer/boxed-malloc-1.c: Add dg-warning for infinite
	loop.
	* gcc.dg/analyzer/data-model-20.c: Likewise.  Add comment about
	suspect code, and create...
	* gcc.dg/analyzer/data-model-20a.c: ...this new test by cleaning
	it up.
	* gcc.dg/analyzer/edges-1.c: Add a placeholder statement to avoid
	the "...to here" from the if stmt occurring at the "while", and
	thus being treated as a bogus event.
	* gcc.dg/analyzer/explode-2a.c: Add dg-warning for infinite loop.
	* gcc.dg/analyzer/infinite-loop-1.c: New test.
	* gcc.dg/analyzer/malloc-1.c: Add dg-warning for infinite loop.
	* gcc.dg/analyzer/out-of-bounds-coreutils.c: Add TODO.
	* gcc.dg/analyzer/paths-4.c: Add dg-warning for infinite loop.
	* gcc.dg/analyzer/pr103892.c: Likewise.
	* gcc.dg/analyzer/pr93546.c: Likewise.

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

1 files changed, 565 insertions, 0 deletions

diff --git a/gcc/analyzer/infinite-loop.cc b/gcc/analyzer/infinite-loop.cc
new file mode 100644
index 0000000..771d698
--- /dev/null
+++ b/gcc/analyzer/infinite-loop.cc
@@ -0,0 +1,565 @@
+/* Detection of infinite loops.
+   Copyright (C) 2022-2023 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"
+#define INCLUDE_MEMORY
+#define INCLUDE_VECTOR
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "fold-const.h"
+#include "gcc-rich-location.h"
+#include "alloc-pool.h"
+#include "fibonacci_heap.h"
+#include "shortest-paths.h"
+#include "diagnostic-core.h"
+#include "diagnostic-event-id.h"
+#include "diagnostic-path.h"
+#include "diagnostic-metadata.h"
+#include "function.h"
+#include "pretty-print.h"
+#include "sbitmap.h"
+#include "bitmap.h"
+#include "tristate.h"
+#include "ordered-hash-map.h"
+#include "selftest.h"
+#include "json.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/analyzer-logging.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 "analyzer/sm.h"
+#include "analyzer/pending-diagnostic.h"
+#include "analyzer/diagnostic-manager.h"
+#include "cfg.h"
+#include "basic-block.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-pretty-print.h"
+#include "cgraph.h"
+#include "digraph.h"
+#include "analyzer/supergraph.h"
+#include "analyzer/program-state.h"
+#include "analyzer/exploded-graph.h"
+#include "analyzer/checker-path.h"
+#include "analyzer/feasible-graph.h"
+#include "make-unique.h"
+
+/* A bundle of data characterizing a particular infinite loop
+   identified within the exploded graph.  */
+
+struct infinite_loop
+{
+  infinite_loop (const exploded_node &enode,
+		location_t loc,
+		std::vector<const exploded_edge *> eedges,
+		logger *logger)
+  : m_enode (enode),
+    m_loc (loc),
+    m_eedge_vec (eedges)
+  {
+    LOG_SCOPE (logger);
+    if (logger)
+      {
+	logger->start_log_line ();
+	logger->log_partial ("infinite loop: EN: %i", m_enode.m_index);
+	for (auto eedge : m_eedge_vec)
+	  {
+	    logger->log_partial (" ->");
+	    if (const superedge *sedge = eedge->m_sedge)
+	      {
+		sedge->dump_label_to_pp (logger->get_printer (), false);
+	      }
+	    logger->log_partial (" EN: %i", eedge->m_dest->m_index);
+	  }
+	logger->end_log_line ();
+      }
+  }
+
+  bool
+  operator== (const infinite_loop &other) const
+  {
+    /* Compare underlying supernode, rather than enodes, so that
+       we don't get duplicates in functions that are called from
+       elsewhere.  */
+    return (m_enode.get_supernode () == other.m_enode.get_supernode ()
+	    && m_loc == other.m_loc);
+  }
+
+  const exploded_node &m_enode;
+  location_t m_loc;
+  std::vector<const exploded_edge *> m_eedge_vec;
+};
+
+/* A custom subclass of start_cfg_edge_event that rewords the
+   message to indicate that the CFG edge is *always* taken on
+   subsequent iterations, assuming it's been taken once. */
+
+class perpetual_start_cfg_edge_event : public start_cfg_edge_event
+{
+public:
+  perpetual_start_cfg_edge_event (const exploded_edge &eedge,
+				  const event_loc_info &loc_info)
+  : start_cfg_edge_event (eedge, loc_info)
+  {
+  }
+
+  label_text get_desc (bool can_colorize) const final override
+  {
+    bool user_facing = !flag_analyzer_verbose_edges;
+    label_text edge_desc (m_sedge->get_description (user_facing));
+    if (user_facing)
+      {
+	if (edge_desc.get () && strlen (edge_desc.get ()) > 0)
+	  {
+	    label_text cond_desc = maybe_describe_condition (can_colorize);
+	    label_text result;
+	    if (cond_desc.get ())
+	      return make_label_text
+		(can_colorize,
+		 "%s: always following %qs branch...",
+		 cond_desc.get (), edge_desc.get ());
+	    else
+	      return make_label_text
+		(can_colorize,
+		 "if it ever follows %qs branch, it will always do so...",
+		 edge_desc.get ());
+	  }
+      }
+    return start_cfg_edge_event::get_desc (can_colorize);
+  }
+};
+
+/* A subclass of pending_diagnostic for complaining about suspected
+   infinite loops.  */
+
+class infinite_loop_diagnostic
+: public pending_diagnostic_subclass<infinite_loop_diagnostic>
+{
+public:
+  infinite_loop_diagnostic (std::unique_ptr<infinite_loop> inf_loop)
+    : m_inf_loop (std::move (inf_loop))
+  {
+    gcc_assert (m_inf_loop != nullptr);
+  }
+
+  const char *get_kind () const final override
+  {
+    return "infinite_loop_diagnostic";
+  }
+
+  bool operator== (const infinite_loop_diagnostic &other) const
+  {
+    return *m_inf_loop == *other.m_inf_loop;
+  }
+
+  int get_controlling_option () const final override
+  {
+    return OPT_Wanalyzer_infinite_loop;
+  }
+
+  bool emit (rich_location *rich_loc, logger *) final override
+  {
+    /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */
+    diagnostic_metadata m;
+    m.add_cwe (835);
+    return warning_meta (rich_loc, m, get_controlling_option (),
+			 "infinite loop");
+  }
+
+  bool maybe_add_custom_events_for_superedge (const exploded_edge &,
+					      checker_path *)
+    final override
+  {
+    /* Don't add any regular events; instead we add them after pruning as
+       part of the "final" warning.  */
+    return true;
+  }
+
+  label_text describe_final_event (const evdesc::final_event &ev) final override
+  {
+    return ev.formatted_print ("infinite loop here");
+  }
+
+  /* Customize the location where the warning_event appears.  */
+  void add_final_event (const state_machine *,
+			const exploded_node *enode,
+			const gimple *,
+			tree,
+			state_machine::state_t,
+			checker_path *emission_path) final override
+  {
+    emission_path->add_event
+      (make_unique<warning_event>
+       (event_loc_info (m_inf_loop->m_loc,
+			enode->get_function ()->decl,
+			enode->get_stack_depth ()),
+	enode,
+	NULL, NULL, NULL));
+
+    logger *logger = emission_path->get_logger ();
+
+    /* EMISSION_PATH has the path to the entry of the infinite loop.
+       Add extra edges showing the loop itself.  */
+    for (auto eedge : m_inf_loop->m_eedge_vec)
+      {
+	if (logger)
+	  logger->log ("EN: %i -> EN: %i",
+		       eedge->m_src->m_index,
+		       eedge->m_dest->m_index);
+	if (!eedge->m_sedge)
+	  continue;
+
+	const cfg_superedge *cfg_sedge
+	  = eedge->m_sedge->dyn_cast_cfg_superedge ();
+	if (!cfg_sedge)
+	  continue;
+
+	const exploded_node *src_node = eedge->m_src;
+	const program_point &src_point = src_node->get_point ();
+	const exploded_node *dst_node = eedge->m_dest;
+	const program_point &dst_point = dst_node->get_point ();
+	const int src_stack_depth = src_point.get_stack_depth ();
+	const int dst_stack_depth = dst_point.get_stack_depth ();
+	const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();
+
+	event_loc_info loc_info_from
+	  (last_stmt ? last_stmt->location : cfg_sedge->get_goto_locus (),
+	   src_point.get_fndecl (),
+	   src_stack_depth);
+	event_loc_info loc_info_to
+	  (dst_point.get_supernode ()->get_start_location (),
+	   dst_point.get_fndecl (),
+	   dst_stack_depth);
+
+	if (const switch_cfg_superedge *switch_cfg_sedge
+	      = cfg_sedge->dyn_cast_switch_cfg_superedge ())
+	  {
+	    if (switch_cfg_sedge->implicitly_created_default_p ())
+	      {
+		emission_path->add_event
+		  (make_unique<perpetual_start_cfg_edge_event> (*eedge,
+								loc_info_from));
+		emission_path->add_event
+		  (make_unique<end_cfg_edge_event>
+		   (*eedge,
+		    loc_info_to));
+	      }
+	  }
+
+	if (cfg_sedge->true_value_p ())
+	  {
+	    emission_path->add_event
+	      (make_unique<perpetual_start_cfg_edge_event> (*eedge,
+							    loc_info_from));
+	    emission_path->add_event
+	      (make_unique<end_cfg_edge_event>
+	       (*eedge,
+		loc_info_to));
+	  }
+	else if (cfg_sedge->false_value_p ())
+	  {
+	    emission_path->add_event
+	      (make_unique<perpetual_start_cfg_edge_event> (*eedge,
+							    loc_info_from));
+	    emission_path->add_event
+	      (make_unique<end_cfg_edge_event>
+	       (*eedge,
+		loc_info_to));
+	  }
+	else if (cfg_sedge->back_edge_p ())
+	  {
+	    emission_path->add_event
+	      (make_unique<precanned_custom_event>
+	       (loc_info_from, "looping back..."));
+	    emission_path->add_event
+	      (make_unique<end_cfg_edge_event>
+	       (*eedge,
+		loc_info_to));
+	  }
+      }
+  }
+
+private:
+  std::unique_ptr<infinite_loop> m_inf_loop;
+};
+
+/* If ENODE has an in-edge corresponding to a CFG backedge, return that
+   exploded in-edge.
+   Otherwise, return nullptr.  */
+
+static const exploded_edge *
+get_in_edge_back_edge (const exploded_node &enode)
+{
+  for (auto in_edge : enode.m_preds)
+    {
+      const superedge *sedge = in_edge->m_sedge;
+      if (!sedge)
+	continue;
+      const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
+      if (!cfg_sedge)
+	continue;
+      if (cfg_sedge->back_edge_p ())
+	return in_edge;
+    }
+  return nullptr;
+}
+
+/* Subclass of region_model_context that rejects conditional branches that
+   aren't known for definite.  */
+
+class infinite_loop_checking_context : public noop_region_model_context
+{
+public:
+  infinite_loop_checking_context () : m_unusable (false) {}
+
+  bool checking_for_infinite_loop_p () const override { return true; }
+  void on_unusable_in_infinite_loop () override { m_unusable = true; }
+
+  bool unusable_p () const { return m_unusable; }
+
+private:
+  bool m_unusable;
+};
+
+/* Determine if an infinite loop starts at ENODE.
+   Return the loop if it is found, nullptr otherwise.
+
+   Look for cycles in the exploded graph in which:
+   - no externally visible work occurs
+   - no escape from the cycle
+   - the program state is "sufficiently concrete" at each step:
+     - no unknown activity could be occurring
+     - the worklist was fully drained for each enode in the cycle
+       i.e. every enode in the cycle is processed.  */
+
+static std::unique_ptr<infinite_loop>
+starts_infinite_loop_p (const exploded_node &enode,
+			const exploded_graph &eg,
+			logger *logger)
+{
+  LOG_FUNC_1 (logger, "considering EN: %i", enode.m_index);
+
+  /* Only consider enodes that have a CFG back edge as an in-edge.  */
+  if (const exploded_edge *back_edge = get_in_edge_back_edge (enode))
+    {
+      if (logger)
+	logger->log ("got backedge from EN: %i",
+		     back_edge->m_src->m_index);
+    }
+  else
+    {
+      if (logger)
+	logger->log ("rejecting: no backedge in in-edges");
+      return nullptr;
+    }
+
+  /* Support for dumping an .infinite-loop.dot file visualizing the
+     traversal for this enode.  */
+  std::unique_ptr<feasible_graph> fg;
+  feasible_node *curr_fnode = nullptr;
+
+  if (flag_dump_analyzer_infinite_loop)
+    fg = ::make_unique<feasible_graph> ();
+
+  location_t first_loc = UNKNOWN_LOCATION;
+  const exploded_node *iter = &enode;
+  feasibility_state state (*enode.get_state ().m_region_model,
+			   eg.get_supergraph ());
+
+  if (fg)
+    curr_fnode = fg->add_node (&enode, state, 0);
+
+  hash_set<const exploded_node *> visited;
+  std::vector<const exploded_edge *> eedges;
+  while (1)
+    {
+      if (logger)
+	logger->log ("iter: EN: %i", iter->m_index);
+      /* Analysis bailed out before processing this node.  */
+      if (iter->get_status () == exploded_node::STATUS_WORKLIST)
+	{
+	  if (logger)
+	    logger->log ("rejecting: EN: %i is still in worklist",
+			 iter->m_index);
+	  return nullptr;
+	}
+      if (visited.contains (iter))
+	{
+	  /* We've looped back on ourselves.  ENODE is in the loop
+	     itself if ENODE is the first place we looped back,
+	     as opposed to being on a path to a loop.  */
+	  if (iter == &enode)
+	    {
+	      if (logger)
+		logger->log ("accepting: looped back to EN: %i",
+			     iter->m_index);
+	      if (fg)
+		{
+		  auto_timevar tv (TV_ANALYZER_DUMP);
+		  pretty_printer pp;
+		  pp_printf (&pp, "%s.en%i.infinite-loop.dot",
+			     dump_base_name, enode.m_index);
+		  char *filename = xstrdup (pp_formatted_text (&pp));
+		  feasible_graph::dump_args_t dump_args (eg);
+		  fg->dump_dot (filename, nullptr, dump_args);
+		  free (filename);
+		}
+	      return ::make_unique<infinite_loop> (enode,
+						  first_loc,
+						  eedges,
+						  logger);
+	    }
+	  else
+	    {
+	      if (logger)
+		logger->log ("rejecting: looped back to EN: %i, not to EN: %i",
+			     iter->m_index, enode.m_index);
+	      return nullptr;
+	    }
+	}
+      visited.add (iter);
+      if (first_loc == UNKNOWN_LOCATION)
+	{
+	  location_t enode_loc = iter->get_point ().get_location ();
+	  if (enode_loc != UNKNOWN_LOCATION)
+	    first_loc = enode_loc;
+	}
+
+      /* Find the out-edges that are feasible, given the
+	 constraints here.  */
+      typedef std::pair<feasibility_state, const exploded_edge *> pair_t;
+      std::vector<pair_t> succs;
+      for (auto out_edge : iter->m_succs)
+	{
+	  log_scope s (logger, "considering out-edge",
+		       "EN:%i -> EN:%i",
+		       out_edge->m_src->m_index,
+		       out_edge->m_dest->m_index);
+	  feasibility_state next_state (state);
+
+	  /* Use this context to require edge conditions to be known,
+	     rather than be merely "possible".  */
+	  infinite_loop_checking_context ctxt;
+	  if (next_state.maybe_update_for_edge (logger,
+						out_edge,
+						&ctxt,
+						nullptr))
+	    succs.push_back (pair_t (next_state, out_edge));
+	  if (ctxt.unusable_p ())
+	    {
+	      /* If we get here, then we have e.g. a gcond where
+		 the condition is UNKNOWN, or a condition
+		 based on a widening_svalue.  Reject such paths.  */
+	      if (logger)
+		logger->log ("rejecting: unusable");
+	      return nullptr;
+	    }
+	}
+
+      if (succs.size () != 1)
+	{
+	  if (logger)
+	    logger->log ("rejecting: %i feasible successors",
+			 (int)succs.size ());
+	  return nullptr;
+	}
+      const feasibility_state &next_state = succs[0].first;
+      const exploded_edge *out_eedge = succs[0].second;
+      if (out_eedge->could_do_work_p ())
+	{
+	  if (logger)
+	    logger->log ("rejecting: edge could do work");
+	  return nullptr;
+	}
+      if (fg)
+	{
+	  feasible_node *next_fnode = fg->add_node (out_eedge->m_dest,
+						    next_state,
+						    fg->m_nodes.length ());
+	  fg->add_edge (new feasible_edge (curr_fnode, next_fnode, out_eedge));
+	  curr_fnode = next_fnode;
+	}
+      state = next_state;
+      eedges.push_back (out_eedge);
+      if (first_loc == UNKNOWN_LOCATION)
+	{
+	  if (out_eedge->m_sedge)
+	    if (::edge cfg_edge = out_eedge->m_sedge->get_any_cfg_edge ())
+	      if (cfg_edge->goto_locus > BUILTINS_LOCATION)
+		first_loc = cfg_edge->goto_locus;
+	}
+      iter = out_eedge->m_dest;
+    }
+}
+
+/* Implementation of -Wanalyzer-infinite-loop.  */
+
+void
+exploded_graph::detect_infinite_loops ()
+{
+  LOG_FUNC (get_logger ());
+  auto_timevar tv (TV_ANALYZER_INFINITE_LOOPS);
+
+  /* Track all enodes we've warned for; both the loop entrypoints
+     and all the enodes within those loops.  */
+  hash_set<const exploded_node *> warned_for;
+
+  for (auto enode : m_nodes)
+    {
+      if (get_logger ())
+	get_logger ()->log ("visited: %i out of %i",
+			    (int)warned_for.elements (), m_nodes.length ());
+
+      /* Only warn about the first enode we encounter in each cycle.  */
+      if (warned_for.contains(enode))
+	continue;
+
+      if (std::unique_ptr<infinite_loop> inf_loop
+	    = starts_infinite_loop_p (*enode, *this, get_logger ()))
+	{
+	  const supernode *snode = enode->get_supernode ();
+
+	  if (get_logger ())
+	    get_logger ()->log ("EN: %i from starts_infinite_loop_p",
+				enode->m_index);
+
+	  for (auto iter : inf_loop->m_eedge_vec)
+	    warned_for.add (iter->m_src);
+	  gcc_assert (warned_for.contains(enode));
+
+	  if (inf_loop->m_loc == UNKNOWN_LOCATION)
+	    {
+	      if (get_logger ())
+		get_logger ()->log
+		  ("no location available for reporting infinite loop");
+	      continue;
+	    }
+
+	  pending_location ploc (enode, snode, inf_loop->m_loc);
+	  auto d
+	    = ::make_unique<infinite_loop_diagnostic> (std::move (inf_loop));
+	  get_diagnostic_manager ().add_diagnostic (ploc, std::move (d));
+	}
+    }
+}