1 /* 2 * Copyright (c) 1980 Regents of the University of California. 3 * All rights reserved. The Berkeley software License Agreement 4 * specifies the terms and conditions for redistribution. 5 */ 6 7 #ifndef lint 8 static char sccsid[] = "@(#)regalloc.c 5.1 (Berkeley) 6/7/85"; 9 #endif not lint 10 11 /* 12 * regalloc.c 13 * 14 * Register optimization routines for f77 compiler, pass 1 15 * 16 * University of Utah CS Dept modification history: 17 * 18 * $History$ 19 * $Log: regalloc.c,v $ 20 * Revision 1.4 86/02/12 15:29:16 rcs 21 * 4.3 F77. C. Keating. 22 * 23 * Revision 2.9 85/03/18 21:35:05 donn 24 * Bob Corbett's hack to prevent conflicts between subroutine side effects 25 * and register assignment. Makes the code a lot worse... 26 * 27 * Revision 2.8 85/02/22 02:14:08 donn 28 * In code like 'x = foo(x)', alreg() would copy the memory version of the 29 * variable 'x' into the register version after the assignment, clobbering 30 * the result. A small change to regwrite() seems to prevent this. 31 * 32 * Revision 2.7 85/02/16 03:32:45 donn 33 * Fixed a bug where the loop test and increment were having register 34 * substitution performed twice, once in the environment of the current 35 * loop and once in the environment of the containing loop. If the 36 * containing loop puts (say) the inner loop's index variable in register 37 * but the inner loop does not, havoc results. 38 * 39 * Revision 2.6 85/02/14 23:21:45 donn 40 * Don't permit variable references of the form 'a(i)' to be put in register 41 * if array 'a' is in common. This is because there is no good way to 42 * identify instances of this sort without getting confused with other 43 * variables in the same common block which are in register. Sigh. 44 * 45 * Revision 2.5 85/01/11 21:08:00 donn 46 * Made changes so that we pay attention to SAVE statements. Added a new 47 * gensetreturn() function to implement this. 48 * 49 * Revision 2.4 84/09/03 22:37:28 donn 50 * Changed the treatment of SKRETURN in alreg() so that all variables in 51 * register, not just COMMON variables, get written out to memory before a 52 * RETURN. This was causing the return value of a function to get lost when 53 * a RETURN was done from inside a loop (among other problems). 54 * 55 * Revision 2.3 84/08/04 20:52:42 donn 56 * Added fixes for EXTERNAL parameters from Jerry Berkman. 57 * 58 * Revision 2.2 84/08/04 20:34:29 donn 59 * Fixed a stupidity pointed out by Jerry Berkman -- the 'floats in register' 60 * stuff applies if the TARGET is a VAX, not if the local machine is a VAX. 61 * 62 * Revision 2.1 84/07/19 12:04:47 donn 63 * Changed comment headers for UofU. 64 * 65 * Revision 1.5 83/11/27 19:25:41 donn 66 * Added REAL to the list of types which may appear in registers (VAXen only). 67 * 68 * Revision 1.4 83/11/13 02:38:39 donn 69 * Bug fixed in alreg()'s handling of computed goto's. A '<=' in place of a 70 * '<' led to core dumps when we walked off the end of the list of labels... 71 * 72 * Revision 1.3 83/11/12 01:25:57 donn 73 * Bug in redundant register assignment code, mistakenly carried over some old 74 * code that sometimes rewound a slot pointer even when a redundant slot wasn't 75 * deleted; this caused an infinite loop... Seems to work now. 76 * 77 * Revision 1.2 83/11/09 14:58:12 donn 78 * Took out broken code dealing with redundant register initializations. 79 * Couldn't see what to do about redundantly initializing a DO variable but 80 * I did fix things so that an assignment from a register into the same 81 * register is always deleted. 82 * 83 */ 84 85 #include "defs.h" 86 #include "optim.h" 87 88 #define LABTABSIZE 101 89 #define VARTABSIZE 1009 90 #define TABLELIMIT 12 91 92 #if TARGET==VAX || TARGET==TAHOE 93 #define MSKREGTYPES M(TYLOGICAL) | M(TYADDR) | M(TYSHORT) | M(TYLONG) | M(TYREAL) 94 #if TARGET==TAHOE 95 #define BUMPREALS /* put floats last */ 96 #endif 97 #else 98 #define MSKREGTYPES M(TYLOGICAL) | M(TYADDR) | M(TYSHORT) | M(TYLONG) 99 #endif 100 101 102 #define ISREGTYPE(x) ONEOF(x, MSKREGTYPES) 103 104 #define MSKVARS M(STGAUTO) | M(STGBSS) | M(STGINIT) | M(STGCONST) |\ 105 M(STGEQUIV) | M(STGARG) | M(STGCOMMON) 106 107 #define ISVAR(x) ((((expptr) x)->headblock.vclass == CLVAR || \ 108 ((expptr) x)->headblock.vclass == CLUNKNOWN) \ 109 && ONEOF(((expptr) x)->headblock.vstg, MSKVARS)) 110 111 112 typedef 113 struct regdata 114 { 115 field vstg; 116 field vtype; 117 int memno; 118 int memoffset; 119 int refs; 120 Addrp stgp; 121 unsigned isarrayarg : 1; 122 unsigned istemp : 1; 123 unsigned isset : 1; 124 unsigned setfirst : 1; 125 } REGDATA; 126 127 128 typedef 129 struct labelnode 130 { 131 struct labelnode *link; 132 int labelno; 133 } LABELNODE; 134 135 136 137 typedef 138 struct varnode 139 { 140 struct varnode *link; 141 int memoffset; 142 unsigned isset : 1; 143 unsigned isused : 1; 144 unsigned setfirst : 1; 145 unsigned unusable : 1; 146 int refs; 147 Addrp stgp; 148 } VARNODE; 149 150 151 typedef 152 struct addrnode 153 { 154 struct addrnode *link; 155 field vtype; 156 field vstg; 157 int memno; 158 unsigned istemp : 1; 159 unsigned isset : 1; 160 unsigned loopset :1; 161 unsigned freeuse : 1; 162 unsigned mixedtype : 1; 163 unsigned fixed : 1; 164 int refs; 165 struct addrnode *commonlink; 166 VARNODE *varlist; 167 } ADDRNODE; 168 169 170 typedef 171 struct setnode 172 { 173 struct setnode *link; 174 field vstg; 175 int memno; 176 int memoffset; 177 } SETNODE; 178 179 180 typedef 181 struct doqueue 182 { 183 struct doqueue *up, *down; 184 Slotp dohead, doend; 185 int nregvars; 186 REGNODE *reg[MAXREGVAR]; 187 } DOQUEUE; 188 189 LOCAL DOQUEUE *dqptr, *dqtop, *dqbottom; 190 191 192 LOCAL Slotp dohead; 193 LOCAL Slotp doend; 194 LOCAL Slotp newcode; 195 196 197 198 LOCAL LABELNODE *labeltable[LABTABSIZE]; 199 LOCAL ADDRNODE *vartable[VARTABSIZE]; 200 LOCAL ADDRNODE *commonvars; 201 LOCAL SETNODE *setlist; 202 LOCAL int topregvar; 203 LOCAL int toplcv; 204 LOCAL int allset; 205 LOCAL ADDRNODE *currentaddr; 206 LOCAL int loopcost; 207 LOCAL REGDATA *regtab[MAXREGVAR]; 208 LOCAL REGDATA *rt[TABLELIMIT]; 209 LOCAL int tabletop; 210 LOCAL int linearcode; 211 LOCAL int docount; 212 LOCAL int globalbranch; 213 LOCAL int commonunusable; 214 LOCAL int regdefined[MAXREGVAR]; 215 LOCAL int memdefined[MAXREGVAR]; 216 LOCAL int regaltered[MAXREGVAR]; 217 218 219 220 LOCAL insertlabel(l) 221 int l; 222 223 { 224 int key; 225 LABELNODE *p; 226 227 key = l % LABTABSIZE; 228 for (p = labeltable[key]; p; p = p->link) 229 if (p->labelno == l) return; 230 p = labeltable[key]; 231 labeltable[key] = ALLOC(labelnode); 232 labeltable[key]->link = p; 233 labeltable[key]->labelno = l; 234 return; 235 } 236 237 238 239 LOCAL int locallabel(l) 240 int l; 241 242 { 243 int key; 244 LABELNODE *p; 245 246 key = l % LABTABSIZE; 247 for (p = labeltable[key]; p; p = p->link) 248 if (p->labelno == l) return YES; 249 250 return NO; 251 } 252 253 254 255 LOCAL freelabtab() 256 257 { 258 int i; 259 LABELNODE *p, *q; 260 261 for (i = 0; i < LABTABSIZE; i++) 262 if (labeltable[i]) 263 { 264 p = labeltable[i]; 265 labeltable[i] = NULL; 266 while (p) 267 { 268 q = p->link; 269 free(p); 270 p = q; 271 } 272 } 273 return; 274 } 275 276 277 278 LOCAL ADDRNODE *getaddr(ap) 279 Addrp ap; 280 281 { 282 int key; 283 field vstg; 284 int memno; 285 register ADDRNODE *q; 286 ADDRNODE *q1; 287 288 if (!ISVAR(ap)) 289 fatal("regalloc: bad data sent to getaddr"); 290 vstg = ap->vstg; 291 memno = ap->memno; 292 key = (256*vstg + memno) % VARTABSIZE; 293 294 for (q = vartable[key]; q; q = q->link) 295 if ((q->vstg == vstg) && (q->memno == memno)) 296 { 297 if (ap->istemp) q->istemp = YES; 298 if (ap->vtype != q->vtype) 299 q->mixedtype = YES; 300 if (!fixedaddress(ap)) 301 q->fixed = NO; 302 return q; 303 } 304 305 q1 = vartable[key]; 306 vartable[key] = q = ALLOC(addrnode); 307 q->link = q1; 308 q->vstg = vstg; 309 q->memno = memno; 310 if (ap->istemp) q->istemp = YES; 311 if (fixedaddress(ap)) q->fixed = YES; 312 q->vtype = ap->vtype; 313 q->varlist = NULL; 314 if (vstg == STGCOMMON) 315 { 316 q->commonlink = commonvars; 317 commonvars = q; 318 } 319 return q; 320 } 321 322 323 324 LOCAL VARNODE *getvar(ainfo, ap) 325 ADDRNODE *ainfo; 326 Addrp ap; 327 328 { 329 register VARNODE *q; 330 register VARNODE *q1; 331 332 int memoffset; 333 334 if (!ISVAR(ap)) 335 fatal("regalloc: bad data sent to getvar"); 336 337 memoffset = ap->memoffset->constblock.constant.ci; 338 339 for (q = ainfo->varlist; q; q = q->link) 340 if (q->memoffset == memoffset) 341 return q; 342 343 q1 = ainfo->varlist; 344 ainfo->varlist = q = ALLOC(varnode); 345 q->link = q1; 346 q->memoffset = memoffset; 347 q->stgp = (Addrp) cpexpr(ap); 348 return q; 349 } 350 351 352 LOCAL ADDRNODE *lookupaddr(vstg, memno) 353 field vstg; 354 int memno; 355 356 { 357 int key; 358 register ADDRNODE *q; 359 360 key = (256*vstg + memno) % VARTABSIZE; 361 362 for (q = vartable[key]; q; q = q->link) 363 if ((q->vstg == vstg) && (q->memno == memno)) 364 return q; 365 366 fatal("regalloc: lookupaddr"); 367 } 368 369 370 LOCAL VARNODE *lookupvar(ainfo, memoffset) 371 ADDRNODE *ainfo; 372 int memoffset; 373 374 { 375 register VARNODE *q; 376 377 for (q = ainfo->varlist; q; q = q->link) 378 if (q->memoffset == memoffset) 379 return q; 380 381 fatal("regalloc: lookupvar"); 382 } 383 384 385 386 LOCAL int invartable(p) 387 REGNODE *p; 388 389 { 390 field vstg; 391 int memno; 392 int key; 393 register ADDRNODE *q; 394 395 vstg = p->vstg; 396 memno = p->memno; 397 key = (256*vstg + memno) % VARTABSIZE; 398 399 for (q = vartable[key]; q; q = q->link) 400 if ((q->vstg == vstg) && (q->memno == memno)) 401 return YES; 402 403 return NO; 404 } 405 406 407 408 LOCAL freevartab() 409 410 { 411 register ADDRNODE *p; 412 ADDRNODE *p1; 413 register VARNODE *q; 414 VARNODE *q1; 415 register int i; 416 417 for (i = 0; i < VARTABSIZE; i++) 418 if (vartable[i]) 419 { 420 p = vartable[i]; 421 vartable[i] = NULL; 422 423 while (p) 424 { 425 for (q = p->varlist; q; q = q1) 426 { 427 q1 = q->link; 428 frexpr(q->stgp); 429 free ((char *) q); 430 } 431 p1 = p->link; 432 free((char *) p); 433 p = p1; 434 } 435 } 436 } 437 438 439 440 LOCAL insertset(vstg, memno, memoffset) 441 field vstg; 442 int memno; 443 int memoffset; 444 445 { 446 register SETNODE *p; 447 SETNODE *q; 448 449 if (allset) return; 450 for (p = setlist; p; p = p->link) 451 if((p->vstg == vstg) && (p->memno == memno) && (p->memoffset == memoffset)) 452 return; 453 454 q = p; 455 setlist = p = ALLOC(setnode); 456 p->link = q; 457 p->vstg = vstg; 458 p->memno = memno; 459 p->memoffset = memoffset; 460 return; 461 } 462 463 464 465 LOCAL int insetlist(vstg, memno, memoffset) 466 field vstg; 467 int memno; 468 int memoffset; 469 470 { 471 register SETNODE *p; 472 473 if (allset) return YES; 474 for (p = setlist; p; p = p->link) 475 if((p->vstg == vstg) && (p->memno == memno) && (p->memoffset == memoffset)) 476 return YES; 477 478 return NO; 479 } 480 481 482 483 LOCAL clearsets() 484 485 { 486 register SETNODE *p, *q; 487 488 allset = NO; 489 490 p = setlist; 491 while (p) 492 { 493 q = p->link; 494 free ((char *) p); 495 p = q; 496 } 497 setlist = NULL; 498 return; 499 } 500 501 502 503 LOCAL alreg() 504 505 { 506 register Slotp sp; 507 register int i; 508 register ADDRNODE *p; 509 register VARNODE *q; 510 Slotp sp1, sp2; 511 ADDRNODE *addrinfo; 512 VARNODE *varinfo; 513 struct Labelblock **lp; 514 int toptrack; 515 int track[MAXREGVAR]; 516 Addrp ap, ap1; 517 DOQUEUE *dqp; 518 REGDATA *rp; 519 REGNODE *regp; 520 521 if (nregvar >= maxregvar) return; 522 523 commonvars = NULL; 524 docount = 0; 525 526 for (sp = dohead; sp != doend->next; sp = sp->next) 527 switch (sp->type) 528 { 529 case SKLABEL: 530 insertlabel(sp->label); 531 break; 532 533 case SKARIF: 534 case SKASGOTO: 535 case SKCALL: 536 case SKCMGOTO: 537 case SKEQ: 538 case SKIFN: 539 case SKIOIFN: 540 case SKSTOP: 541 case SKPAUSE: 542 case SKRETURN: 543 scanvars(sp->expr); 544 break; 545 546 case SKDOHEAD: 547 ++docount; 548 break; 549 550 case SKENDDO: 551 --docount; 552 break; 553 554 case SKNULL: 555 case SKGOTO: 556 case SKASSIGN: 557 break; 558 559 default: 560 badthing ("SKtype", "alreg-1", sp->type); 561 } 562 563 loopcost = 0; 564 docount = 1; 565 commonunusable = NO; 566 if (! dohead->nullslot) fatal ("missing dohead->nullslot -cbb"); 567 for (sp = dohead->next, globalbranch = NO; 568 docount; 569 sp = sp->next, clearsets(), globalbranch = NO) 570 if (docount > 1) 571 switch (sp->type) 572 { 573 case SKDOHEAD: 574 docount++; 575 break; 576 577 case SKENDDO: 578 docount--; 579 580 default: 581 break; 582 } 583 else 584 switch (sp->type) 585 { 586 case SKARIF: 587 #define LM ((struct Labelblock * *)sp->ctlinfo)[0]->labelno 588 #define LZ ((struct Labelblock * *)sp->ctlinfo)[1]->labelno 589 #define LP ((struct Labelblock * *)sp->ctlinfo)[2]->labelno 590 591 if (!locallabel(LM) || !locallabel(LZ) || !locallabel(LP)) 592 { 593 setall(); 594 globalbranch = YES; 595 } 596 countrefs(sp->expr); 597 break; 598 599 case SKASGOTO: 600 setall(); 601 globalbranch = YES; 602 countrefs(sp->expr); 603 break; 604 605 case SKCMGOTO: 606 lp = (struct Labelblock **) sp->ctlinfo; 607 for (i = 0; i < sp->label; i++, lp++) 608 if (!locallabel((*lp)->labelno)) 609 { 610 setall(); 611 globalbranch = YES; 612 break; 613 } 614 countrefs(sp->expr); 615 break; 616 617 case SKDOHEAD: 618 globalbranch = YES; 619 loopcost = 2; 620 docount++; 621 break; 622 623 case SKENDDO: 624 docount = 0; 625 break; 626 627 case SKGOTO: 628 if (!locallabel(sp->label)) 629 { 630 setall(); 631 globalbranch = YES; 632 } 633 break; 634 635 case SKIFN: 636 case SKIOIFN: 637 if (!locallabel(sp->label)) 638 { 639 setall(); 640 globalbranch = YES; 641 } 642 countrefs(sp->expr); 643 break; 644 645 case SKEQ: 646 case SKCALL: 647 case SKSTOP: 648 case SKPAUSE: 649 linearcode = YES; 650 countrefs(sp->expr); 651 linearcode = NO; 652 break; 653 } 654 655 topregvar = toplcv = nregvar - 1; 656 657 for (i = 0; i < nregvar; i++) 658 { 659 ap = memversion(regnamep[i]); 660 regtab[i] = rp = ALLOC(regdata); 661 rp->vstg = ap->vstg; 662 rp->vtype = ap->vtype; 663 rp->memno = ap->memno; 664 rp->memoffset = ap->memoffset->constblock.constant.ci; 665 rp->isarrayarg = NO; 666 rp->stgp = ap; 667 } 668 669 for (i = 0; i < MAXREGVAR; i++) 670 track[i] = YES; 671 672 for (dqp = dqptr->down; dqp; dqp = dqp->down) 673 { 674 if (dqp->nregvars - 1 > topregvar) 675 topregvar = dqp->nregvars -1; 676 for (i = toplcv + 1; i < dqp->nregvars; i++) 677 if (track[i]) 678 if (regp = dqp->reg[i]) 679 if (rp = regtab[i]) 680 { 681 if (!samevar(rp, regp)) 682 track[i] = NO; 683 } 684 else if (invartable(regp)) 685 { 686 regtab[i] = rp = ALLOC(regdata); 687 rp->vstg = regp->vstg; 688 rp->vtype = regp->vtype; 689 rp->memno = regp->memno; 690 rp->memoffset = regp->memoffset; 691 addrinfo = lookupaddr(rp->vstg, rp->memno); 692 if (regp->isarrayarg) 693 { 694 rp->isarrayarg = YES; 695 rp->refs = addrinfo->refs; 696 } 697 else 698 { 699 varinfo = lookupvar(addrinfo, regp->memoffset); 700 rp->refs = varinfo->refs; 701 rp->stgp = (Addrp) cpexpr(varinfo->stgp); 702 rp->istemp = addrinfo->istemp; 703 rp->isset = varinfo->isset; 704 rp->setfirst = varinfo->setfirst; 705 } 706 } 707 else 708 track[i] = NO; 709 else 710 track[i] = NO; 711 } 712 713 toptrack = topregvar; 714 715 for (i = toplcv + 1; i <= topregvar; i++) 716 if (regtab[i]) 717 if ((track[i] == NO) || (regtab[i]->refs <= 0)) 718 { 719 free((char *) regtab[i]); 720 regtab[i] = NULL; 721 } 722 723 tabletop = -1; 724 if (topregvar < maxregvar - 1) 725 for (i = 0; i < VARTABSIZE; i++) 726 for (p = vartable[i]; p; p = p->link) 727 { 728 entableaddr(p); 729 if ((!p->loopset) && 730 (!p->mixedtype) && 731 (p->vstg != STGARG) && 732 !((p->vstg == STGCOMMON) && ((!p->fixed) || commonunusable))) 733 for (q = p->varlist; q; q = q->link) 734 entablevar(q); 735 } 736 737 for (i = 0; (i <= tabletop) && (topregvar + 1 < maxregvar); i++) 738 { 739 if (inregtab(rt[i]) || (loopcost && rt[i]->isset)) 740 continue; 741 topregvar++; 742 regtab[topregvar] = rp = ALLOC(regdata); 743 rp->vstg = rt[i]->vstg; 744 rp->vtype = rt[i]->vtype; 745 rp->memno = rt[i]->memno; 746 rp->memoffset = rt[i]->memoffset; 747 rp->refs = rt[i]->refs; 748 rp->stgp = (Addrp) cpexpr(rt[i]->stgp); 749 rp->isarrayarg = rt[i]->isarrayarg; 750 rp->istemp = rt[i]->istemp; 751 rp->isset = rt[i]->isset; 752 rp->setfirst = rt[i]->setfirst; 753 } 754 755 for (i = toplcv + 1; i <= topregvar; i++) 756 { 757 if (rp = regtab[i]) 758 if (rp->isarrayarg) 759 { 760 ap = ALLOC(Addrblock); 761 ap->tag = TADDR; 762 ap->vstg = STGREG; 763 ap->vtype = TYADDR; 764 ap->vclass = CLVAR; 765 ap->memno = regnum[i]; 766 ap->memoffset = ICON(0); 767 768 ap1 = ALLOC(Addrblock); 769 ap1->tag = TADDR; 770 ap1->vstg = rp->vstg; 771 ap1->vtype = rp->vtype; 772 ap1->vclass = CLVAR; 773 ap1->memno = rp->memno; 774 ap1->memoffset = ICON(0); 775 776 insertassign(dohead, ap, addrof(ap1)); 777 } 778 else if (!(rp->setfirst && rp->istemp)) 779 { 780 if (rp->istemp) 781 for (sp = newcode; sp && sp != dohead; sp = sp->next) 782 if (sp->type == SKEQ) 783 { 784 ap = (Addrp) sp->expr->exprblock.leftp; 785 if ((ap->vstg == rp->vstg) && (ap->memno == rp->memno) && 786 fixedaddress(ap) && 787 (ap->memoffset->constblock.constant.ci == rp->memoffset)) 788 { 789 changetoreg(ap, i); 790 goto L1; 791 } 792 } 793 ap = (Addrp) cpexpr(rp->stgp); 794 changetoreg(ap, i); 795 insertassign(dohead, ap, cpexpr(rp->stgp)); 796 } 797 L1:; 798 } 799 800 for (i = toplcv + 1; i <= topregvar; i++) 801 if (rp = regtab[i]) 802 if (rp->isset && !(rp->istemp || rp->isarrayarg)) 803 { 804 ap = (Addrp) cpexpr(rp->stgp); 805 changetoreg(ap, i); 806 appendassign(doend, cpexpr(rp->stgp), ap); 807 } 808 809 docount = 1; 810 clearmems(); 811 setregs(); 812 sp = dohead->next; 813 if (loopcost) 814 for (i = toptrack + 1; i <= topregvar; i++) 815 if ((rp = regtab[i]) && !rp->isarrayarg) 816 { 817 ap = (Addrp) cpexpr(rp->stgp); 818 changetoreg(ap, i); 819 insertassign(sp, cpexpr(rp->stgp), ap); 820 } 821 822 for ( sp = dohead->next; 823 docount || sp->type != SKNULL; 824 sp = sp->next) 825 if (docount > 1) 826 switch (sp->type) 827 { 828 case SKDOHEAD: 829 docount++; 830 break; 831 832 case SKENDDO: 833 if (--docount == 1) 834 { 835 /* 836 * Remove redundant stores to memory. 837 */ 838 sp1 = sp->nullslot->next; 839 while (sp1) 840 { 841 if (regtomem(sp1)) 842 { 843 ap = (Addrp) sp1->expr->exprblock.rightp; 844 sp2 = sp1->next; 845 for (i = toplcv + 2; i <= toptrack; i++) 846 if (regtab[i] && (regnum[i] == ap->memno)) 847 { 848 deleteslot(sp1); 849 break; 850 } 851 sp1 = sp2; 852 } 853 else 854 sp1 = NULL; 855 } 856 857 /* 858 * Restore register variables (complement to DOHEAD code). 859 */ 860 sp1 = sp->nullslot->next; 861 for (i = toplcv + 1; i <= topregvar; i++) 862 if (rp = regtab[i]) 863 if (!regdefined[i]) 864 if (i >= dqp->nregvars || !samevar(rp, dqp->reg[i])) 865 { 866 ap = (Addrp) cpexpr(rp->stgp); 867 changetoreg(ap, i); 868 insertassign(sp1, ap, cpexpr(rp->stgp)); 869 regdefined[i] = YES; 870 } 871 872 clearmems(); 873 if (toplcv + 1 < maxregvar) 874 memdefined[toplcv + 1] = YES; 875 sp = sp1->prev; 876 } 877 break; 878 } 879 else 880 { 881 setregs(); 882 for (i = 0; i <= MAXREGVAR; i++) 883 regaltered[i] = NO; 884 globalbranch = NO; 885 886 switch (sp->type) 887 { 888 case SKLABEL: 889 clearmems(); 890 break; 891 892 case SKGOTO: 893 if (!locallabel(sp->label)) 894 gensetall(sp); 895 break; 896 897 case SKENDDO: 898 docount = 0; 899 break; 900 901 case SKRETURN: 902 gensetreturn(sp); 903 linearcode = YES; 904 regwrite(sp, sp->expr); 905 linearcode = NO; 906 break; 907 908 case SKDOHEAD: 909 /* 910 * If one of the current loop's register variables is not in 911 * register in an inner loop, we must save it. It's a pity 912 * we don't save enough info to optimize this properly... 913 */ 914 for (dqp = dqptr->down; dqp; dqp = dqp->down) 915 if (dqp->dohead == sp) 916 break; 917 if (dqp == NULL) 918 fatal("confused in alreg loop analysis"); 919 for (i = toplcv + 1; i <= topregvar; i++) 920 if (rp = regtab[i]) 921 if (!memdefined[i]) 922 if (i >= dqp->nregvars || !samevar(rp, dqp->reg[i])) 923 { 924 ap = (Addrp) cpexpr(rp->stgp); 925 changetoreg(ap, i); 926 insertassign(sp, cpexpr(rp->stgp), ap); 927 memdefined[i] = YES; 928 regdefined[i] = NO; 929 } 930 931 docount++; 932 globalbranch = YES; 933 break; 934 935 case SKEQ: 936 case SKCALL: 937 case SKSTOP: 938 case SKPAUSE: 939 linearcode = YES; 940 regwrite(sp, sp->expr); 941 for (i = toplcv + 1; i <= topregvar; i++) 942 if (!regdefined[i] && ((rp = regtab[i]) && rp->isset)) 943 { 944 ap = (Addrp) cpexpr(rp->stgp); 945 changetoreg(ap, i); 946 appendassign(sp, ap, cpexpr(rp->stgp)); 947 sp = sp->next; 948 regdefined[i] = YES; 949 } 950 linearcode = NO; 951 952 /* 953 * Eliminate redundant register moves. 954 */ 955 if (regtoreg(sp)) 956 { 957 ap = (Addrp) sp->expr->exprblock.leftp; 958 sp1 = sp->prev; 959 for (i = toplcv + 1; i <= toptrack; i++) 960 if (regtab[i] && (regnum[i] == ap->memno)) 961 { 962 deleteslot(sp); 963 sp = sp1; 964 break; 965 } 966 } 967 break; 968 969 case SKARIF: 970 if (!locallabel(LM) || !locallabel(LZ) || !locallabel(LP)) 971 { 972 gensetall(sp); 973 globalbranch = YES; 974 } 975 regwrite(sp, sp->expr); 976 break; 977 978 case SKASGOTO: 979 gensetall(sp); 980 globalbranch = YES; 981 regwrite(sp, sp->expr); 982 break; 983 984 case SKCMGOTO: 985 lp = (struct Labelblock **) sp->ctlinfo; 986 for (i = 0; i < sp->label; i++, lp++) 987 if (!locallabel((*lp)->labelno)) 988 { 989 gensetall(sp); 990 globalbranch = YES; 991 break; 992 } 993 regwrite(sp, sp->expr); 994 break; 995 996 case SKIFN: 997 case SKIOIFN: 998 if (!locallabel(sp->label)) 999 { 1000 gensetall(sp); 1001 globalbranch = YES; 1002 } 1003 regwrite(sp, sp->expr); 1004 break; 1005 1006 case SKNULL: 1007 case SKASSIGN: 1008 break; 1009 1010 default: 1011 badthing ("SKtype","alreg-3",sp->type); 1012 } 1013 1014 for (i = toplcv + 1; i <= topregvar; i++) 1015 if (regaltered[i]) 1016 memdefined[i] = NO; 1017 } 1018 1019 if (topregvar + 1 > highregvar) 1020 highregvar = topregvar + 1; 1021 dqptr->nregvars = topregvar + 1; 1022 for (i = 0; i <= topregvar; i++) 1023 if (rp = regtab[i]) 1024 { 1025 dqptr->reg[i] = regp = ALLOC(regnode); 1026 regp->vstg = rp->vstg; 1027 regp->vtype = rp->vtype; 1028 regp->memno = rp->memno; 1029 regp->memoffset = rp->memoffset; 1030 regp->isarrayarg = rp->isarrayarg; 1031 frexpr(rp->stgp); 1032 free((char *) rp); 1033 regtab[i] = NULL; 1034 } 1035 1036 while (tabletop >= 0) 1037 free((char *) rt[tabletop--]); 1038 freelabtab(); 1039 freevartab(); 1040 return; 1041 } 1042 1043 1044 1045 LOCAL scanvars(p) 1046 expptr p; 1047 1048 { 1049 Addrp ap; 1050 ADDRNODE *addrinfo; 1051 VARNODE *varinfo; 1052 chainp args; 1053 VARNODE *q; 1054 1055 if (p == NULL) return; 1056 1057 switch (p->tag) 1058 { 1059 case TCONST: 1060 return; 1061 1062 case TEXPR: 1063 switch (p->exprblock.opcode) 1064 { 1065 case OPASSIGN: 1066 scanassign(p); 1067 return; 1068 1069 case OPPLUSEQ: 1070 case OPSTAREQ: 1071 scanopeq(p); 1072 return; 1073 1074 case OPCALL: 1075 scancall(p); 1076 return; 1077 1078 default: 1079 scanvars(p->exprblock.vleng); 1080 scanvars(p->exprblock.leftp); 1081 scanvars(p->exprblock.rightp); 1082 return; 1083 } 1084 1085 case TADDR: 1086 ap = (Addrp) p; 1087 scanvars(ap->vleng); 1088 scanvars(ap->memoffset); 1089 if (!ISVAR(ap)) return; 1090 1091 addrinfo = getaddr(ap); 1092 if (fixedaddress(ap)) 1093 { 1094 if (ISREGTYPE(ap->vtype)) 1095 { 1096 varinfo = getvar(addrinfo, ap); 1097 varinfo->isused = YES; 1098 } 1099 } 1100 else 1101 { 1102 addrinfo->freeuse = YES; 1103 for (q = addrinfo->varlist; q; q = q->link) 1104 q->isused = YES; 1105 } 1106 return; 1107 1108 case TLIST: 1109 for (args = p->listblock.listp; args; args = args->nextp) 1110 scanvars(args->datap); 1111 return; 1112 1113 default: 1114 badtag ("regalloc:scanvars", p->tag); 1115 } 1116 } 1117 1118 1119 1120 LOCAL scanassign(ep) 1121 Exprp ep; 1122 1123 { 1124 Addrp lhs; 1125 VARNODE *varinfo; 1126 ADDRNODE *addrinfo; 1127 1128 scanvars(ep->rightp); 1129 if (ep->leftp->tag == TADDR) 1130 { 1131 lhs = (Addrp) ep->leftp; 1132 scanvars(lhs->vleng); 1133 scanvars(lhs->memoffset); 1134 if ((lhs->vstg == STGREG) || (lhs->vstg == STGPREG)) 1135 return; 1136 if (ISVAR(lhs)) 1137 { 1138 addrinfo = getaddr(lhs); 1139 addrinfo->isset = YES; 1140 if (docount > 1) 1141 addrinfo->loopset = YES; 1142 if (fixedaddress(lhs) && ISREGTYPE(lhs->vtype)) 1143 { 1144 varinfo = getvar(addrinfo, lhs); 1145 if (addrinfo->freeuse) varinfo->isused = YES; 1146 varinfo->isset = YES; 1147 if (!addrinfo->freeuse && !varinfo->isused) 1148 varinfo->setfirst = YES; 1149 } 1150 } 1151 } 1152 else 1153 badtag ("regalloc:scanassign", ep->leftp->tag); 1154 } 1155 1156 1157 1158 LOCAL scanopeq(ep) 1159 Exprp ep; 1160 1161 { 1162 Addrp lhs; 1163 ADDRNODE *addrinfo; 1164 VARNODE *varinfo; 1165 1166 scanvars(ep->rightp); 1167 if (ep->leftp->tag == TADDR) 1168 { 1169 lhs = (Addrp) ep->leftp; 1170 scanvars(lhs->vleng); 1171 scanvars(lhs->memoffset); 1172 if ((lhs->vstg == STGREG) || (lhs->vstg == STGPREG)) 1173 return; 1174 if (ISVAR(lhs)) 1175 { 1176 addrinfo = getaddr(lhs); 1177 addrinfo->isset = YES; 1178 if (docount > 1) 1179 addrinfo->loopset = YES; 1180 if (fixedaddress(lhs)) 1181 { 1182 if (ISREGTYPE(lhs->vtype)) 1183 { 1184 varinfo = getvar(addrinfo, lhs); 1185 varinfo->isused = YES; 1186 varinfo->isset = YES; 1187 } 1188 } 1189 } 1190 else 1191 addrinfo->freeuse = YES; 1192 } 1193 else 1194 badtag ("regalloc:scanopeq", ep->leftp->tag); 1195 } 1196 1197 1198 1199 LOCAL scancall(ep) 1200 Exprp ep; 1201 1202 { 1203 Addrp lhs; 1204 chainp args; 1205 Addrp ap; 1206 VARNODE *varinfo; 1207 ADDRNODE *addrinfo; 1208 1209 lhs = (Addrp) ep->leftp; 1210 scanvars(lhs->vleng); 1211 scanvars(lhs->memoffset); 1212 1213 if (ep->rightp == NULL) return; 1214 1215 if (lhs->vstg != STGINTR) 1216 { 1217 args = ep->rightp->listblock.listp; 1218 for (; args; args = args->nextp) 1219 { 1220 if (args->datap->tag == TADDR) 1221 { 1222 ap = (Addrp) args->datap; 1223 scanvars(ap->vleng); 1224 scanvars(ap->memoffset); 1225 if (!ISVAR(ap)) continue; 1226 1227 addrinfo = getaddr(ap); 1228 addrinfo->isset = YES; 1229 if (docount > 1) 1230 addrinfo->loopset = YES; 1231 if (fixedaddress(ap)) 1232 { 1233 varinfo = getvar(addrinfo, ap); 1234 if (ap->vstg != STGCONST) 1235 varinfo->isset = YES; 1236 varinfo->isused = YES; 1237 } 1238 else 1239 addrinfo->freeuse = YES; 1240 } 1241 else 1242 scanvars(args->datap); 1243 } 1244 } 1245 else 1246 scanvars(ep->rightp); 1247 1248 return; 1249 } 1250 1251 1252 1253 LOCAL int fixedaddress(ap) 1254 Addrp ap; 1255 1256 { 1257 if (!ap->memoffset) 1258 return NO; 1259 return (ISCONST(ap->memoffset) && ISINT(ap->memoffset->headblock.vtype)); 1260 } 1261 1262 1263 1264 LOCAL countrefs(p) 1265 expptr p; 1266 1267 { 1268 Addrp ap; 1269 ADDRNODE *addrinfo; 1270 VARNODE *varinfo; 1271 VARNODE *vp; 1272 chainp args; 1273 1274 if (p == NULL) return; 1275 1276 switch (p->tag) 1277 { 1278 case TCONST: 1279 return; 1280 1281 case TEXPR: 1282 switch (p->exprblock.opcode) 1283 { 1284 case OPCALL: 1285 if (p->exprblock.leftp->tag != TADDR) 1286 badtag ("regalloc:countrefs", p->exprblock.leftp->tag); 1287 countrefs(p->exprblock.leftp->addrblock.vleng); 1288 countrefs(p->exprblock.leftp->addrblock.memoffset); 1289 1290 if (p->exprblock.leftp->addrblock.vstg != STGINTR) 1291 { 1292 if (!commonunusable) 1293 if (linearcode) 1294 setcommon(); 1295 else 1296 commonunusable = YES; 1297 if (p->exprblock.rightp == NULL) return; 1298 args = p->exprblock.rightp->listblock.listp; 1299 for (; args; args = args->nextp) 1300 if (args->datap->tag == TADDR) 1301 { 1302 ap = (Addrp) args->datap; 1303 countrefs(ap->vleng); 1304 countrefs(ap->memoffset); 1305 if (!ISVAR(ap) || ap->vstg == STGCONST) continue; 1306 addrinfo = lookupaddr(ap->vstg, ap->memno); 1307 if (ap->vstg == STGARG) 1308 addrinfo->refs++; 1309 for (vp = addrinfo->varlist; vp; vp = vp->link) 1310 if (linearcode) 1311 if (!insetlist(ap->vstg, ap->memno, vp->memoffset)) 1312 if (addrinfo->istemp) 1313 vp->refs--; 1314 else 1315 { 1316 vp->refs -= 2; 1317 insertset(ap->vstg, ap->memno, vp->memoffset); 1318 } 1319 else 1320 vp->refs--; 1321 else 1322 { 1323 if (!addrinfo->istemp) 1324 vp->unusable = YES; 1325 } 1326 } 1327 else 1328 countrefs(args->datap); 1329 } 1330 else 1331 { 1332 if (p->exprblock.rightp == NULL) return; 1333 args = p->exprblock.rightp->listblock.listp; 1334 for (; args; args = args->nextp) 1335 if (args->datap->tag == TADDR) 1336 { 1337 ap = (Addrp) args->datap; 1338 countrefs(ap->vleng); 1339 countrefs(ap->memoffset); 1340 if (!ISVAR(ap) || ap->vstg == STGCONST) continue; 1341 addrinfo = lookupaddr(ap->vstg, ap->memno); 1342 addrinfo->refs++; 1343 for (vp = addrinfo->varlist; vp; vp = vp->link) 1344 if (!insetlist(ap->vstg, ap->memno, vp->memoffset)) 1345 { 1346 vp->refs--; 1347 insertset(ap->vstg, ap->memno, vp->memoffset); 1348 } 1349 } 1350 else 1351 countrefs(args->datap); 1352 } 1353 return; 1354 1355 case OPASSIGN: 1356 case OPPLUSEQ: 1357 case OPSTAREQ: 1358 countrefs(p->exprblock.vleng); 1359 countrefs(p->exprblock.rightp); 1360 ap = (Addrp) p->exprblock.leftp; 1361 if (fixedaddress(ap)) 1362 if (globalbranch) 1363 { 1364 countrefs(ap->vleng); 1365 countrefs(ap->memoffset); 1366 } 1367 else 1368 countrefs(ap); 1369 else if (linearcode) 1370 { 1371 countrefs(ap); 1372 for (vp = lookupaddr(ap->vstg, ap->memno)->varlist; 1373 vp; 1374 vp = vp->link) 1375 vp->refs--; 1376 } 1377 else 1378 { 1379 countrefs(ap); 1380 for (vp = lookupaddr(ap->vstg, ap->memno)->varlist; 1381 vp; 1382 vp = vp->link) 1383 vp->unusable = YES; 1384 } 1385 return; 1386 1387 default: 1388 countrefs(p->exprblock.vleng); 1389 countrefs(p->exprblock.leftp); 1390 countrefs(p->exprblock.rightp); 1391 return; 1392 } 1393 1394 case TADDR: 1395 ap = (Addrp) p; 1396 countrefs(ap->vleng); 1397 countrefs(ap->memoffset); 1398 if (!ISVAR(ap)) return; 1399 1400 addrinfo = lookupaddr(ap->vstg, ap->memno); 1401 if (ap->vstg == STGARG) 1402 addrinfo->refs++; 1403 1404 if (fixedaddress(ap)) 1405 { 1406 if (ISREGTYPE(ap->vtype)) 1407 { 1408 varinfo = lookupvar(addrinfo, ap->memoffset->constblock.constant.ci); 1409 varinfo->refs++; 1410 } 1411 } 1412 else 1413 for (vp = addrinfo->varlist; vp; vp = vp->link) 1414 if (!insetlist(ap->vstg, ap->memno, vp->memoffset)) 1415 { 1416 vp->refs--; 1417 insertset(ap->vstg, ap->memno, vp->memoffset); 1418 } 1419 return; 1420 1421 case TLIST: 1422 args = p->listblock.listp; 1423 for (; args; args = args->nextp) 1424 countrefs(args->datap); 1425 return; 1426 1427 default: 1428 badtag ("regalloc:countrefs", p->tag); 1429 } 1430 } 1431 1432 1433 1434 LOCAL regwrite(sp, p) 1435 Slotp sp; 1436 expptr p; 1437 1438 { 1439 register int i; 1440 REGDATA *rp; 1441 chainp args; 1442 Addrp ap, ap1; 1443 int memoffset; 1444 1445 if (p == NULL) return; 1446 1447 switch (p->tag) 1448 { 1449 case TCONST: 1450 return; 1451 1452 case TEXPR: 1453 switch (p->exprblock.opcode) 1454 { 1455 case OPCALL: 1456 ap = (Addrp) p->exprblock.leftp; 1457 regwrite(sp, ap->vleng); 1458 regwrite(sp, ap->memoffset); 1459 if (ap->vstg != STGINTR) 1460 { 1461 if (linearcode) 1462 { 1463 gensetcommon(sp); 1464 for (i = toplcv + 1; i <= topregvar; i++) 1465 if ((rp = regtab[i]) && (rp->vstg == STGCOMMON)) 1466 regdefined[i] = NO; 1467 } 1468 if (p->exprblock.rightp == NULL) return; 1469 args = p->exprblock.rightp->listblock.listp; 1470 for (; args; args = args->nextp) 1471 if (args->datap->tag == TADDR) 1472 { 1473 ap = (Addrp) args->datap; 1474 regwrite(sp, ap->vleng); 1475 regwrite(sp, ap->memoffset); 1476 for (i = toplcv + 1; i <= topregvar; i++) 1477 if ((rp = regtab[i]) && 1478 !rp->isarrayarg && 1479 !rp->istemp && 1480 (rp->vstg == ap->vstg) && 1481 (rp->memno == ap->memno)) 1482 { 1483 regdefined[i] = NO; 1484 if (!memdefined[i]) 1485 { 1486 ap1 = (Addrp) cpexpr(rp->stgp); 1487 changetoreg(ap1, i); 1488 insertassign(sp, cpexpr(rp->stgp), ap1); 1489 memdefined[i] = YES; 1490 } 1491 } 1492 else if (rp->isarrayarg && 1493 (ap->vstg == STGARG) && 1494 (ap->memno == rp->memno)) 1495 { 1496 ap->vstg = STGPREG; 1497 ap->memno = regnum[i]; 1498 } 1499 } 1500 else 1501 regwrite(sp, args->datap); 1502 } 1503 else 1504 { 1505 if (p->exprblock.rightp == NULL) return; 1506 args = p->exprblock.rightp->listblock.listp; 1507 for (; args; args = args->nextp) 1508 if (args->datap->tag == TADDR) 1509 { 1510 ap = (Addrp) args->datap; 1511 regwrite(sp, ap->vleng); 1512 regwrite(sp, ap->memoffset); 1513 for (i = toplcv + 1; i <= topregvar; i++) 1514 if ((rp = regtab[i]) && 1515 !rp->isarrayarg && 1516 !rp->istemp && 1517 (rp->vstg == ap->vstg) && 1518 (rp->memno == ap->memno) && 1519 !memdefined[i]) 1520 { 1521 ap1 = (Addrp) cpexpr(rp->stgp); 1522 changetoreg(ap1, i); 1523 insertassign(sp, cpexpr(rp->stgp), ap1); 1524 memdefined[i] = YES; 1525 } 1526 else if (rp->isarrayarg && 1527 (ap->vstg == STGARG) && 1528 (rp->memno == ap->memno)) 1529 { 1530 ap->vstg = STGPREG; 1531 ap->memno = regnum[i]; 1532 } 1533 } 1534 else 1535 { 1536 regwrite(sp, args->datap); 1537 } 1538 } 1539 return; 1540 1541 case OPASSIGN: 1542 case OPPLUSEQ: 1543 case OPSTAREQ: 1544 regwrite(sp, p->exprblock.vleng); 1545 regwrite(sp, p->exprblock.rightp); 1546 ap = (Addrp) p->exprblock.leftp; 1547 regwrite(sp, ap->vleng); 1548 regwrite(sp, ap->memoffset); 1549 1550 if (ap->vstg == STGARG) 1551 for (i = toplcv + 1; i<=topregvar; i++) 1552 if ((rp = regtab[i]) && 1553 rp->isarrayarg && 1554 (rp->memno == ap->memno)) 1555 { 1556 ap->vstg = STGPREG; 1557 ap->memno = regnum[i]; 1558 return; 1559 } 1560 1561 if (fixedaddress(ap)) 1562 { 1563 memoffset = ap->memoffset->constblock.constant.ci; 1564 for (i = toplcv + 1; i <= topregvar; i++) 1565 if ((rp = regtab[i]) && 1566 !rp->isarrayarg && 1567 (rp->vstg == ap->vstg) && 1568 (rp->memno == ap->memno) && 1569 (rp->memoffset == memoffset)) 1570 { 1571 changetoreg(ap, i); 1572 if (globalbranch) 1573 { 1574 p->exprblock.rightp = (expptr) cpexpr(p); 1575 p->exprblock.leftp = (expptr) cpexpr(rp->stgp); 1576 p->exprblock.opcode = OPASSIGN; 1577 memdefined[i] = YES; 1578 } 1579 else 1580 { 1581 regaltered[i] = YES; 1582 regdefined[i] = YES; 1583 } 1584 } 1585 return; 1586 } 1587 1588 if (linearcode) 1589 for (i = toplcv + 1; i <= topregvar; i++) 1590 if ((rp = regtab[i]) && 1591 !rp->isarrayarg && 1592 (rp->vstg == ap->vstg) && 1593 (rp->memno == ap->memno)) 1594 regdefined[i] = NO; 1595 return; 1596 1597 default: 1598 regwrite(sp, p->exprblock.vleng); 1599 regwrite(sp, p->exprblock.leftp); 1600 regwrite(sp, p->exprblock.rightp); 1601 return; 1602 } 1603 1604 case TADDR: 1605 ap = (Addrp) p; 1606 regwrite(sp, ap->vleng); 1607 regwrite(sp, ap->memoffset); 1608 1609 if (ap->vstg == STGARG) 1610 for (i = toplcv + 1; i <= topregvar; i++) 1611 if ((rp = regtab[i]) && 1612 rp->isarrayarg && 1613 (rp->memno == ap->memno)) 1614 { 1615 ap->vstg = STGPREG; 1616 ap->memno = regnum[i]; 1617 return; 1618 } 1619 1620 if (fixedaddress(ap)) 1621 { 1622 memoffset = ap->memoffset->constblock.constant.ci; 1623 for (i = toplcv + 1; i <= topregvar; i++) 1624 if ((rp = regtab[i]) && 1625 !rp->isarrayarg && 1626 (rp->vstg == ap->vstg) && 1627 (rp->memno == ap->memno) && 1628 (rp->memoffset == memoffset)) 1629 { 1630 changetoreg(ap, i); 1631 return; 1632 } 1633 } 1634 else 1635 { 1636 for (i = toplcv + 1; i <= topregvar; i++) 1637 if ((rp = regtab[i]) && 1638 !rp->isarrayarg && 1639 (rp->vstg == ap->vstg) && 1640 (rp->memno == ap->memno) && 1641 !memdefined[i]) 1642 { 1643 ap1 = (Addrp) cpexpr(rp->stgp); 1644 changetoreg(ap1, i); 1645 insertassign(sp, cpexpr(rp->stgp), ap1); 1646 memdefined[i] = YES; 1647 } 1648 } 1649 return; 1650 1651 case TLIST: 1652 for (args = p->listblock.listp; args; args = args->nextp) 1653 regwrite(sp, args->datap); 1654 return; 1655 1656 default: 1657 badtag ("regalloc:regwrite", p->tag); 1658 } 1659 } 1660 1661 1662 1663 LOCAL setcommon() 1664 1665 { 1666 ADDRNODE *ap; 1667 VARNODE *vp; 1668 1669 for (ap = commonvars; ap; ap = ap->commonlink) 1670 for (vp = ap->varlist; vp; vp = vp->link) 1671 if (!insetlist(ap->vstg, ap->memno, vp->memoffset)) 1672 { 1673 vp->refs -= 2; 1674 insertset(ap->vstg, ap->memno, vp->memoffset); 1675 } 1676 else 1677 vp->refs--; 1678 1679 return; 1680 } 1681 1682 1683 1684 LOCAL setall() 1685 1686 { 1687 register int i; 1688 register ADDRNODE *p; 1689 register VARNODE *q; 1690 1691 for (i = 0; i < VARTABSIZE; i++) 1692 for (p = vartable[i]; p; p = p->link) 1693 if (p->istemp || !p->isset) 1694 break; 1695 else 1696 for (q = p->varlist; q; q = q->link) 1697 if (q->isset && !insetlist(p->vstg, p->memno, q->memoffset)) 1698 q->refs--; 1699 1700 allset = YES; 1701 return; 1702 } 1703 1704 1705 1706 LOCAL int samevar(r1, r2) 1707 register REGDATA *r1; 1708 register REGNODE *r2; 1709 1710 { 1711 if ((r1->vstg != r2->vstg) || 1712 (r1->memno != r2->memno) || 1713 (r1->isarrayarg != r2->isarrayarg)) 1714 return NO; 1715 if (r1->isarrayarg) 1716 return YES; 1717 return (r1->memoffset == r2->memoffset); 1718 } 1719 1720 1721 1722 LOCAL entableaddr(p) 1723 ADDRNODE *p; 1724 1725 { 1726 int refs; 1727 Addrp ap; 1728 register int i; 1729 1730 if (p->vstg != STGARG) 1731 { 1732 currentaddr = p; 1733 return; 1734 } 1735 1736 refs = p->refs; 1737 if (refs <= 0) return; 1738 1739 if (tabletop < 0) 1740 tabletop = i = 0; 1741 else if (refs > rt[tabletop]->refs) 1742 { 1743 if (tabletop + 1 < TABLELIMIT) 1744 tabletop++; 1745 else 1746 { 1747 frexpr(rt[tabletop]->stgp); 1748 free((char *) rt[tabletop]); 1749 } 1750 1751 for (i = tabletop; i > 0; i--) 1752 if (refs > rt[i - 1]->refs) 1753 rt[i] = rt[i - 1]; 1754 else 1755 break; 1756 } 1757 else if (tabletop + 1 < TABLELIMIT) 1758 i = ++tabletop; 1759 else 1760 return; 1761 1762 rt[i] = ALLOC(regdata); 1763 rt[i]->vstg = p->vstg; 1764 rt[i]->vtype = p->vtype; 1765 rt[i]->memno = p->memno; 1766 rt[i]->refs = refs; 1767 rt[i]->isarrayarg = YES; 1768 1769 return; 1770 } 1771 1772 1773 1774 1775 LOCAL entablevar(p) 1776 VARNODE *p; 1777 1778 { 1779 int refs; 1780 register int i; 1781 1782 if (p->unusable) return; 1783 refs = p->refs - loopcost; 1784 if (refs <= 0) return; 1785 1786 if (tabletop < 0) 1787 tabletop = i = 0; 1788 else if (refs > rt[tabletop]->refs 1789 #ifdef BUMPREALS /* put floats last */ 1790 || currentaddr->vtype!=TYREAL && rt[tabletop]->vtype==TYREAL && !rt[tabletop]->isarrayarg 1791 #endif 1792 ){ 1793 if (tabletop + 1 < TABLELIMIT) 1794 tabletop++; 1795 else 1796 { 1797 frexpr(rt[tabletop]->stgp); 1798 free((char *) rt[tabletop]); 1799 } 1800 1801 for (i = tabletop; i > 0; i--) 1802 if (refs > rt[i - 1]->refs 1803 #ifdef BUMPREALS /* put floats last */ 1804 || currentaddr->vtype!=TYREAL && rt[i-1]->vtype==TYREAL && !rt[i-1]->isarrayarg 1805 #endif 1806 ) 1807 rt[i] = rt[i - 1]; 1808 else 1809 break; 1810 } 1811 else if (tabletop + 1 < TABLELIMIT) 1812 i = ++tabletop; 1813 else 1814 return; 1815 1816 rt[i] = ALLOC(regdata); 1817 rt[i]->vstg = currentaddr->vstg; 1818 rt[i]->vtype = currentaddr->vtype; 1819 rt[i]->memno = currentaddr->memno; 1820 rt[i]->memoffset = p->memoffset; 1821 rt[i]->refs = refs; 1822 rt[i]->stgp = (Addrp) cpexpr(p->stgp); 1823 rt[i]->isarrayarg = NO; 1824 rt[i]->istemp = currentaddr->istemp; 1825 rt[i]->isset = p->isset; 1826 rt[i]->setfirst = p->setfirst; 1827 1828 return; 1829 } 1830 1831 1832 1833 LOCAL int inregtab(p) 1834 register REGDATA *p; 1835 1836 { 1837 register REGDATA *rp; 1838 register int i; 1839 1840 for (i = 0; i <= topregvar; i++) 1841 if (rp = regtab[i]) 1842 if ((rp->vstg == p->vstg) && 1843 (rp->memno == p->memno) && 1844 (rp->isarrayarg == p->isarrayarg)) 1845 if (rp->isarrayarg) 1846 return YES; 1847 else if (rp->memoffset == p->memoffset) 1848 return YES; 1849 1850 return NO; 1851 } 1852 1853 1854 1855 LOCAL changetoreg(ap, i) 1856 register Addrp ap; 1857 int i; 1858 1859 { 1860 ap->vstg = STGREG; 1861 ap->memno = regnum[i]; 1862 frexpr(ap->memoffset); 1863 ap->memoffset = ICON(0); 1864 ap->istemp = NO; 1865 return; 1866 } 1867 1868 1869 1870 LOCAL insertassign(sp, dest, src) 1871 Slotp sp; 1872 Addrp dest; 1873 expptr src; 1874 1875 { 1876 Slotp newslot; 1877 expptr p; 1878 1879 p = mkexpr(OPASSIGN, dest, src); 1880 newslot = optinsert (SKEQ,p,0,0,sp); 1881 1882 if (sp == dohead) 1883 if (!newcode) 1884 newcode = newslot; 1885 1886 return; 1887 } 1888 1889 1890 LOCAL appendassign(sp, dest, src) 1891 Slotp sp; 1892 Addrp dest; 1893 expptr src; 1894 1895 { 1896 Slotp newslot; 1897 expptr p; 1898 1899 if (!sp) 1900 fatal ("regalloc:appendassign"); 1901 1902 p = mkexpr(OPASSIGN, dest, src); 1903 newslot = optinsert (SKEQ,p,0,0,sp->next); 1904 1905 return; 1906 } 1907 1908 1909 1910 LOCAL int regtomem(sp) 1911 Slotp sp; 1912 1913 { 1914 expptr p, l, r; 1915 int i; 1916 1917 if (sp->type != SKEQ) return NO; 1918 1919 p = sp->expr; 1920 if ((p->tag != TEXPR) || (p->exprblock.opcode != OPASSIGN)) 1921 return NO; 1922 1923 r = p->exprblock.rightp; 1924 if ((r->tag != TADDR) || (r->addrblock.vstg != STGREG)) 1925 return NO; 1926 1927 l = p->exprblock.leftp; 1928 if (l->tag != TADDR) 1929 return NO; 1930 i = r->addrblock.memno; 1931 if (regtab[i] && 1932 (l->addrblock.vstg == regtab[i]->vstg) && 1933 (l->addrblock.memno == regtab[i]->memno) && 1934 fixedaddress(l) && 1935 (l->addrblock.memoffset->constblock.constant.ci == regtab[i]->memoffset)) 1936 return YES; 1937 1938 return NO; 1939 } 1940 1941 1942 1943 LOCAL int regtoreg(sp) 1944 Slotp sp; 1945 1946 { 1947 expptr p, l, r; 1948 1949 if (sp->type != SKEQ) return NO; 1950 1951 p = sp->expr; 1952 if ((p->tag != TEXPR) || (p->exprblock.opcode != OPASSIGN)) 1953 return NO; 1954 1955 l = p->exprblock.leftp; 1956 if ((l->tag != TADDR) || (l->addrblock.vstg != STGREG)) 1957 return NO; 1958 1959 r = p->exprblock.rightp; 1960 if ((r->tag == TADDR) && 1961 (r->addrblock.vstg == STGREG) && 1962 (r->addrblock.memno == l->addrblock.memno)) 1963 return YES; 1964 1965 if ((r->tag == TEXPR) && 1966 (r->exprblock.opcode == OPADDR) && 1967 (r->exprblock.leftp->tag == TADDR) && 1968 (r->exprblock.leftp->addrblock.vstg == STGPREG) && 1969 (r->exprblock.leftp->addrblock.memno == l->addrblock.memno)) 1970 return YES; 1971 1972 return NO; 1973 } 1974 1975 1976 1977 LOCAL deleteslot(sp) 1978 Slotp sp; 1979 1980 { 1981 if (newcode == sp) 1982 { 1983 newcode = sp->next; 1984 if (newcode == dohead) 1985 newcode = NULL; 1986 } 1987 1988 delslot (sp); 1989 return; 1990 } 1991 1992 1993 1994 LOCAL gensetall(sp) 1995 Slotp sp; 1996 1997 { 1998 register int i; 1999 register REGDATA *rp; 2000 register Addrp ap; 2001 2002 for (i = toplcv + 1; i <= topregvar; i++) 2003 if (rp = regtab[i]) 2004 if (rp->isset && !(rp->istemp || rp->isarrayarg)) 2005 if (!memdefined[i]) 2006 { 2007 ap = (Addrp) cpexpr(rp->stgp); 2008 changetoreg(ap, i); 2009 insertassign(sp, cpexpr(rp->stgp), ap); 2010 memdefined[i] = YES; 2011 } 2012 2013 return; 2014 } 2015 2016 2017 LOCAL gensetcommon(sp) 2018 Slotp sp; 2019 2020 { 2021 register int i; 2022 register REGDATA *rp; 2023 register Addrp ap; 2024 2025 for (i = toplcv + 1; i <= topregvar; i++) 2026 if (rp = regtab[i]) 2027 if ((rp->vstg == STGCOMMON) && !rp->isarrayarg) 2028 if (!memdefined[i]) 2029 { 2030 ap = (Addrp) cpexpr(rp->stgp); 2031 changetoreg(ap, i); 2032 insertassign(sp, cpexpr(rp->stgp), ap); 2033 memdefined[i] = YES; 2034 } 2035 2036 return; 2037 } 2038 2039 2040 LOCAL gensetreturn(sp) 2041 Slotp sp; 2042 2043 { 2044 register int i; 2045 register REGDATA *rp; 2046 register Addrp ap; 2047 2048 for (i = toplcv + 1; i <= topregvar; i++) 2049 if (rp = regtab[i]) 2050 if (((rp->vstg == STGCOMMON) && !rp->isarrayarg) 2051 || (rp->isset && (saveall || rp->stgp->issaved) && !(rp->istemp || rp->isarrayarg))) 2052 if (!memdefined[i]) 2053 { 2054 ap = (Addrp) cpexpr(rp->stgp); 2055 changetoreg(ap, i); 2056 insertassign(sp, cpexpr(rp->stgp), ap); 2057 memdefined[i] = YES; 2058 } 2059 2060 return; 2061 } 2062 2063 2064 2065 LOCAL clearmems() 2066 2067 { 2068 REGDATA *rp; 2069 register int i; 2070 2071 for (i = 0; i <= toplcv; i++) 2072 memdefined[i] = YES; 2073 for (; i <= topregvar; i++) 2074 if ((rp = regtab[i]) && rp->isset) 2075 memdefined[i] = NO; 2076 else 2077 memdefined[i] = YES; 2078 return; 2079 } 2080 2081 2082 LOCAL setregs() 2083 2084 { 2085 register int i; 2086 2087 for (i = 0; i <= topregvar; i++) 2088 regdefined[i] = YES; 2089 return; 2090 } 2091 2092 2093 2094 regalloc() 2095 2096 { 2097 int match; 2098 Slotp nextslot; 2099 Slotp sl1,sl2; 2100 Slotp lastlabslot; 2101 2102 if (! optimflag) return; 2103 2104 docount = 0; 2105 lastlabslot = NULL; 2106 for (sl1 = firstslot; sl1; sl1 = nextslot) 2107 { 2108 nextslot = sl1->next; 2109 switch (sl1->type) 2110 { 2111 2112 /* temporarily commented out ----- 2113 case SKLABEL: 2114 lastlabslot = sl1; 2115 break; 2116 2117 case SKGOTO: 2118 if (lastlabslot && sl1->label == lastlabslot->label) 2119 { 2120 dohead = lastlabslot; 2121 doend = sl1; 2122 alreg (); 2123 } 2124 break; 2125 ----- */ 2126 2127 case SKDOHEAD: 2128 ++docount; 2129 pushq (sl1); 2130 break; 2131 2132 case SKENDDO: 2133 --docount; 2134 match = 0; 2135 for (sl2 = sl1; sl2; sl2 = sl2->prev) 2136 { 2137 if (sl2->type == SKDOHEAD) match++; 2138 else if (sl2->type == SKENDDO) match--; 2139 if (match == 0) break; 2140 } 2141 if (sl2) 2142 dohead = sl2; 2143 else 2144 fatal ("unmatched enddo in code buffer"); 2145 if (sl2->type != SKDOHEAD) 2146 fatal ("internal error in regalloc"); 2147 2148 for (dqptr = dqbottom; dqptr; dqptr = dqptr->up) 2149 { 2150 if (dqptr->dohead == dohead) 2151 break; 2152 } 2153 2154 if (!dqptr) 2155 fatal ("garbled doqueue in regalloc"); 2156 2157 /* sl1 now points to the SKENDDO slot; the SKNULL slot 2158 * is reached through sl1->nullslot 2159 */ 2160 dqptr->doend = (Slotp) sl1->nullslot; 2161 if (docount == 0) 2162 { 2163 for (dqptr = dqbottom; dqptr; dqptr = dqptr->up) 2164 { 2165 dohead = dqptr->dohead; 2166 doend = dqptr->doend; 2167 alreg(); 2168 } 2169 while (dqtop) 2170 popq(dqtop->dohead); 2171 docount = 0; 2172 } 2173 break; 2174 2175 default: 2176 break; 2177 } 2178 } 2179 2180 return; 2181 } 2182 2183 2184 2185 LOCAL pushq(sp) 2186 Slotp sp; 2187 2188 { 2189 DOQUEUE *t; 2190 2191 if (sp->type != SKDOHEAD) 2192 fatal("regalloc:pushq: DO statement expected"); 2193 2194 if (dqbottom) 2195 { 2196 t = ALLOC(doqueue); 2197 t->up = dqbottom; 2198 dqbottom->down = t; 2199 dqbottom = t; 2200 } 2201 else 2202 dqtop = dqbottom = ALLOC(doqueue); 2203 2204 dqbottom->dohead = sp; 2205 } 2206 2207 2208 LOCAL popq(sp) 2209 Slotp sp; 2210 2211 { 2212 DOQUEUE *t; 2213 register int i; 2214 2215 if (!dqtop) 2216 fatal("regalloc:popq: empty DO queue"); 2217 if (dqtop->dohead != sp) 2218 fatal("regalloc:popq: garbled DO queue"); 2219 2220 t = dqtop; 2221 2222 dqtop = t->down; 2223 if (dqtop) 2224 dqtop->up = NULL; 2225 else 2226 dqbottom = NULL; 2227 for (i = 0; i < MAXREGVAR; i++) 2228 if (t->reg[i]) 2229 free((char *) t->reg[i]); 2230 free(t); 2231 } 2232