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
45 gpointer data
[INLINE_SIZE
];
49 mono_ptrset_init (MonoPtrSet
*set
)
55 mono_ptrset_destroy (MonoPtrSet
*set
)
57 if (set
->capacity
> INLINE_SIZE
)
58 g_hash_table_destroy (set
->data
[0]);
62 mono_ptrset_add (MonoPtrSet
*set
, gpointer val
)
65 if (set
->capacity
== INLINE_SIZE
) {
66 GHashTable
*tmp
= g_hash_table_new (NULL
, NULL
);
67 for (int i
= 0; i
< INLINE_SIZE
; ++i
)
68 g_hash_table_insert (tmp
, set
->data
[i
], set
->data
[i
]);
73 if (set
->capacity
> INLINE_SIZE
) {
74 g_hash_table_insert (set
->data
[0], val
, val
);
76 set
->data
[set
->capacity
] = val
;
82 mono_ptrset_contains (MonoPtrSet
*set
, gpointer val
)
84 if (set
->capacity
<= INLINE_SIZE
) {
85 for (int i
= 0; i
< set
->capacity
; ++i
) {
86 if (set
->data
[i
] == val
)
92 return g_hash_table_lookup (set
->data
[0], val
) != NULL
;
97 optimize_initlocals (MonoCompile
*cfg
);
99 /* mono_bitset_mp_new:
101 * allocates a MonoBitSet inside a memory pool
103 static inline MonoBitSet
*
104 mono_bitset_mp_new (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
106 guint8
*mem
= (guint8
*)mono_mempool_alloc0 (mp
, size
);
107 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
110 static inline MonoBitSet
*
111 mono_bitset_mp_new_noinit (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
113 guint8
*mem
= (guint8
*)mono_mempool_alloc (mp
, size
);
114 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
117 G_GNUC_UNUSED
static void
118 mono_bitset_print (MonoBitSet
*set
)
121 gboolean first
= TRUE
;
124 for (i
= 0; i
< mono_bitset_size (set
); i
++) {
126 if (mono_bitset_test (set
, i
)) {
137 visit_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoPtrSet
*visited
)
142 if (mono_ptrset_contains (visited
, bb
))
145 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
146 const char *spec
= INS_INFO (ins
->opcode
);
147 int regtype
, srcindex
, sreg
, num_sregs
;
148 int sregs
[MONO_MAX_SRC_REGS
];
150 if (ins
->opcode
== OP_NOP
)
154 regtype
= spec
[MONO_INST_DEST
];
155 g_assert (((ins
->dreg
== -1) && (regtype
== ' ')) || ((ins
->dreg
!= -1) && (regtype
!= ' ')));
157 if ((ins
->dreg
!= -1) && get_vreg_to_inst (cfg
, ins
->dreg
)) {
158 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
159 int idx
= var
->inst_c0
;
160 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
162 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
163 if (SIZEOF_REGISTER
== 4 && (var
->type
== STACK_I8
|| (var
->type
== STACK_R8
&& COMPILE_SOFT_FLOAT (cfg
)))) {
164 /* Make the component vregs volatile as well (#612206) */
165 get_vreg_to_inst (cfg
, MONO_LVREG_LS (var
->dreg
))->flags
|= MONO_INST_VOLATILE
;
166 get_vreg_to_inst (cfg
, MONO_LVREG_MS (var
->dreg
))->flags
|= MONO_INST_VOLATILE
;
171 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
172 for (srcindex
= 0; srcindex
< num_sregs
; ++srcindex
) {
173 sreg
= sregs
[srcindex
];
175 g_assert (sreg
!= -1);
176 if (get_vreg_to_inst (cfg
, sreg
)) {
177 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
178 int idx
= var
->inst_c0
;
179 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
181 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
182 if (SIZEOF_REGISTER
== 4 && (var
->type
== STACK_I8
|| (var
->type
== STACK_R8
&& COMPILE_SOFT_FLOAT (cfg
)))) {
183 /* Make the component vregs volatile as well (#612206) */
184 get_vreg_to_inst (cfg
, MONO_LVREG_LS (var
->dreg
))->flags
|= MONO_INST_VOLATILE
;
185 get_vreg_to_inst (cfg
, MONO_LVREG_MS (var
->dreg
))->flags
|= MONO_INST_VOLATILE
;
191 mono_ptrset_add (visited
, bb
);
194 * Need to visit all bblocks reachable from this one since they can be
195 * reached during exception handling.
197 for (i
= 0; i
< bb
->out_count
; ++i
) {
198 visit_bb (cfg
, bb
->out_bb
[i
], visited
);
203 mono_liveness_handle_exception_clauses (MonoCompile
*cfg
)
206 MonoMethodHeader
*header
= cfg
->header
;
207 MonoExceptionClause
*clause
, *clause2
;
212 * Determine which clauses are outer try clauses, i.e. they are not contained in any
213 * other non-try clause.
215 outer_try
= (gboolean
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (gboolean
) * header
->num_clauses
);
216 for (i
= 0; i
< header
->num_clauses
; ++i
)
217 outer_try
[i
] = TRUE
;
218 /* Iterate over the clauses backward, so outer clauses come first */
219 /* This avoids doing an O(2) search, since we can determine when inner clauses end */
220 for (i
= header
->num_clauses
- 1; i
>= 0; --i
) {
221 clause
= &header
->clauses
[i
];
223 if (clause
->flags
!= 0) {
224 outer_try
[i
] = TRUE
;
225 /* Iterate over inner clauses */
226 for (j
= i
- 1; j
>= 0; --j
) {
227 clause2
= &header
->clauses
[j
];
229 if (clause2
->flags
== 0 && MONO_OFFSET_IN_HANDLER (clause
, clause2
->try_offset
)) {
230 outer_try
[j
] = FALSE
;
233 if (clause2
->try_offset
< clause
->try_offset
)
234 /* End of inner clauses */
241 mono_ptrset_init (&visited
);
243 * Variables in exception handler register cannot be allocated to registers
244 * so make them volatile. See bug #42136. This will not be neccessary when
245 * the back ends could guarantee that the variables will be in the
246 * correct registers when a handler is called.
247 * This includes try blocks too, since a variable in a try block might be
248 * accessed after an exception handler has been run.
250 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
252 if (bb
->region
== -1)
255 if (MONO_BBLOCK_IS_IN_REGION (bb
, MONO_REGION_TRY
) && outer_try
[MONO_REGION_CLAUSE_INDEX (bb
->region
)])
258 if (cfg
->verbose_level
> 2)
259 printf ("pessimize variables in bb %d.\n", bb
->block_num
);
261 visit_bb (cfg
, bb
, &visited
);
263 mono_ptrset_destroy (&visited
);
267 update_live_range (MonoMethodVar
*var
, int abs_pos
)
269 if (var
->range
.first_use
.abs_pos
> abs_pos
)
270 var
->range
.first_use
.abs_pos
= abs_pos
;
272 if (var
->range
.last_use
.abs_pos
< abs_pos
)
273 var
->range
.last_use
.abs_pos
= abs_pos
;
277 analyze_liveness_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
)
281 MonoMethodVar
*vars
= cfg
->vars
;
282 guint32 abs_pos
= (bb
->dfn
<< BB_ID_SHIFT
);
284 /* Start inst_num from > 0, so last_use.abs_pos is only 0 for dead variables */
285 for (inst_num
= 2, ins
= bb
->code
; ins
; ins
= ins
->next
, inst_num
+= 2) {
286 const char *spec
= INS_INFO (ins
->opcode
);
288 int sregs
[MONO_MAX_SRC_REGS
];
290 #ifdef DEBUG_LIVENESS
291 if (cfg
->verbose_level
> 1) {
292 mono_print_ins_index (1, ins
);
296 if (ins
->opcode
== OP_NOP
)
299 if (ins
->opcode
== OP_LDADDR
) {
300 MonoInst
*var
= (MonoInst
*)ins
->inst_p0
;
301 int idx
= var
->inst_c0
;
302 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
304 #ifdef DEBUG_LIVENESS
305 if (cfg
->verbose_level
> 1)
306 printf ("\tGEN: R%d(%d)\n", var
->dreg
, idx
);
308 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
309 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
310 mono_bitset_set_fast (bb
->gen_set
, idx
);
311 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
314 /* SREGs must come first, so MOVE r <- r is handled correctly */
315 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
316 for (i
= 0; i
< num_sregs
; ++i
) {
318 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
319 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
320 int idx
= var
->inst_c0
;
321 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
323 #ifdef DEBUG_LIVENESS
324 if (cfg
->verbose_level
> 1)
325 printf ("\tGEN: R%d(%d)\n", sreg
, idx
);
327 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
328 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
329 mono_bitset_set_fast (bb
->gen_set
, idx
);
330 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
335 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
336 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
337 int idx
= var
->inst_c0
;
338 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
340 if (MONO_IS_STORE_MEMBASE (ins
)) {
341 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
342 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
343 mono_bitset_set_fast (bb
->gen_set
, idx
);
344 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
346 #ifdef DEBUG_LIVENESS
347 if (cfg
->verbose_level
> 1)
348 printf ("\tKILL: R%d(%d)\n", ins
->dreg
, idx
);
350 update_live_range (&vars
[idx
], abs_pos
+ inst_num
+ 1);
351 mono_bitset_set_fast (bb
->kill_set
, idx
);
352 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
358 /* generic liveness analysis code. CFG specific parts are
359 * in update_gen_kill_set()
362 mono_analyze_liveness (MonoCompile
*cfg
)
364 MonoBitSet
*old_live_out_set
;
365 int i
, j
, max_vars
= cfg
->num_varinfo
;
367 gboolean
*in_worklist
;
368 MonoBasicBlock
**worklist
;
372 #ifdef DEBUG_LIVENESS
373 if (cfg
->verbose_level
> 1)
374 printf ("\nLIVENESS:\n");
377 g_assert (!(cfg
->comp_done
& MONO_COMP_LIVENESS
));
379 cfg
->comp_done
|= MONO_COMP_LIVENESS
;
384 bitsize
= mono_bitset_alloc_size (max_vars
, 0);
386 for (i
= 0; i
< max_vars
; i
++) {
387 MONO_VARINFO (cfg
, i
)->range
.first_use
.abs_pos
= ~ 0;
388 MONO_VARINFO (cfg
, i
)->range
.last_use
.abs_pos
= 0;
389 MONO_VARINFO (cfg
, i
)->spill_costs
= 0;
392 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
393 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
395 bb
->gen_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
396 bb
->kill_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
398 #ifdef DEBUG_LIVENESS
399 if (cfg
->verbose_level
> 1) {
400 printf ("BLOCK BB%d (", bb
->block_num
);
401 for (j
= 0; j
< bb
->out_count
; j
++)
402 printf ("BB%d, ", bb
->out_bb
[j
]->block_num
);
408 analyze_liveness_bb (cfg
, bb
);
410 #ifdef DEBUG_LIVENESS
411 if (cfg
->verbose_level
> 1) {
412 printf ("GEN BB%d: ", bb
->block_num
); mono_bitset_print (bb
->gen_set
);
413 printf ("KILL BB%d: ", bb
->block_num
); mono_bitset_print (bb
->kill_set
);
418 old_live_out_set
= mono_bitset_new (max_vars
, 0);
419 in_worklist
= g_new0 (gboolean
, cfg
->num_bblocks
+ 1);
421 worklist
= g_new (MonoBasicBlock
*, cfg
->num_bblocks
+ 1);
425 * This is a backward dataflow analysis problem, so we process blocks in
426 * decreasing dfn order, this speeds up the iteration.
428 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
429 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
431 worklist
[l_end
++] = bb
;
432 in_worklist
[bb
->dfn
] = TRUE
;
434 /* Initialized later */
435 bb
->live_in_set
= NULL
;
436 bb
->live_out_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
441 if (cfg
->verbose_level
> 1)
442 printf ("\nITERATION:\n");
445 MonoBasicBlock
*bb
= worklist
[--l_end
];
446 MonoBasicBlock
*out_bb
;
449 in_worklist
[bb
->dfn
] = FALSE
;
451 #ifdef DEBUG_LIVENESS
452 if (cfg
->verbose_level
> 1) {
453 printf ("P: BB%d(%d): IN: ", bb
->block_num
, bb
->dfn
);
454 for (j
= 0; j
< bb
->in_count
; ++j
)
455 printf ("BB%d ", bb
->in_bb
[j
]->block_num
);
457 for (j
= 0; j
< bb
->out_count
; ++j
)
458 printf ("BB%d ", bb
->out_bb
[j
]->block_num
);
464 if (bb
->out_count
== 0)
469 if (!bb
->live_in_set
) {
470 /* First pass over this bblock */
475 mono_bitset_copyto_fast (bb
->live_out_set
, old_live_out_set
);
478 for (j
= 0; j
< bb
->out_count
; j
++) {
479 out_bb
= bb
->out_bb
[j
];
481 if (!out_bb
->live_in_set
) {
482 out_bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
484 mono_bitset_copyto_fast (out_bb
->live_out_set
, out_bb
->live_in_set
);
485 mono_bitset_sub_fast (out_bb
->live_in_set
, out_bb
->kill_set
);
486 mono_bitset_union_fast (out_bb
->live_in_set
, out_bb
->gen_set
);
489 // FIXME: Do this somewhere else
490 if (bb
->last_ins
&& bb
->last_ins
->opcode
== OP_NOT_REACHED
) {
492 mono_bitset_union_fast (bb
->live_out_set
, out_bb
->live_in_set
);
496 if (changed
|| !mono_bitset_equal (old_live_out_set
, bb
->live_out_set
)) {
497 if (!bb
->live_in_set
)
498 bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
499 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
500 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
501 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
503 for (j
= 0; j
< bb
->in_count
; j
++) {
504 MonoBasicBlock
*in_bb
= bb
->in_bb
[j
];
506 * Some basic blocks do not seem to be in the
507 * cfg->bblocks array...
509 if (in_bb
->gen_set
&& !in_worklist
[in_bb
->dfn
]) {
510 #ifdef DEBUG_LIVENESS
511 if (cfg
->verbose_level
> 1)
512 printf ("\tADD: %d\n", in_bb
->block_num
);
515 * Put the block at the top of the stack, so it
516 * will be processed right away.
518 worklist
[l_end
++] = in_bb
;
519 in_worklist
[in_bb
->dfn
] = TRUE
;
524 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
525 printf ("\tLIVE IN BB%d: ", bb
->block_num
);
526 mono_bitset_print (bb
->live_in_set
);
530 #ifdef DEBUG_LIVENESS
531 if (cfg
->verbose_level
> 1)
532 printf ("IT: %d %d.\n", cfg
->num_bblocks
, out_iter
);
535 mono_bitset_free (old_live_out_set
);
538 g_free (in_worklist
);
540 /* Compute live_in_set for bblocks skipped earlier */
541 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
542 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
544 if (!bb
->live_in_set
) {
545 bb
->live_in_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
547 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
548 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
549 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
553 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
554 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
556 guint32 abs_pos
= (bb
->dfn
<< BB_ID_SHIFT
);
557 MonoMethodVar
*vars
= cfg
->vars
;
559 if (!bb
->live_out_set
)
562 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
563 for (j
= 0; j
< max
; ++j
) {
568 bits_in
= mono_bitset_get_fast (bb
->live_in_set
, j
);
569 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
571 k
= (j
* BITS_PER_CHUNK
);
572 while ((bits_in
|| bits_out
)) {
574 update_live_range (&vars
[k
], abs_pos
+ 0);
576 update_live_range (&vars
[k
], abs_pos
+ ((1 << BB_ID_SHIFT
) - 1));
585 * Arguments need to have their live ranges extended to the beginning of
586 * the method to account for the arg reg/memory -> global register copies
587 * in the prolog (bug #74992).
590 for (i
= 0; i
< max_vars
; i
++) {
591 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
592 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
) {
593 if (vi
->range
.last_use
.abs_pos
== 0 && !(cfg
->varinfo
[vi
->idx
]->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
595 * Can't eliminate the this variable in gshared code, since
596 * it is needed during exception handling to identify the
598 * It is better to check for this here instead of marking the variable
599 * VOLATILE, since that would prevent it from being allocated to
602 if (!cfg
->disable_deadce_vars
&& !(cfg
->gshared
&& mono_method_signature (cfg
->method
)->hasthis
&& cfg
->varinfo
[vi
->idx
] == cfg
->args
[0]))
603 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_IS_DEAD
;
605 vi
->range
.first_use
.abs_pos
= 0;
609 #ifdef DEBUG_LIVENESS
610 if (cfg
->verbose_level
> 1) {
611 for (i
= cfg
->num_bblocks
- 1; i
>= 0; i
--) {
612 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
614 printf ("LIVE IN BB%d: ", bb
->block_num
);
615 mono_bitset_print (bb
->live_in_set
);
616 printf ("LIVE OUT BB%d: ", bb
->block_num
);
617 mono_bitset_print (bb
->live_out_set
);
620 for (i
= 0; i
< max_vars
; i
++) {
621 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
623 printf ("V%d: [0x%x - 0x%x]\n", i
, vi
->range
.first_use
.abs_pos
, vi
->range
.last_use
.abs_pos
);
628 if (!cfg
->disable_initlocals_opt
)
629 optimize_initlocals (cfg
);
631 #ifdef ENABLE_LIVENESS2
632 /* This improves code size by about 5% but slows down compilation too much */
633 if (cfg
->compile_aot
)
634 mono_analyze_liveness2 (cfg
);
639 * optimize_initlocals:
641 * Try to optimize away some of the redundant initialization code inserted because of
642 * 'locals init' using the liveness information.
645 optimize_initlocals (MonoCompile
*cfg
)
649 MonoBasicBlock
*initlocals_bb
;
651 used
= mono_bitset_new (cfg
->next_vreg
+ 1, 0);
653 mono_bitset_clear_all (used
);
654 initlocals_bb
= cfg
->bb_entry
->next_bb
;
655 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
657 int sregs
[MONO_MAX_SRC_REGS
];
659 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
660 for (i
= 0; i
< num_sregs
; ++i
)
661 mono_bitset_set_fast (used
, sregs
[i
]);
663 if (MONO_IS_STORE_MEMBASE (ins
))
664 mono_bitset_set_fast (used
, ins
->dreg
);
667 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
668 const char *spec
= INS_INFO (ins
->opcode
);
670 /* Look for statements whose dest is not used in this bblock and not live on exit. */
671 if ((spec
[MONO_INST_DEST
] != ' ') && !MONO_IS_STORE_MEMBASE (ins
)) {
672 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
674 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
))) {
675 //printf ("DEAD: "); mono_print_ins (ins);
676 if (cfg
->disable_initlocals_opt_refs
&& var
->type
== STACK_OBJ
)
678 if ((ins
->opcode
== OP_ICONST
) || (ins
->opcode
== OP_I8CONST
) || (ins
->opcode
== OP_R8CONST
) || (ins
->opcode
== OP_R4CONST
)) {
680 MONO_VARINFO (cfg
, var
->inst_c0
)->spill_costs
-= 1;
682 * We should shorten the liveness interval of these vars as well, but
683 * don't have enough info to do that.
694 mono_linterval_add_range (MonoCompile
*cfg
, MonoLiveInterval
*interval
, int from
, int to
)
696 MonoLiveRange2
*prev_range
, *next_range
, *new_range
;
698 g_assert (to
>= from
);
700 /* Optimize for extending the first interval backwards */
701 if (G_LIKELY (interval
->range
&& (interval
->range
->from
> from
) && (interval
->range
->from
== to
))) {
702 interval
->range
->from
= from
;
706 /* Find a place in the list for the new range */
708 next_range
= interval
->range
;
709 while ((next_range
!= NULL
) && (next_range
->from
<= from
)) {
710 prev_range
= next_range
;
711 next_range
= next_range
->next
;
714 if (prev_range
&& prev_range
->to
== from
) {
715 /* Merge with previous */
717 } else if (next_range
&& next_range
->from
== to
) {
718 /* Merge with previous */
719 next_range
->from
= from
;
722 new_range
= (MonoLiveRange2
*)mono_mempool_alloc (cfg
->mempool
, sizeof (MonoLiveRange2
));
723 new_range
->from
= from
;
725 new_range
->next
= NULL
;
728 prev_range
->next
= new_range
;
730 interval
->range
= new_range
;
732 new_range
->next
= next_range
;
734 interval
->last_range
= new_range
;
737 /* FIXME: Merge intersecting ranges */
741 mono_linterval_print (MonoLiveInterval
*interval
)
743 MonoLiveRange2
*range
;
745 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
)
746 printf ("[%x-%x] ", range
->from
, range
->to
);
750 mono_linterval_print_nl (MonoLiveInterval
*interval
)
752 mono_linterval_print (interval
);
757 * mono_linterval_convers:
759 * Return whenever INTERVAL covers the position POS.
762 mono_linterval_covers (MonoLiveInterval
*interval
, int pos
)
764 MonoLiveRange2
*range
;
766 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
) {
767 if (pos
>= range
->from
&& pos
<= range
->to
)
769 if (range
->from
> pos
)
777 * mono_linterval_get_intersect_pos:
779 * Determine whenever I1 and I2 intersect, and if they do, return the first
780 * point of intersection. Otherwise, return -1.
783 mono_linterval_get_intersect_pos (MonoLiveInterval
*i1
, MonoLiveInterval
*i2
)
785 MonoLiveRange2
*r1
, *r2
;
787 /* FIXME: Optimize this */
788 for (r1
= i1
->range
; r1
!= NULL
; r1
= r1
->next
) {
789 for (r2
= i2
->range
; r2
!= NULL
; r2
= r2
->next
) {
790 if (r2
->to
> r1
->from
&& r2
->from
< r1
->to
) {
791 if (r2
->from
<= r1
->from
)
803 * mono_linterval_split
805 * Split L at POS and store the newly created intervals into L1 and L2. POS becomes
809 mono_linterval_split (MonoCompile
*cfg
, MonoLiveInterval
*interval
, MonoLiveInterval
**i1
, MonoLiveInterval
**i2
, int pos
)
813 g_assert (pos
> interval
->range
->from
&& pos
<= interval
->last_range
->to
);
815 *i1
= (MonoLiveInterval
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
816 *i2
= (MonoLiveInterval
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
818 for (r
= interval
->range
; r
; r
= r
->next
) {
820 /* Add it to the first child */
821 mono_linterval_add_range (cfg
, *i1
, r
->from
, r
->to
);
822 } else if (pos
> r
->from
&& pos
<= r
->to
) {
824 mono_linterval_add_range (cfg
, *i1
, r
->from
, pos
- 1);
825 mono_linterval_add_range (cfg
, *i2
, pos
, r
->to
);
827 /* Add it to the second child */
828 mono_linterval_add_range (cfg
, *i2
, r
->from
, r
->to
);
834 #define LIVENESS_DEBUG(a) do { if (cfg->verbose_level > 1) do { a; } while (0); } while (0)
835 #define ENABLE_LIVENESS_DEBUG 1
837 #define LIVENESS_DEBUG(a)
840 #ifdef ENABLE_LIVENESS2
843 update_liveness2 (MonoCompile
*cfg
, MonoInst
*ins
, gboolean set_volatile
, int inst_num
, gint32
*last_use
)
845 const char *spec
= INS_INFO (ins
->opcode
);
848 int sregs
[MONO_MAX_SRC_REGS
];
850 LIVENESS_DEBUG (printf ("\t%x: ", inst_num
); mono_print_ins (ins
));
852 if (ins
->opcode
== OP_NOP
|| ins
->opcode
== OP_IL_SEQ_POINT
)
856 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
857 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
858 int idx
= var
->inst_c0
;
859 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
861 if (MONO_IS_STORE_MEMBASE (ins
)) {
862 if (last_use
[idx
] == 0) {
863 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins
->dreg
, inst_num
));
864 last_use
[idx
] = inst_num
;
867 if (last_use
[idx
] > 0) {
868 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", ins
->dreg
, inst_num
, last_use
[idx
]));
869 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, last_use
[idx
]);
873 /* Try dead code elimination */
874 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
)) {
875 LIVENESS_DEBUG (printf ("\tdead def of R%d, eliminated\n", ins
->dreg
));
879 int inst_num_add
= 1;
880 MonoInst
*next
= ins
->next
;
881 while (next
&& next
->opcode
== OP_IL_SEQ_POINT
) {
886 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
));
887 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, inst_num
+ inst_num_add
);
894 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
895 for (i
= 0; i
< num_sregs
; ++i
) {
897 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
898 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
899 int idx
= var
->inst_c0
;
901 if (last_use
[idx
] == 0) {
902 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
));
903 last_use
[idx
] = inst_num
;
910 mono_analyze_liveness2 (MonoCompile
*cfg
)
912 int bnum
, idx
, i
, j
, nins
, max
, max_vars
, block_from
, block_to
, pos
;
914 static guint32 disabled
= -1;
917 disabled
= g_hasenv ("DISABLED");
922 if (cfg
->num_bblocks
>= (1 << (32 - BB_ID_SHIFT
- 1)))
923 /* Ranges would overflow */
926 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
927 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
931 for (nins
= 0, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
)
934 if (nins
>= ((1 << BB_ID_SHIFT
) - 1))
935 /* Ranges would overflow */
939 LIVENESS_DEBUG (printf ("LIVENESS 2 %s\n", mono_method_full_name (cfg
->method
, TRUE
)));
942 if (strstr (cfg->method->name, "test_") != cfg->method->name)
946 max_vars
= cfg
->num_varinfo
;
947 last_use
= g_new0 (gint32
, max_vars
);
949 for (idx
= 0; idx
< max_vars
; ++idx
) {
950 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
952 vi
->interval
= (MonoLiveInterval
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
956 * Process bblocks in reverse order, so the addition of new live ranges
957 * to the intervals is faster.
959 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
960 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
963 block_from
= (bb
->dfn
<< BB_ID_SHIFT
) + 1; /* so pos > 0 */
964 if (bnum
< cfg
->num_bblocks
- 1)
965 /* Beginning of the next bblock */
966 block_to
= (cfg
->bblocks
[bnum
+ 1]->dfn
<< BB_ID_SHIFT
) + 1;
968 block_to
= (bb
->dfn
<< BB_ID_SHIFT
) + ((1 << BB_ID_SHIFT
) - 1);
970 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb
->block_num
));
972 memset (last_use
, 0, max_vars
* sizeof (gint32
));
974 /* For variables in bb->live_out, set last_use to block_to */
976 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
977 for (j
= 0; j
< max
; ++j
) {
981 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
982 k
= (j
* BITS_PER_CHUNK
);
985 LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", cfg
->varinfo
[k
]->dreg
, block_to
));
986 last_use
[k
] = block_to
;
994 last_use
[cfg
->ret
->inst_c0
] = block_to
;
996 pos
= block_from
+ 1;
997 MONO_BB_FOR_EACH_INS (bb
, ins
) pos
++;
999 /* Process instructions backwards */
1000 MONO_BB_FOR_EACH_INS_REVERSE (bb
, ins
) {
1001 update_liveness2 (cfg
, ins
, FALSE
, pos
, last_use
);
1005 for (idx
= 0; idx
< max_vars
; ++idx
) {
1006 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1008 if (last_use
[idx
] != 0) {
1009 /* Live at exit, not written -> live on enter */
1010 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
]));
1011 mono_linterval_add_range (cfg
, vi
->interval
, block_from
, last_use
[idx
]);
1017 * Arguments need to have their live ranges extended to the beginning of
1018 * the method to account for the arg reg/memory -> global register copies
1019 * in the prolog (bug #74992).
1021 for (i
= 0; i
< max_vars
; i
++) {
1022 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
1023 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
)
1024 mono_linterval_add_range (cfg
, vi
->interval
, 0, 1);
1028 for (idx
= 0; idx
< max_vars
; ++idx
) {
1029 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1031 LIVENESS_DEBUG (printf ("LIVENESS R%d: ", cfg
->varinfo
[idx
]->dreg
));
1032 LIVENESS_DEBUG (mono_linterval_print (vi
->interval
));
1033 LIVENESS_DEBUG (printf ("\n"));
1043 update_liveness_gc (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*ins
, gint32
*last_use
, MonoMethodVar
**vreg_to_varinfo
, GSList
**callsites
)
1045 if (ins
->opcode
== OP_GC_LIVENESS_DEF
|| ins
->opcode
== OP_GC_LIVENESS_USE
) {
1046 int vreg
= ins
->inst_c1
;
1047 MonoMethodVar
*vi
= vreg_to_varinfo
[vreg
];
1049 int pc_offset
= ins
->backend
.pc_offset
;
1051 LIVENESS_DEBUG (printf ("\t%x: ", pc_offset
); mono_print_ins (ins
));
1053 if (ins
->opcode
== OP_GC_LIVENESS_DEF
) {
1054 if (last_use
[idx
] > 0) {
1055 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", vreg
, pc_offset
, last_use
[idx
]));
1059 if (last_use
[idx
] == 0) {
1060 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", vreg
, pc_offset
));
1061 last_use
[idx
] = pc_offset
;
1064 } else if (ins
->opcode
== OP_GC_PARAM_SLOT_LIVENESS_DEF
) {
1067 /* Add it to the last callsite */
1068 g_assert (*callsites
);
1069 last
= (GCCallSite
*)(*callsites
)->data
;
1070 last
->param_slots
= g_slist_prepend_mempool (cfg
->mempool
, last
->param_slots
, ins
);
1071 } else if (ins
->flags
& MONO_INST_GC_CALLSITE
) {
1072 GCCallSite
*callsite
= (GCCallSite
*)mono_mempool_alloc0 (cfg
->mempool
, sizeof (GCCallSite
));
1075 LIVENESS_DEBUG (printf ("\t%x: ", ins
->backend
.pc_offset
); mono_print_ins (ins
));
1076 LIVENESS_DEBUG (printf ("\t\tlive: "));
1079 callsite
->liveness
= (guint8
*)mono_mempool_alloc0 (cfg
->mempool
, ALIGN_TO (cfg
->num_varinfo
, 8) / 8);
1080 callsite
->pc_offset
= ins
->backend
.pc_offset
;
1081 for (i
= 0; i
< cfg
->num_varinfo
; ++i
) {
1082 if (last_use
[i
] != 0) {
1083 LIVENESS_DEBUG (printf ("R%d", MONO_VARINFO (cfg
, i
)->vreg
));
1084 callsite
->liveness
[i
/ 8] |= (1 << (i
% 8));
1087 LIVENESS_DEBUG (printf ("\n"));
1088 *callsites
= g_slist_prepend_mempool (cfg
->mempool
, *callsites
, callsite
);
1093 get_vreg_from_var (MonoCompile
*cfg
, MonoInst
*var
)
1095 if (var
->opcode
== OP_REGVAR
)
1096 /* dreg contains a hreg, but inst_c0 still contains the var index */
1097 return MONO_VARINFO (cfg
, var
->inst_c0
)->vreg
;
1099 /* dreg still contains the vreg */
1104 * mono_analyze_liveness_gc:
1106 * Compute liveness bitmaps for each call site.
1107 * This function is a modified version of mono_analyze_liveness2 ().
1110 mono_analyze_liveness_gc (MonoCompile
*cfg
)
1112 int idx
, i
, j
, nins
, max
, max_vars
, block_from
, block_to
, pos
, reverse_len
;
1115 MonoMethodVar
**vreg_to_varinfo
= NULL
;
1119 LIVENESS_DEBUG (printf ("\n------------ GC LIVENESS: ----------\n"));
1121 max_vars
= cfg
->num_varinfo
;
1122 last_use
= g_new0 (gint32
, max_vars
);
1125 * var->inst_c0 no longer contains the variable index, so compute a mapping now.
1127 vreg_to_varinfo
= g_new0 (MonoMethodVar
*, cfg
->next_vreg
);
1128 for (idx
= 0; idx
< max_vars
; ++idx
) {
1129 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1131 vreg_to_varinfo
[vi
->vreg
] = vi
;
1135 reverse
= (MonoInst
**)mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * reverse_len
);
1137 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
1140 block_from
= bb
->real_native_offset
;
1141 block_to
= bb
->native_offset
+ bb
->native_length
;
1143 LIVENESS_DEBUG (printf ("GC LIVENESS BB%d:\n", bb
->block_num
));
1148 memset (last_use
, 0, max_vars
* sizeof (gint32
));
1150 /* For variables in bb->live_out, set last_use to block_to */
1152 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
1153 for (j
= 0; j
< max
; ++j
) {
1157 if (!bb
->live_out_set
)
1158 /* The variables used in this bblock are volatile anyway */
1161 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
1162 k
= (j
* BITS_PER_CHUNK
);
1164 if ((bits_out
& 1) && cfg
->varinfo
[k
]->flags
& MONO_INST_GC_TRACK
) {
1165 int vreg
= get_vreg_from_var (cfg
, cfg
->varinfo
[k
]);
1166 LIVENESS_DEBUG (printf ("Var R%d live at exit, last_use set to %x.\n", vreg
, block_to
));
1167 last_use
[k
] = block_to
;
1174 for (nins
= 0, pos
= block_from
, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
, ++pos
) {
1175 if (nins
>= reverse_len
) {
1176 int new_reverse_len
= reverse_len
* 2;
1177 MonoInst
**new_reverse
= (MonoInst
**)mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * new_reverse_len
);
1178 memcpy (new_reverse
, reverse
, sizeof (MonoInst
*) * reverse_len
);
1179 reverse
= new_reverse
;
1180 reverse_len
= new_reverse_len
;
1183 reverse
[nins
] = ins
;
1186 /* Process instructions backwards */
1188 for (i
= nins
- 1; i
>= 0; --i
) {
1189 MonoInst
*ins
= (MonoInst
*)reverse
[i
];
1191 update_liveness_gc (cfg
, bb
, ins
, last_use
, vreg_to_varinfo
, &callsites
);
1193 /* The callsites should already be sorted by pc offset because we added them backwards */
1194 bb
->gc_callsites
= callsites
;
1198 g_free (vreg_to_varinfo
);
1201 #else /* !DISABLE_JIT */
1203 MONO_EMPTY_SOURCE_FILE (liveness
);
1205 #endif /* !DISABLE_JIT */