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->bfd_section != NULL)
 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           else
 697             new_number (0);
 698         }
 699       break;
 700
 701     case LENGTH:
 702       {
 703         lang_memory_region_type *mem;
 704
 705         mem = lang_memory_region_lookup (tree->name.name, FALSE);
 706         if (mem != NULL)
 707           new_number (mem->length);
 708         else
 709           einfo (_("%F%S: undefined MEMORY region `%s'"
 710                    " referenced in expression\n"),
 711                  tree, tree->name.name);
 712       }
 713       break;
 714
 715     case ORIGIN:
 716       if (expld.phase != lang_first_phase_enum)
 717         {
 718           lang_memory_region_type *mem;
 719
 720           mem = lang_memory_region_lookup (tree->name.name, FALSE);
 721           if (mem != NULL)
 722             new_rel_from_abs (mem->origin);
 723           else
 724             einfo (_("%F%S: undefined MEMORY region `%s'"
 725                      " referenced in expression\n"),
 726                    tree, tree->name.name);
 727         }
 728       break;
 729
 730     case CONSTANT:
 731       if (strcmp (tree->name.name, "MAXPAGESIZE") == 0)
 732         new_number (config.maxpagesize);
 733       else if (strcmp (tree->name.name, "COMMONPAGESIZE") == 0)
 734         new_number (config.commonpagesize);
 735       else
 736         einfo (_("%F%S: unknown constant `%s' referenced in expression\n"),
 737                tree, tree->name.name);
 738       break;
 739
 740     default:
 741       FAIL ();
 742       break;
 743     }
 744 }
 745
 746 static void
 747 exp_fold_tree_1 (etree_type *tree)
 748 {
 749   if (tree == NULL)
 750     {
 751       memset (&expld.result, 0, sizeof (expld.result));
 752       return;
 753     }
 754
 755   switch (tree->type.node_class)
 756     {
 757     case etree_value:
 758       if (expld.section == bfd_abs_section_ptr
 759           && !config.sane_expr)
 760         new_abs (tree->value.value);
 761       else
 762         new_number (tree->value.value);
 763       expld.result.str = tree->value.str;
 764       break;
 765
 766     case etree_rel:
 767       if (expld.phase != lang_first_phase_enum)
 768         {
 769           asection *output_section = tree->rel.section->output_section;
 770           new_rel (tree->rel.value + tree->rel.section->output_offset,
 771                    output_section);
 772         }
 773       else
 774         memset (&expld.result, 0, sizeof (expld.result));
 775       break;
 776
 777     case etree_assert:
 778       exp_fold_tree_1 (tree->assert_s.child);
 779       if (expld.phase == lang_final_phase_enum && !expld.result.value)
 780         einfo ("%X%P: %s\n", tree->assert_s.message);
 781       break;
 782
 783     case etree_unary:
 784       fold_unary (tree);
 785       break;
 786
 787     case etree_binary:
 788       fold_binary (tree);
 789       break;
 790
 791     case etree_trinary:
 792       fold_trinary (tree);
 793       break;
 794
 795     case etree_assign:
 796     case etree_provide:
 797     case etree_provided:
 798       if (tree->assign.dst[0] == '.' && tree->assign.dst[1] == 0)
 799         {
 800           if (tree->type.node_class != etree_assign)
 801             einfo (_("%F%S can not PROVIDE assignment to"
 802                      " location counter\n"), tree);
 803           if (expld.phase != lang_first_phase_enum)
 804             {
 805               /* Notify the folder that this is an assignment to dot.  */
 806               expld.assigning_to_dot = TRUE;
 807               exp_fold_tree_1 (tree->assign.src);
 808               expld.assigning_to_dot = FALSE;
 809
 810               if (!expld.result.valid_p)
 811                 {
 812                   if (expld.phase != lang_mark_phase_enum)
 813                     einfo (_("%F%S invalid assignment to"
 814                              " location counter\n"), tree);
 815                 }
 816               else if (expld.dotp == NULL)
 817                 einfo (_("%F%S assignment to location counter"
 818                          " invalid outside of SECTIONS\n"), tree);
 819
 820               /* After allocation, assignment to dot should not be
 821                  done inside an output section since allocation adds a
 822                  padding statement that effectively duplicates the
 823                  assignment.  */
 824               else if (expld.phase <= lang_allocating_phase_enum
 825                        || expld.section == bfd_abs_section_ptr)
 826                 {
 827                   bfd_vma nextdot;
 828
 829                   nextdot = expld.result.value;
 830                   if (expld.result.section != NULL)
 831                     nextdot += expld.result.section->vma;
 832                   else
 833                     nextdot += expld.section->vma;
 834                   if (nextdot < expld.dot
 835                       && expld.section != bfd_abs_section_ptr)
 836                     einfo (_("%F%S cannot move location counter backwards"
 837                              " (from %V to %V)\n"),
 838                            tree, expld.dot, nextdot);
 839                   else
 840                     {
 841                       expld.dot = nextdot;
 842                       *expld.dotp = nextdot;
 843                     }
 844                 }
 845             }
 846           else
 847             memset (&expld.result, 0, sizeof (expld.result));
 848         }
 849       else
 850         {
 851           etree_type *name;
 852
 853           struct bfd_link_hash_entry *h = NULL;
 854
 855           if (tree->type.node_class == etree_provide)
 856             {
 857               h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 858                                         FALSE, FALSE, TRUE);
 859               if (h == NULL
 860                   || (h->type != bfd_link_hash_new
 861                       && h->type != bfd_link_hash_undefined
 862                       && h->type != bfd_link_hash_common))
 863                 {
 864                   /* Do nothing.  The symbol was never referenced, or was
 865                      defined by some object.  */
 866                   break;
 867                 }
 868             }
 869
 870           name = tree->assign.src;
 871           if (name->type.node_class == etree_trinary)
 872             {
 873               exp_fold_tree_1 (name->trinary.cond);
 874               if (expld.result.valid_p)
 875                 name = (expld.result.value
 876                         ? name->trinary.lhs : name->trinary.rhs);
 877             }
 878
 879           if (name->type.node_class == etree_name
 880               && name->type.node_code == NAME
 881               && strcmp (tree->assign.dst, name->name.name) == 0)
 882             /* Leave it alone.  Do not replace a symbol with its own
 883                output address, in case there is another section sizing
 884                pass.  Folding does not preserve input sections.  */
 885             break;
 886
 887           exp_fold_tree_1 (tree->assign.src);
 888           if (expld.result.valid_p
 889               || (expld.phase <= lang_mark_phase_enum
 890                   && tree->type.node_class == etree_assign
 891                   && tree->assign.hidden))
 892             {
 893               if (h == NULL)
 894                 {
 895                   h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 896                                             TRUE, FALSE, TRUE);
 897                   if (h == NULL)
 898                     einfo (_("%P%F:%s: hash creation failed\n"),
 899                            tree->assign.dst);
 900                 }
 901
 902               /* FIXME: Should we worry if the symbol is already
 903                  defined?  */
 904               lang_update_definedness (tree->assign.dst, h);
 905               h->type = bfd_link_hash_defined;
 906               h->u.def.value = expld.result.value;
 907               if (expld.result.section == NULL)
 908                 expld.result.section = expld.section;
 909               h->u.def.section = expld.result.section;
 910               if (tree->type.node_class == etree_provide)
 911                 tree->type.node_class = etree_provided;
 912
 913               /* Copy the symbol type if this is a simple assignment of
 914                  one symbol to another.  This could be more general
 915                  (e.g. a ?: operator with NAMEs in each branch).  */
 916               if (tree->assign.src->type.node_class == etree_name)
 917                 {
 918                   struct bfd_link_hash_entry *hsrc;
 919
 920                   hsrc = bfd_link_hash_lookup (link_info.hash,
 921                                                tree->assign.src->name.name,
 922                                                FALSE, FALSE, TRUE);
 923                   if (hsrc)
 924                     bfd_copy_link_hash_symbol_type (link_info.output_bfd, h,
 925                                                     hsrc);
 926                 }
 927             }
 928           else if (expld.phase == lang_final_phase_enum)
 929             {
 930               h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
 931                                         FALSE, FALSE, TRUE);
 932               if (h != NULL
 933                   && h->type == bfd_link_hash_new)
 934                 h->type = bfd_link_hash_undefined;
 935             }
 936         }
 937       break;
 938
 939     case etree_name:
 940       fold_name (tree);
 941       break;
 942
 943     default:
 944       FAIL ();
 945       memset (&expld.result, 0, sizeof (expld.result));
 946       break;
 947     }
 948 }
 949
 950 void
 951 exp_fold_tree (etree_type *tree, asection *current_section, bfd_vma *dotp)
 952 {
 953   expld.dot = *dotp;
 954   expld.dotp = dotp;
 955   expld.section = current_section;
 956   exp_fold_tree_1 (tree);
 957 }
 958
 959 void
 960 exp_fold_tree_no_dot (etree_type *tree)
 961 {
 962   expld.dot = 0;
 963   expld.dotp = NULL;
 964   expld.section = bfd_abs_section_ptr;
 965   exp_fold_tree_1 (tree);
 966 }
 967
 968 etree_type *
 969 exp_binop (int code, etree_type *lhs, etree_type *rhs)
 970 {
 971   etree_type value, *new_e;
 972
 973   value.type.node_code = code;
 974   value.type.filename = lhs->type.filename;
 975   value.type.lineno = lhs->type.lineno;
 976   value.binary.lhs = lhs;
 977   value.binary.rhs = rhs;
 978   value.type.node_class = etree_binary;
 979   exp_fold_tree_no_dot (&value);
 980   if (expld.result.valid_p)
 981     return exp_intop (expld.result.value);
 982
 983   new_e = (etree_type *) stat_alloc (sizeof (new_e->binary));
 984   memcpy (new_e, &value, sizeof (new_e->binary));
 985   return new_e;
 986 }
 987
 988 etree_type *
 989 exp_trinop (int code, etree_type *cond, etree_type *lhs, etree_type *rhs)
 990 {
 991   etree_type value, *new_e;
 992
 993   value.type.node_code = code;
 994   value.type.filename = cond->type.filename;
 995   value.type.lineno = cond->type.lineno;
 996   value.trinary.lhs = lhs;
 997   value.trinary.cond = cond;
 998   value.trinary.rhs = rhs;
 999   value.type.node_class = etree_trinary;
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->trinary));
1005   memcpy (new_e, &value, sizeof (new_e->trinary));
1006   return new_e;
1007 }
1008
1009 etree_type *
1010 exp_unop (int code, etree_type *child)
1011 {
1012   etree_type value, *new_e;
1013
1014   value.unary.type.node_code = code;
1015   value.unary.type.filename = child->type.filename;
1016   value.unary.type.lineno = child->type.lineno;
1017   value.unary.child = child;
1018   value.unary.type.node_class = etree_unary;
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->unary));
1024   memcpy (new_e, &value, sizeof (new_e->unary));
1025   return new_e;
1026 }
1027
1028 etree_type *
1029 exp_nameop (int code, const char *name)
1030 {
1031   etree_type value, *new_e;
1032
1033   value.name.type.node_code = code;
1034   value.name.type.filename = ldlex_filename ();
1035   value.name.type.lineno = lineno;
1036   value.name.name = name;
1037   value.name.type.node_class = etree_name;
1038
1039   exp_fold_tree_no_dot (&value);
1040   if (expld.result.valid_p)
1041     return exp_intop (expld.result.value);
1042
1043   new_e = (etree_type *) stat_alloc (sizeof (new_e->name));
1044   memcpy (new_e, &value, sizeof (new_e->name));
1045   return new_e;
1046
1047 }
1048
1049 static etree_type *
1050 exp_assop (const char *dst,
1051            etree_type *src,
1052            enum node_tree_enum class,
1053            bfd_boolean hidden)
1054 {
1055   etree_type *n;
1056
1057   n = (etree_type *) stat_alloc (sizeof (n->assign));
1058   n->assign.type.node_code = '=';
1059   n->assign.type.filename = src->type.filename;
1060   n->assign.type.lineno = src->type.lineno;
1061   n->assign.type.node_class = class;
1062   n->assign.src = src;
1063   n->assign.dst = dst;
1064   n->assign.hidden = hidden;
1065   return n;
1066 }
1067
1068 etree_type *
1069 exp_assign (const char *dst, etree_type *src)
1070 {
1071   return exp_assop (dst, src, etree_assign, FALSE);
1072 }
1073
1074 etree_type *
1075 exp_defsym (const char *dst, etree_type *src)
1076 {
1077   return exp_assop (dst, src, etree_assign, TRUE);
1078 }
1079
1080 /* Handle PROVIDE.  */
1081
1082 etree_type *
1083 exp_provide (const char *dst, etree_type *src, bfd_boolean hidden)
1084 {
1085   return exp_assop (dst, src, etree_provide, hidden);
1086 }
1087
1088 /* Handle ASSERT.  */
1089
1090 etree_type *
1091 exp_assert (etree_type *exp, const char *message)
1092 {
1093   etree_type *n;
1094
1095   n = (etree_type *) stat_alloc (sizeof (n->assert_s));
1096   n->assert_s.type.node_code = '!';
1097   n->assert_s.type.filename = exp->type.filename;
1098   n->assert_s.type.lineno = exp->type.lineno;
1099   n->assert_s.type.node_class = etree_assert;
1100   n->assert_s.child = exp;
1101   n->assert_s.message = message;
1102   return n;
1103 }
1104
1105 void
1106 exp_print_tree (etree_type *tree)
1107 {
1108   bfd_boolean function_like;
1109
1110   if (config.map_file == NULL)
1111     config.map_file = stderr;
1112
1113   if (tree == NULL)
1114     {
1115       minfo ("NULL TREE\n");
1116       return;
1117     }
1118
1119   switch (tree->type.node_class)
1120     {
1121     case etree_value:
1122       minfo ("0x%v", tree->value.value);
1123       return;
1124     case etree_rel:
1125       if (tree->rel.section->owner != NULL)
1126         minfo ("%B:", tree->rel.section->owner);
1127       minfo ("%s+0x%v", tree->rel.section->name, tree->rel.value);
1128       return;
1129     case etree_assign:
1130       fputs (tree->assign.dst, config.map_file);
1131       exp_print_token (tree->type.node_code, TRUE);
1132       exp_print_tree (tree->assign.src);
1133       break;
1134     case etree_provide:
1135     case etree_provided:
1136       fprintf (config.map_file, "PROVIDE (%s, ", tree->assign.dst);
1137       exp_print_tree (tree->assign.src);
1138       fputc (')', config.map_file);
1139       break;
1140     case etree_binary:
1141       function_like = FALSE;
1142       switch (tree->type.node_code)
1143         {
1144         case MAX_K:
1145         case MIN_K:
1146         case ALIGN_K:
1147         case DATA_SEGMENT_ALIGN:
1148         case DATA_SEGMENT_RELRO_END:
1149           function_like = TRUE;
1150           break;
1151         case SEGMENT_START:
1152           /* Special handling because arguments are in reverse order and
1153              the segment name is quoted.  */
1154           exp_print_token (tree->type.node_code, FALSE);
1155           fputs (" (\"", config.map_file);
1156           exp_print_tree (tree->binary.rhs);
1157           fputs ("\", ", config.map_file);
1158           exp_print_tree (tree->binary.lhs);
1159           fputc (')', config.map_file);
1160           return;
1161         }
1162       if (function_like)
1163         {
1164           exp_print_token (tree->type.node_code, FALSE);
1165           fputc (' ', config.map_file);
1166         }
1167       fputc ('(', config.map_file);
1168       exp_print_tree (tree->binary.lhs);
1169       if (function_like)
1170         fprintf (config.map_file, ", ");
1171       else
1172         exp_print_token (tree->type.node_code, TRUE);
1173       exp_print_tree (tree->binary.rhs);
1174       fputc (')', config.map_file);
1175       break;
1176     case etree_trinary:
1177       exp_print_tree (tree->trinary.cond);
1178       fputc ('?', config.map_file);
1179       exp_print_tree (tree->trinary.lhs);
1180       fputc (':', config.map_file);
1181       exp_print_tree (tree->trinary.rhs);
1182       break;
1183     case etree_unary:
1184       exp_print_token (tree->unary.type.node_code, FALSE);
1185       if (tree->unary.child)
1186         {
1187           fprintf (config.map_file, " (");
1188           exp_print_tree (tree->unary.child);
1189           fputc (')', config.map_file);
1190         }
1191       break;
1192
1193     case etree_assert:
1194       fprintf (config.map_file, "ASSERT (");
1195       exp_print_tree (tree->assert_s.child);
1196       fprintf (config.map_file, ", %s)", tree->assert_s.message);
1197       break;
1198
1199     case etree_name:
1200       if (tree->type.node_code == NAME)
1201         fputs (tree->name.name, config.map_file);
1202       else
1203         {
1204           exp_print_token (tree->type.node_code, FALSE);
1205           if (tree->name.name)
1206             fprintf (config.map_file, " (%s)", tree->name.name);
1207         }
1208       break;
1209     default:
1210       FAIL ();
1211       break;
1212     }
1213 }
1214
1215 bfd_vma
1216 exp_get_vma (etree_type *tree, bfd_vma def, char *name)
1217 {
1218   if (tree != NULL)
1219     {
1220       exp_fold_tree_no_dot (tree);
1221       if (expld.result.valid_p)
1222         return expld.result.value;
1223       else if (name != NULL && expld.phase != lang_mark_phase_enum)
1224         einfo (_("%F%S: nonconstant expression for %s\n"),
1225                tree, name);
1226     }
1227   return def;
1228 }
1229
1230 int
1231 exp_get_value_int (etree_type *tree, int def, char *name)
1232 {
1233   return exp_get_vma (tree, def, name);
1234 }
1235
1236 fill_type *
1237 exp_get_fill (etree_type *tree, fill_type *def, char *name)
1238 {
1239   fill_type *fill;
1240   size_t len;
1241   unsigned int val;
1242
1243   if (tree == NULL)
1244     return def;
1245
1246   exp_fold_tree_no_dot (tree);
1247   if (!expld.result.valid_p)
1248     {
1249       if (name != NULL && expld.phase != lang_mark_phase_enum)
1250         einfo (_("%F%S: nonconstant expression for %s\n"),
1251                tree, name);
1252       return def;
1253     }
1254
1255   if (expld.result.str != NULL && (len = strlen (expld.result.str)) != 0)
1256     {
1257       unsigned char *dst;
1258       unsigned char *s;
1259       fill = (fill_type *) xmalloc ((len + 1) / 2 + sizeof (*fill) - 1);
1260       fill->size = (len + 1) / 2;
1261       dst = fill->data;
1262       s = (unsigned char *) expld.result.str;
1263       val = 0;
1264       do
1265         {
1266           unsigned int digit;
1267
1268           digit = *s++ - '0';
1269           if (digit > 9)
1270             digit = (digit - 'A' + '0' + 10) & 0xf;
1271           val <<= 4;
1272           val += digit;
1273           --len;
1274           if ((len & 1) == 0)
1275             {
1276               *dst++ = val;
1277               val = 0;
1278             }
1279         }
1280       while (len != 0);
1281     }
1282   else
1283     {
1284       fill = (fill_type *) xmalloc (4 + sizeof (*fill) - 1);
1285       val = expld.result.value;
1286       fill->data[0] = (val >> 24) & 0xff;
1287       fill->data[1] = (val >> 16) & 0xff;
1288       fill->data[2] = (val >>  8) & 0xff;
1289       fill->data[3] = (val >>  0) & 0xff;
1290       fill->size = 4;
1291     }
1292   return fill;
1293 }
1294
1295 bfd_vma
1296 exp_get_abs_int (etree_type *tree, int def, char *name)
1297 {
1298   if (tree != NULL)
1299     {
1300       exp_fold_tree_no_dot (tree);
1301
1302       if (expld.result.valid_p)
1303         {
1304           if (expld.result.section != NULL)
1305             expld.result.value += expld.result.section->vma;
1306           return expld.result.value;
1307         }
1308       else if (name != NULL && expld.phase != lang_mark_phase_enum)
1309         {
1310           einfo (_("%F%S: nonconstant expression for %s\n"),
1311                  tree, name);
1312         }
1313     }
1314   return def;
1315 }
1316
1317 static bfd_vma
1318 align_n (bfd_vma value, bfd_vma align)
1319 {
1320   if (align <= 1)
1321     return value;
1322
1323   value = (value + align - 1) / align;
1324   return value * align;
1325 }