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
   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 void exp_fold_tree_no_dot (etree_type *);
  48 static bfd_vma align_n (bfd_vma, bfd_vma);
  49
  50 segment_type *segments;
  51
  52 struct ldexp_control expld;
  53
  54 /* Print the string representation of the given token.  Surround it
  55    with spaces if INFIX_P is TRUE.  */
  56
  57 static void
  58 exp_print_token (token_code_type code, int infix_p)
  59 {
  60   static const struct
  61   {
  62     token_code_type code;
  63     char * name;
  64   }
  65   table[] =
  66   {
  67     { INT, "int" },
  68     { NAME, "NAME" },
  69     { PLUSEQ, "+=" },
  70     { MINUSEQ, "-=" },
  71     { MULTEQ, "*=" },
  72     { DIVEQ, "/=" },
  73     { LSHIFTEQ, "<<=" },
  74     { RSHIFTEQ, ">>=" },
  75     { ANDEQ, "&=" },
  76     { OREQ, "|=" },
  77     { OROR, "||" },
  78     { ANDAND, "&&" },
  79     { EQ, "==" },
  80     { NE, "!=" },
  81     { LE, "<=" },
  82     { GE, ">=" },
  83     { LSHIFT, "<<" },
  84     { RSHIFT, ">>" },
  85     { ALIGN_K, "ALIGN" },
  86     { BLOCK, "BLOCK" },
  87     { QUAD, "QUAD" },
  88     { SQUAD, "SQUAD" },
  89     { LONG, "LONG" },
  90     { SHORT, "SHORT" },
  91     { BYTE, "BYTE" },
  92     { SECTIONS, "SECTIONS" },
  93     { SIZEOF_HEADERS, "SIZEOF_HEADERS" },
  94     { MEMORY, "MEMORY" },
  95     { DEFINED, "DEFINED" },
  96     { TARGET_K, "TARGET" },
  97     { SEARCH_DIR, "SEARCH_DIR" },
  98     { MAP, "MAP" },
  99     { ENTRY, "ENTRY" },
 100     { NEXT, "NEXT" },
 101     { ALIGNOF, "ALIGNOF" },
 102     { SIZEOF, "SIZEOF" },
 103     { ADDR, "ADDR" },
 104     { LOADADDR, "LOADADDR" },
 105     { CONSTANT, "CONSTANT" },
 106     { ABSOLUTE, "ABSOLUTE" },
 107     { MAX_K, "MAX" },
 108     { MIN_K, "MIN" },
 109     { ASSERT_K, "ASSERT" },
 110     { REL, "relocatable" },
 111     { DATA_SEGMENT_ALIGN, "DATA_SEGMENT_ALIGN" },
 112     { DATA_SEGMENT_RELRO_END, "DATA_SEGMENT_RELRO_END" },
 113     { DATA_SEGMENT_END, "DATA_SEGMENT_END" },
 114     { ORIGIN, "ORIGIN" },
 115     { LENGTH, "LENGTH" },
 116     { SEGMENT_START, "SEGMENT_START" }
 117   };
 118   unsigned int idx;
 119
 120   for (idx = 0; idx < ARRAY_SIZE (table); idx++)
 121     if (table[idx].code == code)
 122       break;
 123
 124   if (infix_p)
 125     fputc (' ', config.map_file);
 126
 127   if (idx < ARRAY_SIZE (table))
 128     fputs (table[idx].name, config.map_file);
 129   else if (code < 127)
 130     fputc (code, config.map_file);
 131   else
 132     fprintf (config.map_file, "<code %d>", code);
 133
 134   if (infix_p)
 135     fputc (' ', config.map_file);
 136 }
 137
 138 static void
 139 make_abs (void)
 140 {
 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 = stat_alloc (sizeof (new->value));
 158   new->type.node_code = INT;
 159   new->type.lineno = lineno;
 160   new->value.value = value;
 161   new->value.str = NULL;
 162   new->type.node_class = etree_value;
 163   return new;
 164 }
 165
 166 etree_type *
 167 exp_bigintop (bfd_vma value, char *str)
 168 {
 169   etree_type *new = stat_alloc (sizeof (new->value));
 170   new->type.node_code = INT;
 171   new->type.lineno = lineno;
 172   new->value.value = value;
 173   new->value.str = str;
 174   new->type.node_class = etree_value;
 175   return new;
 176 }
 177
 178 /* Build an expression representing an unnamed relocatable value.  */
 179
 180 etree_type *
 181 exp_relop (asection *section, bfd_vma value)
 182 {
 183   etree_type *new = stat_alloc (sizeof (new->rel));
 184   new->type.node_code = REL;
 185   new->type.lineno = lineno;
 186   new->type.node_class = etree_rel;
 187   new->rel.section = section;
 188   new->rel.value = value;
 189   return new;
 190 }
 191
 192 static void
 193 new_rel (bfd_vma value, char *str, asection *section)
 194 {
 195   expld.result.valid_p = TRUE;
 196   expld.result.value = value;
 197   expld.result.str = str;
 198   expld.result.section = section;
 199 }
 200
 201 static void
 202 new_rel_from_abs (bfd_vma value)
 203 {
 204   expld.result.valid_p = TRUE;
 205   expld.result.value = value - expld.section->vma;
 206   expld.result.str = NULL;
 207   expld.result.section = expld.section;
 208 }
 209
 210 static void
 211 fold_unary (etree_type *tree)
 212 {
 213   exp_fold_tree_1 (tree->unary.child);
 214   if (expld.result.valid_p)
 215     {
 216       switch (tree->type.node_code)
 217         {
 218         case ALIGN_K:
 219           if (expld.phase != lang_first_phase_enum)
 220             new_rel_from_abs (align_n (expld.dot, expld.result.value));
 221           else
 222             expld.result.valid_p = FALSE;
 223           break;
 224
 225         case ABSOLUTE:
 226           make_abs ();
 227           break;
 228
 229         case '~':
 230           make_abs ();
 231           expld.result.value = ~expld.result.value;
 232           break;
 233
 234         case '!':
 235           make_abs ();
 236           expld.result.value = !expld.result.value;
 237           break;
 238
 239         case '-':
 240           make_abs ();
 241           expld.result.value = -expld.result.value;
 242           break;
 243
 244         case NEXT:
 245           /* Return next place aligned to value.  */
 246           if (expld.phase != lang_first_phase_enum)
 247             {
 248               make_abs ();
 249               expld.result.value = align_n (expld.dot, expld.result.value);
 250             }
 251           else
 252             expld.result.valid_p = FALSE;
 253           break;
 254
 255         case DATA_SEGMENT_END:
 256           if (expld.phase != lang_first_phase_enum
 257               && expld.section == bfd_abs_section_ptr
 258               && (expld.dataseg.phase == exp_dataseg_align_seen
 259                   || expld.dataseg.phase == exp_dataseg_relro_seen
 260                   || expld.dataseg.phase == exp_dataseg_adjust
 261                   || expld.dataseg.phase == exp_dataseg_relro_adjust
 262                   || expld.phase == lang_final_phase_enum))
 263             {
 264               if (expld.dataseg.phase == exp_dataseg_align_seen
 265                   || expld.dataseg.phase == exp_dataseg_relro_seen)
 266                 {
 267                   expld.dataseg.phase = exp_dataseg_end_seen;
 268                   expld.dataseg.end = expld.result.value;
 269                 }
 270             }
 271           else
 272             expld.result.valid_p = FALSE;
 273           break;
 274
 275         default:
 276           FAIL ();
 277           break;
 278         }
 279     }
 280 }
 281
 282 static void
 283 fold_binary (etree_type *tree)
 284 {
 285   etree_value_type lhs;
 286   exp_fold_tree_1 (tree->binary.lhs);
 287
 288   /* The SEGMENT_START operator is special because its first
 289      operand is a string, not the name of a symbol.  Note that the
 290      operands have been swapped, so binary.lhs is second (default)
 291      operand, binary.rhs is first operand.  */
 292   if (expld.result.valid_p && tree->type.node_code == SEGMENT_START)
 293     {
 294       const char *segment_name;
 295       segment_type *seg;
 296       /* Check to see if the user has overridden the default
 297          value.  */
 298       segment_name = tree->binary.rhs->name.name;
 299       for (seg = segments; seg; seg = seg->next)
 300         if (strcmp (seg->name, segment_name) == 0)
 301           {
 302             seg->used = TRUE;
 303             expld.result.value = seg->value;
 304             expld.result.str = NULL;
 305             expld.result.section = expld.section;
 306             break;
 307           }
 308       return;
 309     }
 310
 311   lhs = expld.result;
 312   exp_fold_tree_1 (tree->binary.rhs);
 313   expld.result.valid_p &= lhs.valid_p;
 314
 315   if (expld.result.valid_p)
 316     {
 317       /* If the values are from different sections, or this is an
 318          absolute expression, make both the source arguments
 319          absolute.  However, adding or subtracting an absolute
 320          value from a relative value is meaningful, and is an
 321          exception.  */
 322       if (expld.section != bfd_abs_section_ptr
 323           && lhs.section == bfd_abs_section_ptr
 324           && tree->type.node_code == '+')
 325         {
 326           /* Keep the section of the rhs term.  */
 327           expld.result.value = lhs.value + expld.result.value;
 328           return;
 329         }
 330       else if (expld.section != bfd_abs_section_ptr
 331                && expld.result.section == bfd_abs_section_ptr
 332                && (tree->type.node_code == '+'
 333                    || tree->type.node_code == '-'))
 334         {
 335           /* Keep the section of the lhs term.  */
 336           expld.result.section = lhs.section;
 337         }
 338       else if (expld.result.section != lhs.section
 339                || expld.section == bfd_abs_section_ptr)
 340         {
 341           make_abs ();
 342           lhs.value += lhs.section->vma;
 343         }
 344
 345       switch (tree->type.node_code)
 346         {
 347         case '%':
 348           if (expld.result.value != 0)
 349             expld.result.value = ((bfd_signed_vma) lhs.value
 350                                   % (bfd_signed_vma) expld.result.value);
 351           else if (expld.phase != lang_mark_phase_enum)
 352             einfo (_("%F%S %% by zero\n"));
 353           break;
 354
 355         case '/':
 356           if (expld.result.value != 0)
 357             expld.result.value = ((bfd_signed_vma) lhs.value
 358                                   / (bfd_signed_vma) expld.result.value);
 359           else if (expld.phase != lang_mark_phase_enum)
 360             einfo (_("%F%S / by zero\n"));
 361           break;
 362
 363 #define BOP(x, y) \
 364             case x:                                                     \
 365               expld.result.value = lhs.value y expld.result.value;      \
 366               break;
 367
 368           BOP ('+', +);
 369           BOP ('*', *);
 370           BOP ('-', -);
 371           BOP (LSHIFT, <<);
 372           BOP (RSHIFT, >>);
 373           BOP (EQ, ==);
 374           BOP (NE, !=);
 375           BOP ('<', <);
 376           BOP ('>', >);
 377           BOP (LE, <=);
 378           BOP (GE, >=);
 379           BOP ('&', &);
 380           BOP ('^', ^);
 381           BOP ('|', |);
 382           BOP (ANDAND, &&);
 383           BOP (OROR, ||);
 384
 385         case MAX_K:
 386           if (lhs.value > expld.result.value)
 387             expld.result.value = lhs.value;
 388           break;
 389
 390         case MIN_K:
 391           if (lhs.value < expld.result.value)
 392             expld.result.value = lhs.value;
 393           break;
 394
 395         case ALIGN_K:
 396           expld.result.value = align_n (lhs.value, expld.result.value);
 397           break;
 398
 399         case DATA_SEGMENT_ALIGN:
 400           expld.dataseg.relro = exp_dataseg_relro_start;
 401           if (expld.phase != lang_first_phase_enum
 402               && expld.section == bfd_abs_section_ptr
 403               && (expld.dataseg.phase == exp_dataseg_none
 404                   || expld.dataseg.phase == exp_dataseg_adjust
 405                   || expld.dataseg.phase == exp_dataseg_relro_adjust
 406                   || expld.phase == lang_final_phase_enum))
 407             {
 408               bfd_vma maxpage = lhs.value;
 409               bfd_vma commonpage = expld.result.value;
 410
 411               expld.result.value = align_n (expld.dot, maxpage);
 412               if (expld.dataseg.phase == exp_dataseg_relro_adjust)
 413                 expld.result.value = expld.dataseg.base;
 414               else if (expld.dataseg.phase != exp_dataseg_adjust)
 415                 {
 416                   expld.result.value += expld.dot & (maxpage - 1);
 417                   if (expld.phase == lang_allocating_phase_enum)
 418                     {
 419                       expld.dataseg.phase = exp_dataseg_align_seen;
 420                       expld.dataseg.min_base = expld.dot;
 421                       expld.dataseg.base = expld.result.value;
 422                       expld.dataseg.pagesize = commonpage;
 423                       expld.dataseg.maxpagesize = maxpage;
 424                       expld.dataseg.relro_end = 0;
 425                     }
 426                 }
 427               else if (commonpage < maxpage)
 428                 expld.result.value += ((expld.dot + commonpage - 1)
 429                                        & (maxpage - commonpage));
 430             }
 431           else
 432             expld.result.valid_p = FALSE;
 433           break;
 434
 435         case DATA_SEGMENT_RELRO_END:
 436           expld.dataseg.relro = exp_dataseg_relro_end;
 437           if (expld.phase != lang_first_phase_enum
 438               && (expld.dataseg.phase == exp_dataseg_align_seen
 439                   || expld.dataseg.phase == exp_dataseg_adjust
 440                   || expld.dataseg.phase == exp_dataseg_relro_adjust
 441                   || expld.phase == lang_final_phase_enum))
 442             {
 443               if (expld.dataseg.phase == exp_dataseg_align_seen
 444                   || expld.dataseg.phase == exp_dataseg_relro_adjust)
 445                 expld.dataseg.relro_end = lhs.value + expld.result.value;
 446
 447               if (expld.dataseg.phase == exp_dataseg_relro_adjust
 448                   && (expld.dataseg.relro_end
 449                       & (expld.dataseg.pagesize - 1)))
 450                 {
 451                   expld.dataseg.relro_end += expld.dataseg.pagesize - 1;
 452                   expld.dataseg.relro_end &= ~(expld.dataseg.pagesize - 1);
 453                   expld.result.value = (expld.dataseg.relro_end
 454                                         - expld.result.value);
 455                 }
 456               else
 457                 expld.result.value = lhs.value;
 458
 459               if (expld.dataseg.phase == exp_dataseg_align_seen)
 460                 expld.dataseg.phase = exp_dataseg_relro_seen;
 461             }
 462           else
 463             expld.result.valid_p = FALSE;
 464           break;
 465
 466         default:
 467           FAIL ();
 468         }
 469     }
 470 }
 471
 472 static void
 473 fold_trinary (etree_type *tree)
 474 {
 475   exp_fold_tree_1 (tree->trinary.cond);
 476   if (expld.result.valid_p)
 477     exp_fold_tree_1 (expld.result.value
 478                      ? tree->trinary.lhs
 479                      : tree->trinary.rhs);
 480 }
 481
 482 static void
 483 fold_name (etree_type *tree)
 484 {
 485   memset (&expld.result, 0, sizeof (expld.result));
 486
 487   switch (tree->type.node_code)
 488     {
 489     case SIZEOF_HEADERS:
 490       if (expld.phase != lang_first_phase_enum)
 491         {
 492           bfd_vma hdr_size = 0;
 493           /* Don't find the real header size if only marking sections;
 494              The bfd function may cache incorrect data.  */
 495           if (expld.phase != lang_mark_phase_enum)
 496             hdr_size = bfd_sizeof_headers (link_info.output_bfd, &link_info);
 497           new_abs (hdr_size);
 498         }
 499       break;
 500
 501     case DEFINED:
 502       if (expld.phase == lang_first_phase_enum)
 503         lang_track_definedness (tree->name.name);
 504       else
 505         {
 506           struct bfd_link_hash_entry *h;
 507           int def_iteration
 508             = lang_symbol_definition_iteration (tree->name.name);
 509
 510           h = bfd_wrapped_link_hash_lookup (link_info.output_bfd,
 511                                             &link_info,
 512                                             tree->name.name,
 513                                             FALSE, FALSE, TRUE);
 514           expld.result.value = (h != NULL
 515                                 && (h->type == bfd_link_hash_defined
 516                                     || h->type == bfd_link_hash_defweak
 517                                     || h->type == bfd_link_hash_common)
 518                                 && (def_iteration == lang_statement_iteration
 519                                     || def_iteration == -1));
 520           expld.result.section = expld.section;
 521           expld.result.valid_p = TRUE;
 522         }
 523       break;
 524
 525     case NAME:
 526       if (expld.phase == lang_first_phase_enum)
 527         ;
 528       else if (tree->name.name[0] == '.' && tree->name.name[1] == 0)
 529         new_rel_from_abs (expld.dot);
 530       else
 531         {
 532           struct bfd_link_hash_entry *h;
 533
 534           h = bfd_wrapped_link_hash_lookup (link_info.output_bfd,
 535                                             &link_info,
 536                                             tree->name.name,
 537                                             TRUE, FALSE, TRUE);
 538           if (!h)
 539             einfo (_("%P%F: bfd_link_hash_lookup failed: %E\n"));
 540           else if (h->type == bfd_link_hash_defined
 541                    || h->type == bfd_link_hash_defweak)
 542             {
 543               if (bfd_is_abs_section (h->u.def.section))
 544                 new_abs (h->u.def.value);
 545               else
 546                 {
 547                   asection *output_section;
 548
 549                   output_section = h->u.def.section->output_section;
 550                   if (output_section == NULL)
 551                     {
 552                       if (expld.phase != lang_mark_phase_enum)
 553                         einfo (_("%X%S: unresolvable symbol `%s'"
 554                                  " referenced in expression\n"),
 555                                tree->name.name);
 556                     }
 557                   else
 558                     new_rel (h->u.def.value + h->u.def.section->output_offset,
 559                              NULL, output_section);
 560                 }
 561             }
 562           else if (expld.phase == lang_final_phase_enum
 563                    || expld.assigning_to_dot)
 564             einfo (_("%F%S: undefined symbol `%s' referenced in expression\n"),
 565                    tree->name.name);
 566           else if (h->type == bfd_link_hash_new)
 567             {
 568               h->type = bfd_link_hash_undefined;
 569               h->u.undef.abfd = NULL;
 570               if (h->u.undef.next == NULL && h != link_info.hash->undefs_tail)
 571                 bfd_link_add_undef (link_info.hash, h);
 572             }
 573         }
 574       break;
 575
 576     case ADDR:
 577       if (expld.phase != lang_first_phase_enum)
 578         {
 579           lang_output_section_statement_type *os;
 580
 581           os = lang_output_section_find (tree->name.name);
 582           if (os == NULL)
 583             {
 584               if (expld.phase == lang_final_phase_enum)
 585                 einfo (_("%F%S: undefined section `%s' referenced in expression\n"),
 586                        tree->name.name);
 587             }
 588           else if (os->processed_vma)
 589             new_rel (0, NULL, os->bfd_section);
 590         }
 591       break;
 592
 593     case LOADADDR:
 594       if (expld.phase != lang_first_phase_enum)
 595         {
 596           lang_output_section_statement_type *os;
 597
 598           os = lang_output_section_find (tree->name.name);
 599           if (os == NULL)
 600             {
 601               if (expld.phase == lang_final_phase_enum)
 602                 einfo (_("%F%S: undefined section `%s' referenced in expression\n"),
 603                        tree->name.name);
 604             }
 605           else if (os->processed_lma)
 606             {
 607               if (os->load_base == NULL)
 608                 new_abs (os->bfd_section->lma);
 609               else
 610                 {
 611                   exp_fold_tree_1 (os->load_base);
 612                   if (expld.result.valid_p)
 613                     make_abs ();
 614                 }
 615             }
 616         }
 617       break;
 618
 619     case SIZEOF:
 620     case ALIGNOF:
 621       if (expld.phase != lang_first_phase_enum)
 622         {
 623           lang_output_section_statement_type *os;
 624
 625           os = lang_output_section_find (tree->name.name);
 626           if (os == NULL)
 627             {
 628               if (expld.phase == lang_final_phase_enum)
 629                 einfo (_("%F%S: undefined section `%s' referenced in expression\n"),
 630                        tree->name.name);
 631               new_abs (0);
 632             }
 633           else if (os->processed_vma)
 634             {
 635               bfd_vma val;
 636
 637               if (tree->type.node_code == SIZEOF)
 638                 val = (os->bfd_section->size
 639                        / bfd_octets_per_byte (link_info.output_bfd));
 640               else
 641                 val = (bfd_vma)1 << os->bfd_section->alignment_power;
 642
 643               new_abs (val);
 644             }
 645         }
 646       break;
 647
 648     case LENGTH:
 649       {
 650         lang_memory_region_type *mem;
 651
 652         mem = lang_memory_region_lookup (tree->name.name, FALSE);
 653         if (mem != NULL)
 654           new_abs (mem->length);
 655         else
 656           einfo (_("%F%S: undefined MEMORY region `%s'"
 657                    " referenced in expression\n"), tree->name.name);
 658       }
 659       break;
 660
 661     case ORIGIN:
 662       {
 663         lang_memory_region_type *mem;
 664
 665         mem = lang_memory_region_lookup (tree->name.name, FALSE);
 666         if (mem != NULL)
 667           new_abs (mem->origin);
 668         else
 669           einfo (_("%F%S: undefined MEMORY region `%s'"
 670                    " referenced in expression\n"), tree->name.name);
 671       }
 672       break;
 673
 674     case CONSTANT:
 675       if (strcmp (tree->name.name, "MAXPAGESIZE") == 0)
 676         new_abs (bfd_emul_get_maxpagesize (default_target));
 677       else if (strcmp (tree->name.name, "COMMONPAGESIZE") == 0)
 678         new_abs (bfd_emul_get_commonpagesize (default_target));
 679       else
 680         einfo (_("%F%S: unknown constant `%s' referenced in expression\n"),
 681                tree->name.name);
 682       break;
 683
 684     default:
 685       FAIL ();
 686       break;
 687     }
 688 }
 689
 690 static void
 691 exp_fold_tree_1 (etree_type *tree)
 692 {
 693   if (tree == NULL)
 694     {
 695       memset (&expld.result, 0, sizeof (expld.result));
 696       return;
 697     }
 698
 699   switch (tree->type.node_class)
 700     {
 701     case etree_value:
 702       new_rel (tree->value.value, tree->value.str, expld.section);
 703       break;
 704
 705     case etree_rel:
 706       if (expld.phase != lang_first_phase_enum)
 707         {
 708           asection *output_section = tree->rel.section->output_section;
 709           new_rel (tree->rel.value + tree->rel.section->output_offset,
 710                    NULL, output_section);
 711         }
 712       else
 713         memset (&expld.result, 0, sizeof (expld.result));
 714       break;
 715
 716     case etree_assert:
 717       exp_fold_tree_1 (tree->assert_s.child);
 718       if (expld.phase == lang_final_phase_enum && !expld.result.value)
 719         einfo ("%X%P: %s\n", tree->assert_s.message);
 720       break;
 721
 722     case etree_unary:
 723       fold_unary (tree);
 724       break;
 725
 726     case etree_binary:
 727       fold_binary (tree);
 728       break;
 729
 730     case etree_trinary:
 731       fold_trinary (tree);
 732       break;
 733
 734     case etree_assign:
 735     case etree_provide:
 736     case etree_provided:
 737       if (tree->assign.dst[0] == '.' && tree->assign.dst[1] == 0)
 738         {
 739           /* Assignment to dot can only be done during allocation.  */
 740           if (tree->type.node_class != etree_assign)
 741             einfo (_("%F%S can not PROVIDE assignment to location counter\n"));
 742           if (expld.phase == lang_mark_phase_enum
 743               || expld.phase == lang_allocating_phase_enum
 744               || (expld.phase == lang_final_phase_enum
 745                   && expld.section == bfd_abs_section_ptr))
 746             {
 747               /* Notify the folder that this is an assignment to dot.  */
 748               expld.assigning_to_dot = TRUE;
 749               exp_fold_tree_1 (tree->assign.src);
 750               expld.assigning_to_dot = FALSE;
 751
 752               if (!expld.result.valid_p)
 753                 {
 754                   if (expld.phase != lang_mark_phase_enum)
 755                     einfo (_("%F%S invalid assignment to location counter\n"));
 756                 }
 757               else if (expld.dotp == NULL)
 758                 einfo (_("%F%S assignment to location counter"
 759                          " invalid outside of SECTION\n"));
 760               else
 761                 {
 762                   bfd_vma nextdot;
 763
 764                   nextdot = expld.result.value + expld.section->vma;
 765                   if (nextdot < expld.dot
 766                       && expld.section != bfd_abs_section_ptr)
 767                     einfo (_("%F%S cannot move location counter backwards"
 768                              " (from %V to %V)\n"), expld.dot, nextdot);
 769                   else
 770                     {
 771                       expld.dot = nextdot;
 772                       *expld.dotp = nextdot;
 773                     }
 774                 }
 775             }
 776           else
 777             memset (&expld.result, 0, sizeof (expld.result));
 778         }
 779       else
 780         {
 781           struct bfd_link_hash_entry *h = NULL;
 782
 783           if (tree->type.node_class == etree_provide)
 784             {
 785               h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 786                                         FALSE, FALSE, TRUE);
 787               if (h == NULL
 788                   || (h->type != bfd_link_hash_new
 789                       && h->type != bfd_link_hash_undefined
 790                       && h->type != bfd_link_hash_common))
 791                 {
 792                   /* Do nothing.  The symbol was never referenced, or was
 793                      defined by some object.  */
 794                   break;
 795                 }
 796             }
 797
 798           exp_fold_tree_1 (tree->assign.src);
 799           if (expld.result.valid_p)
 800             {
 801               if (h == NULL)
 802                 {
 803                   h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 804                                             TRUE, FALSE, TRUE);
 805                   if (h == NULL)
 806                     einfo (_("%P%F:%s: hash creation failed\n"),
 807                            tree->assign.dst);
 808                 }
 809
 810               /* FIXME: Should we worry if the symbol is already
 811                  defined?  */
 812               lang_update_definedness (tree->assign.dst, h);
 813               h->type = bfd_link_hash_defined;
 814               h->u.def.value = expld.result.value;
 815               h->u.def.section = expld.result.section;
 816               if (tree->type.node_class == etree_provide)
 817                 tree->type.node_class = etree_provided;
 818             }
 819         }
 820       break;
 821
 822     case etree_name:
 823       fold_name (tree);
 824       break;
 825
 826     default:
 827       FAIL ();
 828       memset (&expld.result, 0, sizeof (expld.result));
 829       break;
 830     }
 831 }
 832
 833 void
 834 exp_fold_tree (etree_type *tree, asection *current_section, bfd_vma *dotp)
 835 {
 836   expld.dot = *dotp;
 837   expld.dotp = dotp;
 838   expld.section = current_section;
 839   exp_fold_tree_1 (tree);
 840 }
 841
 842 static void
 843 exp_fold_tree_no_dot (etree_type *tree)
 844 {
 845   expld.dot = 0;
 846   expld.dotp = NULL;
 847   expld.section = bfd_abs_section_ptr;
 848   exp_fold_tree_1 (tree);
 849 }
 850
 851 etree_type *
 852 exp_binop (int code, etree_type *lhs, etree_type *rhs)
 853 {
 854   etree_type value, *new;
 855
 856   value.type.node_code = code;
 857   value.type.lineno = lhs->type.lineno;
 858   value.binary.lhs = lhs;
 859   value.binary.rhs = rhs;
 860   value.type.node_class = etree_binary;
 861   exp_fold_tree_no_dot (&value);
 862   if (expld.result.valid_p)
 863     return exp_intop (expld.result.value);
 864
 865   new = stat_alloc (sizeof (new->binary));
 866   memcpy (new, &value, sizeof (new->binary));
 867   return new;
 868 }
 869
 870 etree_type *
 871 exp_trinop (int code, etree_type *cond, etree_type *lhs, etree_type *rhs)
 872 {
 873   etree_type value, *new;
 874
 875   value.type.node_code = code;
 876   value.type.lineno = lhs->type.lineno;
 877   value.trinary.lhs = lhs;
 878   value.trinary.cond = cond;
 879   value.trinary.rhs = rhs;
 880   value.type.node_class = etree_trinary;
 881   exp_fold_tree_no_dot (&value);
 882   if (expld.result.valid_p)
 883     return exp_intop (expld.result.value);
 884
 885   new = stat_alloc (sizeof (new->trinary));
 886   memcpy (new, &value, sizeof (new->trinary));
 887   return new;
 888 }
 889
 890 etree_type *
 891 exp_unop (int code, etree_type *child)
 892 {
 893   etree_type value, *new;
 894
 895   value.unary.type.node_code = code;
 896   value.unary.type.lineno = child->type.lineno;
 897   value.unary.child = child;
 898   value.unary.type.node_class = etree_unary;
 899   exp_fold_tree_no_dot (&value);
 900   if (expld.result.valid_p)
 901     return exp_intop (expld.result.value);
 902
 903   new = stat_alloc (sizeof (new->unary));
 904   memcpy (new, &value, sizeof (new->unary));
 905   return new;
 906 }
 907
 908 etree_type *
 909 exp_nameop (int code, const char *name)
 910 {
 911   etree_type value, *new;
 912
 913   value.name.type.node_code = code;
 914   value.name.type.lineno = lineno;
 915   value.name.name = name;
 916   value.name.type.node_class = etree_name;
 917
 918   exp_fold_tree_no_dot (&value);
 919   if (expld.result.valid_p)
 920     return exp_intop (expld.result.value);
 921
 922   new = stat_alloc (sizeof (new->name));
 923   memcpy (new, &value, sizeof (new->name));
 924   return new;
 925
 926 }
 927
 928 etree_type *
 929 exp_assop (int code, const char *dst, etree_type *src)
 930 {
 931   etree_type *new;
 932
 933   new = stat_alloc (sizeof (new->assign));
 934   new->type.node_code = code;
 935   new->type.lineno = src->type.lineno;
 936   new->type.node_class = etree_assign;
 937   new->assign.src = src;
 938   new->assign.dst = dst;
 939   return new;
 940 }
 941
 942 /* Handle PROVIDE.  */
 943
 944 etree_type *
 945 exp_provide (const char *dst, etree_type *src, bfd_boolean hidden)
 946 {
 947   etree_type *n;
 948
 949   n = stat_alloc (sizeof (n->assign));
 950   n->assign.type.node_code = '=';
 951   n->assign.type.lineno = src->type.lineno;
 952   n->assign.type.node_class = etree_provide;
 953   n->assign.src = src;
 954   n->assign.dst = dst;
 955   n->assign.hidden = hidden;
 956   return n;
 957 }
 958
 959 /* Handle ASSERT.  */
 960
 961 etree_type *
 962 exp_assert (etree_type *exp, const char *message)
 963 {
 964   etree_type *n;
 965
 966   n = stat_alloc (sizeof (n->assert_s));
 967   n->assert_s.type.node_code = '!';
 968   n->assert_s.type.lineno = exp->type.lineno;
 969   n->assert_s.type.node_class = etree_assert;
 970   n->assert_s.child = exp;
 971   n->assert_s.message = message;
 972   return n;
 973 }
 974
 975 void
 976 exp_print_tree (etree_type *tree)
 977 {
 978   if (config.map_file == NULL)
 979     config.map_file = stderr;
 980
 981   if (tree == NULL)
 982     {
 983       minfo ("NULL TREE\n");
 984       return;
 985     }
 986
 987   switch (tree->type.node_class)
 988     {
 989     case etree_value:
 990       minfo ("0x%v", tree->value.value);
 991       return;
 992     case etree_rel:
 993       if (tree->rel.section->owner != NULL)
 994         minfo ("%B:", tree->rel.section->owner);
 995       minfo ("%s+0x%v", tree->rel.section->name, tree->rel.value);
 996       return;
 997     case etree_assign:
 998       fprintf (config.map_file, "%s", tree->assign.dst);
 999       exp_print_token (tree->type.node_code, TRUE);
1000       exp_print_tree (tree->assign.src);
1001       break;
1002     case etree_provide:
1003     case etree_provided:
1004       fprintf (config.map_file, "PROVIDE (%s, ", tree->assign.dst);
1005       exp_print_tree (tree->assign.src);
1006       fprintf (config.map_file, ")");
1007       break;
1008     case etree_binary:
1009       fprintf (config.map_file, "(");
1010       exp_print_tree (tree->binary.lhs);
1011       exp_print_token (tree->type.node_code, TRUE);
1012       exp_print_tree (tree->binary.rhs);
1013       fprintf (config.map_file, ")");
1014       break;
1015     case etree_trinary:
1016       exp_print_tree (tree->trinary.cond);
1017       fprintf (config.map_file, "?");
1018       exp_print_tree (tree->trinary.lhs);
1019       fprintf (config.map_file, ":");
1020       exp_print_tree (tree->trinary.rhs);
1021       break;
1022     case etree_unary:
1023       exp_print_token (tree->unary.type.node_code, FALSE);
1024       if (tree->unary.child)
1025         {
1026           fprintf (config.map_file, " (");
1027           exp_print_tree (tree->unary.child);
1028           fprintf (config.map_file, ")");
1029         }
1030       break;
1031
1032     case etree_assert:
1033       fprintf (config.map_file, "ASSERT (");
1034       exp_print_tree (tree->assert_s.child);
1035       fprintf (config.map_file, ", %s)", tree->assert_s.message);
1036       break;
1037
1038     case etree_name:
1039       if (tree->type.node_code == NAME)
1040         {
1041           fprintf (config.map_file, "%s", tree->name.name);
1042         }
1043       else
1044         {
1045           exp_print_token (tree->type.node_code, FALSE);
1046           if (tree->name.name)
1047             fprintf (config.map_file, " (%s)", tree->name.name);
1048         }
1049       break;
1050     default:
1051       FAIL ();
1052       break;
1053     }
1054 }
1055
1056 bfd_vma
1057 exp_get_vma (etree_type *tree, bfd_vma def, char *name)
1058 {
1059   if (tree != NULL)
1060     {
1061       exp_fold_tree_no_dot (tree);
1062       if (expld.result.valid_p)
1063         return expld.result.value;
1064       else if (name != NULL && expld.phase != lang_mark_phase_enum)
1065         einfo (_("%F%S: nonconstant expression for %s\n"), name);
1066     }
1067   return def;
1068 }
1069
1070 int
1071 exp_get_value_int (etree_type *tree, int def, char *name)
1072 {
1073   return exp_get_vma (tree, def, name);
1074 }
1075
1076 fill_type *
1077 exp_get_fill (etree_type *tree, fill_type *def, char *name)
1078 {
1079   fill_type *fill;
1080   size_t len;
1081   unsigned int val;
1082
1083   if (tree == NULL)
1084     return def;
1085
1086   exp_fold_tree_no_dot (tree);
1087   if (!expld.result.valid_p)
1088     {
1089       if (name != NULL && expld.phase != lang_mark_phase_enum)
1090         einfo (_("%F%S: nonconstant expression for %s\n"), name);
1091       return def;
1092     }
1093
1094   if (expld.result.str != NULL && (len = strlen (expld.result.str)) != 0)
1095     {
1096       unsigned char *dst;
1097       unsigned char *s;
1098       fill = xmalloc ((len + 1) / 2 + sizeof (*fill) - 1);
1099       fill->size = (len + 1) / 2;
1100       dst = fill->data;
1101       s = (unsigned char *) expld.result.str;
1102       val = 0;
1103       do
1104         {
1105           unsigned int digit;
1106
1107           digit = *s++ - '0';
1108           if (digit > 9)
1109             digit = (digit - 'A' + '0' + 10) & 0xf;
1110           val <<= 4;
1111           val += digit;
1112           --len;
1113           if ((len & 1) == 0)
1114             {
1115               *dst++ = val;
1116               val = 0;
1117             }
1118         }
1119       while (len != 0);
1120     }
1121   else
1122     {
1123       fill = xmalloc (4 + sizeof (*fill) - 1);
1124       val = expld.result.value;
1125       fill->data[0] = (val >> 24) & 0xff;
1126       fill->data[1] = (val >> 16) & 0xff;
1127       fill->data[2] = (val >>  8) & 0xff;
1128       fill->data[3] = (val >>  0) & 0xff;
1129       fill->size = 4;
1130     }
1131   return fill;
1132 }
1133
1134 bfd_vma
1135 exp_get_abs_int (etree_type *tree, int def, char *name)
1136 {
1137   if (tree != NULL)
1138     {
1139       exp_fold_tree_no_dot (tree);
1140
1141       if (expld.result.valid_p)
1142         {
1143           expld.result.value += expld.result.section->vma;
1144           return expld.result.value;
1145         }
1146       else if (name != NULL && expld.phase != lang_mark_phase_enum)
1147         {
1148           lineno = tree->type.lineno;
1149           einfo (_("%F%S: nonconstant expression for %s\n"), name);
1150         }
1151     }
1152   return def;
1153 }
1154
1155 static bfd_vma
1156 align_n (bfd_vma value, bfd_vma align)
1157 {
1158   if (align <= 1)
1159     return value;
1160
1161   value = (value + align - 1) / align;
1162   return value * align;
1163 }