copy.c

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

#include "all.h"

typedef struct RList RList;
struct RList {
    int t;
    RList *l;
};

static Ref
copyof(Ref r, Ref *cp)
{
    if (rtype(r) == RTmp)
        return cp[r.val];
    else
        return r;
}

static void
update(Ref r, Ref rcp, Ref *cp, RList ***pw)
{
    RList *l;

    if (!req(cp[r.val], rcp)) {
        cp[r.val] = rcp;
        l = emalloc(sizeof *l);
        l->t = r.val;
        l->l = 0;
        **pw = l;
        *pw = &l->l;
    }
}

static void
visitphi(Phi *p, Ref *cp, RList ***pw)
{
    uint a;
    Ref r, r1;

    r = R;
    for (a=0; a<p->narg; a++) {
        r1 = copyof(p->arg[a], cp);
        if (req(r1, R) || req(r1, p->to))
            continue;
        if (req(r, R) || req(r, r1))
            r = r1;
        else {
            r = p->to;
            break;
        }
    }
    update(p->to, r, cp, pw);
}

static int
iscopy(Ins *i, Ref r, Fn *fn)
{
    static bits extcpy[] = {
        [WFull] = 0,
        [Wsb] = BIT(Wsb) | BIT(Wsh) | BIT(Wsw),
        [Wub] = BIT(Wub) | BIT(Wuh) | BIT(Wuw),
        [Wsh] = BIT(Wsh) | BIT(Wsw),
        [Wuh] = BIT(Wuh) | BIT(Wuw),
        [Wsw] = BIT(Wsw),
        [Wuw] = BIT(Wuw),
    };
    bits b;
    Tmp *t;

    if (i->op == Ocopy)
        return 1;
    if (!isext(i->op) || rtype(r) != RTmp)
        return 0;
    if (i->op == Oextsw || i->op == Oextuw)
    if (i->cls == Kw)
        return 1;

    t = &fn->tmp[r.val];
    assert(KBASE(t->cls) == 0);
    if (i->cls == Kl && t->cls == Kw)
        return 0;
    b = extcpy[t->width];
    return (BIT(Wsb + (i->op-Oextsb)) & b) != 0;
}

static void
visitins(Ins *i, Ref *cp, RList ***pw, Fn *fn)
{
    Ref r;

    r = copyof(i->arg[0], cp);
    if (iscopy(i, r, fn)) {
        update(i->to, r, cp, pw);
    } else if (!req(i->to, R)) {
        assert(rtype(i->to) == RTmp);
        update(i->to, i->to, cp, pw);
    }
}

static void
subst(Ref *r, Ref *cp)
{
    assert((rtype(*r) != RTmp || !req(copyof(*r, cp), R)) && "ssa invariant broken");
    *r = copyof(*r, cp);
}

void
copy(Fn *fn)
{
    Blk *b;
    Ref *cp, r;
    RList *w, *w1, **pw;
    Use *u, *u1;
    Ins *i;
    Phi *p, **pp;
    uint a;
    int t;

    w = 0;
    pw = &w;
    cp = emalloc(fn->ntmp * sizeof cp[0]);
    for (b=fn->start; b; b=b->link) {
        for (p=b->phi; p; p=p->link)
            visitphi(p, cp, &pw);
        for (i=b->ins; i-b->ins < b->nins; i++)
            visitins(i, cp, &pw, fn);
    }
    while ((w1=w)) {
        t = w->t;
        u = fn->tmp[t].use;
        u1 = u + fn->tmp[t].nuse;
        for (; u<u1; u++)
            switch (u->type) {
            case UPhi:
                visitphi(u->u.phi, cp, &pw);
                break;
            case UIns:
                visitins(u->u.ins, cp, &pw, fn);
                break;
            case UJmp:
                break;
            default:
                die("invalid use %d", u->type);
            }
        w = w->l;
        free(w1);
    }
    for (b=fn->start; b; b=b->link) {
        for (pp=&b->phi; (p=*pp);) {
            r = cp[p->to.val];
            if (!req(r, p->to)) {
                *pp = p->link;
                continue;
            }
            for (a=0; a<p->narg; a++)
                subst(&p->arg[a], cp);
            pp=&p->link;
        }
        for (i=b->ins; i-b->ins < b->nins; i++) {
            r = copyof(i->to, cp);
            if (!req(r, i->to)) {
                *i = (Ins){.op = Onop};
                continue;
            }
            for (a=0; a<2; a++)
                subst(&i->arg[a], cp);
        }
        subst(&b->jmp.arg, cp);
    }
    if (debug['C']) {
        fprintf(stderr, "\n> Copy information:");
        for (t=Tmp0; t<fn->ntmp; t++) {
            if (req(cp[t], R)) {
                fprintf(stderr, "\n%10s not seen!",
                    fn->tmp[t].name);
            }
            else if (!req(cp[t], TMP(t))) {
                fprintf(stderr, "\n%10s copy of ",
                    fn->tmp[t].name);
                printref(cp[t], fn, stderr);
            }
        }
        fprintf(stderr, "\n\n> After copy elimination:\n");
        printfn(fn, stderr);
    }
    free(cp);
}