From 38c3873e5d53902cf9cc73a4a5a05adf371296a6 Mon Sep 17 00:00:00 2001 From: Alexandre Oliva Date: Sat, 13 Apr 2019 05:55:34 -0300 Subject: [PATCH] Speed up locview resolution with relaxable frags 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. This patch enables 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. This enables most view number expressions to be resolved with a small, reasonable depth. PR gas/24444 * frags.c (frag_gtoffset_p): New. * frags.h (frag_gtoffset_p): Declare it. * expr.c (resolve_expression): Use it. --- gas/ChangeLog | 8 ++++++++ gas/expr.c | 5 ++++- gas/frags.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++ gas/frags.h | 2 ++ 4 files changed, 69 insertions(+), 1 deletion(-) diff --git a/gas/ChangeLog b/gas/ChangeLog index eeabe0ccaed..8558ecd7b48 100644 --- a/gas/ChangeLog +++ b/gas/ChangeLog @@ -1,3 +1,11 @@ +2019-04-25 Alexandre Oliva + Alan Modra + + PR gas/24444 + * frags.c (frag_gtoffset_p): New. + * frags.h (frag_gtoffset_p): Declare it. + * expr.c (resolve_expression): Use it. + 2019-04-24 Alan Modra PR 24444 diff --git a/gas/expr.c b/gas/expr.c index ee85bda1cc6..3efde88cc0a 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 a9fc003fbdf..2f21b9db200 100644 --- a/gas/frags.c +++ b/gas/frags.c @@ -462,3 +462,58 @@ frag_offset_fixed_p (const fragS *frag1, const fragS *frag2, offsetT *offset) return FALSE; } + +/* 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 > 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. */ + 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; + } + /* If we run off the end of the frag chain then we have a case + where frag2 is not after frag1, ie. an O_gt expression not + created for .loc view. */ + if (frag == NULL) + return FALSE; + } + + *offset = (off2 - off1 - delta) * OCTETS_PER_BYTE; + return TRUE; +} diff --git a/gas/frags.h b/gas/frags.h index 741ae2ba221..6d84aaab3f6 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); -- 2.30.2