/* SPU specific support for 32-bit ELF

   Copyright (C) 2006-2025 Free Software Foundation, Inc.

   This file is part of BFD, the Binary File Descriptor library.

   This program is free software; you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; either version 3 of the License, or

   (at your option) any later version.

   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License along

   with this program; if not, write to the Free Software Foundation, Inc.,

   51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.  */

#include "sysdep.h"

#include "libiberty.h"

#include "bfd.h"

#include "bfdlink.h"

#include "libbfd.h"

#include "elf-bfd.h"

#include "elf/spu.h"

#include "elf32-spu.h"

/* All users of this file have bfd_octets_per_byte (abfd, sec) == 1.  */

#define OCTETS_PER_BYTE(ABFD, SEC) 1

/* We use RELA style relocs.  Don't define USE_REL.  */

static bfd_reloc_status_type spu_elf_rel9 (bfd *, arelent *, asymbol *,

             void *, asection *,

             bfd *, char **);

/* Values of type 'enum elf_spu_reloc_type' are used to index this

   array, so it must be declared in the order of that type.  */

static reloc_howto_type elf_howto_table[] = {

  HOWTO (R_SPU_NONE,     0, 0,  0, false,  0, complain_overflow_dont,

   bfd_elf_generic_reloc, "SPU_NONE",

   false, 0, 0x00000000, false),

  HOWTO (R_SPU_ADDR10,     4, 4, 10, false, 14, complain_overflow_bitfield,

   bfd_elf_generic_reloc, "SPU_ADDR10",

   false, 0, 0x00ffc000, false),

  HOWTO (R_SPU_ADDR16,     2, 4, 16, false,  7, complain_overflow_bitfield,

   bfd_elf_generic_reloc, "SPU_ADDR16",

   false, 0, 0x007fff80, false),

  HOWTO (R_SPU_ADDR16_HI, 16, 4, 16, false,  7, complain_overflow_bitfield,

   bfd_elf_generic_reloc, "SPU_ADDR16_HI",

   false, 0, 0x007fff80, false),

  HOWTO (R_SPU_ADDR16_LO,  0, 4, 16, false,  7, complain_overflow_dont,

   bfd_elf_generic_reloc, "SPU_ADDR16_LO",

   false, 0, 0x007fff80, false),

  HOWTO (R_SPU_ADDR18,     0, 4, 18, false,  7, complain_overflow_bitfield,

   bfd_elf_generic_reloc, "SPU_ADDR18",

   false, 0, 0x01ffff80, false),

  HOWTO (R_SPU_ADDR32,     0, 4, 32, false,  0, complain_overflow_dont,

   bfd_elf_generic_reloc, "SPU_ADDR32",

   false, 0, 0xffffffff, false),

  HOWTO (R_SPU_REL16,    2, 4, 16,  true,  7, complain_overflow_bitfield,

   bfd_elf_generic_reloc, "SPU_REL16",

   false, 0, 0x007fff80, true),

  HOWTO (R_SPU_ADDR7,    0, 4,  7, false, 14, complain_overflow_dont,

   bfd_elf_generic_reloc, "SPU_ADDR7",

   false, 0, 0x001fc000, false),

  HOWTO (R_SPU_REL9,     2, 4,  9,  true,  0, complain_overflow_signed,

   spu_elf_rel9,    "SPU_REL9",

   false, 0, 0x0180007f, true),

  HOWTO (R_SPU_REL9I,    2, 4,  9,  true,  0, complain_overflow_signed,

   spu_elf_rel9,    "SPU_REL9I",

   false, 0, 0x0000c07f, true),

  HOWTO (R_SPU_ADDR10I,    0, 4, 10, false, 14, complain_overflow_signed,

   bfd_elf_generic_reloc, "SPU_ADDR10I",

   false, 0, 0x00ffc000, false),

  HOWTO (R_SPU_ADDR16I,    0, 4, 16, false,  7, complain_overflow_signed,

   bfd_elf_generic_reloc, "SPU_ADDR16I",

   false, 0, 0x007fff80, false),

  HOWTO (R_SPU_REL32,    0, 4, 32, true,  0, complain_overflow_dont,

   bfd_elf_generic_reloc, "SPU_REL32",

   false, 0, 0xffffffff, true),

  HOWTO (R_SPU_ADDR16X,    0, 4, 16, false,  7, complain_overflow_bitfield,

   bfd_elf_generic_reloc, "SPU_ADDR16X",

   false, 0, 0x007fff80, false),

  HOWTO (R_SPU_PPU32,    0, 4, 32, false,  0, complain_overflow_dont,

   bfd_elf_generic_reloc, "SPU_PPU32",

   false, 0, 0xffffffff, false),

  HOWTO (R_SPU_PPU64,    0, 8, 64, false,  0, complain_overflow_dont,

   bfd_elf_generic_reloc, "SPU_PPU64",

   false, 0, -1, false),

  HOWTO (R_SPU_ADD_PIC,    0, 0,  0, false,  0, complain_overflow_dont,

   bfd_elf_generic_reloc, "SPU_ADD_PIC",

   false, 0, 0x00000000, false),

};

