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