From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pl1-x62d.google.com (mail-pl1-x62d.google.com [IPv6:2607:f8b0:4864:20::62d]) by sourceware.org (Postfix) with ESMTPS id 9D4DF3858C83 for ; Mon, 25 Apr 2022 17:26:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9D4DF3858C83 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-pl1-x62d.google.com with SMTP id k4so16245774plk.7 for ; Mon, 25 Apr 2022 10:26:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rivosinc-com.20210112.gappssmtp.com; s=20210112; h=message-id:date:mime-version:user-agent:subject:content-language:to :cc:references:from:in-reply-to:content-transfer-encoding; bh=EL/oYADZ6rsXn661PEg3TbaMtExM9IH+6LTJdmJGWAQ=; b=iUwjE2/PsoKSdduFV3OxE4yjJQ4H7tiqTcWYDiYhqm2guaYOJW37Uee8peyWqdlOHo DYXCX/9S1hkYtH4Fw9IXcxN2YDNlQZRfa57eomk8Zp+Vg1XmPavsJRD4beDQkHZL+Iy4 HezFzm2ck7/QXWd6rRy7HAdpRIh3AxFenP3+BzktV6n//Z68SjdFT5p30n/Xcyr3z39k LCbFypQDk3WnGO23Ts5EtZW4kOxEo7AEIKkvRjRvu8i9KmHuUo5CV2qPCKWYPFc6B0jB kC5BGCD/vsiohgtAcdpIV5ntdho44NOaVOCQlSlGAYpVsXJSrlVLeGS6tjLbaD07pYX8 A1GQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:cc:references:from:in-reply-to :content-transfer-encoding; bh=EL/oYADZ6rsXn661PEg3TbaMtExM9IH+6LTJdmJGWAQ=; b=4TvuUzrObt0O9MbhnTxoQzlbTfdfH/xVk/SuIsiMjY0xos8DghE4UA413rovQq38c+ /aHkDn3d0oR6iOQ+DW9V7Sgo2ixCnPPjJI7DJRoHHIWe6rDLq32jcsxO062sbfO3CQER XuU+Htu01kNHPLkz3k5BhbEokO58IS1HlSCxD7hVwZdBnCUBpPyx1JxsQBj1l8Vu6gQt iSl3sVCawimBBLcRJ82Lbm6yTKiqeAJeRtxV/DAamA0AVFu4tUu+MAxnqV+dbNjFxLnk r3LmdDuHJpZa+spCEJ0vr0cYDhh3IGz0OZTqy4tDowxGloUTca4/fLMuMGI7Z90fPpWv c1/Q== X-Gm-Message-State: AOAM531VK6iWkv7jAlcdNGb0Z1dlA0QMpCIe/zgNHdj6KVnTv2pocze3 MDHHf1gDMAuSMQPVUDSZws4LWQ== X-Google-Smtp-Source: ABdhPJz+hhPrO4ASZm8xIfr0RBZXoP0fKejNw/uophfoawgKI0z5ihoPC1XTHuk4e++P9Qu1pTKs6w== X-Received: by 2002:a17:902:e481:b0:15c:dc24:64e8 with SMTP id i1-20020a170902e48100b0015cdc2464e8mr14927557ple.35.1650907594515; Mon, 25 Apr 2022 10:26:34 -0700 (PDT) Received: from [10.0.17.150] ([12.3.194.138]) by smtp.gmail.com with ESMTPSA id s3-20020a056a00194300b004f6da3a1a3bsm13430721pfk.8.2022.04.25.10.26.33 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 25 Apr 2022 10:26:33 -0700 (PDT) Message-ID: Date: Mon, 25 Apr 2022 10:26:32 -0700 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.7.0 Subject: Re: [PATCH 0/4] RISCV: Improve linker time complexity Content-Language: en-US To: Palmer Dabbelt , binutils@sourceware.org Cc: Kito Cheng , gnu-toolchain@rivosinc.com References: From: Patrick O'Neill In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-7.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP 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, 25 Apr 2022 17:26:37 -0000 On 4/13/22 11:11, Palmer Dabbelt wrote: > On Tue, 12 Apr 2022 22:12:22 PDT (-0700), binutils@sourceware.org wrote: >> On Wed, Apr 13, 2022 at 08:58:38AM +0800, Kito Cheng via Binutils wrote: >>> And I have a suggestion here is - does it possible to let co-exist >>> with current >>> implementation and having a command line option to select the linker >>> relaxation, of course we >>> could default to using the new implementation, but that gives us an >>> emergency fallback option to use the old implementation :) >> >> You already have an emergency fallback, use an older binutils or >> revert the patchset.  IMO you do not want two implementations of any >> given feature.   Doing so just makes it more likely that neither >> implementation is good. > > IMO a key point here is that the hueristics are subtly different, the > linear-time algorithm will fail at both forwards and backwards targets > where relaxation enables relaxation (as opposed to just failing at the > forwards targets, like the old one did).  The theory is that there > aren't any pathological cases in the wild, but it's hard to know for > sure.  I think it should just be a few lines of code to match the old > behavior (ie, just eagerly delete instead of deferring it to after all > relocations are processed), but I'm not sure -- the change around > alignment handling is tripping me up, as that was unexpected on my end. > > That said, there's certainly enough complexity here so I don't think > it's a big deal to just only support the new flavor. If we're only concerned about the backwards targets then it should be relatively easy to have it evaluate the relaxation deletions immediately. There's a challenge in that the current method expects all deletions to occur one after another with a running tally of deleted bytes. This causes issues when a deletion depends on a later deletion to clear up any slack introduced. To solve this, I think it'd be 2 if statements. One to delete immediately, and one to not depend on a running tally when deleting immediately. Regarding the change to alignment/reordered passes, those changes just defer the deletions related to alignment to one pass at the end. Other than concerns around correctness, I don't see a reason to keep the old flavor of alignment around. The old flavor has O(n^2) time complexity and doesn't change the underlying behavior.