ld/ldexp.c

   1 /* This module handles expression trees.
   2    Copyright 1991-2013 Free Software Foundation, Inc.
   3    Written by Steve Chamberlain of Cygnus Support <sac@cygnus.com>.
   4
   5    This file is part of the GNU Binutils.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
  20    MA 02110-1301, USA.  */
  21
  22
  23 /* This module is in charge of working out the contents of expressions.
  24
  25    It has to keep track of the relative/absness of a symbol etc. This
  26    is done by keeping all values in a struct (an etree_value_type)
  27    which contains a value, a section to which it is relative and a
  28    valid bit.  */
  29
  30 #include "sysdep.h"
  31 #include "bfd.h"
  32 #include "bfdlink.h"
  33
  34 #include "ld.h"
  35 #include "ldmain.h"
  36 #include "ldmisc.h"
  37 #include "ldexp.h"
  38 #include "ldlex.h"
  39 #include <ldgram.h>
  40 #include "ldlang.h"
  41 #include "libiberty.h"
  42 #include "safe-ctype.h"
  43
  44 static void exp_fold_tree_1 (etree_type *);
  45 static bfd_vma align_n (bfd_vma, bfd_vma);
  46
  47 segment_type *segments;
  48
  49 struct ldexp_control expld;
  50
  51 /* Print the string representation of the given token.  Surround it
  52    with spaces if INFIX_P is TRUE.  */
  53
  54 static void
  55 exp_print_token (token_code_type code, int infix_p)
  56 {
  57   static const struct
  58   {
  59     token_code_type code;
  60     const char * name;
  61   }
  62   table[] =
  63   {
  64     { INT, "int" },
  65     { NAME, "NAME" },
  66     { PLUSEQ, "+=" },
  67     { MINUSEQ, "-=" },
  68     { MULTEQ, "*=" },
  69     { DIVEQ, "/=" },
  70     { LSHIFTEQ, "<<=" },
  71     { RSHIFTEQ, ">>=" },
  72     { ANDEQ, "&=" },
  73     { OREQ, "|=" },
  74     { OROR, "||" },
  75     { ANDAND, "&&" },
  76     { EQ, "==" },
  77     { NE, "!=" },
  78     { LE, "<=" },
  79     { GE, ">=" },
  80     { LSHIFT, "<<" },
  81     { RSHIFT, ">>" },
  82     { LOG2CEIL, "LOG2CEIL" },
  83     { ALIGN_K, "ALIGN" },
  84     { BLOCK, "BLOCK" },
  85     { QUAD, "QUAD" },
  86     { SQUAD, "SQUAD" },
  87     { LONG, "LONG" },
  88     { SHORT, "SHORT" },
  89     { BYTE, "BYTE" },
  90     { SECTIONS, "SECTIONS" },
  91     { SIZEOF_HEADERS, "SIZEOF_HEADERS" },
  92     { MEMORY, "MEMORY" },
  93     { DEFINED, "DEFINED" },
  94     { TARGET_K, "TARGET" },
  95     { SEARCH_DIR, "SEARCH_DIR" },
  96     { MAP, "MAP" },
  97     { ENTRY, "ENTRY" },
  98     { NEXT, "NEXT" },
  99     { ALIGNOF, "ALIGNOF" },
 100     { SIZEOF, "SIZEOF" },
 101     { ADDR, "ADDR" },
 102     { LOADADDR, "LOADADDR" },
 103     { CONSTANT, "CONSTANT" },
 104     { ABSOLUTE, "ABSOLUTE" },
 105     { MAX_K, "MAX" },
 106     { MIN_K, "MIN" },
 107     { ASSERT_K, "ASSERT" },
 108     { REL, "relocatable" },
 109     { DATA_SEGMENT_ALIGN, "DATA_SEGMENT_ALIGN" },
 110     { DATA_SEGMENT_RELRO_END, "DATA_SEGMENT_RELRO_END" },
 111     { DATA_SEGMENT_END, "DATA_SEGMENT_END" },
 112     { ORIGIN, "ORIGIN" },
 113     { LENGTH, "LENGTH" },
 114     { SEGMENT_START, "SEGMENT_START" }
 115   };
 116   unsigned int idx;
 117
 118   for (idx = 0; idx < ARRAY_SIZE (table); idx++)
 119     if (table[idx].code == code)
 120       break;
 121
 122   if (infix_p)
 123     fputc (' ', config.map_file);
 124
 125   if (idx < ARRAY_SIZE (table))
 126     fputs (table[idx].name, config.map_file);
 127   else if (code < 127)
 128     fputc (code, config.map_file);
 129   else
 130     fprintf (config.map_file, "<code %d>", code);
 131
 132   if (infix_p)
 133     fputc (' ', config.map_file);
 134 }
 135
 136 static void
 137 make_log2ceil (void)
 138 {
 139   bfd_vma value = expld.result.value;
 140   bfd_vma result = -1;
 141   bfd_boolean round_up = FALSE;
 142
 143   do
 144     {
 145       result++;
 146       /* If more than one bit is set in the value we will need to round up.  */
 147       if ((value > 1) && (value & 1))
 148         round_up = TRUE;
 149     }
 150   while (value >>= 1);
 151
 152   if (round_up)
 153     result += 1;
 154   expld.result.section = NULL;
 155   expld.result.value = result;
 156 }
 157
 158 static void
 159 make_abs (void)
 160 {
 161   if (expld.result.section != NULL)
 162     expld.result.value += expld.result.section->vma;
 163   expld.result.section = bfd_abs_section_ptr;
 164 }
 165
 166 static void
 167 new_abs (bfd_vma value)
 168 {
 169   expld.result.valid_p = TRUE;
 170   expld.result.section = bfd_abs_section_ptr;
 171   expld.result.value = value;
 172   expld.result.str = NULL;
 173 }
 174
 175 etree_type *
 176 exp_intop (bfd_vma value)
 177 {
 178   etree_type *new_e = (etree_type *) stat_alloc (sizeof (new_e->value));
 179   new_e->type.node_code = INT;
 180   new_e->type.filename = ldlex_filename ();
 181   new_e->type.lineno = lineno;
 182   new_e->value.value = value;
 183   new_e->value.str = NULL;
 184   new_e->type.node_class = etree_value;
 185   return new_e;
 186 }
 187
 188 etree_type *
 189 exp_bigintop (bfd_vma value, char *str)
 190 {
 191   etree_type *new_e = (etree_type *) stat_alloc (sizeof (new_e->value));
 192   new_e->type.node_code = INT;
 193   new_e->type.filename = ldlex_filename ();
 194   new_e->type.lineno = lineno;
 195   new_e->value.value = value;
 196   new_e->value.str = str;
 197   new_e->type.node_class = etree_value;
 198   return new_e;
 199 }
 200
 201 /* Build an expression representing an unnamed relocatable value.  */
 202
 203 etree_type *
 204 exp_relop (asection *section, bfd_vma value)
 205 {
 206   etree_type *new_e = (etree_type *) stat_alloc (sizeof (new_e->rel));
 207   new_e->type.node_code = REL;
 208   new_e->type.filename = ldlex_filename ();
 209   new_e->type.lineno = lineno;
 210   new_e->type.node_class = etree_rel;
 211   new_e->rel.section = section;
 212   new_e->rel.value = value;
 213   return new_e;
 214 }
 215
 216 static void
 217 new_number (bfd_vma value)
 218 {
 219   expld.result.valid_p = TRUE;
 220   expld.result.value = value;
 221   expld.result.str = NULL;
 222   expld.result.section = NULL;
 223 }
 224
 225 static void
 226 new_rel (bfd_vma value, asection *section)
 227 {
 228   expld.result.valid_p = TRUE;
 229   expld.result.value = value;
 230   expld.result.str = NULL;
 231   expld.result.section = section;
 232 }
 233
 234 static void
 235 new_rel_from_abs (bfd_vma value)
 236 {
 237   asection *s = expld.section;
 238
 239   if (s == bfd_abs_section_ptr && expld.phase == lang_final_phase_enum)
 240     s = section_for_dot ();
 241   expld.result.valid_p = TRUE;
 242   expld.result.value = value - s->vma;
 243   expld.result.str = NULL;
 244   expld.result.section = s;
 245 }
 246
 247 static void
 248 fold_unary (etree_type *tree)
 249 {
 250   exp_fold_tree_1 (tree->unary.child);
 251   if (expld.result.valid_p)
 252     {
 253       switch (tree->type.node_code)
 254         {
 255         case ALIGN_K:
 256           if (expld.phase != lang_first_phase_enum)
 257             new_rel_from_abs (align_n (expld.dot, expld.result.value));
 258           else
 259             expld.result.valid_p = FALSE;
 260           break;
 261
 262         case ABSOLUTE:
 263           make_abs ();
 264           break;
 265
 266         case LOG2CEIL:
 267           make_log2ceil ();
 268           break;
 269
 270         case '~':
 271           expld.result.value = ~expld.result.value;
 272           break;
 273
 274         case '!':
 275           expld.result.value = !expld.result.value;
 276           break;
 277
 278         case '-':
 279           expld.result.value = -expld.result.value;
 280           break;
 281
 282         case NEXT:
 283           /* Return next place aligned to value.  */
 284           if (expld.phase != lang_first_phase_enum)
 285             {
 286               make_abs ();
 287               expld.result.value = align_n (expld.dot, expld.result.value);
 288             }
 289           else
 290             expld.result.valid_p = FALSE;
 291           break;
 292
 293         case DATA_SEGMENT_END:
 294           if (expld.phase == lang_first_phase_enum
 295               || expld.section != bfd_abs_section_ptr)
 296             {
 297               expld.result.valid_p = FALSE;
 298             }
 299           else if (expld.dataseg.phase == exp_dataseg_align_seen
 300                    || expld.dataseg.phase == exp_dataseg_relro_seen)
 301             {
 302               expld.dataseg.phase = exp_dataseg_end_seen;
 303               expld.dataseg.end = expld.result.value;
 304             }
 305           else if (expld.dataseg.phase == exp_dataseg_done
 306                    || expld.dataseg.phase == exp_dataseg_adjust
 307                    || expld.dataseg.phase == exp_dataseg_relro_adjust)
 308             {
 309               /* OK.  */
 310             }
 311           else
 312             expld.result.valid_p = FALSE;
 313           break;
 314
 315         default:
 316           FAIL ();
 317           break;
 318         }
 319     }
 320 }
 321
 322 static void
 323 fold_binary (etree_type *tree)
 324 {
 325   etree_value_type lhs;
 326   exp_fold_tree_1 (tree->binary.lhs);
 327
 328   /* The SEGMENT_START operator is special because its first
 329      operand is a string, not the name of a symbol.  Note that the
 330      operands have been swapped, so binary.lhs is second (default)
 331      operand, binary.rhs is first operand.  */
 332   if (expld.result.valid_p && tree->type.node_code == SEGMENT_START)
 333     {
 334       const char *segment_name;
 335       segment_type *seg;
 336
 337       /* Check to see if the user has overridden the default
 338          value.  */
 339       segment_name = tree->binary.rhs->name.name;
 340       for (seg = segments; seg; seg = seg->next)
 341         if (strcmp (seg->name, segment_name) == 0)
 342           {
 343             if (!seg->used
 344                 && config.magic_demand_paged
 345                 && (seg->value % config.maxpagesize) != 0)
 346               einfo (_("%P: warning: address of `%s' isn't multiple of maximum page size\n"),
 347                      segment_name);
 348             seg->used = TRUE;
 349             new_rel_from_abs (seg->value);
 350             break;
 351           }
 352       return;
 353     }
 354
 355   lhs = expld.result;
 356   exp_fold_tree_1 (tree->binary.rhs);
 357   expld.result.valid_p &= lhs.valid_p;
 358
 359   if (expld.result.valid_p)
 360     {
 361       if (lhs.section != expld.result.section)
 362         {
 363           /* If the values are from different sections, and neither is
 364              just a number, make both the source arguments absolute.  */
 365           if (expld.result.section != NULL
 366               && lhs.section != NULL)
 367             {
 368               make_abs ();
 369               lhs.value += lhs.section->vma;
 370               lhs.section = bfd_abs_section_ptr;
 371             }
 372
 373           /* If the rhs is just a number, keep the lhs section.  */
 374           else if (expld.result.section == NULL)
 375             {
 376               expld.result.section = lhs.section;
 377               /* Make this NULL so that we know one of the operands
 378                  was just a number, for later tests.  */
 379               lhs.section = NULL;
 380             }
 381         }
 382       /* At this point we know that both operands have the same
 383          section, or at least one of them is a plain number.  */
 384
 385       switch (tree->type.node_code)
 386         {
 387           /* Arithmetic operators, bitwise AND, bitwise OR and XOR
 388              keep the section of one of their operands only when the
 389              other operand is a plain number.  Losing the section when
 390              operating on two symbols, ie. a result of a plain number,
 391              is required for subtraction and XOR.  It's justifiable
 392              for the other operations on the grounds that adding,
 393              multiplying etc. two section relative values does not
 394              really make sense unless they are just treated as
 395              numbers.
 396              The same argument could be made for many expressions
 397              involving one symbol and a number.  For example,
 398              "1 << x" and "100 / x" probably should not be given the
 399              section of x.  The trouble is that if we fuss about such
 400              things the rules become complex and it is onerous to
 401              document ld expression evaluation.  */
 402 #define BOP(x, y) \
 403         case x:                                                 \
 404           expld.result.value = lhs.value y expld.result.value;  \
 405           if (expld.result.section == lhs.section)              \
 406             expld.result.section = NULL;                        \
 407           break;
 408
 409           /* Comparison operators, logical AND, and logical OR always
 410              return a plain number.  */
 411 #define BOPN(x, y) \
 412         case x:                                                 \
 413           expld.result.value = lhs.value y expld.result.value;  \
 414           expld.result.section = NULL;                          \
 415           break;
 416
 417           BOP ('+', +);
 418           BOP ('*', *);
 419           BOP ('-', -);
 420           BOP (LSHIFT, <<);
 421           BOP (RSHIFT, >>);
 422           BOP ('&', &);
 423           BOP ('^', ^);
 424           BOP ('|', |);
 425           BOPN (EQ, ==);
 426           BOPN (NE, !=);
 427           BOPN ('<', <);
 428           BOPN ('>', >);
 429           BOPN (LE, <=);
 430           BOPN (GE, >=);
 431           BOPN (ANDAND, &&);
 432           BOPN (OROR, ||);
 433
 434         case '%':
 435           if (expld.result.value != 0)
 436             expld.result.value = ((bfd_signed_vma) lhs.value
 437                                   % (bfd_signed_vma) expld.result.value);
 438           else if (expld.phase != lang_mark_phase_enum)
 439             einfo (_("%F%S %% by zero\n"), tree->binary.rhs);
 440           if (expld.result.section == lhs.section)
 441             expld.result.section = NULL;
 442           break;
 443
 444         case '/':
 445           if (expld.result.value != 0)
 446             expld.result.value = ((bfd_signed_vma) lhs.value
 447                                   / (bfd_signed_vma) expld.result.value);
 448           else if (expld.phase != lang_mark_phase_enum)
 449             einfo (_("%F%S / by zero\n"), tree->binary.rhs);
 450           if (expld.result.section == lhs.section)
 451             expld.result.section = NULL;
 452           break;
 453
 454         case MAX_K:
 455           if (lhs.value > expld.result.value)
 456             expld.result.value = lhs.value;
 457           break;
 458
 459         case MIN_K:
 460           if (lhs.value < expld.result.value)
 461             expld.result.value = lhs.value;
 462           break;
 463
 464         case ALIGN_K:
 465           expld.result.value = align_n (lhs.value, expld.result.value);
 466           break;
 467
 468         case DATA_SEGMENT_ALIGN:
 469           expld.dataseg.relro = exp_dataseg_relro_start;
 470           if (expld.phase == lang_first_phase_enum
 471               || expld.section != bfd_abs_section_ptr)
 472             expld.result.valid_p = FALSE;
 473           else
 474             {
 475               bfd_vma maxpage = lhs.value;
 476               bfd_vma commonpage = expld.result.value;
 477
 478               expld.result.value = align_n (expld.dot, maxpage);
 479               if (expld.dataseg.phase == exp_dataseg_relro_adjust)
 480                 expld.result.value = expld.dataseg.base;
 481               else if (expld.dataseg.phase == exp_dataseg_adjust)
 482                 {
 483                   if (commonpage < maxpage)
 484                     expld.result.value += ((expld.dot + commonpage - 1)
 485                                            & (maxpage - commonpage));
 486                 }
 487               else
 488                 {
 489                   expld.result.value += expld.dot & (maxpage - 1);
 490                   if (expld.dataseg.phase == exp_dataseg_done)
 491                     {
 492                       /* OK.  */
 493                     }
 494                   else if (expld.dataseg.phase == exp_dataseg_none)
 495                     {
 496                       expld.dataseg.phase = exp_dataseg_align_seen;
 497                       expld.dataseg.min_base = expld.dot;
 498                       expld.dataseg.base = expld.result.value;
 499                       expld.dataseg.pagesize = commonpage;
 500                       expld.dataseg.maxpagesize = maxpage;
 501                       expld.dataseg.relro_end = 0;
 502                     }
 503                   else
 504                     expld.result.valid_p = FALSE;
 505                 }
 506             }
 507           break;
 508
 509         case DATA_SEGMENT_RELRO_END:
 510           expld.dataseg.relro = exp_dataseg_relro_end;
 511           if (expld.phase == lang_first_phase_enum
 512               || expld.section != bfd_abs_section_ptr)
 513             expld.result.valid_p = FALSE;
 514           else if (expld.dataseg.phase == exp_dataseg_align_seen
 515                    || expld.dataseg.phase == exp_dataseg_adjust
 516                    || expld.dataseg.phase == exp_dataseg_relro_adjust
 517                    || expld.dataseg.phase == exp_dataseg_done)
 518             {
 519               if (expld.dataseg.phase == exp_dataseg_align_seen
 520                   || expld.dataseg.phase == exp_dataseg_relro_adjust)
 521                 expld.dataseg.relro_end = lhs.value + expld.result.value;
 522
 523               if (expld.dataseg.phase == exp_dataseg_relro_adjust
 524                   && (expld.dataseg.relro_end
 525                       & (expld.dataseg.pagesize - 1)))
 526                 {
 527                   expld.dataseg.relro_end += expld.dataseg.pagesize - 1;
 528                   expld.dataseg.relro_end &= ~(expld.dataseg.pagesize - 1);
 529                   expld.result.value = (expld.dataseg.relro_end
 530                                         - expld.result.value);
 531                 }
 532               else
 533                 expld.result.value = lhs.value;
 534
 535               if (expld.dataseg.phase == exp_dataseg_align_seen)
 536                 expld.dataseg.phase = exp_dataseg_relro_seen;
 537             }
 538           else
 539             expld.result.valid_p = FALSE;
 540           break;
 541
 542         default:
 543           FAIL ();
 544         }
 545     }
 546 }
 547
 548 static void
 549 fold_trinary (etree_type *tree)
 550 {
 551   exp_fold_tree_1 (tree->trinary.cond);
 552   if (expld.result.valid_p)
 553     exp_fold_tree_1 (expld.result.value
 554                      ? tree->trinary.lhs
 555                      : tree->trinary.rhs);
 556 }
 557
 558 static void
 559 fold_name (etree_type *tree)
 560 {
 561   memset (&expld.result, 0, sizeof (expld.result));
 562
 563   switch (tree->type.node_code)
 564     {
 565     case SIZEOF_HEADERS:
 566       if (expld.phase != lang_first_phase_enum)
 567         {
 568           bfd_vma hdr_size = 0;
 569           /* Don't find the real header size if only marking sections;
 570              The bfd function may cache incorrect data.  */
 571           if (expld.phase != lang_mark_phase_enum)
 572             hdr_size = bfd_sizeof_headers (link_info.output_bfd, &link_info);
 573           new_number (hdr_size);
 574         }
 575       break;
 576
 577     case DEFINED:
 578       if (expld.phase == lang_first_phase_enum)
 579         lang_track_definedness (tree->name.name);
 580       else
 581         {
 582           struct bfd_link_hash_entry *h;
 583           int def_iteration
 584             = lang_symbol_definition_iteration (tree->name.name);
 585
 586           h = bfd_wrapped_link_hash_lookup (link_info.output_bfd,
 587                                             &link_info,
 588                                             tree->name.name,
 589                                             FALSE, FALSE, TRUE);
 590           new_number (h != NULL
 591                       && (h->type == bfd_link_hash_defined
 592                           || h->type == bfd_link_hash_defweak
 593                           || h->type == bfd_link_hash_common)
 594                       && (def_iteration == lang_statement_iteration
 595                           || def_iteration == -1));
 596         }
 597       break;
 598
 599     case NAME:
 600       if (expld.assign_name != NULL
 601           && strcmp (expld.assign_name, tree->name.name) == 0)
 602         expld.assign_name = NULL;
 603       if (expld.phase == lang_first_phase_enum)
 604         ;
 605       else if (tree->name.name[0] == '.' && tree->name.name[1] == 0)
 606         new_rel_from_abs (expld.dot);
 607       else
 608         {
 609           struct bfd_link_hash_entry *h;
 610
 611           h = bfd_wrapped_link_hash_lookup (link_info.output_bfd,
 612                                             &link_info,
 613                                             tree->name.name,
 614                                             TRUE, FALSE, TRUE);
 615           if (!h)
 616             einfo (_("%P%F: bfd_link_hash_lookup failed: %E\n"));
 617           else if (h->type == bfd_link_hash_defined
 618                    || h->type == bfd_link_hash_defweak)
 619             {
 620               asection *output_section;
 621
 622               output_section = h->u.def.section->output_section;
 623               if (output_section == NULL)
 624                 {
 625                   if (expld.phase == lang_mark_phase_enum)
 626                     new_rel (h->u.def.value, h->u.def.section);
 627                   else
 628                     einfo (_("%X%S: unresolvable symbol `%s'"
 629                              " referenced in expression\n"),
 630                            tree, tree->name.name);
 631                 }
 632               else if (output_section == bfd_abs_section_ptr
 633                        && (expld.section != bfd_abs_section_ptr
 634                            || config.sane_expr))
 635                 new_number (h->u.def.value + h->u.def.section->output_offset);
 636               else
 637                 new_rel (h->u.def.value + h->u.def.section->output_offset,
 638                          output_section);
 639             }
 640           else if (expld.phase == lang_final_phase_enum
 641                    || (expld.phase != lang_mark_phase_enum
 642                        && expld.assigning_to_dot))
 643             einfo (_("%F%S: undefined symbol `%s'"
 644                      " referenced in expression\n"),
 645                    tree, tree->name.name);
 646           else if (h->type == bfd_link_hash_new)
 647             {
 648               h->type = bfd_link_hash_undefined;
 649               h->u.undef.abfd = NULL;
 650               if (h->u.undef.next == NULL && h != link_info.hash->undefs_tail)
 651                 bfd_link_add_undef (link_info.hash, h);
 652             }
 653         }
 654       break;
 655
 656     case ADDR:
 657       if (expld.phase != lang_first_phase_enum)
 658         {
 659           lang_output_section_statement_type *os;
 660
 661           os = lang_output_section_find (tree->name.name);
 662           if (os == NULL)
 663             {
 664               if (expld.phase == lang_final_phase_enum)
 665                 einfo (_("%F%S: undefined section `%s'"
 666                          " referenced in expression\n"),
 667                        tree, tree->name.name);
 668             }
 669           else if (os->processed_vma)
 670             new_rel (0, os->bfd_section);
 671         }
 672       break;
 673
 674     case LOADADDR:
 675       if (expld.phase != lang_first_phase_enum)
 676         {
 677           lang_output_section_statement_type *os;
 678
 679           os = lang_output_section_find (tree->name.name);
 680           if (os == NULL)
 681             {
 682               if (expld.phase == lang_final_phase_enum)
 683                 einfo (_("%F%S: undefined section `%s'"
 684                          " referenced in expression\n"),
 685                        tree, tree->name.name);
 686             }
 687           else if (os->processed_lma)
 688             {
 689               if (os->load_base == NULL)
 690                 new_abs (os->bfd_section->lma);
 691               else
 692                 {
 693                   exp_fold_tree_1 (os->load_base);
 694                   if (expld.result.valid_p)
 695                     make_abs ();
 696                 }
 697             }
 698         }
 699       break;
 700
 701     case SIZEOF:
 702     case ALIGNOF:
 703       if (expld.phase != lang_first_phase_enum)
 704         {
 705           lang_output_section_statement_type *os;
 706
 707           os = lang_output_section_find (tree->name.name);
 708           if (os == NULL)
 709             {
 710               if (expld.phase == lang_final_phase_enum)
 711                 einfo (_("%F%S: undefined section `%s'"
 712                          " referenced in expression\n"),
 713                        tree, tree->name.name);
 714               new_number (0);
 715             }
 716           else if (os->bfd_section != NULL)
 717             {
 718               bfd_vma val;
 719
 720               if (tree->type.node_code == SIZEOF)
 721                 val = (os->bfd_section->size
 722                        / bfd_octets_per_byte (link_info.output_bfd));
 723               else
 724                 val = (bfd_vma)1 << os->bfd_section->alignment_power;
 725
 726               new_number (val);
 727             }
 728           else
 729             new_number (0);
 730         }
 731       break;
 732
 733     case LENGTH:
 734       {
 735         lang_memory_region_type *mem;
 736
 737         mem = lang_memory_region_lookup (tree->name.name, FALSE);
 738         if (mem != NULL)
 739           new_number (mem->length);
 740         else
 741           einfo (_("%F%S: undefined MEMORY region `%s'"
 742                    " referenced in expression\n"),
 743                  tree, tree->name.name);
 744       }
 745       break;
 746
 747     case ORIGIN:
 748       if (expld.phase != lang_first_phase_enum)
 749         {
 750           lang_memory_region_type *mem;
 751
 752           mem = lang_memory_region_lookup (tree->name.name, FALSE);
 753           if (mem != NULL)
 754             new_rel_from_abs (mem->origin);
 755           else
 756             einfo (_("%F%S: undefined MEMORY region `%s'"
 757                      " referenced in expression\n"),
 758                    tree, tree->name.name);
 759         }
 760       break;
 761
 762     case CONSTANT:
 763       if (strcmp (tree->name.name, "MAXPAGESIZE") == 0)
 764         new_number (config.maxpagesize);
 765       else if (strcmp (tree->name.name, "COMMONPAGESIZE") == 0)
 766         new_number (config.commonpagesize);
 767       else
 768         einfo (_("%F%S: unknown constant `%s' referenced in expression\n"),
 769                tree, tree->name.name);
 770       break;
 771
 772     default:
 773       FAIL ();
 774       break;
 775     }
 776 }
 777
 778 static void
 779 exp_fold_tree_1 (etree_type *tree)
 780 {
 781   if (tree == NULL)
 782     {
 783       memset (&expld.result, 0, sizeof (expld.result));
 784       return;
 785     }
 786
 787   switch (tree->type.node_class)
 788     {
 789     case etree_value:
 790       if (expld.section == bfd_abs_section_ptr
 791           && !config.sane_expr)
 792         new_abs (tree->value.value);
 793       else
 794         new_number (tree->value.value);
 795       expld.result.str = tree->value.str;
 796       break;
 797
 798     case etree_rel:
 799       if (expld.phase != lang_first_phase_enum)
 800         {
 801           asection *output_section = tree->rel.section->output_section;
 802           new_rel (tree->rel.value + tree->rel.section->output_offset,
 803                    output_section);
 804         }
 805       else
 806         memset (&expld.result, 0, sizeof (expld.result));
 807       break;
 808
 809     case etree_assert:
 810       exp_fold_tree_1 (tree->assert_s.child);
 811       if (expld.phase == lang_final_phase_enum && !expld.result.value)
 812         einfo ("%X%P: %s\n", tree->assert_s.message);
 813       break;
 814
 815     case etree_unary:
 816       fold_unary (tree);
 817       break;
 818
 819     case etree_binary:
 820       fold_binary (tree);
 821       break;
 822
 823     case etree_trinary:
 824       fold_trinary (tree);
 825       break;
 826
 827     case etree_assign:
 828     case etree_provide:
 829     case etree_provided:
 830       if (tree->assign.dst[0] == '.' && tree->assign.dst[1] == 0)
 831         {
 832           if (tree->type.node_class != etree_assign)
 833             einfo (_("%F%S can not PROVIDE assignment to"
 834                      " location counter\n"), tree);
 835           if (expld.phase != lang_first_phase_enum)
 836             {
 837               /* Notify the folder that this is an assignment to dot.  */
 838               expld.assigning_to_dot = TRUE;
 839               exp_fold_tree_1 (tree->assign.src);
 840               expld.assigning_to_dot = FALSE;
 841
 842               if (!expld.result.valid_p)
 843                 {
 844                   if (expld.phase != lang_mark_phase_enum)
 845                     einfo (_("%F%S invalid assignment to"
 846                              " location counter\n"), tree);
 847                 }
 848               else if (expld.dotp == NULL)
 849                 einfo (_("%F%S assignment to location counter"
 850                          " invalid outside of SECTIONS\n"), tree);
 851
 852               /* After allocation, assignment to dot should not be
 853                  done inside an output section since allocation adds a
 854                  padding statement that effectively duplicates the
 855                  assignment.  */
 856               else if (expld.phase <= lang_allocating_phase_enum
 857                        || expld.section == bfd_abs_section_ptr)
 858                 {
 859                   bfd_vma nextdot;
 860
 861                   nextdot = expld.result.value;
 862                   if (expld.result.section != NULL)
 863                     nextdot += expld.result.section->vma;
 864                   else
 865                     nextdot += expld.section->vma;
 866                   if (nextdot < expld.dot
 867                       && expld.section != bfd_abs_section_ptr)
 868                     einfo (_("%F%S cannot move location counter backwards"
 869                              " (from %V to %V)\n"),
 870                            tree, expld.dot, nextdot);
 871                   else
 872                     {
 873                       expld.dot = nextdot;
 874                       *expld.dotp = nextdot;
 875                     }
 876                 }
 877             }
 878           else
 879             memset (&expld.result, 0, sizeof (expld.result));
 880         }
 881       else
 882         {
 883           struct bfd_link_hash_entry *h = NULL;
 884
 885           if (tree->type.node_class == etree_provide)
 886             {
 887               h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 888                                         FALSE, FALSE, TRUE);
 889               if (h == NULL
 890                   || (h->type != bfd_link_hash_new
 891                       && h->type != bfd_link_hash_undefined
 892                       && h->type != bfd_link_hash_common))
 893                 {
 894                   /* Do nothing.  The symbol was never referenced, or was
 895                      defined by some object.  */
 896                   break;
 897                 }
 898             }
 899
 900           expld.assign_name = tree->assign.dst;
 901           exp_fold_tree_1 (tree->assign.src);
 902           /* expld.assign_name remaining equal to tree->assign.dst
 903              below indicates the evaluation of tree->assign.src did
 904              not use the value of tree->assign.dst.  We don't allow
 905              self assignment until the final phase for two reasons:
 906              1) Expressions are evaluated multiple times.  With
 907              relaxation, the number of times may vary.
 908              2) Section relative symbol values cannot be correctly
 909              converted to absolute values, as is required by many
 910              expressions, until final section sizing is complete.  */
 911           if ((expld.result.valid_p
 912                && (expld.phase == lang_final_phase_enum
 913                    || expld.assign_name != NULL))
 914               || (expld.phase <= lang_mark_phase_enum
 915                   && tree->type.node_class == etree_assign
 916                   && tree->assign.defsym))
 917             {
 918               if (h == NULL)
 919                 {
 920                   h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 921                                             TRUE, FALSE, TRUE);
 922                   if (h == NULL)
 923                     einfo (_("%P%F:%s: hash creation failed\n"),
 924                            tree->assign.dst);
 925                 }
 926
 927               /* FIXME: Should we worry if the symbol is already
 928                  defined?  */
 929               lang_update_definedness (tree->assign.dst, h);
 930               h->type = bfd_link_hash_defined;
 931               h->u.def.value = expld.result.value;
 932               if (expld.result.section == NULL)
 933                 expld.result.section = expld.section;
 934               h->u.def.section = expld.result.section;
 935               if (tree->type.node_class == etree_provide)
 936                 tree->type.node_class = etree_provided;
 937
 938               /* Copy the symbol type if this is a simple assignment of
 939                  one symbol to another.  This could be more general
 940                  (e.g. a ?: operator with NAMEs in each branch).  */
 941               if (tree->assign.src->type.node_class == etree_name)
 942                 {
 943                   struct bfd_link_hash_entry *hsrc;
 944
 945                   hsrc = bfd_link_hash_lookup (link_info.hash,
 946                                                tree->assign.src->name.name,
 947                                                FALSE, FALSE, TRUE);
 948                   if (hsrc)
 949                     bfd_copy_link_hash_symbol_type (link_info.output_bfd, h,
 950                                                     hsrc);
 951                 }
 952             }
 953           else if (expld.phase == lang_final_phase_enum)
 954             {
 955               h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 956                                         FALSE, FALSE, TRUE);
 957               if (h != NULL
 958                   && h->type == bfd_link_hash_new)
 959                 h->type = bfd_link_hash_undefined;
 960             }
 961           expld.assign_name = NULL;
 962         }
 963       break;
 964
 965     case etree_name:
 966       fold_name (tree);
 967       break;
 968
 969     default:
 970       FAIL ();
 971       memset (&expld.result, 0, sizeof (expld.result));
 972       break;
 973     }
 974 }
 975
 976 void
 977 exp_fold_tree (etree_type *tree, asection *current_section, bfd_vma *dotp)
 978 {
 979   expld.dot = *dotp;
 980   expld.dotp = dotp;
 981   expld.section = current_section;
 982   exp_fold_tree_1 (tree);
 983 }
 984
 985 void
 986 exp_fold_tree_no_dot (etree_type *tree)
 987 {
 988   expld.dot = 0;
 989   expld.dotp = NULL;
 990   expld.section = bfd_abs_section_ptr;
 991   exp_fold_tree_1 (tree);
 992 }
 993
 994 etree_type *
 995 exp_binop (int code, etree_type *lhs, etree_type *rhs)
 996 {
 997   etree_type value, *new_e;
 998
 999   value.type.node_code = code;
1000   value.type.filename = lhs->type.filename;
1001   value.type.lineno = lhs->type.lineno;
1002   value.binary.lhs = lhs;
1003   value.binary.rhs = rhs;
1004   value.type.node_class = etree_binary;
1005   exp_fold_tree_no_dot (&value);
1006   if (expld.result.valid_p)
1007     return exp_intop (expld.result.value);
1008
1009   new_e = (etree_type *) stat_alloc (sizeof (new_e->binary));
1010   memcpy (new_e, &value, sizeof (new_e->binary));
1011   return new_e;
1012 }
1013
1014 etree_type *
1015 exp_trinop (int code, etree_type *cond, etree_type *lhs, etree_type *rhs)
1016 {
1017   etree_type value, *new_e;
1018
1019   value.type.node_code = code;
1020   value.type.filename = cond->type.filename;
1021   value.type.lineno = cond->type.lineno;
1022   value.trinary.lhs = lhs;
1023   value.trinary.cond = cond;
1024   value.trinary.rhs = rhs;
1025   value.type.node_class = etree_trinary;
1026   exp_fold_tree_no_dot (&value);
1027   if (expld.result.valid_p)
1028     return exp_intop (expld.result.value);
1029
1030   new_e = (etree_type *) stat_alloc (sizeof (new_e->trinary));
1031   memcpy (new_e, &value, sizeof (new_e->trinary));
1032   return new_e;
1033 }
1034
1035 etree_type *
1036 exp_unop (int code, etree_type *child)
1037 {
1038   etree_type value, *new_e;
1039
1040   value.unary.type.node_code = code;
1041   value.unary.type.filename = child->type.filename;
1042   value.unary.type.lineno = child->type.lineno;
1043   value.unary.child = child;
1044   value.unary.type.node_class = etree_unary;
1045   exp_fold_tree_no_dot (&value);
1046   if (expld.result.valid_p)
1047     return exp_intop (expld.result.value);
1048
1049   new_e = (etree_type *) stat_alloc (sizeof (new_e->unary));
1050   memcpy (new_e, &value, sizeof (new_e->unary));
1051   return new_e;
1052 }
1053
1054 etree_type *
1055 exp_nameop (int code, const char *name)
1056 {
1057   etree_type value, *new_e;
1058
1059   value.name.type.node_code = code;
1060   value.name.type.filename = ldlex_filename ();
1061   value.name.type.lineno = lineno;
1062   value.name.name = name;
1063   value.name.type.node_class = etree_name;
1064
1065   exp_fold_tree_no_dot (&value);
1066   if (expld.result.valid_p)
1067     return exp_intop (expld.result.value);
1068
1069   new_e = (etree_type *) stat_alloc (sizeof (new_e->name));
1070   memcpy (new_e, &value, sizeof (new_e->name));
1071   return new_e;
1072
1073 }
1074
1075 static etree_type *
1076 exp_assop (const char *dst,
1077            etree_type *src,
1078            enum node_tree_enum class,
1079            bfd_boolean defsym,
1080            bfd_boolean hidden)
1081 {
1082   etree_type *n;
1083
1084   n = (etree_type *) stat_alloc (sizeof (n->assign));
1085   n->assign.type.node_code = '=';
1086   n->assign.type.filename = src->type.filename;
1087   n->assign.type.lineno = src->type.lineno;
1088   n->assign.type.node_class = class;
1089   n->assign.src = src;
1090   n->assign.dst = dst;
1091   n->assign.defsym = defsym;
1092   n->assign.hidden = hidden;
1093   return n;
1094 }
1095
1096 /* Handle linker script assignments and HIDDEN.  */
1097
1098 etree_type *
1099 exp_assign (const char *dst, etree_type *src, bfd_boolean hidden)
1100 {
1101   return exp_assop (dst, src, etree_assign, FALSE, hidden);
1102 }
1103
1104 /* Handle --defsym command-line option.  */
1105
1106 etree_type *
1107 exp_defsym (const char *dst, etree_type *src)
1108 {
1109   return exp_assop (dst, src, etree_assign, TRUE, FALSE);
1110 }
1111
1112 /* Handle PROVIDE.  */
1113
1114 etree_type *
1115 exp_provide (const char *dst, etree_type *src, bfd_boolean hidden)
1116 {
1117   return exp_assop (dst, src, etree_provide, FALSE, hidden);
1118 }
1119
1120 /* Handle ASSERT.  */
1121
1122 etree_type *
1123 exp_assert (etree_type *exp, const char *message)
1124 {
1125   etree_type *n;
1126
1127   n = (etree_type *) stat_alloc (sizeof (n->assert_s));
1128   n->assert_s.type.node_code = '!';
1129   n->assert_s.type.filename = exp->type.filename;
1130   n->assert_s.type.lineno = exp->type.lineno;
1131   n->assert_s.type.node_class = etree_assert;
1132   n->assert_s.child = exp;
1133   n->assert_s.message = message;
1134   return n;
1135 }
1136
1137 void
1138 exp_print_tree (etree_type *tree)
1139 {
1140   bfd_boolean function_like;
1141
1142   if (config.map_file == NULL)
1143     config.map_file = stderr;
1144
1145   if (tree == NULL)
1146     {
1147       minfo ("NULL TREE\n");
1148       return;
1149     }
1150
1151   switch (tree->type.node_class)
1152     {
1153     case etree_value:
1154       minfo ("0x%v", tree->value.value);
1155       return;
1156     case etree_rel:
1157       if (tree->rel.section->owner != NULL)
1158         minfo ("%B:", tree->rel.section->owner);
1159       minfo ("%s+0x%v", tree->rel.section->name, tree->rel.value);
1160       return;
1161     case etree_assign:
1162       fputs (tree->assign.dst, config.map_file);
1163       exp_print_token (tree->type.node_code, TRUE);
1164       exp_print_tree (tree->assign.src);
1165       break;
1166     case etree_provide:
1167     case etree_provided:
1168       fprintf (config.map_file, "PROVIDE (%s, ", tree->assign.dst);
1169       exp_print_tree (tree->assign.src);
1170       fputc (')', config.map_file);
1171       break;
1172     case etree_binary:
1173       function_like = FALSE;
1174       switch (tree->type.node_code)
1175         {
1176         case MAX_K:
1177         case MIN_K:
1178         case ALIGN_K:
1179         case DATA_SEGMENT_ALIGN:
1180         case DATA_SEGMENT_RELRO_END:
1181           function_like = TRUE;
1182           break;
1183         case SEGMENT_START:
1184           /* Special handling because arguments are in reverse order and
1185              the segment name is quoted.  */
1186           exp_print_token (tree->type.node_code, FALSE);
1187           fputs (" (\"", config.map_file);
1188           exp_print_tree (tree->binary.rhs);
1189           fputs ("\", ", config.map_file);
1190           exp_print_tree (tree->binary.lhs);
1191           fputc (')', config.map_file);
1192           return;
1193         }
1194       if (function_like)
1195         {
1196           exp_print_token (tree->type.node_code, FALSE);
1197           fputc (' ', config.map_file);
1198         }
1199       fputc ('(', config.map_file);
1200       exp_print_tree (tree->binary.lhs);
1201       if (function_like)
1202         fprintf (config.map_file, ", ");
1203       else
1204         exp_print_token (tree->type.node_code, TRUE);
1205       exp_print_tree (tree->binary.rhs);
1206       fputc (')', config.map_file);
1207       break;
1208     case etree_trinary:
1209       exp_print_tree (tree->trinary.cond);
1210       fputc ('?', config.map_file);
1211       exp_print_tree (tree->trinary.lhs);
1212       fputc (':', config.map_file);
1213       exp_print_tree (tree->trinary.rhs);
1214       break;
1215     case etree_unary:
1216       exp_print_token (tree->unary.type.node_code, FALSE);
1217       if (tree->unary.child)
1218         {
1219           fprintf (config.map_file, " (");
1220           exp_print_tree (tree->unary.child);
1221           fputc (')', config.map_file);
1222         }
1223       break;
1224
1225     case etree_assert:
1226       fprintf (config.map_file, "ASSERT (");
1227       exp_print_tree (tree->assert_s.child);
1228       fprintf (config.map_file, ", %s)", tree->assert_s.message);
1229       break;
1230
1231     case etree_name:
1232       if (tree->type.node_code == NAME)
1233         fputs (tree->name.name, config.map_file);
1234       else
1235         {
1236           exp_print_token (tree->type.node_code, FALSE);
1237           if (tree->name.name)
1238             fprintf (config.map_file, " (%s)", tree->name.name);
1239         }
1240       break;
1241     default:
1242       FAIL ();
1243       break;
1244     }
1245 }
1246
1247 bfd_vma
1248 exp_get_vma (etree_type *tree, bfd_vma def, char *name)
1249 {
1250   if (tree != NULL)
1251     {
1252       exp_fold_tree_no_dot (tree);
1253       if (expld.result.valid_p)
1254         return expld.result.value;
1255       else if (name != NULL && expld.phase != lang_mark_phase_enum)
1256         einfo (_("%F%S: nonconstant expression for %s\n"),
1257                tree, name);
1258     }
1259   return def;
1260 }
1261
1262 int
1263 exp_get_value_int (etree_type *tree, int def, char *name)
1264 {
1265   return exp_get_vma (tree, def, name);
1266 }
1267
1268 fill_type *
1269 exp_get_fill (etree_type *tree, fill_type *def, char *name)
1270 {
1271   fill_type *fill;
1272   size_t len;
1273   unsigned int val;
1274
1275   if (tree == NULL)
1276     return def;
1277
1278   exp_fold_tree_no_dot (tree);
1279   if (!expld.result.valid_p)
1280     {
1281       if (name != NULL && expld.phase != lang_mark_phase_enum)
1282         einfo (_("%F%S: nonconstant expression for %s\n"),
1283                tree, name);
1284       return def;
1285     }
1286
1287   if (expld.result.str != NULL && (len = strlen (expld.result.str)) != 0)
1288     {
1289       unsigned char *dst;
1290       unsigned char *s;
1291       fill = (fill_type *) xmalloc ((len + 1) / 2 + sizeof (*fill) - 1);
1292       fill->size = (len + 1) / 2;
1293       dst = fill->data;
1294       s = (unsigned char *) expld.result.str;
1295       val = 0;
1296       do
1297         {
1298           unsigned int digit;
1299
1300           digit = *s++ - '0';
1301           if (digit > 9)
1302             digit = (digit - 'A' + '0' + 10) & 0xf;
1303           val <<= 4;
1304           val += digit;
1305           --len;
1306           if ((len & 1) == 0)
1307             {
1308               *dst++ = val;
1309               val = 0;
1310             }
1311         }
1312       while (len != 0);
1313     }
1314   else
1315     {
1316       fill = (fill_type *) xmalloc (4 + sizeof (*fill) - 1);
1317       val = expld.result.value;
1318       fill->data[0] = (val >> 24) & 0xff;
1319       fill->data[1] = (val >> 16) & 0xff;
1320       fill->data[2] = (val >>  8) & 0xff;
1321       fill->data[3] = (val >>  0) & 0xff;
1322       fill->size = 4;
1323     }
1324   return fill;
1325 }
1326
1327 bfd_vma
1328 exp_get_abs_int (etree_type *tree, int def, char *name)
1329 {
1330   if (tree != NULL)
1331     {
1332       exp_fold_tree_no_dot (tree);
1333
1334       if (expld.result.valid_p)
1335         {
1336           if (expld.result.section != NULL)
1337             expld.result.value += expld.result.section->vma;
1338           return expld.result.value;
1339         }
1340       else if (name != NULL && expld.phase != lang_mark_phase_enum)
1341         {
1342           einfo (_("%F%S: nonconstant expression for %s\n"),
1343                  tree, name);
1344         }
1345     }
1346   return def;
1347 }
1348
1349 static bfd_vma
1350 align_n (bfd_vma value, bfd_vma align)
1351 {
1352   if (align <= 1)
1353     return value;
1354
1355   value = (value + align - 1) / align;
1356   return value * align;
1357 }