mono/mini/linear-scan.c

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