/*
 * liveness.c: liveness analysis
 *
 * Author:
 *   Dietmar Maurer (dietmar@ximian.com)
 *
 * (C) 2002 Ximian, Inc.
 */

#include "mini.h"
#include <mono/metadata/debug-helpers.h>

GList *
mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, int sort_type)
{
	GList *l;

	if (!list)
		return g_list_prepend (NULL, mv);

	for (l = list; l; l = l->next) {
		MonoMethodVar *v1 = l->data;
		
		if (sort_type == 2) {
			if (mv->spill_costs >= v1->spill_costs) {
				list = g_list_insert_before (list, l, mv);
				break;
			}			
		} else if (sort_type == 1) {
			if (mv->range.last_use.abs_pos <= v1->range.last_use.abs_pos) {
				list = g_list_insert_before (list, l, mv);
				break;
			}
		} else {
			if (mv->range.first_use.abs_pos <= v1->range.first_use.abs_pos) {
				list = g_list_insert_before (list, l, mv);
				break;
			}
		}
	}
	if (!l)
		list = g_list_append (list, mv);

	return list;
}

static gint 
compare_by_first_use_func (gconstpointer a, gconstpointer b)
{
	MonoMethodVar *v1 = (MonoMethodVar*)a;
	MonoMethodVar *v2 = (MonoMethodVar*)b;

	return v1->range.first_use.abs_pos - v2->range.first_use.abs_pos;
}

GList *
mono_varlist_sort (MonoCompile *cfg, GList *list, int sort_type)
{
	if (sort_type == 0)
		return g_list_sort (list, compare_by_first_use_func);
	else
		g_assert_not_reached ();

	return NULL;
}

// #define DEBUG_LSCAN

void
mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
{
	GList *l, *a, *active = NULL;
	MonoMethodVar *vmv, *amv;
	int max_regs, gains [sizeof (regmask_t) * 8];
	regmask_t used_regs = 0;
	gboolean cost_driven;

	cost_driven = TRUE;

#ifdef DEBUG_LSCAN
	printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
#endif

#ifdef DEBUG_LSCAN
	for (l = vars; l; l = l->next) {
		vmv = l->data;
		printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos, 
			vmv->range.last_use.abs_pos, vmv->spill_costs);
	}
#endif
	max_regs = g_list_length (regs);

	for (l = regs; l; l = l->next) {
		int regnum = GPOINTER_TO_INT (l->data);
		g_assert (regnum < G_N_ELEMENTS (gains));
		gains [regnum] = 0;
	}

	/* linear scan */
	for (l = vars; l; l = l->next) {
		vmv = l->data;

#ifdef DEBUG_LSCAN
		printf ("START  %2d %08x %08x\n",  vmv->idx, vmv->range.first_use.abs_pos, 
			vmv->range.last_use.abs_pos);
#endif
		/* expire old intervals in active */
		while (active) {
			amv = (MonoMethodVar *)active->data;

			if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
				break;

#ifdef DEBUG_LSCAN
			printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos, 
				amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
#endif
			active = g_list_delete_link (active, active);
			regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
			gains [amv->reg] += amv->spill_costs;
		}

		if (active && g_list_length (active) == max_regs) {
			/* Spill */

			a = g_list_nth (active, max_regs - 1);
			amv = (MonoMethodVar *)a->data;

			if ((cost_driven && amv->spill_costs < vmv->spill_costs) || 			     
			    (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
				vmv->reg = amv->reg;
				amv->reg = -1;
				active = g_list_delete_link (active, a);

				if (cost_driven)
					active = mono_varlist_insert_sorted (cfg, active, vmv, 2);	
				else
					active = mono_varlist_insert_sorted (cfg, active, vmv, 1);	

#ifdef DEBUG_LSCAN
				printf ("SPILL0 %2d %08x %08x C%d\n",  amv->idx, 
					amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
					amv->spill_costs);
#endif
			} else {
#ifdef DEBUG_LSCAN
				printf ("SPILL1 %2d %08x %08x C%d\n",  vmv->idx, 
					vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
					vmv->spill_costs);
#endif
				vmv->reg = -1;
			}
		} else {
			/* assign register */

			g_assert (regs);

			vmv->reg = GPOINTER_TO_INT (regs->data);

			used_regs |= 1LL << vmv->reg;

			regs = g_list_delete_link (regs, regs);

#ifdef DEBUG_LSCAN
			printf ("ADD    %2d %08x %08x C%d R%d\n",  vmv->idx, 
				vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos, 
				vmv->spill_costs, vmv->reg);
#endif
			active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);		
		}


#ifdef DEBUG_LSCAN
		for (a = active; a; a = a->next) {
			amv = (MonoMethodVar *)a->data;		
			printf ("ACT    %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,  
				amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
		}
		printf ("NEXT\n");
#endif
	}	

	for (a = active; a; a = a->next) {
		amv = (MonoMethodVar *)a->data;		
		gains [amv->reg] += amv->spill_costs;
	}

	for (l = vars; l; l = l->next) {
		vmv = l->data;
		
		if (vmv->reg >= 0)  {
			if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
				cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
				cfg->varinfo [vmv->idx]->dreg = vmv->reg;
				if (cfg->verbose_level > 2)
					printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
			} else {
				if (cfg->verbose_level > 2)
					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));
				vmv->reg = -1;
			}
		}

		if (vmv->reg == -1) {
			if ((vmv->range.first_use.abs_pos >> 16) == (vmv->range.last_use.abs_pos >> 16)) {
				/*
				 * This variables is only used in a single basic block so
				 * convert it into a virtual register.
				 * FIXME: This increases register pressure in the local
				 * allocator, leading to the well known 'branches inside
				 * basic blocks screw up the allocator' problem.
				 */
#if 0
				//#ifdef MONO_ARCH_HAS_XP_LOCAL_REGALLOC
				cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
				cfg->varinfo [vmv->idx]->dreg = mono_regstate_next_int (cfg->rs);
#endif
			}
			else {
				if (cfg->verbose_level > 2)
					printf ("NOT REGVAR: %d\n", vmv->idx);
			}
		}
	}

	/* Compute used regs */
	used_regs = 0;
	for (l = vars; l; l = l->next) {
		vmv = l->data;
		
		if (vmv->reg >= 0)
			used_regs |= 1LL << vmv->reg;
	}

	*used_mask |= used_regs;

#ifdef DEBUG_LSCAN
	if (cfg->verbose_level > 2)
		printf ("EXIT: final used mask: %08x\n", *used_mask);
#endif

	g_list_free (regs);
	g_list_free (active);
	g_list_free (vars);
}