From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk1-x735.google.com (mail-qk1-x735.google.com [IPv6:2607:f8b0:4864:20::735]) by sourceware.org (Postfix) with ESMTPS id 342373858C50 for ; Mon, 2 May 2022 13:51:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 342373858C50 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-qk1-x735.google.com with SMTP id j6so11369773qkp.9 for ; Mon, 02 May 2022 06:51:37 -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=7g//bWVYz4GWOP2YIKj97x3EsHOe3IObIkkRHYh+JLs=; b=5YfEpa3RPVdfHf6wbbKwvr06UmgYgAccbOrJsdC/1C7crP4OkxL+e5oRv+KRCtZy8Y bGKilLmg87oIgDB7jl6WjxpHqs8fZsgkpMP70MNObG0PlR9CXMeHi/qTX36hJUhbXzY+ gNfVAigSW32m0CkWqX+0Y4cJHS30RASWdHbCL23cSHQWUSKjnJ3nVy1918X8N53xpIe7 +6W2MWhhnhmwHKM/Kvsfu5UVryjtN1aX31XErAhn1sa1c9nU2Fpib0DV7Wm4dnuDbGth 5LSVeQFYF1BYsof2c7d97zdmnbE8lKHL2Jhc/BTcgkT5C4rUkbQfpuaW0PTF5sWNRJJy XGGA== 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=7g//bWVYz4GWOP2YIKj97x3EsHOe3IObIkkRHYh+JLs=; b=UXXEkJC9O/9OqUcyX4wO32b1/YN3+AC5XYZBGFzf9wTa/UrkEVvCkcGwWTbZsIrvH5 iSb0p3qVci+TxsVtD1t5vySz0hYcDXRq5GyDwyQWDkgrWUFFg5G5cHj2JFM+B9EFpQiO 0ZkFmBcsm0Yor0lbCsCQn9RN5hsOE7n5B//mdSlVGqzP/a8rObPJeFaem1W6tRvpXwWM ZWhVll318E5Njv7PeL8RhWRAH1IPGyALWszaEB0n5jHfEDnRQLhZqgsTv5HQ5nFAWDPA nLzz90M3Z6+e/WHAiW4jxWLWNVWwgeOR/8C6EoTK4dZT35WVZb4bz9cQxWrY+GBgPLLA EzfQ== X-Gm-Message-State: AOAM531VukCDESypHpIUJhzOXnS1ByMeVyKvtdAeRmRm4DBoR62dHN1h 8prfjxOrjrJHylMMM+IZApm5BpwQQRMN0A== X-Google-Smtp-Source: ABdhPJykxJOaTMUKAiv7S51TGcp9t6wgOpIsX0QiYwZY3S5Yy/D5AOS9ChKWqw4KhH4s305EPfo6Lg== X-Received: by 2002:a05:620a:819:b0:69f:c111:8e80 with SMTP id s25-20020a05620a081900b0069fc1118e80mr8584567qks.337.1651499496307; Mon, 02 May 2022 06:51:36 -0700 (PDT) Received: from localhost.localdomain ([38.101.220.237]) by smtp.gmail.com with ESMTPSA id v19-20020ac873d3000000b002f39b99f69asm4232132qtp.52.2022.05.02.06.51.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 May 2022 06:51:35 -0700 (PDT) From: Patrick O'Neill To: binutils@sourceware.org Cc: kito.cheng@gmail.com, palmer@dabbelt.com, gnu-toolchain@rivosinc.com, Patrick O'Neill Subject: [PATCH v2 0/5] RISCV: Improve linker time complexity Date: Mon, 2 May 2022 06:50:43 -0700 Message-Id: <20220502135048.1392596-1-patrick@rivosinc.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220412162601.146507-1-patrick@rivosinc.com> References: <20220412162601.146507-1-patrick@rivosinc.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-5.0 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.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: Mon, 02 May 2022 13:51:38 -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 (4): RISCV: Add linker relaxation tests RISCV: Arrange DELETE pass after .align pass RISCV: Implement piecewise deletion RISCV: Improve runtime of align directives RISCV: Add --defer-deletion flag bfd/elfnn-riscv.c | 212 ++++++++++++++------- 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, 363 insertions(+), 68 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