Can allocate many tmps

3 files changed, 118 insertions, 38 deletions

diff --git a/src/code-generation.c b/src/code-generation.c
index 59e47ad..7abf51b 100644
--- a/src/code-generation.c
+++ b/src/code-generation.c
@@ -156,13 +156,13 @@ static void generate_block(
         offset_diff = current_offset - orig_offset;
         if (offset_diff > 0) {
             if (offset_diff > 4096) {
-                CcmmcTmp *tmp = ccmmc_register_alloc(state->reg_pool);
+                CcmmcTmp *tmp = ccmmc_register_alloc(state->reg_pool, &current_offset);
                 const char *reg_name = ccmmc_register_lock(state->reg_pool, tmp);
                 fprintf(state->asm_output,
                     "\tldr\t%s, =%" PRIu64 "\n"
                     "\tsub\tsp, sp, %s\n", reg_name, offset_diff, reg_name);
                 ccmmc_register_unlock(state->reg_pool, tmp);
-                ccmmc_register_free(state->reg_pool, tmp);
+                ccmmc_register_free(state->reg_pool, tmp, &current_offset);
             } else {
                 fprintf(state->asm_output, "\tsub\tsp, sp, #%" PRIu64 "\n",
                     offset_diff);
@@ -176,13 +176,13 @@ static void generate_block(
     }
     if (offset_diff > 0) {
         if (offset_diff > 4096) {
-            CcmmcTmp *tmp = ccmmc_register_alloc(state->reg_pool);
+            CcmmcTmp *tmp = ccmmc_register_alloc(state->reg_pool, &current_offset);
             const char *reg_name = ccmmc_register_lock(state->reg_pool, tmp);
             fprintf(state->asm_output,
                 "\tldr\t%s, =%" PRIu64 "\n"
                 "\tadd\tsp, sp, %s\n", reg_name, offset_diff, reg_name);
             ccmmc_register_unlock(state->reg_pool, tmp);
-            ccmmc_register_free(state->reg_pool, tmp);
+            ccmmc_register_free(state->reg_pool, tmp, &current_offset);
         } else {
             fprintf(state->asm_output, "\tadd\tsp, sp, #%" PRIu64 "\n",
                 offset_diff);
@@ -227,7 +227,7 @@ void ccmmc_code_generation(CcmmcState *state)
     state->table->this_scope = NULL;
     state->table->current = NULL;
     ccmmc_symbol_table_reopen_scope(state->table);
-    state->reg_pool = ccmmc_register_init();
+    state->reg_pool = ccmmc_register_init(state->asm_output);
     generate_program(state);
     ccmmc_register_fini(state->reg_pool);
     state->reg_pool = NULL;
diff --git a/src/register.c b/src/register.c
index 8f34255..99979b5 100644
--- a/src/register.c
+++ b/src/register.c
@@ -1,21 +1,21 @@
 #include "register.h"
 
 #include <assert.h>
+#include <inttypes.h>
 #include <stdbool.h>
+#include <stdio.h>
 #include <stdlib.h>
 
 #define REG_NUM 6
 #define REG_RESERVED "x9"
 #define REG_LOCK_MAX 3
+#define REG_SIZE 8
+#define SPILL_MAX 64
 
 static const char *reg_name[REG_NUM] = {
     "x10", "x11", "x12", "x13", "x14", "x15"};
 
-/* static void mov(CcmmcTmp *a, CcmmcTmp *b)
-{
-} */
-
-CcmmcRegPool *ccmmc_register_init(void)
+CcmmcRegPool *ccmmc_register_init(FILE *asm_output)
 {
     CcmmcRegPool *pool = malloc(sizeof(CcmmcRegPool));
     pool->num = REG_NUM;
@@ -26,26 +26,43 @@ CcmmcRegPool *ccmmc_register_init(void)
         pool->list[i]->lock = 0;
         pool->list[i]->name = reg_name[i];
     }
+    pool->spill = malloc(sizeof(CcmmcTmp*) * SPILL_MAX);
+    pool->top = 0;
     pool->lock_max = REG_LOCK_MAX;
     pool->lock_cnt = 0;
-    pool->top = 0;
-    pool->exceed = 0;
+    pool->asm_output = asm_output;
     return pool;
 }
 
-CcmmcTmp *ccmmc_register_alloc(CcmmcRegPool *pool)
+CcmmcTmp *ccmmc_register_alloc(CcmmcRegPool *pool, uint64_t *offset)
 {
     CcmmcTmp *tmp = malloc(sizeof(CcmmcTmp));
     if (pool->top < pool->num) {
-        tmp->reg = pool->list[pool->top];
+        // tmp
         tmp->addr = 0;
+        tmp->reg = pool->list[pool->top];
+
+        // reg
         tmp->reg->tmp = tmp;
+        tmp->reg->lock = 0;
+
+        // pool
         pool->top++;
     }
     else {
+        // gen code to alloc space on the stack
+        fprintf(pool->asm_output, "\tsub\tsp, sp, #%d\n", REG_SIZE);
+
+        // tmp and offset
+        *offset += REG_SIZE;
+        tmp->addr = *offset;
         tmp->reg = NULL;
-        tmp->addr = (pool->exceed + 1) * (-8); // TODO: assign an offset for original tmp
-        pool->exceed++;
+
+        // spill
+        pool->spill[pool->top - pool->num] = tmp;
+
+        // pool
+        pool->top++;
     }
     return tmp;
 }
@@ -56,26 +73,49 @@ const char *ccmmc_register_lock(CcmmcRegPool *pool, CcmmcTmp *tmp)
     if (pool->lock_cnt < pool->lock_max) {
         if (tmp->reg !=NULL) {
             if (tmp->reg->lock == 0) {
+                // reg
                 tmp->reg->lock = 1;
+
+                // pool
                 pool->lock_cnt++;
             }
             reg = tmp->reg->name;
         }
-        else { // find a unlocked reg
-            int i;
+        else {
+            // find a unlocked reg
+            int i, j;
             for (i = 0; i < pool->num && pool->list[i]->lock == 1; i++);
+            assert(i < pool->num); //must found
+
+            // gen code to swap the tmp in the register and the tmp on the stack
+            fprintf(pool->asm_output, "\tmov\t%s, %s\n", REG_RESERVED,
+                pool->list[i]->name);
+            fprintf(pool->asm_output, "\tldr\t%s, [fp - #%" PRIu64 "]\n",
+                pool->list[i]->name, tmp->addr);
+            fprintf(pool->asm_output, "\tstr\t%s, [fp - #%" PRIu64 "]\n",
+                REG_RESERVED, tmp->addr);
 
-            // TODO: mov REG_RESERVED, pool->list[i]->name
-            // TODO: ldr pool->list[i]->name, tmp->addr
-            // TODO: str REG_RESERVED, tmp->addr
+            // find the index of tmp in pool->spill
+            for (j = 0; j < pool->top - pool->num && pool->spill[j] != tmp; j++);
 
+            // spill
+            pool->spill[j] = pool->list[i]->tmp;
+
+            // old tmp of the reg
             pool->list[i]->tmp->reg = NULL;
             pool->list[i]->tmp->addr = tmp->addr;
+
+            // tmp
             tmp->reg = pool->list[i];
             tmp->addr = 0;
 
+            // register
+            tmp->reg->tmp = tmp;
             tmp->reg->lock = 1;
+
+            // pool
             pool->lock_cnt++;
+
             reg = tmp->reg->name;
         }
     }
@@ -85,26 +125,60 @@ const char *ccmmc_register_lock(CcmmcRegPool *pool, CcmmcTmp *tmp)
 void ccmmc_register_unlock(CcmmcRegPool *pool, CcmmcTmp *tmp)
 {
     if (tmp->reg != NULL && tmp->reg->lock == 1) {
+        // reg
         tmp->reg->lock = 0;
+
+        // pool
         pool->lock_cnt--;
     }
 }
 
-void ccmmc_register_free(CcmmcRegPool *pool, CcmmcTmp *tmp)
+void ccmmc_register_free(CcmmcRegPool *pool, CcmmcTmp *tmp, uint64_t *offset)
 {
-    if (pool->exceed == 0) {
-        int i;
-        for (i = 0; i < pool->num && pool->list[i] != tmp->reg; i++);
-        if (i < pool->top - 1) {
+    // find the index of register associated with tmp
+    int i;
+    for (i = 0; i < pool->num && pool->list[i] != tmp->reg; i++);
+
+    if (pool->top <= pool->num) {
+        // tmp
+        free(tmp);
+
+        // pool
+        pool->top--;
+        assert(i < pool->num); //must found
+        if (i < pool->top) {
             CcmmcReg *swap = pool->list[i];
-            pool->list[i] = pool->list[pool->top - 1];
-            pool->list[pool->top - 1] = swap;
+            pool->list[i] = pool->list[pool->top];
+            pool->list[pool->top] = swap;
         }
-        pool->top--;
-        free(tmp);
     }
     else {
-        assert(false);
+        if (i < pool->num) {
+            // pool
+            pool->top--;
+
+            // gen code to move the last tmp to this register
+            fprintf(pool->asm_output, "\tldr\t%s, [fp - #%" PRIu64 "]\n",
+                tmp->reg->name, pool->spill[pool->top - pool->num]->addr);
+            fprintf(pool->asm_output, "\tadd\tsp, sp, #%d\n", REG_SIZE);
+
+            // offset
+            *offset -= REG_SIZE;
+
+            // reg
+            tmp->reg->tmp = pool->spill[pool->top - pool->num];
+
+            // the last tmp
+            tmp->reg->tmp->reg = tmp->reg;
+            tmp->reg->tmp->addr = 0;
+
+            // tmp
+            free(tmp);
+        }
+        else {
+            // tmp is on the stack, not handled
+            assert(false);
+        }
     }
 }
 
diff --git a/src/register.h b/src/register.h
index 52cab17..068f6d0 100644
--- a/src/register.h
+++ b/src/register.h
@@ -1,10 +1,13 @@
+#include <inttypes.h>
+#include <stdio.h>
+
 #ifndef CCMMC_HEADER_REGISTER_H
 #define CCMMC_HEADER_REGISTER_H
 
 typedef struct CcmmcRegStruct CcmmcReg;
 typedef struct CcmmcTmpStruct {
     CcmmcReg *reg;
-    int addr;
+    uint64_t addr;
 } CcmmcTmp;
 
 typedef struct CcmmcRegStruct {
@@ -16,20 +19,23 @@ typedef struct CcmmcRegStruct {
 typedef struct CcmmcRegPoolStruct {
     CcmmcReg **list;
     int num;
-    int lock_cnt;
-    int lock_max;
     int top;
-    int exceed;
+    CcmmcTmp **spill;
+    int lock_max;
+    int lock_cnt;
+    FILE *asm_output;
 } CcmmcRegPool;
 
-CcmmcRegPool    *ccmmc_register_init                (void);
-CcmmcTmp        *ccmmc_register_alloc               (CcmmcRegPool *pool);
+CcmmcRegPool    *ccmmc_register_init                (FILE *asm_output);
+CcmmcTmp        *ccmmc_register_alloc               (CcmmcRegPool *pool,
+                                                     uint64_t *offset);
 const char      *ccmmc_register_lock                (CcmmcRegPool *pool,
                                                      CcmmcTmp *tmp);
 void             ccmmc_register_unlock              (CcmmcRegPool *pool,
                                                      CcmmcTmp *tmp);
 void             ccmmc_register_free                (CcmmcRegPool *pool,
-                                                     CcmmcTmp *tmp);
+                                                     CcmmcTmp *tmp,
+                                                     uint64_t *offset);
 void             ccmmc_register_caller_save         (CcmmcRegPool *pool);
 void             ccmmc_register_caller_load         (CcmmcRegPool *pool);
 void             ccmmc_register_fini                (CcmmcRegPool *pool);