2 * liveness.c: liveness analysis
5 * Dietmar Maurer (dietmar@ximian.com)
7 * (C) 2002 Ximian, Inc.
13 mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, int sort_type)
18 return g_list_prepend (NULL, mv);
20 for (l = list; l; l = l->next) {
21 MonoMethodVar *v1 = l->data;
24 if (mv->spill_costs >= v1->spill_costs) {
25 list = g_list_insert_before (list, l, mv);
28 } else if (sort_type == 1) {
29 if (mv->range.last_use.abs_pos <= v1->range.last_use.abs_pos) {
30 list = g_list_insert_before (list, l, mv);
34 if (mv->range.first_use.abs_pos <= v1->range.first_use.abs_pos) {
35 list = g_list_insert_before (list, l, mv);
41 list = g_list_append (list, mv);
47 compare_by_first_use_func (gconstpointer a, gconstpointer b)
49 MonoMethodVar *v1 = (MonoMethodVar*)a;
50 MonoMethodVar *v2 = (MonoMethodVar*)b;
52 return v1->range.first_use.abs_pos - v2->range.first_use.abs_pos;
56 mono_varlist_sort (MonoCompile *cfg, GList *list, int sort_type)
59 return g_list_sort (list, compare_by_first_use_func);
61 g_assert_not_reached ();
69 mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
71 GList *l, *a, *active = NULL;
72 MonoMethodVar *vmv, *amv;
73 int max_regs, gains [sizeof (regmask_t) * 8];
74 regmask_t used_regs = 0;
77 cost_driven = (cfg->comp_done & MONO_COMP_LOOPS);
80 printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
84 for (l = vars; l; l = l->next) {
86 printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos,
87 vmv->range.last_use.abs_pos, vmv->spill_costs);
90 max_regs = g_list_length (regs);
92 for (l = regs; l; l = l->next) {
93 int regnum = (int)l->data;
94 g_assert (regnum < G_N_ELEMENTS (gains));
99 for (l = vars; l; l = l->next) {
103 printf ("START %2d %08x %08x\n", vmv->idx, vmv->range.first_use.abs_pos,
104 vmv->range.last_use.abs_pos);
106 /* expire old intervals in active */
108 amv = (MonoMethodVar *)active->data;
110 if (amv->range.last_use.abs_pos >= vmv->range.first_use.abs_pos)
114 printf ("EXPIR %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
115 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
117 active = g_list_remove_link (active, active);
118 regs = g_list_prepend (regs, (gpointer)amv->reg);
119 gains [amv->reg] += amv->spill_costs;
122 if (active && g_list_length (active) == max_regs) {
125 a = g_list_nth (active, max_regs - 1);
126 amv = (MonoMethodVar *)a->data;
128 if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
129 (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
132 active = g_list_remove_link (active, a);
135 active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
137 active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
140 printf ("SPILL0 %2d %08x %08x C%d\n", amv->idx,
141 amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
146 printf ("SPILL1 %2d %08x %08x C%d\n", vmv->idx,
147 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
153 /* assign register */
157 vmv->reg = (int)regs->data;
159 used_regs |= 1LL << vmv->reg;
161 regs = g_list_remove_link (regs, regs);
164 printf ("ADD %2d %08x %08x C%d R%d\n", vmv->idx,
165 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
166 vmv->spill_costs, vmv->reg);
168 active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
173 for (a = active; a; a = a->next) {
174 amv = (MonoMethodVar *)a->data;
175 printf ("ACT %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
176 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
182 for (a = active; a; a = a->next) {
183 amv = (MonoMethodVar *)a->data;
184 gains [amv->reg] += amv->spill_costs;
187 for (l = vars; l; l = l->next) {
191 if (gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) {
192 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
193 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
194 if (cfg->verbose_level > 2)
195 printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
201 /* Compute used regs */
203 for (l = vars; l; l = l->next) {
207 used_regs |= 1LL << vmv->reg;
210 *used_mask |= used_regs;
213 g_list_free (active);