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