2 * liveness.c: liveness analysis
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2002 Ximian, Inc.
11 #include <mono/metadata/debug-helpers.h>
13 static void mono_linear_scan2 (MonoCompile
*cfg
, GList
*vars
, GList
*regs
, regmask_t
*used_mask
);
16 mono_varlist_insert_sorted (MonoCompile
*cfg
, GList
*list
, MonoMethodVar
*mv
, int sort_type
)
21 return g_list_prepend (NULL
, mv
);
23 for (l
= list
; l
; l
= l
->next
) {
24 MonoMethodVar
*v1
= l
->data
;
27 if (mv
->spill_costs
>= v1
->spill_costs
) {
28 list
= g_list_insert_before (list
, l
, mv
);
31 } else if (sort_type
== 1) {
32 if (mv
->range
.last_use
.abs_pos
<= v1
->range
.last_use
.abs_pos
) {
33 list
= g_list_insert_before (list
, l
, mv
);
37 if (mv
->range
.first_use
.abs_pos
<= v1
->range
.first_use
.abs_pos
) {
38 list
= g_list_insert_before (list
, l
, mv
);
44 list
= g_list_append (list
, mv
);
50 compare_by_first_use_func (gconstpointer a
, gconstpointer b
)
52 MonoMethodVar
*v1
= (MonoMethodVar
*)a
;
53 MonoMethodVar
*v2
= (MonoMethodVar
*)b
;
55 return v1
->range
.first_use
.abs_pos
- v2
->range
.first_use
.abs_pos
;
59 mono_varlist_sort (MonoCompile
*cfg
, GList
*list
, int sort_type
)
62 return g_list_sort (list
, compare_by_first_use_func
);
64 g_assert_not_reached ();
69 // #define DEBUG_LSCAN
72 mono_linear_scan (MonoCompile
*cfg
, GList
*vars
, GList
*regs
, regmask_t
*used_mask
)
74 GList
*l
, *a
, *active
= NULL
;
75 MonoMethodVar
*vmv
, *amv
;
76 int max_regs
, n_regvars
;
77 int gains
[sizeof (regmask_t
) * 8];
78 regmask_t used_regs
= 0;
81 if (vars
&& (((MonoMethodVar
*)vars
->data
)->interval
!= NULL
)) {
82 mono_linear_scan2 (cfg
, vars
, regs
, used_mask
);
89 printf ("Linears scan for %s\n", mono_method_full_name (cfg
->method
, TRUE
));
93 for (l
= vars
; l
; l
= l
->next
) {
95 printf ("VAR %d %08x %08x C%d\n", vmv
->idx
, vmv
->range
.first_use
.abs_pos
,
96 vmv
->range
.last_use
.abs_pos
, vmv
->spill_costs
);
99 max_regs
= g_list_length (regs
);
101 for (l
= regs
; l
; l
= l
->next
) {
102 int regnum
= GPOINTER_TO_INT (l
->data
);
103 g_assert (regnum
< G_N_ELEMENTS (gains
));
108 for (l
= vars
; l
; l
= l
->next
) {
112 printf ("START %2d %08x %08x\n", vmv
->idx
, vmv
->range
.first_use
.abs_pos
,
113 vmv
->range
.last_use
.abs_pos
);
115 /* expire old intervals in active */
116 if (!cfg
->disable_reuse_registers
) {
118 amv
= (MonoMethodVar
*)active
->data
;
120 if (amv
->range
.last_use
.abs_pos
> vmv
->range
.first_use
.abs_pos
)
124 printf ("EXPIR %2d %08x %08x C%d R%d\n", amv
->idx
, amv
->range
.first_use
.abs_pos
,
125 amv
->range
.last_use
.abs_pos
, amv
->spill_costs
, amv
->reg
);
127 active
= g_list_delete_link (active
, active
);
128 regs
= g_list_prepend (regs
, GINT_TO_POINTER (amv
->reg
));
129 gains
[amv
->reg
] += amv
->spill_costs
;
133 if (active
&& g_list_length (active
) == max_regs
) {
136 a
= g_list_nth (active
, max_regs
- 1);
137 amv
= (MonoMethodVar
*)a
->data
;
139 if ((cost_driven
&& amv
->spill_costs
< vmv
->spill_costs
) ||
140 (!cost_driven
&& amv
->range
.last_use
.abs_pos
> vmv
->range
.last_use
.abs_pos
)) {
143 active
= g_list_delete_link (active
, a
);
146 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, 2);
148 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, 1);
151 printf ("SPILL0 %2d %08x %08x C%d\n", amv
->idx
,
152 amv
->range
.first_use
.abs_pos
, amv
->range
.last_use
.abs_pos
,
157 printf ("SPILL1 %2d %08x %08x C%d\n", vmv
->idx
,
158 vmv
->range
.first_use
.abs_pos
, vmv
->range
.last_use
.abs_pos
,
164 /* assign register */
168 vmv
->reg
= GPOINTER_TO_INT (regs
->data
);
170 used_regs
|= 1LL << vmv
->reg
;
172 regs
= g_list_delete_link (regs
, regs
);
175 printf ("ADD %2d %08x %08x C%d R%d\n", vmv
->idx
,
176 vmv
->range
.first_use
.abs_pos
, vmv
->range
.last_use
.abs_pos
,
177 vmv
->spill_costs
, vmv
->reg
);
179 active
= mono_varlist_insert_sorted (cfg
, active
, vmv
, TRUE
);
184 for (a
= active
; a
; a
= a
->next
) {
185 amv
= (MonoMethodVar
*)a
->data
;
186 printf ("ACT %2d %08x %08x C%d R%d\n", amv
->idx
, amv
->range
.first_use
.abs_pos
,
187 amv
->range
.last_use
.abs_pos
, amv
->spill_costs
, amv
->reg
);
193 for (a
= active
; a
; a
= a
->next
) {
194 amv
= (MonoMethodVar
*)a
->data
;
195 gains
[amv
->reg
] += amv
->spill_costs
;
199 for (l
= vars
; l
; l
= l
->next
) {
203 if ((gains
[vmv
->reg
] > mono_arch_regalloc_cost (cfg
, vmv
)) && (cfg
->varinfo
[vmv
->idx
]->opcode
!= OP_REGVAR
)) {
204 if (cfg
->verbose_level
> 2) {
206 printf ("ALLOCATED R%d(%d) TO HREG %d COST %d\n", cfg
->varinfo
[vmv
->idx
]->dreg
, vmv
->idx
, vmv
->reg
, vmv
->spill_costs
);
208 printf ("REGVAR %d C%d R%d\n", vmv
->idx
, vmv
->spill_costs
, vmv
->reg
);
210 cfg
->varinfo
[vmv
->idx
]->opcode
= OP_REGVAR
;
211 cfg
->varinfo
[vmv
->idx
]->dreg
= vmv
->reg
;
214 if (cfg
->verbose_level
> 2)
215 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
));
220 if (vmv
->reg
== -1) {
221 if (cfg
->verbose_level
> 2)
222 printf ("NOT REGVAR: %d\n", vmv
->idx
);
226 mono_jit_stats
.regvars
+= n_regvars
;
228 /* Compute used regs */
230 for (l
= vars
; l
; l
= l
->next
) {
234 used_regs
|= 1LL << vmv
->reg
;
237 *used_mask
|= used_regs
;
240 if (cfg
->verbose_level
> 2)
241 printf ("EXIT: final used mask: %08x\n", *used_mask
);
245 g_list_free (active
);
250 compare_by_interval_start_pos_func (gconstpointer a
, gconstpointer b
)
252 MonoMethodVar
*v1
= (MonoMethodVar
*)a
;
253 MonoMethodVar
*v2
= (MonoMethodVar
*)b
;
257 else if (v1
->interval
->range
&& v2
->interval
->range
)
258 return v1
->interval
->range
->from
- v2
->interval
->range
->from
;
259 else if (v1
->interval
->range
)
266 #define LSCAN_DEBUG(a) do { a; } while (0)
268 #define LSCAN_DEBUG(a)
271 /* FIXME: This is x86 only */
272 static inline guint32
273 regalloc_cost (MonoCompile
*cfg
, MonoMethodVar
*vmv
)
275 MonoInst
*ins
= cfg
->varinfo
[vmv
->idx
];
277 /* Load if it is an argument */
278 return (ins
->opcode
== OP_ARG
) ? 1 : 0;
282 mono_linear_scan2 (MonoCompile
*cfg
, GList
*vars
, GList
*regs
, regmask_t
*used_mask
)
284 GList
*unhandled
, *active
, *inactive
, *l
;
286 gint32 free_pos
[sizeof (regmask_t
) * 8];
287 gint32 gains
[sizeof (regmask_t
) * 8];
288 regmask_t used_regs
= 0;
289 int n_regs
, n_regvars
, i
;
291 for (l
= vars
; l
; l
= l
->next
) {
293 LSCAN_DEBUG (printf ("VAR R%d %08x %08x C%d\n", cfg
->varinfo
[vmv
->idx
]->dreg
, vmv
->range
.first_use
.abs_pos
,
294 vmv
->range
.last_use
.abs_pos
, vmv
->spill_costs
));
297 LSCAN_DEBUG (printf ("Linear Scan 2 for %s:\n", mono_method_full_name (cfg
->method
, TRUE
)));
299 n_regs
= g_list_length (regs
);
300 memset (gains
, 0, n_regs
* sizeof (gint32
));
301 unhandled
= g_list_sort (g_list_copy (vars
), compare_by_interval_start_pos_func
);
306 MonoMethodVar
*current
= unhandled
->data
;
307 int pos
, reg
, max_free_pos
;
310 unhandled
= g_list_delete_link (unhandled
, unhandled
);
312 LSCAN_DEBUG (printf ("Processing R%d: ", cfg
->varinfo
[current
->idx
]->dreg
));
313 LSCAN_DEBUG (mono_linterval_print (current
->interval
));
314 LSCAN_DEBUG (printf ("\n"));
316 if (!current
->interval
->range
)
319 pos
= current
->interval
->range
->from
;
321 /* Check for intervals in active which expired or inactive */
323 /* FIXME: Optimize this */
326 for (l
= active
; l
!= NULL
; l
= l
->next
) {
327 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
329 if (v
->interval
->last_range
->to
< pos
) {
330 active
= g_list_delete_link (active
, l
);
331 LSCAN_DEBUG (printf ("Interval R%d has expired\n", cfg
->varinfo
[v
->idx
]->dreg
));
335 else if (!mono_linterval_covers (v
->interval
, pos
)) {
336 inactive
= g_list_append (inactive
, v
);
337 active
= g_list_delete_link (active
, l
);
338 LSCAN_DEBUG (printf ("Interval R%d became inactive\n", cfg
->varinfo
[v
->idx
]->dreg
));
345 /* Check for intervals in inactive which expired or active */
347 /* FIXME: Optimize this */
350 for (l
= inactive
; l
!= NULL
; l
= l
->next
) {
351 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
353 if (v
->interval
->last_range
->to
< pos
) {
354 inactive
= g_list_delete_link (inactive
, l
);
355 LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", cfg
->varinfo
[v
->idx
]->dreg
));
359 else if (mono_linterval_covers (v
->interval
, pos
)) {
360 active
= g_list_append (active
, v
);
361 inactive
= g_list_delete_link (inactive
, l
);
362 LSCAN_DEBUG (printf ("\tInterval R%d became active\n", cfg
->varinfo
[v
->idx
]->dreg
));
369 /* Find a register for the current interval */
370 for (i
= 0; i
< n_regs
; ++i
)
371 free_pos
[i
] = ((gint32
)0x7fffffff);
373 for (l
= active
; l
!= NULL
; l
= l
->next
) {
374 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
377 free_pos
[v
->reg
] = 0;
378 LSCAN_DEBUG (printf ("\threg %d is busy (cost %d)\n", v
->reg
, v
->spill_costs
));
382 for (l
= inactive
; l
!= NULL
; l
= l
->next
) {
383 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
384 gint32 intersect_pos
;
387 intersect_pos
= mono_linterval_get_intersect_pos (current
->interval
, v
->interval
);
388 if (intersect_pos
!= -1) {
389 free_pos
[v
->reg
] = intersect_pos
;
390 LSCAN_DEBUG (printf ("\threg %d becomes free at %d\n", v
->reg
, intersect_pos
));
397 for (i
= 0; i
< n_regs
; ++i
)
398 if (free_pos
[i
] > max_free_pos
) {
400 max_free_pos
= free_pos
[i
];
403 g_assert (reg
!= -1);
405 if (free_pos
[reg
] >= current
->interval
->last_range
->to
) {
406 /* Register available for whole interval */
408 LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg
, cfg
->varinfo
[current
->idx
]->dreg
));
410 active
= g_list_append (active
, current
);
411 gains
[current
->reg
] += current
->spill_costs
;
415 * free_pos [reg] > 0 means there is a register available for parts
416 * of the interval, so splitting it is possible. This is not yet
417 * supported, so we spill in this case too.
420 /* Spill an interval */
422 /* FIXME: Optimize the selection of the interval */
425 GList
*min_spill_pos
;
428 * This favors registers with big spill costs, thus larger liveness ranges,
429 * thus actually leading to worse code size.
431 guint32 min_spill_value
= G_MAXINT32
;
433 for (l
= active
; l
!= NULL
; l
= l
->next
) {
434 vmv
= (MonoMethodVar
*)l
->data
;
436 if (vmv
->spill_costs
< min_spill_value
) {
438 min_spill_value
= vmv
->spill_costs
;
442 /* Spill either the first active or the current interval */
443 min_spill_pos
= active
;
445 vmv
= (MonoMethodVar
*)min_spill_pos
->data
;
446 if (vmv
->spill_costs
< current
->spill_costs
) {
447 // if (vmv->interval->last_range->to < current->interval->last_range->to) {
448 gains
[vmv
->reg
] -= vmv
->spill_costs
;
450 LSCAN_DEBUG (printf ("\tSpilled R%d\n", cfg
->varinfo
[vmv
->idx
]->dreg
));
451 active
= g_list_delete_link (active
, min_spill_pos
);
454 LSCAN_DEBUG (printf ("\tSpilled current (cost %d)\n", current
->spill_costs
));
457 LSCAN_DEBUG (printf ("\tSpilled current\n"));
461 /* Decrease the gains by the cost of saving+restoring the register */
462 for (i
= 0; i
< n_regs
; ++i
) {
464 /* FIXME: This is x86 only */
465 gains
[i
] -= cfg
->method
->save_lmf
? 1 : 2;
471 /* Do the actual register assignment */
473 for (l
= vars
; l
; l
= l
->next
) {
477 int reg_index
= vmv
->reg
;
479 /* During allocation, vmv->reg is an index into the regs list */
480 vmv
->reg
= GPOINTER_TO_INT (g_list_nth_data (regs
, vmv
->reg
));
482 if ((gains
[reg_index
] > regalloc_cost (cfg
, vmv
)) && (cfg
->varinfo
[vmv
->idx
]->opcode
!= OP_REGVAR
)) {
483 if (cfg
->verbose_level
> 2)
484 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
));
485 cfg
->varinfo
[vmv
->idx
]->opcode
= OP_REGVAR
;
486 cfg
->varinfo
[vmv
->idx
]->dreg
= vmv
->reg
;
490 if (cfg
->verbose_level
> 2)
491 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
));
497 mono_jit_stats
.regvars
+= n_regvars
;
499 /* Compute used regs */
501 for (l
= vars
; l
; l
= l
->next
) {
505 used_regs
|= 1LL << vmv
->reg
;
508 *used_mask
|= used_regs
;
510 g_list_free (active
);
511 g_list_free (inactive
);