-/* vm/jit/schedule/schedule.c - architecture independent instruction scheduler
+/* src/vm/jit/schedule/schedule.c - architecture independent instruction
+ scheduler
Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
Changes:
- $Id: schedule.c 1973 2005-03-02 16:27:05Z twisti $
+ $Id: schedule.c 1985 2005-03-04 17:09:13Z twisti $
*/
/* XXX quick hack: just use a fix number of instructions */
sd->mi = DMNEW(minstruction, 100);
- sd->micount = 0;
-
sd->intregs_define_dep = DMNEW(s4, rd->intregsnum);
sd->fltregs_define_dep = DMNEW(s4, rd->fltregsnum);
sd->intregs_use_dep = DMNEW(nodelink*, rd->intregsnum);
sd->fltregs_use_dep = DMNEW(nodelink*, rd->fltregsnum);
- /* clear all pointers */
-
- MSET(sd->intregs_define_dep, 0, s4, rd->intregsnum);
- MSET(sd->fltregs_define_dep, 0, s4, rd->fltregsnum);
-
- MSET(sd->intregs_use_dep, 0, nodelink*, rd->intregsnum);
- MSET(sd->fltregs_use_dep, 0, nodelink*, rd->fltregsnum);
-
sd->memory_define_dep = NULL;
sd->memory_use_dep = NULL;
}
-/* schedule_calc_priority ******************************************************
-
- 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_priority(minstruction *mi)
+void schedule_setup(scheduledata *sd, registerdata *rd)
{
- s4 i;
- s4 pathpriority;
+ sd->micount = 0;
+ sd->leaders = NULL;
- /* check all dependencies for their priority */
+ /* set define array to -1, because 0 is a valid node number */
- pathpriority = 0;
+ MSET(sd->intregs_define_dep, -1, s4, rd->intregsnum);
+ MSET(sd->fltregs_define_dep, -1, s4, rd->fltregsnum);
- for (i = 0; i < 3; i++) {
-/* if (mi->opdep[i]) { */
-/* if (mi->opdep[i]->priority > pathpriority) */
-/* pathpriority = mi->opdep[i]->priority; */
-/* } */
- }
+ /* clear all use pointers */
- mi->priority = pathpriority + mi->latency + 1;
+ MSET(sd->intregs_use_dep, 0, nodelink*, rd->intregsnum);
+ MSET(sd->fltregs_use_dep, 0, nodelink*, rd->fltregsnum);
+
+ sd->memory_define_dep = NULL;
+ sd->memory_use_dep = NULL;
}
-void schedule_add_int_define_dep(scheduledata *sd, s4 reg)
+void schedule_add_define_dep(scheduledata *sd, s4 *define_dep, nodelink **use_dep)
{
minstruction *mi;
minstruction *defmi;
/* get current machine instruction */
- minode = sd->micount;
- mi = &sd->mi[minode - 1];
+ minode = sd->micount - 1;
+ mi = &sd->mi[minode];
/* get current use dependency nodes, if non-null use them... */
- if ((usenl = sd->intregs_use_dep[reg])) {
+ if ((usenl = *use_dep)) {
/* add a dependency link node to all use dependency nodes */
while (usenl) {
+ /* Save next pointer so we can link the current node to the */
+ /* machine instructions' dependency list. */
+
tmpnl = usenl->next;
- /* don't add to the current machine instruction */
+ /* don't add the current machine instruction */
if (usenl->minode != minode) {
/* some edges to current machine instruction -> no leader */
- mi->leader = false;
+ mi->flags &= ~SCHEDULE_LEADER;
/* get use machine instruction */
- usemi = &sd->mi[usenl->minode - 1];
+ usemi = &sd->mi[usenl->minode];
-/* nl = DNEW(nodelink); */
-/* nl->minode = sd->micount; */
-/* nl->next = usemi->deps; */
-/* usemi->deps = nl; */
+ /* link current use node into dependency list */
usenl->minode = minode;
usenl->next = usemi->deps;
} else {
/* ...otherwise use last define dependency, if non-null */
- if ((defnode = sd->intregs_define_dep[reg]) > 0) {
+ if ((defnode = *define_dep) >= 0) {
/* some edges to current machine instruction -> no leader */
- mi->leader = false;
+ mi->flags &= ~SCHEDULE_LEADER;
/* get last define machine instruction */
- defmi = &sd->mi[defnode - 1];
+ defmi = &sd->mi[defnode];
nl = DNEW(nodelink);
- nl->minode = sd->micount;
+ nl->minode = minode;
nl->next = defmi->deps;
defmi->deps = nl;
}
/* Set current instruction as new define dependency and clear use */
/* depedencies. */
- sd->intregs_define_dep[reg] = sd->micount;
- sd->intregs_use_dep[reg] = NULL;
+ *define_dep = minode;
+ *use_dep = NULL;
}
-void schedule_add_int_use_dep(scheduledata *sd, s4 reg)
+void schedule_add_use_dep(scheduledata *sd, s4 *define_dep, nodelink **use_dep)
{
minstruction *mi;
minstruction *defmi;
nodelink *nl;
+ s4 minode;
s4 defnode;
/* get current machine instruction */
- mi = &sd->mi[sd->micount - 1];
+ minode = sd->micount - 1;
+ mi = &sd->mi[minode];
/* get current define dependency instruction */
- if ((defnode = sd->intregs_define_dep[reg]) > 0) {
+ if ((defnode = *define_dep) >= 0) {
/* some edges to current machine instruction -> no leader */
- mi->leader = false;
+ mi->flags &= ~SCHEDULE_LEADER;
/* add node to dependency list of current define node */
- defmi = &sd->mi[defnode - 1];
+ defmi = &sd->mi[defnode];
nl = DNEW(nodelink);
- nl->minode = sd->micount;
+ nl->minode = minode;
nl->next = defmi->deps;
defmi->deps = nl;
}
/* add node to list of current use nodes */
nl = DNEW(nodelink);
- nl->minode = sd->micount;
- nl->next = sd->intregs_use_dep[reg];
- sd->intregs_use_dep[reg] = nl;
+ nl->minode = minode;
+ nl->next = *use_dep;
+ *use_dep = nl;
}
-void schedule_add_flt_define_dep(scheduledata *sd, s4 reg)
+void schedule_add_memory_define_dep(scheduledata *sd)
{
- minstruction *mi;
- minstruction *defmi;
- minstruction *usemi;
- nodelink *usenl;
- nodelink *nl;
- s4 defnode;
+}
- /* get current machine instruction */
- mi = &sd->mi[sd->micount - 1];
+void schedule_add_memory_use_dep(scheduledata *sd)
+{
+}
- /* get current use dependency nodes, if non-null use them... */
- if ((usenl = sd->fltregs_use_dep[reg])) {
- /* add a dependency link node to all use dependency nodes */
+/* schedule_calc_priorities ****************************************************
- while (usenl) {
- /* don't add to the current machine instruction */
+ Calculates the current node's priority by getting highest priority
+ of the dependency nodes, adding this nodes latency plus 1 (for the
+ instruction itself).
- if (usenl->minode != sd->micount) {
- /* some edges to current machine instruction -> no leader */
+*******************************************************************************/
- mi->leader = false;
+void schedule_calc_priorities(scheduledata *sd)
+{
+ minstruction *mi;
+ nodelink *nl;
+ s4 i;
+ u1 startcycle;
+ u1 endcycle;
+ s1 priority;
+ s4 criticalpath;
+ s4 currentpath;
- /* get use machine instruction */
+ /* walk through all machine instructions backwards */
- usemi = &sd->mi[usenl->minode - 1];
+ for (i = sd->micount - 1, mi = &sd->mi[sd->micount - 1]; i >= 0; i--, mi--) {
+ nl = mi->deps;
- nl = DNEW(nodelink);
- nl->minode = sd->micount;
- nl->next = usemi->deps;
- usemi->deps = nl;
- }
+ /* do we have some dependencies */
- usenl = usenl->next;
- }
+ if (nl) {
+ endcycle = mi->endcycle;
+ criticalpath = 0;
- } else {
- /* ...otherwise use last define dependency, if non-null */
+ /* walk through depedencies and calculate highest latency */
- if ((defnode = sd->fltregs_define_dep[reg]) > 0) {
- /* some edges to current machine instruction -> no leader */
+ while (nl) {
+ startcycle = sd->mi[nl->minode].startcycle;
+ priority = sd->mi[nl->minode].priority;
- mi->leader = false;
+ currentpath = (endcycle - startcycle) + priority;
- /* get last define machine instruction */
+ if (currentpath > criticalpath)
+ criticalpath = currentpath;
- defmi = &sd->mi[defnode - 1];
+ nl = nl->next;
+ }
- nl = DNEW(nodelink);
- nl->minode = sd->micount;
- nl->next = defmi->deps;
- defmi->deps = nl;
+ mi->priority = criticalpath;
+
+ } else {
+ /* no dependencies, use virtual sink node */
+
+ mi->priority = mi->endcycle - mi->startcycle;
}
- }
- /* Set current instruction as new define dependency and clear use */
- /* depedencies. */
+ /* add leader to leader list */
- sd->fltregs_define_dep[reg] = sd->micount;
- sd->fltregs_use_dep[reg] = NULL;
+ if (mi->flags & SCHEDULE_LEADER) {
+ nl = DNEW(nodelink);
+ nl->minode = i;
+ nl->next = sd->leaders;
+ sd->leaders = nl;
+ }
+ }
}
-void schedule_add_flt_use_dep(scheduledata *sd, s4 reg)
+static void schedule_create_graph(scheduledata *sd)
{
minstruction *mi;
- minstruction *defmi;
nodelink *nl;
- s4 defnode;
-
- /* get current machine instruction */
+ s4 i;
- mi = &sd->mi[sd->micount - 1];
+ FILE *file;
- /* get current define dependency instruction */
+ file = fopen("cacao.dot", "w+");
- if ((defnode = sd->fltregs_define_dep[reg]) > 0) {
- /* some edges to current machine instruction -> no leader */
+ fprintf(file, "digraph G {\n");
- mi->leader = false;
+ for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {
+ nl = mi->deps;
- /* add node to dependency list of current define node */
+ if (nl) {
+ while (nl) {
+ s4 priority = mi->priority - sd->mi[nl->minode].priority;
- defmi = &sd->mi[defnode - 1];
+ fprintf(file, "%d -> %d [ label = \"%d\" ]\n", i, nl->minode, priority);
+ nl = nl->next;
+ }
- nl = DNEW(nodelink);
- nl->minode = sd->micount;
- nl->next = defmi->deps;
- defmi->deps = nl;
+ } else {
+ fprintf(file, "%d\n", i);
+ }
}
- /* add node to list of current use nodes */
-
- nl = DNEW(nodelink);
- nl->minode = sd->micount;
- nl->next = sd->fltregs_use_dep[reg];
- sd->fltregs_use_dep[reg] = nl;
-}
-
-
-void schedule_add_memory_define_dep(scheduledata *sd)
-{
-}
-
-
-void schedule_add_memory_use_dep(scheduledata *sd)
-{
+ fprintf(file, "}\n");
+ fclose(file);
}
minstruction *mi;
nodelink *nl;
s4 i;
+ s4 criticalpath;
+
+ /* calculate priorities and critical path */
+
+ schedule_calc_priorities(sd);
printf("bb start ---\n");
- for (i = 1, mi = sd->mi; i <= sd->micount; i++, mi++) {
+ printf("nodes: %d\n", sd->micount);
+
+ printf("leaders: ");
+ criticalpath = 0;
+ nl = sd->leaders;
+ while (nl) {
+ printf("%d ", nl->minode);
+ if (sd->mi[nl->minode].priority > criticalpath)
+ criticalpath = sd->mi[nl->minode].priority;
+ nl = nl->next;
+ }
+ printf("\n");
+
+ printf("critical path: %d\n", criticalpath);
+
+ for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {
disassinstr(&mi->instr);
- printf("\t--> #%d, %d, %d, %d, ", i, mi->latency, mi->priority, mi->leader);
+ printf("\t--> #%d, start=%d, end=%d, prio=%d", i, mi->startcycle, mi->endcycle, mi->priority);
- printf("deps= ");
+ printf(", deps= ");
nl = mi->deps;
while (nl) {
printf("%d ", nl->minode);
printf("\n");
}
printf("bb end ---\n\n");
+
+/* schedule_create_graph(sd); */
}
projects / cacao.git / commitdiff