qbe

Internal scc patchset buffer for QBE
Log | Files | Refs | README | LICENSE

util.c (8604B)


      1 #include "all.h"
      2 #include <stdarg.h>
      3 
      4 typedef struct Bitset Bitset;
      5 typedef struct Vec Vec;
      6 typedef struct Bucket Bucket;
      7 
      8 struct Vec {
      9 	ulong mag;
     10 	Pool pool;
     11 	size_t esz;
     12 	ulong cap;
     13 	union {
     14 		long long ll;
     15 		long double ld;
     16 		void *ptr;
     17 	} align[];
     18 };
     19 
     20 struct Bucket {
     21 	uint nstr;
     22 	char **str;
     23 };
     24 
     25 enum {
     26 	VMin = 2,
     27 	VMag = 0xcabba9e,
     28 	NPtr = 256,
     29 	IBits = 12,
     30 	IMask = (1<<IBits) - 1,
     31 };
     32 
     33 Typ *typ;
     34 Ins insb[NIns], *curi;
     35 
     36 static void *ptr[NPtr];
     37 static void **pool = ptr;
     38 static int nptr = 1;
     39 
     40 static Bucket itbl[IMask+1]; /* string interning table */
     41 
     42 uint32_t
     43 hash(char *s)
     44 {
     45 	uint32_t h;
     46 
     47 	for (h=0; *s; ++s)
     48 		h = *s + 17*h;
     49 	return h;
     50 }
     51 
     52 void
     53 die_(char *file, char *s, ...)
     54 {
     55 	va_list ap;
     56 
     57 	fprintf(stderr, "%s: dying: ", file);
     58 	va_start(ap, s);
     59 	vfprintf(stderr, s, ap);
     60 	va_end(ap);
     61 	fputc('\n', stderr);
     62 	abort();
     63 }
     64 
     65 void *
     66 emalloc(size_t n)
     67 {
     68 	void *p;
     69 
     70 	p = calloc(1, n);
     71 	if (!p)
     72 		die("emalloc, out of memory");
     73 	return p;
     74 }
     75 
     76 void *
     77 alloc(size_t n)
     78 {
     79 	void **pp;
     80 
     81 	if (n == 0)
     82 		return 0;
     83 	if (nptr >= NPtr) {
     84 		pp = emalloc(NPtr * sizeof(void *));
     85 		pp[0] = pool;
     86 		pool = pp;
     87 		nptr = 1;
     88 	}
     89 	return pool[nptr++] = emalloc(n);
     90 }
     91 
     92 void
     93 freeall()
     94 {
     95 	void **pp;
     96 
     97 	for (;;) {
     98 		for (pp = &pool[1]; pp < &pool[nptr]; pp++)
     99 			free(*pp);
    100 		pp = pool[0];
    101 		if (!pp)
    102 			break;
    103 		free(pool);
    104 		pool = pp;
    105 		nptr = NPtr;
    106 	}
    107 	nptr = 1;
    108 }
    109 
    110 void *
    111 vnew(ulong len, size_t esz, Pool pool)
    112 {
    113 	void *(*f)(size_t);
    114 	ulong cap;
    115 	Vec *v;
    116 
    117 	for (cap=VMin; cap<len; cap*=2)
    118 		;
    119 	f = pool == Pheap ? emalloc : alloc;
    120 	v = f(cap * esz + sizeof(Vec));
    121 	v->mag = VMag;
    122 	v->cap = cap;
    123 	v->esz = esz;
    124 	v->pool = pool;
    125 	return v + 1;
    126 }
    127 
    128 void
    129 vfree(void *p)
    130 {
    131 	Vec *v;
    132 
    133 	v = (Vec *)p - 1;
    134 	assert(v->mag == VMag);
    135 	if (v->pool == Pheap) {
    136 		v->mag = 0;
    137 		free(v);
    138 	}
    139 }
    140 
    141 void
    142 vgrow(void *vp, ulong len)
    143 {
    144 	Vec *v;
    145 	void *v1;
    146 
    147 	v = *(Vec **)vp - 1;
    148 	assert(v+1 && v->mag == VMag);
    149 	if (v->cap >= len)
    150 		return;
    151 	v1 = vnew(len, v->esz, v->pool);
    152 	memcpy(v1, v+1, v->cap * v->esz);
    153 	vfree(v+1);
    154 	*(Vec **)vp = v1;
    155 }
    156 
    157 uint32_t
    158 intern(char *s)
    159 {
    160 	Bucket *b;
    161 	uint32_t h;
    162 	uint i, n;
    163 
    164 	h = hash(s) & IMask;
    165 	b = &itbl[h];
    166 	n = b->nstr;
    167 
    168 	for (i=0; i<n; i++)
    169 		if (strcmp(s, b->str[i]) == 0)
    170 			return h + (i<<IBits);
    171 
    172 	if (n == 1<<(32-IBits))
    173 		die("interning table overflow");
    174 	if (n == 0)
    175 		b->str = vnew(1, sizeof b->str[0], Pheap);
    176 	else if ((n & (n-1)) == 0)
    177 		vgrow(&b->str, n+n);
    178 
    179 	b->str[n] = emalloc(strlen(s)+1);
    180 	b->nstr = n + 1;
    181 	strcpy(b->str[n], s);
    182 	return h + (n<<IBits);
    183 }
    184 
    185 char *
    186 str(uint32_t id)
    187 {
    188 	assert(id>>IBits < itbl[id&IMask].nstr);
    189 	return itbl[id&IMask].str[id>>IBits];
    190 }
    191 
    192 int
    193 isreg(Ref r)
    194 {
    195 	return rtype(r) == RTmp && r.val < Tmp0;
    196 }
    197 
    198 int
    199 iscmp(int op, int *pk, int *pc)
    200 {
    201 	if (Ocmpw <= op && op <= Ocmpw1) {
    202 		*pc = op - Ocmpw;
    203 		*pk = Kw;
    204 	}
    205 	else if (Ocmpl <= op && op <= Ocmpl1) {
    206 		*pc = op - Ocmpl;
    207 		*pk = Kl;
    208 	}
    209 	else if (Ocmps <= op && op <= Ocmps1) {
    210 		*pc = NCmpI + op - Ocmps;
    211 		*pk = Ks;
    212 	}
    213 	else if (Ocmpd <= op && op <= Ocmpd1) {
    214 		*pc = NCmpI + op - Ocmpd;
    215 		*pk = Kd;
    216 	}
    217 	else
    218 		return 0;
    219 	return 1;
    220 }
    221 
    222 int
    223 argcls(Ins *i, int n)
    224 {
    225 	return optab[i->op].argcls[n][i->cls];
    226 }
    227 
    228 void
    229 emit(int op, int k, Ref to, Ref arg0, Ref arg1)
    230 {
    231 	if (curi == insb)
    232 		die("emit, too many instructions");
    233 	*--curi = (Ins){
    234 		.op = op, .cls = k,
    235 		.to = to, .arg = {arg0, arg1}
    236 	};
    237 }
    238 
    239 void
    240 emiti(Ins i)
    241 {
    242 	emit(i.op, i.cls, i.to, i.arg[0], i.arg[1]);
    243 }
    244 
    245 void
    246 idup(Ins **pd, Ins *s, ulong n)
    247 {
    248 	*pd = alloc(n * sizeof(Ins));
    249 	if (n)
    250 		memcpy(*pd, s, n * sizeof(Ins));
    251 }
    252 
    253 Ins *
    254 icpy(Ins *d, Ins *s, ulong n)
    255 {
    256 	if (n)
    257 		memcpy(d, s, n * sizeof(Ins));
    258 	return d + n;
    259 }
    260 
    261 static int cmptab[][2] ={
    262 	             /* negation    swap */
    263 	[Ciule]      = {Ciugt,      Ciuge},
    264 	[Ciult]      = {Ciuge,      Ciugt},
    265 	[Ciugt]      = {Ciule,      Ciult},
    266 	[Ciuge]      = {Ciult,      Ciule},
    267 	[Cisle]      = {Cisgt,      Cisge},
    268 	[Cislt]      = {Cisge,      Cisgt},
    269 	[Cisgt]      = {Cisle,      Cislt},
    270 	[Cisge]      = {Cislt,      Cisle},
    271 	[Cieq]       = {Cine,       Cieq},
    272 	[Cine]       = {Cieq,       Cine},
    273 	[NCmpI+Cfle] = {NCmpI+Cfgt, NCmpI+Cfge},
    274 	[NCmpI+Cflt] = {NCmpI+Cfge, NCmpI+Cfgt},
    275 	[NCmpI+Cfgt] = {NCmpI+Cfle, NCmpI+Cflt},
    276 	[NCmpI+Cfge] = {NCmpI+Cflt, NCmpI+Cfle},
    277 	[NCmpI+Cfeq] = {NCmpI+Cfne, NCmpI+Cfeq},
    278 	[NCmpI+Cfne] = {NCmpI+Cfeq, NCmpI+Cfne},
    279 	[NCmpI+Cfo]  = {NCmpI+Cfuo, NCmpI+Cfo},
    280 	[NCmpI+Cfuo] = {NCmpI+Cfo,  NCmpI+Cfuo},
    281 };
    282 
    283 int
    284 cmpneg(int c)
    285 {
    286 	assert(0 <= c && c < NCmp);
    287 	return cmptab[c][0];
    288 }
    289 
    290 int
    291 cmpop(int c)
    292 {
    293 	assert(0 <= c && c < NCmp);
    294 	return cmptab[c][1];
    295 }
    296 
    297 int
    298 clsmerge(short *pk, short k)
    299 {
    300 	short k1;
    301 
    302 	k1 = *pk;
    303 	if (k1 == Kx) {
    304 		*pk = k;
    305 		return 0;
    306 	}
    307 	if ((k1 == Kw && k == Kl) || (k1 == Kl && k == Kw)) {
    308 		*pk = Kw;
    309 		return 0;
    310 	}
    311 	return k1 != k;
    312 }
    313 
    314 int
    315 phicls(int t, Tmp *tmp)
    316 {
    317 	int t1;
    318 
    319 	t1 = tmp[t].phi;
    320 	if (!t1)
    321 		return t;
    322 	t1 = phicls(t1, tmp);
    323 	tmp[t].phi = t1;
    324 	return t1;
    325 }
    326 
    327 Ref
    328 newtmp(char *prfx, int k,  Fn *fn)
    329 {
    330 	static int n;
    331 	int t;
    332 
    333 	t = fn->ntmp++;
    334 	vgrow(&fn->tmp, fn->ntmp);
    335 	memset(&fn->tmp[t], 0, sizeof(Tmp));
    336 	if (prfx)
    337 		sprintf(fn->tmp[t].name, "%s.%d", prfx, ++n);
    338 	fn->tmp[t].cls = k;
    339 	fn->tmp[t].slot = -1;
    340 	fn->tmp[t].nuse = +1;
    341 	fn->tmp[t].ndef = +1;
    342 	return TMP(t);
    343 }
    344 
    345 void
    346 chuse(Ref r, int du, Fn *fn)
    347 {
    348 	if (rtype(r) == RTmp)
    349 		fn->tmp[r.val].nuse += du;
    350 }
    351 
    352 Ref
    353 getcon(int64_t val, Fn *fn)
    354 {
    355 	int c;
    356 
    357 	for (c=0; c<fn->ncon; c++)
    358 		if (fn->con[c].type == CBits && fn->con[c].bits.i == val)
    359 			return CON(c);
    360 	vgrow(&fn->con, ++fn->ncon);
    361 	fn->con[c] = (Con){.type = CBits, .bits.i = val};
    362 	return CON(c);
    363 }
    364 
    365 int
    366 addcon(Con *c0, Con *c1)
    367 {
    368 	if (c0->type == CUndef)
    369 		*c0 = *c1;
    370 	else {
    371 		if (c1->type == CAddr) {
    372 			if (c0->type == CAddr)
    373 				return 0;
    374 			c0->type = CAddr;
    375 			c0->label = c1->label;
    376 		}
    377 		c0->bits.i += c1->bits.i;
    378 	}
    379 	return 1;
    380 }
    381 
    382 void
    383 blit(Ref rdst, uint doff, Ref rsrc, uint sz, Fn *fn)
    384 {
    385 	struct { int st, ld, cls, size; } *p, tbl[] = {
    386 		{ Ostorel, Oload,   Kl, 8 },
    387 		{ Ostorew, Oload,   Kw, 4 },
    388 		{ Ostoreh, Oloaduh, Kw, 2 },
    389 		{ Ostoreb, Oloadub, Kw, 1 }
    390 	};
    391 	Ref r, r1;
    392 	uint boff, s;
    393 
    394 	for (boff=0, p=tbl; sz; p++)
    395 		for (s=p->size; sz>=s; sz-=s, doff+=s, boff+=s) {
    396 			r = newtmp("blt", Kl, fn);
    397 			r1 = newtmp("blt", Kl, fn);
    398 			emit(p->st, 0, R, r, r1);
    399 			emit(Oadd, Kl, r1, rdst, getcon(doff, fn));
    400 			r1 = newtmp("blt", Kl, fn);
    401 			emit(p->ld, p->cls, r, r1, R);
    402 			emit(Oadd, Kl, r1, rsrc, getcon(boff, fn));
    403 		}
    404 }
    405 
    406 void
    407 bsinit(BSet *bs, uint n)
    408 {
    409 	n = (n + NBit-1) / NBit;
    410 	bs->nt = n;
    411 	bs->t = alloc(n * sizeof bs->t[0]);
    412 }
    413 
    414 MAKESURE(NBit_is_64, NBit == 64);
    415 inline static uint
    416 popcnt(bits b)
    417 {
    418 	b = (b & 0x5555555555555555) + ((b>>1) & 0x5555555555555555);
    419 	b = (b & 0x3333333333333333) + ((b>>2) & 0x3333333333333333);
    420 	b = (b & 0x0f0f0f0f0f0f0f0f) + ((b>>4) & 0x0f0f0f0f0f0f0f0f);
    421 	b += (b>>8);
    422 	b += (b>>16);
    423 	b += (b>>32);
    424 	return b & 0xff;
    425 }
    426 
    427 inline static int
    428 firstbit(bits b)
    429 {
    430 	int n;
    431 
    432 	n = 0;
    433 	if (!(b & 0xffffffff)) {
    434 		n += 32;
    435 		b >>= 32;
    436 	}
    437 	if (!(b & 0xffff)) {
    438 		n += 16;
    439 		b >>= 16;
    440 	}
    441 	if (!(b & 0xff)) {
    442 		n += 8;
    443 		b >>= 8;
    444 	}
    445 	if (!(b & 0xf)) {
    446 		n += 4;
    447 		b >>= 4;
    448 	}
    449 	n += (char[16]){4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}[b & 0xf];
    450 	return n;
    451 }
    452 
    453 uint
    454 bscount(BSet *bs)
    455 {
    456 	uint i, n;
    457 
    458 	n = 0;
    459 	for (i=0; i<bs->nt; i++)
    460 		n += popcnt(bs->t[i]);
    461 	return n;
    462 }
    463 
    464 static inline uint
    465 bsmax(BSet *bs)
    466 {
    467 	return bs->nt * NBit;
    468 }
    469 
    470 void
    471 bsset(BSet *bs, uint elt)
    472 {
    473 	assert(elt < bsmax(bs));
    474 	bs->t[elt/NBit] |= BIT(elt%NBit);
    475 }
    476 
    477 void
    478 bsclr(BSet *bs, uint elt)
    479 {
    480 	assert(elt < bsmax(bs));
    481 	bs->t[elt/NBit] &= ~BIT(elt%NBit);
    482 }
    483 
    484 #define BSOP(f, op)                           \
    485 	void                                  \
    486 	f(BSet *a, BSet *b)                   \
    487 	{                                     \
    488 		uint i;                       \
    489 		                              \
    490 		assert(a->nt == b->nt);       \
    491 		for (i=0; i<a->nt; i++)       \
    492 			a->t[i] op b->t[i];   \
    493 	}
    494 
    495 BSOP(bscopy, =)
    496 BSOP(bsunion, |=)
    497 BSOP(bsinter, &=)
    498 BSOP(bsdiff, &= ~)
    499 
    500 int
    501 bsequal(BSet *a, BSet *b)
    502 {
    503 	uint i;
    504 
    505 	assert(a->nt == b->nt);
    506 	for (i=0; i<a->nt; i++)
    507 		if (a->t[i] != b->t[i])
    508 			return 0;
    509 	return 1;
    510 }
    511 
    512 void
    513 bszero(BSet *bs)
    514 {
    515 	memset(bs->t, 0, bs->nt * sizeof bs->t[0]);
    516 }
    517 
    518 /* iterates on a bitset, use as follows
    519  *
    520  * 	for (i=0; bsiter(set, &i); i++)
    521  * 		use(i);
    522  *
    523  */
    524 int
    525 bsiter(BSet *bs, int *elt)
    526 {
    527 	bits b;
    528 	uint t, i;
    529 
    530 	i = *elt;
    531 	t = i/NBit;
    532 	if (t >= bs->nt)
    533 		return 0;
    534 	b = bs->t[t];
    535 	b &= ~(BIT(i%NBit) - 1);
    536 	while (!b) {
    537 		++t;
    538 		if (t >= bs->nt)
    539 			return 0;
    540 		b = bs->t[t];
    541 	}
    542 	*elt = NBit*t + firstbit(b);
    543 	return 1;
    544 }
    545 
    546 void
    547 dumpts(BSet *bs, Tmp *tmp, FILE *f)
    548 {
    549 	int t;
    550 
    551 	fprintf(f, "[");
    552 	for (t=Tmp0; bsiter(bs, &t); t++)
    553 		fprintf(f, " %s", tmp[t].name);
    554 	fprintf(f, " ]\n");
    555 }