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 #include <mono/utils/mono-compiler.h>
  13
  14 #ifndef DISABLE_JIT
  15
  16 static void mono_linear_scan2 (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask);
  17
  18 GList *
  19 mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, int sort_type)
  20 {
  21         GList *l;
  22
  23         if (!list)
  24                 return g_list_prepend (NULL, mv);
  25
  26         for (l = list; l; l = l->next) {
  27                 MonoMethodVar *v1 = (MonoMethodVar *)l->data;
  28
  29                 if (sort_type == 2) {
  30                         if (mv->spill_costs >= v1->spill_costs) {
  31                                 list = g_list_insert_before (list, l, mv);
  32                                 break;
  33                         }
  34                 } else if (sort_type == 1) {
  35                         if (mv->range.last_use.abs_pos <= v1->range.last_use.abs_pos) {
  36                                 list = g_list_insert_before (list, l, mv);
  37                                 break;
  38                         }
  39                 } else {
  40                         if (mv->range.first_use.abs_pos <= v1->range.first_use.abs_pos) {
  41                                 list = g_list_insert_before (list, l, mv);
  42                                 break;
  43                         }
  44                 }
  45         }
  46         if (!l)
  47                 list = g_list_append (list, mv);
  48
  49         return list;
  50 }
  51
  52 static gint
  53 compare_by_first_use_func (gconstpointer a, gconstpointer b)
  54 {
  55         MonoMethodVar *v1 = (MonoMethodVar*)a;
  56         MonoMethodVar *v2 = (MonoMethodVar*)b;
  57
  58         return v1->range.first_use.abs_pos - v2->range.first_use.abs_pos;
  59 }
  60
  61 GList *
  62 mono_varlist_sort (MonoCompile *cfg, GList *list, int sort_type)
  63 {
  64         if (sort_type == 0)
  65                 return g_list_sort (list, compare_by_first_use_func);
  66         else
  67                 g_assert_not_reached ();
  68
  69         return NULL;
  70 }
  71
  72 // #define DEBUG_LSCAN
  73
  74 void
  75 mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
  76 {
  77         GList *l, *a, *active = NULL;
  78         MonoMethodVar *vmv, *amv;
  79         int max_regs, n_regvars;
  80         int gains [sizeof (regmask_t) * 8];
  81         regmask_t used_regs = 0;
  82         gboolean cost_driven;
  83
  84         if (!cfg->disable_reuse_registers && vars && (((MonoMethodVar*)vars->data)->interval != NULL)) {
  85                 mono_linear_scan2 (cfg, vars, regs, used_mask);
  86                 g_list_free (regs);
  87                 g_list_free (vars);
  88                 return;
  89         }
  90
  91         cost_driven = TRUE;
  92
  93 #ifdef DEBUG_LSCAN
  94         printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
  95 #endif
  96
  97 #ifdef DEBUG_LSCAN
  98         for (l = vars; l; l = l->next) {
  99                 vmv = l->data;
 100                 printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos,
 101                         vmv->range.last_use.abs_pos, vmv->spill_costs);
 102         }
 103 #endif
 104         max_regs = g_list_length (regs);
 105
 106         for (l = regs; l; l = l->next) {
 107                 int regnum = GPOINTER_TO_INT (l->data);
 108                 g_assert (regnum < G_N_ELEMENTS (gains));
 109                 gains [regnum] = 0;
 110         }
 111
 112         /* linear scan */
 113         for (l = vars; l; l = l->next) {
 114                 vmv = (MonoMethodVar *)l->data;
 115
 116 #ifdef DEBUG_LSCAN
 117                 printf ("START  %2d %08x %08x\n",  vmv->idx, vmv->range.first_use.abs_pos,
 118                         vmv->range.last_use.abs_pos);
 119 #endif
 120                 /* expire old intervals in active */
 121                 if (!cfg->disable_reuse_registers) {
 122                         while (active) {
 123                                 amv = (MonoMethodVar *)active->data;
 124
 125                                 if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
 126                                         break;
 127
 128 #ifdef DEBUG_LSCAN
 129                                 printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 130                                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 131 #endif
 132                                 active = g_list_delete_link (active, active);
 133                                 regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
 134                                 gains [amv->reg] += amv->spill_costs;
 135                         }
 136                 }
 137
 138                 if (active && g_list_length (active) == max_regs) {
 139                         /* Spill */
 140
 141                         a = g_list_nth (active, max_regs - 1);
 142                         amv = (MonoMethodVar *)a->data;
 143
 144                         if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
 145                             (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
 146                                 vmv->reg = amv->reg;
 147                                 amv->reg = -1;
 148                                 active = g_list_delete_link (active, a);
 149
 150                                 if (cost_driven)
 151                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
 152                                 else
 153                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
 154
 155 #ifdef DEBUG_LSCAN
 156                                 printf ("SPILL0 %2d %08x %08x C%d\n",  amv->idx,
 157                                         amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
 158                                         amv->spill_costs);
 159 #endif
 160                         } else {
 161 #ifdef DEBUG_LSCAN
 162                                 printf ("SPILL1 %2d %08x %08x C%d\n",  vmv->idx,
 163                                         vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 164                                         vmv->spill_costs);
 165 #endif
 166                                 vmv->reg = -1;
 167                         }
 168                 } else {
 169                         /* assign register */
 170
 171                         g_assert (regs);
 172
 173                         vmv->reg = GPOINTER_TO_INT (regs->data);
 174
 175                         used_regs |= 1LL << vmv->reg;
 176
 177                         regs = g_list_delete_link (regs, regs);
 178
 179 #ifdef DEBUG_LSCAN
 180                         printf ("ADD    %2d %08x %08x C%d R%d\n",  vmv->idx,
 181                                 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 182                                 vmv->spill_costs, vmv->reg);
 183 #endif
 184                         active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
 185                 }
 186
 187
 188 #ifdef DEBUG_LSCAN
 189                 for (a = active; a; a = a->next) {
 190                         amv = (MonoMethodVar *)a->data;
 191                         printf ("ACT    %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 192                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 193                 }
 194                 printf ("NEXT\n");
 195 #endif
 196         }
 197
 198         for (a = active; a; a = a->next) {
 199                 amv = (MonoMethodVar *)a->data;
 200                 gains [amv->reg] += amv->spill_costs;
 201         }
 202
 203         n_regvars = 0;
 204         for (l = vars; l; l = l->next) {
 205                 vmv = (MonoMethodVar *)l->data;
 206
 207                 if (vmv->reg >= 0)  {
 208                         if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
 209                                 if (cfg->verbose_level > 2) {
 210                                         printf ("ALLOCATED R%d(%d) TO HREG %d COST %d\n", cfg->varinfo [vmv->idx]->dreg, vmv->idx, vmv->reg, vmv->spill_costs);
 211                                 }
 212                                 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 213                                 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
 214                                 n_regvars ++;
 215                         } else {
 216                                 if (cfg->verbose_level > 2)
 217                                         printf ("COSTLY: R%d C%d C%d %s\n", vmv->idx, vmv->spill_costs, mono_arch_regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
 218                                 vmv->reg = -1;
 219                         }
 220                 }
 221
 222                 if (vmv->reg == -1) {
 223                         if (cfg->verbose_level > 2)
 224                                 printf ("NOT REGVAR: %d\n", vmv->idx);
 225                 }
 226         }
 227
 228         cfg->stat_n_regvars = n_regvars;
 229
 230         /* Compute used regs */
 231         used_regs = 0;
 232         for (l = vars; l; l = l->next) {
 233                 vmv = (MonoMethodVar *)l->data;
 234
 235                 if (vmv->reg >= 0)
 236                         used_regs |= 1LL << vmv->reg;
 237         }
 238
 239         *used_mask |= used_regs;
 240
 241 #ifdef DEBUG_LSCAN
 242         if (cfg->verbose_level > 2)
 243                 printf ("EXIT: final used mask: %08x\n", *used_mask);
 244 #endif
 245
 246         g_list_free (regs);
 247         g_list_free (active);
 248         g_list_free (vars);
 249 }
 250
 251 static gint
 252 compare_by_interval_start_pos_func (gconstpointer a, gconstpointer b)
 253 {
 254         MonoMethodVar *v1 = (MonoMethodVar*)a;
 255         MonoMethodVar *v2 = (MonoMethodVar*)b;
 256
 257         if (v1 == v2)
 258                 return 0;
 259         else if (v1->interval->range && v2->interval->range)
 260                 return v1->interval->range->from - v2->interval->range->from;
 261         else if (v1->interval->range)
 262                 return -1;
 263         else
 264                 return 1;
 265 }
 266
 267 #if 0
 268 #define LSCAN_DEBUG(a) do { a; } while (0)
 269 #else
 270 #define LSCAN_DEBUG(a)
 271 #endif
 272
 273 /* FIXME: This is x86 only */
 274 static inline guint32
 275 regalloc_cost (MonoCompile *cfg, MonoMethodVar *vmv)
 276 {
 277         MonoInst *ins = cfg->varinfo [vmv->idx];
 278
 279         /* Load if it is an argument */
 280         return (ins->opcode == OP_ARG) ? 1 : 0;
 281 }
 282
 283 void
 284 mono_linear_scan2 (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
 285 {
 286         GList *unhandled, *active, *inactive, *l;
 287         MonoMethodVar *vmv;
 288         gint32 free_pos [sizeof (regmask_t) * 8];
 289         gint32 gains [sizeof (regmask_t) * 8];
 290         regmask_t used_regs = 0;
 291         int n_regs, n_regvars, i;
 292
 293         for (l = vars; l; l = l->next) {
 294                 vmv = (MonoMethodVar *)l->data;
 295                 LSCAN_DEBUG (printf ("VAR R%d %08x %08x C%d\n", cfg->varinfo [vmv->idx]->dreg, vmv->range.first_use.abs_pos,
 296                                                          vmv->range.last_use.abs_pos, vmv->spill_costs));
 297         }
 298
 299         LSCAN_DEBUG (printf ("Linear Scan 2 for %s:\n", mono_method_full_name (cfg->method, TRUE)));
 300
 301         n_regs = g_list_length (regs);
 302         memset (gains, 0, n_regs * sizeof (gint32));
 303         unhandled = g_list_sort (g_list_copy (vars), compare_by_interval_start_pos_func);
 304         active = NULL;
 305         inactive = NULL;
 306
 307         while (unhandled) {
 308                 MonoMethodVar *current = (MonoMethodVar *)unhandled->data;
 309                 int pos, reg, max_free_pos;
 310                 gboolean changed;
 311
 312                 unhandled = g_list_delete_link (unhandled, unhandled);
 313
 314                 LSCAN_DEBUG (printf ("Processing R%d: ", cfg->varinfo [current->idx]->dreg));
 315                 LSCAN_DEBUG (mono_linterval_print (current->interval));
 316                 LSCAN_DEBUG (printf ("\n"));
 317
 318                 if (!current->interval->range)
 319                         continue;
 320
 321                 pos = current->interval->range->from;
 322
 323                 /* Check for intervals in active which expired or inactive */
 324                 changed = TRUE;
 325                 /* FIXME: Optimize this */
 326                 while (changed) {
 327                         changed = FALSE;
 328                         for (l = active; l != NULL; l = l->next) {
 329                                 MonoMethodVar *v = (MonoMethodVar*)l->data;
 330
 331                                 if (v->interval->last_range->to < pos) {
 332                                         active = g_list_delete_link (active, l);
 333                                         LSCAN_DEBUG (printf ("Interval R%d has expired\n", cfg->varinfo [v->idx]->dreg));
 334                                         changed = TRUE;
 335                                         break;
 336                                 }
 337                                 else if (!mono_linterval_covers (v->interval, pos)) {
 338                                         inactive = g_list_append (inactive, v);
 339                                         active = g_list_delete_link (active, l);
 340                                         LSCAN_DEBUG (printf ("Interval R%d became inactive\n", cfg->varinfo [v->idx]->dreg));
 341                                         changed = TRUE;
 342                                         break;
 343                                 }
 344                         }
 345                 }
 346
 347                 /* Check for intervals in inactive which expired or active */
 348                 changed = TRUE;
 349                 /* FIXME: Optimize this */
 350                 while (changed) {
 351                         changed = FALSE;
 352                         for (l = inactive; l != NULL; l = l->next) {
 353                                 MonoMethodVar *v = (MonoMethodVar*)l->data;
 354
 355                                 if (v->interval->last_range->to < pos) {
 356                                         inactive = g_list_delete_link (inactive, l);
 357                                         LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", cfg->varinfo [v->idx]->dreg));
 358                                         changed = TRUE;
 359                                         break;
 360                                 }
 361                                 else if (mono_linterval_covers (v->interval, pos)) {
 362                                         active = g_list_append (active, v);
 363                                         inactive = g_list_delete_link (inactive, l);
 364                                         LSCAN_DEBUG (printf ("\tInterval R%d became active\n", cfg->varinfo [v->idx]->dreg));
 365                                         changed = TRUE;
 366                                         break;
 367                                 }
 368                         }
 369                 }
 370
 371                 /* Find a register for the current interval */
 372                 for (i = 0; i < n_regs; ++i)
 373                         free_pos [i] = ((gint32)0x7fffffff);
 374
 375                 for (l = active; l != NULL; l = l->next) {
 376                         MonoMethodVar *v = (MonoMethodVar*)l->data;
 377
 378                         if (v->reg >= 0) {
 379                                 free_pos [v->reg] = 0;
 380                                 LSCAN_DEBUG (printf ("\threg %d is busy (cost %d)\n", v->reg, v->spill_costs));
 381                         }
 382                 }
 383
 384                 for (l = inactive; l != NULL; l = l->next) {
 385                         MonoMethodVar *v = (MonoMethodVar*)l->data;
 386                         gint32 intersect_pos;
 387
 388                         if (v->reg >= 0) {
 389                                 intersect_pos = mono_linterval_get_intersect_pos (current->interval, v->interval);
 390                                 if (intersect_pos != -1) {
 391                                         free_pos [v->reg] = intersect_pos;
 392                                         LSCAN_DEBUG (printf ("\threg %d becomes free at %d\n", v->reg, intersect_pos));
 393                                 }
 394                         }
 395                 }
 396
 397                 max_free_pos = -1;
 398                 reg = -1;
 399                 for (i = 0; i < n_regs; ++i)
 400                         if (free_pos [i] > max_free_pos) {
 401                                 reg = i;
 402                                 max_free_pos = free_pos [i];
 403                         }
 404
 405                 g_assert (reg != -1);
 406
 407                 if (free_pos [reg] >= current->interval->last_range->to) {
 408                         /* Register available for whole interval */
 409                         current->reg = reg;
 410                         LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg, cfg->varinfo [current->idx]->dreg));
 411
 412                         active = g_list_append (active, current);
 413                         gains [current->reg] += current->spill_costs;
 414                 }
 415                 else {
 416                         /*
 417                          * free_pos [reg] > 0 means there is a register available for parts
 418                          * of the interval, so splitting it is possible. This is not yet
 419                          * supported, so we spill in this case too.
 420                          */
 421
 422                         /* Spill an interval */
 423
 424                         /* FIXME: Optimize the selection of the interval */
 425
 426                         if (active) {
 427                                 GList *min_spill_pos;
 428 #if 0
 429                                 /*
 430                                  * This favors registers with big spill costs, thus larger liveness ranges,
 431                                  * thus actually leading to worse code size.
 432                                  */
 433                                 guint32 min_spill_value = G_MAXINT32;
 434
 435                                 for (l = active; l != NULL; l = l->next) {
 436                                         vmv = (MonoMethodVar*)l->data;
 437
 438                                         if (vmv->spill_costs < min_spill_value) {
 439                                                 min_spill_pos = l;
 440                                                 min_spill_value = vmv->spill_costs;
 441                                         }
 442                                 }
 443 #else
 444                                 /* Spill either the first active or the current interval */
 445                                 min_spill_pos = active;
 446 #endif
 447                                 vmv = (MonoMethodVar*)min_spill_pos->data;
 448                                 if (vmv->spill_costs < current->spill_costs) {
 449                                 //                              if (vmv->interval->last_range->to < current->interval->last_range->to) {
 450                                         gains [vmv->reg] -= vmv->spill_costs;
 451                                         vmv->reg = -1;
 452                                         LSCAN_DEBUG (printf ("\tSpilled R%d\n", cfg->varinfo [vmv->idx]->dreg));
 453                                         active = g_list_delete_link (active, min_spill_pos);
 454                                 }
 455                                 else
 456                                         LSCAN_DEBUG (printf ("\tSpilled current (cost %d)\n", current->spill_costs));
 457                         }
 458                         else
 459                                 LSCAN_DEBUG (printf ("\tSpilled current\n"));
 460                 }
 461         }
 462
 463         /* Decrease the gains by the cost of saving+restoring the register */
 464         for (i = 0; i < n_regs; ++i) {
 465                 if (gains [i]) {
 466                         /* FIXME: This is x86 only */
 467                         gains [i] -= cfg->method->save_lmf ? 1 : 2;
 468                         if (gains [i] < 0)
 469                                 gains [i] = 0;
 470                 }
 471         }
 472
 473         /* Do the actual register assignment */
 474         n_regvars = 0;
 475         for (l = vars; l; l = l->next) {
 476                 vmv = (MonoMethodVar *)l->data;
 477
 478                 if (vmv->reg >= 0) {
 479                         int reg_index = vmv->reg;
 480
 481                         /* During allocation, vmv->reg is an index into the regs list */
 482                         vmv->reg = GPOINTER_TO_INT (g_list_nth_data (regs, vmv->reg));
 483
 484                         if ((gains [reg_index] > regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
 485                                 if (cfg->verbose_level > 2)
 486                                         printf ("REGVAR R%d G%d C%d %s\n", cfg->varinfo [vmv->idx]->dreg, gains [reg_index], regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
 487                                 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 488                                 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
 489                                 n_regvars ++;
 490                         }
 491                         else {
 492                                 if (cfg->verbose_level > 2)
 493                                         printf ("COSTLY: %s R%d G%d C%d %s\n", mono_method_full_name (cfg->method, TRUE), cfg->varinfo [vmv->idx]->dreg, gains [reg_index], regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
 494                                 vmv->reg = -1;
 495                         }
 496                 }
 497         }
 498
 499         cfg->stat_n_regvars = n_regvars;
 500
 501         /* Compute used regs */
 502         used_regs = 0;
 503         for (l = vars; l; l = l->next) {
 504                 vmv = (MonoMethodVar *)l->data;
 505
 506                 if (vmv->reg >= 0)
 507                         used_regs |= 1LL << vmv->reg;
 508         }
 509
 510         *used_mask |= used_regs;
 511
 512         g_list_free (active);
 513         g_list_free (inactive);
 514 }
 515
 516 #else /* !DISABLE_JIT */
 517
 518 MONO_EMPTY_SOURCE_FILE (linear_scan);
 519
 520 #endif /* !DISABLE_JIT */