aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile6
-rw-r--r--const.h2
-rw-r--r--main.c9
-rw-r--r--semantics.c5
-rw-r--r--semantics.h2
-rw-r--r--ssa.c371
-rw-r--r--ssa.h53
7 files changed, 441 insertions, 7 deletions
diff --git a/Makefile b/Makefile
index b4bb524..dd26615 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
+cibic: lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o
mkdir -p bin
- gcc -o bin/cibic lex.yy.o cibic.tab.o ast.o main.o semantics.o
+ gcc -o bin/cibic lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o
cp bin/cibic cibic
lex.yy.o: lex.yy.c cibic.tab.c
gcc -c lex.yy.c
@@ -20,6 +20,8 @@ ast.o: ast.c ast.h
gcc -c ast.c -g -Wall -Wextra -DCIBIC_DEBUG
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
lex.yy.c: cibic.l
flex cibic.l
cibic.tab.c: cibic.y
diff --git a/const.h b/const.h
index cd65eaa..f5a8ef4 100644
--- a/const.h
+++ b/const.h
@@ -22,7 +22,7 @@ enum {
NS_ID,
NS_TAG
};
-
+#define MAX_BLOCK 1024
#define MAX_CHDN 1024
#define MAX_DEBUG_PRINT_BUFF 1024
#define MAX_DEBUG_PRINT_LVL 1024
diff --git a/main.c b/main.c
index df9807a..e0b06a7 100644
--- a/main.c
+++ b/main.c
@@ -3,6 +3,7 @@
#include <stdlib.h>
#include "cibic.tab.h"
#include "ast.h"
+#include "ssa.h"
#include "semantics.h"
extern char linebuff[];
@@ -51,6 +52,12 @@ void print_sem() {
/* cnode_debug_print(ast_root, 1); */
}
+void print_ssa() {
+ cibic_init();
+ yyparse();
+ ssa_generate(semantics_check(ast_root));
+}
+
void print_help() {
fprintf(stderr,
"CBIC: C Implemented Bare and Ingenuous Compiler\n\n"
@@ -114,7 +121,7 @@ int main(int argc, char **argv) {
{
case PRINT_AST: print_ast(); break;
case PRINT_HELP: print_help(); break;
- default: print_sem();
+ default: print_ssa();
}
return 0;
}
diff --git a/semantics.c b/semantics.c
index 6bf6925..5a6419c 100644
--- a/semantics.c
+++ b/semantics.c
@@ -1169,10 +1169,10 @@ ExpType semantics_exp(CNode *p, CScope_t scope) {
else
{
p->ext.type = lu->rec.type;
- p->ext.var = NULL;
res.type = p->ext.type;
res.lval = res.type->type == CFUNC;
POINTER_CONV(res.type, p);
+ p->ext.var = cvar_create(p->ext.type->name, res.type, NULL);
}
p->ext.is_const = res.type->type == CARR ||
res.type->type == CFUNC;
@@ -1763,7 +1763,7 @@ 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); }
-void semantics_check(CNode *p) {
+CScope_t 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);
@@ -1816,4 +1816,5 @@ void semantics_check(CNode *p) {
}
}
cnode_debug_print(ast_root, 1);
+ return scope;
}
diff --git a/semantics.h b/semantics.h
index ca97633..d0b681a 100644
--- a/semantics.h
+++ b/semantics.h
@@ -148,7 +148,7 @@ void cscope_debug_print(CScope_t cs);
unsigned int bkdr_hash(const char *str);
const char *ctable_cvar_print(void *var);
-void semantics_check(CNode *ast);
+CScope_t semantics_check(CNode *ast);
enum DefState{
FORCE_ID,
diff --git a/ssa.c b/ssa.c
new file mode 100644
index 0000000..7f7f958
--- /dev/null
+++ b/ssa.c
@@ -0,0 +1,371 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "ast.h"
+#include "ssa.h"
+#define NEW(type) ((type *)malloc(sizeof(type)))
+#define DBLINK(from, to) ((from)->next = (to))->prev = (from)
+
+static CGraph cfg;
+static CBlock_t blks[MAX_BLOCK];
+static int bcnt; /* block counter */
+static int tcnt; /* temporary counter */
+static int gbbase;
+
+CBlock_t cblock_create() {
+ CBlock_t cblk = NEW(CBlock);
+ CInst_t dummy = NEW(CInst);
+ dummy->prev = dummy;
+ dummy->next = dummy;
+ cblk->insts = dummy;
+ cblk->next = NULL;
+ cblk->id = (bcnt++) + gbbase;
+ 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;
+}
+
+CInst_t cblock_getback(CBlock_t cblk) {
+ return cblk->insts->prev;
+}
+
+int cblock_isempty(CBlock_t cblk) {
+ return cblk->insts->prev == cblk->insts;
+}
+
+void cfg_clear() {
+ int i;
+ for (i = 0; i < MAX_BLOCK; i++)
+ if (cfg.head[i])
+ {
+ CEdge *p, *np;
+ for (p = cfg.head[i]; p; p = np)
+ {
+ np = p->next;
+ free(p);
+ }
+ cfg.head[i] = NULL;
+ }
+}
+
+void cfg_add_edge(CBlock_t from, CBlock_t to) {
+ int id = from->id;
+ CEdge *e = NEW(CEdge);
+ e->to = to;
+ e->next = cfg.head[id];
+ cfg.head[id] = e;
+}
+
+void copr_print(COpr *opr) {
+ switch (opr->kind)
+ {
+ case VAR:
+ case TMP: fprintf(stderr, "%s", opr->info.var->name);
+ break;
+ case IMM: fprintf(stderr, "%d", opr->info.imm);
+ break;
+ }
+}
+
+void cinst_print(CInst_t inst) {
+ switch (inst->op)
+ {
+ case MOVE:
+ copr_print(&inst->dest);
+ fprintf(stderr, " = ");
+ copr_print(&inst->src1);
+ break;
+ case BEQZ:
+ fprintf(stderr, "if not (");
+ copr_print(&inst->src1);
+ fprintf(stderr, ") goto _L");
+ copr_print(&inst->dest);
+ break;
+ case GOTO:
+ fprintf(stderr, "goto _L");
+ copr_print(&inst->dest);
+ break;
+ case ADD:
+ copr_print(&inst->dest);
+ fprintf(stderr, " = ");
+ copr_print(&inst->src1);
+ fprintf(stderr, " + ");
+ copr_print(&inst->src2);
+ break;
+ }
+ fprintf(stderr, "\n");
+}
+
+void cblock_print(CBlock_t blk) {
+ CInst_t p, sp = blk->insts;
+ if (blk->ref)
+ fprintf(stderr, "_L%d:\n", blk->id);
+ for (p = sp->next; p != sp; p = p->next)
+ {
+ fprintf(stderr, "\t");
+ cinst_print(p);
+ }
+}
+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));
+ }
+}
+
+COpr ssa_exp(CNode *p, CBlock_t cur) {
+ COpr res;
+ CInst_t inst = NEW(CInst);
+ switch (p->type)
+ {
+ case NOP: ; break;
+ case ID:
+ res.kind = VAR;
+ res.info.var = p->ext.var;
+ break;
+ default:
+ if (p->ext.is_const)
+ {
+ res.kind = IMM;
+ res.info.imm = p->ext.const_val;
+ }
+ else
+ {
+ COpr lhs = ssa_exp(p->chd, cur), rhs;
+ if (p->chd->next)
+ rhs = ssa_exp(p->chd->next, cur);
+ switch (p->rec.subtype)
+ {
+ case '=' :
+ inst->op = MOVE;
+ inst->dest = lhs;
+ inst->src1 = rhs;
+ break;
+ case ASS_ADD:
+ inst->op = ADD;
+ inst->dest = lhs;
+ inst->src1 = lhs;
+ inst->src2 = rhs;
+ break;
+ /*
+ case ASS_MUL:
+ case ASS_DIV:
+ case ASS_MOD:
+ case ASS_ADD:
+ case ASS_SUB:
+ case ASS_SHL:
+ case ASS_SHR:
+ case ASS_AND:
+ case ASS_XOR:
+ case ASS_OR:
+ */
+ }
+ cblock_append(cur, inst);
+ res = inst->dest;
+ }
+ }
+ return res;
+}
+
+CBlock_t ssa_stmt(CNode *, CBlock_t, CBlock_t);
+CBlock_t ssa_while(CNode *p, CBlock_t cur) {
+ CNode *exp = p->chd;
+ CBlock_t loop_blk = cblock_create(), loop_t,
+ cond_blk,
+ next_blk = cblock_create();
+ CInst_t j_inst = NEW(CInst),
+ if_inst = NEW(CInst);
+
+ loop_t = ssa_stmt(exp->next, loop_blk, next_blk);
+
+ cond_blk = cblock_create();
+ DBLINK(loop_t, cond_blk);
+ cfg_add_edge(loop_t, cond_blk);
+
+ ssa_exp(exp, cond_blk);
+
+ j_inst->op = GOTO;
+ j_inst->dest.kind = IMM;
+ j_inst->dest.info.imm = cond_blk->id;
+ cond_blk->ref = 1;
+ cblock_append(cur, j_inst);
+
+ if_inst->op = BEQZ;
+ if_inst->src1 = cblock_getback(cond_blk)->dest;
+ if_inst->dest.kind = IMM;
+ if_inst->dest.info.imm = loop_blk->id;
+ loop_blk->ref = 1;
+ cblock_append(cond_blk, if_inst);
+
+ cfg_add_edge(cur, cond_blk);
+ cfg_add_edge(cond_blk, loop_blk);
+ cfg_add_edge(cond_blk, next_blk);
+
+ DBLINK(cur, loop_blk);
+ DBLINK(cond_blk, next_blk);
+}
+
+CBlock_t ssa_for(CNode *p, CBlock_t cur) {
+ CNode *exp1 = p->chd,
+ *exp2 = exp1->next,
+ *exp3 = exp2->next;
+ CBlock_t loop_blk = cblock_create(), loop_t,
+ cond_blk,
+ next_blk = cblock_create();
+ CInst_t j_inst = NEW(CInst),
+ if_inst = NEW(CInst);
+
+ loop_t = ssa_stmt(exp3->next, loop_blk, next_blk);
+
+ cond_blk = cblock_create();
+ DBLINK(loop_t, cond_blk);
+ cfg_add_edge(loop_t, cond_blk);
+
+ ssa_exp(exp1, cur);
+ ssa_exp(exp2, cond_blk);
+ ssa_exp(exp3, loop_t);
+
+ j_inst->op = GOTO;
+ j_inst->dest.kind = IMM;
+ j_inst->dest.info.imm = cond_blk->id;
+ cond_blk->ref = 1;
+ cblock_append(cur, j_inst);
+
+ if_inst->op = BEQZ;
+ if_inst->src1 = cblock_getback(cond_blk)->dest;
+ if_inst->dest.kind = IMM;
+ if_inst->dest.info.imm = loop_blk->id;
+ loop_blk->ref = 1;
+ cblock_append(cond_blk, if_inst);
+
+ cfg_add_edge(cur, cond_blk);
+ cfg_add_edge(cond_blk, loop_blk);
+ cfg_add_edge(cond_blk, next_blk);
+
+ DBLINK(cur, loop_blk);
+ DBLINK(cond_blk, next_blk);
+
+ 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 = cblock_create(), then_t,
+ next_blk,
+ else_blk, else_t;
+ CInst_t if_inst = NEW(CInst);
+ ssa_exp(p->chd, cur);
+ if_inst->op = BEQZ;
+ if_inst->src1 = cblock_getback(cur)->dest; /* calculated cond */
+ if_inst->dest.kind = IMM;
+ cblock_append(cur, if_inst);
+
+ 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 = NEW(CInst);
+ j_inst->op = GOTO;
+ j_inst->dest.kind = IMM;
+
+ else_blk = cblock_create();
+ if_inst->dest.info.imm = else_blk->id;
+ 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();
+ DBLINK(else_t, next_blk);
+ }
+
+ j_inst->dest.info.imm = next_blk->id;
+ next_blk->ref = 1;
+ cblock_append(then_t, j_inst);
+
+ cfg_add_edge(cur, else_blk);
+ cfg_add_edge(then_t, next_blk);
+ cfg_add_edge(else_t, next_blk);
+ }
+ else
+ {
+ if (cblock_isempty(then_t))
+ next_blk = then_t;
+ else
+ {
+ next_blk = cblock_create();
+ DBLINK(then_t, next_blk);
+ }
+ cfg_add_edge(cur, next_blk);
+ cfg_add_edge(then_t, next_blk);
+ if_inst->dest.info.imm = next_blk->id;
+ next_blk->ref = 1;
+ }
+ return next_blk;
+}
+
+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);
+ 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);
+/* return ssa_while(p, cur);*/
+ /*
+ case STMT_CONT:
+ return ssa_cont(p, cur, loop_exit);
+ case STMT_BREAK:
+ return ssa_break(p, cur, loop_exit);
+ case STMT_RET:
+ return ssa_return(p, cur, loop_exit);
+ */
+ }
+ return cur;
+}
+
+CBlock_t ssa_comp(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
+ CNode *stmts = p->chd->next, *i;
+ if (stmts->chd->type != NOP)
+ for (i = stmts->chd; i; i = i->next)
+ cur = ssa_stmt(i, cur, loop_exit);
+ return cur;
+}
+
+CBlock_t ssa_func(CType_t func) {
+ CBlock_t start = cblock_create();
+ ssa_comp(func->rec.func.body, start, NULL);
+ return start;
+}
+
diff --git a/ssa.h b/ssa.h
new file mode 100644
index 0000000..8b28a39
--- /dev/null
+++ b/ssa.h
@@ -0,0 +1,53 @@
+#ifndef SSA_H
+#define SSA_H
+#include "const.h"
+#include "semantics.h"
+typedef struct COpr {
+ enum {
+ VAR,
+ TMP,
+ IMM
+ } kind;
+ union {
+ CVar_t var;
+ int imm;
+ } info;
+} COpr;
+
+typedef struct CInst CInst;
+typedef CInst *CInst_t;
+struct CInst {
+ enum {
+ MOVE,
+ BEQZ, /* conditional jump */
+ GOTO, /* unconditional jump */
+ ADD
+ } op;
+ COpr dest, src1, src2;
+ CInst_t next, prev;
+};
+
+typedef struct CBlock CBlock;
+typedef CBlock *CBlock_t;
+struct CBlock {
+ CInst_t insts; /* instructions */
+ CBlock_t next, prev;
+ int id;
+ int ref; /* if referenced by any gotos */
+};
+
+CBlock_t cblock_create();
+void cblock_append(CBlock_t cblk, CInst_t inst);
+CInst_t cblock_getback(CBlock_t cblk);
+int cblock_isempty(CBlock_t cblk);
+
+typedef struct CEdge CEdge;
+typedef struct CGraph {
+ struct CEdge {
+ CBlock *to;
+ CEdge *next;
+ } *head[MAX_BLOCK], *rhead[MAX_BLOCK];
+} CGraph;
+
+void ssa_generate(CScope_t scope);
+#endif