1/* Detection of infinite loops.
2 Copyright (C) 2022-2025 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 "diagnostic-format-sarif.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 : start_cfg_edge_event (eedge, loc_info)
113 {
114 }
115
116 void print_desc (pretty_printer &pp) const final override
117 {
118 bool user_facing = !flag_analyzer_verbose_edges;
119 label_text edge_desc (m_sedge->get_description (user_facing));
120 if (user_facing)
121 {
122 if (edge_desc.get () && strlen (s: edge_desc.get ()) > 0)
123 {
124 label_text cond_desc
125 = maybe_describe_condition (can_colorize: pp_show_color (pp: &pp));
126 if (cond_desc.get ())
127 pp_printf (&pp,
128 "%s: always following %qs branch...",
129 cond_desc.get (), edge_desc.get ());
130 else
131 pp_printf (&pp,
132 "if it ever follows %qs branch,"
133 " it will always do so...",
134 edge_desc.get ());
135 }
136 }
137 else
138 return start_cfg_edge_event::print_desc (pp);
139 }
140};
141
142class looping_back_event : public start_cfg_edge_event
143{
144public:
145 looping_back_event (const exploded_edge &eedge,
146 const event_loc_info &loc_info)
147 : start_cfg_edge_event (eedge, loc_info)
148 {
149 }
150
151 void print_desc (pretty_printer &pp) const final override
152 {
153 pp_string (&pp, "looping back...");
154 }
155};
156
157/* A subclass of pending_diagnostic for complaining about suspected
158 infinite loops. */
159
160class infinite_loop_diagnostic
161: public pending_diagnostic_subclass<infinite_loop_diagnostic>
162{
163public:
164 infinite_loop_diagnostic (std::unique_ptr<infinite_loop> inf_loop)
165 : m_inf_loop (std::move (inf_loop))
166 {
167 gcc_assert (m_inf_loop != nullptr);
168 }
169
170 const char *get_kind () const final override
171 {
172 return "infinite_loop_diagnostic";
173 }
174
175 bool operator== (const infinite_loop_diagnostic &other) const
176 {
177 return *m_inf_loop == *other.m_inf_loop;
178 }
179
180 int get_controlling_option () const final override
181 {
182 return OPT_Wanalyzer_infinite_loop;
183 }
184
185 bool emit (diagnostic_emission_context &ctxt) final override
186 {
187 /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */
188 ctxt.add_cwe (cwe: 835);
189 return ctxt.warn ("infinite loop");
190 }
191
192 bool maybe_add_custom_events_for_superedge (const exploded_edge &,
193 checker_path *)
194 final override
195 {
196 /* Don't add any regular events; instead we add them after pruning as
197 part of the "final" warning. */
198 return true;
199 }
200
201 bool
202 describe_final_event (pretty_printer &pp,
203 const evdesc::final_event &) final override
204 {
205 pp_string (&pp, "infinite loop here");
206 return true;
207 }
208
209 /* Customize the location where the warning_event appears. */
210 void add_final_event (const state_machine *,
211 const exploded_node *enode,
212 const event_loc_info &,
213 tree,
214 state_machine::state_t,
215 checker_path *emission_path) final override
216 {
217 emission_path->add_event
218 (event: std::make_unique<warning_event>
219 (args: event_loc_info (m_inf_loop->m_loc,
220 enode->get_function ()->decl,
221 enode->get_stack_depth ()),
222 args&: enode,
223 args: nullptr, args: nullptr, args: nullptr));
224
225 logger *logger = emission_path->get_logger ();
226
227 /* EMISSION_PATH has the path to the entry of the infinite loop.
228 Add extra edges showing the loop itself. */
229 for (auto eedge : m_inf_loop->m_eedge_vec)
230 {
231 if (logger)
232 logger->log (fmt: "EN: %i -> EN: %i",
233 eedge->m_src->m_index,
234 eedge->m_dest->m_index);
235 if (!eedge->m_sedge)
236 continue;
237
238 const cfg_superedge *cfg_sedge
239 = eedge->m_sedge->dyn_cast_cfg_superedge ();
240 if (!cfg_sedge)
241 continue;
242
243 const exploded_node *src_node = eedge->m_src;
244 const program_point &src_point = src_node->get_point ();
245 const exploded_node *dst_node = eedge->m_dest;
246 const program_point &dst_point = dst_node->get_point ();
247 const int src_stack_depth = src_point.get_stack_depth ();
248 const int dst_stack_depth = dst_point.get_stack_depth ();
249 const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();
250
251 event_loc_info loc_info_from
252 (last_stmt ? last_stmt->location : cfg_sedge->get_goto_locus (),
253 src_point.get_fndecl (),
254 src_stack_depth);
255 event_loc_info loc_info_to
256 (dst_point.get_supernode ()->get_start_location (),
257 dst_point.get_fndecl (),
258 dst_stack_depth);
259
260 if (const switch_cfg_superedge *switch_cfg_sedge
261 = cfg_sedge->dyn_cast_switch_cfg_superedge ())
262 {
263 if (switch_cfg_sedge->implicitly_created_default_p ())
264 {
265 emission_path->add_event
266 (event: std::make_unique<perpetual_start_cfg_edge_event>
267 (args: *eedge,
268 args&: loc_info_from));
269 emission_path->add_event
270 (event: std::make_unique<end_cfg_edge_event>
271 (args: *eedge,
272 args&: loc_info_to));
273 }
274 }
275
276 if (cfg_sedge->true_value_p ())
277 {
278 emission_path->add_event
279 (event: std::make_unique<perpetual_start_cfg_edge_event>
280 (args: *eedge,
281 args&: loc_info_from));
282 emission_path->add_event
283 (event: std::make_unique<end_cfg_edge_event>
284 (args: *eedge,
285 args&: loc_info_to));
286 }
287 else if (cfg_sedge->false_value_p ())
288 {
289 emission_path->add_event
290 (event: std::make_unique<perpetual_start_cfg_edge_event>
291 (args: *eedge,
292 args&: loc_info_from));
293 emission_path->add_event
294 (event: std::make_unique<end_cfg_edge_event>
295 (args: *eedge,
296 args&: loc_info_to));
297 }
298 else if (cfg_sedge->back_edge_p ())
299 {
300 emission_path->add_event
301 (event: std::make_unique<looping_back_event> (args: *eedge, args&: loc_info_from));
302 emission_path->add_event
303 (event: std::make_unique<end_cfg_edge_event>
304 (args: *eedge,
305 args&: loc_info_to));
306 }
307 }
308 }
309
310 void maybe_add_sarif_properties (sarif_object &result_obj)
311 const final override
312 {
313 sarif_property_bag &props = result_obj.get_or_create_properties ();
314#define PROPERTY_PREFIX "gcc/analyzer/infinite_loop_diagnostic/"
315 props.set (PROPERTY_PREFIX "inf_loop", v: m_inf_loop->to_json ());
316#undef PROPERTY_PREFIX
317 }
318
319private:
320 std::unique_ptr<infinite_loop> m_inf_loop;
321};
322
323/* If ENODE has an in-edge corresponding to a CFG backedge, return that
324 exploded in-edge.
325 Otherwise, return nullptr. */
326
327static const exploded_edge *
328get_in_edge_back_edge (const exploded_node &enode)
329{
330 for (auto in_edge : enode.m_preds)
331 {
332 const superedge *sedge = in_edge->m_sedge;
333 if (!sedge)
334 continue;
335 const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
336 if (!cfg_sedge)
337 continue;
338 if (cfg_sedge->back_edge_p ())
339 return in_edge;
340 }
341 return nullptr;
342}
343
344/* Subclass of region_model_context that rejects conditional branches that
345 aren't known for definite. */
346
347class infinite_loop_checking_context : public noop_region_model_context
348{
349public:
350 infinite_loop_checking_context () : m_unusable (false) {}
351
352 bool checking_for_infinite_loop_p () const override { return true; }
353 void on_unusable_in_infinite_loop () override { m_unusable = true; }
354
355 bool unusable_p () const { return m_unusable; }
356
357private:
358 bool m_unusable;
359};
360
361/* Determine if an infinite loop starts at ENODE.
362 Return the loop if it is found, nullptr otherwise.
363
364 Look for cycles in the exploded graph in which:
365 - no externally visible work occurs
366 - no escape from the cycle
367 - the program state is "sufficiently concrete" at each step:
368 - no unknown activity could be occurring
369 - the worklist was fully drained for each enode in the cycle
370 i.e. every enode in the cycle is processed. */
371
372static std::unique_ptr<infinite_loop>
373starts_infinite_loop_p (const exploded_node &enode,
374 const exploded_graph &eg,
375 logger *logger)
376{
377 LOG_FUNC_1 (logger, "considering EN: %i", enode.m_index);
378
379 /* Only consider enodes that have a CFG back edge as an in-edge. */
380 if (const exploded_edge *back_edge = get_in_edge_back_edge (enode))
381 {
382 if (logger)
383 logger->log (fmt: "got backedge from EN: %i",
384 back_edge->m_src->m_index);
385 }
386 else
387 {
388 if (logger)
389 logger->log (fmt: "rejecting: no backedge in in-edges");
390 return nullptr;
391 }
392
393 /* Support for dumping an .infinite-loop.dot file visualizing the
394 traversal for this enode. */
395 std::unique_ptr<feasible_graph> fg;
396 feasible_node *curr_fnode = nullptr;
397
398 if (flag_dump_analyzer_infinite_loop)
399 fg = std::make_unique<feasible_graph> ();
400
401 location_t first_loc = UNKNOWN_LOCATION;
402 const exploded_node *iter = &enode;
403 feasibility_state state (*enode.get_state ().m_region_model,
404 eg.get_supergraph ());
405
406 if (fg)
407 curr_fnode = fg->add_node (enode: &enode, state, path_length: 0);
408
409 hash_set<const exploded_node *> visited;
410 std::vector<const exploded_edge *> eedges;
411 while (1)
412 {
413 if (logger)
414 logger->log (fmt: "iter: EN: %i", iter->m_index);
415 /* Analysis bailed out before processing this node. */
416 if (iter->get_status () == exploded_node::status::worklist)
417 {
418 if (logger)
419 logger->log (fmt: "rejecting: EN: %i is still in worklist",
420 iter->m_index);
421 return nullptr;
422 }
423 if (visited.contains (k: iter))
424 {
425 /* We've looped back on ourselves. ENODE is in the loop
426 itself if ENODE is the first place we looped back,
427 as opposed to being on a path to a loop. */
428 if (iter == &enode)
429 {
430 if (logger)
431 logger->log (fmt: "accepting: looped back to EN: %i",
432 iter->m_index);
433 if (fg)
434 {
435 auto_timevar tv (TV_ANALYZER_DUMP);
436 pretty_printer pp;
437 pp_printf (&pp, "%s.en%i.infinite-loop.dot",
438 dump_base_name, enode.m_index);
439 char *filename = xstrdup (pp_formatted_text (&pp));
440 feasible_graph::dump_args_t dump_args (eg);
441 fg->dump_dot (path: filename, root_cluster: nullptr, args: dump_args);
442 free (ptr: filename);
443 }
444 return std::make_unique<infinite_loop> (args: enode,
445 args&: first_loc,
446 args: std::move (eedges),
447 args&: logger);
448 }
449 else
450 {
451 if (logger)
452 logger->log (fmt: "rejecting: looped back to EN: %i, not to EN: %i",
453 iter->m_index, enode.m_index);
454 return nullptr;
455 }
456 }
457 visited.add (k: iter);
458 if (first_loc == UNKNOWN_LOCATION)
459 {
460 location_t enode_loc = iter->get_point ().get_location ();
461 if (enode_loc != UNKNOWN_LOCATION)
462 first_loc = enode_loc;
463 }
464
465 /* Find the out-edges that are feasible, given the
466 constraints here. */
467 typedef std::pair<feasibility_state, const exploded_edge *> pair_t;
468 std::vector<pair_t> succs;
469 for (auto out_edge : iter->m_succs)
470 {
471 log_scope s (logger, "considering out-edge",
472 "EN:%i -> EN:%i",
473 out_edge->m_src->m_index,
474 out_edge->m_dest->m_index);
475 feasibility_state next_state (state);
476
477 /* Use this context to require edge conditions to be known,
478 rather than be merely "possible". */
479 infinite_loop_checking_context ctxt;
480 if (next_state.maybe_update_for_edge (logger,
481 eedge: out_edge,
482 ctxt: &ctxt,
483 out_rc: nullptr))
484 succs.push_back (x: pair_t (next_state, out_edge));
485 if (ctxt.unusable_p ())
486 {
487 /* If we get here, then we have e.g. a gcond where
488 the condition is UNKNOWN, or a condition
489 based on a widening_svalue. Reject such paths. */
490 if (logger)
491 logger->log (fmt: "rejecting: unusable");
492 return nullptr;
493 }
494 }
495
496 if (succs.size () != 1)
497 {
498 if (logger)
499 logger->log (fmt: "rejecting: %i feasible successors",
500 (int)succs.size ());
501 return nullptr;
502 }
503 const feasibility_state &next_state = succs[0].first;
504 const exploded_edge *out_eedge = succs[0].second;
505 if (out_eedge->could_do_work_p ())
506 {
507 if (logger)
508 logger->log (fmt: "rejecting: edge could do work");
509 return nullptr;
510 }
511 if (fg)
512 {
513 feasible_node *next_fnode = fg->add_node (enode: out_eedge->m_dest,
514 state: next_state,
515 path_length: fg->m_nodes.length ());
516 fg->add_edge (edge: new feasible_edge (curr_fnode, next_fnode, out_eedge));
517 curr_fnode = next_fnode;
518 }
519 state = next_state;
520 eedges.push_back (x: out_eedge);
521 if (first_loc == UNKNOWN_LOCATION)
522 {
523 if (out_eedge->m_sedge)
524 if (::edge cfg_edge = out_eedge->m_sedge->get_any_cfg_edge ())
525 if (cfg_edge->goto_locus > BUILTINS_LOCATION)
526 first_loc = cfg_edge->goto_locus;
527 }
528 iter = out_eedge->m_dest;
529 }
530}
531
532/* Implementation of -Wanalyzer-infinite-loop. */
533
534void
535exploded_graph::detect_infinite_loops ()
536{
537 LOG_FUNC (get_logger ());
538 auto_timevar tv (TV_ANALYZER_INFINITE_LOOPS);
539
540 /* Track all enodes we've warned for; both the loop entrypoints
541 and all the enodes within those loops. */
542 hash_set<const exploded_node *> warned_for;
543
544 for (auto enode : m_nodes)
545 {
546 if (get_logger ())
547 get_logger ()->log (fmt: "visited: %i out of %i",
548 (int)warned_for.elements (), m_nodes.length ());
549
550 /* Only warn about the first enode we encounter in each cycle. */
551 if (warned_for.contains(k: enode))
552 continue;
553
554 if (std::unique_ptr<infinite_loop> inf_loop
555 = starts_infinite_loop_p (enode: *enode, eg: *this, logger: get_logger ()))
556 {
557 const supernode *snode = enode->get_supernode ();
558
559 if (get_logger ())
560 get_logger ()->log (fmt: "EN: %i from starts_infinite_loop_p",
561 enode->m_index);
562
563 for (auto iter : inf_loop->m_eedge_vec)
564 warned_for.add (k: iter->m_src);
565 gcc_assert (warned_for.contains(enode));
566
567 if (inf_loop->m_loc == UNKNOWN_LOCATION)
568 {
569 if (get_logger ())
570 get_logger ()->log
571 (fmt: "no location available for reporting infinite loop");
572 continue;
573 }
574
575 pending_location ploc (enode, snode, inf_loop->m_loc);
576 auto d
577 = std::make_unique<infinite_loop_diagnostic> (args: std::move (inf_loop));
578 get_diagnostic_manager ().add_diagnostic (ploc, d: std::move (d));
579 }
580 }
581}
582

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