bfd/elf32-spu.c

   1 /* SPU specific support for 32-bit ELF
   2
   3    Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
   4
   5    This file is part of BFD, the Binary File Descriptor library.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License along
  18    with this program; if not, write to the Free Software Foundation, Inc.,
  19    51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.  */
  20
  21 #include "sysdep.h"
  22 #include "libiberty.h"
  23 #include "bfd.h"
  24 #include "bfdlink.h"
  25 #include "libbfd.h"
  26 #include "elf-bfd.h"
  27 #include "elf/spu.h"
  28 #include "elf32-spu.h"
  29
  30 /* We use RELA style relocs.  Don't define USE_REL.  */
  31
  32 static bfd_reloc_status_type spu_elf_rel9 (bfd *, arelent *, asymbol *,
  33                                            void *, asection *,
  34                                            bfd *, char **);
  35
  36 /* Values of type 'enum elf_spu_reloc_type' are used to index this
  37    array, so it must be declared in the order of that type.  */
  38
  39 static reloc_howto_type elf_howto_table[] = {
  40   HOWTO (R_SPU_NONE,       0, 0,  0, FALSE,  0, complain_overflow_dont,
  41          bfd_elf_generic_reloc, "SPU_NONE",
  42          FALSE, 0, 0x00000000, FALSE),
  43   HOWTO (R_SPU_ADDR10,     4, 2, 10, FALSE, 14, complain_overflow_bitfield,
  44          bfd_elf_generic_reloc, "SPU_ADDR10",
  45          FALSE, 0, 0x00ffc000, FALSE),
  46   HOWTO (R_SPU_ADDR16,     2, 2, 16, FALSE,  7, complain_overflow_bitfield,
  47          bfd_elf_generic_reloc, "SPU_ADDR16",
  48          FALSE, 0, 0x007fff80, FALSE),
  49   HOWTO (R_SPU_ADDR16_HI, 16, 2, 16, FALSE,  7, complain_overflow_bitfield,
  50          bfd_elf_generic_reloc, "SPU_ADDR16_HI",
  51          FALSE, 0, 0x007fff80, FALSE),
  52   HOWTO (R_SPU_ADDR16_LO,  0, 2, 16, FALSE,  7, complain_overflow_dont,
  53          bfd_elf_generic_reloc, "SPU_ADDR16_LO",
  54          FALSE, 0, 0x007fff80, FALSE),
  55   HOWTO (R_SPU_ADDR18,     0, 2, 18, FALSE,  7, complain_overflow_bitfield,
  56          bfd_elf_generic_reloc, "SPU_ADDR18",
  57          FALSE, 0, 0x01ffff80, FALSE),
  58   HOWTO (R_SPU_ADDR32,     0, 2, 32, FALSE,  0, complain_overflow_dont,
  59          bfd_elf_generic_reloc, "SPU_ADDR32",
  60          FALSE, 0, 0xffffffff, FALSE),
  61   HOWTO (R_SPU_REL16,      2, 2, 16,  TRUE,  7, complain_overflow_bitfield,
  62          bfd_elf_generic_reloc, "SPU_REL16",
  63          FALSE, 0, 0x007fff80, TRUE),
  64   HOWTO (R_SPU_ADDR7,      0, 2,  7, FALSE, 14, complain_overflow_dont,
  65          bfd_elf_generic_reloc, "SPU_ADDR7",
  66          FALSE, 0, 0x001fc000, FALSE),
  67   HOWTO (R_SPU_REL9,       2, 2,  9,  TRUE,  0, complain_overflow_signed,
  68          spu_elf_rel9,          "SPU_REL9",
  69          FALSE, 0, 0x0180007f, TRUE),
  70   HOWTO (R_SPU_REL9I,      2, 2,  9,  TRUE,  0, complain_overflow_signed,
  71          spu_elf_rel9,          "SPU_REL9I",
  72          FALSE, 0, 0x0000c07f, TRUE),
  73   HOWTO (R_SPU_ADDR10I,    0, 2, 10, FALSE, 14, complain_overflow_signed,
  74          bfd_elf_generic_reloc, "SPU_ADDR10I",
  75          FALSE, 0, 0x00ffc000, FALSE),
  76   HOWTO (R_SPU_ADDR16I,    0, 2, 16, FALSE,  7, complain_overflow_signed,
  77          bfd_elf_generic_reloc, "SPU_ADDR16I",
  78          FALSE, 0, 0x007fff80, FALSE),
  79   HOWTO (R_SPU_REL32,      0, 2, 32, TRUE,  0, complain_overflow_dont,
  80          bfd_elf_generic_reloc, "SPU_REL32",
  81          FALSE, 0, 0xffffffff, TRUE),
  82   HOWTO (R_SPU_ADDR16X,    0, 2, 16, FALSE,  7, complain_overflow_bitfield,
  83          bfd_elf_generic_reloc, "SPU_ADDR16X",
  84          FALSE, 0, 0x007fff80, FALSE),
  85   HOWTO (R_SPU_PPU32,      0, 2, 32, FALSE,  0, complain_overflow_dont,
  86          bfd_elf_generic_reloc, "SPU_PPU32",
  87          FALSE, 0, 0xffffffff, FALSE),
  88   HOWTO (R_SPU_PPU64,      0, 4, 64, FALSE,  0, complain_overflow_dont,
  89          bfd_elf_generic_reloc, "SPU_PPU64",
  90          FALSE, 0, -1, FALSE),
  91 };
  92
  93 static struct bfd_elf_special_section const spu_elf_special_sections[] = {
  94   { "._ea", 4, 0, SHT_PROGBITS, SHF_WRITE },
  95   { ".toe", 4, 0, SHT_NOBITS, SHF_ALLOC },
  96   { NULL, 0, 0, 0, 0 }
  97 };
  98
  99 static enum elf_spu_reloc_type
 100 spu_elf_bfd_to_reloc_type (bfd_reloc_code_real_type code)
 101 {
 102   switch (code)
 103     {
 104     default:
 105       return R_SPU_NONE;
 106     case BFD_RELOC_SPU_IMM10W:
 107       return R_SPU_ADDR10;
 108     case BFD_RELOC_SPU_IMM16W:
 109       return R_SPU_ADDR16;
 110     case BFD_RELOC_SPU_LO16:
 111       return R_SPU_ADDR16_LO;
 112     case BFD_RELOC_SPU_HI16:
 113       return R_SPU_ADDR16_HI;
 114     case BFD_RELOC_SPU_IMM18:
 115       return R_SPU_ADDR18;
 116     case BFD_RELOC_SPU_PCREL16:
 117       return R_SPU_REL16;
 118     case BFD_RELOC_SPU_IMM7:
 119       return R_SPU_ADDR7;
 120     case BFD_RELOC_SPU_IMM8:
 121       return R_SPU_NONE;
 122     case BFD_RELOC_SPU_PCREL9a:
 123       return R_SPU_REL9;
 124     case BFD_RELOC_SPU_PCREL9b:
 125       return R_SPU_REL9I;
 126     case BFD_RELOC_SPU_IMM10:
 127       return R_SPU_ADDR10I;
 128     case BFD_RELOC_SPU_IMM16:
 129       return R_SPU_ADDR16I;
 130     case BFD_RELOC_32:
 131       return R_SPU_ADDR32;
 132     case BFD_RELOC_32_PCREL:
 133       return R_SPU_REL32;
 134     case BFD_RELOC_SPU_PPU32:
 135       return R_SPU_PPU32;
 136     case BFD_RELOC_SPU_PPU64:
 137       return R_SPU_PPU64;
 138     }
 139 }
 140
 141 static void
 142 spu_elf_info_to_howto (bfd *abfd ATTRIBUTE_UNUSED,
 143                        arelent *cache_ptr,
 144                        Elf_Internal_Rela *dst)
 145 {
 146   enum elf_spu_reloc_type r_type;
 147
 148   r_type = (enum elf_spu_reloc_type) ELF32_R_TYPE (dst->r_info);
 149   BFD_ASSERT (r_type < R_SPU_max);
 150   cache_ptr->howto = &elf_howto_table[(int) r_type];
 151 }
 152
 153 static reloc_howto_type *
 154 spu_elf_reloc_type_lookup (bfd *abfd ATTRIBUTE_UNUSED,
 155                            bfd_reloc_code_real_type code)
 156 {
 157   enum elf_spu_reloc_type r_type = spu_elf_bfd_to_reloc_type (code);
 158
 159   if (r_type == R_SPU_NONE)
 160     return NULL;
 161
 162   return elf_howto_table + r_type;
 163 }
 164
 165 static reloc_howto_type *
 166 spu_elf_reloc_name_lookup (bfd *abfd ATTRIBUTE_UNUSED,
 167                            const char *r_name)
 168 {
 169   unsigned int i;
 170
 171   for (i = 0; i < sizeof (elf_howto_table) / sizeof (elf_howto_table[0]); i++)
 172     if (elf_howto_table[i].name != NULL
 173         && strcasecmp (elf_howto_table[i].name, r_name) == 0)
 174       return &elf_howto_table[i];
 175
 176   return NULL;
 177 }
 178
 179 /* Apply R_SPU_REL9 and R_SPU_REL9I relocs.  */
 180
 181 static bfd_reloc_status_type
 182 spu_elf_rel9 (bfd *abfd, arelent *reloc_entry, asymbol *symbol,
 183               void *data, asection *input_section,
 184               bfd *output_bfd, char **error_message)
 185 {
 186   bfd_size_type octets;
 187   bfd_vma val;
 188   long insn;
 189
 190   /* If this is a relocatable link (output_bfd test tells us), just
 191      call the generic function.  Any adjustment will be done at final
 192      link time.  */
 193   if (output_bfd != NULL)
 194     return bfd_elf_generic_reloc (abfd, reloc_entry, symbol, data,
 195                                   input_section, output_bfd, error_message);
 196
 197   if (reloc_entry->address > bfd_get_section_limit (abfd, input_section))
 198     return bfd_reloc_outofrange;
 199   octets = reloc_entry->address * bfd_octets_per_byte (abfd);
 200
 201   /* Get symbol value.  */
 202   val = 0;
 203   if (!bfd_is_com_section (symbol->section))
 204     val = symbol->value;
 205   if (symbol->section->output_section)
 206     val += symbol->section->output_section->vma;
 207
 208   val += reloc_entry->addend;
 209
 210   /* Make it pc-relative.  */
 211   val -= input_section->output_section->vma + input_section->output_offset;
 212
 213   val >>= 2;
 214   if (val + 256 >= 512)
 215     return bfd_reloc_overflow;
 216
 217   insn = bfd_get_32 (abfd, (bfd_byte *) data + octets);
 218
 219   /* Move two high bits of value to REL9I and REL9 position.
 220      The mask will take care of selecting the right field.  */
 221   val = (val & 0x7f) | ((val & 0x180) << 7) | ((val & 0x180) << 16);
 222   insn &= ~reloc_entry->howto->dst_mask;
 223   insn |= val & reloc_entry->howto->dst_mask;
 224   bfd_put_32 (abfd, insn, (bfd_byte *) data + octets);
 225   return bfd_reloc_ok;
 226 }
 227
 228 static bfd_boolean
 229 spu_elf_new_section_hook (bfd *abfd, asection *sec)
 230 {
 231   if (!sec->used_by_bfd)
 232     {
 233       struct _spu_elf_section_data *sdata;
 234
 235       sdata = bfd_zalloc (abfd, sizeof (*sdata));
 236       if (sdata == NULL)
 237         return FALSE;
 238       sec->used_by_bfd = sdata;
 239     }
 240
 241   return _bfd_elf_new_section_hook (abfd, sec);
 242 }
 243
 244 /* Set up overlay info for executables.  */
 245
 246 static bfd_boolean
 247 spu_elf_object_p (bfd *abfd)
 248 {
 249   if ((abfd->flags & (EXEC_P | DYNAMIC)) != 0)
 250     {
 251       unsigned int i, num_ovl, num_buf;
 252       Elf_Internal_Phdr *phdr = elf_tdata (abfd)->phdr;
 253       Elf_Internal_Ehdr *ehdr = elf_elfheader (abfd);
 254       Elf_Internal_Phdr *last_phdr = NULL;
 255
 256       for (num_buf = 0, num_ovl = 0, i = 0; i < ehdr->e_phnum; i++, phdr++)
 257         if (phdr->p_type == PT_LOAD && (phdr->p_flags & PF_OVERLAY) != 0)
 258           {
 259             unsigned int j;
 260
 261             ++num_ovl;
 262             if (last_phdr == NULL
 263                 || ((last_phdr->p_vaddr ^ phdr->p_vaddr) & 0x3ffff) != 0)
 264               ++num_buf;
 265             last_phdr = phdr;
 266             for (j = 1; j < elf_numsections (abfd); j++)
 267               {
 268                 Elf_Internal_Shdr *shdr = elf_elfsections (abfd)[j];
 269
 270                 if (ELF_IS_SECTION_IN_SEGMENT_MEMORY (shdr, phdr))
 271                   {
 272                     asection *sec = shdr->bfd_section;
 273                     spu_elf_section_data (sec)->u.o.ovl_index = num_ovl;
 274                     spu_elf_section_data (sec)->u.o.ovl_buf = num_buf;
 275                   }
 276               }
 277           }
 278     }
 279   return TRUE;
 280 }
 281
 282 /* Specially mark defined symbols named _EAR_* with BSF_KEEP so that
 283    strip --strip-unneeded will not remove them.  */
 284
 285 static void
 286 spu_elf_backend_symbol_processing (bfd *abfd ATTRIBUTE_UNUSED, asymbol *sym)
 287 {
 288   if (sym->name != NULL
 289       && sym->section != bfd_abs_section_ptr
 290       && strncmp (sym->name, "_EAR_", 5) == 0)
 291     sym->flags |= BSF_KEEP;
 292 }
 293
 294 /* SPU ELF linker hash table.  */
 295
 296 struct spu_link_hash_table
 297 {
 298   struct elf_link_hash_table elf;
 299
 300   /* Shortcuts to overlay sections.  */
 301   asection *ovtab;
 302   asection *toe;
 303   asection **ovl_sec;
 304
 305   /* Count of stubs in each overlay section.  */
 306   unsigned int *stub_count;
 307
 308   /* The stub section for each overlay section.  */
 309   asection **stub_sec;
 310
 311   struct elf_link_hash_entry *ovly_load;
 312   struct elf_link_hash_entry *ovly_return;
 313   unsigned long ovly_load_r_symndx;
 314
 315   /* Number of overlay buffers.  */
 316   unsigned int num_buf;
 317
 318   /* Total number of overlays.  */
 319   unsigned int num_overlays;
 320
 321   /* How much memory we have.  */
 322   unsigned int local_store;
 323   /* Local store --auto-overlay should reserve for non-overlay
 324      functions and data.  */
 325   unsigned int overlay_fixed;
 326   /* Local store --auto-overlay should reserve for stack and heap.  */
 327   unsigned int reserved;
 328   /* If reserved is not specified, stack analysis will calculate a value
 329      for the stack.  This parameter adjusts that value to allow for
 330      negative sp access (the ABI says 2000 bytes below sp are valid,
 331      and the overlay manager uses some of this area).  */
 332   int extra_stack_space;
 333   /* Count of overlay stubs needed in non-overlay area.  */
 334   unsigned int non_ovly_stub;
 335
 336   /* Stash various callbacks for --auto-overlay.  */
 337   void (*spu_elf_load_ovl_mgr) (void);
 338   FILE *(*spu_elf_open_overlay_script) (void);
 339   void (*spu_elf_relink) (void);
 340
 341   /* Bit 0 set if --auto-overlay.
 342      Bit 1 set if --auto-relink.
 343      Bit 2 set if --overlay-rodata.  */
 344   unsigned int auto_overlay : 3;
 345 #define AUTO_OVERLAY 1
 346 #define AUTO_RELINK 2
 347 #define OVERLAY_RODATA 4
 348
 349   /* Set if we should emit symbols for stubs.  */
 350   unsigned int emit_stub_syms:1;
 351
 352   /* Set if we want stubs on calls out of overlay regions to
 353      non-overlay regions.  */
 354   unsigned int non_overlay_stubs : 1;
 355
 356   /* Set on error.  */
 357   unsigned int stub_err : 1;
 358
 359   /* Set if stack size analysis should be done.  */
 360   unsigned int stack_analysis : 1;
 361
 362   /* Set if __stack_* syms will be emitted.  */
 363   unsigned int emit_stack_syms : 1;
 364 };
 365
 366 /* Hijack the generic got fields for overlay stub accounting.  */
 367
 368 struct got_entry
 369 {
 370   struct got_entry *next;
 371   unsigned int ovl;
 372   bfd_vma addend;
 373   bfd_vma stub_addr;
 374 };
 375
 376 #define spu_hash_table(p) \
 377   ((struct spu_link_hash_table *) ((p)->hash))
 378
 379 /* Create a spu ELF linker hash table.  */
 380
 381 static struct bfd_link_hash_table *
 382 spu_elf_link_hash_table_create (bfd *abfd)
 383 {
 384   struct spu_link_hash_table *htab;
 385
 386   htab = bfd_malloc (sizeof (*htab));
 387   if (htab == NULL)
 388     return NULL;
 389
 390   if (!_bfd_elf_link_hash_table_init (&htab->elf, abfd,
 391                                       _bfd_elf_link_hash_newfunc,
 392                                       sizeof (struct elf_link_hash_entry)))
 393     {
 394       free (htab);
 395       return NULL;
 396     }
 397
 398   memset (&htab->ovtab, 0,
 399           sizeof (*htab) - offsetof (struct spu_link_hash_table, ovtab));
 400
 401   htab->elf.init_got_refcount.refcount = 0;
 402   htab->elf.init_got_refcount.glist = NULL;
 403   htab->elf.init_got_offset.offset = 0;
 404   htab->elf.init_got_offset.glist = NULL;
 405   return &htab->elf.root;
 406 }
 407
 408 /* Find the symbol for the given R_SYMNDX in IBFD and set *HP and *SYMP
 409    to (hash, NULL) for global symbols, and (NULL, sym) for locals.  Set
 410    *SYMSECP to the symbol's section.  *LOCSYMSP caches local syms.  */
 411
 412 static bfd_boolean
 413 get_sym_h (struct elf_link_hash_entry **hp,
 414            Elf_Internal_Sym **symp,
 415            asection **symsecp,
 416            Elf_Internal_Sym **locsymsp,
 417            unsigned long r_symndx,
 418            bfd *ibfd)
 419 {
 420   Elf_Internal_Shdr *symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
 421
 422   if (r_symndx >= symtab_hdr->sh_info)
 423     {
 424       struct elf_link_hash_entry **sym_hashes = elf_sym_hashes (ibfd);
 425       struct elf_link_hash_entry *h;
 426
 427       h = sym_hashes[r_symndx - symtab_hdr->sh_info];
 428       while (h->root.type == bfd_link_hash_indirect
 429              || h->root.type == bfd_link_hash_warning)
 430         h = (struct elf_link_hash_entry *) h->root.u.i.link;
 431
 432       if (hp != NULL)
 433         *hp = h;
 434
 435       if (symp != NULL)
 436         *symp = NULL;
 437
 438       if (symsecp != NULL)
 439         {
 440           asection *symsec = NULL;
 441           if (h->root.type == bfd_link_hash_defined
 442               || h->root.type == bfd_link_hash_defweak)
 443             symsec = h->root.u.def.section;
 444           *symsecp = symsec;
 445         }
 446     }
 447   else
 448     {
 449       Elf_Internal_Sym *sym;
 450       Elf_Internal_Sym *locsyms = *locsymsp;
 451
 452       if (locsyms == NULL)
 453         {
 454           locsyms = (Elf_Internal_Sym *) symtab_hdr->contents;
 455           if (locsyms == NULL)
 456             locsyms = bfd_elf_get_elf_syms (ibfd, symtab_hdr,
 457                                             symtab_hdr->sh_info,
 458                                             0, NULL, NULL, NULL);
 459           if (locsyms == NULL)
 460             return FALSE;
 461           *locsymsp = locsyms;
 462         }
 463       sym = locsyms + r_symndx;
 464
 465       if (hp != NULL)
 466         *hp = NULL;
 467
 468       if (symp != NULL)
 469         *symp = sym;
 470
 471       if (symsecp != NULL)
 472         *symsecp = bfd_section_from_elf_index (ibfd, sym->st_shndx);
 473     }
 474
 475   return TRUE;
 476 }
 477
 478 /* Create the note section if not already present.  This is done early so
 479    that the linker maps the sections to the right place in the output.  */
 480
 481 bfd_boolean
 482 spu_elf_create_sections (struct bfd_link_info *info,
 483                          int stack_analysis,
 484                          int emit_stack_syms)
 485 {
 486   bfd *ibfd;
 487   struct spu_link_hash_table *htab = spu_hash_table (info);
 488
 489   /* Stash some options away where we can get at them later.  */
 490   htab->stack_analysis = stack_analysis;
 491   htab->emit_stack_syms = emit_stack_syms;
 492
 493   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
 494     if (bfd_get_section_by_name (ibfd, SPU_PTNOTE_SPUNAME) != NULL)
 495       break;
 496
 497   if (ibfd == NULL)
 498     {
 499       /* Make SPU_PTNOTE_SPUNAME section.  */
 500       asection *s;
 501       size_t name_len;
 502       size_t size;
 503       bfd_byte *data;
 504       flagword flags;
 505
 506       ibfd = info->input_bfds;
 507       flags = SEC_LOAD | SEC_READONLY | SEC_HAS_CONTENTS | SEC_IN_MEMORY;
 508       s = bfd_make_section_anyway_with_flags (ibfd, SPU_PTNOTE_SPUNAME, flags);
 509       if (s == NULL
 510           || !bfd_set_section_alignment (ibfd, s, 4))
 511         return FALSE;
 512
 513       name_len = strlen (bfd_get_filename (info->output_bfd)) + 1;
 514       size = 12 + ((sizeof (SPU_PLUGIN_NAME) + 3) & -4);
 515       size += (name_len + 3) & -4;
 516
 517       if (!bfd_set_section_size (ibfd, s, size))
 518         return FALSE;
 519
 520       data = bfd_zalloc (ibfd, size);
 521       if (data == NULL)
 522         return FALSE;
 523
 524       bfd_put_32 (ibfd, sizeof (SPU_PLUGIN_NAME), data + 0);
 525       bfd_put_32 (ibfd, name_len, data + 4);
 526       bfd_put_32 (ibfd, 1, data + 8);
 527       memcpy (data + 12, SPU_PLUGIN_NAME, sizeof (SPU_PLUGIN_NAME));
 528       memcpy (data + 12 + ((sizeof (SPU_PLUGIN_NAME) + 3) & -4),
 529               bfd_get_filename (info->output_bfd), name_len);
 530       s->contents = data;
 531     }
 532
 533   return TRUE;
 534 }
 535
 536 /* qsort predicate to sort sections by vma.  */
 537
 538 static int
 539 sort_sections (const void *a, const void *b)
 540 {
 541   const asection *const *s1 = a;
 542   const asection *const *s2 = b;
 543   bfd_signed_vma delta = (*s1)->vma - (*s2)->vma;
 544
 545   if (delta != 0)
 546     return delta < 0 ? -1 : 1;
 547
 548   return (*s1)->index - (*s2)->index;
 549 }
 550
 551 /* Identify overlays in the output bfd, and number them.  */
 552
 553 bfd_boolean
 554 spu_elf_find_overlays (struct bfd_link_info *info)
 555 {
 556   struct spu_link_hash_table *htab = spu_hash_table (info);
 557   asection **alloc_sec;
 558   unsigned int i, n, ovl_index, num_buf;
 559   asection *s;
 560   bfd_vma ovl_end;
 561
 562   if (info->output_bfd->section_count < 2)
 563     return FALSE;
 564
 565   alloc_sec
 566     = bfd_malloc (info->output_bfd->section_count * sizeof (*alloc_sec));
 567   if (alloc_sec == NULL)
 568     return FALSE;
 569
 570   /* Pick out all the alloced sections.  */
 571   for (n = 0, s = info->output_bfd->sections; s != NULL; s = s->next)
 572     if ((s->flags & SEC_ALLOC) != 0
 573         && (s->flags & (SEC_LOAD | SEC_THREAD_LOCAL)) != SEC_THREAD_LOCAL
 574         && s->size != 0)
 575       alloc_sec[n++] = s;
 576
 577   if (n == 0)
 578     {
 579       free (alloc_sec);
 580       return FALSE;
 581     }
 582
 583   /* Sort them by vma.  */
 584   qsort (alloc_sec, n, sizeof (*alloc_sec), sort_sections);
 585
 586   /* Look for overlapping vmas.  Any with overlap must be overlays.
 587      Count them.  Also count the number of overlay regions.  */
 588   ovl_end = alloc_sec[0]->vma + alloc_sec[0]->size;
 589   for (ovl_index = 0, num_buf = 0, i = 1; i < n; i++)
 590     {
 591       s = alloc_sec[i];
 592       if (s->vma < ovl_end)
 593         {
 594           asection *s0 = alloc_sec[i - 1];
 595
 596           if (spu_elf_section_data (s0)->u.o.ovl_index == 0)
 597             {
 598               alloc_sec[ovl_index] = s0;
 599               spu_elf_section_data (s0)->u.o.ovl_index = ++ovl_index;
 600               spu_elf_section_data (s0)->u.o.ovl_buf = ++num_buf;
 601             }
 602           alloc_sec[ovl_index] = s;
 603           spu_elf_section_data (s)->u.o.ovl_index = ++ovl_index;
 604           spu_elf_section_data (s)->u.o.ovl_buf = num_buf;
 605           if (s0->vma != s->vma)
 606             {
 607               info->callbacks->einfo (_("%X%P: overlay sections %A and %A "
 608                                         "do not start at the same address.\n"),
 609                                       s0, s);
 610               return FALSE;
 611             }
 612           if (ovl_end < s->vma + s->size)
 613             ovl_end = s->vma + s->size;
 614         }
 615       else
 616         ovl_end = s->vma + s->size;
 617     }
 618
 619   htab->num_overlays = ovl_index;
 620   htab->num_buf = num_buf;
 621   htab->ovl_sec = alloc_sec;
 622   htab->ovly_load = elf_link_hash_lookup (&htab->elf, "__ovly_load",
 623                                           FALSE, FALSE, FALSE);
 624   htab->ovly_return = elf_link_hash_lookup (&htab->elf, "__ovly_return",
 625                                             FALSE, FALSE, FALSE);
 626   return ovl_index != 0;
 627 }
 628
 629 /* Support two sizes of overlay stubs, a slower more compact stub of two
 630    intructions, and a faster stub of four instructions.  */
 631 #ifndef OVL_STUB_SIZE
 632 /* Default to faster.  */
 633 #define OVL_STUB_SIZE 16
 634 /* #define OVL_STUB_SIZE 8 */
 635 #endif
 636 #define BRSL    0x33000000
 637 #define BR      0x32000000
 638 #define NOP     0x40200000
 639 #define LNOP    0x00200000
 640 #define ILA     0x42000000
 641
 642 /* Return true for all relative and absolute branch instructions.
 643    bra   00110000 0..
 644    brasl 00110001 0..
 645    br    00110010 0..
 646    brsl  00110011 0..
 647    brz   00100000 0..
 648    brnz  00100001 0..
 649    brhz  00100010 0..
 650    brhnz 00100011 0..  */
 651
 652 static bfd_boolean
 653 is_branch (const unsigned char *insn)
 654 {
 655   return (insn[0] & 0xec) == 0x20 && (insn[1] & 0x80) == 0;
 656 }
 657
 658 /* Return true for all indirect branch instructions.
 659    bi     00110101 000
 660    bisl   00110101 001
 661    iret   00110101 010
 662    bisled 00110101 011
 663    biz    00100101 000
 664    binz   00100101 001
 665    bihz   00100101 010
 666    bihnz  00100101 011  */
 667
 668 static bfd_boolean
 669 is_indirect_branch (const unsigned char *insn)
 670 {
 671   return (insn[0] & 0xef) == 0x25 && (insn[1] & 0x80) == 0;
 672 }
 673
 674 /* Return true for branch hint instructions.
 675    hbra  0001000..
 676    hbrr  0001001..  */
 677
 678 static bfd_boolean
 679 is_hint (const unsigned char *insn)
 680 {
 681   return (insn[0] & 0xfc) == 0x10;
 682 }
 683
 684 /* True if INPUT_SECTION might need overlay stubs.  */
 685
 686 static bfd_boolean
 687 maybe_needs_stubs (asection *input_section, bfd *output_bfd)
 688 {
 689   /* No stubs for debug sections and suchlike.  */
 690   if ((input_section->flags & SEC_ALLOC) == 0)
 691     return FALSE;
 692
 693   /* No stubs for link-once sections that will be discarded.  */
 694   if (input_section->output_section == NULL
 695       || input_section->output_section->owner != output_bfd)
 696     return FALSE;
 697
 698   /* Don't create stubs for .eh_frame references.  */
 699   if (strcmp (input_section->name, ".eh_frame") == 0)
 700     return FALSE;
 701
 702   return TRUE;
 703 }
 704
 705 enum _stub_type
 706 {
 707   no_stub,
 708   ovl_stub,
 709   nonovl_stub,
 710   stub_error
 711 };
 712
 713 /* Return non-zero if this reloc symbol should go via an overlay stub.
 714    Return 2 if the stub must be in non-overlay area.  */
 715
 716 static enum _stub_type
 717 needs_ovl_stub (struct elf_link_hash_entry *h,
 718                 Elf_Internal_Sym *sym,
 719                 asection *sym_sec,
 720                 asection *input_section,
 721                 Elf_Internal_Rela *irela,
 722                 bfd_byte *contents,
 723                 struct bfd_link_info *info)
 724 {
 725   struct spu_link_hash_table *htab = spu_hash_table (info);
 726   enum elf_spu_reloc_type r_type;
 727   unsigned int sym_type;
 728   bfd_boolean branch;
 729   enum _stub_type ret = no_stub;
 730
 731   if (sym_sec == NULL
 732       || sym_sec->output_section == NULL
 733       || sym_sec->output_section->owner != info->output_bfd
 734       || spu_elf_section_data (sym_sec->output_section) == NULL)
 735     return ret;
 736
 737   if (h != NULL)
 738     {
 739       /* Ensure no stubs for user supplied overlay manager syms.  */
 740       if (h == htab->ovly_load || h == htab->ovly_return)
 741         return ret;
 742
 743       /* setjmp always goes via an overlay stub, because then the return
 744          and hence the longjmp goes via __ovly_return.  That magically
 745          makes setjmp/longjmp between overlays work.  */
 746       if (strncmp (h->root.root.string, "setjmp", 6) == 0
 747           && (h->root.root.string[6] == '\0' || h->root.root.string[6] == '@'))
 748         ret = ovl_stub;
 749     }
 750
 751   /* Usually, symbols in non-overlay sections don't need stubs.  */
 752   if (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index == 0
 753       && !htab->non_overlay_stubs)
 754     return ret;
 755
 756   if (h != NULL)
 757     sym_type = h->type;
 758   else
 759     sym_type = ELF_ST_TYPE (sym->st_info);
 760
 761   r_type = ELF32_R_TYPE (irela->r_info);
 762   branch = FALSE;
 763   if (r_type == R_SPU_REL16 || r_type == R_SPU_ADDR16)
 764     {
 765       bfd_byte insn[4];
 766
 767       if (contents == NULL)
 768         {
 769           contents = insn;
 770           if (!bfd_get_section_contents (input_section->owner,
 771                                          input_section,
 772                                          contents,
 773                                          irela->r_offset, 4))
 774             return stub_error;
 775         }
 776       else
 777         contents += irela->r_offset;
 778
 779       if (is_branch (contents) || is_hint (contents))
 780         {
 781           branch = TRUE;
 782           if ((contents[0] & 0xfd) == 0x31
 783               && sym_type != STT_FUNC
 784               && contents != insn)
 785             {
 786               /* It's common for people to write assembly and forget
 787                  to give function symbols the right type.  Handle
 788                  calls to such symbols, but warn so that (hopefully)
 789                  people will fix their code.  We need the symbol
 790                  type to be correct to distinguish function pointer
 791                  initialisation from other pointer initialisations.  */
 792               const char *sym_name;
 793
 794               if (h != NULL)
 795                 sym_name = h->root.root.string;
 796               else
 797                 {
 798                   Elf_Internal_Shdr *symtab_hdr;
 799                   symtab_hdr = &elf_tdata (input_section->owner)->symtab_hdr;
 800                   sym_name = bfd_elf_sym_name (input_section->owner,
 801                                                symtab_hdr,
 802                                                sym,
 803                                                sym_sec);
 804                 }
 805               (*_bfd_error_handler) (_("warning: call to non-function"
 806                                        " symbol %s defined in %B"),
 807                                      sym_sec->owner, sym_name);
 808
 809             }
 810         }
 811     }
 812
 813   if (sym_type != STT_FUNC
 814       && !branch
 815       && (sym_sec->flags & SEC_CODE) == 0)
 816     return ret;
 817
 818   /* A reference from some other section to a symbol in an overlay
 819      section needs a stub.  */
 820   if (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index
 821        != spu_elf_section_data (input_section->output_section)->u.o.ovl_index)
 822     ret = ovl_stub;
 823
 824   /* If this insn isn't a branch then we are possibly taking the
 825      address of a function and passing it out somehow.  */
 826   return !branch && sym_type == STT_FUNC ? nonovl_stub : ret;
 827 }
 828
 829 static bfd_boolean
 830 count_stub (struct spu_link_hash_table *htab,
 831             bfd *ibfd,
 832             asection *isec,
 833             enum _stub_type stub_type,
 834             struct elf_link_hash_entry *h,
 835             const Elf_Internal_Rela *irela)
 836 {
 837   unsigned int ovl = 0;
 838   struct got_entry *g, **head;
 839   bfd_vma addend;
 840
 841   /* If this instruction is a branch or call, we need a stub
 842      for it.  One stub per function per overlay.
 843      If it isn't a branch, then we are taking the address of
 844      this function so need a stub in the non-overlay area
 845      for it.  One stub per function.  */
 846   if (stub_type != nonovl_stub)
 847     ovl = spu_elf_section_data (isec->output_section)->u.o.ovl_index;
 848
 849   if (h != NULL)
 850     head = &h->got.glist;
 851   else
 852     {
 853       if (elf_local_got_ents (ibfd) == NULL)
 854         {
 855           bfd_size_type amt = (elf_tdata (ibfd)->symtab_hdr.sh_info
 856                                * sizeof (*elf_local_got_ents (ibfd)));
 857           elf_local_got_ents (ibfd) = bfd_zmalloc (amt);
 858           if (elf_local_got_ents (ibfd) == NULL)
 859             return FALSE;
 860         }
 861       head = elf_local_got_ents (ibfd) + ELF32_R_SYM (irela->r_info);
 862     }
 863
 864   addend = 0;
 865   if (irela != NULL)
 866     addend = irela->r_addend;
 867
 868   if (ovl == 0)
 869     {
 870       struct got_entry *gnext;
 871
 872       for (g = *head; g != NULL; g = g->next)
 873         if (g->addend == addend && g->ovl == 0)
 874           break;
 875
 876       if (g == NULL)
 877         {
 878           /* Need a new non-overlay area stub.  Zap other stubs.  */
 879           for (g = *head; g != NULL; g = gnext)
 880             {
 881               gnext = g->next;
 882               if (g->addend == addend)
 883                 {
 884                   htab->stub_count[g->ovl] -= 1;
 885                   free (g);
 886                 }
 887             }
 888         }
 889     }
 890   else
 891     {
 892       for (g = *head; g != NULL; g = g->next)
 893         if (g->addend == addend && (g->ovl == ovl || g->ovl == 0))
 894           break;
 895     }
 896
 897   if (g == NULL)
 898     {
 899       g = bfd_malloc (sizeof *g);
 900       if (g == NULL)
 901         return FALSE;
 902       g->ovl = ovl;
 903       g->addend = addend;
 904       g->stub_addr = (bfd_vma) -1;
 905       g->next = *head;
 906       *head = g;
 907
 908       htab->stub_count[ovl] += 1;
 909     }
 910
 911   return TRUE;
 912 }
 913
 914 /* Two instruction overlay stubs look like:
 915
 916    brsl $75,__ovly_load
 917    .word target_ovl_and_address
 918
 919    ovl_and_address is a word with the overlay number in the top 14 bits
 920    and local store address in the bottom 18 bits.
 921
 922    Four instruction overlay stubs look like:
 923
 924    ila $78,ovl_number
 925    lnop
 926    ila $79,target_address
 927    br __ovly_load  */
 928
 929 static bfd_boolean
 930 build_stub (struct spu_link_hash_table *htab,
 931             bfd *ibfd,
 932             asection *isec,
 933             enum _stub_type stub_type,
 934             struct elf_link_hash_entry *h,
 935             const Elf_Internal_Rela *irela,
 936             bfd_vma dest,
 937             asection *dest_sec)
 938 {
 939   unsigned int ovl;
 940   struct got_entry *g, **head;
 941   asection *sec;
 942   bfd_vma addend, val, from, to;
 943
 944   ovl = 0;
 945   if (stub_type != nonovl_stub)
 946     ovl = spu_elf_section_data (isec->output_section)->u.o.ovl_index;
 947
 948   if (h != NULL)
 949     head = &h->got.glist;
 950   else
 951     head = elf_local_got_ents (ibfd) + ELF32_R_SYM (irela->r_info);
 952
 953   addend = 0;
 954   if (irela != NULL)
 955     addend = irela->r_addend;
 956
 957   for (g = *head; g != NULL; g = g->next)
 958     if (g->addend == addend && (g->ovl == ovl || g->ovl == 0))
 959       break;
 960   if (g == NULL)
 961     abort ();
 962
 963   if (g->ovl == 0 && ovl != 0)
 964     return TRUE;
 965
 966   if (g->stub_addr != (bfd_vma) -1)
 967     return TRUE;
 968
 969   sec = htab->stub_sec[ovl];
 970   dest += dest_sec->output_offset + dest_sec->output_section->vma;
 971   from = sec->size + sec->output_offset + sec->output_section->vma;
 972   g->stub_addr = from;
 973   to = (htab->ovly_load->root.u.def.value
 974         + htab->ovly_load->root.u.def.section->output_offset
 975         + htab->ovly_load->root.u.def.section->output_section->vma);
 976   val = to - from;
 977   if (OVL_STUB_SIZE == 16)
 978     val -= 12;
 979   if (((dest | to | from) & 3) != 0
 980       || val + 0x40000 >= 0x80000)
 981     {
 982       htab->stub_err = 1;
 983       return FALSE;
 984     }
 985   ovl = spu_elf_section_data (dest_sec->output_section)->u.o.ovl_index;
 986
 987   if (OVL_STUB_SIZE == 16)
 988     {
 989       bfd_put_32 (sec->owner, ILA + ((ovl << 7) & 0x01ffff80) + 78,
 990                   sec->contents + sec->size);
 991       bfd_put_32 (sec->owner, LNOP,
 992                   sec->contents + sec->size + 4);
 993       bfd_put_32 (sec->owner, ILA + ((dest << 7) & 0x01ffff80) + 79,
 994                   sec->contents + sec->size + 8);
 995       bfd_put_32 (sec->owner, BR + ((val << 5) & 0x007fff80),
 996                   sec->contents + sec->size + 12);
 997     }
 998   else if (OVL_STUB_SIZE == 8)
 999     {
1000       bfd_put_32 (sec->owner, BRSL + ((val << 5) & 0x007fff80) + 75,
1001                   sec->contents + sec->size);
1002
1003       val = (dest & 0x3ffff) | (ovl << 18);
1004       bfd_put_32 (sec->owner, val,
1005                   sec->contents + sec->size + 4);
1006     }
1007   else
1008     abort ();
1009   sec->size += OVL_STUB_SIZE;
1010
1011   if (htab->emit_stub_syms)
1012     {
1013       size_t len;
1014       char *name;
1015       int add;
1016
1017       len = 8 + sizeof (".ovl_call.") - 1;
1018       if (h != NULL)
1019         len += strlen (h->root.root.string);
1020       else
1021         len += 8 + 1 + 8;
1022       add = 0;
1023       if (irela != NULL)
1024         add = (int) irela->r_addend & 0xffffffff;
1025       if (add != 0)
1026         len += 1 + 8;
1027       name = bfd_malloc (len);
1028       if (name == NULL)
1029         return FALSE;
1030
1031       sprintf (name, "%08x.ovl_call.", g->ovl);
1032       if (h != NULL)
1033         strcpy (name + 8 + sizeof (".ovl_call.") - 1, h->root.root.string);
1034       else
1035         sprintf (name + 8 + sizeof (".ovl_call.") - 1, "%x:%x",
1036                  dest_sec->id & 0xffffffff,
1037                  (int) ELF32_R_SYM (irela->r_info) & 0xffffffff);
1038       if (add != 0)
1039         sprintf (name + len - 9, "+%x", add);
1040
1041       h = elf_link_hash_lookup (&htab->elf, name, TRUE, TRUE, FALSE);
1042       free (name);
1043       if (h == NULL)
1044         return FALSE;
1045       if (h->root.type == bfd_link_hash_new)
1046         {
1047           h->root.type = bfd_link_hash_defined;
1048           h->root.u.def.section = sec;
1049           h->root.u.def.value = sec->size - OVL_STUB_SIZE;
1050           h->size = OVL_STUB_SIZE;
1051           h->type = STT_FUNC;
1052           h->ref_regular = 1;
1053           h->def_regular = 1;
1054           h->ref_regular_nonweak = 1;
1055           h->forced_local = 1;
1056           h->non_elf = 0;
1057         }
1058     }
1059
1060   return TRUE;
1061 }
1062
1063 /* Called via elf_link_hash_traverse to allocate stubs for any _SPUEAR_
1064    symbols.  */
1065
1066 static bfd_boolean
1067 allocate_spuear_stubs (struct elf_link_hash_entry *h, void *inf)
1068 {
1069   /* Symbols starting with _SPUEAR_ need a stub because they may be
1070      invoked by the PPU.  */
1071   struct bfd_link_info *info = inf;
1072   struct spu_link_hash_table *htab = spu_hash_table (info);
1073   asection *sym_sec;
1074
1075   if ((h->root.type == bfd_link_hash_defined
1076        || h->root.type == bfd_link_hash_defweak)
1077       && h->def_regular
1078       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0
1079       && (sym_sec = h->root.u.def.section) != NULL
1080       && sym_sec->output_section != NULL
1081       && sym_sec->output_section->owner == info->output_bfd
1082       && spu_elf_section_data (sym_sec->output_section) != NULL
1083       && (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index != 0
1084           || htab->non_overlay_stubs))
1085     {
1086       return count_stub (htab, NULL, NULL, nonovl_stub, h, NULL);
1087     }
1088
1089   return TRUE;
1090 }
1091
1092 static bfd_boolean
1093 build_spuear_stubs (struct elf_link_hash_entry *h, void *inf)
1094 {
1095   /* Symbols starting with _SPUEAR_ need a stub because they may be
1096      invoked by the PPU.  */
1097   struct bfd_link_info *info = inf;
1098   struct spu_link_hash_table *htab = spu_hash_table (info);
1099   asection *sym_sec;
1100
1101   if ((h->root.type == bfd_link_hash_defined
1102        || h->root.type == bfd_link_hash_defweak)
1103       && h->def_regular
1104       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0
1105       && (sym_sec = h->root.u.def.section) != NULL
1106       && sym_sec->output_section != NULL
1107       && sym_sec->output_section->owner == info->output_bfd
1108       && spu_elf_section_data (sym_sec->output_section) != NULL
1109       && (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index != 0
1110           || htab->non_overlay_stubs))
1111     {
1112       return build_stub (htab, NULL, NULL, nonovl_stub, h, NULL,
1113                          h->root.u.def.value, sym_sec);
1114     }
1115
1116   return TRUE;
1117 }
1118
1119 /* Size or build stubs.  */
1120
1121 static bfd_boolean
1122 process_stubs (struct bfd_link_info *info, bfd_boolean build)
1123 {
1124   struct spu_link_hash_table *htab = spu_hash_table (info);
1125   bfd *ibfd;
1126
1127   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
1128     {
1129       extern const bfd_target bfd_elf32_spu_vec;
1130       Elf_Internal_Shdr *symtab_hdr;
1131       asection *isec;
1132       Elf_Internal_Sym *local_syms = NULL;
1133
1134       if (ibfd->xvec != &bfd_elf32_spu_vec)
1135         continue;
1136
1137       /* We'll need the symbol table in a second.  */
1138       symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
1139       if (symtab_hdr->sh_info == 0)
1140         continue;
1141
1142       /* Walk over each section attached to the input bfd.  */
1143       for (isec = ibfd->sections; isec != NULL; isec = isec->next)
1144         {
1145           Elf_Internal_Rela *internal_relocs, *irelaend, *irela;
1146
1147           /* If there aren't any relocs, then there's nothing more to do.  */
1148           if ((isec->flags & SEC_RELOC) == 0
1149               || isec->reloc_count == 0)
1150             continue;
1151
1152           if (!maybe_needs_stubs (isec, info->output_bfd))
1153             continue;
1154
1155           /* Get the relocs.  */
1156           internal_relocs = _bfd_elf_link_read_relocs (ibfd, isec, NULL, NULL,
1157                                                        info->keep_memory);
1158           if (internal_relocs == NULL)
1159             goto error_ret_free_local;
1160
1161           /* Now examine each relocation.  */
1162           irela = internal_relocs;
1163           irelaend = irela + isec->reloc_count;
1164           for (; irela < irelaend; irela++)
1165             {
1166               enum elf_spu_reloc_type r_type;
1167               unsigned int r_indx;
1168               asection *sym_sec;
1169               Elf_Internal_Sym *sym;
1170               struct elf_link_hash_entry *h;
1171               enum _stub_type stub_type;
1172
1173               r_type = ELF32_R_TYPE (irela->r_info);
1174               r_indx = ELF32_R_SYM (irela->r_info);
1175
1176               if (r_type >= R_SPU_max)
1177                 {
1178                   bfd_set_error (bfd_error_bad_value);
1179                 error_ret_free_internal:
1180                   if (elf_section_data (isec)->relocs != internal_relocs)
1181                     free (internal_relocs);
1182                 error_ret_free_local:
1183                   if (local_syms != NULL
1184                       && (symtab_hdr->contents
1185                           != (unsigned char *) local_syms))
1186                     free (local_syms);
1187                   return FALSE;
1188                 }
1189
1190               /* Determine the reloc target section.  */
1191               if (!get_sym_h (&h, &sym, &sym_sec, &local_syms, r_indx, ibfd))
1192                 goto error_ret_free_internal;
1193
1194               stub_type = needs_ovl_stub (h, sym, sym_sec, isec, irela,
1195                                           NULL, info);
1196               if (stub_type == no_stub)
1197                 continue;
1198               else if (stub_type == stub_error)
1199                 goto error_ret_free_internal;
1200
1201               if (htab->stub_count == NULL)
1202                 {
1203                   bfd_size_type amt;
1204                   amt = (htab->num_overlays + 1) * sizeof (*htab->stub_count);
1205                   htab->stub_count = bfd_zmalloc (amt);
1206                   if (htab->stub_count == NULL)
1207                     goto error_ret_free_internal;
1208                 }
1209
1210               if (!build)
1211                 {
1212                   if (!count_stub (htab, ibfd, isec, stub_type, h, irela))
1213                     goto error_ret_free_internal;
1214                 }
1215               else
1216                 {
1217                   bfd_vma dest;
1218
1219                   if (h != NULL)
1220                     dest = h->root.u.def.value;
1221                   else
1222                     dest = sym->st_value;
1223                   dest += irela->r_addend;
1224                   if (!build_stub (htab, ibfd, isec, stub_type, h, irela,
1225                                    dest, sym_sec))
1226                     goto error_ret_free_internal;
1227                 }
1228             }
1229
1230           /* We're done with the internal relocs, free them.  */
1231           if (elf_section_data (isec)->relocs != internal_relocs)
1232             free (internal_relocs);
1233         }
1234
1235       if (local_syms != NULL
1236           && symtab_hdr->contents != (unsigned char *) local_syms)
1237         {
1238           if (!info->keep_memory)
1239             free (local_syms);
1240           else
1241             symtab_hdr->contents = (unsigned char *) local_syms;
1242         }
1243     }
1244
1245   return TRUE;
1246 }
1247
1248 /* Allocate space for overlay call and return stubs.  */
1249
1250 int
1251 spu_elf_size_stubs (struct bfd_link_info *info,
1252                     void (*place_spu_section) (asection *, asection *,
1253                                                const char *),
1254                     int non_overlay_stubs)
1255 {
1256   struct spu_link_hash_table *htab = spu_hash_table (info);
1257   bfd *ibfd;
1258   bfd_size_type amt;
1259   flagword flags;
1260   unsigned int i;
1261   asection *stub;
1262
1263   htab->non_overlay_stubs = non_overlay_stubs;
1264   if (!process_stubs (info, FALSE))
1265     return 0;
1266
1267   elf_link_hash_traverse (&htab->elf, allocate_spuear_stubs, info);
1268   if (htab->stub_err)
1269     return 0;
1270
1271   if (htab->stub_count == NULL)
1272     return 1;
1273
1274   ibfd = info->input_bfds;
1275   amt = (htab->num_overlays + 1) * sizeof (*htab->stub_sec);
1276   htab->stub_sec = bfd_zmalloc (amt);
1277   if (htab->stub_sec == NULL)
1278     return 0;
1279
1280   flags = (SEC_ALLOC | SEC_LOAD | SEC_CODE | SEC_READONLY
1281            | SEC_HAS_CONTENTS | SEC_IN_MEMORY);
1282   stub = bfd_make_section_anyway_with_flags (ibfd, ".stub", flags);
1283   htab->stub_sec[0] = stub;
1284   if (stub == NULL
1285       || !bfd_set_section_alignment (ibfd, stub, 3 + (OVL_STUB_SIZE > 8)))
1286     return 0;
1287   stub->size = htab->stub_count[0] * OVL_STUB_SIZE;
1288   (*place_spu_section) (stub, NULL, ".text");
1289
1290   for (i = 0; i < htab->num_overlays; ++i)
1291     {
1292       asection *osec = htab->ovl_sec[i];
1293       unsigned int ovl = spu_elf_section_data (osec)->u.o.ovl_index;
1294       stub = bfd_make_section_anyway_with_flags (ibfd, ".stub", flags);
1295       htab->stub_sec[ovl] = stub;
1296       if (stub == NULL
1297           || !bfd_set_section_alignment (ibfd, stub, 3 + (OVL_STUB_SIZE > 8)))
1298         return 0;
1299       stub->size = htab->stub_count[ovl] * OVL_STUB_SIZE;
1300       (*place_spu_section) (stub, osec, NULL);
1301     }
1302
1303  /* htab->ovtab consists of two arrays.
1304     .   struct {
1305     .     u32 vma;
1306     .     u32 size;
1307     .     u32 file_off;
1308     .     u32 buf;
1309     .   } _ovly_table[];
1310     .
1311     .   struct {
1312     .     u32 mapped;
1313     .   } _ovly_buf_table[];
1314     .  */
1315
1316   flags = (SEC_ALLOC | SEC_LOAD
1317            | SEC_HAS_CONTENTS | SEC_IN_MEMORY);
1318   htab->ovtab = bfd_make_section_anyway_with_flags (ibfd, ".ovtab", flags);
1319   if (htab->ovtab == NULL
1320       || !bfd_set_section_alignment (ibfd, htab->ovtab, 4))
1321     return 0;
1322
1323   htab->ovtab->size = htab->num_overlays * 16 + 16 + htab->num_buf * 4;
1324   (*place_spu_section) (htab->ovtab, NULL, ".data");
1325
1326   htab->toe = bfd_make_section_anyway_with_flags (ibfd, ".toe", SEC_ALLOC);
1327   if (htab->toe == NULL
1328       || !bfd_set_section_alignment (ibfd, htab->toe, 4))
1329     return 0;
1330   htab->toe->size = 16;
1331   (*place_spu_section) (htab->toe, NULL, ".toe");
1332
1333   return 2;
1334 }
1335
1336 /* Functions to handle embedded spu_ovl.o object.  */
1337
1338 static void *
1339 ovl_mgr_open (struct bfd *nbfd ATTRIBUTE_UNUSED, void *stream)
1340 {
1341   return stream;
1342 }
1343
1344 static file_ptr
1345 ovl_mgr_pread (struct bfd *abfd ATTRIBUTE_UNUSED,
1346                void *stream,
1347                void *buf,
1348                file_ptr nbytes,
1349                file_ptr offset)
1350 {
1351   struct _ovl_stream *os;
1352   size_t count;
1353   size_t max;
1354
1355   os = (struct _ovl_stream *) stream;
1356   max = (const char *) os->end - (const char *) os->start;
1357
1358   if ((ufile_ptr) offset >= max)
1359     return 0;
1360
1361   count = nbytes;
1362   if (count > max - offset)
1363     count = max - offset;
1364
1365   memcpy (buf, (const char *) os->start + offset, count);
1366   return count;
1367 }
1368
1369 bfd_boolean
1370 spu_elf_open_builtin_lib (bfd **ovl_bfd, const struct _ovl_stream *stream)
1371 {
1372   *ovl_bfd = bfd_openr_iovec ("builtin ovl_mgr",
1373                               "elf32-spu",
1374                               ovl_mgr_open,
1375                               (void *) stream,
1376                               ovl_mgr_pread,
1377                               NULL,
1378                               NULL);
1379   return *ovl_bfd != NULL;
1380 }
1381
1382 /* Define an STT_OBJECT symbol.  */
1383
1384 static struct elf_link_hash_entry *
1385 define_ovtab_symbol (struct spu_link_hash_table *htab, const char *name)
1386 {
1387   struct elf_link_hash_entry *h;
1388
1389   h = elf_link_hash_lookup (&htab->elf, name, TRUE, FALSE, FALSE);
1390   if (h == NULL)
1391     return NULL;
1392
1393   if (h->root.type != bfd_link_hash_defined
1394       || !h->def_regular)
1395     {
1396       h->root.type = bfd_link_hash_defined;
1397       h->root.u.def.section = htab->ovtab;
1398       h->type = STT_OBJECT;
1399       h->ref_regular = 1;
1400       h->def_regular = 1;
1401       h->ref_regular_nonweak = 1;
1402       h->non_elf = 0;
1403     }
1404   else
1405     {
1406       (*_bfd_error_handler) (_("%B is not allowed to define %s"),
1407                              h->root.u.def.section->owner,
1408                              h->root.root.string);
1409       bfd_set_error (bfd_error_bad_value);
1410       return NULL;
1411     }
1412
1413   return h;
1414 }
1415
1416 /* Fill in all stubs and the overlay tables.  */
1417
1418 bfd_boolean
1419 spu_elf_build_stubs (struct bfd_link_info *info, int emit_syms)
1420 {
1421   struct spu_link_hash_table *htab = spu_hash_table (info);
1422   struct elf_link_hash_entry *h;
1423   bfd_byte *p;
1424   asection *s;
1425   bfd *obfd;
1426   unsigned int i;
1427
1428   htab->emit_stub_syms = emit_syms;
1429   if (htab->stub_count == NULL)
1430     return TRUE;
1431
1432   for (i = 0; i <= htab->num_overlays; i++)
1433     if (htab->stub_sec[i]->size != 0)
1434       {
1435         htab->stub_sec[i]->contents = bfd_zalloc (htab->stub_sec[i]->owner,
1436                                                   htab->stub_sec[i]->size);
1437         if (htab->stub_sec[i]->contents == NULL)
1438           return FALSE;
1439         htab->stub_sec[i]->rawsize = htab->stub_sec[i]->size;
1440         htab->stub_sec[i]->size = 0;
1441       }
1442
1443   h = elf_link_hash_lookup (&htab->elf, "__ovly_load", FALSE, FALSE, FALSE);
1444   htab->ovly_load = h;
1445   BFD_ASSERT (h != NULL
1446               && (h->root.type == bfd_link_hash_defined
1447                   || h->root.type == bfd_link_hash_defweak)
1448               && h->def_regular);
1449
1450   s = h->root.u.def.section->output_section;
1451   if (spu_elf_section_data (s)->u.o.ovl_index)
1452     {
1453       (*_bfd_error_handler) (_("%s in overlay section"),
1454                              h->root.root.string);
1455       bfd_set_error (bfd_error_bad_value);
1456       return FALSE;
1457     }
1458
1459   h = elf_link_hash_lookup (&htab->elf, "__ovly_return", FALSE, FALSE, FALSE);
1460   htab->ovly_return = h;
1461
1462   /* Fill in all the stubs.  */
1463   process_stubs (info, TRUE);
1464   if (!htab->stub_err)
1465     elf_link_hash_traverse (&htab->elf, build_spuear_stubs, info);
1466
1467   if (htab->stub_err)
1468     {
1469       (*_bfd_error_handler) (_("overlay stub relocation overflow"));
1470       bfd_set_error (bfd_error_bad_value);
1471       return FALSE;
1472     }
1473
1474   for (i = 0; i <= htab->num_overlays; i++)
1475     {
1476       if (htab->stub_sec[i]->size != htab->stub_sec[i]->rawsize)
1477         {
1478           (*_bfd_error_handler)  (_("stubs don't match calculated size"));
1479           bfd_set_error (bfd_error_bad_value);
1480           return FALSE;
1481         }
1482       htab->stub_sec[i]->rawsize = 0;
1483     }
1484
1485   htab->ovtab->contents = bfd_zalloc (htab->ovtab->owner, htab->ovtab->size);
1486   if (htab->ovtab->contents == NULL)
1487     return FALSE;
1488
1489   /* Write out _ovly_table.  */
1490   p = htab->ovtab->contents;
1491   /* set low bit of .size to mark non-overlay area as present.  */
1492   p[7] = 1;
1493   obfd = htab->ovtab->output_section->owner;
1494   for (s = obfd->sections; s != NULL; s = s->next)
1495     {
1496       unsigned int ovl_index = spu_elf_section_data (s)->u.o.ovl_index;
1497
1498       if (ovl_index != 0)
1499         {
1500           unsigned long off = ovl_index * 16;
1501           unsigned int ovl_buf = spu_elf_section_data (s)->u.o.ovl_buf;
1502
1503           bfd_put_32 (htab->ovtab->owner, s->vma, p + off);
1504           bfd_put_32 (htab->ovtab->owner, (s->size + 15) & -16, p + off + 4);
1505           /* file_off written later in spu_elf_modify_program_headers.  */
1506           bfd_put_32 (htab->ovtab->owner, ovl_buf, p + off + 12);
1507         }
1508     }
1509
1510   h = define_ovtab_symbol (htab, "_ovly_table");
1511   if (h == NULL)
1512     return FALSE;
1513   h->root.u.def.value = 16;
1514   h->size = htab->num_overlays * 16;
1515
1516   h = define_ovtab_symbol (htab, "_ovly_table_end");
1517   if (h == NULL)
1518     return FALSE;
1519   h->root.u.def.value = htab->num_overlays * 16 + 16;
1520   h->size = 0;
1521
1522   h = define_ovtab_symbol (htab, "_ovly_buf_table");
1523   if (h == NULL)
1524     return FALSE;
1525   h->root.u.def.value = htab->num_overlays * 16 + 16;
1526   h->size = htab->num_buf * 4;
1527
1528   h = define_ovtab_symbol (htab, "_ovly_buf_table_end");
1529   if (h == NULL)
1530     return FALSE;
1531   h->root.u.def.value = htab->num_overlays * 16 + 16 + htab->num_buf * 4;
1532   h->size = 0;
1533
1534   h = define_ovtab_symbol (htab, "_EAR_");
1535   if (h == NULL)
1536     return FALSE;
1537   h->root.u.def.section = htab->toe;
1538   h->root.u.def.value = 0;
1539   h->size = 16;
1540
1541   return TRUE;
1542 }
1543
1544 /* Check that all loadable section VMAs lie in the range
1545    LO .. HI inclusive, and stash some parameters for --auto-overlay.  */
1546
1547 asection *
1548 spu_elf_check_vma (struct bfd_link_info *info,
1549                    int auto_overlay,
1550                    unsigned int lo,
1551                    unsigned int hi,
1552                    unsigned int overlay_fixed,
1553                    unsigned int reserved,
1554                    int extra_stack_space,
1555                    void (*spu_elf_load_ovl_mgr) (void),
1556                    FILE *(*spu_elf_open_overlay_script) (void),
1557                    void (*spu_elf_relink) (void))
1558 {
1559   struct elf_segment_map *m;
1560   unsigned int i;
1561   struct spu_link_hash_table *htab = spu_hash_table (info);
1562   bfd *abfd = info->output_bfd;
1563
1564   if (auto_overlay & AUTO_OVERLAY)
1565     htab->auto_overlay = auto_overlay;
1566   htab->local_store = hi + 1 - lo;
1567   htab->overlay_fixed = overlay_fixed;
1568   htab->reserved = reserved;
1569   htab->extra_stack_space = extra_stack_space;
1570   htab->spu_elf_load_ovl_mgr = spu_elf_load_ovl_mgr;
1571   htab->spu_elf_open_overlay_script = spu_elf_open_overlay_script;
1572   htab->spu_elf_relink = spu_elf_relink;
1573
1574   for (m = elf_tdata (abfd)->segment_map; m != NULL; m = m->next)
1575     if (m->p_type == PT_LOAD)
1576       for (i = 0; i < m->count; i++)
1577         if (m->sections[i]->size != 0
1578             && (m->sections[i]->vma < lo
1579                 || m->sections[i]->vma > hi
1580                 || m->sections[i]->vma + m->sections[i]->size - 1 > hi))
1581           return m->sections[i];
1582
1583   /* No need for overlays if it all fits.  */
1584   htab->auto_overlay = 0;
1585   return NULL;
1586 }
1587
1588 /* OFFSET in SEC (presumably) is the beginning of a function prologue.
1589    Search for stack adjusting insns, and return the sp delta.  */
1590
1591 static int
1592 find_function_stack_adjust (asection *sec, bfd_vma offset)
1593 {
1594   int unrecog;
1595   int reg[128];
1596
1597   memset (reg, 0, sizeof (reg));
1598   for (unrecog = 0; offset + 4 <= sec->size && unrecog < 32; offset += 4)
1599     {
1600       unsigned char buf[4];
1601       int rt, ra;
1602       int imm;
1603
1604       /* Assume no relocs on stack adjusing insns.  */
1605       if (!bfd_get_section_contents (sec->owner, sec, buf, offset, 4))
1606         break;
1607
1608       if (buf[0] == 0x24 /* stqd */)
1609         continue;
1610
1611       rt = buf[3] & 0x7f;
1612       ra = ((buf[2] & 0x3f) << 1) | (buf[3] >> 7);
1613       /* Partly decoded immediate field.  */
1614       imm = (buf[1] << 9) | (buf[2] << 1) | (buf[3] >> 7);
1615
1616       if (buf[0] == 0x1c /* ai */)
1617         {
1618           imm >>= 7;
1619           imm = (imm ^ 0x200) - 0x200;
1620           reg[rt] = reg[ra] + imm;
1621
1622           if (rt == 1 /* sp */)
1623             {
1624               if (imm > 0)
1625                 break;
1626               return reg[rt];
1627             }
1628         }
1629       else if (buf[0] == 0x18 && (buf[1] & 0xe0) == 0 /* a */)
1630         {
1631           int rb = ((buf[1] & 0x1f) << 2) | ((buf[2] & 0xc0) >> 6);
1632
1633           reg[rt] = reg[ra] + reg[rb];
1634           if (rt == 1)
1635             return reg[rt];
1636         }
1637       else if ((buf[0] & 0xfc) == 0x40 /* il, ilh, ilhu, ila */)
1638         {
1639           if (buf[0] >= 0x42 /* ila */)
1640             imm |= (buf[0] & 1) << 17;
1641           else
1642             {
1643               imm &= 0xffff;
1644
1645               if (buf[0] == 0x40 /* il */)
1646                 {
1647                   if ((buf[1] & 0x80) == 0)
1648                     goto unknown_insn;
1649                   imm = (imm ^ 0x8000) - 0x8000;
1650                 }
1651               else if ((buf[1] & 0x80) == 0 /* ilhu */)
1652                 imm <<= 16;
1653             }
1654           reg[rt] = imm;
1655           continue;
1656         }
1657       else if (buf[0] == 0x60 && (buf[1] & 0x80) != 0 /* iohl */)
1658         {
1659           reg[rt] |= imm & 0xffff;
1660           continue;
1661         }
1662       else if (buf[0] == 0x04 /* ori */)
1663         {
1664           imm >>= 7;
1665           imm = (imm ^ 0x200) - 0x200;
1666           reg[rt] = reg[ra] | imm;
1667           continue;
1668         }
1669       else if ((buf[0] == 0x33 && imm == 1 /* brsl .+4 */)
1670                || (buf[0] == 0x08 && (buf[1] & 0xe0) == 0 /* sf */))
1671         {
1672           /* Used in pic reg load.  Say rt is trashed.  */
1673           reg[rt] = 0;
1674           continue;
1675         }
1676       else if (is_branch (buf) || is_indirect_branch (buf))
1677         /* If we hit a branch then we must be out of the prologue.  */
1678         break;
1679     unknown_insn:
1680       ++unrecog;
1681     }
1682
1683   return 0;
1684 }
1685
1686 /* qsort predicate to sort symbols by section and value.  */
1687
1688 static Elf_Internal_Sym *sort_syms_syms;
1689 static asection **sort_syms_psecs;
1690
1691 static int
1692 sort_syms (const void *a, const void *b)
1693 {
1694   Elf_Internal_Sym *const *s1 = a;
1695   Elf_Internal_Sym *const *s2 = b;
1696   asection *sec1,*sec2;
1697   bfd_signed_vma delta;
1698
1699   sec1 = sort_syms_psecs[*s1 - sort_syms_syms];
1700   sec2 = sort_syms_psecs[*s2 - sort_syms_syms];
1701
1702   if (sec1 != sec2)
1703     return sec1->index - sec2->index;
1704
1705   delta = (*s1)->st_value - (*s2)->st_value;
1706   if (delta != 0)
1707     return delta < 0 ? -1 : 1;
1708
1709   delta = (*s2)->st_size - (*s1)->st_size;
1710   if (delta != 0)
1711     return delta < 0 ? -1 : 1;
1712
1713   return *s1 < *s2 ? -1 : 1;
1714 }
1715
1716 struct call_info
1717 {
1718   struct function_info *fun;
1719   struct call_info *next;
1720   unsigned int count;
1721   unsigned int max_depth;
1722   unsigned int is_tail : 1;
1723   unsigned int is_pasted : 1;
1724 };
1725
1726 struct function_info
1727 {
1728   /* List of functions called.  Also branches to hot/cold part of
1729      function.  */
1730   struct call_info *call_list;
1731   /* For hot/cold part of function, point to owner.  */
1732   struct function_info *start;
1733   /* Symbol at start of function.  */
1734   union {
1735     Elf_Internal_Sym *sym;
1736     struct elf_link_hash_entry *h;
1737   } u;
1738   /* Function section.  */
1739   asection *sec;
1740   asection *rodata;
1741   /* Where last called from, and number of sections called from.  */
1742   asection *last_caller;
1743   unsigned int call_count;
1744   /* Address range of (this part of) function.  */
1745   bfd_vma lo, hi;
1746   /* Stack usage.  */
1747   int stack;
1748   /* Distance from root of call tree.  Tail and hot/cold branches
1749      count as one deeper.  We aren't counting stack frames here.  */
1750   unsigned int depth;
1751   /* Set if global symbol.  */
1752   unsigned int global : 1;
1753   /* Set if known to be start of function (as distinct from a hunk
1754      in hot/cold section.  */
1755   unsigned int is_func : 1;
1756   /* Set if not a root node.  */
1757   unsigned int non_root : 1;
1758   /* Flags used during call tree traversal.  It's cheaper to replicate
1759      the visit flags than have one which needs clearing after a traversal.  */
1760   unsigned int visit1 : 1;
1761   unsigned int visit2 : 1;
1762   unsigned int marking : 1;
1763   unsigned int visit3 : 1;
1764   unsigned int visit4 : 1;
1765   unsigned int visit5 : 1;
1766   unsigned int visit6 : 1;
1767   unsigned int visit7 : 1;
1768 };
1769
1770 struct spu_elf_stack_info
1771 {
1772   int num_fun;
1773   int max_fun;
1774   /* Variable size array describing functions, one per contiguous
1775      address range belonging to a function.  */
1776   struct function_info fun[1];
1777 };
1778
1779 /* Allocate a struct spu_elf_stack_info with MAX_FUN struct function_info
1780    entries for section SEC.  */
1781
1782 static struct spu_elf_stack_info *
1783 alloc_stack_info (asection *sec, int max_fun)
1784 {
1785   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
1786   bfd_size_type amt;
1787
1788   amt = sizeof (struct spu_elf_stack_info);
1789   amt += (max_fun - 1) * sizeof (struct function_info);
1790   sec_data->u.i.stack_info = bfd_zmalloc (amt);
1791   if (sec_data->u.i.stack_info != NULL)
1792     sec_data->u.i.stack_info->max_fun = max_fun;
1793   return sec_data->u.i.stack_info;
1794 }
1795
1796 /* Add a new struct function_info describing a (part of a) function
1797    starting at SYM_H.  Keep the array sorted by address.  */
1798
1799 static struct function_info *
1800 maybe_insert_function (asection *sec,
1801                        void *sym_h,
1802                        bfd_boolean global,
1803                        bfd_boolean is_func)
1804 {
1805   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
1806   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
1807   int i;
1808   bfd_vma off, size;
1809
1810   if (sinfo == NULL)
1811     {
1812       sinfo = alloc_stack_info (sec, 20);
1813       if (sinfo == NULL)
1814         return NULL;
1815     }
1816
1817   if (!global)
1818     {
1819       Elf_Internal_Sym *sym = sym_h;
1820       off = sym->st_value;
1821       size = sym->st_size;
1822     }
1823   else
1824     {
1825       struct elf_link_hash_entry *h = sym_h;
1826       off = h->root.u.def.value;
1827       size = h->size;
1828     }
1829
1830   for (i = sinfo->num_fun; --i >= 0; )
1831     if (sinfo->fun[i].lo <= off)
1832       break;
1833
1834   if (i >= 0)
1835     {
1836       /* Don't add another entry for an alias, but do update some
1837          info.  */
1838       if (sinfo->fun[i].lo == off)
1839         {
1840           /* Prefer globals over local syms.  */
1841           if (global && !sinfo->fun[i].global)
1842             {
1843               sinfo->fun[i].global = TRUE;
1844               sinfo->fun[i].u.h = sym_h;
1845             }
1846           if (is_func)
1847             sinfo->fun[i].is_func = TRUE;
1848           return &sinfo->fun[i];
1849         }
1850       /* Ignore a zero-size symbol inside an existing function.  */
1851       else if (sinfo->fun[i].hi > off && size == 0)
1852         return &sinfo->fun[i];
1853     }
1854
1855   if (sinfo->num_fun >= sinfo->max_fun)
1856     {
1857       bfd_size_type amt = sizeof (struct spu_elf_stack_info);
1858       bfd_size_type old = amt;
1859
1860       old += (sinfo->max_fun - 1) * sizeof (struct function_info);
1861       sinfo->max_fun += 20 + (sinfo->max_fun >> 1);
1862       amt += (sinfo->max_fun - 1) * sizeof (struct function_info);
1863       sinfo = bfd_realloc (sinfo, amt);
1864       if (sinfo == NULL)
1865         return NULL;
1866       memset ((char *) sinfo + old, 0, amt - old);
1867       sec_data->u.i.stack_info = sinfo;
1868     }
1869
1870   if (++i < sinfo->num_fun)
1871     memmove (&sinfo->fun[i + 1], &sinfo->fun[i],
1872              (sinfo->num_fun - i) * sizeof (sinfo->fun[i]));
1873   sinfo->fun[i].is_func = is_func;
1874   sinfo->fun[i].global = global;
1875   sinfo->fun[i].sec = sec;
1876   if (global)
1877     sinfo->fun[i].u.h = sym_h;
1878   else
1879     sinfo->fun[i].u.sym = sym_h;
1880   sinfo->fun[i].lo = off;
1881   sinfo->fun[i].hi = off + size;
1882   sinfo->fun[i].stack = -find_function_stack_adjust (sec, off);
1883   sinfo->num_fun += 1;
1884   return &sinfo->fun[i];
1885 }
1886
1887 /* Return the name of FUN.  */
1888
1889 static const char *
1890 func_name (struct function_info *fun)
1891 {
1892   asection *sec;
1893   bfd *ibfd;
1894   Elf_Internal_Shdr *symtab_hdr;
1895
1896   while (fun->start != NULL)
1897     fun = fun->start;
1898
1899   if (fun->global)
1900     return fun->u.h->root.root.string;
1901
1902   sec = fun->sec;
1903   if (fun->u.sym->st_name == 0)
1904     {
1905       size_t len = strlen (sec->name);
1906       char *name = bfd_malloc (len + 10);
1907       if (name == NULL)
1908         return "(null)";
1909       sprintf (name, "%s+%lx", sec->name,
1910                (unsigned long) fun->u.sym->st_value & 0xffffffff);
1911       return name;
1912     }
1913   ibfd = sec->owner;
1914   symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
1915   return bfd_elf_sym_name (ibfd, symtab_hdr, fun->u.sym, sec);
1916 }
1917
1918 /* Read the instruction at OFF in SEC.  Return true iff the instruction
1919    is a nop, lnop, or stop 0 (all zero insn).  */
1920
1921 static bfd_boolean
1922 is_nop (asection *sec, bfd_vma off)
1923 {
1924   unsigned char insn[4];
1925
1926   if (off + 4 > sec->size
1927       || !bfd_get_section_contents (sec->owner, sec, insn, off, 4))
1928     return FALSE;
1929   if ((insn[0] & 0xbf) == 0 && (insn[1] & 0xe0) == 0x20)
1930     return TRUE;
1931   if (insn[0] == 0 && insn[1] == 0 && insn[2] == 0 && insn[3] == 0)
1932     return TRUE;
1933   return FALSE;
1934 }
1935
1936 /* Extend the range of FUN to cover nop padding up to LIMIT.
1937    Return TRUE iff some instruction other than a NOP was found.  */
1938
1939 static bfd_boolean
1940 insns_at_end (struct function_info *fun, bfd_vma limit)
1941 {
1942   bfd_vma off = (fun->hi + 3) & -4;
1943
1944   while (off < limit && is_nop (fun->sec, off))
1945     off += 4;
1946   if (off < limit)
1947     {
1948       fun->hi = off;
1949       return TRUE;
1950     }
1951   fun->hi = limit;
1952   return FALSE;
1953 }
1954
1955 /* Check and fix overlapping function ranges.  Return TRUE iff there
1956    are gaps in the current info we have about functions in SEC.  */
1957
1958 static bfd_boolean
1959 check_function_ranges (asection *sec, struct bfd_link_info *info)
1960 {
1961   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
1962   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
1963   int i;
1964   bfd_boolean gaps = FALSE;
1965
1966   if (sinfo == NULL)
1967     return FALSE;
1968
1969   for (i = 1; i < sinfo->num_fun; i++)
1970     if (sinfo->fun[i - 1].hi > sinfo->fun[i].lo)
1971       {
1972         /* Fix overlapping symbols.  */
1973         const char *f1 = func_name (&sinfo->fun[i - 1]);
1974         const char *f2 = func_name (&sinfo->fun[i]);
1975
1976         info->callbacks->einfo (_("warning: %s overlaps %s\n"), f1, f2);
1977         sinfo->fun[i - 1].hi = sinfo->fun[i].lo;
1978       }
1979     else if (insns_at_end (&sinfo->fun[i - 1], sinfo->fun[i].lo))
1980       gaps = TRUE;
1981
1982   if (sinfo->num_fun == 0)
1983     gaps = TRUE;
1984   else
1985     {
1986       if (sinfo->fun[0].lo != 0)
1987         gaps = TRUE;
1988       if (sinfo->fun[sinfo->num_fun - 1].hi > sec->size)
1989         {
1990           const char *f1 = func_name (&sinfo->fun[sinfo->num_fun - 1]);
1991
1992           info->callbacks->einfo (_("warning: %s exceeds section size\n"), f1);
1993           sinfo->fun[sinfo->num_fun - 1].hi = sec->size;
1994         }
1995       else if (insns_at_end (&sinfo->fun[sinfo->num_fun - 1], sec->size))
1996         gaps = TRUE;
1997     }
1998   return gaps;
1999 }
2000
2001 /* Search current function info for a function that contains address
2002    OFFSET in section SEC.  */
2003
2004 static struct function_info *
2005 find_function (asection *sec, bfd_vma offset, struct bfd_link_info *info)
2006 {
2007   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
2008   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
2009   int lo, hi, mid;
2010
2011   lo = 0;
2012   hi = sinfo->num_fun;
2013   while (lo < hi)
2014     {
2015       mid = (lo + hi) / 2;
2016       if (offset < sinfo->fun[mid].lo)
2017         hi = mid;
2018       else if (offset >= sinfo->fun[mid].hi)
2019         lo = mid + 1;
2020       else
2021         return &sinfo->fun[mid];
2022     }
2023   info->callbacks->einfo (_("%A:0x%v not found in function table\n"),
2024                           sec, offset);
2025   return NULL;
2026 }
2027
2028 /* Add CALLEE to CALLER call list if not already present.  Return TRUE
2029    if CALLEE was new.  If this function return FALSE, CALLEE should
2030    be freed.  */
2031
2032 static bfd_boolean
2033 insert_callee (struct function_info *caller, struct call_info *callee)
2034 {
2035   struct call_info **pp, *p;
2036
2037   for (pp = &caller->call_list; (p = *pp) != NULL; pp = &p->next)
2038     if (p->fun == callee->fun)
2039       {
2040         /* Tail calls use less stack than normal calls.  Retain entry
2041            for normal call over one for tail call.  */
2042         p->is_tail &= callee->is_tail;
2043         if (!p->is_tail)
2044           {
2045             p->fun->start = NULL;
2046             p->fun->is_func = TRUE;
2047           }
2048         p->count += 1;
2049         /* Reorder list so most recent call is first.  */
2050         *pp = p->next;
2051         p->next = caller->call_list;
2052         caller->call_list = p;
2053         return FALSE;
2054       }
2055   callee->next = caller->call_list;
2056   callee->count += 1;
2057   caller->call_list = callee;
2058   return TRUE;
2059 }
2060
2061 /* Copy CALL and insert the copy into CALLER.  */
2062
2063 static bfd_boolean
2064 copy_callee (struct function_info *caller, const struct call_info *call)
2065 {
2066   struct call_info *callee;
2067   callee = bfd_malloc (sizeof (*callee));
2068   if (callee == NULL)
2069     return FALSE;
2070   *callee = *call;
2071   if (!insert_callee (caller, callee))
2072     free (callee);
2073   return TRUE;
2074 }
2075
2076 /* We're only interested in code sections.  Testing SEC_IN_MEMORY excludes
2077    overlay stub sections.  */
2078
2079 static bfd_boolean
2080 interesting_section (asection *s, bfd *obfd)
2081 {
2082   return (s->output_section != NULL
2083           && s->output_section->owner == obfd
2084           && ((s->flags & (SEC_ALLOC | SEC_LOAD | SEC_CODE | SEC_IN_MEMORY))
2085               == (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2086           && s->size != 0);
2087 }
2088
2089 /* Rummage through the relocs for SEC, looking for function calls.
2090    If CALL_TREE is true, fill in call graph.  If CALL_TREE is false,
2091    mark destination symbols on calls as being functions.  Also
2092    look at branches, which may be tail calls or go to hot/cold
2093    section part of same function.  */
2094
2095 static bfd_boolean
2096 mark_functions_via_relocs (asection *sec,
2097                            struct bfd_link_info *info,
2098                            int call_tree)
2099 {
2100   Elf_Internal_Rela *internal_relocs, *irelaend, *irela;
2101   Elf_Internal_Shdr *symtab_hdr;
2102   void *psyms;
2103   static bfd_boolean warned;
2104
2105   if (!interesting_section (sec, info->output_bfd)
2106       || sec->reloc_count == 0)
2107     return TRUE;
2108
2109   internal_relocs = _bfd_elf_link_read_relocs (sec->owner, sec, NULL, NULL,
2110                                                info->keep_memory);
2111   if (internal_relocs == NULL)
2112     return FALSE;
2113
2114   symtab_hdr = &elf_tdata (sec->owner)->symtab_hdr;
2115   psyms = &symtab_hdr->contents;
2116   irela = internal_relocs;
2117   irelaend = irela + sec->reloc_count;
2118   for (; irela < irelaend; irela++)
2119     {
2120       enum elf_spu_reloc_type r_type;
2121       unsigned int r_indx;
2122       asection *sym_sec;
2123       Elf_Internal_Sym *sym;
2124       struct elf_link_hash_entry *h;
2125       bfd_vma val;
2126       bfd_boolean reject, is_call;
2127       struct function_info *caller;
2128       struct call_info *callee;
2129
2130       reject = FALSE;
2131       r_type = ELF32_R_TYPE (irela->r_info);
2132       if (r_type != R_SPU_REL16
2133           && r_type != R_SPU_ADDR16)
2134         {
2135           reject = TRUE;
2136           if (!(call_tree && spu_hash_table (info)->auto_overlay))
2137             continue;
2138         }
2139
2140       r_indx = ELF32_R_SYM (irela->r_info);
2141       if (!get_sym_h (&h, &sym, &sym_sec, psyms, r_indx, sec->owner))
2142         return FALSE;
2143
2144       if (sym_sec == NULL
2145           || sym_sec->output_section == NULL
2146           || sym_sec->output_section->owner != info->output_bfd)
2147         continue;
2148
2149       is_call = FALSE;
2150       if (!reject)
2151         {
2152           unsigned char insn[4];
2153
2154           if (!bfd_get_section_contents (sec->owner, sec, insn,
2155                                          irela->r_offset, 4))
2156             return FALSE;
2157           if (is_branch (insn))
2158             {
2159               is_call = (insn[0] & 0xfd) == 0x31;
2160               if ((sym_sec->flags & (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2161                   != (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2162                 {
2163                   if (!warned)
2164                     info->callbacks->einfo
2165                       (_("%B(%A+0x%v): call to non-code section"
2166                          " %B(%A), analysis incomplete\n"),
2167                        sec->owner, sec, irela->r_offset,
2168                        sym_sec->owner, sym_sec);
2169                   warned = TRUE;
2170                   continue;
2171                 }
2172             }
2173           else
2174             {
2175               reject = TRUE;
2176               if (!(call_tree && spu_hash_table (info)->auto_overlay)
2177                   || is_hint (insn))
2178                 continue;
2179             }
2180         }
2181
2182       if (reject)
2183         {
2184           /* For --auto-overlay, count possible stubs we need for
2185              function pointer references.  */
2186           unsigned int sym_type;
2187           if (h)
2188             sym_type = h->type;
2189           else
2190             sym_type = ELF_ST_TYPE (sym->st_info);
2191           if (sym_type == STT_FUNC)
2192             spu_hash_table (info)->non_ovly_stub += 1;
2193           continue;
2194         }
2195
2196       if (h)
2197         val = h->root.u.def.value;
2198       else
2199         val = sym->st_value;
2200       val += irela->r_addend;
2201
2202       if (!call_tree)
2203         {
2204           struct function_info *fun;
2205
2206           if (irela->r_addend != 0)
2207             {
2208               Elf_Internal_Sym *fake = bfd_zmalloc (sizeof (*fake));
2209               if (fake == NULL)
2210                 return FALSE;
2211               fake->st_value = val;
2212               fake->st_shndx
2213                 = _bfd_elf_section_from_bfd_section (sym_sec->owner, sym_sec);
2214               sym = fake;
2215             }
2216           if (sym)
2217             fun = maybe_insert_function (sym_sec, sym, FALSE, is_call);
2218           else
2219             fun = maybe_insert_function (sym_sec, h, TRUE, is_call);
2220           if (fun == NULL)
2221             return FALSE;
2222           if (irela->r_addend != 0
2223               && fun->u.sym != sym)
2224             free (sym);
2225           continue;
2226         }
2227
2228       caller = find_function (sec, irela->r_offset, info);
2229       if (caller == NULL)
2230         return FALSE;
2231       callee = bfd_malloc (sizeof *callee);
2232       if (callee == NULL)
2233         return FALSE;
2234
2235       callee->fun = find_function (sym_sec, val, info);
2236       if (callee->fun == NULL)
2237         return FALSE;
2238       callee->is_tail = !is_call;
2239       callee->is_pasted = FALSE;
2240       callee->count = 0;
2241       if (callee->fun->last_caller != sec)
2242         {
2243           callee->fun->last_caller = sec;
2244           callee->fun->call_count += 1;
2245         }
2246       if (!insert_callee (caller, callee))
2247         free (callee);
2248       else if (!is_call
2249                && !callee->fun->is_func
2250                && callee->fun->stack == 0)
2251         {
2252           /* This is either a tail call or a branch from one part of
2253              the function to another, ie. hot/cold section.  If the
2254              destination has been called by some other function then
2255              it is a separate function.  We also assume that functions
2256              are not split across input files.  */
2257           if (sec->owner != sym_sec->owner)
2258             {
2259               callee->fun->start = NULL;
2260               callee->fun->is_func = TRUE;
2261             }
2262           else if (callee->fun->start == NULL)
2263             callee->fun->start = caller;
2264           else
2265             {
2266               struct function_info *callee_start;
2267               struct function_info *caller_start;
2268               callee_start = callee->fun;
2269               while (callee_start->start)
2270                 callee_start = callee_start->start;
2271               caller_start = caller;
2272               while (caller_start->start)
2273                 caller_start = caller_start->start;
2274               if (caller_start != callee_start)
2275                 {
2276                   callee->fun->start = NULL;
2277                   callee->fun->is_func = TRUE;
2278                 }
2279             }
2280         }
2281     }
2282
2283   return TRUE;
2284 }
2285
2286 /* Handle something like .init or .fini, which has a piece of a function.
2287    These sections are pasted together to form a single function.  */
2288
2289 static bfd_boolean
2290 pasted_function (asection *sec, struct bfd_link_info *info)
2291 {
2292   struct bfd_link_order *l;
2293   struct _spu_elf_section_data *sec_data;
2294   struct spu_elf_stack_info *sinfo;
2295   Elf_Internal_Sym *fake;
2296   struct function_info *fun, *fun_start;
2297
2298   fake = bfd_zmalloc (sizeof (*fake));
2299   if (fake == NULL)
2300     return FALSE;
2301   fake->st_value = 0;
2302   fake->st_size = sec->size;
2303   fake->st_shndx
2304     = _bfd_elf_section_from_bfd_section (sec->owner, sec);
2305   fun = maybe_insert_function (sec, fake, FALSE, FALSE);
2306   if (!fun)
2307     return FALSE;
2308
2309   /* Find a function immediately preceding this section.  */
2310   fun_start = NULL;
2311   for (l = sec->output_section->map_head.link_order; l != NULL; l = l->next)
2312     {
2313       if (l->u.indirect.section == sec)
2314         {
2315           if (fun_start != NULL)
2316             {
2317               struct call_info *callee = bfd_malloc (sizeof *callee);
2318               if (callee == NULL)
2319                 return FALSE;
2320
2321               fun->start = fun_start;
2322               callee->fun = fun;
2323               callee->is_tail = TRUE;
2324               callee->is_pasted = TRUE;
2325               callee->count = 0;
2326               if (!insert_callee (fun_start, callee))
2327                 free (callee);
2328               return TRUE;
2329             }
2330           break;
2331         }
2332       if (l->type == bfd_indirect_link_order
2333           && (sec_data = spu_elf_section_data (l->u.indirect.section)) != NULL
2334           && (sinfo = sec_data->u.i.stack_info) != NULL
2335           && sinfo->num_fun != 0)
2336         fun_start = &sinfo->fun[sinfo->num_fun - 1];
2337     }
2338
2339   info->callbacks->einfo (_("%A link_order not found\n"), sec);
2340   return FALSE;
2341 }
2342
2343 /* Map address ranges in code sections to functions.  */
2344
2345 static bfd_boolean
2346 discover_functions (struct bfd_link_info *info)
2347 {
2348   bfd *ibfd;
2349   int bfd_idx;
2350   Elf_Internal_Sym ***psym_arr;
2351   asection ***sec_arr;
2352   bfd_boolean gaps = FALSE;
2353
2354   bfd_idx = 0;
2355   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
2356     bfd_idx++;
2357
2358   psym_arr = bfd_zmalloc (bfd_idx * sizeof (*psym_arr));
2359   if (psym_arr == NULL)
2360     return FALSE;
2361   sec_arr = bfd_zmalloc (bfd_idx * sizeof (*sec_arr));
2362   if (sec_arr == NULL)
2363     return FALSE;
2364
2365
2366   for (ibfd = info->input_bfds, bfd_idx = 0;
2367        ibfd != NULL;
2368        ibfd = ibfd->link_next, bfd_idx++)
2369     {
2370       extern const bfd_target bfd_elf32_spu_vec;
2371       Elf_Internal_Shdr *symtab_hdr;
2372       asection *sec;
2373       size_t symcount;
2374       Elf_Internal_Sym *syms, *sy, **psyms, **psy;
2375       asection **psecs, **p;
2376
2377       if (ibfd->xvec != &bfd_elf32_spu_vec)
2378         continue;
2379
2380       /* Read all the symbols.  */
2381       symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
2382       symcount = symtab_hdr->sh_size / symtab_hdr->sh_entsize;
2383       if (symcount == 0)
2384         {
2385           if (!gaps)
2386             for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
2387               if (interesting_section (sec, info->output_bfd))
2388                 {
2389                   gaps = TRUE;
2390                   break;
2391                 }
2392           continue;
2393         }
2394
2395       if (symtab_hdr->contents != NULL)
2396         {
2397           /* Don't use cached symbols since the generic ELF linker
2398              code only reads local symbols, and we need globals too.  */
2399           free (symtab_hdr->contents);
2400           symtab_hdr->contents = NULL;
2401         }
2402       syms = bfd_elf_get_elf_syms (ibfd, symtab_hdr, symcount, 0,
2403                                    NULL, NULL, NULL);
2404       symtab_hdr->contents = (void *) syms;
2405       if (syms == NULL)
2406         return FALSE;
2407
2408       /* Select defined function symbols that are going to be output.  */
2409       psyms = bfd_malloc ((symcount + 1) * sizeof (*psyms));
2410       if (psyms == NULL)
2411         return FALSE;
2412       psym_arr[bfd_idx] = psyms;
2413       psecs = bfd_malloc (symcount * sizeof (*psecs));
2414       if (psecs == NULL)
2415         return FALSE;
2416       sec_arr[bfd_idx] = psecs;
2417       for (psy = psyms, p = psecs, sy = syms; sy < syms + symcount; ++p, ++sy)
2418         if (ELF_ST_TYPE (sy->st_info) == STT_NOTYPE
2419             || ELF_ST_TYPE (sy->st_info) == STT_FUNC)
2420           {
2421             asection *s;
2422
2423             *p = s = bfd_section_from_elf_index (ibfd, sy->st_shndx);
2424             if (s != NULL && interesting_section (s, info->output_bfd))
2425               *psy++ = sy;
2426           }
2427       symcount = psy - psyms;
2428       *psy = NULL;
2429
2430       /* Sort them by section and offset within section.  */
2431       sort_syms_syms = syms;
2432       sort_syms_psecs = psecs;
2433       qsort (psyms, symcount, sizeof (*psyms), sort_syms);
2434
2435       /* Now inspect the function symbols.  */
2436       for (psy = psyms; psy < psyms + symcount; )
2437         {
2438           asection *s = psecs[*psy - syms];
2439           Elf_Internal_Sym **psy2;
2440
2441           for (psy2 = psy; ++psy2 < psyms + symcount; )
2442             if (psecs[*psy2 - syms] != s)
2443               break;
2444
2445           if (!alloc_stack_info (s, psy2 - psy))
2446             return FALSE;
2447           psy = psy2;
2448         }
2449
2450       /* First install info about properly typed and sized functions.
2451          In an ideal world this will cover all code sections, except
2452          when partitioning functions into hot and cold sections,
2453          and the horrible pasted together .init and .fini functions.  */
2454       for (psy = psyms; psy < psyms + symcount; ++psy)
2455         {
2456           sy = *psy;
2457           if (ELF_ST_TYPE (sy->st_info) == STT_FUNC)
2458             {
2459               asection *s = psecs[sy - syms];
2460               if (!maybe_insert_function (s, sy, FALSE, TRUE))
2461                 return FALSE;
2462             }
2463         }
2464
2465       for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
2466         if (interesting_section (sec, info->output_bfd))
2467           gaps |= check_function_ranges (sec, info);
2468     }
2469
2470   if (gaps)
2471     {
2472       /* See if we can discover more function symbols by looking at
2473          relocations.  */
2474       for (ibfd = info->input_bfds, bfd_idx = 0;
2475            ibfd != NULL;
2476            ibfd = ibfd->link_next, bfd_idx++)
2477         {
2478           asection *sec;
2479
2480           if (psym_arr[bfd_idx] == NULL)
2481             continue;
2482
2483           for (sec = ibfd->sections; sec != NULL; sec = sec->next)
2484             if (!mark_functions_via_relocs (sec, info, FALSE))
2485               return FALSE;
2486         }
2487
2488       for (ibfd = info->input_bfds, bfd_idx = 0;
2489            ibfd != NULL;
2490            ibfd = ibfd->link_next, bfd_idx++)
2491         {
2492           Elf_Internal_Shdr *symtab_hdr;
2493           asection *sec;
2494           Elf_Internal_Sym *syms, *sy, **psyms, **psy;
2495           asection **psecs;
2496
2497           if ((psyms = psym_arr[bfd_idx]) == NULL)
2498             continue;
2499
2500           psecs = sec_arr[bfd_idx];
2501
2502           symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
2503           syms = (Elf_Internal_Sym *) symtab_hdr->contents;
2504
2505           gaps = FALSE;
2506           for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
2507             if (interesting_section (sec, info->output_bfd))
2508               gaps |= check_function_ranges (sec, info);
2509           if (!gaps)
2510             continue;
2511
2512           /* Finally, install all globals.  */
2513           for (psy = psyms; (sy = *psy) != NULL; ++psy)
2514             {
2515               asection *s;
2516
2517               s = psecs[sy - syms];
2518
2519               /* Global syms might be improperly typed functions.  */
2520               if (ELF_ST_TYPE (sy->st_info) != STT_FUNC
2521                   && ELF_ST_BIND (sy->st_info) == STB_GLOBAL)
2522                 {
2523                   if (!maybe_insert_function (s, sy, FALSE, FALSE))
2524                     return FALSE;
2525                 }
2526             }
2527         }
2528
2529       for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
2530         {
2531           extern const bfd_target bfd_elf32_spu_vec;
2532           asection *sec;
2533
2534           if (ibfd->xvec != &bfd_elf32_spu_vec)
2535             continue;
2536
2537           /* Some of the symbols we've installed as marking the
2538              beginning of functions may have a size of zero.  Extend
2539              the range of such functions to the beginning of the
2540              next symbol of interest.  */
2541           for (sec = ibfd->sections; sec != NULL; sec = sec->next)
2542             if (interesting_section (sec, info->output_bfd))
2543               {
2544                 struct _spu_elf_section_data *sec_data;
2545                 struct spu_elf_stack_info *sinfo;
2546
2547                 sec_data = spu_elf_section_data (sec);
2548                 sinfo = sec_data->u.i.stack_info;
2549                 if (sinfo != NULL)
2550                   {
2551                     int fun_idx;
2552                     bfd_vma hi = sec->size;
2553
2554                     for (fun_idx = sinfo->num_fun; --fun_idx >= 0; )
2555                       {
2556                         sinfo->fun[fun_idx].hi = hi;
2557                         hi = sinfo->fun[fun_idx].lo;
2558                       }
2559                   }
2560                 /* No symbols in this section.  Must be .init or .fini
2561                    or something similar.  */
2562                 else if (!pasted_function (sec, info))
2563                   return FALSE;
2564               }
2565         }
2566     }
2567
2568   for (ibfd = info->input_bfds, bfd_idx = 0;
2569        ibfd != NULL;
2570        ibfd = ibfd->link_next, bfd_idx++)
2571     {
2572       if (psym_arr[bfd_idx] == NULL)
2573         continue;
2574
2575       free (psym_arr[bfd_idx]);
2576       free (sec_arr[bfd_idx]);
2577     }
2578
2579   free (psym_arr);
2580   free (sec_arr);
2581
2582   return TRUE;
2583 }
2584
2585 /* Iterate over all function_info we have collected, calling DOIT on
2586    each node if ROOT_ONLY is false.  Only call DOIT on root nodes
2587    if ROOT_ONLY.  */
2588
2589 static bfd_boolean
2590 for_each_node (bfd_boolean (*doit) (struct function_info *,
2591                                     struct bfd_link_info *,
2592                                     void *),
2593                struct bfd_link_info *info,
2594                void *param,
2595                int root_only)
2596 {
2597   bfd *ibfd;
2598
2599   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
2600     {
2601       extern const bfd_target bfd_elf32_spu_vec;
2602       asection *sec;
2603
2604       if (ibfd->xvec != &bfd_elf32_spu_vec)
2605         continue;
2606
2607       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
2608         {
2609           struct _spu_elf_section_data *sec_data;
2610           struct spu_elf_stack_info *sinfo;
2611
2612           if ((sec_data = spu_elf_section_data (sec)) != NULL
2613               && (sinfo = sec_data->u.i.stack_info) != NULL)
2614             {
2615               int i;
2616               for (i = 0; i < sinfo->num_fun; ++i)
2617                 if (!root_only || !sinfo->fun[i].non_root)
2618                   if (!doit (&sinfo->fun[i], info, param))
2619                     return FALSE;
2620             }
2621         }
2622     }
2623   return TRUE;
2624 }
2625
2626 /* Transfer call info attached to struct function_info entries for
2627    all of a given function's sections to the first entry.  */
2628
2629 static bfd_boolean
2630 transfer_calls (struct function_info *fun,
2631                 struct bfd_link_info *info ATTRIBUTE_UNUSED,
2632                 void *param ATTRIBUTE_UNUSED)
2633 {
2634   struct function_info *start = fun->start;
2635
2636   if (start != NULL)
2637     {
2638       struct call_info *call, *call_next;
2639
2640       while (start->start != NULL)
2641         start = start->start;
2642       for (call = fun->call_list; call != NULL; call = call_next)
2643         {
2644           call_next = call->next;
2645           if (!insert_callee (start, call))
2646             free (call);
2647         }
2648       fun->call_list = NULL;
2649     }
2650   return TRUE;
2651 }
2652
2653 /* Mark nodes in the call graph that are called by some other node.  */
2654
2655 static bfd_boolean
2656 mark_non_root (struct function_info *fun,
2657                struct bfd_link_info *info ATTRIBUTE_UNUSED,
2658                void *param ATTRIBUTE_UNUSED)
2659 {
2660   struct call_info *call;
2661
2662   if (fun->visit1)
2663     return TRUE;
2664   fun->visit1 = TRUE;
2665   for (call = fun->call_list; call; call = call->next)
2666     {
2667       call->fun->non_root = TRUE;
2668       mark_non_root (call->fun, 0, 0);
2669     }
2670   return TRUE;
2671 }
2672
2673 /* Remove cycles from the call graph.  Set depth of nodes.  */
2674
2675 static bfd_boolean
2676 remove_cycles (struct function_info *fun,
2677                struct bfd_link_info *info,
2678                void *param)
2679 {
2680   struct call_info **callp, *call;
2681   unsigned int depth = *(unsigned int *) param;
2682   unsigned int max_depth = depth;
2683
2684   fun->depth = depth;
2685   fun->visit2 = TRUE;
2686   fun->marking = TRUE;
2687
2688   callp = &fun->call_list;
2689   while ((call = *callp) != NULL)
2690     {
2691       if (!call->fun->visit2)
2692         {
2693           call->max_depth = depth + !call->is_pasted;
2694           if (!remove_cycles (call->fun, info, &call->max_depth))
2695             return FALSE;
2696           if (max_depth < call->max_depth)
2697             max_depth = call->max_depth;
2698         }
2699       else if (call->fun->marking)
2700         {
2701           if (!spu_hash_table (info)->auto_overlay)
2702             {
2703               const char *f1 = func_name (fun);
2704               const char *f2 = func_name (call->fun);
2705
2706               info->callbacks->info (_("Stack analysis will ignore the call "
2707                                        "from %s to %s\n"),
2708                                      f1, f2);
2709             }
2710           *callp = call->next;
2711           free (call);
2712           continue;
2713         }
2714       callp = &call->next;
2715     }
2716   fun->marking = FALSE;
2717   *(unsigned int *) param = max_depth;
2718   return TRUE;
2719 }
2720
2721 /* Populate call_list for each function.  */
2722
2723 static bfd_boolean
2724 build_call_tree (struct bfd_link_info *info)
2725 {
2726   bfd *ibfd;
2727   unsigned int depth;
2728
2729   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
2730     {
2731       extern const bfd_target bfd_elf32_spu_vec;
2732       asection *sec;
2733
2734       if (ibfd->xvec != &bfd_elf32_spu_vec)
2735         continue;
2736
2737       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
2738         if (!mark_functions_via_relocs (sec, info, TRUE))
2739           return FALSE;
2740     }
2741
2742   /* Transfer call info from hot/cold section part of function
2743      to main entry.  */
2744   if (!spu_hash_table (info)->auto_overlay
2745       && !for_each_node (transfer_calls, info, 0, FALSE))
2746     return FALSE;
2747
2748   /* Find the call graph root(s).  */
2749   if (!for_each_node (mark_non_root, info, 0, FALSE))
2750     return FALSE;
2751
2752   /* Remove cycles from the call graph.  We start from the root node(s)
2753      so that we break cycles in a reasonable place.  */
2754   depth = 0;
2755   return for_each_node (remove_cycles, info, &depth, TRUE);
2756 }
2757
2758 /* qsort predicate to sort calls by max_depth then count.  */
2759
2760 static int
2761 sort_calls (const void *a, const void *b)
2762 {
2763   struct call_info *const *c1 = a;
2764   struct call_info *const *c2 = b;
2765   int delta;
2766
2767   delta = (*c2)->max_depth - (*c1)->max_depth;
2768   if (delta != 0)
2769     return delta;
2770
2771   delta = (*c2)->count - (*c1)->count;
2772   if (delta != 0)
2773     return delta;
2774
2775   return c1 - c2;
2776 }
2777
2778 struct _mos_param {
2779   unsigned int max_overlay_size;
2780 };
2781
2782 /* Set linker_mark and gc_mark on any sections that we will put in
2783    overlays.  These flags are used by the generic ELF linker, but we
2784    won't be continuing on to bfd_elf_final_link so it is OK to use
2785    them.  linker_mark is clear before we get here.  Set segment_mark
2786    on sections that are part of a pasted function (excluding the last
2787    section).
2788
2789    Set up function rodata section if --overlay-rodata.  We don't
2790    currently include merged string constant rodata sections since
2791
2792    Sort the call graph so that the deepest nodes will be visited
2793    first.  */
2794
2795 static bfd_boolean
2796 mark_overlay_section (struct function_info *fun,
2797                       struct bfd_link_info *info,
2798                       void *param)
2799 {
2800   struct call_info *call;
2801   unsigned int count;
2802   struct _mos_param *mos_param = param;
2803
2804   if (fun->visit4)
2805     return TRUE;
2806
2807   fun->visit4 = TRUE;
2808   if (!fun->sec->linker_mark)
2809     {
2810       fun->sec->linker_mark = 1;
2811       fun->sec->gc_mark = 1;
2812       fun->sec->segment_mark = 0;
2813       /* Ensure SEC_CODE is set on this text section (it ought to
2814          be!), and SEC_CODE is clear on rodata sections.  We use
2815          this flag to differentiate the two overlay section types.  */
2816       fun->sec->flags |= SEC_CODE;
2817       if (spu_hash_table (info)->auto_overlay & OVERLAY_RODATA)
2818         {
2819           char *name = NULL;
2820           unsigned int size;
2821
2822           /* Find the rodata section corresponding to this function's
2823              text section.  */
2824           if (strcmp (fun->sec->name, ".text") == 0)
2825             {
2826               name = bfd_malloc (sizeof (".rodata"));
2827               if (name == NULL)
2828                 return FALSE;
2829               memcpy (name, ".rodata", sizeof (".rodata"));
2830             }
2831           else if (strncmp (fun->sec->name, ".text.", 6) == 0)
2832             {
2833               size_t len = strlen (fun->sec->name);
2834               name = bfd_malloc (len + 3);
2835               if (name == NULL)
2836                 return FALSE;
2837               memcpy (name, ".rodata", sizeof (".rodata"));
2838               memcpy (name + 7, fun->sec->name + 5, len - 4);
2839             }
2840           else if (strncmp (fun->sec->name, ".gnu.linkonce.t.", 16) == 0)
2841             {
2842               size_t len = strlen (fun->sec->name) + 1;
2843               name = bfd_malloc (len);
2844               if (name == NULL)
2845                 return FALSE;
2846               memcpy (name, fun->sec->name, len);
2847               name[14] = 'r';
2848             }
2849
2850           if (name != NULL)
2851             {
2852               asection *rodata = NULL;
2853               asection *group_sec = elf_section_data (fun->sec)->next_in_group;
2854               if (group_sec == NULL)
2855                 rodata = bfd_get_section_by_name (fun->sec->owner, name);
2856               else
2857                 while (group_sec != NULL && group_sec != fun->sec)
2858                   {
2859                     if (strcmp (group_sec->name, name) == 0)
2860                       {
2861                         rodata = group_sec;
2862                         break;
2863                       }
2864                     group_sec = elf_section_data (group_sec)->next_in_group;
2865                   }
2866               fun->rodata = rodata;
2867               if (fun->rodata)
2868                 {
2869                   fun->rodata->linker_mark = 1;
2870                   fun->rodata->gc_mark = 1;
2871                   fun->rodata->flags &= ~SEC_CODE;
2872                 }
2873               free (name);
2874             }
2875           size = fun->sec->size;
2876           if (fun->rodata)
2877             size += fun->rodata->size;
2878           if (mos_param->max_overlay_size < size)
2879             mos_param->max_overlay_size = size;
2880         }
2881     }
2882
2883   for (count = 0, call = fun->call_list; call != NULL; call = call->next)
2884     count += 1;
2885
2886   if (count > 1)
2887     {
2888       struct call_info **calls = bfd_malloc (count * sizeof (*calls));
2889       if (calls == NULL)
2890         return FALSE;
2891
2892       for (count = 0, call = fun->call_list; call != NULL; call = call->next)
2893         calls[count++] = call;
2894
2895       qsort (calls, count, sizeof (*calls), sort_calls);
2896
2897       fun->call_list = NULL;
2898       while (count != 0)
2899         {
2900           --count;
2901           calls[count]->next = fun->call_list;
2902           fun->call_list = calls[count];
2903         }
2904       free (calls);
2905     }
2906
2907   for (call = fun->call_list; call != NULL; call = call->next)
2908     {
2909       if (call->is_pasted)
2910         {
2911           /* There can only be one is_pasted call per function_info.  */
2912           BFD_ASSERT (!fun->sec->segment_mark);
2913           fun->sec->segment_mark = 1;
2914         }
2915       if (!mark_overlay_section (call->fun, info, param))
2916         return FALSE;
2917     }
2918
2919   /* Don't put entry code into an overlay.  The overlay manager needs
2920      a stack!  */
2921   if (fun->lo + fun->sec->output_offset + fun->sec->output_section->vma
2922       == info->output_bfd->start_address)
2923     {
2924       fun->sec->linker_mark = 0;
2925       if (fun->rodata != NULL)
2926         fun->rodata->linker_mark = 0;
2927     }
2928   return TRUE;
2929 }
2930
2931 /* If non-zero then unmark functions called from those within sections
2932    that we need to unmark.  Unfortunately this isn't reliable since the
2933    call graph cannot know the destination of function pointer calls.  */
2934 #define RECURSE_UNMARK 0
2935
2936 struct _uos_param {
2937   asection *exclude_input_section;
2938   asection *exclude_output_section;
2939   unsigned long clearing;
2940 };
2941
2942 /* Undo some of mark_overlay_section's work.  */
2943
2944 static bfd_boolean
2945 unmark_overlay_section (struct function_info *fun,
2946                         struct bfd_link_info *info,
2947                         void *param)
2948 {
2949   struct call_info *call;
2950   struct _uos_param *uos_param = param;
2951   unsigned int excluded = 0;
2952
2953   if (fun->visit5)
2954     return TRUE;
2955
2956   fun->visit5 = TRUE;
2957
2958   excluded = 0;
2959   if (fun->sec == uos_param->exclude_input_section
2960       || fun->sec->output_section == uos_param->exclude_output_section)
2961     excluded = 1;
2962
2963   if (RECURSE_UNMARK)
2964     uos_param->clearing += excluded;
2965
2966   if (RECURSE_UNMARK ? uos_param->clearing : excluded)
2967     {
2968       fun->sec->linker_mark = 0;
2969       if (fun->rodata)
2970         fun->rodata->linker_mark = 0;
2971     }
2972
2973   for (call = fun->call_list; call != NULL; call = call->next)
2974     if (!unmark_overlay_section (call->fun, info, param))
2975       return FALSE;
2976
2977   if (RECURSE_UNMARK)
2978     uos_param->clearing -= excluded;
2979   return TRUE;
2980 }
2981
2982 struct _cl_param {
2983   unsigned int lib_size;
2984   asection **lib_sections;
2985 };
2986
2987 /* Add sections we have marked as belonging to overlays to an array
2988    for consideration as non-overlay sections.  The array consist of
2989    pairs of sections, (text,rodata), for functions in the call graph.  */
2990
2991 static bfd_boolean
2992 collect_lib_sections (struct function_info *fun,
2993                       struct bfd_link_info *info,
2994                       void *param)
2995 {
2996   struct _cl_param *lib_param = param;
2997   struct call_info *call;
2998   unsigned int size;
2999
3000   if (fun->visit6)
3001     return TRUE;
3002
3003   fun->visit6 = TRUE;
3004   if (!fun->sec->linker_mark || !fun->sec->gc_mark || fun->sec->segment_mark)
3005     return TRUE;
3006
3007   size = fun->sec->size;
3008   if (fun->rodata)
3009     size += fun->rodata->size;
3010   if (size > lib_param->lib_size)
3011     return TRUE;
3012
3013   *lib_param->lib_sections++ = fun->sec;
3014   fun->sec->gc_mark = 0;
3015   if (fun->rodata && fun->rodata->linker_mark && fun->rodata->gc_mark)
3016     {
3017       *lib_param->lib_sections++ = fun->rodata;
3018       fun->rodata->gc_mark = 0;
3019     }
3020   else
3021     *lib_param->lib_sections++ = NULL;
3022
3023   for (call = fun->call_list; call != NULL; call = call->next)
3024     collect_lib_sections (call->fun, info, param);
3025
3026   return TRUE;
3027 }
3028
3029 /* qsort predicate to sort sections by call count.  */
3030
3031 static int
3032 sort_lib (const void *a, const void *b)
3033 {
3034   asection *const *s1 = a;
3035   asection *const *s2 = b;
3036   struct _spu_elf_section_data *sec_data;
3037   struct spu_elf_stack_info *sinfo;
3038   int delta;
3039
3040   delta = 0;
3041   if ((sec_data = spu_elf_section_data (*s1)) != NULL
3042       && (sinfo = sec_data->u.i.stack_info) != NULL)
3043     {
3044       int i;
3045       for (i = 0; i < sinfo->num_fun; ++i)
3046         delta -= sinfo->fun[i].call_count;
3047     }
3048
3049   if ((sec_data = spu_elf_section_data (*s2)) != NULL
3050       && (sinfo = sec_data->u.i.stack_info) != NULL)
3051     {
3052       int i;
3053       for (i = 0; i < sinfo->num_fun; ++i)
3054         delta += sinfo->fun[i].call_count;
3055     }
3056
3057   if (delta != 0)
3058     return delta;
3059
3060   return s1 - s2;
3061 }
3062
3063 /* Remove some sections from those marked to be in overlays.  Choose
3064    those that are called from many places, likely library functions.  */
3065
3066 static unsigned int
3067 auto_ovl_lib_functions (struct bfd_link_info *info, unsigned int lib_size)
3068 {
3069   bfd *ibfd;
3070   asection **lib_sections;
3071   unsigned int i, lib_count;
3072   struct _cl_param collect_lib_param;
3073   struct function_info dummy_caller;
3074
3075   memset (&dummy_caller, 0, sizeof (dummy_caller));
3076   lib_count = 0;
3077   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
3078     {
3079       extern const bfd_target bfd_elf32_spu_vec;
3080       asection *sec;
3081
3082       if (ibfd->xvec != &bfd_elf32_spu_vec)
3083         continue;
3084
3085       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
3086         if (sec->linker_mark
3087             && sec->size < lib_size
3088             && (sec->flags & SEC_CODE) != 0)
3089           lib_count += 1;
3090     }
3091   lib_sections = bfd_malloc (lib_count * 2 * sizeof (*lib_sections));
3092   if (lib_sections == NULL)
3093     return (unsigned int) -1;
3094   collect_lib_param.lib_size = lib_size;
3095   collect_lib_param.lib_sections = lib_sections;
3096   if (!for_each_node (collect_lib_sections, info, &collect_lib_param,
3097                       TRUE))
3098     return (unsigned int) -1;
3099   lib_count = (collect_lib_param.lib_sections - lib_sections) / 2;
3100
3101   /* Sort sections so that those with the most calls are first.  */
3102   if (lib_count > 1)
3103     qsort (lib_sections, lib_count, 2 * sizeof (*lib_sections), sort_lib);
3104
3105   for (i = 0; i < lib_count; i++)
3106     {
3107       unsigned int tmp, stub_size;
3108       asection *sec;
3109       struct _spu_elf_section_data *sec_data;
3110       struct spu_elf_stack_info *sinfo;
3111
3112       sec = lib_sections[2 * i];
3113       /* If this section is OK, its size must be less than lib_size.  */
3114       tmp = sec->size;
3115       /* If it has a rodata section, then add that too.  */
3116       if (lib_sections[2 * i + 1])
3117         tmp += lib_sections[2 * i + 1]->size;
3118       /* Add any new overlay call stubs needed by the section.  */
3119       stub_size = 0;
3120       if (tmp < lib_size
3121           && (sec_data = spu_elf_section_data (sec)) != NULL
3122           && (sinfo = sec_data->u.i.stack_info) != NULL)
3123         {
3124           int k;
3125           struct call_info *call;
3126
3127           for (k = 0; k < sinfo->num_fun; ++k)
3128             for (call = sinfo->fun[k].call_list; call; call = call->next)
3129               if (call->fun->sec->linker_mark)
3130                 {
3131                   struct call_info *p;
3132                   for (p = dummy_caller.call_list; p; p = p->next)
3133                     if (p->fun == call->fun)
3134                       break;
3135                   if (!p)
3136                     stub_size += OVL_STUB_SIZE;
3137                 }
3138         }
3139       if (tmp + stub_size < lib_size)
3140         {
3141           struct call_info **pp, *p;
3142
3143           /* This section fits.  Mark it as non-overlay.  */
3144           lib_sections[2 * i]->linker_mark = 0;
3145           if (lib_sections[2 * i + 1])
3146             lib_sections[2 * i + 1]->linker_mark = 0;
3147           lib_size -= tmp + stub_size;
3148           /* Call stubs to the section we just added are no longer
3149              needed.  */
3150           pp = &dummy_caller.call_list;
3151           while ((p = *pp) != NULL)
3152             if (!p->fun->sec->linker_mark)
3153               {
3154                 lib_size += OVL_STUB_SIZE;
3155                 *pp = p->next;
3156                 free (p);
3157               }
3158             else
3159               pp = &p->next;
3160           /* Add new call stubs to dummy_caller.  */
3161           if ((sec_data = spu_elf_section_data (sec)) != NULL
3162               && (sinfo = sec_data->u.i.stack_info) != NULL)
3163             {
3164               int k;
3165               struct call_info *call;
3166
3167               for (k = 0; k < sinfo->num_fun; ++k)
3168                 for (call = sinfo->fun[k].call_list;
3169                      call;
3170                      call = call->next)
3171                   if (call->fun->sec->linker_mark)
3172                     {
3173                       struct call_info *callee;
3174                       callee = bfd_malloc (sizeof (*callee));
3175                       if (callee == NULL)
3176                         return (unsigned int) -1;
3177                       *callee = *call;
3178                       if (!insert_callee (&dummy_caller, callee))
3179                         free (callee);
3180                     }
3181             }
3182         }
3183     }
3184   while (dummy_caller.call_list != NULL)
3185     {
3186       struct call_info *call = dummy_caller.call_list;
3187       dummy_caller.call_list = call->next;
3188       free (call);
3189     }
3190   for (i = 0; i < 2 * lib_count; i++)
3191     if (lib_sections[i])
3192       lib_sections[i]->gc_mark = 1;
3193   free (lib_sections);
3194   return lib_size;
3195 }
3196
3197 /* Build an array of overlay sections.  The deepest node's section is
3198    added first, then its parent node's section, then everything called
3199    from the parent section.  The idea being to group sections to
3200    minimise calls between different overlays.  */
3201
3202 static bfd_boolean
3203 collect_overlays (struct function_info *fun,
3204                   struct bfd_link_info *info,
3205                   void *param)
3206 {
3207   struct call_info *call;
3208   bfd_boolean added_fun;
3209   asection ***ovly_sections = param;
3210
3211   if (fun->visit7)
3212     return TRUE;
3213
3214   fun->visit7 = TRUE;
3215   for (call = fun->call_list; call != NULL; call = call->next)
3216     if (!call->is_pasted)
3217       {
3218         if (!collect_overlays (call->fun, info, ovly_sections))
3219           return FALSE;
3220         break;
3221       }
3222
3223   added_fun = FALSE;
3224   if (fun->sec->linker_mark && fun->sec->gc_mark)
3225     {
3226       fun->sec->gc_mark = 0;
3227       *(*ovly_sections)++ = fun->sec;
3228       if (fun->rodata && fun->rodata->linker_mark && fun->rodata->gc_mark)
3229         {
3230           fun->rodata->gc_mark = 0;
3231           *(*ovly_sections)++ = fun->rodata;
3232         }
3233       else
3234         *(*ovly_sections)++ = NULL;
3235       added_fun = TRUE;
3236
3237       /* Pasted sections must stay with the first section.  We don't
3238          put pasted sections in the array, just the first section.
3239          Mark subsequent sections as already considered.  */
3240       if (fun->sec->segment_mark)
3241         {
3242           struct function_info *call_fun = fun;
3243           do
3244             {
3245               for (call = call_fun->call_list; call != NULL; call = call->next)
3246                 if (call->is_pasted)
3247                   {
3248                     call_fun = call->fun;
3249                     call_fun->sec->gc_mark = 0;
3250                     if (call_fun->rodata)
3251                       call_fun->rodata->gc_mark = 0;
3252                     break;
3253                   }
3254               if (call == NULL)
3255                 abort ();
3256             }
3257           while (call_fun->sec->segment_mark);
3258         }
3259     }
3260
3261   for (call = fun->call_list; call != NULL; call = call->next)
3262     if (!collect_overlays (call->fun, info, ovly_sections))
3263       return FALSE;
3264
3265   if (added_fun)
3266     {
3267       struct _spu_elf_section_data *sec_data;
3268       struct spu_elf_stack_info *sinfo;
3269
3270       if ((sec_data = spu_elf_section_data (fun->sec)) != NULL
3271           && (sinfo = sec_data->u.i.stack_info) != NULL)
3272         {
3273           int i;
3274           for (i = 0; i < sinfo->num_fun; ++i)
3275             if (!collect_overlays (&sinfo->fun[i], info, ovly_sections))
3276               return FALSE;
3277         }
3278     }
3279
3280   return TRUE;
3281 }
3282
3283 struct _sum_stack_param {
3284   size_t cum_stack;
3285   size_t overall_stack;
3286   bfd_boolean emit_stack_syms;
3287 };
3288
3289 /* Descend the call graph for FUN, accumulating total stack required.  */
3290
3291 static bfd_boolean
3292 sum_stack (struct function_info *fun,
3293            struct bfd_link_info *info,
3294            void *param)
3295 {
3296   struct call_info *call;
3297   struct function_info *max;
3298   size_t stack, cum_stack;
3299   const char *f1;
3300   bfd_boolean has_call;
3301   struct _sum_stack_param *sum_stack_param = param;
3302   struct spu_link_hash_table *htab;
3303
3304   cum_stack = fun->stack;
3305   sum_stack_param->cum_stack = cum_stack;
3306   if (fun->visit3)
3307     return TRUE;
3308
3309   has_call = FALSE;
3310   max = NULL;
3311   for (call = fun->call_list; call; call = call->next)
3312     {
3313       if (!call->is_pasted)
3314         has_call = TRUE;
3315       if (!sum_stack (call->fun, info, sum_stack_param))
3316         return FALSE;
3317       stack = sum_stack_param->cum_stack;
3318       /* Include caller stack for normal calls, don't do so for
3319          tail calls.  fun->stack here is local stack usage for
3320          this function.  */
3321       if (!call->is_tail || call->is_pasted || call->fun->start != NULL)
3322         stack += fun->stack;
3323       if (cum_stack < stack)
3324         {
3325           cum_stack = stack;
3326           max = call->fun;
3327         }
3328     }
3329
3330   sum_stack_param->cum_stack = cum_stack;
3331   stack = fun->stack;
3332   /* Now fun->stack holds cumulative stack.  */
3333   fun->stack = cum_stack;
3334   fun->visit3 = TRUE;
3335
3336   if (!fun->non_root
3337       && sum_stack_param->overall_stack < cum_stack)
3338     sum_stack_param->overall_stack = cum_stack;
3339
3340   htab = spu_hash_table (info);
3341   if (htab->auto_overlay)
3342     return TRUE;
3343
3344   f1 = func_name (fun);
3345   if (!fun->non_root)
3346     info->callbacks->info (_("  %s: 0x%v\n"), f1, (bfd_vma) cum_stack);
3347   info->callbacks->minfo (_("%s: 0x%v 0x%v\n"),
3348                           f1, (bfd_vma) stack, (bfd_vma) cum_stack);
3349
3350   if (has_call)
3351     {
3352       info->callbacks->minfo (_("  calls:\n"));
3353       for (call = fun->call_list; call; call = call->next)
3354         if (!call->is_pasted)
3355           {
3356             const char *f2 = func_name (call->fun);
3357             const char *ann1 = call->fun == max ? "*" : " ";
3358             const char *ann2 = call->is_tail ? "t" : " ";
3359
3360             info->callbacks->minfo (_("   %s%s %s\n"), ann1, ann2, f2);
3361           }
3362     }
3363
3364   if (sum_stack_param->emit_stack_syms)
3365     {
3366       char *name = bfd_malloc (18 + strlen (f1));
3367       struct elf_link_hash_entry *h;
3368
3369       if (name == NULL)
3370         return FALSE;
3371
3372       if (fun->global || ELF_ST_BIND (fun->u.sym->st_info) == STB_GLOBAL)
3373         sprintf (name, "__stack_%s", f1);
3374       else
3375         sprintf (name, "__stack_%x_%s", fun->sec->id & 0xffffffff, f1);
3376
3377       h = elf_link_hash_lookup (&htab->elf, name, TRUE, TRUE, FALSE);
3378       free (name);
3379       if (h != NULL
3380           && (h->root.type == bfd_link_hash_new
3381               || h->root.type == bfd_link_hash_undefined
3382               || h->root.type == bfd_link_hash_undefweak))
3383         {
3384           h->root.type = bfd_link_hash_defined;
3385           h->root.u.def.section = bfd_abs_section_ptr;
3386           h->root.u.def.value = cum_stack;
3387           h->size = 0;
3388           h->type = 0;
3389           h->ref_regular = 1;
3390           h->def_regular = 1;
3391           h->ref_regular_nonweak = 1;
3392           h->forced_local = 1;
3393           h->non_elf = 0;
3394         }
3395     }
3396
3397   return TRUE;
3398 }
3399
3400 /* SEC is part of a pasted function.  Return the call_info for the
3401    next section of this function.  */
3402
3403 static struct call_info *
3404 find_pasted_call (asection *sec)
3405 {
3406   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
3407   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
3408   struct call_info *call;
3409   int k;
3410
3411   for (k = 0; k < sinfo->num_fun; ++k)
3412     for (call = sinfo->fun[k].call_list; call != NULL; call = call->next)
3413       if (call->is_pasted)
3414         return call;
3415   abort ();
3416   return 0;
3417 }
3418
3419 /* qsort predicate to sort bfds by file name.  */
3420
3421 static int
3422 sort_bfds (const void *a, const void *b)
3423 {
3424   bfd *const *abfd1 = a;
3425   bfd *const *abfd2 = b;
3426
3427   return strcmp ((*abfd1)->filename, (*abfd2)->filename);
3428 }
3429
3430 /* Handle --auto-overlay.  */
3431
3432 static void spu_elf_auto_overlay (struct bfd_link_info *, void (*) (void))
3433      ATTRIBUTE_NORETURN;
3434
3435 static void
3436 spu_elf_auto_overlay (struct bfd_link_info *info,
3437                       void (*spu_elf_load_ovl_mgr) (void))
3438 {
3439   bfd *ibfd;
3440   bfd **bfd_arr;
3441   struct elf_segment_map *m;
3442   unsigned int fixed_size, lo, hi;
3443   struct spu_link_hash_table *htab;
3444   unsigned int base, i, count, bfd_count;
3445   int ovlynum;
3446   asection **ovly_sections, **ovly_p;
3447   FILE *script;
3448   unsigned int total_overlay_size, overlay_size;
3449   struct elf_link_hash_entry *h;
3450   struct _mos_param mos_param;
3451   struct _uos_param uos_param;
3452   struct function_info dummy_caller;
3453
3454   /* Find the extents of our loadable image.  */
3455   lo = (unsigned int) -1;
3456   hi = 0;
3457   for (m = elf_tdata (info->output_bfd)->segment_map; m != NULL; m = m->next)
3458     if (m->p_type == PT_LOAD)
3459       for (i = 0; i < m->count; i++)
3460         if (m->sections[i]->size != 0)
3461           {
3462             if (m->sections[i]->vma < lo)
3463               lo = m->sections[i]->vma;
3464             if (m->sections[i]->vma + m->sections[i]->size - 1 > hi)
3465               hi = m->sections[i]->vma + m->sections[i]->size - 1;
3466           }
3467   fixed_size = hi + 1 - lo;
3468
3469   if (!discover_functions (info))
3470     goto err_exit;
3471
3472   if (!build_call_tree (info))
3473     goto err_exit;
3474
3475   uos_param.exclude_input_section = 0;
3476   uos_param.exclude_output_section
3477     = bfd_get_section_by_name (info->output_bfd, ".interrupt");
3478
3479   htab = spu_hash_table (info);
3480   h = elf_link_hash_lookup (&htab->elf, "__ovly_load",
3481                             FALSE, FALSE, FALSE);
3482   if (h != NULL
3483       && (h->root.type == bfd_link_hash_defined
3484           || h->root.type == bfd_link_hash_defweak)
3485       && h->def_regular)
3486     {
3487       /* We have a user supplied overlay manager.  */
3488       uos_param.exclude_input_section = h->root.u.def.section;
3489     }
3490   else
3491     {
3492       /* If no user overlay manager, spu_elf_load_ovl_mgr will add our
3493          builtin version to .text, and will adjust .text size.  */
3494       asection *text = bfd_get_section_by_name (info->output_bfd, ".text");
3495       if (text != NULL)
3496         fixed_size -= text->size;
3497       spu_elf_load_ovl_mgr ();
3498       text = bfd_get_section_by_name (info->output_bfd, ".text");
3499       if (text != NULL)
3500         fixed_size += text->size;
3501     }
3502
3503   /* Mark overlay sections, and find max overlay section size.  */
3504   mos_param.max_overlay_size = 0;
3505   if (!for_each_node (mark_overlay_section, info, &mos_param, TRUE))
3506     goto err_exit;
3507
3508   /* We can't put the overlay manager or interrupt routines in
3509      overlays.  */
3510   uos_param.clearing = 0;
3511   if ((uos_param.exclude_input_section
3512        || uos_param.exclude_output_section)
3513       && !for_each_node (unmark_overlay_section, info, &uos_param, TRUE))
3514     goto err_exit;
3515
3516   bfd_count = 0;
3517   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
3518     ++bfd_count;
3519   bfd_arr = bfd_malloc (bfd_count * sizeof (*bfd_arr));
3520   if (bfd_arr == NULL)
3521     goto err_exit;
3522
3523   /* Count overlay sections, and subtract their sizes from "fixed_size".  */
3524   count = 0;
3525   bfd_count = 0;
3526   total_overlay_size = 0;
3527   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
3528     {
3529       extern const bfd_target bfd_elf32_spu_vec;
3530       asection *sec;
3531       unsigned int old_count;
3532
3533       if (ibfd->xvec != &bfd_elf32_spu_vec)
3534         continue;
3535
3536       old_count = count;
3537       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
3538         if (sec->linker_mark)
3539           {
3540             if ((sec->flags & SEC_CODE) != 0)
3541               count += 1;
3542             fixed_size -= sec->size;
3543             total_overlay_size += sec->size;
3544           }
3545       if (count != old_count)
3546         bfd_arr[bfd_count++] = ibfd;
3547     }
3548
3549   /* Since the overlay link script selects sections by file name and
3550      section name, ensure that file names are unique.  */
3551   if (bfd_count > 1)
3552     {
3553       bfd_boolean ok = TRUE;
3554
3555       qsort (bfd_arr, bfd_count, sizeof (*bfd_arr), sort_bfds);
3556       for (i = 1; i < bfd_count; ++i)
3557         if (strcmp (bfd_arr[i - 1]->filename, bfd_arr[i]->filename) == 0)
3558           {
3559             if (bfd_arr[i - 1]->my_archive == bfd_arr[i]->my_archive)
3560               {
3561                 if (bfd_arr[i - 1]->my_archive && bfd_arr[i]->my_archive)
3562                   info->callbacks->einfo (_("%s duplicated in %s\n"),
3563                                           bfd_arr[i]->filename,
3564                                           bfd_arr[i]->my_archive->filename);
3565                 else
3566                   info->callbacks->einfo (_("%s duplicated\n"),
3567                                           bfd_arr[i]->filename);
3568                 ok = FALSE;
3569               }
3570           }
3571       if (!ok)
3572         {
3573           info->callbacks->einfo (_("sorry, no support for duplicate "
3574                                     "object files in auto-overlay script\n"));
3575           bfd_set_error (bfd_error_bad_value);
3576           goto err_exit;
3577         }
3578     }
3579   free (bfd_arr);
3580
3581   if (htab->reserved == 0)
3582     {
3583       struct _sum_stack_param sum_stack_param;
3584
3585       sum_stack_param.emit_stack_syms = 0;
3586       sum_stack_param.overall_stack = 0;
3587       if (!for_each_node (sum_stack, info, &sum_stack_param, TRUE))
3588         goto err_exit;
3589       htab->reserved = sum_stack_param.overall_stack + htab->extra_stack_space;
3590     }
3591   fixed_size += htab->reserved;
3592   fixed_size += htab->non_ovly_stub * OVL_STUB_SIZE;
3593   if (fixed_size + mos_param.max_overlay_size <= htab->local_store)
3594     {
3595       /* Guess number of overlays.  Assuming overlay buffer is on
3596          average only half full should be conservative.  */
3597       ovlynum = total_overlay_size * 2 / (htab->local_store - fixed_size);
3598       /* Space for _ovly_table[], _ovly_buf_table[] and toe.  */
3599       fixed_size += ovlynum * 16 + 16 + 4 + 16;
3600     }
3601
3602   if (fixed_size + mos_param.max_overlay_size > htab->local_store)
3603     info->callbacks->einfo (_("non-overlay plus maximum overlay size "
3604                               "of 0x%x exceeds local store\n"),
3605                             fixed_size + mos_param.max_overlay_size);
3606
3607   /* Now see if we should put some functions in the non-overlay area.  */
3608   if (fixed_size < htab->overlay_fixed
3609       && htab->overlay_fixed + mos_param.max_overlay_size < htab->local_store)
3610     {
3611       unsigned int lib_size = htab->overlay_fixed - fixed_size;
3612       lib_size = auto_ovl_lib_functions (info, lib_size);
3613       if (lib_size == (unsigned int) -1)
3614         goto err_exit;
3615       fixed_size = htab->overlay_fixed - lib_size;
3616     }
3617
3618   /* Build an array of sections, suitably sorted to place into
3619      overlays.  */
3620   ovly_sections = bfd_malloc (2 * count * sizeof (*ovly_sections));
3621   if (ovly_sections == NULL)
3622     goto err_exit;
3623   ovly_p = ovly_sections;
3624   if (!for_each_node (collect_overlays, info, &ovly_p, TRUE))
3625     goto err_exit;
3626   count = (size_t) (ovly_p - ovly_sections) / 2;
3627
3628   script = htab->spu_elf_open_overlay_script ();
3629
3630   if (fprintf (script, "SECTIONS\n{\n OVERLAY :\n {\n") <= 0)
3631     goto file_err;
3632
3633   memset (&dummy_caller, 0, sizeof (dummy_caller));
3634   overlay_size = htab->local_store - fixed_size;
3635   base = 0;
3636   ovlynum = 0;
3637   while (base < count)
3638     {
3639       unsigned int size = 0;
3640       unsigned int j;
3641
3642       for (i = base; i < count; i++)
3643         {
3644           asection *sec;
3645           unsigned int tmp;
3646           unsigned int stub_size;
3647           struct call_info *call, *pasty;
3648           struct _spu_elf_section_data *sec_data;
3649           struct spu_elf_stack_info *sinfo;
3650           int k;
3651
3652           /* See whether we can add this section to the current
3653              overlay without overflowing our overlay buffer.  */
3654           sec = ovly_sections[2 * i];
3655           tmp = size + sec->size;
3656           if (ovly_sections[2 * i + 1])
3657             tmp += ovly_sections[2 * i + 1]->size;
3658           if (tmp > overlay_size)
3659             break;
3660           if (sec->segment_mark)
3661             {
3662               /* Pasted sections must stay together, so add their
3663                  sizes too.  */
3664               struct call_info *pasty = find_pasted_call (sec);
3665               while (pasty != NULL)
3666                 {
3667                   struct function_info *call_fun = pasty->fun;
3668                   tmp += call_fun->sec->size;
3669                   if (call_fun->rodata)
3670                     tmp += call_fun->rodata->size;
3671                   for (pasty = call_fun->call_list; pasty; pasty = pasty->next)
3672                     if (pasty->is_pasted)
3673                       break;
3674                 }
3675             }
3676           if (tmp > overlay_size)
3677             break;
3678
3679           /* If we add this section, we might need new overlay call
3680              stubs.  Add any overlay section calls to dummy_call.  */
3681           pasty = NULL;
3682           sec_data = spu_elf_section_data (sec);
3683           sinfo = sec_data->u.i.stack_info;
3684           for (k = 0; k < sinfo->num_fun; ++k)
3685             for (call = sinfo->fun[k].call_list; call; call = call->next)
3686               if (call->is_pasted)
3687                 {
3688                   BFD_ASSERT (pasty == NULL);
3689                   pasty = call;
3690                 }
3691               else if (call->fun->sec->linker_mark)
3692                 {
3693                   if (!copy_callee (&dummy_caller, call))
3694                     goto err_exit;
3695                 }
3696           while (pasty != NULL)
3697             {
3698               struct function_info *call_fun = pasty->fun;
3699               pasty = NULL;
3700               for (call = call_fun->call_list; call; call = call->next)
3701                 if (call->is_pasted)
3702                   {
3703                     BFD_ASSERT (pasty == NULL);
3704                     pasty = call;
3705                   }
3706                 else if (!copy_callee (&dummy_caller, call))
3707                   goto err_exit;
3708             }
3709
3710           /* Calculate call stub size.  */
3711           stub_size = 0;
3712           for (call = dummy_caller.call_list; call; call = call->next)
3713             {
3714               unsigned int k;
3715
3716               stub_size += OVL_STUB_SIZE;
3717               /* If the call is within this overlay, we won't need a
3718                  stub.  */
3719               for (k = base; k < i + 1; k++)
3720                 if (call->fun->sec == ovly_sections[2 * k])
3721                   {
3722                     stub_size -= OVL_STUB_SIZE;
3723                     break;
3724                   }
3725             }
3726           if (tmp + stub_size > overlay_size)
3727             break;
3728
3729           size = tmp;
3730         }
3731
3732       if (i == base)
3733         {
3734           info->callbacks->einfo (_("%B:%A%s exceeds overlay size\n"),
3735                                   ovly_sections[2 * i]->owner,
3736                                   ovly_sections[2 * i],
3737                                   ovly_sections[2 * i + 1] ? " + rodata" : "");
3738           bfd_set_error (bfd_error_bad_value);
3739           goto err_exit;
3740         }
3741
3742       if (fprintf (script, "  .ovly%d {\n", ++ovlynum) <= 0)
3743         goto file_err;
3744       for (j = base; j < i; j++)
3745         {
3746           asection *sec = ovly_sections[2 * j];
3747
3748           if (fprintf (script, "   %s%c%s (%s)\n",
3749                        (sec->owner->my_archive != NULL
3750                         ? sec->owner->my_archive->filename : ""),
3751                        info->path_separator,
3752                        sec->owner->filename,
3753                        sec->name) <= 0)
3754             goto file_err;
3755           if (sec->segment_mark)
3756             {
3757               struct call_info *call = find_pasted_call (sec);
3758               while (call != NULL)
3759                 {
3760                   struct function_info *call_fun = call->fun;
3761                   sec = call_fun->sec;
3762                   if (fprintf (script, "   %s%c%s (%s)\n",
3763                                (sec->owner->my_archive != NULL
3764                                 ? sec->owner->my_archive->filename : ""),
3765                                info->path_separator,
3766                                sec->owner->filename,
3767                                sec->name) <= 0)
3768                     goto file_err;
3769                   for (call = call_fun->call_list; call; call = call->next)
3770                     if (call->is_pasted)
3771                       break;
3772                 }
3773             }
3774         }
3775
3776       for (j = base; j < i; j++)
3777         {
3778           asection *sec = ovly_sections[2 * j + 1];
3779           if (sec != NULL
3780               && fprintf (script, "   %s%c%s (%s)\n",
3781                           (sec->owner->my_archive != NULL
3782                            ? sec->owner->my_archive->filename : ""),
3783                           info->path_separator,
3784                           sec->owner->filename,
3785                           sec->name) <= 0)
3786             goto file_err;
3787
3788           sec = ovly_sections[2 * j];
3789           if (sec->segment_mark)
3790             {
3791               struct call_info *call = find_pasted_call (sec);
3792               while (call != NULL)
3793                 {
3794                   struct function_info *call_fun = call->fun;
3795                   sec = call_fun->rodata;
3796                   if (sec != NULL
3797                       && fprintf (script, "   %s%c%s (%s)\n",
3798                                   (sec->owner->my_archive != NULL
3799                                    ? sec->owner->my_archive->filename : ""),
3800                                   info->path_separator,
3801                                   sec->owner->filename,
3802                                   sec->name) <= 0)
3803                     goto file_err;
3804                   for (call = call_fun->call_list; call; call = call->next)
3805                     if (call->is_pasted)
3806                       break;
3807                 }
3808             }
3809         }
3810
3811       if (fprintf (script, "  }\n") <= 0)
3812         goto file_err;
3813
3814       while (dummy_caller.call_list != NULL)
3815         {
3816           struct call_info *call = dummy_caller.call_list;
3817           dummy_caller.call_list = call->next;
3818           free (call);
3819         }
3820
3821       base = i;
3822     }
3823   free (ovly_sections);
3824
3825   if (fprintf (script, " }\n}\nINSERT AFTER .text;\n") <= 0)
3826     goto file_err;
3827   if (fclose (script) != 0)
3828     goto file_err;
3829
3830   if (htab->auto_overlay & AUTO_RELINK)
3831     htab->spu_elf_relink ();
3832
3833   xexit (0);
3834
3835  file_err:
3836   bfd_set_error (bfd_error_system_call);
3837  err_exit:
3838   info->callbacks->einfo ("%F%P: auto overlay error: %E\n");
3839   xexit (1);
3840 }
3841
3842 /* Provide an estimate of total stack required.  */
3843
3844 static bfd_boolean
3845 spu_elf_stack_analysis (struct bfd_link_info *info, int emit_stack_syms)
3846 {
3847   struct _sum_stack_param sum_stack_param;
3848
3849   if (!discover_functions (info))
3850     return FALSE;
3851
3852   if (!build_call_tree (info))
3853     return FALSE;
3854
3855   info->callbacks->info (_("Stack size for call graph root nodes.\n"));
3856   info->callbacks->minfo (_("\nStack size for functions.  "
3857                             "Annotations: '*' max stack, 't' tail call\n"));
3858
3859   sum_stack_param.emit_stack_syms = emit_stack_syms;
3860   sum_stack_param.overall_stack = 0;
3861   if (!for_each_node (sum_stack, info, &sum_stack_param, TRUE))
3862     return FALSE;
3863
3864   info->callbacks->info (_("Maximum stack required is 0x%v\n"),
3865                          (bfd_vma) sum_stack_param.overall_stack);
3866   return TRUE;
3867 }
3868
3869 /* Perform a final link.  */
3870
3871 static bfd_boolean
3872 spu_elf_final_link (bfd *output_bfd, struct bfd_link_info *info)
3873 {
3874   struct spu_link_hash_table *htab = spu_hash_table (info);
3875
3876   if (htab->auto_overlay)
3877     spu_elf_auto_overlay (info, htab->spu_elf_load_ovl_mgr);
3878
3879   if (htab->stack_analysis
3880       && !spu_elf_stack_analysis (info, htab->emit_stack_syms))
3881     info->callbacks->einfo ("%X%P: stack analysis error: %E\n");
3882
3883   return bfd_elf_final_link (output_bfd, info);
3884 }
3885
3886 /* Called when not normally emitting relocs, ie. !info->relocatable
3887    and !info->emitrelocations.  Returns a count of special relocs
3888    that need to be emitted.  */
3889
3890 static unsigned int
3891 spu_elf_count_relocs (asection *sec, Elf_Internal_Rela *relocs)
3892 {
3893   unsigned int count = 0;
3894   Elf_Internal_Rela *relend = relocs + sec->reloc_count;
3895
3896   for (; relocs < relend; relocs++)
3897     {
3898       int r_type = ELF32_R_TYPE (relocs->r_info);
3899       if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
3900         ++count;
3901     }
3902
3903   return count;
3904 }
3905
3906 /* Apply RELOCS to CONTENTS of INPUT_SECTION from INPUT_BFD.  */
3907
3908 static int
3909 spu_elf_relocate_section (bfd *output_bfd,
3910                           struct bfd_link_info *info,
3911                           bfd *input_bfd,
3912                           asection *input_section,
3913                           bfd_byte *contents,
3914                           Elf_Internal_Rela *relocs,
3915                           Elf_Internal_Sym *local_syms,
3916                           asection **local_sections)
3917 {
3918   Elf_Internal_Shdr *symtab_hdr;
3919   struct elf_link_hash_entry **sym_hashes;
3920   Elf_Internal_Rela *rel, *relend;
3921   struct spu_link_hash_table *htab;
3922   asection *ea = bfd_get_section_by_name (output_bfd, "._ea");
3923   int ret = TRUE;
3924   bfd_boolean emit_these_relocs = FALSE;
3925   bfd_boolean is_ea_sym;
3926   bfd_boolean stubs;
3927
3928   htab = spu_hash_table (info);
3929   stubs = (htab->stub_sec != NULL
3930            && maybe_needs_stubs (input_section, output_bfd));
3931   symtab_hdr = &elf_tdata (input_bfd)->symtab_hdr;
3932   sym_hashes = (struct elf_link_hash_entry **) (elf_sym_hashes (input_bfd));
3933
3934   rel = relocs;
3935   relend = relocs + input_section->reloc_count;
3936   for (; rel < relend; rel++)
3937     {
3938       int r_type;
3939       reloc_howto_type *howto;
3940       unsigned int r_symndx;
3941       Elf_Internal_Sym *sym;
3942       asection *sec;
3943       struct elf_link_hash_entry *h;
3944       const char *sym_name;
3945       bfd_vma relocation;
3946       bfd_vma addend;
3947       bfd_reloc_status_type r;
3948       bfd_boolean unresolved_reloc;
3949       bfd_boolean warned;
3950       enum _stub_type stub_type;
3951
3952       r_symndx = ELF32_R_SYM (rel->r_info);
3953       r_type = ELF32_R_TYPE (rel->r_info);
3954       howto = elf_howto_table + r_type;
3955       unresolved_reloc = FALSE;
3956       warned = FALSE;
3957       h = NULL;
3958       sym = NULL;
3959       sec = NULL;
3960       if (r_symndx < symtab_hdr->sh_info)
3961         {
3962           sym = local_syms + r_symndx;
3963           sec = local_sections[r_symndx];
3964           sym_name = bfd_elf_sym_name (input_bfd, symtab_hdr, sym, sec);
3965           relocation = _bfd_elf_rela_local_sym (output_bfd, sym, &sec, rel);
3966         }
3967       else
3968         {
3969           if (sym_hashes == NULL)
3970             return FALSE;
3971
3972           h = sym_hashes[r_symndx - symtab_hdr->sh_info];
3973
3974           while (h->root.type == bfd_link_hash_indirect
3975                  || h->root.type == bfd_link_hash_warning)
3976             h = (struct elf_link_hash_entry *) h->root.u.i.link;
3977
3978           relocation = 0;
3979           if (h->root.type == bfd_link_hash_defined
3980               || h->root.type == bfd_link_hash_defweak)
3981             {
3982               sec = h->root.u.def.section;
3983               if (sec == NULL
3984                   || sec->output_section == NULL)
3985                 /* Set a flag that will be cleared later if we find a
3986                    relocation value for this symbol.  output_section
3987                    is typically NULL for symbols satisfied by a shared
3988                    library.  */
3989                 unresolved_reloc = TRUE;
3990               else
3991                 relocation = (h->root.u.def.value
3992                               + sec->output_section->vma
3993                               + sec->output_offset);
3994             }
3995           else if (h->root.type == bfd_link_hash_undefweak)
3996             ;
3997           else if (info->unresolved_syms_in_objects == RM_IGNORE
3998                    && ELF_ST_VISIBILITY (h->other) == STV_DEFAULT)
3999             ;
4000           else if (!info->relocatable
4001                    && !(r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64))
4002             {
4003               bfd_boolean err;
4004               err = (info->unresolved_syms_in_objects == RM_GENERATE_ERROR
4005                      || ELF_ST_VISIBILITY (h->other) != STV_DEFAULT);
4006               if (!info->callbacks->undefined_symbol (info,
4007                                                       h->root.root.string,
4008                                                       input_bfd,
4009                                                       input_section,
4010                                                       rel->r_offset, err))
4011                 return FALSE;
4012               warned = TRUE;
4013             }
4014           sym_name = h->root.root.string;
4015         }
4016
4017       if (sec != NULL && elf_discarded_section (sec))
4018         {
4019           /* For relocs against symbols from removed linkonce sections,
4020              or sections discarded by a linker script, we just want the
4021              section contents zeroed.  Avoid any special processing.  */
4022           _bfd_clear_contents (howto, input_bfd, contents + rel->r_offset);
4023           rel->r_info = 0;
4024           rel->r_addend = 0;
4025           continue;
4026         }
4027
4028       if (info->relocatable)
4029         continue;
4030
4031       is_ea_sym = (ea != NULL
4032                    && sec != NULL
4033                    && sec->output_section == ea);
4034
4035       if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4036         {
4037           if (is_ea_sym)
4038             {
4039               /* ._ea is a special section that isn't allocated in SPU
4040                  memory, but rather occupies space in PPU memory as
4041                  part of an embedded ELF image.  If this reloc is
4042                  against a symbol defined in ._ea, then transform the
4043                  reloc into an equivalent one without a symbol
4044                  relative to the start of the ELF image.  */
4045               rel->r_addend += (relocation
4046                                 - ea->vma
4047                                 + elf_section_data (ea)->this_hdr.sh_offset);
4048               rel->r_info = ELF32_R_INFO (0, r_type);
4049             }
4050           emit_these_relocs = TRUE;
4051           continue;
4052         }
4053
4054       if (is_ea_sym)
4055         unresolved_reloc = TRUE;
4056
4057       if (unresolved_reloc)
4058         {
4059           (*_bfd_error_handler)
4060             (_("%B(%s+0x%lx): unresolvable %s relocation against symbol `%s'"),
4061              input_bfd,
4062              bfd_get_section_name (input_bfd, input_section),
4063              (long) rel->r_offset,
4064              howto->name,
4065              sym_name);
4066           ret = FALSE;
4067         }
4068
4069       /* If this symbol is in an overlay area, we may need to relocate
4070          to the overlay stub.  */
4071       addend = rel->r_addend;
4072       if (stubs
4073           && (stub_type = needs_ovl_stub (h, sym, sec, input_section, rel,
4074                                           contents, info)) != no_stub)
4075         {
4076           unsigned int ovl = 0;
4077           struct got_entry *g, **head;
4078
4079           if (stub_type != nonovl_stub)
4080             ovl = (spu_elf_section_data (input_section->output_section)
4081                    ->u.o.ovl_index);
4082
4083           if (h != NULL)
4084             head = &h->got.glist;
4085           else
4086             head = elf_local_got_ents (input_bfd) + r_symndx;
4087
4088           for (g = *head; g != NULL; g = g->next)
4089             if (g->addend == addend && (g->ovl == ovl || g->ovl == 0))
4090               break;
4091           if (g == NULL)
4092             abort ();
4093
4094           relocation = g->stub_addr;
4095           addend = 0;
4096         }
4097
4098       r = _bfd_final_link_relocate (howto,
4099                                     input_bfd,
4100                                     input_section,
4101                                     contents,
4102                                     rel->r_offset, relocation, addend);
4103
4104       if (r != bfd_reloc_ok)
4105         {
4106           const char *msg = (const char *) 0;
4107
4108           switch (r)
4109             {
4110             case bfd_reloc_overflow:
4111               if (!((*info->callbacks->reloc_overflow)
4112                     (info, (h ? &h->root : NULL), sym_name, howto->name,
4113                      (bfd_vma) 0, input_bfd, input_section, rel->r_offset)))
4114                 return FALSE;
4115               break;
4116
4117             case bfd_reloc_undefined:
4118               if (!((*info->callbacks->undefined_symbol)
4119                     (info, sym_name, input_bfd, input_section,
4120                      rel->r_offset, TRUE)))
4121                 return FALSE;
4122               break;
4123
4124             case bfd_reloc_outofrange:
4125               msg = _("internal error: out of range error");
4126               goto common_error;
4127
4128             case bfd_reloc_notsupported:
4129               msg = _("internal error: unsupported relocation error");
4130               goto common_error;
4131
4132             case bfd_reloc_dangerous:
4133               msg = _("internal error: dangerous error");
4134               goto common_error;
4135
4136             default:
4137               msg = _("internal error: unknown error");
4138               /* fall through */
4139
4140             common_error:
4141               ret = FALSE;
4142               if (!((*info->callbacks->warning)
4143                     (info, msg, sym_name, input_bfd, input_section,
4144                      rel->r_offset)))
4145                 return FALSE;
4146               break;
4147             }
4148         }
4149     }
4150
4151   if (ret
4152       && emit_these_relocs
4153       && !info->emitrelocations)
4154     {
4155       Elf_Internal_Rela *wrel;
4156       Elf_Internal_Shdr *rel_hdr;
4157
4158       wrel = rel = relocs;
4159       relend = relocs + input_section->reloc_count;
4160       for (; rel < relend; rel++)
4161         {
4162           int r_type;
4163
4164           r_type = ELF32_R_TYPE (rel->r_info);
4165           if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4166             *wrel++ = *rel;
4167         }
4168       input_section->reloc_count = wrel - relocs;
4169       /* Backflips for _bfd_elf_link_output_relocs.  */
4170       rel_hdr = &elf_section_data (input_section)->rel_hdr;
4171       rel_hdr->sh_size = input_section->reloc_count * rel_hdr->sh_entsize;
4172       ret = 2;
4173     }
4174
4175   return ret;
4176 }
4177
4178 /* Adjust _SPUEAR_ syms to point at their overlay stubs.  */
4179
4180 static bfd_boolean
4181 spu_elf_output_symbol_hook (struct bfd_link_info *info,
4182                             const char *sym_name ATTRIBUTE_UNUSED,
4183                             Elf_Internal_Sym *sym,
4184                             asection *sym_sec ATTRIBUTE_UNUSED,
4185                             struct elf_link_hash_entry *h)
4186 {
4187   struct spu_link_hash_table *htab = spu_hash_table (info);
4188
4189   if (!info->relocatable
4190       && htab->stub_sec != NULL
4191       && h != NULL
4192       && (h->root.type == bfd_link_hash_defined
4193           || h->root.type == bfd_link_hash_defweak)
4194       && h->def_regular
4195       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0)
4196     {
4197       struct got_entry *g;
4198
4199       for (g = h->got.glist; g != NULL; g = g->next)
4200         if (g->addend == 0 && g->ovl == 0)
4201           {
4202             sym->st_shndx = (_bfd_elf_section_from_bfd_section
4203                              (htab->stub_sec[0]->output_section->owner,
4204                               htab->stub_sec[0]->output_section));
4205             sym->st_value = g->stub_addr;
4206             break;
4207           }
4208     }
4209
4210   return TRUE;
4211 }
4212
4213 static int spu_plugin = 0;
4214
4215 void
4216 spu_elf_plugin (int val)
4217 {
4218   spu_plugin = val;
4219 }
4220
4221 /* Set ELF header e_type for plugins.  */
4222
4223 static void
4224 spu_elf_post_process_headers (bfd *abfd,
4225                               struct bfd_link_info *info ATTRIBUTE_UNUSED)
4226 {
4227   if (spu_plugin)
4228     {
4229       Elf_Internal_Ehdr *i_ehdrp = elf_elfheader (abfd);
4230
4231       i_ehdrp->e_type = ET_DYN;
4232     }
4233 }
4234
4235 /* We may add an extra PT_LOAD segment for .toe.  We also need extra
4236    segments for overlays.  */
4237
4238 static int
4239 spu_elf_additional_program_headers (bfd *abfd, struct bfd_link_info *info)
4240 {
4241   struct spu_link_hash_table *htab = spu_hash_table (info);
4242   int extra = htab->num_overlays;
4243   asection *sec;
4244
4245   if (extra)
4246     ++extra;
4247
4248   sec = bfd_get_section_by_name (abfd, ".toe");
4249   if (sec != NULL && (sec->flags & SEC_LOAD) != 0)
4250     ++extra;
4251
4252   return extra;
4253 }
4254
4255 /* Remove .toe section from other PT_LOAD segments and put it in
4256    a segment of its own.  Put overlays in separate segments too.  */
4257
4258 static bfd_boolean
4259 spu_elf_modify_segment_map (bfd *abfd, struct bfd_link_info *info)
4260 {
4261   asection *toe, *s;
4262   struct elf_segment_map *m;
4263   unsigned int i;
4264
4265   if (info == NULL)
4266     return TRUE;
4267
4268   toe = bfd_get_section_by_name (abfd, ".toe");
4269   for (m = elf_tdata (abfd)->segment_map; m != NULL; m = m->next)
4270     if (m->p_type == PT_LOAD && m->count > 1)
4271       for (i = 0; i < m->count; i++)
4272         if ((s = m->sections[i]) == toe
4273             || spu_elf_section_data (s)->u.o.ovl_index != 0)
4274           {
4275             struct elf_segment_map *m2;
4276             bfd_vma amt;
4277
4278             if (i + 1 < m->count)
4279               {
4280                 amt = sizeof (struct elf_segment_map);
4281                 amt += (m->count - (i + 2)) * sizeof (m->sections[0]);
4282                 m2 = bfd_zalloc (abfd, amt);
4283                 if (m2 == NULL)
4284                   return FALSE;
4285                 m2->count = m->count - (i + 1);
4286                 memcpy (m2->sections, m->sections + i + 1,
4287                         m2->count * sizeof (m->sections[0]));
4288                 m2->p_type = PT_LOAD;
4289                 m2->next = m->next;
4290                 m->next = m2;
4291               }
4292             m->count = 1;
4293             if (i != 0)
4294               {
4295                 m->count = i;
4296                 amt = sizeof (struct elf_segment_map);
4297                 m2 = bfd_zalloc (abfd, amt);
4298                 if (m2 == NULL)
4299                   return FALSE;
4300                 m2->p_type = PT_LOAD;
4301                 m2->count = 1;
4302                 m2->sections[0] = s;
4303                 m2->next = m->next;
4304                 m->next = m2;
4305               }
4306             break;
4307           }
4308
4309   return TRUE;
4310 }
4311
4312 /* Tweak the section type of .note.spu_name.  */
4313
4314 static bfd_boolean
4315 spu_elf_fake_sections (bfd *obfd ATTRIBUTE_UNUSED,
4316                        Elf_Internal_Shdr *hdr,
4317                        asection *sec)
4318 {
4319   if (strcmp (sec->name, SPU_PTNOTE_SPUNAME) == 0)
4320     hdr->sh_type = SHT_NOTE;
4321   return TRUE;
4322 }
4323
4324 /* Tweak phdrs before writing them out.  */
4325
4326 static int
4327 spu_elf_modify_program_headers (bfd *abfd, struct bfd_link_info *info)
4328 {
4329   const struct elf_backend_data *bed;
4330   struct elf_obj_tdata *tdata;
4331   Elf_Internal_Phdr *phdr, *last;
4332   struct spu_link_hash_table *htab;
4333   unsigned int count;
4334   unsigned int i;
4335
4336   if (info == NULL)
4337     return TRUE;
4338
4339   bed = get_elf_backend_data (abfd);
4340   tdata = elf_tdata (abfd);
4341   phdr = tdata->phdr;
4342   count = tdata->program_header_size / bed->s->sizeof_phdr;
4343   htab = spu_hash_table (info);
4344   if (htab->num_overlays != 0)
4345     {
4346       struct elf_segment_map *m;
4347       unsigned int o;
4348
4349       for (i = 0, m = elf_tdata (abfd)->segment_map; m; ++i, m = m->next)
4350         if (m->count != 0
4351             && (o = spu_elf_section_data (m->sections[0])->u.o.ovl_index) != 0)
4352           {
4353             /* Mark this as an overlay header.  */
4354             phdr[i].p_flags |= PF_OVERLAY;
4355
4356             if (htab->ovtab != NULL && htab->ovtab->size != 0)
4357               {
4358                 bfd_byte *p = htab->ovtab->contents;
4359                 unsigned int off = o * 16 + 8;
4360
4361                 /* Write file_off into _ovly_table.  */
4362                 bfd_put_32 (htab->ovtab->owner, phdr[i].p_offset, p + off);
4363               }
4364           }
4365     }
4366
4367   /* Round up p_filesz and p_memsz of PT_LOAD segments to multiples
4368      of 16.  This should always be possible when using the standard
4369      linker scripts, but don't create overlapping segments if
4370      someone is playing games with linker scripts.  */
4371   last = NULL;
4372   for (i = count; i-- != 0; )
4373     if (phdr[i].p_type == PT_LOAD)
4374       {
4375         unsigned adjust;
4376
4377         adjust = -phdr[i].p_filesz & 15;
4378         if (adjust != 0
4379             && last != NULL
4380             && phdr[i].p_offset + phdr[i].p_filesz > last->p_offset - adjust)
4381           break;
4382
4383         adjust = -phdr[i].p_memsz & 15;
4384         if (adjust != 0
4385             && last != NULL
4386             && phdr[i].p_filesz != 0
4387             && phdr[i].p_vaddr + phdr[i].p_memsz > last->p_vaddr - adjust
4388             && phdr[i].p_vaddr + phdr[i].p_memsz <= last->p_vaddr)
4389           break;
4390
4391         if (phdr[i].p_filesz != 0)
4392           last = &phdr[i];
4393       }
4394
4395   if (i == (unsigned int) -1)
4396     for (i = count; i-- != 0; )
4397       if (phdr[i].p_type == PT_LOAD)
4398         {
4399         unsigned adjust;
4400
4401         adjust = -phdr[i].p_filesz & 15;
4402         phdr[i].p_filesz += adjust;
4403
4404         adjust = -phdr[i].p_memsz & 15;
4405         phdr[i].p_memsz += adjust;
4406       }
4407
4408   return TRUE;
4409 }
4410
4411 #define TARGET_BIG_SYM          bfd_elf32_spu_vec
4412 #define TARGET_BIG_NAME         "elf32-spu"
4413 #define ELF_ARCH                bfd_arch_spu
4414 #define ELF_MACHINE_CODE        EM_SPU
4415 /* This matches the alignment need for DMA.  */
4416 #define ELF_MAXPAGESIZE         0x80
4417 #define elf_backend_rela_normal         1
4418 #define elf_backend_can_gc_sections     1
4419
4420 #define bfd_elf32_bfd_reloc_type_lookup         spu_elf_reloc_type_lookup
4421 #define bfd_elf32_bfd_reloc_name_lookup spu_elf_reloc_name_lookup
4422 #define elf_info_to_howto                       spu_elf_info_to_howto
4423 #define elf_backend_count_relocs                spu_elf_count_relocs
4424 #define elf_backend_relocate_section            spu_elf_relocate_section
4425 #define elf_backend_symbol_processing           spu_elf_backend_symbol_processing
4426 #define elf_backend_link_output_symbol_hook     spu_elf_output_symbol_hook
4427 #define elf_backend_object_p                    spu_elf_object_p
4428 #define bfd_elf32_new_section_hook              spu_elf_new_section_hook
4429 #define bfd_elf32_bfd_link_hash_table_create    spu_elf_link_hash_table_create
4430
4431 #define elf_backend_additional_program_headers  spu_elf_additional_program_headers
4432 #define elf_backend_modify_segment_map          spu_elf_modify_segment_map
4433 #define elf_backend_modify_program_headers      spu_elf_modify_program_headers
4434 #define elf_backend_post_process_headers        spu_elf_post_process_headers
4435 #define elf_backend_fake_sections               spu_elf_fake_sections
4436 #define elf_backend_special_sections            spu_elf_special_sections
4437 #define bfd_elf32_bfd_final_link                spu_elf_final_link
4438
4439 #include "elf32-target.h"