From patchwork Wed Nov 24 05:03:35 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xionghu Luo X-Patchwork-Id: 48048 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 871F23858023 for ; Wed, 24 Nov 2021 05:04:18 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 871F23858023 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1637730258; bh=uOtbP6qY+IWuMgIyHndIboKtXow4WwLj5HnCYrRqXQY=; h=Date:Subject:To:References:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=xkyX0b2WtFGJXs26JdSzMf4a0yTKX5xOeNZGdALLtyHXQ4KosjAS3mCWKdTsKNMAz sF5iS2qFc0n3UY0qlBOd3aWM6s6eTdms7ChbJTF8EwmoPrYLMqixVDRMGZh4j+njPL qjGsLQ1jb00m4K5CGHRKwdM22iIGVLDpUSkSMs94= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id 6DEE8385840B; Wed, 24 Nov 2021 05:03:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6DEE8385840B Received: from pps.filterd (m0098410.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 1AO4MbcP030815; Wed, 24 Nov 2021 05:03:45 GMT Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com with ESMTP id 3cheajgjn3-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 24 Nov 2021 05:03:44 +0000 Received: from m0098410.ppops.net (m0098410.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.43/8.16.0.43) with SMTP id 1AO527lJ019969; Wed, 24 Nov 2021 05:03:44 GMT Received: from ppma04ams.nl.ibm.com (63.31.33a9.ip4.static.sl-reverse.com [169.51.49.99]) by mx0a-001b2d01.pphosted.com with ESMTP id 3cheajgjmb-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 24 Nov 2021 05:03:44 +0000 Received: from pps.filterd (ppma04ams.nl.ibm.com [127.0.0.1]) by ppma04ams.nl.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 1AO53Bdx026201; Wed, 24 Nov 2021 05:03:41 GMT Received: from b06cxnps3074.portsmouth.uk.ibm.com (d06relay09.portsmouth.uk.ibm.com [9.149.109.194]) by ppma04ams.nl.ibm.com with ESMTP id 3cernaweag-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 24 Nov 2021 05:03:41 +0000 Received: from d06av23.portsmouth.uk.ibm.com (d06av23.portsmouth.uk.ibm.com [9.149.105.59]) by b06cxnps3074.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 1AO53d0710158342 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 24 Nov 2021 05:03:39 GMT Received: from d06av23.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 6F017A4053; Wed, 24 Nov 2021 05:03:39 +0000 (GMT) Received: from d06av23.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 5F23CA404D; Wed, 24 Nov 2021 05:03:37 +0000 (GMT) Received: from [9.200.154.17] (unknown [9.200.154.17]) by d06av23.portsmouth.uk.ibm.com (Postfix) with ESMTPS; Wed, 24 Nov 2021 05:03:37 +0000 (GMT) Message-ID: Date: Wed, 24 Nov 2021 13:03:35 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.3.1 Subject: [PATCH v2] Fix incorrect loop exit edge probability [PR103270] Content-Language: en-US To: Jan Hubicka , Richard Biener References: <20211123055145.475825-1-luoxhu@linux.ibm.com> <20211123095005.GB63195@kam.mff.cuni.cz> In-Reply-To: <20211123095005.GB63195@kam.mff.cuni.cz> X-TM-AS-GCONF: 00 X-Proofpoint-GUID: 43AZVMABQmHJaU01EWvxsZPUfoBtaEHc X-Proofpoint-ORIG-GUID: p53w83FGrDzFPAy1ZvuTJQPBQpBGrDN1 X-Proofpoint-UnRewURL: 0 URL was un-rewritten MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.790,Hydra:6.0.425,FMLib:17.0.607.475 definitions=2021-11-24_01,2021-11-23_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 phishscore=0 lowpriorityscore=0 priorityscore=1501 clxscore=1015 mlxlogscore=999 mlxscore=0 bulkscore=0 spamscore=0 malwarescore=0 impostorscore=0 suspectscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2110150000 definitions=main-2111240029 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, 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-Patchwork-Original-From: Xionghu Luo via Gcc-patches From: Xionghu Luo Reply-To: Xionghu Luo Cc: GCC Patches , David Edelsohn , Bill Schmidt , linkw@gcc.gnu.org, Segher Boessenkool Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" On 2021/11/23 17:50, Jan Hubicka wrote: >> On Tue, Nov 23, 2021 at 6:52 AM Xionghu Luo wrote: >>> >>> r12-4526 cancelled jump thread path rotates loop. It exposes a issue in >>> profile-estimate when predict_extra_loop_exits, outer loop's exit edge >>> is marked as inner loop's extra loop exit and set with incorrect >>> prediction, then a hot inner loop will become cold loop finally through >>> optimizations, this patch ignores the EDGE_DFS_BACK edge when searching >>> extra exit edges to avoid unexpected predict_edge. >> >> Not sure how outer vs. inner loop exit correlates with EDGE_DFS_BACK, >> I have expected a check based on which loop is exited by the edge instead? >> A backedge should never be an exit, no? >> >> Note that the profile pass does not yet mark backedges so EDGE_DFS_BACK >> settings are unreliable. > > So we have two nested loops and an exit which goes from inner loop and > exists both loops. While processing outer loop we set pretty high exit > probability that is not good for inner loop? No, the edge only belongs to outer loop only. Can an exit edge belongs to two different loops at the same time? Exit edges are iterated with LI_FROM_INNERMOST in predict_loops, if an edge already has prediction by querying edge_predicted_by_p, maybe_predict_edge will early return to not set it again. The CFG is: 2 | 8<---- // l1 | \ | 10 9 | | | ----7 6 <---- // l2 | | 11 | | | 4<- | // l3 | \| | 5 3 | | | ------ l2's edge (6->11,6->7) is set to (33%,67%) by l3 unexpectedly. FYI: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103270#c5 > > I guess we could just check if exit edge source basic block has same > loop depth as the loop we are processing? > Thanks for the suggestion, it works. Loop checks already existed in predict_paths_for_bb, just need pass down the loop argument. Updated as v2 patch. v2-0001-Fix-incorrect-loop-exit-edge-probability-PR103270.patch r12-4526 cancelled jump thread path rotates loop. It exposes a issue in profile-estimate when predict_extra_loop_exits, outer loop's exit edge is marked as inner loop's extra loop exit and set with incorrect prediction, then a hot inner loop will become cold loop finally through optimizations, this patch add loop check when searching extra exit edges to avoid unexpected predict_edge from predict_paths_for_bb. Regression tested pass on P8 & x86, OK for master? gcc/ChangeLog: PR middle-end/103270 * predict.c (predict_extra_loop_exits): Add loop parameter. (predict_loops): Call with loop argument. gcc/testsuite/ChangeLog: PR middle-end/103270 * gcc.dg/pr103270.c: New test. --- gcc/predict.c | 10 ++++++---- gcc/testsuite/gcc.dg/pr103270.c | 19 +++++++++++++++++++ 2 files changed, 25 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr103270.c diff --git a/gcc/predict.c b/gcc/predict.c index 68b11135680..082782ec4e9 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -1859,7 +1859,7 @@ predict_iv_comparison (class loop *loop, basic_block bb, exits to predict them using PRED_LOOP_EXTRA_EXIT. */ static void -predict_extra_loop_exits (edge exit_edge) +predict_extra_loop_exits (class loop *loop, edge exit_edge) { unsigned i; bool check_value_one; @@ -1912,12 +1912,14 @@ predict_extra_loop_exits (edge exit_edge) continue; if (EDGE_COUNT (e->src->succs) != 1) { - predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN); + predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN, + loop); continue; } FOR_EACH_EDGE (e1, ei, e->src->preds) - predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN); + predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN, + loop); } } @@ -2009,7 +2011,7 @@ predict_loops (void) ex->src->index, ex->dest->index); continue; } - predict_extra_loop_exits (ex); + predict_extra_loop_exits (loop, ex); if (number_of_iterations_exit (loop, ex, &niter_desc, false, false)) niter = niter_desc.niter; diff --git a/gcc/testsuite/gcc.dg/pr103270.c b/gcc/testsuite/gcc.dg/pr103270.c new file mode 100644 index 00000000000..819310e360e --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr103270.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +void test(int a, int* i) +{ + for (; a < 5; ++a) + { + int b = 0; + int c = 0; + for (; b != -11; b--) + for (int d = 0; d ==0; d++) + { + *i += c & a; + c = b; + } + } +} + +/* { dg-final { scan-tree-dump-not "extra loop exit heuristics of edge\[^:\]*:" "profile_estimate"} } */