path: root/ssa.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "ast.h"
#include "ssa.h"
#include "mips.h"
#define NEW(type) ((type *)malloc(sizeof(type)))
#define DBLINK(from, to) ((from)->next = (to))->prev = (from)

static CGraph cfg, dtree;
static CBlock_t blks[MAX_BLOCK];
static COList_t raw_defs;   /* defintion of all vars and tmps */
static int bcnt;            /* block counter */
static int tcnt;            /* temporary counter */

static int quiet;
static int gbbase;
static CBlock_t entry;
static COList_t defs;       /* all defintions that have actual effects */

/* for code generation */
CFuncIR_t func_ir;

COpr_t copr_create(void) {
    COpr_t opr = NEW(COpr);
    opr->type = NULL;
    opr->cval = NULL;
    opr->range = NULL;
    opr->same = opr;
    opr->dep = 0;
    opr->mod = 0;
    opr->par = opr;
    return opr;
}

CInst_t cinst_create(void) {
    CInst_t inst = NEW(CInst);
    inst->dest = NULL;
    inst->src1 = NULL;
    inst->src2 = NULL;
    inst->sysp = 0;
    return inst;
}

CBlock_t cblock_create(int inc) {
    CBlock_t cblk = NEW(CBlock);
    CInst_t dum = cinst_create();
    CPhi_t pdum = NEW(CPhi);
    dum->prev = dum;
    dum->next = dum;
    pdum->prev = pdum;
    pdum->next = pdum;
    cblk->insts = dum;
    cblk->phis = pdum;
    cblk->next = NULL;
    if (inc)
        cblk->id = bcnt++;
    cblk->ref = 0;
    return cblk;
}

void cblock_append(CBlock_t cblk, CInst_t inst) {
    CInst_t head = cblk->insts;
    (inst->prev = head->prev)->next = inst;
    (inst->next = head)->prev = inst;
}

void cblock_pushfront(CBlock_t cblk, CInst_t inst) {
    CInst_t head = cblk->insts;
    (inst->next = head->next)->prev = inst;
    (inst->prev = head)->next = inst;
}

void cblock_pappend(CBlock_t cblk, CPhi_t phi) {
    CPhi_t head = cblk->phis;
    (phi->prev = head->prev)->next = phi;
    (phi->next = head)->prev = phi;
}

void cblock_popback(CBlock_t cblk) {
    CInst_t last = cblk->insts->prev;
    last->next->prev = last->prev;
    last->prev->next = last->next;
}

void cblock_popfront(CBlock_t cblk) {
    CInst_t first = cblk->insts->next;
    first->next->prev = first->prev;
    first->prev->next = first->next;
}

CInst_t cblock_getback(CBlock_t cblk) {
    CInst_t res = cblk->insts->prev;
    return res != cblk->insts ? res : NULL;
}

int cblock_isempty(CBlock_t cblk) {
    return cblk->insts->prev == cblk->insts;
}

CVar_t ctmp_create(void) {
    static char buff[MAX_NAMELEN];
    sprintf(buff, "t%d", tcnt++);
    return cvar_create(strdup(buff), NULL, NULL);
}

void ctmp_destroy(CVar_t type) {
    /* allocated dynamically */
    free(type->name);
    free(type);
}

void cfg_clear(void) {
    int i;
    for (i = 0; i < MAX_BLOCK; i++)
    {
        CEdge *p, *np;
        for (p = cfg.head[i]; p; p = np)
        {
            np = p->next;
            free(p);
        }
        cfg.head[i] = NULL;
        for (p = cfg.rhead[i]; p; p = np)
        {
            np = p->next;
            free(p);
        }
        cfg.rhead[i] = NULL;
    }
}

void dtree_clear(void) {
    int i;
    CEdge *p, *np;
    for (i = 0; i < MAX_BLOCK; dtree.head[i++] = NULL)
        for (p = dtree.head[i]; p; p = np)
        {
            np = p->next;
            free(p);
        }
}

void cfg_add_edge(CBlock_t from, CBlock_t to) {
    int fid = from->id, tid = to->id;
#ifdef CIBIC_DEBUG
    fprintf(stderr, "%d -> %d\n", from->id, to->id);
#endif
    CEdge *e = NEW(CEdge), *re = NEW(CEdge);
    e->to = to;
    e->next = cfg.head[fid];
    cfg.head[fid] = e;

    re->to = from;
    re->next = cfg.rhead[tid];
    cfg.rhead[tid] = re;
}

void dtree_add_edge(CBlock_t from, CBlock_t to) {
#ifdef CIBIC_DEBUG
    fprintf(stderr, "%d d-> %d\n", from->id, to->id);
#endif
    int id = from->id;
    CEdge *e = NEW(CEdge);
    e->to = to;
    e->next = dtree.head[id];
    dtree.head[id] = e;
}

void copr_print(FILE *f, COpr_t opr) {
    switch (opr->kind)
    {
        case VAR: 
                  fprintf(f, "%s_%d", opr->info.var->name, opr->sub);
                  break;
        case TMP: fprintf(f, "%s", opr->info.var->name);
                  break;
        case IMM: fprintf(f, "%d", opr->info.imm);
                  break;
        case IMMS: fprintf(f, "\"%s\"", opr->info.cstr->str);
                  break;
        case IMMF: fprintf(f, "%s", opr->info.str);
                  break;
    }
}

void cinst_print(FILE *f, CInst_t inst) {
    switch (inst->op)
    {
        case LOAD:
            fprintf(f, "load ");
            copr_print(f, inst->dest);
            break;
        case MOVE:
            copr_print(f, inst->dest);
            fprintf(f, " = ");
            copr_print(f, inst->src1);
            break;
        case BEQ:
            fprintf(f, "if (");
            copr_print(f, inst->src1);
            fprintf(f, " == ");
            copr_print(f, inst->src2);
            fprintf(f, ") goto _L");
            copr_print(f, inst->dest);
            break;
        case BNE:
            fprintf(f, "if (");
            copr_print(f, inst->src1);
            fprintf(f, " != ");
            copr_print(f, inst->src2);
            fprintf(f, ") goto _L");
            copr_print(f, inst->dest);
            break;
        case GOTO:
            fprintf(f, "goto _L");
            copr_print(f, inst->dest);
            break;
        case ARR:
            copr_print(f, inst->dest);
            fprintf(f, " = ");
            copr_print(f, inst->src1);
            fprintf(f, "[");
            copr_print(f, inst->src2);
            fprintf(f, "]");
            break;
        case NEG:
            copr_print(f, inst->dest);
            fprintf(f, " = -");
            copr_print(f, inst->src1);
            break;
        case WARR:
            copr_print(f, inst->dest);
            fprintf(f, "[");
            copr_print(f, inst->src2);
            fprintf(f, "] = ");
            copr_print(f, inst->src1);
            break;
        case PUSH:
            fprintf(f, "push ");
            copr_print(f, inst->src1);
            break;
        case CALL:
            copr_print(f, inst->dest);
            fprintf(f, " = call ");
            copr_print(f, inst->src1);
            break;
        case RET:
            if (inst->src1)
            {
                fprintf(f, "return ");
                copr_print(f, inst->src1);
            }
            else fprintf(f, "return");
            break;
        case ADDR:
            copr_print(f, inst->dest);
            fprintf(f, " = addr ");
            copr_print(f, inst->src1);
            break;
        default:
            {
                const char *op;
                switch (inst->op)
                {
                    case MUL: op = "*"; break;
                    case DIV: op = "/"; break;
                    case MOD: op = "%"; break;
                    case ADD: op = "+"; break;
                    case SUB: op = "-"; break;
                    case SHL: op = "<<"; break;
                    case SHR: op = ">>"; break;
                    case AND: op = "&"; break;
                    case XOR: op = "^"; break;
                    case OR: op = "|"; break;
                    case LT: op = "<"; break;
                    case GT: op = ">"; break;
                    case LE: op = "<="; break;
                    case GE: op = ">="; break;
                    case EQ: op = "=="; break;
                    case NE: op = "!="; break;
                    case NOR: op = "nor"; break;
                    default: ;
                }
                copr_print(f, inst->dest);
                fprintf(f, " = ");
                copr_print(f, inst->src1);
                fprintf(f, " %s ", op);
                copr_print(f, inst->src2);
            }
    }
    fprintf(f, "\n");
}

void cphi_print(CPhi_t phi, CBlock_t blk) {
    int i;
    fprintf(stderr, "%s_%d = phi", phi->dest->info.var->name,
                                    phi->dest->sub);
    for (i = 0; i < blk->pred; i++)
        fprintf(stderr, " %s_%d", phi->oprs[i]->info.var->name,
                                    phi->oprs[i]->sub);
    fprintf(stderr, "\n");
}

void cblock_print(CBlock_t blk) {
    fprintf(stderr, "_L%d:\n", blk->id + gbbase);
    {
        CPhi_t p, sp = blk->phis;
        for (p = sp->next; p != sp; p = p->next)
        {
            fprintf(stderr, "\t");
            cphi_print(p, blk);
        }
    }
    {
        CInst_t p, sp = blk->insts;
        for (p = sp->next; p != sp; p = p->next)
        {
            fprintf(stderr, "%02d\t", p->id);
            cinst_print(stderr, p);
        }
    }
}
void ssa_func_print(CBlock_t p) {
    for (; p; p = p->next)
        cblock_print(p);
}
void ssa_func(CType_t);
void ssa_generate(int quiet) {
    CTList_t f;
    CFuncIR_t cf;
    func_ir = NULL;
    for (f = funcs; f; f = f->next)
    {
        cf = NEW(CFuncIR);
        ssa_func(cf->func = f->type);
        cf->gbbase = gbbase;
        cf->defs = defs;
        cf->entry = entry;
        cf->next = func_ir;
        func_ir = cf;
        gbbase += bcnt;
        bcnt = 0;
    }
    if (!quiet)
    {
        for (cf = func_ir; cf; cf = cf->next)
        {
            fprintf(stderr, "%s:\n", cf->func->name);
            ssa_func_print(cf->entry);
        }
    }
}

#define POINTER_CONV(inst) \
do { \
    if (rt->type == CARR) \
    { \
        /* convert to pointer type */ \
        CType_t a; \
        a = ctype_create("", CPTR, p); \
        a->rec.ref = rt->rec.arr.elem; \
        (inst)->op = ADD; \
        (inst)->dest->type = a;  \
    } \
    else if (rt->type == CSTRUCT || rt->type == CUNION) \
        (inst)->op = ADD; \
    else (inst)->op = ARR; \
} while (0)


