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) {
205 printf ("ALLOCATED R%d(%d) TO HREG %d COST %d\n", cfg
->varinfo
[vmv
->idx
]->dreg
, vmv
->idx
, vmv
->reg
, vmv
->spill_costs
);
207 cfg
->varinfo
[vmv
->idx
]->opcode
= OP_REGVAR
;
208 cfg
->varinfo
[vmv
->idx
]->dreg
= vmv
->reg
;
211 if (cfg
->verbose_level
> 2)
212 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
));
217 if (vmv
->reg
== -1) {
218 if (cfg
->verbose_level
> 2)
219 printf ("NOT REGVAR: %d\n", vmv
->idx
);
223 mono_jit_stats
.regvars
+= n_regvars
;
225 /* Compute used regs */
227 for (l
= vars
; l
; l
= l
->next
) {
231 used_regs
|= 1LL << vmv
->reg
;
234 *used_mask
|= used_regs
;
237 if (cfg
->verbose_level
> 2)
238 printf ("EXIT: final used mask: %08x\n", *used_mask
);
242 g_list_free (active
);
247 compare_by_interval_start_pos_func (gconstpointer a
, gconstpointer b
)
249 MonoMethodVar
*v1
= (MonoMethodVar
*)a
;
250 MonoMethodVar
*v2
= (MonoMethodVar
*)b
;
254 else if (v1
->interval
->range
&& v2
->interval
->range
)
255 return v1
->interval
->range
->from
- v2
->interval
->range
->from
;
256 else if (v1
->interval
->range
)
263 #define LSCAN_DEBUG(a) do { a; } while (0)
265 #define LSCAN_DEBUG(a)
268 /* FIXME: This is x86 only */
269 static inline guint32
270 regalloc_cost (MonoCompile
*cfg
, MonoMethodVar
*vmv
)
272 MonoInst
*ins
= cfg
->varinfo
[vmv
->idx
];
274 /* Load if it is an argument */
275 return (ins
->opcode
== OP_ARG
) ? 1 : 0;
279 mono_linear_scan2 (MonoCompile
*cfg
, GList
*vars
, GList
*regs
, regmask_t
*used_mask
)
281 GList
*unhandled
, *active
, *inactive
, *l
;
283 gint32 free_pos
[sizeof (regmask_t
) * 8];
284 gint32 gains
[sizeof (regmask_t
) * 8];
285 regmask_t used_regs
= 0;
286 int n_regs
, n_regvars
, i
;
288 for (l
= vars
; l
; l
= l
->next
) {
290 LSCAN_DEBUG (printf ("VAR R%d %08x %08x C%d\n", cfg
->varinfo
[vmv
->idx
]->dreg
, vmv
->range
.first_use
.abs_pos
,
291 vmv
->range
.last_use
.abs_pos
, vmv
->spill_costs
));
294 LSCAN_DEBUG (printf ("Linear Scan 2 for %s:\n", mono_method_full_name (cfg
->method
, TRUE
)));
296 n_regs
= g_list_length (regs
);
297 memset (gains
, 0, n_regs
* sizeof (gint32
));
298 unhandled
= g_list_sort (g_list_copy (vars
), compare_by_interval_start_pos_func
);
303 MonoMethodVar
*current
= unhandled
->data
;
304 int pos
, reg
, max_free_pos
;
307 unhandled
= g_list_delete_link (unhandled
, unhandled
);
309 LSCAN_DEBUG (printf ("Processing R%d: ", cfg
->varinfo
[current
->idx
]->dreg
));
310 LSCAN_DEBUG (mono_linterval_print (current
->interval
));
311 LSCAN_DEBUG (printf ("\n"));
313 if (!current
->interval
->range
)
316 pos
= current
->interval
->range
->from
;
318 /* Check for intervals in active which expired or inactive */
320 /* FIXME: Optimize this */
323 for (l
= active
; l
!= NULL
; l
= l
->next
) {
324 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
326 if (v
->interval
->last_range
->to
< pos
) {
327 active
= g_list_delete_link (active
, l
);
328 LSCAN_DEBUG (printf ("Interval R%d has expired\n", cfg
->varinfo
[v
->idx
]->dreg
));
332 else if (!mono_linterval_covers (v
->interval
, pos
)) {
333 inactive
= g_list_append (inactive
, v
);
334 active
= g_list_delete_link (active
, l
);
335 LSCAN_DEBUG (printf ("Interval R%d became inactive\n", cfg
->varinfo
[v
->idx
]->dreg
));
342 /* Check for intervals in inactive which expired or active */
344 /* FIXME: Optimize this */
347 for (l
= inactive
; l
!= NULL
; l
= l
->next
) {
348 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
350 if (v
->interval
->last_range
->to
< pos
) {
351 inactive
= g_list_delete_link (inactive
, l
);
352 LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", cfg
->varinfo
[v
->idx
]->dreg
));
356 else if (mono_linterval_covers (v
->interval
, pos
)) {
357 active
= g_list_append (active
, v
);
358 inactive
= g_list_delete_link (inactive
, l
);
359 LSCAN_DEBUG (printf ("\tInterval R%d became active\n", cfg
->varinfo
[v
->idx
]->dreg
));
366 /* Find a register for the current interval */
367 for (i
= 0; i
< n_regs
; ++i
)
368 free_pos
[i
] = ((gint32
)0x7fffffff);
370 for (l
= active
; l
!= NULL
; l
= l
->next
) {
371 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
374 free_pos
[v
->reg
] = 0;
375 LSCAN_DEBUG (printf ("\threg %d is busy (cost %d)\n", v
->reg
, v
->spill_costs
));
379 for (l
= inactive
; l
!= NULL
; l
= l
->next
) {
380 MonoMethodVar
*v
= (MonoMethodVar
*)l
->data
;
381 gint32 intersect_pos
;
384 intersect_pos
= mono_linterval_get_intersect_pos (current
->interval
, v
->interval
);
385 if (intersect_pos
!= -1) {
386 free_pos
[v
->reg
] = intersect_pos
;
387 LSCAN_DEBUG (printf ("\threg %d becomes free at %d\n", v
->reg
, intersect_pos
));
394 for (i
= 0; i
< n_regs
; ++i
)
395 if (free_pos
[i
] > max_free_pos
) {
397 max_free_pos
= free_pos
[i
];
400 g_assert (reg
!= -1);
402 if (free_pos
[reg
] >= current
->interval
->last_range
->to
) {
403 /* Register available for whole interval */
405 LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg
, cfg
->varinfo
[current
->idx
]->dreg
));
407 active
= g_list_append (active
, current
);
408 gains
[current
->reg
] += current
->spill_costs
;
412 * free_pos [reg] > 0 means there is a register available for parts
413 * of the interval, so splitting it is possible. This is not yet
414 * supported, so we spill in this case too.
417 /* Spill an interval */
419 /* FIXME: Optimize the selection of the interval */
422 GList
*min_spill_pos
;
425 * This favors registers with big spill costs, thus larger liveness ranges,
426 * thus actually leading to worse code size.
428 guint32 min_spill_value
= G_MAXINT32
;
430 for (l
= active
; l
!= NULL
; l
= l
->next
) {
431 vmv
= (MonoMethodVar
*)l
->data
;
433 if (vmv
->spill_costs
< min_spill_value
) {
435 min_spill_value
= vmv
->spill_costs
;
439 /* Spill either the first active or the current interval */
440 min_spill_pos
= active
;
442 vmv
= (MonoMethodVar
*)min_spill_pos
->data
;
443 if (vmv
->spill_costs
< current
->spill_costs
) {
444 // if (vmv->interval->last_range->to < current->interval->last_range->to) {
445 gains
[vmv
->reg
] -= vmv
->spill_costs
;
447 LSCAN_DEBUG (printf ("\tSpilled R%d\n", cfg
->varinfo
[vmv
->idx
]->dreg
));
448 active
= g_list_delete_link (active
, min_spill_pos
);
451 LSCAN_DEBUG (printf ("\tSpilled current (cost %d)\n", current
->spill_costs
));
454 LSCAN_DEBUG (printf ("\tSpilled current\n"));
458 /* Decrease the gains by the cost of saving+restoring the register */
459 for (i
= 0; i
< n_regs
; ++i
) {
461 /* FIXME: This is x86 only */
462 gains
[i
] -= cfg
->method
->save_lmf
? 1 : 2;
468 /* Do the actual register assignment */
470 for (l
= vars
; l
; l
= l
->next
) {
474 int reg_index
= vmv
->reg
;
476 /* During allocation, vmv->reg is an index into the regs list */
477 vmv
->reg
= GPOINTER_TO_INT (g_list_nth_data (regs
, vmv
->reg
));
479 if ((gains
[reg_index
] > regalloc_cost (cfg
, vmv
)) && (cfg
->varinfo
[vmv
->idx
]->opcode
!= OP_REGVAR
)) {
480 if (cfg
->verbose_level
> 2)
481 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
));
482 cfg
->varinfo
[vmv
->idx
]->opcode
= OP_REGVAR
;
483 cfg
->varinfo
[vmv
->idx
]->dreg
= vmv
->reg
;
487 if (cfg
->verbose_level
> 2)
488 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
));
494 mono_jit_stats
.regvars
+= n_regvars
;
496 /* Compute used regs */
498 for (l
= vars
; l
; l
= l
->next
) {
502 used_regs
|= 1LL << vmv
->reg
;
505 *used_mask
|= used_regs
;
507 g_list_free (active
);
508 g_list_free (inactive
);