src/vm/jit/schedule/schedule.c

   1 /* vm/jit/schedule/schedule.c - architecture independent instruction scheduler
   2
   3    Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Thalinger
  28
  29    Changes:
  30
  31    $Id: schedule.c 1973 2005-03-02 16:27:05Z twisti $
  32
  33 */
  34
  35
  36 #include <stdio.h>
  37
  38 #include "disass.h"
  39
  40 #include "mm/memory.h"
  41 #include "vm/jit/schedule/schedule.h"
  42
  43
  44 scheduledata *schedule_init(registerdata *rd)
  45 {
  46         scheduledata *sd;
  47
  48         sd = DNEW(scheduledata);
  49
  50         /* XXX quick hack: just use a fix number of instructions */
  51         sd->mi = DMNEW(minstruction, 100);
  52
  53         sd->micount = 0;
  54
  55         sd->intregs_define_dep = DMNEW(s4, rd->intregsnum);
  56         sd->fltregs_define_dep = DMNEW(s4, rd->fltregsnum);
  57
  58         sd->intregs_use_dep = DMNEW(nodelink*, rd->intregsnum);
  59         sd->fltregs_use_dep = DMNEW(nodelink*, rd->fltregsnum);
  60
  61         /* clear all pointers */
  62
  63         MSET(sd->intregs_define_dep, 0, s4, rd->intregsnum);
  64         MSET(sd->fltregs_define_dep, 0, s4, rd->fltregsnum);
  65
  66         MSET(sd->intregs_use_dep, 0, nodelink*, rd->intregsnum);
  67         MSET(sd->fltregs_use_dep, 0, nodelink*, rd->fltregsnum);
  68
  69         sd->memory_define_dep = NULL;
  70         sd->memory_use_dep = NULL;
  71
  72         return sd;
  73 }
  74
  75
  76 /* schedule_calc_priority ******************************************************
  77
  78    Calculates the current node's priority by getting highest priority
  79    of the dependency nodes, adding this nodes latency plus 1 (for the
  80    instruction itself).
  81
  82 *******************************************************************************/
  83
  84 void schedule_calc_priority(minstruction *mi)
  85 {
  86         s4 i;
  87         s4 pathpriority;
  88
  89         /* check all dependencies for their priority */
  90
  91         pathpriority = 0;
  92
  93         for (i = 0; i < 3; i++) {
  94 /*              if (mi->opdep[i]) { */
  95 /*                      if (mi->opdep[i]->priority > pathpriority) */
  96 /*                              pathpriority = mi->opdep[i]->priority; */
  97 /*              } */
  98         }
  99
 100         mi->priority = pathpriority + mi->latency + 1;
 101 }
 102
 103
 104 void schedule_add_int_define_dep(scheduledata *sd, s4 reg)
 105 {
 106         minstruction *mi;
 107         minstruction *defmi;
 108         minstruction *usemi;
 109         nodelink     *usenl;
 110         nodelink     *tmpnl;
 111         nodelink     *nl;
 112         s4            defnode;
 113         s4            minode;
 114
 115         /* get current machine instruction */
 116
 117         minode = sd->micount;
 118         mi = &sd->mi[minode - 1];
 119
 120         /* get current use dependency nodes, if non-null use them... */
 121
 122         if ((usenl = sd->intregs_use_dep[reg])) {
 123                 /* add a dependency link node to all use dependency nodes */
 124
 125                 while (usenl) {
 126                         tmpnl = usenl->next;
 127
 128                         /* don't add to the current machine instruction */
 129
 130                         if (usenl->minode != minode) {
 131                                 /* some edges to current machine instruction -> no leader */
 132
 133                                 mi->leader = false;
 134
 135                                 /* get use machine instruction */
 136
 137                                 usemi = &sd->mi[usenl->minode - 1];
 138
 139 /*                              nl = DNEW(nodelink); */
 140 /*                              nl->minode = sd->micount; */
 141 /*                              nl->next = usemi->deps; */
 142 /*                              usemi->deps = nl; */
 143
 144                                 usenl->minode = minode;
 145                                 usenl->next = usemi->deps;
 146                                 usemi->deps = usenl;
 147                         }
 148
 149                         usenl = tmpnl;
 150                 }
 151
 152         } else {
 153                 /* ...otherwise use last define dependency, if non-null */
 154
 155                 if ((defnode = sd->intregs_define_dep[reg]) > 0) {
 156                         /* some edges to current machine instruction -> no leader */
 157
 158                         mi->leader = false;
 159
 160                         /* get last define machine instruction */
 161
 162                         defmi = &sd->mi[defnode - 1];
 163
 164                         nl = DNEW(nodelink);
 165                         nl->minode = sd->micount;
 166                         nl->next = defmi->deps;
 167                         defmi->deps = nl;
 168                 }
 169         }
 170
 171         /* Set current instruction as new define dependency and clear use         */
 172         /* depedencies.                                                           */
 173
 174         sd->intregs_define_dep[reg] = sd->micount;
 175         sd->intregs_use_dep[reg] = NULL;
 176 }
 177
 178
 179 void schedule_add_int_use_dep(scheduledata *sd, s4 reg)
 180 {
 181         minstruction *mi;
 182         minstruction *defmi;
 183         nodelink     *nl;
 184         s4            defnode;
 185
 186         /* get current machine instruction */
 187
 188         mi = &sd->mi[sd->micount - 1];
 189
 190         /* get current define dependency instruction */
 191
 192         if ((defnode = sd->intregs_define_dep[reg]) > 0) {
 193                 /* some edges to current machine instruction -> no leader */
 194
 195                 mi->leader = false;
 196
 197                 /* add node to dependency list of current define node */
 198
 199                 defmi = &sd->mi[defnode - 1];
 200
 201                 nl = DNEW(nodelink);
 202                 nl->minode = sd->micount;
 203                 nl->next = defmi->deps;
 204                 defmi->deps = nl;
 205         }
 206
 207         /* add node to list of current use nodes */
 208
 209         nl = DNEW(nodelink);
 210         nl->minode = sd->micount;
 211         nl->next = sd->intregs_use_dep[reg];
 212         sd->intregs_use_dep[reg] = nl;
 213 }
 214
 215
 216 void schedule_add_flt_define_dep(scheduledata *sd, s4 reg)
 217 {
 218         minstruction *mi;
 219         minstruction *defmi;
 220         minstruction *usemi;
 221         nodelink     *usenl;
 222         nodelink     *nl;
 223         s4            defnode;
 224
 225         /* get current machine instruction */
 226
 227         mi = &sd->mi[sd->micount - 1];
 228
 229         /* get current use dependency nodes, if non-null use them... */
 230
 231         if ((usenl = sd->fltregs_use_dep[reg])) {
 232                 /* add a dependency link node to all use dependency nodes */
 233
 234                 while (usenl) {
 235                         /* don't add to the current machine instruction */
 236
 237                         if (usenl->minode != sd->micount) {
 238                                 /* some edges to current machine instruction -> no leader */
 239
 240                                 mi->leader = false;
 241
 242                                 /* get use machine instruction */
 243
 244                                 usemi = &sd->mi[usenl->minode - 1];
 245
 246                                 nl = DNEW(nodelink);
 247                                 nl->minode = sd->micount;
 248                                 nl->next = usemi->deps;
 249                                 usemi->deps = nl;
 250                         }
 251
 252                         usenl = usenl->next;
 253                 }
 254
 255         } else {
 256                 /* ...otherwise use last define dependency, if non-null */
 257
 258                 if ((defnode = sd->fltregs_define_dep[reg]) > 0) {
 259                         /* some edges to current machine instruction -> no leader */
 260
 261                         mi->leader = false;
 262
 263                         /* get last define machine instruction */
 264
 265                         defmi = &sd->mi[defnode - 1];
 266
 267                         nl = DNEW(nodelink);
 268                         nl->minode = sd->micount;
 269                         nl->next = defmi->deps;
 270                         defmi->deps = nl;
 271                 }
 272         }
 273
 274         /* Set current instruction as new define dependency and clear use         */
 275         /* depedencies.                                                           */
 276
 277         sd->fltregs_define_dep[reg] = sd->micount;
 278         sd->fltregs_use_dep[reg] = NULL;
 279 }
 280
 281
 282 void schedule_add_flt_use_dep(scheduledata *sd, s4 reg)
 283 {
 284         minstruction *mi;
 285         minstruction *defmi;
 286         nodelink     *nl;
 287         s4            defnode;
 288
 289         /* get current machine instruction */
 290
 291         mi = &sd->mi[sd->micount - 1];
 292
 293         /* get current define dependency instruction */
 294
 295         if ((defnode = sd->fltregs_define_dep[reg]) > 0) {
 296                 /* some edges to current machine instruction -> no leader */
 297
 298                 mi->leader = false;
 299
 300                 /* add node to dependency list of current define node */
 301
 302                 defmi = &sd->mi[defnode - 1];
 303
 304                 nl = DNEW(nodelink);
 305                 nl->minode = sd->micount;
 306                 nl->next = defmi->deps;
 307                 defmi->deps = nl;
 308         }
 309
 310         /* add node to list of current use nodes */
 311
 312         nl = DNEW(nodelink);
 313         nl->minode = sd->micount;
 314         nl->next = sd->fltregs_use_dep[reg];
 315         sd->fltregs_use_dep[reg] = nl;
 316 }
 317
 318
 319 void schedule_add_memory_define_dep(scheduledata *sd)
 320 {
 321 }
 322
 323
 324 void schedule_add_memory_use_dep(scheduledata *sd)
 325 {
 326 }
 327
 328
 329 /* schedule_do_schedule ********************************************************
 330
 331    XXX
 332
 333 *******************************************************************************/
 334
 335 void schedule_do_schedule(scheduledata *sd)
 336 {
 337         minstruction *mi;
 338         nodelink     *nl;
 339         s4            i;
 340
 341         printf("bb start ---\n");
 342
 343         for (i = 1, mi = sd->mi; i <= sd->micount; i++, mi++) {
 344                 disassinstr(&mi->instr);
 345
 346                 printf("\t--> #%d, %d, %d, %d, ", i, mi->latency, mi->priority, mi->leader);
 347
 348                 printf("deps= ");
 349                 nl = mi->deps;
 350                 while (nl) {
 351                         printf("%d ", nl->minode);
 352                         nl = nl->next;
 353                 }
 354
 355                 printf("\n");
 356         }
 357         printf("bb end ---\n\n");
 358 }
 359
 360
 361 /*
 362  * These are local overrides for various environment variables in Emacs.
 363  * Please do not remove this and leave it at the end of the file, where
 364  * Emacs will automagically detect them.
 365  * ---------------------------------------------------------------------
 366  * Local variables:
 367  * mode: c
 368  * indent-tabs-mode: t
 369  * c-basic-offset: 4
 370  * tab-width: 4
 371  * End:
 372  */