util.c

   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         memcpy(*pd, s, n * sizeof(Ins));
 250 }
 251
 252 Ins *
 253 icpy(Ins *d, Ins *s, ulong n)
 254 {
 255         memcpy(d, s, n * sizeof(Ins));
 256         return d + n;
 257 }
 258
 259 static int cmptab[][2] ={
 260                      /* negation    swap */
 261         [Ciule]      = {Ciugt,      Ciuge},
 262         [Ciult]      = {Ciuge,      Ciugt},
 263         [Ciugt]      = {Ciule,      Ciult},
 264         [Ciuge]      = {Ciult,      Ciule},
 265         [Cisle]      = {Cisgt,      Cisge},
 266         [Cislt]      = {Cisge,      Cisgt},
 267         [Cisgt]      = {Cisle,      Cislt},
 268         [Cisge]      = {Cislt,      Cisle},
 269         [Cieq]       = {Cine,       Cieq},
 270         [Cine]       = {Cieq,       Cine},
 271         [NCmpI+Cfle] = {NCmpI+Cfgt, NCmpI+Cfge},
 272         [NCmpI+Cflt] = {NCmpI+Cfge, NCmpI+Cfgt},
 273         [NCmpI+Cfgt] = {NCmpI+Cfle, NCmpI+Cflt},
 274         [NCmpI+Cfge] = {NCmpI+Cflt, NCmpI+Cfle},
 275         [NCmpI+Cfeq] = {NCmpI+Cfne, NCmpI+Cfeq},
 276         [NCmpI+Cfne] = {NCmpI+Cfeq, NCmpI+Cfne},
 277         [NCmpI+Cfo]  = {NCmpI+Cfuo, NCmpI+Cfo},
 278         [NCmpI+Cfuo] = {NCmpI+Cfo,  NCmpI+Cfuo},
 279 };
 280
 281 int
 282 cmpneg(int c)
 283 {
 284         assert(0 <= c && c < NCmp);
 285         return cmptab[c][0];
 286 }
 287
 288 int
 289 cmpop(int c)
 290 {
 291         assert(0 <= c && c < NCmp);
 292         return cmptab[c][1];
 293 }
 294
 295 int
 296 clsmerge(short *pk, short k)
 297 {
 298         short k1;
 299
 300         k1 = *pk;
 301         if (k1 == Kx) {
 302                 *pk = k;
 303                 return 0;
 304         }
 305         if ((k1 == Kw && k == Kl) || (k1 == Kl && k == Kw)) {
 306                 *pk = Kw;
 307                 return 0;
 308         }
 309         return k1 != k;
 310 }
 311
 312 int
 313 phicls(int t, Tmp *tmp)
 314 {
 315         int t1;
 316
 317         t1 = tmp[t].phi;
 318         if (!t1)
 319                 return t;
 320         t1 = phicls(t1, tmp);
 321         tmp[t].phi = t1;
 322         return t1;
 323 }
 324
 325 Ref
 326 newtmp(char *prfx, int k,  Fn *fn)
 327 {
 328         static int n;
 329         int t;
 330
 331         t = fn->ntmp++;
 332         vgrow(&fn->tmp, fn->ntmp);
 333         memset(&fn->tmp[t], 0, sizeof(Tmp));
 334         if (prfx)
 335                 sprintf(fn->tmp[t].name, "%s.%d", prfx, ++n);
 336         fn->tmp[t].cls = k;
 337         fn->tmp[t].slot = -1;
 338         fn->tmp[t].nuse = +1;
 339         fn->tmp[t].ndef = +1;
 340         return TMP(t);
 341 }
 342
 343 void
 344 chuse(Ref r, int du, Fn *fn)
 345 {
 346         if (rtype(r) == RTmp)
 347                 fn->tmp[r.val].nuse += du;
 348 }
 349
 350 Ref
 351 getcon(int64_t val, Fn *fn)
 352 {
 353         int c;
 354
 355         for (c=0; c<fn->ncon; c++)
 356                 if (fn->con[c].type == CBits && fn->con[c].bits.i == val)
 357                         return CON(c);
 358         vgrow(&fn->con, ++fn->ncon);
 359         fn->con[c] = (Con){.type = CBits, .bits.i = val};
 360         return CON(c);
 361 }
 362
 363 void
 364 addcon(Con *c0, Con *c1)
 365 {
 366         if (c0->type == CUndef)
 367                 *c0 = *c1;
 368         else {
 369                 if (c1->type == CAddr) {
 370                         assert(c0->type != CAddr && "adding two addresses");
 371                         c0->type = CAddr;
 372                         c0->label = c1->label;
 373                 }
 374                 c0->bits.i += c1->bits.i;
 375         }
 376 }
 377
 378 void
 379 blit(Ref rdst, uint doff, Ref rsrc, uint sz, Fn *fn)
 380 {
 381         struct { int st, ld, cls, size; } *p, tbl[] = {
 382                 { Ostorel, Oload,   Kl, 8 },
 383                 { Ostorew, Oload,   Kw, 8 },
 384                 { Ostoreh, Oloaduh, Kw, 2 },
 385                 { Ostoreb, Oloadub, Kw, 1 }
 386         };
 387         Ref r, r1;
 388         uint boff, s;
 389
 390         for (boff=0, p=tbl; sz; p++)
 391                 for (s=p->size; sz>=s; sz-=s, doff+=s, boff+=s) {
 392                         r = newtmp("blt", Kl, fn);
 393                         r1 = newtmp("blt", Kl, fn);
 394                         emit(p->st, 0, R, r, r1);
 395                         emit(Oadd, Kl, r1, rdst, getcon(doff, fn));
 396                         r1 = newtmp("blt", Kl, fn);
 397                         emit(p->ld, p->cls, r, r1, R);
 398                         emit(Oadd, Kl, r1, rsrc, getcon(boff, fn));
 399                 }
 400 }
 401
 402 void
 403 bsinit(BSet *bs, uint n)
 404 {
 405         n = (n + NBit-1) / NBit;
 406         bs->nt = n;
 407         bs->t = alloc(n * sizeof bs->t[0]);
 408 }
 409
 410 MAKESURE(NBit_is_64, NBit == 64);
 411 inline static uint
 412 popcnt(bits b)
 413 {
 414         b = (b & 0x5555555555555555) + ((b>>1) & 0x5555555555555555);
 415         b = (b & 0x3333333333333333) + ((b>>2) & 0x3333333333333333);
 416         b = (b & 0x0f0f0f0f0f0f0f0f) + ((b>>4) & 0x0f0f0f0f0f0f0f0f);
 417         b += (b>>8);
 418         b += (b>>16);
 419         b += (b>>32);
 420         return b & 0xff;
 421 }
 422
 423 inline static int
 424 firstbit(bits b)
 425 {
 426         int n;
 427
 428         n = 0;
 429         if (!(b & 0xffffffff)) {
 430                 n += 32;
 431                 b >>= 32;
 432         }
 433         if (!(b & 0xffff)) {
 434                 n += 16;
 435                 b >>= 16;
 436         }
 437         if (!(b & 0xff)) {
 438                 n += 8;
 439                 b >>= 8;
 440         }
 441         if (!(b & 0xf)) {
 442                 n += 4;
 443                 b >>= 4;
 444         }
 445         n += (char[16]){4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}[b & 0xf];
 446         return n;
 447 }
 448
 449 uint
 450 bscount(BSet *bs)
 451 {
 452         uint i, n;
 453
 454         n = 0;
 455         for (i=0; i<bs->nt; i++)
 456                 n += popcnt(bs->t[i]);
 457         return n;
 458 }
 459
 460 static inline uint
 461 bsmax(BSet *bs)
 462 {
 463         return bs->nt * NBit;
 464 }
 465
 466 void
 467 bsset(BSet *bs, uint elt)
 468 {
 469         assert(elt < bsmax(bs));
 470         bs->t[elt/NBit] |= BIT(elt%NBit);
 471 }
 472
 473 void
 474 bsclr(BSet *bs, uint elt)
 475 {
 476         assert(elt < bsmax(bs));
 477         bs->t[elt/NBit] &= ~BIT(elt%NBit);
 478 }
 479
 480 #define BSOP(f, op)                           \
 481         void                                  \
 482         f(BSet *a, BSet *b)                   \
 483         {                                     \
 484                 uint i;                       \
 485                                               \
 486                 assert(a->nt == b->nt);       \
 487                 for (i=0; i<a->nt; i++)       \
 488                         a->t[i] op b->t[i];   \
 489         }
 490
 491 BSOP(bscopy, =)
 492 BSOP(bsunion, |=)
 493 BSOP(bsinter, &=)
 494 BSOP(bsdiff, &= ~)
 495
 496 int
 497 bsequal(BSet *a, BSet *b)
 498 {
 499         uint i;
 500
 501         assert(a->nt == b->nt);
 502         for (i=0; i<a->nt; i++)
 503                 if (a->t[i] != b->t[i])
 504                         return 0;
 505         return 1;
 506 }
 507
 508 void
 509 bszero(BSet *bs)
 510 {
 511         memset(bs->t, 0, bs->nt * sizeof bs->t[0]);
 512 }
 513
 514 /* iterates on a bitset, use as follows
 515  *
 516  *      for (i=0; bsiter(set, &i); i++)
 517  *              use(i);
 518  *
 519  */
 520 int
 521 bsiter(BSet *bs, int *elt)
 522 {
 523         bits b;
 524         uint t, i;
 525
 526         i = *elt;
 527         t = i/NBit;
 528         if (t >= bs->nt)
 529                 return 0;
 530         b = bs->t[t];
 531         b &= ~(BIT(i%NBit) - 1);
 532         while (!b) {
 533                 ++t;
 534                 if (t >= bs->nt)
 535                         return 0;
 536                 b = bs->t[t];
 537         }
 538         *elt = NBit*t + firstbit(b);
 539         return 1;
 540 }
 541
 542 void
 543 dumpts(BSet *bs, Tmp *tmp, FILE *f)
 544 {
 545         int t;
 546
 547         fprintf(f, "[");
 548         for (t=Tmp0; bsiter(bs, &t); t++)
 549                 fprintf(f, " %s", tmp[t].name);
 550         fprintf(f, " ]\n");
 551 }