COpr_t ssa_exp_(CNode *p, CBlock_t *, CInst_t, CBlock_t);
COpr_t ssa_postfix(CNode *p, CBlock_t *cur, CInst_t lval, CBlock_t succ) {
    CNode *post = p->chd->next;
    CType_t rt = p->ext.type;
    CInst_t base = cinst_create();
    switch (post->rec.subtype)
    {
        case POSTFIX_ARR:
            {
                CInst_t off = cinst_create();
                off->dest = copr_create();
                off->dest->kind = TMP;
                off->dest->info.var = ctmp_create();
                off->dest->type = post->chd->ext.type;
                off->op = MUL;
                off->src1 = ssa_exp_(post->chd, cur, NULL, succ);
                off->src2 = copr_create();
                off->src2->kind = IMM;
                off->src2->info.imm = calc_size(rt);
                cblock_append(*cur, off);

                base->dest = copr_create();
                base->dest->kind = TMP;
                base->dest->info.var = ctmp_create();
                base->dest->type = rt;
                base->src1 = ssa_exp_(p->chd, cur, NULL, succ);
                base->src2 = off->dest;
                POINTER_CONV(base);
            }
            break;
        case POSTFIX_DOT:
            {
                base->dest = copr_create();
                base->dest->kind = TMP;
                base->dest->info.var = ctmp_create();
                base->dest->type = rt;
                base->src1 = ssa_exp_(p->chd, cur, NULL, succ);
                base->src2 = copr_create();
                base->src2->kind = IMM;
                base->src2->info.imm = p->ext.offset;
                POINTER_CONV(base);
            }
            break;
        case POSTFIX_PTR:
            {
                base->dest = copr_create();
                base->dest->kind = TMP;
                base->dest->info.var = ctmp_create();
                base->dest->type = rt;
                base->src1 = ssa_exp_(p->chd, cur, NULL, succ);
                base->src2 = copr_create();
                base->src2->kind = IMM;
                base->src2->info.imm = p->ext.offset;
                POINTER_CONV(base);
            }
            break;
        case POSTFIX_CALL:
            {
                CNode *arg = post->chd->chd;
                CInst h;
                CInst_t t = &h, n;
                base->op = CALL;
                base->src1 = ssa_exp_(p->chd, cur, lval, succ);
                base->dest = copr_create();
                base->dest->kind = TMP;
                base->dest->info.var = ctmp_create();
                base->dest->type = rt;
                for (; arg; arg = arg->next)
                {
                    CInst_t pi = cinst_create();
                    pi->op = PUSH;
                    pi->src1 = ssa_exp_(arg, cur, lval, succ);
                    t->next = pi;
                    t = pi;
                }
                t->next = NULL;
                for (t = h.next; t; t = n)
                {
                    n = t->next;
                    cblock_append(*cur, t);
                }
            }
            break;
        default:
            {
                CInst_t tins = cinst_create();
                ssa_exp_(p->chd, cur, tins, succ);
                base->op = post->rec.subtype == OPT_INC ? ADD : SUB;
                base->src2 = copr_create();
                base->src2->kind = IMM;
                base->src2->info.imm = 1;
                base->src1 = ssa_exp_(p->chd, cur, NULL, succ);
                if (tins->op == MOVE)
                {
                    base->dest = tins->dest;
                    cblock_append(succ, base);
                    free(tins);
                }
                else
                {
                    CInst_t tins2 = cinst_create();
                    base->dest = copr_create();
                    base->dest->kind = TMP;
                    base->dest->info.var = ctmp_create();
                    base->dest->type = rt;
                    tins->src1 = base->dest;
                    tins2->op = ARR;
                    tins2->src1 = tins->dest;
                    tins2->src2 = tins->src2;
                    tins2->dest = copr_create();
                    tins2->dest->kind = TMP;
                    tins2->dest->info.var = ctmp_create();
                    tins2->dest->type = rt;

                    cblock_append(succ, base);
                    cblock_append(succ, tins);
                    cblock_append(succ, tins2);
                }
                return base->src1;
            }
            break;
    }

    if (lval)
    {
        lval->op = WARR;
        lval->dest = base->src1;
        lval->src2 = base->src2;
        lval->wtype = p->ext.type;
        free(base);
        return lval->dest;
    }
    cblock_append(*cur, base);
    return base->dest;
}

CInst_t compress_branch(COpr_t r, CBlock_t blk, int rev) {
    int flag = -1;
    CInst_t b;
    if (r->kind == TMP)
    {
        b = cblock_getback(blk);
        if (b)
        {
            assert(r == b->dest);
            if (b->op == EQ)
                flag = 0;
            else if (b->op == NE)
                flag = 1;
        }
    }
    if (flag != -1)
        b->op = flag ? BNE : BEQ;
    else
    {
        b = cinst_create();
        b->op = BNE;
        b->src1 = r;
        b->src2 = copr_create();
        b->src2->kind = IMM;
        b->src2->info.imm = 0;
        cblock_append(blk, b);
    }
    b->op ^= rev;
    b->dest = copr_create();
    b->dest->kind = IMM;
    return b;
}

static CNode *opt_if = NULL;
static CBlock_t opt_if_loop_exit = NULL;

