From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg1-x530.google.com (mail-pg1-x530.google.com [IPv6:2607:f8b0:4864:20::530]) by sourceware.org (Postfix) with ESMTPS id 53DB8383A303 for ; Fri, 27 May 2022 21:20:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 53DB8383A303 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=rivosinc.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rivosinc.com Received: by mail-pg1-x530.google.com with SMTP id j21so4900476pga.13 for ; Fri, 27 May 2022 14:20:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rivosinc-com.20210112.gappssmtp.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=nt7EI80uReJtQUEsm2dJWZxd5Y2c2Xv/1z5ZV95KaWk=; b=dUUuw9DPJ2K2LWT+B2adZE7gu0263NLQ2PXfzuLUZjvSEMEZzW3+cwhwXOgY3+9Nue eKwIy+qCtce996IPjpUpHlw63rehss6Tx/Dnv9V87abqstlX2tIANjB3Bt8Me5ayi/cv 14BlOVjs5uwEcUCNn9OtCqy/vLnw+bZVqMgjXaSr3BXWK3A1zt8JgFkl2qwZeOQoOxcO qCdPYJmZ7UYmDmyBawgk/Saww4UQPsS2ZW1e7H3h+Whfj9AWeBLP7QoZIjQGp5Ke+di5 6JD7A2eaBxSQVtf3ISbEfxcHCsShnWm2Zp4kEjuJsrkgAmVgAQjdsAoPymde27mROiR4 QPbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=nt7EI80uReJtQUEsm2dJWZxd5Y2c2Xv/1z5ZV95KaWk=; b=apfkn+Bz/c0OUT6QXkBpPnPNWweTatIFTuzttGhlYC6rYDR9FuEvDfP30EItCcAFdi ++4dWQV0R69J/GVl1yODgpp53sZ5rG0pa9MUBG+kVdyFIztdzBWFSBuDBtbWUXWh4V/1 XBJ6bCtrGLeOsfOctE3hxqqagJzTnI5h6GBrQ7E9ElvhbgKN0cXkjfZWeGtkrr4GYmRw //8oI9aAloe4mEpD6GkhAo6r/yFghKDvpLkdN9j/JOyjUzUqMdGlBN5Tiop42DxR2dmg nGZ8vD8jECoJa5xM9jyCWWK+0T7gpRSIp0XHu7m/xBNviRqme5zT/A35wscSl4uZ0Byw IKOA== X-Gm-Message-State: AOAM53382h/mZyfNnYteVImhQwJkd6FctaxS67Kiv2vuUScCcfRBXwB7 Zt1naS6fqVwahHfxqsfEwOWjVvbiMcFMMA== X-Google-Smtp-Source: ABdhPJwXQ9V8y7EU85GFDDH+Xc1xD03OpJL49rKCyty+b3BI/o3MCdzCYT1m84haNDql2PrdSO1gMQ== X-Received: by 2002:a05:6a00:803:b0:518:8afd:25 with SMTP id m3-20020a056a00080300b005188afd0025mr31400405pfk.41.1653686439045; Fri, 27 May 2022 14:20:39 -0700 (PDT) Received: from patrick-ThinkPad-X1-Carbon-Gen-8.hq.rivosinc.com ([12.3.194.138]) by smtp.gmail.com with ESMTPSA id o20-20020a63fb14000000b003ed6b3dc52esm3901320pgh.55.2022.05.27.14.20.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 27 May 2022 14:20:38 -0700 (PDT) From: Patrick O'Neill To: binutils@sourceware.org, nelson.chu@sifive.com Cc: gnu-toolchain@rivosinc.com, jim.wilson.gcc@gmail.com, palmer@rivosinc.com, andrew@sifive.com, kito.cheng@gmail.com, Patrick O'Neill Subject: [PATCH v3 0/3] RISCV: Improve linker time complexity Date: Fri, 27 May 2022 14:20:02 -0700 Message-Id: <20220527212005.30709-1-patrick@rivosinc.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220502135048.1392596-1-patrick@rivosinc.com> References: <20220502135048.1392596-1-patrick@rivosinc.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 27 May 2022 21:20:42 -0000 The current linker has an O(n^2) time complexity when it comes to deleting bytes. By deferring the deletion of bytes, we can achieve O(n) deletion runtime. There is a pathological case that could cause this to have worse performance, so the --no-defer-deletion flag is added to allow users to opt-out. Patrick O'Neill (3): RISCV: Add linker relaxation tests RISCV: Implement piecewise deletion RISCV: Add --defer-deletion flag bfd/elfnn-riscv.c | 193 ++++++++++++++++----- include/bfdlink.h | 4 + ld/ld.texi | 10 ++ ld/ldlex.h | 2 + ld/lexsup.c | 10 ++ ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp | 6 + ld/testsuite/ld-riscv-elf/relax-call-1.d | 17 ++ ld/testsuite/ld-riscv-elf/relax-call-1.s | 7 + ld/testsuite/ld-riscv-elf/relax-call-2.d | 21 +++ ld/testsuite/ld-riscv-elf/relax-call-2.s | 10 ++ ld/testsuite/ld-riscv-elf/relax-call-3.d | 25 +++ ld/testsuite/ld-riscv-elf/relax-call-3.s | 13 ++ ld/testsuite/ld-riscv-elf/relax-call-4.d | 19 ++ ld/testsuite/ld-riscv-elf/relax-call-4.s | 8 + ld/testsuite/ld-riscv-elf/relax-call-5.d | 23 +++ ld/testsuite/ld-riscv-elf/relax-call-5.s | 11 ++ ld/testsuite/ld-riscv-elf/relax-call-6.d | 22 +++ ld/testsuite/ld-riscv-elf/relax-call-6.s | 11 ++ 18 files changed, 366 insertions(+), 46 deletions(-) create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-1.d create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-1.s create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-2.d create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-2.s create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-3.d create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-3.s create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-4.d create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-4.s create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-5.d create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-5.s create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-6.d create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-6.s -- 2.25.1