From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR03-AM7-obe.outbound.protection.outlook.com (mail-am7eur03on2042.outbound.protection.outlook.com [40.107.105.42]) by sourceware.org (Postfix) with ESMTPS id BD6EC3858D33 for ; Tue, 3 Oct 2023 11:41:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org BD6EC3858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=nMUgSlArisW4STDoncLM5qYl7vKJJS7Ja4YA8tknkfc=; b=FyIgYFdOkwzRrdQJB2L7YAAQDslaANb/wxVlTpCk9777AsqnJh1yvmJDOyUu2GILVrI7aryOu+DE3yGf/MwA5mbzdIvxfO6n6F85VZL2a+C5yfNKAC+2D6ARzKRDb6u9B/olrHDsXo5Oacso2zA+1/+A9h/wh/9rM5X2ppqUM04= Received: from DUZPR01CA0217.eurprd01.prod.exchangelabs.com (2603:10a6:10:4b4::11) by AM9PR08MB6066.eurprd08.prod.outlook.com (2603:10a6:20b:2d8::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6838.33; Tue, 3 Oct 2023 11:41:11 +0000 Received: from DBAEUR03FT016.eop-EUR03.prod.protection.outlook.com (2603:10a6:10:4b4:cafe::dd) by DUZPR01CA0217.outlook.office365.com (2603:10a6:10:4b4::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6838.33 via Frontend Transport; Tue, 3 Oct 2023 11:41:11 +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; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by DBAEUR03FT016.mail.protection.outlook.com (100.127.142.204) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6863.24 via Frontend Transport; Tue, 3 Oct 2023 11:41:11 +0000 Received: ("Tessian outbound 9aeaca65ec26:v211"); Tue, 03 Oct 2023 11:41:11 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 4b4d1ae193c80d70 X-CR-MTA-TID: 64aa7808 Received: from f6262638158d.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 294E7047-D65F-41AF-810B-ACD17BEF548A.1; Tue, 03 Oct 2023 11:41:05 +0000 Received: from EUR03-DBA-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id f6262638158d.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Tue, 03 Oct 2023 11:41:05 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=YS3+rFoB5Ni8sVcwt8WaeCJWamZK8M1Paw8mJcUfZ5cqBUJHaU1DU7dgUaLhLa1IUeFJTjzoImzS2EDxbkD0RQU9oC3jYev7Bpf44ifOugHKLdJrmdg0S+n+Db7Bz4BYb3bwSEsC2mSBHA8658v1obZhnn/LPGDoyVB5OFkjTA+6hNmsbRZ9NerjQ/QXzaTulUF7ysmFK+azAym4LYfjsj2BDtg3HeA2H9mb4EUDX3dapgCC9ZMO0zx6GTjKDpNuvrxrU/bGfb4t00LykZBfDgGYQRwU/zqAjnybGe7ohi4wbRZyqYRJM+repg0Hgw6IoQHHcR4edAYEM/ITVh1Fyg== 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=nMUgSlArisW4STDoncLM5qYl7vKJJS7Ja4YA8tknkfc=; b=g/r9PNCp3EPYzoWiHa1z41LLa6xmrRwwKClXgbvlbEbGvh9AIM286KWobo1HfbVsC3/q1SXW/3Wc5vbg5Int3P8ZX+AKK1GcO6QaThkplRq237OJxfIs3Kj8cLzRiChZqs2vWXCYkKvm8zvImQu6ZQC666isJkcvvX3yZ9cBAVoT9m3tl9kPNXtLnV9BTJKOiF+fVq8rCTW2CPagmBLz9tTGGVIpunNVjX8zIrPT/krWsxCmB4dxDuxHQRUxWLc12QhR/MwbXFV5mkmtmhU7CH8zvD0fnJVtpYTaQyjwI2jmMg69arbpoWzVN4B3Yrbw3SC/awsXt4ck9tyWqKGDdw== 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 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=nMUgSlArisW4STDoncLM5qYl7vKJJS7Ja4YA8tknkfc=; b=FyIgYFdOkwzRrdQJB2L7YAAQDslaANb/wxVlTpCk9777AsqnJh1yvmJDOyUu2GILVrI7aryOu+DE3yGf/MwA5mbzdIvxfO6n6F85VZL2a+C5yfNKAC+2D6ARzKRDb6u9B/olrHDsXo5Oacso2zA+1/+A9h/wh/9rM5X2ppqUM04= Received: from VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) by DB9PR08MB6521.eurprd08.prod.outlook.com (2603:10a6:10:254::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6838.28; Tue, 3 Oct 2023 11:41:02 +0000 Received: from VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::662f:8e26:1bf8:aaa1]) by VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::662f:8e26:1bf8:aaa1%7]) with mapi id 15.20.6838.033; Tue, 3 Oct 2023 11:41:02 +0000 From: Tamar Christina To: Jakub Jelinek CC: "gcc-patches@gcc.gnu.org" , nd , "jwakely@redhat.com" Subject: RE: [PATCH]middle-end: Recursively check is_trivially_copyable_or_pair in vec.h Thread-Topic: [PATCH]middle-end: Recursively check is_trivially_copyable_or_pair in vec.h Thread-Index: AQHZ9S1sAApQkqVeFk2GOXr6jrXFlbA2fFeAgAAwEcCAATtKgIAAB41Q Date: Tue, 3 Oct 2023 11:41:01 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; x-ms-traffictypediagnostic: VI1PR08MB5325:EE_|DB9PR08MB6521:EE_|DBAEUR03FT016:EE_|AM9PR08MB6066:EE_ X-MS-Office365-Filtering-Correlation-Id: cde655d9-16bf-4180-7e05-08dbc405a48e x-checkrecipientrouted: true nodisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: P3Io/Va+lLKUchb/LwH+QSOeqY7H3J+CT2XWnTA4bwXvlicyHfUxmYNtuLPs1d/DUli/JUhz1oE8AHFFQqCNURsbIpThweC+dIdSmSyiFtmHPD0oRiDpybtHWWz8eAwboYvoP0h0QGFDW3Cx1hpmh5Pq6DEKq4Yb1M551BaOUKldzZDdQKlD850Ox5+BJopIGUff948ZcpLcq0/1G7kV4cQMxZiXgfZDDZnLTd+JNIANP5mnL7p5qCMquj116dnjYWsBjuU93L9A0SSOD2FN5k3qNQ9iPrdbGJMjrydrVzuZjn9YV7OYyhDev91/grBOHDC7C+NR0V4rsofqu6o1gFFriDh4GKq1t5dFtw6rtZqiDU55Ezg0bVDYcqQE1FSSqrdTNBlujfSJ2uC1Y3xpS2a6IUwMoDfcYLAxEd8KsHSwVY3NeApsrEyEUl1vzNg5t4rFfVlLcbg82Eo3lTgaoZyVhmLS2hNID8FxLittr2p8iAlwKBe3QQvrFcUOM9LO8W2JnD1fP/F8SBhgwBPC5vf8JN5KK/+FYze2MhDvDagqLm+H1y7k1+HSCIHgQpEz4lAWGVJ+b8tQOliqNLOKRhhEISznwBLK3ASLfo0JfFMCI/hgU9hiG8IFs3CVYHbS 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:(13230031)(39860400002)(396003)(136003)(366004)(346002)(376002)(230922051799003)(186009)(1800799009)(64100799003)(451199024)(7696005)(53546011)(6506007)(9686003)(478600001)(83380400001)(316002)(26005)(71200400001)(52536014)(6916009)(41300700001)(66476007)(38070700005)(64756008)(66446008)(4326008)(5660300002)(8676002)(8936002)(76116006)(54906003)(2906002)(66946007)(66556008)(33656002)(38100700002)(122000001)(86362001)(55016003);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: DB9PR08MB6521 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: DBAEUR03FT016.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: 0b2b2070-f8bf-4c19-163b-08dbc4059eb1 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: S3cCfJ5LU3uvswIO/J/OvN2jgXAc/Q4JDSBMlCAvckKVhiOv+jG4RiO3UzBpX6Haoiyw9pVjcAAJdN1Z7OEyUFZnYvX2q6fwy7kCZ77TtchfIiKmguebzyDjQrbgKF6uaurRiS2W6f/rpnBpF+Iut5E8b+NmhPVJ31VJ+N2qXTRN71kKKbiBZK3jSfQDDGvHc1qr0AN6+CrBlQQztv8OqAS66kKHMTpVIBLCHThlJyuG1Zx2Jj4u/SuKQ74E63Nf4CvPCys6DMxQ59s3oy033aHVr4JWcP4ru5aKiRDwY+0Unw4kYX5quRD5VTr8jvhJvS0UwQTZWbr8j/xcLHC8HQ9FHYDs7/5dZntWzAZM5D7Zx7ZiFN7+NApLxwdKjrStHpFiiZgAiWLNA9X52jrj0PCw7Cz1yQqHa4pXDdLVajCB8m6ZctC4ZmPp4TXL7cvt1OpL7gUtdLuMuyToKYjQtAaNqQWhYdb90Irqpk+8GBui7NBOUPOnVQNPwuXMEHtaBIUaOb12Fp/lxdJUDLN457Gyp/PRy1xVIG77B7oIZkODrZ/QTrIweKW/ObuJbRv8fBU4Hl1qy9JknXPE9/4k2LfX1i8G2m0ts2T8m/xsFl0T7h8GKGnIbhunVCWf3iHngPZDds4rXCuCUgxJGPmhmTNw31sVxuGzTNDmDoCj2o616G/M/NSrUBYVpQKODHg2UlLY5frnJ6q52Ehv3tZshB49/PV1clc39Ud7ghPtD4OvAirjgeDFXF34D4Wp+3nM 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:(13230031)(4636009)(376002)(136003)(39860400002)(396003)(346002)(230922051799003)(82310400011)(186009)(451199024)(64100799003)(1800799009)(36840700001)(40470700004)(46966006)(7696005)(478600001)(6506007)(53546011)(40460700003)(107886003)(55016003)(9686003)(26005)(83380400001)(40480700001)(2906002)(33656002)(36860700001)(54906003)(336012)(47076005)(86362001)(70586007)(70206006)(41300700001)(316002)(356005)(5660300002)(81166007)(52536014)(82740400003)(8936002)(6862004)(4326008)(8676002);DIR:OUT;SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 03 Oct 2023 11:41:11.7270 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: cde655d9-16bf-4180-7e05-08dbc405a48e 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: DBAEUR03FT016.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM9PR08MB6066 X-Spam-Status: No, score=-6.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,FORGED_SPF_HELO,KAM_DMARC_NONE,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_NONE,TXREP,UNPARSEABLE_RELAY autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: > -----Original Message----- > From: Jakub Jelinek > Sent: Tuesday, October 3, 2023 12:02 PM > To: Tamar Christina > Cc: gcc-patches@gcc.gnu.org; nd ; jwakely@redhat.com > Subject: Re: [PATCH]middle-end: Recursively check > is_trivially_copyable_or_pair in vec.h >=20 > On Tue, Oct 03, 2023 at 10:27:16AM +0000, Tamar Christina wrote: > > +/* Structure used to track meta-data on PHI arguments used to generate > > + most efficient comparison sequence to slatten a PHI node. */ >=20 > ^^^ typo (at least, never hea= rd of this word, and > wiktionary doesn't know it either (except for Dannish/Swedish)) >=20 > > @@ -2045,6 +2065,25 @@ gen_phi_nest_statement (gphi *phi, > gimple_stmt_iterator *gsi, > > return lhs; > > } > > >=20 > Perhaps add a short function comment here? >=20 > > +static int > > +cmp_arg_entry (const void *p1, const void *p2) { > > + const ifcvt_arg_entry sval1 =3D *(const ifcvt_arg_entry *)p1; > > + const ifcvt_arg_entry sval2 =3D *(const ifcvt_arg_entry *)p2; > > + > > + if (sval1.num_compares < sval2.num_compares) > > + return -1; > > + else if (sval1.num_compares > sval2.num_compares) > > + return 1; > > + > > + if (sval1.occurs < sval2.occurs) > > + return -1; > > + else if (sval1.occurs > sval2.occurs) > > + return 1; > > + > > + return 0; > > +} > > + >=20 > > @@ -2167,61 +2206,53 @@ predicate_scalar_phi (gphi *phi, > gimple_stmt_iterator *gsi) > > /* Create hashmap for PHI node which contain vector of argument inde= xes > > having the same value. */ > > bool swap =3D false; > > - hash_map > phi_arg_map; > > + hash_map > phi_arg_map; > > unsigned int num_args =3D gimple_phi_num_args (phi); > > /* Vector of different PHI argument values. */ > > - auto_vec args (num_args); > > + auto_vec args; > > > > - /* Compute phi_arg_map. */ > > + /* Compute phi_arg_map, determine the list of unique PHI args and th= e > indices > > + where they are in the PHI node. The indices will be used to dete= rmine > > + the conditions to apply and their complexity. */ > > for (i =3D 0; i < num_args; i++) > > { > > tree arg; > > > > arg =3D gimple_phi_arg_def (phi, i); > > - if (!phi_arg_map.get (arg)) > > - args.quick_push (arg); > > phi_arg_map.get_or_insert (arg).safe_push (i); > > } > > > > - /* Determine element with max number of occurrences and complexity. > Looking at only > > - number of occurrences as a measure for complexity isn't enough as= all > usages can > > - be unique but the comparisons to reach the PHI node differ per br= anch. > */ > > - typedef std::pair > ArgEntry; > > - auto_vec argsKV; > > - for (i =3D 0; i < args.length (); i++) > > + /* Determine element with max number of occurrences and complexity. > Looking > > + at only number of occurrences as a measure for complexity isn't e= nough > as > > + all usages can be unique but the comparisons to reach the PHI nod= e differ > > + per branch. */ > > + for (auto entry : phi_arg_map) > > { > > unsigned int len =3D 0; > > - for (int index : phi_arg_map.get (args[i])) > > + for (int index : entry.second) > > { > > edge e =3D gimple_phi_arg_edge (phi, index); > > len +=3D get_bb_num_predicate_stmts (e->src); > > } > > > > - unsigned occur =3D phi_arg_map.get (args[i])->length (); > > + unsigned occur =3D entry.second.length (); > > if (dump_file && (dump_flags & TDF_DETAILS)) > > fprintf (dump_file, "Ranking %d as len=3D%d, idx=3D%d\n", i, len, occ= ur); > > - argsKV.safe_push ({ args[i], { len, occur }}); > > + args.safe_push ({ entry.first, len, occur, entry.second }); > > } > > > > /* Sort elements based on rankings ARGS. */ > > - std::sort(argsKV.begin(), argsKV.end(), [](const ArgEntry &left, > > - const ArgEntry &right) { > > - return left.second < right.second; > > - }); > > - > > - for (i =3D 0; i < args.length (); i++) > > - args[i] =3D argsKV[i].first; > > + args.qsort (cmp_arg_entry); >=20 > I admit I don't know what you're using the args vector later on for and > whether its ordering affects code generation, but because you qsort it I > assume it does. My worry is that a hash_map traversal might not be the sa= me > order on all hosts and similarly qsort doesn't achieve stable sorting in = case > num_compares and occurrs members are equal for two or more different > arguments. Can that ever happen? The order does matter but only for args. The hashmap is only used to collec= t the unique values and their locations. While you can have num_compares and occurs being the same it wouldn't matter for the optimization as they are b= oth "equally" as expensive. It would matter in the case where they are the las= t 2 entries in the list as we never test the last entry. So your codegen would select a different element then to test. So could potentially affect repro= ducibility. > We have stablesort method instead of > qsort but that would require consistent ordering in the vector (std::sort > doesn't ensure stable sorting either). >=20 > If it is a non-issue, the patch is ok with the above nits fixed. Otherwi= se > perhaps we'd need to push in the first loop into the vector (but that > if (!phi_arg_map.get (arg)) > args.quick_push (arg); > phi_arg_map.get_or_insert (arg).safe_push (i); in there was quite > inefficient, better would be > bool existed; > phi_arg_map.get_or_insert (arg, &existed).safe_push (i); > if (!existed) > args.safe_push (ifcvt_arg_entry { arg, 0, 0, vNULL }); or something > similar), plus use stablesort. Or add another compared member which woul= d > be the first position. Hmm the problem here is that it would make the second loop that fills in th= e len quadratic as it has to search for arg in the list. I suppose I could push = a pointer to the struct instead of `i` in the hashmap and the element into args and u= pdate the pointer as we go along? Would that work? Regards, Tamar >=20 > Jakub