From patchwork Wed Jul 24 11:57:20 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1964263 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=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 [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 (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WTXZp2h3Fz1yZw for ; Wed, 24 Jul 2024 21:57:54 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1A1283858410 for ; Wed, 24 Jul 2024 11:57:52 +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 A82F83858D28 for ; Wed, 24 Jul 2024 11:57:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A82F83858D28 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 A82F83858D28 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=1721822244; cv=none; b=kmFBh0WdyW7BFojwEcUn3ai5MwgD4qZgcE2qDumo9wIub03oVvwvPyAsXvlIxQEqwmO6Q9azOcz3UgBLis9isjKfHSiDO31P0l4dbrQebseS+3ZhlGgqj6YbxuT6KydkuUyVpS7GKBwPoctmJQbNR1hK/Jke26vO58wVEqBOte4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1721822244; c=relaxed/simple; bh=MT7NXF1B+MwEcclFvYJyzEqQvgiyjw//M2zHE5gE/bM=; h=From:To:Subject:Date:Message-ID:MIME-Version; b=bBlMwDk11ew5WTAMlDLqgOYAGFDtZKBs2FdJIfBgXk8EsryxiA8qvysIstuWfTxiVoodEBvTdjfZtXPnAqY2ZnLNN5NZtXxXfT59xsV/jHokXjsQ8cy6sFvDwnvVdkFYNVT0qYin7jiAwye2gpz6Fnj955HOGPICk5/9MrpluHs= 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 EA7CB106F for ; Wed, 24 Jul 2024 04:57:47 -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 146863F5A1 for ; Wed, 24 Jul 2024 04:57:21 -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 tree insertion [PR116044] Date: Wed, 24 Jul 2024 12:57:20 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 X-Spam-Status: No, score=-19.3 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 PR116044 is a regression in the testsuite on AMD GCN caused (again) by the split_clobber_group code. The first patch in this area (g:71b31690a7c52413496e91bcc5ee4c68af2f366f) fixed a bug caused by carrying the old group over as one the split ones. That patch instead: - created two new groups - inserted them in the splay tree as neighbours of the old group - removed the old group, and - invalidated the old group (to force lazy recomputation when a clobber's parent group is queried) However, this left add_def trying to insert the new definition relative to a stale splay tree root. The second patch (g:34f33ea801563e2eabb348e8d3e9344a91abfd48) attempted to fix that by inserting it relative to the new root. But that's not always correct either. We specifically want to insert it after the first of the two new groups, whether that group is the root or not. This patch does that, and tries to refactor the code to make it a bit less brittle. Bootstrapped & regression-tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? Sorry for all the trouble that this code has caused :-( Richard gcc/ PR rtl-optimization/116044 * rtl-ssa/accesses.h (function_info::split_clobber_group): Return an array of two clobber_groups. * rtl-ssa/accesses.cc (function_info::split_clobber_group): Return the new clobber groups. Don't modify the splay tree here. (function_info::add_def): Update call accordingly. Generalize the splay tree insertion code so that the new definition can be inserted as a child of any existing node, not just the root. Fix the insertion used after calling split_clobber_group. --- gcc/rtl-ssa/accesses.cc | 66 +++++++++++++++++++++++------------------ gcc/rtl-ssa/functions.h | 3 +- 2 files changed, 39 insertions(+), 30 deletions(-) diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc index 0bba8391b00..5450ea118d1 100644 --- a/gcc/rtl-ssa/accesses.cc +++ b/gcc/rtl-ssa/accesses.cc @@ -792,12 +792,12 @@ function_info::merge_clobber_groups (clobber_info *clobber1, } // GROUP spans INSN, and INSN now sets the resource that GROUP clobbers. -// Split GROUP around INSN, to form two new groups, and return the clobber -// that comes immediately before INSN. +// Split GROUP around INSN, to form two new groups. The first of the +// returned groups comes before INSN and the second comes after INSN. // -// The resource that GROUP clobbers is known to have an associated -// splay tree. The caller must remove GROUP from the tree on return. -clobber_info * +// The caller is responsible for updating the def_splay_tree and chaining +// the defs together. +std::array function_info::split_clobber_group (clobber_group *group, insn_info *insn) { // Search for either the previous or next clobber in the group. @@ -835,14 +835,10 @@ function_info::split_clobber_group (clobber_group *group, insn_info *insn) 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 (group, 1, group2); - def_splay_tree::insert_child (group, 1, group1); - // Invalidate the old group. group->set_last_clobber (nullptr); - return prev; + return { group1, group2 }; } // Add DEF to the end of the function's list of definitions of @@ -899,7 +895,7 @@ function_info::add_def (def_info *def) insn_info *insn = def->insn (); int comparison; - def_node *root = nullptr; + def_node *neighbor = nullptr; def_info *prev = nullptr; def_info *next = nullptr; if (*insn > *last->insn ()) @@ -909,8 +905,8 @@ function_info::add_def (def_info *def) if (def_splay_tree tree = last->splay_root ()) { tree.splay_max_node (); - root = tree.root (); - last->set_splay_root (root); + last->set_splay_root (tree.root ()); + neighbor = tree.root (); } prev = last; } @@ -921,8 +917,8 @@ function_info::add_def (def_info *def) if (def_splay_tree tree = last->splay_root ()) { tree.splay_min_node (); - root = tree.root (); - last->set_splay_root (root); + last->set_splay_root (tree.root ()); + neighbor = tree.root (); } next = first; } @@ -931,8 +927,8 @@ function_info::add_def (def_info *def) // Search the splay tree for an insertion point. def_splay_tree tree = need_def_splay_tree (last); comparison = lookup_def (tree, insn); - root = tree.root (); - last->set_splay_root (root); + last->set_splay_root (tree.root ()); + neighbor = tree.root (); // Deal with cases in which we found an overlapping live range. if (comparison == 0) @@ -943,22 +939,34 @@ function_info::add_def (def_info *def) add_clobber (clobber, group); return; } - prev = split_clobber_group (group, insn); - next = prev->next_def (); + auto new_groups = split_clobber_group (group, insn); + + // Insert the two new groups immediately after GROUP. + def_splay_tree::insert_child (group, 1, new_groups[1]); + def_splay_tree::insert_child (group, 1, new_groups[0]); + + // Remove GROUP. tree.remove_root (); - root = tree.root (); - last->set_splay_root (root); + last->set_splay_root (tree.root ()); + + prev = new_groups[0]->last_clobber (); + next = new_groups[1]->first_clobber (); + + // DEF comes after the first group. (new_groups[1] and -1 would + // also work.) + neighbor = new_groups[0]; + comparison = 1; } - // COMPARISON is < 0 if DEF comes before ROOT or > 0 if DEF comes - // after ROOT. + // COMPARISON is < 0 if DEF comes before NEIGHBOR or > 0 if DEF comes + // after NEIGHBOR. else if (comparison < 0) { - next = first_def (root); + next = first_def (neighbor); prev = next->prev_def (); } else { - prev = last_def (root); + prev = last_def (neighbor); next = prev->next_def (); } } @@ -973,12 +981,12 @@ function_info::add_def (def_info *def) append_clobber_to_group (clobber, need_clobber_group (prev_clobber)); else if (clobber && next_clobber) prepend_clobber_to_group (clobber, need_clobber_group (next_clobber)); - else if (root) + else if (neighbor) { - // If DEF comes before ROOT, insert DEF to ROOT's left, - // otherwise insert DEF to ROOT's right. + // If DEF comes before NEIGHBOR, insert DEF to NEIGHBOR's left, + // otherwise insert DEF to NEIGHBOR's right. def_node *node = need_def_node (def); - def_splay_tree::insert_child (root, comparison >= 0, node); + def_splay_tree::insert_child (neighbor, comparison >= 0, node); } if (prev) insert_def_after (def, prev); diff --git a/gcc/rtl-ssa/functions.h b/gcc/rtl-ssa/functions.h index 8be04f1aa96..567701c7995 100644 --- a/gcc/rtl-ssa/functions.h +++ b/gcc/rtl-ssa/functions.h @@ -257,7 +257,8 @@ private: void append_clobber_to_group (clobber_info *, clobber_group *); void merge_clobber_groups (clobber_info *, clobber_info *, def_info *); - clobber_info *split_clobber_group (clobber_group *, insn_info *); + std::array split_clobber_group (clobber_group *, + insn_info *); void append_def (def_info *); void add_def (def_info *);