1/* Detection of infinite loops.
2 Copyright (C) 2022-2026 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 "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
48struct infinite_loop
49{
50 infinite_loop (const exploded_node &enode,
51 location_t loc,
52 std::vector<const exploded_edge *> &&eedges,
53 logger *logger)
54 : m_enode (enode),
55 m_loc (loc),
56 m_eedge_vec (eedges)
57 {
58 LOG_SCOPE (logger);
59 if (logger)
60 {
61 logger->start_log_line ();
62 logger->log_partial (fmt: "infinite loop: EN: %i", m_enode.m_index);
63 for (auto eedge : m_eedge_vec)
64 {
65 logger->log_partial (fmt: " ->");
66 if (const superedge *sedge = eedge->m_sedge)
67 {
68 sedge->dump_label_to_pp (pp: logger->get_printer (), user_facing: false);
69 }
70 logger->log_partial (fmt: " EN: %i", eedge->m_dest->m_index);
71 }
72 logger->end_log_line ();
73 }
74 }
75
76 bool
77 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 return (m_enode.get_supernode () == other.m_enode.get_supernode ()
83 && m_loc == other.m_loc);
84 }
85
86 std::unique_ptr<json::object>
87 to_json () const
88 {
89 auto loop_obj = std::make_unique<json::object> ();
90 loop_obj->set_integer (key: "enode", v: m_enode.m_index);
91 auto edge_arr = std::make_unique<json::array> ();
92 for (auto eedge : m_eedge_vec)
93 edge_arr->append (v: eedge->to_json ());
94 loop_obj->set (key: "eedges", v: std::move (edge_arr));
95 return loop_obj;
96 }
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
107class perpetual_start_cfg_edge_event : public start_cfg_edge_event
108{
109public:
110 perpetual_start_cfg_edge_event (const exploded_edge &eedge,
111 const event_loc_info &loc_info,
112 const control_flow_op *op)
113 : start_cfg_edge_event (eedge, loc_info, op)
114 {
115 }
116
117 void print_desc (pretty_printer &pp) const final override
118 {
119 bool user_facing = !flag_analyzer_verbose_edges;
120 label_text edge_desc (m_sedge->get_description (user_facing));
121 if (user_facing)
122 {
123 if (edge_desc.get ()
124 && strlen (s: edge_desc.get ()) > 0
125 && m_op)
126 {
127 label_text cond_desc
128 = m_op->maybe_describe_condition (can_colorize: pp_show_color (pp: &pp));
129 if (cond_desc.get ())
130 pp_printf (&pp,
131 "%s: always following %qs branch...",
132 cond_desc.get (), edge_desc.get ());
133 else
134 pp_printf (&pp,
135 "if it ever follows %qs branch,"
136 " it will always do so...",
137 edge_desc.get ());
138 }
139 }
140 else
141 return start_cfg_edge_event::print_desc (pp);
142 }
143};
144
145class looping_back_event : public start_cfg_edge_event
146{
147public:
148 looping_back_event (const exploded_edge &eedge,
149 const event_loc_info &loc_info,
150 const control_flow_op *op)
151 : start_cfg_edge_event (eedge, loc_info, op)
152 {
153 }
154
155 void print_desc (pretty_printer &pp) const final override
156 {
157 pp_string (&pp, "looping back...");
158 }
159};
160
161/* A subclass of pending_diagnostic for complaining about suspected
162 infinite loops. */
163
164class infinite_loop_diagnostic
165: public pending_diagnostic_subclass<infinite_loop_diagnostic>
166{
167public:
168 infinite_loop_diagnostic (std::unique_ptr<infinite_loop> inf_loop)
169 : m_inf_loop (std::move (inf_loop))
170 {
171 gcc_assert (m_inf_loop != nullptr);
172 }
173
174 const char *get_kind () const final override
175 {
176 return "infinite_loop_diagnostic";
177 }
178
179 bool operator== (const infinite_loop_diagnostic &other) const
180 {
181 return *m_inf_loop == *other.m_inf_loop;
182 }
183
184 int get_controlling_option () const final override
185 {
186 return OPT_Wanalyzer_infinite_loop;
187 }
188
189 bool emit (diagnostic_emission_context &ctxt) final override
190 {
191 /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */
192 ctxt.add_cwe (cwe: 835);
193 return ctxt.warn ("infinite loop");
194 }
195
196 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 return true;
203 }
204
205 bool
206 describe_final_event (pretty_printer &pp,
207 const evdesc::final_event &) final override
208 {
209 pp_string (&pp, "infinite loop here");
210 return true;
211 }
212
213 /* Customize the location where the warning_event appears. */
214 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 emission_path->add_event
222 (event: std::make_unique<warning_event>
223 (args: event_loc_info (m_inf_loop->m_loc,
224 enode->get_function ()->decl,
225 enode->get_stack_depth ()),
226 args&: enode,
227 args: nullptr, args: nullptr, args: nullptr));
228
229 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 for (auto eedge : m_inf_loop->m_eedge_vec)
234 {
235 if (logger)
236 logger->log (fmt: "EN: %i -> EN: %i",
237 eedge->m_src->m_index,
238 eedge->m_dest->m_index);
239 if (!eedge->m_sedge)
240 continue;
241
242 ::edge cfg_edge = eedge->m_sedge->get_any_cfg_edge ();
243 if (!cfg_edge)
244 continue;
245
246 const exploded_node *src_node = eedge->m_src;
247 const program_point &src_point = src_node->get_point ();
248 const exploded_node *dst_node = eedge->m_dest;
249 const program_point &dst_point = dst_node->get_point ();
250 const int src_stack_depth = src_point.get_stack_depth ();
251 const int dst_stack_depth = dst_point.get_stack_depth ();
252 event_loc_info loc_info_from
253 (src_point.get_supernode ()->get_location (),
254 src_point.get_fndecl (),
255 src_stack_depth);
256 event_loc_info loc_info_to
257 (dst_point.get_supernode ()->get_location (),
258 dst_point.get_fndecl (),
259 dst_stack_depth);
260 if (auto base_op = eedge->m_sedge->get_op ())
261 if (auto control_flow_op = base_op->dyn_cast_control_flow_op ())
262 {
263 if (control_flow_op->get_kind () == operation::switch_edge)
264 {
265 const switch_case_op &case_op
266 = *(const switch_case_op *)base_op;
267 if (case_op.implicitly_created_default_p ())
268 {
269 emission_path->add_event
270 (event: std::make_unique<perpetual_start_cfg_edge_event>
271 (args: *eedge,
272 args&: loc_info_from,
273 args&: control_flow_op));
274 emission_path->add_event
275 (event: std::make_unique<end_cfg_edge_event>
276 (args: *eedge,
277 args&: loc_info_to,
278 args&: control_flow_op));
279 }
280 }
281 else if (cfg_edge->flags & EDGE_TRUE_VALUE)
282 {
283 emission_path->add_event
284 (event: std::make_unique<perpetual_start_cfg_edge_event>
285 (args: *eedge,
286 args&: loc_info_from,
287 args&: control_flow_op));
288 emission_path->add_event
289 (event: std::make_unique<end_cfg_edge_event>
290 (args: *eedge,
291 args&: loc_info_to,
292 args&: control_flow_op));
293 }
294 else if (cfg_edge->flags & EDGE_FALSE_VALUE)
295 {
296 emission_path->add_event
297 (event: std::make_unique<perpetual_start_cfg_edge_event>
298 (args: *eedge,
299 args&: loc_info_from,
300 args&: control_flow_op));
301 emission_path->add_event
302 (event: std::make_unique<end_cfg_edge_event>
303 (args: *eedge,
304 args&: loc_info_to,
305 args&: control_flow_op));
306 }
307 }
308
309 if (cfg_edge->flags & EDGE_DFS_BACK)
310 {
311 emission_path->add_event
312 (event: std::make_unique<looping_back_event> (args: *eedge, args&: loc_info_from,
313 args: nullptr));
314 emission_path->add_event
315 (event: std::make_unique<end_cfg_edge_event>
316 (args: *eedge,
317 args&: loc_info_to,
318 args: nullptr));
319 }
320 }
321 }
322
323 void
324 maybe_add_sarif_properties (diagnostics::sarif_object &result_obj)
325 const final override
326 {
327 auto &props = result_obj.get_or_create_properties ();
328#define PROPERTY_PREFIX "gcc/analyzer/infinite_loop_diagnostic/"
329 props.set (PROPERTY_PREFIX "inf_loop", v: m_inf_loop->to_json ());
330#undef PROPERTY_PREFIX
331 }
332
333private:
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
341static const exploded_edge *
342get_in_edge_back_edge (const exploded_node &enode)
343{
344 for (auto in_edge : enode.m_preds)
345 {
346 const superedge *sedge = in_edge->m_sedge;
347 if (!sedge)
348 continue;
349 if (::edge cfg_in_edge = sedge->get_any_cfg_edge ())
350 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
359class infinite_loop_checking_context : public noop_region_model_context
360{
361public:
362 infinite_loop_checking_context () : m_unusable (false) {}
363
364 bool checking_for_infinite_loop_p () const override { return true; }
365 void on_unusable_in_infinite_loop () override { m_unusable = true; }
366
367 bool unusable_p () const { return m_unusable; }
368
369private:
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
384static std::unique_ptr<infinite_loop>
385starts_infinite_loop_p (const exploded_node &enode,
386 const exploded_graph &eg,
387 logger *logger)
388{
389 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 if (const exploded_edge *back_edge = get_in_edge_back_edge (enode))
393 {
394 if (logger)
395 logger->log (fmt: "got backedge from EN: %i",
396 back_edge->m_src->m_index);
397 }
398 else
399 {
400 if (logger)
401 logger->log (fmt: "rejecting: no backedge in in-edges");
402 return nullptr;
403 }
404
405 /* Support for dumping an .infinite-loop.dot file visualizing the
406 traversal for this enode. */
407 std::unique_ptr<feasible_graph> fg;
408 feasible_node *curr_fnode = nullptr;
409
410 if (flag_dump_analyzer_infinite_loop)
411 fg = std::make_unique<feasible_graph> ();
412
413 location_t first_loc = UNKNOWN_LOCATION;
414 const exploded_node *iter = &enode;
415 feasibility_state state (*enode.get_state ().m_region_model,
416 eg.get_supergraph ());
417
418 if (fg)
419 curr_fnode = fg->add_node (enode: &enode, state, path_length: 0);
420
421 hash_set<const exploded_node *> visited;
422 std::vector<const exploded_edge *> eedges;
423 while (1)
424 {
425 if (logger)
426 logger->log (fmt: "iter: EN: %i", iter->m_index);
427 /* Analysis bailed out before processing this node. */
428 if (iter->get_status () == exploded_node::status::worklist)
429 {
430 if (logger)
431 logger->log (fmt: "rejecting: EN: %i is still in worklist",
432 iter->m_index);
433 return nullptr;
434 }
435 if (visited.contains (k: 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 if (iter == &enode)
441 {
442 if (logger)
443 logger->log (fmt: "accepting: looped back to EN: %i",
444 iter->m_index);
445 if (fg)
446 {
447 auto_timevar tv (TV_ANALYZER_DUMP);
448 pretty_printer pp;
449 pp_printf (&pp, "%s.en%i.infinite-loop.dot",
450 dump_base_name, enode.m_index);
451 char *filename = xstrdup (pp_formatted_text (&pp));
452 feasible_graph::dump_args_t dump_args (eg);
453 fg->dump_dot (path: filename, root_cluster: nullptr, args: dump_args);
454 free (ptr: filename);
455 }
456 return std::make_unique<infinite_loop> (args: enode,
457 args&: first_loc,
458 args: std::move (eedges),
459 args&: logger);
460 }
461 else
462 {
463 if (logger)
464 logger->log (fmt: "rejecting: looped back to EN: %i, not to EN: %i",
465 iter->m_index, enode.m_index);
466 return nullptr;
467 }
468 }
469 visited.add (k: iter);
470 if (first_loc == UNKNOWN_LOCATION)
471 {
472 auto snode = iter->get_supernode ();
473 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 if (!(iter == &enode && snode->m_state_merger_node))
478 {
479 location_t enode_loc = snode->get_location ();
480 if (useful_location_p (loc: enode_loc))
481 first_loc = enode_loc;
482 }
483 }
484
485 /* Find the out-edges that are feasible, given the
486 constraints here. */
487 typedef std::pair<feasibility_state, const exploded_edge *> pair_t;
488 std::vector<pair_t> succs;
489 for (auto out_edge : iter->m_succs)
490 {
491 log_scope s (logger, "considering out-edge",
492 "EN:%i -> EN:%i",
493 out_edge->m_src->m_index,
494 out_edge->m_dest->m_index);
495 feasibility_state next_state (state);
496
497 /* Use this context to require edge conditions to be known,
498 rather than be merely "possible". */
499 infinite_loop_checking_context ctxt;
500 if (next_state.maybe_update_for_edge (logger,
501 eedge: out_edge,
502 ctxt: &ctxt,
503 out_rc: nullptr))
504 succs.push_back (x: pair_t (next_state, out_edge));
505 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 if (logger)
511 logger->log (fmt: "rejecting: unusable");
512 return nullptr;
513 }
514 }
515
516 if (succs.size () != 1)
517 {
518 if (logger)
519 logger->log (fmt: "rejecting: %i feasible successors",
520 (int)succs.size ());
521 return nullptr;
522 }
523 const feasibility_state &next_state = succs[0].first;
524 const exploded_edge *out_eedge = succs[0].second;
525 if (out_eedge->could_do_work_p ())
526 {
527 if (logger)
528 logger->log (fmt: "rejecting: edge could do work");
529 return nullptr;
530 }
531 if (fg)
532 {
533 feasible_node *next_fnode = fg->add_node (enode: out_eedge->m_dest,
534 state: next_state,
535 path_length: fg->m_nodes.length ());
536 fg->add_edge (edge: new feasible_edge (curr_fnode, next_fnode, out_eedge));
537 curr_fnode = next_fnode;
538 }
539 state = next_state;
540 eedges.push_back (x: out_eedge);
541 if (first_loc == UNKNOWN_LOCATION)
542 {
543 if (out_eedge->m_sedge)
544 if (::edge cfg_edge = out_eedge->m_sedge->get_any_cfg_edge ())
545 if (cfg_edge->goto_locus > BUILTINS_LOCATION)
546 first_loc = cfg_edge->goto_locus;
547 }
548 iter = out_eedge->m_dest;
549 }
550}
551
552/* Implementation of -Wanalyzer-infinite-loop. */
553
554void
555exploded_graph::detect_infinite_loops ()
556{
557 LOG_FUNC (get_logger ());
558 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 hash_set<const exploded_node *> warned_for;
563
564 for (auto enode : m_nodes)
565 {
566 if (get_logger ())
567 get_logger ()->log (fmt: "visited: %i out of %i",
568 (int)warned_for.elements (), m_nodes.length ());
569
570 /* Only warn about the first enode we encounter in each cycle. */
571 if (warned_for.contains(k: enode))
572 continue;
573
574 if (std::unique_ptr<infinite_loop> inf_loop
575 = starts_infinite_loop_p (enode: *enode, eg: *this, logger: get_logger ()))
576 {
577 if (get_logger ())
578 get_logger ()->log (fmt: "EN: %i from starts_infinite_loop_p",
579 enode->m_index);
580
581 for (auto iter : inf_loop->m_eedge_vec)
582 warned_for.add (k: iter->m_src);
583 gcc_assert (warned_for.contains(enode));
584
585 if (inf_loop->m_loc == UNKNOWN_LOCATION)
586 {
587 if (get_logger ())
588 get_logger ()->log
589 (fmt: "no location available for reporting infinite loop");
590 continue;
591 }
592
593 pending_location ploc (enode, inf_loop->m_loc);
594 auto d
595 = std::make_unique<infinite_loop_diagnostic> (args: std::move (inf_loop));
596 get_diagnostic_manager ().add_diagnostic (ploc: std::move (ploc),
597 d: std::move (d));
598 }
599 }
600}
601

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