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 = izt_port->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 = izt_port->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 = izt_port->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 = izt_port->regs;
166 static void _dumpRegs(void)
168 REG *r = izt_port->regs;
171 printf("%u\t%u\t%s\t%u\n", r->size, r->id, r->name, r->used);
176 void izt_init(IZT_PORT *port)
178 wassert(port && port->regs);
183 /// Lower register pressure by packing iTemps where possible.
184 static void _packRegisters(eBBlock *ebp)
186 // PENDING: Assignment packing
187 // PENDING: Mark address of a true symbol as remat.
188 // PENDING: Propagate remat through equals.
189 // PENDING: Assign bitwise which is followed by a conditional into carry.
190 // PENDING: Pack for one use on pointer get or set. Assumes that the pointer
191 // is stored in the scratch register.
192 // PENDING: Pack short use iTemps into ACC or the scratch register.
195 static void _computeRequiredRegs(void)
200 // Iterate over each live range.
201 for (sym = hTabFirstItem(liveRanges, &k); sym ;
202 sym = hTabNextItem(liveRanges, &k)) {
206 // If the symbol is never used, then next.
207 if ((sym->liveTo - sym->liveFrom) == 0)
210 // Only temporaries need registers.
214 // Conditionals live in carry and dont need registers.
215 if (sym->regType == REG_TYPE_CND)
219 #if 0 // PENDING. Currently we dont compute ruonly or accuse.
220 if (sym->ruonly || sym->accuse) {
221 if (IS_AGGREGATE(sym->type) || sym->isptr)
222 sym->type = aggrToPtr(sym->type,FALSE);
226 // We need registers.
227 if (IS_AGGREGATE(sym->type) || sym->isptr) {
228 // Turn an aggregate into something real.
229 sym->type = aggrToPtr(sym->type, FALSE);
232 sym->nRegs = getSize(sym->type);
233 wassert(sym->nRegs <= 4);
237 static bool _doesntNeedRegs(iCode *ic)
239 // Some types of instructions dont need registers.
240 // PENDING: Flush out the types and make processor specific.
242 ic->op == JUMPTABLE ||
252 static bool _willCauseSpill(int size)
254 return _numRegsAvailable(size) == 0;
257 static void _deassignLRs(iCode *ic, eBBlock *ebp)
264 for (sym = hTabFirstItem(liveRanges, &ignored); sym; sym = hTabNextItem(liveRanges, &ignored)) {
266 // Has this symbol expired yet?
267 if (sym->liveTo > ic->seq) {
268 // No. Cant deassign.
272 // It has expired. Free up the resources.
274 // If it was spilt, then free up the stack spill location.
276 if (sym->stackSpil) {
277 sym->usl.spillLoc->isFree = 1;
283 // If it currently has no registers assigned, then continue.
284 if (bitVectBitValue(_G.regAssigned, sym->key) == 0) {
288 // If it has no registers assigned to it, then continue.
289 if (sym->nRegs == 0) {
293 // Mark this sym as not having registers assigned.
294 bitVectUnSetBit(_G.regAssigned, sym->key);
296 // Free the registers.
297 _freeReg(sym->regs[0]);
299 // If deallocating will free up enough registers for this iCode
300 // then steal them immediatly.
301 if (IC_RESULT(ic) && !_doesntNeedRegs(ic)) {
302 result = OP_SYMBOL(IC_RESULT(ic));
303 if (result && // Has a result
304 result->liveTo > ic->seq && // and lives past this instruction
305 result->liveTo <= ebp->lSeq && // and doesnt go past this block
306 result->nRegs && // and actually needs registers
307 !result->isspilt && // and doesnt have them yet
308 !result->remat && // and wouldnt waste them
309 !bitVectBitValue(_G.regAssigned, result->key) && // doesnt have them yet
310 !_willCauseSpill(result->nRegs)
312 result->regs[0] = _allocateReg(result->nRegs);
318 /// Returns true if the live range of the given symbol doesnt overlap
319 /// with any of the live ranges in the set.
320 static bool _noOverlap (set *itmpStack, symbol *fsym)
324 for (sym = setFirstItem(itmpStack); sym; sym = setNextItem(itmpStack)) {
325 if (sym->liveTo > fsym->liveFrom) {
332 /// Set operator that returns 1 if a free spill location is found.
333 DEFSETFUNC(_stackIsFree)
336 V_ARG(symbol **,sloc);
337 V_ARG(symbol *,fsym);
339 // Dont bother if one has already been found.
343 if (sym->isFree && // This location is free...
344 _noOverlap(sym->usl.itmpStack, fsym) && // and its usage doesnt overlap with the usage of this sym
345 getSize(sym->type) >= getSize(fsym->type) && // and the location is big enough to hold the sym
347 // All good. Take this location.
357 /// Create a new spill location on the stack for this symbol.
358 symbol *_createStackSpill(symbol *sym)
362 // Try to reuse an exisiting spill location.
363 if (applyToSet(_G.spill.set, _stackIsFree, &sloc, sym)) {
364 // Found one. Take it over.
365 sym->usl.spillLoc = sloc;
366 sym->stackSpil = TRUE;
368 addSetHead(&sloc->usl.itmpStack, sym);
372 // No existing location. Time to create one.
373 // Give it a pretty name.
374 sprintf(buffer, "sloc%d", ++_G.spill.loc);
376 sloc = newiTemp(buffer);
379 sloc->type = copyLinkChain(sym->type);
380 sloc->etype = getSpec(sloc->type);
381 SPEC_SCLS(sloc->etype) = S_AUTO ;
385 // "To prevent compiler warning"
388 // Increase the local variable stack size on this function.
389 if (IN_STACK(sloc->etype)) {
390 currFunc->stack += getSize(sloc->type);
391 _G.stackExtend += getSize(sloc->type);
393 // The IZT port currently doesnt support loading locals into data space.
397 // And add it to the spill set.
398 addSetHead(&_G.spill.set, sloc);
399 sym->usl.spillLoc = sloc;
400 sym->stackSpil = TRUE;
402 // "Add it to the set of itempStack set of the spill location
403 addSetHead(&sloc->usl.itmpStack,sym);
408 static void _spillThis(symbol *sym)
410 // Create a spill location if it needs one and doesnt have one yet.
411 if (!(sym->remat || sym->usl.spillLoc)) {
412 _createStackSpill(sym);
416 // Add it to the spilt set.
417 _G.spill.vect = bitVectSetBit(_G.spill.vect, sym->key);
418 // and remove it from the 'has registers' set.
419 bitVectUnSetBit(_G.regAssigned, sym->key);
421 // Free up any registers that were assigned to this.
423 _freeReg(sym->regs[0]);
427 // CHECK: If this sym now has a spill location, mark it as allocated
428 // so that the stack packing later doesnt remove it.
429 if (sym->usl.spillLoc && !sym->remat) {
430 sym->usl.spillLoc->allocreq = TRUE;
436 static bitVect *_findSpillable(iCode *ic)
440 // First create a copy of the currently live ranges.
441 spillable = bitVectCopy(ic->rlive);
442 // Remove those which are already spilt.
443 spillable = bitVectCplAnd(spillable, _G.spill.vect);
444 // Remove those that this iCode uses.
445 spillable = bitVectCplAnd(spillable, ic->uses);
446 // Remove those that this iCode defines.
447 bitVectUnSetBit(spillable, ic->defKey);
449 // Only those that have registers assigned can actually be spilt :)
450 spillable = bitVectIntersect(spillable, _G.regAssigned);
455 /// Finds the least used live range
456 static symbol *_leastUsedLR(set *sset)
458 // sym is the currently least used symbol.
460 // walk walks the list of symbols in the scan set.
463 // Use the first as the seed.
464 sym = walk = setFirstItem(sset);
467 // Prefer spilling the symbol with the least allocated registers.
469 if (walk->used == sym->used) {
470 if (getSize(walk->type) < getSize(sym->type)) {
474 else if (walk->used < sym->used) {
475 // This is used less than the current best. It looses.
479 walk = setNextItem(sset);
482 setToNull((void **)&sset);
488 /// Applies a function to a given set of live ranges.
489 static set *_liveRangesWith(bitVect *lrs, int (func)(symbol *,eBBlock *, iCode *),
490 eBBlock *ebp, iCode *ic)
495 // Dont do anything if the bitVect is empty.
496 if (!lrs || !lrs->size)
499 for (i = 1; i < lrs->size; i++ ) {
502 // If this bit isnt turned on, skip.
503 if (!bitVectBitValue(lrs, i))
506 // If we don't find it in the live range hash table we are in serious trouble.
507 if (!(sym = hTabItemWithKey(liveRanges, i))) {
508 werror(E_INTERNAL_ERROR,__FILE__,__LINE__,
509 "liveRangesWith could not find liveRange");
513 // If the function likes it, and it has registers assigned to
514 // it, add it to the return set.
515 if (func(sym, ebp, ic) && bitVectBitValue(_G.regAssigned, sym->key)) {
516 addSetHead(&rset,sym);
523 /// Returns TRUE always. Used to fetch all live ranges.
524 static int _allLRs(symbol *sym, eBBlock *ebp, iCode *ic)
529 static void _serialRegAssign(eBBlock **ebbs, int count)
533 // For each block, do...
534 for (i=0; i<count; i++) {
537 if (ebbs[i]->noPath &&
538 (ebbs[i]->entryLabel != entryLabel &&
539 ebbs[i]->entryLabel != returnLabel )) {
540 // PENDING: Dont understand.
545 // For each iCode in this block, do...
546 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
552 wassert(ic->op != IPOP);
554 // if result is present && is a true symbol
555 if (IC_RESULT(ic) && ic->op != IFX &&
556 IS_TRUE_SYMOP(IC_RESULT(ic)))
557 OP_SYMBOL(IC_RESULT(ic))->allocreq = 1;
559 // Take away registers from live ranges that end at this
561 _deassignLRs(ic, ebbs[i]);
563 // Some instructions dont need registers.
564 if (_doesntNeedRegs(ic)) {
568 // If there is no result, then it doesnt need registers.
569 if (!IC_RESULT(ic)) {
573 sym = OP_SYMBOL(IC_RESULT(ic));
575 // Does it need any registers?
576 if (sym->nRegs == 0) {
580 // Is it already split?
585 // Does it already have registers assigned?
586 if (bitVectBitValue(_G.regAssigned,sym->key)) {
590 // Will it live past this instruction?
591 if (sym->liveTo <= ic->seq) {
595 // MLH Doesnt understand this.
596 /* "Iif some liverange has been spilt at the block level
597 and this one live beyond this block then spil this
599 if (_G.blockSpill && sym->liveTo > ebbs[i]->lSeq) {
604 // Seems that this symbol needs registers. See if
605 // allocating will cause a spill.
606 willCauseSpill = _willCauseSpill(sym->nRegs);
607 spillable = _findSpillable(ic);
609 // If this is remat., then dont waste any regsiters on it.
615 // If trying to allocate will cause a spill, and nothing
616 // else is spillable then this sym looses.
617 if (willCauseSpill && bitVectIsZero(spillable)) {
622 // If this will cause a spill, and it already has a spill
623 // location then spill this if it is the least used.
624 if (willCauseSpill && sym->usl.spillLoc) {
625 symbol *leastUsed = _leastUsedLR(_liveRangesWith(spillable, _allLRs, ebbs[i], ic));
626 if (leastUsed && leastUsed->used > sym->used) {
632 // Hmm. Here we could have no registers available but
633 // we'll still try to allocate. MLH wonders how this will
636 // Mark this iCode as having registers assigned to it.
637 _G.regAssigned = bitVectSetBit(_G.regAssigned, sym->key);
640 sym->regs[0] = _allocateReg(sym->nRegs);
645 static DEFSETFUNC(_deallocStackSpil)
653 /// Compute the register mask for an operand.
654 bitVect *_rUmaskForOp(operand *op)
659 // "Only temporaries are assigned registers"
665 // If its spilt or no registers are needed, then no regs are assigned.
666 if (sym->isspilt || !sym->nRegs)
669 rumask = newBitVect(REG_ID_MAX);
672 rumask = _markRegBits(rumask, sym->regs[0]);
678 /// Returns bit vector of registers used in iCode.
679 bitVect *_regsUsedIniCode (iCode *ic)
681 bitVect *rmask = newBitVect(REG_ID_MAX);
684 // Special cases first.
685 if (ic->op == IFX ) {
686 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_COND(ic)));
690 if (ic->op == JUMPTABLE) {
691 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_JTCOND(ic)));
695 // Now the good old left, right, and result.
697 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_LEFT(ic)));
701 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_RIGHT(ic)));
705 rmask = bitVectUnion(rmask, _rUmaskForOp(IC_RESULT(ic)));
712 /// Compute the helper bitVect that contains the register used mask.
713 static void _createRegMask(eBBlock **ebbs, int count)
718 for (i = 0; i < count; i++) {
721 // If this code is unused, skip it.
722 if ( ebbs[i]->noPath &&
723 ( ebbs[i]->entryLabel != entryLabel &&
724 ebbs[i]->entryLabel != returnLabel )) {
728 /* for all instructions */
729 for (ic = ebbs[i]->sch; ic; ic = ic->next) {
732 if (SKIP_IC2(ic) || !ic->rlive)
735 // Mark the registers used in this instruction.
736 ic->rUsed = _regsUsedIniCode(ic);
737 // Mark them as used at least once in the function.
738 _G.funcUsedRegs = bitVectUnion(_G.funcUsedRegs, ic->rUsed);
740 /* now create the register mask for those
741 registers that are in use : this is a
742 super set of ic->rUsed */
743 ic->rMask = newBitVect(REG_ID_MAX+1);
745 // "For all live Ranges alive at this point"
746 for (j = 1; j < ic->rlive->size; j++) {
749 // "If if not alive then continue"
750 if (!bitVectBitValue(ic->rlive,j)) {
754 // "Find the live range we are interested in"
755 if (!(sym = hTabItemWithKey(liveRanges,j))) {
756 werror (E_INTERNAL_ERROR,__FILE__,__LINE__,
757 "createRegMask cannot find live range");
761 // "If no register assigned to it"
762 if (!sym->nRegs || sym->isspilt) {
766 // If this has any registers allocated, mark them as such.
768 ic->rMask = _markRegBits(ic->rMask, sym->regs[0]);
775 void izt_assignRegisters(eBBlock **ebbs, int count)
777 // Contains a flat version of ebbs used in code generation.
780 // Clear the bit vector of registers used in this function.
781 // Assumes that assignRegisters is called once per function.
782 setToNull((void *)&_G.funcUsedRegs);
784 // First scan each live range, and figure out what registers
786 _computeRequiredRegs();
788 // Now allocate the registers.
789 _serialRegAssign(ebbs, count);
791 // And create the helper register used mask.
792 _createRegMask(ebbs, count);
794 // Turn the bblock array into an optimised list of iCode entries.
795 chain = iCodeLabelOptimize(iCodeFromeBBlock(ebbs,count));
797 // Redo the stack offsets. This will remove any redundent stack
798 // locations ie iTemps that exist only in registers.
803 // Deallocate any stack spill locations.
804 applyToSet(_G.spill.set, _deallocStackSpil);
807 setToNull((void **)&_G.spill.set);
808 setToNull((void **)&_G.spill.vect);
810 // And free all registers.