public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "cvs-commit at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion Date: Sat, 18 Nov 2023 00:59:18 +0000 [thread overview] Message-ID: <bug-106147-4-8mr12yutM2@http.gcc.gnu.org/bugzilla/> (raw) In-Reply-To: <bug-106147-4@http.gcc.gnu.org/bugzilla/> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106147 --- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by David Malcolm <dmalcolm@gcc.gnu.org>: https://gcc.gnu.org/g:841008d3966c0fe7a80ec10703a50fbdab7620ac commit r14-5566-g841008d3966c0fe7a80ec10703a50fbdab7620ac Author: David Malcolm <dmalcolm@redhat.com> Date: Fri Nov 17 19:55:25 2023 -0500 analyzer: new warning: -Wanalyzer-infinite-loop [PR106147] This patch implements a new analyzer warning: -Wanalyzer-infinite-loop. It works by examining the exploded graph once the latter has been fully built. It attempts to detect cycles in the exploded graph in which: - no externally visible work occurs - no escape is possible from the cycle once it has been entered - the program state is "sufficiently concrete" at each step: - no unknown activity could be occurring - the worklist was fully drained for each enode in the cycle i.e. every enode in the cycle is processed For example, it correctly complains about this bogus "for" loop: int sum = 0; for (struct node *iter = n; iter; iter->next) sum += n->val; return sum; like this: infinite-loop-linked-list.c: In function âfor_loop_noop_nextâ: infinite-loop-linked-list.c:110:31: warning: infinite loop [CWE-835] [-Wanalyzer-infinite-loop] 110 | for (struct node *iter = n; iter; iter->next) | ^~~~ âfor_loop_noop_nextâ: events 1-5 | | 110 | for (struct node *iter = n; iter; iter->next) | | ^~~~ | | | | | (1) infinite loop here | | (2) when âiterâ is non-NULL: always following âtrueâ branch... | | (5) ...to here | 111 | sum += n->val; | | ~~~~~~~~~~~~~ | | | | | | | (3) ...to here | | (4) looping back... | gcc/ChangeLog: PR analyzer/106147 * Makefile.in (ANALYZER_OBJS): Add analyzer/infinite-loop.o. * doc/invoke.texi: Add -fdump-analyzer-infinite-loop and -Wanalyzer-infinite-loop. Add missing CWE link for -Wanalyzer-infinite-recursion. * timevar.def (TV_ANALYZER_INFINITE_LOOPS): New. gcc/analyzer/ChangeLog: PR analyzer/106147 * analyzer.opt (Wanalyzer-infinite-loop): New option. (fdump-analyzer-infinite-loop): New option. * checker-event.h (start_cfg_edge_event::get_desc): Drop "final". (start_cfg_edge_event::maybe_describe_condition): Convert from private to protected. * checker-path.h (checker_path::get_logger): New. * diagnostic-manager.cc (process_worklist_item): Update for new context param of maybe_update_for_edge. * engine.cc (impl_region_model_context::impl_region_model_context): Add out_could_have_done_work param to both ctors and use it to initialize mm_out_could_have_done_work. (impl_region_model_context::maybe_did_work): New vfunc implementation. (exploded_node::on_stmt): Add out_could_have_done_work param and pass to ctxt ctor. (exploded_node::on_stmt_pre): Treat setjmp and longjmp as "doing work". (exploded_node::on_longjmp): Likewise. (exploded_edge::exploded_edge): Add "could_do_work" param and use it to initialize m_could_do_work_p. (exploded_edge::dump_dot_label): Add result of could_do_work_p. (exploded_graph::add_function_entry): Mark edge as doing no work. (exploded_graph::add_edge): Add "could_do_work" param and pass to exploded_edge ctor. (add_tainted_args_callback): Treat as doing no work. (exploded_graph::process_worklist): Likewise when merging nodes. (maybe_process_run_of_before_supernode_enodes::item): Likewise. (exploded_graph::maybe_create_dynamic_call): Likewise. (exploded_graph::process_node): Likewise for phi nodes. Pass in a "could_have_done_work" bool when handling stmts and use when creating edges. Assume work is done at bifurcation. (exploded_path::feasible_p): Update for new context param of maybe_update_for_edge. (feasibility_state::feasibility_state): New ctor. (feasibility_state::operator=): New. (feasibility_state::maybe_update_for_edge): Add ctxt param and use it. Fix missing newline when logging state. (impl_run_checkers): Call exploded_graph::detect_infinite_loops. * exploded-graph.h (impl_region_model_context::impl_region_model_context): Add out_could_have_done_work param to both ctors. (impl_region_model_context::maybe_did_work): New decl. (impl_region_model_context::checking_for_infinite_loop_p): New. (impl_region_model_context::on_unusable_in_infinite_loop): New. (impl_region_model_context::m_out_could_have_done_work): New field. (exploded_node::on_stmt): Add "out_could_have_done_work" param. (exploded_edge::exploded_edge): Add "could_do_work" param. (exploded_edge::could_do_work_p): New accessor. (exploded_edge::m_could_do_work_p): New field. (exploded_graph::add_edge): Add "could_do_work" param. (exploded_graph::detect_infinite_loops): New decl. (feasibility_state::feasibility_state): New ctor. (feasibility_state::operator=): New decl. (feasibility_state::maybe_update_for_edge): Add ctxt param. * infinite-loop.cc: New file. * program-state.cc (program_state::on_edge): Log the rejected constraint when region_model::maybe_update_for_edge fails. * region-model.cc (region_model::on_assignment): Treat any writes other than to the stack as "doing work". (region_model::on_stmt_pre): Treat all asm stmts as "doing work". (region_model::on_call_post): Likewise for all calls to functions with unknown side effects. (region_model::handle_phi): Add svals_changing_meaning param. Mark widening svalue in phi nodes as changing meaning. (unusable_in_infinite_loop_constraint_p): New. (region_model::add_constraint): If we're checking for an infinite loop, bail out on unusable svalues, or if we don't have a definite true/false for the constraint. (region_model::update_for_phis): Gather all svalues changing meaning in phi nodes, and purge constraints involving them. (region_model::replay_call_summary): Treat all call summaries as doing work. (region_model::can_merge_with_p): Purge constraints involving svalues that change meaning. (model_merger::on_widening_reuse): New. (test_iteration_1): Likewise. (selftest::test_iteration_1): Remove assertion that model6 "knows" that i < 157. * region-model.h (region_model::handle_phi): Add svals_changing_meaning param (region_model_context::maybe_did_work): New pure virtual func. (region_model_context::checking_for_infinite_loop_p): Likewise. (region_model_context::on_unusable_in_infinite_loop): Likewise. (noop_region_model_context::maybe_did_work): Implement. (noop_region_model_context::checking_for_infinite_loop_p): Likewise. (noop_region_model_context::on_unusable_in_infinite_loop): Likewise. (region_model_context_decorator::maybe_did_work): Implement. (region_model_context_decorator::checking_for_infinite_loop_p): Likewise. (region_model_context_decorator::on_unusable_in_infinite_loop): Likewise. (model_merger::on_widening_reuse): New decl. (model_merger::m_svals_changing_meaning): New field. * sm-signal.cc (register_signal_handler::impl_transition): Assume the edge "does work". * supergraph.cc (supernode::get_start_location): Use CFG edge's goto_locus if available. (supernode::get_end_location): Likewise. (cfg_superedge::dump_label_to_pp): Dump edges with a "goto_locus" * supergraph.h (cfg_superedge::get_goto_locus): New. * svalue.cc (svalue::can_merge_p): Call on_widening_reuse for widening values. (involvement_visitor::visit_widening_svalue): New. (svalue::involves_p): Update assertion to allow widening svalues. gcc/testsuite/ChangeLog: PR analyzer/106147 * c-c++-common/analyzer/gzio-2.c: Add dg-warning for infinite loop, marked as xfail. * c-c++-common/analyzer/infinite-loop-2.c: New test. * c-c++-common/analyzer/infinite-loop-4.c: New test. * c-c++-common/analyzer/infinite-loop-crc32c.c: New test. * c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c: New test. * c-c++-common/analyzer/infinite-loop-doom-v_video.c: New test. * c-c++-common/analyzer/infinite-loop-g_error.c: New test. * c-c++-common/analyzer/infinite-loop-linked-list.c: New test. * c-c++-common/analyzer/infinite-recursion-inlining.c: Add dg-warning directives for infinite loop. * c-c++-common/analyzer/inlining-4-multiline.c: Update expected paths for event 5 having a location. * gcc.dg/analyzer/boxed-malloc-1.c: Add dg-warning for infinite loop. * gcc.dg/analyzer/data-model-20.c: Likewise. Add comment about suspect code, and create... * gcc.dg/analyzer/data-model-20a.c: ...this new test by cleaning it up. * gcc.dg/analyzer/edges-1.c: Add a placeholder statement to avoid the "...to here" from the if stmt occurring at the "while", and thus being treated as a bogus event. * gcc.dg/analyzer/explode-2a.c: Add dg-warning for infinite loop. * gcc.dg/analyzer/infinite-loop-1.c: New test. * gcc.dg/analyzer/malloc-1.c: Add dg-warning for infinite loop. * gcc.dg/analyzer/out-of-bounds-coreutils.c: Add TODO. * gcc.dg/analyzer/paths-4.c: Add dg-warning for infinite loop. * gcc.dg/analyzer/pr103892.c: Likewise. * gcc.dg/analyzer/pr93546.c: Likewise. Signed-off-by: David Malcolm <dmalcolm@redhat.com>
next prev parent reply other threads:[~2023-11-18 0:59 UTC|newest] Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top 2022-06-30 12:46 [Bug analyzer/106147] New: " dmalcolm at gcc dot gnu.org 2022-06-30 12:57 ` [Bug analyzer/106147] " dmalcolm at gcc dot gnu.org 2022-07-29 22:20 ` dmalcolm at gcc dot gnu.org 2022-08-10 13:48 ` dmalcolm at gcc dot gnu.org 2022-11-10 20:38 ` dmalcolm at gcc dot gnu.org 2022-11-11 21:04 ` cvs-commit at gcc dot gnu.org 2022-11-11 21:24 ` dmalcolm at gcc dot gnu.org 2023-11-18 0:59 ` cvs-commit at gcc dot gnu.org [this message] 2024-01-12 19:14 ` dmalcolm at gcc dot gnu.org 2024-01-20 17:20 ` pinskia at gcc dot gnu.org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-106147-4-8mr12yutM2@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).