6 * Dietmar Maurer (dietmar@ximian.com)
8 * (C) 2002 Ximian, Inc.
9 * Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
10 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
14 #include <mono/utils/mono-compiler.h>
20 #define SPILL_COST_INCREMENT (1 << (bb->nesting << 1))
22 #define DEBUG_LIVENESS
24 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
26 #define BB_ID_SHIFT 18
29 * The liveness2 pass can't handle long vars on 32 bit platforms because the component
30 * vars have the same 'idx'.
32 #if SIZEOF_REGISTER == 8
33 #define ENABLE_LIVENESS2
36 #ifdef ENABLE_LIVENESS2
37 static void mono_analyze_liveness2 (MonoCompile
*cfg
);
41 #define INLINE_SIZE 16
46 gpointer data
[INLINE_SIZE
];
47 GHashTable
*hashtable
;
52 mono_ptrset_init (MonoPtrSet
*set
)
58 mono_ptrset_destroy (MonoPtrSet
*set
)
60 if (set
->capacity
> INLINE_SIZE
)
61 g_hash_table_destroy (set
->hashtable
);
65 mono_ptrset_add (MonoPtrSet
*set
, gpointer val
)
68 if (set
->capacity
== INLINE_SIZE
) {
69 GHashTable
*tmp
= g_hash_table_new (NULL
, NULL
);
70 for (int i
= 0; i
< INLINE_SIZE
; ++i
)
71 g_hash_table_insert (tmp
, set
->data
[i
], set
->data
[i
]);
76 if (set
->capacity
> INLINE_SIZE
) {
77 g_hash_table_insert (set
->hashtable
, val
, val
);
79 set
->data
[set
->capacity
] = val
;
85 mono_ptrset_contains (MonoPtrSet
*set
, gpointer val
)
87 if (set
->capacity
<= INLINE_SIZE
) {
88 for (int i
= 0; i
< set
->capacity
; ++i
) {
89 if (set
->data
[i
] == val
)
95 return g_hash_table_lookup (set
->hashtable
, val
) != NULL
;
100 optimize_initlocals (MonoCompile
*cfg
);
102 /* mono_bitset_mp_new:
104 * allocates a MonoBitSet inside a memory pool
106 static inline MonoBitSet
*
107 mono_bitset_mp_new (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
109 guint8
*mem
= (guint8
*)mono_mempool_alloc0 (mp
, size
);
110 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
113 static inline MonoBitSet
*
114 mono_bitset_mp_new_noinit (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
116 guint8
*mem
= (guint8
*)mono_mempool_alloc (mp
, size
);
117 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
120 G_GNUC_UNUSED
static void
121 mono_bitset_print (MonoBitSet
*set
)
124 gboolean first
= TRUE
;
127 for (i
= 0; i
< mono_bitset_size (set
); i
++) {
129 if (mono_bitset_test (set
, i
)) {
140 visit_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoPtrSet
*visited
)
145 if (mono_ptrset_contains (visited
, bb
))
148 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
149 const char *spec
= INS_INFO (ins
->opcode
);
150 int regtype
, srcindex
, sreg
, num_sregs
;
151 int sregs
[MONO_MAX_SRC_REGS
];
153 if (ins
->opcode
== OP_NOP
)
157 regtype
= spec
[MONO_INST_DEST
];
158 g_assert (((ins
->dreg
== -1) && (regtype
== ' ')) || ((ins
->dreg
!= -1) && (regtype
!= ' ')));
160 if ((ins
->dreg
!= -1) && get_vreg_to_inst (cfg
, ins
->dreg
)) {
161 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
162 int idx
= var
->inst_c0
;
163 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
165 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
166 if (SIZEOF_REGISTER
== 4 && (var
->type
== STACK_I8
|| (var
->type
== STACK_R8
&& COMPILE_SOFT_FLOAT (cfg
)))) {
167 /* Make the component vregs volatile as well (#612206) */
168 get_vreg_to_inst (cfg
, MONO_LVREG_LS (var
->dreg
))->flags
|= MONO_INST_VOLATILE
;
169 get_vreg_to_inst (cfg
, MONO_LVREG_MS (var
->dreg
))->flags
|= MONO_INST_VOLATILE
;
174 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
175 for (srcindex
= 0; srcindex
< num_sregs
; ++srcindex
) {
176 sreg
= sregs
[srcindex
];
178 g_assert (sreg
!= -1);
179 if (get_vreg_to_inst (cfg
, sreg
)) {
180 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
181 int idx
= var
->inst_c0
;
182 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
184 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
185 if (SIZEOF_REGISTER
== 4 && (var
->type
== STACK_I8
|| (var
->type
== STACK_R8
&& COMPILE_SOFT_FLOAT (cfg
)))) {
186 /* Make the component vregs volatile as well (#612206) */
187 get_vreg_to_inst (cfg
, MONO_LVREG_LS (var
->dreg
))->flags
|= MONO_INST_VOLATILE
;
188 get_vreg_to_inst (cfg
, MONO_LVREG_MS (var
->dreg
))->flags
|= MONO_INST_VOLATILE
;
194 mono_ptrset_add (visited
, bb
);
197 * Need to visit all bblocks reachable from this one since they can be
198 * reached during exception handling.
200 for (i
= 0; i
< bb
->out_count
; ++i
) {
201 visit_bb (cfg
, bb
->out_bb
[i
], visited
);
206 mono_liveness_handle_exception_clauses (MonoCompile
*cfg
)
209 MonoMethodHeader
*header
= cfg
->header
;
210 MonoExceptionClause
*clause
, *clause2
;
215 * Determine which clauses are outer try clauses, i.e. they are not contained in any
216 * other non-try clause.
218 outer_try
= (gboolean
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (gboolean
) * header
->num_clauses
);
219 for (i
= 0; i
< header
->num_clauses
; ++i
)
220 outer_try
[i
] = TRUE
;
221 /* Iterate over the clauses backward, so outer clauses come first */
222 /* This avoids doing an O(2) search, since we can determine when inner clauses end */
223 for (i
= header
->num_clauses
- 1; i
>= 0; --i
) {
224 clause
= &header
->clauses
[i
];
226 if (clause
->flags
!= 0) {
227 outer_try
[i
] = TRUE
;
228 /* Iterate over inner clauses */
229 for (j
= i
- 1; j
>= 0; --j
) {
230 clause2
= &header
->clauses
[j
];
232 if (clause2
->flags
== 0 && MONO_OFFSET_IN_HANDLER (clause
, clause2
->try_offset
)) {
233 outer_try
[j
] = FALSE
;
236 if (clause2
->try_offset
< clause
->try_offset
)
237 /* End of inner clauses */
244 mono_ptrset_init (&visited
);
246 * Variables in exception handler register cannot be allocated to registers
247 * so make them volatile. See bug #42136. This will not be neccessary when
248 * the back ends could guarantee that the variables will be in the
249 * correct registers when a handler is called.
250 * This includes try blocks too, since a variable in a try block might be
251 * accessed after an exception handler has been run.
253 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
255 if (bb
->region
== -1)
258 if (MONO_BBLOCK_IS_IN_REGION (bb
, MONO_REGION_TRY
) && outer_try
[MONO_REGION_CLAUSE_INDEX (bb
->region
)])
261 if (cfg
->verbose_level
> 2)
262 printf ("pessimize variables in bb %d.\n", bb
->block_num
);
264 visit_bb (cfg
, bb
, &visited
);
266 mono_ptrset_destroy (&visited
);
270 update_live_range (MonoMethodVar
*var
, int abs_pos
)
272 if (var
->range
.first_use
.abs_pos
> abs_pos
)
273 var
->range
.first_use
.abs_pos
= abs_pos
;
275 if (var
->range
.last_use
.abs_pos
< abs_pos
)
276 var
->range
.last_use
.abs_pos
= abs_pos
;
280 analyze_liveness_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
)
284 MonoMethodVar
*vars
= cfg
->vars
;
285 guint32 abs_pos
= (bb
->dfn
<< BB_ID_SHIFT
);
287 /* Start inst_num from > 0, so last_use.abs_pos is only 0 for dead variables */
288 for (inst_num
= 2, ins
= bb
->code
; ins
; ins
= ins
->next
, inst_num
+= 2) {
289 const char *spec
= INS_INFO (ins
->opcode
);
291 int sregs
[MONO_MAX_SRC_REGS
];
293 #ifdef DEBUG_LIVENESS
294 if (cfg
->verbose_level
> 1) {
295 mono_print_ins_index (1, ins
);
299 if (ins
->opcode
== OP_NOP
)
302 if (ins
->opcode
== OP_LDADDR
) {
303 MonoInst
*var
= (MonoInst
*)ins
->inst_p0
;
304 int idx
= var
->inst_c0
;
305 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
307 #ifdef DEBUG_LIVENESS
308 if (cfg
->verbose_level
> 1)
309 printf ("\tGEN: R%d(%d)\n", var
->dreg
, idx
);
311 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
312 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
313 mono_bitset_set_fast (bb
->gen_set
, idx
);
314 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
317 /* SREGs must come first, so MOVE r <- r is handled correctly */
318 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
319 for (i
= 0; i
< num_sregs
; ++i
) {
321 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
322 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
323 int idx
= var
->inst_c0
;
324 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
326 #ifdef DEBUG_LIVENESS
327 if (cfg
->verbose_level
> 1)
328 printf ("\tGEN: R%d(%d)\n", sreg
, idx
);
330 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
331 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
332 mono_bitset_set_fast (bb
->gen_set
, idx
);
333 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
338 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
339 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
340 int idx
= var
->inst_c0
;
341 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
343 if (MONO_IS_STORE_MEMBASE (ins
)) {
344 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
345 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
346 mono_bitset_set_fast (bb
->gen_set
, idx
);
347 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
349 #ifdef DEBUG_LIVENESS
350 if (cfg
->verbose_level
> 1)
351 printf ("\tKILL: R%d(%d)\n", ins
->dreg
, idx
);
353 update_live_range (&vars
[idx
], abs_pos
+ inst_num
+ 1);
354 mono_bitset_set_fast (bb
->kill_set
, idx
);
355 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
361 /* generic liveness analysis code. CFG specific parts are
362 * in update_gen_kill_set()
365 mono_analyze_liveness (MonoCompile
*cfg
)
367 MonoBitSet
*old_live_out_set
;
368 int i
, j
, max_vars
= cfg
->num_varinfo
;
370 gboolean
*in_worklist
;
371 MonoBasicBlock
**worklist
;
375 #ifdef DEBUG_LIVENESS
376 if (cfg
->verbose_level
> 1)
377 printf ("\nLIVENESS:\n");
380 g_assert (!(cfg
->comp_done
& MONO_COMP_LIVENESS
));
382 cfg
->comp_done
|= MONO_COMP_LIVENESS
;
387 bitsize
= mono_bitset_alloc_size (max_vars
, 0);
389 for (i
= 0; i
< max_vars
; i
++) {
390 MONO_VARINFO (cfg
, i
)->range
.first_use
.abs_pos
= ~ 0;
391 MONO_VARINFO (cfg
, i
)->range
.last_use
.abs_pos
= 0;
392 MONO_VARINFO (cfg
, i
)->spill_costs
= 0;
395 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
396 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
398 bb
->gen_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
399 bb
->kill_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
401 #ifdef DEBUG_LIVENESS
402 if (cfg
->verbose_level
> 1) {
403 printf ("BLOCK BB%d (", bb
->block_num
);
404 for (j
= 0; j
< bb
->out_count
; j
++)
405 printf ("BB%d, ", bb
->out_bb
[j
]->block_num
);
411 analyze_liveness_bb (cfg
, bb
);
413 #ifdef DEBUG_LIVENESS
414 if (cfg
->verbose_level
> 1) {
415 printf ("GEN BB%d: ", bb
->block_num
); mono_bitset_print (bb
->gen_set
);
416 printf ("KILL BB%d: ", bb
->block_num
); mono_bitset_print (bb
->kill_set
);
421 old_live_out_set
= mono_bitset_new (max_vars
, 0);
422 in_worklist
= g_new0 (gboolean
, cfg
->num_bblocks
+ 1);
424 worklist
= g_new (MonoBasicBlock
*, cfg
->num_bblocks
+ 1);
428 * This is a backward dataflow analysis problem, so we process blocks in
429 * decreasing dfn order, this speeds up the iteration.
431 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
432 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
434 worklist
[l_end
++] = bb
;
435 in_worklist
[bb
->dfn
] = TRUE
;
437 /* Initialized later */
438 bb
->live_in_set
= NULL
;
439 bb
->live_out_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
444 if (cfg
->verbose_level
> 1)
445 printf ("\nITERATION:\n");
448 MonoBasicBlock
*bb
= worklist
[--l_end
];
449 MonoBasicBlock
*out_bb
;
452 in_worklist
[bb
->dfn
] = FALSE
;
454 #ifdef DEBUG_LIVENESS
455 if (cfg
->verbose_level
> 1) {
456 printf ("P: BB%d(%d): IN: ", bb
->block_num
, bb
->dfn
);
457 for (j
= 0; j
< bb
->in_count
; ++j
)
458 printf ("BB%d ", bb
->in_bb
[j
]->block_num
);
460 for (j
= 0; j
< bb
->out_count
; ++j
)
461 printf ("BB%d ", bb
->out_bb
[j
]->block_num
);
467 if (bb
->out_count
== 0)
472 if (!bb
->live_in_set
) {
473 /* First pass over this bblock */
478 mono_bitset_copyto_fast (bb
->live_out_set
, old_live_out_set
);
481 for (j
= 0; j
< bb
->out_count
; j
++) {
482 out_bb
= bb
->out_bb
[j
];
484 if (!out_bb
->live_in_set
) {
485 out_bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
487 mono_bitset_copyto_fast (out_bb
->live_out_set
, out_bb
->live_in_set
);
488 mono_bitset_sub_fast (out_bb
->live_in_set
, out_bb
->kill_set
);
489 mono_bitset_union_fast (out_bb
->live_in_set
, out_bb
->gen_set
);
492 // FIXME: Do this somewhere else
493 if (bb
->last_ins
&& bb
->last_ins
->opcode
== OP_NOT_REACHED
) {
495 mono_bitset_union_fast (bb
->live_out_set
, out_bb
->live_in_set
);
499 if (changed
|| !mono_bitset_equal (old_live_out_set
, bb
->live_out_set
)) {
500 if (!bb
->live_in_set
)
501 bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
502 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
503 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
504 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
506 for (j
= 0; j
< bb
->in_count
; j
++) {
507 MonoBasicBlock
*in_bb
= bb
->in_bb
[j
];
509 * Some basic blocks do not seem to be in the
510 * cfg->bblocks array...
512 if (in_bb
->gen_set
&& !in_worklist
[in_bb
->dfn
]) {
513 #ifdef DEBUG_LIVENESS
514 if (cfg
->verbose_level
> 1)
515 printf ("\tADD: %d\n", in_bb
->block_num
);
518 * Put the block at the top of the stack, so it
519 * will be processed right away.
521 worklist
[l_end
++] = in_bb
;
522 in_worklist
[in_bb
->dfn
] = TRUE
;
527 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
528 printf ("\tLIVE IN BB%d: ", bb
->block_num
);
529 mono_bitset_print (bb
->live_in_set
);
533 #ifdef DEBUG_LIVENESS
534 if (cfg
->verbose_level
> 1)
535 printf ("IT: %d %d.\n", cfg
->num_bblocks
, out_iter
);
538 mono_bitset_free (old_live_out_set
);
541 g_free (in_worklist
);
543 /* Compute live_in_set for bblocks skipped earlier */
544 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
545 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
547 if (!bb
->live_in_set
) {
548 bb
->live_in_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
550 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
551 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
552 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
556 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
557 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
559 guint32 abs_pos
= (bb
->dfn
<< BB_ID_SHIFT
);
560 MonoMethodVar
*vars
= cfg
->vars
;
562 if (!bb
->live_out_set
)
565 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
566 for (j
= 0; j
< max
; ++j
) {
571 bits_in
= mono_bitset_get_fast (bb
->live_in_set
, j
);
572 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
574 k
= (j
* BITS_PER_CHUNK
);
575 while ((bits_in
|| bits_out
)) {
577 update_live_range (&vars
[k
], abs_pos
+ 0);
579 update_live_range (&vars
[k
], abs_pos
+ ((1 << BB_ID_SHIFT
) - 1));
588 * Arguments need to have their live ranges extended to the beginning of
589 * the method to account for the arg reg/memory -> global register copies
590 * in the prolog (bug #74992).
593 for (i
= 0; i
< max_vars
; i
++) {
594 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
595 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
) {
596 if (vi
->range
.last_use
.abs_pos
== 0 && !(cfg
->varinfo
[vi
->idx
]->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
598 * Can't eliminate the this variable in gshared code, since
599 * it is needed during exception handling to identify the
601 * It is better to check for this here instead of marking the variable
602 * VOLATILE, since that would prevent it from being allocated to
605 if (!cfg
->disable_deadce_vars
&& !(cfg
->gshared
&& mono_method_signature_internal (cfg
->method
)->hasthis
&& cfg
->varinfo
[vi
->idx
] == cfg
->args
[0]))
606 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_IS_DEAD
;
608 vi
->range
.first_use
.abs_pos
= 0;
612 #ifdef DEBUG_LIVENESS
613 if (cfg
->verbose_level
> 1) {
614 for (i
= cfg
->num_bblocks
- 1; i
>= 0; i
--) {
615 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
617 printf ("LIVE IN BB%d: ", bb
->block_num
);
618 mono_bitset_print (bb
->live_in_set
);
619 printf ("LIVE OUT BB%d: ", bb
->block_num
);
620 mono_bitset_print (bb
->live_out_set
);
623 for (i
= 0; i
< max_vars
; i
++) {
624 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
626 printf ("V%d: [0x%x - 0x%x]\n", i
, vi
->range
.first_use
.abs_pos
, vi
->range
.last_use
.abs_pos
);
631 if (!cfg
->disable_initlocals_opt
)
632 optimize_initlocals (cfg
);
634 #ifdef ENABLE_LIVENESS2
635 /* This improves code size by about 5% but slows down compilation too much */
636 if (cfg
->compile_aot
)
637 mono_analyze_liveness2 (cfg
);
642 * optimize_initlocals:
644 * Try to optimize away some of the redundant initialization code inserted because of
645 * 'locals init' using the liveness information.
648 optimize_initlocals (MonoCompile
*cfg
)
652 MonoBasicBlock
*initlocals_bb
;
654 used
= mono_bitset_new (cfg
->next_vreg
+ 1, 0);
656 mono_bitset_clear_all (used
);
657 initlocals_bb
= cfg
->bb_entry
->next_bb
;
658 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
660 int sregs
[MONO_MAX_SRC_REGS
];
662 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
663 for (i
= 0; i
< num_sregs
; ++i
)
664 mono_bitset_set_fast (used
, sregs
[i
]);
666 if (MONO_IS_STORE_MEMBASE (ins
))
667 mono_bitset_set_fast (used
, ins
->dreg
);
670 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
671 const char *spec
= INS_INFO (ins
->opcode
);
673 /* Look for statements whose dest is not used in this bblock and not live on exit. */
674 if ((spec
[MONO_INST_DEST
] != ' ') && !MONO_IS_STORE_MEMBASE (ins
)) {
675 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
677 if (var
&& !mono_bitset_test_fast (used
, ins
->dreg
) && !mono_bitset_test_fast (initlocals_bb
->live_out_set
, var
->inst_c0
) && (var
!= cfg
->ret
) && !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
678 //printf ("DEAD: "); mono_print_ins (ins);
679 if (cfg
->disable_initlocals_opt_refs
&& var
->type
== STACK_OBJ
)
681 if ((ins
->opcode
== OP_ICONST
) || (ins
->opcode
== OP_I8CONST
) || (ins
->opcode
== OP_R8CONST
) || (ins
->opcode
== OP_R4CONST
)) {
683 MONO_VARINFO (cfg
, var
->inst_c0
)->spill_costs
-= 1;
685 * We should shorten the liveness interval of these vars as well, but
686 * don't have enough info to do that.
697 mono_linterval_add_range (MonoCompile
*cfg
, MonoLiveInterval
*interval
, int from
, int to
)
699 MonoLiveRange2
*prev_range
, *next_range
, *new_range
;
701 g_assert (to
>= from
);
703 /* Optimize for extending the first interval backwards */
704 if (G_LIKELY (interval
->range
&& (interval
->range
->from
> from
) && (interval
->range
->from
== to
))) {
705 interval
->range
->from
= from
;
709 /* Find a place in the list for the new range */
711 next_range
= interval
->range
;
712 while ((next_range
!= NULL
) && (next_range
->from
<= from
)) {
713 prev_range
= next_range
;
714 next_range
= next_range
->next
;
717 if (prev_range
&& prev_range
->to
== from
) {
718 /* Merge with previous */
720 } else if (next_range
&& next_range
->from
== to
) {
721 /* Merge with previous */
722 next_range
->from
= from
;
725 new_range
= (MonoLiveRange2
*)mono_mempool_alloc (cfg
->mempool
, sizeof (MonoLiveRange2
));
726 new_range
->from
= from
;
728 new_range
->next
= NULL
;
731 prev_range
->next
= new_range
;
733 interval
->range
= new_range
;
735 new_range
->next
= next_range
;
737 interval
->last_range
= new_range
;
740 /* FIXME: Merge intersecting ranges */
744 mono_linterval_print (MonoLiveInterval
*interval
)
746 MonoLiveRange2
*range
;
748 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
)
749 printf ("[%x-%x] ", range
->from
, range
->to
);
753 mono_linterval_print_nl (MonoLiveInterval
*interval
)
755 mono_linterval_print (interval
);
760 * mono_linterval_convers:
762 * Return whenever INTERVAL covers the position POS.
765 mono_linterval_covers (MonoLiveInterval
*interval
, int pos
)
767 MonoLiveRange2
*range
;
769 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
) {
770 if (pos
>= range
->from
&& pos
<= range
->to
)
772 if (range
->from
> pos
)
780 * mono_linterval_get_intersect_pos:
782 * Determine whenever I1 and I2 intersect, and if they do, return the first
783 * point of intersection. Otherwise, return -1.
786 mono_linterval_get_intersect_pos (MonoLiveInterval
*i1
, MonoLiveInterval
*i2
)
788 MonoLiveRange2
*r1
, *r2
;
790 /* FIXME: Optimize this */
791 for (r1
= i1
->range
; r1
!= NULL
; r1
= r1
->next
) {
792 for (r2
= i2
->range
; r2
!= NULL
; r2
= r2
->next
) {
793 if (r2
->to
> r1
->from
&& r2
->from
< r1
->to
) {
794 if (r2
->from
<= r1
->from
)
806 * mono_linterval_split
808 * Split L at POS and store the newly created intervals into L1 and L2. POS becomes
812 mono_linterval_split (MonoCompile
*cfg
, MonoLiveInterval
*interval
, MonoLiveInterval
**i1
, MonoLiveInterval
**i2
, int pos
)
816 g_assert (pos
> interval
->range
->from
&& pos
<= interval
->last_range
->to
);
818 *i1
= (MonoLiveInterval
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
819 *i2
= (MonoLiveInterval
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
821 for (r
= interval
->range
; r
; r
= r
->next
) {
823 /* Add it to the first child */
824 mono_linterval_add_range (cfg
, *i1
, r
->from
, r
->to
);
825 } else if (pos
> r
->from
&& pos
<= r
->to
) {
827 mono_linterval_add_range (cfg
, *i1
, r
->from
, pos
- 1);
828 mono_linterval_add_range (cfg
, *i2
, pos
, r
->to
);
830 /* Add it to the second child */
831 mono_linterval_add_range (cfg
, *i2
, r
->from
, r
->to
);
837 #define LIVENESS_DEBUG(a) do { if (cfg->verbose_level > 1) do { a; } while (0); } while (0)
838 #define ENABLE_LIVENESS_DEBUG 1
840 #define LIVENESS_DEBUG(a)
843 #ifdef ENABLE_LIVENESS2
846 update_liveness2 (MonoCompile
*cfg
, MonoInst
*ins
, gboolean set_volatile
, int inst_num
, gint32
*last_use
)
848 const char *spec
= INS_INFO (ins
->opcode
);
851 int sregs
[MONO_MAX_SRC_REGS
];
853 LIVENESS_DEBUG (printf ("\t%x: ", inst_num
); mono_print_ins (ins
));
855 if (ins
->opcode
== OP_NOP
|| ins
->opcode
== OP_IL_SEQ_POINT
)
859 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
860 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
861 int idx
= var
->inst_c0
;
862 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
864 if (MONO_IS_STORE_MEMBASE (ins
)) {
865 if (last_use
[idx
] == 0) {
866 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins
->dreg
, inst_num
));
867 last_use
[idx
] = inst_num
;
870 if (last_use
[idx
] > 0) {
871 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", ins
->dreg
, inst_num
, last_use
[idx
]));
872 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, last_use
[idx
]);
876 /* Try dead code elimination */
877 if (!cfg
->disable_deadce_vars
&& (var
!= cfg
->ret
) && !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
)) && ((ins
->opcode
== OP_ICONST
) || (ins
->opcode
== OP_I8CONST
) || (ins
->opcode
== OP_R8CONST
)) && !(var
->flags
& MONO_INST_VOLATILE
)) {
878 LIVENESS_DEBUG (printf ("\tdead def of R%d, eliminated\n", ins
->dreg
));
882 int inst_num_add
= 1;
883 MonoInst
*next
= ins
->next
;
884 while (next
&& next
->opcode
== OP_IL_SEQ_POINT
) {
889 LIVENESS_DEBUG (printf ("\tdead def of R%d, add range to R%d: [%x, %x]\n", ins
->dreg
, ins
->dreg
, inst_num
, inst_num
+ inst_num_add
));
890 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, inst_num
+ inst_num_add
);
897 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
898 for (i
= 0; i
< num_sregs
; ++i
) {
900 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
901 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
902 int idx
= var
->inst_c0
;
904 if (last_use
[idx
] == 0) {
905 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
));
906 last_use
[idx
] = inst_num
;
913 mono_analyze_liveness2 (MonoCompile
*cfg
)
915 int bnum
, idx
, i
, j
, nins
, max
, max_vars
, block_from
, block_to
, pos
;
917 static guint32 disabled
= -1;
920 disabled
= g_hasenv ("DISABLED");
925 if (cfg
->num_bblocks
>= (1 << (32 - BB_ID_SHIFT
- 1)))
926 /* Ranges would overflow */
929 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
930 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
934 for (nins
= 0, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
)
937 if (nins
>= ((1 << BB_ID_SHIFT
) - 1))
938 /* Ranges would overflow */
942 LIVENESS_DEBUG (printf ("LIVENESS 2 %s\n", mono_method_full_name (cfg
->method
, TRUE
)));
945 if (strstr (cfg->method->name, "test_") != cfg->method->name)
949 max_vars
= cfg
->num_varinfo
;
950 last_use
= g_new0 (gint32
, max_vars
);
952 for (idx
= 0; idx
< max_vars
; ++idx
) {
953 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
955 vi
->interval
= (MonoLiveInterval
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
959 * Process bblocks in reverse order, so the addition of new live ranges
960 * to the intervals is faster.
962 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
963 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
966 block_from
= (bb
->dfn
<< BB_ID_SHIFT
) + 1; /* so pos > 0 */
967 if (bnum
< cfg
->num_bblocks
- 1)
968 /* Beginning of the next bblock */
969 block_to
= (cfg
->bblocks
[bnum
+ 1]->dfn
<< BB_ID_SHIFT
) + 1;
971 block_to
= (bb
->dfn
<< BB_ID_SHIFT
) + ((1 << BB_ID_SHIFT
) - 1);
973 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb
->block_num
));
975 memset (last_use
, 0, max_vars
* sizeof (gint32
));
977 /* For variables in bb->live_out, set last_use to block_to */
979 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
980 for (j
= 0; j
< max
; ++j
) {
984 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
985 k
= (j
* BITS_PER_CHUNK
);
988 LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", cfg
->varinfo
[k
]->dreg
, block_to
));
989 last_use
[k
] = block_to
;
997 last_use
[cfg
->ret
->inst_c0
] = block_to
;
999 pos
= block_from
+ 1;
1000 MONO_BB_FOR_EACH_INS (bb
, ins
) pos
++;
1002 /* Process instructions backwards */
1003 MONO_BB_FOR_EACH_INS_REVERSE (bb
, ins
) {
1004 update_liveness2 (cfg
, ins
, FALSE
, pos
, last_use
);
1008 for (idx
= 0; idx
< max_vars
; ++idx
) {
1009 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1011 if (last_use
[idx
] != 0) {
1012 /* Live at exit, not written -> live on enter */
1013 LIVENESS_DEBUG (printf ("Var R%d live at enter, add range to R%d: [%x, %x)\n", cfg
->varinfo
[idx
]->dreg
, cfg
->varinfo
[idx
]->dreg
, block_from
, last_use
[idx
]));
1014 mono_linterval_add_range (cfg
, vi
->interval
, block_from
, last_use
[idx
]);
1020 * Arguments need to have their live ranges extended to the beginning of
1021 * the method to account for the arg reg/memory -> global register copies
1022 * in the prolog (bug #74992).
1024 for (i
= 0; i
< max_vars
; i
++) {
1025 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
1026 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
)
1027 mono_linterval_add_range (cfg
, vi
->interval
, 0, 1);
1031 for (idx
= 0; idx
< max_vars
; ++idx
) {
1032 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1034 LIVENESS_DEBUG (printf ("LIVENESS R%d: ", cfg
->varinfo
[idx
]->dreg
));
1035 LIVENESS_DEBUG (mono_linterval_print (vi
->interval
));
1036 LIVENESS_DEBUG (printf ("\n"));
1046 update_liveness_gc (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*ins
, gint32
*last_use
, MonoMethodVar
**vreg_to_varinfo
, GSList
**callsites
)
1048 if (ins
->opcode
== OP_GC_LIVENESS_DEF
|| ins
->opcode
== OP_GC_LIVENESS_USE
) {
1049 int vreg
= ins
->inst_c1
;
1050 MonoMethodVar
*vi
= vreg_to_varinfo
[vreg
];
1052 int pc_offset
= ins
->backend
.pc_offset
;
1054 LIVENESS_DEBUG (printf ("\t%x: ", pc_offset
); mono_print_ins (ins
));
1056 if (ins
->opcode
== OP_GC_LIVENESS_DEF
) {
1057 if (last_use
[idx
] > 0) {
1058 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", vreg
, pc_offset
, last_use
[idx
]));
1062 if (last_use
[idx
] == 0) {
1063 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", vreg
, pc_offset
));
1064 last_use
[idx
] = pc_offset
;
1067 } else if (ins
->opcode
== OP_GC_PARAM_SLOT_LIVENESS_DEF
) {
1070 /* Add it to the last callsite */
1071 g_assert (*callsites
);
1072 last
= (GCCallSite
*)(*callsites
)->data
;
1073 last
->param_slots
= g_slist_prepend_mempool (cfg
->mempool
, last
->param_slots
, ins
);
1074 } else if (ins
->flags
& MONO_INST_GC_CALLSITE
) {
1075 GCCallSite
*callsite
= (GCCallSite
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (GCCallSite
));
1078 LIVENESS_DEBUG (printf ("\t%x: ", ins
->backend
.pc_offset
); mono_print_ins (ins
));
1079 LIVENESS_DEBUG (printf ("\t\tlive: "));
1082 callsite
->liveness
= (guint8
*)mono_mempool_alloc0 (cfg
->mempool
, ALIGN_TO (cfg
->num_varinfo
, 8) / 8);
1083 callsite
->pc_offset
= ins
->backend
.pc_offset
;
1084 for (i
= 0; i
< cfg
->num_varinfo
; ++i
) {
1085 if (last_use
[i
] != 0) {
1086 LIVENESS_DEBUG (printf ("R%d", MONO_VARINFO (cfg
, i
)->vreg
));
1087 callsite
->liveness
[i
/ 8] |= (1 << (i
% 8));
1090 LIVENESS_DEBUG (printf ("\n"));
1091 *callsites
= g_slist_prepend_mempool (cfg
->mempool
, *callsites
, callsite
);
1096 get_vreg_from_var (MonoCompile
*cfg
, MonoInst
*var
)
1098 if (var
->opcode
== OP_REGVAR
)
1099 /* dreg contains a hreg, but inst_c0 still contains the var index */
1100 return MONO_VARINFO (cfg
, var
->inst_c0
)->vreg
;
1102 /* dreg still contains the vreg */
1107 * mono_analyze_liveness_gc:
1109 * Compute liveness bitmaps for each call site.
1110 * This function is a modified version of mono_analyze_liveness2 ().
1113 mono_analyze_liveness_gc (MonoCompile
*cfg
)
1115 int idx
, i
, j
, nins
, max
, max_vars
, block_from
, block_to
, pos
, reverse_len
;
1118 MonoMethodVar
**vreg_to_varinfo
= NULL
;
1122 LIVENESS_DEBUG (printf ("\n------------ GC LIVENESS: ----------\n"));
1124 max_vars
= cfg
->num_varinfo
;
1125 last_use
= g_new0 (gint32
, max_vars
);
1128 * var->inst_c0 no longer contains the variable index, so compute a mapping now.
1130 vreg_to_varinfo
= g_new0 (MonoMethodVar
*, cfg
->next_vreg
);
1131 for (idx
= 0; idx
< max_vars
; ++idx
) {
1132 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1134 vreg_to_varinfo
[vi
->vreg
] = vi
;
1138 reverse
= (MonoInst
**)mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * reverse_len
);
1140 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
1143 block_from
= bb
->real_native_offset
;
1144 block_to
= bb
->native_offset
+ bb
->native_length
;
1146 LIVENESS_DEBUG (printf ("GC LIVENESS BB%d:\n", bb
->block_num
));
1151 memset (last_use
, 0, max_vars
* sizeof (gint32
));
1153 /* For variables in bb->live_out, set last_use to block_to */
1155 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
1156 for (j
= 0; j
< max
; ++j
) {
1160 if (!bb
->live_out_set
)
1161 /* The variables used in this bblock are volatile anyway */
1164 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
1165 k
= (j
* BITS_PER_CHUNK
);
1167 if ((bits_out
& 1) && cfg
->varinfo
[k
]->flags
& MONO_INST_GC_TRACK
) {
1168 int vreg
= get_vreg_from_var (cfg
, cfg
->varinfo
[k
]);
1169 LIVENESS_DEBUG (printf ("Var R%d live at exit, last_use set to %x.\n", vreg
, block_to
));
1170 last_use
[k
] = block_to
;
1177 for (nins
= 0, pos
= block_from
, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
, ++pos
) {
1178 if (nins
>= reverse_len
) {
1179 int new_reverse_len
= reverse_len
* 2;
1180 MonoInst
**new_reverse
= (MonoInst
**)mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * new_reverse_len
);
1181 memcpy (new_reverse
, reverse
, sizeof (MonoInst
*) * reverse_len
);
1182 reverse
= new_reverse
;
1183 reverse_len
= new_reverse_len
;
1186 reverse
[nins
] = ins
;
1189 /* Process instructions backwards */
1191 for (i
= nins
- 1; i
>= 0; --i
) {
1192 MonoInst
*ins
= (MonoInst
*)reverse
[i
];
1194 update_liveness_gc (cfg
, bb
, ins
, last_use
, vreg_to_varinfo
, &callsites
);
1196 /* The callsites should already be sorted by pc offset because we added them backwards */
1197 bb
->gc_callsites
= callsites
;
1201 g_free (vreg_to_varinfo
);
1204 #else /* !DISABLE_JIT */
1206 MONO_EMPTY_SOURCE_FILE (liveness
);
1208 #endif /* !DISABLE_JIT */