2 * liveness.c: liveness analysis
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2002 Ximian, Inc.
11 #include <mono/metadata/debug-helpers.h>
12 #include <mono/utils/mono-compiler.h>
16 static void mono_linear_scan2 (MonoCompile
*cfg
, GList
*vars
, GList
*regs
, regmask_t
*used_mask
);
19 mono_varlist_insert_sorted (MonoCompile
*cfg
, GList
*list
, MonoMethodVar
*mv
, int sort_type
)
24 return g_list_prepend (NULL
, mv
);
26 for (l
= list
; l
; l
= l
->next
) {
27 MonoMethodVar
*v1
= (MonoMethodVar
*)l
->data
;
30 if (mv
->spill_costs
>= v1
->spill_costs
) {
31 list
= g_list_insert_before (list
, l
, mv
);
34 } else if (sort_type
== 1) {
35 if (mv
->range
.last_use
.abs_pos
<= v1
->range
.last_use
.abs_pos
) {
36 list
= g_list_insert_before (list
, l
, mv
);
40 if (mv
->range
.first_use
.abs_pos
<= v1
->range
.first_use
.abs_pos
) {
41 list
= g_list_insert_before (list
, l
, mv
);
47 list
= g_list_append (list
, mv
);
53 compare_by_first_use_func (gconstpointer a
, gconstpointer b
)
55 MonoMethodVar
*v1
= (MonoMethodVar
*)a
;
56 MonoMethodVar
*v2
= (MonoMethodVar
*)b
;
58 return v1
->range
.first_use
.abs_pos
- v2
->range
.first_use
.abs_pos
;
62 mono_varlist_sort (MonoCompile
*cfg
, GList
*list
, int sort_type
)
65 return g_list_sort (list
, compare_by_first_use_func
);
67 g_assert_not_reached ();
72 // #define DEBUG_LSCAN
75 mono_linear_scan (MonoCompile
*cfg
, GList
*vars
, GList
*regs
, regmask_t
*used_mask
)
77 GList
*l
, *a
, *active
= NULL
;
78 MonoMethodVar
*vmv
, *amv
;
79 int max_regs
, n_regvars
;
80 int gains
[sizeof (regmask_t
) * 8];
81 regmask_t used_regs
= 0;
84 if (!cfg
->disable_reuse_registers
&& vars
&& (((MonoMethodVar
*)vars
->data
)->interval
!= NULL
)) {
85 mono_linear_scan2 (cfg
, vars
, regs
, used_mask
);
94 printf ("Linears scan for %s\n", mono_method_full_name (cfg
->method
, TRUE
));
98 for (l
= vars
; l
; l
= l
->next
) {
100 printf ("VAR %d %08x %08x C%d\n", vmv
->idx
, vmv
->range
.first_use
.abs_pos
,
101 vmv
->range
.last_use
.abs_pos
, vmv
->spill_costs
);
104 max_regs
= g_list_length (regs
);
106 for (l
= regs
; l
; l
= l
->next
) {
107 int regnum
= GPOINTER_TO_INT (l
->data
);
108 g_assert (regnum
< G_N_ELEMENTS (gains
));
113 for (l
= vars
; l
; l
= l
->next
) {
114 vmv
= (MonoMethodVar
*)l
->data
;
117 printf ("START %2d %08x %08x\n", vmv
->idx
, vmv
->range
.first_use
.abs_pos
,
118 vmv
->range
.last_use
.abs_pos
);
120 /* expire old intervals in active */
121 if (!cfg
->disable_reuse_registers
) {
123 amv
= (MonoMethodVar
*)active
->data
;
125 if (amv
->range
.last_use
.abs_pos
> vmv
->range
.first_use
.abs_pos
)
129 printf ("EXPIR %2d %08x %08x C%d R%d\n", amv
->idx
, amv
->range
.first_use
.abs_pos
,
130 amv
->range
.last_use
.abs_pos
, amv
->spill_costs
, amv
->reg
);
132 active
= g_list_delete_link (active
, active
);
133 regs
= g_list_prepend (regs
, GINT_TO_POINTER (amv
->reg
));
134 gains
[amv
->reg
] += amv
->spill_costs
;
138 if (active
&& g_list_length (active
) == max_regs
) {
141 a
= g_list_nth (active
, max_regs
- 1);
142 amv
= (MonoMethodVar
*)a
->data
;
144 if ((cost_driven
&& amv
->spill_costs
< vmv
->spill_costs
) ||
145 (!cost_driven
&& amv
->range
.last_use
.abs_pos
> vmv
->range
.last_use
.abs_pos
)) {
148 active
= g_list_delete_link (active
, a
);
151 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, 2);
153 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, 1);
156 printf ("SPILL0 %2d %08x %08x C%d\n", amv
->idx
,
157 amv
->range
.first_use
.abs_pos
, amv
->range
.last_use
.abs_pos
,
162 printf ("SPILL1 %2d %08x %08x C%d\n", vmv
->idx
,
163 vmv
->range
.first_use
.abs_pos
, vmv
->range
.last_use
.abs_pos
,
169 /* assign register */
173 vmv
->reg
= GPOINTER_TO_INT (regs
->data
);
175 used_regs
|= 1LL << vmv
->reg
;
177 regs
= g_list_delete_link (regs
, regs
);
180 printf ("ADD %2d %08x %08x C%d R%d\n", vmv
->idx
,
181 vmv
->range
.first_use
.abs_pos
, vmv
->range
.last_use
.abs_pos
,
182 vmv
->spill_costs
, vmv
->reg
);
184 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, TRUE
);
189 for (a
= active
; a
; a
= a
->next
) {
190 amv
= (MonoMethodVar
*)a
->data
;
191 printf ("ACT %2d %08x %08x C%d R%d\n", amv
->idx
, amv
->range
.first_use
.abs_pos
,
192 amv
->range
.last_use
.abs_pos
, amv
->spill_costs
, amv
->reg
);
198 for (a
= active
; a
; a
= a
->next
) {
199 amv
= (MonoMethodVar
*)a
->data
;
200 gains
[amv
->reg
] += amv
->spill_costs
;
204 for (l
= vars
; l
; l
= l
->next
) {
205 vmv
= (MonoMethodVar
*)l
->data
;
208 if ((gains
[vmv
->reg
] > mono_arch_regalloc_cost (cfg
, vmv
)) && (cfg
->varinfo
[vmv
->idx
]->opcode
!= OP_REGVAR
)) {
209 if (cfg
->verbose_level
> 2) {
210 printf ("ALLOCATED R%d(%d) TO HREG %d COST %d\n", cfg
->varinfo
[vmv
->idx
]->dreg
, vmv
->idx
, vmv
->reg
, vmv
->spill_costs
);
212 cfg
->varinfo
[vmv
->idx
]->opcode
= OP_REGVAR
;
213 cfg
->varinfo
[vmv
->idx
]->dreg
= vmv
->reg
;
216 if (cfg
->verbose_level
> 2)
217 printf ("COSTLY: R%d C%d C%d %s\n", vmv
->idx
, vmv
->spill_costs
, mono_arch_regalloc_cost (cfg
, vmv
), mono_arch_regname (vmv
->reg
));
222 if (vmv
->reg
== -1) {
223 if (cfg
->verbose_level
> 2)
224 printf ("NOT REGVAR: %d\n", vmv
->idx
);
228 cfg
->stat_n_regvars
= n_regvars
;
230 /* Compute used regs */
232 for (l
= vars
; l
; l
= l
->next
) {
233 vmv
= (MonoMethodVar
*)l
->data
;
236 used_regs
|= 1LL << vmv
->reg
;
239 *used_mask
|= used_regs
;
242 if (cfg
->verbose_level
> 2)
243 printf ("EXIT: final used mask: %08x\n", *used_mask
);
247 g_list_free (active
);
252 compare_by_interval_start_pos_func (gconstpointer a
, gconstpointer b
)
254 MonoMethodVar
*v1
= (MonoMethodVar
*)a
;
255 MonoMethodVar
*v2
= (MonoMethodVar
*)b
;
259 else if (v1
->interval
->range
&& v2
->interval
->range
)
260 return v1
->interval
->range
->from
- v2
->interval
->range
->from
;
261 else if (v1
->interval
->range
)
268 #define LSCAN_DEBUG(a) do { a; } while (0)
270 #define LSCAN_DEBUG(a)
273 /* FIXME: This is x86 only */
274 static inline guint32
275 regalloc_cost (MonoCompile
*cfg
, MonoMethodVar
*vmv
)
277 MonoInst
*ins
= cfg
->varinfo
[vmv
->idx
];
279 /* Load if it is an argument */
280 return (ins
->opcode
== OP_ARG
) ? 1 : 0;
284 mono_linear_scan2 (MonoCompile
*cfg
, GList
*vars
, GList
*regs
, regmask_t
*used_mask
)
286 GList
*unhandled
, *active
, *inactive
, *l
;
288 gint32 free_pos
[sizeof (regmask_t
) * 8];
289 gint32 gains
[sizeof (regmask_t
) * 8];
290 regmask_t used_regs
= 0;
291 int n_regs
, n_regvars
, i
;
293 for (l
= vars
; l
; l
= l
->next
) {
294 vmv
= (MonoMethodVar
*)l
->data
;
295 LSCAN_DEBUG (printf ("VAR R%d %08x %08x C%d\n", cfg
->varinfo
[vmv
->idx
]->dreg
, vmv
->range
.first_use
.abs_pos
,
296 vmv
->range
.last_use
.abs_pos
, vmv
->spill_costs
));
299 LSCAN_DEBUG (printf ("Linear Scan 2 for %s:\n", mono_method_full_name (cfg
->method
, TRUE
)));
301 n_regs
= g_list_length (regs
);
302 memset (gains
, 0, n_regs
* sizeof (gint32
));
303 unhandled
= g_list_sort (g_list_copy (vars
), compare_by_interval_start_pos_func
);
308 MonoMethodVar
*current
= (MonoMethodVar
*)unhandled
->data
;
309 int pos
, reg
, max_free_pos
;
312 unhandled
= g_list_delete_link (unhandled
, unhandled
);
314 LSCAN_DEBUG (printf ("Processing R%d: ", cfg
->varinfo
[current
->idx
]->dreg
));
315 LSCAN_DEBUG (mono_linterval_print (current
->interval
));
316 LSCAN_DEBUG (printf ("\n"));
318 if (!current
->interval
->range
)
321 pos
= current
->interval
->range
->from
;
323 /* Check for intervals in active which expired or inactive */
325 /* FIXME: Optimize this */
328 for (l
= active
; l
!= NULL
; l
= l
->next
) {
329 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
331 if (v
->interval
->last_range
->to
< pos
) {
332 active
= g_list_delete_link (active
, l
);
333 LSCAN_DEBUG (printf ("Interval R%d has expired\n", cfg
->varinfo
[v
->idx
]->dreg
));
337 else if (!mono_linterval_covers (v
->interval
, pos
)) {
338 inactive
= g_list_append (inactive
, v
);
339 active
= g_list_delete_link (active
, l
);
340 LSCAN_DEBUG (printf ("Interval R%d became inactive\n", cfg
->varinfo
[v
->idx
]->dreg
));
347 /* Check for intervals in inactive which expired or active */
349 /* FIXME: Optimize this */
352 for (l
= inactive
; l
!= NULL
; l
= l
->next
) {
353 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
355 if (v
->interval
->last_range
->to
< pos
) {
356 inactive
= g_list_delete_link (inactive
, l
);
357 LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", cfg
->varinfo
[v
->idx
]->dreg
));
361 else if (mono_linterval_covers (v
->interval
, pos
)) {
362 active
= g_list_append (active
, v
);
363 inactive
= g_list_delete_link (inactive
, l
);
364 LSCAN_DEBUG (printf ("\tInterval R%d became active\n", cfg
->varinfo
[v
->idx
]->dreg
));
371 /* Find a register for the current interval */
372 for (i
= 0; i
< n_regs
; ++i
)
373 free_pos
[i
] = ((gint32
)0x7fffffff);
375 for (l
= active
; l
!= NULL
; l
= l
->next
) {
376 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
379 free_pos
[v
->reg
] = 0;
380 LSCAN_DEBUG (printf ("\threg %d is busy (cost %d)\n", v
->reg
, v
->spill_costs
));
384 for (l
= inactive
; l
!= NULL
; l
= l
->next
) {
385 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
386 gint32 intersect_pos
;
389 intersect_pos
= mono_linterval_get_intersect_pos (current
->interval
, v
->interval
);
390 if (intersect_pos
!= -1) {
391 free_pos
[v
->reg
] = intersect_pos
;
392 LSCAN_DEBUG (printf ("\threg %d becomes free at %d\n", v
->reg
, intersect_pos
));
399 for (i
= 0; i
< n_regs
; ++i
)
400 if (free_pos
[i
] > max_free_pos
) {
402 max_free_pos
= free_pos
[i
];
405 g_assert (reg
!= -1);
407 if (free_pos
[reg
] >= current
->interval
->last_range
->to
) {
408 /* Register available for whole interval */
410 LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg
, cfg
->varinfo
[current
->idx
]->dreg
));
412 active
= g_list_append (active
, current
);
413 gains
[current
->reg
] += current
->spill_costs
;
417 * free_pos [reg] > 0 means there is a register available for parts
418 * of the interval, so splitting it is possible. This is not yet
419 * supported, so we spill in this case too.
422 /* Spill an interval */
424 /* FIXME: Optimize the selection of the interval */
427 GList
*min_spill_pos
;
430 * This favors registers with big spill costs, thus larger liveness ranges,
431 * thus actually leading to worse code size.
433 guint32 min_spill_value
= G_MAXINT32
;
435 for (l
= active
; l
!= NULL
; l
= l
->next
) {
436 vmv
= (MonoMethodVar
*)l
->data
;
438 if (vmv
->spill_costs
< min_spill_value
) {
440 min_spill_value
= vmv
->spill_costs
;
444 /* Spill either the first active or the current interval */
445 min_spill_pos
= active
;
447 vmv
= (MonoMethodVar
*)min_spill_pos
->data
;
448 if (vmv
->spill_costs
< current
->spill_costs
) {
449 // if (vmv->interval->last_range->to < current->interval->last_range->to) {
450 gains
[vmv
->reg
] -= vmv
->spill_costs
;
452 LSCAN_DEBUG (printf ("\tSpilled R%d\n", cfg
->varinfo
[vmv
->idx
]->dreg
));
453 active
= g_list_delete_link (active
, min_spill_pos
);
456 LSCAN_DEBUG (printf ("\tSpilled current (cost %d)\n", current
->spill_costs
));
459 LSCAN_DEBUG (printf ("\tSpilled current\n"));
463 /* Decrease the gains by the cost of saving+restoring the register */
464 for (i
= 0; i
< n_regs
; ++i
) {
466 /* FIXME: This is x86 only */
467 gains
[i
] -= cfg
->method
->save_lmf
? 1 : 2;
473 /* Do the actual register assignment */
475 for (l
= vars
; l
; l
= l
->next
) {
476 vmv
= (MonoMethodVar
*)l
->data
;
479 int reg_index
= vmv
->reg
;
481 /* During allocation, vmv->reg is an index into the regs list */
482 vmv
->reg
= GPOINTER_TO_INT (g_list_nth_data (regs
, vmv
->reg
));
484 if ((gains
[reg_index
] > regalloc_cost (cfg
, vmv
)) && (cfg
->varinfo
[vmv
->idx
]->opcode
!= OP_REGVAR
)) {
485 if (cfg
->verbose_level
> 2)
486 printf ("REGVAR R%d G%d C%d %s\n", cfg
->varinfo
[vmv
->idx
]->dreg
, gains
[reg_index
], regalloc_cost (cfg
, vmv
), mono_arch_regname (vmv
->reg
));
487 cfg
->varinfo
[vmv
->idx
]->opcode
= OP_REGVAR
;
488 cfg
->varinfo
[vmv
->idx
]->dreg
= vmv
->reg
;
492 if (cfg
->verbose_level
> 2)
493 printf ("COSTLY: %s R%d G%d C%d %s\n", mono_method_full_name (cfg
->method
, TRUE
), cfg
->varinfo
[vmv
->idx
]->dreg
, gains
[reg_index
], regalloc_cost (cfg
, vmv
), mono_arch_regname (vmv
->reg
));
499 cfg
->stat_n_regvars
= n_regvars
;
501 /* Compute used regs */
503 for (l
= vars
; l
; l
= l
->next
) {
504 vmv
= (MonoMethodVar
*)l
->data
;
507 used_regs
|= 1LL << vmv
->reg
;
510 *used_mask
|= used_regs
;
512 g_list_free (active
);
513 g_list_free (inactive
);
516 #else /* !DISABLE_JIT */
518 MONO_EMPTY_SOURCE_FILE (linear_scan
);
520 #endif /* !DISABLE_JIT */