From patchwork Tue Jul 16 14:24:23 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1961100 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=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WNhDw3lQ1z1xrK for ; Wed, 17 Jul 2024 00:25:36 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4F422384A056 for ; Tue, 16 Jul 2024 14:25:34 +0000 (GMT) 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 26096384A056 for ; Tue, 16 Jul 2024 14:24:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 26096384A056 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 26096384A056 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=217.140.110.172 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1721139867; cv=none; b=OjLI/xx3Ievgtocbpm5SC5qiCz5N9B01RtWMenZs9B+mlFPIzZ70AJymFVrpr/efPStdmq1yE5VRLC1y6hwMD4X1vDRYq0XfD3FVjhl2M5PZjAaQKnA5QewCAeHf4w1vcjCFMb0MzKacyyRPqfkVn7+PU2UTNJ7hsfEcD31X8kE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1721139867; c=relaxed/simple; bh=xZk/25mEJMoS2FWCSf6Y6M5MekG6G20sMslprC9t1f4=; h=From:To:Subject:Date:Message-ID:MIME-Version; b=xoQ8DXN6hA5zpDq3JM6jZsb8vx/Njf8BuFwjKzqDtwn3WkVC3HsmNxyubAgMwZWLu/sDkYKnK8ujA4o9A5yMSMJRI0usGf1EnS4M86GaQK9Ykg59PEew0ogeL5kAt054LZNpP01h4Bozy8ufaImwohDA5qMTqbg275D6uV64+Lk= ARC-Authentication-Results: i=1; server2.sourceware.org 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 234971063 for ; Tue, 16 Jul 2024 07:24:50 -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 6EF0F3F762 for ; Tue, 16 Jul 2024 07:24:24 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH] rtl-ssa: Fix split_clobber_group [PR115928] Date: Tue, 16 Jul 2024 15:24:23 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 X-Spam-Status: No, score=-19.4 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 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~incoming=patchwork.ozlabs.org@gcc.gnu.org One of the goals of the rtl-ssa representation was to allow a group of consecutive clobbers to be skipped in constant time, with amortised sublinear insertion and deletion. This involves putting consecutive clobbers in groups. Splitting or joining groups would be linear if we had to update every clobber on each update, so the operation to query a clobber's group is lazy and (again) amortised sublinear. This means that, when splitting a group into two, we cannot reuse the old group for one side. We have to invalidate it, so that the lazy clobber_info::group query can tell that something has changed. The ICE in the PR came from failing to do that. Tested on aarch64-linux-gnu & x86_64-linux-gnu. OK to install? Richard gcc/ PR rtl-optimization/115928 * rtl-ssa/accesses.h (clobber_group): Add a new constructor that takes the first, last and root clobbers. * rtl-ssa/internals.inl (clobber_group::clobber_group): Define it. * rtl-ssa/accesses.cc (function_info::split_clobber_group): Use it. Allocate a new group for both sides and invalidate the previous group. (function_info::add_def): After calling split_clobber_group, remove the old group from the splay tree. gcc/testsuite/ PR rtl-optimization/115928 * gcc.dg/torture/pr115928.c: New test. --- gcc/rtl-ssa/accesses.cc | 37 +++++++++++-------------- gcc/rtl-ssa/accesses.h | 3 +- gcc/rtl-ssa/internals.inl | 14 ++++++++++ gcc/testsuite/gcc.dg/torture/pr115928.c | 23 +++++++++++++++ 4 files changed, 55 insertions(+), 22 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr115928.c diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc index 3f1304fc5bf..5cc05cb4be7 100644 --- a/gcc/rtl-ssa/accesses.cc +++ b/gcc/rtl-ssa/accesses.cc @@ -792,11 +792,11 @@ function_info::merge_clobber_groups (clobber_info *clobber1, } // GROUP spans INSN, and INSN now sets the resource that GROUP clobbers. -// Split GROUP around INSN and return the clobber that comes immediately -// before INSN. +// Split GROUP around INSN, to form two new groups, and return the clobber +// that comes immediately before INSN. // // The resource that GROUP clobbers is known to have an associated -// splay tree. +// splay tree. The caller must remove GROUP from the tree on return. clobber_info * function_info::split_clobber_group (clobber_group *group, insn_info *insn) { @@ -827,27 +827,20 @@ function_info::split_clobber_group (clobber_group *group, insn_info *insn) prev = as_a (next->prev_def ()); } - // Use GROUP to hold PREV and earlier clobbers. Create a new group for - // NEXT onwards. + // Create a new group for each side of the split. We need to invalidate + // the old group so that clobber_info::group can tell whether a lazy + // update is needed. + clobber_info *first_clobber = group->first_clobber (); clobber_info *last_clobber = group->last_clobber (); - clobber_group *group1 = group; - clobber_group *group2 = allocate (next); - - // Finish setting up GROUP1, making sure that the roots and extremities - // have a correct group pointer. Leave the rest to be updated lazily. - group1->set_last_clobber (prev); - tree1->set_group (group1); - prev->set_group (group1); - - // Finish setting up GROUP2, with the same approach as for GROUP1. - group2->set_first_clobber (next); - group2->set_last_clobber (last_clobber); - next->set_group (group2); - tree2->set_group (group2); - last_clobber->set_group (group2); + auto *group1 = allocate (first_clobber, prev, tree1.root ()); + auto *group2 = allocate (next, last_clobber, tree2.root ()); // Insert GROUP2 into the splay tree as an immediate successor of GROUP1. - def_splay_tree::insert_child (group1, 1, group2); + def_splay_tree::insert_child (group, 1, group2); + def_splay_tree::insert_child (group, 1, group1); + + // Invalidate the old group. + group->set_last_clobber (nullptr); return prev; } @@ -952,6 +945,8 @@ function_info::add_def (def_info *def) } prev = split_clobber_group (group, insn); next = prev->next_def (); + tree.remove_root (); + last->set_splay_root (tree.root ()); } // COMPARISON is < 0 if DEF comes before ROOT or > 0 if DEF comes // after ROOT. diff --git a/gcc/rtl-ssa/accesses.h b/gcc/rtl-ssa/accesses.h index 7d2916d00c2..27810a02063 100644 --- a/gcc/rtl-ssa/accesses.h +++ b/gcc/rtl-ssa/accesses.h @@ -937,7 +937,8 @@ public: void print (pretty_printer *pp) const; private: - clobber_group (clobber_info *clobber); + clobber_group (clobber_info *); + clobber_group (clobber_info *, clobber_info *, clobber_info *); // Set the values of first_clobber () and last_clobber (). void set_first_clobber (clobber_info *c) { m_clobber_or_set = c; } diff --git a/gcc/rtl-ssa/internals.inl b/gcc/rtl-ssa/internals.inl index c736877479e..9bc40bf35c5 100644 --- a/gcc/rtl-ssa/internals.inl +++ b/gcc/rtl-ssa/internals.inl @@ -380,6 +380,20 @@ inline clobber_group::clobber_group (clobber_info *clobber) clobber->m_group = this; } +// Construct a new group of clobber_infos that spans [FIRST_CLOBBER, +// LAST_CLOBBER]. Set the root of the splay tree to CLOBBER_TREE. +inline clobber_group::clobber_group (clobber_info *first_clobber, + clobber_info *last_clobber, + clobber_info *clobber_tree) + : def_node (first_clobber), + m_last_clobber (last_clobber), + m_clobber_tree (clobber_tree) +{ + first_clobber->m_group = this; + last_clobber->m_group = this; + clobber_tree->m_group = this; +} + // Construct a node for the instruction with uid UID. inline insn_info::order_node::order_node (int uid) : insn_note (kind), diff --git a/gcc/testsuite/gcc.dg/torture/pr115928.c b/gcc/testsuite/gcc.dg/torture/pr115928.c new file mode 100644 index 00000000000..4379fa968ad --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr115928.c @@ -0,0 +1,23 @@ +/* { dg-additional-options "-fgcse-sm" } */ + +int a[1], b, c; +struct { + int d; + int e; + int : 8; +} f[1]; +static int g; +char h, i, j; +void k(int l) { b = 5 ^ a[b ^ (l & 5)]; } +void m(long l) { k(c >> 6); } +int main() { + g++; + if (b) { + h = 5 && j; + if (h) + h -= i; + m(f[g].d); + m(f[g].e); + } + return 0; +}