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