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

source code of gcc/analyzer/infinite-recursion.cc