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