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