8 /// Used to generate a unique name for the spill location.
10 /// Set of all iTemps spilt onto the stack.
12 /// Similar to stackSpill
15 /// Bitvector of all registers used in this function.
16 bitVect *funcUsedRegs;
17 /// If a bit is set in this then the iCode at that sequence has had
18 /// registers allocated.
24 static REG *_findRegById(REG_ID id)
26 REG *r = port_data.regs;
37 static REG *_getSubReg(REG *r, int size, int offset)
39 wassert(r->size >= size);
41 if (r->size == size) {
45 // We use the hiding table to get the parts of the register.
47 wassert(offset == 0 || offset == 1);
48 return _findRegById(r->hides[offset]);
52 return _findRegById(r->hides[2]);
59 static int _numRegsAvailable(int size)
61 REG *r = port_data.regs;
65 if (r->size == size && r->used == 0)
73 static void _setClearUsed(REG_ID id, int clear)
75 REG *r = _findRegById(id);
79 // The parent shouldnt be able to be allocated if this child
81 wassert((r->used & REG_USED_HIDDEN) == 0);
82 r->used |= REG_USED_HIDDEN;
85 wassert((r->used & REG_USED_HIDDEN) != 0);
86 r->used &= ~REG_USED_HIDDEN;
90 static void _markAsUsed(REG_ID id)
92 _setClearUsed(id, FALSE);
95 static void _markAsFree(REG_ID id)
97 _setClearUsed(id, TRUE);
100 static REG *_allocateReg(int size)
102 REG *r = port_data.regs;
105 if (r->size == size && r->used == 0) {
106 // Now go through the interference table and mark all other
107 // registers as used.
109 for (i=0; i < NUM_OF(r->hides); i++) {
110 if (r->hides[i] == REG_ID_NONE) {
113 _markAsUsed(r->hides[i]);
123 static bitVect *_markRegBits(bitVect *v, REG *r)
127 // Mark the primary register.
128 v = bitVectSetBit(v, r->id);
130 // Now add all the hidden registers.
131 for (i=0; i < NUM_OF(r->hides); i++) {
132 if (r->hides[i] == REG_ID_NONE) {
135 v = bitVectSetBit(v, r->hides[i]);
141 static void _freeReg(REG *r)
144 wassert(r->used == REG_USED);
148 for (i=0; i < NUM_OF(r->hides); i++) {
149 if (r->hides[i] == REG_ID_NONE) {
152 _markAsFree(r->hides[i]);
156 static void _freeAllRegs(viod)
158 REG *r = port_data.regs;
166 static void _dumpRegs(void)
168 REG *r = port_data.regs;
171 printf("%u\t%u\t%s\t%u\n", r->size, r->id, r->name, r->used);
176 void izt_init(REG *regs)
179 port_data.regs = regs;
182 /// Lower register pressure by packing iTemps where possible.
183 static void _packRegisters(eBBlock *ebp)
185 // PENDING: Assignment packing
186 // PENDING: Mark address of a true symbol as remat.
187 // PENDING: Propagate remat through equals.
188 // PENDING: Assign bitwise which is followed by a conditional into carry.
189 // PENDING: Pack for one use on pointer get or set. Assumes that the pointer
190 // is stored in the scratch register.
191 // PENDING: Pack short use iTemps into ACC or the scratch register.
194 static void _computeRequiredRegs(void)
199 // Iterate over each live range.
200 for (sym = hTabFirstItem(liveRanges, &k); sym ;
201 sym = hTabNextItem(liveRanges, &k)) {
205 // If the symbol is never used, then next.
206 if ((sym->liveTo - sym->liveFrom) == 0)
209 // Only temporaries need registers.
213 // Conditionals live in carry and dont need registers.
214 if (sym->regType == REG_TYPE_CND)
218 #if 0 // PENDING. Currently we dont compute ruonly or accuse.
219 if (sym->ruonly || sym->accuse) {
220 if (IS_AGGREGATE(sym->type) || sym->isptr)
221 sym->type = aggrToPtr(sym->type,FALSE);
225 // We need registers.
226 if (IS_AGGREGATE(sym->type) || sym->isptr) {
227 // Turn an aggregate into something real.
228 sym->type = aggrToPtr(sym->type, FALSE);
231 sym->nRegs = getSize(sym->type);
232 wassert(sym->nRegs <= 4);
236 static bool _doesntNeedRegs(iCode *ic)
238 // Some types of instructions dont need registers.
239 // PENDING: Flush out the types and make processor specific.
241 ic->op == JUMPTABLE ||
251 static bool _willCauseSpill(int size)
253 return _numRegsAvailable(size) == 0;
256 static void _deassignLRs(iCode *ic, eBBlock *ebp)
263 for (sym = hTabFirstItem(liveRanges, &ignored); sym; sym = hTabNextItem(liveRanges, &ignored)) {
265 // Has this symbol expired yet?
266 if (sym->liveTo > ic->seq) {
267 // No. Cant deassign.
271 // It has expired. Free up the resources.
273 // If it was spilt, then free up the stack spill location.
275 if (sym->stackSpil) {
276 sym->usl.spillLoc->isFree = 1;
282 // If it currently has no registers assigned, then continue.
283 if (bitVectBitValue(_G.regAssigned, sym->key) == 0) {
287 // If it has no registers assigned to it, then continue.
288 if (sym->nRegs == 0) {
292 // Mark this sym as not having registers assigned.
293 bitVectUnSetBit(_G.regAssigned, sym->key);
295 // Free the registers.
296 _freeReg(sym->regs[0]);
298 // If deallocating will free up enough registers for this iCode
299 // then steal them immediatly.
300 if (IC_RESULT(ic) && !_doesntNeedRegs(ic)) {
301 result = OP_SYMBOL(IC_RESULT(ic));
302 if (result && // Has a result
303 result->liveTo > ic->seq && // and lives past this instruction
304 result->liveTo <= ebp->lSeq && // and doesnt go past this block
305 result->nRegs && // and actually needs registers
306 !result->isspilt && // and doesnt have them yet
307 !result->remat && // and wouldnt waste them
308 !bitVectBitValue(_G.regAssigned, result->key) && // doesnt have them yet
309 !_willCauseSpill(result->nRegs)
311 result->regs[0] = _allocateReg(result->nRegs);
317 /// Returns true if the live range of the given symbol doesnt overlap
318 /// with any of the live ranges in the set.
319 static bool _noOverlap (set *itmpStack, symbol *fsym)
323 for (sym = setFirstItem(itmpStack); sym; sym = setNextItem(itmpStack)) {
324 if (sym->liveTo > fsym->liveFrom) {
331 /// Set operator that returns 1 if a free spill location is found.
332 DEFSETFUNC(_stackIsFree)
335 V_ARG(symbol **,sloc);
336 V_ARG(symbol *,fsym);
338 // Dont bother if one has already been found.
342 if (sym->isFree && // This location is free...
343 _noOverlap(sym->usl.itmpStack, fsym) && // and its usage doesnt overlap with the usage of this sym
344 getSize(sym->type) >= getSize(fsym->type) && // and the location is big enough to hold the sym
346 // All good. Take this location.
356 /// Create a new spill location on the stack for this symbol.
357 symbol *_createStackSpill(symbol *sym)
361 // Try to reuse an exisiting spill location.
362 if (applyToSet(_G.spill.set, _stackIsFree, &sloc, sym)) {
363 // Found one. Take it over.
364 sym->usl.spillLoc = sloc;
365 sym->stackSpil = TRUE;
367 addSetHead(&sloc->usl.itmpStack, sym);
371 // No existing location. Time to create one.
372 // Give it a pretty name.
373 sprintf(buffer, "sloc%d", ++_G.spill.loc);
375 sloc = newiTemp(buffer);
378 sloc->type = copyLinkChain(sym->type);
379 sloc->etype = getSpec(sloc->type);
380 SPEC_SCLS(sloc->etype) = S_AUTO ;
384 // "To prevent compiler warning"
387 // Increase the local variable stack size on this function.
388 if (IN_STACK(sloc->etype)) {
389 currFunc->stack += getSize(sloc->type);
390 _G.stackExtend += getSize(sloc->type);
392 // The IZT port currently doesnt support loading locals into data space.
396 // And add it to the spill set.
397 addSetHead(&_G.spill.set, sloc);
398 sym->usl.spillLoc = sloc;
399 sym->stackSpil = TRUE;
401 // "Add it to the set of itempStack set of the spill location
402 addSetHead(&sloc->usl.itmpStack,sym);
407 static void _spillThis(symbol *sym)
409 // Create a spill location if it needs one and doesnt have one yet.
410 if (!(sym->remat || sym->usl.spillLoc)) {
411 _createStackSpill(sym);
415 // Add it to the spilt set.
416 _G.spill.vect = bitVectSetBit(_G.spill.vect, sym->key);
417 // and remove it from the 'has registers' set.
418 bitVectUnSetBit(_G.regAssigned, sym->key);
420 // Free up any registers that were assigned to this.
422 _freeReg(sym->regs[0]);
426 // CHECK: If this sym now has a spill location, mark it as allocated
427 // so that the stack packing later doesnt remove it.
428 if (sym->usl.spillLoc && !sym->remat) {
429 sym->usl.spillLoc->allocreq = TRUE;
435 static bitVect *_findSpillable(iCode *ic)
439 // First create a copy of the currently live ranges.
440 spillable = bitVectCopy(ic->rlive);
441 // Remove those which are already spilt.
442 spillable = bitVectCplAnd(spillable, _G.spill.vect);
443 // Remove those that this iCode uses.
444 spillable = bitVectCplAnd(spillable, ic->uses);
445 // Remove those that this iCode defines.
446 bitVectUnSetBit(spillable, ic->defKey);
448 // Only those that have registers assigned can actually be spilt :)
449 spillable = bitVectIntersect(spillable, _G.regAssigned);
454 /// Finds the least used live range
455 static symbol *_leastUsedLR(set *sset)
457 // sym is the currently least used symbol.
459 // walk walks the list of symbols in the scan set.
462 // Use the first as the seed.
463 sym = walk = setFirstItem(sset);
466 // Prefer spilling the symbol with the least allocated registers.
468 if (walk->used == sym->used) {
469 if (getSize(walk->type) < getSize(sym->type)) {
473 else if (walk->used < sym->used) {
474 // This is used less than the current best. It looses.
478 walk = setNextItem(sset);
481 setToNull((void **)&sset);
487 /// Applies a function to a given set of live ranges.
488 static set *_liveRangesWith(bitVect *lrs, int (func)(symbol *,eBBlock *, iCode *),
489 eBBlock *ebp, iCode *ic)
494 // Dont do anything if the bitVect is empty.
495 if (!lrs || !lrs->size)
498 for (i = 1; i < lrs->size; i++ ) {
501 // If this bit isnt turned on, skip.
502 if (!bitVectBitValue(lrs, i))
505 // If we don't find it in the live range hash table we are in serious trouble.
506 if (!(sym = hTabItemWithKey(liveRanges, i))) {
507 werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
508 "liveRangesWith could not find liveRange");
512 // If the function likes it, and it has registers assigned to
513 // it, add it to the return set.
514 if (func(sym, ebp, ic) && bitVectBitValue(_G.regAssigned, sym->key)) {
515 addSetHead(&rset,sym);
522 /// Returns TRUE always. Used to fetch all live ranges.
523 static int _allLRs(symbol *sym, eBBlock *ebp, iCode *ic)
528 static void _serialRegAssign(eBBlock **ebbs, int count)
532 // For each block, do...
533 for (i=0; i<count; i++) {
536 if (ebbs[i]->noPath &&
537 (ebbs[i]->entryLabel != entryLabel &&
538 ebbs[i]->entryLabel != returnLabel )) {
539 // PENDING: Dont understand.
544 // For each iCode in this block, do...
545 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
551 wassert(ic->op != IPOP);
553 // if result is present && is a true symbol
554 if (IC_RESULT(ic) && ic->op != IFX &&
555 IS_TRUE_SYMOP(IC_RESULT(ic)))
556 OP_SYMBOL(IC_RESULT(ic))->allocreq = 1;
558 // Take away registers from live ranges that end at this
560 _deassignLRs(ic, ebbs[i]);
562 // Some instructions dont need registers.
563 if (_doesntNeedRegs(ic)) {
567 // If there is no result, then it doesnt need registers.
568 if (!IC_RESULT(ic)) {
572 sym = OP_SYMBOL(IC_RESULT(ic));
574 // Does it need any registers?
575 if (sym->nRegs == 0) {
579 // Is it already split?
584 // Does it already have registers assigned?
585 if (bitVectBitValue(_G.regAssigned,sym->key)) {
589 // Will it live past this instruction?
590 if (sym->liveTo <= ic->seq) {
594 // MLH Doesnt understand this.
595 /* "Iif some liverange has been spilt at the block level
596 and this one live beyond this block then spil this
598 if (_G.blockSpill && sym->liveTo > ebbs[i]->lSeq) {
603 // Seems that this symbol needs registers. See if
604 // allocating will cause a spill.
605 willCauseSpill = _willCauseSpill(sym->nRegs);
606 spillable = _findSpillable(ic);
608 // If this is remat., then dont waste any regsiters on it.
614 // If trying to allocate will cause a spill, and nothing
615 // else is spillable then this sym looses.
616 if (willCauseSpill && bitVectIsZero(spillable)) {
621 // If this will cause a spill, and it already has a spill
622 // location then spill this if it is the least used.
623 if (willCauseSpill && sym->usl.spillLoc) {
624 symbol *leastUsed = _leastUsedLR(_liveRangesWith(spillable, _allLRs, ebbs[i], ic));
625 if (leastUsed && leastUsed->used > sym->used) {
631 // Hmm. Here we could have no registers available but
632 // we'll still try to allocate. MLH wonders how this will
635 // Mark this iCode as having registers assigned to it.
636 _G.regAssigned = bitVectSetBit(_G.regAssigned, sym->key);
639 sym->regs[0] = _allocateReg(sym->nRegs);
644 static void izt_gen(iCode *ic)
649 static DEFSETFUNC(_deallocStackSpil)
657 /// Compute the register mask for an operand.
658 bitVect *_rUmaskForOp(operand *op)
663 // "Only temporaries are assigned registers"
669 // If its spilt or no registers are needed, then no regs are assigned.
670 if (sym->isspilt || !sym->nRegs)
673 rumask = newBitVect(REG_ID_MAX);
676 rumask = _markRegBits(rumask, sym->regs[0]);
682 /// Returns bit vector of registers used in iCode.
683 bitVect *_regsUsedIniCode (iCode *ic)
685 bitVect *rmask = newBitVect(REG_ID_MAX);
688 // Special cases first.
689 if (ic->op == IFX ) {
690 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_COND(ic)));
694 if (ic->op == JUMPTABLE) {
695 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_JTCOND(ic)));
699 // Now the good old left, right, and result.
701 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_LEFT(ic)));
705 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_RIGHT(ic)));
709 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_RESULT(ic)));
716 /// Compute the helper bitVect that contains the register used mask.
717 static void _createRegMask(eBBlock **ebbs, int count)
722 for (i = 0; i < count; i++) {
725 // If this code is unused, skip it.
726 if ( ebbs[i]->noPath &&
727 ( ebbs[i]->entryLabel != entryLabel &&
728 ebbs[i]->entryLabel != returnLabel )) {
732 /* for all instructions */
733 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
736 if (SKIP_IC2(ic) || !ic->rlive)
739 // Mark the registers used in this instruction.
740 ic->rUsed = _regsUsedIniCode(ic);
741 // Mark them as used at least once in the function.
742 _G.funcUsedRegs = bitVectUnion(_G.funcUsedRegs, ic->rUsed);
744 /* now create the register mask for those
745 registers that are in use : this is a
746 super set of ic->rUsed */
747 ic->rMask = newBitVect(REG_ID_MAX+1);
749 // "For all live Ranges alive at this point"
750 for (j = 1; j < ic->rlive->size; j++) {
753 // "If if not alive then continue"
754 if (!bitVectBitValue(ic->rlive,j)) {
758 // "Find the live range we are interested in"
759 if (!(sym = hTabItemWithKey(liveRanges,j))) {
760 werror (E_INTERNAL_ERROR,__FILE__,__LINE__,
761 "createRegMask cannot find live range");
765 // "If no register assigned to it"
766 if (!sym->nRegs || sym->isspilt) {
770 // If this has any registers allocated, mark them as such.
772 ic->rMask = _markRegBits(ic->rMask, sym->regs[0]);
779 void izt_assignRegisters(eBBlock **ebbs, int count)
781 // Contains a flat version of ebbs used in code generation.
784 // Clear the bit vector of registers used in this function.
785 // Assumes that assignRegisters is called once per function.
786 setToNull((void *)&_G.funcUsedRegs);
788 // First scan each live range, and figure out what registers
790 _computeRequiredRegs();
792 // Now allocate the registers.
793 _serialRegAssign(ebbs, count);
795 // And create the helper register used mask.
796 _createRegMask(ebbs, count);
798 // Turn the bblock array into an optimised list of iCode entries.
799 chain = iCodeLabelOptimize(iCodeFromeBBlock(ebbs,count));
801 // Redo the stack offsets. This will remove any redundent stack
802 // locations ie iTemps that exist only in registers.
807 // Deallocate any stack spill locations.
808 applyToSet(_G.spill.set, _deallocStackSpil);
811 setToNull((void **)&_G.spill.set);
812 setToNull((void **)&_G.spill.vect);
814 // And free all registers.