comp/reg.c

   1 /******************************* comp/reg.c ************************************
   2
   3         Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
   4
   5         See file COPYRIGHT for information on usage and disclaimer of warranties
   6
   7         The register-manager.
   8
   9         Authors: Reinhard Grafl      EMAIL: cacao@complang.tuwien.ac.at
  10                  Andreas  Krall      EMAIL: cacao@complang.tuwien.ac.at
  11
  12         Last Change: 1997/10/23
  13
  14 *******************************************************************************/
  15
  16 /*********************** Structure of a register info *************************/
  17
  18 #define REG_TYPE_FLT        1    /* integer or floating point type       */
  19 #define REG_SIZE_DBL        2    /* int/single or long/double            */
  20 #define REG_INMEMORY        4    /* true if register is in memory        */
  21 #define REG_ISFREE          8    /* true if register is currently free   */
  22 #define REG_ISUNUSED        16   /* true if register never has been used */
  23 #define REG_ISFREEUNUSED    24
  24
  25 #define IS_INT_LNG_REG(a)   (!((a)&REG_TYPE_FLT))
  26 #define IS_FLT_DBL_REG(a)   ((a)&REG_TYPE_FLT)
  27
  28 #define REGTYPE_INT    0
  29 #define REGTYPE_FLT    1
  30 #define REGTYPE_LNG    2
  31 #define REGTYPE_DBL    3
  32
  33 #define REGTYPE(a)      ((a) & 3)
  34
  35 typedef struct reginfo {
  36         int  typeflags;                   /* register type, size and flags        */
  37         int  num;                         /* register number or stack offset      */
  38         list *waitlist;                   /* free list for register allocation    */
  39         listnode linkage;
  40 } reginfo;
  41
  42
  43
  44 static reginfo *intregs = NULL;       /* table for the integer registers      */
  45 static reginfo *floatregs = NULL;     /* table for the float registers        */
  46 static int intregsnum;                /* absolute number of integer registers */
  47 static int floatregsnum;              /* absolute number of float registers   */
  48
  49 static int intreg_ret;                /* register to return integer values    */
  50 static int intreg_exc;                /* register to return exception value   */
  51 static int intreg_arg1;               /* register for first integer argument  */
  52 static int intreg_argnum;             /* number of integer argument registers */
  53
  54 static int floatreg_ret;              /* register for return float values     */
  55 static int floatreg_arg1;             /* register for first float argument    */
  56 static int floatreg_argnum;           /* number of float argument registers   */
  57
  58
  59 static list savedintslist;     /* free saved int registers during allocation  */
  60 static list savedfloatslist;   /* free saved float registers during allocation*/
  61 static list scratchintslist;   /* free temp int registers during allocation   */
  62 static list scratchfloatslist; /* free temp float registers during allocation */
  63 static int *freeintregs;       /* free int registers table                    */
  64 static int *freefloatregs;     /* free float registers table                  */
  65
  66 static int savedregs_num;      /* total number of registers to be saved       */
  67 static int localvars_num;      /* total number of variables to spilled        */
  68 static int arguments_num;      /* size of parameter field in the stackframe   */
  69
  70
  71
  72 /****************** function reg_init ******************************************
  73
  74         initialises the register-allocator
  75
  76 *******************************************************************************/
  77
  78 static void reg_init()
  79 {
  80         int n;
  81
  82         if (!intregs) {
  83                 for (intregsnum=0; regdescint[intregsnum] != REG_END; intregsnum++);
  84                 intregs = MNEW (reginfo, intregsnum);
  85                 freeintregs = MNEW (int, intregsnum + 2);
  86                 *freeintregs++ = 0;
  87                 freeintregs[intregsnum] = 0;
  88
  89                 intreg_arg1 = -1;
  90                 for (n=0; n<intregsnum; n++) {
  91                         intregs[n].typeflags = 0;
  92                         intregs[n].num = n;
  93                         intregs[n].waitlist = NULL;
  94                         freeintregs[n] = 0;
  95
  96                         switch (regdescint[n]) {
  97                                 case REG_RES: break;
  98                                 case REG_RET: intreg_ret = n;
  99                                               break;
 100                                 case REG_EXC: intreg_exc = n;
 101                                               break;
 102                                 case REG_SAV: intregs[n].waitlist = &(savedintslist);
 103                                               freeintregs[n] = 1;
 104                                               break;
 105                                 case REG_TMP: intregs[n].waitlist = &(scratchintslist);
 106                                               freeintregs[n] = 1;
 107                                               break;
 108                                 case REG_ARG: if (intreg_arg1 < 0) intreg_arg1 = n;
 109                                               intreg_argnum++;
 110                                               break;
 111                                 }
 112                         }
 113
 114
 115                 for (floatregsnum=0; regdescfloat[floatregsnum] != REG_END; floatregsnum++);
 116                 floatregs = MNEW (reginfo, floatregsnum);
 117                 freefloatregs = MNEW (int, floatregsnum + 2);
 118                 *freefloatregs++ = 0;
 119                 freefloatregs[floatregsnum] = 0;
 120
 121         floatreg_arg1 = -1;
 122                 for (n=0; n<floatregsnum; n++) {
 123                         floatregs[n].typeflags = REG_TYPE_FLT;
 124                         floatregs[n].num = n;
 125                         floatregs[n].waitlist = NULL;
 126                         freefloatregs[n] = 0;
 127
 128                         switch (regdescfloat[n]) {
 129                                 case REG_RES: break;
 130                                 case REG_RET: floatreg_ret = n;
 131                                               break;
 132                                 case REG_EXC: panic ("can not use floating-reg as exception");
 133                                               break;
 134                                 case REG_SAV: floatregs[n].waitlist = &(savedfloatslist);
 135                                               freefloatregs[n] = 1;
 136                                               break;
 137                                 case REG_TMP: floatregs[n].waitlist = &(scratchfloatslist);
 138                                               freefloatregs[n] = 1;
 139                                               break;
 140                                 case REG_ARG: if (floatreg_arg1 < 0) floatreg_arg1 = n;
 141                                               floatreg_argnum++;
 142                                               break;
 143                                 }
 144                         }
 145
 146                 }
 147
 148
 149         list_init (&savedintslist, OFFSET(reginfo, linkage));
 150         list_init (&savedfloatslist, OFFSET(reginfo, linkage));
 151         list_init (&scratchintslist, OFFSET(reginfo, linkage));
 152         list_init (&scratchfloatslist, OFFSET(reginfo, linkage));
 153
 154         for (n=0; n<intregsnum; n++) {
 155                 intregs[n].typeflags |= REG_ISFREE | REG_ISUNUSED;
 156                 if (intregs[n].waitlist)
 157                         list_addlast(intregs[n].waitlist, intregs+n);
 158         }
 159         for (n=0; n<floatregsnum; n++) {
 160                 floatregs[n].typeflags |= REG_ISFREE | REG_ISUNUSED;
 161                 if (floatregs[n].waitlist)
 162                         list_addlast(floatregs[n].waitlist, floatregs+n);
 163                 }
 164
 165
 166         localvars_num = 0;
 167         arguments_num = 0;
 168 }
 169
 170
 171 /********************** function reg_close *************************************
 172
 173         releases all allocated space for registers
 174
 175 *******************************************************************************/
 176
 177 static void reg_close ()
 178 {
 179         if (intregs) MFREE (intregs, reginfo, intregsnum);
 180         if (floatregs) MFREE (floatregs, reginfo, floatregsnum);
 181 }
 182
 183
 184 /********************* function reg_free ***************************************
 185
 186         put back a register which has been allocated by reg_allocate into the
 187         corresponding free list
 188
 189 *******************************************************************************/
 190
 191 static void reg_free (reginfo *ri)
 192 {
 193         ri -> typeflags |= REG_ISFREE;
 194
 195         if (ri->waitlist) {
 196                 if (ri->typeflags & REG_INMEMORY)
 197                         list_addlast  (ri->waitlist, ri);
 198                 else {
 199 #if (WORDSIZE == 4)
 200                         reginfo *ri1;
 201
 202                         if (ri->typeflags & REG_TYPE_FLT) {
 203                                 if (ri->typeflags & REG_SIZE_DBL) {
 204                                         freefloatregs[ri->num] = 0;
 205                                         freefloatregs[ri->num + 1] = 0;
 206                                         ri1 = &floatregs[ri->num + 1];
 207                                         list_addfirst (ri1->waitlist, ri1);
 208                                         }
 209                                 else
 210                                         freefloatregs[ri->num] = 0;
 211                                 }
 212                         else {
 213                                 if (ri->typeflags & REG_SIZE_DBL) {
 214                                         freeintregs[ri->num] = 0;
 215                                         freeintregs[ri->num + 1] = 0;
 216                                         ri1 = &intregs[ri->num + 1];
 217                                         list_addfirst (ri1->waitlist, ri1);
 218                                         }
 219                                 else
 220                                         freeintregs[ri->num] = 0;
 221                                 }
 222 #endif
 223                         list_addfirst (ri->waitlist, ri);
 224                         }
 225                 }
 226 }
 227
 228
 229 /******************* internal function reg_suckregister ************************
 230
 231         searches for the first register of a list which fullfills the requirements:
 232         if argument isunused is true ri->typeflags&REG_ISUNUSED has to be true too
 233         if register pairs are required two adjacent register are searched
 234         if a register can be found it is removed from the free list and the
 235         fields 'isunused' and 'isfree' are set to false
 236
 237 *******************************************************************************/
 238
 239 static reginfo *reg_remove (list *l, int num) {
 240         reginfo *ri;
 241
 242         ri = list_first (l);
 243         while (ri->num != num)
 244                 ri = list_next (l, ri);
 245         if (ri->typeflags & REG_TYPE_FLT)
 246                 freefloatregs[num] = 0;
 247         else
 248                 freeintregs[num] = 0;
 249         list_remove (l, ri);
 250         ri -> typeflags &= ~REG_ISFREEUNUSED;
 251         return ri;
 252 }
 253
 254
 255 static reginfo *reg_suckregister (list *l, bool isunused)
 256 {
 257         reginfo *ri;
 258
 259         ri = list_first (l);
 260
 261         while (ri) {
 262                 if ( (!isunused) || (ri->typeflags & REG_ISUNUSED)) {
 263 #if (WORDSIZE == 4)
 264                         reginfo *retreg = NULL;
 265
 266                         if (ri->typeflags & REG_SIZE_DBL) {
 267                                 if (ri->typeflags & REG_TYPE_FLT)
 268                                         if (ri->num & 1) {
 269                                                 if(freefloatregs[ri->num - 1]) {
 270                                                         freefloatregs[ri->num] = 0;
 271                                                         retreg = reg_remove(l, ri->num - 1);
 272                                                         }
 273                                                 }
 274                                         else {
 275                                                 if (freefloatregs[ri->num + 1]) {
 276                                                         freefloatregs[ri->num] = 0;
 277                                                         retreg = ri;
 278                                                         (void) reg_remove(l, ri->num + 1);
 279                                                         }
 280                                                 }
 281                                 else if (freeintregs[ri->num + 1]) {
 282                                                 freeintregs[ri->num] = 0;
 283                                                 retreg = ri;
 284                                                 (void) reg_remove(l, ri->num + 1);
 285                                                 }
 286                                         else if(freeintregs[ri->num - 1]) {
 287                                                 freeintregs[ri->num] = 0;
 288                                                 retreg = reg_remove(l, ri->num - 1);
 289                                                 }
 290                                 if (retreg) {
 291                                         list_remove (l, ri);
 292                                         ri -> typeflags &= ~REG_ISFREEUNUSED;
 293                                         return retreg;
 294                                         }
 295                                 }
 296                         else {
 297                                 if (ri->typeflags & REG_TYPE_FLT)
 298                                         freefloatregs[ri->num] = 0;
 299                                 else
 300                                         freeintregs[ri->num] = 0;
 301                                 list_remove (l, ri);
 302                                 ri -> typeflags &= ~REG_ISFREEUNUSED;
 303                                 return ri;
 304                                 }
 305 #else
 306                         list_remove (l, ri);
 307                         ri -> typeflags &= ~REG_ISFREEUNUSED;
 308                         return ri;
 309 #endif
 310                         }
 311                 ri = list_next (l, ri);
 312                 }
 313         return NULL;
 314 }
 315
 316
 317 /******************** Funktion: reg_allocate **********************************
 318
 319         versucht, ein Register zu belegen, das vom richtigen Typ ist, und
 320         allen gew"unschten Anforderungen entspricht.
 321
 322         Parameter:
 323                 type .... JAVA-Grundtyp (INT,LONG,DOUBLE,FLOAT,ADDRESS)
 324                 saved ... Das Register soll bei Methodenaufrufen nicht zerst"ort werden
 325                 new ..... Das Register soll noch nie vorher verwendet worden sein
 326
 327         Wenn es (aus verschiedenen Gr"unden) kein geeignetes freies Register f"ur
 328         den Zweck mehr gibt, dann erzeugt diese Funktion einen Verweis auf
 329         einen Platz am aktuellen Stackframe (diese Stackframe-Eintr"age erf"ullen
 330         auf jeden Fall alle obigen Forderungen)
 331
 332 *******************************************************************************/
 333
 334 static reginfo *reg_allocate (u2 type, bool saved, bool new)
 335 {
 336         u2 t;
 337         reginfo *ri;
 338
 339         switch (type) {
 340                 case TYPE_LONG:
 341                         t = REG_SIZE_DBL;
 342                         break;
 343                 case TYPE_INT:
 344                         t = 0;
 345                         break;
 346                 case TYPE_FLOAT:
 347                         t = REG_TYPE_FLT;
 348                         break;
 349                 case TYPE_DOUBLE:
 350                         t = REG_TYPE_FLT | REG_SIZE_DBL;
 351                         break;
 352                 default:
 353                         t = 0;
 354                 }
 355
 356         if (!saved) {
 357                 if (IS_INT_LNG_REG(t))
 358                         ri = reg_suckregister (&scratchintslist, new);
 359                 else
 360                         ri = reg_suckregister (&scratchfloatslist, new);
 361                 if (ri) return ri;
 362                 }
 363
 364         if (IS_INT_LNG_REG(t))
 365                 ri = reg_suckregister (&savedintslist, new);
 366         else
 367                 ri = reg_suckregister (&savedfloatslist, new);
 368         if (ri) return ri;
 369
 370         ri = DNEW (reginfo);
 371         ri -> typeflags = t | REG_INMEMORY;
 372 #if (WORDSIZE == 4)
 373         ri -> num = localvars_num;
 374         if (t & REG_SIZE_DBL)
 375                 localvars_num += 2;
 376         else
 377                 localvars_num++;
 378 #else
 379         ri -> num = (localvars_num++);
 380 #endif
 381         ri -> waitlist = (IS_INT_LNG_REG(t)) ? &savedintslist : &savedfloatslist;
 382         return ri;
 383 }
 384
 385
 386 /********************* Funktion: reg_reallocate *******************************
 387
 388         versucht, ein schon einmal angefordertes (aber in der Zwischenzeit
 389         wieder freigegebenens) Register neuerlich anzufordern.
 390         Wenn das Register immer noch unbenutzt ist, dann ist alles OK
 391         (R"uckgabewert true), sonst wird 'false' zur"uckgeben, und aus der
 392         neuerlichen Belegung wird nichts.
 393
 394 ******************************************************************************/
 395
 396 static bool reg_reallocate (reginfo *ri)
 397 {
 398         if (!(ri->typeflags & REG_ISFREE)) return false;
 399
 400         ri->typeflags &= ~REG_ISFREEUNUSED;
 401
 402         if (ri->waitlist) list_remove (ri->waitlist, ri);
 403
 404         return true;
 405 }
 406
 407
 408
 409 /****************** Funktion: reg_parlistresult *******************************
 410
 411         Erzeugt eine Registerreferenz auf das Register, das vom System zur
 412         R"uckgabe von Werten aus Methoden verwendet wird.
 413         Parameter:
 414                 type ... Der JAVA-Grundtyp des R"uckgabewertes
 415
 416 ******************************************************************************/
 417
 418 static reginfo *reg_parlistresult (u2 type)
 419 {
 420         if (type==TYPE_FLOAT || type==TYPE_DOUBLE) return &(floatregs[floatreg_ret]);
 421                                                                                   else return &(intregs[intreg_ret]);
 422 }
 423
 424
 425
 426 /*************** Funktion: reg_parlistexception ******************************
 427
 428         Erzeugt eine Registerreferenz auf das Register, in dem das System die
 429         Zeiger auf allf"allige Exception-Objekte bei Methodenaufrufen
 430         zur"uckliefert.
 431
 432 ******************************************************************************/
 433
 434 static reginfo *reg_parlistexception ()
 435 {
 436         return &(intregs[intreg_exc]);
 437 }
 438
 439
 440
 441 /************************ Funktion: reg_parlistpar ****************************
 442
 443         Erzeugt eine Registerreferenz auf ein Register, in dem das n"achste
 444         Argument (in der Z"ahlung ab dem Zeitpunkt von Aufruf von 'reg_parlistinit')
 445         bei Methodenaufrufen eingetragen wird.
 446         Wenn es in Summe mehr als die m"oglichen Parameter-Register werden, dann
 447         wird auch noch Platz am Stack f"ur die "uberz"ahligen Werte reserviert
 448
 449 ******************************************************************************/
 450
 451 static int usedintpar, usedfloatpar;
 452 static int usedparoverflow;
 453
 454 static reginfo *reg_parlistpar (u2 type)
 455 {
 456         reginfo *f;
 457
 458         if (type == TYPE_FLOAT || type == TYPE_DOUBLE) {
 459                 usedfloatpar++;
 460                 if (reg_parammode == PARAMMODE_NUMBERED) usedintpar++;
 461
 462                 if (usedfloatpar <= floatreg_argnum) {
 463                         f = &floatregs[floatreg_arg1 + (usedfloatpar - 1) ];
 464                         f->typeflags &= ~REG_ISUNUSED;
 465                         return f;
 466                         }
 467                 else goto overflow;
 468                 }
 469         else {
 470                 usedintpar++;
 471                 if (reg_parammode == PARAMMODE_NUMBERED) usedfloatpar++;
 472
 473                 if (usedintpar <= intreg_argnum) {
 474                         f = &intregs[intreg_arg1 + (usedintpar - 1) ];
 475                         f->typeflags &= ~REG_ISUNUSED;
 476                         return f;
 477                         }
 478                 else goto overflow;
 479         }
 480
 481
 482
 483 overflow:
 484         usedparoverflow++;
 485         if (usedparoverflow > arguments_num) arguments_num = usedparoverflow;
 486         return NULL;
 487 }
 488
 489
 490 /****************** Funktion: reg_parlistinit *********************************
 491
 492         initialisiert die Z"ahlung der Parameter-Register
 493
 494 *******************************************************************************/
 495
 496 static void reg_parlistinit()
 497 {
 498         usedintpar = 0;
 499         usedfloatpar = 0;
 500         usedparoverflow = 0;
 501 }
 502
 503
 504
 505
 506
 507 /***************** Funktion: reg_display *************************************
 508
 509         gibt eine Register-Referenz in lesbarer Form auf 'stdout' aus.
 510
 511 ******************************************************************************/
 512
 513 static void reg_display (reginfo *ri)
 514 {
 515         if (ri->typeflags & REG_INMEMORY) {
 516                 printf ("[%d]", (int) (ri->num) );
 517                 }
 518         else {
 519                 printf ("%s%d",
 520                   (IS_INT_LNG_REG(ri->typeflags)) ? "$" : "f$",
 521                   (int) (ri->num) );
 522                 }
 523 }
 524
 525