ld/ldexp.c

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