Update baseline symbols for hppa-linux.
[official-gcc.git] / gcc / analyzer / infinite-recursion.cc
blob9576ff5f58db9c46244dd3e8389ffe20b524f89f
1 /* Detection of infinite recursion.
2 Copyright (C) 2022-2023 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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.
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.
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/>. */
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 "diagnostic-metadata.h"
35 #include "function.h"
36 #include "pretty-print.h"
37 #include "sbitmap.h"
38 #include "bitmap.h"
39 #include "tristate.h"
40 #include "ordered-hash-map.h"
41 #include "selftest.h"
42 #include "json.h"
43 #include "analyzer/analyzer.h"
44 #include "analyzer/analyzer-logging.h"
45 #include "analyzer/call-string.h"
46 #include "analyzer/program-point.h"
47 #include "analyzer/store.h"
48 #include "analyzer/region-model.h"
49 #include "analyzer/constraint-manager.h"
50 #include "analyzer/sm.h"
51 #include "analyzer/pending-diagnostic.h"
52 #include "analyzer/diagnostic-manager.h"
53 #include "cfg.h"
54 #include "basic-block.h"
55 #include "gimple.h"
56 #include "gimple-iterator.h"
57 #include "gimple-pretty-print.h"
58 #include "cgraph.h"
59 #include "digraph.h"
60 #include "analyzer/supergraph.h"
61 #include "analyzer/program-state.h"
62 #include "analyzer/exploded-graph.h"
63 #include "make-unique.h"
64 #include "analyzer/checker-path.h"
65 #include "analyzer/feasible-graph.h"
67 /* A subclass of pending_diagnostic for complaining about suspected
68 infinite recursion. */
70 class infinite_recursion_diagnostic
71 : public pending_diagnostic_subclass<infinite_recursion_diagnostic>
73 public:
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)
83 const char *get_kind () const final override
85 return "infinite_recursion_diagnostic";
88 bool operator== (const infinite_recursion_diagnostic &other) const
90 return m_callee_fndecl == other.m_callee_fndecl;
93 int get_controlling_option () const final override
95 return OPT_Wanalyzer_infinite_recursion;
98 bool emit (rich_location *rich_loc, logger *) final override
100 /* "CWE-674: Uncontrolled Recursion". */
101 diagnostic_metadata m;
102 m.add_cwe (674);
103 return warning_meta (rich_loc, m, get_controlling_option (),
104 "infinite recursion");
107 label_text describe_final_event (const evdesc::final_event &ev) final override
109 const int frames_consumed = (m_new_entry_enode->get_stack_depth ()
110 - m_prev_entry_enode->get_stack_depth ());
111 if (frames_consumed > 1)
112 return ev.formatted_print
113 ("apparently infinite chain of mutually-recursive function calls,"
114 " consuming %i stack frames per recursion",
115 frames_consumed);
116 else
117 return ev.formatted_print ("apparently infinite recursion");
120 void
121 add_function_entry_event (const exploded_edge &eedge,
122 checker_path *emission_path) final override
124 /* Subclass of function_entry_event for use when reporting both
125 the initial and subsequent entries to the function of interest,
126 allowing for cross-referencing the first event in the description
127 of the second. */
128 class recursive_function_entry_event : public function_entry_event
130 public:
131 recursive_function_entry_event (const program_point &dst_point,
132 const infinite_recursion_diagnostic &pd,
133 bool topmost)
134 : function_entry_event (dst_point),
135 m_pd (pd),
136 m_topmost (topmost)
140 label_text
141 get_desc (bool can_colorize) const final override
143 if (m_topmost)
145 if (m_pd.m_prev_entry_event
146 && m_pd.m_prev_entry_event->get_id_ptr ()->known_p ())
147 return make_label_text
148 (can_colorize,
149 "recursive entry to %qE; previously entered at %@",
150 m_effective_fndecl,
151 m_pd.m_prev_entry_event->get_id_ptr ());
152 else
153 return make_label_text (can_colorize, "recursive entry to %qE",
154 m_effective_fndecl);
156 else
157 return make_label_text (can_colorize, "initial entry to %qE",
158 m_effective_fndecl);
161 private:
162 const infinite_recursion_diagnostic &m_pd;
163 bool m_topmost;
165 const exploded_node *dst_node = eedge.m_dest;
166 const program_point &dst_point = dst_node->get_point ();
167 if (eedge.m_dest == m_prev_entry_enode)
169 gcc_assert (m_prev_entry_event == NULL);
170 std::unique_ptr<checker_event> prev_entry_event
171 = make_unique <recursive_function_entry_event> (dst_point,
172 *this, false);
173 m_prev_entry_event = prev_entry_event.get ();
174 emission_path->add_event (std::move (prev_entry_event));
176 else if (eedge.m_dest == m_new_entry_enode)
177 emission_path->add_event
178 (make_unique<recursive_function_entry_event> (dst_point, *this, true));
179 else
180 pending_diagnostic::add_function_entry_event (eedge, emission_path);
183 /* Customize the location where the warning_event appears, putting
184 it at the topmost entrypoint to the function. */
185 void add_final_event (const state_machine *,
186 const exploded_node *enode,
187 const gimple *,
188 tree,
189 state_machine::state_t,
190 checker_path *emission_path) final override
192 gcc_assert (m_new_entry_enode);
193 emission_path->add_event
194 (make_unique<warning_event>
195 (event_loc_info (m_new_entry_enode->get_supernode
196 ()->get_start_location (),
197 m_callee_fndecl,
198 m_new_entry_enode->get_stack_depth ()),
199 enode,
200 NULL, NULL, NULL));
203 /* Reject paths in which conjured svalues have affected control flow
204 since m_prev_entry_enode. */
206 bool check_valid_fpath_p (const feasible_node &final_fnode,
207 const gimple *)
208 const final override
210 /* Reject paths in which calls with unknown side effects have occurred
211 since m_prev_entry_enode.
212 Find num calls with side effects. Walk backward until we reach the
213 pref */
214 gcc_assert (final_fnode.get_inner_node () == m_new_entry_enode);
216 /* FG is actually a tree. Walk backwards from FINAL_FNODE until we
217 reach the prev_entry_enode (or the origin). */
218 const feasible_node *iter_fnode = &final_fnode;
219 while (iter_fnode->get_inner_node ()->m_index != 0)
221 gcc_assert (iter_fnode->m_preds.length () == 1);
223 feasible_edge *pred_fedge
224 = static_cast <feasible_edge *> (iter_fnode->m_preds[0]);
226 /* Determine if conjured svalues have affected control flow
227 since the prev entry node. */
228 if (fedge_uses_conjured_svalue_p (pred_fedge))
229 /* If so, then reject this diagnostic. */
230 return false;
231 iter_fnode = static_cast <feasible_node *> (pred_fedge->m_src);
232 if (iter_fnode->get_inner_node () == m_prev_entry_enode)
233 /* Accept this diagnostic. */
234 return true;
237 /* We shouldn't get here; if we do, reject the diagnostic. */
238 gcc_unreachable ();
239 return false;
242 private:
243 /* Return true iff control flow along FEDGE was affected by
244 a conjured_svalue. */
245 static bool fedge_uses_conjured_svalue_p (feasible_edge *fedge)
247 const exploded_edge *eedge = fedge->get_inner_edge ();
248 const superedge *sedge = eedge->m_sedge;
249 if (!sedge)
250 return false;
251 const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
252 if (!cfg_sedge)
253 return false;
254 const gimple *last_stmt = sedge->m_src->get_last_stmt ();
255 if (!last_stmt)
256 return false;
258 const feasible_node *dst_fnode
259 = static_cast<const feasible_node *> (fedge->m_dest);
260 const region_model &model = dst_fnode->get_state ().get_model ();
262 if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt))
264 if (expr_uses_conjured_svalue_p (model, gimple_cond_lhs (cond_stmt)))
265 return true;
266 if (expr_uses_conjured_svalue_p (model, gimple_cond_rhs (cond_stmt)))
267 return true;
269 else if (const gswitch *switch_stmt
270 = dyn_cast <const gswitch *> (last_stmt))
272 if (expr_uses_conjured_svalue_p (model,
273 gimple_switch_index (switch_stmt)))
274 return true;
276 return false;
279 /* Return true iff EXPR is affected by a conjured_svalue. */
280 static bool expr_uses_conjured_svalue_p (const region_model &model,
281 tree expr)
283 class conjured_svalue_finder : public visitor
285 public:
286 conjured_svalue_finder () : m_found_conjured_svalues (false)
289 void
290 visit_conjured_svalue (const conjured_svalue *) final override
292 m_found_conjured_svalues = true;
295 bool m_found_conjured_svalues;
298 const svalue *sval = model.get_rvalue (expr, NULL);
299 conjured_svalue_finder v;
300 sval->accept (&v);
301 return v.m_found_conjured_svalues;
304 const exploded_node *m_prev_entry_enode;
305 const exploded_node *m_new_entry_enode;
306 tree m_callee_fndecl;
307 const checker_event *m_prev_entry_event;
310 /* Return true iff ENODE is the PK_BEFORE_SUPERNODE at a function
311 entrypoint. */
313 static bool
314 is_entrypoint_p (exploded_node *enode)
316 /* Look for an entrypoint to a function... */
317 const supernode *snode = enode->get_supernode ();
318 if (!snode)
319 return false;
320 if (!snode->entry_p ())
321 return false;;
322 const program_point &point = enode->get_point ();
323 if (point.get_kind () != PK_BEFORE_SUPERNODE)
324 return false;
325 return true;
328 /* Walk backwards through the eg, looking for the first
329 enode we find that's also the entrypoint of the same function. */
331 exploded_node *
332 exploded_graph::find_previous_entry_to (function *top_of_stack_fun,
333 exploded_node *enode) const
335 auto_vec<exploded_node *> worklist;
336 hash_set<exploded_node *> visited;
338 visited.add (enode);
339 for (auto in_edge : enode->m_preds)
340 worklist.safe_push (in_edge->m_src);
342 while (worklist.length () > 0)
344 exploded_node *iter = worklist.pop ();
346 if (is_entrypoint_p (iter)
347 && iter->get_function () == top_of_stack_fun)
348 return iter;
350 if (visited.contains (iter))
351 continue;
352 visited.add (iter);
353 for (auto in_edge : iter->m_preds)
354 worklist.safe_push (in_edge->m_src);
357 /* Not found. */
358 return NULL;
361 /* Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
362 remap it to the equivalent region within EQUIV_PREV_FRAME.
364 For example, given param "n" within frame "foo@3", and equiv prev frame
365 "foo@1", remap it to param "n" within frame "foo@1". */
367 static const region *
368 remap_enclosing_frame (const region *base_reg,
369 const frame_region *enclosing_frame,
370 const frame_region *equiv_prev_frame,
371 region_model_manager *mgr)
373 gcc_assert (base_reg->get_parent_region () == enclosing_frame);
374 switch (base_reg->get_kind ())
376 default:
377 /* We should only encounter params and varargs at the topmost
378 entrypoint. */
379 gcc_unreachable ();
381 case RK_VAR_ARG:
383 const var_arg_region *var_arg_reg = (const var_arg_region *)base_reg;
384 return mgr->get_var_arg_region (equiv_prev_frame,
385 var_arg_reg->get_index ());
387 case RK_DECL:
389 const decl_region *decl_reg = (const decl_region *)base_reg;
390 return equiv_prev_frame->get_region_for_local (mgr,
391 decl_reg->get_decl (),
392 NULL);
397 /* Return true iff SVAL is unknown, or contains an unknown svalue. */
399 static bool
400 contains_unknown_p (const svalue *sval)
402 if (sval->get_kind () == SK_UNKNOWN)
403 return true;
404 if (const compound_svalue *compound_sval
405 = sval->dyn_cast_compound_svalue ())
406 for (auto iter : *compound_sval)
407 if (iter.second->get_kind () == SK_UNKNOWN)
408 return true;
409 return false;
412 /* Subroutine of sufficiently_different_p. Compare the store bindings
413 for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE.
415 Return true if the state of NEW_ENTRY_ENODE is sufficiently different
416 from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is
417 being modified, and thus the recursion isn't infinite.
419 Return false if the states for BASE_REG are effectively the same. */
421 static bool
422 sufficiently_different_region_binding_p (exploded_node *new_entry_enode,
423 exploded_node *prev_entry_enode,
424 const region *base_reg)
426 /* Compare the stores of the two enodes. */
427 const region_model &new_model
428 = *new_entry_enode->get_state ().m_region_model;
429 const region_model &prev_model
430 = *prev_entry_enode->get_state ().m_region_model;
432 /* Get the value within the new frame. */
433 const svalue *new_sval
434 = new_model.get_store_value (base_reg, NULL);
436 /* If any part of the value is UNKNOWN (e.g. due to hitting
437 complexity limits) assume that it differs from the previous
438 value. */
439 if (contains_unknown_p (new_sval))
440 return true;
442 /* Get the equivalent value within the old enode. */
443 const svalue *prev_sval;
445 if (const frame_region *enclosing_frame
446 = base_reg->maybe_get_frame_region ())
448 /* We have a binding within a frame in the new entry enode. */
450 /* Consider changes in bindings below the original entry
451 to the recursion. */
452 const int old_stack_depth = prev_entry_enode->get_stack_depth ();
453 if (enclosing_frame->get_stack_depth () < old_stack_depth)
454 prev_sval = prev_model.get_store_value (base_reg, NULL);
455 else
457 /* Ignore bindings within frames below the new entry node. */
458 const int new_stack_depth = new_entry_enode->get_stack_depth ();
459 if (enclosing_frame->get_stack_depth () < new_stack_depth)
460 return false;
462 /* We have a binding within the frame of the new entry node,
463 presumably a parameter. */
465 /* Get the value within the equivalent frame of
466 the old entrypoint; typically will be the initial_svalue
467 of the parameter. */
468 const frame_region *equiv_prev_frame
469 = prev_model.get_current_frame ();
470 const region *equiv_prev_base_reg
471 = remap_enclosing_frame (base_reg,
472 enclosing_frame,
473 equiv_prev_frame,
474 new_model.get_manager ());
475 prev_sval
476 = prev_model.get_store_value (equiv_prev_base_reg, NULL);
479 else
480 prev_sval = prev_model.get_store_value (base_reg, NULL);
482 /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits)
483 assume that it will differ from any new value. */
484 if (contains_unknown_p (prev_sval))
485 return true;
487 if (new_sval != prev_sval)
488 return true;
490 return false;
493 /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
494 both of which are entrypoints to the same function, where recursion has
495 occurred.
497 Return true if the state of NEW_ENTRY_ENODE is sufficiently different
498 from PREV_ENTRY_ENODE to suggest that some variant is being modified,
499 and thus the recursion isn't infinite.
501 Return false if the states are effectively the same, suggesting that
502 the recursion is infinite.
504 For example, consider mutually recursive functions "foo" and "bar".
505 At the entrypoint to a "foo" frame where we've detected recursion,
506 we might have three frames on the stack: the new 'foo'@3, an inner
507 'bar'@2, and the innermost 'foo'@1.
509 (gdb) call enode->dump(m_ext_state)
510 EN: 16
511 callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
512 before SN: 0 (NULL from-edge)
514 rmodel:
515 stack depth: 3
516 frame (index 2): frame: ‘foo’@3
517 frame (index 1): frame: ‘bar’@2
518 frame (index 0): frame: ‘foo’@1
519 clusters within root region
520 cluster for: (*INIT_VAL(f_4(D)))
521 clusters within frame: ‘bar’@2
522 cluster for: b_2(D): INIT_VAL(f_4(D))
523 clusters within frame: ‘foo’@3
524 cluster for: f_4(D): INIT_VAL(f_4(D))
525 m_called_unknown_fn: FALSE
527 whereas for the previous entry node we'd have just the innermost
528 'foo'@1
530 (gdb) call prev_entry_enode->dump(m_ext_state)
531 EN: 1
532 callstring: []
533 before SN: 0 (NULL from-edge)
535 rmodel:
536 stack depth: 1
537 frame (index 0): frame: ‘foo’@1
538 clusters within root region
539 cluster for: (*INIT_VAL(f_4(D)))
540 m_called_unknown_fn: FALSE
542 We want to abstract away frames 1 and 2 in the new entry enode,
543 and compare its frame 3 with the frame 1 in the previous entry
544 enode, and determine if enough state changes between them to
545 rule out infinite recursion. */
547 static bool
548 sufficiently_different_p (exploded_node *new_entry_enode,
549 exploded_node *prev_entry_enode,
550 logger *logger)
552 LOG_SCOPE (logger);
553 gcc_assert (new_entry_enode);
554 gcc_assert (prev_entry_enode);
555 gcc_assert (is_entrypoint_p (new_entry_enode));
556 gcc_assert (is_entrypoint_p (prev_entry_enode));
558 /* Compare the stores of the two enodes. */
559 const region_model &new_model
560 = *new_entry_enode->get_state ().m_region_model;
561 const store &new_store = *new_model.get_store ();
563 for (auto kv : new_store)
565 const region *base_reg = kv.first;
566 if (sufficiently_different_region_binding_p (new_entry_enode,
567 prev_entry_enode,
568 base_reg))
569 return true;
572 /* No significant differences found. */
573 return false;
576 /* Implementation of -Wanalyzer-infinite-recursion.
578 Called when adding ENODE to the graph, after adding its first in-edge.
580 For function entrypoints, see if recursion has occurred, and, if so,
581 check if the state of memory changed between the recursion levels,
582 which would suggest some kind of decreasing variant that leads to
583 termination.
585 For recursive calls where the state of memory is effectively unchanged
586 between recursion levels, warn with -Wanalyzer-infinite-recursion. */
588 void
589 exploded_graph::detect_infinite_recursion (exploded_node *enode)
591 if (!is_entrypoint_p (enode))
592 return;
593 function *top_of_stack_fun = enode->get_function ();
594 gcc_assert (top_of_stack_fun);
596 /* ....where a call to that function is already in the call string. */
597 const call_string &call_string = enode->get_point ().get_call_string ();
599 if (call_string.count_occurrences_of_function (top_of_stack_fun) < 2)
600 return;
602 tree fndecl = top_of_stack_fun->decl;
604 log_scope s (get_logger (),
605 "checking for infinite recursion",
606 "considering recursion at EN: %i entering %qE",
607 enode->m_index, fndecl);
609 /* Find enode that's the entrypoint for the previous frame for fndecl
610 in the recursion. */
611 exploded_node *prev_entry_enode
612 = find_previous_entry_to (top_of_stack_fun, enode);
613 gcc_assert (prev_entry_enode);
614 if (get_logger ())
615 get_logger ()->log ("previous entrypoint to %qE is EN: %i",
616 fndecl, prev_entry_enode->m_index);
618 /* Look for changes to the state of memory between the recursion levels. */
619 if (sufficiently_different_p (enode, prev_entry_enode, get_logger ()))
620 return;
622 /* Otherwise, the state of memory is effectively the same between the two
623 recursion levels; warn. */
625 const supernode *caller_snode = call_string.get_top_of_stack ().m_caller;
626 const supernode *snode = enode->get_supernode ();
627 gcc_assert (caller_snode->m_returning_call);
628 pending_location ploc (enode,
629 snode,
630 caller_snode->m_returning_call,
631 nullptr);
632 get_diagnostic_manager ().add_diagnostic
633 (ploc,
634 make_unique<infinite_recursion_diagnostic> (prev_entry_enode,
635 enode,
636 fndecl));