bfd/elf32-spu.c

   1 /* SPU specific support for 32-bit ELF
   2
   3    Copyright (C) 2006-2014 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   HOWTO (R_SPU_ADD_PIC,      0, 0, 0, FALSE,  0, complain_overflow_dont,
  92          bfd_elf_generic_reloc, "SPU_ADD_PIC",
  93          FALSE, 0, 0x00000000, FALSE),
  94 };
  95
  96 static struct bfd_elf_special_section const spu_elf_special_sections[] = {
  97   { "._ea", 4, 0, SHT_PROGBITS, SHF_WRITE },
  98   { ".toe", 4, 0, SHT_NOBITS, SHF_ALLOC },
  99   { NULL, 0, 0, 0, 0 }
 100 };
 101
 102 static enum elf_spu_reloc_type
 103 spu_elf_bfd_to_reloc_type (bfd_reloc_code_real_type code)
 104 {
 105   switch (code)
 106     {
 107     default:
 108       return R_SPU_NONE;
 109     case BFD_RELOC_SPU_IMM10W:
 110       return R_SPU_ADDR10;
 111     case BFD_RELOC_SPU_IMM16W:
 112       return R_SPU_ADDR16;
 113     case BFD_RELOC_SPU_LO16:
 114       return R_SPU_ADDR16_LO;
 115     case BFD_RELOC_SPU_HI16:
 116       return R_SPU_ADDR16_HI;
 117     case BFD_RELOC_SPU_IMM18:
 118       return R_SPU_ADDR18;
 119     case BFD_RELOC_SPU_PCREL16:
 120       return R_SPU_REL16;
 121     case BFD_RELOC_SPU_IMM7:
 122       return R_SPU_ADDR7;
 123     case BFD_RELOC_SPU_IMM8:
 124       return R_SPU_NONE;
 125     case BFD_RELOC_SPU_PCREL9a:
 126       return R_SPU_REL9;
 127     case BFD_RELOC_SPU_PCREL9b:
 128       return R_SPU_REL9I;
 129     case BFD_RELOC_SPU_IMM10:
 130       return R_SPU_ADDR10I;
 131     case BFD_RELOC_SPU_IMM16:
 132       return R_SPU_ADDR16I;
 133     case BFD_RELOC_32:
 134       return R_SPU_ADDR32;
 135     case BFD_RELOC_32_PCREL:
 136       return R_SPU_REL32;
 137     case BFD_RELOC_SPU_PPU32:
 138       return R_SPU_PPU32;
 139     case BFD_RELOC_SPU_PPU64:
 140       return R_SPU_PPU64;
 141     case BFD_RELOC_SPU_ADD_PIC:
 142       return R_SPU_ADD_PIC;
 143     }
 144 }
 145
 146 static void
 147 spu_elf_info_to_howto (bfd *abfd ATTRIBUTE_UNUSED,
 148                        arelent *cache_ptr,
 149                        Elf_Internal_Rela *dst)
 150 {
 151   enum elf_spu_reloc_type r_type;
 152
 153   r_type = (enum elf_spu_reloc_type) ELF32_R_TYPE (dst->r_info);
 154   BFD_ASSERT (r_type < R_SPU_max);
 155   cache_ptr->howto = &elf_howto_table[(int) r_type];
 156 }
 157
 158 static reloc_howto_type *
 159 spu_elf_reloc_type_lookup (bfd *abfd ATTRIBUTE_UNUSED,
 160                            bfd_reloc_code_real_type code)
 161 {
 162   enum elf_spu_reloc_type r_type = spu_elf_bfd_to_reloc_type (code);
 163
 164   if (r_type == R_SPU_NONE)
 165     return NULL;
 166
 167   return elf_howto_table + r_type;
 168 }
 169
 170 static reloc_howto_type *
 171 spu_elf_reloc_name_lookup (bfd *abfd ATTRIBUTE_UNUSED,
 172                            const char *r_name)
 173 {
 174   unsigned int i;
 175
 176   for (i = 0; i < sizeof (elf_howto_table) / sizeof (elf_howto_table[0]); i++)
 177     if (elf_howto_table[i].name != NULL
 178         && strcasecmp (elf_howto_table[i].name, r_name) == 0)
 179       return &elf_howto_table[i];
 180
 181   return NULL;
 182 }
 183
 184 /* Apply R_SPU_REL9 and R_SPU_REL9I relocs.  */
 185
 186 static bfd_reloc_status_type
 187 spu_elf_rel9 (bfd *abfd, arelent *reloc_entry, asymbol *symbol,
 188               void *data, asection *input_section,
 189               bfd *output_bfd, char **error_message)
 190 {
 191   bfd_size_type octets;
 192   bfd_vma val;
 193   long insn;
 194
 195   /* If this is a relocatable link (output_bfd test tells us), just
 196      call the generic function.  Any adjustment will be done at final
 197      link time.  */
 198   if (output_bfd != NULL)
 199     return bfd_elf_generic_reloc (abfd, reloc_entry, symbol, data,
 200                                   input_section, output_bfd, error_message);
 201
 202   if (reloc_entry->address > bfd_get_section_limit (abfd, input_section))
 203     return bfd_reloc_outofrange;
 204   octets = reloc_entry->address * bfd_octets_per_byte (abfd);
 205
 206   /* Get symbol value.  */
 207   val = 0;
 208   if (!bfd_is_com_section (symbol->section))
 209     val = symbol->value;
 210   if (symbol->section->output_section)
 211     val += symbol->section->output_section->vma;
 212
 213   val += reloc_entry->addend;
 214
 215   /* Make it pc-relative.  */
 216   val -= input_section->output_section->vma + input_section->output_offset;
 217
 218   val >>= 2;
 219   if (val + 256 >= 512)
 220     return bfd_reloc_overflow;
 221
 222   insn = bfd_get_32 (abfd, (bfd_byte *) data + octets);
 223
 224   /* Move two high bits of value to REL9I and REL9 position.
 225      The mask will take care of selecting the right field.  */
 226   val = (val & 0x7f) | ((val & 0x180) << 7) | ((val & 0x180) << 16);
 227   insn &= ~reloc_entry->howto->dst_mask;
 228   insn |= val & reloc_entry->howto->dst_mask;
 229   bfd_put_32 (abfd, insn, (bfd_byte *) data + octets);
 230   return bfd_reloc_ok;
 231 }
 232
 233 static bfd_boolean
 234 spu_elf_new_section_hook (bfd *abfd, asection *sec)
 235 {
 236   if (!sec->used_by_bfd)
 237     {
 238       struct _spu_elf_section_data *sdata;
 239
 240       sdata = bfd_zalloc (abfd, sizeof (*sdata));
 241       if (sdata == NULL)
 242         return FALSE;
 243       sec->used_by_bfd = sdata;
 244     }
 245
 246   return _bfd_elf_new_section_hook (abfd, sec);
 247 }
 248
 249 /* Set up overlay info for executables.  */
 250
 251 static bfd_boolean
 252 spu_elf_object_p (bfd *abfd)
 253 {
 254   if ((abfd->flags & (EXEC_P | DYNAMIC)) != 0)
 255     {
 256       unsigned int i, num_ovl, num_buf;
 257       Elf_Internal_Phdr *phdr = elf_tdata (abfd)->phdr;
 258       Elf_Internal_Ehdr *ehdr = elf_elfheader (abfd);
 259       Elf_Internal_Phdr *last_phdr = NULL;
 260
 261       for (num_buf = 0, num_ovl = 0, i = 0; i < ehdr->e_phnum; i++, phdr++)
 262         if (phdr->p_type == PT_LOAD && (phdr->p_flags & PF_OVERLAY) != 0)
 263           {
 264             unsigned int j;
 265
 266             ++num_ovl;
 267             if (last_phdr == NULL
 268                 || ((last_phdr->p_vaddr ^ phdr->p_vaddr) & 0x3ffff) != 0)
 269               ++num_buf;
 270             last_phdr = phdr;
 271             for (j = 1; j < elf_numsections (abfd); j++)
 272               {
 273                 Elf_Internal_Shdr *shdr = elf_elfsections (abfd)[j];
 274
 275                 if (ELF_SECTION_SIZE (shdr, phdr) != 0
 276                     && ELF_SECTION_IN_SEGMENT (shdr, phdr))
 277                   {
 278                     asection *sec = shdr->bfd_section;
 279                     spu_elf_section_data (sec)->u.o.ovl_index = num_ovl;
 280                     spu_elf_section_data (sec)->u.o.ovl_buf = num_buf;
 281                   }
 282               }
 283           }
 284     }
 285   return TRUE;
 286 }
 287
 288 /* Specially mark defined symbols named _EAR_* with BSF_KEEP so that
 289    strip --strip-unneeded will not remove them.  */
 290
 291 static void
 292 spu_elf_backend_symbol_processing (bfd *abfd ATTRIBUTE_UNUSED, asymbol *sym)
 293 {
 294   if (sym->name != NULL
 295       && sym->section != bfd_abs_section_ptr
 296       && strncmp (sym->name, "_EAR_", 5) == 0)
 297     sym->flags |= BSF_KEEP;
 298 }
 299
 300 /* SPU ELF linker hash table.  */
 301
 302 struct spu_link_hash_table
 303 {
 304   struct elf_link_hash_table elf;
 305
 306   struct spu_elf_params *params;
 307
 308   /* Shortcuts to overlay sections.  */
 309   asection *ovtab;
 310   asection *init;
 311   asection *toe;
 312   asection **ovl_sec;
 313
 314   /* Count of stubs in each overlay section.  */
 315   unsigned int *stub_count;
 316
 317   /* The stub section for each overlay section.  */
 318   asection **stub_sec;
 319
 320   struct elf_link_hash_entry *ovly_entry[2];
 321
 322   /* Number of overlay buffers.  */
 323   unsigned int num_buf;
 324
 325   /* Total number of overlays.  */
 326   unsigned int num_overlays;
 327
 328   /* For soft icache.  */
 329   unsigned int line_size_log2;
 330   unsigned int num_lines_log2;
 331   unsigned int fromelem_size_log2;
 332
 333   /* How much memory we have.  */
 334   unsigned int local_store;
 335
 336   /* Count of overlay stubs needed in non-overlay area.  */
 337   unsigned int non_ovly_stub;
 338
 339   /* Pointer to the fixup section */
 340   asection *sfixup;
 341
 342   /* Set on error.  */
 343   unsigned int stub_err : 1;
 344 };
 345
 346 /* Hijack the generic got fields for overlay stub accounting.  */
 347
 348 struct got_entry
 349 {
 350   struct got_entry *next;
 351   unsigned int ovl;
 352   union {
 353     bfd_vma addend;
 354     bfd_vma br_addr;
 355   };
 356   bfd_vma stub_addr;
 357 };
 358
 359 #define spu_hash_table(p) \
 360   (elf_hash_table_id ((struct elf_link_hash_table *) ((p)->hash)) \
 361   == SPU_ELF_DATA ? ((struct spu_link_hash_table *) ((p)->hash)) : NULL)
 362
 363 struct call_info
 364 {
 365   struct function_info *fun;
 366   struct call_info *next;
 367   unsigned int count;
 368   unsigned int max_depth;
 369   unsigned int is_tail : 1;
 370   unsigned int is_pasted : 1;
 371   unsigned int broken_cycle : 1;
 372   unsigned int priority : 13;
 373 };
 374
 375 struct function_info
 376 {
 377   /* List of functions called.  Also branches to hot/cold part of
 378      function.  */
 379   struct call_info *call_list;
 380   /* For hot/cold part of function, point to owner.  */
 381   struct function_info *start;
 382   /* Symbol at start of function.  */
 383   union {
 384     Elf_Internal_Sym *sym;
 385     struct elf_link_hash_entry *h;
 386   } u;
 387   /* Function section.  */
 388   asection *sec;
 389   asection *rodata;
 390   /* Where last called from, and number of sections called from.  */
 391   asection *last_caller;
 392   unsigned int call_count;
 393   /* Address range of (this part of) function.  */
 394   bfd_vma lo, hi;
 395   /* Offset where we found a store of lr, or -1 if none found.  */
 396   bfd_vma lr_store;
 397   /* Offset where we found the stack adjustment insn.  */
 398   bfd_vma sp_adjust;
 399   /* Stack usage.  */
 400   int stack;
 401   /* Distance from root of call tree.  Tail and hot/cold branches
 402      count as one deeper.  We aren't counting stack frames here.  */
 403   unsigned int depth;
 404   /* Set if global symbol.  */
 405   unsigned int global : 1;
 406   /* Set if known to be start of function (as distinct from a hunk
 407      in hot/cold section.  */
 408   unsigned int is_func : 1;
 409   /* Set if not a root node.  */
 410   unsigned int non_root : 1;
 411   /* Flags used during call tree traversal.  It's cheaper to replicate
 412      the visit flags than have one which needs clearing after a traversal.  */
 413   unsigned int visit1 : 1;
 414   unsigned int visit2 : 1;
 415   unsigned int marking : 1;
 416   unsigned int visit3 : 1;
 417   unsigned int visit4 : 1;
 418   unsigned int visit5 : 1;
 419   unsigned int visit6 : 1;
 420   unsigned int visit7 : 1;
 421 };
 422
 423 struct spu_elf_stack_info
 424 {
 425   int num_fun;
 426   int max_fun;
 427   /* Variable size array describing functions, one per contiguous
 428      address range belonging to a function.  */
 429   struct function_info fun[1];
 430 };
 431
 432 static struct function_info *find_function (asection *, bfd_vma,
 433                                             struct bfd_link_info *);
 434
 435 /* Create a spu ELF linker hash table.  */
 436
 437 static struct bfd_link_hash_table *
 438 spu_elf_link_hash_table_create (bfd *abfd)
 439 {
 440   struct spu_link_hash_table *htab;
 441
 442   htab = bfd_zmalloc (sizeof (*htab));
 443   if (htab == NULL)
 444     return NULL;
 445
 446   if (!_bfd_elf_link_hash_table_init (&htab->elf, abfd,
 447                                       _bfd_elf_link_hash_newfunc,
 448                                       sizeof (struct elf_link_hash_entry),
 449                                       SPU_ELF_DATA))
 450     {
 451       free (htab);
 452       return NULL;
 453     }
 454
 455   htab->elf.init_got_refcount.refcount = 0;
 456   htab->elf.init_got_refcount.glist = NULL;
 457   htab->elf.init_got_offset.offset = 0;
 458   htab->elf.init_got_offset.glist = NULL;
 459   return &htab->elf.root;
 460 }
 461
 462 void
 463 spu_elf_setup (struct bfd_link_info *info, struct spu_elf_params *params)
 464 {
 465   bfd_vma max_branch_log2;
 466
 467   struct spu_link_hash_table *htab = spu_hash_table (info);
 468   htab->params = params;
 469   htab->line_size_log2 = bfd_log2 (htab->params->line_size);
 470   htab->num_lines_log2 = bfd_log2 (htab->params->num_lines);
 471
 472   /* For the software i-cache, we provide a "from" list whose size
 473      is a power-of-two number of quadwords, big enough to hold one
 474      byte per outgoing branch.  Compute this number here.  */
 475   max_branch_log2 = bfd_log2 (htab->params->max_branch);
 476   htab->fromelem_size_log2 = max_branch_log2 > 4 ? max_branch_log2 - 4 : 0;
 477 }
 478
 479 /* Find the symbol for the given R_SYMNDX in IBFD and set *HP and *SYMP
 480    to (hash, NULL) for global symbols, and (NULL, sym) for locals.  Set
 481    *SYMSECP to the symbol's section.  *LOCSYMSP caches local syms.  */
 482
 483 static bfd_boolean
 484 get_sym_h (struct elf_link_hash_entry **hp,
 485            Elf_Internal_Sym **symp,
 486            asection **symsecp,
 487            Elf_Internal_Sym **locsymsp,
 488            unsigned long r_symndx,
 489            bfd *ibfd)
 490 {
 491   Elf_Internal_Shdr *symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
 492
 493   if (r_symndx >= symtab_hdr->sh_info)
 494     {
 495       struct elf_link_hash_entry **sym_hashes = elf_sym_hashes (ibfd);
 496       struct elf_link_hash_entry *h;
 497
 498       h = sym_hashes[r_symndx - symtab_hdr->sh_info];
 499       while (h->root.type == bfd_link_hash_indirect
 500              || h->root.type == bfd_link_hash_warning)
 501         h = (struct elf_link_hash_entry *) h->root.u.i.link;
 502
 503       if (hp != NULL)
 504         *hp = h;
 505
 506       if (symp != NULL)
 507         *symp = NULL;
 508
 509       if (symsecp != NULL)
 510         {
 511           asection *symsec = NULL;
 512           if (h->root.type == bfd_link_hash_defined
 513               || h->root.type == bfd_link_hash_defweak)
 514             symsec = h->root.u.def.section;
 515           *symsecp = symsec;
 516         }
 517     }
 518   else
 519     {
 520       Elf_Internal_Sym *sym;
 521       Elf_Internal_Sym *locsyms = *locsymsp;
 522
 523       if (locsyms == NULL)
 524         {
 525           locsyms = (Elf_Internal_Sym *) symtab_hdr->contents;
 526           if (locsyms == NULL)
 527             locsyms = bfd_elf_get_elf_syms (ibfd, symtab_hdr,
 528                                             symtab_hdr->sh_info,
 529                                             0, NULL, NULL, NULL);
 530           if (locsyms == NULL)
 531             return FALSE;
 532           *locsymsp = locsyms;
 533         }
 534       sym = locsyms + r_symndx;
 535
 536       if (hp != NULL)
 537         *hp = NULL;
 538
 539       if (symp != NULL)
 540         *symp = sym;
 541
 542       if (symsecp != NULL)
 543         *symsecp = bfd_section_from_elf_index (ibfd, sym->st_shndx);
 544     }
 545
 546   return TRUE;
 547 }
 548
 549 /* Create the note section if not already present.  This is done early so
 550    that the linker maps the sections to the right place in the output.  */
 551
 552 bfd_boolean
 553 spu_elf_create_sections (struct bfd_link_info *info)
 554 {
 555   struct spu_link_hash_table *htab = spu_hash_table (info);
 556   bfd *ibfd;
 557
 558   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
 559     if (bfd_get_section_by_name (ibfd, SPU_PTNOTE_SPUNAME) != NULL)
 560       break;
 561
 562   if (ibfd == NULL)
 563     {
 564       /* Make SPU_PTNOTE_SPUNAME section.  */
 565       asection *s;
 566       size_t name_len;
 567       size_t size;
 568       bfd_byte *data;
 569       flagword flags;
 570
 571       ibfd = info->input_bfds;
 572       flags = SEC_LOAD | SEC_READONLY | SEC_HAS_CONTENTS | SEC_IN_MEMORY;
 573       s = bfd_make_section_anyway_with_flags (ibfd, SPU_PTNOTE_SPUNAME, flags);
 574       if (s == NULL
 575           || !bfd_set_section_alignment (ibfd, s, 4))
 576         return FALSE;
 577
 578       name_len = strlen (bfd_get_filename (info->output_bfd)) + 1;
 579       size = 12 + ((sizeof (SPU_PLUGIN_NAME) + 3) & -4);
 580       size += (name_len + 3) & -4;
 581
 582       if (!bfd_set_section_size (ibfd, s, size))
 583         return FALSE;
 584
 585       data = bfd_zalloc (ibfd, size);
 586       if (data == NULL)
 587         return FALSE;
 588
 589       bfd_put_32 (ibfd, sizeof (SPU_PLUGIN_NAME), data + 0);
 590       bfd_put_32 (ibfd, name_len, data + 4);
 591       bfd_put_32 (ibfd, 1, data + 8);
 592       memcpy (data + 12, SPU_PLUGIN_NAME, sizeof (SPU_PLUGIN_NAME));
 593       memcpy (data + 12 + ((sizeof (SPU_PLUGIN_NAME) + 3) & -4),
 594               bfd_get_filename (info->output_bfd), name_len);
 595       s->contents = data;
 596     }
 597
 598   if (htab->params->emit_fixups)
 599     {
 600       asection *s;
 601       flagword flags;
 602
 603       if (htab->elf.dynobj == NULL)
 604         htab->elf.dynobj = ibfd;
 605       ibfd = htab->elf.dynobj;
 606       flags = (SEC_LOAD | SEC_ALLOC | SEC_READONLY | SEC_HAS_CONTENTS
 607                | SEC_IN_MEMORY | SEC_LINKER_CREATED);
 608       s = bfd_make_section_anyway_with_flags (ibfd, ".fixup", flags);
 609       if (s == NULL || !bfd_set_section_alignment (ibfd, s, 2))
 610         return FALSE;
 611       htab->sfixup = s;
 612     }
 613
 614   return TRUE;
 615 }
 616
 617 /* qsort predicate to sort sections by vma.  */
 618
 619 static int
 620 sort_sections (const void *a, const void *b)
 621 {
 622   const asection *const *s1 = a;
 623   const asection *const *s2 = b;
 624   bfd_signed_vma delta = (*s1)->vma - (*s2)->vma;
 625
 626   if (delta != 0)
 627     return delta < 0 ? -1 : 1;
 628
 629   return (*s1)->index - (*s2)->index;
 630 }
 631
 632 /* Identify overlays in the output bfd, and number them.
 633    Returns 0 on error, 1 if no overlays, 2 if overlays.  */
 634
 635 int
 636 spu_elf_find_overlays (struct bfd_link_info *info)
 637 {
 638   struct spu_link_hash_table *htab = spu_hash_table (info);
 639   asection **alloc_sec;
 640   unsigned int i, n, ovl_index, num_buf;
 641   asection *s;
 642   bfd_vma ovl_end;
 643   static const char *const entry_names[2][2] = {
 644     { "__ovly_load", "__icache_br_handler" },
 645     { "__ovly_return", "__icache_call_handler" }
 646   };
 647
 648   if (info->output_bfd->section_count < 2)
 649     return 1;
 650
 651   alloc_sec
 652     = bfd_malloc (info->output_bfd->section_count * sizeof (*alloc_sec));
 653   if (alloc_sec == NULL)
 654     return 0;
 655
 656   /* Pick out all the alloced sections.  */
 657   for (n = 0, s = info->output_bfd->sections; s != NULL; s = s->next)
 658     if ((s->flags & SEC_ALLOC) != 0
 659         && (s->flags & (SEC_LOAD | SEC_THREAD_LOCAL)) != SEC_THREAD_LOCAL
 660         && s->size != 0)
 661       alloc_sec[n++] = s;
 662
 663   if (n == 0)
 664     {
 665       free (alloc_sec);
 666       return 1;
 667     }
 668
 669   /* Sort them by vma.  */
 670   qsort (alloc_sec, n, sizeof (*alloc_sec), sort_sections);
 671
 672   ovl_end = alloc_sec[0]->vma + alloc_sec[0]->size;
 673   if (htab->params->ovly_flavour == ovly_soft_icache)
 674     {
 675       unsigned int prev_buf = 0, set_id = 0;
 676
 677       /* Look for an overlapping vma to find the first overlay section.  */
 678       bfd_vma vma_start = 0;
 679
 680       for (i = 1; i < n; i++)
 681         {
 682           s = alloc_sec[i];
 683           if (s->vma < ovl_end)
 684             {
 685               asection *s0 = alloc_sec[i - 1];
 686               vma_start = s0->vma;
 687               ovl_end = (s0->vma
 688                          + ((bfd_vma) 1
 689                             << (htab->num_lines_log2 + htab->line_size_log2)));
 690               --i;
 691               break;
 692             }
 693           else
 694             ovl_end = s->vma + s->size;
 695         }
 696
 697       /* Now find any sections within the cache area.  */
 698       for (ovl_index = 0, num_buf = 0; i < n; i++)
 699         {
 700           s = alloc_sec[i];
 701           if (s->vma >= ovl_end)
 702             break;
 703
 704           /* A section in an overlay area called .ovl.init is not
 705              an overlay, in the sense that it might be loaded in
 706              by the overlay manager, but rather the initial
 707              section contents for the overlay buffer.  */
 708           if (strncmp (s->name, ".ovl.init", 9) != 0)
 709             {
 710               num_buf = ((s->vma - vma_start) >> htab->line_size_log2) + 1;
 711               set_id = (num_buf == prev_buf)? set_id + 1 : 0;
 712               prev_buf = num_buf;
 713
 714               if ((s->vma - vma_start) & (htab->params->line_size - 1))
 715                 {
 716                   info->callbacks->einfo (_("%X%P: overlay section %A "
 717                                             "does not start on a cache line.\n"),
 718                                           s);
 719                   bfd_set_error (bfd_error_bad_value);
 720                   return 0;
 721                 }
 722               else if (s->size > htab->params->line_size)
 723                 {
 724                   info->callbacks->einfo (_("%X%P: overlay section %A "
 725                                             "is larger than a cache line.\n"),
 726                                           s);
 727                   bfd_set_error (bfd_error_bad_value);
 728                   return 0;
 729                 }
 730
 731               alloc_sec[ovl_index++] = s;
 732               spu_elf_section_data (s)->u.o.ovl_index
 733                 = (set_id << htab->num_lines_log2) + num_buf;
 734               spu_elf_section_data (s)->u.o.ovl_buf = num_buf;
 735             }
 736         }
 737
 738       /* Ensure there are no more overlay sections.  */
 739       for ( ; i < n; i++)
 740         {
 741           s = alloc_sec[i];
 742           if (s->vma < ovl_end)
 743             {
 744               info->callbacks->einfo (_("%X%P: overlay section %A "
 745                                         "is not in cache area.\n"),
 746                                       alloc_sec[i-1]);
 747               bfd_set_error (bfd_error_bad_value);
 748               return 0;
 749             }
 750           else
 751             ovl_end = s->vma + s->size;
 752         }
 753     }
 754   else
 755     {
 756       /* Look for overlapping vmas.  Any with overlap must be overlays.
 757          Count them.  Also count the number of overlay regions.  */
 758       for (ovl_index = 0, num_buf = 0, i = 1; i < n; i++)
 759         {
 760           s = alloc_sec[i];
 761           if (s->vma < ovl_end)
 762             {
 763               asection *s0 = alloc_sec[i - 1];
 764
 765               if (spu_elf_section_data (s0)->u.o.ovl_index == 0)
 766                 {
 767                   ++num_buf;
 768                   if (strncmp (s0->name, ".ovl.init", 9) != 0)
 769                     {
 770                       alloc_sec[ovl_index] = s0;
 771                       spu_elf_section_data (s0)->u.o.ovl_index = ++ovl_index;
 772                       spu_elf_section_data (s0)->u.o.ovl_buf = num_buf;
 773                     }
 774                   else
 775                     ovl_end = s->vma + s->size;
 776                 }
 777               if (strncmp (s->name, ".ovl.init", 9) != 0)
 778                 {
 779                   alloc_sec[ovl_index] = s;
 780                   spu_elf_section_data (s)->u.o.ovl_index = ++ovl_index;
 781                   spu_elf_section_data (s)->u.o.ovl_buf = num_buf;
 782                   if (s0->vma != s->vma)
 783                     {
 784                       info->callbacks->einfo (_("%X%P: overlay sections %A "
 785                                                 "and %A do not start at the "
 786                                                 "same address.\n"),
 787                                               s0, s);
 788                       bfd_set_error (bfd_error_bad_value);
 789                       return 0;
 790                     }
 791                   if (ovl_end < s->vma + s->size)
 792                     ovl_end = s->vma + s->size;
 793                 }
 794             }
 795           else
 796             ovl_end = s->vma + s->size;
 797         }
 798     }
 799
 800   htab->num_overlays = ovl_index;
 801   htab->num_buf = num_buf;
 802   htab->ovl_sec = alloc_sec;
 803
 804   if (ovl_index == 0)
 805     return 1;
 806
 807   for (i = 0; i < 2; i++)
 808     {
 809       const char *name;
 810       struct elf_link_hash_entry *h;
 811
 812       name = entry_names[i][htab->params->ovly_flavour];
 813       h = elf_link_hash_lookup (&htab->elf, name, TRUE, FALSE, FALSE);
 814       if (h == NULL)
 815         return 0;
 816
 817       if (h->root.type == bfd_link_hash_new)
 818         {
 819           h->root.type = bfd_link_hash_undefined;
 820           h->ref_regular = 1;
 821           h->ref_regular_nonweak = 1;
 822           h->non_elf = 0;
 823         }
 824       htab->ovly_entry[i] = h;
 825     }
 826
 827   return 2;
 828 }
 829
 830 /* Non-zero to use bra in overlay stubs rather than br.  */
 831 #define BRA_STUBS 0
 832
 833 #define BRA     0x30000000
 834 #define BRASL   0x31000000
 835 #define BR      0x32000000
 836 #define BRSL    0x33000000
 837 #define NOP     0x40200000
 838 #define LNOP    0x00200000
 839 #define ILA     0x42000000
 840
 841 /* Return true for all relative and absolute branch instructions.
 842    bra   00110000 0..
 843    brasl 00110001 0..
 844    br    00110010 0..
 845    brsl  00110011 0..
 846    brz   00100000 0..
 847    brnz  00100001 0..
 848    brhz  00100010 0..
 849    brhnz 00100011 0..  */
 850
 851 static bfd_boolean
 852 is_branch (const unsigned char *insn)
 853 {
 854   return (insn[0] & 0xec) == 0x20 && (insn[1] & 0x80) == 0;
 855 }
 856
 857 /* Return true for all indirect branch instructions.
 858    bi     00110101 000
 859    bisl   00110101 001
 860    iret   00110101 010
 861    bisled 00110101 011
 862    biz    00100101 000
 863    binz   00100101 001
 864    bihz   00100101 010
 865    bihnz  00100101 011  */
 866
 867 static bfd_boolean
 868 is_indirect_branch (const unsigned char *insn)
 869 {
 870   return (insn[0] & 0xef) == 0x25 && (insn[1] & 0x80) == 0;
 871 }
 872
 873 /* Return true for branch hint instructions.
 874    hbra  0001000..
 875    hbrr  0001001..  */
 876
 877 static bfd_boolean
 878 is_hint (const unsigned char *insn)
 879 {
 880   return (insn[0] & 0xfc) == 0x10;
 881 }
 882
 883 /* True if INPUT_SECTION might need overlay stubs.  */
 884
 885 static bfd_boolean
 886 maybe_needs_stubs (asection *input_section)
 887 {
 888   /* No stubs for debug sections and suchlike.  */
 889   if ((input_section->flags & SEC_ALLOC) == 0)
 890     return FALSE;
 891
 892   /* No stubs for link-once sections that will be discarded.  */
 893   if (input_section->output_section == bfd_abs_section_ptr)
 894     return FALSE;
 895
 896   /* Don't create stubs for .eh_frame references.  */
 897   if (strcmp (input_section->name, ".eh_frame") == 0)
 898     return FALSE;
 899
 900   return TRUE;
 901 }
 902
 903 enum _stub_type
 904 {
 905   no_stub,
 906   call_ovl_stub,
 907   br000_ovl_stub,
 908   br001_ovl_stub,
 909   br010_ovl_stub,
 910   br011_ovl_stub,
 911   br100_ovl_stub,
 912   br101_ovl_stub,
 913   br110_ovl_stub,
 914   br111_ovl_stub,
 915   nonovl_stub,
 916   stub_error
 917 };
 918
 919 /* Return non-zero if this reloc symbol should go via an overlay stub.
 920    Return 2 if the stub must be in non-overlay area.  */
 921
 922 static enum _stub_type
 923 needs_ovl_stub (struct elf_link_hash_entry *h,
 924                 Elf_Internal_Sym *sym,
 925                 asection *sym_sec,
 926                 asection *input_section,
 927                 Elf_Internal_Rela *irela,
 928                 bfd_byte *contents,
 929                 struct bfd_link_info *info)
 930 {
 931   struct spu_link_hash_table *htab = spu_hash_table (info);
 932   enum elf_spu_reloc_type r_type;
 933   unsigned int sym_type;
 934   bfd_boolean branch, hint, call;
 935   enum _stub_type ret = no_stub;
 936   bfd_byte insn[4];
 937
 938   if (sym_sec == NULL
 939       || sym_sec->output_section == bfd_abs_section_ptr
 940       || spu_elf_section_data (sym_sec->output_section) == NULL)
 941     return ret;
 942
 943   if (h != NULL)
 944     {
 945       /* Ensure no stubs for user supplied overlay manager syms.  */
 946       if (h == htab->ovly_entry[0] || h == htab->ovly_entry[1])
 947         return ret;
 948
 949       /* setjmp always goes via an overlay stub, because then the return
 950          and hence the longjmp goes via __ovly_return.  That magically
 951          makes setjmp/longjmp between overlays work.  */
 952       if (strncmp (h->root.root.string, "setjmp", 6) == 0
 953           && (h->root.root.string[6] == '\0' || h->root.root.string[6] == '@'))
 954         ret = call_ovl_stub;
 955     }
 956
 957   if (h != NULL)
 958     sym_type = h->type;
 959   else
 960     sym_type = ELF_ST_TYPE (sym->st_info);
 961
 962   r_type = ELF32_R_TYPE (irela->r_info);
 963   branch = FALSE;
 964   hint = FALSE;
 965   call = FALSE;
 966   if (r_type == R_SPU_REL16 || r_type == R_SPU_ADDR16)
 967     {
 968       if (contents == NULL)
 969         {
 970           contents = insn;
 971           if (!bfd_get_section_contents (input_section->owner,
 972                                          input_section,
 973                                          contents,
 974                                          irela->r_offset, 4))
 975             return stub_error;
 976         }
 977       else
 978         contents += irela->r_offset;
 979
 980       branch = is_branch (contents);
 981       hint = is_hint (contents);
 982       if (branch || hint)
 983         {
 984           call = (contents[0] & 0xfd) == 0x31;
 985           if (call
 986               && sym_type != STT_FUNC
 987               && contents != insn)
 988             {
 989               /* It's common for people to write assembly and forget
 990                  to give function symbols the right type.  Handle
 991                  calls to such symbols, but warn so that (hopefully)
 992                  people will fix their code.  We need the symbol
 993                  type to be correct to distinguish function pointer
 994                  initialisation from other pointer initialisations.  */
 995               const char *sym_name;
 996
 997               if (h != NULL)
 998                 sym_name = h->root.root.string;
 999               else
1000                 {
1001                   Elf_Internal_Shdr *symtab_hdr;
1002                   symtab_hdr = &elf_tdata (input_section->owner)->symtab_hdr;
1003                   sym_name = bfd_elf_sym_name (input_section->owner,
1004                                                symtab_hdr,
1005                                                sym,
1006                                                sym_sec);
1007                 }
1008               (*_bfd_error_handler) (_("warning: call to non-function"
1009                                        " symbol %s defined in %B"),
1010                                      sym_sec->owner, sym_name);
1011
1012             }
1013         }
1014     }
1015
1016   if ((!branch && htab->params->ovly_flavour == ovly_soft_icache)
1017       || (sym_type != STT_FUNC
1018           && !(branch || hint)
1019           && (sym_sec->flags & SEC_CODE) == 0))
1020     return no_stub;
1021
1022   /* Usually, symbols in non-overlay sections don't need stubs.  */
1023   if (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index == 0
1024       && !htab->params->non_overlay_stubs)
1025     return ret;
1026
1027   /* A reference from some other section to a symbol in an overlay
1028      section needs a stub.  */
1029   if (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index
1030        != spu_elf_section_data (input_section->output_section)->u.o.ovl_index)
1031     {
1032       unsigned int lrlive = 0;
1033       if (branch)
1034         lrlive = (contents[1] & 0x70) >> 4;
1035
1036       if (!lrlive && (call || sym_type == STT_FUNC))
1037         ret = call_ovl_stub;
1038       else
1039         ret = br000_ovl_stub + lrlive;
1040     }
1041
1042   /* If this insn isn't a branch then we are possibly taking the
1043      address of a function and passing it out somehow.  Soft-icache code
1044      always generates inline code to do indirect branches.  */
1045   if (!(branch || hint)
1046       && sym_type == STT_FUNC
1047       && htab->params->ovly_flavour != ovly_soft_icache)
1048     ret = nonovl_stub;
1049
1050   return ret;
1051 }
1052
1053 static bfd_boolean
1054 count_stub (struct spu_link_hash_table *htab,
1055             bfd *ibfd,
1056             asection *isec,
1057             enum _stub_type stub_type,
1058             struct elf_link_hash_entry *h,
1059             const Elf_Internal_Rela *irela)
1060 {
1061   unsigned int ovl = 0;
1062   struct got_entry *g, **head;
1063   bfd_vma addend;
1064
1065   /* If this instruction is a branch or call, we need a stub
1066      for it.  One stub per function per overlay.
1067      If it isn't a branch, then we are taking the address of
1068      this function so need a stub in the non-overlay area
1069      for it.  One stub per function.  */
1070   if (stub_type != nonovl_stub)
1071     ovl = spu_elf_section_data (isec->output_section)->u.o.ovl_index;
1072
1073   if (h != NULL)
1074     head = &h->got.glist;
1075   else
1076     {
1077       if (elf_local_got_ents (ibfd) == NULL)
1078         {
1079           bfd_size_type amt = (elf_tdata (ibfd)->symtab_hdr.sh_info
1080                                * sizeof (*elf_local_got_ents (ibfd)));
1081           elf_local_got_ents (ibfd) = bfd_zmalloc (amt);
1082           if (elf_local_got_ents (ibfd) == NULL)
1083             return FALSE;
1084         }
1085       head = elf_local_got_ents (ibfd) + ELF32_R_SYM (irela->r_info);
1086     }
1087
1088   if (htab->params->ovly_flavour == ovly_soft_icache)
1089     {
1090       htab->stub_count[ovl] += 1;
1091       return TRUE;
1092     }
1093
1094   addend = 0;
1095   if (irela != NULL)
1096     addend = irela->r_addend;
1097
1098   if (ovl == 0)
1099     {
1100       struct got_entry *gnext;
1101
1102       for (g = *head; g != NULL; g = g->next)
1103         if (g->addend == addend && g->ovl == 0)
1104           break;
1105
1106       if (g == NULL)
1107         {
1108           /* Need a new non-overlay area stub.  Zap other stubs.  */
1109           for (g = *head; g != NULL; g = gnext)
1110             {
1111               gnext = g->next;
1112               if (g->addend == addend)
1113                 {
1114                   htab->stub_count[g->ovl] -= 1;
1115                   free (g);
1116                 }
1117             }
1118         }
1119     }
1120   else
1121     {
1122       for (g = *head; g != NULL; g = g->next)
1123         if (g->addend == addend && (g->ovl == ovl || g->ovl == 0))
1124           break;
1125     }
1126
1127   if (g == NULL)
1128     {
1129       g = bfd_malloc (sizeof *g);
1130       if (g == NULL)
1131         return FALSE;
1132       g->ovl = ovl;
1133       g->addend = addend;
1134       g->stub_addr = (bfd_vma) -1;
1135       g->next = *head;
1136       *head = g;
1137
1138       htab->stub_count[ovl] += 1;
1139     }
1140
1141   return TRUE;
1142 }
1143
1144 /* Support two sizes of overlay stubs, a slower more compact stub of two
1145    instructions, and a faster stub of four instructions.
1146    Soft-icache stubs are four or eight words.  */
1147
1148 static unsigned int
1149 ovl_stub_size (struct spu_elf_params *params)
1150 {
1151   return 16 << params->ovly_flavour >> params->compact_stub;
1152 }
1153
1154 static unsigned int
1155 ovl_stub_size_log2 (struct spu_elf_params *params)
1156 {
1157   return 4 + params->ovly_flavour - params->compact_stub;
1158 }
1159
1160 /* Two instruction overlay stubs look like:
1161
1162    brsl $75,__ovly_load
1163    .word target_ovl_and_address
1164
1165    ovl_and_address is a word with the overlay number in the top 14 bits
1166    and local store address in the bottom 18 bits.
1167
1168    Four instruction overlay stubs look like:
1169
1170    ila $78,ovl_number
1171    lnop
1172    ila $79,target_address
1173    br __ovly_load
1174
1175    Software icache stubs are:
1176
1177    .word target_index
1178    .word target_ia;
1179    .word lrlive_branchlocalstoreaddr;
1180    brasl $75,__icache_br_handler
1181    .quad xor_pattern
1182 */
1183
1184 static bfd_boolean
1185 build_stub (struct bfd_link_info *info,
1186             bfd *ibfd,
1187             asection *isec,
1188             enum _stub_type stub_type,
1189             struct elf_link_hash_entry *h,
1190             const Elf_Internal_Rela *irela,
1191             bfd_vma dest,
1192             asection *dest_sec)
1193 {
1194   struct spu_link_hash_table *htab = spu_hash_table (info);
1195   unsigned int ovl, dest_ovl, set_id;
1196   struct got_entry *g, **head;
1197   asection *sec;
1198   bfd_vma addend, from, to, br_dest, patt;
1199   unsigned int lrlive;
1200
1201   ovl = 0;
1202   if (stub_type != nonovl_stub)
1203     ovl = spu_elf_section_data (isec->output_section)->u.o.ovl_index;
1204
1205   if (h != NULL)
1206     head = &h->got.glist;
1207   else
1208     head = elf_local_got_ents (ibfd) + ELF32_R_SYM (irela->r_info);
1209
1210   addend = 0;
1211   if (irela != NULL)
1212     addend = irela->r_addend;
1213
1214   if (htab->params->ovly_flavour == ovly_soft_icache)
1215     {
1216       g = bfd_malloc (sizeof *g);
1217       if (g == NULL)
1218         return FALSE;
1219       g->ovl = ovl;
1220       g->br_addr = 0;
1221       if (irela != NULL)
1222         g->br_addr = (irela->r_offset
1223                       + isec->output_offset
1224                       + isec->output_section->vma);
1225       g->next = *head;
1226       *head = g;
1227     }
1228   else
1229     {
1230       for (g = *head; g != NULL; g = g->next)
1231         if (g->addend == addend && (g->ovl == ovl || g->ovl == 0))
1232           break;
1233       if (g == NULL)
1234         abort ();
1235
1236       if (g->ovl == 0 && ovl != 0)
1237         return TRUE;
1238
1239       if (g->stub_addr != (bfd_vma) -1)
1240         return TRUE;
1241     }
1242
1243   sec = htab->stub_sec[ovl];
1244   dest += dest_sec->output_offset + dest_sec->output_section->vma;
1245   from = sec->size + sec->output_offset + sec->output_section->vma;
1246   g->stub_addr = from;
1247   to = (htab->ovly_entry[0]->root.u.def.value
1248         + htab->ovly_entry[0]->root.u.def.section->output_offset
1249         + htab->ovly_entry[0]->root.u.def.section->output_section->vma);
1250
1251   if (((dest | to | from) & 3) != 0)
1252     {
1253       htab->stub_err = 1;
1254       return FALSE;
1255     }
1256   dest_ovl = spu_elf_section_data (dest_sec->output_section)->u.o.ovl_index;
1257
1258   if (htab->params->ovly_flavour == ovly_normal
1259       && !htab->params->compact_stub)
1260     {
1261       bfd_put_32 (sec->owner, ILA + ((dest_ovl << 7) & 0x01ffff80) + 78,
1262                   sec->contents + sec->size);
1263       bfd_put_32 (sec->owner, LNOP,
1264                   sec->contents + sec->size + 4);
1265       bfd_put_32 (sec->owner, ILA + ((dest << 7) & 0x01ffff80) + 79,
1266                   sec->contents + sec->size + 8);
1267       if (!BRA_STUBS)
1268         bfd_put_32 (sec->owner, BR + (((to - (from + 12)) << 5) & 0x007fff80),
1269                     sec->contents + sec->size + 12);
1270       else
1271         bfd_put_32 (sec->owner, BRA + ((to << 5) & 0x007fff80),
1272                     sec->contents + sec->size + 12);
1273     }
1274   else if (htab->params->ovly_flavour == ovly_normal
1275            && htab->params->compact_stub)
1276     {
1277       if (!BRA_STUBS)
1278         bfd_put_32 (sec->owner, BRSL + (((to - from) << 5) & 0x007fff80) + 75,
1279                     sec->contents + sec->size);
1280       else
1281         bfd_put_32 (sec->owner, BRASL + ((to << 5) & 0x007fff80) + 75,
1282                     sec->contents + sec->size);
1283       bfd_put_32 (sec->owner, (dest & 0x3ffff) | (dest_ovl << 18),
1284                   sec->contents + sec->size + 4);
1285     }
1286   else if (htab->params->ovly_flavour == ovly_soft_icache
1287            && htab->params->compact_stub)
1288     {
1289       lrlive = 0;
1290       if (stub_type == nonovl_stub)
1291         ;
1292       else if (stub_type == call_ovl_stub)
1293         /* A brsl makes lr live and *(*sp+16) is live.
1294            Tail calls have the same liveness.  */
1295         lrlive = 5;
1296       else if (!htab->params->lrlive_analysis)
1297         /* Assume stack frame and lr save.  */
1298         lrlive = 1;
1299       else if (irela != NULL)
1300         {
1301           /* Analyse branch instructions.  */
1302           struct function_info *caller;
1303           bfd_vma off;
1304
1305           caller = find_function (isec, irela->r_offset, info);
1306           if (caller->start == NULL)
1307             off = irela->r_offset;
1308           else
1309             {
1310               struct function_info *found = NULL;
1311
1312               /* Find the earliest piece of this function that
1313                  has frame adjusting instructions.  We might
1314                  see dynamic frame adjustment (eg. for alloca)
1315                  in some later piece, but functions using
1316                  alloca always set up a frame earlier.  Frame
1317                  setup instructions are always in one piece.  */
1318               if (caller->lr_store != (bfd_vma) -1
1319                   || caller->sp_adjust != (bfd_vma) -1)
1320                 found = caller;
1321               while (caller->start != NULL)
1322                 {
1323                   caller = caller->start;
1324                   if (caller->lr_store != (bfd_vma) -1
1325                       || caller->sp_adjust != (bfd_vma) -1)
1326                     found = caller;
1327                 }
1328               if (found != NULL)
1329                 caller = found;
1330               off = (bfd_vma) -1;
1331             }
1332
1333           if (off > caller->sp_adjust)
1334             {
1335               if (off > caller->lr_store)
1336                 /* Only *(*sp+16) is live.  */
1337                 lrlive = 1;
1338               else
1339                 /* If no lr save, then we must be in a
1340                    leaf function with a frame.
1341                    lr is still live.  */
1342                 lrlive = 4;
1343             }
1344           else if (off > caller->lr_store)
1345             {
1346               /* Between lr save and stack adjust.  */
1347               lrlive = 3;
1348               /* This should never happen since prologues won't
1349                  be split here.  */
1350               BFD_ASSERT (0);
1351             }
1352           else
1353             /* On entry to function.  */
1354             lrlive = 5;
1355
1356           if (stub_type != br000_ovl_stub
1357               && lrlive != stub_type - br000_ovl_stub)
1358             info->callbacks->einfo (_("%A:0x%v lrlive .brinfo (%u) differs "
1359                                       "from analysis (%u)\n"),
1360                                     isec, irela->r_offset, lrlive,
1361                                     stub_type - br000_ovl_stub);
1362         }
1363
1364       /* If given lrlive info via .brinfo, use it.  */
1365       if (stub_type > br000_ovl_stub)
1366         lrlive = stub_type - br000_ovl_stub;
1367
1368       if (ovl == 0)
1369         to = (htab->ovly_entry[1]->root.u.def.value
1370               + htab->ovly_entry[1]->root.u.def.section->output_offset
1371               + htab->ovly_entry[1]->root.u.def.section->output_section->vma);
1372
1373       /* The branch that uses this stub goes to stub_addr + 4.  We'll
1374          set up an xor pattern that can be used by the icache manager
1375          to modify this branch to go directly to its destination.  */
1376       g->stub_addr += 4;
1377       br_dest = g->stub_addr;
1378       if (irela == NULL)
1379         {
1380           /* Except in the case of _SPUEAR_ stubs, the branch in
1381              question is the one in the stub itself.  */
1382           BFD_ASSERT (stub_type == nonovl_stub);
1383           g->br_addr = g->stub_addr;
1384           br_dest = to;
1385         }
1386
1387       set_id = ((dest_ovl - 1) >> htab->num_lines_log2) + 1;
1388       bfd_put_32 (sec->owner, (set_id << 18) | (dest & 0x3ffff),
1389                   sec->contents + sec->size);
1390       bfd_put_32 (sec->owner, BRASL + ((to << 5) & 0x007fff80) + 75,
1391                   sec->contents + sec->size + 4);
1392       bfd_put_32 (sec->owner, (lrlive << 29) | (g->br_addr & 0x3ffff),
1393                   sec->contents + sec->size + 8);
1394       patt = dest ^ br_dest;
1395       if (irela != NULL && ELF32_R_TYPE (irela->r_info) == R_SPU_REL16)
1396         patt = (dest - g->br_addr) ^ (br_dest - g->br_addr);
1397       bfd_put_32 (sec->owner, (patt << 5) & 0x007fff80,
1398                   sec->contents + sec->size + 12);
1399
1400       if (ovl == 0)
1401         /* Extra space for linked list entries.  */
1402         sec->size += 16;
1403     }
1404   else
1405     abort ();
1406
1407   sec->size += ovl_stub_size (htab->params);
1408
1409   if (htab->params->emit_stub_syms)
1410     {
1411       size_t len;
1412       char *name;
1413       int add;
1414
1415       len = 8 + sizeof (".ovl_call.") - 1;
1416       if (h != NULL)
1417         len += strlen (h->root.root.string);
1418       else
1419         len += 8 + 1 + 8;
1420       add = 0;
1421       if (irela != NULL)
1422         add = (int) irela->r_addend & 0xffffffff;
1423       if (add != 0)
1424         len += 1 + 8;
1425       name = bfd_malloc (len + 1);
1426       if (name == NULL)
1427         return FALSE;
1428
1429       sprintf (name, "%08x.ovl_call.", g->ovl);
1430       if (h != NULL)
1431         strcpy (name + 8 + sizeof (".ovl_call.") - 1, h->root.root.string);
1432       else
1433         sprintf (name + 8 + sizeof (".ovl_call.") - 1, "%x:%x",
1434                  dest_sec->id & 0xffffffff,
1435                  (int) ELF32_R_SYM (irela->r_info) & 0xffffffff);
1436       if (add != 0)
1437         sprintf (name + len - 9, "+%x", add);
1438
1439       h = elf_link_hash_lookup (&htab->elf, name, TRUE, TRUE, FALSE);
1440       free (name);
1441       if (h == NULL)
1442         return FALSE;
1443       if (h->root.type == bfd_link_hash_new)
1444         {
1445           h->root.type = bfd_link_hash_defined;
1446           h->root.u.def.section = sec;
1447           h->size = ovl_stub_size (htab->params);
1448           h->root.u.def.value = sec->size - h->size;
1449           h->type = STT_FUNC;
1450           h->ref_regular = 1;
1451           h->def_regular = 1;
1452           h->ref_regular_nonweak = 1;
1453           h->forced_local = 1;
1454           h->non_elf = 0;
1455         }
1456     }
1457
1458   return TRUE;
1459 }
1460
1461 /* Called via elf_link_hash_traverse to allocate stubs for any _SPUEAR_
1462    symbols.  */
1463
1464 static bfd_boolean
1465 allocate_spuear_stubs (struct elf_link_hash_entry *h, void *inf)
1466 {
1467   /* Symbols starting with _SPUEAR_ need a stub because they may be
1468      invoked by the PPU.  */
1469   struct bfd_link_info *info = inf;
1470   struct spu_link_hash_table *htab = spu_hash_table (info);
1471   asection *sym_sec;
1472
1473   if ((h->root.type == bfd_link_hash_defined
1474        || h->root.type == bfd_link_hash_defweak)
1475       && h->def_regular
1476       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0
1477       && (sym_sec = h->root.u.def.section) != NULL
1478       && sym_sec->output_section != bfd_abs_section_ptr
1479       && spu_elf_section_data (sym_sec->output_section) != NULL
1480       && (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index != 0
1481           || htab->params->non_overlay_stubs))
1482     {
1483       return count_stub (htab, NULL, NULL, nonovl_stub, h, NULL);
1484     }
1485
1486   return TRUE;
1487 }
1488
1489 static bfd_boolean
1490 build_spuear_stubs (struct elf_link_hash_entry *h, void *inf)
1491 {
1492   /* Symbols starting with _SPUEAR_ need a stub because they may be
1493      invoked by the PPU.  */
1494   struct bfd_link_info *info = inf;
1495   struct spu_link_hash_table *htab = spu_hash_table (info);
1496   asection *sym_sec;
1497
1498   if ((h->root.type == bfd_link_hash_defined
1499        || h->root.type == bfd_link_hash_defweak)
1500       && h->def_regular
1501       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0
1502       && (sym_sec = h->root.u.def.section) != NULL
1503       && sym_sec->output_section != bfd_abs_section_ptr
1504       && spu_elf_section_data (sym_sec->output_section) != NULL
1505       && (spu_elf_section_data (sym_sec->output_section)->u.o.ovl_index != 0
1506           || htab->params->non_overlay_stubs))
1507     {
1508       return build_stub (info, NULL, NULL, nonovl_stub, h, NULL,
1509                          h->root.u.def.value, sym_sec);
1510     }
1511
1512   return TRUE;
1513 }
1514
1515 /* Size or build stubs.  */
1516
1517 static bfd_boolean
1518 process_stubs (struct bfd_link_info *info, bfd_boolean build)
1519 {
1520   struct spu_link_hash_table *htab = spu_hash_table (info);
1521   bfd *ibfd;
1522
1523   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
1524     {
1525       extern const bfd_target spu_elf32_vec;
1526       Elf_Internal_Shdr *symtab_hdr;
1527       asection *isec;
1528       Elf_Internal_Sym *local_syms = NULL;
1529
1530       if (ibfd->xvec != &spu_elf32_vec)
1531         continue;
1532
1533       /* We'll need the symbol table in a second.  */
1534       symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
1535       if (symtab_hdr->sh_info == 0)
1536         continue;
1537
1538       /* Walk over each section attached to the input bfd.  */
1539       for (isec = ibfd->sections; isec != NULL; isec = isec->next)
1540         {
1541           Elf_Internal_Rela *internal_relocs, *irelaend, *irela;
1542
1543           /* If there aren't any relocs, then there's nothing more to do.  */
1544           if ((isec->flags & SEC_RELOC) == 0
1545               || isec->reloc_count == 0)
1546             continue;
1547
1548           if (!maybe_needs_stubs (isec))
1549             continue;
1550
1551           /* Get the relocs.  */
1552           internal_relocs = _bfd_elf_link_read_relocs (ibfd, isec, NULL, NULL,
1553                                                        info->keep_memory);
1554           if (internal_relocs == NULL)
1555             goto error_ret_free_local;
1556
1557           /* Now examine each relocation.  */
1558           irela = internal_relocs;
1559           irelaend = irela + isec->reloc_count;
1560           for (; irela < irelaend; irela++)
1561             {
1562               enum elf_spu_reloc_type r_type;
1563               unsigned int r_indx;
1564               asection *sym_sec;
1565               Elf_Internal_Sym *sym;
1566               struct elf_link_hash_entry *h;
1567               enum _stub_type stub_type;
1568
1569               r_type = ELF32_R_TYPE (irela->r_info);
1570               r_indx = ELF32_R_SYM (irela->r_info);
1571
1572               if (r_type >= R_SPU_max)
1573                 {
1574                   bfd_set_error (bfd_error_bad_value);
1575                 error_ret_free_internal:
1576                   if (elf_section_data (isec)->relocs != internal_relocs)
1577                     free (internal_relocs);
1578                 error_ret_free_local:
1579                   if (local_syms != NULL
1580                       && (symtab_hdr->contents
1581                           != (unsigned char *) local_syms))
1582                     free (local_syms);
1583                   return FALSE;
1584                 }
1585
1586               /* Determine the reloc target section.  */
1587               if (!get_sym_h (&h, &sym, &sym_sec, &local_syms, r_indx, ibfd))
1588                 goto error_ret_free_internal;
1589
1590               stub_type = needs_ovl_stub (h, sym, sym_sec, isec, irela,
1591                                           NULL, info);
1592               if (stub_type == no_stub)
1593                 continue;
1594               else if (stub_type == stub_error)
1595                 goto error_ret_free_internal;
1596
1597               if (htab->stub_count == NULL)
1598                 {
1599                   bfd_size_type amt;
1600                   amt = (htab->num_overlays + 1) * sizeof (*htab->stub_count);
1601                   htab->stub_count = bfd_zmalloc (amt);
1602                   if (htab->stub_count == NULL)
1603                     goto error_ret_free_internal;
1604                 }
1605
1606               if (!build)
1607                 {
1608                   if (!count_stub (htab, ibfd, isec, stub_type, h, irela))
1609                     goto error_ret_free_internal;
1610                 }
1611               else
1612                 {
1613                   bfd_vma dest;
1614
1615                   if (h != NULL)
1616                     dest = h->root.u.def.value;
1617                   else
1618                     dest = sym->st_value;
1619                   dest += irela->r_addend;
1620                   if (!build_stub (info, ibfd, isec, stub_type, h, irela,
1621                                    dest, sym_sec))
1622                     goto error_ret_free_internal;
1623                 }
1624             }
1625
1626           /* We're done with the internal relocs, free them.  */
1627           if (elf_section_data (isec)->relocs != internal_relocs)
1628             free (internal_relocs);
1629         }
1630
1631       if (local_syms != NULL
1632           && symtab_hdr->contents != (unsigned char *) local_syms)
1633         {
1634           if (!info->keep_memory)
1635             free (local_syms);
1636           else
1637             symtab_hdr->contents = (unsigned char *) local_syms;
1638         }
1639     }
1640
1641   return TRUE;
1642 }
1643
1644 /* Allocate space for overlay call and return stubs.
1645    Return 0 on error, 1 if no overlays, 2 otherwise.  */
1646
1647 int
1648 spu_elf_size_stubs (struct bfd_link_info *info)
1649 {
1650   struct spu_link_hash_table *htab;
1651   bfd *ibfd;
1652   bfd_size_type amt;
1653   flagword flags;
1654   unsigned int i;
1655   asection *stub;
1656
1657   if (!process_stubs (info, FALSE))
1658     return 0;
1659
1660   htab = spu_hash_table (info);
1661   elf_link_hash_traverse (&htab->elf, allocate_spuear_stubs, info);
1662   if (htab->stub_err)
1663     return 0;
1664
1665   ibfd = info->input_bfds;
1666   if (htab->stub_count != NULL)
1667     {
1668       amt = (htab->num_overlays + 1) * sizeof (*htab->stub_sec);
1669       htab->stub_sec = bfd_zmalloc (amt);
1670       if (htab->stub_sec == NULL)
1671         return 0;
1672
1673       flags = (SEC_ALLOC | SEC_LOAD | SEC_CODE | SEC_READONLY
1674                | SEC_HAS_CONTENTS | SEC_IN_MEMORY);
1675       stub = bfd_make_section_anyway_with_flags (ibfd, ".stub", flags);
1676       htab->stub_sec[0] = stub;
1677       if (stub == NULL
1678           || !bfd_set_section_alignment (ibfd, stub,
1679                                          ovl_stub_size_log2 (htab->params)))
1680         return 0;
1681       stub->size = htab->stub_count[0] * ovl_stub_size (htab->params);
1682       if (htab->params->ovly_flavour == ovly_soft_icache)
1683         /* Extra space for linked list entries.  */
1684         stub->size += htab->stub_count[0] * 16;
1685
1686       for (i = 0; i < htab->num_overlays; ++i)
1687         {
1688           asection *osec = htab->ovl_sec[i];
1689           unsigned int ovl = spu_elf_section_data (osec)->u.o.ovl_index;
1690           stub = bfd_make_section_anyway_with_flags (ibfd, ".stub", flags);
1691           htab->stub_sec[ovl] = stub;
1692           if (stub == NULL
1693               || !bfd_set_section_alignment (ibfd, stub,
1694                                              ovl_stub_size_log2 (htab->params)))
1695             return 0;
1696           stub->size = htab->stub_count[ovl] * ovl_stub_size (htab->params);
1697         }
1698     }
1699
1700   if (htab->params->ovly_flavour == ovly_soft_icache)
1701     {
1702       /* Space for icache manager tables.
1703          a) Tag array, one quadword per cache line.
1704          b) Rewrite "to" list, one quadword per cache line.
1705          c) Rewrite "from" list, one byte per outgoing branch (rounded up to
1706             a power-of-two number of full quadwords) per cache line.  */
1707
1708       flags = SEC_ALLOC;
1709       htab->ovtab = bfd_make_section_anyway_with_flags (ibfd, ".ovtab", flags);
1710       if (htab->ovtab == NULL
1711           || !bfd_set_section_alignment (ibfd, htab->ovtab, 4))
1712         return 0;
1713
1714       htab->ovtab->size = (16 + 16 + (16 << htab->fromelem_size_log2))
1715                           << htab->num_lines_log2;
1716
1717       flags = SEC_ALLOC | SEC_LOAD | SEC_HAS_CONTENTS | SEC_IN_MEMORY;
1718       htab->init = bfd_make_section_anyway_with_flags (ibfd, ".ovini", flags);
1719       if (htab->init == NULL
1720           || !bfd_set_section_alignment (ibfd, htab->init, 4))
1721         return 0;
1722
1723       htab->init->size = 16;
1724     }
1725   else if (htab->stub_count == NULL)
1726     return 1;
1727   else
1728     {
1729       /* htab->ovtab consists of two arrays.
1730          .      struct {
1731          .        u32 vma;
1732          .        u32 size;
1733          .        u32 file_off;
1734          .        u32 buf;
1735          .      } _ovly_table[];
1736          .
1737          .      struct {
1738          .        u32 mapped;
1739          .      } _ovly_buf_table[];
1740          .  */
1741
1742       flags = SEC_ALLOC | SEC_LOAD | SEC_HAS_CONTENTS | SEC_IN_MEMORY;
1743       htab->ovtab = bfd_make_section_anyway_with_flags (ibfd, ".ovtab", flags);
1744       if (htab->ovtab == NULL
1745           || !bfd_set_section_alignment (ibfd, htab->ovtab, 4))
1746         return 0;
1747
1748       htab->ovtab->size = htab->num_overlays * 16 + 16 + htab->num_buf * 4;
1749     }
1750
1751   htab->toe = bfd_make_section_anyway_with_flags (ibfd, ".toe", SEC_ALLOC);
1752   if (htab->toe == NULL
1753       || !bfd_set_section_alignment (ibfd, htab->toe, 4))
1754     return 0;
1755   htab->toe->size = 16;
1756
1757   return 2;
1758 }
1759
1760 /* Called from ld to place overlay manager data sections.  This is done
1761    after the overlay manager itself is loaded, mainly so that the
1762    linker's htab->init section is placed after any other .ovl.init
1763    sections.  */
1764
1765 void
1766 spu_elf_place_overlay_data (struct bfd_link_info *info)
1767 {
1768   struct spu_link_hash_table *htab = spu_hash_table (info);
1769   unsigned int i;
1770
1771   if (htab->stub_sec != NULL)
1772     {
1773       (*htab->params->place_spu_section) (htab->stub_sec[0], NULL, ".text");
1774
1775       for (i = 0; i < htab->num_overlays; ++i)
1776         {
1777           asection *osec = htab->ovl_sec[i];
1778           unsigned int ovl = spu_elf_section_data (osec)->u.o.ovl_index;
1779           (*htab->params->place_spu_section) (htab->stub_sec[ovl], osec, NULL);
1780         }
1781     }
1782
1783   if (htab->params->ovly_flavour == ovly_soft_icache)
1784     (*htab->params->place_spu_section) (htab->init, NULL, ".ovl.init");
1785
1786   if (htab->ovtab != NULL)
1787     {
1788       const char *ovout = ".data";
1789       if (htab->params->ovly_flavour == ovly_soft_icache)
1790         ovout = ".bss";
1791       (*htab->params->place_spu_section) (htab->ovtab, NULL, ovout);
1792     }
1793
1794   if (htab->toe != NULL)
1795     (*htab->params->place_spu_section) (htab->toe, NULL, ".toe");
1796 }
1797
1798 /* Functions to handle embedded spu_ovl.o object.  */
1799
1800 static void *
1801 ovl_mgr_open (struct bfd *nbfd ATTRIBUTE_UNUSED, void *stream)
1802 {
1803   return stream;
1804 }
1805
1806 static file_ptr
1807 ovl_mgr_pread (struct bfd *abfd ATTRIBUTE_UNUSED,
1808                void *stream,
1809                void *buf,
1810                file_ptr nbytes,
1811                file_ptr offset)
1812 {
1813   struct _ovl_stream *os;
1814   size_t count;
1815   size_t max;
1816
1817   os = (struct _ovl_stream *) stream;
1818   max = (const char *) os->end - (const char *) os->start;
1819
1820   if ((ufile_ptr) offset >= max)
1821     return 0;
1822
1823   count = nbytes;
1824   if (count > max - offset)
1825     count = max - offset;
1826
1827   memcpy (buf, (const char *) os->start + offset, count);
1828   return count;
1829 }
1830
1831 bfd_boolean
1832 spu_elf_open_builtin_lib (bfd **ovl_bfd, const struct _ovl_stream *stream)
1833 {
1834   *ovl_bfd = bfd_openr_iovec ("builtin ovl_mgr",
1835                               "elf32-spu",
1836                               ovl_mgr_open,
1837                               (void *) stream,
1838                               ovl_mgr_pread,
1839                               NULL,
1840                               NULL);
1841   return *ovl_bfd != NULL;
1842 }
1843
1844 static unsigned int
1845 overlay_index (asection *sec)
1846 {
1847   if (sec == NULL
1848       || sec->output_section == bfd_abs_section_ptr)
1849     return 0;
1850   return spu_elf_section_data (sec->output_section)->u.o.ovl_index;
1851 }
1852
1853 /* Define an STT_OBJECT symbol.  */
1854
1855 static struct elf_link_hash_entry *
1856 define_ovtab_symbol (struct spu_link_hash_table *htab, const char *name)
1857 {
1858   struct elf_link_hash_entry *h;
1859
1860   h = elf_link_hash_lookup (&htab->elf, name, TRUE, FALSE, FALSE);
1861   if (h == NULL)
1862     return NULL;
1863
1864   if (h->root.type != bfd_link_hash_defined
1865       || !h->def_regular)
1866     {
1867       h->root.type = bfd_link_hash_defined;
1868       h->root.u.def.section = htab->ovtab;
1869       h->type = STT_OBJECT;
1870       h->ref_regular = 1;
1871       h->def_regular = 1;
1872       h->ref_regular_nonweak = 1;
1873       h->non_elf = 0;
1874     }
1875   else if (h->root.u.def.section->owner != NULL)
1876     {
1877       (*_bfd_error_handler) (_("%B is not allowed to define %s"),
1878                              h->root.u.def.section->owner,
1879                              h->root.root.string);
1880       bfd_set_error (bfd_error_bad_value);
1881       return NULL;
1882     }
1883   else
1884     {
1885       (*_bfd_error_handler) (_("you are not allowed to define %s in a script"),
1886                              h->root.root.string);
1887       bfd_set_error (bfd_error_bad_value);
1888       return NULL;
1889     }
1890
1891   return h;
1892 }
1893
1894 /* Fill in all stubs and the overlay tables.  */
1895
1896 static bfd_boolean
1897 spu_elf_build_stubs (struct bfd_link_info *info)
1898 {
1899   struct spu_link_hash_table *htab = spu_hash_table (info);
1900   struct elf_link_hash_entry *h;
1901   bfd_byte *p;
1902   asection *s;
1903   bfd *obfd;
1904   unsigned int i;
1905
1906   if (htab->num_overlays != 0)
1907     {
1908       for (i = 0; i < 2; i++)
1909         {
1910           h = htab->ovly_entry[i];
1911           if (h != NULL
1912               && (h->root.type == bfd_link_hash_defined
1913                   || h->root.type == bfd_link_hash_defweak)
1914               && h->def_regular)
1915             {
1916               s = h->root.u.def.section->output_section;
1917               if (spu_elf_section_data (s)->u.o.ovl_index)
1918                 {
1919                   (*_bfd_error_handler) (_("%s in overlay section"),
1920                                          h->root.root.string);
1921                   bfd_set_error (bfd_error_bad_value);
1922                   return FALSE;
1923                 }
1924             }
1925         }
1926     }
1927
1928   if (htab->stub_sec != NULL)
1929     {
1930       for (i = 0; i <= htab->num_overlays; i++)
1931         if (htab->stub_sec[i]->size != 0)
1932           {
1933             htab->stub_sec[i]->contents = bfd_zalloc (htab->stub_sec[i]->owner,
1934                                                       htab->stub_sec[i]->size);
1935             if (htab->stub_sec[i]->contents == NULL)
1936               return FALSE;
1937             htab->stub_sec[i]->rawsize = htab->stub_sec[i]->size;
1938             htab->stub_sec[i]->size = 0;
1939           }
1940
1941       /* Fill in all the stubs.  */
1942       process_stubs (info, TRUE);
1943       if (!htab->stub_err)
1944         elf_link_hash_traverse (&htab->elf, build_spuear_stubs, info);
1945
1946       if (htab->stub_err)
1947         {
1948           (*_bfd_error_handler) (_("overlay stub relocation overflow"));
1949           bfd_set_error (bfd_error_bad_value);
1950           return FALSE;
1951         }
1952
1953       for (i = 0; i <= htab->num_overlays; i++)
1954         {
1955           if (htab->stub_sec[i]->size != htab->stub_sec[i]->rawsize)
1956             {
1957               (*_bfd_error_handler)  (_("stubs don't match calculated size"));
1958               bfd_set_error (bfd_error_bad_value);
1959               return FALSE;
1960             }
1961           htab->stub_sec[i]->rawsize = 0;
1962         }
1963     }
1964
1965   if (htab->ovtab == NULL || htab->ovtab->size == 0)
1966     return TRUE;
1967
1968   htab->ovtab->contents = bfd_zalloc (htab->ovtab->owner, htab->ovtab->size);
1969   if (htab->ovtab->contents == NULL)
1970     return FALSE;
1971
1972   p = htab->ovtab->contents;
1973   if (htab->params->ovly_flavour == ovly_soft_icache)
1974     {
1975       bfd_vma off;
1976
1977       h = define_ovtab_symbol (htab, "__icache_tag_array");
1978       if (h == NULL)
1979         return FALSE;
1980       h->root.u.def.value = 0;
1981       h->size = 16 << htab->num_lines_log2;
1982       off = h->size;
1983
1984       h = define_ovtab_symbol (htab, "__icache_tag_array_size");
1985       if (h == NULL)
1986         return FALSE;
1987       h->root.u.def.value = 16 << htab->num_lines_log2;
1988       h->root.u.def.section = bfd_abs_section_ptr;
1989
1990       h = define_ovtab_symbol (htab, "__icache_rewrite_to");
1991       if (h == NULL)
1992         return FALSE;
1993       h->root.u.def.value = off;
1994       h->size = 16 << htab->num_lines_log2;
1995       off += h->size;
1996
1997       h = define_ovtab_symbol (htab, "__icache_rewrite_to_size");
1998       if (h == NULL)
1999         return FALSE;
2000       h->root.u.def.value = 16 << htab->num_lines_log2;
2001       h->root.u.def.section = bfd_abs_section_ptr;
2002
2003       h = define_ovtab_symbol (htab, "__icache_rewrite_from");
2004       if (h == NULL)
2005         return FALSE;
2006       h->root.u.def.value = off;
2007       h->size = 16 << (htab->fromelem_size_log2 + htab->num_lines_log2);
2008       off += h->size;
2009
2010       h = define_ovtab_symbol (htab, "__icache_rewrite_from_size");
2011       if (h == NULL)
2012         return FALSE;
2013       h->root.u.def.value = 16 << (htab->fromelem_size_log2
2014                                    + htab->num_lines_log2);
2015       h->root.u.def.section = bfd_abs_section_ptr;
2016
2017       h = define_ovtab_symbol (htab, "__icache_log2_fromelemsize");
2018       if (h == NULL)
2019         return FALSE;
2020       h->root.u.def.value = htab->fromelem_size_log2;
2021       h->root.u.def.section = bfd_abs_section_ptr;
2022
2023       h = define_ovtab_symbol (htab, "__icache_base");
2024       if (h == NULL)
2025         return FALSE;
2026       h->root.u.def.value = htab->ovl_sec[0]->vma;
2027       h->root.u.def.section = bfd_abs_section_ptr;
2028       h->size = htab->num_buf << htab->line_size_log2;
2029
2030       h = define_ovtab_symbol (htab, "__icache_linesize");
2031       if (h == NULL)
2032         return FALSE;
2033       h->root.u.def.value = 1 << htab->line_size_log2;
2034       h->root.u.def.section = bfd_abs_section_ptr;
2035
2036       h = define_ovtab_symbol (htab, "__icache_log2_linesize");
2037       if (h == NULL)
2038         return FALSE;
2039       h->root.u.def.value = htab->line_size_log2;
2040       h->root.u.def.section = bfd_abs_section_ptr;
2041
2042       h = define_ovtab_symbol (htab, "__icache_neg_log2_linesize");
2043       if (h == NULL)
2044         return FALSE;
2045       h->root.u.def.value = -htab->line_size_log2;
2046       h->root.u.def.section = bfd_abs_section_ptr;
2047
2048       h = define_ovtab_symbol (htab, "__icache_cachesize");
2049       if (h == NULL)
2050         return FALSE;
2051       h->root.u.def.value = 1 << (htab->num_lines_log2 + htab->line_size_log2);
2052       h->root.u.def.section = bfd_abs_section_ptr;
2053
2054       h = define_ovtab_symbol (htab, "__icache_log2_cachesize");
2055       if (h == NULL)
2056         return FALSE;
2057       h->root.u.def.value = htab->num_lines_log2 + htab->line_size_log2;
2058       h->root.u.def.section = bfd_abs_section_ptr;
2059
2060       h = define_ovtab_symbol (htab, "__icache_neg_log2_cachesize");
2061       if (h == NULL)
2062         return FALSE;
2063       h->root.u.def.value = -(htab->num_lines_log2 + htab->line_size_log2);
2064       h->root.u.def.section = bfd_abs_section_ptr;
2065
2066       if (htab->init != NULL && htab->init->size != 0)
2067         {
2068           htab->init->contents = bfd_zalloc (htab->init->owner,
2069                                              htab->init->size);
2070           if (htab->init->contents == NULL)
2071             return FALSE;
2072
2073           h = define_ovtab_symbol (htab, "__icache_fileoff");
2074           if (h == NULL)
2075             return FALSE;
2076           h->root.u.def.value = 0;
2077           h->root.u.def.section = htab->init;
2078           h->size = 8;
2079         }
2080     }
2081   else
2082     {
2083       /* Write out _ovly_table.  */
2084       /* set low bit of .size to mark non-overlay area as present.  */
2085       p[7] = 1;
2086       obfd = htab->ovtab->output_section->owner;
2087       for (s = obfd->sections; s != NULL; s = s->next)
2088         {
2089           unsigned int ovl_index = spu_elf_section_data (s)->u.o.ovl_index;
2090
2091           if (ovl_index != 0)
2092             {
2093               unsigned long off = ovl_index * 16;
2094               unsigned int ovl_buf = spu_elf_section_data (s)->u.o.ovl_buf;
2095
2096               bfd_put_32 (htab->ovtab->owner, s->vma, p + off);
2097               bfd_put_32 (htab->ovtab->owner, (s->size + 15) & -16,
2098                           p + off + 4);
2099               /* file_off written later in spu_elf_modify_program_headers.  */
2100               bfd_put_32 (htab->ovtab->owner, ovl_buf, p + off + 12);
2101             }
2102         }
2103
2104       h = define_ovtab_symbol (htab, "_ovly_table");
2105       if (h == NULL)
2106         return FALSE;
2107       h->root.u.def.value = 16;
2108       h->size = htab->num_overlays * 16;
2109
2110       h = define_ovtab_symbol (htab, "_ovly_table_end");
2111       if (h == NULL)
2112         return FALSE;
2113       h->root.u.def.value = htab->num_overlays * 16 + 16;
2114       h->size = 0;
2115
2116       h = define_ovtab_symbol (htab, "_ovly_buf_table");
2117       if (h == NULL)
2118         return FALSE;
2119       h->root.u.def.value = htab->num_overlays * 16 + 16;
2120       h->size = htab->num_buf * 4;
2121
2122       h = define_ovtab_symbol (htab, "_ovly_buf_table_end");
2123       if (h == NULL)
2124         return FALSE;
2125       h->root.u.def.value = htab->num_overlays * 16 + 16 + htab->num_buf * 4;
2126       h->size = 0;
2127     }
2128
2129   h = define_ovtab_symbol (htab, "_EAR_");
2130   if (h == NULL)
2131     return FALSE;
2132   h->root.u.def.section = htab->toe;
2133   h->root.u.def.value = 0;
2134   h->size = 16;
2135
2136   return TRUE;
2137 }
2138
2139 /* Check that all loadable section VMAs lie in the range
2140    LO .. HI inclusive, and stash some parameters for --auto-overlay.  */
2141
2142 asection *
2143 spu_elf_check_vma (struct bfd_link_info *info)
2144 {
2145   struct elf_segment_map *m;
2146   unsigned int i;
2147   struct spu_link_hash_table *htab = spu_hash_table (info);
2148   bfd *abfd = info->output_bfd;
2149   bfd_vma hi = htab->params->local_store_hi;
2150   bfd_vma lo = htab->params->local_store_lo;
2151
2152   htab->local_store = hi + 1 - lo;
2153
2154   for (m = elf_seg_map (abfd); m != NULL; m = m->next)
2155     if (m->p_type == PT_LOAD)
2156       for (i = 0; i < m->count; i++)
2157         if (m->sections[i]->size != 0
2158             && (m->sections[i]->vma < lo
2159                 || m->sections[i]->vma > hi
2160                 || m->sections[i]->vma + m->sections[i]->size - 1 > hi))
2161           return m->sections[i];
2162
2163   return NULL;
2164 }
2165
2166 /* OFFSET in SEC (presumably) is the beginning of a function prologue.
2167    Search for stack adjusting insns, and return the sp delta.
2168    If a store of lr is found save the instruction offset to *LR_STORE.
2169    If a stack adjusting instruction is found, save that offset to
2170    *SP_ADJUST.  */
2171
2172 static int
2173 find_function_stack_adjust (asection *sec,
2174                             bfd_vma offset,
2175                             bfd_vma *lr_store,
2176                             bfd_vma *sp_adjust)
2177 {
2178   int reg[128];
2179
2180   memset (reg, 0, sizeof (reg));
2181   for ( ; offset + 4 <= sec->size; offset += 4)
2182     {
2183       unsigned char buf[4];
2184       int rt, ra;
2185       int imm;
2186
2187       /* Assume no relocs on stack adjusing insns.  */
2188       if (!bfd_get_section_contents (sec->owner, sec, buf, offset, 4))
2189         break;
2190
2191       rt = buf[3] & 0x7f;
2192       ra = ((buf[2] & 0x3f) << 1) | (buf[3] >> 7);
2193
2194       if (buf[0] == 0x24 /* stqd */)
2195         {
2196           if (rt == 0 /* lr */ && ra == 1 /* sp */)
2197             *lr_store = offset;
2198           continue;
2199         }
2200
2201       /* Partly decoded immediate field.  */
2202       imm = (buf[1] << 9) | (buf[2] << 1) | (buf[3] >> 7);
2203
2204       if (buf[0] == 0x1c /* ai */)
2205         {
2206           imm >>= 7;
2207           imm = (imm ^ 0x200) - 0x200;
2208           reg[rt] = reg[ra] + imm;
2209
2210           if (rt == 1 /* sp */)
2211             {
2212               if (reg[rt] > 0)
2213                 break;
2214               *sp_adjust = offset;
2215               return reg[rt];
2216             }
2217         }
2218       else if (buf[0] == 0x18 && (buf[1] & 0xe0) == 0 /* a */)
2219         {
2220           int rb = ((buf[1] & 0x1f) << 2) | ((buf[2] & 0xc0) >> 6);
2221
2222           reg[rt] = reg[ra] + reg[rb];
2223           if (rt == 1)
2224             {
2225               if (reg[rt] > 0)
2226                 break;
2227               *sp_adjust = offset;
2228               return reg[rt];
2229             }
2230         }
2231       else if (buf[0] == 0x08 && (buf[1] & 0xe0) == 0 /* sf */)
2232         {
2233           int rb = ((buf[1] & 0x1f) << 2) | ((buf[2] & 0xc0) >> 6);
2234
2235           reg[rt] = reg[rb] - reg[ra];
2236           if (rt == 1)
2237             {
2238               if (reg[rt] > 0)
2239                 break;
2240               *sp_adjust = offset;
2241               return reg[rt];
2242             }
2243         }
2244       else if ((buf[0] & 0xfc) == 0x40 /* il, ilh, ilhu, ila */)
2245         {
2246           if (buf[0] >= 0x42 /* ila */)
2247             imm |= (buf[0] & 1) << 17;
2248           else
2249             {
2250               imm &= 0xffff;
2251
2252               if (buf[0] == 0x40 /* il */)
2253                 {
2254                   if ((buf[1] & 0x80) == 0)
2255                     continue;
2256                   imm = (imm ^ 0x8000) - 0x8000;
2257                 }
2258               else if ((buf[1] & 0x80) == 0 /* ilhu */)
2259                 imm <<= 16;
2260             }
2261           reg[rt] = imm;
2262           continue;
2263         }
2264       else if (buf[0] == 0x60 && (buf[1] & 0x80) != 0 /* iohl */)
2265         {
2266           reg[rt] |= imm & 0xffff;
2267           continue;
2268         }
2269       else if (buf[0] == 0x04 /* ori */)
2270         {
2271           imm >>= 7;
2272           imm = (imm ^ 0x200) - 0x200;
2273           reg[rt] = reg[ra] | imm;
2274           continue;
2275         }
2276       else if (buf[0] == 0x32 && (buf[1] & 0x80) != 0 /* fsmbi */)
2277         {
2278           reg[rt] = (  ((imm & 0x8000) ? 0xff000000 : 0)
2279                      | ((imm & 0x4000) ? 0x00ff0000 : 0)
2280                      | ((imm & 0x2000) ? 0x0000ff00 : 0)
2281                      | ((imm & 0x1000) ? 0x000000ff : 0));
2282           continue;
2283         }
2284       else if (buf[0] == 0x16 /* andbi */)
2285         {
2286           imm >>= 7;
2287           imm &= 0xff;
2288           imm |= imm << 8;
2289           imm |= imm << 16;
2290           reg[rt] = reg[ra] & imm;
2291           continue;
2292         }
2293       else if (buf[0] == 0x33 && imm == 1 /* brsl .+4 */)
2294         {
2295           /* Used in pic reg load.  Say rt is trashed.  Won't be used
2296              in stack adjust, but we need to continue past this branch.  */
2297           reg[rt] = 0;
2298           continue;
2299         }
2300       else if (is_branch (buf) || is_indirect_branch (buf))
2301         /* If we hit a branch then we must be out of the prologue.  */
2302         break;
2303     }
2304
2305   return 0;
2306 }
2307
2308 /* qsort predicate to sort symbols by section and value.  */
2309
2310 static Elf_Internal_Sym *sort_syms_syms;
2311 static asection **sort_syms_psecs;
2312
2313 static int
2314 sort_syms (const void *a, const void *b)
2315 {
2316   Elf_Internal_Sym *const *s1 = a;
2317   Elf_Internal_Sym *const *s2 = b;
2318   asection *sec1,*sec2;
2319   bfd_signed_vma delta;
2320
2321   sec1 = sort_syms_psecs[*s1 - sort_syms_syms];
2322   sec2 = sort_syms_psecs[*s2 - sort_syms_syms];
2323
2324   if (sec1 != sec2)
2325     return sec1->index - sec2->index;
2326
2327   delta = (*s1)->st_value - (*s2)->st_value;
2328   if (delta != 0)
2329     return delta < 0 ? -1 : 1;
2330
2331   delta = (*s2)->st_size - (*s1)->st_size;
2332   if (delta != 0)
2333     return delta < 0 ? -1 : 1;
2334
2335   return *s1 < *s2 ? -1 : 1;
2336 }
2337
2338 /* Allocate a struct spu_elf_stack_info with MAX_FUN struct function_info
2339    entries for section SEC.  */
2340
2341 static struct spu_elf_stack_info *
2342 alloc_stack_info (asection *sec, int max_fun)
2343 {
2344   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
2345   bfd_size_type amt;
2346
2347   amt = sizeof (struct spu_elf_stack_info);
2348   amt += (max_fun - 1) * sizeof (struct function_info);
2349   sec_data->u.i.stack_info = bfd_zmalloc (amt);
2350   if (sec_data->u.i.stack_info != NULL)
2351     sec_data->u.i.stack_info->max_fun = max_fun;
2352   return sec_data->u.i.stack_info;
2353 }
2354
2355 /* Add a new struct function_info describing a (part of a) function
2356    starting at SYM_H.  Keep the array sorted by address.  */
2357
2358 static struct function_info *
2359 maybe_insert_function (asection *sec,
2360                        void *sym_h,
2361                        bfd_boolean global,
2362                        bfd_boolean is_func)
2363 {
2364   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
2365   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
2366   int i;
2367   bfd_vma off, size;
2368
2369   if (sinfo == NULL)
2370     {
2371       sinfo = alloc_stack_info (sec, 20);
2372       if (sinfo == NULL)
2373         return NULL;
2374     }
2375
2376   if (!global)
2377     {
2378       Elf_Internal_Sym *sym = sym_h;
2379       off = sym->st_value;
2380       size = sym->st_size;
2381     }
2382   else
2383     {
2384       struct elf_link_hash_entry *h = sym_h;
2385       off = h->root.u.def.value;
2386       size = h->size;
2387     }
2388
2389   for (i = sinfo->num_fun; --i >= 0; )
2390     if (sinfo->fun[i].lo <= off)
2391       break;
2392
2393   if (i >= 0)
2394     {
2395       /* Don't add another entry for an alias, but do update some
2396          info.  */
2397       if (sinfo->fun[i].lo == off)
2398         {
2399           /* Prefer globals over local syms.  */
2400           if (global && !sinfo->fun[i].global)
2401             {
2402               sinfo->fun[i].global = TRUE;
2403               sinfo->fun[i].u.h = sym_h;
2404             }
2405           if (is_func)
2406             sinfo->fun[i].is_func = TRUE;
2407           return &sinfo->fun[i];
2408         }
2409       /* Ignore a zero-size symbol inside an existing function.  */
2410       else if (sinfo->fun[i].hi > off && size == 0)
2411         return &sinfo->fun[i];
2412     }
2413
2414   if (sinfo->num_fun >= sinfo->max_fun)
2415     {
2416       bfd_size_type amt = sizeof (struct spu_elf_stack_info);
2417       bfd_size_type old = amt;
2418
2419       old += (sinfo->max_fun - 1) * sizeof (struct function_info);
2420       sinfo->max_fun += 20 + (sinfo->max_fun >> 1);
2421       amt += (sinfo->max_fun - 1) * sizeof (struct function_info);
2422       sinfo = bfd_realloc (sinfo, amt);
2423       if (sinfo == NULL)
2424         return NULL;
2425       memset ((char *) sinfo + old, 0, amt - old);
2426       sec_data->u.i.stack_info = sinfo;
2427     }
2428
2429   if (++i < sinfo->num_fun)
2430     memmove (&sinfo->fun[i + 1], &sinfo->fun[i],
2431              (sinfo->num_fun - i) * sizeof (sinfo->fun[i]));
2432   sinfo->fun[i].is_func = is_func;
2433   sinfo->fun[i].global = global;
2434   sinfo->fun[i].sec = sec;
2435   if (global)
2436     sinfo->fun[i].u.h = sym_h;
2437   else
2438     sinfo->fun[i].u.sym = sym_h;
2439   sinfo->fun[i].lo = off;
2440   sinfo->fun[i].hi = off + size;
2441   sinfo->fun[i].lr_store = -1;
2442   sinfo->fun[i].sp_adjust = -1;
2443   sinfo->fun[i].stack = -find_function_stack_adjust (sec, off,
2444                                                      &sinfo->fun[i].lr_store,
2445                                                      &sinfo->fun[i].sp_adjust);
2446   sinfo->num_fun += 1;
2447   return &sinfo->fun[i];
2448 }
2449
2450 /* Return the name of FUN.  */
2451
2452 static const char *
2453 func_name (struct function_info *fun)
2454 {
2455   asection *sec;
2456   bfd *ibfd;
2457   Elf_Internal_Shdr *symtab_hdr;
2458
2459   while (fun->start != NULL)
2460     fun = fun->start;
2461
2462   if (fun->global)
2463     return fun->u.h->root.root.string;
2464
2465   sec = fun->sec;
2466   if (fun->u.sym->st_name == 0)
2467     {
2468       size_t len = strlen (sec->name);
2469       char *name = bfd_malloc (len + 10);
2470       if (name == NULL)
2471         return "(null)";
2472       sprintf (name, "%s+%lx", sec->name,
2473                (unsigned long) fun->u.sym->st_value & 0xffffffff);
2474       return name;
2475     }
2476   ibfd = sec->owner;
2477   symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
2478   return bfd_elf_sym_name (ibfd, symtab_hdr, fun->u.sym, sec);
2479 }
2480
2481 /* Read the instruction at OFF in SEC.  Return true iff the instruction
2482    is a nop, lnop, or stop 0 (all zero insn).  */
2483
2484 static bfd_boolean
2485 is_nop (asection *sec, bfd_vma off)
2486 {
2487   unsigned char insn[4];
2488
2489   if (off + 4 > sec->size
2490       || !bfd_get_section_contents (sec->owner, sec, insn, off, 4))
2491     return FALSE;
2492   if ((insn[0] & 0xbf) == 0 && (insn[1] & 0xe0) == 0x20)
2493     return TRUE;
2494   if (insn[0] == 0 && insn[1] == 0 && insn[2] == 0 && insn[3] == 0)
2495     return TRUE;
2496   return FALSE;
2497 }
2498
2499 /* Extend the range of FUN to cover nop padding up to LIMIT.
2500    Return TRUE iff some instruction other than a NOP was found.  */
2501
2502 static bfd_boolean
2503 insns_at_end (struct function_info *fun, bfd_vma limit)
2504 {
2505   bfd_vma off = (fun->hi + 3) & -4;
2506
2507   while (off < limit && is_nop (fun->sec, off))
2508     off += 4;
2509   if (off < limit)
2510     {
2511       fun->hi = off;
2512       return TRUE;
2513     }
2514   fun->hi = limit;
2515   return FALSE;
2516 }
2517
2518 /* Check and fix overlapping function ranges.  Return TRUE iff there
2519    are gaps in the current info we have about functions in SEC.  */
2520
2521 static bfd_boolean
2522 check_function_ranges (asection *sec, struct bfd_link_info *info)
2523 {
2524   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
2525   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
2526   int i;
2527   bfd_boolean gaps = FALSE;
2528
2529   if (sinfo == NULL)
2530     return FALSE;
2531
2532   for (i = 1; i < sinfo->num_fun; i++)
2533     if (sinfo->fun[i - 1].hi > sinfo->fun[i].lo)
2534       {
2535         /* Fix overlapping symbols.  */
2536         const char *f1 = func_name (&sinfo->fun[i - 1]);
2537         const char *f2 = func_name (&sinfo->fun[i]);
2538
2539         info->callbacks->einfo (_("warning: %s overlaps %s\n"), f1, f2);
2540         sinfo->fun[i - 1].hi = sinfo->fun[i].lo;
2541       }
2542     else if (insns_at_end (&sinfo->fun[i - 1], sinfo->fun[i].lo))
2543       gaps = TRUE;
2544
2545   if (sinfo->num_fun == 0)
2546     gaps = TRUE;
2547   else
2548     {
2549       if (sinfo->fun[0].lo != 0)
2550         gaps = TRUE;
2551       if (sinfo->fun[sinfo->num_fun - 1].hi > sec->size)
2552         {
2553           const char *f1 = func_name (&sinfo->fun[sinfo->num_fun - 1]);
2554
2555           info->callbacks->einfo (_("warning: %s exceeds section size\n"), f1);
2556           sinfo->fun[sinfo->num_fun - 1].hi = sec->size;
2557         }
2558       else if (insns_at_end (&sinfo->fun[sinfo->num_fun - 1], sec->size))
2559         gaps = TRUE;
2560     }
2561   return gaps;
2562 }
2563
2564 /* Search current function info for a function that contains address
2565    OFFSET in section SEC.  */
2566
2567 static struct function_info *
2568 find_function (asection *sec, bfd_vma offset, struct bfd_link_info *info)
2569 {
2570   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
2571   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
2572   int lo, hi, mid;
2573
2574   lo = 0;
2575   hi = sinfo->num_fun;
2576   while (lo < hi)
2577     {
2578       mid = (lo + hi) / 2;
2579       if (offset < sinfo->fun[mid].lo)
2580         hi = mid;
2581       else if (offset >= sinfo->fun[mid].hi)
2582         lo = mid + 1;
2583       else
2584         return &sinfo->fun[mid];
2585     }
2586   info->callbacks->einfo (_("%A:0x%v not found in function table\n"),
2587                           sec, offset);
2588   bfd_set_error (bfd_error_bad_value);
2589   return NULL;
2590 }
2591
2592 /* Add CALLEE to CALLER call list if not already present.  Return TRUE
2593    if CALLEE was new.  If this function return FALSE, CALLEE should
2594    be freed.  */
2595
2596 static bfd_boolean
2597 insert_callee (struct function_info *caller, struct call_info *callee)
2598 {
2599   struct call_info **pp, *p;
2600
2601   for (pp = &caller->call_list; (p = *pp) != NULL; pp = &p->next)
2602     if (p->fun == callee->fun)
2603       {
2604         /* Tail calls use less stack than normal calls.  Retain entry
2605            for normal call over one for tail call.  */
2606         p->is_tail &= callee->is_tail;
2607         if (!p->is_tail)
2608           {
2609             p->fun->start = NULL;
2610             p->fun->is_func = TRUE;
2611           }
2612         p->count += callee->count;
2613         /* Reorder list so most recent call is first.  */
2614         *pp = p->next;
2615         p->next = caller->call_list;
2616         caller->call_list = p;
2617         return FALSE;
2618       }
2619   callee->next = caller->call_list;
2620   caller->call_list = callee;
2621   return TRUE;
2622 }
2623
2624 /* Copy CALL and insert the copy into CALLER.  */
2625
2626 static bfd_boolean
2627 copy_callee (struct function_info *caller, const struct call_info *call)
2628 {
2629   struct call_info *callee;
2630   callee = bfd_malloc (sizeof (*callee));
2631   if (callee == NULL)
2632     return FALSE;
2633   *callee = *call;
2634   if (!insert_callee (caller, callee))
2635     free (callee);
2636   return TRUE;
2637 }
2638
2639 /* We're only interested in code sections.  Testing SEC_IN_MEMORY excludes
2640    overlay stub sections.  */
2641
2642 static bfd_boolean
2643 interesting_section (asection *s)
2644 {
2645   return (s->output_section != bfd_abs_section_ptr
2646           && ((s->flags & (SEC_ALLOC | SEC_LOAD | SEC_CODE | SEC_IN_MEMORY))
2647               == (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2648           && s->size != 0);
2649 }
2650
2651 /* Rummage through the relocs for SEC, looking for function calls.
2652    If CALL_TREE is true, fill in call graph.  If CALL_TREE is false,
2653    mark destination symbols on calls as being functions.  Also
2654    look at branches, which may be tail calls or go to hot/cold
2655    section part of same function.  */
2656
2657 static bfd_boolean
2658 mark_functions_via_relocs (asection *sec,
2659                            struct bfd_link_info *info,
2660                            int call_tree)
2661 {
2662   Elf_Internal_Rela *internal_relocs, *irelaend, *irela;
2663   Elf_Internal_Shdr *symtab_hdr;
2664   void *psyms;
2665   unsigned int priority = 0;
2666   static bfd_boolean warned;
2667
2668   if (!interesting_section (sec)
2669       || sec->reloc_count == 0)
2670     return TRUE;
2671
2672   internal_relocs = _bfd_elf_link_read_relocs (sec->owner, sec, NULL, NULL,
2673                                                info->keep_memory);
2674   if (internal_relocs == NULL)
2675     return FALSE;
2676
2677   symtab_hdr = &elf_tdata (sec->owner)->symtab_hdr;
2678   psyms = &symtab_hdr->contents;
2679   irela = internal_relocs;
2680   irelaend = irela + sec->reloc_count;
2681   for (; irela < irelaend; irela++)
2682     {
2683       enum elf_spu_reloc_type r_type;
2684       unsigned int r_indx;
2685       asection *sym_sec;
2686       Elf_Internal_Sym *sym;
2687       struct elf_link_hash_entry *h;
2688       bfd_vma val;
2689       bfd_boolean nonbranch, is_call;
2690       struct function_info *caller;
2691       struct call_info *callee;
2692
2693       r_type = ELF32_R_TYPE (irela->r_info);
2694       nonbranch = r_type != R_SPU_REL16 && r_type != R_SPU_ADDR16;
2695
2696       r_indx = ELF32_R_SYM (irela->r_info);
2697       if (!get_sym_h (&h, &sym, &sym_sec, psyms, r_indx, sec->owner))
2698         return FALSE;
2699
2700       if (sym_sec == NULL
2701           || sym_sec->output_section == bfd_abs_section_ptr)
2702         continue;
2703
2704       is_call = FALSE;
2705       if (!nonbranch)
2706         {
2707           unsigned char insn[4];
2708
2709           if (!bfd_get_section_contents (sec->owner, sec, insn,
2710                                          irela->r_offset, 4))
2711             return FALSE;
2712           if (is_branch (insn))
2713             {
2714               is_call = (insn[0] & 0xfd) == 0x31;
2715               priority = insn[1] & 0x0f;
2716               priority <<= 8;
2717               priority |= insn[2];
2718               priority <<= 8;
2719               priority |= insn[3];
2720               priority >>= 7;
2721               if ((sym_sec->flags & (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2722                   != (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2723                 {
2724                   if (!warned)
2725                     info->callbacks->einfo
2726                       (_("%B(%A+0x%v): call to non-code section"
2727                          " %B(%A), analysis incomplete\n"),
2728                        sec->owner, sec, irela->r_offset,
2729                        sym_sec->owner, sym_sec);
2730                   warned = TRUE;
2731                   continue;
2732                 }
2733             }
2734           else
2735             {
2736               nonbranch = TRUE;
2737               if (is_hint (insn))
2738                 continue;
2739             }
2740         }
2741
2742       if (nonbranch)
2743         {
2744           /* For --auto-overlay, count possible stubs we need for
2745              function pointer references.  */
2746           unsigned int sym_type;
2747           if (h)
2748             sym_type = h->type;
2749           else
2750             sym_type = ELF_ST_TYPE (sym->st_info);
2751           if (sym_type == STT_FUNC)
2752             {
2753               if (call_tree && spu_hash_table (info)->params->auto_overlay)
2754                 spu_hash_table (info)->non_ovly_stub += 1;
2755               /* If the symbol type is STT_FUNC then this must be a
2756                  function pointer initialisation.  */
2757               continue;
2758             }
2759           /* Ignore data references.  */
2760           if ((sym_sec->flags & (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2761               != (SEC_ALLOC | SEC_LOAD | SEC_CODE))
2762             continue;
2763           /* Otherwise we probably have a jump table reloc for
2764              a switch statement or some other reference to a
2765              code label.  */
2766         }
2767
2768       if (h)
2769         val = h->root.u.def.value;
2770       else
2771         val = sym->st_value;
2772       val += irela->r_addend;
2773
2774       if (!call_tree)
2775         {
2776           struct function_info *fun;
2777
2778           if (irela->r_addend != 0)
2779             {
2780               Elf_Internal_Sym *fake = bfd_zmalloc (sizeof (*fake));
2781               if (fake == NULL)
2782                 return FALSE;
2783               fake->st_value = val;
2784               fake->st_shndx
2785                 = _bfd_elf_section_from_bfd_section (sym_sec->owner, sym_sec);
2786               sym = fake;
2787             }
2788           if (sym)
2789             fun = maybe_insert_function (sym_sec, sym, FALSE, is_call);
2790           else
2791             fun = maybe_insert_function (sym_sec, h, TRUE, is_call);
2792           if (fun == NULL)
2793             return FALSE;
2794           if (irela->r_addend != 0
2795               && fun->u.sym != sym)
2796             free (sym);
2797           continue;
2798         }
2799
2800       caller = find_function (sec, irela->r_offset, info);
2801       if (caller == NULL)
2802         return FALSE;
2803       callee = bfd_malloc (sizeof *callee);
2804       if (callee == NULL)
2805         return FALSE;
2806
2807       callee->fun = find_function (sym_sec, val, info);
2808       if (callee->fun == NULL)
2809         return FALSE;
2810       callee->is_tail = !is_call;
2811       callee->is_pasted = FALSE;
2812       callee->broken_cycle = FALSE;
2813       callee->priority = priority;
2814       callee->count = nonbranch? 0 : 1;
2815       if (callee->fun->last_caller != sec)
2816         {
2817           callee->fun->last_caller = sec;
2818           callee->fun->call_count += 1;
2819         }
2820       if (!insert_callee (caller, callee))
2821         free (callee);
2822       else if (!is_call
2823                && !callee->fun->is_func
2824                && callee->fun->stack == 0)
2825         {
2826           /* This is either a tail call or a branch from one part of
2827              the function to another, ie. hot/cold section.  If the
2828              destination has been called by some other function then
2829              it is a separate function.  We also assume that functions
2830              are not split across input files.  */
2831           if (sec->owner != sym_sec->owner)
2832             {
2833               callee->fun->start = NULL;
2834               callee->fun->is_func = TRUE;
2835             }
2836           else if (callee->fun->start == NULL)
2837             {
2838               struct function_info *caller_start = caller;
2839               while (caller_start->start)
2840                 caller_start = caller_start->start;
2841
2842               if (caller_start != callee->fun)
2843                 callee->fun->start = caller_start;
2844             }
2845           else
2846             {
2847               struct function_info *callee_start;
2848               struct function_info *caller_start;
2849               callee_start = callee->fun;
2850               while (callee_start->start)
2851                 callee_start = callee_start->start;
2852               caller_start = caller;
2853               while (caller_start->start)
2854                 caller_start = caller_start->start;
2855               if (caller_start != callee_start)
2856                 {
2857                   callee->fun->start = NULL;
2858                   callee->fun->is_func = TRUE;
2859                 }
2860             }
2861         }
2862     }
2863
2864   return TRUE;
2865 }
2866
2867 /* Handle something like .init or .fini, which has a piece of a function.
2868    These sections are pasted together to form a single function.  */
2869
2870 static bfd_boolean
2871 pasted_function (asection *sec)
2872 {
2873   struct bfd_link_order *l;
2874   struct _spu_elf_section_data *sec_data;
2875   struct spu_elf_stack_info *sinfo;
2876   Elf_Internal_Sym *fake;
2877   struct function_info *fun, *fun_start;
2878
2879   fake = bfd_zmalloc (sizeof (*fake));
2880   if (fake == NULL)
2881     return FALSE;
2882   fake->st_value = 0;
2883   fake->st_size = sec->size;
2884   fake->st_shndx
2885     = _bfd_elf_section_from_bfd_section (sec->owner, sec);
2886   fun = maybe_insert_function (sec, fake, FALSE, FALSE);
2887   if (!fun)
2888     return FALSE;
2889
2890   /* Find a function immediately preceding this section.  */
2891   fun_start = NULL;
2892   for (l = sec->output_section->map_head.link_order; l != NULL; l = l->next)
2893     {
2894       if (l->u.indirect.section == sec)
2895         {
2896           if (fun_start != NULL)
2897             {
2898               struct call_info *callee = bfd_malloc (sizeof *callee);
2899               if (callee == NULL)
2900                 return FALSE;
2901
2902               fun->start = fun_start;
2903               callee->fun = fun;
2904               callee->is_tail = TRUE;
2905               callee->is_pasted = TRUE;
2906               callee->broken_cycle = FALSE;
2907               callee->priority = 0;
2908               callee->count = 1;
2909               if (!insert_callee (fun_start, callee))
2910                 free (callee);
2911               return TRUE;
2912             }
2913           break;
2914         }
2915       if (l->type == bfd_indirect_link_order
2916           && (sec_data = spu_elf_section_data (l->u.indirect.section)) != NULL
2917           && (sinfo = sec_data->u.i.stack_info) != NULL
2918           && sinfo->num_fun != 0)
2919         fun_start = &sinfo->fun[sinfo->num_fun - 1];
2920     }
2921
2922   /* Don't return an error if we did not find a function preceding this
2923      section.  The section may have incorrect flags.  */
2924   return TRUE;
2925 }
2926
2927 /* Map address ranges in code sections to functions.  */
2928
2929 static bfd_boolean
2930 discover_functions (struct bfd_link_info *info)
2931 {
2932   bfd *ibfd;
2933   int bfd_idx;
2934   Elf_Internal_Sym ***psym_arr;
2935   asection ***sec_arr;
2936   bfd_boolean gaps = FALSE;
2937
2938   bfd_idx = 0;
2939   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
2940     bfd_idx++;
2941
2942   psym_arr = bfd_zmalloc (bfd_idx * sizeof (*psym_arr));
2943   if (psym_arr == NULL)
2944     return FALSE;
2945   sec_arr = bfd_zmalloc (bfd_idx * sizeof (*sec_arr));
2946   if (sec_arr == NULL)
2947     return FALSE;
2948
2949   for (ibfd = info->input_bfds, bfd_idx = 0;
2950        ibfd != NULL;
2951        ibfd = ibfd->link.next, bfd_idx++)
2952     {
2953       extern const bfd_target spu_elf32_vec;
2954       Elf_Internal_Shdr *symtab_hdr;
2955       asection *sec;
2956       size_t symcount;
2957       Elf_Internal_Sym *syms, *sy, **psyms, **psy;
2958       asection **psecs, **p;
2959
2960       if (ibfd->xvec != &spu_elf32_vec)
2961         continue;
2962
2963       /* Read all the symbols.  */
2964       symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
2965       symcount = symtab_hdr->sh_size / symtab_hdr->sh_entsize;
2966       if (symcount == 0)
2967         {
2968           if (!gaps)
2969             for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
2970               if (interesting_section (sec))
2971                 {
2972                   gaps = TRUE;
2973                   break;
2974                 }
2975           continue;
2976         }
2977
2978       if (symtab_hdr->contents != NULL)
2979         {
2980           /* Don't use cached symbols since the generic ELF linker
2981              code only reads local symbols, and we need globals too.  */
2982           free (symtab_hdr->contents);
2983           symtab_hdr->contents = NULL;
2984         }
2985       syms = bfd_elf_get_elf_syms (ibfd, symtab_hdr, symcount, 0,
2986                                    NULL, NULL, NULL);
2987       symtab_hdr->contents = (void *) syms;
2988       if (syms == NULL)
2989         return FALSE;
2990
2991       /* Select defined function symbols that are going to be output.  */
2992       psyms = bfd_malloc ((symcount + 1) * sizeof (*psyms));
2993       if (psyms == NULL)
2994         return FALSE;
2995       psym_arr[bfd_idx] = psyms;
2996       psecs = bfd_malloc (symcount * sizeof (*psecs));
2997       if (psecs == NULL)
2998         return FALSE;
2999       sec_arr[bfd_idx] = psecs;
3000       for (psy = psyms, p = psecs, sy = syms; sy < syms + symcount; ++p, ++sy)
3001         if (ELF_ST_TYPE (sy->st_info) == STT_NOTYPE
3002             || ELF_ST_TYPE (sy->st_info) == STT_FUNC)
3003           {
3004             asection *s;
3005
3006             *p = s = bfd_section_from_elf_index (ibfd, sy->st_shndx);
3007             if (s != NULL && interesting_section (s))
3008               *psy++ = sy;
3009           }
3010       symcount = psy - psyms;
3011       *psy = NULL;
3012
3013       /* Sort them by section and offset within section.  */
3014       sort_syms_syms = syms;
3015       sort_syms_psecs = psecs;
3016       qsort (psyms, symcount, sizeof (*psyms), sort_syms);
3017
3018       /* Now inspect the function symbols.  */
3019       for (psy = psyms; psy < psyms + symcount; )
3020         {
3021           asection *s = psecs[*psy - syms];
3022           Elf_Internal_Sym **psy2;
3023
3024           for (psy2 = psy; ++psy2 < psyms + symcount; )
3025             if (psecs[*psy2 - syms] != s)
3026               break;
3027
3028           if (!alloc_stack_info (s, psy2 - psy))
3029             return FALSE;
3030           psy = psy2;
3031         }
3032
3033       /* First install info about properly typed and sized functions.
3034          In an ideal world this will cover all code sections, except
3035          when partitioning functions into hot and cold sections,
3036          and the horrible pasted together .init and .fini functions.  */
3037       for (psy = psyms; psy < psyms + symcount; ++psy)
3038         {
3039           sy = *psy;
3040           if (ELF_ST_TYPE (sy->st_info) == STT_FUNC)
3041             {
3042               asection *s = psecs[sy - syms];
3043               if (!maybe_insert_function (s, sy, FALSE, TRUE))
3044                 return FALSE;
3045             }
3046         }
3047
3048       for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
3049         if (interesting_section (sec))
3050           gaps |= check_function_ranges (sec, info);
3051     }
3052
3053   if (gaps)
3054     {
3055       /* See if we can discover more function symbols by looking at
3056          relocations.  */
3057       for (ibfd = info->input_bfds, bfd_idx = 0;
3058            ibfd != NULL;
3059            ibfd = ibfd->link.next, bfd_idx++)
3060         {
3061           asection *sec;
3062
3063           if (psym_arr[bfd_idx] == NULL)
3064             continue;
3065
3066           for (sec = ibfd->sections; sec != NULL; sec = sec->next)
3067             if (!mark_functions_via_relocs (sec, info, FALSE))
3068               return FALSE;
3069         }
3070
3071       for (ibfd = info->input_bfds, bfd_idx = 0;
3072            ibfd != NULL;
3073            ibfd = ibfd->link.next, bfd_idx++)
3074         {
3075           Elf_Internal_Shdr *symtab_hdr;
3076           asection *sec;
3077           Elf_Internal_Sym *syms, *sy, **psyms, **psy;
3078           asection **psecs;
3079
3080           if ((psyms = psym_arr[bfd_idx]) == NULL)
3081             continue;
3082
3083           psecs = sec_arr[bfd_idx];
3084
3085           symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;
3086           syms = (Elf_Internal_Sym *) symtab_hdr->contents;
3087
3088           gaps = FALSE;
3089           for (sec = ibfd->sections; sec != NULL && !gaps; sec = sec->next)
3090             if (interesting_section (sec))
3091               gaps |= check_function_ranges (sec, info);
3092           if (!gaps)
3093             continue;
3094
3095           /* Finally, install all globals.  */
3096           for (psy = psyms; (sy = *psy) != NULL; ++psy)
3097             {
3098               asection *s;
3099
3100               s = psecs[sy - syms];
3101
3102               /* Global syms might be improperly typed functions.  */
3103               if (ELF_ST_TYPE (sy->st_info) != STT_FUNC
3104                   && ELF_ST_BIND (sy->st_info) == STB_GLOBAL)
3105                 {
3106                   if (!maybe_insert_function (s, sy, FALSE, FALSE))
3107                     return FALSE;
3108                 }
3109             }
3110         }
3111
3112       for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
3113         {
3114           extern const bfd_target spu_elf32_vec;
3115           asection *sec;
3116
3117           if (ibfd->xvec != &spu_elf32_vec)
3118             continue;
3119
3120           /* Some of the symbols we've installed as marking the
3121              beginning of functions may have a size of zero.  Extend
3122              the range of such functions to the beginning of the
3123              next symbol of interest.  */
3124           for (sec = ibfd->sections; sec != NULL; sec = sec->next)
3125             if (interesting_section (sec))
3126               {
3127                 struct _spu_elf_section_data *sec_data;
3128                 struct spu_elf_stack_info *sinfo;
3129
3130                 sec_data = spu_elf_section_data (sec);
3131                 sinfo = sec_data->u.i.stack_info;
3132                 if (sinfo != NULL && sinfo->num_fun != 0)
3133                   {
3134                     int fun_idx;
3135                     bfd_vma hi = sec->size;
3136
3137                     for (fun_idx = sinfo->num_fun; --fun_idx >= 0; )
3138                       {
3139                         sinfo->fun[fun_idx].hi = hi;
3140                         hi = sinfo->fun[fun_idx].lo;
3141                       }
3142
3143                     sinfo->fun[0].lo = 0;
3144                   }
3145                 /* No symbols in this section.  Must be .init or .fini
3146                    or something similar.  */
3147                 else if (!pasted_function (sec))
3148                   return FALSE;
3149               }
3150         }
3151     }
3152
3153   for (ibfd = info->input_bfds, bfd_idx = 0;
3154        ibfd != NULL;
3155        ibfd = ibfd->link.next, bfd_idx++)
3156     {
3157       if (psym_arr[bfd_idx] == NULL)
3158         continue;
3159
3160       free (psym_arr[bfd_idx]);
3161       free (sec_arr[bfd_idx]);
3162     }
3163
3164   free (psym_arr);
3165   free (sec_arr);
3166
3167   return TRUE;
3168 }
3169
3170 /* Iterate over all function_info we have collected, calling DOIT on
3171    each node if ROOT_ONLY is false.  Only call DOIT on root nodes
3172    if ROOT_ONLY.  */
3173
3174 static bfd_boolean
3175 for_each_node (bfd_boolean (*doit) (struct function_info *,
3176                                     struct bfd_link_info *,
3177                                     void *),
3178                struct bfd_link_info *info,
3179                void *param,
3180                int root_only)
3181 {
3182   bfd *ibfd;
3183
3184   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
3185     {
3186       extern const bfd_target spu_elf32_vec;
3187       asection *sec;
3188
3189       if (ibfd->xvec != &spu_elf32_vec)
3190         continue;
3191
3192       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
3193         {
3194           struct _spu_elf_section_data *sec_data;
3195           struct spu_elf_stack_info *sinfo;
3196
3197           if ((sec_data = spu_elf_section_data (sec)) != NULL
3198               && (sinfo = sec_data->u.i.stack_info) != NULL)
3199             {
3200               int i;
3201               for (i = 0; i < sinfo->num_fun; ++i)
3202                 if (!root_only || !sinfo->fun[i].non_root)
3203                   if (!doit (&sinfo->fun[i], info, param))
3204                     return FALSE;
3205             }
3206         }
3207     }
3208   return TRUE;
3209 }
3210
3211 /* Transfer call info attached to struct function_info entries for
3212    all of a given function's sections to the first entry.  */
3213
3214 static bfd_boolean
3215 transfer_calls (struct function_info *fun,
3216                 struct bfd_link_info *info ATTRIBUTE_UNUSED,
3217                 void *param ATTRIBUTE_UNUSED)
3218 {
3219   struct function_info *start = fun->start;
3220
3221   if (start != NULL)
3222     {
3223       struct call_info *call, *call_next;
3224
3225       while (start->start != NULL)
3226         start = start->start;
3227       for (call = fun->call_list; call != NULL; call = call_next)
3228         {
3229           call_next = call->next;
3230           if (!insert_callee (start, call))
3231             free (call);
3232         }
3233       fun->call_list = NULL;
3234     }
3235   return TRUE;
3236 }
3237
3238 /* Mark nodes in the call graph that are called by some other node.  */
3239
3240 static bfd_boolean
3241 mark_non_root (struct function_info *fun,
3242                struct bfd_link_info *info ATTRIBUTE_UNUSED,
3243                void *param ATTRIBUTE_UNUSED)
3244 {
3245   struct call_info *call;
3246
3247   if (fun->visit1)
3248     return TRUE;
3249   fun->visit1 = TRUE;
3250   for (call = fun->call_list; call; call = call->next)
3251     {
3252       call->fun->non_root = TRUE;
3253       mark_non_root (call->fun, 0, 0);
3254     }
3255   return TRUE;
3256 }
3257
3258 /* Remove cycles from the call graph.  Set depth of nodes.  */
3259
3260 static bfd_boolean
3261 remove_cycles (struct function_info *fun,
3262                struct bfd_link_info *info,
3263                void *param)
3264 {
3265   struct call_info **callp, *call;
3266   unsigned int depth = *(unsigned int *) param;
3267   unsigned int max_depth = depth;
3268
3269   fun->depth = depth;
3270   fun->visit2 = TRUE;
3271   fun->marking = TRUE;
3272
3273   callp = &fun->call_list;
3274   while ((call = *callp) != NULL)
3275     {
3276       call->max_depth = depth + !call->is_pasted;
3277       if (!call->fun->visit2)
3278         {
3279           if (!remove_cycles (call->fun, info, &call->max_depth))
3280             return FALSE;
3281           if (max_depth < call->max_depth)
3282             max_depth = call->max_depth;
3283         }
3284       else if (call->fun->marking)
3285         {
3286           struct spu_link_hash_table *htab = spu_hash_table (info);
3287
3288           if (!htab->params->auto_overlay
3289               && htab->params->stack_analysis)
3290             {
3291               const char *f1 = func_name (fun);
3292               const char *f2 = func_name (call->fun);
3293
3294               info->callbacks->info (_("Stack analysis will ignore the call "
3295                                        "from %s to %s\n"),
3296                                      f1, f2);
3297             }
3298
3299           call->broken_cycle = TRUE;
3300         }
3301       callp = &call->next;
3302     }
3303   fun->marking = FALSE;
3304   *(unsigned int *) param = max_depth;
3305   return TRUE;
3306 }
3307
3308 /* Check that we actually visited all nodes in remove_cycles.  If we
3309    didn't, then there is some cycle in the call graph not attached to
3310    any root node.  Arbitrarily choose a node in the cycle as a new
3311    root and break the cycle.  */
3312
3313 static bfd_boolean
3314 mark_detached_root (struct function_info *fun,
3315                     struct bfd_link_info *info,
3316                     void *param)
3317 {
3318   if (fun->visit2)
3319     return TRUE;
3320   fun->non_root = FALSE;
3321   *(unsigned int *) param = 0;
3322   return remove_cycles (fun, info, param);
3323 }
3324
3325 /* Populate call_list for each function.  */
3326
3327 static bfd_boolean
3328 build_call_tree (struct bfd_link_info *info)
3329 {
3330   bfd *ibfd;
3331   unsigned int depth;
3332
3333   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
3334     {
3335       extern const bfd_target spu_elf32_vec;
3336       asection *sec;
3337
3338       if (ibfd->xvec != &spu_elf32_vec)
3339         continue;
3340
3341       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
3342         if (!mark_functions_via_relocs (sec, info, TRUE))
3343           return FALSE;
3344     }
3345
3346   /* Transfer call info from hot/cold section part of function
3347      to main entry.  */
3348   if (!spu_hash_table (info)->params->auto_overlay
3349       && !for_each_node (transfer_calls, info, 0, FALSE))
3350     return FALSE;
3351
3352   /* Find the call graph root(s).  */
3353   if (!for_each_node (mark_non_root, info, 0, FALSE))
3354     return FALSE;
3355
3356   /* Remove cycles from the call graph.  We start from the root node(s)
3357      so that we break cycles in a reasonable place.  */
3358   depth = 0;
3359   if (!for_each_node (remove_cycles, info, &depth, TRUE))
3360     return FALSE;
3361
3362   return for_each_node (mark_detached_root, info, &depth, FALSE);
3363 }
3364
3365 /* qsort predicate to sort calls by priority, max_depth then count.  */
3366
3367 static int
3368 sort_calls (const void *a, const void *b)
3369 {
3370   struct call_info *const *c1 = a;
3371   struct call_info *const *c2 = b;
3372   int delta;
3373
3374   delta = (*c2)->priority - (*c1)->priority;
3375   if (delta != 0)
3376     return delta;
3377
3378   delta = (*c2)->max_depth - (*c1)->max_depth;
3379   if (delta != 0)
3380     return delta;
3381
3382   delta = (*c2)->count - (*c1)->count;
3383   if (delta != 0)
3384     return delta;
3385
3386   return (char *) c1 - (char *) c2;
3387 }
3388
3389 struct _mos_param {
3390   unsigned int max_overlay_size;
3391 };
3392
3393 /* Set linker_mark and gc_mark on any sections that we will put in
3394    overlays.  These flags are used by the generic ELF linker, but we
3395    won't be continuing on to bfd_elf_final_link so it is OK to use
3396    them.  linker_mark is clear before we get here.  Set segment_mark
3397    on sections that are part of a pasted function (excluding the last
3398    section).
3399
3400    Set up function rodata section if --overlay-rodata.  We don't
3401    currently include merged string constant rodata sections since
3402
3403    Sort the call graph so that the deepest nodes will be visited
3404    first.  */
3405
3406 static bfd_boolean
3407 mark_overlay_section (struct function_info *fun,
3408                       struct bfd_link_info *info,
3409                       void *param)
3410 {
3411   struct call_info *call;
3412   unsigned int count;
3413   struct _mos_param *mos_param = param;
3414   struct spu_link_hash_table *htab = spu_hash_table (info);
3415
3416   if (fun->visit4)
3417     return TRUE;
3418
3419   fun->visit4 = TRUE;
3420   if (!fun->sec->linker_mark
3421       && (htab->params->ovly_flavour != ovly_soft_icache
3422           || htab->params->non_ia_text
3423           || strncmp (fun->sec->name, ".text.ia.", 9) == 0
3424           || strcmp (fun->sec->name, ".init") == 0
3425           || strcmp (fun->sec->name, ".fini") == 0))
3426     {
3427       unsigned int size;
3428
3429       fun->sec->linker_mark = 1;
3430       fun->sec->gc_mark = 1;
3431       fun->sec->segment_mark = 0;
3432       /* Ensure SEC_CODE is set on this text section (it ought to
3433          be!), and SEC_CODE is clear on rodata sections.  We use
3434          this flag to differentiate the two overlay section types.  */
3435       fun->sec->flags |= SEC_CODE;
3436
3437       size = fun->sec->size;
3438       if (htab->params->auto_overlay & OVERLAY_RODATA)
3439         {
3440           char *name = NULL;
3441
3442           /* Find the rodata section corresponding to this function's
3443              text section.  */
3444           if (strcmp (fun->sec->name, ".text") == 0)
3445             {
3446               name = bfd_malloc (sizeof (".rodata"));
3447               if (name == NULL)
3448                 return FALSE;
3449               memcpy (name, ".rodata", sizeof (".rodata"));
3450             }
3451           else if (strncmp (fun->sec->name, ".text.", 6) == 0)
3452             {
3453               size_t len = strlen (fun->sec->name);
3454               name = bfd_malloc (len + 3);
3455               if (name == NULL)
3456                 return FALSE;
3457               memcpy (name, ".rodata", sizeof (".rodata"));
3458               memcpy (name + 7, fun->sec->name + 5, len - 4);
3459             }
3460           else if (strncmp (fun->sec->name, ".gnu.linkonce.t.", 16) == 0)
3461             {
3462               size_t len = strlen (fun->sec->name) + 1;
3463               name = bfd_malloc (len);
3464               if (name == NULL)
3465                 return FALSE;
3466               memcpy (name, fun->sec->name, len);
3467               name[14] = 'r';
3468             }
3469
3470           if (name != NULL)
3471             {
3472               asection *rodata = NULL;
3473               asection *group_sec = elf_section_data (fun->sec)->next_in_group;
3474               if (group_sec == NULL)
3475                 rodata = bfd_get_section_by_name (fun->sec->owner, name);
3476               else
3477                 while (group_sec != NULL && group_sec != fun->sec)
3478                   {
3479                     if (strcmp (group_sec->name, name) == 0)
3480                       {
3481                         rodata = group_sec;
3482                         break;
3483                       }
3484                     group_sec = elf_section_data (group_sec)->next_in_group;
3485                   }
3486               fun->rodata = rodata;
3487               if (fun->rodata)
3488                 {
3489                   size += fun->rodata->size;
3490                   if (htab->params->line_size != 0
3491                       && size > htab->params->line_size)
3492                     {
3493                       size -= fun->rodata->size;
3494                       fun->rodata = NULL;
3495                     }
3496                   else
3497                     {
3498                       fun->rodata->linker_mark = 1;
3499                       fun->rodata->gc_mark = 1;
3500                       fun->rodata->flags &= ~SEC_CODE;
3501                     }
3502                 }
3503               free (name);
3504             }
3505         }
3506       if (mos_param->max_overlay_size < size)
3507         mos_param->max_overlay_size = size;
3508     }
3509
3510   for (count = 0, call = fun->call_list; call != NULL; call = call->next)
3511     count += 1;
3512
3513   if (count > 1)
3514     {
3515       struct call_info **calls = bfd_malloc (count * sizeof (*calls));
3516       if (calls == NULL)
3517         return FALSE;
3518
3519       for (count = 0, call = fun->call_list; call != NULL; call = call->next)
3520         calls[count++] = call;
3521
3522       qsort (calls, count, sizeof (*calls), sort_calls);
3523
3524       fun->call_list = NULL;
3525       while (count != 0)
3526         {
3527           --count;
3528           calls[count]->next = fun->call_list;
3529           fun->call_list = calls[count];
3530         }
3531       free (calls);
3532     }
3533
3534   for (call = fun->call_list; call != NULL; call = call->next)
3535     {
3536       if (call->is_pasted)
3537         {
3538           /* There can only be one is_pasted call per function_info.  */
3539           BFD_ASSERT (!fun->sec->segment_mark);
3540           fun->sec->segment_mark = 1;
3541         }
3542       if (!call->broken_cycle
3543           && !mark_overlay_section (call->fun, info, param))
3544         return FALSE;
3545     }
3546
3547   /* Don't put entry code into an overlay.  The overlay manager needs
3548      a stack!  Also, don't mark .ovl.init as an overlay.  */
3549   if (fun->lo + fun->sec->output_offset + fun->sec->output_section->vma
3550       == info->output_bfd->start_address
3551       || strncmp (fun->sec->output_section->name, ".ovl.init", 9) == 0)
3552     {
3553       fun->sec->linker_mark = 0;
3554       if (fun->rodata != NULL)
3555         fun->rodata->linker_mark = 0;
3556     }
3557   return TRUE;
3558 }
3559
3560 /* If non-zero then unmark functions called from those within sections
3561    that we need to unmark.  Unfortunately this isn't reliable since the
3562    call graph cannot know the destination of function pointer calls.  */
3563 #define RECURSE_UNMARK 0
3564
3565 struct _uos_param {
3566   asection *exclude_input_section;
3567   asection *exclude_output_section;
3568   unsigned long clearing;
3569 };
3570
3571 /* Undo some of mark_overlay_section's work.  */
3572
3573 static bfd_boolean
3574 unmark_overlay_section (struct function_info *fun,
3575                         struct bfd_link_info *info,
3576                         void *param)
3577 {
3578   struct call_info *call;
3579   struct _uos_param *uos_param = param;
3580   unsigned int excluded = 0;
3581
3582   if (fun->visit5)
3583     return TRUE;
3584
3585   fun->visit5 = TRUE;
3586
3587   excluded = 0;
3588   if (fun->sec == uos_param->exclude_input_section
3589       || fun->sec->output_section == uos_param->exclude_output_section)
3590     excluded = 1;
3591
3592   if (RECURSE_UNMARK)
3593     uos_param->clearing += excluded;
3594
3595   if (RECURSE_UNMARK ? uos_param->clearing : excluded)
3596     {
3597       fun->sec->linker_mark = 0;
3598       if (fun->rodata)
3599         fun->rodata->linker_mark = 0;
3600     }
3601
3602   for (call = fun->call_list; call != NULL; call = call->next)
3603     if (!call->broken_cycle
3604         && !unmark_overlay_section (call->fun, info, param))
3605       return FALSE;
3606
3607   if (RECURSE_UNMARK)
3608     uos_param->clearing -= excluded;
3609   return TRUE;
3610 }
3611
3612 struct _cl_param {
3613   unsigned int lib_size;
3614   asection **lib_sections;
3615 };
3616
3617 /* Add sections we have marked as belonging to overlays to an array
3618    for consideration as non-overlay sections.  The array consist of
3619    pairs of sections, (text,rodata), for functions in the call graph.  */
3620
3621 static bfd_boolean
3622 collect_lib_sections (struct function_info *fun,
3623                       struct bfd_link_info *info,
3624                       void *param)
3625 {
3626   struct _cl_param *lib_param = param;
3627   struct call_info *call;
3628   unsigned int size;
3629
3630   if (fun->visit6)
3631     return TRUE;
3632
3633   fun->visit6 = TRUE;
3634   if (!fun->sec->linker_mark || !fun->sec->gc_mark || fun->sec->segment_mark)
3635     return TRUE;
3636
3637   size = fun->sec->size;
3638   if (fun->rodata)
3639     size += fun->rodata->size;
3640
3641   if (size <= lib_param->lib_size)
3642     {
3643       *lib_param->lib_sections++ = fun->sec;
3644       fun->sec->gc_mark = 0;
3645       if (fun->rodata && fun->rodata->linker_mark && fun->rodata->gc_mark)
3646         {
3647           *lib_param->lib_sections++ = fun->rodata;
3648           fun->rodata->gc_mark = 0;
3649         }
3650       else
3651         *lib_param->lib_sections++ = NULL;
3652     }
3653
3654   for (call = fun->call_list; call != NULL; call = call->next)
3655     if (!call->broken_cycle)
3656       collect_lib_sections (call->fun, info, param);
3657
3658   return TRUE;
3659 }
3660
3661 /* qsort predicate to sort sections by call count.  */
3662
3663 static int
3664 sort_lib (const void *a, const void *b)
3665 {
3666   asection *const *s1 = a;
3667   asection *const *s2 = b;
3668   struct _spu_elf_section_data *sec_data;
3669   struct spu_elf_stack_info *sinfo;
3670   int delta;
3671
3672   delta = 0;
3673   if ((sec_data = spu_elf_section_data (*s1)) != NULL
3674       && (sinfo = sec_data->u.i.stack_info) != NULL)
3675     {
3676       int i;
3677       for (i = 0; i < sinfo->num_fun; ++i)
3678         delta -= sinfo->fun[i].call_count;
3679     }
3680
3681   if ((sec_data = spu_elf_section_data (*s2)) != NULL
3682       && (sinfo = sec_data->u.i.stack_info) != NULL)
3683     {
3684       int i;
3685       for (i = 0; i < sinfo->num_fun; ++i)
3686         delta += sinfo->fun[i].call_count;
3687     }
3688
3689   if (delta != 0)
3690     return delta;
3691
3692   return s1 - s2;
3693 }
3694
3695 /* Remove some sections from those marked to be in overlays.  Choose
3696    those that are called from many places, likely library functions.  */
3697
3698 static unsigned int
3699 auto_ovl_lib_functions (struct bfd_link_info *info, unsigned int lib_size)
3700 {
3701   bfd *ibfd;
3702   asection **lib_sections;
3703   unsigned int i, lib_count;
3704   struct _cl_param collect_lib_param;
3705   struct function_info dummy_caller;
3706   struct spu_link_hash_table *htab;
3707
3708   memset (&dummy_caller, 0, sizeof (dummy_caller));
3709   lib_count = 0;
3710   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
3711     {
3712       extern const bfd_target spu_elf32_vec;
3713       asection *sec;
3714
3715       if (ibfd->xvec != &spu_elf32_vec)
3716         continue;
3717
3718       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
3719         if (sec->linker_mark
3720             && sec->size < lib_size
3721             && (sec->flags & SEC_CODE) != 0)
3722           lib_count += 1;
3723     }
3724   lib_sections = bfd_malloc (lib_count * 2 * sizeof (*lib_sections));
3725   if (lib_sections == NULL)
3726     return (unsigned int) -1;
3727   collect_lib_param.lib_size = lib_size;
3728   collect_lib_param.lib_sections = lib_sections;
3729   if (!for_each_node (collect_lib_sections, info, &collect_lib_param,
3730                       TRUE))
3731     return (unsigned int) -1;
3732   lib_count = (collect_lib_param.lib_sections - lib_sections) / 2;
3733
3734   /* Sort sections so that those with the most calls are first.  */
3735   if (lib_count > 1)
3736     qsort (lib_sections, lib_count, 2 * sizeof (*lib_sections), sort_lib);
3737
3738   htab = spu_hash_table (info);
3739   for (i = 0; i < lib_count; i++)
3740     {
3741       unsigned int tmp, stub_size;
3742       asection *sec;
3743       struct _spu_elf_section_data *sec_data;
3744       struct spu_elf_stack_info *sinfo;
3745
3746       sec = lib_sections[2 * i];
3747       /* If this section is OK, its size must be less than lib_size.  */
3748       tmp = sec->size;
3749       /* If it has a rodata section, then add that too.  */
3750       if (lib_sections[2 * i + 1])
3751         tmp += lib_sections[2 * i + 1]->size;
3752       /* Add any new overlay call stubs needed by the section.  */
3753       stub_size = 0;
3754       if (tmp < lib_size
3755           && (sec_data = spu_elf_section_data (sec)) != NULL
3756           && (sinfo = sec_data->u.i.stack_info) != NULL)
3757         {
3758           int k;
3759           struct call_info *call;
3760
3761           for (k = 0; k < sinfo->num_fun; ++k)
3762             for (call = sinfo->fun[k].call_list; call; call = call->next)
3763               if (call->fun->sec->linker_mark)
3764                 {
3765                   struct call_info *p;
3766                   for (p = dummy_caller.call_list; p; p = p->next)
3767                     if (p->fun == call->fun)
3768                       break;
3769                   if (!p)
3770                     stub_size += ovl_stub_size (htab->params);
3771                 }
3772         }
3773       if (tmp + stub_size < lib_size)
3774         {
3775           struct call_info **pp, *p;
3776
3777           /* This section fits.  Mark it as non-overlay.  */
3778           lib_sections[2 * i]->linker_mark = 0;
3779           if (lib_sections[2 * i + 1])
3780             lib_sections[2 * i + 1]->linker_mark = 0;
3781           lib_size -= tmp + stub_size;
3782           /* Call stubs to the section we just added are no longer
3783              needed.  */
3784           pp = &dummy_caller.call_list;
3785           while ((p = *pp) != NULL)
3786             if (!p->fun->sec->linker_mark)
3787               {
3788                 lib_size += ovl_stub_size (htab->params);
3789                 *pp = p->next;
3790                 free (p);
3791               }
3792             else
3793               pp = &p->next;
3794           /* Add new call stubs to dummy_caller.  */
3795           if ((sec_data = spu_elf_section_data (sec)) != NULL
3796               && (sinfo = sec_data->u.i.stack_info) != NULL)
3797             {
3798               int k;
3799               struct call_info *call;
3800
3801               for (k = 0; k < sinfo->num_fun; ++k)
3802                 for (call = sinfo->fun[k].call_list;
3803                      call;
3804                      call = call->next)
3805                   if (call->fun->sec->linker_mark)
3806                     {
3807                       struct call_info *callee;
3808                       callee = bfd_malloc (sizeof (*callee));
3809                       if (callee == NULL)
3810                         return (unsigned int) -1;
3811                       *callee = *call;
3812                       if (!insert_callee (&dummy_caller, callee))
3813                         free (callee);
3814                     }
3815             }
3816         }
3817     }
3818   while (dummy_caller.call_list != NULL)
3819     {
3820       struct call_info *call = dummy_caller.call_list;
3821       dummy_caller.call_list = call->next;
3822       free (call);
3823     }
3824   for (i = 0; i < 2 * lib_count; i++)
3825     if (lib_sections[i])
3826       lib_sections[i]->gc_mark = 1;
3827   free (lib_sections);
3828   return lib_size;
3829 }
3830
3831 /* Build an array of overlay sections.  The deepest node's section is
3832    added first, then its parent node's section, then everything called
3833    from the parent section.  The idea being to group sections to
3834    minimise calls between different overlays.  */
3835
3836 static bfd_boolean
3837 collect_overlays (struct function_info *fun,
3838                   struct bfd_link_info *info,
3839                   void *param)
3840 {
3841   struct call_info *call;
3842   bfd_boolean added_fun;
3843   asection ***ovly_sections = param;
3844
3845   if (fun->visit7)
3846     return TRUE;
3847
3848   fun->visit7 = TRUE;
3849   for (call = fun->call_list; call != NULL; call = call->next)
3850     if (!call->is_pasted && !call->broken_cycle)
3851       {
3852         if (!collect_overlays (call->fun, info, ovly_sections))
3853           return FALSE;
3854         break;
3855       }
3856
3857   added_fun = FALSE;
3858   if (fun->sec->linker_mark && fun->sec->gc_mark)
3859     {
3860       fun->sec->gc_mark = 0;
3861       *(*ovly_sections)++ = fun->sec;
3862       if (fun->rodata && fun->rodata->linker_mark && fun->rodata->gc_mark)
3863         {
3864           fun->rodata->gc_mark = 0;
3865           *(*ovly_sections)++ = fun->rodata;
3866         }
3867       else
3868         *(*ovly_sections)++ = NULL;
3869       added_fun = TRUE;
3870
3871       /* Pasted sections must stay with the first section.  We don't
3872          put pasted sections in the array, just the first section.
3873          Mark subsequent sections as already considered.  */
3874       if (fun->sec->segment_mark)
3875         {
3876           struct function_info *call_fun = fun;
3877           do
3878             {
3879               for (call = call_fun->call_list; call != NULL; call = call->next)
3880                 if (call->is_pasted)
3881                   {
3882                     call_fun = call->fun;
3883                     call_fun->sec->gc_mark = 0;
3884                     if (call_fun->rodata)
3885                       call_fun->rodata->gc_mark = 0;
3886                     break;
3887                   }
3888               if (call == NULL)
3889                 abort ();
3890             }
3891           while (call_fun->sec->segment_mark);
3892         }
3893     }
3894
3895   for (call = fun->call_list; call != NULL; call = call->next)
3896     if (!call->broken_cycle
3897         && !collect_overlays (call->fun, info, ovly_sections))
3898       return FALSE;
3899
3900   if (added_fun)
3901     {
3902       struct _spu_elf_section_data *sec_data;
3903       struct spu_elf_stack_info *sinfo;
3904
3905       if ((sec_data = spu_elf_section_data (fun->sec)) != NULL
3906           && (sinfo = sec_data->u.i.stack_info) != NULL)
3907         {
3908           int i;
3909           for (i = 0; i < sinfo->num_fun; ++i)
3910             if (!collect_overlays (&sinfo->fun[i], info, ovly_sections))
3911               return FALSE;
3912         }
3913     }
3914
3915   return TRUE;
3916 }
3917
3918 struct _sum_stack_param {
3919   size_t cum_stack;
3920   size_t overall_stack;
3921   bfd_boolean emit_stack_syms;
3922 };
3923
3924 /* Descend the call graph for FUN, accumulating total stack required.  */
3925
3926 static bfd_boolean
3927 sum_stack (struct function_info *fun,
3928            struct bfd_link_info *info,
3929            void *param)
3930 {
3931   struct call_info *call;
3932   struct function_info *max;
3933   size_t stack, cum_stack;
3934   const char *f1;
3935   bfd_boolean has_call;
3936   struct _sum_stack_param *sum_stack_param = param;
3937   struct spu_link_hash_table *htab;
3938
3939   cum_stack = fun->stack;
3940   sum_stack_param->cum_stack = cum_stack;
3941   if (fun->visit3)
3942     return TRUE;
3943
3944   has_call = FALSE;
3945   max = NULL;
3946   for (call = fun->call_list; call; call = call->next)
3947     {
3948       if (call->broken_cycle)
3949         continue;
3950       if (!call->is_pasted)
3951         has_call = TRUE;
3952       if (!sum_stack (call->fun, info, sum_stack_param))
3953         return FALSE;
3954       stack = sum_stack_param->cum_stack;
3955       /* Include caller stack for normal calls, don't do so for
3956          tail calls.  fun->stack here is local stack usage for
3957          this function.  */
3958       if (!call->is_tail || call->is_pasted || call->fun->start != NULL)
3959         stack += fun->stack;
3960       if (cum_stack < stack)
3961         {
3962           cum_stack = stack;
3963           max = call->fun;
3964         }
3965     }
3966
3967   sum_stack_param->cum_stack = cum_stack;
3968   stack = fun->stack;
3969   /* Now fun->stack holds cumulative stack.  */
3970   fun->stack = cum_stack;
3971   fun->visit3 = TRUE;
3972
3973   if (!fun->non_root
3974       && sum_stack_param->overall_stack < cum_stack)
3975     sum_stack_param->overall_stack = cum_stack;
3976
3977   htab = spu_hash_table (info);
3978   if (htab->params->auto_overlay)
3979     return TRUE;
3980
3981   f1 = func_name (fun);
3982   if (htab->params->stack_analysis)
3983     {
3984       if (!fun->non_root)
3985         info->callbacks->info (_("  %s: 0x%v\n"), f1, (bfd_vma) cum_stack);
3986       info->callbacks->minfo (_("%s: 0x%v 0x%v\n"),
3987                               f1, (bfd_vma) stack, (bfd_vma) cum_stack);
3988
3989       if (has_call)
3990         {
3991           info->callbacks->minfo (_("  calls:\n"));
3992           for (call = fun->call_list; call; call = call->next)
3993             if (!call->is_pasted && !call->broken_cycle)
3994               {
3995                 const char *f2 = func_name (call->fun);
3996                 const char *ann1 = call->fun == max ? "*" : " ";
3997                 const char *ann2 = call->is_tail ? "t" : " ";
3998
3999                 info->callbacks->minfo (_("   %s%s %s\n"), ann1, ann2, f2);
4000               }
4001         }
4002     }
4003
4004   if (sum_stack_param->emit_stack_syms)
4005     {
4006       char *name = bfd_malloc (18 + strlen (f1));
4007       struct elf_link_hash_entry *h;
4008
4009       if (name == NULL)
4010         return FALSE;
4011
4012       if (fun->global || ELF_ST_BIND (fun->u.sym->st_info) == STB_GLOBAL)
4013         sprintf (name, "__stack_%s", f1);
4014       else
4015         sprintf (name, "__stack_%x_%s", fun->sec->id & 0xffffffff, f1);
4016
4017       h = elf_link_hash_lookup (&htab->elf, name, TRUE, TRUE, FALSE);
4018       free (name);
4019       if (h != NULL
4020           && (h->root.type == bfd_link_hash_new
4021               || h->root.type == bfd_link_hash_undefined
4022               || h->root.type == bfd_link_hash_undefweak))
4023         {
4024           h->root.type = bfd_link_hash_defined;
4025           h->root.u.def.section = bfd_abs_section_ptr;
4026           h->root.u.def.value = cum_stack;
4027           h->size = 0;
4028           h->type = 0;
4029           h->ref_regular = 1;
4030           h->def_regular = 1;
4031           h->ref_regular_nonweak = 1;
4032           h->forced_local = 1;
4033           h->non_elf = 0;
4034         }
4035     }
4036
4037   return TRUE;
4038 }
4039
4040 /* SEC is part of a pasted function.  Return the call_info for the
4041    next section of this function.  */
4042
4043 static struct call_info *
4044 find_pasted_call (asection *sec)
4045 {
4046   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
4047   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
4048   struct call_info *call;
4049   int k;
4050
4051   for (k = 0; k < sinfo->num_fun; ++k)
4052     for (call = sinfo->fun[k].call_list; call != NULL; call = call->next)
4053       if (call->is_pasted)
4054         return call;
4055   abort ();
4056   return 0;
4057 }
4058
4059 /* qsort predicate to sort bfds by file name.  */
4060
4061 static int
4062 sort_bfds (const void *a, const void *b)
4063 {
4064   bfd *const *abfd1 = a;
4065   bfd *const *abfd2 = b;
4066
4067   return filename_cmp ((*abfd1)->filename, (*abfd2)->filename);
4068 }
4069
4070 static unsigned int
4071 print_one_overlay_section (FILE *script,
4072                            unsigned int base,
4073                            unsigned int count,
4074                            unsigned int ovlynum,
4075                            unsigned int *ovly_map,
4076                            asection **ovly_sections,
4077                            struct bfd_link_info *info)
4078 {
4079   unsigned int j;
4080
4081   for (j = base; j < count && ovly_map[j] == ovlynum; j++)
4082     {
4083       asection *sec = ovly_sections[2 * j];
4084
4085       if (fprintf (script, "   %s%c%s (%s)\n",
4086                    (sec->owner->my_archive != NULL
4087                     ? sec->owner->my_archive->filename : ""),
4088                    info->path_separator,
4089                    sec->owner->filename,
4090                    sec->name) <= 0)
4091         return -1;
4092       if (sec->segment_mark)
4093         {
4094           struct call_info *call = find_pasted_call (sec);
4095           while (call != NULL)
4096             {
4097               struct function_info *call_fun = call->fun;
4098               sec = call_fun->sec;
4099               if (fprintf (script, "   %s%c%s (%s)\n",
4100                            (sec->owner->my_archive != NULL
4101                             ? sec->owner->my_archive->filename : ""),
4102                            info->path_separator,
4103                            sec->owner->filename,
4104                            sec->name) <= 0)
4105                 return -1;
4106               for (call = call_fun->call_list; call; call = call->next)
4107                 if (call->is_pasted)
4108                   break;
4109             }
4110         }
4111     }
4112
4113   for (j = base; j < count && ovly_map[j] == ovlynum; j++)
4114     {
4115       asection *sec = ovly_sections[2 * j + 1];
4116       if (sec != NULL
4117           && fprintf (script, "   %s%c%s (%s)\n",
4118                       (sec->owner->my_archive != NULL
4119                        ? sec->owner->my_archive->filename : ""),
4120                       info->path_separator,
4121                       sec->owner->filename,
4122                       sec->name) <= 0)
4123         return -1;
4124
4125       sec = ovly_sections[2 * j];
4126       if (sec->segment_mark)
4127         {
4128           struct call_info *call = find_pasted_call (sec);
4129           while (call != NULL)
4130             {
4131               struct function_info *call_fun = call->fun;
4132               sec = call_fun->rodata;
4133               if (sec != NULL
4134                   && fprintf (script, "   %s%c%s (%s)\n",
4135                               (sec->owner->my_archive != NULL
4136                                ? sec->owner->my_archive->filename : ""),
4137                               info->path_separator,
4138                               sec->owner->filename,
4139                               sec->name) <= 0)
4140                 return -1;
4141               for (call = call_fun->call_list; call; call = call->next)
4142                 if (call->is_pasted)
4143                   break;
4144             }
4145         }
4146     }
4147
4148   return j;
4149 }
4150
4151 /* Handle --auto-overlay.  */
4152
4153 static void
4154 spu_elf_auto_overlay (struct bfd_link_info *info)
4155 {
4156   bfd *ibfd;
4157   bfd **bfd_arr;
4158   struct elf_segment_map *m;
4159   unsigned int fixed_size, lo, hi;
4160   unsigned int reserved;
4161   struct spu_link_hash_table *htab;
4162   unsigned int base, i, count, bfd_count;
4163   unsigned int region, ovlynum;
4164   asection **ovly_sections, **ovly_p;
4165   unsigned int *ovly_map;
4166   FILE *script;
4167   unsigned int total_overlay_size, overlay_size;
4168   const char *ovly_mgr_entry;
4169   struct elf_link_hash_entry *h;
4170   struct _mos_param mos_param;
4171   struct _uos_param uos_param;
4172   struct function_info dummy_caller;
4173
4174   /* Find the extents of our loadable image.  */
4175   lo = (unsigned int) -1;
4176   hi = 0;
4177   for (m = elf_seg_map (info->output_bfd); m != NULL; m = m->next)
4178     if (m->p_type == PT_LOAD)
4179       for (i = 0; i < m->count; i++)
4180         if (m->sections[i]->size != 0)
4181           {
4182             if (m->sections[i]->vma < lo)
4183               lo = m->sections[i]->vma;
4184             if (m->sections[i]->vma + m->sections[i]->size - 1 > hi)
4185               hi = m->sections[i]->vma + m->sections[i]->size - 1;
4186           }
4187   fixed_size = hi + 1 - lo;
4188
4189   if (!discover_functions (info))
4190     goto err_exit;
4191
4192   if (!build_call_tree (info))
4193     goto err_exit;
4194
4195   htab = spu_hash_table (info);
4196   reserved = htab->params->auto_overlay_reserved;
4197   if (reserved == 0)
4198     {
4199       struct _sum_stack_param sum_stack_param;
4200
4201       sum_stack_param.emit_stack_syms = 0;
4202       sum_stack_param.overall_stack = 0;
4203       if (!for_each_node (sum_stack, info, &sum_stack_param, TRUE))
4204         goto err_exit;
4205       reserved = (sum_stack_param.overall_stack
4206                   + htab->params->extra_stack_space);
4207     }
4208
4209   /* No need for overlays if everything already fits.  */
4210   if (fixed_size + reserved <= htab->local_store
4211       && htab->params->ovly_flavour != ovly_soft_icache)
4212     {
4213       htab->params->auto_overlay = 0;
4214       return;
4215     }
4216
4217   uos_param.exclude_input_section = 0;
4218   uos_param.exclude_output_section
4219     = bfd_get_section_by_name (info->output_bfd, ".interrupt");
4220
4221   ovly_mgr_entry = "__ovly_load";
4222   if (htab->params->ovly_flavour == ovly_soft_icache)
4223     ovly_mgr_entry = "__icache_br_handler";
4224   h = elf_link_hash_lookup (&htab->elf, ovly_mgr_entry,
4225                             FALSE, FALSE, FALSE);
4226   if (h != NULL
4227       && (h->root.type == bfd_link_hash_defined
4228           || h->root.type == bfd_link_hash_defweak)
4229       && h->def_regular)
4230     {
4231       /* We have a user supplied overlay manager.  */
4232       uos_param.exclude_input_section = h->root.u.def.section;
4233     }
4234   else
4235     {
4236       /* If no user overlay manager, spu_elf_load_ovl_mgr will add our
4237          builtin version to .text, and will adjust .text size.  */
4238       fixed_size += (*htab->params->spu_elf_load_ovl_mgr) ();
4239     }
4240
4241   /* Mark overlay sections, and find max overlay section size.  */
4242   mos_param.max_overlay_size = 0;
4243   if (!for_each_node (mark_overlay_section, info, &mos_param, TRUE))
4244     goto err_exit;
4245
4246   /* We can't put the overlay manager or interrupt routines in
4247      overlays.  */
4248   uos_param.clearing = 0;
4249   if ((uos_param.exclude_input_section
4250        || uos_param.exclude_output_section)
4251       && !for_each_node (unmark_overlay_section, info, &uos_param, TRUE))
4252     goto err_exit;
4253
4254   bfd_count = 0;
4255   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
4256     ++bfd_count;
4257   bfd_arr = bfd_malloc (bfd_count * sizeof (*bfd_arr));
4258   if (bfd_arr == NULL)
4259     goto err_exit;
4260
4261   /* Count overlay sections, and subtract their sizes from "fixed_size".  */
4262   count = 0;
4263   bfd_count = 0;
4264   total_overlay_size = 0;
4265   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
4266     {
4267       extern const bfd_target spu_elf32_vec;
4268       asection *sec;
4269       unsigned int old_count;
4270
4271       if (ibfd->xvec != &spu_elf32_vec)
4272         continue;
4273
4274       old_count = count;
4275       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
4276         if (sec->linker_mark)
4277           {
4278             if ((sec->flags & SEC_CODE) != 0)
4279               count += 1;
4280             fixed_size -= sec->size;
4281             total_overlay_size += sec->size;
4282           }
4283         else if ((sec->flags & (SEC_ALLOC | SEC_LOAD)) == (SEC_ALLOC | SEC_LOAD)
4284                  && sec->output_section->owner == info->output_bfd
4285                  && strncmp (sec->output_section->name, ".ovl.init", 9) == 0)
4286           fixed_size -= sec->size;
4287       if (count != old_count)
4288         bfd_arr[bfd_count++] = ibfd;
4289     }
4290
4291   /* Since the overlay link script selects sections by file name and
4292      section name, ensure that file names are unique.  */
4293   if (bfd_count > 1)
4294     {
4295       bfd_boolean ok = TRUE;
4296
4297       qsort (bfd_arr, bfd_count, sizeof (*bfd_arr), sort_bfds);
4298       for (i = 1; i < bfd_count; ++i)
4299         if (filename_cmp (bfd_arr[i - 1]->filename, bfd_arr[i]->filename) == 0)
4300           {
4301             if (bfd_arr[i - 1]->my_archive == bfd_arr[i]->my_archive)
4302               {
4303                 if (bfd_arr[i - 1]->my_archive && bfd_arr[i]->my_archive)
4304                   info->callbacks->einfo (_("%s duplicated in %s\n"),
4305                                           bfd_arr[i]->filename,
4306                                           bfd_arr[i]->my_archive->filename);
4307                 else
4308                   info->callbacks->einfo (_("%s duplicated\n"),
4309                                           bfd_arr[i]->filename);
4310                 ok = FALSE;
4311               }
4312           }
4313       if (!ok)
4314         {
4315           info->callbacks->einfo (_("sorry, no support for duplicate "
4316                                     "object files in auto-overlay script\n"));
4317           bfd_set_error (bfd_error_bad_value);
4318           goto err_exit;
4319         }
4320     }
4321   free (bfd_arr);
4322
4323   fixed_size += reserved;
4324   fixed_size += htab->non_ovly_stub * ovl_stub_size (htab->params);
4325   if (fixed_size + mos_param.max_overlay_size <= htab->local_store)
4326     {
4327       if (htab->params->ovly_flavour == ovly_soft_icache)
4328         {
4329           /* Stubs in the non-icache area are bigger.  */
4330           fixed_size += htab->non_ovly_stub * 16;
4331           /* Space for icache manager tables.
4332              a) Tag array, one quadword per cache line.
4333              - word 0: ia address of present line, init to zero.  */
4334           fixed_size += 16 << htab->num_lines_log2;
4335           /* b) Rewrite "to" list, one quadword per cache line.  */
4336           fixed_size += 16 << htab->num_lines_log2;
4337           /* c) Rewrite "from" list, one byte per outgoing branch (rounded up
4338                 to a power-of-two number of full quadwords) per cache line.  */
4339           fixed_size += 16 << (htab->fromelem_size_log2
4340                                + htab->num_lines_log2);
4341           /* d) Pointer to __ea backing store (toe), 1 quadword.  */
4342           fixed_size += 16;
4343         }
4344       else
4345         {
4346           /* Guess number of overlays.  Assuming overlay buffer is on
4347              average only half full should be conservative.  */
4348           ovlynum = (total_overlay_size * 2 * htab->params->num_lines
4349                      / (htab->local_store - fixed_size));
4350           /* Space for _ovly_table[], _ovly_buf_table[] and toe.  */
4351           fixed_size += ovlynum * 16 + 16 + 4 + 16;
4352         }
4353     }
4354
4355   if (fixed_size + mos_param.max_overlay_size > htab->local_store)
4356     info->callbacks->einfo (_("non-overlay size of 0x%v plus maximum overlay "
4357                               "size of 0x%v exceeds local store\n"),
4358                             (bfd_vma) fixed_size,
4359                             (bfd_vma) mos_param.max_overlay_size);
4360
4361   /* Now see if we should put some functions in the non-overlay area.  */
4362   else if (fixed_size < htab->params->auto_overlay_fixed)
4363     {
4364       unsigned int max_fixed, lib_size;
4365
4366       max_fixed = htab->local_store - mos_param.max_overlay_size;
4367       if (max_fixed > htab->params->auto_overlay_fixed)
4368         max_fixed = htab->params->auto_overlay_fixed;
4369       lib_size = max_fixed - fixed_size;
4370       lib_size = auto_ovl_lib_functions (info, lib_size);
4371       if (lib_size == (unsigned int) -1)
4372         goto err_exit;
4373       fixed_size = max_fixed - lib_size;
4374     }
4375
4376   /* Build an array of sections, suitably sorted to place into
4377      overlays.  */
4378   ovly_sections = bfd_malloc (2 * count * sizeof (*ovly_sections));
4379   if (ovly_sections == NULL)
4380     goto err_exit;
4381   ovly_p = ovly_sections;
4382   if (!for_each_node (collect_overlays, info, &ovly_p, TRUE))
4383     goto err_exit;
4384   count = (size_t) (ovly_p - ovly_sections) / 2;
4385   ovly_map = bfd_malloc (count * sizeof (*ovly_map));
4386   if (ovly_map == NULL)
4387     goto err_exit;
4388
4389   memset (&dummy_caller, 0, sizeof (dummy_caller));
4390   overlay_size = (htab->local_store - fixed_size) / htab->params->num_lines;
4391   if (htab->params->line_size != 0)
4392     overlay_size = htab->params->line_size;
4393   base = 0;
4394   ovlynum = 0;
4395   while (base < count)
4396     {
4397       unsigned int size = 0, rosize = 0, roalign = 0;
4398
4399       for (i = base; i < count; i++)
4400         {
4401           asection *sec, *rosec;
4402           unsigned int tmp, rotmp;
4403           unsigned int num_stubs;
4404           struct call_info *call, *pasty;
4405           struct _spu_elf_section_data *sec_data;
4406           struct spu_elf_stack_info *sinfo;
4407           unsigned int k;
4408
4409           /* See whether we can add this section to the current
4410              overlay without overflowing our overlay buffer.  */
4411           sec = ovly_sections[2 * i];
4412           tmp = align_power (size, sec->alignment_power) + sec->size;
4413           rotmp = rosize;
4414           rosec = ovly_sections[2 * i + 1];
4415           if (rosec != NULL)
4416             {
4417               rotmp = align_power (rotmp, rosec->alignment_power) + rosec->size;
4418               if (roalign < rosec->alignment_power)
4419                 roalign = rosec->alignment_power;
4420             }
4421           if (align_power (tmp, roalign) + rotmp > overlay_size)
4422             break;
4423           if (sec->segment_mark)
4424             {
4425               /* Pasted sections must stay together, so add their
4426                  sizes too.  */
4427               pasty = find_pasted_call (sec);
4428               while (pasty != NULL)
4429                 {
4430                   struct function_info *call_fun = pasty->fun;
4431                   tmp = (align_power (tmp, call_fun->sec->alignment_power)
4432                          + call_fun->sec->size);
4433                   if (call_fun->rodata)
4434                     {
4435                       rotmp = (align_power (rotmp,
4436                                             call_fun->rodata->alignment_power)
4437                                + call_fun->rodata->size);
4438                       if (roalign < rosec->alignment_power)
4439                         roalign = rosec->alignment_power;
4440                     }
4441                   for (pasty = call_fun->call_list; pasty; pasty = pasty->next)
4442                     if (pasty->is_pasted)
4443                       break;
4444                 }
4445             }
4446           if (align_power (tmp, roalign) + rotmp > overlay_size)
4447             break;
4448
4449           /* If we add this section, we might need new overlay call
4450              stubs.  Add any overlay section calls to dummy_call.  */
4451           pasty = NULL;
4452           sec_data = spu_elf_section_data (sec);
4453           sinfo = sec_data->u.i.stack_info;
4454           for (k = 0; k < (unsigned) sinfo->num_fun; ++k)
4455             for (call = sinfo->fun[k].call_list; call; call = call->next)
4456               if (call->is_pasted)
4457                 {
4458                   BFD_ASSERT (pasty == NULL);
4459                   pasty = call;
4460                 }
4461               else if (call->fun->sec->linker_mark)
4462                 {
4463                   if (!copy_callee (&dummy_caller, call))
4464                     goto err_exit;
4465                 }
4466           while (pasty != NULL)
4467             {
4468               struct function_info *call_fun = pasty->fun;
4469               pasty = NULL;
4470               for (call = call_fun->call_list; call; call = call->next)
4471                 if (call->is_pasted)
4472                   {
4473                     BFD_ASSERT (pasty == NULL);
4474                     pasty = call;
4475                   }
4476                 else if (!copy_callee (&dummy_caller, call))
4477                   goto err_exit;
4478             }
4479
4480           /* Calculate call stub size.  */
4481           num_stubs = 0;
4482           for (call = dummy_caller.call_list; call; call = call->next)
4483             {
4484               unsigned int stub_delta = 1;
4485
4486               if (htab->params->ovly_flavour == ovly_soft_icache)
4487                 stub_delta = call->count;
4488               num_stubs += stub_delta;
4489
4490               /* If the call is within this overlay, we won't need a
4491                  stub.  */
4492               for (k = base; k < i + 1; k++)
4493                 if (call->fun->sec == ovly_sections[2 * k])
4494                   {
4495                     num_stubs -= stub_delta;
4496                     break;
4497                   }
4498             }
4499           if (htab->params->ovly_flavour == ovly_soft_icache
4500               && num_stubs > htab->params->max_branch)
4501             break;
4502           if (align_power (tmp, roalign) + rotmp
4503               + num_stubs * ovl_stub_size (htab->params) > overlay_size)
4504             break;
4505           size = tmp;
4506           rosize = rotmp;
4507         }
4508
4509       if (i == base)
4510         {
4511           info->callbacks->einfo (_("%B:%A%s exceeds overlay size\n"),
4512                                   ovly_sections[2 * i]->owner,
4513                                   ovly_sections[2 * i],
4514                                   ovly_sections[2 * i + 1] ? " + rodata" : "");
4515           bfd_set_error (bfd_error_bad_value);
4516           goto err_exit;
4517         }
4518
4519       while (dummy_caller.call_list != NULL)
4520         {
4521           struct call_info *call = dummy_caller.call_list;
4522           dummy_caller.call_list = call->next;
4523           free (call);
4524         }
4525
4526       ++ovlynum;
4527       while (base < i)
4528         ovly_map[base++] = ovlynum;
4529     }
4530
4531   script = htab->params->spu_elf_open_overlay_script ();
4532
4533   if (htab->params->ovly_flavour == ovly_soft_icache)
4534     {
4535       if (fprintf (script, "SECTIONS\n{\n") <= 0)
4536         goto file_err;
4537
4538       if (fprintf (script,
4539                    " . = ALIGN (%u);\n"
4540                    " .ovl.init : { *(.ovl.init) }\n"
4541                    " . = ABSOLUTE (ADDR (.ovl.init));\n",
4542                    htab->params->line_size) <= 0)
4543         goto file_err;
4544
4545       base = 0;
4546       ovlynum = 1;
4547       while (base < count)
4548         {
4549           unsigned int indx = ovlynum - 1;
4550           unsigned int vma, lma;
4551
4552           vma = (indx & (htab->params->num_lines - 1)) << htab->line_size_log2;
4553           lma = vma + (((indx >> htab->num_lines_log2) + 1) << 18);
4554
4555           if (fprintf (script, " .ovly%u ABSOLUTE (ADDR (.ovl.init)) + %u "
4556                                ": AT (LOADADDR (.ovl.init) + %u) {\n",
4557                        ovlynum, vma, lma) <= 0)
4558             goto file_err;
4559
4560           base = print_one_overlay_section (script, base, count, ovlynum,
4561                                             ovly_map, ovly_sections, info);
4562           if (base == (unsigned) -1)
4563             goto file_err;
4564
4565           if (fprintf (script, "  }\n") <= 0)
4566             goto file_err;
4567
4568           ovlynum++;
4569         }
4570
4571       if (fprintf (script, " . = ABSOLUTE (ADDR (.ovl.init)) + %u;\n",
4572                    1 << (htab->num_lines_log2 + htab->line_size_log2)) <= 0)
4573         goto file_err;
4574
4575       if (fprintf (script, "}\nINSERT AFTER .toe;\n") <= 0)
4576         goto file_err;
4577     }
4578   else
4579     {
4580       if (fprintf (script, "SECTIONS\n{\n") <= 0)
4581         goto file_err;
4582
4583       if (fprintf (script,
4584                    " . = ALIGN (16);\n"
4585                    " .ovl.init : { *(.ovl.init) }\n"
4586                    " . = ABSOLUTE (ADDR (.ovl.init));\n") <= 0)
4587         goto file_err;
4588
4589       for (region = 1; region <= htab->params->num_lines; region++)
4590         {
4591           ovlynum = region;
4592           base = 0;
4593           while (base < count && ovly_map[base] < ovlynum)
4594             base++;
4595
4596           if (base == count)
4597             break;
4598
4599           if (region == 1)
4600             {
4601               /* We need to set lma since we are overlaying .ovl.init.  */
4602               if (fprintf (script,
4603                            " OVERLAY : AT (ALIGN (LOADADDR (.ovl.init) + SIZEOF (.ovl.init), 16))\n {\n") <= 0)
4604                 goto file_err;
4605             }
4606           else
4607             {
4608               if (fprintf (script, " OVERLAY :\n {\n") <= 0)
4609                 goto file_err;
4610             }
4611
4612           while (base < count)
4613             {
4614               if (fprintf (script, "  .ovly%u {\n", ovlynum) <= 0)
4615                 goto file_err;
4616
4617               base = print_one_overlay_section (script, base, count, ovlynum,
4618                                                 ovly_map, ovly_sections, info);
4619               if (base == (unsigned) -1)
4620                 goto file_err;
4621
4622               if (fprintf (script, "  }\n") <= 0)
4623                 goto file_err;
4624
4625               ovlynum += htab->params->num_lines;
4626               while (base < count && ovly_map[base] < ovlynum)
4627                 base++;
4628             }
4629
4630           if (fprintf (script, " }\n") <= 0)
4631             goto file_err;
4632         }
4633
4634       if (fprintf (script, "}\nINSERT BEFORE .text;\n") <= 0)
4635         goto file_err;
4636     }
4637
4638   free (ovly_map);
4639   free (ovly_sections);
4640
4641   if (fclose (script) != 0)
4642     goto file_err;
4643
4644   if (htab->params->auto_overlay & AUTO_RELINK)
4645     (*htab->params->spu_elf_relink) ();
4646
4647   xexit (0);
4648
4649  file_err:
4650   bfd_set_error (bfd_error_system_call);
4651  err_exit:
4652   info->callbacks->einfo ("%F%P: auto overlay error: %E\n");
4653   xexit (1);
4654 }
4655
4656 /* Provide an estimate of total stack required.  */
4657
4658 static bfd_boolean
4659 spu_elf_stack_analysis (struct bfd_link_info *info)
4660 {
4661   struct spu_link_hash_table *htab;
4662   struct _sum_stack_param sum_stack_param;
4663
4664   if (!discover_functions (info))
4665     return FALSE;
4666
4667   if (!build_call_tree (info))
4668     return FALSE;
4669
4670   htab = spu_hash_table (info);
4671   if (htab->params->stack_analysis)
4672     {
4673       info->callbacks->info (_("Stack size for call graph root nodes.\n"));
4674       info->callbacks->minfo (_("\nStack size for functions.  "
4675                                 "Annotations: '*' max stack, 't' tail call\n"));
4676     }
4677
4678   sum_stack_param.emit_stack_syms = htab->params->emit_stack_syms;
4679   sum_stack_param.overall_stack = 0;
4680   if (!for_each_node (sum_stack, info, &sum_stack_param, TRUE))
4681     return FALSE;
4682
4683   if (htab->params->stack_analysis)
4684     info->callbacks->info (_("Maximum stack required is 0x%v\n"),
4685                            (bfd_vma) sum_stack_param.overall_stack);
4686   return TRUE;
4687 }
4688
4689 /* Perform a final link.  */
4690
4691 static bfd_boolean
4692 spu_elf_final_link (bfd *output_bfd, struct bfd_link_info *info)
4693 {
4694   struct spu_link_hash_table *htab = spu_hash_table (info);
4695
4696   if (htab->params->auto_overlay)
4697     spu_elf_auto_overlay (info);
4698
4699   if ((htab->params->stack_analysis
4700        || (htab->params->ovly_flavour == ovly_soft_icache
4701            && htab->params->lrlive_analysis))
4702       && !spu_elf_stack_analysis (info))
4703     info->callbacks->einfo ("%X%P: stack/lrlive analysis error: %E\n");
4704
4705   if (!spu_elf_build_stubs (info))
4706     info->callbacks->einfo ("%F%P: can not build overlay stubs: %E\n");
4707
4708   return bfd_elf_final_link (output_bfd, info);
4709 }
4710
4711 /* Called when not normally emitting relocs, ie. !info->relocatable
4712    and !info->emitrelocations.  Returns a count of special relocs
4713    that need to be emitted.  */
4714
4715 static unsigned int
4716 spu_elf_count_relocs (struct bfd_link_info *info, asection *sec)
4717 {
4718   Elf_Internal_Rela *relocs;
4719   unsigned int count = 0;
4720
4721   relocs = _bfd_elf_link_read_relocs (sec->owner, sec, NULL, NULL,
4722                                       info->keep_memory);
4723   if (relocs != NULL)
4724     {
4725       Elf_Internal_Rela *rel;
4726       Elf_Internal_Rela *relend = relocs + sec->reloc_count;
4727
4728       for (rel = relocs; rel < relend; rel++)
4729         {
4730           int r_type = ELF32_R_TYPE (rel->r_info);
4731           if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4732             ++count;
4733         }
4734
4735       if (elf_section_data (sec)->relocs != relocs)
4736         free (relocs);
4737     }
4738
4739   return count;
4740 }
4741
4742 /* Functions for adding fixup records to .fixup */
4743
4744 #define FIXUP_RECORD_SIZE 4
4745
4746 #define FIXUP_PUT(output_bfd,htab,index,addr) \
4747           bfd_put_32 (output_bfd, addr, \
4748                       htab->sfixup->contents + FIXUP_RECORD_SIZE * (index))
4749 #define FIXUP_GET(output_bfd,htab,index) \
4750           bfd_get_32 (output_bfd, \
4751                       htab->sfixup->contents + FIXUP_RECORD_SIZE * (index))
4752
4753 /* Store OFFSET in .fixup.  This assumes it will be called with an
4754    increasing OFFSET.  When this OFFSET fits with the last base offset,
4755    it just sets a bit, otherwise it adds a new fixup record.  */
4756 static void
4757 spu_elf_emit_fixup (bfd * output_bfd, struct bfd_link_info *info,
4758                     bfd_vma offset)
4759 {
4760   struct spu_link_hash_table *htab = spu_hash_table (info);
4761   asection *sfixup = htab->sfixup;
4762   bfd_vma qaddr = offset & ~(bfd_vma) 15;
4763   bfd_vma bit = ((bfd_vma) 8) >> ((offset & 15) >> 2);
4764   if (sfixup->reloc_count == 0)
4765     {
4766       FIXUP_PUT (output_bfd, htab, 0, qaddr | bit);
4767       sfixup->reloc_count++;
4768     }
4769   else
4770     {
4771       bfd_vma base = FIXUP_GET (output_bfd, htab, sfixup->reloc_count - 1);
4772       if (qaddr != (base & ~(bfd_vma) 15))
4773         {
4774           if ((sfixup->reloc_count + 1) * FIXUP_RECORD_SIZE > sfixup->size)
4775             (*_bfd_error_handler) (_("fatal error while creating .fixup"));
4776           FIXUP_PUT (output_bfd, htab, sfixup->reloc_count, qaddr | bit);
4777           sfixup->reloc_count++;
4778         }
4779       else
4780         FIXUP_PUT (output_bfd, htab, sfixup->reloc_count - 1, base | bit);
4781     }
4782 }
4783
4784 /* Apply RELOCS to CONTENTS of INPUT_SECTION from INPUT_BFD.  */
4785
4786 static int
4787 spu_elf_relocate_section (bfd *output_bfd,
4788                           struct bfd_link_info *info,
4789                           bfd *input_bfd,
4790                           asection *input_section,
4791                           bfd_byte *contents,
4792                           Elf_Internal_Rela *relocs,
4793                           Elf_Internal_Sym *local_syms,
4794                           asection **local_sections)
4795 {
4796   Elf_Internal_Shdr *symtab_hdr;
4797   struct elf_link_hash_entry **sym_hashes;
4798   Elf_Internal_Rela *rel, *relend;
4799   struct spu_link_hash_table *htab;
4800   asection *ea;
4801   int ret = TRUE;
4802   bfd_boolean emit_these_relocs = FALSE;
4803   bfd_boolean is_ea_sym;
4804   bfd_boolean stubs;
4805   unsigned int iovl = 0;
4806
4807   htab = spu_hash_table (info);
4808   stubs = (htab->stub_sec != NULL
4809            && maybe_needs_stubs (input_section));
4810   iovl = overlay_index (input_section);
4811   ea = bfd_get_section_by_name (output_bfd, "._ea");
4812   symtab_hdr = &elf_tdata (input_bfd)->symtab_hdr;
4813   sym_hashes = (struct elf_link_hash_entry **) (elf_sym_hashes (input_bfd));
4814
4815   rel = relocs;
4816   relend = relocs + input_section->reloc_count;
4817   for (; rel < relend; rel++)
4818     {
4819       int r_type;
4820       reloc_howto_type *howto;
4821       unsigned int r_symndx;
4822       Elf_Internal_Sym *sym;
4823       asection *sec;
4824       struct elf_link_hash_entry *h;
4825       const char *sym_name;
4826       bfd_vma relocation;
4827       bfd_vma addend;
4828       bfd_reloc_status_type r;
4829       bfd_boolean unresolved_reloc;
4830       enum _stub_type stub_type;
4831
4832       r_symndx = ELF32_R_SYM (rel->r_info);
4833       r_type = ELF32_R_TYPE (rel->r_info);
4834       howto = elf_howto_table + r_type;
4835       unresolved_reloc = FALSE;
4836       h = NULL;
4837       sym = NULL;
4838       sec = NULL;
4839       if (r_symndx < symtab_hdr->sh_info)
4840         {
4841           sym = local_syms + r_symndx;
4842           sec = local_sections[r_symndx];
4843           sym_name = bfd_elf_sym_name (input_bfd, symtab_hdr, sym, sec);
4844           relocation = _bfd_elf_rela_local_sym (output_bfd, sym, &sec, rel);
4845         }
4846       else
4847         {
4848           if (sym_hashes == NULL)
4849             return FALSE;
4850
4851           h = sym_hashes[r_symndx - symtab_hdr->sh_info];
4852
4853           if (info->wrap_hash != NULL
4854               && (input_section->flags & SEC_DEBUGGING) != 0)
4855             h = ((struct elf_link_hash_entry *)
4856                  unwrap_hash_lookup (info, input_bfd, &h->root));
4857
4858           while (h->root.type == bfd_link_hash_indirect
4859                  || h->root.type == bfd_link_hash_warning)
4860             h = (struct elf_link_hash_entry *) h->root.u.i.link;
4861
4862           relocation = 0;
4863           if (h->root.type == bfd_link_hash_defined
4864               || h->root.type == bfd_link_hash_defweak)
4865             {
4866               sec = h->root.u.def.section;
4867               if (sec == NULL
4868                   || sec->output_section == NULL)
4869                 /* Set a flag that will be cleared later if we find a
4870                    relocation value for this symbol.  output_section
4871                    is typically NULL for symbols satisfied by a shared
4872                    library.  */
4873                 unresolved_reloc = TRUE;
4874               else
4875                 relocation = (h->root.u.def.value
4876                               + sec->output_section->vma
4877                               + sec->output_offset);
4878             }
4879           else if (h->root.type == bfd_link_hash_undefweak)
4880             ;
4881           else if (info->unresolved_syms_in_objects == RM_IGNORE
4882                    && ELF_ST_VISIBILITY (h->other) == STV_DEFAULT)
4883             ;
4884           else if (!info->relocatable
4885                    && !(r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64))
4886             {
4887               bfd_boolean err;
4888               err = (info->unresolved_syms_in_objects == RM_GENERATE_ERROR
4889                      || ELF_ST_VISIBILITY (h->other) != STV_DEFAULT);
4890               if (!info->callbacks->undefined_symbol (info,
4891                                                       h->root.root.string,
4892                                                       input_bfd,
4893                                                       input_section,
4894                                                       rel->r_offset, err))
4895                 return FALSE;
4896             }
4897           sym_name = h->root.root.string;
4898         }
4899
4900       if (sec != NULL && discarded_section (sec))
4901         RELOC_AGAINST_DISCARDED_SECTION (info, input_bfd, input_section,
4902                                          rel, 1, relend, howto, 0, contents);
4903
4904       if (info->relocatable)
4905         continue;
4906
4907       /* Change "a rt,ra,rb" to "ai rt,ra,0". */
4908       if (r_type == R_SPU_ADD_PIC
4909           && h != NULL
4910           && !(h->def_regular || ELF_COMMON_DEF_P (h)))
4911         {
4912           bfd_byte *loc = contents + rel->r_offset;
4913           loc[0] = 0x1c;
4914           loc[1] = 0x00;
4915           loc[2] &= 0x3f;
4916         }
4917
4918       is_ea_sym = (ea != NULL
4919                    && sec != NULL
4920                    && sec->output_section == ea);
4921
4922       /* If this symbol is in an overlay area, we may need to relocate
4923          to the overlay stub.  */
4924       addend = rel->r_addend;
4925       if (stubs
4926           && !is_ea_sym
4927           && (stub_type = needs_ovl_stub (h, sym, sec, input_section, rel,
4928                                           contents, info)) != no_stub)
4929         {
4930           unsigned int ovl = 0;
4931           struct got_entry *g, **head;
4932
4933           if (stub_type != nonovl_stub)
4934             ovl = iovl;
4935
4936           if (h != NULL)
4937             head = &h->got.glist;
4938           else
4939             head = elf_local_got_ents (input_bfd) + r_symndx;
4940
4941           for (g = *head; g != NULL; g = g->next)
4942             if (htab->params->ovly_flavour == ovly_soft_icache
4943                 ? (g->ovl == ovl
4944                    && g->br_addr == (rel->r_offset
4945                                      + input_section->output_offset
4946                                      + input_section->output_section->vma))
4947                 : g->addend == addend && (g->ovl == ovl || g->ovl == 0))
4948               break;
4949           if (g == NULL)
4950             abort ();
4951
4952           relocation = g->stub_addr;
4953           addend = 0;
4954         }
4955       else
4956         {
4957           /* For soft icache, encode the overlay index into addresses.  */
4958           if (htab->params->ovly_flavour == ovly_soft_icache
4959               && (r_type == R_SPU_ADDR16_HI
4960                   || r_type == R_SPU_ADDR32 || r_type == R_SPU_REL32)
4961               && !is_ea_sym)
4962             {
4963               unsigned int ovl = overlay_index (sec);
4964               if (ovl != 0)
4965                 {
4966                   unsigned int set_id = ((ovl - 1) >> htab->num_lines_log2) + 1;
4967                   relocation += set_id << 18;
4968                 }
4969             }
4970         }
4971
4972       if (htab->params->emit_fixups && !info->relocatable
4973           && (input_section->flags & SEC_ALLOC) != 0
4974           && r_type == R_SPU_ADDR32)
4975         {
4976           bfd_vma offset;
4977           offset = rel->r_offset + input_section->output_section->vma
4978                    + input_section->output_offset;
4979           spu_elf_emit_fixup (output_bfd, info, offset);
4980         }
4981
4982       if (unresolved_reloc)
4983         ;
4984       else if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4985         {
4986           if (is_ea_sym)
4987             {
4988               /* ._ea is a special section that isn't allocated in SPU
4989                  memory, but rather occupies space in PPU memory as
4990                  part of an embedded ELF image.  If this reloc is
4991                  against a symbol defined in ._ea, then transform the
4992                  reloc into an equivalent one without a symbol
4993                  relative to the start of the ELF image.  */
4994               rel->r_addend += (relocation
4995                                 - ea->vma
4996                                 + elf_section_data (ea)->this_hdr.sh_offset);
4997               rel->r_info = ELF32_R_INFO (0, r_type);
4998             }
4999           emit_these_relocs = TRUE;
5000           continue;
5001         }
5002       else if (is_ea_sym)
5003         unresolved_reloc = TRUE;
5004
5005       if (unresolved_reloc
5006           && _bfd_elf_section_offset (output_bfd, info, input_section,
5007                                       rel->r_offset) != (bfd_vma) -1)
5008         {
5009           (*_bfd_error_handler)
5010             (_("%B(%s+0x%lx): unresolvable %s relocation against symbol `%s'"),
5011              input_bfd,
5012              bfd_get_section_name (input_bfd, input_section),
5013              (long) rel->r_offset,
5014              howto->name,
5015              sym_name);
5016           ret = FALSE;
5017         }
5018
5019       r = _bfd_final_link_relocate (howto,
5020                                     input_bfd,
5021                                     input_section,
5022                                     contents,
5023                                     rel->r_offset, relocation, addend);
5024
5025       if (r != bfd_reloc_ok)
5026         {
5027           const char *msg = (const char *) 0;
5028
5029           switch (r)
5030             {
5031             case bfd_reloc_overflow:
5032               if (!((*info->callbacks->reloc_overflow)
5033                     (info, (h ? &h->root : NULL), sym_name, howto->name,
5034                      (bfd_vma) 0, input_bfd, input_section, rel->r_offset)))
5035                 return FALSE;
5036               break;
5037
5038             case bfd_reloc_undefined:
5039               if (!((*info->callbacks->undefined_symbol)
5040                     (info, sym_name, input_bfd, input_section,
5041                      rel->r_offset, TRUE)))
5042                 return FALSE;
5043               break;
5044
5045             case bfd_reloc_outofrange:
5046               msg = _("internal error: out of range error");
5047               goto common_error;
5048
5049             case bfd_reloc_notsupported:
5050               msg = _("internal error: unsupported relocation error");
5051               goto common_error;
5052
5053             case bfd_reloc_dangerous:
5054               msg = _("internal error: dangerous error");
5055               goto common_error;
5056
5057             default:
5058               msg = _("internal error: unknown error");
5059               /* fall through */
5060
5061             common_error:
5062               ret = FALSE;
5063               if (!((*info->callbacks->warning)
5064                     (info, msg, sym_name, input_bfd, input_section,
5065                      rel->r_offset)))
5066                 return FALSE;
5067               break;
5068             }
5069         }
5070     }
5071
5072   if (ret
5073       && emit_these_relocs
5074       && !info->emitrelocations)
5075     {
5076       Elf_Internal_Rela *wrel;
5077       Elf_Internal_Shdr *rel_hdr;
5078
5079       wrel = rel = relocs;
5080       relend = relocs + input_section->reloc_count;
5081       for (; rel < relend; rel++)
5082         {
5083           int r_type;
5084
5085           r_type = ELF32_R_TYPE (rel->r_info);
5086           if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
5087             *wrel++ = *rel;
5088         }
5089       input_section->reloc_count = wrel - relocs;
5090       /* Backflips for _bfd_elf_link_output_relocs.  */
5091       rel_hdr = _bfd_elf_single_rel_hdr (input_section);
5092       rel_hdr->sh_size = input_section->reloc_count * rel_hdr->sh_entsize;
5093       ret = 2;
5094     }
5095
5096   return ret;
5097 }
5098
5099 static bfd_boolean
5100 spu_elf_finish_dynamic_sections (bfd *output_bfd ATTRIBUTE_UNUSED,
5101                                  struct bfd_link_info *info ATTRIBUTE_UNUSED)
5102 {
5103   return TRUE;
5104 }
5105
5106 /* Adjust _SPUEAR_ syms to point at their overlay stubs.  */
5107
5108 static int
5109 spu_elf_output_symbol_hook (struct bfd_link_info *info,
5110                             const char *sym_name ATTRIBUTE_UNUSED,
5111                             Elf_Internal_Sym *sym,
5112                             asection *sym_sec ATTRIBUTE_UNUSED,
5113                             struct elf_link_hash_entry *h)
5114 {
5115   struct spu_link_hash_table *htab = spu_hash_table (info);
5116
5117   if (!info->relocatable
5118       && htab->stub_sec != NULL
5119       && h != NULL
5120       && (h->root.type == bfd_link_hash_defined
5121           || h->root.type == bfd_link_hash_defweak)
5122       && h->def_regular
5123       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0)
5124     {
5125       struct got_entry *g;
5126
5127       for (g = h->got.glist; g != NULL; g = g->next)
5128         if (htab->params->ovly_flavour == ovly_soft_icache
5129             ? g->br_addr == g->stub_addr
5130             : g->addend == 0 && g->ovl == 0)
5131           {
5132             sym->st_shndx = (_bfd_elf_section_from_bfd_section
5133                              (htab->stub_sec[0]->output_section->owner,
5134                               htab->stub_sec[0]->output_section));
5135             sym->st_value = g->stub_addr;
5136             break;
5137           }
5138     }
5139
5140   return 1;
5141 }
5142
5143 static int spu_plugin = 0;
5144
5145 void
5146 spu_elf_plugin (int val)
5147 {
5148   spu_plugin = val;
5149 }
5150
5151 /* Set ELF header e_type for plugins.  */
5152
5153 static void
5154 spu_elf_post_process_headers (bfd *abfd, struct bfd_link_info *info)
5155 {
5156   if (spu_plugin)
5157     {
5158       Elf_Internal_Ehdr *i_ehdrp = elf_elfheader (abfd);
5159
5160       i_ehdrp->e_type = ET_DYN;
5161     }
5162
5163   _bfd_elf_post_process_headers (abfd, info);
5164 }
5165
5166 /* We may add an extra PT_LOAD segment for .toe.  We also need extra
5167    segments for overlays.  */
5168
5169 static int
5170 spu_elf_additional_program_headers (bfd *abfd, struct bfd_link_info *info)
5171 {
5172   int extra = 0;
5173   asection *sec;
5174
5175   if (info != NULL)
5176     {
5177       struct spu_link_hash_table *htab = spu_hash_table (info);
5178       extra = htab->num_overlays;
5179     }
5180
5181   if (extra)
5182     ++extra;
5183
5184   sec = bfd_get_section_by_name (abfd, ".toe");
5185   if (sec != NULL && (sec->flags & SEC_LOAD) != 0)
5186     ++extra;
5187
5188   return extra;
5189 }
5190
5191 /* Remove .toe section from other PT_LOAD segments and put it in
5192    a segment of its own.  Put overlays in separate segments too.  */
5193
5194 static bfd_boolean
5195 spu_elf_modify_segment_map (bfd *abfd, struct bfd_link_info *info)
5196 {
5197   asection *toe, *s;
5198   struct elf_segment_map *m, *m_overlay;
5199   struct elf_segment_map **p, **p_overlay;
5200   unsigned int i;
5201
5202   if (info == NULL)
5203     return TRUE;
5204
5205   toe = bfd_get_section_by_name (abfd, ".toe");
5206   for (m = elf_seg_map (abfd); m != NULL; m = m->next)
5207     if (m->p_type == PT_LOAD && m->count > 1)
5208       for (i = 0; i < m->count; i++)
5209         if ((s = m->sections[i]) == toe
5210             || spu_elf_section_data (s)->u.o.ovl_index != 0)
5211           {
5212             struct elf_segment_map *m2;
5213             bfd_vma amt;
5214
5215             if (i + 1 < m->count)
5216               {
5217                 amt = sizeof (struct elf_segment_map);
5218                 amt += (m->count - (i + 2)) * sizeof (m->sections[0]);
5219                 m2 = bfd_zalloc (abfd, amt);
5220                 if (m2 == NULL)
5221                   return FALSE;
5222                 m2->count = m->count - (i + 1);
5223                 memcpy (m2->sections, m->sections + i + 1,
5224                         m2->count * sizeof (m->sections[0]));
5225                 m2->p_type = PT_LOAD;
5226                 m2->next = m->next;
5227                 m->next = m2;
5228               }
5229             m->count = 1;
5230             if (i != 0)
5231               {
5232                 m->count = i;
5233                 amt = sizeof (struct elf_segment_map);
5234                 m2 = bfd_zalloc (abfd, amt);
5235                 if (m2 == NULL)
5236                   return FALSE;
5237                 m2->p_type = PT_LOAD;
5238                 m2->count = 1;
5239                 m2->sections[0] = s;
5240                 m2->next = m->next;
5241                 m->next = m2;
5242               }
5243             break;
5244           }
5245
5246
5247   /* Some SPU ELF loaders ignore the PF_OVERLAY flag and just load all
5248      PT_LOAD segments.  This can cause the .ovl.init section to be
5249      overwritten with the contents of some overlay segment.  To work
5250      around this issue, we ensure that all PF_OVERLAY segments are
5251      sorted first amongst the program headers; this ensures that even
5252      with a broken loader, the .ovl.init section (which is not marked
5253      as PF_OVERLAY) will be placed into SPU local store on startup.  */
5254
5255   /* Move all overlay segments onto a separate list.  */
5256   p = &elf_seg_map (abfd);
5257   p_overlay = &m_overlay;
5258   while (*p != NULL)
5259     {
5260       if ((*p)->p_type == PT_LOAD && (*p)->count == 1
5261           && spu_elf_section_data ((*p)->sections[0])->u.o.ovl_index != 0)
5262         {
5263           m = *p;
5264           *p = m->next;
5265           *p_overlay = m;
5266           p_overlay = &m->next;
5267           continue;
5268         }
5269
5270       p = &((*p)->next);
5271     }
5272
5273   /* Re-insert overlay segments at the head of the segment map.  */
5274   *p_overlay = elf_seg_map (abfd);
5275   elf_seg_map (abfd) = m_overlay;
5276
5277   return TRUE;
5278 }
5279
5280 /* Tweak the section type of .note.spu_name.  */
5281
5282 static bfd_boolean
5283 spu_elf_fake_sections (bfd *obfd ATTRIBUTE_UNUSED,
5284                        Elf_Internal_Shdr *hdr,
5285                        asection *sec)
5286 {
5287   if (strcmp (sec->name, SPU_PTNOTE_SPUNAME) == 0)
5288     hdr->sh_type = SHT_NOTE;
5289   return TRUE;
5290 }
5291
5292 /* Tweak phdrs before writing them out.  */
5293
5294 static int
5295 spu_elf_modify_program_headers (bfd *abfd, struct bfd_link_info *info)
5296 {
5297   const struct elf_backend_data *bed;
5298   struct elf_obj_tdata *tdata;
5299   Elf_Internal_Phdr *phdr, *last;
5300   struct spu_link_hash_table *htab;
5301   unsigned int count;
5302   unsigned int i;
5303
5304   if (info == NULL)
5305     return TRUE;
5306
5307   bed = get_elf_backend_data (abfd);
5308   tdata = elf_tdata (abfd);
5309   phdr = tdata->phdr;
5310   count = elf_program_header_size (abfd) / bed->s->sizeof_phdr;
5311   htab = spu_hash_table (info);
5312   if (htab->num_overlays != 0)
5313     {
5314       struct elf_segment_map *m;
5315       unsigned int o;
5316
5317       for (i = 0, m = elf_seg_map (abfd); m; ++i, m = m->next)
5318         if (m->count != 0
5319             && (o = spu_elf_section_data (m->sections[0])->u.o.ovl_index) != 0)
5320           {
5321             /* Mark this as an overlay header.  */
5322             phdr[i].p_flags |= PF_OVERLAY;
5323
5324             if (htab->ovtab != NULL && htab->ovtab->size != 0
5325                 && htab->params->ovly_flavour != ovly_soft_icache)
5326               {
5327                 bfd_byte *p = htab->ovtab->contents;
5328                 unsigned int off = o * 16 + 8;
5329
5330                 /* Write file_off into _ovly_table.  */
5331                 bfd_put_32 (htab->ovtab->owner, phdr[i].p_offset, p + off);
5332               }
5333           }
5334       /* Soft-icache has its file offset put in .ovl.init.  */
5335       if (htab->init != NULL && htab->init->size != 0)
5336         {
5337           bfd_vma val = elf_section_data (htab->ovl_sec[0])->this_hdr.sh_offset;
5338
5339           bfd_put_32 (htab->init->owner, val, htab->init->contents + 4);
5340         }
5341     }
5342
5343   /* Round up p_filesz and p_memsz of PT_LOAD segments to multiples
5344      of 16.  This should always be possible when using the standard
5345      linker scripts, but don't create overlapping segments if
5346      someone is playing games with linker scripts.  */
5347   last = NULL;
5348   for (i = count; i-- != 0; )
5349     if (phdr[i].p_type == PT_LOAD)
5350       {
5351         unsigned adjust;
5352
5353         adjust = -phdr[i].p_filesz & 15;
5354         if (adjust != 0
5355             && last != NULL
5356             && phdr[i].p_offset + phdr[i].p_filesz > last->p_offset - adjust)
5357           break;
5358
5359         adjust = -phdr[i].p_memsz & 15;
5360         if (adjust != 0
5361             && last != NULL
5362             && phdr[i].p_filesz != 0
5363             && phdr[i].p_vaddr + phdr[i].p_memsz > last->p_vaddr - adjust
5364             && phdr[i].p_vaddr + phdr[i].p_memsz <= last->p_vaddr)
5365           break;
5366
5367         if (phdr[i].p_filesz != 0)
5368           last = &phdr[i];
5369       }
5370
5371   if (i == (unsigned int) -1)
5372     for (i = count; i-- != 0; )
5373       if (phdr[i].p_type == PT_LOAD)
5374         {
5375         unsigned adjust;
5376
5377         adjust = -phdr[i].p_filesz & 15;
5378         phdr[i].p_filesz += adjust;
5379
5380         adjust = -phdr[i].p_memsz & 15;
5381         phdr[i].p_memsz += adjust;
5382       }
5383
5384   return TRUE;
5385 }
5386
5387 bfd_boolean
5388 spu_elf_size_sections (bfd * output_bfd, struct bfd_link_info *info)
5389 {
5390   struct spu_link_hash_table *htab = spu_hash_table (info);
5391   if (htab->params->emit_fixups)
5392     {
5393       asection *sfixup = htab->sfixup;
5394       int fixup_count = 0;
5395       bfd *ibfd;
5396       size_t size;
5397
5398       for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)
5399         {
5400           asection *isec;
5401
5402           if (bfd_get_flavour (ibfd) != bfd_target_elf_flavour)
5403             continue;
5404
5405           /* Walk over each section attached to the input bfd.  */
5406           for (isec = ibfd->sections; isec != NULL; isec = isec->next)
5407             {
5408               Elf_Internal_Rela *internal_relocs, *irelaend, *irela;
5409               bfd_vma base_end;
5410
5411               /* If there aren't any relocs, then there's nothing more
5412                  to do.  */
5413               if ((isec->flags & SEC_ALLOC) == 0
5414                   || (isec->flags & SEC_RELOC) == 0
5415                   || isec->reloc_count == 0)
5416                 continue;
5417
5418               /* Get the relocs.  */
5419               internal_relocs =
5420                 _bfd_elf_link_read_relocs (ibfd, isec, NULL, NULL,
5421                                            info->keep_memory);
5422               if (internal_relocs == NULL)
5423                 return FALSE;
5424
5425               /* 1 quadword can contain up to 4 R_SPU_ADDR32
5426                  relocations.  They are stored in a single word by
5427                  saving the upper 28 bits of the address and setting the
5428                  lower 4 bits to a bit mask of the words that have the
5429                  relocation.  BASE_END keeps track of the next quadword. */
5430               irela = internal_relocs;
5431               irelaend = irela + isec->reloc_count;
5432               base_end = 0;
5433               for (; irela < irelaend; irela++)
5434                 if (ELF32_R_TYPE (irela->r_info) == R_SPU_ADDR32
5435                     && irela->r_offset >= base_end)
5436                   {
5437                     base_end = (irela->r_offset & ~(bfd_vma) 15) + 16;
5438                     fixup_count++;
5439                   }
5440             }
5441         }
5442
5443       /* We always have a NULL fixup as a sentinel */
5444       size = (fixup_count + 1) * FIXUP_RECORD_SIZE;
5445       if (!bfd_set_section_size (output_bfd, sfixup, size))
5446         return FALSE;
5447       sfixup->contents = (bfd_byte *) bfd_zalloc (info->input_bfds, size);
5448       if (sfixup->contents == NULL)
5449         return FALSE;
5450     }
5451   return TRUE;
5452 }
5453
5454 #define TARGET_BIG_SYM          spu_elf32_vec
5455 #define TARGET_BIG_NAME         "elf32-spu"
5456 #define ELF_ARCH                bfd_arch_spu
5457 #define ELF_TARGET_ID           SPU_ELF_DATA
5458 #define ELF_MACHINE_CODE        EM_SPU
5459 /* This matches the alignment need for DMA.  */
5460 #define ELF_MAXPAGESIZE         0x80
5461 #define elf_backend_rela_normal         1
5462 #define elf_backend_can_gc_sections     1
5463
5464 #define bfd_elf32_bfd_reloc_type_lookup         spu_elf_reloc_type_lookup
5465 #define bfd_elf32_bfd_reloc_name_lookup         spu_elf_reloc_name_lookup
5466 #define elf_info_to_howto                       spu_elf_info_to_howto
5467 #define elf_backend_count_relocs                spu_elf_count_relocs
5468 #define elf_backend_relocate_section            spu_elf_relocate_section
5469 #define elf_backend_finish_dynamic_sections     spu_elf_finish_dynamic_sections
5470 #define elf_backend_symbol_processing           spu_elf_backend_symbol_processing
5471 #define elf_backend_link_output_symbol_hook     spu_elf_output_symbol_hook
5472 #define elf_backend_object_p                    spu_elf_object_p
5473 #define bfd_elf32_new_section_hook              spu_elf_new_section_hook
5474 #define bfd_elf32_bfd_link_hash_table_create    spu_elf_link_hash_table_create
5475
5476 #define elf_backend_additional_program_headers  spu_elf_additional_program_headers
5477 #define elf_backend_modify_segment_map          spu_elf_modify_segment_map
5478 #define elf_backend_modify_program_headers      spu_elf_modify_program_headers
5479 #define elf_backend_post_process_headers        spu_elf_post_process_headers
5480 #define elf_backend_fake_sections               spu_elf_fake_sections
5481 #define elf_backend_special_sections            spu_elf_special_sections
5482 #define bfd_elf32_bfd_final_link                spu_elf_final_link
5483
5484 #include "elf32-target.h"