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: 
   50: segment_type *segments;
   51: 
   52: struct ldexp_control expld;
   53: 
   54: /* Print the string representation of the given token.  Surround it
   55:    with spaces if INFIX_P is TRUE.  */
   56: 
   57: static void
   58: exp_print_token (token_code_type code, int infix_p)
   59: {
   60:   static const struct
   61:   {
   62:     token_code_type code;
   63:     char * name;
   64:   }
   65:   table[] =
   66:   {
   67:     { INT, "int" },
   68:     { NAME, "NAME" },
   69:     { PLUSEQ, "+=" },
   70:     { MINUSEQ, "-=" },
   71:     { MULTEQ, "*=" },
   72:     { DIVEQ, "/=" },
   73:     { LSHIFTEQ, "<<=" },
   74:     { RSHIFTEQ, ">>=" },
   75:     { ANDEQ, "&=" },
   76:     { OREQ, "|=" },
   77:     { OROR, "||" },
   78:     { ANDAND, "&&" },
   79:     { EQ, "==" },
   80:     { NE, "!=" },
   81:     { LE, "<=" },
   82:     { GE, ">=" },
   83:     { LSHIFT, "<<" },
   84:     { RSHIFT, ">>" },
   85:     { ALIGN_K, "ALIGN" },
   86:     { BLOCK, "BLOCK" },
   87:     { QUAD, "QUAD" },
   88:     { SQUAD, "SQUAD" },
   89:     { LONG, "LONG" },
   90:     { SHORT, "SHORT" },
   91:     { BYTE, "BYTE" },
   92:     { SECTIONS, "SECTIONS" },
   93:     { SIZEOF_HEADERS, "SIZEOF_HEADERS" },
   94:     { MEMORY, "MEMORY" },
   95:     { DEFINED, "DEFINED" },
   96:     { TARGET_K, "TARGET" },
   97:     { SEARCH_DIR, "SEARCH_DIR" },
   98:     { MAP, "MAP" },
   99:     { ENTRY, "ENTRY" },
  100:     { NEXT, "NEXT" },
  101:     { ALIGNOF, "ALIGNOF" },
  102:     { SIZEOF, "SIZEOF" },
  103:     { ADDR, "ADDR" },
  104:     { LOADADDR, "LOADADDR" },
  105:     { CONSTANT, "CONSTANT" },
  106:     { MAX_K, "MAX_K" },
  107:     { REL, "relocatable" },
  108:     { DATA_SEGMENT_ALIGN, "DATA_SEGMENT_ALIGN" },
  109:     { DATA_SEGMENT_RELRO_END, "DATA_SEGMENT_RELRO_END" },
  110:     { DATA_SEGMENT_END, "DATA_SEGMENT_END" },
  111:     { ORIGIN, "ORIGIN" },
  112:     { LENGTH, "LENGTH" },
  113:     { SEGMENT_START, "SEGMENT_START" }
  114:   };
  115:   unsigned int idx;
  116: 
  117:   for (idx = 0; idx < ARRAY_SIZE (table); idx++)
  118:     if (table[idx].code == code)
  119:       break;
  120: 
  121:   if (infix_p)
  122:     fputc (' ', config.map_file);
  123: 
  124:   if (idx < ARRAY_SIZE (table))
  125:     fputs (table[idx].name, config.map_file);
  126:   else if (code < 127)
  127:     fputc (code, config.map_file);
  128:   else
  129:     fprintf (config.map_file, "<code %d>", code);
  130: 
  131:   if (infix_p)
  132:     fputc (' ', config.map_file);
  133: }
  134: 
  135: static void
  136: make_abs (void)
  137: {
  138:   expld.result.value += expld.result.section->vma;
  139:   expld.result.section = bfd_abs_section_ptr;
  140: }
  141: 
  142: static void
  143: new_abs (bfd_vma value)
  144: {
  145:   expld.result.valid_p = TRUE;
  146:   expld.result.section = bfd_abs_section_ptr;
  147:   expld.result.value = value;
  148:   expld.result.str = NULL;
  149: }
  150: 
  151: etree_type *
  152: exp_intop (bfd_vma value)
  153: {
  154:   etree_type *new = stat_alloc (sizeof (new->value));
  155:   new->type.node_code = INT;
  156:   new->type.lineno = lineno;
  157:   new->value.value = value;
  158:   new->value.str = NULL;
  159:   new->type.node_class = etree_value;
  160:   return new;
  161: }
  162: 
  163: etree_type *
  164: exp_bigintop (bfd_vma value, char *str)
  165: {
  166:   etree_type *new = stat_alloc (sizeof (new->value));
  167:   new->type.node_code = INT;
  168:   new->type.lineno = lineno;
  169:   new->value.value = value;
  170:   new->value.str = str;
  171:   new->type.node_class = etree_value;
  172:   return new;
  173: }
  174: 
  175: /* Build an expression representing an unnamed relocatable value.  */
  176: 
  177: etree_type *
  178: exp_relop (asection *section, bfd_vma value)
  179: {
  180:   etree_type *new = stat_alloc (sizeof (new->rel));
  181:   new->type.node_code = REL;
  182:   new->type.lineno = lineno;
  183:   new->type.node_class = etree_rel;
  184:   new->rel.section = section;
  185:   new->rel.value = value;
  186:   return new;
  187: }
  188: 
  189: static void
  190: new_rel (bfd_vma value, char *str, asection *section)
  191: {
  192:   expld.result.valid_p = TRUE;
  193:   expld.result.value = value;
  194:   expld.result.str = str;
  195:   expld.result.section = section;
  196: }
  197: 
  198: static void
  199: new_rel_from_abs (bfd_vma value)
  200: {
  201:   expld.result.valid_p = TRUE;
  202:   expld.result.value = value - expld.section->vma;
  203:   expld.result.str = NULL;
  204:   expld.result.section = expld.section;
  205: }
  206: 
  207: static void
  208: fold_unary (etree_type *tree)
  209: {
  210:   exp_fold_tree_1 (tree->unary.child);
  211:   if (expld.result.valid_p)
  212:     {
  213:       switch (tree->type.node_code)
  214:         {
  215:         case ALIGN_K:
  216:           if (expld.phase != lang_first_phase_enum)
  217:             new_rel_from_abs (align_n (expld.dot, expld.result.value));
  218:           else
  219:             expld.result.valid_p = FALSE;
  220:           break;
  221: 
  222:         case ABSOLUTE:
  223:           make_abs ();
  224:           break;
  225: 
  226:         case '~':
  227:           make_abs ();
  228:           expld.result.value = ~expld.result.value;
  229:           break;
  230: 
  231:         case '!':
  232:           make_abs ();
  233:           expld.result.value = !expld.result.value;
  234:           break;
  235: 
  236:         case '-':
  237:           make_abs ();
  238:           expld.result.value = -expld.result.value;
  239:           break;
  240: 
  241:         case NEXT:
  242:           /* Return next place aligned to value.  */
  243:           if (expld.phase != lang_first_phase_enum)
  244:             {
  245:               make_abs ();
  246:               expld.result.value = align_n (expld.dot, expld.result.value);
  247:             }
  248:           else
  249:             expld.result.valid_p = FALSE;
  250:           break;
  251: 
  252:         case DATA_SEGMENT_END:
  253:           if (expld.phase != lang_first_phase_enum
  254:               && expld.section == bfd_abs_section_ptr
  255:               && (expld.dataseg.phase == exp_dataseg_align_seen
  256:                   || expld.dataseg.phase == exp_dataseg_relro_seen
  257:                   || expld.dataseg.phase == exp_dataseg_adjust
  258:                   || expld.dataseg.phase == exp_dataseg_relro_adjust
  259:                   || expld.phase == lang_final_phase_enum))
  260:             {
  261:               if (expld.dataseg.phase == exp_dataseg_align_seen
  262:                   || expld.dataseg.phase == exp_dataseg_relro_seen)
  263:                 {
  264:                   expld.dataseg.phase = exp_dataseg_end_seen;
  265:                   expld.dataseg.end = expld.result.value;
  266:                 }
  267:             }
  268:           else
  269:             expld.result.valid_p = FALSE;
  270:           break;
  271: 
  272:         default:
  273:           FAIL ();
  274:           break;
  275:         }
  276:     }
  277: }
  278: 
  279: static void
  280: fold_binary (etree_type *tree)
  281: {
  282:   exp_fold_tree_1 (tree->binary.lhs);
  283: 
  284:   /* The SEGMENT_START operator is special because its first
  285:      operand is a string, not the name of a symbol.  */
  286:   if (expld.result.valid_p && tree->type.node_code == SEGMENT_START)
  287:     {
  288:       const char *segment_name;
  289:       segment_type *seg;
  290:       /* Check to see if the user has overridden the default
  291:          value.  */
  292:       segment_name = tree->binary.rhs->name.name;
  293:       for (seg = segments; seg; seg = seg->next) 
  294:         if (strcmp (seg->name, segment_name) == 0)
  295:           {
  296:             seg->used = TRUE;
  297:             expld.result.value = seg->value;
  298:             expld.result.str = NULL;
  299:             expld.result.section = NULL;
  300:             break;
  301:           }
  302:     }
  303:   else if (expld.result.valid_p)
  304:     {
  305:       etree_value_type lhs = expld.result;
  306: 
  307:       exp_fold_tree_1 (tree->binary.rhs);
  308:       if (expld.result.valid_p)
  309:         {
  310:           /* If the values are from different sections, or this is an
  311:              absolute expression, make both the source arguments
  312:              absolute.  However, adding or subtracting an absolute
  313:              value from a relative value is meaningful, and is an
  314:              exception.  */
  315:           if (expld.section != bfd_abs_section_ptr
  316:               && lhs.section == bfd_abs_section_ptr
  317:               && tree->type.node_code == '+')
  318:             {
  319:               /* Keep the section of the rhs term.  */
  320:               expld.result.value = lhs.value + expld.result.value;
  321:               return;
  322:             }
  323:           else if (expld.section != bfd_abs_section_ptr
  324:               && expld.result.section == bfd_abs_section_ptr
  325:               && (tree->type.node_code == '+'
  326:                   || tree->type.node_code == '-'))
  327:             {
  328:               /* Keep the section of the lhs term.  */
  329:               expld.result.section = lhs.section;
  330:             }
  331:           else if (expld.result.section != lhs.section
  332:                    || expld.section == bfd_abs_section_ptr)
  333:             {
  334:               make_abs ();
  335:               lhs.value += lhs.section->vma;
  336:             }
  337: 
  338:           switch (tree->type.node_code)
  339:             {
  340:             case '%':
  341:               if (expld.result.value != 0)
  342:                 expld.result.value = ((bfd_signed_vma) lhs.value
  343:                                       % (bfd_signed_vma) expld.result.value);
  344:               else if (expld.phase != lang_mark_phase_enum)
  345:                 einfo (_("%F%S %% by zero\n"));
  346:               break;
  347: 
  348:             case '/':
  349:               if (expld.result.value != 0)
  350:                 expld.result.value = ((bfd_signed_vma) lhs.value
  351:                                       / (bfd_signed_vma) expld.result.value);
  352:               else if (expld.phase != lang_mark_phase_enum)
  353:                 einfo (_("%F%S / by zero\n"));
  354:               break;
  355: 
  356: #define BOP(x, y) \
  357:             case x:                                                    \
  358:               expld.result.value = lhs.value y expld.result.value;     \
  359:               break;
  360: 
  361:               BOP ('+', +);
  362:               BOP ('*', *);
  363:               BOP ('-', -);
  364:               BOP (LSHIFT, <<);
  365:               BOP (RSHIFT, >>);
  366:               BOP (EQ, ==);
  367:               BOP (NE, !=);
  368:               BOP ('<', <);
  369:               BOP ('>', >);
  370:               BOP (LE, <=);
  371:               BOP (GE, >=);
  372:               BOP ('&', &);
  373:               BOP ('^', ^);
  374:               BOP ('|', |);
  375:               BOP (ANDAND, &&);
  376:               BOP (OROR, ||);
  377: 
  378:             case MAX_K:
  379:               if (lhs.value > expld.result.value)
  380:                 expld.result.value = lhs.value;
  381:               break;
  382: 
  383:             case MIN_K:
  384:               if (lhs.value < expld.result.value)
  385:                 expld.result.value = lhs.value;
  386:               break;
  387: 
  388:             case ALIGN_K:
  389:               expld.result.value = align_n (lhs.value, expld.result.value);
  390:               break;
  391: 
  392:             case DATA_SEGMENT_ALIGN:
  393:               if (expld.phase != lang_first_phase_enum
  394:                   && expld.section == bfd_abs_section_ptr
  395:                   && (expld.dataseg.phase == exp_dataseg_none
  396:                       || expld.dataseg.phase == exp_dataseg_adjust
  397:                       || expld.dataseg.phase == exp_dataseg_relro_adjust
  398:                       || expld.phase == lang_final_phase_enum))
  399:                 {
  400:                   bfd_vma maxpage = lhs.value;
  401:                   bfd_vma commonpage = expld.result.value;
  402: 
  403:                   expld.result.value = align_n (expld.dot, maxpage);
  404:                   if (expld.dataseg.phase == exp_dataseg_relro_adjust)
  405:                     expld.result.value = expld.dataseg.base;
  406:                   else if (expld.dataseg.phase != exp_dataseg_adjust)
  407:                     {
  408:                       expld.result.value += expld.dot & (maxpage - 1);
  409:                       if (expld.phase == lang_allocating_phase_enum)
  410:                         {
  411:                           expld.dataseg.phase = exp_dataseg_align_seen;
  412:                           expld.dataseg.min_base = align_n (expld.dot, maxpage);
  413:                           expld.dataseg.base = expld.result.value;
  414:                           expld.dataseg.pagesize = commonpage;
  415:                           expld.dataseg.maxpagesize = maxpage;
  416:                           expld.dataseg.relro_end = 0;
  417:                         }
  418:                     }
  419:                   else if (commonpage < maxpage)
  420:                     expld.result.value += ((expld.dot + commonpage - 1)
  421:                                            & (maxpage - commonpage));
  422:                 }
  423:               else
  424:                 expld.result.valid_p = FALSE;
  425:               break;
  426: 
  427:             case DATA_SEGMENT_RELRO_END:
  428:               if (expld.phase != lang_first_phase_enum
  429:                   && (expld.dataseg.phase == exp_dataseg_align_seen
  430:                       || expld.dataseg.phase == exp_dataseg_adjust
  431:                       || expld.dataseg.phase == exp_dataseg_relro_adjust
  432:                       || expld.phase == lang_final_phase_enum))
  433:                 {
  434:                   if (expld.dataseg.phase == exp_dataseg_align_seen
  435:                       || expld.dataseg.phase == exp_dataseg_relro_adjust)
  436:                     expld.dataseg.relro_end = lhs.value + expld.result.value;
  437: 
  438:                   if (expld.dataseg.phase == exp_dataseg_relro_adjust
  439:                       && (expld.dataseg.relro_end
  440:                           & (expld.dataseg.pagesize - 1)))
  441:                     {
  442:                       expld.dataseg.relro_end += expld.dataseg.pagesize - 1;
  443:                       expld.dataseg.relro_end &= ~(expld.dataseg.pagesize - 1);
  444:                       expld.result.value = (expld.dataseg.relro_end
  445:                                             - expld.result.value);
  446:                     }
  447:                   else
  448:                     expld.result.value = lhs.value;
  449: 
  450:                   if (expld.dataseg.phase == exp_dataseg_align_seen)
  451:                     expld.dataseg.phase = exp_dataseg_relro_seen;
  452:                 }
  453:               else
  454:                 expld.result.valid_p = FALSE;
  455:               break;
  456: 
  457:             default:
  458:               FAIL ();
  459:             }
  460:         }
  461:       else
  462:         expld.result.valid_p = FALSE;
  463:     }
  464: }
  465: 
  466: static void
  467: fold_trinary (etree_type *tree)
  468: {
  469:   exp_fold_tree_1 (tree->trinary.cond);
  470:   if (expld.result.valid_p)
  471:     exp_fold_tree_1 (expld.result.value
  472:                      ? tree->trinary.lhs
  473:                      : tree->trinary.rhs);
  474: }
  475: 
  476: static void
  477: fold_name (etree_type *tree)
  478: {
  479:   memset (&expld.result, 0, sizeof (expld.result));
  480: 
  481:   switch (tree->type.node_code)
  482:     {
  483:     case SIZEOF_HEADERS:
  484:       if (expld.phase != lang_first_phase_enum)
  485:         {
  486:           bfd_vma hdr_size = 0;
  487:           /* Don't find the real header size if only marking sections;
  488:              The bfd function may cache incorrect data.  */
  489:           if (expld.phase != lang_mark_phase_enum)
  490:             hdr_size = bfd_sizeof_headers (output_bfd, &link_info);
  491:           new_abs (hdr_size);
  492:         }
  493:       break;
  494: 
  495:     case DEFINED:
  496:       if (expld.phase == lang_first_phase_enum)
  497:         lang_track_definedness (tree->name.name);
  498:       else
  499:         {
  500:           struct bfd_link_hash_entry *h;
  501:           int def_iteration
  502:             = lang_symbol_definition_iteration (tree->name.name);
  503: 
  504:           h = bfd_wrapped_link_hash_lookup (output_bfd, &link_info,
  505:                                             tree->name.name,
  506:                                             FALSE, FALSE, TRUE);
  507:           expld.result.value = (h != NULL
  508:                                 && (h->type == bfd_link_hash_defined
  509:                                     || h->type == bfd_link_hash_defweak
  510:                                     || h->type == bfd_link_hash_common)
  511:                                 && (def_iteration == lang_statement_iteration
  512:                                     || def_iteration == -1));
  513:           expld.result.section = bfd_abs_section_ptr;
  514:           expld.result.valid_p = TRUE;
  515:         }
  516:       break;
  517: 
  518:     case NAME:
  519:       if (expld.phase == lang_first_phase_enum)
  520:         ;
  521:       else if (tree->name.name[0] == '.' && tree->name.name[1] == 0)
  522:         new_rel_from_abs (expld.dot);
  523:       else
  524:         {
  525:           struct bfd_link_hash_entry *h;
  526: 
  527:           h = bfd_wrapped_link_hash_lookup (output_bfd, &link_info,
  528:                                             tree->name.name,
  529:                                             TRUE, FALSE, TRUE);
  530:           if (!h)
  531:             einfo (_("%P%F: bfd_link_hash_lookup failed: %E\n"));
  532:           else if (h->type == bfd_link_hash_defined
  533:                    || h->type == bfd_link_hash_defweak)
  534:             {
  535:               if (bfd_is_abs_section (h->u.def.section))
  536:                 new_abs (h->u.def.value);
  537:               else
  538:                 {
  539:                   asection *output_section;
  540: 
  541:                   output_section = h->u.def.section->output_section;
  542:                   if (output_section == NULL)
  543:                     {
  544:                       if (expld.phase != lang_mark_phase_enum)
  545:                         einfo (_("%X%S: unresolvable symbol `%s'"
  546:                                  " referenced in expression\n"),
  547:                                tree->name.name);
  548:                     }
  549:                   else
  550:                     new_rel (h->u.def.value + h->u.def.section->output_offset,
  551:                              NULL, output_section);
  552:                 }
  553:             }
  554:           else if (expld.phase == lang_final_phase_enum
  555:                    || expld.assigning_to_dot)
  556:             einfo (_("%F%S: undefined symbol `%s' referenced in expression\n"),
  557:                    tree->name.name);
  558:           else if (h->type == bfd_link_hash_new)
  559:             {
  560:               h->type = bfd_link_hash_undefined;
  561:               h->u.undef.abfd = NULL;
  562:               if (h->u.undef.next == NULL && h != link_info.hash->undefs_tail)
  563:                 bfd_link_add_undef (link_info.hash, h);
  564:             }
  565:         }
  566:       break;
  567: