1 /* src/vm/jit/schedule/schedule.c - architecture independent instruction
4 Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
5 C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
6 E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
7 J. Wenninger, Institut f. Computersprachen - TU Wien
9 This file is part of CACAO.
11 This program is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License as
13 published by the Free Software Foundation; either version 2, or (at
14 your option) any later version.
16 This program is distributed in the hope that it will be useful, but
17 WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 General Public License for more details.
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
26 Contact: cacao@cacaojvm.org
28 Authors: Christian Thalinger
43 #include "mm/memory.h"
44 #include "vm/options.h"
45 #include "vm/statistics.h"
46 #include "vm/jit/schedule/schedule.h"
52 scheduledata *schedule_init(methodinfo *m, registerdata *rd)
56 sd = DNEW(scheduledata);
59 (rd->savintregcnt - rd->maxsavintreguse) +
60 (rd->savfltregcnt - rd->maxsavfltreguse) +
62 m->parseddesc->paramcount +
63 1; /* index 0 are all other memory accesses */
65 /* XXX quick hack: just use a fixed number of instructions */
66 sd->mi = DMNEW(minstruction, 20000);
68 sd->intregs_define_dep = DMNEW(edgenode*, rd->intregsnum);
69 sd->fltregs_define_dep = DMNEW(edgenode*, rd->fltregsnum);
71 sd->intregs_use_dep = DMNEW(edgenode*, rd->intregsnum);
72 sd->fltregs_use_dep = DMNEW(edgenode*, rd->fltregsnum);
74 sd->memory_define_dep = DMNEW(edgenode*, stackrange);
75 sd->memory_use_dep = DMNEW(edgenode*, stackrange);
78 /* open graphviz file */
83 file = fopen("cacao.dot", "w+");
84 fprintf(file, "digraph G {\n");
93 void schedule_reset(scheduledata *sd, registerdata *rd)
98 /* set define array to -1, because 0 is a valid node number */
100 MSET(sd->intregs_define_dep, 0, edgenode*, rd->intregsnum);
101 MSET(sd->fltregs_define_dep, 0, edgenode*, rd->fltregsnum);
103 /* clear all use pointers */
105 MSET(sd->intregs_use_dep, 0, edgenode*, rd->intregsnum);
106 MSET(sd->fltregs_use_dep, 0, edgenode*, rd->fltregsnum);
108 MSET(sd->memory_define_dep, 0, edgenode*, stackrange);
109 MSET(sd->memory_use_dep, 0, edgenode*, stackrange);
113 void schedule_close(scheduledata *sd)
120 fprintf(file, "}\n");
127 /* schedule_add_define_dep *****************************************************
131 *******************************************************************************/
133 void schedule_add_define_dep(scheduledata *sd, s1 opnum, edgenode **define_dep, edgenode **use_dep)
144 /* get current machine instruction */
146 minum = sd->micount - 1;
149 /* get current use dependency nodes, if non-null use them... */
151 if ((useen = *use_dep)) {
153 /* Save next pointer so we can link the current node to the */
154 /* machine instructions' dependency list. */
158 /* don't add the current machine instruction (e.g. add A0,A0,A0) */
160 if (useen->minum != minum) {
161 /* some edges to current machine instruction -> no leader */
163 mi->flags &= ~SCHEDULE_LEADER;
165 /* get use machine instruction */
167 usemi = &sd->mi[useen->minum];
169 /* link current use node into dependency list */
171 useen->minum = minum;
172 useen->opnum2 = opnum;
174 /* calculate latency, for define add 1 cycle */
175 useen->latency = (usemi->op[useen->opnum].lastcycle -
176 mi->op[opnum].firstcycle) + 1;
178 useen->next = usemi->deps;
185 /* ...otherwise use last define dependency, if non-null */
186 } else if ((defen = *define_dep)) {
187 /* some edges to current machine instruction -> no leader */
189 mi->flags &= ~SCHEDULE_LEADER;
191 /* get last define machine instruction */
193 defmi = &sd->mi[defen->minum];
195 /* link current define node into dependency list */
197 defen->minum = minum;
198 defen->opnum2 = opnum;
200 /* calculate latency, for define add 1 cycle */
201 defen->latency = (defmi->op[defen->opnum].lastcycle -
202 mi->op[opnum].firstcycle) + 1;
204 defen->next = defmi->deps;
208 /* Set current instruction as new define dependency and clear use */
220 /* schedule_add_use_dep ********************************************************
224 *******************************************************************************/
226 void schedule_add_use_dep(scheduledata *sd, s1 opnum, edgenode **define_dep, edgenode **use_dep)
234 /* get current machine instruction */
236 minum = sd->micount - 1;
239 /* get current define dependency instruction */
241 if ((defen = *define_dep)) {
242 /* some edges to current machine instruction -> no leader */
244 mi->flags &= ~SCHEDULE_LEADER;
246 /* add node to dependency list of current define node */
248 defmi = &sd->mi[defen->minum];
252 en->opnum = defen->opnum;
255 /* calculate latency */
256 en->latency = (defmi->op[defen->opnum].lastcycle -
257 mi->op[opnum].firstcycle);
259 en->next = defmi->deps;
263 /* add node to list of current use nodes */
273 /* schedule_calc_priorities ****************************************************
275 Calculates the current node's priority by getting highest priority
276 of the dependency nodes, adding this nodes latency plus 1 (for the
279 *******************************************************************************/
281 void schedule_calc_priorities(scheduledata *sd)
284 minstruction *lastmi;
294 /* last node MUST always be the last instruction scheduled */
296 lastnode = sd->micount - 1;
298 /* if last instruction is the first instruction, skip everything */
301 lastmi = &sd->mi[lastnode];
303 /* last instruction is no leader */
305 lastmi->flags &= ~SCHEDULE_LEADER;
307 /* last instruction has no dependencies, use virtual sink node */
311 for (j = 0; j < 4; j++) {
312 if (lastmi->op[j].lastcycle > lastcycle)
313 lastcycle = lastmi->op[j].lastcycle;
316 #define EARLIEST_USE_CYCLE 3
317 lastmi->priority = (lastcycle - EARLIEST_USE_CYCLE) + 1;
320 /* walk through all remaining machine instructions backwards */
322 for (i = lastnode - 1, mi = &sd->mi[lastnode - 1]; i >= 0; i--, mi--) {
330 /* walk through depedencies and calculate highest latency */
333 priority = sd->mi[en->minum].priority;
335 currentpath = en->latency + priority;
337 if (currentpath > criticalpath)
338 criticalpath = currentpath;
343 /* set priority to critical path */
345 mi->priority = criticalpath;
348 /* no dependencies, use virtual sink node */
352 for (j = 0; j < 4; j++) {
353 if (mi->op[j].lastcycle > lastcycle)
354 lastcycle = mi->op[j].lastcycle;
357 mi->priority = (lastcycle - EARLIEST_USE_CYCLE);
360 /* add current machine instruction to leader list, if one */
362 if (mi->flags & SCHEDULE_LEADER) {
365 en->next = sd->leaders;
371 /* last node is first instruction, add to leader list */
374 en->minum = lastnode;
375 en->next = sd->leaders;
381 static void schedule_create_graph(scheduledata *sd, s4 criticalpath)
392 fprintf(file, "subgraph cluster_%d {\n", bb);
393 fprintf(file, "label = \"BB%d (nodes: %d, critical path: %d)\"\n", bb, sd->micount, criticalpath);
395 for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {
401 fprintf(file, "\"#%d.%d ", bb, i);
402 disassinstr(file, &mi->instr);
403 fprintf(file, "\\np=%d\"", mi->priority);
405 fprintf(file, " -> ");
407 fprintf(file, "\"#%d.%d ", bb, en->minum);
408 disassinstr(file, &sd->mi[en->minum].instr);
409 fprintf(file, "\\np=%d\"", sd->mi[en->minum].priority);
411 fprintf(file, " [ label = \"%d\" ]\n", en->latency);
416 fprintf(file, "\"#%d.%d ", bb, i);
417 disassinstr(file, &mi->instr);
418 fprintf(file, "\\np=%d\"", mi->priority);
420 fprintf(file, " -> ");
422 fprintf(file, "\"end %d\"", bb);
424 fprintf(file, " [ label = \"%d\" ]\n", mi->priority);
430 fprintf(file, "}\n");
436 /* schedule_add_deps_to_leaders ************************************************
438 Walk through all dependencies, change the starttime and add the
439 node to the leaders list.
441 *******************************************************************************/
443 static void schedule_add_deps_to_leaders(scheduledata *sd, edgenode *deps, s4 time)
448 if ((depen = deps)) {
450 /* set starttime of instruction */
452 sd->mi[depen->minum].starttime = time + depen->latency;
454 /* save last entry */
461 /* add dependencies to front of the list */
463 preven->next = sd->leaders;
469 /* schedule_do_schedule ********************************************************
473 *******************************************************************************/
475 void schedule_do_schedule(scheduledata *sd)
497 /* It may be possible that no instructions are in the current basic block */
498 /* because after an branch instruction the instructions are scheduled. */
500 if (sd->micount > 0) {
501 /* calculate priorities and critical path */
503 schedule_calc_priorities(sd);
506 printf("bb start ---\n");
507 printf("nodes: %d\n", sd->micount);
517 printf("#%d ", en->minum);
521 if (sd->mi[en->minum].priority > criticalpath)
522 criticalpath = sd->mi[en->minum].priority;
526 /* check last node for critical path (e.g. ret) */
528 if (sd->mi[sd->micount - 1].priority > criticalpath)
529 criticalpath = sd->mi[sd->micount - 1].priority;
533 printf("critical path: %d\n", criticalpath);
535 for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {
536 disassinstr(stdout, &mi->instr);
538 printf("\t--> #%d, prio=%d", i, mi->priority);
540 printf(", mem=%d:%d", mi->op[0].firstcycle, mi->op[0].lastcycle);
542 for (j = 1; j <= 3; j++) {
543 printf(", op%d=%d:%d", j, mi->op[j].firstcycle, mi->op[j].lastcycle);
549 printf("#%d (op%d->op%d: %d) ", en->minum, en->opnum, en->opnum2, en->latency);
554 printf("bb end ---\n\n");
556 schedule_create_graph(sd, criticalpath);
560 /* set start time to zero */
562 printf("\n\nschedule start ---\n");
566 while (sd->leaders) {
567 /* XXX argh! how to make this portable? */
568 for (j = 0; j < 2; j++ ) {
580 printf("\n\nleaders: ");
582 /* get current machine instruction from leader list */
584 mi = &sd->mi[en->minum];
585 disassinstr(stdout, &mi->instr);
588 /* starttime reached */
590 if (mi->starttime <= time) {
592 /* check for a suitable ALU instruction */
594 if ((mi->flags & SCHEDULE_UNIT_ALU) &&
595 (!alumi || (mi->priority > alumi->priority))) {
596 /* remove/replace current node from leaders list */
600 preven->next = aluen;
601 aluen->next = en->next;
603 preven->next = en->next;
608 aluen->next = en->next;
610 sd->leaders = en->next;
613 /* set current ALU instruction and node */
618 /* check for a suitable MEM instruction */
620 } else if ((mi->flags & SCHEDULE_UNIT_MEM) &&
621 (!memmi || (mi->priority > memmi->priority))) {
624 preven->next = memen;
625 memen->next = en->next;
627 preven->next = en->next;
632 memen->next = en->next;
634 sd->leaders = en->next;
640 /* check for a suitable BRANCH instruction */
642 } else if ((mi->flags & SCHEDULE_UNIT_BRANCH) &&
643 (!brmi || (mi->priority > brmi->priority))) {
645 preven->next = en->next;
647 sd->leaders = en->next;
656 /* not leader removed, save next previous node */
665 /* schedule ALU instruction, if one was found */
668 mi = &sd->mi[aluen->minum];
670 disassinstr(stdout, &mi->instr);
674 schedule_add_deps_to_leaders(sd, mi->deps, time);
677 /* schedule MEM instruction, if one was found */
680 mi = &sd->mi[memen->minum];
682 disassinstr(stdout, &mi->instr);
686 schedule_add_deps_to_leaders(sd, mi->deps, time);
689 /* schedule BRANCH instruction, if one was found */
692 mi = &sd->mi[bren->minum];
694 disassinstr(stdout, &brmi->instr);
698 schedule_add_deps_to_leaders(sd, mi->deps, time);
701 if (!aluen && !memen && !bren) {
708 /* bundle finished, increase execution time */
712 printf("schedule end ---\n\n");
714 #if defined(ENABLE_STATISTICS)
716 count_schedule_basic_blocks++;
717 count_schedule_nodes += sd->micount;
718 count_schedule_leaders += leaders;
720 if (leaders > count_schedule_max_leaders)
721 count_schedule_max_leaders = leaders;
723 count_schedule_critical_path += criticalpath;
731 * These are local overrides for various environment variables in Emacs.
732 * Please do not remove this and leave it at the end of the file, where
733 * Emacs will automagically detect them.
734 * ---------------------------------------------------------------------
737 * indent-tabs-mode: t