Branch data Line data Source code
1 : : /* Detection of infinite recursion.
2 : : Copyright (C) 2022-2025 Free Software Foundation, Inc.
3 : : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it
8 : : under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but
13 : : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "analyzer/common.h"
22 : :
23 : : #include "cfg.h"
24 : : #include "gimple-iterator.h"
25 : : #include "gimple-pretty-print.h"
26 : : #include "cgraph.h"
27 : : #include "digraph.h"
28 : :
29 : : #include "analyzer/analyzer-logging.h"
30 : : #include "analyzer/call-string.h"
31 : : #include "analyzer/program-point.h"
32 : : #include "analyzer/store.h"
33 : : #include "analyzer/region-model.h"
34 : : #include "analyzer/constraint-manager.h"
35 : : #include "analyzer/sm.h"
36 : : #include "analyzer/pending-diagnostic.h"
37 : : #include "analyzer/diagnostic-manager.h"
38 : : #include "analyzer/supergraph.h"
39 : : #include "analyzer/program-state.h"
40 : : #include "analyzer/exploded-graph.h"
41 : : #include "analyzer/checker-path.h"
42 : : #include "analyzer/feasible-graph.h"
43 : : #include "diagnostic-format-sarif.h"
44 : :
45 : : /* A subclass of pending_diagnostic for complaining about suspected
46 : : infinite recursion. */
47 : :
48 : : class infinite_recursion_diagnostic
49 : : : public pending_diagnostic_subclass<infinite_recursion_diagnostic>
50 : : {
51 : : public:
52 : 454 : infinite_recursion_diagnostic (const exploded_node *prev_entry_enode,
53 : : const exploded_node *new_entry_enode,
54 : : tree callee_fndecl)
55 : 454 : : m_prev_entry_enode (prev_entry_enode),
56 : 454 : m_new_entry_enode (new_entry_enode),
57 : 454 : m_callee_fndecl (callee_fndecl),
58 : 454 : m_prev_entry_event (nullptr)
59 : : {}
60 : :
61 : 2810 : const char *get_kind () const final override
62 : : {
63 : 2810 : return "infinite_recursion_diagnostic";
64 : : }
65 : :
66 : 394 : bool operator== (const infinite_recursion_diagnostic &other) const
67 : : {
68 : 394 : return m_callee_fndecl == other.m_callee_fndecl;
69 : : }
70 : :
71 : 594 : int get_controlling_option () const final override
72 : : {
73 : 594 : return OPT_Wanalyzer_infinite_recursion;
74 : : }
75 : :
76 : 140 : bool emit (diagnostic_emission_context &ctxt) final override
77 : : {
78 : : /* "CWE-674: Uncontrolled Recursion". */
79 : 140 : ctxt.add_cwe (674);
80 : 140 : return ctxt.warn ("infinite recursion");
81 : : }
82 : :
83 : : bool
84 : 280 : describe_final_event (pretty_printer &pp,
85 : : const evdesc::final_event &) final override
86 : : {
87 : 280 : const int frames_consumed = (m_new_entry_enode->get_stack_depth ()
88 : 280 : - m_prev_entry_enode->get_stack_depth ());
89 : 280 : if (frames_consumed > 1)
90 : 64 : pp_printf (&pp,
91 : : "apparently infinite chain of mutually-recursive function"
92 : : " calls, consuming %i stack frames per recursion",
93 : : frames_consumed);
94 : : else
95 : 216 : pp_string (&pp, "apparently infinite recursion");
96 : 280 : return true;
97 : : }
98 : :
99 : : void
100 : 358 : add_function_entry_event (const exploded_edge &eedge,
101 : : checker_path *emission_path) final override
102 : : {
103 : : /* Subclass of function_entry_event for use when reporting both
104 : : the initial and subsequent entries to the function of interest,
105 : : allowing for cross-referencing the first event in the description
106 : : of the second. */
107 : 0 : class recursive_function_entry_event : public function_entry_event
108 : : {
109 : : public:
110 : 280 : recursive_function_entry_event (const program_point &dst_point,
111 : : const program_state &dst_state,
112 : : const infinite_recursion_diagnostic &pd,
113 : : bool topmost)
114 : 280 : : function_entry_event (dst_point, dst_state),
115 : 280 : m_pd (pd),
116 : 280 : m_topmost (topmost)
117 : : {
118 : : }
119 : :
120 : : void
121 : 560 : print_desc (pretty_printer &pp) const final override
122 : : {
123 : 560 : if (m_topmost)
124 : : {
125 : 280 : if (m_pd.m_prev_entry_event
126 : 280 : && m_pd.m_prev_entry_event->get_id_ptr ()->known_p ())
127 : 280 : pp_printf (&pp,
128 : : "recursive entry to %qE; previously entered at %@",
129 : 280 : m_effective_fndecl,
130 : 280 : m_pd.m_prev_entry_event->get_id_ptr ());
131 : : else
132 : 0 : pp_printf (&pp,
133 : : "recursive entry to %qE",
134 : 0 : m_effective_fndecl);
135 : : }
136 : : else
137 : 280 : pp_printf (&pp,
138 : : "initial entry to %qE",
139 : 280 : m_effective_fndecl);
140 : 560 : }
141 : :
142 : : private:
143 : : const infinite_recursion_diagnostic &m_pd;
144 : : bool m_topmost;
145 : : };
146 : 358 : const exploded_node *dst_node = eedge.m_dest;
147 : 358 : const program_point &dst_point = dst_node->get_point ();
148 : 358 : if (eedge.m_dest == m_prev_entry_enode)
149 : : {
150 : 140 : gcc_assert (m_prev_entry_event == nullptr);
151 : 140 : std::unique_ptr<checker_event> prev_entry_event
152 : : = std::make_unique <recursive_function_entry_event>
153 : 140 : (dst_point,
154 : : dst_node->get_state (),
155 : 140 : *this, false);
156 : 140 : m_prev_entry_event = prev_entry_event.get ();
157 : 140 : emission_path->add_event (std::move (prev_entry_event));
158 : 140 : }
159 : 218 : else if (eedge.m_dest == m_new_entry_enode)
160 : 140 : emission_path->add_event
161 : 140 : (std::make_unique<recursive_function_entry_event>
162 : 140 : (dst_point, dst_node->get_state (), *this, true));
163 : : else
164 : 78 : pending_diagnostic::add_function_entry_event (eedge, emission_path);
165 : 358 : }
166 : :
167 : : /* Customize the location where the warning_event appears, putting
168 : : it at the topmost entrypoint to the function. */
169 : 140 : void add_final_event (const state_machine *,
170 : : const exploded_node *enode,
171 : : const event_loc_info &,
172 : : tree,
173 : : state_machine::state_t,
174 : : checker_path *emission_path) final override
175 : : {
176 : 140 : gcc_assert (m_new_entry_enode);
177 : 140 : emission_path->add_event
178 : 140 : (std::make_unique<warning_event>
179 : 140 : (event_loc_info (m_new_entry_enode->get_supernode
180 : : ()->get_start_location (),
181 : : m_callee_fndecl,
182 : 140 : m_new_entry_enode->get_stack_depth ()),
183 : : enode,
184 : 140 : nullptr, nullptr, nullptr));
185 : 140 : }
186 : :
187 : : /* Reject paths in which conjured svalues have affected control flow
188 : : since m_prev_entry_enode. */
189 : :
190 : 446 : bool check_valid_fpath_p (const feasible_node &final_fnode,
191 : : const gimple *)
192 : : const final override
193 : : {
194 : : /* Reject paths in which calls with unknown side effects have occurred
195 : : since m_prev_entry_enode.
196 : : Find num calls with side effects. Walk backward until we reach the
197 : : pref */
198 : 446 : gcc_assert (final_fnode.get_inner_node () == m_new_entry_enode);
199 : :
200 : : /* FG is actually a tree. Walk backwards from FINAL_FNODE until we
201 : : reach the prev_entry_enode (or the origin). */
202 : : const feasible_node *iter_fnode = &final_fnode;
203 : 5041 : while (iter_fnode->get_inner_node ()->m_index != 0)
204 : : {
205 : 5041 : gcc_assert (iter_fnode->m_preds.length () == 1);
206 : :
207 : 5041 : feasible_edge *pred_fedge
208 : 5041 : = static_cast <feasible_edge *> (iter_fnode->m_preds[0]);
209 : :
210 : : /* Determine if conjured svalues have affected control flow
211 : : since the prev entry node. */
212 : 5041 : if (fedge_uses_conjured_svalue_p (pred_fedge))
213 : : /* If so, then reject this diagnostic. */
214 : : return false;
215 : 4989 : iter_fnode = static_cast <feasible_node *> (pred_fedge->m_src);
216 : 4989 : if (iter_fnode->get_inner_node () == m_prev_entry_enode)
217 : : /* Accept this diagnostic. */
218 : : return true;
219 : : }
220 : :
221 : : /* We shouldn't get here; if we do, reject the diagnostic. */
222 : 0 : gcc_unreachable ();
223 : : return false;
224 : : }
225 : :
226 : 0 : void maybe_add_sarif_properties (sarif_object &result_obj)
227 : : const final override
228 : : {
229 : 0 : sarif_property_bag &props = result_obj.get_or_create_properties ();
230 : : #define PROPERTY_PREFIX "gcc/analyzer/infinite_recursion_diagnostic/"
231 : 0 : props.set_integer (PROPERTY_PREFIX "prev_entry_enode",
232 : 0 : m_prev_entry_enode->m_index);
233 : 0 : props.set_integer (PROPERTY_PREFIX "new_entry_enode",
234 : 0 : m_new_entry_enode->m_index);
235 : : #undef PROPERTY_PREFIX
236 : 0 : }
237 : :
238 : : private:
239 : : /* Return true iff control flow along FEDGE was affected by
240 : : a conjured_svalue. */
241 : 5041 : static bool fedge_uses_conjured_svalue_p (feasible_edge *fedge)
242 : : {
243 : 5041 : const exploded_edge *eedge = fedge->get_inner_edge ();
244 : 5041 : const superedge *sedge = eedge->m_sedge;
245 : 5041 : if (!sedge)
246 : : return false;
247 : 1928 : const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
248 : 1928 : if (!cfg_sedge)
249 : : return false;
250 : 1194 : const gimple *last_stmt = sedge->m_src->get_last_stmt ();
251 : 1194 : if (!last_stmt)
252 : : return false;
253 : :
254 : 496 : const feasible_node *dst_fnode
255 : : = static_cast<const feasible_node *> (fedge->m_dest);
256 : 496 : const region_model &model = dst_fnode->get_state ().get_model ();
257 : :
258 : 496 : if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt))
259 : : {
260 : 440 : if (expr_uses_conjured_svalue_p (model, gimple_cond_lhs (cond_stmt)))
261 : : return true;
262 : 412 : if (expr_uses_conjured_svalue_p (model, gimple_cond_rhs (cond_stmt)))
263 : : return true;
264 : : }
265 : 56 : else if (const gswitch *switch_stmt
266 : 5065 : = dyn_cast <const gswitch *> (last_stmt))
267 : : {
268 : 24 : if (expr_uses_conjured_svalue_p (model,
269 : : gimple_switch_index (switch_stmt)))
270 : : return true;
271 : : }
272 : : return false;
273 : : }
274 : :
275 : : /* Return true iff EXPR is affected by a conjured_svalue. */
276 : 876 : static bool expr_uses_conjured_svalue_p (const region_model &model,
277 : : tree expr)
278 : : {
279 : 876 : class conjured_svalue_finder : public visitor
280 : : {
281 : : public:
282 : 876 : conjured_svalue_finder () : m_found_conjured_svalues (false)
283 : : {
284 : : }
285 : : void
286 : 56 : visit_conjured_svalue (const conjured_svalue *) final override
287 : : {
288 : 56 : m_found_conjured_svalues = true;
289 : 56 : }
290 : :
291 : : bool m_found_conjured_svalues;
292 : : };
293 : :
294 : 876 : const svalue *sval = model.get_rvalue (expr, nullptr);
295 : 876 : conjured_svalue_finder v;
296 : 876 : sval->accept (&v);
297 : 876 : return v.m_found_conjured_svalues;
298 : : }
299 : :
300 : : const exploded_node *m_prev_entry_enode;
301 : : const exploded_node *m_new_entry_enode;
302 : : tree m_callee_fndecl;
303 : : const checker_event *m_prev_entry_event;
304 : : };
305 : :
306 : : /* Return true iff ENODE is the PK_BEFORE_SUPERNODE at a function
307 : : entrypoint. */
308 : :
309 : : static bool
310 : 139325 : is_entrypoint_p (exploded_node *enode)
311 : : {
312 : : /* Look for an entrypoint to a function... */
313 : 139325 : const supernode *snode = enode->get_supernode ();
314 : 139325 : if (!snode)
315 : : return false;
316 : 139325 : if (!snode->entry_p ())
317 : 11538 : return false;;
318 : 11538 : const program_point &point = enode->get_point ();
319 : 11538 : if (point.get_kind () != PK_BEFORE_SUPERNODE)
320 : 1606 : return false;
321 : : return true;
322 : : }
323 : :
324 : : /* Walk backwards through the eg, looking for the first
325 : : enode we find that's also the entrypoint of the same function. */
326 : :
327 : : exploded_node *
328 : 1054 : exploded_graph::find_previous_entry_to (function *top_of_stack_fun,
329 : : exploded_node *enode) const
330 : : {
331 : 1054 : auto_vec<exploded_node *> worklist;
332 : 1054 : hash_set<exploded_node *> visited;
333 : :
334 : 1054 : visited.add (enode);
335 : 4216 : for (auto in_edge : enode->m_preds)
336 : 1054 : worklist.safe_push (in_edge->m_src);
337 : :
338 : 18685 : while (worklist.length () > 0)
339 : : {
340 : 17631 : exploded_node *iter = worklist.pop ();
341 : :
342 : 17631 : if (is_entrypoint_p (iter)
343 : 17631 : && iter->get_function () == top_of_stack_fun)
344 : 1054 : return iter;
345 : :
346 : 16577 : if (visited.contains (iter))
347 : 32 : continue;
348 : 16545 : visited.add (iter);
349 : 66448 : for (auto in_edge : iter->m_preds)
350 : 16813 : worklist.safe_push (in_edge->m_src);
351 : : }
352 : :
353 : : /* Not found. */
354 : : return nullptr;
355 : 1054 : }
356 : :
357 : : /* Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
358 : : remap it to the equivalent region within EQUIV_PREV_FRAME.
359 : :
360 : : For example, given param "n" within frame "foo@3", and equiv prev frame
361 : : "foo@1", remap it to param "n" within frame "foo@1". */
362 : :
363 : : static const region *
364 : 823 : remap_enclosing_frame (const region *base_reg,
365 : : const frame_region *enclosing_frame,
366 : : const frame_region *equiv_prev_frame,
367 : : region_model_manager *mgr)
368 : : {
369 : 823 : gcc_assert (base_reg->get_parent_region () == enclosing_frame);
370 : 823 : switch (base_reg->get_kind ())
371 : : {
372 : 0 : default:
373 : : /* We should only encounter params and varargs at the topmost
374 : : entrypoint. */
375 : 0 : gcc_unreachable ();
376 : :
377 : 20 : case RK_VAR_ARG:
378 : 20 : {
379 : 20 : const var_arg_region *var_arg_reg = (const var_arg_region *)base_reg;
380 : 20 : return mgr->get_var_arg_region (equiv_prev_frame,
381 : 20 : var_arg_reg->get_index ());
382 : : }
383 : 803 : case RK_DECL:
384 : 803 : {
385 : 803 : const decl_region *decl_reg = (const decl_region *)base_reg;
386 : 803 : return equiv_prev_frame->get_region_for_local (mgr,
387 : : decl_reg->get_decl (),
388 : 803 : nullptr);
389 : : }
390 : : }
391 : : }
392 : :
393 : : /* Return true iff SVAL is unknown, or contains an unknown svalue. */
394 : :
395 : : static bool
396 : 7161 : contains_unknown_p (const svalue *sval)
397 : : {
398 : 7161 : if (sval->get_kind () == SK_UNKNOWN)
399 : : return true;
400 : 14090 : if (const compound_svalue *compound_sval
401 : 7045 : = sval->dyn_cast_compound_svalue ())
402 : 66 : for (auto iter : *compound_sval)
403 : 39 : if (iter.second->get_kind () == SK_UNKNOWN)
404 : 18 : return true;
405 : : return false;
406 : : }
407 : :
408 : : /* Subroutine of sufficiently_different_p. Compare the store bindings
409 : : for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE.
410 : :
411 : : Return true if the state of NEW_ENTRY_ENODE is sufficiently different
412 : : from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is
413 : : being modified, and thus the recursion isn't infinite.
414 : :
415 : : Return false if the states for BASE_REG are effectively the same. */
416 : :
417 : : static bool
418 : 4483 : sufficiently_different_region_binding_p (exploded_node *new_entry_enode,
419 : : exploded_node *prev_entry_enode,
420 : : const region *base_reg)
421 : : {
422 : : /* Compare the stores of the two enodes. */
423 : 4483 : const region_model &new_model
424 : 4483 : = *new_entry_enode->get_state ().m_region_model;
425 : 4483 : const region_model &prev_model
426 : 4483 : = *prev_entry_enode->get_state ().m_region_model;
427 : :
428 : : /* Get the value within the new frame. */
429 : 4483 : const svalue *new_sval
430 : 4483 : = new_model.get_store_value (base_reg, nullptr);
431 : :
432 : : /* If any part of the value is UNKNOWN (e.g. due to hitting
433 : : complexity limits) assume that it differs from the previous
434 : : value. */
435 : 4483 : if (contains_unknown_p (new_sval))
436 : : return true;
437 : :
438 : : /* Get the equivalent value within the old enode. */
439 : 4349 : const svalue *prev_sval;
440 : :
441 : 8698 : if (const frame_region *enclosing_frame
442 : 4349 : = base_reg->maybe_get_frame_region ())
443 : : {
444 : : /* We have a binding within a frame in the new entry enode. */
445 : :
446 : : /* Consider changes in bindings below the original entry
447 : : to the recursion. */
448 : 3951 : const int old_stack_depth = prev_entry_enode->get_stack_depth ();
449 : 3951 : if (enclosing_frame->get_stack_depth () < old_stack_depth)
450 : 1457 : prev_sval = prev_model.get_store_value (base_reg, nullptr);
451 : : else
452 : : {
453 : : /* Ignore bindings within frames below the new entry node. */
454 : 2494 : const int new_stack_depth = new_entry_enode->get_stack_depth ();
455 : 2494 : if (enclosing_frame->get_stack_depth () < new_stack_depth)
456 : : return false;
457 : :
458 : : /* We have a binding within the frame of the new entry node,
459 : : presumably a parameter. */
460 : :
461 : : /* Get the value within the equivalent frame of
462 : : the old entrypoint; typically will be the initial_svalue
463 : : of the parameter. */
464 : 823 : const frame_region *equiv_prev_frame
465 : 823 : = prev_model.get_current_frame ();
466 : 823 : const region *equiv_prev_base_reg
467 : 823 : = remap_enclosing_frame (base_reg,
468 : : enclosing_frame,
469 : : equiv_prev_frame,
470 : : new_model.get_manager ());
471 : 823 : prev_sval
472 : 823 : = prev_model.get_store_value (equiv_prev_base_reg, nullptr);
473 : : }
474 : : }
475 : : else
476 : 398 : prev_sval = prev_model.get_store_value (base_reg, nullptr);
477 : :
478 : : /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits)
479 : : assume that it will differ from any new value. */
480 : 2678 : if (contains_unknown_p (prev_sval))
481 : : return true;
482 : :
483 : 2678 : if (new_sval != prev_sval)
484 : : return true;
485 : :
486 : : return false;
487 : : }
488 : :
489 : : /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
490 : : both of which are entrypoints to the same function, where recursion has
491 : : occurred.
492 : :
493 : : Return true if the state of NEW_ENTRY_ENODE is sufficiently different
494 : : from PREV_ENTRY_ENODE to suggest that some variant is being modified,
495 : : and thus the recursion isn't infinite.
496 : :
497 : : Return false if the states are effectively the same, suggesting that
498 : : the recursion is infinite.
499 : :
500 : : For example, consider mutually recursive functions "foo" and "bar".
501 : : At the entrypoint to a "foo" frame where we've detected recursion,
502 : : we might have three frames on the stack: the new 'foo'@3, an inner
503 : : 'bar'@2, and the innermost 'foo'@1.
504 : :
505 : : (gdb) call enode->dump(m_ext_state)
506 : : EN: 16
507 : : callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
508 : : before SN: 0 (NULL from-edge)
509 : :
510 : : rmodel:
511 : : stack depth: 3
512 : : frame (index 2): frame: ‘foo’@3
513 : : frame (index 1): frame: ‘bar’@2
514 : : frame (index 0): frame: ‘foo’@1
515 : : clusters within root region
516 : : cluster for: (*INIT_VAL(f_4(D)))
517 : : clusters within frame: ‘bar’@2
518 : : cluster for: b_2(D): INIT_VAL(f_4(D))
519 : : clusters within frame: ‘foo’@3
520 : : cluster for: f_4(D): INIT_VAL(f_4(D))
521 : : m_called_unknown_fn: FALSE
522 : :
523 : : whereas for the previous entry node we'd have just the innermost
524 : : 'foo'@1
525 : :
526 : : (gdb) call prev_entry_enode->dump(m_ext_state)
527 : : EN: 1
528 : : callstring: []
529 : : before SN: 0 (NULL from-edge)
530 : :
531 : : rmodel:
532 : : stack depth: 1
533 : : frame (index 0): frame: ‘foo’@1
534 : : clusters within root region
535 : : cluster for: (*INIT_VAL(f_4(D)))
536 : : m_called_unknown_fn: FALSE
537 : :
538 : : We want to abstract away frames 1 and 2 in the new entry enode,
539 : : and compare its frame 3 with the frame 1 in the previous entry
540 : : enode, and determine if enough state changes between them to
541 : : rule out infinite recursion. */
542 : :
543 : : static bool
544 : 1054 : sufficiently_different_p (exploded_node *new_entry_enode,
545 : : exploded_node *prev_entry_enode,
546 : : logger *logger)
547 : : {
548 : 1054 : LOG_SCOPE (logger);
549 : 1054 : gcc_assert (new_entry_enode);
550 : 1054 : gcc_assert (prev_entry_enode);
551 : 1054 : gcc_assert (is_entrypoint_p (new_entry_enode));
552 : 1054 : gcc_assert (is_entrypoint_p (prev_entry_enode));
553 : :
554 : : /* Compare the stores of the two enodes. */
555 : 1054 : const region_model &new_model
556 : 1054 : = *new_entry_enode->get_state ().m_region_model;
557 : 1054 : const store &new_store = *new_model.get_store ();
558 : :
559 : 8820 : for (auto kv : new_store)
560 : : {
561 : 4483 : const region *base_reg = kv.first;
562 : 4483 : if (sufficiently_different_region_binding_p (new_entry_enode,
563 : : prev_entry_enode,
564 : : base_reg))
565 : 600 : return true;
566 : : }
567 : :
568 : : /* No significant differences found. */
569 : 454 : return false;
570 : 1054 : }
571 : :
572 : : /* Implementation of -Wanalyzer-infinite-recursion.
573 : :
574 : : Called when adding ENODE to the graph, after adding its first in-edge.
575 : :
576 : : For function entrypoints, see if recursion has occurred, and, if so,
577 : : check if the state of memory changed between the recursion levels,
578 : : which would suggest some kind of decreasing variant that leads to
579 : : termination.
580 : :
581 : : For recursive calls where the state of memory is effectively unchanged
582 : : between recursion levels, warn with -Wanalyzer-infinite-recursion. */
583 : :
584 : : void
585 : 119586 : exploded_graph::detect_infinite_recursion (exploded_node *enode)
586 : : {
587 : 119586 : if (!is_entrypoint_p (enode))
588 : 119132 : return;
589 : 6218 : function *top_of_stack_fun = enode->get_function ();
590 : 6218 : gcc_assert (top_of_stack_fun);
591 : :
592 : : /* ....where a call to that function is already in the call string. */
593 : 6218 : const call_string &call_string = enode->get_point ().get_call_string ();
594 : :
595 : 6218 : if (call_string.count_occurrences_of_function (top_of_stack_fun) < 2)
596 : : return;
597 : :
598 : 1054 : tree fndecl = top_of_stack_fun->decl;
599 : :
600 : 1054 : log_scope s (get_logger (),
601 : : "checking for infinite recursion",
602 : : "considering recursion at EN: %i entering %qE",
603 : 1054 : enode->m_index, fndecl);
604 : :
605 : : /* Find enode that's the entrypoint for the previous frame for fndecl
606 : : in the recursion. */
607 : 1054 : exploded_node *prev_entry_enode
608 : 1054 : = find_previous_entry_to (top_of_stack_fun, enode);
609 : 1054 : gcc_assert (prev_entry_enode);
610 : 1054 : if (get_logger ())
611 : 0 : get_logger ()->log ("previous entrypoint to %qE is EN: %i",
612 : 0 : fndecl, prev_entry_enode->m_index);
613 : :
614 : : /* Look for changes to the state of memory between the recursion levels. */
615 : 1054 : if (sufficiently_different_p (enode, prev_entry_enode, get_logger ()))
616 : 600 : return;
617 : :
618 : : /* Otherwise, the state of memory is effectively the same between the two
619 : : recursion levels; warn. */
620 : :
621 : 454 : const supernode *caller_snode = call_string.get_top_of_stack ().m_caller;
622 : 454 : const supernode *snode = enode->get_supernode ();
623 : 454 : gcc_assert (caller_snode->m_returning_call);
624 : 454 : pending_location ploc (enode,
625 : : snode,
626 : : caller_snode->m_returning_call,
627 : 454 : nullptr);
628 : 454 : get_diagnostic_manager ().add_diagnostic
629 : 454 : (ploc,
630 : 454 : std::make_unique<infinite_recursion_diagnostic> (prev_entry_enode,
631 : : enode,
632 : : fndecl));
633 : 1054 : }
|