CBlock_t ssa_stmt(CNode *, CBlock_t, CBlock_t);
#define IS_PTR(tt) ((tt) == CPTR || (tt) == CARR)
COpr_t ssa_exp(CNode *, CBlock_t *, int);
COpr_t ssa_exp_(CNode *p, CBlock_t *cur, CInst_t lval, CBlock_t succ) {/*{{{*/
    COpr_t res;
    CInst_t inst = cinst_create();
    switch (p->type)
    {
        case NOP: ; break;
        case ID:
            res = copr_create();
            res->kind = VAR;
            res->info.var = p->ext.var;
            res->type = p->ext.type;
            {
                CVar_t var = res->info.var;
                CType_t type = var->type;
                if (type->type == CPTR &&
                        type->rec.ref->type == CFUNC)
                {
                    char *name = type->rec.ref->name;
                    if (*name != '\0')
                    {
                        res->kind = IMMF;
                        res->info.str = name;
                    }
                }
            }

            if (lval)
            {
                lval->op = MOVE;
                lval->dest = res;
            }
            break;
        case STR:
            res = copr_create();
            res->kind = IMMS;
            res->info.cstr = (CSList_t)(p->ext.const_val);
            break;
        default:
            if (p->ext.is_const)
            {
                res = copr_create();
                res->kind = IMM;
                res->info.imm = p->ext.const_val;
            }
            else
            {
                int op = p->rec.subtype;
                int rec = 1, auto_dest = 1;

                if (op == ',')
                {
                    ssa_exp(p->chd, cur, 1);
                    return ssa_exp_(p->chd->next, cur, NULL, succ);
                }
                else if (op == '=')
                {
                    inst->src1 = ssa_exp_(p->chd->next, cur, NULL, succ);
                    ssa_exp_(p->chd, cur, inst, succ);
                    if (inst->op == MOVE)
                    {
                        CInst_t last = cblock_getback(*cur);
                        if (last && last->dest->kind == TMP
                                && last->dest == inst->src1)
                        {
                            free(last->dest);
                            last->dest = inst->dest;
                            free(inst);
                            return last->dest;
                        }
                        else 
                        {
                            cblock_append(*cur, inst);
                            return inst->dest;
                        }
                    }
                    else
                    {
                        CInst_t tins = cinst_create();
                        cblock_append(*cur, inst);
                        tins->op = ARR;
                        tins->src1 = inst->dest;    /* base */
                        tins->src2 = inst->src2;    /* displacement */
                        tins->dest = copr_create();
                        tins->dest->kind = TMP;
                        tins->dest->info.var = ctmp_create();
                        tins->dest->type = p->ext.type;
                        cblock_append(*cur, tins);
                        return tins->dest;
                    }
                }
                else if (op == '*' && !p->chd->next)
                {
                    if (lval)
                    {
                        lval->op = WARR;
                        lval->dest = ssa_exp_(p->chd, cur, NULL, succ);
                        lval->src2 = copr_create();
                        lval->src2->kind = IMM;
                        lval->src2->info.imm = 0;
                        lval->wtype = p->ext.type;
                        return lval->dest;
                    }
                    else
                    {
                        CType_t rt = p->ext.type;
                        inst->src1 = ssa_exp_(p->chd, cur, NULL, succ);
                        inst->src2 = copr_create();
                        inst->src2->kind = IMM;
                        inst->src2->info.imm = 0;
                        inst->dest = copr_create();
                        inst->dest->kind = TMP;
                        inst->dest->info.var = ctmp_create();
                        inst->dest->type = rt;
                        POINTER_CONV(inst);
                        cblock_append(*cur, inst);
                        return inst->dest;
                    }
                }
                else if (op == OPT_AND)
                {
                    CBlock_t else_h = cblock_create(1), else_t = else_h,
                             one_h = cblock_create(1), one_t = one_h,
                             zero_h = cblock_create(1), zero_t = zero_h,
                             next_blk = cblock_create(1), sblk;
                    COpr_t r0, r1, ri;
                    CInst_t b, a0, a1;
                    CPhi_t m = NEW(CPhi);
                    CNode *t;
                    if (opt_if)
                    {
                        CNode *body1 = opt_if->chd->next, *body2 = body1->next;
                        one_t = ssa_stmt(body1, one_h, opt_if_loop_exit);
                        if (body2->type != NOP)
                            zero_t = ssa_stmt(body2, zero_h, opt_if_loop_exit);
                        opt_if = NULL;
                    }
                    else
                    {
                        /* constant opt */
                        a0 = cinst_create();
                        a0->op = MOVE;
                        a0->dest = copr_create();
                        a0->dest->kind = TMP;
                        a0->dest->info.var = ctmp_create();
                        a0->dest->type = p->ext.type; /* int */
                        a0->src1 = copr_create();
                        a0->src1->kind = IMM;
                        a0->src1->info.imm = 0;
                        cblock_append(zero_h, a0);

                        a1 = cinst_create();
                        a1->op = MOVE;
                        a1->dest = copr_create();
                        a1->dest->kind = TMP;
                        a1->dest->info.var = ctmp_create();
                        a1->dest->type = p->ext.type;
                        a1->src1 = copr_create();
                        a1->src1->kind = IMM;
                        a1->src1->info.imm = 1;
                        cblock_append(one_h, a1);

                        m->dest = copr_create();
                        m->dest->kind = TMP;
                        m->dest->info.var = ctmp_create();
                        m->dest->type = p->ext.type;
                        m->oprs = (COpr_t *)malloc(sizeof(COpr_t) * 2);
                        m->oprs[0] = a0->dest;
                        m->oprs[1] = a1->dest;
                        cblock_pappend(next_blk, m);
                    }

                    r1 = ssa_exp_(p->chd->next, &else_t, NULL, succ);
                    compress_branch(r1, else_t, 1)->dest->info.imm = zero_h->id + gbbase;
                    zero_h->ref = 1;

                    sblk = else_h;
                    for (t = p->chd; t->rec.subtype == OPT_AND; t = t->chd)
                    {
                        CBlock_t c_h = cblock_create(1), c_t = c_h;
                        ri = ssa_exp_(t->chd->next, &c_t, NULL, succ);
                        compress_branch(ri, c_t, 1)->dest->info.imm = zero_h->id + gbbase;
                        cfg_add_edge(c_t, zero_h);  /* tail */
                        DBLINK(c_t, sblk);
                        cfg_add_edge(c_t, sblk);      /* connect to header */
                        sblk = c_h;
                    }

                    r0 = ssa_exp_(t, cur, NULL, succ);
                    compress_branch(r0, *cur, 1)->dest->info.imm = zero_h->id + gbbase;
                    cfg_add_edge(*cur, zero_h);
                    DBLINK(*cur, sblk);
                    cfg_add_edge(*cur, sblk);

                    b = cinst_create();
                    b->op = GOTO;
                    b->dest = copr_create();
                    b->dest->kind = IMM;
                    b->dest->info.imm = next_blk->id + gbbase;
                    cblock_append(one_t, b);
                    next_blk->ref = 1;

                    DBLINK(else_t, one_h);
                    DBLINK(one_t, zero_h);
                    DBLINK(zero_t, next_blk);

                    cfg_add_edge(else_t, one_h);
                    cfg_add_edge(else_t, zero_h);
                    cfg_add_edge(one_t, next_blk);
                    cfg_add_edge(zero_t, next_blk);

                    *cur = next_blk;
                    return m->dest;
                }
                else if (op == OPT_OR)
                {
                    CBlock_t else_h = cblock_create(1), else_t = else_h,
                             one_h = cblock_create(1), one_t = one_h,
                             zero_h = cblock_create(1), zero_t = zero_h,
                             next_blk = cblock_create(1), sblk;
                    COpr_t r0, r1, ri;
                    CInst_t b, a0, a1;
                    CPhi_t m = NEW(CPhi);
                    CNode *t;
                    if (opt_if)
                    {
                        CNode *body1 = opt_if->chd->next, *body2 = body1->next;
                        one_t = ssa_stmt(body1, one_h, opt_if_loop_exit);
                        if (body2->type != NOP)
                            zero_t = ssa_stmt(body2, zero_h, opt_if_loop_exit);
                        opt_if = NULL;
                    }
                    else
                    {
                        /* constant opt */
                        a0 = cinst_create();
                        a0->op = MOVE;
                        a0->dest = copr_create();
                        a0->dest->kind = TMP;
                        a0->dest->info.var = ctmp_create();
                        a0->dest->type = p->ext.type; /* int */
                        a0->src1 = copr_create();
                        a0->src1->kind = IMM;
                        a0->src1->info.imm = 0;
                        cblock_append(zero_h, a0);

                        a1 = cinst_create();
                        a1->op = MOVE;
                        a1->dest = copr_create();
                        a1->dest->kind = TMP;
                        a1->dest->info.var = ctmp_create();
                        a1->dest->type = p->ext.type;
                        a1->src1 = copr_create();
                        a1->src1->kind = IMM;
                        a1->src1->info.imm = 1;
                        cblock_append(one_h, a1);

                        m->dest = copr_create();
                        m->dest->kind = TMP;
                        m->dest->info.var = ctmp_create();
                        m->dest->type = p->ext.type;
                        m->oprs = (COpr_t *)malloc(sizeof(COpr_t) * 2);
                        m->oprs[0] = a1->dest;
                        m->oprs[1] = a0->dest;
                        cblock_pappend(next_blk, m);
                    }

                    r1 = ssa_exp_(p->chd->next, &else_t, NULL, succ);
                    compress_branch(r1, else_t, 0)->dest->info.imm = one_h->id + gbbase;
                    one_h->ref = 1;

                    sblk = else_h;
                    for (t = p->chd; t->rec.subtype == OPT_OR; t = t->chd)
                    {
                        CBlock_t c_h = cblock_create(1), c_t = c_h;
                        ri = ssa_exp_(t->chd->next, &c_t, NULL, succ);
                        compress_branch(ri, c_t, 0)->dest->info.imm = one_h->id + gbbase;
                        cfg_add_edge(c_t, one_h);  /* tail */
                        DBLINK(c_t, sblk);
                        cfg_add_edge(c_t, sblk);      /* connect to header */
                        sblk = c_h;
                    }

                    r0 = ssa_exp_(t, cur, NULL, succ);
                    compress_branch(r0, *cur, 0)->dest->info.imm = one_h->id + gbbase;
                    cfg_add_edge(*cur, one_h);
                    DBLINK(*cur, sblk);
                    cfg_add_edge(*cur, sblk);

                    b = cinst_create();
                    b->op = GOTO;
                    b->dest = copr_create();
                    b->dest->kind = IMM;
                    b->dest->info.imm = next_blk->id + gbbase;
                    cblock_append(zero_t, b);
                    next_blk->ref = 1;

                    DBLINK(else_t, zero_h);
                    DBLINK(zero_t, one_h);
                    DBLINK(one_t, next_blk);

                    cfg_add_edge(else_t, zero_h);
                    cfg_add_edge(else_t, one_h);
                    cfg_add_edge(zero_t, next_blk);
                    cfg_add_edge(one_t, next_blk);

                    *cur = next_blk;
                    return m->dest;
                }
                else if (op == '+' && IS_PTR(p->ext.type->type))
                {
                    COpr_t lhs = ssa_exp_(p->chd, cur, lval, succ),
                           rhs = ssa_exp_(p->chd->next, cur, lval, succ);
                    CInst_t index = cinst_create();
                    CType_t et = p->chd->ext.type;
                    if (et->type == CPTR)
                        et = et->rec.ref;
                    else
                        et = et->rec.arr.elem;
                    index->op = MUL;
                    index->dest = copr_create();
                    index->dest->kind = TMP;
                    index->dest->info.var = ctmp_create();
                    index->dest->type = p->chd->next->ext.type;
                    index->src1 = rhs;
                    index->src2 = copr_create();
                    index->src2->kind = IMM;
                    index->src2->info.imm = calc_size(et);

                    inst->op = ADD;
                    inst->dest = copr_create();
                    inst->dest->kind = TMP;
                    inst->dest->info.var = ctmp_create();
                    inst->dest->type = p->ext.type;
                    inst->src1 = lhs;
                    inst->src2 = index->dest;
                    cblock_append(*cur, index);
                    cblock_append(*cur, inst);
                    return inst->dest;
                }
                else if (op == '-' && IS_PTR(p->chd->ext.type->type))
                {
                    CType_t nt = p->chd->next->ext.type;
                    CType_t et = p->chd->ext.type;
                    COpr_t lhs = ssa_exp_(p->chd, cur, lval, succ),
                           rhs = ssa_exp_(p->chd->next, cur, lval, succ);
                    CInst_t diff = cinst_create();

                    if (et->type == CPTR)
                        et = et->rec.ref;
                    else
                        et = et->rec.arr.elem;

                    if (IS_PTR(nt->type))
                    {
                        diff->op = SUB;
                        diff->dest = copr_create();
                        diff->dest->kind = TMP;
                        diff->dest->info.var = ctmp_create();
                        diff->dest->type = p->ext.type;
                        diff->src1 = lhs;
                        diff->src2 = rhs;

                        inst->op = DIV;
                        inst->dest = copr_create();
                        inst->dest->kind = TMP;
                        inst->dest->info.var = ctmp_create();
                        inst->dest->type = p->ext.type;
                        inst->src1 = diff->dest;
                        inst->src2 = copr_create();
                        inst->src2->kind = IMM;
                        inst->src2->info.imm = calc_size(et);
                    }
                    else
                    {
                        diff->op = MUL;
                        diff->dest = copr_create();
                        diff->dest->kind = TMP;
                        diff->dest->info.var = ctmp_create();
                        diff->dest->type = p->chd->next->ext.type;
                        diff->src1 = rhs;
                        diff->src2 = copr_create();
                        diff->src2->kind = IMM;
                        diff->src2->info.imm = calc_size(et);

                        inst->op = SUB;
                        inst->dest = copr_create();
                        inst->dest->kind = TMP;
                        inst->dest->info.var = ctmp_create();
                        inst->dest->type = p->ext.type;
                        inst->src1 = lhs;
                        inst->src2 = diff->dest;
                    }
                    cblock_append(*cur, diff);
                    cblock_append(*cur, inst);
                    return inst->dest;
                }
                else if (op == '&' && !p->chd->next)
                {
                    ssa_exp_(p->chd, cur, inst, succ);
                    if (inst->op == MOVE)
                    {
                        inst->op = ADDR;
                        inst->src1 = inst->dest;
                    }
                    else
                    {
                        inst->op = ADD;
                        inst->src1 = inst->dest;
                    }
                    inst->dest = copr_create();
                    inst->dest->kind = TMP;
                    inst->dest->info.var = ctmp_create();
                    inst->dest->type = p->ext.type;
                    cblock_append(*cur, inst);
                    return inst->dest;
                }
                else
                {
                    int unary = 0;
                    inst->op = (unsigned)-1;
                    switch (op)
                    {
                        case ASS_MUL: inst->op = MUL; break;
                        case ASS_DIV: inst->op = DIV; break;
                        case ASS_MOD: inst->op = MOD; break;
                        case ASS_ADD: inst->op = ADD; break;
                        case ASS_SUB: inst->op = SUB; break;
                        case ASS_SHL: inst->op = SHL; break;
                        case ASS_SHR: inst->op = SHR; break;
                        case ASS_AND: inst->op = AND; break;
                        case ASS_XOR: inst->op = XOR; break;
                        case ASS_OR:  inst->op = OR; break;
                        case OPT_INC: inst->op = ADD; unary = 1; break;
                        case OPT_DEC: inst->op = SUB; unary = 1; break;
                    }
                    if (inst->op != (unsigned)-1)
                    {
                        CInst_t tins = cinst_create();
                        ssa_exp_(p->chd, cur, tins, succ);                 /* as lval */
                        inst->src1 = ssa_exp_(p->chd, cur, NULL, succ);    /* as rval */
                        if (unary)
                        {
                            inst->src2 = copr_create();
                            inst->src2->kind = IMM;
                            inst->src2->info.imm = 1;
                        }
                        else
                            inst->src2 = ssa_exp_(p->chd->next, cur, NULL, succ);
                        if (tins->op == MOVE)
                        {
                            inst->dest = tins->dest;
                            cblock_append(*cur, inst);
                            free(tins);
                            return inst->dest;
                        }
                        else
                        {
                            CInst_t tins2 = cinst_create();
                            inst->dest = copr_create();
                            inst->dest->kind = TMP;
                            inst->dest->info.var = ctmp_create();
                            inst->dest->type = p->ext.type;
                            tins->src1 = inst->dest;
                            tins2->op = ARR;
                            tins2->src1 = tins->dest;    /* base */
                            tins2->src2 = tins->src2;    /* displacement */
                            tins2->dest = copr_create();
                            tins2->dest->kind = TMP;
                            tins2->dest->info.var = ctmp_create();
                            tins2->dest->type = p->ext.type;
                            cblock_append(*cur, inst);
                            cblock_append(*cur, tins);
                            cblock_append(*cur, tins2);
                            return tins2->dest;
                        }
                    }
                }

                switch (op)
                {
                    case EXP_CAST:
                        {
                            res = ssa_exp_(p->chd->next, cur, lval, succ);
                            res->type = p->ext.type;
                            free(inst);
                            return res;
                        }
                    case EXP_POSTFIX:
                        free(inst);
                        return ssa_postfix(p, cur, lval, succ);
                    /* KW_SIZEOF is eliminated during semantic checking */
                    default:
                        {
                            COpr_t lhs = ssa_exp_(p->chd, cur, lval, succ),
                                   rhs = NULL;
                            if (p->chd->next)
                                rhs = ssa_exp_(p->chd->next, cur, lval, succ);

                            inst->src1 = lhs;
                            inst->src2 = rhs;
                            switch (op)
                            {
                                case OPT_SHL: inst->op = SHL; break;
                                case OPT_SHR: inst->op = SHR; break;
                                case '|': inst->op = OR; break;
                                case '^': inst->op = XOR; break;
                                case OPT_EQ: inst->op = EQ; break;
                                case OPT_NE: inst->op = NE; break;
                                case '<': inst->op = LT; break;
                                case '>': inst->op = GT; break;
                                case OPT_LE: inst->op = LE; break;
                                case OPT_GE: inst->op = GE; break;
                                case '/': inst->op = DIV; break;
                                case '%': inst->op = MOD; break;
                                case '*':
                                          inst->op = MUL;
                                          break;
                                case '&':
                                          inst->op = AND;
                                          break;
                                case '+':
                                          if (p->chd->next)
                                              inst->op = ADD;
                                          else res = lhs;
                                          break;
                                case '-':
                                          if (p->chd->next)
                                              inst->op = SUB;
                                          else
                                          {
                                              inst->op = NEG;
                                              inst->src1 = lhs;
                                          }
                                          break;
                                case '~':
                                          inst->op = NOR;
                                          inst->src1 = lhs;
                                          inst->src2 = copr_create();
                                          inst->src2->kind = IMM;
                                          inst->src2->info.imm = 0;
                                          break;
                                case '!':
                                          inst->op = EQ;
                                          inst->src1 = lhs;
                                          inst->src2 = copr_create();
                                          inst->src2->kind = IMM;
                                          inst->src2->info.imm = 0;
                                          break;
                                default:
                                          auto_dest = 0;
                            }
                            if (rec)
                            {
                                if (auto_dest)
                                {
                                    inst->dest = copr_create();
                                    inst->dest->kind = TMP;
                                    inst->dest->info.var = ctmp_create();
                                    inst->dest->type = p->ext.type;
                                }
                                cblock_append(*cur, inst);
                                res = inst->dest;
                            }
                        }
                }
            }
    }
    return res;
}/*}}}*/