static struct bfd_elf_special_section const spu_elf_special_sections[] = {

  { "._ea", 4, 0, SHT_PROGBITS, SHF_WRITE },

  { ".toe", 4, 0, SHT_NOBITS, SHF_ALLOC },

  { NULL, 0, 0, 0, 0 }

};

static enum elf_spu_reloc_type

spu_elf_bfd_to_reloc_type (bfd_reloc_code_real_type code)

{

  switch (code)

    {

    default:

      return (enum elf_spu_reloc_type) -1;

    case BFD_RELOC_NONE:

      return R_SPU_NONE;

    case BFD_RELOC_SPU_IMM10W:

      return R_SPU_ADDR10;

    case BFD_RELOC_SPU_IMM16W:

      return R_SPU_ADDR16;

    case BFD_RELOC_SPU_LO16:

      return R_SPU_ADDR16_LO;

    case BFD_RELOC_SPU_HI16:

      return R_SPU_ADDR16_HI;

    case BFD_RELOC_SPU_IMM18:

      return R_SPU_ADDR18;

    case BFD_RELOC_SPU_PCREL16:

      return R_SPU_REL16;

    case BFD_RELOC_SPU_IMM7:

      return R_SPU_ADDR7;

    case BFD_RELOC_SPU_IMM8:

      return R_SPU_NONE;

    case BFD_RELOC_SPU_PCREL9a:

      return R_SPU_REL9;

    case BFD_RELOC_SPU_PCREL9b:

      return R_SPU_REL9I;

    case BFD_RELOC_SPU_IMM10:

      return R_SPU_ADDR10I;

    case BFD_RELOC_SPU_IMM16:

      return R_SPU_ADDR16I;

    case BFD_RELOC_32:

      return R_SPU_ADDR32;

    case BFD_RELOC_32_PCREL:

      return R_SPU_REL32;

    case BFD_RELOC_SPU_PPU32:

      return R_SPU_PPU32;

    case BFD_RELOC_SPU_PPU64:

      return R_SPU_PPU64;

    case BFD_RELOC_SPU_ADD_PIC:

      return R_SPU_ADD_PIC;

    }

}

static bool

spu_elf_info_to_howto (bfd *abfd,

           arelent *cache_ptr,

           Elf_Internal_Rela *dst)

{

  enum elf_spu_reloc_type r_type;

  r_type = (enum elf_spu_reloc_type) ELF32_R_TYPE (dst->r_info);

  /* PR 17512: file: 90c2a92e.  */

  if (r_type >= R_SPU_max)

    {

      /* xgettext:c-format */

      _bfd_error_handler (_("%pB: unsupported relocation type %#x"),

        abfd, r_type);

      bfd_set_error (bfd_error_bad_value);

      return false;

    }

  cache_ptr->howto = &elf_howto_table[(int) r_type];

  return true;

}

static reloc_howto_type *

spu_elf_reloc_type_lookup (bfd *abfd ATTRIBUTE_UNUSED,

         bfd_reloc_code_real_type code)

