]>
Commit | Line | Data |
---|---|---|
841008d3 | 1 | /* Detection of infinite loops. |
a945c346 | 2 | Copyright (C) 2022-2024 Free Software Foundation, Inc. |
841008d3 DM |
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" | |
841008d3 DM |
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 | ||
67 | /* A bundle of data characterizing a particular infinite loop | |
68 | identified within the exploded graph. */ | |
69 | ||
70 | struct infinite_loop | |
71 | { | |
72 | infinite_loop (const exploded_node &enode, | |
73 | location_t loc, | |
8cf5afba | 74 | std::vector<const exploded_edge *> &&eedges, |
841008d3 DM |
75 | logger *logger) |
76 | : m_enode (enode), | |
77 | m_loc (loc), | |
78 | m_eedge_vec (eedges) | |
79 | { | |
80 | LOG_SCOPE (logger); | |
81 | if (logger) | |
82 | { | |
83 | logger->start_log_line (); | |
84 | logger->log_partial ("infinite loop: EN: %i", m_enode.m_index); | |
85 | for (auto eedge : m_eedge_vec) | |
86 | { | |
87 | logger->log_partial (" ->"); | |
88 | if (const superedge *sedge = eedge->m_sedge) | |
89 | { | |
90 | sedge->dump_label_to_pp (logger->get_printer (), false); | |
91 | } | |
92 | logger->log_partial (" EN: %i", eedge->m_dest->m_index); | |
93 | } | |
94 | logger->end_log_line (); | |
95 | } | |
96 | } | |
97 | ||
98 | bool | |
99 | operator== (const infinite_loop &other) const | |
100 | { | |
101 | /* Compare underlying supernode, rather than enodes, so that | |
102 | we don't get duplicates in functions that are called from | |
103 | elsewhere. */ | |
104 | return (m_enode.get_supernode () == other.m_enode.get_supernode () | |
105 | && m_loc == other.m_loc); | |
106 | } | |
107 | ||
108 | const exploded_node &m_enode; | |
109 | location_t m_loc; | |
110 | std::vector<const exploded_edge *> m_eedge_vec; | |
111 | }; | |
112 | ||
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. */ | |
116 | ||
117 | class perpetual_start_cfg_edge_event : public start_cfg_edge_event | |
118 | { | |
119 | public: | |
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) | |
123 | { | |
124 | } | |
125 | ||
126 | label_text get_desc (bool can_colorize) const final override | |
127 | { | |
128 | bool user_facing = !flag_analyzer_verbose_edges; | |
129 | label_text edge_desc (m_sedge->get_description (user_facing)); | |
130 | if (user_facing) | |
131 | { | |
132 | if (edge_desc.get () && strlen (edge_desc.get ()) > 0) | |
133 | { | |
134 | label_text cond_desc = maybe_describe_condition (can_colorize); | |
135 | label_text result; | |
136 | if (cond_desc.get ()) | |
137 | return make_label_text | |
138 | (can_colorize, | |
139 | "%s: always following %qs branch...", | |
140 | cond_desc.get (), edge_desc.get ()); | |
141 | else | |
142 | return make_label_text | |
143 | (can_colorize, | |
144 | "if it ever follows %qs branch, it will always do so...", | |
145 | edge_desc.get ()); | |
146 | } | |
147 | } | |
148 | return start_cfg_edge_event::get_desc (can_colorize); | |
149 | } | |
150 | }; | |
151 | ||
152 | /* A subclass of pending_diagnostic for complaining about suspected | |
153 | infinite loops. */ | |
154 | ||
155 | class infinite_loop_diagnostic | |
156 | : public pending_diagnostic_subclass<infinite_loop_diagnostic> | |
157 | { | |
158 | public: | |
159 | infinite_loop_diagnostic (std::unique_ptr<infinite_loop> inf_loop) | |
160 | : m_inf_loop (std::move (inf_loop)) | |
161 | { | |
162 | gcc_assert (m_inf_loop != nullptr); | |
163 | } | |
164 | ||
165 | const char *get_kind () const final override | |
166 | { | |
167 | return "infinite_loop_diagnostic"; | |
168 | } | |
169 | ||
170 | bool operator== (const infinite_loop_diagnostic &other) const | |
171 | { | |
172 | return *m_inf_loop == *other.m_inf_loop; | |
173 | } | |
174 | ||
175 | int get_controlling_option () const final override | |
176 | { | |
177 | return OPT_Wanalyzer_infinite_loop; | |
178 | } | |
179 | ||
12b67d1e | 180 | bool emit (diagnostic_emission_context &ctxt) final override |
841008d3 DM |
181 | { |
182 | /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */ | |
12b67d1e DM |
183 | ctxt.add_cwe (835); |
184 | return ctxt.warn ("infinite loop"); | |
841008d3 DM |
185 | } |
186 | ||
187 | bool maybe_add_custom_events_for_superedge (const exploded_edge &, | |
188 | checker_path *) | |
189 | final override | |
190 | { | |
191 | /* Don't add any regular events; instead we add them after pruning as | |
192 | part of the "final" warning. */ | |
193 | return true; | |
194 | } | |
195 | ||
196 | label_text describe_final_event (const evdesc::final_event &ev) final override | |
197 | { | |
198 | return ev.formatted_print ("infinite loop here"); | |
199 | } | |
200 | ||
201 | /* Customize the location where the warning_event appears. */ | |
202 | void add_final_event (const state_machine *, | |
203 | const exploded_node *enode, | |
204 | const gimple *, | |
205 | tree, | |
206 | state_machine::state_t, | |
207 | checker_path *emission_path) final override | |
208 | { | |
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 ()), | |
214 | enode, | |
215 | NULL, NULL, NULL)); | |
216 | ||
217 | logger *logger = emission_path->get_logger (); | |
218 | ||
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) | |
222 | { | |
223 | if (logger) | |
224 | logger->log ("EN: %i -> EN: %i", | |
225 | eedge->m_src->m_index, | |
226 | eedge->m_dest->m_index); | |
227 | if (!eedge->m_sedge) | |
228 | continue; | |
229 | ||
230 | const cfg_superedge *cfg_sedge | |
231 | = eedge->m_sedge->dyn_cast_cfg_superedge (); | |
232 | if (!cfg_sedge) | |
233 | continue; | |
234 | ||
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 (); | |
242 | ||
243 | event_loc_info loc_info_from | |
244 | (last_stmt ? last_stmt->location : cfg_sedge->get_goto_locus (), | |
245 | src_point.get_fndecl (), | |
246 | src_stack_depth); | |
247 | event_loc_info loc_info_to | |
248 | (dst_point.get_supernode ()->get_start_location (), | |
249 | dst_point.get_fndecl (), | |
250 | dst_stack_depth); | |
251 | ||
252 | if (const switch_cfg_superedge *switch_cfg_sedge | |
253 | = cfg_sedge->dyn_cast_switch_cfg_superedge ()) | |
254 | { | |
255 | if (switch_cfg_sedge->implicitly_created_default_p ()) | |
256 | { | |
257 | emission_path->add_event | |
258 | (make_unique<perpetual_start_cfg_edge_event> (*eedge, | |
259 | loc_info_from)); | |
260 | emission_path->add_event | |
261 | (make_unique<end_cfg_edge_event> | |
262 | (*eedge, | |
263 | loc_info_to)); | |
264 | } | |
265 | } | |
266 | ||
267 | if (cfg_sedge->true_value_p ()) | |
268 | { | |
269 | emission_path->add_event | |
270 | (make_unique<perpetual_start_cfg_edge_event> (*eedge, | |
271 | loc_info_from)); | |
272 | emission_path->add_event | |
273 | (make_unique<end_cfg_edge_event> | |
274 | (*eedge, | |
275 | loc_info_to)); | |
276 | } | |
277 | else if (cfg_sedge->false_value_p ()) | |
278 | { | |
279 | emission_path->add_event | |
280 | (make_unique<perpetual_start_cfg_edge_event> (*eedge, | |
281 | loc_info_from)); | |
282 | emission_path->add_event | |
283 | (make_unique<end_cfg_edge_event> | |
284 | (*eedge, | |
285 | loc_info_to)); | |
286 | } | |
287 | else if (cfg_sedge->back_edge_p ()) | |
288 | { | |
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> | |
294 | (*eedge, | |
295 | loc_info_to)); | |
296 | } | |
297 | } | |
298 | } | |
299 | ||
300 | private: | |
301 | std::unique_ptr<infinite_loop> m_inf_loop; | |
302 | }; | |
303 | ||
304 | /* If ENODE has an in-edge corresponding to a CFG backedge, return that | |
305 | exploded in-edge. | |
306 | Otherwise, return nullptr. */ | |
307 | ||
308 | static const exploded_edge * | |
309 | get_in_edge_back_edge (const exploded_node &enode) | |
310 | { | |
311 | for (auto in_edge : enode.m_preds) | |
312 | { | |
313 | const superedge *sedge = in_edge->m_sedge; | |
314 | if (!sedge) | |
315 | continue; | |
316 | const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge (); | |
317 | if (!cfg_sedge) | |
318 | continue; | |
319 | if (cfg_sedge->back_edge_p ()) | |
320 | return in_edge; | |
321 | } | |
322 | return nullptr; | |
323 | } | |
324 | ||
325 | /* Subclass of region_model_context that rejects conditional branches that | |
326 | aren't known for definite. */ | |
327 | ||
328 | class infinite_loop_checking_context : public noop_region_model_context | |
329 | { | |
330 | public: | |
331 | infinite_loop_checking_context () : m_unusable (false) {} | |
332 | ||
333 | bool checking_for_infinite_loop_p () const override { return true; } | |
334 | void on_unusable_in_infinite_loop () override { m_unusable = true; } | |
335 | ||
336 | bool unusable_p () const { return m_unusable; } | |
337 | ||
338 | private: | |
339 | bool m_unusable; | |
340 | }; | |
341 | ||
342 | /* Determine if an infinite loop starts at ENODE. | |
343 | Return the loop if it is found, nullptr otherwise. | |
344 | ||
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. */ | |
352 | ||
353 | static std::unique_ptr<infinite_loop> | |
354 | starts_infinite_loop_p (const exploded_node &enode, | |
355 | const exploded_graph &eg, | |
356 | logger *logger) | |
357 | { | |
358 | LOG_FUNC_1 (logger, "considering EN: %i", enode.m_index); | |
359 | ||
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)) | |
362 | { | |
363 | if (logger) | |
364 | logger->log ("got backedge from EN: %i", | |
365 | back_edge->m_src->m_index); | |
366 | } | |
367 | else | |
368 | { | |
369 | if (logger) | |
370 | logger->log ("rejecting: no backedge in in-edges"); | |
371 | return nullptr; | |
372 | } | |
373 | ||
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; | |
378 | ||
379 | if (flag_dump_analyzer_infinite_loop) | |
380 | fg = ::make_unique<feasible_graph> (); | |
381 | ||
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 ()); | |
386 | ||
387 | if (fg) | |
388 | curr_fnode = fg->add_node (&enode, state, 0); | |
389 | ||
390 | hash_set<const exploded_node *> visited; | |
391 | std::vector<const exploded_edge *> eedges; | |
392 | while (1) | |
393 | { | |
394 | if (logger) | |
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) | |
398 | { | |
399 | if (logger) | |
400 | logger->log ("rejecting: EN: %i is still in worklist", | |
401 | iter->m_index); | |
402 | return nullptr; | |
403 | } | |
404 | if (visited.contains (iter)) | |
405 | { | |
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. */ | |
409 | if (iter == &enode) | |
410 | { | |
411 | if (logger) | |
412 | logger->log ("accepting: looped back to EN: %i", | |
413 | iter->m_index); | |
414 | if (fg) | |
415 | { | |
416 | auto_timevar tv (TV_ANALYZER_DUMP); | |
417 | pretty_printer pp; | |
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); | |
423 | free (filename); | |
424 | } | |
425 | return ::make_unique<infinite_loop> (enode, | |
8cf5afba DM |
426 | first_loc, |
427 | std::move (eedges), | |
428 | logger); | |
841008d3 DM |
429 | } |
430 | else | |
431 | { | |
432 | if (logger) | |
433 | logger->log ("rejecting: looped back to EN: %i, not to EN: %i", | |
434 | iter->m_index, enode.m_index); | |
435 | return nullptr; | |
436 | } | |
437 | } | |
438 | visited.add (iter); | |
439 | if (first_loc == UNKNOWN_LOCATION) | |
440 | { | |
441 | location_t enode_loc = iter->get_point ().get_location (); | |
442 | if (enode_loc != UNKNOWN_LOCATION) | |
443 | first_loc = enode_loc; | |
444 | } | |
445 | ||
446 | /* Find the out-edges that are feasible, given the | |
447 | constraints here. */ | |
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) | |
451 | { | |
452 | log_scope s (logger, "considering out-edge", | |
453 | "EN:%i -> EN:%i", | |
454 | out_edge->m_src->m_index, | |
455 | out_edge->m_dest->m_index); | |
456 | feasibility_state next_state (state); | |
457 | ||
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, | |
462 | out_edge, | |
463 | &ctxt, | |
464 | nullptr)) | |
465 | succs.push_back (pair_t (next_state, out_edge)); | |
466 | if (ctxt.unusable_p ()) | |
467 | { | |
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. */ | |
471 | if (logger) | |
472 | logger->log ("rejecting: unusable"); | |
473 | return nullptr; | |
474 | } | |
475 | } | |
476 | ||
477 | if (succs.size () != 1) | |
478 | { | |
479 | if (logger) | |
480 | logger->log ("rejecting: %i feasible successors", | |
481 | (int)succs.size ()); | |
482 | return nullptr; | |
483 | } | |
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 ()) | |
487 | { | |
488 | if (logger) | |
489 | logger->log ("rejecting: edge could do work"); | |
490 | return nullptr; | |
491 | } | |
492 | if (fg) | |
493 | { | |
494 | feasible_node *next_fnode = fg->add_node (out_eedge->m_dest, | |
495 | next_state, | |
496 | fg->m_nodes.length ()); | |
497 | fg->add_edge (new feasible_edge (curr_fnode, next_fnode, out_eedge)); | |
498 | curr_fnode = next_fnode; | |
499 | } | |
500 | state = next_state; | |
501 | eedges.push_back (out_eedge); | |
502 | if (first_loc == UNKNOWN_LOCATION) | |
503 | { | |
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; | |
508 | } | |
509 | iter = out_eedge->m_dest; | |
510 | } | |
511 | } | |
512 | ||
513 | /* Implementation of -Wanalyzer-infinite-loop. */ | |
514 | ||
515 | void | |
516 | exploded_graph::detect_infinite_loops () | |
517 | { | |
518 | LOG_FUNC (get_logger ()); | |
519 | auto_timevar tv (TV_ANALYZER_INFINITE_LOOPS); | |
520 | ||
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; | |
524 | ||
525 | for (auto enode : m_nodes) | |
526 | { | |
527 | if (get_logger ()) | |
528 | get_logger ()->log ("visited: %i out of %i", | |
529 | (int)warned_for.elements (), m_nodes.length ()); | |
530 | ||
531 | /* Only warn about the first enode we encounter in each cycle. */ | |
532 | if (warned_for.contains(enode)) | |
533 | continue; | |
534 | ||
535 | if (std::unique_ptr<infinite_loop> inf_loop | |
536 | = starts_infinite_loop_p (*enode, *this, get_logger ())) | |
537 | { | |
538 | const supernode *snode = enode->get_supernode (); | |
539 | ||
540 | if (get_logger ()) | |
541 | get_logger ()->log ("EN: %i from starts_infinite_loop_p", | |
542 | enode->m_index); | |
543 | ||
544 | for (auto iter : inf_loop->m_eedge_vec) | |
545 | warned_for.add (iter->m_src); | |
546 | gcc_assert (warned_for.contains(enode)); | |
547 | ||
548 | if (inf_loop->m_loc == UNKNOWN_LOCATION) | |
549 | { | |
550 | if (get_logger ()) | |
551 | get_logger ()->log | |
552 | ("no location available for reporting infinite loop"); | |
553 | continue; | |
554 | } | |
555 | ||
556 | pending_location ploc (enode, snode, inf_loop->m_loc); | |
557 | auto d | |
558 | = ::make_unique<infinite_loop_diagnostic> (std::move (inf_loop)); | |
559 | get_diagnostic_manager ().add_diagnostic (ploc, std::move (d)); | |
560 | } | |
561 | } | |
562 | } |