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);
49 mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, guint32 *used_mask)
51 GList *l, *a, *active = NULL;
52 MonoMethodVar *vmv, *amv;
53 int max_regs, gains [32];
54 guint32 used_regs = 0;
57 cost_driven = (cfg->comp_done & MONO_COMP_LOOPS);
60 printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
64 for (l = vars; l; l = l->next) {
66 printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos,
67 vmv->range.last_use.abs_pos, vmv->spill_costs);
70 max_regs = g_list_length (regs);
72 for (l = regs; l; l = l->next) {
73 int regnum = (int)l->data;
74 g_assert (regnum < G_N_ELEMENTS (gains));
79 for (l = vars; l; l = l->next) {
83 printf ("START %2d %08x %08x\n", vmv->idx, vmv->range.first_use.abs_pos,
84 vmv->range.last_use.abs_pos);
86 /* expire old intervals in active */
88 amv = (MonoMethodVar *)active->data;
90 if (amv->range.last_use.abs_pos >= vmv->range.first_use.abs_pos)
94 printf ("EXPIR %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
95 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
97 active = g_list_remove_link (active, active);
98 regs = g_list_prepend (regs, (gpointer)amv->reg);
99 gains [amv->reg] += amv->spill_costs;
102 if (active && g_list_length (active) == max_regs) {
105 a = g_list_nth (active, max_regs - 1);
106 amv = (MonoMethodVar *)a->data;
108 if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
109 (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
112 active = g_list_remove_link (active, a);
115 active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
117 active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
120 printf ("SPILL0 %2d %08x %08x C%d\n", amv->idx,
121 amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
126 printf ("SPILL1 %2d %08x %08x C%d\n", vmv->idx,
127 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
133 /* assign register */
137 vmv->reg = (int)regs->data;
139 used_regs |= 1 << vmv->reg;
141 regs = g_list_remove_link (regs, regs);
144 printf ("ADD %2d %08x %08x C%d\n", vnum,
145 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
148 active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
153 for (a = active; a; a = a->next) {
154 amv = (MonoMethodVar *)a->data;
155 printf ("ACT %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
156 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
162 for (a = active; a; a = a->next) {
163 amv = (MonoMethodVar *)a->data;
164 gains [amv->reg] += amv->spill_costs;
167 for (l = vars; l; l = l->next) {
171 if (gains [vmv->reg] > 5) {
172 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
173 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
175 printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
178 used_regs &= ~(1 << vmv->reg);
184 *used_mask |= used_regs;
187 g_list_free (active);