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

This patch adds a new -Wanalyzer-infinite-recursion warning to
-fanalyzer, which complains about certain cases of infinite recursion.

Specifically, when it detects recursion during its symbolic execution
of the user's code, it compares the state of memory to that at the
previous level of recursion, and if nothing appears to have effectively
changed, it issues a warning.

Unlike the middle-end warning -Winfinite-recursion (added by Martin
Sebor in GCC 12; r12-5483-g30ba058f77eedf), the analyzer warning
complains if there exists an interprocedural path in which recursion
occurs in which memory has not changed, whereas -Winfinite-recursion
complains if *every* intraprocedural path through the function leads to
a self-call.

Hence the warnings complement each other: there's some overlap, but each
also catches issues that the other misses.

For example, the new warning complains about a guarded recursion in
which the guard is passed unchanged:

void test_guarded (int flag)
{
  if (flag)
    test_guarded (flag);
}

t.c: In function 'test_guarded':
t.c:4:5: warning: infinite recursion [CWE-674] [-Wanalyzer-infinite-recursion]
    4 |     test_guarded (flag);
      |     ^~~~~~~~~~~~~~~~~~~
  'test_guarded': events 1-4
    |
    |    1 | void test_guarded (int flag)
    |      |      ^~~~~~~~~~~~
    |      |      |
    |      |      (1) initial entry to 'test_guarded'
    |    2 | {
    |    3 |   if (flag)
    |      |      ~
    |      |      |
    |      |      (2) following 'true' branch (when 'flag != 0')...
    |    4 |     test_guarded (flag);
    |      |     ~~~~~~~~~~~~~~~~~~~
    |      |     |
    |      |     (3) ...to here
    |      |     (4) calling 'test_guarded' from 'test_guarded'
    |
    +--> 'test_guarded': events 5-6
           |
           |    1 | void test_guarded (int flag)
           |      |      ^~~~~~~~~~~~
           |      |      |
           |      |      (5) recursive entry to 'test_guarded'; previously entered at (1)
           |      |      (6) apparently infinite recursion
           |

whereas the existing warning doesn't complain, since when "flag" is
false the function doesn't recurse.

The new warning doesn't trigger for e.g.:

  void test_param_variant (int depth)
  {
    if (depth > 0)
      test_param_variant (depth - 1);
  }

on the grounds that "depth" is changing, and appears to be a variant
that enforces termination of the recursion.

gcc/ChangeLog:
	PR analyzer/106147
	* Makefile.in (ANALYZER_OBJS): Add analyzer/infinite-recursion.o.

gcc/analyzer/ChangeLog:
	PR analyzer/106147
	* analyzer.opt (Wanalyzer-infinite-recursion): New.
	* call-string.cc (call_string::count_occurrences_of_function):
	New.
	* call-string.h (call_string::count_occurrences_of_function): New
	decl.
	* checker-path.cc (function_entry_event::function_entry_event):
	New ctor.
	(checker_path::add_final_event): Delete.
	* checker-path.h (function_entry_event::function_entry_event): New
	ctor.
	(function_entry_event::get_desc): Drop "final".
	(checker_path::add_final_event): Delete.
	* diagnostic-manager.cc
	(diagnostic_manager::emit_saved_diagnostic): Create the final
	event via a new pending_diagnostic::add_final_event vfunc, rather
	than checker_path::add_final_event.
	(diagnostic_manager::add_events_for_eedge): Create function entry
	events via a new pending_diagnostic::add_function_entry_event
	vfunc.
	* engine.cc (exploded_graph::process_node): When creating a new
	PK_BEFORE_SUPERNODE node, call
	exploded_graph::detect_infinite_recursion on it after adding the
	in-edge.
	* exploded-graph.h (exploded_graph::detect_infinite_recursion):
	New decl.
	(exploded_graph::find_previous_entry_to): New decl.
	* infinite-recursion.cc: New file.
	* pending-diagnostic.cc
	(pending_diagnostic::add_function_entry_event): New.
	(pending_diagnostic::add_final_event): New.
	* pending-diagnostic.h
	(pending_diagnostic::add_function_entry_event): New vfunc.
	(pending_diagnostic::add_final_event): New vfunc.

gcc/ChangeLog:
	PR analyzer/106147
	* doc/gcc/gcc-command-options/options-that-control-static-analysis.rst:
	Add -Wanalyzer-infinite-recursion.
	* doc/gcc/gcc-command-options/options-to-request-or-suppress-warnings.rst
	(-Winfinite-recursion): Mention -Wanalyzer-infinite-recursion.

gcc/testsuite/ChangeLog:
	PR analyzer/106147
	* g++.dg/analyzer/infinite-recursion-1.C: New test.
	* g++.dg/analyzer/infinite-recursion-2.C: New test, copied from
	g++.dg/warn/Winfinite-recursion-2.C.
	* g++.dg/analyzer/infinite-recursion-3.C: New test, adapted from
	g++.dg/warn/Winfinite-recursion-3.C.
	* gcc.dg/analyzer/infinite-recursion-2.c: New test.
	* gcc.dg/analyzer/infinite-recursion-3.c: New test.
	* gcc.dg/analyzer/infinite-recursion-4-limited-buggy.c: New test.
	* gcc.dg/analyzer/infinite-recursion-4-limited.c: New test.
	* gcc.dg/analyzer/infinite-recursion-4-unlimited-buggy.c: New test.
	* gcc.dg/analyzer/infinite-recursion-4-unlimited.c: New test.
	* gcc.dg/analyzer/infinite-recursion-5.c: New test, adapted from
	gcc.dg/Winfinite-recursion.c.
	* gcc.dg/analyzer/infinite-recursion-alloca.c: New test.
	* gcc.dg/analyzer/infinite-recursion-inlining.c: New test.
	* gcc.dg/analyzer/infinite-recursion-multiline-1.c: New test.
	* gcc.dg/analyzer/infinite-recursion-multiline-2.c: New test.
	* gcc.dg/analyzer/infinite-recursion-variadic.c: New test.
	* gcc.dg/analyzer/infinite-recursion.c: Add dg-warning directives
	where infinite recursions occur.
	* gcc.dg/analyzer/malloc-ipa-12.c: Likewise.
	* gcc.dg/analyzer/pr105365.c: Likewise.
	* gcc.dg/analyzer/pr105366.c: Likewise.
	* gcc.dg/analyzer/pr97029.c: Likewise.

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

1 files changed, 2 insertions, 0 deletions

diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h
index c3cea90..d97ff84 100644
--- a/gcc/analyzer/call-string.h
+++ b/gcc/analyzer/call-string.h
@@ -105,6 +105,8 @@ public:
     return m_elements[m_elements.length () - 1];
   }
 
+  int count_occurrences_of_function (function *) const;
+
   void validate () const;
 
 private: