util.c

См. документацию.

#include "all.h"
#include <stdarg.h>

typedef struct Bitset Bitset;
typedef struct Vec Vec;
typedef struct Bucket Bucket;

struct Vec {
    ulong mag;
    Pool pool;
    size_t esz;
    ulong cap;
    union {
        long long ll;
        long double ld;
        void *ptr;
    } align[];
};

struct Bucket {
    uint nstr;
    char **str;
};

enum {
    VMin = 2,
    VMag = 0xcabba9e,
    NPtr = 256,
    IBits = 12,
    IMask = (1<<IBits) - 1,
};

Typ *typ;
Ins insb[NIns], *curi;

static void *ptr[NPtr];
static void **pool = ptr;
static int nptr = 1;

static Bucket itbl[IMask+1]; /* string interning table */

uint32_t
hash(char *s)
{
    uint32_t h;

    for (h=0; *s; ++s)
        h = *s + 17*h;
    return h;
}

void
die_(char *file, char *s, ...)
{
    va_list ap;

    fprintf(stderr, "%s: dying: ", file);
    va_start(ap, s);
    vfprintf(stderr, s, ap);
    va_end(ap);
    fputc('\n', stderr);
    abort();
}

void *
emalloc(size_t n)
{
    void *p;

    p = calloc(1, n);
    if (!p)
        die("emalloc, out of memory");
    return p;
}

void *
alloc(size_t n)
{
    void **pp;

    if (n == 0)
        return 0;
    if (nptr >= NPtr) {
        pp = emalloc(NPtr * sizeof(void *));
        pp[0] = pool;
        pool = pp;
        nptr = 1;
    }
    return pool[nptr++] = emalloc(n);
}

void
freeall()
{
    void **pp;

    for (;;) {
        for (pp = &pool[1]; pp < &pool[nptr]; pp++)
            free(*pp);
        pp = pool[0];
        if (!pp)
            break;
        free(pool);
        pool = pp;
        nptr = NPtr;
    }
    nptr = 1;
}

void *
vnew(ulong len, size_t esz, Pool pool)
{
    void *(*f)(size_t);
    ulong cap;
    Vec *v;

    for (cap=VMin; cap<len; cap*=2)
        ;
    f = pool == Pheap ? emalloc : alloc;
    v = f(cap * esz + sizeof(Vec));
    v->mag = VMag;
    v->cap = cap;
    v->esz = esz;
    v->pool = pool;
    return v + 1;
}

void
vfree(void *p)
{
    Vec *v;

    v = (Vec *)p - 1;
    assert(v->mag == VMag);
    if (v->pool == Pheap) {
        v->mag = 0;
        free(v);
    }
}

void
vgrow(void *vp, ulong len)
{
    Vec *v;
    void *v1;

    v = *(Vec **)vp - 1;
    assert(v+1 && v->mag == VMag);
    if (v->cap >= len)
        return;
    v1 = vnew(len, v->esz, v->pool);
    memcpy(v1, v+1, v->cap * v->esz);
    vfree(v+1);
    *(Vec **)vp = v1;
}

uint32_t
intern(char *s)
{
    Bucket *b;
    uint32_t h;
    uint i, n;

    h = hash(s) & IMask;
    b = &itbl[h];
    n = b->nstr;

    for (i=0; i<n; i++)
        if (strcmp(s, b->str[i]) == 0)
            return h + (i<<IBits);

    if (n == 1<<(32-IBits))
        die("interning table overflow");
    if (n == 0)
        b->str = vnew(1, sizeof b->str[0], Pheap);
    else if ((n & (n-1)) == 0)
        vgrow(&b->str, n+n);

    b->str[n] = emalloc(strlen(s)+1);
    b->nstr = n + 1;
    strcpy(b->str[n], s);
    return h + (n<<IBits);
}

char *
str(uint32_t id)
{
    assert(id>>IBits < itbl[id&IMask].nstr);
    return itbl[id&IMask].str[id>>IBits];
}

int
isreg(Ref r)
{
    return rtype(r) == RTmp && r.val < Tmp0;
}

int
iscmp(int op, int *pk, int *pc)
{
    if (Ocmpw <= op && op <= Ocmpw1) {
        *pc = op - Ocmpw;
        *pk = Kw;
    }
    else if (Ocmpl <= op && op <= Ocmpl1) {
        *pc = op - Ocmpl;
        *pk = Kl;
    }
    else if (Ocmps <= op && op <= Ocmps1) {
        *pc = NCmpI + op - Ocmps;
        *pk = Ks;
    }
    else if (Ocmpd <= op && op <= Ocmpd1) {
        *pc = NCmpI + op - Ocmpd;
        *pk = Kd;
    }
    else
        return 0;
    return 1;
}

