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