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 ();
67 mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
69 GList *l, *a, *active = NULL;
70 MonoMethodVar *vmv, *amv;
71 int max_regs, gains [sizeof (regmask_t) * 8];
72 regmask_t used_regs = 0;
75 cost_driven = (cfg->comp_done & MONO_COMP_LOOPS);
78 printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
82 for (l = vars; l; l = l->next) {
84 printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos,
85 vmv->range.last_use.abs_pos, vmv->spill_costs);
88 max_regs = g_list_length (regs);
90 for (l = regs; l; l = l->next) {
91 int regnum = (int)l->data;
92 g_assert (regnum < G_N_ELEMENTS (gains));
97 for (l = vars; l; l = l->next) {
101 printf ("START %2d %08x %08x\n", vmv->idx, vmv->range.first_use.abs_pos,
102 vmv->range.last_use.abs_pos);
104 /* expire old intervals in active */
106 amv = (MonoMethodVar *)active->data;
108 if (amv->range.last_use.abs_pos >= vmv->range.first_use.abs_pos)
112 printf ("EXPIR %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
113 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
115 active = g_list_remove_link (active, active);
116 regs = g_list_prepend (regs, (gpointer)amv->reg);
117 gains [amv->reg] += amv->spill_costs;
120 if (active && g_list_length (active) == max_regs) {
123 a = g_list_nth (active, max_regs - 1);
124 amv = (MonoMethodVar *)a->data;
126 if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
127 (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
130 active = g_list_remove_link (active, a);
133 active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
135 active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
138 printf ("SPILL0 %2d %08x %08x C%d\n", amv->idx,
139 amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
144 printf ("SPILL1 %2d %08x %08x C%d\n", vmv->idx,
145 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
151 /* assign register */
155 vmv->reg = (int)regs->data;
157 used_regs |= 1LL << vmv->reg;
159 regs = g_list_remove_link (regs, regs);
162 printf ("ADD %2d %08x %08x C%d R%d\n", vmv->idx,
163 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
164 vmv->spill_costs, vmv->reg);
166 active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
171 for (a = active; a; a = a->next) {
172 amv = (MonoMethodVar *)a->data;
173 printf ("ACT %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
174 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
180 for (a = active; a; a = a->next) {
181 amv = (MonoMethodVar *)a->data;
182 gains [amv->reg] += amv->spill_costs;
185 for (l = vars; l; l = l->next) {
189 if (gains [vmv->reg] > 3) {
190 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
191 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
192 if (cfg->verbose_level > 2)
193 printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
195 used_regs &= ~(1LL << vmv->reg);
201 *used_mask |= used_regs;
204 g_list_free (active);