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