bfd/elf32-spu.c

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