1 /**
2 * \file
3 * liveness analysis
4 *
5 * Author:
6 * Dietmar Maurer (dietmar@ximian.com)
7 *
8 * (C) 2002 Ximian, Inc.
9 */
10
11 #include "mini.h"
12 #include <mono/metadata/debug-helpers.h>
13 #include <mono/utils/mono-compiler.h>
14
15 #ifndef DISABLE_JIT
16
17 static void mono_linear_scan2 (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask);
18
19 GList *
mono_varlist_insert_sorted(MonoCompile * cfg,GList * list,MonoMethodVar * mv,int sort_type)20 mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, int sort_type)
21 {
22 GList *l;
23
24 if (!list)
25 return g_list_prepend (NULL, mv);
26
27 for (l = list; l; l = l->next) {
28 MonoMethodVar *v1 = (MonoMethodVar *)l->data;
29
30 if (sort_type == 2) {
31 if (mv->spill_costs >= v1->spill_costs) {
32 list = g_list_insert_before (list, l, mv);
33 break;
34 }
35 } else if (sort_type == 1) {
36 if (mv->range.last_use.abs_pos <= v1->range.last_use.abs_pos) {
37 list = g_list_insert_before (list, l, mv);
38 break;
39 }
40 } else {
41 if (mv->range.first_use.abs_pos <= v1->range.first_use.abs_pos) {
42 list = g_list_insert_before (list, l, mv);
43 break;
44 }
45 }
46 }
47 if (!l)
48 list = g_list_append (list, mv);
49
50 return list;
51 }
52
53 static gint
compare_by_first_use_func(gconstpointer a,gconstpointer b)54 compare_by_first_use_func (gconstpointer a, gconstpointer b)
55 {
56 MonoMethodVar *v1 = (MonoMethodVar*)a;
57 MonoMethodVar *v2 = (MonoMethodVar*)b;
58
59 return v1->range.first_use.abs_pos - v2->range.first_use.abs_pos;
60 }
61
62 GList *
mono_varlist_sort(MonoCompile * cfg,GList * list,int sort_type)63 mono_varlist_sort (MonoCompile *cfg, GList *list, int sort_type)
64 {
65 if (sort_type == 0)
66 return g_list_sort (list, compare_by_first_use_func);
67 else
68 g_assert_not_reached ();
69
70 return NULL;
71 }
72
73 // #define DEBUG_LSCAN
74
75 void
mono_linear_scan(MonoCompile * cfg,GList * vars,GList * regs,regmask_t * used_mask)76 mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
77 {
78 GList *l, *a, *active = NULL;
79 MonoMethodVar *vmv, *amv;
80 int max_regs, n_regvars;
81 int gains [sizeof (regmask_t) * 8];
82 regmask_t used_regs = 0;
83 gboolean cost_driven;
84
85 if (!cfg->disable_reuse_registers && vars && (((MonoMethodVar*)vars->data)->interval != NULL)) {
86 mono_linear_scan2 (cfg, vars, regs, used_mask);
87 g_list_free (regs);
88 g_list_free (vars);
89 return;
90 }
91
92 cost_driven = TRUE;
93
94 #ifdef DEBUG_LSCAN
95 printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
96 #endif
97
98 #ifdef DEBUG_LSCAN
99 for (l = vars; l; l = l->next) {
100 vmv = l->data;
101 printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos,
102 vmv->range.last_use.abs_pos, vmv->spill_costs);
103 }
104 #endif
105 max_regs = g_list_length (regs);
106
107 for (l = regs; l; l = l->next) {
108 int regnum = GPOINTER_TO_INT (l->data);
109 g_assert (regnum < G_N_ELEMENTS (gains));
110 gains [regnum] = 0;
111 }
112
113 /* linear scan */
114 for (l = vars; l; l = l->next) {
115 vmv = (MonoMethodVar *)l->data;
116
117 #ifdef DEBUG_LSCAN
118 printf ("START %2d %08x %08x\n", vmv->idx, vmv->range.first_use.abs_pos,
119 vmv->range.last_use.abs_pos);
120 #endif
121 /* expire old intervals in active */
122 if (!cfg->disable_reuse_registers) {
123 while (active) {
124 amv = (MonoMethodVar *)active->data;
125
126 if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
127 break;
128
129 #ifdef DEBUG_LSCAN
130 printf ("EXPIR %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
131 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
132 #endif
133 active = g_list_delete_link (active, active);
134 regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
135 gains [amv->reg] += amv->spill_costs;
136 }
137 }
138
139 if (active && g_list_length (active) == max_regs) {
140 /* Spill */
141
142 a = g_list_nth (active, max_regs - 1);
143 amv = (MonoMethodVar *)a->data;
144
145 if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
146 (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
147 vmv->reg = amv->reg;
148 amv->reg = -1;
149 active = g_list_delete_link (active, a);
150
151 if (cost_driven)
152 active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
153 else
154 active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
155
156 #ifdef DEBUG_LSCAN
157 printf ("SPILL0 %2d %08x %08x C%d\n", amv->idx,
158 amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
159 amv->spill_costs);
160 #endif
161 } else {
162 #ifdef DEBUG_LSCAN
163 printf ("SPILL1 %2d %08x %08x C%d\n", vmv->idx,
164 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
165 vmv->spill_costs);
166 #endif
167 vmv->reg = -1;
168 }
169 } else {
170 /* assign register */
171
172 g_assert (regs);
173
174 vmv->reg = GPOINTER_TO_INT (regs->data);
175
176 used_regs |= 1LL << vmv->reg;
177
178 regs = g_list_delete_link (regs, regs);
179
180 #ifdef DEBUG_LSCAN
181 printf ("ADD %2d %08x %08x C%d R%d\n", vmv->idx,
182 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
183 vmv->spill_costs, vmv->reg);
184 #endif
185 active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
186 }
187
188
189 #ifdef DEBUG_LSCAN
190 for (a = active; a; a = a->next) {
191 amv = (MonoMethodVar *)a->data;
192 printf ("ACT %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
193 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
194 }
195 printf ("NEXT\n");
196 #endif
197 }
198
199 for (a = active; a; a = a->next) {
200 amv = (MonoMethodVar *)a->data;
201 gains [amv->reg] += amv->spill_costs;
202 }
203
204 n_regvars = 0;
205 for (l = vars; l; l = l->next) {
206 vmv = (MonoMethodVar *)l->data;
207
208 if (vmv->reg >= 0) {
209 if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
210 if (cfg->verbose_level > 2) {
211 printf ("ALLOCATED R%d(%d) TO HREG %d COST %d\n", cfg->varinfo [vmv->idx]->dreg, vmv->idx, vmv->reg, vmv->spill_costs);
212 }
213 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
214 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
215 n_regvars ++;
216 } else {
217 if (cfg->verbose_level > 2)
218 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));
219 vmv->reg = -1;
220 }
221 }
222
223 if (vmv->reg == -1) {
224 if (cfg->verbose_level > 2)
225 printf ("NOT REGVAR: %d\n", vmv->idx);
226 }
227 }
228
229 cfg->stat_n_regvars = n_regvars;
230
231 /* Compute used regs */
232 used_regs = 0;
233 for (l = vars; l; l = l->next) {
234 vmv = (MonoMethodVar *)l->data;
235
236 if (vmv->reg >= 0)
237 used_regs |= 1LL << vmv->reg;
238 }
239
240 *used_mask |= used_regs;
241
242 #ifdef DEBUG_LSCAN
243 if (cfg->verbose_level > 2)
244 printf ("EXIT: final used mask: %08x\n", *used_mask);
245 #endif
246
247 g_list_free (regs);
248 g_list_free (active);
249 g_list_free (vars);
250 }
251
252 static gint
compare_by_interval_start_pos_func(gconstpointer a,gconstpointer b)253 compare_by_interval_start_pos_func (gconstpointer a, gconstpointer b)
254 {
255 MonoMethodVar *v1 = (MonoMethodVar*)a;
256 MonoMethodVar *v2 = (MonoMethodVar*)b;
257
258 if (v1 == v2)
259 return 0;
260 else if (v1->interval->range && v2->interval->range)
261 return v1->interval->range->from - v2->interval->range->from;
262 else if (v1->interval->range)
263 return -1;
264 else
265 return 1;
266 }
267
268 #if 0
269 #define LSCAN_DEBUG(a) do { a; } while (0)
270 #else
271 #define LSCAN_DEBUG(a)
272 #endif
273
274 /* FIXME: This is x86 only */
275 static inline guint32
regalloc_cost(MonoCompile * cfg,MonoMethodVar * vmv)276 regalloc_cost (MonoCompile *cfg, MonoMethodVar *vmv)
277 {
278 MonoInst *ins = cfg->varinfo [vmv->idx];
279
280 /* Load if it is an argument */
281 return (ins->opcode == OP_ARG) ? 1 : 0;
282 }
283
284 void
mono_linear_scan2(MonoCompile * cfg,GList * vars,GList * regs,regmask_t * used_mask)285 mono_linear_scan2 (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
286 {
287 GList *unhandled, *active, *inactive, *l;
288 MonoMethodVar *vmv;
289 gint32 free_pos [sizeof (regmask_t) * 8];
290 gint32 gains [sizeof (regmask_t) * 8];
291 regmask_t used_regs = 0;
292 int n_regs, n_regvars, i;
293
294 for (l = vars; l; l = l->next) {
295 vmv = (MonoMethodVar *)l->data;
296 LSCAN_DEBUG (printf ("VAR R%d %08x %08x C%d\n", cfg->varinfo [vmv->idx]->dreg, vmv->range.first_use.abs_pos,
297 vmv->range.last_use.abs_pos, vmv->spill_costs));
298 }
299
300 LSCAN_DEBUG (printf ("Linear Scan 2 for %s:\n", mono_method_full_name (cfg->method, TRUE)));
301
302 n_regs = g_list_length (regs);
303 memset (gains, 0, n_regs * sizeof (gint32));
304 unhandled = g_list_sort (g_list_copy (vars), compare_by_interval_start_pos_func);
305 active = NULL;
306 inactive = NULL;
307
308 while (unhandled) {
309 MonoMethodVar *current = (MonoMethodVar *)unhandled->data;
310 int pos, reg, max_free_pos;
311 gboolean changed;
312
313 unhandled = g_list_delete_link (unhandled, unhandled);
314
315 LSCAN_DEBUG (printf ("Processing R%d: ", cfg->varinfo [current->idx]->dreg));
316 LSCAN_DEBUG (mono_linterval_print (current->interval));
317 LSCAN_DEBUG (printf ("\n"));
318
319 if (!current->interval->range)
320 continue;
321
322 pos = current->interval->range->from;
323
324 /* Check for intervals in active which expired or inactive */
325 changed = TRUE;
326 /* FIXME: Optimize this */
327 while (changed) {
328 changed = FALSE;
329 for (l = active; l != NULL; l = l->next) {
330 MonoMethodVar *v = (MonoMethodVar*)l->data;
331
332 if (v->interval->last_range->to < pos) {
333 active = g_list_delete_link (active, l);
334 LSCAN_DEBUG (printf ("Interval R%d has expired\n", cfg->varinfo [v->idx]->dreg));
335 changed = TRUE;
336 break;
337 }
338 else if (!mono_linterval_covers (v->interval, pos)) {
339 inactive = g_list_append (inactive, v);
340 active = g_list_delete_link (active, l);
341 LSCAN_DEBUG (printf ("Interval R%d became inactive\n", cfg->varinfo [v->idx]->dreg));
342 changed = TRUE;
343 break;
344 }
345 }
346 }
347
348 /* Check for intervals in inactive which expired or active */
349 changed = TRUE;
350 /* FIXME: Optimize this */
351 while (changed) {
352 changed = FALSE;
353 for (l = inactive; l != NULL; l = l->next) {
354 MonoMethodVar *v = (MonoMethodVar*)l->data;
355
356 if (v->interval->last_range->to < pos) {
357 inactive = g_list_delete_link (inactive, l);
358 LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", cfg->varinfo [v->idx]->dreg));
359 changed = TRUE;
360 break;
361 }
362 else if (mono_linterval_covers (v->interval, pos)) {
363 active = g_list_append (active, v);
364 inactive = g_list_delete_link (inactive, l);
365 LSCAN_DEBUG (printf ("\tInterval R%d became active\n", cfg->varinfo [v->idx]->dreg));
366 changed = TRUE;
367 break;
368 }
369 }
370 }
371
372 /* Find a register for the current interval */
373 for (i = 0; i < n_regs; ++i)
374 free_pos [i] = ((gint32)0x7fffffff);
375
376 for (l = active; l != NULL; l = l->next) {
377 MonoMethodVar *v = (MonoMethodVar*)l->data;
378
379 if (v->reg >= 0) {
380 free_pos [v->reg] = 0;
381 LSCAN_DEBUG (printf ("\threg %d is busy (cost %d)\n", v->reg, v->spill_costs));
382 }
383 }
384
385 for (l = inactive; l != NULL; l = l->next) {
386 MonoMethodVar *v = (MonoMethodVar*)l->data;
387 gint32 intersect_pos;
388
389 if (v->reg >= 0) {
390 intersect_pos = mono_linterval_get_intersect_pos (current->interval, v->interval);
391 if (intersect_pos != -1) {
392 free_pos [v->reg] = intersect_pos;
393 LSCAN_DEBUG (printf ("\threg %d becomes free at %d\n", v->reg, intersect_pos));
394 }
395 }
396 }
397
398 max_free_pos = -1;
399 reg = -1;
400 for (i = 0; i < n_regs; ++i)
401 if (free_pos [i] > max_free_pos) {
402 reg = i;
403 max_free_pos = free_pos [i];
404 }
405
406 g_assert (reg != -1);
407
408 if (free_pos [reg] >= current->interval->last_range->to) {
409 /* Register available for whole interval */
410 current->reg = reg;
411 LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg, cfg->varinfo [current->idx]->dreg));
412
413 active = g_list_append (active, current);
414 gains [current->reg] += current->spill_costs;
415 }
416 else {
417 /*
418 * free_pos [reg] > 0 means there is a register available for parts
419 * of the interval, so splitting it is possible. This is not yet
420 * supported, so we spill in this case too.
421 */
422
423 /* Spill an interval */
424
425 /* FIXME: Optimize the selection of the interval */
426
427 if (active) {
428 GList *min_spill_pos;
429 #if 0
430 /*
431 * This favors registers with big spill costs, thus larger liveness ranges,
432 * thus actually leading to worse code size.
433 */
434 guint32 min_spill_value = G_MAXINT32;
435
436 for (l = active; l != NULL; l = l->next) {
437 vmv = (MonoMethodVar*)l->data;
438
439 if (vmv->spill_costs < min_spill_value) {
440 min_spill_pos = l;
441 min_spill_value = vmv->spill_costs;
442 }
443 }
444 #else
445 /* Spill either the first active or the current interval */
446 min_spill_pos = active;
447 #endif
448 vmv = (MonoMethodVar*)min_spill_pos->data;
449 if (vmv->spill_costs < current->spill_costs) {
450 // if (vmv->interval->last_range->to < current->interval->last_range->to) {
451 gains [vmv->reg] -= vmv->spill_costs;
452 vmv->reg = -1;
453 LSCAN_DEBUG (printf ("\tSpilled R%d\n", cfg->varinfo [vmv->idx]->dreg));
454 active = g_list_delete_link (active, min_spill_pos);
455 }
456 else
457 LSCAN_DEBUG (printf ("\tSpilled current (cost %d)\n", current->spill_costs));
458 }
459 else
460 LSCAN_DEBUG (printf ("\tSpilled current\n"));
461 }
462 }
463
464 /* Decrease the gains by the cost of saving+restoring the register */
465 for (i = 0; i < n_regs; ++i) {
466 if (gains [i]) {
467 /* FIXME: This is x86 only */
468 gains [i] -= cfg->method->save_lmf ? 1 : 2;
469 if (gains [i] < 0)
470 gains [i] = 0;
471 }
472 }
473
474 /* Do the actual register assignment */
475 n_regvars = 0;
476 for (l = vars; l; l = l->next) {
477 vmv = (MonoMethodVar *)l->data;
478
479 if (vmv->reg >= 0) {
480 int reg_index = vmv->reg;
481
482 /* During allocation, vmv->reg is an index into the regs list */
483 vmv->reg = GPOINTER_TO_INT (g_list_nth_data (regs, vmv->reg));
484
485 if ((gains [reg_index] > regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
486 if (cfg->verbose_level > 2)
487 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));
488 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
489 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
490 n_regvars ++;
491 }
492 else {
493 if (cfg->verbose_level > 2)
494 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));
495 vmv->reg = -1;
496 }
497 }
498 }
499
500 cfg->stat_n_regvars = n_regvars;
501
502 /* Compute used regs */
503 used_regs = 0;
504 for (l = vars; l; l = l->next) {
505 vmv = (MonoMethodVar *)l->data;
506
507 if (vmv->reg >= 0)
508 used_regs |= 1LL << vmv->reg;
509 }
510
511 *used_mask |= used_regs;
512
513 g_list_free (active);
514 g_list_free (inactive);
515 }
516
517 #else /* !DISABLE_JIT */
518
519 MONO_EMPTY_SOURCE_FILE (linear_scan);
520
521 #endif /* !DISABLE_JIT */
522