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