From patchwork Fri Dec 3 02:53:43 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eugene Rozenfeld X-Patchwork-Id: 48450 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 030463857C59 for ; Fri, 3 Dec 2021 02:54:17 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 030463857C59 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638500057; bh=IsxBN21LvWK4Lv8dl4h7vAr9isllulr3Jiu4fydv1g0=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=kzqHqAt00+xzOycCaMSY+we6usULa7WSy3ET/M59yTQdUxoOiRCSw/QIp62VlKuh7 AW58LKMjDhX4OCJiH4gS5YQjYlOcc17ueaaDmDpn/fh0d1Asf1LTDzYcLybCY5AeBt nix0ql4VauQyk9KEaUQ8+FjPFLKtoudracCD1Dps= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from na01-obe.outbound.protection.outlook.com (mail-eus2azlp17011010.outbound.protection.outlook.com [40.93.12.10]) by sourceware.org (Postfix) with ESMTPS id 3892E3858010 for ; Fri, 3 Dec 2021 02:53:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3892E3858010 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=EYLrmIHyj4j4ypbNL8Um5pqrxEhAKEuhAW1o/hkvgNaDlWirtEGesmjm8Do/OiFdVRFYt/Jd54ToxpbqY81PxVJT/7zwhgdgj01Zz1EdHdajq/4/57E5mSGO5WT5VZV2EESfqqgWVOVGFwJJskpcV5NUuufSjljaBa6Z17r9FVqleQfiES40xDOq6LObmZt214yOJqJ0LiNpsaKep7KbsnsFZPOy0ZH9UEHtkUJnw4W/FKA7SsZc4g2FnjJf0wZQwuc0ZkcTv9JcxJmN/cFlEO74AHA/swt1K6dRdYDiNMPGqvWMNoeadV1cYGQtYnGEOowRZI5dAmvMkEgSBVJX1Q== 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-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=IsxBN21LvWK4Lv8dl4h7vAr9isllulr3Jiu4fydv1g0=; b=TO2Rib5HqpsVXCsxnxjaJJZbiJJi+mc1Uihxa0rXeH/mz49075CYbin8qx/QZa+MHMGPqujDAXfXi3XXRoC+uPI7pjNsTr0AneC3rJnjJleYxSZZPfcIZjp1H0PD3ZgoPC81eePjLKM3MdnARbzThokq+08W6GcEGml2De5Dr14KXLFsN9SNyRinZz1asgsP4tNQ+qZW4N8CB0Hw25lQfsiP7PZBE31CtGo8u9/GC6OPvAdopq6VaLTeorOwN7GEKromvOwqHJi0svyiOmApYBgFYjtYvz4ucI65RPfCSaTx7K8Tx5m7kYKcRC16HypMxPng8B/m7/OKWrnDajumqg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=microsoft.com; dmarc=pass action=none header.from=microsoft.com; dkim=pass header.d=microsoft.com; arc=none Received: from MW2PR2101MB1100.namprd21.prod.outlook.com (2603:10b6:302:a::29) by MW2PR2101MB1019.namprd21.prod.outlook.com (2603:10b6:302:5::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4755.4; Fri, 3 Dec 2021 02:53:44 +0000 Received: from MW2PR2101MB1100.namprd21.prod.outlook.com ([fe80::c8fc:3947:18f1:49f]) by MW2PR2101MB1100.namprd21.prod.outlook.com ([fe80::c8fc:3947:18f1:49f%4]) with mapi id 15.20.4734.013; Fri, 3 Dec 2021 02:53:44 +0000 To: "gcc-patches@gcc.gnu.org" Subject: [PATCH] Improve AutoFDO count propagation algorithm Thread-Topic: [PATCH] Improve AutoFDO count propagation algorithm Thread-Index: Adfn8KSCTfsjrTuWTeiJclaopmkREw== Date: Fri, 3 Dec 2021 02:53:43 +0000 Message-ID: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: msip_labels: MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_ActionId=ef444da5-dfa9-4ce3-85c8-8912fd2a8e9e; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_ContentBits=0; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Enabled=true; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Method=Standard; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Name=Internal; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_SetDate=2021-12-03T02:50:56Z; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_SiteId=72f988bf-86f1-41af-91ab-2d7cd011db47; x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: a6fb7ea8-60d2-408f-f616-08d9b6081eb5 x-ms-traffictypediagnostic: MW2PR2101MB1019:EE_ x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:2958; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: aUEk0g0srAaEJh3BCcTv71YIKUQDWRZ6r02JwangOgkdVAEwZ3ufupdWIKnDcqt9YvCgOHMRKLqEkrV/SWOF6Fh5yYcuATH8aXHDl4PoeDYRsR57wgZ2HjiLAhUxyXyFrZy6Hhq2YeSJHYPbNB1lNnaHjOuUB6EGknR6ckpj/ycWUyPuSGOQx6pyikCYav8gEj80aIBmmgejvTDYty5S44Q962FoLIEzSUat0mzl8MRiJnGSoDVTmGOUvsFZ4ptQG/AkfKKxbXolAw7iKqb68mcfglljsvh65j/XAD2nSbt8sgzMyRcSXPIEhjwS7pD+S0HDAIstg9QS0cE12LovTvSw2a9pdZWA2Wu6mR8wtmwisgpHGPjgox+7roHvAz2VMHeJWkAkiSqY9S1Aleiz6nGTxURZ5InSSfkOrR2Zj1uXDA0ifD+cRjpXniOV/USRRJBBd23YHpwC5XyzWflrwf2rkU4igfE/Q7ZUpn0ke4NTIWBX3D1+cpRENrkZBpkBSFpyOItqtS372GBmt6ez6sI79MDWDEIKzc2DD6hiq+SNTqHpZZ6llyyzOR7/gYh+MRCCDMATkX2+EIho7e1c8qpdhxvAxw1hrvpr3zr8b0QQX4s9UPlsZjUBJQy7Ev6YUDE//KllYJh31u/7dUw+w26aPthpiEM/mGrYEeuIDKy8NhJXIdlxbR83hr9WXDHhrDH5uXwwpzgT6Hy8GUh5LzeIgKHBSge1Anwb18Zgy0NmD3f3SBt3b1rJ68fsOGZ16dG6MeqESsI6i5KyrjV62qsvbf9DQbyeZ/+Ucz1qyGPdnLt4sGkhHHPe44MC6fbG0S/ME4nIOcK0Cqa4m4YL/A== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:MW2PR2101MB1100.namprd21.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(8676002)(38070700005)(33656002)(122000001)(316002)(38100700002)(76116006)(8990500004)(6916009)(66476007)(66556008)(186003)(8936002)(66946007)(26005)(82950400001)(82960400001)(86362001)(83380400001)(7696005)(55016003)(84970400001)(2906002)(52536014)(9686003)(508600001)(71200400001)(6506007)(66446008)(64756008)(5660300002)(10290500003)(20210929001); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: pIOsjD1mrR1aBXhl2eE6Bl0ze7jDll89NlhIWoPTGjQAIp+hHKLhbPFfFSWQh5GHxSoAJRsPceWAAZe27eEPIoGhOAzbpUQ6nt/nPbDXh2/ZHYavp5ue4OWiz5wblFMk5zdO2qR+xYSRjABiiv8zrLwx2w8RvG629C7BxDtrwGBJCb4ejx7VQ01nOaMKdhmnfPu1IntAJiO7SdcWzZbid6EDpV/t6ULaiDPlVQSwjPvtxD21TQkkV4mS5vfJ8D/sbO62/ei6OpcrFpTtntybQStBgsKgjQCUtIm1tGIEEmoaNUbChG/45Bm9/iXRi763IGvWjtduRQAE8mIDRoekNvLcA8bA31E4fNTwVc94c1oA/mmTFFigp9n3UL9PcG6gGLGXro1ASBBrBHBBjTjbusA8H/SS3aXMtj3Pe1TNoHMC5ZMvOG9TIio5krgrdeCxESM/KhiAKju9qI8AcMByWeAmleOYObv1eVqJSwTHJ6unPZuf1vXb6JYBYCZK2fCZZh9Sy7ZXsr9WhO89APcgH/aKpv7CDPlyi2Bh53m7YAbMp7CBJwbYkFypXKR41yMvKjtGlbHEp4DAlgscj0RS8FaP0jVnE+wL2dlvnaF0DWlb/eVejaxaWQTnqZ8cvnq6J4ieuhmM7kUMH261/uAUsLAjzeU3oOW/GeNQ4s6eQJTVAUHWTsbhe8l7xLk8tu6LzKsgrLUg9Z62CFmGois3jQg4ln94l4S2aCrlmapzSA+LcM7hPh+Wvt2X8hlLtYYg6PcLD+jeoaGK5oT8LTVnm6VX4PRTcFL3tkJXty13Y2NXPb59OpDX6FtK37MQNpAW2M8aJ7b/9wSWcJIjpxwr8Jpn0wTm9fwM1fi0DPqTiYl+bjHqXmDp3NRScNlGYCRjLSKtA4jJMyHwLAgoV2stWTxuVG0CqyN+J+LVsadp8YKycz2Yk1kgvzQc6uVK37v9YXoIXmAUkDxzWg+ZNr6aczv98P6gJ/wJqQiprrQ23ko7mLHUxSbTkcws1csPgJZkbgV/lhAE+M6PmSidDvkBBq8KH3LnVu0QxuS1AWbWQS3DLU2NEopBHc6XpE6EetltLGIHuDzKOFxXXLiIECOeYQnzu9LGo+JEUMZ9Wj8UM22NQuaqES7sDwCHBRvcZAAPb/KefSv2NRsctHjZPY4U/hc2z4D6u+ubJMd7h2IbjbZ268PKGKWTalMJrKjp2XX4POBg/iGw2TVYjtmHi3xYAVZapIZZZSre+dFusW4eGKI4tMwaG/m5FVlwubhxRHJAo+wNzf2iXZp5fTA/qWmdki5tkj2XPbRZWrO1pBLcXZZT6U1Mgm3f3krFesGhojrhAespHiU0fvazk2vE035dDdewYMi7CiXXRv6iju6ua3IUWmabhrnq5V1lHJeXs7pYNvywIFm4D9GD6WLtVCjZ+dTPFMYfbWHAm7C1Hz3ANLyOd/IRci1gUOsqakBnq3+zsAKJThCdvwKUVEQShxr2LGUIDftn07qrHGx8AiD6X1GH1YUarOMlSXeMRj9nr/tiu94e6woXspnT1n90iImHo5C7UFe1zqQB0fz/MDfCQFehQz2sijcCdhvS+5/JP0OF1EUpeML4nQ4tToACuUjUSg== MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: MW2PR2101MB1100.namprd21.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: a6fb7ea8-60d2-408f-f616-08d9b6081eb5 X-MS-Exchange-CrossTenant-originalarrivaltime: 03 Dec 2021 02:53:43.8182 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: 7kGWtQEOrZwDvagPN49WcwU7TeFcj30xEP6Dp8CSNK9mcT2SSOudEgtoQ8OzcPCttkzEeWb7EhPRHWYHemoIrQ== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW2PR2101MB1019 X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FORGED_SPF_HELO, GIT_PATCH_0, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_NONE, 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: Eugene Rozenfeld via Gcc-patches From: Eugene Rozenfeld Reply-To: Eugene Rozenfeld Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" When a basic block A has been annotated with a count and it has only one successor (or predecessor) B, we can propagate the A's count to B. The algorithm without this change could leave B without an annotation if B had other unannotated predecessors (or successors). For example, in the test case I added, the loop header block was left unannotated, which prevented loop unrolling. gcc/ChangeLog: * auto-profile.c (afdo_propagate_edge): Improve count propagation algorithm. gcc/testsuite/ChangeLog: * gcc.dg/tree-prof/init-array.c: New test for unrolling inner loops. --- gcc/auto-profile.c | 20 +++++++++- gcc/testsuite/gcc.dg/tree-prof/init-array.c | 43 +++++++++++++++++++++ 2 files changed, 61 insertions(+), 2 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-prof/init-array.c -- 2.25.1 diff --git a/gcc/auto-profile.c b/gcc/auto-profile.c index 4c1fc6b536b..dfcd68113aa 100644 --- a/gcc/auto-profile.c +++ b/gcc/auto-profile.c @@ -1192,7 +1192,8 @@ afdo_find_equiv_class (bb_set *annotated_bb) /* If a basic block's count is known, and only one of its in/out edges' count is unknown, its count can be calculated. Meanwhile, if all of the in/out edges' counts are known, then the basic block's unknown count can also be - calculated. + calculated. Also, if a block has a single predecessor or successor, the block's + count can be propagated to that predecessor or successor. IS_SUCC is true if out edges of a basic blocks are examined. Update ANNOTATED_BB accordingly. Return TRUE if any basic block/edge count is changed. */ @@ -1208,6 +1209,7 @@ afdo_propagate_edge (bool is_succ, bb_set *annotated_bb) edge e, unknown_edge = NULL; edge_iterator ei; int num_unknown_edge = 0; + int num_edge = 0; profile_count total_known_count = profile_count::zero ().afdo (); FOR_EACH_EDGE (e, ei, is_succ ? bb->succs : bb->preds) @@ -1217,6 +1219,7 @@ afdo_propagate_edge (bool is_succ, bb_set *annotated_bb) num_unknown_edge++, unknown_edge = e; else total_known_count += AFDO_EINFO (e)->get_count (); + num_edge++; } /* Be careful not to annotate block with no successor in special cases. */ @@ -1230,7 +1233,20 @@ afdo_propagate_edge (bool is_succ, bb_set *annotated_bb) else if (num_unknown_edge == 1 && is_bb_annotated (bb, *annotated_bb)) { if (bb->count > total_known_count) - AFDO_EINFO (unknown_edge)->set_count (bb->count - total_known_count); + { + profile_count new_count = bb->count - total_known_count; + AFDO_EINFO(unknown_edge)->set_count(new_count); + if (num_edge == 1) + { + basic_block succ_or_pred_bb = is_succ ? unknown_edge->dest : unknown_edge->src; + if (new_count > succ_or_pred_bb->count) + { + succ_or_pred_bb->count = new_count; + if (!is_bb_annotated (succ_or_pred_bb, *annotated_bb)) + set_bb_annotated (succ_or_pred_bb, annotated_bb); + } + } + } else AFDO_EINFO (unknown_edge)->set_count (profile_count::zero().afdo ()); AFDO_EINFO (unknown_edge)->set_annotated (); diff --git a/gcc/testsuite/gcc.dg/tree-prof/init-array.c b/gcc/testsuite/gcc.dg/tree-prof/init-array.c new file mode 100644 index 00000000000..0f7a5c84481 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-prof/init-array.c @@ -0,0 +1,43 @@ +/* { dg-options "-O3 -fdump-tree-cunrolli-details" } */ + +static int s[10][10][10]; +static int d[10][10][10]; + +__attribute__((noipa)) +int array() +{ + int i; + register int j, k; + for (i = 0; i < 10; i++) + for (j = 0; j < 10; j++) + for (k = 0; k < 10; k++) + d[i][j][k] = s[i][j][k]; + + return(0); +} + +__attribute__((noipa)) +void TestBench() +{ + for (int i = 0; i < 150000; ++i) + { + array(); + } +} + +int main(int argc, char *argv[]) +{ + + TestBench(); + + if (d[9][9][9] == 0 && s[9][9][9] == 0) + { + return 0; + } + else + { + return -1; + } +} + +/* { dg-final-use { scan-tree-dump-times "loop with 10 iterations completely unrolled" 2 "cunrolli"} } */