From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id 75DAA3858D20 for ; Tue, 30 May 2023 07:35:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 75DAA3858D20 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=linux.ibm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linux.ibm.com Received: from pps.filterd (m0353727.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 34U6VfKG004167; Tue, 30 May 2023 07:35:29 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ibm.com; h=message-id : date : mime-version : subject : to : cc : references : from : in-reply-to : content-type : content-transfer-encoding; s=pp1; bh=6qmBqjuePaZctb+zWzPhtXO6klM3ntZarxx7XGGv7qA=; b=SZZ3n3ORCrZR58qMk/NWqYv8bmUJA/wz8AJWh4Do5KgzonIKuKEw+xs61W9jAy48mcRA 0kCi8OVwzMTH3IcEP6yeP0c1sdI0FKX9TRJxZ/IMZFmE/eFAKnti06ehfnqr+fnJ8Nhd nZIDc77EYgkgRSBn77jmjHQh1MHDZw562Zo1pdd2I+5vONF6R1u7IO3itf/x8Y/L9Ecu AjqyneRRsiCcNY4mRs1cB9TJ+y6yDqsr0ZFmCrRydia7VOppteQWC+ehfqMBJEWArIj/ WUqBBzTOsEUwNU8i2rHwyv8HYWrgFJMIy/RHccd1lMYDP9+7SAjaa4XP15nHRpXwkMpa GQ== Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3qwbxmhjuf-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 30 May 2023 07:35:28 +0000 Received: from m0353727.ppops.net (m0353727.ppops.net [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 34U6fIlo016641; Tue, 30 May 2023 07:35:28 GMT Received: from ppma01wdc.us.ibm.com (fd.55.37a9.ip4.static.sl-reverse.com [169.55.85.253]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3qwbxmhjjh-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 30 May 2023 07:35:26 +0000 Received: from pps.filterd (ppma01wdc.us.ibm.com [127.0.0.1]) by ppma01wdc.us.ibm.com (8.17.1.19/8.17.1.19) with ESMTP id 34U4d8Xv009536; Tue, 30 May 2023 07:32:12 GMT Received: from smtprelay06.wdc07v.mail.ibm.com ([9.208.129.118]) by ppma01wdc.us.ibm.com (PPS) with ESMTPS id 3qu9g5ntgv-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 30 May 2023 07:32:12 +0000 Received: from smtpav01.wdc07v.mail.ibm.com (smtpav01.wdc07v.mail.ibm.com [10.39.53.228]) by smtprelay06.wdc07v.mail.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 34U7WBmk66650604 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 30 May 2023 07:32:11 GMT Received: from smtpav01.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 24D4E58067; Tue, 30 May 2023 07:32:11 +0000 (GMT) Received: from smtpav01.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id DE27E58055; Tue, 30 May 2023 07:32:07 +0000 (GMT) Received: from [9.43.74.244] (unknown [9.43.74.244]) by smtpav01.wdc07v.mail.ibm.com (Postfix) with ESMTP; Tue, 30 May 2023 07:32:07 +0000 (GMT) Message-ID: <355d8fa5-dbba-c8ba-bf46-78596b88d572@linux.ibm.com> Date: Tue, 30 May 2023 13:02:05 +0530 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: Re: [PATCH v1] tree-ssa-sink: Improve code sinking pass. Content-Language: en-US To: Richard Biener Cc: gcc-patches , Segher Boessenkool , Peter Bergner , Jeff Law References: From: Ajit Agarwal In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-TM-AS-GCONF: 00 X-Proofpoint-ORIG-GUID: pSO5-iX86Y3hJPpqaaQN7jjxe7ct83Zw X-Proofpoint-GUID: jNtAapbKbEfzSdrt93-8OeRIxoQFtiq_ X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.573,FMLib:17.11.176.26 definitions=2023-05-30_04,2023-05-29_02,2023-05-22_02 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 malwarescore=0 adultscore=0 lowpriorityscore=0 clxscore=1015 bulkscore=0 spamscore=0 phishscore=0 priorityscore=1501 suspectscore=0 impostorscore=0 mlxlogscore=999 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2304280000 definitions=main-2305300062 X-Spam-Status: No, score=-12.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_EF,GIT_PATCH_0,NICE_REPLY_A,RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_PASS,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 List-Id: Hello Richard: On 30/05/23 12:34 pm, Richard Biener wrote: > On Tue, May 30, 2023 at 7:06 AM Ajit Agarwal wrote: >> >> Hello Richard: >> >> On 22/05/23 6:26 pm, Richard Biener wrote: >>> On Thu, May 18, 2023 at 9:14 AM Ajit Agarwal wrote: >>>> >>>> Hello All: >>>> >>>> This patch improves code sinking pass to sink statements before call to reduce >>>> register pressure. >>>> Review comments are incorporated. >>>> >>>> Bootstrapped and regtested on powerpc64-linux-gnu. >>>> >>>> Thanks & Regards >>>> Ajit >>>> >>>> >>>> tree-ssa-sink: Improve code sinking pass. >>>> >>>> Code Sinking sinks the blocks after call. This increases >>>> register pressure for callee-saved registers. Improves >>>> code sinking before call in the use blocks or immediate >>>> dominator of use blocks. >>>> >>>> 2023-05-18 Ajit Kumar Agarwal >>>> >>>> gcc/ChangeLog: >>>> >>>> * tree-ssa-sink.cc (statement_sink_location): Modifed to >>>> move statements before calls. >>>> (block_call_p): New function. >>>> (def_use_same_block): New function. >>>> (select_best_block): Add heuristics to select the best >>>> blocks in the immediate post dominator. >>>> >>>> gcc/testsuite/ChangeLog: >>>> >>>> * gcc.dg/tree-ssa/ssa-sink-20.c: New testcase. >>>> * gcc.dg/tree-ssa/ssa-sink-21.c: New testcase. >>>> --- >>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c | 16 ++ >>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 20 +++ >>>> gcc/tree-ssa-sink.cc | 159 ++++++++++++++++++-- >>>> 3 files changed, 185 insertions(+), 10 deletions(-) >>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c >>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c >>>> >>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c >>>> new file mode 100644 >>>> index 00000000000..716bc1f9257 >>>> --- /dev/null >>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c >>>> @@ -0,0 +1,16 @@ >>>> +/* { dg-do compile } */ >>>> +/* { dg-options "-O2 -fdump-tree-sink -fdump-tree-optimized -fdump-tree-sink-stats" } */ >>>> + >>>> +void bar(); >>>> +int j; >>>> +void foo(int a, int b, int c, int d, int e, int f) >>>> +{ >>>> + int l; >>>> + l = a + b + c + d +e + f; >>>> + if (a != 5) >>>> + { >>>> + bar(); >>>> + j = l; >>>> + } >>>> +} >>>> +/* { dg-final { scan-tree-dump-times "Sunk statements: 5" 1 "sink" } } */ >>> >>> this doesn't verify the place we sink to? >>> >> >> I am not sure how to verify the place we sink to with dg-final. > > I think dejagnu supports matching multi-line regexps so I suggest > to scan for the sunk expr RHS to be followed by the call? > You meant to use dg-begin-multiline-output and dg-end-multiline-output. Thanks & Regards Ajit >>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c >>>> new file mode 100644 >>>> index 00000000000..ff41e2ea8ae >>>> --- /dev/null >>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c >>>> @@ -0,0 +1,20 @@ >>>> +/* { dg-do compile } */ >>>> +/* { dg-options "-O2 -fdump-tree-sink-stats -fdump-tree-sink-stats" } */ >>>> + >>>> +void bar(); >>>> +int j, x; >>>> +void foo(int a, int b, int c, int d, int e, int f) >>>> +{ >>>> + int l; >>>> + l = a + b + c + d +e + f; >>>> + if (a != 5) >>>> + { >>>> + bar(); >>>> + if (b != 3) >>>> + x = 3; >>>> + else >>>> + x = 5; >>>> + j = l; >>>> + } >>>> +} >>>> +/* { dg-final { scan-tree-dump-times "Sunk statements: 5" 1 "sink" } } */ >>> >>> likewise. So both tests already pass before the patch? >>> >>>> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc >>>> index 87b1d40c174..76556e7795b 100644 >>>> --- a/gcc/tree-ssa-sink.cc >>>> +++ b/gcc/tree-ssa-sink.cc >>>> @@ -171,6 +171,72 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) >>>> return commondom; >>>> } >>>> >>>> +/* Return TRUE if immediate uses of the defs in >>>> + USE occur in the same block as USE, FALSE otherwise. */ >>>> + >>>> +bool >>>> +def_use_same_block (gimple *stmt) >>>> +{ >>>> + use_operand_p use_p; >>>> + def_operand_p def_p; >>>> + imm_use_iterator imm_iter; >>>> + ssa_op_iter iter; >>>> + >>>> + FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF) >>>> + { >>>> + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p)) >>>> + { >>>> + if (is_gimple_debug (USE_STMT (use_p))) >>>> + continue; >>>> + >>>> + if (use_p >>> >>> use_p is never null >>> >>>> + && (gimple_bb (USE_STMT (use_p)) == gimple_bb (stmt))) >>>> + return true; >>> >>> the function behavior is obviously odd ... >>> >>>> + } >>>> + } >>>> + return false; >>>> +} >>>> + >>>> +/* Return TRUE if the block has only calls, FALSE otherwise. */ >>>> + >>>> +bool >>>> +block_call_p (basic_block bb) >>>> +{ >>>> + int i = 0; >>>> + bool is_call = false; >>>> + gimple_stmt_iterator gsi = gsi_last_bb (bb); >>>> + gimple *last_stmt = gsi_stmt (gsi); >>>> + >>>> + if (last_stmt && gimple_code (last_stmt) == GIMPLE_COND) >>>> + { >>>> + if (!gsi_end_p (gsi)) >>>> + gsi_prev (&gsi); >>>> + >>>> + for (; !gsi_end_p (gsi);) >>>> + { >>>> + gimple *stmt = gsi_stmt (gsi); >>>> + >>>> + /* We have already seen a call. */ >>>> + if (is_call) >>>> + return false; >>> >>> Likewise. Do you want to check whether a block has >>> a single stmt and that is a call and that is followed by >>> a condition? It looks like a very convoluted way to write this. >>> >>>> + >>>> + if (is_gimple_call (stmt)) >>>> + is_call = true; >>>> + else >>>> + return false; >>>> + >>>> + if (!gsi_end_p (gsi)) >>>> + gsi_prev (&gsi); >>>> + >>>> + ++i; >>>> + } >>>> + } >>>> + if (is_call && i == 1) >>>> + return true; >>>> + >>>> + return false; >>>> +} >>>> + >>>> /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator >>>> tree, return the best basic block between them (inclusive) to place >>>> statements. >>>> @@ -190,7 +256,8 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) >>>> static basic_block >>>> select_best_block (basic_block early_bb, >>>> basic_block late_bb, >>>> - gimple *stmt) >>>> + gimple *stmt, >>>> + gimple *use) >>> >>> please update the function comment >>> >>>> { >>>> basic_block best_bb = late_bb; >>>> basic_block temp_bb = late_bb; >>>> @@ -230,14 +297,47 @@ select_best_block (basic_block early_bb, >>>> if (threshold > 100) >>>> threshold = 100; >>>> } >>>> - >>>> /* If BEST_BB is at the same nesting level, then require it to have >>>> significantly lower execution frequency to avoid gratuitous movement. */ >>>> if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb) >>>> /* If result of comparsion is unknown, prefer EARLY_BB. >>>> Thus use !(...>=..) rather than (...<...) */ >>>> && !(best_bb->count * 100 >= early_bb->count * threshold)) >>>> - return best_bb; >>>> + { >>>> + basic_block new_best_bb = get_immediate_dominator (CDI_DOMINATORS, best_bb); >>>> + /* Return best_bb if def and use are in same block otherwise new_best_bb. >>>> + >>>> + Things to consider: >>>> + >>>> + new_best_bb is not equal to best_bb and early_bb. >>>> + >>>> + stmt is not call. >>>> + >>>> + new_best_bb doesnt have any phis. >>>> + >>>> + use basic block is not equal to early_bb. >>>> + >>>> + use basic block post dominates to new_best_bb. >>>> + >>>> + new_best_bb dominates early_bb. */ >>>> + if (new_best_bb && use >>>> + && (new_best_bb != best_bb) >>>> + && (new_best_bb != early_bb) >>>> + && !is_gimple_call (stmt) >>>> + && gsi_end_p (gsi_start_phis (new_best_bb)) >>>> + && (gimple_bb (use) != early_bb) >>>> + && !is_gimple_call (use) >>>> + && dominated_by_p (CDI_POST_DOMINATORS, new_best_bb, gimple_bb(use)) >>>> + && dominated_by_p (CDI_DOMINATORS, new_best_bb, early_bb) >>>> + && block_call_p (new_best_bb)) >>>> + { >>>> + if (def_use_same_block (use)) >>>> + return best_bb; >>> >>> given the odd implementation of the predicates this matches very very >>> specific cases. >>> >>> Consider >>> >>> if (..) >>> { >>> foo(); >>> bar(); >>> ... = l; >>> } >>> >>> and C++ where foo and bar might throw. You then likely want to sink >>> before foo (). >>> >>> What's the reason to only consider blocks with exactly 'call; cond;' ? >>> >>>> + >>>> + return new_best_bb; >>>> + } >>>> + return best_bb; >>>> + } >>>> >>>> /* No better block found, so return EARLY_BB, which happens to be the >>>> statement's original block. */ >>>> @@ -439,7 +539,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, >>>> if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb)) >>>> return false; >>>> >>>> - commondom = select_best_block (frombb, commondom, stmt); >>>> + commondom = select_best_block (frombb, commondom, stmt, NULL); >>>> >>>> if (commondom == frombb) >>>> return false; >>>> @@ -456,19 +556,58 @@ statement_sink_location (gimple *stmt, basic_block frombb, >>>> continue; >>>> break; >>>> } >>>> + >>>> use = USE_STMT (one_use); >>>> >>>> if (gimple_code (use) != GIMPLE_PHI) >>>> { >>>> - sinkbb = select_best_block (frombb, gimple_bb (use), stmt); >>>> + sinkbb = select_best_block (frombb, gimple_bb (use), stmt, use); >>>> >>>> if (sinkbb == frombb) >>>> return false; >>>> >>>> - if (sinkbb == gimple_bb (use)) >>>> - *togsi = gsi_for_stmt (use); >>>> - else >>>> - *togsi = gsi_after_labels (sinkbb); >>>> + gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def_p)); >>>> + >>>> + if ((gimple_bb (def_stmt) == gimple_bb (use)) >>>> + && (gimple_bb (use) != sinkbb)) >>>> + sinkbb = gimple_bb (use); >>>> + >>>> + if (sinkbb == gimple_bb (use)) >>>> + { >>>> + gimple_stmt_iterator gsi = gsi_last_bb (sinkbb); >>>> + gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def_p)); >>>> + gimple *last_stmt = gsi_stmt (gsi); >>>> + >>>> + /* Update sinking point as stmt before call if the sinking block >>>> + has only calls. Otherwise update sinking point as the use >>>> + stmt. */ >>>> + if (gsi_stmt (gsi) == use >>>> + && !is_gimple_call (last_stmt) >>>> + && (gimple_code (last_stmt) != GIMPLE_SWITCH) >>>> + && (gimple_code (last_stmt) != GIMPLE_COND) >>>> + && (gimple_code (last_stmt) != GIMPLE_GOTO) >>>> + && (!gimple_vdef (use) || !def_use_same_block (def_stmt))) >>>> + { >>>> + if (!gsi_end_p (gsi)) >>>> + gsi_prev (&gsi); >>>> + >>>> + gimple *stmt = gsi_stmt (gsi); >>>> + >>>> + if (!gsi_end_p (gsi)) >>>> + gsi_prev (&gsi); >>>> + >>>> + if (gsi_end_p (gsi) && stmt && is_gimple_call (stmt) >>>> + && gsi_end_p (gsi_start_phis (sinkbb)) >>>> + && !is_gimple_call (def_stmt)) >>>> + *togsi = gsi_for_stmt (stmt); >>>> + else >>>> + *togsi = gsi_for_stmt (use); >>>> + } >>>> + else >>>> + *togsi = gsi_for_stmt(use); >>>> + } >>>> + else >>>> + *togsi = gsi_after_labels (sinkbb); >>> >>> This is very convoluted. I think that in the end you want to compute (once) the >>> position of the first call in each block. Since we're waking the CFG backwards >>> in post-dominator order this information can be gathered during this walk. >>> This would determine the location to sink to iff the use stmt is dominated by >>> this location (you can for example use gimple_uid to mark stmts before it). >>> >>> The alternative is to simply always sink to the start of blocks even for the >>> use stmt block in case that has a call before the use (but you still need to >>> efficiently compute that). >>> >> >> Incorporated the above comments and sent a separate patch. >> >> Thanks & Regards >> Ajit >> >>> Richard. >>> >>>> >>>> return true; >>>> } >>>> @@ -480,7 +619,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, >>>> if (!sinkbb) >>>> return false; >>>> >>>> - sinkbb = select_best_block (frombb, sinkbb, stmt); >>>> + sinkbb = select_best_block (frombb, sinkbb, stmt, NULL); >>>> if (!sinkbb || sinkbb == frombb) >>>> return false; >>>> >>>> -- >>>> 2.31.1 >>>>