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: 56858 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B98A23858C52 for ; Thu, 18 Aug 2022 14:06:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B98A23858C52 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1660831611; 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=jnFGUMS42MJ3FG0ed9LTZdD579DRIbJe6DhYcBOIvfj2yo/EvMTnO9DEvhq5WzAVU X2mzoC7OVtct0IaKdPY9ipZ5fXcFUHC9MeSGlGvxY3qP+w/97MyWofqoouph/mM1Wy AdHi94iNf7q6B65fgfzIOmwsK+cxjJWBHnOel2Bg= 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+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Message-Id: <20220818140651.B98A23858C52@sourceware.org> 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; }