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