value position allocation, fixing a possible endless loop in ir_values_overlap

diff --git a/ir.c b/ir.c
index 398744ed512f376d82874ed764236795284c5e5c..806b8bd98130bf2b1c292d5684ad5d4579ea0222 100644 (file)
--- a/ir.c
+++ b/ir.c
@@ -438,7 +438,8 @@ ir_value* ir_value_out(ir_function *owner, const char *name, int storetype, int
 
 void ir_value_delete(ir_value* self)
 {
-    mem_d((void*)self->name);
+    if (self->name)
+        mem_d((void*)self->name);
     if (self->isconst)
     {
         if (self->vtype == TYPE_STRING)
@@ -661,7 +662,7 @@ bool ir_value_life_merge_into(ir_value *self, const ir_value *other)
     return true;
 }
 
-bool ir_values_overlap(ir_value *a, ir_value *b)
+bool ir_values_overlap(const ir_value *a, const ir_value *b)
 {
     /* For any life entry in A see if it overlaps with
      * any life entry in B.
@@ -700,7 +701,7 @@ bool ir_values_overlap(ir_value *a, ir_value *b)
          * one entry is earlier than the other
          * that earlier entry will be moved forward
          */
-        if (la->end < lb->end)
+        if (la->start < lb->start)
         {
             /* order: A B, move A forward
              * check if we hit the end with A
@@ -708,7 +709,7 @@ bool ir_values_overlap(ir_value *a, ir_value *b)
             if (++la == enda)
                 break;
         }
-        else if (lb->end < la->end)
+        else if (lb->start < la->start)
         {
             /* order: B A, move B forward
              * check if we hit the end with B
@@ -1500,9 +1501,128 @@ bool ir_function_calculate_liferanges(ir_function *self)
  * we can allocate their global-positions.
  * This is the counterpart to register-allocation in register machines.
  */
+typedef struct {
+    MEM_VECTOR_MAKE(ir_value*, locals);
+    MEM_VECTOR_MAKE(size_t,    sizes);
+    MEM_VECTOR_MAKE(size_t,    positions);
+} function_allocator;
+MEM_VEC_FUNCTIONS(function_allocator, ir_value*, locals)
+MEM_VEC_FUNCTIONS(function_allocator, size_t,    sizes)
+MEM_VEC_FUNCTIONS(function_allocator, size_t,    positions)
+
+static bool function_allocator_alloc(function_allocator *alloc, const ir_value *var)
+{
+    ir_value *slot;
+    size_t vsize = 1;
+
+    slot = ir_value_var("reg", store_global, var->vtype);
+    if (!slot)
+        return false;
+
+    if (slot->vtype == TYPE_VECTOR || slot->vtype == TYPE_VARIANT)
+        vsize = 3;
+
+    if (!ir_value_life_merge_into(slot, var))
+        goto localerror;
+
+    if (!function_allocator_locals_add(alloc, slot))
+        goto localerror;
+
+    if (!function_allocator_sizes_add(alloc, vsize))
+        goto localerror;
+
+    return true;
+
+localerror:
+    ir_value_delete(slot);
+    return false;
+}
+
 bool ir_function_allocate_locals(ir_function *self)
 {
-    return true;
+    size_t i, a;
+    bool   retval = true;
+    size_t pos;
+
+    ir_value *slot;
+    const ir_value *v;
+
+    function_allocator alloc;
+
+    MEM_VECTOR_INIT(&alloc, locals);
+    MEM_VECTOR_INIT(&alloc, sizes);
+    MEM_VECTOR_INIT(&alloc, positions);
+
+    for (i = 0; i < self->locals_count; ++i)
+    {
+        if (!function_allocator_alloc(&alloc, self->locals[i]))
+            goto error;
+    }
+
+    /* Allocate a slot for any value that still exists */
+    for (i = 0; i < self->values_count; ++i)
+    {
+        v = self->values[i];
+
+        if (!v->life_count)
+            continue;
+
+        for (a = 0; a < alloc.locals_count; ++a)
+        {
+            slot = alloc.locals[a];
+
+            if (ir_values_overlap(v, slot)) {
+                printf("over\n");
+                continue;
+            }
+                printf("not\n");
+
+            if (!ir_value_life_merge_into(slot, v))
+                goto error;
+
+            /* adjust size for this slot */
+            if (v->vtype == TYPE_VECTOR || v->vtype == TYPE_VARIANT)
+                alloc.sizes[a] = 3;
+
+            self->values[i]->code.slot = a;
+            break;
+        }
+        if (a >= alloc.locals_count) {
+            self->values[i]->code.slot = alloc.locals_count;
+            if (!function_allocator_alloc(&alloc, v))
+                goto error;
+        }
+    }
+
+    /* Adjust slot positions based on sizes */
+    if (!function_allocator_positions_add(&alloc, 0))
+        goto error;
+
+    for (i = 1; i < alloc.sizes_count; ++i)
+    {
+        pos = alloc.positions[i-1] + alloc.sizes[i-1];
+        if (!function_allocator_positions_add(&alloc, pos))
+            goto error;
+    }
+
+    /* Take over the actual slot positions */
+    for (i = 0; i < self->values_count; ++i)
+        self->values[i]->code.slot = alloc.positions[self->values[i]->code.slot];
+
+    for (i = 0; i < self->values_count; ++i)
+        printf("Value %s at slot %i\n", self->values[i]->name,
+                                        self->values[i]->code.slot);
+    goto cleanup;
+
+error:
+    retval = false;
+cleanup:
+    for (i = 0; i < alloc.locals_count; ++i)
+        ir_value_delete(alloc.locals[i]);
+    MEM_VECTOR_CLEAR(&alloc, locals);
+    MEM_VECTOR_CLEAR(&alloc, sizes);
+    MEM_VECTOR_CLEAR(&alloc, positions);
+    return retval;
 }
 
 /* Get information about which operand

diff --git a/ir.h b/ir.h
index a7f0076ccaf6ada0d6cbc85850d5b9af8377839e..3cb045c5d8a42092aa457d5f1b2b9398ec35284f 100644 (file)
--- a/ir.h
+++ b/ir.h
@@ -58,6 +58,8 @@ typedef struct ir_value_s {
     struct {
         int32_t globaladdr;
         int32_t name;
+        /* filled by the local-allocator */
+        int32_t slot;
     } code;
 
     /* For the temp allocator */
@@ -93,7 +95,7 @@ bool ir_value_life_merge_into(ir_value*, const ir_value*);
 /* check if a value lives at a specific point */
 bool ir_value_lives(ir_value*, size_t);
 /* check if the life-range of 2 values overlaps */
-bool ir_values_overlap(ir_value*, ir_value*);
+bool ir_values_overlap(const ir_value*, const ir_value*);
 
 void ir_value_dump(ir_value*, int (*oprintf)(const char*,...));
 void ir_value_dump_life(ir_value *self, int (*oprintf)(const char*,...));