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