int
argcls(Ins *i, int n)
{
    return optab[i->op].argcls[n][i->cls];
}

void
emit(int op, int k, Ref to, Ref arg0, Ref arg1)
{
    if (curi == insb)
        die("emit, too many instructions");
    *--curi = (Ins){
        .op = op, .cls = k,
        .to = to, .arg = {arg0, arg1}
    };
}

void
emiti(Ins i)
{
    emit(i.op, i.cls, i.to, i.arg[0], i.arg[1]);
}

void
idup(Ins **pd, Ins *s, ulong n)
{
    *pd = alloc(n * sizeof(Ins));
    memcpy(*pd, s, n * sizeof(Ins));
}

Ins *
icpy(Ins *d, Ins *s, ulong n)
{
    memcpy(d, s, n * sizeof(Ins));
    return d + n;
}

static int cmptab[][2] ={
                 /* negation    swap */
    [Ciule]      = {Ciugt,      Ciuge},
    [Ciult]      = {Ciuge,      Ciugt},
    [Ciugt]      = {Ciule,      Ciult},
    [Ciuge]      = {Ciult,      Ciule},
    [Cisle]      = {Cisgt,      Cisge},
    [Cislt]      = {Cisge,      Cisgt},
    [Cisgt]      = {Cisle,      Cislt},
    [Cisge]      = {Cislt,      Cisle},
    [Cieq]       = {Cine,       Cieq},
    [Cine]       = {Cieq,       Cine},
    [NCmpI+Cfle] = {NCmpI+Cfgt, NCmpI+Cfge},
    [NCmpI+Cflt] = {NCmpI+Cfge, NCmpI+Cfgt},
    [NCmpI+Cfgt] = {NCmpI+Cfle, NCmpI+Cflt},
    [NCmpI+Cfge] = {NCmpI+Cflt, NCmpI+Cfle},
    [NCmpI+Cfeq] = {NCmpI+Cfne, NCmpI+Cfeq},
    [NCmpI+Cfne] = {NCmpI+Cfeq, NCmpI+Cfne},
    [NCmpI+Cfo]  = {NCmpI+Cfuo, NCmpI+Cfo},
    [NCmpI+Cfuo] = {NCmpI+Cfo,  NCmpI+Cfuo},
};

int
cmpneg(int c)
{
    assert(0 <= c && c < NCmp);
    return cmptab[c][0];
}

int
cmpop(int c)
{
    assert(0 <= c && c < NCmp);
    return cmptab[c][1];
}

int
clsmerge(short *pk, short k)
{
    short k1;

    k1 = *pk;
    if (k1 == Kx) {
        *pk = k;
        return 0;
    }
    if ((k1 == Kw && k == Kl) || (k1 == Kl && k == Kw)) {
        *pk = Kw;
        return 0;
    }
    return k1 != k;
}

int
phicls(int t, Tmp *tmp)
{
    int t1;

    t1 = tmp[t].phi;
    if (!t1)
        return t;
    t1 = phicls(t1, tmp);
    tmp[t].phi = t1;
    return t1;
}

Ref
newtmp(char *prfx, int k,  Fn *fn)
{
    static int n;
    int t;

    t = fn->ntmp++;
    vgrow(&fn->tmp, fn->ntmp);
    memset(&fn->tmp[t], 0, sizeof(Tmp));
    if (prfx)
        sprintf(fn->tmp[t].name, "%s.%d", prfx, ++n);
    fn->tmp[t].cls = k;
    fn->tmp[t].slot = -1;
    fn->tmp[t].nuse = +1;
    fn->tmp[t].ndef = +1;
    return TMP(t);
}

void
chuse(Ref r, int du, Fn *fn)
{
    if (rtype(r) == RTmp)
        fn->tmp[r.val].nuse += du;
}

Ref
getcon(int64_t val, Fn *fn)
{
    int c;

    for (c=0; c<fn->ncon; c++)
        if (fn->con[c].type == CBits && fn->con[c].bits.i == val)
            return CON(c);
    vgrow(&fn->con, ++fn->ncon);
    fn->con[c] = (Con){.type = CBits, .bits.i = val};
    return CON(c);
}

void
addcon(Con *c0, Con *c1)
{
    if (c0->type == CUndef)
        *c0 = *c1;
    else {
        if (c1->type == CAddr) {
            assert(c0->type != CAddr && "adding two addresses");
            c0->type = CAddr;
            c0->label = c1->label;
        }
        c0->bits.i += c1->bits.i;
    }
}

