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 "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 : :
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 : 341 : const char *get_kind () const final override
171 : : {
172 : 341 : 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 : 0 : void maybe_add_sarif_properties (sarif_object &result_obj)
311 : : const final override
312 : : {
313 : 0 : sarif_property_bag &props = result_obj.get_or_create_properties ();
314 : : #define PROPERTY_PREFIX "gcc/analyzer/infinite_loop_diagnostic/"
315 : 0 : props.set (PROPERTY_PREFIX "inf_loop", m_inf_loop->to_json ());
316 : : #undef PROPERTY_PREFIX
317 : 0 : }
318 : :
319 : : private:
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 : :
327 : : static const exploded_edge *
328 : 378967 : get_in_edge_back_edge (const exploded_node &enode)
329 : : {
330 : 1517027 : for (auto in_edge : enode.m_preds)
331 : : {
332 : 391848 : const superedge *sedge = in_edge->m_sedge;
333 : 391848 : if (!sedge)
334 : 271121 : continue;
335 : 120727 : const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
336 : 120727 : if (!cfg_sedge)
337 : 14225 : continue;
338 : 106502 : 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 : :
347 : : class infinite_loop_checking_context : public noop_region_model_context
348 : : {
349 : : public:
350 : 22240 : infinite_loop_checking_context () : m_unusable (false) {}
351 : :
352 : 4974 : bool checking_for_infinite_loop_p () const override { return true; }
353 : 3299 : void on_unusable_in_infinite_loop () override { m_unusable = true; }
354 : :
355 : 22240 : bool unusable_p () const { return m_unusable; }
356 : :
357 : : private:
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 : :
372 : : static std::unique_ptr<infinite_loop>
373 : 378967 : starts_infinite_loop_p (const exploded_node &enode,
374 : : const exploded_graph &eg,
375 : : logger *logger)
376 : : {
377 : 378967 : 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 : 378967 : if (const exploded_edge *back_edge = get_in_edge_back_edge (enode))
381 : : {
382 : 5104 : if (logger)
383 : 9 : logger->log ("got backedge from EN: %i",
384 : 9 : back_edge->m_src->m_index);
385 : : }
386 : : else
387 : : {
388 : 373863 : if (logger)
389 : 106 : logger->log ("rejecting: no backedge in in-edges");
390 : 373863 : return nullptr;
391 : : }
392 : :
393 : : /* Support for dumping an .infinite-loop.dot file visualizing the
394 : : traversal for this enode. */
395 : 5104 : std::unique_ptr<feasible_graph> fg;
396 : 5104 : feasible_node *curr_fnode = nullptr;
397 : :
398 : 5104 : if (flag_dump_analyzer_infinite_loop)
399 : 0 : fg = std::make_unique<feasible_graph> ();
400 : :
401 : 5104 : location_t first_loc = UNKNOWN_LOCATION;
402 : 5104 : const exploded_node *iter = &enode;
403 : 5104 : feasibility_state state (*enode.get_state ().m_region_model,
404 : 5104 : eg.get_supergraph ());
405 : :
406 : 5104 : if (fg)
407 : 0 : curr_fnode = fg->add_node (&enode, state, 0);
408 : :
409 : 5104 : hash_set<const exploded_node *> visited;
410 : 5104 : std::vector<const exploded_edge *> eedges;
411 : 17018 : while (1)
412 : : {
413 : 22122 : if (logger)
414 : 27 : logger->log ("iter: EN: %i", iter->m_index);
415 : : /* Analysis bailed out before processing this node. */
416 : 22122 : if (iter->get_status () == exploded_node::status::worklist)
417 : : {
418 : 5 : if (logger)
419 : 0 : logger->log ("rejecting: EN: %i is still in worklist",
420 : 0 : iter->m_index);
421 : 5104 : return nullptr;
422 : : }
423 : 22117 : if (visited.contains (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 : 272 : if (iter == &enode)
429 : : {
430 : 88 : if (logger)
431 : 0 : logger->log ("accepting: looped back to EN: %i",
432 : 0 : iter->m_index);
433 : 88 : if (fg)
434 : : {
435 : 0 : auto_timevar tv (TV_ANALYZER_DUMP);
436 : 0 : pretty_printer pp;
437 : 0 : pp_printf (&pp, "%s.en%i.infinite-loop.dot",
438 : 0 : dump_base_name, enode.m_index);
439 : 0 : char *filename = xstrdup (pp_formatted_text (&pp));
440 : 0 : feasible_graph::dump_args_t dump_args (eg);
441 : 0 : fg->dump_dot (filename, nullptr, dump_args);
442 : 0 : free (filename);
443 : 0 : }
444 : 88 : return std::make_unique<infinite_loop> (enode,
445 : : first_loc,
446 : : std::move (eedges),
447 : 88 : logger);
448 : : }
449 : : else
450 : : {
451 : 184 : if (logger)
452 : 0 : logger->log ("rejecting: looped back to EN: %i, not to EN: %i",
453 : 0 : iter->m_index, enode.m_index);
454 : 184 : return nullptr;
455 : : }
456 : : }
457 : 21845 : visited.add (iter);
458 : 21845 : if (first_loc == UNKNOWN_LOCATION)
459 : : {
460 : 5140 : location_t enode_loc = iter->get_point ().get_location ();
461 : 5140 : if (enode_loc != UNKNOWN_LOCATION)
462 : 5092 : first_loc = enode_loc;
463 : : }
464 : :
465 : : /* Find the out-edges that are feasible, given the
466 : : constraints here. */
467 : 21845 : typedef std::pair<feasibility_state, const exploded_edge *> pair_t;
468 : 21845 : std::vector<pair_t> succs;
469 : 83668 : for (auto out_edge : iter->m_succs)
470 : : {
471 : 22240 : log_scope s (logger, "considering out-edge",
472 : : "EN:%i -> EN:%i",
473 : 22240 : out_edge->m_src->m_index,
474 : 22240 : out_edge->m_dest->m_index);
475 : 22240 : feasibility_state next_state (state);
476 : :
477 : : /* Use this context to require edge conditions to be known,
478 : : rather than be merely "possible". */
479 : 22240 : infinite_loop_checking_context ctxt;
480 : 22240 : if (next_state.maybe_update_for_edge (logger,
481 : : out_edge,
482 : : &ctxt,
483 : : nullptr))
484 : 18353 : succs.push_back (pair_t (next_state, out_edge));
485 : 22240 : 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 : 3299 : if (logger)
491 : 6 : logger->log ("rejecting: unusable");
492 : 3299 : return nullptr;
493 : : }
494 : 22240 : }
495 : :
496 : 18546 : if (succs.size () != 1)
497 : : {
498 : 555 : if (logger)
499 : 0 : logger->log ("rejecting: %i feasible successors",
500 : 0 : (int)succs.size ());
501 : 555 : return nullptr;
502 : : }
503 : 17991 : const feasibility_state &next_state = succs[0].first;
504 : 17991 : const exploded_edge *out_eedge = succs[0].second;
505 : 17991 : if (out_eedge->could_do_work_p ())
506 : : {
507 : 973 : if (logger)
508 : 3 : logger->log ("rejecting: edge could do work");
509 : 973 : return nullptr;
510 : : }
511 : 17018 : if (fg)
512 : : {
513 : 0 : feasible_node *next_fnode = fg->add_node (out_eedge->m_dest,
514 : : next_state,
515 : 0 : fg->m_nodes.length ());
516 : 0 : fg->add_edge (new feasible_edge (curr_fnode, next_fnode, out_eedge));
517 : 0 : curr_fnode = next_fnode;
518 : : }
519 : 17018 : state = next_state;
520 : 17018 : eedges.push_back (out_eedge);
521 : 17018 : if (first_loc == UNKNOWN_LOCATION)
522 : : {
523 : 36 : if (out_eedge->m_sedge)
524 : 6 : if (::edge cfg_edge = out_eedge->m_sedge->get_any_cfg_edge ())
525 : 6 : if (cfg_edge->goto_locus > BUILTINS_LOCATION)
526 : 0 : first_loc = cfg_edge->goto_locus;
527 : : }
528 : 17018 : iter = out_eedge->m_dest;
529 : 21845 : }
530 : 378967 : }
531 : :
532 : : /* Implementation of -Wanalyzer-infinite-loop. */
533 : :
534 : : void
535 : 3313 : exploded_graph::detect_infinite_loops ()
536 : : {
537 : 3313 : LOG_FUNC (get_logger ());
538 : 3313 : 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 : 3313 : hash_set<const exploded_node *> warned_for;
543 : :
544 : 388960 : for (auto enode : m_nodes)
545 : : {
546 : 379029 : if (get_logger ())
547 : 230 : get_logger ()->log ("visited: %i out of %i",
548 : 115 : (int)warned_for.elements (), m_nodes.length ());
549 : :
550 : : /* Only warn about the first enode we encounter in each cycle. */
551 : 379029 : if (warned_for.contains(enode))
552 : 62 : continue;
553 : :
554 : 378967 : if (std::unique_ptr<infinite_loop> inf_loop
555 : 378967 : = starts_infinite_loop_p (*enode, *this, get_logger ()))
556 : : {
557 : 88 : const supernode *snode = enode->get_supernode ();
558 : :
559 : 88 : if (get_logger ())
560 : 0 : get_logger ()->log ("EN: %i from starts_infinite_loop_p",
561 : 0 : enode->m_index);
562 : :
563 : 622 : for (auto iter : inf_loop->m_eedge_vec)
564 : 534 : warned_for.add (iter->m_src);
565 : 88 : gcc_assert (warned_for.contains(enode));
566 : :
567 : 88 : if (inf_loop->m_loc == UNKNOWN_LOCATION)
568 : : {
569 : 0 : if (get_logger ())
570 : 0 : get_logger ()->log
571 : 0 : ("no location available for reporting infinite loop");
572 : 0 : continue;
573 : : }
574 : :
575 : 88 : pending_location ploc (enode, snode, inf_loop->m_loc);
576 : 88 : auto d
577 : 88 : = std::make_unique<infinite_loop_diagnostic> (std::move (inf_loop));
578 : 88 : get_diagnostic_manager ().add_diagnostic (ploc, std::move (d));
579 : 379055 : }
580 : : }
581 : 3313 : }
|
