From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from NAM10-DM6-obe.outbound.protection.outlook.com (mail-dm6nam10on2130.outbound.protection.outlook.com [40.107.93.130]) by sourceware.org (Postfix) with ESMTPS id 84E5C3854812 for ; Wed, 2 Jun 2021 20:55:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 84E5C3854812 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Ki0f2Vf3yBFV3rjjE/FU2sfa6IFlshbSjRHtOoI6UJ6G9dtGlf41DiSpTkfek7o1cZy3jVKG2Avlll4Tt2SKK99A/tp4NEoXAEbwJKEexnIath4kNxnzSGbN2Vm9Oj57c7heAZgzcoPM89WKhhmHJkSY6R6KXUrkc4ahLcaLAFyde2V2sAomwxqVqobI2JITakKu+aY6jrao5BYm3LfmP18BzsCE3cb6dRLM86FU9eRQdPcl0Ou8oaD5ldboBp27InznSY3Hep4MXN/51fJXAtD8q9Z8ssRg4mLWRIwQ726bD3J5AhkYsF9e2TU2mzeEU7Waw3sYSMZyJhCzO84uGw== 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=p6wvwJC30F1eifEF6jXTAK8U5EtQ8AOVxd94qBS8VLc=; b=hcrge58BM24nBx94IgQEaE1DysuNzzmfsPHjmxbEF4kkYEW8ETBaZbYZPfP5vQF+L4RDAYbpyNeZjtOsl97igjqlAIhOCA3aG1XWI7m6FneED3HBTHLBw5xB0GZw6HmrjBS17noHj09ewUm2WQXf1KiUkTl90M7LR3y1+Uq9nowpWIwI+6D9nHh2LkBS4U48y9LKaOh3el7MLdFyJCszybtqahlUCs66cJKWnJhFiShPpOJP0QsxN8xM4/W0efC8kCNHSX2t+oFQIGxaHKFPj8836i6aHtxPiCpgkEZSonQQA8/90HtwmxLwNLXYKozBJF0/8yJBSqBGMjTfjjz7yQ== 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 MWHPR2101MB0811.namprd21.prod.outlook.com (2603:10b6:301:7b::39) by MWHPR21MB0512.namprd21.prod.outlook.com (2603:10b6:300:df::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4219.3; Wed, 2 Jun 2021 20:55:13 +0000 Received: from MWHPR2101MB0811.namprd21.prod.outlook.com ([fe80::94d:2b94:ee7d:bb53]) by MWHPR2101MB0811.namprd21.prod.outlook.com ([fe80::94d:2b94:ee7d:bb53%9]) with mapi id 15.20.4219.007; Wed, 2 Jun 2021 20:55:13 +0000 From: Victor Tong To: Richard Biener CC: "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: AQHXJoDrR4fklL4IYku64pH3Fv0p3qrIMcqAgDljMP8= Date: Wed, 2 Jun 2021 20:55:13 +0000 Message-ID: References: , In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: 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-06-02T20:55:12.762Z; 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-originating-ip: [73.83.15.195] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: d17aa071-f515-4fa4-8278-08d92608b7b7 x-ms-traffictypediagnostic: MWHPR21MB0512: x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:9508; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: 1EZ+Nt+yRcI3YvFOrtoyX9ByDIA6TJ7YEzobyD/2bvko3C3/JPOO/s/LXq2cdZQmojl4T4vgaeNePuOJ33+yyhkeXuxBkfgtHgmhUH/oslgHNioqoAlRze9BtN3Ex6JfJjFP97oIVKPUTzGJBUPT3YkxAZ5njNe9nx3RS+zlidYxZIWJk/hvhRKipCdYAv8M5T0k0RnRdrygN9pKi0eu3VBbd7GmQWWfW01Ro+INTkJHy0tx2sGTzKNdQomYPGyFdzddG0sRjIaA69hTz2znB8/4qM3bhMa1vOhc7kajTdfII/u1gUlkIhLJz22tbQc2BOGYMLlvg7G8CT13QC0xXVKbnIhyaC/x/IdWhhKHKAjUGLpROQW0eHuo3YRtJAKFy/j4Qnxr/8KerCR69p++znvDQVOFbTHN/fI4kGnPGCD6jDNH2xHV615yKztBHybayk/E+8pafl/WNTzUlw9UJPxPWKwtlHn8CM5kC7HCZzQZaCpyy7pwhbwEDRLo9c/QasYUfq+HCrUYv/XD/KdBB7zTai/m9T6GBazBQLGM7Oc9rc4nGBb6mdBQTO9Z3W4DJlMXq1vhab/z3jhX2RLrk8v6aO43AsVE80eUgeWEs4VfPymWI2aoaA0uHUmx03Yj4cC5lSHl1q9oL50b4EKKOg== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:MWHPR2101MB0811.namprd21.prod.outlook.com; PTR:; CAT:NONE; SFS:(4636009)(366004)(9686003)(8990500004)(76116006)(52536014)(498600001)(122000001)(66946007)(71200400001)(6916009)(38100700002)(5660300002)(7696005)(6506007)(53546011)(33656002)(64756008)(26005)(86362001)(10290500003)(82960400001)(82950400001)(8676002)(66476007)(8936002)(186003)(4326008)(66556008)(55016002)(66446008)(2906002)(83380400001); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 2 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?6Ymgonk1rMF/I1j7XlAXzX3Ezd3DAGx9LT8/dNuZ86t+9Dz5Rf10BKhZAg?= =?iso-8859-1?Q?31oPhmr77ILM7wkBEpDAZbKnhZ7t3tcUA/mrDVRZCt8qD+Eyd2f7ijeG5d?= =?iso-8859-1?Q?Kr+I9xK3rOPG6uXvP5QlEziGg1wYm0gCvCsmvabUXQ9czM2CwAospRl0g3?= =?iso-8859-1?Q?b1qkfJXz1l2UNmdL3RaWXVK9vL+YDAWiswH7IqRYxfJNePDRqrg3I2fd1r?= =?iso-8859-1?Q?wkQe9UivylH3cHF8p3DpgLzl7mXBPdE+05jBx9Iv51mEdNiiq0NYS+SOuD?= =?iso-8859-1?Q?G2MEPgTIyId8edWcpYGLW+VcEEe+sxpH/3vk83R/MsyzlbcsCPirHSHCWu?= =?iso-8859-1?Q?PQwOrQx/giuv8TqGDQoShu3mywCO2AejSxXjAvX7LT2M5fhEl7Wu8B16un?= =?iso-8859-1?Q?CzHPREieC4OAKxgpW85paPmUEAeyex9d8xsQ7bT3lYZn0Mv3h/DICDA/o+?= =?iso-8859-1?Q?O6wkW9UtSJkIBV13ACZt3Z/SySCQOWZI4t8WxD6LoPUOQB5JAn0krXxt64?= =?iso-8859-1?Q?TFUCYbdtLTsn05K28J7f4JxVzTYhiilf7HiVVob9F1xKYLTssTjbdlauL/?= =?iso-8859-1?Q?1iTY/eaFaGP2tUTQlFsEvOkdx2LLkdmk+JQoKCwmdoM0sxWnBEaeT4+NFh?= =?iso-8859-1?Q?WJKHzMx0FH8dGc+95XvEvQ6PB8VsphifTHVcKTnpHDpcFHLhm7rnYvUYy+?= =?iso-8859-1?Q?Z0FOefwP/GMtzZf9Ak8CzCLrRy+nBtwvjJKD0/+n7pX9Y3xqdFqHd7J2Of?= =?iso-8859-1?Q?hJNtXbD3HLD4hQtpwkxa2R9wNVvqy6RGQW95YnY+rEY2KFw98t4isCYwK9?= =?iso-8859-1?Q?uqJchAtiadWyaYA/zLeesPcnz24PUJ5YZvZ+OLKUC66LmipkyyFjxTofYP?= =?iso-8859-1?Q?6iCUG8ZlzsbnqW2fhH7yrkWSuo4zGqrT+kxY8vA5mYHKxR4ktpImsgz+cR?= =?iso-8859-1?Q?9Pyagj/judusV3rA8yD0UQjjpOUmdmiNMXcQYDKUMMWbyXdUaeqqiEVDYJ?= =?iso-8859-1?Q?eOfCmMUSC1sVk5?= x-ms-exchange-antispam-messagedata-1: P2qQquEIADk+huun3s0Wv5bAt2rGodFVvwMnKcWbXkjY33Z9v/1D0HjE7qwT9i6EZ6OG4fU6RGaXnPj1SaMJwwef+NT2mt4CHQq0KrjJO4WWV5NODMi2x0bwrb14iO2fLFEJ8rz8I+V/kePrt9uSUAtp0l8fk3751P93tIYzW8nbc4lz9AHstYeoL/9YW/uv//zjaOWnnuZi9lPSzeRFVD2KhJz1Rxp/5k8PeSgzfWOH4Z3PMyw0RQXa0N6hGa6mqejN9rVlMImD4b2/4aE5ASnEMKkMKd3PmYLHttQXeyFhYCV1i+Oi74Cut7jobg84K48= x-ms-exchange-transport-forked: True Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: MWHPR2101MB0811.namprd21.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: d17aa071-f515-4fa4-8278-08d92608b7b7 X-MS-Exchange-CrossTenant-originalarrivaltime: 02 Jun 2021 20:55:13.2697 (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: eHShr5WcdtA39yLAYnermYulXZyElSHLUT8rtSyRFRA1pJeufk0h4Xx4zhheJik5nUHe3giDvH0B9cijZZmHPQ== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR21MB0512 X-Spam-Status: No, score=-1.1 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, 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: Wed, 02 Jun 2021 20:55:17 -0000 Hi Richard,=0A= =0A= Thanks for reviewing my patch. I did a search online and you're right -- th= ere isn't a vector modulo instruction. I'll remove the X * (Y / X) --> Y - = (Y % X) pattern and the existing X - (X / Y) * Y --> X % Y from triggering = on vector types.=0A= =0A= I looked into why the following pattern isn't triggering:=0A= =0A= =A0 (simplify=0A= =A0 =A0(minus @0 (nop_convert1? (minus (nop_convert2? @0) @1)))=0A= =A0 =A0(view_convert @1))=0A= =0A= The nop_converts expand into tree_nop_conversion_p checks. In fn2() of the = testsuite/gcc.dg/fold-minus-6.c, the expression during generic matching loo= ks like: =0A= =0A= 42 - (long int) (42 - 42 % x)=0A= =0A= When looking at the right-hand side of the expression (the (long int) (42 -= 42 % x)), the tree_nop_conversion_p check fails because of the type precis= ion difference. The expression inside of the cast has a 32-bit precision an= d the outer expression has a 64-bit precision.=0A= =0A= I looked around at other patterns and it seems like nop_convert and view_co= nvert are used because of underflow/overflow concerns. I'm not familiar wit= h the two constructs. What's the difference between using them and checking= TYPE_OVERFLOW_UNDEFINED? In the scenario above, since TYPE_OVERFLOW_UNDEFI= NED is true, the second pattern that I added (X - (X - Y) --> Y) gets trigg= ered.=0A= =0A= Thanks,=0A= Victor=0A= =0A= =0A= From: Richard Biener =0A= Sent: Tuesday, April 27, 2021 1:29 AM=0A= To: Victor Tong =0A= Cc: gcc-patches@gcc.gnu.org =0A= Subject: [EXTERNAL] Re: [PATCH] tree-optimization: Optimize division follow= ed by multiply [PR95176] =0A= =A0=0A= On Thu, Apr 1, 2021 at 1:03 AM Victor Tong via Gcc-patches=0A= wrote:=0A= >=0A= > Hello,=0A= >=0A= > This patch fixes PR tree-optimization/95176. A new pattern in match.pd wa= s added to transform "a * (b / a)" --> "b - (b % a)". A new test case was a= lso added to cover this scenario.=0A= >=0A= > The new pattern interfered with the existing pattern of "X - (X / Y) * Y"= . In some cases (such as in fn4() in gcc/testsuite/gcc.dg/fold-minus-6.c), = the new pattern is applied causing the existing pattern to no longer apply.= This results in worse code generation because the expression is left as "X= - (X - Y)". An additional subtraction pattern of "X - (X - Y) --> Y" was a= dded to this patch to avoid this regression.=0A= >=0A= > I also didn't remove the existing pattern because it triggered in more ca= ses than the new pattern because of a tree_invariant_p check that's inserte= d by genmatch for the new pattern.=0A= =0A= Yes, we do not handle using Y multiple times when it might contain=0A= side-effects in GENERIC folding=0A= (comments in genmatch suggest we can use save_expr but we don't=0A= implement this [anymore]).=0A= =0A= On GIMPLE there's also the issue that your new pattern creates a=0A= complex expression which=0A= makes it failed to be used by value-numbering for example where the=0A= old pattern was OK=0A= (eventually, if no conversion was required).=0A= =0A= So indeed it looks OK to preserve both.=0A= =0A= I wonder why you needed the=0A= =0A= +/* X - (X - Y) --> Y */=0A= +(simplify=0A= + (minus (convert1? @0) (convert2? (minus @@0 @1)))=0A= + (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type)) &&=0A= TYPE_OVERFLOW_UNDEFINED(type))=0A= +=A0 (convert @1)))=0A= =0A= pattern since it should be handled by=0A= =0A= =A0 /* Match patterns that allow contracting a plus-minus pair=0A= =A0=A0=A0=A0 irrespective of overflow issues.=A0 */=0A= =A0 /* (A +- B) - A=A0=A0=A0=A0=A0=A0 ->=A0 +- B */=0A= =A0 /* (A +- B) -+ B=A0=A0=A0=A0=A0 ->=A0 A */=0A= =A0 /* A - (A +- B)=A0=A0=A0=A0=A0=A0 -> -+ B */=0A= =A0 /* A +- (B -+ A)=A0=A0=A0=A0=A0 ->=A0 +- B */=0A= =0A= in particular=0A= =0A= =A0 (simplify=0A= =A0=A0 (minus @0 (nop_convert1? (minus (nop_convert2? @0) @1)))=0A= =A0=A0 (view_convert @1))=0A= =0A= if there's supported cases missing I'd rather extend this pattern than=0A= replicating it.=0A= =0A= +/* X * (Y / X) is the same as Y - (Y % X).=A0 */=0A= +(simplify=0A= + (mult:c (convert1? @0) (convert2? (trunc_div @1 @@0)))=0A= + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))=0A= +=A0 (minus (convert @1) (convert (trunc_mod @1 @0)))))=0A= =0A= note that if you're allowing vector types you have to use=0A= (view_convert ...) in the=0A= transform and you also need to make sure that the target can expand=0A= the modulo - I suspect that's an issue with the existing pattern as well.= =0A= I don't know of any vector ISA that supports modulo (or integer=0A= division, that is).=0A= Restricting the patterns to integer types is probably the most=0A= sensible solution.=0A= =0A= Thanks,=0A= Richard.=0A= =0A= > I verified that all "make -k check" tests pass when targeting x86_64-pc-l= inux-gnu.=0A= >=0A= > 2021-03-31=A0 Victor Tong=A0 =0A= >=0A= > gcc/ChangeLog:=0A= >=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 * match.pd: Two new patterns: One to optimize div= ision followed by multiply and the other to avoid a regression as explained= above=0A= >=0A= > gcc/testsuite/ChangeLog:=0A= >=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 * gcc.dg/tree-ssa/20030807-10.c: Update existing = test to look for a subtraction because a shift is no longer emitted=0A= >=A0=A0=A0=A0=A0=A0=A0=A0 * gcc.dg/pr95176.c: New test to cover optimizing = division followed by multiply=0A= >=0A= > I don't have write access to the GCC repo but I've completed the FSF pape= rwork as I plan to make more contributions in the future. I'm looking for a= sponsorship from an existing GCC maintainer before applying for write acce= ss.=0A= >=0A= > Thanks,=0A= > Victor=