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