src/vm/jit/schedule/schedule.c

   1 /* src/vm/jit/schedule/schedule.c - architecture independent instruction
   2                                     scheduler
   3
   4    Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   5    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   6    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   7    Institut f. Computersprachen - TU Wien
   8
   9    This file is part of CACAO.
  10
  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.
  15
  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.
  20
  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., 59 Temple Place - Suite 330, Boston, MA
  24    02111-1307, USA.
  25
  26    Contact: cacao@complang.tuwien.ac.at
  27
  28    Authors: Christian Thalinger
  29
  30    Changes:
  31
  32    $Id: schedule.c 2056 2005-03-22 11:21:32Z twisti $
  33
  34 */
  35
  36
  37 #include <stdio.h>
  38
  39 #include "config.h"
  40 #include "disass.h"
  41
  42 #include "mm/memory.h"
  43 #include "vm/options.h"
  44 #include "vm/statistics.h"
  45 #include "vm/jit/schedule/schedule.h"
  46
  47
  48 /* XXX quick hack */
  49 s4 stackrange;
  50
  51 scheduledata *schedule_init(methodinfo *m, registerdata *rd)
  52 {
  53         scheduledata *sd;
  54
  55         sd = DNEW(scheduledata);
  56
  57         stackrange =
  58                 (rd->savintregcnt - rd->maxsavintreguse) +
  59                 (rd->savfltregcnt - rd->maxsavfltreguse) +
  60                 rd->maxmemuse +
  61                 m->paramcount +
  62                 1;                           /* index 0 are all other memory accesses */
  63
  64         /* XXX quick hack: just use a fixed number of instructions */
  65         sd->mi = DMNEW(minstruction, 20000);
  66
  67         sd->intregs_define_dep = DMNEW(edgenode*, rd->intregsnum);
  68         sd->fltregs_define_dep = DMNEW(edgenode*, rd->fltregsnum);
  69
  70         sd->intregs_use_dep = DMNEW(edgenode*, rd->intregsnum);
  71         sd->fltregs_use_dep = DMNEW(edgenode*, rd->fltregsnum);
  72
  73         sd->memory_define_dep = DMNEW(edgenode*, stackrange);
  74         sd->memory_use_dep = DMNEW(edgenode*, stackrange);
  75
  76
  77         /* open graphviz file */
  78
  79         if (opt_verbose) {
  80                 FILE *file;
  81
  82                 file = fopen("cacao.dot", "w+");
  83                 fprintf(file, "digraph G {\n");
  84
  85                 sd->file = file;
  86         }
  87
  88         return sd;
  89 }
  90
  91
  92 void schedule_reset(scheduledata *sd, registerdata *rd)
  93 {
  94         sd->micount = 0;
  95         sd->leaders = NULL;
  96
  97         /* set define array to -1, because 0 is a valid node number */
  98
  99         MSET(sd->intregs_define_dep, 0, edgenode*, rd->intregsnum);
 100         MSET(sd->fltregs_define_dep, 0, edgenode*, rd->fltregsnum);
 101
 102         /* clear all use pointers */
 103
 104         MSET(sd->intregs_use_dep, 0, edgenode*, rd->intregsnum);
 105         MSET(sd->fltregs_use_dep, 0, edgenode*, rd->fltregsnum);
 106
 107         MSET(sd->memory_define_dep, 0, edgenode*, stackrange);
 108         MSET(sd->memory_use_dep, 0, edgenode*, stackrange);
 109 }
 110
 111
 112 void schedule_close(scheduledata *sd)
 113 {
 114         if (opt_verbose) {
 115                 FILE *file;
 116
 117                 file = sd->file;
 118
 119                 fprintf(file, "}\n");
 120                 fclose(file);
 121         }
 122 }
 123
 124
 125
 126 /* schedule_add_define_dep *****************************************************
 127
 128    XXX
 129
 130 *******************************************************************************/
 131
 132 void schedule_add_define_dep(scheduledata *sd, s1 opnum, edgenode **define_dep, edgenode **use_dep)
 133 {
 134         minstruction *mi;
 135         minstruction *defmi;
 136         minstruction *usemi;
 137         edgenode     *en;
 138         edgenode     *useen;
 139         edgenode     *defen;
 140         edgenode     *tmpen;
 141         s4            minum;
 142
 143         /* get current machine instruction */
 144
 145         minum = sd->micount - 1;
 146         mi = &sd->mi[minum];
 147
 148         /* get current use dependency nodes, if non-null use them... */
 149
 150         if ((useen = *use_dep)) {
 151                 while (useen) {
 152                         /* Save next pointer so we can link the current node to the       */
 153                         /* machine instructions' dependency list.                         */
 154
 155                         tmpen = useen->next;
 156
 157                         /* don't add the current machine instruction (e.g. add A0,A0,A0) */
 158
 159                         if (useen->minum != minum) {
 160                                 /* some edges to current machine instruction -> no leader */
 161
 162                                 mi->flags &= ~SCHEDULE_LEADER;
 163
 164                                 /* get use machine instruction */
 165
 166                                 usemi = &sd->mi[useen->minum];
 167
 168                                 /* link current use node into dependency list */
 169
 170                                 useen->minum = minum;
 171                                 useen->opnum2 = opnum;
 172
 173                                 /* calculate latency, for define add 1 cycle */
 174                                 useen->latency = (usemi->op[useen->opnum].lastcycle -
 175                                                                   mi->op[opnum].firstcycle) + 1;
 176
 177                                 useen->next = usemi->deps;
 178                                 usemi->deps = useen;
 179                         }
 180
 181                         useen = tmpen;
 182                 }
 183
 184                 /* ...otherwise use last define dependency, if non-null */
 185         } else if ((defen = *define_dep)) {
 186                 /* some edges to current machine instruction -> no leader */
 187
 188                 mi->flags &= ~SCHEDULE_LEADER;
 189
 190                 /* get last define machine instruction */
 191
 192                 defmi = &sd->mi[defen->minum];
 193
 194                 /* link current define node into dependency list */
 195
 196                 defen->minum = minum;
 197                 defen->opnum2 = opnum;
 198
 199                 /* calculate latency, for define add 1 cycle */
 200                 defen->latency = (defmi->op[defen->opnum].lastcycle -
 201                                                   mi->op[opnum].firstcycle) + 1;
 202
 203                 defen->next = defmi->deps;
 204                 defmi->deps = defen;
 205         }
 206
 207         /* Set current instruction as new define dependency and clear use         */
 208         /* dependencies.                                                          */
 209
 210         en = DNEW(edgenode);
 211         en->minum = minum;
 212         en->opnum = opnum;
 213
 214         *define_dep = en;
 215         *use_dep = NULL;
 216 }
 217
 218
 219 /* schedule_add_use_dep ********************************************************
 220
 221    XXX
 222
 223 *******************************************************************************/
 224
 225 void schedule_add_use_dep(scheduledata *sd, s1 opnum, edgenode **define_dep, edgenode **use_dep)
 226 {
 227         minstruction *mi;
 228         minstruction *defmi;
 229         edgenode     *en;
 230         edgenode     *defen;
 231         s4            minum;
 232
 233         /* get current machine instruction */
 234
 235         minum = sd->micount - 1;
 236         mi = &sd->mi[minum];
 237
 238         /* get current define dependency instruction */
 239
 240         if ((defen = *define_dep)) {
 241                 /* some edges to current machine instruction -> no leader */
 242
 243                 mi->flags &= ~SCHEDULE_LEADER;
 244
 245                 /* add node to dependency list of current define node */
 246
 247                 defmi = &sd->mi[defen->minum];
 248
 249                 en = DNEW(edgenode);
 250                 en->minum = minum;
 251                 en->opnum = defen->opnum;
 252                 en->opnum2 = opnum;
 253
 254                 /* calculate latency */
 255                 en->latency = (defmi->op[defen->opnum].lastcycle -
 256                                            mi->op[opnum].firstcycle);
 257
 258                 en->next = defmi->deps;
 259                 defmi->deps = en;
 260         }
 261
 262         /* add node to list of current use nodes */
 263
 264         en = DNEW(edgenode);
 265         en->minum = minum;
 266         en->opnum = opnum;
 267         en->next = *use_dep;
 268         *use_dep = en;
 269 }
 270
 271
 272 /* schedule_calc_priorities ****************************************************
 273
 274    Calculates the current node's priority by getting highest priority
 275    of the dependency nodes, adding this nodes latency plus 1 (for the
 276    instruction itself).
 277
 278 *******************************************************************************/
 279
 280 void schedule_calc_priorities(scheduledata *sd)
 281 {
 282         minstruction *mi;
 283         minstruction *lastmi;
 284         edgenode     *en;
 285         s4            lastnode;
 286         s4            i;
 287         s4            j;
 288         s4            criticalpath;
 289         s4            currentpath;
 290         s1            lastcycle;
 291
 292
 293         /* last node MUST always be the last instruction scheduled */
 294
 295         lastnode = sd->micount - 1;
 296
 297         /* if last instruction is the first instruction, skip everything */
 298
 299         if (lastnode > 0) {
 300                 lastmi = &sd->mi[lastnode];
 301
 302                 /* last instruction is no leader */
 303
 304                 lastmi->flags &= ~SCHEDULE_LEADER;
 305
 306                 /* last instruction has no dependencies, use virtual sink node */
 307
 308                 lastcycle = 0;
 309
 310                 for (j = 0; j < 4; j++) {
 311                         if (lastmi->op[j].lastcycle > lastcycle)
 312                                 lastcycle = lastmi->op[j].lastcycle;
 313                 }
 314
 315 #define EARLIEST_USE_CYCLE 3
 316                 lastmi->priority = (lastcycle - EARLIEST_USE_CYCLE) + 1;
 317
 318
 319                 /* walk through all remaining machine instructions backwards */
 320
 321                 for (i = lastnode - 1, mi = &sd->mi[lastnode - 1]; i >= 0; i--, mi--) {
 322                         en = mi->deps;
 323
 324                         if (en) {
 325                                 s4 priority;
 326
 327                                 criticalpath = 0;
 328
 329                                 /* walk through depedencies and calculate highest latency */
 330
 331                                 while (en) {
 332                                         priority = sd->mi[en->minum].priority;
 333
 334                                         currentpath = en->latency + priority;
 335
 336                                         if (currentpath > criticalpath)
 337                                                 criticalpath = currentpath;
 338
 339                                         en = en->next;
 340                                 }
 341
 342                                 /* set priority to critical path */
 343
 344                                 mi->priority = criticalpath;
 345
 346                         } else {
 347                                 /* no dependencies, use virtual sink node */
 348
 349                                 lastcycle = 0;
 350
 351                                 for (j = 0; j < 4; j++) {
 352                                         if (mi->op[j].lastcycle > lastcycle)
 353                                                 lastcycle = mi->op[j].lastcycle;
 354                                 }
 355
 356                                 mi->priority = (lastcycle - EARLIEST_USE_CYCLE);
 357                         }
 358
 359                         /* add current machine instruction to leader list, if one */
 360
 361                         if (mi->flags & SCHEDULE_LEADER) {
 362                                 en = DNEW(edgenode);
 363                                 en->minum = i;
 364                                 en->next = sd->leaders;
 365                                 sd->leaders = en;
 366                         }
 367                 }
 368
 369         } else {
 370                 /* last node is first instruction, add to leader list */
 371
 372                 en = DNEW(edgenode);
 373                 en->minum = lastnode;
 374                 en->next = sd->leaders;
 375                 sd->leaders = en;
 376         }
 377 }
 378
 379
 380 static void schedule_create_graph(scheduledata *sd, s4 criticalpath)
 381 {
 382         minstruction *mi;
 383         edgenode     *en;
 384         s4            i;
 385
 386         FILE *file;
 387         static int bb = 1;
 388
 389         file = sd->file;
 390
 391         fprintf(file, "subgraph cluster_%d {\n", bb);
 392         fprintf(file, "label = \"BB%d (nodes: %d, critical path: %d)\"\n", bb, sd->micount, criticalpath);
 393
 394         for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {
 395
 396                 en = mi->deps;
 397
 398                 if (en) {
 399                         while (en) {
 400                                 fprintf(file, "\"#%d.%d ", bb, i);
 401                                 disassinstr(file, &mi->instr);
 402                                 fprintf(file, "\\np=%d\"", mi->priority);
 403
 404                                 fprintf(file, " -> ");
 405
 406                                 fprintf(file, "\"#%d.%d ", bb, en->minum);
 407                                 disassinstr(file, &sd->mi[en->minum].instr);
 408                                 fprintf(file, "\\np=%d\"", sd->mi[en->minum].priority);
 409
 410                                 fprintf(file, " [ label = \"%d\" ]\n", en->latency);
 411                                 en = en->next;
 412                         }
 413
 414                 } else {
 415                         fprintf(file, "\"#%d.%d ", bb, i);
 416                         disassinstr(file, &mi->instr);
 417                         fprintf(file, "\\np=%d\"", mi->priority);
 418
 419                         fprintf(file, " -> ");
 420
 421                         fprintf(file, "\"end %d\"", bb);
 422
 423                         fprintf(file, " [ label = \"%d\" ]\n", mi->priority);
 424
 425                         fprintf(file, "\n");
 426                 }
 427         }
 428
 429         fprintf(file, "}\n");
 430
 431         bb++;
 432 }
 433
 434
 435 /* schedule_add_deps_to_leaders ************************************************
 436
 437    Walk through all dependencies, change the starttime and add the
 438    node to the leaders list.
 439
 440 *******************************************************************************/
 441
 442 static void schedule_add_deps_to_leaders(scheduledata *sd, edgenode *deps, s4 time)
 443 {
 444         edgenode *depen;
 445         edgenode *preven;
 446
 447         if ((depen = deps)) {
 448                 while (depen) {
 449                         /* set starttime of instruction */
 450
 451                         sd->mi[depen->minum].starttime = time + depen->latency;
 452
 453                         /* save last entry */
 454
 455                         preven = depen;
 456
 457                         depen = depen->next;
 458                 }
 459
 460                 /* add dependencies to front of the list */
 461
 462                 preven->next = sd->leaders;
 463                 sd->leaders = deps;
 464         }
 465 }
 466
 467
 468 /* schedule_do_schedule ********************************************************
 469
 470    XXX
 471
 472 *******************************************************************************/
 473
 474 void schedule_do_schedule(scheduledata *sd)
 475 {
 476         minstruction *mi;
 477         edgenode     *en;
 478         s4            i;
 479         s4            j;
 480         s4            leaders;
 481         s4            criticalpath;
 482         s4            time;
 483         s4            schedulecount;
 484
 485         minstruction *alumi;
 486         minstruction *memmi;
 487         minstruction *brmi;
 488
 489         edgenode     *preven;
 490         edgenode     *depen;
 491
 492         edgenode     *aluen;
 493         edgenode     *memen;
 494         edgenode     *bren;
 495
 496         /* It may be possible that no instructions are in the current basic block */
 497         /* because after an branch instruction the instructions are scheduled.    */
 498
 499         if (sd->micount > 0) {
 500                 /* calculate priorities and critical path */
 501
 502                 schedule_calc_priorities(sd);
 503
 504                 if (opt_verbose) {
 505                         printf("bb start ---\n");
 506                         printf("nodes: %d\n", sd->micount);
 507                         printf("leaders: ");
 508                 }
 509
 510                 leaders = 0;
 511                 criticalpath = 0;
 512
 513                 en = sd->leaders;
 514                 while (en) {
 515                         if (opt_verbose) {
 516                                 printf("#%d ", en->minum);
 517                         }
 518
 519                         leaders++;
 520                         if (sd->mi[en->minum].priority > criticalpath)
 521                                 criticalpath = sd->mi[en->minum].priority;
 522                         en = en->next;
 523                 }
 524
 525                 /* check last node for critical path (e.g. ret) */
 526
 527                 if (sd->mi[sd->micount - 1].priority > criticalpath)
 528                         criticalpath = sd->mi[sd->micount - 1].priority;
 529
 530                 if (opt_verbose) {
 531                         printf("\n");
 532                         printf("critical path: %d\n", criticalpath);
 533
 534                         for (i = 0, mi = sd->mi; i < sd->micount; i++, mi++) {
 535                                 disassinstr(stdout, &mi->instr);
 536
 537                                 printf("\t--> #%d, prio=%d", i, mi->priority);
 538
 539                                 printf(", mem=%d:%d", mi->op[0].firstcycle, mi->op[0].lastcycle);
 540
 541                                 for (j = 1; j <= 3; j++) {
 542                                         printf(", op%d=%d:%d", j, mi->op[j].firstcycle, mi->op[j].lastcycle);
 543                                 }
 544
 545                                 printf(", deps= ");
 546                                 en = mi->deps;
 547                                 while (en) {
 548                                         printf("#%d (op%d->op%d: %d) ", en->minum, en->opnum, en->opnum2, en->latency);
 549                                         en = en->next;
 550                                 }
 551                                 printf("\n");
 552                         }
 553                         printf("bb end ---\n\n");
 554
 555                         schedule_create_graph(sd, criticalpath);
 556                 }
 557
 558
 559                 /* set start time to zero */
 560
 561                 printf("\n\nschedule start ---\n");
 562                 time = 0;
 563                 schedulecount = 0;
 564
 565                 while (sd->leaders) {
 566                         /* XXX argh! how to make this portable? */
 567                         for (j = 0; j < 2; j++ ) {
 568                                 en = sd->leaders;
 569                                 preven = NULL;
 570
 571                                 alumi = NULL;
 572                                 memmi = NULL;
 573                                 brmi = NULL;
 574
 575                                 aluen = NULL;
 576                                 memen = NULL;
 577                                 bren = NULL;
 578
 579                                 printf("\n\nleaders: ");
 580                                 while (en) {
 581                                         /* get current machine instruction from leader list */
 582
 583                                         mi = &sd->mi[en->minum];
 584                                         disassinstr(stdout, &mi->instr);
 585                                         printf(", ");
 586
 587                                         /* starttime reached */
 588
 589                                         if (mi->starttime <= time) {
 590
 591                                                 /* check for a suitable ALU instruction */
 592
 593                                                 if ((mi->flags & SCHEDULE_UNIT_ALU) &&
 594                                                         (!alumi || (mi->priority > alumi->priority))) {
 595                                                         /* remove/replace current node from leaders list */
 596
 597                                                         if (preven)
 598                                                                 if (alumi) {
 599                                                                         preven->next = aluen;
 600                                                                         aluen->next = en->next;
 601                                                                 } else {
 602                                                                         preven->next = en->next;
 603                                                                 }
 604                                                         else
 605                                                                 if (alumi) {
 606                                                                         sd->leaders = aluen;
 607                                                                         aluen->next = en->next;
 608                                                                 } else {
 609                                                                         sd->leaders = en->next;
 610                                                                 }
 611
 612                                                         /* set current ALU instruction and node */
 613
 614                                                         alumi = mi;
 615                                                         aluen = en;
 616
 617                                                 /* check for a suitable MEM instruction */
 618
 619                                                 } else if ((mi->flags & SCHEDULE_UNIT_MEM) &&
 620                                                                    (!memmi || (mi->priority > memmi->priority))) {
 621                                                         if (preven)
 622                                                                 if (memmi) {
 623                                                                         preven->next = memen;
 624                                                                         memen->next = en->next;
 625                                                                 } else {
 626                                                                         preven->next = en->next;
 627                                                                 }
 628                                                         else
 629                                                                 if (memmi) {
 630                                                                         sd->leaders = memen;
 631                                                                         memen->next = en->next;
 632                                                                 } else {
 633                                                                         sd->leaders = en->next;
 634                                                                 }
 635
 636                                                         memmi = mi;
 637                                                         memen = en;
 638
 639                                                 /* check for a suitable BRANCH instruction */
 640
 641                                                 } else if ((mi->flags & SCHEDULE_UNIT_BRANCH) &&
 642                                                                    (!brmi || (mi->priority > brmi->priority))) {
 643                                                         if (preven)
 644                                                                 preven->next = en->next;
 645                                                         else
 646                                                                 sd->leaders = en->next;
 647
 648                                                         memmi = mi;
 649                                                         memen = en;
 650
 651                                                 } else
 652                                                         preven = en;
 653
 654                                         } else {
 655                                                 /* not leader removed, save next previous node */
 656
 657                                                 preven = en;
 658                                         }
 659
 660                                         en = en->next;
 661                                 }
 662                                 printf("\n");
 663
 664                                 /* schedule ALU instruction, if one was found */
 665
 666                                 if (aluen) {
 667                                         mi = &sd->mi[aluen->minum];
 668
 669                                         disassinstr(stdout, &mi->instr);
 670                                         printf(" || ");
 671
 672                                         schedulecount++;
 673                                         schedule_add_deps_to_leaders(sd, mi->deps, time);
 674                                 }
 675
 676                                 /* schedule MEM instruction, if one was found */
 677
 678                                 if (memen) {
 679                                         mi = &sd->mi[memen->minum];
 680
 681                                         disassinstr(stdout, &mi->instr);
 682                                         printf(" || ");
 683
 684                                         schedulecount++;
 685                                         schedule_add_deps_to_leaders(sd, mi->deps, time);
 686                                 }
 687
 688                                 /* schedule BRANCH instruction, if one was found */
 689
 690                                 if (bren) {
 691                                         mi = &sd->mi[bren->minum];
 692
 693                                         disassinstr(stdout, &brmi->instr);
 694                                         printf(" || ");
 695
 696                                         schedulecount++;
 697                                         schedule_add_deps_to_leaders(sd, mi->deps, time);
 698                                 }
 699
 700                                 if (!aluen && !memen && !bren) {
 701                                         printf("nop");
 702                                         printf(" || ");
 703                                 }
 704                         }
 705                         printf("\n");
 706
 707                         /* bundle finished, increase execution time */
 708
 709                         time++;
 710                 }
 711                 printf("schedule end ---\n\n");
 712
 713 #if defined(STATISTICS)
 714                 if (opt_stat) {
 715                         count_schedule_basic_blocks++;
 716                         count_schedule_nodes += sd->micount;
 717                         count_schedule_leaders += leaders;
 718
 719                         if (leaders > count_schedule_max_leaders)
 720                                 count_schedule_max_leaders = leaders;
 721
 722                         count_schedule_critical_path += criticalpath;
 723                 }
 724 #endif
 725         }
 726 }
 727
 728
 729 /*
 730  * These are local overrides for various environment variables in Emacs.
 731  * Please do not remove this and leave it at the end of the file, where
 732  * Emacs will automagically detect them.
 733  * ---------------------------------------------------------------------
 734  * Local variables:
 735  * mode: c
 736  * indent-tabs-mode: t
 737  * c-basic-offset: 4
 738  * tab-width: 4
 739  * End:
 740  */