From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from NAM12-BN8-obe.outbound.protection.outlook.com (mail-bn8nam12on2125.outbound.protection.outlook.com [40.107.237.125]) by sourceware.org (Postfix) with ESMTPS id DB6F03865C28 for ; Fri, 6 Aug 2021 21:17:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DB6F03865C28 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=cA7it5I8uAPP2xzbPZ+cR34op9yru6jjHpD9nOcmt55f7t02o7dtEsUtMnvOl5dMhfhYzzduvtGya41yrw93dtLlzTbXR3YJEHRQHtWHS/bhPKGLwPRI16AO2lpDyzxhsfgsymrIv0xMEGlFqVCi3VBVqbZlQkP2Sw32etg8JglSGHMpu3+6g8e6lHBkxJ4ORqFGla73oA1xJPHhS1vKaYhDIQtDWWokkkcoxLhkvgRnbqHrXyjnp4MXPCnwi/EXIUwWEn/5gaS/GlZX2Z0DYXVgtx2FsuzDlQNzu8tgV6FrP79ZTz+w19QyMeU2dgPJ96wmK32G3UqH23NG1P3jQQ== 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-SenderADCheck; bh=YoU47CtJU4sYtcrorLg3LMXj0BZrwqEQ59QUkW7Luz8=; b=RGVSDEZc9ahy+5mUAvm4ZZ+cx8n0w5bbbLhtEo9mT645sXVOOLbAkYREgS7+W8oTrSmjbyntXu1gRJEOUTPKDK0mp5kO7Ck0I3Z1kV3MrimP7Vas/lnvoZSTX9q/WzC2s3GlJKEOj3QFL9wjGUOHcqRcnIMvmFwXounUHPw5YaWZFSIla4GwGazwdObkvQnRwx5q7V/wrhbsjNm53fnkkCMNEWirl3opTGSZqjw2XhPc0atJBuoWrtDmH9kghoGXatYXeDXfYgjpu1yU1W1VnEr0TigZRx2IzLROnPYAsVvWl5nqtzNAlUIC/EmZHQn4pE4YIM/MG1+XBSWJsriqQA== 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 CY4PR2101MB0801.namprd21.prod.outlook.com (2603:10b6:910:8d::25) by CY4PR21MB0503.namprd21.prod.outlook.com (2603:10b6:903:dc::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4415.2; Fri, 6 Aug 2021 21:17:03 +0000 Received: from CY4PR2101MB0801.namprd21.prod.outlook.com ([fe80::21fe:400a:5e9d:8a32]) by CY4PR2101MB0801.namprd21.prod.outlook.com ([fe80::21fe:400a:5e9d:8a32%5]) with mapi id 15.20.4415.009; Fri, 6 Aug 2021 21:17:03 +0000 From: Victor Tong To: Richard Biener CC: Marc Glisse , "gcc-patches@gcc.gnu.org" Subject: Re: [EXTERNAL] Re: [PATCH] tree-optimization: Optimize division followed by multiply [PR95176] Thread-Topic: [EXTERNAL] Re: [PATCH] tree-optimization: Optimize division followed by multiply [PR95176] Thread-Index: AQHXJoDrR4fklL4IYku64pH3Fv0p3qrIMcqAgDljMP+ABwtigIAO0uy/gAKMnwCAAg2QAIACfg6AgAwMpn6ALklBAIAO4Vis Date: Fri, 6 Aug 2021 21:17:02 +0000 Message-ID: References: <1e409dd-c5a8-a59f-d7ba-86ae805ab54f@hippo.saclay.inria.fr> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: yes X-MS-TNEF-Correlator: msip_labels: MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Enabled=True; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_SiteId=72f988bf-86f1-41af-91ab-2d7cd011db47; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_SetDate=2021-08-06T21:17:01.928Z; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Name=General; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_ContentBits=0; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Method=Standard; x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: d797276b-5740-4f22-3719-08d9591f893b x-ms-traffictypediagnostic: CY4PR21MB0503: x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:10000; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: yCP3alUuP63kt42CFEmlqM+hnkg1vVU+8wpPXa6LgIU3jAqwM58SPxDb9Hu5r7hMLnNZJ0AWHHvHk81Egyy7i+oLhY+A5SdrQ616cTklHiy817am+fS0gd9m0cKbk326c1mP5vJGeKK8S+B2w0dv3Fe6OHADDu2sfmXZRPAto6whYXaa+5ZqkV2aPse2kFi12l8hL4Bub/rKlYzQ/4uiYWesasiE1Y3EGB7RulSnva3ApEmLKYn2sqKhycmzNC4I1dyKVmijtr7SQdoYktQA+Yad0fwv44HRsQ4BzUfaYWb9SRaUzQdX4dCuJPYuGCvtDhTj2KhG02xBDEYBH3NT12eGSHHVTzKBpQLt5n4z5dunIbnJptOlWBpquK5wAv7M26BVEFIj8FW7OxWidzRwuTAhy+VTlP2aFZcdn1Z/jCmz6tlYyV2+jDsAktCj2zSHJ91GjvfCQVxQjzMT+XFYlhx+TcqagDBo4Ks6FEcqQ1dV5Xkl2LHdlkrVaOrO5k/IPqxAsq/33BY9IZuLQaSsWJ5vJ6oo/30ylWf1pF9L7lzPRaahWvJHijdrO0QONGdQfShwSQH7gE/ccOxmWIVkaBXP3FPB8QRVxVDfAtt+6/RtFHlHSVwXND2yy6tUtX107YujG7QfUWrc49V40PUXeQDCznIPI0nOvuOzvk6F7vlj60CAFjlYhU93F1iEeZFI5xe6PmBrmLM+Hf4sdoj0MSC9ba9ked7fhwmD2xWNvNsXEAzrgeYP8KcVURC+bn8rXStXuGA1NPUCQVVGxQ3qM5Ns2AWZgknYQi2eMsX9tb8= x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:CY4PR2101MB0801.namprd21.prod.outlook.com; PTR:; CAT:NONE; SFS:(4636009)(366004)(86362001)(66616009)(122000001)(966005)(52536014)(66946007)(186003)(71200400001)(4326008)(54906003)(8676002)(508600001)(10290500003)(83380400001)(33656002)(5660300002)(66446008)(8990500004)(91956017)(66556008)(66476007)(76116006)(64756008)(38100700002)(38070700005)(26005)(6506007)(53546011)(82960400001)(82950400001)(6916009)(99936003)(8936002)(9686003)(7696005)(55016002)(2906002)(316002); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?oYJZNOeQTXvWZqF9h+EKq4um10nLbI6/Laj7/vAAxVhJh9lZsunu89zrhF?= =?iso-8859-1?Q?qi0egF5plhVH9e67/5ZIwya5UvxUb2QUEt0hPYY3Zaahumu/rCPMw9ZQXG?= =?iso-8859-1?Q?Ahrqoq/JnkfKE/rt2cnR2RVRHUOE8pHPFJt/SxacUBuTmfAW6TEOYYoPvN?= =?iso-8859-1?Q?9Pj/eQy7UGfCDEFjd/9zoUl7DK+7R4bklnRZQn1KSw8l52B3WcBbjx9XH4?= =?iso-8859-1?Q?iR8I9+s2LAVgmP9uRjVQcXA3WB5loopRmWiNxAB0fIRdfpYpFNAi+1js5i?= =?iso-8859-1?Q?XDi9OcqBa0T7NoS7h7y4miRwSyDQqKgqAi6Wt04rpe/mon8ftMTj4vZwQO?= =?iso-8859-1?Q?EOre+9PsZ5diFzowngb3q6wTO4nGY9uBsU/Mmq+hlVaIV76HAK22r9dGIk?= =?iso-8859-1?Q?QI2mRaWahHKql/6XyWvBzNXfk/5V+jCcMdX5FV+Coz+uurU1qeI80kfLPR?= =?iso-8859-1?Q?3v1+eg8sNVf6Y31iTIMDvqRn0Dkd3L47UXNbgBC2ElHxJBLFJuYdR32bht?= =?iso-8859-1?Q?NOIBygXVk8XnHF5hlrMmXV4N3VyuJwAFLfhExETYNumA7PasPTxfrUXUwk?= =?iso-8859-1?Q?9suV+Oafo9K6M5J64T13HuPsgfrbAfJYwsVysn0/ap63yrRNqcwLehjNZI?= =?iso-8859-1?Q?/L4mvOFhp/9Ft5FKlCYulysiK2YUnt1CRqfJ1JyNFz/HZHyGc9RtjDi70z?= =?iso-8859-1?Q?NjB90o0Q01wqkO2ivbYY39BPZsUr61xXm0yvo6ubTCfCNMZLQQhkaCDOnI?= =?iso-8859-1?Q?Z7LTKfA81ZcHeqWeyaoXrRntYM69I6kcL3SUUevNGLhdEhkVkjnpKz1/5Y?= =?iso-8859-1?Q?f5PhipHAhUlVo9REqpW/ySpdSaddCC8rpqrleJo7sJ+SiMMsmcBY7rYvws?= =?iso-8859-1?Q?L2BNnABUZVI1sCoIGeO+vZ50HtZrIR4LziNq+J8XtWa/uj3L3sx2XSJB13?= =?iso-8859-1?Q?X8ZFKeVYvAYnusfyBwLqgWd+HxOONfihgYdQp6M9or/DFVK46l69+bnjmH?= =?iso-8859-1?Q?4tO6Uet0/GoAgYzF13Oa/hGltUfuVxoSPHYv1JY2mUptzd/ushmwzc8ple?= =?iso-8859-1?Q?x+ii0etwdOG3xUHfuCQ+fC5ii5r3SppcxoattQnXnWwJ3t816TLwLRoFTy?= =?iso-8859-1?Q?0ZeDu6hC/RLE8q4bjToKt/4TCqsKrNp8iwwlwZGAXH7zEMSknfQejG2Flz?= =?iso-8859-1?Q?GIiqnnTWGHsIkdMIf7NWHiNq1UgyJI1pT1YOCwbpeb2O3R7II+K5oGBzjv?= =?iso-8859-1?Q?ip9S8FR97bibfN6J7Zdq/OLdehNpCQF74ql3KuqbY3PFsegikj/OdQucug?= =?iso-8859-1?Q?6FSZOo7O6AHMZBayW2LqYlRXMi4SnfsMa/4079+cAkii3a8=3D?= x-ms-exchange-transport-forked: True Content-Type: multipart/mixed; boundary="_002_CY4PR2101MB0801630BD910A329C791ACDCCCF39CY4PR2101MB0801_" MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: CY4PR2101MB0801.namprd21.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: d797276b-5740-4f22-3719-08d9591f893b X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Aug 2021 21:17:02.9374 (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: nt9x5fl2dMnZSC6iYmrDPB0Z9Kt8LVe5zP8ernaEM8dCLhaBDbeJAVYbbJarhKDrjzwSS8e8kdJi43j2/GRa5g== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY4PR21MB0503 X-Spam-Status: No, score=-0.7 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FORGED_SPF_HELO, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_NONE, TXREP autolearn=no 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-List-Received-Date: Fri, 06 Aug 2021 21:17:17 -0000 --_002_CY4PR2101MB0801630BD910A329C791ACDCCCF39CY4PR2101MB0801_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Thanks for the feedback. Here's the updated pattern:=0A= =0A= /* X - (X - Y) --> Y */=0A= (simplify=0A= (minus (convert1? @0) (convert2? (minus@2 (convert3? @@0) @1)))=0A= (if (ANY_INTEGRAL_TYPE_P (type)=0A= && TYPE_OVERFLOW_UNDEFINED(type)=0A= && !TYPE_OVERFLOW_SANITIZED(type)=0A= && ANY_INTEGRAL_TYPE_P (TREE_TYPE(@2))=0A= && TYPE_OVERFLOW_UNDEFINED(TREE_TYPE(@2))=0A= && !TYPE_OVERFLOW_SANITIZED(TREE_TYPE(@2))=0A= && ANY_INTEGRAL_TYPE_P (TREE_TYPE(@0))=0A= && TYPE_OVERFLOW_UNDEFINED(TREE_TYPE(@0))=0A= && !TYPE_OVERFLOW_SANITIZED(TREE_TYPE(@0))=0A= && TYPE_PRECISION (TREE_TYPE (@2)) <=3D TYPE_PRECISION (type)=0A= && TYPE_PRECISION (TREE_TYPE (@0)) <=3D TYPE_PRECISION (type))=0A= (convert @1)))=0A= =0A= I kept the TYPE_OVERFLOW_SANITIZED checks because I saw other patterns that= leverage undefined overflows check for it. I think this new pattern should= n't be applied if overflow sanitizer checks are enabled.=0A= =0A= >> why is this testing TREE_TYPE (@0)?=0A= =0A= I'm checking the type of @0 because I'm concerned that there could be a cas= e where @0's type isn't an integer type with undefined overflow. I tried cr= eating a test case and couldn't seem to create one where this is violated b= ut I kept the checks to avoid causing a regression. If I'm being overcautio= us and you feel that the type checks on @0 aren't needed, I can remove them= . I think the precision check on TREE_TYPE(@0) is needed to avoid truncatio= n cases though.=0A= =0A= >> Once we'd "inline" nop_convert genmatch would complain=0A= about this.=0A= =0A= Is someone working on inlining nop_convert? I'd like to avoid breaking some= one else's work if that's being worked on right now.=0A= =0A= I've also added some extra tests to cover this new pattern. I've attached a= patch with my latest changes.=0A= =0A= =0A= From: Richard Biener =0A= Sent: Wednesday, July 28, 2021 2:59 AM=0A= To: Victor Tong =0A= Cc: Marc Glisse ; gcc-patches@gcc.gnu.org =0A= Subject: Re: [EXTERNAL] Re: [PATCH] tree-optimization: Optimize division fo= llowed by multiply [PR95176] =0A= =A0=0A= On Tue, Jun 29, 2021 at 1:10 AM Victor Tong wrote:= =0A= >=0A= > Thanks Richard and Marc.=0A= >=0A= > I wrote the following test case to compare the outputs of fn1() and fn1No= Opt() below with my extra pattern being applied. I tested the two functions= with all of the integers from INT_MIN to INT_MAX.=0A= >=0A= > long=0A= > fn1 (int x)=0A= > {=0A= >=A0=A0 return 42L - (long)(42 - x);=0A= > }=0A= >=0A= > #pragma GCC push_options=0A= > #pragma GCC optimize ("O0")=0A= > long=0A= > fn1NoOpt (int x)=0A= > {=0A= >=A0=A0 volatile int y =3D (42 - x);=0A= >=A0=A0 return 42L - (long)y;=0A= > }=0A= > #pragma GCC pop_options=0A= >=0A= > int main ()=0A= > {=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 for (long i=3DINT_MIN; i<=3DINT_MAX;i++)=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 {=0A= >=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 auto valNoOpt =3D fn1NoOp= t(i);=0A= >=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 auto valOpt =3D fn1(i);= =0A= >=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 if (valNoOpt !=3D valOpt)= =0A= >=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 p= rintf("valOpt=3D%ld, valNoOpt=3D%ld\n", valOpt, valNoOpt);=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 }=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 return 0;=0A= > }=0A= >=0A= > I saw that the return values of fn1() and fn1NoOpt() differed when the in= put was between INT_MIN and INT_MIN+42 inclusive. When passing values in th= is range to fn1NoOpt(), a signed overflow is triggered which causes the val= ue to differ (undefined behavior). This seems to go in line with what Marc = described and I think the transformation is correct in the scenario above. = I do think that type casts that result in truncation (i.e. from a higher pr= ecision to a lower one) or with unsigned types will result in an incorrect = transformation so those scenarios need to be avoided.=0A= >=0A= > Given that the extra pattern I'm adding is taking advantage the undefined= behavior of signed integer overflow, I'm considering keeping the existing = nop_convert pattern in place and adding a new pattern to cover these new ca= ses. I'd also like to avoid touching nop_convert given that it's used in a = number of other patterns.=0A= >=0A= > This is the pattern I have currently:=0A= >=0A= >=A0=A0 (simplify=0A= >=A0=A0=A0=A0 (minus (convert1? @0) (convert2? (minus (convert3? @2) @1)))= =0A= >=A0=A0=A0=A0 (if (operand_equal_p(@0, @2, 0)=0A= =0A= The operand_equal_p should be reflected by using @0 in place of @2.=0A= =0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && INTEGRAL_TYPE_P (type)=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && TYPE_OVERFLOW_UNDEFINED(type)=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && !TYPE_OVERFLOW_SANITIZED(type)=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && INTEGRAL_TYPE_P (TREE_TYPE(@1))=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && TYPE_OVERFLOW_UNDEFINED(TREE_TYPE(@1))=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && !TYPE_OVERFLOW_SANITIZED(TREE_TYPE(@1))=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && !TYPE_UNSIGNED (TREE_TYPE (@1))=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && !TYPE_UNSIGNED (type)=0A= =0A= please group checks on common argument.=A0 I think a single test=0A= on INTEGRAL_TYPE_P (type) is enough, it could be ANY_INTEGRAL_TYPE_P=0A= to include vector and complex types.=0A= =0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && TYPE_PRECISION (TREE_TYPE (@1)) <=3D TYPE_PREC= ISION (type)=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && INTEGRAL_TYPE_P (TREE_TYPE(@0))=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && TYPE_OVERFLOW_UNDEFINED(TREE_TYPE(@0))=0A= =0A= why is this testing TREE_TYPE (@0)?=A0 The outer subtract is using 'type',= =0A= the inner subtract uses TREE_TYPE (@1) though you could place=0A= a capture on the minus to make what you test more obvious, like=0A= =0A= =A0 (minus (convert1? @0) (convert2? (minus@3 (convert3? @2) @1)))=0A= =0A= TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@3))=0A= =0A= there's one set of checks too much I think.=0A= =0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && !TYPE_OVERFLOW_SANITIZED(TREE_TYPE(@0))=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && !TYPE_UNSIGNED (TREE_TYPE (@0))=0A= =0A= we only ever have TYPE_OVERFLOW_UNDEFINED on singed types so=0A= the !TYPE_UNSIGNED checks are superfluous.=0A= =0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && TYPE_PRECISION (TREE_TYPE (@0)) <=3D TYPE_PREC= ISION (type)=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 && TREE_TYPE(@1) =3D=3D TREE_TYPE(@2))=0A= =0A= This check means that convert3 is never present since a MINUS requires=0A= compatible types.=0A= =0A= Sorry for the late reply.=0A= =0A= Note the pattern will necessarily be partly redundant with the=0A= =0A= =A0 (simplify=0A= =A0=A0 (minus (nop_convert1? (minus (nop_convert2? @0) @1)) @0)=0A= =A0=A0 (if (!ANY_INTEGRAL_TYPE_P (type)=0A= =A0=A0=A0=A0=A0=A0=A0 || TYPE_OVERFLOW_WRAPS (type))=0A= =A0=A0 (negate (view_convert @1))=0A= =A0=A0 (view_convert (negate @1))))=0A= =0A= pattern.=A0 Once we'd "inline" nop_convert genmatch would complain=0A= about this.=0A= =0A= >=A0=A0=A0=A0 (convert @1)))=0A= >=0A= > Is there a more concise/better way of writing the pattern? I was looking = for similar checks in match.pd and I couldn't find anything that I could le= verage.=0A= >=0A= > I also kept my pattern to the specific scenario I'm seeing with the regre= ssion to lower the risk of something breaking. I've limited @1 and @2 to ha= ve the same type.=0A= >=0A= > I'm also in favor of adding/running computer verification to make sure th= e transformation is legal. I've written some tests to verify that the patte= rn is being applied in the right scenarios and not being applied in others,= but I think there are too many possibilities to manually write them all. I= s there anything in GCC that can be used to verify that match.pd transforma= tions are correct? I'm thinking of something like Alive https://nam06.safel= inks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fgithub.com%2FAliveToolkit%= 2Falive2&data=3D04%7C01%7Cvitong%40microsoft.com%7C64334bd5c79443af04ec= 08d951ae6117%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C63763063167823109= 7%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1ha= WwiLCJXVCI6Mn0%3D%7C1000&sdata=3Dx9Heq%2Bjgb%2Fy1PJFZ0gT9yfkQuzOz0rzWnZ= sl7VOymp0%3D&reserved=3D0.=0A= >=0A= > Thanks,=0A= > Victor=0A= >=0A= >=0A= >=0A= > From: Richard Biener =0A= > Sent: Monday, June 21, 2021 12:08 AM=0A= > To: Marc Glisse =0A= > Cc: Victor Tong ; gcc-patches@gcc.gnu.org =0A= > Subject: Re: [EXTERNAL] Re: [PATCH] tree-optimization: Optimize division = followed by multiply [PR95176]=0A= >=0A= > On Sat, Jun 19, 2021 at 7:05 PM Marc Glisse wrote:= =0A= > >=0A= > > On Fri, 18 Jun 2021, Richard Biener wrote:=0A= > >=0A= > > >> Option 2: Add a new pattern to support scenarios that the existing n= op_convert pattern bails out on.=0A= > > >>=0A= > > >> Existing pattern:=0A= > > >>=0A= > > >> (simplify=0A= > > >>=A0=A0=A0 (minus (nop_convert1? @0) (nop_convert2? (minus (nop_conver= t3? @@0) @1)))=0A= > > >>=A0=A0=A0 (view_convert @1))=0A= > >=0A= > > I tried to check with a program when=0A= > >=0A= > > T3 x;=0A= > > T1 y;=0A= > > (T2)x-(T2)((T1)x-y)=0A= > >=0A= > > can be safely replaced with=0A= > >=0A= > > (T2)y=0A= > >=0A= > > From the output, it looks like this is safe when T1 is at least as larg= e=0A= > > as T2. It is wrong when T1 is unsigned and smaller than T2. And when T1= is=0A= > > signed and smaller than T2, it is ok if T3 is the same type as T1 (sign= ed=0A= > > then) or has strictly less precision (any sign), and not in other cases= .=0A= > >=0A= > > Note that this is when signed implies undefined overflow and unsigned= =0A= > > implies wrapping, and I wouldn't put too much faith in this recently=0A= > > dusted program. And it doesn't say how to write the match.pd pattern wi= th=0A= > > '?', "@@", disabling it if TYPE_OVERFLOW_SANITIZED, etc.=0A= > >=0A= > > Mostly, I wanted to say that if we are going to go handle more than=0A= > > nop_convert for more than just 1 or 2 easy transformations, I think som= e=0A= > > kind of computer verification would be useful, it would save a lot of t= ime=0A= > > and headaches.=0A= >=0A= > True.=A0 I wonder if auto-generating such tests from match.pd rules would= =0A= > be a good project to work on (GSoC?).=A0 When there's define_match=0A= > involved things get a little tricky, but then one item on the TODO list= =0A= > is "inlining" those at the use site (exploding the decision tree even mor= e).=0A= >=0A= > Richard.=0A= >=0A= > > (I just check by brute force all possible precisions (from 1 to 6) and= =0A= > > signedness for T1, T2 and T3, all possible values for x and y, compute= =0A= > > the before and after formulas, accepting if there is UB before, rejecti= ng=0A= > > if there is UB after (and not before), and manually try to see a patter= n=0A= > > in the list of types that work)=0A= > >=0A= > > --=0A= > > Marc Glisse= --_002_CY4PR2101MB0801630BD910A329C791ACDCCCF39CY4PR2101MB0801_ Content-Type: application/octet-stream; name="pr95176-2.patch" Content-Description: pr95176-2.patch Content-Disposition: attachment; filename="pr95176-2.patch"; size=6019; creation-date="Fri, 06 Aug 2021 21:14:04 GMT"; modification-date="Fri, 06 Aug 2021 21:14:04 GMT" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL2djYy9tYXRjaC5wZCBiL2djYy9tYXRjaC5wZAppbmRleCAxOWY0YTc4MmFl OS4uMTA2ODk1YWE1NjggMTAwNjQ0Ci0tLSBhL2djYy9tYXRjaC5wZAorKysgYi9nY2MvbWF0Y2gu cGQKQEAgLTU5OSw2ICs1OTksMTIgQEAgREVGSU5FX0lOVF9BTkRfRkxPQVRfUk9VTkRfRk4gKFJJ TlQpCiAgKGlmIChJTlRFR1JBTF9UWVBFX1AgKHR5cGUpIHx8IFZFQ1RPUl9JTlRFR0VSX1RZUEVf UCAodHlwZSkpCiAgIChjb252ZXJ0ICh0cnVuY19tb2QgQDAgQDEpKSkpCiAKKy8qIFggKiAoWSAv IFgpIGlzIHRoZSBzYW1lIGFzIFkgLSAoWSAlIFgpLiAgKi8KKyhzaW1wbGlmeQorIChtdWx0OmMg KGNvbnZlcnQxPyBAMCkgKGNvbnZlcnQyPyAodHJ1bmNfZGl2IEAxIEBAMCkpKQorIChpZiAoSU5U RUdSQUxfVFlQRV9QICh0eXBlKSkKKyAgKG1pbnVzIChjb252ZXJ0IEAxKSAoY29udmVydCAodHJ1 bmNfbW9kIEAxIEAwKSkpKSkKKwogLyogT3B0aW1pemUgVFJVTkNfTU9EX0VYUFIgYnkgYSBwb3dl ciBvZiB0d28gaW50byBhIEJJVF9BTkRfRVhQUiwKICAgIGkuZS4gIlggJSBDIiBpbnRvICJYICYg KEMgLSAxKSIsIGlmIFggYW5kIEMgYXJlIHBvc2l0aXZlLgogICAgQWxzbyBvcHRpbWl6ZSBBICUg KEMgPDwgTikgIHdoZXJlIEMgaXMgYSBwb3dlciBvZiAyLApAQCAtMjM4OCw5ICsyMzk0LDI3IEBA IERFRklORV9JTlRfQU5EX0ZMT0FUX1JPVU5EX0ZOIChSSU5UKQogCSB8fCBUWVBFX09WRVJGTE9X X1dSQVBTICh0eXBlKSkKICAgICAgKG5lZ2F0ZSAodmlld19jb252ZXJ0IEAxKSkKICAgICAgKHZp ZXdfY29udmVydCAobmVnYXRlIEAxKSkpKQorCiAgIChzaW1wbGlmeQogICAgKG1pbnVzIEAwIChu b3BfY29udmVydDE/IChtaW51cyAobm9wX2NvbnZlcnQyPyBAMCkgQDEpKSkKICAgICh2aWV3X2Nv bnZlcnQgQDEpKQorCisgIC8qIFggLSAoWCAtIFkpIC0tPiBZICovCisgIChzaW1wbGlmeQorICAg IChtaW51cyAoY29udmVydDE/IEAwKSAoY29udmVydDI/IChtaW51c0AyIChjb252ZXJ0Mz8gQEAw KSBAMSkpKQorICAgIChpZiAoQU5ZX0lOVEVHUkFMX1RZUEVfUCAodHlwZSkKKyAgICAgICAgJiYg VFlQRV9PVkVSRkxPV19VTkRFRklORUQodHlwZSkKKyAgICAgICAgJiYgIVRZUEVfT1ZFUkZMT1df U0FOSVRJWkVEKHR5cGUpCisgICAgICAgICYmIEFOWV9JTlRFR1JBTF9UWVBFX1AgKFRSRUVfVFlQ RShAMikpCisgICAgICAgICYmIFRZUEVfT1ZFUkZMT1dfVU5ERUZJTkVEKFRSRUVfVFlQRShAMikp CisgICAgICAgICYmICFUWVBFX09WRVJGTE9XX1NBTklUSVpFRChUUkVFX1RZUEUoQDIpKQorICAg ICAgICAmJiBBTllfSU5URUdSQUxfVFlQRV9QIChUUkVFX1RZUEUoQDApKQorICAgICAgICAmJiBU WVBFX09WRVJGTE9XX1VOREVGSU5FRChUUkVFX1RZUEUoQDApKQorICAgICAgICAmJiAhVFlQRV9P VkVSRkxPV19TQU5JVElaRUQoVFJFRV9UWVBFKEAwKSkKKyAgICAgICAgJiYgVFlQRV9QUkVDSVNJ T04gKFRSRUVfVFlQRSAoQDIpKSA8PSBUWVBFX1BSRUNJU0lPTiAodHlwZSkKKyAgICAgICAgJiYg VFlQRV9QUkVDSVNJT04gKFRSRUVfVFlQRSAoQDApKSA8PSBUWVBFX1BSRUNJU0lPTiAodHlwZSkp CisgICAgKGNvbnZlcnQgQDEpKSkKKwogICAvKiAoQSArLSBCKSArIChDIC0gQSkgICAtPiBDICst IEIgKi8KICAgLyogKEEgKyAgQikgLSAoQSAtIEMpICAgLT4gQiArIEMgKi8KICAgLyogTW9yZSBj YXNlcyBhcmUgaGFuZGxlZCB3aXRoIGNvbXBhcmlzb25zLiAgKi8KZGlmZiAtLWdpdCBhL2djYy90 ZXN0c3VpdGUvZ2NjLmRnL3ByOTUxNzYtMi5jIGIvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHI5NTE3 Ni0yLmMKbmV3IGZpbGUgbW9kZSAxMDA2NDQKaW5kZXggMDAwMDAwMDAwMDAuLjAzZmVkNDEzMjQw Ci0tLSAvZGV2L251bGwKKysrIGIvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHI5NTE3Ni0yLmMKQEAg LTAsMCArMSw5MSBAQAorLyogeyBkZy1kbyBydW4gfSAqLworLyogeyBkZy1vcHRpb25zICItTyAt ZmR1bXAtdHJlZS1vcHRpbWl6ZWQtcmF3IiB9ICovCisKKy8qIFRlc3QgdGhlIFggLSAoWCAtIFkp IC0tPiBZIHRyYW5zZm9ybWF0aW9uICovCisKK2V4dGVybiBpbnQgcHJpbnRmIChfX2NvbnN0IGNo YXIgKl9fcmVzdHJpY3QgX19mb3JtYXQsIC4uLik7CisKK2ludCBfX2F0dHJpYnV0ZV9fICgobm9p bmxpbmUpKQorZihpbnQgYSwgaW50IGIpCit7CisgICAgcmV0dXJuIGEgLSAoYS1iKTsKK30KKwor aW50IF9fYXR0cmlidXRlX18oKG9wdGltaXplKCJPMCIpKSkgX19hdHRyaWJ1dGVfXyAoKG5vaW5s aW5lKSkKK2ZOb09wdCh2b2xhdGlsZSBpbnQgYSwgdm9sYXRpbGUgaW50IGIpCit7CisgICAgcmV0 dXJuIGEgLSAoYS1iKTsKK30KKworbG9uZyBfX2F0dHJpYnV0ZV9fICgobm9pbmxpbmUpKQorZjIo c2hvcnQgYSwgbG9uZyBiKQoreworCXJldHVybiBhIC0gKCgoaW50KSBhKS1iKTsKK30KKworbG9u ZyBfX2F0dHJpYnV0ZV9fKChvcHRpbWl6ZSgiTzAiKSkpIF9fYXR0cmlidXRlX18gKChub2lubGlu ZSkpCitmMk5vT3B0KHZvbGF0aWxlIHNob3J0IGEsIHZvbGF0aWxlIGxvbmcgYikKK3sKKyAgICBy ZXR1cm4gYSAtICgoKGludCkgYSktYik7Cit9CisKK2xvbmcgX19hdHRyaWJ1dGVfXyAoKG5vaW5s aW5lKSkKK2YzKHNob3J0IGEsIGxvbmcgYikKK3sKKyAgICByZXR1cm4gYSAtIChhLWIpOworfQor Citsb25nIF9fYXR0cmlidXRlX18oKG9wdGltaXplKCJPMCIpKSkgX19hdHRyaWJ1dGVfXyAoKG5v aW5saW5lKSkKK2YzTm9PcHQodm9sYXRpbGUgc2hvcnQgYSwgdm9sYXRpbGUgbG9uZyBiKQorewor ICAgIHJldHVybiBhIC0gKGEtYik7Cit9CisKK2xvbmcgbG9uZyBfX2F0dHJpYnV0ZV9fICgobm9p bmxpbmUpKQorZjQobG9uZyBiKQoreworICAgIHJldHVybiAoKHNob3J0KTQwTCkgLSAoKChpbnQp NDApLWIpOworfQorCitsb25nIF9fYXR0cmlidXRlX18oKG9wdGltaXplKCJPMCIpKSkgX19hdHRy aWJ1dGVfXyAoKG5vaW5saW5lKSkKK2Y0Tm9PcHQodm9sYXRpbGUgbG9uZyBiKQoreworICAgIHJl dHVybiAoKHNob3J0KTQwTCkgLSAoKChpbnQpNDApLWIpOworfQorCitsb25nIF9fYXR0cmlidXRl X18gKChub2lubGluZSkpCitmTmVnKGxvbmcgYSwgbG9uZyBiKQoreworCXJldHVybiBhIC0gKCgo c2hvcnQpIGEpLWIpOworfQorCitsb25nIGxvbmcgX19hdHRyaWJ1dGVfXyAoKG5vaW5saW5lKSkK K2ZOZWcyKGxvbmcgbG9uZyB2LCBsb25nIGIpCit7CisgICAgcmV0dXJuICgoaW50KXYpIC0gKCgo c2hvcnQpdiktYik7Cit9CisKK2xvbmcgX19hdHRyaWJ1dGVfXyAoKG5vaW5saW5lKSkKK2ZOZWcz KHNob3J0IGEsIGxvbmcgYikKK3sKKwlyZXR1cm4gYSAtICgoKHVuc2lnbmVkIGludCkgYSktYik7 Cit9CisKK2ludCBtYWluKCkKK3sKKyAgICBpZiAoZigyLCAxNSkgIT0gZk5vT3B0KDIsIDE1KSkK KyAgICAgICAgX19idWlsdGluX2Fib3J0KCk7CisgICAgaWYgKGYyKDIsIDE1KSAhPSBmMk5vT3B0 KDIsIDE1KSkKKyAgICAgICAgX19idWlsdGluX2Fib3J0KCk7CisgICAgaWYgKGYzKDIsIDE1KSAh PSBmM05vT3B0KDIsIDE1KSkKKyAgICAgICAgX19idWlsdGluX2Fib3J0KCk7CisgICAgaWYgKGY0 KDE1KSAhPSBmNE5vT3B0KDE1KSkKKyAgICAgICAgX19idWlsdGluX2Fib3J0KCk7CisgICAgcHJp bnRmKCJwYXNzIik7Cit9CisKKy8vIFRoZXJlIHNob3VsZCBiZSAxNCBpbnN0YW5jZXMgb2YgbWlu dXNfZXhwciBpbiB0aGUgb3V0cHV0OgorLy8gVHdvIGZvciBlYWNoIE5vT3B0KiBmdW5jdGlvbgor Ly8gVHdvIGZvciBlYWNoIGZOZWcqIGZ1bmN0aW9uCisvKiB7IGRnLWZpbmFsIHsgc2Nhbi10cmVl LWR1bXAtdGltZXMgIm1pbnVzX2V4cHIiIDEyICJvcHRpbWl6ZWQiIH0gfSAqLworLyogeyBkZy1v dXRwdXQgInBhc3MiIH0gKi8KZGlmZiAtLWdpdCBhL2djYy90ZXN0c3VpdGUvZ2NjLmRnL3ByOTUx NzYuYyBiL2djYy90ZXN0c3VpdGUvZ2NjLmRnL3ByOTUxNzYuYwpuZXcgZmlsZSBtb2RlIDEwMDY0 NAppbmRleCAwMDAwMDAwMDAwMC4uZWYwODczMTcxODcKLS0tIC9kZXYvbnVsbAorKysgYi9nY2Mv dGVzdHN1aXRlL2djYy5kZy9wcjk1MTc2LmMKQEAgLTAsMCArMSw0NSBAQAorLyogeyBkZy1kbyBy dW4gfSAqLworLyogeyBkZy1vcHRpb25zICItTyAtZmR1bXAtdHJlZS1vcHRpbWl6ZWQtcmF3IiB9 ICovCisKK2V4dGVybiBpbnQgcHJpbnRmIChfX2NvbnN0IGNoYXIgKl9fcmVzdHJpY3QgX19mb3Jt YXQsIC4uLik7CisKK2ludCBfX2F0dHJpYnV0ZV9fICgobm9pbmxpbmUpKQorZihpbnQgYSwgaW50 IGIpCit7CisgICAgcmV0dXJuIGEgKiAoYiAvIGEpOworfQorCitpbnQgX19hdHRyaWJ1dGVfXygo b3B0aW1pemUoIk8wIikpKSBfX2F0dHJpYnV0ZV9fICgobm9pbmxpbmUpKQorZk5vT3B0KGludCBh LCBpbnQgYikKK3sKKyAgICByZXR1cm4gYSAqIChiIC8gYSk7Cit9CisKK2ludCBfX2F0dHJpYnV0 ZV9fICgobm9pbmxpbmUpKQorZjIoaW50IGEsIGludCBiKQoreworICAgIHJldHVybiAoYiAvIGEp ICogYTsKK30KKworaW50IF9fYXR0cmlidXRlX18oKG9wdGltaXplKCJPMCIpKSkgX19hdHRyaWJ1 dGVfXyAoKG5vaW5saW5lKSkKK2YyTm9PcHQoaW50IGEsIGludCBiKQoreworICAgIHJldHVybiAo YiAvIGEpICogYTsKK30KKworaW50IG1haW4oKQoreworICAgIGlmIChmKDIsIDE1KSAhPSBmTm9P cHQoMiwgMTUpKQorICAgICAgICBfX2J1aWx0aW5fYWJvcnQoKTsKKyAgICBpZiAoZjIoMiwgMTUp ICE9IGYyTm9PcHQoMiwgMTUpKQorICAgICAgICBfX2J1aWx0aW5fYWJvcnQoKTsKKyAgICBwcmlu dGYoInBhc3MiKTsKK30KKworLy8gVGhlcmUgc2hvdWxkIGJlIHR3byBpbnN0YW5jZXMgb2YgdHJ1 bmNfZGl2X2V4cHIgYW5kIAorLy8gbXVsdF9leHByIGluIHRoZSBvdXRwdXQuIE9uZSBpbiBmTm9P cHQgYW5kIG9uZSBpbiBmMk5vT3B0LgorLyogeyBkZy1maW5hbCB7IHNjYW4tdHJlZS1kdW1wLXRp bWVzICJ0cnVuY19kaXZfZXhwciIgMiAib3B0aW1pemVkIiB9IH0gKi8KKy8qIHsgZGctZmluYWwg eyBzY2FuLXRyZWUtZHVtcC10aW1lcyAibXVsdF9leHByIiAyICJvcHRpbWl6ZWQiIH0gfSAqLwor LyogeyBkZy1maW5hbCB7IHNjYW4tdHJlZS1kdW1wLXRpbWVzICJ0cnVuY19tb2RfZXhwciIgMiAi b3B0aW1pemVkIiB9IH0gKi8KKy8qIHsgZGctZmluYWwgeyBzY2FuLXRyZWUtZHVtcC10aW1lcyAi bWludXNfZXhwciIgMiAib3B0aW1pemVkIiB9IH0gKi8KKy8qIHsgZGctb3V0cHV0ICJwYXNzIiB9 ICovCmRpZmYgLS1naXQgYS9nY2MvdGVzdHN1aXRlL2djYy5kZy90cmVlLXNzYS8yMDAzMDgwNy0x MC5jIGIvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvdHJlZS1zc2EvMjAwMzA4MDctMTAuYwppbmRleCAw ZTAxZTUxMWI3OC4uNGNkMzU3MzgwNTcgMTAwNjQ0Ci0tLSBhL2djYy90ZXN0c3VpdGUvZ2NjLmRn L3RyZWUtc3NhLzIwMDMwODA3LTEwLmMKKysrIGIvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvdHJlZS1z c2EvMjAwMzA4MDctMTAuYwpAQCAtMjAsNiArMjAsOSBAQCBzdWJyZWdfaGlnaHBhcnRfb2Zmc2V0 IChvdXRlcm1vZGUsIGlubmVybW9kZSkKIC8qIFRoZXJlIHNob3VsZCBiZSBvbmUgbWFzayB3aXRo IHRoZSB2YWx1ZSAzLiAgKi8KIC8qIHsgZGctZmluYWwgeyBzY2FuLXRyZWUtZHVtcC10aW1lcyAi IFwmIDMiIDEgInZycDEifSB9ICovCiAgIAotLyogVGhlcmUgc2hvdWxkIGJlIG9uZSByaWdodCBz aGlmdCBieSAyIHBsYWNlcy4gICovCi0vKiB7IGRnLWZpbmFsIHsgc2Nhbi10cmVlLWR1bXAtdGlt ZXMgIiA+PiAyIiAxICJ2cnAxIn0gfSAqLworLyogVGhlcmUgc2hvdWxkIGJlIG5vIHJpZ2h0IHNo aWZ0IGJ5IDIgcGxhY2VzLiAgKi8KKy8qIHsgZGctZmluYWwgeyBzY2FuLXRyZWUtZHVtcC10aW1l cyAiID4+IDIiIDAgInZycDEifSB9ICovCisKKy8qIFRoZSAiZGlmZmVyZW5jZSAvIDQgKiA0IiBz aG91bGQgYmVjb21lIGEgc3VidHJhY3Rpb24gKi8KKy8qIHsgZGctZmluYWwgeyBzY2FuLXRyZWUt ZHVtcC10aW1lcyAiIC0gIiAyICJ2cnAxIn0gfSAqLwogCg== --_002_CY4PR2101MB0801630BD910A329C791ACDCCCF39CY4PR2101MB0801_--