From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 79F773857B85; Sat, 18 Nov 2023 00:59:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 79F773857B85 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1700269177; bh=ytAEKUjF064Ym6QXYBaBxcilQkX88IlAGvOkXn85FQE=; h=From:To:Subject:Date:In-Reply-To:References:From; b=H2vCjXHN8c4bQkIzkOd1JNaMAODJ8WtCMhEEnfTP+uLXbQqQD6CcBw0faOyQ1Gqk1 tToPx3/Dl7YkBw58rjKoPYAR4cai9EQftNhYtspB4RxXZdBvF7RdMGy0BzCP7c/WgS XTh9cbVNZBIX45G19WA6Zqxmzx7vGPCOB+NkBaLg= From: "cvs-commit at gcc dot 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 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: analyzer X-Bugzilla-Version: 13.0 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: cvs-commit at gcc dot gnu.org X-Bugzilla-Status: ASSIGNED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: dmalcolm at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D106147 --- Comment #7 from CVS Commits --- The master branch has been updated by David Malcolm : https://gcc.gnu.org/g:841008d3966c0fe7a80ec10703a50fbdab7620ac commit r14-5566-g841008d3966c0fe7a80ec10703a50fbdab7620ac Author: David Malcolm 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 =3D 0; for (struct node *iter =3D n; iter; iter->next) sum +=3D n->val; return sum; like this: infinite-loop-linked-list.c: In function =C3=A2for_loop_noop_next=C3=A2: infinite-loop-linked-list.c:110:31: warning: infinite loop [CWE-835] [-Wanalyzer-infinite-loop] 110 | for (struct node *iter =3D n; iter; iter->next) | ^~~~ =C3=A2for_loop_noop_next=C3=A2: events 1-5 | | 110 | for (struct node *iter =3D n; iter; iter->next) | | ^~~~ | | | | | (1) infinite loop here | | (2) when =C3=A2iter=C3=A2 is= non-NULL: always following =C3=A2true=C3=A2 branch... | | (5) ...to here | 111 | sum +=3D 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 u= se 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 wor= k. (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 u= se 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=3D): 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=3D): 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 writ= es 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 functio= ns 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 infini= te loop, bail out on unusable svalues, or if we don't have a defin= ite 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 "kno= ws" 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): Assu= me 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_locu= s" * 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 svalue= s. 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 avo= id 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 loo= p. * 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 =