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)
17 #define SPILL_COST_INCREMENT (1 << (bb->nesting << 1))
19 #define DEBUG_LIVENESS
21 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
24 * The liveness2 pass can't handle long vars on 32 bit platforms because the component
25 * vars have the same 'idx'.
27 #if SIZEOF_REGISTER == 8
28 #define ENABLE_LIVENESS2
31 #ifdef ENABLE_LIVENESS2
32 static void mono_analyze_liveness2 (MonoCompile *cfg);
36 optimize_initlocals (MonoCompile *cfg);
38 /* mono_bitset_mp_new:
40 * allocates a MonoBitSet inside a memory pool
42 static inline MonoBitSet*
43 mono_bitset_mp_new (MonoMemPool *mp, guint32 size, guint32 max_size)
45 guint8 *mem = mono_mempool_alloc0 (mp, size);
46 return mono_bitset_mem_new (mem, max_size, MONO_BITSET_DONT_FREE);
49 static inline MonoBitSet*
50 mono_bitset_mp_new_noinit (MonoMemPool *mp, guint32 size, guint32 max_size)
52 guint8 *mem = mono_mempool_alloc (mp, size);
53 return mono_bitset_mem_new (mem, max_size, MONO_BITSET_DONT_FREE);
56 G_GNUC_UNUSED static void
57 mono_bitset_print (MonoBitSet *set)
60 gboolean first = TRUE;
63 for (i = 0; i < mono_bitset_size (set); i++) {
65 if (mono_bitset_test (set, i)) {
76 visit_bb (MonoCompile *cfg, MonoBasicBlock *bb, GSList **visited)
81 if (g_slist_find (*visited, bb))
84 for (ins = bb->code; ins; ins = ins->next) {
85 const char *spec = INS_INFO (ins->opcode);
86 int regtype, srcindex, sreg, num_sregs;
87 int sregs [MONO_MAX_SRC_REGS];
89 if (ins->opcode == OP_NOP)
93 regtype = spec [MONO_INST_DEST];
94 g_assert (((ins->dreg == -1) && (regtype == ' ')) || ((ins->dreg != -1) && (regtype != ' ')));
96 if ((ins->dreg != -1) && get_vreg_to_inst (cfg, ins->dreg)) {
97 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
98 int idx = var->inst_c0;
99 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
101 cfg->varinfo [vi->idx]->flags |= MONO_INST_VOLATILE;
102 if (SIZEOF_REGISTER == 4 && (var->type == STACK_I8 || (var->type == STACK_R8 && COMPILE_SOFT_FLOAT (cfg)))) {
103 /* Make the component vregs volatile as well (#612206) */
104 get_vreg_to_inst (cfg, var->dreg + 1)->flags |= MONO_INST_VOLATILE;
105 get_vreg_to_inst (cfg, var->dreg + 2)->flags |= MONO_INST_VOLATILE;
110 num_sregs = mono_inst_get_src_registers (ins, sregs);
111 for (srcindex = 0; srcindex < num_sregs; ++srcindex) {
112 sreg = sregs [srcindex];
114 g_assert (sreg != -1);
115 if (get_vreg_to_inst (cfg, sreg)) {
116 MonoInst *var = get_vreg_to_inst (cfg, sreg);
117 int idx = var->inst_c0;
118 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
120 cfg->varinfo [vi->idx]->flags |= MONO_INST_VOLATILE;
121 if (SIZEOF_REGISTER == 4 && (var->type == STACK_I8 || (var->type == STACK_R8 && COMPILE_SOFT_FLOAT (cfg)))) {
122 /* Make the component vregs volatile as well (#612206) */
123 get_vreg_to_inst (cfg, var->dreg + 1)->flags |= MONO_INST_VOLATILE;
124 get_vreg_to_inst (cfg, var->dreg + 2)->flags |= MONO_INST_VOLATILE;
130 *visited = g_slist_append (*visited, bb);
133 * Need to visit all bblocks reachable from this one since they can be
134 * reached during exception handling.
136 for (i = 0; i < bb->out_count; ++i) {
137 visit_bb (cfg, bb->out_bb [i], visited);
142 mono_liveness_handle_exception_clauses (MonoCompile *cfg)
145 GSList *visited = NULL;
146 MonoMethodHeader *header = cfg->header;
147 MonoExceptionClause *clause, *clause2;
152 * Determine which clauses are outer try clauses, i.e. they are not contained in any
153 * other non-try clause.
155 outer_try = mono_mempool_alloc0 (cfg->mempool, sizeof (gboolean) * header->num_clauses);
156 for (i = 0; i < header->num_clauses; ++i)
157 outer_try [i] = TRUE;
158 /* Iterate over the clauses backward, so outer clauses come first */
159 /* This avoids doing an O(2) search, since we can determine when inner clauses end */
160 for (i = header->num_clauses - 1; i >= 0; --i) {
161 clause = &header->clauses [i];
163 if (clause->flags != 0) {
164 outer_try [i] = TRUE;
165 /* Iterate over inner clauses */
166 for (j = i - 1; j >= 0; --j) {
167 clause2 = &header->clauses [j];
169 if (clause2->flags == 0 && MONO_OFFSET_IN_HANDLER (clause, clause2->try_offset)) {
170 outer_try [j] = FALSE;
173 if (clause2->try_offset < clause->try_offset)
174 /* End of inner clauses */
181 * Variables in exception handler register cannot be allocated to registers
182 * so make them volatile. See bug #42136. This will not be neccessary when
183 * the back ends could guarantee that the variables will be in the
184 * correct registers when a handler is called.
185 * This includes try blocks too, since a variable in a try block might be
186 * accessed after an exception handler has been run.
188 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
190 if (bb->region == -1)
193 if (MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY) && outer_try [MONO_REGION_CLAUSE_INDEX (bb->region)])
196 if (cfg->verbose_level > 2)
197 printf ("pessimize variables in bb %d.\n", bb->block_num);
199 visit_bb (cfg, bb, &visited);
201 g_slist_free (visited);
205 update_live_range (MonoMethodVar *var, int abs_pos)
207 if (var->range.first_use.abs_pos > abs_pos)
208 var->range.first_use.abs_pos = abs_pos;
210 if (var->range.last_use.abs_pos < abs_pos)
211 var->range.last_use.abs_pos = abs_pos;
215 analyze_liveness_bb (MonoCompile *cfg, MonoBasicBlock *bb)
219 MonoMethodVar *vars = cfg->vars;
220 guint32 abs_pos = (bb->dfn << 16);
222 for (inst_num = 0, ins = bb->code; ins; ins = ins->next, inst_num += 2) {
223 const char *spec = INS_INFO (ins->opcode);
225 int sregs [MONO_MAX_SRC_REGS];
227 #ifdef DEBUG_LIVENESS
228 if (cfg->verbose_level > 1) {
230 mono_print_ins (ins);
234 if (ins->opcode == OP_NOP)
237 if (ins->opcode == OP_LDADDR) {
238 MonoInst *var = ins->inst_p0;
239 int idx = var->inst_c0;
240 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
242 #ifdef DEBUG_LIVENESS
243 if (cfg->verbose_level > 1)
244 printf ("\tGEN: R%d(%d)\n", var->dreg, idx);
246 update_live_range (&vars [idx], abs_pos + inst_num);
247 if (!mono_bitset_test_fast (bb->kill_set, idx))
248 mono_bitset_set_fast (bb->gen_set, idx);
249 vi->spill_costs += SPILL_COST_INCREMENT;
252 /* SREGs must come first, so MOVE r <- r is handled correctly */
253 num_sregs = mono_inst_get_src_registers (ins, sregs);
254 for (i = 0; i < num_sregs; ++i) {
256 if ((spec [MONO_INST_SRC1 + i] != ' ') && get_vreg_to_inst (cfg, sreg)) {
257 MonoInst *var = get_vreg_to_inst (cfg, sreg);
258 int idx = var->inst_c0;
259 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
261 #ifdef DEBUG_LIVENESS
262 if (cfg->verbose_level > 1)
263 printf ("\tGEN: R%d(%d)\n", sreg, idx);
265 update_live_range (&vars [idx], abs_pos + inst_num);
266 if (!mono_bitset_test_fast (bb->kill_set, idx))
267 mono_bitset_set_fast (bb->gen_set, idx);
268 vi->spill_costs += SPILL_COST_INCREMENT;
273 if ((spec [MONO_INST_DEST] != ' ') && get_vreg_to_inst (cfg, ins->dreg)) {
274 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
275 int idx = var->inst_c0;
276 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
278 if (MONO_IS_STORE_MEMBASE (ins)) {
279 update_live_range (&vars [idx], abs_pos + inst_num);
280 if (!mono_bitset_test_fast (bb->kill_set, idx))
281 mono_bitset_set_fast (bb->gen_set, idx);
282 vi->spill_costs += SPILL_COST_INCREMENT;
284 #ifdef DEBUG_LIVENESS
285 if (cfg->verbose_level > 1)
286 printf ("\tKILL: R%d(%d)\n", ins->dreg, idx);
288 update_live_range (&vars [idx], abs_pos + inst_num + 1);
289 mono_bitset_set_fast (bb->kill_set, idx);
290 vi->spill_costs += SPILL_COST_INCREMENT;
296 /* generic liveness analysis code. CFG specific parts are
297 * in update_gen_kill_set()
300 mono_analyze_liveness (MonoCompile *cfg)
302 MonoBitSet *old_live_out_set;
303 int i, j, max_vars = cfg->num_varinfo;
305 gboolean *in_worklist;
306 MonoBasicBlock **worklist;
310 #ifdef DEBUG_LIVENESS
311 if (cfg->verbose_level > 1)
312 printf ("\nLIVENESS:\n");
315 g_assert (!(cfg->comp_done & MONO_COMP_LIVENESS));
317 cfg->comp_done |= MONO_COMP_LIVENESS;
322 bitsize = mono_bitset_alloc_size (max_vars, 0);
324 for (i = 0; i < max_vars; i ++) {
325 MONO_VARINFO (cfg, i)->range.first_use.abs_pos = ~ 0;
326 MONO_VARINFO (cfg, i)->range.last_use .abs_pos = 0;
327 MONO_VARINFO (cfg, i)->spill_costs = 0;
330 for (i = 0; i < cfg->num_bblocks; ++i) {
331 MonoBasicBlock *bb = cfg->bblocks [i];
333 bb->gen_set = mono_bitset_mp_new (cfg->mempool, bitsize, max_vars);
334 bb->kill_set = mono_bitset_mp_new (cfg->mempool, bitsize, max_vars);
336 #ifdef DEBUG_LIVENESS
337 if (cfg->verbose_level > 1) {
338 printf ("BLOCK BB%d (", bb->block_num);
339 for (j = 0; j < bb->out_count; j++)
340 printf ("BB%d, ", bb->out_bb [j]->block_num);
346 analyze_liveness_bb (cfg, bb);
348 #ifdef DEBUG_LIVENESS
349 if (cfg->verbose_level > 1) {
350 printf ("GEN BB%d: ", bb->block_num); mono_bitset_print (bb->gen_set);
351 printf ("KILL BB%d: ", bb->block_num); mono_bitset_print (bb->kill_set);
356 old_live_out_set = mono_bitset_new (max_vars, 0);
357 in_worklist = g_new0 (gboolean, cfg->num_bblocks + 1);
359 worklist = g_new (MonoBasicBlock *, cfg->num_bblocks + 1);
363 * This is a backward dataflow analysis problem, so we process blocks in
364 * decreasing dfn order, this speeds up the iteration.
366 for (i = 0; i < cfg->num_bblocks; i ++) {
367 MonoBasicBlock *bb = cfg->bblocks [i];
369 worklist [l_end ++] = bb;
370 in_worklist [bb->dfn] = TRUE;
372 /* Initialized later */
373 bb->live_in_set = NULL;
374 bb->live_out_set = mono_bitset_mp_new (cfg->mempool, bitsize, max_vars);
379 if (cfg->verbose_level > 1)
380 printf ("\nITERATION:\n");
383 MonoBasicBlock *bb = worklist [--l_end];
384 MonoBasicBlock *out_bb;
387 in_worklist [bb->dfn] = FALSE;
389 #ifdef DEBUG_LIVENESS
390 if (cfg->verbose_level > 1) {
391 printf ("P: BB%d(%d): IN: ", bb->block_num, bb->dfn);
392 for (j = 0; j < bb->in_count; ++j)
393 printf ("BB%d ", bb->in_bb [j]->block_num);
395 for (j = 0; j < bb->out_count; ++j)
396 printf ("BB%d ", bb->out_bb [j]->block_num);
402 if (bb->out_count == 0)
407 if (!bb->live_in_set) {
408 /* First pass over this bblock */
413 mono_bitset_copyto_fast (bb->live_out_set, old_live_out_set);
416 for (j = 0; j < bb->out_count; j++) {
417 out_bb = bb->out_bb [j];
419 if (!out_bb->live_in_set) {
420 out_bb->live_in_set = mono_bitset_mp_new_noinit (cfg->mempool, bitsize, max_vars);
422 mono_bitset_copyto_fast (out_bb->live_out_set, out_bb->live_in_set);
423 mono_bitset_sub_fast (out_bb->live_in_set, out_bb->kill_set);
424 mono_bitset_union_fast (out_bb->live_in_set, out_bb->gen_set);
427 // FIXME: Do this somewhere else
428 if (bb->last_ins && bb->last_ins->opcode == OP_NOT_REACHED) {
430 mono_bitset_union_fast (bb->live_out_set, out_bb->live_in_set);
434 if (changed || !mono_bitset_equal (old_live_out_set, bb->live_out_set)) {
435 if (!bb->live_in_set)
436 bb->live_in_set = mono_bitset_mp_new_noinit (cfg->mempool, bitsize, max_vars);
437 mono_bitset_copyto_fast (bb->live_out_set, bb->live_in_set);
438 mono_bitset_sub_fast (bb->live_in_set, bb->kill_set);
439 mono_bitset_union_fast (bb->live_in_set, bb->gen_set);
441 for (j = 0; j < bb->in_count; j++) {
442 MonoBasicBlock *in_bb = bb->in_bb [j];
444 * Some basic blocks do not seem to be in the
445 * cfg->bblocks array...
447 if (in_bb->gen_set && !in_worklist [in_bb->dfn]) {
448 #ifdef DEBUG_LIVENESS
449 if (cfg->verbose_level > 1)
450 printf ("\tADD: %d\n", in_bb->block_num);
453 * Put the block at the top of the stack, so it
454 * will be processed right away.
456 worklist [l_end ++] = in_bb;
457 in_worklist [in_bb->dfn] = TRUE;
462 if (G_UNLIKELY (cfg->verbose_level > 1)) {
463 printf ("\tLIVE IN BB%d: ", bb->block_num);
464 mono_bitset_print (bb->live_in_set);
468 #ifdef DEBUG_LIVENESS
469 if (cfg->verbose_level > 1)
470 printf ("IT: %d %d.\n", cfg->num_bblocks, out_iter);
473 mono_bitset_free (old_live_out_set);
476 g_free (in_worklist);
478 /* Compute live_in_set for bblocks skipped earlier */
479 for (i = 0; i < cfg->num_bblocks; ++i) {
480 MonoBasicBlock *bb = cfg->bblocks [i];
482 if (!bb->live_in_set) {
483 bb->live_in_set = mono_bitset_mp_new (cfg->mempool, bitsize, max_vars);
485 mono_bitset_copyto_fast (bb->live_out_set, bb->live_in_set);
486 mono_bitset_sub_fast (bb->live_in_set, bb->kill_set);
487 mono_bitset_union_fast (bb->live_in_set, bb->gen_set);
491 for (i = 0; i < cfg->num_bblocks; ++i) {
492 MonoBasicBlock *bb = cfg->bblocks [i];
494 guint32 abs_pos = (bb->dfn << 16);
495 MonoMethodVar *vars = cfg->vars;
497 if (!bb->live_out_set)
500 max = ((max_vars + (BITS_PER_CHUNK -1)) / BITS_PER_CHUNK);
501 for (j = 0; j < max; ++j) {
506 bits_in = mono_bitset_get_fast (bb->live_in_set, j);
507 bits_out = mono_bitset_get_fast (bb->live_out_set, j);
509 k = (j * BITS_PER_CHUNK);
510 while ((bits_in || bits_out)) {
512 update_live_range (&vars [k], abs_pos + 0);
514 update_live_range (&vars [k], abs_pos + 0xffff);
523 * Arguments need to have their live ranges extended to the beginning of
524 * the method to account for the arg reg/memory -> global register copies
525 * in the prolog (bug #74992).
528 for (i = 0; i < max_vars; i ++) {
529 MonoMethodVar *vi = MONO_VARINFO (cfg, i);
530 if (cfg->varinfo [vi->idx]->opcode == OP_ARG) {
531 if (vi->range.last_use.abs_pos == 0 && !(cfg->varinfo [vi->idx]->flags & (MONO_INST_VOLATILE|MONO_INST_INDIRECT))) {
533 * Can't eliminate the this variable in gshared code, since
534 * it is needed during exception handling to identify the
536 * It is better to check for this here instead of marking the variable
537 * VOLATILE, since that would prevent it from being allocated to
540 if (!cfg->disable_deadce_vars && !(cfg->generic_sharing_context && mono_method_signature (cfg->method)->hasthis && cfg->varinfo [vi->idx] == cfg->args [0]))
541 cfg->varinfo [vi->idx]->flags |= MONO_INST_IS_DEAD;
543 vi->range.first_use.abs_pos = 0;
547 #ifdef DEBUG_LIVENESS
548 if (cfg->verbose_level > 1) {
549 for (i = cfg->num_bblocks - 1; i >= 0; i--) {
550 MonoBasicBlock *bb = cfg->bblocks [i];
552 printf ("LIVE IN BB%d: ", bb->block_num);
553 mono_bitset_print (bb->live_in_set);
554 printf ("LIVE OUT BB%d: ", bb->block_num);
555 mono_bitset_print (bb->live_out_set);
558 for (i = 0; i < max_vars; i ++) {
559 MonoMethodVar *vi = MONO_VARINFO (cfg, i);
561 printf ("V%d: [0x%x - 0x%x]\n", i, vi->range.first_use.abs_pos, vi->range.last_use.abs_pos);
566 if (!cfg->disable_initlocals_opt)
567 optimize_initlocals (cfg);
569 #ifdef ENABLE_LIVENESS2
570 /* This improves code size by about 5% but slows down compilation too much */
571 if (cfg->compile_aot)
572 mono_analyze_liveness2 (cfg);
577 * optimize_initlocals:
579 * Try to optimize away some of the redundant initialization code inserted because of
580 * 'locals init' using the liveness information.
583 optimize_initlocals (MonoCompile *cfg)
587 MonoBasicBlock *initlocals_bb;
589 used = mono_bitset_new (cfg->next_vreg + 1, 0);
591 mono_bitset_clear_all (used);
592 initlocals_bb = cfg->bb_entry->next_bb;
593 for (ins = initlocals_bb->code; ins; ins = ins->next) {
595 int sregs [MONO_MAX_SRC_REGS];
597 num_sregs = mono_inst_get_src_registers (ins, sregs);
598 for (i = 0; i < num_sregs; ++i)
599 mono_bitset_set_fast (used, sregs [i]);
601 if (MONO_IS_STORE_MEMBASE (ins))
602 mono_bitset_set_fast (used, ins->dreg);
605 for (ins = initlocals_bb->code; ins; ins = ins->next) {
606 const char *spec = INS_INFO (ins->opcode);
608 /* Look for statements whose dest is not used in this bblock and not live on exit. */
609 if ((spec [MONO_INST_DEST] != ' ') && !MONO_IS_STORE_MEMBASE (ins)) {
610 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
612 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))) {
613 //printf ("DEAD: "); mono_print_ins (ins);
614 if (cfg->disable_initlocals_opt_refs && var->type == STACK_OBJ)
616 if ((ins->opcode == OP_ICONST) || (ins->opcode == OP_I8CONST) || (ins->opcode == OP_R8CONST)) {
618 MONO_VARINFO (cfg, var->inst_c0)->spill_costs -= 1;
620 * We should shorten the liveness interval of these vars as well, but
621 * don't have enough info to do that.
632 mono_linterval_add_range (MonoCompile *cfg, MonoLiveInterval *interval, int from, int to)
634 MonoLiveRange2 *prev_range, *next_range, *new_range;
636 g_assert (to >= from);
638 /* Optimize for extending the first interval backwards */
639 if (G_LIKELY (interval->range && (interval->range->from > from) && (interval->range->from == to))) {
640 interval->range->from = from;
644 /* Find a place in the list for the new range */
646 next_range = interval->range;
647 while ((next_range != NULL) && (next_range->from <= from)) {
648 prev_range = next_range;
649 next_range = next_range->next;
652 if (prev_range && prev_range->to == from) {
653 /* Merge with previous */
655 } else if (next_range && next_range->from == to) {
656 /* Merge with previous */
657 next_range->from = from;
660 new_range = mono_mempool_alloc (cfg->mempool, sizeof (MonoLiveRange2));
661 new_range->from = from;
663 new_range->next = NULL;
666 prev_range->next = new_range;
668 interval->range = new_range;
670 new_range->next = next_range;
672 interval->last_range = new_range;
675 /* FIXME: Merge intersecting ranges */
679 mono_linterval_print (MonoLiveInterval *interval)
681 MonoLiveRange2 *range;
683 for (range = interval->range; range != NULL; range = range->next)
684 printf ("[%x-%x] ", range->from, range->to);
688 mono_linterval_print_nl (MonoLiveInterval *interval)
690 mono_linterval_print (interval);
695 * mono_linterval_convers:
697 * Return whenever INTERVAL covers the position POS.
700 mono_linterval_covers (MonoLiveInterval *interval, int pos)
702 MonoLiveRange2 *range;
704 for (range = interval->range; range != NULL; range = range->next) {
705 if (pos >= range->from && pos <= range->to)
707 if (range->from > pos)
715 * mono_linterval_get_intersect_pos:
717 * Determine whenever I1 and I2 intersect, and if they do, return the first
718 * point of intersection. Otherwise, return -1.
721 mono_linterval_get_intersect_pos (MonoLiveInterval *i1, MonoLiveInterval *i2)
723 MonoLiveRange2 *r1, *r2;
725 /* FIXME: Optimize this */
726 for (r1 = i1->range; r1 != NULL; r1 = r1->next) {
727 for (r2 = i2->range; r2 != NULL; r2 = r2->next) {
728 if (r2->to > r1->from && r2->from < r1->to) {
729 if (r2->from <= r1->from)
741 * mono_linterval_split
743 * Split L at POS and store the newly created intervals into L1 and L2. POS becomes
747 mono_linterval_split (MonoCompile *cfg, MonoLiveInterval *interval, MonoLiveInterval **i1, MonoLiveInterval **i2, int pos)
751 g_assert (pos > interval->range->from && pos <= interval->last_range->to);
753 *i1 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoLiveInterval));
754 *i2 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoLiveInterval));
756 for (r = interval->range; r; r = r->next) {
758 /* Add it to the first child */
759 mono_linterval_add_range (cfg, *i1, r->from, r->to);
760 } else if (pos > r->from && pos <= r->to) {
762 mono_linterval_add_range (cfg, *i1, r->from, pos - 1);
763 mono_linterval_add_range (cfg, *i2, pos, r->to);
765 /* Add it to the second child */
766 mono_linterval_add_range (cfg, *i2, r->from, r->to);
772 #define LIVENESS_DEBUG(a) do { if (cfg->verbose_level > 1) do { a; } while (0); } while (0)
773 #define ENABLE_LIVENESS_DEBUG 1
775 #define LIVENESS_DEBUG(a)
778 #ifdef ENABLE_LIVENESS2
781 update_liveness2 (MonoCompile *cfg, MonoInst *ins, gboolean set_volatile, int inst_num, gint32 *last_use)
783 const char *spec = INS_INFO (ins->opcode);
786 int sregs [MONO_MAX_SRC_REGS];
788 LIVENESS_DEBUG (printf ("\t%x: ", inst_num); mono_print_ins (ins));
790 if (ins->opcode == OP_NOP)
794 if ((spec [MONO_INST_DEST] != ' ') && get_vreg_to_inst (cfg, ins->dreg)) {
795 MonoInst *var = get_vreg_to_inst (cfg, ins->dreg);
796 int idx = var->inst_c0;
797 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
799 if (MONO_IS_STORE_MEMBASE (ins)) {
800 if (last_use [idx] == 0) {
801 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins->dreg, inst_num));
802 last_use [idx] = inst_num;
805 if (last_use [idx] > 0) {
806 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", ins->dreg, inst_num, last_use [idx]));
807 mono_linterval_add_range (cfg, vi->interval, inst_num, last_use [idx]);
811 /* Try dead code elimination */
812 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)) {
813 LIVENESS_DEBUG (printf ("\tdead def of R%d, eliminated\n", ins->dreg));
814 ins->opcode = OP_NOP;
816 MONO_INST_NULLIFY_SREGS (ins);
820 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));
821 mono_linterval_add_range (cfg, vi->interval, inst_num, inst_num + 1);
827 num_sregs = mono_inst_get_src_registers (ins, sregs);
828 for (i = 0; i < num_sregs; ++i) {
830 if ((spec [MONO_INST_SRC1 + i] != ' ') && get_vreg_to_inst (cfg, sreg)) {
831 MonoInst *var = get_vreg_to_inst (cfg, sreg);
832 int idx = var->inst_c0;
834 if (last_use [idx] == 0) {
835 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg, inst_num));
836 last_use [idx] = inst_num;
843 mono_analyze_liveness2 (MonoCompile *cfg)
845 int bnum, idx, i, j, nins, max, max_vars, block_from, block_to, pos, reverse_len;
847 static guint32 disabled = -1;
851 disabled = getenv ("DISABLED") != NULL;
856 LIVENESS_DEBUG (printf ("LIVENESS 2 %s\n", mono_method_full_name (cfg->method, TRUE)));
859 if (strstr (cfg->method->name, "test_") != cfg->method->name)
863 max_vars = cfg->num_varinfo;
864 last_use = g_new0 (gint32, max_vars);
867 reverse = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * reverse_len);
869 for (idx = 0; idx < max_vars; ++idx) {
870 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
872 vi->interval = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoLiveInterval));
876 * Process bblocks in reverse order, so the addition of new live ranges
877 * to the intervals is faster.
879 for (bnum = cfg->num_bblocks - 1; bnum >= 0; --bnum) {
880 MonoBasicBlock *bb = cfg->bblocks [bnum];
883 block_from = (bb->dfn << 16) + 1; /* so pos > 0 */
884 if (bnum < cfg->num_bblocks - 1)
885 /* Beginning of the next bblock */
886 block_to = (cfg->bblocks [bnum + 1]->dfn << 16) + 1;
888 block_to = (bb->dfn << 16) + 0xffff;
890 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb->block_num));
892 memset (last_use, 0, max_vars * sizeof (gint32));
894 /* For variables in bb->live_out, set last_use to block_to */
896 max = ((max_vars + (BITS_PER_CHUNK -1)) / BITS_PER_CHUNK);
897 for (j = 0; j < max; ++j) {
901 bits_out = mono_bitset_get_fast (bb->live_out_set, j);
902 k = (j * BITS_PER_CHUNK);
905 LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", cfg->varinfo [k]->dreg, block_to));
906 last_use [k] = block_to;
914 last_use [cfg->ret->inst_c0] = block_to;
916 for (nins = 0, pos = block_from, ins = bb->code; ins; ins = ins->next, ++nins, ++pos) {
917 if (nins >= reverse_len) {
918 int new_reverse_len = reverse_len * 2;
919 MonoInst **new_reverse = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * new_reverse_len);
920 memcpy (new_reverse, reverse, sizeof (MonoInst*) * reverse_len);
921 reverse = new_reverse;
922 reverse_len = new_reverse_len;
925 reverse [nins] = ins;
928 /* Process instructions backwards */
929 for (i = nins - 1; i >= 0; --i) {
930 MonoInst *ins = (MonoInst*)reverse [i];
932 update_liveness2 (cfg, ins, FALSE, pos, last_use);
937 for (idx = 0; idx < max_vars; ++idx) {
938 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
940 if (last_use [idx] != 0) {
941 /* Live at exit, not written -> live on enter */
942 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]));
943 mono_linterval_add_range (cfg, vi->interval, block_from, last_use [idx]);
949 * Arguments need to have their live ranges extended to the beginning of
950 * the method to account for the arg reg/memory -> global register copies
951 * in the prolog (bug #74992).
953 for (i = 0; i < max_vars; i ++) {
954 MonoMethodVar *vi = MONO_VARINFO (cfg, i);
955 if (cfg->varinfo [vi->idx]->opcode == OP_ARG)
956 mono_linterval_add_range (cfg, vi->interval, 0, 1);
960 for (idx = 0; idx < max_vars; ++idx) {
961 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
963 LIVENESS_DEBUG (printf ("LIVENESS R%d: ", cfg->varinfo [idx]->dreg));
964 LIVENESS_DEBUG (mono_linterval_print (vi->interval));
965 LIVENESS_DEBUG (printf ("\n"));
974 #define ALIGN_TO(val,align) ((((guint64)val) + ((align) - 1)) & ~((align) - 1))
977 update_liveness_gc (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *ins, gint32 *last_use, MonoMethodVar **vreg_to_varinfo, GSList **callsites)
979 if (ins->opcode == OP_GC_LIVENESS_DEF || ins->opcode == OP_GC_LIVENESS_USE) {
980 int vreg = ins->inst_c1;
981 MonoMethodVar *vi = vreg_to_varinfo [vreg];
983 int pc_offset = ins->backend.pc_offset;
985 LIVENESS_DEBUG (printf ("\t%x: ", pc_offset); mono_print_ins (ins));
987 if (ins->opcode == OP_GC_LIVENESS_DEF) {
988 if (last_use [idx] > 0) {
989 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", vreg, pc_offset, last_use [idx]));
993 if (last_use [idx] == 0) {
994 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", vreg, pc_offset));
995 last_use [idx] = pc_offset;
998 } else if (ins->opcode == OP_GC_PARAM_SLOT_LIVENESS_DEF) {
1001 /* Add it to the last callsite */
1002 g_assert (*callsites);
1003 last = (*callsites)->data;
1004 last->param_slots = g_slist_prepend_mempool (cfg->mempool, last->param_slots, ins);
1005 } else if (ins->flags & MONO_INST_GC_CALLSITE) {
1006 GCCallSite *callsite = mono_mempool_alloc0 (cfg->mempool, sizeof (GCCallSite));
1009 LIVENESS_DEBUG (printf ("\t%x: ", ins->backend.pc_offset); mono_print_ins (ins));
1010 LIVENESS_DEBUG (printf ("\t\tlive: "));
1013 callsite->liveness = mono_mempool_alloc0 (cfg->mempool, ALIGN_TO (cfg->num_varinfo, 8) / 8);
1014 callsite->pc_offset = ins->backend.pc_offset;
1015 for (i = 0; i < cfg->num_varinfo; ++i) {
1016 if (last_use [i] != 0) {
1017 LIVENESS_DEBUG (printf ("R%d", MONO_VARINFO (cfg, i)->vreg));
1018 callsite->liveness [i / 8] |= (1 << (i % 8));
1021 LIVENESS_DEBUG (printf ("\n"));
1022 *callsites = g_slist_prepend_mempool (cfg->mempool, *callsites, callsite);
1027 get_vreg_from_var (MonoCompile *cfg, MonoInst *var)
1029 if (var->opcode == OP_REGVAR)
1030 /* dreg contains a hreg, but inst_c0 still contains the var index */
1031 return MONO_VARINFO (cfg, var->inst_c0)->vreg;
1033 /* dreg still contains the vreg */
1038 * mono_analyze_liveness_gc:
1040 * Compute liveness bitmaps for each call site.
1041 * This function is a modified version of mono_analyze_liveness2 ().
1044 mono_analyze_liveness_gc (MonoCompile *cfg)
1046 int idx, i, j, nins, max, max_vars, block_from, block_to, pos, reverse_len;
1049 MonoMethodVar **vreg_to_varinfo = NULL;
1053 LIVENESS_DEBUG (printf ("\n------------ GC LIVENESS: ----------\n"));
1055 max_vars = cfg->num_varinfo;
1056 last_use = g_new0 (gint32, max_vars);
1059 * var->inst_c0 no longer contains the variable index, so compute a mapping now.
1061 vreg_to_varinfo = g_new0 (MonoMethodVar*, cfg->next_vreg);
1062 for (idx = 0; idx < max_vars; ++idx) {
1063 MonoMethodVar *vi = MONO_VARINFO (cfg, idx);
1065 vreg_to_varinfo [vi->vreg] = vi;
1069 reverse = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * reverse_len);
1071 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1074 block_from = bb->real_native_offset;
1075 block_to = bb->native_offset + bb->native_length;
1077 LIVENESS_DEBUG (printf ("GC LIVENESS BB%d:\n", bb->block_num));
1082 memset (last_use, 0, max_vars * sizeof (gint32));
1084 /* For variables in bb->live_out, set last_use to block_to */
1086 max = ((max_vars + (BITS_PER_CHUNK -1)) / BITS_PER_CHUNK);
1087 for (j = 0; j < max; ++j) {
1091 if (!bb->live_out_set)
1092 /* The variables used in this bblock are volatile anyway */
1095 bits_out = mono_bitset_get_fast (bb->live_out_set, j);
1096 k = (j * BITS_PER_CHUNK);
1098 if ((bits_out & 1) && cfg->varinfo [k]->flags & MONO_INST_GC_TRACK) {
1099 int vreg = get_vreg_from_var (cfg, cfg->varinfo [k]);
1100 LIVENESS_DEBUG (printf ("Var R%d live at exit, last_use set to %x.\n", vreg, block_to));
1101 last_use [k] = block_to;
1108 for (nins = 0, pos = block_from, ins = bb->code; ins; ins = ins->next, ++nins, ++pos) {
1109 if (nins >= reverse_len) {
1110 int new_reverse_len = reverse_len * 2;
1111 MonoInst **new_reverse = mono_mempool_alloc (cfg->mempool, sizeof (MonoInst*) * new_reverse_len);
1112 memcpy (new_reverse, reverse, sizeof (MonoInst*) * reverse_len);
1113 reverse = new_reverse;
1114 reverse_len = new_reverse_len;
1117 reverse [nins] = ins;
1120 /* Process instructions backwards */
1122 for (i = nins - 1; i >= 0; --i) {
1123 MonoInst *ins = (MonoInst*)reverse [i];
1125 update_liveness_gc (cfg, bb, ins, last_use, vreg_to_varinfo, &callsites);
1127 /* The callsites should already be sorted by pc offset because we added them backwards */
1128 bb->gc_callsites = callsites;
1132 g_free (vreg_to_varinfo);
1135 #endif /* DISABLE_JIT */