| /* Detection of infinite recursion. | |
| Copyright (C) 2022-2026 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 "analyzer/common.h" | |
| #include "cfg.h" | |
| #include "gimple-iterator.h" | |
| #include "gimple-pretty-print.h" | |
| #include "cgraph.h" | |
| #include "digraph.h" | |
| #include "diagnostics/sarif-sink.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 "analyzer/supergraph.h" | |
| #include "analyzer/program-state.h" | |
| #include "analyzer/exploded-graph.h" | |
| #include "analyzer/checker-path.h" | |
| #include "analyzer/feasible-graph.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 (nullptr) | |
| {} | |
| 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 (diagnostic_emission_context &ctxt) final override | |
| { | |
| /* "CWE-674: Uncontrolled Recursion". */ | |
| ctxt.add_cwe (674); | |
| return ctxt.warn ("infinite recursion"); | |
| } | |
| bool | |
| describe_final_event (pretty_printer &pp, | |
| const evdesc::final_event &) final override | |
| { | |
| const int frames_consumed = (m_new_entry_enode->get_stack_depth () | |
| - m_prev_entry_enode->get_stack_depth ()); | |
| if (frames_consumed > 1) | |
| pp_printf (&pp, | |
| "apparently infinite chain of mutually-recursive function" | |
| " calls, consuming %i stack frames per recursion", | |
| frames_consumed); | |
| else | |
| pp_string (&pp, "apparently infinite recursion"); | |
| return true; | |
| } | |
| void | |
| add_function_entry_event (const exploded_edge &eedge, | |
| checker_path *emission_path, | |
| const state_transition_at_call *state_trans) 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 program_state &dst_state, | |
| const infinite_recursion_diagnostic &pd, | |
| bool topmost) | |
| : function_entry_event (event_loc_info (dst_point), | |
| dst_state, | |
| nullptr), | |
| m_pd (pd), | |
| m_topmost (topmost) | |
| { | |
| } | |
| void | |
| print_desc (pretty_printer &pp) const final override | |
| { | |
| if (m_topmost) | |
| { | |
| if (m_pd.m_prev_entry_event | |
| && m_pd.m_prev_entry_event->get_id_ptr ()->known_p ()) | |
| pp_printf (&pp, | |
| "recursive entry to %qE; previously entered at %@", | |
| m_effective_fndecl, | |
| m_pd.m_prev_entry_event->get_id_ptr ()); | |
| else | |
| pp_printf (&pp, | |
| "recursive entry to %qE", | |
| m_effective_fndecl); | |
| } | |
| else | |
| pp_printf (&pp, | |
| "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 == nullptr); | |
| std::unique_ptr<checker_event> prev_entry_event | |
| = std::make_unique <recursive_function_entry_event> | |
| (dst_point, | |
| dst_node->get_state (), | |
| *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 | |
| (std::make_unique<recursive_function_entry_event> | |
| (dst_point, dst_node->get_state (), *this, true)); | |
| else | |
| pending_diagnostic::add_function_entry_event (eedge, emission_path, | |
| state_trans); | |
| } | |
| /* 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 *enode, | |
| const event_loc_info &, | |
| tree, | |
| state_machine::state_t, | |
| checker_path *emission_path) final override | |
| { | |
| gcc_assert (m_new_entry_enode); | |
| emission_path->add_event | |
| (std::make_unique<warning_event> | |
| (event_loc_info (m_new_entry_enode->get_supernode | |
| ()->get_location (), | |
| m_callee_fndecl, | |
| m_new_entry_enode->get_stack_depth ()), | |
| enode, | |
| nullptr, nullptr, nullptr)); | |
| } | |
| /* Reject paths in which conjured svalues have affected control flow | |
| since m_prev_entry_enode. */ | |
| bool check_valid_fpath_p (const feasible_node &final_fnode) | |
| const final override | |
| { | |
| /* Reject paths in which calls with unknown side effects have occurred | |
| since m_prev_entry_enode. | |
| Find num calls with side effects. Walk backward until we reach the | |
| pref */ | |
| gcc_assert (final_fnode.get_inner_node () == m_new_entry_enode); | |
| /* FG is actually a tree. Walk backwards from FINAL_FNODE until we | |
| reach the prev_entry_enode (or the origin). */ | |
| const feasible_node *iter_fnode = &final_fnode; | |
| while (iter_fnode->get_inner_node ()->m_index != 0) | |
| { | |
| gcc_assert (iter_fnode->m_preds.length () == 1); | |
| feasible_edge *pred_fedge | |
| = static_cast <feasible_edge *> (iter_fnode->m_preds[0]); | |
| /* Determine if conjured svalues have affected control flow | |
| since the prev entry node. */ | |
| if (fedge_uses_conjured_value_p (pred_fedge)) | |
| /* If so, then reject this diagnostic. */ | |
| return false; | |
| iter_fnode = static_cast <feasible_node *> (pred_fedge->m_src); | |
| if (iter_fnode->get_inner_node () == m_prev_entry_enode) | |
| /* Accept this diagnostic. */ | |
| return true; | |
| } | |
| /* We shouldn't get here; if we do, reject the diagnostic. */ | |
| gcc_unreachable (); | |
| return false; | |
| } | |
| void | |
| maybe_add_sarif_properties (diagnostics::sarif_object &result_obj) | |
| const final override | |
| { | |
| auto &props = result_obj.get_or_create_properties (); | |
| #define PROPERTY_PREFIX "gcc/analyzer/infinite_recursion_diagnostic/" | |
| props.set_integer (PROPERTY_PREFIX "prev_entry_enode", | |
| m_prev_entry_enode->m_index); | |
| props.set_integer (PROPERTY_PREFIX "new_entry_enode", | |
| m_new_entry_enode->m_index); | |
| #undef PROPERTY_PREFIX | |
| } | |
| private: | |
| /* Return true iff control flow along FEDGE was affected by | |
| a conjured_svalue. */ | |
| static bool fedge_uses_conjured_value_p (feasible_edge *fedge) | |
| { | |
| const exploded_edge *eedge = fedge->get_inner_edge (); | |
| const superedge *sedge = eedge->m_sedge; | |
| if (!sedge) | |
| return false; | |
| auto op = sedge->get_op (); | |
| if (!op) | |
| return false; | |
| const control_flow_op *ctrlflow_op = op->dyn_cast_control_flow_op (); | |
| if (!ctrlflow_op) | |
| return false; | |
| const gimple &last_stmt = ctrlflow_op->get_ctrlflow_stmt (); | |
| const feasible_node *dst_fnode | |
| = static_cast<const feasible_node *> (fedge->m_dest); | |
| const region_model &model = dst_fnode->get_state ().get_model (); | |
| if (const gcond *cond_stmt = dyn_cast <const gcond *> (&last_stmt)) | |
| { | |
| if (expr_uses_conjured_value_p (model, gimple_cond_lhs (cond_stmt))) | |
| return true; | |
| if (expr_uses_conjured_value_p (model, gimple_cond_rhs (cond_stmt))) | |
| return true; | |
| } | |
| else if (const gswitch *switch_stmt | |
| = dyn_cast <const gswitch *> (&last_stmt)) | |
| { | |
| if (expr_uses_conjured_value_p (model, | |
| gimple_switch_index (switch_stmt))) | |
| return true; | |
| } | |
| return false; | |
| } | |
| /* Return true iff EXPR is affected by a conjured_svalue. */ | |
| static bool expr_uses_conjured_value_p (const region_model &model, | |
| tree expr) | |
| { | |
| class conjured_bit_vector_finder : public symbolic::node_visitor | |
| { | |
| public: | |
| conjured_bit_vector_finder () : m_found_conjured_svalues (false) | |
| { | |
| } | |
| bool | |
| visit_bit_vector (const symbolic::bit_vector &bv) final override | |
| { | |
| if (!node_visitor::visit_bit_vector (bv)) | |
| return false; | |
| if (bv.dyn_cast_conjured_bit_vector ()) | |
| m_found_conjured_svalues = true; | |
| return true; | |
| } | |
| bool m_found_conjured_svalues; | |
| }; | |
| const svalue *sval = model.get_rvalue (expr, nullptr); | |
| conjured_bit_vector_finder v; | |
| sval->accept_node_visitor (v); | |
| return v.m_found_conjured_svalues; | |
| } | |
| 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 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; | |
| return snode->entry_p (); | |
| } | |
| /* 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 nullptr; | |
| } | |
| /* 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 (), | |
| nullptr); | |
| } | |
| } | |
| } | |
| /* Return true iff NODE is unknown, or contains an unknown value. */ | |
| static bool | |
| contains_unknown_p (const symbolic::node &node) | |
| { | |
| struct unknown_finder : public symbolic::node_visitor | |
| { | |
| unknown_finder () | |
| : m_found_unknown (false) | |
| { | |
| } | |
| bool | |
| visit_svalue (const svalue &sval) final override | |
| { | |
| if (!symbolic::node_visitor::visit_svalue (sval)) | |
| return false; | |
| if (sval.get_kind () == SK_UNKNOWN) | |
| m_found_unknown = true; | |
| return true; | |
| } | |
| bool | |
| visit_bit_vector (const symbolic::bit_vector &bv) final override | |
| { | |
| if (!symbolic::node_visitor::visit_bit_vector (bv)) | |
| return false; | |
| if (auto *tristate_bv = bv.dyn_cast_tristate_bit_vector ()) | |
| if (tristate_bv->get_bit_value () == tristate::unknown ()) | |
| m_found_unknown = true; | |
| return true; | |
| } | |
| bool | |
| visit_bit_contents (const symbolic::bit_contents &bc) final override | |
| { | |
| if (!symbolic::node_visitor::visit_bit_contents (bc)) | |
| return false; | |
| if (bc.get_kind () == symbolic::bit_contents::kind::untracked) | |
| m_found_unknown = true; | |
| return true; | |
| } | |
| bool m_found_unknown; | |
| } v; | |
| node.accept_node_visitor (v); | |
| return v.m_found_unknown; | |
| } | |
| /* Subroutine of sufficiently_different_p. Compare the store bindings | |
| for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE. | |
| Return true if the state of NEW_ENTRY_ENODE is sufficiently different | |
| from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is | |
| being modified, and thus the recursion isn't infinite. | |
| Return false if the states for BASE_REG are effectively the same. */ | |
| static bool | |
| sufficiently_different_region_binding_p (exploded_node *new_entry_enode, | |
| exploded_node *prev_entry_enode, | |
| const region *base_reg) | |
| { | |
| /* 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; | |
| /* Get the contents of BASE_REG within the new frame. */ | |
| const symbolic::bit_contents &new_contents | |
| = new_model.get_bit_contents (*base_reg); | |
| /* If any part of the contents is UNKNOWN (e.g. due to hitting | |
| complexity limits) assume that it differs from the previous | |
| value. */ | |
| if (contains_unknown_p (new_contents)) | |
| return true; | |
| /* Get the equivalent contents within the old enode. */ | |
| const symbolic::bit_contents *prev_contents; | |
| if (const frame_region *enclosing_frame | |
| = base_reg->maybe_get_frame_region ()) | |
| { | |
| /* We have a binding within a frame in the new entry enode. */ | |
| /* Consider changes in bindings below the original entry | |
| to the recursion. */ | |
| const int old_stack_depth = prev_entry_enode->get_stack_depth (); | |
| if (enclosing_frame->get_stack_depth () < old_stack_depth) | |
| prev_contents = &prev_model.get_bit_contents (*base_reg); | |
| else | |
| { | |
| /* Ignore bindings within frames below the new entry node. */ | |
| const int new_stack_depth = new_entry_enode->get_stack_depth (); | |
| if (enclosing_frame->get_stack_depth () < new_stack_depth) | |
| return false; | |
| /* 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_contents = &prev_model.get_bit_contents (*equiv_prev_base_reg); | |
| } | |
| } | |
| else | |
| prev_contents = &prev_model.get_bit_contents (*base_reg); | |
| /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits) | |
| assume that it will differ from any new value. */ | |
| if (contains_unknown_p (*prev_contents)) | |
| return true; | |
| if (&new_contents != prev_contents) | |
| return true; | |
| return false; | |
| } | |
| /* 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 suggest 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)); | |
| /* Compare the stores of the two enodes. */ | |
| const region_model &new_model | |
| = *new_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; | |
| if (sufficiently_different_region_binding_p (new_entry_enode, | |
| prev_entry_enode, | |
| base_reg)) | |
| 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. */ | |
| pending_location ploc (enode, | |
| call_string.get_top_of_stack ().get_call_stmt ().location); | |
| get_diagnostic_manager ().add_diagnostic | |
| (std::move (ploc), | |
| std::make_unique<infinite_recursion_diagnostic> (prev_entry_enode, | |
| enode, | |
| fndecl)); | |
| } |