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