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