COpr_t ssa_exp(CNode *p, CBlock_t *cur, int discard_last) {
    CBlock_t succ = cblock_create(0);
    COpr_t res = ssa_exp_(p, cur, NULL, succ);
    CInst_t last; 
    {
        CInst_t head = succ->insts, t;
        while (head->next != head)
        {
            t = head->next;
            cblock_popfront(succ);
            cblock_append(*cur, t);
        }
        free(succ);
    }
    last = cblock_getback(*cur);
    if (discard_last && last 
                    && last->dest->kind == TMP
                    && last->op != CALL) /* temporary not used */
    {
        ctmp_destroy(last->dest->info.var);
        cblock_popback(*cur);
        free(last);
    }
    return res;
}

CBlock_t ssa_while(CNode *p, CBlock_t cur) {/*{{{*/
    CNode *exp = p->chd;
    CBlock_t loop_h = cblock_create(1), loop_t,
             cond_h= cblock_create(1), cond_t = cond_h,
             next_blk = cblock_create(1);
    CInst_t j_inst = cinst_create();
    COpr_t e = ssa_exp(exp, &cond_t, 0);
    compress_branch(e, cond_t, 0)->dest->info.imm = loop_h->id + gbbase;
    loop_h->ref = 1;

    DBLINK(cond_t, next_blk);
    loop_t = ssa_stmt(exp->next, loop_h, next_blk);

    j_inst->op = GOTO;
    j_inst->dest = copr_create();
    j_inst->dest->kind = IMM;
    j_inst->dest->info.imm = cond_h->id + gbbase;
    cond_h->ref = 1;
    cblock_append(cur, j_inst);

    cfg_add_edge(cur, cond_h);
    cfg_add_edge(cond_t, loop_h);
    cfg_add_edge(loop_t, cond_h);
    cfg_add_edge(cond_t, next_blk);

    DBLINK(cur, loop_h);
    DBLINK(loop_t, cond_h);

    return next_blk;
}/*}}}*/

CBlock_t ssa_for(CNode *p, CBlock_t cur) {/*{{{*/
    CNode *exp1 = p->chd,
          *exp2 = exp1->next,
          *exp3 = exp2->next;
    CBlock_t loop_h = cblock_create(1), loop_t,
             cond_h = cblock_create(1), cond_t = cond_h,
             next_blk = cblock_create(1);
    CInst_t j_inst = cinst_create();
    COpr_t e = ssa_exp(exp2, &cond_t, 0);
    compress_branch(e, cond_t, 0)->dest->info.imm = loop_h->id + gbbase;
    loop_h->ref = 1;

    DBLINK(cond_t, next_blk);
    loop_t = ssa_stmt(exp3->next, loop_h, next_blk);

    ssa_exp(exp1, &cur, 1);
    ssa_exp(exp3, &loop_t, 1);

    j_inst->op = GOTO;
    j_inst->dest = copr_create();
    j_inst->dest->kind = IMM;
    j_inst->dest->info.imm = cond_h->id + gbbase;
    cond_h->ref = 1;
    cblock_append(cur, j_inst);

    cfg_add_edge(cur, cond_h);
    cfg_add_edge(cond_t, loop_h);
    cfg_add_edge(loop_t, cond_h);
    cfg_add_edge(cond_t, next_blk);

    DBLINK(cur, loop_h);
    DBLINK(loop_t, cond_h);

    return next_blk;
}/*}}}*/

CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {/*{{{*/
    CNode *body1 = p->chd->next,
          *body2 = body1->next;
    CBlock_t then_blk, then_t, next_blk,
             else_blk, else_t;
    CInst_t if_inst; /* = cinst_create(); */
    COpr_t rt;
    opt_if = p;
    opt_if_loop_exit = loop_exit;
    rt = ssa_exp(p->chd, &cur, 0); /* calculate cond */
    if (!opt_if) return cur;
    else
    {
        opt_if = NULL;
        opt_if_loop_exit = NULL;
    }
    if (rt->kind == IMM)
    {
        if (rt->info.imm)
            return ssa_stmt(body1, cur, loop_exit);
        else if (body2->type != NOP)
            return ssa_stmt(body2, cur, loop_exit);
        else
            return cur;
    }
    then_blk = cblock_create(1);
    if_inst = compress_branch(rt, cur, 1);

    cfg_add_edge(cur, then_blk);
    DBLINK(cur, then_blk);
    then_t = ssa_stmt(body1, then_blk, loop_exit);
    if (body2->type != NOP)
    {
        CInst_t j_inst = cinst_create();
        j_inst->op = GOTO;
        j_inst->dest = copr_create();
        j_inst->dest->kind = IMM;

        else_blk = cblock_create(1);
        if_inst->dest->info.imm = else_blk->id + gbbase;
        else_blk->ref = 1;
        DBLINK(then_t, else_blk);
        else_t = ssa_stmt(body2, else_blk, loop_exit);
        if (cblock_isempty(else_t))
            next_blk = else_t;
        else
        {
            next_blk = cblock_create(1);
            DBLINK(else_t, next_blk);
            cfg_add_edge(else_t, next_blk);
        }

        j_inst->dest->info.imm = next_blk->id + gbbase;
        next_blk->ref = 1;
        cblock_append(then_t, j_inst);

        cfg_add_edge(cur, else_blk);
        cfg_add_edge(then_t, next_blk);
    }
    else
    {
        if (cblock_isempty(then_t))
            next_blk = then_t;
        else
        {
            next_blk = cblock_create(1);
            DBLINK(then_t, next_blk);
            cfg_add_edge(then_t, next_blk);
        }
        cfg_add_edge(cur, next_blk);
        if_inst->dest->info.imm = next_blk->id + gbbase;
        next_blk->ref = 1;
    }
    return next_blk;
}/*}}}*/

CBlock_t ssa_ret(CNode *p, CBlock_t cur) {
    CInst_t inst = cinst_create();
    inst->op = RET;
    if (p->chd->type != NOP)
        inst->src1 = ssa_exp(p->chd, &cur, 0);
    cblock_append(cur, inst);
    return cur;
}

CBlock_t ssa_break(CBlock_t cur, CBlock_t loop_exit) {
    CInst_t inst = cinst_create();
    assert(loop_exit);
    inst->op = GOTO;
    inst->dest = copr_create();
    inst->dest->kind = IMM;
    inst->dest->info.imm = loop_exit->id + gbbase;
    loop_exit->ref = 1;
    cblock_append(cur, inst);
    cfg_add_edge(cur, loop_exit);
    return cur;
}

