2 * liveness.c: liveness analysis
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2002 Ximian, Inc.
8 * Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
13 #define SPILL_COST_INCREMENT (1 << (bb->nesting << 1))
15 #define DEBUG_LIVENESS
17 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
20 * The liveness2 pass can't handle long vars on 32 bit platforms because the component
21 * vars have the same 'idx'.
23 #if SIZEOF_REGISTER == 8
24 #define ENABLE_LIVENESS2
27 #ifdef ENABLE_LIVENESS2
28 static void mono_analyze_liveness2 (MonoCompile
*cfg
);
32 optimize_initlocals (MonoCompile
*cfg
);
34 /* mono_bitset_mp_new:
36 * allocates a MonoBitSet inside a memory pool
38 static inline MonoBitSet
*
39 mono_bitset_mp_new (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
41 guint8
*mem
= mono_mempool_alloc0 (mp
, size
);
42 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
45 static inline MonoBitSet
*
46 mono_bitset_mp_new_noinit (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
48 guint8
*mem
= mono_mempool_alloc (mp
, size
);
49 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
52 G_GNUC_UNUSED
static void
53 mono_bitset_print (MonoBitSet
*set
)
56 gboolean first
= TRUE
;
59 for (i
= 0; i
< mono_bitset_size (set
); i
++) {
61 if (mono_bitset_test (set
, i
)) {
72 visit_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
, GSList
**visited
)
77 if (g_slist_find (*visited
, bb
))
80 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
81 const char *spec
= INS_INFO (ins
->opcode
);
82 int regtype
, srcindex
, sreg
, num_sregs
;
83 int sregs
[MONO_MAX_SRC_REGS
];
85 if (ins
->opcode
== OP_NOP
)
89 regtype
= spec
[MONO_INST_DEST
];
90 g_assert (((ins
->dreg
== -1) && (regtype
== ' ')) || ((ins
->dreg
!= -1) && (regtype
!= ' ')));
92 if ((ins
->dreg
!= -1) && get_vreg_to_inst (cfg
, ins
->dreg
)) {
93 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
94 int idx
= var
->inst_c0
;
95 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
97 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
98 if (SIZEOF_REGISTER
== 4 && (var
->type
== STACK_I8
|| (var
->type
== STACK_R8
&& COMPILE_SOFT_FLOAT (cfg
)))) {
99 /* Make the component vregs volatile as well (#612206) */
100 get_vreg_to_inst (cfg
, var
->dreg
+ 1)->flags
|= MONO_INST_VOLATILE
;
101 get_vreg_to_inst (cfg
, var
->dreg
+ 2)->flags
|= MONO_INST_VOLATILE
;
106 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
107 for (srcindex
= 0; srcindex
< num_sregs
; ++srcindex
) {
108 sreg
= sregs
[srcindex
];
110 g_assert (sreg
!= -1);
111 if (get_vreg_to_inst (cfg
, sreg
)) {
112 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
113 int idx
= var
->inst_c0
;
114 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
116 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
117 if (SIZEOF_REGISTER
== 4 && (var
->type
== STACK_I8
|| (var
->type
== STACK_R8
&& COMPILE_SOFT_FLOAT (cfg
)))) {
118 /* Make the component vregs volatile as well (#612206) */
119 get_vreg_to_inst (cfg
, var
->dreg
+ 1)->flags
|= MONO_INST_VOLATILE
;
120 get_vreg_to_inst (cfg
, var
->dreg
+ 2)->flags
|= MONO_INST_VOLATILE
;
126 *visited
= g_slist_append (*visited
, bb
);
129 * Need to visit all bblocks reachable from this one since they can be
130 * reached during exception handling.
132 for (i
= 0; i
< bb
->out_count
; ++i
) {
133 visit_bb (cfg
, bb
->out_bb
[i
], visited
);
138 mono_liveness_handle_exception_clauses (MonoCompile
*cfg
)
141 GSList
*visited
= NULL
;
142 MonoMethodHeader
*header
= cfg
->header
;
143 MonoExceptionClause
*clause
, *clause2
;
148 * Determine which clauses are outer try clauses, i.e. they are not contained in any
149 * other non-try clause.
151 outer_try
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (gboolean
) * header
->num_clauses
);
152 for (i
= 0; i
< header
->num_clauses
; ++i
)
153 outer_try
[i
] = TRUE
;
154 /* Iterate over the clauses backward, so outer clauses come first */
155 /* This avoids doing an O(2) search, since we can determine when inner clauses end */
156 for (i
= header
->num_clauses
- 1; i
>= 0; --i
) {
157 clause
= &header
->clauses
[i
];
159 if (clause
->flags
!= 0) {
160 outer_try
[i
] = TRUE
;
161 /* Iterate over inner clauses */
162 for (j
= i
- 1; j
>= 0; --j
) {
163 clause2
= &header
->clauses
[j
];
165 if (clause2
->flags
== 0 && MONO_OFFSET_IN_HANDLER (clause
, clause2
->try_offset
)) {
166 outer_try
[j
] = FALSE
;
169 if (clause2
->try_offset
< clause
->try_offset
)
170 /* End of inner clauses */
177 * Variables in exception handler register cannot be allocated to registers
178 * so make them volatile. See bug #42136. This will not be neccessary when
179 * the back ends could guarantee that the variables will be in the
180 * correct registers when a handler is called.
181 * This includes try blocks too, since a variable in a try block might be
182 * accessed after an exception handler has been run.
184 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
186 if (bb
->region
== -1)
189 if (MONO_BBLOCK_IS_IN_REGION (bb
, MONO_REGION_TRY
) && outer_try
[MONO_REGION_CLAUSE_INDEX (bb
->region
)])
192 if (cfg
->verbose_level
> 2)
193 printf ("pessimize variables in bb %d.\n", bb
->block_num
);
195 visit_bb (cfg
, bb
, &visited
);
197 g_slist_free (visited
);
201 update_live_range (MonoMethodVar
*var
, int abs_pos
)
203 if (var
->range
.first_use
.abs_pos
> abs_pos
)
204 var
->range
.first_use
.abs_pos
= abs_pos
;
206 if (var
->range
.last_use
.abs_pos
< abs_pos
)
207 var
->range
.last_use
.abs_pos
= abs_pos
;
211 analyze_liveness_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
)
215 MonoMethodVar
*vars
= cfg
->vars
;
216 guint32 abs_pos
= (bb
->dfn
<< 16);
218 for (inst_num
= 0, ins
= bb
->code
; ins
; ins
= ins
->next
, inst_num
+= 2) {
219 const char *spec
= INS_INFO (ins
->opcode
);
221 int sregs
[MONO_MAX_SRC_REGS
];
223 #ifdef DEBUG_LIVENESS
224 if (cfg
->verbose_level
> 1) {
226 mono_print_ins (ins
);
230 if (ins
->opcode
== OP_NOP
)
233 if (ins
->opcode
== OP_LDADDR
) {
234 MonoInst
*var
= ins
->inst_p0
;
235 int idx
= var
->inst_c0
;
236 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
238 #ifdef DEBUG_LIVENESS
239 if (cfg
->verbose_level
> 1)
240 printf ("\tGEN: R%d(%d)\n", var
->dreg
, idx
);
242 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
243 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
244 mono_bitset_set_fast (bb
->gen_set
, idx
);
245 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
248 /* SREGs must come first, so MOVE r <- r is handled correctly */
249 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
250 for (i
= 0; i
< num_sregs
; ++i
) {
252 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
253 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
254 int idx
= var
->inst_c0
;
255 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
257 #ifdef DEBUG_LIVENESS
258 if (cfg
->verbose_level
> 1)
259 printf ("\tGEN: R%d(%d)\n", sreg
, idx
);
261 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
262 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
263 mono_bitset_set_fast (bb
->gen_set
, idx
);
264 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
269 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
270 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
271 int idx
= var
->inst_c0
;
272 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
274 if (MONO_IS_STORE_MEMBASE (ins
)) {
275 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
276 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
277 mono_bitset_set_fast (bb
->gen_set
, idx
);
278 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
280 #ifdef DEBUG_LIVENESS
281 if (cfg
->verbose_level
> 1)
282 printf ("\tKILL: R%d(%d)\n", ins
->dreg
, idx
);
284 update_live_range (&vars
[idx
], abs_pos
+ inst_num
+ 1);
285 mono_bitset_set_fast (bb
->kill_set
, idx
);
286 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
292 /* generic liveness analysis code. CFG specific parts are
293 * in update_gen_kill_set()
296 mono_analyze_liveness (MonoCompile
*cfg
)
298 MonoBitSet
*old_live_out_set
;
299 int i
, j
, max_vars
= cfg
->num_varinfo
;
301 gboolean
*in_worklist
;
302 MonoBasicBlock
**worklist
;
306 #ifdef DEBUG_LIVENESS
307 if (cfg
->verbose_level
> 1)
308 printf ("\nLIVENESS:\n");
311 g_assert (!(cfg
->comp_done
& MONO_COMP_LIVENESS
));
313 cfg
->comp_done
|= MONO_COMP_LIVENESS
;
318 bitsize
= mono_bitset_alloc_size (max_vars
, 0);
320 for (i
= 0; i
< max_vars
; i
++) {
321 MONO_VARINFO (cfg
, i
)->range
.first_use
.abs_pos
= ~ 0;
322 MONO_VARINFO (cfg
, i
)->range
.last_use
.abs_pos
= 0;
323 MONO_VARINFO (cfg
, i
)->spill_costs
= 0;
326 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
327 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
329 bb
->gen_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
330 bb
->kill_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
332 #ifdef DEBUG_LIVENESS
333 if (cfg
->verbose_level
> 1) {
334 printf ("BLOCK BB%d (", bb
->block_num
);
335 for (j
= 0; j
< bb
->out_count
; j
++)
336 printf ("BB%d, ", bb
->out_bb
[j
]->block_num
);
342 analyze_liveness_bb (cfg
, bb
);
344 #ifdef DEBUG_LIVENESS
345 if (cfg
->verbose_level
> 1) {
346 printf ("GEN BB%d: ", bb
->block_num
); mono_bitset_print (bb
->gen_set
);
347 printf ("KILL BB%d: ", bb
->block_num
); mono_bitset_print (bb
->kill_set
);
352 old_live_out_set
= mono_bitset_new (max_vars
, 0);
353 in_worklist
= g_new0 (gboolean
, cfg
->num_bblocks
+ 1);
355 worklist
= g_new (MonoBasicBlock
*, cfg
->num_bblocks
+ 1);
359 * This is a backward dataflow analysis problem, so we process blocks in
360 * decreasing dfn order, this speeds up the iteration.
362 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
363 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
365 worklist
[l_end
++] = bb
;
366 in_worklist
[bb
->dfn
] = TRUE
;
368 /* Initialized later */
369 bb
->live_in_set
= NULL
;
370 bb
->live_out_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
375 if (cfg
->verbose_level
> 1)
376 printf ("\nITERATION:\n");
379 MonoBasicBlock
*bb
= worklist
[--l_end
];
380 MonoBasicBlock
*out_bb
;
383 in_worklist
[bb
->dfn
] = FALSE
;
385 #ifdef DEBUG_LIVENESS
386 if (cfg
->verbose_level
> 1) {
387 printf ("P: BB%d(%d): IN: ", bb
->block_num
, bb
->dfn
);
388 for (j
= 0; j
< bb
->in_count
; ++j
)
389 printf ("BB%d ", bb
->in_bb
[j
]->block_num
);
391 for (j
= 0; j
< bb
->out_count
; ++j
)
392 printf ("BB%d ", bb
->out_bb
[j
]->block_num
);
398 if (bb
->out_count
== 0)
403 if (!bb
->live_in_set
) {
404 /* First pass over this bblock */
409 mono_bitset_copyto_fast (bb
->live_out_set
, old_live_out_set
);
412 for (j
= 0; j
< bb
->out_count
; j
++) {
413 out_bb
= bb
->out_bb
[j
];
415 if (!out_bb
->live_in_set
) {
416 out_bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
418 mono_bitset_copyto_fast (out_bb
->live_out_set
, out_bb
->live_in_set
);
419 mono_bitset_sub_fast (out_bb
->live_in_set
, out_bb
->kill_set
);
420 mono_bitset_union_fast (out_bb
->live_in_set
, out_bb
->gen_set
);
423 // FIXME: Do this somewhere else
424 if (bb
->last_ins
&& bb
->last_ins
->opcode
== OP_NOT_REACHED
) {
426 mono_bitset_union_fast (bb
->live_out_set
, out_bb
->live_in_set
);
430 if (changed
|| !mono_bitset_equal (old_live_out_set
, bb
->live_out_set
)) {
431 if (!bb
->live_in_set
)
432 bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
433 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
434 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
435 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
437 for (j
= 0; j
< bb
->in_count
; j
++) {
438 MonoBasicBlock
*in_bb
= bb
->in_bb
[j
];
440 * Some basic blocks do not seem to be in the
441 * cfg->bblocks array...
443 if (in_bb
->gen_set
&& !in_worklist
[in_bb
->dfn
]) {
444 #ifdef DEBUG_LIVENESS
445 if (cfg
->verbose_level
> 1)
446 printf ("\tADD: %d\n", in_bb
->block_num
);
449 * Put the block at the top of the stack, so it
450 * will be processed right away.
452 worklist
[l_end
++] = in_bb
;
453 in_worklist
[in_bb
->dfn
] = TRUE
;
458 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
459 printf ("\tLIVE IN BB%d: ", bb
->block_num
);
460 mono_bitset_print (bb
->live_in_set
);
464 #ifdef DEBUG_LIVENESS
465 if (cfg
->verbose_level
> 1)
466 printf ("IT: %d %d.\n", cfg
->num_bblocks
, out_iter
);
469 mono_bitset_free (old_live_out_set
);
472 g_free (in_worklist
);
474 /* Compute live_in_set for bblocks skipped earlier */
475 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
476 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
478 if (!bb
->live_in_set
) {
479 bb
->live_in_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
481 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
482 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
483 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
487 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
488 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
490 guint32 abs_pos
= (bb
->dfn
<< 16);
491 MonoMethodVar
*vars
= cfg
->vars
;
493 if (!bb
->live_out_set
)
496 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
497 for (j
= 0; j
< max
; ++j
) {
502 bits_in
= mono_bitset_get_fast (bb
->live_in_set
, j
);
503 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
505 k
= (j
* BITS_PER_CHUNK
);
506 while ((bits_in
|| bits_out
)) {
508 update_live_range (&vars
[k
], abs_pos
+ 0);
510 update_live_range (&vars
[k
], abs_pos
+ 0xffff);
519 * Arguments need to have their live ranges extended to the beginning of
520 * the method to account for the arg reg/memory -> global register copies
521 * in the prolog (bug #74992).
524 for (i
= 0; i
< max_vars
; i
++) {
525 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
526 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
) {
527 if (vi
->range
.last_use
.abs_pos
== 0 && !(cfg
->varinfo
[vi
->idx
]->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
529 * Can't eliminate the this variable in gshared code, since
530 * it is needed during exception handling to identify the
532 * It is better to check for this here instead of marking the variable
533 * VOLATILE, since that would prevent it from being allocated to
536 if (!cfg
->disable_deadce_vars
&& !(cfg
->generic_sharing_context
&& mono_method_signature (cfg
->method
)->hasthis
&& cfg
->varinfo
[vi
->idx
] == cfg
->args
[0]))
537 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_IS_DEAD
;
539 vi
->range
.first_use
.abs_pos
= 0;
543 #ifdef DEBUG_LIVENESS
544 if (cfg
->verbose_level
> 1) {
545 for (i
= cfg
->num_bblocks
- 1; i
>= 0; i
--) {
546 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
548 printf ("LIVE IN BB%d: ", bb
->block_num
);
549 mono_bitset_print (bb
->live_in_set
);
550 printf ("LIVE OUT BB%d: ", bb
->block_num
);
551 mono_bitset_print (bb
->live_out_set
);
554 for (i
= 0; i
< max_vars
; i
++) {
555 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
557 printf ("V%d: [0x%x - 0x%x]\n", i
, vi
->range
.first_use
.abs_pos
, vi
->range
.last_use
.abs_pos
);
562 if (!cfg
->disable_initlocals_opt
)
563 optimize_initlocals (cfg
);
565 #ifdef ENABLE_LIVENESS2
566 /* This improves code size by about 5% but slows down compilation too much */
567 if (cfg
->compile_aot
)
568 mono_analyze_liveness2 (cfg
);
573 * optimize_initlocals:
575 * Try to optimize away some of the redundant initialization code inserted because of
576 * 'locals init' using the liveness information.
579 optimize_initlocals (MonoCompile
*cfg
)
583 MonoBasicBlock
*initlocals_bb
;
585 used
= mono_bitset_new (cfg
->next_vreg
+ 1, 0);
587 mono_bitset_clear_all (used
);
588 initlocals_bb
= cfg
->bb_entry
->next_bb
;
589 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
591 int sregs
[MONO_MAX_SRC_REGS
];
593 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
594 for (i
= 0; i
< num_sregs
; ++i
)
595 mono_bitset_set_fast (used
, sregs
[i
]);
597 if (MONO_IS_STORE_MEMBASE (ins
))
598 mono_bitset_set_fast (used
, ins
->dreg
);
601 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
602 const char *spec
= INS_INFO (ins
->opcode
);
604 /* Look for statements whose dest is not used in this bblock and not live on exit. */
605 if ((spec
[MONO_INST_DEST
] != ' ') && !MONO_IS_STORE_MEMBASE (ins
)) {
606 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
608 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
))) {
609 //printf ("DEAD: "); mono_print_ins (ins);
610 if (cfg
->disable_initlocals_opt_refs
&& var
->type
== STACK_OBJ
)
612 if ((ins
->opcode
== OP_ICONST
) || (ins
->opcode
== OP_I8CONST
) || (ins
->opcode
== OP_R8CONST
)) {
614 MONO_VARINFO (cfg
, var
->inst_c0
)->spill_costs
-= 1;
616 * We should shorten the liveness interval of these vars as well, but
617 * don't have enough info to do that.
628 mono_linterval_add_range (MonoCompile
*cfg
, MonoLiveInterval
*interval
, int from
, int to
)
630 MonoLiveRange2
*prev_range
, *next_range
, *new_range
;
632 g_assert (to
>= from
);
634 /* Optimize for extending the first interval backwards */
635 if (G_LIKELY (interval
->range
&& (interval
->range
->from
> from
) && (interval
->range
->from
== to
))) {
636 interval
->range
->from
= from
;
640 /* Find a place in the list for the new range */
642 next_range
= interval
->range
;
643 while ((next_range
!= NULL
) && (next_range
->from
<= from
)) {
644 prev_range
= next_range
;
645 next_range
= next_range
->next
;
648 if (prev_range
&& prev_range
->to
== from
) {
649 /* Merge with previous */
651 } else if (next_range
&& next_range
->from
== to
) {
652 /* Merge with previous */
653 next_range
->from
= from
;
656 new_range
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoLiveRange2
));
657 new_range
->from
= from
;
659 new_range
->next
= NULL
;
662 prev_range
->next
= new_range
;
664 interval
->range
= new_range
;
666 new_range
->next
= next_range
;
668 interval
->last_range
= new_range
;
671 /* FIXME: Merge intersecting ranges */
675 mono_linterval_print (MonoLiveInterval
*interval
)
677 MonoLiveRange2
*range
;
679 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
)
680 printf ("[%x-%x] ", range
->from
, range
->to
);
684 mono_linterval_print_nl (MonoLiveInterval
*interval
)
686 mono_linterval_print (interval
);
691 * mono_linterval_convers:
693 * Return whenever INTERVAL covers the position POS.
696 mono_linterval_covers (MonoLiveInterval
*interval
, int pos
)
698 MonoLiveRange2
*range
;
700 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
) {
701 if (pos
>= range
->from
&& pos
<= range
->to
)
703 if (range
->from
> pos
)
711 * mono_linterval_get_intersect_pos:
713 * Determine whenever I1 and I2 intersect, and if they do, return the first
714 * point of intersection. Otherwise, return -1.
717 mono_linterval_get_intersect_pos (MonoLiveInterval
*i1
, MonoLiveInterval
*i2
)
719 MonoLiveRange2
*r1
, *r2
;
721 /* FIXME: Optimize this */
722 for (r1
= i1
->range
; r1
!= NULL
; r1
= r1
->next
) {
723 for (r2
= i2
->range
; r2
!= NULL
; r2
= r2
->next
) {
724 if (r2
->to
> r1
->from
&& r2
->from
< r1
->to
) {
725 if (r2
->from
<= r1
->from
)
737 * mono_linterval_split
739 * Split L at POS and store the newly created intervals into L1 and L2. POS becomes
743 mono_linterval_split (MonoCompile
*cfg
, MonoLiveInterval
*interval
, MonoLiveInterval
**i1
, MonoLiveInterval
**i2
, int pos
)
747 g_assert (pos
> interval
->range
->from
&& pos
<= interval
->last_range
->to
);
749 *i1
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
750 *i2
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
752 for (r
= interval
->range
; r
; r
= r
->next
) {
754 /* Add it to the first child */
755 mono_linterval_add_range (cfg
, *i1
, r
->from
, r
->to
);
756 } else if (pos
> r
->from
&& pos
<= r
->to
) {
758 mono_linterval_add_range (cfg
, *i1
, r
->from
, pos
- 1);
759 mono_linterval_add_range (cfg
, *i2
, pos
, r
->to
);
761 /* Add it to the second child */
762 mono_linterval_add_range (cfg
, *i2
, r
->from
, r
->to
);
768 #define LIVENESS_DEBUG(a) do { if (cfg->verbose_level > 1) do { a; } while (0); } while (0)
769 #define ENABLE_LIVENESS_DEBUG 1
771 #define LIVENESS_DEBUG(a)
774 #ifdef ENABLE_LIVENESS2
777 update_liveness2 (MonoCompile
*cfg
, MonoInst
*ins
, gboolean set_volatile
, int inst_num
, gint32
*last_use
)
779 const char *spec
= INS_INFO (ins
->opcode
);
782 int sregs
[MONO_MAX_SRC_REGS
];
784 LIVENESS_DEBUG (printf ("\t%x: ", inst_num
); mono_print_ins (ins
));
786 if (ins
->opcode
== OP_NOP
)
790 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
791 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
792 int idx
= var
->inst_c0
;
793 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
795 if (MONO_IS_STORE_MEMBASE (ins
)) {
796 if (last_use
[idx
] == 0) {
797 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins
->dreg
, inst_num
));
798 last_use
[idx
] = inst_num
;
801 if (last_use
[idx
] > 0) {
802 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", ins
->dreg
, inst_num
, last_use
[idx
]));
803 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, last_use
[idx
]);
807 /* Try dead code elimination */
808 if ((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
)) {
809 LIVENESS_DEBUG (printf ("\tdead def of R%d, eliminated\n", ins
->dreg
));
810 ins
->opcode
= OP_NOP
;
812 MONO_INST_NULLIFY_SREGS (ins
);
816 LIVENESS_DEBUG (printf ("\tdead def of R%d, add range to R%d: [%x, %x]\n", ins
->dreg
, ins
->dreg
, inst_num
, inst_num
+ 1));
817 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, inst_num
+ 1);
823 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
824 for (i
= 0; i
< num_sregs
; ++i
) {
826 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
827 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
828 int idx
= var
->inst_c0
;
830 if (last_use
[idx
] == 0) {
831 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
));
832 last_use
[idx
] = inst_num
;
839 mono_analyze_liveness2 (MonoCompile
*cfg
)
841 int bnum
, idx
, i
, j
, nins
, max
, max_vars
, block_from
, block_to
, pos
, reverse_len
;
843 static guint32 disabled
= -1;
847 disabled
= getenv ("DISABLED") != NULL
;
852 LIVENESS_DEBUG (printf ("LIVENESS 2 %s\n", mono_method_full_name (cfg
->method
, TRUE
)));
855 if (strstr (cfg->method->name, "test_") != cfg->method->name)
859 max_vars
= cfg
->num_varinfo
;
860 last_use
= g_new0 (gint32
, max_vars
);
863 reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * reverse_len
);
865 for (idx
= 0; idx
< max_vars
; ++idx
) {
866 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
868 vi
->interval
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
872 * Process bblocks in reverse order, so the addition of new live ranges
873 * to the intervals is faster.
875 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
876 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
879 block_from
= (bb
->dfn
<< 16) + 1; /* so pos > 0 */
880 if (bnum
< cfg
->num_bblocks
- 1)
881 /* Beginning of the next bblock */
882 block_to
= (cfg
->bblocks
[bnum
+ 1]->dfn
<< 16) + 1;
884 block_to
= (bb
->dfn
<< 16) + 0xffff;
886 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb
->block_num
));
888 memset (last_use
, 0, max_vars
* sizeof (gint32
));
890 /* For variables in bb->live_out, set last_use to block_to */
892 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
893 for (j
= 0; j
< max
; ++j
) {
897 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
898 k
= (j
* BITS_PER_CHUNK
);
901 LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", cfg
->varinfo
[k
]->dreg
, block_to
));
902 last_use
[k
] = block_to
;
910 last_use
[cfg
->ret
->inst_c0
] = block_to
;
912 for (nins
= 0, pos
= block_from
, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
, ++pos
) {
913 if (nins
>= reverse_len
) {
914 int new_reverse_len
= reverse_len
* 2;
915 MonoInst
**new_reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * new_reverse_len
);
916 memcpy (new_reverse
, reverse
, sizeof (MonoInst
*) * reverse_len
);
917 reverse
= new_reverse
;
918 reverse_len
= new_reverse_len
;
921 reverse
[nins
] = ins
;
924 /* Process instructions backwards */
925 for (i
= nins
- 1; i
>= 0; --i
) {
926 MonoInst
*ins
= (MonoInst
*)reverse
[i
];
928 update_liveness2 (cfg
, ins
, FALSE
, pos
, last_use
);
933 for (idx
= 0; idx
< max_vars
; ++idx
) {
934 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
936 if (last_use
[idx
] != 0) {
937 /* Live at exit, not written -> live on enter */
938 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
]));
939 mono_linterval_add_range (cfg
, vi
->interval
, block_from
, last_use
[idx
]);
945 * Arguments need to have their live ranges extended to the beginning of
946 * the method to account for the arg reg/memory -> global register copies
947 * in the prolog (bug #74992).
949 for (i
= 0; i
< max_vars
; i
++) {
950 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
951 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
)
952 mono_linterval_add_range (cfg
, vi
->interval
, 0, 1);
956 for (idx
= 0; idx
< max_vars
; ++idx
) {
957 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
959 LIVENESS_DEBUG (printf ("LIVENESS R%d: ", cfg
->varinfo
[idx
]->dreg
));
960 LIVENESS_DEBUG (mono_linterval_print (vi
->interval
));
961 LIVENESS_DEBUG (printf ("\n"));
970 #define ALIGN_TO(val,align) ((((guint64)val) + ((align) - 1)) & ~((align) - 1))
973 update_liveness_gc (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*ins
, gint32
*last_use
, MonoMethodVar
**vreg_to_varinfo
, GSList
**callsites
)
975 if (ins
->opcode
== OP_GC_LIVENESS_DEF
|| ins
->opcode
== OP_GC_LIVENESS_USE
) {
976 int vreg
= ins
->inst_c1
;
977 MonoMethodVar
*vi
= vreg_to_varinfo
[vreg
];
979 int pc_offset
= ins
->backend
.pc_offset
;
981 LIVENESS_DEBUG (printf ("\t%x: ", pc_offset
); mono_print_ins (ins
));
983 if (ins
->opcode
== OP_GC_LIVENESS_DEF
) {
984 if (last_use
[idx
] > 0) {
985 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", vreg
, pc_offset
, last_use
[idx
]));
989 if (last_use
[idx
] == 0) {
990 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", vreg
, pc_offset
));
991 last_use
[idx
] = pc_offset
;
994 } else if (ins
->opcode
== OP_GC_PARAM_SLOT_LIVENESS_DEF
) {
997 /* Add it to the last callsite */
998 g_assert (*callsites
);
999 last
= (*callsites
)->data
;
1000 last
->param_slots
= g_slist_prepend_mempool (cfg
->mempool
, last
->param_slots
, ins
);
1001 } else if (ins
->flags
& MONO_INST_GC_CALLSITE
) {
1002 GCCallSite
*callsite
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (GCCallSite
));
1005 LIVENESS_DEBUG (printf ("\t%x: ", ins
->backend
.pc_offset
); mono_print_ins (ins
));
1006 LIVENESS_DEBUG (printf ("\t\tlive: "));
1009 callsite
->liveness
= mono_mempool_alloc0 (cfg
->mempool
, ALIGN_TO (cfg
->num_varinfo
, 8) / 8);
1010 callsite
->pc_offset
= ins
->backend
.pc_offset
;
1011 for (i
= 0; i
< cfg
->num_varinfo
; ++i
) {
1012 if (last_use
[i
] != 0) {
1013 LIVENESS_DEBUG (printf ("R%d", MONO_VARINFO (cfg
, i
)->vreg
));
1014 callsite
->liveness
[i
/ 8] |= (1 << (i
% 8));
1017 LIVENESS_DEBUG (printf ("\n"));
1018 *callsites
= g_slist_prepend_mempool (cfg
->mempool
, *callsites
, callsite
);
1023 get_vreg_from_var (MonoCompile
*cfg
, MonoInst
*var
)
1025 if (var
->opcode
== OP_REGVAR
)
1026 /* dreg contains a hreg, but inst_c0 still contains the var index */
1027 return MONO_VARINFO (cfg
, var
->inst_c0
)->vreg
;
1029 /* dreg still contains the vreg */
1034 * mono_analyze_liveness_gc:
1036 * Compute liveness bitmaps for each call site.
1037 * This function is a modified version of mono_analyze_liveness2 ().
1040 mono_analyze_liveness_gc (MonoCompile
*cfg
)
1042 int idx
, i
, j
, nins
, max
, max_vars
, block_from
, block_to
, pos
, reverse_len
;
1045 MonoMethodVar
**vreg_to_varinfo
= NULL
;
1049 LIVENESS_DEBUG (printf ("\n------------ GC LIVENESS: ----------\n"));
1051 max_vars
= cfg
->num_varinfo
;
1052 last_use
= g_new0 (gint32
, max_vars
);
1055 * var->inst_c0 no longer contains the variable index, so compute a mapping now.
1057 vreg_to_varinfo
= g_new0 (MonoMethodVar
*, cfg
->next_vreg
);
1058 for (idx
= 0; idx
< max_vars
; ++idx
) {
1059 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1061 vreg_to_varinfo
[vi
->vreg
] = vi
;
1065 reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * reverse_len
);
1067 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
1070 block_from
= bb
->real_native_offset
;
1071 block_to
= bb
->native_offset
+ bb
->native_length
;
1073 LIVENESS_DEBUG (printf ("GC LIVENESS BB%d:\n", bb
->block_num
));
1078 memset (last_use
, 0, max_vars
* sizeof (gint32
));
1080 /* For variables in bb->live_out, set last_use to block_to */
1082 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
1083 for (j
= 0; j
< max
; ++j
) {
1087 if (!bb
->live_out_set
)
1088 /* The variables used in this bblock are volatile anyway */
1091 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
1092 k
= (j
* BITS_PER_CHUNK
);
1094 if ((bits_out
& 1) && cfg
->varinfo
[k
]->flags
& MONO_INST_GC_TRACK
) {
1095 int vreg
= get_vreg_from_var (cfg
, cfg
->varinfo
[k
]);
1096 LIVENESS_DEBUG (printf ("Var R%d live at exit, last_use set to %x.\n", vreg
, block_to
));
1097 last_use
[k
] = block_to
;
1104 for (nins
= 0, pos
= block_from
, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
, ++pos
) {
1105 if (nins
>= reverse_len
) {
1106 int new_reverse_len
= reverse_len
* 2;
1107 MonoInst
**new_reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * new_reverse_len
);
1108 memcpy (new_reverse
, reverse
, sizeof (MonoInst
*) * reverse_len
);
1109 reverse
= new_reverse
;
1110 reverse_len
= new_reverse_len
;
1113 reverse
[nins
] = ins
;
1116 /* Process instructions backwards */
1118 for (i
= nins
- 1; i
>= 0; --i
) {
1119 MonoInst
*ins
= (MonoInst
*)reverse
[i
];
1121 update_liveness_gc (cfg
, bb
, ins
, last_use
, vreg_to_varinfo
, &callsites
);
1123 /* The callsites should already be sorted by pc offset because we added them backwards */
1124 bb
->gc_callsites
= callsites
;
1128 g_free (vreg_to_varinfo
);