From 6586df0797ad60af031cb80889f8205b6adcdfe3 Mon Sep 17 00:00:00 2001 From: Teddy Date: Mon, 5 May 2014 02:04:39 +0800 Subject: higher code-gen quality --- Makefile | 8 ---- ast.c | 2 +- mips.c | 60 ++++++++++++------------- mips.h | 4 +- semantics.c | 10 ++--- ssa.c | 142 +++++++++++++++++++++++++++++++++++++++++++++++++----------- ssa.h | 21 ++++++++- 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); -- cgit v1.2.3