CBlock_t ssa_cont(CBlock_t cur, CBlock_t loop_exit) {
    CInst_t inst = cinst_create();
    assert(loop_exit);
    loop_exit = loop_exit->prev;    /* loop cond */
    inst->op = GOTO;
    inst->dest = copr_create();
    inst->dest->kind = IMM;
    inst->dest->info.imm = loop_exit->id + gbbase;
    loop_exit->ref = 1;
    cblock_append(cur, inst);
    cfg_add_edge(cur, loop_exit);
    return cur;
}

CBlock_t ssa_comp(CNode *, CBlock_t, CBlock_t loop_exit);
CBlock_t ssa_stmt(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
    switch (p->rec.subtype)
    {
        case STMT_EXP:
            ssa_exp(p->chd, &cur, 1);
            break;
        case STMT_COMP:
            cur = ssa_comp(p, cur, loop_exit);
            break;
        case STMT_IF:
            return ssa_if(p, cur, loop_exit);
        case STMT_FOR:
            return ssa_for(p, cur);
        case STMT_WHILE:
            return ssa_while(p, cur);
        case STMT_CONT:
            return ssa_cont(cur, loop_exit);
        case STMT_BREAK:
            return ssa_break(cur, loop_exit);
        case STMT_RET:
            return ssa_ret(p, cur);
    }
    return cur;
}

CBlock_t ssa_comp(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
    CNode *decls = p->chd,
          *stmts = p->chd->next, *i;
    if (decls->chd->type != NOP)
    {
        CVList_t a;
        for (a = p->ext.autos; a; a = a->next)
        {
            CNode *initr = a->var->initr;
            CInst_t last, inst;
            if (!initr) continue;
            assert(initr->rec.subtype == INITR_NORM);
            inst = cinst_create();
            inst->src1 = ssa_exp(initr->chd, &cur, 0);
            last = cblock_getback(cur);
            if (last && last->dest->kind == TMP)
            {
                last->dest->kind = VAR;
                free(last->dest->info.var);
                free(inst);
                last->dest->info.var = a->var;
                last->dest->type = a->var->type;
            }
            else
            {
                inst->op = MOVE;
                inst->dest = copr_create();
                inst->dest->kind = VAR;
                inst->dest->info.var = a->var;
                inst->dest->type = a->var->type;
                cblock_append(cur, inst);
            }
        }
    }
    if (stmts->chd->type != NOP)
        for (i = stmts->chd; i; i = i->next)
            cur = ssa_stmt(i, cur, loop_exit);
    return cur;
}

int dom[MAX_BLOCK], ord[MAX_BLOCK], vis[MAX_BLOCK], par[MAX_BLOCK], ocnt;
int loop_tail[MAX_BLOCK];
CPSet_t dfset[MAX_BLOCK], phi[MAX_BLOCK];
CBList_t df[MAX_BLOCK];

void dfs(CBlock_t u, int v) {
    CEdge *e;
    par[u->id] = v;
    vis[u->id] = -2;
    for (e = cfg.head[u->id]; e; e = e->next)
    {
        CBlock_t v = e->to;
        if (vis[v->id] == -1)
            dfs(v, u->id);
        else if (vis[v->id] == -2)
            loop_tail[v->id] = u->id;
    }
    vis[u->id] = ocnt;
    ord[ocnt++] = u->id;
}

int intersect(int b1, int b2) {
    while (b1 != b2)
        if (b1 < b2) b1 = dom[b1];
        else b2 = dom[b2];
    return b1;
}

void calc_dominant_frontier(void) {
    int i;
    int ch = 1;
    ocnt = 0;
    memset(vis, -1, sizeof vis);
    memset(dom, -1, sizeof dom);
    memset(loop_tail, -1, sizeof loop_tail);
    dfs(entry, -1);
    dom[vis[entry->id]] = vis[entry->id];
    while (ch)
    {
        int i;
        ch = 0;
        for (i = bcnt - 2; i >= 0; i--)
        {
            int id = ord[i];
            CEdge *e = cfg.rhead[id];
            int new_idom = vis[par[id]];
            for (; e; e = e->next)
            {
                int p = e->to->id;
                if (vis[p] == new_idom) continue;
                if (dom[vis[p]] != -1)
                    new_idom = intersect(vis[p], new_idom);
            }
            if (dom[i] != new_idom)
            {
                ch = 1;
                dom[i] = new_idom;
            }
        }
    }
    for (i = 0; i < bcnt; i++)
        dfset[i] = cpset_create();
    for (i = 0; i < bcnt; i++)
        if (cfg.rhead[i] && cfg.rhead[i]->next)
        {
            CEdge *p = cfg.rhead[i];
            for (; p; p = p->next)
            {
                int runner = p->to->id;
                while (vis[runner] != dom[vis[i]])
                {
                    if (!cpset_belongs(dfset[runner], i))
                    {
                        CBList_t np = NEW(CBList);
                        np->cblk = blks[i];
                        np->next = df[runner];
                        cpset_insert(dfset[runner], i);
                        df[runner] = np;
                    }
                    runner = ord[dom[vis[runner]]];
                }
            }
        }
    for (i = 1; i < bcnt; i++)
        dtree_add_edge(blks[ord[dom[vis[i]]]], blks[i]);
}

void insert_phi(CVList_t vars) {
    CVList_t vp;
    int i;
    for (i = 0; i < bcnt; i++)
        phi[i] = cpset_create();
    for (vp = vars; vp; vp = vp->next)
    { /* for each variable */
        CVar_t var = vp->var;
        CBList_t t = var->defsite;
        CBList_t def = NULL;
        static int indef[MAX_BLOCK];
        for (t = var->defsite; t; t = t->next)
            if (++indef[t->cblk->id] == 1)
            {
                CBList_t p = NEW(CBList);
                p->cblk = t->cblk;
                p->next = def;
                def = p;
            }
        for (t = var->defsite; t; t = t->next)
            indef[t->cblk->id] = 0; /* clear */
        while (def) /* while def not empty */
        {
            CBList_t n = def, i; /* remove some node n from def */
            def = def->next;
            for (i = df[n->cblk->id]; i; i = i->next)
            {
                CBlock_t y = i->cblk;
                CPSet_t phiy = phi[y->id];
                if (!cpset_belongs(phiy, (uintptr_t)var))
                {
                    CPhi_t phi = NEW(CPhi);
                    CBList_t ndef;
                    phi->dest = copr_create();
                    phi->dest->kind = VAR;
                    phi->dest->info.var = var;
                    phi->dest->type = var->type;
                    phi->oprs = (COpr_t *)malloc(sizeof(COpr_t) * y->pred);
                    cblock_pappend(y, phi); 
                    cpset_insert(phiy, (uintptr_t)var);
                    ndef = NEW(CBList);
                    ndef->cblk = y;
                    ndef->next = def;
                    def = ndef;
                }
            }
        }
    }
    for (i = 0; i < bcnt; i++)
    {
        CBList_t p, np;
        for (p = df[i]; p; p = np)
        {
            np = p->next;
            free(p);
        }
        df[i] = NULL;
        if (phi[i]) cpset_destroy(phi[i]);
        if (dfset[i]) cpset_destroy(dfset[i]);
    }
}

void renaming_dfs(CBlock_t blk) {
    CInst_t ih = blk->insts, i;
    CPhi_t ph = blk->phis, pi;
    CEdge *e = cfg.head[blk->id];
    COList_t defl = NULL, dn;
    for (pi = ph->next; pi != ph; pi = pi->next)
    {
        COpr_t dest = pi->dest;
        CVar_t var = dest->info.var;
        COList_t n = NEW(COList), n2;
        dest->sub = var->cnt++;
/*        dest->def = ih->next; *//* the first inst */ 
        n->opr = dest;
        n->next = var->stack;
        var->stack = n;
        n2 = NEW(COList);
        n2->opr = dest;
        n2->next = defl;
        defl = n2;
    }
    for (i = ih->next; i != ih; i = i->next)
    {
        COpr_t dest = i->dest;
        COpr_t *opr[3] = {NULL, &(i->src1), &(i->src2)};
        int t;
        if (i->op == WARR)
            opr[0] = &(i->dest);
        for (t = 0; t < 3; t++)
        {
            COpr_t p;
            if (!opr[t]) continue;
            p = *(opr[t]);
            if (!(p && (p->kind == VAR || p->kind == TMP))) continue;
            /* free(p); */  /* memory leak */
            (*opr[t] = p->info.var->stack->opr)->type = p->type;
            (*opr[t])->info.var->weight++;
        }
        if (dest)
        {
            if (i->op == WARR)
                i->dest = dest->info.var->stack->opr;
            else
            {
                if (dest->kind == VAR || dest->kind == TMP)
                {
                    CVar_t var = dest->info.var;
                    COList_t n = NEW(COList), n2;
                    dest->sub = var->cnt++;
                    /* dest->def = i; */
                    n->opr = dest;
                    n->next = var->stack;
                    var->stack = n;
                    n2 = NEW(COList);
                    n2->opr = dest;
                    n2->next = defl;
                    defl = n2;
                }
            }
        }
    }
    for (; e; e = e->next) /* for each successor */
    {
        CBlock_t y = e->to;
        int j = 0;
        CEdge *pre = cfg.rhead[y->id];
        for (; pre->to != blk; pre = pre->next) j++;
        ph = y->phis;
        for (pi = ph->next; pi != ph; pi = pi->next)
        {
            if (pi->dest->kind == VAR)
                pi->oprs[j] = pi->dest->info.var->stack->opr;
            pi->oprs[j]->dep = 1;
        }
    }
    for (e = dtree.head[blk->id]; e; e = e->next)
        renaming_dfs(e->to);
    for (; defl; defl = dn)
    {
        CVar_t var = defl->opr->info.var;
        COList_t nf = var->stack->next;
        free(var->stack);
        var->stack = nf;
        dn = defl->next;
        free(defl);
    }
}

void renaming_vars(COList_t oprs) {
    COList_t p;
    for (p = oprs; p; p = p->next)
        if (p->opr->kind == VAR)
        {
            CInst_t ld = cinst_create();
            CVar_t var = p->opr->info.var;
            var->cnt = 0;
            var->reload = var->loc > 0 && var->type->type != CARR;
            ld->op = LOAD;
            ld->dest = copr_create();
            ld->dest->kind = VAR;
            ld->dest->info.var = var;
            ld->dest->type = var->type;
            cblock_pushfront(entry, ld);
        }
    renaming_dfs(entry);
}

