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