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