1 /* Detection of infinite loops.
2 Copyright (C) 2022-2023 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
22 #define INCLUDE_MEMORY
23 #define INCLUDE_VECTOR
25 #include "coretypes.h"
27 #include "fold-const.h"
28 #include "gcc-rich-location.h"
29 #include "alloc-pool.h"
30 #include "fibonacci_heap.h"
31 #include "shortest-paths.h"
32 #include "diagnostic-core.h"
33 #include "diagnostic-event-id.h"
34 #include "diagnostic-path.h"
36 #include "pretty-print.h"
40 #include "ordered-hash-map.h"
43 #include "analyzer/analyzer.h"
44 #include "analyzer/analyzer-logging.h"
45 #include "analyzer/call-string.h"
46 #include "analyzer/program-point.h"
47 #include "analyzer/store.h"
48 #include "analyzer/region-model.h"
49 #include "analyzer/constraint-manager.h"
50 #include "analyzer/sm.h"
51 #include "analyzer/pending-diagnostic.h"
52 #include "analyzer/diagnostic-manager.h"
54 #include "basic-block.h"
56 #include "gimple-iterator.h"
57 #include "gimple-pretty-print.h"
60 #include "analyzer/supergraph.h"
61 #include "analyzer/program-state.h"
62 #include "analyzer/exploded-graph.h"
63 #include "analyzer/checker-path.h"
64 #include "analyzer/feasible-graph.h"
65 #include "make-unique.h"
67 /* A bundle of data characterizing a particular infinite loop
68 identified within the exploded graph. */
72 infinite_loop (const exploded_node
&enode
,
74 std::vector
<const exploded_edge
*> &&eedges
,
83 logger
->start_log_line ();
84 logger
->log_partial ("infinite loop: EN: %i", m_enode
.m_index
);
85 for (auto eedge
: m_eedge_vec
)
87 logger
->log_partial (" ->");
88 if (const superedge
*sedge
= eedge
->m_sedge
)
90 sedge
->dump_label_to_pp (logger
->get_printer (), false);
92 logger
->log_partial (" EN: %i", eedge
->m_dest
->m_index
);
94 logger
->end_log_line ();
99 operator== (const infinite_loop
&other
) const
101 /* Compare underlying supernode, rather than enodes, so that
102 we don't get duplicates in functions that are called from
104 return (m_enode
.get_supernode () == other
.m_enode
.get_supernode ()
105 && m_loc
== other
.m_loc
);
108 const exploded_node
&m_enode
;
110 std::vector
<const exploded_edge
*> m_eedge_vec
;
113 /* A custom subclass of start_cfg_edge_event that rewords the
114 message to indicate that the CFG edge is *always* taken on
115 subsequent iterations, assuming it's been taken once. */
117 class perpetual_start_cfg_edge_event
: public start_cfg_edge_event
120 perpetual_start_cfg_edge_event (const exploded_edge
&eedge
,
121 const event_loc_info
&loc_info
)
122 : start_cfg_edge_event (eedge
, loc_info
)
126 label_text
get_desc (bool can_colorize
) const final override
128 bool user_facing
= !flag_analyzer_verbose_edges
;
129 label_text
edge_desc (m_sedge
->get_description (user_facing
));
132 if (edge_desc
.get () && strlen (edge_desc
.get ()) > 0)
134 label_text cond_desc
= maybe_describe_condition (can_colorize
);
136 if (cond_desc
.get ())
137 return make_label_text
139 "%s: always following %qs branch...",
140 cond_desc
.get (), edge_desc
.get ());
142 return make_label_text
144 "if it ever follows %qs branch, it will always do so...",
148 return start_cfg_edge_event::get_desc (can_colorize
);
152 /* A subclass of pending_diagnostic for complaining about suspected
155 class infinite_loop_diagnostic
156 : public pending_diagnostic_subclass
<infinite_loop_diagnostic
>
159 infinite_loop_diagnostic (std::unique_ptr
<infinite_loop
> inf_loop
)
160 : m_inf_loop (std::move (inf_loop
))
162 gcc_assert (m_inf_loop
!= nullptr);
165 const char *get_kind () const final override
167 return "infinite_loop_diagnostic";
170 bool operator== (const infinite_loop_diagnostic
&other
) const
172 return *m_inf_loop
== *other
.m_inf_loop
;
175 int get_controlling_option () const final override
177 return OPT_Wanalyzer_infinite_loop
;
180 bool emit (diagnostic_emission_context
&ctxt
) final override
182 /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */
184 return ctxt
.warn ("infinite loop");
187 bool maybe_add_custom_events_for_superedge (const exploded_edge
&,
191 /* Don't add any regular events; instead we add them after pruning as
192 part of the "final" warning. */
196 label_text
describe_final_event (const evdesc::final_event
&ev
) final override
198 return ev
.formatted_print ("infinite loop here");
201 /* Customize the location where the warning_event appears. */
202 void add_final_event (const state_machine
*,
203 const exploded_node
*enode
,
206 state_machine::state_t
,
207 checker_path
*emission_path
) final override
209 emission_path
->add_event
210 (make_unique
<warning_event
>
211 (event_loc_info (m_inf_loop
->m_loc
,
212 enode
->get_function ()->decl
,
213 enode
->get_stack_depth ()),
217 logger
*logger
= emission_path
->get_logger ();
219 /* EMISSION_PATH has the path to the entry of the infinite loop.
220 Add extra edges showing the loop itself. */
221 for (auto eedge
: m_inf_loop
->m_eedge_vec
)
224 logger
->log ("EN: %i -> EN: %i",
225 eedge
->m_src
->m_index
,
226 eedge
->m_dest
->m_index
);
230 const cfg_superedge
*cfg_sedge
231 = eedge
->m_sedge
->dyn_cast_cfg_superedge ();
235 const exploded_node
*src_node
= eedge
->m_src
;
236 const program_point
&src_point
= src_node
->get_point ();
237 const exploded_node
*dst_node
= eedge
->m_dest
;
238 const program_point
&dst_point
= dst_node
->get_point ();
239 const int src_stack_depth
= src_point
.get_stack_depth ();
240 const int dst_stack_depth
= dst_point
.get_stack_depth ();
241 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
243 event_loc_info loc_info_from
244 (last_stmt
? last_stmt
->location
: cfg_sedge
->get_goto_locus (),
245 src_point
.get_fndecl (),
247 event_loc_info loc_info_to
248 (dst_point
.get_supernode ()->get_start_location (),
249 dst_point
.get_fndecl (),
252 if (const switch_cfg_superedge
*switch_cfg_sedge
253 = cfg_sedge
->dyn_cast_switch_cfg_superedge ())
255 if (switch_cfg_sedge
->implicitly_created_default_p ())
257 emission_path
->add_event
258 (make_unique
<perpetual_start_cfg_edge_event
> (*eedge
,
260 emission_path
->add_event
261 (make_unique
<end_cfg_edge_event
>
267 if (cfg_sedge
->true_value_p ())
269 emission_path
->add_event
270 (make_unique
<perpetual_start_cfg_edge_event
> (*eedge
,
272 emission_path
->add_event
273 (make_unique
<end_cfg_edge_event
>
277 else if (cfg_sedge
->false_value_p ())
279 emission_path
->add_event
280 (make_unique
<perpetual_start_cfg_edge_event
> (*eedge
,
282 emission_path
->add_event
283 (make_unique
<end_cfg_edge_event
>
287 else if (cfg_sedge
->back_edge_p ())
289 emission_path
->add_event
290 (make_unique
<precanned_custom_event
>
291 (loc_info_from
, "looping back..."));
292 emission_path
->add_event
293 (make_unique
<end_cfg_edge_event
>
301 std::unique_ptr
<infinite_loop
> m_inf_loop
;
304 /* If ENODE has an in-edge corresponding to a CFG backedge, return that
306 Otherwise, return nullptr. */
308 static const exploded_edge
*
309 get_in_edge_back_edge (const exploded_node
&enode
)
311 for (auto in_edge
: enode
.m_preds
)
313 const superedge
*sedge
= in_edge
->m_sedge
;
316 const cfg_superedge
*cfg_sedge
= sedge
->dyn_cast_cfg_superedge ();
319 if (cfg_sedge
->back_edge_p ())
325 /* Subclass of region_model_context that rejects conditional branches that
326 aren't known for definite. */
328 class infinite_loop_checking_context
: public noop_region_model_context
331 infinite_loop_checking_context () : m_unusable (false) {}
333 bool checking_for_infinite_loop_p () const override
{ return true; }
334 void on_unusable_in_infinite_loop () override
{ m_unusable
= true; }
336 bool unusable_p () const { return m_unusable
; }
342 /* Determine if an infinite loop starts at ENODE.
343 Return the loop if it is found, nullptr otherwise.
345 Look for cycles in the exploded graph in which:
346 - no externally visible work occurs
347 - no escape from the cycle
348 - the program state is "sufficiently concrete" at each step:
349 - no unknown activity could be occurring
350 - the worklist was fully drained for each enode in the cycle
351 i.e. every enode in the cycle is processed. */
353 static std::unique_ptr
<infinite_loop
>
354 starts_infinite_loop_p (const exploded_node
&enode
,
355 const exploded_graph
&eg
,
358 LOG_FUNC_1 (logger
, "considering EN: %i", enode
.m_index
);
360 /* Only consider enodes that have a CFG back edge as an in-edge. */
361 if (const exploded_edge
*back_edge
= get_in_edge_back_edge (enode
))
364 logger
->log ("got backedge from EN: %i",
365 back_edge
->m_src
->m_index
);
370 logger
->log ("rejecting: no backedge in in-edges");
374 /* Support for dumping an .infinite-loop.dot file visualizing the
375 traversal for this enode. */
376 std::unique_ptr
<feasible_graph
> fg
;
377 feasible_node
*curr_fnode
= nullptr;
379 if (flag_dump_analyzer_infinite_loop
)
380 fg
= ::make_unique
<feasible_graph
> ();
382 location_t first_loc
= UNKNOWN_LOCATION
;
383 const exploded_node
*iter
= &enode
;
384 feasibility_state
state (*enode
.get_state ().m_region_model
,
385 eg
.get_supergraph ());
388 curr_fnode
= fg
->add_node (&enode
, state
, 0);
390 hash_set
<const exploded_node
*> visited
;
391 std::vector
<const exploded_edge
*> eedges
;
395 logger
->log ("iter: EN: %i", iter
->m_index
);
396 /* Analysis bailed out before processing this node. */
397 if (iter
->get_status () == exploded_node::STATUS_WORKLIST
)
400 logger
->log ("rejecting: EN: %i is still in worklist",
404 if (visited
.contains (iter
))
406 /* We've looped back on ourselves. ENODE is in the loop
407 itself if ENODE is the first place we looped back,
408 as opposed to being on a path to a loop. */
412 logger
->log ("accepting: looped back to EN: %i",
416 auto_timevar
tv (TV_ANALYZER_DUMP
);
418 pp_printf (&pp
, "%s.en%i.infinite-loop.dot",
419 dump_base_name
, enode
.m_index
);
420 char *filename
= xstrdup (pp_formatted_text (&pp
));
421 feasible_graph::dump_args_t
dump_args (eg
);
422 fg
->dump_dot (filename
, nullptr, dump_args
);
425 return ::make_unique
<infinite_loop
> (enode
,
433 logger
->log ("rejecting: looped back to EN: %i, not to EN: %i",
434 iter
->m_index
, enode
.m_index
);
439 if (first_loc
== UNKNOWN_LOCATION
)
441 location_t enode_loc
= iter
->get_point ().get_location ();
442 if (enode_loc
!= UNKNOWN_LOCATION
)
443 first_loc
= enode_loc
;
446 /* Find the out-edges that are feasible, given the
448 typedef std::pair
<feasibility_state
, const exploded_edge
*> pair_t
;
449 std::vector
<pair_t
> succs
;
450 for (auto out_edge
: iter
->m_succs
)
452 log_scope
s (logger
, "considering out-edge",
454 out_edge
->m_src
->m_index
,
455 out_edge
->m_dest
->m_index
);
456 feasibility_state
next_state (state
);
458 /* Use this context to require edge conditions to be known,
459 rather than be merely "possible". */
460 infinite_loop_checking_context ctxt
;
461 if (next_state
.maybe_update_for_edge (logger
,
465 succs
.push_back (pair_t (next_state
, out_edge
));
466 if (ctxt
.unusable_p ())
468 /* If we get here, then we have e.g. a gcond where
469 the condition is UNKNOWN, or a condition
470 based on a widening_svalue. Reject such paths. */
472 logger
->log ("rejecting: unusable");
477 if (succs
.size () != 1)
480 logger
->log ("rejecting: %i feasible successors",
484 const feasibility_state
&next_state
= succs
[0].first
;
485 const exploded_edge
*out_eedge
= succs
[0].second
;
486 if (out_eedge
->could_do_work_p ())
489 logger
->log ("rejecting: edge could do work");
494 feasible_node
*next_fnode
= fg
->add_node (out_eedge
->m_dest
,
496 fg
->m_nodes
.length ());
497 fg
->add_edge (new feasible_edge (curr_fnode
, next_fnode
, out_eedge
));
498 curr_fnode
= next_fnode
;
501 eedges
.push_back (out_eedge
);
502 if (first_loc
== UNKNOWN_LOCATION
)
504 if (out_eedge
->m_sedge
)
505 if (::edge cfg_edge
= out_eedge
->m_sedge
->get_any_cfg_edge ())
506 if (cfg_edge
->goto_locus
> BUILTINS_LOCATION
)
507 first_loc
= cfg_edge
->goto_locus
;
509 iter
= out_eedge
->m_dest
;
513 /* Implementation of -Wanalyzer-infinite-loop. */
516 exploded_graph::detect_infinite_loops ()
518 LOG_FUNC (get_logger ());
519 auto_timevar
tv (TV_ANALYZER_INFINITE_LOOPS
);
521 /* Track all enodes we've warned for; both the loop entrypoints
522 and all the enodes within those loops. */
523 hash_set
<const exploded_node
*> warned_for
;
525 for (auto enode
: m_nodes
)
528 get_logger ()->log ("visited: %i out of %i",
529 (int)warned_for
.elements (), m_nodes
.length ());
531 /* Only warn about the first enode we encounter in each cycle. */
532 if (warned_for
.contains(enode
))
535 if (std::unique_ptr
<infinite_loop
> inf_loop
536 = starts_infinite_loop_p (*enode
, *this, get_logger ()))
538 const supernode
*snode
= enode
->get_supernode ();
541 get_logger ()->log ("EN: %i from starts_infinite_loop_p",
544 for (auto iter
: inf_loop
->m_eedge_vec
)
545 warned_for
.add (iter
->m_src
);
546 gcc_assert (warned_for
.contains(enode
));
548 if (inf_loop
->m_loc
== UNKNOWN_LOCATION
)
552 ("no location available for reporting infinite loop");
556 pending_location
ploc (enode
, snode
, inf_loop
->m_loc
);
558 = ::make_unique
<infinite_loop_diagnostic
> (std::move (inf_loop
));
559 get_diagnostic_manager ().add_diagnostic (ploc
, std::move (d
));