From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR03-VI1-obe.outbound.protection.outlook.com (mail-vi1eur03on2048.outbound.protection.outlook.com [40.107.103.48]) by sourceware.org (Postfix) with ESMTPS id 688AB3857C5C for ; Tue, 25 Oct 2022 10:11:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 688AB3857C5C Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com ARC-Seal: i=2; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=pass; b=Hr3+w5DrznkXsAfRCpkem0284ElGkGYfC1NQk9aLdGbaQ0KCHIGYsWaTqOWj3hlHs1p5t0hJSogh9oD8MuW/E3gYr6vKM5bGSDXXuH413UA4jN7si5OwJ8i2rQBpy9iiWbbnmuz7z0ZzITd7X7U+X/UxTfx1PjfejSjNkmb+vzsNYs9WhgAfJW69sLKCADclYgcuWj5sZmSYpIniOwLvfSYLglyNt6XbGXDsKk5+5pEWBZ3SBurG1o4ktAYc2dtiWN6fX5vkpiT6mD6B6AF811p0GOLCl1EANED9ggJ+aDgYbLcuj0+UHltNMzZIhqj9BVwQ4CtoTrh9XEBxKYormQ== ARC-Message-Signature: i=2; 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=caYUQRoaIB9hXdLk0ryopBojO26uICRgnjFuw71rATU=; b=FK0dw5RlGjBgUf6b+pgXz7kxy8IjgTUOiE9oOIePQXAwoPFPJQpfpzTJESXu2rsO9vm2XxysbB0TkSqMjFu3nwVhjg+BU7LsuB7oBkZDy5KroK4+bwyAO8juF9ipYXe+zah62+3gNdYXG8jSirtbXDrxZsPf7/idna7a4ZbRi2bRLFnq25BZM/Y3tDYaM+8sLDeBgxOPCYJw1JRQVo4QTnMyOXtXfIi5nX+/sfK9TJ74GGkUIk7lonDx9XBLZLqoxd6g5cvMW4NYuo4DlZ/+oTnu6LdKSRm2PH0dW98bM8XiBsuIlNeLlIJFGLRguF9+ZuCBgBZiyJkBK5QV1MLfzQ== ARC-Authentication-Results: i=2; mx.microsoft.com 1; spf=pass (sender ip is 63.35.35.123) smtp.rcpttodomain=sourceware.org smtp.mailfrom=arm.com; dmarc=pass (p=none sp=none pct=100) action=none header.from=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com; arc=pass (0 oda=1 ltdi=1 spf=[1,1,smtp.mailfrom=arm.com] dkim=[1,1,header.d=arm.com] dmarc=[1,1,header.from=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=caYUQRoaIB9hXdLk0ryopBojO26uICRgnjFuw71rATU=; b=d2U3cvoA5YtuXXI4hlvno25n18wcwXiGQBYbEeShLnOWzqvKzMYyDuYx1KuPwASQcxl4gwRxfpY5DxThuj8eRc6wm03wWNR60pAUdIae/D0NT1MviD32N/6PpjZbxD2PGDIF4AMsg6uDiAGSu9Pr6uaJ0txEwQshV2Q/iX5whv8= Received: from FR3P281CA0151.DEUP281.PROD.OUTLOOK.COM (2603:10a6:d10:a2::12) by AS8PR08MB6232.eurprd08.prod.outlook.com (2603:10a6:20b:296::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5723.34; Tue, 25 Oct 2022 10:11:02 +0000 Received: from VI1EUR03FT004.eop-EUR03.prod.protection.outlook.com (2603:10a6:d10:a2:cafe::f6) by FR3P281CA0151.outlook.office365.com (2603:10a6:d10:a2::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5769.12 via Frontend Transport; Tue, 25 Oct 2022 10:11:02 +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 VI1EUR03FT004.mail.protection.outlook.com (100.127.144.92) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5723.32 via Frontend Transport; Tue, 25 Oct 2022 10:11:02 +0000 Received: ("Tessian outbound aeae1c7b66fd:v130"); Tue, 25 Oct 2022 10:11:01 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 0fcfdc8fb4582b8e X-CR-MTA-TID: 64aa7808 Received: from 07cc1ae027fa.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id C512D155-ADC6-4EDB-BC18-B387754BFBB1.1; Tue, 25 Oct 2022 10:10:55 +0000 Received: from EUR05-AM6-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 07cc1ae027fa.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Tue, 25 Oct 2022 10:10:55 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=fcnA1T1rGkoixM/zwLCgkaP68HSKeoD1ij/YQYfmb3Y/dWUGGVqbBmaQHFqykK9Nkjp8v+Yjs13y3ogkqdUe8V750UDszuN9j1UY7J2uN/mGYkt+gqyh1Ny0z9RWjbwYFl7nKg38c9+Etsxf/HukVA36rfn8aV4Y8esdNh0e2lkmkBCGsS2gJcnAZ3X3QpEEzjcebih3s8y3jG1FTnhpVqmwWSyGMBnJPTaEWd3PDxtp3IyKKnVwoKb9fHAP8nD8F9Ii6NYpYK5rXm+zH6850uSEaDauxrNsFIqZwXegqWjD6tyDP+4GRyQTH9FxD//oMuQJsJBi0ZLPPr3YzIjgew== 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=caYUQRoaIB9hXdLk0ryopBojO26uICRgnjFuw71rATU=; b=FN3+cUVK8xdw5fg4PNcO2wqXgK7LjhsSG2Dw6PFbdSBnnLvW7qRI7Vc5Om+pZ+8BCIbB7lpoFJGYmttzBElEa5q9kP9c1c1B0+WYBuMbQdYX1qdj49PAeTDVdjCK750aehWB4z6sXxSpK+tZJl5Z1+CsQOfAV7RGXGg79T+XACeIM0xc5alSbX3TqgJQxtoghc3AM4DZdcAzOx2Lx94pAf1da4MEKmUvAan092HW7zsawaQl2HjhXdkCylsQgeRJhPXttTy1CMwqh0+kh7BFSHuleEyOg9f0ahklN20EikPR+ph+Vv00vBQCbvVnD3a/neCVH/9uqU9BrR/p5wMYEA== 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=caYUQRoaIB9hXdLk0ryopBojO26uICRgnjFuw71rATU=; b=d2U3cvoA5YtuXXI4hlvno25n18wcwXiGQBYbEeShLnOWzqvKzMYyDuYx1KuPwASQcxl4gwRxfpY5DxThuj8eRc6wm03wWNR60pAUdIae/D0NT1MviD32N/6PpjZbxD2PGDIF4AMsg6uDiAGSu9Pr6uaJ0txEwQshV2Q/iX5whv8= Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; Received: from VI1PR08MB3919.eurprd08.prod.outlook.com (2603:10a6:803:c4::31) by AM9PR08MB6036.eurprd08.prod.outlook.com (2603:10a6:20b:2dc::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5746.26; Tue, 25 Oct 2022 10:10:54 +0000 Received: from VI1PR08MB3919.eurprd08.prod.outlook.com ([fe80::7f57:1601:9b18:7529]) by VI1PR08MB3919.eurprd08.prod.outlook.com ([fe80::7f57:1601:9b18:7529%7]) with mapi id 15.20.5746.028; Tue, 25 Oct 2022 10:10:54 +0000 Message-ID: <84a75951-f5a7-fc53-a11a-9a1b964200b7@arm.com> Date: Tue, 25 Oct 2022 11:10:47 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.2 Subject: Re: [committed 1/2] RISC-V: Improve link time complexity. Content-Language: en-US To: Nelson Chu , binutils@sourceware.org Cc: Patrick O'Neill References: <20221025013347.68282-1-nelson@rivosinc.com> From: Luis Machado In-Reply-To: <20221025013347.68282-1-nelson@rivosinc.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-ClientProxiedBy: LO4P265CA0066.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:2af::9) To VI1PR08MB3919.eurprd08.prod.outlook.com (2603:10a6:803:c4::31) MIME-Version: 1.0 X-MS-TrafficTypeDiagnostic: VI1PR08MB3919:EE_|AM9PR08MB6036:EE_|VI1EUR03FT004:EE_|AS8PR08MB6232:EE_ X-MS-Office365-Filtering-Correlation-Id: 0a66ec4a-6a5f-4c7a-d845-08dab67138b6 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: Jy4C9DRfXe2EAleRl6cl+OI7d8eSX1k/LY2lIX25U6Mu+vyY/RpZq77r9gu0rfd8wLKpFUZ7Hjjk9g7Fyn8SQkyauNQAz/KaKKHvDvhZ1S+JMpg0moMNX1JsrQ00QGL/RZDdQQGOdP0ZjaoIauPqkVCbt2fc86wzZlYaFAyBe3w167+Iqt5Fy8bcWBPDg1HWGSSB6x3edMuhfZa54TmrIh+sszbIN2Om2L8hEEuxqffAeew0xe7BS4Q16OUlx/584JA3d9x4G5UdujhZVbd8CHieXnC0IGV01/ivKUC4npS6qAf+ph6kDvC7BJidJO01986Qj9OdhjfqyYCg0AaiuT5opthakkUItHa4U2wWJvkZo20y/2M3YYMn7Zc3WZGnS4z7kFfGAmjwvr+x0g2R1nEIIu7HykdV+pdBsjjOBq/FhnJhvxIAHJHsfLL6Kijumc4Z/o8RodN/V15Zr3D5SBJvW0AMSScZKJWSn3vKW9/fytbK1ebEpXMshQN7AXdmpWx8xwY3ClD51ZTXu977NaLlJ7NeNQPkOE2myBccg6wLllcZiq8vOyicPGfjFdhgJC3vRqWCmTABmOlyu4oU38y1IM2Sm7Lu8f439xCN2tpraD7zl0DIbFHuY240HDjqdHQDnqp4PaAh0sWr0Z/WINhGZ56+6n85C7dlbHUuVYdtp1w/iAp8zuN54+n7zBDv9me9A2ZzdLUYLuX8UgHepCZ/jJYE1GIetXYMbyG8YyFzKZBS6mYDwf7OF8ptIQ7TuRnYvBtj81cCyVSYKwsVWs5Tx1WmH0z5esefrjpIgw0= X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:VI1PR08MB3919.eurprd08.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230022)(4636009)(366004)(39860400002)(376002)(396003)(346002)(136003)(451199015)(31696002)(83380400001)(86362001)(66556008)(38100700002)(8936002)(5660300002)(66946007)(8676002)(2906002)(41300700001)(44832011)(66476007)(4326008)(6506007)(53546011)(6666004)(186003)(26005)(6512007)(2616005)(316002)(478600001)(6486002)(31686004)(36756003)(45980500001)(43740500002);DIR:OUT;SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM9PR08MB6036 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: VI1EUR03FT004.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: a0596439-100c-4174-a2ee-08dab67133bd X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: SJ6pG9Ga4Hl+9WdUn6XK0itFjd0oXmt42s6pvAzxZYWesDe9bZRPt7j6caFO/INiVaTEzhlrnar3mI6gwaoDO0A0GFLmEuXrRU35VXppsXZknaa6yLJ/eP9Inr4PfgkIuFz8gtgaL3xgDyWtZdtUgzy5cmufKMrLExEFhH4MhwHSvrKdmT/eIYzdetp3SssSVfHxH6FT5QIPRBapfxm79jM5gU0SVxU0Blfxkjk5PBsjA5J3NpTukpPCE2cxooAUgUzgQdgfuU75OGjc3Gub25A5GATBzD/e++LG6ADu9PBphObHdVfLA4Hg7bwsXoJv8/aWAdtudwHNJLTTx6iTU//NAS/eKqXwAwSoXcoPUjEec0Mv5k9Urcdo/8PVcw8HKgqcE/1LJfLqxTyRK/XdAe7/MagLnEbhNAXZekzPFQvEFB9wh1FnLzV7ftQqW3saD29jzCiqKnncgyMjEdn6Ueyy/EDWLkXWQv6tN1x5jOoVvYpbMZF0Tg4/Fr7FvsWLpfzp7kiyD9iCYGT/n7+9eYc/Kcvmip66UVs7TiFA00Sa/7ZOBdoE0Hs7ud7uQP+2cBdcxmhC6cRm/fJzKgQvNtKsc9BFyRjSMe+bLxxMX6xPSK2zKVgJDmTft1xfZinzJBrw+ZjNQTucfz+CXv/8dDVQ8fjsMKHkvJKEqoOv8L2HARZgq/pHebW8TIYBWNb/hDpk5QnMg3jCeW6RJSbG+4ji88OmRSGiQpdU4Sszq9Ht3LM9eG6hJWlpYvwqn8yMcZo5vERCEzvD3i9RarvPXHEZtCDnNVfsiLMiK/BUmFduAms/MB8KEujsmmUzNdZA 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:(13230022)(4636009)(346002)(396003)(136003)(376002)(39860400002)(451199015)(36840700001)(46966006)(40470700004)(26005)(2616005)(8936002)(4326008)(47076005)(53546011)(8676002)(6512007)(70206006)(70586007)(5660300002)(41300700001)(36756003)(83380400001)(86362001)(6506007)(31686004)(316002)(31696002)(107886003)(6666004)(336012)(36860700001)(186003)(82740400003)(2906002)(44832011)(356005)(81166007)(478600001)(40460700003)(82310400005)(40480700001)(6486002)(43740500002);DIR:OUT;SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 25 Oct 2022 10:11:02.4319 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 0a66ec4a-6a5f-4c7a-d845-08dab67138b6 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: VI1EUR03FT004.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR08MB6232 X-Spam-Status: No, score=-6.3 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,FORGED_SPF_HELO,KAM_DMARC_NONE,NICE_REPLY_A,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: Hi Nelson, On 10/25/22 02:33, Nelson Chu wrote: > From: Patrick O'Neill > > The riscv port does deletion and symbol table update for each relocation > while relaxing, so we are moving section bytes and scanning symbol table once > for each relocation. Compared to microblaze port, they record the relaxation > changes into a table, then do the deletion and symbol table update once per > section, rather than per relocation. Therefore, they should have better link > time complexity than us. > > To improve the link time complexity, this patch try to make the deletion in > linear time. Compared to record the relaxation changes into a table, we > replace the unused relocation with R_RISCV_DELETE for the deleted bytes, and > then resolve them at the end of the section. Assuming the number of > R_RISCV_DELETE is m, and the number of symbols is n, the total link complexity > should be O(m) for moving section bytes, and O(m*n^2) for symbol table update. > If we record the relaxation changes into the table, and then sort the symbol > table by values, then probably can reduce the time complexity to O(m*n*log(n)) > for updating symbol table, but it doesn't seem worth it for now. > > bfd/ > * elfnn-riscv.c (_riscv_relax_delete_bytes): Renamed from > riscv_relax_delete_bytes, updated to reduce the tiem complexity to O(m) > for memmove. > (typedef relax_delete_t): Function pointer declaration of delete functions. > (riscv_relax_delete_bytes): Can choose to use _riscv_relax_delete_piecewise > or _riscv_relax_delete_immediate for deletion. > (_riscv_relax_delete_piecewise): Just mark the deleted bytes as R_RISCV_DELETE. > (_riscv_relax_delete_immediate): Delete some bytes from a section while > relaxing. > (riscv_relax_resolve_delete_relocs): Delete the bytes for R_RISCV_DELETE > relocations from a section, at the end of _bfd_riscv_relax_section. > (_bfd_riscv_relax_call): Mark deleted bytes as R_RISCV_DELETE by reusing > R_RISCV_RELAX. > (_bfd_riscv_relax_lui): Likewise, but reuse R_RISCV_HI20 for lui, and reuse > R_RISCV_RELAX for c.lui. > (_bfd_riscv_relax_tls_le): Likewise, but resue R_RISCV_TPREL_HI20 and > R_RISCV_TPREL_ADD. > (_bfd_riscv_relax_pc): Likewise, but resue R_RISCV_PCREL_HI20 for auipc. > (_bfd_riscv_relax_align): Updated, don't need to resue relocation since > calling _riscv_relax_delete_immediate. > (_bfd_riscv_relax_delete): Removed. > (_bfd_riscv_relax_section): Set riscv_relax_delete_bytes for each relax_func, > to delete bytes immediately or later. Call riscv_relax_resolve_delete_relocs > to delete bytes for DELETE relocations from a section. > --- > bfd/elfnn-riscv.c | 180 +++++++++++++++++++++++++++++++++------------- > 1 file changed, 131 insertions(+), 49 deletions(-) > This seems to cause build failures due to a couple warnings (Werror). I can reproduce it on armhf Ubuntu 22.04, with the following configure line: configure --enable-targets=all --enable-64-bit-bfd The following warnings show up: elfnn-riscv.c: In function ‘riscv_relax_resolve_delete_relocs’: elfnn-riscv.c:4256:30: error: operand of ‘?:’ changes signedness from ‘int’ to ‘unsigned int’ due to unsignedness of other operand [-Werror=sign-compare] elfnn-riscv.c: In function ‘riscv_relax_resolve_delete_relocs’: elfnn-riscv.c:4256:30: error: operand of ‘?:’ changes signedness from ‘int’ to ‘unsigned int’ due to unsignedness of other operand [-Werror=sign-compare]