From patchwork Sat Nov 18 01:03:47 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 166419 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:9910:0:b0:403:3b70:6f57 with SMTP id i16csp920123vqn; Fri, 17 Nov 2023 17:05:01 -0800 (PST) X-Google-Smtp-Source: AGHT+IEK2KmvZiwfOSDtCFhK35AGWvccbwHtZvri16qmjy3nmv8FpDFHtUyFPP0TNzWFUidDs8t4 X-Received: by 2002:ae9:e004:0:b0:77a:51ab:fd46 with SMTP id m4-20020ae9e004000000b0077a51abfd46mr1229350qkk.31.1700269500910; Fri, 17 Nov 2023 17:05:00 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1700269500; cv=pass; d=google.com; s=arc-20160816; b=fQxb4EV40sXYH+vMA1XGfjHvtj0sq9igFzsFFiSSUMEiWT7pMYj7e5BrOqXy22heYH TlPsuNCDgFEvW3FeSWS6fpqmYDGtK/NbJ1hjJRRVe7GN4mQysBsJIrlv1y6x2gt4rDLa aF/w6j5skYxCFvKpV1uWSE0jJTPz7rUmp+A14v2r8GMiDxlmxEbp+2ghqJNYkOZAwnqS jgGXoPXpY5DLuB88yWGIA+LPDrzi+vF9O3SyGPfJ/SzBiXqg3UxbWMZ4PAyV1OmndraD ai0cCMJadNVqR/gYwsZQfERBYSY30cPwe4hbYZnmBxuW/MIahVK5WRduSVoD1J55EHkk 5g1A== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:message-id:date:subject:cc:to:from:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=+fNxfCdrRxd8lZ+UOLLgiQ2crqztAUaMKxyL4CAOLjw=; fh=NXemEfxTRbZtBxUkxR2ehQUaYlcDfMdzPkO8MChVQE4=; b=BkUt3n+5MD8qVvqDXFTKPxqMPEaEuzl+y3Gan1hDaR3Cxm9W5eyjbxx9r2TDNqo2ml qeCO4me6GjwNKCfrFqEUXogyrFycbLa5xd93K8xxbWsqKA4SFhz00Jzx494Mf8Ls00pD hH885YsZ3pbVSxkrUNhhHpdioxL1ug72P5Hvc3qu6XXTSavRvRZhx2WYep9fTaaHHtZd Y4D1DfOi98FTAS17qTeV4aHgy/YqKLL27yaInh2f+yyAFUzua0dEZiFcBay1kFmGYewO C/b2BQr0x8udCiIEwcIngRCMrIp1Y3xN5TR78w1Sy7tZlg8g/SaHUgCHQk/SgTkj1Q/y DpaA== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=TwWLgRru; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id u7-20020a05620a430700b0077412011692si2989798qko.18.2023.11.17.17.05.00 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 17 Nov 2023 17:05:00 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=TwWLgRru; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9A21B385782F for ; Sat, 18 Nov 2023 01:05:00 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 2004E3858404 for ; Sat, 18 Nov 2023 01:03:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2004E3858404 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 2004E3858404 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700269439; cv=none; b=WOsEUpxUzEBj5O4CNdlKrz41F6GyWqEEGewlzfSgNqCps6srugbrPe1lVX1Xv15USpyqeC8n7dxKSNLP9sKpdizIJGVjWaU0vLJWQ763D20emIpFBigtr1CN45gN/84W3EeqXKdUBGfMSf/9uWGLOKsDHW3PMm4zkLSBGC0pLOc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700269439; c=relaxed/simple; bh=aeXKtSX6ua2rm6GLAup1XIaiAqM0yjMsE/zxmBrxFIY=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=pzXgXQBFHp0mfOXK9kpK9TLLj4ix9S7avb0Hgi80tX8PHAoeyCUkh0RjYe2Vs94Yh7TKzmzMdwy7Bt4e6z78oJpZIcZ3lVXpDkoBcbo7ot1Fd4aFY1dUVlWeBwsR4mgk8JoRQNTHNVW7TeVFYQdHfKAIPYOAeVG84j960r4D+Ns= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1700269432; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=+fNxfCdrRxd8lZ+UOLLgiQ2crqztAUaMKxyL4CAOLjw=; b=TwWLgRruy8RuKnNf0j+Z8dCo4Yu9+RG/atEH5Frcq030a3San+3uZm9psRo2yPkN88kRw6 IeMRotcuU8u9+1EMxLV1poPlNZqZa61M0IAClV2epnjPb6aedu9Ou2CgOH4Uux0WQZIzg5 5SabCRmCPii3zM0WY+YiGZYwf8euMvc= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-656-CaEnqN08PoiwmXMlWbT1sQ-1; Fri, 17 Nov 2023 20:03:51 -0500 X-MC-Unique: CaEnqN08PoiwmXMlWbT1sQ-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.rdu2.redhat.com [10.11.54.8]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id D7CCA85A5BD for ; Sat, 18 Nov 2023 01:03:50 +0000 (UTC) Received: from t14s.localdomain.com (unknown [10.22.10.115]) by smtp.corp.redhat.com (Postfix) with ESMTP id 84601C15881; Sat, 18 Nov 2023 01:03:50 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [pushed] analyzer: new warning: -Wanalyzer-infinite-loop [PR106147] Date: Fri, 17 Nov 2023 20:03:47 -0500 Message-Id: <20231118010347.39147-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.8 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-11.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_FILL_THIS_FORM_SHORT, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1782861792024183258 X-GMAIL-MSGID: 1782861792024183258 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... | Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. My integration test suite shows 12 true positives and 2 false positives, which seems good enough for an initial implementation; I'll file bugs for myself to track fixing the two false positives. Pushed to trunk as r14-5566-g841008d3966c0f. 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. --- gcc/Makefile.in | 1 + gcc/analyzer/analyzer.opt | 8 + gcc/analyzer/checker-event.h | 5 +- gcc/analyzer/checker-path.h | 1 + gcc/analyzer/diagnostic-manager.cc | 2 +- gcc/analyzer/engine.cc | 122 ++-- gcc/analyzer/exploded-graph.h | 39 +- gcc/analyzer/infinite-loop.cc | 565 ++++++++++++++++++ gcc/analyzer/program-state.cc | 17 +- gcc/analyzer/region-model.cc | 77 ++- gcc/analyzer/region-model.h | 31 + gcc/analyzer/sm-signal.cc | 1 + gcc/analyzer/supergraph.cc | 16 + gcc/analyzer/supergraph.h | 2 + gcc/analyzer/svalue.cc | 10 +- gcc/doc/invoke.texi | 62 ++ gcc/testsuite/c-c++-common/analyzer/gzio-2.c | 2 +- .../c-c++-common/analyzer/infinite-loop-2.c | 34 ++ .../c-c++-common/analyzer/infinite-loop-4.c | 71 +++ .../analyzer/infinite-loop-crc32c.c | 14 + ...nfinite-loop-doom-d_main-IdentifyVersion.c | 26 + .../analyzer/infinite-loop-doom-v_video.c | 31 + .../analyzer/infinite-loop-g_error.c | 19 + .../analyzer/infinite-loop-linked-list.c | 131 ++++ .../analyzer/infinite-recursion-inlining.c | 28 +- .../analyzer/inlining-4-multiline.c | 34 +- .../gcc.dg/analyzer/boxed-malloc-1.c | 2 +- gcc/testsuite/gcc.dg/analyzer/data-model-20.c | 6 +- .../gcc.dg/analyzer/data-model-20a.c | 25 + gcc/testsuite/gcc.dg/analyzer/edges-1.c | 2 + gcc/testsuite/gcc.dg/analyzer/explode-2a.c | 2 +- .../gcc.dg/analyzer/infinite-loop-1.c | 235 ++++++++ gcc/testsuite/gcc.dg/analyzer/malloc-1.c | 2 +- .../gcc.dg/analyzer/out-of-bounds-coreutils.c | 2 +- gcc/testsuite/gcc.dg/analyzer/paths-4.c | 3 +- gcc/testsuite/gcc.dg/analyzer/pr103892.c | 2 +- gcc/testsuite/gcc.dg/analyzer/pr93546.c | 2 +- gcc/timevar.def | 1 + 38 files changed, 1547 insertions(+), 86 deletions(-) create mode 100644 gcc/analyzer/infinite-loop.cc create mode 100644 gcc/testsuite/c-c++-common/analyzer/infinite-loop-2.c create mode 100644 gcc/testsuite/c-c++-common/analyzer/infinite-loop-4.c create mode 100644 gcc/testsuite/c-c++-common/analyzer/infinite-loop-crc32c.c create mode 100644 gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c create mode 100644 gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-v_video.c create mode 100644 gcc/testsuite/c-c++-common/analyzer/infinite-loop-g_error.c create mode 100644 gcc/testsuite/c-c++-common/analyzer/infinite-loop-linked-list.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/data-model-20a.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-loop-1.c diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 7f2df4b5925..7228b79f223 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1324,6 +1324,7 @@ ANALYZER_OBJS = \ analyzer/engine.o \ analyzer/feasible-graph.o \ analyzer/function-set.o \ + analyzer/infinite-loop.o \ analyzer/infinite-recursion.o \ analyzer/kf.o \ analyzer/kf-analyzer.o \ diff --git a/gcc/analyzer/analyzer.opt b/gcc/analyzer/analyzer.opt index 25df89d9c06..fae2649389a 100644 --- a/gcc/analyzer/analyzer.opt +++ b/gcc/analyzer/analyzer.opt @@ -134,6 +134,10 @@ Wanalyzer-imprecise-fp-arithmetic Common Var(warn_analyzer_imprecise_fp_arithmetic) Init(1) Warning Warn about code paths in which floating-point arithmetic is used in locations where precise computation is needed. +Wanalyzer-infinite-loop +Common Var(warn_analyzer_infinite_loop) Init(1) Warning +Warn about code paths which appear to lead to an infinite loop. + Wanalyzer-infinite-recursion Common Var(warn_analyzer_infinite_recursion) Init(1) Warning Warn about code paths which appear to lead to infinite recursion. @@ -354,6 +358,10 @@ fdump-analyzer-feasibility Common RejectNegative Var(flag_dump_analyzer_feasibility) Dump various analyzer internals to SRCFILE.*.fg.dot and SRCFILE.*.tg.dot. +fdump-analyzer-infinite-loop +Common RejectNegative Var(flag_dump_analyzer_infinite_loop) +Dump various analyzer internals to SRCFILE.*.infinite-loop.dot. + fdump-analyzer-json Common RejectNegative Var(flag_dump_analyzer_json) Dump analyzer-specific data to a SRCFILE.analyzer.json.gz file. diff --git a/gcc/analyzer/checker-event.h b/gcc/analyzer/checker-event.h index 7ba92f19650..dcb2e27faa6 100644 --- a/gcc/analyzer/checker-event.h +++ b/gcc/analyzer/checker-event.h @@ -444,11 +444,12 @@ public: { } - label_text get_desc (bool can_colorize) const final override; + label_text get_desc (bool can_colorize) const override; - private: +protected: label_text maybe_describe_condition (bool can_colorize) const; +private: static label_text maybe_describe_condition (bool can_colorize, tree lhs, enum tree_code op, diff --git a/gcc/analyzer/checker-path.h b/gcc/analyzer/checker-path.h index 93c807c3d24..055d5e38b3f 100644 --- a/gcc/analyzer/checker-path.h +++ b/gcc/analyzer/checker-path.h @@ -65,6 +65,7 @@ public: void dump (pretty_printer *pp) const; void debug () const; + logger *get_logger () const { return m_logger; } void maybe_log (logger *logger, const char *desc) const; void add_event (std::unique_ptr event); diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index 972413a751a..a6755f2193f 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -517,7 +517,7 @@ process_worklist_item (feasible_worklist *worklist, feasibility_state succ_state (fnode->get_state ()); std::unique_ptr rc; - if (succ_state.maybe_update_for_edge (logger, succ_eedge, &rc)) + if (succ_state.maybe_update_for_edge (logger, succ_eedge, nullptr, &rc)) { gcc_assert (rc == NULL); feasible_node *succ_fnode diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index 4861ee54e98..041fe6a1d40 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -85,7 +85,8 @@ impl_region_model_context (exploded_graph &eg, uncertainty_t *uncertainty, path_context *path_ctxt, const gimple *stmt, - stmt_finder *stmt_finder) + stmt_finder *stmt_finder, + bool *out_could_have_done_work) : m_eg (&eg), m_logger (eg.get_logger ()), m_enode_for_diag (enode_for_diag), m_old_state (old_state), @@ -94,7 +95,8 @@ impl_region_model_context (exploded_graph &eg, m_stmt_finder (stmt_finder), m_ext_state (eg.get_ext_state ()), m_uncertainty (uncertainty), - m_path_ctxt (path_ctxt) + m_path_ctxt (path_ctxt), + m_out_could_have_done_work (out_could_have_done_work) { } @@ -110,7 +112,8 @@ impl_region_model_context (program_state *state, m_stmt_finder (NULL), m_ext_state (ext_state), m_uncertainty (uncertainty), - m_path_ctxt (NULL) + m_path_ctxt (NULL), + m_out_could_have_done_work (nullptr) { } @@ -1024,6 +1027,17 @@ impl_region_model_context::on_unexpected_tree_code (tree t, m_new_state->m_valid = false; } +/* Implementation of region_model_context::maybe_did_work vfunc. + Mark that "externally visible work" has occurred, and thus we + shouldn't report an infinite loop here. */ + +void +impl_region_model_context::maybe_did_work () +{ + if (m_out_could_have_done_work) + *m_out_could_have_done_work = true; +} + /* struct point_and_state. */ /* Assert that this object is sane. */ @@ -1439,6 +1453,7 @@ exploded_node::on_stmt (exploded_graph &eg, const gimple *stmt, program_state *state, uncertainty_t *uncertainty, + bool *out_could_have_done_work, path_context *path_ctxt) { logger *logger = eg.get_logger (); @@ -1464,7 +1479,8 @@ exploded_node::on_stmt (exploded_graph &eg, impl_region_model_context ctxt (eg, this, &old_state, state, uncertainty, - path_ctxt, stmt); + path_ctxt, stmt, nullptr, + out_could_have_done_work); /* Handle call summaries here. */ if (cgraph_edge *cgedge @@ -1551,12 +1567,16 @@ exploded_node::on_stmt_pre (exploded_graph &eg, else if (is_setjmp_call_p (call)) { state->m_region_model->on_setjmp (call, this, ctxt); + if (ctxt) + ctxt->maybe_did_work (); return; } else if (is_longjmp_call_p (call)) { on_longjmp (eg, call, state, ctxt); *out_terminate_path = true; + if (ctxt) + ctxt->maybe_did_work (); return; } } @@ -1938,8 +1958,9 @@ exploded_node::on_longjmp (exploded_graph &eg, if (next) { exploded_edge *eedge - = eg.add_edge (const_cast (this), next, NULL, - make_unique (tmp_setjmp_record, longjmp_call)); + = eg.add_edge (const_cast (this), next, NULL, true, + make_unique (tmp_setjmp_record, + longjmp_call)); /* For any diagnostics that were queued here (such as leaks) we want the checker_path to show the rewinding events after the "final event" @@ -2161,10 +2182,11 @@ rewind_info_t::add_events_to_path (checker_path *emission_path, /* exploded_edge's ctor. */ exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest, - const superedge *sedge, + const superedge *sedge, bool could_do_work, std::unique_ptr custom_info) : dedge (src, dest), m_sedge (sedge), - m_custom_info (std::move (custom_info)) + m_custom_info (std::move (custom_info)), + m_could_do_work_p (could_do_work) { } @@ -2228,6 +2250,9 @@ exploded_edge::dump_dot_label (pretty_printer *pp) const else if (m_custom_info) m_custom_info->print (pp); + pp_printf (pp, "%s", + could_do_work_p () ? "(could do work)" : "DOES NO WORK"); + //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false); pp_printf (pp, "\"];\n"); @@ -2790,7 +2815,7 @@ exploded_graph::add_function_entry (function *fun) if (!enode) return NULL; - add_edge (m_origin, enode, NULL, std::move (edge_info)); + add_edge (m_origin, enode, NULL, false, std::move (edge_info)); m_functions_with_enodes.add (fun); @@ -2988,19 +3013,20 @@ exploded_graph::get_or_create_node (const program_point &point, /* Add an exploded_edge from SRC to DEST, recording its association with SEDGE (which may be NULL), and, if non-NULL, taking ownership - of CUSTOM_INFO. + of CUSTOM_INFO. COULD_DO_WORK is used for detecting infinite loops. Return the newly-created eedge. */ exploded_edge * exploded_graph::add_edge (exploded_node *src, exploded_node *dest, - const superedge *sedge, - std::unique_ptr custom_info) + const superedge *sedge, bool could_do_work, + std::unique_ptr custom_info) { if (get_logger ()) get_logger ()->log ("creating edge EN: %i -> EN: %i", src->m_index, dest->m_index); - exploded_edge *e = new exploded_edge (src, dest, sedge, - std::move (custom_info)); + exploded_edge *e + = new exploded_edge (src, dest, sedge, could_do_work, + std::move (custom_info)); digraph::add_edge (e); return e; } @@ -3249,7 +3275,7 @@ add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl, } } - eg->add_edge (eg->get_origin (), enode, NULL, + eg->add_edge (eg->get_origin (), enode, NULL, false, make_unique (field, fndecl, loc)); } @@ -3403,7 +3429,7 @@ exploded_graph::process_worklist () if (merged_state == state) { /* Then merge node_2 into node by adding an edge. */ - add_edge (node_2, node, NULL); + add_edge (node_2, node, NULL, false); /* Remove node_2 from the worklist. */ m_worklist.take_next (); @@ -3416,7 +3442,7 @@ exploded_graph::process_worklist () /* Then merge node into node_2, and leave node_2 in the worklist, to be processed on the next iteration. */ - add_edge (node, node_2, NULL); + add_edge (node, node_2, NULL, false); node->set_status (exploded_node::STATUS_MERGER); continue; } @@ -3461,7 +3487,7 @@ exploded_graph::process_worklist () m_worklist.add_node (merged_enode); else { - add_edge (node, merged_enode, NULL); + add_edge (node, merged_enode, NULL, false); node->set_status (exploded_node::STATUS_MERGER); } @@ -3469,7 +3495,7 @@ exploded_graph::process_worklist () m_worklist.add_node (merged_enode); else { - add_edge (node_2, merged_enode, NULL); + add_edge (node_2, merged_enode, NULL, false); node_2->set_status (exploded_node::STATUS_MERGER); } @@ -3704,7 +3730,8 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode) { exploded_node *next = next_enodes[it->m_merger_idx]; if (next) - add_edge (it->m_input_enode, next, NULL); + add_edge (it->m_input_enode, next, NULL, + false); /* no "work" is done during merger. */ it->m_input_enode->set_status (exploded_node::STATUS_BULK_MERGED); } @@ -3847,6 +3874,7 @@ exploded_graph::maybe_create_dynamic_call (const gcall *call, node); if (enode) add_edge (node,enode, NULL, + false, /* No work is done by the call itself. */ make_unique (call)); return true; } @@ -4039,7 +4067,8 @@ exploded_graph::process_node (exploded_node *node) program_point next_point (point.get_next ()); exploded_node *next = get_or_create_node (next_point, next_state, node); if (next) - add_edge (node, next, NULL); + add_edge (node, next, NULL, + false); /* Assume no work is done at phi nodes. */ } break; case PK_BEFORE_STMT: @@ -4067,6 +4096,7 @@ exploded_graph::process_node (exploded_node *node) impl_path_context path_ctxt (&next_state, logger); + bool could_have_done_work = false; uncertainty_t uncertainty; const supernode *snode = point.get_supernode (); unsigned stmt_idx; @@ -4090,7 +4120,7 @@ exploded_graph::process_node (exploded_node *node) /* Process the stmt. */ exploded_node::on_stmt_flags flags = node->on_stmt (*this, snode, stmt, &next_state, &uncertainty, - &path_ctxt); + &could_have_done_work, &path_ctxt); node->m_num_processed_stmts++; /* If flags.m_terminate_path, stop analyzing; any nodes/edges @@ -4147,7 +4177,7 @@ exploded_graph::process_node (exploded_node *node) node->m_num_processed_stmts--; if (logger) logger->log ("creating edge to split_enode"); - add_edge (node, split_enode, NULL); + add_edge (node, split_enode, NULL, could_have_done_work); return; } else @@ -4174,7 +4204,7 @@ exploded_graph::process_node (exploded_node *node) exploded_node *next = get_or_create_node (next_point, next_state, node); if (next) - add_edge (node, next, NULL); + add_edge (node, next, NULL, could_have_done_work); } /* If we have custom edge infos, "bifurcate" the state @@ -4212,7 +4242,9 @@ exploded_graph::process_node (exploded_node *node) exploded_node *next2 = get_or_create_node (next_point, bifurcated_new_state, node); if (next2) - add_edge (node, next2, NULL, std::move (edge_info)); + add_edge (node, next2, NULL, + true /* assume that work could be done */, + std::move (edge_info)); } else { @@ -4327,7 +4359,8 @@ exploded_graph::process_node (exploded_node *node) next_state, node); if (next) - add_edge (node, next, succ); + add_edge (node, next, succ, + true /* assume that work is done */); } } @@ -4343,7 +4376,7 @@ exploded_graph::process_node (exploded_node *node) node); if (next) { - add_edge (node, next, succ); + add_edge (node, next, succ, false); /* We might have a function entrypoint. */ detect_infinite_recursion (next); @@ -4377,7 +4410,7 @@ exploded_graph::process_node (exploded_node *node) next_state, node); if (enode) - add_edge (node, enode, NULL, + add_edge (node, enode, NULL, false, make_unique (call, true)); } } @@ -4708,7 +4741,7 @@ exploded_path::feasible_p (logger *logger, eedge->m_dest->m_index); std::unique_ptr rc; - if (!state.maybe_update_for_edge (logger, eedge, &rc)) + if (!state.maybe_update_for_edge (logger, eedge, nullptr, &rc)) { gcc_assert (rc); if (out) @@ -4835,6 +4868,21 @@ feasibility_state::feasibility_state (const feasibility_state &other) bitmap_copy (m_snodes_visited, other.m_snodes_visited); } +feasibility_state::feasibility_state (const region_model &model, + const supergraph &sg) +: m_model (model), + m_snodes_visited (sg.m_nodes.length ()) +{ +} + +feasibility_state & +feasibility_state::operator= (const feasibility_state &other) +{ + m_model = other.m_model; + bitmap_copy (m_snodes_visited, other.m_snodes_visited); + return *this; +} + /* The heart of feasibility-checking. Attempt to update this state in-place based on traversing EEDGE @@ -4849,6 +4897,7 @@ bool feasibility_state:: maybe_update_for_edge (logger *logger, const exploded_edge *eedge, + region_model_context *ctxt, std::unique_ptr *out_rc) { const exploded_node &src_enode = *eedge->m_src; @@ -4887,12 +4936,14 @@ maybe_update_for_edge (logger *logger, } const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); - if (!m_model.maybe_update_for_edge (*sedge, last_stmt, NULL, out_rc)) + if (!m_model.maybe_update_for_edge (*sedge, last_stmt, ctxt, out_rc)) { if (logger) { - logger->log ("rejecting due to region model"); + logger->start_log_line (); + logger->log_partial ("rejecting due to region model: "); m_model.dump_to_pp (logger->get_printer (), true, false); + logger->end_log_line (); } return false; } @@ -4908,13 +4959,13 @@ maybe_update_for_edge (logger *logger, == PK_BEFORE_SUPERNODE); function *fun = eedge->m_dest->get_function (); gcc_assert (fun); - m_model.push_frame (fun, NULL, NULL); + m_model.push_frame (fun, NULL, ctxt); if (logger) logger->log (" pushing frame for %qD", fun->decl); } else if (eedge->m_custom_info) { - eedge->m_custom_info->update_model (&m_model, eedge, NULL); + eedge->m_custom_info->update_model (&m_model, eedge, ctxt); } } @@ -4933,7 +4984,7 @@ maybe_update_for_edge (logger *logger, logger->log (" update for phis"); m_model.update_for_phis (src_enode.get_supernode (), last_cfg_superedge, - NULL); + ctxt); /* If we've entering an snode that we've already visited on this epath, then we need do fix things up for loops; see the comment for store::loop_replay_fixup. @@ -6153,6 +6204,9 @@ impl_run_checkers (logger *logger) /* Now process the worklist, exploring the graph. */ eg.process_worklist (); + if (warn_analyzer_infinite_loop) + eg.detect_infinite_loops (); + if (flag_dump_analyzer_exploded_graph) { auto_timevar tv (TV_ANALYZER_DUMP); diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index cb64c2a180a..45ee0d1f175 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -49,7 +49,9 @@ class impl_region_model_context : public region_model_context path_context *path_ctxt, const gimple *stmt, - stmt_finder *stmt_finder = NULL); + stmt_finder *stmt_finder = NULL, + + bool *out_could_have_done_work = nullptr); impl_region_model_context (program_state *state, const extrinsic_state &ext_state, @@ -110,6 +112,10 @@ class impl_region_model_context : public region_model_context const gimple *get_stmt () const override { return m_stmt; } const exploded_graph *get_eg () const override { return m_eg; } + void maybe_did_work () override; + bool checking_for_infinite_loop_p () const override { return false; } + void on_unusable_in_infinite_loop () override {} + exploded_graph *m_eg; log_user m_logger; exploded_node *m_enode_for_diag; @@ -120,6 +126,7 @@ class impl_region_model_context : public region_model_context const extrinsic_state &m_ext_state; uncertainty_t *m_uncertainty; path_context *m_path_ctxt; + bool *m_out_could_have_done_work; }; /* A pair, used internally by @@ -260,6 +267,7 @@ class exploded_node : public dnode const gimple *stmt, program_state *state, uncertainty_t *uncertainty, + bool *out_could_have_done_work, path_context *path_ctxt); void on_stmt_pre (exploded_graph &eg, const gimple *stmt, @@ -373,7 +381,7 @@ class exploded_edge : public dedge { public: exploded_edge (exploded_node *src, exploded_node *dest, - const superedge *sedge, + const superedge *sedge, bool could_do_work, std::unique_ptr custom_info); void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override; @@ -389,8 +397,25 @@ class exploded_edge : public dedge a signal is delivered to a signal-handler. */ std::unique_ptr m_custom_info; + bool could_do_work_p () const { return m_could_do_work_p; } + private: DISABLE_COPY_AND_ASSIGN (exploded_edge); + + /* For -Wanalyzer-infinite-loop. + Set to true during processing if any of the activity along + this edge is "externally-visible work" (and thus ruling this + out as being part of an infinite loop. + + For example, given: + + while (1) + do_something (); + + although it is an infinite loop, presumably the point of the + program is the loop body, and thus reporting this as an infinite + loop is likely to be unhelpful to the user. */ + bool m_could_do_work_p; }; /* Extra data for an exploded_edge that represents dynamic call info ( calls @@ -804,7 +829,7 @@ public: const program_state &state, exploded_node *enode_for_diag); exploded_edge *add_edge (exploded_node *src, exploded_node *dest, - const superedge *sedge, + const superedge *sedge, bool could_do_work, std::unique_ptr custom = NULL); per_program_point_data * @@ -856,6 +881,9 @@ public: void on_escaped_function (tree fndecl); + /* In infinite-loop.cc */ + void detect_infinite_loops (); + /* In infinite-recursion.cc */ void detect_infinite_recursion (exploded_node *enode); exploded_node *find_previous_entry_to (function *top_of_stack_fun, @@ -970,10 +998,15 @@ class feasibility_state public: feasibility_state (region_model_manager *manager, const supergraph &sg); + feasibility_state (const region_model &model, + const supergraph &sg); feasibility_state (const feasibility_state &other); + feasibility_state &operator= (const feasibility_state &other); + bool maybe_update_for_edge (logger *logger, const exploded_edge *eedge, + region_model_context *ctxt, std::unique_ptr *out_rc); void update_for_stmt (const gimple *stmt); diff --git a/gcc/analyzer/infinite-loop.cc b/gcc/analyzer/infinite-loop.cc new file mode 100644 index 00000000000..771d698a60b --- /dev/null +++ b/gcc/analyzer/infinite-loop.cc @@ -0,0 +1,565 @@ +/* Detection of infinite loops. + Copyright (C) 2022-2023 Free Software Foundation, Inc. + Contributed by David Malcolm . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#define INCLUDE_MEMORY +#define INCLUDE_VECTOR +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "fold-const.h" +#include "gcc-rich-location.h" +#include "alloc-pool.h" +#include "fibonacci_heap.h" +#include "shortest-paths.h" +#include "diagnostic-core.h" +#include "diagnostic-event-id.h" +#include "diagnostic-path.h" +#include "diagnostic-metadata.h" +#include "function.h" +#include "pretty-print.h" +#include "sbitmap.h" +#include "bitmap.h" +#include "tristate.h" +#include "ordered-hash-map.h" +#include "selftest.h" +#include "json.h" +#include "analyzer/analyzer.h" +#include "analyzer/analyzer-logging.h" +#include "analyzer/call-string.h" +#include "analyzer/program-point.h" +#include "analyzer/store.h" +#include "analyzer/region-model.h" +#include "analyzer/constraint-manager.h" +#include "analyzer/sm.h" +#include "analyzer/pending-diagnostic.h" +#include "analyzer/diagnostic-manager.h" +#include "cfg.h" +#include "basic-block.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "gimple-pretty-print.h" +#include "cgraph.h" +#include "digraph.h" +#include "analyzer/supergraph.h" +#include "analyzer/program-state.h" +#include "analyzer/exploded-graph.h" +#include "analyzer/checker-path.h" +#include "analyzer/feasible-graph.h" +#include "make-unique.h" + +/* A bundle of data characterizing a particular infinite loop + identified within the exploded graph. */ + +struct infinite_loop +{ + infinite_loop (const exploded_node &enode, + location_t loc, + std::vector eedges, + logger *logger) + : m_enode (enode), + m_loc (loc), + m_eedge_vec (eedges) + { + LOG_SCOPE (logger); + if (logger) + { + logger->start_log_line (); + logger->log_partial ("infinite loop: EN: %i", m_enode.m_index); + for (auto eedge : m_eedge_vec) + { + logger->log_partial (" ->"); + if (const superedge *sedge = eedge->m_sedge) + { + sedge->dump_label_to_pp (logger->get_printer (), false); + } + logger->log_partial (" EN: %i", eedge->m_dest->m_index); + } + logger->end_log_line (); + } + } + + bool + operator== (const infinite_loop &other) const + { + /* Compare underlying supernode, rather than enodes, so that + we don't get duplicates in functions that are called from + elsewhere. */ + return (m_enode.get_supernode () == other.m_enode.get_supernode () + && m_loc == other.m_loc); + } + + const exploded_node &m_enode; + location_t m_loc; + std::vector m_eedge_vec; +}; + +/* A custom subclass of start_cfg_edge_event that rewords the + message to indicate that the CFG edge is *always* taken on + subsequent iterations, assuming it's been taken once. */ + +class perpetual_start_cfg_edge_event : public start_cfg_edge_event +{ +public: + perpetual_start_cfg_edge_event (const exploded_edge &eedge, + const event_loc_info &loc_info) + : start_cfg_edge_event (eedge, loc_info) + { + } + + label_text get_desc (bool can_colorize) const final override + { + bool user_facing = !flag_analyzer_verbose_edges; + label_text edge_desc (m_sedge->get_description (user_facing)); + if (user_facing) + { + if (edge_desc.get () && strlen (edge_desc.get ()) > 0) + { + label_text cond_desc = maybe_describe_condition (can_colorize); + label_text result; + if (cond_desc.get ()) + return make_label_text + (can_colorize, + "%s: always following %qs branch...", + cond_desc.get (), edge_desc.get ()); + else + return make_label_text + (can_colorize, + "if it ever follows %qs branch, it will always do so...", + edge_desc.get ()); + } + } + return start_cfg_edge_event::get_desc (can_colorize); + } +}; + +/* A subclass of pending_diagnostic for complaining about suspected + infinite loops. */ + +class infinite_loop_diagnostic +: public pending_diagnostic_subclass +{ +public: + infinite_loop_diagnostic (std::unique_ptr inf_loop) + : m_inf_loop (std::move (inf_loop)) + { + gcc_assert (m_inf_loop != nullptr); + } + + const char *get_kind () const final override + { + return "infinite_loop_diagnostic"; + } + + bool operator== (const infinite_loop_diagnostic &other) const + { + return *m_inf_loop == *other.m_inf_loop; + } + + int get_controlling_option () const final override + { + return OPT_Wanalyzer_infinite_loop; + } + + bool emit (rich_location *rich_loc, logger *) final override + { + /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */ + diagnostic_metadata m; + m.add_cwe (835); + return warning_meta (rich_loc, m, get_controlling_option (), + "infinite loop"); + } + + bool maybe_add_custom_events_for_superedge (const exploded_edge &, + checker_path *) + final override + { + /* Don't add any regular events; instead we add them after pruning as + part of the "final" warning. */ + return true; + } + + label_text describe_final_event (const evdesc::final_event &ev) final override + { + return ev.formatted_print ("infinite loop here"); + } + + /* Customize the location where the warning_event appears. */ + void add_final_event (const state_machine *, + const exploded_node *enode, + const gimple *, + tree, + state_machine::state_t, + checker_path *emission_path) final override + { + emission_path->add_event + (make_unique + (event_loc_info (m_inf_loop->m_loc, + enode->get_function ()->decl, + enode->get_stack_depth ()), + enode, + NULL, NULL, NULL)); + + logger *logger = emission_path->get_logger (); + + /* EMISSION_PATH has the path to the entry of the infinite loop. + Add extra edges showing the loop itself. */ + for (auto eedge : m_inf_loop->m_eedge_vec) + { + if (logger) + logger->log ("EN: %i -> EN: %i", + eedge->m_src->m_index, + eedge->m_dest->m_index); + if (!eedge->m_sedge) + continue; + + const cfg_superedge *cfg_sedge + = eedge->m_sedge->dyn_cast_cfg_superedge (); + if (!cfg_sedge) + continue; + + const exploded_node *src_node = eedge->m_src; + const program_point &src_point = src_node->get_point (); + const exploded_node *dst_node = eedge->m_dest; + const program_point &dst_point = dst_node->get_point (); + const int src_stack_depth = src_point.get_stack_depth (); + const int dst_stack_depth = dst_point.get_stack_depth (); + const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); + + event_loc_info loc_info_from + (last_stmt ? last_stmt->location : cfg_sedge->get_goto_locus (), + src_point.get_fndecl (), + src_stack_depth); + event_loc_info loc_info_to + (dst_point.get_supernode ()->get_start_location (), + dst_point.get_fndecl (), + dst_stack_depth); + + if (const switch_cfg_superedge *switch_cfg_sedge + = cfg_sedge->dyn_cast_switch_cfg_superedge ()) + { + if (switch_cfg_sedge->implicitly_created_default_p ()) + { + emission_path->add_event + (make_unique (*eedge, + loc_info_from)); + emission_path->add_event + (make_unique + (*eedge, + loc_info_to)); + } + } + + if (cfg_sedge->true_value_p ()) + { + emission_path->add_event + (make_unique (*eedge, + loc_info_from)); + emission_path->add_event + (make_unique + (*eedge, + loc_info_to)); + } + else if (cfg_sedge->false_value_p ()) + { + emission_path->add_event + (make_unique (*eedge, + loc_info_from)); + emission_path->add_event + (make_unique + (*eedge, + loc_info_to)); + } + else if (cfg_sedge->back_edge_p ()) + { + emission_path->add_event + (make_unique + (loc_info_from, "looping back...")); + emission_path->add_event + (make_unique + (*eedge, + loc_info_to)); + } + } + } + +private: + std::unique_ptr m_inf_loop; +}; + +/* If ENODE has an in-edge corresponding to a CFG backedge, return that + exploded in-edge. + Otherwise, return nullptr. */ + +static const exploded_edge * +get_in_edge_back_edge (const exploded_node &enode) +{ + for (auto in_edge : enode.m_preds) + { + const superedge *sedge = in_edge->m_sedge; + if (!sedge) + continue; + const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge (); + if (!cfg_sedge) + continue; + if (cfg_sedge->back_edge_p ()) + return in_edge; + } + return nullptr; +} + +/* Subclass of region_model_context that rejects conditional branches that + aren't known for definite. */ + +class infinite_loop_checking_context : public noop_region_model_context +{ +public: + infinite_loop_checking_context () : m_unusable (false) {} + + bool checking_for_infinite_loop_p () const override { return true; } + void on_unusable_in_infinite_loop () override { m_unusable = true; } + + bool unusable_p () const { return m_unusable; } + +private: + bool m_unusable; +}; + +/* Determine if an infinite loop starts at ENODE. + Return the loop if it is found, nullptr otherwise. + + Look for cycles in the exploded graph in which: + - no externally visible work occurs + - no escape from the cycle + - 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. */ + +static std::unique_ptr +starts_infinite_loop_p (const exploded_node &enode, + const exploded_graph &eg, + logger *logger) +{ + LOG_FUNC_1 (logger, "considering EN: %i", enode.m_index); + + /* Only consider enodes that have a CFG back edge as an in-edge. */ + if (const exploded_edge *back_edge = get_in_edge_back_edge (enode)) + { + if (logger) + logger->log ("got backedge from EN: %i", + back_edge->m_src->m_index); + } + else + { + if (logger) + logger->log ("rejecting: no backedge in in-edges"); + return nullptr; + } + + /* Support for dumping an .infinite-loop.dot file visualizing the + traversal for this enode. */ + std::unique_ptr fg; + feasible_node *curr_fnode = nullptr; + + if (flag_dump_analyzer_infinite_loop) + fg = ::make_unique (); + + location_t first_loc = UNKNOWN_LOCATION; + const exploded_node *iter = &enode; + feasibility_state state (*enode.get_state ().m_region_model, + eg.get_supergraph ()); + + if (fg) + curr_fnode = fg->add_node (&enode, state, 0); + + hash_set visited; + std::vector eedges; + while (1) + { + if (logger) + logger->log ("iter: EN: %i", iter->m_index); + /* Analysis bailed out before processing this node. */ + if (iter->get_status () == exploded_node::STATUS_WORKLIST) + { + if (logger) + logger->log ("rejecting: EN: %i is still in worklist", + iter->m_index); + return nullptr; + } + if (visited.contains (iter)) + { + /* We've looped back on ourselves. ENODE is in the loop + itself if ENODE is the first place we looped back, + as opposed to being on a path to a loop. */ + if (iter == &enode) + { + if (logger) + logger->log ("accepting: looped back to EN: %i", + iter->m_index); + if (fg) + { + auto_timevar tv (TV_ANALYZER_DUMP); + pretty_printer pp; + pp_printf (&pp, "%s.en%i.infinite-loop.dot", + dump_base_name, enode.m_index); + char *filename = xstrdup (pp_formatted_text (&pp)); + feasible_graph::dump_args_t dump_args (eg); + fg->dump_dot (filename, nullptr, dump_args); + free (filename); + } + return ::make_unique (enode, + first_loc, + eedges, + logger); + } + else + { + if (logger) + logger->log ("rejecting: looped back to EN: %i, not to EN: %i", + iter->m_index, enode.m_index); + return nullptr; + } + } + visited.add (iter); + if (first_loc == UNKNOWN_LOCATION) + { + location_t enode_loc = iter->get_point ().get_location (); + if (enode_loc != UNKNOWN_LOCATION) + first_loc = enode_loc; + } + + /* Find the out-edges that are feasible, given the + constraints here. */ + typedef std::pair pair_t; + std::vector succs; + for (auto out_edge : iter->m_succs) + { + log_scope s (logger, "considering out-edge", + "EN:%i -> EN:%i", + out_edge->m_src->m_index, + out_edge->m_dest->m_index); + feasibility_state next_state (state); + + /* Use this context to require edge conditions to be known, + rather than be merely "possible". */ + infinite_loop_checking_context ctxt; + if (next_state.maybe_update_for_edge (logger, + out_edge, + &ctxt, + nullptr)) + succs.push_back (pair_t (next_state, out_edge)); + if (ctxt.unusable_p ()) + { + /* If we get here, then we have e.g. a gcond where + the condition is UNKNOWN, or a condition + based on a widening_svalue. Reject such paths. */ + if (logger) + logger->log ("rejecting: unusable"); + return nullptr; + } + } + + if (succs.size () != 1) + { + if (logger) + logger->log ("rejecting: %i feasible successors", + (int)succs.size ()); + return nullptr; + } + const feasibility_state &next_state = succs[0].first; + const exploded_edge *out_eedge = succs[0].second; + if (out_eedge->could_do_work_p ()) + { + if (logger) + logger->log ("rejecting: edge could do work"); + return nullptr; + } + if (fg) + { + feasible_node *next_fnode = fg->add_node (out_eedge->m_dest, + next_state, + fg->m_nodes.length ()); + fg->add_edge (new feasible_edge (curr_fnode, next_fnode, out_eedge)); + curr_fnode = next_fnode; + } + state = next_state; + eedges.push_back (out_eedge); + if (first_loc == UNKNOWN_LOCATION) + { + if (out_eedge->m_sedge) + if (::edge cfg_edge = out_eedge->m_sedge->get_any_cfg_edge ()) + if (cfg_edge->goto_locus > BUILTINS_LOCATION) + first_loc = cfg_edge->goto_locus; + } + iter = out_eedge->m_dest; + } +} + +/* Implementation of -Wanalyzer-infinite-loop. */ + +void +exploded_graph::detect_infinite_loops () +{ + LOG_FUNC (get_logger ()); + auto_timevar tv (TV_ANALYZER_INFINITE_LOOPS); + + /* Track all enodes we've warned for; both the loop entrypoints + and all the enodes within those loops. */ + hash_set warned_for; + + for (auto enode : m_nodes) + { + if (get_logger ()) + get_logger ()->log ("visited: %i out of %i", + (int)warned_for.elements (), m_nodes.length ()); + + /* Only warn about the first enode we encounter in each cycle. */ + if (warned_for.contains(enode)) + continue; + + if (std::unique_ptr inf_loop + = starts_infinite_loop_p (*enode, *this, get_logger ())) + { + const supernode *snode = enode->get_supernode (); + + if (get_logger ()) + get_logger ()->log ("EN: %i from starts_infinite_loop_p", + enode->m_index); + + for (auto iter : inf_loop->m_eedge_vec) + warned_for.add (iter->m_src); + gcc_assert (warned_for.contains(enode)); + + if (inf_loop->m_loc == UNKNOWN_LOCATION) + { + if (get_logger ()) + get_logger ()->log + ("no location available for reporting infinite loop"); + continue; + } + + pending_location ploc (enode, snode, inf_loop->m_loc); + auto d + = ::make_unique (std::move (inf_loop)); + get_diagnostic_manager ().add_diagnostic (ploc, std::move (d)); + } + } +} diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc index 8dade4b5b3e..9bb81e6dddd 100644 --- a/gcc/analyzer/program-state.cc +++ b/gcc/analyzer/program-state.cc @@ -1145,15 +1145,22 @@ program_state::on_edge (exploded_graph &eg, this, uncertainty, &path_ctxt, last_stmt); + std::unique_ptr rc; + logger * const logger = eg.get_logger (); if (!m_region_model->maybe_update_for_edge (*succ, last_stmt, - &ctxt, NULL)) + &ctxt, + logger ? &rc : nullptr)) { - logger * const logger = eg.get_logger (); if (logger) - logger->log ("edge to SN: %i is impossible" - " due to region_model constraints", - succ->m_dest->m_index); + { + logger->start_log_line (); + logger->log_partial ("edge to SN: %i is impossible" + " due to region_model constraint: ", + succ->m_dest->m_index); + rc->dump_to_pp (logger->get_printer ()); + logger->end_log_line (); + } return false; } if (terminated) diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index dc834406520..052c47d38f1 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -1179,6 +1179,15 @@ region_model::on_assignment (const gassign *assign, region_model_context *ctxt) const region *lhs_reg = get_lvalue (lhs, ctxt); + /* Any writes other than to the stack are treated + as externally visible. */ + if (ctxt) + { + enum memory_space memspace = lhs_reg->get_memory_space (); + if (memspace != MEMSPACE_STACK) + ctxt->maybe_did_work (); + } + /* Most assignments are handled by: set_value (lhs_reg, SVALUE, CTXT) for some SVALUE. */ @@ -1277,6 +1286,8 @@ region_model::on_stmt_pre (const gimple *stmt, { const gasm *asm_stmt = as_a (stmt); on_asm_stmt (asm_stmt, ctxt); + if (ctxt) + ctxt->maybe_did_work (); } break; @@ -1701,7 +1712,11 @@ region_model::on_call_post (const gcall *call, } if (unknown_side_effects) - handle_unrecognized_call (call, ctxt); + { + handle_unrecognized_call (call, ctxt); + if (ctxt) + ctxt->maybe_did_work (); + } } /* Purge state involving SVAL from this region_model, using CTXT @@ -2236,6 +2251,7 @@ void region_model::handle_phi (const gphi *phi, tree lhs, tree rhs, const region_model &old_state, + hash_set &svals_changing_meaning, region_model_context *ctxt) { /* For now, don't bother tracking the .MEM SSA names. */ @@ -2247,6 +2263,10 @@ region_model::handle_phi (const gphi *phi, const svalue *src_sval = old_state.get_rvalue (rhs, ctxt); const region *dst_reg = old_state.get_lvalue (lhs, ctxt); + const svalue *sval = old_state.get_rvalue (lhs, nullptr); + if (sval->get_kind () == SK_WIDENING) + svals_changing_meaning.add (sval); + set_value (dst_reg, src_sval, ctxt); if (ctxt) @@ -4661,6 +4681,14 @@ region_model::add_constraint (tree lhs, enum tree_code op, tree rhs, return add_constraint (lhs_sval, op, rhs_sval, ctxt); } +static bool +unusable_in_infinite_loop_constraint_p (const svalue *sval) +{ + if (sval->get_kind () == SK_WIDENING) + return true; + return false; +} + /* Attempt to add the constraint "LHS OP RHS" to this region_model. If it is consistent with existing constraints, add it, and return true. Return false if it contradicts existing constraints. @@ -4672,6 +4700,20 @@ region_model::add_constraint (const svalue *lhs, const svalue *rhs, region_model_context *ctxt) { + const bool checking_for_infinite_loop + = ctxt ? ctxt->checking_for_infinite_loop_p () : false; + + if (checking_for_infinite_loop) + { + if (unusable_in_infinite_loop_constraint_p (lhs) + || unusable_in_infinite_loop_constraint_p (rhs)) + { + gcc_assert (ctxt); + ctxt->on_unusable_in_infinite_loop (); + return false; + } + } + tristate t_cond = eval_condition (lhs, op, rhs); /* If we already have the condition, do nothing. */ @@ -4683,6 +4725,15 @@ region_model::add_constraint (const svalue *lhs, if (t_cond.is_false ()) return false; + if (checking_for_infinite_loop) + { + /* Here, we don't have a definite true/false value, so bail out + when checking for infinite loops. */ + gcc_assert (ctxt); + ctxt->on_unusable_in_infinite_loop (); + return false; + } + bool out; if (add_constraints_from_binop (lhs, op, rhs, &out, ctxt)) return out; @@ -5068,6 +5119,8 @@ region_model::update_for_phis (const supernode *snode, are effectively handled simultaneously. */ const region_model old_state (*this); + hash_set svals_changing_meaning; + for (gphi_iterator gpi = const_cast(snode)->start_phis (); !gsi_end_p (gpi); gsi_next (&gpi)) { @@ -5077,8 +5130,11 @@ region_model::update_for_phis (const supernode *snode, tree lhs = gimple_phi_result (phi); /* Update next_state based on phi and old_state. */ - handle_phi (phi, lhs, src, old_state, ctxt); + handle_phi (phi, lhs, src, old_state, svals_changing_meaning, ctxt); } + + for (auto iter : svals_changing_meaning) + m_constraints->purge_state_involving (iter); } /* Attempt to update this model for taking EDGE (where the last statement @@ -5246,6 +5302,9 @@ region_model::replay_call_summary (call_summary_replay &r, m_store.replay_call_summary (r, summary.m_store); + if (r.get_ctxt ()) + r.get_ctxt ()->maybe_did_work (); + if (!m_constraints->replay_call_summary (r, *summary.m_constraints)) return false; @@ -5807,6 +5866,9 @@ region_model::can_merge_with_p (const region_model &other_model, *other_model.m_constraints, out_model->m_constraints); + for (auto iter : m.m_svals_changing_meaning) + out_model->m_constraints->purge_state_involving (iter); + return true; } @@ -6658,6 +6720,14 @@ model_merger::mergeable_svalue_p (const svalue *sval) const return true; } +/* Mark WIDENING_SVAL as changing meaning during the merge. */ + +void +model_merger::on_widening_reuse (const widening_svalue *widening_sval) +{ + m_svals_changing_meaning.add (widening_sval); +} + } // namespace ana /* Dump RMODEL fully to stderr (i.e. without summarization). */ @@ -8364,7 +8434,6 @@ test_iteration_1 () tree int_0 = build_int_cst (integer_type_node, 0); tree int_1 = build_int_cst (integer_type_node, 1); tree int_256 = build_int_cst (integer_type_node, 256); - tree int_257 = build_int_cst (integer_type_node, 257); tree i = build_global_decl ("i", integer_type_node); test_region_model_context ctxt; @@ -8426,8 +8495,6 @@ test_iteration_1 () ASSERT_TRUE (model5.can_merge_with_p (model2, point, &model6)); const svalue *merged_widening = model6.get_rvalue (i, &ctxt); ASSERT_EQ (merged_widening->get_kind (), SK_WIDENING); - - ASSERT_CONDITION_TRUE (model6, i, LT_EXPR, int_257); } /* Verify that if we mark a pointer to a malloc-ed region as non-NULL, diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index 4d8480df141..e26d18713b1 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -328,6 +328,7 @@ class region_model void handle_phi (const gphi *phi, tree lhs, tree rhs, const region_model &old_state, + hash_set &svals_changing_meaning, region_model_context *ctxt); bool maybe_update_for_edge (const superedge &edge, @@ -804,6 +805,11 @@ class region_model_context virtual const gimple *get_stmt () const = 0; virtual const exploded_graph *get_eg () const = 0; + + /* Hooks for detecting infinite loops. */ + virtual void maybe_did_work () = 0; + virtual bool checking_for_infinite_loop_p () const = 0; + virtual void on_unusable_in_infinite_loop () = 0; }; /* A "do nothing" subclass of region_model_context. */ @@ -861,6 +867,9 @@ public: const gimple *get_stmt () const override { return NULL; } const exploded_graph *get_eg () const override { return NULL; } + void maybe_did_work () override {} + bool checking_for_infinite_loop_p () const override { return false; } + void on_unusable_in_infinite_loop () override {} }; /* A subclass of region_model_context for determining if operations fail @@ -1036,6 +1045,24 @@ class region_model_context_decorator : public region_model_context return nullptr; } + void maybe_did_work () override + { + if (m_inner) + m_inner->maybe_did_work (); + } + + bool checking_for_infinite_loop_p () const override + { + if (m_inner) + return m_inner->checking_for_infinite_loop_p (); + return false; + } + void on_unusable_in_infinite_loop () override + { + if (m_inner) + m_inner->on_unusable_in_infinite_loop (); + } + protected: region_model_context_decorator (region_model_context *inner) : m_inner (inner) @@ -1108,6 +1135,8 @@ struct model_merger return m_point.get_function_point (); } + void on_widening_reuse (const widening_svalue *widening_sval); + const region_model *m_model_a; const region_model *m_model_b; const program_point &m_point; @@ -1116,6 +1145,8 @@ struct model_merger const extrinsic_state *m_ext_state; const program_state *m_state_a; const program_state *m_state_b; + + hash_set m_svals_changing_meaning; }; /* A record that can (optionally) be written out when diff --git a/gcc/analyzer/sm-signal.cc b/gcc/analyzer/sm-signal.cc index e3f90921df9..9ebcbdbc8e0 100644 --- a/gcc/analyzer/sm-signal.cc +++ b/gcc/analyzer/sm-signal.cc @@ -279,6 +279,7 @@ public: src_enode); if (dst_enode) eg->add_edge (src_enode, dst_enode, NULL, /*state_change (),*/ + true, /* assume does work */ make_unique ()); } diff --git a/gcc/analyzer/supergraph.cc b/gcc/analyzer/supergraph.cc index 31707e743a5..52cb8771de3 100644 --- a/gcc/analyzer/supergraph.cc +++ b/gcc/analyzer/supergraph.cc @@ -790,6 +790,13 @@ supernode::get_start_location () const if (return_p ()) return m_fun->function_end_locus; + /* We have no locations for stmts. If we have a single out-edge that's + a CFG edge, the goto_locus of that edge is a better location for this + than UNKNOWN_LOCATION. */ + if (m_succs.length () == 1) + if (const cfg_superedge *cfg_sedge = m_succs[0]->dyn_cast_cfg_superedge ()) + return cfg_sedge->get_goto_locus (); + return UNKNOWN_LOCATION; } @@ -813,6 +820,12 @@ supernode::get_end_location () const if (return_p ()) return m_fun->function_end_locus; + /* If we have a single out-edge that's a CFG edge, use the goto_locus of + that edge. */ + if (m_succs.length () == 1) + if (const cfg_superedge *cfg_sedge = m_succs[0]->dyn_cast_cfg_superedge ()) + return cfg_sedge->get_goto_locus (); + return UNKNOWN_LOCATION; } @@ -1063,6 +1076,9 @@ cfg_superedge::dump_label_to_pp (pretty_printer *pp, pp_string (pp, ")"); } + if (m_cfg_edge->goto_locus > BUILTINS_LOCATION) + pp_string (pp, " (has goto_locus)"); + /* Otherwise, no label. */ } diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h index 27ebd13feb2..0cafbb57234 100644 --- a/gcc/analyzer/supergraph.h +++ b/gcc/analyzer/supergraph.h @@ -532,6 +532,8 @@ class cfg_superedge : public superedge size_t get_phi_arg_idx () const; tree get_phi_arg (const gphi *phi) const; + location_t get_goto_locus () const { return m_cfg_edge->goto_locus; } + private: const ::edge m_cfg_edge; }; diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc index 35eb8307b20..e5811bd1395 100644 --- a/gcc/analyzer/svalue.cc +++ b/gcc/analyzer/svalue.cc @@ -251,6 +251,7 @@ svalue::can_merge_p (const svalue *other, a descending chain of constraints. */ if (other == widen_arg0) { + merger->on_widening_reuse (widen_arg0); return widen_arg0; } @@ -606,6 +607,12 @@ public: m_found = true; } + void visit_widening_svalue (const widening_svalue *candidate) final override + { + if (candidate == m_needle) + m_found = true; + } + bool found_p () const { return m_found; } private: @@ -620,7 +627,8 @@ svalue::involves_p (const svalue *other) const { /* Currently only implemented for these kinds. */ gcc_assert (other->get_kind () == SK_INITIAL - || other->get_kind () == SK_CONJURED); + || other->get_kind () == SK_CONJURED + || other->get_kind () == SK_WIDENING); involvement_visitor v (other); accept (&v); diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 1748afdbfe0..c0b571327fb 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -448,6 +448,7 @@ Objective-C and Objective-C++ Dialects}. -fdump-analyzer-exploded-nodes-3 -fdump-analyzer-exploded-paths -fdump-analyzer-feasibility +-fdump-analyzer-infinite-loop -fdump-analyzer-json -fdump-analyzer-state-purge -fdump-analyzer-stderr @@ -467,6 +468,7 @@ Objective-C and Objective-C++ Dialects}. -Wno-analyzer-file-leak -Wno-analyzer-free-of-non-heap -Wno-analyzer-imprecise-fp-arithmetic +-Wno-analyzer-infinite-loop -Wno-analyzer-infinite-recursion -Wno-analyzer-jump-through-null -Wno-analyzer-malloc-leak @@ -10401,6 +10403,7 @@ Enabling this option effectively enables the following warnings: -Wanalyzer-file-leak -Wanalyzer-free-of-non-heap -Wanalyzer-imprecise-fp-arithmetic +-Wanalyzer-infinite-loop -Wanalyzer-infinite-recursion -Wanalyzer-jump-through-null -Wanalyzer-malloc-leak @@ -10666,6 +10669,57 @@ arithmetic is used in locations where precise computation is needed. This diagnostic only warns on use of floating-point operands inside the calculation of an allocation size at the moment. +@opindex Wanalyzer-infinite-loop +@opindex Wno-analyzer-infinite-loop +@item -Wno-analyzer-infinite-loop +This warning requires @option{-fanalyzer}, which enables it; use +@option{-Wno-analyzer-infinite-loop} to disable it. + +This diagnostics warns for paths through the code which appear to +lead to an infinite loop. + +Specifically, the analyzer will issue this warning when it "sees" a loop +in which: +@itemize @bullet +@item +no externally-visible work could be being done within the loop +@item +there is no way to escape from the loop +@item +the analyzer is sufficiently confident about the program state +throughout the loop to know that the above are true +@end itemize + +One way for this warning to be emitted is when there is an execution +path through a loop for which taking the path on one iteration implies +that the same path will be taken on all subsequent iterations. + +For example, consider: + +@smallexample + while (1) + @{ + char opcode = *cpu_state.pc; + switch (opcode) + @{ + case OPCODE_FOO: + handle_opcode_foo (&cpu_state); + break; + case OPCODE_BAR: + handle_opcode_bar (&cpu_state); + break; + @} + @} +@end smallexample + +The analyzer will complain for the above case because if @code{opcode} +ever matches none of the cases, the @code{switch} will follow the +implicit @code{default} case, making the body of the loop be a ``no-op'' +with @code{cpu_state.pc} unchanged, and thus using the same value of +@code{opcode} on all subseqent iterations, leading to an infinite loop. + +See @uref{https://cwe.mitre.org/data/definitions/835.html, CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')}. + @opindex Wanalyzer-infinite-recursion @opindex Wno-analyzer-infinite-recursion @item -Wno-analyzer-infinite-recursion @@ -10690,6 +10744,8 @@ this diagnostic. Compare with @option{-Winfinite-recursion}, which provides a similar diagnostic, but is implemented in a different way. +See @uref{https://cwe.mitre.org/data/definitions/674.html, CWE-674: Uncontrolled Recursion}. + @opindex Wanalyzer-jump-through-null @opindex Wno-analyzer-jump-through-null @item -Wno-analyzer-jump-through-null @@ -11455,6 +11511,12 @@ The details are written in a form suitable for viewing with GraphViz to filenames of the form @file{@var{file}.*.fg.dot}, @file{@var{file}.*.tg.dot}, and @file{@var{file}.*.fpath.txt}. +@opindex dump-analyzer-infinite-loop +@item -fdump-analyzer-infinite-loop +Dump internal details about the analyzer's search for infinite loops. +The details are written in a form suitable for viewing with GraphViz +to filenames of the form @file{@var{file}.*.infinite-loop.dot}. + @opindex fdump-analyzer-json @item -fdump-analyzer-json Dump a compressed JSON representation of analyzer internals to diff --git a/gcc/testsuite/c-c++-common/analyzer/gzio-2.c b/gcc/testsuite/c-c++-common/analyzer/gzio-2.c index 855ecc8f73d..a0dd112b05d 100644 --- a/gcc/testsuite/c-c++-common/analyzer/gzio-2.c +++ b/gcc/testsuite/c-c++-common/analyzer/gzio-2.c @@ -6,6 +6,6 @@ void gzseek (long offset, int whence) offset -= 1; if (offset < 0) return; - while (offset > 0) { + while (offset > 0) { /* { dg-warning "infinite loop" "" { xfail *-*-* } } */ } } diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-2.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-2.c new file mode 100644 index 00000000000..f2825d606fa --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-2.c @@ -0,0 +1,34 @@ +extern int do_stuff (void); + +/* Various misleading "while" loops that look like do-whiles due + to proximity to another clause, but are actually empty. */ + +void not_a_do_while_1 (int flag) +{ + if (flag) { + do_stuff (); + flag = 0; + } while (flag); // TODO: should we complain here? +} + +void not_a_do_while_2 (int flag) +{ + if (!flag) { + do_stuff (); + flag = 1; + } while (flag); // TODO: should we complain here? +} + +void not_a_do_while_3 (int flag) +{ + while (!flag) { + flag = do_stuff (); + } while (flag); // TODO: should we complain here? +} + +void not_a_do_while_4 (int flag) +{ + while (flag) { + flag = do_stuff (); + } while (flag); // TODO: should we complain here? +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-4.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-4.c new file mode 100644 index 00000000000..032f7fd5860 --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-4.c @@ -0,0 +1,71 @@ +/* Various tests for loops that aren't infinite, strictly speaking, + but look bogus. */ + +// TODO: should we complain about these? + +extern int maybe_useful_work (); + +/* Loop iteration going the wrong way, with a signed iterator + + Not infinite, as will eventually overflow and bail out, but probably + not what the user intended. */ + +void test_wrong_way_signed_1 (int n) +{ + for (int i = 0; i < n; i--) + { + } +} + +void test_wrong_way_signed_2 (int n) +{ + for (int i = 0; i < n; i--) + maybe_useful_work (); +} + +int test_wrong_way_signed_3 (int *arr, int n) +{ + int sum = 0; + for (int i = 0; i < n; i--) + sum += arr[i]; + return sum; +} + + +/* As above, but with an unsigned iterator. + + Not infinite, as will immediately overflow and bail out, but probably + not what the user intended. */ + +void test_wrong_way_unsigned_1 (unsigned n) +{ + for (unsigned i = 0; i < n; i--) + { + } +} + +void test_wrong_way_unsigned_2 (unsigned n) +{ + for (unsigned i = 0; i < n; i--) + maybe_useful_work (); +} + +int test_wrong_way_unsigned_3 (int *arr, unsigned n) +{ + int sum = 0; + for (unsigned i = 0; i < n; i--) + sum += arr[i]; + return sum; +} + +/* BUG: "n" never changes, so loop is never entered. */ + +void test_1 (void) +{ + int n = 0; + + /* [...snip...] */ + + for (int i = 0; i < n; i++) + maybe_useful_work (); +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-crc32c.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-crc32c.c new file mode 100644 index 00000000000..01d4e4d91f9 --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-crc32c.c @@ -0,0 +1,14 @@ +/* Based on qemu's util/crc32c.c, in turn based on the + Linux kernel cryptographic crc32c module. */ + +#include + +extern const uint32_t crc32c_table[256]; + +uint32_t crc32c(uint32_t crc, const uint8_t *data, unsigned int length) +{ + while (length--) { /* { dg-bogus "infinite loop" } */ + crc = crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8); + } + return crc^0xffffffff; +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c new file mode 100644 index 00000000000..166d6da11f9 --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c @@ -0,0 +1,26 @@ +/* Reduced from a -Wanalyzer-infinite-loop false positive seen in Doom's + d_main.c, which is under the GPLv2 or later. */ + +extern char* wadfiles[20]; + +void +D_AddFile(const char* file) +{ + int numwadfiles; + char* newfile; + + for (numwadfiles = 0; wadfiles[numwadfiles]; numwadfiles++) /* { dg-bogus "infinite loop" } */ + ; + + newfile = (char *)__builtin_malloc(__builtin_strlen(file) + 1); + __builtin_strcpy(newfile, file); /* { dg-warning "possibly-NULL" } */ + + wadfiles[numwadfiles] = newfile; +} + +void +IdentifyVersion(void) +{ + D_AddFile("doom1.wad"); + D_AddFile("data_se/texture1.lmp"); +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-v_video.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-v_video.c new file mode 100644 index 00000000000..35f420655c4 --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-doom-v_video.c @@ -0,0 +1,31 @@ +/* Reduced from a -Wanalyzer-infinite-loop false positive seen in Doom's + v_video.c, which is under the GPLv2 or later. */ + +typedef unsigned char byte; + +byte* screens[5]; + +#define SCREENWIDTH 320 + +void +V_DrawBlock +( int x, + int y, + int scrn, + int width, + int height, + byte* src ) +{ + byte* dest; + + /* [...snip...] */ + + dest = screens[scrn] + y*SCREENWIDTH+x; + + while (height--) /* { dg-bogus "infinite loop" } */ + { + __builtin_memcpy (dest, src, width); + src += width; + dest += SCREENWIDTH; + } +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-g_error.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-g_error.c new file mode 100644 index 00000000000..5a267be0770 --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-g_error.c @@ -0,0 +1,19 @@ +/* Reduced from glib, which has a g_error macro with this infinite + loop in it: + for (;;) ; + + Make sure we provide a readable warning for this case. */ + +extern void g_log_structured_standard (const char *); + +#define g_error(MSG) \ + do { \ + g_log_structured_standard (MSG); \ + for (;;) ; \ + } while (0) +/* { dg-message "5: infinite loop" "" { target *-*-* } .-2 } */ + +void test_g_error (void) +{ + g_error ("something went wrong"); /* { dg-message "in expansion of macro 'g_error'" } */ +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-loop-linked-list.c b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-linked-list.c new file mode 100644 index 00000000000..aaa387fd310 --- /dev/null +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-loop-linked-list.c @@ -0,0 +1,131 @@ +/* Various correct and incorrect ways to walk a linked list, accumulating + a value. */ + +/* { dg-additional-options "-O0" } */ + +extern int maybe_useful_work (); + +struct node +{ + struct node *next; + int val; +}; + +/* Various "while" loops. */ + +int correct_while_loop (struct node *n) +{ + int sum = 0; + while (n) + { + sum += n->val; + n = n->next; + } + return sum; +} + +int while_loop_missing_next (struct node *n) +{ + int sum = 0; + while (n) /* { dg-line "while_loop_missing_next_WHILE_LINE" } */ + { + sum += n->val; /* { dg-line "while_loop_missing_next_LOOP_BODY" } */ + /* We're missing: "n = n->next;", so n does not change */ + } + return sum; + + /* { dg-warning "10: infinite loop" "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */ + /* { dg-message "10: \\(2\\) when 'n' is non-NULL: always following 'true' branch\.\.\." "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */ + /* { dg-message "\\(3\\) \.\.\.to here" "" { target *-*-* } while_loop_missing_next_LOOP_BODY } */ + /* { dg-message "\\(4\\) looping back\.\.\." "" { target *-*-* } while_loop_missing_next_LOOP_BODY } */ + /* { dg-message "\\(5\\) \.\.\.to here" "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */ +} + +int while_loop_missing_next_with_work (struct node *n) +{ + int sum = 0; + while (n) /* { dg-bogus "infinite loop" } */ + { + sum += n->val; + /* We're missing: "n = n->next;", so n does not change */ + /* But here we do something that could be doing useful work. */ + maybe_useful_work (); + } + return sum; +} + +/* BUG: missing: "sum += ", so sum does not change. */ + +int while_loop_missing_add (struct node *n) +{ + int sum = 0; + while (n) /* { dg-warning "infinite loop" } */ + n->val; + return sum; +} + +/* Various "for" loops. */ + +int correct_for_loop (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; iter = iter->next) + sum += n->val; + return sum; +} + +int for_loop_missing_condition (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; ; iter = iter->next) + sum += n->val; /* { dg-warning "infinite loop" } */ + return sum; +} + +int for_loop_missing_next (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; ) /* { dg-warning "infinite loop" } */ + sum += n->val; + return sum; +} + +/* BUG: missing: "sum += ", so sum does not change. + Not an infinite loop though, as we do iterate to the + end of the list. */ + +int for_loop_missing_add (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; iter = iter->next) + n->val; /* { dg-bogus "infinite loop" } */ + return sum; +} + +/* BUG: "iter->next" should be "iter = iter->next". */ + +int for_loop_noop_next (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; iter->next) /* { dg-line for_loop_noop_next_FOR_LINE } */ + sum += n->val; /* { dg-line for_loop_noop_next_LOOP_BODY } */ + return sum; + + /* { dg-warning "31: infinite loop" "" { target *-*-* } for_loop_noop_next_FOR_LINE } */ + /* { dg-message "31: \\(2\\) when 'iter' is non-NULL: always following 'true' branch\.\.\." "" { target *-*-* } for_loop_noop_next_FOR_LINE } */ + /* { dg-message "\\(3\\) \.\.\.to here" "" { target *-*-* } for_loop_noop_next_LOOP_BODY } */ + /* { dg-message "\\(4\\) looping back\.\.\." "" { target *-*-* } for_loop_noop_next_LOOP_BODY } */ + /* { dg-message "\\(5\\) \.\.\.to here" "" { target *-*-* } for_loop_noop_next_FOR_LINE } */ +} + +/* BUG: "iter = n->next" should be "iter = iter->next" + and so it becomes an infinite loop at the 2nd element. */ + +int for_loop_wrong_next (struct node *n) +{ + int sum = 0; + for (struct node *iter = n; iter; iter = n->next) /* { dg-warning "infinite loop" "" { xfail *-*-* } } */ + /* TODO: xfail. */ + sum += n->val; + return sum; +} diff --git a/gcc/testsuite/c-c++-common/analyzer/infinite-recursion-inlining.c b/gcc/testsuite/c-c++-common/analyzer/infinite-recursion-inlining.c index c885c922fe1..9dd5590acc0 100644 --- a/gcc/testsuite/c-c++-common/analyzer/infinite-recursion-inlining.c +++ b/gcc/testsuite/c-c++-common/analyzer/infinite-recursion-inlining.c @@ -11,13 +11,13 @@ void test_direct (void) { - test_direct (); /* Ideally would warn here, but it becomes an infinite loop. */ -} + test_direct (); +} /* { dg-warning "infinite-loop" } */ void test_guarded (int flag) { - if (flag) - test_guarded (flag); /* Ideally would warn here, but it becomes an infinite loop. */ + if (flag) /* { dg-warning "infinite-loop" } */ + test_guarded (flag); } void test_flipped_guard (int flag) @@ -34,7 +34,7 @@ void test_param_variant (int depth) void test_unguarded_param_variant (int depth) { - test_unguarded_param_variant (depth - 1); /* Ideally would warn here, but it becomes an infinite loop. */ + test_unguarded_param_variant (depth - 1); /* { dg-warning "infinite-loop" } */ } int g; @@ -90,27 +90,23 @@ int test_do_while_postdecrement_param (int n) /* Various cases of decrementing "n" as the recursion proceeds where not every path recurses, but we're not actually checking "n", so - if "flag" is true it's an infinite recursion. */ + if "flag" is true it's an infinite recursion (which looks like an + infinite loop after inlining). */ void test_partially_guarded_postdecrement (int flag, int n) { - /* Ideally we'd catch this, but it becomes an infinite loop. */ - if (flag) + if (flag) /* { dg-warning "infinite loop" } */ test_partially_guarded_postdecrement (flag, n--); } void test_partially_guarded_predecrement (int flag, int n) { - /* We fail to report this; we see that "n" is changing, - though it isn't relevant to whether we recurse. */ - if (flag) - test_partially_guarded_predecrement (flag, --n); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */ + if (flag) /* { dg-warning "infinite loop" } */ + test_partially_guarded_predecrement (flag, --n); } void test_partially_guarded_subtract (int flag, int n) { - /* We fail to report this; we see that "n" is changing, - though it isn't relevant to whether we recurse. */ - if (flag) - test_partially_guarded_subtract (flag, n - 1); /* { dg-warning "infinite recursion" "TODO" { xfail *-*-* } } */ + if (flag) /* { dg-warning "infinite loop" } */ + test_partially_guarded_subtract (flag, n - 1); } diff --git a/gcc/testsuite/c-c++-common/analyzer/inlining-4-multiline.c b/gcc/testsuite/c-c++-common/analyzer/inlining-4-multiline.c index c870a9f654d..5c971c581ae 100644 --- a/gcc/testsuite/c-c++-common/analyzer/inlining-4-multiline.c +++ b/gcc/testsuite/c-c++-common/analyzer/inlining-4-multiline.c @@ -56,13 +56,20 @@ outer (int flag) | | | (4) following 'true' branch (when 'flag != 0')... | + 'inner': event 5 (depth 3) + | + | + | #define NULL ((void *)0) + | ^ + | | + | (5) ...to here + { dg-end-multiline-output "" { target c } } */ +/* { dg-begin-multiline-output "" } + | return NULL; + | ^~~~ + | <-------------+ | - 'outer': event 5 (depth 1) - | - |cc1: - | (5): ...to here - | 'outer': event 6 (depth 1) | | return *middle (flag); @@ -100,13 +107,20 @@ outer (int flag) | | | (4) following 'true' branch (when 'flag != 0')... | + 'const char* inner(int)': event 5 (depth 3) + | + | + | #define NULL + | + | | + | (5) ...to here + { dg-end-multiline-output "" { target c++ } } */ +/* { dg-begin-multiline-output "" } + | return NULL; + | ^~~~ + | <-------------+ | - 'char outer(int)': event 5 (depth 1) - | - |cc1plus: - | (5): ...to here - | 'char outer(int)': event 6 (depth 1) | | return *middle (flag); diff --git a/gcc/testsuite/gcc.dg/analyzer/boxed-malloc-1.c b/gcc/testsuite/gcc.dg/analyzer/boxed-malloc-1.c index 435fb4f01c3..6b6bba338ae 100644 --- a/gcc/testsuite/gcc.dg/analyzer/boxed-malloc-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/boxed-malloc-1.c @@ -141,7 +141,7 @@ void test_12 (void) while (1) { - free (ptr.value); + free (ptr.value); /* { dg-warning "infinite loop" } */ free (ptr.value); /* { dg-warning "double-'free' of 'ptr.value'" } */ } } diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-20.c b/gcc/testsuite/gcc.dg/analyzer/data-model-20.c index ff65883dac1..59f62853ad6 100644 --- a/gcc/testsuite/gcc.dg/analyzer/data-model-20.c +++ b/gcc/testsuite/gcc.dg/analyzer/data-model-20.c @@ -14,7 +14,11 @@ test (int n) { for (i = 0; i < n; i++) { if ((arr[i] = (struct foo *)malloc(sizeof(struct foo))) == NULL) { - for (; i >= 0; i++) { + for (; i >= 0; i++) { /* { dg-warning "infinite loop" } */ + /* This loop is in the wrong direction, so not technically an + infinite loop ("i" will eventually wrap around), but the + analyzer's condition handling treats the overflow as such. + In any case, the code is suspect and warrants a warning. */ free(arr[i]); /* { dg-bogus "double-'free'" } */ } free(arr); /* { dg-warning "leak" } */ diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-20a.c b/gcc/testsuite/gcc.dg/analyzer/data-model-20a.c new file mode 100644 index 00000000000..767b9912ed9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/data-model-20a.c @@ -0,0 +1,25 @@ +/* { dg-additional-options "-Wno-analyzer-too-complex" } */ + +#include + +struct foo { int dummy; }; + +struct foo ** +test (int n) { + struct foo **arr; + int i; + + if ((arr = (struct foo **)malloc(n * sizeof(struct foo *))) == NULL) + return NULL; + + for (i = 0; i < n; i++) { + if ((arr[i] = (struct foo *)malloc(sizeof(struct foo))) == NULL) { + for (; i >= 0; i--) { + free(arr[i]); /* { dg-bogus "double-'free'" } */ + } + free(arr); /* { dg-bogus "leak" "" { xfail *-*-* } } */ + return NULL; + } + } + return arr; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/edges-1.c b/gcc/testsuite/gcc.dg/analyzer/edges-1.c index f08a6143d59..644a2df8daf 100644 --- a/gcc/testsuite/gcc.dg/analyzer/edges-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/edges-1.c @@ -15,6 +15,8 @@ void test_1 (const char *path, int flag) if (!fp) /* { dg-message "when 'fp' is non-NULL" } */ return; + bar (); + /* We shouldn't report this control flow. */ while (foo ()) /* { dg-bogus "" } */ bar (); diff --git a/gcc/testsuite/gcc.dg/analyzer/explode-2a.c b/gcc/testsuite/gcc.dg/analyzer/explode-2a.c index 32c71ca44aa..d07ce5b270a 100644 --- a/gcc/testsuite/gcc.dg/analyzer/explode-2a.c +++ b/gcc/testsuite/gcc.dg/analyzer/explode-2a.c @@ -14,7 +14,7 @@ void test (void) explode-2.c as this code. */ int a = get (); int b = get (); - while (a) + while (a) /* { dg-warning "infinite loop" } */ { switch (b) { diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-loop-1.c b/gcc/testsuite/gcc.dg/analyzer/infinite-loop-1.c new file mode 100644 index 00000000000..c3515bb140a --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-loop-1.c @@ -0,0 +1,235 @@ +/* { dg-additional-options "-O0" } */ + +extern int maybe_useful_work (); + +int global_var; +volatile int volatile_global_var; + +struct st +{ + int x; + int y; +}; + +static void __attribute__((noinline)) +do_nothing (void) +{ +} + +void test_empty_while_true () +{ + while (1) {} /* { dg-warning "infinite loop" } */ + /* { dg-message "looping back\.\.\." "" { target *-*-* } .-1 } */ + /* { dg-message "\.\.\.to here" "" { target *-*-* } .-2 } */ +} + +void test_empty_do_while () +{ + do {} while (1); /* { dg-warning "infinite loop" } */ + /* { dg-message "looping back\.\.\." "" { target *-*-* } .-1 } */ + /* { dg-message "\.\.\.to here" "" { target *-*-* } .-2 } */ +} + +void test_empty_for () +{ + for (;;) {} /* { dg-warning "infinite loop" } */ + /* { dg-message "looping back\.\.\." "" { target *-*-* } .-1 } */ + /* { dg-message "\.\.\.to here" "" { target *-*-* } .-2 } */ +} + +void test_while_true_maybe_useful_work () +{ + while (1) + maybe_useful_work (); +} + +void test_while_true_interproc_empty () +{ + /* Depending on optimization level, location is sometimes + on "while", sometimes on "do_nothing", and sometimes the + unknown location. */ + while (1) + do_nothing (); /* { dg-warning "infinite loop" } */ +} + +void test_while_true_increment_local () +{ + int i = 0; + while (1) + i++; /* { dg-warning "infinite loop" } */ +} + +void test_while_true_increment_global () +{ + while (1) + global_var++; +} + +void test_guarded_while_true_increment_local (int flag) +{ + if (flag) + { + int i = 0; + while (1) + i++; /* { dg-warning "infinite loop" } */ + } +} + +void test_while_local_flag_increment_local (int flag) +{ + int i = 0; + while (flag) /* { dg-warning "infinite loop" } */ + i++; +} + +extern int check_flag (void); + +void test_while_calling_fn (void) +{ + while (check_flag ()) + do_nothing (); +} + +void test_missing_parens_on_call (void) +{ + while (check_flag) + do_nothing (); /* { dg-warning "infinite loop" } */ +} + +void test_iteration_copy_and_paste_error (int m, int n) +{ + /* Wrong variable is incremented in inner "for" loop, thus + effectively an infinite loop. */ + float arr[m][n]; + for (int i = 0; i < m; i++) + for (int j = 0; j < n; i++) /* { dg-warning "infinite loop" } */ + arr[i][j] = 0.f; +} + +void test_missing_comparison_in_for_condition_1 (int n) +{ + /* Should have been "i < n", rather than just "n". */ + for (int i = 0; n; i++) /* { dg-warning "infinite loop" } */ + { + } +} + +int test_missing_comparison_in_for_condition_2 (int val, int *arr, int n) +{ + /* Should have been "i < n", rather than just "n". */ + int acc = 0; + for (int i = 0; n; i++) /* { dg-warning "infinite loop" } */ + acc += arr[i]; + return acc; +} + +void test_non_volatile_local_1 (void) +{ + int flag = 0; + while (!flag) /* { dg-warning "infinite loop" } */ + { + } +} + +void test_non_volatile_local_2a (void) +{ + int flag = 0; + + /* Perhaps should complain about this. + Although the infinite loop might be doing useful work, + "while (!flag)" is a misleading way to spell "infinite loop". */ + while (!flag) + maybe_useful_work (); +} + +void test_non_volatile_local_2b (void) +{ + int flag = 0; + + while (!flag) + flag = maybe_useful_work (); +} + +void test_non_volatile_local_3a (int n) +{ + int i = 0; + + /* Perhaps should complain about this. + Although the infinite loop might be doing useful work, + "while (i < n)" is a misleading way to spell "infinite loop". */ + while (i < n) + maybe_useful_work (); +} + +void test_non_volatile_local_3b (int n) +{ + int i = 0; + + while (i < n) + { + maybe_useful_work (); + i++; + } +} + +void test_volatile_local (void) +{ + volatile int flag = 0; + while (!flag) /* { dg-bogus "infinite loop" } */ + { + } +} + +void test_non_volatile_global (void) +{ + /* Not sure if we should warn here. */ + while (!global_var) /* { dg-warning "infinite loop" } */ + { + } +} + +void test_volatile_global (void) +{ + while (!volatile_global_var) /* { dg-bogus "infinite loop" } */ + { + } +} + +void test_field_1 (struct st *p) +{ + /* Not sure if we should warn here. */ + while (!p->x) /* { dg-warning "infinite loop" } */ + { + } +} + +void test_field_2 (struct st *p) +{ + while (!p->x) /* { dg-bogus "infinite loop" } */ + maybe_useful_work (); +} + + +int missing_init_of_i (int *arr, unsigned n) +{ + int sum = 0; + for (int i; i < n; i--) /* { dg-warning "use of uninitialized value 'i'" } */ + sum += arr[i]; + return sum; +} + +void test_switch (char *pc) +{ + while (1) + { + char opcode = *pc; /* { dg-warning "infinite loop" } */ + switch (opcode) /* { dg-message "if it ever follows 'default:' branch, it will always do so\.\.\." } */ + { + case 'A': + pc++; + break; + case 'B': + return; + } + } +} diff --git a/gcc/testsuite/gcc.dg/analyzer/malloc-1.c b/gcc/testsuite/gcc.dg/analyzer/malloc-1.c index 6b5590a433a..2a42a05fb9e 100644 --- a/gcc/testsuite/gcc.dg/analyzer/malloc-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/malloc-1.c @@ -124,7 +124,7 @@ void test_12 (void) while (1) { - free (ptr); + free (ptr); /* { dg-warning "infinite loop" } */ free (ptr); /* { dg-warning "double-'free' of 'ptr'" } */ } } diff --git a/gcc/testsuite/gcc.dg/analyzer/out-of-bounds-coreutils.c b/gcc/testsuite/gcc.dg/analyzer/out-of-bounds-coreutils.c index cd0f4b7f7b2..7af4c3794aa 100644 --- a/gcc/testsuite/gcc.dg/analyzer/out-of-bounds-coreutils.c +++ b/gcc/testsuite/gcc.dg/analyzer/out-of-bounds-coreutils.c @@ -3,7 +3,7 @@ void add_zero_terminator (char *buf) { char *end = buf; - while (end++); + while (end++); /* TODO: arguably we should report this. */ if (buf < end) end[-1] = '\0'; } diff --git a/gcc/testsuite/gcc.dg/analyzer/paths-4.c b/gcc/testsuite/gcc.dg/analyzer/paths-4.c index b72e658739e..60b3a0cfd2a 100644 --- a/gcc/testsuite/gcc.dg/analyzer/paths-4.c +++ b/gcc/testsuite/gcc.dg/analyzer/paths-4.c @@ -26,9 +26,10 @@ int test_2 (struct state *s) while (1) { __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enode" } */ + /* { dg-warning "infinite loop" "" { target *-*-* } .-1 } */ __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enode" } */ /* TODO: why does the above need an extra stmt to merge state? */ - switch (s->mode) + switch (s->mode) /* { dg-message "if it ever follows 'default:' branch, it will always do so\.\.\." } */ { case 0: __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enode" } */ diff --git a/gcc/testsuite/gcc.dg/analyzer/pr103892.c b/gcc/testsuite/gcc.dg/analyzer/pr103892.c index 95d4b17d18b..d16cd83c472 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr103892.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr103892.c @@ -38,7 +38,7 @@ typedef struct pipecmd_sequence pipecmd_sequence_t; static char *argstr_get_word (const char **argstr) { - while (**argstr) { + while (**argstr) { /* { dg-warning "infinite loop" } */ switch (**argstr) { case ' ': case '\t': diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93546.c b/gcc/testsuite/gcc.dg/analyzer/pr93546.c index 66f6805b07a..07898e9bde5 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr93546.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr93546.c @@ -5,7 +5,7 @@ void ch (int x1) { ({ bx: &&bx; }); - while (x1 == 0) + while (x1 == 0) /* { dg-warning "infinite loop" } */ { } } diff --git a/gcc/timevar.def b/gcc/timevar.def index d21b08c030d..9628223a436 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -342,6 +342,7 @@ DEFTIMEVAR (TV_ANALYZER_STATE_PURGE , "analyzer: state purge") DEFTIMEVAR (TV_ANALYZER_PLAN , "analyzer: planning") DEFTIMEVAR (TV_ANALYZER_SCC , "analyzer: scc") DEFTIMEVAR (TV_ANALYZER_WORKLIST , "analyzer: processing worklist") +DEFTIMEVAR (TV_ANALYZER_INFINITE_LOOPS, "analyzer: finding infinite loops") DEFTIMEVAR (TV_ANALYZER_DUMP , "analyzer: dump") DEFTIMEVAR (TV_ANALYZER_DIAGNOSTICS , "analyzer: emitting diagnostics") DEFTIMEVAR (TV_ANALYZER_SHORTEST_PATHS, "analyzer: shortest paths")