mono/mini/regalloc2.c

   1 /*
   2  * regalloc2.c: Global Register Allocator
   3  *
   4  * Author:
   5  *   Zoltan Varga (vargaz@gmail.com)
   6  *
   7  * (C) 2007 Novell, Inc.
   8  */
   9
  10 #include "mini.h"
  11 #include <mono/metadata/debug-helpers.h>
  12 #include <mono/metadata/mempool-internals.h>
  13
  14 /* Disable for now to save space */
  15 #undef MONO_ARCH_ENABLE_GLOBAL_RA
  16
  17 #ifdef MONO_ARCH_ENABLE_GLOBAL_RA
  18
  19 /*
  20  * Documentation
  21  *
  22  *   This allocator is based on the paper
  23  * "Linear Scan Register Allocation for the Java HotSpot Client Compiler"
  24  * by Christian Wimmer.
  25  *
  26  * It differs from the current allocator in the following respects:
  27  * - all variables (vregs) are allocated a register, there is no separate local/global
  28  *   register allocator.
  29  * - there are no variables allocated strictly to the stack. Even those variables
  30  *   allocated to the stack are loaded into a register before they are accessed.
  31  */
  32
  33 /*
  34  * Current status:
  35  *
  36  * - Only works on amd64.
  37  * - Tests in mono/mini and mono/tests work, "Hello, World!" works.
  38  * - The quality of generated code is not bad, but needs more optimizations.
  39  * - Focus was on correctness and easy debuggability so performance is bad, especially on
  40  *   large methods (like Main in transparentproxy.exe). Since each interval can be
  41  *   split at each use position, run time is linear in the number of variable accesses,
  42  *   not the number of variables.
  43  * - Have to think about splitting the available registers between caller saved and callee
  44  *   saved, and take this into account during allocation (callee saved - good for
  45  *   variables which are accessed a lot, and/or are live across calls, caller saved -
  46  *   good for scratch registers used only in a bblock and not live across calls).
  47  * - FIXME: Fix mono_arch_get_ireg_clobbered_by_call () to only return caller saved
  48  *   registers.
  49  */
  50
  51 /*
  52  * TYPES
  53  */
  54 typedef struct MonoRegallocInterval {
  55         /*
  56          * 0..MONO_MAX_IREGS - iregs
  57          * MONO_MAX_IREGS + 1...MONO_MAX_IREGS+MONO_MAX_FREGS - fregs
  58          * MONO_MAX_IREGS+MONO_MAX_FREGS... cfg->next_vreg - vregs
  59      * cfg->next_vreg... - split intervals
  60          */
  61         int vreg;
  62         /*
  63          * Hard register assigned to this interval, -1 if no register is assigned or the
  64          * interval is spilled.
  65          */
  66         int hreg;
  67
  68         /*
  69          * The actual interval data
  70          */
  71         MonoLiveInterval *interval;
  72
  73         /*
  74          * Split children of this interval. NULL if the interval is not split.
  75          */
  76         struct MonoRegallocInterval *child1, *child2;
  77
  78         /*
  79          * List of use positions, each position is identified by (bb->dfn << 16) + ins_pos
  80          * The list is sorted by increasing position.
  81          */
  82         GSList *use_pos;
  83
  84         /*
  85          * The offset relative to the frame pointer where this interval is spilled.
  86          */
  87         int offset;
  88
  89         /*
  90          * If we are a split child of an interval, this points to our parent
  91          */
  92         struct MonoRegallocInterval *parent;
  93
  94         /*
  95          * Whenever vreg is an fp vreg
  96          */
  97         guint fp : 1;
  98
  99         /*
 100          * Whenever the variable is volatile
 101          */
 102         guint is_volatile : 1;
 103
 104         /*
 105          * The exact type of the variable
 106          */
 107         MonoType *type;
 108
 109         /*
 110          * The register where this interval should be allocated
 111          */
 112         int preferred_reg;
 113 } MonoRegallocInterval;
 114
 115 typedef struct MonoRegallocContext {
 116         MonoCompile *cfg;
 117         MonoRegallocInterval *varinfo;
 118         int num_intervals;
 119         /*
 120          * Maps ins pos -> GSList of intervals split at that pos.
 121          */
 122         GHashTable *split_positions;
 123         /*
 124          * Used to avoid lookups in split_positions for every position.
 125          */
 126         GHashTable *split_position_set;
 127         /*
 128          * Contains MonoInst's representing spill loads/stores
 129          */
 130         GHashTable *spill_ins;
 131 } MonoRegallocContext;
 132
 133 /*
 134  * MACROS
 135  */
 136
 137 #define NEW_UNALU(cfg,dest,op,dr,sr1) do { \
 138         MONO_INST_NEW ((cfg), (dest), (op)); \
 139         (dest)->dreg = dr; \
 140         (dest)->sreg1 = sr1; \
 141     } while (0)
 142
 143 #define NEW_STORE_MEMBASE(cfg,dest,op,base,offset,sr) do { \
 144         MONO_INST_NEW ((cfg), (dest), (op)); \
 145         (dest)->sreg1 = sr; \
 146         (dest)->inst_destbasereg = base; \
 147         (dest)->inst_offset = offset; \
 148         } while (0)
 149
 150 #define NEW_LOAD_MEMBASE(cfg,dest,op,dr,base,offset) do { \
 151         MONO_INST_NEW ((cfg), (dest), (op)); \
 152         (dest)->dreg = (dr); \
 153         (dest)->inst_basereg = (base); \
 154         (dest)->inst_offset = (offset); \
 155         (dest)->type = STACK_I4; \
 156         } while (0)
 157
 158 #if SIZEOF_VOID_P == 8
 159 #define BITS_PER_CHUNK 64
 160 #else
 161 #define BITS_PER_CHUNK 32
 162 #endif
 163
 164 #define MONO_FIRST_VREG (MONO_MAX_IREGS+MONO_MAX_FREGS)
 165
 166 /*
 167  * Each instruction is allocated 4 liveness phases:
 168  * 0 - USE  - the instruction reads its input registers in this phase
 169  * 1 - CLOB   - the instruction clobbers some registers in this phase
 170  * 2 - DEF - the instruction writes its output register(s) in this phase
 171  * 3 - SPILL  - spill code
 172  * In liveness ranges, the start position of the range is the DEF position of the
 173  * instruction which defines the vreg.
 174  */
 175
 176 #define INS_POS_USE 0
 177 #define INS_POS_CLOB 1
 178 #define INS_POS_DEF 2
 179 #define INS_POS_SPILL 3
 180
 181 /* 16 is used instead of 4 so liveness ranges are easier to read */
 182 #define INS_POS_INTERVAL 16
 183
 184 #define is_hard_reg(r,fp) ((fp) ? ((r) < MONO_MAX_FREGS) : ((r) < MONO_MAX_IREGS))
 185 #define is_soft_reg(r,fp) (!is_hard_reg((r),(fp)))
 186
 187 #ifdef MONO_ARCH_INST_IS_FLOAT
 188 #define dreg_is_fp(spec)  (MONO_ARCH_INST_IS_FLOAT (spec [MONO_INST_DEST]))
 189 #define sreg1_is_fp(spec) (MONO_ARCH_INST_IS_FLOAT (spec [MONO_INST_SRC1]))
 190 #define sreg2_is_fp(spec) (MONO_ARCH_INST_IS_FLOAT (spec [MONO_INST_SRC2]))
 191 #else
 192 #define sreg1_is_fp(spec) (spec [MONO_INST_SRC1] == 'f')
 193 #define sreg2_is_fp(spec) (spec [MONO_INST_SRC2] == 'f')
 194 #define dreg_is_fp(spec)  (spec [MONO_INST_DEST] == 'f')
 195 #endif
 196
 197 static inline GSList*
 198 g_slist_append_mempool (MonoMemPool *mp, GSList   *list,
 199                                                 gpointer  data)
 200 {
 201         GSList *new_list, *last;
 202
 203         last = g_slist_last (list);
 204         new_list = mono_mempool_alloc (mp, sizeof (GSList));
 205         new_list->data = data;
 206         new_list->next = NULL;
 207         if (last) {
 208                 last->next = new_list;
 209                 return list;
 210         } else {
 211                 return new_list;
 212         }
 213 }
 214
 215 static void
 216 insert_after_ins (MonoBasicBlock *bb, MonoInst *ins, MonoInst *insert_after)
 217 {
 218         if (insert_after == NULL) {
 219                 insert_after = bb->code;
 220                 bb->code = ins;
 221                 ins->next = insert_after;
 222
 223                 if (bb->last_ins == NULL)
 224                         bb->last_ins = ins;
 225         }
 226         else {
 227                 ins->next = insert_after->next;
 228                 insert_after->next = ins;
 229
 230                 if (bb->last_ins == insert_after)
 231                         bb->last_ins = ins;
 232         }
 233 }
 234
 235 static MonoInst*
 236 create_move (MonoCompile *cfg, int dreg, int sreg)
 237 {
 238         MonoInst *ins;
 239
 240         MONO_INST_NEW (cfg, ins, OP_MOVE);
 241         ins->dreg = dreg;
 242         ins->sreg1 = sreg;
 243
 244         return ins;
 245 }
 246
 247 static MonoInst*
 248 create_fp_move (MonoCompile *cfg, int dreg, int sreg)
 249 {
 250         MonoInst *ins;
 251
 252         MONO_INST_NEW (cfg, ins, OP_FMOVE);
 253         ins->dreg = dreg;
 254         ins->sreg1 = sreg;
 255
 256         return ins;
 257 }
 258
 259 static void
 260 emit_move (MonoCompile *cfg, int dreg, int sreg, MonoInst *insert_after)
 261 {
 262         MonoInst *ins = create_move (cfg, dreg, sreg);
 263
 264         insert_after_ins (cfg->cbb, ins, insert_after);
 265 }
 266
 267 static void
 268 emit_fp_move (MonoCompile *cfg, int dreg, int sreg, MonoInst *insert_after)
 269 {
 270         MonoInst *ins = create_fp_move (cfg, dreg, sreg);
 271
 272         insert_after_ins (cfg->cbb, ins, insert_after);
 273 }
 274
 275 static void
 276 emit_nop (MonoCompile *cfg, MonoInst *insert_after)
 277 {
 278         MonoInst *ins;
 279
 280         MONO_INST_NEW (cfg, ins, OP_NOP);
 281
 282         insert_after_ins (cfg->cbb, ins, insert_after);
 283 }
 284
 285 /**
 286  * handle_reg_constraints:
 287  *
 288  *   Rewrite the IR so it satisfies the register constraints of the architecture.
 289  */
 290 static void
 291 handle_reg_constraints (MonoCompile *cfg)
 292 {
 293         MonoMethodSignature *sig;
 294         MonoBasicBlock *bb;
 295         int i;
 296
 297         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 298                 MonoInst *ins = bb->code;
 299                 MonoInst *prev = NULL;
 300
 301                 if (cfg->verbose_level > 1) mono_print_bb (bb, "BEFORE HANDLE-REG-CONSTRAINTS ");
 302
 303                 cfg->cbb = bb;
 304                 for (; ins; ins = ins->next) {
 305                         const char *spec = ins_get_spec (ins->opcode);
 306                         int dest_sreg1, dest_sreg2, dest_dreg;
 307
 308                         dest_sreg1 = MONO_ARCH_INST_FIXED_REG (spec [MONO_INST_SRC1]);
 309                         dest_sreg2 = MONO_ARCH_INST_FIXED_REG (spec [MONO_INST_SRC2]);
 310                         dest_dreg = MONO_ARCH_INST_FIXED_REG (spec [MONO_INST_DEST]);
 311
 312                         if (MONO_ARCH_INST_IS_REGPAIR (spec [MONO_INST_DEST]) ||
 313                                 MONO_ARCH_INST_IS_REGPAIR (spec [MONO_INST_SRC1]) ||
 314                                 MONO_ARCH_INST_IS_REGPAIR (spec [MONO_INST_SRC2]))
 315                                 /* FIXME: */
 316                                 g_assert_not_reached ();
 317
 318                         if (spec [MONO_INST_CLOB] == 'c') {
 319                                 MonoCallInst *call = (MonoCallInst*)ins;
 320                                 GSList *list;
 321
 322                                 /*
 323                                  * FIXME: mono_arch_emit_call () already adds moves for each argument,
 324                                  * it might be better to rewrite those by changing the dreg to the hreg.
 325                                  */
 326                                 for (list = call->out_ireg_args; list; list = list->next) {
 327                                         guint32 regpair;
 328                                         int reg, hreg;
 329                                         MonoInst *move;
 330
 331                                         regpair = (guint32)(gssize)(list->data);
 332                                         hreg = regpair >> 24;
 333                                         reg = regpair & 0xffffff;
 334
 335                                         move = create_move (cfg, hreg, reg);
 336                                         insert_after_ins (bb, move, prev);
 337                                         prev = move;
 338                                 }
 339
 340                                 for (list = call->out_freg_args; list; list = list->next) {
 341                                         guint32 regpair;
 342                                         int reg, hreg;
 343                                         MonoInst *move;
 344
 345                                         regpair = (guint32)(gssize)(list->data);
 346                                         hreg = regpair >> 24;
 347                                         reg = regpair & 0xffffff;
 348
 349                                         move = create_fp_move (cfg, hreg + MONO_MAX_IREGS, reg);
 350                                         insert_after_ins (bb, move, prev);
 351                                         prev = move;
 352                                 }
 353                         }
 354
 355                         if (spec [MONO_INST_CLOB] == '1') {
 356                                 /* Copying sreg1 to dreg could clobber sreg2 so make a copy of sreg2 */
 357                                 if (spec [MONO_INST_SRC2] && (ins->dreg == ins->sreg2)) {
 358                                         int new_sreg2 = mono_alloc_preg (cfg);
 359                                         MonoInst *move;
 360                                         g_assert (spec [MONO_INST_DEST] != 'f');
 361                                         move = create_move (cfg, new_sreg2, ins->sreg2);
 362                                         insert_after_ins (cfg->cbb, move, prev);
 363                                         prev = move;
 364                                         ins->sreg2 = new_sreg2;
 365                                 }
 366                                 if (spec [MONO_INST_DEST] == 'f')
 367                                         emit_fp_move (cfg, ins->dreg, ins->sreg1, prev);
 368                                 else
 369                                         emit_move (cfg, ins->dreg, ins->sreg1, prev);
 370                                 ins->sreg1 = ins->dreg;
 371                         }
 372
 373                         if (dest_sreg1 != -1) {
 374                                 emit_move (cfg, dest_sreg1, ins->sreg1, prev);
 375                                 ins->sreg1 = dest_sreg1;
 376                         }
 377
 378                         if (dest_sreg2 != -1) {
 379                                 emit_move (cfg, dest_sreg2, ins->sreg2, prev);
 380                                 ins->sreg2 = dest_sreg2;
 381                         }
 382
 383                         if (dest_dreg != -1) {
 384                                 emit_move (cfg, ins->dreg, dest_dreg, ins);
 385                                 g_assert (spec [MONO_INST_CLOB] != '1');
 386                                 ins->dreg = dest_dreg;
 387                         }
 388
 389                         /* FIXME: Add fixed fp regs to the machine description */
 390                         if (ins->opcode == OP_FCALL || ins->opcode == OP_FCALL_REG || ins->opcode == OP_FCALL_MEMBASE) {
 391                                 emit_fp_move (cfg, ins->dreg, MONO_MAX_IREGS + MONO_ARCH_FP_RETURN_REG, ins);
 392                                 ins->dreg = MONO_MAX_IREGS + MONO_ARCH_FP_RETURN_REG;
 393                         }
 394
 395                         /*
 396                          * Add a dummy instruction after each definition of a volatile vreg, this is
 397                          * needed by the code in decompose_volatile_intervals ().
 398                          */
 399                         if (get_vreg_to_inst (cfg, ins->dreg) && (get_vreg_to_inst (cfg, ins->dreg)->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
 400                                 emit_nop (cfg, ins);
 401                         }
 402
 403                         prev = ins;
 404                 }
 405
 406                 sig = mono_method_signature (cfg->method);
 407
 408                 /* Add move of arguments */
 409                 /*
 410                  * FIXME: Maybe this should be done by the allocator.
 411                  */
 412                 if (bb == cfg->bb_entry) {
 413                         MonoType *arg_type;
 414
 415                         prev = NULL;
 416                         if (cfg->vret_addr) {
 417                                 g_assert (cfg->vret_addr->opcode == OP_REGVAR);
 418                                 emit_move (cfg, cfg->vret_addr->dreg, cfg->vret_addr->inst_c0, prev);
 419                                 prev = bb->code;
 420                         }
 421
 422                         for (i = 0; i < sig->param_count + sig->hasthis; ++i) {
 423                                 ins = cfg->args [i];
 424
 425                                 if (sig->hasthis && (i == 0))
 426                                         arg_type = &mono_defaults.object_class->byval_arg;
 427                                 else
 428                                         arg_type = sig->params [i - sig->hasthis];
 429
 430                                 // FIXME: vtypes in registers (pass + return)
 431
 432                                 if (ins->opcode == OP_REGVAR) {
 433                                         if (!arg_type->byref && ((arg_type->type == MONO_TYPE_R4) || (arg_type->type == MONO_TYPE_R8)))
 434                                                 /* For R4, the prolog is assumed to do the conversion */
 435                                                 emit_fp_move (cfg, ins->dreg, ins->inst_c0 + MONO_MAX_IREGS, prev);
 436                                         else
 437                                                 emit_move (cfg, ins->dreg, ins->inst_c0, prev);
 438                                 }
 439
 440                                 prev = bb->code;
 441                         }
 442                 }
 443
 444                 /* Add move of return value */
 445                 for (i = 0; i < bb->out_count; ++i) {
 446                         if (cfg->ret && !cfg->vret_addr && !MONO_TYPE_ISSTRUCT (sig->ret) && bb->out_bb [i] == cfg->bb_exit) {
 447                                 MonoInst *ins = NULL;
 448                                 int hreg;
 449
 450                                 hreg = cfg->ret->inst_c0;
 451
 452                                 if ((sig->ret->type == MONO_TYPE_R4) || (sig->ret->type == MONO_TYPE_R8))
 453                                         /* For R4, the JIT has already emitted code to do the conversion */
 454                                         ins = create_fp_move (cfg, hreg + MONO_MAX_IREGS, cfg->ret->dreg);
 455                                 else
 456                                         ins = create_move (cfg, hreg, cfg->ret->dreg);
 457                                 mono_add_ins_to_end (bb, ins);
 458                         }
 459                 }
 460
 461                 if (cfg->verbose_level > 1) mono_print_bb (bb, "AFTER HANDLE-REG-CONSTRAINTS ");
 462         }
 463 }
 464
 465 /*
 466  * collect_fp_vregs:
 467  *
 468  *   Set varinfo->fp for all float vregs
 469  */
 470 static void
 471 collect_fp_vregs (MonoCompile *cfg, MonoRegallocContext *ctx)
 472 {
 473         MonoBasicBlock *bb;
 474
 475         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 476                 MonoInst *ins = bb->code;
 477
 478                 for (; ins; ins = ins->next) {
 479                         const char *spec = ins_get_spec (ins->opcode);
 480
 481                         if (G_UNLIKELY (sreg1_is_fp (spec) || sreg2_is_fp (spec) || dreg_is_fp (spec))) {
 482                                 if (sreg1_is_fp (spec)) {
 483                                         g_assert (ins->sreg1 >= MONO_MAX_IREGS);
 484                                         ctx->varinfo [ins->sreg1].fp = TRUE;
 485                                         if (ctx->varinfo [ins->sreg1].type->type != MONO_TYPE_R4)
 486                                                 ctx->varinfo [ins->sreg1].type = &mono_defaults.double_class->byval_arg;
 487                                 }
 488                                 if (sreg2_is_fp (spec)) {
 489                                         g_assert (ins->sreg2 >= MONO_MAX_IREGS);
 490                                         ctx->varinfo [ins->sreg2].fp = TRUE;
 491                                         if (ctx->varinfo [ins->sreg2].type->type != MONO_TYPE_R4)
 492                                                 ctx->varinfo [ins->sreg2].type = &mono_defaults.double_class->byval_arg;
 493                                 }
 494                                 if (dreg_is_fp (spec)) {
 495                                         g_assert (ins->dreg >= MONO_MAX_IREGS);
 496                                         ctx->varinfo [ins->dreg].fp = TRUE;
 497                                         if (ctx->varinfo [ins->dreg].type->type != MONO_TYPE_R4)
 498                                                 ctx->varinfo [ins->dreg].type = &mono_defaults.double_class->byval_arg;
 499                                 }
 500                         }
 501                 }
 502         }
 503 }
 504
 505 #if 1
 506 #define LIVENESS_DEBUG(a) do { if (cfg->verbose_level > 2) { a; } } while (0)
 507 #else
 508 #define LIVENESS_DEBUG(a)
 509 #endif
 510
 511 // #define DEBUG_LIVENESS 1
 512
 513 G_GNUC_UNUSED static void
 514 mono_bitset_print (MonoBitSet *set)
 515 {
 516         int i;
 517
 518         printf ("{");
 519         for (i = 0; i < mono_bitset_size (set); i++) {
 520
 521                 if (mono_bitset_test (set, i))
 522                         printf ("%d, ", i);
 523
 524         }
 525         printf ("}\n");
 526 }
 527
 528 static inline void
 529 update_gen_kill_set (MonoCompile *cfg, MonoRegallocContext *ctx, MonoBasicBlock *bb, MonoInst *ins)
 530 {
 531         const char *spec = INS_INFO (ins->opcode);
 532         int sreg;
 533
 534         /* SREG1 */
 535         sreg = ins->sreg1;
 536         if (spec [MONO_INST_SRC1] != ' ') {
 537                 if (!mono_bitset_test_fast (bb->kill_set, sreg))
 538                         mono_bitset_set_fast (bb->gen_set, sreg);
 539         }
 540
 541         /* SREG2 */
 542         sreg = ins->sreg2;
 543         if (spec [MONO_INST_SRC2] != ' ') {
 544                 if (!mono_bitset_test_fast (bb->kill_set, sreg))
 545                         mono_bitset_set_fast (bb->gen_set, sreg);
 546         }
 547
 548         /* DREG */
 549         if (spec [MONO_INST_DEST] != ' ') {
 550                 if (MONO_IS_STORE_MEMBASE (ins)) {
 551                         if (!mono_bitset_test_fast (bb->kill_set, ins->dreg))
 552                                 mono_bitset_set_fast (bb->gen_set, ins->dreg);
 553                 } else {
 554                         mono_bitset_set_fast (bb->kill_set, ins->dreg);
 555                 }
 556         }
 557 }
 558
 559 static void
 560 compute_gen_kill_sets (MonoCompile *cfg, MonoRegallocContext *ctx)
 561 {
 562         int i, max_vars = cfg->next_vreg;
 563         int bitsize;
 564         guint8 *mem;
 565
 566         bitsize = mono_bitset_alloc_size (max_vars, 0);
 567         mem = mono_mempool_alloc0 (cfg->mempool, cfg->num_bblocks * bitsize * 3);
 568
 569         for (i = 0; i < cfg->num_bblocks; ++i) {
 570                 MonoBasicBlock *bb = cfg->bblocks [i];
 571
 572                 bb->gen_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 573                 mem += bitsize;
 574                 bb->kill_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 575                 mem += bitsize;
 576                 /* Initialized later */
 577                 bb->live_in_set = NULL;
 578                 bb->live_out_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 579                 mem += bitsize;
 580         }
 581
 582         for (i = 0; i < cfg->num_bblocks; ++i) {
 583                 MonoBasicBlock *bb = cfg->bblocks [i];
 584                 MonoInst *ins;
 585 #ifdef DEBUG_LIVENESS
 586                 int j;
 587 #endif
 588
 589                 for (ins = bb->code; ins; ins = ins->next)
 590                         update_gen_kill_set (cfg, ctx, bb, ins);
 591
 592 #ifdef DEBUG_LIVENESS
 593                 printf ("BLOCK BB%d (", bb->block_num);
 594                 for (j = 0; j < bb->out_count; j++)
 595                         printf ("BB%d, ", bb->out_bb [j]->block_num);
 596
 597                 printf (")\n");
 598                 printf ("GEN  BB%d: ", bb->block_num); mono_bitset_print (bb->gen_set);
 599                 printf ("KILL BB%d: ", bb->block_num); mono_bitset_print (bb->kill_set);
 600 #endif
 601         }
 602
 603         if (cfg->ret && cfg->ret->opcode == OP_REGVAR) {
 604                 int hreg = cfg->ret->inst_c0;
 605
 606                 /* gen_set might be empty if bb_exit is not reachable, like when using a tail call */
 607                 if (cfg->bb_exit->gen_set)
 608                         mono_bitset_set (cfg->bb_exit->gen_set, hreg);
 609         }
 610 }
 611
 612 static void
 613 compute_live_in_out_sets (MonoCompile *cfg, MonoRegallocContext *ctx)
 614 {
 615         MonoBitSet *old_live_out_set;
 616         int i, j, max_vars = cfg->next_vreg;
 617         int out_iter;
 618         gboolean *in_worklist;
 619         MonoBasicBlock **worklist;
 620         guint32 l_end;
 621         int bitsize;
 622         guint8 *mem;
 623
 624         bitsize = mono_bitset_alloc_size (max_vars, 0);
 625         mem = mono_mempool_alloc0 (cfg->mempool, cfg->num_bblocks * bitsize);
 626
 627         old_live_out_set = mono_bitset_new (max_vars, 0);
 628         in_worklist = g_new0 (gboolean, cfg->num_bblocks + 1);
 629
 630         worklist = g_new (MonoBasicBlock *, cfg->num_bblocks + 1);
 631         l_end = 0;
 632
 633         /*
 634          * This is a backward dataflow analysis problem, so we process blocks in
 635          * decreasing dfn order, this speeds up the iteration.
 636          */
 637         for (i = 0; i < cfg->num_bblocks; i ++) {
 638                 MonoBasicBlock *bb = cfg->bblocks [i];
 639
 640                 worklist [l_end ++] = bb;
 641                 in_worklist [bb->dfn] = TRUE;
 642         }
 643
 644         out_iter = 0;
 645
 646         while (l_end != 0) {
 647                 MonoBasicBlock *bb = worklist [--l_end];
 648                 MonoBasicBlock *out_bb;
 649                 gboolean changed;
 650
 651                 in_worklist [bb->dfn] = FALSE;
 652
 653 #ifdef DEBUG_LIVENESS
 654                 printf ("P: %d(%d): IN: ", bb->block_num, bb->dfn);
 655                 for (j = 0; j < bb->in_count; ++j)
 656                         printf ("BB%d ", bb->in_bb [j]->block_num);
 657                 printf ("OUT:");
 658                 for (j = 0; j < bb->out_count; ++j)
 659                         printf ("BB%d ", bb->out_bb [j]->block_num);
 660                 printf ("\n");
 661 #endif
 662
 663
 664                 if (bb->out_count == 0)
 665                         continue;
 666
 667                 out_iter ++;
 668
 669                 if (!bb->live_in_set) {
 670                         /* First pass over this bblock */
 671                         changed = TRUE;
 672                 }
 673                 else {
 674                         changed = FALSE;
 675                         mono_bitset_copyto_fast (bb->live_out_set, old_live_out_set);
 676                 }
 677
 678                 for (j = 0; j < bb->out_count; j++) {
 679                         out_bb = bb->out_bb [j];
 680
 681                         if (!out_bb->live_in_set) {
 682                                 out_bb->live_in_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 683                                 mem += bitsize;
 684
 685                                 mono_bitset_copyto_fast (out_bb->live_out_set, out_bb->live_in_set);
 686                                 mono_bitset_sub_fast (out_bb->live_in_set, out_bb->kill_set);
 687                                 mono_bitset_union_fast (out_bb->live_in_set, out_bb->gen_set);
 688                         }
 689
 690                         mono_bitset_union_fast (bb->live_out_set, out_bb->live_in_set);
 691                 }
 692
 693                 if (changed || !mono_bitset_equal (old_live_out_set, bb->live_out_set)) {
 694                         if (!bb->live_in_set) {
 695                                 bb->live_in_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 696                                 mem += bitsize;
 697                         }
 698                         mono_bitset_copyto_fast (bb->live_out_set, bb->live_in_set);
 699                         mono_bitset_sub_fast (bb->live_in_set, bb->kill_set);
 700                         mono_bitset_union_fast (bb->live_in_set, bb->gen_set);
 701
 702                         for (j = 0; j < bb->in_count; j++) {
 703                                 MonoBasicBlock *in_bb = bb->in_bb [j];
 704                                 /*
 705                                  * Some basic blocks do not seem to be in the
 706                                  * cfg->bblocks array...
 707                                  */
 708                                 if (in_bb->gen_set && !in_worklist [in_bb->dfn]) {
 709 #ifdef DEBUG_LIVENESS
 710                                         printf ("\tADD: %d\n", in_bb->block_num);
 711 #endif
 712                                         /*
 713                                          * Put the block at the top of the stack, so it
 714                                          * will be processed right away.
 715                                          */
 716                                         worklist [l_end ++] = in_bb;
 717                                         in_worklist [in_bb->dfn] = TRUE;
 718                                 }
 719                         }
 720                 }
 721         }
 722
 723 #ifdef DEBUG_LIVENESS
 724                 printf ("IT: %d %d.\n", cfg->num_bblocks, out_iter);
 725 #endif
 726
 727         mono_bitset_free (old_live_out_set);
 728
 729         g_free (worklist);
 730         g_free (in_worklist);
 731
 732         /* Compute live_in_set for bblocks skipped earlier */
 733         for (i = 0; i < cfg->num_bblocks; ++i) {
 734                 MonoBasicBlock *bb = cfg->bblocks [i];
 735
 736                 if (!bb->live_in_set) {
 737                         bb->live_in_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
 738                         mem += bitsize;
 739
 740                         mono_bitset_copyto_fast (bb->live_out_set, bb->live_in_set);
 741                         mono_bitset_sub_fast (bb->live_in_set, bb->kill_set);
 742                         mono_bitset_union_fast (bb->live_in_set, bb->gen_set);
 743                 }
 744         }
 745
 746 #ifdef DEBUG_LIVENESS
 747         for (i = cfg->num_bblocks - 1; i >= 0; i--) {
 748                 MonoBasicBlock *bb = cfg->bblocks [i];
 749
 750                 printf ("LIVE IN  BB%d: ", bb->block_num);
 751                 mono_bitset_print (bb->live_in_set);
 752                 printf ("LIVE OUT BB%d: ", bb->block_num);
 753                 mono_bitset_print (bb->live_out_set);
 754         }
 755 #endif
 756 }
 757
 758 static inline void
 759 update_liveness (MonoCompile *cfg, MonoRegallocContext *ctx, MonoInst *ins, int inst_num, gint32 *last_use)
 760 {
 761         const char *spec = INS_INFO (ins->opcode);
 762         int sreg;
 763
 764         LIVENESS_DEBUG (printf ("\t%x: ", inst_num); mono_print_ins (ins));
 765
 766         /* DREG */
 767         if (spec [MONO_INST_DEST] != ' ') {
 768                 if (MONO_IS_STORE_MEMBASE (ins)) {
 769                         if (last_use [ins->dreg] == 0) {
 770                                 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins->dreg, inst_num + INS_POS_USE));
 771                                 last_use [ins->dreg] = inst_num + INS_POS_USE;
 772                         }
 773                 } else {
 774                         if (last_use [ins->dreg] > 0) {
 775                                 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x]\n", ins->dreg, inst_num + INS_POS_DEF, last_use [ins->dreg]));
 776                                 mono_linterval_add_range (ctx->cfg, ctx->varinfo [ins->dreg].interval, inst_num + INS_POS_DEF, last_use [ins->dreg]);
 777                                 last_use [ins->dreg] = 0;
 778                         }
 779                         else {
 780                                 if (!vreg_is_volatile (cfg, ins->dreg) && ((ins->opcode == OP_ICONST) || (ins->opcode == OP_I8CONST) || (ins->opcode == OP_R8CONST) || (ins->opcode == OP_MOVE) || (ins->opcode == OP_FMOVE))) {
 781                                         LIVENESS_DEBUG (printf ("\tdead def of R%d eliminated\n", ins->dreg));
 782                                         NULLIFY_INS (ins);
 783                                         spec = INS_INFO (ins->opcode);
 784                                 } else {
 785                                         LIVENESS_DEBUG (printf ("\tdead def of R%d, add range to R%d: [%x, %x]\n", ins->dreg, ins->dreg, inst_num + INS_POS_DEF, inst_num + INS_POS_DEF));
 786                                         mono_linterval_add_range (ctx->cfg, ctx->varinfo [ins->dreg].interval, inst_num + INS_POS_DEF, inst_num + INS_POS_DEF);
 787                                 }
 788                         }
 789                 }
 790                 if (ins->opcode != OP_NOP)
 791                         /* Since we process instructions backwards, the list will be properly sorted */
 792                         ctx->varinfo [ins->dreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [ins->dreg].use_pos, GINT_TO_POINTER (inst_num));
 793
 794                 /* Set preferred vregs */
 795                 if ((ins->opcode == OP_MOVE) || (ins->opcode == OP_FMOVE)) {
 796                         if (ins->sreg1 < MONO_FIRST_VREG) {
 797                                 ctx->varinfo [ins->dreg].preferred_reg = ins->sreg1;
 798                         } else if (ins->dreg < MONO_FIRST_VREG) {
 799                                 ctx->varinfo [ins->sreg1].preferred_reg = ins->dreg;
 800                         } else if (ctx->varinfo [ins->dreg].preferred_reg != -1) {
 801                                 /*
 802                                  * Propagate preferred vregs. This works because instructions are
 803                                  * processed in reverse order.
 804                                  */
 805                                 ctx->varinfo [ins->sreg1].preferred_reg = ctx->varinfo [ins->dreg].preferred_reg;
 806                         }
 807                 }
 808         }
 809
 810         /* SREG1 */
 811         sreg = ins->sreg1;
 812         if (spec [MONO_INST_SRC1] != ' ') {
 813                 if (last_use [sreg] == 0) {
 814                         LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg, inst_num + INS_POS_USE));
 815                         last_use [sreg] = inst_num + INS_POS_USE;
 816                 }
 817                 ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
 818         }
 819
 820         /* SREG2 */
 821         sreg = ins->sreg2;
 822         if (spec [MONO_INST_SRC2] != ' ') {
 823                 if (last_use [sreg] == 0) {
 824                         LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg, inst_num + INS_POS_USE));
 825                         last_use [sreg] = inst_num + INS_POS_USE;
 826                 }
 827                 ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
 828         }
 829
 830         if (ins_get_spec (ins->opcode)[MONO_INST_CLOB] == 'c') {
 831                 MonoCallInst *call = (MonoCallInst*)ins;
 832                 GSList *list;
 833
 834                 for (list = call->out_ireg_args; list; list = list->next) {
 835                         guint32 regpair;
 836
 837                         regpair = (guint32)(gssize)(list->data);
 838                         sreg = regpair >> 24;
 839
 840                         if (last_use [sreg] == 0) {
 841                                 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg, inst_num + INS_POS_USE));
 842                                 last_use [sreg] = inst_num + INS_POS_USE;
 843                         }
 844                         ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
 845                 }
 846
 847                 for (list = call->out_freg_args; list; list = list->next) {
 848                         guint32 regpair;
 849
 850                         regpair = (guint32)(gssize)(list->data);
 851                         sreg = (regpair >> 24) + MONO_MAX_IREGS;
 852
 853                         if (last_use [sreg] == 0) {
 854                                 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg, inst_num + INS_POS_USE));
 855                                 last_use [sreg] = inst_num + INS_POS_USE;
 856                         }
 857                         ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
 858                 }
 859         }
 860
 861         /* CLOBBERING */
 862         if (ins_get_spec (ins->opcode)[MONO_INST_CLOB]) {
 863                 char clob = ins_get_spec (ins->opcode)[MONO_INST_CLOB];
 864                 GList *l;
 865
 866                 if (clob == 'c') {
 867                         /* A call clobbers some int/fp registers */
 868                         for (l = mono_arch_get_iregs_clobbered_by_call ((MonoCallInst*)ins); l; l = l->next)
 869                                 mono_linterval_add_range (ctx->cfg, ctx->varinfo [GPOINTER_TO_INT (l->data)].interval, inst_num + INS_POS_CLOB, inst_num + INS_POS_CLOB);
 870                         for (l = mono_arch_get_fregs_clobbered_by_call ((MonoCallInst*)ins); l; l = l->next)
 871                                 mono_linterval_add_range (ctx->cfg, ctx->varinfo [GPOINTER_TO_INT (l->data)].interval, inst_num + INS_POS_CLOB, inst_num + INS_POS_CLOB);
 872                 }
 873                 else {
 874                         int clob_reg = MONO_ARCH_INST_FIXED_REG (clob);
 875
 876                         if (clob_reg != -1)
 877                                 mono_linterval_add_range (ctx->cfg, ctx->varinfo [clob_reg].interval, inst_num + INS_POS_CLOB, inst_num + INS_POS_CLOB);
 878                 }
 879         }
 880 }
 881
 882 /*
 883  * compute_intervals:
 884  *
 885  *   Compute liveness intervals for all vregs.
 886  */
 887 static void
 888 compute_intervals (MonoCompile *cfg, MonoRegallocContext *ctx)
 889 {
 890         int bnum, idx, i, j, nins, rem, max, max_vars, block_from, block_to, pos, reverse_len;
 891         gint32 *last_use;
 892         MonoInst **reverse;
 893
 894         max_vars = cfg->next_vreg;
 895         last_use = g_new0 (gint32, max_vars);
 896
 897         reverse_len = 1024;
 898         reverse = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * reverse_len);
 899
 900         for (idx = 0; idx < max_vars; ++idx) {
 901                 ctx->varinfo [idx].interval = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoLiveInterval));
 902         }
 903
 904         /*
 905          * Process bblocks in reverse order, so the addition of new live ranges
 906          * to the intervals is faster.
 907          */
 908         for (bnum = cfg->num_bblocks - 1; bnum >= 0; --bnum) {
 909                 MonoBasicBlock *bb = cfg->bblocks [bnum];
 910                 MonoInst *ins;
 911
 912                 block_from = (bb->dfn << 16); /* so pos > 0 */
 913                 if (bnum < cfg->num_bblocks - 1)
 914                         /* Beginning of the next bblock */
 915                         block_to = (cfg->bblocks [bnum + 1]->dfn << 16);
 916                 else
 917                         block_to = (bb->dfn << 16) + 0xffff;
 918
 919                 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb->block_num));
 920
 921                 memset (last_use, 0, max_vars * sizeof (gint32));
 922
 923                 /* For variables in bb->live_out, set last_use to block_to */
 924
 925                 rem = max_vars % BITS_PER_CHUNK;
 926                 max = ((max_vars + (BITS_PER_CHUNK -1)) / BITS_PER_CHUNK);
 927                 for (j = 0; j < max; ++j) {
 928                         gsize bits_out;
 929                         int k;
 930
 931                         bits_out = mono_bitset_get_fast (bb->live_out_set, j);
 932                         k = (j * BITS_PER_CHUNK);
 933                         while (bits_out) {
 934                                 if (bits_out & 1) {
 935                                         LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", k, block_to));
 936                                         last_use [k] = block_to;
 937                                 }
 938                                 bits_out >>= 1;
 939                                 k ++;
 940                         }
 941                 }
 942
 943                 for (nins = 0, pos = block_from, ins = bb->code; ins; ins = ins->next, ++nins, pos += INS_POS_INTERVAL) {
 944                         if (nins >= reverse_len) {
 945                                 int new_reverse_len = reverse_len * 2;
 946                                 MonoInst **new_reverse = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * new_reverse_len);
 947                                 memcpy (new_reverse, reverse, sizeof (MonoInst*) * reverse_len);
 948                                 reverse = new_reverse;
 949                                 reverse_len = new_reverse_len;
 950                         }
 951
 952                         reverse [nins] = ins;
 953                 }
 954
 955                 g_assert (pos < block_to);
 956
 957                 /* Process instructions backwards */
 958                 for (i = nins - 1; i >= 0; --i) {
 959                         MonoInst *ins = (MonoInst*)reverse [i];
 960
 961                         update_liveness (cfg, ctx, ins, pos, last_use);
 962
 963                         pos -= INS_POS_INTERVAL;
 964                 }
 965
 966                 for (idx = 0; idx < max_vars; ++idx) {
 967                         if (last_use [idx] != 0) {
 968                                 /* Live at exit, not written -> live on enter */
 969                                 LIVENESS_DEBUG (printf ("Var R%d live at enter, add range to R%d: [%x, %x)\n", idx, idx, block_from, last_use [idx]));
 970                                 mono_linterval_add_range (cfg, ctx->varinfo [idx].interval, block_from, last_use [idx]);
 971                         }
 972                 }
 973         }
 974
 975 #if 0
 976         // FIXME:
 977         /*
 978          * Arguments need to have their live ranges extended to the beginning of
 979          * the method to account for the arg reg/memory -> global register copies
 980          * in the prolog (bug #74992).
 981          */
 982         for (i = 0; i < cfg->num_varinfo; i ++) {
 983                 MonoMethodVar *vi = MONO_VARINFO (cfg, i);
 984                 if ((cfg->varinfo [vi->idx]->opcode == OP_ARG) && (cfg->varinfo [vi->idx] != cfg->ret))
 985                         mono_linterval_add_range (cfg, ctx->varinfo [cfg->varinfo [i]->dreg].interval, 0, 1);
 986         }
 987 #endif
 988
 989 #if 0
 990                 for (idx = 0; idx < max_vars; ++idx) {
 991                         printf ("LIVENESS R%d: ", idx);
 992                         mono_linterval_print (ctx->varinfo [idx].interval);
 993                         printf ("\n");
 994                 }
 995         }
 996 #endif
 997
 998         g_free (last_use);
 999 }
