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 A342D3858C52 for ; Tue, 17 Oct 2023 13:23:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A342D3858C52 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 ARC-Filter: OpenARC Filter v1.0.0 sourceware.org A342D3858C52 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=148.163.156.1 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1697549029; cv=none; b=vzz2ntmYGy5i/af27IlNjDCuTOCg8LO5TarP3C2UjxLPGsKIfPhg4f0Q1hBvoMT28M6jgu1JHkejfQQAroUs+tvCyvGcaiMqzGxy7poExRuZfC+pQUmOCVxsgiNfLWb8coLZYY47HgfJzIdEjHIr7KUYL2QRO+5QOxdRqkEyzoo= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1697549029; c=relaxed/simple; bh=xlSms9hGr+fpfkENogNL5j+naqUaN+Wnxn83M8qLsSA=; h=DKIM-Signature:Message-ID:Date:MIME-Version:Subject:To:From; b=Tq1OuX6j/XNV/manTm8nJyEQclxSXjjnfgy46hWif8vogVzIS6i/EsY0lEjz3B13cOcXRKJuRcwEsK+l9hJw7g/uyrnG7/So+LsjHzSnp0DNwMUzcoX8ACx7EN/oFY7i608GDFliOHvESTG8be/MmMjYFONMdxOBGaZQXFioBBM= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from pps.filterd (m0360083.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 39HDMdho015997; Tue, 17 Oct 2023 13:23:46 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=ih/U5eW+zySXyFJS+BB9q8RnLe8PkuehaZiHcI/PRPk=; b=Fxf2CGvCke67LBPbydW4fbWZkOzQ5yTputW9lBq99UEP+nUb0D+77/K0z2OKNvyYHrF4 nTCanbgkjGIj2uIFj75sq+lBWSuvqR+y4T/z3rnG1xFkeXjkiEx4tP8e0u7TxmaIadXH +3RCjp7BR9ZeTs5orq0rrcufc7h2QpEBH61i1u2KGI2kE27O+ne+GAHDUwbfaN8Cg+Mw AKh5Z778JIbOW+GvyEVOwLMpf/Oym++XbrKBvYls751lnCp3SQ8ipZ4+DEOZ7hFKgA8l OwZ+8AWznQow9vVNF+WTXbZw2SP9GLC6NSa+LJWcliq41+1//sbpTKelcLmFJivGPBtg Qw== Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3tsu3gr382-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 17 Oct 2023 13:23:45 +0000 Received: from m0360083.ppops.net (m0360083.ppops.net [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 39HDMiNu016300; Tue, 17 Oct 2023 13:23:45 GMT Received: from ppma11.dal12v.mail.ibm.com (db.9e.1632.ip4.static.sl-reverse.com [50.22.158.219]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3tsu3gr33c-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 17 Oct 2023 13:23:44 +0000 Received: from pps.filterd (ppma11.dal12v.mail.ibm.com [127.0.0.1]) by ppma11.dal12v.mail.ibm.com (8.17.1.19/8.17.1.19) with ESMTP id 39HDGFYk019881; Tue, 17 Oct 2023 13:23:41 GMT Received: from smtprelay03.dal12v.mail.ibm.com ([172.16.1.5]) by ppma11.dal12v.mail.ibm.com (PPS) with ESMTPS id 3tr811gmn6-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 17 Oct 2023 13:23:41 +0000 Received: from smtpav04.wdc07v.mail.ibm.com (smtpav04.wdc07v.mail.ibm.com [10.39.53.231]) by smtprelay03.dal12v.mail.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 39HDNeCX15925796 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 17 Oct 2023 13:23:40 GMT Received: from smtpav04.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 67D1658050; Tue, 17 Oct 2023 13:23:40 +0000 (GMT) Received: from smtpav04.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id E1A4B58045; Tue, 17 Oct 2023 13:23:37 +0000 (GMT) Received: from [9.43.39.223] (unknown [9.43.39.223]) by smtpav04.wdc07v.mail.ibm.com (Postfix) with ESMTP; Tue, 17 Oct 2023 13:23:37 +0000 (GMT) Message-ID: Date: Tue, 17 Oct 2023 18:53:37 +0530 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v8] tree-ssa-sink: Improve code sinking pass Content-Language: en-US To: Richard Biener Cc: gcc-patches , Jeff Law , Segher Boessenkool , Peter Bergner References: <79f04438-7473-2b01-d26a-9357ad9318af@linux.ibm.com> From: Ajit Agarwal In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-TM-AS-GCONF: 00 X-Proofpoint-GUID: 3aceIl_XT_z6NodZFYhmsURJaAM4B_Lr X-Proofpoint-ORIG-GUID: yazZMEB_fBssGBbrBYBP-81Ez_8L3haT X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.272,Aquarius:18.0.980,Hydra:6.0.619,FMLib:17.11.176.26 definitions=2023-10-17_02,2023-10-17_01,2023-05-22_02 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 bulkscore=0 priorityscore=1501 lowpriorityscore=0 mlxlogscore=999 suspectscore=0 malwarescore=0 clxscore=1015 adultscore=0 impostorscore=0 mlxscore=0 phishscore=0 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2309180000 definitions=main-2310170113 X-Spam-Status: No, score=-12.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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Hello Richard: Below review comments are incorporated in version 10 of the patch, Please review and let me know if its okay for trunk. Thanks & Regards Ajit On 17/10/23 2:47 pm, Richard Biener wrote: > On Tue, Oct 17, 2023 at 10:53 AM Ajit Agarwal wrote: >> >> Hello Richard: >> >> On 17/10/23 2:03 pm, Richard Biener wrote: >>> On Thu, Oct 12, 2023 at 10:42 AM Ajit Agarwal wrote: >>>> >>>> This patch improves code sinking pass to sink statements before call to reduce >>>> register pressure. >>>> Review comments are incorporated. Synced and modified with latest trunk sources. >>>> >>>> For example : >>>> >>>> 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; >>>> } >>>> } >>>> >>>> Code Sinking does the following: >>>> >>>> void bar(); >>>> int j; >>>> void foo(int a, int b, int c, int d, int e, int f) >>>> { >>>> int l; >>>> >>>> if (a != 5) >>>> { >>>> l = a + b + c + d +e + f; >>>> bar(); >>>> j = l; >>>> } >>>> } >>>> >>>> Bootstrapped regtested on powerpc64-linux-gnu. >>>> >>>> Thanks & Regards >>>> Ajit >>>> >>>> tree-ssa-sink: Improve code sinking pass >>>> >>>> Currently, code sinking will sink code after function calls. This increases >>>> register pressure for callee-saved registers. The following patch improves >>>> code sinking by placing the sunk code before calls in the use block or in >>>> the immediate dominator of the use blocks. >>> >>> The patch no longer does what the description above says. >> Why you think so. Please let me know. > > You talk about calls above but the patch doesn't do anything about calls. You > also don't do anything about register pressure, rather the effect of > your changes > are to move some stmts by a smaller "distance", whatever effect that has. > >>> >>> More comments below. >>> >>>> 2023-10-12 Ajit Kumar Agarwal >>>> >>>> gcc/ChangeLog: >>>> >>>> PR tree-optimization/81953 >>>> * tree-ssa-sink.cc (statement_sink_location): Move statements before >>>> calls. >>>> (select_best_block): Add heuristics to select the best blocks in the >>>> immediate post dominator. >>>> >>>> gcc/testsuite/ChangeLog: >>>> >>>> PR tree-optimization/81953 >>>> * gcc.dg/tree-ssa/ssa-sink-20.c: New test. >>>> * gcc.dg/tree-ssa/ssa-sink-21.c: New test. >>>> --- >>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 15 ++++++++ >>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c | 19 ++++++++++ >>>> gcc/tree-ssa-sink.cc | 39 ++++++++++++--------- >>>> 3 files changed, 56 insertions(+), 17 deletions(-) >>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c >>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c >>>> >>>> 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..d3b79ca5803 >>>> --- /dev/null >>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c >>>> @@ -0,0 +1,15 @@ >>>> +/* { dg-do compile } */ >>>> +/* { dg-options "-O2 -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 {l_12\s+=\s+_4\s+\+\s+f_11\(D\);\n\s+bar\s+\(\)} sink1 } } */ >>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c >>>> new file mode 100644 >>>> index 00000000000..84e7938c54f >>>> --- /dev/null >>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-22.c >>>> @@ -0,0 +1,19 @@ >>>> +/* { dg-do compile } */ >>>> +/* { dg-options "-O2 -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 {l_13\s+=\s+_4\s+\+\s+f_12\(D\);\n\s+bar\s+\(\)} sink1 } } */ >>>> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc >>>> index a360c5cdd6e..95298bc8402 100644 >>>> --- a/gcc/tree-ssa-sink.cc >>>> +++ b/gcc/tree-ssa-sink.cc >>>> @@ -174,7 +174,8 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) >>>> >>>> /* 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. >>>> + statements. The best basic block should be an immediate dominator of >>>> + best basic block if the use stmt is after the call. >>>> >>>> We want the most control dependent block in the shallowest loop nest. >>>> >>>> @@ -196,6 +197,16 @@ select_best_block (basic_block early_bb, >>>> basic_block best_bb = late_bb; >>>> basic_block temp_bb = late_bb; >>>> int threshold; >>>> + /* Get the sinking threshold. If the statement to be moved has memory >>>> + operands, then increase the threshold by 7% as those are even more >>>> + profitable to avoid, clamping at 100%. */ >>>> + threshold = param_sink_frequency_threshold; >>>> + if (gimple_vuse (stmt) || gimple_vdef (stmt)) >>>> + { >>>> + threshold += 7; >>>> + if (threshold > 100) >>>> + threshold = 100; >>>> + } >>>> >>>> while (temp_bb != early_bb) >>>> { >>>> @@ -204,6 +215,14 @@ select_best_block (basic_block early_bb, >>>> if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb)) >>>> best_bb = temp_bb; >>>> >>>> + /* if we have temp_bb post dominated by use block block then immediate >>>> + * dominator would be our best block. */ >>>> + if (!gimple_vuse (stmt) >>>> + && bb_loop_depth (temp_bb) == bb_loop_depth (early_bb) >>>> + && !(temp_bb->count * 100 >= early_bb->count * threshold) >>>> + && dominated_by_p (CDI_DOMINATORS, late_bb, temp_bb)) >>> >>> this isn't a post-dominance check, in fact this always returns true. This >>> also overrides the best found loop depth which probably means finding >>> both inside the same loop doesn't work. >> >> I can remove dominated check. You would like me to do in different loop than doing inside the same >> loop. Please let me know. >> >> >>> What's the intent of the change? >> >> The purpose of this change is to assign best_bb the immediate dominator if both early_bb and temp_bb have same loop depth. > > So why is the change then not simply > > - if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb)) > + if (bb_loop_depth (temp_bb) <= bb_loop_depth (best_bb)) > best_bb = temp_bb; > > ? Not that I think this is desirable. We want to sink to the least > executed place which > doesn't map 1:1 to loop depth but control flow forks. The heuristic using > basic-block counts is prone to profile errors (but otherwise should cover the > general idea of the existing code). > >> Thanks & Regards >> Ajit >>> >>>> + best_bb = temp_bb; >>>> + >>>> /* Walk up the dominator tree, hopefully we'll find a shallower >>>> loop nest. */ >>>> temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb); >>>> @@ -233,17 +252,6 @@ select_best_block (basic_block early_bb, >>>> && !dominated_by_p (CDI_DOMINATORS, best_bb->loop_father->latch, best_bb)) >>>> return early_bb; >>>> >>>> - /* Get the sinking threshold. If the statement to be moved has memory >>>> - operands, then increase the threshold by 7% as those are even more >>>> - profitable to avoid, clamping at 100%. */ >>>> - threshold = param_sink_frequency_threshold; >>>> - if (gimple_vuse (stmt) || gimple_vdef (stmt)) >>>> - { >>>> - threshold += 7; >>>> - 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) >>>> @@ -430,6 +438,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, >>>> continue; >>>> break; >>>> } >>>> + >>>> use = USE_STMT (one_use); >>>> >>>> if (gimple_code (use) != GIMPLE_PHI) >>>> @@ -439,10 +448,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, >>>> if (sinkbb == frombb) >>>> return false; >>>> >>>> - if (sinkbb == gimple_bb (use)) >>>> - *togsi = gsi_for_stmt (use); >>>> - else >>>> - *togsi = gsi_after_labels (sinkbb); >>>> + *togsi = gsi_after_labels (sinkbb); >>>> >>>> return true; >>>> } >>>> @@ -825,7 +831,6 @@ pass_sink_code::execute (function *fun) >>>> mark_dfs_back_edges (fun); >>>> memset (&sink_stats, 0, sizeof (sink_stats)); >>>> calculate_dominance_info (CDI_DOMINATORS); >>>> - >>>> virtual_operand_live vop_live; >>>> >>>> int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); >>>> -- >>>> 2.39.3 >>>>