diff options
34 files changed, 1590 insertions, 37 deletions
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 4982012..246a85a 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -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 \ diff --git a/gcc/analyzer/analyzer.opt b/gcc/analyzer/analyzer.opt index 58ad326..518a5d4 100644 --- a/gcc/analyzer/analyzer.opt +++ b/gcc/analyzer/analyzer.opt @@ -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. diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc index 5caf921..d78ae81 100644 --- a/gcc/analyzer/call-string.cc +++ b/gcc/analyzer/call-string.cc @@ -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. 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: diff --git a/gcc/analyzer/checker-path.cc b/gcc/analyzer/checker-path.cc index ffab91c..39de745 100644 --- a/gcc/analyzer/checker-path.cc +++ b/gcc/analyzer/checker-path.cc @@ -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) { diff --git a/gcc/analyzer/checker-path.h b/gcc/analyzer/checker-path.h index 46f4875..53e6bff 100644 --- a/gcc/analyzer/checker-path.h +++ b/gcc/analyzer/checker-path.h @@ -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 diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index f82dd3a..9b319c3 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -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) diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index fc90b49..d0595ef 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -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. diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index de927e6..a4cbc8f 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -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; diff --git a/gcc/analyzer/infinite-recursion.cc b/gcc/analyzer/infinite-recursion.cc new file mode 100644 index 0000000..7055926 --- /dev/null +++ b/gcc/analyzer/infinite-recursion.cc @@ -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)); +} diff --git a/gcc/analyzer/pending-diagnostic.cc b/gcc/analyzer/pending-diagnostic.cc index fdbe615..9216a22 100644 --- a/gcc/analyzer/pending-diagnostic.cc +++ b/gcc/analyzer/pending-diagnostic.cc @@ -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 */ diff --git a/gcc/analyzer/pending-diagnostic.h b/gcc/analyzer/pending-diagnostic.h index 6ca8ab9..0e91e71 100644 --- a/gcc/analyzer/pending-diagnostic.h +++ b/gcc/analyzer/pending-diagnostic.h @@ -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. */ diff --git a/gcc/doc/gcc/gcc-command-options/options-that-control-static-analysis.rst b/gcc/doc/gcc/gcc-command-options/options-that-control-static-analysis.rst index 09bf049..32a626c 100644 --- a/gcc/doc/gcc/gcc-command-options/options-that-control-static-analysis.rst +++ b/gcc/doc/gcc/gcc-command-options/options-that-control-static-analysis.rst @@ -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 diff --git a/gcc/doc/gcc/gcc-command-options/options-to-request-or-suppress-warnings.rst b/gcc/doc/gcc/gcc-command-options/options-to-request-or-suppress-warnings.rst index a4a2888..b57f478 100644 --- a/gcc/doc/gcc/gcc-command-options/options-to-request-or-suppress-warnings.rst +++ b/gcc/doc/gcc/gcc-command-options/options-to-request-or-suppress-warnings.rst @@ -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`. diff --git a/gcc/testsuite/g++.dg/analyzer/infinite-recursion-1.C b/gcc/testsuite/g++.dg/analyzer/infinite-recursion-1.C new file mode 100644 index 0000000..33f3b33 --- /dev/null +++ b/gcc/testsuite/g++.dg/analyzer/infinite-recursion-1.C @@ -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 (); +} diff --git a/gcc/testsuite/g++.dg/analyzer/infinite-recursion-2.C b/gcc/testsuite/g++.dg/analyzer/infinite-recursion-2.C new file mode 100644 index 0000000..c582fbf --- /dev/null +++ b/gcc/testsuite/g++.dg/analyzer/infinite-recursion-2.C @@ -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>(); +} diff --git a/gcc/testsuite/g++.dg/analyzer/infinite-recursion-3.C b/gcc/testsuite/g++.dg/analyzer/infinite-recursion-3.C new file mode 100644 index 0000000..a749f62 --- /dev/null +++ b/gcc/testsuite/g++.dg/analyzer/infinite-recursion-3.C @@ -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; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-2.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-2.c new file mode 100644 index 0000000..f0ab130 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-2.c @@ -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 *-*-* } } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-3.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-3.c new file mode 100644 index 0000000..68c4fa3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-3.c @@ -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; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-limited-buggy.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-limited-buggy.c new file mode 100644 index 0000000..a71b902 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-limited-buggy.c @@ -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" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-limited.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-limited.c new file mode 100644 index 0000000..55326d2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-limited.c @@ -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" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-unlimited-buggy.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-unlimited-buggy.c new file mode 100644 index 0000000..7ed1a2b --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-unlimited-buggy.c @@ -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" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-unlimited.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-unlimited.c new file mode 100644 index 0000000..bdb54a3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-4-unlimited.c @@ -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" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-5.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-5.c new file mode 100644 index 0000000..bf20639 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-5.c @@ -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; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-alloca.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-alloca.c new file mode 100644 index 0000000..8c50631 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-alloca.c @@ -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; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-inlining.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-inlining.c new file mode 100644 index 0000000..c885c92 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-inlining.c @@ -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 *-*-* } } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-multiline-1.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-multiline-1.c new file mode 100644 index 0000000..e236dd4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-multiline-1.c @@ -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 "" } */ diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-multiline-2.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-multiline-2.c new file mode 100644 index 0000000..2c69dd5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-multiline-2.c @@ -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 "" } */ diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-variadic.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-variadic.c new file mode 100644 index 0000000..eafbeba --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-variadic.c @@ -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; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion.c index b770e12..6b7d25c 100644 --- a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion.c +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion.c @@ -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" } */ } diff --git a/gcc/testsuite/gcc.dg/analyzer/malloc-ipa-12.c b/gcc/testsuite/gcc.dg/analyzer/malloc-ipa-12.c index fce5437..3813c9a 100644 --- a/gcc/testsuite/gcc.dg/analyzer/malloc-ipa-12.c +++ b/gcc/testsuite/gcc.dg/analyzer/malloc-ipa-12.c @@ -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" } */ } diff --git a/gcc/testsuite/gcc.dg/analyzer/pr105365.c b/gcc/testsuite/gcc.dg/analyzer/pr105365.c index aa576d0..c2e6b2e 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr105365.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr105365.c @@ -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" } */ } diff --git a/gcc/testsuite/gcc.dg/analyzer/pr105366.c b/gcc/testsuite/gcc.dg/analyzer/pr105366.c index 3dba870..af8a2c4 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr105366.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr105366.c @@ -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" } */ } diff --git a/gcc/testsuite/gcc.dg/analyzer/pr97029.c b/gcc/testsuite/gcc.dg/analyzer/pr97029.c index e3b4531..2ab2d41 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr97029.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr97029.c @@ -5,5 +5,5 @@ struct vj { void setjmp (struct vj pl) { - setjmp (pl); + setjmp (pl); /* { dg-warning "infinite recursion" } */ } |