ld/emultempl/xtensaelf.em

   1 # This shell script emits a C file. -*- C -*-
   2 #   Copyright (C) 2003-2016 Free Software Foundation, Inc.
   3 #
   4 # This file is part of the GNU Binutils.
   5 #
   6 # This program is free software; you can redistribute it and/or modify
   7 # it under the terms of the GNU General Public License as published by
   8 # the Free Software Foundation; either version 3 of the License, or
   9 # (at your option) any later version.
  10 #
  11 # This program is distributed in the hope that it will be useful,
  12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 # GNU General Public License for more details.
  15 #
  16 # You should have received a copy of the GNU General Public License
  17 # along with this program; if not, write to the Free Software
  18 # Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
  19 # MA 02110-1301, USA.
  20 #
  21
  22 # This file is sourced from elf32.em, and defines extra xtensa-elf
  23 # specific routines.
  24 #
  25 fragment <<EOF
  26
  27 #include <xtensa-config.h>
  28 #include "../bfd/elf-bfd.h"
  29 #include "../bfd/libbfd.h"
  30 #include "elf/xtensa.h"
  31 #include "bfd.h"
  32
  33 /* Provide default values for new configuration settings.  */
  34 #ifndef XSHAL_ABI
  35 #define XSHAL_ABI 0
  36 #endif
  37
  38 static void xtensa_wild_group_interleave (lang_statement_union_type *);
  39 static void xtensa_colocate_output_literals (lang_statement_union_type *);
  40 static void xtensa_strip_inconsistent_linkonce_sections
  41   (lang_statement_list_type *);
  42
  43
  44 /* This number is irrelevant until we turn on use_literal_pages */
  45 static bfd_vma xtensa_page_power = 12; /* 4K pages.  */
  46
  47 /* To force a page break between literals and text, change
  48    xtensa_use_literal_pages to "TRUE".  */
  49 static bfd_boolean xtensa_use_literal_pages = FALSE;
  50
  51 #define EXTRA_VALIDATION 0
  52
  53
  54 static char *
  55 elf_xtensa_choose_target (int argc ATTRIBUTE_UNUSED,
  56                           char **argv ATTRIBUTE_UNUSED)
  57 {
  58   if (XCHAL_HAVE_BE)
  59     return "${BIG_OUTPUT_FORMAT}";
  60   else
  61     return "${LITTLE_OUTPUT_FORMAT}";
  62 }
  63
  64
  65 static void
  66 elf_xtensa_before_parse (void)
  67 {
  68   /* Just call the default hook.... Tensilica's version of this function
  69      does some other work that isn't relevant here.  */
  70   gld${EMULATION_NAME}_before_parse ();
  71 }
  72
  73
  74 static void
  75 remove_section (bfd *abfd, asection *os)
  76 {
  77   asection **spp;
  78   for (spp = &abfd->sections; *spp; spp = &(*spp)->next)
  79     if (*spp == os)
  80       {
  81         *spp = os->next;
  82         os->owner->section_count--;
  83         break;
  84       }
  85 }
  86
  87
  88 static bfd_boolean
  89 replace_insn_sec_with_prop_sec (bfd *abfd,
  90                                 const char *insn_sec_name,
  91                                 const char *prop_sec_name,
  92                                 char **error_message)
  93 {
  94   asection *insn_sec;
  95   asection *prop_sec;
  96   bfd_byte *prop_contents = NULL;
  97   bfd_byte *insn_contents = NULL;
  98   unsigned entry_count;
  99   unsigned entry;
 100   Elf_Internal_Shdr *rel_hdr;
 101   Elf_Internal_Rela *internal_relocs = NULL;
 102   unsigned reloc_count;
 103
 104   *error_message = "";
 105   insn_sec = bfd_get_section_by_name (abfd, insn_sec_name);
 106   if (insn_sec == NULL)
 107     return TRUE;
 108   entry_count = insn_sec->size / 8;
 109
 110   prop_sec = bfd_get_section_by_name (abfd, prop_sec_name);
 111   if (prop_sec != NULL && insn_sec != NULL)
 112     {
 113       *error_message = _("file already has property tables");
 114       return FALSE;
 115     }
 116
 117   if (insn_sec->size != 0)
 118     {
 119       insn_contents = (bfd_byte *) bfd_malloc (insn_sec->size);
 120       if (insn_contents == NULL)
 121         {
 122           *error_message = _("out of memory");
 123           goto cleanup;
 124         }
 125       if (! bfd_get_section_contents (abfd, insn_sec, insn_contents,
 126                                       (file_ptr) 0, insn_sec->size))
 127         {
 128           *error_message = _("failed to read section contents");
 129           goto cleanup;
 130         }
 131     }
 132
 133   /* Create a property table section for it.  */
 134   prop_sec_name = strdup (prop_sec_name);
 135   prop_sec = bfd_make_section_with_flags
 136     (abfd, prop_sec_name, bfd_get_section_flags (abfd, insn_sec));
 137   if (prop_sec == NULL
 138       || ! bfd_set_section_alignment (abfd, prop_sec, 2))
 139     {
 140       *error_message = _("could not create new section");
 141       goto cleanup;
 142     }
 143
 144   prop_sec->size = entry_count * 12;
 145   prop_contents = (bfd_byte *) bfd_zalloc (abfd, prop_sec->size);
 146   elf_section_data (prop_sec)->this_hdr.contents = prop_contents;
 147
 148   /* The entry size and size must be set to allow the linker to compute
 149      the number of relocations since it does not use reloc_count.  */
 150   rel_hdr = _bfd_elf_single_rel_hdr (prop_sec);
 151   rel_hdr->sh_entsize = sizeof (Elf32_External_Rela);
 152   rel_hdr->sh_size = _bfd_elf_single_rel_hdr (insn_sec)->sh_size;
 153
 154   if (prop_contents == NULL && prop_sec->size != 0)
 155     {
 156       *error_message = _("could not allocate section contents");
 157       goto cleanup;
 158     }
 159
 160   /* Read the relocations.  */
 161   reloc_count = insn_sec->reloc_count;
 162   if (reloc_count != 0)
 163     {
 164       /* If there is already an internal_reloc, then save it so that the
 165          read_relocs function freshly allocates a copy.  */
 166       Elf_Internal_Rela *saved_relocs = elf_section_data (insn_sec)->relocs;
 167
 168       elf_section_data (insn_sec)->relocs = NULL;
 169       internal_relocs =
 170         _bfd_elf_link_read_relocs (abfd, insn_sec, NULL, NULL, FALSE);
 171       elf_section_data (insn_sec)->relocs = saved_relocs;
 172
 173       if (internal_relocs == NULL)
 174         {
 175           *error_message = _("out of memory");
 176           goto cleanup;
 177         }
 178     }
 179
 180   /* Create a relocation section for the property section.  */
 181   if (internal_relocs != NULL)
 182     {
 183       elf_section_data (prop_sec)->relocs = internal_relocs;
 184       prop_sec->reloc_count = reloc_count;
 185     }
 186
 187   /* Now copy each insn table entry to the prop table entry with
 188      appropriate flags.  */
 189   for (entry = 0; entry < entry_count; ++entry)
 190     {
 191       unsigned value;
 192       unsigned flags = (XTENSA_PROP_INSN | XTENSA_PROP_NO_TRANSFORM
 193                         | XTENSA_PROP_INSN_NO_REORDER);
 194       value = bfd_get_32 (abfd, insn_contents + entry * 8 + 0);
 195       bfd_put_32 (abfd, value, prop_contents + entry * 12 + 0);
 196       value = bfd_get_32 (abfd, insn_contents + entry * 8 + 4);
 197       bfd_put_32 (abfd, value, prop_contents + entry * 12 + 4);
 198       bfd_put_32 (abfd, flags, prop_contents + entry * 12 + 8);
 199     }
 200
 201   /* Now copy all of the relocations.  Change offsets for the
 202      instruction table section to offsets in the property table
 203      section.  */
 204   if (internal_relocs)
 205     {
 206       unsigned i;
 207
 208       for (i = 0; i < reloc_count; i++)
 209         {
 210           Elf_Internal_Rela *rela;
 211           unsigned r_offset;
 212
 213           rela = &internal_relocs[i];
 214
 215           /* If this relocation is to the .xt.insn section,
 216              change the section number and the offset.  */
 217           r_offset = rela->r_offset;
 218           r_offset += 4 * (r_offset / 8);
 219           rela->r_offset = r_offset;
 220         }
 221     }
 222
 223   remove_section (abfd, insn_sec);
 224
 225   if (insn_contents)
 226     free (insn_contents);
 227
 228   return TRUE;
 229
 230  cleanup:
 231   if (prop_sec && prop_sec->owner)
 232     remove_section (abfd, prop_sec);
 233   if (insn_contents)
 234     free (insn_contents);
 235   if (internal_relocs)
 236     free (internal_relocs);
 237
 238   return FALSE;
 239 }
 240
 241
 242 #define PROP_SEC_BASE_NAME ".xt.prop"
 243 #define INSN_SEC_BASE_NAME ".xt.insn"
 244 #define LINKONCE_SEC_OLD_TEXT_BASE_NAME ".gnu.linkonce.x."
 245
 246
 247 static void
 248 replace_instruction_table_sections (bfd *abfd, asection *sec)
 249 {
 250   char *message = "";
 251   const char *insn_sec_name = NULL;
 252   char *prop_sec_name = NULL;
 253   char *owned_prop_sec_name = NULL;
 254   const char *sec_name;
 255
 256   sec_name = bfd_get_section_name (abfd, sec);
 257   if (strcmp (sec_name, INSN_SEC_BASE_NAME) == 0)
 258     {
 259       insn_sec_name = INSN_SEC_BASE_NAME;
 260       prop_sec_name = PROP_SEC_BASE_NAME;
 261     }
 262   else if (CONST_STRNEQ (sec_name, LINKONCE_SEC_OLD_TEXT_BASE_NAME))
 263     {
 264       insn_sec_name = sec_name;
 265       owned_prop_sec_name = (char *) xmalloc (strlen (sec_name) + 20);
 266       prop_sec_name = owned_prop_sec_name;
 267       strcpy (prop_sec_name, ".gnu.linkonce.prop.t.");
 268       strcat (prop_sec_name,
 269               sec_name + strlen (LINKONCE_SEC_OLD_TEXT_BASE_NAME));
 270     }
 271   if (insn_sec_name != NULL)
 272     {
 273       if (! replace_insn_sec_with_prop_sec (abfd, insn_sec_name, prop_sec_name,
 274                                             &message))
 275         {
 276           einfo (_("%P: warning: failed to convert %s table in %B (%s); subsequent disassembly may be incomplete\n"),
 277                  insn_sec_name, abfd, message);
 278         }
 279     }
 280   if (owned_prop_sec_name)
 281     free (owned_prop_sec_name);
 282 }
 283
 284
 285 /* This is called after all input sections have been opened to convert
 286    instruction tables (.xt.insn, gnu.linkonce.x.*) tables into property
 287    tables (.xt.prop) before any section placement.  */
 288
 289 static void
 290 elf_xtensa_after_open (void)
 291 {
 292   /* First call the ELF version.  */
 293   gld${EMULATION_NAME}_after_open ();
 294
 295   /* Now search the input files looking for instruction table sections.  */
 296   LANG_FOR_EACH_INPUT_STATEMENT (f)
 297     {
 298       asection *sec = f->the_bfd->sections;
 299       asection *next_sec;
 300
 301       /* Do not use bfd_map_over_sections here since we are removing
 302          sections as we iterate.  */
 303       while (sec != NULL)
 304         {
 305           next_sec = sec->next;
 306           replace_instruction_table_sections (f->the_bfd, sec);
 307           sec = next_sec;
 308         }
 309     }
 310 }
 311
 312
 313 static bfd_boolean
 314 xt_config_info_unpack_and_check (char *data,
 315                                  bfd_boolean *pmismatch,
 316                                  char **pmsg)
 317 {
 318   char *d, *key;
 319   unsigned num;
 320
 321   *pmismatch = FALSE;
 322
 323   d = data;
 324   while (*d)
 325     {
 326       key = d;
 327       d = strchr (d, '=');
 328       if (! d)
 329         goto error;
 330
 331       /* Overwrite the equal sign.  */
 332       *d++ = 0;
 333
 334       /* Check if this is a quoted string or a number.  */
 335       if (*d == '"')
 336         {
 337           /* No string values are currently checked by LD;
 338              just skip over the quotes.  */
 339           d++;
 340           d = strchr (d, '"');
 341           if (! d)
 342             goto error;
 343           /* Overwrite the trailing quote.  */
 344           *d++ = 0;
 345         }
 346       else
 347         {
 348           if (*d == 0)
 349             goto error;
 350           num = strtoul (d, &d, 0);
 351
 352           if (! strcmp (key, "ABI"))
 353             {
 354               if (num != XSHAL_ABI)
 355                 {
 356                   *pmismatch = TRUE;
 357                   *pmsg = "ABI does not match";
 358                 }
 359             }
 360           else if (! strcmp (key, "USE_ABSOLUTE_LITERALS"))
 361             {
 362               if (num != XSHAL_USE_ABSOLUTE_LITERALS)
 363                 {
 364                   *pmismatch = TRUE;
 365                   *pmsg = "incompatible use of the Extended L32R option";
 366                 }
 367             }
 368         }
 369
 370       if (*d++ != '\n')
 371         goto error;
 372     }
 373
 374   return TRUE;
 375
 376  error:
 377   return FALSE;
 378 }
 379
 380
 381 #define XTINFO_NAME "Xtensa_Info"
 382 #define XTINFO_NAMESZ 12
 383 #define XTINFO_TYPE 1
 384
 385 static void
 386 check_xtensa_info (bfd *abfd, asection *info_sec)
 387 {
 388   char *data, *errmsg = "";
 389   bfd_boolean mismatch;
 390
 391   data = xmalloc (info_sec->size);
 392   if (! bfd_get_section_contents (abfd, info_sec, data, 0, info_sec->size))
 393     einfo (_("%F%P:%B: cannot read contents of section %A\n"), abfd, info_sec);
 394
 395   if (info_sec->size > 24
 396       && info_sec->size >= 24 + bfd_get_32 (abfd, data + 4)
 397       && bfd_get_32 (abfd, data + 0) == XTINFO_NAMESZ
 398       && bfd_get_32 (abfd, data + 8) == XTINFO_TYPE
 399       && strcmp (data + 12, XTINFO_NAME) == 0
 400       && xt_config_info_unpack_and_check (data + 12 + XTINFO_NAMESZ,
 401                                           &mismatch, &errmsg))
 402     {
 403       if (mismatch)
 404         einfo (_("%P:%B: warning: incompatible Xtensa configuration (%s)\n"),
 405                abfd, errmsg);
 406     }
 407   else
 408     einfo (_("%P:%B: warning: cannot parse .xtensa.info section\n"), abfd);
 409
 410   free (data);
 411 }
 412
 413
 414 /* This is called after the sections have been attached to output
 415    sections, but before any sizes or addresses have been set.  */
 416
 417 static void
 418 elf_xtensa_before_allocation (void)
 419 {
 420   asection *info_sec, *first_info_sec;
 421   bfd *first_bfd;
 422   bfd_boolean is_big_endian = XCHAL_HAVE_BE;
 423
 424   /* Check that the output endianness matches the Xtensa
 425      configuration.  The BFD library always includes both big and
 426      little endian target vectors for Xtensa, but it only supports the
 427      detailed instruction encode/decode operations (such as are
 428      required to process relocations) for the selected Xtensa
 429      configuration.  */
 430
 431   if (is_big_endian
 432       && link_info.output_bfd->xvec->byteorder == BFD_ENDIAN_LITTLE)
 433     {
 434       einfo (_("%F%P: little endian output does not match "
 435                "Xtensa configuration\n"));
 436     }
 437   if (!is_big_endian
 438       && link_info.output_bfd->xvec->byteorder == BFD_ENDIAN_BIG)
 439     {
 440       einfo (_("%F%P: big endian output does not match "
 441                "Xtensa configuration\n"));
 442     }
 443
 444   /* Keep track of the first input .xtensa.info section, and as a fallback,
 445      the first input bfd where a .xtensa.info section could be created.
 446      After the input .xtensa.info has been checked, the contents of the
 447      first one will be replaced with the output .xtensa.info table.  */
 448   first_info_sec = 0;
 449   first_bfd = 0;
 450
 451   LANG_FOR_EACH_INPUT_STATEMENT (f)
 452     {
 453       /* Check that the endianness for each input file matches the output.
 454          The merge_private_bfd_data hook has already reported any mismatches
 455          as errors, but those errors are not fatal.  At this point, we
 456          cannot go any further if there are any mismatches.  */
 457       if ((is_big_endian && f->the_bfd->xvec->byteorder == BFD_ENDIAN_LITTLE)
 458           || (!is_big_endian && f->the_bfd->xvec->byteorder == BFD_ENDIAN_BIG))
 459         einfo (_("%F%P: cross-endian linking for %B not supported\n"),
 460                f->the_bfd);
 461
 462       if (! first_bfd)
 463         first_bfd = f->the_bfd;
 464
 465       info_sec = bfd_get_section_by_name (f->the_bfd, ".xtensa.info");
 466       if (! info_sec)
 467         continue;
 468
 469       if (! first_info_sec)
 470         first_info_sec = info_sec;
 471
 472       /* Unpack the .xtensa.info section and check it against the current
 473          Xtensa configuration.  */
 474       check_xtensa_info (f->the_bfd, info_sec);
 475
 476       /* Do not include this copy of .xtensa.info in the output.  */
 477       info_sec->size = 0;
 478       info_sec->flags |= SEC_EXCLUDE;
 479     }
 480
 481   /* Reuse the first .xtensa.info input section to hold the output
 482      .xtensa.info; or, if none were found, create a new section in the
 483      first input bfd (assuming there is one).  */
 484   info_sec = first_info_sec;
 485   if (! info_sec && first_bfd)
 486     {
 487       info_sec = bfd_make_section_with_flags (first_bfd, ".xtensa.info",
 488                                               SEC_HAS_CONTENTS | SEC_READONLY);
 489       if (! info_sec)
 490         einfo (_("%F%P: failed to create .xtensa.info section\n"));
 491     }
 492   if (info_sec)
 493     {
 494       int xtensa_info_size;
 495       char *data;
 496
 497       info_sec->flags &= ~SEC_EXCLUDE;
 498       info_sec->flags |= SEC_IN_MEMORY;
 499
 500       data = xmalloc (100);
 501       sprintf (data, "USE_ABSOLUTE_LITERALS=%d\nABI=%d\n",
 502                XSHAL_USE_ABSOLUTE_LITERALS, XSHAL_ABI);
 503       xtensa_info_size = strlen (data) + 1;
 504
 505       /* Add enough null terminators to pad to a word boundary.  */
 506       do
 507         data[xtensa_info_size++] = 0;
 508       while ((xtensa_info_size & 3) != 0);
 509
 510       info_sec->size = 12 + XTINFO_NAMESZ + xtensa_info_size;
 511       info_sec->contents = xmalloc (info_sec->size);
 512       bfd_put_32 (info_sec->owner, XTINFO_NAMESZ, info_sec->contents + 0);
 513       bfd_put_32 (info_sec->owner, xtensa_info_size, info_sec->contents + 4);
 514       bfd_put_32 (info_sec->owner, XTINFO_TYPE, info_sec->contents + 8);
 515       memcpy (info_sec->contents + 12, XTINFO_NAME, XTINFO_NAMESZ);
 516       memcpy (info_sec->contents + 12 + XTINFO_NAMESZ, data, xtensa_info_size);
 517       free (data);
 518     }
 519
 520   /* Enable relaxation by default if the "--no-relax" option was not
 521      specified.  This is done here instead of in the before_parse hook
 522      because there is a check in main() to prohibit use of --relax and
 523      -r together and that combination should be allowed for Xtensa.  */
 524   if (RELAXATION_DISABLED_BY_DEFAULT)
 525     ENABLE_RELAXATION;
 526
 527   xtensa_strip_inconsistent_linkonce_sections (stat_ptr);
 528
 529   gld${EMULATION_NAME}_before_allocation ();
 530
 531   xtensa_wild_group_interleave (stat_ptr->head);
 532
 533   if (RELAXATION_ENABLED)
 534     xtensa_colocate_output_literals (stat_ptr->head);
 535
 536   /* TBD: We need to force the page alignments to here and only do
 537      them as needed for the entire output section.  Finally, if this
 538      is a relocatable link then we need to add alignment notes so
 539      that the literals can be separated later.  */
 540 }
 541
 542
 543 typedef struct wildcard_list section_name_list;
 544
 545 typedef struct reloc_deps_e_t reloc_deps_e;
 546 typedef struct reloc_deps_section_t reloc_deps_section;
 547 typedef struct reloc_deps_graph_t reloc_deps_graph;
 548
 549
 550 struct reloc_deps_e_t
 551 {
 552   asection *src; /* Contains l32rs.  */
 553   asection *tgt; /* Contains literals.  */
 554   reloc_deps_e *next;
 555 };
 556
 557 /* Place these in the userdata field.  */
 558 struct reloc_deps_section_t
 559 {
 560   reloc_deps_e *preds;
 561   reloc_deps_e *succs;
 562   bfd_boolean is_only_literal;
 563 };
 564
 565
 566 struct reloc_deps_graph_t
 567 {
 568   size_t count;
 569   size_t size;
 570   asection **sections;
 571 };
 572
 573 static void xtensa_layout_wild
 574   (const reloc_deps_graph *, lang_wild_statement_type *);
 575
 576 typedef void (*deps_callback_t) (asection *, /* src_sec */
 577                                  bfd_vma,    /* src_offset */
 578                                  asection *, /* target_sec */
 579                                  bfd_vma,    /* target_offset */
 580                                  void *);    /* closure */
 581
 582 extern bfd_boolean xtensa_callback_required_dependence
 583   (bfd *, asection *, struct bfd_link_info *, deps_callback_t, void *);
 584 static void xtensa_ldlang_clear_addresses (lang_statement_union_type *);
 585 static bfd_boolean ld_local_file_relocations_fit
 586   (lang_statement_union_type *, const reloc_deps_graph *);
 587 static bfd_vma ld_assign_relative_paged_dot
 588   (bfd_vma, lang_statement_union_type *, const reloc_deps_graph *,
 589    bfd_boolean);
 590 static bfd_vma ld_xtensa_insert_page_offsets
 591   (bfd_vma, lang_statement_union_type *, reloc_deps_graph *, bfd_boolean);
 592 #if EXTRA_VALIDATION
 593 static size_t ld_count_children (lang_statement_union_type *);
 594 #endif
 595
 596 extern lang_statement_list_type constructor_list;
 597
 598 static reloc_deps_section *
 599 xtensa_get_section_deps (const reloc_deps_graph *deps ATTRIBUTE_UNUSED,
 600                          asection *sec)
 601 {
 602   /* We have a separate function for this so that
 603      we could in the future keep a completely independent
 604      structure that maps a section to its dependence edges.
 605      For now, we place these in the sec->userdata field.  */
 606   reloc_deps_section *sec_deps = sec->userdata;
 607   return sec_deps;
 608 }
 609
 610 static void
 611 xtensa_set_section_deps (const reloc_deps_graph *deps ATTRIBUTE_UNUSED,
 612                          asection *sec,
 613                          reloc_deps_section *deps_section)
 614 {
 615   sec->userdata = deps_section;
 616 }
 617
 618
 619 /* This is used to keep a list of all of the sections participating in
 620    the graph so we can clean them up quickly.  */
 621
 622 static void
 623 xtensa_append_section_deps (reloc_deps_graph *deps, asection *sec)
 624 {
 625   if (deps->size <= deps->count)
 626     {
 627       asection **new_sections;
 628       size_t i;
 629       size_t new_size;
 630
 631       new_size = deps->size * 2;
 632       if (new_size == 0)
 633         new_size = 20;
 634
 635       new_sections = xmalloc (sizeof (asection *) * new_size);
 636       memset (new_sections, 0, sizeof (asection *) * new_size);
 637       for (i = 0; i < deps->count; i++)
 638         {
 639           new_sections[i] = deps->sections[i];
 640         }
 641       if (deps->sections != NULL)
 642         free (deps->sections);
 643       deps->sections = new_sections;
 644       deps->size = new_size;
 645     }
 646   deps->sections[deps->count] = sec;
 647   deps->count++;
 648 }
 649
 650
 651 static void
 652 free_reloc_deps_graph (reloc_deps_graph *deps)
 653 {
 654   size_t i;
 655   for (i = 0; i < deps->count; i++)
 656     {
 657       asection *sec = deps->sections[i];
 658       reloc_deps_section *sec_deps;
 659       sec_deps = xtensa_get_section_deps (deps, sec);
 660       if (sec_deps)
 661         {
 662           reloc_deps_e *next;
 663           while (sec_deps->succs != NULL)
 664             {
 665               next = sec_deps->succs->next;
 666               free (sec_deps->succs);
 667               sec_deps->succs = next;
 668             }
 669
 670           while (sec_deps->preds != NULL)
 671             {
 672               next = sec_deps->preds->next;
 673               free (sec_deps->preds);
 674               sec_deps->preds = next;
 675             }
 676           free (sec_deps);
 677         }
 678       xtensa_set_section_deps (deps, sec, NULL);
 679     }
 680   if (deps->sections)
 681     free (deps->sections);
 682
 683   free (deps);
 684 }
 685
 686
 687 static bfd_boolean
 688 section_is_source (const reloc_deps_graph *deps ATTRIBUTE_UNUSED,
 689                    lang_statement_union_type *s)
 690 {
 691   asection *sec;
 692   const reloc_deps_section *sec_deps;
 693
 694   if (s->header.type != lang_input_section_enum)
 695     return FALSE;
 696   sec = s->input_section.section;
 697
 698   sec_deps = xtensa_get_section_deps (deps, sec);
 699   return sec_deps && sec_deps->succs != NULL;
 700 }
 701
 702
 703 static bfd_boolean
 704 section_is_target (const reloc_deps_graph *deps ATTRIBUTE_UNUSED,
 705                    lang_statement_union_type *s)
 706 {
 707   asection *sec;
 708   const reloc_deps_section *sec_deps;
 709
 710   if (s->header.type != lang_input_section_enum)
 711     return FALSE;
 712   sec = s->input_section.section;
 713
 714   sec_deps = xtensa_get_section_deps (deps, sec);
 715   return sec_deps && sec_deps->preds != NULL;
 716 }
 717
 718
 719 static bfd_boolean
 720 section_is_source_or_target (const reloc_deps_graph *deps ATTRIBUTE_UNUSED,
 721                              lang_statement_union_type *s)
 722 {
 723   return (section_is_source (deps, s)
 724           || section_is_target (deps, s));
 725 }
 726
 727
 728 typedef struct xtensa_ld_iter_stack_t xtensa_ld_iter_stack;
 729 typedef struct xtensa_ld_iter_t xtensa_ld_iter;
 730
 731 struct xtensa_ld_iter_t
 732 {
 733   lang_statement_union_type *parent;    /* Parent of the list.  */
 734   lang_statement_list_type *l;          /* List that holds it.  */
 735   lang_statement_union_type **loc;      /* Place in the list.  */
 736 };
 737
 738 struct xtensa_ld_iter_stack_t
 739 {
 740   xtensa_ld_iter iterloc;               /* List that hold it.  */
 741
 742   xtensa_ld_iter_stack *next;           /* Next in the stack.  */
 743   xtensa_ld_iter_stack *prev;           /* Back pointer for stack.  */
 744 };
 745
 746
 747 static void
 748 ld_xtensa_move_section_after (xtensa_ld_iter *to, xtensa_ld_iter *current)
 749 {
 750   lang_statement_union_type *to_next;
 751   lang_statement_union_type *current_next;
 752   lang_statement_union_type **e;
 753
 754 #if EXTRA_VALIDATION
 755   size_t old_to_count, new_to_count;
 756   size_t old_current_count, new_current_count;
 757 #endif
 758
 759   if (to == current)
 760     return;
 761
 762 #if EXTRA_VALIDATION
 763   old_to_count = ld_count_children (to->parent);
 764   old_current_count = ld_count_children (current->parent);
 765 #endif
 766
 767   to_next = *(to->loc);
 768   current_next = (*current->loc)->header.next;
 769
 770   *(to->loc) = *(current->loc);
 771
 772   *(current->loc) = current_next;
 773   (*(to->loc))->header.next = to_next;
 774
 775   /* reset "to" list tail */
 776   for (e = &to->l->head; *e != NULL; e = &(*e)->header.next)
 777     ;
 778   to->l->tail = e;
 779
 780   /* reset "current" list tail */
 781   for (e = &current->l->head; *e != NULL; e = &(*e)->header.next)
 782     ;
 783   current->l->tail = e;
 784
 785 #if EXTRA_VALIDATION
 786   new_to_count = ld_count_children (to->parent);
 787   new_current_count = ld_count_children (current->parent);
 788
 789   ASSERT ((old_to_count + old_current_count)
 790           == (new_to_count + new_current_count));
 791 #endif
 792 }
 793
 794
 795 /* Can only be called with lang_statements that have lists.  Returns
 796    FALSE if the list is empty.  */
 797
 798 static bfd_boolean
 799 iter_stack_empty (xtensa_ld_iter_stack **stack_p)
 800 {
 801   return *stack_p == NULL;
 802 }
 803
 804
 805 static bfd_boolean
 806 iter_stack_push (xtensa_ld_iter_stack **stack_p,
 807                  lang_statement_union_type *parent)
 808 {
 809   xtensa_ld_iter_stack *stack;
 810   lang_statement_list_type *l = NULL;
 811
 812   switch (parent->header.type)
 813     {
 814     case lang_output_section_statement_enum:
 815       l = &parent->output_section_statement.children;
 816       break;
 817     case lang_wild_statement_enum:
 818       l = &parent->wild_statement.children;
 819       break;
 820     case lang_group_statement_enum:
 821       l = &parent->group_statement.children;
 822       break;
 823     default:
 824       ASSERT (0);
 825       return FALSE;
 826     }
 827
 828   /* Empty. do not push.  */
 829   if (l->tail == &l->head)
 830     return FALSE;
 831
 832   stack = xmalloc (sizeof (xtensa_ld_iter_stack));
 833   memset (stack, 0, sizeof (xtensa_ld_iter_stack));
 834   stack->iterloc.parent = parent;
 835   stack->iterloc.l = l;
 836   stack->iterloc.loc = &l->head;
 837
 838   stack->next = *stack_p;
 839   stack->prev = NULL;
 840   if (*stack_p != NULL)
 841     (*stack_p)->prev = stack;
 842   *stack_p = stack;
 843   return TRUE;
 844 }
 845
 846
 847 static void
 848 iter_stack_pop (xtensa_ld_iter_stack **stack_p)
 849 {
 850   xtensa_ld_iter_stack *stack;
 851
 852   stack = *stack_p;
 853
 854   if (stack == NULL)
 855     {
 856       ASSERT (stack != NULL);
 857       return;
 858     }
 859
 860   if (stack->next != NULL)
 861     stack->next->prev = NULL;
 862
 863   *stack_p = stack->next;
 864   free (stack);
 865 }
 866
 867
 868 /* This MUST be called if, during iteration, the user changes the
 869    underlying structure.  It will check for a NULL current and advance
 870    accordingly.  */
 871
 872 static void
 873 iter_stack_update (xtensa_ld_iter_stack **stack_p)
 874 {
 875   if (!iter_stack_empty (stack_p)
 876       && (*(*stack_p)->iterloc.loc) == NULL)
 877     {
 878       iter_stack_pop (stack_p);
 879
 880       while (!iter_stack_empty (stack_p)
 881              && ((*(*stack_p)->iterloc.loc)->header.next == NULL))
 882         {
 883           iter_stack_pop (stack_p);
 884         }
 885       if (!iter_stack_empty (stack_p))
 886         (*stack_p)->iterloc.loc = &(*(*stack_p)->iterloc.loc)->header.next;
 887     }
 888 }
 889
 890
 891 static void
 892 iter_stack_next (xtensa_ld_iter_stack **stack_p)
 893 {
 894   xtensa_ld_iter_stack *stack;
 895   lang_statement_union_type *current;
 896   stack = *stack_p;
 897
 898   current = *stack->iterloc.loc;
 899   /* If we are on the first element.  */
 900   if (current != NULL)
 901     {
 902       switch (current->header.type)
 903         {
 904         case lang_output_section_statement_enum:
 905         case lang_wild_statement_enum:
 906         case lang_group_statement_enum:
 907           /* If the list if not empty, we are done.  */
 908           if (iter_stack_push (stack_p, *stack->iterloc.loc))
 909             return;
 910           /* Otherwise increment the pointer as normal.  */
 911           break;
 912         default:
 913           break;
 914         }
 915     }
 916
 917   while (!iter_stack_empty (stack_p)
 918          && ((*(*stack_p)->iterloc.loc)->header.next == NULL))
 919     {
 920       iter_stack_pop (stack_p);
 921     }
 922   if (!iter_stack_empty (stack_p))
 923     (*stack_p)->iterloc.loc = &(*(*stack_p)->iterloc.loc)->header.next;
 924 }
 925
 926
 927 static lang_statement_union_type *
 928 iter_stack_current (xtensa_ld_iter_stack **stack_p)
 929 {
 930   return *((*stack_p)->iterloc.loc);
 931 }
 932
 933
 934 /* The iter stack is a preorder.  */
 935
 936 static void
 937 iter_stack_create (xtensa_ld_iter_stack **stack_p,
 938                    lang_statement_union_type *parent)
 939 {
 940   iter_stack_push (stack_p, parent);
 941 }
 942
 943
 944 static void
 945 iter_stack_copy_current (xtensa_ld_iter_stack **stack_p, xtensa_ld_iter *front)
 946 {
 947   *front = (*stack_p)->iterloc;
 948 }
 949
 950
 951 static void
 952 xtensa_colocate_literals (reloc_deps_graph *deps,
 953                           lang_statement_union_type *statement)
 954 {
 955   /* Keep a stack of pointers to control iteration through the contours.  */
 956   xtensa_ld_iter_stack *stack = NULL;
 957   xtensa_ld_iter_stack **stack_p = &stack;
 958
 959   xtensa_ld_iter front;  /* Location where new insertion should occur.  */
 960   xtensa_ld_iter *front_p = NULL;
 961
 962   xtensa_ld_iter current; /* Location we are checking.  */
 963   xtensa_ld_iter *current_p = NULL;
 964   bfd_boolean in_literals = FALSE;
 965
 966   if (deps->count == 0)
 967     return;
 968
 969   iter_stack_create (stack_p, statement);
 970
 971   while (!iter_stack_empty (stack_p))
 972     {
 973       bfd_boolean skip_increment = FALSE;
 974       lang_statement_union_type *l = iter_stack_current (stack_p);
 975
 976       switch (l->header.type)
 977         {
 978         case lang_assignment_statement_enum:
 979           /* Any assignment statement should block reordering across it.  */
 980           front_p = NULL;
 981           in_literals = FALSE;
 982           break;
 983
 984         case lang_input_section_enum:
 985           if (front_p == NULL)
 986             {
 987               in_literals = (section_is_target (deps, l)
 988                              && !section_is_source (deps, l));
 989               if (in_literals)
 990                 {
 991                   front_p = &front;
 992                   iter_stack_copy_current (stack_p, front_p);
 993                 }
 994             }
 995           else
 996             {
 997               bfd_boolean is_target;
 998               current_p = &current;
 999               iter_stack_copy_current (stack_p, current_p);
1000               is_target = (section_is_target (deps, l)
1001                            && !section_is_source (deps, l));
1002
1003               if (in_literals)
1004                 {
1005                   iter_stack_copy_current (stack_p, front_p);
1006                   if (!is_target)
1007                     in_literals = FALSE;
1008                 }
1009               else
1010                 {
1011                   if (is_target)
1012                     {
1013                       /* Try to insert in place.  */
1014                       ld_xtensa_move_section_after (front_p, current_p);
1015                       ld_assign_relative_paged_dot (0x100000,
1016                                                     statement,
1017                                                     deps,
1018                                                     xtensa_use_literal_pages);
1019
1020                       /* We use this code because it's already written.  */
1021                       if (!ld_local_file_relocations_fit (statement, deps))
1022                         {
1023                           /* Move it back.  */
1024                           ld_xtensa_move_section_after (current_p, front_p);
1025                           /* Reset the literal placement.  */
1026                           iter_stack_copy_current (stack_p, front_p);
1027                         }
1028                       else
1029                         {
1030                           /* Move front pointer up by one.  */
1031                           front_p->loc = &(*front_p->loc)->header.next;
1032
1033                           /* Do not increment the current pointer.  */
1034                           skip_increment = TRUE;
1035                         }
1036                     }
1037                 }
1038             }
1039           break;
1040         default:
1041           break;
1042         }
1043
1044       if (!skip_increment)
1045         iter_stack_next (stack_p);
1046       else
1047         /* Be careful to update the stack_p if it now is a null.  */
1048         iter_stack_update (stack_p);
1049     }
1050
1051   lang_for_each_statement_worker (xtensa_ldlang_clear_addresses, statement);
1052 }
1053
1054
1055 static void
1056 xtensa_move_dependencies_to_front (reloc_deps_graph *deps,
1057                                    lang_wild_statement_type *w)
1058 {
1059   /* Keep a front pointer and a current pointer.  */
1060   lang_statement_union_type **front;
1061   lang_statement_union_type **current;
1062
1063   /* Walk to the end of the targets.  */
1064   for (front = &w->children.head;
1065        (*front != NULL) && section_is_source_or_target (deps, *front);
1066        front = &(*front)->header.next)
1067     ;
1068
1069   if (*front == NULL)
1070     return;
1071
1072   current = &(*front)->header.next;
1073   while (*current != NULL)
1074     {
1075       if (section_is_source_or_target (deps, *current))
1076         {
1077           /* Insert in place.  */
1078           xtensa_ld_iter front_iter;
1079           xtensa_ld_iter current_iter;
1080
1081           front_iter.parent = (lang_statement_union_type *) w;
1082           front_iter.l = &w->children;
1083           front_iter.loc = front;
1084
1085           current_iter.parent = (lang_statement_union_type *) w;
1086           current_iter.l = &w->children;
1087           current_iter.loc = current;
1088
1089           ld_xtensa_move_section_after (&front_iter, &current_iter);
1090           front = &(*front)->header.next;
1091         }
1092       else
1093         {
1094           current = &(*current)->header.next;
1095         }
1096     }
1097 }
1098
1099
1100 static bfd_boolean
1101 deps_has_sec_edge (const reloc_deps_graph *deps, asection *src, asection *tgt)
1102 {
1103   const reloc_deps_section *sec_deps;
1104   const reloc_deps_e *sec_deps_e;
1105
1106   sec_deps = xtensa_get_section_deps (deps, src);
1107   if (sec_deps == NULL)
1108     return FALSE;
1109
1110   for (sec_deps_e = sec_deps->succs;
1111        sec_deps_e != NULL;
1112        sec_deps_e = sec_deps_e->next)
1113     {
1114       ASSERT (sec_deps_e->src == src);
1115       if (sec_deps_e->tgt == tgt)
1116         return TRUE;
1117     }
1118   return FALSE;
1119 }
1120
1121
1122 static bfd_boolean
1123 deps_has_edge (const reloc_deps_graph *deps,
1124                lang_statement_union_type *src,
1125                lang_statement_union_type *tgt)
1126 {
1127   if (!section_is_source (deps, src))
1128     return FALSE;
1129   if (!section_is_target (deps, tgt))
1130     return FALSE;
1131
1132   if (src->header.type != lang_input_section_enum)
1133     return FALSE;
1134   if (tgt->header.type != lang_input_section_enum)
1135     return FALSE;
1136
1137   return deps_has_sec_edge (deps, src->input_section.section,
1138                             tgt->input_section.section);
1139 }
1140
1141
1142 static void
1143 add_deps_edge (reloc_deps_graph *deps, asection *src_sec, asection *tgt_sec)
1144 {
1145   reloc_deps_section *src_sec_deps;
1146   reloc_deps_section *tgt_sec_deps;
1147
1148   reloc_deps_e *src_edge;
1149   reloc_deps_e *tgt_edge;
1150
1151   if (deps_has_sec_edge (deps, src_sec, tgt_sec))
1152     return;
1153
1154   src_sec_deps = xtensa_get_section_deps (deps, src_sec);
1155   if (src_sec_deps == NULL)
1156     {
1157       /* Add a section.  */
1158       src_sec_deps = xmalloc (sizeof (reloc_deps_section));
1159       memset (src_sec_deps, 0, sizeof (reloc_deps_section));
1160       src_sec_deps->is_only_literal = 0;
1161       src_sec_deps->preds = NULL;
1162       src_sec_deps->succs = NULL;
1163       xtensa_set_section_deps (deps, src_sec, src_sec_deps);
1164       xtensa_append_section_deps (deps, src_sec);
1165     }
1166
1167   tgt_sec_deps = xtensa_get_section_deps (deps, tgt_sec);
1168   if (tgt_sec_deps == NULL)
1169     {
1170       /* Add a section.  */
1171       tgt_sec_deps = xmalloc (sizeof (reloc_deps_section));
1172       memset (tgt_sec_deps, 0, sizeof (reloc_deps_section));
1173       tgt_sec_deps->is_only_literal = 0;
1174       tgt_sec_deps->preds = NULL;
1175       tgt_sec_deps->succs = NULL;
1176       xtensa_set_section_deps (deps, tgt_sec, tgt_sec_deps);
1177       xtensa_append_section_deps (deps, tgt_sec);
1178     }
1179
1180   /* Add the edges.  */
1181   src_edge = xmalloc (sizeof (reloc_deps_e));
1182   memset (src_edge, 0, sizeof (reloc_deps_e));
1183   src_edge->src = src_sec;
1184   src_edge->tgt = tgt_sec;
1185   src_edge->next = src_sec_deps->succs;
1186   src_sec_deps->succs = src_edge;
1187
1188   tgt_edge = xmalloc (sizeof (reloc_deps_e));
1189   memset (tgt_edge, 0, sizeof (reloc_deps_e));
1190   tgt_edge->src = src_sec;
1191   tgt_edge->tgt = tgt_sec;
1192   tgt_edge->next = tgt_sec_deps->preds;
1193   tgt_sec_deps->preds = tgt_edge;
1194 }
1195
1196
1197 static void
1198 build_deps_graph_callback (asection *src_sec,
1199                            bfd_vma src_offset ATTRIBUTE_UNUSED,
1200                            asection *target_sec,
1201                            bfd_vma target_offset ATTRIBUTE_UNUSED,
1202                            void *closure)
1203 {
1204   reloc_deps_graph *deps = closure;
1205
1206   /* If the target is defined.  */
1207   if (target_sec != NULL)
1208     add_deps_edge (deps, src_sec, target_sec);
1209 }
1210
1211
1212 static reloc_deps_graph *
1213 ld_build_required_section_dependence (lang_statement_union_type *s)
1214 {
1215   reloc_deps_graph *deps;
1216   xtensa_ld_iter_stack *stack = NULL;
1217
1218   deps = xmalloc (sizeof (reloc_deps_graph));
1219   deps->sections = NULL;
1220   deps->count = 0;
1221   deps->size = 0;
1222
1223   for (iter_stack_create (&stack, s);
1224        !iter_stack_empty (&stack);
1225        iter_stack_next (&stack))
1226     {
1227       lang_statement_union_type *l = iter_stack_current (&stack);
1228
1229       if (l->header.type == lang_input_section_enum)
1230         {
1231           lang_input_section_type *input;
1232           input = &l->input_section;
1233           xtensa_callback_required_dependence (input->section->owner,
1234                                                input->section,
1235                                                &link_info,
1236                                                /* Use the same closure.  */
1237                                                build_deps_graph_callback,
1238                                                deps);
1239         }
1240     }
1241   return deps;
1242 }
1243
1244
1245 #if EXTRA_VALIDATION
1246 static size_t
1247 ld_count_children (lang_statement_union_type *s)
1248 {
1249   size_t count = 0;
1250   xtensa_ld_iter_stack *stack = NULL;
1251   for (iter_stack_create (&stack, s);
1252        !iter_stack_empty (&stack);
1253        iter_stack_next (&stack))
1254     {
1255       lang_statement_union_type *l = iter_stack_current (&stack);
1256       ASSERT (l != NULL);
1257       count++;
1258     }
1259   return count;
1260 }
1261 #endif /* EXTRA_VALIDATION */
1262
1263
1264 /* Check if a particular section is included in the link.  This will only
1265    be true for one instance of a particular linkonce section.  */
1266
1267 static bfd_boolean input_section_found = FALSE;
1268 static asection *input_section_target = NULL;
1269
1270 static void
1271 input_section_linked_worker (lang_statement_union_type *statement)
1272 {
1273   if ((statement->header.type == lang_input_section_enum
1274        && (statement->input_section.section == input_section_target)))
1275     input_section_found = TRUE;
1276 }
1277
1278 static bfd_boolean
1279 input_section_linked (asection *sec)
1280 {
1281   input_section_found = FALSE;
1282   input_section_target = sec;
1283   lang_for_each_statement_worker (input_section_linked_worker, stat_ptr->head);
1284   return input_section_found;
1285 }
1286
1287
1288 /* Strip out any linkonce property tables or XCC exception tables where the
1289    associated linkonce text is from a different object file.  Normally,
1290    a matching set of linkonce sections is taken from the same object file,
1291    but sometimes the files are compiled differently so that some of the
1292    linkonce sections are not present in all files.  Stripping the
1293    inconsistent sections like this is not completely robust -- a much
1294    better solution is to use comdat groups.  */
1295
1296 static int linkonce_len = sizeof (".gnu.linkonce.") - 1;
1297
1298 static bfd_boolean
1299 is_inconsistent_linkonce_section (asection *sec)
1300 {
1301   bfd *abfd = sec->owner;
1302   const char *sec_name = bfd_get_section_name (abfd, sec);
1303   const char *name;
1304
1305   if ((bfd_get_section_flags (abfd, sec) & SEC_LINK_ONCE) == 0
1306       || strncmp (sec_name, ".gnu.linkonce.", linkonce_len) != 0)
1307     return FALSE;
1308
1309   /* Check if this is an Xtensa property section or an exception table
1310      for Tensilica's XCC compiler.  */
1311   name = sec_name + linkonce_len;
1312   if (CONST_STRNEQ (name, "prop."))
1313     name = strchr (name + 5, '.') ? strchr (name + 5, '.') + 1 : name + 5;
1314   else if (name[1] == '.'
1315            && (name[0] == 'p' || name[0] == 'e' || name[0] == 'h'))
1316     name += 2;
1317   else
1318     name = 0;
1319
1320   if (name)
1321     {
1322       char *dep_sec_name = xmalloc (strlen (sec_name) + 1);
1323       asection *dep_sec;
1324
1325       /* Get the associated linkonce text section and check if it is
1326          included in the link.  If not, this section is inconsistent
1327          and should be stripped.  */
1328       strcpy (dep_sec_name, ".gnu.linkonce.t.");
1329       strcat (dep_sec_name, name);
1330       dep_sec = bfd_get_section_by_name (abfd, dep_sec_name);
1331       if (dep_sec == NULL || ! input_section_linked (dep_sec))
1332         {
1333           free (dep_sec_name);
1334           return TRUE;
1335         }
1336       free (dep_sec_name);
1337     }
1338
1339   return FALSE;
1340 }
1341
1342
1343 static void
1344 xtensa_strip_inconsistent_linkonce_sections (lang_statement_list_type *slist)
1345 {
1346   lang_statement_union_type **s_p = &slist->head;
1347   while (*s_p)
1348     {
1349       lang_statement_union_type *s = *s_p;
1350       lang_statement_union_type *s_next = (*s_p)->header.next;
1351
1352       switch (s->header.type)
1353         {
1354         case lang_input_section_enum:
1355           if (is_inconsistent_linkonce_section (s->input_section.section))
1356             {
1357               s->input_section.section->output_section = bfd_abs_section_ptr;
1358               *s_p = s_next;
1359               continue;
1360             }
1361           break;
1362
1363         case lang_constructors_statement_enum:
1364           xtensa_strip_inconsistent_linkonce_sections (&constructor_list);
1365           break;
1366
1367         case lang_output_section_statement_enum:
1368           if (s->output_section_statement.children.head)
1369             xtensa_strip_inconsistent_linkonce_sections
1370               (&s->output_section_statement.children);
1371           break;
1372
1373         case lang_wild_statement_enum:
1374           xtensa_strip_inconsistent_linkonce_sections
1375             (&s->wild_statement.children);
1376           break;
1377
1378         case lang_group_statement_enum:
1379           xtensa_strip_inconsistent_linkonce_sections
1380             (&s->group_statement.children);
1381           break;
1382
1383         case lang_data_statement_enum:
1384         case lang_reloc_statement_enum:
1385         case lang_object_symbols_statement_enum:
1386         case lang_output_statement_enum:
1387         case lang_target_statement_enum:
1388         case lang_input_statement_enum:
1389         case lang_assignment_statement_enum:
1390         case lang_padding_statement_enum:
1391         case lang_address_statement_enum:
1392         case lang_fill_statement_enum:
1393           break;
1394
1395         default:
1396           FAIL ();
1397           break;
1398         }
1399
1400       s_p = &(*s_p)->header.next;
1401     }
1402
1403   /* Reset the tail of the list, in case the last entry was removed.  */
1404   if (s_p != slist->tail)
1405     slist->tail = s_p;
1406 }
1407
1408
1409 static void
1410 xtensa_wild_group_interleave_callback (lang_statement_union_type *statement)
1411 {
1412   lang_wild_statement_type *w;
1413   reloc_deps_graph *deps;
1414   if (statement->header.type == lang_wild_statement_enum)
1415     {
1416 #if EXTRA_VALIDATION
1417       size_t old_child_count;
1418       size_t new_child_count;
1419 #endif
1420       bfd_boolean no_reorder;
1421
1422       w = &statement->wild_statement;
1423
1424       no_reorder = FALSE;
1425
1426       /* If it has 0 or 1 section bound, then do not reorder.  */
1427       if (w->children.head == NULL
1428           || (w->children.head->header.type == lang_input_section_enum
1429               && w->children.head->header.next == NULL))
1430         no_reorder = TRUE;
1431
1432       if (w->filenames_sorted)
1433         no_reorder = TRUE;
1434
1435       /* Check for sorting in a section list wildcard spec as well.  */
1436       if (!no_reorder)
1437         {
1438           struct wildcard_list *l;
1439           for (l = w->section_list; l != NULL; l = l->next)
1440             {
1441               if (l->spec.sorted == TRUE)
1442                 {
1443                   no_reorder = TRUE;
1444                   break;
1445                 }
1446             }
1447         }
1448
1449       /* Special case until the NOREORDER linker directive is supported:
1450          *(.init) output sections and *(.fini) specs may NOT be reordered.  */
1451
1452       /* Check for sorting in a section list wildcard spec as well.  */
1453       if (!no_reorder)
1454         {
1455           struct wildcard_list *l;
1456           for (l = w->section_list; l != NULL; l = l->next)
1457             {
1458               if (l->spec.name
1459                   && ((strcmp (".init", l->spec.name) == 0)
1460                       || (strcmp (".fini", l->spec.name) == 0)))
1461                 {
1462                   no_reorder = TRUE;
1463                   break;
1464                 }
1465             }
1466         }
1467
1468 #if EXTRA_VALIDATION
1469       old_child_count = ld_count_children (statement);
1470 #endif
1471
1472       /* It is now officially a target.  Build the graph of source
1473          section -> target section (kept as a list of edges).  */
1474       deps = ld_build_required_section_dependence (statement);
1475
1476       /* If this wildcard does not reorder....  */
1477       if (!no_reorder && deps->count != 0)
1478         {
1479           /* First check for reverse dependences.  Fix if possible.  */
1480           xtensa_layout_wild (deps, w);
1481
1482           xtensa_move_dependencies_to_front (deps, w);
1483 #if EXTRA_VALIDATION
1484           new_child_count = ld_count_children (statement);
1485           ASSERT (new_child_count == old_child_count);
1486 #endif
1487
1488           xtensa_colocate_literals (deps, statement);
1489
1490 #if EXTRA_VALIDATION
1491           new_child_count = ld_count_children (statement);
1492           ASSERT (new_child_count == old_child_count);
1493 #endif
1494         }
1495
1496       /* Clean up.  */
1497       free_reloc_deps_graph (deps);
1498     }
1499 }
1500
1501
1502 static void
1503 xtensa_wild_group_interleave (lang_statement_union_type *s)
1504 {
1505   lang_for_each_statement_worker (xtensa_wild_group_interleave_callback, s);
1506 }
1507
1508
1509 static void
1510 xtensa_layout_wild (const reloc_deps_graph *deps, lang_wild_statement_type *w)
1511 {
1512   /* If it does not fit initially, we need to do this step.  Move all
1513      of the wild literal sections to a new list, then move each of
1514      them back in just before the first section they depend on.  */
1515   lang_statement_union_type **s_p;
1516 #if EXTRA_VALIDATION
1517   size_t old_count, new_count;
1518   size_t ct1, ct2;
1519 #endif
1520
1521   lang_wild_statement_type literal_wild;
1522   literal_wild.header.next = NULL;
1523   literal_wild.header.type = lang_wild_statement_enum;
1524   literal_wild.filename = NULL;
1525   literal_wild.filenames_sorted = FALSE;
1526   literal_wild.section_list = NULL;
1527   literal_wild.keep_sections = FALSE;
1528   literal_wild.children.head = NULL;
1529   literal_wild.children.tail = &literal_wild.children.head;
1530
1531 #if EXTRA_VALIDATION
1532   old_count = ld_count_children ((lang_statement_union_type*) w);
1533 #endif
1534
1535   s_p = &w->children.head;
1536   while (*s_p != NULL)
1537     {
1538       lang_statement_union_type *l = *s_p;
1539       if (l->header.type == lang_input_section_enum)
1540         {
1541           if (section_is_target (deps, l)
1542               && ! section_is_source (deps, l))
1543             {
1544               /* Detach.  */
1545               *s_p = l->header.next;
1546               if (*s_p == NULL)
1547                 w->children.tail = s_p;
1548               l->header.next = NULL;
1549
1550               /* Append.  */
1551               *literal_wild.children.tail = l;
1552               literal_wild.children.tail = &l->header.next;
1553               continue;
1554             }
1555         }
1556       s_p = &(*s_p)->header.next;
1557     }
1558
1559 #if EXTRA_VALIDATION
1560   ct1 = ld_count_children ((lang_statement_union_type*) w);
1561   ct2 = ld_count_children ((lang_statement_union_type*) &literal_wild);
1562
1563   ASSERT (old_count == (ct1 + ct2));
1564 #endif
1565
1566   /* Now place them back in front of their dependent sections.  */
1567
1568   while (literal_wild.children.head != NULL)
1569     {
1570       lang_statement_union_type *lit = literal_wild.children.head;
1571       bfd_boolean placed = FALSE;
1572
1573 #if EXTRA_VALIDATION
1574       ASSERT (ct2 > 0);
1575       ct2--;
1576 #endif
1577
1578       /* Detach.  */
1579       literal_wild.children.head = lit->header.next;
1580       if (literal_wild.children.head == NULL)
1581         literal_wild.children.tail = &literal_wild.children.head;
1582       lit->header.next = NULL;
1583
1584       /* Find a spot to place it.  */
1585       for (s_p = &w->children.head; *s_p != NULL; s_p = &(*s_p)->header.next)
1586         {
1587           lang_statement_union_type *src = *s_p;
1588           if (deps_has_edge (deps, src, lit))
1589             {
1590               /* Place it here.  */
1591               lit->header.next = *s_p;
1592               *s_p = lit;
1593               placed = TRUE;
1594               break;
1595             }
1596         }
1597
1598       if (!placed)
1599         {
1600           /* Put it at the end.  */
1601           *w->children.tail = lit;
1602           w->children.tail = &lit->header.next;
1603         }
1604     }
1605
1606 #if EXTRA_VALIDATION
1607   new_count = ld_count_children ((lang_statement_union_type*) w);
1608   ASSERT (new_count == old_count);
1609 #endif
1610 }
1611
1612
1613 static void
1614 xtensa_colocate_output_literals_callback (lang_statement_union_type *statement)
1615 {
1616   reloc_deps_graph *deps;
1617   if (statement->header.type == lang_output_section_statement_enum)
1618     {
1619       /* Now, we walk over the contours of the output section statement.
1620
1621          First we build the literal section dependences as before.
1622
1623          At the first uniquely_literal section, we mark it as a good
1624          spot to place other literals.  Continue walking (and counting
1625          sizes) until we find the next literal section.  If this
1626          section can be moved to the first one, then we move it.  If
1627          we every find a modification of ".", start over.  If we find
1628          a labeling of the current location, start over.  Finally, at
1629          the end, if we require page alignment, add page alignments.  */
1630
1631 #if EXTRA_VALIDATION
1632       size_t old_child_count;
1633       size_t new_child_count;
1634 #endif
1635       bfd_boolean no_reorder = FALSE;
1636
1637 #if EXTRA_VALIDATION
1638       old_child_count = ld_count_children (statement);
1639 #endif
1640
1641       /* It is now officially a target.  Build the graph of source
1642          section -> target section (kept as a list of edges).  */
1643
1644       deps = ld_build_required_section_dependence (statement);
1645
1646       /* If this wildcard does not reorder....  */
1647       if (!no_reorder)
1648         {
1649           /* First check for reverse dependences.  Fix if possible.  */
1650           xtensa_colocate_literals (deps, statement);
1651
1652 #if EXTRA_VALIDATION
1653           new_child_count = ld_count_children (statement);
1654           ASSERT (new_child_count == old_child_count);
1655 #endif
1656         }
1657
1658       /* Insert align/offset assignment statement.  */
1659       if (xtensa_use_literal_pages)
1660         {
1661           ld_xtensa_insert_page_offsets (0, statement, deps,
1662                                          xtensa_use_literal_pages);
1663           lang_for_each_statement_worker (xtensa_ldlang_clear_addresses,
1664                                           statement);
1665         }
1666
1667       /* Clean up.  */
1668       free_reloc_deps_graph (deps);
1669     }
1670 }
1671
1672
1673 static void
1674 xtensa_colocate_output_literals (lang_statement_union_type *s)
1675 {
1676   lang_for_each_statement_worker (xtensa_colocate_output_literals_callback, s);
1677 }
1678
1679
1680 static void
1681 xtensa_ldlang_clear_addresses (lang_statement_union_type *statement)
1682 {
1683   switch (statement->header.type)
1684     {
1685     case lang_input_section_enum:
1686       {
1687         asection *bfd_section = statement->input_section.section;
1688         bfd_section->output_offset = 0;
1689       }
1690       break;
1691     default:
1692       break;
1693     }
1694 }
1695
1696
1697 static bfd_vma
1698 ld_assign_relative_paged_dot (bfd_vma dot,
1699                               lang_statement_union_type *s,
1700                               const reloc_deps_graph *deps ATTRIBUTE_UNUSED,
1701                               bfd_boolean lit_align)
1702 {
1703   /* Walk through all of the input statements in this wild statement
1704      assign dot to all of them.  */
1705
1706   xtensa_ld_iter_stack *stack = NULL;
1707   xtensa_ld_iter_stack **stack_p = &stack;
1708
1709   bfd_boolean first_section = FALSE;
1710   bfd_boolean in_literals = FALSE;
1711
1712   for (iter_stack_create (stack_p, s);
1713        !iter_stack_empty (stack_p);
1714        iter_stack_next (stack_p))
1715     {
1716       lang_statement_union_type *l = iter_stack_current (stack_p);
1717
1718       switch (l->header.type)
1719         {
1720         case lang_input_section_enum:
1721           {
1722             asection *section = l->input_section.section;
1723             size_t align_pow = section->alignment_power;
1724             bfd_boolean do_xtensa_alignment = FALSE;
1725
1726             if (lit_align)
1727               {
1728                 bfd_boolean sec_is_target = section_is_target (deps, l);
1729                 bfd_boolean sec_is_source = section_is_source (deps, l);
1730
1731                 if (section->size != 0
1732                     && (first_section
1733                         || (in_literals && !sec_is_target)
1734                         || (!in_literals && sec_is_target)))
1735                   {
1736                     do_xtensa_alignment = TRUE;
1737                   }
1738                 first_section = FALSE;
1739                 if (section->size != 0)
1740                   in_literals = (sec_is_target && !sec_is_source);
1741               }
1742
1743             if (do_xtensa_alignment && xtensa_page_power != 0)
1744               dot += (1 << xtensa_page_power);
1745
1746             dot = align_power (dot, align_pow);
1747             section->output_offset = dot;
1748             dot += section->size;
1749           }
1750           break;
1751         case lang_fill_statement_enum:
1752           dot += l->fill_statement.size;
1753           break;
1754         case lang_padding_statement_enum:
1755           dot += l->padding_statement.size;
1756           break;
1757         default:
1758           break;
1759         }
1760     }
1761   return dot;
1762 }
1763
1764
1765 static bfd_boolean
1766 ld_local_file_relocations_fit (lang_statement_union_type *statement,
1767                                const reloc_deps_graph *deps ATTRIBUTE_UNUSED)
1768 {
1769   /* Walk over all of the dependencies that we identified and make
1770      sure that IF the source and target are here (addr != 0):
1771      1) target addr < source addr
1772      2) (roundup(source + source_size, 4) - rounddown(target, 4))
1773         < (256K - (1 << bad align))
1774      Need a worst-case proof....  */
1775
1776   xtensa_ld_iter_stack *stack = NULL;
1777   xtensa_ld_iter_stack **stack_p = &stack;
1778   size_t max_align_power = 0;
1779   size_t align_penalty = 256;
1780   reloc_deps_e *e;
1781   size_t i;
1782
1783   /* Find the worst-case alignment requirement for this set of statements.  */
1784   for (iter_stack_create (stack_p, statement);
1785        !iter_stack_empty (stack_p);
1786        iter_stack_next (stack_p))
1787     {
1788       lang_statement_union_type *l = iter_stack_current (stack_p);
1789       if (l->header.type == lang_input_section_enum)
1790         {
1791           lang_input_section_type *input = &l->input_section;
1792           asection *section = input->section;
1793           if (section->alignment_power > max_align_power)
1794             max_align_power = section->alignment_power;
1795         }
1796     }
1797
1798   /* Now check that everything fits.  */
1799   for (i = 0; i < deps->count; i++)
1800     {
1801       asection *sec = deps->sections[i];
1802       const reloc_deps_section *deps_section =
1803         xtensa_get_section_deps (deps, sec);
1804       if (deps_section)
1805         {
1806           /* We choose to walk through the successors.  */
1807           for (e = deps_section->succs; e != NULL; e = e->next)
1808             {
1809               if (e->src != e->tgt
1810                   && e->src->output_section == e->tgt->output_section
1811                   && e->src->output_offset != 0
1812                   && e->tgt->output_offset != 0)
1813                 {
1814                   bfd_vma l32r_addr =
1815                     align_power (e->src->output_offset + e->src->size, 2);
1816                   bfd_vma target_addr = e->tgt->output_offset & ~3;
1817                   if (l32r_addr < target_addr)
1818                     {
1819                       fflush (stdout);
1820                       fprintf (stderr, "Warning: "
1821                                "l32r target section before l32r\n");
1822                       fflush (stderr);
1823                       return FALSE;
1824                     }
1825
1826                   if (l32r_addr - target_addr > 256 * 1024 - align_penalty)
1827                     return FALSE;
1828                 }
1829             }
1830         }
1831     }
1832
1833   return TRUE;
1834 }
1835
1836
1837 static bfd_vma
1838 ld_xtensa_insert_page_offsets (bfd_vma dot,
1839                                lang_statement_union_type *s,
1840                                reloc_deps_graph *deps,
1841                                bfd_boolean lit_align)
1842 {
1843   xtensa_ld_iter_stack *stack = NULL;
1844   xtensa_ld_iter_stack **stack_p = &stack;
1845
1846   bfd_boolean first_section = FALSE;
1847   bfd_boolean in_literals = FALSE;
1848
1849   if (!lit_align)
1850     return FALSE;
1851
1852   for (iter_stack_create (stack_p, s);
1853        !iter_stack_empty (stack_p);
1854        iter_stack_next (stack_p))
1855     {
1856       lang_statement_union_type *l = iter_stack_current (stack_p);
1857
1858       switch (l->header.type)
1859         {
1860         case lang_input_section_enum:
1861           {
1862             asection *section = l->input_section.section;
1863             bfd_boolean do_xtensa_alignment = FALSE;
1864
1865             if (lit_align)
1866               {
1867                 if (section->size != 0
1868                     && (first_section
1869                         || (in_literals && !section_is_target (deps, l))
1870                         || (!in_literals && section_is_target (deps, l))))
1871                   {
1872                     do_xtensa_alignment = TRUE;
1873                   }
1874                 first_section = FALSE;
1875                 if (section->size != 0)
1876                   {
1877                     in_literals = (section_is_target (deps, l)
1878                                    && !section_is_source (deps, l));
1879                   }
1880               }
1881
1882             if (do_xtensa_alignment && xtensa_page_power != 0)
1883               {
1884                 /* Create an expression that increments the current address,
1885                    i.e., "dot", by (1 << xtensa_align_power).  */
1886                 etree_type *name_op = exp_nameop (NAME, ".");
1887                 etree_type *addend_op = exp_intop (1 << xtensa_page_power);
1888                 etree_type *add_op = exp_binop ('+', name_op, addend_op);
1889                 etree_type *assign_op = exp_assign (".", add_op, FALSE);
1890
1891                 lang_assignment_statement_type *assign_stmt;
1892                 lang_statement_union_type *assign_union;
1893                 lang_statement_list_type tmplist;
1894
1895                 /* There is hidden state in "lang_add_assignment".  It
1896                    appends the new assignment statement to the stat_ptr
1897                    list.  Thus, we swap it before and after the call.  */
1898
1899                 lang_list_init (&tmplist);
1900                 push_stat_ptr (&tmplist);
1901                 /* Warning: side effect; statement appended to stat_ptr.  */
1902                 assign_stmt = lang_add_assignment (assign_op);
1903                 assign_union = (lang_statement_union_type *) assign_stmt;
1904                 pop_stat_ptr ();
1905
1906                 assign_union->header.next = l;
1907                 *(*stack_p)->iterloc.loc = assign_union;
1908                 iter_stack_next (stack_p);
1909               }
1910           }
1911           break;
1912         default:
1913           break;
1914         }
1915     }
1916   return dot;
1917 }
1918
1919 EOF
1920
1921 # Define some shell vars to insert bits of code into the standard ELF
1922 # parse_args and list_options functions.
1923 #
1924 PARSE_AND_LIST_PROLOGUE='
1925 #define OPTION_OPT_SIZEOPT              (300)
1926 #define OPTION_LITERAL_MOVEMENT         (OPTION_OPT_SIZEOPT + 1)
1927 #define OPTION_NO_LITERAL_MOVEMENT      (OPTION_LITERAL_MOVEMENT + 1)
1928 extern int elf32xtensa_size_opt;
1929 extern int elf32xtensa_no_literal_movement;
1930 '
1931
1932 PARSE_AND_LIST_LONGOPTS='
1933   { "size-opt", no_argument, NULL, OPTION_OPT_SIZEOPT},
1934   { "literal-movement", no_argument, NULL, OPTION_LITERAL_MOVEMENT},
1935   { "no-literal-movement", no_argument, NULL, OPTION_NO_LITERAL_MOVEMENT},
1936 '
1937
1938 PARSE_AND_LIST_OPTIONS='
1939   fprintf (file, _("\
1940   --size-opt                  When relaxing longcalls, prefer size\n\
1941                                 optimization over branch target alignment\n"));
1942 '
1943
1944 PARSE_AND_LIST_ARGS_CASES='
1945     case OPTION_OPT_SIZEOPT:
1946       elf32xtensa_size_opt = 1;
1947       break;
1948     case OPTION_LITERAL_MOVEMENT:
1949       elf32xtensa_no_literal_movement = 0;
1950       break;
1951     case OPTION_NO_LITERAL_MOVEMENT:
1952       elf32xtensa_no_literal_movement = 1;
1953       break;
1954 '
1955
1956 # Replace some of the standard ELF functions with our own versions.
1957 #
1958 LDEMUL_BEFORE_PARSE=elf_xtensa_before_parse
1959 LDEMUL_AFTER_OPEN=elf_xtensa_after_open
1960 LDEMUL_CHOOSE_TARGET=elf_xtensa_choose_target
1961 LDEMUL_BEFORE_ALLOCATION=elf_xtensa_before_allocation