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