{

  enum elf_spu_reloc_type r_type = spu_elf_bfd_to_reloc_type (code);

  if (r_type == (enum elf_spu_reloc_type) -1)

    return NULL;

  return elf_howto_table + r_type;

}

static reloc_howto_type *

spu_elf_reloc_name_lookup (bfd *abfd ATTRIBUTE_UNUSED,

         const char *r_name)

{

  unsigned int i;

  for (i = 0; i < sizeof (elf_howto_table) / sizeof (elf_howto_table[0]); i++)

    if (elf_howto_table[i].name != NULL

  && strcasecmp (elf_howto_table[i].name, r_name) == 0)

      return &elf_howto_table[i];

  return NULL;

}

/* Apply R_SPU_REL9 and R_SPU_REL9I relocs.  */

static bfd_reloc_status_type

spu_elf_rel9 (bfd *abfd, arelent *reloc_entry, asymbol *symbol,

        void *data, asection *input_section,

        bfd *output_bfd, char **error_message)

{

  bfd_size_type octets;

  bfd_vma val;

  long insn;

  /* If this is a relocatable link (output_bfd test tells us), just

     call the generic function.  Any adjustment will be done at final

     link time.  */

  if (output_bfd != NULL)

    return bfd_elf_generic_reloc (abfd, reloc_entry, symbol, data,

          input_section, output_bfd, error_message);

  if (reloc_entry->address > bfd_get_section_limit (abfd, input_section))

    return bfd_reloc_outofrange;

  octets = reloc_entry->address * OCTETS_PER_BYTE (abfd, input_section);

  /* Get symbol value.  */

  val = 0;

  if (!bfd_is_com_section (symbol->section))

    val = symbol->value;

  if (symbol->section->output_section)

    val += symbol->section->output_section->vma;

  val += reloc_entry->addend;

  /* Make it pc-relative.  */

  val -= input_section->output_section->vma + input_section->output_offset;

  val >>= 2;

  if (val + 256 >= 512)

    return bfd_reloc_overflow;

  insn = bfd_get_32 (abfd, (bfd_byte *) data + octets);

  /* Move two high bits of value to REL9I and REL9 position.

     The mask will take care of selecting the right field.  */

  val = (val & 0x7f) | ((val & 0x180) << 7) | ((val & 0x180) << 16);

  insn &= ~reloc_entry->howto->dst_mask;

  insn |= val & reloc_entry->howto->dst_mask;

  bfd_put_32 (abfd, insn, (bfd_byte *) data + octets);

  return bfd_reloc_ok;

}

static bool

spu_elf_new_section_hook (bfd *abfd, asection *sec)

{

  struct _spu_elf_section_data *sdata;

  sdata = bfd_zalloc (abfd, sizeof (*sdata));

  if (sdata == NULL)

    return false;

  sec->used_by_bfd = sdata;

  return _bfd_elf_new_section_hook (abfd, sec);

}

/* Set up overlay info for executables.  */

static bool

spu_elf_object_p (bfd *abfd)

{

  if ((abfd->flags & (EXEC_P | DYNAMIC)) != 0)

    {

      unsigned int i, num_ovl, num_buf;

      Elf_Internal_Phdr *phdr = elf_tdata (abfd)->phdr;

      Elf_Internal_Ehdr *ehdr = elf_elfheader (abfd);

      Elf_Internal_Phdr *last_phdr = NULL;

      for (num_buf = 0, num_ovl = 0, i = 0; i < ehdr->e_phnum; i++, phdr++)

  if (phdr->p_type == PT_LOAD && (phdr->p_flags & PF_OVERLAY) != 0)

    {

      unsigned int j;

      ++num_ovl;

      if (last_phdr == NULL

    || ((last_phdr->p_vaddr ^ phdr->p_vaddr) & 0x3ffff) != 0)

        ++num_buf;

      last_phdr = phdr;

      for (j = 1; j < elf_numsections (abfd); j++)

        {

    Elf_Internal_Shdr *shdr = elf_elfsections (abfd)[j];

    if (shdr->bfd_section != NULL

        && ELF_SECTION_SIZE (shdr, phdr) != 0

        && ELF_SECTION_IN_SEGMENT (shdr, phdr))

      {

        asection *sec = shdr->bfd_section;

        spu_elf_section_data (sec)->u.o.ovl_index = num_ovl;

        spu_elf_section_data (sec)->u.o.ovl_buf = num_buf;

      }

        }

    }

    }

  return true;

}

