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 (NULL)
59 : : {}
60 : :
61 : 1374 : const char *get_kind () const final override
62 : : {
63 : 1374 : 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 infinite_recursion_diagnostic &pd,
112 : : bool topmost)
113 : 280 : : function_entry_event (dst_point),
114 : 280 : m_pd (pd),
115 : 280 : m_topmost (topmost)
116 : : {
117 : : }
118 : :
119 : : void
120 : 560 : print_desc (pretty_printer &pp) const final override
121 : : {
122 : 560 : if (m_topmost)
123 : : {
124 : 280 : if (m_pd.m_prev_entry_event
125 : 280 : && m_pd.m_prev_entry_event->get_id_ptr ()->known_p ())
126 : 280 : pp_printf (&pp,
127 : : "recursive entry to %qE; previously entered at %@",
128 : 280 : m_effective_fndecl,
129 : 280 : m_pd.m_prev_entry_event->get_id_ptr ());
130 : : else
131 : 0 : pp_printf (&pp,
132 : : "recursive entry to %qE",
133 : 0 : m_effective_fndecl);
134 : : }
135 : : else
136 : 280 : pp_printf (&pp,
137 : : "initial entry to %qE",
138 : 280 : m_effective_fndecl);
139 : 560 : }
140 : :
141 : : private:
142 : : const infinite_recursion_diagnostic &m_pd;
143 : : bool m_topmost;
144 : : };
145 : 358 : const exploded_node *dst_node = eedge.m_dest;
146 : 358 : const program_point &dst_point = dst_node->get_point ();
147 : 358 : if (eedge.m_dest == m_prev_entry_enode)
148 : : {
149 : 140 : gcc_assert (m_prev_entry_event == NULL);
150 : 140 : std::unique_ptr<checker_event> prev_entry_event
151 : 140 : = std::make_unique <recursive_function_entry_event> (dst_point,
152 : 140 : *this, false);
153 : 140 : m_prev_entry_event = prev_entry_event.get ();
154 : 140 : emission_path->add_event (std::move (prev_entry_event));
155 : 140 : }
156 : 218 : else if (eedge.m_dest == m_new_entry_enode)
157 : 140 : emission_path->add_event
158 : 140 : (std::make_unique<recursive_function_entry_event>
159 : 140 : (dst_point, *this, true));
160 : : else
161 : 78 : pending_diagnostic::add_function_entry_event (eedge, emission_path);
162 : 358 : }
163 : :
164 : : /* Customize the location where the warning_event appears, putting
165 : : it at the topmost entrypoint to the function. */
166 : 140 : void add_final_event (const state_machine *,
167 : : const exploded_node *enode,
168 : : const event_loc_info &,
169 : : tree,
170 : : state_machine::state_t,
171 : : checker_path *emission_path) final override
172 : : {
173 : 140 : gcc_assert (m_new_entry_enode);
174 : 140 : emission_path->add_event
175 : 140 : (std::make_unique<warning_event>
176 : 140 : (event_loc_info (m_new_entry_enode->get_supernode
177 : : ()->get_start_location (),
178 : : m_callee_fndecl,
179 : 140 : m_new_entry_enode->get_stack_depth ()),
180 : : enode,
181 : 140 : nullptr, nullptr, nullptr));
182 : 140 : }
183 : :
184 : : /* Reject paths in which conjured svalues have affected control flow
185 : : since m_prev_entry_enode. */
186 : :
187 : 446 : bool check_valid_fpath_p (const feasible_node &final_fnode,
188 : : const gimple *)
189 : : const final override
190 : : {
191 : : /* Reject paths in which calls with unknown side effects have occurred
192 : : since m_prev_entry_enode.
193 : : Find num calls with side effects. Walk backward until we reach the
194 : : pref */
195 : 446 : gcc_assert (final_fnode.get_inner_node () == m_new_entry_enode);
196 : :
197 : : /* FG is actually a tree. Walk backwards from FINAL_FNODE until we
198 : : reach the prev_entry_enode (or the origin). */
199 : : const feasible_node *iter_fnode = &final_fnode;
200 : 5041 : while (iter_fnode->get_inner_node ()->m_index != 0)
201 : : {
202 : 5041 : gcc_assert (iter_fnode->m_preds.length () == 1);
203 : :
204 : 5041 : feasible_edge *pred_fedge
205 : 5041 : = static_cast <feasible_edge *> (iter_fnode->m_preds[0]);
206 : :
207 : : /* Determine if conjured svalues have affected control flow
208 : : since the prev entry node. */
209 : 5041 : if (fedge_uses_conjured_svalue_p (pred_fedge))
210 : : /* If so, then reject this diagnostic. */
211 : : return false;
212 : 4989 : iter_fnode = static_cast <feasible_node *> (pred_fedge->m_src);
213 : 4989 : if (iter_fnode->get_inner_node () == m_prev_entry_enode)
214 : : /* Accept this diagnostic. */
215 : : return true;
216 : : }
217 : :
218 : : /* We shouldn't get here; if we do, reject the diagnostic. */
219 : 0 : gcc_unreachable ();
220 : : return false;
221 : : }
222 : :
223 : 0 : void maybe_add_sarif_properties (sarif_object &result_obj)
224 : : const final override
225 : : {
226 : 0 : sarif_property_bag &props = result_obj.get_or_create_properties ();
227 : : #define PROPERTY_PREFIX "gcc/analyzer/infinite_recursion_diagnostic/"
228 : 0 : props.set_integer (PROPERTY_PREFIX "prev_entry_enode",
229 : 0 : m_prev_entry_enode->m_index);
230 : 0 : props.set_integer (PROPERTY_PREFIX "new_entry_enode",
231 : 0 : m_new_entry_enode->m_index);
232 : : #undef PROPERTY_PREFIX
233 : 0 : }
234 : :
235 : : private:
236 : : /* Return true iff control flow along FEDGE was affected by
237 : : a conjured_svalue. */
238 : 5041 : static bool fedge_uses_conjured_svalue_p (feasible_edge *fedge)
239 : : {
240 : 5041 : const exploded_edge *eedge = fedge->get_inner_edge ();
241 : 5041 : const superedge *sedge = eedge->m_sedge;
242 : 5041 : if (!sedge)
243 : : return false;
244 : 1928 : const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
245 : 1928 : if (!cfg_sedge)
246 : : return false;
247 : 1194 : const gimple *last_stmt = sedge->m_src->get_last_stmt ();
248 : 1194 : if (!last_stmt)
249 : : return false;
250 : :
251 : 496 : const feasible_node *dst_fnode
252 : : = static_cast<const feasible_node *> (fedge->m_dest);
253 : 496 : const region_model &model = dst_fnode->get_state ().get_model ();
254 : :
255 : 496 : if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt))
256 : : {
257 : 440 : if (expr_uses_conjured_svalue_p (model, gimple_cond_lhs (cond_stmt)))
258 : : return true;
259 : 412 : if (expr_uses_conjured_svalue_p (model, gimple_cond_rhs (cond_stmt)))
260 : : return true;
261 : : }
262 : 56 : else if (const gswitch *switch_stmt
263 : 5065 : = dyn_cast <const gswitch *> (last_stmt))
264 : : {
265 : 24 : if (expr_uses_conjured_svalue_p (model,
266 : : gimple_switch_index (switch_stmt)))
267 : : return true;
268 : : }
269 : : return false;
270 : : }
271 : :
272 : : /* Return true iff EXPR is affected by a conjured_svalue. */
273 : 876 : static bool expr_uses_conjured_svalue_p (const region_model &model,
274 : : tree expr)
275 : : {
276 : 876 : class conjured_svalue_finder : public visitor
277 : : {
278 : : public:
279 : 876 : conjured_svalue_finder () : m_found_conjured_svalues (false)
280 : : {
281 : : }
282 : : void
283 : 56 : visit_conjured_svalue (const conjured_svalue *) final override
284 : : {
285 : 56 : m_found_conjured_svalues = true;
286 : 56 : }
287 : :
288 : : bool m_found_conjured_svalues;
289 : : };
290 : :
291 : 876 : const svalue *sval = model.get_rvalue (expr, NULL);
292 : 876 : conjured_svalue_finder v;
293 : 876 : sval->accept (&v);
294 : 876 : return v.m_found_conjured_svalues;
295 : : }
296 : :
297 : : const exploded_node *m_prev_entry_enode;
298 : : const exploded_node *m_new_entry_enode;
299 : : tree m_callee_fndecl;
300 : : const checker_event *m_prev_entry_event;
301 : : };
302 : :
303 : : /* Return true iff ENODE is the PK_BEFORE_SUPERNODE at a function
304 : : entrypoint. */
305 : :
306 : : static bool
307 : 139200 : is_entrypoint_p (exploded_node *enode)
308 : : {
309 : : /* Look for an entrypoint to a function... */
310 : 139200 : const supernode *snode = enode->get_supernode ();
311 : 139200 : if (!snode)
312 : : return false;
313 : 139200 : if (!snode->entry_p ())
314 : 11495 : return false;;
315 : 11495 : const program_point &point = enode->get_point ();
316 : 11495 : if (point.get_kind () != PK_BEFORE_SUPERNODE)
317 : 1606 : return false;
318 : : return true;
319 : : }
320 : :
321 : : /* Walk backwards through the eg, looking for the first
322 : : enode we find that's also the entrypoint of the same function. */
323 : :
324 : : exploded_node *
325 : 1054 : exploded_graph::find_previous_entry_to (function *top_of_stack_fun,
326 : : exploded_node *enode) const
327 : : {
328 : 1054 : auto_vec<exploded_node *> worklist;
329 : 1054 : hash_set<exploded_node *> visited;
330 : :
331 : 1054 : visited.add (enode);
332 : 4216 : for (auto in_edge : enode->m_preds)
333 : 1054 : worklist.safe_push (in_edge->m_src);
334 : :
335 : 18685 : while (worklist.length () > 0)
336 : : {
337 : 17631 : exploded_node *iter = worklist.pop ();
338 : :
339 : 17631 : if (is_entrypoint_p (iter)
340 : 17631 : && iter->get_function () == top_of_stack_fun)
341 : 1054 : return iter;
342 : :
343 : 16577 : if (visited.contains (iter))
344 : 32 : continue;
345 : 16545 : visited.add (iter);
346 : 66448 : for (auto in_edge : iter->m_preds)
347 : 16813 : worklist.safe_push (in_edge->m_src);
348 : : }
349 : :
350 : : /* Not found. */
351 : : return NULL;
352 : 1054 : }
353 : :
354 : : /* Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
355 : : remap it to the equivalent region within EQUIV_PREV_FRAME.
356 : :
357 : : For example, given param "n" within frame "foo@3", and equiv prev frame
358 : : "foo@1", remap it to param "n" within frame "foo@1". */
359 : :
360 : : static const region *
361 : 825 : remap_enclosing_frame (const region *base_reg,
362 : : const frame_region *enclosing_frame,
363 : : const frame_region *equiv_prev_frame,
364 : : region_model_manager *mgr)
365 : : {
366 : 825 : gcc_assert (base_reg->get_parent_region () == enclosing_frame);
367 : 825 : switch (base_reg->get_kind ())
368 : : {
369 : 0 : default:
370 : : /* We should only encounter params and varargs at the topmost
371 : : entrypoint. */
372 : 0 : gcc_unreachable ();
373 : :
374 : 21 : case RK_VAR_ARG:
375 : 21 : {
376 : 21 : const var_arg_region *var_arg_reg = (const var_arg_region *)base_reg;
377 : 21 : return mgr->get_var_arg_region (equiv_prev_frame,
378 : 21 : var_arg_reg->get_index ());
379 : : }
380 : 804 : case RK_DECL:
381 : 804 : {
382 : 804 : const decl_region *decl_reg = (const decl_region *)base_reg;
383 : 804 : return equiv_prev_frame->get_region_for_local (mgr,
384 : : decl_reg->get_decl (),
385 : 804 : NULL);
386 : : }
387 : : }
388 : : }
389 : :
390 : : /* Return true iff SVAL is unknown, or contains an unknown svalue. */
391 : :
392 : : static bool
393 : 7257 : contains_unknown_p (const svalue *sval)
394 : : {
395 : 7257 : if (sval->get_kind () == SK_UNKNOWN)
396 : : return true;
397 : 14260 : if (const compound_svalue *compound_sval
398 : 7130 : = sval->dyn_cast_compound_svalue ())
399 : 77 : for (auto iter : *compound_sval)
400 : 43 : if (iter.second->get_kind () == SK_UNKNOWN)
401 : 17 : return true;
402 : : return false;
403 : : }
404 : :
405 : : /* Subroutine of sufficiently_different_p. Compare the store bindings
406 : : for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE.
407 : :
408 : : Return true if the state of NEW_ENTRY_ENODE is sufficiently different
409 : : from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is
410 : : being modified, and thus the recursion isn't infinite.
411 : :
412 : : Return false if the states for BASE_REG are effectively the same. */
413 : :
414 : : static bool
415 : 4557 : sufficiently_different_region_binding_p (exploded_node *new_entry_enode,
416 : : exploded_node *prev_entry_enode,
417 : : const region *base_reg)
418 : : {
419 : : /* Compare the stores of the two enodes. */
420 : 4557 : const region_model &new_model
421 : 4557 : = *new_entry_enode->get_state ().m_region_model;
422 : 4557 : const region_model &prev_model
423 : 4557 : = *prev_entry_enode->get_state ().m_region_model;
424 : :
425 : : /* Get the value within the new frame. */
426 : 4557 : const svalue *new_sval
427 : 4557 : = new_model.get_store_value (base_reg, NULL);
428 : :
429 : : /* If any part of the value is UNKNOWN (e.g. due to hitting
430 : : complexity limits) assume that it differs from the previous
431 : : value. */
432 : 4557 : if (contains_unknown_p (new_sval))
433 : : return true;
434 : :
435 : : /* Get the equivalent value within the old enode. */
436 : 4413 : const svalue *prev_sval;
437 : :
438 : 8826 : if (const frame_region *enclosing_frame
439 : 4413 : = base_reg->maybe_get_frame_region ())
440 : : {
441 : : /* We have a binding within a frame in the new entry enode. */
442 : :
443 : : /* Consider changes in bindings below the original entry
444 : : to the recursion. */
445 : 4014 : const int old_stack_depth = prev_entry_enode->get_stack_depth ();
446 : 4014 : if (enclosing_frame->get_stack_depth () < old_stack_depth)
447 : 1476 : prev_sval = prev_model.get_store_value (base_reg, NULL);
448 : : else
449 : : {
450 : : /* Ignore bindings within frames below the new entry node. */
451 : 2538 : const int new_stack_depth = new_entry_enode->get_stack_depth ();
452 : 2538 : if (enclosing_frame->get_stack_depth () < new_stack_depth)
453 : : return false;
454 : :
455 : : /* We have a binding within the frame of the new entry node,
456 : : presumably a parameter. */
457 : :
458 : : /* Get the value within the equivalent frame of
459 : : the old entrypoint; typically will be the initial_svalue
460 : : of the parameter. */
461 : 825 : const frame_region *equiv_prev_frame
462 : 825 : = prev_model.get_current_frame ();
463 : 825 : const region *equiv_prev_base_reg
464 : 825 : = remap_enclosing_frame (base_reg,
465 : : enclosing_frame,
466 : : equiv_prev_frame,
467 : : new_model.get_manager ());
468 : 825 : prev_sval
469 : 825 : = prev_model.get_store_value (equiv_prev_base_reg, NULL);
470 : : }
471 : : }
472 : : else
473 : 399 : prev_sval = prev_model.get_store_value (base_reg, NULL);
474 : :
475 : : /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits)
476 : : assume that it will differ from any new value. */
477 : 2700 : if (contains_unknown_p (prev_sval))
478 : : return true;
479 : :
480 : 2700 : if (new_sval != prev_sval)
481 : : return true;
482 : :
483 : : return false;
484 : : }
485 : :
486 : : /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
487 : : both of which are entrypoints to the same function, where recursion has
488 : : occurred.
489 : :
490 : : Return true if the state of NEW_ENTRY_ENODE is sufficiently different
491 : : from PREV_ENTRY_ENODE to suggest that some variant is being modified,
492 : : and thus the recursion isn't infinite.
493 : :
494 : : Return false if the states are effectively the same, suggesting that
495 : : the recursion is infinite.
496 : :
497 : : For example, consider mutually recursive functions "foo" and "bar".
498 : : At the entrypoint to a "foo" frame where we've detected recursion,
499 : : we might have three frames on the stack: the new 'foo'@3, an inner
500 : : 'bar'@2, and the innermost 'foo'@1.
501 : :
502 : : (gdb) call enode->dump(m_ext_state)
503 : : EN: 16
504 : : callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
505 : : before SN: 0 (NULL from-edge)
506 : :
507 : : rmodel:
508 : : stack depth: 3
509 : : frame (index 2): frame: ‘foo’@3
510 : : frame (index 1): frame: ‘bar’@2
511 : : frame (index 0): frame: ‘foo’@1
512 : : clusters within root region
513 : : cluster for: (*INIT_VAL(f_4(D)))
514 : : clusters within frame: ‘bar’@2
515 : : cluster for: b_2(D): INIT_VAL(f_4(D))
516 : : clusters within frame: ‘foo’@3
517 : : cluster for: f_4(D): INIT_VAL(f_4(D))
518 : : m_called_unknown_fn: FALSE
519 : :
520 : : whereas for the previous entry node we'd have just the innermost
521 : : 'foo'@1
522 : :
523 : : (gdb) call prev_entry_enode->dump(m_ext_state)
524 : : EN: 1
525 : : callstring: []
526 : : before SN: 0 (NULL from-edge)
527 : :
528 : : rmodel:
529 : : stack depth: 1
530 : : frame (index 0): frame: ‘foo’@1
531 : : clusters within root region
532 : : cluster for: (*INIT_VAL(f_4(D)))
533 : : m_called_unknown_fn: FALSE
534 : :
535 : : We want to abstract away frames 1 and 2 in the new entry enode,
536 : : and compare its frame 3 with the frame 1 in the previous entry
537 : : enode, and determine if enough state changes between them to
538 : : rule out infinite recursion. */
539 : :
540 : : static bool
541 : 1054 : sufficiently_different_p (exploded_node *new_entry_enode,
542 : : exploded_node *prev_entry_enode,
543 : : logger *logger)
544 : : {
545 : 1054 : LOG_SCOPE (logger);
546 : 1054 : gcc_assert (new_entry_enode);
547 : 1054 : gcc_assert (prev_entry_enode);
548 : 1054 : gcc_assert (is_entrypoint_p (new_entry_enode));
549 : 1054 : gcc_assert (is_entrypoint_p (prev_entry_enode));
550 : :
551 : : /* Compare the stores of the two enodes. */
552 : 1054 : const region_model &new_model
553 : 1054 : = *new_entry_enode->get_state ().m_region_model;
554 : 1054 : const store &new_store = *new_model.get_store ();
555 : :
556 : 8968 : for (auto kv : new_store)
557 : : {
558 : 4557 : const region *base_reg = kv.first;
559 : 4557 : if (sufficiently_different_region_binding_p (new_entry_enode,
560 : : prev_entry_enode,
561 : : base_reg))
562 : 600 : return true;
563 : : }
564 : :
565 : : /* No significant differences found. */
566 : 454 : return false;
567 : 1054 : }
568 : :
569 : : /* Implementation of -Wanalyzer-infinite-recursion.
570 : :
571 : : Called when adding ENODE to the graph, after adding its first in-edge.
572 : :
573 : : For function entrypoints, see if recursion has occurred, and, if so,
574 : : check if the state of memory changed between the recursion levels,
575 : : which would suggest some kind of decreasing variant that leads to
576 : : termination.
577 : :
578 : : For recursive calls where the state of memory is effectively unchanged
579 : : between recursion levels, warn with -Wanalyzer-infinite-recursion. */
580 : :
581 : : void
582 : 119461 : exploded_graph::detect_infinite_recursion (exploded_node *enode)
583 : : {
584 : 119461 : if (!is_entrypoint_p (enode))
585 : 119007 : return;
586 : 6175 : function *top_of_stack_fun = enode->get_function ();
587 : 6175 : gcc_assert (top_of_stack_fun);
588 : :
589 : : /* ....where a call to that function is already in the call string. */
590 : 6175 : const call_string &call_string = enode->get_point ().get_call_string ();
591 : :
592 : 6175 : if (call_string.count_occurrences_of_function (top_of_stack_fun) < 2)
593 : : return;
594 : :
595 : 1054 : tree fndecl = top_of_stack_fun->decl;
596 : :
597 : 1054 : log_scope s (get_logger (),
598 : : "checking for infinite recursion",
599 : : "considering recursion at EN: %i entering %qE",
600 : 1054 : enode->m_index, fndecl);
601 : :
602 : : /* Find enode that's the entrypoint for the previous frame for fndecl
603 : : in the recursion. */
604 : 1054 : exploded_node *prev_entry_enode
605 : 1054 : = find_previous_entry_to (top_of_stack_fun, enode);
606 : 1054 : gcc_assert (prev_entry_enode);
607 : 1054 : if (get_logger ())
608 : 0 : get_logger ()->log ("previous entrypoint to %qE is EN: %i",
609 : 0 : fndecl, prev_entry_enode->m_index);
610 : :
611 : : /* Look for changes to the state of memory between the recursion levels. */
612 : 1054 : if (sufficiently_different_p (enode, prev_entry_enode, get_logger ()))
613 : 600 : return;
614 : :
615 : : /* Otherwise, the state of memory is effectively the same between the two
616 : : recursion levels; warn. */
617 : :
618 : 454 : const supernode *caller_snode = call_string.get_top_of_stack ().m_caller;
619 : 454 : const supernode *snode = enode->get_supernode ();
620 : 454 : gcc_assert (caller_snode->m_returning_call);
621 : 454 : pending_location ploc (enode,
622 : : snode,
623 : : caller_snode->m_returning_call,
624 : 454 : nullptr);
625 : 454 : get_diagnostic_manager ().add_diagnostic
626 : 454 : (ploc,
627 : 454 : std::make_unique<infinite_recursion_diagnostic> (prev_entry_enode,
628 : : enode,
629 : : fndecl));
630 : 1054 : }
|
