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