void mark_insts(void) {
    int i, icnt = 0;
    for (i = bcnt - 1; i >= 0; i--)
    {
        CBlock_t b = blks[ord[i]];
        CInst_t ih = b->insts, ii;
        CPhi_t ph = b->phis, pi;
        for (pi = ph->next; pi != ph; pi = pi->next)
        {
            pi->dest->def = ih->next;
            icnt++;
        }
        if (cblock_isempty(b))
            b->first = b->last = icnt++;
        else
        {
            for (ii = ih->next; ii != ih; ii = ii->next)
            {
                if (ii->op != WARR && ii->dest)
                    ii->dest->def = ii;
                ii->id = icnt++;
            }
            b->first = ih->next->id;
            b->last = ih->prev->id;
        }
    }
}

CPSet_t liveset[MAX_BLOCK];
COList_t live[MAX_BLOCK];

CRange_t crange_merge(CRange_t a, CRange_t b) {
    CRange res;
    CRange_t tail = &res;
    res.next = NULL;
    res.r = -1;
    for (; a || b;)
    {
        if (a && (!b || (a->l < b->l || (a->l == b->l && a->r < b->r))))
        {
            if (tail->r >= a->l)
            {
                if (a->r > tail->r)
                    tail->r = a->r;
            }
            else
            {
                assert(tail->r < a->l);
                tail->next = a;
                tail = a;
            }
            a = a->next;
        }
        else
        {
            if (tail->r >= b->l)
            {
                if (b->r > tail->r)
                    tail->r = b->r;
            }
            else
            {
                assert(tail->r < b->l);
                tail->next = b;
                tail = b;
            }
            b = b->next;
        }
    }
    tail->next = NULL;
    return res.next;
}

void add_range_(COpr_t opr, int begin, int end) {
    CRange_t range;
    range = NEW(CRange);
    range->l = begin;
    range->r = end;
    range->next = NULL;
    opr->range = crange_merge(opr->range, range);
}

void add_range(COpr_t opr, CBlock_t blk, int end) {
    int dfid = opr->def->id;
    int begin;
    if (blk->first <= dfid && dfid <= blk->last)
        begin = dfid;
    else
        begin = blk->first;
    add_range_(opr, begin, end);
}

void build_intervals(void) {
    int i;
    for (i = 0; i < bcnt; i++)
        liveset[i] = cpset_create();
    for (i = 0; i < bcnt; i++)
    {
        int id = ord[i];
        CBlock_t b = blks[id];
        CEdge *e = cfg.head[id]; 
        CPSet_t curlive = liveset[id];
        for (; e; e = e->next)
        {
            int sid = e->to->id;
            CBlock_t s = blks[sid];
            COList_t p = live[sid];
            CPhi_t ph = s->phis, i;
            for (i = ph->prev; i != ph; i = i->prev)
            {
                CEdge *pe;
                int t;
                for (t = 0, pe = cfg.rhead[sid]; pe->to != b; pe = pe->next) t++;
                COpr_t opr = i->oprs[t];
                if (opr && 
                        (opr->kind == VAR ||
                         opr->kind == TMP) && !cpset_belongs(curlive, (uintptr_t)opr))
                {
                    COList_t np = NEW(COList);
                    np->opr = opr;
                    np->next = live[id];
                    live[id] = np;
                    cpset_insert(curlive, (uintptr_t)opr);
                }
            }
            for (; p; p = p->next)
                if (cpset_belongs(liveset[sid], (uintptr_t)p->opr) &&
                        cpset_insert(curlive, (uintptr_t)p->opr))
                {
                    COList_t np = NEW(COList);
                    np->opr = p->opr;
                    np->next = live[id];
                    live[id] = np;
                }
        }
        {
            COList_t p;
            for (p = live[id]; p; p = p->next) 
                add_range(p->opr, b, b->last + 1);
        }
        {
            CInst_t ih = b->insts, i;
            for (i = ih->prev; i != ih; i = i->prev)
            {
                int t;
                COpr_t oprs[3] = {NULL, i->src1, i->src2};
                if (i->dest &&
                    (i->dest->kind == VAR ||
                     i->dest->kind == TMP) && i->op != WARR) /* def */
                {
                    i->is_def = 1;
                    cpset_erase(curlive, (uintptr_t)i->dest);
                }
                else
                {
                    if (i->op == WARR)
                        oprs[0] = i->dest;
                    i->is_def = 0;
                }
                for (t = 0; t < 3; t++)
                {
                    COpr_t opr = oprs[t];
                    if (opr && 
                        (opr->kind == VAR ||
                         opr->kind == TMP) && !cpset_belongs(curlive, (uintptr_t)opr))
                    {
                        COList_t np = NEW(COList);
                        np->opr = opr;
                        np->next = live[id];
                        live[id] = np;
                        cpset_insert(curlive, (uintptr_t)opr);
                        add_range(opr, b, i->id);
                    }
                }
            }
        }
        {
            CPhi_t ph = b->phis, i;
            for (i = ph->prev; i != ph; i = i->prev)
                cpset_erase(curlive, (uintptr_t)i->dest);
        }
        if (loop_tail[id] != -1)
        {
            COList_t p;
            for (p = live[id]; p; p = p->next) 
                if (cpset_belongs(curlive, (uintptr_t)p->opr))
                    add_range_(p->opr, b->first, blks[loop_tail[id]]->last + 1);
        }
    }
    for (i = 0; i < bcnt; i++)
    {
        COList_t p = live[i], np;
        for (; p; p = np)
        {
            np = p->next;
            free(p);
        }
        live[i] = NULL;
        if (liveset[i]) cpset_destroy(liveset[i]);
    }
}

COpr_t cinterv_repr(COpr_t opr) {
    return opr->par == opr ? opr : (opr->par = cinterv_repr(opr->par));
}

void cinterv_union(COpr_t a, COpr_t b) {
    a = cinterv_repr(a);
    b = cinterv_repr(b);
#ifdef CIBIC_DEBUG
    fprintf(stderr, "merging ");
    copr_print(stderr, a);
    fprintf(stderr, " ");
    copr_print(stderr, b);
    fprintf(stderr, "\n");
#endif
    if (a == b) return;
    b->range = crange_merge(b->range, a->range);
    a->par = b;
    b->mod |= a->mod;
}

void init_def(void) {
    CBlock_t p;
    COList_t def;
    raw_defs = NULL;
    for (p = entry; p; p = p->next)
    {
        CInst_t i, ih = p->insts;
        CPhi_t pi, ph = p->phis;
        for (i = ih->next; i != ih; i = i->next)
            if (i->is_def)
            {
                def = NEW(COList);
                def->opr = i->dest;
                def->next = raw_defs;
                raw_defs = def;
            }
        for (pi = ph->next; pi != ph; pi = pi->next)
        {
            def = NEW(COList);
            def->opr = pi->dest;
            def->next = raw_defs;
            raw_defs = def;
        }
    }
    for (p = entry; p; p = p->next)
    {
        CPhi_t pi, ph = p->phis;
        for (pi = ph->next; pi != ph; pi = pi->next)
        {
            int i;
            for (i = 0; i < p->pred; i++)
                cinterv_union(pi->dest, pi->oprs[i]);
        }
    }
    for (def = raw_defs; def; def = def->next)
    {
        COpr_t opr = def->opr;
        opr->spill = cinterv_repr(opr);
    }
    /* coalescing */
    for (p = entry; p; p = p->next)
    {
        CInst_t i, ih = p->insts;
        for (i = ih->next; i != ih; i = i->next)
            if (i->op == MOVE && i->dest->kind == TMP &&
                    (i->src1->kind == TMP || i->src1->kind == VAR))
                cinterv_union(i->dest, i->src1);
    }
}

