ld/ldexp.c

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