src/vm/jit/schedule/schedule.c

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