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, 1 insertions, 0 deletions

diff --git a/gcc/timevar.def b/gcc/timevar.def
index d21b08c..9628223 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -342,6 +342,7 @@ DEFTIMEVAR (TV_ANALYZER_STATE_PURGE  , "analyzer: state purge")
 DEFTIMEVAR (TV_ANALYZER_PLAN         , "analyzer: planning")
 DEFTIMEVAR (TV_ANALYZER_SCC          , "analyzer: scc")
 DEFTIMEVAR (TV_ANALYZER_WORKLIST     , "analyzer: processing worklist")
+DEFTIMEVAR (TV_ANALYZER_INFINITE_LOOPS, "analyzer: finding infinite loops")
 DEFTIMEVAR (TV_ANALYZER_DUMP         , "analyzer: dump")
 DEFTIMEVAR (TV_ANALYZER_DIAGNOSTICS  , "analyzer: emitting diagnostics")
 DEFTIMEVAR (TV_ANALYZER_SHORTEST_PATHS, "analyzer: shortest paths")