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 : : #include "diagnostics/sarif-sink.h"
29 : :
30 : : #include "analyzer/analyzer-logging.h"
31 : : #include "analyzer/call-string.h"
32 : : #include "analyzer/program-point.h"
33 : : #include "analyzer/store.h"
34 : : #include "analyzer/region-model.h"
35 : : #include "analyzer/constraint-manager.h"
36 : : #include "analyzer/sm.h"
37 : : #include "analyzer/pending-diagnostic.h"
38 : : #include "analyzer/diagnostic-manager.h"
39 : : #include "analyzer/supergraph.h"
40 : : #include "analyzer/program-state.h"
41 : : #include "analyzer/exploded-graph.h"
42 : : #include "analyzer/checker-path.h"
43 : : #include "analyzer/feasible-graph.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 : 2842 : const char *get_kind () const final override
62 : : {
63 : 2842 : 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 : : void
227 : 0 : maybe_add_sarif_properties (diagnostics::sarif_object &result_obj)
228 : : const final override
229 : : {
230 : 0 : auto &props = result_obj.get_or_create_properties ();
231 : : #define PROPERTY_PREFIX "gcc/analyzer/infinite_recursion_diagnostic/"
232 : 0 : props.set_integer (PROPERTY_PREFIX "prev_entry_enode",
233 : 0 : m_prev_entry_enode->m_index);
234 : 0 : props.set_integer (PROPERTY_PREFIX "new_entry_enode",
235 : 0 : m_new_entry_enode->m_index);
236 : : #undef PROPERTY_PREFIX
237 : 0 : }
238 : :
239 : : private:
240 : : /* Return true iff control flow along FEDGE was affected by
241 : : a conjured_svalue. */
242 : 5041 : static bool fedge_uses_conjured_svalue_p (feasible_edge *fedge)
243 : : {
244 : 5041 : const exploded_edge *eedge = fedge->get_inner_edge ();
245 : 5041 : const superedge *sedge = eedge->m_sedge;
246 : 5041 : if (!sedge)
247 : : return false;
248 : 1928 : const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
249 : 1928 : if (!cfg_sedge)
250 : : return false;
251 : 1194 : const gimple *last_stmt = sedge->m_src->get_last_stmt ();
252 : 1194 : if (!last_stmt)
253 : : return false;
254 : :
255 : 496 : const feasible_node *dst_fnode
256 : : = static_cast<const feasible_node *> (fedge->m_dest);
257 : 496 : const region_model &model = dst_fnode->get_state ().get_model ();
258 : :
259 : 496 : if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt))
260 : : {
261 : 440 : if (expr_uses_conjured_svalue_p (model, gimple_cond_lhs (cond_stmt)))
262 : : return true;
263 : 412 : if (expr_uses_conjured_svalue_p (model, gimple_cond_rhs (cond_stmt)))
264 : : return true;
265 : : }
266 : 56 : else if (const gswitch *switch_stmt
267 : 5065 : = dyn_cast <const gswitch *> (last_stmt))
268 : : {
269 : 24 : if (expr_uses_conjured_svalue_p (model,
270 : : gimple_switch_index (switch_stmt)))
271 : : return true;
272 : : }
273 : : return false;
274 : : }
275 : :
276 : : /* Return true iff EXPR is affected by a conjured_svalue. */
277 : 876 : static bool expr_uses_conjured_svalue_p (const region_model &model,
278 : : tree expr)
279 : : {
280 : 876 : class conjured_svalue_finder : public visitor
281 : : {
282 : : public:
283 : 876 : conjured_svalue_finder () : m_found_conjured_svalues (false)
284 : : {
285 : : }
286 : : void
287 : 56 : visit_conjured_svalue (const conjured_svalue *) final override
288 : : {
289 : 56 : m_found_conjured_svalues = true;
290 : 56 : }
291 : :
292 : : bool m_found_conjured_svalues;
293 : : };
294 : :
295 : 876 : const svalue *sval = model.get_rvalue (expr, nullptr);
296 : 876 : conjured_svalue_finder v;
297 : 876 : sval->accept (&v);
298 : 876 : return v.m_found_conjured_svalues;
299 : : }
300 : :
301 : : const exploded_node *m_prev_entry_enode;
302 : : const exploded_node *m_new_entry_enode;
303 : : tree m_callee_fndecl;
304 : : const checker_event *m_prev_entry_event;
305 : : };
306 : :
307 : : /* Return true iff ENODE is the PK_BEFORE_SUPERNODE at a function
308 : : entrypoint. */
309 : :
310 : : static bool
311 : 139431 : is_entrypoint_p (exploded_node *enode)
312 : : {
313 : : /* Look for an entrypoint to a function... */
314 : 139431 : const supernode *snode = enode->get_supernode ();
315 : 139431 : if (!snode)
316 : : return false;
317 : 139431 : if (!snode->entry_p ())
318 : 11539 : return false;;
319 : 11539 : const program_point &point = enode->get_point ();
320 : 11539 : if (point.get_kind () != PK_BEFORE_SUPERNODE)
321 : 1606 : return false;
322 : : return true;
323 : : }
324 : :
325 : : /* Walk backwards through the eg, looking for the first
326 : : enode we find that's also the entrypoint of the same function. */
327 : :
328 : : exploded_node *
329 : 1054 : exploded_graph::find_previous_entry_to (function *top_of_stack_fun,
330 : : exploded_node *enode) const
331 : : {
332 : 1054 : auto_vec<exploded_node *> worklist;
333 : 1054 : hash_set<exploded_node *> visited;
334 : :
335 : 1054 : visited.add (enode);
336 : 4216 : for (auto in_edge : enode->m_preds)
337 : 1054 : worklist.safe_push (in_edge->m_src);
338 : :
339 : 18685 : while (worklist.length () > 0)
340 : : {
341 : 17631 : exploded_node *iter = worklist.pop ();
342 : :
343 : 17631 : if (is_entrypoint_p (iter)
344 : 17631 : && iter->get_function () == top_of_stack_fun)
345 : 1054 : return iter;
346 : :
347 : 16577 : if (visited.contains (iter))
348 : 32 : continue;
349 : 16545 : visited.add (iter);
350 : 66448 : for (auto in_edge : iter->m_preds)
351 : 16813 : worklist.safe_push (in_edge->m_src);
352 : : }
353 : :
354 : : /* Not found. */
355 : : return nullptr;
356 : 1054 : }
357 : :
358 : : /* Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
359 : : remap it to the equivalent region within EQUIV_PREV_FRAME.
360 : :
361 : : For example, given param "n" within frame "foo@3", and equiv prev frame
362 : : "foo@1", remap it to param "n" within frame "foo@1". */
363 : :
364 : : static const region *
365 : 828 : remap_enclosing_frame (const region *base_reg,
366 : : const frame_region *enclosing_frame,
367 : : const frame_region *equiv_prev_frame,
368 : : region_model_manager *mgr)
369 : : {
370 : 828 : gcc_assert (base_reg->get_parent_region () == enclosing_frame);
371 : 828 : switch (base_reg->get_kind ())
372 : : {
373 : 0 : default:
374 : : /* We should only encounter params and varargs at the topmost
375 : : entrypoint. */
376 : 0 : gcc_unreachable ();
377 : :
378 : 20 : case RK_VAR_ARG:
379 : 20 : {
380 : 20 : const var_arg_region *var_arg_reg = (const var_arg_region *)base_reg;
381 : 20 : return mgr->get_var_arg_region (equiv_prev_frame,
382 : 20 : var_arg_reg->get_index ());
383 : : }
384 : 808 : case RK_DECL:
385 : 808 : {
386 : 808 : const decl_region *decl_reg = (const decl_region *)base_reg;
387 : 808 : return equiv_prev_frame->get_region_for_local (mgr,
388 : : decl_reg->get_decl (),
389 : 808 : nullptr);
390 : : }
391 : : }
392 : : }
393 : :
394 : : /* Return true iff SVAL is unknown, or contains an unknown svalue. */
395 : :
396 : : static bool
397 : 7230 : contains_unknown_p (const svalue *sval)
398 : : {
399 : 7230 : if (sval->get_kind () == SK_UNKNOWN)
400 : : return true;
401 : 14208 : if (const compound_svalue *compound_sval
402 : 7104 : = sval->dyn_cast_compound_svalue ())
403 : 86 : for (auto iter : *compound_sval)
404 : 48 : if (iter.second->get_kind () == SK_UNKNOWN)
405 : 18 : return true;
406 : : return false;
407 : : }
408 : :
409 : : /* Subroutine of sufficiently_different_p. Compare the store bindings
410 : : for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE.
411 : :
412 : : Return true if the state of NEW_ENTRY_ENODE is sufficiently different
413 : : from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is
414 : : being modified, and thus the recursion isn't infinite.
415 : :
416 : : Return false if the states for BASE_REG are effectively the same. */
417 : :
418 : : static bool
419 : 4531 : sufficiently_different_region_binding_p (exploded_node *new_entry_enode,
420 : : exploded_node *prev_entry_enode,
421 : : const region *base_reg)
422 : : {
423 : : /* Compare the stores of the two enodes. */
424 : 4531 : const region_model &new_model
425 : 4531 : = *new_entry_enode->get_state ().m_region_model;
426 : 4531 : const region_model &prev_model
427 : 4531 : = *prev_entry_enode->get_state ().m_region_model;
428 : :
429 : : /* Get the value within the new frame. */
430 : 4531 : const svalue *new_sval
431 : 4531 : = new_model.get_store_value (base_reg, nullptr);
432 : :
433 : : /* If any part of the value is UNKNOWN (e.g. due to hitting
434 : : complexity limits) assume that it differs from the previous
435 : : value. */
436 : 4531 : if (contains_unknown_p (new_sval))
437 : : return true;
438 : :
439 : : /* Get the equivalent value within the old enode. */
440 : 4388 : const svalue *prev_sval;
441 : :
442 : 8776 : if (const frame_region *enclosing_frame
443 : 4388 : = base_reg->maybe_get_frame_region ())
444 : : {
445 : : /* We have a binding within a frame in the new entry enode. */
446 : :
447 : : /* Consider changes in bindings below the original entry
448 : : to the recursion. */
449 : 3947 : const int old_stack_depth = prev_entry_enode->get_stack_depth ();
450 : 3947 : if (enclosing_frame->get_stack_depth () < old_stack_depth)
451 : 1430 : prev_sval = prev_model.get_store_value (base_reg, nullptr);
452 : : else
453 : : {
454 : : /* Ignore bindings within frames below the new entry node. */
455 : 2517 : const int new_stack_depth = new_entry_enode->get_stack_depth ();
456 : 2517 : if (enclosing_frame->get_stack_depth () < new_stack_depth)
457 : : return false;
458 : :
459 : : /* We have a binding within the frame of the new entry node,
460 : : presumably a parameter. */
461 : :
462 : : /* Get the value within the equivalent frame of
463 : : the old entrypoint; typically will be the initial_svalue
464 : : of the parameter. */
465 : 828 : const frame_region *equiv_prev_frame
466 : 828 : = prev_model.get_current_frame ();
467 : 828 : const region *equiv_prev_base_reg
468 : 828 : = remap_enclosing_frame (base_reg,
469 : : enclosing_frame,
470 : : equiv_prev_frame,
471 : : new_model.get_manager ());
472 : 828 : prev_sval
473 : 828 : = prev_model.get_store_value (equiv_prev_base_reg, nullptr);
474 : : }
475 : : }
476 : : else
477 : 441 : prev_sval = prev_model.get_store_value (base_reg, nullptr);
478 : :
479 : : /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits)
480 : : assume that it will differ from any new value. */
481 : 2699 : if (contains_unknown_p (prev_sval))
482 : : return true;
483 : :
484 : 2698 : if (new_sval != prev_sval)
485 : : return true;
486 : :
487 : : return false;
488 : : }
489 : :
490 : : /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
491 : : both of which are entrypoints to the same function, where recursion has
492 : : occurred.
493 : :
494 : : Return true if the state of NEW_ENTRY_ENODE is sufficiently different
495 : : from PREV_ENTRY_ENODE to suggest that some variant is being modified,
496 : : and thus the recursion isn't infinite.
497 : :
498 : : Return false if the states are effectively the same, suggesting that
499 : : the recursion is infinite.
500 : :
501 : : For example, consider mutually recursive functions "foo" and "bar".
502 : : At the entrypoint to a "foo" frame where we've detected recursion,
503 : : we might have three frames on the stack: the new 'foo'@3, an inner
504 : : 'bar'@2, and the innermost 'foo'@1.
505 : :
506 : : (gdb) call enode->dump(m_ext_state)
507 : : EN: 16
508 : : callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
509 : : before SN: 0 (NULL from-edge)
510 : :
511 : : rmodel:
512 : : stack depth: 3
513 : : frame (index 2): frame: ‘foo’@3
514 : : frame (index 1): frame: ‘bar’@2
515 : : frame (index 0): frame: ‘foo’@1
516 : : clusters within root region
517 : : cluster for: (*INIT_VAL(f_4(D)))
518 : : clusters within frame: ‘bar’@2
519 : : cluster for: b_2(D): INIT_VAL(f_4(D))
520 : : clusters within frame: ‘foo’@3
521 : : cluster for: f_4(D): INIT_VAL(f_4(D))
522 : : m_called_unknown_fn: FALSE
523 : :
524 : : whereas for the previous entry node we'd have just the innermost
525 : : 'foo'@1
526 : :
527 : : (gdb) call prev_entry_enode->dump(m_ext_state)
528 : : EN: 1
529 : : callstring: []
530 : : before SN: 0 (NULL from-edge)
531 : :
532 : : rmodel:
533 : : stack depth: 1
534 : : frame (index 0): frame: ‘foo’@1
535 : : clusters within root region
536 : : cluster for: (*INIT_VAL(f_4(D)))
537 : : m_called_unknown_fn: FALSE
538 : :
539 : : We want to abstract away frames 1 and 2 in the new entry enode,
540 : : and compare its frame 3 with the frame 1 in the previous entry
541 : : enode, and determine if enough state changes between them to
542 : : rule out infinite recursion. */
543 : :
544 : : static bool
545 : 1054 : sufficiently_different_p (exploded_node *new_entry_enode,
546 : : exploded_node *prev_entry_enode,
547 : : logger *logger)
548 : : {
549 : 1054 : LOG_SCOPE (logger);
550 : 1054 : gcc_assert (new_entry_enode);
551 : 1054 : gcc_assert (prev_entry_enode);
552 : 1054 : gcc_assert (is_entrypoint_p (new_entry_enode));
553 : 1054 : gcc_assert (is_entrypoint_p (prev_entry_enode));
554 : :
555 : : /* Compare the stores of the two enodes. */
556 : 1054 : const region_model &new_model
557 : 1054 : = *new_entry_enode->get_state ().m_region_model;
558 : 1054 : const store &new_store = *new_model.get_store ();
559 : :
560 : 8916 : for (auto kv : new_store)
561 : : {
562 : 4531 : const region *base_reg = kv.first;
563 : 4531 : if (sufficiently_different_region_binding_p (new_entry_enode,
564 : : prev_entry_enode,
565 : : base_reg))
566 : 600 : return true;
567 : : }
568 : :
569 : : /* No significant differences found. */
570 : 454 : return false;
571 : 1054 : }
572 : :
573 : : /* Implementation of -Wanalyzer-infinite-recursion.
574 : :
575 : : Called when adding ENODE to the graph, after adding its first in-edge.
576 : :
577 : : For function entrypoints, see if recursion has occurred, and, if so,
578 : : check if the state of memory changed between the recursion levels,
579 : : which would suggest some kind of decreasing variant that leads to
580 : : termination.
581 : :
582 : : For recursive calls where the state of memory is effectively unchanged
583 : : between recursion levels, warn with -Wanalyzer-infinite-recursion. */
584 : :
585 : : void
586 : 119692 : exploded_graph::detect_infinite_recursion (exploded_node *enode)
587 : : {
588 : 119692 : if (!is_entrypoint_p (enode))
589 : 119238 : return;
590 : 6219 : function *top_of_stack_fun = enode->get_function ();
591 : 6219 : gcc_assert (top_of_stack_fun);
592 : :
593 : : /* ....where a call to that function is already in the call string. */
594 : 6219 : const call_string &call_string = enode->get_point ().get_call_string ();
595 : :
596 : 6219 : if (call_string.count_occurrences_of_function (top_of_stack_fun) < 2)
597 : : return;
598 : :
599 : 1054 : tree fndecl = top_of_stack_fun->decl;
600 : :
601 : 1054 : log_scope s (get_logger (),
602 : : "checking for infinite recursion",
603 : : "considering recursion at EN: %i entering %qE",
604 : 1054 : enode->m_index, fndecl);
605 : :
606 : : /* Find enode that's the entrypoint for the previous frame for fndecl
607 : : in the recursion. */
608 : 1054 : exploded_node *prev_entry_enode
609 : 1054 : = find_previous_entry_to (top_of_stack_fun, enode);
610 : 1054 : gcc_assert (prev_entry_enode);
611 : 1054 : if (get_logger ())
612 : 0 : get_logger ()->log ("previous entrypoint to %qE is EN: %i",
613 : 0 : fndecl, prev_entry_enode->m_index);
614 : :
615 : : /* Look for changes to the state of memory between the recursion levels. */
616 : 1054 : if (sufficiently_different_p (enode, prev_entry_enode, get_logger ()))
617 : 600 : return;
618 : :
619 : : /* Otherwise, the state of memory is effectively the same between the two
620 : : recursion levels; warn. */
621 : :
622 : 454 : const supernode *caller_snode = call_string.get_top_of_stack ().m_caller;
623 : 454 : const supernode *snode = enode->get_supernode ();
624 : 454 : gcc_assert (caller_snode->m_returning_call);
625 : 454 : pending_location ploc (enode,
626 : : snode,
627 : : caller_snode->m_returning_call,
628 : 454 : nullptr);
629 : 454 : get_diagnostic_manager ().add_diagnostic
630 : 454 : (ploc,
631 : 454 : std::make_unique<infinite_recursion_diagnostic> (prev_entry_enode,
632 : : enode,
633 : : fndecl));
634 : 1054 : }
|
