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