mono/mini/linear-scan.c

   1 /*
   2  * liveness.c: liveness analysis
   3  *
   4  * Author:
   5  *   Dietmar Maurer (dietmar@ximian.com)
   6  *
   7  * (C) 2002 Ximian, Inc.
   8  */
   9
  10 #include "mini.h"
  11 #include <mono/metadata/debug-helpers.h>
  12
  13 GList *
  14 mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, int sort_type)
  15 {
  16         GList *l;
  17
  18         if (!list)
  19                 return g_list_prepend (NULL, mv);
  20
  21         for (l = list; l; l = l->next) {
  22                 MonoMethodVar *v1 = l->data;
  23
  24                 if (sort_type == 2) {
  25                         if (mv->spill_costs >= v1->spill_costs) {
  26                                 list = g_list_insert_before (list, l, mv);
  27                                 break;
  28                         }
  29                 } else if (sort_type == 1) {
  30                         if (mv->range.last_use.abs_pos <= v1->range.last_use.abs_pos) {
  31                                 list = g_list_insert_before (list, l, mv);
  32                                 break;
  33                         }
  34                 } else {
  35                         if (mv->range.first_use.abs_pos <= v1->range.first_use.abs_pos) {
  36                                 list = g_list_insert_before (list, l, mv);
  37                                 break;
  38                         }
  39                 }
  40         }
  41         if (!l)
  42                 list = g_list_append (list, mv);
  43
  44         return list;
  45 }
  46
  47 static gint
  48 compare_by_first_use_func (gconstpointer a, gconstpointer b)
  49 {
  50         MonoMethodVar *v1 = (MonoMethodVar*)a;
  51         MonoMethodVar *v2 = (MonoMethodVar*)b;
  52
  53         return v1->range.first_use.abs_pos - v2->range.first_use.abs_pos;
  54 }
  55
  56 GList *
  57 mono_varlist_sort (MonoCompile *cfg, GList *list, int sort_type)
  58 {
  59         if (sort_type == 0)
  60                 return g_list_sort (list, compare_by_first_use_func);
  61         else
  62                 g_assert_not_reached ();
  63
  64         return NULL;
  65 }
  66
  67 // #define DEBUG_LSCAN
  68
  69 void
  70 mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
  71 {
  72         GList *l, *a, *active = NULL;
  73         MonoMethodVar *vmv, *amv;
  74         int max_regs, gains [sizeof (regmask_t) * 8];
  75         regmask_t used_regs = 0;
  76         gboolean cost_driven;
  77
  78         cost_driven = TRUE;
  79
  80 #ifdef DEBUG_LSCAN
  81         printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
  82 #endif
  83
  84 #ifdef DEBUG_LSCAN
  85         for (l = vars; l; l = l->next) {
  86                 vmv = l->data;
  87                 printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos,
  88                         vmv->range.last_use.abs_pos, vmv->spill_costs);
  89         }
  90 #endif
  91         max_regs = g_list_length (regs);
  92
  93         for (l = regs; l; l = l->next) {
  94                 int regnum = GPOINTER_TO_INT (l->data);
  95                 g_assert (regnum < G_N_ELEMENTS (gains));
  96                 gains [regnum] = 0;
  97         }
  98
  99         /* linear scan */
 100         for (l = vars; l; l = l->next) {
 101                 vmv = l->data;
 102
 103 #ifdef DEBUG_LSCAN
 104                 printf ("START  %2d %08x %08x\n",  vmv->idx, vmv->range.first_use.abs_pos,
 105                         vmv->range.last_use.abs_pos);
 106 #endif
 107                 /* expire old intervals in active */
 108                 if (!cfg->disable_reuse_registers) {
 109                         while (active) {
 110                                 amv = (MonoMethodVar *)active->data;
 111
 112                                 if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
 113                                         break;
 114
 115 #ifdef DEBUG_LSCAN
 116                                 printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 117                                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 118 #endif
 119                                 active = g_list_delete_link (active, active);
 120                                 regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
 121                                 gains [amv->reg] += amv->spill_costs;
 122                         }
 123                 }
 124
 125                 if (active && g_list_length (active) == max_regs) {
 126                         /* Spill */
 127
 128                         a = g_list_nth (active, max_regs - 1);
 129                         amv = (MonoMethodVar *)a->data;
 130
 131                         if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
 132                             (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
 133                                 vmv->reg = amv->reg;
 134                                 amv->reg = -1;
 135                                 active = g_list_delete_link (active, a);
 136
 137                                 if (cost_driven)
 138                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
 139                                 else
 140                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
 141
 142 #ifdef DEBUG_LSCAN
 143                                 printf ("SPILL0 %2d %08x %08x C%d\n",  amv->idx,
 144                                         amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
 145                                         amv->spill_costs);
 146 #endif
 147                         } else {
 148 #ifdef DEBUG_LSCAN
 149                                 printf ("SPILL1 %2d %08x %08x C%d\n",  vmv->idx,
 150                                         vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 151                                         vmv->spill_costs);
 152 #endif
 153                                 vmv->reg = -1;
 154                         }
 155                 } else {
 156                         /* assign register */
 157
 158                         g_assert (regs);
 159
 160                         vmv->reg = GPOINTER_TO_INT (regs->data);
 161
 162                         used_regs |= 1LL << vmv->reg;
 163
 164                         regs = g_list_delete_link (regs, regs);
 165
 166 #ifdef DEBUG_LSCAN
 167                         printf ("ADD    %2d %08x %08x C%d R%d\n",  vmv->idx,
 168                                 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 169                                 vmv->spill_costs, vmv->reg);
 170 #endif
 171                         active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
 172                 }
 173
 174
 175 #ifdef DEBUG_LSCAN
 176                 for (a = active; a; a = a->next) {
 177                         amv = (MonoMethodVar *)a->data;
 178                         printf ("ACT    %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 179                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 180                 }
 181                 printf ("NEXT\n");
 182 #endif
 183         }
 184
 185         for (a = active; a; a = a->next) {
 186                 amv = (MonoMethodVar *)a->data;
 187                 gains [amv->reg] += amv->spill_costs;
 188         }
 189
 190         for (l = vars; l; l = l->next) {
 191                 vmv = l->data;
 192
 193                 if (vmv->reg >= 0)  {
 194                         if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
 195                                 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 196                                 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
 197                                 if (cfg->verbose_level > 2)
 198                                         printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
 199                         } else {
 200                                 if (cfg->verbose_level > 2)
 201                                         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));
 202                                 vmv->reg = -1;
 203                         }
 204                 }
 205
 206                 if (vmv->reg == -1) {
 207                         if ((vmv->range.first_use.abs_pos >> 16) == (vmv->range.last_use.abs_pos >> 16)) {
 208                                 /*
 209                                  * This variables is only used in a single basic block so
 210                                  * convert it into a virtual register.
 211                                  * FIXME: This increases register pressure in the local
 212                                  * allocator, leading to the well known 'branches inside
 213                                  * basic blocks screw up the allocator' problem.
 214                                  */
 215 #if 0
 216                                 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 217                                 cfg->varinfo [vmv->idx]->dreg = mono_regstate_next_int (cfg->rs);
 218 #endif
 219                         }
 220                         else {
 221                                 if (cfg->verbose_level > 2)
 222                                         printf ("NOT REGVAR: %d\n", vmv->idx);
 223                         }
 224                 }
 225         }
 226
 227         /* Compute used regs */
 228         used_regs = 0;
 229         for (l = vars; l; l = l->next) {
 230                 vmv = l->data;
 231
 232                 if (vmv->reg >= 0)
 233                         used_regs |= 1LL << vmv->reg;
 234         }
 235
 236         *used_mask |= used_regs;
 237
 238 #ifdef DEBUG_LSCAN
 239         if (cfg->verbose_level > 2)
 240                 printf ("EXIT: final used mask: %08x\n", *used_mask);
 241 #endif
 242
 243         g_list_free (regs);
 244         g_list_free (active);
 245         g_list_free (vars);
 246 }
 247