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