bfd/elf32-spu.c

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