From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 27932 invoked by alias); 14 Aug 2014 07:37:27 -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 27920 invoked by uid 89); 14 Aug 2014 07:37:25 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-qa0-f48.google.com Received: from mail-qa0-f48.google.com (HELO mail-qa0-f48.google.com) (209.85.216.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Thu, 14 Aug 2014 07:37:23 +0000 Received: by mail-qa0-f48.google.com with SMTP id m5so674988qaj.21 for ; Thu, 14 Aug 2014 00:37:21 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.224.5.1 with SMTP id 1mr14585254qat.30.1408001841335; Thu, 14 Aug 2014 00:37:21 -0700 (PDT) Received: by 10.140.18.173 with HTTP; Thu, 14 Aug 2014 00:37:21 -0700 (PDT) In-Reply-To: References: <002e01cfa19e$ac13fed0$043bfc70$@arm.com> Date: Thu, 14 Aug 2014 07:37:00 -0000 Message-ID: Subject: Re: [PATCH 2/3]Improve induction variable elimination From: "Bin.Cheng" To: Richard Biener Cc: Bin Cheng , GCC Patches Content-Type: multipart/mixed; boundary=001a11c2e77298c322050091f92b X-IsSubscribed: yes X-SW-Source: 2014-08/txt/msg01430.txt.bz2 --001a11c2e77298c322050091f92b Content-Type: text/plain; charset=ISO-8859-1 Content-length: 2193 On Fri, Jul 25, 2014 at 8:35 PM, Richard Biener wrote: > On Thu, Jul 17, 2014 at 11:08 AM, Bin Cheng wrote: >> Hi, >> As quoted from the function difference_cannot_overflow_p, >> >> /* TODO: deeper inspection may be necessary to prove the equality. */ >> switch (code) >> { >> case PLUS_EXPR: >> return expr_equal_p (e1, offset) || expr_equal_p (e2, offset); >> case POINTER_PLUS_EXPR: >> return expr_equal_p (e2, offset); >> >> default: >> return false; >> } >> >> The overflow check can be improved by using deeper inspection to prove the >> equality. This patch deals with that by making below two improvements: >> a) Handles constant cases. >> b) Uses affine expansion as deeper inspection to check the equality. >> >> As a result, functions strip_wrap_conserving_type_conversions and >> expr_equal_p can be removed now. A test case is also added to illustrate iv >> elimination opportunity captured by this patch. >> >> Thanks, >> bin > > You add special casing for constants but I don't see any testcases for that. > Specifically > > + /* No overflow if offset is zero. */ > + if (offset == integer_zero_node) > return true; > > is a bogus check (use integer_zerop). Apart from the special-casing of > constants the patch looks good to me. Hi, I changed/rebased the patch which passes bootstrap/test on x86_64. Since it was review/approved before, I will commit it in 24 hours if there is no objection. Thanks, bin > > >> 2014-07-17 Bin Cheng >> >> * tree-ssa-loop-ivopts.c (ivopts_data): New field name_expansion. >> (tree_ssa_iv_optimize_init): Initialize name_expansion. >> (tree_ssa_iv_optimize_finalize): Free name_expansion. >> (strip_wrap_conserving_type_conversions, expr_equal_p): Delete. >> (difference_cannot_overflow_p): New parameter. Handle constant >> cases. Use affine expansion for equality check. >> (iv_elimination_compare_lt): Pass new argument. >> >> gcc/testsuite/ChangeLog >> 2014-07-17 Bin Cheng >> >> * gcc.dg/tree-ssa/ivopts-lt-2.c: New test. --001a11c2e77298c322050091f92b Content-Type: text/plain; charset=US-ASCII; name="iv_elimination-improve-b-20140814.txt" Content-Disposition: attachment; filename="iv_elimination-improve-b-20140814.txt" Content-Transfer-Encoding: base64 X-Attachment-Id: f_hytrx8rs0 Content-length: 7756 SW5kZXg6IGdjYy90ZXN0c3VpdGUvZ2NjLmRnL3RyZWUtc3NhL2l2b3B0cy1s dC0yLmMKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gZ2NjL3Rlc3RzdWl0 ZS9nY2MuZGcvdHJlZS1zc2EvaXZvcHRzLWx0LTIuYwkocmV2aXNpb24gMCkK KysrIGdjYy90ZXN0c3VpdGUvZ2NjLmRnL3RyZWUtc3NhL2l2b3B0cy1sdC0y LmMJKHJldmlzaW9uIDApCkBAIC0wLDAgKzEsMjAgQEAKKy8qIHsgZGctZG8g Y29tcGlsZSB9ICovCisvKiB7IGRnLW9wdGlvbnMgIi1PMiAtZmR1bXAtdHJl ZS1pdm9wdHMiIH0gKi8KKwordm9pZAorZjEgKGludCAqcCwgdW5zaWduZWQg aW50IGkpCit7CisgIHAgKz0gaTsKKyAgZG8KKyAgICB7CisgICAgICAqcCA9 IDA7CisgICAgICBwICs9IDE7CisgICAgICBpKys7CisgICAgfQorICB3aGls ZSAoaSA8IDEwMCk7Cit9CisKKy8qIHsgZGctZmluYWwgeyBzY2FuLXRyZWUt ZHVtcC10aW1lcyAiUEhJIiAxICJpdm9wdHMiIH0gfSAqLworLyogeyBkZy1m aW5hbCB7IHNjYW4tdHJlZS1kdW1wLXRpbWVzICJQSEkgPHBfIiAxICJpdm9w dHMifSB9ICovCisvKiB7IGRnLWZpbmFsIHsgc2Nhbi10cmVlLWR1bXAtdGlt ZXMgInBfXFswLTlcXSogPCIgMSAiaXZvcHRzIiB9IH0gKi8KKy8qIHsgZGct ZmluYWwgeyBjbGVhbnVwLXRyZWUtZHVtcCAiaXZvcHRzIiB9IH0gKi8KSW5k ZXg6IGdjYy90cmVlLXNzYS1sb29wLWl2b3B0cy5jCj09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT0KLS0tIGdjYy90cmVlLXNzYS1sb29wLWl2b3B0cy5jCShyZXZp c2lvbiAyMTM5MzcpCisrKyBnY2MvdHJlZS1zc2EtbG9vcC1pdm9wdHMuYwko d29ya2luZyBjb3B5KQpAQCAtMzIzLDYgKzMyMyw5IEBAIHN0cnVjdCBpdm9w dHNfZGF0YQogICAvKiBBIGJpdG1hcCBvZiBpbXBvcnRhbnQgY2FuZGlkYXRl cy4gICovCiAgIGJpdG1hcCBpbXBvcnRhbnRfY2FuZGlkYXRlczsKIAorICAv KiBDYWNoZSB1c2VkIGJ5IHRyZWVfdG9fYWZmX2NvbWJpbmF0aW9uX2V4cGFu ZC4gICovCisgIGhhc2hfbWFwPHRyZWUsIG5hbWVfZXhwYW5zaW9uICo+ICpu YW1lX2V4cGFuc2lvbl9jYWNoZTsKKwogICAvKiBUaGUgbWF4aW11bSBpbnZh cmlhbnQgaWQuICAqLwogICB1bnNpZ25lZCBtYXhfaW52X2lkOwogCkBAIC04 NzYsNiArODc5LDcgQEAgdHJlZV9zc2FfaXZfb3B0aW1pemVfaW5pdCAoc3Ry dWN0IGl2b3B0c19kYXRhICpkYXQKICAgZGF0YS0+aXZfY2FuZGlkYXRlcy5j cmVhdGUgKDIwKTsKICAgZGF0YS0+aW52X2V4cHJfdGFiID0gbmV3IGhhc2hf dGFibGU8aXZfaW52X2V4cHJfaGFzaGVyPiAoMTApOwogICBkYXRhLT5pbnZf ZXhwcl9pZCA9IDA7CisgIGRhdGEtPm5hbWVfZXhwYW5zaW9uX2NhY2hlID0g TlVMTDsKICAgZGVjbF9ydGxfdG9fcmVzZXQuY3JlYXRlICgyMCk7CiB9CiAK QEAgLTQ0NjIsNzUgKzQ0NjYsMjAgQEAgaXZfZWxpbWluYXRpb25fY29tcGFy ZSAoc3RydWN0IGl2b3B0c19kYXRhICpkYXRhLAogICByZXR1cm4gKGV4aXQt PmZsYWdzICYgRURHRV9UUlVFX1ZBTFVFID8gRVFfRVhQUiA6IE5FX0VYUFIp OwogfQogCi1zdGF0aWMgdHJlZQotc3RyaXBfd3JhcF9jb25zZXJ2aW5nX3R5 cGVfY29udmVyc2lvbnMgKHRyZWUgZXhwKQotewotICB3aGlsZSAodHJlZV9z c2FfdXNlbGVzc190eXBlX2NvbnZlcnNpb24gKGV4cCkKLQkgJiYgKG5vd3Jh cF90eXBlX3AgKFRSRUVfVFlQRSAoZXhwKSkKLQkgICAgID09IG5vd3JhcF90 eXBlX3AgKFRSRUVfVFlQRSAoVFJFRV9PUEVSQU5EIChleHAsIDApKSkpKQot ICAgIGV4cCA9IFRSRUVfT1BFUkFORCAoZXhwLCAwKTsKLSAgcmV0dXJuIGV4 cDsKLX0KLQotLyogV2FsayB0aGUgU1NBIGZvcm0gYW5kIGNoZWNrIHdoZXRo ZXIgRSA9PSBXSEFULiAgRmFpcmx5IHNpbXBsaXN0aWMsIHdlCi0gICBjaGVj ayBmb3IgYW4gZXhhY3QgbWF0Y2guICAqLwotCi1zdGF0aWMgYm9vbAotZXhw cl9lcXVhbF9wICh0cmVlIGUsIHRyZWUgd2hhdCkKLXsKLSAgZ2ltcGxlIHN0 bXQ7Ci0gIGVudW0gdHJlZV9jb2RlIGNvZGU7Ci0KLSAgZSA9IHN0cmlwX3dy YXBfY29uc2VydmluZ190eXBlX2NvbnZlcnNpb25zIChlKTsKLSAgd2hhdCA9 IHN0cmlwX3dyYXBfY29uc2VydmluZ190eXBlX2NvbnZlcnNpb25zICh3aGF0 KTsKLQotICBjb2RlID0gVFJFRV9DT0RFICh3aGF0KTsKLSAgaWYgKFRSRUVf VFlQRSAoZSkgIT0gVFJFRV9UWVBFICh3aGF0KSkKLSAgICByZXR1cm4gZmFs c2U7Ci0KLSAgaWYgKG9wZXJhbmRfZXF1YWxfcCAoZSwgd2hhdCwgMCkpCi0g ICAgcmV0dXJuIHRydWU7Ci0KLSAgaWYgKFRSRUVfQ09ERSAoZSkgIT0gU1NB X05BTUUpCi0gICAgcmV0dXJuIGZhbHNlOwotCi0gIHN0bXQgPSBTU0FfTkFN RV9ERUZfU1RNVCAoZSk7Ci0gIGlmIChnaW1wbGVfY29kZSAoc3RtdCkgIT0g R0lNUExFX0FTU0lHTgotICAgICAgfHwgZ2ltcGxlX2Fzc2lnbl9yaHNfY29k ZSAoc3RtdCkgIT0gY29kZSkKLSAgICByZXR1cm4gZmFsc2U7Ci0KLSAgc3dp dGNoIChnZXRfZ2ltcGxlX3Joc19jbGFzcyAoY29kZSkpCi0gICAgewotICAg IGNhc2UgR0lNUExFX0JJTkFSWV9SSFM6Ci0gICAgICBpZiAoIWV4cHJfZXF1 YWxfcCAoZ2ltcGxlX2Fzc2lnbl9yaHMyIChzdG10KSwgVFJFRV9PUEVSQU5E ICh3aGF0LCAxKSkpCi0JcmV0dXJuIGZhbHNlOwotICAgICAgLyogRmFsbHRo cnUuICAqLwotCi0gICAgY2FzZSBHSU1QTEVfVU5BUllfUkhTOgotICAgIGNh c2UgR0lNUExFX1NJTkdMRV9SSFM6Ci0gICAgICByZXR1cm4gZXhwcl9lcXVh bF9wIChnaW1wbGVfYXNzaWduX3JoczEgKHN0bXQpLCBUUkVFX09QRVJBTkQg KHdoYXQsIDApKTsKLSAgICBkZWZhdWx0OgotICAgICAgcmV0dXJuIGZhbHNl OwotICAgIH0KLX0KLQogLyogUmV0dXJucyB0cnVlIGlmIHdlIGNhbiBwcm92 ZSB0aGF0IEJBU0UgLSBPRkZTRVQgZG9lcyBub3Qgb3ZlcmZsb3cuICBGb3Ig bm93LAogICAgd2Ugb25seSBkZXRlY3QgdGhlIHNpdHVhdGlvbiB0aGF0IEJB U0UgPSBTT01FVEhJTkcgKyBPRkZTRVQsIHdoZXJlIHRoZQogICAgY2FsY3Vs YXRpb24gaXMgcGVyZm9ybWVkIGluIG5vbi13cmFwcGluZyB0eXBlLgogCiAg ICBUT0RPOiBNb3JlIGdlbmVyYWxseSwgd2UgY291bGQgdGVzdCBmb3IgdGhl IHNpdHVhdGlvbiB0aGF0CiAJIEJBU0UgPSBTT01FVEhJTkcgKyBPRkZTRVQn IGFuZCBPRkZTRVQgaXMgYmV0d2VlbiBPRkZTRVQnIGFuZCB6ZXJvLgotCSBU aGlzIHdvdWxkIHJlcXVpcmUga25vd2luZyB0aGUgc2lnbiBvZiBPRkZTRVQu CisJIFRoaXMgd291bGQgcmVxdWlyZSBrbm93aW5nIHRoZSBzaWduIG9mIE9G RlNFVC4gICovCiAKLQkgQWxzbywgd2Ugb25seSBsb29rIGZvciB0aGUgZmly c3QgYWRkaXRpb24gaW4gdGhlIGNvbXB1dGF0aW9uIG9mIEJBU0UuCi0JIE1v cmUgY29tcGxleCBhbmFseXNpcyB3b3VsZCBiZSBiZXR0ZXIsIGJ1dCBpbnRy b2R1Y2luZyBpdCBqdXN0IGZvcgotCSB0aGlzIG9wdGltaXphdGlvbiBzZWVt cyBsaWtlIGFuIG92ZXJraWxsLiAgKi8KLQogc3RhdGljIGJvb2wKLWRpZmZl cmVuY2VfY2Fubm90X292ZXJmbG93X3AgKHRyZWUgYmFzZSwgdHJlZSBvZmZz ZXQpCitkaWZmZXJlbmNlX2Nhbm5vdF9vdmVyZmxvd19wIChzdHJ1Y3QgaXZv cHRzX2RhdGEgKmRhdGEsIHRyZWUgYmFzZSwgdHJlZSBvZmZzZXQpCiB7CiAg IGVudW0gdHJlZV9jb2RlIGNvZGU7CiAgIHRyZWUgZTEsIGUyOworICBhZmZf dHJlZSBhZmZfZTEsIGFmZl9lMiwgYWZmX29mZnNldDsKIAogICBpZiAoIW5v d3JhcF90eXBlX3AgKFRSRUVfVFlQRSAoYmFzZSkpKQogICAgIHJldHVybiBm YWxzZTsKQEAgLTQ1NjAsMTMgKzQ1MDksMjcgQEAgc3RhdGljIGJvb2wKICAg ICAgIGUyID0gVFJFRV9PUEVSQU5EIChiYXNlLCAxKTsKICAgICB9CiAKLSAg LyogVE9ETzogZGVlcGVyIGluc3BlY3Rpb24gbWF5IGJlIG5lY2Vzc2FyeSB0 byBwcm92ZSB0aGUgZXF1YWxpdHkuICAqLworICAvKiBVc2UgYWZmaW5lIGV4 cGFuc2lvbiBhcyBkZWVwZXIgaW5zcGVjdGlvbiB0byBwcm92ZSB0aGUgZXF1 YWxpdHkuICAqLworICB0cmVlX3RvX2FmZl9jb21iaW5hdGlvbl9leHBhbmQg KGUyLCBUUkVFX1RZUEUgKGUyKSwKKwkJCQkgICZhZmZfZTIsICZkYXRhLT5u YW1lX2V4cGFuc2lvbl9jYWNoZSk7CisgIHRyZWVfdG9fYWZmX2NvbWJpbmF0 aW9uX2V4cGFuZCAob2Zmc2V0LCBUUkVFX1RZUEUgKG9mZnNldCksCisJCQkJ ICAmYWZmX29mZnNldCwgJmRhdGEtPm5hbWVfZXhwYW5zaW9uX2NhY2hlKTsK KyAgYWZmX2NvbWJpbmF0aW9uX3NjYWxlICgmYWZmX29mZnNldCwgLTEpOwog ICBzd2l0Y2ggKGNvZGUpCiAgICAgewogICAgIGNhc2UgUExVU19FWFBSOgot ICAgICAgcmV0dXJuIGV4cHJfZXF1YWxfcCAoZTEsIG9mZnNldCkgfHwgZXhw cl9lcXVhbF9wIChlMiwgb2Zmc2V0KTsKKyAgICAgIGFmZl9jb21iaW5hdGlv bl9hZGQgKCZhZmZfZTIsICZhZmZfb2Zmc2V0KTsKKyAgICAgIGlmIChhZmZf Y29tYmluYXRpb25femVyb19wICgmYWZmX2UyKSkKKwlyZXR1cm4gdHJ1ZTsK KworICAgICAgdHJlZV90b19hZmZfY29tYmluYXRpb25fZXhwYW5kIChlMSwg VFJFRV9UWVBFIChlMSksCisJCQkJICAgICAgJmFmZl9lMSwgJmRhdGEtPm5h bWVfZXhwYW5zaW9uX2NhY2hlKTsKKyAgICAgIGFmZl9jb21iaW5hdGlvbl9h ZGQgKCZhZmZfZTEsICZhZmZfb2Zmc2V0KTsKKyAgICAgIHJldHVybiBhZmZf Y29tYmluYXRpb25femVyb19wICgmYWZmX2UxKTsKKwogICAgIGNhc2UgUE9J TlRFUl9QTFVTX0VYUFI6Ci0gICAgICByZXR1cm4gZXhwcl9lcXVhbF9wIChl Miwgb2Zmc2V0KTsKKyAgICAgIGFmZl9jb21iaW5hdGlvbl9hZGQgKCZhZmZf ZTIsICZhZmZfb2Zmc2V0KTsKKyAgICAgIHJldHVybiBhZmZfY29tYmluYXRp b25femVyb19wICgmYWZmX2UyKTsKIAogICAgIGRlZmF1bHQ6CiAgICAgICBy ZXR1cm4gZmFsc2U7CkBAIC00NjkwLDcgKzQ2NTMsNyBAQCBpdl9lbGltaW5h dGlvbl9jb21wYXJlX2x0IChzdHJ1Y3QgaXZvcHRzX2RhdGEgKmRhdAogICBv ZmZzZXQgPSBmb2xkX2J1aWxkMiAoTVVMVF9FWFBSLCBUUkVFX1RZUEUgKGNh bmQtPml2LT5zdGVwKSwKIAkJCWNhbmQtPml2LT5zdGVwLAogCQkJZm9sZF9j b252ZXJ0IChUUkVFX1RZUEUgKGNhbmQtPml2LT5zdGVwKSwgYSkpOwotICBp ZiAoIWRpZmZlcmVuY2VfY2Fubm90X292ZXJmbG93X3AgKGNhbmQtPml2LT5i YXNlLCBvZmZzZXQpKQorICBpZiAoIWRpZmZlcmVuY2VfY2Fubm90X292ZXJm bG93X3AgKGRhdGEsIGNhbmQtPml2LT5iYXNlLCBvZmZzZXQpKQogICAgIHJl dHVybiBmYWxzZTsKIAogICAvKiBEZXRlcm1pbmUgdGhlIG5ldyBjb21wYXJp c29uIG9wZXJhdG9yLiAgKi8KQEAgLTY4MTUsNiArNjc3OCw3IEBAIHRyZWVf c3NhX2l2X29wdGltaXplX2ZpbmFsaXplIChzdHJ1Y3QgaXZvcHRzX2RhdGEK ICAgZGF0YS0+aXZfY2FuZGlkYXRlcy5yZWxlYXNlICgpOwogICBkZWxldGUg ZGF0YS0+aW52X2V4cHJfdGFiOwogICBkYXRhLT5pbnZfZXhwcl90YWIgPSBO VUxMOworICBmcmVlX2FmZmluZV9leHBhbmRfY2FjaGUgKCZkYXRhLT5uYW1l X2V4cGFuc2lvbl9jYWNoZSk7CiB9CiAKIC8qIFJldHVybnMgdHJ1ZSBpZiB0 aGUgbG9vcCBib2R5IEJPRFkgaW5jbHVkZXMgYW55IGZ1bmN0aW9uIGNhbGxz LiAgKi8K --001a11c2e77298c322050091f92b--