2 * liveness.c: liveness analysis
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2002 Ximian, Inc.
14 #define SPILL_COST_INCREMENT (1 << (bb->nesting << 1))
16 //#define DEBUG_LIVENESS
18 #if SIZEOF_VOID_P == 8
19 #define BITS_PER_CHUNK 64
21 #define BITS_PER_CHUNK 32
25 * The liveness2 pass can't handle long vars on 32 bit platforms because the component
26 * vars have the same 'idx'.
28 #if SIZEOF_VOID_P == 8
29 //#define ENABLE_LIVENESS2
32 #ifdef ENABLE_LIVENESS2
33 static void mono_analyze_liveness2 (MonoCompile
*cfg
);
37 optimize_initlocals (MonoCompile
*cfg
);
40 optimize_initlocals2 (MonoCompile
*cfg
);
42 /* mono_bitset_mp_new:
44 * allocates a MonoBitSet inside a memory pool
46 static inline MonoBitSet
*
47 mono_bitset_mp_new (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
49 guint8
*mem
= mono_mempool_alloc0 (mp
, size
);
50 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
53 static inline MonoBitSet
*
54 mono_bitset_mp_new_noinit (MonoMemPool
*mp
, guint32 size
, guint32 max_size
)
56 guint8
*mem
= mono_mempool_alloc (mp
, size
);
57 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
60 G_GNUC_UNUSED
static void
61 mono_bitset_print (MonoBitSet
*set
)
66 for (i
= 0; i
< mono_bitset_size (set
); i
++) {
68 if (mono_bitset_test (set
, i
))
76 update_live_range (MonoCompile
*cfg
, int idx
, int block_dfn
, int tree_pos
)
78 MonoLiveRange
*range
= &MONO_VARINFO (cfg
, idx
)->range
;
79 guint32 abs_pos
= (block_dfn
<< 16) | tree_pos
;
81 if (range
->first_use
.abs_pos
> abs_pos
)
82 range
->first_use
.abs_pos
= abs_pos
;
84 if (range
->last_use
.abs_pos
< abs_pos
)
85 range
->last_use
.abs_pos
= abs_pos
;
89 update_gen_kill_set (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*inst
, int inst_num
)
92 int max_vars
= cfg
->num_varinfo
;
94 arity
= mono_burg_arity
[inst
->opcode
];
96 update_gen_kill_set (cfg
, bb
, inst
->inst_i0
, inst_num
);
99 update_gen_kill_set (cfg
, bb
, inst
->inst_i1
, inst_num
);
101 if ((inst
->ssa_op
& MONO_SSA_LOAD_STORE
) || (inst
->opcode
== OP_DUMMY_STORE
)) {
102 MonoLocalVariableList
* affected_variables
;
103 MonoLocalVariableList local_affected_variable
;
105 if (cfg
->aliasing_info
== NULL
) {
106 if ((inst
->ssa_op
== MONO_SSA_LOAD
) || (inst
->ssa_op
== MONO_SSA_STORE
) || (inst
->opcode
== OP_DUMMY_STORE
)) {
107 local_affected_variable
.variable_index
= inst
->inst_i0
->inst_c0
;
108 local_affected_variable
.next
= NULL
;
109 affected_variables
= &local_affected_variable
;
111 affected_variables
= NULL
;
114 affected_variables
= mono_aliasing_get_affected_variables_for_inst_traversing_code (cfg
->aliasing_info
, inst
);
117 if (inst
->ssa_op
& MONO_SSA_LOAD
) {
118 MonoLocalVariableList
* affected_variable
= affected_variables
;
119 while (affected_variable
!= NULL
) {
120 int idx
= affected_variable
->variable_index
;
121 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
122 g_assert (idx
< max_vars
);
123 update_live_range (cfg
, idx
, bb
->dfn
, inst_num
);
124 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
125 mono_bitset_set_fast (bb
->gen_set
, idx
);
126 if (inst
->ssa_op
== MONO_SSA_LOAD
)
127 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
129 affected_variable
= affected_variable
->next
;
131 } else if ((inst
->ssa_op
== MONO_SSA_STORE
) || (inst
->opcode
== OP_DUMMY_STORE
)) {
132 MonoLocalVariableList
* affected_variable
= affected_variables
;
133 while (affected_variable
!= NULL
) {
134 int idx
= affected_variable
->variable_index
;
135 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
136 g_assert (idx
< max_vars
);
138 //g_assert (inst->inst_i1->opcode != OP_PHI);
139 update_live_range (cfg
, idx
, bb
->dfn
, inst_num
);
140 mono_bitset_set_fast (bb
->kill_set
, idx
);
141 if (inst
->ssa_op
== MONO_SSA_STORE
)
142 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
144 affected_variable
= affected_variable
->next
;
147 } else if (inst
->opcode
== OP_JMP
) {
148 /* Keep arguments live! */
150 for (i
= 0; i
< cfg
->num_varinfo
; i
++) {
151 if (cfg
->varinfo
[i
]->opcode
== OP_ARG
) {
152 if (!mono_bitset_test_fast (bb
->kill_set
, i
))
153 mono_bitset_set_fast (bb
->gen_set
, i
);
160 update_volatile (MonoCompile
*cfg
, MonoBasicBlock
*bb
, MonoInst
*inst
)
162 int arity
= mono_burg_arity
[inst
->opcode
];
163 int max_vars
= cfg
->num_varinfo
;
166 update_volatile (cfg
, bb
, inst
->inst_i0
);
169 update_volatile (cfg
, bb
, inst
->inst_i1
);
171 if (inst
->ssa_op
& MONO_SSA_LOAD_STORE
) {
172 MonoLocalVariableList
* affected_variables
;
173 MonoLocalVariableList local_affected_variable
;
175 if (cfg
->aliasing_info
== NULL
) {
176 if ((inst
->ssa_op
== MONO_SSA_LOAD
) || (inst
->ssa_op
== MONO_SSA_STORE
)) {
177 local_affected_variable
.variable_index
= inst
->inst_i0
->inst_c0
;
178 local_affected_variable
.next
= NULL
;
179 affected_variables
= &local_affected_variable
;
181 affected_variables
= NULL
;
184 affected_variables
= mono_aliasing_get_affected_variables_for_inst_traversing_code (cfg
->aliasing_info
, inst
);
187 while (affected_variables
!= NULL
) {
188 int idx
= affected_variables
->variable_index
;
189 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
190 g_assert (idx
< max_vars
);
191 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
193 affected_variables
= affected_variables
->next
;
199 visit_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
, GSList
**visited
)
204 if (g_slist_find (*visited
, bb
))
208 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
209 const char *spec
= INS_INFO (ins
->opcode
);
210 int regtype
, srcindex
, sreg
;
212 if (ins
->opcode
== OP_NOP
)
216 regtype
= spec
[MONO_INST_DEST
];
217 g_assert (((ins
->dreg
== -1) && (regtype
== ' ')) || ((ins
->dreg
!= -1) && (regtype
!= ' ')));
219 if ((ins
->dreg
!= -1) && 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 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
228 for (srcindex
= 0; srcindex
< 2; ++srcindex
) {
229 regtype
= spec
[(srcindex
== 0) ? MONO_INST_SRC1
: MONO_INST_SRC2
];
230 sreg
= srcindex
== 0 ? ins
->sreg1
: ins
->sreg2
;
232 g_assert (((sreg
== -1) && (regtype
== ' ')) || ((sreg
!= -1) && (regtype
!= ' ')));
233 if ((sreg
!= -1) && get_vreg_to_inst (cfg
, sreg
)) {
234 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
235 int idx
= var
->inst_c0
;
236 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
238 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_VOLATILE
;
243 if (cfg
->aliasing_info
!= NULL
)
244 mono_aliasing_initialize_code_traversal (cfg
->aliasing_info
, bb
);
246 for (ins
= bb
->code
; ins
; ins
= ins
->next
) {
247 update_volatile (cfg
, bb
, ins
);
251 *visited
= g_slist_append (*visited
, bb
);
254 * Need to visit all bblocks reachable from this one since they can be
255 * reached during exception handling.
257 for (i
= 0; i
< bb
->out_count
; ++i
) {
258 visit_bb (cfg
, bb
->out_bb
[i
], visited
);
263 mono_liveness_handle_exception_clauses (MonoCompile
*cfg
)
266 GSList
*visited
= NULL
;
269 * Variables in exception handler register cannot be allocated to registers
270 * so make them volatile. See bug #42136. This will not be neccessary when
271 * the back ends could guarantee that the variables will be in the
272 * correct registers when a handler is called.
273 * This includes try blocks too, since a variable in a try block might be
274 * accessed after an exception handler has been run.
276 for (bb
= cfg
->bb_entry
; bb
; bb
= bb
->next_bb
) {
278 if (bb
->region
== -1 || MONO_BBLOCK_IS_IN_REGION (bb
, MONO_REGION_TRY
))
281 visit_bb (cfg
, bb
, &visited
);
283 g_slist_free (visited
);
287 update_live_range2 (MonoMethodVar
*var
, int abs_pos
)
289 if (var
->range
.first_use
.abs_pos
> abs_pos
)
290 var
->range
.first_use
.abs_pos
= abs_pos
;
292 if (var
->range
.last_use
.abs_pos
< abs_pos
)
293 var
->range
.last_use
.abs_pos
= abs_pos
;
297 analyze_liveness_bb (MonoCompile
*cfg
, MonoBasicBlock
*bb
)
301 MonoMethodVar
*vars
= cfg
->vars
;
302 guint32 abs_pos
= (bb
->dfn
<< 16);
304 for (inst_num
= 0, ins
= bb
->code
; ins
; ins
= ins
->next
, inst_num
+= 2) {
305 const char *spec
= INS_INFO (ins
->opcode
);
307 #ifdef DEBUG_LIVENESS
308 printf ("\t"); mono_print_ins (ins
);
311 if (ins
->opcode
== OP_NOP
)
314 if (ins
->opcode
== OP_LDADDR
) {
315 MonoInst
*var
= ins
->inst_p0
;
316 int idx
= var
->inst_c0
;
317 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
319 #ifdef DEBUG_LIVENESS
320 printf ("\tGEN: R%d(%d)\n", var
->dreg
, idx
);
322 update_live_range2 (&vars
[idx
], abs_pos
+ inst_num
);
323 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
324 mono_bitset_set_fast (bb
->gen_set
, idx
);
325 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
328 /* SREGs must come first, so MOVE r <- r is handled correctly */
332 if ((spec
[MONO_INST_SRC1
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
333 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
334 int idx
= var
->inst_c0
;
335 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
337 #ifdef DEBUG_LIVENESS
338 printf ("\tGEN: R%d(%d)\n", sreg
, idx
);
340 update_live_range2 (&vars
[idx
], abs_pos
+ inst_num
);
341 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
342 mono_bitset_set_fast (bb
->gen_set
, idx
);
343 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
348 if ((spec
[MONO_INST_SRC2
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
349 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
350 int idx
= var
->inst_c0
;
351 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
353 #ifdef DEBUG_LIVENESS
354 printf ("\tGEN: R%d(%d)\n", sreg
, idx
);
356 update_live_range2 (&vars
[idx
], abs_pos
+ inst_num
);
357 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
358 mono_bitset_set_fast (bb
->gen_set
, idx
);
359 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
363 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
364 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
365 int idx
= var
->inst_c0
;
366 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
368 if (MONO_IS_STORE_MEMBASE (ins
)) {
369 update_live_range2 (&vars
[idx
], abs_pos
+ inst_num
);
370 if (!mono_bitset_test_fast (bb
->kill_set
, idx
))
371 mono_bitset_set_fast (bb
->gen_set
, idx
);
372 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
374 #ifdef DEBUG_LIVENESS
375 printf ("\tKILL: R%d(%d)\n", ins
->dreg
, idx
);
377 update_live_range2 (&vars
[idx
], abs_pos
+ inst_num
+ 1);
378 mono_bitset_set_fast (bb
->kill_set
, idx
);
379 vi
->spill_costs
+= SPILL_COST_INCREMENT
;
385 /* generic liveness analysis code. CFG specific parts are
386 * in update_gen_kill_set()
389 mono_analyze_liveness (MonoCompile
*cfg
)
391 MonoBitSet
*old_live_out_set
;
392 int i
, j
, max_vars
= cfg
->num_varinfo
;
394 gboolean
*in_worklist
;
395 MonoBasicBlock
**worklist
;
399 #ifdef DEBUG_LIVENESS
400 printf ("LIVENESS %s\n", mono_method_full_name (cfg
->method
, TRUE
));
403 g_assert (!(cfg
->comp_done
& MONO_COMP_LIVENESS
));
405 cfg
->comp_done
|= MONO_COMP_LIVENESS
;
410 bitsize
= mono_bitset_alloc_size (max_vars
, 0);
412 for (i
= 0; i
< max_vars
; i
++) {
413 MONO_VARINFO (cfg
, i
)->range
.first_use
.abs_pos
= ~ 0;
414 MONO_VARINFO (cfg
, i
)->range
.last_use
.abs_pos
= 0;
415 MONO_VARINFO (cfg
, i
)->spill_costs
= 0;
418 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
419 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
423 bb
->gen_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
424 bb
->kill_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
427 analyze_liveness_bb (cfg
, bb
);
429 if (cfg
->aliasing_info
!= NULL
)
430 mono_aliasing_initialize_code_traversal (cfg
->aliasing_info
, bb
);
433 MONO_BB_FOR_EACH_INS (bb
, inst
) {
434 #ifdef DEBUG_LIVENESS
435 mono_print_tree (inst
); printf ("\n");
437 update_gen_kill_set (cfg
, bb
, inst
, tree_num
);
442 #ifdef DEBUG_LIVENESS
443 printf ("BLOCK BB%d (", bb
->block_num
);
444 for (j
= 0; j
< bb
->out_count
; j
++)
445 printf ("BB%d, ", bb
->out_bb
[j
]->block_num
);
448 printf ("GEN BB%d: ", bb
->block_num
); mono_bitset_print (bb
->gen_set
);
449 printf ("KILL BB%d: ", bb
->block_num
); mono_bitset_print (bb
->kill_set
);
453 old_live_out_set
= mono_bitset_new (max_vars
, 0);
454 in_worklist
= g_new0 (gboolean
, cfg
->num_bblocks
+ 1);
456 worklist
= g_new (MonoBasicBlock
*, cfg
->num_bblocks
+ 1);
460 * This is a backward dataflow analysis problem, so we process blocks in
461 * decreasing dfn order, this speeds up the iteration.
463 for (i
= 0; i
< cfg
->num_bblocks
; i
++) {
464 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
466 worklist
[l_end
++] = bb
;
467 in_worklist
[bb
->dfn
] = TRUE
;
469 /* Initialized later */
470 bb
->live_in_set
= NULL
;
471 bb
->live_out_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
477 MonoBasicBlock
*bb
= worklist
[--l_end
];
478 MonoBasicBlock
*out_bb
;
481 in_worklist
[bb
->dfn
] = FALSE
;
483 #ifdef DEBUG_LIVENESS
484 printf ("P: %d(%d): IN: ", bb
->block_num
, bb
->dfn
);
485 for (j
= 0; j
< bb
->in_count
; ++j
)
486 printf ("BB%d ", bb
->in_bb
[j
]->block_num
);
488 for (j
= 0; j
< bb
->out_count
; ++j
)
489 printf ("BB%d ", bb
->out_bb
[j
]->block_num
);
494 if (bb
->out_count
== 0)
499 if (!bb
->live_in_set
) {
500 /* First pass over this bblock */
505 mono_bitset_copyto_fast (bb
->live_out_set
, old_live_out_set
);
508 for (j
= 0; j
< bb
->out_count
; j
++) {
509 out_bb
= bb
->out_bb
[j
];
511 if (!out_bb
->live_in_set
) {
512 out_bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
514 mono_bitset_copyto_fast (out_bb
->live_out_set
, out_bb
->live_in_set
);
515 mono_bitset_sub_fast (out_bb
->live_in_set
, out_bb
->kill_set
);
516 mono_bitset_union_fast (out_bb
->live_in_set
, out_bb
->gen_set
);
519 mono_bitset_union_fast (bb
->live_out_set
, out_bb
->live_in_set
);
522 if (changed
|| !mono_bitset_equal (old_live_out_set
, bb
->live_out_set
)) {
523 if (!bb
->live_in_set
)
524 bb
->live_in_set
= mono_bitset_mp_new_noinit (cfg
->mempool
, bitsize
, max_vars
);
525 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
526 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
527 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
529 for (j
= 0; j
< bb
->in_count
; j
++) {
530 MonoBasicBlock
*in_bb
= bb
->in_bb
[j
];
532 * Some basic blocks do not seem to be in the
533 * cfg->bblocks array...
535 if (in_bb
->gen_set
&& !in_worklist
[in_bb
->dfn
]) {
536 #ifdef DEBUG_LIVENESS
537 printf ("\tADD: %d\n", in_bb
->block_num
);
540 * Put the block at the top of the stack, so it
541 * will be processed right away.
543 worklist
[l_end
++] = in_bb
;
544 in_worklist
[in_bb
->dfn
] = TRUE
;
550 #ifdef DEBUG_LIVENESS
551 printf ("IT: %d %d.\n", cfg
->num_bblocks
, out_iter
);
554 mono_bitset_free (old_live_out_set
);
557 g_free (in_worklist
);
559 /* Compute live_in_set for bblocks skipped earlier */
560 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
561 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
563 if (!bb
->live_in_set
) {
564 bb
->live_in_set
= mono_bitset_mp_new (cfg
->mempool
, bitsize
, max_vars
);
566 mono_bitset_copyto_fast (bb
->live_out_set
, bb
->live_in_set
);
567 mono_bitset_sub_fast (bb
->live_in_set
, bb
->kill_set
);
568 mono_bitset_union_fast (bb
->live_in_set
, bb
->gen_set
);
572 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
573 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
575 guint32 abs_pos
= (bb
->dfn
<< 16);
576 MonoMethodVar
*vars
= cfg
->vars
;
578 if (!bb
->live_out_set
)
581 rem
= max_vars
% BITS_PER_CHUNK
;
582 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
583 for (j
= 0; j
< max
; ++j
) {
588 bits_in
= mono_bitset_get_fast (bb
->live_in_set
, j
);
589 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
591 k
= (j
* BITS_PER_CHUNK
);
592 while ((bits_in
|| bits_out
)) {
594 update_live_range2 (&vars
[k
], abs_pos
+ 0);
596 update_live_range2 (&vars
[k
], abs_pos
+ 0xffff);
605 * Arguments need to have their live ranges extended to the beginning of
606 * the method to account for the arg reg/memory -> global register copies
607 * in the prolog (bug #74992).
610 for (i
= 0; i
< max_vars
; i
++) {
611 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
612 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
) {
613 if (vi
->range
.last_use
.abs_pos
== 0 && !(cfg
->varinfo
[vi
->idx
]->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
615 * Can't eliminate the this variable in gshared code, since
616 * it is needed during exception handling to identify the
618 * It is better to check for this here instead of marking the variable
619 * VOLATILE, since that would prevent it from being allocated to
622 if (!(cfg
->generic_sharing_context
&& mono_method_signature (cfg
->method
)->hasthis
&& cfg
->varinfo
[vi
->idx
] == cfg
->args
[0]))
623 cfg
->varinfo
[vi
->idx
]->flags
|= MONO_INST_IS_DEAD
;
625 vi
->range
.first_use
.abs_pos
= 0;
629 #ifdef DEBUG_LIVENESS
630 for (i
= cfg
->num_bblocks
- 1; i
>= 0; i
--) {
631 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
633 printf ("LIVE IN BB%d: ", bb
->block_num
);
634 mono_bitset_print (bb
->live_in_set
);
635 printf ("LIVE OUT BB%d: ", bb
->block_num
);
636 mono_bitset_print (bb
->live_out_set
);
641 if (!cfg
->disable_initlocals_opt
)
642 optimize_initlocals2 (cfg
);
644 #ifdef ENABLE_LIVENESS2
645 /* This improves code size by about 5% but slows down compilation too much */
646 /* FIXME: This crashes when compiling 2.0 mscorlib */
647 if (FALSE
&& cfg
->compile_aot
)
648 mono_analyze_liveness2 (cfg
);
652 if (!cfg
->disable_initlocals_opt
)
653 optimize_initlocals (cfg
);
658 * optimize_initlocals:
660 * Try to optimize away some of the redundant initialization code inserted because of
661 * 'locals init' using the liveness information.
664 optimize_initlocals2 (MonoCompile
*cfg
)
668 MonoBasicBlock
*initlocals_bb
;
670 used
= mono_bitset_new (cfg
->next_vreg
+ 1, 0);
672 mono_bitset_clear_all (used
);
673 initlocals_bb
= cfg
->bb_entry
->next_bb
;
674 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
675 const char *spec
= INS_INFO (ins
->opcode
);
677 if (spec
[MONO_INST_SRC1
] != ' ')
678 mono_bitset_set_fast (used
, ins
->sreg1
);
679 if (spec
[MONO_INST_SRC2
] != ' ')
680 mono_bitset_set_fast (used
, ins
->sreg2
);
681 if (MONO_IS_STORE_MEMBASE (ins
))
682 mono_bitset_set_fast (used
, ins
->dreg
);
685 for (ins
= initlocals_bb
->code
; ins
; ins
= ins
->next
) {
686 const char *spec
= INS_INFO (ins
->opcode
);
688 /* Look for statements whose dest is not used in this bblock and not live on exit. */
689 if ((spec
[MONO_INST_DEST
] != ' ') && !MONO_IS_STORE_MEMBASE (ins
)) {
690 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
692 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
))) {
693 //printf ("DEAD: "); mono_print_ins (ins);
694 if ((ins
->opcode
== OP_ICONST
) || (ins
->opcode
== OP_I8CONST
) || (ins
->opcode
== OP_R8CONST
)) {
696 MONO_VARINFO (cfg
, var
->inst_c0
)->spill_costs
-= 1;
698 * We should shorten the liveness interval of these vars as well, but
699 * don't have enough info to do that.
710 mono_linterval_add_range (MonoCompile
*cfg
, MonoLiveInterval
*interval
, int from
, int to
)
712 MonoLiveRange2
*prev_range
, *next_range
, *new_range
;
714 g_assert (to
>= from
);
716 /* Optimize for extending the first interval backwards */
717 if (G_LIKELY (interval
->range
&& (interval
->range
->from
> from
) && (interval
->range
->from
== to
))) {
718 interval
->range
->from
= from
;
722 /* Find a place in the list for the new range */
724 next_range
= interval
->range
;
725 while ((next_range
!= NULL
) && (next_range
->from
<= from
)) {
726 prev_range
= next_range
;
727 next_range
= next_range
->next
;
730 if (prev_range
&& prev_range
->to
== from
) {
731 /* Merge with previous */
733 } else if (next_range
&& next_range
->from
== to
) {
734 /* Merge with previous */
735 next_range
->from
= from
;
738 new_range
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoLiveRange2
));
739 new_range
->from
= from
;
741 new_range
->next
= NULL
;
744 prev_range
->next
= new_range
;
746 interval
->range
= new_range
;
748 new_range
->next
= next_range
;
750 interval
->last_range
= new_range
;
753 /* FIXME: Merge intersecting ranges */
757 mono_linterval_print (MonoLiveInterval
*interval
)
759 MonoLiveRange2
*range
;
761 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
)
762 printf ("[%x-%x] ", range
->from
, range
->to
);
766 mono_linterval_print_nl (MonoLiveInterval
*interval
)
768 mono_linterval_print (interval
);
773 * mono_linterval_convers:
775 * Return whenever INTERVAL covers the position POS.
778 mono_linterval_covers (MonoLiveInterval
*interval
, int pos
)
780 MonoLiveRange2
*range
;
782 for (range
= interval
->range
; range
!= NULL
; range
= range
->next
) {
783 if (pos
>= range
->from
&& pos
<= range
->to
)
785 if (range
->from
> pos
)
793 * mono_linterval_get_intersect_pos:
795 * Determine whenever I1 and I2 intersect, and if they do, return the first
796 * point of intersection. Otherwise, return -1.
799 mono_linterval_get_intersect_pos (MonoLiveInterval
*i1
, MonoLiveInterval
*i2
)
801 MonoLiveRange2
*r1
, *r2
;
803 /* FIXME: Optimize this */
804 for (r1
= i1
->range
; r1
!= NULL
; r1
= r1
->next
) {
805 for (r2
= i2
->range
; r2
!= NULL
; r2
= r2
->next
) {
806 if (r2
->to
> r1
->from
&& r2
->from
< r1
->to
) {
807 if (r2
->from
<= r1
->from
)
819 * mono_linterval_split
821 * Split L at POS and store the newly created intervals into L1 and L2. POS becomes
825 mono_linterval_split (MonoCompile
*cfg
, MonoLiveInterval
*interval
, MonoLiveInterval
**i1
, MonoLiveInterval
**i2
, int pos
)
829 g_assert (pos
> interval
->range
->from
&& pos
<= interval
->last_range
->to
);
831 *i1
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
832 *i2
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
834 for (r
= interval
->range
; r
; r
= r
->next
) {
836 /* Add it to the first child */
837 mono_linterval_add_range (cfg
, *i1
, r
->from
, r
->to
);
838 } else if (pos
> r
->from
&& pos
<= r
->to
) {
840 mono_linterval_add_range (cfg
, *i1
, r
->from
, pos
- 1);
841 mono_linterval_add_range (cfg
, *i2
, pos
, r
->to
);
843 /* Add it to the second child */
844 mono_linterval_add_range (cfg
, *i2
, r
->from
, r
->to
);
849 #ifdef ENABLE_LIVENESS2
852 #define LIVENESS_DEBUG(a) do { a; } while (0)
854 #define LIVENESS_DEBUG(a)
858 update_liveness2 (MonoCompile
*cfg
, MonoInst
*ins
, gboolean set_volatile
, int inst_num
, gint32
*last_use
)
860 const char *spec
= INS_INFO (ins
->opcode
);
863 LIVENESS_DEBUG (printf ("\t%x: ", inst_num
); mono_print_ins (ins
));
865 if (ins
->opcode
== OP_NOP
)
869 if ((spec
[MONO_INST_DEST
] != ' ') && get_vreg_to_inst (cfg
, ins
->dreg
)) {
870 MonoInst
*var
= get_vreg_to_inst (cfg
, ins
->dreg
);
871 int idx
= var
->inst_c0
;
872 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
874 if (MONO_IS_STORE_MEMBASE (ins
)) {
875 if (last_use
[idx
] == 0) {
876 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", ins
->dreg
, inst_num
));
877 last_use
[idx
] = inst_num
;
880 if (last_use
[idx
] > 0) {
881 LIVENESS_DEBUG (printf ("\tadd range to R%d: [%x, %x)\n", ins
->dreg
, inst_num
, last_use
[idx
]));
882 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, last_use
[idx
]);
886 /* Try dead code elimination */
887 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
)) {
888 LIVENESS_DEBUG (printf ("\tdead def of R%d, eliminated\n", ins
->dreg
));
889 ins
->opcode
= OP_NOP
;
890 ins
->dreg
= ins
->sreg1
= ins
->sreg2
= -1;
894 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));
895 mono_linterval_add_range (cfg
, vi
->interval
, inst_num
, inst_num
+ 1);
902 if ((spec
[MONO_INST_SRC1
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
903 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
904 int idx
= var
->inst_c0
;
906 if (last_use
[idx
] == 0) {
907 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
));
908 last_use
[idx
] = inst_num
;
914 if ((spec
[MONO_INST_SRC2
] != ' ') && get_vreg_to_inst (cfg
, sreg
)) {
915 MonoInst
*var
= get_vreg_to_inst (cfg
, sreg
);
916 int idx
= var
->inst_c0
;
918 if (last_use
[idx
] == 0) {
919 LIVENESS_DEBUG (printf ("\tlast use of R%d set to %x\n", sreg
, inst_num
));
920 last_use
[idx
] = inst_num
;
926 mono_analyze_liveness2 (MonoCompile
*cfg
)
928 int bnum
, idx
, i
, j
, nins
, rem
, max
, max_vars
, block_from
, block_to
, pos
, reverse_len
;
930 static guint32 disabled
= -1;
934 disabled
= getenv ("DISABLED") != NULL
;
939 LIVENESS_DEBUG (printf ("LIVENESS 2 %s\n", mono_method_full_name (cfg
->method
, TRUE
)));
942 if (strstr (cfg->method->name, "test_") != cfg->method->name)
946 max_vars
= cfg
->num_varinfo
;
947 last_use
= g_new0 (gint32
, max_vars
);
950 reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * reverse_len
);
952 for (idx
= 0; idx
< max_vars
; ++idx
) {
953 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
955 vi
->interval
= mono_mempool_alloc0 (cfg
->mempool
, sizeof (MonoLiveInterval
));
959 * Process bblocks in reverse order, so the addition of new live ranges
960 * to the intervals is faster.
962 for (bnum
= cfg
->num_bblocks
- 1; bnum
>= 0; --bnum
) {
963 MonoBasicBlock
*bb
= cfg
->bblocks
[bnum
];
966 block_from
= (bb
->dfn
<< 16) + 1; /* so pos > 0 */
967 if (bnum
< cfg
->num_bblocks
- 1)
968 /* Beginning of the next bblock */
969 block_to
= (cfg
->bblocks
[bnum
+ 1]->dfn
<< 16) + 1;
971 block_to
= (bb
->dfn
<< 16) + 0xffff;
973 LIVENESS_DEBUG (printf ("LIVENESS BLOCK BB%d:\n", bb
->block_num
));
975 memset (last_use
, 0, max_vars
* sizeof (gint32
));
977 /* For variables in bb->live_out, set last_use to block_to */
979 rem
= max_vars
% BITS_PER_CHUNK
;
980 max
= ((max_vars
+ (BITS_PER_CHUNK
-1)) / BITS_PER_CHUNK
);
981 for (j
= 0; j
< max
; ++j
) {
985 bits_out
= mono_bitset_get_fast (bb
->live_out_set
, j
);
986 k
= (j
* BITS_PER_CHUNK
);
989 LIVENESS_DEBUG (printf ("Var R%d live at exit, set last_use to %x\n", cfg
->varinfo
[k
]->dreg
, block_to
));
990 last_use
[k
] = block_to
;
998 last_use
[cfg
->ret
->inst_c0
] = block_to
;
1000 for (nins
= 0, pos
= block_from
, ins
= bb
->code
; ins
; ins
= ins
->next
, ++nins
, ++pos
) {
1001 if (nins
>= reverse_len
) {
1002 int new_reverse_len
= reverse_len
* 2;
1003 MonoInst
**new_reverse
= mono_mempool_alloc (cfg
->mempool
, sizeof (MonoInst
*) * new_reverse_len
);
1004 memcpy (new_reverse
, reverse
, sizeof (MonoInst
*) * reverse_len
);
1005 reverse
= new_reverse
;
1006 reverse_len
= new_reverse_len
;
1009 reverse
[nins
] = ins
;
1012 /* Process instructions backwards */
1013 for (i
= nins
- 1; i
>= 0; --i
) {
1014 MonoInst
*ins
= (MonoInst
*)reverse
[i
];
1016 update_liveness2 (cfg
, ins
, FALSE
, pos
, last_use
);
1021 for (idx
= 0; idx
< max_vars
; ++idx
) {
1022 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1024 if (last_use
[idx
] != 0) {
1025 /* Live at exit, not written -> live on enter */
1026 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
]));
1027 mono_linterval_add_range (cfg
, vi
->interval
, block_from
, last_use
[idx
]);
1033 * Arguments need to have their live ranges extended to the beginning of
1034 * the method to account for the arg reg/memory -> global register copies
1035 * in the prolog (bug #74992).
1037 for (i
= 0; i
< max_vars
; i
++) {
1038 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, i
);
1039 if (cfg
->varinfo
[vi
->idx
]->opcode
== OP_ARG
)
1040 mono_linterval_add_range (cfg
, vi
->interval
, 0, 1);
1044 for (idx
= 0; idx
< max_vars
; ++idx
) {
1045 MonoMethodVar
*vi
= MONO_VARINFO (cfg
, idx
);
1047 LIVENESS_DEBUG (printf ("LIVENESS R%d: ", cfg
->varinfo
[idx
]->dreg
));
1048 LIVENESS_DEBUG (mono_linterval_print (vi
->interval
));
1049 LIVENESS_DEBUG (printf ("\n"));
1059 update_used (MonoCompile
*cfg
, MonoInst
*inst
, MonoBitSet
*used
)
1061 int arity
= mono_burg_arity
[inst
->opcode
];
1064 update_used (cfg
, inst
->inst_i0
, used
);
1067 update_used (cfg
, inst
->inst_i1
, used
);
1069 if (inst
->ssa_op
& MONO_SSA_LOAD_STORE
) {
1070 if (inst
->ssa_op
== MONO_SSA_LOAD
) {
1071 int idx
= inst
->inst_i0
->inst_c0
;
1073 mono_bitset_set_fast (used
, idx
);
1079 * optimize_initlocals:
1081 * Try to optimize away some of the redundant initialization code inserted because of
1082 * 'locals init' using the liveness information.
1085 optimize_initlocals (MonoCompile
*cfg
)
1089 MonoBasicBlock
*initlocals_bb
;
1091 used
= mono_bitset_new (cfg
->num_varinfo
, 0);
1093 mono_bitset_clear_all (used
);
1094 initlocals_bb
= cfg
->bb_entry
->next_bb
;
1095 MONO_BB_FOR_EACH_INS (initlocals_bb
, ins
)
1096 update_used (cfg
, ins
, used
);
1098 MONO_BB_FOR_EACH_INS (initlocals_bb
, ins
) {
1099 if (ins
->ssa_op
== MONO_SSA_STORE
) {
1100 int idx
= ins
->inst_i0
->inst_c0
;
1101 MonoInst
*var
= cfg
->varinfo
[idx
];
1103 if (var
&& !mono_bitset_test_fast (used
, idx
) && !mono_bitset_test_fast (initlocals_bb
->live_out_set
, var
->inst_c0
) && (var
!= cfg
->ret
) && !(var
->flags
& (MONO_INST_VOLATILE
|MONO_INST_INDIRECT
))) {
1104 if (ins
->inst_i1
&& ((ins
->inst_i1
->opcode
== OP_ICONST
) || (ins
->inst_i1
->opcode
== OP_I8CONST
))) {
1106 ins
->ssa_op
= MONO_SSA_NOP
;
1107 MONO_VARINFO (cfg
, var
->inst_c0
)->spill_costs
-= 1;