1 /* This module handles expression trees.
2 Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
4 Free Software Foundation, Inc.
5 Written by Steve Chamberlain of Cygnus Support <sac@cygnus.com>.
7 This file is part of GLD, the Gnu Linker.
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)
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.
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, 59 Temple Place - Suite 330, Boston, MA
24 /* This module is in charge of working out the contents of expressions.
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
41 #include "libiberty.h"
42 #include "safe-ctype.h"
44 static etree_value_type exp_fold_tree_no_dot
45 (etree_type *, lang_output_section_statement_type *, lang_phase_type);
47 struct exp_data_seg exp_data_seg;
49 /* Print the string representation of the given token. Surround it
50 with spaces if INFIX_P is TRUE. */
53 exp_print_token (token_code_type code, int infix_p)
87 { SECTIONS, "SECTIONS" },
88 { SIZEOF_HEADERS, "SIZEOF_HEADERS" },
90 { DEFINED, "DEFINED" },
91 { TARGET_K, "TARGET" },
92 { SEARCH_DIR, "SEARCH_DIR" },
98 { LOADADDR, "LOADADDR" },
100 { REL, "relocatable" },
101 { DATA_SEGMENT_ALIGN, "DATA_SEGMENT_ALIGN" },
102 { DATA_SEGMENT_END, "DATA_SEGMENT_END" }
106 for (idx = 0; idx < ARRAY_SIZE (table); idx++)
107 if (table[idx].code == code)
111 fputc (' ', config.map_file);
113 if (idx < ARRAY_SIZE (table))
114 fputs (table[idx].name, config.map_file);
116 fputc (code, config.map_file);
118 fprintf (config.map_file, "<code %d>", code);
121 fputc (' ', config.map_file);
125 make_abs (etree_value_type *ptr)
127 asection *s = ptr->section->bfd_section;
128 ptr->value += s->vma;
129 ptr->section = abs_output_section;
132 static etree_value_type
133 new_abs (bfd_vma value)
135 etree_value_type new;
137 new.section = abs_output_section;
143 check (lang_output_section_statement_type *os,
148 einfo (_("%F%P: %s uses undefined section %s\n"), op, name);
150 einfo (_("%F%P: %s forward reference of section %s\n"), op, name);
154 exp_intop (bfd_vma value)
156 etree_type *new = stat_alloc (sizeof (new->value));
157 new->type.node_code = INT;
158 new->value.value = value;
159 new->value.str = NULL;
160 new->type.node_class = etree_value;
165 exp_bigintop (bfd_vma value, char *str)
167 etree_type *new = stat_alloc (sizeof (new->value));
168 new->type.node_code = INT;
169 new->value.value = value;
170 new->value.str = str;
171 new->type.node_class = etree_value;
175 /* Build an expression representing an unnamed relocatable value. */
178 exp_relop (asection *section, bfd_vma value)
180 etree_type *new = stat_alloc (sizeof (new->rel));
181 new->type.node_code = REL;
182 new->type.node_class = etree_rel;
183 new->rel.section = section;
184 new->rel.value = value;
188 static etree_value_type
189 new_rel (bfd_vma value,
191 lang_output_section_statement_type *section)
193 etree_value_type new;
197 new.section = section;
201 static etree_value_type
202 new_rel_from_section (bfd_vma value,
203 lang_output_section_statement_type *section)
205 etree_value_type new;
209 new.section = section;
211 new.value -= section->bfd_section->vma;
216 static etree_value_type
217 fold_unary (etree_type *tree,
218 lang_output_section_statement_type *current_section,
219 lang_phase_type allocation_done,
223 etree_value_type result;
225 result = exp_fold_tree (tree->unary.child,
227 allocation_done, dot, dotp);
230 switch (tree->type.node_code)
233 if (allocation_done != lang_first_phase_enum)
234 result = new_rel_from_section (align_n (dot, result.value),
237 result.valid_p = FALSE;
241 if (allocation_done != lang_first_phase_enum)
243 result.value += result.section->bfd_section->vma;
244 result.section = abs_output_section;
247 result.valid_p = FALSE;
252 result.value = ~result.value;
257 result.value = !result.value;
262 result.value = -result.value;
266 /* Return next place aligned to value. */
267 if (allocation_done == lang_allocating_phase_enum)
270 result.value = align_n (dot, result.value);
273 result.valid_p = FALSE;
276 case DATA_SEGMENT_END:
277 if (allocation_done != lang_first_phase_enum
278 && current_section == abs_output_section
279 && (exp_data_seg.phase == exp_dataseg_align_seen
280 || exp_data_seg.phase == exp_dataseg_adjust
281 || allocation_done != lang_allocating_phase_enum))
283 if (exp_data_seg.phase == exp_dataseg_align_seen)
285 exp_data_seg.phase = exp_dataseg_end_seen;
286 exp_data_seg.end = result.value;
290 result.valid_p = FALSE;
302 static etree_value_type
303 fold_binary (etree_type *tree,
304 lang_output_section_statement_type *current_section,
305 lang_phase_type allocation_done,
309 etree_value_type result;
311 result = exp_fold_tree (tree->binary.lhs, current_section,
312 allocation_done, dot, dotp);
315 etree_value_type other;
317 other = exp_fold_tree (tree->binary.rhs,
319 allocation_done, dot, dotp);
322 /* If the values are from different sections, or this is an
323 absolute expression, make both the source arguments
324 absolute. However, adding or subtracting an absolute
325 value from a relative value is meaningful, and is an
327 if (current_section != abs_output_section
328 && (other.section == abs_output_section
329 || (result.section == abs_output_section
330 && tree->type.node_code == '+'))
331 && (tree->type.node_code == '+'
332 || tree->type.node_code == '-'))
334 if (other.section != abs_output_section)
336 /* Keep the section of the other term. */
337 if (tree->type.node_code == '+')
338 other.value = result.value + other.value;
340 other.value = result.value - other.value;
344 else if (result.section != other.section
345 || current_section == abs_output_section)
351 switch (tree->type.node_code)
354 if (other.value == 0)
355 einfo (_("%F%S %% by zero\n"));
356 result.value = ((bfd_signed_vma) result.value
357 % (bfd_signed_vma) other.value);
361 if (other.value == 0)
362 einfo (_("%F%S / by zero\n"));
363 result.value = ((bfd_signed_vma) result.value
364 / (bfd_signed_vma) other.value);
367 #define BOP(x,y) case x : result.value = result.value y other.value; break;
386 if (result.value < other.value)
391 if (result.value > other.value)
395 case DATA_SEGMENT_ALIGN:
396 if (allocation_done != lang_first_phase_enum
397 && current_section == abs_output_section
398 && (exp_data_seg.phase == exp_dataseg_none
399 || exp_data_seg.phase == exp_dataseg_adjust
400 || allocation_done != lang_allocating_phase_enum))
402 bfd_vma maxpage = result.value;
404 result.value = align_n (dot, maxpage);
405 if (exp_data_seg.phase != exp_dataseg_adjust)
407 result.value += dot & (maxpage - 1);
408 if (allocation_done == lang_allocating_phase_enum)
410 exp_data_seg.phase = exp_dataseg_align_seen;
411 exp_data_seg.base = result.value;
412 exp_data_seg.pagesize = other.value;
415 else if (other.value < maxpage)
416 result.value += (dot + other.value - 1)
417 & (maxpage - other.value);
420 result.valid_p = FALSE;
429 result.valid_p = FALSE;
436 static etree_value_type
437 fold_trinary (etree_type *tree,
438 lang_output_section_statement_type *current_section,
439 lang_phase_type allocation_done,
443 etree_value_type result;
445 result = exp_fold_tree (tree->trinary.cond, current_section,
446 allocation_done, dot, dotp);
448 result = exp_fold_tree ((result.value
450 : tree->trinary.rhs),
452 allocation_done, dot, dotp);
460 etree_value_type new;
465 static etree_value_type
466 fold_name (etree_type *tree,
467 lang_output_section_statement_type *current_section,
468 lang_phase_type allocation_done,
471 etree_value_type result;
473 switch (tree->type.node_code)
476 if (allocation_done != lang_first_phase_enum)
478 result = new_abs (bfd_sizeof_headers (output_bfd,
479 link_info.relocatable));
483 result.valid_p = FALSE;
487 if (allocation_done == lang_first_phase_enum)
488 result.valid_p = FALSE;
491 struct bfd_link_hash_entry *h;
493 h = bfd_wrapped_link_hash_lookup (output_bfd, &link_info,
496 result.value = (h != NULL
497 && (h->type == bfd_link_hash_defined
498 || h->type == bfd_link_hash_defweak
499 || h->type == bfd_link_hash_common));
500 result.section = abs_output_section;
501 result.valid_p = TRUE;
505 result.valid_p = FALSE;
506 if (tree->name.name[0] == '.' && tree->name.name[1] == 0)
508 if (allocation_done != lang_first_phase_enum)
509 result = new_rel_from_section (dot, current_section);
513 else if (allocation_done != lang_first_phase_enum)
515 struct bfd_link_hash_entry *h;
517 h = bfd_wrapped_link_hash_lookup (output_bfd, &link_info,
521 && (h->type == bfd_link_hash_defined
522 || h->type == bfd_link_hash_defweak))
524 if (bfd_is_abs_section (h->u.def.section))
525 result = new_abs (h->u.def.value);
526 else if (allocation_done == lang_final_phase_enum
527 || allocation_done == lang_allocating_phase_enum)
529 asection *output_section;
531 output_section = h->u.def.section->output_section;
532 if (output_section == NULL)
533 einfo (_("%X%S: unresolvable symbol `%s' referenced in expression\n"),
537 lang_output_section_statement_type *os;
539 os = (lang_output_section_statement_lookup
540 (bfd_get_section_name (output_bfd,
543 /* FIXME: Is this correct if this section is
544 being linked with -R? */
545 result = new_rel ((h->u.def.value
546 + h->u.def.section->output_offset),
552 else if (allocation_done == lang_final_phase_enum)
553 einfo (_("%F%S: undefined symbol `%s' referenced in expression\n"),
559 if (allocation_done != lang_first_phase_enum)
561 lang_output_section_statement_type *os;
563 os = lang_output_section_find (tree->name.name);
564 check (os, tree->name.name, "ADDR");
565 result = new_rel (0, NULL, os);
572 if (allocation_done != lang_first_phase_enum)
574 lang_output_section_statement_type *os;
576 os = lang_output_section_find (tree->name.name);
577 check (os, tree->name.name, "LOADADDR");
578 if (os->load_base == NULL)
579 result = new_rel (0, NULL, os);
581 result = exp_fold_tree_no_dot (os->load_base,
590 if (allocation_done != lang_first_phase_enum)
592 int opb = bfd_octets_per_byte (output_bfd);
593 lang_output_section_statement_type *os;
595 os = lang_output_section_find (tree->name.name);
596 check (os, tree->name.name, "SIZEOF");
597 result = new_abs (os->bfd_section->_raw_size / opb);
612 exp_fold_tree (etree_type *tree,
613 lang_output_section_statement_type *current_section,
614 lang_phase_type allocation_done,
618 etree_value_type result;
622 result.valid_p = FALSE;
626 switch (tree->type.node_class)
629 result = new_rel (tree->value.value, tree->value.str, current_section);
633 if (allocation_done != lang_final_phase_enum)
634 result.valid_p = FALSE;
636 result = new_rel ((tree->rel.value
637 + tree->rel.section->output_section->vma
638 + tree->rel.section->output_offset),
644 result = exp_fold_tree (tree->assert_s.child,
646 allocation_done, dot, dotp);
650 einfo ("%F%P: %s\n", tree->assert_s.message);
656 result = fold_unary (tree, current_section, allocation_done,
661 result = fold_binary (tree, current_section, allocation_done,
666 result = fold_trinary (tree, current_section, allocation_done,
673 if (tree->assign.dst[0] == '.' && tree->assign.dst[1] == 0)
675 /* Assignment to dot can only be done during allocation. */
676 if (tree->type.node_class != etree_assign)
677 einfo (_("%F%S can not PROVIDE assignment to location counter\n"));
678 if (allocation_done == lang_allocating_phase_enum
679 || (allocation_done == lang_final_phase_enum
680 && current_section == abs_output_section))
682 result = exp_fold_tree (tree->assign.src,
684 allocation_done, dot,
686 if (! result.valid_p)
687 einfo (_("%F%S invalid assignment to location counter\n"));
690 if (current_section == NULL)
691 einfo (_("%F%S assignment to location counter invalid outside of SECTION\n"));
696 nextdot = (result.value
697 + current_section->bfd_section->vma);
699 && current_section != abs_output_section)
700 einfo (_("%F%S cannot move location counter backwards (from %V to %V)\n"),
710 result = exp_fold_tree (tree->assign.src,
711 current_section, allocation_done,
716 struct bfd_link_hash_entry *h;
718 if (tree->type.node_class == etree_assign)
722 h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
723 create, FALSE, FALSE);
726 if (tree->type.node_class == etree_assign)
727 einfo (_("%P%F:%s: hash creation failed\n"),
730 else if (tree->type.node_class == etree_provide
731 && h->type != bfd_link_hash_undefined
732 && h->type != bfd_link_hash_common)
734 /* Do nothing. The symbol was defined by some
739 /* FIXME: Should we worry if the symbol is already
741 h->type = bfd_link_hash_defined;
742 h->u.def.value = result.value;
743 h->u.def.section = result.section->bfd_section;
744 if (tree->type.node_class == etree_provide)
745 tree->type.node_class = etree_provided;
752 result = fold_name (tree, current_section, allocation_done, dot);
763 static etree_value_type
764 exp_fold_tree_no_dot (etree_type *tree,
765 lang_output_section_statement_type *current_section,
766 lang_phase_type allocation_done)
768 return exp_fold_tree (tree, current_section, allocation_done, 0, NULL);
772 exp_binop (int code, etree_type *lhs, etree_type *rhs)
774 etree_type value, *new;
777 value.type.node_code = code;
778 value.binary.lhs = lhs;
779 value.binary.rhs = rhs;
780 value.type.node_class = etree_binary;
781 r = exp_fold_tree_no_dot (&value,
783 lang_first_phase_enum);
786 return exp_intop (r.value);
788 new = stat_alloc (sizeof (new->binary));
789 memcpy (new, &value, sizeof (new->binary));
794 exp_trinop (int code, etree_type *cond, etree_type *lhs, etree_type *rhs)
796 etree_type value, *new;
798 value.type.node_code = code;
799 value.trinary.lhs = lhs;
800 value.trinary.cond = cond;
801 value.trinary.rhs = rhs;
802 value.type.node_class = etree_trinary;
803 r = exp_fold_tree_no_dot (&value, NULL, lang_first_phase_enum);
805 return exp_intop (r.value);
807 new = stat_alloc (sizeof (new->trinary));
808 memcpy (new, &value, sizeof (new->trinary));
813 exp_unop (int code, etree_type *child)
815 etree_type value, *new;
818 value.unary.type.node_code = code;
819 value.unary.child = child;
820 value.unary.type.node_class = etree_unary;
821 r = exp_fold_tree_no_dot (&value, abs_output_section,
822 lang_first_phase_enum);
824 return exp_intop (r.value);
826 new = stat_alloc (sizeof (new->unary));
827 memcpy (new, &value, sizeof (new->unary));
832 exp_nameop (int code, const char *name)
834 etree_type value, *new;
836 value.name.type.node_code = code;
837 value.name.name = name;
838 value.name.type.node_class = etree_name;
840 r = exp_fold_tree_no_dot (&value, NULL, lang_first_phase_enum);
842 return exp_intop (r.value);
844 new = stat_alloc (sizeof (new->name));
845 memcpy (new, &value, sizeof (new->name));
851 exp_assop (int code, const char *dst, etree_type *src)
853 etree_type value, *new;
855 value.assign.type.node_code = code;
857 value.assign.src = src;
858 value.assign.dst = dst;
859 value.assign.type.node_class = etree_assign;
862 if (exp_fold_tree_no_dot (&value, &result))
863 return exp_intop (result);
865 new = stat_alloc (sizeof (new->assign));
866 memcpy (new, &value, sizeof (new->assign));
870 /* Handle PROVIDE. */
873 exp_provide (const char *dst, etree_type *src)
877 n = stat_alloc (sizeof (n->assign));
878 n->assign.type.node_code = '=';
879 n->assign.type.node_class = etree_provide;
888 exp_assert (etree_type *exp, const char *message)
892 n = stat_alloc (sizeof (n->assert_s));
893 n->assert_s.type.node_code = '!';
894 n->assert_s.type.node_class = etree_assert;
895 n->assert_s.child = exp;
896 n->assert_s.message = message;
901 exp_print_tree (etree_type *tree)
903 if (config.map_file == NULL)
904 config.map_file = stderr;
908 minfo ("NULL TREE\n");
912 switch (tree->type.node_class)
915 minfo ("0x%v", tree->value.value);
918 if (tree->rel.section->owner != NULL)
919 minfo ("%B:", tree->rel.section->owner);
920 minfo ("%s+0x%v", tree->rel.section->name, tree->rel.value);
924 if (tree->assign.dst->sdefs != NULL)
925 fprintf (config.map_file, "%s (%x) ", tree->assign.dst->name,
926 tree->assign.dst->sdefs->value);
928 fprintf (config.map_file, "%s (UNDEFINED)", tree->assign.dst->name);
930 fprintf (config.map_file, "%s", tree->assign.dst);
931 exp_print_token (tree->type.node_code, TRUE);
932 exp_print_tree (tree->assign.src);
936 fprintf (config.map_file, "PROVIDE (%s, ", tree->assign.dst);
937 exp_print_tree (tree->assign.src);
938 fprintf (config.map_file, ")");
941 fprintf (config.map_file, "(");
942 exp_print_tree (tree->binary.lhs);
943 exp_print_token (tree->type.node_code, TRUE);
944 exp_print_tree (tree->binary.rhs);
945 fprintf (config.map_file, ")");
948 exp_print_tree (tree->trinary.cond);
949 fprintf (config.map_file, "?");
950 exp_print_tree (tree->trinary.lhs);
951 fprintf (config.map_file, ":");
952 exp_print_tree (tree->trinary.rhs);
955 exp_print_token (tree->unary.type.node_code, FALSE);
956 if (tree->unary.child)
958 fprintf (config.map_file, " (");
959 exp_print_tree (tree->unary.child);
960 fprintf (config.map_file, ")");
965 fprintf (config.map_file, "ASSERT (");
966 exp_print_tree (tree->assert_s.child);
967 fprintf (config.map_file, ", %s)", tree->assert_s.message);
971 fprintf (config.map_file, "????????");
974 if (tree->type.node_code == NAME)
976 fprintf (config.map_file, "%s", tree->name.name);
980 exp_print_token (tree->type.node_code, FALSE);
982 fprintf (config.map_file, " (%s)", tree->name.name);
992 exp_get_vma (etree_type *tree,
995 lang_phase_type allocation_done)
1001 r = exp_fold_tree_no_dot (tree, abs_output_section, allocation_done);
1002 if (! r.valid_p && name != NULL)
1003 einfo (_("%F%S nonconstant expression for %s\n"), name);
1011 exp_get_value_int (etree_type *tree,
1014 lang_phase_type allocation_done)
1016 return exp_get_vma (tree, def, name, allocation_done);
1020 exp_get_fill (etree_type *tree,
1023 lang_phase_type allocation_done)
1033 r = exp_fold_tree_no_dot (tree, abs_output_section, allocation_done);
1034 if (! r.valid_p && name != NULL)
1035 einfo (_("%F%S nonconstant expression for %s\n"), name);
1037 if (r.str != NULL && (len = strlen (r.str)) != 0)
1041 fill = xmalloc ((len + 1) / 2 + sizeof (*fill) - 1);
1042 fill->size = (len + 1) / 2;
1052 digit = (digit - 'A' + '0' + 10) & 0xf;
1066 fill = xmalloc (4 + sizeof (*fill) - 1);
1068 fill->data[0] = (val >> 24) & 0xff;
1069 fill->data[1] = (val >> 16) & 0xff;
1070 fill->data[2] = (val >> 8) & 0xff;
1071 fill->data[3] = (val >> 0) & 0xff;
1078 exp_get_abs_int (etree_type *tree,
1079 int def ATTRIBUTE_UNUSED,
1081 lang_phase_type allocation_done)
1083 etree_value_type res;
1084 res = exp_fold_tree_no_dot (tree, abs_output_section, allocation_done);
1087 res.value += res.section->bfd_section->vma;
1089 einfo (_("%F%S non constant expression for %s\n"), name);
1094 bfd_vma align_n (bfd_vma value, bfd_vma align)
1099 value = (value + align - 1) / align;
1100 return value * align;