Line data Source code
1 : /* Detection of infinite loops.
2 : Copyright (C) 2022-2026 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 bundle of data characterizing a particular infinite loop
46 : identified within the exploded graph. */
47 :
48 92 : struct infinite_loop
49 : {
50 92 : infinite_loop (const exploded_node &enode,
51 : location_t loc,
52 : std::vector<const exploded_edge *> &&eedges,
53 : logger *logger)
54 92 : : m_enode (enode),
55 92 : m_loc (loc),
56 92 : m_eedge_vec (eedges)
57 : {
58 92 : LOG_SCOPE (logger);
59 92 : if (logger)
60 : {
61 1 : logger->start_log_line ();
62 1 : logger->log_partial ("infinite loop: EN: %i", m_enode.m_index);
63 4 : for (auto eedge : m_eedge_vec)
64 : {
65 3 : logger->log_partial (" ->");
66 3 : if (const superedge *sedge = eedge->m_sedge)
67 : {
68 3 : sedge->dump_label_to_pp (logger->get_printer (), false);
69 : }
70 3 : logger->log_partial (" EN: %i", eedge->m_dest->m_index);
71 : }
72 1 : logger->end_log_line ();
73 : }
74 92 : }
75 :
76 : bool
77 92 : operator== (const infinite_loop &other) const
78 : {
79 : /* Compare underlying supernode, rather than enodes, so that
80 : we don't get duplicates in functions that are called from
81 : elsewhere. */
82 92 : return (m_enode.get_supernode () == other.m_enode.get_supernode ()
83 92 : && m_loc == other.m_loc);
84 : }
85 :
86 : std::unique_ptr<json::object>
87 0 : to_json () const
88 : {
89 0 : auto loop_obj = std::make_unique<json::object> ();
90 0 : loop_obj->set_integer ("enode", m_enode.m_index);
91 0 : auto edge_arr = std::make_unique<json::array> ();
92 0 : for (auto eedge : m_eedge_vec)
93 0 : edge_arr->append (eedge->to_json ());
94 0 : loop_obj->set ("eedges", std::move (edge_arr));
95 0 : return loop_obj;
96 0 : }
97 :
98 : const exploded_node &m_enode;
99 : location_t m_loc;
100 : std::vector<const exploded_edge *> m_eedge_vec;
101 : };
102 :
103 : /* A custom subclass of start_cfg_edge_event that rewords the
104 : message to indicate that the CFG edge is *always* taken on
105 : subsequent iterations, assuming it's been taken once. */
106 :
107 : class perpetual_start_cfg_edge_event : public start_cfg_edge_event
108 : {
109 : public:
110 66 : perpetual_start_cfg_edge_event (const exploded_edge &eedge,
111 : const event_loc_info &loc_info,
112 : const control_flow_op *op)
113 66 : : start_cfg_edge_event (eedge, loc_info, op)
114 : {
115 : }
116 :
117 132 : void print_desc (pretty_printer &pp) const final override
118 : {
119 132 : bool user_facing = !flag_analyzer_verbose_edges;
120 132 : label_text edge_desc (m_sedge->get_description (user_facing));
121 132 : if (user_facing)
122 : {
123 132 : if (edge_desc.get ()
124 132 : && strlen (edge_desc.get ()) > 0
125 264 : && m_op)
126 : {
127 132 : label_text cond_desc
128 132 : = m_op->maybe_describe_condition (pp_show_color (&pp));
129 132 : if (cond_desc.get ())
130 106 : pp_printf (&pp,
131 : "%s: always following %qs branch...",
132 : cond_desc.get (), edge_desc.get ());
133 : else
134 26 : pp_printf (&pp,
135 : "if it ever follows %qs branch,"
136 : " it will always do so...",
137 : edge_desc.get ());
138 132 : }
139 : }
140 : else
141 0 : return start_cfg_edge_event::print_desc (pp);
142 132 : }
143 : };
144 :
145 : class looping_back_event : public start_cfg_edge_event
146 : {
147 : public:
148 99 : looping_back_event (const exploded_edge &eedge,
149 : const event_loc_info &loc_info,
150 : const control_flow_op *op)
151 99 : : start_cfg_edge_event (eedge, loc_info, op)
152 : {
153 : }
154 :
155 204 : void print_desc (pretty_printer &pp) const final override
156 : {
157 204 : pp_string (&pp, "looping back...");
158 204 : }
159 : };
160 :
161 : /* A subclass of pending_diagnostic for complaining about suspected
162 : infinite loops. */
163 :
164 : class infinite_loop_diagnostic
165 : : public pending_diagnostic_subclass<infinite_loop_diagnostic>
166 : {
167 : public:
168 92 : infinite_loop_diagnostic (std::unique_ptr<infinite_loop> inf_loop)
169 92 : : m_inf_loop (std::move (inf_loop))
170 : {
171 92 : gcc_assert (m_inf_loop != nullptr);
172 92 : }
173 :
174 1292 : const char *get_kind () const final override
175 : {
176 1292 : return "infinite_loop_diagnostic";
177 : }
178 :
179 92 : bool operator== (const infinite_loop_diagnostic &other) const
180 : {
181 92 : return *m_inf_loop == *other.m_inf_loop;
182 : }
183 :
184 183 : int get_controlling_option () const final override
185 : {
186 183 : return OPT_Wanalyzer_infinite_loop;
187 : }
188 :
189 91 : bool emit (diagnostic_emission_context &ctxt) final override
190 : {
191 : /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */
192 91 : ctxt.add_cwe (835);
193 91 : return ctxt.warn ("infinite loop");
194 : }
195 :
196 977 : bool maybe_add_custom_events_for_eedge (const exploded_edge &,
197 : checker_path *)
198 : final override
199 : {
200 : /* Don't add any regular events; instead we add them after pruning as
201 : part of the "final" warning. */
202 977 : return true;
203 : }
204 :
205 : bool
206 182 : describe_final_event (pretty_printer &pp,
207 : const evdesc::final_event &) final override
208 : {
209 182 : pp_string (&pp, "infinite loop here");
210 182 : return true;
211 : }
212 :
213 : /* Customize the location where the warning_event appears. */
214 91 : void add_final_event (const state_machine *,
215 : const exploded_node *enode,
216 : const event_loc_info &,
217 : tree,
218 : state_machine::state_t,
219 : checker_path *emission_path) final override
220 : {
221 91 : emission_path->add_event
222 91 : (std::make_unique<warning_event>
223 91 : (event_loc_info (m_inf_loop->m_loc,
224 182 : enode->get_function ()->decl,
225 182 : enode->get_stack_depth ()),
226 : enode,
227 91 : nullptr, nullptr, nullptr));
228 :
229 91 : logger *logger = emission_path->get_logger ();
230 :
231 : /* EMISSION_PATH has the path to the entry of the infinite loop.
232 : Add extra edges showing the loop itself. */
233 489 : for (auto eedge : m_inf_loop->m_eedge_vec)
234 : {
235 398 : if (logger)
236 3 : logger->log ("EN: %i -> EN: %i",
237 3 : eedge->m_src->m_index,
238 3 : eedge->m_dest->m_index);
239 398 : if (!eedge->m_sedge)
240 231 : continue;
241 :
242 396 : ::edge cfg_edge = eedge->m_sedge->get_any_cfg_edge ();
243 396 : if (!cfg_edge)
244 229 : continue;
245 :
246 167 : const exploded_node *src_node = eedge->m_src;
247 167 : const program_point &src_point = src_node->get_point ();
248 167 : const exploded_node *dst_node = eedge->m_dest;
249 167 : const program_point &dst_point = dst_node->get_point ();
250 167 : const int src_stack_depth = src_point.get_stack_depth ();
251 167 : const int dst_stack_depth = dst_point.get_stack_depth ();
252 167 : event_loc_info loc_info_from
253 : (src_point.get_supernode ()->get_location (),
254 : src_point.get_fndecl (),
255 167 : src_stack_depth);
256 167 : event_loc_info loc_info_to
257 : (dst_point.get_supernode ()->get_location (),
258 : dst_point.get_fndecl (),
259 167 : dst_stack_depth);
260 167 : if (auto base_op = eedge->m_sedge->get_op ())
261 130 : if (auto control_flow_op = base_op->dyn_cast_control_flow_op ())
262 : {
263 78 : if (control_flow_op->get_kind () == operation::switch_edge)
264 : {
265 18 : const switch_case_op &case_op
266 : = *(const switch_case_op *)base_op;
267 18 : if (case_op.implicitly_created_default_p ())
268 : {
269 6 : emission_path->add_event
270 6 : (std::make_unique<perpetual_start_cfg_edge_event>
271 6 : (*eedge,
272 : loc_info_from,
273 : control_flow_op));
274 6 : emission_path->add_event
275 6 : (std::make_unique<end_cfg_edge_event>
276 6 : (*eedge,
277 : loc_info_to,
278 : control_flow_op));
279 : }
280 : }
281 60 : else if (cfg_edge->flags & EDGE_TRUE_VALUE)
282 : {
283 60 : emission_path->add_event
284 60 : (std::make_unique<perpetual_start_cfg_edge_event>
285 60 : (*eedge,
286 : loc_info_from,
287 : control_flow_op));
288 60 : emission_path->add_event
289 60 : (std::make_unique<end_cfg_edge_event>
290 60 : (*eedge,
291 : loc_info_to,
292 : control_flow_op));
293 : }
294 0 : else if (cfg_edge->flags & EDGE_FALSE_VALUE)
295 : {
296 0 : emission_path->add_event
297 0 : (std::make_unique<perpetual_start_cfg_edge_event>
298 0 : (*eedge,
299 : loc_info_from,
300 : control_flow_op));
301 0 : emission_path->add_event
302 0 : (std::make_unique<end_cfg_edge_event>
303 0 : (*eedge,
304 : loc_info_to,
305 : control_flow_op));
306 : }
307 : }
308 :
309 167 : if (cfg_edge->flags & EDGE_DFS_BACK)
310 : {
311 99 : emission_path->add_event
312 99 : (std::make_unique<looping_back_event> (*eedge, loc_info_from,
313 99 : nullptr));
314 99 : emission_path->add_event
315 99 : (std::make_unique<end_cfg_edge_event>
316 99 : (*eedge,
317 : loc_info_to,
318 198 : nullptr));
319 : }
320 : }
321 91 : }
322 :
323 : void
324 0 : maybe_add_sarif_properties (diagnostics::sarif_object &result_obj)
325 : const final override
326 : {
327 0 : auto &props = result_obj.get_or_create_properties ();
328 : #define PROPERTY_PREFIX "gcc/analyzer/infinite_loop_diagnostic/"
329 0 : props.set (PROPERTY_PREFIX "inf_loop", m_inf_loop->to_json ());
330 : #undef PROPERTY_PREFIX
331 0 : }
332 :
333 : private:
334 : std::unique_ptr<infinite_loop> m_inf_loop;
335 : };
336 :
337 : /* If ENODE has an in-edge corresponding to a CFG backedge, return that
338 : exploded in-edge.
339 : Otherwise, return nullptr. */
340 :
341 : static const exploded_edge *
342 389726 : get_in_edge_back_edge (const exploded_node &enode)
343 : {
344 1560138 : for (auto in_edge : enode.m_preds)
345 : {
346 403534 : const superedge *sedge = in_edge->m_sedge;
347 403534 : if (!sedge)
348 28617 : continue;
349 374917 : if (::edge cfg_in_edge = sedge->get_any_cfg_edge ())
350 107634 : if (cfg_in_edge->flags & EDGE_DFS_BACK)
351 : return in_edge;
352 : }
353 : return nullptr;
354 : }
355 :
356 : /* Subclass of region_model_context that rejects conditional branches that
357 : aren't known for definite. */
358 :
359 : class infinite_loop_checking_context : public noop_region_model_context
360 : {
361 : public:
362 64262 : infinite_loop_checking_context () : m_unusable (false) {}
363 :
364 8669 : bool checking_for_infinite_loop_p () const override { return true; }
365 3835 : void on_unusable_in_infinite_loop () override { m_unusable = true; }
366 :
367 64262 : bool unusable_p () const { return m_unusable; }
368 :
369 : private:
370 : bool m_unusable;
371 : };
372 :
373 : /* Determine if an infinite loop starts at ENODE.
374 : Return the loop if it is found, nullptr otherwise.
375 :
376 : Look for cycles in the exploded graph in which:
377 : - no externally visible work occurs
378 : - no escape from the cycle
379 : - the program state is "sufficiently concrete" at each step:
380 : - no unknown activity could be occurring
381 : - the worklist was fully drained for each enode in the cycle
382 : i.e. every enode in the cycle is processed. */
383 :
384 : static std::unique_ptr<infinite_loop>
385 389726 : starts_infinite_loop_p (const exploded_node &enode,
386 : const exploded_graph &eg,
387 : logger *logger)
388 : {
389 389726 : LOG_FUNC_1 (logger, "considering EN: %i", enode.m_index);
390 :
391 : /* Only consider enodes that have a CFG back edge as an in-edge. */
392 389726 : if (const exploded_edge *back_edge = get_in_edge_back_edge (enode))
393 : {
394 5828 : if (logger)
395 12 : logger->log ("got backedge from EN: %i",
396 12 : back_edge->m_src->m_index);
397 : }
398 : else
399 : {
400 383898 : if (logger)
401 190 : logger->log ("rejecting: no backedge in in-edges");
402 383898 : return nullptr;
403 : }
404 :
405 : /* Support for dumping an .infinite-loop.dot file visualizing the
406 : traversal for this enode. */
407 5828 : std::unique_ptr<feasible_graph> fg;
408 5828 : feasible_node *curr_fnode = nullptr;
409 :
410 5828 : if (flag_dump_analyzer_infinite_loop)
411 0 : fg = std::make_unique<feasible_graph> ();
412 :
413 5828 : location_t first_loc = UNKNOWN_LOCATION;
414 5828 : const exploded_node *iter = &enode;
415 5828 : feasibility_state state (*enode.get_state ().m_region_model,
416 5828 : eg.get_supergraph ());
417 :
418 5828 : if (fg)
419 0 : curr_fnode = fg->add_node (&enode, state, 0);
420 :
421 5828 : hash_set<const exploded_node *> visited;
422 5828 : std::vector<const exploded_edge *> eedges;
423 58655 : while (1)
424 : {
425 64483 : if (logger)
426 69 : logger->log ("iter: EN: %i", iter->m_index);
427 : /* Analysis bailed out before processing this node. */
428 64483 : if (iter->get_status () == exploded_node::status::worklist)
429 : {
430 79 : if (logger)
431 0 : logger->log ("rejecting: EN: %i is still in worklist",
432 0 : iter->m_index);
433 5828 : return nullptr;
434 : }
435 64404 : if (visited.contains (iter))
436 : {
437 : /* We've looped back on ourselves. ENODE is in the loop
438 : itself if ENODE is the first place we looped back,
439 : as opposed to being on a path to a loop. */
440 295 : if (iter == &enode)
441 : {
442 92 : if (logger)
443 1 : logger->log ("accepting: looped back to EN: %i",
444 1 : iter->m_index);
445 92 : if (fg)
446 : {
447 0 : auto_timevar tv (TV_ANALYZER_DUMP);
448 0 : pretty_printer pp;
449 0 : pp_printf (&pp, "%s.en%i.infinite-loop.dot",
450 0 : dump_base_name, enode.m_index);
451 0 : char *filename = xstrdup (pp_formatted_text (&pp));
452 0 : feasible_graph::dump_args_t dump_args (eg);
453 0 : fg->dump_dot (filename, nullptr, dump_args);
454 0 : free (filename);
455 0 : }
456 92 : return std::make_unique<infinite_loop> (enode,
457 : first_loc,
458 : std::move (eedges),
459 92 : logger);
460 : }
461 : else
462 : {
463 203 : if (logger)
464 0 : logger->log ("rejecting: looped back to EN: %i, not to EN: %i",
465 0 : iter->m_index, enode.m_index);
466 203 : return nullptr;
467 : }
468 : }
469 64109 : visited.add (iter);
470 64109 : if (first_loc == UNKNOWN_LOCATION)
471 : {
472 10839 : auto snode = iter->get_supernode ();
473 10839 : gcc_assert (snode);
474 : /* Ignore initial location in loop if it's a merger node,
475 : to avoid using locations of phi nodes that are at the end
476 : of the loop in the source. */
477 10839 : if (!(iter == &enode && snode->m_state_merger_node))
478 : {
479 5488 : location_t enode_loc = snode->get_location ();
480 5488 : if (useful_location_p (enode_loc))
481 5448 : first_loc = enode_loc;
482 : }
483 : }
484 :
485 : /* Find the out-edges that are feasible, given the
486 : constraints here. */
487 64109 : typedef std::pair<feasibility_state, const exploded_edge *> pair_t;
488 64109 : std::vector<pair_t> succs;
489 251286 : for (auto out_edge : iter->m_succs)
490 : {
491 64262 : log_scope s (logger, "considering out-edge",
492 : "EN:%i -> EN:%i",
493 64262 : out_edge->m_src->m_index,
494 64262 : out_edge->m_dest->m_index);
495 64262 : feasibility_state next_state (state);
496 :
497 : /* Use this context to require edge conditions to be known,
498 : rather than be merely "possible". */
499 64262 : infinite_loop_checking_context ctxt;
500 64262 : if (next_state.maybe_update_for_edge (logger,
501 : out_edge,
502 : &ctxt,
503 : nullptr))
504 59751 : succs.push_back (pair_t (next_state, out_edge));
505 64262 : if (ctxt.unusable_p ())
506 : {
507 : /* If we get here, then we have e.g. a gcond where
508 : the condition is UNKNOWN, or a condition
509 : based on a widening_svalue. Reject such paths. */
510 3835 : if (logger)
511 8 : logger->log ("rejecting: unusable");
512 3835 : return nullptr;
513 : }
514 64262 : }
515 :
516 60274 : if (succs.size () != 1)
517 : {
518 891 : if (logger)
519 0 : logger->log ("rejecting: %i feasible successors",
520 0 : (int)succs.size ());
521 891 : return nullptr;
522 : }
523 59383 : const feasibility_state &next_state = succs[0].first;
524 59383 : const exploded_edge *out_eedge = succs[0].second;
525 59383 : if (out_eedge->could_do_work_p ())
526 : {
527 728 : if (logger)
528 3 : logger->log ("rejecting: edge could do work");
529 728 : return nullptr;
530 : }
531 58655 : if (fg)
532 : {
533 0 : feasible_node *next_fnode = fg->add_node (out_eedge->m_dest,
534 : next_state,
535 0 : fg->m_nodes.length ());
536 0 : fg->add_edge (new feasible_edge (curr_fnode, next_fnode, out_eedge));
537 0 : curr_fnode = next_fnode;
538 : }
539 58655 : state = next_state;
540 58655 : eedges.push_back (out_eedge);
541 58655 : if (first_loc == UNKNOWN_LOCATION)
542 : {
543 5075 : if (out_eedge->m_sedge)
544 5075 : if (::edge cfg_edge = out_eedge->m_sedge->get_any_cfg_edge ())
545 11 : if (cfg_edge->goto_locus > BUILTINS_LOCATION)
546 1 : first_loc = cfg_edge->goto_locus;
547 : }
548 58655 : iter = out_eedge->m_dest;
549 64109 : }
550 389726 : }
551 :
552 : /* Implementation of -Wanalyzer-infinite-loop. */
553 :
554 : void
555 3377 : exploded_graph::detect_infinite_loops ()
556 : {
557 3377 : LOG_FUNC (get_logger ());
558 3377 : auto_timevar tv (TV_ANALYZER_INFINITE_LOOPS);
559 :
560 : /* Track all enodes we've warned for; both the loop entrypoints
561 : and all the enodes within those loops. */
562 3377 : hash_set<const exploded_node *> warned_for;
563 :
564 399909 : for (auto enode : m_nodes)
565 : {
566 389786 : if (get_logger ())
567 404 : get_logger ()->log ("visited: %i out of %i",
568 202 : (int)warned_for.elements (), m_nodes.length ());
569 :
570 : /* Only warn about the first enode we encounter in each cycle. */
571 389786 : if (warned_for.contains(enode))
572 60 : continue;
573 :
574 389726 : if (std::unique_ptr<infinite_loop> inf_loop
575 389726 : = starts_infinite_loop_p (*enode, *this, get_logger ()))
576 : {
577 92 : if (get_logger ())
578 1 : get_logger ()->log ("EN: %i from starts_infinite_loop_p",
579 1 : enode->m_index);
580 :
581 496 : for (auto iter : inf_loop->m_eedge_vec)
582 404 : warned_for.add (iter->m_src);
583 92 : gcc_assert (warned_for.contains(enode));
584 :
585 92 : if (inf_loop->m_loc == UNKNOWN_LOCATION)
586 : {
587 0 : if (get_logger ())
588 0 : get_logger ()->log
589 0 : ("no location available for reporting infinite loop");
590 0 : continue;
591 : }
592 :
593 92 : pending_location ploc (enode, inf_loop->m_loc);
594 92 : auto d
595 92 : = std::make_unique<infinite_loop_diagnostic> (std::move (inf_loop));
596 92 : get_diagnostic_manager ().add_diagnostic (std::move (ploc),
597 92 : std::move (d));
598 389726 : }
599 : }
600 3377 : }
|
