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                 while (active) {
 109                         amv = (MonoMethodVar *)active->data;
 110
 111                         if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
 112                                 break;
 113
 114 #ifdef DEBUG_LSCAN
 115                         printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 116                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 117 #endif
 118                         active = g_list_delete_link (active, active);
 119                         regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
 120                         gains [amv->reg] += amv->spill_costs;
 121                 }
 122
 123                 if (active && g_list_length (active) == max_regs) {
 124                         /* Spill */
 125
 126                         a = g_list_nth (active, max_regs - 1);
 127                         amv = (MonoMethodVar *)a->data;
 128
 129                         if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
 130                             (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
 131                                 vmv->reg = amv->reg;
 132                                 amv->reg = -1;
 133                                 active = g_list_delete_link (active, a);
 134
 135                                 if (cost_driven)
 136                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
 137                                 else
 138                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
 139
 140 #ifdef DEBUG_LSCAN
 141                                 printf ("SPILL0 %2d %08x %08x C%d\n",  amv->idx,
 142                                         amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
 143                                         amv->spill_costs);
 144 #endif
 145                         } else {
 146 #ifdef DEBUG_LSCAN
 147                                 printf ("SPILL1 %2d %08x %08x C%d\n",  vmv->idx,
 148                                         vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 149                                         vmv->spill_costs);
 150 #endif
 151                                 vmv->reg = -1;
 152                         }
 153                 } else {
 154                         /* assign register */
 155
 156                         g_assert (regs);
 157
 158                         vmv->reg = GPOINTER_TO_INT (regs->data);
 159
 160                         used_regs |= 1LL << vmv->reg;
 161
 162                         regs = g_list_delete_link (regs, regs);
 163
 164 #ifdef DEBUG_LSCAN
 165                         printf ("ADD    %2d %08x %08x C%d R%d\n",  vmv->idx,
 166                                 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 167                                 vmv->spill_costs, vmv->reg);
 168 #endif
 169                         active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
 170                 }
 171
 172
 173 #ifdef DEBUG_LSCAN
 174                 for (a = active; a; a = a->next) {
 175                         amv = (MonoMethodVar *)a->data;
 176                         printf ("ACT    %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 177                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 178                 }
 179                 printf ("NEXT\n");
 180 #endif
 181         }
 182
 183         for (a = active; a; a = a->next) {
 184                 amv = (MonoMethodVar *)a->data;
 185                 gains [amv->reg] += amv->spill_costs;
 186         }
 187
 188         for (l = vars; l; l = l->next) {
 189                 vmv = l->data;
 190
 191                 if (vmv->reg >= 0)  {
 192                         if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
 193                                 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 194                                 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
 195                                 if (cfg->verbose_level > 2)
 196                                         printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
 197                         } else {
 198                                 if (cfg->verbose_level > 2)
 199                                         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));
 200                                 vmv->reg = -1;
 201                         }
 202                 }
 203
 204                 if (vmv->reg == -1) {
 205                         if ((vmv->range.first_use.abs_pos >> 16) == (vmv->range.last_use.abs_pos >> 16)) {
 206                                 /*
 207                                  * This variables is only used in a single basic block so
 208                                  * convert it into a virtual register.
 209                                  * FIXME: This increases register pressure in the local
 210                                  * allocator, leading to the well known 'branches inside
 211                                  * basic blocks screw up the allocator' problem.
 212                                  */
 213 #if 0
 214                                 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 215                                 cfg->varinfo [vmv->idx]->dreg = mono_regstate_next_int (cfg->rs);
 216 #endif
 217                         }
 218                         else {
 219                                 if (cfg->verbose_level > 2)
 220                                         printf ("NOT REGVAR: %d\n", vmv->idx);
 221                         }
 222                 }
 223         }
 224
 225         /* Compute used regs */
 226         used_regs = 0;
 227         for (l = vars; l; l = l->next) {
 228                 vmv = l->data;
 229
 230                 if (vmv->reg >= 0)
 231                         used_regs |= 1LL << vmv->reg;
 232         }
 233
 234         *used_mask |= used_regs;
 235
 236 #ifdef DEBUG_LSCAN
 237         if (cfg->verbose_level > 2)
 238                 printf ("EXIT: final used mask: %08x\n", *used_mask);
 239 #endif
 240
 241         g_list_free (regs);
 242         g_list_free (active);
 243         g_list_free (vars);
 244 }
 245