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 */
108 if (!cfg->disable_reuse_registers) {
110 amv = (MonoMethodVar *)active->data;
112 if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
116 printf ("EXPIR %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
117 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
119 active = g_list_delete_link (active, active);
120 regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
121 gains [amv->reg] += amv->spill_costs;
125 if (active && g_list_length (active) == max_regs) {
128 a = g_list_nth (active, max_regs - 1);
129 amv = (MonoMethodVar *)a->data;
131 if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
132 (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
135 active = g_list_delete_link (active, a);
138 active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
140 active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
143 printf ("SPILL0 %2d %08x %08x C%d\n", amv->idx,
144 amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
149 printf ("SPILL1 %2d %08x %08x C%d\n", vmv->idx,
150 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
156 /* assign register */
160 vmv->reg = GPOINTER_TO_INT (regs->data);
162 used_regs |= 1LL << vmv->reg;
164 regs = g_list_delete_link (regs, regs);
167 printf ("ADD %2d %08x %08x C%d R%d\n", vmv->idx,
168 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
169 vmv->spill_costs, vmv->reg);
171 active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
176 for (a = active; a; a = a->next) {
177 amv = (MonoMethodVar *)a->data;
178 printf ("ACT %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
179 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
185 for (a = active; a; a = a->next) {
186 amv = (MonoMethodVar *)a->data;
187 gains [amv->reg] += amv->spill_costs;
190 for (l = vars; l; l = l->next) {
194 if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
195 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
196 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
197 if (cfg->verbose_level > 2)
198 printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
200 if (cfg->verbose_level > 2)
201 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));
206 if (vmv->reg == -1) {
207 if ((vmv->range.first_use.abs_pos >> 16) == (vmv->range.last_use.abs_pos >> 16)) {
209 * This variables is only used in a single basic block so
210 * convert it into a virtual register.
211 * FIXME: This increases register pressure in the local
212 * allocator, leading to the well known 'branches inside
213 * basic blocks screw up the allocator' problem.
216 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
217 cfg->varinfo [vmv->idx]->dreg = mono_regstate_next_int (cfg->rs);
221 if (cfg->verbose_level > 2)
222 printf ("NOT REGVAR: %d\n", vmv->idx);
227 /* Compute used regs */
229 for (l = vars; l; l = l->next) {
233 used_regs |= 1LL << vmv->reg;
236 *used_mask |= used_regs;
239 if (cfg->verbose_level > 2)
240 printf ("EXIT: final used mask: %08x\n", *used_mask);
244 g_list_free (active);