comparison keiko/symtab.c @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:bfdcc3820b32
1 /*
2 * symtab.c
3 *
4 * This file is part of the Oxford Oberon-2 compiler
5 * Copyright (c) 2006--2016 J. M. Spivey
6 * All rights reserved
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright notice,
12 * this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright notice,
14 * this list of conditions and the following disclaimer in the documentation
15 * and/or other materials provided with the distribution.
16 * 3. The name of the author may not be used to endorse or promote products
17 * derived from this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
25 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
27 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
28 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31 #include "oblink.h"
32
33 /* This module implements two completely independent symbol tables:
34 one for global symbols, and another for labels used in branches.
35 Global symbols have symbolic names, and are used only in the data
36 segment. Labels have names that are integers. */
37
38
39 /* GLOBAL SYMBOLS */
40
41 struct _symbol {
42 const char *s_name; /* Name of the symbol */
43 segment s_seg; /* Segment, or UNDEFINED */
44 int s_kind; /* Kind of symbol -- X_PROC, etc. */
45 int s_value; /* Numeric value */
46 unsigned s_index; /* Index as a local label */
47 unsigned s_check; /* Checksum for module */
48 int s_nlines; /* Line count for module */
49 symbol s_next; /* Next in hash chain */
50 int s_uchain; /* Start of use chain in data segment */
51 char *s_file; /* Source file that uses the symbol */
52 };
53
54 #define HSIZE 1024
55
56 static symbol stable[HSIZE];
57
58 static growdecl(dict);
59 #define dict growbuf(dict, symbol)
60 #define ndict growsize(dict)
61
62 /* make_symbol -- create a symbol, but don't put it in the hash table */
63 symbol make_symbol(const char *name) {
64 symbol s =
65 (symbol) must_alloc(sizeof(struct _symbol), "symbol table entry");
66 s->s_name = must_strdup(name);
67 s->s_seg = UNDEFINED;
68 s->s_kind = X_NONE;
69 s->s_value = -1;
70 s->s_next = NULL;
71 s->s_index = 0;
72 s->s_uchain = -1;
73 s->s_check = s->s_nlines = 0;
74 s->s_file = NULL;
75
76 buf_grow(dict);
77 dict[ndict++] = s;
78 return s;
79 }
80
81 static symbol lookup(const char *name, mybool create) {
82 if (dict == NULL)
83 buf_init(dict, INIT_SMEM, 1, symbol, "symbol table");
84
85 unsigned h = 0;
86 for (const char *p = name; *p != '\0'; p++) h = 5 * h + *p;
87 h %= HSIZE;
88
89 symbol s;
90 for (s = stable[h]; s != NULL; s = s->s_next)
91 if (strcmp(name, s->s_name) == 0)
92 return s;
93
94 if (create) {
95 s = make_symbol(name);
96 s->s_next = stable[h];
97 stable[h] = s;
98 }
99
100 return s;
101 }
102
103 /* find_symbol -- find a global symbol, or create one if necessary */
104 symbol find_symbol(const char *name) {
105 return lookup(name, TRUE);
106 }
107
108 /* known -- test if a symbol has been entered */
109 mybool known(const char *name) {
110 symbol s = lookup(name, FALSE);
111 return (s != NULL);
112 }
113
114 const char *sym_name(symbol s) {
115 return s->s_name;
116 }
117
118 /* sym_value -- compute value of global symbol */
119 int sym_value(symbol s) {
120 if (s->s_file == NULL) s->s_file = err_file;
121
122 if (s->s_seg == UNDEFINED) {
123 err_file = s->s_file;
124 error("undefined symbol %s", s->s_name);
125 s->s_seg = ABS;
126 }
127
128 return s->s_value;
129 }
130
131 #ifdef DEBUG
132 static const char *seg_name[] = {
133 "abs", "data", "bss", "code", "undefined"
134 };
135 #endif
136
137 /* def_global -- set value of a global symbol */
138 void def_global(symbol s, segment seg, int off, int kind) {
139 if (s->s_seg != UNDEFINED)
140 error("multiply defined symbol %s", s->s_name);
141
142 s->s_seg = seg;
143 s->s_value = off;
144 s->s_kind = kind;
145
146 #ifdef DEBUG
147 if (dflag)
148 fprintf(stderr, "Symbol %s = %d(%s)\n",
149 s->s_name, s->s_value, seg_name[s->s_seg]);
150 #endif
151 }
152
153 /* Uses of globals are linked in chains, so the values can be patched at
154 the last minute before the data segment is output. Because the buffer for
155 the data segment may grow and be relocated, we must store the links as
156 offsets from the start of the buffer. */
157
158 /* use_global -- add location to use chain for a global symbol */
159 void use_global(symbol s, uchar *base, int offset) {
160 if (s->s_file == NULL) s->s_file = err_file;
161 *((int *) &base[offset]) = s->s_uchain;
162 s->s_uchain = offset;
163 }
164
165 /* fix_data -- fix up global refs in the data segment */
166 void fix_data(uchar *base, int bss) {
167 /* Shift BSS symbols by offset bss */
168 for (int i = 0; i < ndict; i++) {
169 symbol s = dict[i];
170 if (s->s_seg == BSS) s->s_value += bss;
171 }
172
173 /* Fix up each symbol */
174 for (int i = 0; i < ndict; i++) {
175 symbol s = dict[i];
176 int val;
177
178 if (s->s_uchain == -1) continue;
179
180 if (dflag > 0) printf("Fixing %s\n", s->s_name);
181
182 val = sym_value(s);
183
184 /* Run along the use chain, inserting the value */
185 for (int u = s->s_uchain, v; u != -1; u = v) {
186 v = *((int *) &base[u]);
187 put4(&base[u], val);
188 relocate(u, (s->s_seg == ABS ? R_WORD : R_DATA));
189 }
190 }
191 }
192
193 /* module_data -- add data for module */
194 void module_data(symbol s, unsigned checksum, int nlines) {
195 s->s_check = checksum;
196 s->s_nlines = nlines;
197 }
198
199 static int cf_syms(symbol *a, symbol *b) {
200 int z = (*a)->s_kind - (*b)->s_kind;
201 if (z == 0) z = (*a)->s_value - (*b)->s_value;
202 return z;
203 }
204
205 /* write_symtab -- write the symbol table */
206 int write_symtab(void) {
207 int nwritten = 0;
208
209 qsort(dict, ndict, sizeof(symbol),
210 (int (*)(const void *, const void *)) cf_syms);
211
212 for (int i = 0; i < ndict; i++) {
213 symbol s = dict[i];
214
215 if (s->s_kind == X_SYM || s->s_kind == X_NONE) continue;
216
217 write_int(4, s->s_kind);
218 write_string(s->s_name);
219 write_int(4, s->s_value);
220
221 if (s->s_kind == X_MODULE) {
222 write_int(4, s->s_check);
223 write_int(4, s->s_nlines);
224 }
225
226 nwritten++;
227 }
228
229 return nwritten;
230 }
231
232
233 /* LOCAL LABELS */
234
235 /* The table contains local symbols for the current procedure only.
236 As the procedure is initially assembled into the linker's buffer,
237 the value of each label is defined as its location in the buffer.
238 When the procedure is complete, we replace each use of a
239 label by the corresponding value. The values are turned into
240 offsets as the code is output. */
241
242 struct _locdef {
243 symbol l_lab;
244 phrase l_val;
245 };
246
247 static growdecl(locdefs);
248 #define locdefs growbuf(locdefs, struct _locdef)
249 #define n_locs growsize(locdefs)
250
251 void init_labels(void) {
252 if (locdefs == NULL)
253 buf_init(locdefs, INIT_LMEM, 1, struct _locdef, "labels");
254 n_locs = 0;
255 }
256
257 int make_label(symbol s) {
258 int n = s->s_index;
259
260 if (s->s_index >= n_locs || locdefs[s->s_index].l_lab != s) {
261 buf_grow(locdefs);
262 n = n_locs++;
263 locdefs[n].l_lab = s;
264 locdefs[n].l_val = NULL;
265 s->s_index = n;
266 }
267
268 return n;
269 }
270
271 const char *label_name(int n) {
272 return sym_name(locdefs[n].l_lab);
273 }
274
275 void def_label(symbol s, phrase val) {
276 int n = make_label(s);
277 if (locdefs[n].l_val != NULL)
278 error("multiply defined label %s", s->s_name);
279 locdefs[n].l_val = val;
280 }
281
282 phrase find_label(int n) {
283 phrase val = locdefs[n].l_val;
284 if (val == NULL)
285 error("undefined label %s", locdefs[n].l_lab->s_name);
286 return val;
287 }