From patchwork Wed May 24 06:46:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1785554 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=w1YPRUUn; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QR1vY42xJz20Q0 for ; Wed, 24 May 2023 16:47:21 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 89D053858414 for ; Wed, 24 May 2023 06:47:19 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 89D053858414 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684910839; bh=Ufbl16y5TX3L8LMnC39RO7tI/Zv4IFkPiqCU44Ra6sc=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=w1YPRUUnnYgCh9hrGFPuc8gVRRZzNPyo3WdShA2qMJlPOhxJX7Ikbw0mWfhPTDsoq JTRXQuMnV75jW1NOPRprLmflqit2CEJpJJX3bzF3LrSDtdTdtwIkaHXPvJ1voKjucf fTTCl4RWf5fgeoPs16wbLsvrpvJs3YEn6VU+gM50= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id 8BE523858C54 for ; Wed, 24 May 2023 06:46:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8BE523858C54 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 31059113E; Tue, 23 May 2023 23:47:44 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.110.72]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id A7AC53F840; Tue, 23 May 2023 23:46:58 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, rguenther@suse.de, richard.sandiford@arm.com Cc: rguenther@suse.de Subject: [PATCH] early-remat: Resync with new DF postorders [PR109940] Date: Wed, 24 May 2023 07:46:57 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-28.8 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, 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 Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" When I wrote early-remat, the DF_FORWARD block order was a postorder of a reverse/backward walk (i.e. of the inverted cfg), rather than a reverse postorder of a forward walk. A postorder of a backward walk lacked the important property that dominators come before the blocks they dominate; instead it ensures that postdominators come after the blocks that they postdominate. The DF_BACKWARD block order was similarly a postorder of a forward walk. Since early-remat wanted a standard postorder and reverse postorder with normal dominator properties, it used the DF_BACKWARD order instead of the DF_FORWARD order. g:53dddbfeb213ac4ec39f fixed the DF orders so that DF_FORWARD was an RPO of a forward walk and so that DF_BACKWARD was an RPO of a backward walk. This meant that iterating backwards over the DF_BACKWARD order had the exact problem that the original DF_FORWARD order had, triggering a flurry of ICEs for SVE. This fixes the build with SVE enabled. It also fixes an ICE in g++.target/aarch64/sve/pr99766.C with normal builds. I've included the test from the PR as well, for extra coverage. Tested on aarch64-linux-gnu and aarch64_be-elf. OK to install? Richard gcc/ PR rtl-optimization/109940 * early-remat.cc (postorder_index): Rename to... (rpo_index): ...this. (compare_candidates): Sort by decreasing rpo_index rather than increasing postorder_index. (early_remat::sort_candidates): Calculate the forward RPO from DF_FORWARD. (early_remat::local_phase): Follow forward RPO using DF_FORWARD, rather than DF_BACKWARD in reverse. gcc/testsuite/ * gcc.dg/torture/pr109940.c: New test. --- gcc/early-remat.cc | 28 ++++++++++++------------- gcc/testsuite/gcc.dg/torture/pr109940.c | 18 ++++++++++++++++ 2 files changed, 32 insertions(+), 14 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr109940.c diff --git a/gcc/early-remat.cc b/gcc/early-remat.cc index b76771eaf0d..1ee63c73c1b 100644 --- a/gcc/early-remat.cc +++ b/gcc/early-remat.cc @@ -1010,8 +1010,8 @@ early_remat::init_block_info (void) m_block_info.safe_grow_cleared (n_blocks, true); } -/* Maps basic block indices to their position in the post order. */ -static unsigned int *postorder_index; +/* Maps basic block indices to their position in the forward RPO. */ +static unsigned int *rpo_index; /* Order remat_candidates X_IN and Y_IN according to the cfg postorder. */ @@ -1024,7 +1024,7 @@ compare_candidates (const void *x_in, const void *y_in) basic_block y_bb = BLOCK_FOR_INSN (y->insn); if (x_bb != y_bb) /* Make X and Y follow block postorder. */ - return postorder_index[x_bb->index] - postorder_index[y_bb->index]; + return rpo_index[y_bb->index] - rpo_index[x_bb->index]; /* Make X and Y follow a backward traversal of the containing block. */ return DF_INSN_LUID (y->insn) - DF_INSN_LUID (x->insn); @@ -1051,15 +1051,15 @@ early_remat::sort_candidates (void) /* Create a mapping from block numbers to their position in the postorder. */ unsigned int n_blocks = last_basic_block_for_fn (m_fn); - int *postorder = df_get_postorder (DF_BACKWARD); - unsigned int postorder_len = df_get_n_blocks (DF_BACKWARD); - postorder_index = new unsigned int[n_blocks]; - for (unsigned int i = 0; i < postorder_len; ++i) - postorder_index[postorder[i]] = i; + int *rpo = df_get_postorder (DF_FORWARD); + unsigned int rpo_len = df_get_n_blocks (DF_FORWARD); + rpo_index = new unsigned int[n_blocks]; + for (unsigned int i = 0; i < rpo_len; ++i) + rpo_index[rpo[i]] = i; m_candidates.qsort (compare_candidates); - delete[] postorder_index; + delete[] rpo_index; } /* Commit to the current candidate indices and initialize cross-references. */ @@ -2097,11 +2097,11 @@ early_remat::local_phase (void) if (dump_file) fprintf (dump_file, "\n;; Local phase:\n"); - int *postorder = df_get_postorder (DF_BACKWARD); - unsigned int postorder_len = df_get_n_blocks (DF_BACKWARD); - for (unsigned int i = postorder_len; i-- > 0; ) - if (postorder[i] >= NUM_FIXED_BLOCKS) - process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i])); + int *rpo = df_get_postorder (DF_FORWARD); + unsigned int rpo_len = df_get_n_blocks (DF_FORWARD); + for (unsigned int i = 0; i < rpo_len; ++i) + if (rpo[i] >= NUM_FIXED_BLOCKS) + process_block (BASIC_BLOCK_FOR_FN (m_fn, rpo[i])); } /* Return true if available values survive across edge E. */ diff --git a/gcc/testsuite/gcc.dg/torture/pr109940.c b/gcc/testsuite/gcc.dg/torture/pr109940.c new file mode 100644 index 00000000000..23364708e86 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr109940.c @@ -0,0 +1,18 @@ +/* { dg-additional-options "-march=armv9-a" { target aarch64*-*-* } } */ + +int a; +int *b; +void +c (int *d) { *d = a; } + +int +e(int d, int f) { + if (d <= 1) + return 1; + int g = d / 2; + for (int h = 0; h < g; h++) + if (f == (long int)b > b[h]) + c(&b[h]); + e(g, f); + e(g, f); +}