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_END
, "DATA_SEGMENT_END" }
108 for (idx
= 0; idx
< ARRAY_SIZE (table
); idx
++)
109 if (table
[idx
].code
== code
)
113 fputc (' ', config
.map_file
);
115 if (idx
< ARRAY_SIZE (table
))
116 fputs (table
[idx
].name
, config
.map_file
);
118 fputc (code
, config
.map_file
);
120 fprintf (config
.map_file
, "<code %d>", code
);
123 fputc (' ', config
.map_file
);
127 make_abs (etree_value_type
*ptr
)
129 asection
*s
= ptr
->section
->bfd_section
;
130 ptr
->value
+= s
->vma
;
131 ptr
->section
= abs_output_section
;
134 static etree_value_type
135 new_abs (bfd_vma value
)
137 etree_value_type
new;
139 new.section
= abs_output_section
;
145 check (lang_output_section_statement_type
*os
,
150 einfo (_("%F%P: %s uses undefined section %s\n"), op
, name
);
152 einfo (_("%F%P: %s forward reference of section %s\n"), op
, name
);
156 exp_intop (bfd_vma value
)
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
;
167 exp_bigintop (bfd_vma value
, char *str
)
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
;
177 /* Build an expression representing an unnamed relocatable value. */
180 exp_relop (asection
*section
, bfd_vma value
)
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
;
190 static etree_value_type
191 new_rel (bfd_vma value
,
193 lang_output_section_statement_type
*section
)
195 etree_value_type
new;
199 new.section
= section
;
203 static etree_value_type
204 new_rel_from_section (bfd_vma value
,
205 lang_output_section_statement_type
*section
)
207 etree_value_type
new;
211 new.section
= section
;
213 new.value
-= section
->bfd_section
->vma
;
218 static etree_value_type
219 fold_unary (etree_type
*tree
,
220 lang_output_section_statement_type
*current_section
,
221 lang_phase_type allocation_done
,
225 etree_value_type result
;
227 result
= exp_fold_tree (tree
->unary
.child
,
229 allocation_done
, dot
, dotp
);
232 switch (tree
->type
.node_code
)
235 if (allocation_done
!= lang_first_phase_enum
)
236 result
= new_rel_from_section (align_n (dot
, result
.value
),
239 result
.valid_p
= FALSE
;
243 if (allocation_done
!= lang_first_phase_enum
)
245 result
.value
+= result
.section
->bfd_section
->vma
;
246 result
.section
= abs_output_section
;
249 result
.valid_p
= FALSE
;
254 result
.value
= ~result
.value
;
259 result
.value
= !result
.value
;
264 result
.value
= -result
.value
;
268 /* Return next place aligned to value. */
269 if (allocation_done
== lang_allocating_phase_enum
)
272 result
.value
= align_n (dot
, result
.value
);
275 result
.valid_p
= FALSE
;
278 case DATA_SEGMENT_END
:
279 if (allocation_done
!= lang_first_phase_enum
280 && current_section
== abs_output_section
281 && (exp_data_seg
.phase
== exp_dataseg_align_seen
282 || exp_data_seg
.phase
== exp_dataseg_adjust
283 || allocation_done
!= lang_allocating_phase_enum
))
285 if (exp_data_seg
.phase
== exp_dataseg_align_seen
)
287 exp_data_seg
.phase
= exp_dataseg_end_seen
;
288 exp_data_seg
.end
= result
.value
;
292 result
.valid_p
= FALSE
;
304 static etree_value_type
305 fold_binary (etree_type
*tree
,
306 lang_output_section_statement_type
*current_section
,
307 lang_phase_type allocation_done
,
311 etree_value_type result
;
313 result
= exp_fold_tree (tree
->binary
.lhs
, current_section
,
314 allocation_done
, dot
, dotp
);
317 etree_value_type other
;
319 other
= exp_fold_tree (tree
->binary
.rhs
,
321 allocation_done
, dot
, dotp
);
324 /* If the values are from different sections, or this is an
325 absolute expression, make both the source arguments
326 absolute. However, adding or subtracting an absolute
327 value from a relative value is meaningful, and is an
329 if (current_section
!= abs_output_section
330 && (other
.section
== abs_output_section
331 || (result
.section
== abs_output_section
332 && tree
->type
.node_code
== '+'))
333 && (tree
->type
.node_code
== '+'
334 || tree
->type
.node_code
== '-'))
336 if (other
.section
!= abs_output_section
)
338 /* Keep the section of the other term. */
339 if (tree
->type
.node_code
== '+')
340 other
.value
= result
.value
+ other
.value
;
342 other
.value
= result
.value
- other
.value
;
346 else if (result
.section
!= other
.section
347 || current_section
== abs_output_section
)
353 switch (tree
->type
.node_code
)
356 if (other
.value
== 0)
357 einfo (_("%F%S %% by zero\n"));
358 result
.value
= ((bfd_signed_vma
) result
.value
359 % (bfd_signed_vma
) other
.value
);
363 if (other
.value
== 0)
364 einfo (_("%F%S / by zero\n"));
365 result
.value
= ((bfd_signed_vma
) result
.value
366 / (bfd_signed_vma
) other
.value
);
369 #define BOP(x,y) case x : result.value = result.value y other.value; break;
388 if (result
.value
< other
.value
)
393 if (result
.value
> other
.value
)
398 result
.value
= align_n (result
.value
, other
.value
);
401 case DATA_SEGMENT_ALIGN
:
402 if (allocation_done
!= lang_first_phase_enum
403 && current_section
== abs_output_section
404 && (exp_data_seg
.phase
== exp_dataseg_none
405 || exp_data_seg
.phase
== exp_dataseg_adjust
406 || allocation_done
!= lang_allocating_phase_enum
))
408 bfd_vma maxpage
= result
.value
;
410 result
.value
= align_n (dot
, maxpage
);
411 if (exp_data_seg
.phase
!= exp_dataseg_adjust
)
413 result
.value
+= dot
& (maxpage
- 1);
414 if (allocation_done
== lang_allocating_phase_enum
)
416 exp_data_seg
.phase
= exp_dataseg_align_seen
;
417 exp_data_seg
.base
= result
.value
;
418 exp_data_seg
.pagesize
= other
.value
;
421 else if (other
.value
< maxpage
)
422 result
.value
+= (dot
+ other
.value
- 1)
423 & (maxpage
- other
.value
);
426 result
.valid_p
= FALSE
;
435 result
.valid_p
= FALSE
;
442 static etree_value_type
443 fold_trinary (etree_type
*tree
,
444 lang_output_section_statement_type
*current_section
,
445 lang_phase_type allocation_done
,
449 etree_value_type result
;
451 result
= exp_fold_tree (tree
->trinary
.cond
, current_section
,
452 allocation_done
, dot
, dotp
);
454 result
= exp_fold_tree ((result
.value
456 : tree
->trinary
.rhs
),
458 allocation_done
, dot
, dotp
);
466 etree_value_type
new;
471 static etree_value_type
472 fold_name (etree_type
*tree
,
473 lang_output_section_statement_type
*current_section
,
474 lang_phase_type allocation_done
,
477 etree_value_type result
;
479 switch (tree
->type
.node_code
)
482 if (allocation_done
!= lang_first_phase_enum
)
484 result
= new_abs (bfd_sizeof_headers (output_bfd
,
485 link_info
.relocatable
));
489 result
.valid_p
= FALSE
;
493 if (allocation_done
== lang_first_phase_enum
)
495 lang_track_definedness (tree
->name
.name
);
496 result
.valid_p
= FALSE
;
500 struct bfd_link_hash_entry
*h
;
502 = lang_symbol_definition_iteration (tree
->name
.name
);
504 h
= bfd_wrapped_link_hash_lookup (output_bfd
, &link_info
,
507 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 result
.section
= abs_output_section
;
514 result
.valid_p
= TRUE
;
518 result
.valid_p
= FALSE
;
519 if (tree
->name
.name
[0] == '.' && tree
->name
.name
[1] == 0)
521 if (allocation_done
!= lang_first_phase_enum
)
522 result
= new_rel_from_section (dot
, current_section
);
526 else if (allocation_done
!= lang_first_phase_enum
)
528 struct bfd_link_hash_entry
*h
;
530 h
= bfd_wrapped_link_hash_lookup (output_bfd
, &link_info
,
534 && (h
->type
== bfd_link_hash_defined
535 || h
->type
== bfd_link_hash_defweak
))
537 if (bfd_is_abs_section (h
->u
.def
.section
))
538 result
= new_abs (h
->u
.def
.value
);
539 else if (allocation_done
== lang_final_phase_enum
540 || allocation_done
== lang_allocating_phase_enum
)
542 asection
*output_section
;
544 output_section
= h
->u
.def
.section
->output_section
;
545 if (output_section
== NULL
)
546 einfo (_("%X%S: unresolvable symbol `%s' referenced in expression\n"),
550 lang_output_section_statement_type
*os
;
552 os
= (lang_output_section_statement_lookup
553 (bfd_get_section_name (output_bfd
,
556 /* FIXME: Is this correct if this section is
557 being linked with -R? */
558 result
= new_rel ((h
->u
.def
.value
559 + h
->u
.def
.section
->output_offset
),
565 else if (allocation_done
== lang_final_phase_enum
)
566 einfo (_("%F%S: undefined symbol `%s' referenced in expression\n"),
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
, "ADDR");
578 result
= new_rel (0, NULL
, os
);
585 if (allocation_done
!= lang_first_phase_enum
)
587 lang_output_section_statement_type
*os
;
589 os
= lang_output_section_find (tree
->name
.name
);
590 check (os
, tree
->name
.name
, "LOADADDR");
591 if (os
->load_base
== NULL
)
592 result
= new_rel (0, NULL
, os
);
594 result
= exp_fold_tree_no_dot (os
->load_base
,
603 if (allocation_done
!= lang_first_phase_enum
)
605 int opb
= bfd_octets_per_byte (output_bfd
);
606 lang_output_section_statement_type
*os
;
608 os
= lang_output_section_find (tree
->name
.name
);
609 check (os
, tree
->name
.name
, "SIZEOF");
610 result
= new_abs (os
->bfd_section
->_raw_size
/ opb
);
625 exp_fold_tree (etree_type
*tree
,
626 lang_output_section_statement_type
*current_section
,
627 lang_phase_type allocation_done
,
631 etree_value_type result
;
635 result
.valid_p
= FALSE
;
639 switch (tree
->type
.node_class
)
642 result
= new_rel (tree
->value
.value
, tree
->value
.str
, current_section
);
646 if (allocation_done
!= lang_final_phase_enum
)
647 result
.valid_p
= FALSE
;
649 result
= new_rel ((tree
->rel
.value
650 + tree
->rel
.section
->output_section
->vma
651 + tree
->rel
.section
->output_offset
),
657 result
= exp_fold_tree (tree
->assert_s
.child
,
659 allocation_done
, dot
, dotp
);
663 einfo ("%F%P: %s\n", tree
->assert_s
.message
);
669 result
= fold_unary (tree
, current_section
, allocation_done
,
674 result
= fold_binary (tree
, current_section
, allocation_done
,
679 result
= fold_trinary (tree
, current_section
, allocation_done
,
686 if (tree
->assign
.dst
[0] == '.' && tree
->assign
.dst
[1] == 0)
688 /* Assignment to dot can only be done during allocation. */
689 if (tree
->type
.node_class
!= etree_assign
)
690 einfo (_("%F%S can not PROVIDE assignment to location counter\n"));
691 if (allocation_done
== lang_allocating_phase_enum
692 || (allocation_done
== lang_final_phase_enum
693 && current_section
== abs_output_section
))
695 result
= exp_fold_tree (tree
->assign
.src
,
697 allocation_done
, dot
,
699 if (! result
.valid_p
)
700 einfo (_("%F%S invalid assignment to location counter\n"));
703 if (current_section
== NULL
)
704 einfo (_("%F%S assignment to location counter invalid outside of SECTION\n"));
709 nextdot
= (result
.value
710 + current_section
->bfd_section
->vma
);
712 && current_section
!= abs_output_section
)
713 einfo (_("%F%S cannot move location counter backwards (from %V to %V)\n"),
723 result
= exp_fold_tree (tree
->assign
.src
,
724 current_section
, allocation_done
,
729 struct bfd_link_hash_entry
*h
;
731 if (tree
->type
.node_class
== etree_assign
)
735 h
= bfd_link_hash_lookup (link_info
.hash
, tree
->assign
.dst
,
736 create
, FALSE
, FALSE
);
739 if (tree
->type
.node_class
== etree_assign
)
740 einfo (_("%P%F:%s: hash creation failed\n"),
743 else if (tree
->type
.node_class
== etree_provide
744 && h
->type
!= bfd_link_hash_undefined
745 && h
->type
!= bfd_link_hash_common
)
747 /* Do nothing. The symbol was defined by some
752 /* FIXME: Should we worry if the symbol is already
754 lang_update_definedness (tree
->assign
.dst
, h
);
755 h
->type
= bfd_link_hash_defined
;
756 h
->u
.def
.value
= result
.value
;
757 h
->u
.def
.section
= result
.section
->bfd_section
;
758 if (tree
->type
.node_class
== etree_provide
)
759 tree
->type
.node_class
= etree_provided
;
766 result
= fold_name (tree
, current_section
, allocation_done
, dot
);
777 static etree_value_type
778 exp_fold_tree_no_dot (etree_type
*tree
,
779 lang_output_section_statement_type
*current_section
,
780 lang_phase_type allocation_done
)
782 return exp_fold_tree (tree
, current_section
, allocation_done
, 0, NULL
);
786 exp_binop (int code
, etree_type
*lhs
, etree_type
*rhs
)
788 etree_type value
, *new;
791 value
.type
.node_code
= code
;
792 value
.binary
.lhs
= lhs
;
793 value
.binary
.rhs
= rhs
;
794 value
.type
.node_class
= etree_binary
;
795 r
= exp_fold_tree_no_dot (&value
,
797 lang_first_phase_enum
);
800 return exp_intop (r
.value
);
802 new = stat_alloc (sizeof (new->binary
));
803 memcpy (new, &value
, sizeof (new->binary
));
808 exp_trinop (int code
, etree_type
*cond
, etree_type
*lhs
, etree_type
*rhs
)
810 etree_type value
, *new;
812 value
.type
.node_code
= code
;
813 value
.trinary
.lhs
= lhs
;
814 value
.trinary
.cond
= cond
;
815 value
.trinary
.rhs
= rhs
;
816 value
.type
.node_class
= etree_trinary
;
817 r
= exp_fold_tree_no_dot (&value
, NULL
, lang_first_phase_enum
);
819 return exp_intop (r
.value
);
821 new = stat_alloc (sizeof (new->trinary
));
822 memcpy (new, &value
, sizeof (new->trinary
));
827 exp_unop (int code
, etree_type
*child
)
829 etree_type value
, *new;
832 value
.unary
.type
.node_code
= code
;
833 value
.unary
.child
= child
;
834 value
.unary
.type
.node_class
= etree_unary
;
835 r
= exp_fold_tree_no_dot (&value
, abs_output_section
,
836 lang_first_phase_enum
);
838 return exp_intop (r
.value
);
840 new = stat_alloc (sizeof (new->unary
));
841 memcpy (new, &value
, sizeof (new->unary
));
846 exp_nameop (int code
, const char *name
)
848 etree_type value
, *new;
850 value
.name
.type
.node_code
= code
;
851 value
.name
.name
= name
;
852 value
.name
.type
.node_class
= etree_name
;
854 r
= exp_fold_tree_no_dot (&value
, NULL
, lang_first_phase_enum
);
856 return exp_intop (r
.value
);
858 new = stat_alloc (sizeof (new->name
));
859 memcpy (new, &value
, sizeof (new->name
));
865 exp_assop (int code
, const char *dst
, etree_type
*src
)
867 etree_type value
, *new;
869 value
.assign
.type
.node_code
= code
;
871 value
.assign
.src
= src
;
872 value
.assign
.dst
= dst
;
873 value
.assign
.type
.node_class
= etree_assign
;
876 if (exp_fold_tree_no_dot (&value
, &result
))
877 return exp_intop (result
);
879 new = stat_alloc (sizeof (new->assign
));
880 memcpy (new, &value
, sizeof (new->assign
));
884 /* Handle PROVIDE. */
887 exp_provide (const char *dst
, etree_type
*src
)
891 n
= stat_alloc (sizeof (n
->assign
));
892 n
->assign
.type
.node_code
= '=';
893 n
->assign
.type
.node_class
= etree_provide
;
902 exp_assert (etree_type
*exp
, const char *message
)
906 n
= stat_alloc (sizeof (n
->assert_s
));
907 n
->assert_s
.type
.node_code
= '!';
908 n
->assert_s
.type
.node_class
= etree_assert
;
909 n
->assert_s
.child
= exp
;
910 n
->assert_s
.message
= message
;
915 exp_print_tree (etree_type
*tree
)
917 if (config
.map_file
== NULL
)
918 config
.map_file
= stderr
;
922 minfo ("NULL TREE\n");
926 switch (tree
->type
.node_class
)
929 minfo ("0x%v", tree
->value
.value
);
932 if (tree
->rel
.section
->owner
!= NULL
)
933 minfo ("%B:", tree
->rel
.section
->owner
);
934 minfo ("%s+0x%v", tree
->rel
.section
->name
, tree
->rel
.value
);
938 if (tree
->assign
.dst
->sdefs
!= NULL
)
939 fprintf (config
.map_file
, "%s (%x) ", tree
->assign
.dst
->name
,
940 tree
->assign
.dst
->sdefs
->value
);
942 fprintf (config
.map_file
, "%s (UNDEFINED)", tree
->assign
.dst
->name
);
944 fprintf (config
.map_file
, "%s", tree
->assign
.dst
);
945 exp_print_token (tree
->type
.node_code
, TRUE
);
946 exp_print_tree (tree
->assign
.src
);
950 fprintf (config
.map_file
, "PROVIDE (%s, ", tree
->assign
.dst
);
951 exp_print_tree (tree
->assign
.src
);
952 fprintf (config
.map_file
, ")");
955 fprintf (config
.map_file
, "(");
956 exp_print_tree (tree
->binary
.lhs
);
957 exp_print_token (tree
->type
.node_code
, TRUE
);
958 exp_print_tree (tree
->binary
.rhs
);
959 fprintf (config
.map_file
, ")");
962 exp_print_tree (tree
->trinary
.cond
);
963 fprintf (config
.map_file
, "?");
964 exp_print_tree (tree
->trinary
.lhs
);
965 fprintf (config
.map_file
, ":");
966 exp_print_tree (tree
->trinary
.rhs
);
969 exp_print_token (tree
->unary
.type
.node_code
, FALSE
);
970 if (tree
->unary
.child
)
972 fprintf (config
.map_file
, " (");
973 exp_print_tree (tree
->unary
.child
);
974 fprintf (config
.map_file
, ")");
979 fprintf (config
.map_file
, "ASSERT (");
980 exp_print_tree (tree
->assert_s
.child
);
981 fprintf (config
.map_file
, ", %s)", tree
->assert_s
.message
);
985 fprintf (config
.map_file
, "????????");
988 if (tree
->type
.node_code
== NAME
)
990 fprintf (config
.map_file
, "%s", tree
->name
.name
);
994 exp_print_token (tree
->type
.node_code
, FALSE
);
996 fprintf (config
.map_file
, " (%s)", tree
->name
.name
);
1006 exp_get_vma (etree_type
*tree
,
1009 lang_phase_type allocation_done
)
1015 r
= exp_fold_tree_no_dot (tree
, abs_output_section
, allocation_done
);
1016 if (! r
.valid_p
&& name
!= NULL
)
1017 einfo (_("%F%S nonconstant expression for %s\n"), name
);
1025 exp_get_value_int (etree_type
*tree
,
1028 lang_phase_type allocation_done
)
1030 return exp_get_vma (tree
, def
, name
, allocation_done
);
1034 exp_get_fill (etree_type
*tree
,
1037 lang_phase_type allocation_done
)
1047 r
= exp_fold_tree_no_dot (tree
, abs_output_section
, allocation_done
);
1048 if (! r
.valid_p
&& name
!= NULL
)
1049 einfo (_("%F%S nonconstant expression for %s\n"), name
);
1051 if (r
.str
!= NULL
&& (len
= strlen (r
.str
)) != 0)
1055 fill
= xmalloc ((len
+ 1) / 2 + sizeof (*fill
) - 1);
1056 fill
->size
= (len
+ 1) / 2;
1066 digit
= (digit
- 'A' + '0' + 10) & 0xf;
1080 fill
= xmalloc (4 + sizeof (*fill
) - 1);
1082 fill
->data
[0] = (val
>> 24) & 0xff;
1083 fill
->data
[1] = (val
>> 16) & 0xff;
1084 fill
->data
[2] = (val
>> 8) & 0xff;
1085 fill
->data
[3] = (val
>> 0) & 0xff;
1092 exp_get_abs_int (etree_type
*tree
,
1093 int def ATTRIBUTE_UNUSED
,
1095 lang_phase_type allocation_done
)
1097 etree_value_type res
;
1098 res
= exp_fold_tree_no_dot (tree
, abs_output_section
, allocation_done
);
1101 res
.value
+= res
.section
->bfd_section
->vma
;
1103 einfo (_("%F%S non constant expression for %s\n"), name
);
1109 align_n (bfd_vma value
, bfd_vma align
)
1114 value
= (value
+ align
- 1) / align
;
1115 return value
* align
;