/* src/vm/jit/schedule/schedule.c - architecture independent instruction
                                    scheduler

   Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   J. Wenninger, Institut f. Computersprachen - TU Wien

   This file is part of CACAO.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2, or (at
   your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301, USA.

   Contact: cacao@cacaojvm.org

   Authors: Christian Thalinger

   Changes:

*/


#include "config.h"

#include <stdio.h>

#include "vm/types.h"

#include "disass.h"

#include "mm/memory.h"
#include "vm/options.h"
#include "vm/statistics.h"
#include "vm/jit/schedule/schedule.h"


/* XXX quick hack */
s4 stackrange;

scheduledata *schedule_init(methodinfo *m, registerdata *rd)
{
	scheduledata *sd;

	sd = DNEW(scheduledata);

	stackrange = 
		(rd->savintregcnt - rd->maxsavintreguse) +
		(rd->savfltregcnt - rd->maxsavfltreguse) +
		rd->maxmemuse +
		m->parseddesc->paramcount +
		1;                           /* index 0 are all other memory accesses */

	/* XXX quick hack: just use a fixed number of instructions */
	sd->mi = DMNEW(minstruction, 20000);

	sd->intregs_define_dep = DMNEW(edgenode*, rd->intregsnum);
	sd->fltregs_define_dep = DMNEW(edgenode*, rd->fltregsnum);

	sd->intregs_use_dep = DMNEW(edgenode*, rd->intregsnum);
	sd->fltregs_use_dep = DMNEW(edgenode*, rd->fltregsnum);

  	sd->memory_define_dep = DMNEW(edgenode*, stackrange);
  	sd->memory_use_dep = DMNEW(edgenode*, stackrange);


	/* open graphviz file */

	if (opt_verbose) {
		FILE *file;

		file = fopen("cacao.dot", "w+");
		fprintf(file, "digraph G {\n");

		sd->file = file;
	}

	return sd;
}


void schedule_reset(scheduledata *sd, registerdata *rd)
{
	sd->micount = 0;
	sd->leaders = NULL;

	/* set define array to -1, because 0 is a valid node number */

	MSET(sd->intregs_define_dep, 0, edgenode*, rd->intregsnum);
	MSET(sd->fltregs_define_dep, 0, edgenode*, rd->fltregsnum);

	/* clear all use pointers */

	MSET(sd->intregs_use_dep, 0, edgenode*, rd->intregsnum);
	MSET(sd->fltregs_use_dep, 0, edgenode*, rd->fltregsnum);

  	MSET(sd->memory_define_dep, 0, edgenode*, stackrange);
  	MSET(sd->memory_use_dep, 0, edgenode*, stackrange);
}


void schedule_close(scheduledata *sd)
{
	if (opt_verbose) {
		FILE *file;

		file = sd->file;

		fprintf(file, "}\n");
		fclose(file);
	}
}



/* schedule_add_define_dep *****************************************************

   XXX

*******************************************************************************/

void schedule_add_define_dep(scheduledata *sd, s1 opnum, edgenode **define_dep, edgenode **use_dep)
{
	minstruction *mi;
	minstruction *defmi;
	minstruction *usemi;
	edgenode     *en;
	edgenode     *useen;
	edgenode     *defen;
	edgenode     *tmpen;
	s4            minum;

	/* get current machine instruction */

	minum = sd->micount - 1;
	mi = &sd->mi[minum];

	/* get current use dependency nodes, if non-null use them... */

	if ((useen = *use_dep)) {
		while (useen) {
			/* Save next pointer so we can link the current node to the       */
			/* machine instructions' dependency list.                         */

			tmpen = useen->next;

			/* don't add the current machine instruction (e.g. add A0,A0,A0) */

			if (useen->minum != minum) {
				/* some edges to current machine instruction -> no leader */

				mi->flags &= ~SCHEDULE_LEADER;

				/* get use machine instruction */

				usemi = &sd->mi[useen->minum];

				/* link current use node into dependency list */

				useen->minum = minum;
				useen->opnum2 = opnum;

				/* calculate latency, for define add 1 cycle */
				useen->latency = (usemi->op[useen->opnum].lastcycle -
								  mi->op[opnum].firstcycle) + 1;

				useen->next = usemi->deps;
				usemi->deps = useen;
			}

			useen = tmpen;
		}

		/* ...otherwise use last define dependency, if non-null */
	} else if ((defen = *define_dep)) {
		/* some edges to current machine instruction -> no leader */

		mi->flags &= ~SCHEDULE_LEADER;

		/* get last define machine instruction */

		defmi = &sd->mi[defen->minum];

		/* link current define node into dependency list */

		defen->minum = minum;
		defen->opnum2 = opnum;

		/* calculate latency, for define add 1 cycle */
		defen->latency = (defmi->op[defen->opnum].lastcycle -
						  mi->op[opnum].firstcycle) + 1;

		defen->next = defmi->deps;
		defmi->deps = defen;
	}

	/* Set current instruction as new define dependency and clear use         */
	/* dependencies.                                                          */

	en = DNEW(edgenode);
	en->minum = minum;
	en->opnum = opnum;
	
	*define_dep = en;
	*use_dep = NULL;
}


