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