From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 39243 invoked by alias); 12 Jun 2017 17:02:47 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 39142 invoked by uid 89); 12 Jun 2017 17:02:46 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: EUR03-AM5-obe.outbound.protection.outlook.com Received: from mail-eopbgr30042.outbound.protection.outlook.com (HELO EUR03-AM5-obe.outbound.protection.outlook.com) (40.107.3.42) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 12 Jun 2017 17:02:44 +0000 Received: from VI1PR0802MB2176.eurprd08.prod.outlook.com (10.172.12.21) by VI1PR0802MB2175.eurprd08.prod.outlook.com (10.172.12.20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1157.12; Mon, 12 Jun 2017 17:02:46 +0000 Received: from VI1PR0802MB2176.eurprd08.prod.outlook.com ([fe80::2dae:8af1:7884:bb6d]) by VI1PR0802MB2176.eurprd08.prod.outlook.com ([fe80::2dae:8af1:7884:bb6d%18]) with mapi id 15.01.1157.017; Mon, 12 Jun 2017 17:02:46 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH GCC][04/13]Sort statements in topological order for loop distribution Date: Mon, 12 Jun 2017 17:03:00 -0000 Message-ID: authentication-results: arm.com; dkim=none (message not signed) header.d=none;arm.com; dmarc=none action=none header.from=arm.com; x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;VI1PR0802MB2175;7:Wj+6nRLunv9XEUfZY9DfUeB0vkucgK+Xs5gIgK+t8pZN6AC1e5Ht4ItlYw5iwLgVer/7SJTPwdocwl4eorYBwwJXVfikkvmwfwv32AhTKOkHYvrszb/ZQFbbXO/3AD4ImGSGqydvybhgWk0JcJqDWV5xGHeySz1ShKwR7FABI6BTtk7NFXk7FRbydwe4z1xV/KlRdnpTDNw29P8VsJKjSdFc6mApiPzmfNDGUHNBuSglzB5JDL4SI/O2A/2kMA0g2ZJtboILmWu/wA7gm62rNBOSCCzV/oINeQzqE1YhH8+cs0zkJLH67a3g3TeKx8bbmxjW8+H0mkhDUpRnL5XLPA== x-ms-traffictypediagnostic: VI1PR0802MB2175: x-ms-office365-filtering-correlation-id: acc95107-1367-4a41-227b-08d4b1b4d91d x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:(22001)(2017030254075)(48565401081)(201703131423075)(201703031133081);SRVR:VI1PR0802MB2175; nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917); x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(102415395)(6040450)(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001)(100000703101)(100105400095)(93006095)(93001095)(6055026)(6041248)(20161123560025)(20161123564025)(20161123562025)(20161123555025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123558100)(6072148)(100000704101)(100105200095)(100000705101)(100105500095);SRVR:VI1PR0802MB2175;BCL:0;PCL:0;RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095);SRVR:VI1PR0802MB2175; x-forefront-prvs: 03361FCC43 x-forefront-antispam-report: SFV:NSPM;SFS:(10009020)(6009001)(39450400003)(39400400002)(39410400002)(39860400002)(39850400002)(39840400002)(377424004)(38730400002)(55016002)(50986999)(110136004)(99286003)(72206003)(14454004)(33656002)(53936002)(8936002)(478600001)(9686003)(5660300001)(86362001)(8676002)(3280700002)(2906002)(6506006)(99936001)(2351001)(189998001)(2501003)(7696004)(6436002)(25786009)(2900100001)(54356999)(74316002)(81166006)(3660700001)(4326008)(7736002)(5640700003)(5250100002)(305945005)(6916009)(66066001)(102836003)(3846002);DIR:OUT;SFP:1101;SCL:1;SRVR:VI1PR0802MB2175;H:VI1PR0802MB2176.eurprd08.prod.outlook.com;FPR:;SPF:None;MLV:sfv;LANG:en; spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: multipart/mixed; boundary="_002_VI1PR0802MB217674C5C7E97D5D96EE982AE7CD0VI1PR0802MB2176_" MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Jun 2017 17:02:45.9636 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0802MB2175 X-IsSubscribed: yes X-SW-Source: 2017-06/txt/msg00827.txt.bz2 --_002_VI1PR0802MB217674C5C7E97D5D96EE982AE7CD0VI1PR0802MB2176_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-length: 676 Hi, During the work I ran into a latent bug for distributing. For the moment w= e sort statements in dominance order, but that's not enough because basic blocks may be sorte= d in reverse order of execution flow. This results in wrong data dependence direction later. = This patch fixes the issue by sorting in topological order. Bootstrap and test on x86_64 and AArch64. Is it OK? Thanks, bin 2017-06-07 Bin Cheng * tree-loop-distribution.c (bb_top_order_index): New. (bb_top_order_index_size, bb_top_order_cmp): New. (stmts_from_loop): Use topological order. (pass_loop_distribution::execute): Compute topological order for. basic blocks.= --_002_VI1PR0802MB217674C5C7E97D5D96EE982AE7CD0VI1PR0802MB2176_ Content-Type: text/plain; name="0004-sort-stmts-in-top-order-20170607.txt" Content-Description: 0004-sort-stmts-in-top-order-20170607.txt Content-Disposition: attachment; filename="0004-sort-stmts-in-top-order-20170607.txt"; size=3520; creation-date="Mon, 12 Jun 2017 16:45:50 GMT"; modification-date="Mon, 12 Jun 2017 16:45:50 GMT" Content-Transfer-Encoding: base64 Content-length: 4775 RnJvbSA0YmIyMzMyMzllMDgwZWNhOTU2YjNkYjc4MzZjZGY2NGRhNDg2ZGJm IE1vbiBTZXAgMTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBCaW4gQ2hlbmcgPGJp bmNoZTAxQGUxMDg0NTEtbGluLmNhbWJyaWRnZS5hcm0uY29tPgpEYXRlOiBX ZWQsIDcgSnVuIDIwMTcgMTM6NDc6NTIgKzAxMDAKU3ViamVjdDogW1BBVENI IDA0LzE0XSBzb3J0LXN0bXRzLWluLXRvcC1vcmRlci0yMDE3MDYwNy50eHQK Ci0tLQogZ2NjL3RyZWUtbG9vcC1kaXN0cmlidXRpb24uYyB8IDU4ICsrKysr KysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKy0tLS0tCiAxIGZp bGUgY2hhbmdlZCwgNTIgaW5zZXJ0aW9ucygrKSwgNiBkZWxldGlvbnMoLSkK CmRpZmYgLS1naXQgYS9nY2MvdHJlZS1sb29wLWRpc3RyaWJ1dGlvbi5jIGIv Z2NjL3RyZWUtbG9vcC1kaXN0cmlidXRpb24uYwppbmRleCBiMGI5ZDY2Li5h MzIyNTNjIDEwMDY0NAotLS0gYS9nY2MvdHJlZS1sb29wLWRpc3RyaWJ1dGlv bi5jCisrKyBiL2djYy90cmVlLWxvb3AtZGlzdHJpYnV0aW9uLmMKQEAgLTM3 MywxNiArMzczLDM5IEBAIGNyZWF0ZV9yZGdfdmVydGljZXMgKHN0cnVjdCBn cmFwaCAqcmRnLCB2ZWM8Z2ltcGxlICo+IHN0bXRzLCBsb29wX3AgbG9vcCwK ICAgcmV0dXJuIHRydWU7CiB9CiAKLS8qIEluaXRpYWxpemUgU1RNVFMgd2l0 aCBhbGwgdGhlIHN0YXRlbWVudHMgb2YgTE9PUC4gIFRoZSBvcmRlciBpbgot ICAgd2hpY2ggd2UgZGlzY292ZXIgc3RhdGVtZW50cyBpcyBpbXBvcnRhbnQg YXMKLSAgIGdlbmVyYXRlX2xvb3BzX2Zvcl9wYXJ0aXRpb24gaXMgdXNpbmcg dGhlIHNhbWUgdHJhdmVyc2FsIGZvcgotICAgaWRlbnRpZnlpbmcgc3RhdGVt ZW50cyBpbiBsb29wIGNvcGllcy4gICovCisvKiBBcnJheSBtYXBwaW5nIGJh c2ljIGJsb2NrJ3MgaW5kZXggdG8gaXRzIHRvcG9sb2dpY2FsIG9yZGVyLiAg Ki8KK3N0YXRpYyBpbnQgKmJiX3RvcF9vcmRlcl9pbmRleDsKKy8qIEFuZCBz aXplIG9mIHRoZSBhcnJheS4gICovCitzdGF0aWMgaW50IGJiX3RvcF9vcmRl cl9pbmRleF9zaXplOworCisvKiBJZiBYIGhhcyBhIHNtYWxsZXIgdG9wb2xv Z2ljYWwgc29ydCBudW1iZXIgdGhhbiBZLCByZXR1cm5zIC0xOworICAgaWYg Z3JlYXRlciwgcmV0dXJucyAxLiAgKi8KKworc3RhdGljIGludAorYmJfdG9w X29yZGVyX2NtcCAoY29uc3Qgdm9pZCAqeCwgY29uc3Qgdm9pZCAqeSkKK3sK KyAgYmFzaWNfYmxvY2sgYmIxID0gKihjb25zdCBiYXNpY19ibG9jayAqKSB4 OworICBiYXNpY19ibG9jayBiYjIgPSAqKGNvbnN0IGJhc2ljX2Jsb2NrICop IHk7CisKKyAgZ2NjX2Fzc2VydCAoYmIxLT5pbmRleCA8IGJiX3RvcF9vcmRl cl9pbmRleF9zaXplCisJICAgICAgJiYgYmIyLT5pbmRleCA8IGJiX3RvcF9v cmRlcl9pbmRleF9zaXplKTsKKyAgZ2NjX2Fzc2VydCAoYmIxID09IGJiMgor CSAgICAgIHx8IGJiX3RvcF9vcmRlcl9pbmRleFtiYjEtPmluZGV4XQorCQkg IT0gYmJfdG9wX29yZGVyX2luZGV4W2JiMi0+aW5kZXhdKTsKKworICByZXR1 cm4gKGJiX3RvcF9vcmRlcl9pbmRleFtiYjEtPmluZGV4XSAtIGJiX3RvcF9v cmRlcl9pbmRleFtiYjItPmluZGV4XSk7Cit9CisKKy8qIEluaXRpYWxpemUg U1RNVFMgd2l0aCBhbGwgdGhlIHN0YXRlbWVudHMgb2YgTE9PUC4gIFdlIHVz ZSB0b3BvbG9naWNhbAorICAgb3JkZXIgdG8gZGlzY292ZXIgYWxsIHN0YXRl bWVudHMuICBUaGUgb3JkZXIgaXMgaW1wb3J0YW50IGJlY2F1c2UKKyAgIGdl bmVyYXRlX2xvb3BzX2Zvcl9wYXJ0aXRpb24gaXMgdXNpbmcgdGhlIHNhbWUg dHJhdmVyc2FsIGZvciBpZGVudGlmeWluZworICAgc3RhdGVtZW50cyBpbiBs b29wIGNvcGllcy4gICovCiAKIHN0YXRpYyB2b2lkCiBzdG10c19mcm9tX2xv b3AgKHN0cnVjdCBsb29wICpsb29wLCB2ZWM8Z2ltcGxlICo+ICpzdG10cykK IHsKICAgdW5zaWduZWQgaW50IGk7Ci0gIGJhc2ljX2Jsb2NrICpiYnMgPSBn ZXRfbG9vcF9ib2R5X2luX2RvbV9vcmRlciAobG9vcCk7CisgIGJhc2ljX2Js b2NrICpiYnMgPSBnZXRfbG9vcF9ib2R5X2luX2N1c3RvbV9vcmRlciAobG9v cCwgYmJfdG9wX29yZGVyX2NtcCk7CiAKICAgZm9yIChpID0gMDsgaSA8IGxv b3AtPm51bV9ub2RlczsgaSsrKQogICAgIHsKQEAgLTE3NjQsNiArMTc4Nywy MiBAQCBwYXNzX2xvb3BfZGlzdHJpYnV0aW9uOjpleGVjdXRlIChmdW5jdGlv biAqZnVuKQogICBpZiAobnVtYmVyX29mX2xvb3BzIChmdW4pIDw9IDEpCiAg ICAgcmV0dXJuIDA7CiAKKyAgLyogQ29tcHV0ZSB0b3BvbG9naWNhbCBvcmRl ciBmb3IgYmFzaWMgYmxvY2tzLiAgVG9wb2xvZ2ljYWwgb3JkZXIgaXMKKyAg ICAgbmVlZGVkIGJlY2F1c2UgZGF0YSBkZXBlbmRlbmNlIGlzIGNvbXB1dGVk IGZvciBkYXRhIHJlZmVyZW5jZXMgaW4KKyAgICAgbGV4aWNvZ3JhcGhpY2Fs IG9yZGVyLiAgKi8KKyAgaWYgKGJiX3RvcF9vcmRlcl9pbmRleCA9PSBOVUxM KQorICAgIHsKKyAgICAgIGludCAqcnBvID0gWE5FV1ZFQyAoaW50LCBsYXN0 X2Jhc2ljX2Jsb2NrX2Zvcl9mbiAoY2Z1bikpOworCisgICAgICBiYl90b3Bf b3JkZXJfaW5kZXggPSBYTkVXVkVDIChpbnQsIGxhc3RfYmFzaWNfYmxvY2tf Zm9yX2ZuIChjZnVuKSk7CisgICAgICBiYl90b3Bfb3JkZXJfaW5kZXhfc2l6 ZQorCT0gcHJlX2FuZF9yZXZfcG9zdF9vcmRlcl9jb21wdXRlX2ZuIChjZnVu LCBOVUxMLCBycG8sIHRydWUpOworICAgICAgZm9yIChpbnQgaSA9IDA7IGkg PCBiYl90b3Bfb3JkZXJfaW5kZXhfc2l6ZTsgaSsrKQorCWJiX3RvcF9vcmRl cl9pbmRleFtycG9baV1dID0gaTsKKworICAgICAgZnJlZSAocnBvKTsKKyAg ICB9CisKICAgRk9SX0FMTF9CQl9GTiAoYmIsIGZ1bikKICAgICB7CiAgICAg ICBnaW1wbGVfc3RtdF9pdGVyYXRvciBnc2k7CkBAIC0xODgxLDEzICsxOTIw LDIwIEBAIG91dDoKICAgaWYgKGNkKQogICAgIGRlbGV0ZSBjZDsKIAorICBp ZiAoYmJfdG9wX29yZGVyX2luZGV4ICE9IE5VTEwpCisgICAgeworICAgICAg ZnJlZSAoYmJfdG9wX29yZGVyX2luZGV4KTsKKyAgICAgIGJiX3RvcF9vcmRl cl9pbmRleCA9IE5VTEw7CisgICAgICBiYl90b3Bfb3JkZXJfaW5kZXhfc2l6 ZSA9IDA7CisgICAgfQorCiAgIGlmIChjaGFuZ2VkKQogICAgIHsKICAgICAg IC8qIERlc3Ryb3kgbG9vcCBib2RpZXMgdGhhdCBjb3VsZCBub3QgYmUgcmV1 c2VkLiAgRG8gdGhpcyBsYXRlIGFzIHdlCiAJIG90aGVyd2lzZSBjYW4gZW5k IHVwIHJlZmVyaW5nIHRvIHN0YWxlIGRhdGEgaW4gY29udHJvbCBkZXBlbmRl bmNlcy4gICovCiAgICAgICB1bnNpZ25lZCBpOwogICAgICAgRk9SX0VBQ0hf VkVDX0VMVCAobG9vcHNfdG9fYmVfZGVzdHJveWVkLCBpLCBsb29wKQotCSAg ZGVzdHJveV9sb29wIChsb29wKTsKKwlkZXN0cm95X2xvb3AgKGxvb3ApOwog CiAgICAgICAvKiBDYWNoZWQgc2NhbGFyIGV2b2x1dGlvbnMgbm93IG1heSBy ZWZlciB0byB3cm9uZyBvciBub24tZXhpc3RpbmcKIAkgbG9vcHMuICAqLwot LSAKMS45LjEKCg== --_002_VI1PR0802MB217674C5C7E97D5D96EE982AE7CD0VI1PR0802MB2176_--