ld/emultempl/xtensaelf.em

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