From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from NAM12-BN8-obe.outbound.protection.outlook.com (mail-bn8nam12on2092.outbound.protection.outlook.com [40.107.237.92]) by sourceware.org (Postfix) with ESMTPS id 2E067386EC2F; Mon, 9 Aug 2021 04:33:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2E067386EC2F ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=OeIW7NjD55UfX0CBJkCKE9Z/hSU7/vnAWU5x2KKTFsOZhYdsd5OEMkzAPlUYS1CEDPV4OqpSM/N1/1D1ll/wv0iHFnFjhsnsGnBPmO0WqGpslroRJViAccx5Glfsu15vk+UFR3kF8jz0Gpeh+kw4mn9pL2W05XPzgGKsnkgiHf3226k2QhmDFfHrrlcIx2wHrKWq//95qoJ3SXqpTUAqf+gRagvTT4IFUofiBFrpIenuyt40z0WbG8emMAP26ilwpQJMKcmNKjUtskUh0b6cvASvGpZWyKIo4/L8Ffvp8wNroNisQlrOlOSUPVbnCWD8uoBMhWMzPn3oTCT4Qoarjw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Wjh2/h04YEH6FtuDdx3TJjiRGDsEOFfxhDtPK4t7iGg=; b=mAp2Y712ogcZiqr+Es1qqaa/rsX1xz/U9RR1+YNMOpqS+YhDL4hhLNa5YHOBUqmCcEpP8FEVQ34ds5xjP0la3SCf0sAomyAhMOUB91VE1OQ/tAqAC+1zAew1ggPL4Rxvv6jx82rxU+Fo7pvTh4qnYjNyw9y8TQ8fVPx6+2MHSxx8JEFPa3+HG+ARZHZH1lD7wggH8Ltc4ktvXql09m+B641ZK7lieRY07jXoYAohRS52jrtAfry448E/tlHIqIDUzPFLDcCzOrFN5RUolgw+Mymqw8dZKmNjSDn8b+Z/0HTfcxGYVSRZtgA8oRkYvJldHGuN0VGVjVAkGGj+5MDSpg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=os.amperecomputing.com; dmarc=pass action=none header.from=os.amperecomputing.com; dkim=pass header.d=os.amperecomputing.com; arc=none Received: from SN6PR01MB4958.prod.exchangelabs.com (2603:10b6:805:c1::15) by SN6PR01MB4544.prod.exchangelabs.com (2603:10b6:805:ea::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4394.19; Mon, 9 Aug 2021 04:33:19 +0000 Received: from SN6PR01MB4958.prod.exchangelabs.com ([fe80::c49e:d520:c095:a631]) by SN6PR01MB4958.prod.exchangelabs.com ([fe80::c49e:d520:c095:a631%3]) with mapi id 15.20.4394.022; Mon, 9 Aug 2021 04:33:19 +0000 From: Feng Xue OS To: Xionghu Luo , Richard Biener CC: "segher@kernel.crashing.org" , "wschmidt@linux.ibm.com" , "linkw@gcc.gnu.org" , "gcc-patches@gcc.gnu.org" , "hubicka@ucw.cz" , "dje.gcc@gmail.com" Subject: Re: [PATCH] Fix loop split incorrect count and probability Thread-Topic: [PATCH] Fix loop split incorrect count and probability Thread-Index: AQHXiEXTWKpj+O9eGEaGVcY8GBLnfatmYNQAgAQtgTI= Date: Mon, 9 Aug 2021 04:33:19 +0000 Message-ID: References: <20210803085813.2217766-1-luoxhu@linux.ibm.com>, In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 23da1d6a-6702-47db-aa45-08d95aeed078 x-ms-traffictypediagnostic: SN6PR01MB4544: x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:10000; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: 7gDtaYUptzuT9Prt1QUnHs8fkwnRMgi+I20IcDyH5MrMhMvsBEpmhl722gq1xqXWlEhlVMWex84YX+s8EtPKJ+KiTPG8IbaE1S62eE54vPcgzKCgFng4+Za4Vvvu1MMqc2O2EA+FVFnXVcjLa6CjwcFrKFv6VpP+M5SRjfe0x0en91ZB1l5Auni5uLRHLjfU666HDI3IeBTjG23xMQoiWK5lIjDkSzPVF3ZFr2zy1LMJBAiukbMg0MiNeOzE5VUgfOOpQuzlYKtL27qvD4dY28g7pF29KHtlLyUfBpiX/2dg88BMQJ+if+8Ba7IFRgUbGS3N1UT47sbQMBfsZZHmt8wDfW4BMpwnuNsCLRLchsRg7v9Nn8OlOSXdIRfTHfCTZSRgBUL9FxrXdov60t5/r3PsnLawVVm9Ciy8QD6RLTpvVUU12l6dHGdQ1fmisa3YAdeQjjzRv+ENwONqRMx7yyfRmRXJnRtXsc3V9IEpDNzG5iNj70QUPnCHv8ys6tgprMrptyB+4mRIi89CwLUMWgQOtI52Bt/no+x5fNXjxQ1YlaysMJcy1ejETZK2BRFInGkb6Zwfzj5c0sWMcwJGhvu0TTMSwhQv65WBYB0RX128uzsYPfe/4Po9DKpHKztKBwqJ/oUEao6tDS0TBlv0l+Z+iNO1kZTd2dhgDbg6eYa0bdXglE/ulpZR62Y9fuCLVgNXPFS37FW9obDTRWVTlQ== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:SN6PR01MB4958.prod.exchangelabs.com; PTR:; CAT:NONE; SFS:(4636009)(366004)(376002)(136003)(39830400003)(346002)(396003)(2906002)(86362001)(9686003)(83380400001)(55016002)(71200400001)(38070700005)(66476007)(66556008)(186003)(7696005)(122000001)(4326008)(38100700002)(66946007)(33656002)(316002)(5660300002)(6506007)(66446008)(110136005)(76116006)(478600001)(52536014)(8936002)(26005)(53546011)(91956017)(8676002)(54906003)(64756008); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?b4JRevRcw88q2A1KuiXlTo09kAe6Dg2s/QpJsrupsWJUbWO6EpTb1cHsTGqs?= =?us-ascii?Q?0U5UHibaso6WazlcFOZbTYYPmF9kxhECaYn3Wt0jCv0hLNMtVCyJJnpiivM+?= =?us-ascii?Q?1nCZzrMPYWxdqPQ5lpDPoPU7NbTat+iyxWfzQfBavjVl3AEzvcDTbn6Ouk0X?= =?us-ascii?Q?7pyqb+uj4URMkCG1Nh0R0Fk6azEka6Td1FZsgJaNe7ADxnXapgCCDvoF6CaS?= =?us-ascii?Q?3NhNK0eYutKUSf1lbsdUZQ+wnziXKn/kOKbTf5mMtE19w/Snh47GNStGlXg8?= =?us-ascii?Q?k6Qm2SyE3i1BYOlXhFePK7nEMGZrgOXgl1WMwbiowfiEaCKnoMT00sdeR2X9?= =?us-ascii?Q?snNJvkSNE0QTPO5Rg5kRAJ69tbnESbzZg+OIOb5VjU4Fsr9Ljh0EapIDN0cw?= =?us-ascii?Q?/oQooFfJ5eP9pgrcs/q9akEkPT/doz/fcklm5vBzvORYgRB8DoFwy2B1lPCs?= =?us-ascii?Q?ggdLaiQQRZTAmBCsDueduBUqPAcyZbtMhwLCegnAh+qz5FpLMmqp5vE5hu64?= =?us-ascii?Q?W8ZXJQRDM+4/5nbp+wdcggktTSFZU5bl0X+nHxnVR0bS5Xgnt+hAjMfkWrbF?= =?us-ascii?Q?AqXDfkGotYbMh3jpD+LYlenmJQu2jd6sbUM91WN5TAaL2kVwV+3JuWG3Cu1z?= =?us-ascii?Q?3avUYl1PPUdH1Y+a2cSOj5MM0JetxUTQPRDor8EEFgGyy1vntQB2nSOABW//?= =?us-ascii?Q?iKnVrFqgKiPapWtuMwBCm5wbue1tW9O5YUcXP4oQj18oA1vITrg8uZ6Qtzrv?= =?us-ascii?Q?Csxb1i9SKAFC2MG9xISBGZb9Hj1+X4QNZ5Kr9K3uwbOKKMeTNd1vUosiOeb6?= =?us-ascii?Q?1l5oLtb6vmR+ZV52RJC/pzoRDNvVzDPzwvFjd3lFNT2ZChaOYZZXypx3gd5I?= =?us-ascii?Q?KkFaMR2AGmpDhch2v/e+VZxlB3jkfqwkDkCiBdVFmzu/3Kc4NHzH+1yk/Ctx?= =?us-ascii?Q?GUkKXZY030RcKCP7vQycpcLfFvQfGFT7p0DLvbWsiLQLAUA3z5fQ7sRXELr/?= =?us-ascii?Q?cFG3SgTSH0GNu1FB1Qbh0n6hZ+MjNL3DTj5VjqbtYCizE/vX7odyYNxRyT/G?= =?us-ascii?Q?5IyYMbM7dMLTtsyGcpxYI0s8dLzsroHAsLaJAiWnGWDT9ASqL/Mm3dhzJp+R?= =?us-ascii?Q?tDOpZ9hc994Vc6gKbJsQPIFqcSRSmFWswW0HQhY+/89wvbZ+tSD1btAW4TQm?= =?us-ascii?Q?ka8Pdm7JHeHBwZSnfsmHCJjv3EMB9T+be1rRpJzVia6ioOQTiOGsiiSWFHHv?= =?us-ascii?Q?Lm5VA0xdTCubmhFtGjkTA5XmYKVF31LO+Lc/UNyeiN+WR8zpj/HU/1TrwPQJ?= =?us-ascii?Q?pUE=3D?= x-ms-exchange-transport-forked: True Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: os.amperecomputing.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: SN6PR01MB4958.prod.exchangelabs.com X-MS-Exchange-CrossTenant-Network-Message-Id: 23da1d6a-6702-47db-aa45-08d95aeed078 X-MS-Exchange-CrossTenant-originalarrivaltime: 09 Aug 2021 04:33:19.4611 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 3bc2b170-fd94-476d-b0ce-4229bdc904a7 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: fNdQON89DWDmmoSCzLfEtlYFt2cpdJFJkQlqaB7Lk3j2BHYNdDoJN6gAYIw6DR7XU5XWoJXSVINoYdEcnuXigyKntPu/gIosQU3BtK2JjUE= X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR01MB4544 X-Spam-Status: No, score=-11.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, 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: Mon, 09 Aug 2021 04:33:23 -0000 Yes. Condition to to switch two versioned loops is "true", the first two ar= guments should be 100% and 0%. It is different from normal loop split, we could not deduce exactly precise= probability for condition-based loop split, since cfg inside loop2 would be changed. (invar= -branch is replaced to "true", as shown in the comment on do_split_loop_on_cond). Any way, your= way of scaling two loops' probabilities according to that of invar-branch, seems to be a b= etter heuristics than original, which would give us more reasonable execution count, at least for= loop header bb. Thanks, Feng ________________________________________ From: Gcc-patches on behalf of Richard Biener via Gcc-patches Sent: Friday, August 6, 2021 7:46 PM To: Xionghu Luo Cc: segher@kernel.crashing.org; wschmidt@linux.ibm.com; linkw@gcc.gnu.org; = gcc-patches@gcc.gnu.org; hubicka@ucw.cz; dje.gcc@gmail.com Subject: Re: [PATCH] Fix loop split incorrect count and probability On Tue, 3 Aug 2021, Xionghu Luo wrote: > loop split condition is moved between loop1 and loop2, the split bb's > count and probability should also be duplicated instead of (100% vs INV), > secondly, the original loop1 and loop2 count need be propotional from the > original loop. > > Regression tested pass, OK for master? > > diff base/loop-cond-split-1.c.151t.lsplit patched/loop-cond-split-1.c.15= 1t.lsplit: > ... > int prephitmp_16; > int prephitmp_25; > > [local count: 118111600]: > if (n_7(D) > 0) > goto ; [89.00%] > else > goto ; [11.00%] > > [local count: 118111600]: > return; > > [local count: 105119324]: > pretmp_3 =3D ga; > > - [local count: 955630225]: > + [local count: 315357973]: > # i_13 =3D PHI > # prephitmp_12 =3D PHI > if (prephitmp_12 !=3D 0) > goto ; [33.00%] > else > goto ; [67.00%] > > - [local count: 315357972]: > + [local count: 104068130]: > _2 =3D do_something (); > ga =3D _2; > > - [local count: 955630225]: > + [local count: 315357973]: > # prephitmp_5 =3D PHI > i_10 =3D 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 !=3D 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 =3D PHI > # prephitmp_25 =3D PHI > > - [local count: 955630225]: > + [local count: 640272252]: > # i_15 =3D PHI > # prephitmp_16 =3D PHI > i_22 =3D 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 probability. > (do_split_loop_on_cond): Likewise. > --- > gcc/tree-ssa-loop-split.c | 16 ++++++++-------- > 1 file changed, 8 insertions(+), 8 deletions(-) > > diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c > index 3a09bbc39e5..8e5a7ded0f7 100644 > --- a/gcc/tree-ssa-loop-split.c > +++ b/gcc/tree-ssa-loop-split.c > @@ -583,10 +583,10 @@ split_loop (class loop *loop1) > basic_block cond_bb; > > class loop *loop2 =3D loop_version (loop1, cond, &cond_bb, > - profile_probability::always (), > - profile_probability::always (), > - profile_probability::always (), > - profile_probability::always (), > + true_edge->probability, > + true_edge->probability.invert ()= , > + true_edge->probability, > + true_edge->probability.invert ()= , > true); there is no 'true_edge' variable at this point. > gcc_assert (loop2); > > @@ -1486,10 +1486,10 @@ do_split_loop_on_cond (struct loop *loop1, edge i= nvar_branch) > initialize_original_copy_tables (); > > struct loop *loop2 =3D loop_version (loop1, boolean_true_node, NULL, > - profile_probability::always (), > - profile_probability::never (), > - profile_probability::always (), > - profile_probability::always (), > + invar_branch->probability.invert (), > + invar_branch->probability, > + invar_branch->probability.invert (), > + invar_branch->probability, > true); > if (!loop2) > { The patch introduction seems to talk about do_split_loop_on_cond only. Since loop versioning inserts a condition with the passed probabilities but in this case a 'boolean_true_node' condition the then and else probabilities passed look correct. It's just the scaling arguments that look wrong? This loop_version call should get a comment as to why we are passing probabilities the way we do. It does seem that scaling the loop by the invar_branch probability is correct. Since this does similar things to unswitching, I see that unswitching does prob_true =3D edge_true->probability; loop_version (loop, unshare_expr (cond), NULL, prob_true, prob_true.invert (), prob_true, prob_true.invert (), false); which maybe suggests that your invar_branch based passing should depend on 'true_invar'? Also compared to unswitching the first loop is always entered, so I wonder if the scaling is correct with respect to that given unswitching where only ever one loop is entered? Thanks, Richard.