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);
46 static bfd_vma align_n
49 struct exp_data_seg exp_data_seg;
51 /* Print the string representation of the given token. Surround it
52 with spaces if INFIX_P is TRUE. */
55 exp_print_token (token_code_type code, int infix_p)
89 { SECTIONS, "SECTIONS" },
90 { SIZEOF_HEADERS, "SIZEOF_HEADERS" },
92 { DEFINED, "DEFINED" },
93 { TARGET_K, "TARGET" },
94 { SEARCH_DIR, "SEARCH_DIR" },
100 { LOADADDR, "LOADADDR" },
102 { REL, "relocatable" },
103 { DATA_SEGMENT_ALIGN, "DATA_SEGMENT_ALIGN" },
104 { DATA_SEGMENT_RELRO_END, "DATA_SEGMENT_RELRO_END" },
105 { DATA_SEGMENT_END, "DATA_SEGMENT_END" }
109 for (idx = 0; idx < ARRAY_SIZE (table); idx++)
110 if (table[idx].code == code)
114 fputc (' ', config.map_file);
116 if (idx < ARRAY_SIZE (table))
117 fputs (table[idx].name, config.map_file);
119 fputc (code, config.map_file);
121 fprintf (config.map_file, "<code %d>", code);
124 fputc (' ', config.map_file);
128 make_abs (etree_value_type *ptr)
130 asection *s = ptr->section->bfd_section;
131 ptr->value += s->vma;
132 ptr->section = abs_output_section;
135 static etree_value_type
136 new_abs (bfd_vma value)
138 etree_value_type new;
140 new.section = abs_output_section;
146 exp_intop (bfd_vma value)
148 etree_type *new = stat_alloc (sizeof (new->value));
149 new->type.node_code = INT;
150 new->value.value = value;
151 new->value.str = NULL;
152 new->type.node_class = etree_value;
157 exp_bigintop (bfd_vma value, char *str)
159 etree_type *new = stat_alloc (sizeof (new->value));
160 new->type.node_code = INT;
161 new->value.value = value;
162 new->value.str = str;
163 new->type.node_class = etree_value;
167 /* Build an expression representing an unnamed relocatable value. */
170 exp_relop (asection *section, bfd_vma value)
172 etree_type *new = stat_alloc (sizeof (new->rel));
173 new->type.node_code = REL;
174 new->type.node_class = etree_rel;
175 new->rel.section = section;
176 new->rel.value = value;
180 static etree_value_type
181 new_rel (bfd_vma value,
183 lang_output_section_statement_type *section)
185 etree_value_type new;
189 new.section = section;
193 static etree_value_type
194 new_rel_from_section (bfd_vma value,
195 lang_output_section_statement_type *section)
197 etree_value_type new;
201 new.section = section;
203 new.value -= section->bfd_section->vma;
208 static etree_value_type
209 fold_unary (etree_type *tree,
210 lang_output_section_statement_type *current_section,
211 lang_phase_type allocation_done,
215 etree_value_type result;
217 result = exp_fold_tree (tree->unary.child,
219 allocation_done, dot, dotp);
222 switch (tree->type.node_code)
225 if (allocation_done != lang_first_phase_enum)
226 result = new_rel_from_section (align_n (dot, result.value),
229 result.valid_p = FALSE;
233 if (allocation_done != lang_first_phase_enum)
235 result.value += result.section->bfd_section->vma;
236 result.section = abs_output_section;
239 result.valid_p = FALSE;
244 result.value = ~result.value;
249 result.value = !result.value;
254 result.value = -result.value;
258 /* Return next place aligned to value. */
259 if (allocation_done == lang_allocating_phase_enum)
262 result.value = align_n (dot, result.value);
265 result.valid_p = FALSE;
268 case DATA_SEGMENT_RELRO_END:
269 if (allocation_done != lang_first_phase_enum
270 && (exp_data_seg.phase == exp_dataseg_align_seen
271 || exp_data_seg.phase == exp_dataseg_adjust
272 || exp_data_seg.phase == exp_dataseg_relro_adjust
273 || allocation_done != lang_allocating_phase_enum))
275 if (exp_data_seg.phase == exp_dataseg_align_seen
276 || exp_data_seg.phase == exp_dataseg_relro_adjust)
277 exp_data_seg.relro_end
278 = result.value + current_section->bfd_section->vma;
279 if (exp_data_seg.phase == exp_dataseg_align_seen)
280 exp_data_seg.phase = exp_dataseg_relro_seen;
281 result.value = dot - current_section->bfd_section->vma;
284 result.valid_p = FALSE;
287 case DATA_SEGMENT_END:
288 if (allocation_done != lang_first_phase_enum
289 && current_section == abs_output_section
290 && (exp_data_seg.phase == exp_dataseg_align_seen
291 || exp_data_seg.phase == exp_dataseg_relro_seen
292 || exp_data_seg.phase == exp_dataseg_adjust
293 || exp_data_seg.phase == exp_dataseg_relro_adjust
294 || allocation_done != lang_allocating_phase_enum))
296 if (exp_data_seg.phase == exp_dataseg_align_seen
297 || exp_data_seg.phase == exp_dataseg_relro_seen)
299 exp_data_seg.phase = exp_dataseg_end_seen;
300 exp_data_seg.end = result.value;
304 result.valid_p = FALSE;
316 static etree_value_type
317 fold_binary (etree_type *tree,
318 lang_output_section_statement_type *current_section,
319 lang_phase_type allocation_done,
323 etree_value_type result;
325 result = exp_fold_tree (tree->binary.lhs, current_section,
326 allocation_done, dot, dotp);
329 etree_value_type other;
331 other = exp_fold_tree (tree->binary.rhs,
333 allocation_done, dot, dotp);
336 /* If the values are from different sections, or this is an
337 absolute expression, make both the source arguments
338 absolute. However, adding or subtracting an absolute
339 value from a relative value is meaningful, and is an
341 if (current_section != abs_output_section
342 && (other.section == abs_output_section
343 || (result.section == abs_output_section
344 && tree->type.node_code == '+'))
345 && (tree->type.node_code == '+'
346 || tree->type.node_code == '-'))
348 if (other.section != abs_output_section)
350 /* Keep the section of the other term. */
351 if (tree->type.node_code == '+')
352 other.value = result.value + other.value;
354 other.value = result.value - other.value;
358 else if (result.section != other.section
359 || current_section == abs_output_section)
365 switch (tree->type.node_code)
368 if (other.value == 0)
369 einfo (_("%F%S %% by zero\n"));
370 result.value = ((bfd_signed_vma) result.value
371 % (bfd_signed_vma) other.value);
375 if (other.value == 0)
376 einfo (_("%F%S / by zero\n"));
377 result.value = ((bfd_signed_vma) result.value
378 / (bfd_signed_vma) other.value);
381 #define BOP(x,y) case x : result.value = result.value y other.value; break;
400 if (result.value < other.value)
405 if (result.value > other.value)
410 result.value = align_n (result.value, other.value);
413 case DATA_SEGMENT_ALIGN:
414 if (allocation_done != lang_first_phase_enum
415 && current_section == abs_output_section
416 && (exp_data_seg.phase == exp_dataseg_none
417 || exp_data_seg.phase == exp_dataseg_adjust
418 || exp_data_seg.phase == exp_dataseg_relro_adjust
419 || allocation_done != lang_allocating_phase_enum))
421 bfd_vma maxpage = result.value;
423 result.value = align_n (dot, maxpage);
424 if (exp_data_seg.phase == exp_dataseg_relro_adjust)
426 /* Attempt to align DATA_SEGMENT_RELRO_END at
427 a common page boundary. */
428 exp_data_seg.base += (-exp_data_seg.relro_end
429 & (other.value - 1));
430 result.value = exp_data_seg.base;
432 else if (exp_data_seg.phase != exp_dataseg_adjust)
434 result.value += dot & (maxpage - 1);
435 if (allocation_done == lang_allocating_phase_enum)
437 exp_data_seg.phase = exp_dataseg_align_seen;
438 exp_data_seg.base = result.value;
439 exp_data_seg.pagesize = other.value;
440 exp_data_seg.relro_end = 0;
443 else if (other.value < maxpage)
444 result.value += (dot + other.value - 1)
445 & (maxpage - other.value);
448 result.valid_p = FALSE;
457 result.valid_p = FALSE;
464 static etree_value_type
465 fold_trinary (etree_type *tree,
466 lang_output_section_statement_type *current_section,
467 lang_phase_type allocation_done,
471 etree_value_type result;
473 result = exp_fold_tree (tree->trinary.cond, current_section,
474 allocation_done, dot, dotp);
476 result = exp_fold_tree ((result.value
478 : tree->trinary.rhs),
480 allocation_done, dot, dotp);
485 static etree_value_type
486 fold_name (etree_type *tree,
487 lang_output_section_statement_type *current_section,
488 lang_phase_type allocation_done,
491 etree_value_type result;
493 result.valid_p = FALSE;
495 switch (tree->type.node_code)
498 if (allocation_done != lang_first_phase_enum)
499 result = new_abs (bfd_sizeof_headers (output_bfd,
500 link_info.relocatable));
503 if (allocation_done == lang_first_phase_enum)
504 lang_track_definedness (tree->name.name);
507 struct bfd_link_hash_entry *h;
509 = lang_symbol_definition_iteration (tree->name.name);
511 h = bfd_wrapped_link_hash_lookup (output_bfd, &link_info,
514 result.value = (h != NULL
515 && (h->type == bfd_link_hash_defined
516 || h->type == bfd_link_hash_defweak
517 || h->type == bfd_link_hash_common)
518 && (def_iteration == lang_statement_iteration
519 || def_iteration == -1));
520 result.section = abs_output_section;
521 result.valid_p = TRUE;
525 if (tree->name.name[0] == '.' && tree->name.name[1] == 0)
527 if (allocation_done != lang_first_phase_enum)
528 result = new_rel_from_section (dot, current_section);
530 else if (allocation_done != lang_first_phase_enum)
532 struct bfd_link_hash_entry *h;
534 h = bfd_wrapped_link_hash_lookup (output_bfd, &link_info,
538 einfo (_("%P%F: bfd_link_hash_lookup failed: %E\n"));
539 else if (h->type == bfd_link_hash_defined
540 || h->type == bfd_link_hash_defweak)
542 if (bfd_is_abs_section (h->u.def.section))
543 result = new_abs (h->u.def.value);
544 else if (allocation_done == lang_final_phase_enum
545 || allocation_done == lang_allocating_phase_enum)
547 asection *output_section;
549 output_section = h->u.def.section->output_section;
550 if (output_section == NULL)
551 einfo (_("%X%S: unresolvable symbol `%s' referenced in expression\n"),
555 lang_output_section_statement_type *os;
557 os = (lang_output_section_statement_lookup
558 (bfd_get_section_name (output_bfd,
561 /* FIXME: Is this correct if this section is
562 being linked with -R? */
563 result = new_rel ((h->u.def.value
564 + h->u.def.section->output_offset),
570 else if (allocation_done == lang_final_phase_enum)
571 einfo (_("%F%S: undefined symbol `%s' referenced in expression\n"),
573 else if (h->type == bfd_link_hash_new)
575 h->type = bfd_link_hash_undefined;
576 h->u.undef.abfd = NULL;
577 if (h->u.undef.next == NULL)
578 bfd_link_add_undef (link_info.hash, h);
584 if (allocation_done != lang_first_phase_enum)
586 lang_output_section_statement_type *os;
588 os = lang_output_section_find (tree->name.name);
589 if (os && os->processed > 0)
590 result = new_rel (0, NULL, os);
595 if (allocation_done != lang_first_phase_enum)
597 lang_output_section_statement_type *os;
599 os = lang_output_section_find (tree->name.name);
600 if (os && os->processed != 0)
602 if (os->load_base == NULL)
603 result = new_rel (0, NULL, os);
605 result = exp_fold_tree_no_dot (os->load_base,
613 if (allocation_done != lang_first_phase_enum)
615 int opb = bfd_octets_per_byte (output_bfd);
616 lang_output_section_statement_type *os;
618 os = lang_output_section_find (tree->name.name);
619 if (os && os->processed > 0)
620 result = new_abs (os->bfd_section->size / opb);
633 exp_fold_tree (etree_type *tree,
634 lang_output_section_statement_type *current_section,
635 lang_phase_type allocation_done,
639 etree_value_type result;
643 result.valid_p = FALSE;
647 switch (tree->type.node_class)
650 result = new_rel (tree->value.value, tree->value.str, current_section);
654 if (allocation_done != lang_final_phase_enum)
655 result.valid_p = FALSE;
657 result = new_rel ((tree->rel.value
658 + tree->rel.section->output_section->vma
659 + tree->rel.section->output_offset),
665 result = exp_fold_tree (tree->assert_s.child,
667 allocation_done, dot, dotp);
671 einfo ("%F%P: %s\n", tree->assert_s.message);
677 result = fold_unary (tree, current_section, allocation_done,
682 result = fold_binary (tree, current_section, allocation_done,
687 result = fold_trinary (tree, current_section, allocation_done,
694 if (tree->assign.dst[0] == '.' && tree->assign.dst[1] == 0)
696 /* Assignment to dot can only be done during allocation. */
697 if (tree->type.node_class != etree_assign)
698 einfo (_("%F%S can not PROVIDE assignment to location counter\n"));
699 if (allocation_done == lang_allocating_phase_enum
700 || (allocation_done == lang_final_phase_enum
701 && current_section == abs_output_section))
703 result = exp_fold_tree (tree->assign.src,
705 allocation_done, dot,
707 if (! result.valid_p)
708 einfo (_("%F%S invalid assignment to location counter\n"));
711 if (current_section == NULL)
712 einfo (_("%F%S assignment to location counter invalid outside of SECTION\n"));
717 nextdot = (result.value
718 + current_section->bfd_section->vma);
720 && current_section != abs_output_section)
721 einfo (_("%F%S cannot move location counter backwards (from %V to %V)\n"),
731 result = exp_fold_tree (tree->assign.src,
732 current_section, allocation_done,
737 struct bfd_link_hash_entry *h;
739 if (tree->type.node_class == etree_assign)
743 h = bfd_link_hash_lookup (link_info.hash, tree->assign.dst,
744 create, FALSE, TRUE);
748 einfo (_("%P%F:%s: hash creation failed\n"),
751 else if (tree->type.node_class == etree_provide
752 && h->type != bfd_link_hash_new
753 && h->type != bfd_link_hash_undefined
754 && h->type != bfd_link_hash_common)
756 /* Do nothing. The symbol was defined by some
761 /* FIXME: Should we worry if the symbol is already
763 lang_update_definedness (tree->assign.dst, h);
764 h->type = bfd_link_hash_defined;
765 h->u.def.value = result.value;
766 h->u.def.section = result.section->bfd_section;
767 if (tree->type.node_class == etree_provide)
768 tree->type.node_class = etree_provided;
775 result = fold_name (tree, current_section, allocation_done, dot);
786 static etree_value_type
787 exp_fold_tree_no_dot (etree_type *tree,
788 lang_output_section_statement_type *current_section,
789 lang_phase_type allocation_done)
791 return exp_fold_tree (tree, current_section, allocation_done, 0, NULL);
795 exp_binop (int code, etree_type *lhs, etree_type *rhs)
797 etree_type value, *new;
800 value.type.node_code = code;
801 value.binary.lhs = lhs;
802 value.binary.rhs = rhs;
803 value.type.node_class = etree_binary;
804 r = exp_fold_tree_no_dot (&value,
806 lang_first_phase_enum);
809 return exp_intop (r.value);
811 new = stat_alloc (sizeof (new->binary));
812 memcpy (new, &value, sizeof (new->binary));
817 exp_trinop (int code, etree_type *cond, etree_type *lhs, etree_type *rhs)
819 etree_type value, *new;
821 value.type.node_code = code;
822 value.trinary.lhs = lhs;
823 value.trinary.cond = cond;
824 value.trinary.rhs = rhs;
825 value.type.node_class = etree_trinary;
826 r = exp_fold_tree_no_dot (&value, NULL, lang_first_phase_enum);
828 return exp_intop (r.value);
830 new = stat_alloc (sizeof (new->trinary));
831 memcpy (new, &value, sizeof (new->trinary));
836 exp_unop (int code, etree_type *child)
838 etree_type value, *new;
841 value.unary.type.node_code = code;
842 value.unary.child = child;
843 value.unary.type.node_class = etree_unary;
844 r = exp_fold_tree_no_dot (&value, abs_output_section,
845 lang_first_phase_enum);
847 return exp_intop (r.value);
849 new = stat_alloc (sizeof (new->unary));
850 memcpy (new, &value, sizeof (new->unary));
855 exp_nameop (int code, const char *name)
857 etree_type value, *new;
859 value.name.type.node_code = code;
860 value.name.name = name;
861 value.name.type.node_class = etree_name;
863 r = exp_fold_tree_no_dot (&value, NULL, lang_first_phase_enum);
865 return exp_intop (r.value);
867 new = stat_alloc (sizeof (new->name));
868 memcpy (new, &value, sizeof (new->name));
874 exp_assop (int code, const char *dst, etree_type *src)
876 etree_type value, *new;
878 value.assign.type.node_code = code;
880 value.assign.src = src;
881 value.assign.dst = dst;
882 value.assign.type.node_class = etree_assign;
885 if (exp_fold_tree_no_dot (&value, &result))
886 return exp_intop (result);
888 new = stat_alloc (sizeof (new->assign));
889 memcpy (new, &value, sizeof (new->assign));
893 /* Handle PROVIDE. */
896 exp_provide (const char *dst, etree_type *src)
900 n = stat_alloc (sizeof (n->assign));
901 n->assign.type.node_code = '=';
902 n->assign.type.node_class = etree_provide;
911 exp_assert (etree_type *exp, const char *message)
915 n = stat_alloc (sizeof (n->assert_s));
916 n->assert_s.type.node_code = '!';
917 n->assert_s.type.node_class = etree_assert;
918 n->assert_s.child = exp;
919 n->assert_s.message = message;
924 exp_print_tree (etree_type *tree)
926 if (config.map_file == NULL)
927 config.map_file = stderr;
931 minfo ("NULL TREE\n");
935 switch (tree->type.node_class)
938 minfo ("0x%v", tree->value.value);
941 if (tree->rel.section->owner != NULL)
942 minfo ("%B:", tree->rel.section->owner);
943 minfo ("%s+0x%v", tree->rel.section->name, tree->rel.value);
947 if (tree->assign.dst->sdefs != NULL)
948 fprintf (config.map_file, "%s (%x) ", tree->assign.dst->name,
949 tree->assign.dst->sdefs->value);
951 fprintf (config.map_file, "%s (UNDEFINED)", tree->assign.dst->name);
953 fprintf (config.map_file, "%s", tree->assign.dst);
954 exp_print_token (tree->type.node_code, TRUE);
955 exp_print_tree (tree->assign.src);
959 fprintf (config.map_file, "PROVIDE (%s, ", tree->assign.dst);
960 exp_print_tree (tree->assign.src);
961 fprintf (config.map_file, ")");
964 fprintf (config.map_file, "(");
965 exp_print_tree (tree->binary.lhs);
966 exp_print_token (tree->type.node_code, TRUE);
967 exp_print_tree (tree->binary.rhs);
968 fprintf (config.map_file, ")");
971 exp_print_tree (tree->trinary.cond);
972 fprintf (config.map_file, "?");
973 exp_print_tree (tree->trinary.lhs);
974 fprintf (config.map_file, ":");
975 exp_print_tree (tree->trinary.rhs);
978 exp_print_token (tree->unary.type.node_code, FALSE);
979 if (tree->unary.child)
981 fprintf (config.map_file, " (");
982 exp_print_tree (tree->unary.child);
983 fprintf (config.map_file, ")");
988 fprintf (config.map_file, "ASSERT (");
989 exp_print_tree (tree->assert_s.child);
990 fprintf (config.map_file, ", %s)", tree->assert_s.message);
994 fprintf (config.map_file, "????????");
997 if (tree->type.node_code == NAME)
999 fprintf (config.map_file, "%s", tree->name.name);
1003 exp_print_token (tree->type.node_code, FALSE);
1004 if (tree->name.name)
1005 fprintf (config.map_file, " (%s)", tree->name.name);
1015 exp_get_vma (etree_type *tree,
1018 lang_phase_type allocation_done)
1024 r = exp_fold_tree_no_dot (tree, abs_output_section, allocation_done);
1025 if (! r.valid_p && name != NULL)
1026 einfo (_("%F%S nonconstant expression for %s\n"), name);
1034 exp_get_value_int (etree_type *tree,
1037 lang_phase_type allocation_done)
1039 return exp_get_vma (tree, def, name, allocation_done);
1043 exp_get_fill (etree_type *tree,
1046 lang_phase_type allocation_done)
1056 r = exp_fold_tree_no_dot (tree, abs_output_section, allocation_done);
1057 if (! r.valid_p && name != NULL)
1058 einfo (_("%F%S nonconstant expression for %s\n"), name);
1060 if (r.str != NULL && (len = strlen (r.str)) != 0)
1064 fill = xmalloc ((len + 1) / 2 + sizeof (*fill) - 1);
1065 fill->size = (len + 1) / 2;
1075 digit = (digit - 'A' + '0' + 10) & 0xf;
1089 fill = xmalloc (4 + sizeof (*fill) - 1);
1091 fill->data[0] = (val >> 24) & 0xff;
1092 fill->data[1] = (val >> 16) & 0xff;
1093 fill->data[2] = (val >> 8) & 0xff;
1094 fill->data[3] = (val >> 0) & 0xff;
1101 exp_get_abs_int (etree_type *tree,
1102 int def ATTRIBUTE_UNUSED,
1104 lang_phase_type allocation_done)
1106 etree_value_type res;
1107 res = exp_fold_tree_no_dot (tree, abs_output_section, allocation_done);
1110 res.value += res.section->bfd_section->vma;
1112 einfo (_("%F%S non constant expression for %s\n"), name);
1118 align_n (bfd_vma value, bfd_vma align)
1123 value = (value + align - 1) / align;
1124 return value * align;