typedef struct Name Name;
struct Name {
    Ref r;
    Blk *b;
};

static void newname(Ref *r, Blk *b, vector<Name> *stk, Fn * fn, int *counter) {
    int tmp_idx = r->val;
    int i = counter[tmp_idx];
    counter[tmp_idx]++;
    Name x1;
    Ref r1 = newtmp(fn->tmp[tmp_idx].name, i, fn);
    x1.r = r1;
    x1.b = b;
    stk[tmp_idx].push_back(x1);
    *r = r1;
}

static Ref
getstk(int t, Blk *b, vector<Name> *stk)
{
    auto &n = stk[t].back();
    while (!stk[t].empty() && !dom(n.b, b)) {
        stk[t].pop_back();
    }
    n = stk[t].back();
    return n.r;
}

static void rename(Fn *fn, Blk *b, vector<Name> *stk, int *counter) {
    for (Phi *p = b->phi; p; p = p->link) {
        newname(&p->to, b, stk, fn, counter);
    }
    for (Ins *i = b->ins; i - b->ins < b->nins; i++) {
        for (auto & k : i->arg) {
            int t = k.val;
            if (fn->tmp[t].visit)
                k = getstk(t, b, stk);
        }
        newname(&i->to, b, stk, fn, counter);
    }
    Blk *succ[3], **ps, *s;
    int t, m;
    succ[0] = b->s1;
    succ[1] = b->s2 == b->s1 ? nullptr : b->s2;
    succ[2] = nullptr;
    for (ps = succ; (s = *ps); ps++)
        for (Phi *p = s->phi; p; p = p->link) {
            t = p->to.val;
            if ((t = fn->tmp[t].visit)) {
                m = p->narg++;
                p->arg[m] = getstk(t, b, stk);
                p->blk[m] = b;
            }
        }
    for (s = b->dom; s; s = s->dlink)
        rename(fn, s, stk, counter);
    for (Phi *p = b->phi; p; p = p->link) {
        stk[p->to.val].pop_back();
    }
    for (Ins *i = b->ins; i - b->ins < b->nins; i++)
        stk[i->to.val].pop_back();
}