higher code-gen quality

7 files changed, 174 insertions, 73 deletions

diff --git a/Makefile b/Makefile
index 025649d..7d10bcb 100644
--- a/Makefile
+++ b/Makefile
@@ -1,8 +1,5 @@
 all: cibic
 
-run: 
-	./cibic --ast
-
 db:
 	gdb cibic
 
@@ -31,8 +28,3 @@ cibic.tab.c: cibic.y
 
 clean:
 	rm -f cibic lex.yy.c cibic.tab.c cibic.tab.h *.o
-
-sem: semantics.o test.o
-	gcc -o sem semantics.o test.o
-test.o: test.c
-	gcc -c test.c -Wall -Wextra -g
diff --git a/ast.c b/ast.c
index 959addf..627a85a 100644
--- a/ast.c
+++ b/ast.c
@@ -29,7 +29,7 @@ CNode *cnode_create_ast(CNode *wrapped) {
     return wrapped;
 }
 
-CNode *cnode_create_nop() {
+CNode *cnode_create_nop(void) {
     CNode *nop = NEW_CNODE;
     nop->type = NOP;
     nop->next = nop->chd = NULL;
diff --git a/mips.c b/mips.c
index 0ae3184..e4039ee 100644
--- a/mips.c
+++ b/mips.c
@@ -11,7 +11,7 @@ int memcpy_cnt;
 static int save_pos[32];
 static int used_reg[32]; 
 
-void mips_prologue() {
+void mips_prologue(void) {
     CVList_t v;
     CSList_t s;
     printf(".data 0x10000000\n");
@@ -120,7 +120,7 @@ int mips_to_reg(COpr_t opr, int reg0) {
     return reg0;
 }
 
-void mips_memcpy() {
+void mips_memcpy(void) {
     printf("\tj _mem_cond%d\n", memcpy_cnt);
     printf("_mem_loop%d:\n", memcpy_cnt);
     printf("\tlw $5, 0($%d)\n", reg_v0);
@@ -135,7 +135,7 @@ void mips_memcpy() {
 
 /* memcpy requires three arguments */
 #define RESERVED_CALL_SIZE 12
-void mips_space_alloc() {
+void mips_space_alloc(void) {
     int local_size = func->rec.func.local_size;
     int arg_size = RESERVED_CALL_SIZE;
     int bret_size = 0;
@@ -244,7 +244,7 @@ void mips_space_alloc() {
     func->rec.func.frame_size = prev;
 }
 
-void mips_func_begin() {
+void mips_func_begin(void) {
     int fsize = func->rec.func.frame_size;
     if (fsize < 0x8000)
         printf("\taddiu $sp, $sp, -%d\n", fsize);
@@ -256,7 +256,7 @@ void mips_func_begin() {
     printf("\tsw $31, %d($sp) #%s\n", fsize - 4, func->name);
 }
 
-void mips_func_end() {
+void mips_func_end(void) {
     int fsize = func->rec.func.frame_size;
     printf("_ret_%s:\n", func->name);
     printf("\tlw $31, %d($sp)\n", fsize - 4);
@@ -272,7 +272,7 @@ void mips_func_end() {
 
 #define IN_IMM(x) (-0x8000 <= (x) && (x) < 0x8000)
 
-void mips_generate() {
+void mips_generate(void) {
     CBlock_t p;
     CType_t rt = func->rec.func.ret;
     /* int arg_cnt = 0; */
@@ -289,7 +289,7 @@ void mips_generate() {
         const char *bop;
         for (i = ih->next; i != ih; i = i->next)
         {
-            int flag = 1, swap;
+            int flag = 1, swap, rimm;
             if (i->dest && i->dest->reg == -2 && i->dest->kind == TMP && i->op != CALL)
                 continue;
             printf("# ");
@@ -590,26 +590,26 @@ void mips_generate() {
             }
             if (flag) continue;
             flag = 1;
-            swap = 0;
+            swap = rimm = 0;
             switch (i->op)
             {
-                case MUL: bop = "mul"; break;
-                case DIV: bop = "divu"; break;
-                case MOD: bop = "rem"; break;
-                case ADD: bop = "addu"; swap = 1; break;
-                case SUB: bop = "subu"; break;
-                case SHL: bop = "sllv"; break;
-                case SHR: bop = "srlv"; break;
-                case AND: bop = "and"; swap = 1; break;
-                case XOR: bop = "xor"; swap = 1; break;
-                case OR: bop = "or"; swap = 1; break;
-                case NOR: bop = "nor"; break;
-                case EQ: bop = "seq"; break;
-                case NE: bop = "sne"; break;
-                case LT: bop = "slt"; break;
-                case GT: bop = "sgt"; break;
-                case LE: bop = "sle"; break;
-                case GE: bop = "sge"; break;
+                case MUL: bop = "mul"; rimm = 1; break;
+                case DIV: bop = "divu"; rimm = 1; break;
+                case MOD: bop = "rem"; rimm = 1; break;
+                case ADD: bop = "addu"; rimm = swap = 1; break;
+                case SUB: bop = "subu"; rimm = 1; break;
+                case SHL: bop = "sllv"; rimm = 1; break;
+                case SHR: bop = "srlv"; rimm = 1; break;
+                case AND: bop = "and"; rimm = swap = 1; break;
+                case XOR: bop = "xor"; rimm = swap = 1; break;
+                case OR: bop = "or"; rimm = swap = 1; break;
+                case NOR: bop = "nor"; rimm = 1; break;
+                case EQ: bop = "seq"; rimm = 1; break;
+                case NE: bop = "sne"; rimm = 1; break;
+                case LT: bop = "slt"; rimm = 1; break;
+                case GT: bop = "sgt"; rimm = 1; break;
+                case LE: bop = "sle"; rimm = 1; break;
+                case GE: bop = "sge"; rimm = 1; break;
                 default: flag = 0;
             }
             if (flag)
@@ -617,10 +617,10 @@ void mips_generate() {
                 int rs, rt;
                 int rd = i->dest->reg;
                 if (rd < 0) rd = reg_v0;
-                if (swap)
+                if (rimm)
                 {
                     COpr_t t;
-                    if (i->src1->kind == IMM)
+                    if (swap && i->src1->kind == IMM)
                     {
                         t = i->src1;
                         i->src1 = i->src2;
@@ -634,15 +634,17 @@ void mips_generate() {
                             case AND: bop = "andi"; break;
                             case XOR: bop = "xori"; break;
                             case OR: bop = "ori"; break;
+                            case SHL: bop = "sll"; break;
+                            case SHR: bop = "srl"; break;
                             default: ;
                         }
                         rs = mips_to_reg(i->src1, reg_v0);
                         printf("\t%s $%d, $%d, %d\n",
                                 bop, rd, rs, i->src2->info.imm);
                     }
-                    else swap = 0;
+                    else rimm = 0;
                 }
-                if (!swap)
+                if (!rimm)
                 {
                     rs = mips_to_reg(i->src1, reg_v0);
                     rt = mips_to_reg(i->src2, reg_v1);
diff --git a/mips.h b/mips.h
index 3a9db9b..f78be3c 100644
--- a/mips.h
+++ b/mips.h
@@ -1,5 +1,5 @@
 #ifndef MIPS_C
 #define MIPS_C
-void mips_prologue();
-void mips_generate();
+void mips_prologue(void);
+void mips_generate(void);
 #endif
diff --git a/semantics.c b/semantics.c
index 3379321..b1afee2 100644
--- a/semantics.c
+++ b/semantics.c
@@ -159,7 +159,7 @@ void ctable_clip(CTable_t ct, const char *key, int max_lvl) {
     ct->head[hv] = p;
 }
 
-CScope_t cscope_create() {
+CScope_t cscope_create(void) {
     CScope_t p = NEW(CScope);
     p->lvl = -1;
     p->top = NULL;
@@ -1624,7 +1624,7 @@ struct DNode{
     DNode *next;
 } *typedef_stack;
 
-void cibic_init() {
+void cibic_init(void) {
     typedef_scope = cscope_create();
     typedef_stack = NULL;
 }
@@ -1667,14 +1667,14 @@ void def_enter(enum DefState kind) {
     typedef_stack = ntop;
 }
 
-void def_exit() {
+void def_exit(void) {
     DNode *ntop = typedef_stack->next;
     free(typedef_stack);
     typedef_stack = ntop;
 }
 
-void block_enter() { cscope_enter(typedef_scope); }
-void block_exit() { cscope_exit(typedef_scope); }
+void block_enter(void) { cscope_enter(typedef_scope); }
+void block_exit(void) { cscope_exit(typedef_scope); }
 
 void ctable_debug_print(CTable_t ct) {
     int i;
diff --git a/ssa.c b/ssa.c
index 1c43920..fed2843 100644
--- a/ssa.c
+++ b/ssa.c
@@ -20,7 +20,7 @@ CBlock_t entry;
 CType_t func;
 COList_t defs;              /* all defintions that have actual effects */
 
-COpr_t copr_create() {
+COpr_t copr_create(void) {
     COpr_t opr = NEW(COpr);
     opr->type = NULL;
     opr->cval = NULL;
@@ -30,7 +30,7 @@ COpr_t copr_create() {
     return opr;
 }
 
-CInst_t cinst_create() {
+CInst_t cinst_create(void) {
     CInst_t inst = NEW(CInst);
     inst->dest = NULL;
     inst->src1 = NULL;
@@ -94,7 +94,7 @@ int cblock_isempty(CBlock_t cblk) {
     return cblk->insts->prev == cblk->insts;
 }
 
-CVar_t ctmp_create() {
+CVar_t ctmp_create(void) {
     static char buff[MAX_NAMELEN];
     sprintf(buff, "t%d", tcnt++);
     return cvar_create(strdup(buff), NULL, NULL);
@@ -106,7 +106,7 @@ void ctmp_destroy(CVar_t type) {
     free(type);
 }
 
-void cfg_clear() {
+void cfg_clear(void) {
     int i;
     for (i = 0; i < MAX_BLOCK; i++)
     {
@@ -126,18 +126,15 @@ void cfg_clear() {
     }
 }
 
-void dtree_clear() {
+void dtree_clear(void) {
     int i;
-    for (i = 0; i < MAX_BLOCK; i++)
-    {
-        CEdge *p, *np;
+    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);
         }
-        dtree.head[i] = NULL;
-    }
 }
 
 void cfg_add_edge(CBlock_t from, CBlock_t to) {
@@ -320,7 +317,7 @@ void ssa_func_print(CBlock_t p) {
         cblock_print(p);
 }
 void ssa_func(CType_t);
-void ssa_generate() {
+void ssa_generate(void) {
     CTList_t f;
     mips_prologue();
     for (f = funcs; f; f = f->next)
@@ -1315,7 +1312,7 @@ CBlock_t ssa_comp(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
     return cur;
 }
 
-CPSet_t cpset_create() {
+CPSet_t cpset_create(void) {
     CPSet_t res = NEW(CPSet);
     memset(res->head, 0, sizeof res->head);
     return res;
@@ -1332,6 +1329,7 @@ void cpset_destroy(CPSet_t cps) {
             free(p);
         }
     }
+    free(cps);
 }
 
 int cpset_insert(CPSet_t cps, long key) {
@@ -1402,7 +1400,7 @@ int intersect(int b1, int b2) {
     return b1;
 }
 
-void calc_dominant_frontier() {
+void calc_dominant_frontier(void) {
     int i;
     int ch = 1;
     ocnt = 0;
@@ -1638,7 +1636,7 @@ void renaming_vars(COList_t oprs) {
     renaming_dfs(entry);
 }
 
-void mark_insts() {
+void mark_insts(void) {
     int i, icnt = 0;
     for (i = bcnt - 1; i >= 0; i--)
     {
@@ -1723,7 +1721,7 @@ void add_range(COpr_t opr, CBlock_t blk, int end) {
     add_range_(opr, begin, end);
 }
 
-void build_intervals() {
+void build_intervals(void) {
     int i;
     for (i = 0; i < bcnt; i++)
         liveset[i] = cpset_create();
@@ -1851,7 +1849,7 @@ void cinterv_union(COpr_t a, COpr_t b) {
     b->mod |= a->mod;
 }
 
-void init_def() {
+void init_def(void) {
     CBlock_t p;
     COList_t def;
     raw_defs = NULL;
@@ -1887,7 +1885,7 @@ void init_def() {
     }
 }
 
-void print_intervals() {
+void print_intervals(void) {
     COList_t d;
     for (d = raw_defs; d; d = d->next)
     {
@@ -1941,7 +1939,7 @@ int copr_comp(const void *a, const void *b) {
 const int avail_regs[] = {8, 9, 10, 11, 12, 13, 14, 15, 24, 25};
 const int MAX_AVAIL_REGS = sizeof(avail_regs) / sizeof(avail_regs[0]);
 
-void register_alloc() {
+void register_alloc(void) {
     /* Algorithm from the paper:
      * Linear Scan Register Allocation
      * in the Context of SSA Form and Register Constraints */
@@ -2133,7 +2131,7 @@ void register_alloc() {
     free(unhandled);
 }
 
-void const_propagation() {
+void const_propagation(void) {
     int i;
     for (i = bcnt - 1; i >= 0; i--)
     {
@@ -2229,7 +2227,17 @@ void const_propagation() {
     }
 }
 
-void strength_reduction() {
+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)
+
     int i;
     for (i = bcnt - 1; i >= 0; i--)
     {
@@ -2241,22 +2249,103 @@ void strength_reduction() {
             switch (i->op)
             {
                 case ADD:
-                    if (i->src1->kind == IMM)
-                    {
-                        COpr_t t = i->src1;
-                        i->src1 = i->src2;
-                        i->src2 = t;
-                    }
+                    SWAP_IMM;
                     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->info.imm = p;
+                        }
+                    } 
+                    break;
+
+                default: ;
+            }
+        }
+    }
+}
+
+unsigned int cexpmap_hash(CInst_t exp) {
+    unsigned int res = 0;
+    res = ((unsigned int)exp->op) << 10;
+    res ^= (unsigned long)exp->src1;
+    res = (res << 1) ^ (unsigned long)exp->src2;
+    return res;
+}
+
+CExpMap_t cexpmap_create(void) {
+    CExpMap_t res = NEW(CExpMap);
+    memset(res->head, 0, sizeof res->head);
+    return res;
+}
+
+int cexpmap_comp(CInst_t exp1, CInst_t exp2) {
+    if (exp1->op != exp2->op) return 0;
+    if (exp1->src1 != exp2->src1) return 0;
+    return 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->next;
+}
+
+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;
+            free(p);
+        }
+}
+
+void cexpmap_destroy(CExpMap_t cem) {
+    cexpmap_clear(cem);
+    free(cem);
+}
+
+void subexp_elimination(void) {
+    int i;
+    CExpMap_t cem = cexpmap_create();
+    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)
+            {
                 default: ;
             }
         }
     }
+    cexpmap_destroy(cem);
 }
 
 void ssa_func(CType_t func) {
@@ -2334,6 +2423,7 @@ void ssa_func(CType_t func) {
     renaming_vars(oprs);
     /* optimization on SSA */
     const_propagation();
+    subexp_elimination();
     strength_reduction();
     /* out of SSA */
     mark_insts();
diff --git a/ssa.h b/ssa.h
index 54e3f98..827bbb2 100644
--- a/ssa.h
+++ b/ssa.h
@@ -53,15 +53,15 @@ struct COList {
 void colist_remove(COList_t node);
 
 struct CInst {
-    enum {
+    enum OpCode {
         BEQZ,   /* conditional jump */
         BNEZ,
         GOTO,   /* unconditional jump */
         ARR,    /* displacement */
-        WARR,
         PUSH,   /* push to stack top */
         CALL,   /* call function */
         RET,    /* return */
+        WARR,
         MOVE,
         LOAD,   /* load from memory */
         ADDR,   /* get address */
@@ -141,6 +141,23 @@ typedef struct CInterv {
     CRange_t range;
 } CInterv;
 
+typedef struct CENode CENode; 
+typedef struct CExpMap {
+    struct CENode {
+        CInst_t exp;
+        CENode *next;
+    } *head[MAX_TABLE_SIZE];
+} CExpMap;
+typedef CExpMap *CExpMap_t;
+
+CExpMap_t cexpmap_create(void);
+unsigned int cexpmap_hash(CInst_t exp);
+int cexpmap_comp(CInst_t exp1, CInst_t exp2);
+void cexpmap_insert(CExpMap_t cem, CInst_t exp);
+CInst_t cexpmap_lookup(CExpMap_t cem, CInst_t exp);
+void cexpmap_clear(CExpMap_t cem);
+void cexpmap_destroy(CExpMap_t cem);
+
 void ssa_generate(void);
 COpr_t cinterv_repr(COpr_t opr);
 void cinst_print(FILE *stream, CInst_t inst);