/* Specially mark defined symbols named _EAR_* with BSF_KEEP so that

   strip --strip-unneeded will not remove them.  */

static void

spu_elf_backend_symbol_processing (bfd *abfd ATTRIBUTE_UNUSED, asymbol *sym)

{

  if (sym->name != NULL

      && sym->section != bfd_abs_section_ptr

      && startswith (sym->name, "_EAR_"))

    sym->flags |= BSF_KEEP;

}

/* SPU ELF linker hash table.  */

struct spu_link_hash_table

{

  struct elf_link_hash_table elf;

  struct spu_elf_params *params;

  /* Shortcuts to overlay sections.  */

  asection *ovtab;

  asection *init;

  asection *toe;

  asection **ovl_sec;

  /* Count of stubs in each overlay section.  */

  unsigned int *stub_count;

  /* The stub section for each overlay section.  */

  asection **stub_sec;

  struct elf_link_hash_entry *ovly_entry[2];

  /* Number of overlay buffers.  */

  unsigned int num_buf;

  /* Total number of overlays.  */

  unsigned int num_overlays;

  /* For soft icache.  */

  unsigned int line_size_log2;

  unsigned int num_lines_log2;

  unsigned int fromelem_size_log2;

  /* How much memory we have.  */

  unsigned int local_store;

  /* Count of overlay stubs needed in non-overlay area.  */

  unsigned int non_ovly_stub;

  /* Pointer to the fixup section */

  asection *sfixup;

  /* Set on error.  */

  unsigned int stub_err : 1;

};

/* Hijack the generic got fields for overlay stub accounting.  */

struct got_entry

{

  struct got_entry *next;

  unsigned int ovl;

  union {

    bfd_vma addend;

    bfd_vma br_addr;

  };

  bfd_vma stub_addr;

};

#define spu_hash_table(p) \

  ((is_elf_hash_table ((p)->hash)          \

    && elf_hash_table_id (elf_hash_table (p)) == SPU_ELF_DATA)   \

   ? (struct spu_link_hash_table *) (p)->hash : NULL)

struct call_info

{

  struct function_info *fun;

  struct call_info *next;

  unsigned int count;

  unsigned int max_depth;

  unsigned int is_tail : 1;

  unsigned int is_pasted : 1;

  unsigned int broken_cycle : 1;

  unsigned int priority : 13;

};

struct function_info

{

  /* List of functions called.  Also branches to hot/cold part of

     function.  */

  struct call_info *call_list;

  /* For hot/cold part of function, point to owner.  */

  struct function_info *start;

  /* Symbol at start of function.  */

  union {

    Elf_Internal_Sym *sym;

    struct elf_link_hash_entry *h;

  } u;

  /* Function section.  */

  asection *sec;

  asection *rodata;

  /* Where last called from, and number of sections called from.  */

  asection *last_caller;

  unsigned int call_count;

  /* Address range of (this part of) function.  */

  bfd_vma lo, hi;

  /* Offset where we found a store of lr, or -1 if none found.  */

  bfd_vma lr_store;

  /* Offset where we found the stack adjustment insn.  */

  bfd_vma sp_adjust;

  /* Stack usage.  */

  int stack;

  /* Distance from root of call tree.  Tail and hot/cold branches

     count as one deeper.  We aren't counting stack frames here.  */

  unsigned int depth;

  /* Set if global symbol.  */

  unsigned int global : 1;

  /* Set if known to be start of function (as distinct from a hunk

     in hot/cold section.  */

  unsigned int is_func : 1;

  /* Set if not a root node.  */

  unsigned int non_root : 1;

  /* Flags used during call tree traversal.  It's cheaper to replicate

     the visit flags than have one which needs clearing after a traversal.  */

  unsigned int visit1 : 1;

  unsigned int visit2 : 1;

  unsigned int marking : 1;

