@@ -1250,6 +1250,7 @@ ANALYZER_OBJS = \
analyzer/engine.o \
analyzer/feasible-graph.o \
analyzer/function-set.o \
+ analyzer/infinite-recursion.o \
analyzer/known-function-manager.o \
analyzer/pending-diagnostic.o \
analyzer/program-point.o \
@@ -110,6 +110,10 @@ Wanalyzer-imprecise-fp-arithmetic
Common Var(warn_analyzer_imprecise_fp_arithmetic) Init(1) Warning
Warn about code paths in which floating-point arithmetic is used in locations where precise computation is needed.
+Wanalyzer-infinite-recursion
+Common Var(warn_analyzer_infinite_recursion) Init(1) Warning
+Warn about code paths which appear to lead to infinite recursion.
+
Wanalyzer-jump-through-null
Common Var(warn_analyzer_jump_through_null) Init(1) Warning
Warn about code paths in which a NULL function pointer is called.
@@ -170,6 +170,22 @@ call_string::calc_recursion_depth () const
return result;
}
+/* Count the number of times FUN appears in the string. */
+
+int
+call_string::count_occurrences_of_function (function *fun) const
+{
+ int result = 0;
+ for (const call_string::element_t &e : m_elements)
+ {
+ if (e.get_callee_function () == fun)
+ result++;
+ if (e.get_caller_function () == fun)
+ result++;
+ }
+ return result;
+}
+
/* Comparator for call strings.
This implements a version of lexicographical order.
Return negative if A is before B.
@@ -105,6 +105,8 @@ public:
return m_elements[m_elements.length () - 1];
}
+ int count_occurrences_of_function (function *) const;
+
void validate () const;
private:
@@ -377,6 +377,14 @@ region_creation_event::get_desc (bool can_colorize) const
/* class function_entry_event : public checker_event. */
+function_entry_event::function_entry_event (const program_point &dst_point)
+: checker_event (EK_FUNCTION_ENTRY,
+ dst_point.get_supernode ()->get_start_location (),
+ dst_point.get_fndecl (),
+ dst_point.get_stack_depth ())
+{
+}
+
/* Implementation of diagnostic_event::get_desc vfunc for
function_entry_event.
@@ -1304,21 +1312,6 @@ checker_path::add_region_creation_events (const region *reg,
loc, fndecl, depth));
}
-/* Add a warning_event to the end of this path. */
-
-void
-checker_path::add_final_event (const state_machine *sm,
- const exploded_node *enode, const gimple *stmt,
- tree var, state_machine::state_t state)
-{
- add_event
- (make_unique<warning_event> (get_stmt_location (stmt,
- enode->get_function ()),
- enode->get_function ()->decl,
- enode->get_stack_depth (),
- sm, var, state));
-}
-
void
checker_path::fixup_locations (pending_diagnostic *pd)
{
@@ -260,7 +260,9 @@ public:
{
}
- label_text get_desc (bool can_colorize) const final override;
+ function_entry_event (const program_point &dst_point);
+
+ label_text get_desc (bool can_colorize) const override;
meaning get_meaning () const override;
bool is_function_entry_p () const final override { return true; }
@@ -660,10 +662,6 @@ public:
tree fndecl, int depth,
bool debug);
- void add_final_event (const state_machine *sm,
- const exploded_node *enode, const gimple *stmt,
- tree var, state_machine::state_t state);
-
/* After all event-pruning, a hook for notifying each event what
its ID will be. The events are notified in order, allowing
for later events to refer to the IDs of earlier events in
@@ -1368,8 +1368,8 @@ 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 (), sd.m_stmt,
- sd.m_var, sd.m_state);
+ sd.m_d->add_final_event (sd.m_sm, epath->get_final_enode (), sd.m_stmt,
+ sd.m_var, sd.m_state, &emission_path);
/* The "final" event might not be final; if the saved_diagnostic has a
trailing eedge stashed, add any events for it. This is for use
@@ -1922,11 +1922,8 @@ diagnostic_manager::add_events_for_eedge (const path_builder &pb,
/* Add function entry events. */
if (dst_point.get_supernode ()->entry_p ())
{
- emission_path->add_event
- (make_unique<function_entry_event>
- (dst_point.get_supernode ()->get_start_location (),
- dst_point.get_fndecl (),
- dst_stack_depth));
+ pb.get_pending_diagnostic ()->add_function_entry_event
+ (eedge, emission_path);
/* Create region_creation_events for on-stack regions within
this frame. */
if (interest)
@@ -4276,7 +4276,12 @@ exploded_graph::process_node (exploded_node *node)
exploded_node *next = get_or_create_node (next_point, next_state,
node);
if (next)
- add_edge (node, next, succ);
+ {
+ add_edge (node, next, succ);
+
+ /* We might have a function entrypoint. */
+ detect_infinite_recursion (next);
+ }
}
/* Return from the calls which doesn't have a return superedge.
@@ -851,6 +851,11 @@ public:
void on_escaped_function (tree fndecl);
+ /* In infinite-recursion.cc */
+ void detect_infinite_recursion (exploded_node *enode);
+ exploded_node *find_previous_entry_to (function *top_of_stack_fun,
+ exploded_node *enode) const;
+
private:
void print_bar_charts (pretty_printer *pp) const;
new file mode 100644
@@ -0,0 +1,481 @@
+/* Detection of infinite recursion.
+ Copyright (C) 2022 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
+#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 "make-unique.h"
+#include "analyzer/checker-path.h"
+
+/* A subclass of pending_diagnostic for complaining about suspected
+ infinite recursion. */
+
+class infinite_recursion_diagnostic
+: public pending_diagnostic_subclass<infinite_recursion_diagnostic>
+{
+public:
+ infinite_recursion_diagnostic (const exploded_node *prev_entry_enode,
+ const exploded_node *new_entry_enode,
+ tree callee_fndecl)
+ : m_prev_entry_enode (prev_entry_enode),
+ m_new_entry_enode (new_entry_enode),
+ m_callee_fndecl (callee_fndecl),
+ m_prev_entry_event (NULL)
+ {}
+
+ const char *get_kind () const final override
+ {
+ return "infinite_recursion_diagnostic";
+ }
+
+ bool operator== (const infinite_recursion_diagnostic &other) const
+ {
+ return m_callee_fndecl == other.m_callee_fndecl;
+ }
+
+ int get_controlling_option () const final override
+ {
+ return OPT_Wanalyzer_infinite_recursion;
+ }
+
+ bool emit (rich_location *rich_loc) final override
+ {
+ /* "CWE-674: Uncontrolled Recursion". */
+ diagnostic_metadata m;
+ m.add_cwe (674);
+ return warning_meta (rich_loc, m, get_controlling_option (),
+ "infinite recursion");
+ }
+
+ label_text describe_final_event (const evdesc::final_event &ev) final override
+ {
+ const int frames_consumed = (m_new_entry_enode->get_stack_depth ()
+ - m_prev_entry_enode->get_stack_depth ());
+ if (frames_consumed > 1)
+ return ev.formatted_print
+ ("apparently infinite chain of mutually-recursive function calls,"
+ " consuming %i stack frames per recursion",
+ frames_consumed);
+ else
+ return ev.formatted_print ("apparently infinite recursion");
+ }
+
+ void
+ add_function_entry_event (const exploded_edge &eedge,
+ checker_path *emission_path) final override
+ {
+ /* Subclass of function_entry_event for use when reporting both
+ the initial and subsequent entries to the function of interest,
+ allowing for cross-referencing the first event in the description
+ of the second. */
+ class recursive_function_entry_event : public function_entry_event
+ {
+ public:
+ recursive_function_entry_event (const program_point &dst_point,
+ const infinite_recursion_diagnostic &pd,
+ bool topmost)
+ : function_entry_event (dst_point),
+ m_pd (pd),
+ m_topmost (topmost)
+ {
+ }
+
+ label_text
+ get_desc (bool can_colorize) const final override
+ {
+ if (m_topmost)
+ {
+ if (m_pd.m_prev_entry_event
+ && m_pd.m_prev_entry_event->get_id_ptr ()->known_p ())
+ return make_label_text
+ (can_colorize,
+ "recursive entry to %qE; previously entered at %@",
+ m_effective_fndecl,
+ m_pd.m_prev_entry_event->get_id_ptr ());
+ else
+ return make_label_text (can_colorize, "recursive entry to %qE",
+ m_effective_fndecl);
+ }
+ else
+ return make_label_text (can_colorize, "initial entry to %qE",
+ m_effective_fndecl);
+ }
+
+ private:
+ const infinite_recursion_diagnostic &m_pd;
+ bool m_topmost;
+ };
+ const exploded_node *dst_node = eedge.m_dest;
+ const program_point &dst_point = dst_node->get_point ();
+ if (eedge.m_dest == m_prev_entry_enode)
+ {
+ gcc_assert (m_prev_entry_event == NULL);
+ std::unique_ptr<checker_event> prev_entry_event
+ = make_unique <recursive_function_entry_event> (dst_point,
+ *this, false);
+ m_prev_entry_event = prev_entry_event.get ();
+ emission_path->add_event (std::move (prev_entry_event));
+ }
+ else if (eedge.m_dest == m_new_entry_enode)
+ emission_path->add_event
+ (make_unique<recursive_function_entry_event> (dst_point, *this, true));
+ else
+ pending_diagnostic::add_function_entry_event (eedge, emission_path);
+ }
+
+ /* Customize the location where the warning_event appears, putting
+ it at the topmost entrypoint to the function. */
+ void add_final_event (const state_machine *,
+ const exploded_node *,
+ const gimple *,
+ tree,
+ state_machine::state_t,
+ checker_path *emission_path) final override
+ {
+ gcc_assert (m_new_entry_enode);
+ emission_path->add_event
+ (make_unique<warning_event>
+ (m_new_entry_enode->get_supernode ()->get_start_location (),
+ m_callee_fndecl,
+ m_new_entry_enode->get_stack_depth (),
+ NULL, NULL, NULL));
+ }
+
+private:
+ const exploded_node *m_prev_entry_enode;
+ const exploded_node *m_new_entry_enode;
+ tree m_callee_fndecl;
+ const checker_event *m_prev_entry_event;
+};
+
+/* Return true iff ENODE is the PK_BEFORE_SUPERNODE at a function
+ entrypoint. */
+
+static bool
+is_entrypoint_p (exploded_node *enode)
+{
+ /* Look for an entrypoint to a function... */
+ const supernode *snode = enode->get_supernode ();
+ if (!snode)
+ return false;
+ if (!snode->entry_p ())
+ return false;;
+ const program_point &point = enode->get_point ();
+ if (point.get_kind () != PK_BEFORE_SUPERNODE)
+ return false;
+ return true;
+}
+
+/* Walk backwards through the eg, looking for the first
+ enode we find that's also the entrypoint of the same function. */
+
+exploded_node *
+exploded_graph::find_previous_entry_to (function *top_of_stack_fun,
+ exploded_node *enode) const
+{
+ auto_vec<exploded_node *> worklist;
+ hash_set<exploded_node *> visited;
+
+ visited.add (enode);
+ for (auto in_edge : enode->m_preds)
+ worklist.safe_push (in_edge->m_src);
+
+ while (worklist.length () > 0)
+ {
+ exploded_node *iter = worklist.pop ();
+
+ if (is_entrypoint_p (iter)
+ && iter->get_function () == top_of_stack_fun)
+ return iter;
+
+ if (visited.contains (iter))
+ continue;
+ visited.add (iter);
+ for (auto in_edge : iter->m_preds)
+ worklist.safe_push (in_edge->m_src);
+ }
+
+ /* Not found. */
+ return NULL;
+}
+
+/* Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
+ remap it to the equivalent region within EQUIV_PREV_FRAME.
+
+ For example, given param "n" within frame "foo@3", and equiv prev frame
+ "foo@1", remap it to param "n" within frame "foo@1". */
+
+static const region *
+remap_enclosing_frame (const region *base_reg,
+ const frame_region *enclosing_frame,
+ const frame_region *equiv_prev_frame,
+ region_model_manager *mgr)
+{
+ gcc_assert (base_reg->get_parent_region () == enclosing_frame);
+ switch (base_reg->get_kind ())
+ {
+ default:
+ /* We should only encounter params and varargs at the topmost
+ entrypoint. */
+ gcc_unreachable ();
+
+ case RK_VAR_ARG:
+ {
+ const var_arg_region *var_arg_reg = (const var_arg_region *)base_reg;
+ return mgr->get_var_arg_region (equiv_prev_frame,
+ var_arg_reg->get_index ());
+ }
+ case RK_DECL:
+ {
+ const decl_region *decl_reg = (const decl_region *)base_reg;
+ return equiv_prev_frame->get_region_for_local (mgr,
+ decl_reg->get_decl (),
+ NULL);
+ }
+ }
+}
+
+/* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
+ both of which are entrypoints to the same function, where recursion has
+ occurred.
+
+ Return true if the state of NEW_ENTRY_ENODE is sufficiently different
+ from PREV_ENTRY_ENODE to suggests that some variant is being modified,
+ and thus the recursion isn't infinite.
+
+ Return false if the states are effectively the same, suggesting that
+ the recursion is infinite.
+
+ For example, consider mutually recursive functions "foo" and "bar".
+ At the entrypoint to a "foo" frame where we've detected recursion,
+ we might have three frames on the stack: the new 'foo'@3, an inner
+ 'bar'@2, and the innermost 'foo'@1.
+
+ (gdb) call enode->dump(m_ext_state)
+ EN: 16
+ callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
+ before SN: 0 (NULL from-edge)
+
+ rmodel:
+ stack depth: 3
+ frame (index 2): frame: ‘foo’@3
+ frame (index 1): frame: ‘bar’@2
+ frame (index 0): frame: ‘foo’@1
+ clusters within root region
+ cluster for: (*INIT_VAL(f_4(D)))
+ clusters within frame: ‘bar’@2
+ cluster for: b_2(D): INIT_VAL(f_4(D))
+ clusters within frame: ‘foo’@3
+ cluster for: f_4(D): INIT_VAL(f_4(D))
+ m_called_unknown_fn: FALSE
+
+ whereas for the previous entry node we'd have just the innermost
+ 'foo'@1
+
+ (gdb) call prev_entry_enode->dump(m_ext_state)
+ EN: 1
+ callstring: []
+ before SN: 0 (NULL from-edge)
+
+ rmodel:
+ stack depth: 1
+ frame (index 0): frame: ‘foo’@1
+ clusters within root region
+ cluster for: (*INIT_VAL(f_4(D)))
+ m_called_unknown_fn: FALSE
+
+ We want to abstract away frames 1 and 2 in the new entry enode,
+ and compare its frame 3 with the frame 1 in the previous entry
+ enode, and determine if enough state changes between them to
+ rule out infinite recursion. */
+
+static bool
+sufficiently_different_p (exploded_node *new_entry_enode,
+ exploded_node *prev_entry_enode,
+ logger *logger)
+{
+ LOG_SCOPE (logger);
+ gcc_assert (new_entry_enode);
+ gcc_assert (prev_entry_enode);
+ gcc_assert (is_entrypoint_p (new_entry_enode));
+ gcc_assert (is_entrypoint_p (prev_entry_enode));
+
+ const int new_stack_depth = new_entry_enode->get_stack_depth ();
+
+ /* Compare the stores of the two enodes. */
+ const region_model &new_model
+ = *new_entry_enode->get_state ().m_region_model;
+ const region_model &prev_model
+ = *prev_entry_enode->get_state ().m_region_model;
+ const store &new_store = *new_model.get_store ();
+
+ for (auto kv : new_store)
+ {
+ const region *base_reg = kv.first;
+
+ /* Get the value within the new frame. */
+ const svalue *new_sval
+ = new_model.get_store_value (base_reg, NULL);
+
+ /* If the value is UNKNOWN (e.g. due to hitting complexity limits)
+ assume that it differs from the previous value. */
+ if (new_sval->get_kind () == SK_UNKNOWN)
+ return true;
+
+ /* Get the equivalent value within the old enode. */
+ const svalue *prev_sval;
+
+ if (const frame_region *enclosing_frame
+ = base_reg->maybe_get_frame_region ())
+ {
+ /* We have a binding within a frame in the new entry enode. */
+
+ /* Ignore bindings within frames below the new entry node. */
+ if (enclosing_frame->get_stack_depth () < new_stack_depth)
+ continue;
+
+ /* We have a binding within the frame of the new entry node,
+ presumably a parameter. */
+
+ /* Get the value within the equivalent frame of
+ the old entrypoint; typically will be the initial_svalue
+ of the parameter. */
+ const frame_region *equiv_prev_frame
+ = prev_model.get_current_frame ();
+ const region *equiv_prev_base_reg
+ = remap_enclosing_frame (base_reg,
+ enclosing_frame,
+ equiv_prev_frame,
+ new_model.get_manager ());
+ prev_sval = prev_model.get_store_value (equiv_prev_base_reg, NULL);
+ }
+ else
+ prev_sval = prev_model.get_store_value (base_reg, NULL);
+
+ /* If the prev_sval is UNKNOWN (e.g. due to hitting complexity limits)
+ assume that it will differ from any new value. */
+ if (prev_sval->get_kind () == SK_UNKNOWN)
+ return true;
+
+ if (new_sval != prev_sval)
+ return true;
+ }
+
+ /* No significant differences found. */
+ return false;
+}
+
+/* Implementation of -Wanalyzer-infinite-recursion.
+
+ Called when adding ENODE to the graph, after adding its first in-edge.
+
+ For function entrypoints, see if recursion has occurred, and, if so,
+ check if the state of memory changed between the recursion levels,
+ which would suggest some kind of decreasing variant that leads to
+ termination.
+
+ For recursive calls where the state of memory is effectively unchanged
+ between recursion levels, warn with -Wanalyzer-infinite-recursion. */
+
+void
+exploded_graph::detect_infinite_recursion (exploded_node *enode)
+{
+ if (!is_entrypoint_p (enode))
+ return;
+ function *top_of_stack_fun = enode->get_function ();
+ gcc_assert (top_of_stack_fun);
+
+ /* ....where a call to that function is already in the call string. */
+ const call_string &call_string = enode->get_point ().get_call_string ();
+
+ if (call_string.count_occurrences_of_function (top_of_stack_fun) < 2)
+ return;
+
+ tree fndecl = top_of_stack_fun->decl;
+
+ log_scope s (get_logger (),
+ "checking for infinite recursion",
+ "considering recursion at EN: %i entering %qE",
+ enode->m_index, fndecl);
+
+ /* Find enode that's the entrypoint for the previous frame for fndecl
+ in the recursion. */
+ exploded_node *prev_entry_enode
+ = find_previous_entry_to (top_of_stack_fun, enode);
+ gcc_assert (prev_entry_enode);
+ if (get_logger ())
+ get_logger ()->log ("previous entrypoint to %qE is EN: %i",
+ fndecl, prev_entry_enode->m_index);
+
+ /* Look for changes to the state of memory between the recursion levels. */
+ if (sufficiently_different_p (enode, prev_entry_enode, get_logger ()))
+ return;
+
+ /* Otherwise, the state of memory is effectively the same between the two
+ recursion levels; warn. */
+
+ const supernode *caller_snode = call_string.get_top_of_stack ().m_caller;
+ const supernode *snode = enode->get_supernode ();
+ gcc_assert (caller_snode->m_returning_call);
+ get_diagnostic_manager ().add_diagnostic
+ (enode, snode, caller_snode->m_returning_call, NULL,
+ make_unique<infinite_recursion_diagnostic> (prev_entry_enode,
+ enode,
+ fndecl));
+}
@@ -167,6 +167,18 @@ pending_diagnostic::fixup_location (location_t loc) const
return loc;
}
+/* Base implementation of pending_diagnostic::add_function_entry_event.
+ Add a function_entry_event to EMISSION_PATH. */
+
+void
+pending_diagnostic::add_function_entry_event (const exploded_edge &eedge,
+ checker_path *emission_path)
+{
+ const exploded_node *dst_node = eedge.m_dest;
+ const program_point &dst_point = dst_node->get_point ();
+ emission_path->add_event (make_unique<function_entry_event> (dst_point));
+}
+
/* Base implementation of pending_diagnostic::add_call_event.
Add a call_event to EMISSION_PATH. */
@@ -187,6 +199,24 @@ pending_diagnostic::add_call_event (const exploded_edge &eedge,
src_stack_depth));
}
+/* Base implementation of pending_diagnostic::add_final_event.
+ Add a warning_event to the end of EMISSION_PATH. */
+
+void
+pending_diagnostic::add_final_event (const state_machine *sm,
+ const exploded_node *enode,
+ const gimple *stmt,
+ tree var, state_machine::state_t state,
+ checker_path *emission_path)
+{
+ emission_path->add_event
+ (make_unique<warning_event> (get_stmt_location (stmt,
+ enode->get_function ()),
+ enode->get_function ()->decl,
+ enode->get_stack_depth (),
+ sm, var, state));
+}
+
} // namespace ana
#endif /* #if ENABLE_ANALYZER */
@@ -309,6 +309,14 @@ class pending_diagnostic
/* End of precision-of-wording vfuncs. */
+ /* Vfunc for adding a function_entry_event to a checker_path, so that e.g.
+ the infinite recursion diagnostic can add a custom event subclass
+ that annotates recursively entering a function. */
+
+ virtual void
+ add_function_entry_event (const exploded_edge &eedge,
+ checker_path *emission_path);
+
/* Vfunc for extending/overriding creation of the events for an
exploded_edge that corresponds to a superedge, allowing for custom
events to be created that are pertinent to a particular
@@ -330,6 +338,16 @@ class pending_diagnostic
virtual void add_call_event (const exploded_edge &,
checker_path *);
+ /* Vfunc for adding the final warning_event to a checker_path, so that e.g.
+ the infinite recursion diagnostic can have its diagnostic appear at
+ the callsite, but the final event in the path be at the entrypoint
+ of the called function. */
+ virtual void add_final_event (const state_machine *sm,
+ const exploded_node *enode,
+ const gimple *stmt,
+ tree var, state_machine::state_t state,
+ checker_path *emission_path);
+
/* Vfunc for determining that this pending_diagnostic supercedes OTHER,
and that OTHER should therefore not be emitted.
They have already been tested for being at the same stmt. */
@@ -32,6 +32,7 @@ Options That Control Static Analysis
:option:`-Wanalyzer-file-leak` |gol|
:option:`-Wanalyzer-free-of-non-heap` |gol|
:option:`-Wanalyzer-imprecise-fp-arithmetic` |gol|
+ :option:`-Wanalyzer-infinite-recursion` |gol|
:option:`-Wanalyzer-jump-through-null` |gol|
:option:`-Wanalyzer-malloc-leak` |gol|
:option:`-Wanalyzer-mismatching-deallocation` |gol|
@@ -308,6 +309,33 @@ Options That Control Static Analysis
Default setting; overrides :option:`-Wno-analyzer-imprecise-fp-arithmetic`.
+.. option:: -Wno-analyzer-infinite-recursion
+
+ This warning requires :option:`-fanalyzer`, which enables it; use
+ :option:`-Wno-analyzer-infinite-recursion` to disable it.
+
+ This diagnostics warns for paths through the code which appear to
+ lead to infinite recursion.
+
+ Specifically, when the analyzer "sees" a recursive call, it will compare
+ the state of memory at the entry to the new frame with that at the entry
+ to the previous frame of that function on the stack. The warning is
+ issued if nothing in memory appears to be changing; any changes observed
+ to parameters or globals are assumed to lead to termination of the
+ recursion and thus suppress the warning.
+
+ This diagnostic is likely to miss cases of infinite recursion that
+ are convered to iteration by the optimizer before the analyzer "sees"
+ them. Hence optimization should be disabled when attempting to trigger
+ this diagnostic.
+
+ Compare with :option:`-Winfinite-recursion`, which provides a similar
+ diagnostic, but is implemented in a different way.
+
+.. option:: -Wanalyzer-infinite-recursion
+
+ Default setting; overrides :option:`-Wno-analyzer-infinite-recursion`.
+
.. option:: -Wno-analyzer-jump-through-null
This warning requires :option:`-fanalyzer`, which enables it; use
@@ -804,6 +804,10 @@ warnings, in some cases it may also cause false positives.
recursion in calls between two or more functions.
:option:`-Winfinite-recursion` is included in :option:`-Wall`.
+ Compare with :option:`-Wanalyzer-infinite-recursion` which provides a
+ similar diagnostic, but is implemented in a different way (as part of
+ :option:`-fanalyzer`).
+
.. option:: -Wno-infinite-recursion
Default setting; overrides :option:`-Winfinite-recursion`.
new file mode 100644
@@ -0,0 +1,84 @@
+class widget
+{
+public:
+ virtual void draw ()
+ {
+ /* no-op */
+ }
+};
+
+class foo_widget : public widget
+{
+public:
+ void draw ();
+};
+
+void foo_widget::draw ()
+{
+ // Bogus attempt to chain up to base class leading to infinite recursion:
+ foo_widget::draw (); /* { dg-warning "infinite recursion" } */
+
+ // [...snip...]
+}
+
+/* Infinite recursion due to a buggy "operator int". */
+
+class boxed_int
+{
+ int m_val;
+public:
+ operator int ();
+};
+
+boxed_int::operator int ()
+{
+ return *this; /* { dg-warning "infinite recursion" } */
+}
+
+template <typename T>
+class buggy_getter
+{
+public:
+ T get_value () const
+ {
+ return get_value (); /* { dg-warning "infinite recursion" } */
+ }
+};
+
+int test_buggy_getter (buggy_getter<int> g)
+{
+ return g.get_value ();
+}
+
+/* Copy of g++.dg/warn/Winfinite-recursion.C */
+
+template <typename D>
+struct C
+{
+ void foo ()
+ {
+ static_cast<D *>(this)->foo (); /* { dg-warning "-Wanalyzer-infinite-recursion" } */
+ }
+};
+
+struct D : C<D>
+{
+ // this is missing:
+ // void foo() {}
+};
+
+void f (D *d)
+{
+ d->foo ();
+}
+
+
+struct E : C<D>
+{
+ void foo() {}
+};
+
+void g (E *e)
+{
+ e->foo ();
+}
new file mode 100644
@@ -0,0 +1,74 @@
+/* Copy of g++.dg/warn/Winfinite-recursion-2.C */
+
+/* { dg-do compile { target c++11 } } */
+
+namespace std
+{
+class type_info {
+public:
+ void k() const;
+};
+
+} // namespace std
+
+using std::type_info;
+
+template <int a> struct f { static constexpr int c = a; };
+struct h {
+ typedef int e;
+};
+
+template <unsigned long, typename...> struct m;
+template <unsigned long ab, typename i, typename j, typename... ac>
+struct m<ab, i, j, ac...> : m<ab + 1, i, ac...> {};
+template <unsigned long ab, typename j, typename... ac>
+struct m<ab, j, j, ac...> : f<ab> {};
+template <unsigned long, typename...> struct n;
+template <unsigned long ab, typename j, typename... ac>
+struct n<ab, j, ac...> : n<ab - 1, ac...> {};
+template <typename j, typename... ac> struct n<0, j, ac...> : h {};
+template <typename... l> class F {
+ template <typename i> struct I : m<0, i, l...> {};
+ template <int ab> struct s : n<ab, l...> {};
+ static const type_info *const b[];
+ struct G {
+ template <typename ag>
+ operator ag() const
+ {
+ return *this; /* { dg-warning "-Wanalyzer-infinite-recursion" } */
+ }
+ };
+ unsigned o;
+ G ah;
+
+public:
+ F();
+ long t() const { return o; }
+ const type_info &m_fn3() const { return *b[o]; }
+ template <int ab> typename s<ab>::e *m_fn4() const {
+ if (o != ab)
+ return nullptr;
+ return ah;
+ }
+ template <int ab> void m_fn5() const {
+ m_fn4<ab>();
+ const type_info &r = m_fn3();
+ r.k();
+ }
+ template <typename i> void u() const { m_fn5<I<i>::c>(); }
+};
+template <typename... l> const type_info *const F<l...>::b[] {&typeid(l)...};
+using am = unsigned char;
+class H {
+ enum bd : am { be = 2 };
+ using bf = F<int, int, H>;
+ bf ah;
+ template <typename bg> void v() const { ah.u<bg>(); }
+ void w() const;
+};
+void H::w() const {
+ bd d = bd(ah.t());
+ switch (d)
+ case be:
+ v<H>();
+}
new file mode 100644
@@ -0,0 +1,62 @@
+/* Adapted from g++.dg/warn/Winfinite-recursion-3.C */
+
+typedef __SIZE_TYPE__ size_t;
+
+/* Might throw. */
+void f ();
+
+void warn_f_call_r (int n)
+{
+ if (n > 7)
+ f ();
+ warn_f_call_r (n - 1);
+}
+
+void warn_f_do_while_call_r (int n)
+{
+ f ();
+ do
+ {
+ f ();
+ warn_f_do_while_call_r (n - 1);
+ }
+ while (1);
+}
+
+
+struct X
+{
+ X (int);
+ ~X ();
+};
+
+int warn_class_with_ctor (int n)
+{
+ X x (n);
+ return n + warn_class_with_ctor (n - 1);
+}
+
+
+int nowarn_throw (int n)
+{
+ if (n > 7)
+ throw "argument too big";
+
+ return n + nowarn_throw (n - 1);
+}
+
+extern int* eipa[];
+
+void warn_call_new (int i)
+{
+ eipa[i] = new int;
+
+ warn_call_new (i - 1);
+}
+
+void* operator new[] (size_t n)
+{
+ char *p = new char[n + sizeof (n)];
+ *(size_t*)p = n;
+ return p + sizeof n;
+}
new file mode 100644
@@ -0,0 +1,109 @@
+void test_direct (void)
+{
+ test_direct (); /* { dg-warning "infinite recursion" } */
+}
+
+void test_guarded (int flag)
+{
+ if (flag)
+ test_guarded (flag); /* { dg-warning "infinite recursion" } */
+}
+
+void test_flipped_guard (int flag)
+{
+ if (flag)
+ test_guarded (!flag); /* { dg-bogus "infinite recursion" } */
+}
+
+void test_param_variant (int depth)
+{
+ if (depth > 0)
+ test_param_variant (depth - 1); /* { dg-bogus "infinite recursion" } */
+}
+
+void test_unguarded_param_variant (int depth)
+{
+ /* We fail to report this: we see that depth is being decremented,
+ but don't notice that every path through the function is
+ recursing. */
+ test_unguarded_param_variant (depth - 1); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */
+}
+
+int g;
+
+void test_global_variant ()
+{
+ if (g-- > 0)
+ test_global_variant (); /* { dg-bogus "infinite recursion" } */
+}
+
+/* This is a bounded recursion, as "n" is decremented before recursing... */
+
+int test_while_do_predecrement_param (int n)
+{
+ int x = 0;
+ while (n)
+ x += test_while_do_predecrement_param (--n); /* { dg-bogus "infinite recursion" } */
+ return x;
+}
+
+/* ...whereas this one is unbounded, as "n" is decremented *after* the
+ recursive call, and so is repeatedly called with the same value. */
+
+int test_while_do_postdecrement_param (int n)
+{
+ int x = 0;
+ while (n)
+ x += test_while_do_postdecrement_param (n--); /* { dg-warning "infinite recursion" } */
+ return x;
+}
+/* This is a bounded recursion, as "n" is decremented before recursing... */
+
+int test_do_while_predecrement_param (int n)
+{
+ int x = 0;
+ do
+ x += test_do_while_predecrement_param (--n); /* { dg-bogus "infinite recursion" } */
+ while (--n);
+ return x;
+}
+
+/* ...whereas this one is unbounded, as "n" is decremented *after* the
+ recursive call, and so is repeatedly called with the same value. */
+
+int test_do_while_postdecrement_param (int n)
+{
+ int x = 0;
+ do
+ x += test_do_while_postdecrement_param (n--); /* { dg-warning "infinite recursion" } */
+ while (--n);
+ return x;
+}
+
+/* Various cases of decrementing "n" as the recursion proceeds where
+ not every path recurses, but we're not actually checking "n", so
+ if "flag" is true it's an infinite recursion. */
+
+void test_partially_guarded_postdecrement (int flag, int n)
+{
+ /* We catch this; the "n--" means we recurse with the
+ same value for the 2nd param. */
+ if (flag) /* { dg-message "when 'flag != 0'" } */
+ test_partially_guarded_postdecrement (flag, n--); /* { dg-warning "infinite recursion" } */
+}
+
+void test_partially_guarded_predecrement (int flag, int n)
+{
+ /* We fail to report this; we see that "n" is changing,
+ though it isn't relevant to whether we recurse. */
+ if (flag)
+ test_partially_guarded_predecrement (flag, --n); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */
+}
+
+void test_partially_guarded_subtract (int flag, int n)
+{
+ /* We fail to report this; we see that "n" is changing,
+ though it isn't relevant to whether we recurse. */
+ if (flag)
+ test_partially_guarded_subtract (flag, n - 1); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */
+}
new file mode 100644
@@ -0,0 +1,18 @@
+/* { dg-additional-options "-fno-analyzer-call-summaries -Wno-analyzer-too-complex" } */
+
+struct node
+{
+ struct node *left;
+ struct node *right;
+ int val;
+};
+
+int sum (struct node *n)
+{
+ int result = 0;
+ if (n->left)
+ result += sum (n->left); /* { dg-bogus "infinite recursion" } */
+ if (n->right)
+ result += sum (n->right); /* { dg-bogus "infinite recursion" } */
+ return result;
+}
new file mode 100644
@@ -0,0 +1,25 @@
+/* { dg-additional-options "-fno-analyzer-call-summaries -Wno-analyzer-too-complex" } */
+
+/* A two-deep mutual recursion, and failing to walk a list,
+ but with a depth limit, thus not an infinite recursion (assuming a
+ suitable depth limit). */
+
+struct node
+{
+ struct node *child;
+};
+
+void foo (struct node *f, int depth);
+
+void bar (struct node *b, int depth)
+{
+ foo (b, depth); /* { dg-bogus "infinite recursion" } */
+}
+
+void foo (struct node *f, int depth)
+{
+ if (f->child && depth > 0)
+ /* Bug: should have recursed to f->child, not to f,
+ but we assume that the depth limit should save us. */
+ bar (f, depth - 1); /* { dg-bogus "infinite recursion" } */
+}
new file mode 100644
@@ -0,0 +1,22 @@
+/* { dg-additional-options "-fno-analyzer-call-summaries -Wno-analyzer-too-complex" } */
+
+/* A two-deep mutual recursion, walking a singly-linked list,
+ with a depth limit. */
+
+struct node
+{
+ struct node *child;
+};
+
+void foo (struct node *f, int depth);
+
+void bar (struct node *b, int depth)
+{
+ foo (b, depth); /* { dg-bogus "infinite recursion" } */
+}
+
+void foo (struct node *f, int depth)
+{
+ if (f->child && depth > 0)
+ bar (f->child, depth - 1); /* { dg-bogus "infinite recursion" } */
+}
new file mode 100644
@@ -0,0 +1,23 @@
+/* { dg-additional-options "-fno-analyzer-call-summaries -Wno-analyzer-too-complex" } */
+
+/* A two-deep mutual recursion, with no limit, and
+ failing to walk the list, thus leading to an infinite recursion. */
+
+struct node
+{
+ struct node *child;
+};
+
+void foo (struct node *f);
+
+void bar (struct node *b)
+{
+ foo (b); /* { dg-warning "infinite recursion" } */
+}
+
+void foo (struct node *f)
+{
+ if (f->child)
+ /* Bug: should have recursed to f->child, not to f. */
+ bar (f); /* { dg-warning "infinite recursion" } */
+}
new file mode 100644
@@ -0,0 +1,22 @@
+/* { dg-additional-options "-fno-analyzer-call-summaries -Wno-analyzer-too-complex" } */
+
+/* A two-deep mutual recursion, walking a linked list (and thus presumably
+ terminating), with no explicit depth limit. */
+
+struct node
+{
+ struct node *child;
+};
+
+void foo (struct node *f);
+
+void bar (struct node *b)
+{
+ foo (b); /* { dg-bogus "infinite recursion" } */
+}
+
+void foo (struct node *f)
+{
+ if (f->child)
+ bar (f->child); /* { dg-bogus "infinite recursion" } */
+}
new file mode 100644
@@ -0,0 +1,221 @@
+/* Adapted from gcc.dg/Winfinite-recursion.c. */
+
+#define NORETURN __attribute__ ((noreturn))
+
+typedef __SIZE_TYPE__ size_t;
+
+extern void abort (void);
+extern void exit (int);
+
+extern int ei;
+int (*pfi_v)(void);
+
+
+/* Make sure the warning doesn't assume every call has a DECL. */
+
+int nowarn_pfi_v (void)
+{
+ return pfi_v ();
+}
+
+
+int warn_fi_v (void)
+{
+ return warn_fi_v (); // { dg-warning "-Wanalyzer-infinite-recursion" }
+}
+
+/* Verify #pragma suppression works. */
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wanalyzer-infinite-recursion"
+
+int suppress_warn_fi_v (void)
+{
+ return suppress_warn_fi_v ();
+}
+
+#pragma GCC diagnostic pop
+
+
+int nowarn_fi_v (void)
+{
+ if (ei++ == 0)
+ return nowarn_fi_v ();
+ return 0;
+}
+
+/* -Winfinite-recursion warns for this, but
+ -Wanalyzer-infinite-recursion doesn't. */
+
+int warn_if_i (int i)
+{
+ if (i > 0)
+ return warn_if_i (--i);
+ else if (i < 0)
+ return warn_if_i (-i);
+ else
+ return warn_if_i (7);
+}
+
+
+int nowarn_if_i (int i)
+{
+ if (i > 0)
+ return nowarn_if_i (--i);
+ else if (i < 0)
+ return nowarn_if_i (-i);
+ else
+ return -1;
+}
+
+int nowarn_switch (int i, int a[])
+{
+ switch (i)
+ {
+ case 0: return nowarn_switch (a[3], a + 1);
+ case 1: return nowarn_switch (a[5], a + 2);
+ case 2: return nowarn_switch (a[7], a + 3);
+ case 3: return nowarn_switch (a[9], a + 4);
+ }
+ return 77;
+}
+
+/* -Winfinite-recursion warns for this, but
+ -Wanalyzer-infinite-recursion doesn't. */
+
+int warn_switch (int i, int a[])
+{
+ switch (i)
+ {
+ case 0: return warn_switch (a[3], a + 1);
+ case 1: return warn_switch (a[5], a + 2);
+ case 2: return warn_switch (a[7], a + 3);
+ case 3: return warn_switch (a[9], a + 4);
+ default: return warn_switch (a[1], a + 5);
+ }
+}
+
+NORETURN void fnoreturn (void);
+
+/* Verify there's no warning for a function that doesn't return. */
+int nowarn_call_noret (void)
+{
+ fnoreturn ();
+}
+
+int warn_call_noret_r (void)
+{
+ warn_call_noret_r (); // { dg-warning "-Wanalyzer-infinite-recursion" }
+ fnoreturn ();
+}
+
+/* -Winfinite-recursion warns for this, but
+ -Wanalyzer-infinite-recursion doesn't. */
+
+int
+warn_noret_call_abort_r (char *s, int n)
+{
+ if (!s)
+ abort ();
+
+ if (n > 7)
+ abort ();
+
+ return n + warn_noret_call_abort_r (s, n - 1);
+}
+
+NORETURN void nowarn_noret_call_abort_r (int n)
+{
+ if (n > 7)
+ abort ();
+
+ nowarn_noret_call_abort_r (n - 1);
+}
+
+/* -Winfinite-recursion warns for this, but
+ -Wanalyzer-infinite-recursion doesn't. */
+
+int warn_call_abort_r (int n)
+{
+ n += warn_call_abort_r (n - 1);
+ if (n > 7) // unreachable
+ abort ();
+ return n;
+}
+
+
+/* -Winfinite-recursion warns for this, but
+ -Wanalyzer-infinite-recursion doesn't. */
+
+int warn_call_exit_r (int n)
+{
+ n += warn_call_exit_r (n - 1);
+ if (n > 7)
+ exit (0);
+ return n;
+}
+
+struct __jmp_buf_tag { };
+typedef struct __jmp_buf_tag jmp_buf[1];
+
+extern jmp_buf jmpbuf;
+
+/* A call to longjmp() breaks infinite recursion. Verify it suppresses
+ the warning. */
+
+int nowarn_call_longjmp_r (int n)
+{
+ if (n > 7)
+ __builtin_longjmp (jmpbuf, 1);
+ return n + nowarn_call_longjmp_r (n - 1);
+}
+
+/* -Winfinite-recursion warns for this, but
+ -Wanalyzer-infinite-recursion doesn't. */
+
+int warn_call_longjmp_r (int n)
+{
+ n += warn_call_longjmp_r (n - 1);
+ if (n > 7)
+ __builtin_longjmp (jmpbuf, 1);
+ return n;
+}
+
+
+struct __sigjmp_buf_tag { };
+typedef struct __sigjmp_buf_tag sigjmp_buf[1];
+
+extern sigjmp_buf sigjmpbuf;
+
+/* GCC has no __builtin_siglongjmp(). */
+extern void siglongjmp (sigjmp_buf, int);
+
+/* A call to longjmp() breaks infinite recursion. Verify it suppresses
+ the warning. */
+
+int nowarn_call_siglongjmp_r (int n)
+{
+ if (n > 7)
+ siglongjmp (sigjmpbuf, 1);
+ return n + nowarn_call_siglongjmp_r (n - 1);
+}
+
+/* -Winfinite-recursion doesn't warn for this unbounded recursion, but
+ -Wanalyzer-infinite-recursion does. */
+
+int nowarn_while_do_call_r (int n)
+{
+ int z = 0;
+ while (n)
+ z += nowarn_while_do_call_r (n--); // { dg-warning "-Wanalyzer-infinite-recursion" }
+ return z;
+}
+
+int warn_do_while_call_r (int n)
+{
+ int z = 0;
+ do
+ z += warn_do_while_call_r (n); // { dg-warning "-Wanalyzer-infinite-recursion" }
+ while (--n);
+ return z;
+}
new file mode 100644
@@ -0,0 +1,27 @@
+typedef __SIZE_TYPE__ size_t;
+
+int test_alloca_1 (void)
+{
+ void *buf = __builtin_alloca (1024);
+ return test_alloca_1 (); /* { dg-warning "-Wanalyzer-infinite-recursion" } */
+}
+
+int test_alloca_2 (size_t n)
+{
+ void *buf = __builtin_alloca (n);
+ return test_alloca_2 (n); /* { dg-warning "-Wanalyzer-infinite-recursion" } */
+}
+
+int test_alloca_3 (size_t n)
+{
+ void *buf = __builtin_alloca (n);
+ return test_alloca_2 (n - 1);
+}
+
+int test_alloca_4 (size_t n)
+{
+ void *buf = __builtin_alloca (n);
+ if (n > 0)
+ return test_alloca_2 (n - 1);
+ return 42;
+}
new file mode 100644
@@ -0,0 +1,116 @@
+/* A copy of infinite-recursion-2.c, to see what inlining does to the IR
+ when we see it.
+
+ Many cases get converted by the optimizer into iteration, and
+ into infinite loops, sometimes trivial ones.
+
+ Right now this is a documented limitation of the warning, but perhaps
+ could be readdressed by moving the analyzer earlier. */
+
+/* { dg-additional-options "-O3" } */
+
+void test_direct (void)
+{
+ test_direct (); /* Ideally would warn here, but it becomes an infinite loop. */
+}
+
+void test_guarded (int flag)
+{
+ if (flag)
+ test_guarded (flag); /* Ideally would warn here, but it becomes an infinite loop. */
+}
+
+void test_flipped_guard (int flag)
+{
+ if (flag)
+ test_guarded (!flag);
+}
+
+void test_param_variant (int depth)
+{
+ if (depth > 0)
+ test_param_variant (depth - 1);
+}
+
+void test_unguarded_param_variant (int depth)
+{
+ test_unguarded_param_variant (depth - 1); /* Ideally would warn here, but it becomes an infinite loop. */
+}
+
+int g;
+
+void test_global_variant ()
+{
+ if (g-- > 0)
+ test_global_variant ();
+}
+
+/* This is a bounded recursion, as "n" is decremented before recursing... */
+
+int test_while_do_predecrement_param (int n)
+{
+ int x = 0;
+ while (n)
+ x += test_while_do_predecrement_param (--n);
+ return x;
+}
+
+/* ...whereas this one is unbounded, as "n" is decremented *after* the
+ recursive call, and so is repeatedly called with the same value. */
+
+int test_while_do_postdecrement_param (int n)
+{
+ int x = 0;
+ while (n)
+ x += test_while_do_postdecrement_param (n--); /* { dg-warning "infinite recursion" } */
+ return x;
+}
+/* This is a bounded recursion, as "n" is decremented before recursing... */
+
+int test_do_while_predecrement_param (int n)
+{
+ int x = 0;
+ do
+ x += test_do_while_predecrement_param (--n);
+ while (--n);
+ return x;
+}
+
+/* ...whereas this one is unbounded, as "n" is decremented *after* the
+ recursive call, and so is repeatedly called with the same value. */
+
+int test_do_while_postdecrement_param (int n)
+{
+ int x = 0;
+ do
+ x += test_do_while_postdecrement_param (n--); /* { dg-warning "infinite recursion" } */
+ while (--n);
+ return x;
+}
+
+/* Various cases of decrementing "n" as the recursion proceeds where
+ not every path recurses, but we're not actually checking "n", so
+ if "flag" is true it's an infinite recursion. */
+
+void test_partially_guarded_postdecrement (int flag, int n)
+{
+ /* Ideally we'd catch this, but it becomes an infinite loop. */
+ if (flag)
+ test_partially_guarded_postdecrement (flag, n--);
+}
+
+void test_partially_guarded_predecrement (int flag, int n)
+{
+ /* We fail to report this; we see that "n" is changing,
+ though it isn't relevant to whether we recurse. */
+ if (flag)
+ test_partially_guarded_predecrement (flag, --n); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */
+}
+
+void test_partially_guarded_subtract (int flag, int n)
+{
+ /* We fail to report this; we see that "n" is changing,
+ though it isn't relevant to whether we recurse. */
+ if (flag)
+ test_partially_guarded_subtract (flag, n - 1); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */
+}
new file mode 100644
@@ -0,0 +1,41 @@
+/* Integration test of how the execution path looks for
+ -Wanalyzer-infinite-recursion. */
+
+/* { dg-additional-options "-fdiagnostics-show-path-depths" } */
+/* { dg-additional-options "-fdiagnostics-path-format=inline-events -fdiagnostics-show-caret" } */
+
+void foo (int flag)
+{
+ if (flag)
+ foo (flag); /* { dg-warning "infinite recursion" } */
+}
+
+/* { dg-begin-multiline-output "" }
+ foo (flag);
+ ^~~~~~~~~~
+ 'foo': events 1-4 (depth 1)
+ |
+ | void foo (int flag)
+ | ^~~
+ | |
+ | (1) initial entry to 'foo'
+ |
+ | if (flag)
+ | ~
+ | |
+ | (2) following 'true' branch (when 'flag != 0')...
+ | foo (flag);
+ | ~~~~~~~~~~
+ | |
+ | (3) ...to here
+ | (4) calling 'foo' from 'foo'
+ |
+ +--> 'foo': events 5-6 (depth 2)
+ |
+ | void foo (int flag)
+ | ^~~
+ | |
+ | (5) recursive entry to 'foo'; previously entered at (1)
+ | (6) apparently infinite recursion
+ |
+ { dg-end-multiline-output "" } */
new file mode 100644
@@ -0,0 +1,93 @@
+/* Integration test of how the execution path looks for
+ -Wanalyzer-infinite-recursion. */
+
+/* { dg-additional-options "-fdiagnostics-show-path-depths" } */
+/* { dg-additional-options "-fdiagnostics-path-format=inline-events -fdiagnostics-show-caret" } */
+
+void mutual_2 (void);
+
+void mutual_1 (void)
+{
+ mutual_2 (); /* { dg-warning "infinite recursion" } */
+}
+
+void mutual_2 (void)
+{
+ mutual_1 (); /* { dg-warning "infinite recursion" } */
+}
+
+
+/* { dg-begin-multiline-output "" }
+ mutual_2 ();
+ ^~~~~~~~~~~
+ 'mutual_2': events 1-2 (depth 1)
+ |
+ | void mutual_2 (void)
+ | ^~~~~~~~
+ | |
+ | (1) initial entry to 'mutual_2'
+ |
+ | mutual_1 ();
+ | ~~~~~~~~~~~
+ | |
+ | (2) calling 'mutual_1' from 'mutual_2'
+ |
+ +--> 'mutual_1': events 3-4 (depth 2)
+ |
+ | void mutual_1 (void)
+ | ^~~~~~~~
+ | |
+ | (3) entry to 'mutual_1'
+ |
+ | mutual_2 ();
+ | ~~~~~~~~~~~
+ | |
+ | (4) calling 'mutual_2' from 'mutual_1'
+ |
+ +--> 'mutual_2': events 5-6 (depth 3)
+ |
+ | void mutual_2 (void)
+ | ^~~~~~~~
+ | |
+ | (5) recursive entry to 'mutual_2'; previously entered at (1)
+ | (6) apparently infinite chain of mutually-recursive function calls, consuming 2 stack frames per recursion
+ |
+ { dg-end-multiline-output "" } */
+
+
+/* { dg-begin-multiline-output "" }
+ mutual_1 ();
+ ^~~~~~~~~~~
+ 'mutual_1': events 1-2 (depth 1)
+ |
+ | void mutual_1 (void)
+ | ^~~~~~~~
+ | |
+ | (1) initial entry to 'mutual_1'
+ |
+ | mutual_2 ();
+ | ~~~~~~~~~~~
+ | |
+ | (2) calling 'mutual_2' from 'mutual_1'
+ |
+ +--> 'mutual_2': events 3-4 (depth 2)
+ |
+ | void mutual_2 (void)
+ | ^~~~~~~~
+ | |
+ | (3) entry to 'mutual_2'
+ |
+ | mutual_1 ();
+ | ~~~~~~~~~~~
+ | |
+ | (4) calling 'mutual_1' from 'mutual_2'
+ |
+ +--> 'mutual_1': events 5-6 (depth 3)
+ |
+ | void mutual_1 (void)
+ | ^~~~~~~~
+ | |
+ | (5) recursive entry to 'mutual_1'; previously entered at (1)
+ | (6) apparently infinite chain of mutually-recursive function calls, consuming 2 stack frames per recursion
+ |
+ { dg-end-multiline-output "" } */
new file mode 100644
@@ -0,0 +1,34 @@
+int test_variadic_1 (int n, ...)
+{
+ __builtin_va_list args;
+ int total =0;
+ int i;
+
+ __builtin_va_start(args, n);
+
+ for (i = 0; i < n; i++)
+ total += __builtin_va_arg(args, int);
+
+ __builtin_va_end(args);
+
+ return total;
+}
+
+int test_variadic_2 (int n, ...)
+{
+ return test_variadic_2 (n, 42); /* { dg-warning "-Wanalyzer-infinite-recursion" } */
+}
+
+int test_variadic_3 (int n, ...)
+{
+ if (n > 0) /* { dg-message "when 'n > 0'" } */
+ return test_variadic_3 (n, 42); /* { dg-warning "-Wanalyzer-infinite-recursion" } */
+ return 0;
+}
+
+int test_variadic_4 (int n, ...)
+{
+ if (n > 0)
+ return test_variadic_4 (n - 1, 42);
+ return 0;
+}
@@ -11,7 +11,7 @@ void test(int flag)
marker_B();
/* Recurse, infinitely, as it happens: */
- test(flag);
+ test(flag); /* { dg-warning "infinite recursion" } */
marker_C();
}
@@ -30,26 +30,26 @@ void mutual_test_1 (int flag)
{
marker_A ();
if (flag)
- mutual_test_2 (flag);
+ mutual_test_2 (flag); /* { dg-warning "infinite recursion" } */
}
void mutual_test_2 (int flag)
{
marker_B ();
if (flag)
- mutual_test_3 (flag);
+ mutual_test_3 (flag); /* { dg-warning "infinite recursion" } */
}
void mutual_test_3 (int flag)
{
marker_C ();
if (flag)
- mutual_test_4 (flag);
+ mutual_test_4 (flag); /* { dg-warning "infinite recursion" } */
}
void mutual_test_4 (int flag)
{
marker_D ();
if (flag)
- mutual_test_1 (flag);
+ mutual_test_1 (flag); /* { dg-warning "infinite recursion" } */
}
@@ -3,5 +3,5 @@
void recursive_free (void *ptr)
{
free (ptr); /* { dg-warning "double-'free' of 'ptr'" } */
- recursive_free (ptr);
+ recursive_free (ptr); /* { dg-warning "infinite recursion" } */
}
@@ -13,5 +13,5 @@ foo(_Float32 k) {
f /= (_Complex char)__builtin_llround(g);
k /= (cf32)__builtin_copysignf(0, i);
bar(f + k);
- foo(0);
+ foo(0); /* { dg-warning "infinite recursion" } */
}
@@ -15,5 +15,5 @@ foo(u32 u, __int128 i) {
u /= (_Complex short)s;
u32 r = u + c;
bar(r);
- foo(0, 0);
+ foo(0, 0); /* { dg-warning "infinite recursion" } */
}
@@ -5,5 +5,5 @@ struct vj {
void
setjmp (struct vj pl)
{
- setjmp (pl);
+ setjmp (pl); /* { dg-warning "infinite recursion" } */
}
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. Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as r13-3912-g12c583a2a3da79. 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> --- gcc/Makefile.in | 1 + gcc/analyzer/analyzer.opt | 4 + gcc/analyzer/call-string.cc | 16 + gcc/analyzer/call-string.h | 2 + gcc/analyzer/checker-path.cc | 23 +- gcc/analyzer/checker-path.h | 8 +- gcc/analyzer/diagnostic-manager.cc | 11 +- gcc/analyzer/engine.cc | 7 +- gcc/analyzer/exploded-graph.h | 5 + gcc/analyzer/infinite-recursion.cc | 481 ++++++++++++++++++ gcc/analyzer/pending-diagnostic.cc | 30 ++ gcc/analyzer/pending-diagnostic.h | 18 + .../options-that-control-static-analysis.rst | 28 + ...ptions-to-request-or-suppress-warnings.rst | 4 + .../g++.dg/analyzer/infinite-recursion-1.C | 84 +++ .../g++.dg/analyzer/infinite-recursion-2.C | 74 +++ .../g++.dg/analyzer/infinite-recursion-3.C | 62 +++ .../gcc.dg/analyzer/infinite-recursion-2.c | 109 ++++ .../gcc.dg/analyzer/infinite-recursion-3.c | 18 + .../infinite-recursion-4-limited-buggy.c | 25 + .../analyzer/infinite-recursion-4-limited.c | 22 + .../infinite-recursion-4-unlimited-buggy.c | 23 + .../analyzer/infinite-recursion-4-unlimited.c | 22 + .../gcc.dg/analyzer/infinite-recursion-5.c | 221 ++++++++ .../analyzer/infinite-recursion-alloca.c | 27 + .../analyzer/infinite-recursion-inlining.c | 116 +++++ .../analyzer/infinite-recursion-multiline-1.c | 41 ++ .../analyzer/infinite-recursion-multiline-2.c | 93 ++++ .../analyzer/infinite-recursion-variadic.c | 34 ++ .../gcc.dg/analyzer/infinite-recursion.c | 10 +- gcc/testsuite/gcc.dg/analyzer/malloc-ipa-12.c | 2 +- gcc/testsuite/gcc.dg/analyzer/pr105365.c | 2 +- gcc/testsuite/gcc.dg/analyzer/pr105366.c | 2 +- gcc/testsuite/gcc.dg/analyzer/pr97029.c | 2 +- 34 files changed, 1590 insertions(+), 37 deletions(-) create mode 100644 gcc/analyzer/infinite-recursion.cc create mode 100644 gcc/testsuite/g++.dg/analyzer/infinite-recursion-1.C create mode 100644 gcc/testsuite/g++.dg/analyzer/infinite-recursion-2.C create mode 100644 gcc/testsuite/g++.dg/analyzer/infinite-recursion-3.C create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-2.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-3.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-limited-buggy.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-limited.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-unlimited-buggy.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-unlimited.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-5.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-alloca.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-inlining.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-multiline-1.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-multiline-2.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-variadic.c