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