void
blit(Ref rdst, uint doff, Ref rsrc, uint sz, Fn *fn)
{
    struct { int st, ld, cls, size; } *p, tbl[] = {
        { Ostorel, Oload,   Kl, 8 },
        { Ostorew, Oload,   Kw, 8 },
        { Ostoreh, Oloaduh, Kw, 2 },
        { Ostoreb, Oloadub, Kw, 1 }
    };
    Ref r, r1;
    uint boff, s;

    for (boff=0, p=tbl; sz; p++)
        for (s=p->size; sz>=s; sz-=s, doff+=s, boff+=s) {
            r = newtmp("blt", Kl, fn);
            r1 = newtmp("blt", Kl, fn);
            emit(p->st, 0, R, r, r1);
            emit(Oadd, Kl, r1, rdst, getcon(doff, fn));
            r1 = newtmp("blt", Kl, fn);
            emit(p->ld, p->cls, r, r1, R);
            emit(Oadd, Kl, r1, rsrc, getcon(boff, fn));
        }
}

void
bsinit(BSet *bs, uint n)
{
    n = (n + NBit-1) / NBit;
    bs->nt = n;
    bs->t = alloc(n * sizeof bs->t[0]);
}

MAKESURE(NBit_is_64, NBit == 64);
inline static uint
popcnt(bits b)
{
    b = (b & 0x5555555555555555) + ((b>>1) & 0x5555555555555555);
    b = (b & 0x3333333333333333) + ((b>>2) & 0x3333333333333333);
    b = (b & 0x0f0f0f0f0f0f0f0f) + ((b>>4) & 0x0f0f0f0f0f0f0f0f);
    b += (b>>8);
    b += (b>>16);
    b += (b>>32);
    return b & 0xff;
}

inline static int
firstbit(bits b)
{
    int n;

    n = 0;
    if (!(b & 0xffffffff)) {
        n += 32;
        b >>= 32;
    }
    if (!(b & 0xffff)) {
        n += 16;
        b >>= 16;
    }
    if (!(b & 0xff)) {
        n += 8;
        b >>= 8;
    }
    if (!(b & 0xf)) {
        n += 4;
        b >>= 4;
    }
    n += (char[16]){4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}[b & 0xf];
    return n;
}

uint
bscount(BSet *bs)
{
    uint i, n;

    n = 0;
    for (i=0; i<bs->nt; i++)
        n += popcnt(bs->t[i]);
    return n;
}

static inline uint
bsmax(BSet *bs)
{
    return bs->nt * NBit;
}

void
bsset(BSet *bs, uint elt)
{
    assert(elt < bsmax(bs));
    bs->t[elt/NBit] |= BIT(elt%NBit);
}

void
bsclr(BSet *bs, uint elt)
{
    assert(elt < bsmax(bs));
    bs->t[elt/NBit] &= ~BIT(elt%NBit);
}

#define BSOP(f, op)                           \
    void                                  \
    f(BSet *a, BSet *b)                   \
    {                                     \
        uint i;                       \
                                      \
        assert(a->nt == b->nt);       \
        for (i=0; i<a->nt; i++)       \
            a->t[i] op b->t[i];   \
    }

BSOP(bscopy, =)
BSOP(bsunion, |=)
BSOP(bsinter, &=)
BSOP(bsdiff, &= ~)

int
bsequal(BSet *a, BSet *b)
{
    uint i;

    assert(a->nt == b->nt);
    for (i=0; i<a->nt; i++)
        if (a->t[i] != b->t[i])
            return 0;
    return 1;
}

void
bszero(BSet *bs)
{
    memset(bs->t, 0, bs->nt * sizeof bs->t[0]);
}

/* iterates on a bitset, use as follows
 *
 *  for (i=0; bsiter(set, &i); i++)
 *      use(i);
 *
 */
int
bsiter(BSet *bs, int *elt)
{
    bits b;
    uint t, i;

    i = *elt;
    t = i/NBit;
    if (t >= bs->nt)
        return 0;
    b = bs->t[t];
    b &= ~(BIT(i%NBit) - 1);
    while (!b) {
        ++t;
        if (t >= bs->nt)
            return 0;
        b = bs->t[t];
    }
    *elt = NBit*t + firstbit(b);
    return 1;
}

void
dumpts(BSet *bs, Tmp *tmp, FILE *f)
{
    int t;

    fprintf(f, "[");
    for (t=Tmp0; bsiter(bs, &t); t++)
        fprintf(f, " %s", tmp[t].name);
    fprintf(f, " ]\n");
}