  unsigned int visit3 : 1;

  unsigned int visit4 : 1;

  unsigned int visit5 : 1;

  unsigned int visit6 : 1;

  unsigned int visit7 : 1;

};

struct spu_elf_stack_info

{

  int num_fun;

  int max_fun;

  /* Variable size array describing functions, one per contiguous

     address range belonging to a function.  */

  struct function_info fun[1];

};

static struct function_info *find_function (asection *, bfd_vma,

              struct bfd_link_info *);

/* Create a spu ELF linker hash table.  */

static struct bfd_link_hash_table *

spu_elf_link_hash_table_create (bfd *abfd)

{

  struct spu_link_hash_table *htab;

  htab = bfd_zmalloc (sizeof (*htab));

  if (htab == NULL)

    return NULL;

  if (!_bfd_elf_link_hash_table_init (&htab->elf, abfd,

              _bfd_elf_link_hash_newfunc,

              sizeof (struct elf_link_hash_entry)))

    {

      free (htab);

      return NULL;

    }

  htab->elf.init_got_refcount.refcount = 0;

  htab->elf.init_got_refcount.glist = NULL;

  htab->elf.init_got_offset.offset = 0;

  htab->elf.init_got_offset.glist = NULL;

  return &htab->elf.root;

}

void

spu_elf_setup (struct bfd_link_info *info, struct spu_elf_params *params)

{

  bfd_vma max_branch_log2;

  struct spu_link_hash_table *htab = spu_hash_table (info);

  htab->params = params;

  htab->line_size_log2 = bfd_log2 (htab->params->line_size);

  htab->num_lines_log2 = bfd_log2 (htab->params->num_lines);

  /* For the software i-cache, we provide a "from" list whose size

     is a power-of-two number of quadwords, big enough to hold one

     byte per outgoing branch.  Compute this number here.  */

  max_branch_log2 = bfd_log2 (htab->params->max_branch);

  htab->fromelem_size_log2 = max_branch_log2 > 4 ? max_branch_log2 - 4 : 0;

}

/* Find the symbol for the given R_SYMNDX in IBFD and set *HP and *SYMP

   to (hash, NULL) for global symbols, and (NULL, sym) for locals.  Set

   *SYMSECP to the symbol's section.  *LOCSYMSP caches local syms.  */

static bool

get_sym_h (struct elf_link_hash_entry **hp,

     Elf_Internal_Sym **symp,

     asection **symsecp,

     Elf_Internal_Sym **locsymsp,

     unsigned long r_symndx,

     bfd *ibfd)

{

  Elf_Internal_Shdr *symtab_hdr = &elf_tdata (ibfd)->symtab_hdr;

  if (r_symndx >= symtab_hdr->sh_info)

    {

      struct elf_link_hash_entry **sym_hashes = elf_sym_hashes (ibfd);

      struct elf_link_hash_entry *h;

      h = sym_hashes[r_symndx - symtab_hdr->sh_info];

      while (h->root.type == bfd_link_hash_indirect

       || h->root.type == bfd_link_hash_warning)

  h = (struct elf_link_hash_entry *) h->root.u.i.link;

      if (hp != NULL)

  *hp = h;

      if (symp != NULL)

  *symp = NULL;

      if (symsecp != NULL)

  {

    asection *symsec = NULL;

    if (h->root.type == bfd_link_hash_defined

        || h->root.type == bfd_link_hash_defweak)

      symsec = h->root.u.def.section;

    *symsecp = symsec;

  }

    }

  else

    {

      Elf_Internal_Sym *sym;

      Elf_Internal_Sym *locsyms = *locsymsp;

      if (locsyms == NULL)

  {

    locsyms = (Elf_Internal_Sym *) symtab_hdr->contents;

    if (locsyms == NULL)

      locsyms = bfd_elf_get_elf_syms (ibfd, symtab_hdr,

              symtab_hdr->sh_info,

              0, NULL, NULL, NULL);

    if (locsyms == NULL)

      return false;

    *locsymsp = locsyms;

  }

      sym = locsyms + r_symndx;

      if (hp != NULL)

  *hp = NULL;

      if (symp != NULL)

  *symp = sym;

      if (symsecp != NULL)

  *symsecp = bfd_section_from_elf_index (ibfd, sym->st_shndx);

    }

  return true;

}

