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 1314C3858405; Wed, 27 Oct 2021 01:43:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1314C3858405 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 19R0Hn2h005309; Wed, 27 Oct 2021 01:43:00 GMT Received: from ppma03fra.de.ibm.com (6b.4a.5195.ip4.static.sl-reverse.com [149.81.74.107]) by mx0a-001b2d01.pphosted.com with ESMTP id 3bxv3t9v7y-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 27 Oct 2021 01:43:00 +0000 Received: from pps.filterd (ppma03fra.de.ibm.com [127.0.0.1]) by ppma03fra.de.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 19R1WKDq008270; Wed, 27 Oct 2021 01:42:57 GMT Received: from b06cxnps4074.portsmouth.uk.ibm.com (d06relay11.portsmouth.uk.ibm.com [9.149.109.196]) by ppma03fra.de.ibm.com with ESMTP id 3bx4epsdvd-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 27 Oct 2021 01:42:57 +0000 Received: from d06av25.portsmouth.uk.ibm.com (d06av25.portsmouth.uk.ibm.com [9.149.105.61]) by b06cxnps4074.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 19R1gsU861341986 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 27 Oct 2021 01:42:54 GMT Received: from d06av25.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 40FE411C058; Wed, 27 Oct 2021 01:42:54 +0000 (GMT) Received: from d06av25.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id BC9AB11C04A; Wed, 27 Oct 2021 01:42:51 +0000 (GMT) Received: from [9.200.154.17] (unknown [9.200.154.17]) by d06av25.portsmouth.uk.ibm.com (Postfix) with ESMTPS; Wed, 27 Oct 2021 01:42:51 +0000 (GMT) Message-ID: Date: Wed, 27 Oct 2021 09:42:49 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.2.1 Subject: Re: [PATCH] Fix loop split incorrect count and probability Content-Language: en-US To: Jan Hubicka , Feng Xue OS Cc: Richard Biener , "gcc-patches@gcc.gnu.org" , "segher@kernel.crashing.org" , "wschmidt@linux.ibm.com" , "guojiufu@linux.ibm.com" , "linkw@gcc.gnu.org" References: <20210803085813.2217766-1-luoxhu@linux.ibm.com> <58f9e351-fc10-406e-5272-270ece73be71@linux.ibm.com> <20211026130523.GA49464@kam.mff.cuni.cz> From: Xionghu Luo In-Reply-To: <20211026130523.GA49464@kam.mff.cuni.cz> Content-Type: text/plain; charset=UTF-8 X-TM-AS-GCONF: 00 X-Proofpoint-GUID: Y_lL38b-VcthT6OZwQfrUabrc_sOtD8h X-Proofpoint-ORIG-GUID: Y_lL38b-VcthT6OZwQfrUabrc_sOtD8h Content-Transfer-Encoding: 7bit X-Proofpoint-UnRewURL: 0 URL was un-rewritten MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.790,Hydra:6.0.425,FMLib:17.0.607.475 definitions=2021-10-26_07,2021-10-26_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 malwarescore=0 bulkscore=0 spamscore=0 lowpriorityscore=0 mlxlogscore=999 clxscore=1011 phishscore=0 impostorscore=0 mlxscore=0 adultscore=0 priorityscore=1501 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2110150000 definitions=main-2110270006 X-Spam-Status: No, score=-5.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, KAM_SHORT, NICE_REPLY_A, RCVD_IN_MSPIKE_H2, 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-List-Received-Date: Wed, 27 Oct 2021 01:43:05 -0000 On 2021/10/26 21:05, Jan Hubicka wrote: >>> > >> That said, likely the profile update cannot be done uniformly >> for all blocks of a loop? > > For the loop: > > for (i = 0; i < n; i = inc (i)) > { > if (ga) > ga = do_something (); > } > > to: > > for (i = 0; i < x; i = inc (i)) > { > if (true) > ga = do_something (); > if (!ga) > break; > } > for (; i < n; i = inc (i)) > { > if (false) > ga = do_something (); > } > > If probability of if (ga) being true is p, then you indeed can scale the > first loop by p and second loop by 1-p. > > Imagine that loop has n iterations and it takes m iterations for ga to > become false, then probability of if(ga) is m/n and you get frequencies > with m=n*(m/n) for first loop and n-m=n*(1-n/m) for second loop. > > Because the conditional becomes constant true, one needs to scale up the > basic block guarded by the if (true) up by n/m to compensate for the > change. With that the udpate should be right. > Ideally one can bypass scaling of basic block(s) containing > ga = do_something () since the scaling first scales down to m/n > and then scale sup to m/n. Which may not combine to noop. > Perhaps one wants to have a parameter specifying basic blocks on which > the scaling is performed while duplicating for this? Yes. This is the patch I tried to fix the issue for the case you pasted for loop split. https://gcc.gnu.org/pipermail/gcc-patches/2021-August/576566.html 5<---------------- | \ | 6-- 7 | | \ | 21 11->3 | | \ | 19 20---------- | 12<---- / | | 3<-11 16-- with the patch, Loop 1's bb {5,6,7,21,20} is scaled to 33% * count, Loop 2's bb {12,16} is scaled to 66% * count, especially, probability of edge 21->19 and 21->20 is fixed to (33%, 67%) instead of (100%, INV). - [local count: 955630225]: + [local count: 315357973]: # i_13 = PHI # prephitmp_12 = PHI if (prephitmp_12 != 0) goto ; [33.00%] else goto ; [67.00%] - [local count: 315357972]: + [local count: 104068130]: _2 = do_something (); ga = _2; - [local count: 955630225]: + [local count: 315357973]: # prephitmp_5 = PHI i_10 = inc (i_13); if (n_7(D) > i_10) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: goto ; [100.00%] - [local count: 850510901]: + [local count: 280668596]: if (prephitmp_12 != 0) - goto ; [100.00%] + goto ; [33.00%] else - goto ; [INV] + goto ; [67.00%] - [local count: 850510901]: + [local count: 280668596]: goto ; [100.00%] - [count: 0]: + [local count: 70429947]: # i_23 = PHI # prephitmp_25 = PHI - [local count: 955630225]: + [local count: 640272252]: # i_15 = PHI # prephitmp_16 = PHI i_22 = inc (i_15); if (n_7(D) > i_22) goto ; [89.00%] else goto ; [11.00%] - [local count: 850510901]: + [local count: 569842305]: goto ; [100.00%] > > Honza >> >> Richard. -- Thanks, Xionghu