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