/* Create the note section if not already present.  This is done early so

   that the linker maps the sections to the right place in the output.  */

bool

spu_elf_create_sections (struct bfd_link_info *info)

{

  struct spu_link_hash_table *htab = spu_hash_table (info);

  bfd *ibfd;

  for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next)

    if (bfd_get_section_by_name (ibfd, SPU_PTNOTE_SPUNAME) != NULL)

      break;

  if (ibfd == NULL)

    {

      /* Make SPU_PTNOTE_SPUNAME section.  */

      asection *s;

      size_t name_len;

      size_t size;

      bfd_byte *data;

      flagword flags;

      ibfd = info->input_bfds;

      /* This should really be SEC_LINKER_CREATED, but then we'd need

   to write out the section ourselves.  */

      flags = SEC_LOAD | SEC_READONLY | SEC_HAS_CONTENTS | SEC_IN_MEMORY;

      s = bfd_make_section_anyway_with_flags (ibfd, SPU_PTNOTE_SPUNAME, flags);

      if (s == NULL

    || !bfd_set_section_alignment (s, 4))

  return false;

      /* Because we didn't set SEC_LINKER_CREATED we need to set the

   proper section type.  */

      elf_section_type (s) = SHT_NOTE;

      name_len = strlen (bfd_get_filename (info->output_bfd)) + 1;

      size = 12 + ((sizeof (SPU_PLUGIN_NAME) + 3) & -4);

      size += (name_len + 3) & -4;

      if (!bfd_set_section_size (s, size))

  return false;

      data = bfd_zalloc (ibfd, size);

      if (data == NULL)

  return false;

      bfd_put_32 (ibfd, sizeof (SPU_PLUGIN_NAME), data + 0);

      bfd_put_32 (ibfd, name_len, data + 4);

      bfd_put_32 (ibfd, 1, data + 8);

      memcpy (data + 12, SPU_PLUGIN_NAME, sizeof (SPU_PLUGIN_NAME));

      memcpy (data + 12 + ((sizeof (SPU_PLUGIN_NAME) + 3) & -4),

        bfd_get_filename (info->output_bfd), name_len);

      s->contents = data;

      s->alloced = 1;

    }

  if (htab->params->emit_fixups)

    {

      asection *s;

      flagword flags;

      if (htab->elf.dynobj == NULL)

  htab->elf.dynobj = ibfd;

      ibfd = htab->elf.dynobj;

      flags = (SEC_LOAD | SEC_ALLOC | SEC_READONLY | SEC_HAS_CONTENTS

         | SEC_IN_MEMORY | SEC_LINKER_CREATED);

      s = bfd_make_section_anyway_with_flags (ibfd, ".fixup", flags);

      if (s == NULL || !bfd_set_section_alignment (s, 2))

  return false;

      htab->sfixup = s;

    }

  return true;

}

/* qsort predicate to sort sections by vma.  */

static int

sort_sections (const void *a, const void *b)

{

  const asection *const *s1 = a;

  const asection *const *s2 = b;

  bfd_signed_vma delta = (*s1)->vma - (*s2)->vma;

  if (delta != 0)

    return delta < 0 ? -1 : 1;

  return (*s1)->index - (*s2)->index;

}

/* Identify overlays in the output bfd, and number them.

   Returns 0 on error, 1 if no overlays, 2 if overlays.  */

int

spu_elf_find_overlays (struct bfd_link_info *info)

