1 /* Id: symtabs.c,v 1.38 2015/09/15 20:01:10 ragge Exp */
2 /* $NetBSD: symtabs.c,v 1.1.1.5 2016/02/09 20:28:53 plunky Exp $ */
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 #include "unicode.h"
33 #include <stdlib.h>
34
35 #define NODE P1ND
36 #define fwalk p1fwalk
37
38 /*
39 * These definitions are used in the patricia tree that stores
40 * the strings.
41 */
42 #define LEFT_IS_LEAF 0x80000000
43 #define RIGHT_IS_LEAF 0x40000000
44 #define IS_LEFT_LEAF(x) (((x) & LEFT_IS_LEAF) != 0)
45 #define IS_RIGHT_LEAF(x) (((x) & RIGHT_IS_LEAF) != 0)
46 #define BITNO(x) ((x) & ~(LEFT_IS_LEAF|RIGHT_IS_LEAF))
47 #define CHECKBITS 8
48
49 struct tree {
50 int bitno;
51 struct tree *lr[2];
52 };
53
54 extern int dimfuncnt;
55 static struct tree *firstname;
56 int nametabs, namestrlen;
57 static struct tree *firststr;
58 int strtabs, strstrlen, symtreecnt;
59 static char *symtab_add(char *key, struct tree **, int *, int *);
60 int lastloc = NOSEG;
61 int treestrsz = sizeof(struct tree);
62
63 #define P_BIT(key, bit) (key[bit >> 3] >> (bit & 7)) & 1
64 #define getree() permalloc(sizeof(struct tree))
65
66 char *
addname(char * key)67 addname(char *key)
68 {
69 return symtab_add(key, &firstname, &nametabs, &namestrlen);
70 }
71
72 char *
addstring(char * key)73 addstring(char *key)
74 {
75 return symtab_add(key, &firststr, &strtabs, &strstrlen);
76 }
77
78 /*
79 * Add a name to the name stack (if its non-existing),
80 * return its address.
81 * This is a simple patricia implementation.
82 */
83 static char *
symtab_add(char * key,struct tree ** first,int * tabs,int * stlen)84 symtab_add(char *key, struct tree **first, int *tabs, int *stlen)
85 {
86 struct tree *w, *new, *last;
87 int cix, bit, fbit, svbit, ix, bitno, len;
88 char *m, *k, *sm;
89
90 /* Count full string length */
91 for (k = key, len = 0; *k; k++, len++)
92 ;
93
94 switch (*tabs) {
95 case 0:
96 *first = (struct tree *)newstring(key, len);
97 *stlen += (len + 1);
98 (*tabs)++;
99 return (char *)*first;
100
101 case 1:
102 m = (char *)*first;
103 svbit = 0; /* XXX why? */
104 break;
105
106 default:
107 w = *first;
108 bitno = len * CHECKBITS;
109 for (;;) {
110 bit = BITNO(w->bitno);
111 fbit = bit > bitno ? 0 : P_BIT(key, bit);
112 svbit = fbit ? IS_RIGHT_LEAF(w->bitno) :
113 IS_LEFT_LEAF(w->bitno);
114 w = w->lr[fbit];
115 if (svbit) {
116 m = (char *)w;
117 break;
118 }
119 }
120 }
121
122 sm = m;
123 k = key;
124
125 /* Check for correct string and return */
126 for (cix = 0; *m && *k && *m == *k; m++, k++, cix += CHECKBITS)
127 ;
128 if (*m == 0 && *k == 0)
129 return sm;
130
131 ix = *m ^ *k;
132 while ((ix & 1) == 0)
133 ix >>= 1, cix++;
134
135 /* Create new node */
136 new = getree();
137 bit = P_BIT(key, cix);
138 new->bitno = cix | (bit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
139 new->lr[bit] = (struct tree *)newstring(key, len);
140 *stlen += (len + 1);
141
142 if ((*tabs)++ == 1) {
143 new->lr[!bit] = *first;
144 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
145 *first = new;
146 return (char *)new->lr[bit];
147 }
148
149
150 w = *first;
151 last = NULL;
152 for (;;) {
153 fbit = w->bitno;
154 bitno = BITNO(w->bitno);
155 if (bitno == cix)
156 cerror("bitno == cix");
157 if (bitno > cix)
158 break;
159 svbit = P_BIT(key, bitno);
160 last = w;
161 w = w->lr[svbit];
162 if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
163 break;
164 }
165
166 new->lr[!bit] = w;
167 if (last == NULL) {
168 *first = new;
169 } else {
170 last->lr[svbit] = new;
171 last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
172 }
173 if (bitno < cix)
174 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
175 return (char *)new->lr[bit];
176 }
177
178 static struct tree *sympole[NSTYPES];
179 static struct symtab *tmpsyms[NSTYPES];
180 int numsyms[NSTYPES];
181
182 /*
183 * Inserts a symbol into the symbol tree.
184 * Returns a struct symtab.
185 */
186 struct symtab *
lookup(char * key,int stype)187 lookup(char *key, int stype)
188 {
189 struct symtab *sym;
190 struct tree *w, *new, *last;
191 int cix, bit, fbit, svbit, bitno;
192 int type, uselvl;
193 intptr_t ix, match, code = (intptr_t)key;
194
195 type = stype & SMASK;
196 uselvl = (blevel > 0 && type != SSTRING);
197
198 /*
199 * The local symbols are kept in a simple linked list.
200 * Check this list first.
201 */
202 if (blevel > 0)
203 for (sym = tmpsyms[type]; sym; sym = sym->snext)
204 if (sym->sname == key)
205 return sym;
206
207 switch (numsyms[type]) {
208 case 0:
209 if (stype & SNOCREAT)
210 return NULL;
211 if (uselvl) {
212 if (type == SNORMAL)
213 stype |= SBLK;
214 sym = getsymtab(key, stype);
215 sym->snext = tmpsyms[type];
216 tmpsyms[type] = sym;
217 return sym;
218 }
219 sympole[type] = (struct tree *)getsymtab(key, stype);
220 numsyms[type]++;
221 return (struct symtab *)sympole[type];
222
223 case 1:
224 w = (struct tree *)sympole[type];
225 svbit = 0; /* XXX why? */
226 break;
227
228 default:
229 w = sympole[type];
230 for (;;) {
231 bit = BITNO(w->bitno);
232 fbit = (code >> bit) & 1;
233 svbit = fbit ? IS_RIGHT_LEAF(w->bitno) :
234 IS_LEFT_LEAF(w->bitno);
235 w = w->lr[fbit];
236 if (svbit)
237 break;
238 }
239 }
240
241 sym = (struct symtab *)w;
242 match = (intptr_t)sym->sname;
243
244 ix = code ^ match;
245 if (ix == 0)
246 return sym;
247 else if (stype & SNOCREAT)
248 return NULL;
249
250 #ifdef PCC_DEBUG
251 if (ddebug)
252 printf(" adding %s as %s at level %d\n",
253 key, uselvl ? "temp" : "perm", blevel);
254 #endif
255
256 /*
257 * Insert into the linked list, if feasible.
258 */
259 if (uselvl) {
260 sym = getsymtab(key, stype|STEMP);
261 sym->snext = tmpsyms[type];
262 tmpsyms[type] = sym;
263 return sym;
264 }
265
266 /*
267 * Need a new node. If type is SNORMAL and inside a function
268 * the node must be allocated as permanent anyway.
269 * This could be optimized by adding a remove routine, but it
270 * may be more trouble than it is worth.
271 */
272 if (stype == (STEMP|SNORMAL))
273 stype = SNORMAL;
274
275 for (cix = 0; (ix & 1) == 0; ix >>= 1, cix++)
276 ;
277
278 new = (symtreecnt++, permalloc(sizeof(struct tree)));
279 bit = (code >> cix) & 1;
280 new->bitno = cix | (bit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
281 new->lr[bit] = (struct tree *)getsymtab(key, stype);
282 if (numsyms[type]++ == 1) {
283 new->lr[!bit] = sympole[type];
284 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
285 sympole[type] = new;
286 return (struct symtab *)new->lr[bit];
287 }
288
289
290 w = sympole[type];
291 last = NULL;
292 for (;;) {
293 fbit = w->bitno;
294 bitno = BITNO(w->bitno);
295 if (bitno == cix)
296 cerror("bitno == cix");
297 if (bitno > cix)
298 break;
299 svbit = (code >> bitno) & 1;
300 last = w;
301 w = w->lr[svbit];
302 if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
303 break;
304 }
305
306 new->lr[!bit] = w;
307 if (last == NULL) {
308 sympole[type] = new;
309 } else {
310 last->lr[svbit] = new;
311 last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
312 }
313 if (bitno < cix)
314 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
315 return (struct symtab *)new->lr[bit];
316 }
317
318 void
symclear(int level)319 symclear(int level)
320 {
321 struct symtab *s;
322 int i;
323
324 #ifdef PCC_DEBUG
325 if (ddebug)
326 printf("symclear(%d)\n", level);
327 #endif
328 if (level < 1) {
329 for (i = 0; i < NSTYPES; i++) {
330 s = tmpsyms[i];
331 tmpsyms[i] = 0;
332 if (i != SLBLNAME)
333 continue;
334 while (s != NULL) {
335 if (s->soffset < 0)
336 uerror("label '%s' undefined",s->sname);
337 s = s->snext;
338 }
339 }
340 } else {
341 for (i = 0; i < NSTYPES; i++) {
342 if (i == SLBLNAME)
343 continue; /* function scope */
344 while (tmpsyms[i] != NULL &&
345 tmpsyms[i]->slevel > level) {
346 tmpsyms[i] = tmpsyms[i]->snext;
347 }
348 }
349 }
350 }
351
352 struct symtab *
hide(struct symtab * sym)353 hide(struct symtab *sym)
354 {
355 struct symtab *new;
356 int typ = sym->sflags & SMASK;
357
358 new = getsymtab(sym->sname, typ|STEMP);
359 new->snext = tmpsyms[typ];
360 tmpsyms[typ] = new;
361
362 #ifdef PCC_DEBUG
363 if (ddebug)
364 printf("\t%s hidden at level %d (%p -> %p)\n",
365 sym->sname, blevel, sym, new);
366 #endif
367 return new;
368 }
369
370 /*
371 * Extract correct segment for the specified symbol and call
372 * target routines to print it out.
373 * If symtab entry is specified, output alignment as well.
374 */
375 void
locctr(int seg,struct symtab * sp)376 locctr(int seg, struct symtab *sp)
377 {
378 #ifdef GCC_COMPAT
379 struct attr *ga;
380 #endif
381
382 if (seg == NOSEG) {
383 ;
384 } else if (sp == NULL) {
385 if (lastloc != seg)
386 setseg(seg, NULL);
387 #ifdef GCC_COMPAT
388 } else if ((ga = attr_find(sp->sap, GCC_ATYP_SECTION)) != NULL) {
389 setseg(NMSEG, ga->sarg(0));
390 seg = NOSEG;
391 #endif
392 } else {
393 if (seg == DATA) {
394 if (ISCON(cqual(sp->stype, sp->squal)))
395 seg = RDATA;
396 else if (sp->sclass == STATIC)
397 seg = LDATA;
398 }
399 if (sp->sflags & STLS) {
400 if (seg == DATA || seg == LDATA)
401 seg = TLSDATA;
402 if (seg == UDATA) seg = TLSUDATA;
403 } else if (kflag) {
404 if (seg == DATA) seg = PICDATA;
405 if (seg == RDATA) seg = PICRDATA;
406 if (seg == LDATA) seg = PICLDATA;
407 }
408 if (lastloc != seg)
409 setseg(seg, NULL);
410 }
411 lastloc = seg;
412
413 /* setup alignment */
414 #ifndef ALFTN
415 #define ALFTN ALINT
416 #endif
417 if (sp) {
418 int al;
419
420 if (ISFTN(sp->stype)) {
421 al = ALFTN;
422 } else
423 al = talign(sp->stype, sp->sap);
424 defalign(al);
425 symdirec(sp);
426 }
427 }
428
429 #ifndef MYALIGN
430 void
defalign(int al)431 defalign(int al)
432 {
433 #ifdef HASP2ALIGN
434 #define P2ALIGN(x) ispow2(x)
435 #else
436 #define P2ALIGN(x) (x)
437 #endif
438 if (al != ALCHAR)
439 printf(PRTPREF "\t.align %d\n", P2ALIGN(al/ALCHAR));
440 }
441 #endif
442
443 #ifndef MYDIREC
444 /*
445 * Directives given as attributes to symbols.
446 */
447 void
symdirec(struct symtab * sp)448 symdirec(struct symtab *sp)
449 {
450 #ifdef GCC_COMPAT
451 struct attr *ga;
452 char *name;
453
454 name = getexname(sp);
455 if ((ga = attr_find(sp->sap, GCC_ATYP_WEAK)) != NULL)
456 printf(PRTPREF "\t.weak %s\n", name);
457 if ((ga = attr_find(sp->sap, GCC_ATYP_VISIBILITY)) &&
458 strcmp(ga->sarg(0), "default"))
459 printf(PRTPREF "\t.%s %s\n", ga->sarg(0), name);
460 if ((ga = attr_find(sp->sap, GCC_ATYP_ALIASWEAK))) {
461 printf(PRTPREF "\t.weak %s\n", ga->sarg(0));
462 printf(PRTPREF "\t.set %s,%s\n", ga->sarg(0), name);
463 }
464 #endif
465 }
466 #endif
467
468 char *
getexname(struct symtab * sp)469 getexname(struct symtab *sp)
470 {
471 struct attr *ap = attr_find(sp->sap, ATTR_SONAME);
472
473 return (ap ? ap->sarg(0) : addname(exname(sp->sname)));
474 }
475
476 static char *csbuf;
477 static int csbufp, cssz, strtype;
478 #ifndef NO_STRING_SAVE
479 static struct symtab *strpole;
480 #endif
481 #define STCHNK 128
482
483 static void
savch(int ch)484 savch(int ch)
485 {
486 if (csbufp == cssz) {
487 cssz += STCHNK;
488 csbuf = realloc(csbuf, cssz);
489 }
490 csbuf[csbufp++] = ch;
491 }
492
493 /*
494 * save value as 3-digit octal escape sequence
495 */
496 static void
voct(unsigned int v)497 voct(unsigned int v)
498 {
499 savch('\\');
500 savch(((v & 0700) >> 6) + '0');
501 savch(((v & 0070) >> 3) + '0');
502 savch((v & 0007) + '0');
503 }
504
505
506 /*
507 * Add string new to string old.
508 * String new must come directly after old.
509 * new is expected to be utf-8. Will be cleaned slightly here.
510 */
511 char *
stradd(char * old,char * new)512 stradd(char *old, char *new)
513 {
514 if (old == NULL) {
515 strtype = 0;
516 csbufp = 0;
517 } else if (old != csbuf)
518 cerror("string synk error");
519
520 /* special hack for function names */
521 for (old = new; *old; old++)
522 ;
523 if (old[-1] != '\"') {
524 do {
525 savch(*new);
526 } while (*new++);
527 return csbuf;
528 }
529
530 if (*new != '\"') {
531 int ny = *new++;
532 if (ny == 'u' && *new == '8')
533 ny = '8', new++;
534 if (strtype && ny != strtype)
535 uerror("clash in string types");
536 strtype = ny;
537 }
538 if (*new++ != '\"')
539 cerror("snuff synk error");
540
541 while (*new != '\"') {
542 if (*new == '\\') {
543 voct(esccon(&new));
544 } else if (*new < ' ' || *new > '~') {
545 voct(*(unsigned char *)new++);
546 } else {
547 savch(*new++);
548 }
549 }
550 savch(0);
551 csbufp--;
552 return csbuf;
553 }
554
555 TWORD
styp(void)556 styp(void)
557 {
558 TWORD t;
559
560 if (strtype == 0 || strtype == '8')
561 t = xuchar ? UCHAR+ARY : CHAR+ARY;
562 else if (strtype == 'u')
563 t = ctype(USHORT)+ARY;
564 else if (strtype == 'L')
565 t = WCHAR_TYPE+ARY;
566 else
567 t = ctype(SZINT < 32 ? ULONG : UNSIGNED)+ARY;
568 return t;
569 }
570
571 /*
572 * Create a string struct.
573 */
574 static void
strst(struct symtab * sp,TWORD t)575 strst(struct symtab *sp, TWORD t)
576 {
577 char *wr;
578 int i;
579
580 sp->sclass = STATIC;
581 sp->slevel = 1;
582 sp->soffset = getlab();
583 sp->squal = (CON >> TSHIFT);
584 #ifndef NO_STRING_SAVE
585 sp->sdf = permalloc(sizeof(union dimfun));
586 #else
587 sp->sdf = stmtalloc(sizeof(union dimfun));
588 #endif
589 dimfuncnt++;
590 sp->stype = t;
591
592 for (wr = sp->sname, i = 1; *wr; i++) {
593 if (strtype == 'L' || strtype == 'U' || strtype == 'u')
594 (void)u82cp(&wr);
595 else if (*wr == '\\')
596 (void)esccon(&wr);
597 else
598 wr++;
599 }
600 sp->sdf->ddim = i;
601 #ifndef NO_STRING_SAVE
602 sp->snext = strpole;
603 strpole = sp;
604 #endif
605 }
606
607 /*
608 * Save string (if needed) and return NODE for it.
609 * String is already in utf-8 format.
610 */
611 NODE *
strend(char * s,TWORD t)612 strend(char *s, TWORD t)
613 {
614 struct symtab *sp, *sp2;
615 NODE *p;
616
617 #ifdef NO_STRING_SAVE
618 sp = getsymtab(s, SSTRING|SSTMT);
619 #else
620 s = addstring(s);
621 sp = lookup(s, SSTRING);
622 #endif
623
624 if (sp->soffset && sp->stype != t) {
625 /* same string stored but different type */
626 /* This is uncommon, create a new symtab struct for it */
627 sp2 = permalloc(sizeof(*sp));
628 *sp2 = *sp;
629 strst(sp2, t);
630 sp = sp2;
631 } else if (sp->soffset == 0) { /* No string */
632 strst(sp, t);
633 }
634 if (cssz > STCHNK) {
635 cssz = STCHNK;
636 csbuf = realloc(csbuf, cssz);
637 }
638 #ifdef NO_STRING_SAVE
639 instring(sp);
640 #endif
641 p = block(NAME, NIL, NIL, sp->stype, sp->sdf, sp->sap);
642 p->n_sp = sp;
643 return(clocal(p));
644 }
645
646 #ifndef NO_STRING_SAVE
647 /*
648 * Print out strings that have been referenced.
649 */
650 void
strprint(void)651 strprint(void)
652 {
653 struct symtab *sp;
654
655 for (sp = strpole; sp; sp = sp->snext) {
656 if ((sp->sflags & SASG) == 0)
657 continue; /* not referenced */
658 instring(sp);
659 }
660 }
661 #endif
662