cirros-testvm/src-cirros/buildroot-2015.05/package/binutils/2.24/910-xtensa-optimize-trampolines-relaxation.patch

   1 From cbe53e134d4c3a656880a906738ce19fdcd38e8b Mon Sep 17 00:00:00 2001
   2 From: Max Filippov <jcmvbkbc@gmail.com>
   3 Date: Fri, 1 May 2015 11:39:12 +0300
   4 Subject: [PATCH] xtensa: optimize trampolines relaxation
   5
   6 Currently every fixup in the current segment is checked when relaxing
   7 trampoline frag. This is very expensive. Make a searchable array of
   8 fixups pointing at potentially oversized jumps at the beginning of every
   9 relaxation pass and only check subset of this cache in the reach of
  10 single jump from the trampoline frag currently being relaxed.
  11
  12 Original profile:
  13
  14 % time    self  children    called     name
  15 -----------------------------------------
  16         370.16  593.38 12283048/12283048     relax_segment
  17   98.4  370.16  593.38 12283048         xtensa_relax_frag
  18          58.91  269.26 2691463834/2699602236     xtensa_insnbuf_from_chars
  19          68.35   68.17 811266668/813338977     S_GET_VALUE
  20          36.85   29.51 2684369246/2685538060     xtensa_opcode_decode
  21          28.34    8.84 2684369246/2685538060     xtensa_format_get_slot
  22          12.39    5.94 2691463834/2699775044     xtensa_format_decode
  23           0.03    4.60 4101109/4101109     relax_frag_for_align
  24           0.18    1.76  994617/994617      relax_frag_immed
  25           0.07    0.09 24556277/24851220     new_logical_line
  26           0.06    0.00 12283048/14067410     as_where
  27           0.04    0.00 7094588/15460506     xtensa_format_num_slots
  28           0.00    0.00       1/712477      xtensa_insnbuf_alloc
  29 -----------------------------------------
  30
  31 Same data, after optimization:
  32
  33 % time    self  children    called     name
  34 -----------------------------------------
  35           0.51    7.47 12283048/12283048     relax_segment
  36   58.0    0.51    7.47 12283048         xtensa_relax_frag
  37           0.02    4.08 4101109/4101109     relax_frag_for_align
  38           0.18    1.39  994617/994617      relax_frag_immed
  39           0.01    0.98     555/555         xtensa_cache_relaxable_fixups
  40           0.21    0.25 7094588/16693271     xtensa_insnbuf_from_chars
  41           0.06    0.12 24556277/24851220     new_logical_line
  42           0.06    0.00 7094588/15460506     xtensa_format_num_slots
  43           0.02    0.04 7094588/16866079     xtensa_format_decode
  44           0.05    0.00 12283048/14067410     as_where
  45           0.00    0.00       1/712477      xtensa_insnbuf_alloc
  46           0.00    0.00   93808/93808       xtensa_find_first_cached_fixup
  47 -----------------------------------------
  48
  49 2015-05-02  Max Filippov  <jcmvbkbc@gmail.com>
  50 gas/
  51         * config/tc-xtensa.c (cached_fixupS, fixup_cacheS): New typedefs.
  52         (struct cached_fixup, struct fixup_cache): New structures.
  53         (fixup_order, xtensa_make_cached_fixup),
  54         (xtensa_realloc_fixup_cache, xtensa_cache_relaxable_fixups),
  55         (xtensa_find_first_cached_fixup, xtensa_delete_cached_fixup),
  56         (xtensa_add_cached_fixup): New functions.
  57         (xtensa_relax_frag): Cache fixups pointing at potentially
  58         oversized jumps at the beginning of every relaxation pass. Only
  59         check subset of this cache in the reach of single jump from the
  60         trampoline frag currently being relaxed.
  61
  62 Signed-off-by: Max Filippov <jcmvbkbc@gmail.com>
  63 ---
  64 Backported from: b76f99d702c3501ac320396ea06bc7f9237173c3
  65 Changes to ChangeLog are dropped.
  66
  67  gas/config/tc-xtensa.c | 220 +++++++++++++++++++++++++++++++++++++++++++------
  68  1 file changed, 194 insertions(+), 26 deletions(-)
  69
  70 diff --git a/gas/config/tc-xtensa.c b/gas/config/tc-xtensa.c
  71 index 3e85b69..31c0b6b 100644
  72 --- a/gas/config/tc-xtensa.c
  73 +++ b/gas/config/tc-xtensa.c
  74 @@ -8785,6 +8785,154 @@ static long relax_frag_for_align (fragS *, long);
  75  static long relax_frag_immed
  76    (segT, fragS *, long, int, xtensa_format, int, int *, bfd_boolean);
  77
  78 +typedef struct cached_fixup cached_fixupS;
  79 +struct cached_fixup
  80 +{
  81 +  int addr;
  82 +  int target;
  83 +  int delta;
  84 +  fixS *fixP;
  85 +};
  86 +
  87 +typedef struct fixup_cache fixup_cacheS;
  88 +struct fixup_cache
  89 +{
  90 +  cached_fixupS *fixups;
  91 +  unsigned n_fixups;
  92 +  unsigned n_max;
  93 +
  94 +  segT seg;
  95 +  fragS *first_frag;
  96 +};
  97 +
  98 +static int fixup_order (const void *a, const void *b)
  99 +{
 100 +  const cached_fixupS *pa = a;
 101 +  const cached_fixupS *pb = b;
 102 +
 103 +  if (pa->addr == pb->addr)
 104 +    {
 105 +      if (pa->target == pb->target)
 106 +       {
 107 +         if (pa->fixP->fx_r_type == pb->fixP->fx_r_type)
 108 +           return 0;
 109 +         return pa->fixP->fx_r_type < pb->fixP->fx_r_type ?  -1 : 1;
 110 +       }
 111 +      return pa->target - pb->target;
 112 +    }
 113 +  return pa->addr - pb->addr;
 114 +}
 115 +
 116 +static bfd_boolean xtensa_make_cached_fixup (cached_fixupS *o, fixS *fixP)
 117 +{
 118 +  xtensa_isa isa = xtensa_default_isa;
 119 +  int addr = fixP->fx_frag->fr_address;
 120 +  int target;
 121 +  int delta;
 122 +  symbolS *s = fixP->fx_addsy;
 123 +  int slot;
 124 +  xtensa_format fmt;
 125 +  xtensa_opcode opcode;
 126 +
 127 +  if (fixP->fx_r_type < BFD_RELOC_XTENSA_SLOT0_OP ||
 128 +      fixP->fx_r_type > BFD_RELOC_XTENSA_SLOT14_OP)
 129 +    return FALSE;
 130 +  target = S_GET_VALUE (s);
 131 +  delta = target - addr;
 132 +
 133 +  if (abs(delta) < J_RANGE / 2)
 134 +    return FALSE;
 135 +
 136 +  xtensa_insnbuf_from_chars (isa, trampoline_buf,
 137 +                            (unsigned char *) fixP->fx_frag->fr_literal +
 138 +                            fixP->fx_where, 0);
 139 +  fmt = xtensa_format_decode (isa, trampoline_buf);
 140 +  gas_assert (fmt != XTENSA_UNDEFINED);
 141 +  slot = fixP->tc_fix_data.slot;
 142 +  xtensa_format_get_slot (isa, fmt, slot, trampoline_buf, trampoline_slotbuf);
 143 +  opcode = xtensa_opcode_decode (isa, fmt, slot, trampoline_slotbuf);
 144 +  if (opcode != xtensa_j_opcode)
 145 +    return FALSE;
 146 +
 147 +  o->addr = addr;
 148 +  o->target = target;
 149 +  o->delta = delta;
 150 +  o->fixP = fixP;
 151 +
 152 +  return TRUE;
 153 +}
 154 +
 155 +static void xtensa_realloc_fixup_cache (fixup_cacheS *cache, unsigned add)
 156 +{
 157 +  if (cache->n_fixups + add > cache->n_max)
 158 +    {
 159 +      cache->n_max = (cache->n_fixups + add) * 2;
 160 +      cache->fixups = xrealloc (cache->fixups,
 161 +                               sizeof (*cache->fixups) * cache->n_max);
 162 +    }
 163 +}
 164 +
 165 +static void xtensa_cache_relaxable_fixups (fixup_cacheS *cache,
 166 +                                          segment_info_type *seginfo)
 167 +{
 168 +  fixS *fixP;
 169 +
 170 +  cache->n_fixups = 0;
 171 +
 172 +  for (fixP = seginfo->fix_root; fixP ; fixP = fixP->fx_next)
 173 +    {
 174 +      xtensa_realloc_fixup_cache (cache, 1);
 175 +
 176 +      if (xtensa_make_cached_fixup (cache->fixups + cache->n_fixups, fixP))
 177 +       ++cache->n_fixups;
 178 +    }
 179 +  qsort (cache->fixups, cache->n_fixups, sizeof (*cache->fixups), fixup_order);
 180 +}
 181 +
 182 +static unsigned xtensa_find_first_cached_fixup (const fixup_cacheS *cache,
 183 +                                               int addr)
 184 +{
 185 +  unsigned a = 0;
 186 +  unsigned b = cache->n_fixups;
 187 +
 188 +  while (b - a > 1)
 189 +    {
 190 +      unsigned c = (a + b) / 2;
 191 +
 192 +      if (cache->fixups[c].addr < addr)
 193 +       a = c;
 194 +      else
 195 +       b = c;
 196 +    }
 197 +  return a;
 198 +}
 199 +
 200 +static void xtensa_delete_cached_fixup (fixup_cacheS *cache, unsigned i)
 201 +{
 202 +  memmove (cache->fixups + i, cache->fixups + i + 1,
 203 +          (cache->n_fixups - i - 1) * sizeof (*cache->fixups));
 204 +  --cache->n_fixups;
 205 +}
 206 +
 207 +static bfd_boolean xtensa_add_cached_fixup (fixup_cacheS *cache, fixS *fixP)
 208 +{
 209 +  cached_fixupS o;
 210 +  unsigned i;
 211 +
 212 +  if (!xtensa_make_cached_fixup (&o, fixP))
 213 +    return FALSE;
 214 +  xtensa_realloc_fixup_cache (cache, 1);
 215 +  i = xtensa_find_first_cached_fixup (cache, o.addr);
 216 +  if (i < cache->n_fixups)
 217 +    {
 218 +      ++i;
 219 +      memmove (cache->fixups + i + 1, cache->fixups + i,
 220 +              (cache->n_fixups - i) * sizeof (*cache->fixups));
 221 +    }
 222 +  cache->fixups[i] = o;
 223 +  ++cache->n_fixups;
 224 +  return TRUE;
 225 +}
 226
 227  /* Return the number of bytes added to this fragment, given that the
 228     input has been stretched already by "stretch".  */
 229 @@ -8896,35 +9044,42 @@ xtensa_relax_frag (fragS *fragP, long stretch, int *stretched_p)
 230      case RELAX_TRAMPOLINE:
 231        if (fragP->tc_frag_data.relax_seen)
 232          {
 233 -          segment_info_type *seginfo = seg_info (now_seg);
 234 -          fragS *fP; /* The out-of-range jump.  */
 235 -          fixS *fixP;
 236 +         static fixup_cacheS fixup_cache;
 237 +         segment_info_type *seginfo = seg_info (now_seg);
 238 +         int trampaddr = fragP->fr_address + fragP->fr_fix;
 239 +         int searchaddr = trampaddr < J_RANGE ? 0 : trampaddr - J_RANGE;
 240 +         unsigned i;
 241 +
 242 +         if (now_seg != fixup_cache.seg ||
 243 +             fragP == fixup_cache.first_frag ||
 244 +             fixup_cache.first_frag == NULL)
 245 +           {
 246 +             xtensa_cache_relaxable_fixups (&fixup_cache, seginfo);
 247 +             fixup_cache.seg = now_seg;
 248 +             fixup_cache.first_frag = fragP;
 249 +           }
 250
 251            /* Scan for jumps that will not reach.  */
 252 -          for (fixP = seginfo->fix_root; fixP ; fixP = fixP->fx_next)
 253 +          for (i = xtensa_find_first_cached_fixup (&fixup_cache, searchaddr);
 254 +              i < fixup_cache.n_fixups; ++i)
 255 +
 256              {
 257 -              symbolS *s = fixP->fx_addsy;
 258 -             xtensa_opcode opcode;
 259 -              int target;
 260 -              int addr;
 261 -              int delta;
 262 -
 263 -              if (fixP->fx_r_type < BFD_RELOC_XTENSA_SLOT0_OP ||
 264 -                  fixP->fx_r_type > BFD_RELOC_XTENSA_SLOT14_OP)
 265 -                continue;
 266 -             xtensa_insnbuf_from_chars (isa, trampoline_buf,
 267 -                                        (unsigned char *) fixP->fx_frag->fr_literal + fixP->fx_where,
 268 -                                        0);
 269 -             fmt = xtensa_format_decode (isa, trampoline_buf);
 270 -             gas_assert (fmt != XTENSA_UNDEFINED);
 271 -             slot = fixP->tc_fix_data.slot;
 272 -             xtensa_format_get_slot (isa, fmt, slot, trampoline_buf, trampoline_slotbuf);
 273 -             opcode = xtensa_opcode_decode (isa, fmt, slot, trampoline_slotbuf);
 274 -             if (opcode != xtensa_j_opcode)
 275 +             fixS *fixP = fixup_cache.fixups[i].fixP;
 276 +             int target = fixup_cache.fixups[i].target;
 277 +             int addr = fixup_cache.fixups[i].addr;
 278 +             int delta = fixup_cache.fixups[i].delta + stretch;
 279 +
 280 +             trampaddr = fragP->fr_address + fragP->fr_fix;
 281 +
 282 +             if (addr + J_RANGE < trampaddr)
 283                 continue;
 284 -              target = S_GET_VALUE (s);
 285 -              addr = fixP->fx_frag->fr_address;
 286 -              delta = target - addr + stretch;
 287 +             if (addr > trampaddr + J_RANGE)
 288 +               break;
 289 +             if (abs (delta) < J_RANGE)
 290 +               continue;
 291 +
 292 +             slot = fixP->tc_fix_data.slot;
 293 +
 294                if (delta > J_RANGE  || delta < -1 * J_RANGE)
 295                  { /* Found an out-of-range jump; scan the list of trampolines for the best match.  */
 296                   struct trampoline_seg *ts = find_trampoline_seg (now_seg);
 297 @@ -8978,14 +9133,13 @@ xtensa_relax_frag (fragS *fragP, long stretch, int *stretched_p)
 298                     }
 299                   if (tf->fragP == fragP)
 300                     {
 301 -                     int trampaddr = fragP->fr_address + fragP->fr_fix;
 302 -
 303                       if (abs (addr - trampaddr) < J_RANGE)
 304                         { /* The trampoline is in range of original; fix it!  */
 305                           fixS *newfixP;
 306                           int offset;
 307                           TInsn insn;
 308                           symbolS *lsym;
 309 +                         fragS *fP; /* The out-of-range jump.  */
 310
 311                           new_stretch += init_trampoline_frag (tf);
 312                           offset = fragP->fr_fix; /* Where to assemble the j insn.  */
 313 @@ -9009,10 +9163,20 @@ xtensa_relax_frag (fragS *fragP, long stretch, int *stretched_p)
 314                           newfixP->tc_fix_data.X_add_symbol = lsym;
 315                           newfixP->tc_fix_data.X_add_number = offset;
 316                           newfixP->tc_fix_data.slot = slot;
 317 +
 318 +                         xtensa_delete_cached_fixup (&fixup_cache, i);
 319 +                         xtensa_add_cached_fixup (&fixup_cache, newfixP);
 320 +
 321                           /* Move the fix-up from the original j insn to this one.  */
 322                           fixP->fx_frag = fragP;
 323                           fixP->fx_where = fragP->fr_fix - 3;
 324                           fixP->tc_fix_data.slot = 0;
 325 +
 326 +                         xtensa_add_cached_fixup (&fixup_cache, fixP);
 327 +
 328 +                         /* re-do current fixup */
 329 +                         --i;
 330 +
 331                           /* Adjust the jump around this trampoline (if present).  */
 332                           if (tf->fixP != NULL)
 333                             {
 334 @@ -9027,6 +9191,8 @@ xtensa_relax_frag (fragS *fragP, long stretch, int *stretched_p)
 335                               fragP->fr_subtype = 0;
 336                               /* Remove from the trampoline_list.  */
 337                               prev->next = tf->next;
 338 +                             if (fragP == fixup_cache.first_frag)
 339 +                               fixup_cache.first_frag = NULL;
 340                               break;
 341                             }
 342                         }
 343 --
 344 1.8.1.4
 345