2 * liveness.c: liveness analysis
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2002 Ximian, Inc.
12 #define SPILL_COST_INCREMENT (1 << (bb->nesting << 1))
14 #define DEBUG_LIVENESS
16 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
19 * The liveness2 pass can't handle long vars on 32 bit platforms because the component
20 * vars have the same 'idx'.
22 #if SIZEOF_REGISTER == 8
23 #define ENABLE_LIVENESS2
26 #ifdef ENABLE_LIVENESS2
27 static void mono_analyze_liveness2 (MonoCompile
*cfg
);
31 optimize_initlocals (MonoCompile
*cfg
);
33 /* mono_bitset_mp_new:
35 * allocates a MonoBitSet inside a memory pool
37 static inline MonoBitSet
*
38 mono_bitset_mp_new (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
40 guint8
*mem
= mono_mempool_alloc0 (mp
, size
);
41 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
44 static inline MonoBitSet
*
45 mono_bitset_mp_new_noinit (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
47 guint8
*mem
= mono_mempool_alloc (mp
, size
);
48 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
51 G_GNUC_UNUSED
static void
52 mono_bitset_print (MonoBitSet
*set
)
55 gboolean first
= TRUE
;
58 for (i
= 0; i
< mono_bitset_size (set
); i
++) {
60 if (mono_bitset_test (set
, i
)) {
71 visit_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
, GSList
**visited
)
76 if (g_slist_find (*visited
, bb
))
79 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
80 const char *spec
= INS_INFO (ins
->opcode
);
81 int regtype
, srcindex
, sreg
, num_sregs
;
82 int sregs
[MONO_MAX_SRC_REGS
];
84 if (ins
->opcode
== OP_NOP
)
88 regtype
= spec
[MONO_INST_DEST
];
89 g_assert (((ins
->dreg
== -1) && (regtype
== ' ')) || ((ins
->dreg
!= -1) && (regtype
!= ' ')));
91 if ((ins
->dreg
!= -1) && get_vreg_to_inst (cfg
, ins
->dreg
)) {
92 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
93 int idx
= var
->inst_c0
;
94 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
96 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
100 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
101 for (srcindex
= 0; srcindex
< num_sregs
; ++srcindex
) {
102 sreg
= sregs
[srcindex
];
104 g_assert (sreg
!= -1);
105 if (get_vreg_to_inst (cfg
, sreg
)) {
106 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
107 int idx
= var
->inst_c0
;
108 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
110 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
115 *visited
= g_slist_append (*visited
, bb
);
118 * Need to visit all bblocks reachable from this one since they can be
119 * reached during exception handling.
121 for (i
= 0; i
< bb
->out_count
; ++i
) {
122 visit_bb (cfg
, bb
->out_bb
[i
], visited
);
127 mono_liveness_handle_exception_clauses (MonoCompile
*cfg
)
130 GSList
*visited
= NULL
;
133 * Variables in exception handler register cannot be allocated to registers
134 * so make them volatile. See bug #42136. This will not be neccessary when
135 * the back ends could guarantee that the variables will be in the
136 * correct registers when a handler is called.
137 * This includes try blocks too, since a variable in a try block might be
138 * accessed after an exception handler has been run.
140 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
142 if (bb
->region
== -1 || MONO_BBLOCK_IS_IN_REGION (bb
, MONO_REGION_TRY
))
145 visit_bb (cfg
, bb
, &visited
);
147 g_slist_free (visited
);
151 update_live_range (MonoMethodVar
*var
, int abs_pos
)
153 if (var
->range
.first_use
.abs_pos
> abs_pos
)
154 var
->range
.first_use
.abs_pos
= abs_pos
;
156 if (var
->range
.last_use
.abs_pos
< abs_pos
)
157 var
->range
.last_use
.abs_pos
= abs_pos
;
161 analyze_liveness_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
)
165 MonoMethodVar
*vars
= cfg
->vars
;
166 guint32 abs_pos
= (bb
->dfn
<< 16);
168 for (inst_num
= 0, ins
= bb
->code
; ins
; ins
= ins
->next
, inst_num
+= 2) {
169 const char *spec
= INS_INFO (ins
->opcode
);
171 int sregs
[MONO_MAX_SRC_REGS
];
173 #ifdef DEBUG_LIVENESS
174 if (cfg
->verbose_level
> 1) {
176 mono_print_ins (ins
);
180 if (ins
->opcode
== OP_NOP
)
183 if (ins
->opcode
== OP_LDADDR
) {
184 MonoInst
*var
= ins
->inst_p0
;
185 int idx
= var
->inst_c0
;
186 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
188 #ifdef DEBUG_LIVENESS
189 if (cfg
->verbose_level
> 1)
190 printf ("\tGEN: R%d(%d)\n", var
->dreg
, idx
);
192 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
193 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
194 mono_bitset_set_fast (bb
->gen_set
, idx
);
195 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
198 /* SREGs must come first, so MOVE r <- r is handled correctly */
199 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
200 for (i
= 0; i
< num_sregs
; ++i
) {
202 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
203 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
204 int idx
= var
->inst_c0
;
205 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
207 #ifdef DEBUG_LIVENESS
208 if (cfg
->verbose_level
> 1)
209 printf ("\tGEN: R%d(%d)\n", sreg
, idx
);
211 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
212 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
213 mono_bitset_set_fast (bb
->gen_set
, idx
);
214 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
219 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
220 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
221 int idx
= var
->inst_c0
;
222 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
224 if (MONO_IS_STORE_MEMBASE (ins
)) {
225 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
226 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
227 mono_bitset_set_fast (bb
->gen_set
, idx
);
228 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
230 #ifdef DEBUG_LIVENESS
231 if (cfg
->verbose_level
> 1)
232 printf ("\tKILL: R%d(%d)\n", ins
->dreg
, idx
);
234 update_live_range (&vars
[idx
], abs_pos
+ inst_num
+ 1);
235 mono_bitset_set_fast (bb
->kill_set
, idx
);
236 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
242 /* generic liveness analysis code. CFG specific parts are
243 * in update_gen_kill_set()
246 mono_analyze_liveness (MonoCompile
*cfg
)
248 MonoBitSet
*old_live_out_set
;
249 int i
, j
, max_vars
= cfg
->num_varinfo
;
251 gboolean
*in_worklist
;
252 MonoBasicBlock
**worklist
;
256 #ifdef DEBUG_LIVENESS
257 if (cfg
->verbose_level
> 1)
258 printf ("\nLIVENESS:\n");
261 g_assert (!(cfg
->comp_done
& MONO_COMP_LIVENESS
));
263 cfg
->comp_done
|= MONO_COMP_LIVENESS
;
268 bitsize
= mono_bitset_alloc_size (max_vars
, 0);
270 for (i
= 0; i
< max_vars
; i
++) {
271 MONO_VARINFO (cfg
, i
)->range
.first_use
.abs_pos
= ~ 0;
272 MONO_VARINFO (cfg
, i
)->range
.last_use
.abs_pos
= 0;
273 MONO_VARINFO (cfg
, i
)->spill_costs
= 0;
276 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
277 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
279 bb
->gen_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
280 bb
->kill_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
282 #ifdef DEBUG_LIVENESS
283 if (cfg
->verbose_level
> 1) {
284 printf ("BLOCK BB%d (", bb
->block_num
);
285 for (j
= 0; j
< bb
->out_count
; j
++)
286 printf ("BB%d, ", bb
->out_bb
[j
]->block_num
);
292 analyze_liveness_bb (cfg
, bb
);
294 #ifdef DEBUG_LIVENESS
295 if (cfg
->verbose_level
> 1) {
296 printf ("GEN BB%d: ", bb
->block_num
); mono_bitset_print (bb
->gen_set
);
297 printf ("KILL BB%d: ", bb
->block_num
); mono_bitset_print (bb
->kill_set
);
302 old_live_out_set
= mono_bitset_new (max_vars
, 0);
303 in_worklist
= g_new0 (gboolean
, cfg
->num_bblocks
+ 1);
305 worklist
= g_new (MonoBasicBlock
*, cfg
->num_bblocks
+ 1);
309 * This is a backward dataflow analysis problem, so we process blocks in
310 * decreasing dfn order, this speeds up the iteration.
312 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
313 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
315 worklist
[l_end
++] = bb
;
316 in_worklist
[bb
->dfn
] = TRUE
;
318 /* Initialized later */
319 bb
->live_in_set
= NULL
;
320 bb
->live_out_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
325 if (cfg
->verbose_level
> 1)
326 printf ("\nITERATION:\n");
329 MonoBasicBlock
*bb
= worklist
[--l_end
];
330 MonoBasicBlock
*out_bb
;
333 in_worklist
[bb
->dfn
] = FALSE
;
335 #ifdef DEBUG_LIVENESS
336 if (cfg
->verbose_level
> 1) {
337 printf ("P: BB%d(%d): IN: ", bb
->block_num
, bb
->dfn
);
338 for (j
= 0; j
< bb
->in_count
; ++j
)
339 printf ("BB%d ", bb
->in_bb
[j
]->block_num
);
341 for (j
= 0; j
< bb
->out_count
; ++j
)
342 printf ("BB%d ", bb
->out_bb
[j
]->block_num
);
348 if (bb
->out_count
== 0)
353 if (!bb
->live_in_set
) {
354 /* First pass over this bblock */
359 mono_bitset_copyto_fast (bb
->live_out_set
, old_live_out_set
);
362 for (j
= 0; j
< bb
->out_count
; j
++) {
363 out_bb
= bb
->out_bb
[j
];
365 if (!out_bb
->live_in_set
) {
366 out_bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
368 mono_bitset_copyto_fast (out_bb
->live_out_set
, out_bb
->live_in_set
);
369 mono_bitset_sub_fast (out_bb
->live_in_set
, out_bb
->kill_set
);
370 mono_bitset_union_fast (out_bb
->live_in_set
, out_bb
->gen_set
);
373 // FIXME: Do this somewhere else
374 if (bb
->last_ins
&& bb
->last_ins
->opcode
== OP_NOT_REACHED
) {
376 mono_bitset_union_fast (bb
->live_out_set
, out_bb
->live_in_set
);
380 if (changed
|| !mono_bitset_equal (old_live_out_set
, bb
->live_out_set
)) {
381 if (!bb
->live_in_set
)
382 bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
383 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
384 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
385 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
387 for (j
= 0; j
< bb
->in_count
; j
++) {
388 MonoBasicBlock
*in_bb
= bb
->in_bb
[j
];
390 * Some basic blocks do not seem to be in the
391 * cfg->bblocks array...
393 if (in_bb
->gen_set
&& !in_worklist
[in_bb
->dfn
]) {
394 #ifdef DEBUG_LIVENESS
395 if (cfg
->verbose_level
> 1)
396 printf ("\tADD: %d\n", in_bb
->block_num
);
399 * Put the block at the top of the stack, so it
400 * will be processed right away.
402 worklist
[l_end
++] = in_bb
;
403 in_worklist
[in_bb
->dfn
] = TRUE
;
408 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
409 printf ("\tLIVE IN BB%d: ", bb
->block_num
);
410 mono_bitset_print (bb
->live_in_set
);
414 #ifdef DEBUG_LIVENESS
415 if (cfg
->verbose_level
> 1)
416 printf ("IT: %d %d.\n", cfg
->num_bblocks
, out_iter
);
419 mono_bitset_free (old_live_out_set
);
422 g_free (in_worklist
);
424 /* Compute live_in_set for bblocks skipped earlier */
425 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
426 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
428 if (!bb
->live_in_set
) {
429 bb
->live_in_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
431 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
432 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
433 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
437 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
438 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
440 guint32 abs_pos
= (bb
->dfn
<< 16);
441 MonoMethodVar
*vars
= cfg
->vars
;
443 if (!bb
->live_out_set
)
446 rem
= max_vars
% BITS_PER_CHUNK
;
447 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
448 for (j
= 0; j
< max
; ++j
) {
453 bits_in
= mono_bitset_get_fast (bb
->live_in_set
, j
);
454 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
456 k
= (j
* BITS_PER_CHUNK
);
457 while ((bits_in
|| bits_out
)) {
459 update_live_range (&vars
[k
], abs_pos
+ 0);
461 update_live_range (&vars
[k
], abs_pos
+ 0xffff);
470 * Arguments need to have their live ranges extended to the beginning of
471 * the method to account for the arg reg/memory -> global register copies
472 * in the prolog (bug #74992).
475 for (i
= 0; i
< max_vars
; i
++) {
476 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
477 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
) {
478 if (vi
->range
.last_use
.abs_pos
== 0 && !(cfg
->varinfo
[vi
->idx
]->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
480 * Can't eliminate the this variable in gshared code, since
481 * it is needed during exception handling to identify the
483 * It is better to check for this here instead of marking the variable
484 * VOLATILE, since that would prevent it from being allocated to
487 if (!cfg
->disable_deadce_vars
&& !(cfg
->generic_sharing_context
&& mono_method_signature (cfg
->method
)->hasthis
&& cfg
->varinfo
[vi
->idx
] == cfg
->args
[0]))
488 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_IS_DEAD
;
490 vi
->range
.first_use
.abs_pos
= 0;
494 #ifdef DEBUG_LIVENESS
495 if (cfg
->verbose_level
> 1) {
496 for (i
= cfg
->num_bblocks
- 1; i
>= 0; i
--) {
497 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
499 printf ("LIVE IN BB%d: ", bb
->block_num
);
500 mono_bitset_print (bb
->live_in_set
);
501 printf ("LIVE OUT BB%d: ", bb
->block_num
);
502 mono_bitset_print (bb
->live_out_set
);
505 for (i
= 0; i
< max_vars
; i
++) {
506 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
508 printf ("V%d: [0x%x - 0x%x]\n", i
, vi
->range
.first_use
.abs_pos
, vi
->range
.last_use
.abs_pos
);
513 if (!cfg
->disable_initlocals_opt
)
514 optimize_initlocals (cfg
);
516 #ifdef ENABLE_LIVENESS2
517 /* This improves code size by about 5% but slows down compilation too much */
518 if (cfg
->compile_aot
)
519 mono_analyze_liveness2 (cfg
);
524 * optimize_initlocals:
526 * Try to optimize away some of the redundant initialization code inserted because of
527 * 'locals init' using the liveness information.
530 optimize_initlocals (MonoCompile
*cfg
)
534 MonoBasicBlock
*initlocals_bb
;
536 used
= mono_bitset_new (cfg
->next_vreg
+ 1, 0);
538 mono_bitset_clear_all (used
);
539 initlocals_bb
= cfg
->bb_entry
->next_bb
;
540 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
542 int sregs
[MONO_MAX_SRC_REGS
];
544 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
545 for (i
= 0; i
< num_sregs
; ++i
)
546 mono_bitset_set_fast (used
, sregs
[i
]);
548 if (MONO_IS_STORE_MEMBASE (ins
))
549 mono_bitset_set_fast (used
, ins
->dreg
);
552 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
553 const char *spec
= INS_INFO (ins
->opcode
);
555 /* Look for statements whose dest is not used in this bblock and not live on exit. */
556 if ((spec
[MONO_INST_DEST
] != ' ') && !MONO_IS_STORE_MEMBASE (ins
)) {
557 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
559 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
))) {
560 //printf ("DEAD: "); mono_print_ins (ins);
561 if (cfg
->disable_initlocals_opt_refs
&& var
->type
== STACK_OBJ
)
563 if ((ins
->opcode
== OP_ICONST
) || (ins
->opcode
== OP_I8CONST
) || (ins
->opcode
== OP_R8CONST
)) {
565 MONO_VARINFO (cfg
, var
->inst_c0
)->spill_costs
-= 1;
567 * We should shorten the liveness interval of these vars as well, but
568 * don't have enough info to do that.
579 mono_linterval_add_range (MonoCompile
*cfg
, MonoLiveInterval
*interval
, int from
, int to
)
581 MonoLiveRange2
*prev_range
, *next_range
, *new_range
;
583 g_assert (to
>= from
);
585 /* Optimize for extending the first interval backwards */
586 if (G_LIKELY (interval
->range
&& (interval
->range
->from
> from
) && (interval
->range
->from
== to
))) {
587 interval
->range
->from
= from
;
591 /* Find a place in the list for the new range */
593 next_range
= interval
->range
;
594 while ((next_range
!= NULL
) && (next_range
->from
<= from
)) {
595 prev_range
= next_range
;
596 next_range
= next_range
->next
;
599 if (prev_range
&& prev_range
->to
== from
) {
600 /* Merge with previous */
602 } else if (next_range
&& next_range
->from
== to
) {
603 /* Merge with previous */
604 next_range
->from
= from
;
607 new_range
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoLiveRange2
));
608 new_range
->from
= from
;
610 new_range
->next
= NULL
;
613 prev_range
->next
= new_range
;
615 interval
->range
= new_range
;
617 new_range
->next
= next_range
;
619 interval
->last_range
= new_range
;
622 /* FIXME: Merge intersecting ranges */
626 mono_linterval_print (MonoLiveInterval
*interval
)
628 MonoLiveRange2
*range
;
630 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
)
631 printf ("[%x-%x] ", range
->from
, range
->to
);
635 mono_linterval_print_nl (MonoLiveInterval
*interval
)
637 mono_linterval_print (interval
);
642 * mono_linterval_convers:
644 * Return whenever INTERVAL covers the position POS.
647 mono_linterval_covers (MonoLiveInterval
*interval
, int pos
)
649 MonoLiveRange2
*range
;
651 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
) {
652 if (pos
>= range
->from
&& pos
<= range
->to
)
654 if (range
->from
> pos
)
662 * mono_linterval_get_intersect_pos:
664 * Determine whenever I1 and I2 intersect, and if they do, return the first
665 * point of intersection. Otherwise, return -1.
668 mono_linterval_get_intersect_pos (MonoLiveInterval
*i1
, MonoLiveInterval
*i2
)
670 MonoLiveRange2
*r1
, *r2
;
672 /* FIXME: Optimize this */
673 for (r1
= i1
->range
; r1
!= NULL
; r1
= r1
->next
) {
674 for (r2
= i2
->range
; r2
!= NULL
; r2
= r2
->next
) {
675 if (r2
->to
> r1
->from
&& r2
->from
< r1
->to
) {
676 if (r2
->from
<= r1
->from
)
688 * mono_linterval_split
690 * Split L at POS and store the newly created intervals into L1 and L2. POS becomes
694 mono_linterval_split (MonoCompile
*cfg
, MonoLiveInterval
*interval
, MonoLiveInterval
**i1
, MonoLiveInterval
**i2
, int pos
)
698 g_assert (pos
> interval
->range
->from
&& pos
<= interval
->last_range
->to
);
700 *i1
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
701 *i2
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
703 for (r
= interval
->range
; r
; r
= r
->next
) {
705 /* Add it to the first child */
706 mono_linterval_add_range (cfg
, *i1
, r
->from
, r
->to
);
707 } else if (pos
> r
->from
&& pos
<= r
->to
) {
709 mono_linterval_add_range (cfg
, *i1
, r
->from
, pos
- 1);
710 mono_linterval_add_range (cfg
, *i2
, pos
, r
->to
);
712 /* Add it to the second child */
713 mono_linterval_add_range (cfg
, *i2
, r
->from
, r
->to
);
718 #ifdef ENABLE_LIVENESS2
721 #define LIVENESS_DEBUG(a) do { a; } while (0)
723 #define LIVENESS_DEBUG(a)
727 update_liveness2 (MonoCompile
*cfg
, MonoInst
*ins
, gboolean set_volatile
, int inst_num
, gint32
*last_use
)
729 const char *spec
= INS_INFO (ins
->opcode
);
732 int sregs
[MONO_MAX_SRC_REGS
];
734 LIVENESS_DEBUG (printf ("\t%x: ", inst_num
); mono_print_ins (ins
));
736 if (ins
->opcode
== OP_NOP
)
740 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
741 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
742 int idx
= var
->inst_c0
;
743 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
745 if (MONO_IS_STORE_MEMBASE (ins
)) {
746 if (last_use
[idx
] == 0) {
747 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins
->dreg
, inst_num
));
748 last_use
[idx
] = inst_num
;
751 if (last_use
[idx
] > 0) {
752 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", ins
->dreg
, inst_num
, last_use
[idx
]));
753 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, last_use
[idx
]);
757 /* Try dead code elimination */
758 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
)) {
759 LIVENESS_DEBUG (printf ("\tdead def of R%d, eliminated\n", ins
->dreg
));
760 ins
->opcode
= OP_NOP
;
762 MONO_INST_NULLIFY_SREGS (ins
);
766 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));
767 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, inst_num
+ 1);
773 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
774 for (i
= 0; i
< num_sregs
; ++i
) {
776 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
777 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
778 int idx
= var
->inst_c0
;
780 if (last_use
[idx
] == 0) {
781 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
));
782 last_use
[idx
] = inst_num
;
789 mono_analyze_liveness2 (MonoCompile
*cfg
)
791 int bnum
, idx
, i
, j
, nins
, rem
, max
, max_vars
, block_from
, block_to
, pos
, reverse_len
;
793 static guint32 disabled
= -1;
797 disabled
= getenv ("DISABLED") != NULL
;
802 LIVENESS_DEBUG (printf ("LIVENESS 2 %s\n", mono_method_full_name (cfg
->method
, TRUE
)));
805 if (strstr (cfg->method->name, "test_") != cfg->method->name)
809 max_vars
= cfg
->num_varinfo
;
810 last_use
= g_new0 (gint32
, max_vars
);
813 reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * reverse_len
);
815 for (idx
= 0; idx
< max_vars
; ++idx
) {
816 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
818 vi
->interval
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
822 * Process bblocks in reverse order, so the addition of new live ranges
823 * to the intervals is faster.
825 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
826 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
829 block_from
= (bb
->dfn
<< 16) + 1; /* so pos > 0 */
830 if (bnum
< cfg
->num_bblocks
- 1)
831 /* Beginning of the next bblock */
832 block_to
= (cfg
->bblocks
[bnum
+ 1]->dfn
<< 16) + 1;
834 block_to
= (bb
->dfn
<< 16) + 0xffff;
836 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb
->block_num
));
838 memset (last_use
, 0, max_vars
* sizeof (gint32
));
840 /* For variables in bb->live_out, set last_use to block_to */
842 rem
= max_vars
% BITS_PER_CHUNK
;
843 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
844 for (j
= 0; j
< max
; ++j
) {
848 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
849 k
= (j
* BITS_PER_CHUNK
);
852 LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", cfg
->varinfo
[k
]->dreg
, block_to
));
853 last_use
[k
] = block_to
;
861 last_use
[cfg
->ret
->inst_c0
] = block_to
;
863 for (nins
= 0, pos
= block_from
, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
, ++pos
) {
864 if (nins
>= reverse_len
) {
865 int new_reverse_len
= reverse_len
* 2;
866 MonoInst
**new_reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * new_reverse_len
);
867 memcpy (new_reverse
, reverse
, sizeof (MonoInst
*) * reverse_len
);
868 reverse
= new_reverse
;
869 reverse_len
= new_reverse_len
;
872 reverse
[nins
] = ins
;
875 /* Process instructions backwards */
876 for (i
= nins
- 1; i
>= 0; --i
) {
877 MonoInst
*ins
= (MonoInst
*)reverse
[i
];
879 update_liveness2 (cfg
, ins
, FALSE
, pos
, last_use
);
884 for (idx
= 0; idx
< max_vars
; ++idx
) {
885 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
887 if (last_use
[idx
] != 0) {
888 /* Live at exit, not written -> live on enter */
889 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
]));
890 mono_linterval_add_range (cfg
, vi
->interval
, block_from
, last_use
[idx
]);
896 * Arguments need to have their live ranges extended to the beginning of
897 * the method to account for the arg reg/memory -> global register copies
898 * in the prolog (bug #74992).
900 for (i
= 0; i
< max_vars
; i
++) {
901 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
902 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
)
903 mono_linterval_add_range (cfg
, vi
->interval
, 0, 1);
907 for (idx
= 0; idx
< max_vars
; ++idx
) {
908 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
910 LIVENESS_DEBUG (printf ("LIVENESS R%d: ", cfg
->varinfo
[idx
]->dreg
));
911 LIVENESS_DEBUG (mono_linterval_print (vi
->interval
));
912 LIVENESS_DEBUG (printf ("\n"));