From patchwork Sun Sep 26 11:09:34 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Leoshkevich X-Patchwork-Id: 1532957 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: 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=n27hLzOG; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4HHNP74Lk7z9t1s for ; Sun, 26 Sep 2021 21:11:07 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2C6D4385801A for ; Sun, 26 Sep 2021 11:11:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2C6D4385801A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632654663; bh=QWUW8wimGrqZuqwW7BM0TvP7Ai2ygk2wxaK8baFo38c=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=n27hLzOGSdmgYcY/EUlSh0uNepn7ZtisyyUsOn+ylcZNYjDkB/56bZUIW5IlHreGq 2iKlrQjVYZ2SB18wCLU1W96KAN+cCEGUKo0c4eXwzFgvPXfCAEV9+qPLXU+Uecswz0 3FnhR81NKMLEJvMd1HLgVITcIXng5h3MbpHUEbW4= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id 228593858404; Sun, 26 Sep 2021 11:09:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 228593858404 Received: from pps.filterd (m0098409.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18Q9bB1X023100; Sun, 26 Sep 2021 07:09:44 -0400 Received: from ppma04ams.nl.ibm.com (63.31.33a9.ip4.static.sl-reverse.com [169.51.49.99]) by mx0a-001b2d01.pphosted.com with ESMTP id 3bagua5d7n-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Sun, 26 Sep 2021 07:09:43 -0400 Received: from pps.filterd (ppma04ams.nl.ibm.com [127.0.0.1]) by ppma04ams.nl.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 18QB3OXH009024; Sun, 26 Sep 2021 11:09:41 GMT Received: from b06cxnps4076.portsmouth.uk.ibm.com (d06relay13.portsmouth.uk.ibm.com [9.149.109.198]) by ppma04ams.nl.ibm.com with ESMTP id 3b9ud95ds6-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Sun, 26 Sep 2021 11:09:41 +0000 Received: from d06av26.portsmouth.uk.ibm.com (d06av26.portsmouth.uk.ibm.com [9.149.105.62]) by b06cxnps4076.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 18QB9cDv23724468 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sun, 26 Sep 2021 11:09:38 GMT Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 3399AAE07B; Sun, 26 Sep 2021 11:09:38 +0000 (GMT) Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id D155FAE087; Sun, 26 Sep 2021 11:09:37 +0000 (GMT) Received: from vm.lan (unknown [9.145.45.184]) by d06av26.portsmouth.uk.ibm.com (Postfix) with ESMTP; Sun, 26 Sep 2021 11:09:37 +0000 (GMT) To: Richard Biener Subject: [PATCH v3 1/3] reassoc: Do not bias loop-carried PHIs early Date: Sun, 26 Sep 2021 13:09:34 +0200 Message-Id: <20210926110936.344019-2-iii@linux.ibm.com> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20210926110936.344019-1-iii@linux.ibm.com> References: <20210926110936.344019-1-iii@linux.ibm.com> MIME-Version: 1.0 X-TM-AS-GCONF: 00 X-Proofpoint-ORIG-GUID: 4jVbMcGK60LH_1EwXvNcwTVZU7LxzEyX X-Proofpoint-GUID: 4jVbMcGK60LH_1EwXvNcwTVZU7LxzEyX X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.790,Hydra:6.0.391,FMLib:17.0.607.475 definitions=2021-09-26_03,2021-09-24_02,2020-04-07_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 priorityscore=1501 clxscore=1011 phishscore=0 bulkscore=0 adultscore=0 lowpriorityscore=0 impostorscore=0 mlxscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2109260078 X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP 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: Ilya Leoshkevich via Gcc-patches From: Ilya Leoshkevich Reply-To: Ilya Leoshkevich Cc: Andreas Krebbel , gcc-patches@gcc.gnu.org Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Biasing loop-carried PHIs during the 1st reassociation pass interferes with reduction chains and does not bring measurable benefits, so do it only during the 2nd reassociation pass. gcc/ChangeLog: * passes.def (pass_reassoc): Rename parameter to early_p. * tree-ssa-reassoc.c (reassoc_bias_loop_carried_phi_ranks_p): New variable. (phi_rank): Don't bias loop-carried phi ranks before vectorization pass. (execute_reassoc): Add bias_loop_carried_phi_ranks_p parameter. (pass_reassoc::pass_reassoc): Add bias_loop_carried_phi_ranks_p initializer. (pass_reassoc::set_param): Set bias_loop_carried_phi_ranks_p value. (pass_reassoc::execute): Pass bias_loop_carried_phi_ranks_p to execute_reassoc. (pass_reassoc::bias_loop_carried_phi_ranks_p): New member. --- gcc/passes.def | 4 ++-- gcc/tree-ssa-reassoc.c | 16 ++++++++++++++-- 2 files changed, 16 insertions(+), 4 deletions(-) diff --git a/gcc/passes.def b/gcc/passes.def index d7a1f8c97a6..c5f915d04c6 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -242,7 +242,7 @@ along with GCC; see the file COPYING3. If not see /* Identify paths that should never be executed in a conforming program and isolate those paths. */ NEXT_PASS (pass_isolate_erroneous_paths); - NEXT_PASS (pass_reassoc, true /* insert_powi_p */); + NEXT_PASS (pass_reassoc, true /* early_p */); NEXT_PASS (pass_dce); NEXT_PASS (pass_forwprop); NEXT_PASS (pass_phiopt, false /* early_p */); @@ -325,7 +325,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_lower_vector_ssa); NEXT_PASS (pass_lower_switch); NEXT_PASS (pass_cse_reciprocals); - NEXT_PASS (pass_reassoc, false /* insert_powi_p */); + NEXT_PASS (pass_reassoc, false /* early_p */); NEXT_PASS (pass_strength_reduction); NEXT_PASS (pass_split_paths); NEXT_PASS (pass_tracer); diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 8498cfc7aa8..420c14e8cf5 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -180,6 +180,10 @@ along with GCC; see the file COPYING3. If not see point 3a in the pass header comment. */ static bool reassoc_insert_powi_p; +/* Enable biasing ranks of loop accumulators. We don't want this before + vectorization, since it interferes with reduction chains. */ +static bool reassoc_bias_loop_carried_phi_ranks_p; + /* Statistics */ static struct { @@ -269,6 +273,9 @@ phi_rank (gimple *stmt) use_operand_p use; gimple *use_stmt; + if (!reassoc_bias_loop_carried_phi_ranks_p) + return bb_rank[bb->index]; + /* We only care about real loops (those with a latch). */ if (!father->latch) return bb_rank[bb->index]; @@ -6940,9 +6947,10 @@ fini_reassoc (void) optimization of a gimple conditional. Otherwise returns zero. */ static unsigned int -execute_reassoc (bool insert_powi_p) +execute_reassoc (bool insert_powi_p, bool bias_loop_carried_phi_ranks_p) { reassoc_insert_powi_p = insert_powi_p; + reassoc_bias_loop_carried_phi_ranks_p = bias_loop_carried_phi_ranks_p; init_reassoc (); @@ -6983,15 +6991,19 @@ public: { gcc_assert (n == 0); insert_powi_p = param; + bias_loop_carried_phi_ranks_p = !param; } virtual bool gate (function *) { return flag_tree_reassoc != 0; } virtual unsigned int execute (function *) - { return execute_reassoc (insert_powi_p); } + { + return execute_reassoc (insert_powi_p, bias_loop_carried_phi_ranks_p); + } private: /* Enable insertion of __builtin_powi calls during execute_reassoc. See point 3a in the pass header comment. */ bool insert_powi_p; + bool bias_loop_carried_phi_ranks_p; }; // class pass_reassoc } // anon namespace From patchwork Sun Sep 26 11:09:35 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Leoshkevich X-Patchwork-Id: 1532958 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: 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=ef8uDk9G; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4HHNQb6Vf5z9t1s for ; Sun, 26 Sep 2021 21:12:23 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9E49B3858403 for ; Sun, 26 Sep 2021 11:12:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9E49B3858403 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632654741; bh=DRff1XODAm1vYXWBqjgEaS/6Vn8palAJPS9mvDlnhUk=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=ef8uDk9GoNVkvwxLI1VrVO8K1pooNtNkX61o8Yh+uUM8a2e5owQR8VvWj/u8GoezL ebUNolhE+9tNzhV4JaJuBwsSKxPb6RQ5OP3NfuQvOEvThEtoZoJCH8mjy8NOVWCZaJ G2f53qNQNW2U3HzuQJiEWKJj4E+Tj19lOe4II0Ps= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id 389393858409; Sun, 26 Sep 2021 11:09:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 389393858409 Received: from pps.filterd (m0098409.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18Q9PXvs022949; Sun, 26 Sep 2021 07:09:45 -0400 Received: from ppma04fra.de.ibm.com (6a.4a.5195.ip4.static.sl-reverse.com [149.81.74.106]) by mx0a-001b2d01.pphosted.com with ESMTP id 3bagua5d7s-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Sun, 26 Sep 2021 07:09:44 -0400 Received: from pps.filterd (ppma04fra.de.ibm.com [127.0.0.1]) by ppma04fra.de.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 18QB3AJ8013505; Sun, 26 Sep 2021 11:09:42 GMT Received: from b06avi18878370.portsmouth.uk.ibm.com (b06avi18878370.portsmouth.uk.ibm.com [9.149.26.194]) by ppma04fra.de.ibm.com with ESMTP id 3b9ud9cyyk-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Sun, 26 Sep 2021 11:09:42 +0000 Received: from d06av26.portsmouth.uk.ibm.com (d06av26.portsmouth.uk.ibm.com [9.149.105.62]) by b06avi18878370.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 18QB4eoQ48300528 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sun, 26 Sep 2021 11:04:40 GMT Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id EA000AE07B; Sun, 26 Sep 2021 11:09:38 +0000 (GMT) Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 91E11AE087; Sun, 26 Sep 2021 11:09:38 +0000 (GMT) Received: from vm.lan (unknown [9.145.45.184]) by d06av26.portsmouth.uk.ibm.com (Postfix) with ESMTP; Sun, 26 Sep 2021 11:09:38 +0000 (GMT) To: Richard Biener Subject: [PATCH v3 2/3] reassoc: Propagate PHI_LOOP_BIAS along single uses Date: Sun, 26 Sep 2021 13:09:35 +0200 Message-Id: <20210926110936.344019-3-iii@linux.ibm.com> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20210926110936.344019-1-iii@linux.ibm.com> References: <20210926110936.344019-1-iii@linux.ibm.com> MIME-Version: 1.0 X-TM-AS-GCONF: 00 X-Proofpoint-ORIG-GUID: VPTcq_o0HW30_Wvrt2RYoiN9EpKSag9h X-Proofpoint-GUID: VPTcq_o0HW30_Wvrt2RYoiN9EpKSag9h X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.790,Hydra:6.0.391,FMLib:17.0.607.475 definitions=2021-09-26_03,2021-09-24_02,2020-04-07_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 priorityscore=1501 clxscore=1015 phishscore=0 bulkscore=0 adultscore=0 lowpriorityscore=0 impostorscore=0 mlxscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2109260078 X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP 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: Ilya Leoshkevich via Gcc-patches From: Ilya Leoshkevich Reply-To: Ilya Leoshkevich Cc: Andreas Krebbel , gcc-patches@gcc.gnu.org Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" PR tree-optimization/49749 introduced code that shortens dependency chains containing loop accumulators by placing them last on operand lists of associative operations. 456.hmmer benchmark on s390 could benefit from this, however, the code that needs it modifies loop accumulator before using it, and since only so-called loop-carried phis are are treated as loop accumulators, the code in the present form doesn't really help. According to Bill Schmidt - the original author - such a conservative approach was chosen so as to avoid unnecessarily swapping operands, which might cause unpredictable effects. However, giving special treatment to forms of loop accumulators is acceptable. The definition of loop-carried phi is: it's a single-use phi, which is used in the same innermost loop it's defined in, at least one argument of which is defined in the same innermost loop as the phi itself. Given this, it seems natural to treat single uses of such phis as phis themselves. gcc/ChangeLog: * tree-ssa-reassoc.c (biased_names): New global. (propagate_bias_p): New function. (loop_carried_phi): Remove. (propagate_rank): Propagate bias along single uses. (get_rank): Update biased_names when needed. --- gcc/tree-ssa-reassoc.c | 109 ++++++++++++++++++++++++++++------------- 1 file changed, 74 insertions(+), 35 deletions(-) diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 420c14e8cf5..db9fb4e1cac 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -211,6 +211,10 @@ static int64_t *bb_rank; /* Operand->rank hashtable. */ static hash_map *operand_rank; +/* SSA_NAMEs that are forms of loop accumulators and whose ranks need to be + biased. */ +static auto_bitmap biased_names; + /* Vector of SSA_NAMEs on which after reassociate_bb is done with all basic blocks the CFG should be adjusted - basic blocks split right after that SSA_NAME's definition statement and before @@ -256,6 +260,53 @@ reassoc_remove_stmt (gimple_stmt_iterator *gsi) the rank difference between two blocks. */ #define PHI_LOOP_BIAS (1 << 15) +/* Return TRUE iff PHI_LOOP_BIAS should be propagated from one of the STMT's + operands to the STMT's left-hand side. The goal is to preserve bias in code + like this: + + x_1 = phi(x_0, x_2) + a = x_1 | 1 + b = a ^ 2 + .MEM = b + c = b + d + x_2 = c + e + + That is, we need to preserve bias along single-use chains originating from + loop-carried phis. Only GIMPLE_ASSIGNs to SSA_NAMEs are considered to be + uses, because only they participate in rank propagation. */ +static bool +propagate_bias_p (gimple *stmt) +{ + use_operand_p use; + imm_use_iterator use_iter; + gimple *single_use_stmt = NULL; + + if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_reference) + return false; + + FOR_EACH_IMM_USE_FAST (use, use_iter, gimple_assign_lhs (stmt)) + { + gimple *current_use_stmt = USE_STMT (use); + + if (is_gimple_assign (current_use_stmt) + && TREE_CODE (gimple_assign_lhs (current_use_stmt)) == SSA_NAME) + { + if (single_use_stmt != NULL && single_use_stmt != current_use_stmt) + return false; + single_use_stmt = current_use_stmt; + } + } + + if (single_use_stmt == NULL) + return false; + + if (gimple_bb (stmt)->loop_father + != gimple_bb (single_use_stmt)->loop_father) + return false; + + return true; +} + /* Rank assigned to a phi statement. If STMT is a loop-carried phi of an innermost loop, and the phi has only a single use which is inside the loop, then the rank is the block rank of the loop latch plus an @@ -313,49 +364,27 @@ phi_rank (gimple *stmt) return bb_rank[bb->index]; } -/* If EXP is an SSA_NAME defined by a PHI statement that represents a - loop-carried dependence of an innermost loop, return TRUE; else - return FALSE. */ -static bool -loop_carried_phi (tree exp) -{ - gimple *phi_stmt; - int64_t block_rank; - - if (TREE_CODE (exp) != SSA_NAME - || SSA_NAME_IS_DEFAULT_DEF (exp)) - return false; - - phi_stmt = SSA_NAME_DEF_STMT (exp); - - if (gimple_code (SSA_NAME_DEF_STMT (exp)) != GIMPLE_PHI) - return false; - - /* Non-loop-carried phis have block rank. Loop-carried phis have - an additional bias added in. If this phi doesn't have block rank, - it's biased and should not be propagated. */ - block_rank = bb_rank[gimple_bb (phi_stmt)->index]; - - if (phi_rank (phi_stmt) != block_rank) - return true; - - return false; -} - /* Return the maximum of RANK and the rank that should be propagated from expression OP. For most operands, this is just the rank of OP. For loop-carried phis, the value is zero to avoid undoing the bias in favor of the phi. */ static int64_t -propagate_rank (int64_t rank, tree op) +propagate_rank (int64_t rank, tree op, bool *maybe_biased_p) { int64_t op_rank; - if (loop_carried_phi (op)) - return rank; - op_rank = get_rank (op); + /* Check whether op is biased after the get_rank () call, since it might have + updated biased_names. */ + if (TREE_CODE (op) == SSA_NAME + && bitmap_bit_p (biased_names, SSA_NAME_VERSION (op))) + { + if (maybe_biased_p == NULL) + return rank; + *maybe_biased_p = true; + } + return MAX (rank, op_rank); } @@ -433,13 +462,20 @@ get_rank (tree e) stmt = SSA_NAME_DEF_STMT (e); if (gimple_code (stmt) == GIMPLE_PHI) - rank = phi_rank (stmt); + { + rank = phi_rank (stmt); + if (rank != bb_rank[gimple_bb (stmt)->index]) + bitmap_set_bit (biased_names, SSA_NAME_VERSION (e)); + } else if (!is_gimple_assign (stmt)) rank = bb_rank[gimple_bb (stmt)->index]; else { + bool biased_p = false; + bool *maybe_biased_p = propagate_bias_p (stmt) ? &biased_p : NULL; + /* Otherwise, find the maximum rank for the operands. As an exception, remove the bias from loop-carried phis when propagating the rank so that dependent operations are not also biased. */ @@ -448,9 +484,11 @@ get_rank (tree e) thus have rank 0. */ rank = 0; FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) - rank = propagate_rank (rank, op); + rank = propagate_rank (rank, op, maybe_biased_p); rank += 1; + if (biased_p) + bitmap_set_bit (biased_names, SSA_NAME_VERSION (e)); } if (dump_file && (dump_flags & TDF_DETAILS)) @@ -6933,6 +6971,7 @@ fini_reassoc (void) reassociate_stats.pows_created); delete operand_rank; + bitmap_clear (biased_names); operand_entry_pool.release (); free (bb_rank); plus_negates.release (); From patchwork Sun Sep 26 11:09:36 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Leoshkevich X-Patchwork-Id: 1532959 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: 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=T5nFDnIe; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4HHNRH2Nmqz9s82 for ; Sun, 26 Sep 2021 21:12:59 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 232CB385803D for ; Sun, 26 Sep 2021 11:12:57 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 232CB385803D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632654777; bh=x66X0LS0XZUhAZlPFIS4gZBDt4Jqsd6hd4WUS3sZJDM=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=T5nFDnIeplQHyap/6Cs/ro0v2r/F/FaeqMudaKf8fM0ICPpILSwywOYQpGygz4u/V SYlQbPNfXvJaSFt/BK9+rPfpO+5Tbu+fXav+G5plDyCeaeNK62OEsZL1Zdni9U4h++ 5UVwkwXlJm1HoiYJE43gLkR8ry8uxNFkXyQKjvWU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id D483F3858408; Sun, 26 Sep 2021 11:09:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D483F3858408 Received: from pps.filterd (m0098416.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18Q99VOD003740; Sun, 26 Sep 2021 07:09:45 -0400 Received: from ppma02fra.de.ibm.com (47.49.7a9f.ip4.static.sl-reverse.com [159.122.73.71]) by mx0b-001b2d01.pphosted.com with ESMTP id 3bagq3dech-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Sun, 26 Sep 2021 07:09:45 -0400 Received: from pps.filterd (ppma02fra.de.ibm.com [127.0.0.1]) by ppma02fra.de.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 18QB3NWG012158; Sun, 26 Sep 2021 11:09:43 GMT Received: from b06avi18878370.portsmouth.uk.ibm.com (b06avi18878370.portsmouth.uk.ibm.com [9.149.26.194]) by ppma02fra.de.ibm.com with ESMTP id 3b9ud8w0f6-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Sun, 26 Sep 2021 11:09:43 +0000 Received: from d06av26.portsmouth.uk.ibm.com (d06av26.portsmouth.uk.ibm.com [9.149.105.62]) by b06avi18878370.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 18QB4e1Q55706080 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sun, 26 Sep 2021 11:04:40 GMT Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 90024AE086; Sun, 26 Sep 2021 11:09:39 +0000 (GMT) Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 39BA0AE077; Sun, 26 Sep 2021 11:09:39 +0000 (GMT) Received: from vm.lan (unknown [9.145.45.184]) by d06av26.portsmouth.uk.ibm.com (Postfix) with ESMTP; Sun, 26 Sep 2021 11:09:39 +0000 (GMT) To: Richard Biener Subject: [PATCH v3 3/3] reassoc: Test rank biasing Date: Sun, 26 Sep 2021 13:09:36 +0200 Message-Id: <20210926110936.344019-4-iii@linux.ibm.com> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20210926110936.344019-1-iii@linux.ibm.com> References: <20210926110936.344019-1-iii@linux.ibm.com> MIME-Version: 1.0 X-TM-AS-GCONF: 00 X-Proofpoint-GUID: yTD3BU_UpxQOyranLIX48l0uSZp_Q9QO X-Proofpoint-ORIG-GUID: yTD3BU_UpxQOyranLIX48l0uSZp_Q9QO X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.790,Hydra:6.0.391,FMLib:17.0.607.475 definitions=2021-09-26_03,2021-09-24_02,2020-04-07_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 clxscore=1015 malwarescore=0 adultscore=0 mlxscore=0 phishscore=0 priorityscore=1501 impostorscore=0 bulkscore=0 suspectscore=0 mlxlogscore=999 lowpriorityscore=0 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2109260078 X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP 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: Ilya Leoshkevich via Gcc-patches From: Ilya Leoshkevich Reply-To: Ilya Leoshkevich Cc: Andreas Krebbel , gcc-patches@gcc.gnu.org Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Add both positive and negative tests. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/reassoc-46.c: New test. * gcc.dg/tree-ssa/reassoc-46.h: Common code for new tests. * gcc.dg/tree-ssa/reassoc-47.c: New test. * gcc.dg/tree-ssa/reassoc-48.c: New test. * gcc.dg/tree-ssa/reassoc-49.c: New test. * gcc.dg/tree-ssa/reassoc-50.c: New test. * gcc.dg/tree-ssa/reassoc-51.c: New test. --- gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.c | 7 +++++ gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.h | 33 ++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/reassoc-47.c | 9 ++++++ gcc/testsuite/gcc.dg/tree-ssa/reassoc-48.c | 9 ++++++ gcc/testsuite/gcc.dg/tree-ssa/reassoc-49.c | 11 ++++++++ gcc/testsuite/gcc.dg/tree-ssa/reassoc-50.c | 10 +++++++ gcc/testsuite/gcc.dg/tree-ssa/reassoc-51.c | 11 ++++++++ 7 files changed, 90 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.h create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-47.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-48.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-49.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-50.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-51.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.c new file mode 100644 index 00000000000..97563dd929f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.c @@ -0,0 +1,7 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ftree-vectorize" } */ + +#include "reassoc-46.h" + +/* Check that the loop accumulator is added last. */ +/* { dg-final { scan-tree-dump-times {(?:vect_)?sum_[\d._]+ = (?:(?:vect_)?_[\d._]+ \+ (?:vect_)?sum_[\d._]+|(?:vect_)?sum_[\d._]+ \+ (?:vect_)?_[\d._]+)} 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.h b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.h new file mode 100644 index 00000000000..e60b490ea0d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-46.h @@ -0,0 +1,33 @@ +#define M 1024 +unsigned int arr1[M]; +unsigned int arr2[M]; +volatile unsigned int sink; + +unsigned int +test (void) +{ + unsigned int sum = 0; + for (int i = 0; i < M; i++) + { +#ifdef MODIFY + /* Modify the loop accumulator using a chain of operations - this should + not affect its rank biasing. */ + sum |= 1; + sum ^= 2; +#endif +#ifdef STORE + /* Save the loop accumulator into a global variable - this should not + affect its rank biasing. */ + sink = sum; +#endif +#ifdef USE + /* Add a tricky use of the loop accumulator - this should prevent its + rank biasing. */ + i = (i + sum) % M; +#endif + /* Use addends with different ranks. */ + sum += arr1[i]; + sum += arr2[((i ^ 1) + 1) % M]; + } + return sum; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-47.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-47.c new file mode 100644 index 00000000000..1b0f0fdabe1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-47.c @@ -0,0 +1,9 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ftree-vectorize" } */ + +#define MODIFY +#include "reassoc-46.h" + +/* Check that if the loop accumulator is saved into a global variable, it's + still added last. */ +/* { dg-final { scan-tree-dump-times {(?:vect_)?sum_[\d._]+ = (?:(?:vect_)?_[\d._]+ \+ (?:vect_)?sum_[\d._]+|(?:vect_)?sum_[\d._]+ \+ (?:vect_)?_[\d._]+)} 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-48.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-48.c new file mode 100644 index 00000000000..13836ebe8e6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-48.c @@ -0,0 +1,9 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ftree-vectorize" } */ + +#define STORE +#include "reassoc-46.h" + +/* Check that if the loop accumulator is modified using a chain of operations + other than addition, its new value is still added last. */ +/* { dg-final { scan-tree-dump-times {(?:vect_)?sum_[\d._]+ = (?:(?:vect_)?_[\d._]+ \+ (?:vect_)?sum_[\d._]+|(?:vect_)?sum_[\d._]+ \+ (?:vect_)?_[\d._]+)} 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-49.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-49.c new file mode 100644 index 00000000000..c1136a447a2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-49.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ftree-vectorize" } */ + +#define MODIFY +#define STORE +#include "reassoc-46.h" + +/* Check that if the loop accumulator is both modified using a chain of + operations other than addition and stored into a global variable, its new + value is still added last. */ +/* { dg-final { scan-tree-dump-times {(?:vect_)?sum_[\d._]+ = (?:(?:vect_)?_[\d._]+ \+ (?:vect_)?sum_[\d._]+|(?:vect_)?sum_[\d._]+ \+ (?:vect_)?_[\d._]+)} 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-50.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-50.c new file mode 100644 index 00000000000..e35a4ff1278 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-50.c @@ -0,0 +1,10 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ftree-vectorize" } */ + +#define MODIFY +#define USE +#include "reassoc-46.h" + +/* Check that if the loop accumulator has multiple uses inside the loop, it's + not forced to the end of the reassociation chain. */ +/* { dg-final { scan-tree-dump-times {(?:vect_)?sum_[\d._]+ = (?:(?:vect_)?_[\d._]+ \+ (?:vect_)?sum_[\d._]+|(?:vect_)?sum_[\d._]+ \+ (?:vect_)?_[\d._]+)} 2 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-51.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-51.c new file mode 100644 index 00000000000..07175675e24 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-51.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized -ftree-vectorize" } */ + +#define MODIFY +#define STORE +#define USE +#include "reassoc-46.h" + +/* Check that if the loop accumulator has multiple uses inside the loop, it's + not forced to the end of the reassociation chain. */ +/* { dg-final { scan-tree-dump-times {(?:vect_)?sum_[\d._]+ = (?:(?:vect_)?_[\d._]+ \+ (?:vect_)?sum_[\d._]+|(?:vect_)?sum_[\d._]+ \+ (?:vect_)?_[\d._]+)} 2 "optimized" } } */