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