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