From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-eopbgr140073.outbound.protection.outlook.com [40.107.14.73]) by sourceware.org (Postfix) with ESMTPS id E17D03858417 for ; Mon, 29 Nov 2021 09:16:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E17D03858417 Received: from DU2P250CA0017.EURP250.PROD.OUTLOOK.COM (2603:10a6:10:231::22) by AM9PR08MB6817.eurprd08.prod.outlook.com (2603:10a6:20b:2ff::23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4734.23; Mon, 29 Nov 2021 09:16:36 +0000 Received: from DB5EUR03FT027.eop-EUR03.prod.protection.outlook.com (2603:10a6:10:231:cafe::60) by DU2P250CA0017.outlook.office365.com (2603:10a6:10:231::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4734.22 via Frontend Transport; Mon, 29 Nov 2021 09:16:36 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by DB5EUR03FT027.mail.protection.outlook.com (10.152.20.121) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4734.20 via Frontend Transport; Mon, 29 Nov 2021 09:16:36 +0000 Received: ("Tessian outbound a33f292be81b:v110"); Mon, 29 Nov 2021 09:16:36 +0000 X-CR-MTA-TID: 64aa7808 Received: from 444b8d711295.2 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 3B784FCD-F7DB-4C30-AF06-7ED0CAA1F6E4.1; Mon, 29 Nov 2021 09:16:31 +0000 Received: from EUR04-HE1-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 444b8d711295.2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Mon, 29 Nov 2021 09:16:31 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Uv8n4WuCujqpvL2zDGu82ueGhedlkti/JZQgMO0FqnMfcFsIsq4uCVqilyLRL2e2ry8irmdTeq2Dx80ijMAoAtbaTPBXwXfFUS32EFolTsh805l/PYHtVa3unb7yc/FqLuMeao4bDRghBY2bVSXPOz83QigAoRUr8TiwsfzUuw6gCdGOSwYtDjYXRvuhCGf6oYghnmiUBE4JdJBgpOf6zkSBJPdcUe5duBtGS+7c+rnnK/6Ln7dK1s/r5816eMvRtZCPk6vIlafNuXRX4wlQEbpvVlQR8hLpZ8J53ZlgqNMG8X/t6Q8OAehiSaF9cUQinI/XV/vuhCxD6pY8XYj7YA== 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=KX7ITi+6PO43q2ZZ8heqb9SsI2DLP9HCNxFyU60evys=; b=Stt8XJJoAuggI2aQfydVpojFP4TwDbfQWPmiYdJumJujPL1+i0GzNzyrxgls8LM2/jb7HH2bEw2a+qe6XLS+cri9kptE0BANkXt6QK1twrZOfAKbB7sk+eH+bTuEPisecoTp1CZxeXoj5R9V0iEzBXxwhQpaBSXLqNqyRpYiesv1gJFih16g5CZy56rDdkcmaes3+eMYHW5Ktg4hVDilkS2e9X/sAvVznnwbQX1ZVBwcuSM1o5ocdXU8glCj0zv7ZTaKsOcUmyWG7oWhZrjh1sYUA8vmzKoxQcxj/P1+V261mm36vtnJ/OmfULPoPACGNFNMuKpdmO2Dcl0FyJmmdQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none Received: from VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) by VE1PR08MB5630.eurprd08.prod.outlook.com (2603:10a6:800:1ae::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4734.22; Mon, 29 Nov 2021 09:16:28 +0000 Received: from VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::12a:3d2c:81ff:8fcc]) by VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::12a:3d2c:81ff:8fcc%8]) with mapi id 15.20.4734.024; Mon, 29 Nov 2021 09:16:28 +0000 From: Tamar Christina To: Richard Biener CC: "gcc-patches@gcc.gnu.org" , nd , "jlaw@tachyum.com" , Richard Sandiford Subject: RE: [PATCH]middle-end cse: Make sure duplicate elements are not entered into the equivalence set [PR103404] Thread-Topic: [PATCH]middle-end cse: Make sure duplicate elements are not entered into the equivalence set [PR103404] Thread-Index: AQHX5PRZD+XAU+VdDEyXdfalDGWtE6waNYQAgAAAtiA= Date: Mon, 29 Nov 2021 09:16:27 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ts-tracking-id: 64971CE45DD47B42B5B9BCD19CE1E04F.0 x-checkrecipientchecked: true Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; x-ms-publictraffictype: Email X-MS-Office365-Filtering-Correlation-Id: 57731928-5273-46e1-c8e4-08d9b318f1bf x-ms-traffictypediagnostic: VE1PR08MB5630:|AM9PR08MB6817: X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true nodisclaimer: true x-ms-oob-tlc-oobclassifiers: OLM:8273;OLM:8273; X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: kXB+xYyYA7Li4H0X3OTAkopaHsCQFTtoU8YJhXlYhQ9W49l0EmJsUnM0rT2zt5s+i3cGqKsox4kfmwpokQvZyfCQYpoCwLBRssBFAgW8ZsM3Sfno59DL6Yy0wN0eP8oOoG1LERVSWJIIc91LA8DhdS8eYyfOoUT/nPjT64qvZrdmmyZys8QrU4B4oaJotSCgX/CAk/znMY/P8tMNe0fQEWjoMh2zucrdC92HeqXVrVsCP/2SvcRY62NFHPJjHR/9PffELWUcIWV1nlHsEBPY9ZmIOQ0i/ICog92P7HqDaP51vBXVCMH/2Xir260nbcnbaS+EojXuSr1V1DgWUOAJcr20hJoeij3nQRG0qFIanPAPtJvficj0ZTPsG+XX16clEdNhKcD7DH68u2xkrLRCx4kJ0NoX93tgp6q2td6si/pGFS48Ql5i/U49fQhwIVHxvvUO6SorEAu7qIqyy5Bm6UA228zVl9Y8xy/LxqhmEerOp+B3U9foN9abJ7lI03eZj4DJF5CEIJN6pzhH8wuc2CV7lpKnMdH97N1S3M+mDAum+VsyHV124SYEGvL75J8AWTLx8AsgZHE6XPB9NAbuxd1LLjP63CvBFM74IHw6siCFx1Qn1ej/xgeVYd197tXx28+bqW5TnXY4Tph3RRv2lYITBzFC3hhV+tHjaFfqDcw03BDQuAcNte4Dss03GlQ73D8NncncVJQ6363AX+sr2GjeFkcfwnrMwO2vZKlptf+ycupsakyD9Qr3kv3oWdqVRMWMGCz58zx15583hO/5lKbF3P5vSXhXOgnmQaaWkZM= X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:VI1PR08MB5325.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(4636009)(366004)(6506007)(26005)(122000001)(54906003)(76116006)(38100700002)(316002)(53546011)(186003)(2906002)(33656002)(5660300002)(7696005)(83380400001)(55016003)(66446008)(71200400001)(4326008)(508600001)(8676002)(6916009)(9686003)(8936002)(84970400001)(86362001)(52536014)(38070700005)(64756008)(66556008)(66476007)(66946007); DIR:OUT; SFP:1101; Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: VE1PR08MB5630 Original-Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: DB5EUR03FT027.eop-EUR03.prod.protection.outlook.com X-MS-Office365-Filtering-Correlation-Id-Prvs: 3f01ce2d-520a-4fd3-4b1f-08d9b318ecb3 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: AI1J/k7tji9QGvQ2yZnwYx55bJFTgZielRH5nCjJ2MMs75aT3Blge+8QfVC2+AMxyvXaCRihMtobIlEGtERfnVEt0lNNx6Ll8yxHW/ZDEFATYXNFsBHk1B/Ep1MH/Lx59YtFIGN3X6gFxQN2BUH6hczN55P9I+TG/5H1LFi9tUA/8PFOKRJ4ixF+bwmgIZZq+QW3B4/9TmQGzYsMwE9XkNs5HbEuxLYOlvAItwICHsdKZfEl2CXxPUxWUpyFY22y1GX0DbpG/EGSnm+8usg8KQLDOYFL/hl58WpsiVNQJVqZ//3PQam7ygXY6tusmkSxszJBnYEPP/9E216FLzzH34Da3ZwnBEvPlnMIY94/qW15H11CqY4ChcwBaeBtpi7melL4hW5CoTabhjuVUe9JDB/6iv8IkIvoZenyW9B/UYGfqiced8T9Bj3BwmMXaNni31IXJW3or+I9MorGcuwbAGkSOQfgnJTv210YYWT+GPttt3pq7wjih1jM316GC2bISLQbggHLnMGb6sCxO72A2OzIExKW5V+UBw6EKSBiF3xk81WBOM9KCRe9hKmo/9IqQVt+V5dExnWDGMcYX6u/RuiIewYHNBgVqSSsuMfGz+7bAFljzpR9oD3N2NXEcDO1hBAkkYajzwy4ISAYP6pLi1Cy8y8RYgbb9T9L9ZBzAmztBz/IjzFf2JJJpVDHvOURAmJffMakOM6dPaizFniA9rrXEmnY4oGBn9PKTMvwQM9HHvMiHizndI90zL5nhoRP1JtmURxBEXf9mV61rmpLzXRkd2AQ3OpPu76zmiQNYUk= X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; CAT:NONE; SFS:(4636009)(46966006)(36840700001)(8676002)(52536014)(83380400001)(82310400004)(86362001)(6506007)(53546011)(9686003)(6862004)(54906003)(8936002)(33656002)(7696005)(5660300002)(81166007)(316002)(4326008)(2906002)(84970400001)(508600001)(36860700001)(336012)(186003)(70586007)(70206006)(26005)(47076005)(356005)(55016003); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 29 Nov 2021 09:16:36.6010 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 57731928-5273-46e1-c8e4-08d9b318f1bf X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: DB5EUR03FT027.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM9PR08MB6817 X-Spam-Status: No, score=-13.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_PASS, TXREP, UNPARSEABLE_RELAY autolearn=ham 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: Mon, 29 Nov 2021 09:16:54 -0000 > -----Original Message----- > From: Richard Biener > Sent: Monday, November 29, 2021 9:02 AM > To: Tamar Christina > Cc: gcc-patches@gcc.gnu.org; nd ; jlaw@tachyum.com; > Richard Sandiford > Subject: Re: [PATCH]middle-end cse: Make sure duplicate elements are not > entered into the equivalence set [PR103404] >=20 > On Mon, 29 Nov 2021, Tamar Christina wrote: >=20 > > Hi All, > > > > CSE uses equivalence classes to keep track of expressions that all > > have the same values at the current point in the program. > > > > Normal equivalences through SETs only insert and perform lookups in > > this set but equivalence determined from comparisons, e.g. > > > > (insn 46 44 47 7 (set (reg:CCZ 17 flags) > > (compare:CCZ (reg:SI 105 [ iD.2893 ]) > > (const_int 0 [0]))) "cse.c":18:22 7 {*cmpsi_ccno_1} > > (expr_list:REG_DEAD (reg:SI 105 [ iD.2893 ]) > > (nil))) > > > > creates the equivalence EQ on (reg:SI 105 [ iD.2893 ]) and (const_int 0= [0]). > > > > This causes a merge to happen between the two equivalence sets denoted > > by (const_int 0 [0]) and (reg:SI 105 [ iD.2893 ]) respectively. > > > > The operation happens through merge_equiv_classes however this > > function has an invariant that the classes to be merge not contain any > > duplicates. This is because it frees entries before merging. > > > > The given testcase when using the supplied flags trigger an ICE due to > > the equivalence set being > > > > (rr) p dump_class (class1) > > Equivalence chain for (reg:SI 105 [ iD.2893 ]): > > (reg:SI 105 [ iD.2893 ]) > > $3 =3D void > > > > (rr) p dump_class (class2) > > Equivalence chain for (const_int 0 [0]): > > (const_int 0 [0]) > > (reg:SI 97 [ _10 ]) > > (reg:SI 97 [ _10 ]) > > $4 =3D void > > > > This happens because the original INSN being recorded is > > > > (insn 18 17 24 2 (set (subreg:V1SI (reg:SI 97 [ _10 ]) 0) > > (const_vector:V1SI [ > > (const_int 0 [0]) > > ])) "cse.c":11:9 1363 {*movv1si_internal} > > (expr_list:REG_UNUSED (reg:SI 97 [ _10 ]) > > (nil))) > > > > and we end up generating two equivalences. the first one is simply > > that reg:SI 97 is 0. The second one is that 0 can be extracted from > > the V1SI, so subreg (subreg:V1SI (reg:SI 97) 0) 0 =3D=3D 0. This neste= d > > subreg gets folded away to just reg:SI 97 and we re-insert the same > equivalence. > > > > This patch changes it so that once we figure out the bucket to insert > > into we check if the equivalence set already contains the entry and if > > so just return the existing entry and exit. > > > > Bootstrapped Regtested on aarch64-none-linux-gnu, x86_64-pc-linux-gnu > > and no regressions. > > > > > > Ok for master? > > > > Thanks, > > Tamar > > > > gcc/ChangeLog: > > > > PR rtl-optimization/103404 > > * cse.c (insert_with_costs): Check if item exists already before > adding > > a new entry in the equivalence class. > > > > gcc/testsuite/ChangeLog: > > > > PR rtl-optimization/103404 > > * gcc.target/i386/pr103404.c: New test. > > > > --- inline copy of patch -- > > diff --git a/gcc/cse.c b/gcc/cse.c > > index > > > c1c7d0ca27b73c4b944b4719f95fece74e0358d5..08295246c594109e947276051c > 67 > > 76e4cabca4ec 100644 > > --- a/gcc/cse.c > > +++ b/gcc/cse.c > > @@ -1537,6 +1537,17 @@ insert_with_costs (rtx x, struct table_elt *clas= sp, > unsigned int hash, > > if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER) > > add_to_hard_reg_set (&hard_regs_in_table, GET_MODE (x), REGNO > > (x)); > > > > + /* We cannot allow a duplicate to be entered into the equivalence se= ts > > + and so we should perform a check before we do any allocations or > > + change the buckets. */ > > + if (classp) > > + { > > + struct table_elt *p; > > + for (p =3D classp; p; p =3D p->next_same_value) > > + if (exp_equiv_p (p->exp, x, 1, false)) > > + return p; >=20 > not really a review, leaving that to who approved the original change, bu= t > these things always look bad - this linear list walk makes insert_with_co= sts > quadratic. Is there any mitigation (like limiting the number of entries?= ), is > that already an existing problem elsewhere in CSE? Hmm I believe insert_with_costs is already quadratic as it walks the list a= fter allocations in a similar manner.=20 The problem is that the function assumes it can't ever fail, so it starts o= ff by allocating memory and modifying the table itself. There are also two ways it can allo= cate memory, so by the time it starts walking the classp itself and we notice any duplic= ates we did quite a lot of work already and can't easily undo all of it. Ideally the function= would identify the insertion point before it does any changes. But there are multiple way= s to determine where to insert. But.. I think I can use the result of the first walk to seed the second wal= k which becomes O(1). That way there's no additional work being done. I'll update the patch. Regards, Tamar >=20 > > + } > > + > > /* Put an element for X into the right hash bucket. */ > > > > elt =3D free_element_chain; > > diff --git a/gcc/testsuite/gcc.target/i386/pr103404.c > > b/gcc/testsuite/gcc.target/i386/pr103404.c > > new file mode 100644 > > index > > > 0000000000000000000000000000000000000000..66f33645301db09503fc0977fd > 0f > > 061a19e56ea5 > > --- /dev/null > > +++ b/gcc/testsuite/gcc.target/i386/pr103404.c > > @@ -0,0 +1,32 @@ > > +/* { dg-do compile } */ > > +/* { dg-additional-options "-Og -fcse-follow-jumps -fno-dce > > +-fno-early-inlining -fgcse -fharden-conditional-branches > > +-frerun-cse-after-loop -fno-tree-ccp -mavx5124fmaps -std=3Dc99 -w" } *= / > > + > > +typedef unsigned __attribute__((__vector_size__ (4))) U; typedef > > +unsigned __attribute__((__vector_size__ (16))) V; typedef unsigned > > +__attribute__((__vector_size__ (64))) W; > > + > > +int x, y; > > + > > +V v; > > +W w; > > + > > +inline > > +int bar (U a) > > +{ > > + a |=3D x; > > + W k =3D > > + __builtin_shufflevector (v, 5 / a, > > + 2, 4, 0, 2, 4, 1, 0, 1, > > + 1, 2, 1, 3, 0, 4, 4, 0); > > + w =3D k; > > + y =3D 0; > > +} > > + > > +int > > +foo () > > +{ > > + bar ((U){0xffffffff}); > > + for (unsigned i; i < sizeof (foo);) > > + ; > > +} > > + > > > > > > >=20 > -- > Richard Biener > SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 > Nuernberg, Germany; GF: Ivo Totev; HRB 36809 (AG Nuernberg)