From patchwork Tue Sep 21 22:54:28 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Leoshkevich X-Patchwork-Id: 45259 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 BC4EF3858411 for ; Tue, 21 Sep 2021 22:57:08 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BC4EF3858411 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632265028; bh=qzvVEc2ESGDh22RGZT1DzBF6aSqQCtQLQHTR/bPMxvM=; 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=cvemNsdKG/N3H1S+7CkwOEwCWzigpOmcTwNZFq3WOy1ZnUizbB/IVejMZh5Wri2wp mtvA2/lzrDW/Zgck18ye4cMswm8Dox5QNvgukCXBvgxDO647VliCv1MyiIohbtJsIl lFL4uDaFoAMa6RWd/YdTh/Sj0Y/duW2jQfAv6BzM= 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 16EAA3858C3A; Tue, 21 Sep 2021 22:54:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 16EAA3858C3A Received: from pps.filterd (m0098414.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18LMCEgF024585; Tue, 21 Sep 2021 18:54:37 -0400 Received: from ppma06ams.nl.ibm.com (66.31.33a9.ip4.static.sl-reverse.com [169.51.49.102]) by mx0b-001b2d01.pphosted.com with ESMTP id 3b7qyugmf5-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:37 -0400 Received: from pps.filterd (ppma06ams.nl.ibm.com [127.0.0.1]) by ppma06ams.nl.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 18LMroiY019714; Tue, 21 Sep 2021 22:54:35 GMT Received: from b06avi18878370.portsmouth.uk.ibm.com (b06avi18878370.portsmouth.uk.ibm.com [9.149.26.194]) by ppma06ams.nl.ibm.com with ESMTP id 3b7q6ngeq9-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 22:54:35 +0000 Received: from d06av25.portsmouth.uk.ibm.com (d06av25.portsmouth.uk.ibm.com [9.149.105.61]) by b06avi18878370.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 18LMnhie55837134 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 21 Sep 2021 22:49:43 GMT Received: from d06av25.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 6784911C088; Tue, 21 Sep 2021 22:54:32 +0000 (GMT) Received: from d06av25.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 0F3C111C08B; Tue, 21 Sep 2021 22:54:32 +0000 (GMT) Received: from vm.lan (unknown [9.145.45.184]) by d06av25.portsmouth.uk.ibm.com (Postfix) with ESMTP; Tue, 21 Sep 2021 22:54:31 +0000 (GMT) To: Richard Biener Subject: [PATCH v2 2/3] reassoc: Propagate PHI_LOOP_BIAS along single uses Date: Wed, 22 Sep 2021 00:54:28 +0200 Message-Id: <20210921225429.326017-3-iii@linux.ibm.com> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20210921225429.326017-1-iii@linux.ibm.com> References: <20210921225429.326017-1-iii@linux.ibm.com> MIME-Version: 1.0 X-TM-AS-GCONF: 00 X-Proofpoint-GUID: 4QG4UgA0X30faenjmkO36P0OVxyc8BTd X-Proofpoint-ORIG-GUID: 4QG4UgA0X30faenjmkO36P0OVxyc8BTd 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-21_07,2021-09-20_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 mlxlogscore=999 lowpriorityscore=0 spamscore=0 clxscore=1015 bulkscore=0 phishscore=0 impostorscore=0 adultscore=0 suspectscore=0 priorityscore=1501 malwarescore=0 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109200000 definitions=main-2109210134 X-Spam-Status: No, score=-11.7 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+patchwork=sourceware.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 | 97 ++++++++++++++++++++++++++++-------------- 1 file changed, 64 insertions(+), 33 deletions(-) diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 420c14e8cf5..2f7a8882aac 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,50 @@ 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; + + 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) + 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,46 +361,23 @@ 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, gimple *stmt, bool *bias_p) { int64_t op_rank; - if (loop_carried_phi (op)) - return rank; + if (TREE_CODE (op) == SSA_NAME + && bitmap_bit_p (biased_names, SSA_NAME_VERSION (op))) + { + if (propagate_bias_p (stmt)) + *bias_p = true; + else + return rank; + } op_rank = get_rank (op); @@ -440,6 +465,8 @@ get_rank (tree e) else { + bool bias_p = false; + /* 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 +475,12 @@ 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, stmt, &bias_p); rank += 1; + if (bias_p) + bitmap_set_bit (biased_names, + SSA_NAME_VERSION (gimple_assign_lhs (stmt))); } if (dump_file && (dump_flags & TDF_DETAILS)) @@ -6933,6 +6963,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 ();