From patchwork Fri Apr 1 11:08:32 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 52567 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 610183945C3C for ; Fri, 1 Apr 2022 11:09:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 610183945C3C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1648811343; bh=z/R8Rg3CeQCXxkdtUZIWujjqu1v0mX6KtjihH2RN8ds=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=cIhD0BWFq3CKhntpGQNvUmxz8c2mwF4vIya+oxqqlI5mDca8RYdJnwpmo12B+N8OS QrZ4TnpleIWcZAc2OWiRdsxkvSXKUMQADOQXr0DVmw4N44ZVYG9wOR5L6+iAX1Qx29 fS3bJ0hJma+PZi8494NitBdakO/M634s/T81Roys= 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 EFDAC3858D28 for ; Fri, 1 Apr 2022 11:08:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EFDAC3858D28 Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id A191921612; Fri, 1 Apr 2022 11:08:32 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 84869132C1; Fri, 1 Apr 2022 11:08:32 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id Mbf9HjDdRmKgDwAAMHmgww (envelope-from ); Fri, 01 Apr 2022 11:08:32 +0000 Date: Fri, 1 Apr 2022 13:08:32 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/100810 - avoid undefs in IVOPT rewrites MIME-Version: 1.0 Message-Id: <20220401110832.84869132C1@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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 Cc: bin.cheng@linux.alibaba.com, roger@nextmovesoftware.com Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The following attempts to avoid IVOPTs rewriting uses using IV candidates that involve undefined behavior by using uninitialized SSA names. First we restrict the set of candidates we produce for such IVs to the original ones and mark them as not important. Second we try to only allow expressing uses with such IV if they originally use them. That is to avoid rewriting all such uses in terms of other IVs. Since cand->iv and use->iv seem to never exactly match up we resort to comparing the IV bases. The approach ends up similar to the one posted by Roger at https://gcc.gnu.org/pipermail/gcc-patches/2021-August/578441.html but it marks IV candidates rather than use groups and the cases we allow in determine_group_iv_cost_generic are slightly different. Bootstrapped and tested on x86_64-unknown-linux-gnu. OK for trunk? Thanks, Richard. 2022-01-04 Richard Biener PR tree-optimization/100810 * tree-ssa-loop-ivopts.cc (struct iv_cand): Add involves_undefs flag. (find_ssa_undef): New function. (add_candidate_1): Avoid adding derived candidates with undefined SSA names and mark the original ones. (determine_group_iv_cost_generic): Reject rewriting uses with a different IV when that involves undefined SSA names. * gcc.dg/torture/pr100810.c: New testcase. --- gcc/testsuite/gcc.dg/torture/pr100810.c | 34 +++++++++++++++++++++++++ gcc/tree-ssa-loop-ivopts.cc | 31 ++++++++++++++++++++++ 2 files changed, 65 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/torture/pr100810.c diff --git a/gcc/testsuite/gcc.dg/torture/pr100810.c b/gcc/testsuite/gcc.dg/torture/pr100810.c new file mode 100644 index 00000000000..63566f530f7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr100810.c @@ -0,0 +1,34 @@ +/* { dg-do run } */ + +int a, b = 1, c = 1, e, f = 1, g, h, j; +volatile int d; +static void k() +{ + int i; + h = b; + if (c && a >= 0) { + while (a) { + i++; + h--; + } + if (g) + for (h = 0; h < 2; h++) + ; + if (!b) + i &&d; + } +} +static void l() +{ + for (; j < 1; j++) + if (!e && c && f) + k(); +} +int main() +{ + if (f) + l(); + if (h != 1) + __builtin_abort(); + return 0; +} diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc index 935d2d4d8f3..b0305c494cd 100644 --- a/gcc/tree-ssa-loop-ivopts.cc +++ b/gcc/tree-ssa-loop-ivopts.cc @@ -452,6 +452,7 @@ struct iv_cand unsigned id; /* The number of the candidate. */ bool important; /* Whether this is an "important" candidate, i.e. such that it should be considered by all uses. */ + bool involves_undefs; /* Whether the IV involves undefined values. */ ENUM_BITFIELD(iv_position) pos : 8; /* Where it is computed. */ gimple *incremented_at;/* For original biv, the statement where it is incremented. */ @@ -3068,6 +3069,19 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr) return *slot; } +/* Find the first undefined SSA name in *TP. */ + +static tree +find_ssa_undef (tree *tp, int *walk_subtrees, void *) +{ + if (TREE_CODE (*tp) == SSA_NAME + && ssa_undefined_value_p (*tp, false)) + return *tp; + if (!EXPR_P (*tp)) + *walk_subtrees = 0; + return NULL; +} + /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and position to POS. If USE is not NULL, the candidate is set as related to it. If both BASE and STEP are NULL, we add a pseudocandidate for the @@ -3095,6 +3109,17 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important, if (flag_keep_gc_roots_live && POINTER_TYPE_P (TREE_TYPE (base))) return NULL; + /* If BASE contains undefined SSA names make sure we only record + the original IV. */ + bool involves_undefs = false; + if (walk_tree (&base, find_ssa_undef, NULL, NULL)) + { + if (pos != IP_ORIGINAL) + return NULL; + important = false; + involves_undefs = true; + } + /* For non-original variables, make sure their values are computed in a type that does not invoke undefined behavior on overflows (since in general, we cannot prove that these induction variables are non-wrapping). */ @@ -3143,6 +3168,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important, cand->var_after = cand->var_before; } cand->important = important; + cand->involves_undefs = involves_undefs; cand->incremented_at = incremented_at; cand->doloop_p = doloop; data->vcands.safe_push (cand); @@ -4956,6 +4982,11 @@ determine_group_iv_cost_generic (struct ivopts_data *data, the candidate. */ if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt) cost = no_cost; + /* If the IV candidate involves undefined SSA values and is not the + same IV as on the USE avoid using that candidate here. */ + else if (cand->involves_undefs + && (!use->iv || !operand_equal_p (cand->iv->base, use->iv->base, 0))) + return false; else cost = get_computation_cost (data, use, cand, false, &inv_vars, NULL, &inv_expr);