/* schedule_add_use_dep ********************************************************

   XXX

*******************************************************************************/

void schedule_add_use_dep(scheduledata *sd, s1 opnum, edgenode **define_dep, edgenode **use_dep)
{
	minstruction *mi;
	minstruction *defmi;
	edgenode     *en;
	edgenode     *defen;
	s4            minum;

	/* get current machine instruction */

	minum = sd->micount - 1;
	mi = &sd->mi[minum];

	/* get current define dependency instruction */

	if ((defen = *define_dep)) {
		/* some edges to current machine instruction -> no leader */

		mi->flags &= ~SCHEDULE_LEADER;

		/* add node to dependency list of current define node */

		defmi = &sd->mi[defen->minum];

		en = DNEW(edgenode);
		en->minum = minum;
		en->opnum = defen->opnum;
		en->opnum2 = opnum;

		/* calculate latency */
		en->latency = (defmi->op[defen->opnum].lastcycle -
					   mi->op[opnum].firstcycle);

		en->next = defmi->deps;
		defmi->deps = en;
	}

	/* add node to list of current use nodes */

	en = DNEW(edgenode);
	en->minum = minum;
	en->opnum = opnum;
	en->next = *use_dep;
	*use_dep = en;
}


/* schedule_calc_priorities ****************************************************

   Calculates the current node's priority by getting highest priority
   of the dependency nodes, adding this nodes latency plus 1 (for the
   instruction itself).

*******************************************************************************/

void schedule_calc_priorities(scheduledata *sd)
{
	minstruction *mi;
	minstruction *lastmi;
	edgenode     *en;
	s4            lastnode;
	s4            i;
	s4            j;
	s4            criticalpath;
	s4            currentpath;
	s1            lastcycle;


	/* last node MUST always be the last instruction scheduled */

	lastnode = sd->micount - 1;

	/* if last instruction is the first instruction, skip everything */

	if (lastnode > 0) {
		lastmi = &sd->mi[lastnode];

		/* last instruction is no leader */

		lastmi->flags &= ~SCHEDULE_LEADER;

		/* last instruction has no dependencies, use virtual sink node */

		lastcycle = 0;

		for (j = 0; j < 4; j++) {
			if (lastmi->op[j].lastcycle > lastcycle)
				lastcycle = lastmi->op[j].lastcycle;
		}

#define EARLIEST_USE_CYCLE 3
		lastmi->priority = (lastcycle - EARLIEST_USE_CYCLE) + 1;


		/* walk through all remaining machine instructions backwards */

		for (i = lastnode - 1, mi = &sd->mi[lastnode - 1]; i >= 0; i--, mi--) {
			en = mi->deps;

			if (en) {
				s4 priority;

				criticalpath = 0;

				/* walk through depedencies and calculate highest latency */

				while (en) {
					priority = sd->mi[en->minum].priority;

					currentpath = en->latency + priority;

					if (currentpath > criticalpath)
						criticalpath = currentpath;

					en = en->next;
				}

				/* set priority to critical path */

				mi->priority = criticalpath;

			} else {
				/* no dependencies, use virtual sink node */

				lastcycle = 0;

				for (j = 0; j < 4; j++) {
					if (mi->op[j].lastcycle > lastcycle)
						lastcycle = mi->op[j].lastcycle;
				}

				mi->priority = (lastcycle - EARLIEST_USE_CYCLE);
			}

			/* add current machine instruction to leader list, if one */

			if (mi->flags & SCHEDULE_LEADER) {
				en = DNEW(edgenode);
				en->minum = i;
				en->next = sd->leaders;
				sd->leaders = en;
			}
		}

	} else {
		/* last node is first instruction, add to leader list */

		en = DNEW(edgenode);
		en->minum = lastnode;
		en->next = sd->leaders;
		sd->leaders = en;
	}
}


