From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 127370 invoked by alias); 30 Sep 2015 20:28:35 -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 127355 invoked by uid 89); 30 Sep 2015 20:28:35 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.7 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 30 Sep 2015 20:28:33 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (Postfix) with ESMTPS id 6DBE9AC1BD for ; Wed, 30 Sep 2015 20:28:32 +0000 (UTC) Received: from localhost.localdomain (ovpn-113-59.phx2.redhat.com [10.3.113.59]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t8UKSV6g031254 for ; Wed, 30 Sep 2015 16:28:31 -0400 To: gcc-patches@gcc.gnu.org From: Jeff Law Subject: [PATCH] Improve DOM's optimization of control statements Message-ID: <560C45EE.10202@redhat.com> Date: Wed, 30 Sep 2015 22:11:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------060509070200060402090102" X-IsSubscribed: yes X-SW-Source: 2015-09/txt/msg02395.txt.bz2 This is a multi-part message in MIME format. --------------060509070200060402090102 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Content-length: 1676 Until now DOM has had to be very conservative with handling control statements with known conditions. This as been an unfortunate side effect of the interaction between removing edges and recycling names via the SSA_NAME manager. Essentially DOM would have to leave control statements alone. So you'd see stuff like if (0 == 0) left around by DOM. The jump threader would thankfully come along and optimize that as a jump thread. But that's terribly inefficient, not to mention it creates unnecessary churn in the CFG and SSA_NAMEs. By optimizing that directly in DOM, including removing whatever edges are not executable, we no longer have to rely on jump threading to handle that case. Less churn in the CFG & SSA_NAMEs. There's also some chance for secondary optimizations with fewer edges left in the CFG for DOM to consider. Unfortunately, the churn caused by jump threading made it excessively difficult to analyze before/after dumps. Sadly, you can have the same code, but if the SSA_NAMEs have changed, that impacts coalescing as we leave SSA. Churn in the CFG changes labels/jumps, often without changing the actual structure, etc. I did some tests with valgrind to evaluate branching behaviour before/after effects on the resulting code and those effects were tiny, in the I doubt you could measure them range. That was expected since what we're really doing here is just capturing the optimization earlier. I had a couple more tests, but they were lost in a bit of idiocy. The test included is the one I had a second copy of lying around. Bootstrapped and regression tested on x86_64-linux-gnu. Installed on the trunk. Jeff --------------060509070200060402090102 Content-Type: text/plain; charset=UTF-8; name="P" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="P" Content-length: 8471 CSogdHJlZS1zc2EtZG9tLmMgKG9wdGltaXplX3N0bXQpOiBDb2xsYXBzZSBj b250cm9sIGZsb3cgc3RhdGVtZW50cwoJd2l0aCBjb25zdGFudCBjb25kaXRp b25zLgoJKiB0cmVlLXNzYS10aHJlYWR1cGRhdGUuYyAocmVtb3ZlX2p1bXBf dGhyZWFkc19zdGFydGluZ19hdCk6IE5ldy4KCShyZW1vdmVfY3RybF9zdG10 X2FuZF91c2VsZXNzX2VkZ2VzKTogTm8gbG9uZ2VyIHN0YXRpYy4KCSogdHJl ZS1zc2EtdGhyZWFkdXBkYXRlLmggKHJlbW92ZV9qdW1wX3RocmVhZHNfc3Rh cnRpbmdfYXQpOiBQcm90b3R5cGUuCgkocmVtb3ZlX2N0cmxfc3RtdF9hbmRf dXNlbGVzc19lZGdlcyk6IExpa2V3aXNlLgoKCSogZ2NjLmRnL3RyZWUtc3Nh L3NzYS1kb20tYnJhbmNoLTEuYzogTmV3IHRlc3QuCgpkaWZmIC0tZ2l0IGEv Z2NjL3RyZWUtc3NhLWRvbS5jIGIvZ2NjL3RyZWUtc3NhLWRvbS5jCmluZGV4 IDJjNTFlMzYuLmE4YjcwMzggMTAwNjQ0Ci0tLSBhL2djYy90cmVlLXNzYS1k b20uYworKysgYi9nY2MvdHJlZS1zc2EtZG9tLmMKQEAgLTE4MjAsMzEgKzE4 MjAsOCBAQCBvcHRpbWl6ZV9zdG10IChiYXNpY19ibG9jayBiYiwgZ2ltcGxl X3N0bXRfaXRlcmF0b3Igc2ksCiAgIGlmIChpc19naW1wbGVfYXNzaWduIChz dG10KSkKICAgICByZWNvcmRfZXF1aXZhbGVuY2VzX2Zyb21fc3RtdCAoc3Rt dCwgbWF5X29wdGltaXplX3AsIGF2YWlsX2V4cHJzX3N0YWNrKTsKIAotICAv KiBJZiBTVE1UIGlzIGEgQ09ORF9FWFBSIGFuZCBpdCB3YXMgbW9kaWZpZWQs IHRoZW4gd2UgbWF5IGtub3cKLSAgICAgd2hlcmUgaXQgZ29lcy4gIElmIHRo YXQgaXMgdGhlIGNhc2UsIHRoZW4gbWFyayB0aGUgQ0ZHIGFzIGFsdGVyZWQu Ci0KLSAgICAgVGhpcyB3aWxsIGNhdXNlIHVzIHRvIGxhdGVyIGNhbGwgcmVt b3ZlX3VucmVhY2hhYmxlX2Jsb2NrcyBhbmQKLSAgICAgY2xlYW51cF90cmVl X2NmZyB3aGVuIGl0IGlzIHNhZmUgdG8gZG8gc28uICBJdCBpcyBub3Qgc2Fm ZSB0bwotICAgICBjbGVhbiB0aGluZ3MgdXAgaGVyZSBzaW5jZSByZW1vdmFs IG9mIGVkZ2VzIGFuZCBzdWNoIGNhbiB0cmlnZ2VyCi0gICAgIHRoZSByZW1v dmFsIG9mIFBISSBub2Rlcywgd2hpY2ggaW4gdHVybiBjYW4gcmVsZWFzZSBT U0FfTkFNRXMgdG8KLSAgICAgdGhlIG1hbmFnZXIuCi0KLSAgICAgVGhhdCdz IGFsbCBmaW5lIGFuZCBnb29kLCBleGNlcHQgdGhhdCBvbmNlIFNTQV9OQU1F cyBhcmUgcmVsZWFzZWQKLSAgICAgdG8gdGhlIG1hbmFnZXIsIHdlIG11c3Qg bm90IGNhbGwgY3JlYXRlX3NzYV9uYW1lIHVudGlsIGFsbCByZWZlcmVuY2Vz Ci0gICAgIHRvIHJlbGVhc2VkIFNTQV9OQU1FcyBoYXZlIGJlZW4gZWxpbWlu YXRlZC4KLQotICAgICBBbGwgcmVmZXJlbmNlcyB0byB0aGUgZGVsZXRlZCBT U0FfTkFNRXMgY2FuIG5vdCBiZSBlbGltaW5hdGVkIHVudGlsCi0gICAgIHdl IHJlbW92ZSB1bnJlYWNoYWJsZSBibG9ja3MuCi0KLSAgICAgV2UgY2FuIG5v dCByZW1vdmUgdW5yZWFjaGFibGUgYmxvY2tzIHVudGlsIGFmdGVyIHdlIGhh dmUgY29tcGxldGVkCi0gICAgIGFueSBxdWV1ZWQganVtcCB0aHJlYWRpbmcu Ci0KLSAgICAgV2UgY2FuIG5vdCBjb21wbGV0ZSBhbnkgcXVldWVkIGp1bXAg dGhyZWFkcyB1bnRpbCB3ZSBoYXZlIHRha2VuCi0gICAgIGFwcHJvcHJpYXRl IHZhcmlhYmxlcyBvdXQgb2YgU1NBIGZvcm0uICBUYWtpbmcgdmFyaWFibGVz IG91dCBvZgotICAgICBTU0EgZm9ybSBjYW4gY2FsbCBjcmVhdGVfc3NhX25h bWUgYW5kIHRodXMgd2UgbG9zZS4KLQotICAgICBVbHRpbWF0ZWx5IEkgc3Vz cGVjdCB3ZSdyZSBnb2luZyB0byBuZWVkIHRvIGNoYW5nZSB0aGUgaW50ZXJm YWNlCi0gICAgIGludG8gdGhlIFNTQV9OQU1FIG1hbmFnZXIuICAqLworICAv KiBJZiBTVE1UIGlzIGEgQ09ORF9FWFBSIG9yIFNXSVRDSF9FWFBSIGFuZCBp dCB3YXMgbW9kaWZpZWQsIHRoZW4gd2UgbWF5CisgICAgIGtub3cgd2hlcmUg aXQgZ29lcy4gICovCiAgIGlmIChnaW1wbGVfbW9kaWZpZWRfcCAoc3RtdCkg fHwgbW9kaWZpZWRfcCkKICAgICB7CiAgICAgICB0cmVlIHZhbCA9IE5VTEw7 CkBAIC0xODU4LDggKzE4MzUsMjcgQEAgb3B0aW1pemVfc3RtdCAoYmFzaWNf YmxvY2sgYmIsIGdpbXBsZV9zdG10X2l0ZXJhdG9yIHNpLAogICAgICAgZWxz ZSBpZiAoZ3N3aXRjaCAqc3d0Y2hfc3RtdCA9IGR5bl9jYXN0IDxnc3dpdGNo ICo+IChzdG10KSkKIAl2YWwgPSBnaW1wbGVfc3dpdGNoX2luZGV4IChzd3Rj aF9zdG10KTsKIAotICAgICAgaWYgKHZhbCAmJiBUUkVFX0NPREUgKHZhbCkg PT0gSU5URUdFUl9DU1QgJiYgZmluZF90YWtlbl9lZGdlIChiYiwgdmFsKSkK LQljZmdfYWx0ZXJlZCA9IHRydWU7CisgICAgICBpZiAodmFsICYmIFRSRUVf Q09ERSAodmFsKSA9PSBJTlRFR0VSX0NTVCkKKwl7CisJICBlZGdlIHRha2Vu X2VkZ2UgPSBmaW5kX3Rha2VuX2VkZ2UgKGJiLCB2YWwpOworCSAgaWYgKHRh a2VuX2VkZ2UpCisJICAgIHsKKwkgICAgICAvKiBEZWxldGUgdGhyZWFkcyB0 aGF0IHN0YXJ0IGF0IEJCLiAgKi8KKwkgICAgICByZW1vdmVfanVtcF90aHJl YWRzX3N0YXJ0aW5nX2F0IChiYik7CisKKwkgICAgICAvKiBOb3cgY2xlYW4g dXAgdGhlIGNvbnRyb2wgc3RhdGVtZW50IGF0IHRoZSBlbmQgb2YKKwkJIEJC IGFuZCByZW1vdmUgdW5leGVjdXRhYmxlIGVkZ2VzLiAgKi8KKwkgICAgICBy ZW1vdmVfY3RybF9zdG10X2FuZF91c2VsZXNzX2VkZ2VzIChiYiwgdGFrZW5f ZWRnZS0+ZGVzdCk7CisKKwkgICAgICAvKiBGaXh1cCB0aGUgZmxhZ3Mgb24g dGhlIHNpbmdsZSByZW1haW5pbmcgZWRnZS4gICovCisJICAgICAgdGFrZW5f ZWRnZS0+ZmxhZ3MKKwkJJj0gfihFREdFX1RSVUVfVkFMVUUgfCBFREdFX0ZB TFNFX1ZBTFVFIHwgRURHRV9BQk5PUk1BTCk7CisJICAgICAgdGFrZW5fZWRn ZS0+ZmxhZ3MgfD0gRURHRV9GQUxMVEhSVTsKKworCSAgICAgIC8qIEZ1cnRo ZXIgc2ltcGxpZmljYXRpb25zIG1heSBiZSBwb3NzaWJsZS4gICovCisJICAg ICAgY2ZnX2FsdGVyZWQgPSB0cnVlOworCSAgICB9CisJfQogCiAgICAgICAv KiBJZiB3ZSBzaW1wbGlmaWVkIGEgc3RhdGVtZW50IGluIHN1Y2ggYSB3YXkg YXMgdG8gYmUgc2hvd24gdGhhdCBpdAogCSBjYW5ub3QgdHJhcCwgdXBkYXRl IHRoZSBlaCBpbmZvcm1hdGlvbiBhbmQgdGhlIGNmZyB0byBtYXRjaC4gICov CmRpZmYgLS1naXQgYS9nY2MvdHJlZS1zc2EtdGhyZWFkdXBkYXRlLmMgYi9n Y2MvdHJlZS1zc2EtdGhyZWFkdXBkYXRlLmMKaW5kZXggNmYyMTUyOS4uNGEx NDdiYiAxMDA2NDQKLS0tIGEvZ2NjL3RyZWUtc3NhLXRocmVhZHVwZGF0ZS5j CisrKyBiL2djYy90cmVlLXNzYS10aHJlYWR1cGRhdGUuYwpAQCAtMjYwLDcg KzI2MCw3IEBAIHN0cnVjdCB0aHJlYWRfc3RhdHNfZCB0aHJlYWRfc3RhdHM7 CiAgICBBbHNvIHJlbW92ZSBhbGwgb3V0Z29pbmcgZWRnZXMgZXhjZXB0IHRo ZSBlZGdlIHdoaWNoIHJlYWNoZXMgREVTVF9CQi4KICAgIElmIERFU1RfQkIg aXMgTlVMTCwgdGhlbiByZW1vdmUgYWxsIG91dGdvaW5nIGVkZ2VzLiAgKi8K IAotc3RhdGljIHZvaWQKK3ZvaWQKIHJlbW92ZV9jdHJsX3N0bXRfYW5kX3Vz ZWxlc3NfZWRnZXMgKGJhc2ljX2Jsb2NrIGJiLCBiYXNpY19ibG9jayBkZXN0 X2JiKQogewogICBnaW1wbGVfc3RtdF9pdGVyYXRvciBnc2k7CkBAIC0yNTM5 LDYgKzI1MzksMzcgQEAgdmFsaWRfanVtcF90aHJlYWRfcGF0aCAodmVjPGp1 bXBfdGhyZWFkX2VkZ2UgKj4gKnBhdGgpCiAgIHJldHVybiB0cnVlOwogfQog CisvKiBSZW1vdmUgYW55IHF1ZXVlZCBqdW1wIHRocmVhZHMgdGhhdCBzdGFy dCBhdCBCQi4gICovCisKK3ZvaWQKK3JlbW92ZV9qdW1wX3RocmVhZHNfc3Rh cnRpbmdfYXQgKGJhc2ljX2Jsb2NrIGJiKQoreworICBpZiAoIXBhdGhzLmV4 aXN0cyAoKSkKKyAgICByZXR1cm47CisKKyAgZm9yICh1bnNpZ25lZCBpID0g MDsgaSA8IHBhdGhzLmxlbmd0aCAoKTspCisgICAgeworICAgICAgdmVjPGp1 bXBfdGhyZWFkX2VkZ2UgKj4gKnBhdGggPSBwYXRoc1tpXTsKKworICAgICAg LyogU2FkbHksIEZTTSBqdW1wIHRocmVhZHMgaGF2ZSBhIHNsaWdodGx5IGRp ZmZlcmVudAorCSByZXByZXNlbnRhdGlvbiB0aGFuIHRoZSByZXN0IG9mIHRo ZSBqdW1wIHRocmVhZHMuICAqLworICAgICAgaWYgKCgqcGF0aClbMF0tPnR5 cGUgPT0gRURHRV9GU01fVEhSRUFECisJICAmJiAoKnBhdGgpWzBdLT5lLT5z cmMgPT0gYmIpCisJeworCSAgZGVsZXRlX2p1bXBfdGhyZWFkX3BhdGggKHBh dGgpOworCSAgcGF0aHMudW5vcmRlcmVkX3JlbW92ZSAoaSk7CisJfQorICAg ICAgZWxzZSBpZiAoKCpwYXRoKVswXS0+dHlwZSAhPSBFREdFX0ZTTV9USFJF QUQKKwkgICAgICAgJiYgKCpwYXRoKVswXS0+ZS0+ZGVzdCA9PSBiYikKKwl7 CisJICBkZWxldGVfanVtcF90aHJlYWRfcGF0aCAocGF0aCk7CisJICBwYXRo cy51bm9yZGVyZWRfcmVtb3ZlIChpKTsKKwl9CisgICAgICBlbHNlCisJaSsr OworICAgIH0KK30KKwogLyogV2FsayB0aHJvdWdoIGFsbCBibG9ja3MgYW5k IHRocmVhZCBpbmNvbWluZyBlZGdlcyB0byB0aGUgYXBwcm9wcmlhdGUKICAg IG91dGdvaW5nIGVkZ2UgZm9yIGVhY2ggZWRnZSBwYWlyIHJlY29yZGVkIGlu IFRIUkVBREVEX0VER0VTLgogCmRpZmYgLS1naXQgYS9nY2MvdHJlZS1zc2Et dGhyZWFkdXBkYXRlLmggYi9nY2MvdHJlZS1zc2EtdGhyZWFkdXBkYXRlLmgK aW5kZXggMjFhOWVlMy4uMzA0MjhlOCAxMDA2NDQKLS0tIGEvZ2NjL3RyZWUt c3NhLXRocmVhZHVwZGF0ZS5oCisrKyBiL2djYy90cmVlLXNzYS10aHJlYWR1 cGRhdGUuaApAQCAtNDMsNSArNDMsNyBAQCBwdWJsaWM6CiB9OwogCiBleHRl cm4gdm9pZCByZWdpc3Rlcl9qdW1wX3RocmVhZCAodmVjIDxjbGFzcyBqdW1w X3RocmVhZF9lZGdlICo+ICopOworZXh0ZXJuIHZvaWQgcmVtb3ZlX2p1bXBf dGhyZWFkc19zdGFydGluZ19hdCAoYmFzaWNfYmxvY2spOwogZXh0ZXJuIHZv aWQgZGVsZXRlX2p1bXBfdGhyZWFkX3BhdGggKHZlYyA8Y2xhc3MganVtcF90 aHJlYWRfZWRnZSAqPiAqKTsKK2V4dGVybiB2b2lkIHJlbW92ZV9jdHJsX3N0 bXRfYW5kX3VzZWxlc3NfZWRnZXMgKGJhc2ljX2Jsb2NrLCBiYXNpY19ibG9j ayk7CiAjZW5kaWYKZGlmZiAtLWdpdCBhL2djYy90ZXN0c3VpdGUvZ2NjLmRn L3RyZWUtc3NhL3NzYS1kb20tYnJhbmNoLTEuYyBiL2djYy90ZXN0c3VpdGUv Z2NjLmRnL3RyZWUtc3NhL3NzYS1kb20tYnJhbmNoLTEuYwpuZXcgZmlsZSBt b2RlIDEwMDY0NAppbmRleCAwMDAwMDAwLi40Yzc2MzFjCi0tLSAvZGV2L251 bGwKKysrIGIvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvdHJlZS1zc2Evc3NhLWRv bS1icmFuY2gtMS5jCkBAIC0wLDAgKzEsMzEgQEAKKy8qIHsgZGctZG8gY29t cGlsZSB9ICovIAorLyogeyBkZy1vcHRpb25zICItTzIgLXcgLWZkdW1wLXRy ZWUtZG9tMS1kZXRhaWxzIiB9ICovCisKK3R5cGVkZWYgc3RydWN0IHJ0eF9k ZWYgKnJ0eDsKK3N0cnVjdCBydHhfZGVmCit7CisgIGludCBjb2RlOworICBy dHggcnRfcnR4OworfTsKK3J0eAordHJ5X2NvbWJpbmUgKHJ0eCBpMSwgcnR4 IG5ld3BhdCkKK3sKKyAgcnR4IHRlbXA7CisgIGlmIChpMSAmJiAodGVtcCA9 ICgoKCgoKG5ld3BhdC0+cnRfcnR4LCAoKCgodGVtcCktPmNvZGUpID09IDQy KSkpKSkpKSkpCisgICAgICAmJiAoKHRlbXAgPQorCSgoKCgoKCgoKCgobmV3 cGF0KS0+cnRfcnR4KSwKKwkJICgoKCh0ZW1wKS0+Y29kZSkgPT0gNDIpICYm IGFyZiAoKSkpKSkpKSkpKSkpKSkKKyAgICA7CisgIGVsc2UgaWYgKGkxICYm IGZvbyAoKSk7Cit9CisKKy8qIFRoZXJlIHNob3VsZCBiZSB0aHJlZSB0ZXN0 cyBhZ2FpbnN0IGkxLiAgVHdvIGZyb20gdGhlIGhhc2ggdGFibGUKKyAgIGR1 bXBzLCBvbmUgaW4gdGhlIGNvZGUgaXRzZWxmLiAgKi8KKy8qIHsgZGctZmlu YWwgeyBzY2FuLXRyZWUtZHVtcC10aW1lcyAiaWYgLmkxXyIgMyAiZG9tMSJ9 IH0gKi8KKworLyogVGhlcmUgc2hvdWxkIGJlIG5vIGFjdHVhbCBqdW1wIHRo cmVhZHMgcmVhbGl6ZWQgYnkgRE9NLiAgVGhlCisgICBsZWdpdGltaXplIGp1 bXAgdGhyZWFkcyBhcmUgaGFuZGxlZCBpbiBWUlAgYW5kIHRob3NlIGRpc2Nv dmVyZWQKKyAgIGJ5IERPTSBhcmUgc3Vic3VtZWQgYnkgY29sbGFwc2luZyBh IGNvbmRpdGlvbmFsLiAgKi8KKy8qIHsgZGctZmluYWwgeyBzY2FuLXRyZWUt ZHVtcC1ub3QgIlRocmVhZGVkIiAiZG9tMSJ9IH0gKi8KKworCg== --------------060509070200060402090102--