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