projects / mono.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
2007-10-08 Mark Probst <mark.probst@gmail.com>
[mono.git] / mono / mini / linear-scan.c
diff --git a/mono/mini/linear-scan.c b/mono/mini/linear-scan.c
index 3cf0775d29699fb070cde27fa60e5724caf8e8d3..cfb4ad327aac3ebc77a0d2e954470d968405223f 100644 (file)
--- a/mono/mini/linear-scan.c
+++ b/mono/mini/linear-scan.c
@@ -8,6 +8,7 @@
  */
 
 #include "mini.h"
+#include <mono/metadata/debug-helpers.h>
 
 GList *
 mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, int sort_type)
@@ -43,18 +44,38 @@ mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, in
        return list;
 }
 
-//#define DEBUG_LSCAN
+static gint 
+compare_by_first_use_func (gconstpointer a, gconstpointer b)
+{
+       MonoMethodVar *v1 = (MonoMethodVar*)a;
+       MonoMethodVar *v2 = (MonoMethodVar*)b;
+
+       return v1->range.first_use.abs_pos - v2->range.first_use.abs_pos;
+}
+
+GList *
+mono_varlist_sort (MonoCompile *cfg, GList *list, int sort_type)
+{
+       if (sort_type == 0)
+               return g_list_sort (list, compare_by_first_use_func);
+       else
+               g_assert_not_reached ();
+
+       return NULL;
+}
+
+// #define DEBUG_LSCAN
 
 void
-mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, guint32 *used_mask)
+mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
 {
        GList *l, *a, *active = NULL;
        MonoMethodVar *vmv, *amv;
-       int max_regs, gains [32];
-       guint32 used_regs = 0;
+       int max_regs, gains [sizeof (regmask_t) * 8];
+       regmask_t used_regs = 0;
        gboolean cost_driven;
 
-       cost_driven = (cfg->comp_done & MONO_COMP_LOOPS);
+       cost_driven = TRUE;
 
 #ifdef DEBUG_LSCAN
        printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
@@ -70,7 +91,7 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, guint32 *used_mask
        max_regs = g_list_length (regs);
 
        for (l = regs; l; l = l->next) {
-               int regnum = (int)l->data;
+               int regnum = GPOINTER_TO_INT (l->data);
                g_assert (regnum < G_N_ELEMENTS (gains));
                gains [regnum] = 0;
        }
@@ -87,18 +108,18 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, guint32 *used_mask
                while (active) {
                        amv = (MonoMethodVar *)active->data;
 
-                       if (amv->range.last_use.abs_pos >= vmv->range.first_use.abs_pos)
+                       if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
                                break;
 
 #ifdef DEBUG_LSCAN
                        printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos, 
                                amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 #endif
-                       active = g_list_remove_link (active, active);
-                       regs = g_list_prepend (regs, (gpointer)amv->reg);
+                       active = g_list_delete_link (active, active);
+                       regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
                        gains [amv->reg] += amv->spill_costs;
                }
-               
+
                if (active && g_list_length (active) == max_regs) {
                        /* Spill */
 
@@ -109,7 +130,7 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, guint32 *used_mask
                            (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
                                vmv->reg = amv->reg;
                                amv->reg = -1;
-                               active = g_list_remove_link (active, a);
+                               active = g_list_delete_link (active, a);
 
                                if (cost_driven)
                                        active = mono_varlist_insert_sorted (cfg, active, vmv, 2);      
@@ -134,16 +155,16 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, guint32 *used_mask
 
                        g_assert (regs);
 
-                       vmv->reg = (int)regs->data;
+                       vmv->reg = GPOINTER_TO_INT (regs->data);
 
-                       used_regs |= 1 << vmv->reg;
+                       used_regs |= 1LL << vmv->reg;
 
-                       regs = g_list_remove_link (regs, regs);
+                       regs = g_list_delete_link (regs, regs);
 
 #ifdef DEBUG_LSCAN
-                       printf ("ADD    %2d %08x %08x C%d\n",  vnum, 
+                       printf ("ADD    %2d %08x %08x C%d R%d\n",  vmv->idx, 
                                vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos, 
-                               vmv->spill_costs);
+                               vmv->spill_costs, vmv->reg);
 #endif
                        active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);           
                }
@@ -168,22 +189,57 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, guint32 *used_mask
                vmv = l->data;
                
                if (vmv->reg >= 0)  {
-                       if (gains [vmv->reg] > 5) {
+                       if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
                                cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
                                cfg->varinfo [vmv->idx]->dreg = vmv->reg;
-#ifdef DEBUG_LSCAN
-                               printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
-#endif
+                               if (cfg->verbose_level > 2)
+                                       printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
                        } else {
-                               used_regs &= ~(1 << vmv->reg); 
+                               if (cfg->verbose_level > 2)
+                                       printf ("COSTLY: %s R%d C%d C%d %s\n", mono_method_full_name (cfg->method, TRUE), vmv->idx, vmv->spill_costs, mono_arch_regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
                                vmv->reg = -1;
                        }
                }
+
+               if (vmv->reg == -1) {
+                       if ((vmv->range.first_use.abs_pos >> 16) == (vmv->range.last_use.abs_pos >> 16)) {
+                               /*
+                                * This variables is only used in a single basic block so
+                                * convert it into a virtual register.
+                                * FIXME: This increases register pressure in the local
+                                * allocator, leading to the well known 'branches inside
+                                * basic blocks screw up the allocator' problem.
+                                */
+#if 0
+                               cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
+                               cfg->varinfo [vmv->idx]->dreg = mono_regstate_next_int (cfg->rs);
+#endif
+                       }
+                       else {
+                               if (cfg->verbose_level > 2)
+                                       printf ("NOT REGVAR: %d\n", vmv->idx);
+                       }
+               }
+       }
+
+       /* Compute used regs */
+       used_regs = 0;
+       for (l = vars; l; l = l->next) {
+               vmv = l->data;
+               
+               if (vmv->reg >= 0)
+                       used_regs |= 1LL << vmv->reg;
        }
 
        *used_mask |= used_regs;
 
+#ifdef DEBUG_LSCAN
+       if (cfg->verbose_level > 2)
+               printf ("EXIT: final used mask: %08x\n", *used_mask);
+#endif
+
        g_list_free (regs);
        g_list_free (active);
        g_list_free (vars);
 }
+
my mono mirror. check out Moved to http://github.com/mono/mono