1/*	Id: symtabs.c,v 1.24 2011/07/16 20:34:50 ragge Exp 	*/
2/*	$NetBSD$	*/
3/*
4 * Copyright (c) 2003 Anders Magnusson (ragge@ludd.luth.se).
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. The name of the author may not be used to endorse or promote products
16 *    derived from this software without specific prior written permission
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30
31#include "pass1.h"
32
33/*
34 * These definitions are used in the patricia tree that stores
35 * the strings.
36 */
37#define	LEFT_IS_LEAF		0x80000000
38#define	RIGHT_IS_LEAF		0x40000000
39#define	IS_LEFT_LEAF(x)		(((x) & LEFT_IS_LEAF) != 0)
40#define	IS_RIGHT_LEAF(x)	(((x) & RIGHT_IS_LEAF) != 0)
41#define	BITNO(x)		((x) & ~(LEFT_IS_LEAF|RIGHT_IS_LEAF))
42#define	CHECKBITS		8
43
44struct tree {
45	int bitno;
46	struct tree *lr[2];
47};
48
49static struct tree *firstname;
50int nametabs, namestrlen;
51static struct tree *firststr;
52int strtabs, strstrlen;
53static char *symtab_add(char *key, struct tree **, int *, int *);
54int lastloc = NOSEG;
55
56#define	P_BIT(key, bit) (key[bit >> 3] >> (bit & 7)) & 1
57#define	getree() permalloc(sizeof(struct tree))
58
59char *
60addname(char *key)
61{
62	return symtab_add(key, &firstname, &nametabs, &namestrlen);
63}
64
65char *
66addstring(char *key)
67{
68	return symtab_add(key, &firststr, &strtabs, &strstrlen);
69}
70
71/*
72 * Add a name to the name stack (if its non-existing),
73 * return its address.
74 * This is a simple patricia implementation.
75 */
76char *
77symtab_add(char *key, struct tree **first, int *tabs, int *stlen)
78{
79	struct tree *w, *new, *last;
80	int cix, bit, fbit, svbit, ix, bitno, len;
81	char *m, *k, *sm;
82
83	/* Count full string length */
84	for (k = key, len = 0; *k; k++, len++)
85		;
86
87	switch (*tabs) {
88	case 0:
89		*first = (struct tree *)newstring(key, len);
90		*stlen += (len + 1);
91		(*tabs)++;
92		return (char *)*first;
93
94	case 1:
95		m = (char *)*first;
96		svbit = 0; /* XXX why? */
97		break;
98
99	default:
100		w = *first;
101		bitno = len * CHECKBITS;
102		for (;;) {
103			bit = BITNO(w->bitno);
104			fbit = bit > bitno ? 0 : P_BIT(key, bit);
105			svbit = fbit ? IS_RIGHT_LEAF(w->bitno) :
106			    IS_LEFT_LEAF(w->bitno);
107			w = w->lr[fbit];
108			if (svbit) {
109				m = (char *)w;
110				break;
111			}
112		}
113	}
114
115	sm = m;
116	k = key;
117
118	/* Check for correct string and return */
119	for (cix = 0; *m && *k && *m == *k; m++, k++, cix += CHECKBITS)
120		;
121	if (*m == 0 && *k == 0)
122		return sm;
123
124	ix = *m ^ *k;
125	while ((ix & 1) == 0)
126		ix >>= 1, cix++;
127
128	/* Create new node */
129	new = getree();
130	bit = P_BIT(key, cix);
131	new->bitno = cix | (bit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
132	new->lr[bit] = (struct tree *)newstring(key, len);
133	*stlen += (len + 1);
134
135	if ((*tabs)++ == 1) {
136		new->lr[!bit] = *first;
137		new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
138		*first = new;
139		return (char *)new->lr[bit];
140	}
141
142
143	w = *first;
144	last = NULL;
145	for (;;) {
146		fbit = w->bitno;
147		bitno = BITNO(w->bitno);
148		if (bitno == cix)
149			cerror("bitno == cix");
150		if (bitno > cix)
151			break;
152		svbit = P_BIT(key, bitno);
153		last = w;
154		w = w->lr[svbit];
155		if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
156			break;
157	}
158
159	new->lr[!bit] = w;
160	if (last == NULL) {
161		*first = new;
162	} else {
163		last->lr[svbit] = new;
164		last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
165	}
166	if (bitno < cix)
167		new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
168	return (char *)new->lr[bit];
169}
170
171static struct tree *sympole[NSTYPES];
172static struct symtab *tmpsyms[NSTYPES];
173int numsyms[NSTYPES];
174
175/*
176 * Inserts a symbol into the symbol tree.
177 * Returns a struct symtab.
178 */
179struct symtab *
180lookup(char *key, int stype)
181{
182	struct symtab *sym;
183	struct tree *w, *new, *last;
184	int cix, bit, fbit, svbit, bitno;
185	int type, uselvl;
186	intptr_t ix, match, code = (intptr_t)key;
187
188	type = stype & SMASK;
189	uselvl = (blevel > 0 && type != SSTRING);
190
191	/*
192	 * The local symbols are kept in a simple linked list.
193	 * Check this list first.
194	 */
195	if (blevel > 0)
196		for (sym = tmpsyms[type]; sym; sym = sym->snext)
197			if (sym->sname == key)
198				return sym;
199
200	switch (numsyms[type]) {
201	case 0:
202		if (stype & SNOCREAT)
203			return NULL;
204		if (uselvl) {
205			sym = getsymtab(key, stype|STEMP);
206			sym->snext = tmpsyms[type];
207			tmpsyms[type] = sym;
208			return sym;
209		}
210		sympole[type] = (struct tree *)getsymtab(key, stype);
211		numsyms[type]++;
212		return (struct symtab *)sympole[type];
213
214	case 1:
215		w = (struct tree *)sympole[type];
216		svbit = 0; /* XXX why? */
217		break;
218
219	default:
220		w = sympole[type];
221		for (;;) {
222			bit = BITNO(w->bitno);
223			fbit = (code >> bit) & 1;
224			svbit = fbit ? IS_RIGHT_LEAF(w->bitno) :
225			    IS_LEFT_LEAF(w->bitno);
226			w = w->lr[fbit];
227			if (svbit)
228				break;
229		}
230	}
231
232	sym = (struct symtab *)w;
233	match = (intptr_t)sym->sname;
234
235	ix = code ^ match;
236	if (ix == 0)
237		return sym;
238	else if (stype & SNOCREAT)
239		return NULL;
240
241#ifdef PCC_DEBUG
242	if (ddebug)
243		printf("	adding %s as %s at level %d\n",
244		    key, uselvl ? "temp" : "perm", blevel);
245#endif
246
247	/*
248	 * Insert into the linked list, if feasible.
249	 */
250	if (uselvl) {
251		sym = getsymtab(key, stype|STEMP);
252		sym->snext = tmpsyms[type];
253		tmpsyms[type] = sym;
254		return sym;
255	}
256
257	/*
258	 * Need a new node. If type is SNORMAL and inside a function
259	 * the node must be allocated as permanent anyway.
260	 * This could be optimized by adding a remove routine, but it
261	 * may be more trouble than it is worth.
262	 */
263	if (stype == (STEMP|SNORMAL))
264		stype = SNORMAL;
265
266	for (cix = 0; (ix & 1) == 0; ix >>= 1, cix++)
267		;
268
269	new = stype & STEMP ? tmpalloc(sizeof(struct tree)) :
270	    permalloc(sizeof(struct tree));
271	bit = (code >> cix) & 1;
272	new->bitno = cix | (bit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
273	new->lr[bit] = (struct tree *)getsymtab(key, stype);
274	if (numsyms[type]++ == 1) {
275		new->lr[!bit] = sympole[type];
276		new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
277		sympole[type] = new;
278		return (struct symtab *)new->lr[bit];
279	}
280
281
282	w = sympole[type];
283	last = NULL;
284	for (;;) {
285		fbit = w->bitno;
286		bitno = BITNO(w->bitno);
287		if (bitno == cix)
288			cerror("bitno == cix");
289		if (bitno > cix)
290			break;
291		svbit = (code >> bitno) & 1;
292		last = w;
293		w = w->lr[svbit];
294		if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
295			break;
296	}
297
298	new->lr[!bit] = w;
299	if (last == NULL) {
300		sympole[type] = new;
301	} else {
302		last->lr[svbit] = new;
303		last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
304	}
305	if (bitno < cix)
306		new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
307	return (struct symtab *)new->lr[bit];
308}
309
310void
311symclear(int level)
312{
313	struct symtab *s;
314	int i;
315
316#ifdef PCC_DEBUG
317	if (ddebug)
318		printf("symclear(%d)\n", level);
319#endif
320	if (level < 1) {
321		for (i = 0; i < NSTYPES; i++) {
322			s = tmpsyms[i];
323			tmpsyms[i] = 0;
324			if (i != SLBLNAME)
325				continue;
326			while (s != NULL) {
327				if (s->soffset < 0)
328					uerror("label '%s' undefined",s->sname);
329				s = s->snext;
330			}
331		}
332	} else {
333		for (i = 0; i < NSTYPES; i++) {
334			if (i == SLBLNAME)
335				continue; /* function scope */
336			while (tmpsyms[i] != NULL &&
337			    tmpsyms[i]->slevel > level) {
338				tmpsyms[i] = tmpsyms[i]->snext;
339			}
340		}
341	}
342}
343
344struct symtab *
345hide(struct symtab *sym)
346{
347	struct symtab *new;
348	int typ = sym->sflags & SMASK;
349
350	new = getsymtab(sym->sname, typ|STEMP);
351	new->snext = tmpsyms[typ];
352	tmpsyms[typ] = new;
353
354	warner(Wshadow, sym->sname, sym->slevel ? "local" : "global");
355
356#ifdef PCC_DEBUG
357	if (ddebug)
358		printf("\t%s hidden at level %d (%p -> %p)\n",
359		    sym->sname, blevel, sym, new);
360#endif
361	return new;
362}
363
364/*
365 * Extract correct segment for the specified symbol and call
366 * target routines to print it out.
367 * If symtab entry is specified, output alignment as well.
368 */
369void
370locctr(int seg, struct symtab *sp)
371{
372	struct attr *ga;
373
374	if (seg == NOSEG) {
375		;
376	} else if (sp == NULL) {
377		if (lastloc != seg)
378			setseg(seg, NULL);
379	} else if ((ga = attr_find(sp->sap, GCC_ATYP_SECTION)) != NULL) {
380		setseg(NMSEG, ga->sarg(0));
381		seg = NOSEG;
382	} else {
383		if (seg == DATA) {
384			if (ISCON(cqual(sp->stype, sp->squal)))
385				seg = RDATA;
386			else if (sp->sclass == STATIC)
387				seg = LDATA;
388		}
389		if (sp->sflags & STLS) {
390			if (seg == DATA || seg == LDATA)
391				seg = TLSDATA;
392			if (seg == UDATA) seg = TLSUDATA;
393		} else if (kflag) {
394			if (seg == DATA) seg = PICDATA;
395			if (seg == RDATA) seg = PICRDATA;
396			if (seg == LDATA) seg = PICLDATA;
397		}
398		if (lastloc != seg)
399			setseg(seg, NULL);
400	}
401	lastloc = seg;
402
403	/* setup alignment */
404#ifndef ALFTN
405#define	ALFTN	ALINT
406#endif
407	if (sp) {
408		int al;
409
410		if (ISFTN(sp->stype)) {
411			al = ALFTN;
412		} else
413			al = talign(sp->stype, sp->sap);
414		defalign(al);
415		symdirec(sp);
416	}
417}
418
419#ifndef MYALIGN
420void
421defalign(int al)
422{
423#ifdef	HASP2ALIGN
424#define	P2ALIGN(x)	ispow2(x)
425#else
426#define	P2ALIGN(x)	(x)
427#endif
428	if (al != ALCHAR)
429		printf("\t.align %d\n", P2ALIGN(al/ALCHAR));
430}
431#endif
432
433#ifndef MYDIREC
434/*
435 * Directives given as attributes to symbols.
436 */
437void
438symdirec(struct symtab *sp)
439{
440	struct attr *ga;
441	char *name;
442
443	if ((name = sp->soname) == NULL)
444		name = exname(sp->sname);
445	if ((ga = attr_find(sp->sap, GCC_ATYP_WEAK)) != NULL)
446		printf("\t.weak %s\n", name);
447	if ((ga = attr_find(sp->sap, GCC_ATYP_VISIBILITY)) &&
448	    strcmp(ga->sarg(0), "default"))
449		printf("\t.%s %s\n", ga->sarg(0), name);
450	if ((ga = attr_find(sp->sap, GCC_ATYP_ALIASWEAK))) {
451		printf("\t.weak %s\n", ga->sarg(0));
452		printf("\t.set %s,%s\n", ga->sarg(0), name);
453	}
454}
455#endif
456