cirros-testvm/src-cirros/buildroot-2015.05/package/binutils/2.25/909-xtensa-replace-action-list-with-splay-tree.patch

   1 From e5409aedd3ee2192855018a564650ffb75c26e60 Mon Sep 17 00:00:00 2001
   2 From: Max Filippov <jcmvbkbc@gmail.com>
   3 Date: Sun, 5 Apr 2015 17:04:22 +0300
   4 Subject: [PATCH 4/4] xtensa: replace action list with splay tree
   5
   6 text_action_add uses linear list search to order text actions list by
   7 action VMA. The list is used at the first relaxation pass, when it's not
   8 fixed yet.
   9 Replace the list with splay tree from libiberty.
  10
  11 Original profile:
  12
  13 % time    self  children    called     name
  14 -----------------------------------------
  15           0.00    0.00      14/158225      compute_text_actions
  16           3.62    0.00   25211/158225      remove_dead_literal
  17           8.42    0.00   58645/158225      coalesce_shared_literal
  18          10.68    0.00   74355/158225      text_action_add_proposed
  19   38.8   22.73    0.00  158225         text_action_add
  20           0.00    0.00  144527/293246      bfd_zmalloc
  21 -----------------------------------------
  22
  23 Same data, after optimization:
  24
  25 % time    self  children    called     name
  26 -----------------------------------------
  27           0.00    0.00      14/158225      compute_text_actions
  28           0.00    0.00   25211/158225      remove_dead_literal
  29           0.00    0.01   58645/158225      coalesce_shared_literal
  30           0.00    0.01   74355/158225      text_action_add_proposed
  31    0.1    0.00    0.02  158225         text_action_add
  32           0.01    0.00  144527/144527      splay_tree_insert
  33           0.00    0.00  144527/195130      splay_tree_lookup
  34           0.00    0.00  144527/293246      bfd_zmalloc
  35 -----------------------------------------
  36
  37 2015-04-03  Max Filippov  <jcmvbkbc@gmail.com>
  38 bfd/
  39         * elf32-xtensa.c (splay-tree.h): include header.
  40         (text_action_struct): drop next pointer.
  41         (text_action_list_struct): drop head pointer, add count and
  42         tree fields.
  43         (find_fill_action): instead of linear search in text_action_list
  44         search in the tree.
  45         (text_action_compare, action_first, action_next): new functions.
  46         (text_action_add, text_action_add_literal): instead of linear
  47         search and insertion insert new node into the tree.
  48         (removed_by_actions): pass additional parameter: action_list,
  49         use it to traverse the tree.
  50         (offset_with_removed_text): pass additional action_list parameter
  51         to removed_by_actions.
  52         (map_action_fn_context): new typedef.
  53         (map_action_fn_context_struct): new structure.
  54         (map_action_fn): new function.
  55         (map_removal_by_action): use splay_tree_foreach to build map.
  56         (find_insn_action): replace linear search in text_action_list
  57         with series of splay_tree_lookups.
  58         (print_action, print_action_list_fn): new functions.
  59         (print_action_list): use splay_tree_foreach.
  60         (init_xtensa_relax_info): drop action_list.head initialization.
  61         Initialize the tree.
  62         (compute_text_actions): use non-zero action_list_count instead of
  63         non-NULL action list.
  64         (xlate_map_context): new typedef.
  65         (xlate_map_context_struct): new structure.
  66         (xlate_map_fn): new function.
  67         (build_xlate_map): use splay_tree_foreach to build map.
  68         (action_remove_bytes_fn): new function.
  69         (relax_section): use zero action_list_count instead of NULL
  70         action list. Use splay_tree_foreach to count final section size.
  71         Drop unused variable 'removed'.
  72
  73 Backported from: 4c2af04fe8b4452bf51d2debf1bb467fafcd0f08
  74 Signed-off-by: Max Filippov <jcmvbkbc@gmail.com>
  75 ---
  76  bfd/elf32-xtensa.c | 488 +++++++++++++++++++++++++++++++----------------------
  77  1 file changed, 282 insertions(+), 206 deletions(-)
  78
  79 diff --git a/bfd/elf32-xtensa.c b/bfd/elf32-xtensa.c
  80 index 51733ad..53af1c6 100644
  81 --- a/bfd/elf32-xtensa.c
  82 +++ b/bfd/elf32-xtensa.c
  83 @@ -28,6 +28,7 @@
  84  #include "libbfd.h"
  85  #include "elf-bfd.h"
  86  #include "elf/xtensa.h"
  87 +#include "splay-tree.h"
  88  #include "xtensa-isa.h"
  89  #include "xtensa-config.h"
  90
  91 @@ -5416,8 +5417,6 @@ struct text_action_struct
  92    bfd_vma virtual_offset;  /* Zero except for adding literals.  */
  93    int removed_bytes;
  94    literal_value value; /* Only valid when adding literals.  */
  95 -
  96 -  text_action *next;
  97  };
  98
  99  struct removal_by_action_entry_struct
 100 @@ -5440,7 +5439,8 @@ typedef struct removal_by_action_map_struct removal_by_action_map;
 101  /* List of all of the actions taken on a text section.  */
 102  struct text_action_list_struct
 103  {
 104 -  text_action *head;
 105 +  unsigned count;
 106 +  splay_tree tree;
 107    removal_by_action_map map;
 108  };
 109
 110 @@ -5448,20 +5448,18 @@ struct text_action_list_struct
 111  static text_action *
 112  find_fill_action (text_action_list *l, asection *sec, bfd_vma offset)
 113  {
 114 -  text_action **m_p;
 115 +  text_action a;
 116
 117    /* It is not necessary to fill at the end of a section.  */
 118    if (sec->size == offset)
 119      return NULL;
 120
 121 -  for (m_p = &l->head; *m_p && (*m_p)->offset <= offset; m_p = &(*m_p)->next)
 122 -    {
 123 -      text_action *t = *m_p;
 124 -      /* When the action is another fill at the same address,
 125 -        just increase the size.  */
 126 -      if (t->offset == offset && t->action == ta_fill)
 127 -       return t;
 128 -    }
 129 +  a.offset = offset;
 130 +  a.action = ta_fill;
 131 +
 132 +  splay_tree_node node = splay_tree_lookup (l->tree, (splay_tree_key)&a);
 133 +  if (node)
 134 +    return (text_action *)node->value;
 135    return NULL;
 136  }
 137
 138 @@ -5509,6 +5507,49 @@ adjust_fill_action (text_action *ta, int fill_diff)
 139  }
 140
 141
 142 +static int
 143 +text_action_compare (splay_tree_key a, splay_tree_key b)
 144 +{
 145 +  text_action *pa = (text_action *)a;
 146 +  text_action *pb = (text_action *)b;
 147 +  static const int action_priority[] =
 148 +    {
 149 +      [ta_fill] = 0,
 150 +      [ta_none] = 1,
 151 +      [ta_convert_longcall] = 2,
 152 +      [ta_narrow_insn] = 3,
 153 +      [ta_remove_insn] = 4,
 154 +      [ta_remove_longcall] = 5,
 155 +      [ta_remove_literal] = 6,
 156 +      [ta_widen_insn] = 7,
 157 +      [ta_add_literal] = 8,
 158 +    };
 159 +
 160 +  if (pa->offset == pb->offset)
 161 +    {
 162 +      if (pa->action == pb->action)
 163 +         return 0;
 164 +      return action_priority[pa->action] - action_priority[pb->action];
 165 +    }
 166 +  else
 167 +    return pa->offset < pb->offset ? -1 : 1;
 168 +}
 169 +
 170 +static text_action *
 171 +action_first (text_action_list *action_list)
 172 +{
 173 +  splay_tree_node node = splay_tree_min (action_list->tree);
 174 +  return node ? (text_action *)node->value : NULL;
 175 +}
 176 +
 177 +static text_action *
 178 +action_next (text_action_list *action_list, text_action *action)
 179 +{
 180 +  splay_tree_node node = splay_tree_successor (action_list->tree,
 181 +                                              (splay_tree_key)action);
 182 +  return node ? (text_action *)node->value : NULL;
 183 +}
 184 +
 185  /* Add a modification action to the text.  For the case of adding or
 186     removing space, modify any current fill and assume that
 187     "unreachable_space" bytes can be freely contracted.  Note that a
 188 @@ -5521,8 +5562,8 @@ text_action_add (text_action_list *l,
 189                  bfd_vma offset,
 190                  int removed)
 191  {
 192 -  text_action **m_p;
 193    text_action *ta;
 194 +  text_action a;
 195
 196    /* It is not necessary to fill at the end of a section.  */
 197    if (action == ta_fill && sec->size == offset)
 198 @@ -5532,34 +5573,30 @@ text_action_add (text_action_list *l,
 199    if (action == ta_fill && removed == 0)
 200      return;
 201
 202 -  for (m_p = &l->head; *m_p && (*m_p)->offset <= offset; m_p = &(*m_p)->next)
 203 +  a.action = action;
 204 +  a.offset = offset;
 205 +
 206 +  if (action == ta_fill)
 207      {
 208 -      text_action *t = *m_p;
 209 +      splay_tree_node node = splay_tree_lookup (l->tree, (splay_tree_key)&a);
 210
 211 -      if (action == ta_fill)
 212 +      if (node)
 213         {
 214 -         /* When the action is another fill at the same address,
 215 -            just increase the size.  */
 216 -         if (t->offset == offset && t->action == ta_fill)
 217 -           {
 218 -             t->removed_bytes += removed;
 219 -             return;
 220 -           }
 221 -         /* Fills need to happen before widens so that we don't
 222 -            insert fill bytes into the instruction stream.  */
 223 -         if (t->offset == offset && t->action == ta_widen_insn)
 224 -           break;
 225 +         ta = (text_action *)node->value;
 226 +         ta->removed_bytes += removed;
 227 +         return;
 228         }
 229      }
 230 +  else
 231 +    BFD_ASSERT (splay_tree_lookup (l->tree, (splay_tree_key)&a) == NULL);
 232
 233 -  /* Create a new record and fill it up.  */
 234    ta = (text_action *) bfd_zmalloc (sizeof (text_action));
 235    ta->action = action;
 236    ta->sec = sec;
 237    ta->offset = offset;
 238    ta->removed_bytes = removed;
 239 -  ta->next = (*m_p);
 240 -  *m_p = ta;
 241 +  splay_tree_insert (l->tree, (splay_tree_key)ta, (splay_tree_value)ta);
 242 +  ++l->count;
 243  }
 244
 245
 246 @@ -5570,7 +5607,6 @@ text_action_add_literal (text_action_list *l,
 247                          const literal_value *value,
 248                          int removed)
 249  {
 250 -  text_action **m_p;
 251    text_action *ta;
 252    asection *sec = r_reloc_get_section (loc);
 253    bfd_vma offset = loc->target_offset;
 254 @@ -5578,14 +5614,6 @@ text_action_add_literal (text_action_list *l,
 255
 256    BFD_ASSERT (action == ta_add_literal);
 257
 258 -  for (m_p = &l->head; *m_p != NULL; m_p = &(*m_p)->next)
 259 -    {
 260 -      if ((*m_p)->offset > offset
 261 -         && ((*m_p)->offset != offset
 262 -             || (*m_p)->virtual_offset > virtual_offset))
 263 -       break;
 264 -    }
 265 -
 266    /* Create a new record and fill it up.  */
 267    ta = (text_action *) bfd_zmalloc (sizeof (text_action));
 268    ta->action = action;
 269 @@ -5594,8 +5622,10 @@ text_action_add_literal (text_action_list *l,
 270    ta->virtual_offset = virtual_offset;
 271    ta->value = *value;
 272    ta->removed_bytes = removed;
 273 -  ta->next = (*m_p);
 274 -  *m_p = ta;
 275 +
 276 +  BFD_ASSERT (splay_tree_lookup (l->tree, (splay_tree_key)ta) == NULL);
 277 +  splay_tree_insert (l->tree, (splay_tree_key)ta, (splay_tree_value)ta);
 278 +  ++l->count;
 279  }
 280
 281
 282 @@ -5606,7 +5636,8 @@ text_action_add_literal (text_action_list *l,
 283     so that each search may begin where the previous one left off.  */
 284
 285  static int
 286 -removed_by_actions (text_action **p_start_action,
 287 +removed_by_actions (text_action_list *action_list,
 288 +                   text_action **p_start_action,
 289                     bfd_vma offset,
 290                     bfd_boolean before_fill)
 291  {
 292 @@ -5614,6 +5645,13 @@ removed_by_actions (text_action **p_start_action,
 293    int removed = 0;
 294
 295    r = *p_start_action;
 296 +  if (r)
 297 +    {
 298 +      splay_tree_node node = splay_tree_lookup (action_list->tree,
 299 +                                               (splay_tree_key)r);
 300 +      BFD_ASSERT (node != NULL && r == (text_action *)node->value);
 301 +    }
 302 +
 303    while (r)
 304      {
 305        if (r->offset > offset)
 306 @@ -5625,7 +5663,7 @@ removed_by_actions (text_action **p_start_action,
 307
 308        removed += r->removed_bytes;
 309
 310 -      r = r->next;
 311 +      r = action_next (action_list, r);
 312      }
 313
 314    *p_start_action = r;
 315 @@ -5636,68 +5674,74 @@ removed_by_actions (text_action **p_start_action,
 316  static bfd_vma
 317  offset_with_removed_text (text_action_list *action_list, bfd_vma offset)
 318  {
 319 -  text_action *r = action_list->head;
 320 -  return offset - removed_by_actions (&r, offset, FALSE);
 321 +  text_action *r = action_first (action_list);
 322 +
 323 +  return offset - removed_by_actions (action_list, &r, offset, FALSE);
 324  }
 325
 326
 327  static unsigned
 328  action_list_count (text_action_list *action_list)
 329  {
 330 -  text_action *r = action_list->head;
 331 -  unsigned count = 0;
 332 -  for (r = action_list->head; r != NULL; r = r->next)
 333 -    {
 334 -      count++;
 335 -    }
 336 -  return count;
 337 +  return action_list->count;
 338  }
 339
 340 -static void
 341 -map_removal_by_action (text_action_list *action_list)
 342 +typedef struct map_action_fn_context_struct map_action_fn_context;
 343 +struct map_action_fn_context_struct
 344  {
 345 -  text_action *r;
 346 -  int removed = 0;
 347 +  int removed;
 348    removal_by_action_map map;
 349    bfd_boolean eq_complete;
 350 +};
 351
 352 -  map.n_entries = 0;
 353 -  map.entry = bfd_malloc (action_list_count (action_list) *
 354 -                         sizeof (removal_by_action_entry));
 355 -  eq_complete = FALSE;
 356 +static int
 357 +map_action_fn (splay_tree_node node, void *p)
 358 +{
 359 +  map_action_fn_context *ctx = p;
 360 +  text_action *r = (text_action *)node->value;
 361 +  removal_by_action_entry *ientry = ctx->map.entry + ctx->map.n_entries;
 362
 363 -  for (r = action_list->head; r;)
 364 +  if (ctx->map.n_entries && (ientry - 1)->offset == r->offset)
 365      {
 366 -      removal_by_action_entry *ientry = map.entry + map.n_entries;
 367 +      --ientry;
 368 +    }
 369 +  else
 370 +    {
 371 +      ++ctx->map.n_entries;
 372 +      ctx->eq_complete = FALSE;
 373 +      ientry->offset = r->offset;
 374 +      ientry->eq_removed_before_fill = ctx->removed;
 375 +    }
 376
 377 -      if (map.n_entries && (ientry - 1)->offset == r->offset)
 378 +  if (!ctx->eq_complete)
 379 +    {
 380 +      if (r->action != ta_fill || r->removed_bytes >= 0)
 381         {
 382 -         --ientry;
 383 +         ientry->eq_removed = ctx->removed;
 384 +         ctx->eq_complete = TRUE;
 385         }
 386        else
 387 -       {
 388 -         ++map.n_entries;
 389 -         eq_complete = FALSE;
 390 -         ientry->offset = r->offset;
 391 -         ientry->eq_removed_before_fill = removed;
 392 -       }
 393 +       ientry->eq_removed = ctx->removed + r->removed_bytes;
 394 +    }
 395
 396 -      if (!eq_complete)
 397 -       {
 398 -         if (r->action != ta_fill || r->removed_bytes >= 0)
 399 -           {
 400 -             ientry->eq_removed = removed;
 401 -             eq_complete = TRUE;
 402 -           }
 403 -         else
 404 -           ientry->eq_removed = removed + r->removed_bytes;
 405 -       }
 406 +  ctx->removed += r->removed_bytes;
 407 +  ientry->removed = ctx->removed;
 408 +  return 0;
 409 +}
 410
 411 -      removed += r->removed_bytes;
 412 -      ientry->removed = removed;
 413 -      r = r->next;
 414 -    }
 415 -  action_list->map = map;
 416 +static void
 417 +map_removal_by_action (text_action_list *action_list)
 418 +{
 419 +  map_action_fn_context ctx;
 420 +
 421 +  ctx.removed = 0;
 422 +  ctx.map.n_entries = 0;
 423 +  ctx.map.entry = bfd_malloc (action_list_count (action_list) *
 424 +                             sizeof (removal_by_action_entry));
 425 +  ctx.eq_complete = FALSE;
 426 +
 427 +  splay_tree_foreach (action_list->tree, map_action_fn, &ctx);
 428 +  action_list->map = ctx.map;
 429  }
 430
 431  static int
 432 @@ -5754,28 +5798,26 @@ offset_with_removed_text_map (text_action_list *action_list, bfd_vma offset)
 433  static text_action *
 434  find_insn_action (text_action_list *action_list, bfd_vma offset)
 435  {
 436 -  text_action *t;
 437 -  for (t = action_list->head; t; t = t->next)
 438 +  static const text_action_t action[] =
 439      {
 440 -      if (t->offset == offset)
 441 -       {
 442 -         switch (t->action)
 443 -           {
 444 -           case ta_none:
 445 -           case ta_fill:
 446 -             break;
 447 -           case ta_remove_insn:
 448 -           case ta_remove_longcall:
 449 -           case ta_convert_longcall:
 450 -           case ta_narrow_insn:
 451 -           case ta_widen_insn:
 452 -             return t;
 453 -           case ta_remove_literal:
 454 -           case ta_add_literal:
 455 -             BFD_ASSERT (0);
 456 -             break;
 457 -           }
 458 -       }
 459 +      ta_convert_longcall,
 460 +      ta_remove_longcall,
 461 +      ta_widen_insn,
 462 +      ta_narrow_insn,
 463 +      ta_remove_insn,
 464 +    };
 465 +  text_action a;
 466 +  unsigned i;
 467 +
 468 +  a.offset = offset;
 469 +  for (i = 0; i < sizeof (action) / sizeof (*action); ++i)
 470 +    {
 471 +      splay_tree_node node;
 472 +
 473 +      a.action = action[i];
 474 +      node = splay_tree_lookup (action_list->tree, (splay_tree_key)&a);
 475 +      if (node)
 476 +       return (text_action *)node->value;
 477      }
 478    return NULL;
 479  }
 480 @@ -5784,40 +5826,50 @@ find_insn_action (text_action_list *action_list, bfd_vma offset)
 481  #if DEBUG
 482
 483  static void
 484 -print_action_list (FILE *fp, text_action_list *action_list)
 485 +print_action (FILE *fp, text_action *r)
 486 +{
 487 +  const char *t = "unknown";
 488 +  switch (r->action)
 489 +    {
 490 +    case ta_remove_insn:
 491 +      t = "remove_insn"; break;
 492 +    case ta_remove_longcall:
 493 +      t = "remove_longcall"; break;
 494 +    case ta_convert_longcall:
 495 +      t = "convert_longcall"; break;
 496 +    case ta_narrow_insn:
 497 +      t = "narrow_insn"; break;
 498 +    case ta_widen_insn:
 499 +      t = "widen_insn"; break;
 500 +    case ta_fill:
 501 +      t = "fill"; break;
 502 +    case ta_none:
 503 +      t = "none"; break;
 504 +    case ta_remove_literal:
 505 +      t = "remove_literal"; break;
 506 +    case ta_add_literal:
 507 +      t = "add_literal"; break;
 508 +    }
 509 +
 510 +  fprintf (fp, "%s: %s[0x%lx] \"%s\" %d\n",
 511 +          r->sec->owner->filename,
 512 +          r->sec->name, (unsigned long) r->offset, t, r->removed_bytes);
 513 +}
 514 +
 515 +static int
 516 +print_action_list_fn (splay_tree_node node, void *p)
 517  {
 518 -  text_action *r;
 519 +  text_action *r = (text_action *)node->value;
 520
 521 -  fprintf (fp, "Text Action\n");
 522 -  for (r = action_list->head; r != NULL; r = r->next)
 523 -    {
 524 -      const char *t = "unknown";
 525 -      switch (r->action)
 526 -       {
 527 -       case ta_remove_insn:
 528 -         t = "remove_insn"; break;
 529 -       case ta_remove_longcall:
 530 -         t = "remove_longcall"; break;
 531 -       case ta_convert_longcall:
 532 -         t = "convert_longcall"; break;
 533 -       case ta_narrow_insn:
 534 -         t = "narrow_insn"; break;
 535 -       case ta_widen_insn:
 536 -         t = "widen_insn"; break;
 537 -       case ta_fill:
 538 -         t = "fill"; break;
 539 -       case ta_none:
 540 -         t = "none"; break;
 541 -       case ta_remove_literal:
 542 -         t = "remove_literal"; break;
 543 -       case ta_add_literal:
 544 -         t = "add_literal"; break;
 545 -       }
 546 +  print_action (p, r);
 547 +  return 0;
 548 +}
 549
 550 -      fprintf (fp, "%s: %s[0x%lx] \"%s\" %d\n",
 551 -              r->sec->owner->filename,
 552 -              r->sec->name, (unsigned long) r->offset, t, r->removed_bytes);
 553 -    }
 554 +static void
 555 +print_action_list (FILE *fp, text_action_list *action_list)
 556 +{
 557 +  fprintf (fp, "Text Action\n");
 558 +  splay_tree_foreach (action_list->tree, print_action_list_fn, fp);
 559  }
 560
 561  #endif /* DEBUG */
 562 @@ -6071,8 +6123,8 @@ init_xtensa_relax_info (asection *sec)
 563    relax_info->removed_list.head = NULL;
 564    relax_info->removed_list.tail = NULL;
 565
 566 -  relax_info->action_list.head = NULL;
 567 -
 568 +  relax_info->action_list.tree = splay_tree_new (text_action_compare,
 569 +                                                NULL, NULL);
 570    relax_info->action_list.map.n_entries = 0;
 571    relax_info->action_list.map.entry = NULL;
 572
 573 @@ -7762,7 +7814,7 @@ compute_text_actions (bfd *abfd,
 574    free_reloc_range_list (&relevant_relocs);
 575
 576  #if DEBUG
 577 -  if (relax_info->action_list.head)
 578 +  if (action_list_count (&relax_info->action_list))
 579      print_action_list (stderr, &relax_info->action_list);
 580  #endif
 581
 582 @@ -8263,6 +8315,54 @@ xlate_offset_with_removed_text (const xlate_map_t *map,
 583    return e->new_address - e->orig_address + offset;
 584  }
 585
 586 +typedef struct xlate_map_context_struct xlate_map_context;
 587 +struct xlate_map_context_struct
 588 +{
 589 +  xlate_map_t *map;
 590 +  xlate_map_entry_t *current_entry;
 591 +  int removed;
 592 +};
 593 +
 594 +static int
 595 +xlate_map_fn (splay_tree_node node, void *p)
 596 +{
 597 +  text_action *r = (text_action *)node->value;
 598 +  xlate_map_context *ctx = p;
 599 +  unsigned orig_size = 0;
 600 +
 601 +  switch (r->action)
 602 +    {
 603 +    case ta_none:
 604 +    case ta_remove_insn:
 605 +    case ta_convert_longcall:
 606 +    case ta_remove_literal:
 607 +    case ta_add_literal:
 608 +      break;
 609 +    case ta_remove_longcall:
 610 +      orig_size = 6;
 611 +      break;
 612 +    case ta_narrow_insn:
 613 +      orig_size = 3;
 614 +      break;
 615 +    case ta_widen_insn:
 616 +      orig_size = 2;
 617 +      break;
 618 +    case ta_fill:
 619 +      break;
 620 +    }
 621 +  ctx->current_entry->size =
 622 +    r->offset + orig_size - ctx->current_entry->orig_address;
 623 +  if (ctx->current_entry->size != 0)
 624 +    {
 625 +      ctx->current_entry++;
 626 +      ctx->map->entry_count++;
 627 +    }
 628 +  ctx->current_entry->orig_address = r->offset + orig_size;
 629 +  ctx->removed += r->removed_bytes;
 630 +  ctx->current_entry->new_address = r->offset + orig_size - ctx->removed;
 631 +  ctx->current_entry->size = 0;
 632 +  return 0;
 633 +}
 634
 635  /* Build a binary searchable offset translation map from a section's
 636     action list.  */
 637 @@ -8270,75 +8370,40 @@ xlate_offset_with_removed_text (const xlate_map_t *map,
 638  static xlate_map_t *
 639  build_xlate_map (asection *sec, xtensa_relax_info *relax_info)
 640  {
 641 -  xlate_map_t *map = (xlate_map_t *) bfd_malloc (sizeof (xlate_map_t));
 642    text_action_list *action_list = &relax_info->action_list;
 643    unsigned num_actions = 0;
 644 -  text_action *r;
 645 -  int removed;
 646 -  xlate_map_entry_t *current_entry;
 647 +  xlate_map_context ctx;
 648
 649 -  if (map == NULL)
 650 +  ctx.map = (xlate_map_t *) bfd_malloc (sizeof (xlate_map_t));
 651 +
 652 +  if (ctx.map == NULL)
 653      return NULL;
 654
 655    num_actions = action_list_count (action_list);
 656 -  map->entry = (xlate_map_entry_t *)
 657 +  ctx.map->entry = (xlate_map_entry_t *)
 658      bfd_malloc (sizeof (xlate_map_entry_t) * (num_actions + 1));
 659 -  if (map->entry == NULL)
 660 +  if (ctx.map->entry == NULL)
 661      {
 662 -      free (map);
 663 +      free (ctx.map);
 664        return NULL;
 665      }
 666 -  map->entry_count = 0;
 667 +  ctx.map->entry_count = 0;
 668
 669 -  removed = 0;
 670 -  current_entry = &map->entry[0];
 671 +  ctx.removed = 0;
 672 +  ctx.current_entry = &ctx.map->entry[0];
 673
 674 -  current_entry->orig_address = 0;
 675 -  current_entry->new_address = 0;
 676 -  current_entry->size = 0;
 677 +  ctx.current_entry->orig_address = 0;
 678 +  ctx.current_entry->new_address = 0;
 679 +  ctx.current_entry->size = 0;
 680
 681 -  for (r = action_list->head; r != NULL; r = r->next)
 682 -    {
 683 -      unsigned orig_size = 0;
 684 -      switch (r->action)
 685 -       {
 686 -       case ta_none:
 687 -       case ta_remove_insn:
 688 -       case ta_convert_longcall:
 689 -       case ta_remove_literal:
 690 -       case ta_add_literal:
 691 -         break;
 692 -       case ta_remove_longcall:
 693 -         orig_size = 6;
 694 -         break;
 695 -       case ta_narrow_insn:
 696 -         orig_size = 3;
 697 -         break;
 698 -       case ta_widen_insn:
 699 -         orig_size = 2;
 700 -         break;
 701 -       case ta_fill:
 702 -         break;
 703 -       }
 704 -      current_entry->size =
 705 -       r->offset + orig_size - current_entry->orig_address;
 706 -      if (current_entry->size != 0)
 707 -       {
 708 -         current_entry++;
 709 -         map->entry_count++;
 710 -       }
 711 -      current_entry->orig_address = r->offset + orig_size;
 712 -      removed += r->removed_bytes;
 713 -      current_entry->new_address = r->offset + orig_size - removed;
 714 -      current_entry->size = 0;
 715 -    }
 716 +  splay_tree_foreach (action_list->tree, xlate_map_fn, &ctx);
 717
 718 -  current_entry->size = (bfd_get_section_limit (sec->owner, sec)
 719 -                        - current_entry->orig_address);
 720 -  if (current_entry->size != 0)
 721 -    map->entry_count++;
 722 +  ctx.current_entry->size = (bfd_get_section_limit (sec->owner, sec)
 723 +                            - ctx.current_entry->orig_address);
 724 +  if (ctx.current_entry->size != 0)
 725 +    ctx.map->entry_count++;
 726
 727 -  return map;
 728 +  return ctx.map;
 729  }
 730
 731
 732 @@ -9302,6 +9367,16 @@ move_shared_literal (asection *sec,
 733  \f
 734  /* Second relaxation pass.  */
 735
 736 +static int
 737 +action_remove_bytes_fn (splay_tree_node node, void *p)
 738 +{
 739 +  bfd_size_type *final_size = p;
 740 +  text_action *action = (text_action *)node->value;
 741 +
 742 +  *final_size -= action->removed_bytes;
 743 +  return 0;
 744 +}
 745 +
 746  /* Modify all of the relocations to point to the right spot, and if this
 747     is a relaxable section, delete the unwanted literals and fix the
 748     section size.  */
 749 @@ -9334,7 +9409,7 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 750
 751    internal_relocs = retrieve_internal_relocs (abfd, sec,
 752                                               link_info->keep_memory);
 753 -  if (!internal_relocs && !relax_info->action_list.head)
 754 +  if (!internal_relocs && !action_list_count (&relax_info->action_list))
 755      return TRUE;
 756
 757    contents = retrieve_contents (abfd, sec, link_info->keep_memory);
 758 @@ -9412,6 +9487,12 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 759                         }
 760                       /* Update the action so that the code that moves
 761                          the contents will do the right thing.  */
 762 +                     /* ta_remove_longcall and ta_remove_insn actions are
 763 +                        grouped together in the tree as well as
 764 +                        ta_convert_longcall and ta_none, so that changes below
 765 +                        can be done w/o removing and reinserting action into
 766 +                        the tree.  */
 767 +
 768                       if (action->action == ta_remove_longcall)
 769                         action->action = ta_remove_insn;
 770                       else
 771 @@ -9584,13 +9665,12 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 772
 773    if ((relax_info->is_relaxable_literal_section
 774         || relax_info->is_relaxable_asm_section)
 775 -      && relax_info->action_list.head)
 776 +      && action_list_count (&relax_info->action_list))
 777      {
 778        /* Walk through the planned actions and build up a table
 779          of move, copy and fill records.  Use the move, copy and
 780          fill records to perform the actions once.  */
 781
 782 -      int removed = 0;
 783        bfd_size_type final_size, copy_size, orig_insn_size;
 784        bfd_byte *scratch = NULL;
 785        bfd_byte *dup_contents = NULL;
 786 @@ -9601,15 +9681,12 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 787        bfd_vma orig_dot_vo = 0; /* Virtual offset from orig_dot.  */
 788        bfd_vma dup_dot = 0;
 789
 790 -      text_action *action = relax_info->action_list.head;
 791 +      text_action *action;
 792
 793        final_size = sec->size;
 794 -      for (action = relax_info->action_list.head; action;
 795 -          action = action->next)
 796 -       {
 797 -         final_size -= action->removed_bytes;
 798 -       }
 799
 800 +      splay_tree_foreach (relax_info->action_list.tree,
 801 +                         action_remove_bytes_fn, &final_size);
 802        scratch = (bfd_byte *) bfd_zmalloc (final_size);
 803        dup_contents = (bfd_byte *) bfd_zmalloc (final_size);
 804
 805 @@ -9618,8 +9695,8 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 806        print_action_list (stderr, &relax_info->action_list);
 807  #endif
 808
 809 -      for (action = relax_info->action_list.head; action;
 810 -          action = action->next)
 811 +      for (action = action_first (&relax_info->action_list); action;
 812 +          action = action_next (&relax_info->action_list, action))
 813         {
 814           virtual_action = FALSE;
 815           if (action->offset > orig_dot)
 816 @@ -9748,7 +9825,6 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 817               break;
 818             }
 819
 820 -         removed += action->removed_bytes;
 821           BFD_ASSERT (dup_dot <= final_size);
 822           BFD_ASSERT (orig_dot <= orig_size);
 823         }
 824 --
 825 1.8.1.4
 826