{

  struct spu_link_hash_table *htab = spu_hash_table (info);

  asection **alloc_sec;

  unsigned int i, n, ovl_index, num_buf;

  asection *s;

  bfd_vma ovl_end;

  static const char *const entry_names[2][2] = {

    { "__ovly_load", "__icache_br_handler" },

    { "__ovly_return", "__icache_call_handler" }

  };

  if (info->output_bfd->section_count < 2)

    return 1;

  alloc_sec

    = bfd_malloc (info->output_bfd->section_count * sizeof (*alloc_sec));

  if (alloc_sec == NULL)

    return 0;

  /* Pick out all the alloced sections.  */

  for (n = 0, s = info->output_bfd->sections; s != NULL; s = s->next)

    if ((s->flags & SEC_ALLOC) != 0

  && (s->flags & (SEC_LOAD | SEC_THREAD_LOCAL)) != SEC_THREAD_LOCAL

  && s->size != 0)

      alloc_sec[n++] = s;

  if (n == 0)

    {

      free (alloc_sec);

      return 1;

    }

  /* Sort them by vma.  */

  qsort (alloc_sec, n, sizeof (*alloc_sec), sort_sections);

  ovl_end = alloc_sec[0]->vma + alloc_sec[0]->size;

  if (htab->params->ovly_flavour == ovly_soft_icache)

    {

      unsigned int prev_buf = 0, set_id = 0;

      /* Look for an overlapping vma to find the first overlay section.  */

      bfd_vma vma_start = 0;

      for (i = 1; i < n; i++)

  {

    s = alloc_sec[i];

    if (s->vma < ovl_end)

      {

        asection *s0 = alloc_sec[i - 1];

        vma_start = s0->vma;

        ovl_end = (s0->vma

       + ((bfd_vma) 1

          << (htab->num_lines_log2 + htab->line_size_log2)));

        --i;

        break;

      }

    else

      ovl_end = s->vma + s->size;

  }

      /* Now find any sections within the cache area.  */

      for (ovl_index = 0, num_buf = 0; i < n; i++)

  {

    s = alloc_sec[i];

    if (s->vma >= ovl_end)

      break;

    /* A section in an overlay area called .ovl.init is not

       an overlay, in the sense that it might be loaded in

       by the overlay manager, but rather the initial

       section contents for the overlay buffer.  */

    if (!startswith (s->name, ".ovl.init"))

      {

        num_buf = ((s->vma - vma_start) >> htab->line_size_log2) + 1;

        set_id = (num_buf == prev_buf)? set_id + 1 : 0;

        prev_buf = num_buf;

        if ((s->vma - vma_start) & (htab->params->line_size - 1))

    {

      info->callbacks->einfo (_("%X%P: overlay section %pA "

              "does not start on a cache line\n"),

            s);

      bfd_set_error (bfd_error_bad_value);

      return 0;

    }

        else if (s->size > htab->params->line_size)

    {

      info->callbacks->einfo (_("%X%P: overlay section %pA "

              "is larger than a cache line\n"),

            s);

      bfd_set_error (bfd_error_bad_value);

      return 0;

    }

        alloc_sec[ovl_index++] = s;

        spu_elf_section_data (s)->u.o.ovl_index

    = (set_id << htab->num_lines_log2) + num_buf;

        spu_elf_section_data (s)->u.o.ovl_buf = num_buf;

      }

  }

      /* Ensure there are no more overlay sections.  */

      for ( ; i < n; i++)

  {

    s = alloc_sec[i];

    if (s->vma < ovl_end)

      {

        info->callbacks->einfo (_("%X%P: overlay section %pA "

          "is not in cache area\n"),

              alloc_sec[i-1]);

        bfd_set_error (bfd_error_bad_value);

        return 0;

      }

    else

      ovl_end = s->vma + s->size;

  }

    }

  else

    {

      /* Look for overlapping vmas.  Any with overlap must be overlays.

   Count them.  Also count the number of overlay regions.  */

      for (ovl_index = 0, num_buf = 0, i = 1; i < n; i++)

  {

    s = alloc_sec[i];

    if (s->vma < ovl_end)

      {

        asection *s0 = alloc_sec[i - 1];

        if (spu_elf_section_data (s0)->u.o.ovl_index == 0)

    {

      ++num_buf;

      if (!startswith (s0->name, ".ovl.init"))

        {

          alloc_sec[ovl_index] = s0;

          spu_elf_section_data (s0)->u.o.ovl_index = ++ovl_index;

          spu_elf_section_data (s0)->u.o.ovl_buf = num_buf;

        }

      else

        ovl_end = s->vma + s->size;

    }

        if (!startswith (s->name, ".ovl.init"))

    {

      alloc_sec[ovl_index] = s;

      spu_elf_section_data (s)->u.o.ovl_index = ++ovl_index;

      spu_elf_section_data (s)->u.o.ovl_buf = num_buf;

      if (s0->vma != s->vma)

        {

          /* xgettext:c-format */

          info->callbacks->einfo (_("%X%P: overlay sections %pA "

            "and %pA do not start at the "

            "same address\n"),

                s0, s);

          bfd_set_error (bfd_error_bad_value);

          return 0;

        }

      if (ovl_end < s->vma + s->size)

        ovl_end = s->vma + s->size;

    }

      }

    else

      ovl_end = s->vma + s->size;

  }

    }

  htab->num_overlays = ovl_index;

  htab->num_buf = num_buf;

  htab->ovl_sec = alloc_sec;

  if (ovl_index == 0)

    return 1;

  for (i = 0; i < 2; i++)

    {

      const char *name;

      struct elf_link_hash_entry *h;

      name = entry_names[i][htab->params->ovly_flavour];

      h = elf_link_hash_lookup (&htab->elf, name, true, false, false);

      if (h == NULL)

  return 0;

      if (h->root.type == bfd_link_hash_new)

  {

    h->root.type = bfd_link_hash_undefined;

    h->ref_regular = 1;

    h->ref_regular_nonweak = 1;

    h->non_elf = 0;

  }

      htab->ovly_entry[i] = h;

    }

  return 2;

}