1000
1001 /*
1002  * analyze_liveness:
1003  *
1004  *   Perform liveness analysis.
1005  */
1006 static void
1007 analyze_liveness (MonoCompile *cfg, MonoRegallocContext *ctx)
1008 {
1009         LIVENESS_DEBUG (printf ("LIVENESS 3 %s\n", mono_method_full_name (cfg->method, TRUE)));
1010
1011         /* FIXME: Make only one pass over the IR */
1012
1013         compute_gen_kill_sets (cfg, ctx);
1014
1015         compute_live_in_out_sets (cfg, ctx);
1016
1017         compute_intervals (cfg, ctx);
1018 }
1019
1020
1021 static gint
1022 compare_by_interval_start_pos_func (gconstpointer a, gconstpointer b)
1023 {
1024         MonoRegallocInterval *v1 = (MonoRegallocInterval*)a;
1025         MonoRegallocInterval *v2 = (MonoRegallocInterval*)b;
1026
1027         if (v1 == v2)
1028                 return 0;
1029         else if (v1->interval->range && v2->interval->range)
1030                 return v1->interval->range->from - v2->interval->range->from;
1031         else if (v1->interval->range)
1032                 return -1;
1033         else
1034                 return 1;
1035 }
1036
1037 #define LSCAN_DEBUG(a) MINI_DEBUG(cfg->verbose_level, 2, a;)
1038
1039 /**
1040  * split_interval:
1041  *
1042  *   Split the interval into two child intervals at POS.
1043  * [a, b] becomes [a, POS - 1], [POS, b].
1044  */
1045 static void
1046 split_interval (MonoCompile *cfg, MonoRegallocContext *ctx, MonoRegallocInterval *interval, int pos)
1047 {
1048         MonoRegallocInterval *child1, *child2;
1049         GSList *l, *split_list;
1050
1051         child1 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRegallocInterval));
1052         child2 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRegallocInterval));
1053         child1->vreg = ctx->num_intervals ++;
1054         child1->hreg = -1;
1055         child1->offset = -1;
1056         child1->preferred_reg = -1;
1057         child1->is_volatile = interval->is_volatile;
1058         child1->fp = interval->fp;
1059         child1->type = interval->type;
1060         child2->vreg = ctx->num_intervals ++;
1061         child2->hreg = -1;
1062         child2->offset = -1;
1063         child2->preferred_reg = -1;
1064         child2->is_volatile = interval->is_volatile;
1065         child2->fp = interval->fp;
1066         child2->type = interval->type;
1067
1068         interval->child1 = child1;
1069         interval->child2 = child2;
1070         child1->parent = interval;
1071         child2->parent = interval;
1072
1073         mono_linterval_split (cfg, interval->interval, &child1->interval, &child2->interval, pos);
1074
1075         /* Split use positions */
1076         for (l = interval->use_pos; l; l = l->next) {
1077                 int use_pos = GPOINTER_TO_INT (l->data);
1078
1079                 if (use_pos < pos)
1080                         child1->use_pos = g_slist_append_mempool (cfg->mempool, child1->use_pos, l->data);
1081                 else
1082                         child2->use_pos = g_slist_append_mempool (cfg->mempool, child2->use_pos, l->data);
1083         }
1084
1085         /* Remember where spill code needs to be inserted */
1086         split_list = g_hash_table_lookup (ctx->split_positions, GUINT_TO_POINTER (pos));
1087         split_list = g_slist_prepend (split_list, interval);
1088         g_hash_table_insert (ctx->split_positions, GUINT_TO_POINTER (pos), split_list);
1089         g_hash_table_insert (ctx->split_position_set, GUINT_TO_POINTER (pos - (pos % INS_POS_INTERVAL)), GUINT_TO_POINTER (pos));
1090
1091         if (cfg->verbose_level > 2) {
1092                 printf ("\tSplit R%d into R%d and R%d at %x\n", interval->vreg, child1->vreg, child2->vreg, pos);
1093                 printf ("\t R%d ", interval->vreg);
1094                 mono_linterval_print (interval->interval);
1095                 printf ("-> R%d ", child1->vreg);
1096                 mono_linterval_print (child1->interval);
1097                 printf ("||| R%d ", child2->vreg);
1098                 mono_linterval_print (child2->interval);
1099                 printf ("\n");
1100         }
1101 }
1102
1103 /**
1104  * child_at:
1105  *
1106  *   Return L or one of its children which covers POS.
1107  */
1108 static MonoRegallocInterval*
1109 child_at (MonoRegallocInterval *l, int pos)
1110 {
1111         if (l->vreg < MONO_FIRST_VREG)
1112                 return l;
1113
1114         if (!l->child1) {
1115                 g_assert (mono_linterval_covers (l->interval, pos));
1116                 return l;
1117         }
1118
1119         if (mono_linterval_covers (l->child1->interval, pos))
1120                 return child_at (l->child1, pos);
1121         else if (mono_linterval_covers (l->child2->interval, pos))
1122                 return child_at (l->child2, pos);
1123         else {
1124                 g_assert_not_reached ();
1125                 return NULL;
1126         }
1127 }
1128
1129 /**
1130  * decompose_volatile_intervals:
1131  *
1132  *   Decompose intervals belonging to volatile variables. Return the decomposed intervals
1133  * which should be allocated to registers.
1134  */
1135 static GList*
1136 decompose_volatile_intervals (MonoCompile *cfg, MonoRegallocContext *ctx, GList *intervals)
1137 {
1138         GList *new_intervals;
1139         GList *l;
1140
1141         /*
1142          * We model volatile intervals by splitting them at use positions and spilling the
1143          * sub intervals, ie. [a, b] is transformed to [a, a], [a + 1, b], [b, b] with the
1144          * middle interval spilled. This ensures that the variable will be spilled after each
1145          * def, and it will be loaded before each use.
1146          * FIXME: Stress test this by making most variables volatile
1147          */
1148         new_intervals = g_list_copy (intervals);
1149         for (l = intervals; l; l = l->next) {
1150                 MonoRegallocInterval *current = l->data;
1151                 GSList *use_pos;
1152
1153                 if (!current->is_volatile)
1154                         continue;
1155
1156                 /*
1157                  * Instead of trying to split the arbitrary interval produced by the liveness
1158                  * analysis phase, just use one big interval.
1159                  */
1160                 current->interval = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoLiveInterval));
1161                 mono_linterval_add_range (cfg, current->interval, 0, (32767 << 16));
1162
1163                 LSCAN_DEBUG (printf ("R%d is volatile ", current->vreg));
1164                 LSCAN_DEBUG (mono_linterval_print (current->interval));
1165                 LSCAN_DEBUG (printf ("\n"));
1166
1167                 new_intervals = g_list_remove (new_intervals, current);
1168
1169                 use_pos = current->use_pos;
1170                 while (use_pos) {
1171                         int pos = GPOINTER_TO_INT (use_pos->data);
1172                         use_pos = use_pos->next;
1173
1174                         LSCAN_DEBUG (printf ("\tUse pos: %x\n", pos));
1175
1176                         /* Split the part of the interval before the definition into its own interval */
1177                         if (pos > current->interval->range->from) {
1178                                 split_interval (cfg, ctx, current, pos);
1179                                 current = current->child2;
1180                         }
1181
1182                         /* Split the use into its own interval */
1183                         split_interval (cfg, ctx, current, pos + INS_POS_INTERVAL);
1184                         new_intervals = g_list_insert_sorted (new_intervals, current->child1, compare_by_interval_start_pos_func);
1185                         current = current->child2;
1186
1187                         /* No need to (and hard to) split between use positions at the same place */
1188                         while (use_pos && GPOINTER_TO_INT (use_pos->data) == pos)
1189                                 use_pos = use_pos->next;
1190                 }
1191         }
1192
1193         return new_intervals;
1194 }
1195
1196 /**
1197  * linear_scan:
1198  *
1199  *   The actual linear scan register allocation algorithm.
1200  */
1201 static void
1202 linear_scan (MonoCompile *cfg, MonoRegallocContext *ctx)
1203 {
1204         GList *int_regs = mono_arch_get_global_int_regs (cfg);
1205         GList *fp_regs = mono_arch_get_global_fp_regs (cfg);
1206         GList *vars;
1207         GList *unhandled, *active, *inactive, *l, *next;
1208         gint32 free_pos [MONO_MAX_IREGS + MONO_MAX_FREGS];
1209         gboolean allocateable [MONO_MAX_IREGS + MONO_MAX_FREGS];
1210         int i;
1211         MonoMethodSignature *sig;
1212         MonoMethodHeader *header;
1213
1214         LSCAN_DEBUG (printf ("\nLinear Scan 2 for %s:\n", mono_method_full_name (cfg->method, TRUE)));
1215
1216         header = mono_method_get_header (cfg->method);
1217
1218         sig = mono_method_signature (cfg->method);
1219
1220         /* Create list of allocatable variables */
1221         vars = NULL;
1222         for (i = MONO_FIRST_VREG; i < cfg->next_vreg; ++i) {
1223                 if (ctx->varinfo [i].interval->range)
1224                         vars = g_list_prepend (vars, &ctx->varinfo [i]);
1225         }
1226
1227         for (i = 0; i < MONO_MAX_IREGS; ++i)
1228                 allocateable [i] = g_list_find (int_regs, GINT_TO_POINTER (i)) != NULL;
1229         for (i = 0; i < MONO_MAX_FREGS; ++i)
1230                 allocateable [MONO_MAX_IREGS + i] = g_list_find (fp_regs, GINT_TO_POINTER (i)) != NULL;
1231         g_list_free (int_regs);
1232         g_list_free (fp_regs);
1233
1234         unhandled = g_list_sort (g_list_copy (vars), compare_by_interval_start_pos_func);
1235         active = NULL;
1236         inactive = NULL;
1237
1238         /* The hard registers are assigned to themselves */
1239         for (i = 0; i < MONO_MAX_IREGS + MONO_MAX_FREGS; ++i) {
1240                 ctx->varinfo [i].hreg = i;
1241                 if (ctx->varinfo [i].interval->range)
1242                         inactive = g_list_append (inactive, &ctx->varinfo [i]);
1243         }
1244
1245         unhandled = decompose_volatile_intervals (cfg, ctx, unhandled);
1246
1247         /*
1248          * Handle arguments received on the stack by splitting their interval, and later
1249          * allocating the spilled part to the arg location.
1250          */
1251         for (i = 0; i < sig->param_count + sig->hasthis; ++i) {
1252                 MonoInst *ins = cfg->args [i];
1253                 MonoRegallocInterval *current = &ctx->varinfo [ins->dreg];
1254                 MonoType *arg_type;
1255
1256                 if (sig->hasthis && (i == 0))
1257                         arg_type = &mono_defaults.object_class->byval_arg;
1258                 else
1259                         arg_type = sig->params [i - sig->hasthis];
1260
1261                 if (ins->opcode != OP_REGVAR && !MONO_TYPE_ISSTRUCT (arg_type) && !current->is_volatile && current->interval->range) {
1262                         /* This ensures there is some part of the interval before the use pos */
1263                         g_assert (current->interval->range->from == 0);
1264
1265                         /* Have to split at an use pos so a spill load can be inserted */
1266                         if (current->use_pos) {
1267                                 guint32 pos = GPOINTER_TO_INT (current->use_pos->data);
1268
1269                                 split_interval (cfg, ctx, current, pos);
1270                                 unhandled = g_list_remove (unhandled, current);
1271                                 unhandled = g_list_insert_sorted (unhandled, current->child2, compare_by_interval_start_pos_func);
1272                         }
1273                 }
1274         }
1275
1276         while (unhandled) {
1277             MonoRegallocInterval *current = unhandled->data;
1278                 int pos, reg, max_free_pos;
1279                 gboolean changed;
1280
1281                 unhandled = g_list_delete_link (unhandled, unhandled);
1282
1283                 LSCAN_DEBUG (printf ("Processing R%d: ", current->vreg));
1284                 LSCAN_DEBUG (mono_linterval_print (current->interval));
1285                 LSCAN_DEBUG (printf ("\n"));
1286
1287                 if (!current->interval->range)
1288                         continue;
1289
1290                 /* Happens when splitting intervals */
1291                 if (!current->use_pos)
1292                         continue;
1293
1294                 pos = current->interval->range->from;
1295
1296                 /* Check for intervals in active which expired or inactive */
1297                 changed = TRUE;
1298                 /* FIXME: Optimize this */
1299                 l = active;
1300                 while (l) {
1301                         MonoRegallocInterval *v = l->data;
1302
1303                         next = l->next;
1304                         if (v->interval->last_range->to < pos) {
1305                                 active = g_list_delete_link (active, l);
1306                                 LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", v->vreg));
1307                         } else if (!mono_linterval_covers (v->interval, pos)) {
1308                                 inactive = g_list_append (inactive, v);
1309                                 active = g_list_delete_link (active, l);
1310                                 LSCAN_DEBUG (printf ("\tInterval R%d became inactive\n", v->vreg));
1311                         }
1312                         l = next;
1313                 }
1314
1315                 /* Check for intervals in inactive which are expired or active */
1316                 l = inactive;
1317                 while (l) {
1318                         MonoRegallocInterval *v = l->data;
1319
1320                         next = l->next;
1321                         if (v->interval->last_range->to < pos) {
1322                                 inactive = g_list_delete_link (inactive, l);
1323                                 LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", v->vreg));
1324                         } else if (mono_linterval_covers (v->interval, pos)) {
1325                                 active = g_list_append (active, v);
1326                                 inactive = g_list_delete_link (inactive, l);
1327                                 LSCAN_DEBUG (printf ("\tInterval R%d became active\n", v->vreg));
1328                         }
1329                         l = next;
1330                 }
1331
1332                 /* Find a register for the current interval */
1333                 if (G_UNLIKELY (current->fp)) {
1334                         for (i = MONO_MAX_IREGS; i < MONO_MAX_IREGS + MONO_MAX_FREGS; ++i)
1335                                 if (allocateable [i])
1336                                         free_pos [i] = G_MAXINT32;
1337                                 else
1338                                         free_pos [i] = 0;
1339                 } else {
1340                         for (i = 0; i < MONO_MAX_IREGS; ++i)
1341                                 if (allocateable [i])
1342                                         free_pos [i] = G_MAXINT32;
1343                                 else
1344                                         free_pos [i] = 0;
1345                 }
1346
1347                 for (l = active; l != NULL; l = l->next) {
1348                         MonoRegallocInterval *v = l->data;
1349
1350                         if (v->hreg >= 0) {
1351                                 free_pos [v->hreg] = 0;
1352                                 LSCAN_DEBUG (printf ("\threg %d is busy (R%d)\n", v->hreg, v->vreg));
1353                         }
1354                 }
1355
1356                 for (l = inactive; l != NULL; l = l->next) {
1357                         MonoRegallocInterval *v = l->data;
1358                         gint32 intersect_pos;
1359
1360                         if ((v->hreg >= 0) && (current->fp == v->fp)) {
1361                                 intersect_pos = mono_linterval_get_intersect_pos (current->interval, v->interval);
1362                                 if (intersect_pos != -1) {
1363                                         if (intersect_pos < free_pos [v->hreg])
1364                                                 free_pos [v->hreg] = intersect_pos;
1365                                         LSCAN_DEBUG (printf ("\threg %d becomes free at %x\n", v->hreg, intersect_pos));
1366                                 }
1367                         }
1368                 }
1369
1370                 max_free_pos = -1;
1371                 reg = -1;
1372
1373 #if 0
1374                 /*
1375                  * Arguments should be allocated to the registers they reside in at the start of
1376                  * the method.
1377                  */
1378                 for (i = 0; i < sig->param_count + sig->hasthis; ++i) {
1379                         MonoInst *ins = cfg->args [i];
1380
1381                         g_assert (ins->opcode == OP_REGVAR);
1382                         if (ins->dreg == current->vreg)
1383                                 reg = ins->inst_c0;
1384                 }
1385 #endif
1386
1387                 if (reg == -1) {
1388                         if (G_UNLIKELY (current->fp)) {
1389                                 for (i = MONO_MAX_IREGS; i < MONO_MAX_IREGS + MONO_MAX_FREGS; ++i)
1390                                         if (free_pos [i] > max_free_pos) {
1391                                                 reg = i;
1392                                                 max_free_pos = free_pos [i];
1393                                         }
1394                         } else {
1395                                 for (i = 0; i < MONO_MAX_IREGS; ++i)
1396                                         if (free_pos [i] > max_free_pos) {
1397                                                 reg = i;
1398                                                 max_free_pos = free_pos [i];
1399                                         }
1400                         }
1401
1402                         if (current->preferred_reg != -1) {
1403                                 LSCAN_DEBUG (printf ("\tPreferred register is hreg %d\n", current->preferred_reg));
1404                                 /* FIXME: Add more cases */
1405                                 if (free_pos [current->preferred_reg] >= free_pos [reg]) {
1406                                         reg = current->preferred_reg;
1407                                 } else {
1408 #if 0
1409                                         /*
1410                                          * We have a choice to make: assigning to the preferred reg avoids
1411                                          * a move, while assigning to 'reg' will keep the variable in a
1412                                          * register for longer.
1413                                          */
1414                                         if (free_pos [current->preferred_reg] >= current->interval->range->from)
1415                                                 reg = current->preferred_reg;
1416 #endif
1417                                 }
1418                         }
1419                 }
1420
1421                 g_assert (reg != -1);
1422
1423                 if (!(free_pos [reg] > 0 && free_pos [reg] >= current->interval->range->from) &&
1424                         GPOINTER_TO_INT (current->use_pos->data) <= current->interval->range->from) {
1425                         /*
1426                          * No register is available, and current is needed in a register right now.
1427                          * So free up a register by spilling an interval in active.
1428                          */
1429                         MonoRegallocInterval *to_spill;
1430                         guint32 split_pos;
1431
1432                         g_assert (!current->is_volatile);
1433
1434                         /* Spill the first */
1435                         /* FIXME: Optimize the selection of the interval */
1436                         l = active;
1437                         to_spill = NULL;
1438                         for (l = active; l; l = l->next) {
1439                                 to_spill = l->data;
1440
1441                                 /* Fixed intervals cannot be spilled */
1442                                 if (to_spill->vreg >= MONO_FIRST_VREG)
1443                                         break;
1444                         }
1445                         g_assert (to_spill);
1446
1447                         LSCAN_DEBUG (printf ("\tNo free register found, splitting and spilling R%d\n", to_spill->vreg));
1448                         split_pos = GPOINTER_TO_INT (current->use_pos->data);
1449                         /*
1450                          * Avoid splitting to_spill before the start of current, since
1451                          * its second child, which is added to unhandled would begin before
1452                          * current.
1453                          */
1454                         if (split_pos < current->interval->range->from)
1455                                 split_pos = current->interval->range->from;
1456                         split_interval (cfg, ctx, to_spill, split_pos);
1457                         to_spill->child1->hreg = to_spill->hreg;
1458                         active = g_list_remove (active, to_spill);
1459                         unhandled = g_list_insert_sorted (unhandled, to_spill->child2, compare_by_interval_start_pos_func);
1460                         reg = to_spill->hreg;
1461
1462                         /* Recompute free_pos [reg] */
1463                         free_pos [reg] = G_MAXINT32;
1464                         for (l = active; l != NULL; l = l->next) {
1465                                 MonoRegallocInterval *v = l->data;
1466
1467                                 if (v->hreg == reg) {
1468                                         free_pos [v->hreg] = 0;
1469                                         LSCAN_DEBUG (printf ("\threg %d is busy (R%d)\n", v->hreg, v->vreg));
1470                                 }
1471                         }
1472
1473                         for (l = inactive; l != NULL; l = l->next) {
1474                                 MonoRegallocInterval *v = l->data;
1475                                 gint32 intersect_pos;
1476
1477                                 if ((v->hreg == reg) && (current->fp == v->fp)) {
1478                                         intersect_pos = mono_linterval_get_intersect_pos (current->interval, v->interval);
1479                                         if (intersect_pos != -1) {
1480                                                 if (intersect_pos < free_pos [v->hreg])
1481                                                         free_pos [v->hreg] = intersect_pos;
1482                                                 LSCAN_DEBUG (printf ("\threg %d becomes free at %x\n", v->hreg, intersect_pos));
1483                                         }
1484                                 }
1485                         }
1486                 }
1487
1488                 if (free_pos [reg] > 0 && free_pos [reg] >= current->interval->last_range->to) {
1489                         /* Register available for whole interval */
1490                         current->hreg = reg;
1491                         if (!current->fp)
1492                                 cfg->used_int_regs |= (1 << reg);
1493                         LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg, current->vreg));
1494
1495                         active = g_list_append (active, current);
1496                 }
1497                 else if (free_pos [reg] > 0 && free_pos [reg] >= current->interval->range->from) {
1498                         /*
1499                          * The register is available for some part of the interval.
1500                          * Split the interval, assign the register to the first part of the
1501                          * interval, and save the second part for later processing.
1502                          */
1503                         LSCAN_DEBUG (printf ("\tRegister %d is available until %x, splitting current.\n", reg, free_pos [reg]));
1504                         split_interval (cfg, ctx, current, free_pos [reg]);
1505
1506                         current->child1->hreg = reg;
1507                         if (!current->fp)
1508                                 cfg->used_int_regs |= (1 << reg);
1509                         LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg, current->child1->vreg));
1510                         active = g_list_append (active, current->child1);
1511
1512                         unhandled = g_list_insert_sorted (unhandled, current->child2, compare_by_interval_start_pos_func);
1513                 } else {
1514                         /* No register is available */
1515                         if (GPOINTER_TO_INT (current->use_pos->data) > current->interval->range->from) {
1516                                 /*
1517                                  * The interval is not currently needed in a register. So split it, and
1518                                  * spill the first part to memory, and save the second part for later
1519                                  * processing.
1520                                  */
1521                                 LSCAN_DEBUG (printf ("\tSplitting current at first use pos %x, spilling the first part.\n", GPOINTER_TO_INT (current->use_pos->data)));
1522                                 split_interval (cfg, ctx, current, GPOINTER_TO_INT (current->use_pos->data));
1523                                 unhandled = g_list_insert_sorted (unhandled, current->child2, compare_by_interval_start_pos_func);
1524                         } else {
1525                                 /* Handled previously */
1526                                 g_assert_not_reached ();
1527                         }
1528                 }
1529         }
1530
1531         /*
1532          * The fp registers are numbered from MONO_MAX_IREGS during allocation, but they are
1533          * numbered from 0 in machine code.
1534          */
1535         for (i = 0; i < cfg->next_vreg; ++i) {
1536                 if (ctx->varinfo [i].fp) {
1537                         GSList *children;
1538
1539                         /* Need to process child intervals as well */
1540                         /* This happens rarely so it is not perf critical */
1541                         children = NULL;
1542                         children = g_slist_prepend (children, &ctx->varinfo [i]);
1543                         while (children) {
1544                                 MonoRegallocInterval *interval = children->data;
1545
1546                                 children = g_slist_delete_link (children, children);
1547                                 if (interval->hreg != -1)
1548                                         interval->hreg -= MONO_MAX_IREGS;
1549                                 if (interval->child1)
1550                                         children = g_slist_prepend (children, interval->child1);
1551                                 if (interval->child2)
1552                                         children = g_slist_prepend (children, interval->child2);
1553                         }
1554                 }
1555         }
1556 }
1557
1558 static GSList*
1559 collect_spilled_intervals (MonoRegallocInterval *interval, GSList *list)
1560 {
1561         if ((interval->hreg == -1) && !interval->child1 && interval->interval->range)
1562                 list = g_slist_prepend (list, interval);
1563
1564         if (interval->is_volatile && !interval->interval->range)
1565                 /* Variables which are only referenced by ldaddr */
1566                 list = g_slist_prepend (list, interval);
1567
1568         if (interval->child1) {
1569                 list = collect_spilled_intervals (interval->child1, list);
1570                 list = collect_spilled_intervals (interval->child2, list);
1571         }
1572
1573         return list;
1574 }
1575
1576 static int
1577 alloc_spill_slot (MonoCompile *cfg, guint32 size, guint32 align)
1578 {
1579         guint32 res;
1580
1581         if (size == 0) {
1582                 res = cfg->stack_offset;
1583         } else {
1584                 if (cfg->flags & MONO_CFG_HAS_SPILLUP) {
1585                         cfg->stack_offset += align - 1;
1586                         cfg->stack_offset &= ~(align - 1);
1587                         res = cfg->stack_offset;
1588                         cfg->stack_offset += size;
1589                 } else {
1590                         cfg->stack_offset += align - 1;
1591                         cfg->stack_offset &= ~(align - 1);
1592                         cfg->stack_offset += size;
1593                         res = - cfg->stack_offset;
1594                 }
1595         }
1596
1597         return res;
1598 }
1599
1600 static void
1601 assign_spill_slots (MonoCompile *cfg, MonoRegallocContext *ctx)
1602 {
1603         GSList *spilled_intervals = NULL;
1604         GSList *l;
1605         MonoMethodSignature *sig;
1606         int i;
1607
1608         /* Handle arguments passed on the stack */
1609         sig = mono_method_signature (cfg->method);
1610         for (i = 0; i < sig->param_count + sig->hasthis; ++i) {
1611                 MonoInst *ins = cfg->args [i];
1612                 MonoType *arg_type;
1613
1614                 if (sig->hasthis && (i == 0))
1615                         arg_type = &mono_defaults.object_class->byval_arg;
1616                 else
1617                         arg_type = sig->params [i - sig->hasthis];
1618
1619                 if (MONO_TYPE_ISSTRUCT (arg_type) || (ins->opcode != OP_REGVAR)) {
1620                         g_assert (ins->opcode == OP_REGOFFSET);
1621                         // FIXME: Add a basereg field to varinfo
1622                         // FIXME:
1623                         g_assert (ins->inst_offset != -1);
1624                         ctx->varinfo [ins->dreg].offset = ins->inst_offset;
1625                 }
1626         }
1627
1628         /* Handle a vtype return */
1629         if (!cfg->vret_addr && MONO_TYPE_ISSTRUCT (sig->ret)) {
1630                 MonoInst *ins = cfg->ret;
1631
1632                 ctx->varinfo [ins->dreg].offset = ins->inst_offset;
1633         }
1634
1635         for (i = 0; i < cfg->next_vreg; ++i) {
1636                 spilled_intervals = collect_spilled_intervals (&ctx->varinfo [i], spilled_intervals);
1637         }
1638
1639         LSCAN_DEBUG (printf ("\nSPILL OFFSETS:\n\n"));
1640
1641         for (l = spilled_intervals; l; l = l->next) {
1642                 MonoRegallocInterval *interval = l->data;
1643                 MonoRegallocInterval *parent;
1644
1645                 /*
1646                  * All spilled sub-intervals of a interval must share the stack slot.
1647                  * This is accomplished by storing the stack offset in the original interval
1648                  * and using that offset for all its children.
1649                  */
1650
1651                 for (parent = interval; parent->parent != NULL; parent = parent->parent)
1652                         ;
1653                 if (parent->offset != -1) {
1654                         interval->offset = parent->offset;
1655                 } else if (interval->offset != -1) {
1656                         /* Already allocated (for example, valuetypes as arguments) */
1657                 } else {
1658                         guint32 size, align;
1659
1660                         if (MONO_TYPE_ISSTRUCT (interval->type)) {
1661                                 // FIXME: pinvoke, gsctx
1662                                 // FIXME: Align
1663                                 size = mini_type_stack_size (NULL, interval->type, NULL);
1664                         } else if (interval->fp) {
1665                                 size = sizeof (double);
1666                         } else {
1667                                 size = sizeof (gpointer);
1668                         }
1669
1670                         align = sizeof (gpointer);
1671                         interval->offset = alloc_spill_slot (cfg, size, align);
1672                 }
1673
1674                 for (parent = interval; parent != NULL; parent = parent->parent) {
1675                         if (parent->offset == -1)
1676                                 parent->offset = interval->offset;
1677                 }
1678
1679                 LSCAN_DEBUG (printf ("R%d %d", interval->vreg, interval->offset));
1680                 LSCAN_DEBUG (mono_linterval_print (interval->interval));
1681                 LSCAN_DEBUG (printf ("\n"));
1682         }
1683 }
1684
1685 /**
1686  * order_moves:
1687  *
1688  *   Order the instructions in MOVES so earlier moves don't overwrite the sources of
1689  * later moves.
1690  */
1691 static GSList*
1692 order_moves (MonoCompile *cfg, MonoRegallocContext *ctx, MonoInst **moves, int nmoves)
1693 {
1694         int i, j, niter;
1695         GSList *l;
1696
1697         /*
1698          * Sort the moves so earlier moves don't overwrite the sources of later
1699          * moves.
1700          */
1701         /* FIXME: Do proper cycle detection instead of the current ugly hack */
1702         niter = 0;
1703         for (i = 0; i < nmoves; ++i) {
1704                 gboolean found;
1705
1706                 found = TRUE;
1707                 while (found) {
1708                         found = FALSE;
1709                         for (j = i + 1; j < nmoves; ++j)
1710                                 if (moves [i]->dreg == moves [j]->sreg1) {
1711                                         found = TRUE;
1712                                         break;
1713                                 }
1714                         if (found) {
1715                                 MonoInst *ins;
1716
1717                                 ins = moves [j];
1718                                 moves [j] = moves [i];
1719                                 moves [i] = ins;
1720
1721                                 niter ++;
1722                                 if (niter > nmoves * 2)
1723                                         /* Possible cycle */
1724                                         break;
1725                         }
1726                 }
1727                 if (niter > nmoves * 2)
1728                         break;
1729         }
1730
1731         l = NULL;
1732         if (niter > nmoves * 2) {
1733                 MonoInst *ins;
1734                 int *offsets;
1735
1736                 /*
1737                  * Save all registers to the stack and reload them again.
1738                  * FIXME: Optimize this.
1739                  */
1740
1741                 /* Allocate spill slots */
1742                 offsets = mono_mempool_alloc (cfg->mempool, nmoves * sizeof (int));
1743                 for (i = 0; i < nmoves; ++i) {
1744                         guint32 size = sizeof (gpointer);
1745
1746                         if (cfg->flags & MONO_CFG_HAS_SPILLUP) {
1747                                 cfg->stack_offset += size - 1;
1748                                 cfg->stack_offset &= ~(size - 1);
1749                                 offsets [i] = cfg->stack_offset;
1750                                 cfg->stack_offset += size;
1751                         } else {
1752                                 cfg->stack_offset += size - 1;
1753                                 cfg->stack_offset &= ~(size - 1);
1754                                 cfg->stack_offset += size;
1755                                 offsets [i] = - cfg->stack_offset;
1756                         }
1757                 }
1758
1759                 /* Create stores */
1760                 for (i = 0; i < nmoves; ++i) {
1761                         if (moves [i]->opcode != OP_MOVE)
1762                                 NOT_IMPLEMENTED;
1763                         MONO_INST_NEW (cfg, ins, OP_STORE_MEMBASE_REG);
1764                         ins->sreg1 = moves [i]->sreg1;
1765                         ins->inst_destbasereg = cfg->frame_reg;
1766                         ins->inst_offset = offsets [i];
1767
1768                         l = g_slist_append_mempool (cfg->mempool, l, ins);
1769                         g_hash_table_insert (ctx->spill_ins, ins, ins);
1770                 }
1771
1772                 /* Create loads */
1773                 for (i = 0; i < nmoves; ++i) {
1774                         if (moves [i]->opcode != OP_MOVE)
1775                                 NOT_IMPLEMENTED;
1776                         MONO_INST_NEW (cfg, ins, OP_LOAD_MEMBASE);
1777                         ins->dreg = moves [i]->dreg;
1778                         ins->inst_basereg = cfg->frame_reg;
1779                         ins->inst_offset = offsets [i];
1780
1781                         l = g_slist_append_mempool (cfg->mempool, l, ins);
1782                         g_hash_table_insert (ctx->spill_ins, ins, ins);
1783                 }
1784
1785                 return l;
1786         } else {
1787                 for (i = 0; i < nmoves; ++i)
1788                         l = g_slist_append_mempool (cfg->mempool, l, moves [i]);
1789
1790                 return l;
1791         }
1792 }
1793
1794 /**
1795  * add_spill_code:
1796  *
1797  *   Add spill loads and stores to the IR at the locations where intervals were split.
1798  */
1799 static void
1800 add_spill_code (MonoCompile *cfg, MonoRegallocContext *ctx)
1801 {
1802         MonoBasicBlock *bb;
1803         MonoInst *ins, *prev, *store, *load, *move, *insert_after;
1804         GSList *spill_list, *l, *ins_to_add, *moves_to_add;
1805         MonoRegallocInterval *child1, *child2;
1806         int pos, pos_interval, pos_interval_limit;
1807         MonoBasicBlock *out_bb;
1808         int i, bb_count, from_pos, to_pos, iter;
1809         gboolean after_last_ins, add_at_head;
1810
1811         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1812                 if (cfg->verbose_level > 1)
1813                         printf ("\nREGALLOC-ADD SPILL CODE %d (DFN 0x%x):\n", bb->block_num, bb->dfn);
1814
1815                 /* First pass: Add spill loads/stores to the IR */
1816                 pos = (bb->dfn << 16) + INS_POS_INTERVAL;
1817                 prev = NULL;
1818                 after_last_ins = FALSE;
1819                 for (ins = bb->code; !after_last_ins;) {
1820                         if (ins == NULL) {
1821                                 after_last_ins = TRUE;
1822                         } else if (g_hash_table_lookup (ctx->spill_ins, ins)) {
1823                                 /* Spill instruction added by an earlier bblock */
1824                                 /* No need to increase pos */
1825
1826                                 if (G_UNLIKELY (cfg->verbose_level > 1)) {
1827                                         printf (" <spill ins>\n");
1828                                 }
1829
1830                                 prev = ins;
1831                                 ins = ins->next;
1832                                 continue;
1833                         }
1834
1835                         if (!g_hash_table_lookup (ctx->split_position_set, GUINT_TO_POINTER (pos))) {
1836                                 /* No split position at this instruction */
1837                                 pos_interval_limit = 0;
1838                                 pos += INS_POS_INTERVAL;
1839                         } else {
1840                                 pos_interval_limit = INS_POS_INTERVAL;
1841                         }
1842
1843                         for (pos_interval = 0; pos_interval < pos_interval_limit; ++pos_interval) {
1844                                 spill_list = g_hash_table_lookup (ctx->split_positions, GUINT_TO_POINTER (pos));
1845                                 /* Insert stores first, then loads so registers don't get overwritten */
1846                                 for (iter = 0; iter < 2; ++iter) {
1847                                         for (l = spill_list; l; l = l->next) {
1848                                                 MonoRegallocInterval *interval = l->data;
1849
1850                                                 /* The childs might be split */
1851                                                 if (interval->child1->child1)
1852                                                         child1 = child_at (interval->child1, pos - pos_interval);
1853                                                 else
1854                                                         child1 = interval->child1;
1855                                                 if (pos < interval->child2->interval->range->from)
1856                                                         /* Happens when volatile intervals are split */
1857                                                         continue;
1858                                                 child2 = child_at (interval->child2, pos);
1859
1860                                                 if ((child1->hreg == -1) && (child2->hreg == -1))
1861                                                         /*
1862                                                          * Happens when an interval is split, then the first child
1863                                                          * is split again.
1864                                                          */
1865                                                         continue;
1866
1867                                                 // FIXME: Why is !is_volatile needed ?
1868                                                 // It seems to fail when the same volatile var is a source and a
1869                                                 // destination of the same instruction
1870                                                 if ((iter == 0) && (child1->hreg != -1) && (child2->hreg != -1) && !interval->is_volatile) {
1871                                                         int offset;
1872
1873                                                         /*
1874                                                          * This is complex situation: the vreg is expected to be in
1875                                                          * child1->hreg before the instruction, and in child2->hreg
1876                                                          * after the instruction. We can't insert a move before,
1877                                                          * because that could overwrite the input regs of the
1878                                                          * instruction, and we can't insert a move after, since the
1879                                                          * instruction could overwrite the source reg of the move.
1880                                                          * Instead, we insert a store before the instruction, and a
1881                                                          * load afterwards.
1882                                                          * FIXME: Optimize child1->hreg == child2->hreg
1883                                                          */
1884                                                         offset = alloc_spill_slot (cfg, sizeof (gpointer), sizeof (gpointer));
1885
1886                                                         NEW_STORE_MEMBASE (cfg, store, mono_type_to_store_membase (cfg, interval->type), cfg->frame_reg, offset, child1->hreg);
1887
1888                                                         if (prev)
1889                                                                 prev->next = store;
1890                                                         else
1891                                                                 bb->code = store;
1892                                                         store->next = ins;
1893                                                         prev = store;
1894                                                         g_hash_table_insert (ctx->spill_ins, store, store);
1895
1896                                                         NEW_LOAD_MEMBASE (cfg, load, mono_type_to_load_membase (cfg, interval->type), child2->hreg, cfg->frame_reg, offset);
1897
1898                                                         insert_after_ins (bb, load, ins);
1899                                                         g_hash_table_insert (ctx->spill_ins, load, load);
1900
1901                                                         LSCAN_DEBUG (printf (" Spill store/load added for R%d (R%d -> R%d) at %x\n", interval->vreg, child1->vreg, child2->vreg, pos));
1902                                                 } else if ((iter == 0) && (child1->hreg != -1) && (child2->hreg == -1)) {
1903                                                         g_assert (child2->offset != -1);
1904
1905                                                         NEW_STORE_MEMBASE (cfg, store, mono_type_to_store_membase (cfg, interval->type), cfg->frame_reg, child2->offset, child1->hreg);
1906
1907                                                         if (prev)
1908                                                                 prev->next = store;
1909                                                         else
1910                                                                 bb->code = store;
1911                                                         store->next = ins;
1912                                                         prev = store;
1913                                                         g_hash_table_insert (ctx->spill_ins, store, store);
1914
1915                                                         LSCAN_DEBUG (printf (" Spill store added for R%d (R%d -> R%d) at %x\n", interval->vreg, child1->vreg, child2->vreg, pos));
1916                                                 } else if ((iter == 1) && (child1->hreg == -1) && (child2->hreg != -1)) {
1917                                                         g_assert (child1->offset != -1);
1918                                                         NEW_LOAD_MEMBASE (cfg, load, mono_type_to_load_membase (cfg, interval->type), child2->hreg, cfg->frame_reg, child1->offset);
1919
1920                                                         if (prev)
1921                                                                 prev->next = load;
1922                                                         else
1923                                                                 bb->code = load;
1924                                                         load->next = ins;
1925                                                         prev = load;
1926                                                         g_hash_table_insert (ctx->spill_ins, load, load);
1927
1928                                                         LSCAN_DEBUG (printf (" Spill load added for R%d (R%d -> R%d) at %x\n", interval->vreg, child1->vreg, child2->vreg, pos));
1929                                                 }
1930                                         }
1931                                 }
1932
1933                                 pos ++;
1934                         }
1935
1936                         if (G_UNLIKELY (cfg->verbose_level > 1))
1937                                 if (ins)
1938                                         mono_print_ins (ins);
1939
1940                         prev = ins;
1941
1942                         if (ins)
1943                                 ins = ins->next;
1944                 }
1945
1946                 /* Second pass: Resolve data flow */
1947                 for (bb_count = 0; bb_count < bb->out_count; ++bb_count) {
1948                         out_bb = bb->out_bb [bb_count];
1949
1950                         if (!out_bb->live_in_set)
1951                                 /* Exception handling block */
1952                                 continue;
1953
1954                         from_pos = (bb->dfn << 16) + 0xffff;
1955                         to_pos = (out_bb->dfn << 16);
1956
1957                         ins_to_add = NULL;
1958                         for (i = 0; i < cfg->next_vreg; ++i) {
1959                                 MonoRegallocInterval *interval = &ctx->varinfo [i];
1960
1961                                 if (mono_bitset_test_fast (out_bb->live_in_set, i) && mono_linterval_covers (interval->interval, from_pos) && mono_linterval_covers (interval->interval, to_pos)) {
1962                                         child1 = child_at (interval, from_pos);
1963                                         child2 = child_at (interval, to_pos);
1964                                         if (child1 != child2) {
1965                                                 if ((child1->hreg != -1) && (child2->hreg == -1)) {
1966                                                         LSCAN_DEBUG (printf (" Add store for R%d (R%d -> R%d) at BB%d -> BB%d [%x - %x]\n", interval->vreg, child1->vreg, child2->vreg, bb->block_num, out_bb->block_num, from_pos, to_pos));
1967                                                         NEW_STORE_MEMBASE (cfg, store, mono_type_to_store_membase (cfg, interval->type), cfg->frame_reg, child2->offset, child1->hreg);
1968                                                         ins_to_add = g_slist_prepend_mempool (cfg->mempool, ins_to_add, store);
1969                                                         g_hash_table_insert (ctx->spill_ins, store, store);
1970                                                 } else if ((child1->hreg != -1) && (child2->hreg != -1)) {
1971                                                         if (child1->hreg != child2->hreg) {
1972                                                                 LSCAN_DEBUG (printf (" Add move for R%d (R%d -> R%d) at BB%d -> BB%d [%x - %x]\n", interval->vreg, child1->vreg, child2->vreg, bb->block_num, out_bb->block_num, from_pos, to_pos));
1973                                                                 NEW_UNALU (cfg, move, interval->fp ? OP_FMOVE : OP_MOVE, child2->hreg, child1->hreg);
1974                                                                 ins_to_add = g_slist_prepend_mempool (cfg->mempool, ins_to_add, move);
1975                                                                 g_hash_table_insert (ctx->spill_ins, move, move);
1976                                                         }
1977                                                 } else if ((child1->hreg == -1) && (child2->hreg != -1)) {
1978                                                         LSCAN_DEBUG (printf (" Add load for R%d (R%d -> R%d) at BB%d -> BB%d [%x - %x]\n", interval->vreg, child1->vreg, child2->vreg, bb->block_num, out_bb->block_num, from_pos, to_pos));
1979                                                         NEW_LOAD_MEMBASE (cfg, load, mono_type_to_load_membase (cfg, interval->type), child2->hreg, cfg->frame_reg, child1->offset);
1980                                                         ins_to_add = g_slist_prepend_mempool (cfg->mempool, ins_to_add, load);
1981                                                         g_hash_table_insert (ctx->spill_ins, load, load);
1982                                                 } else {
1983                                                         g_assert (child1->offset == child2->offset);
1984                                                 }
1985                                         }
1986                                 }
1987                         }
1988
1989                         if (bb->out_count == 1) {
1990                                 add_at_head = TRUE;
1991                         } else if (out_bb->in_count == 1) {
1992                                 add_at_head = FALSE;
1993                         } else {
1994                                 // FIXME: Split critical edges
1995                                 add_at_head = TRUE;
1996                                 NOT_IMPLEMENTED;
1997                         }
1998
1999                         insert_after = NULL;
2000
2001                         if (ins_to_add) {
2002                                 MonoInst **moves;
2003                                 int nmoves;
2004
2005                                 /*
2006                                  * Emit spill instructions in such a way that instructions don't
2007                                  * overwrite the source registers of instructions coming after them.
2008                                  */
2009                                 /* Simply emit stores, then moves then loads */
2010                                 for (l = ins_to_add; l; l = l->next) {
2011                                         MonoInst *ins = l->data;
2012
2013                                         if (MONO_IS_STORE_MEMBASE (ins)) {
2014                                                 if (add_at_head) {
2015                                                         mono_add_ins_to_end (bb, ins);
2016                                                 } else {
2017                                                         insert_after_ins (out_bb, ins, insert_after);
2018                                                         insert_after = ins;
2019                                                 }
2020                                         }
2021                                 }
2022
2023                                 /* Collect the moves */
2024                                 nmoves = 0;
2025                                 for (l = ins_to_add; l; l = l->next) {
2026                                         MonoInst *ins = l->data;
2027
2028                                         if (MONO_IS_MOVE (ins))
2029                                                 nmoves ++;
2030                                 }
2031                                 moves = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoInst*) * nmoves);
2032                                 nmoves = 0;
2033                                 for (l = ins_to_add; l; l = l->next) {
2034                                         MonoInst *ins = l->data;
2035
2036                                         if (MONO_IS_MOVE (ins))
2037                                                 moves [nmoves ++] = ins;
2038                                 }
2039
2040                                 moves_to_add = order_moves (cfg, ctx, moves, nmoves);
2041
2042                                 for (l = moves_to_add; l; l = l->next) {
2043                                         MonoInst *ins = l->data;
2044
2045                                         if (add_at_head) {
2046                                                 mono_add_ins_to_end (bb, ins);
2047                                         } else {
2048                                                 insert_after_ins (out_bb, ins, insert_after);
2049                                                 insert_after = ins;
2050                                         }
2051                                 }
2052
2053                                 for (l = ins_to_add; l; l = l->next) {
2054                                         MonoInst *ins = l->data;
2055
2056                                         if (MONO_IS_LOAD_MEMBASE (ins)) {
2057                                                 if (add_at_head) {
2058                                                         mono_add_ins_to_end (bb, ins);
2059                                                 } else {
2060                                                         insert_after_ins (out_bb, ins, insert_after);
2061                                                         insert_after = ins;
2062                                                 }
2063                                         }
2064                                 }
2065                         }
2066                 }
2067         }
2068 }
2069
2070 /*
2071  * rewrite_code:
2072  *
2073  *   Replace references to vregs with their assigned physical registers or spill
2074  * locations.
2075  */
2076 static void
2077 rewrite_code (MonoCompile *cfg, MonoRegallocContext *ctx)
2078 {
2079         MonoBasicBlock *bb;
2080         MonoInst *ins, *prev;
2081         int pos;
2082
2083         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
2084                 if (cfg->verbose_level > 1)
2085                         printf ("\nREGALLOC-REWRITE BLOCK %d:\n", bb->block_num);
2086
2087                 pos = (bb->dfn << 16);
2088                 prev = NULL;
2089                 for (ins = bb->code; ins; ins = ins->next) {
2090                         const char *spec = INS_INFO (ins->opcode);
2091                         pos += INS_POS_INTERVAL;
2092
2093                         if (G_UNLIKELY (cfg->verbose_level > 1))
2094                                 mono_print_ins (ins);
2095
2096                         if (g_hash_table_lookup (ctx->spill_ins, ins)) {
2097                                 /*
2098                                  * This instruction was added after liveness info was computed, and thus
2099                                  * screws up the pos calculation. The instruction already uses hregs.
2100                                  */
2101                                 pos -= INS_POS_INTERVAL;
2102                                 prev = ins;
2103                                 continue;
2104                         }
2105
2106                         /* FIXME: */
2107                         if (ins->opcode == OP_NOP)
2108                                 continue;
2109
2110                         if (ins->opcode == OP_LDADDR) {
2111                                 MonoRegallocInterval *l = child_at (&ctx->varinfo [ins->dreg], pos + INS_POS_DEF);
2112                                 MonoInst *var = ins->inst_p0;
2113                                 MonoInst *move;
2114
2115                                 g_assert (ctx->varinfo [var->dreg].hreg == -1);
2116                                 g_assert (ctx->varinfo [var->dreg].offset != -1);
2117
2118                                 if (ctx->varinfo [var->dreg].offset != 0) {
2119                                         /*
2120                                          * The ADD_IMM does not satisfy register constraints on x86/amd64.
2121                                          */
2122                                         MONO_INST_NEW (cfg, move, OP_MOVE);
2123                                         move->dreg = l->hreg;
2124                                         move->sreg1 = cfg->frame_reg;
2125
2126                                         if (prev == NULL)
2127                                                 bb->code = move;
2128                                         else
2129                                                 prev->next = move;
2130
2131                                         move->next = ins;
2132                                         ins->opcode = OP_ADD_IMM;
2133                                         ins->dreg = l->hreg;
2134                                         ins->sreg1 = l->hreg;
2135                                         ins->inst_imm = ctx->varinfo [var->dreg].offset;
2136                                 } else {
2137                                         ins->opcode = OP_MOVE;
2138                                         ins->dreg = l->hreg;
2139                                         ins->sreg1 = cfg->frame_reg;
2140                                 }
2141                                 spec = INS_INFO (OP_NOP);
2142                         }
2143
2144                         if (spec [MONO_INST_DEST] != ' ') {
2145                                 if (MONO_IS_STORE_MEMBASE (ins)) {
2146                                         MonoRegallocInterval *l = child_at (&ctx->varinfo [ins->dreg], pos + INS_POS_USE);
2147                                         g_assert (l->hreg != -1);
2148                                         ins->dreg = l->hreg;
2149                                 } else {
2150                                         MonoRegallocInterval *l = child_at (&ctx->varinfo [ins->dreg], pos + INS_POS_DEF);
2151                                         g_assert (l->hreg != -1);
2152                                         ins->dreg = l->hreg;
2153                                 }
2154                         }
2155                         if (spec [MONO_INST_SRC1] != ' ') {
2156                                 MonoRegallocInterval *l = child_at (&ctx->varinfo [ins->sreg1], pos + INS_POS_USE);
2157                                 g_assert (l->hreg != -1);
2158                                 ins->sreg1 = l->hreg;
2159                         }
2160                         if (spec [MONO_INST_SRC2] != ' ') {
2161                                 MonoRegallocInterval *l = child_at (&ctx->varinfo [ins->sreg2], pos + INS_POS_USE);
2162                                 g_assert (l->hreg != -1);
2163                                 ins->sreg2 = l->hreg;
2164                         }
2165
2166                         if (cfg->verbose_level > 1)
2167                                 mono_print_ins_index (1, ins);
2168
2169                         prev = ins;
2170                 }
2171         }
2172 }
2173
2174 static MonoRegallocContext*
2175 regalloc_ctx_create (MonoCompile *cfg)
2176 {
2177         MonoRegallocContext *ctx;
2178         int i;
2179
2180         ctx = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRegallocContext));
2181         ctx->cfg = cfg;
2182         ctx->varinfo = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRegallocInterval) * cfg->next_vreg);
2183         ctx->num_intervals = cfg->next_vreg;
2184         for (i = 0; i < cfg->next_vreg; ++i) {
2185                 MonoInst *var;
2186
2187                 ctx->varinfo [i].vreg = i;
2188                 ctx->varinfo [i].hreg = -1;
2189                 ctx->varinfo [i].offset = -1;
2190                 ctx->varinfo [i].preferred_reg = -1;
2191
2192                 if (i >= MONO_MAX_IREGS && i < MONO_MAX_IREGS + MONO_MAX_FREGS)
2193                         ctx->varinfo [i].fp = TRUE;
2194
2195                 var = get_vreg_to_inst (cfg, i);
2196                 if (var && (var != cfg->ret) && (var->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
2197                         ctx->varinfo [i].is_volatile = TRUE;
2198                 }
2199                 if (var)
2200                         ctx->varinfo [i].type = var->inst_vtype;
2201                 else
2202                         ctx->varinfo [i].type = sizeof (gpointer) == 8 ? &mono_defaults.int64_class->byval_arg : &mono_defaults.int_class->byval_arg;
2203         }
2204
2205         ctx->split_positions = g_hash_table_new (NULL, NULL);
2206         ctx->split_position_set = g_hash_table_new (NULL, NULL);
2207         ctx->spill_ins = g_hash_table_new (NULL, NULL);
2208
2209         return ctx;
2210 }
2211
2212 void
2213 mono_global_regalloc (MonoCompile *cfg)
2214 {
2215         MonoRegallocContext *ctx;
2216
2217         mono_arch_fill_argument_info (cfg);
2218
2219         /* This could create vregs, so it has to come before ctx_create */
2220         handle_reg_constraints (cfg);
2221
2222         ctx = regalloc_ctx_create (cfg);
2223
2224         collect_fp_vregs (cfg, ctx);
2225
2226         analyze_liveness (cfg, ctx);
2227
2228         linear_scan (cfg, ctx);
2229
2230         mono_arch_allocate_vars (cfg);
2231
2232         assign_spill_slots (cfg, ctx);
2233
2234         add_spill_code (cfg, ctx);
2235
2236         rewrite_code (cfg, ctx);
2237 }
2238
2239 #else
2240
2241 void
2242 mono_global_regalloc (MonoCompile *cfg)
2243 {
2244         NOT_IMPLEMENTED;
2245 }
2246
2247 #endif