From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from na01-obe.outbound.protection.outlook.com (mail-cusazlp17010004.outbound.protection.outlook.com [40.93.13.4]) by sourceware.org (Postfix) with ESMTPS id 895193858419 for ; Tue, 30 Nov 2021 23:41:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 895193858419 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Bq7ZGknCE3Y7f0/t8JfrVKNF2SUA4mjcrIr3fYbcAEPds335fm06FolivHZ98UMRRjIBrBHgKPXhTMCnZPNwJCfiJNYOmtYa2CKN8NRLDPOF/f3W2YZck2fPD+xGb08N6HIO3NF7u7hXmqqWCZgplhA0PnU2byT3K03grCrLUQG/7nREWqKjEQrPy8FNCGqJr2dzx5v9NkZbL41gj/qVGWB6e/1fs9q5uqMYdRglgfK9DYuhCYOwgHgWrbtcZCyczFPgSm0zp4PFfohg7tfCkGFlJyV4IBOjxQh9S8QvnChOtrYIPkOqglZ1Nv+GoLi4uou59cP6e9U7omrCx3BGDA== 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-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=KJaEesKQcsJrBYTK33wlPMgWC0LqAOclIO+xRvmcfOE=; b=ZCxoO9Rh7vn5lfw7eDkYpJmcl852LUMaxUtjfb3bJTv3nHY40H01rJNGQqJB+H45k9xv1ZQY+oDGhQtAll7eu8mqZ7+CCXboQdzrl9NHkh8iM5ghLtd32vtGrU7RdcSOihUQwxntzzbT/4bZASrC4b7Vw/s5OqgirOVRvmvF++mV0vDuJlg3AspvJnfcJFZiaE/FuPCHvkFs9Mv2fJ33HpzTh2pVtk1e868yAOvcdPoiqakE/a02EKL83LI4hZ3Al7Thp8sn69OSHwJCFuHFqeSLtra6OjSHFjRoIR0V1nKroAqPOylHDwzX8SdRPuWkWvvNy7lmzd+jl10hJRSlUA== 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 BN6PR21MB0162.namprd21.prod.outlook.com (2603:10b6:404:94::8) by BN8PR21MB1169.namprd21.prod.outlook.com (2603:10b6:408:74::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4734.5; Tue, 30 Nov 2021 23:41:14 +0000 Received: from BN6PR21MB0162.namprd21.prod.outlook.com ([fe80::c5fd:4e4:96cc:b150]) by BN6PR21MB0162.namprd21.prod.outlook.com ([fe80::c5fd:4e4:96cc:b150%11]) with mapi id 15.20.4778.001; Tue, 30 Nov 2021 23:41:14 +0000 From: Navid Rahimi To: Andrew Pinski CC: Navid Rahimi via Gcc-patches Subject: Re: [EXTERNAL] Re: [PATCH] tree-optimization/98956 Optimizing out boolean left shift Thread-Topic: [EXTERNAL] Re: [PATCH] tree-optimization/98956 Optimizing out boolean left shift Thread-Index: AQHX5b3deGA957tQL0666jm+hsv6aKwcoMAAgAALeQ2AAAmVgIAAAcEI Date: Tue, 30 Nov 2021 23:41:14 +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-11-30T23:41:13.303Z; 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: 9c3ce84d-4317-4cbc-5f7e-08d9b45ae5d1 x-ms-traffictypediagnostic: BN8PR21MB1169:EE_ x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:9508; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: 2ifHvOEtKNR5HsCxkcLEORF07xYQFN8KTm07VO+uW4WvqAayCugubO3LsdC1Yox7LbnjRGLCrFIvytjGocWAR/6Bik1oX1ZZCCgNtbadfG7pHJAgueba5T5eVbSPH5mkvOfbniZo/bI19fw6TOKjo26Z293LXbUq+hKKfuIOWv93OIqE0zJ81pIq99sw/5/ue+TC/yb71JFk9F20b7LwUzzLGC0sc42fY9QZsYgUmav/kRIr88Z5270yafVmztXNXS3YOjMW5e5WsTyRDK7FcYBDjtXgWskEaaXG5ttVRrTgMG0YAVMvR/kdnCud8idJmJtDVLHcYLqdvhA8Qy048lzuOaAI6qiU6vcV26JBZ6UrZ66Ejb1SWg8CtOiXGQSdpRE+esaIEPD3ckr7sTWYWxrRkw/45l/Rw2770AH8a3BiBxYyTghOq50iMiadJNLbE8Opxy38+6R/7DW05YwOZ54pUF0HnBG1XmgDja3iMmesQ0CmnYa9b6Cg3+mpyTkmayl3ps4fknZFozPCLJobK85Wisvnw4Qt1XzyoXGVAq7r9YffW/nFjyKwDf19XOjWJupcNq4WQEd3LorZlpDD0khfI+ptOtMktcNktgHhIe4xqVGgJQ642DicbmMkUVstTxayXx1jJcQ4DheRXjZhBJ/wn40XDY5aOgzYZg/wGBqDkdAFBY3cScE0TaMDZm+iJCg4hcqRrUBOsL6uSIVVQ5225rzD22Ytxwvh0IkEs+w+qAXXuMihMPohPV8OHuUALlezTliS3kbLGgfjG32W+FtGGpvEEEbywB24TYuWiee5knSAGyuQVA7cDsB/LZxv3TcYPeRjFcapVJBUXQwBSQ== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:BN6PR21MB0162.namprd21.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(83380400001)(6506007)(53546011)(966005)(71200400001)(10290500003)(7696005)(508600001)(38070700005)(186003)(9686003)(55016003)(84970400001)(5660300002)(38100700002)(2906002)(122000001)(66476007)(82960400001)(86362001)(8990500004)(33656002)(6916009)(91956017)(76116006)(316002)(66556008)(66946007)(82950400001)(52536014)(64756008)(66446008)(4326008)(8936002)(8676002)(20210929001); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?ukpww5MlqIyScJTZTS2bSF/IJ+fTUdPX3Aex29kO++oBpap/ZBDyafHy+RuH?= =?us-ascii?Q?xxuAXMsdTr4Wl6A4AxZkjusqo43CvbGcQNqkQ39vaD5czf0f+GPx5pjgTVKw?= =?us-ascii?Q?gtD+YSPVmnslFYDHARj5nQEHfRD3sLwtRI8Nb4A30dNedLGGfv2wRkVGlhph?= =?us-ascii?Q?mpFmm9sHF929oBW9cVZG+JNer4oB7kKTl0mx3rRPHcO9m18r34VznJtLqpRQ?= =?us-ascii?Q?kJmOsKk6GWtVvj5i0khxF1la90sdQeyjIhoEnYSDsQurAdexE5L4tTg72xj1?= =?us-ascii?Q?uzIEFKz5tdP9unJWzASZzrbWt9S9Jjr2nLtjWYwjkwa39uQclbJFAjukcbBU?= =?us-ascii?Q?xHBOq4upoIgWHxEM8gCRxZ4r4haPwGmbxLWG2GUefOiKYDsNInzR9Kzdb9ZL?= =?us-ascii?Q?xrPpE6RjUSUpY7cxLR9ZdCclBBJZoTHWXK29sbWXT1VzmBIeDANSuSN1/9lm?= =?us-ascii?Q?/S+548pb/NkfdnQwrOQ2xhKHBKiiUL1TmvPPKfMvAE7umFAkAmMKhabakO8T?= =?us-ascii?Q?jKJiwzT9F5LfpTRdWfgeb72lPuzF/CoycMBNsThYaYK84daHulczzJ3naOtX?= =?us-ascii?Q?zSf8tJLx+NG3x02qMYyraskego9Gr0KTsKYbvPsULrD17Ea06jGaJ3FQdDcv?= =?us-ascii?Q?TzOMcVtK0M+HBumABuFvZRR1/Pm81ciUig2WzlDiav/yfwbzGaITIf69+o9Z?= =?us-ascii?Q?o2Yi40GCWCrKlVR306ix4+AemgsmZ4F1KCnYFVJ+NnkBlbxdSNr4efduGZG8?= =?us-ascii?Q?rQHRItecSepEvxLofUJo16uZZQFjUWi19jQDh4Ae1o7vgkMVheTYaGGSMzBh?= =?us-ascii?Q?bIO2Kt6hZ3/5gyyktJoR3P+fxUTJVF2qL+STEAJMB9fEKoxQctvVDlx6q3kL?= =?us-ascii?Q?MHi4Bxj3weeydeF2c9WAM1BeE7T3xtQ/jKZH5HZRYSPqWxD5Mf6X9yHXGhM3?= =?us-ascii?Q?D4JSy0oG/kqtm76oIKV/Vf+O92ntZ+vD/w2CgLvqq8Yl0eTCdz6ZDSPEUipx?= =?us-ascii?Q?kY57KrA9tgS16q+QxVKG+Z4uo89pDjOtJxqQhZhCrqqVL6D/ChzCyv4eg1Bf?= =?us-ascii?Q?N8nABlcGs7g271AVgHGS63KWHh948/G6b0qcmSIhwWe72hmfniy7DNPF7Uf2?= =?us-ascii?Q?WSxJiRd3ZY4JeICtpoFiqa2hcSiCJkixgsw1FEndugEy/ywJhgnurDKV90OQ?= =?us-ascii?Q?6TSOZNL7UysrsbGNiy/rGX5a6EjHBkthx7gsXMkkQc0NF0vvzSkrmHkKAESM?= =?us-ascii?Q?V2la8hfoZKpd1kNZTuCrnmSO1mjW26IQf0S+qRcZUtETmQn1jSfHj0nfNBzf?= =?us-ascii?Q?mpxBRdkr4KHA3R0XbQC+w9TSSQLvP09ynvhixMJEnCzZnHI36cN2gVPk1DJM?= =?us-ascii?Q?7lhnXsWwoWGEOIvJ58uNMLEBYW9uhL9pcSMrTUBQPODhC+e88aF+4Duzt3ER?= =?us-ascii?Q?3VSGQ9r7+cymBxMAFWoFnVaiewxDF1Mjuf6e7H/zQsYidWdpaz4KbKn7Cgqd?= =?us-ascii?Q?CpZfsEXW/j8+gOmSznEp7TgrEO07JdBKtGi6JMF//tC/bJ8Nd4nL6ytMMoqF?= =?us-ascii?Q?UpfuJi0Q5Yk5bLKOBrED53cuZw3Jz2MIV6IPNXwy778hUI9J63FI51N1VCmu?= =?us-ascii?Q?VRkdez08AR94NETadNjcYTusOnTw1xRZ7yeWUdj0ZJaZ?= Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: BN6PR21MB0162.namprd21.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 9c3ce84d-4317-4cbc-5f7e-08d9b45ae5d1 X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Nov 2021 23:41:14.3606 (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: FIVRpqRBvbm/hG7nW48bSLGfhOS1JezPapZnBBItwWBBInJDB+pAjtD1yArdmgnsfAWe/yXQrvwunSdNcCUMSFE/UwHZbxgqLwedzMQlGGw= X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN8PR21MB1169 X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FORGED_SPF_HELO, KAM_ASCII_DIVIDERS, KAM_LOTSOFHASH, KAM_SHORT, 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: Tue, 30 Nov 2021 23:41:22 -0000 I see. That makes sense. Thanks for the explanation. I was looking at the 6= 4992 and it seems all the implementation right now are only using INTEGER_C= ST at the moment. But now it makes sense. Best wishes, Navid. ________________________________________ From: Andrew Pinski Sent: Tuesday, November 30, 2021 15:18 To: Navid Rahimi Cc: Navid Rahimi via Gcc-patches Subject: Re: [EXTERNAL] Re: [PATCH] tree-optimization/98956 Optimizing out = boolean left shift On Tue, Nov 30, 2021 at 3:08 PM Navid Rahimi wr= ote: > > Hi Andrew, > > Thanks for your detailed comment. There are two problem I wanted to discu= ss with you about: > > a) The optimization I have sent patch, does optimize variable length "<<"= too(for example B0 << x, where x is variable). This [1] link shows the act= ual optimization and a link for the proof is included in the editor. > > b) I am unable to prove the optimization you are describing for non-const= ant length shift. You can take a look at the code example [2] and proof [3]= . I am getting "Transformation doesn't verify!" when I do implement the opt= imization you mentioned for non-constant shift. > > The optimization you are describing only works for "(take: (t << 1) !=3D = 0) -> ((t & 0x7fffffff) !=3D 0)" which only is provable and works for INTEG= ER_CST. No it works with non constants too: t << y !=3D 0 -> t & (-1u>>y) !=3D 0 When y =3D=3D 0, you have t !=3D 0. Which is exactly what you think it should be. Which can be further reduced to t !=3D 0 as y >=3D sizeof(t)*BITS_PER_UNIT is undefined. Thanks, Andrew Pinski > > My understanding might be incorrect here, please don't hesitate to correc= t me. > > 1) https://nam06.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fco= mpiler-explorer.com%2Fz%2Fr46znh4Tj&data=3D04%7C01%7Cnavidrahimi%40micr= osoft.com%7Caa5443e61a5e4cdc177f08d9b457d03e%7C72f988bf86f141af91ab2d7cd011= db47%7C1%7C0%7C637739111521114457%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwM= DAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DhGkyUk= h4Srjb5%2BhvYdT30VLaDLGlkM6jBt3TmfcHFUw%3D&reserved=3D0 > 2) https://nam06.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fco= mpiler-explorer.com%2Fz%2FK1so39dbK&data=3D04%7C01%7Cnavidrahimi%40micr= osoft.com%7Caa5443e61a5e4cdc177f08d9b457d03e%7C72f988bf86f141af91ab2d7cd011= db47%7C1%7C0%7C637739111521124452%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwM= DAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DEiVD3a= IDzds%2BIX5EY3onWVuc%2FdMjoeDSyc5I1B2Xr%2F4%3D&reserved=3D0 > 3) https://nam06.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fal= ive2.llvm.org%2Fce%2Fz%2F-54zZv&data=3D04%7C01%7Cnavidrahimi%40microsof= t.com%7Caa5443e61a5e4cdc177f08d9b457d03e%7C72f988bf86f141af91ab2d7cd011db47= %7C1%7C0%7C637739111521124452%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiL= CJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DvFiA3eWi5R= y3rFwp6iUc61JaVtzoWS6careE4I5rZvk%3D&reserved=3D0 > > Best wishes, > Navid. > > ________________________________________ > From: Andrew Pinski > Sent: Tuesday, November 30, 2021 14:03 > To: Navid Rahimi > Cc: Navid Rahimi via Gcc-patches > Subject: [EXTERNAL] Re: [PATCH] tree-optimization/98956 Optimizing out bo= olean left shift > > On Tue, Nov 30, 2021 at 8:35 AM Navid Rahimi via Gcc-patches > wrote: > > > > Hi GCC community, > > > > This patch will add the missed pattern described in bug 98956 [1] to th= e match.pd. The codegen and correctness proof for this pattern is here [2,3= ] in case anyone is curious. Tested on x86_64 Linux. > > > > A better way to optimize this is the following (which I describe in PR 64= 992): > take: (t << 1) !=3D 0; > > This should be transformed into: > (t & 0x7fffffff) !=3D 0 > > The rest will just fall out really. That is there is no reason to > special case bool here. > I have most of the patch except for creating the mask part which > should be simple, I just did not want to look up the wi:: functions at > the time I was writing it into the bug report. > > Thanks, > Andrew Pinski > > > > > Tree-optimization/98956: > > > > Adding new optimization to match.pd: > > * match.pd ((B0 << x) cmp 0) -> B0 cmp 0 : New optimiza= tion. > > * gcc.dg/tree-ssa/pr98956.c: testcase for this optimiza= tion. > > * gcc.dg/tree-ssa/pr98956-2.c: testcase for node with s= ide-effect. > > > > 1) https://nam06.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2F= gcc.gnu.org%2Fbugzilla%2Fshow_bug.cgi%3Fid%3D98956&data=3D04%7C01%7Cnav= idrahimi%40microsoft.com%7Caa5443e61a5e4cdc177f08d9b457d03e%7C72f988bf86f14= 1af91ab2d7cd011db47%7C1%7C0%7C637739111521124452%7CUnknown%7CTWFpbGZsb3d8ey= JWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&= ;sdata=3DD2%2Fsh1qyHezbiH8xfcwONjnob00Pvu5ktj2kcFlQSxE%3D&reserved=3D0 > > 2) https://nam06.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2F= compiler-explorer.com%2Fz%2Fnj4PTrecW&data=3D04%7C01%7Cnavidrahimi%40mi= crosoft.com%7Caa5443e61a5e4cdc177f08d9b457d03e%7C72f988bf86f141af91ab2d7cd0= 11db47%7C1%7C0%7C637739111521124452%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjA= wMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DcWJR= aWXZBuR6Wt42YkUT5bFpvvWr3n81Kml5KF7gq38%3D&reserved=3D0 > > 3) https://nam06.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2F= alive2.llvm.org%2Fce%2Fz%2FjyJAoS&data=3D04%7C01%7Cnavidrahimi%40micros= oft.com%7Caa5443e61a5e4cdc177f08d9b457d03e%7C72f988bf86f141af91ab2d7cd011db= 47%7C1%7C0%7C637739111521124452%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDA= iLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3Dc1%2FRY7= g4iSCwo5QwJQ3j%2FrpNvM2wlu2nr%2BtaDOOB7v8%3D&reserved=3D0 > > > > Best wishes, > > Navid.