aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile6
-rw-r--r--main.c3
-rw-r--r--semantics.c67
-rw-r--r--semantics.h25
-rw-r--r--ssa.c101
-rw-r--r--ssa.h14
6 files changed, 155 insertions, 61 deletions
diff --git a/Makefile b/Makefile
index dd26615..025649d 100644
--- a/Makefile
+++ b/Makefile
@@ -6,9 +6,9 @@ run:
db:
gdb cibic
-cibic: lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o
+cibic: lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o mips.o
mkdir -p bin
- gcc -o bin/cibic lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o
+ gcc -o bin/cibic lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o mips.o
cp bin/cibic cibic
lex.yy.o: lex.yy.c cibic.tab.c
gcc -c lex.yy.c
@@ -22,6 +22,8 @@ semantics.o: semantics.c semantics.h
gcc -c semantics.c -g -Wall -Wextra -DCIBIC_DEBUG
ssa.o: ssa.c ssa.h
gcc -c ssa.c -g -Wall -Wextra -DCIBIC_DEBUG
+mips.o: mips.c mips.h
+ gcc -c mips.c -g -Wall -Wextra -DCIBIC_DEBUG
lex.yy.c: cibic.l
flex cibic.l
cibic.tab.c: cibic.y
diff --git a/main.c b/main.c
index 08655f0..91bcc17 100644
--- a/main.c
+++ b/main.c
@@ -55,7 +55,8 @@ void print_sem() {
void print_ssa() {
cibic_init();
yyparse();
- ssa_generate(semantics_check(ast_root));
+ semantics_check(ast_root);
+ ssa_generate();
}
void print_help() {
diff --git a/semantics.c b/semantics.c
index 5af8761..9ef5f7f 100644
--- a/semantics.c
+++ b/semantics.c
@@ -273,8 +273,8 @@ CType_t ctype_create(char *name, int type, CNode *ast) {
return ct;
}
-static int align_shift(int x) {
- return x + ((4 - (x & 3)) & 3);
+int align_shift(int x) {
+ return ((4 - (x & 3)) & 3);
}
int calc_size(CType_t type) {
@@ -296,8 +296,11 @@ int calc_size(CType_t type) {
if (!p) return -1;
for (; p; p = p->next)
{
+ /* add padding to align to word boundary */
+ if (p->type->type != CCHAR)
+ size += align_shift(size);
p->start = size;
- size += align_shift(calc_size(p->type));
+ size += calc_size(p->type);
}
}
break;
@@ -308,7 +311,7 @@ int calc_size(CType_t type) {
if (!p) return -1;
for (; p; p = p->next)
{
- int t = align_shift(calc_size(p->type));
+ int t = calc_size(p->type);
if (t > size) size = t;
p->start = 0;
}
@@ -1809,7 +1812,10 @@ void ctype_print(CType_t ct) { ctype_print_(ct, 0); }
void cvar_print(CVar_t cv) { cvar_print_(cv, 0); }
void cdef_print(CDef_t cd) { cdef_print_(cd, 0); }
-CScope_t semantics_check(CNode *p) {
+CTList_t funcs;
+CVList_t gvars;
+
+void semantics_check(CNode *p) {
CScope_t scope = cscope_create();
basic_type_int = ctype_create("int", CINT, NULL);
basic_type_char = ctype_create("char", CCHAR, NULL);
@@ -1840,7 +1846,55 @@ CScope_t semantics_check(CNode *p) {
default: assert(0);
}
}
-/* cscope_debug_print(scope);
+ {
+ int i;
+ CTNode *p;
+ funcs = NULL;
+ gvars = NULL;
+ for (i = 0; i < MAX_TABLE_SIZE; i++)
+ for (p = scope->ids->head[i]; p; p = p->next)
+ {
+ CSymbol_t tp = (CSymbol_t)(p->val);
+ CType_t func = tp->rec.type;
+ if (tp->kind == CTYPE &&
+ func->type == CFUNC &&
+ func->rec.func.body)
+ {
+ CTList_t nf = NEW(CTList);
+ CVar_t p;
+ int size;
+ nf->type = func;
+ nf->next = funcs;
+ funcs = nf;
+ size = 0;
+ for (p = func->rec.func.params; p; p = p->next)
+ {
+ /* force to a word alignment */
+ size += align_shift(size);
+ p->start = size;
+ size += calc_size(p->type);
+ }
+ func->rec.func.params_size = size;
+ size = 0;
+ for (p = func->rec.func.local; p; p = p->next)
+ {
+ /* force to a word alignment */
+ size += align_shift(size);
+ p->start = size;
+ size += calc_size(p->type);
+ }
+ func->rec.func.local_size = size;
+ }
+ else if (tp->kind == CVAR)
+ {
+ CVList_t nv = NEW(CVList);
+ nv->var = tp->rec.var;
+ nv->next = gvars;
+ gvars = nv;
+ }
+ }
+ }
+ /* cscope_debug_print(scope);
{
CTNode *p;
int i;
@@ -1862,5 +1916,4 @@ CScope_t semantics_check(CNode *p) {
}
}
cnode_debug_print(ast_root, 1); */
- return scope;
}
diff --git a/semantics.h b/semantics.h
index 65d1b7e..4db33b6 100644
--- a/semantics.h
+++ b/semantics.h
@@ -13,8 +13,25 @@ typedef CSymbol *CSymbol_t;
typedef struct CDef CDef;
typedef CDef *CDef_t;
+typedef struct CTList CTList;
+typedef CTList *CTList_t;
+struct CTList {
+ CType_t type;
+ CTList_t next;
+};
+
+typedef struct CVList CVList;
+typedef CVList *CVList_t;
+struct CVList {
+ CVar_t var;
+ CVList_t next;
+};
+
+
typedef struct CBList *CBList_t;
typedef struct COList *COList_t;
+typedef struct CVList *CVList_t;
+
struct CVar {
char *name;
CVar_t next; /* next in the linked list */
@@ -57,6 +74,8 @@ struct CType {
CVar_t local;
CType_t ret;
CNode *body;
+ int params_size;
+ int local_size;
} func; /* for a function */
} rec;
int size; /* memory footprint */
@@ -154,7 +173,7 @@ void cscope_debug_print(CScope_t cs);
unsigned int bkdr_hash(const char *str);
const char *ctable_cvar_print(void *var);
-CScope_t semantics_check(CNode *ast);
+void semantics_check(CNode *ast);
enum DefState{
FORCE_ID,
@@ -170,4 +189,8 @@ void block_exit(void);
void def_enter(enum DefState kind);
void def_exit(void);
int calc_size(CType_t type);
+int align_shift(int x);
+
+extern CTList_t funcs;
+extern CVList_t gvars;
#endif
diff --git a/ssa.c b/ssa.c
index 28970c0..3ad5097 100644
--- a/ssa.c
+++ b/ssa.c
@@ -4,6 +4,7 @@
#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)
@@ -11,7 +12,12 @@ static CGraph cfg, dtree;
static CBlock_t blks[MAX_BLOCK];
static int bcnt; /* block counter */
static int tcnt; /* temporary counter */
-static int gbbase;
+
+/* for code generation */
+int gbbase;
+CBlock_t entry;
+COList_t defs;
+CType_t func;
CBlock_t cblock_create(int inc) {
CBlock_t cblk = NEW(CBlock);
@@ -218,6 +224,11 @@ void cinst_print(CInst_t inst) {
}
else fprintf(stderr, "return");
break;
+ case ADDR:
+ copr_print(inst->dest);
+ fprintf(stderr, " = addr ");
+ copr_print(inst->src1);
+ break;
default:
{
const char *op;
@@ -289,23 +300,19 @@ void ssa_func_print(CBlock_t p) {
for (; p; p = p->next)
cblock_print(p);
}
-CBlock_t ssa_func(CType_t);
-void ssa_generate(CScope_t scope) {
- CTNode *p;
- int i;
- for (i = 0; i < MAX_TABLE_SIZE; i++)
- for (p = scope->ids->head[i]; p; p = p->next)
- {
- CSymbol_t tp = (CSymbol_t)(p->val);
- CType_t func = tp->rec.type;
- if (tp->kind != CTYPE ||
- func->type != CFUNC ||
- !func->rec.func.body) continue;
- fprintf(stderr, "%s:\n", tp->rec.type->name);
- ssa_func_print(ssa_func(func));
- gbbase += bcnt;
- bcnt = 0;
- }
+void ssa_func(CType_t);
+void ssa_generate() {
+ CTList_t f;
+ for (f = funcs; f; f = f->next)
+ {
+ func = f->type;
+ fprintf(stderr, "%s:\n", func->name);
+ ssa_func(func);
+ ssa_func_print(entry);
+ mips_generate();
+ gbbase += bcnt;
+ bcnt = 0;
+ }
}
COpr_t ssa_exp_(CNode *p, CBlock_t, CInst_t, CBlock_t);
@@ -556,6 +563,26 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
}
}
}
+ else if (op == '&' && !p->chd->next)
+ {
+ ssa_exp_(p->chd, cur, inst, succ);
+ if (inst->op == MOVE)
+ {
+ inst->op = ADDR;
+ inst->src1 = inst->dest;
+ inst->src2 = NULL;
+ }
+ else
+ {
+ inst->op = ADD;
+ inst->src1 = inst->dest;
+ }
+ inst->dest = NEW(COpr);
+ inst->dest->kind = TMP;
+ inst->dest->info.var = ctmp_create(p->ext.type);
+ cblock_append(cur, inst);
+ return inst->dest;
+ }
else
{
int unary = 0;
@@ -649,21 +676,12 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
case OPT_GE: inst->op = GE; break;
case '/': inst->op = DIV; break;
case '%': inst->op = MOD; break;
- case '&':
- if (p->chd->next)
- inst->op = AND;
- else
- {
- rec = 0;
- res = NEW(COpr);
- res->kind = IMM;
- res->info.imm = 0;
- /* TODO: be filled in with correct address */
- }
- break;
case '*':
inst->op = MUL;
break;
+ case '&':
+ inst->op = AND;
+ break;
case '+':
if (p->chd->next)
inst->op = ADD;
@@ -1062,7 +1080,7 @@ int intersect(int b1, int b2) {
return b1;
}
-void calc_dominant_frontier(CBlock_t entry) {
+void calc_dominant_frontier() {
int i;
int ch = 1;
ocnt = 0;
@@ -1282,7 +1300,7 @@ void renaming_dfs(CBlock_t blk) {
}
}
-void renaming_vars(CVList_t vars, CBlock_t entry) {
+void renaming_vars(CVList_t vars) {
CVList_t vp;
for (vp = vars; vp; vp = vp->next)
{
@@ -1498,7 +1516,7 @@ void cinterv_union(COpr_t a, COpr_t b) {
a->par = b;
}
-COList_t init_def(CBlock_t entry) {
+COList_t init_def() {
CBlock_t p;
COList_t defs = NULL, def;
for (p = entry; p; p = p->next)
@@ -1554,16 +1572,16 @@ void print_intervals(COList_t defs) {
}
}
-void register_alloc(CBlock_t entry) {
- COList_t defs;
+void register_alloc() {
mark_insts();
build_intervals();
- defs = init_def(entry);
+ defs = init_def();
print_intervals(defs);
}
-CBlock_t ssa_func(CType_t func) {
- CBlock_t entry = cblock_create(1), p;
+void ssa_func(CType_t func) {
+ CBlock_t p;
+ entry = cblock_create(1);
CPSet_t vs = cpset_create(), avs = cpset_create();
CVList_t vars = NULL, all_vars = NULL;
int i;
@@ -1601,7 +1619,7 @@ CBlock_t ssa_func(CType_t func) {
}
blks[p->id] = p;
}
- calc_dominant_frontier(entry);
+ calc_dominant_frontier();
{
CPNode *p;
for (i = 0; i < MAX_TABLE_SIZE; i++)
@@ -1623,9 +1641,8 @@ CBlock_t ssa_func(CType_t func) {
}
}
insert_phi(vars);
- renaming_vars(all_vars, entry);
- register_alloc(entry);
+ renaming_vars(all_vars);
+ register_alloc();
cpset_destroy(vs);
cpset_destroy(avs);
- return entry;
}
diff --git a/ssa.h b/ssa.h
index 67ce3a4..400e0a3 100644
--- a/ssa.h
+++ b/ssa.h
@@ -55,6 +55,7 @@ struct CInst {
RET, /* return */
MOVE,
LOAD, /* load from memory */
+ ADDR, /* get address */
MUL, DIV, MOD, ADD, SUB,
SHL, SHR, AND, XOR, OR,
LOR, LAND, NEG, NOR, SEQ,
@@ -93,13 +94,6 @@ struct CBList {
CBList_t next;
};
-typedef struct CVList CVList;
-typedef CVList *CVList_t;
-struct CVList {
- CVar_t var;
- CVList_t next;
-};
-
CBlock_t cblock_create(int inc);
void cblock_append(CBlock_t cblk, CInst_t inst);
void cblock_pappend(CBlock_t cblk, CPhi_t phi);
@@ -134,5 +128,9 @@ typedef struct CInterv {
CRange_t range;
} CInterv;
-void ssa_generate(CScope_t scope);
+void ssa_generate();
+extern int gbbase;
+extern CBlock_t entry;
+extern COList_t defs;
+extern CType_t func;
#endif