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_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_dreg
= MONO_ARCH_INST_FIXED_REG (spec
[MONO_INST_DEST
]);
261 if (MONO_ARCH_INST_IS_REGPAIR (spec
[MONO_INST_DEST
]) ||
262 MONO_ARCH_INST_IS_REGPAIR (spec
[MONO_INST_SRC1
]) ||
263 MONO_ARCH_INST_IS_REGPAIR (spec
[MONO_INST_SRC2
]))
265 g_assert_not_reached ();
267 if (spec
[MONO_INST_CLOB
] == 'c') {
268 MonoCallInst
*call
= (MonoCallInst
*)ins
;
272 * FIXME: mono_arch_emit_call () already adds moves for each argument,
273 * it might be better to rewrite those by changing the dreg to the hreg.
275 for (list
= call
->out_ireg_args
; list
; list
= list
->next
) {
280 regpair
= (guint32
)(gssize
)(list
->data
);
281 hreg
= regpair
>> 24;
282 reg
= regpair
& 0xffffff;
284 move
= create_move (cfg
, hreg
, reg
);
285 mono_bblock_insert_after_ins (bb
, prev
, move
);
289 for (list
= call
->out_freg_args
; list
; list
= list
->next
) {
294 regpair
= (guint32
)(gssize
)(list
->data
);
295 hreg
= regpair
>> 24;
296 reg
= regpair
& 0xffffff;
298 move
= create_fp_move (cfg
, hreg
+ MONO_MAX_IREGS
, reg
);
299 mono_bblock_insert_after_ins (bb
, prev
, move
);
304 if (spec
[MONO_INST_CLOB
] == '1') {
305 /* Copying sreg1 to dreg could clobber sreg2 so make a copy of sreg2 */
306 if (spec
[MONO_INST_SRC2
] && (ins
->dreg
== ins
->sreg2
)) {
307 int new_sreg2
= mono_alloc_preg (cfg
);
309 g_assert (spec
[MONO_INST_DEST
] != 'f');
310 move
= create_move (cfg
, new_sreg2
, ins
->sreg2
);
311 mono_bblock_insert_after_ins (bb
, prev
, move
);
313 ins
->sreg2
= new_sreg2
;
315 if (spec
[MONO_INST_DEST
] == 'f')
316 emit_fp_move (cfg
, ins
->dreg
, ins
->sreg1
, prev
);
318 emit_move (cfg
, ins
->dreg
, ins
->sreg1
, prev
);
319 ins
->sreg1
= ins
->dreg
;
322 if (dest_sreg1
!= -1) {
323 emit_move (cfg
, dest_sreg1
, ins
->sreg1
, prev
);
324 ins
->sreg1
= dest_sreg1
;
327 if (dest_sreg2
!= -1) {
328 emit_move (cfg
, dest_sreg2
, ins
->sreg2
, prev
);
329 ins
->sreg2
= dest_sreg2
;
332 if (dest_dreg
!= -1) {
333 emit_move (cfg
, ins
->dreg
, dest_dreg
, ins
);
334 g_assert (spec
[MONO_INST_CLOB
] != '1');
335 ins
->dreg
= dest_dreg
;
338 /* FIXME: Add fixed fp regs to the machine description */
339 if (ins
->opcode
== OP_FCALL
|| ins
->opcode
== OP_FCALL_REG
|| ins
->opcode
== OP_FCALL_MEMBASE
) {
340 emit_fp_move (cfg
, ins
->dreg
, MONO_MAX_IREGS
+ MONO_ARCH_FP_RETURN_REG
, ins
);
341 ins
->dreg
= MONO_MAX_IREGS
+ MONO_ARCH_FP_RETURN_REG
;
345 * Add a dummy instruction after each definition of a volatile vreg, this is
346 * needed by the code in decompose_volatile_intervals ().
348 if (get_vreg_to_inst (cfg
, ins
->dreg
) && (get_vreg_to_inst (cfg
, ins
->dreg
)->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
355 sig
= mono_method_signature (cfg
->method
);
357 /* Add move of arguments */
359 * FIXME: Maybe this should be done by the allocator.
361 if (bb
== cfg
->bb_entry
) {
365 if (cfg
->vret_addr
) {
366 g_assert (cfg
->vret_addr
->opcode
== OP_REGVAR
);
367 emit_move (cfg
, cfg
->vret_addr
->dreg
, cfg
->vret_addr
->inst_c0
, prev
);
371 for (i
= 0; i
< sig
->param_count
+ sig
->hasthis
; ++i
) {
374 if (sig
->hasthis
&& (i
== 0))
375 arg_type
= &mono_defaults
.object_class
->byval_arg
;
377 arg_type
= sig
->params
[i
- sig
->hasthis
];
379 // FIXME: vtypes in registers (pass + return)
381 if (ins
->opcode
== OP_REGVAR
) {
382 if (!arg_type
->byref
&& ((arg_type
->type
== MONO_TYPE_R4
) || (arg_type
->type
== MONO_TYPE_R8
)))
383 /* For R4, the prolog is assumed to do the conversion */
384 emit_fp_move (cfg
, ins
->dreg
, ins
->inst_c0
+ MONO_MAX_IREGS
, prev
);
386 emit_move (cfg
, ins
->dreg
, ins
->inst_c0
, prev
);
393 /* Add move of return value */
394 for (i
= 0; i
< bb
->out_count
; ++i
) {
395 /* bb->dfn == 0 -> unreachable */
396 if (cfg
->ret
&& !cfg
->vret_addr
&& !MONO_TYPE_ISSTRUCT (sig
->ret
) && bb
->out_bb
[i
] == cfg
->bb_exit
&& bb
->dfn
) {
397 MonoInst
*ins
= NULL
;
400 hreg
= cfg
->ret
->inst_c0
;
402 if ((sig
->ret
->type
== MONO_TYPE_R4
) || (sig
->ret
->type
== MONO_TYPE_R8
))
403 /* For R4, the JIT has already emitted code to do the conversion */
404 ins
= create_fp_move (cfg
, hreg
+ MONO_MAX_IREGS
, cfg
->ret
->dreg
);
406 ins
= create_move (cfg
, hreg
, cfg
->ret
->dreg
);
407 mono_add_ins_to_end (bb
, ins
);
411 if (cfg
->verbose_level
> 1) mono_print_bb (bb
, "AFTER HANDLE-REG-CONSTRAINTS ");
414 mono_verify_cfg (cfg
);
420 * Set varinfo->fp for all float vregs
423 collect_fp_vregs (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
427 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
430 MONO_BB_FOR_EACH_INS (bb
, ins
) {
431 const char *spec
= ins_get_spec (ins
->opcode
);
433 if (G_UNLIKELY (sreg1_is_fp (spec
) || sreg2_is_fp (spec
) || dreg_is_fp (spec
))) {
434 if (sreg1_is_fp (spec
)) {
435 g_assert (ins
->sreg1
>= MONO_MAX_IREGS
);
436 ctx
->varinfo
[ins
->sreg1
].fp
= TRUE
;
437 if (ctx
->varinfo
[ins
->sreg1
].type
->type
!= MONO_TYPE_R4
)
438 ctx
->varinfo
[ins
->sreg1
].type
= &mono_defaults
.double_class
->byval_arg
;
440 if (sreg2_is_fp (spec
)) {
441 g_assert (ins
->sreg2
>= MONO_MAX_IREGS
);
442 ctx
->varinfo
[ins
->sreg2
].fp
= TRUE
;
443 if (ctx
->varinfo
[ins
->sreg2
].type
->type
!= MONO_TYPE_R4
)
444 ctx
->varinfo
[ins
->sreg2
].type
= &mono_defaults
.double_class
->byval_arg
;
446 if (dreg_is_fp (spec
)) {
447 g_assert (ins
->dreg
>= MONO_MAX_IREGS
);
448 ctx
->varinfo
[ins
->dreg
].fp
= TRUE
;
449 if (ctx
->varinfo
[ins
->dreg
].type
->type
!= MONO_TYPE_R4
)
450 ctx
->varinfo
[ins
->dreg
].type
= &mono_defaults
.double_class
->byval_arg
;
458 #define LIVENESS_DEBUG(a) do { if (cfg->verbose_level > 2) { a; } } while (0)
460 #define LIVENESS_DEBUG(a)
463 // #define DEBUG_LIVENESS 1
465 G_GNUC_UNUSED
static void
466 mono_bitset_print (MonoBitSet
*set
)
471 for (i
= 0; i
< mono_bitset_size (set
); i
++) {
473 if (mono_bitset_test (set
, i
))
481 update_gen_kill_set (MonoCompile
*cfg
, MonoRegallocContext
*ctx
, MonoBasicBlock
*bb
, MonoInst
*ins
)
483 const char *spec
= INS_INFO (ins
->opcode
);
488 if (spec
[MONO_INST_SRC1
] != ' ') {
489 if (!mono_bitset_test_fast (bb
->kill_set
, sreg
))
490 mono_bitset_set_fast (bb
->gen_set
, sreg
);
495 if (spec
[MONO_INST_SRC2
] != ' ') {
496 if (!mono_bitset_test_fast (bb
->kill_set
, sreg
))
497 mono_bitset_set_fast (bb
->gen_set
, sreg
);
501 if (spec
[MONO_INST_DEST
] != ' ') {
502 if (MONO_IS_STORE_MEMBASE (ins
)) {
503 if (!mono_bitset_test_fast (bb
->kill_set
, ins
->dreg
))
504 mono_bitset_set_fast (bb
->gen_set
, ins
->dreg
);
506 mono_bitset_set_fast (bb
->kill_set
, ins
->dreg
);
512 compute_gen_kill_sets (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
514 int i
, max_vars
= cfg
->next_vreg
;
518 bitsize
= mono_bitset_alloc_size (max_vars
, 0);
519 mem
= mono_mempool_alloc0 (cfg
->mempool
, cfg
->num_bblocks
* bitsize
* 3);
521 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
522 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
524 bb
->gen_set
= mono_bitset_mem_new (mem
, max_vars
, MONO_BITSET_DONT_FREE
);
526 bb
->kill_set
= mono_bitset_mem_new (mem
, max_vars
, MONO_BITSET_DONT_FREE
);
528 /* Initialized later */
529 bb
->live_in_set
= NULL
;
530 bb
->live_out_set
= mono_bitset_mem_new (mem
, max_vars
, MONO_BITSET_DONT_FREE
);
534 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
535 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
537 #ifdef DEBUG_LIVENESS
541 MONO_BB_FOR_EACH_INS (bb
, ins
)
542 update_gen_kill_set (cfg
, ctx
, bb
, ins
);
544 #ifdef DEBUG_LIVENESS
545 printf ("BLOCK BB%d (", bb
->block_num
);
546 for (j
= 0; j
< bb
->out_count
; j
++)
547 printf ("BB%d, ", bb
->out_bb
[j
]->block_num
);
550 printf ("GEN BB%d: ", bb
->block_num
); mono_bitset_print (bb
->gen_set
);
551 printf ("KILL BB%d: ", bb
->block_num
); mono_bitset_print (bb
->kill_set
);
555 if (cfg
->ret
&& cfg
->ret
->opcode
== OP_REGVAR
) {
556 int hreg
= cfg
->ret
->inst_c0
;
558 /* gen_set might be empty if bb_exit is not reachable, like when using a tail call */
559 if (cfg
->bb_exit
->gen_set
)
560 mono_bitset_set (cfg
->bb_exit
->gen_set
, hreg
);
565 compute_live_in_out_sets (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
567 MonoBitSet
*old_live_out_set
;
568 int i
, j
, max_vars
= cfg
->next_vreg
;
570 gboolean
*in_worklist
;
571 MonoBasicBlock
**worklist
;
576 bitsize
= mono_bitset_alloc_size (max_vars
, 0);
577 mem
= mono_mempool_alloc0 (cfg
->mempool
, cfg
->num_bblocks
* bitsize
);
579 old_live_out_set
= mono_bitset_new (max_vars
, 0);
580 in_worklist
= g_new0 (gboolean
, cfg
->num_bblocks
+ 1);
582 worklist
= g_new (MonoBasicBlock
*, cfg
->num_bblocks
+ 1);
586 * This is a backward dataflow analysis problem, so we process blocks in
587 * decreasing dfn order, this speeds up the iteration.
589 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
590 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
592 worklist
[l_end
++] = bb
;
593 in_worklist
[bb
->dfn
] = TRUE
;
599 MonoBasicBlock
*bb
= worklist
[--l_end
];
600 MonoBasicBlock
*out_bb
;
603 in_worklist
[bb
->dfn
] = FALSE
;
605 #ifdef DEBUG_LIVENESS
606 printf ("P: %d(%d): IN: ", bb
->block_num
, bb
->dfn
);
607 for (j
= 0; j
< bb
->in_count
; ++j
)
608 printf ("BB%d ", bb
->in_bb
[j
]->block_num
);
610 for (j
= 0; j
< bb
->out_count
; ++j
)
611 printf ("BB%d ", bb
->out_bb
[j
]->block_num
);
616 if (bb
->out_count
== 0)
621 if (!bb
->live_in_set
) {
622 /* First pass over this bblock */
627 mono_bitset_copyto_fast (bb
->live_out_set
, old_live_out_set
);
630 for (j
= 0; j
< bb
->out_count
; j
++) {
631 out_bb
= bb
->out_bb
[j
];
633 if (!out_bb
->live_in_set
) {
634 out_bb
->live_in_set
= mono_bitset_mem_new (mem
, max_vars
, MONO_BITSET_DONT_FREE
);
637 mono_bitset_copyto_fast (out_bb
->live_out_set
, out_bb
->live_in_set
);
638 mono_bitset_sub_fast (out_bb
->live_in_set
, out_bb
->kill_set
);
639 mono_bitset_union_fast (out_bb
->live_in_set
, out_bb
->gen_set
);
642 mono_bitset_union_fast (bb
->live_out_set
, out_bb
->live_in_set
);
645 if (changed
|| !mono_bitset_equal (old_live_out_set
, bb
->live_out_set
)) {
646 if (!bb
->live_in_set
) {
647 bb
->live_in_set
= mono_bitset_mem_new (mem
, max_vars
, MONO_BITSET_DONT_FREE
);
650 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
651 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
652 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
654 for (j
= 0; j
< bb
->in_count
; j
++) {
655 MonoBasicBlock
*in_bb
= bb
->in_bb
[j
];
657 * Some basic blocks do not seem to be in the
658 * cfg->bblocks array...
660 if (in_bb
->gen_set
&& !in_worklist
[in_bb
->dfn
]) {
661 #ifdef DEBUG_LIVENESS
662 printf ("\tADD: %d\n", in_bb
->block_num
);
665 * Put the block at the top of the stack, so it
666 * will be processed right away.
668 worklist
[l_end
++] = in_bb
;
669 in_worklist
[in_bb
->dfn
] = TRUE
;
675 #ifdef DEBUG_LIVENESS
676 printf ("IT: %d %d.\n", cfg
->num_bblocks
, out_iter
);
679 mono_bitset_free (old_live_out_set
);
682 g_free (in_worklist
);
684 /* Compute live_in_set for bblocks skipped earlier */
685 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
686 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
688 if (!bb
->live_in_set
) {
689 bb
->live_in_set
= mono_bitset_mem_new (mem
, max_vars
, MONO_BITSET_DONT_FREE
);
692 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
693 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
694 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
698 #ifdef DEBUG_LIVENESS
699 for (i
= cfg
->num_bblocks
- 1; i
>= 0; i
--) {
700 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
702 printf ("LIVE IN BB%d: ", bb
->block_num
);
703 mono_bitset_print (bb
->live_in_set
);
704 printf ("LIVE OUT BB%d: ", bb
->block_num
);
705 mono_bitset_print (bb
->live_out_set
);
711 update_liveness (MonoCompile
*cfg
, MonoRegallocContext
*ctx
, MonoInst
*ins
, int inst_num
, gint32
*last_use
)
713 const char *spec
= INS_INFO (ins
->opcode
);
716 LIVENESS_DEBUG (printf ("\t%x: ", inst_num
); mono_print_ins (ins
));
719 if (spec
[MONO_INST_DEST
] != ' ') {
720 if (MONO_IS_STORE_MEMBASE (ins
)) {
721 if (last_use
[ins
->dreg
] == 0) {
722 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins
->dreg
, inst_num
+ INS_POS_USE
));
723 last_use
[ins
->dreg
] = inst_num
+ INS_POS_USE
;
726 if (last_use
[ins
->dreg
] > 0) {
727 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x]\n", ins
->dreg
, inst_num
+ INS_POS_DEF
, last_use
[ins
->dreg
]));
728 if (ins
->dreg
== ins
->sreg1
&& ins
->dreg
< MONO_FIRST_VREG
) {
730 * Avoid a hole in the liveness range, since the allocation code
731 * could think the register is free there.
733 mono_linterval_add_range (ctx
->cfg
, ctx
->varinfo
[ins
->dreg
].interval
, inst_num
, last_use
[ins
->dreg
]);
735 mono_linterval_add_range (ctx
->cfg
, ctx
->varinfo
[ins
->dreg
].interval
, inst_num
+ INS_POS_DEF
, last_use
[ins
->dreg
]);
737 last_use
[ins
->dreg
] = 0;
740 if (!vreg_is_volatile (cfg
, ins
->dreg
) && ((ins
->opcode
== OP_ICONST
) || (ins
->opcode
== OP_I8CONST
) || (ins
->opcode
== OP_R8CONST
) || (ins
->opcode
== OP_MOVE
) || (ins
->opcode
== OP_FMOVE
))) {
741 LIVENESS_DEBUG (printf ("\tdead def of R%d eliminated\n", ins
->dreg
));
743 spec
= INS_INFO (ins
->opcode
);
745 LIVENESS_DEBUG (printf ("\tdead def of R%d, add range to R%d: [%x, %x]\n", ins
->dreg
, ins
->dreg
, inst_num
+ INS_POS_DEF
, inst_num
+ INS_POS_DEF
));
746 mono_linterval_add_range (ctx
->cfg
, ctx
->varinfo
[ins
->dreg
].interval
, inst_num
+ INS_POS_DEF
, inst_num
+ INS_POS_DEF
);
750 if (ins
->opcode
!= OP_NOP
) {
751 /* Since we process instructions backwards, the list will be properly sorted */
752 if (MONO_IS_STORE_MEMBASE (ins
))
753 ctx
->varinfo
[ins
->dreg
].use_pos
= g_slist_prepend_mempool (ctx
->cfg
->mempool
, ctx
->varinfo
[ins
->dreg
].use_pos
, GINT_TO_POINTER (inst_num
));
755 ctx
->varinfo
[ins
->dreg
].use_pos
= g_slist_prepend_mempool (ctx
->cfg
->mempool
, ctx
->varinfo
[ins
->dreg
].use_pos
, GINT_TO_POINTER (inst_num
+ INS_POS_DEF
));
758 /* Set preferred vregs */
759 if ((ins
->opcode
== OP_MOVE
) || (ins
->opcode
== OP_FMOVE
)) {
760 if (ins
->sreg1
< MONO_FIRST_VREG
) {
761 ctx
->varinfo
[ins
->dreg
].preferred_reg
= ins
->sreg1
;
762 } else if (ins
->dreg
< MONO_FIRST_VREG
) {
763 ctx
->varinfo
[ins
->sreg1
].preferred_reg
= ins
->dreg
;
764 } else if (ctx
->varinfo
[ins
->dreg
].preferred_reg
!= -1) {
766 * Propagate preferred vregs. This works because instructions are
767 * processed in reverse order.
769 ctx
->varinfo
[ins
->sreg1
].preferred_reg
= ctx
->varinfo
[ins
->dreg
].preferred_reg
;
776 if (spec
[MONO_INST_SRC1
] != ' ') {
777 if (last_use
[sreg
] == 0) {
778 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
+ INS_POS_USE
));
779 last_use
[sreg
] = inst_num
+ INS_POS_USE
;
781 ctx
->varinfo
[sreg
].use_pos
= g_slist_prepend_mempool (ctx
->cfg
->mempool
, ctx
->varinfo
[sreg
].use_pos
, GINT_TO_POINTER (inst_num
));
786 if (spec
[MONO_INST_SRC2
] != ' ') {
787 if (last_use
[sreg
] == 0) {
788 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
+ INS_POS_USE
));
789 last_use
[sreg
] = inst_num
+ INS_POS_USE
;
791 ctx
->varinfo
[sreg
].use_pos
= g_slist_prepend_mempool (ctx
->cfg
->mempool
, ctx
->varinfo
[sreg
].use_pos
, GINT_TO_POINTER (inst_num
));
794 if (ins_get_spec (ins
->opcode
)[MONO_INST_CLOB
] == 'c') {
795 MonoCallInst
*call
= (MonoCallInst
*)ins
;
798 for (list
= call
->out_ireg_args
; list
; list
= list
->next
) {
801 regpair
= (guint32
)(gssize
)(list
->data
);
802 sreg
= regpair
>> 24;
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
));
811 for (list
= call
->out_freg_args
; list
; list
= list
->next
) {
814 regpair
= (guint32
)(gssize
)(list
->data
);
815 sreg
= (regpair
>> 24) + MONO_MAX_IREGS
;
817 if (last_use
[sreg
] == 0) {
818 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
+ INS_POS_USE
));
819 last_use
[sreg
] = inst_num
+ INS_POS_USE
;
821 ctx
->varinfo
[sreg
].use_pos
= g_slist_prepend_mempool (ctx
->cfg
->mempool
, ctx
->varinfo
[sreg
].use_pos
, GINT_TO_POINTER (inst_num
));
826 if (ins_get_spec (ins
->opcode
)[MONO_INST_CLOB
]) {
827 char clob
= ins_get_spec (ins
->opcode
)[MONO_INST_CLOB
];
831 /* A call clobbers some int/fp registers */
832 for (l
= mono_arch_get_iregs_clobbered_by_call ((MonoCallInst
*)ins
); l
; l
= l
->next
)
833 mono_linterval_add_range (ctx
->cfg
, ctx
->varinfo
[GPOINTER_TO_INT (l
->data
)].interval
, inst_num
+ INS_POS_CLOB
, inst_num
+ INS_POS_CLOB
);
834 for (l
= mono_arch_get_fregs_clobbered_by_call ((MonoCallInst
*)ins
); l
; l
= l
->next
)
835 mono_linterval_add_range (ctx
->cfg
, ctx
->varinfo
[GPOINTER_TO_INT (l
->data
)].interval
, inst_num
+ INS_POS_CLOB
, inst_num
+ INS_POS_CLOB
);
838 int clob_reg
= MONO_ARCH_INST_FIXED_REG (clob
);
841 mono_linterval_add_range (ctx
->cfg
, ctx
->varinfo
[clob_reg
].interval
, inst_num
+ INS_POS_CLOB
, inst_num
+ INS_POS_CLOB
);
849 * Compute liveness intervals for all vregs.
852 compute_intervals (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
854 int bnum
, idx
, i
, j
, nins
, rem
, max
, max_vars
, block_from
, block_to
, pos
, reverse_len
;
858 max_vars
= cfg
->next_vreg
;
859 last_use
= g_new0 (gint32
, max_vars
);
862 reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * reverse_len
);
864 for (idx
= 0; idx
< max_vars
; ++idx
) {
865 ctx
->varinfo
[idx
].interval
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
869 * Process bblocks in reverse order, so the addition of new live ranges
870 * to the intervals is faster.
872 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
873 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
876 block_from
= (bb
->dfn
<< 16); /* so pos > 0 */
877 if (bnum
< cfg
->num_bblocks
- 1)
878 /* Beginning of the next bblock */
879 block_to
= (cfg
->bblocks
[bnum
+ 1]->dfn
<< 16);
881 block_to
= (bb
->dfn
<< 16) + 0xffff;
883 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb
->block_num
));
885 memset (last_use
, 0, max_vars
* sizeof (gint32
));
887 /* For variables in bb->live_out, set last_use to block_to */
889 rem
= max_vars
% BITS_PER_CHUNK
;
890 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
891 for (j
= 0; j
< max
; ++j
) {
895 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
896 k
= (j
* BITS_PER_CHUNK
);
899 LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", k
, block_to
));
900 last_use
[k
] = block_to
;
907 for (nins
= 0, pos
= block_from
, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
, pos
+= INS_POS_INTERVAL
) {
908 if (nins
>= reverse_len
) {
909 int new_reverse_len
= reverse_len
* 2;
910 MonoInst
**new_reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * new_reverse_len
);
911 memcpy (new_reverse
, reverse
, sizeof (MonoInst
*) * reverse_len
);
912 reverse
= new_reverse
;
913 reverse_len
= new_reverse_len
;
916 reverse
[nins
] = ins
;
919 g_assert (pos
< block_to
);
921 /* Process instructions backwards */
922 for (i
= nins
- 1; i
>= 0; --i
) {
923 MonoInst
*ins
= (MonoInst
*)reverse
[i
];
925 update_liveness (cfg
, ctx
, ins
, pos
, last_use
);
927 pos
-= INS_POS_INTERVAL
;
930 for (idx
= 0; idx
< max_vars
; ++idx
) {
931 if (last_use
[idx
] != 0) {
932 /* Live at exit, not written -> live on enter */
933 LIVENESS_DEBUG (printf ("Var R%d live at enter, add range to R%d: [%x, %x)\n", idx
, idx
, block_from
, last_use
[idx
]));
934 mono_linterval_add_range (cfg
, ctx
->varinfo
[idx
].interval
, block_from
, last_use
[idx
]);
942 * Arguments need to have their live ranges extended to the beginning of
943 * the method to account for the arg reg/memory -> global register copies
944 * in the prolog (bug #74992).
946 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
947 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
948 if ((cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
) && (cfg
->varinfo
[vi
->idx
] != cfg
->ret
))
949 mono_linterval_add_range (cfg
, ctx
->varinfo
[cfg
->varinfo
[i
]->dreg
].interval
, 0, 1);
954 for (idx
= 0; idx
< max_vars
; ++idx
) {
955 printf ("LIVENESS R%d: ", idx
);
956 mono_linterval_print (ctx
->varinfo
[idx
].interval
);
968 * Perform liveness analysis.
971 analyze_liveness (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
973 LIVENESS_DEBUG (printf ("LIVENESS 3 %s\n", mono_method_full_name (cfg
->method
, TRUE
)));
975 /* FIXME: Make only one pass over the IR */
977 compute_gen_kill_sets (cfg
, ctx
);
979 compute_live_in_out_sets (cfg
, ctx
);
981 compute_intervals (cfg
, ctx
);
986 compare_by_interval_start_pos_func (gconstpointer a
, gconstpointer b
)
988 MonoRegallocInterval
*v1
= (MonoRegallocInterval
*)a
;
989 MonoRegallocInterval
*v2
= (MonoRegallocInterval
*)b
;
993 else if (v1
->interval
->range
&& v2
->interval
->range
)
994 return v1
->interval
->range
->from
- v2
->interval
->range
->from
;
995 else if (v1
->interval
->range
)
1001 #define LSCAN_DEBUG(a) MINI_DEBUG(cfg->verbose_level, 2, a;)
1006 * Split the interval into two child intervals at POS.
1007 * [a, b] becomes [a, POS - 1], [POS, b].
1010 split_interval (MonoCompile
*cfg
, MonoRegallocContext
*ctx
, MonoRegallocInterval
*interval
, int pos
)
1012 MonoRegallocInterval
*child1
, *child2
;
1013 GSList
*l
, *split_list
;
1015 child1
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoRegallocInterval
));
1016 child2
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoRegallocInterval
));
1017 child1
->vreg
= ctx
->num_intervals
++;
1019 child1
->offset
= -1;
1020 child1
->preferred_reg
= -1;
1021 child1
->is_volatile
= interval
->is_volatile
;
1022 child1
->fp
= interval
->fp
;
1023 child1
->type
= interval
->type
;
1024 child2
->vreg
= ctx
->num_intervals
++;
1026 child2
->offset
= -1;
1027 child2
->preferred_reg
= -1;
1028 child2
->is_volatile
= interval
->is_volatile
;
1029 child2
->fp
= interval
->fp
;
1030 child2
->type
= interval
->type
;
1032 interval
->child1
= child1
;
1033 interval
->child2
= child2
;
1034 child1
->parent
= interval
;
1035 child2
->parent
= interval
;
1037 mono_linterval_split (cfg
, interval
->interval
, &child1
->interval
, &child2
->interval
, pos
);
1039 /* Split use positions */
1040 for (l
= interval
->use_pos
; l
; l
= l
->next
) {
1041 int use_pos
= GPOINTER_TO_INT (l
->data
);
1044 child1
->use_pos
= g_slist_append_mempool (cfg
->mempool
, child1
->use_pos
, l
->data
);
1046 child2
->use_pos
= g_slist_append_mempool (cfg
->mempool
, child2
->use_pos
, l
->data
);
1049 /* Remember where spill code needs to be inserted */
1050 split_list
= g_hash_table_lookup (ctx
->split_positions
, GUINT_TO_POINTER (pos
));
1051 split_list
= g_slist_prepend (split_list
, interval
);
1052 g_hash_table_insert (ctx
->split_positions
, GUINT_TO_POINTER (pos
), split_list
);
1053 g_hash_table_insert (ctx
->split_position_set
, GUINT_TO_POINTER (pos
- (pos
% INS_POS_INTERVAL
)), GUINT_TO_POINTER (pos
));
1055 if (cfg
->verbose_level
> 2) {
1056 printf ("\tSplit R%d into R%d and R%d at %x\n", interval
->vreg
, child1
->vreg
, child2
->vreg
, pos
);
1057 printf ("\t R%d ", interval
->vreg
);
1058 mono_linterval_print (interval
->interval
);
1059 printf ("-> R%d ", child1
->vreg
);
1060 mono_linterval_print (child1
->interval
);
1061 printf ("||| R%d ", child2
->vreg
);
1062 mono_linterval_print (child2
->interval
);
1070 * Return L or one of its children which covers POS.
1072 static MonoRegallocInterval
*
1073 child_at (MonoRegallocInterval
*l
, int pos
)
1075 if (l
->vreg
< MONO_FIRST_VREG
)
1079 g_assert (mono_linterval_covers (l
->interval
, pos
));
1083 if (mono_linterval_covers (l
->child1
->interval
, pos
))
1084 return child_at (l
->child1
, pos
);
1085 else if (mono_linterval_covers (l
->child2
->interval
, pos
))
1086 return child_at (l
->child2
, pos
);
1088 g_assert_not_reached ();
1094 * decompose_volatile_intervals:
1096 * Decompose intervals belonging to volatile variables. Return the decomposed intervals
1097 * which should be allocated to registers.
1100 decompose_volatile_intervals (MonoCompile
*cfg
, MonoRegallocContext
*ctx
, GList
*intervals
)
1102 GList
*new_intervals
;
1106 * We model volatile intervals by splitting them at use positions and spilling the
1107 * sub intervals, ie. [a, b] is transformed to [a, a], [a + 1, b], [b, b] with the
1108 * middle interval spilled. This ensures that the variable will be spilled after each
1109 * def, and it will be loaded before each use.
1110 * FIXME: Stress test this by making most variables volatile
1112 new_intervals
= g_list_copy (intervals
);
1113 for (l
= intervals
; l
; l
= l
->next
) {
1114 MonoRegallocInterval
*current
= l
->data
;
1115 MonoLiveInterval
*new;
1117 gboolean ends_with_def
;
1119 if (!current
->is_volatile
)
1123 * Instead of trying to split the arbitrary interval produced by the liveness
1124 * analysis phase, just use one big interval.
1126 ends_with_def
= FALSE
;
1127 use_pos
= current
->use_pos
;
1129 int pos
= GPOINTER_TO_INT (use_pos
->data
);
1131 use_pos
= use_pos
->next
;
1132 if (!use_pos
&& USE_POS_IS_DEF (pos
))
1133 ends_with_def
= TRUE
;
1136 new = mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
1137 mono_linterval_add_range (cfg
, new, 0, current
->interval
->last_range
->to
+ (ends_with_def
? INS_POS_INTERVAL
: 0));
1138 current
->interval
= new;
1140 LSCAN_DEBUG (printf ("R%d is volatile ", current
->vreg
));
1141 LSCAN_DEBUG (mono_linterval_print (current
->interval
));
1142 LSCAN_DEBUG (printf ("\n"));
1144 new_intervals
= g_list_remove (new_intervals
, current
);
1146 use_pos
= current
->use_pos
;
1148 gboolean is_def
= USE_POS_IS_DEF (GPOINTER_TO_INT (use_pos
->data
));
1149 int pos
= USE_POS_BASE (GPOINTER_TO_INT (use_pos
->data
));
1150 use_pos
= use_pos
->next
;
1152 LSCAN_DEBUG (printf ("\tUse pos: %x\n", pos
));
1154 /* Split the part of the interval before the definition into its own interval */
1155 if (pos
> current
->interval
->range
->from
) {
1156 split_interval (cfg
, ctx
, current
, pos
);
1157 current
= current
->child2
;
1160 if (!is_def
&& pos
== current
->interval
->last_range
->to
) {
1161 /* No need to split the last use */
1162 new_intervals
= g_list_insert_sorted (new_intervals
, current
, compare_by_interval_start_pos_func
);
1166 /* Split the use into its own interval */
1167 split_interval (cfg
, ctx
, current
, pos
+ INS_POS_INTERVAL
);
1168 new_intervals
= g_list_insert_sorted (new_intervals
, current
->child1
, compare_by_interval_start_pos_func
);
1169 current
= current
->child2
;
1171 /* No need to (and hard to) split between use positions at the same place */
1172 while (use_pos
&& USE_POS_BASE (GPOINTER_TO_INT (use_pos
->data
)) == pos
)
1173 use_pos
= use_pos
->next
;
1177 return new_intervals
;
1183 * The actual linear scan register allocation algorithm.
1186 linear_scan (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
1188 GList
*int_regs
= mono_arch_get_global_int_regs (cfg
);
1189 GList
*fp_regs
= mono_arch_get_global_fp_regs (cfg
);
1191 GList
*unhandled
, *active
, *inactive
, *l
, *next
;
1192 gint32 free_pos
[MONO_MAX_IREGS
+ MONO_MAX_FREGS
];
1193 gboolean allocateable
[MONO_MAX_IREGS
+ MONO_MAX_FREGS
];
1195 MonoMethodSignature
*sig
;
1196 MonoMethodHeader
*header
;
1198 LSCAN_DEBUG (printf ("\nLINEAR SCAN 2 for %s:\n", mono_method_full_name (cfg
->method
, TRUE
)));
1200 header
= cfg
->header
;
1202 sig
= mono_method_signature (cfg
->method
);
1204 /* Create list of allocatable variables */
1206 for (i
= MONO_FIRST_VREG
; i
< cfg
->next_vreg
; ++i
) {
1207 if (ctx
->varinfo
[i
].interval
->range
)
1208 vars
= g_list_prepend (vars
, &ctx
->varinfo
[i
]);
1211 for (i
= 0; i
< MONO_MAX_IREGS
; ++i
)
1212 allocateable
[i
] = g_list_find (int_regs
, GINT_TO_POINTER (i
)) != NULL
;
1213 for (i
= 0; i
< MONO_MAX_FREGS
; ++i
)
1214 allocateable
[MONO_MAX_IREGS
+ i
] = g_list_find (fp_regs
, GINT_TO_POINTER (i
)) != NULL
;
1215 g_list_free (int_regs
);
1216 g_list_free (fp_regs
);
1218 unhandled
= g_list_sort (g_list_copy (vars
), compare_by_interval_start_pos_func
);
1222 /* The hard registers are assigned to themselves */
1223 for (i
= 0; i
< MONO_MAX_IREGS
+ MONO_MAX_FREGS
; ++i
) {
1224 ctx
->varinfo
[i
].hreg
= i
;
1225 if (ctx
->varinfo
[i
].interval
->range
)
1226 inactive
= g_list_append (inactive
, &ctx
->varinfo
[i
]);
1229 unhandled
= decompose_volatile_intervals (cfg
, ctx
, unhandled
);
1232 * Handle arguments received on the stack by splitting their interval, and later
1233 * allocating the spilled part to the arg location.
1235 for (i
= 0; i
< sig
->param_count
+ sig
->hasthis
; ++i
) {
1236 MonoInst
*ins
= cfg
->args
[i
];
1237 MonoRegallocInterval
*current
= &ctx
->varinfo
[ins
->dreg
];
1240 if (sig
->hasthis
&& (i
== 0))
1241 arg_type
= &mono_defaults
.object_class
->byval_arg
;
1243 arg_type
= sig
->params
[i
- sig
->hasthis
];
1245 if (ins
->opcode
!= OP_REGVAR
&& !MONO_TYPE_ISSTRUCT (arg_type
) && !current
->is_volatile
&& current
->interval
->range
) {
1246 /* This ensures there is some part of the interval before the use pos */
1247 g_assert (current
->interval
->range
->from
== 0);
1249 /* Have to split at an use pos so a spill load can be inserted */
1250 if (current
->use_pos
) {
1251 guint32 pos
= USE_POS_BASE (GPOINTER_TO_INT (current
->use_pos
->data
));
1253 split_interval (cfg
, ctx
, current
, pos
);
1254 unhandled
= g_list_remove (unhandled
, current
);
1255 unhandled
= g_list_insert_sorted (unhandled
, current
->child2
, compare_by_interval_start_pos_func
);
1261 MonoRegallocInterval
*current
= unhandled
->data
;
1262 int pos
, reg
, max_free_pos
;
1265 unhandled
= g_list_delete_link (unhandled
, unhandled
);
1267 LSCAN_DEBUG (printf ("Processing R%d: ", current
->vreg
));
1268 LSCAN_DEBUG (mono_linterval_print (current
->interval
));
1269 LSCAN_DEBUG (printf ("\n"));
1271 if (!current
->interval
->range
)
1274 /* Happens when splitting intervals */
1275 if (!current
->use_pos
)
1278 pos
= current
->interval
->range
->from
;
1280 /* Check for intervals in active which expired or inactive */
1282 /* FIXME: Optimize this */
1285 MonoRegallocInterval
*v
= l
->data
;
1288 if (v
->interval
->last_range
->to
< pos
) {
1289 active
= g_list_delete_link (active
, l
);
1290 LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", v
->vreg
));
1291 } else if (!mono_linterval_covers (v
->interval
, pos
)) {
1292 inactive
= g_list_append (inactive
, v
);
1293 active
= g_list_delete_link (active
, l
);
1294 LSCAN_DEBUG (printf ("\tInterval R%d became inactive\n", v
->vreg
));
1299 /* Check for intervals in inactive which are expired or active */
1302 MonoRegallocInterval
*v
= l
->data
;
1305 if (v
->interval
->last_range
->to
< pos
) {
1306 inactive
= g_list_delete_link (inactive
, l
);
1307 LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", v
->vreg
));
1308 } else if (mono_linterval_covers (v
->interval
, pos
)) {
1309 active
= g_list_append (active
, v
);
1310 inactive
= g_list_delete_link (inactive
, l
);
1311 LSCAN_DEBUG (printf ("\tInterval R%d became active\n", v
->vreg
));
1316 /* Find a register for the current interval */
1317 if (G_UNLIKELY (current
->fp
)) {
1318 for (i
= MONO_MAX_IREGS
; i
< MONO_MAX_IREGS
+ MONO_MAX_FREGS
; ++i
)
1319 if (allocateable
[i
])
1320 free_pos
[i
] = G_MAXINT32
;
1324 for (i
= 0; i
< MONO_MAX_IREGS
; ++i
)
1325 if (allocateable
[i
])
1326 free_pos
[i
] = G_MAXINT32
;
1331 for (l
= active
; l
!= NULL
; l
= l
->next
) {
1332 MonoRegallocInterval
*v
= l
->data
;
1335 free_pos
[v
->hreg
] = 0;
1336 LSCAN_DEBUG (printf ("\threg %d is busy (R%d)\n", v
->hreg
, v
->vreg
));
1340 for (l
= inactive
; l
!= NULL
; l
= l
->next
) {
1341 MonoRegallocInterval
*v
= l
->data
;
1342 gint32 intersect_pos
;
1344 if ((v
->hreg
>= 0) && (current
->fp
== v
->fp
)) {
1345 intersect_pos
= mono_linterval_get_intersect_pos (current
->interval
, v
->interval
);
1346 if (intersect_pos
!= -1) {
1347 if (intersect_pos
< free_pos
[v
->hreg
])
1348 free_pos
[v
->hreg
] = intersect_pos
;
1349 LSCAN_DEBUG (printf ("\threg %d becomes free at %x\n", v
->hreg
, intersect_pos
));
1359 * Arguments should be allocated to the registers they reside in at the start of
1362 for (i
= 0; i
< sig
->param_count
+ sig
->hasthis
; ++i
) {
1363 MonoInst
*ins
= cfg
->args
[i
];
1365 g_assert (ins
->opcode
== OP_REGVAR
);
1366 if (ins
->dreg
== current
->vreg
)
1372 if (G_UNLIKELY (current
->fp
)) {
1373 for (i
= MONO_MAX_IREGS
; i
< MONO_MAX_IREGS
+ MONO_MAX_FREGS
; ++i
)
1374 if (free_pos
[i
] > max_free_pos
) {
1376 max_free_pos
= free_pos
[i
];
1379 for (i
= 0; i
< MONO_MAX_IREGS
; ++i
)
1380 if (free_pos
[i
] > max_free_pos
) {
1382 max_free_pos
= free_pos
[i
];
1386 if (current
->preferred_reg
!= -1) {
1387 LSCAN_DEBUG (printf ("\tPreferred register is hreg %d\n", current
->preferred_reg
));
1388 /* FIXME: Add more cases */
1389 if (free_pos
[current
->preferred_reg
] >= free_pos
[reg
]) {
1390 reg
= current
->preferred_reg
;
1394 * We have a choice to make: assigning to the preferred reg avoids
1395 * a move, while assigning to 'reg' will keep the variable in a
1396 * register for longer.
1398 if (free_pos
[current
->preferred_reg
] >= current
->interval
->range
->from
)
1399 reg
= current
->preferred_reg
;
1405 g_assert (reg
!= -1);
1407 if (!(free_pos
[reg
] > 0 && free_pos
[reg
] >= current
->interval
->range
->from
) &&
1408 USE_POS_BASE (GPOINTER_TO_INT (current
->use_pos
->data
)) <= current
->interval
->range
->from
) {
1410 * No register is available, and current is needed in a register right now.
1411 * So free up a register by spilling an interval in active.
1413 MonoRegallocInterval
*to_spill
;
1416 // FIXME: Why was this needed ?
1417 //g_assert (!current->is_volatile);
1419 /* Spill the first */
1420 /* FIXME: Optimize the selection of the interval */
1423 for (l
= active
; l
; l
= l
->next
) {
1426 /* Fixed intervals cannot be spilled */
1427 if (to_spill
->vreg
>= MONO_FIRST_VREG
)
1430 g_assert (to_spill
);
1432 LSCAN_DEBUG (printf ("\tNo free register found, splitting and spilling R%d\n", to_spill
->vreg
));
1433 split_pos
= USE_POS_BASE (GPOINTER_TO_INT (current
->use_pos
->data
));
1435 * Avoid splitting to_spill before the start of current, since
1436 * its second child, which is added to unhandled would begin before
1439 if (split_pos
< current
->interval
->range
->from
)
1440 split_pos
= current
->interval
->range
->from
;
1441 split_interval (cfg
, ctx
, to_spill
, split_pos
);
1442 to_spill
->child1
->hreg
= to_spill
->hreg
;
1443 active
= g_list_remove (active
, to_spill
);
1444 unhandled
= g_list_insert_sorted (unhandled
, to_spill
->child2
, compare_by_interval_start_pos_func
);
1445 reg
= to_spill
->hreg
;
1447 /* Recompute free_pos [reg] */
1448 free_pos
[reg
] = G_MAXINT32
;
1449 for (l
= active
; l
!= NULL
; l
= l
->next
) {
1450 MonoRegallocInterval
*v
= l
->data
;
1452 if (v
->hreg
== reg
) {
1453 free_pos
[v
->hreg
] = 0;
1454 LSCAN_DEBUG (printf ("\threg %d is busy (R%d)\n", v
->hreg
, v
->vreg
));
1458 for (l
= inactive
; l
!= NULL
; l
= l
->next
) {
1459 MonoRegallocInterval
*v
= l
->data
;
1460 gint32 intersect_pos
;
1462 if ((v
->hreg
== reg
) && (current
->fp
== v
->fp
)) {
1463 intersect_pos
= mono_linterval_get_intersect_pos (current
->interval
, v
->interval
);
1464 if (intersect_pos
!= -1) {
1465 if (intersect_pos
< free_pos
[v
->hreg
])
1466 free_pos
[v
->hreg
] = intersect_pos
;
1467 LSCAN_DEBUG (printf ("\threg %d becomes free at %x\n", v
->hreg
, intersect_pos
));
1473 if (free_pos
[reg
] > 0 && free_pos
[reg
] >= current
->interval
->last_range
->to
) {
1474 /* Register available for whole interval */
1475 current
->hreg
= reg
;
1477 cfg
->used_int_regs
|= (1 << reg
);
1478 LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg
, current
->vreg
));
1480 active
= g_list_append (active
, current
);
1482 else if (free_pos
[reg
] > 0 && free_pos
[reg
] >= current
->interval
->range
->from
) {
1484 * The register is available for some part of the interval.
1485 * Split the interval, assign the register to the first part of the
1486 * interval, and save the second part for later processing.
1488 LSCAN_DEBUG (printf ("\tRegister %d is available until %x, splitting current.\n", reg
, free_pos
[reg
]));
1489 split_interval (cfg
, ctx
, current
, free_pos
[reg
]);
1491 current
->child1
->hreg
= reg
;
1493 cfg
->used_int_regs
|= (1 << reg
);
1494 LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg
, current
->child1
->vreg
));
1495 active
= g_list_append (active
, current
->child1
);
1497 unhandled
= g_list_insert_sorted (unhandled
, current
->child2
, compare_by_interval_start_pos_func
);
1499 guint32 use_pos
= USE_POS_BASE (GPOINTER_TO_INT (current
->use_pos
->data
));
1501 /* No register is available */
1502 if (use_pos
> current
->interval
->range
->from
) {
1504 * The interval is not currently needed in a register. So split it, and
1505 * spill the first part to memory, and save the second part for later
1508 LSCAN_DEBUG (printf ("\tSplitting R%d(current) at first use pos %x, spilling the first part.\n", current
->vreg
, use_pos
));
1509 split_interval (cfg
, ctx
, current
, use_pos
);
1510 unhandled
= g_list_insert_sorted (unhandled
, current
->child2
, compare_by_interval_start_pos_func
);
1512 /* Handled previously */
1513 g_assert_not_reached ();
1519 * The fp registers are numbered from MONO_MAX_IREGS during allocation, but they are
1520 * numbered from 0 in machine code.
1522 for (i
= 0; i
< cfg
->next_vreg
; ++i
) {
1523 if (ctx
->varinfo
[i
].fp
) {
1526 /* Need to process child intervals as well */
1527 /* This happens rarely so it is not perf critical */
1529 children
= g_slist_prepend (children
, &ctx
->varinfo
[i
]);
1531 MonoRegallocInterval
*interval
= children
->data
;
1533 children
= g_slist_delete_link (children
, children
);
1534 if (interval
->hreg
!= -1)
1535 interval
->hreg
-= MONO_MAX_IREGS
;
1536 if (interval
->child1
)
1537 children
= g_slist_prepend (children
, interval
->child1
);
1538 if (interval
->child2
)
1539 children
= g_slist_prepend (children
, interval
->child2
);
1546 collect_spilled_intervals (MonoRegallocInterval
*interval
, GSList
*list
)
1548 if ((interval
->hreg
== -1) && !interval
->child1
&& interval
->interval
->range
)
1549 list
= g_slist_prepend (list
, interval
);
1551 if (interval
->is_volatile
&& !interval
->interval
->range
)
1552 /* Variables which are only referenced by ldaddr */
1553 list
= g_slist_prepend (list
, interval
);
1555 if (interval
->child1
) {
1556 list
= collect_spilled_intervals (interval
->child1
, list
);
1557 list
= collect_spilled_intervals (interval
->child2
, list
);
1564 alloc_spill_slot (MonoCompile
*cfg
, guint32 size
, guint32 align
)
1569 res
= cfg
->stack_offset
;
1571 if (cfg
->flags
& MONO_CFG_HAS_SPILLUP
) {
1572 cfg
->stack_offset
+= align
- 1;
1573 cfg
->stack_offset
&= ~(align
- 1);
1574 res
= cfg
->stack_offset
;
1575 cfg
->stack_offset
+= size
;
1577 cfg
->stack_offset
+= align
- 1;
1578 cfg
->stack_offset
&= ~(align
- 1);
1579 cfg
->stack_offset
+= size
;
1580 res
= - cfg
->stack_offset
;
1588 assign_spill_slots (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
1590 GSList
*spilled_intervals
= NULL
;
1592 MonoMethodSignature
*sig
;
1595 /* Handle arguments passed on the stack */
1596 sig
= mono_method_signature (cfg
->method
);
1597 for (i
= 0; i
< sig
->param_count
+ sig
->hasthis
; ++i
) {
1598 MonoInst
*ins
= cfg
->args
[i
];
1601 if (sig
->hasthis
&& (i
== 0))
1602 arg_type
= &mono_defaults
.object_class
->byval_arg
;
1604 arg_type
= sig
->params
[i
- sig
->hasthis
];
1606 if (MONO_TYPE_ISSTRUCT (arg_type
) || (ins
->opcode
!= OP_REGVAR
)) {
1607 g_assert (ins
->opcode
== OP_REGOFFSET
);
1608 // FIXME: Add a basereg field to varinfo
1610 g_assert (ins
->inst_offset
!= -1);
1611 ctx
->varinfo
[ins
->dreg
].offset
= ins
->inst_offset
;
1615 /* Handle a vtype return */
1616 if (!cfg
->vret_addr
&& MONO_TYPE_ISSTRUCT (sig
->ret
)) {
1617 MonoInst
*ins
= cfg
->ret
;
1619 ctx
->varinfo
[ins
->dreg
].offset
= ins
->inst_offset
;
1622 for (i
= 0; i
< cfg
->next_vreg
; ++i
) {
1623 spilled_intervals
= collect_spilled_intervals (&ctx
->varinfo
[i
], spilled_intervals
);
1626 LSCAN_DEBUG (printf ("\nSPILL OFFSETS:\n\n"));
1628 for (l
= spilled_intervals
; l
; l
= l
->next
) {
1629 MonoRegallocInterval
*interval
= l
->data
;
1630 MonoRegallocInterval
*parent
;
1633 * All spilled sub-intervals of a interval must share the stack slot.
1634 * This is accomplished by storing the stack offset in the original interval
1635 * and using that offset for all its children.
1638 for (parent
= interval
; parent
->parent
!= NULL
; parent
= parent
->parent
)
1640 if (parent
->offset
!= -1) {
1641 interval
->offset
= parent
->offset
;
1642 } else if (interval
->offset
!= -1) {
1643 /* Already allocated (for example, valuetypes as arguments) */
1645 guint32 size
, align
;
1647 if (MONO_TYPE_ISSTRUCT (interval
->type
)) {
1648 // FIXME: pinvoke, gsctx
1650 size
= mini_type_stack_size (NULL
, interval
->type
, NULL
);
1651 } else if (interval
->fp
) {
1652 size
= sizeof (double);
1654 size
= sizeof (gpointer
);
1657 align
= sizeof (gpointer
);
1658 interval
->offset
= alloc_spill_slot (cfg
, size
, align
);
1661 for (parent
= interval
; parent
!= NULL
; parent
= parent
->parent
) {
1662 if (parent
->offset
== -1)
1663 parent
->offset
= interval
->offset
;
1666 LSCAN_DEBUG (printf ("R%d %d", interval
->vreg
, interval
->offset
));
1667 LSCAN_DEBUG (mono_linterval_print (interval
->interval
));
1668 LSCAN_DEBUG (printf ("\n"));
1671 /* Write back information needed by the backend */
1672 if (cfg
->rgctx_var
) {
1673 /* rgctx_var is marked as volatile, so it won't be allocated to a register */
1674 cfg
->rgctx_var
->opcode
= OP_REGOFFSET
;
1675 cfg
->rgctx_var
->inst_basereg
= cfg
->frame_reg
;
1676 cfg
->rgctx_var
->inst_offset
= ctx
->varinfo
[cfg
->rgctx_var
->dreg
].offset
;
1683 * Order the instructions in MOVES so earlier moves don't overwrite the sources of
1687 order_moves (MonoCompile
*cfg
, MonoRegallocContext
*ctx
, MonoInst
**moves
, int nmoves
)
1693 * Sort the moves so earlier moves don't overwrite the sources of later
1696 /* FIXME: Do proper cycle detection instead of the current ugly hack */
1698 for (i
= 0; i
< nmoves
; ++i
) {
1704 for (j
= i
+ 1; j
< nmoves
; ++j
)
1705 if (moves
[i
]->dreg
== moves
[j
]->sreg1
) {
1713 moves
[j
] = moves
[i
];
1717 if (niter
> nmoves
* 2)
1718 /* Possible cycle */
1722 if (niter
> nmoves
* 2)
1727 if (niter
> nmoves
* 2) {
1732 * Save all registers to the stack and reload them again.
1733 * FIXME: Optimize this.
1736 /* Allocate spill slots */
1737 offsets
= mono_mempool_alloc (cfg
->mempool
, nmoves
* sizeof (int));
1738 for (i
= 0; i
< nmoves
; ++i
) {
1739 guint32 size
= sizeof (gpointer
);
1741 if (cfg
->flags
& MONO_CFG_HAS_SPILLUP
) {
1742 cfg
->stack_offset
+= size
- 1;
1743 cfg
->stack_offset
&= ~(size
- 1);
1744 offsets
[i
] = cfg
->stack_offset
;
1745 cfg
->stack_offset
+= size
;
1747 cfg
->stack_offset
+= size
- 1;
1748 cfg
->stack_offset
&= ~(size
- 1);
1749 cfg
->stack_offset
+= size
;
1750 offsets
[i
] = - cfg
->stack_offset
;
1755 for (i
= 0; i
< nmoves
; ++i
) {
1756 if (moves
[i
]->opcode
== OP_MOVE
)
1757 MONO_INST_NEW (cfg
, ins
, OP_STORE_MEMBASE_REG
);
1758 else if (moves
[i
]->opcode
== OP_FMOVE
)
1759 MONO_INST_NEW (cfg
, ins
, OP_STORER8_MEMBASE_REG
);
1762 ins
->sreg1
= moves
[i
]->sreg1
;
1763 ins
->inst_destbasereg
= cfg
->frame_reg
;
1764 ins
->inst_offset
= offsets
[i
];
1766 l
= g_slist_append_mempool (cfg
->mempool
, l
, ins
);
1767 g_hash_table_insert (ctx
->spill_ins
, ins
, ins
);
1771 for (i
= 0; i
< nmoves
; ++i
) {
1772 if (moves
[i
]->opcode
== OP_MOVE
)
1773 MONO_INST_NEW (cfg
, ins
, OP_LOAD_MEMBASE
);
1774 else if (moves
[i
]->opcode
== OP_FMOVE
)
1775 MONO_INST_NEW (cfg
, ins
, OP_LOADR8_MEMBASE
);
1778 ins
->dreg
= moves
[i
]->dreg
;
1779 ins
->inst_basereg
= cfg
->frame_reg
;
1780 ins
->inst_offset
= offsets
[i
];
1782 l
= g_slist_append_mempool (cfg
->mempool
, l
, ins
);
1783 g_hash_table_insert (ctx
->spill_ins
, ins
, ins
);
1788 for (i
= 0; i
< nmoves
; ++i
)
1789 l
= g_slist_append_mempool (cfg
->mempool
, l
, moves
[i
]);
1798 * Add spill loads and stores to the IR at the locations where intervals were split.
1801 add_spill_code (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
1804 MonoInst
*ins
, *prev
, *store
, *load
, *move
, *insert_after
;
1805 GSList
*spill_list
, *l
, *ins_to_add
, *moves_to_add
;
1806 MonoRegallocInterval
*child1
, *child2
;
1807 int pos
, pos_interval
, pos_interval_limit
;
1808 MonoBasicBlock
*out_bb
;
1809 int i
, bb_count
, from_pos
, to_pos
, iter
;
1810 gboolean after_last_ins
, add_at_head
;
1812 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
1813 if (cfg
->verbose_level
> 1)
1814 printf ("\nREGALLOC-ADD SPILL CODE %d (DFN 0x%x):\n", bb
->block_num
, bb
->dfn
);
1816 /* First pass: Add spill loads/stores to the IR */
1817 pos
= (bb
->dfn
<< 16) + INS_POS_INTERVAL
;
1819 after_last_ins
= FALSE
;
1820 for (ins
= bb
->code
; !after_last_ins
;) {
1822 after_last_ins
= TRUE
;
1823 } else if (g_hash_table_lookup (ctx
->spill_ins
, ins
)) {
1824 /* Spill instruction added by an earlier bblock */
1825 /* No need to increase pos */
1827 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
1828 printf (" <spill ins>\n");
1836 if (!g_hash_table_lookup (ctx
->split_position_set
, GUINT_TO_POINTER (pos
))) {
1837 /* No split position at this instruction */
1838 pos_interval_limit
= 0;
1839 pos
+= INS_POS_INTERVAL
;
1841 pos_interval_limit
= INS_POS_INTERVAL
;
1845 * This is the most complex/hackish part of the allocator, but I failed to
1846 * make it any simpler.
1847 * FIXME FIXME FIXME: CLEAN THIS UP
1849 for (pos_interval
= 0; pos_interval
< pos_interval_limit
; ++pos_interval
) {
1850 spill_list
= g_hash_table_lookup (ctx
->split_positions
, GUINT_TO_POINTER (pos
));
1851 /* Insert stores first, then loads so registers don't get overwritten */
1852 for (iter
= 0; iter
< 2; ++iter
) {
1853 for (l
= spill_list
; l
; l
= l
->next
) {
1854 MonoRegallocInterval
*interval
= l
->data
;
1856 /* The childs might be split */
1857 if (interval
->child1
->child1
)
1858 child1
= child_at (interval
->child1
, pos
- pos_interval
);
1860 child1
= interval
->child1
;
1861 if (pos
< interval
->child2
->interval
->range
->from
)
1862 /* Happens when volatile intervals are split */
1864 child2
= child_at (interval
->child2
, pos
);
1866 if ((child1
->hreg
== -1) && (child2
->hreg
== -1))
1868 * Happens when an interval is split, then the first child
1873 // FIXME: Why is !is_volatile needed ?
1874 // It seems to fail when the same volatile var is a source and a
1875 // destination of the same instruction
1876 if ((iter
== 0) && (child1
->hreg
!= -1) && (child2
->hreg
!= -1) && !interval
->is_volatile
&& pos_interval
> 0) {
1880 * This is complex situation: the vreg is expected to be in
1881 * child1->hreg before the instruction, and in child2->hreg
1882 * after the instruction. We can't insert a move before,
1883 * because that could overwrite the input regs of the
1884 * instruction, and we can't insert a move after, since the
1885 * instruction could overwrite the source reg of the move.
1886 * Instead, we insert a store before the instruction, and a
1888 * FIXME: Optimize child1->hreg == child2->hreg
1890 offset
= alloc_spill_slot (cfg
, sizeof (gpointer
), sizeof (gpointer
));
1892 NEW_STORE_MEMBASE (cfg
, store
, mono_type_to_store_membase (cfg
, interval
->type
), cfg
->frame_reg
, offset
, child1
->hreg
);
1894 mono_bblock_insert_after_ins (bb
, prev
, store
);
1896 g_hash_table_insert (ctx
->spill_ins
, store
, store
);
1898 NEW_LOAD_MEMBASE (cfg
, load
, mono_type_to_load_membase (cfg
, interval
->type
), child2
->hreg
, cfg
->frame_reg
, offset
);
1900 mono_bblock_insert_after_ins (bb
, ins
, load
);
1901 g_hash_table_insert (ctx
->spill_ins
, load
, load
);
1903 LSCAN_DEBUG (printf (" Spill store/load added for R%d (R%d -> R%d) at %x\n", interval
->vreg
, child1
->vreg
, child2
->vreg
, pos
));
1904 } else if ((iter
== 0) && (child1
->hreg
!= -1) && (child2
->hreg
!= -1) && (child1
->hreg
!= child2
->hreg
) && pos_interval
== 0) {
1905 /* Happens with volatile intervals, i.e. in
1908 * R1's interval is split between the two instructions.
1910 // FIXME: This should be done in iter 1, but it has
1911 // ordering problems with other loads. Now it might have
1912 // ordering problems with stores.
1913 g_assert (!interval
->fp
);
1914 move
= create_move (cfg
, child2
->hreg
, child1
->hreg
);
1915 mono_bblock_insert_before_ins (bb
, ins
, move
);
1917 g_hash_table_insert (ctx
->spill_ins
, move
, move
);
1918 } else if ((iter
== 0) && (child1
->hreg
!= -1) && (child2
->hreg
== -1)) {
1919 g_assert (child2
->offset
!= -1);
1921 NEW_STORE_MEMBASE (cfg
, store
, mono_type_to_store_membase (cfg
, interval
->type
), cfg
->frame_reg
, child2
->offset
, child1
->hreg
);
1923 mono_bblock_insert_after_ins (bb
, prev
, store
);
1925 g_hash_table_insert (ctx
->spill_ins
, store
, store
);
1927 LSCAN_DEBUG (printf (" Spill store added for R%d (R%d -> R%d) at %x\n", interval
->vreg
, child1
->vreg
, child2
->vreg
, pos
));
1928 } else if ((iter
== 1) && (child1
->hreg
== -1) && (child2
->hreg
!= -1)) {
1929 g_assert (child1
->offset
!= -1);
1930 NEW_LOAD_MEMBASE (cfg
, load
, mono_type_to_load_membase (cfg
, interval
->type
), child2
->hreg
, cfg
->frame_reg
, child1
->offset
);
1932 if (pos_interval
>= INS_POS_DEF
)
1933 /* Happens in InternalGetChars, couldn't create a testcase */
1934 mono_bblock_insert_after_ins (bb
, ins
, load
);
1936 mono_bblock_insert_before_ins (bb
, ins
, load
);
1939 g_hash_table_insert (ctx
->spill_ins
, load
, load
);
1941 LSCAN_DEBUG (printf (" Spill load added for R%d (R%d -> R%d) at %x\n", interval
->vreg
, child1
->vreg
, child2
->vreg
, pos
));
1949 if (G_UNLIKELY (cfg
->verbose_level
> 1))
1951 mono_print_ins (ins
);
1959 /* Second pass: Resolve data flow */
1960 for (bb_count
= 0; bb_count
< bb
->out_count
; ++bb_count
) {
1961 out_bb
= bb
->out_bb
[bb_count
];
1963 if (!out_bb
->live_in_set
)
1964 /* Exception handling block */
1967 from_pos
= (bb
->dfn
<< 16) + 0xffff;
1968 to_pos
= (out_bb
->dfn
<< 16);
1971 for (i
= 0; i
< cfg
->next_vreg
; ++i
) {
1972 MonoRegallocInterval
*interval
= &ctx
->varinfo
[i
];
1974 if (mono_bitset_test_fast (out_bb
->live_in_set
, i
) && mono_linterval_covers (interval
->interval
, from_pos
) && mono_linterval_covers (interval
->interval
, to_pos
)) {
1975 child1
= child_at (interval
, from_pos
);
1976 child2
= child_at (interval
, to_pos
);
1977 if (child1
!= child2
) {
1978 if ((child1
->hreg
!= -1) && (child2
->hreg
== -1)) {
1979 LSCAN_DEBUG (printf (" Add store for R%d (R%d -> R%d) at BB%d -> BB%d [%x - %x]\n", interval
->vreg
, child1
->vreg
, child2
->vreg
, bb
->block_num
, out_bb
->block_num
, from_pos
, to_pos
));
1980 NEW_STORE_MEMBASE (cfg
, store
, mono_type_to_store_membase (cfg
, interval
->type
), cfg
->frame_reg
, child2
->offset
, child1
->hreg
);
1981 ins_to_add
= g_slist_prepend_mempool (cfg
->mempool
, ins_to_add
, store
);
1982 g_hash_table_insert (ctx
->spill_ins
, store
, store
);
1983 } else if ((child1
->hreg
!= -1) && (child2
->hreg
!= -1)) {
1984 if (child1
->hreg
!= child2
->hreg
) {
1985 LSCAN_DEBUG (printf (" Add move for R%d (R%d -> R%d) at BB%d -> BB%d [%x - %x]\n", interval
->vreg
, child1
->vreg
, child2
->vreg
, bb
->block_num
, out_bb
->block_num
, from_pos
, to_pos
));
1986 NEW_UNALU (cfg
, move
, interval
->fp
? OP_FMOVE
: OP_MOVE
, child2
->hreg
, child1
->hreg
);
1987 ins_to_add
= g_slist_prepend_mempool (cfg
->mempool
, ins_to_add
, move
);
1988 g_hash_table_insert (ctx
->spill_ins
, move
, move
);
1990 } else if ((child1
->hreg
== -1) && (child2
->hreg
!= -1)) {
1991 LSCAN_DEBUG (printf (" Add load for R%d (R%d -> R%d) at BB%d -> BB%d [%x - %x]\n", interval
->vreg
, child1
->vreg
, child2
->vreg
, bb
->block_num
, out_bb
->block_num
, from_pos
, to_pos
));
1992 NEW_LOAD_MEMBASE (cfg
, load
, mono_type_to_load_membase (cfg
, interval
->type
), child2
->hreg
, cfg
->frame_reg
, child1
->offset
);
1993 ins_to_add
= g_slist_prepend_mempool (cfg
->mempool
, ins_to_add
, load
);
1994 g_hash_table_insert (ctx
->spill_ins
, load
, load
);
1996 g_assert (child1
->offset
== child2
->offset
);
2002 if (bb
->out_count
== 1) {
2004 } else if (out_bb
->in_count
== 1) {
2005 add_at_head
= FALSE
;
2007 // FIXME: Split critical edges
2012 insert_after
= NULL
;
2019 * Emit spill instructions in such a way that instructions don't
2020 * overwrite the source registers of instructions coming after them.
2022 /* Simply emit stores, then moves then loads */
2023 for (l
= ins_to_add
; l
; l
= l
->next
) {
2024 MonoInst
*ins
= l
->data
;
2026 if (MONO_IS_STORE_MEMBASE (ins
)) {
2028 mono_add_ins_to_end (bb
, ins
);
2030 mono_bblock_insert_after_ins (out_bb
, insert_after
, ins
);
2036 /* Collect the moves */
2038 for (l
= ins_to_add
; l
; l
= l
->next
) {
2039 MonoInst
*ins
= l
->data
;
2041 if (MONO_IS_MOVE (ins
))
2044 moves
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoInst
*) * nmoves
);
2046 for (l
= ins_to_add
; l
; l
= l
->next
) {
2047 MonoInst
*ins
= l
->data
;
2049 if (MONO_IS_MOVE (ins
))
2050 moves
[nmoves
++] = ins
;
2053 moves_to_add
= order_moves (cfg
, ctx
, moves
, nmoves
);
2055 for (l
= moves_to_add
; l
; l
= l
->next
) {
2056 MonoInst
*ins
= l
->data
;
2059 mono_add_ins_to_end (bb
, ins
);
2061 mono_bblock_insert_after_ins (out_bb
, insert_after
, ins
);
2066 for (l
= ins_to_add
; l
; l
= l
->next
) {
2067 MonoInst
*ins
= l
->data
;
2069 if (MONO_IS_LOAD_MEMBASE (ins
)) {
2071 mono_add_ins_to_end (bb
, ins
);
2073 mono_bblock_insert_after_ins (out_bb
, insert_after
, ins
);
2086 * Replace references to vregs with their assigned physical registers or spill
2090 rewrite_code (MonoCompile
*cfg
, MonoRegallocContext
*ctx
)
2093 MonoInst
*ins
, *prev
;
2097 defs
= g_new (MonoInst
*, MONO_MAX_IREGS
+ MONO_MAX_FREGS
);
2099 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
2100 if (cfg
->verbose_level
> 1)
2101 printf ("\nREGALLOC-REWRITE BLOCK %d:\n", bb
->block_num
);
2103 memset (defs
, 0, sizeof (MonoInst
*) * (MONO_MAX_IREGS
+ MONO_MAX_FREGS
));
2105 pos
= (bb
->dfn
<< 16);
2107 MONO_BB_FOR_EACH_INS (bb
, ins
) {
2108 const char *spec
= INS_INFO (ins
->opcode
);
2109 pos
+= INS_POS_INTERVAL
;
2111 if (G_UNLIKELY (cfg
->verbose_level
> 1))
2112 mono_print_ins (ins
);
2114 if (g_hash_table_lookup (ctx
->spill_ins
, ins
)) {
2116 * This instruction was added after liveness info was computed, and thus
2117 * screws up the pos calculation. The instruction already uses hregs.
2119 pos
-= INS_POS_INTERVAL
;
2125 if (ins
->opcode
== OP_NOP
)
2128 if (ins
->opcode
== OP_LDADDR
) {
2129 MonoRegallocInterval
*l
= child_at (&ctx
->varinfo
[ins
->dreg
], pos
+ INS_POS_DEF
);
2130 MonoInst
*var
= ins
->inst_p0
;
2133 g_assert (ctx
->varinfo
[var
->dreg
].hreg
== -1);
2134 g_assert (ctx
->varinfo
[var
->dreg
].offset
!= -1);
2136 if (ctx
->varinfo
[var
->dreg
].offset
!= 0) {
2138 * The ADD_IMM does not satisfy register constraints on x86/amd64.
2140 MONO_INST_NEW (cfg
, move
, OP_MOVE
);
2141 move
->dreg
= l
->hreg
;
2142 move
->sreg1
= cfg
->frame_reg
;
2143 mono_bblock_insert_before_ins (bb
, ins
, move
);
2145 ins
->opcode
= OP_ADD_IMM
;
2146 ins
->dreg
= l
->hreg
;
2147 ins
->sreg1
= l
->hreg
;
2148 ins
->inst_imm
= ctx
->varinfo
[var
->dreg
].offset
;
2149 defs
[ins
->dreg
] = ins
;
2151 ins
->opcode
= OP_MOVE
;
2152 ins
->dreg
= l
->hreg
;
2153 ins
->sreg1
= cfg
->frame_reg
;
2154 defs
[ins
->dreg
] = ins
;
2156 spec
= INS_INFO (OP_NOP
);
2159 * We need to fold these instructions into the instructions which
2160 * use them, but we can't call mono_local_cprop () since that could
2161 * generate code which doesn't obey register constraints.
2162 * So we do it manually.
2166 if (spec
[MONO_INST_DEST
] != ' ') {
2167 if (MONO_IS_STORE_MEMBASE (ins
)) {
2168 MonoRegallocInterval
*l
= child_at (&ctx
->varinfo
[ins
->dreg
], pos
+ INS_POS_USE
);
2169 g_assert (l
->hreg
!= -1);
2170 ins
->dreg
= l
->hreg
;
2172 /* Fold the instruction computing the address */
2173 /* FIXME: fails in generics-sharing.2.exe
2174 def = defs [ins->dreg];
2175 if (def && def->opcode == OP_MOVE && def->sreg1 == cfg->frame_reg) {
2176 ins->dreg = cfg->frame_reg;
2177 } else if (def && def->opcode == OP_ADD_IMM && def->sreg1 == cfg->frame_reg) {
2178 ins->dreg = cfg->frame_reg;
2179 ins->inst_destbasereg += def->inst_imm;
2183 * FIXME: Deadce the def. This is hard to do, since it could be
2184 * accessed in other bblocks.
2187 MonoRegallocInterval
*l
= child_at (&ctx
->varinfo
[ins
->dreg
], pos
+ INS_POS_DEF
);
2188 g_assert (l
->hreg
!= -1);
2189 ins
->dreg
= l
->hreg
;
2190 defs
[ins
->dreg
] = NULL
;
2193 if (spec
[MONO_INST_SRC1
] != ' ') {
2194 MonoRegallocInterval
*l
= child_at (&ctx
->varinfo
[ins
->sreg1
], pos
+ INS_POS_USE
);
2195 g_assert (l
->hreg
!= -1);
2196 ins
->sreg1
= l
->hreg
;
2199 def = defs [ins->sreg1];
2200 if (def && def->opcode == OP_MOVE && def->sreg1 == cfg->frame_reg)
2201 ins->sreg1 = cfg->frame_reg;
2204 if (spec
[MONO_INST_SRC2
] != ' ') {
2205 MonoRegallocInterval
*l
= child_at (&ctx
->varinfo
[ins
->sreg2
], pos
+ INS_POS_USE
);
2206 g_assert (l
->hreg
!= -1);
2207 ins
->sreg2
= l
->hreg
;
2210 if (cfg
->verbose_level
> 1)
2211 mono_print_ins_index (1, ins
);
2220 static MonoRegallocContext
*
2221 regalloc_ctx_create (MonoCompile
*cfg
)
2223 MonoRegallocContext
*ctx
;
2226 ctx
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoRegallocContext
));
2228 ctx
->varinfo
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoRegallocInterval
) * cfg
->next_vreg
);
2229 ctx
->num_intervals
= cfg
->next_vreg
;
2230 for (i
= 0; i
< cfg
->next_vreg
; ++i
) {
2233 ctx
->varinfo
[i
].vreg
= i
;
2234 ctx
->varinfo
[i
].hreg
= -1;
2235 ctx
->varinfo
[i
].offset
= -1;
2236 ctx
->varinfo
[i
].preferred_reg
= -1;
2238 if (i
>= MONO_MAX_IREGS
&& i
< MONO_MAX_IREGS
+ MONO_MAX_FREGS
)
2239 ctx
->varinfo
[i
].fp
= TRUE
;
2241 var
= get_vreg_to_inst (cfg
, i
);
2242 if (var
&& (var
!= cfg
->ret
) && (var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
2243 ctx
->varinfo
[i
].is_volatile
= TRUE
;
2246 ctx
->varinfo
[i
].type
= var
->inst_vtype
;
2248 ctx
->varinfo
[i
].type
= sizeof (gpointer
) == 8 ? &mono_defaults
.int64_class
->byval_arg
: &mono_defaults
.int_class
->byval_arg
;
2251 ctx
->split_positions
= g_hash_table_new (NULL
, NULL
);
2252 ctx
->split_position_set
= g_hash_table_new (NULL
, NULL
);
2253 ctx
->spill_ins
= g_hash_table_new (NULL
, NULL
);
2259 mono_global_regalloc (MonoCompile
*cfg
)
2261 MonoRegallocContext
*ctx
;
2263 mono_arch_fill_argument_info (cfg
);
2265 /* This could create vregs, so it has to come before ctx_create */
2266 handle_reg_constraints (cfg
);
2268 ctx
= regalloc_ctx_create (cfg
);
2270 collect_fp_vregs (cfg
, ctx
);
2272 analyze_liveness (cfg
, ctx
);
2274 linear_scan (cfg
, ctx
);
2276 mono_arch_allocate_vars (cfg
);
2278 assign_spill_slots (cfg
, ctx
);
2280 add_spill_code (cfg
, ctx
);
2282 rewrite_code (cfg
, ctx
);
2288 mono_global_regalloc (MonoCompile
*cfg
)