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