X-Git-Url: https://git.xonotic.org/?p=xonotic%2Fgmqcc.git;a=blobdiff_plain;f=ir.c;h=b1835c875b586e3eae3bcc49cb0b80d1519e19b5;hp=91e8d7f5ca54f6bba11650eb152f4e71af9f62cc;hb=5e23e8296d1d82df528481e04262a9e3afb38908;hpb=ebc6954bf566a1e7f66eee8be5f4d9b06fb05212

diff --git a/ir.c b/ir.c
index 91e8d7f..b1835c8 100644
--- a/ir.c
+++ b/ir.c
@@ -284,6 +284,9 @@ ir_builder* ir_builder_new(const char *modulename)
     self->extparams   = NULL;
     self->filenames   = NULL;
     self->filestrings = NULL;
+    self->htglobals   = util_htnew(IR_HT_SIZE);
+    self->htfields    = util_htnew(IR_HT_SIZE);
+    self->htfunctions = util_htnew(IR_HT_SIZE);
 
     self->str_immediate = 0;
     self->name = NULL;
@@ -298,6 +301,9 @@ ir_builder* ir_builder_new(const char *modulename)
 void ir_builder_delete(ir_builder* self)
 {
     size_t i;
+    util_htdel(self->htglobals);
+    util_htdel(self->htfields);
+    util_htdel(self->htfunctions);
     mem_d((void*)self->name);
     for (i = 0; i != vec_size(self->functions); ++i) {
         ir_function_delete_quick(self->functions[i]);
@@ -330,12 +336,7 @@ bool ir_builder_set_name(ir_builder *self, const char *name)
 
 ir_function* ir_builder_get_function(ir_builder *self, const char *name)
 {
-    size_t i;
-    for (i = 0; i < vec_size(self->functions); ++i) {
-        if (!strcmp(name, self->functions[i]->name))
-            return self->functions[i];
-    }
-    return NULL;
+    return (ir_function*)util_htget(self->htfunctions, name);
 }
 
 ir_function* ir_builder_create_function(ir_builder *self, const char *name, int outtype)
@@ -352,6 +353,7 @@ ir_function* ir_builder_create_function(ir_builder *self, const char *name, int
         return NULL;
     }
     vec_push(self->functions, fn);
+    util_htset(self->htfunctions, name, fn);
 
     fn->value = ir_builder_create_global(self, fn->name, TYPE_FUNCTION);
     if (!fn->value) {
@@ -359,7 +361,7 @@ ir_function* ir_builder_create_function(ir_builder *self, const char *name, int
         return NULL;
     }
 
-    fn->value->isconst = true;
+    fn->value->hasvalue = true;
     fn->value->outtype = outtype;
     fn->value->constval.vfunc = fn;
     fn->value->context = fn->context;
@@ -369,12 +371,7 @@ ir_function* ir_builder_create_function(ir_builder *self, const char *name, int
 
 ir_value* ir_builder_get_global(ir_builder *self, const char *name)
 {
-    size_t i;
-    for (i = 0; i < vec_size(self->globals); ++i) {
-        if (!strcmp(self->globals[i]->name, name))
-            return self->globals[i];
-    }
-    return NULL;
+    return (ir_value*)util_htget(self->htglobals, name);
 }
 
 ir_value* ir_builder_create_global(ir_builder *self, const char *name, int vtype)
@@ -391,17 +388,13 @@ ir_value* ir_builder_create_global(ir_builder *self, const char *name, int vtype
 
     ve = ir_value_var(name, store_global, vtype);
     vec_push(self->globals, ve);
+    util_htset(self->htglobals, name, ve);
     return ve;
 }
 
 ir_value* ir_builder_get_field(ir_builder *self, const char *name)
 {
-    size_t i;
-    for (i = 0; i < vec_size(self->fields); ++i) {
-        if (!strcmp(self->fields[i]->name, name))
-            return self->fields[i];
-    }
-    return NULL;
+    return (ir_value*)util_htget(self->htfields, name);
 }
 
 
@@ -415,6 +408,7 @@ ir_value* ir_builder_create_field(ir_builder *self, const char *name, int vtype)
     ve = ir_value_var(name, store_global, TYPE_FIELD);
     ve->fieldtype = vtype;
     vec_push(self->fields, ve);
+    util_htset(self->htfields, name, ve);
     return ve;
 }
 
@@ -522,19 +516,113 @@ void ir_function_collect_value(ir_function *self, ir_value *v)
     vec_push(self->values, v);
 }
 
-ir_block* ir_function_create_block(ir_function *self, const char *label)
+ir_block* ir_function_create_block(lex_ctx ctx, ir_function *self, const char *label)
 {
     ir_block* bn = ir_block_new(self, label);
-    memcpy(&bn->context, &self->context, sizeof(self->context));
+    bn->context = ctx;
     vec_push(self->blocks, bn);
     return bn;
 }
 
+bool ir_function_pass_tailcall(ir_function *self)
+{
+    size_t b, p;
+
+    for (b = 0; b < vec_size(self->blocks); ++b) {
+        ir_value *funcval;
+        ir_instr *ret, *call, *store = NULL;
+        ir_block *block = self->blocks[b];
+
+        if (!block->final || vec_size(block->instr) < 2)
+            continue;
+
+        ret = block->instr[vec_size(block->instr)-1];
+        if (ret->opcode != INSTR_DONE && ret->opcode != INSTR_RETURN)
+            continue;
+
+        call = block->instr[vec_size(block->instr)-2];
+        if (call->opcode >= INSTR_STORE_F && call->opcode <= INSTR_STORE_FNC) {
+            /* account for the unoptimized
+             * CALL
+             * STORE %return, %tmp
+             * RETURN %tmp
+             * version
+             */
+            if (vec_size(block->instr) < 3)
+                continue;
+
+            store = call;
+            call = block->instr[vec_size(block->instr)-3];
+        }
+
+        if (call->opcode < INSTR_CALL0 || call->opcode > INSTR_CALL8)
+            continue;
+
+        if (store) {
+            /* optimize out the STORE */
+            if (ret->_ops[0]   &&
+                ret->_ops[0]   == store->_ops[0] &&
+                store->_ops[1] == call->_ops[0])
+            {
+                ++optimization_count[OPTIM_MINOR];
+                call->_ops[0] = store->_ops[0];
+                vec_remove(block->instr, vec_size(block->instr) - 2, 1);
+                ir_instr_delete(store);
+            }
+            else
+                continue;
+        }
+
+        if (!call->_ops[0])
+            continue;
+
+        funcval = call->_ops[1];
+        if (!funcval)
+            continue;
+        if (funcval->vtype != TYPE_FUNCTION || funcval->constval.vfunc != self)
+            continue;
+
+        /* now we have a CALL and a RET, check if it's a tailcall */
+        if (ret->_ops[0] && call->_ops[0] != ret->_ops[0])
+            continue;
+
+        ++optimization_count[OPTIM_TAIL_RECURSION];
+        vec_shrinkby(block->instr, 2);
+
+        block->final = false; /* open it back up */
+
+        /* emite parameter-stores */
+        for (p = 0; p < vec_size(call->params); ++p) {
+            /* assert(call->params_count <= self->locals_count); */
+            if (!ir_block_create_store(block, self->locals[p], call->params[p])) {
+                irerror(call->context, "failed to create tailcall store instruction for parameter %i", (int)p);
+                return false;
+            }
+        }
+        if (!ir_block_create_jump(block, self->blocks[0])) {
+            irerror(call->context, "failed to create tailcall jump");
+            return false;
+        }
+
+        ir_instr_delete(call);
+        ir_instr_delete(ret);
+    }
+
+    return true;
+}
+
 bool ir_function_finalize(ir_function *self)
 {
     if (self->builtin)
         return true;
 
+    if (OPTS_OPTIMIZATION(OPTIM_TAIL_RECURSION)) {
+        if (!ir_function_pass_tailcall(self)) {
+            irerror(self->context, "tailcall optimization pass broke something in `%s`", self->name);
+            return false;
+        }
+    }
+
     if (!ir_function_naive_phi(self))
         return false;
 
@@ -542,31 +630,15 @@ bool ir_function_finalize(ir_function *self)
 
     if (!ir_function_calculate_liferanges(self))
         return false;
-
     if (!ir_function_allocate_locals(self))
         return false;
     return true;
 }
 
-ir_value* ir_function_get_local(ir_function *self, const char *name)
-{
-    size_t i;
-    for (i = 0; i < vec_size(self->locals); ++i) {
-        if (!strcmp(self->locals[i]->name, name))
-            return self->locals[i];
-    }
-    return NULL;
-}
-
 ir_value* ir_function_create_local(ir_function *self, const char *name, int vtype, bool param)
 {
     ir_value *ve;
 
-    /*
-    if (ir_function_get_local(self, name))
-        return NULL;
-    */
-
     if (param &&
         vec_size(self->locals) &&
         self->locals[vec_size(self->locals)-1]->store != store_param) {
@@ -769,7 +841,8 @@ ir_value* ir_value_var(const char *name, int storetype, int vtype)
     self->reads  = NULL;
     self->writes = NULL;
 
-    self->isconst = false;
+    self->cvq          = CV_NONE;
+    self->hasvalue     = false;
     self->context.file = "<@no context>";
     self->context.line = 0;
     self->name = NULL;
@@ -847,7 +920,7 @@ void ir_value_delete(ir_value* self)
     size_t i;
     if (self->name)
         mem_d((void*)self->name);
-    if (self->isconst)
+    if (self->hasvalue)
     {
         if (self->vtype == TYPE_STRING)
             mem_d((void*)self->constval.vstring);
@@ -875,7 +948,7 @@ bool ir_value_set_float(ir_value *self, float f)
     if (self->vtype != TYPE_FLOAT)
         return false;
     self->constval.vfloat = f;
-    self->isconst = true;
+    self->hasvalue = true;
     return true;
 }
 
@@ -884,7 +957,7 @@ bool ir_value_set_func(ir_value *self, int f)
     if (self->vtype != TYPE_FUNCTION)
         return false;
     self->constval.vint = f;
-    self->isconst = true;
+    self->hasvalue = true;
     return true;
 }
 
@@ -893,7 +966,7 @@ bool ir_value_set_vector(ir_value *self, vector v)
     if (self->vtype != TYPE_VECTOR)
         return false;
     self->constval.vvec = v;
-    self->isconst = true;
+    self->hasvalue = true;
     return true;
 }
 
@@ -902,7 +975,7 @@ bool ir_value_set_field(ir_value *self, ir_value *fld)
     if (self->vtype != TYPE_FIELD)
         return false;
     self->constval.vpointer = fld;
-    self->isconst = true;
+    self->hasvalue = true;
     return true;
 }
 
@@ -922,7 +995,7 @@ bool ir_value_set_string(ir_value *self, const char *str)
     if (self->vtype != TYPE_STRING)
         return false;
     self->constval.vstring = ir_strdup(str);
-    self->isconst = true;
+    self->hasvalue = true;
     return true;
 }
 
