'&' operator

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