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