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   /* Count of overlay stubs needed in non-overlay area.  */
 329   unsigned int non_ovly_stub;
 330
 331   /* Stash various callbacks for --auto-overlay.  */
 332   void (*spu_elf_load_ovl_mgr) (void);
 333   FILE *(*spu_elf_open_overlay_script) (void);
 334   void (*spu_elf_relink) (void);
 335
 336   /* Bit 0 set if --auto-overlay.
 337      Bit 1 set if --auto-relink.
 338      Bit 2 set if --overlay-rodata.  */
 339   unsigned int auto_overlay : 3;
 340 #define AUTO_OVERLAY 1
 341 #define AUTO_RELINK 2
 342 #define OVERLAY_RODATA 4
 343
 344   /* Set if we should emit symbols for stubs.  */
 345   unsigned int emit_stub_syms:1;
 346
 347   /* Set if we want stubs on calls out of overlay regions to
 348      non-overlay regions.  */
 349   unsigned int non_overlay_stubs : 1;
 350
 351   /* Set on error.  */
 352   unsigned int stub_err : 1;
 353
 354   /* Set if stack size analysis should be done.  */
 355   unsigned int stack_analysis : 1;
 356
 357   /* Set if __stack_* syms will be emitted.  */
 358   unsigned int emit_stack_syms : 1;
 359 };
 360
 361 /* Hijack the generic got fields for overlay stub accounting.  */
 362
 363 struct got_entry
 364 {
 365   struct got_entry *next;
 366   unsigned int ovl;
 367   bfd_vma addend;
 368   bfd_vma stub_addr;
 369 };
 370
 371 #define spu_hash_table(p) \
 372   ((struct spu_link_hash_table *) ((p)->hash))
 373
 374 /* Create a spu ELF linker hash table.  */
 375
 376 static struct bfd_link_hash_table *
 377 spu_elf_link_hash_table_create (bfd *abfd)
 378 {
 379   struct spu_link_hash_table *htab;
 380
 381   htab = bfd_malloc (sizeof (*htab));
 382   if (htab == NULL)
 383     return NULL;
 384
 385   if (!_bfd_elf_link_hash_table_init (&htab->elf, abfd,
 386                                       _bfd_elf_link_hash_newfunc,
 387                                       sizeof (struct elf_link_hash_entry)))
 388     {
 389       free (htab);
 390       return NULL;
 391     }
 392
 393   memset (&htab->ovtab, 0,
 394           sizeof (*htab) - offsetof (struct spu_link_hash_table, ovtab));
 395
 396   htab->elf.init_got_refcount.refcount = 0;
 397   htab->elf.init_got_refcount.glist = NULL;
 398   htab->elf.init_got_offset.offset = 0;
 399   htab->elf.init_got_offset.glist = NULL;
 400   return &htab->elf.root;
 401 }
 402
 403 /* Find the symbol for the given R_SYMNDX in IBFD and set *HP and *SYMP
 404    to (hash, NULL) for global symbols, and (NULL, sym) for locals.  Set
 405    *SYMSECP to the symbol's section.  *LOCSYMSP caches local syms.  */
 406
 407 static bfd_boolean
 408 get_sym_h (struct elf_link_hash_entry **hp,
 409            Elf_Internal_Sym **symp,
 410            asection **symsecp,
 411            Elf_Internal_Sym **locsymsp,
 412            unsigned long r_symndx,
 413            bfd *ibfd)
 414 {
 415   Elf_Internal_Shdr *symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
 416
 417   if (r_symndx >= symtab_hdr->sh_info)
 418     {
 419       struct elf_link_hash_entry **sym_hashes = elf_sym_hashes (ibfd);
 420       struct elf_link_hash_entry *h;
 421
 422       h = sym_hashes[r_symndx - symtab_hdr->sh_info];
 423       while (h->root.type == bfd_link_hash_indirect
 424              || h->root.type == bfd_link_hash_warning)
 425         h = (struct elf_link_hash_entry *) h->root.u.i.link;
 426
 427       if (hp != NULL)
 428         *hp = h;
 429
 430       if (symp != NULL)
 431         *symp = NULL;
 432
 433       if (symsecp != NULL)
 434         {
 435           asection *symsec = NULL;
 436           if (h->root.type == bfd_link_hash_defined
 437               || h->root.type == bfd_link_hash_defweak)
 438             symsec = h->root.u.def.section;
 439           *symsecp = symsec;
 440         }
 441     }
 442   else
 443     {
 444       Elf_Internal_Sym *sym;
 445       Elf_Internal_Sym *locsyms = *locsymsp;
 446
 447       if (locsyms == NULL)
 448         {
 449           locsyms = (Elf_Internal_Sym *) symtab_hdr->contents;
 450           if (locsyms == NULL)
 451             {
 452               size_t symcount = symtab_hdr->sh_info;
 453
 454               /* If we are reading symbols into the contents, then
 455                  read the global syms too.  This is done to cache
 456                  syms for later stack analysis.  */
 457               if ((unsigned char **) locsymsp == &symtab_hdr->contents)
 458                 symcount = symtab_hdr->sh_size / symtab_hdr->sh_entsize;
 459               locsyms = bfd_elf_get_elf_syms (ibfd, symtab_hdr, symcount, 0,
 460                                               NULL, NULL, NULL);
 461             }
 462           if (locsyms == NULL)
 463             return FALSE;
 464           *locsymsp = locsyms;
 465         }
 466       sym = locsyms + r_symndx;
 467
 468       if (hp != NULL)
 469         *hp = NULL;
 470
 471       if (symp != NULL)
 472         *symp = sym;
 473
 474       if (symsecp != NULL)
 475         *symsecp = bfd_section_from_elf_index (ibfd, sym->st_shndx);
 476     }
 477
 478   return TRUE;
 479 }
 480
 481 /* Create the note section if not already present.  This is done early so
 482    that the linker maps the sections to the right place in the output.  */
 483
 484 bfd_boolean
 485 spu_elf_create_sections (struct bfd_link_info *info,
 486                          int stack_analysis,
 487                          int emit_stack_syms)
 488 {
 489   bfd *ibfd;
 490   struct spu_link_hash_table *htab = spu_hash_table (info);
 491
 492   /* Stash some options away where we can get at them later.  */
 493   htab->stack_analysis = stack_analysis;
 494   htab->emit_stack_syms = emit_stack_syms;
 495
 496   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
 497     if (bfd_get_section_by_name (ibfd, SPU_PTNOTE_SPUNAME) != NULL)
 498       break;
 499
 500   if (ibfd == NULL)
 501     {
 502       /* Make SPU_PTNOTE_SPUNAME section.  */
 503       asection *s;
 504       size_t name_len;
 505       size_t size;
 506       bfd_byte *data;
 507       flagword flags;
 508
 509       ibfd = info->input_bfds;
 510       flags = SEC_LOAD | SEC_READONLY | SEC_HAS_CONTENTS | SEC_IN_MEMORY;
 511       s = bfd_make_section_anyway_with_flags (ibfd, SPU_PTNOTE_SPUNAME, flags);
 512       if (s == NULL
 513           || !bfd_set_section_alignment (ibfd, s, 4))
 514         return FALSE;
 515
 516       name_len = strlen (bfd_get_filename (info->output_bfd)) + 1;
 517       size = 12 + ((sizeof (SPU_PLUGIN_NAME) + 3) & -4);
 518       size += (name_len + 3) & -4;
 519
 520       if (!bfd_set_section_size (ibfd, s, size))
 521         return FALSE;
 522
 523       data = bfd_zalloc (ibfd, size);
 524       if (data == NULL)
 525         return FALSE;
 526
 527       bfd_put_32 (ibfd, sizeof (SPU_PLUGIN_NAME), data + 0);
 528       bfd_put_32 (ibfd, name_len, data + 4);
 529       bfd_put_32 (ibfd, 1, data + 8);
 530       memcpy (data + 12, SPU_PLUGIN_NAME, sizeof (SPU_PLUGIN_NAME));
 531       memcpy (data + 12 + ((sizeof (SPU_PLUGIN_NAME) + 3) & -4),
 532               bfd_get_filename (info->output_bfd), name_len);
 533       s->contents = data;
 534     }
 535
 536   return TRUE;
 537 }
 538
 539 /* qsort predicate to sort sections by vma.  */
 540
 541 static int
 542 sort_sections (const void *a, const void *b)
 543 {
 544   const asection *const *s1 = a;
 545   const asection *const *s2 = b;
 546   bfd_signed_vma delta = (*s1)->vma - (*s2)->vma;
 547
 548   if (delta != 0)
 549     return delta < 0 ? -1 : 1;
 550
 551   return (*s1)->index - (*s2)->index;
 552 }
 553
 554 /* Identify overlays in the output bfd, and number them.  */
 555
 556 bfd_boolean
 557 spu_elf_find_overlays (struct bfd_link_info *info)
 558 {
 559   struct spu_link_hash_table *htab = spu_hash_table (info);
 560   asection **alloc_sec;
 561   unsigned int i, n, ovl_index, num_buf;
 562   asection *s;
 563   bfd_vma ovl_end;
 564
 565   if (info->output_bfd->section_count < 2)
 566     return FALSE;
 567
 568   alloc_sec
 569     = bfd_malloc (info->output_bfd->section_count * sizeof (*alloc_sec));
 570   if (alloc_sec == NULL)
 571     return FALSE;
 572
 573   /* Pick out all the alloced sections.  */
 574   for (n = 0, s = info->output_bfd->sections; s != NULL; s = s->next)
 575     if ((s->flags & SEC_ALLOC) != 0
 576         && (s->flags & (SEC_LOAD | SEC_THREAD_LOCAL)) != SEC_THREAD_LOCAL
 577         && s->size != 0)
 578       alloc_sec[n++] = s;
 579
 580   if (n == 0)
 581     {
 582       free (alloc_sec);
 583       return FALSE;
 584     }
 585
 586   /* Sort them by vma.  */
 587   qsort (alloc_sec, n, sizeof (*alloc_sec), sort_sections);
 588
 589   /* Look for overlapping vmas.  Any with overlap must be overlays.
 590      Count them.  Also count the number of overlay regions.  */
 591   ovl_end = alloc_sec[0]->vma + alloc_sec[0]->size;
 592   for (ovl_index = 0, num_buf = 0, i = 1; i < n; i++)
 593     {
 594       s = alloc_sec[i];
 595       if (s->vma < ovl_end)
 596         {
 597           asection *s0 = alloc_sec[i - 1];
 598
 599           if (spu_elf_section_data (s0)->u.o.ovl_index == 0)
 600             {
 601               alloc_sec[ovl_index] = s0;
 602               spu_elf_section_data (s0)->u.o.ovl_index = ++ovl_index;
 603               spu_elf_section_data (s0)->u.o.ovl_buf = ++num_buf;
 604             }
 605           alloc_sec[ovl_index] = s;
 606           spu_elf_section_data (s)->u.o.ovl_index = ++ovl_index;
 607           spu_elf_section_data (s)->u.o.ovl_buf = num_buf;
 608           if (s0->vma != s->vma)
 609             {
 610               info->callbacks->einfo (_("%X%P: overlay sections %A and %A "
 611                                         "do not start at the same address.\n"),
 612                                       s0, s);
 613               return FALSE;
 614             }
 615           if (ovl_end < s->vma + s->size)
 616             ovl_end = s->vma + s->size;
 617         }
 618       else
 619         ovl_end = s->vma + s->size;
 620     }
 621
 622   htab->num_overlays = ovl_index;
 623   htab->num_buf = num_buf;
 624   htab->ovl_sec = alloc_sec;
 625   htab->ovly_load = elf_link_hash_lookup (&htab->elf, "__ovly_load",
 626                                           FALSE, FALSE, FALSE);
 627   htab->ovly_return = elf_link_hash_lookup (&htab->elf, "__ovly_return",
 628                                             FALSE, FALSE, FALSE);
 629   return ovl_index != 0;
 630 }
 631
 632 /* Support two sizes of overlay stubs, a slower more compact stub of two
 633    intructions, and a faster stub of four instructions.  */
 634 #ifndef OVL_STUB_SIZE
 635 /* Default to faster.  */
 636 #define OVL_STUB_SIZE 16
 637 /* #define OVL_STUB_SIZE 8 */
 638 #endif
 639 #define BRSL    0x33000000
 640 #define BR      0x32000000
 641 #define NOP     0x40200000
 642 #define LNOP    0x00200000
 643 #define ILA     0x42000000
 644
 645 /* Return true for all relative and absolute branch instructions.
 646    bra   00110000 0..
 647    brasl 00110001 0..
 648    br    00110010 0..
 649    brsl  00110011 0..
 650    brz   00100000 0..
 651    brnz  00100001 0..
 652    brhz  00100010 0..
 653    brhnz 00100011 0..  */
 654
 655 static bfd_boolean
 656 is_branch (const unsigned char *insn)
 657 {
 658   return (insn[0] & 0xec) == 0x20 && (insn[1] & 0x80) == 0;
 659 }
 660
 661 /* Return true for all indirect branch instructions.
 662    bi     00110101 000
 663    bisl   00110101 001
 664    iret   00110101 010
 665    bisled 00110101 011
 666    biz    00100101 000
 667    binz   00100101 001
 668    bihz   00100101 010
 669    bihnz  00100101 011  */
 670
 671 static bfd_boolean
 672 is_indirect_branch (const unsigned char *insn)
 673 {
 674   return (insn[0] & 0xef) == 0x25 && (insn[1] & 0x80) == 0;
 675 }
 676
 677 /* Return true for branch hint instructions.
 678    hbra  0001000..
 679    hbrr  0001001..  */
 680
 681 static bfd_boolean
 682 is_hint (const unsigned char *insn)
 683 {
 684   return (insn[0] & 0xfc) == 0x10;
 685 }
 686
 687 /* True if INPUT_SECTION might need overlay stubs.  */
 688
 689 static bfd_boolean
 690 maybe_needs_stubs (asection *input_section, bfd *output_bfd)
 691 {
 692   /* No stubs for debug sections and suchlike.  */
 693   if ((input_section->flags & SEC_ALLOC) == 0)
 694     return FALSE;
 695
 696   /* No stubs for link-once sections that will be discarded.  */
 697   if (input_section->output_section == NULL
 698       || input_section->output_section->owner != output_bfd)
 699     return FALSE;
 700
 701   /* Don't create stubs for .eh_frame references.  */
 702   if (strcmp (input_section->name, ".eh_frame") == 0)
 703     return FALSE;
 704
 705   return TRUE;
 706 }
 707
 708 enum _stub_type
 709 {
 710   no_stub,
 711   ovl_stub,
 712   nonovl_stub,
 713   stub_error
 714 };
 715
 716 /* Return non-zero if this reloc symbol should go via an overlay stub.
 717    Return 2 if the stub must be in non-overlay area.  */
 718
 719 static enum _stub_type
 720 needs_ovl_stub (struct elf_link_hash_entry *h,
 721                 Elf_Internal_Sym *sym,
 722                 asection *sym_sec,
 723                 asection *input_section,
 724                 Elf_Internal_Rela *irela,
 725                 bfd_byte *contents,
 726                 struct bfd_link_info *info)
 727 {
 728   struct spu_link_hash_table *htab = spu_hash_table (info);
 729   enum elf_spu_reloc_type r_type;
 730   unsigned int sym_type;
 731   bfd_boolean branch;
 732   enum _stub_type ret = no_stub;
 733
 734   if (sym_sec == NULL
 735       || sym_sec->output_section == NULL
 736       || sym_sec->output_section->owner != info->output_bfd
 737       || spu_elf_section_data (sym_sec->output_section) == NULL)
 738     return ret;
 739
 740   if (h != NULL)
 741     {
 742       /* Ensure no stubs for user supplied overlay manager syms.  */
 743       if (h == htab->ovly_load || h == htab->ovly_return)
 744         return ret;
 745
 746       /* setjmp always goes via an overlay stub, because then the return
 747          and hence the longjmp goes via __ovly_return.  That magically
 748          makes setjmp/longjmp between overlays work.  */
 749       if (strncmp (h->root.root.string, "setjmp", 6) == 0
 750           && (h->root.root.string[6] == '\0' || h->root.root.string[6] == '@'))
 751         ret = ovl_stub;
 752     }
 753
 754   /* Usually, symbols in non-overlay sections don't need stubs.  */
 755   if (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index == 0
 756       && !htab->non_overlay_stubs)
 757     return ret;
 758
 759   if (h != NULL)
 760     sym_type = h->type;
 761   else
 762     sym_type = ELF_ST_TYPE (sym->st_info);
 763
 764   r_type = ELF32_R_TYPE (irela->r_info);
 765   branch = FALSE;
 766   if (r_type == R_SPU_REL16 || r_type == R_SPU_ADDR16)
 767     {
 768       bfd_byte insn[4];
 769
 770       if (contents == NULL)
 771         {
 772           contents = insn;
 773           if (!bfd_get_section_contents (input_section->owner,
 774                                          input_section,
 775                                          contents,
 776                                          irela->r_offset, 4))
 777             return stub_error;
 778         }
 779       else
 780         contents += irela->r_offset;
 781
 782       if (is_branch (contents) || is_hint (contents))
 783         {
 784           branch = TRUE;
 785           if ((contents[0] & 0xfd) == 0x31
 786               && sym_type != STT_FUNC
 787               && contents != insn)
 788             {
 789               /* It's common for people to write assembly and forget
 790                  to give function symbols the right type.  Handle
 791                  calls to such symbols, but warn so that (hopefully)
 792                  people will fix their code.  We need the symbol
 793                  type to be correct to distinguish function pointer
 794                  initialisation from other pointer initialisations.  */
 795               const char *sym_name;
 796
 797               if (h != NULL)
 798                 sym_name = h->root.root.string;
 799               else
 800                 {
 801                   Elf_Internal_Shdr *symtab_hdr;
 802                   symtab_hdr = &elf_tdata (input_section->owner)->symtab_hdr;
 803                   sym_name = bfd_elf_sym_name (input_section->owner,
 804                                                symtab_hdr,
 805                                                sym,
 806                                                sym_sec);
 807                 }
 808               (*_bfd_error_handler) (_("warning: call to non-function"
 809                                        " symbol %s defined in %B"),
 810                                      sym_sec->owner, sym_name);
 811
 812             }
 813         }
 814     }
 815
 816   if (sym_type != STT_FUNC
 817       && !branch
 818       && (sym_sec->flags & SEC_CODE) == 0)
 819     return ret;
 820
 821   /* A reference from some other section to a symbol in an overlay
 822      section needs a stub.  */
 823   if (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index
 824        != spu_elf_section_data (input_section->output_section)->u.o.ovl_index)
 825     return ovl_stub;
 826
 827   /* If this insn isn't a branch then we are possibly taking the
 828      address of a function and passing it out somehow.  */
 829   return !branch && sym_type == STT_FUNC ? nonovl_stub : ret;
 830 }
 831
 832 static bfd_boolean
 833 count_stub (struct spu_link_hash_table *htab,
 834             bfd *ibfd,
 835             asection *isec,
 836             enum _stub_type stub_type,
 837             struct elf_link_hash_entry *h,
 838             const Elf_Internal_Rela *irela)
 839 {
 840   unsigned int ovl = 0;
 841   struct got_entry *g, **head;
 842   bfd_vma addend;
 843
 844   /* If this instruction is a branch or call, we need a stub
 845      for it.  One stub per function per overlay.
 846      If it isn't a branch, then we are taking the address of
 847      this function so need a stub in the non-overlay area
 848      for it.  One stub per function.  */
 849   if (stub_type != nonovl_stub)
 850     ovl = spu_elf_section_data (isec->output_section)->u.o.ovl_index;
 851
 852   if (h != NULL)
 853     head = &h->got.glist;
 854   else
 855     {
 856       if (elf_local_got_ents (ibfd) == NULL)
 857         {
 858           bfd_size_type amt = (elf_tdata (ibfd)->symtab_hdr.sh_info
 859                                * sizeof (*elf_local_got_ents (ibfd)));
 860           elf_local_got_ents (ibfd) = bfd_zmalloc (amt);
 861           if (elf_local_got_ents (ibfd) == NULL)
 862             return FALSE;
 863         }
 864       head = elf_local_got_ents (ibfd) + ELF32_R_SYM (irela->r_info);
 865     }
 866
 867   addend = 0;
 868   if (irela != NULL)
 869     addend = irela->r_addend;
 870
 871   if (ovl == 0)
 872     {
 873       struct got_entry *gnext;
 874
 875       for (g = *head; g != NULL; g = g->next)
 876         if (g->addend == addend && g->ovl == 0)
 877           break;
 878
 879       if (g == NULL)
 880         {
 881           /* Need a new non-overlay area stub.  Zap other stubs.  */
 882           for (g = *head; g != NULL; g = gnext)
 883             {
 884               gnext = g->next;
 885               if (g->addend == addend)
 886                 {
 887                   htab->stub_count[g->ovl] -= 1;
 888                   free (g);
 889                 }
 890             }
 891         }
 892     }
 893   else
 894     {
 895       for (g = *head; g != NULL; g = g->next)
 896         if (g->addend == addend && (g->ovl == ovl || g->ovl == 0))
 897           break;
 898     }
 899
 900   if (g == NULL)
 901     {
 902       g = bfd_malloc (sizeof *g);
 903       if (g == NULL)
 904         return FALSE;
 905       g->ovl = ovl;
 906       g->addend = addend;
 907       g->stub_addr = (bfd_vma) -1;
 908       g->next = *head;
 909       *head = g;
 910
 911       htab->stub_count[ovl] += 1;
 912     }
 913
 914   return TRUE;
 915 }
 916
 917 /* Two instruction overlay stubs look like:
 918
 919    brsl $75,__ovly_load
 920    .word target_ovl_and_address
 921
 922    ovl_and_address is a word with the overlay number in the top 14 bits
 923    and local store address in the bottom 18 bits.
 924
 925    Four instruction overlay stubs look like:
 926
 927    ila $78,ovl_number
 928    lnop
 929    ila $79,target_address
 930    br __ovly_load  */
 931
 932 static bfd_boolean
 933 build_stub (struct spu_link_hash_table *htab,
 934             bfd *ibfd,
 935             asection *isec,
 936             enum _stub_type stub_type,
 937             struct elf_link_hash_entry *h,
 938             const Elf_Internal_Rela *irela,
 939             bfd_vma dest,
 940             asection *dest_sec)
 941 {
 942   unsigned int ovl;
 943   struct got_entry *g, **head;
 944   asection *sec;
 945   bfd_vma addend, val, from, to;
 946
 947   ovl = 0;
 948   if (stub_type != nonovl_stub)
 949     ovl = spu_elf_section_data (isec->output_section)->u.o.ovl_index;
 950
 951   if (h != NULL)
 952     head = &h->got.glist;
 953   else
 954     head = elf_local_got_ents (ibfd) + ELF32_R_SYM (irela->r_info);
 955
 956   addend = 0;
 957   if (irela != NULL)
 958     addend = irela->r_addend;
 959
 960   for (g = *head; g != NULL; g = g->next)
 961     if (g->addend == addend && (g->ovl == ovl || g->ovl == 0))
 962       break;
 963   if (g == NULL)
 964     abort ();
 965
 966   if (g->ovl == 0 && ovl != 0)
 967     return TRUE;
 968
 969   if (g->stub_addr != (bfd_vma) -1)
 970     return TRUE;
 971
 972   sec = htab->stub_sec[ovl];
 973   dest += dest_sec->output_offset + dest_sec->output_section->vma;
 974   from = sec->size + sec->output_offset + sec->output_section->vma;
 975   g->stub_addr = from;
 976   to = (htab->ovly_load->root.u.def.value
 977         + htab->ovly_load->root.u.def.section->output_offset
 978         + htab->ovly_load->root.u.def.section->output_section->vma);
 979   val = to - from;
 980   if (OVL_STUB_SIZE == 16)
 981     val -= 12;
 982   if (((dest | to | from) & 3) != 0
 983       || val + 0x20000 >= 0x40000)
 984     {
 985       htab->stub_err = 1;
 986       return FALSE;
 987     }
 988   ovl = spu_elf_section_data (dest_sec->output_section)->u.o.ovl_index;
 989
 990   if (OVL_STUB_SIZE == 16)
 991     {
 992       bfd_put_32 (sec->owner, ILA + ((ovl << 7) & 0x01ffff80) + 78,
 993                   sec->contents + sec->size);
 994       bfd_put_32 (sec->owner, LNOP,
 995                   sec->contents + sec->size + 4);
 996       bfd_put_32 (sec->owner, ILA + ((dest << 7) & 0x01ffff80) + 79,
 997                   sec->contents + sec->size + 8);
 998       bfd_put_32 (sec->owner, BR + ((val << 5) & 0x007fff80),
 999                   sec->contents + sec->size + 12);
1000     }
1001   else if (OVL_STUB_SIZE == 8)
1002     {
1003       bfd_put_32 (sec->owner, BRSL + ((val << 5) & 0x007fff80) + 75,
1004                   sec->contents + sec->size);
1005
1006       val = (dest & 0x3ffff) | (ovl << 18);
1007       bfd_put_32 (sec->owner, val,
1008                   sec->contents + sec->size + 4);
1009     }
1010   else
1011     abort ();
1012   sec->size += OVL_STUB_SIZE;
1013
1014   if (htab->emit_stub_syms)
1015     {
1016       size_t len;
1017       char *name;
1018       int add;
1019
1020       len = 8 + sizeof (".ovl_call.") - 1;
1021       if (h != NULL)
1022         len += strlen (h->root.root.string);
1023       else
1024         len += 8 + 1 + 8;
1025       add = 0;
1026       if (irela != NULL)
1027         add = (int) irela->r_addend & 0xffffffff;
1028       if (add != 0)
1029         len += 1 + 8;
1030       name = bfd_malloc (len);
1031       if (name == NULL)
1032         return FALSE;
1033
1034       sprintf (name, "%08x.ovl_call.", g->ovl);
1035       if (h != NULL)
1036         strcpy (name + 8 + sizeof (".ovl_call.") - 1, h->root.root.string);
1037       else
1038         sprintf (name + 8 + sizeof (".ovl_call.") - 1, "%x:%x",
1039                  dest_sec->id & 0xffffffff,
1040                  (int) ELF32_R_SYM (irela->r_info) & 0xffffffff);
1041       if (add != 0)
1042         sprintf (name + len - 9, "+%x", add);
1043
1044       h = elf_link_hash_lookup (&htab->elf, name, TRUE, TRUE, FALSE);
1045       free (name);
1046       if (h == NULL)
1047         return FALSE;
1048       if (h->root.type == bfd_link_hash_new)
1049         {
1050           h->root.type = bfd_link_hash_defined;
1051           h->root.u.def.section = sec;
1052           h->root.u.def.value = sec->size - OVL_STUB_SIZE;
1053           h->size = OVL_STUB_SIZE;
1054           h->type = STT_FUNC;
1055           h->ref_regular = 1;
1056           h->def_regular = 1;
1057           h->ref_regular_nonweak = 1;
1058           h->forced_local = 1;
1059           h->non_elf = 0;
1060         }
1061     }
1062
1063   return TRUE;
1064 }
1065
1066 /* Called via elf_link_hash_traverse to allocate stubs for any _SPUEAR_
1067    symbols.  */
1068
1069 static bfd_boolean
1070 allocate_spuear_stubs (struct elf_link_hash_entry *h, void *inf)
1071 {
1072   /* Symbols starting with _SPUEAR_ need a stub because they may be
1073      invoked by the PPU.  */
1074   struct bfd_link_info *info = inf;
1075   struct spu_link_hash_table *htab = spu_hash_table (info);
1076   asection *sym_sec;
1077
1078   if ((h->root.type == bfd_link_hash_defined
1079        || h->root.type == bfd_link_hash_defweak)
1080       && h->def_regular
1081       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0
1082       && (sym_sec = h->root.u.def.section) != NULL
1083       && sym_sec->output_section != NULL
1084       && sym_sec->output_section->owner == info->output_bfd
1085       && spu_elf_section_data (sym_sec->output_section) != NULL
1086       && (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index != 0
1087           || htab->non_overlay_stubs))
1088     {
1089       count_stub (htab, NULL, NULL, nonovl_stub, h, NULL);
1090     }
1091
1092   return TRUE;
1093 }
1094
1095 static bfd_boolean
1096 build_spuear_stubs (struct elf_link_hash_entry *h, void *inf)
1097 {
1098   /* Symbols starting with _SPUEAR_ need a stub because they may be
1099      invoked by the PPU.  */
1100   struct bfd_link_info *info = inf;
1101   struct spu_link_hash_table *htab = spu_hash_table (info);
1102   asection *sym_sec;
1103
1104   if ((h->root.type == bfd_link_hash_defined
1105        || h->root.type == bfd_link_hash_defweak)
1106       && h->def_regular
1107       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0
1108       && (sym_sec = h->root.u.def.section) != NULL
1109       && sym_sec->output_section != NULL
1110       && sym_sec->output_section->owner == info->output_bfd
1111       && spu_elf_section_data (sym_sec->output_section) != NULL
1112       && (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index != 0
1113           || htab->non_overlay_stubs))
1114     {
1115       build_stub (htab, NULL, NULL, nonovl_stub, h, NULL,
1116                   h->root.u.def.value, sym_sec);
1117     }
1118
1119   return TRUE;
1120 }
1121
1122 /* Size or build stubs.  */
1123
1124 static bfd_boolean
1125 process_stubs (struct bfd_link_info *info, bfd_boolean build)
1126 {
1127   struct spu_link_hash_table *htab = spu_hash_table (info);
1128   bfd *ibfd;
1129
1130   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
1131     {
1132       extern const bfd_target bfd_elf32_spu_vec;
1133       Elf_Internal_Shdr *symtab_hdr;
1134       asection *isec;
1135       Elf_Internal_Sym *local_syms = NULL;
1136       void *psyms;
1137
1138       if (ibfd->xvec != &bfd_elf32_spu_vec)
1139         continue;
1140
1141       /* We'll need the symbol table in a second.  */
1142       symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
1143       if (symtab_hdr->sh_info == 0)
1144         continue;
1145
1146       /* Arrange to read and keep global syms for later stack analysis.  */
1147       psyms = &local_syms;
1148       if (htab->stack_analysis)
1149         psyms = &symtab_hdr->contents;
1150
1151       /* Walk over each section attached to the input bfd.  */
1152       for (isec = ibfd->sections; isec != NULL; isec = isec->next)
1153         {
1154           Elf_Internal_Rela *internal_relocs, *irelaend, *irela;
1155
1156           /* If there aren't any relocs, then there's nothing more to do.  */
1157           if ((isec->flags & SEC_RELOC) == 0
1158               || isec->reloc_count == 0)
1159             continue;
1160
1161           if (!maybe_needs_stubs (isec, info->output_bfd))
1162             continue;
1163
1164           /* Get the relocs.  */
1165           internal_relocs = _bfd_elf_link_read_relocs (ibfd, isec, NULL, NULL,
1166                                                        info->keep_memory);
1167           if (internal_relocs == NULL)
1168             goto error_ret_free_local;
1169
1170           /* Now examine each relocation.  */
1171           irela = internal_relocs;
1172           irelaend = irela + isec->reloc_count;
1173           for (; irela < irelaend; irela++)
1174             {
1175               enum elf_spu_reloc_type r_type;
1176               unsigned int r_indx;
1177               asection *sym_sec;
1178               Elf_Internal_Sym *sym;
1179               struct elf_link_hash_entry *h;
1180               enum _stub_type stub_type;
1181
1182               r_type = ELF32_R_TYPE (irela->r_info);
1183               r_indx = ELF32_R_SYM (irela->r_info);
1184
1185               if (r_type >= R_SPU_max)
1186                 {
1187                   bfd_set_error (bfd_error_bad_value);
1188                 error_ret_free_internal:
1189                   if (elf_section_data (isec)->relocs != internal_relocs)
1190                     free (internal_relocs);
1191                 error_ret_free_local:
1192                   if (local_syms != NULL
1193                       && (symtab_hdr->contents
1194                           != (unsigned char *) local_syms))
1195                     free (local_syms);
1196                   return FALSE;
1197                 }
1198
1199               /* Determine the reloc target section.  */
1200               if (!get_sym_h (&h, &sym, &sym_sec, psyms, r_indx, ibfd))
1201                 goto error_ret_free_internal;
1202
1203               stub_type = needs_ovl_stub (h, sym, sym_sec, isec, irela,
1204                                           NULL, info);
1205               if (stub_type == no_stub)
1206                 continue;
1207               else if (stub_type == stub_error)
1208                 goto error_ret_free_internal;
1209
1210               if (htab->stub_count == NULL)
1211                 {
1212                   bfd_size_type amt;
1213                   amt = (htab->num_overlays + 1) * sizeof (*htab->stub_count);
1214                   htab->stub_count = bfd_zmalloc (amt);
1215                   if (htab->stub_count == NULL)
1216                     goto error_ret_free_internal;
1217                 }
1218
1219               if (!build)
1220                 {
1221                   if (!count_stub (htab, ibfd, isec, stub_type, h, irela))
1222                     goto error_ret_free_internal;
1223                 }
1224               else
1225                 {
1226                   bfd_vma dest;
1227
1228                   if (h != NULL)
1229                     dest = h->root.u.def.value;
1230                   else
1231                     dest = sym->st_value;
1232                   dest += irela->r_addend;
1233                   if (!build_stub (htab, ibfd, isec, stub_type, h, irela,
1234                                    dest, sym_sec))
1235                     goto error_ret_free_internal;
1236                 }
1237             }
1238
1239           /* We're done with the internal relocs, free them.  */
1240           if (elf_section_data (isec)->relocs != internal_relocs)
1241             free (internal_relocs);
1242         }
1243
1244       if (local_syms != NULL
1245           && symtab_hdr->contents != (unsigned char *) local_syms)
1246         {
1247           if (!info->keep_memory)
1248             free (local_syms);
1249           else
1250             symtab_hdr->contents = (unsigned char *) local_syms;
1251         }
1252     }
1253
1254   return TRUE;
1255 }
1256
1257 /* Allocate space for overlay call and return stubs.  */
1258
1259 int
1260 spu_elf_size_stubs (struct bfd_link_info *info,
1261                     void (*place_spu_section) (asection *, asection *,
1262                                                const char *),
1263                     int non_overlay_stubs)
1264 {
1265   struct spu_link_hash_table *htab = spu_hash_table (info);
1266   bfd *ibfd;
1267   bfd_size_type amt;
1268   flagword flags;
1269   unsigned int i;
1270   asection *stub;
1271
1272   htab->non_overlay_stubs = non_overlay_stubs;
1273   if (!process_stubs (info, FALSE))
1274     return 0;
1275
1276   elf_link_hash_traverse (&htab->elf, allocate_spuear_stubs, info);
1277   if (htab->stub_err)
1278     return 0;
1279
1280   if (htab->stub_count == NULL)
1281     return 1;
1282
1283   ibfd = info->input_bfds;
1284   amt = (htab->num_overlays + 1) * sizeof (*htab->stub_sec);
1285   htab->stub_sec = bfd_zmalloc (amt);
1286   if (htab->stub_sec == NULL)
1287     return 0;
1288
1289   flags = (SEC_ALLOC | SEC_LOAD | SEC_CODE | SEC_READONLY
1290            | SEC_HAS_CONTENTS | SEC_IN_MEMORY);
1291   stub = bfd_make_section_anyway_with_flags (ibfd, ".stub", flags);
1292   htab->stub_sec[0] = stub;
1293   if (stub == NULL
1294       || !bfd_set_section_alignment (ibfd, stub, 3 + (OVL_STUB_SIZE > 8)))
1295     return 0;
1296   stub->size = htab->stub_count[0] * OVL_STUB_SIZE;
1297   (*place_spu_section) (stub, NULL, ".text");
1298
1299   for (i = 0; i < htab->num_overlays; ++i)
1300     {
1301       asection *osec = htab->ovl_sec[i];
1302       unsigned int ovl = spu_elf_section_data (osec)->u.o.ovl_index;
1303       stub = bfd_make_section_anyway_with_flags (ibfd, ".stub", flags);
1304       htab->stub_sec[ovl] = stub;
1305       if (stub == NULL
1306           || !bfd_set_section_alignment (ibfd, stub, 3 + (OVL_STUB_SIZE > 8)))
1307         return 0;
1308       stub->size = htab->stub_count[ovl] * OVL_STUB_SIZE;
1309       (*place_spu_section) (stub, osec, NULL);
1310     }
1311
1312  /* htab->ovtab consists of two arrays.
1313     .   struct {
1314     .     u32 vma;
1315     .     u32 size;
1316     .     u32 file_off;
1317     .     u32 buf;
1318     .   } _ovly_table[];
1319     .
1320     .   struct {
1321     .     u32 mapped;
1322     .   } _ovly_buf_table[];
1323     .  */
1324
1325   flags = (SEC_ALLOC | SEC_LOAD
1326            | SEC_HAS_CONTENTS | SEC_IN_MEMORY);
1327   htab->ovtab = bfd_make_section_anyway_with_flags (ibfd, ".ovtab", flags);
1328   if (htab->ovtab == NULL
1329       || !bfd_set_section_alignment (ibfd, htab->ovtab, 4))
1330     return 0;
1331
1332   htab->ovtab->size = htab->num_overlays * 16 + 16 + htab->num_buf * 4;
1333   (*place_spu_section) (htab->ovtab, NULL, ".data");
1334
1335   htab->toe = bfd_make_section_anyway_with_flags (ibfd, ".toe", SEC_ALLOC);
1336   if (htab->toe == NULL
1337       || !bfd_set_section_alignment (ibfd, htab->toe, 4))
1338     return 0;
1339   htab->toe->size = 16;
1340   (*place_spu_section) (htab->toe, NULL, ".toe");
1341
1342   return 2;
1343 }
1344
1345 /* Functions to handle embedded spu_ovl.o object.  */
1346
1347 static void *
1348 ovl_mgr_open (struct bfd *nbfd ATTRIBUTE_UNUSED, void *stream)
1349 {
1350   return stream;
1351 }
1352
1353 static file_ptr
1354 ovl_mgr_pread (struct bfd *abfd ATTRIBUTE_UNUSED,
1355                void *stream,
1356                void *buf,
1357                file_ptr nbytes,
1358                file_ptr offset)
1359 {
1360   struct _ovl_stream *os;
1361   size_t count;
1362   size_t max;
1363
1364   os = (struct _ovl_stream *) stream;
1365   max = (const char *) os->end - (const char *) os->start;
1366
1367   if ((ufile_ptr) offset >= max)
1368     return 0;
1369
1370   count = nbytes;
1371   if (count > max - offset)
1372     count = max - offset;
1373
1374   memcpy (buf, (const char *) os->start + offset, count);
1375   return count;
1376 }
1377
1378 bfd_boolean
1379 spu_elf_open_builtin_lib (bfd **ovl_bfd, const struct _ovl_stream *stream)
1380 {
1381   *ovl_bfd = bfd_openr_iovec ("builtin ovl_mgr",
1382                               "elf32-spu",
1383                               ovl_mgr_open,
1384                               (void *) stream,
1385                               ovl_mgr_pread,
1386                               NULL,
1387                               NULL);
1388   return *ovl_bfd != NULL;
1389 }
1390
1391 /* Define an STT_OBJECT symbol.  */
1392
1393 static struct elf_link_hash_entry *
1394 define_ovtab_symbol (struct spu_link_hash_table *htab, const char *name)
1395 {
1396   struct elf_link_hash_entry *h;
1397
1398   h = elf_link_hash_lookup (&htab->elf, name, TRUE, FALSE, FALSE);
1399   if (h == NULL)
1400     return NULL;
1401
1402   if (h->root.type != bfd_link_hash_defined
1403       || !h->def_regular)
1404     {
1405       h->root.type = bfd_link_hash_defined;
1406       h->root.u.def.section = htab->ovtab;
1407       h->type = STT_OBJECT;
1408       h->ref_regular = 1;
1409       h->def_regular = 1;
1410       h->ref_regular_nonweak = 1;
1411       h->non_elf = 0;
1412     }
1413   else
1414     {
1415       (*_bfd_error_handler) (_("%B is not allowed to define %s"),
1416                              h->root.u.def.section->owner,
1417                              h->root.root.string);
1418       bfd_set_error (bfd_error_bad_value);
1419       return NULL;
1420     }
1421
1422   return h;
1423 }
1424
1425 /* Fill in all stubs and the overlay tables.  */
1426
1427 bfd_boolean
1428 spu_elf_build_stubs (struct bfd_link_info *info, int emit_syms)
1429 {
1430   struct spu_link_hash_table *htab = spu_hash_table (info);
1431   struct elf_link_hash_entry *h;
1432   bfd_byte *p;
1433   asection *s;
1434   bfd *obfd;
1435   unsigned int i;
1436
1437   htab->emit_stub_syms = emit_syms;
1438   if (htab->stub_count == NULL)
1439     return TRUE;
1440
1441   for (i = 0; i <= htab->num_overlays; i++)
1442     if (htab->stub_sec[i]->size != 0)
1443       {
1444         htab->stub_sec[i]->contents = bfd_zalloc (htab->stub_sec[i]->owner,
1445                                                   htab->stub_sec[i]->size);
1446         if (htab->stub_sec[i]->contents == NULL)
1447           return FALSE;
1448         htab->stub_sec[i]->rawsize = htab->stub_sec[i]->size;
1449         htab->stub_sec[i]->size = 0;
1450       }
1451
1452   h = elf_link_hash_lookup (&htab->elf, "__ovly_load", FALSE, FALSE, FALSE);
1453   htab->ovly_load = h;
1454   BFD_ASSERT (h != NULL
1455               && (h->root.type == bfd_link_hash_defined
1456                   || h->root.type == bfd_link_hash_defweak)
1457               && h->def_regular);
1458
1459   s = h->root.u.def.section->output_section;
1460   if (spu_elf_section_data (s)->u.o.ovl_index)
1461     {
1462       (*_bfd_error_handler) (_("%s in overlay section"),
1463                              h->root.root.string);
1464       bfd_set_error (bfd_error_bad_value);
1465       return FALSE;
1466     }
1467
1468   h = elf_link_hash_lookup (&htab->elf, "__ovly_return", FALSE, FALSE, FALSE);
1469   htab->ovly_return = h;
1470
1471   /* Fill in all the stubs.  */
1472   process_stubs (info, TRUE);
1473
1474   elf_link_hash_traverse (&htab->elf, build_spuear_stubs, info);
1475   if (htab->stub_err)
1476     return FALSE;
1477
1478   for (i = 0; i <= htab->num_overlays; i++)
1479     {
1480       if (htab->stub_sec[i]->size != htab->stub_sec[i]->rawsize)
1481         {
1482           (*_bfd_error_handler)  (_("stubs don't match calculated size"));
1483           bfd_set_error (bfd_error_bad_value);
1484           return FALSE;
1485         }
1486       htab->stub_sec[i]->rawsize = 0;
1487     }
1488
1489   if (htab->stub_err)
1490     {
1491       (*_bfd_error_handler) (_("overlay stub relocation overflow"));
1492       bfd_set_error (bfd_error_bad_value);
1493       return FALSE;
1494     }
1495
1496   htab->ovtab->contents = bfd_zalloc (htab->ovtab->owner, htab->ovtab->size);
1497   if (htab->ovtab->contents == NULL)
1498     return FALSE;
1499
1500   /* Write out _ovly_table.  */
1501   p = htab->ovtab->contents;
1502   /* set low bit of .size to mark non-overlay area as present.  */
1503   p[7] = 1;
1504   obfd = htab->ovtab->output_section->owner;
1505   for (s = obfd->sections; s != NULL; s = s->next)
1506     {
1507       unsigned int ovl_index = spu_elf_section_data (s)->u.o.ovl_index;
1508
1509       if (ovl_index != 0)
1510         {
1511           unsigned long off = ovl_index * 16;
1512           unsigned int ovl_buf = spu_elf_section_data (s)->u.o.ovl_buf;
1513
1514           bfd_put_32 (htab->ovtab->owner, s->vma, p + off);
1515           bfd_put_32 (htab->ovtab->owner, (s->size + 15) & -16, p + off + 4);
1516           /* file_off written later in spu_elf_modify_program_headers.  */
1517           bfd_put_32 (htab->ovtab->owner, ovl_buf, p + off + 12);
1518         }
1519     }
1520
1521   h = define_ovtab_symbol (htab, "_ovly_table");
1522   if (h == NULL)
1523     return FALSE;
1524   h->root.u.def.value = 16;
1525   h->size = htab->num_overlays * 16;
1526
1527   h = define_ovtab_symbol (htab, "_ovly_table_end");
1528   if (h == NULL)
1529     return FALSE;
1530   h->root.u.def.value = htab->num_overlays * 16 + 16;
1531   h->size = 0;
1532
1533   h = define_ovtab_symbol (htab, "_ovly_buf_table");
1534   if (h == NULL)
1535     return FALSE;
1536   h->root.u.def.value = htab->num_overlays * 16 + 16;
1537   h->size = htab->num_buf * 4;
1538
1539   h = define_ovtab_symbol (htab, "_ovly_buf_table_end");
1540   if (h == NULL)
1541     return FALSE;
1542   h->root.u.def.value = htab->num_overlays * 16 + 16 + htab->num_buf * 4;
1543   h->size = 0;
1544
1545   h = define_ovtab_symbol (htab, "_EAR_");
1546   if (h == NULL)
1547     return FALSE;
1548   h->root.u.def.section = htab->toe;
1549   h->root.u.def.value = 0;
1550   h->size = 16;
1551
1552   return TRUE;
1553 }
1554
1555 /* Check that all loadable section VMAs lie in the range
1556    LO .. HI inclusive, and stash some parameters for --auto-overlay.  */
1557
1558 asection *
1559 spu_elf_check_vma (struct bfd_link_info *info,
1560                    int auto_overlay,
1561                    unsigned int lo,
1562                    unsigned int hi,
1563                    unsigned int overlay_fixed,
1564                    unsigned int reserved,
1565                    void (*spu_elf_load_ovl_mgr) (void),
1566                    FILE *(*spu_elf_open_overlay_script) (void),
1567                    void (*spu_elf_relink) (void))
1568 {
1569   struct elf_segment_map *m;
1570   unsigned int i;
1571   struct spu_link_hash_table *htab = spu_hash_table (info);
1572   bfd *abfd = info->output_bfd;
1573
1574   if (auto_overlay & AUTO_OVERLAY)
1575     htab->auto_overlay = auto_overlay;
1576   htab->local_store = hi + 1 - lo;
1577   htab->overlay_fixed = overlay_fixed;
1578   htab->reserved = reserved;
1579   htab->spu_elf_load_ovl_mgr = spu_elf_load_ovl_mgr;
1580   htab->spu_elf_open_overlay_script = spu_elf_open_overlay_script;
1581   htab->spu_elf_relink = spu_elf_relink;
1582
1583   for (m = elf_tdata (abfd)->segment_map; m != NULL; m = m->next)
1584     if (m->p_type == PT_LOAD)
1585       for (i = 0; i < m->count; i++)
1586         if (m->sections[i]->size != 0
1587             && (m->sections[i]->vma < lo
1588                 || m->sections[i]->vma > hi
1589                 || m->sections[i]->vma + m->sections[i]->size - 1 > hi))
1590           return m->sections[i];
1591
1592   /* No need for overlays if it all fits.  */
1593   htab->auto_overlay = 0;
1594   return NULL;
1595 }
1596
1597 /* OFFSET in SEC (presumably) is the beginning of a function prologue.
1598    Search for stack adjusting insns, and return the sp delta.  */
1599
1600 static int
1601 find_function_stack_adjust (asection *sec, bfd_vma offset)
1602 {
1603   int unrecog;
1604   int reg[128];
1605
1606   memset (reg, 0, sizeof (reg));
1607   for (unrecog = 0; offset + 4 <= sec->size && unrecog < 32; offset += 4)
1608     {
1609       unsigned char buf[4];
1610       int rt, ra;
1611       int imm;
1612
1613       /* Assume no relocs on stack adjusing insns.  */
1614       if (!bfd_get_section_contents (sec->owner, sec, buf, offset, 4))
1615         break;
1616
1617       if (buf[0] == 0x24 /* stqd */)
1618         continue;
1619
1620       rt = buf[3] & 0x7f;
1621       ra = ((buf[2] & 0x3f) << 1) | (buf[3] >> 7);
1622       /* Partly decoded immediate field.  */
1623       imm = (buf[1] << 9) | (buf[2] << 1) | (buf[3] >> 7);
1624
1625       if (buf[0] == 0x1c /* ai */)
1626         {
1627           imm >>= 7;
1628           imm = (imm ^ 0x200) - 0x200;
1629           reg[rt] = reg[ra] + imm;
1630
1631           if (rt == 1 /* sp */)
1632             {
1633               if (imm > 0)
1634                 break;
1635               return reg[rt];
1636             }
1637         }
1638       else if (buf[0] == 0x18 && (buf[1] & 0xe0) == 0 /* a */)
1639         {
1640           int rb = ((buf[1] & 0x1f) << 2) | ((buf[2] & 0xc0) >> 6);
1641
1642           reg[rt] = reg[ra] + reg[rb];
1643           if (rt == 1)
1644             return reg[rt];
1645         }
1646       else if ((buf[0] & 0xfc) == 0x40 /* il, ilh, ilhu, ila */)
1647         {
1648           if (buf[0] >= 0x42 /* ila */)
1649             imm |= (buf[0] & 1) << 17;
1650           else
1651             {
1652               imm &= 0xffff;
1653
1654               if (buf[0] == 0x40 /* il */)
1655                 {
1656                   if ((buf[1] & 0x80) == 0)
1657                     goto unknown_insn;
1658                   imm = (imm ^ 0x8000) - 0x8000;
1659                 }
1660               else if ((buf[1] & 0x80) == 0 /* ilhu */)
1661                 imm <<= 16;
1662             }
1663           reg[rt] = imm;
1664           continue;
1665         }
1666       else if (buf[0] == 0x60 && (buf[1] & 0x80) != 0 /* iohl */)
1667         {
1668           reg[rt] |= imm & 0xffff;
1669           continue;
1670         }
1671       else if (buf[0] == 0x04 /* ori */)
1672         {
1673           imm >>= 7;
1674           imm = (imm ^ 0x200) - 0x200;
1675           reg[rt] = reg[ra] | imm;
1676           continue;
1677         }
1678       else if ((buf[0] == 0x33 && imm == 1 /* brsl .+4 */)
1679                || (buf[0] == 0x08 && (buf[1] & 0xe0) == 0 /* sf */))
1680         {
1681           /* Used in pic reg load.  Say rt is trashed.  */
1682           reg[rt] = 0;
1683           continue;
1684         }
1685       else if (is_branch (buf) || is_indirect_branch (buf))
1686         /* If we hit a branch then we must be out of the prologue.  */
1687         break;
1688     unknown_insn:
1689       ++unrecog;
1690     }
1691
1692   return 0;
1693 }
1694
1695 /* qsort predicate to sort symbols by section and value.  */
1696
1697 static Elf_Internal_Sym *sort_syms_syms;
1698 static asection **sort_syms_psecs;
1699
1700 static int
1701 sort_syms (const void *a, const void *b)
1702 {
1703   Elf_Internal_Sym *const *s1 = a;
1704   Elf_Internal_Sym *const *s2 = b;
1705   asection *sec1,*sec2;
1706   bfd_signed_vma delta;
1707
1708   sec1 = sort_syms_psecs[*s1 - sort_syms_syms];
1709   sec2 = sort_syms_psecs[*s2 - sort_syms_syms];
1710
1711   if (sec1 != sec2)
1712     return sec1->index - sec2->index;
1713
1714   delta = (*s1)->st_value - (*s2)->st_value;
1715   if (delta != 0)
1716     return delta < 0 ? -1 : 1;
1717
1718   delta = (*s2)->st_size - (*s1)->st_size;
1719   if (delta != 0)
1720     return delta < 0 ? -1 : 1;
1721
1722   return *s1 < *s2 ? -1 : 1;
1723 }
1724
1725 struct call_info
1726 {
1727   struct function_info *fun;
1728   struct call_info *next;
1729   unsigned int count;
1730   unsigned int max_depth;
1731   unsigned int is_tail : 1;
1732   unsigned int is_pasted : 1;
1733 };
1734
1735 struct function_info
1736 {
1737   /* List of functions called.  Also branches to hot/cold part of
1738      function.  */
1739   struct call_info *call_list;
1740   /* For hot/cold part of function, point to owner.  */
1741   struct function_info *start;
1742   /* Symbol at start of function.  */
1743   union {
1744     Elf_Internal_Sym *sym;
1745     struct elf_link_hash_entry *h;
1746   } u;
1747   /* Function section.  */
1748   asection *sec;
1749   asection *rodata;
1750   /* Where last called from, and number of sections called from.  */
1751   asection *last_caller;
1752   unsigned int call_count;
1753   /* Address range of (this part of) function.  */
1754   bfd_vma lo, hi;
1755   /* Stack usage.  */
1756   int stack;
1757   /* Distance from root of call tree.  Tail and hot/cold branches
1758      count as one deeper.  We aren't counting stack frames here.  */
1759   unsigned int depth;
1760   /* Set if global symbol.  */
1761   unsigned int global : 1;
1762   /* Set if known to be start of function (as distinct from a hunk
1763      in hot/cold section.  */
1764   unsigned int is_func : 1;
1765   /* Set if not a root node.  */
1766   unsigned int non_root : 1;
1767   /* Flags used during call tree traversal.  It's cheaper to replicate
1768      the visit flags than have one which needs clearing after a traversal.  */
1769   unsigned int visit1 : 1;
1770   unsigned int visit2 : 1;
1771   unsigned int marking : 1;
1772   unsigned int visit3 : 1;
1773   unsigned int visit4 : 1;
1774   unsigned int visit5 : 1;
1775   unsigned int visit6 : 1;
1776   unsigned int visit7 : 1;
1777 };
1778
1779 struct spu_elf_stack_info
1780 {
1781   int num_fun;
1782   int max_fun;
1783   /* Variable size array describing functions, one per contiguous
1784      address range belonging to a function.  */
1785   struct function_info fun[1];
1786 };
1787
1788 /* Allocate a struct spu_elf_stack_info with MAX_FUN struct function_info
1789    entries for section SEC.  */
1790
1791 static struct spu_elf_stack_info *
1792 alloc_stack_info (asection *sec, int max_fun)
1793 {
1794   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
1795   bfd_size_type amt;
1796
1797   amt = sizeof (struct spu_elf_stack_info);
1798   amt += (max_fun - 1) * sizeof (struct function_info);
1799   sec_data->u.i.stack_info = bfd_zmalloc (amt);
1800   if (sec_data->u.i.stack_info != NULL)
1801     sec_data->u.i.stack_info->max_fun = max_fun;
1802   return sec_data->u.i.stack_info;
1803 }
1804
1805 /* Add a new struct function_info describing a (part of a) function
1806    starting at SYM_H.  Keep the array sorted by address.  */
1807
1808 static struct function_info *
1809 maybe_insert_function (asection *sec,
1810                        void *sym_h,
1811                        bfd_boolean global,
1812                        bfd_boolean is_func)
1813 {
1814   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
1815   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
1816   int i;
1817   bfd_vma off, size;
1818
1819   if (sinfo == NULL)
1820     {
1821       sinfo = alloc_stack_info (sec, 20);
1822       if (sinfo == NULL)
1823         return NULL;
1824     }
1825
1826   if (!global)
1827     {
1828       Elf_Internal_Sym *sym = sym_h;
1829       off = sym->st_value;
1830       size = sym->st_size;
1831     }
1832   else
1833     {
1834       struct elf_link_hash_entry *h = sym_h;
1835       off = h->root.u.def.value;
1836       size = h->size;
1837     }
1838
1839   for (i = sinfo->num_fun; --i >= 0; )
1840     if (sinfo->fun[i].lo <= off)
1841       break;
1842
1843   if (i >= 0)
1844     {
1845       /* Don't add another entry for an alias, but do update some
1846          info.  */
1847       if (sinfo->fun[i].lo == off)
1848         {
1849           /* Prefer globals over local syms.  */
1850           if (global && !sinfo->fun[i].global)
1851             {
1852               sinfo->fun[i].global = TRUE;
1853               sinfo->fun[i].u.h = sym_h;
1854             }
1855           if (is_func)
1856             sinfo->fun[i].is_func = TRUE;
1857           return &sinfo->fun[i];
1858         }
1859       /* Ignore a zero-size symbol inside an existing function.  */
1860       else if (sinfo->fun[i].hi > off && size == 0)
1861         return &sinfo->fun[i];
1862     }
1863
1864   if (++i < sinfo->num_fun)
1865     memmove (&sinfo->fun[i + 1], &sinfo->fun[i],
1866              (sinfo->num_fun - i) * sizeof (sinfo->fun[i]));
1867   else if (i >= sinfo->max_fun)
1868     {
1869       bfd_size_type amt = sizeof (struct spu_elf_stack_info);
1870       bfd_size_type old = amt;
1871
1872       old += (sinfo->max_fun - 1) * sizeof (struct function_info);
1873       sinfo->max_fun += 20 + (sinfo->max_fun >> 1);
1874       amt += (sinfo->max_fun - 1) * sizeof (struct function_info);
1875       sinfo = bfd_realloc (sinfo, amt);
1876       if (sinfo == NULL)
1877         return NULL;
1878       memset ((char *) sinfo + old, 0, amt - old);
1879       sec_data->u.i.stack_info = sinfo;
1880     }
1881   sinfo->fun[i].is_func = is_func;
1882   sinfo->fun[i].global = global;
1883   sinfo->fun[i].sec = sec;
1884   if (global)
1885     sinfo->fun[i].u.h = sym_h;
1886   else
1887     sinfo->fun[i].u.sym = sym_h;
1888   sinfo->fun[i].lo = off;
1889   sinfo->fun[i].hi = off + size;
1890   sinfo->fun[i].stack = -find_function_stack_adjust (sec, off);
1891   sinfo->num_fun += 1;
1892   return &sinfo->fun[i];
1893 }
1894
1895 /* Return the name of FUN.  */
1896
1897 static const char *
1898 func_name (struct function_info *fun)
1899 {
1900   asection *sec;
1901   bfd *ibfd;
1902   Elf_Internal_Shdr *symtab_hdr;
1903
1904   while (fun->start != NULL)
1905     fun = fun->start;
1906
1907   if (fun->global)
1908     return fun->u.h->root.root.string;
1909
1910   sec = fun->sec;
1911   if (fun->u.sym->st_name == 0)
1912     {
1913       size_t len = strlen (sec->name);
1914       char *name = bfd_malloc (len + 10);
1915       if (name == NULL)
1916         return "(null)";
1917       sprintf (name, "%s+%lx", sec->name,
1918                (unsigned long) fun->u.sym->st_value & 0xffffffff);
1919       return name;
1920     }
1921   ibfd = sec->owner;
1922   symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
1923   return bfd_elf_sym_name (ibfd, symtab_hdr, fun->u.sym, sec);
1924 }
1925
1926 /* Read the instruction at OFF in SEC.  Return true iff the instruction
1927    is a nop, lnop, or stop 0 (all zero insn).  */
1928
1929 static bfd_boolean
1930 is_nop (asection *sec, bfd_vma off)
1931 {
1932   unsigned char insn[4];
1933
1934   if (off + 4 > sec->size
1935       || !bfd_get_section_contents (sec->owner, sec, insn, off, 4))
1936     return FALSE;
1937   if ((insn[0] & 0xbf) == 0 && (insn[1] & 0xe0) == 0x20)
1938     return TRUE;
1939   if (insn[0] == 0 && insn[1] == 0 && insn[2] == 0 && insn[3] == 0)
1940     return TRUE;
1941   return FALSE;
1942 }
1943
1944 /* Extend the range of FUN to cover nop padding up to LIMIT.
1945    Return TRUE iff some instruction other than a NOP was found.  */
1946
1947 static bfd_boolean
1948 insns_at_end (struct function_info *fun, bfd_vma limit)
1949 {
1950   bfd_vma off = (fun->hi + 3) & -4;
1951
1952   while (off < limit && is_nop (fun->sec, off))
1953     off += 4;
1954   if (off < limit)
1955     {
1956       fun->hi = off;
1957       return TRUE;
1958     }
1959   fun->hi = limit;
1960   return FALSE;
1961 }
1962
1963 /* Check and fix overlapping function ranges.  Return TRUE iff there
1964    are gaps in the current info we have about functions in SEC.  */
1965
1966 static bfd_boolean
1967 check_function_ranges (asection *sec, struct bfd_link_info *info)
1968 {
1969   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
1970   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
1971   int i;
1972   bfd_boolean gaps = FALSE;
1973
1974   if (sinfo == NULL)
1975     return FALSE;
1976
1977   for (i = 1; i < sinfo->num_fun; i++)
1978     if (sinfo->fun[i - 1].hi > sinfo->fun[i].lo)
1979       {
1980         /* Fix overlapping symbols.  */
1981         const char *f1 = func_name (&sinfo->fun[i - 1]);
1982         const char *f2 = func_name (&sinfo->fun[i]);
1983
1984         info->callbacks->einfo (_("warning: %s overlaps %s\n"), f1, f2);
1985         sinfo->fun[i - 1].hi = sinfo->fun[i].lo;
1986       }
1987     else if (insns_at_end (&sinfo->fun[i - 1], sinfo->fun[i].lo))
1988       gaps = TRUE;
1989
1990   if (sinfo->num_fun == 0)
1991     gaps = TRUE;
1992   else
1993     {
1994       if (sinfo->fun[0].lo != 0)
1995         gaps = TRUE;
1996       if (sinfo->fun[sinfo->num_fun - 1].hi > sec->size)
1997         {
1998           const char *f1 = func_name (&sinfo->fun[sinfo->num_fun - 1]);
1999
2000           info->callbacks->einfo (_("warning: %s exceeds section size\n"), f1);
2001           sinfo->fun[sinfo->num_fun - 1].hi = sec->size;
2002         }
2003       else if (insns_at_end (&sinfo->fun[sinfo->num_fun - 1], sec->size))
2004         gaps = TRUE;
2005     }
2006   return gaps;
2007 }
2008
2009 /* Search current function info for a function that contains address
2010    OFFSET in section SEC.  */
2011
2012 static struct function_info *
2013 find_function (asection *sec, bfd_vma offset, struct bfd_link_info *info)
2014 {
2015   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
2016   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
2017   int lo, hi, mid;
2018
2019   lo = 0;
2020   hi = sinfo->num_fun;
2021   while (lo < hi)
2022     {
2023       mid = (lo + hi) / 2;
2024       if (offset < sinfo->fun[mid].lo)
2025         hi = mid;
2026       else if (offset >= sinfo->fun[mid].hi)
2027         lo = mid + 1;
2028       else
2029         return &sinfo->fun[mid];
2030     }
2031   info->callbacks->einfo (_("%A:0x%v not found in function table\n"),
2032                           sec, offset);
2033   return NULL;
2034 }
2035
2036 /* Add CALLEE to CALLER call list if not already present.  Return TRUE
2037    if CALLEE was new.  If this function return FALSE, CALLEE should
2038    be freed.  */
2039
2040 static bfd_boolean
2041 insert_callee (struct function_info *caller, struct call_info *callee)
2042 {
2043   struct call_info **pp, *p;
2044
2045   for (pp = &caller->call_list; (p = *pp) != NULL; pp = &p->next)
2046     if (p->fun == callee->fun)
2047       {
2048         /* Tail calls use less stack than normal calls.  Retain entry
2049            for normal call over one for tail call.  */
2050         p->is_tail &= callee->is_tail;
2051         if (!p->is_tail)
2052           {
2053             p->fun->start = NULL;
2054             p->fun->is_func = TRUE;
2055           }
2056         p->count += 1;
2057         /* Reorder list so most recent call is first.  */
2058         *pp = p->next;
2059         p->next = caller->call_list;
2060         caller->call_list = p;
2061         return FALSE;
2062       }
2063   callee->next = caller->call_list;
2064   callee->count += 1;
2065   caller->call_list = callee;
2066   return TRUE;
2067 }
2068
2069 /* Copy CALL and insert the copy into CALLER.  */
2070
2071 static bfd_boolean
2072 copy_callee (struct function_info *caller, const struct call_info *call)
2073 {
2074   struct call_info *callee;
2075   callee = bfd_malloc (sizeof (*callee));
2076   if (callee == NULL)
2077     return FALSE;
2078   *callee = *call;
2079   if (!insert_callee (caller, callee))
2080     free (callee);
2081   return TRUE;
2082 }
2083
2084 /* We're only interested in code sections.  Testing SEC_IN_MEMORY excludes
2085    overlay stub sections.  */
2086
2087 static bfd_boolean
2088 interesting_section (asection *s, bfd *obfd)
2089 {
2090   return (s->output_section != NULL
2091           && s->output_section->owner == obfd
2092           && ((s->flags & (SEC_ALLOC | SEC_LOAD | SEC_CODE | SEC_IN_MEMORY))
2093               == (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2094           && s->size != 0);
2095 }
2096
2097 /* Rummage through the relocs for SEC, looking for function calls.
2098    If CALL_TREE is true, fill in call graph.  If CALL_TREE is false,
2099    mark destination symbols on calls as being functions.  Also
2100    look at branches, which may be tail calls or go to hot/cold
2101    section part of same function.  */
2102
2103 static bfd_boolean
2104 mark_functions_via_relocs (asection *sec,
2105                            struct bfd_link_info *info,
2106                            int call_tree)
2107 {
2108   Elf_Internal_Rela *internal_relocs, *irelaend, *irela;
2109   Elf_Internal_Shdr *symtab_hdr;
2110   Elf_Internal_Sym *syms;
2111   void *psyms;
2112   static bfd_boolean warned;
2113
2114   if (!interesting_section (sec, info->output_bfd)
2115       || sec->reloc_count == 0)
2116     return TRUE;
2117
2118   internal_relocs = _bfd_elf_link_read_relocs (sec->owner, sec, NULL, NULL,
2119                                                info->keep_memory);
2120   if (internal_relocs == NULL)
2121     return FALSE;
2122
2123   symtab_hdr = &elf_tdata (sec->owner)->symtab_hdr;
2124   psyms = &symtab_hdr->contents;
2125   syms = *(Elf_Internal_Sym **) psyms;
2126   irela = internal_relocs;
2127   irelaend = irela + sec->reloc_count;
2128   for (; irela < irelaend; irela++)
2129     {
2130       enum elf_spu_reloc_type r_type;
2131       unsigned int r_indx;
2132       asection *sym_sec;
2133       Elf_Internal_Sym *sym;
2134       struct elf_link_hash_entry *h;
2135       bfd_vma val;
2136       bfd_boolean reject, is_call;
2137       struct function_info *caller;
2138       struct call_info *callee;
2139
2140       reject = FALSE;
2141       r_type = ELF32_R_TYPE (irela->r_info);
2142       if (r_type != R_SPU_REL16
2143           && r_type != R_SPU_ADDR16)
2144         {
2145           reject = TRUE;
2146           if (!(call_tree && spu_hash_table (info)->auto_overlay))
2147             continue;
2148         }
2149
2150       r_indx = ELF32_R_SYM (irela->r_info);
2151       if (!get_sym_h (&h, &sym, &sym_sec, psyms, r_indx, sec->owner))
2152         return FALSE;
2153
2154       if (sym_sec == NULL
2155           || sym_sec->output_section == NULL
2156           || sym_sec->output_section->owner != info->output_bfd)
2157         continue;
2158
2159       is_call = FALSE;
2160       if (!reject)
2161         {
2162           unsigned char insn[4];
2163
2164           if (!bfd_get_section_contents (sec->owner, sec, insn,
2165                                          irela->r_offset, 4))
2166             return FALSE;
2167           if (is_branch (insn))
2168             {
2169               is_call = (insn[0] & 0xfd) == 0x31;
2170               if ((sym_sec->flags & (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2171                   != (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2172                 {
2173                   if (!warned)
2174                     info->callbacks->einfo
2175                       (_("%B(%A+0x%v): call to non-code section"
2176                          " %B(%A), analysis incomplete\n"),
2177                        sec->owner, sec, irela->r_offset,
2178                        sym_sec->owner, sym_sec);
2179                   warned = TRUE;
2180                   continue;
2181                 }
2182             }
2183           else
2184             {
2185               reject = TRUE;
2186               if (!(call_tree && spu_hash_table (info)->auto_overlay)
2187                   || is_hint (insn))
2188                 continue;
2189             }
2190         }
2191
2192       if (reject)
2193         {
2194           /* For --auto-overlay, count possible stubs we need for
2195              function pointer references.  */
2196           unsigned int sym_type;
2197           if (h)
2198             sym_type = h->type;
2199           else
2200             sym_type = ELF_ST_TYPE (sym->st_info);
2201           if (sym_type == STT_FUNC)
2202             spu_hash_table (info)->non_ovly_stub += 1;
2203           continue;
2204         }
2205
2206       if (h)
2207         val = h->root.u.def.value;
2208       else
2209         val = sym->st_value;
2210       val += irela->r_addend;
2211
2212       if (!call_tree)
2213         {
2214           struct function_info *fun;
2215
2216           if (irela->r_addend != 0)
2217             {
2218               Elf_Internal_Sym *fake = bfd_zmalloc (sizeof (*fake));
2219               if (fake == NULL)
2220                 return FALSE;
2221               fake->st_value = val;
2222               fake->st_shndx
2223                 = _bfd_elf_section_from_bfd_section (sym_sec->owner, sym_sec);
2224               sym = fake;
2225             }
2226           if (sym)
2227             fun = maybe_insert_function (sym_sec, sym, FALSE, is_call);
2228           else
2229             fun = maybe_insert_function (sym_sec, h, TRUE, is_call);
2230           if (fun == NULL)
2231             return FALSE;
2232           if (irela->r_addend != 0
2233               && fun->u.sym != sym)
2234             free (sym);
2235           continue;
2236         }
2237
2238       caller = find_function (sec, irela->r_offset, info);
2239       if (caller == NULL)
2240         return FALSE;
2241       callee = bfd_malloc (sizeof *callee);
2242       if (callee == NULL)
2243         return FALSE;
2244
2245       callee->fun = find_function (sym_sec, val, info);
2246       if (callee->fun == NULL)
2247         return FALSE;
2248       callee->is_tail = !is_call;
2249       callee->is_pasted = FALSE;
2250       callee->count = 0;
2251       if (callee->fun->last_caller != sec)
2252         {
2253           callee->fun->last_caller = sec;
2254           callee->fun->call_count += 1;
2255         }
2256       if (!insert_callee (caller, callee))
2257         free (callee);
2258       else if (!is_call
2259                && !callee->fun->is_func
2260                && callee->fun->stack == 0)
2261         {
2262           /* This is either a tail call or a branch from one part of
2263              the function to another, ie. hot/cold section.  If the
2264              destination has been called by some other function then
2265              it is a separate function.  We also assume that functions
2266              are not split across input files.  */
2267           if (sec->owner != sym_sec->owner)
2268             {
2269               callee->fun->start = NULL;
2270               callee->fun->is_func = TRUE;
2271             }
2272           else if (callee->fun->start == NULL)
2273             callee->fun->start = caller;
2274           else
2275             {
2276               struct function_info *callee_start;
2277               struct function_info *caller_start;
2278               callee_start = callee->fun;
2279               while (callee_start->start)
2280                 callee_start = callee_start->start;
2281               caller_start = caller;
2282               while (caller_start->start)
2283                 caller_start = caller_start->start;
2284               if (caller_start != callee_start)
2285                 {
2286                   callee->fun->start = NULL;
2287                   callee->fun->is_func = TRUE;
2288                 }
2289             }
2290         }
2291     }
2292
2293   return TRUE;
2294 }
2295
2296 /* Handle something like .init or .fini, which has a piece of a function.
2297    These sections are pasted together to form a single function.  */
2298
2299 static bfd_boolean
2300 pasted_function (asection *sec, struct bfd_link_info *info)
2301 {
2302   struct bfd_link_order *l;
2303   struct _spu_elf_section_data *sec_data;
2304   struct spu_elf_stack_info *sinfo;
2305   Elf_Internal_Sym *fake;
2306   struct function_info *fun, *fun_start;
2307
2308   fake = bfd_zmalloc (sizeof (*fake));
2309   if (fake == NULL)
2310     return FALSE;
2311   fake->st_value = 0;
2312   fake->st_size = sec->size;
2313   fake->st_shndx
2314     = _bfd_elf_section_from_bfd_section (sec->owner, sec);
2315   fun = maybe_insert_function (sec, fake, FALSE, FALSE);
2316   if (!fun)
2317     return FALSE;
2318
2319   /* Find a function immediately preceding this section.  */
2320   fun_start = NULL;
2321   for (l = sec->output_section->map_head.link_order; l != NULL; l = l->next)
2322     {
2323       if (l->u.indirect.section == sec)
2324         {
2325           if (fun_start != NULL)
2326             {
2327               struct call_info *callee = bfd_malloc (sizeof *callee);
2328               if (callee == NULL)
2329                 return FALSE;
2330
2331               fun->start = fun_start;
2332               callee->fun = fun;
2333               callee->is_tail = TRUE;
2334               callee->is_pasted = TRUE;
2335               callee->count = 0;
2336               if (!insert_callee (fun_start, callee))
2337                 free (callee);
2338               return TRUE;
2339             }
2340           break;
2341         }
2342       if (l->type == bfd_indirect_link_order
2343           && (sec_data = spu_elf_section_data (l->u.indirect.section)) != NULL
2344           && (sinfo = sec_data->u.i.stack_info) != NULL
2345           && sinfo->num_fun != 0)
2346         fun_start = &sinfo->fun[sinfo->num_fun - 1];
2347     }
2348
2349   info->callbacks->einfo (_("%A link_order not found\n"), sec);
2350   return FALSE;
2351 }
2352
2353 /* Map address ranges in code sections to functions.  */
2354
2355 static bfd_boolean
2356 discover_functions (struct bfd_link_info *info)
2357 {
2358   bfd *ibfd;
2359   int bfd_idx;
2360   Elf_Internal_Sym ***psym_arr;
2361   asection ***sec_arr;
2362   bfd_boolean gaps = FALSE;
2363
2364   bfd_idx = 0;
2365   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
2366     bfd_idx++;
2367
2368   psym_arr = bfd_zmalloc (bfd_idx * sizeof (*psym_arr));
2369   if (psym_arr == NULL)
2370     return FALSE;
2371   sec_arr = bfd_zmalloc (bfd_idx * sizeof (*sec_arr));
2372   if (sec_arr == NULL)
2373     return FALSE;
2374
2375
2376   for (ibfd = info->input_bfds, bfd_idx = 0;
2377        ibfd != NULL;
2378        ibfd = ibfd->link_next, bfd_idx++)
2379     {
2380       extern const bfd_target bfd_elf32_spu_vec;
2381       Elf_Internal_Shdr *symtab_hdr;
2382       asection *sec;
2383       size_t symcount;
2384       Elf_Internal_Sym *syms, *sy, **psyms, **psy;
2385       asection **psecs, **p;
2386
2387       if (ibfd->xvec != &bfd_elf32_spu_vec)
2388         continue;
2389
2390       /* Read all the symbols.  */
2391       symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
2392       symcount = symtab_hdr->sh_size / symtab_hdr->sh_entsize;
2393       if (symcount == 0)
2394         {
2395           if (!gaps)
2396             for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
2397               if (interesting_section (sec, info->output_bfd))
2398                 {
2399                   gaps = TRUE;
2400                   break;
2401                 }
2402           continue;
2403         }
2404
2405       syms = (Elf_Internal_Sym *) symtab_hdr->contents;
2406       if (syms == NULL)
2407         {
2408           syms = bfd_elf_get_elf_syms (ibfd, symtab_hdr, symcount, 0,
2409                                        NULL, NULL, NULL);
2410           symtab_hdr->contents = (void *) syms;
2411           if (syms == NULL)
2412             return FALSE;
2413         }
2414
2415       /* Select defined function symbols that are going to be output.  */
2416       psyms = bfd_malloc ((symcount + 1) * sizeof (*psyms));
2417       if (psyms == NULL)
2418         return FALSE;
2419       psym_arr[bfd_idx] = psyms;
2420       psecs = bfd_malloc (symcount * sizeof (*psecs));
2421       if (psecs == NULL)
2422         return FALSE;
2423       sec_arr[bfd_idx] = psecs;
2424       for (psy = psyms, p = psecs, sy = syms; sy < syms + symcount; ++p, ++sy)
2425         if (ELF_ST_TYPE (sy->st_info) == STT_NOTYPE
2426             || ELF_ST_TYPE (sy->st_info) == STT_FUNC)
2427           {
2428             asection *s;
2429
2430             *p = s = bfd_section_from_elf_index (ibfd, sy->st_shndx);
2431             if (s != NULL && interesting_section (s, info->output_bfd))
2432               *psy++ = sy;
2433           }
2434       symcount = psy - psyms;
2435       *psy = NULL;
2436
2437       /* Sort them by section and offset within section.  */
2438       sort_syms_syms = syms;
2439       sort_syms_psecs = psecs;
2440       qsort (psyms, symcount, sizeof (*psyms), sort_syms);
2441
2442       /* Now inspect the function symbols.  */
2443       for (psy = psyms; psy < psyms + symcount; )
2444         {
2445           asection *s = psecs[*psy - syms];
2446           Elf_Internal_Sym **psy2;
2447
2448           for (psy2 = psy; ++psy2 < psyms + symcount; )
2449             if (psecs[*psy2 - syms] != s)
2450               break;
2451
2452           if (!alloc_stack_info (s, psy2 - psy))
2453             return FALSE;
2454           psy = psy2;
2455         }
2456
2457       /* First install info about properly typed and sized functions.
2458          In an ideal world this will cover all code sections, except
2459          when partitioning functions into hot and cold sections,
2460          and the horrible pasted together .init and .fini functions.  */
2461       for (psy = psyms; psy < psyms + symcount; ++psy)
2462         {
2463           sy = *psy;
2464           if (ELF_ST_TYPE (sy->st_info) == STT_FUNC)
2465             {
2466               asection *s = psecs[sy - syms];
2467               if (!maybe_insert_function (s, sy, FALSE, TRUE))
2468                 return FALSE;
2469             }
2470         }
2471
2472       for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
2473         if (interesting_section (sec, info->output_bfd))
2474           gaps |= check_function_ranges (sec, info);
2475     }
2476
2477   if (gaps)
2478     {
2479       /* See if we can discover more function symbols by looking at
2480          relocations.  */
2481       for (ibfd = info->input_bfds, bfd_idx = 0;
2482            ibfd != NULL;
2483            ibfd = ibfd->link_next, bfd_idx++)
2484         {
2485           asection *sec;
2486
2487           if (psym_arr[bfd_idx] == NULL)
2488             continue;
2489
2490           for (sec = ibfd->sections; sec != NULL; sec = sec->next)
2491             if (!mark_functions_via_relocs (sec, info, FALSE))
2492               return FALSE;
2493         }
2494
2495       for (ibfd = info->input_bfds, bfd_idx = 0;
2496            ibfd != NULL;
2497            ibfd = ibfd->link_next, bfd_idx++)
2498         {
2499           Elf_Internal_Shdr *symtab_hdr;
2500           asection *sec;
2501           Elf_Internal_Sym *syms, *sy, **psyms, **psy;
2502           asection **psecs;
2503
2504           if ((psyms = psym_arr[bfd_idx]) == NULL)
2505             continue;
2506
2507           psecs = sec_arr[bfd_idx];
2508
2509           symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
2510           syms = (Elf_Internal_Sym *) symtab_hdr->contents;
2511
2512           gaps = FALSE;
2513           for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
2514             if (interesting_section (sec, info->output_bfd))
2515               gaps |= check_function_ranges (sec, info);
2516           if (!gaps)
2517             continue;
2518
2519           /* Finally, install all globals.  */
2520           for (psy = psyms; (sy = *psy) != NULL; ++psy)
2521             {
2522               asection *s;
2523
2524               s = psecs[sy - syms];
2525
2526               /* Global syms might be improperly typed functions.  */
2527               if (ELF_ST_TYPE (sy->st_info) != STT_FUNC
2528                   && ELF_ST_BIND (sy->st_info) == STB_GLOBAL)
2529                 {
2530                   if (!maybe_insert_function (s, sy, FALSE, FALSE))
2531                     return FALSE;
2532                 }
2533             }
2534         }
2535
2536       for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
2537         {
2538           extern const bfd_target bfd_elf32_spu_vec;
2539           asection *sec;
2540
2541           if (ibfd->xvec != &bfd_elf32_spu_vec)
2542             continue;
2543
2544           /* Some of the symbols we've installed as marking the
2545              beginning of functions may have a size of zero.  Extend
2546              the range of such functions to the beginning of the
2547              next symbol of interest.  */
2548           for (sec = ibfd->sections; sec != NULL; sec = sec->next)
2549             if (interesting_section (sec, info->output_bfd))
2550               {
2551                 struct _spu_elf_section_data *sec_data;
2552                 struct spu_elf_stack_info *sinfo;
2553
2554                 sec_data = spu_elf_section_data (sec);
2555                 sinfo = sec_data->u.i.stack_info;
2556                 if (sinfo != NULL)
2557                   {
2558                     int fun_idx;
2559                     bfd_vma hi = sec->size;
2560
2561                     for (fun_idx = sinfo->num_fun; --fun_idx >= 0; )
2562                       {
2563                         sinfo->fun[fun_idx].hi = hi;
2564                         hi = sinfo->fun[fun_idx].lo;
2565                       }
2566                   }
2567                 /* No symbols in this section.  Must be .init or .fini
2568                    or something similar.  */
2569                 else if (!pasted_function (sec, info))
2570                   return FALSE;
2571               }
2572         }
2573     }
2574
2575   for (ibfd = info->input_bfds, bfd_idx = 0;
2576        ibfd != NULL;
2577        ibfd = ibfd->link_next, bfd_idx++)
2578     {
2579       if (psym_arr[bfd_idx] == NULL)
2580         continue;
2581
2582       free (psym_arr[bfd_idx]);
2583       free (sec_arr[bfd_idx]);
2584     }
2585
2586   free (psym_arr);
2587   free (sec_arr);
2588
2589   return TRUE;
2590 }
2591
2592 /* Iterate over all function_info we have collected, calling DOIT on
2593    each node if ROOT_ONLY is false.  Only call DOIT on root nodes
2594    if ROOT_ONLY.  */
2595
2596 static bfd_boolean
2597 for_each_node (bfd_boolean (*doit) (struct function_info *,
2598                                     struct bfd_link_info *,
2599                                     void *),
2600                struct bfd_link_info *info,
2601                void *param,
2602                int root_only)
2603 {
2604   bfd *ibfd;
2605
2606   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
2607     {
2608       extern const bfd_target bfd_elf32_spu_vec;
2609       asection *sec;
2610
2611       if (ibfd->xvec != &bfd_elf32_spu_vec)
2612         continue;
2613
2614       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
2615         {
2616           struct _spu_elf_section_data *sec_data;
2617           struct spu_elf_stack_info *sinfo;
2618
2619           if ((sec_data = spu_elf_section_data (sec)) != NULL
2620               && (sinfo = sec_data->u.i.stack_info) != NULL)
2621             {
2622               int i;
2623               for (i = 0; i < sinfo->num_fun; ++i)
2624                 if (!root_only || !sinfo->fun[i].non_root)
2625                   if (!doit (&sinfo->fun[i], info, param))
2626                     return FALSE;
2627             }
2628         }
2629     }
2630   return TRUE;
2631 }
2632
2633 /* Transfer call info attached to struct function_info entries for
2634    all of a given function's sections to the first entry.  */
2635
2636 static bfd_boolean
2637 transfer_calls (struct function_info *fun,
2638                 struct bfd_link_info *info ATTRIBUTE_UNUSED,
2639                 void *param ATTRIBUTE_UNUSED)
2640 {
2641   struct function_info *start = fun->start;
2642
2643   if (start != NULL)
2644     {
2645       struct call_info *call, *call_next;
2646
2647       while (start->start != NULL)
2648         start = start->start;
2649       for (call = fun->call_list; call != NULL; call = call_next)
2650         {
2651           call_next = call->next;
2652           if (!insert_callee (start, call))
2653             free (call);
2654         }
2655       fun->call_list = NULL;
2656     }
2657   return TRUE;
2658 }
2659
2660 /* Mark nodes in the call graph that are called by some other node.  */
2661
2662 static bfd_boolean
2663 mark_non_root (struct function_info *fun,
2664                struct bfd_link_info *info ATTRIBUTE_UNUSED,
2665                void *param ATTRIBUTE_UNUSED)
2666 {
2667   struct call_info *call;
2668
2669   if (fun->visit1)
2670     return TRUE;
2671   fun->visit1 = TRUE;
2672   for (call = fun->call_list; call; call = call->next)
2673     {
2674       call->fun->non_root = TRUE;
2675       mark_non_root (call->fun, 0, 0);
2676     }
2677   return TRUE;
2678 }
2679
2680 /* Remove cycles from the call graph.  Set depth of nodes.  */
2681
2682 static bfd_boolean
2683 remove_cycles (struct function_info *fun,
2684                struct bfd_link_info *info,
2685                void *param)
2686 {
2687   struct call_info **callp, *call;
2688   unsigned int depth = *(unsigned int *) param;
2689   unsigned int max_depth = depth;
2690
2691   fun->depth = depth;
2692   fun->visit2 = TRUE;
2693   fun->marking = TRUE;
2694
2695   callp = &fun->call_list;
2696   while ((call = *callp) != NULL)
2697     {
2698       if (!call->fun->visit2)
2699         {
2700           call->max_depth = depth + !call->is_pasted;
2701           if (!remove_cycles (call->fun, info, &call->max_depth))
2702             return FALSE;
2703           if (max_depth < call->max_depth)
2704             max_depth = call->max_depth;
2705         }
2706       else if (call->fun->marking)
2707         {
2708           if (!spu_hash_table (info)->auto_overlay)
2709             {
2710               const char *f1 = func_name (fun);
2711               const char *f2 = func_name (call->fun);
2712
2713               info->callbacks->info (_("Stack analysis will ignore the call "
2714                                        "from %s to %s\n"),
2715                                      f1, f2);
2716             }
2717           *callp = call->next;
2718           free (call);
2719           continue;
2720         }
2721       callp = &call->next;
2722     }
2723   fun->marking = FALSE;
2724   *(unsigned int *) param = max_depth;
2725   return TRUE;
2726 }
2727
2728 /* Populate call_list for each function.  */
2729
2730 static bfd_boolean
2731 build_call_tree (struct bfd_link_info *info)
2732 {
2733   bfd *ibfd;
2734   unsigned int depth;
2735
2736   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
2737     {
2738       extern const bfd_target bfd_elf32_spu_vec;
2739       asection *sec;
2740
2741       if (ibfd->xvec != &bfd_elf32_spu_vec)
2742         continue;
2743
2744       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
2745         if (!mark_functions_via_relocs (sec, info, TRUE))
2746           return FALSE;
2747     }
2748
2749   /* Transfer call info from hot/cold section part of function
2750      to main entry.  */
2751   if (!spu_hash_table (info)->auto_overlay
2752       && !for_each_node (transfer_calls, info, 0, FALSE))
2753     return FALSE;
2754
2755   /* Find the call graph root(s).  */
2756   if (!for_each_node (mark_non_root, info, 0, FALSE))
2757     return FALSE;
2758
2759   /* Remove cycles from the call graph.  We start from the root node(s)
2760      so that we break cycles in a reasonable place.  */
2761   depth = 0;
2762   return for_each_node (remove_cycles, info, &depth, TRUE);
2763 }
2764
2765 /* qsort predicate to sort calls by max_depth then count.  */
2766
2767 static int
2768 sort_calls (const void *a, const void *b)
2769 {
2770   struct call_info *const *c1 = a;
2771   struct call_info *const *c2 = b;
2772   int delta;
2773
2774   delta = (*c2)->max_depth - (*c1)->max_depth;
2775   if (delta != 0)
2776     return delta;
2777
2778   delta = (*c2)->count - (*c1)->count;
2779   if (delta != 0)
2780     return delta;
2781
2782   return c1 - c2;
2783 }
2784
2785 struct _mos_param {
2786   unsigned int max_overlay_size;
2787 };
2788
2789 /* Set linker_mark and gc_mark on any sections that we will put in
2790    overlays.  These flags are used by the generic ELF linker, but we
2791    won't be continuing on to bfd_elf_final_link so it is OK to use
2792    them.  linker_mark is clear before we get here.  Set segment_mark
2793    on sections that are part of a pasted function (excluding the last
2794    section).
2795
2796    Set up function rodata section if --overlay-rodata.  We don't
2797    currently include merged string constant rodata sections since
2798
2799    Sort the call graph so that the deepest nodes will be visited
2800    first.  */
2801
2802 static bfd_boolean
2803 mark_overlay_section (struct function_info *fun,
2804                       struct bfd_link_info *info,
2805                       void *param)
2806 {
2807   struct call_info *call;
2808   unsigned int count;
2809   struct _mos_param *mos_param = param;
2810
2811   if (fun->visit4)
2812     return TRUE;
2813
2814   fun->visit4 = TRUE;
2815   if (!fun->sec->linker_mark)
2816     {
2817       fun->sec->linker_mark = 1;
2818       fun->sec->gc_mark = 1;
2819       fun->sec->segment_mark = 0;
2820       /* Ensure SEC_CODE is set on this text section (it ought to
2821          be!), and SEC_CODE is clear on rodata sections.  We use
2822          this flag to differentiate the two overlay section types.  */
2823       fun->sec->flags |= SEC_CODE;
2824       if (spu_hash_table (info)->auto_overlay & OVERLAY_RODATA)
2825         {
2826           char *name = NULL;
2827           unsigned int size;
2828
2829           /* Find the rodata section corresponding to this function's
2830              text section.  */
2831           if (strcmp (fun->sec->name, ".text") == 0)
2832             {
2833               name = bfd_malloc (sizeof (".rodata"));
2834               if (name == NULL)
2835                 return FALSE;
2836               memcpy (name, ".rodata", sizeof (".rodata"));
2837             }
2838           else if (strncmp (fun->sec->name, ".text.", 6) == 0)
2839             {
2840               size_t len = strlen (fun->sec->name);
2841               name = bfd_malloc (len + 3);
2842               if (name == NULL)
2843                 return FALSE;
2844               memcpy (name, ".rodata", sizeof (".rodata"));
2845               memcpy (name + 7, fun->sec->name + 5, len - 4);
2846             }
2847           else if (strncmp (fun->sec->name, ".gnu.linkonce.t.", 16) == 0)
2848             {
2849               size_t len = strlen (fun->sec->name) + 1;
2850               name = bfd_malloc (len);
2851               if (name == NULL)
2852                 return FALSE;
2853               memcpy (name, fun->sec->name, len);
2854               name[14] = 'r';
2855             }
2856
2857           if (name != NULL)
2858             {
2859               asection *rodata = NULL;
2860               asection *group_sec = elf_section_data (fun->sec)->next_in_group;
2861               if (group_sec == NULL)
2862                 rodata = bfd_get_section_by_name (fun->sec->owner, name);
2863               else
2864                 while (group_sec != NULL && group_sec != fun->sec)
2865                   {
2866                     if (strcmp (group_sec->name, name) == 0)
2867                       {
2868                         rodata = group_sec;
2869                         break;
2870                       }
2871                     group_sec = elf_section_data (group_sec)->next_in_group;
2872                   }
2873               fun->rodata = rodata;
2874               if (fun->rodata)
2875                 {
2876                   fun->rodata->linker_mark = 1;
2877                   fun->rodata->gc_mark = 1;
2878                   fun->rodata->flags &= ~SEC_CODE;
2879                 }
2880               free (name);
2881             }
2882           size = fun->sec->size;
2883           if (fun->rodata)
2884             size += fun->rodata->size;
2885           if (mos_param->max_overlay_size < size)
2886             mos_param->max_overlay_size = size;
2887         }
2888     }
2889
2890   for (count = 0, call = fun->call_list; call != NULL; call = call->next)
2891     count += 1;
2892
2893   if (count > 1)
2894     {
2895       struct call_info **calls = bfd_malloc (count * sizeof (*calls));
2896       if (calls == NULL)
2897         return FALSE;
2898
2899       for (count = 0, call = fun->call_list; call != NULL; call = call->next)
2900         calls[count++] = call;
2901
2902       qsort (calls, count, sizeof (*calls), sort_calls);
2903
2904       fun->call_list = NULL;
2905       while (count != 0)
2906         {
2907           --count;
2908           calls[count]->next = fun->call_list;
2909           fun->call_list = calls[count];
2910         }
2911       free (calls);
2912     }
2913
2914   for (call = fun->call_list; call != NULL; call = call->next)
2915     {
2916       if (call->is_pasted)
2917         {
2918           /* There can only be one is_pasted call per function_info.  */
2919           BFD_ASSERT (!fun->sec->segment_mark);
2920           fun->sec->segment_mark = 1;
2921         }
2922       if (!mark_overlay_section (call->fun, info, param))
2923         return FALSE;
2924     }
2925
2926   /* Don't put entry code into an overlay.  The overlay manager needs
2927      a stack!  */
2928   if (fun->lo + fun->sec->output_offset + fun->sec->output_section->vma
2929       == info->output_bfd->start_address)
2930     {
2931       fun->sec->linker_mark = 0;
2932       if (fun->rodata != NULL)
2933         fun->rodata->linker_mark = 0;
2934     }
2935   return TRUE;
2936 }
2937
2938 struct _uos_param {
2939   asection *exclude_input_section;
2940   asection *exclude_output_section;
2941   unsigned long clearing;
2942 };
2943
2944 /* Undo some of mark_overlay_section's work.  */
2945
2946 static bfd_boolean
2947 unmark_overlay_section (struct function_info *fun,
2948                         struct bfd_link_info *info,
2949                         void *param)
2950 {
2951   struct call_info *call;
2952   struct _uos_param *uos_param = param;
2953   unsigned int excluded = 0;
2954
2955   if (fun->visit5)
2956     return TRUE;
2957
2958   fun->visit5 = TRUE;
2959
2960   excluded = 0;
2961   if (fun->sec == uos_param->exclude_input_section
2962       || fun->sec->output_section == uos_param->exclude_output_section)
2963     excluded = 1;
2964
2965   uos_param->clearing += excluded;
2966
2967   if (uos_param->clearing)
2968     {
2969       fun->sec->linker_mark = 0;
2970       if (fun->rodata)
2971         fun->rodata->linker_mark = 0;
2972     }
2973
2974   for (call = fun->call_list; call != NULL; call = call->next)
2975     if (!unmark_overlay_section (call->fun, info, param))
2976       return FALSE;
2977
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 - 1]->filename,
3564                                           bfd_arr[i - 1]->my_archive->filename);
3565                 else
3566                   info->callbacks->einfo (_("%s in both %s and %s\n"),
3567                                           bfd_arr[i - 1]->filename,
3568                                           bfd_arr[i - 1]->my_archive->filename,
3569                                           bfd_arr[i]->my_archive->filename);
3570               }
3571             else if (bfd_arr[i - 1]->my_archive)
3572               info->callbacks->einfo (_("%s in %s and as an object\n"),
3573                                       bfd_arr[i - 1]->filename,
3574                                       bfd_arr[i - 1]->my_archive->filename);
3575             else if (bfd_arr[i]->my_archive)
3576               info->callbacks->einfo (_("%s in %s and as an object\n"),
3577                                       bfd_arr[i]->filename,
3578                                       bfd_arr[i]->my_archive->filename);
3579             else
3580               info->callbacks->einfo (_("%s duplicated\n"),
3581                                       bfd_arr[i]->filename);
3582             ok = FALSE;
3583           }
3584       if (!ok)
3585         {
3586           /* FIXME: modify plain object files from foo.o to ./foo.o
3587              and emit EXCLUDE_FILE to handle the duplicates in
3588              archives.  There is a pathological case we can't handle:
3589              We may have duplicate file names within a single archive.  */
3590           info->callbacks->einfo (_("sorry, no support for duplicate "
3591                                     "object files in auto-overlay script\n"));
3592           bfd_set_error (bfd_error_bad_value);
3593           goto err_exit;
3594         }
3595     }
3596   free (bfd_arr);
3597
3598   if (htab->reserved == 0)
3599     {
3600       struct _sum_stack_param sum_stack_param;
3601
3602       sum_stack_param.emit_stack_syms = 0;
3603       sum_stack_param.overall_stack = 0;
3604       if (!for_each_node (sum_stack, info, &sum_stack_param, TRUE))
3605         goto err_exit;
3606       htab->reserved = sum_stack_param.overall_stack;
3607     }
3608   fixed_size += htab->reserved;
3609   fixed_size += htab->non_ovly_stub * OVL_STUB_SIZE;
3610   if (fixed_size + mos_param.max_overlay_size <= htab->local_store)
3611     {
3612       /* Guess number of overlays.  Assuming overlay buffer is on
3613          average only half full should be conservative.  */
3614       ovlynum = total_overlay_size * 2 / (htab->local_store - fixed_size);
3615       /* Space for _ovly_table[], _ovly_buf_table[] and toe.  */
3616       fixed_size += ovlynum * 16 + 16 + 4 + 16;
3617     }
3618
3619   if (fixed_size + mos_param.max_overlay_size > htab->local_store)
3620     info->callbacks->einfo (_("non-overlay plus maximum overlay size "
3621                               "of 0x%x exceeds local store\n"),
3622                             fixed_size + mos_param.max_overlay_size);
3623
3624   /* Now see if we should put some functions in the non-overlay area.  */
3625   if (fixed_size < htab->overlay_fixed
3626       && htab->overlay_fixed + mos_param.max_overlay_size < htab->local_store)
3627     {
3628       unsigned int lib_size = htab->overlay_fixed - fixed_size;
3629       lib_size = auto_ovl_lib_functions (info, lib_size);
3630       if (lib_size == (unsigned int) -1)
3631         goto err_exit;
3632       fixed_size = htab->overlay_fixed - lib_size;
3633     }
3634
3635   /* Build an array of sections, suitably sorted to place into
3636      overlays.  */
3637   ovly_sections = bfd_malloc (2 * count * sizeof (*ovly_sections));
3638   if (ovly_sections == NULL)
3639     goto err_exit;
3640   ovly_p = ovly_sections;
3641   if (!for_each_node (collect_overlays, info, &ovly_p, TRUE))
3642     goto err_exit;
3643   count = (size_t) (ovly_p - ovly_sections) / 2;
3644
3645   script = htab->spu_elf_open_overlay_script ();
3646
3647   if (fprintf (script, "SECTIONS\n{\n OVERLAY :\n {\n") <= 0)
3648     goto file_err;
3649
3650   memset (&dummy_caller, 0, sizeof (dummy_caller));
3651   overlay_size = htab->local_store - fixed_size;
3652   base = 0;
3653   ovlynum = 0;
3654   while (base < count)
3655     {
3656       unsigned int size = 0;
3657       unsigned int j;
3658
3659       for (i = base; i < count; i++)
3660         {
3661           asection *sec;
3662           unsigned int tmp;
3663           unsigned int stub_size;
3664           struct call_info *call, *pasty;
3665           struct _spu_elf_section_data *sec_data;
3666           struct spu_elf_stack_info *sinfo;
3667           int k;
3668
3669           /* See whether we can add this section to the current
3670              overlay without overflowing our overlay buffer.  */
3671           sec = ovly_sections[2 * i];
3672           tmp = size + sec->size;
3673           if (ovly_sections[2 * i + 1])
3674             tmp += ovly_sections[2 * i + 1]->size;
3675           if (tmp > overlay_size)
3676             break;
3677           if (sec->segment_mark)
3678             {
3679               /* Pasted sections must stay together, so add their
3680                  sizes too.  */
3681               struct call_info *pasty = find_pasted_call (sec);
3682               while (pasty != NULL)
3683                 {
3684                   struct function_info *call_fun = pasty->fun;
3685                   tmp += call_fun->sec->size;
3686                   if (call_fun->rodata)
3687                     tmp += call_fun->rodata->size;
3688                   for (pasty = call_fun->call_list; pasty; pasty = pasty->next)
3689                     if (pasty->is_pasted)
3690                       break;
3691                 }
3692             }
3693           if (tmp > overlay_size)
3694             break;
3695
3696           /* If we add this section, we might need new overlay call
3697              stubs.  Add any overlay section calls to dummy_call.  */
3698           pasty = NULL;
3699           sec_data = spu_elf_section_data (sec);
3700           sinfo = sec_data->u.i.stack_info;
3701           for (k = 0; k < sinfo->num_fun; ++k)
3702             for (call = sinfo->fun[k].call_list; call; call = call->next)
3703               if (call->is_pasted)
3704                 {
3705                   BFD_ASSERT (pasty == NULL);
3706                   pasty = call;
3707                 }
3708               else if (call->fun->sec->linker_mark)
3709                 {
3710                   if (!copy_callee (&dummy_caller, call))
3711                     goto err_exit;
3712                 }
3713           while (pasty != NULL)
3714             {
3715               struct function_info *call_fun = pasty->fun;
3716               pasty = NULL;
3717               for (call = call_fun->call_list; call; call = call->next)
3718                 if (call->is_pasted)
3719                   {
3720                     BFD_ASSERT (pasty == NULL);
3721                     pasty = call;
3722                   }
3723                 else if (!copy_callee (&dummy_caller, call))
3724                   goto err_exit;
3725             }
3726
3727           /* Calculate call stub size.  */
3728           stub_size = 0;
3729           for (call = dummy_caller.call_list; call; call = call->next)
3730             {
3731               unsigned int k;
3732
3733               stub_size += OVL_STUB_SIZE;
3734               /* If the call is within this overlay, we won't need a
3735                  stub.  */
3736               for (k = base; k < i + 1; k++)
3737                 if (call->fun->sec == ovly_sections[2 * k])
3738                   {
3739                     stub_size -= OVL_STUB_SIZE;
3740                     break;
3741                   }
3742             }
3743           if (tmp + stub_size > overlay_size)
3744             break;
3745
3746           size = tmp;
3747         }
3748
3749       if (i == base)
3750         {
3751           info->callbacks->einfo (_("%B:%A%s exceeds overlay size\n"),
3752                                   ovly_sections[2 * i]->owner,
3753                                   ovly_sections[2 * i],
3754                                   ovly_sections[2 * i + 1] ? " + rodata" : "");
3755           bfd_set_error (bfd_error_bad_value);
3756           goto err_exit;
3757         }
3758
3759       if (fprintf (script, "  .ovly%d {\n", ++ovlynum) <= 0)
3760         goto file_err;
3761       for (j = base; j < i; j++)
3762         {
3763           asection *sec = ovly_sections[2 * j];
3764
3765           if (fprintf (script, "   [%c]%s (%s)\n",
3766                        sec->owner->filename[0],
3767                        sec->owner->filename + 1,
3768                        sec->name) <= 0)
3769             goto file_err;
3770           if (sec->segment_mark)
3771             {
3772               struct call_info *call = find_pasted_call (sec);
3773               while (call != NULL)
3774                 {
3775                   struct function_info *call_fun = call->fun;
3776                   sec = call_fun->sec;
3777                   if (fprintf (script, "   [%c]%s (%s)\n",
3778                                sec->owner->filename[0],
3779                                sec->owner->filename + 1,
3780                                sec->name) <= 0)
3781                     goto file_err;
3782                   for (call = call_fun->call_list; call; call = call->next)
3783                     if (call->is_pasted)
3784                       break;
3785                 }
3786             }
3787         }
3788
3789       for (j = base; j < i; j++)
3790         {
3791           asection *sec = ovly_sections[2 * j + 1];
3792           if (sec != NULL && fprintf (script, "   [%c]%s (%s)\n",
3793                                       sec->owner->filename[0],
3794                                       sec->owner->filename + 1,
3795                                       sec->name) <= 0)
3796             goto file_err;
3797
3798           sec = ovly_sections[2 * j];
3799           if (sec->segment_mark)
3800             {
3801               struct call_info *call = find_pasted_call (sec);
3802               while (call != NULL)
3803                 {
3804                   struct function_info *call_fun = call->fun;
3805                   sec = call_fun->rodata;
3806                   if (sec != NULL && fprintf (script, "   [%c]%s (%s)\n",
3807                                               sec->owner->filename[0],
3808                                               sec->owner->filename + 1,
3809                                               sec->name) <= 0)
3810                     goto file_err;
3811                   for (call = call_fun->call_list; call; call = call->next)
3812                     if (call->is_pasted)
3813                       break;
3814                 }
3815             }
3816         }
3817
3818       if (fprintf (script, "  }\n") <= 0)
3819         goto file_err;
3820
3821       while (dummy_caller.call_list != NULL)
3822         {
3823           struct call_info *call = dummy_caller.call_list;
3824           dummy_caller.call_list = call->next;
3825           free (call);
3826         }
3827
3828       base = i;
3829     }
3830   free (ovly_sections);
3831
3832   if (fprintf (script, " }\n}\nINSERT AFTER .text;\n") <= 0)
3833     goto file_err;
3834   if (fclose (script) != 0)
3835     goto file_err;
3836
3837   if (htab->auto_overlay & AUTO_RELINK)
3838     htab->spu_elf_relink ();
3839
3840   xexit (0);
3841
3842  file_err:
3843   bfd_set_error (bfd_error_system_call);
3844  err_exit:
3845   info->callbacks->einfo ("%F%P: auto overlay error: %E\n");
3846   xexit (1);
3847 }
3848
3849 /* Provide an estimate of total stack required.  */
3850
3851 static bfd_boolean
3852 spu_elf_stack_analysis (struct bfd_link_info *info, int emit_stack_syms)
3853 {
3854   struct _sum_stack_param sum_stack_param;
3855
3856   if (!discover_functions (info))
3857     return FALSE;
3858
3859   if (!build_call_tree (info))
3860     return FALSE;
3861
3862   info->callbacks->info (_("Stack size for call graph root nodes.\n"));
3863   info->callbacks->minfo (_("\nStack size for functions.  "
3864                             "Annotations: '*' max stack, 't' tail call\n"));
3865
3866   sum_stack_param.emit_stack_syms = emit_stack_syms;
3867   sum_stack_param.overall_stack = 0;
3868   if (!for_each_node (sum_stack, info, &sum_stack_param, TRUE))
3869     return FALSE;
3870
3871   info->callbacks->info (_("Maximum stack required is 0x%v\n"),
3872                          (bfd_vma) sum_stack_param.overall_stack);
3873   return TRUE;
3874 }
3875
3876 /* Perform a final link.  */
3877
3878 static bfd_boolean
3879 spu_elf_final_link (bfd *output_bfd, struct bfd_link_info *info)
3880 {
3881   struct spu_link_hash_table *htab = spu_hash_table (info);
3882
3883   if (htab->auto_overlay)
3884     spu_elf_auto_overlay (info, htab->spu_elf_load_ovl_mgr);
3885
3886   if (htab->stack_analysis
3887       && !spu_elf_stack_analysis (info, htab->emit_stack_syms))
3888     info->callbacks->einfo ("%X%P: stack analysis error: %E\n");
3889
3890   return bfd_elf_final_link (output_bfd, info);
3891 }
3892
3893 /* Called when not normally emitting relocs, ie. !info->relocatable
3894    and !info->emitrelocations.  Returns a count of special relocs
3895    that need to be emitted.  */
3896
3897 static unsigned int
3898 spu_elf_count_relocs (asection *sec, Elf_Internal_Rela *relocs)
3899 {
3900   unsigned int count = 0;
3901   Elf_Internal_Rela *relend = relocs + sec->reloc_count;
3902
3903   for (; relocs < relend; relocs++)
3904     {
3905       int r_type = ELF32_R_TYPE (relocs->r_info);
3906       if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
3907         ++count;
3908     }
3909
3910   return count;
3911 }
3912
3913 /* Apply RELOCS to CONTENTS of INPUT_SECTION from INPUT_BFD.  */
3914
3915 static int
3916 spu_elf_relocate_section (bfd *output_bfd,
3917                           struct bfd_link_info *info,
3918                           bfd *input_bfd,
3919                           asection *input_section,
3920                           bfd_byte *contents,
3921                           Elf_Internal_Rela *relocs,
3922                           Elf_Internal_Sym *local_syms,
3923                           asection **local_sections)
3924 {
3925   Elf_Internal_Shdr *symtab_hdr;
3926   struct elf_link_hash_entry **sym_hashes;
3927   Elf_Internal_Rela *rel, *relend;
3928   struct spu_link_hash_table *htab;
3929   asection *ea = bfd_get_section_by_name (output_bfd, "._ea");
3930   int ret = TRUE;
3931   bfd_boolean emit_these_relocs = FALSE;
3932   bfd_boolean is_ea_sym;
3933   bfd_boolean stubs;
3934
3935   htab = spu_hash_table (info);
3936   stubs = (htab->stub_sec != NULL
3937            && maybe_needs_stubs (input_section, output_bfd));
3938   symtab_hdr = &elf_tdata (input_bfd)->symtab_hdr;
3939   sym_hashes = (struct elf_link_hash_entry **) (elf_sym_hashes (input_bfd));
3940
3941   rel = relocs;
3942   relend = relocs + input_section->reloc_count;
3943   for (; rel < relend; rel++)
3944     {
3945       int r_type;
3946       reloc_howto_type *howto;
3947       unsigned int r_symndx;
3948       Elf_Internal_Sym *sym;
3949       asection *sec;
3950       struct elf_link_hash_entry *h;
3951       const char *sym_name;
3952       bfd_vma relocation;
3953       bfd_vma addend;
3954       bfd_reloc_status_type r;
3955       bfd_boolean unresolved_reloc;
3956       bfd_boolean warned;
3957       enum _stub_type stub_type;
3958
3959       r_symndx = ELF32_R_SYM (rel->r_info);
3960       r_type = ELF32_R_TYPE (rel->r_info);
3961       howto = elf_howto_table + r_type;
3962       unresolved_reloc = FALSE;
3963       warned = FALSE;
3964       h = NULL;
3965       sym = NULL;
3966       sec = NULL;
3967       if (r_symndx < symtab_hdr->sh_info)
3968         {
3969           sym = local_syms + r_symndx;
3970           sec = local_sections[r_symndx];
3971           sym_name = bfd_elf_sym_name (input_bfd, symtab_hdr, sym, sec);
3972           relocation = _bfd_elf_rela_local_sym (output_bfd, sym, &sec, rel);
3973         }
3974       else
3975         {
3976           RELOC_FOR_GLOBAL_SYMBOL (info, input_bfd, input_section, rel,
3977                                    r_symndx, symtab_hdr, sym_hashes,
3978                                    h, sec, relocation,
3979                                    unresolved_reloc, warned);
3980           sym_name = h->root.root.string;
3981         }
3982
3983       if (sec != NULL && elf_discarded_section (sec))
3984         {
3985           /* For relocs against symbols from removed linkonce sections,
3986              or sections discarded by a linker script, we just want the
3987              section contents zeroed.  Avoid any special processing.  */
3988           _bfd_clear_contents (howto, input_bfd, contents + rel->r_offset);
3989           rel->r_info = 0;
3990           rel->r_addend = 0;
3991           continue;
3992         }
3993
3994       if (info->relocatable)
3995         continue;
3996
3997       is_ea_sym = (ea != NULL
3998                    && sec != NULL
3999                    && sec->output_section == ea);
4000
4001       if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4002         {
4003           if (is_ea_sym)
4004             {
4005               /* ._ea is a special section that isn't allocated in SPU
4006                  memory, but rather occupies space in PPU memory as
4007                  part of an embedded ELF image.  If this reloc is
4008                  against a symbol defined in ._ea, then transform the
4009                  reloc into an equivalent one without a symbol
4010                  relative to the start of the ELF image.  */
4011               rel->r_addend += (relocation
4012                                 - ea->vma
4013                                 + elf_section_data (ea)->this_hdr.sh_offset);
4014               rel->r_info = ELF32_R_INFO (0, r_type);
4015             }
4016           emit_these_relocs = TRUE;
4017           continue;
4018         }
4019
4020       if (is_ea_sym)
4021         unresolved_reloc = TRUE;
4022
4023       if (unresolved_reloc)
4024         {
4025           (*_bfd_error_handler)
4026             (_("%B(%s+0x%lx): unresolvable %s relocation against symbol `%s'"),
4027              input_bfd,
4028              bfd_get_section_name (input_bfd, input_section),
4029              (long) rel->r_offset,
4030              howto->name,
4031              sym_name);
4032           ret = FALSE;
4033         }
4034
4035       /* If this symbol is in an overlay area, we may need to relocate
4036          to the overlay stub.  */
4037       addend = rel->r_addend;
4038       if (stubs
4039           && (stub_type = needs_ovl_stub (h, sym, sec, input_section, rel,
4040                                           contents, info)) != no_stub)
4041         {
4042           unsigned int ovl = 0;
4043           struct got_entry *g, **head;
4044
4045           if (stub_type != nonovl_stub)
4046             ovl = (spu_elf_section_data (input_section->output_section)
4047                    ->u.o.ovl_index);
4048
4049           if (h != NULL)
4050             head = &h->got.glist;
4051           else
4052             head = elf_local_got_ents (input_bfd) + r_symndx;
4053
4054           for (g = *head; g != NULL; g = g->next)
4055             if (g->addend == addend && (g->ovl == ovl || g->ovl == 0))
4056               break;
4057           if (g == NULL)
4058             abort ();
4059
4060           relocation = g->stub_addr;
4061           addend = 0;
4062         }
4063
4064       r = _bfd_final_link_relocate (howto,
4065                                     input_bfd,
4066                                     input_section,
4067                                     contents,
4068                                     rel->r_offset, relocation, addend);
4069
4070       if (r != bfd_reloc_ok)
4071         {
4072           const char *msg = (const char *) 0;
4073
4074           switch (r)
4075             {
4076             case bfd_reloc_overflow:
4077               if (!((*info->callbacks->reloc_overflow)
4078                     (info, (h ? &h->root : NULL), sym_name, howto->name,
4079                      (bfd_vma) 0, input_bfd, input_section, rel->r_offset)))
4080                 return FALSE;
4081               break;
4082
4083             case bfd_reloc_undefined:
4084               if (!((*info->callbacks->undefined_symbol)
4085                     (info, sym_name, input_bfd, input_section,
4086                      rel->r_offset, TRUE)))
4087                 return FALSE;
4088               break;
4089
4090             case bfd_reloc_outofrange:
4091               msg = _("internal error: out of range error");
4092               goto common_error;
4093
4094             case bfd_reloc_notsupported:
4095               msg = _("internal error: unsupported relocation error");
4096               goto common_error;
4097
4098             case bfd_reloc_dangerous:
4099               msg = _("internal error: dangerous error");
4100               goto common_error;
4101
4102             default:
4103               msg = _("internal error: unknown error");
4104               /* fall through */
4105
4106             common_error:
4107               ret = FALSE;
4108               if (!((*info->callbacks->warning)
4109                     (info, msg, sym_name, input_bfd, input_section,
4110                      rel->r_offset)))
4111                 return FALSE;
4112               break;
4113             }
4114         }
4115     }
4116
4117   if (ret
4118       && emit_these_relocs
4119       && !info->emitrelocations)
4120     {
4121       Elf_Internal_Rela *wrel;
4122       Elf_Internal_Shdr *rel_hdr;
4123
4124       wrel = rel = relocs;
4125       relend = relocs + input_section->reloc_count;
4126       for (; rel < relend; rel++)
4127         {
4128           int r_type;
4129
4130           r_type = ELF32_R_TYPE (rel->r_info);
4131           if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4132             *wrel++ = *rel;
4133         }
4134       input_section->reloc_count = wrel - relocs;
4135       /* Backflips for _bfd_elf_link_output_relocs.  */
4136       rel_hdr = &elf_section_data (input_section)->rel_hdr;
4137       rel_hdr->sh_size = input_section->reloc_count * rel_hdr->sh_entsize;
4138       ret = 2;
4139     }
4140
4141   return ret;
4142 }
4143
4144 /* Adjust _SPUEAR_ syms to point at their overlay stubs.  */
4145
4146 static bfd_boolean
4147 spu_elf_output_symbol_hook (struct bfd_link_info *info,
4148                             const char *sym_name ATTRIBUTE_UNUSED,
4149                             Elf_Internal_Sym *sym,
4150                             asection *sym_sec ATTRIBUTE_UNUSED,
4151                             struct elf_link_hash_entry *h)
4152 {
4153   struct spu_link_hash_table *htab = spu_hash_table (info);
4154
4155   if (!info->relocatable
4156       && htab->stub_sec != NULL
4157       && h != NULL
4158       && (h->root.type == bfd_link_hash_defined
4159           || h->root.type == bfd_link_hash_defweak)
4160       && h->def_regular
4161       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0)
4162     {
4163       struct got_entry *g;
4164
4165       for (g = h->got.glist; g != NULL; g = g->next)
4166         if (g->addend == 0 && g->ovl == 0)
4167           {
4168             sym->st_shndx = (_bfd_elf_section_from_bfd_section
4169                              (htab->stub_sec[0]->output_section->owner,
4170                               htab->stub_sec[0]->output_section));
4171             sym->st_value = g->stub_addr;
4172             break;
4173           }
4174     }
4175
4176   return TRUE;
4177 }
4178
4179 static int spu_plugin = 0;
4180
4181 void
4182 spu_elf_plugin (int val)
4183 {
4184   spu_plugin = val;
4185 }
4186
4187 /* Set ELF header e_type for plugins.  */
4188
4189 static void
4190 spu_elf_post_process_headers (bfd *abfd,
4191                               struct bfd_link_info *info ATTRIBUTE_UNUSED)
4192 {
4193   if (spu_plugin)
4194     {
4195       Elf_Internal_Ehdr *i_ehdrp = elf_elfheader (abfd);
4196
4197       i_ehdrp->e_type = ET_DYN;
4198     }
4199 }
4200
4201 /* We may add an extra PT_LOAD segment for .toe.  We also need extra
4202    segments for overlays.  */
4203
4204 static int
4205 spu_elf_additional_program_headers (bfd *abfd, struct bfd_link_info *info)
4206 {
4207   struct spu_link_hash_table *htab = spu_hash_table (info);
4208   int extra = htab->num_overlays;
4209   asection *sec;
4210
4211   if (extra)
4212     ++extra;
4213
4214   sec = bfd_get_section_by_name (abfd, ".toe");
4215   if (sec != NULL && (sec->flags & SEC_LOAD) != 0)
4216     ++extra;
4217
4218   return extra;
4219 }
4220
4221 /* Remove .toe section from other PT_LOAD segments and put it in
4222    a segment of its own.  Put overlays in separate segments too.  */
4223
4224 static bfd_boolean
4225 spu_elf_modify_segment_map (bfd *abfd, struct bfd_link_info *info)
4226 {
4227   asection *toe, *s;
4228   struct elf_segment_map *m;
4229   unsigned int i;
4230
4231   if (info == NULL)
4232     return TRUE;
4233
4234   toe = bfd_get_section_by_name (abfd, ".toe");
4235   for (m = elf_tdata (abfd)->segment_map; m != NULL; m = m->next)
4236     if (m->p_type == PT_LOAD && m->count > 1)
4237       for (i = 0; i < m->count; i++)
4238         if ((s = m->sections[i]) == toe
4239             || spu_elf_section_data (s)->u.o.ovl_index != 0)
4240           {
4241             struct elf_segment_map *m2;
4242             bfd_vma amt;
4243
4244             if (i + 1 < m->count)
4245               {
4246                 amt = sizeof (struct elf_segment_map);
4247                 amt += (m->count - (i + 2)) * sizeof (m->sections[0]);
4248                 m2 = bfd_zalloc (abfd, amt);
4249                 if (m2 == NULL)
4250                   return FALSE;
4251                 m2->count = m->count - (i + 1);
4252                 memcpy (m2->sections, m->sections + i + 1,
4253                         m2->count * sizeof (m->sections[0]));
4254                 m2->p_type = PT_LOAD;
4255                 m2->next = m->next;
4256                 m->next = m2;
4257               }
4258             m->count = 1;
4259             if (i != 0)
4260               {
4261                 m->count = i;
4262                 amt = sizeof (struct elf_segment_map);
4263                 m2 = bfd_zalloc (abfd, amt);
4264                 if (m2 == NULL)
4265                   return FALSE;
4266                 m2->p_type = PT_LOAD;
4267                 m2->count = 1;
4268                 m2->sections[0] = s;
4269                 m2->next = m->next;
4270                 m->next = m2;
4271               }
4272             break;
4273           }
4274
4275   return TRUE;
4276 }
4277
4278 /* Tweak the section type of .note.spu_name.  */
4279
4280 static bfd_boolean
4281 spu_elf_fake_sections (bfd *obfd ATTRIBUTE_UNUSED,
4282                        Elf_Internal_Shdr *hdr,
4283                        asection *sec)
4284 {
4285   if (strcmp (sec->name, SPU_PTNOTE_SPUNAME) == 0)
4286     hdr->sh_type = SHT_NOTE;
4287   return TRUE;
4288 }
4289
4290 /* Tweak phdrs before writing them out.  */
4291
4292 static int
4293 spu_elf_modify_program_headers (bfd *abfd, struct bfd_link_info *info)
4294 {
4295   const struct elf_backend_data *bed;
4296   struct elf_obj_tdata *tdata;
4297   Elf_Internal_Phdr *phdr, *last;
4298   struct spu_link_hash_table *htab;
4299   unsigned int count;
4300   unsigned int i;
4301
4302   if (info == NULL)
4303     return TRUE;
4304
4305   bed = get_elf_backend_data (abfd);
4306   tdata = elf_tdata (abfd);
4307   phdr = tdata->phdr;
4308   count = tdata->program_header_size / bed->s->sizeof_phdr;
4309   htab = spu_hash_table (info);
4310   if (htab->num_overlays != 0)
4311     {
4312       struct elf_segment_map *m;
4313       unsigned int o;
4314
4315       for (i = 0, m = elf_tdata (abfd)->segment_map; m; ++i, m = m->next)
4316         if (m->count != 0
4317             && (o = spu_elf_section_data (m->sections[0])->u.o.ovl_index) != 0)
4318           {
4319             /* Mark this as an overlay header.  */
4320             phdr[i].p_flags |= PF_OVERLAY;
4321
4322             if (htab->ovtab != NULL && htab->ovtab->size != 0)
4323               {
4324                 bfd_byte *p = htab->ovtab->contents;
4325                 unsigned int off = o * 16 + 8;
4326
4327                 /* Write file_off into _ovly_table.  */
4328                 bfd_put_32 (htab->ovtab->owner, phdr[i].p_offset, p + off);
4329               }
4330           }
4331     }
4332
4333   /* Round up p_filesz and p_memsz of PT_LOAD segments to multiples
4334      of 16.  This should always be possible when using the standard
4335      linker scripts, but don't create overlapping segments if
4336      someone is playing games with linker scripts.  */
4337   last = NULL;
4338   for (i = count; i-- != 0; )
4339     if (phdr[i].p_type == PT_LOAD)
4340       {
4341         unsigned adjust;
4342
4343         adjust = -phdr[i].p_filesz & 15;
4344         if (adjust != 0
4345             && last != NULL
4346             && phdr[i].p_offset + phdr[i].p_filesz > last->p_offset - adjust)
4347           break;
4348
4349         adjust = -phdr[i].p_memsz & 15;
4350         if (adjust != 0
4351             && last != NULL
4352             && phdr[i].p_filesz != 0
4353             && phdr[i].p_vaddr + phdr[i].p_memsz > last->p_vaddr - adjust
4354             && phdr[i].p_vaddr + phdr[i].p_memsz <= last->p_vaddr)
4355           break;
4356
4357         if (phdr[i].p_filesz != 0)
4358           last = &phdr[i];
4359       }
4360
4361   if (i == (unsigned int) -1)
4362     for (i = count; i-- != 0; )
4363       if (phdr[i].p_type == PT_LOAD)
4364         {
4365         unsigned adjust;
4366
4367         adjust = -phdr[i].p_filesz & 15;
4368         phdr[i].p_filesz += adjust;
4369
4370         adjust = -phdr[i].p_memsz & 15;
4371         phdr[i].p_memsz += adjust;
4372       }
4373
4374   return TRUE;
4375 }
4376
4377 #define TARGET_BIG_SYM          bfd_elf32_spu_vec
4378 #define TARGET_BIG_NAME         "elf32-spu"
4379 #define ELF_ARCH                bfd_arch_spu
4380 #define ELF_MACHINE_CODE        EM_SPU
4381 /* This matches the alignment need for DMA.  */
4382 #define ELF_MAXPAGESIZE         0x80
4383 #define elf_backend_rela_normal         1
4384 #define elf_backend_can_gc_sections     1
4385
4386 #define bfd_elf32_bfd_reloc_type_lookup         spu_elf_reloc_type_lookup
4387 #define bfd_elf32_bfd_reloc_name_lookup spu_elf_reloc_name_lookup
4388 #define elf_info_to_howto                       spu_elf_info_to_howto
4389 #define elf_backend_count_relocs                spu_elf_count_relocs
4390 #define elf_backend_relocate_section            spu_elf_relocate_section
4391 #define elf_backend_symbol_processing           spu_elf_backend_symbol_processing
4392 #define elf_backend_link_output_symbol_hook     spu_elf_output_symbol_hook
4393 #define elf_backend_object_p                    spu_elf_object_p
4394 #define bfd_elf32_new_section_hook              spu_elf_new_section_hook
4395 #define bfd_elf32_bfd_link_hash_table_create    spu_elf_link_hash_table_create
4396
4397 #define elf_backend_additional_program_headers  spu_elf_additional_program_headers
4398 #define elf_backend_modify_segment_map          spu_elf_modify_segment_map
4399 #define elf_backend_modify_program_headers      spu_elf_modify_program_headers
4400 #define elf_backend_post_process_headers        spu_elf_post_process_headers
4401 #define elf_backend_fake_sections               spu_elf_fake_sections
4402 #define elf_backend_special_sections            spu_elf_special_sections
4403 #define bfd_elf32_bfd_final_link                spu_elf_final_link
4404
4405 #include "elf32-target.h"