/************************************************************************/ /* */ /* 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/locals.c,v $ $Date: 2004/08/13 01:48:59 $ $Revision: 1.5 $ $Name: $ Log of changes: $Log: locals.c,v $ Revision 1.5 2004/08/13 01:48:59 avdhoot debugged register allocation for small test cases Revision 1.4 2003/12/04 01:08:59 jpmarath fixes for alignment in function fixentry code Revision 1.3 2003/11/08 20:29:31 jpmarath Changes to setup powerpc-vpo correctly. Major ones: 1. mach.h in powerpc-vpo/driver modified to setup "ppc" environment" 2. added yyerror to YACC parser in vpo.out, makes it work correctly. earlier it was linking to some other yyerror, and exiting silently. Revision 1.1.1.1 2003/10/29 01:00:22 avdhoot power pc version of vpo Revision 1.4 1999/01/06 15:36:59 jwd Added VET directives. Revision 1.3 1998/04/03 18:19:37 jwd First ANSI C version. *************************************************************************/ /*-------------History of Changes ------------------- 1/12/98: Modified for ANSI-C function prototyping ---------------------------------------------------*/ #include #include #include #include "vpo.h" #include "assign.h" #include "cdmotion.h" #include "controlflow.h" #include "dataflow.h" #include "links.h" #include "misc.h" #include "vectors.h" #include "vpo2.h" #include "regs.h" #include "locals.h" #include "regs2.h" /* Machine Dependent */ #include "rtl.h" /* Machine Dependent */ #ifdef VET #include "../lib/view.h" #endif /* * This file contains functions to perform global register allocation and * associated optimizations on procedures. */ struct locuse *locs = NULL; /* local variable and argument info */ struct locuse *loce = NULL; /* last item in local information */ struct ignode *igptr = NULL; /* pointer to coloring graph */ struct ignode *iglast = NULL; /* pointer to end of coloring graph */ int csnum[MAXREGS]; /* callersave points for each reg */ extern char *fn; extern int swd, swr, swo, sww; extern struct bblock *top; extern struct loopl *loope; extern int hascs; extern int minargrefs, minlocrefs; extern int ignums; extern int regallocptr; extern unsigned short gallocptr; extern int isused[MAXREGS]; struct list *locsub(struct locuse *, struct list *,int,char*); /* * simple_global_allocation - perform simple global register allocation */ int simple_global_allocation(int invocation, int *csalloc) { register struct bblock *cblk; register struct locuse *ptr; register struct list *rtlptr; int change, first, ifcheap, ifcs; char reg[REGSTRING]; /* 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_simple_global_allocation", invocation)) dump_function_i("before simple_global_allocation()", invocation, SHOW_SE); first = (invocation == 1); #ifdef VET begin_phase(REGALLOC_PHASE); #endif /* If this is not the first invocation of this allocator, then forget all of the old (stale) local variable information. */ if (!first) clean_locals(); /* Determine where locals are used in the function. These data are essential for determining the payoff of allocating registers to locals. */ locals_used(); change = FALSE; for (ptr = locs; ptr; ptr = ptr->next) { /* If this local has been marked to be ignored, then ignore it */ if (ptr->nouse) continue; /* Emit warning messages about locals that are declared but not used and perform a cost-benefit analysis on each local. */ ifcheap = FALSE; if (!ptr->reps) { if (first && !sww) { if (ptr->arg) (void) fprintf(stderr, "vpo: argument '%s'", ptr->item); else (void) fprintf(stderr, "vpo: local '%s'", ptr->item); if (fn) (void) fprintf(stderr, " not used in %s()\n", fn); else (void) fprintf(stderr, " not used\n"); } ptr->nouse = TRUE; continue; } else if (!ptr->arg && ptr->reps == 1) { if (first && !sww) { (void) fprintf(stderr, "vpo: local '%s'", ptr->item); if (fn) (void) fprintf(stderr, " referenced only once in %s()\n", fn); else (void) fprintf(stderr, " referenced only once\n"); } ptr->nouse = TRUE; continue; } else if (ptr->vol) continue; else if (!ptr->arg && ptr->reps < minlocrefs) { ptr->nouse = TRUE; ifcheap = TRUE; } else if (ptr->arg && ptr->reps < minargrefs) { ptr->nouse = TRUE; ifcheap = TRUE; } /* Determine the maximum number of saves and restores that can be tolerated if a callersaves register is allocated to this local. */ ifcs = ptr->reps - minargrefs; if (ifcs < 0) ifcs = 0; /* If there is no reason why this local should not be allocated to a register, then attempt to allocate a register of the appropriate type to this local. If a register is allocated, modify the function to change all of the references of the local to references to the register. */ if (canreplace(ptr->type, top->regstate, reg, ifcheap, ifcs)) { /* * Let fixentry know that this register is used. */ isused[regtoindex(ptr->type, regnum(reg))] = TRUE; #ifdef VET begin_trans(VET_OPT_TRANS); #endif /* Indicate that this item has no more references, this may change if the item is an argument or if it has been allocated to a callersaves register. */ ptr->reps = 0; /* If the local is an argument, then we need to place an initial load of the register at the entry point of the function unless the argument enters the function via a register, in which case it will be the task of fixentry() to ensure that the entry register and the use register match up. */ if (ptr->arg) { if (regarg(ptr)) (void) strcpy(ptr->regin, reg); else { load(ptr->type, TRUE, ptr->code, top, top->rtls, reg, TRUE); ptr->reps++; } } /* Modify the function to change all of the references of the local to references to the allocated register. */ for (cblk = top; cblk; cblk = cblk->down) { for (rtlptr = cblk->rtls; rtlptr; rtlptr = rtlptr->next) { if (cnts(rtlptr) && vin(ptr->olist, rtlptr->onum)) loctoreg(ptr, rtlptr, ptr->type, reg); } } /* Indicate that the local has been allocated to a register and that some modifications have been made to the function. If the register that the local was allocated to needs to be saved and restored around function calls, then we place the value of the register in the "csreg" field so that move_caller_save() knows that this item needs to be looked at. */ ptr->reg = ptr->nouse = change = TRUE; if (hascs && callersave(reg)) { *csalloc = TRUE; (void) strcpy(ptr->csreg, reg); } #ifdef VET end_trans(); #endif } } #ifdef VET end_phase(REGALLOC_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_after_simple_global_allocation", invocation)) dump_function_i("after simple_global_allocation()", invocation, SHOW_SE); /* Return indicating if any changes have been made to the function */ return (change); } /* * color_life - * Here we try to allocate a register for the lifetime of a local * variable. */ struct ignode* color_life(struct ignode* iptr, vector allocate, int* change) { register struct ignode *sptr; struct ignode *eptr; struct list *rtlptr; struct locuse *ptr; struct conflict *cptr; int freq, type, first, ifcheap, entry; char reg[REGSTRING]; ptr = iptr->item->local; /* Look through all of the "blobs" of life that comprise this life of a local to determine which registers it conflicts with, what type it is referenced as, how often it is referenced, and if it extends to the entry point of the function. */ regcopy(allocate, iptr->regs); type = iptr->type; freq = iptr->freq; for (sptr = iptr->nsib; sptr != iptr; sptr = sptr->nsib) { /* This macro is created by regtool in order to include in the "allocate" vector all of the items that conflict with this "blob" of life (as given by the "sptr->regs" item). On most machines, this macro will emit the following code: *allocate |= *sptr->regs; but on machines where there are more allocable registers than there are bits in an "int", there will be additional lines to move the whole register vector as quickly as possible. */ REGINC(allocate, sptr->regs); /* Here we ensure that the item was referenced consistently with respect to its type. If the same local is referenced as an "int" in one place and as a "double" in another, then there is some obvious confusion as to which type of register should be allocated for it, so we mark it as a local that should not be allocated. */ if (sptr->type != NOTYPE) { if ((type = checktype(type, sptr->type)) == NOTYPE) { ptr->nouse = TRUE; break; } } /* Add the number of times that the item is referenced in this "blob" of life to its overall reference count. */ freq += sptr->freq; } /* Determine if the local is used often enough to justify allocating it to a register. If it is used infrequently, it might be okay to allocate it to a scratch register, if one is available, since these registers are "cheap" to use relative to non-scratch ones. */ if (ptr->nouse || !freq) { iptr->status |= CONSIDERED; for (sptr = iptr->nsib; sptr != iptr; sptr = sptr->nsib) sptr->status |= CONSIDERED; return iptr->next; } if (!ptr->arg && freq < minlocrefs) ifcheap = TRUE; else if (ptr->arg && freq == 1 && !regarg(ptr)) { iptr->status |= CONSIDERED; for (sptr = iptr->nsib; sptr != iptr; sptr = sptr->nsib) sptr->status |= CONSIDERED; fprintf(stdout, "# color_life: exit 2\n"); return iptr->next; } else if (ptr->arg && freq < minargrefs) { // In this case, minargrefs == 2 ifcheap = TRUE; iptr->status |= CONSIDERED; for (sptr = iptr->nsib; sptr != iptr; sptr = sptr->nsib) sptr->status |= CONSIDERED; return iptr->next; } else ifcheap = FALSE; /* Attempt to allocate a register for this life of the local. If one is found, then update the RTLs of the function to change the local variable reference to appropriate register references. */ if (cancolor(type, allocate, reg, ifcheap)) { /* * Let fixentry know that this register was used in the function. */ isused[regtoindex(type, regnum(reg))] = TRUE; #ifdef VET begin_trans(VET_OPT_TRANS); #endif sptr = iptr; entry = !ptr->arg; do { /* If this item of life extends to the entry point of the function, then set "entry" to TRUE and place the register that was allocated to this local in the "regin" field of the local variable information structure. */ if (!entry && sptr->ptr == top) { for (eptr = top->conin; eptr; eptr = eptr->conin) { if (eptr == sptr) { entry = TRUE; if (regarg(ptr)) { (void) strcpy(ptr->regin, reg); ptr->atype = type; sptr->status &= ~MUSTLOAD; } break; } } } /* Mark this local item as "colored" and the register that is allocated to it as unavailable for allocation to any of the other locals whose life intersect this one. */ sptr->status |= COLORED; for (cptr = sptr->conflicts; cptr; cptr = cptr->next) touchreg(cptr->ptr->regs, reg); /* Change the local variable references in the function to refer to the appropriate register instead. Note that in some instances we must load and spill the value of the local when indicated by the interference graph. */ if (rtlptr = sptr->start) { for (;;) { if (cnts(rtlptr) && vin(ptr->olist, rtlptr->onum)) { loctoreg(ptr, rtlptr, type, reg); } if (rtlptr == sptr->end) break; if (!(rtlptr = rtlptr->next)) break; } if (sptr->status & MUSTLOAD) load(type, ptr->arg, ptr->code, sptr->ptr, sptr->start, reg, TRUE); } else if (sptr->status & MUSTLOAD) { rtlptr = sptr->ptr->rtlend; if (rtlptr && rtlptr->val && is_rjmp(rtlptr->val)) { if (rtlptr->prev) rtlptr = rtlptr->prev; } else if (!rtlptr || !rtlptr->val || !is_pc(rtlptr->val)) rtlptr = (struct list *) NULL; } /* Continue on to the next "blob" that makes up part of this local's life. */ sptr = sptr->nsib; } while (sptr != iptr); #ifdef VET end_trans(); #endif /* Note that changes have been made to the function. Also update the local variable usage count and set the "reg" field when no references remain to the local in order for fixentry() to know that it should not allocate any space to hold the local. */ *change = TRUE; ptr->reps -= freq; if (!ptr->reps) ptr->reg = ptr->nouse = TRUE; /* Since we are done with this local variable, move on to the next */ return iptr->next; } else { /* No register could be allocated for the entirety of the local */ /* Mark all "blobs" that make up this life as considered, since there is no use in trying to consider them again as a whole. They will and should, however, be considered in other groupings. */ iptr->status |= CONSIDERED; for (sptr = iptr->nsib; sptr != iptr; sptr = sptr->nsib) sptr->status |= CONSIDERED; /* Since it can still be colored on a blob-by-blob basis, pass this local variable off to another handler */ return iptr; } } /* * color_blob - * Here we just try to allocate a regsiter on a blob-by-blob basis * instead of the entire lifetime of a local variable. */ struct ignode* color_blob(struct ignode* iptr, vector allocate, int* change) { register struct ignode *sptr; struct ignode *eptr; struct list *rtlptr; struct locuse *ptr; struct conflict *cptr; int freq, type, first, ifcheap, entry; char reg[REGSTRING]; /* Estimate the releative advantage of allocating this "blob" of life to a register. If the item needs to be loaded or spilled at its life boundaries, then these factors count against it. */ freq = iptr->freq; if (iptr->status & ISSET) freq -= (iptr->ptr->freq << 4) + 1; if (iptr->status & ISUSED) freq -= (iptr->ptr->freq << 4) + 1; /* If the item would cost most to load and spill that it would save on references or it is only used in a single RTL, then there is no advantage in allocating it to a register. */ if (freq <= 0 || iptr->start == iptr->end) { return iptr->next; } /* Ensure that the item is used enough to warrant its allocation. Also, determine if the register used must be cheap to make the allocation worthwhile. */ ptr = iptr->item->local; if (!ptr->arg && freq < minlocrefs) ifcheap = TRUE; else if (ptr->arg && freq == 1 && !regarg(ptr)) { return iptr->next; } else if (ptr->arg && freq < minargrefs) ifcheap = TRUE; else ifcheap = FALSE; /* Attempt to locate a suitable register to contain this "blob" of life. */ if (cancolor(iptr->type, iptr->regs, reg, ifcheap)) { /* * Let fixentry know that this register is used during this function. */ isused[regtoindex(type, regnum(reg))] = TRUE; #ifdef VET begin_trans(VET_OPT_TRANS); #endif /* Determine if this life "blob" reaches the entry point of the function. If it does, we set the "regin" field to indicate which register contains the argument at the entry point of the function. Also, if the local is passed to this function in a register, we abstain from placing a load of it at the entry point of the function, since fixentry() will ensure that the appropriate value winds up in the register given by the "regin" field for this local. */ if (iptr->ptr == top) { for (eptr = top->conin; eptr; eptr = eptr->conin) { if (eptr == iptr) { if (ptr->arg && regarg(ptr)) { (void) strcpy(ptr->regin, reg); ptr->atype = iptr->type; } if (!ptr->arg || regarg(ptr)) { iptr->status &= ~ISUSED; if (ptr->arg) iptr->status |= ISSET; } break; } } } /* Indicate that this "blob" has been colored and make the register used conflict with any "blobs" that are live simultaneously with this one. */ iptr->status |= COLORED; for (cptr = iptr->conflicts; cptr; cptr = cptr->next) touchreg(cptr->ptr->regs, reg); /* If the local is used (referenced) in this "blob" of life, then we must first load it before referencing it. */ rtlptr = iptr->start; if (iptr->status & ISUSED) load(iptr->type, ptr->arg, ptr->code, iptr->ptr, rtlptr, reg, FALSE); /* Change all of the RTLs that reference this local in the "blob" of life to appropriate register references. */ for (;;) { if (cnts(rtlptr) && vin(ptr->olist, rtlptr->onum)) loctoreg(ptr, rtlptr, iptr->type, reg); if (rtlptr == iptr->end) break; rtlptr = rtlptr->next; } /* If the local is set (modified) within this "blob" of life, then we must update its value before exiting the "blob". We must be sure not to place the store in a location that destroys a condition code value. */ if (cnts(rtlptr) && !is_pc(rtlptr->val)) rtlptr = rtlptr->next; if (iptr->status & ISSET) { if (rtlptr && rtlptr->val && is_rjmp(rtlptr->val) && sets_only_cc(rtlptr->prev)) rtlptr = rtlptr->prev; /* fprintf(stderr, "About to store a register inside color_blob\n"); */ store(iptr->type, ptr->arg, ptr->code, iptr->ptr, rtlptr, reg, FALSE); } #ifdef VET end_trans(); #endif /* Note the changes that have taken place because of this allocation. */ *change = TRUE; ptr->reps -= freq; if (!ptr->reps) ptr->reg = ptr->nouse = TRUE; } /* Having considered this "blob" singly, move on to the next one */ return iptr->next; } /* * color_gobal_allocation - allocates using a coloring algorithm */ int color_global_allocation(int invocation) { register struct ignode *iptr; struct locuse *ptr; vector allocate; int change; int first; /* 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_color_global_allocation", invocation)) dump_function_i("before color_global_allocation()", invocation, SHOW_LABELS | SHOW_USE | SHOW_NONRTLS | SHOW_SE); first = (invocation == 1); change = FALSE; /* Complain about locals that are declared and not used and items that are only written to (if the "no warning messages" flag is not set). */ #ifdef VET begin_phase(REGALLOC_PHASE); #endif for (ptr = locs; ptr; ptr = ptr->next) { if (ptr->nouse) continue; if (!ptr->reps) { if (first && !sww) { if (ptr->arg) (void) fprintf(stderr, "vpo: argument '%s'", ptr->item); else (void) fprintf(stderr, "vpo: local '%s'", ptr->item); if (fn) (void) fprintf(stderr, " not used in %s()\n", fn); else (void) fprintf(stderr, " not used\n"); } ptr->nouse = TRUE; } else if (first && !sww && !ptr->arg && ptr->reps == 1) { (void) fprintf(stderr, "vpo: local '%s'", ptr->item); if (fn) (void) fprintf(stderr, " referenced only once in %s()\n", fn); else (void) fprintf(stderr, " referenced only once\n"); ptr->nouse = TRUE; } else if (ptr->arg && ptr->reps == 1 && !regarg(ptr)) ptr->nouse = TRUE; } /* Generate an interference graph for the current function. Sort the nodes in the graph so that the most frequently used items are considered for allocation first. */ build_interference_graph(); sort_interference_graph(); /* Perform global register mapping using a map-coloring style algorithm which is driven by access frequency estimation information. */ allocate = regnew(); iptr = igptr; while (iptr) { /* fprintf(stderr, "Coloring local: %s\n", iptr->item->item); */ /* If the local has been identified as either one that should not be allocated to a register (because the code takes the address of it) or if it was declared as a volatile item (in ANSI C), then skip it. */ ptr = iptr->item->local; if (ptr->nouse || ptr->vol) { iptr = iptr->next; } /* Our first attempt at coloring is to consider the whole life of a specific item together at once. To do so, we consider all of the "blobs" of life that are related together at once. If we cannot do so, then we mark such "blobs" as CONSIDERED and move on to other possible strategies. */ else if ( !(iptr->status & (COLORED | CONSIDERED)) ) { /* fprintf(stderr, "entered: color_life iptr: %x\n", iptr); */ iptr = color_life(iptr, allocate, &change); /* fprintf(stderr, "exited: color_life iptr: %x\n", iptr); */ } /* Sometime in the future, I think it will be worthwhile to attempt allocation over the life of a loop. Some locals tend to be used heavily inside just one single loop. This would allow some items which cannot be allocated over their whole life, but are used heavily within a single loop to be allocated at such loops. else if( !(iptr->status & COLORED) ) { iptr = color_loop(iptr, &change); } */ /* If no register could be allocated for the whole life of a local, then consider individual life "blobs" to see if it is worthwhile to allocate the local to a register for the duration of a "blob". Note that we will have to consider the fact that a register load and spill might have to take place at the borders of the life. */ else if (!(iptr->status & COLORED)) { /* fprintf(stderr, "entered: color_blob\n"); */ iptr = color_blob(iptr, allocate, &change); /* fprintf(stderr, "exited: color_blob\n"); */ } /* This local has already been colored, so we skip on to the next one */ else iptr = iptr->next; } mrfree(allocate); /* Release the space allocated to hold the interference graph */ clear_interference_graph(); #ifdef VET end_phase(REGALLOC_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_after_color_global_allocation", invocation)) dump_function_i("after color_global_allocation()", invocation, SHOW_LABELS | SHOW_USE | SHOW_NONRTLS | SHOW_SE); /* Return indicating if any changes have been made to the function */ return (change); } /* * loctoreg - replace local reference with a register */ void loctoreg(struct locuse * ptr, struct list * rtl, int type, char *reg) { register struct list *lptr; if (!(rtl->type & ARGLINE) && (lptr = locsub(ptr, rtl, type, reg))) { combmark(lptr); lptr->cost = 0; lptr->kind = 0; lptr->type &= ~SIDEFFECT; if (lptr->se) { FREE(lptr->se); lptr->se = (char *) NULL; } #ifdef VET /* Type has changed and possibly the side effect was cleared. */ mod_side(lptr); #endif } } /* * locals_used - look for local variable references in the function */ void locals_used() { register struct locuse *ptr; register int i; register struct list *rtl; register struct bblock *cblk; int type, ind, set; char *c, code[REGSTRING]; /* Look through every basic block and every RTL in the function for local register references. Update the local information structure as each reference is found to indicate where each local is used. */ for (cblk = top; cblk; cblk = cblk->down) { for (rtl = cblk->rtls; rtl; rtl = rtl->next) { if (c = cnts(rtl)) { while (locget(&c, code, &type, &ind, &set, rtl)) { i = vecmap[USP(code)]; if (i < 0) { (void) fprintf(stderr, "vpo (locals_used): undeclared local reference\n"); exit(1); } ptr = sets[i].local; vinsert(&ptr->olist, rtl->onum); if (!ptr->nouse) { if (set) dinsert(&ptr->setin, cblk->bnum); else dinsert(&ptr->usedin, cblk->bnum); } if (ind) ptr->nouse = ptr->indref = TRUE; else if ((ptr->atype = checktype(ptr->atype, type)) == NOTYPE) ptr->nouse = TRUE; ptr->reps += (cblk->freq << 4) + 1; reorder_local(ptr); } } } } } /* * reorder_local - place local in order according to its "reps" field */ void reorder_local(register struct locuse * ptr) { register struct locuse *prev; /* Order this local in the coloring graph list according to the estimate of the number of times that it is referenced. */ while ((prev = ptr->prev) && prev->reps < ptr->reps) { if (ptr->next) ptr->next->prev = prev; prev->next = ptr->next; if (prev->prev) prev->prev->next = ptr; else locs = ptr; ptr->next = prev; ptr->prev = ptr->next->prev; ptr->next->prev = ptr; } } /* * sort_interference_graph - sort the interference graph nodes by "freq" */ void sort_interference_graph() { register struct igsort *sptr, *nptr, *rptr; register int find; struct igsort (*igptrs)[]; struct igsort tmp; struct ignode *ptr; int heap; /* Sort the interference graph according to the value of the "freq" field. This function utilizes a heap sort because its fast and I happen to like heap sorts. */ /* Check to be sure that there is something to sort */ if (!igptr) return; /* Allocate a heap of the appropriate size */ igptrs = (struct igsort(*)[]) SALLOC((int) ignums * sizeof(struct igsort)); heap = 0; for (ptr = igptr; ptr; ptr = ptr->next) { /* Insert the item into the next slot in the heap */ sptr = &(*igptrs)[++heap]; sptr->freq = ptr->freq; sptr->ptr = ptr; /* Percolate the item up to the point where its parent has a value at least as large as the item does. */ for (find = heap >> 1; find; find >>= 1) { nptr = &(*igptrs)[find]; if (sptr->freq > nptr->freq) { tmp = *nptr; *nptr = *sptr; *sptr = tmp; sptr = nptr; } else break; } } /* The top item in the heap is has the largest value */ sptr = &(*igptrs)[1]; igptr = iglast = sptr->ptr; /* Move the last item in the heap to the top and percolate it down to allow the next highest item to move up to the top. This is what the heap sort is all about. */ while (heap > 1) { *sptr = (*igptrs)[heap--]; find = 2; while (find <= heap) { nptr = &(*igptrs)[find]; if (find == heap) { if (sptr->freq < nptr->freq) { tmp = *nptr; *nptr = *sptr; *sptr = tmp; sptr = nptr; } break; } else { rptr = &(*igptrs)[find + 1]; if (rptr->freq > nptr->freq) { if (sptr->freq < rptr->freq) { tmp = *rptr; *rptr = *sptr; *sptr = tmp; sptr = rptr; find++; } else break; } else { if (sptr->freq < nptr->freq) { tmp = *nptr; *nptr = *sptr; *sptr = tmp; sptr = nptr; } else break; } } find <<= 1; } /* The new top is now the next item to go on the list */ sptr = &(*igptrs)[1]; iglast->next = sptr->ptr; iglast = sptr->ptr; } /* Mark the end of the list */ iglast->next = (struct ignode *) NULL; /* Return the heap */ FREE(igptrs); } /* * sets_only_cc - check RTL to ensure that is only sets condition codes */ int sets_only_cc(struct list * ptr) { register char *rtl, c; if (rtl = cnts(ptr)) { while (c = *rtl++) { if (c == '=' && !is_cc(rtl - 3)) return (FALSE); } return (TRUE); } return (FALSE); } /* * count_caller_save - count the number of callersave points in the function */ int count_caller_save() { register struct list *rtl; register char *c; register struct bblock *cblk; register int index; int rcont, rt, calls; /* Clear out the existing caller save items found for each register */ for (index = 0; index < MAXREGS; csnum[index++] = 0); /* Search through the function for caller save points and note which registers are affected. */ calls = FALSE; for (cblk = top; cblk; cblk = cblk->down) { for (rtl = cblk->rtls; rtl; rtl = rtl->next) { if (rtl->type & CSLINE) { for (c = rtl->val; *c; c += 2) { rt = regtype(c); index = regtoindex(rt, regnum(c)); for (rcont = contreg(rt); rcont--; index++) csnum[index] += (cblk->freq << 5) + 2; } calls = TRUE; } } } /* Indicate if any caller save lines are present in the function */ return (calls); } /* * callersave - return the number of times register must be saved and restored */ int callersave(char *reg) { register int index, max, rcont; int rt; max = 0; rt = regtype(reg); index = regtoindex(rt, regnum(reg)); for (rcont = contreg(rt); rcont--; index++) { if (csnum[index] > max) max = csnum[index]; } return (max); } /* * move_caller_save - locate the best place to save locals around calls */ void move_caller_save(int invocation) { register struct list *rtl; register int fptr, iptr; struct bblock *cblk, *hblk; struct list *ptr; struct locinfo item[MAXREGS]; struct blist *eptr; struct locuse *lptr; struct loopl *loop; /* 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_move_caller_save", invocation)) dump_function_i("before move_caller_save()", invocation, SHOW_LABELS | SHOW_SUCCS | SHOW_PREDS | SHOW_LOOP | SHOW_NONRTLS); /* The purpose of this routine is to locate the best place to save and restore registers that need to be saved by the caller around function calls. We only deal with registers that are allocated by the simple global register allocator in this function. First, we start out by locating the callersave points in the function. */ for (cblk = top; cblk; cblk = cblk->down) { for (rtl = cblk->rtls; rtl; rtl = rtl->next) { if (rtl->type & CSLINE) { /* Save a pointer to the local information record of every local that we must insert save and restore information for at this call site. If there are no locals that need to be saved and restored here, proceed to the next site. */ iptr = 0; for (lptr = locs; lptr; lptr = lptr->next) { if (*lptr->csreg && fmatch(rtl->val, lptr->csreg)) { item[iptr].ptr = lptr; item[iptr].st = FALSE; item[iptr++].ld = FALSE; } } if (!iptr) continue; /* Now examine the control-flow information to determine the outer- most loop in which this call site is in. We will then move on into inner loops unless we manage to save and restore all caller- save items. The reason we want to do this is because it pays off to move the save and restores outside of loops if possible, since these points will usually be executed less often. We can only do this, however, if the item we have to save and restore is not set or referenced inside the loop. */ for (loop = loope; iptr && loop; loop = loop->prev) { if (block_in_loop(loop, cblk)) { /* Now we examine all of the items that still need to be stored. If the item is not set inside the current loop, then we can store it just once at the preheader of the loop. */ for (fptr = 0; fptr < iptr; fptr++) { if (!(item[fptr].st || any_block_in_loop(loop, item[fptr].ptr->setin))) { /* Make a loop pre-header, if one doesn't already exist */ if (!(hblk = loop->preheader)) hblk = loop->preheader = preheader(loop->ptr); /* Find a suitable place to place a store operation at the end of the pre-header block. */ if (!((ptr = hblk->rtlend) && cnts(ptr) && is_pc(ptr->val))) ptr = (struct list *) NULL; /* Insert the store of the local and update the information to reflect the fact that the store has been placed. Note that we check to see if the item has already been stored in the pre-header of this loop and, if it has, we avoid placing another store at this point. */ lptr = item[fptr].ptr; if (!rexists(lptr->code, loop->stored)) { store(lptr->type, lptr->arg, lptr->code, hblk, ptr, lptr->csreg, TRUE); rinsert(lptr->code, &loop->stored); } item[fptr].st = TRUE; /* If the item is now both saved and restored, we can remove it from the list of items still needing attention. */ if (item[fptr].ld) { item[fptr].ptr = item[--iptr].ptr; item[fptr].st = item[iptr].st; item[fptr--].ld = item[iptr].ld; } } /* Now we examine all of the items that we still need to load. If there are no sets or uses of the item in this loop, then we can place the load at the exit points of the loop. */ if (!(item[fptr].ld || any_block_in_loop(loop, item[fptr].ptr->setin) || any_block_in_loop(loop, item[fptr].ptr->usedin))) { /* Place a load at each exit point of the loop. If the exit points are not adequate for placing stores (because more than just the exit of this loop flows through it), then make a suitable exit points. */ if (!rexists(lptr->code, loop->loaded)) { for (eptr = loop->exits; eptr; eptr = eptr->next) { hblk = loop_exit(loop, eptr->ptr); lptr = item[fptr].ptr; load(lptr->type, lptr->arg, lptr->code, hblk, hblk->rtls, lptr->csreg, TRUE); } rinsert(lptr->code, &loop->loaded); } /* Note the fact that this item has been loaded. If the item has been both loaded and stored, then we can remove it from the list of items that still require consideration. */ item[fptr].ld = TRUE; if (item[fptr].st) { item[fptr].ptr = item[--iptr].ptr; item[fptr].st = item[iptr].st; item[fptr--].ld = item[iptr].ld; } } } } } /* If there are any items left that we were not able to locate a suitable place to save and restore for, we must place the save and restore instructions immediately before and after this callersave site. */ if (iptr) { for (ptr = rtl->prev; !(ptr->type & RTLINE); ptr = ptr->prev); for (fptr = 0; fptr < iptr; fptr++) { if (!item[fptr].st) { lptr = item[fptr].ptr; store(lptr->type, lptr->arg, lptr->code, cblk, ptr, lptr->csreg, TRUE); } if (!item[fptr].ld) { lptr = item[fptr].ptr; load(lptr->type, lptr->arg, lptr->code, cblk, rtl, lptr->csreg, TRUE); } } } } } } /* Now mark all items that were taken care of by this fuction so that we don't attempt to save and restore them in a future pass through this function. */ for (lptr = locs; lptr; lptr = lptr->next) *lptr->csreg = '\0'; /* 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_move_caller_save", invocation)) dump_function_i("before move_caller_save()", invocation, SHOW_LABELS | SHOW_SUCCS | SHOW_PREDS | SHOW_LOOP | SHOW_NONRTLS); } /* * clean_locals - selectively forget some things about locals */ void clean_locals() { register struct locuse *ptr; for (ptr = locs; ptr; ptr = ptr->next) { ptr->reps = 0; ptr->indref = FALSE; if (!(ptr->nouse = ptr->reg)) ptr->atype = NOTYPE; vfree(ptr->olist); ptr->olist = vinit(); dfree(ptr->setin); ptr->setin = dinit(); dfree(ptr->usedin); ptr->usedin = dinit(); } } /* * clear_locals - return local variable information structures to the heap */ void clear_locals() { #ifndef DISPOSE register struct locuse *ptr, *dptr; ptr = locs; while (ptr) { dptr = ptr; ptr = ptr->next; free(dptr->item); vfree(dptr->olist); dfree(dptr->setin); dfree(dptr->usedin); free((char *) dptr); } #endif locs = (struct locuse *) NULL; } /* * declaration - handle local and global variable declarations */ int declaration(char *val) { register struct locuse *ptr; int blev, type; char *a, *start, id[MAXSTRING], code[REGSTRING]; /* The first item in a declare line is the identifier name */ start = val; a = id; while ((*a++ = *val++) != '\t'); *(a - 1) = *(val - 1) = '\0'; /* The second item is the two-character code that will be used in RTLs */ *code = *val++; *(code + 1) = *val++; *(code + 2) = '\0'; val++; /* The third item is the identifier level: 0 -- global 1 -- argument 2 -- normal local >2 -- locals within blocks */ blev = atoi(val); val = is_const(val); if (!blev) { if (vecmap[USP(code)] < 0) { vecmap[USP(code)] = gallocptr; for (a = globals + gallocptr; *a++ = *start++; gallocptr++) { if (gallocptr == (unsigned short) (GLOBALS - 1)) { (void) fprintf(stderr, "vpo (declaration): out of global storage\n"); exit(1); } } gallocptr++; } else { (void) fprintf(stderr, "vpo (declaration): global code multiply declared: id = \"%s\"\n",id); exit(1); } } else { if (vecmap[USP(code)] < 0) { if (regallocptr == MAXRVEC) { (void) fprintf(stderr, "vpo (declaration): too many items\n"); exit(1); } (void) strcpy(sets[regallocptr].item, code); sets[regallocptr].num = regallocptr; vecmap[regname(regallocptr)] = regallocptr; ptr = (struct locuse *) SALLOC(sizeof(struct locuse)); if (!locs) { ptr->prev = (struct locuse *) NULL; locs = loce = ptr; } else { loce->next = ptr; ptr->prev = loce; loce = ptr; } ptr->next = (struct locuse *) NULL; sets[regallocptr].local = ptr; regallocptr++; ptr->item = start; ptr->level = blev; *(code + 2) = '\0'; (void) strcpy(ptr->code, code); ptr->setin = dinit(); ptr->usedin = dinit(); ptr->size = ptr->vol = 0; ptr->reps = (swr) ? 0 : 3; ptr->indref = (swr || swo) ? FALSE : TRUE; ptr->nouse = ptr->reg = ptr->structure = FALSE; ptr->arg = (blev == 1) ? TRUE : FALSE; ptr->atype = NOTYPE; *ptr->regin = '\0'; *ptr->csreg = '\0'; ptr->olist = vinit(); ptr->conptr = (struct ignode *) NULL; } else { (void) fprintf(stderr, "vpo (declaration): local code multiply declared\n"); exit(1); } } /* The fourth item is the register type that corresponds to the type that the item was declared as. This may or may not be the register type that will be used to actually hold this local if it is allocated to a register, but it does provide a method to differentiate between locals that should be allocated to address registers versus data registers on machines like the Motorola 68020. The base type is limited to the eight least-significant bits of the type. The ninth bit, if set, indicates that the item is a structure. This field is not used on all machines, only on those that need to know that the item is a structure for some particular reason. */ type = atoi(++val); val = is_const(val); if (blev) { ptr->type = type & 255; if (type & 256) ptr->structure = TRUE; } /* The fifth (optional) item is the size of the item */ if (blev && *val) { ptr->size = atoi(++val); val = is_const(val); /* The sixth (optional) item is the offset of the item */ if (*val) { ptr->offset = atoi(++val); val = is_const(val); /* The seventh (optional) item is non-zero if the item is volatile */ if (*val) ptr->vol = atoi(++val); } } return (blev); } /* * makeglobal - sets up a new global identifier and returns its code */ void makeglobal(char *id, char *code) { register int i; char *a; /* Locate a free slot for the global */ for (i = 0x0fff; i >= 0; i++) { *code = (char) (0x80 | ((i & 0x0f80) >> 7)); *(code + 1) = (char) (0x80 | (i & 0x007f)); if (vecmap[USP(code)] == -1) break; } if (i < 0) { (void) fprintf(stderr, "vpo (makeglobal): out of global storage\n"); exit(1); } /* Insert the identifier in the appropriate slot */ vecmap[USP(code)] = gallocptr; for (a = globals + gallocptr; *a++ = *id++; gallocptr++) { if (gallocptr == (unsigned short) (GLOBALS - 1)) { (void) fprintf(stderr, "vpo (makeglobal): out of global storage\n"); exit(1); } } gallocptr++; *(code + 2) = '\0'; }