static void schedule_create_graph(scheduledata *sd, s4 criticalpath)
{
	minstruction *mi;
	edgenode     *en;
	s4            i;

	FILE *file;
	static int bb = 1;

	file = sd->file;

	fprintf(file, "subgraph cluster_%d {\n", bb);
	fprintf(file, "label = \"BB%d (nodes: %d, critical path: %d)\"\n", bb, sd->micount, criticalpath);

	for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {

		en = mi->deps;

		if (en) {
			while (en) {
				fprintf(file, "\"#%d.%d ", bb, i);
				disassinstr(file, &mi->instr);
				fprintf(file, "\\np=%d\"", mi->priority);

				fprintf(file, " -> ");

				fprintf(file, "\"#%d.%d ", bb, en->minum);
				disassinstr(file, &sd->mi[en->minum].instr);
				fprintf(file, "\\np=%d\"", sd->mi[en->minum].priority);

				fprintf(file, " [ label = \"%d\" ]\n", en->latency);
				en = en->next;
			}

		} else {
			fprintf(file, "\"#%d.%d ", bb, i);
			disassinstr(file, &mi->instr);
			fprintf(file, "\\np=%d\"", mi->priority);

			fprintf(file, " -> ");
			
			fprintf(file, "\"end %d\"", bb);

			fprintf(file, " [ label = \"%d\" ]\n", mi->priority);
	
			fprintf(file, "\n");
		}
	}

	fprintf(file, "}\n");

	bb++;
}


/* schedule_add_deps_to_leaders ************************************************

   Walk through all dependencies, change the starttime and add the
   node to the leaders list.

*******************************************************************************/

static void schedule_add_deps_to_leaders(scheduledata *sd, edgenode *deps, s4 time)
{
	edgenode *depen;
	edgenode *preven;

	if ((depen = deps)) {
		while (depen) {
			/* set starttime of instruction */

			sd->mi[depen->minum].starttime = time + depen->latency;

			/* save last entry */

			preven = depen;

			depen = depen->next;
		}

		/* add dependencies to front of the list */

		preven->next = sd->leaders;
		sd->leaders = deps;
	}
}


/* schedule_do_schedule ********************************************************

   XXX

*******************************************************************************/

