From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 85743 invoked by alias); 14 Apr 2019 13:22:57 -0000 Mailing-List: contact binutils-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: binutils-owner@sourceware.org Received: (qmail 85440 invoked by uid 89); 14 Apr 2019 13:22:57 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-21.8 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=threw, whereas, param, finding X-HELO: mail-pf1-f173.google.com Received: from mail-pf1-f173.google.com (HELO mail-pf1-f173.google.com) (209.85.210.173) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 14 Apr 2019 13:22:54 +0000 Received: by mail-pf1-f173.google.com with SMTP id w25so7278555pfi.9 for ; Sun, 14 Apr 2019 06:22:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=D9EHI3gTtYWpTbm8zjwgOc8w7r4TaWS+fl+G4d1ngPM=; b=WpCc/2Ss2a/DVg6NGBMHMU56pqxl5vTnzYUezbdcuQla3u/i71iU3L3OKr4XZQLHO9 xZX/xX/PDPdL7W/XdpQJhYopdABSEbdGGgQb4WhudNzMEcH/2lmWHsQsuRk/r0rSUQzk aRCrpj7bmgqtgK9Hsmn6kSx+3rghc2xyF8CSO9BAjDabauC0lSKaptwcqg0jS62w/gNc XKpZJN6SxSZqAsootiIBsUHjnEqaGsXTR4znc+2J/6psL6EGPmZPZxG9ApvYODfpqoWp OKrbBS6kWCFlA/+jUk3hG+KgoRXtO5sUftivM3a26+xHzUwhukz3PrY65PAP/mk6SO3A ct1w== Return-Path: Received: from bubble.grove.modra.org (15.193.233.220.static.exetel.com.au. [220.233.193.15]) by smtp.gmail.com with ESMTPSA id l26sm70927364pfb.20.2019.04.14.06.22.51 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sun, 14 Apr 2019 06:22:52 -0700 (PDT) Received: by bubble.grove.modra.org (Postfix, from userid 1000) id A3BE28049B; Sun, 14 Apr 2019 22:52:47 +0930 (ACST) Date: Sun, 14 Apr 2019 13:22:00 -0000 From: Alan Modra To: Alexandre Oliva Cc: binutils@sourceware.org Subject: Re: [PR24444] speed up locview resolution wiht relaxable frags Message-ID: <20190414132247.GO14424@bubble.grove.modra.org> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.9.4 (2018-02-28) X-IsSubscribed: yes X-SW-Source: 2019-04/txt/msg00168.txt.bz2 On Sat, Apr 13, 2019 at 05:55:34AM -0300, Alexandre Oliva wrote: > > Targets such as xtensa incur a much higher overhead to resolve > location view numbers than e.g. x86, because the expressions used to > compute view numbers cannot be resolved soon enough. > > Each view number is computed by incrementing the previous view, if > they are both at the same address, or by resetting it to zero > otherwise. If PV is the previous view number, PL is its location, and > NL is the location of the next view, its number is computed by > evaluating NV = !(NL > PL) * (PV + 1). > > set_or_check_view uses resolve_expression to decide whether portions > of this expression can be simplified to constants. The (NL > PL) > subexpression is one that can often be resolved to a constant, > breaking chains of view number computations at instructions of nonzero > length, but not after alignment that might be unnecessary. > > Alas, when nearly every frag ends with a relaxable instruction, > frag_offset_fixed_p will correctly fail to determine a known offset > between two unresolved addresses in neighboring frags, so the > unresolved symbolic operation will be constructed and used in the > computation of most view numbers. This results in very deep > expressions. > > As view numbers get referenced in location view lists, each operand in > the list goes through symbol_clone_if_forward_ref, which recurses on > every subexpression. If each view number were to be referenced, this > would exhibit O(n^2) behavior, where n is the depth of the view number > expressions, i.e., the length of view number sequences without an > early resolution that cuts the expression short. > > I see two ways to go about this: > > - make forward_ref a tri-state, so that symbol_clone_if_forward_ref > can avoid revisiting the same nodes over and over when they have > already been visited and the conclusion was that their expression does > not contain forward refs. This doesn't work. I threw together a quick patch when I saw this bug report and the result was a reduction in gas run-time from 89 to 80 minutes on the testcase in the PR. The problem is simply the depth of the expressions.. > - enable address compares used by view numbering to be resolved even > when exact offsets are not known, using new logic to determine when > the location either remained the same or changed for sure, even with > the possibility of relaxation. Whereas this approach does in fact result in shorter expressions, reducing run-time to 3 seconds. > This patch implements the latter, assuming fr_fix to be the minimum > size the frag will end up with, even for machine-dependent frags, but > not rs_org: for those, or for negative fr_fix, it conservatively > refrains from resolving the expression. This enables most view number > expressions to be resolved with a small, reasonable depth. > > Now, is the assumption on fr_fix a reasonable one to make across all > supported targets? Yes, I believe so. In fact, fr_fix is really unsigned. Also, it is an error for rs_org frags to go backwards. > Tested on x86_64-linux-gnu, native and cross to xtensa-elf. No new > testcase; the issue was just performance, not output correctness. Ok to > install? Um, the testcase object file after this patch differs from the original. First readelf -wi difference shown below. @@ -109941,7 +109941,7 @@ <2><3e4f6>: Abbrev Number: 8 (DW_TAG_inlined_subroutine) <3e4f7> DW_AT_abstract_origin: <0x2e531> <3e4fb> DW_AT_entry_pc : 0x2a - <3e4ff> DW_AT_GNU_entry_view: 9 + <3e4ff> DW_AT_GNU_entry_view: 2 <3e501> DW_AT_low_pc : 0x2a <3e505> DW_AT_high_pc : 0x0 <3e509> DW_AT_call_file : 3 > > > for gas/ChangeLog > > PR gas/24444 > * frags.c (frag_gtoffset_p): New. > * frags.h (frag_gtoffset_p): Declare it. > * expr.c (resolve_expression): Use it. > --- > gas/expr.c | 5 +++- > gas/frags.c | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > gas/frags.h | 2 ++ > 3 files changed, 80 insertions(+), 1 deletion(-) > > diff --git a/gas/expr.c b/gas/expr.c > index ee85bda1cc60..3efde88cc0a2 100644 > --- a/gas/expr.c > +++ b/gas/expr.c > @@ -2179,7 +2179,10 @@ resolve_expression (expressionS *expressionP) > || op == O_lt || op == O_le || op == O_ge || op == O_gt) > && seg_left == seg_right > && (finalize_syms > - || frag_offset_fixed_p (frag_left, frag_right, &frag_off)) > + || frag_offset_fixed_p (frag_left, frag_right, &frag_off) > + || (op == O_gt > + && frag_gtoffset_p (left, frag_left, > + right, frag_right, &frag_off))) > && (seg_left != reg_section || left == right) > && (seg_left != undefined_section || add_symbol == op_symbol))) > { > diff --git a/gas/frags.c b/gas/frags.c > index 90096ff696d7..e2ff79fbcc04 100644 > --- a/gas/frags.c > +++ b/gas/frags.c > @@ -460,3 +460,77 @@ frag_offset_fixed_p (const fragS *frag1, const fragS *frag2, offsetT *offset) > > return FALSE; > } > + > +/* Return TRUE if we can determine whether FRAG1 OFF1 appears after > + (strict >, not >=) FRAG2 OFF2, assuming it is not before. Set > + *OFFSET so that resolve_expression will resolve an O_gt operation > + between them to false (0) if they are guaranteed to be at the same > + location, or to true (-1) if they are guaranteed to be at different > + locations. Return FALSE conservatively, e.g. if neither result can > + be guaranteed (yet). > + > + They are known to be in the same segment, and not the same frag > + (this is a fallback for frag_offset_fixed_p, that always takes care > + of this case), and it is expected (from the uses this is designed > + to simplify, namely location view increments) that frag1 is > + reachable from frag2 following the fr_next links, rather than the > + other way round. */ For the sake of anyone reading this code, please swap the param names, with frag1/off1 being the first in the frag chain. > + > +bfd_boolean > +frag_gtoffset_p (valueT off1, const fragS *frag1, > + valueT off2, const fragS *frag2, offsetT *offset) > +{ > + if (frag1 == frag2 || off2 > (valueT)frag2->fr_fix) > + return FALSE; > + > + /* If any frag from frag2, inclusive, to frag1, exclusive, has a > + nonzero fixed length, the addresses won't be the same as long as > + we reach frag1. */ > + bfd_boolean maybe_same_addr = off1 == 0 && off2 == (valueT)frag2->fr_fix; Ins't it true that if the symbol offsets are not at exactly the above values, then you already know the result and there's no need to traverse the frags? This is assuming you can't .org backwards, which is the case. > + bfd_boolean found_varlength = FALSE; > + const fragS *frag = frag2; > + for (;;) > + { > + switch (frag->fr_type) > + { > + case rs_dummy: > + break; > + > + case rs_fill: > + case rs_align: > + case rs_align_code: > + case rs_align_test: > + case rs_space: > + case rs_space_nop: > + case rs_fill_nop: > + case rs_leb128: > + case rs_cfa: > + case rs_dwarf2dbg: > + case rs_machine_dependent: > + found_varlength = TRUE; > + break; > + > + default: > + /* case rs_broken_word: */ > + case rs_org: > + return FALSE; > + } > + > + frag = frag->fr_next; > + if (frag == frag1 || !frag) > + break; > + if (maybe_same_addr && frag->fr_fix > 0) > + maybe_same_addr = FALSE; > + if (frag->fr_fix < 0) > + return FALSE; > + } > + > + /* If both are TRUE, we don't know whether or not it will resolve to > + the same address. */ > + if (maybe_same_addr && found_varlength) > + return FALSE; > + > + if (frag) > + *offset = (off1 - off2 - !maybe_same_addr) * OCTETS_PER_BYTE; > + return !!frag; > +} > diff --git a/gas/frags.h b/gas/frags.h > index 6ac5d4426c79..9eb066229085 100644 > --- a/gas/frags.h > +++ b/gas/frags.h > @@ -154,6 +154,8 @@ char *frag_var (relax_stateT type, > char *opcode); > > bfd_boolean frag_offset_fixed_p (const fragS *, const fragS *, offsetT *); > +bfd_boolean frag_gtoffset_p (valueT, const fragS *, valueT, const fragS *, > + offsetT *); > > int get_frag_count (void); > void clear_frag_count (void); The following makes the changes I'm suggesting, and simplifies a few more things. The object file for the testcase is the same as with your patch. /* Return TRUE if we can determine whether FRAG2 OFF2 appears after (strict >, not >=) FRAG1 OFF1, assuming it is not before. Set *OFFSET so that resolve_expression will resolve an O_gt operation between them to false (0) if they are guaranteed to be at the same location, or to true (-1) if they are guaranteed to be at different locations. Return FALSE conservatively, e.g. if neither result can be guaranteed (yet). They are known to be in the same segment, and not the same frag (this is a fallback for frag_offset_fixed_p, that always takes care of this case), and it is expected (from the uses this is designed to simplify, namely location view increments) that frag2 is reachable from frag1 following the fr_next links, rather than the other way round. */ bfd_boolean frag_gtoffset_p (valueT off2, const fragS *frag2, valueT off1, const fragS *frag1, offsetT *offset) { /* Insanity check. */ if (frag2 == frag1 || off1 > (valueT) frag1->fr_fix) return FALSE; /* If the first symbol offset is at the end of the first frag and the second symbol offset at the beginning of the second frag then it is possible they are at the same address. Go looking for a non-zero fr_fix in any frag between these frags. If found then we can say the O_gt result will be true. If no such frag is found we assume that frag1 or any of the following frags might have a variable tail and thus the answer is unknown. This isn't strictly true; some frags don't have a variable tail, but it doesn't seem worth optimizing for those cases. We could omit the loop on off1 != frag1->fr_fix || off2 != 0 and exit the loop on finding a non-zero fr_fix, but loop until we hit frag2 to check our assumptions. */ const fragS *frag = frag1; offsetT delta = off2 - off1; for (;;) { delta += frag->fr_fix; frag = frag->fr_next; if (frag == frag2) { if (delta == 0) return FALSE; break; } /* Insanity check. */ if (frag == NULL) return FALSE; } *offset = (off2 - off1 - 1) * OCTETS_PER_BYTE; return TRUE; } -- Alan Modra Australia Development Lab, IBM