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