void schedule_do_schedule(scheduledata *sd)
{
	minstruction *mi;
	edgenode     *en;
	s4            i;
	s4            j;
	s4            leaders;
	s4            criticalpath;
	s4            time;
	s4            schedulecount;

	minstruction *alumi;
	minstruction *memmi;
	minstruction *brmi;

	edgenode     *preven;
	edgenode     *depen;

	edgenode     *aluen;
	edgenode     *memen;
	edgenode     *bren;

	/* It may be possible that no instructions are in the current basic block */
	/* because after an branch instruction the instructions are scheduled.    */

	if (sd->micount > 0) {
		/* calculate priorities and critical path */

		schedule_calc_priorities(sd);

		if (opt_verbose) {
			printf("bb start ---\n");
			printf("nodes: %d\n", sd->micount);
			printf("leaders: ");
		}

		leaders = 0;
		criticalpath = 0;

		en = sd->leaders;
		while (en) {
			if (opt_verbose) {
				printf("#%d ", en->minum);
			}

			leaders++;
			if (sd->mi[en->minum].priority > criticalpath)
				criticalpath = sd->mi[en->minum].priority;
			en = en->next;
		}

		/* check last node for critical path (e.g. ret) */

		if (sd->mi[sd->micount - 1].priority > criticalpath)
			criticalpath = sd->mi[sd->micount - 1].priority;
		
		if (opt_verbose) {
			printf("\n");
			printf("critical path: %d\n", criticalpath);

			for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {
				disassinstr(stdout, &mi->instr);

				printf("\t--> #%d, prio=%d", i, mi->priority);

				printf(", mem=%d:%d", mi->op[0].firstcycle, mi->op[0].lastcycle);

				for (j = 1; j <= 3; j++) {
					printf(", op%d=%d:%d", j, mi->op[j].firstcycle, mi->op[j].lastcycle);
				}

				printf(", deps= ");
				en = mi->deps;
				while (en) {
					printf("#%d (op%d->op%d: %d) ", en->minum, en->opnum, en->opnum2, en->latency);
					en = en->next;
				}
				printf("\n");
			}
			printf("bb end ---\n\n");

			schedule_create_graph(sd, criticalpath);
		}


		/* set start time to zero */

		printf("\n\nschedule start ---\n");
		time = 0;
		schedulecount = 0;

		while (sd->leaders) {
			/* XXX argh! how to make this portable? */
			for (j = 0; j < 2; j++ ) {
				en = sd->leaders;
				preven = NULL;

				alumi = NULL;
				memmi = NULL;
				brmi = NULL;

				aluen = NULL;
				memen = NULL;
				bren = NULL;

				printf("\n\nleaders: ");
				while (en) {
					/* get current machine instruction from leader list */

					mi = &sd->mi[en->minum];
					disassinstr(stdout, &mi->instr);
					printf(", ");

					/* starttime reached */

					if (mi->starttime <= time) {

						/* check for a suitable ALU instruction */

						if ((mi->flags & SCHEDULE_UNIT_ALU) &&
							(!alumi || (mi->priority > alumi->priority))) {
							/* remove/replace current node from leaders list */

							if (preven)
								if (alumi) {
									preven->next = aluen;
									aluen->next = en->next;
								} else {
									preven->next = en->next;
								}
							else
								if (alumi) {
									sd->leaders = aluen;
									aluen->next = en->next;
								} else {
									sd->leaders = en->next;
								}

							/* set current ALU instruction and node */

							alumi = mi;
							aluen = en;

						/* check for a suitable MEM instruction */

						} else if ((mi->flags & SCHEDULE_UNIT_MEM) &&
								   (!memmi || (mi->priority > memmi->priority))) {
							if (preven)
								if (memmi) {
									preven->next = memen;
									memen->next = en->next;
								} else {
									preven->next = en->next;
								}
							else
								if (memmi) {
									sd->leaders = memen;
									memen->next = en->next;
								} else {
									sd->leaders = en->next;
								}

							memmi = mi;
							memen = en;

						/* check for a suitable BRANCH instruction */

						} else if ((mi->flags & SCHEDULE_UNIT_BRANCH) &&
								   (!brmi || (mi->priority > brmi->priority))) {
							if (preven)
								preven->next = en->next;
							else
								sd->leaders = en->next;

							memmi = mi;
							memen = en;

						} else
							preven = en;

					} else {
						/* not leader removed, save next previous node */

						preven = en;
					}

					en = en->next;
				}
				printf("\n");

				/* schedule ALU instruction, if one was found */

				if (aluen) {
					mi = &sd->mi[aluen->minum];

					disassinstr(stdout, &mi->instr);
					printf(" || ");

					schedulecount++;
					schedule_add_deps_to_leaders(sd, mi->deps, time);
				}

				/* schedule MEM instruction, if one was found */

				if (memen) {
					mi = &sd->mi[memen->minum];

					disassinstr(stdout, &mi->instr);
					printf(" || ");

					schedulecount++;
					schedule_add_deps_to_leaders(sd, mi->deps, time);
				}

				/* schedule BRANCH instruction, if one was found */

				if (bren) {
					mi = &sd->mi[bren->minum];

					disassinstr(stdout, &brmi->instr);
					printf(" || ");

					schedulecount++;
					schedule_add_deps_to_leaders(sd, mi->deps, time);
				}

				if (!aluen && !memen && !bren) {
					printf("nop");
					printf(" || ");
				}
			}
			printf("\n");

			/* bundle finished, increase execution time */

			time++;
		}
		printf("schedule end ---\n\n");

#if defined(ENABLE_STATISTICS)
		if (opt_stat) {
			count_schedule_basic_blocks++;
			count_schedule_nodes += sd->micount;
			count_schedule_leaders += leaders;

			if (leaders > count_schedule_max_leaders)
				count_schedule_max_leaders = leaders;

			count_schedule_critical_path += criticalpath;
		}
#endif
	}
}


/*
 * These are local overrides for various environment variables in Emacs.
 * Please do not remove this and leave it at the end of the file, where
 * Emacs will automagically detect them.
 * ---------------------------------------------------------------------
 * Local variables:
 * mode: c
 * indent-tabs-mode: t
 * c-basic-offset: 4
 * tab-width: 4
 * End:
 */