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