mono/jit/linear-scan.c

   1 /*
   2  * linear-scan.c: linbear scan register allocation
   3  *
   4  * Authors:
   5  *   Dietmar Maurer (dietmar@ximian.com)
   6  *   Miguel de Icaza (miguel@ximian.com)
   7  *
   8  * (C) 2001 Ximian, Inc.
   9  */
  10
  11 #include <config.h>
  12 #include <glib.h>
  13
  14 #include "jit.h"
  15 #include "codegen.h"
  16 #include "debug.h"
  17
  18 //#define MNAME "nest_test"
  19
  20 #ifdef MNAME
  21 #define DEGUG_LIVENESS
  22 #define DEBUG_LSCAN
  23 #endif
  24
  25 static MonoBitSet*
  26 mono_bitset_mp_new (MonoMemPool *mp,  guint32 max_size)
  27 {
  28         int size = mono_bitset_alloc_size (max_size, 0);
  29         gpointer mem;
  30
  31         mem = mono_mempool_alloc0 (mp, size);
  32         return mono_bitset_mem_new (mem, max_size, MONO_BITSET_DONT_FREE);
  33 }
  34
  35 static void
  36 mono_bitset_print (MonoBitSet *set)
  37 {
  38         int i;
  39
  40         printf ("{");
  41         for (i = 0; i < mono_bitset_size (set); i++) {
  42
  43                 if (mono_bitset_test (set, i))
  44                         printf ("%d, ", i);
  45
  46         }
  47         printf ("}");
  48 }
  49
  50 static void
  51 mono_update_live_range (MonoFlowGraph *cfg, int varnum, int block_num, int tree_pos)
  52 {
  53         MonoVarInfo *vi = &g_array_index (cfg->varinfo, MonoVarInfo, varnum);
  54         guint32 abs_pos = (block_num << 16) | tree_pos;
  55
  56         if (vi->range.first_use.abs_pos > abs_pos)
  57                 vi->range.first_use.abs_pos = abs_pos;
  58
  59         if (vi->range.last_use.abs_pos < abs_pos)
  60                 vi->range.last_use.abs_pos = abs_pos;
  61 }
  62
  63 static void
  64 mono_update_live_info (MonoFlowGraph *cfg)
  65 {
  66         int i, j;
  67
  68         for (i = 0; i < cfg->block_count; i++) {
  69                 MonoBBlock *bb = &cfg->bblocks [i];
  70
  71                 for (j = cfg->varinfo->len - 1; j > 0; j--) {
  72
  73                         if (mono_bitset_test (bb->live_in_set, j))
  74                                 mono_update_live_range (cfg, j, bb->num, 0);
  75
  76                         if (mono_bitset_test (bb->live_out_set, j))
  77                                 mono_update_live_range (cfg, j, bb->num, bb->forest->len);
  78                 }
  79         }
  80 }
  81
  82 static void
  83 mono_update_gen_set (MonoFlowGraph *cfg, MonoBBlock *bb, MBTree *tree,
  84                      int tnum, MonoBitSet *set)
  85 {
  86         if (tree->left) {
  87                 switch (tree->op) {
  88                 case MB_TERM_REMOTE_STIND_I1:
  89                 case MB_TERM_REMOTE_STIND_I2:
  90                 case MB_TERM_REMOTE_STIND_I4:
  91                 case MB_TERM_REMOTE_STIND_I8:
  92                 case MB_TERM_REMOTE_STIND_R4:
  93                 case MB_TERM_REMOTE_STIND_R8:
  94                 case MB_TERM_REMOTE_STIND_OBJ:
  95                 case MB_TERM_STIND_I1:
  96                 case MB_TERM_STIND_I2:
  97                 case MB_TERM_STIND_I4:
  98                 case MB_TERM_STIND_I8:
  99                 case MB_TERM_STIND_R4:
 100                 case MB_TERM_STIND_R8:
 101                 case MB_TERM_STIND_OBJ:
 102                         if (tree->left->op != MB_TERM_ADDR_L)
 103                                 mono_update_gen_set (cfg, bb, tree->left, tnum, set);
 104                         else
 105                                 mono_update_live_range (cfg, tree->left->data.i,
 106                                                         bb->num, tnum);
 107                         break;
 108                 default:
 109                         mono_update_gen_set (cfg, bb, tree->left, tnum, set);
 110                         break;
 111                 }
 112         }
 113
 114         if (tree->right)
 115                 mono_update_gen_set (cfg, bb, tree->right, tnum, set);
 116
 117         if (tree->op == MB_TERM_ADDR_L) {
 118                 mono_update_live_range (cfg, tree->data.i, bb->num, tnum);
 119                 mono_bitset_set (set, tree->data.i);
 120         }
 121 }
 122
 123 static void
 124 mono_analyze_liveness (MonoFlowGraph *cfg)
 125 {
 126         MonoBitSet *old_live_in_set, *old_live_out_set;
 127         gboolean changes;
 128         GList *l;
 129         int i, j , max_vars = cfg->varinfo->len;
 130
 131 #ifdef DEGUG_LIVENESS
 132         int debug = !strcmp (cfg->method->name, MNAME);
 133         if (debug)
 134                 printf ("LIVENLESS %s.%s:%s\n", cfg->method->klass->name_space,
 135                         cfg->method->klass->name, cfg->method->name);
 136 #endif
 137
 138         old_live_in_set = mono_bitset_new (max_vars, 0);
 139         old_live_out_set = mono_bitset_new (max_vars, 0);
 140
 141         for (i = 0; i < cfg->block_count; i++) {
 142                 MonoBBlock *bb = &cfg->bblocks [i];
 143
 144                 bb->gen_set = mono_bitset_mp_new (cfg->mp, max_vars);
 145                 bb->kill_set = mono_bitset_mp_new (cfg->mp, max_vars);
 146                 bb->live_in_set = mono_bitset_mp_new (cfg->mp, max_vars);
 147                 bb->live_out_set = mono_bitset_mp_new (cfg->mp, max_vars);
 148
 149                 for (j = 0; j < bb->forest->len; j++) {
 150                         MBTree *t1 = (MBTree *) g_ptr_array_index (bb->forest, j);
 151
 152                         mono_bitset_clear_all (old_live_in_set);
 153                         mono_update_gen_set (cfg, bb, t1, j, old_live_in_set);
 154                         mono_bitset_sub (old_live_in_set, bb->kill_set);
 155                         mono_bitset_union (bb->gen_set, old_live_in_set);
 156
 157                         switch (t1->op) {
 158                         case MB_TERM_REMOTE_STIND_I1:
 159                         case MB_TERM_REMOTE_STIND_I2:
 160                         case MB_TERM_REMOTE_STIND_I4:
 161                         case MB_TERM_REMOTE_STIND_I8:
 162                         case MB_TERM_REMOTE_STIND_R4:
 163                         case MB_TERM_REMOTE_STIND_R8:
 164                         case MB_TERM_REMOTE_STIND_OBJ:
 165                         case MB_TERM_STIND_I1:
 166                         case MB_TERM_STIND_I2:
 167                         case MB_TERM_STIND_I4:
 168                         case MB_TERM_STIND_I8:
 169                         case MB_TERM_STIND_R4:
 170                         case MB_TERM_STIND_R8:
 171                         case MB_TERM_STIND_OBJ:
 172                                 if (t1->left->op == MB_TERM_ADDR_L)
 173                                         mono_bitset_set (bb->kill_set, t1->left->data.i);
 174                                 break;
 175                         }
 176                 }
 177
 178 #ifdef DEGUG_LIVENESS
 179                 if (debug) {
 180                         printf ("BLOCK %d (", bb->num);
 181                         for (l = bb->succ; l; l = l->next) {
 182                                 MonoBBlock *t = (MonoBBlock *)l->data;
 183                                 printf ("%d, ", t->num);
 184                         }
 185                         printf (")\n");
 186                         printf ("GEN  %d: ", i); mono_bitset_print (bb->gen_set); printf ("\n");
 187                         printf ("KILL %d: ", i); mono_bitset_print (bb->kill_set); printf ("\n");
 188                 }
 189 #endif
 190         }
 191
 192         do {
 193                 changes = FALSE;
 194
 195                 for (i =  cfg->block_count - 1; i >= 0; i--) {
 196                         MonoBBlock *bb = &cfg->bblocks [i];
 197
 198                         mono_bitset_copyto (bb->live_in_set, old_live_in_set);
 199                         mono_bitset_copyto (bb->live_out_set, old_live_out_set);
 200
 201                         mono_bitset_copyto (bb->live_out_set, bb->live_in_set);
 202                         mono_bitset_sub (bb->live_in_set, bb->kill_set);
 203                         mono_bitset_union (bb->live_in_set, bb->gen_set);
 204
 205                         mono_bitset_clear_all (bb->live_out_set);
 206
 207                         for (l = bb->succ; l; l = l->next) {
 208                                 MonoBBlock *t = (MonoBBlock *)l->data;
 209                                 mono_bitset_union (bb->live_out_set, t->live_in_set);
 210                         }
 211
 212                         if (!(mono_bitset_equal (old_live_in_set, bb->live_in_set) &&
 213                               mono_bitset_equal (old_live_out_set, bb->live_out_set)))
 214                                 changes = TRUE;
 215                 }
 216
 217         } while (changes);
 218
 219         mono_bitset_free (old_live_in_set);
 220         mono_bitset_free (old_live_out_set);
 221
 222
 223 #ifdef DEGUG_LIVENESS
 224         if (debug) {
 225                 for (i = 0; i < cfg->block_count; i++) {
 226                         MonoBBlock *bb = &cfg->bblocks [i];
 227
 228                         printf ("LIVE IN  %d: ", i);
 229                         mono_bitset_print (bb->live_in_set);
 230                         printf ("\n");
 231                         printf ("LIVE OUT %d: ", i);
 232                         mono_bitset_print (bb->live_out_set);
 233                         printf ("\n");
 234                 }
 235         }
 236 #endif
 237 }
 238
 239 static GList *
 240 mono_varlist_insert_sorted (GList *list, MonoVarInfo *vi, gboolean sort_end)
 241 {
 242         GList *l;
 243
 244         if (!list)
 245                 return g_list_prepend (NULL, vi);
 246
 247         for (l = list; l; l = l->next) {
 248                 MonoVarInfo *v = (MonoVarInfo *)l->data;
 249
 250                 if (sort_end) {
 251                         if (vi->range.last_use.abs_pos <= v->range.last_use.abs_pos) {
 252                                 list = g_list_insert_before (list, l, vi);
 253                                 break;
 254                         }
 255                 } else {
 256                         if (vi->range.first_use.abs_pos <= v->range.first_use.abs_pos) {
 257                                 list = g_list_insert_before (list, l, vi);
 258                                 break;
 259                         }
 260                 }
 261         }
 262         if (!l)
 263                 list = g_list_append (list, vi);
 264
 265         return list;
 266 }
 267
 268 void
 269 mono_linear_scan (MonoFlowGraph *cfg, guint32 *used_mask)
 270 {
 271         GList *l, *ranges = NULL;
 272         GList *active = NULL;
 273         GList *regs = NULL;
 274         int i, max_regs;
 275
 276 #ifdef DEBUG_LSCAN
 277         MonoMethod *m = cfg->method;
 278         int debug = !strcmp (cfg->method->name, MNAME);
 279
 280         if (debug)
 281                 printf ("VARINFO for %s.%s:%s\n", m->klass->name_space, m->klass->name, m->name);
 282 #endif
 283
 284         mono_analyze_liveness (cfg);
 285         mono_update_live_info (cfg);
 286
 287         for (i = 1; i < cfg->varinfo->len; i++) {
 288                 MonoVarInfo *vi = &g_array_index (cfg->varinfo, MonoVarInfo, i);
 289
 290                 /* unused vars */
 291                 if (vi->range.first_use.abs_pos > vi->range.last_use.abs_pos)
 292                         continue;
 293
 294                 /* we can only allocate 32 bit values */
 295                 if (vi->isvolatile || (vi->type != VAL_I32 && vi->type != VAL_POINTER))
 296                         continue;
 297
 298                 ranges = mono_varlist_insert_sorted (ranges, vi, FALSE);
 299
 300         }
 301
 302 #ifdef DEBUG_LSCAN
 303         if (debug) {
 304                 for (l = ranges; l; l = l->next) {
 305                         MonoVarInfo *vi = (MonoVarInfo *)l->data;
 306
 307                         printf ("VAR %d %08x %08x\n", vi->varnum, vi->range.first_use.abs_pos,
 308                                 vi->range.last_use.abs_pos);
 309                 }
 310         }
 311 #endif
 312
 313         /* we can use 2 registers for global allocation */
 314         regs = g_list_prepend (regs, (gpointer)X86_EBX);
 315         regs = g_list_prepend (regs, (gpointer)X86_ESI);
 316
 317         max_regs = g_list_length (regs);
 318
 319         /* linear scan */
 320
 321         for (l = ranges; l; l = l->next) {
 322                 MonoVarInfo *vi = (MonoVarInfo *)l->data;
 323
 324 #ifdef DEBUG_LSCAN
 325                 if (debug)
 326                         printf ("START  %2d %08x %08x\n",  vi->varnum, vi->range.first_use.abs_pos,
 327                                 vi->range.last_use.abs_pos);
 328 #endif
 329                 /* expire old intervals in active */
 330                 while (active) {
 331                         MonoVarInfo *v = (MonoVarInfo *)active->data;
 332
 333                         if (v->range.last_use.abs_pos >= vi->range.first_use.abs_pos)
 334                                 break;
 335
 336 #ifdef DEBUG_LSCAN
 337                         if (debug)
 338                                 printf ("EXPIR  %2d %08x %08x\n",  v->varnum,
 339                                         v->range.first_use.abs_pos, v->range.last_use.abs_pos);
 340 #endif
 341                         active = g_list_remove_link (active, active);
 342                         regs = g_list_prepend (regs, (gpointer)v->reg);
 343                 }
 344
 345                 if (active && g_list_length (active) == max_regs) {
 346                         /* Spill */
 347
 348                         GList *a = g_list_nth (active, max_regs - 1);
 349                         MonoVarInfo *v = (MonoVarInfo *)a->data;
 350
 351                         if (v->range.last_use.abs_pos > vi->range.last_use.abs_pos) {
 352                                 vi->reg = v->reg;
 353                                 v->reg = -1;
 354                                 active = g_list_remove_link (active, a);
 355                                 active = mono_varlist_insert_sorted (active, vi, TRUE);
 356 #ifdef DEBUG_LSCAN
 357                                 if (debug)
 358                                         printf ("SPILL0 %2d %08x %08x\n",  v->varnum,
 359                                                 v->range.first_use.abs_pos, v->range.last_use.abs_pos);
 360 #endif
 361                         } else {
 362 #ifdef DEBUG_LSCAN
 363                                 if (debug)
 364                                         printf ("SPILL1 %2d %08x %08x\n",  vi->varnum,
 365                                                 vi->range.first_use.abs_pos, vi->range.last_use.abs_pos);
 366 #endif
 367                                 vi->reg = -1;
 368                         }
 369                 } else {
 370                         /* assign register */
 371
 372                         g_assert (regs);
 373
 374                         vi->reg = (int)regs->data;
 375
 376                         *used_mask |= 1 << vi->reg;
 377
 378                         regs = g_list_remove_link (regs, regs);
 379
 380 #ifdef DEBUG_LSCAN
 381                         if (debug)
 382                                 printf ("ADD    %2d %08x %08x\n",  vi->varnum,
 383                                         vi->range.first_use.abs_pos, vi->range.last_use.abs_pos);
 384 #endif
 385                         active = mono_varlist_insert_sorted (active, vi, TRUE);
 386                 }
 387
 388
 389 #ifdef DEBUG_LSCAN
 390                 if (debug) {
 391                         GList *a;
 392                         for (a = active; a; a = a->next) {
 393                                 MonoVarInfo *v = (MonoVarInfo *)a->data;
 394
 395                                 printf ("ACT    %2d %08x %08x %d\n", v->varnum,
 396                                         v->range.first_use.abs_pos,  v->range.last_use.abs_pos, v->reg);
 397                         }
 398                         printf ("NEXT\n");
 399                 }
 400 #endif
 401         }
 402
 403         g_list_free (regs);
 404         g_list_free (active);
 405         g_list_free (ranges);
 406
 407 }
 408