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