From patchwork Wed Dec 8 05:54:14 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xionghu Luo X-Patchwork-Id: 1565085 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=MzA6XsYX; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4J85y06hpZz9sRN for ; Wed, 8 Dec 2021 16:56:08 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BDBA03858426 for ; Wed, 8 Dec 2021 05:56:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BDBA03858426 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638942966; bh=UiOQW7/Sz/EVFDL+vwVRTcsqLrmLXOq/81YhMyS2/48=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=MzA6XsYXIsGYW02fh1WVMZ29YA5KIbJBZY5ShJX1jsCC2kdbLXj/6mRZPVxqC7FYC dIPBj4cjceXk/lB8/VZ4gKPvspXsubBDpPuOci5miz5PEt6CTTDj6/wYlzQ4VZrUSD cqsMGbsWUMEXsF2TH+dwU/lcdk9nWgB2fVUsr+Q0= 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 8AA993858D3C; Wed, 8 Dec 2021 05:54:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8AA993858D3C Received: from pps.filterd (m0098394.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 1B84MSYx032750; Wed, 8 Dec 2021 05:54:49 GMT Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com with ESMTP id 3ctnmg9d5p-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:49 +0000 Received: from m0098394.ppops.net (m0098394.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.43/8.16.0.43) with SMTP id 1B85snxr014842; Wed, 8 Dec 2021 05:54:49 GMT Received: from ppma03ams.nl.ibm.com (62.31.33a9.ip4.static.sl-reverse.com [169.51.49.98]) by mx0a-001b2d01.pphosted.com with ESMTP id 3ctnmg9d57-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:48 +0000 Received: from pps.filterd (ppma03ams.nl.ibm.com [127.0.0.1]) by ppma03ams.nl.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 1B85rrk4029744; Wed, 8 Dec 2021 05:54:46 GMT Received: from b06cxnps3075.portsmouth.uk.ibm.com (d06relay10.portsmouth.uk.ibm.com [9.149.109.195]) by ppma03ams.nl.ibm.com with ESMTP id 3cqyya44qd-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:46 +0000 Received: from d06av21.portsmouth.uk.ibm.com (d06av21.portsmouth.uk.ibm.com [9.149.105.232]) by b06cxnps3075.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 1B85shJX31523114 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 8 Dec 2021 05:54:43 GMT Received: from d06av21.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 4B9F752057; Wed, 8 Dec 2021 05:54:43 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by d06av21.portsmouth.uk.ibm.com (Postfix) with ESMTP id D971152059; Wed, 8 Dec 2021 05:54:41 +0000 (GMT) To: gcc-patches@gcc.gnu.org Subject: [PATCH 1/3] loop-invariant: Don't move cold bb instructions to preheader in RTL Date: Tue, 7 Dec 2021 23:54:14 -0600 Message-Id: <20211208055416.1415283-2-luoxhu@linux.ibm.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211208055416.1415283-1-luoxhu@linux.ibm.com> References: <20211208055416.1415283-1-luoxhu@linux.ibm.com> MIME-Version: 1.0 X-TM-AS-GCONF: 00 X-Proofpoint-GUID: 4KwNhTYVQhiJnWL5kpx97OuVpB5FDQBQ X-Proofpoint-ORIG-GUID: SvS9dBh3-4SaBDSb5N3gpoeEpNXWvtiz X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.790,Hydra:6.0.425,FMLib:17.11.62.513 definitions=2021-12-08_01,2021-12-06_02,2021-12-02_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 mlxscore=0 lowpriorityscore=0 suspectscore=0 priorityscore=1501 clxscore=1015 mlxlogscore=811 phishscore=0 adultscore=0 malwarescore=0 spamscore=0 impostorscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2110150000 definitions=main-2112080038 X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, 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: segher@kernel.crashing.org, Xionghu Luo , hubicka@kam.mff.cuni.cz, wschmidt@linux.ibm.com, linkw@gcc.gnu.org, dje.gcc@gmail.com Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" gcc/ChangeLog: * loop-invariant.c (find_invariants_bb): Check profile count before motion. (find_invariants_body): Add argument. --- gcc/loop-invariant.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c index 5eee2e5c9f8..c61c8612fae 100644 --- a/gcc/loop-invariant.c +++ b/gcc/loop-invariant.c @@ -1183,9 +1183,14 @@ find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed) call. */ static void -find_invariants_bb (basic_block bb, bool always_reached, bool always_executed) +find_invariants_bb (class loop *loop, basic_block bb, bool always_reached, + bool always_executed) { rtx_insn *insn; + basic_block preheader = loop_preheader_edge (loop)->src; + + if (preheader->count > bb->count) + return; FOR_BB_INSNS (bb, insn) { @@ -1214,8 +1219,7 @@ find_invariants_body (class loop *loop, basic_block *body, unsigned i; for (i = 0; i < loop->num_nodes; i++) - find_invariants_bb (body[i], - bitmap_bit_p (always_reached, i), + find_invariants_bb (loop, body[i], bitmap_bit_p (always_reached, i), bitmap_bit_p (always_executed, i)); } From patchwork Wed Dec 8 05:54:15 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xionghu Luo X-Patchwork-Id: 1565086 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=Z4Y3nb8l; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4J85zX0xDyz9t2p for ; Wed, 8 Dec 2021 16:57:27 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id ED340385841E for ; Wed, 8 Dec 2021 05:57:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org ED340385841E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638943045; bh=IXwNQjHtOCpdLX9nzNDKkAVUCviXd8QIGxKtDfk21TY=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=Z4Y3nb8lIg8ssWn/EvAbzUxc7sZeSwyT1/poAjHrvCZ44XvOttcZUifpf2SBiTasa GNZ1MNlG7LwZMsxtidc2qu9frMi7WzsURKBz6Dp45NQeLwF1Bn+mn/6k42FMEURInU NDxkjJwCKg2oaPsUfluMaGJ1ZOZN23ddpL/Yu+3A= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0b-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id 3CA823858C60; Wed, 8 Dec 2021 05:54:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3CA823858C60 Received: from pps.filterd (m0127361.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 1B82Ng7j011033; Wed, 8 Dec 2021 05:54:50 GMT Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com with ESMTP id 3ctkvq3108-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:50 +0000 Received: from m0127361.ppops.net (m0127361.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.43/8.16.0.43) with SMTP id 1B85S9AL002671; Wed, 8 Dec 2021 05:54:50 GMT Received: from ppma06ams.nl.ibm.com (66.31.33a9.ip4.static.sl-reverse.com [169.51.49.102]) by mx0a-001b2d01.pphosted.com with ESMTP id 3ctkvq30yy-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:49 +0000 Received: from pps.filterd (ppma06ams.nl.ibm.com [127.0.0.1]) by ppma06ams.nl.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 1B85qroT003706; Wed, 8 Dec 2021 05:54:48 GMT Received: from b06cxnps4076.portsmouth.uk.ibm.com (d06relay13.portsmouth.uk.ibm.com [9.149.109.198]) by ppma06ams.nl.ibm.com with ESMTP id 3cqykjc7f7-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:48 +0000 Received: from d06av21.portsmouth.uk.ibm.com (d06av21.portsmouth.uk.ibm.com [9.149.105.232]) by b06cxnps4076.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 1B85sisf29884824 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 8 Dec 2021 05:54:45 GMT Received: from d06av21.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id DD37A52050; Wed, 8 Dec 2021 05:54:44 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by d06av21.portsmouth.uk.ibm.com (Postfix) with ESMTP id 7D7945204F; Wed, 8 Dec 2021 05:54:43 +0000 (GMT) To: gcc-patches@gcc.gnu.org Subject: [PATCH 2/3] Fix incorrect loop exit edge probability [PR103270] Date: Tue, 7 Dec 2021 23:54:15 -0600 Message-Id: <20211208055416.1415283-3-luoxhu@linux.ibm.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211208055416.1415283-1-luoxhu@linux.ibm.com> References: <20211208055416.1415283-1-luoxhu@linux.ibm.com> MIME-Version: 1.0 X-TM-AS-GCONF: 00 X-Proofpoint-GUID: Xp2As9Q4dUjwgWL2NNiMZLbyznwgfr18 X-Proofpoint-ORIG-GUID: GNafevTR1IeFYF2M1J6ZyDwGeE3KFNFT X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.790,Hydra:6.0.425,FMLib:17.11.62.513 definitions=2021-12-08_01,2021-12-06_02,2021-12-02_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 malwarescore=0 mlxlogscore=926 phishscore=0 impostorscore=0 adultscore=0 spamscore=0 mlxscore=0 clxscore=1015 bulkscore=0 suspectscore=0 priorityscore=1501 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2110150000 definitions=main-2112080038 X-Spam-Status: No, score=-11.2 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.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: segher@kernel.crashing.org, Xionghu Luo , hubicka@kam.mff.cuni.cz, wschmidt@linux.ibm.com, linkw@gcc.gnu.org, dje.gcc@gmail.com Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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 on P8LE, 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 3cb4e3c0eb5..5b6e0cf722b 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); } } @@ -2008,7 +2010,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"} } */ From patchwork Wed Dec 8 05:54:16 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xionghu Luo X-Patchwork-Id: 1565087 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=MSyJArlY; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4J860J5Y9Jz9t2p for ; Wed, 8 Dec 2021 16:58:08 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8CAE33858424 for ; Wed, 8 Dec 2021 05:58:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8CAE33858424 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638943086; bh=ifC9K9L5DU9W7Uksl+ByeJjYRVPe2Kh52y35psImwBI=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=MSyJArlYpy68UoRKpcM7tpCGoJeNnTCTkvplG6KGPWTVJ+Nrh6B387PutBTJWNY16 uvvC2Cbc6tBAFbDEhQ/OJUuhHccPonnvY3TC9BF5tgTZUZWpSVh4DkAgsD1PcVkcvF PH+TqsxAP4KphfNb7Dj/RS6s+YI4EoJq3dxhQpzc= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id E0C393858412; Wed, 8 Dec 2021 05:54:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E0C393858412 Received: from pps.filterd (m0098420.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 1B85MWm0000632; Wed, 8 Dec 2021 05:54:52 GMT Received: from pps.reinject (localhost [127.0.0.1]) by mx0b-001b2d01.pphosted.com with ESMTP id 3ctpgm8f9e-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:52 +0000 Received: from m0098420.ppops.net (m0098420.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.43/8.16.0.43) with SMTP id 1B85spQY018356; Wed, 8 Dec 2021 05:54:51 GMT Received: from ppma02fra.de.ibm.com (47.49.7a9f.ip4.static.sl-reverse.com [159.122.73.71]) by mx0b-001b2d01.pphosted.com with ESMTP id 3ctpgm8f96-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:51 +0000 Received: from pps.filterd (ppma02fra.de.ibm.com [127.0.0.1]) by ppma02fra.de.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 1B85r2Qi008021; Wed, 8 Dec 2021 05:54:50 GMT Received: from b06avi18626390.portsmouth.uk.ibm.com (b06avi18626390.portsmouth.uk.ibm.com [9.149.26.192]) by ppma02fra.de.ibm.com with ESMTP id 3cqyy9jtw5-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 08 Dec 2021 05:54:49 +0000 Received: from d06av21.portsmouth.uk.ibm.com (d06av21.portsmouth.uk.ibm.com [9.149.105.232]) by b06avi18626390.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 1B85l43F28836286 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 8 Dec 2021 05:47:04 GMT Received: from d06av21.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 7192F5205A; Wed, 8 Dec 2021 05:54:46 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by d06av21.portsmouth.uk.ibm.com (Postfix) with ESMTP id 19EE45204F; Wed, 8 Dec 2021 05:54:44 +0000 (GMT) To: gcc-patches@gcc.gnu.org Subject: [PATCH 3/3] Fix loop split incorrect count and probability Date: Tue, 7 Dec 2021 23:54:16 -0600 Message-Id: <20211208055416.1415283-4-luoxhu@linux.ibm.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211208055416.1415283-1-luoxhu@linux.ibm.com> References: <20211208055416.1415283-1-luoxhu@linux.ibm.com> MIME-Version: 1.0 X-TM-AS-GCONF: 00 X-Proofpoint-GUID: DB0MAfS6KPw_rQt7xBhesvQy3SBOcfxy X-Proofpoint-ORIG-GUID: mLdglNlF-heKyRWfTftMnekHIhaMMcdc X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.790,Hydra:6.0.425,FMLib:17.11.62.513 definitions=2021-12-08_01,2021-12-06_02,2021-12-02_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 clxscore=1015 impostorscore=0 adultscore=0 suspectscore=0 lowpriorityscore=0 malwarescore=0 phishscore=0 bulkscore=0 mlxlogscore=999 priorityscore=1501 mlxscore=0 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2110150000 definitions=main-2112080038 X-Spam-Status: No, score=-11.2 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.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: segher@kernel.crashing.org, Xionghu Luo , hubicka@kam.mff.cuni.cz, wschmidt@linux.ibm.com, linkw@gcc.gnu.org, dje.gcc@gmail.com Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" In tree-ssa-loop-split.c, split_loop and split_loop_on_cond does two kind of split. split_loop only works for single loop and insert edge at exit when split, while split_loop_on_cond is not limited to single loop and insert edge at latch when split. Both split behavior should consider loop count and probability update. For split_loop, loop split condition is moved in front of loop1 and loop2; But split_loop_on_cond moves the condition between loop1 and loop2, this patch does: 1) profile count proportion for both original loop and copied loop without dropping down the true branch's count; 2) probability update in the two loops and between the two loops. Regression tested pass, OK for master? Changes diff for split_loop and split_loop_on_cond cases: 1) diff base/loop-split.c.151t.lsplit patched/loop-split.c.152t.lsplit ... [local count: 118111600]: if (beg_5(D) < end_8(D)) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: if (beg2_6(D) < c_9(D)) - goto ; [100.00%] + goto ; [33.00%] else - goto ; [100.00%] + goto ; [67.00%] - [local count: 105119324]: + [local count: 34689377]: _25 = beg_5(D) + 1; _26 = end_8(D) - beg_5(D); _27 = beg2_6(D) + _26; _28 = MIN_EXPR ; - [local count: 955630225]: + [local count: 315357973]: # i_16 = PHI # j_17 = PHI printf ("a: %d %d\n", i_16, j_17); i_11 = i_16 + 1; j_12 = j_17 + 1; if (j_12 < _28) - goto ; [89.00%] + goto ; [29.37%] else - goto ; [11.00%] + goto ; [70.63%] - [local count: 850510901]: + [local count: 280668596]: goto ; [100.00%] - [local count: 105119324]: + [local count: 70429947]: # i_22 = PHI # j_23 = PHI [local count: 955630225]: # i_2 = PHI # j_1 = PHI i_20 = i_2 + 1; j_21 = j_1 + 1; if (end_8(D) > i_20) - goto ; [89.00%] + goto ; [59.63%] else - goto ; [11.00%] + goto ; [40.37%] - [local count: 850510901]: + [local count: 569842305]: goto ; [100.00%] [local count: 105119324]: # i_29 = PHI # j_30 = PHI if (end_8(D) > i_29) goto ; [80.00%] else goto ; [20.00%] [local count: 105119324]: [local count: 118111600]: return 0; } [local count: 118111600]: - if (beg_5(D) < end_8(D)) + _1 = end_6(D) - beg_7(D); + j_9 = _1 + beg2_8(D); + if (end_6(D) > beg_7(D)) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: - if (beg2_6(D) < c_9(D)) - goto ; [100.00%] + if (j_9 >= c_11(D)) + goto ; [33.00%] else - goto ; [100.00%] + goto ; [67.00%] - [local count: 105119324]: - _25 = beg_5(D) + 1; - _26 = end_8(D) - beg_5(D); - _27 = beg2_6(D) + _26; - _28 = MIN_EXPR ; - - [local count: 955630225]: - # i_16 = PHI - # j_17 = PHI - printf ("a: %d %d\n", i_16, j_17); - i_11 = i_16 + 1; - j_12 = j_17 + 1; - if (j_12 < _28) - goto ; [89.00%] + [local count: 34689377]: + _27 = end_6(D) + -1; + _28 = beg_7(D) - end_6(D); + _29 = j_9 + _28; + _30 = _29 + 1; + _31 = MAX_EXPR ; + + [local count: 315357973]: + # i_18 = PHI + # j_19 = PHI + printf ("a: %d %d\n", i_18, j_19); + i_13 = i_18 + -1; + j_14 = j_19 + -1; + if (j_14 >= _31) + goto ; [29.37%] else - goto ; [11.00%] + goto ; [70.63%] - [local count: 850510901]: + [local count: 280668596]: goto ; [100.00%] - [local count: 105119324]: - # i_22 = PHI - # j_23 = PHI + [local count: 70429947]: + # i_24 = PHI + # j_25 = PHI [local count: 955630225]: - # i_2 = PHI - # j_1 = PHI - i_20 = i_2 + 1; - j_21 = j_1 + 1; - if (end_8(D) > i_20) + # i_3 = PHI + # j_2 = PHI + i_22 = i_3 + -1; + j_23 = j_2 + -1; + if (beg_7(D) < i_22) goto ; [89.00%] else goto ; [11.00%] - [local count: 850510901]: + [local count: 569842305]: goto ; [100.00%] [local count: 105119324]: - # i_29 = PHI - # j_30 = PHI - if (end_8(D) > i_29) + # i_32 = PHI + # j_33 = PHI + if (beg_7(D) < i_32) goto ; [80.00%] else goto ; [20.00%] [local count: 105119324]: [local count: 118111600]: return 0; } 2) diff base/loop-cond-split-1.c.151t.lsplit patched/loop-cond-split-1.c.151t.lsplit: ... [local count: 118111600]: if (n_7(D) > 0) goto ; [89.00%] else goto ; [11.00%] [local count: 118111600]: return; [local count: 105119324]: pretmp_3 = ga; - [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]: _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%] } gcc/ChangeLog: * tree-ssa-loop-split.c (split_loop): Fix incorrect profile_count and probability. (do_split_loop_on_cond): Likewise. --- gcc/tree-ssa-loop-split.c | 85 +++++++++++++++++++++++++++++++++++---- 1 file changed, 77 insertions(+), 8 deletions(-) diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c index 3f6ad046623..33128061aab 100644 --- a/gcc/tree-ssa-loop-split.c +++ b/gcc/tree-ssa-loop-split.c @@ -575,7 +575,10 @@ split_loop (class loop *loop1) stmts2); tree cond = build2 (guard_code, boolean_type_node, guard_init, border); if (!initial_true) - cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond); + cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond); + + edge true_edge, false_edge; + extract_true_false_edges_from_block (bbs[i], &true_edge, &false_edge); /* Now version the loop, placing loop2 after loop1 connecting them, and fix up SSA form for that. */ @@ -583,11 +586,11 @@ split_loop (class loop *loop1) basic_block cond_bb; class loop *loop2 = loop_version (loop1, cond, &cond_bb, - profile_probability::always (), - profile_probability::always (), - profile_probability::always (), - profile_probability::always (), - true); + true_edge->probability, + true_edge->probability.invert (), + profile_probability::always (), + profile_probability::always (), + true); gcc_assert (loop2); edge new_e = connect_loops (loop1, loop2); @@ -607,6 +610,38 @@ split_loop (class loop *loop1) tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1)); patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true); + update_ssa (TODO_update_ssa); + + /* Proportion first loop's bb counts except those dominated by true + branch to avoid drop 1s down. */ + basic_block *bbs1, *bbs2; + bbs1 = get_loop_body (loop1); + unsigned j; + for (j = 0; j < loop1->num_nodes; j++) + if (bbs1[j] == loop1->latch + || !dominated_by_p (CDI_DOMINATORS, bbs1[j], true_edge->dest)) + bbs1[j]->count + = bbs1[j]->count.apply_probability (true_edge->probability); + free (bbs1); + + /* Fix first loop's exit probability after scaling. */ + edge exit_to_latch1 = single_pred_edge (loop1->latch); + exit_to_latch1->probability = exit_to_latch1->probability.apply_scale ( + true_edge->probability.to_reg_br_prob_base (), REG_BR_PROB_BASE); + single_exit (loop1)->probability + = exit_to_latch1->probability.invert (); + + /* Proportion second loop's bb counts except those dominated by false + branch to avoid drop 1s down. */ + basic_block bbi_copy = get_bb_copy (false_edge->dest); + bbs2 = get_loop_body (loop2); + for (j = 0; j < loop2->num_nodes; j++) + if (bbs2[j] == loop2->latch + || !dominated_by_p (CDI_DOMINATORS, bbs2[j], bbi_copy)) + bbs2[j]->count = bbs2[j]->count.apply_probability ( + true_edge->probability.invert ()); + free (bbs2); + /* Finally patch out the two copies of the condition to be always true/false (or opposite). */ gcond *force_true = as_a (last_stmt (bbs[i])); @@ -1486,8 +1521,8 @@ do_split_loop_on_cond (struct loop *loop1, edge invar_branch) initialize_original_copy_tables (); struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL, - profile_probability::always (), - profile_probability::never (), + invar_branch->probability.invert (), + invar_branch->probability, profile_probability::always (), profile_probability::always (), true); @@ -1535,6 +1570,40 @@ do_split_loop_on_cond (struct loop *loop1, edge invar_branch) between loop1 and loop2. */ connect_loop_phis (loop1, loop2, to_loop2); + update_ssa (TODO_update_ssa); + + edge true_edge, false_edge, skip_edge1, skip_edge2; + extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); + + /* Proportion first loop's bb counts except those dominated by true + branch to avoid drop 1s down. */ + skip_edge1 = true_invar ? false_edge : true_edge; + skip_edge2 = true_invar ? true_edge : false_edge; + basic_block *bbs1, *bbs2; + bbs1 = get_loop_body (loop1); + unsigned j; + for (j = 0; j < loop1->num_nodes; j++) + if (bbs1[j] == loop1->latch + || !dominated_by_p (CDI_DOMINATORS, bbs1[j], skip_edge1->dest)) + bbs1[j]->count + = bbs1[j]->count.apply_probability (skip_edge1->probability); + free (bbs1); + + /* Fix first loop's exit probability after scaling. */ + to_loop1->probability = invar_branch->probability.invert (); + to_loop2->probability = invar_branch->probability; + + /* Proportion second loop's bb counts except those dominated by false + branch to avoid drop 1s down. */ + basic_block bbi_copy = get_bb_copy (skip_edge2->dest); + bbs2 = get_loop_body (loop2); + for (j = 0; j < loop2->num_nodes; j++) + if (bbs2[j] == loop2->latch + || !dominated_by_p (CDI_DOMINATORS, bbs2[j], bbi_copy)) + bbs2[j]->count + = bbs2[j]->count.apply_probability (skip_edge2->probability); + free (bbs2); + free_original_copy_tables (); return true;