2 * liveness.c: liveness analysis
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2002 Ximian, Inc.
11 #include <mono/metadata/debug-helpers.h>
14 mono_varlist_insert_sorted (MonoCompile
*cfg
, GList
*list
, MonoMethodVar
*mv
, int sort_type
)
19 return g_list_prepend (NULL
, mv
);
21 for (l
= list
; l
; l
= l
->next
) {
22 MonoMethodVar
*v1
= l
->data
;
25 if (mv
->spill_costs
>= v1
->spill_costs
) {
26 list
= g_list_insert_before (list
, l
, mv
);
29 } else if (sort_type
== 1) {
30 if (mv
->range
.last_use
.abs_pos
<= v1
->range
.last_use
.abs_pos
) {
31 list
= g_list_insert_before (list
, l
, mv
);
35 if (mv
->range
.first_use
.abs_pos
<= v1
->range
.first_use
.abs_pos
) {
36 list
= g_list_insert_before (list
, l
, mv
);
42 list
= g_list_append (list
, mv
);
48 compare_by_first_use_func (gconstpointer a
, gconstpointer b
)
50 MonoMethodVar
*v1
= (MonoMethodVar
*)a
;
51 MonoMethodVar
*v2
= (MonoMethodVar
*)b
;
53 return v1
->range
.first_use
.abs_pos
- v2
->range
.first_use
.abs_pos
;
57 mono_varlist_sort (MonoCompile
*cfg
, GList
*list
, int sort_type
)
60 return g_list_sort (list
, compare_by_first_use_func
);
62 g_assert_not_reached ();
67 // #define DEBUG_LSCAN
70 mono_linear_scan (MonoCompile
*cfg
, GList
*vars
, GList
*regs
, regmask_t
*used_mask
)
72 GList
*l
, *a
, *active
= NULL
;
73 MonoMethodVar
*vmv
, *amv
;
74 int max_regs
, gains
[sizeof (regmask_t
) * 8];
75 regmask_t used_regs
= 0;
81 printf ("Linears scan for %s\n", mono_method_full_name (cfg
->method
, TRUE
));
85 for (l
= vars
; l
; l
= l
->next
) {
87 printf ("VAR %d %08x %08x C%d\n", vmv
->idx
, vmv
->range
.first_use
.abs_pos
,
88 vmv
->range
.last_use
.abs_pos
, vmv
->spill_costs
);
91 max_regs
= g_list_length (regs
);
93 for (l
= regs
; l
; l
= l
->next
) {
94 int regnum
= GPOINTER_TO_INT (l
->data
);
95 g_assert (regnum
< G_N_ELEMENTS (gains
));
100 for (l
= vars
; l
; l
= l
->next
) {
104 printf ("START %2d %08x %08x\n", vmv
->idx
, vmv
->range
.first_use
.abs_pos
,
105 vmv
->range
.last_use
.abs_pos
);
107 /* expire old intervals in active */
109 amv
= (MonoMethodVar
*)active
->data
;
111 if (amv
->range
.last_use
.abs_pos
> vmv
->range
.first_use
.abs_pos
)
115 printf ("EXPIR %2d %08x %08x C%d R%d\n", amv
->idx
, amv
->range
.first_use
.abs_pos
,
116 amv
->range
.last_use
.abs_pos
, amv
->spill_costs
, amv
->reg
);
118 active
= g_list_delete_link (active
, active
);
119 regs
= g_list_prepend (regs
, GINT_TO_POINTER (amv
->reg
));
120 gains
[amv
->reg
] += amv
->spill_costs
;
123 if (active
&& g_list_length (active
) == max_regs
) {
126 a
= g_list_nth (active
, max_regs
- 1);
127 amv
= (MonoMethodVar
*)a
->data
;
129 if ((cost_driven
&& amv
->spill_costs
< vmv
->spill_costs
) ||
130 (!cost_driven
&& amv
->range
.last_use
.abs_pos
> vmv
->range
.last_use
.abs_pos
)) {
133 active
= g_list_delete_link (active
, a
);
136 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, 2);
138 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, 1);
141 printf ("SPILL0 %2d %08x %08x C%d\n", amv
->idx
,
142 amv
->range
.first_use
.abs_pos
, amv
->range
.last_use
.abs_pos
,
147 printf ("SPILL1 %2d %08x %08x C%d\n", vmv
->idx
,
148 vmv
->range
.first_use
.abs_pos
, vmv
->range
.last_use
.abs_pos
,
154 /* assign register */
158 vmv
->reg
= GPOINTER_TO_INT (regs
->data
);
160 used_regs
|= 1LL << vmv
->reg
;
162 regs
= g_list_delete_link (regs
, regs
);
165 printf ("ADD %2d %08x %08x C%d R%d\n", vmv
->idx
,
166 vmv
->range
.first_use
.abs_pos
, vmv
->range
.last_use
.abs_pos
,
167 vmv
->spill_costs
, vmv
->reg
);
169 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, TRUE
);
174 for (a
= active
; a
; a
= a
->next
) {
175 amv
= (MonoMethodVar
*)a
->data
;
176 printf ("ACT %2d %08x %08x C%d R%d\n", amv
->idx
, amv
->range
.first_use
.abs_pos
,
177 amv
->range
.last_use
.abs_pos
, amv
->spill_costs
, amv
->reg
);
183 for (a
= active
; a
; a
= a
->next
) {
184 amv
= (MonoMethodVar
*)a
->data
;
185 gains
[amv
->reg
] += amv
->spill_costs
;
188 for (l
= vars
; l
; l
= l
->next
) {
192 if ((gains
[vmv
->reg
] > mono_arch_regalloc_cost (cfg
, vmv
)) && (cfg
->varinfo
[vmv
->idx
]->opcode
!= OP_REGVAR
)) {
193 cfg
->varinfo
[vmv
->idx
]->opcode
= OP_REGVAR
;
194 cfg
->varinfo
[vmv
->idx
]->dreg
= vmv
->reg
;
195 if (cfg
->verbose_level
> 2)
196 printf ("REGVAR %d C%d R%d\n", vmv
->idx
, vmv
->spill_costs
, vmv
->reg
);
198 if (cfg
->verbose_level
> 2)
199 printf ("COSTLY: %s R%d C%d C%d %s\n", mono_method_full_name (cfg
->method
, TRUE
), vmv
->idx
, vmv
->spill_costs
, mono_arch_regalloc_cost (cfg
, vmv
), mono_arch_regname (vmv
->reg
));
204 if (vmv
->reg
== -1) {
205 if ((vmv
->range
.first_use
.abs_pos
>> 16) == (vmv
->range
.last_use
.abs_pos
>> 16)) {
207 * This variables is only used in a single basic block so
208 * convert it into a virtual register.
209 * FIXME: This increases register pressure in the local
210 * allocator, leading to the well known 'branches inside
211 * basic blocks screw up the allocator' problem.
214 //#ifdef MONO_ARCH_HAS_XP_LOCAL_REGALLOC
215 cfg
->varinfo
[vmv
->idx
]->opcode
= OP_REGVAR
;
216 cfg
->varinfo
[vmv
->idx
]->dreg
= mono_regstate_next_int (cfg
->rs
);
220 if (cfg
->verbose_level
> 2)
221 printf ("NOT REGVAR: %d\n", vmv
->idx
);
226 /* Compute used regs */
228 for (l
= vars
; l
; l
= l
->next
) {
232 used_regs
|= 1LL << vmv
->reg
;
235 *used_mask
|= used_regs
;
238 if (cfg
->verbose_level
> 2)
239 printf ("EXIT: final used mask: %08x\n", *used_mask
);
243 g_list_free (active
);