cirros-testvm/src-cirros/buildroot-2015.05/package/binutils/2.25/907-xtensa-optimize-removed_by_actions.patch

   1 From 3e3f60207399ab29dd55af109e5ae9facc7d8e83 Mon Sep 17 00:00:00 2001
   2 From: Max Filippov <jcmvbkbc@gmail.com>
   3 Date: Sat, 28 Mar 2015 08:46:28 +0300
   4 Subject: [PATCH 2/4] xtensa: optimize removed_by_actions
   5
   6 The function removed_by_actions iterates through text actions to
   7 calculate an offset applied by text actions to a given VMA. Although it
   8 has a parameter p_start_action that allows for incremental offset
   9 calculation, in many places it's used with p_start_action explicitly set
  10 to the first action. After the first relaxation pass when the list of
  11 text actions is finalized, an array of offsets sorted by VMA may be used
  12 to speed up this function.
  13
  14 Original profile:
  15
  16 % time    self  children    called     name
  17 -----------------------------------------
  18           0.35    0.00   33872/4808961     relax_section_symbols
  19           3.32    0.00  326022/4808961     relax_property_section
  20          12.83    0.00 1259379/4808961     offset_with_removed_text
  21          32.50    0.00 3189688/4808961     translate_reloc
  22   71.5   49.00    0.00 4808961         removed_by_actions
  23 -----------------------------------------
  24
  25 Same data, after optimization:
  26
  27 % time    self  children    called     name
  28 -----------------------------------------
  29           0.00    0.00   33872/4808537     relax_section_symbols
  30           0.01    0.00  326022/4808537     relax_property_section
  31           0.05    0.00 1258955/4808537     offset_with_removed_text_map
  32           0.13    0.00 3189688/4808537     translate_reloc
  33    1.0    0.20    0.00 4808537         removed_by_actions_map
  34           0.00    0.00     120/120         map_removal_by_action
  35 -----------------------------------------
  36
  37 2015-04-01  Max Filippov  <jcmvbkbc@gmail.com>
  38 bfd/
  39         * elf32-xtensa.c (removal_by_action_entry_struct,
  40         removal_by_action_map_struct): new structures.
  41         (removal_by_action_entry, removal_by_action_map): new typedefs.
  42         (text_action_list_struct): add new field: map.
  43         (map_removal_by_action, removed_by_actions_map,
  44         offset_with_removed_text_map): new functions.
  45         (relax_section): replace offset_with_removed_text with
  46         offset_with_removed_text_map.
  47         (translate_reloc, relax_property_section, relax_section_symbols):
  48         replace removed_by_actions with removed_by_actions_map.
  49
  50 Backported from: 071aa5c98a31c966f5fbfc573fcee61350fd1936
  51 Signed-off-by: Max Filippov <jcmvbkbc@gmail.com>
  52 ---
  53  bfd/elf32-xtensa.c | 181 +++++++++++++++++++++++++++++++++++++++++++++--------
  54  1 file changed, 156 insertions(+), 25 deletions(-)
  55
  56 diff --git a/bfd/elf32-xtensa.c b/bfd/elf32-xtensa.c
  57 index 872370b..21b2871 100644
  58 --- a/bfd/elf32-xtensa.c
  59 +++ b/bfd/elf32-xtensa.c
  60 @@ -5420,11 +5420,28 @@ struct text_action_struct
  61    text_action *next;
  62  };
  63
  64 +struct removal_by_action_entry_struct
  65 +{
  66 +  bfd_vma offset;
  67 +  int removed;
  68 +  int eq_removed;
  69 +  int eq_removed_before_fill;
  70 +};
  71 +typedef struct removal_by_action_entry_struct removal_by_action_entry;
  72 +
  73 +struct removal_by_action_map_struct
  74 +{
  75 +  unsigned n_entries;
  76 +  removal_by_action_entry *entry;
  77 +};
  78 +typedef struct removal_by_action_map_struct removal_by_action_map;
  79 +
  80
  81  /* List of all of the actions taken on a text section.  */
  82  struct text_action_list_struct
  83  {
  84    text_action *head;
  85 +  removal_by_action_map map;
  86  };
  87
  88
  89 @@ -5636,6 +5653,101 @@ action_list_count (text_action_list *action_list)
  90    return count;
  91  }
  92
  93 +static void
  94 +map_removal_by_action (text_action_list *action_list)
  95 +{
  96 +  text_action *r;
  97 +  int removed = 0;
  98 +  removal_by_action_map map;
  99 +  bfd_boolean eq_complete;
 100 +
 101 +  map.n_entries = 0;
 102 +  map.entry = bfd_malloc (action_list_count (action_list) *
 103 +                         sizeof (removal_by_action_entry));
 104 +  eq_complete = FALSE;
 105 +
 106 +  for (r = action_list->head; r;)
 107 +    {
 108 +      removal_by_action_entry *ientry = map.entry + map.n_entries;
 109 +
 110 +      if (map.n_entries && (ientry - 1)->offset == r->offset)
 111 +       {
 112 +         --ientry;
 113 +       }
 114 +      else
 115 +       {
 116 +         ++map.n_entries;
 117 +         eq_complete = FALSE;
 118 +         ientry->offset = r->offset;
 119 +         ientry->eq_removed_before_fill = removed;
 120 +       }
 121 +
 122 +      if (!eq_complete)
 123 +       {
 124 +         if (r->action != ta_fill || r->removed_bytes >= 0)
 125 +           {
 126 +             ientry->eq_removed = removed;
 127 +             eq_complete = TRUE;
 128 +           }
 129 +         else
 130 +           ientry->eq_removed = removed + r->removed_bytes;
 131 +       }
 132 +
 133 +      removed += r->removed_bytes;
 134 +      ientry->removed = removed;
 135 +      r = r->next;
 136 +    }
 137 +  action_list->map = map;
 138 +}
 139 +
 140 +static int
 141 +removed_by_actions_map (text_action_list *action_list, bfd_vma offset,
 142 +                       bfd_boolean before_fill)
 143 +{
 144 +  unsigned a, b;
 145 +
 146 +  if (!action_list->map.entry)
 147 +    map_removal_by_action (action_list);
 148 +
 149 +  if (!action_list->map.n_entries)
 150 +    return 0;
 151 +
 152 +  a = 0;
 153 +  b = action_list->map.n_entries;
 154 +
 155 +  while (b - a > 1)
 156 +    {
 157 +      unsigned c = (a + b) / 2;
 158 +
 159 +      if (action_list->map.entry[c].offset <= offset)
 160 +       a = c;
 161 +      else
 162 +       b = c;
 163 +    }
 164 +
 165 +  if (action_list->map.entry[a].offset < offset)
 166 +    {
 167 +      return action_list->map.entry[a].removed;
 168 +    }
 169 +  else if (action_list->map.entry[a].offset == offset)
 170 +    {
 171 +      return before_fill ?
 172 +       action_list->map.entry[a].eq_removed_before_fill :
 173 +       action_list->map.entry[a].eq_removed;
 174 +    }
 175 +  else
 176 +    {
 177 +      return 0;
 178 +    }
 179 +}
 180 +
 181 +static bfd_vma
 182 +offset_with_removed_text_map (text_action_list *action_list, bfd_vma offset)
 183 +{
 184 +  int removed = removed_by_actions_map (action_list, offset, FALSE);
 185 +  return offset - removed;
 186 +}
 187 +
 188
 189  /* The find_insn_action routine will only find non-fill actions.  */
 190
 191 @@ -5909,6 +6021,9 @@ init_xtensa_relax_info (asection *sec)
 192
 193    relax_info->action_list.head = NULL;
 194
 195 +  relax_info->action_list.map.n_entries = 0;
 196 +  relax_info->action_list.map.entry = NULL;
 197 +
 198    relax_info->fix_list = NULL;
 199    relax_info->fix_array = NULL;
 200    relax_info->fix_array_count = 0;
 201 @@ -9218,7 +9333,7 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 202                   if (elf_hash_table (link_info)->dynamic_sections_created)
 203                     shrink_dynamic_reloc_sections (link_info, abfd, sec, irel);
 204                   irel->r_info = ELF32_R_INFO (0, R_XTENSA_NONE);
 205 -                 irel->r_offset = offset_with_removed_text
 206 +                 irel->r_offset = offset_with_removed_text_map
 207                     (&relax_info->action_list, irel->r_offset);
 208                   continue;
 209                 }
 210 @@ -9255,7 +9370,7 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 211                     }
 212                 }
 213
 214 -             source_offset = offset_with_removed_text
 215 +             source_offset = offset_with_removed_text_map
 216                 (&relax_info->action_list, irel->r_offset);
 217               irel->r_offset = source_offset;
 218             }
 219 @@ -9352,7 +9467,7 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 220                       break;
 221                     }
 222
 223 -                 new_end_offset = offset_with_removed_text
 224 +                 new_end_offset = offset_with_removed_text_map
 225                     (&target_relax_info->action_list,
 226                      r_rel.target_offset + diff_value);
 227                   diff_value = new_end_offset - new_reloc.target_offset;
 228 @@ -9750,7 +9865,6 @@ translate_reloc (const r_reloc *orig_rel, r_reloc *new_rel, asection *sec)
 229    xtensa_relax_info *relax_info;
 230    removed_literal *removed;
 231    bfd_vma target_offset, base_offset;
 232 -  text_action *act;
 233
 234    *new_rel = *orig_rel;
 235
 236 @@ -9803,19 +9917,26 @@ translate_reloc (const r_reloc *orig_rel, r_reloc *new_rel, asection *sec)
 237       offset.  */
 238
 239    base_offset = r_reloc_get_target_offset (new_rel) - new_rel->rela.r_addend;
 240 -  act = relax_info->action_list.head;
 241    if (base_offset <= target_offset)
 242      {
 243 -      int base_removed = removed_by_actions (&act, base_offset, FALSE);
 244 -      int addend_removed = removed_by_actions (&act, target_offset, FALSE);
 245 +      int base_removed = removed_by_actions_map (&relax_info->action_list,
 246 +                                                base_offset, FALSE);
 247 +      int addend_removed = removed_by_actions_map (&relax_info->action_list,
 248 +                                                  target_offset, FALSE) -
 249 +       base_removed;
 250 +
 251        new_rel->target_offset = target_offset - base_removed - addend_removed;
 252        new_rel->rela.r_addend -= addend_removed;
 253      }
 254    else
 255      {
 256        /* Handle a negative addend.  The base offset comes first.  */
 257 -      int tgt_removed = removed_by_actions (&act, target_offset, FALSE);
 258 -      int addend_removed = removed_by_actions (&act, base_offset, FALSE);
 259 +      int tgt_removed = removed_by_actions_map (&relax_info->action_list,
 260 +                                               target_offset, FALSE);
 261 +      int addend_removed = removed_by_actions_map (&relax_info->action_list,
 262 +                                                  base_offset, FALSE) -
 263 +       tgt_removed;
 264 +
 265        new_rel->target_offset = target_offset - tgt_removed;
 266        new_rel->rela.r_addend += addend_removed;
 267      }
 268 @@ -10138,9 +10259,10 @@ relax_property_section (bfd *abfd,
 269               bfd_vma old_offset = val.r_rel.target_offset;
 270               bfd_vma new_offset;
 271               long old_size, new_size;
 272 -             text_action *act = target_relax_info->action_list.head;
 273 -             new_offset = old_offset -
 274 -               removed_by_actions (&act, old_offset, FALSE);
 275 +             int removed_by_old_offset =
 276 +               removed_by_actions_map (&target_relax_info->action_list,
 277 +                                       old_offset, FALSE);
 278 +             new_offset = old_offset - removed_by_old_offset;
 279
 280               /* Assert that we are not out of bounds.  */
 281               old_size = bfd_get_32 (abfd, size_p);
 282 @@ -10164,9 +10286,10 @@ relax_property_section (bfd *abfd,
 283
 284                       /* Recompute the new_offset, but this time don't
 285                          include any fill inserted by relaxation.  */
 286 -                     act = target_relax_info->action_list.head;
 287 -                     new_offset = old_offset -
 288 -                       removed_by_actions (&act, old_offset, TRUE);
 289 +                     removed_by_old_offset =
 290 +                       removed_by_actions_map (&target_relax_info->action_list,
 291 +                                               old_offset, TRUE);
 292 +                     new_offset = old_offset - removed_by_old_offset;
 293
 294                       /* If it is not unreachable and we have not yet
 295                          seen an unreachable at this address, place it
 296 @@ -10182,8 +10305,12 @@ relax_property_section (bfd *abfd,
 297                     }
 298                 }
 299               else
 300 -               new_size -=
 301 -                   removed_by_actions (&act, old_offset + old_size, TRUE);
 302 +               {
 303 +                 int removed_by_old_offset_size =
 304 +                   removed_by_actions_map (&target_relax_info->action_list,
 305 +                                           old_offset + old_size, TRUE);
 306 +                 new_size -= removed_by_old_offset_size - removed_by_old_offset;
 307 +               }
 308
 309               if (new_size != old_size)
 310                 {
 311 @@ -10441,14 +10568,16 @@ relax_section_symbols (bfd *abfd, asection *sec)
 312
 313        if (isym->st_shndx == sec_shndx)
 314         {
 315 -         text_action *act = relax_info->action_list.head;
 316           bfd_vma orig_addr = isym->st_value;
 317 +         int removed = removed_by_actions_map (&relax_info->action_list,
 318 +                                               orig_addr, FALSE);
 319
 320 -         isym->st_value -= removed_by_actions (&act, orig_addr, FALSE);
 321 -
 322 +         isym->st_value -= removed;
 323           if (ELF32_ST_TYPE (isym->st_info) == STT_FUNC)
 324             isym->st_size -=
 325 -             removed_by_actions (&act, orig_addr + isym->st_size, FALSE);
 326 +             removed_by_actions_map (&relax_info->action_list,
 327 +                                     orig_addr + isym->st_size, FALSE) -
 328 +             removed;
 329         }
 330      }
 331
 332 @@ -10466,15 +10595,17 @@ relax_section_symbols (bfd *abfd, asection *sec)
 333            || sym_hash->root.type == bfd_link_hash_defweak)
 334           && sym_hash->root.u.def.section == sec)
 335         {
 336 -         text_action *act = relax_info->action_list.head;
 337           bfd_vma orig_addr = sym_hash->root.u.def.value;
 338 +         int removed = removed_by_actions_map (&relax_info->action_list,
 339 +                                               orig_addr, FALSE);
 340
 341 -         sym_hash->root.u.def.value -=
 342 -           removed_by_actions (&act, orig_addr, FALSE);
 343 +         sym_hash->root.u.def.value -= removed;
 344
 345           if (sym_hash->type == STT_FUNC)
 346             sym_hash->size -=
 347 -             removed_by_actions (&act, orig_addr + sym_hash->size, FALSE);
 348 +             removed_by_actions_map (&relax_info->action_list,
 349 +                                     orig_addr + sym_hash->size, FALSE) -
 350 +             removed;
 351         }
 352      }
 353
 354 --
 355 1.8.1.4
 356