From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sourceware.org (Postfix) with ESMTPS id D39C73857C4A for ; Sun, 9 Aug 2020 21:25:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org D39C73857C4A Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=inria.fr Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=marc.glisse@inria.fr X-IronPort-AV: E=Sophos;i="5.75,455,1589234400"; d="scan'208";a="462936056" Received: from grove.saclay.inria.fr ([193.55.177.244]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 09 Aug 2020 23:25:05 +0200 Date: Sun, 9 Aug 2020 23:24:54 +0200 (CEST) From: Marc Glisse X-X-Sender: glisse@grove.saclay.inria.fr To: gcc-patches@gcc.gnu.org Subject: Simplify X * C1 == C2 with wrapping overflow In-Reply-To: Message-ID: References: User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 Content-Type: MULTIPART/MIXED; BOUNDARY="8323329-393194599-1597008305=:2882193" X-Spam-Status: No, score=-8.5 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: Sun, 09 Aug 2020 21:25:25 -0000 This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. --8323329-393194599-1597008305=:2882193 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII Odd numbers are invertible in Z / 2^n Z, so X * C1 == C2 can be rewritten as X == C2 * inv(C1) when overflow wraps. mod_inv should probably be updated to better match the other wide_int functions, but that's a separate issue. Bootstrap+regtest on x86_64-pc-linux-gnu. 2020-08-10 Marc Glisse PR tree-optimization/95433 * match.pd (X * C1 == C2): Handle wrapping overflow. * expr.c (maybe_optimize_mod_cmp): Qualify call to mod_inv. (mod_inv): Move... * wide-int.cc (mod_inv): ... here. * wide-int.h (mod_inv): Declare it. * gcc.dg/tree-ssa/pr95433-2.c: New file. -- Marc Glisse --8323329-393194599-1597008305=:2882193 Content-Type: TEXT/x-diff; name=equal2.patch Content-Transfer-Encoding: BASE64 Content-ID: Content-Description: Content-Disposition: inline; filename=equal2.patch ZGlmZiAtLWdpdCBhL2djYy9leHByLmMgYi9nY2MvZXhwci5jDQppbmRleCBh MTUwZmEwZDNiNS4uZWJmMGM5ZTQ3OTcgMTAwNjQ0DQotLS0gYS9nY2MvZXhw ci5jDQorKysgYi9nY2MvZXhwci5jDQpAQCAtMTE4NTksMzggKzExODU5LDYg QEAgc3RyaW5nX2NvbnN0YW50ICh0cmVlIGFyZywgdHJlZSAqcHRyX29mZnNl dCwgdHJlZSAqbWVtX3NpemUsIHRyZWUgKmRlY2wpDQogICByZXR1cm4gaW5p dDsNCiB9DQogDA0KLS8qIENvbXB1dGUgdGhlIG1vZHVsYXIgbXVsdGlwbGlj YXRpdmUgaW52ZXJzZSBvZiBBIG1vZHVsbyBNDQotICAgdXNpbmcgZXh0ZW5k ZWQgRXVjbGlkJ3MgYWxnb3JpdGhtLiAgQXNzdW1lcyBBIGFuZCBNIGFyZSBj b3ByaW1lLiAgKi8NCi1zdGF0aWMgd2lkZV9pbnQNCi1tb2RfaW52IChjb25z dCB3aWRlX2ludCAmYSwgY29uc3Qgd2lkZV9pbnQgJmIpDQotew0KLSAgLyog VmVyaWZ5IHRoZSBhc3N1bXB0aW9uLiAgKi8NCi0gIGdjY19jaGVja2luZ19h c3NlcnQgKHdpOjplcV9wICh3aTo6Z2NkIChhLCBiKSwgMSkpOw0KLQ0KLSAg dW5zaWduZWQgaW50IHAgPSBhLmdldF9wcmVjaXNpb24gKCkgKyAxOw0KLSAg Z2NjX2NoZWNraW5nX2Fzc2VydCAoYi5nZXRfcHJlY2lzaW9uICgpICsgMSA9 PSBwKTsNCi0gIHdpZGVfaW50IGMgPSB3aWRlX2ludDo6ZnJvbSAoYSwgcCwg VU5TSUdORUQpOw0KLSAgd2lkZV9pbnQgZCA9IHdpZGVfaW50Ojpmcm9tIChi LCBwLCBVTlNJR05FRCk7DQotICB3aWRlX2ludCB4MCA9IHdpZGVfaW50Ojpm cm9tICgwLCBwLCBVTlNJR05FRCk7DQotICB3aWRlX2ludCB4MSA9IHdpZGVf aW50Ojpmcm9tICgxLCBwLCBVTlNJR05FRCk7DQotDQotICBpZiAod2k6OmVx X3AgKGIsIDEpKQ0KLSAgICByZXR1cm4gd2lkZV9pbnQ6OmZyb20gKDEsIHAs IFVOU0lHTkVEKTsNCi0NCi0gIHdoaWxlICh3aTo6Z3RfcCAoYywgMSwgVU5T SUdORUQpKQ0KLSAgICB7DQotICAgICAgd2lkZV9pbnQgdCA9IGQ7DQotICAg ICAgd2lkZV9pbnQgcSA9IHdpOjpkaXZtb2RfdHJ1bmMgKGMsIGQsIFVOU0lH TkVELCAmZCk7DQotICAgICAgYyA9IHQ7DQotICAgICAgd2lkZV9pbnQgcyA9 IHgwOw0KLSAgICAgIHgwID0gd2k6OnN1YiAoeDEsIHdpOjptdWwgKHEsIHgw KSk7DQotICAgICAgeDEgPSBzOw0KLSAgICB9DQotICBpZiAod2k6Omx0X3Ag KHgxLCAwLCBTSUdORUQpKQ0KLSAgICB4MSArPSBkOw0KLSAgcmV0dXJuIHgx Ow0KLX0NCi0NCiAvKiBPcHRpbWl6ZSB4ICUgQzEgPT0gQzIgZm9yIHNpZ25l ZCBtb2R1bG8gaWYgQzEgaXMgYSBwb3dlciBvZiB0d28gYW5kIEMyDQogICAg aXMgbm9uLXplcm8gYW5kIEMzICgoMTw8KHByZWMtMSkpIHwgKEMxIC0gMSkp Og0KICAgIGZvciBDMiA+IDAgdG8geCAmIEMzID09IEMyDQpAQCAtMTIxMDEs NyArMTIwNjksNyBAQCBtYXliZV9vcHRpbWl6ZV9tb2RfY21wIChlbnVtIHRy ZWVfY29kZSBjb2RlLCB0cmVlICphcmcwLCB0cmVlICphcmcxKQ0KICAgdyA9 IHdpOjpscnNoaWZ0ICh3LCBzaGlmdCk7DQogICB3aWRlX2ludCBhID0gd2lk ZV9pbnQ6OmZyb20gKHcsIHByZWMgKyAxLCBVTlNJR05FRCk7DQogICB3aWRl X2ludCBiID0gd2k6OnNoaWZ0ZWRfbWFzayAocHJlYywgMSwgZmFsc2UsIHBy ZWMgKyAxKTsNCi0gIHdpZGVfaW50IG0gPSB3aWRlX2ludDo6ZnJvbSAobW9k X2ludiAoYSwgYiksIHByZWMsIFVOU0lHTkVEKTsNCisgIHdpZGVfaW50IG0g PSB3aWRlX2ludDo6ZnJvbSAod2k6Om1vZF9pbnYgKGEsIGIpLCBwcmVjLCBV TlNJR05FRCk7DQogICB0cmVlIGMzID0gd2lkZV9pbnRfdG9fdHJlZSAodHlw ZSwgbSk7DQogICB0cmVlIGM1ID0gTlVMTF9UUkVFOw0KICAgd2lkZV9pbnQg ZCwgZTsNCmRpZmYgLS1naXQgYS9nY2MvbWF0Y2gucGQgYi9nY2MvbWF0Y2gu cGQNCmluZGV4IDdlNWM1YTZlYWU2Li5jM2I4ODE2OGFjNCAxMDA2NDQNCi0t LSBhL2djYy9tYXRjaC5wZA0KKysrIGIvZ2NjL21hdGNoLnBkDQpAQCAtMzgy OCw3ICszODI4LDkgQEAgREVGSU5FX0lOVF9BTkRfRkxPQVRfUk9VTkRfRk4g KFJJTlQpDQogICAgICAoY21wIEAwIEAyKSkpKSkpDQogDQogLyogRm9yIGlu dGVncmFsIHR5cGVzIHdpdGggdW5kZWZpbmVkIG92ZXJmbG93IGZvbGQNCi0g ICB4ICogQzEgPT0gQzIgaW50byB4ID09IEMyIC8gQzEgb3IgZmFsc2UuICAq Lw0KKyAgIHggKiBDMSA9PSBDMiBpbnRvIHggPT0gQzIgLyBDMSBvciBmYWxz ZS4NCisgICBJZiBvdmVyZmxvdyB3cmFwcyBhbmQgQzEgaXMgb2RkLCBzaW1w bGlmeSB0byB4ID09IEMyIC8gQzEgaW4gdGhlIHJpbmcNCisgICBaIC8gMl5u IFouICAqLw0KIChmb3IgY21wIChlcSBuZSkNCiAgKHNpbXBsaWZ5DQogICAo Y21wIChtdWx0IEAwIElOVEVHRVJfQ1NUQDEpIElOVEVHRVJfQ1NUQDIpDQpA QCAtMzgzOSw3ICszODQxLDIwIEBAIERFRklORV9JTlRfQU5EX0ZMT0FUX1JP VU5EX0ZOIChSSU5UKQ0KICAgICAoaWYgKHdpOjptdWx0aXBsZV9vZl9wICh3 aTo6dG9fd2lkZXN0IChAMiksIHdpOjp0b193aWRlc3QgKEAxKSwNCiAJCQkg ICAgVFlQRV9TSUdOIChUUkVFX1RZUEUgKEAwKSksICZxdW90KSkNCiAgICAg IChjbXAgQDAgeyB3aWRlX2ludF90b190cmVlIChUUkVFX1RZUEUgKEAwKSwg cXVvdCk7IH0pDQotICAgICB7IGNvbnN0YW50X2Jvb2xlYW5fbm9kZSAoY21w ID09IE5FX0VYUFIsIHR5cGUpOyB9KSkpKSkNCisgICAgIHsgY29uc3RhbnRf Ym9vbGVhbl9ub2RlIChjbXAgPT0gTkVfRVhQUiwgdHlwZSk7IH0pKQ0KKyAg IChpZiAoSU5URUdSQUxfVFlQRV9QIChUUkVFX1RZUEUgKEAwKSkNCisJJiYg VFlQRV9PVkVSRkxPV19XUkFQUyAoVFJFRV9UWVBFIChAMCkpDQorCSYmICh3 aTo6Yml0X2FuZCAod2k6OnRvX3dpZGUgKEAxKSwgMSkgPT0gMSkpDQorICAg IChjbXAgQDANCisgICAgIHsNCisgICAgICAgdHJlZSBpdHlwZSA9IFRSRUVf VFlQRSAoQDApOw0KKyAgICAgICBpbnQgcCA9IFRZUEVfUFJFQ0lTSU9OIChp dHlwZSk7DQorICAgICAgIHdpZGVfaW50IG0gPSB3aTo6b25lIChwICsgMSkg PDwgcDsNCisgICAgICAgd2lkZV9pbnQgYSA9IHdpZGVfaW50Ojpmcm9tICh3 aTo6dG9fd2lkZSAoQDEpLCBwICsgMSwgVU5TSUdORUQpOw0KKyAgICAgICB3 aWRlX2ludCBpID0gd2lkZV9pbnQ6OmZyb20gKHdpOjptb2RfaW52IChhLCBt KSwNCisJCQkJICAgIHAsIFRZUEVfU0lHTiAoaXR5cGUpKTsNCisgICAgICAg d2lkZV9pbnRfdG9fdHJlZSAoaXR5cGUsIHdpOjptdWwgKGksIHdpOjp0b193 aWRlIChAMikpKTsNCisgICAgIH0pKSkpKQ0KIA0KIC8qIFNpbXBsaWZ5IGNv bXBhcmlzb24gb2Ygc29tZXRoaW5nIHdpdGggaXRzZWxmLiAgRm9yIElFRUUN CiAgICBmbG9hdGluZy1wb2ludCwgd2UgY2FuIG9ubHkgZG8gc29tZSBvZiB0 aGVzZSBzaW1wbGlmaWNhdGlvbnMuICAqLw0KZGlmZiAtLWdpdCBhL2djYy90 ZXN0c3VpdGUvZ2NjLmRnL3RyZWUtc3NhL3ByOTU0MzMtMi5jIGIvZ2NjL3Rl c3RzdWl0ZS9nY2MuZGcvdHJlZS1zc2EvcHI5NTQzMy0yLmMNCm5ldyBmaWxl IG1vZGUgMTAwNjQ0DQppbmRleCAwMDAwMDAwMDAwMC4uYzgzMGEzZDE5NWYN Ci0tLSAvZGV2L251bGwNCisrKyBiL2djYy90ZXN0c3VpdGUvZ2NjLmRnL3Ry ZWUtc3NhL3ByOTU0MzMtMi5jDQpAQCAtMCwwICsxLDE1IEBADQorLyogeyBk Zy1kbyBjb21waWxlIH0gKi8NCisvKiB7IGRnLW9wdGlvbnMgIi1PIC1md3Jh cHYgLWZkdW1wLXRyZWUtZ2ltcGxlIiB9ICovDQorDQordHlwZWRlZiBfX0lO VDMyX1RZUEVfXyBpbnQzMl90Ow0KK3R5cGVkZWYgdW5zaWduZWQgX19JTlQz Ml9UWVBFX18gdWludDMyX3Q7DQorDQoraW50IGUoaW50MzJfdCB4KXtyZXR1 cm4gMyp4PT01O30NCitpbnQgZihpbnQzMl90IHgpe3JldHVybiAzKng9PS01 O30NCitpbnQgZyhpbnQzMl90IHgpe3JldHVybiAtMyp4PT01O30NCitpbnQg aChpbnQzMl90IHgpe3JldHVybiA3Kng9PTM7fQ0KK2ludCBpKHVpbnQzMl90 IHgpe3JldHVybiA3Kng9PTM7fQ0KKw0KKy8qIHsgZGctZmluYWwgeyBzY2Fu LXRyZWUtZHVtcC10aW1lcyAiPT0gMTQzMTY1NTc2NyIgMSAiZ2ltcGxlIiB9 IH0gKi8NCisvKiB7IGRnLWZpbmFsIHsgc2Nhbi10cmVlLWR1bXAtdGltZXMg Ij09IC0xNDMxNjU1NzY3IiAyICJnaW1wbGUiIH0gfSAqLw0KKy8qIHsgZGct ZmluYWwgeyBzY2FuLXRyZWUtZHVtcC10aW1lcyAiPT0gNjEzNTY2NzU3IiAy ICJnaW1wbGUiIH0gfSAqLw0KZGlmZiAtLWdpdCBhL2djYy93aWRlLWludC5j YyBiL2djYy93aWRlLWludC5jYw0KaW5kZXggMDNiZTAwNzQ4MTYuLmY0ZDk0 OWMzOGEwIDEwMDY0NA0KLS0tIGEvZ2NjL3dpZGUtaW50LmNjDQorKysgYi9n Y2Mvd2lkZS1pbnQuY2MNCkBAIC0yMjIzLDYgKzIyMjMsMzkgQEAgd2k6OnJv dW5kX3VwX2Zvcl9tYXNrIChjb25zdCB3aWRlX2ludCAmdmFsLCBjb25zdCB3 aWRlX2ludCAmbWFzaykNCiAgIHJldHVybiAodmFsIHwgdG1wKSAmIC10bXA7 DQogfQ0KIA0KKy8qIENvbXB1dGUgdGhlIG1vZHVsYXIgbXVsdGlwbGljYXRp dmUgaW52ZXJzZSBvZiBBIG1vZHVsbyBCDQorICAgdXNpbmcgZXh0ZW5kZWQg RXVjbGlkJ3MgYWxnb3JpdGhtLiAgQXNzdW1lcyBBIGFuZCBCIGFyZSBjb3By aW1lLA0KKyAgIGFuZCB0aGF0IEEgYW5kIEIgaGF2ZSB0aGUgc2FtZSBwcmVj aXNpb24uICAqLw0KK3dpZGVfaW50DQord2k6Om1vZF9pbnYgKGNvbnN0IHdp ZGVfaW50ICZhLCBjb25zdCB3aWRlX2ludCAmYikNCit7DQorICAvKiBWZXJp ZnkgdGhlIGFzc3VtcHRpb24uICAqLw0KKyAgZ2NjX2NoZWNraW5nX2Fzc2Vy dCAod2k6OmVxX3AgKHdpOjpnY2QgKGEsIGIpLCAxKSk7DQorDQorICB1bnNp Z25lZCBpbnQgcCA9IGEuZ2V0X3ByZWNpc2lvbiAoKSArIDE7DQorICBnY2Nf Y2hlY2tpbmdfYXNzZXJ0IChiLmdldF9wcmVjaXNpb24gKCkgKyAxID09IHAp Ow0KKyAgd2lkZV9pbnQgYyA9IHdpZGVfaW50Ojpmcm9tIChhLCBwLCBVTlNJ R05FRCk7DQorICB3aWRlX2ludCBkID0gd2lkZV9pbnQ6OmZyb20gKGIsIHAs IFVOU0lHTkVEKTsNCisgIHdpZGVfaW50IHgwID0gd2lkZV9pbnQ6OmZyb20g KDAsIHAsIFVOU0lHTkVEKTsNCisgIHdpZGVfaW50IHgxID0gd2lkZV9pbnQ6 OmZyb20gKDEsIHAsIFVOU0lHTkVEKTsNCisNCisgIGlmICh3aTo6ZXFfcCAo YiwgMSkpDQorICAgIHJldHVybiB3aWRlX2ludDo6ZnJvbSAoMSwgcCwgVU5T SUdORUQpOw0KKw0KKyAgd2hpbGUgKHdpOjpndF9wIChjLCAxLCBVTlNJR05F RCkpDQorICAgIHsNCisgICAgICB3aWRlX2ludCB0ID0gZDsNCisgICAgICB3 aWRlX2ludCBxID0gd2k6OmRpdm1vZF90cnVuYyAoYywgZCwgVU5TSUdORUQs ICZkKTsNCisgICAgICBjID0gdDsNCisgICAgICB3aWRlX2ludCBzID0geDA7 DQorICAgICAgeDAgPSB3aTo6c3ViICh4MSwgd2k6Om11bCAocSwgeDApKTsN CisgICAgICB4MSA9IHM7DQorICAgIH0NCisgIGlmICh3aTo6bHRfcCAoeDEs IDAsIFNJR05FRCkpDQorICAgIHgxICs9IGQ7DQorICByZXR1cm4geDE7DQor fQ0KKw0KIC8qDQogICogUHJpdmF0ZSB1dGlsaXRpZXMuDQogICovDQpkaWZm IC0tZ2l0IGEvZ2NjL3dpZGUtaW50LmggYi9nY2Mvd2lkZS1pbnQuaA0KaW5k ZXggYmIwZDE2Yjk5YjEuLjM5Y2Q1YjliZDE3IDEwMDY0NA0KLS0tIGEvZ2Nj L3dpZGUtaW50LmgNCisrKyBiL2djYy93aWRlLWludC5oDQpAQCAtMzM4OSw2 ICszMzg5LDggQEAgbmFtZXNwYWNlIHdpDQogICB3aWRlX2ludCByb3VuZF9k b3duX2Zvcl9tYXNrIChjb25zdCB3aWRlX2ludCAmLCBjb25zdCB3aWRlX2lu dCAmKTsNCiAgIHdpZGVfaW50IHJvdW5kX3VwX2Zvcl9tYXNrIChjb25zdCB3 aWRlX2ludCAmLCBjb25zdCB3aWRlX2ludCAmKTsNCiANCisgIHdpZGVfaW50 IG1vZF9pbnYgKGNvbnN0IHdpZGVfaW50ICZhLCBjb25zdCB3aWRlX2ludCAm Yik7DQorDQogICB0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4NCiAgIFQgbWFzayAo dW5zaWduZWQgaW50LCBib29sKTsNCiANCg== --8323329-393194599-1597008305=:2882193--