-/* 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,
- C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
- Institut f. Computersprachen - TU Wien
+ 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.
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., 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA.
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.
- Contact: cacao@complang.tuwien.ac.at
+ Contact: cacao@cacaojvm.org
Authors: Christian Thalinger
Changes:
- $Id: schedule.c 1966 2005-02-24 23:39:12Z twisti $
-
*/
+#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"
-scheduledata *schedule_init(registerdata *rd)
+/* XXX quick hack */
+s4 stackrange;
+
+scheduledata *schedule_init(methodinfo *m, registerdata *rd)
{
scheduledata *sd;
sd = DNEW(scheduledata);
- /* XXX quick hack: just use a fix number of instructions */
- sd->mi = DMNEW(minstruction, 100);
+ 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_read_dep = DMNEW(minstruction*, rd->intregsnum);
- sd->intregs_write_dep = DMNEW(minstruction*, rd->intregsnum);
+ sd->intregs_use_dep = DMNEW(edgenode*, rd->intregsnum);
+ sd->fltregs_use_dep = DMNEW(edgenode*, rd->fltregsnum);
- sd->fltregs_read_dep = DMNEW(minstruction*, rd->fltregsnum);
- sd->fltregs_write_dep = DMNEW(minstruction*, rd->fltregsnum);
+ sd->memory_define_dep = DMNEW(edgenode*, stackrange);
+ sd->memory_use_dep = DMNEW(edgenode*, stackrange);
- /* XXX: memory is currently only one cell */
-/* sd->memory_write_dep; */
- /* clear all pointers */
+ /* open graphviz file */
- MSET(sd->intregs_read_dep, 0, minstruction*, rd->intregsnum);
- MSET(sd->intregs_write_dep, 0, minstruction*, rd->intregsnum);
+ if (opt_verbose) {
+ FILE *file;
- MSET(sd->fltregs_read_dep, 0, minstruction*, rd->fltregsnum);
- MSET(sd->fltregs_write_dep, 0, minstruction*, rd->fltregsnum);
+ file = fopen("cacao.dot", "w+");
+ fprintf(file, "digraph G {\n");
- sd->memory_write_dep = NULL;
+ sd->file = file;
+ }
return sd;
}
-minstruction *schedule_prepend_minstruction(minstruction *mi)
+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 *tmpmi;
+ minstruction *mi;
+ minstruction *defmi;
+ edgenode *en;
+ edgenode *defen;
+ s4 minum;
- /* add new instruction in front of the list */
+ /* get current machine instruction */
- tmpmi = DNEW(minstruction);
+ minum = sd->micount - 1;
+ mi = &sd->mi[minum];
- tmpmi->latency = 0;
- tmpmi->priority = 0;
- tmpmi->opdep[0] = NULL;
- tmpmi->opdep[1] = NULL;
- tmpmi->opdep[2] = NULL;
+ /* get current define dependency instruction */
- tmpmi->next = mi; /* link to next instruction */
+ if ((defen = *define_dep)) {
+ /* some edges to current machine instruction -> no leader */
- return tmpmi;
+ 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_priority ******************************************************
+/* 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
*******************************************************************************/
-void schedule_calc_priority(minstruction *mi)
+void schedule_calc_priorities(scheduledata *sd)
{
- s4 i;
- s4 pathpriority;
+ 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 */
- /* check all dependencies for their priority */
+ if (lastnode > 0) {
+ lastmi = &sd->mi[lastnode];
- pathpriority = 0;
+ /* last instruction is no leader */
- for (i = 0; i < 3; i++) {
- if (mi->opdep[i]) {
- if (mi->opdep[i]->priority > pathpriority)
- pathpriority = mi->opdep[i]->priority;
+ 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;
- mi->priority = pathpriority + mi->latency + 1;
+ 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;
+ }
}
*******************************************************************************/
-void schedule_do_schedule(minstruction *mi)
+void schedule_do_schedule(scheduledata *sd)
{
- minstruction *rootmi;
+ 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: ");
+ }
- /* initialize variables */
+ leaders = 0;
+ criticalpath = 0;
- rootmi = mi;
+ 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;
+ }
- printf("bb start ---\n");
+ /* check last node for critical path (e.g. ret) */
- mi = rootmi;
+ 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);
- while (mi) {
- printf("%p: ", mi);
+ for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {
+ disassinstr(stdout, &mi->instr);
-/* disassinstr(&tmpmi->instr); */
- printf("%05x", mi->instr);
+ printf("\t--> #%d, prio=%d", i, mi->priority);
- printf(" --> %d, %d: op1=%p, op2=%p, op3=%p\n", mi->latency, mi->priority, mi->opdep[0], mi->opdep[1], mi->opdep[2]);
+ printf(", mem=%d:%d", mi->op[0].firstcycle, mi->op[0].lastcycle);
- mi = mi->next;
+ 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
}
- printf("bb end ---\n\n");
}
projects / cacao.git / blobdiff