From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0b-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id F03A03856DD6 for ; Tue, 30 May 2023 05:06:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org F03A03856DD6 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 (m0360072.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 34U2Ddfa014320; Tue, 30 May 2023 05:06:40 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=ppyW024lMWR4bftarka8p8Af/3APb0HEzmflTQswix4=; b=jU5FeSV/zW8O+6i7cC5dI7Civ+scI97ppMreIxKZtx6aLqSrcU1V4Ely5PXExa6wquQh 49IG18lvaKGyRMnfnEGPdZiw13nsWHMxDGwlRA27GXsWzEdtM5jCET4PGsrG1fsvHTws MbHpIhQ2WYpHm7iumcPl63TwLHfEteKlDMvdU0jViCdXY9al4IdeJPN1pW3kCFUDJPrv z5oGfNkM549r4kULxKgbR1Xdl+OK+XZnKc7DJHof823Dp9d9YVy53sRqGWB9oPIvU4ad Sp7X5vfuko+01pCJNozOBrOF4xABkHoBgnkO38C4U+m/EqSIOaQDOt5+J/GUeCbuNBGB tw== Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3qw85xayrf-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 30 May 2023 05:06:39 +0000 Received: from m0360072.ppops.net (m0360072.ppops.net [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 34U56dDk024489; Tue, 30 May 2023 05:06:39 GMT Received: from ppma04wdc.us.ibm.com (1a.90.2fa9.ip4.static.sl-reverse.com [169.47.144.26]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3qw85xayr3-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 30 May 2023 05:06:39 +0000 Received: from pps.filterd (ppma04wdc.us.ibm.com [127.0.0.1]) by ppma04wdc.us.ibm.com (8.17.1.19/8.17.1.19) with ESMTP id 34U4eet6013955; Tue, 30 May 2023 05:06:38 GMT Received: from smtprelay05.wdc07v.mail.ibm.com ([9.208.129.117]) by ppma04wdc.us.ibm.com (PPS) with ESMTPS id 3qu9g5ncqy-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 30 May 2023 05:06:38 +0000 Received: from smtpav03.wdc07v.mail.ibm.com (smtpav03.wdc07v.mail.ibm.com [10.39.53.230]) by smtprelay05.wdc07v.mail.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 34U56bNG7995980 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 30 May 2023 05:06:37 GMT Received: from smtpav03.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 5DDE25805D; Tue, 30 May 2023 05:06:37 +0000 (GMT) Received: from smtpav03.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 5E6A95805C; Tue, 30 May 2023 05:06:34 +0000 (GMT) Received: from [9.43.74.244] (unknown [9.43.74.244]) by smtpav03.wdc07v.mail.ibm.com (Postfix) with ESMTP; Tue, 30 May 2023 05:06:33 +0000 (GMT) Message-ID: Date: Tue, 30 May 2023 10:36:32 +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: I0DN-Kg_gbaxIOFz-iM4ymJiPwB43Zcs X-Proofpoint-GUID: DXRbP6ZZBzprBH6I8k2hozc_R69XAiBB 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_02,2023-05-29_02,2023-05-22_02 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 mlxscore=0 spamscore=0 priorityscore=1501 suspectscore=0 bulkscore=0 clxscore=1015 impostorscore=0 lowpriorityscore=0 mlxlogscore=999 malwarescore=0 phishscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2304280000 definitions=main-2305300041 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 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. >> 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 >>