2 * regalloc2.c: Global Register Allocator
5 * Zoltan Varga (vargaz@gmail.com)
7 * (C) 2007 Novell, Inc.
12 #include <mono/metadata/debug-helpers.h>
13 #include <mono/metadata/mempool-internals.h>
15 /* Disable for now to save space */
16 #undef MONO_ARCH_ENABLE_GLOBAL_RA
18 #ifdef MONO_ARCH_ENABLE_GLOBAL_RA
23 * This allocator is based on the paper
24 * "Linear Scan Register Allocation for the Java HotSpot Client Compiler"
25 * by Christian Wimmer.
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
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.
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
55 typedef struct MonoRegallocInterval {
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
64 * Hard register assigned to this interval, -1 if no register is assigned or the
65 * interval is spilled.
70 * The actual interval data
72 MonoLiveInterval *interval;
75 * Split children of this interval. NULL if the interval is not split.
77 struct MonoRegallocInterval *child1, *child2;
80 * List of use positions, each position is identified by (bb->dfn << 16) + ins_pos
81 * The list is sorted by increasing position.
86 * The offset relative to the frame pointer where this interval is spilled.
91 * If we are a split child of an interval, this points to our parent
93 struct MonoRegallocInterval *parent;
96 * Whenever vreg is an fp vreg
101 * Whenever the variable is volatile
103 guint is_volatile : 1;
106 * The exact type of the variable
111 * The register where this interval should be allocated
114 } MonoRegallocInterval;
116 typedef struct MonoRegallocContext {
118 MonoRegallocInterval *varinfo;
121 * Maps ins pos -> GSList of intervals split at that pos.
123 GHashTable *split_positions;
125 * Used to avoid lookups in split_positions for every position.
127 GHashTable *split_position_set;
129 * Contains MonoInst's representing spill loads/stores
131 GHashTable *spill_ins;
132 } MonoRegallocContext;
138 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
139 #define MONO_FIRST_VREG (MONO_MAX_IREGS+MONO_MAX_FREGS)
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.
151 #define INS_POS_USE 0
152 #define INS_POS_CLOB 1
153 #define INS_POS_DEF 2
154 #define INS_POS_SPILL 3
157 * Should use 16 so liveness ranges are easier to read, but that would overflow
160 #define INS_POS_INTERVAL 8
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)))
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]))
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')
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.
180 #define USE_POS_BASE(ins_pos) ((ins_pos) & ~(INS_POS_INTERVAL - 1))
182 #define USE_POS_IS_DEF(ins_pos) ((ins_pos) & INS_POS_DEF)
185 create_move (MonoCompile *cfg, int dreg, int sreg)
189 MONO_INST_NEW (cfg, ins, OP_MOVE);
197 create_fp_move (MonoCompile *cfg, int dreg, int sreg)
201 MONO_INST_NEW (cfg, ins, OP_FMOVE);
209 emit_move (MonoCompile *cfg, int dreg, int sreg, MonoInst *insert_after)
211 MonoInst *ins = create_move (cfg, dreg, sreg);
213 mono_bblock_insert_after_ins (cfg->cbb, insert_after, ins);
217 emit_fp_move (MonoCompile *cfg, int dreg, int sreg, MonoInst *insert_after)
219 MonoInst *ins = create_fp_move (cfg, dreg, sreg);
221 mono_bblock_insert_after_ins (cfg->cbb, insert_after, ins);
225 emit_nop (MonoCompile *cfg, MonoInst *insert_after)
229 MONO_INST_NEW (cfg, ins, OP_NOP);
231 mono_bblock_insert_after_ins (cfg->cbb, insert_after, ins);
235 * handle_reg_constraints:
237 * Rewrite the IR so it satisfies the register constraints of the architecture.
240 handle_reg_constraints (MonoCompile *cfg)
242 MonoMethodSignature *sig;
246 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
248 MonoInst *prev = NULL;
250 if (cfg->verbose_level > 1) mono_print_bb (bb, "BEFORE HANDLE-REG-CONSTRAINTS ");
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;
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]);
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])) {
267 g_assert_not_reached ();
270 if (spec [MONO_INST_CLOB] == 'c') {
271 MonoCallInst *call = (MonoCallInst*)ins;
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.
278 for (list = call->out_ireg_args; list; list = list->next) {
283 regpair = (guint32)(gssize)(list->data);
284 hreg = regpair >> 24;
285 reg = regpair & 0xffffff;
287 move = create_move (cfg, hreg, reg);
288 mono_bblock_insert_after_ins (bb, prev, move);
292 for (list = call->out_freg_args; list; list = list->next) {
297 regpair = (guint32)(gssize)(list->data);
298 hreg = regpair >> 24;
299 reg = regpair & 0xffffff;
301 move = create_fp_move (cfg, hreg + MONO_MAX_IREGS, reg);
302 mono_bblock_insert_after_ins (bb, prev, move);
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);
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);
316 ins->sreg2 = new_sreg2;
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);
322 emit_move (cfg, ins->dreg, ins->sreg1, prev);
323 ins->sreg1 = ins->dreg;
326 if (dest_sreg1 != -1) {
327 emit_move (cfg, dest_sreg1, ins->sreg1, prev);
328 ins->sreg1 = dest_sreg1;
331 if (dest_sreg2 != -1) {
332 emit_move (cfg, dest_sreg2, ins->sreg2, prev);
333 ins->sreg2 = dest_sreg2;
336 if (dest_sreg3 != -1) {
337 emit_move (cfg, dest_sreg3, ins->sreg3, prev);
338 ins->sreg3 = dest_sreg3;
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;
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;
354 * Add a dummy instruction after each definition of a volatile vreg, this is
355 * needed by the code in decompose_volatile_intervals ().
357 if (get_vreg_to_inst (cfg, ins->dreg) && (get_vreg_to_inst (cfg, ins->dreg)->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
364 sig = mono_method_signature (cfg->method);
366 /* Add move of arguments */
368 * FIXME: Maybe this should be done by the allocator.
370 if (bb == cfg->bb_entry) {
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);
380 for (i = 0; i < sig->param_count + sig->hasthis; ++i) {
383 if (sig->hasthis && (i == 0))
384 arg_type = &mono_defaults.object_class->byval_arg;
386 arg_type = sig->params [i - sig->hasthis];
388 // FIXME: vtypes in registers (pass + return)
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);
395 emit_move (cfg, ins->dreg, ins->inst_c0, prev);
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;
409 hreg = cfg->ret->inst_c0;
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);
415 ins = create_move (cfg, hreg, cfg->ret->dreg);
416 mono_add_ins_to_end (bb, ins);
420 if (cfg->verbose_level > 1) mono_print_bb (bb, "AFTER HANDLE-REG-CONSTRAINTS ");
423 mono_verify_cfg (cfg);
429 * Set varinfo->fp for all float vregs
432 collect_fp_vregs (MonoCompile *cfg, MonoRegallocContext *ctx)
436 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
439 MONO_BB_FOR_EACH_INS (bb, ins) {
440 const char *spec = ins_get_spec (ins->opcode);
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;
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;
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;
467 #define LIVENESS_DEBUG(a) do { if (cfg->verbose_level > 2) { a; } } while (0)
469 #define LIVENESS_DEBUG(a)
472 // #define DEBUG_LIVENESS 1
474 G_GNUC_UNUSED static void
475 mono_bitset_print (MonoBitSet *set)
480 for (i = 0; i < mono_bitset_size (set); i++) {
482 if (mono_bitset_test (set, i))
490 update_gen_kill_set (MonoCompile *cfg, MonoRegallocContext *ctx, MonoBasicBlock *bb, MonoInst *ins)
492 const char *spec = INS_INFO (ins->opcode);
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);
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);
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);
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);
522 mono_bitset_set_fast (bb->kill_set, ins->dreg);
528 compute_gen_kill_sets (MonoCompile *cfg, MonoRegallocContext *ctx)
530 int i, max_vars = cfg->next_vreg;
534 bitsize = mono_bitset_alloc_size (max_vars, 0);
535 mem = mono_mempool_alloc0 (cfg->mempool, cfg->num_bblocks * bitsize * 3);
537 for (i = 0; i < cfg->num_bblocks; ++i) {
538 MonoBasicBlock *bb = cfg->bblocks [i];
540 bb->gen_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
542 bb->kill_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
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);
550 for (i = 0; i < cfg->num_bblocks; ++i) {
551 MonoBasicBlock *bb = cfg->bblocks [i];
553 #ifdef DEBUG_LIVENESS
557 MONO_BB_FOR_EACH_INS (bb, ins)
558 update_gen_kill_set (cfg, ctx, bb, ins);
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);
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);
571 if (cfg->ret && cfg->ret->opcode == OP_REGVAR) {
572 int hreg = cfg->ret->inst_c0;
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);
581 compute_live_in_out_sets (MonoCompile *cfg, MonoRegallocContext *ctx)
583 MonoBitSet *old_live_out_set;
584 int i, j, max_vars = cfg->next_vreg;
586 gboolean *in_worklist;
587 MonoBasicBlock **worklist;
592 bitsize = mono_bitset_alloc_size (max_vars, 0);
593 mem = mono_mempool_alloc0 (cfg->mempool, cfg->num_bblocks * bitsize);
595 old_live_out_set = mono_bitset_new (max_vars, 0);
596 in_worklist = g_new0 (gboolean, cfg->num_bblocks + 1);
598 worklist = g_new (MonoBasicBlock *, cfg->num_bblocks + 1);
602 * This is a backward dataflow analysis problem, so we process blocks in
603 * decreasing dfn order, this speeds up the iteration.
605 for (i = 0; i < cfg->num_bblocks; i ++) {
606 MonoBasicBlock *bb = cfg->bblocks [i];
608 worklist [l_end ++] = bb;
609 in_worklist [bb->dfn] = TRUE;
615 MonoBasicBlock *bb = worklist [--l_end];
616 MonoBasicBlock *out_bb;
619 in_worklist [bb->dfn] = FALSE;
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);
626 for (j = 0; j < bb->out_count; ++j)
627 printf ("BB%d ", bb->out_bb [j]->block_num);
632 if (bb->out_count == 0)
637 if (!bb->live_in_set) {
638 /* First pass over this bblock */
643 mono_bitset_copyto_fast (bb->live_out_set, old_live_out_set);
646 for (j = 0; j < bb->out_count; j++) {
647 out_bb = bb->out_bb [j];
649 if (!out_bb->live_in_set) {
650 out_bb->live_in_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
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);
658 mono_bitset_union_fast (bb->live_out_set, out_bb->live_in_set);
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);
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);
670 for (j = 0; j < bb->in_count; j++) {
671 MonoBasicBlock *in_bb = bb->in_bb [j];
673 * Some basic blocks do not seem to be in the
674 * cfg->bblocks array...
676 if (in_bb->gen_set && !in_worklist [in_bb->dfn]) {
677 #ifdef DEBUG_LIVENESS
678 printf ("\tADD: %d\n", in_bb->block_num);
681 * Put the block at the top of the stack, so it
682 * will be processed right away.
684 worklist [l_end ++] = in_bb;
685 in_worklist [in_bb->dfn] = TRUE;
691 #ifdef DEBUG_LIVENESS
692 printf ("IT: %d %d.\n", cfg->num_bblocks, out_iter);
695 mono_bitset_free (old_live_out_set);
698 g_free (in_worklist);
700 /* Compute live_in_set for bblocks skipped earlier */
701 for (i = 0; i < cfg->num_bblocks; ++i) {
702 MonoBasicBlock *bb = cfg->bblocks [i];
704 if (!bb->live_in_set) {
705 bb->live_in_set = mono_bitset_mem_new (mem, max_vars, MONO_BITSET_DONT_FREE);
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);
714 #ifdef DEBUG_LIVENESS
715 for (i = cfg->num_bblocks - 1; i >= 0; i--) {
716 MonoBasicBlock *bb = cfg->bblocks [i];
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);
726 static MonoLiveInterval*
727 get_var_interval (MonoCompile *cfg, MonoRegallocContext *ctx, int idx)
729 MonoLiveInterval *interval = ctx->varinfo [idx].interval;
732 interval = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoLiveInterval));
733 ctx->varinfo [idx].interval = interval;
738 update_liveness (MonoCompile *cfg, MonoRegallocContext *ctx, MonoInst *ins, int inst_num, gint32 *last_use)
740 const char *spec = INS_INFO (ins->opcode);
743 LIVENESS_DEBUG (printf ("\t%x: ", inst_num); mono_print_ins (ins));
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;
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) {
757 * Avoid a hole in the liveness range, since the allocation code
758 * could think the register is free there.
760 mono_linterval_add_range (ctx->cfg, get_var_interval (cfg, ctx, ins->dreg), inst_num, last_use [ins->dreg]);
762 mono_linterval_add_range (ctx->cfg, get_var_interval (cfg, ctx, ins->dreg), inst_num + INS_POS_DEF, last_use [ins->dreg]);
764 last_use [ins->dreg] = 0;
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));
770 spec = INS_INFO (ins->opcode);
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);
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));
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));
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) {
793 * Propagate preferred vregs. This works because instructions are
794 * processed in reverse order.
796 ctx->varinfo [ins->sreg1].preferred_reg = ctx->varinfo [ins->dreg].preferred_reg;
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;
808 ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
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;
818 ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
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;
827 ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
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);
835 if (ins_get_spec (ins->opcode)[MONO_INST_CLOB] == 'c') {
836 MonoCallInst *call = (MonoCallInst*)ins;
839 for (list = call->out_ireg_args; list; list = list->next) {
842 regpair = (guint32)(gssize)(list->data);
843 sreg = regpair >> 24;
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;
849 ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
852 for (list = call->out_freg_args; list; list = list->next) {
855 regpair = (guint32)(gssize)(list->data);
856 sreg = (regpair >> 24) + MONO_MAX_IREGS;
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;
862 ctx->varinfo [sreg].use_pos = g_slist_prepend_mempool (ctx->cfg->mempool, ctx->varinfo [sreg].use_pos, GINT_TO_POINTER (inst_num));
867 if (ins_get_spec (ins->opcode)[MONO_INST_CLOB]) {
868 char clob = ins_get_spec (ins->opcode)[MONO_INST_CLOB];
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);
879 int clob_reg = MONO_ARCH_INST_FIXED_REG (clob);
882 mono_linterval_add_range (ctx->cfg, get_var_interval (cfg, ctx, clob_reg), inst_num + INS_POS_CLOB, inst_num + INS_POS_CLOB);
890 * Compute liveness intervals for all vregs.
893 compute_intervals (MonoCompile *cfg, MonoRegallocContext *ctx)
895 int bnum, idx, i, j, nins, rem, max, max_vars, block_from, block_to, pos, reverse_len;
899 max_vars = cfg->next_vreg;
900 last_use = g_new0 (gint32, max_vars);
903 reverse = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * reverse_len);
906 * Process bblocks in reverse order, so the addition of new live ranges
907 * to the intervals is faster.
909 for (bnum = cfg->num_bblocks - 1; bnum >= 0; --bnum) {
910 MonoBasicBlock *bb = cfg->bblocks [bnum];
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);
918 block_to = (bb->dfn << 16) + 0xffff;
920 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb->block_num));
922 memset (last_use, 0, max_vars * sizeof (gint32));
924 /* For variables in bb->live_out, set last_use to block_to */
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) {
932 bits_out = mono_bitset_get_fast (bb->live_out_set, j);
933 k = (j * BITS_PER_CHUNK);
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;
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;
953 reverse [nins] = ins;
956 g_assert (pos < block_to);
958 /* Process instructions backwards */
959 for (i = nins - 1; i >= 0; --i) {
960 MonoInst *ins = (MonoInst*)reverse [i];
962 update_liveness (cfg, ctx, ins, pos, last_use);
964 pos -= INS_POS_INTERVAL;
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]);
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).
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);
991 for (idx = 0; idx < max_vars; ++idx) {
992 printf ("LIVENESS R%d: ", idx);
993 mono_linterval_print (get_var_interval (cfg, ctx, idx));
1005 * Perform liveness analysis.
1008 analyze_liveness (MonoCompile *cfg, MonoRegallocContext *ctx)
1010 LIVENESS_DEBUG (printf ("LIVENESS 3 %s\n", mono_method_full_name (cfg->method, TRUE)));
1012 /* FIXME: Make only one pass over the IR */
1014 compute_gen_kill_sets (cfg, ctx);
1016 compute_live_in_out_sets (cfg, ctx);
1018 compute_intervals (cfg, ctx);
1023 compare_by_interval_start_pos_func (gconstpointer a, gconstpointer b)
1025 MonoRegallocInterval *v1 = (MonoRegallocInterval*)a;
1026 MonoRegallocInterval *v2 = (MonoRegallocInterval*)b;
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)
1038 #define LSCAN_DEBUG(a) MINI_DEBUG(cfg->verbose_level, 2, a;)
1043 * Split the interval into two child intervals at POS.
1044 * [a, b] becomes [a, POS - 1], [POS, b].
1047 split_interval (MonoCompile *cfg, MonoRegallocContext *ctx, MonoRegallocInterval *interval, int pos)
1049 MonoRegallocInterval *child1, *child2;
1050 GSList *l, *split_list;
1052 child1 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRegallocInterval));
1053 child2 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRegallocInterval));
1054 child1->vreg = ctx->num_intervals ++;
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 ++;
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;
1069 interval->child1 = child1;
1070 interval->child2 = child2;
1071 child1->parent = interval;
1072 child2->parent = interval;
1074 mono_linterval_split (cfg, interval->interval, &child1->interval, &child2->interval, pos);
1076 /* Split use positions */
1077 for (l = interval->use_pos; l; l = l->next) {
1078 int use_pos = GPOINTER_TO_INT (l->data);
1081 child1->use_pos = g_slist_append_mempool (cfg->mempool, child1->use_pos, l->data);
1083 child2->use_pos = g_slist_append_mempool (cfg->mempool, child2->use_pos, l->data);
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));
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);
1107 * Return L or one of its children which covers POS.
1109 static MonoRegallocInterval*
1110 child_at (MonoRegallocInterval *l, int pos)
1112 if (l->vreg < MONO_FIRST_VREG)
1116 g_assert (mono_linterval_covers (l->interval, pos));
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);
1125 g_assert_not_reached ();
1131 * decompose_volatile_intervals:
1133 * Decompose intervals belonging to volatile variables. Return the decomposed intervals
1134 * which should be allocated to registers.
1137 decompose_volatile_intervals (MonoCompile *cfg, MonoRegallocContext *ctx, GList *intervals)
1139 GList *new_intervals;
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
1149 new_intervals = g_list_copy (intervals);
1150 for (l = intervals; l; l = l->next) {
1151 MonoRegallocInterval *current = l->data;
1152 MonoLiveInterval *new;
1154 gboolean ends_with_def;
1156 if (!current->is_volatile)
1160 * Instead of trying to split the arbitrary interval produced by the liveness
1161 * analysis phase, just use one big interval.
1163 ends_with_def = FALSE;
1164 use_pos = current->use_pos;
1166 int pos = GPOINTER_TO_INT (use_pos->data);
1168 use_pos = use_pos->next;
1169 if (!use_pos && USE_POS_IS_DEF (pos))
1170 ends_with_def = TRUE;
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;
1177 LSCAN_DEBUG (printf ("R%d is volatile ", current->vreg));
1178 LSCAN_DEBUG (mono_linterval_print (current->interval));
1179 LSCAN_DEBUG (printf ("\n"));
1181 new_intervals = g_list_remove (new_intervals, current);
1183 use_pos = current->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;
1189 LSCAN_DEBUG (printf ("\tUse pos: %x\n", pos));
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;
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);
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;
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;
1214 return new_intervals;
1220 * The actual linear scan register allocation algorithm.
1223 linear_scan (MonoCompile *cfg, MonoRegallocContext *ctx)
1225 GList *int_regs = mono_arch_get_global_int_regs (cfg);
1226 GList *fp_regs = mono_arch_get_global_fp_regs (cfg);
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];
1232 MonoMethodSignature *sig;
1233 MonoMethodHeader *header;
1235 LSCAN_DEBUG (printf ("\nLINEAR SCAN 2 for %s:\n", mono_method_full_name (cfg->method, TRUE)));
1237 header = cfg->header;
1239 sig = mono_method_signature (cfg->method);
1241 /* Create list of allocatable variables */
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]);
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);
1255 unhandled = g_list_sort (g_list_copy (vars), compare_by_interval_start_pos_func);
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]);
1266 unhandled = decompose_volatile_intervals (cfg, ctx, unhandled);
1269 * Handle arguments received on the stack by splitting their interval, and later
1270 * allocating the spilled part to the arg location.
1272 for (i = 0; i < sig->param_count + sig->hasthis; ++i) {
1273 MonoInst *ins = cfg->args [i];
1274 MonoRegallocInterval *current = &ctx->varinfo [ins->dreg];
1277 if (sig->hasthis && (i == 0))
1278 arg_type = &mono_defaults.object_class->byval_arg;
1280 arg_type = sig->params [i - sig->hasthis];
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);
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));
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);
1298 MonoRegallocInterval *current = unhandled->data;
1299 int pos, reg, max_free_pos;
1302 unhandled = g_list_delete_link (unhandled, unhandled);
1304 LSCAN_DEBUG (printf ("Processing R%d: ", current->vreg));
1305 LSCAN_DEBUG (mono_linterval_print (current->interval));
1306 LSCAN_DEBUG (printf ("\n"));
1308 if (!current->interval->range)
1311 /* Happens when splitting intervals */
1312 if (!current->use_pos)
1315 pos = current->interval->range->from;
1317 /* Check for intervals in active which expired or inactive */
1319 /* FIXME: Optimize this */
1322 MonoRegallocInterval *v = l->data;
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));
1336 /* Check for intervals in inactive which are expired or active */
1339 MonoRegallocInterval *v = l->data;
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));
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;
1361 for (i = 0; i < MONO_MAX_IREGS; ++i)
1362 if (allocateable [i])
1363 free_pos [i] = G_MAXINT32;
1368 for (l = active; l != NULL; l = l->next) {
1369 MonoRegallocInterval *v = l->data;
1372 free_pos [v->hreg] = 0;
1373 LSCAN_DEBUG (printf ("\threg %d is busy (R%d)\n", v->hreg, v->vreg));
1377 for (l = inactive; l != NULL; l = l->next) {
1378 MonoRegallocInterval *v = l->data;
1379 gint32 intersect_pos;
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));
1396 * Arguments should be allocated to the registers they reside in at the start of
1399 for (i = 0; i < sig->param_count + sig->hasthis; ++i) {
1400 MonoInst *ins = cfg->args [i];
1402 g_assert (ins->opcode == OP_REGVAR);
1403 if (ins->dreg == current->vreg)
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) {
1413 max_free_pos = free_pos [i];
1416 for (i = 0; i < MONO_MAX_IREGS; ++i)
1417 if (free_pos [i] > max_free_pos) {
1419 max_free_pos = free_pos [i];
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;
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.
1435 if (free_pos [current->preferred_reg] >= current->interval->range->from)
1436 reg = current->preferred_reg;
1442 g_assert (reg != -1);
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) {
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.
1450 MonoRegallocInterval *to_spill;
1453 // FIXME: Why was this needed ?
1454 //g_assert (!current->is_volatile);
1456 /* Spill the first */
1457 /* FIXME: Optimize the selection of the interval */
1460 for (l = active; l; l = l->next) {
1463 /* Fixed intervals cannot be spilled */
1464 if (to_spill->vreg >= MONO_FIRST_VREG)
1467 g_assert (to_spill);
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));
1472 * Avoid splitting to_spill before the start of current, since
1473 * its second child, which is added to unhandled would begin before
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;
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;
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));
1495 for (l = inactive; l != NULL; l = l->next) {
1496 MonoRegallocInterval *v = l->data;
1497 gint32 intersect_pos;
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));
1510 if (free_pos [reg] > 0 && free_pos [reg] >= current->interval->last_range->to) {
1511 /* Register available for whole interval */
1512 current->hreg = reg;
1514 cfg->used_int_regs |= (1 << reg);
1515 LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg, current->vreg));
1517 active = g_list_append (active, current);
1519 else if (free_pos [reg] > 0 && free_pos [reg] >= current->interval->range->from) {
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.
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]);
1528 current->child1->hreg = reg;
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);
1534 unhandled = g_list_insert_sorted (unhandled, current->child2, compare_by_interval_start_pos_func);
1536 guint32 use_pos = USE_POS_BASE (GPOINTER_TO_INT (current->use_pos->data));
1538 /* No register is available */
1539 if (use_pos > current->interval->range->from) {
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
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);
1549 /* Handled previously */
1550 g_assert_not_reached ();
1556 * The fp registers are numbered from MONO_MAX_IREGS during allocation, but they are
1557 * numbered from 0 in machine code.
1559 for (i = 0; i < cfg->next_vreg; ++i) {
1560 if (ctx->varinfo [i].fp) {
1563 /* Need to process child intervals as well */
1564 /* This happens rarely so it is not perf critical */
1566 children = g_slist_prepend (children, &ctx->varinfo [i]);
1568 MonoRegallocInterval *interval = children->data;
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);
1583 collect_spilled_intervals (MonoRegallocInterval *interval, GSList *list)
1585 if ((interval->hreg == -1) && !interval->child1 && interval->interval->range)
1586 list = g_slist_prepend (list, interval);
1588 if (interval->is_volatile && !interval->interval->range)
1589 /* Variables which are only referenced by ldaddr */
1590 list = g_slist_prepend (list, interval);
1592 if (interval->child1) {
1593 list = collect_spilled_intervals (interval->child1, list);
1594 list = collect_spilled_intervals (interval->child2, list);
1601 alloc_spill_slot (MonoCompile *cfg, guint32 size, guint32 align)
1606 res = cfg->stack_offset;
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;
1614 cfg->stack_offset += align - 1;
1615 cfg->stack_offset &= ~(align - 1);
1616 cfg->stack_offset += size;
1617 res = - cfg->stack_offset;
1625 assign_spill_slots (MonoCompile *cfg, MonoRegallocContext *ctx)
1627 GSList *spilled_intervals = NULL;
1629 MonoMethodSignature *sig;
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];
1638 if (sig->hasthis && (i == 0))
1639 arg_type = &mono_defaults.object_class->byval_arg;
1641 arg_type = sig->params [i - sig->hasthis];
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
1647 g_assert (ins->inst_offset != -1);
1648 ctx->varinfo [ins->dreg].offset = ins->inst_offset;
1652 /* Handle a vtype return */
1653 if (!cfg->vret_addr && MONO_TYPE_ISSTRUCT (sig->ret)) {
1654 MonoInst *ins = cfg->ret;
1656 ctx->varinfo [ins->dreg].offset = ins->inst_offset;
1659 for (i = 0; i < cfg->next_vreg; ++i) {
1660 spilled_intervals = collect_spilled_intervals (&ctx->varinfo [i], spilled_intervals);
1663 LSCAN_DEBUG (printf ("\nSPILL OFFSETS:\n\n"));
1665 for (l = spilled_intervals; l; l = l->next) {
1666 MonoRegallocInterval *interval = l->data;
1667 MonoRegallocInterval *parent;
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.
1675 for (parent = interval; parent->parent != NULL; parent = parent->parent)
1677 if (parent->offset != -1) {
1678 interval->offset = parent->offset;
1679 } else if (interval->offset != -1) {
1680 /* Already allocated (for example, valuetypes as arguments) */
1682 guint32 size, align;
1684 if (MONO_TYPE_ISSTRUCT (interval->type)) {
1685 // FIXME: pinvoke, gsctx
1687 size = mini_type_stack_size (NULL, interval->type, NULL);
1688 } else if (interval->fp) {
1689 size = sizeof (double);
1691 size = sizeof (gpointer);
1694 align = sizeof (gpointer);
1695 interval->offset = alloc_spill_slot (cfg, size, align);
1698 for (parent = interval; parent != NULL; parent = parent->parent) {
1699 if (parent->offset == -1)
1700 parent->offset = interval->offset;
1703 LSCAN_DEBUG (printf ("R%d %d", interval->vreg, interval->offset));
1704 LSCAN_DEBUG (mono_linterval_print (interval->interval));
1705 LSCAN_DEBUG (printf ("\n"));
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;
1720 * Order the instructions in MOVES so earlier moves don't overwrite the sources of
1724 order_moves (MonoCompile *cfg, MonoRegallocContext *ctx, MonoInst **moves, int nmoves)
1730 * Sort the moves so earlier moves don't overwrite the sources of later
1733 /* FIXME: Do proper cycle detection instead of the current ugly hack */
1735 for (i = 0; i < nmoves; ++i) {
1741 for (j = i + 1; j < nmoves; ++j)
1742 if (moves [i]->dreg == moves [j]->sreg1) {
1750 moves [j] = moves [i];
1754 if (niter > nmoves * 2)
1755 /* Possible cycle */
1759 if (niter > nmoves * 2)
1764 if (niter > nmoves * 2) {
1769 * Save all registers to the stack and reload them again.
1770 * FIXME: Optimize this.
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);
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;
1784 cfg->stack_offset += size - 1;
1785 cfg->stack_offset &= ~(size - 1);
1786 cfg->stack_offset += size;
1787 offsets [i] = - cfg->stack_offset;
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);
1799 ins->sreg1 = moves [i]->sreg1;
1800 ins->inst_destbasereg = cfg->frame_reg;
1801 ins->inst_offset = offsets [i];
1803 l = g_slist_append_mempool (cfg->mempool, l, ins);
1804 g_hash_table_insert (ctx->spill_ins, ins, ins);
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);
1815 ins->dreg = moves [i]->dreg;
1816 ins->inst_basereg = cfg->frame_reg;
1817 ins->inst_offset = offsets [i];
1819 l = g_slist_append_mempool (cfg->mempool, l, ins);
1820 g_hash_table_insert (ctx->spill_ins, ins, ins);
1825 for (i = 0; i < nmoves; ++i)
1826 l = g_slist_append_mempool (cfg->mempool, l, moves [i]);
1835 * Add spill loads and stores to the IR at the locations where intervals were split.
1838 add_spill_code (MonoCompile *cfg, MonoRegallocContext *ctx)
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;
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);
1853 /* First pass: Add spill loads/stores to the IR */
1854 pos = (bb->dfn << 16) + INS_POS_INTERVAL;
1856 after_last_ins = FALSE;
1857 for (ins = bb->code; !after_last_ins;) {
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 */
1864 if (G_UNLIKELY (cfg->verbose_level > 1)) {
1865 printf (" <spill ins>\n");
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;
1878 pos_interval_limit = INS_POS_INTERVAL;
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
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;
1893 /* The childs might be split */
1894 if (interval->child1->child1)
1895 child1 = child_at (interval->child1, pos - pos_interval);
1897 child1 = interval->child1;
1898 if (pos < interval->child2->interval->range->from)
1899 /* Happens when volatile intervals are split */
1901 child2 = child_at (interval->child2, pos);
1903 if ((child1->hreg == -1) && (child2->hreg == -1))
1905 * Happens when an interval is split, then the first child
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) {
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
1925 * FIXME: Optimize child1->hreg == child2->hreg
1927 offset = alloc_spill_slot (cfg, sizeof (gpointer), sizeof (gpointer));
1929 NEW_STORE_MEMBASE (cfg, store, mono_type_to_store_membase (cfg, interval->type), cfg->frame_reg, offset, child1->hreg);
1931 mono_bblock_insert_after_ins (bb, prev, store);
1933 g_hash_table_insert (ctx->spill_ins, store, store);
1935 NEW_LOAD_MEMBASE (cfg, load, mono_type_to_load_membase (cfg, interval->type), child2->hreg, cfg->frame_reg, offset);
1937 mono_bblock_insert_after_ins (bb, ins, load);
1938 g_hash_table_insert (ctx->spill_ins, load, load);
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
1945 * R1's interval is split between the two instructions.
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);
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);
1958 NEW_STORE_MEMBASE (cfg, store, mono_type_to_store_membase (cfg, interval->type), cfg->frame_reg, child2->offset, child1->hreg);
1960 mono_bblock_insert_after_ins (bb, prev, store);
1962 g_hash_table_insert (ctx->spill_ins, store, store);
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);
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);
1973 mono_bblock_insert_before_ins (bb, ins, load);
1976 g_hash_table_insert (ctx->spill_ins, load, load);
1978 LSCAN_DEBUG (printf (" Spill load added for R%d (R%d -> R%d) at %x\n", interval->vreg, child1->vreg, child2->vreg, pos));
1986 if (G_UNLIKELY (cfg->verbose_level > 1))
1988 mono_print_ins (ins);
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];
2000 if (!out_bb->live_in_set)
2001 /* Exception handling block */
2004 from_pos = (bb->dfn << 16) + 0xffff;
2005 to_pos = (out_bb->dfn << 16);
2008 for (i = 0; i < cfg->next_vreg; ++i) {
2009 MonoRegallocInterval *interval = &ctx->varinfo [i];
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);
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);
2033 g_assert (child1->offset == child2->offset);
2039 if (bb->out_count == 1) {
2041 } else if (out_bb->in_count == 1) {
2042 add_at_head = FALSE;
2044 // FIXME: Split critical edges
2049 insert_after = NULL;
2056 * Emit spill instructions in such a way that instructions don't
2057 * overwrite the source registers of instructions coming after them.
2059 /* Simply emit stores, then moves then loads */
2060 for (l = ins_to_add; l; l = l->next) {
2061 MonoInst *ins = l->data;
2063 if (MONO_IS_STORE_MEMBASE (ins)) {
2065 mono_add_ins_to_end (bb, ins);
2067 mono_bblock_insert_after_ins (out_bb, insert_after, ins);
2073 /* Collect the moves */
2075 for (l = ins_to_add; l; l = l->next) {
2076 MonoInst *ins = l->data;
2078 if (MONO_IS_MOVE (ins))
2081 moves = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoInst*) * nmoves);
2083 for (l = ins_to_add; l; l = l->next) {
2084 MonoInst *ins = l->data;
2086 if (MONO_IS_MOVE (ins))
2087 moves [nmoves ++] = ins;
2090 moves_to_add = order_moves (cfg, ctx, moves, nmoves);
2092 for (l = moves_to_add; l; l = l->next) {
2093 MonoInst *ins = l->data;
2096 mono_add_ins_to_end (bb, ins);
2098 mono_bblock_insert_after_ins (out_bb, insert_after, ins);
2103 for (l = ins_to_add; l; l = l->next) {
2104 MonoInst *ins = l->data;
2106 if (MONO_IS_LOAD_MEMBASE (ins)) {
2108 mono_add_ins_to_end (bb, ins);
2110 mono_bblock_insert_after_ins (out_bb, insert_after, ins);
2123 * Replace references to vregs with their assigned physical registers or spill
2127 rewrite_code (MonoCompile *cfg, MonoRegallocContext *ctx)
2130 MonoInst *ins, *prev;
2134 defs = g_new (MonoInst*, MONO_MAX_IREGS + MONO_MAX_FREGS);
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);
2140 memset (defs, 0, sizeof (MonoInst*) * (MONO_MAX_IREGS + MONO_MAX_FREGS));
2142 pos = (bb->dfn << 16);
2144 MONO_BB_FOR_EACH_INS (bb, ins) {
2145 const char *spec = INS_INFO (ins->opcode);
2146 pos += INS_POS_INTERVAL;
2148 if (G_UNLIKELY (cfg->verbose_level > 1))
2149 mono_print_ins (ins);
2151 if (g_hash_table_lookup (ctx->spill_ins, ins)) {
2153 * This instruction was added after liveness info was computed, and thus
2154 * screws up the pos calculation. The instruction already uses hregs.
2156 pos -= INS_POS_INTERVAL;
2162 if (ins->opcode == OP_NOP)
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;
2170 g_assert (ctx->varinfo [var->dreg].hreg == -1);
2171 g_assert (ctx->varinfo [var->dreg].offset != -1);
2173 if (ctx->varinfo [var->dreg].offset != 0) {
2175 * The ADD_IMM does not satisfy register constraints on x86/amd64.
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);
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;
2188 ins->opcode = OP_MOVE;
2189 ins->dreg = l->hreg;
2190 ins->sreg1 = cfg->frame_reg;
2191 defs [ins->dreg] = ins;
2193 spec = INS_INFO (OP_NOP);
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.
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;
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;
2220 * FIXME: Deadce the def. This is hard to do, since it could be
2221 * accessed in other bblocks.
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;
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;
2236 def = defs [ins->sreg1];
2237 if (def && def->opcode == OP_MOVE && def->sreg1 == cfg->frame_reg)
2238 ins->sreg1 = cfg->frame_reg;
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;
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;
2253 if (cfg->verbose_level > 1)
2254 mono_print_ins_index (1, ins);
2263 static MonoRegallocContext*
2264 regalloc_ctx_create (MonoCompile *cfg)
2266 MonoRegallocContext *ctx;
2269 ctx = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoRegallocContext));
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) {
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;
2281 if (i >= MONO_MAX_IREGS && i < MONO_MAX_IREGS + MONO_MAX_FREGS)
2282 ctx->varinfo [i].fp = TRUE;
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;
2289 ctx->varinfo [i].type = var->inst_vtype;
2291 ctx->varinfo [i].type = sizeof (gpointer) == 8 ? &mono_defaults.int64_class->byval_arg : &mono_defaults.int_class->byval_arg;
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);
2302 mono_global_regalloc (MonoCompile *cfg)
2304 MonoRegallocContext *ctx;
2306 mono_arch_fill_argument_info (cfg);
2308 /* This could create vregs, so it has to come before ctx_create */
2309 handle_reg_constraints (cfg);
2311 ctx = regalloc_ctx_create (cfg);
2313 collect_fp_vregs (cfg, ctx);
2315 analyze_liveness (cfg, ctx);
2317 linear_scan (cfg, ctx);
2319 mono_arch_allocate_vars (cfg);
2321 assign_spill_slots (cfg, ctx);
2323 add_spill_code (cfg, ctx);
2325 rewrite_code (cfg, ctx);
2331 mono_global_regalloc (MonoCompile *cfg)