From patchwork Thu Aug 18 14:05:44 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 604 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:6a10:38f:b0:2d5:3c95:9e21 with SMTP id 15csp302167pxh; Thu, 18 Aug 2022 07:07:08 -0700 (PDT) X-Google-Smtp-Source: AA6agR6ZiL+SPoLgFAp6a57N544aztr+o6IDpKOr/CIQS3Ap+iTMMowkTmOczzx+BOYkzuI0Xp63 X-Received: by 2002:a17:906:974b:b0:733:10e:b940 with SMTP id o11-20020a170906974b00b00733010eb940mr2038109ejy.326.1660831628140; Thu, 18 Aug 2022 07:07:08 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1660831628; cv=none; d=google.com; s=arc-20160816; b=GMO3nJZlaLJ3TzwtR3eWlYryAkoSFgUZrkkWSREkMPYmczBTdzZVb08ZqkFu6UifQ7 QYnpHl5Kyvqa5htLMe9JWXHkO2gNXM4PAnjs2biMwnb31846CHE2QPu68NZ2KgzNTHEx yGdx+opX/CKSrCYzC+T7OiN1bOObzIWmd6DMze+jaITSY2IUaX8oBnl3apQ1vrdVx7is h0qPZRVb+egx9n32PiPy81bpLnGYKVRe7vb8asHC4QFQ+xfhrHPfHKFWpxJOzYA6JrTF iZcY3MbuXfXR12CvYjeZsE96RJdKFtJy9ukeZjfKk4KPbY3UN2uUGDJVieOStXiX1t7t EAcA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=message-id:sender:errors-to:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :mime-version:user-agent:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=jq7r6tSZVaI2tjxpjJLwe/0L9I/4uTSHJIv/7tc08mI=; b=GvDJg5SGmcdZYq3JC+CKXCV+P9g8oRCJSHRWGJ3yBaeTs4iJivSC2y68IG6yt/7qBv QRgRh1x1P2+I42UPyUfMsAo3MGbnzXHcanyWcSgp16WDOsIofUNmXpVatVLuPAL+L11l 4ZepfHfO9pswkZgveUMsH42J0z4pqJT1ugCVxOHnL5dS+jzzouUoQPJUeEtL413Guv1p XCjv3PPGTw6vZXk6xC/g5BDkTy8a3WHxs7YNyguDOpU5N3T/vUkKjlNYZQtEu6u6uac8 YQb+69AZZPVRllsWQpMap3MyikvkEV5kSxKcxtop6FoC3HGWcS+EFt6pOeGbE2f3wxhR XfhQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=QM+oRGbF; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id du8-20020a17090772c800b0072b4b8a0ce7si1182156ejc.946.2022.08.18.07.07.07 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 18 Aug 2022 07:07:08 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=QM+oRGbF; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id ECB923858413 for ; Thu, 18 Aug 2022 14:07:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org ECB923858413 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1660831627; bh=jq7r6tSZVaI2tjxpjJLwe/0L9I/4uTSHJIv/7tc08mI=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=QM+oRGbFXexzmS5hA//TWv2hovIQMB300ic2UlW4GqLxvMAP8CIYNPy1w0eXC3UBQ /l8H5A2dms533e9i4qGC73MVUOS89aMSihe33uezQlRZvaUfl0E1VdGx2idki2ttP5 44QaTFIlcB3n66PnGJYPWbd2fXsM3S1NYH5xNxL4= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 36CD7385843E for ; Thu, 18 Aug 2022 14:05:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 36CD7385843E Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 696043F171 for ; Thu, 18 Aug 2022 14:05:44 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 5A39A2C184 for ; Thu, 18 Aug 2022 14:05:44 +0000 (UTC) Date: Thu, 18 Aug 2022 14:05:44 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Improve uninit analysis User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" Message-Id: <20220818140706.ECB923858413@sourceware.org> X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1741508185182093042?= X-GMAIL-MSGID: =?utf-8?q?1741508185182093042?= The following reduces the number of false positives in uninit analysis by providing fallback for situations the current analysis gives up and thus warns because it cannot prove initialization. The first situation is when compute_control_dep_chain gives up walking because it runs into either param_uninit_control_dep_attempts or MAX_CHAIN_LEN. If in the process it did not collect a single path from function entry to the interesting PHI edge then we'll give up and diagnose. The following patch insteads provides a sparse path including only those predicates that always hold when the PHI edge is reached in that case. That's cheap to produce but may in some odd cases prove less precise than what the code tries now (enumerating all possible paths from function entry to the PHI edge, but only use the first N of those and only require unreachability of those N). The second situation is when the set of predicates computed to hold on the use stmt was formed from multiple paths (there's a similar enumeration of all paths and their predicates from the PHI def to the use). In that case use_preds.use_cannot_happen gives up because it doesn't know which of the predicates from which path from PHI to the use it can use to prove unreachability of the PHI edge that has the uninitialized def. The patch for this case simply computes the intersection of the predicates and uses that for further analysis, but in a crude way since the predicate vectors are not sorted. Fortunately the total size is limited - we have max MAX_NUM_CHAINS number of predicates each of length MAX_CHAIN_LEN so the brute force intersection code should behave quite reasonable in practice. Bootstrap and regtest running on x86_64-unknown-linux-gnu. The testcase that made me produce this is tree-ssa-math-opts.cc compiled with the backward jump threading limit increased by a factor of two, so I don't have any testcase, not even one with some --param adjustment (because that also affects DOM). * gimple-predicate-analysis.cc (predicate::use_cannot_happen): If the use is guarded with multiple predicate paths compute the predicates intersection before going forward. When compute_control_dep_chain wasn't able to come up with at least one path from function entry to the PHI edge compute a conservative sparse path instead. --- gcc/gimple-predicate-analysis.cc | 64 ++++++++++++++++++++++++++++---- 1 file changed, 56 insertions(+), 8 deletions(-) diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc index b8221d3fb8d..820a9bde28a 100644 --- a/gcc/gimple-predicate-analysis.cc +++ b/gcc/gimple-predicate-analysis.cc @@ -40,6 +40,7 @@ #include "builtins.h" #include "calls.h" #include "value-query.h" +#include "cfganal.h" #include "gimple-predicate-analysis.h" @@ -1224,13 +1225,36 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds) /* PHI_USE_GUARDS are OR'ed together. If we have more than one possible guard, there's no way of knowing which guard was true. - Since we need to be absolutely sure that the uninitialized - operands will be invalidated, bail. */ + In that case compute the intersection of all use predicates + and use that. */ const pred_chain_union &phi_use_guards = m_preds; + const pred_chain *use_guard = &phi_use_guards[0]; + pred_chain phi_use_guard_intersection = vNULL; if (phi_use_guards.length () != 1) - return false; - - const pred_chain &use_guard = phi_use_guards[0]; + { + phi_use_guard_intersection = use_guard->copy (); + for (unsigned i = 1; i < phi_use_guards.length (); ++i) + { + for (unsigned j = 0; j < phi_use_guard_intersection.length ();) + { + unsigned k; + for (k = 0; k < phi_use_guards[i].length (); ++k) + if (pred_equal_p (phi_use_guards[i][k], + phi_use_guard_intersection[j])) + break; + if (k == phi_use_guards[i].length ()) + phi_use_guard_intersection.unordered_remove (j); + else + j++; + } + } + if (phi_use_guard_intersection.is_empty ()) + { + phi_use_guard_intersection.release (); + return false; + } + use_guard = &phi_use_guard_intersection; + } /* Look for the control dependencies of all the interesting operands and build guard predicates describing them. */ @@ -1250,7 +1274,27 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds) if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun), e->src, dep_chains, &num_chains, cur_chain, &num_calls)) - return false; + { + gcc_assert (num_chains == 0); + /* If compute_control_dep_chain bailed out due to limits + build a partial sparse path using dominators. Collect + only edges whose predicates are always true when reaching E. */ + cur_chain.truncate (0); + cur_chain.quick_push (e); + basic_block src = e->src; + while (src->index != ENTRY_BLOCK + && cur_chain.length () <= MAX_CHAIN_LEN) + { + basic_block dest = src; + src = get_immediate_dominator (CDI_DOMINATORS, src); + edge pred_e; + if (single_pred_p (dest) + && (pred_e = find_edge (src, dest))) + cur_chain.quick_push (pred_e); + } + dep_chains[0] = cur_chain.copy (); + num_chains++; + } if (DEBUG_PREDICATE_ANALYZER && dump_file) { @@ -1272,10 +1316,14 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds) /* Can the guard for this PHI argument be negated by the one guarding the PHI use? */ - if (!can_be_invalidated_p (def_preds.chain (), use_guard)) - return false; + if (!can_be_invalidated_p (def_preds.chain (), *use_guard)) + { + phi_use_guard_intersection.release (); + return false; + } } + phi_use_guard_intersection.release (); return true; }