void colist_remove(COList_t node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

void colist_add(COList_t head, COList_t p) {
    (p->next = head->next)->prev = p;
    (p->prev = head)->next = p;
}

int overlap_with_beg(COpr_t i, int beg) {
    CRange_t r;
    for (r = i->range; r && r->l <= beg; r = r->next)
        if (r->r > beg) return 1;
    return 0;
}

int overlap_with_interv(COpr_t i, COpr_t cur) {
    CRange_t pi, pc;
    for (pi = i->range, pc = cur->range; pi && pc;)
    {
        if (pi->r <= pc->l) pi = pi->next;
        else if (pc->r <= pi->l) pc = pc->next;
        else return 1;
    }
    return 0;
}

int copr_comp(const void *a, const void *b) {
    return (*(COpr_t *)a)->range->l - (*(COpr_t *)b)->range->l;
}

const int avail_regs[] = {8, 9, 10, 11,
                          12, 13, 14, 15,
                          16, 17, 24, 25};

const int MAX_AVAIL_REGS = sizeof(avail_regs) / sizeof(avail_regs[0]);

void register_alloc(void) {
    /* Algorithm from the paper:
     * Linear Scan Register Allocation
     * in the Context of SSA Form and Register Constraints */
    static int freg[32], f[32];
    int dn = 0, i;
    COpr_t *unhandled;
    COList_t p;
    COList_t active = NEW(COList),
             inactive = NEW(COList);
    active->next = active->prev = active;
    inactive->next = inactive->prev = inactive;
    memset(freg, -1, sizeof freg);
    init_def();
    for (i = 0; i < MAX_AVAIL_REGS; i++)
        freg[avail_regs[i]] = 1; /* available */
    for (p = raw_defs; p; p = p->next)
    {
        COpr_t opr = p->opr;
        /*
        if (opr->info.var->loc < 0)
        {
            opr->reg = 3 - opr->info.var->loc;
            continue;
        } */ /* arguments */
        opr->reg = -2;
        if (opr->par != opr) continue;
        if (cinterv_repr(opr)->range)
        {
            opr->reg = -1;
            dn++;
        }
    }
    unhandled = (COpr_t *)malloc(dn * sizeof(COpr_t));
    i = 0;
    for (p = raw_defs; p; p = p->next)
        if (p->opr->reg == -1)
            unhandled[i++] = p->opr;
    for (i = 0; i < dn; i++)
    {
        COpr_t opr = unhandled[i];
        CRange_t r;
        for (r = opr->range; r->next; r = r->next);
        opr->begin = opr->range->l;
        opr->end = r->r;
    }
    qsort(unhandled, dn, sizeof(COpr_t), copr_comp);
    /* preparation done */
    for (i = 0; i < dn; i++)
    {
        COList_t c = NEW(COList);
        COpr_t cur;
        COList_t np;
        int reg, t;
        cur = c->opr = unhandled[i];
        /* for each interval in active */
        for (p = active->next; p != active; p = np)
        {
            COpr_t i = p->opr;
            np = p->next;
            if (i->end <= cur->begin) /* if i ends before cur.beg */
            {
                colist_remove(p);
                free(p);            /* move i to handled */
                freg[i->reg] = 1;   /* add i.reg to free */
            }
            else if (!overlap_with_beg(i, cur->begin))
            {
                colist_remove(p); 
                colist_add(inactive, p); /* move i to inactive */
                freg[i->reg] = 1;        /* add i.reg to free */
            }
        }
        /* for each interval i in inactive */
        for (p = inactive->next; p != inactive; p = np)
        {
            COpr_t i = p->opr;
            np = p->next;
            if (i->end <= cur->begin)   /* if i ends before cur.beg */
            {
                colist_remove(p);
                free(p);                /* move i to handled */
            }
            else if (overlap_with_beg(i, cur->begin))
            {
                colist_remove(p);
                colist_add(active, p);  /* move i to active */
                freg[i->reg] = 0;       /* remove i.reg from free */
            }
        }
        memmove(f, freg, sizeof f);
        /* for each interval i in inactive that overlaps cur do
         * f <- f - {i.reg} */
        for (p = inactive->next; p != inactive; p = p->next)
            if (overlap_with_interv(p->opr, cur))
                f[p->opr->reg] = 0;
        reg = -1;
        for (t = 0; t < 32; t++)
            if (f[t] > 0) { reg = t; break; }
        if (reg == -1) /* if f = {} */
        { /* assign mem loc */
            static int w[32];
            int min = 0x7fffffff;
            memset(w, 0, sizeof w);
            for (p = active->next; p != active; p = p->next)
                if (overlap_with_interv(p->opr, cur))
                    w[p->opr->reg] += p->opr->info.var->weight;
            for (p = inactive->next; p != inactive; p = p->next)
                if (overlap_with_interv(p->opr, cur))
                    w[p->opr->reg] += p->opr->info.var->weight;
            for (t = 0; t < 32; t++)
                if (f[t] != -1 && w[t] < min) min = t, reg = t;
            if (reg == -1 || cur->info.var->weight < w[reg])
            {
                cur->reg = -1;      /* assign a memory location to cur */
                free(c);            /* and move cur to handled */
            }
            else
            {
                /* move all active or inactive intervals to which r was assigned to handled
                 * assign memory locations to them */
                for (p = active->next; p != active; p = np)
                {
                    np = p->next;
                    if (p->opr->reg == reg)
                    {
                        p->opr->reg = -1;
                        colist_remove(p);
                        free(p);
                    }
                }
                for (p = inactive->next; p != inactive; p = np)
                {
                    np = p->next;
                    if (p->opr->reg == reg)
                    {
                        p->opr->reg = -1;
                        colist_remove(p);
                        free(p);
                    }
                }
                cur->reg = reg;
                colist_add(active, c); /* move cur to active */
            }
        }
        else if (cur->mod)      /* may be referenced by a pointer */
        {
            cur->reg = -1;      /* assign a memory location to cur */
            free(c);            /* and move cur to handled */
        }
        else
        {
            cur->reg = reg; /* cur.reg <- any register in f */
            freg[reg] = 0;  /* free <- free - {cur.reg} */
            colist_add(active, c); /* move cur to active */
        }
    }
    for (p = raw_defs; p; p = p->next)
    {
        COpr_t opr = p->opr;
/*        opr->spill = cinterv_repr(opr); */
        if (cinterv_repr(opr)->range)
            opr->reg = cinterv_repr(opr)->reg;
    }
    defs = NULL;
    for (i = 0; i < dn; i++)
    {
        COList_t p = NEW(COList);
        p->opr = unhandled[i];
        p->next = defs;
        defs = p;
    }
    if (!quiet)
    {
        for (i = 0; i < dn; i++)
        {
            COpr_t opr = unhandled[i];
            CRange_t p;
            copr_print(stderr, opr);
            fprintf(stderr, ":");
            for (p = opr->range; p; p = p->next)
                fprintf(stderr, " [%d, %d)", p->l, p->r);
            fprintf(stderr, " (begin: %d, end: %d, weight: %d, reg: %d)\n",
                    opr->begin, opr->end, opr->info.var->weight, opr->reg);
        }
    }
    free(unhandled);
}

void const_propagation(void) {
#define IS_STATIC(opr) (!((opr)->mod || (opr)->info.var->reload))
    int i;
    for (i = bcnt - 1; i >= 0; i--)
    {
        CBlock_t b = blks[vis[i]];
        CInst_t i, ni, ih = b->insts;
        for (i = ih->next; i != ih; i = ni)
        {
            int flag = 0;
            COpr_t t;
            if (i->op == ADDR)
                i->src1->mod = 1;
            if (i->src1 && i->src1->cval && IS_STATIC(i->src1))
            {
                t = i->src1->cval;
                i->src1 = copr_create();
                *(i->src1) = *t;
            }
            if (i->src2 && i->src2->cval && IS_STATIC(i->src2))
            {
                t = i->src2->cval;
                i->src2 = copr_create();
                *(i->src2) = *t;
            }
            if (!i->dest) 
            {
                ni = i->next;
                continue;
            }
            if (i->src1 && i->src1->kind == IMM)
            {
                if (i->op == MOVE)
                    flag = 1;
                else if (i->op == NEG)
                {
                    i->op = MOVE;
                    i->src1->info.imm *= -1;
                    flag = 1;
                }
                else if (i->src2 && i->src2->kind == IMM)
                {
                    COpr_t c;
                    int immd;
                    int imm1 = i->src1->info.imm;
                    int imm2 = i->src2->info.imm;
                    flag = 1;
                    switch (i->op)
                    {
                        case MUL: immd = imm1 * imm2; break;
                        case DIV: immd = imm1 / imm2; break;
                        case MOD: immd = imm1 % imm2; break;
                        case ADD: immd = imm1 + imm2; break;
                        case SUB: immd = imm1 - imm2; break;
                        case SHL: immd = imm1 << imm2; break;
                        case SHR: immd = imm1 >> imm2; break;
                        case AND: immd = imm1 & imm2; break;
                        case XOR: immd = imm1 ^ imm2; break;
                        case OR: immd = imm1 | imm2; break;
                        case NOR: immd = ~(imm1 | imm2); break;
                        case EQ: immd = imm1 == imm2; break;
                        case NE: immd = imm1 != imm2; break;
                        case LT: immd = imm1 < imm2; break;
                        case GT: immd = imm1 > imm2; break;
                        case LE: immd = imm1 <= imm2; break;
                        case GE: immd = imm1 >= imm2; break;
                        default: flag = 0;
                    }
                    if (flag)
                    {
                        c = copr_create();
                        c->kind = IMM;
                        free(i->src1);
                        free(i->src2);
                        i->op = MOVE;
                        i->src1 = c;
                        c->info.imm = immd;
                    }
                }
            }
            ni = i->next;
            if (flag)
            {
                i->dest->cval = i->src1;
                if (i->dest->kind == TMP && !i->dest->dep)
                {
                    i->next->prev = i->prev;
                    i->prev->next = i->next;
                    free(i);
                }
            }
        }
    }
}

void strength_reduction(void) {
#define SWAP_IMM \
    do { \
        if (i->src1->kind == IMM) \
        { \
            COpr_t t = i->src1; \
            i->src1 = i->src2; \
            i->src2 = t; \
        } \
    } while (0)

#define PRINT_BARE_STRING \
    do { \
        if (bp != buff) \
        { \
            CInst_t print = cinst_create(); \
            CSList_t cstr = NEW(CSList); \
            print->op = CALL; \
            print->dest = copr_create(); \
            print->dest->kind = TMP; \
            print->dest->info.var = ctmp_create(); \
            print->dest->type = i->dest->type; \
            print->src1 = copr_create(); \
            print->src1->kind = IMMF; \
            *bp = '\0'; \
            print->src1->kind = IMMF; \
            cstr->str = strdup(buff);  \
            (cstr->prev = cstrs->prev)->next = cstr; \
            (cstr->next = cstrs)->prev = cstr; \
            cstr->id = cstr->prev->id + 1; \
            inst = cinst_create(); \
            inst->op = PUSH; \
            inst->sysp = 1; \
            inst->src1 = copr_create(); \
            inst->src1->kind = IMMS; \
            inst->src1->info.cstr = cstr; \
            cblock_append(ibuff, inst); \
            print->src1->info.str = "__print_string"; \
            cblock_append(ibuff, print); \
            bp = buff; \
        } \
    } while (0)

    int i;
    int call_cnt = 0;
    for (i = bcnt - 1; i >= 0; i--)
    {
        CBlock_t b = blks[vis[i]];
        CInst_t i, ni, ih = b->insts;
        for (i = ih->next; i != ih; i = ni)
        {
            ni = i->next;
            switch (i->op)
            {
                case ADD:
                    SWAP_IMM;
                case SUB:
                    if (i->src2->kind == IMM && !i->src2->info.imm)
                    {
                        i->op = MOVE;
                        i->src2 = NULL;
                    }
                    break;
                case MUL:
                    SWAP_IMM;
                    if (i->src2->kind == IMM)
                    {
                        int p = 0, n = i->src2->info.imm;
                        while (!(n & 1)) n >>= 1, p++;
                        if (n == 1)
                        {
                            i->op = SHL;
                            i->src2 = copr_create();
                            i->src2->kind = IMM;
                            i->src2->info.imm = p;
                        }
                    } 
                    break;
                case DIV:
                    SWAP_IMM;
                    if (i->src2->kind == IMM)
                    {
                        int p = 0, n = i->src2->info.imm;
                        while (!(n & 1)) n >>= 1, p++;
                        if (n == 1)
                        {
                            i->op = SHR;
                            i->src2 = copr_create();
                            i->src2->kind = IMM;
                            i->src2->info.imm = p;
                        }
                    } 
                    break;
                case PUSH:
                    call_cnt++;
                    break;
                case CALL:
                    if (i->src1->kind == IMMF &&
                        !strcmp(i->src1->info.str, "printf"))
                    {
                        static char buff[1024];
                        char *bp = buff, *sp;
                        CInst_t push = i, inst,  phead, np;
                        CBlock_t ibuff;
                        CSList_t fmt;
                        /* move to the first push */
                        while (call_cnt--) push = push->prev;
                        if (push->src1->kind != IMMS) break; /* not a const pattern */
                        ibuff = cblock_create(0);
                        fmt = push->src1->info.cstr;
                        push->prev->next = i->next;
                        i->next->prev = push->prev;
                        phead = push->prev;
                        np = push->next;
                        free(push);
                        push = np;
                        for (sp = fmt->str; *sp != '\0'; sp++)
                        {
                            if (*sp == '%')
                            {
                                CInst_t print = cinst_create();
                                print->op = CALL;
                                print->dest = copr_create();
                                print->dest->kind = TMP;
                                print->dest->info.var = ctmp_create();
                                print->dest->type = i->dest->type;
                                print->src1 = copr_create();
                                print->src1->kind = IMMF;
                                PRINT_BARE_STRING;
                                switch (*(++sp))
                                {
                                    case 'd': 
                                        {
                                            if (push != i)
                                            {
                                                np = push->next;
                                                push->sysp = 1;
                                                cblock_append(ibuff, push);
                                                push = np;
                                            }
                                            print->src1->info.str = "__print_int";
                                            cblock_append(ibuff, print);
                                        }
                                        break;
                                    case 'c':
                                        {
                                            if (push != i)
                                            {
                                                np = push->next;
                                                push->sysp = 1;
                                                cblock_append(ibuff, push);
                                                push = np;
                                            }
                                            print->src1->info.str = "__print_char";
                                            cblock_append(ibuff, print);
                                        }
                                        break;
                                    case 's':
                                        {

                                            if (push != i)
                                            {
                                                np = push->next;
                                                push->sysp = 1;
                                                cblock_append(ibuff, push);
                                                push = np;
                                            }
                                            print->src1->info.str = "__print_string";
                                            cblock_append(ibuff, print);
                                        }
                                        break;
                                    default:
                                        {
                                            CSList_t cstr = NEW(CSList);
                                            cstr->str = strdup(sp - 1); 
                                            (cstr->prev = cstrs->prev)->next = cstr;
                                            (cstr->next = cstrs)->prev = cstr;
                                            cstr->id = cstr->prev->id + 1;
                                            inst = cinst_create();
                                            inst->op = PUSH;
                                            inst->src1 = copr_create();
                                            inst->src1->kind = IMMS;
                                            inst->src1->info.cstr = cstr;
                                            cblock_append(ibuff, inst);
                                            for (; push != i; push = np)
                                            {
                                                np = push->next;
                                                cblock_append(ibuff, push);
                                            }
                                            print->src1->info.str = "printf";
                                            cblock_append(ibuff, print);
                                            sp = fmt->str + strlen(fmt->str) - 1;
                                        }
                                        break;
                                }
                            }
                            else *bp++ = *sp;
                        }
                        PRINT_BARE_STRING;
                        fmt->prev->next = fmt->next;
                        fmt->next->prev = fmt->prev;
                        free(fmt);
                        (i->next->prev = ibuff->insts->prev)->next = i->next;
                        (phead->next = ibuff->insts->next)->prev = phead;
                        free(ibuff);
                    }
                    call_cnt = 0;
                    break;
                default: ;
            }
        }
    }
}

unsigned int copr_hash(COpr_t opr) {
    if (!opr) return 0;
    switch (opr->kind)
    {
        case VAR:
        case TMP:
            return (unsigned long)opr;
        default:
            return (unsigned int)opr->info.imm;
    }
}

int copr_eq(COpr_t a, COpr_t b) {
    if (a->kind != b->kind) return 0;
    switch (a->kind)
    {
        case VAR:
        case TMP:
            return a == b;
        case IMM:
            return a->info.imm == b->info.imm;
        case IMMS:
            return a->info.cstr == b->info.cstr;
        case IMMF:
            return !strcmp(a->info.str, b->info.str);
        default:
            return 0;
    }
}

unsigned int cexpmap_hash(CInst_t exp) {
    unsigned int res = 0;
    res = ((unsigned int)exp->op) << 10;
    res ^= copr_hash(exp->src1);
    res = (res << 1) ^ copr_hash(exp->src2);
    return res;
}

CExpMap_t cexpmap_create(void) {
    CExpMap_t res = NEW(CExpMap);
    memset(res->head, 0, sizeof res->head);
    return res;
}

CExpMap_t cexpmap_dup(CExpMap_t cem) {
    int i;
    CExpMap_t res = cexpmap_create();
    for (i = 0; i < MAX_TABLE_SIZE; i++)
    {
        CENode *p, *t;
        for (p = cem->head[i]; p; p = p->next)
        {
            t = NEW(CENode);
            t->exp = p->exp;
            t->next = res->head[i];
            res->head[i] = t;
        }
    }
    return res;
}

int cexpmap_comp(CInst_t exp1, CInst_t exp2) {
    if (exp1->op != exp2->op) return 0;
    if (!copr_eq(exp1->src1, exp2->src1)) return 0;
    return copr_eq(exp1->src2, exp2->src2);
}

void cexpmap_insert(CExpMap_t cem, CInst_t exp) {
    int hv = cexpmap_hash(exp) % MAX_TABLE_SIZE;
    CENode *np = NEW(CENode);
    np->exp = exp;
    np->next = cem->head[hv];
    cem->head[hv] = np;
}

CInst_t cexpmap_lookup(CExpMap_t cem, CInst_t exp) {
    int hv = cexpmap_hash(exp) % MAX_TABLE_SIZE;
    CENode *p;
    for (p = cem->head[hv]; p; p = p->next)
        if (cexpmap_comp(p->exp, exp))
            return p->exp;
    return NULL;
}

void cexpmap_clear(CExpMap_t cem) {
    int i;
    CENode *p, *np;
    for (i = 0; i < MAX_TABLE_SIZE; cem->head[i++] = NULL)
        for (p = cem->head[i]; p; p = np)
        {
            np = p->next;
            free(p);
        }
}

void cexpmap_destroy(CExpMap_t cem) {
    cexpmap_clear(cem);
    free(cem);
}
void copr_shortcut(COpr_t *opr) {
    COpr_t t = *opr;
    if (!t) return;
    t = t->same;
    if (t->kind == TMP)
        *opr = t->same;
}

void subexp_elimination_(CBlock_t b, CExpMap_t cem) {
    CInst_t i, ih = b->insts, ni;
    CEdge *e;
    for (i = ih->next; i != ih; i = ni)
    {
        CInst_t t;
        ni = i->next;
        if (i->op == MOVE)
        {
            i->dest->same = i->src1->same;
            continue;
        }
        else if (i->op == CALL)
        {
            cexpmap_clear(cem);
            continue;
        }
        copr_shortcut(&i->src1);
        copr_shortcut(&i->src2);
        t = cexpmap_lookup(cem, i);
        if (t)
        {
            i->op = MOVE;
            i->src1 = t->dest;
            i->src2 = NULL;
            i->dest->same = i->src1;
        }
        else
        {
            switch (i->op)
            {
                case MUL: case DIV: case MOD: case ADD: case SUB:
                case SHL: case SHR: case AND: case XOR: case OR: case NOR: 
                case EQ: case NE: case LT: case GT: case LE: case GE:
                case NEG:
                    if (i->dest->kind == TMP) cexpmap_insert(cem, i);
                    break;
                default: ;
            }
        }
    }
    for (e = dtree.head[b->id]; e; e = e->next)
    {
        CExpMap_t scem = cexpmap_dup(cem);
        subexp_elimination_(e->to, scem);
        cexpmap_destroy(scem);
    }
}

void subexp_elimination(void) {
    CExpMap_t cem = cexpmap_create();
    subexp_elimination_(entry, cem);
    cexpmap_destroy(cem);
}

void deadcode_elimination() {
    int i;
    for (i = bcnt - 1; i >= 0; i--)
    {
        CBlock_t b = blks[vis[i]];
        CInst_t i, ih = b->insts;
        for (i = ih->next; i != ih; i = i->next)
        {
            if (i->src1) i->src1->dep = 1;
            if (i->src2) i->src2->dep = 1;
            if (i->op == WARR && i->dest) i->dest->dep = 1;
        }
    }
    for (i = bcnt - 1; i >= 0; i--)
    {
        CBlock_t b = blks[vis[i]];
        CInst_t i, ih = b->insts;
        for (i = ih->next; i != ih; i = i->next)
            if (i->op != CALL && i->dest && i->dest->kind == TMP && !i->dest->dep)
            {
                i->next->prev = i->prev;
                i->prev->next = i->next;
                free(i);
            }
    }
}

void ssa_func(CType_t func) {
#define OPRS_ADD(_opr) \
    do { \
        if (cpset_insert(avs, (uintptr_t)((_opr)->info.var))) \
        { \
            COList_t n = NEW(COList); \
            n->next = oprs; \
            n->opr = _opr; \
            oprs = n; \
        } \
    } while (0)

#define VS_ADD(_d) \
    do { \
        if (cpset_insert(vs, (uintptr_t)(_d))) \
        { \
            CVList_t n = NEW(CVList); \
            n->next = vars; \
            n->var = _d; \
            vars = n; \
        } \
    } while (0)

    CBlock_t p;
    entry = cblock_create(1);
    CPSet_t vs = cpset_create(), avs = cpset_create();
    CVList_t vars = NULL;
    COList_t oprs = NULL;
    /* CVar_t pr; */
    cfg_clear();
    dtree_clear();
    ssa_comp(func->rec.func.body, entry, NULL);
    /*
    for (i = 0, pr = func->rec.func.params;
        i < 4 && pr;
        i++, pr = pr->next)
        pr->loc = -(i + 1); */ /* mark arguments */

    for (p = entry; p; p = p->next)
    {
        CInst_t head = p->insts, i;
        CEdge *e;
        p->pred = 0;
        for (e = cfg.rhead[p->id]; e; e = e->next)
            p->pred++;
        for (i = head->next; i != head; i = i->next)
        {
            if (i->src1 && (i->src1->kind == VAR || i->src1->kind == TMP))
                OPRS_ADD(i->src1);
            if (i->src2 && (i->src2->kind == VAR || i->src2->kind == TMP))
                OPRS_ADD(i->src2);
            if (i->op == WARR)
                OPRS_ADD(i->dest);
            else if (i->dest && i->dest->kind == VAR)
            {
                CVar_t d = i->dest->info.var;
                CBList_t b = NEW(CBList);
                VS_ADD(d);
                OPRS_ADD(i->dest);
                b->next = d->defsite;
                b->cblk = p;
                d->defsite = b;
            }
        }
        blks[p->id] = p;
    }
    cpset_destroy(avs);
    cpset_destroy(vs);
    calc_dominant_frontier();
    /* build SSA */
    insert_phi(vars);
    renaming_vars(oprs);
    /* optimization on SSA */
    const_propagation();
    subexp_elimination();
    const_propagation();
    strength_reduction();
    deadcode_elimination();
    /* out of SSA */
    mark_insts();
    build_intervals();
    register_alloc();
}