@@ -932,7 +1005,7 @@ bool ir_value_set_int(ir_value *self, int i)
     if (self->vtype != TYPE_INTEGER)
         return false;
     self->constval.vint = i;
-    self->isconst = true;
+    self->hasvalue = true;
     return true;
 }
 #endif
@@ -2171,6 +2244,9 @@ static bool ir_block_living_add_instr(ir_block *self, size_t eid)
 static bool ir_block_life_prop_previous(ir_block* self, ir_block *prev, bool *changed)
 {
     size_t i;
+
+    (void)changed;
+
     /* values which have been read in a previous iteration are now
      * in the "living" array even if the previous block doesn't use them.
      * So we have to remove whatever does not exist in the previous block.
@@ -2365,7 +2441,7 @@ static bool ir_builder_gen_global(ir_builder *self, ir_value *global, bool isloc
 
 static bool gen_global_field(ir_value *global)
 {
-    if (global->isconst)
+    if (global->hasvalue)
     {
         ir_value *fld = global->constval.vpointer;
         if (!fld) {
@@ -2410,7 +2486,7 @@ static bool gen_global_field(ir_value *global)
 
 static bool gen_global_pointer(ir_value *global)
 {
-    if (global->isconst)
+    if (global->hasvalue)
     {
         ir_value *target = global->constval.vpointer;
         if (!target) {
@@ -2601,20 +2677,20 @@ tailcall:
                 stmt.o2.u1 = OFS_PARM0 + 3 * p;
                 vec_push(code_statements, stmt);
             }
-            /* No whandle extparams */
+            /* Now handle extparams */
             first = vec_size(instr->params);
             for (; p < first; ++p)
             {
                 ir_builder *ir = func->owner;
                 ir_value *param = instr->params[p];
-                ir_value *target;
+                ir_value *targetparam;
 
                 if (p-8 >= vec_size(ir->extparams)) {
                     irerror(instr->context, "Not enough extparam-globals have been created");
                     return false;
                 }
 
-                target = ir->extparams[p-8];
+                targetparam = ir->extparams[p-8];
 
                 stmt.opcode = INSTR_STORE_F;
                 stmt.o3.u1 = 0;
@@ -2624,7 +2700,7 @@ tailcall:
                 else
                     stmt.opcode = type_store_instr[param->vtype];
                 stmt.o1.u1 = ir_value_code_addr(param);
-                stmt.o2.u1 = ir_value_code_addr(target);
+                stmt.o2.u1 = ir_value_code_addr(targetparam);
                 vec_push(code_statements, stmt);
             }
 
@@ -2750,7 +2826,7 @@ static bool gen_global_function(ir_builder *ir, ir_value *global)
     size_t i;
     size_t local_var_end;
 
-    if (!global->isconst || (!global->constval.vfunc))
+    if (!global->hasvalue || (!global->constval.vfunc))
     {
         irerror(global->context, "Invalid state of function-global: not constant: %s", global->name);
         return false;
@@ -2872,6 +2948,8 @@ static bool gen_global_function_code(ir_builder *ir, ir_value *global)
     prog_section_function *fundef;
     ir_function           *irfun;
 
+    (void)ir;
+
     irfun = global->constval.vfunc;
     if (!irfun) {
         irwarning(global->context, WARN_IMPLICIT_FUNCTION_POINTER,
@@ -2958,7 +3036,7 @@ static bool ir_builder_gen_global(ir_builder *self, ir_value *global, bool isloc
     case TYPE_FLOAT:
     {
         ir_value_code_setaddr(global, vec_size(code_globals));
-        if (global->isconst) {
+        if (global->hasvalue) {
             iptr = (int32_t*)&global->constval.ivec[0];
             vec_push(code_globals, *iptr);
         } else {
@@ -2973,7 +3051,7 @@ static bool ir_builder_gen_global(ir_builder *self, ir_value *global, bool isloc
     case TYPE_STRING:
     {
         ir_value_code_setaddr(global, vec_size(code_globals));
-        if (global->isconst) {
+        if (global->hasvalue) {
             vec_push(code_globals, code_genstring(global->constval.vstring));
         } else {
             vec_push(code_globals, 0);
@@ -2987,7 +3065,7 @@ static bool ir_builder_gen_global(ir_builder *self, ir_value *global, bool isloc
     {
         size_t d;
         ir_value_code_setaddr(global, vec_size(code_globals));
-        if (global->isconst) {
+        if (global->hasvalue) {
             iptr = (int32_t*)&global->constval.ivec[0];
             vec_push(code_globals, iptr[0]);
             if (global->code.globaladdr < 0)
@@ -3013,7 +3091,7 @@ static bool ir_builder_gen_global(ir_builder *self, ir_value *global, bool isloc
     }
     case TYPE_FUNCTION:
         ir_value_code_setaddr(global, vec_size(code_globals));
-        if (!global->isconst) {
+        if (!global->hasvalue) {
             vec_push(code_globals, 0);
             if (global->code.globaladdr < 0)
                 return false;
@@ -3046,8 +3124,10 @@ static bool ir_builder_gen_field(ir_builder *self, ir_value *field)
     prog_section_def def;
     prog_section_field fld;
 
-    def.type   = field->vtype;
-    def.offset = vec_size(code_globals);
+    (void)self;
+
+    def.type   = (uint16_t)field->vtype;
+    def.offset = (uint16_t)vec_size(code_globals);
 
     /* create a global named the same as the field */
     if (opts_standard == COMPILER_GMQCC) {
@@ -3135,6 +3215,11 @@ bool ir_builder_generate(ir_builder *self, const char *filename)
         }
     }
 
+    if (vec_size(code_globals) >= 65536) {
+        irerror(vec_last(self->globals)->context, "This progs file would require more globals than the metadata can handle. Bailing out.");
+        return false;
+    }
+
     /* DP errors if the last instruction is not an INSTR_DONE
      * and for debugging purposes we add an additional AINSTR_END
      * to the end of functions, so here it goes:
@@ -3163,7 +3248,7 @@ bool ir_builder_generate(ir_builder *self, const char *filename)
 const char *qc_opname(int op)
 {
     if (op < 0) return "<INVALID>";
-    if (op < ( sizeof(asm_instr) / sizeof(asm_instr[0]) ))
+    if (op < (int)( sizeof(asm_instr) / sizeof(asm_instr[0]) ))
         return asm_instr[op].m;
     switch (op) {
         case VINSTR_PHI:  return "PHI";
@@ -3184,7 +3269,7 @@ void ir_builder_dump(ir_builder *b, int (*oprintf)(const char*, ...))
     for (i = 0; i < vec_size(b->globals); ++i)
     {
         oprintf("global ");
-        if (b->globals[i]->isconst)
+        if (b->globals[i]->hasvalue)
             oprintf("%s = ", b->globals[i]->name);
         ir_value_dump(b->globals[i], oprintf);
         oprintf("\n");
@@ -3259,8 +3344,7 @@ void ir_block_dump(ir_block* b, char *ind,
     ind[strlen(ind)-1] = 0;
 }
 
-void dump_phi(ir_instr *in, char *ind,
-              int (*oprintf)(const char*, ...))
+void dump_phi(ir_instr *in, int (*oprintf)(const char*, ...))
 {
     size_t i;
     oprintf("%s <- phi ", in->_ops[0]->name);
@@ -3281,7 +3365,7 @@ void ir_instr_dump(ir_instr *in, char *ind,
     oprintf("%s (%i) ", ind, (int)in->eid);
 
     if (in->opcode == VINSTR_PHI) {
-        dump_phi(in, ind, oprintf);
+        dump_phi(in, oprintf);
         return;
     }
 
@@ -3330,9 +3414,29 @@ void ir_instr_dump(ir_instr *in, char *ind,
     ind[strlen(ind)-1] = 0;
 }
 
+void ir_value_dump_string(const char *str, int (*oprintf)(const char*, ...))
+{
+    oprintf("\"");
+    for (; *str; ++str) {
+        switch (*str) {
+            case '\n': oprintf("\\n"); break;
+            case '\r': oprintf("\\r"); break;
+            case '\t': oprintf("\\t"); break;
+            case '\v': oprintf("\\v"); break;
+            case '\f': oprintf("\\f"); break;
+            case '\b': oprintf("\\b"); break;
+            case '\a': oprintf("\\a"); break;
+            case '\\': oprintf("\\\\"); break;
+            case '"': oprintf("\\\""); break;
+            default: oprintf("%c", *str); break;
+        }
+    }
+    oprintf("\"");
+}
+
 void ir_value_dump(ir_value* v, int (*oprintf)(const char*, ...))
 {
-    if (v->isconst) {
+    if (v->hasvalue) {
         switch (v->vtype) {
             default:
             case TYPE_VOID:
@@ -3354,7 +3458,7 @@ void ir_value_dump(ir_value* v, int (*oprintf)(const char*, ...))
                 oprintf("(entity)");
                 break;
             case TYPE_STRING:
-                oprintf("\"%s\"", v->constval.vstring);
+                ir_value_dump_string(v->constval.vstring, oprintf);
                 break;
 #if 0
             case TYPE_INTEGER: