/************************************************************************/ /* */ /* Copyright (c) 1987, 1988, 1989, 1990, 1991, 1992 - */ /* The Rector and Visitors of the University of Virginia */ /* */ /* This code may not be distributed further without permission */ /* from the University of Virginia. */ /* This code is distributed WITHOUT ANY WARRANTY. No claims are */ /* made as to whether it serves any particular purpose or even */ /* works at all. */ /* */ /************************************************************************/ /************************************************************************ Revision Control information $Source: /home/cvs/cvs/powerpc-vpo/vpo/lib/assign.c,v $ $Date: 2004/08/13 01:48:59 $ $Revision: 1.6 $ $Name: $ Log of changes: $Log: assign.c,v $ Revision 1.6 2004/08/13 01:48:59 avdhoot debugged register allocation for small test cases Revision 1.4 2003/12/24 22:09:32 jpmarath integrated jpm's updates (switch case,millcode) with avd's floating pt support Revision 1.3 2003/11/28 02:34:14 jpmarath changed r0 to be a reserved register, updated front-end output code for right shift, updated cex_name for taking address of an element Revision 1.2 2003/11/12 00:14:00 jpmarath changed function prologue/epilogue for POWER environment Revision 1.1.1.1 2003/10/29 01:00:22 avdhoot power pc version of vpo Revision 1.5 1998/10/06 19:37:29 jwd Added vet support. Revision 1.4 1998/04/28 19:17:16 jwd Added an return (unreachable) to keep compiler from complaining. Revision 1.3 1998/04/03 16:47:01 jwd First ANSI C version. *************************************************************************/ /* ------------------------------------------------ Change history -------------- 7/3/95 Fixed a bug in findreg. The code was using check to index the conflict array. It should have been using loop. It's strange that this never popped up before 1/12/98: Modified the funnction prototyping to be ansi-c compatible with modularity by removing nonlocal prototypes ------------------------------------------------*/ #define ASSIGN 1 #ifdef RRLRA #define CLASSREG #endif #include #include #include "vpo.h" #include "vpo2.h" #include "vectors.h" #include "database.h" #include "misc.h" #include "controlflow.h" #include "links.h" #include "locals.h" #include "dataflow.h" #include "assign.h" #include "regs.h" /* Machine Dependent */ #include "regs2.h" /* Machine Dependent */ #ifdef VET #include "../lib/view.h" #endif int isused[MAXREGS]; /* TRUE if there is a use line for this register */ int usedregs[MAXREGS]; /* TRUE if the register is used as a temporary */ int usedtemps[MAXTEMP]; /* TRUE if the spill area is used by the fuction */ int maxregs = MAXREGS; /* Variable used to pass on the value of MAXREGS */ int mrveclen; /* Length of vector that holds MAXREGS bits */ int hascs; /* Will be set to TRUE if function makes calls */ char *trash_cc = TRASH_CC; /* String needed to trash condition codes */ char *memprt = MEMPRT; /* String needed to determine memory types */ #ifdef VET char oldrtl[300]; #endif #ifdef RRLRA static int lastfound[MAXCLASSES]; /* Last location where register was found */ #endif extern struct bblock *top; /* Personally, I've never understood why an */ extern rlist pseudos; /* extern access statement should have to be */ extern char *bpos, *epos; /* a recomposition of variable arguments, it */ extern char *pc_equ; /* should not involve details of strucure of */ extern int bitsperint; /* the included data ! : JCH */ extern int intscale; extern int int2char; extern int regallocptr; extern int mems[MAXCHARS]; extern int swd; /* * registers_used - scan the function and determines which registers are used */ void registers_used() { register char c; register char *rtlin; register struct list *ptr; register int i; regarray tr; struct bblock *cblk; int rt, rcont; /* First, mark all registers as NOTUSED */ tr = (regarray) top->regstate; for (i = 0; i < MAXREGS; i++) tr->reg[i].status = NOTUSED; /* Now scan through all of the RTLs and determine which registers are still in use. If a register that occupies only a single allocation item is used, then mark it as USED. If a register item requires more than one allocation item or it is a part of a group, then mark each item as FOLLOWER. */ for (cblk = top; cblk; cblk = cblk->down) { for (ptr = cblk->rtls; ptr; ptr = ptr->next) { if (rtlin = cnts(ptr)) { for (;;) { for (c = *rtlin++; (c & 0xc0) != 0xc0 && c; c = *rtlin++); if (!c) break; if (*rtlin & 0x80) { rt = regtype(rtlin - 1); if (headgroup(rt) >= 0) rt = headgroup(rt); i = regtoindex(rt, regnum(rtlin - 1)); rtlin++; rcont = allocreg(rt); if (rcont == 1) tr->reg[i].status |= USED; else { while (rcont--) tr->reg[i++].status |= FOLLOWER; } } } } } } } /* * local_register_assignment - perform local register assignment */ int local_register_assignment(int invocation) { register struct bblock *cblk; register struct list *rtlptr; register int rnum; regarray tr; int change; #ifdef VET begin_phase(REGASSIGN_PHASE); #endif /* Check to see if the user would like to see the state of the function at this point in time. */ if (swd && debug_opt_i("dump_before_local_register_assignment", invocation)) dump_function_i("before local_register_assignment()", invocation, SHOW_DEF | SHOW_USE | SHOW_PREDS | SHOW_NONRTLS | SHOW_SE); /* Clear out all of the global state */ for (rnum = 0; rnum < MAXREGS; rnum++) { isused[rnum] = FALSE; usedregs[rnum] = NOTUSED; } for (rnum = 0; rnum < MAXTEMP; usedtemps[rnum++] = FALSE); #ifdef RRLRA for (rnum = 0; rnum < MAXCLASSES; lastfound[rnum++] = -1); #endif /* Set all basic blocks to UNDONE and mark all registers in use lines */ for (cblk = top; cblk != NULL; cblk = cblk->down) { STATUS(cblk, UNDONE); for (rtlptr = cblk->rtls; rtlptr; rtlptr = rtlptr->next) if (rtlptr->type & USELINE) isused[rtlptr->cost] = TRUE; } /* This item will be set to TRUE at the end of local register allocation only if the current function contains function calls that require the caller to save any live registers at the point of the function call. */ hascs = FALSE; /* Perform local register allocation on the whole function, starting with the entry block of the function. */ change = assign(top); /* Save the state of registers used with the entry block of the function */ regfree(top->regstate); initassign(&top->regstate); tr = (regarray) top->regstate; for (rnum = 0; rnum < MAXREGS; rnum++) tr->reg[rnum].status = usedregs[rnum]; /* Clear out any left over entry state records */ for (cblk = top; cblk; cblk = cblk->down) cblk->elist = (struct eqvtable *) NULL; /* Check to see if the user would like to see the state of the function at this point in time. */ if (swd && debug_opt_i("dump_after_local_register_assignment", invocation)) dump_function_i("after local_register_assignment()", invocation, SHOW_DEF| SHOW_USE | SHOW_PREDS | SHOW_NONRTLS | SHOW_SE); #ifdef VET end_phase(REGASSIGN_PHASE); #endif /* Indicate if any new code has been added during the assignment phase */ return (change); } /* * assign - perform local register assignment */ int assign(register struct bblock * cblk) { register struct blist *bptr; register int go, save_state; int change; /* No changes to begin with */ change = FALSE; /* Set the state of the current basic block to waiting, to indicate that this block is waiting to have local register allocation performed pending the completion of all of the blocks that are predecessors of it (except in the case of loops, of course, in which case one of the blocks in the loop will have to be allocated before all of its predecessors are finished. */ STATUS(cblk, WAITING); /* Set the "go" state to perform local register allocation on a basic block unless it has any live pseudo-registers at the entry point of the basic block. If there are live pseudo-registers, then we check to see there are any predecessor basic blocks that have not yet had local register allocation done on them. If we find any such blocks, then we go ahead and handle them first. If we find a predecessor block that is still waiting, then we have located a loop and we hold off on performing allocation on this basic block until the predecessor block is allocated. */ go = TRUE; save_state = FALSE; if (rcommon(cblk->ulist, pseudos)) { for (bptr = cblk->preds; bptr; bptr = bptr->next) //for each predecessor, check { if (bptr->ptr->status & UNDONE) change |= assign(bptr->ptr); if (bptr->ptr == cblk) save_state = TRUE; else if (bptr->ptr->status & WAITING) go = FALSE; else if (bptr->ptr->status & DORMANT) save_state = TRUE; }//end for }//end if common elements /* If we have been given the go-ahead to perform local register allocation on this basic block, we initialize a local register allocation vector for this basic block, then we handle any conflicts in allocation that may exists between the various predecessors of this basic block. Once that is done, we perform local register allocation on this basic block. Then, we go ahead and attempt to perform local register allocation on any of the children of this basic block that haven't already been allocated. */ if (go) { initassign(&cblk->regstate); solveconflicts(cblk); if (save_state) save_entry(cblk); change |= assign_basic_block(cblk); STATUS(cblk, DONE); if (cblk->left) { if (cblk->left->status & (UNDONE | DORMANT)) change |= assign(cblk->left); else if (cblk->left->elist) loopconflicts(cblk, cblk->left); } if (cblk->right) { if (cblk->right->status & (UNDONE | DORMANT)) change |= assign(cblk->right); else if (cblk->right->elist) loopconflicts(cblk, cblk->right); } } /* Otherwise, we are waiting for a predecessor block to be allocated, so we enter a dormant state and wait for the predecessor block to be allocated first. */ else STATUS(cblk, DORMANT); /* Indicate if any new code has been added to the function */ return (change); } /* * assign_basic_block - perform local register allocation on a basic block */ int assign_basic_block(struct bblock * cblk) { register char *rtl; register int rtnum, update; register struct list *ptr; int change; char *dptr[MAXRTS]; #ifdef VET begin_trans(VET_REQUIRED_TRANS); #endif /* No changes to begin with */ change = FALSE; /* Examine each line of this basic block */ for (ptr = cblk->rtls; ptr; ptr = ptr->next) { /* If this line is an RTL line, then if it has any effects, scan the line and examine each register in the RTL individually. First, look at all register uses. Map all pseudo registers to corresponding hardware registers. If the pseudo register values needed had been spilled to memory, new RTLs may be added to this basic block that load the values from memory. Remember the location of any of the register sets located in the RTL, so that we can come back and deal with them later without having to re-scan the whole RTL. */ if (ptr->type & RTLINE) { if (rtl = ptr->val) { #ifdef VET strcpy(oldrtl, rtl); #endif rtnum = 0; update = FALSE; while (rtl = gtrg(rtl)) { if (*rtl != '=') assoc(cblk, ptr, rtl - 2, &change, FALSE); else{ /* OLD : remember the location and process the items set later AVD : This creates a bug if an additional caller saved register needs to be restored and is being set here. If so then the restore should happen before this set Hence we need to process it first, if the same register is set here */ dptr[rtnum++] = rtl - 2; /* New move the processing here */ while (rtnum--) { assoc(cblk, ptr, dptr[rtnum], &change, TRUE); rdelete(dptr[rtnum], &ptr->deads); } } update = TRUE; } /* Now we deal with the dead register list. This will tell us which registers will no longer be needed, so that we can free up the hardware register that are allocated to them. Note that pseudo-register deaths will be altered to represent the hardware registers that were allocated to them at this point in the basic block. */ dodeads(cblk, &ptr->deads, FALSE); #ifdef VET mod_deads(ptr); #endif /* Now we go back and look at the registers that are set in this RTL. If it is a pseudo-register, it will be mapped to an appropriate hardware register. In some cases, the values currently in some hardware register may have to be spilled in order to make room for the new value that will be assigned to this new register. If the register is a hardware register, the local register allocator will ensure that the indicated hardware register is available to hold the value that is being assigned to it. We also ensure that none of the registers that are set are in the dead register list, since they obviously do not die at this point. */ /* OLD AVD moved up 30 lines While (rtnum--) { assoc(cblk, ptr, dptr[rtnum], &change, TRUE); rdelete(dptr[rtnum], &ptr->deads); } */ /* If we have made any changes to this RTL, we throw away any cost, kind and side effect information that we may have on this RTL, since it may now be invalid. */ if (update) { ptr->cost = 0; ptr->kind = 0; ptr->type &= ~SIDEFFECT; FREE(ptr->se); ptr->se = (char *) NULL; #ifdef VET mod_side(ptr); #endif } #ifdef VET if (strcmp(oldrtl, ptr->val)) mod_rtl(ptr); #endif } //end if rtl != NULL /* If this RTL has no effects, then it may just be here to mark certain registers as dead. We will now free up any such registers, except that in this case we do not leave behind the death of any pseudo-register, even if it was mapped to a hardware register. */ else dodeads(cblk, &ptr->deads, TRUE); #ifdef VET mod_deads(ptr); #endif }//end of if RTLLINE /* A hardware register may be explicitly reserved at any point in time with a reserve line. The effect is that the local register allocator ensures that the register is free and that its value will be preserved until it dies. */ else if (ptr->type & RESLINE) ptr = reserve(cblk, ptr, &change); /* A caller-saves line indicates that the registers indicated must be spilled to memory at this point if they contain valid items. This is used to implement caller-saves calling conventions. */ else if (ptr->type & CSLINE) savregs(cblk, ptr, &change); }//end for #ifdef VET end_trans(); #endif /* Since we are finished with this basic block. We unassociate all our links with the register database, so that another basic block may establish them. */ unassociate(cblk); /* Indicate if any new code has been added to the function */ return (change); } /* * dodeads - examine a dead register list and free up dead registers */ void dodeads(struct bblock * cblk, rlist * deads, int empty) { register char *a; register struct setlist *sptr; int rt; char reg[MAXSTRING], dreg[REGSTRING]; /* Examine each register marked dead at this point */ reget(*deads, reg); for (a = reg; *a; a += 3) { sptr = s_add(a); switch (sptr->regstatus) { case UNASSIGNED: /* If the register was not assigned to anything, then we simply make it disappear from the dead register list unless it was a hardware register. I'm not too sure if we need to keep dead unassigned hardware registers around any more (they used to be used in place of set lines at call sites), but for now we will leave them alone. */ if (!(sptr->status & HARDWARE)) rdel(sptr->num, deads); break; case REGISTER: /* If the dead item was allocated to a hardware register, then we can go ahead and free up the hardware register for allocation. If the register was a pseudo-register and this RTL is empty (it has no effects), then we can just make such pseudo-registers disappear. */ if (!(sptr->status & HARDWARE)) rdel(sptr->num, deads); if (!empty) { rt = regtype(a); makerg(dreg, rt, indextoreg(rt, sptr->assign)); rinsert(dreg, deads); } freereg(cblk, sptr); sptr->sets = (struct list *) NULL; break; case TEMP: /* If the value of the register was spilled to a temporary location, then we can go ahead and free up the temporary location. */ freetemp(cblk, sptr); rdel(sptr->num, deads); break; default: (void) fprintf(stderr, "vpo (dodeads): register data corrupt\n"); exit(1); } } } /* * solveconflicts - ensures a consistent register state for all predecessors */ void solveconflicts(struct bblock * cblk) { register regarray cr, pr; struct bblock *fblk; struct setlist *sptr; struct blist *bptr; rlist conflict, deads[MAXXFER]; int index, rt, rcont, check, change; char *c, creg[MAXSTRING], reg[BIGSTRING]; /* There are no conflicts to begin with */ conflict = rinit(); /* Pointer to register status information of current basic block */ cr = (regarray) cblk->regstate; /* If any hardware register is live at the start of the current basic block, then mark it as used so that it is not overwritten by a temporary value. */ reget(cblk->ulist, c = creg); while (*c) { sptr = s_lookup(c); if (sptr->status & HARDWARE) { rt = regtype(c); index = regtoindex(rt, regnum(c)); markreg(cblk, sptr, rt, index); } c += 3; } /* Search through all of the predecessors of the current basic block */ for (bptr = cblk->preds; bptr; bptr = bptr->next) { /* Examine the predecessor if it is not the current basic block and if register allocation has been done on it. */ if (bptr->ptr != cblk && (pr = (regarray) bptr->ptr->regstate)) { /* Allocate all register items still live from the predecessors */ for (index = 0; index < MAXREGS; index++) { /* If a pseudo register is live and the current basic block does not have it allocated to the same register as its predecessor, then we need to examine it a bit more closely. */ if (pr->reg[index].status == USED && cr->reg[index].pseudo != (sptr = pr->reg[index].pseudo) && rin(sptr->num, cblk->ulist)) { /* If it has not yet been assigned to anything in the current block, then maybe it just needs an assignment. */ if (sptr->regstatus == UNASSIGNED) { /* Check to see if the register will fit in the same place that it was allocated to in the predecessor. */ rt = regtype(sptr->item); rcont = contreg(rt); for (check = index; rcont--; check++) if (cr->reg[check].status != NOTUSED) break; /* If it fits, then go ahead and allocate it to the same register, otherwise, add it to the conflict list so that it can be resolved later. */ if (rcont < 0) markreg(cblk, sptr, rt, index); else { rins(sptr->num, &conflict); if (cr->reg[index].status == NOTUSED) cr->reg[index].status = CONFLICT; } } /* If it was already allocated, then there is a definite conflict */ else { rins(sptr->num, &conflict); if (cr->reg[index].status == NOTUSED) cr->reg[index].status = CONFLICT; } } } /* Allocate all spilled items still live from the predecessors */ for (index = 0; index < MAXTEMP; index++) { if (pr->temp[index].status == USED && cr->temp[index].pseudo != (sptr = pr->temp[index].pseudo) && rin(sptr->num, cblk->ulist)) { if (sptr->regstatus == UNASSIGNED) { rt = regtype(sptr->item); rcont = conttemp(rt); for (check = index; rcont--; check++) if (cr->temp[check].status != NOTUSED) break; if (rcont < 0) marktemp(cblk, sptr, rt, index); else { rins(sptr->num, &conflict); if (cr->temp[index].status == NOTUSED) cr->temp[index].status = CONFLICT; } } else { rins(sptr->num, &conflict); if (cr->temp[index].status == NOTUSED) cr->temp[index].status = CONFLICT; } } } } } /* If there are no conflicting items, then we have completed our task, which was to set up association links with the register database that are consistent with the associations made by all of the predecessors of this basic block. */ if (conflict) { #ifdef VET begin_trans(VET_REQUIRED_TRANS); #endif /* Free up every item that is in a conflict */ reget(conflict, c = creg); while (*c) { sptr = s_lookup(c); if (sptr->regstatus == REGISTER) conflictreg(cblk, sptr); else if (sptr->regstatus == TEMP) conflicttemp(cblk, sptr); c += 3; } /* Allocate all items that were in conflict into items that were not implicated in the conflict. */ c = creg; while (*c) { sptr = s_lookup(c); rt = regtype(c); if (fitreg(cblk, cblk->rtls, sptr, rt, &index, &change, FALSE)) markreg(cblk, sptr, rt, index); else if (fittemp(cblk, rt, &index)) marktemp(cblk, sptr, rt, index); else { (void) fprintf(stderr, "vpo (solveconflicts): out of temporaries\n"); exit(1); } c += 3; } /* Now free up the items that were implicated in the conflict so that they can be used. */ for (index = 0; index < MAXREGS; index++) if (cr->reg[index].status == CONFLICT) cr->reg[index].status = NOTUSED; for (index = 0; index < MAXTEMP; index++) if (cr->temp[index].status == CONFLICT) cr->temp[index].status = NOTUSED; /* Now we must visit each predecessor, and for each item we find where the current association does not match that of the predecessor, we must generate appropriate transfer RTLs to ensure that the items in conflict wind up in the proper locations. */ for (bptr = cblk->preds; bptr; bptr = bptr->next) { pr = (regarray) bptr->ptr->regstate; if (pr && bptr->ptr != cblk) { fblk = (struct bblock *) NULL; /* Generate appropriate transfer RTLs to move register conflicts into their appropriate locations. */ for (index = 0; index < MAXREGS; index++) { if ((sptr = pr->reg[index].pseudo) && rin(sptr->num, conflict)) { rt = regtype(sptr->item); if (sptr->regstatus == REGISTER) { if (sptr->assign == index) continue; (void) transfer(reg, deads, REGISTER, rt, indextoreg(rt, sptr->assign), REGISTER, rt, indextoreg(rt, index)); } else (void) transfer(reg, deads, TEMP, rt, sptr->assign, REGISTER, rt, indextoreg(rt, index)); fblk = add_fix_code(bptr->ptr, cblk, fblk, reg, deads); } } /* Generate appropriate transfer RTLs to move temporary spill locations that are in conflict into appropriate locations. */ for (index = 0; index < MAXTEMP; index++) { if ((sptr = pr->temp[index].pseudo) && rin(sptr->num, conflict)) { rt = regtype(sptr->item); if (sptr->regstatus == REGISTER) (void) transfer(reg, deads, REGISTER, rt, indextoreg(rt, sptr->assign), TEMP, rt, index); else { if (sptr->assign == index) continue; /* When having to move a temporary location to another temporary location, the transfer() routine may indicate that the target machine is not capable of doing so without using an intermediate register. If that is the case, then we will have to do some work in order to ensure that we can provide a register to help perform the transfer. */ if (!transfer(reg, deads, TEMP, rt, sptr->assign, TEMP, rt, index)) { /* If we can locate a free register in the current basic block, then we can go ahead and use it to transfer the item. */ if (find_unused_register(cblk, rt, &check)) { (void) transfer(reg, deads, REGISTER, rt, indextoreg(rt, check), TEMP, rt, index); fblk = add_fix_code(bptr->ptr, cblk, fblk, reg, deads); (void) transfer(reg, deads, TEMP, rt, sptr->assign, REGISTER, rt, indextoreg(rt, check)); } else (void) fprintf(stderr, "vpo (solveconflicts): cannot transfer temporary\n"); } } fblk = add_fix_code(bptr->ptr, cblk, fblk, reg, deads); } } } } #ifdef VET end_trans(); #endif } /* Release the temporary conflict vector */ rfree(conflict); } /* * loopconflicts - fix up any loop conflicts between two basic blocks */ void loopconflicts(struct bblock * from, struct bblock * to) { register regarray fv, tv; struct bblock *fblk; struct setlist *sptr, *bptr; rlist deads[MAXXFER]; int index, find, found, check, rcont, rt, reload; int sfound, sfind, srt, scont, sfree, sskip, savl; char reg[BIGSTRING]; #ifdef VET begin_trans(VET_REQUIRED_TRANS); #endif fv = (regarray) from->regstate; tv = (regarray) to->elist; fblk = (struct bblock *) NULL; /* Look at the items that are allocated to hardware registers in the block that we are going to transfer control to. */ for (index = 0; index < MAXREGS; index++) { if (sptr = tv->reg[index].pseudo) { /* Attempt to locate the item in our current allocation list. First, try to see if it is allocated to a register. */ found = FALSE; for (find = 0; find < MAXREGS; find++) { if (sptr == fv->reg[find].pseudo) { found = TRUE; /* If all goes well, it should be allocated to the same hardware register, in which case there is no need for us to do anything. */ if (index == find) break; /* If we get here, we ran out of luck, so we have to insert some code to get the item from the register that it is mapped to in the current block to the one that it will go to in the destination block. The first thing we will try is to see if can move the register value from where it is to where we need it directly. */ rt = regtype(sptr->item); rcont = contreg(rt); for (check = index; rcont--; check++) { if (fv->reg[check].status != NOTUSED) { /* There is a value in this slot that must be moved elsewhere. We will attempt to spill it, but we will first scan to see if there is a particular spill location for this item that would fix things up perfectly. */ bptr = fv->reg[check].pseudo; srt = regtype(bptr->item); sfound = FALSE; for (sfind = 0; sfind < MAXTEMP; sfind++) { if (bptr == tv->temp[sfind].pseudo) { /* We have located a spill location where the register that is blocking our progress should be moved to, so we determine if there is anything impeding us from spilling the item to that location so that we can continue. */ scont = conttemp(srt); for (sfree = sfind; scont--; sfree++) if (fv->temp[sfree].status != NOTUSED) break; if (scont < 0) { fv->reg[check].pseudo = (struct setlist *) NULL; scont = contreg(srt); for (sfree = check; scont--; sfree++) fv->reg[sfree].status = NOTUSED; fv->temp[sfind].pseudo = bptr; fv->temp[sfree = sfind].status = USED; scont = conttemp(srt); while (--scont) fv->temp[++sfree].status = FOLLOWER; (void) transfer(reg, deads, TEMP, srt, sfind, REGISTER, srt, indextoreg(srt, check)); fblk = add_fix_code(from, to, fblk, reg, deads); sfound = TRUE; } break; } } /* If we where not able to locate the final place to store the register item that is blocking our progress, then we look for a spill location that will not block anything if it is used. */ if (!sfound) { savl = availtemp(srt); sskip = skiptemp(srt); for (sfind = firsttemp(srt); savl--; sfind += sskip) { scont = conttemp(srt); for (sfree = sfind; scont--; sfree++) if (tv->temp[sfree].status != NOTUSED || fv->temp[sfree].status != NOTUSED) break; /* If we have located a suitable spill location, then we go ahead and move the blocking register to that spill location, knowing that we will have to move it to some other location later on in this same function. */ if (scont < 0) { fv->reg[check].pseudo = (struct setlist *) NULL; scont = contreg(srt); for (sfree = check; scont--; sfree++) fv->reg[sfree].status = NOTUSED; fv->temp[sfind].pseudo = bptr; fv->temp[sfree = sfind].status = USED; scont = conttemp(srt); while (--scont) fv->temp[++sfree].status = FOLLOWER; (void) transfer(reg, deads, TEMP, srt, sfind, REGISTER, srt, indextoreg(srt, check)); fblk = add_fix_code(from, to, fblk, reg, deads); sfound = TRUE; break; } } } /* If we have failed to locate an appropriate spill location in both instances, then we exit this loop in failure. */ if (!sfound) break; } } /* If we have not been able to clear out the way for the item, then we have run out of temporary locations that are not affected by either the from or to blocks. */ if (rcont >= 0) (void) fprintf(stderr, "vpo (loopconflicts): need to spill\n"); /* Free up the register that holds the value that we are moving */ fv->reg[find].pseudo = (struct setlist *) NULL; rcont = contreg(rt); for (check = find; rcont--; check++) fv->reg[check].status = NOTUSED; /* Mark the new register assignment that we have just made */ fv->reg[index].pseudo = sptr; fv->reg[check = index].status = USED; rcont = contreg(rt); while (--rcont) fv->reg[++check].status = FOLLOWER; /* Generate the code required to transfer the register to its appropriate location. */ (void) transfer(reg, deads, REGISTER, rt, indextoreg(rt, index), REGISTER, rt, indextoreg(rt, find)); fblk = add_fix_code(from, to, fblk, reg, deads); break; } } /* If the register value was not among any of the registers, then we look for it among the spill locations. */ if (!found) { for (find = 0; find < MAXTEMP; find++) { if (sptr == fv->temp[find].pseudo) { /* In this case, the value get need in a register exists in a temporary memory location. We must generate code to move that value into the appropriate register. The first thing we will try is to see if can move the register value from where it is to where we need it directly. */ rt = regtype(sptr->item); rcont = contreg(rt); for (check = index; rcont--; check++) { if (fv->reg[check].status != NOTUSED) { /* There is a value in this slot that must be moved elsewhere. We will attempt to spill it, but we will first scan to see if there is a particular spill location for this item that would fix things up perfectly. */ bptr = fv->reg[check].pseudo; sfound = FALSE; for (sfind = 0; sfind < MAXTEMP; sfind++) { if (bptr == tv->temp[sfind].pseudo) { /* We have located a spill location where the register that is blocking our progress should be moved to, so we determine if there is anything impeding us from spilling the item to that location so that we can continue. */ srt = regtype(bptr->item); scont = conttemp(srt); for (sfree = sfind; scont--; sfree++) if (fv->temp[sfree].status != NOTUSED) break; if (scont < 0) { fv->reg[check].pseudo = (struct setlist *) NULL; scont = contreg(srt); for (sfree = check; scont--; sfree++) fv->reg[sfree].status = NOTUSED; fv->temp[sfind].pseudo = bptr; fv->temp[sfree = sfind].status = USED; scont = conttemp(srt); while (--scont) fv->temp[++sfree].status = FOLLOWER; (void) transfer(reg, deads, TEMP, srt, sfind, REGISTER, srt, indextoreg(srt, check)); fblk = add_fix_code(from, to, fblk, reg, deads); sfound = TRUE; } break; } } /* If we where not able to locate the final place to store the register item that is blocking our progress, then we look for a spill location that will not block anything if it is used. */ if (!sfound) { savl = availtemp(srt); sskip = skiptemp(srt); for (sfind = firsttemp(srt); savl--; sfind += sskip) { scont = conttemp(srt); for (sfree = sfind; scont--; sfree++) if (tv->temp[sfree].status != NOTUSED || fv->temp[sfree].status != NOTUSED) break; /* If we have located a suitable spill location, then we go ahead and move the blocking register to that spill location, knowing that we will have to move it to some other location later on in this same function. */ if (scont < 0) { fv->reg[check].pseudo = (struct setlist *) NULL; scont = contreg(srt); for (sfree = check; scont--; sfree++) fv->reg[sfree].status = NOTUSED; fv->temp[sfind].pseudo = bptr; fv->temp[sfree = sfind].status = USED; scont = conttemp(srt); while (--scont) fv->temp[++sfree].status = FOLLOWER; (void) transfer(reg, deads, TEMP, srt, sfind, REGISTER, srt, indextoreg(srt, check)); fblk = add_fix_code(from, to, fblk, reg, deads); sfound = TRUE; break; } } } /* If we have failed to locate an appropriate spill location in both instances, then we exit this loop in failure. */ if (!sfound) break; } } /* If we have not been able to clear out the way for the item, then we have run out of temporary locations that are not affected by either the from or to blocks. */ if (rcont >= 0) (void) fprintf(stderr, "vpo (loopconflicts): need to spill\n"); /* Free up the temporary location that holds the value that we are moving. */ fv->temp[find].pseudo = (struct setlist *) NULL; rcont = conttemp(rt); for (check = find; rcont--; check++) fv->temp[check].status = NOTUSED; /* Mark the new register assignment that we have just made */ fv->reg[index].pseudo = sptr; fv->reg[check = index].status = USED; rcont = contreg(rt); while (--rcont) fv->reg[++check].status = FOLLOWER; /* Generate the code required to transfer the register to its appropriate location. */ (void) transfer(reg, deads, REGISTER, rt, indextoreg(rt, index), TEMP, rt, find); fblk = add_fix_code(from, to, fblk, reg, deads); break; } } } } } /* Look at the items that are allocated to spill locations in the block that we are going to transfer control to. */ for (index = 0; index < MAXTEMP; index++) { if (sptr = tv->temp[index].pseudo) { /* Attempt to locate the item in our current allocation list. First, try to see if it is allocated to a temporary spill location. */ found = FALSE; for (find = 0; find < MAXREGS; find++) { if (sptr == fv->temp[find].pseudo) { found = TRUE; /* If all goes well, it should be allocated to the same temporary location, in which case there is no need for us to do anything. */ if (index == find) break; /* First thing that we need to do is grab an appropriate register. We try first to find an unused one. */ rt = regtype(sptr->item); savl = availreg(rt); sskip = skipreg(rt); for (check = firstreg(rt); savl--; check += sskip) { rcont = contreg(rt); for (sfind = check; rcont--; sfind++) if (tv->reg[check].status != NOTUSED) break; if (rcont < 0) break; } /* Failing that, we comandeer the first register available, spill its value so that we can use the register to move spill values around and then we will end up re-loading the spilled value. */ reload = FALSE; if (savl < 0) { rcont = contreg(rt); for (check = firstreg(rt); rcont--; check++) { if (tv->reg[check].status == USED) { bptr = tv->reg[check].pseudo; srt = regtype(bptr->item); savl = availtemp(srt); sskip = skiptemp(srt); for (sfind = firsttemp(srt); savl--; sfind += sskip) { scont = conttemp(srt); for (sfree = sfind; scont--; sfree++) if (tv->temp[sfree].status != NOTUSED || fv->temp[sfree].status != NOTUSED) break; if (scont < 0) break; } /* Spill the items required to obtain the items that we need */ if (savl >= 0) { (void) transfer(reg, deads, TEMP, srt, bptr->uses = sfind, REGISTER, srt, indextoreg(srt, check)); fblk = add_fix_code(from, to, fblk, reg, deads); break; } else (void) fprintf(stderr, "vpo (loopconflicts): need to spill\n"); } } check = firstreg(rt); reload = TRUE; } /* Load the register with the temporary value from the "from" block. */ (void) transfer(reg, deads, REGISTER, rt, indextoreg(rt, check), TEMP, rt, find); fblk = add_fix_code(from, to, fblk, reg, deads); /* Store the register in the spill location required by the "to" block. */ (void) transfer(reg, deads, TEMP, rt, index, REGISTER, rt, indextoreg(rt, check)); fblk = add_fix_code(from, to, fblk, reg, deads); /* If we had to spill items to get a free register, then put them back. */ if (reload) { rcont = contreg(rt); for (check = firstreg(rt); rcont--; check++) { if (tv->reg[check].status == USED) { bptr = tv->reg[check].pseudo; srt = regtype(bptr->item); (void) transfer(reg, deads, REGISTER, srt, indextoreg(srt, check), TEMP, srt, bptr->uses); fblk = add_fix_code(from, to, fblk, reg, deads); } } } } } if (!found) (void) fprintf(stderr, "vpo (loopconflicts): spill mismatch\n"); } } #ifdef VET end_trans(); #endif } /* * add_fix_code - add new transfer RTLs to perform a fix */ struct bblock *add_fix_code(struct bblock * from, struct bblock * to, struct bblock * cblk, register char *new, rlist * deads) { register struct list *iptr; /* If we don't already have a suitable block to insert the transfer RTLs into, then either find a suitable one or create one. */ if (!cblk) cblk = add_fix_block(from, to); /* Add new transfer RTLs at end of block. Be sure to place them in front of any jump that may exist at the end of the block. */ iptr = (cblk->status & JUMP || cblk->right) ? cblk->rtlend : (struct list *) NULL; /* This mechanism supports adding multiple RTLs to a block. The RTLs are passed in as a single string separated by a single '\0', the end of the list is delimited by two consecutive '\0's. */ while (*new) { (void) add_rtl(cblk, iptr, new, *deads++); while (*new++); } /* Return a pointer to the basic block that the fix code was added to */ return (cblk); } /* * save_entry - save a copy of the entry state of the assignment vector */ void save_entry(struct bblock * cblk) { register regarray fv, tv; register int index; regvec copyreg; copyreg = reginit(); initassign(©reg); fv = (regarray) cblk->regstate; tv = (regarray) copyreg; for (index = 0; index < MAXREGS; index++) tv->reg[index] = fv->reg[index]; for (index = 0; index < MAXTEMP; index++) tv->temp[index] = fv->temp[index]; cblk->elist = (struct eqvtable *) copyreg; } /* * initassign - initialize a register assignment vector for a basic block */ void initassign(regvec * regstate) { register regarray cr; register int index; if (!(cr = (regarray) * regstate)) cr = (regarray) (*regstate = (regvec) SALLOC(sizeof(reginfo))); for (index = 0; index < MAXREGS; index++) { cr->reg[index].status = NOTUSED; cr->reg[index].pseudo = (struct setlist *) NULL; } for (index = 0; index < MAXTEMP; index++) { cr->temp[index].status = NOTUSED; cr->temp[index].pseudo = (struct setlist *) NULL; } } /* * unassociate - remove all pointers from pseudo registers left alive */ void unassociate(struct bblock * cblk) { register regarray cr; register struct setlist *sptr; register int index; cr = (regarray) cblk->regstate; for (index = 0; index < MAXREGS; index++) if (sptr = cr->reg[index].pseudo) { sptr->regstatus = UNASSIGNED; sptr->assign = 0; } for (index = 0; index < MAXTEMP; index++) if (sptr = cr->temp[index].pseudo) { sptr->regstatus = UNASSIGNED; sptr->assign = 0; } } /* * savregs - save used registers before a procedure call */ void savregs(struct bblock * cblk, struct list * ptr, int *change) { register regarray cr; register int i; register char *a; struct list *cptr; int rt, rcont; hascs = TRUE; /* The caller-saves line is always placed following the call, in order to ensure that any items used and dead at the call site are not spilled needlessly. The spills themselves, must be placed before the call, therefore, we must back up and look for the call RTL. */ for (cptr = ptr->prev; !(cptr->type & RTLINE); cptr = cptr->prev); /* For each register indicated in the caller-saves line, we determine if that register is allocated to any pseudo-register and, if it is, we spill that pseudo-register so that the caller-saves register is no longer live at this point. */ cr = (regarray) cblk->regstate; for (a = ptr->val; *a; a += 2) { rt = regtype(a); i = regtoindex(rt, regnum(a)); for (rcont = contreg(rt); rcont--; i++) { if (cr->reg[i].status != NOTUSED) { while (cr->reg[i].status == FOLLOWER) i--; spillreg(cblk, cptr, i, TRUE); printf("#SPILLREG %d\n", i); *change = TRUE; } } } } /* * assoc - change pseudo register into corresponding hardware register */ void assoc(struct bblock * cblk, struct list * ptr, char *item, int *change, int dest) { register struct setlist *sptr; register int rt; sptr = s_add(item); rt = regtype(item); makerg(item, rt, gtreg(cblk, ptr, sptr, rt, change, dest)); sptr->sets = (dest) ? ptr : (struct list *) NULL; } /* * reserve - assign a particular hardware value to a pseudo-register */ struct list *reserve(struct bblock * cblk, struct list * ptr, int *change) { register struct setlist *sptr, *pptr; register int rt; register regarray cr; rlist *deads, deadlist[MAXXFER]; int rnum, find, conflict[MAXREGS]; char *a, new[BIGSTRING]; /* Start by reserving the hardware register value to itself */ rt = regtype(ptr->val); pptr = s_add(ptr->val); sptr = s_add(ptr->val + 3); rnum = gtreg(cblk, ptr, sptr, rt, change, FALSE); /* Modify the reserve line to indicate which register value is reserved. */ makerg(ptr->val, rt, rnum); *(ptr->val + 2) = '\0'; #ifdef VET mod_res(ptr); #endif sptr->sets = (struct list *) NULL; /* If the source and destination registers are the same, then we have done everything that is required. */ if (pptr == sptr) return (ptr); /* Ensure that the hardware register that we are allocating the pseudo-register to is available over the life of the pseudo- register. Otherwise, we will have to locate a more suitable register and transfer the value to it. */ if (isused[sptr->assign]) { conflicts(ptr, pptr->item, conflict, TRUE); if (conflict[sptr->assign]) { find = gtreg(cblk, ptr, pptr, rt, change, TRUE); deads = deadlist; a = new; (void) transfer(a, deads, REGISTER, rt, find, REGISTER, rt, rnum); while (*a) { pptr->sets = add_rtl(cblk, ptr->next, a, *deads++); while (*a++); } freereg(cblk, sptr); return (pptr->sets); } } /* Swap the pseudo-register value and the harware register value */ cr = (regarray) cblk->regstate; pptr->regstatus = sptr->regstatus; pptr->assign = sptr->assign; cr->reg[sptr->assign].pseudo = pptr; sptr->regstatus = UNASSIGNED; pptr->sets = (struct list *) NULL; return (ptr); } /* * gtreg - return hard register number to associate with pseudo register */ int gtreg(struct bblock * cblk, struct list * ptr, struct setlist * sptr, int rt, int *change, int dest) { register int index, find, pt; struct setlist *pptr; char reg[REGSTRING]; /* Determine the current status of the pseudo-register to take the action required to return the hardware register mapping for this pseudo- register. */ switch (sptr->regstatus) { case UNASSIGNED: /* If the pseudo-register type belongs to a group, then start with the first register type in the group and make a suitable slot which can contain all of the registers in the group. Then, place each item in the group into its appropriate slot separately. */ if ((pt = headgroup(rt)) >= 0) { makerg(reg, pt, regnum(sptr->item)); pptr = s_lookup(reg); index = find = findreg(cblk, ptr, sptr, pt, change, dest); markreg(cblk, pptr, pt, index); index += contreg(pt); while ((pt = nextgroup(pt)) >= 0) { makerg(reg, pt, regnum(sptr->item)); pptr = s_lookup(reg); if (sptr == pptr) find = index; markreg(cblk, pptr, pt, index); index += contreg(pt); } return (indextoreg(rt, find)); } /* Allocate a non-group pseudo-register to a hardware register by finding (or making) a suitable slot for it. */ find = findreg(cblk, ptr, sptr, rt, change, dest); markreg(cblk, sptr, rt, find); return (indextoreg(rt, find)); case REGISTER: /* If this pesudo-register is already allocated to a hardware register, then return the hardware register mapping. */ return (indextoreg(rt, sptr->assign)); case TEMP: /* If this pseudo-register is currently spilled, then load it up from memory into an appropriate hardware register and return the new hardware register mapping. */ find = findreg(cblk, ptr, sptr, rt, change, dest); loadreg(cblk, ptr, sptr, rt, find); return (indextoreg(rt, find)); default: /* Something has gone wrong if we get here */ (void) fprintf(stderr, "vpo (gtreg): register data corrupt\n"); exit(1); } /* unreachable, but necessary so compiler doesn't complain (especially lcc) */ return (0); } /* * findreg - find a free hardware register of the appropriate type */ int findreg(struct bblock * cblk, struct list * ptr, struct setlist * sptr, int rt, int *change, int dest) { register regarray cr; register int find, loop; long cost, check, dist; int index, ravl, rskip, rcont, end, conflict[MAXREGS]; char reg[REGSTRING]; /* First, try to find an unallocated register to allocate to the pseudo-register. If we find one, then we are done. */ if (fitreg(cblk, ptr, sptr, rt, &index, change, dest)) return (index); /* If we get here, then there are no unallocated registers that can be allocated to the new pseudo-register, so we have to start considering spilling somebody. Start by getting the allocation parameters for the required type of register. */ cr = (regarray) cblk->regstate; ravl = availreg(rt); rskip = skipreg(rt); rcont = allocreg(rt); conflicts(ptr, sptr->item, conflict, dest); /* The algorithm that determines which register to spill is cost-driven. The basic idea is to spill the register that costs the least to spill and will be needed again as far off into the future as possible. */ cost = 0L; for (find = index = firstreg(rt); ravl--; find += rskip) { end = rcont; /* If we start "halfway" into a group of allocated registers, back up and find the pseudo-register that straddles them all. */ if (cr->reg[find].status == FOLLOWER) { /* Back up to find the "start" of the register that we are on. This is a special case that allows us to estimate the cost of spilling the first item that may be in the way. */ for (loop = find - 1; cr->reg[loop].status == FOLLOWER; loop--); /* Now let's find the place where this register is used next and calculate a spill cost based on how far away the next use is and how large the register is. If the item will be used in the very RTL that we need to spill for, then we cannot make use of the item and must continue on to the next one. */ sptr = cr->reg[loop].pseudo; if (!(dist = distance(ptr, sptr->item))) continue; dist /= contreg(regtype(sptr->item)); check = (dist) ? dist : 1L; } else check = 0L; /* Check to see if we have to spill more than one item in order to make room for this item. The costs of spilling add up. */ for (loop = find; end--; loop++) { /* If this item will be needed sometime before the register that we want to assign it to dies, then we cannot use this item. */ if (isused[loop] && conflict[loop]) { check = 0L; break; } /* If this item is currently holding a real register value, then we calculate the cost of using it. */ else if (cr->reg[loop].status == USED) { sptr = cr->reg[loop].pseudo; /* If the register will be used in the very RTL that we need to spill for, then we obviously cannot make use of this item. */ if (!(dist = distance(ptr, sptr->item))) { check = 0L; break; } /* Otherwise, it may be the case that the register has already been allocated and modified in the RTL, so we check to see if the hardware register that it is currently assigned to is used in the RTL that we are spilling for. */ else if (!dest) { makereg(reg, rt, indextoreg(rt, loop)); if (isref(ptr->val, reg)) { check = 0L; break; } } dist /= contreg(regtype(sptr->item)); check += ((dist) ? dist : 1); } /* If this slot is currenty empty, then we want to make it as attractive to spill as possible. */ else if (cr->reg[loop].status == NOTUSED) check += 10L; } /* Remember the items that are best to spill */ if (check > cost) { cost = check; index = find; } } /* If we cannot locate any suitable registers to spill, it must mean that this RTL requires more registers to execute that there are registers to allocate. */ if (!cost) { (void) fprintf(stderr, "vpo (findreg): too many registers in '"); show_rtl(stderr, ptr->val); (void) fprintf(stderr, "'\n"); exit(1); } /* Now that we have determined which register to spill, we go ahead and do so. */ for (find = index; cr->reg[find].status == FOLLOWER; find--); if (find != index) spillreg(cblk, ptr, find, TRUE); for (find = index; rcont--; find++) { if (cr->reg[find].status == USED) spillreg(cblk, ptr, find, TRUE); } *change = TRUE; return (index); } /* * distance - measure the number of RTLs to the next reference of a register */ long distance(register struct list * ptr, char *reg) { struct bblock *cblk; long dist; dist = 0L; cblk = ptr->daddy; for (;;) { while (ptr) { if (cnts(ptr)) { if (fmatch(ptr->val, reg)) return (dist); dist++; } ptr = ptr->next; } if (cblk = cblk->down) ptr = cblk->rtls; else return (dist); } } /* * fitreg - look for a register allocation for a given type */ int fitreg(struct bblock * cblk, struct list * ptr, struct setlist * sptr, int rt, int *index, int *change, int dest) { register regarray cr; register int check, find, end, rcont; int ravl, rskip, cflag, conflict[MAXREGS]; #ifdef RRLRA int class; char reg[REGSTRING]; #endif cr = (regarray) cblk->regstate; /* If we are allocating for a hardware register, then there is no need to look for an available hardware register, but we do need to make sure that the hardware register is not currently being used for any purpose. */ if (sptr->status & HARDWARE) { *index = end = regtoindex(rt, regnum(sptr->item)); for (rcont = allocreg(rt); rcont--; end++) { if (cr->reg[end].status != NOTUSED) { /* Here we make a check to see if the item is part of a larger hardware register that was reserved earlier. If this is the case, then we free up the larger hardware item and put the current item where it belongs. */ for (check = end; cr->reg[check].status == FOLLOWER; check--); if (cr->reg[check].pseudo && cr->reg[check].pseudo->status & HARDWARE) freereg(cblk, cr->reg[check].pseudo); /* It is possible that use lines where properly generated, but a lack of registers forced us to spill the hardware item before we reached the point where it was needed again. If this is the case, then we try to free up the hardware register by spilling its current value. It may be the case that there are other registers free at this time that could accept the value directly, but checking for that and taking appropriate action would require a good bit of care, so I'll leave that for a future time. There is also the chance that the hardware register was spilled and then assigned to a pseudo-register item that will be used in the next RTL, in which case spilling the value and then restoring it will leave behind code that doesn't work. I am not sure of what the best way to solve such a problem is, since it requires that we re-examine the whole RTL and re-map the register we need to restore here that has already been modified to another register. Here is an example: r[10]=L[_x]; r[10]=L[_x]; -- r[10] reserved ur[10] r[80]=L[_item]; L[spill1]=r[10]; -- r[10] spill r[10]=L[_item]; -- r[10] re-use r[80]=r[80]+r[10]; L[spill2]=r[10]; -- r[80] spill r[10]=L[spill1]; -- r[10] restore r[80]=r[10]+r[10]; -- WRONG! This case can occur on machines where the number of allocable registers for at least one type of registers is very small. The example shown has been overly-simplified, but the idea is that a particular hardware register value is reserved after a function call or for some other purpose. The lack of registers then forces the allocator to spill the r[10] value so that it can calculate a new r[80] value. Finally, we run into an RTL that uses both the r[80] value and the spilled r[10] value and r[80] shows up before r[10]. So we first look at the sources and determine that r[80] is mapped to r[10], so we make the appropriate update. Then we see the need for the r[10] value. We then get here and try to obtain the r[10] value into r[10] by spilling r[80], which is is r[10] and then loading r[10] from its spill location. The result is not correct. The only solution at this time is to avoid the situation that causes the problem, which will probably only happen in certain register deprivation experiments. */ else if (cr->reg[check].status == TEMP) { spillreg(cblk, ptr, check, FALSE); *change = TRUE; } /* If we get here then we can be fairly sure that the register is not available because the code expander failed to emit a use line at the appropriate point. Rather than try to patch up things by generating inefficient code and continue, it makes more sense to stop and force the user to determine the exact cause of the problem. */ else { (void) fprintf(stderr, "vpo (fitreg): hardware register "); show_rtl(stderr, sptr->item); (void) fprintf(stderr, " not available on demand\n"); exit(1); } } } return (TRUE); } /* This flag is used to indicate that we have performed a search over the life of the pseudo-register that we need to allocate a hardware register to and determined which hardware registers, if any, cannot be allocated to this pseudo-register because its life overlaps a use line indicating that a particular hardware register is needed at that point. */ cflag = FALSE; rskip = skipreg(rt); rcont = allocreg(rt); #ifdef RRLRA class = classreg(rt); /* If we have already allocated a register in this class, we try to allocate the next available one in a round-robin scheme. */ if (lastfound[class] >= 0) { ravl = availreg(rt); for (find = firstreg(rt); find < lastfound[class]; find += rskip) ravl--; while (ravl-- > 0) { end = rcont; for (check = find; end--; check++) { /* Determine if we have reached the end of the scratch registers, if so, we fall out of this loop. */ makerg(reg, rt, check); if (!scratchreg(reg)) { lastfound[class] = -1; goto fail; } if (cr->reg[check].status != NOTUSED) break; else if (isused[check]) { if (!cflag) { /* At this point we are considering allocating a hardware register that has been marked as used (by the code expander through the use line feature) somewhere in the function. What we are going to do now is search from this point until the death of the pseudo register that we are allocating for. If we encounter any use lines, then those registers marked used cannot be allocated to this pseudo register because there would be a future conflict. */ conflicts(ptr, sptr->item, conflict, dest); cflag = TRUE; } if (conflict[check]) break; } } if (end < 0) { *index = find; lastfound[class] = find + 1; return (TRUE); } find += rskip; } } fail: #endif /* This loop is the normal allocation loop which begins with the first allocable register for the type requested and searches over all of the allocable registers. The least expensive registers are placed first. */ ravl = availreg(rt); for (find = firstreg(rt); ravl--; find += rskip) { end = rcont; for (check = find; end--; check++) { if (cr->reg[check].status != NOTUSED) break; else if (isused[check]) { if (!cflag) { conflicts(ptr, sptr->item, conflict, dest); cflag = TRUE; } if (conflict[check]) break; } } if (end < 0) { *index = find; #ifdef RRLRA lastfound[class] = find + 1; #endif return (TRUE); } } #ifdef RRLRA lastfound[class] = -1; #endif /* We could find no available registers, so we return indicating our failure. */ return (FALSE); } /* * spillreg - saves a register into a temporary location */ void spillreg(struct bblock * cblk, struct list * ptr, int index, int checkuse) { struct setlist *sptr; struct list *nptr, *bptr; rlist *deads, deadlist[MAXXFER]; int find, rt, used_here, i; char *a, new[BIGSTRING]; /* fprintf(stderr, "# inside spillreg\n"); /* Free up the register that we are about to spill from its current hardware register assignment. First, however, check to see if the register is used in the RTL that caused the spill. If it is, then we must not mark the register that we are spilling dead at the point where we spill the register, but rather at the last point where the register will be used. */ sptr = ((regarray) cblk->regstate)->reg[index].pseudo; rt = regtype(sptr->item); used_here = FALSE; if (checkuse && cnts(ptr)) { makereg(new, rt, indextoreg(rt, index)); if (isref(ptr->val, new)) { used_here = TRUE; if (!isset(ptr->val, new)) rinsert(new, &ptr->deads); #ifdef VET mod_deads(ptr); #endif } } /* fprintf(stderr, "# just before freereg\n"); */ freereg(cblk, sptr); /* fprintf(stderr, "# just after freereg\nh"); */ /* Find a temporary spill location to hold this register value */ if (fittemp(cblk, rt, &find)) { /* We will now insert the RTLs required to move the register value we need to spil to the temporary spill location that has been allocated to hold the value. */ deads = deadlist; (void) transfer(new, deads, TEMP, rt, find, (used_here) ? LIVEREG : REGISTER, rt, indextoreg(rt, index)); a = new; while (*a) { nptr = add_rtl(cblk, ptr, a, *deads++); while (*a++); } /* If the "sets" field for the register that we are spilling points to a valid RTL, then the spill code is the first use of the register since it was set, so we set up a combiner link and mark the new code for attention on the next combiner pass. In some instances, the register set and the spill may combine to produce more efficient code. Note that we only set such links if the items are in the same basic block, since we might otherwise introduce an unsafe link. */ if (sptr->sets) { remv_links_to(sptr->sets); if (sptr->sets->daddy == cblk) { (void) add_link(nptr, sptr->sets); combmark(sptr->sets); } sptr->sets = (struct list *) NULL; } /* Otherwise, it may be the case that we still do need to get rid of an unsafe link and set up one from this spill to the set in order to ensure that the most efficient and correct code is produced, but because the register involved has already been assigned in the following line, the "sets" pointer has been removed. Here we examine the RTLs that the following line is linked to and, if any of them set the register that we are spilling, we remove the link and set it up to the spill location instead. */ else if (used_here) { makereg(new, rt, indextoreg(rt, index)); for (i = 0; i < MAXLINKS && (bptr = ptr->lnks[i]); i++) { if (isset(bptr->val, new)) { remv_link(bptr->blnks, ptr); remv_link(ptr->lnks, bptr); #ifdef VET mod_links(ptr); #endif if (bptr->daddy == cblk) { (void) add_link(nptr, bptr); combmark(bptr); } break; } } } /* Now we update the register database to indicate the new location of the value spilled. */ marktemp(cblk, sptr, rt, find); } /* If we run out of temorary memory locations, then we print a fatal error message. The user will then have to increase the number of temporary memory locations by increasing the number of SPILL class items defined in the regtool description for this target machine. */ else { (void) fprintf(stderr, "vpo (spillreg): out of temporary locations\n"); exit(1); } } /* * loadreg - loads a register from a temporary location */ void loadreg(struct bblock * cblk, struct list * ptr, struct setlist * sptr, int rt, int index) { struct list *nptr; rlist *deads, deadlist[MAXXFER]; char *a, new[BIGSTRING]; deads = deadlist; (void) transfer(new, deads, REGISTER, rt, indextoreg(rt, index), TEMP, rt, sptr->assign); a = new; while (*a) { nptr = add_rtl(cblk, ptr, a, *deads++); while (*a++); } freetemp(cblk, sptr); markreg(cblk, sptr, rt, index); (void) add_link(ptr, nptr); } /* * fittemp - look for a temporary allocation for a given type */ int fittemp(struct bblock * cblk, int rt, int *index) { register regarray cr; register int check, find, end, tcont; int tavl, tskip; cr = (regarray) cblk->regstate; tavl = availtemp(rt); tskip = skiptemp(rt); tcont = conttemp(rt); for (find = firsttemp(rt); tavl--; find += tskip) { end = tcont; for (check = find; end--; check++) { if (cr->temp[check].status != NOTUSED) break; } if (end < 0) { *index = find; return (TRUE); } } return (FALSE); } /* * conflicts - find out which hardware registers we conflict with */ void conflicts(register struct list * ptr, char *reg, int *conflict, int dest) { register unsigned int ref; register struct bblock *mblk; struct bblock *cblk; /* No conflicts to begin with */ for (ref = 0; ref < MAXREGS; conflict[ref++] = FALSE); cblk = ptr->daddy; ref = (unsigned int) regtovec(reg); /* If we are allocating for an item that is being set, then we do not want to examine the dead register list of the current RTL. */ if (dest) ptr = ptr->next; /* Attempt to locate the death of the register, if we encounter any "use" type lines before the death of the pseudo register, then those uses conflict with the life of the register. */ while (ptr) { if (ptr->type & RTLINE && rin(ref, ptr->deads)) return; else if (ptr->type & USELINE) conflict[ptr->cost] = TRUE; ptr = ptr->next; } /* Set all blocks to unvisited */ for (mblk = top; mblk; mblk = mblk->down) mblk->status &= ~DRYRUN; /* Since the death is not in this block, we need to follow the children and continue the search. */ if (cblk->right && rin(ref, cblk->right->ulist)) doconflicts(cblk->right, ref, conflict); if (cblk->left && rin(ref, cblk->left->ulist)) doconflicts(cblk->left, ref, conflict); } /* * doconflicts - find out which hardware registers we conflict with */ void doconflicts(register struct bblock * cblk, register unsigned int ref, int *conflict) { register struct list *ptr; /* Attempt to locate the death of the register, if we encounter any "use" type lines before the death of the pseudo register, then those uses conflict with the life of the register. */ for (ptr = cblk->rtls; ptr; ptr = ptr->next) { if (ptr->type & RTLINE && rin(ref, ptr->deads)) return; else if (ptr->type & USELINE) conflict[ptr->cost] = TRUE; } /* Do a depth-first search ensuring that examined blocks are not re-visited */ cblk->status |= DRYRUN; if (cblk->right && !(cblk->right->status & DRYRUN) && rin(ref, cblk->right->ulist)) doconflicts(cblk->right, ref, conflict); if (cblk->left && !(cblk->left->status & DRYRUN) && rin(ref, cblk->left->ulist)) doconflicts(cblk->left, ref, conflict); } /* * markreg - mark a register as used and associate it with a pseudo register */ void markreg(struct bblock * cblk, struct setlist * sptr, int rt, register int index) { register regarray cr; register int rcont; sptr->regstatus = REGISTER; sptr->assign = index; cr = (regarray) cblk->regstate; cr->reg[index].pseudo = sptr; cr->reg[index].status = USED; rcont = contreg(rt); usedregs[index] |= (rcont == 1) ? USED : FOLLOWER; while (--rcont) { cr->reg[++index].status = FOLLOWER; usedregs[index] |= FOLLOWER; } } /* * touchreg - marks a register as used */ void touchreg(vector regs, char *reg) { register int index, rcont; int rt; rt = regtype(reg); index = regtoindex(rt, regnum(reg)); for (rcont = contreg(rt); rcont--; index++) regs[index >> intscale] |= (((unsigned) 1) << (index & bitsperint)); } /* * releasereg - releases a register marked as used */ void releasereg(vector regs, char *reg) { register int index, rcont; int rt; rt = regtype(reg); index = regtoindex(rt, regnum(reg)); for (rcont = contreg(rt); rcont--; index++) regs[index >> intscale] &= ~(((unsigned) 1) << (index & bitsperint)); } /* * marktemp - marks temporary as used and associates it with a pseudo register */ void marktemp(struct bblock * cblk, struct setlist * sptr, int rt, int index) { register regarray cr; register int tcont; sptr->regstatus = TEMP; sptr->assign = index; cr = (regarray) cblk->regstate; cr->temp[index].pseudo = sptr; cr->temp[index].status = USED; usedtemps[index] = TRUE; tcont = conttemp(rt); while (--tcont) { cr->temp[++index].status = FOLLOWER; usedtemps[index] = TRUE; } } /* * freereg - frees a register from its association to a pseudo register */ void freereg(struct bblock * cblk, struct setlist * sptr) { register regarray cr; register int index; sptr->regstatus = UNASSIGNED; index = sptr->assign; cr = (regarray) cblk->regstate; do { cr->reg[index].status = NOTUSED; cr->reg[index++].pseudo = (struct setlist *) NULL; } while (cr->reg[index].status == FOLLOWER); } /* * freetemp - frees a register from its association to a temporary location */ void freetemp(struct bblock * cblk, struct setlist * sptr) { register regarray cr; register int index; sptr->regstatus = UNASSIGNED; index = sptr->assign; cr = (regarray) cblk->regstate; do { cr->temp[index].status = NOTUSED; cr->temp[index++].pseudo = (struct setlist *) NULL; } while (cr->temp[index].status == FOLLOWER); } /* * conflictreg - indicate a conflicting association to a pseudo register */ void conflictreg(struct bblock * cblk, struct setlist * sptr) { register regarray cr; register int index; sptr->regstatus = UNASSIGNED; index = sptr->assign; cr = (regarray) cblk->regstate; do { cr->reg[index].status = CONFLICT; cr->reg[index++].pseudo = (struct setlist *) NULL; } while (cr->reg[index].status == CONFLICT || cr->reg[index].status == FOLLOWER); } /* * conflicttemp - indicate a conflicting association to a temporary location */ void conflicttemp(struct bblock * cblk, struct setlist * sptr) { register regarray cr; register int index; sptr->regstatus = UNASSIGNED; index = sptr->assign; cr = (regarray) cblk->regstate; do { cr->temp[index].status = CONFLICT; cr->temp[index++].pseudo = (struct setlist *) NULL; } while (cr->temp[index].status == CONFLICT || cr->temp[index].status == FOLLOWER); } /* * find_unused_register - attempt to locate an unused register of a given type */ int find_unused_register(struct bblock * cblk, int rt, int *index) { register regarray cr; register int find, check, end, ravl, rskip, rcont; cr = (regarray) cblk->regstate; ravl = availreg(rt); rskip = skipreg(rt); rcont = contreg(rt); for (find = firstreg(rt); ravl--; find += rskip) { end = rcont; for (check = find; end--; check++) { if (cr->reg[check].status != NOTUSED) break; } if (end < 0) { *index = find; return (TRUE); } } return (FALSE); } /* * gtrg - get register of any type */ char *gtrg(register char *s) { register char c; for (;;) { for (c = *s++; (c & 0xc0) != 0xc0 && c; c = *s++); if (!c) return ((char *) NULL); if (*s & 0x80) return (s + 1); } } /* * gtrgstr - get register of any type and place a copy of it in str */ char *gtrgstr(register char *s, register char *str) { register char c; for (;;) { for (c = *s++; (c & 0xc0) != 0xc0 && c; c = *s++); if (!c) return ((char *) NULL); if (*s & 0x80) { *str = c; *(str + 1) = *s; *(str + 2) = '\0'; return (s + 1); } } } /* * gthrg - get hardware register */ char *gthrg(register char *s) { register char c; for (;;) { for (c = *s++; (c & 0xc0) != 0xc0 && c; c = *s++); if (!c) return ((char *) NULL); if (*s & 0x80 && !pseudoreg(s - 1)) return (s + 1); } } #ifdef FIFOS /* * gtfrg - get fifo register */ char *gtfrg(register char *s) { register char c; for (;;) { for (c = *s++; (c & 0xc0) != 0xc0 && c; c = *s++); if (!c) return ((char *) NULL); if (*s & 0x80 && fiforeg(s - 1)) return (s + 1); } } #endif /* * makerg - make a register of a given type and number */ void makerg(char *reg, int rt, int rnum) { *reg = (char) (0xc0 | (rt << 2) | (rnum >> 7)); *(reg + 1) = (char) (0x80 | (rnum & 0x7f)); } /* * makereg - make a register of a given type and number */ void makereg(char *reg, int rt, int rnum) { *reg = (char) (0xc0 | (rt << 2) | (rnum >> 7)); *(reg + 1) = (char) (0x80 | (rnum & 0x7f)); *(reg + 2) = '\0'; } /* * memtype - returns the type of a memory reference */ int memtype(char *mem) { register int type; if ((type = mems[(int) *mem]) == NOTYPE) { (void) fprintf(stderr, "vpo (memtype): bad memory type '%c'\n", *mem); exit(1); } return (type); } /* * gtmem - return next memory reference in the RTL string */ char *gtmem(register char *s) { register char c; register int depth; /* If we find a capital letter that denotes a valid memory type, followed by a '[' at this point, then we have found the start of a memory reference. We then scan forward to find the matching ']' that indicates the end of the memory reference, set "epos" and "bpos" appropriately, and return. */ while (c = *s++) { if (*s == '[' && mems[(int) c] != NOTYPE) { bpos = s++ - 1; depth = 1; while (c = *s++) { if (c == '[') depth++; if (c == ']' && !--depth) return (epos = s); } return ((char *) NULL); } } return ((char *) NULL); } /* * ismem - return TRUE if the string starts a memory reference */ int ismem(char *s) { return (mems[(int) *s] != NOTYPE && *(s + 1) == '['); } /* * canreplace - returns TRUE if there is a register available of a given type */ int canreplace(int type, regvec regstate, char *reg, int ifcheap, int ifcs) { register int check, rcont, end, find; regarray cr; int ravl, rskip; cr = (regarray) regstate; if ((type = localtype(type)) >= 0) { ravl = availreg(type); rskip = skipreg(type); rcont = contreg(type); for (find = firstreg(type); ravl--; find += rskip) { end = rcont; for (check = find; end--; check++) { if (cr->reg[check].status != NOTUSED || isused[check]) break; } if (end < 0) { makereg(reg, type, indextoreg(type, find)); if (ifcheap && !scratchreg(reg)) *reg = '\0'; else if (callersave(reg) > ifcs) *reg = '\0'; else { rcont = contreg(type); if (rcont == 1) cr->reg[find].status |= USED; else { while (rcont--) cr->reg[find++].status |= FOLLOWER; } return (TRUE); } } } } return (FALSE); } /* * cancolor - returns TRUE if there is a register available of a given type */ int cancolor(int type, vector regs, char *reg, int ifcheap) { register unsigned int check; register int rcont, end, find; int ravl, rskip; #ifdef RRLRA int class; char creg[REGSTRING]; #endif if ((type = localtype(type)) >= 0) { rskip = skipreg(type); rcont = allocreg(type); #ifdef RRLRA class = classreg(type); if (lastfound[class] >= 0) { ravl = availreg(type); for (find = firstreg(type); find < lastfound[class]; find += rskip) ravl--; while (ravl-- > 0) { end = rcont; for (check = (unsigned int) find; end--; check++) { /* Determine if we have reached the end of the scratch registers, if so, we fall out of this loop. */ makerg(creg, type, check); if (!scratchreg(creg)) { lastfound[class] = -1; goto fail; } if (vin(regs, check)) break; } if (end < 0) { makereg(reg, type, indextoreg(type, find)); if (ifcheap && !scratchreg(reg)) *reg = '\0'; else { lastfound[class] = find + 1; for (rcont = allocreg(type); rcont--; vinsert(®s, (unsigned int) find++)); return (TRUE); } } find += rskip; } } fail: #endif #define _TONES_STUFF ravl = availreg(type); #ifdef _TONES_STUFF if( ifcheap == FALSE ) { for( find = firstreg(type)+(ravl-1)*rskip; ravl--; find -= rskip ) { end = rcont; for( check = (unsigned int) find; end--; check++ ) if( vin(regs, check) ) break; if( end < 0 ) { makereg(reg, type, indextoreg(type, find)); if( !scratchreg(reg) ) { for( rcont = allocreg(type); rcont--; find++); vinsert(®s, (unsigned int) find); return (TRUE); } } } } else { #endif for (find = firstreg(type); ravl--; find += rskip) { end = rcont; for (check = (unsigned int) find; end--; check++) if (vin(regs, check)) break; if (end < 0) { makereg(reg, type, indextoreg(type, find)); if( !scratchreg(reg) ) fprintf(stdout, "# Allocated non-scratch register: %d\n", regnum(reg)); else fprintf(stdout, "# Allocated scratch register: %d\n", regnum(reg)); if (ifcheap && !scratchreg(reg)) *reg = '\0'; else { #ifdef RRLRA lastfound[class] = find + 1; #endif for (rcont = allocreg(type); rcont--; vinsert(®s, (unsigned int) find++)); return (TRUE); } } } #ifdef _TONES_STUFF } #endif } return (FALSE); } /* * regnew - return new register assignment vector */ vector regnew() { register unsigned int *ptr1, *end; register vector nptr; nptr = (vector) (ptr1 = MRALLOC); for (end = ptr1 + mrveclen; ptr1 != end; *ptr1++ = (unsigned int) 0); return (nptr); } /* * regcopy - copy a register assignment vector to another */ void regcopy(vector reg1, vector reg2) { register unsigned int *ptr1, *ptr2, *end; ptr1 = (unsigned int *) reg1; ptr2 = (unsigned int *) reg2; for (end = ptr1 + mrveclen; ptr1 != end; *ptr1++ = *ptr2++); } #ifdef MEASURE /* * get_freereg - allocate a register that is either scratch or will be saved */ int get_freereg(struct bblock * cblk, struct list * ptr, int num, int type, char *reg, char *mapreg) { regarray tr; vector regs; /* Determine which registers are live at this point in the function */ regs = live_regs(cblk, ptr); /* Attempt to allocate a suitable register */ tr = (regarray) top->regstate; while (cancolor(type, regs, reg, FALSE)) { /* Determine which register the register allocated will actually map to when it is emitted. */ makereg(mapreg, type, map(reg)); /* If the register maps to a scratch register, then it can be used without any problems. */ if (scratchreg(mapreg)) { reg += 3; mapreg += 3; if (!--num) { *reg = *mapreg = '\0'; mrfree(regs); return (TRUE); } } /* If the register is already being used elsewhere in the function, then go ahead and use it at this point. */ else if (tr->reg[regtoindex(type, regnum(reg))].status != NOTUSED) { reg += 3; mapreg += 3; if (!--num) { *reg = *mapreg = '\0'; mrfree(regs); return (TRUE); } } } /* Return indicating that no suitable register was available */ mrfree(regs); *reg = *mapreg = '\0'; return (FALSE); } #endif /* * inithardregs - set up register mapping info for hardware registers */ void inithardregs() { #ifdef HREGINFO register int index; for (index = 0; index < HREGINFO; index++) { (void) strcpy(sets[regallocptr].item, _hrinfo[index].name); sets[regallocptr].status = _hrinfo[index].flags; sets[regallocptr].num = regallocptr; vecmap[regname(regallocptr)] = regallocptr; regallocptr++; } #endif } /* * markinvariant - mark registers that are always invariant in loops */ void markinvariant() { register struct setlist *sptr; MARKINVARIANT } /* * aliases - given a hardware register, return a list of all aliases */ char *aliases(register char *reg) { return (_aliases[regtype(reg)][regnum(reg)]); } /* * regtoindexf - return regtoindex macro value as a function */ int regtoindexf(int rt, int reg) { return (regtoindex(rt, reg)); } /* * allocregf - return allocreg() macro value as a function */ int allocregf(int rt) { return ((int) allocreg(rt)); } /* * contregf - return contreg() macro value as a function */ int contregf(int rt) { return ((int) contreg(rt)); } /* * is_cc - returns TRUE is the item is a condition code token */ int is_cc(register char *s) { return (IS_CC(s)); } /* * set_cc - returns TRUE is the RTL sets the condition codes */ int set_cc(register char *s) { return (SET_CC(s)); } /* * checktype - check two types for global allocation compatibility */ int checktype(int prev, int new) { return ((prev == NOTYPE) ? new : (int) _checktype[prev][new]); }