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