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           if (tree->type.node_class != etree_assign)
 787             einfo (_("%F%S can not PROVIDE assignment to location counter\n"));
 788           /* After allocation, assignment to dot should not be done inside
 789              an output section since allocation adds a padding statement
 790              that effectively duplicates the assignment.  */
 791           if (expld.phase == lang_mark_phase_enum
 792               || expld.phase == lang_allocating_phase_enum
 793               || ((expld.phase == lang_assigning_phase_enum
 794                    || expld.phase == lang_final_phase_enum)
 795                   && expld.section == bfd_abs_section_ptr))
 796             {
 797               /* Notify the folder that this is an assignment to dot.  */
 798               expld.assigning_to_dot = TRUE;
 799               exp_fold_tree_1 (tree->assign.src);
 800               expld.assigning_to_dot = FALSE;
 801
 802               if (!expld.result.valid_p)
 803                 {
 804                   if (expld.phase != lang_mark_phase_enum)
 805                     einfo (_("%F%S invalid assignment to location counter\n"));
 806                 }
 807               else if (expld.dotp == NULL)
 808                 einfo (_("%F%S assignment to location counter"
 809                          " invalid outside of SECTION\n"));
 810               else
 811                 {
 812                   bfd_vma nextdot;
 813
 814                   nextdot = expld.result.value;
 815                   if (expld.result.section != NULL)
 816                     nextdot += expld.result.section->vma;
 817                   else
 818                     nextdot += expld.section->vma;
 819                   if (nextdot < expld.dot
 820                       && expld.section != bfd_abs_section_ptr)
 821                     einfo (_("%F%S cannot move location counter backwards"
 822                              " (from %V to %V)\n"), expld.dot, nextdot);
 823                   else
 824                     {
 825                       expld.dot = nextdot;
 826                       *expld.dotp = nextdot;
 827                     }
 828                 }
 829             }
 830           else
 831             memset (&expld.result, 0, sizeof (expld.result));
 832         }
 833       else
 834         {
 835           struct bfd_link_hash_entry *h = NULL;
 836
 837           if (tree->type.node_class == etree_provide)
 838             {
 839               h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 840                                         FALSE, FALSE, TRUE);
 841               if (h == NULL
 842                   || (h->type != bfd_link_hash_new
 843                       && h->type != bfd_link_hash_undefined
 844                       && h->type != bfd_link_hash_common))
 845                 {
 846                   /* Do nothing.  The symbol was never referenced, or was
 847                      defined by some object.  */
 848                   break;
 849                 }
 850             }
 851
 852           exp_fold_tree_1 (tree->assign.src);
 853           if (expld.result.valid_p
 854               || (expld.phase == lang_first_phase_enum
 855                   && tree->type.node_class == etree_assign
 856                   && tree->assign.hidden))
 857             {
 858               if (h == NULL)
 859                 {
 860                   h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 861                                             TRUE, FALSE, TRUE);
 862                   if (h == NULL)
 863                     einfo (_("%P%F:%s: hash creation failed\n"),
 864                            tree->assign.dst);
 865                 }
 866
 867               /* FIXME: Should we worry if the symbol is already
 868                  defined?  */
 869               lang_update_definedness (tree->assign.dst, h);
 870               h->type = bfd_link_hash_defined;
 871               h->u.def.value = expld.result.value;
 872               if (expld.result.section == NULL)
 873                 expld.result.section = expld.section;
 874               h->u.def.section = expld.result.section;
 875               if (tree->type.node_class == etree_provide)
 876                 tree->type.node_class = etree_provided;
 877
 878               /* Copy the symbol type if this is a simple assignment of
 879                  one symbol to annother.  */
 880               if (tree->assign.src->type.node_class == etree_name)
 881                 {
 882                   struct bfd_link_hash_entry *hsrc;
 883
 884                   hsrc = bfd_link_hash_lookup (link_info.hash,
 885                                                tree->assign.src->name.name,
 886                                                FALSE, FALSE, TRUE);
 887                   if (hsrc)
 888                     bfd_copy_link_hash_symbol_type (link_info.output_bfd, h,
 889                                                     hsrc);
 890                 }
 891             }
 892           else if (expld.phase == lang_final_phase_enum)
 893             {
 894               h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 895                                         FALSE, FALSE, TRUE);
 896               if (h != NULL
 897                   && h->type == bfd_link_hash_new)
 898                 h->type = bfd_link_hash_undefined;
 899             }
 900         }
 901       break;
 902
 903     case etree_name:
 904       fold_name (tree);
 905       break;
 906
 907     default:
 908       FAIL ();
 909       memset (&expld.result, 0, sizeof (expld.result));
 910       break;
 911     }
 912 }
 913
 914 void
 915 exp_fold_tree (etree_type *tree, asection *current_section, bfd_vma *dotp)
 916 {
 917   expld.dot = *dotp;
 918   expld.dotp = dotp;
 919   expld.section = current_section;
 920   exp_fold_tree_1 (tree);
 921 }
 922
 923 void
 924 exp_fold_tree_no_dot (etree_type *tree)
 925 {
 926   expld.dot = 0;
 927   expld.dotp = NULL;
 928   expld.section = bfd_abs_section_ptr;
 929   exp_fold_tree_1 (tree);
 930 }
 931
 932 etree_type *
 933 exp_binop (int code, etree_type *lhs, etree_type *rhs)
 934 {
 935   etree_type value, *new_e;
 936
 937   value.type.node_code = code;
 938   value.type.lineno = lhs->type.lineno;
 939   value.binary.lhs = lhs;
 940   value.binary.rhs = rhs;
 941   value.type.node_class = etree_binary;
 942   exp_fold_tree_no_dot (&value);
 943   if (expld.result.valid_p)
 944     return exp_intop (expld.result.value);
 945
 946   new_e = (etree_type *) stat_alloc (sizeof (new_e->binary));
 947   memcpy (new_e, &value, sizeof (new_e->binary));
 948   return new_e;
 949 }
 950
 951 etree_type *
 952 exp_trinop (int code, etree_type *cond, etree_type *lhs, etree_type *rhs)
 953 {
 954   etree_type value, *new_e;
 955
 956   value.type.node_code = code;
 957   value.type.lineno = lhs->type.lineno;
 958   value.trinary.lhs = lhs;
 959   value.trinary.cond = cond;
 960   value.trinary.rhs = rhs;
 961   value.type.node_class = etree_trinary;
 962   exp_fold_tree_no_dot (&value);
 963   if (expld.result.valid_p)
 964     return exp_intop (expld.result.value);
 965
 966   new_e = (etree_type *) stat_alloc (sizeof (new_e->trinary));
 967   memcpy (new_e, &value, sizeof (new_e->trinary));
 968   return new_e;
 969 }
 970
 971 etree_type *
 972 exp_unop (int code, etree_type *child)
 973 {
 974   etree_type value, *new_e;
 975
 976   value.unary.type.node_code = code;
 977   value.unary.type.lineno = child->type.lineno;
 978   value.unary.child = child;
 979   value.unary.type.node_class = etree_unary;
 980   exp_fold_tree_no_dot (&value);
 981   if (expld.result.valid_p)
 982     return exp_intop (expld.result.value);
 983
 984   new_e = (etree_type *) stat_alloc (sizeof (new_e->unary));
 985   memcpy (new_e, &value, sizeof (new_e->unary));
 986   return new_e;
 987 }
 988
 989 etree_type *
 990 exp_nameop (int code, const char *name)
 991 {
 992   etree_type value, *new_e;
 993
 994   value.name.type.node_code = code;
 995   value.name.type.lineno = lineno;
 996   value.name.name = name;
 997   value.name.type.node_class = etree_name;
 998
 999   exp_fold_tree_no_dot (&value);
1000   if (expld.result.valid_p)
1001     return exp_intop (expld.result.value);
1002
1003   new_e = (etree_type *) stat_alloc (sizeof (new_e->name));
1004   memcpy (new_e, &value, sizeof (new_e->name));
1005   return new_e;
1006
1007 }
1008
1009 static etree_type *
1010 exp_assop (const char *dst,
1011            etree_type *src,
1012            enum node_tree_enum class,
1013            bfd_boolean hidden)
1014 {
1015   etree_type *n;
1016
1017   n = (etree_type *) stat_alloc (sizeof (n->assign));
1018   n->assign.type.node_code = '=';
1019   n->assign.type.lineno = src->type.lineno;
1020   n->assign.type.node_class = class;
1021   n->assign.src = src;
1022   n->assign.dst = dst;
1023   n->assign.hidden = hidden;
1024   return n;
1025 }
1026
1027 etree_type *
1028 exp_assign (const char *dst, etree_type *src)
1029 {
1030   return exp_assop (dst, src, etree_assign, FALSE);
1031 }
1032
1033 etree_type *
1034 exp_defsym (const char *dst, etree_type *src)
1035 {
1036   return exp_assop (dst, src, etree_assign, TRUE);
1037 }
1038
1039 /* Handle PROVIDE.  */
1040
1041 etree_type *
1042 exp_provide (const char *dst, etree_type *src, bfd_boolean hidden)
1043 {
1044   return exp_assop (dst, src, etree_provide, hidden);
1045 }
1046
1047 /* Handle ASSERT.  */
1048
1049 etree_type *
1050 exp_assert (etree_type *exp, const char *message)
1051 {
1052   etree_type *n;
1053
1054   n = (etree_type *) stat_alloc (sizeof (n->assert_s));
1055   n->assert_s.type.node_code = '!';
1056   n->assert_s.type.lineno = exp->type.lineno;
1057   n->assert_s.type.node_class = etree_assert;
1058   n->assert_s.child = exp;
1059   n->assert_s.message = message;
1060   return n;
1061 }
1062
1063 void
1064 exp_print_tree (etree_type *tree)
1065 {
1066   bfd_boolean function_like;
1067
1068   if (config.map_file == NULL)
1069     config.map_file = stderr;
1070
1071   if (tree == NULL)
1072     {
1073       minfo ("NULL TREE\n");
1074       return;
1075     }
1076
1077   switch (tree->type.node_class)
1078     {
1079     case etree_value:
1080       minfo ("0x%v", tree->value.value);
1081       return;
1082     case etree_rel:
1083       if (tree->rel.section->owner != NULL)
1084         minfo ("%B:", tree->rel.section->owner);
1085       minfo ("%s+0x%v", tree->rel.section->name, tree->rel.value);
1086       return;
1087     case etree_assign:
1088       fputs (tree->assign.dst, config.map_file);
1089       exp_print_token (tree->type.node_code, TRUE);
1090       exp_print_tree (tree->assign.src);
1091       break;
1092     case etree_provide:
1093     case etree_provided:
1094       fprintf (config.map_file, "PROVIDE (%s, ", tree->assign.dst);
1095       exp_print_tree (tree->assign.src);
1096       fputc (')', config.map_file);
1097       break;
1098     case etree_binary:
1099       function_like = FALSE;
1100       switch (tree->type.node_code)
1101         {
1102         case MAX_K:
1103         case MIN_K:
1104         case ALIGN_K:
1105         case DATA_SEGMENT_ALIGN:
1106         case DATA_SEGMENT_RELRO_END:
1107           function_like = TRUE;
1108         }
1109       if (function_like)
1110         {
1111           exp_print_token (tree->type.node_code, FALSE);
1112           fputc (' ', config.map_file);
1113         }
1114       fputc ('(', config.map_file);
1115       exp_print_tree (tree->binary.lhs);
1116       if (function_like)
1117         fprintf (config.map_file, ", ");
1118       else
1119         exp_print_token (tree->type.node_code, TRUE);
1120       exp_print_tree (tree->binary.rhs);
1121       fputc (')', config.map_file);
1122       break;
1123     case etree_trinary:
1124       exp_print_tree (tree->trinary.cond);
1125       fputc ('?', config.map_file);
1126       exp_print_tree (tree->trinary.lhs);
1127       fputc (':', config.map_file);
1128       exp_print_tree (tree->trinary.rhs);
1129       break;
1130     case etree_unary:
1131       exp_print_token (tree->unary.type.node_code, FALSE);
1132       if (tree->unary.child)
1133         {
1134           fprintf (config.map_file, " (");
1135           exp_print_tree (tree->unary.child);
1136           fputc (')', config.map_file);
1137         }
1138       break;
1139
1140     case etree_assert:
1141       fprintf (config.map_file, "ASSERT (");
1142       exp_print_tree (tree->assert_s.child);
1143       fprintf (config.map_file, ", %s)", tree->assert_s.message);
1144       break;
1145
1146     case etree_name:
1147       if (tree->type.node_code == NAME)
1148         fputs (tree->name.name, config.map_file);
1149       else
1150         {
1151           exp_print_token (tree->type.node_code, FALSE);
1152           if (tree->name.name)
1153             fprintf (config.map_file, " (%s)", tree->name.name);
1154         }
1155       break;
1156     default:
1157       FAIL ();
1158       break;
1159     }
1160 }
1161
1162 bfd_vma
1163 exp_get_vma (etree_type *tree, bfd_vma def, char *name)
1164 {
1165   if (tree != NULL)
1166     {
1167       exp_fold_tree_no_dot (tree);
1168       if (expld.result.valid_p)
1169         return expld.result.value;
1170       else if (name != NULL && expld.phase != lang_mark_phase_enum)
1171         einfo (_("%F%S: nonconstant expression for %s\n"), name);
1172     }
1173   return def;
1174 }
1175
1176 int
1177 exp_get_value_int (etree_type *tree, int def, char *name)
1178 {
1179   return exp_get_vma (tree, def, name);
1180 }
1181
1182 fill_type *
1183 exp_get_fill (etree_type *tree, fill_type *def, char *name)
1184 {
1185   fill_type *fill;
1186   size_t len;
1187   unsigned int val;
1188
1189   if (tree == NULL)
1190     return def;
1191
1192   exp_fold_tree_no_dot (tree);
1193   if (!expld.result.valid_p)
1194     {
1195       if (name != NULL && expld.phase != lang_mark_phase_enum)
1196         einfo (_("%F%S: nonconstant expression for %s\n"), name);
1197       return def;
1198     }
1199
1200   if (expld.result.str != NULL && (len = strlen (expld.result.str)) != 0)
1201     {
1202       unsigned char *dst;
1203       unsigned char *s;
1204       fill = (fill_type *) xmalloc ((len + 1) / 2 + sizeof (*fill) - 1);
1205       fill->size = (len + 1) / 2;
1206       dst = fill->data;
1207       s = (unsigned char *) expld.result.str;
1208       val = 0;
1209       do
1210         {
1211           unsigned int digit;
1212
1213           digit = *s++ - '0';
1214           if (digit > 9)
1215             digit = (digit - 'A' + '0' + 10) & 0xf;
1216           val <<= 4;
1217           val += digit;
1218           --len;
1219           if ((len & 1) == 0)
1220             {
1221               *dst++ = val;
1222               val = 0;
1223             }
1224         }
1225       while (len != 0);
1226     }
1227   else
1228     {
1229       fill = (fill_type *) xmalloc (4 + sizeof (*fill) - 1);
1230       val = expld.result.value;
1231       fill->data[0] = (val >> 24) & 0xff;
1232       fill->data[1] = (val >> 16) & 0xff;
1233       fill->data[2] = (val >>  8) & 0xff;
1234       fill->data[3] = (val >>  0) & 0xff;
1235       fill->size = 4;
1236     }
1237   return fill;
1238 }
1239
1240 bfd_vma
1241 exp_get_abs_int (etree_type *tree, int def, char *name)
1242 {
1243   if (tree != NULL)
1244     {
1245       exp_fold_tree_no_dot (tree);
1246
1247       if (expld.result.valid_p)
1248         {
1249           if (expld.result.section != NULL)
1250             expld.result.value += expld.result.section->vma;
1251           return expld.result.value;
1252         }
1253       else if (name != NULL && expld.phase != lang_mark_phase_enum)
1254         {
1255           lineno = tree->type.lineno;
1256           einfo (_("%F%S: nonconstant expression for %s\n"), name);
1257         }
1258     }
1259   return def;
1260 }
1261
1262 static bfd_vma
1263 align_n (bfd_vma value, bfd_vma align)
1264 {
1265   if (align <= 1)
1266     return value;
1267
1268   value = (value + align - 1) / align;
1269   return value * align;
1270 }