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 = htab->ovl_sec[0]->vma;
1955       h->root.u.def.section = bfd_abs_section_ptr;
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       call->max_depth = depth + !call->is_pasted;
3144       if (!call->fun->visit2)
3145         {
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   struct spu_link_hash_table *htab = spu_hash_table (info);
3283
3284   if (fun->visit4)
3285     return TRUE;
3286
3287   fun->visit4 = TRUE;
3288   if (!fun->sec->linker_mark
3289       && (htab->params->ovly_flavour != ovly_soft_icache
3290           || htab->params->non_ia_text
3291           || strncmp (fun->sec->name, ".text.ia.", 9) == 0))
3292     {
3293       unsigned int size;
3294
3295       fun->sec->linker_mark = 1;
3296       fun->sec->gc_mark = 1;
3297       fun->sec->segment_mark = 0;
3298       /* Ensure SEC_CODE is set on this text section (it ought to
3299          be!), and SEC_CODE is clear on rodata sections.  We use
3300          this flag to differentiate the two overlay section types.  */
3301       fun->sec->flags |= SEC_CODE;
3302
3303       size = fun->sec->size;
3304       if (htab->params->auto_overlay & OVERLAY_RODATA)
3305         {
3306           char *name = NULL;
3307
3308           /* Find the rodata section corresponding to this function's
3309              text section.  */
3310           if (strcmp (fun->sec->name, ".text") == 0)
3311             {
3312               name = bfd_malloc (sizeof (".rodata"));
3313               if (name == NULL)
3314                 return FALSE;
3315               memcpy (name, ".rodata", sizeof (".rodata"));
3316             }
3317           else if (strncmp (fun->sec->name, ".text.", 6) == 0)
3318             {
3319               size_t len = strlen (fun->sec->name);
3320               name = bfd_malloc (len + 3);
3321               if (name == NULL)
3322                 return FALSE;
3323               memcpy (name, ".rodata", sizeof (".rodata"));
3324               memcpy (name + 7, fun->sec->name + 5, len - 4);
3325             }
3326           else if (strncmp (fun->sec->name, ".gnu.linkonce.t.", 16) == 0)
3327             {
3328               size_t len = strlen (fun->sec->name) + 1;
3329               name = bfd_malloc (len);
3330               if (name == NULL)
3331                 return FALSE;
3332               memcpy (name, fun->sec->name, len);
3333               name[14] = 'r';
3334             }
3335
3336           if (name != NULL)
3337             {
3338               asection *rodata = NULL;
3339               asection *group_sec = elf_section_data (fun->sec)->next_in_group;
3340               if (group_sec == NULL)
3341                 rodata = bfd_get_section_by_name (fun->sec->owner, name);
3342               else
3343                 while (group_sec != NULL && group_sec != fun->sec)
3344                   {
3345                     if (strcmp (group_sec->name, name) == 0)
3346                       {
3347                         rodata = group_sec;
3348                         break;
3349                       }
3350                     group_sec = elf_section_data (group_sec)->next_in_group;
3351                   }
3352               fun->rodata = rodata;
3353               if (fun->rodata)
3354                 {
3355                   size += fun->rodata->size;
3356                   if (htab->params->line_size != 0
3357                       && size > htab->params->line_size)
3358                     {
3359                       size -= fun->rodata->size;
3360                       fun->rodata = NULL;
3361                     }
3362                   else
3363                     {
3364                       fun->rodata->linker_mark = 1;
3365                       fun->rodata->gc_mark = 1;
3366                       fun->rodata->flags &= ~SEC_CODE;
3367                     }
3368                 }
3369               free (name);
3370             }
3371         }
3372       if (mos_param->max_overlay_size < size)
3373         mos_param->max_overlay_size = size;
3374     }
3375
3376   for (count = 0, call = fun->call_list; call != NULL; call = call->next)
3377     count += 1;
3378
3379   if (count > 1)
3380     {
3381       struct call_info **calls = bfd_malloc (count * sizeof (*calls));
3382       if (calls == NULL)
3383         return FALSE;
3384
3385       for (count = 0, call = fun->call_list; call != NULL; call = call->next)
3386         calls[count++] = call;
3387
3388       qsort (calls, count, sizeof (*calls), sort_calls);
3389
3390       fun->call_list = NULL;
3391       while (count != 0)
3392         {
3393           --count;
3394           calls[count]->next = fun->call_list;
3395           fun->call_list = calls[count];
3396         }
3397       free (calls);
3398     }
3399
3400   for (call = fun->call_list; call != NULL; call = call->next)
3401     {
3402       if (call->is_pasted)
3403         {
3404           /* There can only be one is_pasted call per function_info.  */
3405           BFD_ASSERT (!fun->sec->segment_mark);
3406           fun->sec->segment_mark = 1;
3407         }
3408       if (!mark_overlay_section (call->fun, info, param))
3409         return FALSE;
3410     }
3411
3412   /* Don't put entry code into an overlay.  The overlay manager needs
3413      a stack!  Also, don't mark .ovl.init as an overlay.  */
3414   if (fun->lo + fun->sec->output_offset + fun->sec->output_section->vma
3415       == info->output_bfd->start_address
3416       || strncmp (fun->sec->output_section->name, ".ovl.init", 9) == 0)
3417     {
3418       fun->sec->linker_mark = 0;
3419       if (fun->rodata != NULL)
3420         fun->rodata->linker_mark = 0;
3421     }
3422   return TRUE;
3423 }
3424
3425 /* If non-zero then unmark functions called from those within sections
3426    that we need to unmark.  Unfortunately this isn't reliable since the
3427    call graph cannot know the destination of function pointer calls.  */
3428 #define RECURSE_UNMARK 0
3429
3430 struct _uos_param {
3431   asection *exclude_input_section;
3432   asection *exclude_output_section;
3433   unsigned long clearing;
3434 };
3435
3436 /* Undo some of mark_overlay_section's work.  */
3437
3438 static bfd_boolean
3439 unmark_overlay_section (struct function_info *fun,
3440                         struct bfd_link_info *info,
3441                         void *param)
3442 {
3443   struct call_info *call;
3444   struct _uos_param *uos_param = param;
3445   unsigned int excluded = 0;
3446
3447   if (fun->visit5)
3448     return TRUE;
3449
3450   fun->visit5 = TRUE;
3451
3452   excluded = 0;
3453   if (fun->sec == uos_param->exclude_input_section
3454       || fun->sec->output_section == uos_param->exclude_output_section)
3455     excluded = 1;
3456
3457   if (RECURSE_UNMARK)
3458     uos_param->clearing += excluded;
3459
3460   if (RECURSE_UNMARK ? uos_param->clearing : excluded)
3461     {
3462       fun->sec->linker_mark = 0;
3463       if (fun->rodata)
3464         fun->rodata->linker_mark = 0;
3465     }
3466
3467   for (call = fun->call_list; call != NULL; call = call->next)
3468     if (!unmark_overlay_section (call->fun, info, param))
3469       return FALSE;
3470
3471   if (RECURSE_UNMARK)
3472     uos_param->clearing -= excluded;
3473   return TRUE;
3474 }
3475
3476 struct _cl_param {
3477   unsigned int lib_size;
3478   asection **lib_sections;
3479 };
3480
3481 /* Add sections we have marked as belonging to overlays to an array
3482    for consideration as non-overlay sections.  The array consist of
3483    pairs of sections, (text,rodata), for functions in the call graph.  */
3484
3485 static bfd_boolean
3486 collect_lib_sections (struct function_info *fun,
3487                       struct bfd_link_info *info,
3488                       void *param)
3489 {
3490   struct _cl_param *lib_param = param;
3491   struct call_info *call;
3492   unsigned int size;
3493
3494   if (fun->visit6)
3495     return TRUE;
3496
3497   fun->visit6 = TRUE;
3498   if (!fun->sec->linker_mark || !fun->sec->gc_mark || fun->sec->segment_mark)
3499     return TRUE;
3500
3501   size = fun->sec->size;
3502   if (fun->rodata)
3503     size += fun->rodata->size;
3504
3505   if (size <= lib_param->lib_size)
3506     {
3507       *lib_param->lib_sections++ = fun->sec;
3508       fun->sec->gc_mark = 0;
3509       if (fun->rodata && fun->rodata->linker_mark && fun->rodata->gc_mark)
3510         {
3511           *lib_param->lib_sections++ = fun->rodata;
3512           fun->rodata->gc_mark = 0;
3513         }
3514       else
3515         *lib_param->lib_sections++ = NULL;
3516     }
3517
3518   for (call = fun->call_list; call != NULL; call = call->next)
3519     collect_lib_sections (call->fun, info, param);
3520
3521   return TRUE;
3522 }
3523
3524 /* qsort predicate to sort sections by call count.  */
3525
3526 static int
3527 sort_lib (const void *a, const void *b)
3528 {
3529   asection *const *s1 = a;
3530   asection *const *s2 = b;
3531   struct _spu_elf_section_data *sec_data;
3532   struct spu_elf_stack_info *sinfo;
3533   int delta;
3534
3535   delta = 0;
3536   if ((sec_data = spu_elf_section_data (*s1)) != NULL
3537       && (sinfo = sec_data->u.i.stack_info) != NULL)
3538     {
3539       int i;
3540       for (i = 0; i < sinfo->num_fun; ++i)
3541         delta -= sinfo->fun[i].call_count;
3542     }
3543
3544   if ((sec_data = spu_elf_section_data (*s2)) != NULL
3545       && (sinfo = sec_data->u.i.stack_info) != NULL)
3546     {
3547       int i;
3548       for (i = 0; i < sinfo->num_fun; ++i)
3549         delta += sinfo->fun[i].call_count;
3550     }
3551
3552   if (delta != 0)
3553     return delta;
3554
3555   return s1 - s2;
3556 }
3557
3558 /* Remove some sections from those marked to be in overlays.  Choose
3559    those that are called from many places, likely library functions.  */
3560
3561 static unsigned int
3562 auto_ovl_lib_functions (struct bfd_link_info *info, unsigned int lib_size)
3563 {
3564   bfd *ibfd;
3565   asection **lib_sections;
3566   unsigned int i, lib_count;
3567   struct _cl_param collect_lib_param;
3568   struct function_info dummy_caller;
3569   struct spu_link_hash_table *htab;
3570
3571   memset (&dummy_caller, 0, sizeof (dummy_caller));
3572   lib_count = 0;
3573   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
3574     {
3575       extern const bfd_target bfd_elf32_spu_vec;
3576       asection *sec;
3577
3578       if (ibfd->xvec != &bfd_elf32_spu_vec)
3579         continue;
3580
3581       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
3582         if (sec->linker_mark
3583             && sec->size < lib_size
3584             && (sec->flags & SEC_CODE) != 0)
3585           lib_count += 1;
3586     }
3587   lib_sections = bfd_malloc (lib_count * 2 * sizeof (*lib_sections));
3588   if (lib_sections == NULL)
3589     return (unsigned int) -1;
3590   collect_lib_param.lib_size = lib_size;
3591   collect_lib_param.lib_sections = lib_sections;
3592   if (!for_each_node (collect_lib_sections, info, &collect_lib_param,
3593                       TRUE))
3594     return (unsigned int) -1;
3595   lib_count = (collect_lib_param.lib_sections - lib_sections) / 2;
3596
3597   /* Sort sections so that those with the most calls are first.  */
3598   if (lib_count > 1)
3599     qsort (lib_sections, lib_count, 2 * sizeof (*lib_sections), sort_lib);
3600
3601   htab = spu_hash_table (info);
3602   for (i = 0; i < lib_count; i++)
3603     {
3604       unsigned int tmp, stub_size;
3605       asection *sec;
3606       struct _spu_elf_section_data *sec_data;
3607       struct spu_elf_stack_info *sinfo;
3608
3609       sec = lib_sections[2 * i];
3610       /* If this section is OK, its size must be less than lib_size.  */
3611       tmp = sec->size;
3612       /* If it has a rodata section, then add that too.  */
3613       if (lib_sections[2 * i + 1])
3614         tmp += lib_sections[2 * i + 1]->size;
3615       /* Add any new overlay call stubs needed by the section.  */
3616       stub_size = 0;
3617       if (tmp < lib_size
3618           && (sec_data = spu_elf_section_data (sec)) != NULL
3619           && (sinfo = sec_data->u.i.stack_info) != NULL)
3620         {
3621           int k;
3622           struct call_info *call;
3623
3624           for (k = 0; k < sinfo->num_fun; ++k)
3625             for (call = sinfo->fun[k].call_list; call; call = call->next)
3626               if (call->fun->sec->linker_mark)
3627                 {
3628                   struct call_info *p;
3629                   for (p = dummy_caller.call_list; p; p = p->next)
3630                     if (p->fun == call->fun)
3631                       break;
3632                   if (!p)
3633                     stub_size += ovl_stub_size (htab->params->ovly_flavour);
3634                 }
3635         }
3636       if (tmp + stub_size < lib_size)
3637         {
3638           struct call_info **pp, *p;
3639
3640           /* This section fits.  Mark it as non-overlay.  */
3641           lib_sections[2 * i]->linker_mark = 0;
3642           if (lib_sections[2 * i + 1])
3643             lib_sections[2 * i + 1]->linker_mark = 0;
3644           lib_size -= tmp + stub_size;
3645           /* Call stubs to the section we just added are no longer
3646              needed.  */
3647           pp = &dummy_caller.call_list;
3648           while ((p = *pp) != NULL)
3649             if (!p->fun->sec->linker_mark)
3650               {
3651                 lib_size += ovl_stub_size (htab->params->ovly_flavour);
3652                 *pp = p->next;
3653                 free (p);
3654               }
3655             else
3656               pp = &p->next;
3657           /* Add new call stubs to dummy_caller.  */
3658           if ((sec_data = spu_elf_section_data (sec)) != NULL
3659               && (sinfo = sec_data->u.i.stack_info) != NULL)
3660             {
3661               int k;
3662               struct call_info *call;
3663
3664               for (k = 0; k < sinfo->num_fun; ++k)
3665                 for (call = sinfo->fun[k].call_list;
3666                      call;
3667                      call = call->next)
3668                   if (call->fun->sec->linker_mark)
3669                     {
3670                       struct call_info *callee;
3671                       callee = bfd_malloc (sizeof (*callee));
3672                       if (callee == NULL)
3673                         return (unsigned int) -1;
3674                       *callee = *call;
3675                       if (!insert_callee (&dummy_caller, callee))
3676                         free (callee);
3677                     }
3678             }
3679         }
3680     }
3681   while (dummy_caller.call_list != NULL)
3682     {
3683       struct call_info *call = dummy_caller.call_list;
3684       dummy_caller.call_list = call->next;
3685       free (call);
3686     }
3687   for (i = 0; i < 2 * lib_count; i++)
3688     if (lib_sections[i])
3689       lib_sections[i]->gc_mark = 1;
3690   free (lib_sections);
3691   return lib_size;
3692 }
3693
3694 /* Build an array of overlay sections.  The deepest node's section is
3695    added first, then its parent node's section, then everything called
3696    from the parent section.  The idea being to group sections to
3697    minimise calls between different overlays.  */
3698
3699 static bfd_boolean
3700 collect_overlays (struct function_info *fun,
3701                   struct bfd_link_info *info,
3702                   void *param)
3703 {
3704   struct call_info *call;
3705   bfd_boolean added_fun;
3706   asection ***ovly_sections = param;
3707
3708   if (fun->visit7)
3709     return TRUE;
3710
3711   fun->visit7 = TRUE;
3712   for (call = fun->call_list; call != NULL; call = call->next)
3713     if (!call->is_pasted)
3714       {
3715         if (!collect_overlays (call->fun, info, ovly_sections))
3716           return FALSE;
3717         break;
3718       }
3719
3720   added_fun = FALSE;
3721   if (fun->sec->linker_mark && fun->sec->gc_mark)
3722     {
3723       fun->sec->gc_mark = 0;
3724       *(*ovly_sections)++ = fun->sec;
3725       if (fun->rodata && fun->rodata->linker_mark && fun->rodata->gc_mark)
3726         {
3727           fun->rodata->gc_mark = 0;
3728           *(*ovly_sections)++ = fun->rodata;
3729         }
3730       else
3731         *(*ovly_sections)++ = NULL;
3732       added_fun = TRUE;
3733
3734       /* Pasted sections must stay with the first section.  We don't
3735          put pasted sections in the array, just the first section.
3736          Mark subsequent sections as already considered.  */
3737       if (fun->sec->segment_mark)
3738         {
3739           struct function_info *call_fun = fun;
3740           do
3741             {
3742               for (call = call_fun->call_list; call != NULL; call = call->next)
3743                 if (call->is_pasted)
3744                   {
3745                     call_fun = call->fun;
3746                     call_fun->sec->gc_mark = 0;
3747                     if (call_fun->rodata)
3748                       call_fun->rodata->gc_mark = 0;
3749                     break;
3750                   }
3751               if (call == NULL)
3752                 abort ();
3753             }
3754           while (call_fun->sec->segment_mark);
3755         }
3756     }
3757
3758   for (call = fun->call_list; call != NULL; call = call->next)
3759     if (!collect_overlays (call->fun, info, ovly_sections))
3760       return FALSE;
3761
3762   if (added_fun)
3763     {
3764       struct _spu_elf_section_data *sec_data;
3765       struct spu_elf_stack_info *sinfo;
3766
3767       if ((sec_data = spu_elf_section_data (fun->sec)) != NULL
3768           && (sinfo = sec_data->u.i.stack_info) != NULL)
3769         {
3770           int i;
3771           for (i = 0; i < sinfo->num_fun; ++i)
3772             if (!collect_overlays (&sinfo->fun[i], info, ovly_sections))
3773               return FALSE;
3774         }
3775     }
3776
3777   return TRUE;
3778 }
3779
3780 struct _sum_stack_param {
3781   size_t cum_stack;
3782   size_t overall_stack;
3783   bfd_boolean emit_stack_syms;
3784 };
3785
3786 /* Descend the call graph for FUN, accumulating total stack required.  */
3787
3788 static bfd_boolean
3789 sum_stack (struct function_info *fun,
3790            struct bfd_link_info *info,
3791            void *param)
3792 {
3793   struct call_info *call;
3794   struct function_info *max;
3795   size_t stack, cum_stack;
3796   const char *f1;
3797   bfd_boolean has_call;
3798   struct _sum_stack_param *sum_stack_param = param;
3799   struct spu_link_hash_table *htab;
3800
3801   cum_stack = fun->stack;
3802   sum_stack_param->cum_stack = cum_stack;
3803   if (fun->visit3)
3804     return TRUE;
3805
3806   has_call = FALSE;
3807   max = NULL;
3808   for (call = fun->call_list; call; call = call->next)
3809     {
3810       if (!call->is_pasted)
3811         has_call = TRUE;
3812       if (!sum_stack (call->fun, info, sum_stack_param))
3813         return FALSE;
3814       stack = sum_stack_param->cum_stack;
3815       /* Include caller stack for normal calls, don't do so for
3816          tail calls.  fun->stack here is local stack usage for
3817          this function.  */
3818       if (!call->is_tail || call->is_pasted || call->fun->start != NULL)
3819         stack += fun->stack;
3820       if (cum_stack < stack)
3821         {
3822           cum_stack = stack;
3823           max = call->fun;
3824         }
3825     }
3826
3827   sum_stack_param->cum_stack = cum_stack;
3828   stack = fun->stack;
3829   /* Now fun->stack holds cumulative stack.  */
3830   fun->stack = cum_stack;
3831   fun->visit3 = TRUE;
3832
3833   if (!fun->non_root
3834       && sum_stack_param->overall_stack < cum_stack)
3835     sum_stack_param->overall_stack = cum_stack;
3836
3837   htab = spu_hash_table (info);
3838   if (htab->params->auto_overlay)
3839     return TRUE;
3840
3841   f1 = func_name (fun);
3842   if (htab->params->stack_analysis)
3843     {
3844       if (!fun->non_root)
3845         info->callbacks->info (_("  %s: 0x%v\n"), f1, (bfd_vma) cum_stack);
3846       info->callbacks->minfo (_("%s: 0x%v 0x%v\n"),
3847                               f1, (bfd_vma) stack, (bfd_vma) cum_stack);
3848
3849       if (has_call)
3850         {
3851           info->callbacks->minfo (_("  calls:\n"));
3852           for (call = fun->call_list; call; call = call->next)
3853             if (!call->is_pasted)
3854               {
3855                 const char *f2 = func_name (call->fun);
3856                 const char *ann1 = call->fun == max ? "*" : " ";
3857                 const char *ann2 = call->is_tail ? "t" : " ";
3858
3859                 info->callbacks->minfo (_("   %s%s %s\n"), ann1, ann2, f2);
3860               }
3861         }
3862     }
3863
3864   if (sum_stack_param->emit_stack_syms)
3865     {
3866       char *name = bfd_malloc (18 + strlen (f1));
3867       struct elf_link_hash_entry *h;
3868
3869       if (name == NULL)
3870         return FALSE;
3871
3872       if (fun->global || ELF_ST_BIND (fun->u.sym->st_info) == STB_GLOBAL)
3873         sprintf (name, "__stack_%s", f1);
3874       else
3875         sprintf (name, "__stack_%x_%s", fun->sec->id & 0xffffffff, f1);
3876
3877       h = elf_link_hash_lookup (&htab->elf, name, TRUE, TRUE, FALSE);
3878       free (name);
3879       if (h != NULL
3880           && (h->root.type == bfd_link_hash_new
3881               || h->root.type == bfd_link_hash_undefined
3882               || h->root.type == bfd_link_hash_undefweak))
3883         {
3884           h->root.type = bfd_link_hash_defined;
3885           h->root.u.def.section = bfd_abs_section_ptr;
3886           h->root.u.def.value = cum_stack;
3887           h->size = 0;
3888           h->type = 0;
3889           h->ref_regular = 1;
3890           h->def_regular = 1;
3891           h->ref_regular_nonweak = 1;
3892           h->forced_local = 1;
3893           h->non_elf = 0;
3894         }
3895     }
3896
3897   return TRUE;
3898 }
3899
3900 /* SEC is part of a pasted function.  Return the call_info for the
3901    next section of this function.  */
3902
3903 static struct call_info *
3904 find_pasted_call (asection *sec)
3905 {
3906   struct _spu_elf_section_data *sec_data = spu_elf_section_data (sec);
3907   struct spu_elf_stack_info *sinfo = sec_data->u.i.stack_info;
3908   struct call_info *call;
3909   int k;
3910
3911   for (k = 0; k < sinfo->num_fun; ++k)
3912     for (call = sinfo->fun[k].call_list; call != NULL; call = call->next)
3913       if (call->is_pasted)
3914         return call;
3915   abort ();
3916   return 0;
3917 }
3918
3919 /* qsort predicate to sort bfds by file name.  */
3920
3921 static int
3922 sort_bfds (const void *a, const void *b)
3923 {
3924   bfd *const *abfd1 = a;
3925   bfd *const *abfd2 = b;
3926
3927   return strcmp ((*abfd1)->filename, (*abfd2)->filename);
3928 }
3929
3930 static unsigned int
3931 print_one_overlay_section (FILE *script,
3932                            unsigned int base,
3933                            unsigned int count,
3934                            unsigned int ovlynum,
3935                            unsigned int *ovly_map,
3936                            asection **ovly_sections,
3937                            struct bfd_link_info *info)
3938 {
3939   unsigned int j;
3940
3941   for (j = base; j < count && ovly_map[j] == ovlynum; j++)
3942     {
3943       asection *sec = ovly_sections[2 * j];
3944
3945       if (fprintf (script, "   %s%c%s (%s)\n",
3946                    (sec->owner->my_archive != NULL
3947                     ? sec->owner->my_archive->filename : ""),
3948                    info->path_separator,
3949                    sec->owner->filename,
3950                    sec->name) <= 0)
3951         return -1;
3952       if (sec->segment_mark)
3953         {
3954           struct call_info *call = find_pasted_call (sec);
3955           while (call != NULL)
3956             {
3957               struct function_info *call_fun = call->fun;
3958               sec = call_fun->sec;
3959               if (fprintf (script, "   %s%c%s (%s)\n",
3960                            (sec->owner->my_archive != NULL
3961                             ? sec->owner->my_archive->filename : ""),
3962                            info->path_separator,
3963                            sec->owner->filename,
3964                            sec->name) <= 0)
3965                 return -1;
3966               for (call = call_fun->call_list; call; call = call->next)
3967                 if (call->is_pasted)
3968                   break;
3969             }
3970         }
3971     }
3972
3973   for (j = base; j < count && ovly_map[j] == ovlynum; j++)
3974     {
3975       asection *sec = ovly_sections[2 * j + 1];
3976       if (sec != NULL
3977           && fprintf (script, "   %s%c%s (%s)\n",
3978                       (sec->owner->my_archive != NULL
3979                        ? sec->owner->my_archive->filename : ""),
3980                       info->path_separator,
3981                       sec->owner->filename,
3982                       sec->name) <= 0)
3983         return -1;
3984
3985       sec = ovly_sections[2 * j];
3986       if (sec->segment_mark)
3987         {
3988           struct call_info *call = find_pasted_call (sec);
3989           while (call != NULL)
3990             {
3991               struct function_info *call_fun = call->fun;
3992               sec = call_fun->rodata;
3993               if (sec != NULL
3994                   && fprintf (script, "   %s%c%s (%s)\n",
3995                               (sec->owner->my_archive != NULL
3996                                ? sec->owner->my_archive->filename : ""),
3997                               info->path_separator,
3998                               sec->owner->filename,
3999                               sec->name) <= 0)
4000                 return -1;
4001               for (call = call_fun->call_list; call; call = call->next)
4002                 if (call->is_pasted)
4003                   break;
4004             }
4005         }
4006     }
4007
4008   return j;
4009 }
4010
4011 /* Handle --auto-overlay.  */
4012
4013 static void spu_elf_auto_overlay (struct bfd_link_info *)
4014      ATTRIBUTE_NORETURN;
4015
4016 static void
4017 spu_elf_auto_overlay (struct bfd_link_info *info)
4018 {
4019   bfd *ibfd;
4020   bfd **bfd_arr;
4021   struct elf_segment_map *m;
4022   unsigned int fixed_size, lo, hi;
4023   struct spu_link_hash_table *htab;
4024   unsigned int base, i, count, bfd_count;
4025   unsigned int region, ovlynum;
4026   asection **ovly_sections, **ovly_p;
4027   unsigned int *ovly_map;
4028   FILE *script;
4029   unsigned int total_overlay_size, overlay_size;
4030   const char *ovly_mgr_entry;
4031   struct elf_link_hash_entry *h;
4032   struct _mos_param mos_param;
4033   struct _uos_param uos_param;
4034   struct function_info dummy_caller;
4035
4036   /* Find the extents of our loadable image.  */
4037   lo = (unsigned int) -1;
4038   hi = 0;
4039   for (m = elf_tdata (info->output_bfd)->segment_map; m != NULL; m = m->next)
4040     if (m->p_type == PT_LOAD)
4041       for (i = 0; i < m->count; i++)
4042         if (m->sections[i]->size != 0)
4043           {
4044             if (m->sections[i]->vma < lo)
4045               lo = m->sections[i]->vma;
4046             if (m->sections[i]->vma + m->sections[i]->size - 1 > hi)
4047               hi = m->sections[i]->vma + m->sections[i]->size - 1;
4048           }
4049   fixed_size = hi + 1 - lo;
4050
4051   if (!discover_functions (info))
4052     goto err_exit;
4053
4054   if (!build_call_tree (info))
4055     goto err_exit;
4056
4057   uos_param.exclude_input_section = 0;
4058   uos_param.exclude_output_section
4059     = bfd_get_section_by_name (info->output_bfd, ".interrupt");
4060
4061   htab = spu_hash_table (info);
4062   ovly_mgr_entry = "__ovly_load";
4063   if (htab->params->ovly_flavour == ovly_soft_icache)
4064     ovly_mgr_entry = "__icache_br_handler";
4065   h = elf_link_hash_lookup (&htab->elf, ovly_mgr_entry,
4066                             FALSE, FALSE, FALSE);
4067   if (h != NULL
4068       && (h->root.type == bfd_link_hash_defined
4069           || h->root.type == bfd_link_hash_defweak)
4070       && h->def_regular)
4071     {
4072       /* We have a user supplied overlay manager.  */
4073       uos_param.exclude_input_section = h->root.u.def.section;
4074     }
4075   else
4076     {
4077       /* If no user overlay manager, spu_elf_load_ovl_mgr will add our
4078          builtin version to .text, and will adjust .text size.  */
4079       fixed_size += (*htab->params->spu_elf_load_ovl_mgr) ();
4080     }
4081
4082   /* Mark overlay sections, and find max overlay section size.  */
4083   mos_param.max_overlay_size = 0;
4084   if (!for_each_node (mark_overlay_section, info, &mos_param, TRUE))
4085     goto err_exit;
4086
4087   /* We can't put the overlay manager or interrupt routines in
4088      overlays.  */
4089   uos_param.clearing = 0;
4090   if ((uos_param.exclude_input_section
4091        || uos_param.exclude_output_section)
4092       && !for_each_node (unmark_overlay_section, info, &uos_param, TRUE))
4093     goto err_exit;
4094
4095   bfd_count = 0;
4096   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
4097     ++bfd_count;
4098   bfd_arr = bfd_malloc (bfd_count * sizeof (*bfd_arr));
4099   if (bfd_arr == NULL)
4100     goto err_exit;
4101
4102   /* Count overlay sections, and subtract their sizes from "fixed_size".  */
4103   count = 0;
4104   bfd_count = 0;
4105   total_overlay_size = 0;
4106   for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link_next)
4107     {
4108       extern const bfd_target bfd_elf32_spu_vec;
4109       asection *sec;
4110       unsigned int old_count;
4111
4112       if (ibfd->xvec != &bfd_elf32_spu_vec)
4113         continue;
4114
4115       old_count = count;
4116       for (sec = ibfd->sections; sec != NULL; sec = sec->next)
4117         if (sec->linker_mark)
4118           {
4119             if ((sec->flags & SEC_CODE) != 0)
4120               count += 1;
4121             fixed_size -= sec->size;
4122             total_overlay_size += sec->size;
4123           }
4124         else if ((sec->flags & (SEC_ALLOC | SEC_LOAD)) == (SEC_ALLOC | SEC_LOAD)
4125                  && sec->output_section->owner == info->output_bfd
4126                  && strncmp (sec->output_section->name, ".ovl.init", 9) == 0)
4127           fixed_size -= sec->size;
4128       if (count != old_count)
4129         bfd_arr[bfd_count++] = ibfd;
4130     }
4131
4132   /* Since the overlay link script selects sections by file name and
4133      section name, ensure that file names are unique.  */
4134   if (bfd_count > 1)
4135     {
4136       bfd_boolean ok = TRUE;
4137
4138       qsort (bfd_arr, bfd_count, sizeof (*bfd_arr), sort_bfds);
4139       for (i = 1; i < bfd_count; ++i)
4140         if (strcmp (bfd_arr[i - 1]->filename, bfd_arr[i]->filename) == 0)
4141           {
4142             if (bfd_arr[i - 1]->my_archive == bfd_arr[i]->my_archive)
4143               {
4144                 if (bfd_arr[i - 1]->my_archive && bfd_arr[i]->my_archive)
4145                   info->callbacks->einfo (_("%s duplicated in %s\n"),
4146                                           bfd_arr[i]->filename,
4147                                           bfd_arr[i]->my_archive->filename);
4148                 else
4149                   info->callbacks->einfo (_("%s duplicated\n"),
4150                                           bfd_arr[i]->filename);
4151                 ok = FALSE;
4152               }
4153           }
4154       if (!ok)
4155         {
4156           info->callbacks->einfo (_("sorry, no support for duplicate "
4157                                     "object files in auto-overlay script\n"));
4158           bfd_set_error (bfd_error_bad_value);
4159           goto err_exit;
4160         }
4161     }
4162   free (bfd_arr);
4163
4164   if (htab->reserved == 0)
4165     {
4166       struct _sum_stack_param sum_stack_param;
4167
4168       sum_stack_param.emit_stack_syms = 0;
4169       sum_stack_param.overall_stack = 0;
4170       if (!for_each_node (sum_stack, info, &sum_stack_param, TRUE))
4171         goto err_exit;
4172       htab->reserved = sum_stack_param.overall_stack + htab->extra_stack_space;
4173     }
4174   fixed_size += htab->reserved;
4175   fixed_size += htab->non_ovly_stub * ovl_stub_size (htab->params->ovly_flavour);
4176   if (fixed_size + mos_param.max_overlay_size <= htab->local_store)
4177     {
4178       if (htab->params->ovly_flavour == ovly_soft_icache)
4179         {
4180           /* Stubs in the non-icache area are bigger.  */
4181           fixed_size += htab->non_ovly_stub * 16;
4182           /* Space for icache manager tables.
4183              a) Tag array, one quadword per cache line.
4184              - word 0: ia address of present line, init to zero.
4185              - word 1: link locator.  link_elem=stub_addr/2+locator
4186              - halfwords 4-7: head/tail pointers for linked lists.  */
4187           fixed_size += 16 << htab->num_lines_log2;
4188           /* b) Linked list elements, max_branch per line.  */
4189           fixed_size += htab->params->max_branch << (htab->num_lines_log2 + 4);
4190           /* c) Indirect branch descriptors, 8 quadwords.  */
4191           fixed_size += 8 * 16;
4192           /* d) Pointers to __ea backing store, 16 quadwords.  */
4193           fixed_size += 16 * 16;
4194         }
4195       else
4196         {
4197           /* Guess number of overlays.  Assuming overlay buffer is on
4198              average only half full should be conservative.  */
4199           ovlynum = (total_overlay_size * 2 * htab->params->num_lines
4200                      / (htab->local_store - fixed_size));
4201           /* Space for _ovly_table[], _ovly_buf_table[] and toe.  */
4202           fixed_size += ovlynum * 16 + 16 + 4 + 16;
4203         }
4204     }
4205
4206   if (fixed_size + mos_param.max_overlay_size > htab->local_store)
4207     info->callbacks->einfo (_("non-overlay size of 0x%v plus maximum overlay "
4208                               "size of 0x%v exceeds local store\n"),
4209                             (bfd_vma) fixed_size,
4210                             (bfd_vma) mos_param.max_overlay_size);
4211
4212   /* Now see if we should put some functions in the non-overlay area.  */
4213   else if (fixed_size < htab->overlay_fixed)
4214     {
4215       unsigned int max_fixed, lib_size;
4216
4217       max_fixed = htab->local_store - mos_param.max_overlay_size;
4218       if (max_fixed > htab->overlay_fixed)
4219         max_fixed = htab->overlay_fixed;
4220       lib_size = max_fixed - fixed_size;
4221       lib_size = auto_ovl_lib_functions (info, lib_size);
4222       if (lib_size == (unsigned int) -1)
4223         goto err_exit;
4224       fixed_size = max_fixed - lib_size;
4225     }
4226
4227   /* Build an array of sections, suitably sorted to place into
4228      overlays.  */
4229   ovly_sections = bfd_malloc (2 * count * sizeof (*ovly_sections));
4230   if (ovly_sections == NULL)
4231     goto err_exit;
4232   ovly_p = ovly_sections;
4233   if (!for_each_node (collect_overlays, info, &ovly_p, TRUE))
4234     goto err_exit;
4235   count = (size_t) (ovly_p - ovly_sections) / 2;
4236   ovly_map = bfd_malloc (count * sizeof (*ovly_map));
4237   if (ovly_map == NULL)
4238     goto err_exit;
4239
4240   memset (&dummy_caller, 0, sizeof (dummy_caller));
4241   overlay_size = (htab->local_store - fixed_size) / htab->params->num_lines;
4242   if (htab->params->line_size != 0)
4243     overlay_size = htab->params->line_size;
4244   base = 0;
4245   ovlynum = 0;
4246   while (base < count)
4247     {
4248       unsigned int size = 0;
4249
4250       for (i = base; i < count; i++)
4251         {
4252           asection *sec;
4253           unsigned int tmp;
4254           unsigned int num_stubs;
4255           struct call_info *call, *pasty;
4256           struct _spu_elf_section_data *sec_data;
4257           struct spu_elf_stack_info *sinfo;
4258           int k;
4259
4260           /* See whether we can add this section to the current
4261              overlay without overflowing our overlay buffer.  */
4262           sec = ovly_sections[2 * i];
4263           tmp = size + sec->size;
4264           if (ovly_sections[2 * i + 1])
4265             tmp += ovly_sections[2 * i + 1]->size;
4266           if (tmp > overlay_size)
4267             break;
4268           if (sec->segment_mark)
4269             {
4270               /* Pasted sections must stay together, so add their
4271                  sizes too.  */
4272               struct call_info *pasty = find_pasted_call (sec);
4273               while (pasty != NULL)
4274                 {
4275                   struct function_info *call_fun = pasty->fun;
4276                   tmp += call_fun->sec->size;
4277                   if (call_fun->rodata)
4278                     tmp += call_fun->rodata->size;
4279                   for (pasty = call_fun->call_list; pasty; pasty = pasty->next)
4280                     if (pasty->is_pasted)
4281                       break;
4282                 }
4283             }
4284           if (tmp > overlay_size)
4285             break;
4286
4287           /* If we add this section, we might need new overlay call
4288              stubs.  Add any overlay section calls to dummy_call.  */
4289           pasty = NULL;
4290           sec_data = spu_elf_section_data (sec);
4291           sinfo = sec_data->u.i.stack_info;
4292           for (k = 0; k < sinfo->num_fun; ++k)
4293             for (call = sinfo->fun[k].call_list; call; call = call->next)
4294               if (call->is_pasted)
4295                 {
4296                   BFD_ASSERT (pasty == NULL);
4297                   pasty = call;
4298                 }
4299               else if (call->fun->sec->linker_mark)
4300                 {
4301                   if (!copy_callee (&dummy_caller, call))
4302                     goto err_exit;
4303                 }
4304           while (pasty != NULL)
4305             {
4306               struct function_info *call_fun = pasty->fun;
4307               pasty = NULL;
4308               for (call = call_fun->call_list; call; call = call->next)
4309                 if (call->is_pasted)
4310                   {
4311                     BFD_ASSERT (pasty == NULL);
4312                     pasty = call;
4313                   }
4314                 else if (!copy_callee (&dummy_caller, call))
4315                   goto err_exit;
4316             }
4317
4318           /* Calculate call stub size.  */
4319           num_stubs = 0;
4320           for (call = dummy_caller.call_list; call; call = call->next)
4321             {
4322               unsigned int k;
4323
4324               ++num_stubs;
4325               /* If the call is within this overlay, we won't need a
4326                  stub.  */
4327               for (k = base; k < i + 1; k++)
4328                 if (call->fun->sec == ovly_sections[2 * k])
4329                   {
4330                     --num_stubs;
4331                     break;
4332                   }
4333             }
4334           if (htab->params->ovly_flavour == ovly_soft_icache
4335               && num_stubs > htab->params->max_branch)
4336             break;
4337           if (tmp + num_stubs * ovl_stub_size (htab->params->ovly_flavour)
4338               > overlay_size)
4339             break;
4340           size = tmp;
4341         }
4342
4343       if (i == base)
4344         {
4345           info->callbacks->einfo (_("%B:%A%s exceeds overlay size\n"),
4346                                   ovly_sections[2 * i]->owner,
4347                                   ovly_sections[2 * i],
4348                                   ovly_sections[2 * i + 1] ? " + rodata" : "");
4349           bfd_set_error (bfd_error_bad_value);
4350           goto err_exit;
4351         }
4352
4353       while (dummy_caller.call_list != NULL)
4354         {
4355           struct call_info *call = dummy_caller.call_list;
4356           dummy_caller.call_list = call->next;
4357           free (call);
4358         }
4359
4360       ++ovlynum;
4361       while (base < i)
4362         ovly_map[base++] = ovlynum;
4363     }
4364
4365   script = htab->params->spu_elf_open_overlay_script ();
4366
4367   if (fprintf (script, "SECTIONS\n{\n") <= 0)
4368     goto file_err;
4369
4370   if (htab->params->ovly_flavour == ovly_soft_icache)
4371     {
4372       if (fprintf (script,
4373                    " .data.icache ALIGN (16) : { *(.ovtab) *(.data.icache) }\n"
4374                    " . = ALIGN (%u);\n"
4375                    " .ovl.init : { *(.ovl.init) }\n"
4376                    " . = ABSOLUTE (ADDR (.ovl.init));\n",
4377                    htab->params->line_size) <= 0)
4378         goto file_err;
4379
4380       base = 0;
4381       ovlynum = 1;
4382       while (base < count)
4383         {
4384           unsigned int indx = ovlynum - 1;
4385           unsigned int vma, lma;
4386
4387           vma = (indx & (htab->params->num_lines - 1)) << htab->line_size_log2;
4388           lma = indx << htab->line_size_log2;
4389
4390           if (fprintf (script, " .ovly%u ABSOLUTE (ADDR (.ovl.init)) + %u "
4391                        ": AT (ALIGN (LOADADDR (.ovl.init) + SIZEOF (.ovl.init), 16) + %u) {\n",
4392                        ovlynum, vma, lma) <= 0)
4393             goto file_err;
4394
4395           base = print_one_overlay_section (script, base, count, ovlynum,
4396                                             ovly_map, ovly_sections, info);
4397           if (base == (unsigned) -1)
4398             goto file_err;
4399
4400           if (fprintf (script, "  }\n") <= 0)
4401             goto file_err;
4402
4403           ovlynum++;
4404         }
4405
4406       if (fprintf (script, " . = ABSOLUTE (ADDR (.ovl.init)) + %u;\n",
4407                    1 << (htab->num_lines_log2 + htab->line_size_log2)) <= 0)
4408         goto file_err;
4409     }
4410   else
4411     {
4412       if (fprintf (script,
4413                    " . = ALIGN (16);\n"
4414                    " .ovl.init : { *(.ovl.init) }\n"
4415                    " . = ABSOLUTE (ADDR (.ovl.init));\n") <= 0)
4416         goto file_err;
4417
4418       for (region = 1; region <= htab->params->num_lines; region++)
4419         {
4420           ovlynum = region;
4421           base = 0;
4422           while (base < count && ovly_map[base] < ovlynum)
4423             base++;
4424
4425           if (base == count)
4426             break;
4427
4428           if (region == 1)
4429             {
4430               /* We need to set lma since we are overlaying .ovl.init.  */
4431               if (fprintf (script,
4432                            " OVERLAY : AT (ALIGN (LOADADDR (.ovl.init) + SIZEOF (.ovl.init), 16))\n {\n") <= 0)
4433                 goto file_err;
4434             }
4435           else
4436             {
4437               if (fprintf (script, " OVERLAY :\n {\n") <= 0)
4438                 goto file_err;
4439             }
4440
4441           while (base < count)
4442             {
4443               if (fprintf (script, "  .ovly%u {\n", ovlynum) <= 0)
4444                 goto file_err;
4445
4446               base = print_one_overlay_section (script, base, count, ovlynum,
4447                                                 ovly_map, ovly_sections, info);
4448               if (base == (unsigned) -1)
4449                 goto file_err;
4450
4451               if (fprintf (script, "  }\n") <= 0)
4452                 goto file_err;
4453
4454               ovlynum += htab->params->num_lines;
4455               while (base < count && ovly_map[base] < ovlynum)
4456                 base++;
4457             }
4458
4459           if (fprintf (script, " }\n") <= 0)
4460             goto file_err;
4461         }
4462
4463     }
4464
4465   free (ovly_map);
4466   free (ovly_sections);
4467
4468   if (fprintf (script, "}\nINSERT BEFORE .text;\n") <= 0)
4469     goto file_err;
4470   if (fclose (script) != 0)
4471     goto file_err;
4472
4473   if (htab->params->auto_overlay & AUTO_RELINK)
4474     (*htab->params->spu_elf_relink) ();
4475
4476   xexit (0);
4477
4478  file_err:
4479   bfd_set_error (bfd_error_system_call);
4480  err_exit:
4481   info->callbacks->einfo ("%F%P: auto overlay error: %E\n");
4482   xexit (1);
4483 }
4484
4485 /* Provide an estimate of total stack required.  */
4486
4487 static bfd_boolean
4488 spu_elf_stack_analysis (struct bfd_link_info *info)
4489 {
4490   struct spu_link_hash_table *htab;
4491   struct _sum_stack_param sum_stack_param;
4492
4493   if (!discover_functions (info))
4494     return FALSE;
4495
4496   if (!build_call_tree (info))
4497     return FALSE;
4498
4499   htab = spu_hash_table (info);
4500   if (htab->params->stack_analysis)
4501     {
4502       info->callbacks->info (_("Stack size for call graph root nodes.\n"));
4503       info->callbacks->minfo (_("\nStack size for functions.  "
4504                                 "Annotations: '*' max stack, 't' tail call\n"));
4505     }
4506
4507   sum_stack_param.emit_stack_syms = htab->params->emit_stack_syms;
4508   sum_stack_param.overall_stack = 0;
4509   if (!for_each_node (sum_stack, info, &sum_stack_param, TRUE))
4510     return FALSE;
4511
4512   if (htab->params->stack_analysis)
4513     info->callbacks->info (_("Maximum stack required is 0x%v\n"),
4514                            (bfd_vma) sum_stack_param.overall_stack);
4515   return TRUE;
4516 }
4517
4518 /* Perform a final link.  */
4519
4520 static bfd_boolean
4521 spu_elf_final_link (bfd *output_bfd, struct bfd_link_info *info)
4522 {
4523   struct spu_link_hash_table *htab = spu_hash_table (info);
4524
4525   if (htab->params->auto_overlay)
4526     spu_elf_auto_overlay (info);
4527
4528   if ((htab->params->stack_analysis
4529        || (htab->params->ovly_flavour == ovly_soft_icache
4530            && htab->params->lrlive_analysis))
4531       && !spu_elf_stack_analysis (info))
4532     info->callbacks->einfo ("%X%P: stack/lrlive analysis error: %E\n");
4533
4534   if (!spu_elf_build_stubs (info))
4535     info->callbacks->einfo ("%F%P: can not build overlay stubs: %E\n");
4536
4537   return bfd_elf_final_link (output_bfd, info);
4538 }
4539
4540 /* Called when not normally emitting relocs, ie. !info->relocatable
4541    and !info->emitrelocations.  Returns a count of special relocs
4542    that need to be emitted.  */
4543
4544 static unsigned int
4545 spu_elf_count_relocs (struct bfd_link_info *info, asection *sec)
4546 {
4547   Elf_Internal_Rela *relocs;
4548   unsigned int count = 0;
4549
4550   relocs = _bfd_elf_link_read_relocs (sec->owner, sec, NULL, NULL,
4551                                       info->keep_memory);
4552   if (relocs != NULL)
4553     {
4554       Elf_Internal_Rela *rel;
4555       Elf_Internal_Rela *relend = relocs + sec->reloc_count;
4556
4557       for (rel = relocs; rel < relend; rel++)
4558         {
4559           int r_type = ELF32_R_TYPE (rel->r_info);
4560           if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4561             ++count;
4562         }
4563
4564       if (elf_section_data (sec)->relocs != relocs)
4565         free (relocs);
4566     }
4567
4568   return count;
4569 }
4570
4571 /* Apply RELOCS to CONTENTS of INPUT_SECTION from INPUT_BFD.  */
4572
4573 static int
4574 spu_elf_relocate_section (bfd *output_bfd,
4575                           struct bfd_link_info *info,
4576                           bfd *input_bfd,
4577                           asection *input_section,
4578                           bfd_byte *contents,
4579                           Elf_Internal_Rela *relocs,
4580                           Elf_Internal_Sym *local_syms,
4581                           asection **local_sections)
4582 {
4583   Elf_Internal_Shdr *symtab_hdr;
4584   struct elf_link_hash_entry **sym_hashes;
4585   Elf_Internal_Rela *rel, *relend;
4586   struct spu_link_hash_table *htab;
4587   asection *ea;
4588   int ret = TRUE;
4589   bfd_boolean emit_these_relocs = FALSE;
4590   bfd_boolean is_ea_sym;
4591   bfd_boolean stubs;
4592   unsigned int iovl = 0;
4593
4594   htab = spu_hash_table (info);
4595   stubs = (htab->stub_sec != NULL
4596            && maybe_needs_stubs (input_section));
4597   iovl = overlay_index (input_section);
4598   ea = bfd_get_section_by_name (output_bfd, "._ea");
4599   symtab_hdr = &elf_tdata (input_bfd)->symtab_hdr;
4600   sym_hashes = (struct elf_link_hash_entry **) (elf_sym_hashes (input_bfd));
4601
4602   rel = relocs;
4603   relend = relocs + input_section->reloc_count;
4604   for (; rel < relend; rel++)
4605     {
4606       int r_type;
4607       reloc_howto_type *howto;
4608       unsigned int r_symndx;
4609       Elf_Internal_Sym *sym;
4610       asection *sec;
4611       struct elf_link_hash_entry *h;
4612       const char *sym_name;
4613       bfd_vma relocation;
4614       bfd_vma addend;
4615       bfd_reloc_status_type r;
4616       bfd_boolean unresolved_reloc;
4617       bfd_boolean warned;
4618       bfd_boolean overlay_encoded;
4619       enum _stub_type stub_type;
4620
4621       r_symndx = ELF32_R_SYM (rel->r_info);
4622       r_type = ELF32_R_TYPE (rel->r_info);
4623       howto = elf_howto_table + r_type;
4624       unresolved_reloc = FALSE;
4625       warned = FALSE;
4626       h = NULL;
4627       sym = NULL;
4628       sec = NULL;
4629       if (r_symndx < symtab_hdr->sh_info)
4630         {
4631           sym = local_syms + r_symndx;
4632           sec = local_sections[r_symndx];
4633           sym_name = bfd_elf_sym_name (input_bfd, symtab_hdr, sym, sec);
4634           relocation = _bfd_elf_rela_local_sym (output_bfd, sym, &sec, rel);
4635         }
4636       else
4637         {
4638           if (sym_hashes == NULL)
4639             return FALSE;
4640
4641           h = sym_hashes[r_symndx - symtab_hdr->sh_info];
4642
4643           while (h->root.type == bfd_link_hash_indirect
4644                  || h->root.type == bfd_link_hash_warning)
4645             h = (struct elf_link_hash_entry *) h->root.u.i.link;
4646
4647           relocation = 0;
4648           if (h->root.type == bfd_link_hash_defined
4649               || h->root.type == bfd_link_hash_defweak)
4650             {
4651               sec = h->root.u.def.section;
4652               if (sec == NULL
4653                   || sec->output_section == NULL)
4654                 /* Set a flag that will be cleared later if we find a
4655                    relocation value for this symbol.  output_section
4656                    is typically NULL for symbols satisfied by a shared
4657                    library.  */
4658                 unresolved_reloc = TRUE;
4659               else
4660                 relocation = (h->root.u.def.value
4661                               + sec->output_section->vma
4662                               + sec->output_offset);
4663             }
4664           else if (h->root.type == bfd_link_hash_undefweak)
4665             ;
4666           else if (info->unresolved_syms_in_objects == RM_IGNORE
4667                    && ELF_ST_VISIBILITY (h->other) == STV_DEFAULT)
4668             ;
4669           else if (!info->relocatable
4670                    && !(r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64))
4671             {
4672               bfd_boolean err;
4673               err = (info->unresolved_syms_in_objects == RM_GENERATE_ERROR
4674                      || ELF_ST_VISIBILITY (h->other) != STV_DEFAULT);
4675               if (!info->callbacks->undefined_symbol (info,
4676                                                       h->root.root.string,
4677                                                       input_bfd,
4678                                                       input_section,
4679                                                       rel->r_offset, err))
4680                 return FALSE;
4681               warned = TRUE;
4682             }
4683           sym_name = h->root.root.string;
4684         }
4685
4686       if (sec != NULL && elf_discarded_section (sec))
4687         {
4688           /* For relocs against symbols from removed linkonce sections,
4689              or sections discarded by a linker script, we just want the
4690              section contents zeroed.  Avoid any special processing.  */
4691           _bfd_clear_contents (howto, input_bfd, contents + rel->r_offset);
4692           rel->r_info = 0;
4693           rel->r_addend = 0;
4694           continue;
4695         }
4696
4697       if (info->relocatable)
4698         continue;
4699
4700       is_ea_sym = (ea != NULL
4701                    && sec != NULL
4702                    && sec->output_section == ea);
4703       overlay_encoded = FALSE;
4704
4705       /* If this symbol is in an overlay area, we may need to relocate
4706          to the overlay stub.  */
4707       addend = rel->r_addend;
4708       if (stubs
4709           && !is_ea_sym
4710           && (stub_type = needs_ovl_stub (h, sym, sec, input_section, rel,
4711                                           contents, info)) != no_stub)
4712         {
4713           unsigned int ovl = 0;
4714           struct got_entry *g, **head;
4715
4716           if (stub_type != nonovl_stub)
4717             ovl = iovl;
4718
4719           if (h != NULL)
4720             head = &h->got.glist;
4721           else
4722             head = elf_local_got_ents (input_bfd) + r_symndx;
4723
4724           for (g = *head; g != NULL; g = g->next)
4725             if (htab->params->ovly_flavour == ovly_soft_icache
4726                 ? g->br_addr == (rel->r_offset
4727                                  + input_section->output_offset
4728                                  + input_section->output_section->vma)
4729                 : g->addend == addend && (g->ovl == ovl || g->ovl == 0))
4730               break;
4731           if (g == NULL)
4732             abort ();
4733
4734           relocation = g->stub_addr;
4735           addend = 0;
4736         }
4737       else
4738         {
4739           /* For soft icache, encode the overlay index into addresses.  */
4740           if (htab->params->ovly_flavour == ovly_soft_icache
4741               && !is_ea_sym)
4742             {
4743               unsigned int ovl = overlay_index (sec);
4744               if (ovl != 0)
4745                 {
4746                   unsigned int set_id = (ovl - 1) >> htab->num_lines_log2;
4747                   relocation += set_id << 18;
4748                   overlay_encoded = set_id != 0;
4749                 }
4750             }
4751         }
4752
4753       if (unresolved_reloc)
4754         ;
4755       else if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4756         {
4757           if (is_ea_sym)
4758             {
4759               /* ._ea is a special section that isn't allocated in SPU
4760                  memory, but rather occupies space in PPU memory as
4761                  part of an embedded ELF image.  If this reloc is
4762                  against a symbol defined in ._ea, then transform the
4763                  reloc into an equivalent one without a symbol
4764                  relative to the start of the ELF image.  */
4765               rel->r_addend += (relocation
4766                                 - ea->vma
4767                                 + elf_section_data (ea)->this_hdr.sh_offset);
4768               rel->r_info = ELF32_R_INFO (0, r_type);
4769             }
4770           emit_these_relocs = TRUE;
4771           continue;
4772         }
4773       else if (is_ea_sym)
4774         unresolved_reloc = TRUE;
4775
4776       if (unresolved_reloc)
4777         {
4778           (*_bfd_error_handler)
4779             (_("%B(%s+0x%lx): unresolvable %s relocation against symbol `%s'"),
4780              input_bfd,
4781              bfd_get_section_name (input_bfd, input_section),
4782              (long) rel->r_offset,
4783              howto->name,
4784              sym_name);
4785           ret = FALSE;
4786         }
4787
4788       r = _bfd_final_link_relocate (howto,
4789                                     input_bfd,
4790                                     input_section,
4791                                     contents,
4792                                     rel->r_offset, relocation, addend);
4793
4794       if (r != bfd_reloc_ok)
4795         {
4796           const char *msg = (const char *) 0;
4797
4798           switch (r)
4799             {
4800             case bfd_reloc_overflow:
4801               /* FIXME: We don't want to warn on most references
4802                  within an overlay to itself, but this may silence a
4803                  warning that should be reported.  */
4804               if (overlay_encoded && sec == input_section)
4805                 break;
4806               if (!((*info->callbacks->reloc_overflow)
4807                     (info, (h ? &h->root : NULL), sym_name, howto->name,
4808                      (bfd_vma) 0, input_bfd, input_section, rel->r_offset)))
4809                 return FALSE;
4810               break;
4811
4812             case bfd_reloc_undefined:
4813               if (!((*info->callbacks->undefined_symbol)
4814                     (info, sym_name, input_bfd, input_section,
4815                      rel->r_offset, TRUE)))
4816                 return FALSE;
4817               break;
4818
4819             case bfd_reloc_outofrange:
4820               msg = _("internal error: out of range error");
4821               goto common_error;
4822
4823             case bfd_reloc_notsupported:
4824               msg = _("internal error: unsupported relocation error");
4825               goto common_error;
4826
4827             case bfd_reloc_dangerous:
4828               msg = _("internal error: dangerous error");
4829               goto common_error;
4830
4831             default:
4832               msg = _("internal error: unknown error");
4833               /* fall through */
4834
4835             common_error:
4836               ret = FALSE;
4837               if (!((*info->callbacks->warning)
4838                     (info, msg, sym_name, input_bfd, input_section,
4839                      rel->r_offset)))
4840                 return FALSE;
4841               break;
4842             }
4843         }
4844     }
4845
4846   if (ret
4847       && emit_these_relocs
4848       && !info->emitrelocations)
4849     {
4850       Elf_Internal_Rela *wrel;
4851       Elf_Internal_Shdr *rel_hdr;
4852
4853       wrel = rel = relocs;
4854       relend = relocs + input_section->reloc_count;
4855       for (; rel < relend; rel++)
4856         {
4857           int r_type;
4858
4859           r_type = ELF32_R_TYPE (rel->r_info);
4860           if (r_type == R_SPU_PPU32 || r_type == R_SPU_PPU64)
4861             *wrel++ = *rel;
4862         }
4863       input_section->reloc_count = wrel - relocs;
4864       /* Backflips for _bfd_elf_link_output_relocs.  */
4865       rel_hdr = &elf_section_data (input_section)->rel_hdr;
4866       rel_hdr->sh_size = input_section->reloc_count * rel_hdr->sh_entsize;
4867       ret = 2;
4868     }
4869
4870   return ret;
4871 }
4872
4873 /* Adjust _SPUEAR_ syms to point at their overlay stubs.  */
4874
4875 static bfd_boolean
4876 spu_elf_output_symbol_hook (struct bfd_link_info *info,
4877                             const char *sym_name ATTRIBUTE_UNUSED,
4878                             Elf_Internal_Sym *sym,
4879                             asection *sym_sec ATTRIBUTE_UNUSED,
4880                             struct elf_link_hash_entry *h)
4881 {
4882   struct spu_link_hash_table *htab = spu_hash_table (info);
4883
4884   if (!info->relocatable
4885       && htab->stub_sec != NULL
4886       && h != NULL
4887       && (h->root.type == bfd_link_hash_defined
4888           || h->root.type == bfd_link_hash_defweak)
4889       && h->def_regular
4890       && strncmp (h->root.root.string, "_SPUEAR_", 8) == 0)
4891     {
4892       struct got_entry *g;
4893
4894       for (g = h->got.glist; g != NULL; g = g->next)
4895         if (htab->params->ovly_flavour == ovly_soft_icache
4896             ? g->br_addr == g->stub_addr
4897             : g->addend == 0 && g->ovl == 0)
4898           {
4899             sym->st_shndx = (_bfd_elf_section_from_bfd_section
4900                              (htab->stub_sec[0]->output_section->owner,
4901                               htab->stub_sec[0]->output_section));
4902             sym->st_value = g->stub_addr;
4903             break;
4904           }
4905     }
4906
4907   return TRUE;
4908 }
4909
4910 static int spu_plugin = 0;
4911
4912 void
4913 spu_elf_plugin (int val)
4914 {
4915   spu_plugin = val;
4916 }
4917
4918 /* Set ELF header e_type for plugins.  */
4919
4920 static void
4921 spu_elf_post_process_headers (bfd *abfd,
4922                               struct bfd_link_info *info ATTRIBUTE_UNUSED)
4923 {
4924   if (spu_plugin)
4925     {
4926       Elf_Internal_Ehdr *i_ehdrp = elf_elfheader (abfd);
4927
4928       i_ehdrp->e_type = ET_DYN;
4929     }
4930 }
4931
4932 /* We may add an extra PT_LOAD segment for .toe.  We also need extra
4933    segments for overlays.  */
4934
4935 static int
4936 spu_elf_additional_program_headers (bfd *abfd, struct bfd_link_info *info)
4937 {
4938   int extra = 0;
4939   asection *sec;
4940
4941   if (info != NULL)
4942     {
4943       struct spu_link_hash_table *htab = spu_hash_table (info);
4944       extra = htab->num_overlays;
4945     }
4946
4947   if (extra)
4948     ++extra;
4949
4950   sec = bfd_get_section_by_name (abfd, ".toe");
4951   if (sec != NULL && (sec->flags & SEC_LOAD) != 0)
4952     ++extra;
4953
4954   return extra;
4955 }
4956
4957 /* Remove .toe section from other PT_LOAD segments and put it in
4958    a segment of its own.  Put overlays in separate segments too.  */
4959
4960 static bfd_boolean
4961 spu_elf_modify_segment_map (bfd *abfd, struct bfd_link_info *info)
4962 {
4963   asection *toe, *s;
4964   struct elf_segment_map *m;
4965   unsigned int i;
4966
4967   if (info == NULL)
4968     return TRUE;
4969
4970   toe = bfd_get_section_by_name (abfd, ".toe");
4971   for (m = elf_tdata (abfd)->segment_map; m != NULL; m = m->next)
4972     if (m->p_type == PT_LOAD && m->count > 1)
4973       for (i = 0; i < m->count; i++)
4974         if ((s = m->sections[i]) == toe
4975             || spu_elf_section_data (s)->u.o.ovl_index != 0)
4976           {
4977             struct elf_segment_map *m2;
4978             bfd_vma amt;
4979
4980             if (i + 1 < m->count)
4981               {
4982                 amt = sizeof (struct elf_segment_map);
4983                 amt += (m->count - (i + 2)) * sizeof (m->sections[0]);
4984                 m2 = bfd_zalloc (abfd, amt);
4985                 if (m2 == NULL)
4986                   return FALSE;
4987                 m2->count = m->count - (i + 1);
4988                 memcpy (m2->sections, m->sections + i + 1,
4989                         m2->count * sizeof (m->sections[0]));
4990                 m2->p_type = PT_LOAD;
4991                 m2->next = m->next;
4992                 m->next = m2;
4993               }
4994             m->count = 1;
4995             if (i != 0)
4996               {
4997                 m->count = i;
4998                 amt = sizeof (struct elf_segment_map);
4999                 m2 = bfd_zalloc (abfd, amt);
5000                 if (m2 == NULL)
5001                   return FALSE;
5002                 m2->p_type = PT_LOAD;
5003                 m2->count = 1;
5004                 m2->sections[0] = s;
5005                 m2->next = m->next;
5006                 m->next = m2;
5007               }
5008             break;
5009           }
5010
5011   return TRUE;
5012 }
5013
5014 /* Tweak the section type of .note.spu_name.  */
5015
5016 static bfd_boolean
5017 spu_elf_fake_sections (bfd *obfd ATTRIBUTE_UNUSED,
5018                        Elf_Internal_Shdr *hdr,
5019                        asection *sec)
5020 {
5021   if (strcmp (sec->name, SPU_PTNOTE_SPUNAME) == 0)
5022     hdr->sh_type = SHT_NOTE;
5023   return TRUE;
5024 }
5025
5026 /* Tweak phdrs before writing them out.  */
5027
5028 static int
5029 spu_elf_modify_program_headers (bfd *abfd, struct bfd_link_info *info)
5030 {
5031   const struct elf_backend_data *bed;
5032   struct elf_obj_tdata *tdata;
5033   Elf_Internal_Phdr *phdr, *last;
5034   struct spu_link_hash_table *htab;
5035   unsigned int count;
5036   unsigned int i;
5037
5038   if (info == NULL)
5039     return TRUE;
5040
5041   bed = get_elf_backend_data (abfd);
5042   tdata = elf_tdata (abfd);
5043   phdr = tdata->phdr;
5044   count = tdata->program_header_size / bed->s->sizeof_phdr;
5045   htab = spu_hash_table (info);
5046   if (htab->num_overlays != 0)
5047     {
5048       struct elf_segment_map *m;
5049       unsigned int o;
5050
5051       for (i = 0, m = elf_tdata (abfd)->segment_map; m; ++i, m = m->next)
5052         if (m->count != 0
5053             && (o = spu_elf_section_data (m->sections[0])->u.o.ovl_index) != 0)
5054           {
5055             /* Mark this as an overlay header.  */
5056             phdr[i].p_flags |= PF_OVERLAY;
5057
5058             if (htab->ovtab != NULL && htab->ovtab->size != 0
5059                 && htab->params->ovly_flavour != ovly_soft_icache)
5060               {
5061                 bfd_byte *p = htab->ovtab->contents;
5062                 unsigned int off = o * 16 + 8;
5063
5064                 /* Write file_off into _ovly_table.  */
5065                 bfd_put_32 (htab->ovtab->owner, phdr[i].p_offset, p + off);
5066               }
5067           }
5068       /* Soft-icache has its file offset put in .ovl.init.  */
5069       if (htab->init != NULL && htab->init->size != 0)
5070         {
5071           bfd_vma val = elf_section_data (htab->ovl_sec[0])->this_hdr.sh_offset;
5072
5073           bfd_put_32 (htab->init->owner, val, htab->init->contents + 4);
5074         }
5075     }
5076
5077   /* Round up p_filesz and p_memsz of PT_LOAD segments to multiples
5078      of 16.  This should always be possible when using the standard
5079      linker scripts, but don't create overlapping segments if
5080      someone is playing games with linker scripts.  */
5081   last = NULL;
5082   for (i = count; i-- != 0; )
5083     if (phdr[i].p_type == PT_LOAD)
5084       {
5085         unsigned adjust;
5086
5087         adjust = -phdr[i].p_filesz & 15;
5088         if (adjust != 0
5089             && last != NULL
5090             && phdr[i].p_offset + phdr[i].p_filesz > last->p_offset - adjust)
5091           break;
5092
5093         adjust = -phdr[i].p_memsz & 15;
5094         if (adjust != 0
5095             && last != NULL
5096             && phdr[i].p_filesz != 0
5097             && phdr[i].p_vaddr + phdr[i].p_memsz > last->p_vaddr - adjust
5098             && phdr[i].p_vaddr + phdr[i].p_memsz <= last->p_vaddr)
5099           break;
5100
5101         if (phdr[i].p_filesz != 0)
5102           last = &phdr[i];
5103       }
5104
5105   if (i == (unsigned int) -1)
5106     for (i = count; i-- != 0; )
5107       if (phdr[i].p_type == PT_LOAD)
5108         {
5109         unsigned adjust;
5110
5111         adjust = -phdr[i].p_filesz & 15;
5112         phdr[i].p_filesz += adjust;
5113
5114         adjust = -phdr[i].p_memsz & 15;
5115         phdr[i].p_memsz += adjust;
5116       }
5117
5118   return TRUE;
5119 }
5120
5121 #define TARGET_BIG_SYM          bfd_elf32_spu_vec
5122 #define TARGET_BIG_NAME         "elf32-spu"
5123 #define ELF_ARCH                bfd_arch_spu
5124 #define ELF_MACHINE_CODE        EM_SPU
5125 /* This matches the alignment need for DMA.  */
5126 #define ELF_MAXPAGESIZE         0x80
5127 #define elf_backend_rela_normal         1
5128 #define elf_backend_can_gc_sections     1
5129
5130 #define bfd_elf32_bfd_reloc_type_lookup         spu_elf_reloc_type_lookup
5131 #define bfd_elf32_bfd_reloc_name_lookup spu_elf_reloc_name_lookup
5132 #define elf_info_to_howto                       spu_elf_info_to_howto
5133 #define elf_backend_count_relocs                spu_elf_count_relocs
5134 #define elf_backend_relocate_section            spu_elf_relocate_section
5135 #define elf_backend_symbol_processing           spu_elf_backend_symbol_processing
5136 #define elf_backend_link_output_symbol_hook     spu_elf_output_symbol_hook
5137 #define elf_backend_object_p                    spu_elf_object_p
5138 #define bfd_elf32_new_section_hook              spu_elf_new_section_hook
5139 #define bfd_elf32_bfd_link_hash_table_create    spu_elf_link_hash_table_create
5140
5141 #define elf_backend_additional_program_headers  spu_elf_additional_program_headers
5142 #define elf_backend_modify_segment_map          spu_elf_modify_segment_map
5143 #define elf_backend_modify_program_headers      spu_elf_modify_program_headers
5144 #define elf_backend_post_process_headers        spu_elf_post_process_headers
5145 #define elf_backend_fake_sections               spu_elf_fake_sections
5146 #define elf_backend_special_sections            spu_elf_special_sections
5147 #define bfd_elf32_bfd_final_link                spu_elf_final_link
5148
5149 #include "elf32-target.h"