ssa init

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