/* Non-zero to use bra in overlay stubs rather than br.  */

#define BRA_STUBS 0

#define BRA 0x30000000

#define BRASL 0x31000000

#define BR  0x32000000

#define BRSL  0x33000000

#define NOP 0x40200000

#define LNOP  0x00200000

#define ILA 0x42000000

/* Return true for all relative and absolute branch instructions.

   bra   00110000 0..

   brasl 00110001 0..

   br    00110010 0..

   brsl  00110011 0..

   brz   00100000 0..

   brnz  00100001 0..

   brhz  00100010 0..

   brhnz 00100011 0..  */

static bool

is_branch (const unsigned char *insn)

{

  return (insn[0] & 0xec) == 0x20 && (insn[1] & 0x80) == 0;

}

/* Return true for all indirect branch instructions.

   bi     00110101 000

   bisl   00110101 001

   iret   00110101 010

   bisled 00110101 011

   biz    00100101 000

   binz   00100101 001

   bihz   00100101 010

   bihnz  00100101 011  */

static bool

is_indirect_branch (const unsigned char *insn)

{

  return (insn[0] & 0xef) == 0x25 && (insn[1] & 0x80) == 0;

}

/* Return true for branch hint instructions.

   hbra  0001000..

   hbrr  0001001..  */

static bool

is_hint (const unsigned char *insn)

{

  return (insn[0] & 0xfc) == 0x10;

}

/* True if INPUT_SECTION might need overlay stubs.  */

static bool

maybe_needs_stubs (asection *input_section)

{

  /* No stubs for debug sections and suchlike.  */

  if ((input_section->flags & SEC_ALLOC) == 0)

    return false;

  /* No stubs for link-once sections that will be discarded.  */

  if (input_section->output_section == bfd_abs_section_ptr)

    return false;

  /* Don't create stubs for .eh_frame references.  */

  if (strcmp (input_section->name, ".eh_frame") == 0)

    return false;

  return true;

}

enum _stub_type

{

  no_stub,

  call_ovl_stub,

  br000_ovl_stub,

  br001_ovl_stub,

  br010_ovl_stub,

  br011_ovl_stub,

  br100_ovl_stub,

  br101_ovl_stub,

  br110_ovl_stub,

  br111_ovl_stub,

  nonovl_stub,

  stub_error

};

/* Return non-zero if this reloc symbol should go via an overlay stub.

   Return 2 if the stub must be in non-overlay area.  */

static enum _stub_type

needs_ovl_stub (struct elf_link_hash_entry *h,

    Elf_Internal_Sym *sym,

    asection *sym_sec,