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
;
97 if (SIZEOF_REGISTER
== 4 && (var
->type
== STACK_I8
|| (var
->type
== STACK_R8
&& COMPILE_SOFT_FLOAT (cfg
)))) {
98 /* Make the component vregs volatile as well (#612206) */
99 get_vreg_to_inst (cfg
, var
->dreg
+ 1)->flags
|= MONO_INST_VOLATILE
;
100 get_vreg_to_inst (cfg
, var
->dreg
+ 2)->flags
|= MONO_INST_VOLATILE
;
105 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
106 for (srcindex
= 0; srcindex
< num_sregs
; ++srcindex
) {
107 sreg
= sregs
[srcindex
];
109 g_assert (sreg
!= -1);
110 if (get_vreg_to_inst (cfg
, sreg
)) {
111 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
112 int idx
= var
->inst_c0
;
113 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
115 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
116 if (SIZEOF_REGISTER
== 4 && (var
->type
== STACK_I8
|| (var
->type
== STACK_R8
&& COMPILE_SOFT_FLOAT (cfg
)))) {
117 /* Make the component vregs volatile as well (#612206) */
118 get_vreg_to_inst (cfg
, var
->dreg
+ 1)->flags
|= MONO_INST_VOLATILE
;
119 get_vreg_to_inst (cfg
, var
->dreg
+ 2)->flags
|= MONO_INST_VOLATILE
;
125 *visited
= g_slist_append (*visited
, bb
);
128 * Need to visit all bblocks reachable from this one since they can be
129 * reached during exception handling.
131 for (i
= 0; i
< bb
->out_count
; ++i
) {
132 visit_bb (cfg
, bb
->out_bb
[i
], visited
);
137 mono_liveness_handle_exception_clauses (MonoCompile
*cfg
)
140 GSList
*visited
= NULL
;
143 * Variables in exception handler register cannot be allocated to registers
144 * so make them volatile. See bug #42136. This will not be neccessary when
145 * the back ends could guarantee that the variables will be in the
146 * correct registers when a handler is called.
147 * This includes try blocks too, since a variable in a try block might be
148 * accessed after an exception handler has been run.
150 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
152 if (bb
->region
== -1 || MONO_BBLOCK_IS_IN_REGION (bb
, MONO_REGION_TRY
))
155 visit_bb (cfg
, bb
, &visited
);
157 g_slist_free (visited
);
161 update_live_range (MonoMethodVar
*var
, int abs_pos
)
163 if (var
->range
.first_use
.abs_pos
> abs_pos
)
164 var
->range
.first_use
.abs_pos
= abs_pos
;
166 if (var
->range
.last_use
.abs_pos
< abs_pos
)
167 var
->range
.last_use
.abs_pos
= abs_pos
;
171 analyze_liveness_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
)
175 MonoMethodVar
*vars
= cfg
->vars
;
176 guint32 abs_pos
= (bb
->dfn
<< 16);
178 for (inst_num
= 0, ins
= bb
->code
; ins
; ins
= ins
->next
, inst_num
+= 2) {
179 const char *spec
= INS_INFO (ins
->opcode
);
181 int sregs
[MONO_MAX_SRC_REGS
];
183 #ifdef DEBUG_LIVENESS
184 if (cfg
->verbose_level
> 1) {
186 mono_print_ins (ins
);
190 if (ins
->opcode
== OP_NOP
)
193 if (ins
->opcode
== OP_LDADDR
) {
194 MonoInst
*var
= ins
->inst_p0
;
195 int idx
= var
->inst_c0
;
196 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
198 #ifdef DEBUG_LIVENESS
199 if (cfg
->verbose_level
> 1)
200 printf ("\tGEN: R%d(%d)\n", var
->dreg
, idx
);
202 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
203 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
204 mono_bitset_set_fast (bb
->gen_set
, idx
);
205 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
208 /* SREGs must come first, so MOVE r <- r is handled correctly */
209 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
210 for (i
= 0; i
< num_sregs
; ++i
) {
212 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
213 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
214 int idx
= var
->inst_c0
;
215 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
217 #ifdef DEBUG_LIVENESS
218 if (cfg
->verbose_level
> 1)
219 printf ("\tGEN: R%d(%d)\n", sreg
, idx
);
221 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
222 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
223 mono_bitset_set_fast (bb
->gen_set
, idx
);
224 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
229 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
230 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
231 int idx
= var
->inst_c0
;
232 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
234 if (MONO_IS_STORE_MEMBASE (ins
)) {
235 update_live_range (&vars
[idx
], abs_pos
+ inst_num
);
236 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
237 mono_bitset_set_fast (bb
->gen_set
, idx
);
238 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
240 #ifdef DEBUG_LIVENESS
241 if (cfg
->verbose_level
> 1)
242 printf ("\tKILL: R%d(%d)\n", ins
->dreg
, idx
);
244 update_live_range (&vars
[idx
], abs_pos
+ inst_num
+ 1);
245 mono_bitset_set_fast (bb
->kill_set
, idx
);
246 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
252 /* generic liveness analysis code. CFG specific parts are
253 * in update_gen_kill_set()
256 mono_analyze_liveness (MonoCompile
*cfg
)
258 MonoBitSet
*old_live_out_set
;
259 int i
, j
, max_vars
= cfg
->num_varinfo
;
261 gboolean
*in_worklist
;
262 MonoBasicBlock
**worklist
;
266 #ifdef DEBUG_LIVENESS
267 if (cfg
->verbose_level
> 1)
268 printf ("\nLIVENESS:\n");
271 g_assert (!(cfg
->comp_done
& MONO_COMP_LIVENESS
));
273 cfg
->comp_done
|= MONO_COMP_LIVENESS
;
278 bitsize
= mono_bitset_alloc_size (max_vars
, 0);
280 for (i
= 0; i
< max_vars
; i
++) {
281 MONO_VARINFO (cfg
, i
)->range
.first_use
.abs_pos
= ~ 0;
282 MONO_VARINFO (cfg
, i
)->range
.last_use
.abs_pos
= 0;
283 MONO_VARINFO (cfg
, i
)->spill_costs
= 0;
286 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
287 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
289 bb
->gen_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
290 bb
->kill_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
292 #ifdef DEBUG_LIVENESS
293 if (cfg
->verbose_level
> 1) {
294 printf ("BLOCK BB%d (", bb
->block_num
);
295 for (j
= 0; j
< bb
->out_count
; j
++)
296 printf ("BB%d, ", bb
->out_bb
[j
]->block_num
);
302 analyze_liveness_bb (cfg
, bb
);
304 #ifdef DEBUG_LIVENESS
305 if (cfg
->verbose_level
> 1) {
306 printf ("GEN BB%d: ", bb
->block_num
); mono_bitset_print (bb
->gen_set
);
307 printf ("KILL BB%d: ", bb
->block_num
); mono_bitset_print (bb
->kill_set
);
312 old_live_out_set
= mono_bitset_new (max_vars
, 0);
313 in_worklist
= g_new0 (gboolean
, cfg
->num_bblocks
+ 1);
315 worklist
= g_new (MonoBasicBlock
*, cfg
->num_bblocks
+ 1);
319 * This is a backward dataflow analysis problem, so we process blocks in
320 * decreasing dfn order, this speeds up the iteration.
322 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
323 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
325 worklist
[l_end
++] = bb
;
326 in_worklist
[bb
->dfn
] = TRUE
;
328 /* Initialized later */
329 bb
->live_in_set
= NULL
;
330 bb
->live_out_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
335 if (cfg
->verbose_level
> 1)
336 printf ("\nITERATION:\n");
339 MonoBasicBlock
*bb
= worklist
[--l_end
];
340 MonoBasicBlock
*out_bb
;
343 in_worklist
[bb
->dfn
] = FALSE
;
345 #ifdef DEBUG_LIVENESS
346 if (cfg
->verbose_level
> 1) {
347 printf ("P: BB%d(%d): IN: ", bb
->block_num
, bb
->dfn
);
348 for (j
= 0; j
< bb
->in_count
; ++j
)
349 printf ("BB%d ", bb
->in_bb
[j
]->block_num
);
351 for (j
= 0; j
< bb
->out_count
; ++j
)
352 printf ("BB%d ", bb
->out_bb
[j
]->block_num
);
358 if (bb
->out_count
== 0)
363 if (!bb
->live_in_set
) {
364 /* First pass over this bblock */
369 mono_bitset_copyto_fast (bb
->live_out_set
, old_live_out_set
);
372 for (j
= 0; j
< bb
->out_count
; j
++) {
373 out_bb
= bb
->out_bb
[j
];
375 if (!out_bb
->live_in_set
) {
376 out_bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
378 mono_bitset_copyto_fast (out_bb
->live_out_set
, out_bb
->live_in_set
);
379 mono_bitset_sub_fast (out_bb
->live_in_set
, out_bb
->kill_set
);
380 mono_bitset_union_fast (out_bb
->live_in_set
, out_bb
->gen_set
);
383 // FIXME: Do this somewhere else
384 if (bb
->last_ins
&& bb
->last_ins
->opcode
== OP_NOT_REACHED
) {
386 mono_bitset_union_fast (bb
->live_out_set
, out_bb
->live_in_set
);
390 if (changed
|| !mono_bitset_equal (old_live_out_set
, bb
->live_out_set
)) {
391 if (!bb
->live_in_set
)
392 bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
393 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
394 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
395 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
397 for (j
= 0; j
< bb
->in_count
; j
++) {
398 MonoBasicBlock
*in_bb
= bb
->in_bb
[j
];
400 * Some basic blocks do not seem to be in the
401 * cfg->bblocks array...
403 if (in_bb
->gen_set
&& !in_worklist
[in_bb
->dfn
]) {
404 #ifdef DEBUG_LIVENESS
405 if (cfg
->verbose_level
> 1)
406 printf ("\tADD: %d\n", in_bb
->block_num
);
409 * Put the block at the top of the stack, so it
410 * will be processed right away.
412 worklist
[l_end
++] = in_bb
;
413 in_worklist
[in_bb
->dfn
] = TRUE
;
418 if (G_UNLIKELY (cfg
->verbose_level
> 1)) {
419 printf ("\tLIVE IN BB%d: ", bb
->block_num
);
420 mono_bitset_print (bb
->live_in_set
);
424 #ifdef DEBUG_LIVENESS
425 if (cfg
->verbose_level
> 1)
426 printf ("IT: %d %d.\n", cfg
->num_bblocks
, out_iter
);
429 mono_bitset_free (old_live_out_set
);
432 g_free (in_worklist
);
434 /* Compute live_in_set for bblocks skipped earlier */
435 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
436 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
438 if (!bb
->live_in_set
) {
439 bb
->live_in_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
441 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
442 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
443 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
447 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
448 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
450 guint32 abs_pos
= (bb
->dfn
<< 16);
451 MonoMethodVar
*vars
= cfg
->vars
;
453 if (!bb
->live_out_set
)
456 rem
= max_vars
% BITS_PER_CHUNK
;
457 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
458 for (j
= 0; j
< max
; ++j
) {
463 bits_in
= mono_bitset_get_fast (bb
->live_in_set
, j
);
464 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
466 k
= (j
* BITS_PER_CHUNK
);
467 while ((bits_in
|| bits_out
)) {
469 update_live_range (&vars
[k
], abs_pos
+ 0);
471 update_live_range (&vars
[k
], abs_pos
+ 0xffff);
480 * Arguments need to have their live ranges extended to the beginning of
481 * the method to account for the arg reg/memory -> global register copies
482 * in the prolog (bug #74992).
485 for (i
= 0; i
< max_vars
; i
++) {
486 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
487 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
) {
488 if (vi
->range
.last_use
.abs_pos
== 0 && !(cfg
->varinfo
[vi
->idx
]->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
490 * Can't eliminate the this variable in gshared code, since
491 * it is needed during exception handling to identify the
493 * It is better to check for this here instead of marking the variable
494 * VOLATILE, since that would prevent it from being allocated to
497 if (!cfg
->disable_deadce_vars
&& !(cfg
->generic_sharing_context
&& mono_method_signature (cfg
->method
)->hasthis
&& cfg
->varinfo
[vi
->idx
] == cfg
->args
[0]))
498 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_IS_DEAD
;
500 vi
->range
.first_use
.abs_pos
= 0;
504 #ifdef DEBUG_LIVENESS
505 if (cfg
->verbose_level
> 1) {
506 for (i
= cfg
->num_bblocks
- 1; i
>= 0; i
--) {
507 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
509 printf ("LIVE IN BB%d: ", bb
->block_num
);
510 mono_bitset_print (bb
->live_in_set
);
511 printf ("LIVE OUT BB%d: ", bb
->block_num
);
512 mono_bitset_print (bb
->live_out_set
);
515 for (i
= 0; i
< max_vars
; i
++) {
516 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
518 printf ("V%d: [0x%x - 0x%x]\n", i
, vi
->range
.first_use
.abs_pos
, vi
->range
.last_use
.abs_pos
);
523 if (!cfg
->disable_initlocals_opt
)
524 optimize_initlocals (cfg
);
526 #ifdef ENABLE_LIVENESS2
527 /* This improves code size by about 5% but slows down compilation too much */
528 if (cfg
->compile_aot
)
529 mono_analyze_liveness2 (cfg
);
534 * optimize_initlocals:
536 * Try to optimize away some of the redundant initialization code inserted because of
537 * 'locals init' using the liveness information.
540 optimize_initlocals (MonoCompile
*cfg
)
544 MonoBasicBlock
*initlocals_bb
;
546 used
= mono_bitset_new (cfg
->next_vreg
+ 1, 0);
548 mono_bitset_clear_all (used
);
549 initlocals_bb
= cfg
->bb_entry
->next_bb
;
550 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
552 int sregs
[MONO_MAX_SRC_REGS
];
554 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
555 for (i
= 0; i
< num_sregs
; ++i
)
556 mono_bitset_set_fast (used
, sregs
[i
]);
558 if (MONO_IS_STORE_MEMBASE (ins
))
559 mono_bitset_set_fast (used
, ins
->dreg
);
562 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
563 const char *spec
= INS_INFO (ins
->opcode
);
565 /* Look for statements whose dest is not used in this bblock and not live on exit. */
566 if ((spec
[MONO_INST_DEST
] != ' ') && !MONO_IS_STORE_MEMBASE (ins
)) {
567 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
569 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
))) {
570 //printf ("DEAD: "); mono_print_ins (ins);
571 if (cfg
->disable_initlocals_opt_refs
&& var
->type
== STACK_OBJ
)
573 if ((ins
->opcode
== OP_ICONST
) || (ins
->opcode
== OP_I8CONST
) || (ins
->opcode
== OP_R8CONST
)) {
575 MONO_VARINFO (cfg
, var
->inst_c0
)->spill_costs
-= 1;
577 * We should shorten the liveness interval of these vars as well, but
578 * don't have enough info to do that.
589 mono_linterval_add_range (MonoCompile
*cfg
, MonoLiveInterval
*interval
, int from
, int to
)
591 MonoLiveRange2
*prev_range
, *next_range
, *new_range
;
593 g_assert (to
>= from
);
595 /* Optimize for extending the first interval backwards */
596 if (G_LIKELY (interval
->range
&& (interval
->range
->from
> from
) && (interval
->range
->from
== to
))) {
597 interval
->range
->from
= from
;
601 /* Find a place in the list for the new range */
603 next_range
= interval
->range
;
604 while ((next_range
!= NULL
) && (next_range
->from
<= from
)) {
605 prev_range
= next_range
;
606 next_range
= next_range
->next
;
609 if (prev_range
&& prev_range
->to
== from
) {
610 /* Merge with previous */
612 } else if (next_range
&& next_range
->from
== to
) {
613 /* Merge with previous */
614 next_range
->from
= from
;
617 new_range
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoLiveRange2
));
618 new_range
->from
= from
;
620 new_range
->next
= NULL
;
623 prev_range
->next
= new_range
;
625 interval
->range
= new_range
;
627 new_range
->next
= next_range
;
629 interval
->last_range
= new_range
;
632 /* FIXME: Merge intersecting ranges */
636 mono_linterval_print (MonoLiveInterval
*interval
)
638 MonoLiveRange2
*range
;
640 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
)
641 printf ("[%x-%x] ", range
->from
, range
->to
);
645 mono_linterval_print_nl (MonoLiveInterval
*interval
)
647 mono_linterval_print (interval
);
652 * mono_linterval_convers:
654 * Return whenever INTERVAL covers the position POS.
657 mono_linterval_covers (MonoLiveInterval
*interval
, int pos
)
659 MonoLiveRange2
*range
;
661 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
) {
662 if (pos
>= range
->from
&& pos
<= range
->to
)
664 if (range
->from
> pos
)
672 * mono_linterval_get_intersect_pos:
674 * Determine whenever I1 and I2 intersect, and if they do, return the first
675 * point of intersection. Otherwise, return -1.
678 mono_linterval_get_intersect_pos (MonoLiveInterval
*i1
, MonoLiveInterval
*i2
)
680 MonoLiveRange2
*r1
, *r2
;
682 /* FIXME: Optimize this */
683 for (r1
= i1
->range
; r1
!= NULL
; r1
= r1
->next
) {
684 for (r2
= i2
->range
; r2
!= NULL
; r2
= r2
->next
) {
685 if (r2
->to
> r1
->from
&& r2
->from
< r1
->to
) {
686 if (r2
->from
<= r1
->from
)
698 * mono_linterval_split
700 * Split L at POS and store the newly created intervals into L1 and L2. POS becomes
704 mono_linterval_split (MonoCompile
*cfg
, MonoLiveInterval
*interval
, MonoLiveInterval
**i1
, MonoLiveInterval
**i2
, int pos
)
708 g_assert (pos
> interval
->range
->from
&& pos
<= interval
->last_range
->to
);
710 *i1
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
711 *i2
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
713 for (r
= interval
->range
; r
; r
= r
->next
) {
715 /* Add it to the first child */
716 mono_linterval_add_range (cfg
, *i1
, r
->from
, r
->to
);
717 } else if (pos
> r
->from
&& pos
<= r
->to
) {
719 mono_linterval_add_range (cfg
, *i1
, r
->from
, pos
- 1);
720 mono_linterval_add_range (cfg
, *i2
, pos
, r
->to
);
722 /* Add it to the second child */
723 mono_linterval_add_range (cfg
, *i2
, r
->from
, r
->to
);
728 #ifdef ENABLE_LIVENESS2
731 #define LIVENESS_DEBUG(a) do { a; } while (0)
733 #define LIVENESS_DEBUG(a)
737 update_liveness2 (MonoCompile
*cfg
, MonoInst
*ins
, gboolean set_volatile
, int inst_num
, gint32
*last_use
)
739 const char *spec
= INS_INFO (ins
->opcode
);
742 int sregs
[MONO_MAX_SRC_REGS
];
744 LIVENESS_DEBUG (printf ("\t%x: ", inst_num
); mono_print_ins (ins
));
746 if (ins
->opcode
== OP_NOP
)
750 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
751 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
752 int idx
= var
->inst_c0
;
753 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
755 if (MONO_IS_STORE_MEMBASE (ins
)) {
756 if (last_use
[idx
] == 0) {
757 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins
->dreg
, inst_num
));
758 last_use
[idx
] = inst_num
;
761 if (last_use
[idx
] > 0) {
762 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", ins
->dreg
, inst_num
, last_use
[idx
]));
763 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, last_use
[idx
]);
767 /* Try dead code elimination */
768 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
)) {
769 LIVENESS_DEBUG (printf ("\tdead def of R%d, eliminated\n", ins
->dreg
));
770 ins
->opcode
= OP_NOP
;
772 MONO_INST_NULLIFY_SREGS (ins
);
776 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));
777 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, inst_num
+ 1);
783 num_sregs
= mono_inst_get_src_registers (ins
, sregs
);
784 for (i
= 0; i
< num_sregs
; ++i
) {
786 if ((spec
[MONO_INST_SRC1
+ i
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
787 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
788 int idx
= var
->inst_c0
;
790 if (last_use
[idx
] == 0) {
791 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
));
792 last_use
[idx
] = inst_num
;
799 mono_analyze_liveness2 (MonoCompile
*cfg
)
801 int bnum
, idx
, i
, j
, nins
, rem
, max
, max_vars
, block_from
, block_to
, pos
, reverse_len
;
803 static guint32 disabled
= -1;
807 disabled
= getenv ("DISABLED") != NULL
;
812 LIVENESS_DEBUG (printf ("LIVENESS 2 %s\n", mono_method_full_name (cfg
->method
, TRUE
)));
815 if (strstr (cfg->method->name, "test_") != cfg->method->name)
819 max_vars
= cfg
->num_varinfo
;
820 last_use
= g_new0 (gint32
, max_vars
);
823 reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * reverse_len
);
825 for (idx
= 0; idx
< max_vars
; ++idx
) {
826 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
828 vi
->interval
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
832 * Process bblocks in reverse order, so the addition of new live ranges
833 * to the intervals is faster.
835 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
836 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
839 block_from
= (bb
->dfn
<< 16) + 1; /* so pos > 0 */
840 if (bnum
< cfg
->num_bblocks
- 1)
841 /* Beginning of the next bblock */
842 block_to
= (cfg
->bblocks
[bnum
+ 1]->dfn
<< 16) + 1;
844 block_to
= (bb
->dfn
<< 16) + 0xffff;
846 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb
->block_num
));
848 memset (last_use
, 0, max_vars
* sizeof (gint32
));
850 /* For variables in bb->live_out, set last_use to block_to */
852 rem
= max_vars
% BITS_PER_CHUNK
;
853 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
854 for (j
= 0; j
< max
; ++j
) {
858 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
859 k
= (j
* BITS_PER_CHUNK
);
862 LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", cfg
->varinfo
[k
]->dreg
, block_to
));
863 last_use
[k
] = block_to
;
871 last_use
[cfg
->ret
->inst_c0
] = block_to
;
873 for (nins
= 0, pos
= block_from
, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
, ++pos
) {
874 if (nins
>= reverse_len
) {
875 int new_reverse_len
= reverse_len
* 2;
876 MonoInst
**new_reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * new_reverse_len
);
877 memcpy (new_reverse
, reverse
, sizeof (MonoInst
*) * reverse_len
);
878 reverse
= new_reverse
;
879 reverse_len
= new_reverse_len
;
882 reverse
[nins
] = ins
;
885 /* Process instructions backwards */
886 for (i
= nins
- 1; i
>= 0; --i
) {
887 MonoInst
*ins
= (MonoInst
*)reverse
[i
];
889 update_liveness2 (cfg
, ins
, FALSE
, pos
, last_use
);
894 for (idx
= 0; idx
< max_vars
; ++idx
) {
895 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
897 if (last_use
[idx
] != 0) {
898 /* Live at exit, not written -> live on enter */
899 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
]));
900 mono_linterval_add_range (cfg
, vi
->interval
, block_from
, last_use
[idx
]);
906 * Arguments need to have their live ranges extended to the beginning of
907 * the method to account for the arg reg/memory -> global register copies
908 * in the prolog (bug #74992).
910 for (i
= 0; i
< max_vars
; i
++) {
911 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
912 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
)
913 mono_linterval_add_range (cfg
, vi
->interval
, 0, 1);
917 for (idx
= 0; idx
< max_vars
; ++idx
) {
918 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
920 LIVENESS_DEBUG (printf ("LIVENESS R%d: ", cfg
->varinfo
[idx
]->dreg
));
921 LIVENESS_DEBUG (mono_linterval_print (vi
->interval
));
922 LIVENESS_DEBUG (printf ("\n"));